Tec Tips Reminder

what is LMA in objdump?

2011-09-02T15:22:00.000-07:00

I am wondering what is LMA in the output of objdump -h. Finally, I find this. And it explains VMA/LMA as following:

Every loadable or allocatable output section has two addresses. The first is the VMA, or virtual memory address. This is the address the section will have when the output file is run. The second is the LMA, or load memory address. This is the address at which the section will be loaded. In most cases the two addresses will be the same. An example of when they might be different is when a data section is loaded into ROM, and then copied into RAM when the program starts up (this technique is often used to initialize global variables in a ROM based system). In this case the ROM address would be the LMA, and the RAM address would be the VMA

Note: GCC - link static library

2010-05-25T09:55:00.001-07:00

We can generate our own static library. That is not a big problem. Firstly, compile the source file and then use "ar" to generate the .a library. But the problem is if you want to use you library, in GCC you have to put static library at the end of compiling command. For example, we have three file:


dummy_lib.h
dummy_lib.cc
main.cc

We create a static library with the first file:


$ g++ -c dummy_lib.cc
$ ar cvq libdummy.a dummy_lib.o
$ ranlib -t libdummy.a

Then the following statement won't work if there is something in dummy_lib is required by main.cc


$ g++ -o output -L./ -ldummy_lib main.cc

since gcc will discard the library dummy_lib before it is going to compile main.cc. Instead we have to do:


$ g++ -o output -L./ main.cc -ldummy_lib

This is kind of annoying, but have to remember.

L4 Exercises(1) - Construct Test Env in Mac OSX

2010-03-04T22:41:00.000-08:00

Just a simple introduction for how to construct experiment environment for L4-Pistachio under Mac OSX. The only requirement for my way is that you have VM Fusion installed. The model I used is consisted of two VMs. One as build machine and tftp boot server, the other as crash machine. You can argue that you can use Mac OSX as build machine. I tried and in my opinion cross compiling is possible but complicated and unclear. Although I successfully build a L4 kernel with cross compiling, I still prefer using virtual machine, since I am not good at cross compiling.

In the build VM, you need to install:

g++
autoconfig
autoheader
HG Mercury

You can get source from http://hg.l4ka.org/l4ka-pistachio with HG. You have to build kernel/ and user/ separated. Type "make" under kernel/ will give you more instructions for building it. Read README.HG for special instruments for building user/ part. It is not difficult to get it.

Since I use the build VM as tftp boot server too, I have to install tftpd on it. My host system in build VM is Ubuntu, this site will instruct you how to set up tftp server in Ubuntu. Then we have to modify VM Fusion's configuration so that crash VM can be booted through a network source.

First of all, this article is very helpful for finding configuration files of VM fusion. Two virtual networks are available after you install VM fusion, i.e. vmnet1 and vmnet8. vmnet1 is usually used for host only network, which is "private", i.e. VMs inside this network can only communicate with each other and the host system. For example, a VM inside vmnet1 can not access another one inside vmnet8. vmnet8 is NAT network. No matter what kind of network you selected for your VMs, i.e. build and crash. Both of them should be in the same network, so that they can talk to each other. To allow the tftp function, you only need to modify file dhcpd.conf under either vmnet1/ or vmnet8/, depend on your VMs network setting, and add following line:

subnet 192.168.7.0 netmask 255.255.255.0 {
    range 192.168.7.128 192.168.7.254;
    next-server 192.168.7.128;
    option broadcast-address 192.168.7.255;
    option domain-name-servers 192.168.7.2;
    option domain-name localdomain;
    default-lease-time 1800;                # default is 30 minutes
    max-lease-time 7200;                    # default is 2 hours
    option routers 192.168.7.2;
    allow booting;
    allow bootp;
}

The IP in next-server is the IP of your build VM. After this, you need to restart server with command:

    $sudo ./boot.sh --restart

Then it is ready to boot from network. One thing more for booting is that you need to download a floppy image from this site. Using it for your crash VM's floppy driver. Then your crash VM is ready for booting from build VM.

Finally, you need a way to debug the kernel. Of course you need to enable this function before you build kernel through command make menuconfig. Then you have to specify your VM to have a serial port. By default, VM fusion create a file for serial port output, but it is not useful in our case. Fortunately, it still support named pipe solution for serial port. You need go into your VMs package directory under command line and find ".vmx" file. Looking for keyword "pipe" and seting it as following:

    erial0.fileType = "pipe"
    serial0.pipe.endPoint = "server"

Also you need a tool to connect to your crash VM's serial port so that it can send command and get output from crash VM. I use minicom, which can be installed through Darwinports. To configure the minicom to connect to crash VM, you need to create a minicom file by using:

    $sudo minicom -s vmcrash

After the configuration page comes out, select "Serial port setup" and then press "A" to setup Serial Device. The path should be set like:

    unix#/Volumes/MacSpace/CrashMachine/crashvm

Then save and quit. Next time, after you start crash VM, you start minicom like:

    $sudo minicom crashvm

It will connect to the serial pipe created by crash VM.

Life in the userspace(6) - PingPong

2009-11-21T05:17:00.001-08:00

Finally, I am in this point. From now on, I am going to talk how to write a app for L4. The basic design concept in L4 is using L4 as a base layer and upon the base layer different apps is able to be hosted. Apps can also be understood as service in my opinion. L4 guys deliver three apps as example in there source tree. They are located in user/apps/. "pingpong" shows you the way to start thread in L4. "grabmem" shows you how to require memory from Sigma0. And "l4test" is a complicated app which allows user to try different APIs of L4. I will explain "pingpong" today.

"pingpong" is quite simple. It is used to test the performance of IPC, LIPC, even inter-processor IPC. It is consists of 4 threads, i.e. root thread, pager thread, ping thread, pong thread. However there can be 2 or 3 address space. Depending on which kind of IPC test you select, ping and pong threads reside either in the same AS (LIPC) or different AS (IPC).

The files used for IA32 are following:

pingpong.cc
ia32.h
crt0-ia32.S

pingpong.cc implements common codes for different architecture. ia32.h includes the special implementation of page handling and ipc in IA32 architecture. Furthermore it shows the way to measure performance in IA32 architecture.crt0-ia32.S is the C run time stub and has been discussed before.

Two points is interested here:

How to start a thread
L4 API

How to start a thread

In L4, to start a thread you need two system calls,

L4_ThreadControl
L4_SpaceControl

You have to provide them three things to create an thread: 1. thread id; 2. stack; 3. UTCB address. The steps to create a thread is as following:

Using L4_ThreadControl create an inactive thread. Here you have to provide a new unique globe thread id, space provider's thread id, scheduler's thread id and UTCB address. If space provider's thread id is the same as the new thread id, the a new address space is going to be created, otherwise thread is going to be created in the space provider's address space. Furthermore you have to leave pager's thread id as nil so that thread is created as inactive.
Using L4_SpaceControl to initial the address space. You have to provide the KIP address and the begin of UTCB area so that L4 can map or initialize the corresponding address space for the created thread. If the thread is created in an existing address space then we don't need this step.
Finally using L4_ThreadControl agian but with pager's thread id to activate the thread.
Till this point the created thread is only runnable, an startup IPC is required to let new thread run.

Two places in the pingpong's source code can be used as good example. The first place is when pager thread is created.

L4_ThreadControl(pager_tid, L4_Myself(), L4_Myself(), L4_Myself(), (void*)pager_utcb);
L4_Start(pager_tid, (L4_Word_t)pager_stack + sizeof(pager_stack) - 32, START_ADDR(pager));

Since pager reuses the address apace of root server, there is no L4_SpaceControl used and pager is created as an active thread. Since root server is the pager of pager thread, L4_Start is used directly to start pager.

Another place is where ping and pong threads are created:

L4_ThreadControl(ping_tid, ping_tid, master_tid, L4_nilthread, UTCB(0));
L4_ThreadControl(pong_tid, pong_tid, master_tid, L4_nilthread, UTCB(1));
L4_SpaceControl(ping_tid, 0, kip_area, utcb_area, &control);
L4_SpaceControl(pong_tid, 0, kip_area, utcb_area, &control);
L4_ThreadControl(ping_tid, ping_tid, master_tid, pager_tid, NOUTCB);
L4_ThreadControl(pong_tid, pong_tid, master_tid, pager_tid, NOUTCB);

IPC

This is the most important part of L4. In fact there is only one IPC system call in L4. It is always synchronized. An IPC is consists of two phases, i.e. send and receive. If you specify both "send to" and "receive from" argument in IPC. Then it is blocked on waiting for reply after it finishes sending phase. If only "send to" is specified, IPC is returned after sending phase is finished. If only "received from" is specified, IPC doesn't send anything and just waits for a message from other threads. There is a IA32 specific pingpong IPC written in ia32.h,

L4_INLINE L4_Word_t pingpong_ipc (L4_ThreadId_t dest, L4_Word_t untyped)
{
   L4_Word_t dummy;
   __asm__ __volatile__ (
   "/* pingpong_arch_ipc() */\n"
   "pushl    %%ebp        \n"
   "xorl    %%ecx, %%ecx    \n"
   "movl    %%esi, (%%edi)    \n"
#if 1
   "call    __L4_Ipc    \n"    /* jump via KIP */
#else
   "leal    1f, %%ebx    \n"    /* enter kernel directly */
   "movl    %%esp, %%ebp    \n"
   "sysenter        \n"
   "1:            \n"
#endif
   "popl    %%ebp        \n"
   : "=d" (dummy), "=S"(untyped)
   : "a" (dest), "d" (dest), "S"(untyped), "D"(__L4_X86_Utcb())
   : "ebx", "ecx" );
   return untyped;
}

I don't know why it is written in assembly. The most important is that AX and DX registers are specified as dest in the example. And both of them are the first argument of IPC system. Therefore pingpong IPC is an IPC with both "send" and "receive" phases, which means the next "send" is only possible when the previous "receive" is finished. pingpong threads both use this call to communicate with each other. The only difference between them is that ping thread is in charge of calculating performance.

Ok, I will stop here today. Next step is see how to manager the memory. See u soon.

EP(entry point) of a program

2009-11-08T14:08:00.000-08:00

I know that EP(entry point) can be different from "main", but I don't know how and why, again... I remember I found out this before, but the knowledge is lost somehow. So I will write down here again. There are two way to have an entry point of program:

Using the default entry point. It is "start", not "main". C/C++ library makes a glue and redirect the entry point to "main".
Specify a entry pointer with "-e" in linker (for sure, I am talking about the gnu linker). In L4, you will find "-e_start" in the makefile and this is why in all crt0.S, the first .global symbol is mostly "_start", i.e. it is the entry point.

Life in the userspace (5) - Sigma0 as Pager

2009-10-30T01:57:00.000-07:00

There are several confusions after my last post. One of them is how the address space of Sigma0 looks like. Following my intuition, I thought the address space is filled by kernel with 1-1 mapping, since I heard something like 1-1 mapping during my old study. For proving this I dig into kernel source code, what I found is are following factors:

Sigma0 doesn't have a pager.
Sigma0 is handled specially by L4 kernel, especially for page fault handling, since it has no pager.
Kernel doesn't mapping physical address into Sigma0's address space till there is a page fault.

You can find the prove for first point through function init_root_servers() in file kernel/src/api/v4/thread.cc, a simple code snip is like:

    TRACE_INIT ("Creating sigma0 (%t)\n", TID(sigma0));
    tcb = create_root_server( sigma0,     // tid and space
                              root_server,// scheduler
                              NILTHREAD,  // pager
                              utcb_area,
                              kip_area,
                              ROOT_UTCB_START,
                              get_kip()->sigma0.ip,
                              get_kip()->sigma0.sp);

you see, the pager is NILTHREAD.

The second point you can find the prove through member function handle_pagefault(...) in structure space_t. The implementation of this function is located in file kernel/src/api/v4/space. You will find the the page fault ipc is only going to be sent to pager when the page fault is not caused by Sigma0. For Sigma0, map_sigma0(...) is simply used.

OK, in my opinion, there are two cases where page fault is going to happen in Sigma0. Firstly, Sigma0 need memory for its own usage, for example allocate a new region_t structure. The initial number of pre-allocated region_t is 32. If they are used up, following codes is going to cause a page fault and let kernel map memory to Sigma0's address space:

region_t * region_list_t::alloc (void)
{
 if (! list)
 {
     // We might need some memory for allocating memory.
     region_t tmp;                        <-page fault could happen
     add ((L4_Word_t) &tmp, sizeof (tmp));

     // Allocate some memory to sigma0.
     L4_MapItem_t dummy;                  <- page fault could happen
     if (! allocate_page (sigma0_id, min_pgsize, dummy))
     {
         printf ("s0: Unable to allocate memory.\n");
         for (;;)
             L4_KDB_Enter ("s0: out of memory");
     }

     bool was_alloced = (list == NULL);
     if (! was_alloced)
         list = (region_listent_t *) NULL;

     // Add newly allocated memory to pool.
     add (L4_Address (L4_SndFpage (dummy)), (1UL << min_pgsize));

     if (was_alloced)
         // Swap temorary structure with a newly allocated one.
         tmp.swap (alloc ());
 }

 // Remove first item from free list.
 region_listent_t * r = list;
 list = r->next ();

 return r->region ();
}

The second one is when Sigma0 functions as pager. It will manage to allocate a MapItem, which contains the virtual address of Sigma0 to be mapped. The virtual address could contain nothing while the mapping happens, then a page fault during mapping happens and kernel will handle this page fault as I discussed above.

Finally what is 1-1 mapping? You will see map_sigma0(...) has only one address as input parameter, which means that it represents both virtual address and physical address, i.e. 1-1 mapping.

