Pp. 31–38 of the Proceedings

Abstract

1 Motivation

Firstly, component interaction in such systems has to be highly efficient. Therefore, for over a decade, performance-oriented research focused on microkernel construction, in particular IPC performance, finally resulting in acceptable IPC overheads (100...200 cycles) [6, 2].

Secondly, component interaction has to be conveniently usable from an application programmer’s perspective. This requirement led to the development of interface-definition languages (IDLs), e.g. Corba IDL [7], DCOM [3] and their corresponding IDL compilers. From interface procedure/method definitions, such compilers generate stub code that marshals parameters on the client side, communicates through IPC or RPC kernel primitives with the server, unmarshals the parameters on the server side, invokes the corresponding server procedure/method, etc. As a result, a programmer can specify and use remote interfaces as easily as internal ones.

So far, IDL-compiler research has focused more on generating code in a portable and adaptable way than on producing efficient stubs. In fact, stub-code performance was insignificant for early microkernels that required multiple thousands of cycles per IPC. However, with high-performance IPC, stub-code efficiency becomes an issue.

For example, when using the Flick IDL compiler [4] for the SawMill Linux file system [5], we found that the generated user-level stub code consumed about 260 instructions per read request. When reading a 4K block from the file system, the stub code adds an overhead of about 17% due to stub instructions. (The stub code may also generates further indirect costs through side effects such as cache pollution.) For an industrial system, such overheads can no longer be ignored.

Hand coding of the aforementioned stub resulted in 80 instead of 260 instructions. Although this was a singular experiment, it gave us some evidence that improving stub-code generation might be worthwhile. The potentially achievable reductions justified a compiler-construction experiment to explore whether near-optimal stub code can be generated at reasonable costs.

This paper describes the resulting IDL4 compiler that generates code for gcc on x86 and the L4 microkernel. The current IDL4 is a prototype that purely focuses on generating efficient code. Portability and adaptability are ignored and remain a topic for future work.

Structure of the paper

2 Prerequisites

2.1 L4/x86 IPC

Register messages consist of a small number of 32-bit words that are sent and received in general purpose registers. On the x86 platform, up to 3 words (plus sender id and message descriptor) can be transferred as a register message. As there is no need for copy operations across address space boundaries, register messages have the lowest IPC costs, e.g. 180 cycles on a Pentium III 450 MHz.

Memory messages can be used to copy longer messages from the sender’s address space to the receiver. Message size can be up to 2MB; however, this mechanism is slower than a register message because it involves copying from/to memory, and the kernel might have to establish a temporary mapping to make both address spaces available at the same time.

Indirect strings avoid unnecessary copy operations to/from the message buffer. Up to 31 strings can be included in a memory message. On the receiver side, buffers for such strings can be specified so that the IPC can copy directly from server object to client object or vice versa. Scatter/gather permits strings to be gathered on the sender side and/or scattered on the receiver side. Thus multiple blocks can be directly transferred to a single receive buffer; a single send buffer can be split into multiple blocks. Figure 1 illustrates how a complex memory message is transferred.

Map messages map pages or larger parts of the sender’s address space into the receiver’s space. This feature enables user-level pagers and main-memory management on top of the microkernel. Special communication mechanisms based on shared regions can also be constructed.

2.2 SawMill

2.3 Flick

Flick tries to generate efficient stub code by using inline functions and macros for the generated stubs whenever possible. Nevertheless, at least when combined with gcc, this results in huge amounts of data transfer operations that are logically superfluous. In theory, a compiler should be able to remove all of them. In practice, the required data flow analysis is too complicated; consequently, inefficient code is generated.

3 Designing a Stub Model

3.1 A Simple Stub Model

The IDL compiler generates a client stub procedure M_client for each function M in the interface definition. The client stub is called locally by the client application. The fact remains hidden that the service function does not run locally, but rather in another address space or even on another computer thousands of miles away. The client stub assembles a message with all the information the server requires to complete the task, including all the parameters (marshalling).

The message is then sent to the server, and the client waits for the server’s reply. The reply message contains all out and inout result values. The client stub unpacks these values from the message and stores them in the appropriate client parameters (unmarshalling). In detail, the client stub M_client

The server programmer implements a procedure M_server on the server side for each method M of the interface definition.

The IDL compiler generates a central code pattern that handles communication, decoding, marshalling, and unmarshalling of parameters. This central server code typically includes a main loop that receives requests from clients and distributes them to the corresponding server procedures M_server. For each M_server, the IDL compiler generates a server stub that examines the request packet and retrieves the input data (unmarshalling). The stub then invokes the routine itself and finally creates a reply for the client.

