One way to guarantee cpu mode switches consistently with the kind of code being executed is to use a trap instruction.

The trap instruction saves the user code address and cpu user mode in the process table entry for the user.

The trap instruction then uses the integer argument to determine an entry in a kernel table containing both the kernel code address and cpu kernel mode which are loaded into the cpu's registers so that the system routine begins executing in kernel mode.

If kernel code were executed in a separate process from user processes, another possiblity for system calls might be to pass a messages between the user process and the kernel.

In this case, the kernel process code would always execute in cpu kernel mode and user process code would always execute in cpu user mode.

But to make this work, you would need to have a mechanism for passing messages.

Minix uses mechanism I, but only to implement message passing.

      int 33     ; 33 identifies the kernel sys_call function
    

Minix operating system code is structured into separate processes:

1. kernel process
2. clock process
3. process manager process
4. file system processes
5. driver manager process

To make an operating system call, an ordinary Minix user process must send a message to the appropriate Minix operating system process.

The user level library routine to send the message contains a trap operation in order to implement actually sending the message passing. The trap switches to code in the Minix kernel process which handles transferring the message to its the intended operating system process.

The function linked into user programs to send a message to an operating system process is:

int _syscall(int destination, int fncNum, message *msg);

• destination: endpoint number of the receiving operating system process
• fncNum: an integer associated with the operating system function to be executed.
• msg: the address of a message structure

The message structure should be initialized and filled in with any appropriate values to be transferred to the operating system function.

The destination operating system process will receive the message, including the fncNum, and will use this number to access a pointer the corresponding function. It then uses the pointer to invoke the function.

The function should put its results into a reply message structure located in the original caller's process table.

Finally, the reply message is transferred back to the user process. The reply is copied back by the kernel process into the message structure parameter the user process passed to _syscall.

Message primitives typically include

1. send(destination, &msg)
2. receive(source, &msg)

Messages are copied from one process's address space to another's.

Basic Issues

1. Direct/Indirect: Do the destination and source direclty specify the process or just a mailbox?
2. Buffer Capacity: How many sent messages can be stored before being received.
3. Blocking/Nonblocking: If a process sends a message does that process block until the message is received. Does a receive block the caller if no message has been sent?

If the buffer is full, an additional send operation should block in order to avoid losing the message.

If the buffer is empty, a receive operation should block.

Capacity 0: A send will block until the message is received. A receive will block until the matching send occurs. This is called a rendezvous

Bounded capacity N > 0 A send will block if the buffer is full. Receive blocks if the buffer is empty

Unbounded capacity: A send should not block. Receive blocks as usual if the buffer is empty.

1. Minix user processes can only send/receive messages to system processes, not to other user processes.

2. Minix system processes can send messages to other system processes and reply to user process messages subject to certain restrictions.

3. The following message passing functions are implemented by the kernel:
   • send
   • receive
   • sendrec (send/receive)
   • notify
   • echo

The first three use the rendezvous style message passing. So sendrec in a user process will block the user if the destination system process is currently doing something other than trying to receive an new request message.

The _syscall function used by user level programs actually uses the sendrec (send/receive) function to send a request and receive a reply.

The notify type message does not use the rendezvous. That is, it does not get blocked if the destination is not yet ready to receive the notification.

The echo is used by the kernel process for passing a message from a process to itself.

With blocking message passing primitives, Minix has to be careful to avoid deadlock.

A sends to B, but B doesn't do a receive. So A blocks

Now B sends to A. A doesn't receive because it is still blocked waiting for B to receive A's message. B blocks since A hasn't received the message. A and B would be deadlocked.

When a process attempts to send a message, Minix would need to check to see if granting the request to send could cause deadlock.

However, if A is a user level process and B is a server process, B only replies (sends) to A if it has already received from A. So in this case, the conditions of the deadlock senario don't apply.

If A is a server process and B is the user level process, B isn't allowed to send without doing a receive. So in this case also, the conditions of the deadlock senario don't apply.

What is required to add a new system call to Minix?

First, there are several system "processes", including the server processes - process manager (pm) and file system process (vfs) as well as the idle, clock, system, and kernel processes.