Life in the userspace (4) - Sigma0

2009-10-21T13:12:00.000-07:00

Finally, we reached the topic Sigma0. In my opinion, Sigma0 is a very simple memory manager. It arranges free memory, including I/O memory, and provides a way for root task to get memory from it. The crt0-ia32.S indicates the entry point of whole program, i.e. _start or _stext. There are two labels because different compiler need different entry point. Besides a multi boot header is also defined in crt0-ia32.S. I don't want to talk this here, you can find more information about multi bot header in my old post. The real entry point function is sigma0_main, which is implemented in sigma0.cc. If you look into sigma0.cc, you will find that Sigma0 is consisted of three steps.

Getting information from KIP region.
Using the information to initialize it memory management structures.
Entering a endless loop to wait for IPCs from other threads, e.g. kernel threads, root server.

We have talked how L4 pass KIP to user space in previous post, so I will skip the first step. The second step is initializing memory management structures. First of all, I will introduce four structures for memory management, i.e. region_t, region_listent_t, region_list_t, region_list_t. They are defined and implemented in region.cc and region.h. The idea is to manage memory with unit region_t. There are one list to store unused region_t unit and many pools to manage the memory allocation and management. The list of region_t works as a unit store. If one region_t retires from one of pool, Sigma0 will put it into this list, so that it can be reused when another pool or the same pool want a region_t for allocating a new memory block. One thing confused me for a while is the following code of region_listent_t:

    /**
     * Opaque class for holding a region_t structure.
     */
    class region_listent_t
    {
        region_t    reg;

    public:

        region_t * region (void)
        { return &reg; }

        region_listent_t * next (void)
        { return *(region_listent_t **) this; }

        void set_next (region_listent_t * n)
        { *(region_listent_t **) this = n; }
    } __attribute__ ((packed));

The next() and set_next looks weired. But the purpose is to store the next free region_t's pointer in the beginning space of current region_t structure. The following figure may explain the situation:


 ___________      ___________
|   pnext---|--->|   pnext---|---> ....
|           |    |           |
|           |    |           |
|___________|    |___________|

region_t         region_t

Since the content of region_t in free list doesn't make any sense, so L4 guy just use it as plane memory region. However, in my opinion, it is better use it with union instead of some weired tricks, this may be clearer for reader. The pools represent the memory region of different type. The allocated memory is managed by alloc_pool, the unused memories are managed by conv_momery_pool (conventional) and memory_pool (non-conventional). After allocation, a region in unused pool could be removed from pool, be split into two regions and contain reduced size.

Now come back to initialization. The initialization is simple and finished by function init_mempool_from_kip(void). There are two styles, but there is only one aim, i.e. put used memory to alloc_pool and unused memory into memory_pool and conv_memory_pool. The memory descriptor stored in KIP is used to provide base information. I remember that I have talked this in old post. After the base information is processed, Sigma0 focuses on the memories that are used by loaded service, e.g. itself, RootServer and Kdebug. These informations are also stored in KIP. alloc_memory(...) is used to register the memory used by these services.

The last step is to listen IPC from other threads. Regarding the codes the major task of Sigam0 is memory allocation. One thing I'd like to notice here is that Sigma0 grabs all memory in it's address space and uses 1-1 mapping.

I don't remember whether low 2G or low 3G address space is used for user space. I have to check this. But anyway, there will be a problem to manage more than 4G memory. I remember there is some solution for this problem.

Life in the userspace (3) - Back To Kernel Space

2009-10-13T06:05:00.001-07:00

As I planned in last post, I will go though the exception handling in this post. To better understand this post, you need to read my old post L4 pistachio Kernel (6), since in that post I explain how the default handler exc_catch_common is installed for all IDT entries. That is very interesting. I will start with the codes after for(...) loop in idt_t()'s constructor. In fact, if there is no kernel debug support required, L4 installs only 4 exception handlers in IDT table. They are:

    void exc_invliad_opcode(void)
    void exc_nomath_coproc(void)
    void exc_gp(void)
    void exc_pagefault(void)

First three are defined in file l4ka-pistachio/kernel/src/glue/v4-x86/exception.cc. The last one is defined in file l4ka-pistachio/kernel/src/glue/v4-x86/space.cc. There are two kinds of exceptions. For one kind, you will get the error code from cpu, for the other you won't. So L4 guys make 2 macros for simplifying declaration of exception handler. You can find them in file l4ka-pistachio/kernel/src/arch/x86/x32/trapgate.h. I will explain only the one for "with error code". The only difference between these two macro is one single stack operation.

/**
 * X86_EXCWITH_ERRORCODE: allows C implementation of 
 *   exception handlers and trap/interrupt gates with error 
 *   code.
 *
 * Usage: X86_EXCWITH_ERRORCODE(exc_gp)
 */
#define X86_EXCWITH_ERRORCODE(name, reason)                 \
extern "C" void name (void);                                \
static void name##handler(x86_exceptionframe_t * frame);    \
void name##_wrapper()                                       \
{                                                           \
    __asm__ (                                               \
        ".global "#name "               \n"                 \
        "\t.type "#name",@function      \n"                 \
        #name":                         \n"                 \
        "pusha                          \n"                 \
        "push   %%ds                    \n"                 \
        "push   %%es                    \n"                 \
        "push   %1                      \n"                 \
        "push   %%esp                   \n"                 \
        set_kds (eax)                                       \
        clr_dbgctl_lbr ()                                   \
        "call   %0                      \n"                 \
        set_dbgctl_lbr ()                                   \
        "addl   $8, %%esp               \n"                 \
        "popl   %%es                    \n"                 \
        "popl   %%ds                    \n"                 \
        "popa                           \n"                 \
        "addl   $4, %%esp               \n"                 \
        "iret                           \n"                 \
        :                                                   \
        : "m"(*(u32_t*)name##handler), "i"(reason)          \
        );                                                  \
}                                                           \
static void name##handler(x86_exceptionframe_t * frame)

All exc_ functions are defined, in fact, in wrapper function. The wrapper function is never called by anyone, they just reserve the space in code segment and then define the exc_ function in assembly style. In short, the macro declares and defines the exc_ functions in a very strange way... Why should this be implemented like this? no idea. Furthermore, in the end of macro, there is just a beginning of a function's implementation. If we combine the following code, you will know how the Macro is used:

X86_EXCNO_ERRORCODE(exc_nomath_coproc, X86_EXC_NOMATH_COPROC)
{
    tcb_t * current = get_current_tcb();

    TRACEPOINT(X86_NOMATH, "X86_NOMATH %t @ %p\n",
               current, frame->regs[x86_exceptionframe_t::ipreg]);

    current->resources.x86_no_math_exception(current);
}

So if you want to use the macro, you have to append at least one pair "{}" after it. Back to the previous macro, its job is simple. It saves current execution environment and jumps into real handler routine. For the exception without error code, one more line code is added:

"subl   $4, %%esp               \n"                     \

Since exception error code is pushed into stack, it is needed to simulated in no error code situation so that codes:

"addl   $8, %%esp               \n"                     \

can be used to recovery execution environment for both "with error" and "without error" situation.

I don't want to dig into how the exceptions are really handled. If you are interested, you can read exception.cc and space.cc I mentioned above.

Life in the userspace (2) - L4_KernelInterface

2009-10-03T11:55:00.000-07:00

Before I start to dig into sigma0, I would like to talk about one system call:

L4_INLINE void* L4_KernelInterface(L4_Word_t *ApiVersion,
                            L4_Word_t *ApiFlags,
                            L4_Word_t *KernelId)
{
    void * base_address;

  __asm__ __volatile__ (
        "/* L4_KernelInterface() */                 \n"
        "       lock; nop                           \n"

        : /* outputs */
        "=a" (base_address),
        "=c" (*ApiVersion),
        "=d" (*ApiFlags),
        "=S" (*KernelId)

        /* no inputs */
        /* no clobbers */
    );

    return base_address;
}

This system call is used by L4 applications to get base address of L4 kernel interface page and other three information, i.e. API version, API flags and Kernel id. I don't want to dig into the means of three API parameters, but focus on the codes. For a beginner, like me, it might very difficult to understand how the function works. There is only one inline assembly and only one line assembly codes:

"       lock; nop                           \n"

How does this line make the L4 pistachio kernel copy information to EAX, ECX, EDX and ESI? Experienced programmer may find immediately that this assembly code is invalid! This is why we call it a slow system call. In fact, the function will raise a system exception "Invalid Opcode", L4 kernel will exception handler will put necessary information into suitable registers and return back to user space. Then user space function, inline assembly will copy information from registers to the variables. The exception handler for x86 is defined in l4ka-pistachio/kernel/src/glue/v4-x86/exception.cc as:

X86_EXCNO_ERRORCODE(exc_invalid_opcode, X86_EXC_INVALIDOPCODE)

Looks like we may need to look into exception handlers in detail later. It is helpful for understand codes.

Moreover, you can find how L4 initializes IDT in post L4 pistachio Kernel(6).

Code Highlighting

2009-10-01T12:47:00.000-07:00

In order to write blog more professionally, I tried to find some website to get html codes for highlighting C/C++ code. Let's see the result:

First one from "CodeColorizer":


void * region_t::operator new (L4_Size_t size)
{
    return (void *) region_list.alloc ();
}

Second one from "toHtml":

void * region_t::operator new (L4_Size_t size)
{
    return (void *) region_list.alloc ();
}

Last one from "CodeHTMLer":

void * region_t::operator new (L4_Size_t size)
{ 
    return (void *) region_list.alloc ();
}

I like the second one in fact. And it is the easiest converter for getting html code directly.

Life in the userspace (1) - Preface

2009-10-01T06:52:00.000-07:00

One and half years ago, I described some details about pistachio kernel. I stopped after I started my first job at RTS Realtime System. Should I say I love my current job? It is better to shut up now. Anyway, meanwhile I have some time to continue my hobby and write something here. For me, I found that to write down the knowledge is much better than to keep them in my mind (I am getting older every day).

In the next few days, I will try to explore the way to write an application upon pistachio. I was looking for a program manual for pistachio, but failed. API specification is there, but that is not very useful for a beginner to start writing his application upon L4. I also found a draft of program manual, but it is far from sufficient and may be a little out-of-date.

The focus of next days is /user directory under lk4a-pistachio directory - assuming that you clone the pistachio source tree from HG repository. The road map would be like: I started from sigma0 directory and show what sigma0 is; then I will jump between lib/ and /apps to explain how an root task could be written; finally I will try write my own root task application as an exercise for myself.

There is another util/ directory under user/. I won't go into it since I have introduced kickstart/ before I introduced pistachio, while piggybacker/ is not related to x86 architecture and grubdisk is only the stuff for booting menu.

I will and must stick to my plan. ^_^

Hard to bring it back again

2009-08-03T14:32:00.000-07:00

Looks like I forget a lot of things. I have to pick them up again bit by bit. This would take a lot time..

Lazy...as always

2009-05-23T16:20:00.000-07:00

I am really lazy... I didn't do what I want to do for a long time. Can I start working on VM again? I doubt...doubt...

Finally...

2009-03-16T08:49:00.000-07:00

Finally, I have internet at home... Now I should restart blogging!

New Year and New Life

2009-01-19T01:50:00.000-08:00

I didn't update this blog for a very very long time. There are two reasons:

1. I don't have internet connection at home.
2. There is something wasting too much of my time - I get divorced.

What a bad year 2008! Anyway, I would like to restart my life together with this blog in 2009.

Good luck for myself and hope I can make something this year.

Short Notes (7) - VMWare Fusion & Minicom

2008-05-04T13:24:00.000-07:00

VMWare Fusion is the release version of VMWare on Mac OSX. It doesn't officially support serial port with "named pipe", but you can manually change the setting in ".vmx" file to use "named pipe" serial port. However, the pipe is created as "root" and cannot be written except "root" so that minicom cannot successfully use this pipe. I don't know how to change this situation, but the simplest way to work around it is starting minicom with "sudo"... That's it!

Short Notes (6) - New Plan

2008-04-29T10:53:00.000-07:00

Because of my current day job I haven't update my blog for a very long time. How to use my time well is a big challenge standing before me. Therefore, I am trying to make a schedule here so that I can regularly update this blog. After the day job I usually have 5 hours for relax and own hobbies. I would like to pick out two hours a day to learn L4. In my old plan, I should code and write at the same time, which means I should figure out how L4 works through programming a small system on L4. Now, I'd like to detail this plan here.

- One blog per week (at least).
- Two hours a day for investigating L4.
- Every week I need to find a theme (Short Note on weekend)

So what is the first theme?


###########################################
  "Create/Manipulate/Stop a thread on L4"
###########################################

God bless me to finish it this week :)

Heartbeat...Heartbeat

2008-04-24T03:20:00.000-07:00

Keep my u-kernel blog alive!!!

Short Notes (5) - .depend

2008-03-09T14:33:00.000-07:00

Yeah, I will answer the last question now. How is the ".depend" file used? "make" allows you to specify an extended script file besides "makefile" or "Makefile". So in SDI project, .depend is specified as extended script. Looking into the ".depend" file, you will find the format is just like a rule for "make" script. For example,


a.o : b.h

so, you will find that all header files for server stub is described as dependent file for some object file and their compilation rules are defined in l4.build.mk as:


$(SERV_STUBS) : ...

That's it!

Short Notes (4) - .depend

2008-03-09T10:15:00.000-07:00

It's shame to keep my blog live through writing "Short Notes"... Maybe next weekend I could write more here... In the last two weeks, I just lost my passion for a while. The reason is probably the day job. After my regular working time, no energy more for my hobby consult. Weekend.. Yeah, just spending a lot of time for relaxing... hey.

