Understanding Re-entrant Kernels

If you ever go to a book-shop, pick up a book on "Linux Kernel Architecture" or "Unix Kernel Architecture", or maybe even a book on "Linux Kernel programming" which has topics like 'POSIX Threads', 'Processes and Signals' etc. you are bound to come across words such as 'Re-entrancy', 'Re-entrant Kernels', 'Re-entrant threads' and so on. So, what does the word "Re-entrant' mean?

This article begins to explores the depths of the Linux, in other words, the Unix Kernel architecture, in this case specifically the term "Re-entrancy". So, these are the things that will be covered:

1. An Overview of the Unix/Linux Kernel Architecture (in relation to "Re-entrancy").

2. What the term "Re-entrant Kernel" means.

3. A practical example illustrating "re-entrancy" at its best.

Please Note:

Though "re-entrancy" is an advanced topic in Linux Kernel architecture, I will try to explain all other things that need to be mentioned for proper understanding of the subject matter. The example shown at the end illustrating "re-entrant routines" uses "POSIX Threads" as its core.

I have used Red Hat Linux 7.1, Linux Kernel 2.4.2-2 for compiling all the code.

An Overview of Unix Kernels

In Unix Kernels, applications (i.e. executables) run in a specific execution environment that is provided by the Kernel. Thus, the Kernel implements a set of services, interfaces and other resources that the applications use for interacting with the hardware resources of the system (like the keyboard, monitor etc). The applications don't just directly interact with the hardware resources.

Let's look into the "Unix Process/Kernel Model" in more detail. A CPU either runs in User Mode or in Kernel Mode. (Please note however, Intel 80x86 microprocessors have four different execution states.) But, all standard Unix Kernels implements the User and the Kernel Mode.

When an application is running in User Mode, it cannot directly access the kernel programs, more precisely the Kernel data structures. But, when an application is executing in Kernel Mode, there are no restrictions on accessing the kernel data structures. An application mostly executes in the User mode, and switches to Kernel mode only when it needs to utilize a particular resource managed by the Kernel. Different CPU models govern this "switching" of an application from the User to the Kernel mode. Each CPU model provides special instructions to switch from User Mode to Kernel Mode and vice-versa when required.

Now let's talk about "processes" and "threads". A process is simply an application/program in execution. The path of execution defines a "thread". And an execution context is defined as an "apartment". In many articles and books, I have come across this line: "a "thread" is a Light-weight process". I personally feel that this definition of a "thread" is an injustice to threads! It's like defining Linux in terms of Microsoft Windows 98. 'Processes' and 'Threads' are two totally different entities and should never be defined in terms of one another. (For a very detailed coverage of "POSIX Threads", please refer to one of my forth coming articles at Linux.com.)

Now, the task of creating, eliminating and synchronizing processes is controlled by a group of routines in the Kernel. Same with POSIX threads. This group of routines are referred to as "re-entrant routines". An example illustrating "POSIX Threads using re-entrant routines" will been given later.

An important point to keep in mind while dealing with Unix/Linux Kernels is: The Kernel is not a process but only a process manager. The Process/Kernel model assumes that processes that require a kernel service utilize specific program constructs called "system calls". When a "system call" is invoked by a process (an executing program), the system call sets up a group of parameters, which then identifies the process request, then hands over the power to the CPU, which then performs the earlier mentioned "switching" of the process from User Mode to Kernel Mode.

Kernel Threads

Now, let's talk a little about "Kernel Threads". Kernel threads are very easy to understand, but extremely difficult when it comes to implementing them in the real world. Programming multithreaded applications in Linux can be an extremely hazardous task at times, and dangerous too, and is one of the most advanced stages in Linux programming. The question that arises here is: Why? The answer is: Kernel threads run in Kernel mode in the Kernel address space. (Please note: Each process runs in its private address space.) A process running in User Mode refers to a private stack, private data and code sections. When it runs in Kernel Mode (as Kernel threads do), it addresses the kernel data and code area directly. So, if you write a program that runs in User mode, and it corrupts some code section (often referred to as "malicious code"), in most cases it receives a "Segmentation fault (core dumped)" memory segmentation fault error and exits. This doesn't happen in Kernel Mode when you have a faulty Kernel Thread running, which can ultimately crash a running system.

On a uniprocessor system only one process is running at any given point in time and it may run either in User or in Kernel Mode. If it runs in Kernel Mode, the processor is executing some Kernel routine. Let's look at a transition between User and Kernel Mode more closely. Suppose we have a process named Process 1 initially running in User Mode. Process 1 issues a system call, after which Process 1 is switched to Kernel Mode and the system call is thus serviced. After the system call has been serviced, Process 1 then resumes execution in User Mode. All this time (while you were reading this section), another process named Process 2 has appeared and is waiting for its turn in User Mode. A timer interrupt occurs, and the "scheduler" in Kernel Mode is activated. Thus, a process switch takes place, Process 2 starts execution in User Mode until a particular hardware raises an interrupt. As a result of this interrupt, Process 2 switches to Kernel Mode and finally the interrupt is serviced. It then again switches back to User Mode. This is how transitions take place between the two modes.