If you execute the command ps -ef | more, you can see that the last four are listed with negative PID's and pm has pid 0 in Minix.

A user cannot directly make a system call to the kernel or system (except for the message passing function _syscall).

So implementing a new system call available to a user must start with sending a message to a server process.

Create a new system call to get a process's pid and parent's pid.

Two new "system calls" will be available to the user as calls to:

      int mygetpid();
      int mygetppid();

We need to be familiar with a number of Minix source files and directories.

Several will be examined sometimes using the mygetpid example.

The first project will need to imitate the example.

Note that in Minix there is a distinction between tasks calls and system calls.

What is the difference?

• User level programs can only make "system calls" to Minix server processs (process manager, file manager, etc).

• Server processes and Device driver processes can make calls to the System task in the kernel code - "task calls".

Each of these "calls" is really implemented by sending a message.

• Sending a message is therefore the mechanism for Minix "system calls" and "task calls".

• Message passing itself is implemented by executing a trap instruction to switch to kernel mode and execute the kernel routine for handling sending/receiving messages.

Code to implement system calls is not linked into user level programs.

User level programs get the service of system calls by sending a message to a server process containing an integer identifying the system call to be executed.

User code must fill in a message structure with the system call's parameters (possibly none, depending on the system call).

The reply will overwrite the user's message structure with the return results.

A Minix header file contains symbolic names (preprocessor define macros) for the system call integers.

	/usr/src/include/minix/callnr.h
      

Note this header file as well as .c and .s files needed to build the Minix components are in the /usr/src subdirectories.

The system can be cleanly rebuilt (recompiled).

The recompiled versions can then be installed; that is, the header files from the /usr/src subdirectories are copied into their standard places, e.g. in /usr/include and its subdirectories.

As root, in the /usr/src/tools directory, type this command:

      make clean install
    

/usr/src/include/minix/callnr.h

 This file contains the integer codes for each system call. 

 ...
 #define FSTAT  28
 #define PAUSE  29
 #define UTIME	30
 #define ACCESS	33
 ...

• Note that 31 and 32 are not defined.

• These numbers are not currently assigned for system routines by any server process.

• So 31 and 32 and are available for new system calls directed to any server.

For our new example system call, we could add this line to callnr.h:

 ...
 #define FSTAT  28
 #define PAUSE  29
 #define UTIME	30
 #define MYGETPID 31
 #define ACCESS	33
 ...

File: /usr/src/servers/pm/table.c

  This file contains an array of function pointers that map the integers for
  system calls to the function that implements the call.

  call_vec is an array of pointers to functions of type int (*)(void)

  Entry 29 is do_pause, /* 29 = pause  */
  Entry 30 is no_sys,   /* 30 = utime  */
  Entry 31 is no_sys,   /* 31 = (stty) */

  The no_sys function is defined in several different places:

  - /usr/src/servers/pm/utility.c
  - /usr/src/servers/vfs/utility.c
  - /usr/src/servers/mfs/utility.c

  In each of these places the function just prints a message on the
  console that the function is not implemented and returns an error code: ENOSYS

The no_sys function in pm/utility.c:

  PUBLIC int no_sys()
  {
      /* A system call number not implemented by PM has been requested. */
      printf("PM: in no_sys, call nr %d from %d\n", call_nr, who_e);
      return(ENOSYS);
  }

PUBLIC and PRIVATE are preprocessor macros defined in

  /usr/src/include/minix/const.h

    #define PUBLIC   
    #define PRIVATE  static

If a function is defined in a file such as utility.c, and has the static modifier, it is not visible to the linker.

So it can't be called from any other files.

Consequently for static functions, each file can have its own 'private' version of a function.

EINVAL is defined in the header file errno.h

     #define EINVAL  (_SIGN 22) /* invalid argument */

In header files kernel.h, vfs.h, and pm.h, the macro _SYSTEM is defined (with value 1). Then errno.h is included.

In errno.h, _SIGN is defined so that it can be included by a system process or by a user process:

     #ifdef _SYSTEM
     #   define _SIGN -
     #   define  OK    0
     #else
     #   define _SIGN
     #endif

So in a system process, EINVAL will be (-22)

In a user process, EINVAL will be (22)