Here I would like to discuss a small technique used for compiling, source code dependence. I was wondering how the .depend files are created in L4 or SDI project. This file is used for "make" to check the file dependence among different source files, i.e. on which header files a C source file dependents. I googled in order to see how this file could be generated. However, most results indicate that dependency is mostly found out through makedepend tool which is kinda not used in SDI project. At last, through check make script, I found that gcc can also generate the dependency map through option -M and -MG. This is really interesting for me :).

Another question is how .depend file is used? Is it automatically checked by "make" or not?? Is MAKEFILES macro is preserved by "make"?

Short Note (3) - minicom

2008-03-03T03:12:00.000-08:00

I didn't post anything for a long time, since I didn't have enough energy to continue investigating L4 current. The regular work sucks me up... Last weekend, I am trying to compile L4 on Mac OS X, but failed :(. I think the problem is assembler used under Mac OS X is different from that under Linux. I will try to compile and install the latest gnu Binutil later and see whether this works. What I would like to notice here is something about minicom. Under Max OS X minicom's default directory for lockfile is /opt/var/lock, where normal user is not permitted to create, modify file. If you want to use minicom as normal user, you should change the directory path through

1. sudo minicom -s {configuration}
2. select Serial device setting
3. press B to change the directory

L4 pistachio Kernel (11)

2008-02-23T10:12:00.000-08:00

In this post I will discuss the last function in init_all_threads(), i.e. init_root_servers(), located in api/v4/thread.cc. The root servers consist of sigma0, sigma1 and root task. sigma0 is essential, whereas sigma1 and root task are optional. These 3 services don't run in kernel space, but in user space. init_root_servers() actually creates three threads for each service. In oder to create thread, we need thread number, KTCB area and UTCB area. So in the beginning of codes, init_root_servers() get the minimal thread number for user space services from UserBase field of ThreadInfo section in KIP. It then allocate to pages, represented by flex page structure in L4, to UTCB area and KIP area in new address space.


  fpage_t utcb_area = fpage_t::nilpage(),
           kip_area = fpage_t::nilpage();

The next while(...) loop is used to calculate the necessary UTCB size.


  while((1U <<>utcb_info.get_minimal_size(),
     get_kip()->utcb_info.get_utcb_size() * ROOT_MAX_THREADS ))
  size_utcb++;

Then the page structure for UTCB area and KIP area are initialized through fpage_t::set(...). You need to mention that the page size passed into fpage_t::set(...) is in log2 format. This is also the reason L4 guys use left shift operation to calculate the UTCB size. After these initialization init_root_servers() checks the special fields in KIP to consider whether there are sigma0, sigma1 and root service mapped in the memory. I have discussed these area before, you can check them out in old post. Then create_root_server(...) is used to create and initialize the address space, KTCB area and so on. It is better to talk about it detailedly.

After some checking, create_root_server(...) gets the KTCB entry for new thread from the current address space, since KTCB area should be mapped in the same phase of each address space. In order to allocate address space, it uses allocate_space() in glue/v4-x86/space.cc. This function get the memory resource from the kernel memory region represented by kmem. It also allocate the page directory for the space and uses it to initialize space_t structure. The next step is arch_init_root_server(...), which is empty in IA-32 platform. Then create_inactive(...) is used to create an thread in inactive state. It is similar to the tcb_t::create_kernel_thread(...), which I have discussed before. UTCB area and KIP area are passed to initialize new space_t structure after new thread is created and the new space_t is hooked to new KTCB. After these initialization, the thread is prepared to be executed, so tcb_t::activate(). The most important work in tcb::activate() is manipulating the kernel stack, which is achieved through tcb_t::create_startup_stack(...). Then IP and SP is set in KTCB and the thread state is changed to running. At last the new created thread is inserted into running queue of current scheduler. The the sigma0 service is up, more exactly is ready to up! I suggest you read above suffer along with the code located in api/v4/thread.cc.

The rest of init_root_servers() is using the same to create threads for sigma1 and root service.

L4 pistachio Kernel (10)

2008-02-20T13:20:00.001-08:00

In this post I'd like to investigate what init_all_threads() does. In this function there are three calls for other functions, i.e. init_interrupt_threads(), init_kernel_threads() and init_root_servers(). The duty of first function is simple,


void SECTION(".init") init_interrupt_threads()
{
  /* initialize KIP */
  word_t num_irqs = get_interrupt_ctrl()->get_number_irqs();
  get_kip()->thread_info.set_system_base(num_irqs);
  TRACE_INIT("System has %d interrupts\n", num_irqs);
}

it sets the SystemBase field of ThreadInfo in KIP to the number of hardware IRQs. The thread id lower than SystemBase is dedicated for IRQ threads in L4. And thread id between SystemBase and UserBase (another field of ThreadInfo in KIP) is used by kernel internally. The thread id above UserBase can be used by applications upon L4. For more information, please checking the L4 manual.

The next function is called init_kernel_threads(). At first, it, just like init_interrupt_threads(), initializes UserBase field. But then I am confused, because this function creates a dummy kernel thread. Why should a dummy kernel thread created? I'm not sure. However, it is worth to look how L4 create a thread (at least kernel level). You may notice that L4 has already created a thread before, i.e. idle thread. But, creating idle thread differs at least from two aspects from creating a general kernel thread. At first, idle thread has the thread id NILTHREAD, which cannot be used by other threads. Secondly, idle thread has its dedicated, per processor KTCB block, whereas the other threads will share a common KTCB array. L4 divides kernel space into four region, e.g. small space region, static kernel region, per cpu kernel region. Idle thread's KTCBs are located in per cpu region and common KTCB array is located in other kernel region. Now, let's discuss the steps for creating a kernel thread.

At first, a thread needs a thread id. The dummy kernel thread uses the lowest valid thread id, which can be retrieved by get_kip()->thread_info.get_system_base(), then threadid_t::set_global_id(...) will fill the the fields, i.e. thread number and version, in threadid_t structure. After that, you will see space_t::get_tcb(...) function. It returns the virtual address of current thread's KTCB. Be careful it ONLY return the address, the page containing such KTCB may not exist in current page table. The code in the function is like,


INLINE tcb_t * space_t::get_tcb(threadid_t tid)
{
   return (tcb_t*)((KTCB_AREA_START)
        + ((tid.get_threadno() & VALID_THREADNO_MASK) * KTCB_SIZE));
}

KTCB_AREA_START is a dedicated virtual address for the start of KTCB array. Thread number is used as index in the KTCB array. The other looks like naive. Why may not the current thread's KTCB exist in it's address space? It's better to watch video about L4 address space of MKC leture. But I will explain a little here.

In L4, each address space will synchronize their dynamic kernel area (vaddr > 0xC0000000) with the kernel space, e.g. space_t for kernel. In the beginning, KTCB array is empty (or 0 mapping? must investigate). When a thread is created, kernel first allocates an empty address space to it and then find a KTCB according to its thread number. However, the corresponding KTCB entry may not allocated in page table. So a page fault happens, the corresponding page entry is filled with a physical page address. Now the mapping only exists in the kernel space, but still not in the thread's address space. Later the KTCB is required in this thread's address space, e.g. thread switch need to retrieve current thread's KTCB. Another page fault happens in current address space and the kernel space maps corresponding physical page into current address space. OK, I just guess about this according to the knowledge I learned from MKC lecture. Don't blame me if I am wrong. I may correct this explanation sometime later :).

