CPU hanging

[Whatever5k]

I have built my kernel, that just clears the screen and prints a string out on the screen...
So that's my main.c:

Code: Select all

void kernel_start()
{
clear_screen();
printk("Hi, this is my OS booting\n");
for (;;);
}

Ok, clear_screen() works without problems, but printk() doesn't put anything on the screen...
printk() just calls my OWN vsprintf() function and then calls putc() (also written by me):

Code: Select all

* printk() - print a message on the screen */
int printk(const char *format, ...)
{
???char buffer[MAXLEN], *foo;
???va_list arg;
???int i = 0;
???
???va_start(arg, format);
???vsprintf(buffer, format, arg);???
???
???*foo = buffer[0];
???while (*(foo++) != '\0' && i++)
??????putc(*foo);

???return i;
}

So this is my self-written vsprintf() function:

Code: Select all

/* vsprintf() - dissolve conversions */
void vsprintf(char *str, const char *format, va_list ap)
{
???char *p = str;
???char *s; int d; char c;
???int size = sizeof(str);???/* against buffer-overflow */
???
???*p = '\0';
???
???/* go through format until we reach a % */
???while (*(format++) != '\0' && size-- > 0)
???{
??????if (*format != '%')???/* ordinary character */
??????{
?????????*(p++) = *format;
?????????*p = '\0';
??????}
??????
??????else
??????{
?????????switch (*(format+1))
?????????{
????????????case 'c':???/* char */
???????????????c = (char) va_arg(ap, int);
???????????????*(p++) = *(format+1);
???????????????*p = '\0';
???????????????break;??????
????????????case 's':???/* string */
???????????????s = va_arg(ap, char *);
???????????????strcat(p, s);
???????????????break;
????????????case 'd':???/* integer */
????????????case 'i':
???????????????d = va_arg(ap, int);
???????????????itoa(d, s, 10);???/* convert to string */
???????????????strcat(p, s);
???????????????break;
?????????}
??????}
???}
}????????????

And this is my putc() function:

Code: Select all

/* putc() - puts a character on the screen */
int putc(u_char c)
{
???char *video_memory = (char *) 0xb8000;???/* video memory address */
???u_int video_index = 0;
???
???/* first of all, do a lock_mutex() for
??? * security reasons...
??? */
???lock_mutex(&putc_mutex);

???switch (c)
???{
??????case '\n':???/* new line */
??????case '\r':???
?????????screen_x = 0;
?????????screen_y++;
?????????break;
??????case '\b':???/* backspace */
?????????screen_x--;???/* overwrite last character */
?????????break;
??????case '\t':???/* tabulator */
?????????screen_x += 8;
?????????break;
??????default:???/* it's an ordinary character */
?????????video_index = ((screen_y + 80) + screen_x);
?????????video_index *= 2;

?????????video_memory[video_index] = c;???/* put c into video memory */
?????????video_memory[video_index+1] = 0x07;???/* white text on black screen */

?????????/* update coordinates */
?????????screen_x++;
?????????break;
???}

???/* check if line is full */
???if (screen_x > 79)
???{
??????screen_x = 0;
??????screen_y++;
???}

???/* check if we are at the bottom of the screen */
???if (screen_y > 24)
???{
??????/* copy all lines one up */
??????memcpy(video_memory, (void*) (0xb8000+(80*2)), 24*80*2);
??????/* clear the last line */
??????memset((void*) (0xb8000+(24*80*2)), 0x0720, 80);
??????screen_y = 24;
???}

???/* now update the cursor */
???gotoxy (screen_x, screen_y);

???/* at last, unlock the mutex */
???unlock_mutex (&putc_mutex);

???/* for the moment, putc() always returns 1 which
??? * means everything is fine
??? */
???return 1;???
}

So, why does the PC hangs? I really have no idea...
I think it causes an exception (3), but I don't know why it should do that..
Please help, thanks!

[Pype.Clicker]