In /usr/src/servers/pm/table.c, change entry 31 from

    no_sys, /* 31 = not used */

to

    do_mygetpid, /* 31 = mygetpid */

The do_mygetpid function will be compiled into the pm process.

This function will be called when a user process sends a message to the pm with system call number MYGETPID.

The pm manages part of the process table (and so must have permission to access it).

The fs (file system) process manages a different part of the process table

The kernel manages yet another different part.

The process table is actually defined in separate arrays, but of the same size.

The pm's part of the process table is declared in the header file:

pm/mproc.h

Each entry of the table is of type struct mproc and the pm's whole table is an array:

struct mproc mproc[NR_PROCS];

where NR_PROCS is a macro definition for the size of the process table (maximum number of user processes).

The struct mproc entry for a given process contains the process table entries that are managed by the pm.

NR_PROCS is defined in the include file

 /usr/include/minix/config.h

which defines it in terms of _NR_PROCS in

/usr/include/minix/sys_config.h:

config.h:
#include <minix/sys_config.h>
#define NR_PROCS _NR_PROCS

sys_config.h:
#define _NR_PROCS 100

The vfs manages part of the abstract process table that deals with files.

Concretely, vfs manages a different table than the pm (but of the same size) named fproc (instead of mproc).

struct fproc fproc[NR_PROCS];

We won't be concerned with this table if we are building a system call associated to be sent to the pm.

Each of the directories,

 /usr/src/servers/pm and    
 /usr/src/servers/vfs 

has its own version of a header file:

 glo.h

In the header file included by all files in the pm directory:

pm.h 

a number of includes are for headers used by all processes and in the standard include directory /usr/src/include

 From /usr/src/include 

  #define _POSIX_SOURCE 1
  #define _MINIX 1
  #define _SYSTEM
  #include <minix/config.h>
  #include <ansi.h>
  #include <sys/types.h>
  #include <minix/const.h>
  ...

Then there are additional includes that come from /usr/src/servers/pm, the same directory in which pm.h lives:

  #include "const.h"
  #include "type.h"
  #include "proto.h"
  #include "glo.h"

All files linked into the pm executable include pm.h and so indirectly include the "glo.h" that lives in the pm's directory.

The "glo.h" file in the pm's directory defines a pointer to the slot in the process table (the pm's table) for the current process; i.e., the user process that has sent a message to the pm process.

struct mproc * mp;
    

The header file also declares several important global pm variables that are filled in for each message that is received:

message m_in;
int who_e;
int who_p;
int call_nr;

The process manager repeatedly tries to receive a message from any (user) process by calling a function: get_work.

This function calls receive, which will block until some message is sent to the process manager.

Once a message is received, the get_work function extracts information from the message about the sender and assigns values to:

• m_in - where the incomming message is placed by the kernel.
• mp - pointer to the process table entry of the user who sent the message
• who_e - the endpoint value of the same user
• who_p - the index of this user's entry in the process table.
• call_nr - the number of the user requested system call

The get_work function makes a check that the process table entry at index who_p is still being used by the user who sent the message.

To add code to the pm, it can be placed in one of the .c files that are compiled and linked into the pm executable such as misc.c.

As noted this requires no adjustment to the compilation process; in particular no change needs to be made to makefiles.

However, a header file,

 proto.h

will need to be modified so that the compiler will see the prototype of the new function being called.

/usr/src/servers/pm/proto.h

In the section for file misc.c add a PROTOTYPE declaration for the new do_xxxx. The PROTOTYPE macro generatess ANSI prototypes or KR prototypes depending on the compiler used to build minix. Yuk.

For example,

  _PROTOTYPE( int do_mygetpid, (void)                           );
  _PROTOTYPE( void setreply, (int proc_nr, int result)          );

The _PROTOTYPE macro is define like this:

#ifdef ANSI
#define _PROTOTYPE(a,b) a##b
#else
#define _PROTOTYPE(a,b) a()
#endif

When the preprocessor sees the two macro calls above it generates

If ANSI is defined, standard ANSI declarations are generated

     int do_mygetpid (void);
     void setreply (int proc_nr, int result);

else old style Kernighan-Ritchie declarations with parameter list omitted:

     int do_mygetpid();
     void setreply();

