Session 11: Minix and messages

Textbook: None related

Today we're going to look at Minix source code. The textbook will step you through these two files line by line. I want to discuss the code a different way: The sequence actually executed in particular situations.

Today I want to see how Minix handles messages. What exactly happens when one process tries to send a message to another?

Message format
Minix process table
Sending a message

Message format

Minix uses the concept of a message to support communication between processes. This is used universally througout Minix whenever one process needs to access another. For example, the exit() system call will construct a message and send it on to the memory manager (the process that handles exit system calls). The handout listing lists exactly what the exit() system call accomplishes.

In memory, a message is simply a constructor. Lines 3128-3146 explain this structure. A message consists of: the process ID of the opposing process (the receiving process if the process is sending a message), an identifier telling the process what sort of message it is, and then a union for holding arguments. There is a union here to allow for a variety of sets of parameters. In the case of exit(), the relevant parameter set is mess_1, and the only argument to be sent is the m1i1 field of that. System calls with a more complex interface may have to use alternative interfaces.

Process table

Before we go on, it's important to get a quick peek at the process table. The proc structure is defined in lines 5110 to 5148 (in proc.h. The actual process table, also named proc, is declared in line 5186.

The process table includes several fields of interest, but especially notice the p_reg field on line 5111 (using the stackframe_s structure defined in 4583-4603), for the process registers, the p_nextready filed is 5143, which is to point to the next process in the ready queue after the current process.

Also important are the rdy_head and rdy_tail global variables, in lines 5192 and 5193, which point to the first and last processes in the ready queues for each priority.

Sending a message