anything wrong with your mutex ? (is it properly initialised ? isn't your function recursive? can an interrupt occur while the mutex is hold and use printf? etc.)

Else, try to study the EIP location when the exc#03 (which one is this again ??) rises and you'll see where's the problem ....

[Whatever5k]

Well, this is the code for the mutex lock and unlock...
I call the function from C, so the parameter is put on the stack:

Code: Select all

[global lock_mutex]
lock_mutex:
   cli   ; disable interrupts
   push eax;   ; save
   push edx;   ; registers
   push ebp;
   mov ebp,esp
   mov edx,[ss:ebp+12]   ; MOV the parameter of the function to edx
   mov al,1
.loop:
   xchg [edx],al
   cmp al,1
   je .loop
   pop ebp;
   pop edx;   
   pop eax;
   ret

[global unlock_mutex]
unlock_mutex:
   push eax;
   push edx;
   push ebp;
   mov ebp,esp
   mov edx,[ss:ebp+12]
   mov byte [edx],0
   pop ebp;
   pop edx;
   pop eax;
   sti   ; enable interrupts
   ret

See anything wrong here?

[Pype.Clicker]

i can't see an initializer for putc_mutex anywhere ... you might be waiting to find a "0" value restored while what you read is the random initial value ...

[Whatever5k]

No, I have a
unsigned int putc_mutex = 0;
at the start of stdio.c

But look what Bochs sais, this message is repeated many, many times:

00021724461i[CPU ] BxError: instruction with op1=0xff
00021724461i[CPU ] nnn was 7
00021724461i[CPU ] WARNING: Encountered an unknown instruction (signalling illegal instruction):

Any idea what that means?

[Pype.Clicker]

there are chances you're jumping to a location that holds no code (but 0xffff) or that you overwrote a part of your code (less likely to happen)

[Schol-R-LEA]

Well, this is the code for the mutex lock and unlock...
I call the function from C, so the parameter is put on the stack:

Code: Select all

[global lock_mutex]
lock_mutex:
???cli???; disable interrupts
???push eax;???; save
???push edx;???; registers
???push ebp;
???mov ebp,esp
???mov edx,[ss:ebp+12]???; MOV the parameter of the function to edx
???mov al,1
.loop:
???xchg [edx],al
???cmp al,1
???je .loop
???pop ebp;
???pop edx;???
???pop eax;
???ret

[global unlock_mutex]
unlock_mutex:
???push eax;
???push edx;
???push ebp;
???mov ebp,esp
???mov edx,[ss:ebp+12]
???mov byte [edx],0
???pop ebp;
???pop edx;
???pop eax;
???sti???; enable interrupts
???ret

See anything wrong here?

I can't be sure if it is the cause of the problem you're having, but the big thing I see is that you are diabling the interrupts at the start of the lock_mutex() function, and then leaving them disabled until the end of unlock_mutex(). This is not only redundant - the whole purpose of a mutex variable is so that you don't need to have interrupts locked out for the whole time you are in the critical section - it is potentially disasterous combined with busy-waiting on the mutex variable.

As long as the interrupts are disabled, no other processes can run at all, and there is no way for the mutex variable to get changed except within you existing function. This means that, on the one hand, if the mutex value is cleared at the time of the function call, it is redundant to set it - it can't get changed by anyone else anyway. Conversely, if it is set, and you loop to test it, it will remain set forever - with the interrupts locked out, the original process can never come back to clear it, resulting in deadlock for both processes.

The whole purpose of the mutex variable is that it can be set and tested as an atomic operation to avoid race conditions. No well-behaved process (one that checks the mutex, that is) will try to use the resource while the mutex has been set by some other process, but all other functions of the OS (i.e., those depending on the interrupts) can continue unimpeded. Furhter, since individual machine operations are atomic (you can't interrupt an XCHG or BTS in the middle of its being performed), it is not necessary to . You could try something like:

Code: Select all

[global lock_mutex]
lock_mutex:
???push ebp
???mov ebp, esp
???mov edx,[ss:ebp+4]???; MOV the parameter of the function to edx

???mov al,1
.loop:
???xchg [edx],al  ; locks bus, and exchanges operands, atomically
???cmp al,1
???je .loop
???pop ebp
???ret

[global unlock_mutex]
unlock_mutex:
???push ebp
???mov ebp,esp
???mov edx,[ss:ebp+4]
??? mov al , 0
    xchg [edx],al  ; this still needs to be an atomic operation, 
                             ; even though it isn't tested against
???pop ebp
???ret

While it may not solve the problem, it should help clarify the design.

(Minor points: It is not necessary to save the EAX and EDX variables under if you are using gcc; in fact, since they are used to pass function return values, the compiler assumes they will get trashed.

It is odd though: I thought you needed to prefix assembly language functions with an underscore in order to link them with C code. It looks like you have no trouble with that, however, so I must have been mistaken.)

Personally, I prefer to use BTS and BTR, as being more compact:

Code: Select all

lock_mutex:
; ...
.loop 
   lock bts [edx], 0 ; locks the bus, copies test bit to carry flag, and sets test bit
   jc short .loop
;...

unlock_mutex:
;...
   lock btr [edx], 0
;... 

but that's a matter of coding style.

In any case, this still has a serious problem, in that it eats clock cycles with busy-waiting. You would be much better off having the scheduler support semaphores, or message-passing, or some equivalent system of process synchronization which avoids that problem - once you get to that point in your kernel, that is. Conversely, at this stage of the design, with no other processes running and no interrupts which would print to the screen set up, it is kind of pointless to be bothering with mutal exclusion at all.

[Schol-R-LEA]

In retrospect, it may be better to try a simpler approach first. If you can write a simple 'kernel' function which prints a fixed message at a fixed location on the screen, it may help narrow down where the problem lies. Try to break the whole thing down piece by piece:

Code: Select all

#define TESTONE 1

void kernel_start()
{
#ifdef TESTONE
   char str1[] = "T\00e\00s\00t\00 \00o\00n\00e\00 \00-\00 \00w\00r\00i\00t\00i\00n\00g\00 \00d\00i\00r\00e\00c\00t\00 \00t\00o\00 \00s\00c\00r\00e\00e\00n\00";
#endif
#ifdef TESTTWO
   char str2[] = "Test two - one character at a time, through putc()\n";
   int i;
   char c;
#endif
#ifdef TESTTHREE
   char str3[] = "Test Three - print string using vsprintf()\n";
#endif
#ifdef TESTFOUR
   char str4[] = "Test four - printing string with printk()\n";
#endif

/* test one - writing directly to the screen */
#ifdef TESTONE
   memcpy((char*) 0xb8000, str1, 70);
#endif

/* test two - putc()  */
#ifdef TESTTWO
   gotoxy(0, 1);
   i = 0;
   do
   {   
        c = str2[i];
        putc(c);
        i++;
    } while (NULL != c);

#endif
  
/* tests three and four left as an exercise - I'm a bit short on time right now  */

}

You get the idea - make sure each step is working properly first before going on to the next one.

[Whatever5k]

Yeah, you're right with the mutex thing...I had the same code as you show here, but anybody (I don't remember who) told me to use his code...anyway...

I do not have to add an underscore before the asm-functions, because I compile to ELF, which does not need this...

[Pype.Clicker]

i think i'm the one who uses cli/sti with its mutex-lock/unlock functions. And here's why i do so:
1) i mainly use mutexes to implement larger synchronization structures. So for instance, a mutex is only locked while updating a semaphore, not while a process wait for the semaphore to be up.
2) some of my mutexes access some structures that could be accessed by some interrupt-driven process too. Now, if you have thread 1 that 'owns' mutex M and that is (no luck) interrupted while it locks it by some handler 1# (executing in the same thread as 1, thus 1 is suspended while 1# runs ...), needing to access M in 1# will lead to a deadlock