After reading to this point, the most obvious question in the minds of the readers might be: This article was supposed to explain "Re-entrant Kernels". What has all this got to do with that? Well, a lot. Since understanding the basic operations of "Processes" and "Kernel Threads" is what re-entrancy is all about. So, let's move on to the next section.

Re-entrant Kernels

All Unix Kernels are re-entrant. This means that: "several processes may be executing in the Kernel Mode at the same time." Of course on uniprocessor systems only one process can progress at one instant in time, but the others are blocked in Kernel Mode waiting for the CPU time. For example, suppose a process issues a read to a disk. After issuing the read, the Kernel will let the disk controller handle it and in the mean while resume executing the other waiting processes. After the read from the disk has completed, an interrupt notifies the Kernel that the device has satisfied the read, and thus the former process resumes the execution. This feature in Unix Kernels(Linux Kernel) is referred to as "re-entrancy". It's like seeing the kernel as a massive and very fast switch.

Now the question that comes up is: Okay, now we know what re-entrancy means, but how is it implemented in reality? Well, one way to provide re-entrancy is to write functions so that they modify only local variables and do not alter global data structures. Such functions are referred to as "Re-entrant functions". A Kernel that implements "re-entrant routines" are referred to as "Re-entrant Kernels". Other than using "re-entrant functions", a Kernel can also use "Locking" methods to ensure that only one process can execute a non-re-entrant function at a time.

But one very significant point to keep in mind is: In Kernel Mode, every single process acts on its own set of memory locations and thus cannot interfere with the others.

On a "Re-entrant Kernel", when a hardware interrupt occurs, it is able to suspend the current running process, even if the process is in Kernel Mode. This improves the throughput of the device controllers that issue interrupts. What exactly happens is this: When a device issues an interrupt, it waits for the CPU to acknowledge. If the Kernel answers quickly, the device controller will be able to perform other tasks while the CPU handles the interrupt.

A Kernel Control Path

Soon we'll look into Kernel re-entrancy in more detail. But first, let's understand what a "kernel control path" means. A kernel control path denotes the sequence of instructions that the Kernel executes to handle a system call, an exception or an interrupt. If we consider the simplest case, the CPU executes a kernel control path sequentially from the first instruction to the last. But, this does not always happen. There are events which the CPU interleaves with the kernel control paths. Some of these events include:

1. If a process executing in User Mode invokes a system call and the corresponding kernel control path verifies that the request cannot be satisfied immediately.

2. The CPU detects an "exception". It can be of many types, for example, an access to a page not present in RAM - while running a kernel control path.

3. Hardware interrupts enabled. If a hardware interrupt occurs while the CPU is running a kernel control path. In such a case, the first kernel control path is left unfinished and the CPU starts processing another kernel control path for handling the interrupt.

Theoretically speaking, this is all that we can say about re-entrancy issues in a Unix/Linux Kernel. But as mentioned earlier, the real fun of learning this stuff begins when we create a program, and see the "re-entrant routines" in action. So, let's move on to the next section and get our hands dirty with some raw Linux Kernel programming.

Threads in action

There is a whole set of library calls associated with threads. Most of those names start with pthread_. To use these library calls, we must define the macro _REENTRANT, include the file pthread.h and then link with the threads library using -lpthread. We utilize the functionality of routines called "re-entrant routines". Re-entrant code can be called more than once, either by different threads running together, or maybe be called by thread invocations in some other way. But the significant point to note is that: The re-entrant section of code must only use local variables, and in such a way that every call to the code gets its own unique copy of the data. This is very important to note.

All the re-entrancy issues that we have discussed so far are implemented in multithreaded programs using the macro _REENTRANT. We define this macro before any #include lines in our program. Including the macro _REENTRANT in the command line when we are compiling the program does three significant things for us:

1. Some chosen functions get re-entrant safe equivalents. They have a _r appended to their initial name. For example, a function gethostbyname becomes gethostbyname_r.