We have to write do_mygetpid function and make sure it is compiled into the pm process's executable file when Minix is recompiled.

The source files for the pm are in

  /usr/src/servers/pm

One of the files already used to build the pm process is

  /usr/src/servers/pm/misc.c

That is, the makefiles that control rebuilding Minix already build misc.o and link it into the pm executable file.

So misc.c is a "convenient" place to put a new implementation of do_xxxx so that it gets linked into the pm.

There are other choices, but they are mostly concerned with keeping related system call implementations in suitably chosen files.

We could add the function do_mygetpid to the misc.c file.

PUBLIC int do_mygetpid()
{
  /**
   * Global mp will point to the caller's process table entry.
   * Lookup information in the process table.
   * Insert this information in the reply message (also 
   * in the process table entry)
   */



  return OK;
}

This needs explanation, but for the moment note that do_mygetpid should do 2 things:

• fill in the reply message that will be sent back to the user process.
• return a value which will also be placed into the m_type part of the reply message.

If the return value is negative, say -E, the _syscall function treats this as an error and returns -1 to the user and sets the the user global variable errno to E.

Otherwise, _syscall just returns the value your do_mygetpid function returned.

To make calling the new system call look just like calling any other function, we need to write a user level "library" function that starts the system call.

Define two files mygetpid.c and the associated header file myunistd.h:

File: myunistd.h
#ifndef MYUNISTD_H
#define MYUNISTD_H
#include <lib.h>

int mygetpid();
int mygetppid();
#endif

File: mygetpid.c 

#include "myunistd.h"
int mygetpid ()
{
  message m;

        
  status = _syscall(MM,MYGETPID,&m);

  if ( status < 0 ) {
	return status;
  } else {
    return m.m1_i1;
  }
}

int mygetppid()
{
  /**
   *  same as mygetpid except return m.m1_i2;
   */
}

/usr/include/lib.h defines or includes headers that define:

1. MM (This is defined as PM_PROC_NR and identifies the receiver process as the pm).
2. MYGETPID, etc., defines for the number of each system call.

   (These are not defined directly in lib.h, but lib.h includes minix/callnr.h where they are defined.

   So in general, you don't change lib.h, but you will need to change callnr.h when adding a new system call to Minix.

3. _syscall prototype (defined in lib.h)
4. message (This is defined in minix/ipc.h which is included by lib.h)

It may also instructive to look at

/usr/src/lib/posix

For example, here is _fork.c from that directory:

    #include <lib.h>
    #define fork _fork
    #include <unistd.h>
    PUBLIC pid_t fork()
    {
      message m;
 
      return( _syscall(MM, FORK, &m) );
    }

message is a struct.

There are 7 different message formats numbered 1 - 8, but number 6 is obsolete.

All share the following fields:

    int m_source;   /* sender */
    int m_type;     /* what kind of message; e.g., the system call number */

The other fields depend on which of the 7 message formats is to be used.

The function

 _syscall(who, syscallnr, &m) 

puts the syscallnr into m.m_type for you.

So in general a user level function will not have to fill in the message type or source.

Instead the system call gets the address of the user's message and may fill in various fields as a result of executing whatever the system call implementation function does.

For functions like mygetpid() that don't have parameters, no message fields need to be filled in.

The user level function WILL need to then extract the information from the message.

At that point it is necessary to know which of the 7 message formats is being used for this system call.

Adding a system call to get the number of not-yet-waited-for children of the calling process.

(A "hello world" exercise?)

As indicated in Appendix A of the text, a suite of about 40 programs are available for testing the Minix installation.

Instructions to run the tests is given there and repeated here:

1. Log in as root.
2. Change to the /usr/src/test directory and compile the test programs:

   # cd /usr/src/test
   # make
   

3. Log in as user bin (either log out and log back in; use the command su bin or in VMware Player type one of alt-F2, alt-F4 to get another "terminal" to log in as bin.
4. Change to /usr/src/test again and run the tests:

   $ cd /usr/src/test
   $ ./run
   

   The ./ is necessary since by default, the current directory is not in bin's PATH.

The Minx libraries, code for all operating system processes can be recompiled and installed in the proper places by the following:

1. Log in as root
2. Change directories to /usr/src/tools
3. At the # prompt, type:

   # make clean install
   

4. Wait while the system is recompiled and installed.
5. Check that any users are logged out.
6. Shutdown the system:

   # shutdown
   

7. Reboot: At the boot prompt type 'menu' to get:

    1 Start Minix 3
    2 Start Custom Minix 3	  
   	

   Be sure to choose 2. This will load the new image you just built. Choosing 1 seems to boot the original boot image - which would be very confusing!

The message passing implemented in Minix is not designed for and doesn't support sending messages from user processes to other user processes.

Consequently, the kinds and size of the data in the Minix messages is predictable and reduces to a relatively small number of variations.

Unfortunately, Minix is written in the C subset of C++. In particular, there is no inheritance that would allow defining a message type with subtypes for the different variations.

So we have to work with C's approach to this.

Minix uses a union member of the message structure for the part of the message that depends on the message type (member m_type).

A union of 2 or more types only uses the storage for the largest of these types.

That is because a union of 2 or more types can only hold value(s) for one of the types at a time. So the types share the storage for a union.

Ex1. (a) Type is union blob
     (b) Variable u is declared to be of type union blob and so is
     (c) variable v.
     (d) blob is called the union tag

  union blob {
    int x;
    float y;
  } u;

  union blob v;

Ex2. (a) Union type with no tag used to declare variable u
     (b) No tag for union, so no name for the union type.
     (c) So whole union has to be repeated to declare variable v

  union {
    int x;
    float y;
  } u;

  union {
    int x;
    float y;
  } v;

The typedef declaration is used to give a name to a type expression without declaring a variable.

Example 1. Define the name intptr to be the type pointer to
int:

typedef int * intptr;

Example 2. Define the name pair to be a struct with no tag,
but with two int's:

typedef struct { int x; int y; } pair;

Example 3. Define the name number to be a union with no tag,
but with either an int or a float (sharing the same storage):

typedef union { int x; float y; } number;

Here is an example that indicates how union members are accessed.

The output also indicates that the union members share the same storage!

The value of u.x uses the same bits as u.y, but interprets them as an int instead of a float.

typedef  union {
    int x;
    float y;
  } number;

number u;

  u.y = 10.0;
  printf("u.x = %d, u.y = %f\n", u.x, u.y);

Output:
u.x = 1092616192, u.y = 10.000000

Minix message structures are C struct's with two fixed members for the message type and the message source and a union member.

The union member is a union of 7 different struct types.

Here is a slightly simlified example definition of a message structure containing a union with only 2 members instead of 7. It will be used to illustrate the approach taken in the Minix code for naming and accessing the message components.

typedef struct
{
  int m1i1;
  int m1i2;
  char* m1p1;
} mess_1;

typedef struct
{
  int m2i1;
  int m2i2;
  long m2l1;
} mess_2;

typedef struct
{
  int m_type;
  long m_source;
  union {
    mess_1 m_m1;
    mess_2 m_m2;
  } m_u;
} message;

typedef struct
{
  int m1i1;
  int m1i2;
  char* m1p1;
} mess_1;

typedef struct
{
  int m_type;
  long m_source;
  union {
    mess_1 m_m1;
    mess_2 m_m2;
  } m_u;
} message;

message msg;

Access the m1i2 member of msg and assign the value 5:

  msg.m_u.m_m1.m1i1 = 5;

Here is a more complete example.

It becomes very tedious to have to mention the union member name as well as the particular struct member of the union and finally the member of that struct.

Minix code uses preprocessor definitions to give names to a dotted expression:

Instead of

  msg.m_u.m_m1.m1i1 = 5;
  msg.m_u.m_m1.m1i2 = 10;

Minix would use this approach

#define m1_i1 m_u.m_m1.m1i1
#define m1_i2 m_u.m_m1.m1i2
   

Then the union member name, m_u doesn't need to be used at all:

  msg.m1_i1 = 5;
  msg.m1_i2 = 10;

Here is a more complete example using appropriate #defines.

Message structures are defined in the header file /usr/src/include/minix/ipc.h, which also contains the #define's to shorten the names for accessing the members of the different structs in the message union.