After the address of KTCB is retrieved. create_kernel_thread() is used for initializing the created thread. The most important thing in this function is tcb_t::init(...). At first tcb_t::init(...) use tcb_t::allocate() to ensure the physical page for this KTCB is mapped into current address space. tcb_t::allocate() uses a or instruction to touch the virtual address of KTCB. If it doesn't exist in current address space, a page fault will bring the corresponding physical page. Besides it also set the initial state, partner of the created thread. The further initialization touches myself_global, myself_local, resource (fpu_state, copy area), queue. Finally scheduler_t::init_tcb(...) sets some scheduler related parameter into KTCB and init_stack() returns the highest virtual address of current KTCB as the kernel stack point. In the end of create_kernel_threads(), the dummy thread's state is set to aborted so that it will never be executed. Now I guess that kernel creats a dummy thread in order to finish some thread related area, e.g. KTCB array in kernel space. But I am still not sure :{.

The last thing in init_all_threads() is init_root_servers(). I will discuss it next post.

L4 pistachio Kernel (9)

2008-02-18T11:47:00.000-08:00

I would like to discuss more about the system's startup. Till now things are in the kernel level. And a lot of codes for initialization are actually put things, e.g. function pointer onto stack. For example, scheduler_t::init(...) puts function pointer of idle_thread() and initial_all_threads() onto the kernel stack of idle thread. The stack looks actually like this


______________________ Highest Address of KTCB
| user level DS   |      = start_addr + KTCB_SIZE
|_________________|
| user level SP   |
|_________________|
| user level flag |
|_________________|
| user level CS   |
|_________________|
| user level ip   |
|_________________|_____
|                 |
|      ...        |      EXC_FRAME_SIZE
|                 |
|_________________|_____
| return_to_user  |
|_________________|
|  idle_thread    |
|_________________|
| init_all_threads|
|_________________|
|                 |
|                 |
|      ...        |
|                 |

You may be confused, where comes those user level stuff, and why should be exist here. I have to say that I skipped introducing create_startup_stack() function last time. It is actually important and It is the one who puts such lot user level stuff and function pointer of return_to_user() onto the stack. Of course it also puts function pointer of idle_thread(). All things above &return_to_user is used for switching from kernel level to user level. In IA-32, iret is used for automatically changing privilege level and task switch. When iret executes, CPU looks current stack pointed by ESP and fetch vary user level information and restores the interrupted execution environment so that interrupted user application can continue its work. In legend OS, kernel level is only entered when interrupts or exceptions happen. In order to prove this, let's see what actually needs intervention from kernel. In common, there are two situations, i.e system calls and hardware interrupts. For hardware interrupts, it is already clear from its name that it uses iret to go back to user level. For system calls, you need to know that they are usually implemented through exception. For example, some systems dedicate INT 0x80 (software exception) for system calls. When user application invokes system call, it actually raises an exception. Of course, the return from exception is also achieved by iret instruction. But in modern system, there is an alternative for exception and iret, i.e sysenter & sysexit. They works faster than iret and sysexit doesn't require OS provides user level information, except IP and SP, since the calling convention in programming language, i.e. C/C++ will have to preserve these information. In simple words, sysenter and sysexit are more like function call and return, whereas exception and iret are different at all.

At last, let's recall the scheduler_t::start(...) function and see what happens when this function is called. initial_switch_to(...) is the major body of scheduler_t::start(...). As we saw in last post, there are only two assembly statement. The first moves stack's address of idle thread into esp, and the second ret instruction direct retrieve the function pointer of init_all_threads() and starts executing this function. The return point of init_all_threads() will redirect to start of idle_thread(). Since idle_thread() never returns, the rest of idle thread's stack may never be used.

OK, now I stop here today. The pace of my post may be slower in the future, since one side I will start my normal work from tomorrow and other side the codes are more and more complex than before now. I need more time to understand them and write down my thought.

L4 pistachio Kernel (8)

2008-02-17T01:28:00.000-08:00

Today I will try to finish reading the routine startup_system(). Last time we stopped after init_mdb(). The next general step is initializing the kernel debugger. The function pointer kdebug_init() is only effective when you turn on the kernel debug option in kernel configuration. It is put into KIP in the file api/v4/kernelinterface.cc. The real definition for kdebug_init() is located in l4ka_pistachio/kernel/kdb. I will talk it more when I discuss kernel debugger.

Following the initializing for kernel debugger there is initialization routine for interrupt controller. get_interrupt_ctrl() returns a variable named intctrl, which is defined in file platform/generic/intctrl-pic.cc or platfor/generic/intctrl-apic.cc. I only discuss the legend interrupt controller, so I focus on intctrl-pic.cc. In the routine init_arch() you will see, L4 initialize all 15 hardware vector in IDT with function hwirq_x(), where x represents interrupt number, e.g. 1. The definition of hwirq_x is achieved by Macro HW_IRQ(x) which is located in file glue/v4-x86/x32/hwirq.h. Using macro to define function is at least widely used in system programming, especially for those very similar functions. For example hwirq_x() functions are only differed by interrupt number from each other. The most code settles in hwirq_x() functions is same. However using Macro increasing the difficulty for reader, since they usually cannot find out the declaration through searching the function name. Looking into the Macro,


  __asm__ (                                                   \
      "   .section .text                  \n"\
      "   .align 16                   \n"\
      "   .global hwirq_"#num"                \n"\
      "   .type hwirq_"#num",@function            \n"\
      "hwirq_"#num":                      \n"\
      "   pusha           /* save regs    */  \n"\
      "   pushl   %ds                 \n"\
      "   pushl   %es                 \n"\
      "   pushl   $"#num"     /* irq number   */      \n"\
      "   jmp hwirq_common    /* common stuff */      \n");

you will find all interrupt handlers are redirected to function hwirq_common(), which is defined through Macro HW_IRQ_COMMON().


  __asm__(                            \
  "   .section .text                  \n"\
  "   .align 16                   \n"\
  "   .globl hwirq_common             \n"\
  "hwirq_common:                      \n"\
  "   pushl   $intctrl    /* this pointer */  \n"\
  __SET_KDS                       \
  "   call    intctrl_t_handle_irq            \n"\
  "   addl    $8,%esp     /* clear stack  */  \n"\
  "   popl    %es                 \n"\
  "   popl    %ds                 \n"\
  "   popa            /* restore regs */  \n"\
  "   iret                        \n"\
  );

so now we know intctrl_t_handle_irq is final handler for all interrupt in L4. So where is this function? I find answer in platform/generic/intctrl-pic.h. See the last function declaration in class generic_intctrl_t.


  void handle_irq(word_t irq) __asm__("intctrl_t_handle_irq");

It looks like handle_irq() will be renamed to intctrl_t_handle_irq after compiling. Note, in GCC __asm__ can only be put after function declaration, not definition. That means:


  void func1( ... ) __asm__("..."); // legal

  void func1( ... ) __asm__("...") { ... } // illegal

The handle_irq() masks and acknowledges the hardware interrupt and tries to find a user level interrupt handler through handle_interrupt() function. I will discuss this when I talk about L4 API about interrupt later.

After the vectors in IDT are initialized. The master and slave interrupt controller are hardware initialized. One interrupt controller (i8259) can only handle 8 interrupt request. In order to achieve 15 interrupts, an additional interrupt controller is necessary, i.e. slave i8259. The slave is connected with pin 2 of master. In the code, i8259 is represented by i8259_pic_t class template in file platform/pc99/8259.h. Master and slave are defined as follow in generic_intctrl_t class,


  i8259_pic_t<0x20> master;
  i8259_pic_t<0xa0> slave;

0x20 and 0xa0 are port address for master and slave i8259 controller. In IA-32, I/O ports are used to communicate with hardware. The i8259_pic_t::init(...) routine tells controller the base address of interrupt vectors it can use, the slave id if it is master and the initial mode. These purposes are all achieved by port operations.

After interrupt controller is initialized, L4 tries to initial the hardware timer. The hardware timer is represented by timer_t class, which is defined in glue/v4-x86/timer.cc. timer_t::init_global() is used for initializing. At first it changes the interrupt vector entry in IDT. Then it uses rtc_t class to hardware initialize the timer. rtc_t is defined in platform/pc99/rtc.h. The hardware operation is achieved similar to i8259 through I/O port.

The code after timer initialization is for SMP initialization. I don't talk about SMP currently, so I just skip it and see the initialization for scheduler. Scheduler is represented by scheduler_t in file api/v4/scheduler.h and api/v4/scheduler.cc. The most work of scheduler_t::init(...) does is to create and initialize the idle thread.


   get_idle_tcb()->create_kernel_thread(NILTHREAD, &__idle_utcb);
   get_idle_tcb()->set_space(get_kernel_space());
   get_idle_tcb()->myself_global.set_raw((word_t)0x1d1e1d1e1d1e1d1eULL);
   get_idle_tcb()->create_startup_stack(idle_thread);
   if( bootcpu )
       get_idle_tcb()->notify(init_all_threads);

get_idle_tcb() return's idle thread's tcb_t structure. create_kernel_thread() is used for allocating thread ID and filling utcb field in tcb_t structure. set_space() sets the space_t pointer. my_global.set_raw(...) sets the global TID. At last a startup stack is created for idle thread, and the entry point is idle_thread(). How L4 creates and initializes thread will be detailed discussed when I investigate the API implementation of L4. At last, notify() will be call to set return point in stack to the function point of init_all_threads(). I will discuss this in next post, now I will explain idle_thread(), which look like:


   while(1)
   {
   if (!get_current_scheduler()->schedule(get_idle_tcb()))
   {
       spin(78, get_current_cpu());
       processor_sleep();
   }
   }

you see this is an endless loop, so this thread will never return. In processor_sleep(), instruction is used for stop CPU execution. The execution resumes when an external interrupt happens, e.g. timer interrupt. x86_sleep() in arch/x86/cpu.h is used by processor_sleep() to achieve the implementation with hlthlt.


   INLINE void x86_sleep(void)
   {
       __asm__ __volatile__(
           "sti   \n"
           "hlt   \n"
           "cli   \n"
           :);
   }

before hlt, sti will enable the interrupt flag in EFLAGS, after that the flag will be cleared so that current interrupt can be handled. After init() routine scheduler_t::start() routine will set the cpu that initial thread will run on and switch the stack to the initial thread (idle thread).


   INLINE void NORETURN initial_switch_to (tcb_t * tcb)
   {
       asm("movl %0, %%esp\n"
       "ret\n"
       :
       : "r"(tcb->stack));
       while (true)
       /* do nothing */;
   }

the ret instruction will jump to the function entry pushed on the idle_stack. Then the system startup finishes.

L4 pistachio Kernel (7)

2008-02-15T12:08:00.000-08:00

Since the next step is about initializing mapping database, it is better to shortly introduce mapping and mapping database before I go deeply.

Mapping is a mechanism in L4 to share memory or allocate memory. A physical memory page can be mapped into different address spaces, but there is only one owner of this page. This owner can allow the other to map its memory page into their address space within permitted access right. The receivers can also give their received pages to other requesters, however the granted right cannot exceed what they received from owner. So you see, a lot of address space can have the same physical page. This implements the memory sharing. The owner can also give up his ownership of one page, so the one who mapped this page will own the page, this might be used as memory allocation. The latter one is unusual, because I think the memory manager should own all memory page and never give up the ownership so that it can monitor the memory usage. In fact, mapping with sharing can also achieve memory allocation. One important thing is that the the giver can take back page from all sub-mapped address space. For example, A, B, C, D are for address space, a page is mapped from A to B, from B to C, and from C to D. If A want to take back mapped page (unmap) from B then C and D also lose this page. In order to achieve this effect, mapping database is introduced to manage the hierarchical mapping relationship. The relationship is constructed as a tree. When a unmapping happens, L4 will search the tree and find the node that revoke the unmapping. Then according to each child and sub-child of this node, it find out the corresponding address space and remove the physical page from it. For more information, please read the Joshua's slides about L4 and watch his video about mapping. I thought, maybe I should put them on line sometimes.

Now let's see the init_mdb() function. At first, I'd like to introduce some classes about mapping database, i.e. mapnode_t, rootnode_t and dualnode_t. I think mapnode_t is used to represent the address space received a mapping. rootnode_t represents the owner of physical page. What dualnode_t represents, I am still not sure now. Looking into init_mdb() may help a little. It first creates a array for root nodes by using mdb_create_roots(). This array covers the whole rage of possible address space of platform. But every node represents the biggest size of page supported by platform. For example, IA-32 supports 4M page and the address space is 4G, the number of entries in this array is 4G/4M = 1024. See the following code,

dual =
    mdb_create_dual(NULL,mdb_create_roots(mapnode_t::size_max);

static NOINLINE
rootnode_t * mdb_create_roots (mapnode_t::pgsize_e size)
{
    rootnode_t *newnodes, *n;

    word_t num = mdb_arraysize (size);
    newnodes =
       (rootnode_t *) mdb_alloc_buffer(sizeof(rootnode_t)*num);

    for (n = newnodes; num--; n++)
    n->set_ptr ((mapnode_t *) NULL);

    return newnodes;
}

INLINE word_t mdb_arraysize (mapnode_t::pgsize_e pgsize)
{
    return 1 << (mdb_pgshifts[pgsize+1]-mdb_pgshifts[pgsize]);
}

The first assignment is located in init_mdb(), where size_max represents 4M page. You can find this meaning in arch/x86/x32/ptab.h and arch/x86/pgent.h by searching X86_PGSIZES. Following the sequence of function call you will see in mdb_arraysize() the maximal address space size is retrieved though max page size. It will be cleaner if you see pgsize_e and mdb_pgshifts[]. Actually pgsize_e is used as index in array mdb_pgshifts[], each entry represents a supported page size by platform. mdb_arraysize() converts the index finally into real page size.

The node array is assigned to a created dual node and the map node in dual node is assigned as NULL. The dual node is assigned to sigma0's map node, which means sigma0 can control a whole address space because of the root node array. Note, this still doesn't mean sigma0 own all physical memory. They are still not mapped into its address space.

After initialization for sigma0's map node. A page size support checking is executed. Then init_mdb() finishes its work...

L4 pistachio Kernel (6)

2008-02-14T03:04:00.000-08:00

Let's continue the reading today. After setup_gdt() comes idt.activate(). This is similar to how people activates GDT and TSS,

void SECTION(".init.cpu")
 idt_t::activate()
 {
     x86_descreg_t ide((word_t)descriptors,sizeof(descriptors));
     idt.setdescreg(x86_descreg_t::idtr);
 }

These codes are located in glue/v4_x86/idt.cc. It fill the value into IDTR. However, what more interesting is how IDT is initialized. The initialization filled each exception handler, by default, exc_catch_common. The codes for initialization follows the above codes and reside in class constructor idt_t(). The most confused codes is the first loop in idt_t().

exc_catch_all[i] =
     ((sizeof(exc_catch_all)-i*sizeof(u64_t)-5)<<8)|0xe8;
 add_int_gate(i, (func_exc) &exc_catch_all[i]);

In order to understand this loop, it is necessary to read three files, i.e. exception.cc, linker-pc99.lds under directory glue/v4-x86/x32 and glue/v4-x86/exception.cc. In the linker-pc99.lds you will find that exc_catch_all[] array and exc_catch_common handler are put side by side. I describe this situation as follow,


________________
|                |
|                |
|                |
|                |
|                |
.                .
. exc_catch_all  .
.                .
.                .
|                |
|                |
|                |
|                |
|                |
|________________|
|                |
|exc_catch_common|
|________________|

from the above figure you may understand where sizeof(exc_catch_all) - i*sizeof(u64_t) comes from. Closer the entry is to exc_catch_common, smaller is the offset that should be filled into entry. I don't know if I clearly explained this stuff... Hope you understand. 0xe8 represents the "near call with 4 byte offset (5 byte)", this is the reason for existence of "-5". After each entry is initialized, they are put into the descriptor table as interrupt gate. The rest code fills special entry in descriptor table with special values, e.g. replace the entry for handling pagefault with the function pointer exc_pagefault.

After IDT is activated, an initializing routine for KIP is called. The initializing routine sets the system call variables to their proper value, the function pointer of each system call routine. I am not very sure what ARCH_SYSCALL is, I will investigate them later. Then more memory will be grabbed for kernel through add_more_kmem(). It looks for the reserved contiguous memory region in KIP's memory descriptors. If there is one, it is reserved for our kernel. add_more_kmem() will put into free memory list in kernel memory manager. If there is not, add_more_kmem() continues to see if special memory descriptor reserved_mem1 is set and put the memory described by reserved_mem1 into free memory list. Then init_meminfo() will reconstruct the memory descriptor map in KIP. init_meminfo() is located in glue/v4-x86/x32/init.cc. The next step is initializing the mapping database in L4 pistachio. I will discuss it in next post.

L4 pistachio Kernel (5) - IA-32 Registers

2008-02-13T03:14:00.000-08:00

In last post I finished reading init_kernel_space(), and now let's come back to startup_system() and see the next step. The next step is initialize task state segment structure (TSS). What does this structure do, I will not discuss here. The initializing routine tss.setup(...) for x86 architect is responsible for calculating the offset of IO protection bitmap and setting value of stopper (a variable) to 0xFF.


  INLINE void x86_tss_t::setup(u16_t ss0)
  {
      iopbm_offset =
          (u16_t)((u64_t)io_bitmap - (u64_t)this);
      stopper = 0xff;
  }

It seems that ss0 is not used in this initializing routine...why? I guess, maybe L4 doesn't use TSS. But I am not very sure. Then global descriptor table(GDT) is setup through setup_gdt(). I think it is better to explain first the basic structure of INTEL CPU and its registers. IMHO, there are three kinds of registers in the Intel's IA-32 architect. One type is called Memory-Management Register, the second is called Control Register, the third is called General Purpose Register. I will not discuss the third kind here, since it is usually very familiar to most people.

Memory-Management Register contains briefly 4 registers, i.e. global descriptor table register (GDTR), local descriptor table register (LDTR), interrupt descriptor table register (IDTR) and task register (TR). The format of each register consists of two parts, i.e. base address and limit. There is relationship among GDTR, LDTR and TR. Global descriptor table contains the content of TR and LDTR. When task switch happens, CPU automatically reads the LDTR descriptor and descriptor from TSS and GDT fill them into LDTR and TR. That means theoretically each task can have its own Local Descriptor Table and Task State Segment. But most mode operating system doesn't use TSS. Furthermore, I guess Linux doesn't use LDT whereas Windows uses it. The figure 2.1 in Intel 64 and IA-32 Software Developer's Manual tells us when the registers and corresponding tables are useful. The GDT and IDT are always necessary, since Intel architecture requires GDT to provide the base segment descriptor, e.g the data segment descriptor for user mode (unprivileged) or the code segment descriptor for kernel mode (privileged), and IDT is at least used to handle the incoming interrupt. LDT is useful when OS decides to use Trap gate and call gate, which are not very popular. TSS is an alternative to accelerate the task switch speed, however this feature is alway not very popular. Anyway, GDT and IDT are essential, but LDT and TSS are not.

Control Registers is made up with 6 register. They CR0, CR1, CR2, CR3, CR4 and CR8. CR0 is very important, since it controls a lot of important CPU behavior, e.g. on/off Paging, real/protected mode. CR3 is another important control register, it contains the root physical address of page directory table, remember how L4 set active page directory table in last post? CR2 contains the page fault linear address (virtual address).

Ok, After this explanation let's continue to read the codes in startup_system(...). After the TSS is initialized. It tried to initialize the global descriptor table.


  setup_gdt(tss, 0)

This function is defined in glue/v4-x86/x32/init.cc. Looking into it, the first four lines are used to setting privileged code/data segment descriptor and unprivileged code/data segment.


  gdt[gdt_idx(X86_KCS)].set_seg(0, ~0UL, 0, x86_segdesc_t::code);
  gdt[gdt_idx(X86_KCS)].set_seg(0, ~0UL, 0, x86_segdesc_t::data);
  gdt[gdt_idx(X86_KCS)].set_seg(0, ~0UL, 3, x86_segdesc_t::code);
  gdt[gdt_idx(X86_KCS)].set_seg(0, ~0UL, 3, x86_segdesc_t::data);

The third parameter indicates the privilege-level. 0 means the highest (privileged), 3 means the lowest (unprivileged). The gdt variable is defined in glue/v4-x86/x32/init.cc as array of type x86_segdesc_t. It also put the shared UTCB page into GDT as a separate segment. Then is the TSS segment descriptor which we just initialized. Then codes set the GDTR and TR register.


  x86_descreg_t gdtr((word_t) &gdt, sizeof(gdt));
  gdtr.setdescreg(x86_descreg_t::gdtr);
  x86_descreg_t tr((word_t) &tr, sizeof(tr));
  tr.setdescreg(x86_descreg_t::tr);

Then some codes appear to make CPU to use the new settings.


  asm("ljmp %0, $1f \n"
      "1: \n"
      :
      : "i" (X86_KCS)
  );

ljmp will reload the segments setting from just filled GDT. The next inline assembly fills all segment registers with correct value. Then the set_gdt(...) function finishes its work.

L4 pistachio Kernel (4) - More

2008-02-12T13:50:00.000-08:00

I will try to finish talking about init_kernel_space(). The last big work is


   space_t::init_kernel_mappings();

Before we talk about this structure, I'd like to introduce one structure mem_region_t in file generic/memregion.h. It is used in kernel_interface_page_t for indicating the special memory regions, dedicated or reserved, e.g. bootmem region is recorded as the first reserved memory region in KIP. The most interesting thing here is how L4 guys put these information. Do you remember how KIP records information about sigma0 and root_task when kickstart loads the kernel? Yeap, they use the undefined sections in KIP. This time the guys do the same, they use the other undefined regions to record special memory regions. Try to compare the structure definition of kernel_interface_page_t and the L4 manual, count the offset of following code:


   class kernel_interface_page_t {
       ...
       mem_region_t main_men;
       mem_region_t reserved_mem0;

       mem_region_t reserved_mem1;
       mem_region_t dedicated_mem0;

       mem_region_t dedicated_mem1;
       mem_region_t dedicated_mem2;

       mem_region_t dedicated_mem3;
       mem_region_t dedicated_mem4;
       ...
   };

you will find it is between 0x60 and 0x90, where is marked undefined in manual. So almost each undefined sections in KIP is used for some purpose. Ok, let's come back to the function init_kernel_mappings(). Till this point all kernel are still working at 1-1 mapping style, which means virtual address is the same as physic address. After init_kernel_mappings() function, the kernel will be put into correct virtual address area, i.e. phys_addr + KERNEL_OFFSET. An example is to remap the boot memory region, which is stored in reserved_mem0:


   mem_region_t reg = get_kip()->reserved_mem0;
   align_memregion(reg, KERNEL_PAGE_SIZE);
   remap_area(phys_to_virt(reg.low), reg.low, PGSIZE_KERNEL,
          reg.get_size(), true, true, true);

These codes first get the memory information, then align it to page size, at last remap them into correct virtual address area. Then the .init segment will also be remapped into high virtual area, after that is the special low 4M memory region, video memory and a special page for UTCBs. The page is a part of kernel stuff, but it can be accessed through gs:0. L4 guys do this in order to get rid of some unnecessary kernel/user switchs. The rest part of code is very special. I am not going to talk about them currently. After I finish the whole general review, I may come back to talk about them. One question here is why the UTCB page be allocated and remapped twice? I may dig it out sometimes.

At the end of init_kernel_space() is the action to load current root space's page table into gdt register. This is achieved through:


   x86_mmu_t::set_active_pagetable(
                 (word_t)kernel_space->get_top_pdir_phys(0))

The method is implemented in arch/x86/mmu.h by moving the root address into CR3 register.

L4 pistachio Kernel (4)

2008-02-12T03:42:00.001-08:00

In last post I stopped after kmem.init(...), now let's see the next statement:


get_kip()->reserved_mem0.set(...);

Here, I was stopped by finding what get_kip() does. get_kip() was defined in api/v4/kernelinterface.h as,


INLINE kernel_interface_page_t * get_kip()
{
    return &KIP;
}

before this function definition, there is a declaration for KIP.


extern "C" {
    extern kernel_interface_page_t KIP;
}

First this is not the real declaration of KIP because of the "extern" keyword. The real declaration and initialization locate in api/v4/kernelinterface.cc as,


kernel_interface_page_t KIP UNIT(KIP_SECTION) =
{
    ...
};

One more thing you should know is that KIP is on earth the same as variable kip. It is defined at the beginning of file kernelinterface.h


#define KIP kip

The function reserved_mem0.set(...) is used to set the kernel occupied region as reserved. After this, the init_bootmem() finishes its work.

Following the init_bootmem() is the initialization code for space_t structure. According to lecture given by Joschua, every L4 thread has its space_t structure, but all L4 threads share the same kernel region. The shared region is based on a root space(kernel space). Mostly that means all kernel stuff in other space_t will be synchronized upon the root space (I guess). The init_kernel_space() is a static function defined in glue/v4-x86/space.cc and responsible for initializing this root space_t. Looking into init_kernel_space(), it first check if the kernel space is already initialized,


ASSERT(!kernel_space);

Then it tried to allocate memory for kernel space_t, this is achieved through alloc(...) function in kmem_t class.


kernel_space=
   (space_t*)kmem.alloc(kmem_space,sizeof(space_t));

Be careful, there are two alloc(...) functions. One is declared as public, the other is declared as protected. The latter is called by former. The reason for this is that the public alloc(...) function contains codes for debugging. Then it checks if the allocation is successful,


ASSERT(kernel_space);

then init_kernel_space() also allocate memory to page directory for kernel space and record the address of kernel address in itself. If you look into space_t class, you will find how L4 divide its address space. The whole address space, represented by class top_pdir_t, is divided into five sections:


class top_pdir_t{
public:
union{
    pgent_t pgent[1024];  //allocate enough space
    struct {
    x86_pgent_t
      user[USER_AREA_END>>X86_X32_PDIR_BITS];
    x86_pgent_t
      small[SMALLSPACE_AREA_SIZE >> X86_X32_PDIR_BITS];
    x86_pgent_t
      copy_area[COPY_AREA_COUNT]
    [COPY_AREA_SIZE >> X86_X32_PDIR_BITS];
    x86_pgent_t
      readmem_area[MEMREAD_AREA_SIZE >> X86_X32_PDIR_BITS];
    space_t * space;
}; // five sections
};
};

The first section is user space, then a section for small space, which is used to optimize the performance. You can put such as device driver in this space to reduce the space switch. The third section called copy area, the string copy between two address space can be achieved more efficient by mapping the target space into this area and avoid one space switch. The forth section is the readonly section of kernel. After that is a section for mixed variables. You can find more information from the slides of MKC lectured in Uni. Karlsruhe.

After the memory is successfully allocated for kernel space, init_kernel_mappings() is used to initialize the mappings in kernel space. I will talk it in next post.

Short Note (2) - Good Resource

2008-02-11T06:44:00.000-08:00

If you want to understand L4 pistachio micro kernel, I recommend you watch Joshua LeVasseur's teaching records. You can get them from here. Note they are password protected, but I think you can ask the guy in Uni. Karlsruhe for the username and password.

L4 pistachio Kernel (3)

2008-02-11T02:48:00.000-08:00

First of all, I have to mention again that a lot of variables are not directly declared in source files but in linker script. You will see that during my explanation. Yesterday I stopped at function startup_system(). What this function does is initializing the kernel structure and activating some functions. Let's start looking into it.


 if(is_ap)
    startup_processor();

This is used in multiprocessor scenario in order to initial and startup adjunct processor. It is not in the range of our current discussion.


 clear_bss();

Then BSS section is cleared. I am not very sure if this is necessary since I remember it is cleared when kernel is relocated.


 call_global_ctors();
 call_node_ctors();

are two statements used for invoking constructors. Why? Don't forget that L4 didn't use the standard C/C++ library, so the initialization routine included in this library is not linked into the pistachio kernel. However, L4 pistachio uses C/C++ as its default programming language, people must find a way to follow the C/C++ ABI convention. These two statements are used for this purpose. If we look deeper inside these two functions, you will find there are an array of functions to be called, e.g. in call_global_ctors(), defined in ctors.cc, it works like:


 for (unsigned int i = 0; __ctors_GLOBAL__[i] != 0; i++)
    __ctors_GLOBAL__[i]();

where __ctors_GLOBAL__[] are declared in ctors.ldi. After the C/C++ convention requirement is filled, init_hello() is used to display a message on the output console. Usually you will see it on the com port monitor, e.g. minicom. This function is special, it only works when you activate the debug option when you configure the kernel build. Otherwise, it is replaced by a empty statement.


 check_cpu_features();

is the next step. It was defined in glue/v4-x86/x32/init.cc. It checks if CPU has all features L4 required. If not, it will print all missed feature and stop execution. Of course, CPUID is used to finish this checking. For how to check if CPU supports CPUID instruction, you'd like to check function x86_x32_has_cpuid(). Inside this function, it uses EFLAG to check the existence of CPUID instruction. What kind of features are necessary for L4? It is relied on your configuration.


 init_bootmem();

prepares the scratch space "boot mem" that I mentioned when I explained the linker script. At first, it clear up the region. start_bootmem and end_bootmem are two variables defined in linker script. Now we are going to see something about kernel memory management. The kernel memory management is achieved by kmem of class kmem_t, which you can find in file generic/kmemory.h and generic/kmemory.cc. In current stage, we need to initialize this manager by invoking kmem.init(...). The init(...) function does only two things, initialize the variable for kernel memory management:


 kmem_free_list = NULL;
 free_chunks = 0;

and register the boot memory area as free memory in kmem_free_list.


 free(start, (word_t)end - (word_t)start);

The free(...) function is used to update the information about free memory resource. It first tests the region that is declared as free, e.g. size checking. Then it splits the free region into predefined chuck size and organizes them as a list, if necessary. Following codes do this:


 for( p = (word_t*)address;
 p < ((word_t*)(((word_t)address)+size - KMEM_CHUNKSIZE));
 p = (word_t *) *p)  *p = (word_t)
     p + KMEM_CHUNKSIZE;

At last, the organized list is inserted into free memory list as following:

 // Iterating the list and find a place
 for (pre=(word_t*)(void *)&kmem_free_list,
     curr = kmem_free_list;
 curr && (address > curr);
 prev = curr, curr = (word_t*) *curr);
 // insert here
 *prev = (word_t)address; *p = (word_t) curr;

There are two things you need to know. First, before modifying the list structure, L4 uses spinlock to prevent the race condition. Second, KMEM_CHECK is meaningless currently, it is declared as empty.

After the boot memory is register for free, it is also declared as reserved memory region, so that user cannot use it. Ok, I think it is enough for today :).

Short Note (1) - BSP v.s. AP

2008-02-10T13:13:00.001-08:00

During reading the source code of pistachio, I was stopped by BSP and AP. After searching I get the result:

BSP - Bootstrap Processor
AP - Adjunct Processor

They are used in multi-processor scenario.

L4 pistachio Kernel (2)

2008-02-10T04:21:00.000-08:00

Today, I am going to start reading codes of L4 pistachio. I don't want to complicate the explanation, my discussion only focuses on IA-32 uniprocessor system. Let's start with startup.S, located in platform, which takes over the control from kickstart. One thing I have to mention is that I was trying to explain the codes one directory after another, however this doesn't work. So I decided to follow the control flow and explain whatever I encounter.

The code in startup.S is very similar to the codes in startup.S of kickstart. It first initializes the segments:


.section .init.startup32
.code32
start:
_start:
 cli
 cld
 mov %ds, %ax
 mov %ax, %es
 mov %ax, %fs
 mov %ax, %gs
 mov %ax, %ss

Here, .init.startup32 shows that following codes belongs to .init section, see linker-pc99.lds. Then .code32 indicates that these codes are executed in protected mode of x86 machine. Defining both labels start and _start is for the compatibility of different compiler. Then:


 lea _mini_stack-4, %esp

will set the stack for further execution. B.T.W. lea means load effective address. After this step, kernel is going to initialize the paging system and the call init_paging function. The init_paging is defined in glue/v4-x86/x32/init.cc. Take a look in the function, two variables are initialized, i.e. init_pdir[] and init_ptable[][]. init_pdir[] represents the initial page directory and init_ptable[][] contains the page tables that will be installed into page directory. The first dimension of init_ptable[][] indexes the address of each page table, the second dimension contains the actual page table entries. The following codes are the most important in this function,

for (int i = 0; i < MAX_KERNEL_MAPPINGS; i++)
{
for (int j = 0; j < 1024; j++)
 // first assignment
 init_ptable[i][j] = ((i << IA32_PDIR_BITS) |
        (j << X86_PAGE_BITS)  |
        PAGE_ATTRIB_INIT);
 // second assignment
 init_pdir[i] =
  init_pdir[(KERNEL_OFFSET >> IA32_PDIR_BITS) + 1] =
  (word_t)(init_ptable[i]) | PAGE_ATTRIB_INIT;
}

The first assignment initializes page tables with the physic address from 0. The second assignment puts each page table into two places of the virtual memory space. One place is the 1-1 mapping place and the second place is kernel area in the virtual memory space, see the figure below.

After the initial virtual memory space is filled, the page directory table should be installed into MMU. The MMU functions can be found in directory arch/x86/mmu.h. I will discuss two of them in this post. The first is set_active_pagetable(...), which is actually implemented with one assembly instruction,

 mov root_addr, %cr3

since we are in privileged mode, CR3 register can be modified. The second is enable_paging(). It uses x86_cr0_set(...) to change the flags about paging in CR0 register. x86_cr0_set can be found in file arch/x86/cpu.h. Its work is reading CR0, ORing its value with the given value and writing back to CR0. After the paging is enabled. The control flow runs back to startup.S. The mini stack is cleared and startup_system is called, which I will explained next time.

The Saturday :)