An IDL compiler should generate both the main loop and the stubs automatically. Users should be able to easily modify the loop code, because they might want to implement additional features, e.g. load balancing.

In detail, a thread that waits for client requests

Steps C2, S0, and S4 are basically determined by the underlying IPC system, in our case by the L4 microkernel. Steps C4 and S2 are determined by the general-purpose compiler used, in our case gcc. Marshalling and unmarshalling, steps C1+S1 and S3+C3, are less restricted and more crucial. As our experience with Flick shows, a less optimal model can easily result in significant copy overhead for marshalling and unmarshalling.

3.2 Marshalling Through Direct Stack Transfer

Since out parameters in C are typically implemented through pointers (which are passed as in parameters), we have to extend the parameter set by pointers that point to those variables that are later sent back to the client as out parameters. Figure 3 illustrates the three basic layouts:

1. The client constructs a message that contains all in and inout values (plus optional strings). The message buffer has enough space to receive the reply message from the server.
2. The server extends the received message by pointers that make the inout and out parameters (and optional strings) accessible for the server procedure M_server. Then it invokes M_server. As a normal C function, it works on its input parameters (PTR, IN and the caller ID).
3. After returning from M_server, the stub removes pointer and in parameters from the stack, pushes the return value and an appropriate message header, and sends the resulting reply message to the client.

3.3 Complex Data Types

4 Generated Code - An Example

    int pfs_write([in] int handle,
                  [in, out] int *pos,
                  [in] int len,
                  [in] int data_size,
                  [in, size_is(data_size)] int *data);

    setupNewBuffer();
    ipcReceive();
    do {
         unpackQuery();
         callStub();
         packResponse();
         setupNewBuffer();
         ipcReplyWait();
       } while (1);

Client stub

1. Create descriptors for indirect strings. pfs_write() has one input string, *data, so a descriptor has to be created.
2. Marshal parameters. The input and inout parameters are pushed on the stack; inout parameters go first. Note that the last two parameters (len and handl) are not pushed, but loaded into the EBX and EDI registers.
3. Generate message header. The header specifies the number of dwords to be transferred for both directions, as well as one dword for the mapping function, which is not used here.
4. Load registers for IPC and supply function key. IDL4 needs to specify the send and receive buffer addresses and a timeout. The function key is transferred via registers and loaded here as well.
5. Invoke IPC call.
6. Unmarshal server output. In the case of pfs_write(), a return value and the *pos parameter must be handled. These can be transferred via registers, so the memory buffer is entirely discarded.

__inline__ extern sdword pfs_write(sm_service_t __service, sdword handl,
                                   sdword *pos, sdword len,
                                   sdword data_size, sdword *data)
{
  dword __return;
  int dummy0,dummy1,dummy2,dummy3;
  
  asm volatile (sub $8, %esp);
  asm volatile (pushl %0 ::"g" ((int)data)); // (1) push instring
  asm volatile (pushl %0 ::"g" (data_size)); // descriptor
  asm volatile (pushl %0 ::"g" (*pos));      // (2) push 2 in
  asm volatile (pushl %0 ::"g" (data_size)); // parameters
  asm volatile (
                 sub   $12, %%esp
                 
                 pushl $0xA100               // (3) msg header,
                 pushl $0x8000               // bits describe msg struct
                 pushl $0
                 
                 mov   %%esp, %%eax          // (4) ipc register setup
                 pushl %%ebp                 // save frame prt reg
                 xor   %%ebp, %%ebp          // reply msg type = short
                 mov   func_id, %%edx        // function key
                 xor   %%ecx, %%ecx          // timeouts = infinity
                 
                 int   $0x30                 // (5)
                 popl  %%ebp                 // (6) (restore frame ptr reg)
                 add  $48, %%esp             // release stack space
                 
                 : "=S" (dummy0), "=d" (__return), "=b" (*pos), "=D" (dummy3)
                 : "S" (__service), "D" (len), "b" (handl)
                 : "%eax", "%ecx"
               );
  return __return;
}

Server stub

1. Move the stack pointer to the message buffer. The message header and the function ID (which is the first dword in the payload) can be overwritten, so the new ESP points to the fifth dword in the buffer.
2. Add pointers to strings and output values. First, a pointer to *pos is pushed, then one to the input string buffer. Finally, the ID of the source thread is supplied.
3. Perform function call.
4. Create reply message. The input values and pointers are discarded, then the return value and a new message header are added.
5. Restore the stack pointer. Its original value was saved in EBP during the function call, as it is the only register that is automatically saved by gcc.