imho, the "lock" byte of the mutex is present for multiprocessor systems.

As interrupts were disabled before any access to the mutex, when you CLI before access,
- either the mutex is free and you take it (you remain disabled, no switch can occur until you released the mutex)
- either the mutex is taken, but by another CPU, thus you're safe with your busy-waiting because this other CPU is about to release the mutex in a very soon future (as i only use that trick to protect very small critical sessions)

For sure, it's better to have atomic semaphores than using some cli/sti while modifying them, but i'm afraid you can't do "if x=0 enqueue current thread else x--" in an atomic fashion

[Schol-R-LEA]

i think i'm the one who uses cli/sti with its mutex-lock/unlock functions. And here's why i do so:
1) i mainly use mutexes to implement larger synchronization structures. So for instance, a mutex is only locked while updating a semaphore, not while a process wait for the semaphore to be up.
2) some of my mutexes access some structures that could be accessed by some interrupt-driven process too. Now, if you have thread 1 that 'owns' mutex M and that is (no luck) interrupted while it locks it by some handler 1# (executing in the same thread as 1, thus 1 is suspended while 1# runs ...), needing to access M in 1# will lead to a deadlock

Ah, now that clarifies quite a bit. In that case, blocking interrupts is reasonable enough, given the short time you're doing so. Especially if, as you seem to indicate below, that your coding the mutual exclusion code entirely in C or another HLL, and don't have direct access to an unquestionably atomic operation ('++' or '--' are usually implemented as one instruction, but there are exceptional cases and you wouldn't want second-guess your compiler unless you knew it would always emit 'DEC foo' as the only possible result of 'foo--;').

imho, the "lock" byte of the mutex is present for multiprocessor systems.

That is my understanding, too. However, I wasn't sure what kind of future design plans W5K had in mind. I wasn't sure if it was part of why he'd chosen XCHG (which locks the bus by default) rather than BTS/BTR or some other equivalent.

As interrupts were disabled before any access to the mutex, when you CLI before access,
- either the mutex is free and you take it (you remain disabled, no switch can occur until you released the mutex)
- either the mutex is taken, but by another CPU, thus you're safe with your busy-waiting because this other CPU is about to release the mutex in a very soon future (as i only use that trick to protect very small critical sessions)

Well, again, that 'very small critical sessions' were exactly what were being lost in Whatever5k's code. While it sounds like you were giving him good advice, it seems that there was some confusion on this point, which. Not a problem, though; these is some very confusing and complex issues, and it's just that kind of mistake that you often have to make before you can really understand them. Looking at how long it took to develop these
ideas in the first place, and how long it was before anyone really got them right, and you quickly get a sense of how difficult these problems realy are.

For sure, it's better to have atomic semaphores than using some cli/sti while modifying them, but i'm afraid you can't do "if x=0 enqueue current thread else x--" in an atomic fashion

Perfectly reasonable, in that case. The main issues in Whatever's code were that a) the way he wrote his code didn't require the atomic modification to span more than one assembly language instruction, and b) he wasn't renabling interrupts after he atomic modification was finished (i.e., his lock_mutex() and unlock_mutex() functions were turning off interrupts in the entire area between the lock_mutex() and unlock_mutex() calls). It was that part that seemed to be a potential problem, as it looked like a possible cause of deadlock (based on the particular set-and-test loop he was using), lost interrupts, or other system-crashing nastiness.