2008-02-09T11:25:00.000-08:00

It's Saturday. It is the day I chat with my parents in Shanghai. So I just want to rest my soul today. Totally relax! (Although I read part of paper for variable radix page table, Hey~).

L4 pistachio Kernel (1)

2008-02-08T01:24:00.000-08:00

Following the plan, I'd like to explain the linker script used to build L4 pistachio kernel. I discuss this because I was confused when I first touch the source code of L4. At least, I don't know where to start reading the codes. The Makefile can help a little, but it doesn't reveal the structure of kernel, but only indicates the requirements for building the kernel. For example, you need to specify the option so that linker doesn't use the standard C library for your binary (It is meaningless to use it, since there is no such library when the kernel boots). However, Makefile gives me a tip where to find the structure of binary, the linker script. During reading the Makefile, I recognize the option that commands the GNU linker to finally generate binary, where also indicates which linker script is used.

Recall! I only focus on the source codes for IA-32 platform. For other platforms, you can use the same way as I used for IA-32 to analyze them.

First of all, the major linker script for IA-32 platform is stored in directory:

(l4-top-dir)/kernel/src/glue/v4-x86/x32/

and named linker-pc99.lds. Through the whole file, you can find out more sub linker scripts which are included in linker-pc99.lds. They are kip.ldi, linkersets.ldi, mdb.ldi, ctor.ldi and debug.ldi. They are responded to different sections in final binary.