__inline__ extern void *call_pfs_write(void *buf, int com_source, int *strlist)

{
  int __return,dummy0,dummy1;
  
  asm volatile (
                 pushl %%ebp                 // (1)
                 mov   %%esp, %%ebp
                 mov   %%eax, %%esp
                 
                 mov   %%eax, %%edi          // (2)
                 add   $12, %%edi
                 pushl %%edi
                 pushl 4(%%esi)
                 pushl %%ebx
                 
                 call  _pfs_write            // (3)
                 
                 add   $24, %%esp            // (4)
                 pushl %%eax
                 pushl $0x2000
                 pushl $0x2000
                 pushl $0
                 
                 mov   %%esp, %%eax          // (5)
                 mov   %%ebp, %%esp
                 popl  %%ebp
                 
                 : "=a" (__return), "=b" (dummy0), "=S" (dummy1)
                 : "a" (buf), "b" (com_source), "S" ((int)strlist)
                 : "%ecx", "%edx", "%edi"
               );
               
  return (void*)__return;
}

5 Performance

5.1 Measurement Environment - SawMill Linux

For SawMill, we analyze the stubs that are required to let a normal Linux process execute file-system operations such as open, read, and write. The physical file system we used in the experiments is compatible to Linux’ ext2. In fact, the ext2 code was extracted from Linux and then combined with IDL4-generated server templates. The resulting ext2-compliant PFS runs as a user-level server in its own address space. Libraries have been modified such that now IDL4 stubs and L4 IPC communicate with SawMill servers. An open request is always sent first to the virtual file system (VFS) which propagates it to the corresponding PFS server. Subsequent read/write requests, however, are handled through direct communication between the user application and that PFS server, i.e., need only one RPC (two IPCs).

The normal SawMill Linux has all stubs generated by the IDL4 compiler. In addition, we generated a second version of SawMill Linux whose stubs were all generated by the Flick compiler. For both versions, we measured stub instructions and application performance.

For our measurements, we used a Pentium III running at 500 MHz with 64 MB of main memory and a 540 MB IDE disk drive (IBM DALA-3540).

5.2 Effects On IOzone Throughput

We measured reread throughput where IOzone read 4 KB² of file data per read request. Table 3 presents the overall performance results reported by IOzone (ten consecutive iterations). IDL4 improves the IOzone throughput by approximately 13%. The time for a 4-KB read request decreases from 8.0 µs to 7.0 µs. Since reread costs are dominated by the data copy costs this result can only be explained by significant improvements in stub code.

5.3 Stub-Code Instructions

Flick stubs take almost as many instructions as the microkernel needs for the IPC system call (including the message copy). Current IDL4 stubs use only half as many instructions.

6 Portability Versus Specialization

Currently, the IDL4 code generation is specialized for the gcc compiler and x86 processors. From our current experience, we can give some raw estimates about the costs to adapt IDL4 to other architectures:

New register link conditions:

Low adaptation costs, comparable to those that are required to modify the C bindings for all 7 microkernel system calls.

Different Processor:

Low adaptation costs as long as the stack layout is similar. Basically, the stub templates used by the IDL4 code generator have to be translated into the new machine/assembler language.

Different stack layout

Depending on how different the stack layout is, adaptation costs might be lower or higher. Different orderings or distances on the stack are easy; a runtime model without a stack might require designing a new data model for cross-address space parameter transfer.

Different C compiler

Easy if the C compiler offers inline asm procedures exactly like gcc. Medium-high costs if the compiler offers basically the same features but uses different syntax. Impossible or ineffective if the compiler offers no such features.

7 Conclusions

We have shown that significant performance improvements are possible. Nevertheless, it is still open, how far the current IDL4-generated stubs are from the optimum.

The optimized stub-code generation requires specialization of the IDL compiler’s code generator in two dimensions, firstly, toward the target programming language and compiler, secondly, toward the target machine. In this area, two questions are still open: (1) How specialized (with respect to acceptable efficiency) must an optimizing IDL compiler be? (2) Can we find a small set of templates and/or methods that permit easy and low-cost specialization of an optimizing IDL compiler for most existing programming-language compilers and hardware architectures?

An obvious next step therefore is to determine whether and how the current results can be generalized. An ideal solution would permit extension of the portable Flick compiler with the presented code-generation techniques.

References