Process Context ID and the TLBLast edited on Nov 11, 2015

In an earlier post I said that the x86_64 architecture did not have a way to tag TLB entries. Apparently, it is possible. I don't know how I missed it. But there are caveats. I wrote another post about memory paging: Memory Paging

What the TLB does

The TLB is a cache for page translation descriptors. It stores information about virtual to physical memory mapping. When the CPU wants to access memory, it looks for a translation in the TLB. If a translation is not cached in the TLB, then this is considered a "TLB miss". The CPU then has to fetch the page descriptor from RAM using the table pointer stored in register cr3. Once the descriptor is loaded in the TLB, it stays there until the TLB gets full. When the TLB is full, the CPU purges entries to to replace them with newer ones. Access to the TLB is a lot faster than accesses to RAM. So The TLB really is just a page descriptor cache.

Benefits of TLB tagging

On the x86 architecture, when loading the cr3 register with a new PML4 address, the whole TLB gets invalidated automatically. This is because entries in the TLB might not describe pages correctly according to the new tables loaded. Entries in there are considered stale. Adress vX might point pX, but before the PML4 change, it was pointing to pY. You don't want the CPU to use those mappings.

Normally, you would change the mapping on a process change. Since the page mapping is different for each process. But the TLB is quite large. It could easily hold entries for 2 processes. So a TLB flush would be expensive for no reason. That is why Process Context Identifiers (PCID) were introduced.

First, you need to enable the PCID feature on the CPU in the cr4 register. With PCID enabled, a load to cr3 will no longer invalidate the TLB So this is dangerous if you do not maintain the PCID for each process at that point. Now, everytime you load cr3, you must change the current PCID. Each Entry added in the TLB will be tagged against the current PCID. This "tag" is invisible to us, it is only used internally in the TLB (The whole TLB is invisible to us anymway). So now, if two process access adrress vX with two different physical mapping, those two addresses can reside in the TLB without conflicting with each other. When doing a lookup in the TLB the CPU will ignore any entries tagged against a PCID that is different than the current one. So if virtual address vA exists in the TLB, and is tagged with PCID-1, then process 2 tries to use address vA, the CPU will generate a TLB-miss. Exactly what we want.

But then what about pages such as the one that contains the interrupt handler code? Every thread will want such a page mapped and the mapping would be identical. Using PCIDs would result in several TLB entries describing the same mapping but for different PCID. Those entries pollute the TLB (and waste precious cache space) since they all map to the same place. Well this is exactly why there is a "g" bit, the Global flag, in each page descriptors. The CPU will ignore the PCID for pages that are global, It would be considered an incorrect usage of the paging system if a page is global but has a differnt physical address on different threads. So the global flag is to be used carefully. I use it for kernel code and MMIO.

Advantages at a certain cost

So PCIDs are a way to avoid flushing the TLB on each cr3 load, which would become VERY expensive as the CPU would generate TLB-misses at every context switch. Now, there are no more TLB flushes but the tagging still guarantees integrity of page mapping accross threads. Can you see how important that feature is and how big the befefits are? This will considerably increase performances in your OS.

But there is one thing you must consider. When destroying a process and then, possibly, recycling the processID for a new process, you must make sure that there are no stale entries of that last process in the TLB. The INVPCID instruction is just for that. It will allow you to invalidate all TLB entries associated to a particular PCID. But then, if you are running in a multi-CPU system, things get complicated. The INVPCID instruction will only execute on the CPU executing it (obviously). But what if other CPUS have stale entries in their TLB? You then need to do a "TLB shootdown". In my OS, a TLB shootdown is done by sending an Inter-Processor Interrupt (IPI) to all CPUs. The IPI tells them to invalidate their TLB with the PCID that was shared as part of the IPI. As you can guess, this can be very costly. Sending an IPI is very expensive as all CPUs will acquire a lock, disabled their interrupts plus all the needed processing. But it would only happen everytime a new process gets created.

How to use it

First, enable the PCID feature. This is simply done by setting bit 17 in CR4. Then, everytime you load CR3, the lower 12bits are used as the PCID. So you need to guarantee a unique 12bit ID for every process. But that can be a problem. 12bits only allows 4096 processes. If you plan on supporting more than 4096 process simultaneously, then you will need to come up with some dynamic PCID scheme.