Before I go further, I'd like to mention one thing that in linker script people can also define variable used in source code. Verse vise, you can also use the variables defined in C source code in linker script. The variable "memory_descriptors" is a good example. You may be confused because there is no declaration for this variable, but it is used in the linker script. To find the declaration of this variable is not a easy way for me to go. But at last, I found it in file kernelinterfaces.cc. The declaration is not finished directly, it looks like:


#if !define(KIP_MEMDESCS)
#define KIP_MEMDESCS memory_descriptors
#endif

extern "C" {
memdesc_t KIP_MEMDESCS[KIP_MIN_MEMDESCS]\
  UNIT (KIP_SECTION ".mdesc);
}

As you saw above, the memory_descriptors is declared through Marco "KIP_MEMDESCS". A lot of Macros are used in pistachio's source code. It may be easy for coding but it's really difficult for reading.

Now let's walk through the linker_pc99.lds. In the beginning,


ENTRY(_start)

BOOTMEM_SIZE = 128K;

_start_text_phys = 0x00100000 + 0x200;
_start_text = _start_text_phys + KERNEL_OFFSET;

it declares entry point for the binary, which is labeled as "_start". Then the size of a scratch region for booting are defined. Then _start_text_phys indicates the physic memory location for the kernel to load, and _start_text is the virtual address location for the kernel, where KERNEL_OFFSET is defined in offsets.h as 0xF0000000. From this declaration we know that kernel is loaded into the 0x00100000 in the physic memory and 0xF0100000 in every L4 thread's address space.

The SECTIONS indicates the organization of binary. Briefly it is made up of .text section, .utramp section, .rodata section, .kip section, .cpulocal section, .data section, .kdebug section, .sets section and .init section. However, .init section is different from the others, if you see the attributes of each sections. The most section are specified as:


.#section# . : AT (ADDR(.#section# - KERNEL_OFFSET))

but .init section is defined as:


.init (. - KERNEL_OFFSET) : AT (ADDR(.init))

The attribute before ":" specifies the virtual address, the attribute after ":" specifies the physic address (I guess). For more information you can see this section in GNU linker manual. So the statement for .init section indicates that its virtual address is the same as its physic address! It is a 1-1 mapping. For this setting is because there is still no paging system during the init stage.

One more thing is that that all section is page aligned(4K in IA-32). It is achieved by code:

 ALIGN(4K);

why is this necessary? Do you still remember how kickstart find KIP page? Yea...This is one of reasons that make every section page aligned!

L4 pistachio Kernel - Road Map

2008-02-07T11:21:00.000-08:00

I am very tired today, since I traveled for almost whole day. So today I'd like only to list out a road map for next step - reading source code of L4 pistachio kernel.

The source tree for L4 pistachio kernel consists of for major sub directory. They are "api", "generic", "glue" and "platform". "api" contains the codes for constructing system calls. "generic" contains mostly the memory management stuff. "glue" contains the code that abstracts the hardware platform, e.g. codes implementing interrupt & exception mechanism in kernel. User application cannot directly modify the interrupt description table, L4 provides interface for user to set their interrupt or exception handler. At last, "platform" directory contains the code to initialize the platform dependent hardware, for example, the interrupt controller, CPU. It also contains the the codes to startup the kernel - Startup.S.

In the next days, I will first try to analyze the linker script and figure out the structure of kernel binary. Then I will start with "platform" directory, followed by "glue" and "generic", and finally "api". I am not sure yet, which of "glue" and "generic" I should review firstly. Most probably I will analyze the code in these directories mixed.

Before I finish this post, I recommend you (if there is one :) to read the paper about radix page table, since pistachio seems using such kind of page table instead of traditional page table.

Kickstart - kick the kenrel to start (5) - ELF

2008-02-06T02:13:00.000-08:00

In last post I finished walking through the main routines of kickstart. However, I put the ELF stuff aside in order not to destroy the continuity of explanation. Today I would like to pick back ELF stuff and make them clear. At first, I'd like to make a brief introduce of ELF.

ELF means "executable and linkable format". It defines a way how people constructs a executable or linkable file. A file in ELF format usually contains three headers, i.e. ELF header, section header and program header.

The ELF header indicates some brief information about the whole file. For example, it contains the identity of ELF. The identity is 16-byte long. The first four bytes must contain 0x7F, 'E', 'L', and 'F'. The fifth byte indicates in what kind of platform the ELF file fits, e.g. 1 means 32-bit platform and 2 means 64-bit platform. ELF header also contains the offset to section header and program header in file. For more details about ELF you can check here.

The section header contains very detailed organization information about the ELF file, since the ELF file is made up with various sections. It is useful for linker but not so important when the file need to be loaded into memory for execution. For your interesting you can learn it from this site.

The program header is relevant for all ELF loader, because it tells loader how to split the content of current ELF file and where to put them in the memory. What may confuse you here is the vaddr and paddr field in program header. In my opinion, the vaddr (virtual address) field is only used when the virtual address mechanism is turned on in system, e.g. after OS initializes its virtual memory management component. And paddr (physical address) is only used when the system requires to know the exact physical location in memory, e.g. there is no VM system or VM system should be skipped over. For more information look here.

Now let's go back to kickstart and see how it implements the ELF loader. The prototype of ELF loader is declared as:

bool elf_load (L4_Word_t file_start,
L4_Word_t file_end,
L4_Word_t *memory_start,
L4_Word_t *memory_end,
L4_Word_t *entry,
L4_Word_t *type,
L4_MemCheck_Func_t check)

You can find out from this declaration that memory_start, memory_end, entry and type are the result of elf_load(...), since pointers are passed into elf_load(...) and the content of these variables is allowed to be changed. The memory_start and memory_end is the final location of binary in the memory, entry is the entry point of this binary and type will indicate 32-bit or 64-bit format.

elf_load(...) checks the identity of current file first and determines the platform type. Then it calls a subroutine according to type of platform, i.e. 32-bit platform with elf_load32(...) and 64-bit platform with elf_load64(...), to actually relocate the binary. The subroutine checks if the current elf binary executable, i.e. type field of ELF header, is 2. Then it finds out the entry point in entry field of ELF header. It also checks if the program header valid, since without program header the loader doesn't know where to put the different sections in file. At last it loads all loadable parts, according to the type field in program header, of ELF file into the right place in memory. Since in this stage, we don't have any virtual memory system, all operations are handled with physical addresses in program header. In the end of elf_loadxx(...) the start_addr and end_addr of memory region for binary is calculated and stored.

I also understand now what root_task_type means, it is platform information from ELF header, i.e. 32-bit or 64-bit. To read the code of elf loader is really helpful for me :).

Kickstart - kick the kenrel to start (4)

2008-02-05T03:32:00.000-08:00

Today I will continue reviewing the initial routine in kickstart. In last post I introduced the class L4_KernelConfigurationPage_t which is used by kickstart to install information in KIP region. Now we look back to the mbi_init() function. The function starts with finding KIP region with find_kip(...), see last post. Then it turns to analyze the multi-boot information (mbi) from boot loader. At first, it checks the command line passed contained in mbi. Inner mbi_init(), three Macros are defined to copy and analyze the command line,

- COPY_STRING is used to copy command line string into a preserved cache.

- PARSENUM is used to covert string numbers to real number according to the metric, i.e Kilobytes, Megabytes, Gigabytes, and put and print them in a predefined message.

- PARSEBOOL is a macro to switch on and off some options according to the command line.

After finishing parsing the command line comes the most important task of mbi_init(), i.e. looking for the modules following kickstart and relocating them. As I mentioned before, the first module following kickstart is L4 micro kernel pistachio, and then there comes sigma0, after sigma0 is root_task. root_task is not included by kernel source tree, it should be provided by L4 user. In the beginning mbi_init() checks if the flag bit of modules is set in the mbi flags. If so, it will check if the number of current modules are exceed the limit defined by MAX_MBI_MODULES. If exceeds, the additional modules will be dropped, i.e.

mbi->modcount = MAX_MBI_MODULES;

According to the number of modules, mbi_init() relocates the modules information in new place through copying, i.e.

// mbi is a global var!
orig_mbi_modules[i] = mbi_modules[i] = mbi->mods[i];
//switch the pointer to new location
mbi->mods = mbi_modules;

To do like this allows kernel to free the memory occupied by boot loader (I guess). Then the command line passed by root_task also replace the original command line stored in mbi, since the original one isn't used by further execution any more. At last, mbi_init() uses function load_modules() to relocate the modules.

Now let's see the load_modules() function. In this function it also checks the modules flag for sure. One thing special is it clears entry point in each modules, since, I think, after relocation the entry point will be certainly changed. Another reason, I guess, is that boot loader, e.g. Grub, didn't extract the modules' binary format, it only load them in their original form into memory, so the entry point for each module is useless. The actual work to analyze and relocate modules are handed to elf_load() function, in elf.h and elf.cc, through Macro LOADIT. Let's put the elf stuff aside first and continue reading the codes. After the three essential modules are loaded, the other modules followed are also loaded as demand. I also believe, when the load_modules() finishes, each entry of mbi->mods[i] will be filled correctly. Furthermore the start and end of each module is also modified to fit in new location.

Now the L4 kernel is relocated, so we need to find KIP region in the new location through find_kip() again. The kernel now is in its final position, the modified information should be write back into the KIP region. install_memory(), in mbi-ia32.cc, will fill the region of memory information through the memory map either stored in mbi or predefined by L4 guys. After the memory map is installed, information about sigma0 and root_task is also installed through fuctions, install_sigma0 and install_root_task introduced in last post. At last, the user level modules, which are loaded besides kernel, sigma0 and root_task, are protected by marking memory occupied by them as L4_BootLoaderSpecificMemoryType, definded in include/l4/kip.h. In the final stage of mbi_init(), a bootinfo section is created if necessary. The section records the original information from boot loader, e.g. where the modules are original placed in the memory. These information could be used by kernel later.

Finally we reach the end of mbi_init(). Here the kip_update() is called, see more about it in last post, and then the entry point of kernel is returned. A question is still not answered when I read the code. What is the root_task_type?

Kickstart - kick the kenrel to start (3)

2008-02-04T07:54:00.000-08:00

In this post I will start explaining what initial routine in kickstart does. It is heavier work than last two posts.

The initial routine in kickstart (for multi-boot loader) is called mbi_init and defined in mbi-loader.cc. Before we start digging into this routine, I'd like to introduce a class for managing "kernel interface page"(KIP) of L4 pistachio micro kernel. The class is named kip_manager_t, which is declared in kipmgr.h and implemented in kipmgr.cc. For figuring out what this class really represents, I'd like to describe some important member functions in this class one by one.

"bool find_kip(L4_Word_t kernel_start, L4_Word_t kernel_end)"

This function is used to find out the KIP region located in micro kernel. In order to achieve this, you need to pass the start address and end address of current location of microkernel, which should be determined by boot loader. This method will iterate all pages from kernel_start to kernel_end according to the size of L4 configuration page, currently 4K bytes, in order to locate the KIP page. The KIP can be recognized through its magic label "L4_MIGIC" (user/include/l4/kcp.h). After kickstart finds KIP, it begans preparing the further modification. At first it determines the length of "word" defined by current kernel. This is a metric for kernel to measure the SIZE. Probably it only differs between different architect, e.g. IA-32 and IA-64. The word size on IA-32 may only be 32 bits (I guess). Next step is to retrieve the offset to the region of "memory information" in KIP, since the memory information passed from boot loader need to be filled into this region so that applications upon L4 can use it. If you look into a little for this step you may confused by GET_KIP(MemoryInfo). Where does MemoryInfo come from? After searching the source tree, you should only find a definition of MemoryInfo in class L4_KernelConfigurationPage_t, which normally cannot be directly used as a separated variable. However, GET_KIP(...) is not a function but a Macro, which is define as,

#define GET_KIP(field) get_value(KCP_OFFSET(field))