[Schol-R-LEA]

W5k, I was wondering what boot loader you're using (your own design, or GRUB, or BING, or whatever), and how would the IDT it sets up handle an exp#3 (the one you thought was occurring)? Have you set any interrupt handlers of your own yet?

Also, assuming that no other function references it by name, you may want to redefine putc_mutex as a static in the putc function itself. That way, it is a) globally persistent but not globally scoped, and b) clearly visible in the putc() code. I'm not sure just how gcc compiles statics in C - whether it puts them in the global heap, or if it saves the actual function stack frame - but I'm assuming the former (support for closures in C would be simply too odd and idea to deal with, and decidedly non-portable, though it could have some interesting uses...). While it would probably not change the behavior of the code, it would make it a bit cleaner.

[Whatever5k]

1) I'm using GRUB to load my kernel
2) I've set up an IDT, each descriptor having the same interrupt service routine (which does nothing than a iret at the moment)
3) So I don't have any interrupt handlers (no exception handlers either)...
4) For the moment, the exception 3 is not calling...
5) I'm debugging my code
6) putc_mutex is not defined in putc(), but is global...perhaps it is better to declare it as static...let's see...

Thanks for your answers!

[Whatever5k]

Ok, look at the that...
I've changed my kernel_start() function like this:

Code: Select all

void kernel_start(void)
{
char str[] = "Hello";
int i = 0;

clear_screen();
while (str[i] != '\0')
         putc(str[i++]);
for (;;);
}

Ok, so I just test the putc() function (same as before). The first character ('H') is printed successfully on the screen, but nothing more. I've checked some things and I know what's wrong:
At first, putc() is given a 'H' as parameter. putc() locks the mutex, prints the character on the screen and unlocks the mutex. Next, putc() is given a 'e' as parameter. putc() tries to lock the mutex, but there is the error. It can't! It keeps on looping and waiting in the lock_mutex() function. I'm sure of this...

So, what could be wrong? I suppose, unlock_mutex() is doing something wrong. I think it doesn't change putc_mutex to 0...
Do you have any ideas?

[Whatever5k]

I've got it!
I forgot that the return address is also put on the stack (it seems as if you had forgotten it, too ).
So it's not
mov edx, [ss+12]
but
mov edx, [ss+16]

So, putc() works...but my printk() function does not yet..
I'll go step by step through it now...