Unfortunately, my CPU does not support INVPCID. It does support PCID though. It make no sense, in my head, that the CPU would support PCID but not INVPID. So I had to work around it. I found the solution by starting a thread at forum.osdev.org. By setting bit 63 of cr3, the CPU will delete all TLB entries associated with the loaded PCID. So I came up with the following solution

// emulate_invpcid(rdx=PCID)
// will invalidate all TLB entries associated with PCID specified in RDI
// This emulation uses bit63 of cr3 to do the invalidation.
// It loads a temporary address
    push        %rax
    and         $0xFFF,%rdi
    or          $PML4TABLE,%rdi
    btsq        $63,%rdi
    mov         %cr3,%rax

    // We need to mask interrupts because getting preempted
    // while using the temporary page table address
    // things would go bad.
    mov         %rdi,%cr3
    mov         %rax,%cr3
    pop         %rax

Thread management in my hobby OSLast edited on Oct 26, 2015

I thought I'd write a little more about my home-grown x86-64 OS. This is about my threading mechanism.

The Task list

The global task list contains a list of 16bytes entries that contains the adress of the PML4 base for the task and the value of the Ring0 RSP. Since task switches always occur during Ring0, only the RSP0 needs to be saved (RSP3 will have been pushed on stack during privilege change). Upons switching task, the scheduler will restore cr3 and rsp from the list.

Task State Segment

In 64bit long mode, the TSS doesn't have as much significance than in protected mode when hardware context switching was available. The TSS is only used to store the RSP0 value. When a privilege change is performed, from Ring3 to Ring0, the CPU will load the TSS.RSP0 value in RSP and the old RSP3 value will have been pushed on the Ring0 stack. So the IRET instruction will pop out the Ring3 RSP value (hence why it is not needed in the TSS). The only time that the CPU will look into the TSS is during a privilege switch from Ring3 to Ring0.

Only one TSS is needed in the system since the value it contains is a virtual address. Every task will use the same address for RSP3 and RSP0 but it will be mapped differently.

So the TSS is only used to tell the process which address to use for the stack when going from Ring3 to Ring0. Since that address is the same virtual address for every task, only 1 TSS needs to be created.

There is no point in showing the TSS here since only one value is used. It's basically a 0x67 bytes long table with a 64bit entry at byte index 4 that represents the RSP0 value. the rest of the table can be filled with zeros

Kernel and user tasks

Kernel tasks have the following properties:

  • Run in ring0.
  • Their Code Segment Selector is the same as the kernel.
  • Each kernel task has its own stack.
  • Code is located in kernel memory which is the identity-mapped portion of virtual memory.
  • The RSP value that is set in the Ring0 stack (for iret) upon task creation is the ring0 stack pointer.

User tasks have the following properties:

  • Run in ring3
  • Their Code Segment Selector is the same for all user thread.
  • Their Code Segment Selector has DPL=3
  • Each user task has 2 stacks: one for Ring0 and one for Ring3
  • Code is relocated at load time and appears to be running at virtual address 0x08000000
  • The RSP value that is set in the ring0 stack (for iret) upon task creation is the ring3 base stack pointer.


When an interrupt occurs, the Trap or Interrupt Gate contains a DPL field and target Selector field. The DPL will always be set to 3 so that any privilege levels (Ring0-Ring3) can access the interrupt handler. The target selector is for a Code Segment Descriptor (inthe GDT) with a DPL value of 0. This will effectively run the handler in Ring0.

Interrupt or task switch during user task

If the interrupt occured during a user task, the task may have been in Ring3 or in Ring0 if in the middle of a system call. If a privilege change occurs, the value of RSP will be set to the value in the TSS for RSP0. That value is the same for all tasks but mapped differently to physical memory. The ring3 stack will be left untouched.

If there is no privilege change, then the same stack will be used. The scheduler algorithm doesn't need to change since the Ring3 stack's RSP has been pushed sometime before when entering Ring0 (ie: when calling a system function)

Interrupt or task switch during kernel task

If the interrupt occured during a kernel task then nothing special happens. The same stack is being used and same protection level is applied. Although it would be possible to use the new ITS mechanism to use another stack during interrupt handling. This would be usefull, for example, when a stack overflow occurs in a kernel thread and the #PF exception is raised. If there is not stack switch, then the return address can't be pushed on the stack since the stack if faulty (hence the #PF). So using another stack for interrupts would be a wise choice. But I'm not implementing this for now.

Task switch

