Miscellaneous Linux Patches


Cache colouring task_struct ( version 1 )

This is a simple patch for x86 CPU family with 32 bytes cacheline size ( can be easily changed to other sizes ) that colours "struct task_struct" allocations inside the kernel by adding four different colours that will offer a collision reduction of about 1/4 :


Cache colouring task_struct and kernel stack

This patch cache-colours both task_struct and kernel stack using a slab allocator for task_struct and initial stack pointer jittering for kernel stack. An extra structure is defined for task_struct allocations as long as a new init task structure :


#define TSK_TO_KSTACK(p)    (((struct full_task_struct *) (p))->stack)
#define TSK_KSTACK_TOP(p)   (((struct full_task_struct *) (p))->stack_top)
#define TSK_COUNT(p)    (((struct full_task_struct *) (p))->count)

struct full_task_struct {
    struct task_struct task;
    atomic_t count;
    unsigned long stack;
    unsigned long stack_top;

struct init_task_struct {
    unsigned long stack[INIT_TASK_SIZE/sizeof(long)];
    struct full_task_struct ftsk;

So, each pointer to a task_struct is really a full_task_struct pointer that can be used to access other fields like task stack base, task stack top and task_struct use count. The stack to task_struct iverse lookup is done by storing the pointer of the stack's owner task_struct at the base of the stack :


struct task_struct *alloc_task_struct(void)
    struct full_task_struct *f = (struct full_task_struct *) kmem_cache_alloc(tsk_cache, GFP_KERNEL);

    if (!f)
        return NULL;
    f->stack = __get_free_pages(GFP_KERNEL, 1);
    if (!f->stack) {
        kmem_cache_free(tsk_cache, f);
        return NULL;
    atomic_set(&f->count, 1);
    *((struct task_struct **) f->stack) = (struct task_struct *) f;
    return (struct task_struct *) f;

The initial stack frame pointer jittering is done by :


#define L2_CACHE_SIZE       (256 * 1024)
#define L2_ASSOCIATIVITY    4
static inline unsigned long get_stack_jitter(struct task_struct *p)

int copy_thread(int nr, unsigned long clone_flags, unsigned long esp,
    unsigned long unused,
    struct task_struct * p, struct pt_regs * regs)
    struct pt_regs * childregs;

    childregs = ((struct pt_regs *) (THREAD_SIZE + TSK_TO_KSTACK(p) - get_stack_jitter(p))) - 1;
    struct_cpy(childregs, regs);
    childregs->eax = 0;
    childregs->esp = esp;

    p->thread.esp = TSK_KSTACK_TOP(p) = (unsigned long) childregs;
    p->thread.esp0 = (unsigned long) (childregs+1);

    p->thread.eip = (unsigned long) ret_from_fork;


    struct_cpy(&p->thread.i387, &current->thread.i387);

    return 0;

By using three stack color bits eight colors will be used for initial stack frame pointer jittering that should be enough for most cache architectures. Care has to be taken in increasing too much STACK_COLOUR_BITS because this can lead to kernel stack overflows ( for example a STACK_COLOUR_BITS set to 4 with a cache line size of 128 bytes like P4 will result in a maximum jitter of 2048 bytes by leaving only 6 Kb for the kernel stack ). The patch is available here :



SiS 96x IRQ router patches

My brand new CPQ Presario 3045US had a new SiS chipset (650) whose IRQ router was not compatible with the code that was inside the kernel. New requests were present inside the PCI configuration space (0x60...0x63) that were used by the USB subsystem. Those patches correctly recognize the new 96x South Bridge and fix the problem.



Enable smart wake ups with wake_up_info()

The current (2.6.0) Linux kernel does not allow the task that wakes up a wait queue, to pass information about the cause of the wake up and this forces the freshly wake up tasks to perform additional steps to query such information. This is time consuming and not efficent. The following patch introduces a new wake up function wake_up_info() that enables the caller to pass additional information to the woke up tasks. The information is passed to the callback function registered inside the wait structure.


Lazy TSS's I/O bitmap update

The following patch implements a lazy TSS's I/O bitmap copy for the i386 and x86-64 architecture. Instead of copying the bitmap at every context switch, the
TSS's I/O bitmap offset is set to an invalid offset, so that an attempt to access the bitmap from the CPU will trigger a GP fault. It is lazily at that stage that the bitmap is updated, by hence avoiding bitmap copies in cases where the switched task do not perfom any I/O operation.