2. Some stdio.h functions that are normally implemented as macros become proper re-entrant safe functions.
   The variable errno from the file errno.h is changed to call a function, whose real value can be read in a multithread safe way.

   Get a Multithreaded Program Running

   Okay, now perform the following steps to get a multithreaded program running:
   • Step 1: Boot your system into Linux, and then create a file named thread1.c

   • Step 2: Type this down neat and smooth.

     
     
     /* A Simple Threaded Program:
     By: Subhasish Ghosh
     Date: August 14th 2001
     Place: Calcutta, West Bengal, India
     */
     
     #include <stdio.h>
     #include <unistd.h>
     #include <stdlib.h>
     #include <pthread.h>
     
     void *thread_function(void *arg);
     
     char message[ ] = "Hello World";
     
     int main( )
     {
     	int res;
     	pthread_t a_thread;
     	void *thread_result;
     
      	res = pthread_create(&a_thread, NULL, thread_function, (void *)message);
     
     	if (res != 0)
     	{
     		perror("Thread creation failed.");
     		exit(EXIT_FAILURE);
     	}
     
     	printf("Waiting for thread to finish....\n");
     	res = pthread_join(a_thread, &thread_result);
     
     	if (res != 0)
     	{
     		perror("Thread join failed");
     		exit(EXIT_FAILURE);
     	}
     
     	printf("Thread joined, it returned %s\n", (char *)thread_result);
     	printf("Message is now %s\n", message);
     
     	exit(EXIT_SUCCESS);
     }
     
     void *thread_function(void *arg)
     {
     	printf("thread_function is running. Argument was %s\n", (char *)arg);
     
     	sleep(3);
     
     	strcpy(message, "Bye!");
     
     	pthread_exit("Thank you for the CPU time");
     }
     

   • Step 3: To compile this, we need to define _REENTRANT macro on the command line. So, do this now:

     cc -D_REENTRANT -o thread1 thread1.c -lpthread

   • Step 4: It should compile without any errors and you will get an object file thread1. Then execute thread1 from the command line: ./thread1 and press enter. You should see an output similar to this:

     Waiting for thread to finish...
     
     thread_function is running. Argument was Hello World
     
     Thread joined, it returned Thank you for the CPU time
     
     Message is now Bye!
     

     An Explanation

     At the top, we have declared a prototype for the function that the thread will call when we create it. This is: void *thread_function (void *arg); as required by pthread_create, it takes a pointer to void as its only argument and returns a pointer to void. In main we declare some variables. And then we call pthread_create to cause our new thread to start running.

     pthread_t a_thread;
void *thread_result;
res = pthread_create (&a_thread, NULL, thread_function, (void *)message);


     Here we pass the address of the a_thread object that refers to the instance of the newly created thread and that we can use to refer to the thread afterwards. We pass the default thread attribute, as NULL, and the final two parameters are the function to call and a parameter to pass to it.

     If the pthread_create call succeeds we now have two threads running. The original thread (which is main) continues and executes the code section lying after the pthread_create and a new thread starts executing in the function thread_function. The original thread checks that the new thread has started and then calls pthread_join. pthread_join is the thread equivalent of wait that processes use to collect child processes. The function is defined in pthread.h and is declared below:

     int pthread_join (pthread_t th, void **thread_return);

     Here we have:

     res = pthread_join (a_thread, &thread_result);

     Here we pass the identifier of the thread that we are waiting for to join and a pointer to a result. This function will wait until the thread terminates before it returns. It then prints the return value from the thread, the contents of the variable and then exits.

     In thread_function something else happens. The new thread starts executing in thread_function, prints out its arguments, sleeps for a short period, updates the global variables and then exits returning a string to the main thread. The new thread writes to the same array, message, to which the original thread has access. Thus, this multithreaded program illustrates re-entrancy, though in a very controlled and mild fashion.

     So, this brings us to the end of the world of "Re-entrant Kernels" at least for the time being. But as we have had seen earlier, creating re-entrant routines in Linux can be a whole lot of fun.

     Further Reading

     Besides the Online resources on Unix/Linux Kernels, if one wants to study about the Unix/Linux Kernels seriously in more detail, I am sure these following books would be immensely helpful.
     1. Books on UNIX Kernel:
        • The Design of the Unix Operating System; By: M.J.Bach
        • The Magic Garden Explained : The Internals of the Unix System V Release 4; By: B. Goodheart and J. Cox
        • The Design and Implementation of the 4.4 BSD Operating System; By: McKusick, Karels & Quarterman
        • Unix Internals: The New Frontiers; By: U. Vahalia
     2. Books on Linux Kernel:
        • Linux Kernel Internals; By: Bohme
        • The Linux Kernel Book; By: Dumas & Mevel
        • Linux Core Kernel Commentary; By: S. Maxwell
        • Linux Device Drivers; By: A. Rubini

     About the Author: My name is Subhasish Ghosh. I am 20 years old, currently a computer-systems engineering student in India. I am a Microsoft Certified Professional (MCP), MCSD, MCP certified on NT 4.0, recently completed Red Hat Linux Certified Engineer (RHCE) Training & cleared Brainbench.com "Linux General Administration" certification exam. I have been working with Linux for a long time now, have had programmed using C, C++, VC++, VB, COM, DCOM, MFC, ATL 3.0, PERL, Python and Linux Kernel programming.

     Latest News: Currently busy playing with POSIX threads, riding my new bike at top speed and broke-off with my girlfriend. E-mail: subhasish_ghosh@linuxmail.org