A task switch will always be initiated by the timer iterrupt. The scheduler runs in Ring0 so the Ring0 stack is used. If the interrupted task was in Ring3, we don't need to worry about its stack since RSP has been pushed on the Ring0 stack. The current CPU context will be saved on the Ring0 stack. Therefore, the scheduler will always save the RSP value in the tasklist's rsp0 entry since it occurs in ring0 code. Upon resuming the task, RSP will be reloaded from the rsp0 entry, context will be restored and the iret instruction will pop the ring3 RSP to resume execution.

In a multi-cpu system, it would be possible to have less threads running than the number of CPUs. In that case, upon task-switching, a CPU would just continue to run its current thread, giving 100% of its time to that thread. But for other CPUs that don't have any task to execute, they should get parked. Once a CPU's thread is terminated, if there is no other threads to run for him, then it will parked. Normally the CPU would load the context of the next task but instead it will simply jump to a park function. Since the scheduler is invoked through an interrupt, we eventually need to "iret". But in the case of parking, we will just "jmp" to a function and spin indefinitely. The iret instruction would restore flags and pop out the stack a jump to a return address but in this case we don't want to do any of that. Since there are no flags to restore, no return function and no stack to clean. The park function does the following:

  • load kernel PML4 base address in cr3 to restore identity paging
  • load RSP with a stack unique for the current CPU
  • acknowledge interrupt (APIC or PIC)
  • restore interrupt-enable flag (cleared when entering handler)
  • spin-wait with "hlt" instruction.

    // Set back the kernel page tables, 
    mov         $PML4TABLE,%rax
    mov         %rax,%cr3

    // set back the cpu's stack. This could be 
    // optimized but kept the way it is for clarity purposes. 
    // We're parking the CPU... it's not like we need the performance here
    mov         APIC_BASE+0x20,%eax
    shr         $24,%eax
    mov         %rax,%rsp
    shl         $8,%rsp
    add         $AP_STACKS,%rsp

    // re-enable interrupts and set some registers for debug and wait 
    mov         $0x11111111,%rax
    mov         $0x22222222,%rax
    mov         $0x33333333,%rax
    call        ackAPIC
1:  hlt
    jmp         1b

Since interrupts are re-enabled and APIC has been ack'd, we will continue to be interrupted by the timer and we are ready to take on a new task at any time. It would be wise to warn the parked CPU about newly created tasks (with IPIs) so we don't need to wait until the timer to kick in. But that's for another day.

Creating a new task

When a new task is created, memory is allocated for its stack and code. An initial context is setup in the newly created stack. All registers are initialized to 0. Since the task will be scheduled by an interrupt handler, it needs to have more data initilased in the stack for proper "iret" execution. Of course, the RSP value saved in the task list will be the bottom of that context in the task's stack. The initial stack looks as follow:

Stack top
152 SS 0 for kernel thread / Ring3 selector for user thread
144 RSP Ring0 stack top or Ring3 stack top
136 RFLAGS 0x200202
128 CS Ring0 Code selector or Ring3 Code selector
120 RIP entry point for Kernel thread / 0x080000000 for User thread
112 RAX 0
104 RDI 0
96 RBX 0
88 RCX 0
80 RDX Parameter to pass to thread on load
72 RSI 0
64 RBP 0
56 R8 0
48 R9 0
40 R10 0
32 R11 0
24 R12 0
16 R13 0
8 R14 0
0 R15 0
Stack bottom

Scheduling algorithm

My scheduling algorithm is nothing fancy. Just the good old round-robin way. But on multi-processor, it is probably the worse thing you could do. Here is an example task list (Note that I should also use a linked list instead of a fixed size table)


As this table show, each task except Task5 are running on one of the 4 CPUS. At the next schedule(), the task list will look like this:


The problem here is that Task 1,2 and 3 are still running. So doing a context switch imposed a large overhead for no reason. But the fact that they are still running is good, but they are not running on the same CPU anymore. So they will never fully benefit from the CPU cache since memory will need to be fetched all over again because that CPU had no idea about the code and data being used by the task. A better algorithm would detect that the task should continue to run on the same CPU. I need to take the time to think about it.

Ring 3 tasks