Here, get_value(...) is a protected method in kip_manager_t, and KCP_OFFSET(...) is another Macro. If you dig deeper in KCP_OFFSET(...), you will find how MemoryInfo is used.

#define KCP_OFFSET(field) \
(((L4_Word_t) (&((L4_KernelConfigurationPage_t *) 0)->field))/\
sizeof(L4_Word_t)

The statement (((L4_Word_t) (&((L4_KernelConfigurationPage_t *) 0)->field)) will give the offset of field in class L4_KernelConfigurationPage_t in bytes. And then the division will turn the offset into "word" aligned, since all fields in L4_KernelConfigurationPage_t are word aligned. So actually the GET_KIP(MemoryInfo) will be expanded into

get_value( (((L4_Word_t) (&((L4_KernelConfigurationPage_t *) 0)->MemoryInfo)) \
/sizeof(L4_word_t) )

Be careful, here we didn't get the final offset of memory information. The effective offset is stored in the high end of the word, i.e 31-16 bit in IA-32. So a shift operation according to the word size is necessary. And then we can finally calculate the address of region of memory information through

base address of kernel + effective offset

For more information, please read L4 x2 revision 4 manual.

"void update_bootinfo(L4_Word_t boot_info)"

This function will write bootinfo section in KIP with the value passed from boot loader. Another task of this function is to write the count of memory information description in the low-end of MemoryInfo section, i.e 15-0 bit in IA-32.

"void install_sigma0(...) & void install_root_task(...)"

As I first looked at these two methods, I was confused, since there are no official regions to put the information of sigma0 and root task (not in the L4 manual). Later I notice this is a tricky implementation from L4 guys. There are two header files, i.e. kcp.h and kip.h. kcp.h is used by kickstart to modify the KIP, kip.h is used by user application to access the KIP. After reading the kcp.h, I notice that the scratch place of KIP in manual, say offset 0x10 - 0x40 in IA-32, are used to store the sigma0 and root task information. Why they are need to be stored?? investigate later...

Kickstart - kick the kernel to start (2)

2008-02-03T08:57:00.000-08:00

After the kickstart takes over the control, e.g. setup a mini_stack, retrieve the multi-boot information pointer, a function named "loader" is called, which is defined in file kickstart.cc. It should never return, because in the end of this function a "launch_kernel" function hands the control to the mircokernel. Before this transaction happens, a few things must be done.

First kickstart checks the current loader format. Although in the crt0-ia32.S codes are dedicated to cooperate with multi-boot specification compatible boot loader, the codes in kickstart.cc are still written to be able to be extended for other loader formats. An array named loader_formats[], defined in file ia32.cc, are used to test the format of current boot loader. Currently it contains only the entry for multi-boot (MB) boot loader. Each entry is a loader_format_t variable, which has three members - a string to describe the format, a probe function to see if current boot loader matches this format and an initial routine to initialize the information from boot loader. loader_format_t is defined in file kickstart.h. For the MB format, mbi_probe and mbi_init are used to probe and init the information from boot loader. I will look into three files, mbi.cc, mbi-ia32.cc and mbi-loader.cc for more information. Obviously, their names told us they will handle the multi-boot information (mbi).

Let's see first what mbi_probe in mbi_loader.cc does. At first it call a static function prepare of class mbi_t. This function achieve a simple task, checking if the boot_loader is multi-boot compatible and if it is, returning the multi-boot information structure. Recall my last post, there is a variable called grub_mbi_flags. This variable should contain the magic number of multi-boot format, which is 0x2BADB002, if the boot loader is in this format. After the boot loader passes the checking of magic number, the pointer of multi-boot information will be returned and stored in a global variable called mbi_copy. Then the probe routine finishes.

Before we go on, it may be better to see what is in the multi-boot information. I don't want to explain too much here, because there is a good manual to explain everything. You can find this manual here.

After the probe routine, the initial routine comes. It fills the boot information into KIP section in the microkernel binary, then relocates the different modules into their proper location. I will explain it in the next post.

Kickstart - kick the kernel to start (1)

2008-02-02T07:52:00.000-08:00

Kickstart is a tool loaded by "grub" before L4 kernel is going to be loaded. You may think it is a bridge between the world of "grub" and the world of L4. Conceptually kickstart will relocate the modules following it into their correct place, initial the kernel and start the kernel. If you are a student of University Karlsruhe, you can find more information from the website of course "SDI". Slide named "L4 crash course 1" explains the duty of kickstart briefly. Here I would like to investigate how kickstart is implemented to fill its responsibility. I will only discuss the source for 32bit x86 (IA-32) machine. By the way, source code of kickstart is located in folder "(l4-top-folder-name)/user/util/kickstart".

The kickstart for IA-32 consists of following source files:

crt0-ia32.S
bootinfo.cc
elf.cc
ia32.cc
kickstart.cc
kipmgr.cc
lib.cc
mbi.cc
mbi-ia32.cc
mbi-loader.cc

There are some files in order to get the information from boot loader, e.g. crt0-ia32.S. Some are used to relocate the kernel, e.g. elf.cc, the elf loader. And other are used to initial kernel, e.g. bootinfo.cc, which is used to fill the boot information into "kip" area of kernel. Otherwise, a library for IO will be linked with final binary. I will describe one by one later. In this article, let's see what crt0-ia32.S does.

crt0-ia32.S contains the codes used to get control from multi-boot bootloader. "Grub" puts multi-boot information descriptor in register file EBX. Furthermore, a flag for Multi-boot is contained in register EAX. The following codes fetch these two descriptor and store them in static variable grub_mbi_ptr and grub_mbi_flags.

movl %ebx, grub_mbi_ptr
movl %eax, grub_mbi_flags

One note is that, in assembly all undefined symbols, e.g. grub_mbi_* here, will be put into symbol table as external symbols. After these codes, kickstart initial the necessary segments with the value of current data segment for the further execution. The string index register(ESI) and data seg index register(EDI) is initialed with the address of grub_mbi_flags and grub_mbi_ptr. Then the function "loader", which is implemented in kickstart.cc, is called. In the end of crt0-ia32.S, there is a _mini_stack region, which is also labeled as multi-boot header(.mbh) section. The .mbh region will be put in the start of kickstart binary. After grub loads kickstart, it will check the __mb_header structure at the begin of kickstart to see if kickstart is a multi-boot kernel. However, after this check these information isn't useful anymore, so this region can be used as mini stack for the further execution. Because it is the first part of .text segment (see. kickstart.ld),

.text : {
_kickstart_begin = .;
*(.mbh)
*(.text)
*(.*data*)
_edata = .;
}

a jmp instruction, i.e. "jmp _start", must exist in order to jump to the real start of kickstart.

The start of all

2008-02-01T07:36:00.000-08:00

Although boot loader is not part of L4 project, I still think it is better to know how it works before my deep watching into the microkernel. That might be not necessary at all, since the purpose of separating boot loader from OS development is similar to that of my idea, i.e. simplifying the development and save the effort of developer for constructing boot loading to more important things in other part of OS. However, because of my nature I am interested in everything that is necessary to bring up the machine. So the boot loader cannot escape from my sight. Although there are lots of boot loader projects, "grub" is the most popular general purpose boot loader.

The whole "grub" project briefly consists of two parts, the installer and the boot loader. The former is used to install the latter into boot sector and locate the next further disk sectors for booting. The boot loader can be divided into three part, stage1, stage1.5 and stage 2. Stage1 is the start of all and resides in the boot sector and thus must be 512 bytes. Stage1.5 is file system specific part. It is optional and not always installed onto disk for booting. Stage2 is final loading stage of "grub" which finds and loads the real OS kernel into memory, changes real mode to protect mode(x86), pass the necessary information to OS kernel and hand off the control. My investigation focused on stage1, which is the smallest part of "grub", since this part is more common for all boot loader and the other two parts are more "grub" specific.

The current PC boots itself by using BIOS. There is a small piece of codes reside in the BIOS ROM and will be executed when the machine is powered on. And then BIOS will look for bootable device in its hardware list. For simplicity, I only talk about the disk device here. Assuming there is only a bootable hard drive. BIOS checks the first sector (header 0, cylinder 0, sector 1) of the disk and look if it is a legal boot sector, which should end with signature "0xaa55". By the way, just before this signature there is a 4-entry partition table for hard disk. The code in this boot sector will be loaded into memory started from 0x7c00 and executed in real mode, i.e. no more then 1M bytes segmentation. Since every instruction cannot be dynamically relocated in this stage, the address of "jmp" instruction should be absolutely calculated. That is why grub defines "ABS(x)" macro to help calculate the jmp's destination.

Stage1's mission is to load the next boot sectors into memory. Obviously in the world stage1 living there are no helper except BIOS (OS are still sleeping on the hard disk). Int 0x13 and Int 0x10 are the most useful BIOS Interrupt Services for boot loader. Int 0x13 is responsible to read the sectors from disk. You can learn more from Interrupt Jump Table.

One more thing must be mentioned here is that the generated stage1 binary is not the final binary installed into boot sector. The grub installer manipulates the binary, e.g. filling variables with actual values, eliminating the unnecessary codes before it is coped. One Example is the codes after label boot_drive_check.

boot_driver_check:

jmp 1f
testb $0x80, %dl
jnz 1f
movb $0x80, %dl

"jmp 1f" must be removed when stage1 is copied into the boot sector of a hard disk, so that the next three instructions can work around some BIOS bogus value. The installer will manually replace this jmp instruction with nop (0x90) instruction.

Another Example is that installer copies the master partition table of original boot sector into stage1 since it varies on different machines.

My way to understand the L4

2008-01-31T13:18:00.000-08:00

I studied L4 not a long time ago, since I needed to know its internal to pass my final examination. During the preparation I found L4 is interesting, though everything I learned is only the concept. There are few implementation and source code explanations for student to understand how a L4 is really implemented. Especially it lacks of the introduction for the tools along with L4 project, which are mostly also implemented by L4 guys. So, in the next days, I would like to read more source codes and record my understanding about the organization of implementation of L4. If you find my pages occasionally, I beg your understanding for my poor English and some "beginner's" explanations. I will start with listing some essential knowledges, people need to know before starting read the source code.

- How the binaries or executable files are created..

In the beginning I just thought there is a simple and nature answer, "using the compiler". But now I knew the thing is not as simple as I thought. As a system developer you really need to know not only the "gcc -o exename file" stuff, but also how to use the linker option to manipulate the final product. If you develop the things under Linux, reading the manual of LD is very useful for you to understand how the source codes are used for final binary. You can specify the final opcode schema by defining the linker script, usually suffixed with "lds", "ld" or "ldi" ( in L4 Project).

Furthermore, some binary tools are also useful for developer to manipulate their binaries. For example, if you don't use a boot loader, you must create your own boot loader binary and put it into the boot sector to load your rest kernel. The codes settling in the boot sector must be a raw binary, i.e. no any kind of executable format's meta info. I didn't find a way that can directly create raw binary from a source code. So the way is converting a executable binary into raw binary by using "objcopy". An example is:

$ objcopy -O binary elf.exec raw.exec

- L4 is using Grub as its default boot loader, although it is not the official boot loader for L4 (you can also use other multi-bootable boot loader, which can load elf format binary).

So you'd better to read the manual on gnu Grub site. It is very helpful for understanding the kickstart stuff, which will get over the job from Grub and load the rest of L4. What is multi-boot header? How a multi-bootable kernel should be organized, e.g. where the mult-boot header should be put in the binary. And how the boot information could be passed to the kernel? These are important in implementing a multi-bootable kernel following the multi-boot specification. I will answer these questions & explain more during the source code review of "kickstart" in L4.

- How to compile the L4?

There are two folders in L4 project contains the essential sources to build kernel and booting tools, i.e. "kernel" and "user". "kernel" contain the codes for L4 pistachio kernel. You cannot compile the kernel under its original folder. How to compile it? Try to compile the kernel under its original folder, the error message will tell your all. In the "user" folder contains the source codes for "kickstart" and "sigma0". "kickstart" is used to help load the L4 kernel, "sigma0" is used after kernel initialization and help user to create the root task. To build them, read the "INSTALL" under the "user" folder.

- How to find out the core of L4?

Although the number of source code lines in L4 is very small, it is necessary to divide the essential source files and the additional source files for special features. To find out the core part of L4 distribution, you can compiling the source and go to the build directory and then look which object files are created. According to these obj files, you can know which source files are really used to create final kernel binary.

The brief architecture of the idea

2008-01-29T09:28:00.000-08:00

The architecture is similar to some kind of para-virtualization system. It is divided at least three layer vertically. The bottom layer is probably a microkernel. The middle layer is virtualization layer, or I call it "bridge layer", which will uniform the hardware view to the upper layer and also bridge the communication between OS and driver pool. The up layer is the service layer. This layer can be divided into briefly two parts horizontally. One part is "Driver Pools". The middle layer will provide driver writer tools to implement driver to support different hardwares, there would be a way for driver writer to quickly install their driver into driver pool. The other part is OS region. OS developer can develop the system upon a set of "simple virtual hardware devices". OS developer should not concentrate on how the hardware can correctly work, because it should be resolved by driver pool. In contrast, OS developer should do more work how to use more efficiently use the CPU & memory resource, how to let user be more satisfied with OS.

Why will it be similar to para-virtualization. Since para-virtualization promises the performance and all OS will run in this environment will be dedicated for this environment (maybe not? If we provide full emulation of classic hardware, the OS can also run on bare machine within classic hardware installed. However this pulls down the performance.)

Microkernel, Virtuliazation & OS

2007-12-25T08:24:00.000-08:00

I have an idea at the end of this year to separate the traditional OS model into a more flexible and maybe equal efficient OS model, which will keep in touch with Microkernel, Virtualization techniques. I learned L4 Microkernel during my study in University Karlsruhe. Although the people there announce that this kernel can be faster than ever, it is still not used for most possible commercial OS. Despite the pay off problem for migrate current designate to new microkernel based designate, how to construct a efficient OS upon the microkernel and how complex this work is is also a big problem to stop people use microkernel. The OS complexity comes a lot from the diversity of hardware platform, however virtualization can hide this diversity and simplify the OS design and implementation problem. Otherwise virtualization can let the driver developer avoid the complexity of underlying OS in traditional OS architecture.

Virtualization is recently used to virtually replicate a physical machine and support convenient commercial OS to achieve the most important purpose, i.e. Server consolidation. People usually still hang on the OS to provide I/O support, memory management support and so on.. So driver guys still need to develop drivers for new hardware in a developing OS environment, where they need to understand the complicated OS environment and to cooperate with OS architecture. On the other hand OS developer also need to think about interfaces provided to the driver developers, which increases the complexity of OS architecture. In this article, I think we can using virtualization more than an emulator but a revolutionist in the OS world. The microkernel idea is very similar to the virtualization, but the multi-servers architecture are much loose coupled, whereas in traditional OS system device services are too tight coupled. Virtualization technique stays in the middle of these two models, it may take the advantages of both and decrease the engineering efforts for both OS developer and hardware driver developer.

inline function in C++

2007-09-13T09:58:00.001-07:00

If you want to use inline function with a class, then the function body must be together with class definition. Either you write it inner the class definition together with the function declaration or you put the implementation outside the class, the body should always appear where the class definition appears. Otherwise, you will get a LINK error that tells you that linker cannot find the reference of the function declared with inline. This is quite similar as MACRO, since MACRO are mostly defined in header file. So just remember, using inline function "like" MACRO, i.e. writing it in header file, although they don't work in the same way.

javax.xml.transform.TransformerException: java.io.FileNotFoundException:

2007-03-02T01:59:00.000-08:00

I encountered this problem when I try to fix a web application.

Situation:

Using Transformer in javax.xml to transform xml file into fo file.

Original Code:

transformer.transform(xmlSource, new StreamResult(new File(filePath)));

Problem:

"javax.xml.transform.TransformerException: java.io.FileNotFoundException:" happens, although the file path is correct and file really exists.

Solution:

Using URI format.

Code:

File foFile = new File(filePath);
Result foResult = new StreamResult(foFile.toURI().getPath());
transformer.transform(xmlSource, foResult);

a small notation for ANTLR ( wrong spelling )

2006-10-31T07:50:00.000-08:00

Be careful when you use the ANTLR c++ version( I don't know if the problem happens in JAVA version ). You must care about the validation of every TOKEN name by yourself, ANTLR will not warn you, if the TOKEN is not really defined. It will simply create a new empty TOKEN for the undefined TOKEN. For exmaple:

rule
: SINGLE "hehe" // SINGLE doesn't appeared anywhere except here
;

SINGLE is actually not define in context. But ANTLR doesn't warn you that SINGLE is used but not defined as a parser rule or lexer rule. In constrat, ANTLR will create a new useless TOKEN named "SINGLE". Where is the problem? Think, if you occationally tipp a wrong TOKEN name, e.g. "SINGEL" for "SINGLE", and you don't mention it. After successful compiling, you may get an "unexpected TOKEN" exception. At this moment, you may confuse for a long time, why?, because all your defined rule is in the right way, where comes the exception? Check your word spell, you may find out the reason!

Where is my AST node?

2006-10-25T10:11:00.000-07:00

Recently I may find a bug in ANTLR c++ version. If i define a AST node, namely "as", as follow in parser, error message "as is undeclared" appears during the compiling phase:

rule1
: as:assignOperator COLON id:ID SEMI
{ table->addFunctionPair(as->getText(), id->getText()); } // as not declared? id works well!
;

I read the c++ source file created by anrlt and found that "as" is really not declared as "id". For "id" there are two varibles related with it, "id" and "id_AST", but for "as" there is only one varbile named "as_AST". I don't know why. A bug? So I use "as_AST" instead of "as" in my code. This can work around.

Add additional literal with with existed literal value

2006-10-13T03:14:00.000-07:00

we now have literal "const", the corresponding literal value is represented by varible "LITERAL_const". Now problem is that in gcc "__const__" has the same meaning as "const". People can use alternative operator "|" in every place where "const" is required. We can write the codes as following.

rule1
  : ("const"|"__const__") "int" ID
  ;

but if "const" is very frequently used, adding alternative operator will become complicated and unefficient. So people usually puts the alternative literal as ANTLRHashString into literals while the Lexer is initialized. With Anltr Java, you can do as follow:

class SomeLexer extends Lexer;
options
{
}
//initializing code
{
  void initialize() // initializer must be called after the lexer is created.
  {
    literals.put(new ANTLRHashString("__const__", this),
         new Integer(LITERAL_const);
  }
}

In Antlr C++ we don't have ANTLRHashString class, but actually, it is simpler than in Java, because literals is a std:map(or similar) object in Antlr C++, what we need to do is just:

class SomeLexer extends Lexer;
options
{
}
//initializing code
{
  void initialize()
  {
    literals["__const__"] = LITERAL_const;
  }
}

I am lazy again, but tired...

2006-10-08T15:19:00.001-07:00

Ok, i must say, I am lazy again now. I didn't do a lot of thing these days. But why do I feel always very busy? I am always on the way. On the way home, on the way to work, on the way to university and so on. I don't know where my time goes. I hope I can have more time a day, and I hope I can never feel so tired like now...

Java... knocked me out.

2006-10-01T09:13:00.000-07:00

It took me 10 hours to find out a "No Attribute is Implemented" Exception when I used "xml security for java" package to encrypt a xml data. The ONLY MISTAKE is just that I added a package, which appears as one of pre-requirement packages in the security package document, into my lib, and it raised a conflict with another package. After I removed this package, everything went well. Surely I am a freshmeat in the java world, but I have at least five-year C/C++ expierence. And I never encounted a problem in C/C++ world raised by library confiliction. The inconsistance among different packages is the death point of java, I think. I hate to waste so much time just because a conflict of packages. I found out that if you want to avoid this waste your time, it is better to write everything yourself from the basic API provided by java. But sometime this may cost more time... No efficiency, More complex, these are how I feel with my first blick into java world. Much worse is that you may never know what's going wrong with your program, because it is not the duty of your program, but some silly mistakes in evironment setting.

"=>": predicator and more

2006-09-19T13:04:00.000-07:00

On significant advantage in ANTLR is that you can use "=>" in parser to test the non-determinant grama. Look following example,

rule1
    :LCURLY rule3 RCURLY
    ;

rule2
    :LCRULY LPAREN rule3 RPAREN RCURLY
    ;

rule3...

expr:
    : rule1
    | rule2
    ;

Then expr is non-determinant, because rule1 and rule2 both begin with LCRULY. You may increase look ahead varible "k" to solve the problem. But sometimes k is also useless and increases the complexity of parser. So we can use "=>" to predicate the expr. We can write expr as follow:

expr:
    : (rule1) => rule1
    | rule2
    ;

ANTLR will try first rule1, if the input stream doesn't match rule1 then it must be rule2. One shortcome of this method is that rule1 will be executed twice. This also increases the complexity and hurts the performance. It is better to use some simple characteristic of different rules instead of whole rule for predication,

expr:
    : (LCURLY LPAREN)=> rule2
    | rule1
    ;

Changing the order of two rules and using LPAREN make expr-parsing more efficient.

customized "Delegate" or "EventHandler"?

2006-09-18T10:56:00.000-07:00

In C# we can define an event handler in an interface. Here is a lesson from me. If you want to transfer your own information into the event handler, you must not use the EventHandler provided by C#. As described in msdn, "EventHandler is a predefined delegate that specifically represents an event handler method for an event that does not generate data." That means you can also not cast the EventArgs in EventHandler to any other class derived from EventArgs. But if EventArgs is used in your customized Delegate, it can be right casted. A Example for better explaination:

// A customized EventArgs class
public class MyEventArgs:EventArgs
{
}

// A interface that contains a event handler
interface ITest
{
event EventHandler receiverHandler;
}

public class EventTrigger : ITest
{
public EventHandler MyHanlder;
private callHandler(MyEventArgs arg)
{
MyHandler(this, arg); // down cast from MyEventArgs to EventArgs
}
}

public class EventReceiver
{
public EventReceiver()
{
EventTrigger trigger = new EventTrigger();
trigger.receiverHanlder += new EventHandler(this.receiverHandler);
}

public receiverHandler(object this, EventArgs arg)
{
//Try to up cast arg to MyEventArgs
MyEventArgs cast_arg = (MyEventArgs)arg; //cast exception happens
}
}

You see the type casting exception happens because we use the EventHandler in Interface. If we define a customized handler, say MyEventHandler as follow,

public delegate void MyEventHandler(object this, EventArgs arg);

and declarate receiverHandler as MyEventHandler, then up casting operation in class EventReceiver will be permitted.

a small tip on output stream.

2006-09-15T06:05:00.000-07:00

For long time I suffered from the difficulty to turn on and turn off the output stream in my antlr emitter. Because antlr uses recusive detection, some rules may be called twice or more themselves in order to reach the aim. For Example, I need first get the AST refrence and then operate on it, I did before as follow:

expr1:
{ bAuto = false; }// turn off the output, because I only want to get the reference
pr:primaryExpr // Get it!!
{
bAuto = true; // after that, turn on the output
do some operation on pr and then...
primaryExpr(pr) // now the subrule will print the expression out
}

but Problem is, if primaryExpr can also call expr1 rule, then some additional string will be outputted before the right output. For a expresion a=b(), you may see b()a=b(). Now I use an additional local varible to solve this problem.

expr1:
{
bool bOldAuto = bAuto; // save the old setting
bAuto = false; // turn off the output whatever it is on or off.
}
pr:primaryExpr // Get it!!
{
bAuto = bOldAuto; // after that, restore the old setting
do some operation on pr and then...
primaryExpr(pr) // now whether the subrule will print
// the expression out is dependent on bOldAuto
}

This way ensures that only who turn off the ourput can turn on it.

ifstream problem

2006-09-03T14:32:00.000-07:00

I use ifstream class to access the user defined option in two different files. Problem is that if I use the same object of ifstream to access these two different files in turn, something went wrong when I access the second file. So I create different object of ifstream for each file, then everything goes well. At first I think people must use different ifstream object to access different file. But when I compile the old files on another machine, the problem happened on my laptop didn't appear. I was confused. I checked gcc version, this may be reason. The gcc version on my laptop is 3.4.6, on the other machine it is 4.1. I hope this is the bug in gcc.

with # or without # in Anltr (using c++ antlr lib)

2006-08-30T13:54:00.000-07:00

In ANTLR you can label your rules with an identifier , for example, lb:expRule. "lb" will represent ASTNode returned by rule "expRule". There are two ways to use "lb", without #, e.g. lb->getText(), and with #, e.g. #lb->getText(). I always think #lb is the same as lb, but actually it is NOT! they represent two ASTNodes that clone the ASTNode returned by rule "expRule". Don't mixed using these two ways, It will confuse you why the changes I made doesn't work.

A simple example:

assignExpr: #( ao:NAssignOperator e1:expr { printContent(ao); } e2:expr )
{
e1->setText("test1");
#e1->setText("test2");
printf("%s", e1->getText()); // output: test1
}
;

I don't know whether it is a c++ version characteristic, because I did't use the java version.

Why does g++ not compile my changes with "automake"?

2006-08-30T13:28:00.000-07:00

After I started to program under linux, this is always a question symbol in my head. Today I find out the reason. An example for this question:

I changed a in-place implemented function init() in a head file. In order to make this changes to work with automake, the old object file that use this function should be deleted.

So why? I guess the reason is, if you implement a method in the head file, it will only be compiled when a c++ source file use this method and added into the corresponding object file of this source file. If no one uses this method, this part of code may be simply ignored by compiler ( in the situation you use automake to batch the compiling work ) and not added into any output files for optimal reason -- because no one uses it.

A little step in my Life

2006-08-30T11:12:00.001-07:00

A friend of mine sugguested me to start a technical blog so that I can remember solutions of the encounted problems during my programing life. I have also thought about it before, but because of lazi.... I didn't start this blog until today. But from this momnet I will try my best to maintain this blog and record one part of my life. At first I will simply list the project I am and was working on.

Project "pre-virtualization":

This is a project of virtualization in University Karlsruhe where I am studying now. My master thesis is writing a gramma parser for pre-virtualization technique so that people can use the parser to analyz c source code, find the things they want and replace them as their wish. The major tool I use is ANTLR, a parser genarator.

Language parsing and ANTLR are both new concept for me. I have struggled with them for about 2 months and at last get some little success. I will write down the expierence during the implementation later in this blog.

Project "EQSIM":

Also a project from University Karlsruhe. My job is kind of improving the ability of EQSIM server side application and developing the web interfaces and services for EQSIM project. I didn't touch web developing before, so it is really a challenge for me. Web technique I used are php and Ajax.

Project "MobiNaf"

A mobile e-guider porject from FZK ( Forschungs Zentrum Karlsruhe ). I am responding to the GPS navigation module in this Project. The basic functionalities are implemented. Future work includes testing alarm functionality and integret the module into main project. I learn a lot about project organization and software design from this project. I am also thinking over whether I promote this module into navigation software. only for fun and more expierences in mobile development.

Project "SIPPS"

An old project when I worked in Rapidsulotion Corp. From this project I really understood what is OO programing, how to use Visual Studio. Maybe I will write some usefule things from this project.