When a process sends a message, it calls send(), and when it wants to receive a message, it calls receive(). (Since it's so frequent that a process wants to send and immediately receive a message, there's also sendrec(). In fact, Minix forces user processes to use sendrec(), since all the system calls that they might use have a return value that needs to be sent back to the user process.

Process handling in Minix is split primarily between two files: the assembler code in mpx.s (lines 5900-6491), and the C code in proc.c (lines 6900-7419).

The user process

The handout code goes through the process of building up a message and sending it to the operating system.

1. When a user program calls exit(0), control immediately transfers to the _exit() C function. You'll notice that the jump is actually to the __exit label. This is because the C compiler automatically prepends an underscore to every C function name generates.
2. The _exit() function builds the argument part of the message (which in exit()'s case is just the status argument). Then it calls _syscall to send a message of type EXIT to the memory manager process (whose process ID is the constant value MM).

3. The _syscall() function sets up the message and calls the _sendrec() assembly code. In fact the label jumped to is line 337, named __sendrec - this is again because the C compiler prepends an underscore to every function name. The arguments are passed into the function by pushing them in reverse order. So the stack has who at its top (the lowest address), follewed by msgptr, the address of the message.

4. The __sendrec label (line 337) saves the values of ebp and ebx.

5. Now the process sets up the arguments for the system call. In line 341, it loads the process ID to which the message should be sent - it loads from [ebp + 8], since ebp points to the top of the stack at 339, which at that point is the ebp value stored in line 338. The next four bytes ([ebp + 4]) is the return address within _syscall() to where the CPU should jump on a ret. And the next four bytes is the first parameter passed to __sendrec (which in this case is the memory manager). The next line loads the pointer to the message structure into ebx, and the next line loads the value 3 into ecx to indicate to the OS that it wants to both send and receive.

6. In line 344, there is interrupt with code 33, which transfers control into the operating system to handle the system call. That system call will take quite a while, but once it finishes, the __sendrec function restores the registers and returns. (It is actually returning a number indicating the success or failure of the OS in sending/receiving the message. The OS would leave such a code in eax, and the assembly code just leaves it there so it gets returned back to _syscall(). In line 208, this return code gets stored into the status variable.

The operating system

More complicated stuff occurs in the operating system. At boot time the CPU is set up to jump to _s_call. (This set-up actually happens at line 6116, though s_call itself is mentioned line 7882. But we'll get into the boot process later.)

1. When the user process does interrupt number 33, the CPU pushes the instruction pointer onto the stack. Also, the CPU automatically changes the stack pointer to point into the process table. (We'll see later how the CPU sets this up, but for now just understand that esp is actually pointing into the process table.) Finally, the CPU jumps to _s_call at line 6288.

2. The CPU then executes the instructions following line 6288. The first thing the OS does is move the stack pointer down 24-bytes, since it doesn't see a need to save those registers into the process table at this time. Lines 6292 to 6298 save several registers so that we can restore them later. It's significant that at this point the stack pointer is actually pointing to the current process's entry of the process table. So these values are stored into the p_reg structure inside of the current process's table entry.

3. Then s_call() starts playing games with the stack. Notice especially line 6274, which changes esp to point to the kernel's stack. (!) Thus, in line 6309, when we push ebx to the stack, we're pushing onto the kernel's stack, not into the process table any more. Notice that the old stack pointer (which is the position within the current process table entry) is saved in esi in 6303.

4. Interrupts are re-enabled at 6307, since now we have everything saved so that a later interrupt won't get into our way. (More precisely, a similar interrupt interrupting us will have saved everything it needs to know about us in order to restore us later where it left off.)

5. Now we make a call to sys_call(), setting up the parameters (by pushing them back onto the stack). Control transfers to proc.c, at line 7008. Remember, we're thinking that a user process is trying to perform an exit(). The arguments passed into sys_call() are BOTH for function, MM (the memory manager's process ID) for src_dest, and a pointer to the message contents for m_ptr (of which we have set the m_type field to be EXIT and the m1_i1 field to be the argument passed into exit().

6. The OS checks to make sure the destination process is reasonable at line 7023. This is just using the macro at 5172, which basically checks that the process ID is within the valid range. Line 7026 prevents user processes from doing anything other than sendrec - they can't just send or receive a message.

7. If the process has requested to send a message (which our user process has), we call mini_send at 7031. This transfers control to 7045.

8. Now we're into the confusing part. Line 7060 verifies that the user process is sending a message to a legal recipient. (Minix requires user processes to send messages only to server processes.) Line 7062 verifies that the destination process is actually still running. Ignore lines 7068-7073 - they're checking that the message pointer is actually pointing to valid memory.

9. Lines 7076-7085 check that the destination process isn't trying to send to the sending process, or to a process that's itself trying to send to the sending process, or .... If this is the case, then the processes would get deadlocked, with a cycle of processes each trying to send a message to the next one. If the OS can detect this is about to happen, it prevents it by refusing the send.

10. Lines 7088-7090 check whether the destination process is already waiting for a message. Here we branch into two possibilities.
    • Receiving process is waiting:
      If so, we do lines 7091-7095, which simply copies the message into the destination process's table entry (using CopyMess, a macro defined in lines 6932-6933, which uses the function cp_mess() defined at 8243 in klib386.s. In 7089, the destination process is marked as no longer waiting to receive. And in line 7095, the ready() function is called (assuming that now the process has nothing else on which it is blocked).
      1. The ready() function is at 7210. Its purpose is to insert a newly ready process into the proper ready queue. Lines 7220-7231 handle tasks. Lines 7232-7240 handle server processes. And lines 7241-7244 handle user processes. Then ready() returns, and then mini_send() returns.

    • Receiving process is not waiting:
      1. If, however, the receiving process was not waiting for a message, it must still be doing some computation. Minix will block the sending process until the receiving process is ready. This is handled by lines 7097-7111. In lines 7097-7101, the process table is updated to reflect that the sending process is trying to send a message, and unready() is called to remove the sending process from the ready queues.

      2. unready() is at 7258. It is some linked list code to remove the process from the appropriate queue. The only weird thing about it is that, if the removed process is the current process, then we need to pick a new process to be the current process by calling pick_proc(). This is quite likely to be the case in our situation, since proc_ptr is quite likely to still point to the user process calling exit(). (The only reason it would not is if another interrupt occurred that changed proc_ptr before we got to this point.)

      3. pick_proc() (line 7179) updates the global variable proc_ptr to point to the next process to execute. Here you can see the policy of choosing first a task, then a server, then a user process, and finally the idle process. pick_proc() then returns, and unready() returns.

      4. We're back in mini_send(). In lines 7103 to 7111, the sending process is inserted into the list of processes trying to send messages to the destination process, so that the destination process, when it is ready to receive a message, can quickly find the process waiting to send to it. We return from mini_send(), with the current process removed from the ready queue and a new process selected to run. At this point, you might think that this new process would start running. But in fact we haven't transferred control to it yet... despite the calling process being halted, the interrupt handling still continues.

11. We pick up from where we called mini_send() in line 7031. At 7039, we call mini_rec() (since in fact our user process is both sending and receiving).

12. In line 7135, we test to see whether the user process (which is now the receiving process) is blocked trying to send a message. This would be the case if earlier the receiving process (the memory manager) was not ready to receive yet.

13. If the user process is not blocked, we do lines 7137-7159. Essentially, these lines check whether somebody is blocked trying to send us a message. We go through the list trying to find somebody. If we find a match, we copy the sent message into our message buffer (line 7141), remove the sending process from our linked list, and then add the process to the appropriate ready queue with a call to ready(). We return OK, since the receive was successful.

14. Line 7154 checks for a special type of buffered message that gets saved when a hardware interrupt occurs. This really only applies to I/O tasks, to which the process manager may try to send a message when it receives a hardware interrupt that the I/O task should manage. It's not really applicable to us right now.

15. If a message isn't waiting for us to receive, we get to line 7163. In this case, we want to block, waiting for a message. Lines 7163-7166 mark the process as waiting for a message, and in line 7165 we block the process if we haven't already with a call to unready().

16. Line 7171 handles a special case that we don't want to worry about now. And line 7173 returns back to sys_call(), line 7039. Now, remember that the user process that called exit() is still going, whether or not it is still in the ready queue. It may have blocked because the receiving process wasn't ready to receive the message yet, or it may have blocked because the receiving process didn't immediately have an answer. (In the first case, it'll actually be blocked for both reasons.)

17. sys_call() returns, back to s_call(), line 6314. We copy the eax returned by sys_call() into the process table, so that this is the value that will be restored to eax when the process finally gets the CPU again.

18. At 6315, we disable interrupts, since now we're about to switch into a different process. We continue onto line 6329.

19. Ignore lines 6329-6332 - they won't happen in our case. Line 6333 makes the stack pointer point to the process that should now be entering the CPU (which probably won't be the user process that called exit() - in fact, it'll probably be the memory manager, which we probably awakened when we sent a message to it).
20. At 6334, we change the memory segments to reflect this new process. Lines 6335 and 6336 set things up so that the stack will switch into the process table again at the next interrupt (so that save will save into the process table). Then we pop off the registers we saved in lines 6263-6267, in reverse order. Finally, we execute iretd at 6345, and we're in the new process, which is likely the memory manager.