To make a task run in ring3, it needs the following

  • A "non-conforming" code segment descriptor with DPL=3.
    63 Irrelevant 1000Irrelevant 48
    47 P:1DPL:311C:0R:1A:0 Irrelevant 32
    31 Irrelevant 16
    15 Irrelevant 0
  • cs must be loaded with RPL=3
    15 GDTIndex15:3 TI:0RPL=3 0
  • A writable data segment with DPL=3. This is for the stack.
    63 Irrelevant 1000Irrelevant 48
    47 P:1DPL:310E:0R:1A:0 Irrelevant 32
    31 Irrelevant 16
    15 Irrelevant 0
  • ss must be loaded with RPL=3
    15 GDTIndex15:3 TI:0RPL=3 0
  • The task register must be loaded with a valid tss selector. The TSS should be initialzed with a valid RSP0 value for when the code switches to Ring0 (interrupts). TSS Descriptor:
    63 base31:24 10000 48
    47 P:1DPL:301001 base23:16 32
    31 base15:0 16
    15 0x67 0

Please refer to Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3 for more information These values would be on the stack prior to invoking "iret" from the scheduler. The scheduler runs in ring0, hence why the RPL value in selectors is important

Memory layout

The kernel's page tables is as follow:

  • The first 128mb is identity mapped using 2mb pages (first 64 page directory entries).
  • The rest of the available memory is identiy mapped with 4k pages.
  • The whole memory is again identity mapped, using 2mb pages, at 0x4000000000.

The kernel's 4k pages is only used to track free pages to be distributed to requesting threads. Each 4k page entry has its 3 AVL bits cleared. This is how the kernel keeps track of available memory. A page with non-zero AVL is in use. So when a process needs to create a new page, it does the following:

  • look through the kernel 4k pages structure for a free page. Mark is as not-free
  • look though the process 4k pages structure for a free page. Mark is as not-free
  • take the physical address of the kernel page (easy since it is identity mapped) and store it in the process page entry. The process's page now maps to the proper physical page.

The AVL bits are set as follow:

  • 0b000: physical memory pointed to by this page is free to use
  • 0b001: physical memory pointed to by this page is also mapped somewhere else and is a stack page for a thread
  • 0b010: physical memory pointed to by this page is used by the kernel
  • 0b011: physical memory pointed to by this page is used as heap for a thread or the kernel

Creating a process

When creating a new process, the process code will start at 0x8000000. So the kernel will reserve a physical page (as per the process in step 1 above). The physical address of that page will be used in the process's page entry for address 0x8000000. This should correspond to Page Directory entry #64. Since the first 64 entries are 2mb pages and the rest are pointers to page tables, then this virtual address maps to a 4k page. So all processes will see their entrypoint at 0x08000000 but they will obviously be mapped to different physical pages. This allows to to compile position dependant code and run it in the OS.

Whole memory identity mapping

Each process have their own virtual address mapping. If a process calls a system function that needs to manipulate physical memory this causes a problem. For example, if a process wants to allocate memory, it needs to access it own page tables. but the pages reside above kernel memory so it is not mapped into process virtual addressing space. The same can happen when trying to create a process: The system call will reserve a virtual address in its page tables, which is identity mapped, but then it will attempt to fill in some data in the physical page, that physical page resides above the kernel memory, so it is not mapped in the process. for example:

  • Kernel memory ends at 0x08000000. Kernel page tables are 0x00020000.
  • The kernel page tables is just a list of identity mapped pages above kernel memory with the AVL field indicating if the page is available.
  • The first entry maps to physical location 0x08000000. So when searching for a free page, the kernel will find, for example, an entry at 0x00020B00 with the AVL bits set the "free".
  • This entry maps to 0x08000000+(4096*(B00/16)) = 0x080B0000.
  • The process would like that physical address to be mapped to 0x08001000 and fill it with zeros. Two problem arises:
    • The process cannot modify its page table to write an entry for 0x08001000 since its page tables are not mapped.
    • It cannot fill the page with zeros prior to map it since the page is not mapped and it cannot access 0x080B0000 directly because this is a physical address and it would be interpreted as a virtual address by the CPU.

The solution is to keep an indentity mapping of the whole memory at some other address. Lucky for us, with 64bit addressing we have a very large address range. So identiy mapping will start at 0x4000000000 (256th gig). That address will map to physical address 0x00000000. So by getting the PLM4 address from cr3 and adding 0x4000000000 (or simply setting bit38), the process can now access its page tables.

Dynamic stack growth

A user thread is initially created with a 16k stack. If the thread attempts an access below the bottom of its stack, a Page Fault exception (#PF) will occur since the page will not be mapped (unless the access went as far down as the heap, in which case corruption would happen). The #PF handler will verify it the fault meets all the following conditions:

  • Fault was caused by a not-present page.
  • Fault was caused by an instruction executing in Ring3.
  • Fault was caused by a write operation.
  • Pages above the faulting address is a stack pages

If any of those condition is not met, the thread dies. If all of the conditions are met, then the OS allocates a page for that address. The goal here is to try to recognize that the fault was caused by a user thread wanting to use more stack space than it currently can in order to grow its stack. The first 3 conditions are easy to understand. But 4th condition is unfortunately not that good. It would be nice if the Exception error code would tell us if this operation was using rbp or rsp, or any implied usage of the ss segment segment selector. for example, all these operations should be recognized as stack growth demand:

  • push %rax
  • mov %rax,(%rsp)
  • mov %rax,-5000(%rbp)
  • mov %rax,-5000(%rbp)
  • And to some extent: lea -10000(%rsp),%rax; mov %rbx,(%rax)

But it's impossible to detect all those conditions. So unfortunately, the best we can do is to detect if the faulting address is in a page right under the bottom of the stack. So we just find the page table entry for the faulting address, check if it is free and check if the next one is a stack page. If all is good, then we allocate the page and return from the exception to retry the offending instruction and it should succeed.

But this algorithm is not perfect. What if the thread's RSP is at the bottom of the stack and it tries to write at -5000(%rsp). This would fall 2 pages down below the bottom of the stack so the check would fail. Unfortunately, I can't think of any better way of doing this. I wish Intel could give us a hint that the #PF was due to a stack operation. After all, they seem to be able to make that deduction when trigerring #TS. So it means that the following code could potentially be dangerous:

// This would be dangerous
void test1()
    char a[0x2000];

// This would be safe.
void test1()
    char a[0x2000];

    // the fact that we access a page that is no further than 0x1000 from
    // the bottom of the stack will make the #PF correctly create the page
    // Doing this is called Stack Probing
    a[0x1001] = a[0x1001];

After trying to find an alternate solution, I found out that apparently Windows and linux are facing the same dillema. Apparently, my algorithm is good. When compiling a C application under those OS, the compiler will detect if the program tries to allocate more than one page on the stack and will generate "stack probing" code. So Stack Probably is a well-known technique to work around that limitation. But if you write a ASM application under linux or windows, then you need to take care of that.

Another possible way I will eventually explore is to set the stack memory at virtual location 0x1000000000000. By looking at bit 47of the offending address, I would get a strong hint about this being a stack operation. This means the OS couldn't support systems with more than 256 terabytes of RAM.... It also has other downsides.

Enabling Multi-Processors in my hobby OSLast edited on Oct 19, 2015

I recently added multi-processor support in my homebrew OS. Here are the technical details. BTW: Chapter 8 and 10 of the Intel Manual 3 are probably your best resource.

When the system starts, all but one CPU is halted. We must signal the other CPUs to start. I won't go into the details of how to bootstrap the processor, that step is easy: just go in protected mode then setup paging and jump to long mode. This is very well covered in the Intel manuals.

Basically, this is how we switch to protected mode

    // Before going any further, you must enable the A-20 line. Not covered in this example

    push    %cs     /* remember, cs is 07C0*/
    pop     %ds
    mov     $GDTINFO,%eax
    lgdtl   (%eax)
    mov     %cr0,%eax
    or      $1,%al
    mov     %eax,%cr0   /* protected mode */
    mov     $0x08,%bx

    // far jump to clear cache

     // GDT INFO
    .WORD 0x20
    .LONG . + 0x7C04    /*that will be the address of the begining of GDT table*/

    // GDT
    .LONG 00
    .LONG 00

    // GDT entry 1. Data segment descriptor used during unreal mode
    .BYTE 0xFF
    .BYTE 0xFF
    .BYTE 0x00
    .BYTE 0x00
    .BYTE 0x00
    .BYTE 0b10010010
    .BYTE 0b11001111
    .BYTE 0x00

    // GDT entry 2. Code segment used during protected mode code execution
    .BYTE 0xFF
    .BYTE 0xFF
    .BYTE 0x00
    .BYTE 0x00
    .BYTE 0x00
    .BYTE 0b10011010
    .BYTE 0b11001111
    .BYTE 0x00

    // GDT entry 3. 64bit Code segment used for jumping to 64bit mode.
    // This is just used to turn on 64bit mode. Segmentation will not be used anymore after 64bit code runs.
    // We will jump into that segment and it will enable 64bit. But limit and permissions are ignored,
    // the CPU will only check for bit D and L in this case because when we will jump in this, we will
    // already be in long mode, but in compatibility sub-mode. This means that while in long mode, segments are ignored.
    // but not entiorely. Long mode will check for D and L bits when jumping in another segment and will change
    // submodes accordingly. So in long mode, segments have a different purpose: to change sub-modes
    .BYTE 0xFF
    .BYTE 0xFF
    .BYTE 0x00
    .BYTE 0x00
    .BYTE 0x00
    .BYTE 0b10011010
    .BYTE 0b10101111  // bit 6 (D) must be 0, and bit 5 (L, was reserved before) must be 1
    .BYTE 0x00

This is how we switch to long mode

    // Before going any further, you must  setup paging structures.
    // Not covered in this example since it is very easy and well document
    // in the Intel manuals
    mov     $8,%ax
    mov     %ax,%ds
    mov     %ax,%es
    mov     %ax,%fs
    mov     %ax,%gs
    mov     %ax,%ss

    // set PML4 address
    mov     $PML4TABLE,%eax
    mov     %eax,%cr3

    // Enable PAE
    mov     %cr4,%eax
    or      $0b10100000,%eax
    mov     %eax,%cr4

    // enable long mode
    mov     $0xC0000080,%ecx
    or      $0b100000000,%eax

    //enable paging
    mov     %cr0,%eax
    or      $0x80000001,%eax
    mov     %eax,%cr0
    ljmpl   $0x18,$LONG_MODE_ENTRY_POINT

So at this point, the kernel is running in 64bit long mode.

Detecting the number of CPUs

The first thing to do is to detect the number of CPUs present. This can be done by looking for the "MP floating pointer" structure. It is located somewhere in in the BIOS address space and we must find it. I won't go into the details of the structure since it is very well documented everywhere. The MP structure contains information about the CPUs and IO APIC on the system. This structure is filled in by the BIOS at boot time. The structure can be at many places hence why we must search for it in memory. It starts with "_MP_" and contains a checksum, so by scanning the memory, you will find it. The important thing to know is that you do the following:

  • Find the structure in memory. According to the specs, it can be in a couple of different places.
  • Detect number of CPUs and Local APIC address of CPUs
  • Detect IO APIC address.

For more details on how to find the structure and its format, make a search for "Intel Multi-Processor Specification".

When wandering in the SMP world, you must forget about using the PIC (Programmable Interrupt Controller) The PIC is an old obsolete device anyway. The new way now is the use the APIC. So we won't be using the PIC anymore. There is a notion of a local APIC and the IO APIC. The local APIC is an APIC that is present on each CPU. The local APICs can be use to trigger interrupts from one CPU to another, as a way of communication. When the system starts, all but one CPU is halted. We must signal the other CPUs to start. The PIC could not allow us to do that, hence why we must use the APIC. The local APIC will allow us to trigger an interrupt on the other CPUs to get them out of their halted state.

We must then setup the local APIC for the current CPU. Each CPU have their own APIC and their APIC is mapped at the same address for each CPU. The local APIC address is 0xFEE00000. So when CPU0 read/writes at 0xFEE00000 it is not the same as if CPU1 read/write at 0xFEE00000 since the address maps to each CPU's own APIC. This is nice because it means you dont need to do something like "What CPU am I? number x? ok, then use address xyz then." Each CPU only need to write at the same address and they will be guaranteed to write to their own APIC. It's all transparent so you don't need to worry about it. The address of the IO APIC maps to the same IO APIC for all CPUs though. But that's also good because all CPUs want to use the same IO APIC anyway.

    mov     $APIC_BASE,%rdi
    mov     $(SPURIOUS_INTERRUPT_VECTOR | 0x100), %rax   // OR with enable flag

Then, we start the APs

    #define WAIT(x) push %rcx; mov $x,%rcx; rep nop; pop %rcx;
    #define STALL() 1337: hlt; jmp 1337b;
    #define COUNT_ONES(regx,regy) push %rcx; \
        xor regy,regy; \
        1337:; \
        cmp $0,regx; \
        jz  1338f; \
        inc regy; \
        mov regx,%rcx; \
        dec %rcx; \
        and %rcx,regx; \
        jmp 1337b; \
        1338:; \
        pop  %rcx

    mov     $APIC_BASE,%rdi
    mov     $0xC4500, %rax              // broadcast INIT to all APs
    mov     %eax, APIC_REG_INTERRUPTCOMMANDLOW(%rdi)
    WAIT(100000000)                     //1 billion loop should take more than 10ms on a 4ghz CPU
    mov     $0xC4600, %rax              // broadcast SIPI to all APs
    mov     $SMP_TRAMPOLINE,%rcx
    shr     $12,%rcx
    and     $0xFF,%rcx
    or      %rcx,%rax
    mov     %eax, APIC_REG_INTERRUPTCOMMANDLOW(%rdi)

    mov     STARTEDCPUS,%rbx
    cmp     CPUCOUNT,%rdx
    jz      1f
    mov     %eax, APIC_REG_INTERRUPTCOMMANDLOW(%rdi)
    mov     STARTEDCPUS,%rbx
    cmp     CPUCOUNT,%rdx
    jz      1f
    //CPUs are not all started. should do something about that

The SMP_TRAMPOLINE constant is the address of where I want the APs to jump to when starting. This address must be aligned on a 4k boundary because we the SIPI message takes the page number as a parameter. Hence why I SHR the address by 12 (div by 4096). And since the APs will start in 16bit mode, the address must reside under the 1meg barrier. STARTEDCPUS is a 64bit bitfield that represents the CPUs. Each bit get set by the APs (cpuX sets bit X).

Application processors trampoline code

I decided to put the Application Processor's trampoline code in the bootloader (I've got 512bytes of room, that should be enough). The bootloader is a good decision beacause it is below the 1meg mark, the source file is compiled as 16bit code and all the initialisation is done there anyway. But when an AP starts, it will be given a start address aligned on a 4k page boundary and the bootloader is at 0x7C00. So the bootloader will copy a "jmp" at 0x1000 to jump to the bootloader AP init function. So the order of execution is:

  • AP receives SIPI with vector 0x01
  • AP jumps to 0x1000
  • Code at 0x1000 will make AP jump to 0x7C0:
  • AP will switch protected mode and jump to KernelMain
  • KernelMain will check in MSR[0x1B] if this is an AP or the BST. if BST, then jump to normal initialisation
  • setup the temporary stack for the AP's thread of exeuction: 0x70000+256*APIC_ID (256 bytes stacks)
  • enable long mode (64 bit)
  • set CPU started flag in global variable: STARTEDCPU = STARTEDCPU | (1<

    So now I have multiple processor ready for work. The next step is to make a SMP compatible scheduler and start using the IO-APIC. I'll cover that another time.

SHA256 assembly implementationLast edited on Oct 11, 2015

Assembly implementation

For a moment now, I've been wanting to try the intel AVX instructions. So I decided to write an SHA256 function in pure x86-64 assembly. That algorithm might not be the best thing to parallelize though but it still was fun to do.


The use of AVX instructions in this algorithm might not give better performances. The only reason I did this was because I wanted to play with AVX. Using AVX2 could probably help a lot more since a lot of the AVX instructions could be elliminated.

In fact, I'm not entirely convinced that using AVX will benefit a lot. One thing to consider here, is that for small hashes it could be slower. The thing is that when using AVX, you are using the xmm/ymm registers. During a context switch, the OS does not automatically save/restore the state of the AVX registers. Those are lazy-saved. Meaning that, without going too much into the details, the CPU will only save/restore the AVX registers if it detects that the current thread is using them (using a dirty flag and an exception). Such a save/restore is crazy expensive. So introducing the usage of AVX registers in a thread will cost a lot for the context switch, yielding less processing time for the thread. So the thing to consider is: will the thread use the AVX instructions enough to overcome the cost of the context switch?

New Home Automation systemLast edited on Aug 5, 2015


During the past months, I've been working on my Home Automation System. I did some major refactoring and moved away from the rPi. I am now running my home automation software on a x86-64 server.

The projects is hosted on github at https://github.com/pdumais/dhas.

The system uses a modular architecture now. I like to think of DHAS as a hub for different technologies. Since my home automation system is mix of Insteon devices, ethernet relays and temperature sensors, IP phones, and more, I made a central software that can interface with all those technologies. Each module is responsible for interfacing with one technology. on github, you will find these modules under the src/module folder. Everytime I need to add a new kind of module, I just create the class and it automatically gets instanciated and used. The modules register their own REST callbacks and the REST engine being self-documenting will show the newly added functions when querying the help API. This way, the system doesn't know anything about its modules. It only knows that it is running modules. So adding new modules becomes very easy because the work is isolated from the rest of the system.

The most simple module to look at is the Weather Module.


Since I am not using the rPi anymore, I needed to find a way to get GPIOs on the server. So I bought an Arduino Leonardo and made a very simple firmware that presents the device as a CDC device using the LUFA library. The source code for the firmware is here:


#include "usblib.h"

#define STABLE 100

uint8_t currentData = 0;

Sent byte to host:
bit     Arduino pin     AVR Pin
0           2               PD1
1           4               PD4
2           7               PE6
3           8               PB4
4           12              PD6

    'a' -> arduino 10 -> PB6   ; 'a' = ON, 'A' = off
    'b' -> arduino 11 -> PB7   ; 'b' = ON, 'B' = off
to test the live stream: cat /dev/ttyACM0 | xxd -c1

void setCurrentData(uint8_t data)
    currentData = data;

void sendCurrentData()

int main(void)
    uint8_t pb,pd,pe;
    uint8_t newData = 0;
    uint8_t lastData = 0;
    char stabilizerCount = -1;


    // Set pins as pullups
    PORTB |= ((1<<4));
    PORTD |= ((1<<1)|(1<<4)|(1<<6));
    PORTE |= ((1<<6));
    // Set pins as input
    DDRB &= ~((1<<4));
    DDRD &= ~((1<<1)|(1<<4)|(1<<6));
    DDRE &= ~((1<<6));

    // set PB6 and PB6 as output
    DDRB |= (1<<6)|(1<<7);
    PORTB |= (1<<6)|(1<<7); // initially off (high = off)

    uint8_t receivedChar;
    while (1)
        pb = PINB;
        pd = PIND;
        pe = PINE;

        newData = ~(((pd>>1)&1)|(((pd>>4)&1)<<1)|(((pe>>6)&1)<<2)|(((pb>>4)&1)<<3)|(((pd>>6)&1)<<4));
        newData &= 0x1F; // clear 3 top bits since we don't use them

        if (GetCDCChar(&receivedChar))
            if (receivedChar == '?')
            else if (receivedChar == 'A')
                PORTB |= (1<<6);
            else if (receivedChar == 'B')
                PORTB |= (1<<7);
            else if (receivedChar == 'a')
                PORTB &= ~(1<<6);
            else if (receivedChar == 'b')
                PORTB &= ~(1<<7);

        // debounce
        if (lastData != newData)
            stabilizerCount = STABLE;
        if (stabilizerCount>0) stabilizerCount--;
        if (stabilizerCount==0)
            if (currentData != newData)



#include "usblib.h"
#include "Descriptors.h"

USB_ClassInfo_CDC_Device_t VirtualSerial_CDC_Interface =
.Config = {
    .ControlInterfaceNumber = INTERFACE_ID_CDC_CCI,
    .DataINEndpoint = {
        .Address = CDC_TX_EPADDR,
        .Size = CDC_TXRX_EPSIZE,
        .Banks = 1,
    .DataOUTEndpoint = {
        .Address = CDC_RX_EPADDR,
        .Size = CDC_TXRX_EPSIZE,
        .Banks = 1,
    .NotificationEndpoint = {
        .Banks = 1,

void CDCWork()

uint8_t GetCDCChar(uint8_t* data)
    int16_t r = CDC_Device_ReceiveByte(&VirtualSerial_CDC_Interface);
    if (r >= 0)
        *data = r;
        return 1;
    return 0;

void SendCDCChar(uint8_t data)
    CDC_Device_SendByte(&VirtualSerial_CDC_Interface, data);

void InitCDC()
    MCUSR &= ~(1 << WDRF);

void EVENT_USB_Device_Connect(void)

void EVENT_USB_Device_Disconnect(void)

void EVENT_USB_Device_ConfigurationChanged(void)
    bool ConfigSuccess = true;
    ConfigSuccess &= CDC_Device_ConfigureEndpoints(&VirtualSerial_CDC_Interface);

void EVENT_USB_Device_ControlRequest(void)

void EVENT_CDC_Device_LineEncodingChanged(USB_ClassInfo_CDC_Device_t* const CDCInterfaceInfo)