Qnote

public

Concept

linux/concept.md

Concept Flow

Concept flow

1Process descriptor (taskstruct) and the current macro
2File Descriptor, File Object and File Descriptor Table
3Virtual Function Table (VFT)
4Socket, Sock and SKB
5Netlink Socket
6Reference counters
7Task State
8Run Queues

Process descriptor (task_struct) and the current macro

One of the most important structures in the kernel is the struct task_struct, yet not the simplest one.

Every task has a task_struct object living in memory. A userland process is composed of at least one task. In a multi-threaded application, there is one task_struct for every thread. Kernel threads also have their own task_struct (e.g. kworker, migration).

The task_struct holds crucial information like:

// [include/linux/sched.h]

struct task_struct {
    volatile long state;            // process state (running, stopped, ...)
    void *stack;                    // task's stack pointer
    int prio;                       // process priority
    struct mm_struct *mm;           // memory address space
    struct files_struct *files;     // open file information
    const struct cred *cred;        // credentials
  // ...
};

Accessing the current running task is such a common operation that a macro exists to get a pointer on it: current.

File Descriptor, File Object and File Descriptor Table

Everybody knows that "everything is a file", but what does it actually mean?

In the Linux kernel, there are basically seven kinds of files:

Each of them can be represented by a file descriptor. A file descriptor is basically an integer that is only meaningful for a given process. For each file descriptor, there is an associated structure: struct file.

A struct file (or file object) represents a file that has been opened. It does not necessarily match any image on the disk. For instance, think about accessing files in a pseudo-file systems like /proc. While reading a file, the system may need to keep track of the cursor. This is the kind of information stored in a struct file. Pointers to struct file are often named filp (for file pointer).

The most important fields of a struct file are:

// [include/linux/fs.h]

struct file {
    loff_t                            f_pos;            // "cursor" while reading file
    atomic_long_t                     f_count;          // object's reference counter
    const struct file_operations      *f_op;            // virtual function table (VFT) pointer
  void                              *private_data;      // used by file "specialization"
  // ...
};

The mapping which translates a file descriptor into a struct file pointer is called the file descriptor table (fdt). Note that this is not a 1:1 mapping, there could be several file descriptors pointing to the same file object. In that case, the pointed file object has its reference counter increased by one (cf. Reference Counters). The FDT is stored in a structure called: struct fdtable. This is really just an array of struct file pointers that can be indexed with a file descriptor.

// [include/linux/fdtable.h]

struct fdtable {
    unsigned int max_fds;
    struct file ** fd;      /* current fd array */
  // ...
};

What links a file descriptor table to a process is the struct files_struct. The reason why the fdtable is not directly embedded into a task_struct is that it has other information (e.g. close on exec bitmask, ...). A struct files_struct can also be shared between several threads (i.e. task_struct) and there is some optimization tricks as well.

// [include/linux/fdtable.h]

struct files_struct {
    atomic_t count;           // reference counter
    struct fdtable *fdt;      // pointer to the file descriptor table
  // ...
};

A pointer to a files_struct is stored in the task_struct (field files).

Virtual Function Table (VFT)

While being mostly implemented in C, Linux remains an object-oriented kernel.

One way to achieve some genericity is to use a virtual function table (vft). A virtual function table is a structure which is mostly composed of function pointers.

The mostly known VFT is struct file_operations:

// [include/linux/fs.h]

struct file_operations {
    ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
    int (*open) (struct inode *, struct file *);
    int (*release) (struct inode *, struct file *);
  // ...
};

Since everything is a file but not of the same type, they all have different file operations, often called f_ops. Doing so allows the kernel code to handle file independently of their type and code factorization. It leads to such kind of code:

        if (file->f_op->read)
            ret = file->f_op->read(file, buf, count, pos);

Socket, Sock and SKB

A struct socket lives at the top-layer of the network stack. From a file perspective, this is the first level of specialization. During socket creation (socket() syscall), a new struct file is created and its file operation (field f_op) is set to socket_file_ops.

Since every file is represented with a file descriptor, you can use any syscall that takes a file descriptor as argument (e.g. read(), write(), close()) with a socket file descriptor. This is actually the main benefit of "everything is a file" motto. Independently of the socket's type, the kernel will invoke the generic socket file operation:

// [net/socket.c]

static const struct file_operations socket_file_ops = {
    .read = sock_aio_read,      // <---- calls sock->ops->recvmsg()
    .write =    sock_aio_write, // <---- calls sock->ops->sendmsg()
    .llseek =   no_llseek,      // <---- returns an error
  // ...
}

Since struct socket actually implements the BSD socket API (connect(), bind(), accept(), listen(), ...), they embedded a special virtual function table (vft) of type struct proto_ops. Every type of socket (e.g. AF_INET, AF_NETLINK) implements its own proto_ops.

// [include/linux/net.h]

struct proto_ops {
    int     (*bind)    (struct socket *sock, struct sockaddr *myaddr, int sockaddr_len);
    int     (*connect) (struct socket *sock, struct sockaddr *vaddr,  int sockaddr_len, int flags);
    int     (*accept)  (struct socket *sock, struct socket *newsock, int flags);
  // ...
}

When a BSD-style syscall is invoked (e.g. bind()), the kernel generally follows that scheme:

Because some protocol operations (e.g. sending/receiving data) might actually need to go into the lower layer of the network stack, the struct socket has a pointer to a struct sock object. This pointer is generally used by the socket protocol operations (proto_ops). In the end, a struct socket is a kind of glue between a struct file and a struct sock.

// [include/linux/net.h]

struct socket {
    struct file     *file;
    struct sock     *sk;
    const struct proto_ops  *ops;
  // ...
};

The struct sock is a complex data structure. One might see it as a middle-ish thing between the lower layer (network card driver) and higher level (socket). Its main purpose is the ability to hold the receive/send buffers in a generic way.

When a packet is received over the network card, the driver "enqueued" the network packet into the sock receive buffer. It will stay there until a program decides to receive it (recvmsg() syscall). The other way around, when a program wants to send data (sendmsg() syscall), a network packet is "enqueued" onto the sock sending buffer. Once notified, the network card will then "dequeue" that packet and send it.

Those "network packets" are the so-called struct sk_buff (or skb). The receive/send buffers are basically a doubly-linked list of skb:

// [include/linux/sock.h]

struct sock {
    int         sk_rcvbuf;    // theorical "max" size of the receive buffer
    int         sk_sndbuf;    // theorical "max" size of the send buffer
    atomic_t        sk_rmem_alloc;  // "current" size of the receive buffer
    atomic_t        sk_wmem_alloc;  // "current" size of the send buffer
    struct sk_buff_head sk_receive_queue;   // head of doubly-linked list
    struct sk_buff_head sk_write_queue;     // head of doubly-linked list
    struct socket       *sk_socket;
  // ...
}

As we can see, a struct sock references a struct socket (field sk_socket), while a struct socket references a struct sock (field sk). In the very same way, a struct socket references a struct file (field file) while a struct file references a struct socket (field private_data). This "2-way mechanism" allows data to go up-and-down through the network stack.

NOTE: Do not get confused! The struct sock objects are often called sk, while struct socket objects are often called sock.

Netlink socket is a type of socket (i.e. family) just like UNIX or INET sockets.

Netlink socket (AF_NETLINK) allows communication between kernel and user space. It can be used to modify the routing table (NETLINK_ROUTE protocol), to receive SELinux event notifications (NETLINK_SELINUX) and even communicate to other userland process (NETLINK_USERSOCK).

Since struct sock and struct socket are generic data structure supporting all kinds of sockets, it is necessary to somehow "specialize them" at some point.

From the socket perspective, the proto_ops field needs to be defined. For the netlink family (AF_NETLINK), the BSD-style socket operations are netlink_ops:

// [net/netlink/af_netlink.c]

static const struct proto_ops netlink_ops = {
    .bind =     netlink_bind,
    .accept =   sock_no_accept,     // <--- calling accept() on netlink sockets leads to EOPNOTSUPP error
    .sendmsg =  netlink_sendmsg,
    .recvmsg =  netlink_recvmsg,
  // ...
}

It gets a little bit more complicated, from the sock perspective. One might see a struct sock as an abstract class. Hence, a sock needs to be specialized. In the netlink case, this is made with struct netlink_sock:

// [include/net/netlink_sock.h]

struct netlink_sock {
    /* struct sock has to be the first member of netlink_sock */
    struct sock     sk;
    u32         pid;
    u32         dst_pid;
    u32         dst_group;
  // ...
};

In other words, a netlink_sock is a "sock" with some additional attributes (i.e. inheritance).

The top-level comment is of utter importance. It allows the kernel to manipulate a generic struct sock without knowing its precise type. It also brings another benefit, the &netlink_sock.sk and &netlink_sock addresses aliases. Consequently, freeing the pointer &netlink_sock.sk actually frees the whole netlink_sock object. From a language theory perspective, this is how the kernel does type polymorphism whilst the C language does not have any feature for it. The netlink_sock life cycle logic can then be kept in a generic, well tested, code.

Reference counters

In order to conclude this introduction of the kernel core concepts, it is necessary to understand how the Linux kernel handles reference counters.

To reduce memory leaks in the kernel and to prevent use-after-free, most Linux data structures embed a "ref counter". The refcounter itself is represented with an atomic_t type which is basically an integer. The refcounter is only manipulated through atomic operations like:

atomic_inc()
atomic_add()
atomic_dec_and_test() // substract 1 and test if it is equals zero

Because there is no "smart pointer" (or operator overload stuff), the reference counter handling is done manually by the developers. It means that when an object becomes referenced by another object, its refcounter must be explicitly increased. When this reference is dropped, the refcounter must be explicitly decreased. The object is generally freed when its refcounter reaches zero.

NOTE: increasing the refcounter is often called "taking a reference", while decreasing the refcounter is called "dropping/releasing a reference".

However, if at any time, there is an imbalance (e.g. taking one reference and dropping two), there is a risk of memory corruption:

The Linux Kernel has several facilities to handle refcounters (kref, kobject) with a common interface. However, it is not systematically used and the objects we will manipulate here have their own reference counter helpers. In general, taking a reference is mostly made of "_get()" like functions, while dropping reference are "_put()" like functions.

In our case, each object has different helpers names:

struct sock: sock_hold(), sock_put()
struct file: fget(), fput()
struct files_struct: get_files_struct(), put_files_struct()
...

WARNING: it can get even more confusing! For instance, skb_put() actually does not decrease any refcounter, it "pushes" data into the sk buffer! Do not assume anything about what a function does based on its name, check it.

Task State

The running state of a task is stored in the state field of a task_struct. A task is basically in one of those states (there are more):

A "running" task (TASK_RUNNING) is a task that belongs to a run queue. It can either be running on a cpu (right now) or in a near future (if elected by the scheduler).

A "waiting" task is not running on any CPU. It can be woken up with the help of wait queues or signals. The most common state for waiting tasks is TASK_INTERRUPTIBLE (i.e. "sleeping" can be interrupted).

The various task states are defined here:

// [include/linux/sched.h]

#define TASK_RUNNING        0
#define TASK_INTERRUPTIBLE  1
// ... cut (other states) ...

The state field can be manipulated directly or through the __set_current_state() helper which uses the "current" macro:

// [include/linux/sched.h]

#define __set_current_state(state_value)            \
    do { current->state = (state_value); } while (0)

Run Queues

The struct rq (run queue) is one of the most important data structure for the scheduler. Every task that is in a run queue will be executed by a CPU. Every CPU has it own run queue (allowing true multi-tasking). It holds the list of tasks which are "electable" (by the scheduler) to run on a given CPU. It also has statistics used by the scheduler to make "fair" choices, and eventually rebalance the load between each cpu (i.e. cpu migration).

// [kernel/sched.c]

struct rq {
  unsigned long nr_running;   // <----- statistics
  u64 nr_switches;            // <----- statistics
  struct task_struct *curr;   // <----- the current running task on the cpu
  // ...
};

NOTE: With the "Completely Fair Scheduler (CFS)", the way the actual task list is stored is a bit complex but it does not matter here.

To keep it simple, consider that a task moved out of any run queue will not be executed (i.e. there is no CPU to execute it). This is exactly what the deactivate_task() function does. On the contrary, activate_task() does the exact opposite (it moves task into a run queue).

Blocking a task and the schedule() function

When a task wants to transition from a running state to a waiting state it has to do at least two things:

In practice, no one calls deactivate_task() directly. Instead, schedule() is invoked (see below).

The schedule() function is the main function of the scheduler. When schedule() is invoked, the next (running) task must be elected to run on the CPU. That is, the curr field of a run queue must be updated.

However, if schedule() is called while the current task state is not running (i.e. its state is different from zero), and no signals are pending, it will call deactivate_task():

      asmlinkage void __sched schedule(void)
      {
        struct task_struct *prev, *next;
        unsigned long *switch_count;
        struct rq *rq;
        int cpu;

          // ... cut ...

        prev = rq->curr;    // <---- "prev" is the task running on the current CPU

        if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {   // <----- ignore the "preempt" stuff
          if (unlikely(signal_pending_state(prev->state, prev)))
            prev->state = TASK_RUNNING;
          else
            deactivate_task(rq, prev, DEQUEUE_SLEEP);     // <----- task is moved out of run queue
          switch_count = &prev->nvcsw;
        }

        // ... cut (choose the next task) ...
      }

In the end, a task can block by doing the following sequence:

void make_it_block(void)
{
  __set_current_state(TASK_INTERRUPTIBLE);
  schedule();
}

The task will stay blocked until something else wakes it up.

Wait Queues

Waiting for a resource or a special event is very common. For instance, if you run a server, the main thread might be waiting for incoming connections. Unless it is marked as "non blocking", the accept() syscall will block the main thread. That is, the main thread is stuck in kernel land until something else wakes it up.

A wait queue is basically a doubly linked list of processes that are currently blocked (waiting). One might see it as the "opposite" of run queues. The queue itself is represented with wait_queue_head_t:

// [include/linux/wait.h]

typedef struct __wait_queue_head wait_queue_head_t;

struct __wait_queue_head {
    spinlock_t lock;
    struct list_head task_list;
};

NOTE: The struct list_head type is how Linux implements doubly linked list.

Each element of the wait queue has the type wait_queue_t:

// [include/linux.wait.h]

typedef struct __wait_queue wait_queue_t;
typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int flags, void *key);

struct __wait_queue {
    unsigned int flags;
    void *private;                
    wait_queue_func_t func;     // <----- we will get back to this
    struct list_head task_list;
};

A wait queue element can be created with the DECLARE_WAITQUEUE() macro...

// [include/linux/wait.h]

#define __WAITQUEUE_INITIALIZER(name, tsk) {                \
    .private    = tsk,                      \
    .func       = default_wake_function,            \
    .task_list  = { NULL, NULL } }

#define DECLARE_WAITQUEUE(name, tsk)                    \
    wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk) // <----- it creates a variable!

...which is invoked like this:

DECLARE_WAITQUEUE(my_wait_queue_elt, current); // <----- use the "current" macro

Finally, once a wait queue element is declared, it can be queued into a wait queue with the function add_wait_queue(). It basically just adds the element into the doubly linked list with proper locking (do not worry about it for now).

// [kernel/wait.c]

void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    wait->flags &= ~WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&q->lock, flags);
    __add_wait_queue(q, wait);              // <----- here
    spin_unlock_irqrestore(&q->lock, flags);
}

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
    list_add(&new->task_list, &head->task_list);
}

Invoking add_wait_queue() is also called "registering to a wait queue".

Waking up a task

So far, we know that there are two kinds of queues: run queues and wait queues. We saw that blocking a task is all about removing it from a run queue (with deactivate_task()). But how can it transition from the blocked (sleeping) state back to the running state?

NOTE: Blocked task can be woken up through signals (and other means), but this is out-of-topic here.

Since a blocked task is not running anymore, it can't wake up itself. This needs to be done from another task.

Data structures which have the ownership of a particular resource have a wait queue. When a task wants to access this resource but it is not available at the moment, the task can put itself in a sleeping state until woken up by the resource's owner.

In order to be woken up when the resource becomes available, it has to register to the resource's wait queue. As we saw earlier, this "registration" is made with the add_wait_queue() call.

When the resource becomes available, the owner wakes one or more tasks so they can continue their executions. This is done with the __wake_up() function:

// [kernel/sched.c]

/**
 * __wake_up - wake up threads blocked on a waitqueue.
 * @q: the waitqueue
 * @mode: which threads
 * @nr_exclusive: how many wake-one or wake-many threads to wake up
 * @key: is directly passed to the wakeup function
 *
 * It may be assumed that this function implies a write memory barrier before
 * changing the task state if and only if any tasks are woken up.
 */

void __wake_up(wait_queue_head_t *q, unsigned int mode,
            int nr_exclusive, void *key)
{
    unsigned long flags;

    spin_lock_irqsave(&q->lock, flags);
    __wake_up_common(q, mode, nr_exclusive, 0, key);    // <----- here
    spin_unlock_irqrestore(&q->lock, flags);
}
    // [kernel/sched.c]

    static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
          int nr_exclusive, int wake_flags, void *key)
    {
      wait_queue_t *curr, *next;

[0]   list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
        unsigned flags = curr->flags;

[1]     if (curr->func(curr, mode, wake_flags, key) &&
            (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
          break;
      }
    }

This function iterates over every element in the wait queue [0] (list_for_each_entry_safe() is a common macro used with doubly linked list). For each element, it invokes the func() callback [1].

Remember the DECLARE_WAITQUEUE() macro? It sets the func callback to default_wake_function():

// [include/linux/wait.h]

#define __WAITQUEUE_INITIALIZER(name, tsk) {                \
    .private    = tsk,                      \
    .func       = default_wake_function,            \                 // <------
    .task_list  = { NULL, NULL } }

#define DECLARE_WAITQUEUE(name, tsk)                    \
    wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)

In turn, the default_wake_function() just calls try_to_wake_up() using the private field of the wait queue element (which points to the sleeping's task_struct most of the time):

int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
              void *key)
{
    return try_to_wake_up(curr->private, mode, wake_flags);
}

Finally, try_to_wake_up() is kind of the "opposite" of schedule(). While schedule() "schedules-out" the current task, try_to_wake_up() makes it schedulable again. That is, it puts it in a run queue and changes its running state!

static int try_to_wake_up(struct task_struct *p, unsigned int state,
              int wake_flags)
{
    struct rq *rq;

    // ... cut (find the appropriate run queue) ...

out_activate:
    schedstat_inc(p, se.nr_wakeups);              // <----- update some stats
    if (wake_flags & WF_SYNC)
        schedstat_inc(p, se.nr_wakeups_sync);
    if (orig_cpu != cpu)
        schedstat_inc(p, se.nr_wakeups_migrate);
    if (cpu == this_cpu)
        schedstat_inc(p, se.nr_wakeups_local);
    else
        schedstat_inc(p, se.nr_wakeups_remote);
    activate_task(rq, p, en_flags);               // <----- put it back to run queue!
    success = 1;

    p->state = TASK_RUNNING;                      // <----- the state has changed!

    // ... cut ...
}

This is where activate_task() is invoked (there are other places). Because the task is now back in a run queue and its state is TASK_RUNNING, it has a chance of being scheduled. Hence, continue its execution where it was after the call to schedule().

In practice, __wake_up() is rarely called directly. Instead, those helper macros are invoked:

// [include/linux/wait.h]

#define wake_up(x)          __wake_up(x, TASK_NORMAL, 1, NULL)
#define wake_up_nr(x, nr)       __wake_up(x, TASK_NORMAL, nr, NULL)
#define wake_up_all(x)          __wake_up(x, TASK_NORMAL, 0, NULL)

#define wake_up_interruptible(x)    __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
#define wake_up_interruptible_nr(x, nr) __wake_up(x, TASK_INTERRUPTIBLE, nr, NULL)
#define wake_up_interruptible_all(x)    __wake_up(x, TASK_INTERRUPTIBLE, 0, NULL)

A Complete Example

Here is a simple example to summarize the aforementioned concepts:

struct resource_a {
  bool resource_is_ready;
  wait_queue_head_t wq;
};

void task_0_wants_resource_a(struct resource_a *res)
{
  if (!res->resource_is_ready) {
    // "register" to be woken up
    DECLARE_WAITQUEUE(task0_wait_element, current);
    add_wait_queue(&res->wq, &task0_wait_element);

    // start sleeping
    __set_current_state(TASK_INTERRUPTIBLE);
    schedule();

    // We'll restart HERE once woken up
    // Remember to "unregister" from wait queue
  }

  // XXX: ... do something with the resource ...
}

void task_1_makes_resource_available(struct resource_a *res)
{
  res->resource_is_ready = true;
  wake_up_interruptible_all(&res->wq);  // <--- unblock "task 0"
}

One thread runs the task_0_wants_resource_a() function which becomes blocking because the "resource" is not available. At some point, the resource owner makes it available (from another thread) and calls task_1_makes_resource_available(). After this, the execution of task_0_wants_resource_a() can resume.

This is a pattern that you will often see in the Linux Kernel code, you now know what it means. Note that the term "resource" has been used here in a generic way. Tasks can wait for an event, a condition to be true or something else. Every time you see a "blocking" syscall, chances are a wait queue is not that far :-).

Physical Page Management

One of the most critical tasks of any operating system is to manage memory. It has to be fast, secure, stable and minimize fragmentation. Unfortunately, most of these goals are orthogonal (security often implies performance penalty). For efficiency reasons, the physical memory is divided in a fixed-length block of contiguous memory. This block is called a page frame and (generally) has a fixed size of 4096 bytes. It can be retrieved using the PAGE_SIZE macro.

Because the kernel must handle memory, it has kept track of every physical page frames as well as information about them. For instance, it has to know if a particular page frame is free for use or not. This kind of information is stored in a struct page data structure (also called "Page Descriptor").

The kernel can request one or more contiguous pages with alloc_pages() and free them with free_pages(). The allocator responsible to handle those requests is called the Zoned Page Frame Allocator. Since this allocator uses a buddy system algorithm, it is often just called the Buddy Allocator.

Slab Allocators

The granularity offered by the buddy allocator is not suitable for every situation. For instance, if the kernel only wants to allocate 128 bytes of memory, it might ask for a page but then, 3968 bytes of memory will get wasted. This is called internal fragmentation. To overcome this issue, Linux implements more fine-grained allocators: Slab Allocators. To keep it simple, consider that the Slab Allocator is responsible for handling the equivalence of malloc() / free() for the kernel.

The Linux kernel offers three different Slab allocators (only one is used):

NOTE: We will use the following naming convention: Slab is "a" Slab allocator (be it SLAB, SLUB, SLOB). The SLAB (capital) is one of the three allocators. While a slab (lowercase) is an object used by Slab allocators.

We cannot cover every Slab allocator here. Our target uses the SLAB allocator which is well documented. The SLUB seems to be more widespread nowadays and there isn't much documentation but the code itself. Fortunately, (we think that) the SLUB is actually easier to understand. There is no "cache coloring" stuff, it does not track "full slab", there is no internal/external slab management, etc. In order to know which Slab is deployed on your target, read the config file:

$ grep "CONFIG_SL.B=" /boot/config-$(uname -r)

The reallocation part will change depending on the deployed Slab allocator. While being more complex to understand, it is easier to exploit use-after-free on the SLAB than the SLUB. On the other hand, exploiting the SLUB brings another benefit: slab aliasing (i.e. more objects are stored in the "general" kmemcaches).

Cache and slab

Because the kernel tends to allocate object of the same size again and again, it would be inefficient to request/release pages of the same memory area. To prevent this, the Slab allocator stores object of the same size in a cache (a pool of allocated page frames). A cache is described by the struct kmem_cache (also called "cache descriptor"):

struct kmem_cache {
  // ...
    unsigned int        num;              // number of objects per slab
    unsigned int        gfporder;         // logarithm number of contiguous page frames in a slab
    const char          *name;            // name of the cache 
    int                 obj_size;         // object size in this cache
    struct kmem_list3   **nodelists;      // holds list of empty/partial/full slabs
    struct array_cache  *array[NR_CPUS];  // per-cpu cache
};

The objects themselves are stored in slabs. A slab is basically one or more contiguous page frame(s). A single slab can hold num objects of size obj_size. For instance, a slab spanned across a single page (4096 bytes) can holds 4 objects of 1024 bytes.

The status of a single slab (e.g. number of free objects) is described by the struct slab (also called "slab management structure"):

struct slab {
    struct list_head list;
    unsigned long colouroff;
    void *s_mem;                  // virtual address of the first object
    unsigned int inuse;           // number of "used" object in the slab
    kmem_bufctl_t free;           // the use/free status of each objects
    unsigned short nodeid;
};

The slab management structure can be either stored in the slab itself (internal) or in another memory location (external). The rationale behind this is to reduce external fragmentation. Where the slab management structure is stored depends on the object size of the cache. If the object size is smaller than 512 bytes, the slab management structure is stored inside the slab otherwise it is stored externally.

NOTE: Do not worry too much about this internal/external stuff, we are exploiting a use-after-free. On the other hand, if you are exploiting a heap overflow, understanding this would be mandatory.

Retrieving the virtual address of an object in a slab can be done with the s_mem field in combination with offsets. To keep it simple, consider that the first object address is s_mem, the second object is s_mem + obj_size, the third s_mem + 2*obj_size, etc... This is actually more complex because of "colouring" stuff used for hardware cache efficiency, but this is out-of-topic.

Slabs Housekeeping and Buddy interactions

When a new slab is created, the Slab allocator politely asks the Buddy allocator for page frames. Conversely, when a slab is destroyed, it gives its pages back to the Buddy. Of course, the kernel tries to reduce slab creation/destruction for performance reasons.

NOTE: One might wonder why gfporder (struct kmem_cache) is the "logarithm number" of contiguous page frames. The reason is that the Buddy allocator does not work with byte sizes. Instead it works with power-of-two "order". That is, an order of 0 means 1 page, order of 1 means 2 contiguous pages, order of 2 means 4 contiguous pages, etc.

For each cache, the Slab allocator keeps three doubly-linked lists of slabs:

These lists are stored in the cache descriptor (struct kmem_cache) in the nodelists field. Each slab belong to one of these lists. A slab can be moved between them during allocation or free operations (e.g. when allocating the last free object of a partial list, the slab is moved to the full slabs list).

In order to reduce the interactions with the Buddy allocator, the SLAB allocator keeps a pool of several free/partial slabs. When allocating an object, it tries to find a free object from those lists. If every slab is full, the Slab needs to create new slabs by asking more pages to the Buddy. This is known as a cache_grow() operation. Conversely, if the Slab has "too much" free slabs, it destroys some to give pages back to the Buddy.

Per-CPU Array Cache

In the previous section, we've seen than during an allocation, the Slab needs to scan the free or the partial slabs list. Finding a free slot through list scanning is somehow inefficient (e.g. accessing lists require some locking, need to find the offset in the slab, etc.).

In order to boost the performance, the Slab stores an array of pointers to free objects. This array is the struct array_cache data structure and is stored in the array field of a struct kmem_cache.

struct array_cache {
    unsigned int avail;       // number of pointers available AND index to the first free slot
    unsigned int limit;       // maximum number of pointers
    unsigned int batchcount;
    unsigned int touched;
    spinlock_t lock;
    void *entry[];            //  the actual pointers array
};

The array_cache itself is used as a Last-In First-Out (LIFO) data structure (i.e. a stack). This is an awesome property from an exploiter point-of-view! This is the main reason why exploiting use-after-free is easier on SLAB than SLUB.

In the fastest code path, allocating memory is as simple as:

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags) // yes... four "_"
{
    void *objp;
    struct array_cache *ac;

    ac = cpu_cache_get(cachep);

    if (likely(ac->avail)) {
        STATS_INC_ALLOCHIT(cachep);
        ac->touched = 1;
        objp = ac->entry[--ac->avail];        // <-----
  }

  // ... cut ...

  return objp;
}

In the very same way, the fastest free code path is:

static inline void __cache_free(struct kmem_cache *cachep, void *objp)
{
    struct array_cache *ac = cpu_cache_get(cachep);

  // ... cut ...

    if (likely(ac->avail < ac->limit)) {
        STATS_INC_FREEHIT(cachep);
        ac->entry[ac->avail++] = objp;          // <-----
        return;
  }
}

In other words, allocation/free operations have a O(1) complexity in the best scenario case.

WARNING: If the fastest path fails, then the allocation algorithm falls back to a slower solution (scan free/partial slab lists) or even slower (cache grow).

Note that there is one array_cache per cpu. The array cache of the currently running cpu can be retrieved with cpu_cache_get(). Doing so (like any per-cpu variables) allows to reduce locking operations, hence boost the performance.

WARNING: Each object pointer in the array cache might belong to different slabs!

General Purpose and Dedicated Caches

In order to reduce internal fragmentation, the kernel creates several caches with a power-of-two object size (32, 64, 128, ...). It guarantees that the internal fragmentation will always be smaller than 50%. In fact, when the kernel tries to allocate memory of a particular size, it searches the closest upper-bounded cache where the object can fit. For instance, allocating 100 bytes will land into the 128 bytes cache.

In the SLAB, general purpose caches are prefixed with "size-" (e.g. "size-32", "size-64"). In the SLUB, general purpose caches are prefixed with "kmalloc-" (e.g. "kmalloc-32", ...). Since we think the SLUB convention is better, we will always use it even if our target runs with the SLAB.

In order to allocate/free memory from a general purpose cache, the kernel uses kmalloc() and kfree().

Because some objects will be allocated/freed a lot, the kernel creates some special "dedicated" caches. For instance, the struct file object is an object used in lots of places which has its own dedicated cache (filp). By creating a dedicated cache for these objects, it guarantees that the internal fragmentation of those caches will be near zero.

In order to allocate/free memory from a dedicated cache, the kernel uses kmem_cache_alloc() and kmem_cache_free().

In the end, both kmalloc() and kmem_cache_alloc() land in the __cache_alloc() function. Similarly, both kfree() and kmem_cache_free() end in __cache_free().

NOTE: You can see the full list of caches as well as handful information in /proc/slabinfo.

The container_of() Macro

The container_of() macro is used all over the place in the Linux kernel. Sooner or later you will need to understand it. Let's look at the code:

#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

The purpose of container_of() macro is to retrieve the address of a structure from one of its members. It uses two macros:

That is, it takes the current field address and subtracts its offset from the "embedder" structure. Let's take a concrete example:

struct foo {
  unsigned long a;
  unsigned long b;  // offset=8
}

void* get_foo_from_b(unsigned long *ptr)
{
  // "ptr" points to the "b" field of a "struct foo"
  return container_of(ptr, struct foo, b);
}

void bar() {
  struct foo f;
  void *ptr;

  printf("f=%p\n", &f);         // <----- print 0x0000aa00
  printf("&f->b=%p\n", &f->b);  // <----- print 0x0000aa08

  ptr = get_foo_from_b(&f->b);
  printf("ptr=%p\n", ptr);      // <----- print 0x0000aa00, the address of "f"
}

Doubly-Linked Circular List Usage

The Linux kernel makes an extensive use of doubly-linked circular list. It is important to understand them in general AND it is required here to reach our arbitrary call primitive. Instead of just looking at the actual implementation, we will develop a simple example to understand how they are used. By the end of this section, you should be able to understand the list_for_each_entry_safe() macro.

NOTE: To keep this section simple, we will simply use "list" instead of "doubly-linked circular list".

To handle the list, Linux uses a single structure:

struct list_head {
    struct list_head *next, *prev;
};

This is a dual-purpose structure that can be either used to:

A list can be initialized with the INIT_LIST_HEAD function which makes both next and prev field point to the list itself.

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

Let's define a fictional resource_owner structure:

struct resource_owner
{
  char name[16];
  struct list_head consumer_list;
};

void init_resource_owner(struct resource_owner *ro)
{
  strncpy(ro->name, "MYRESOURCE", 16);
  INIT_LIST_HEAD(&ro->consumer_list);
}

To use a list, each element (e.g. consumer) of that list must embed a struct list_head field. For instance:

struct resource_consumer
{
  int id;
  struct list_head list_elt;    // <----- this is NOT a pointer
};

This consumer is added/removed to the list with list_add() and list_del() function respectively. A typical code is:

int add_consumer(struct resource_owner *ro, int id)
{
  struct resource_consumer *rc;

  if ((rc = kmalloc(sizeof(*rc), GFP_KERNEL)) == NULL)
    return -ENOMEM;

  rc->id = id;
  list_add(&rc->list_elt, &ro->consumer_list);

  return 0;
}

Next, we want to release a consumer but we only have a pointer from the list entry (bad design intended). We retrieve the structure with container_of() macro, delete the element from the list and free it:

void release_consumer_by_entry(struct list_head *consumer_entry)
{
  struct resource_consumer *rc;

  // "consumer_entry" points to the "list_elt" field of a "struct resource_consumer"
  rc = container_of(consumer_entry, struct resource_consumer, list_elt);

  list_del(&rc->list_elt);
  kfree(rc);
}

Then, we want to provide a helper to retrieve a resource consumer based on its id. We will need to iterate over the whole list using the list_for_each() macro:

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

As we can see, we need to use the container_of() macro because list_for_each() only gives us a struct list_head pointer (i.e. iterator). This operation is often replaced with the list_entry() macro (which does the exact same thing, but has a better name):

struct resource_consumer* find_consumer_by_id(struct resource_owner *ro, int id)
{
  struct resource_consumer *rc = NULL;
  struct list_head *pos = NULL;

  list_for_each(pos, &ro->consumer_list) {
    rc = list_entry(pos, struct resource_consumer, list_elt);
    if (rc->id == id)
      return rc;
  }

  return NULL; // not found
}

Having to declare a struct list_head variable and using list_entry()/container_of() macros is actually a bit heavy. Because of this, there is the list_for_each_entry() macro (which uses list_first_entry() and list_next_entry() macros):

#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

#define list_next_entry(pos, member) \
    list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_for_each_entry(pos, head, member)              \
    for (pos = list_first_entry(head, typeof(*pos), member);    \
         &pos->member != (head);                    \
         pos = list_next_entry(pos, member))

We can re-write the previous code with a more compact version (without declaring a struct list_head anymore):

struct resource_consumer* find_consumer_by_id(struct resource_owner *ro, int id)
{
  struct resource_consumer *rc = NULL;

  list_for_each_entry(rc, &ro->consumer_list, list_elt) {
    if (rc->id == id)
      return rc;
  }

  return NULL; // not found
}

Next, we want a function that releases every consumer. This raises two problems:

That is, we can't release an element while walking the list. This would lead to use-after-free (they are everywhere...). To address this issue, the list_for_each_safe() has been created. It "prefetches" the next element:

#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

It implies that we will need to declare two struct list_head:

void release_all_consumers(struct resource_owner *ro)
{
  struct list_head *pos, *next;

  list_for_each_safe(pos, next, &ro->consumer_list) {
    release_consumer_by_entry(pos);
  }
}

Finally, we realized that release_consumer_by_entry() was ugly, so we rewrite it using a struct resource_consumer pointer in argument (no more container_of()):

void release_consumer(struct resource_consumer *rc)
{
  if (rc)
  {
    list_del(&rc->list_elt);
    kfree(rc);
  }
}

Because it does not take a struct list_head in argument anymore, our release_all_consumers() function can be rewritten with the list_for_each_entry_safe() macro:

#define list_for_each_entry_safe(pos, n, head, member)          \
    for (pos = list_first_entry(head, typeof(*pos), member),    \
        n = list_next_entry(pos, member);           \
         &pos->member != (head);                    \
         pos = n, n = list_next_entry(n, member))

That is:

void release_all_consumers(struct resource_owner *ro)
{
  struct resource_consumer *rc, *next;

  list_for_each_entry_safe(rc, next, &ro->consumer_list, list_elt) {
    release_consumer(rc);
  }
}

Nice, our code does not use struct list_head variables anymore.

Hopefully, you now understand the list_for_each_entry_safe() macro. If not, read this section again. It is mandatory to understand it because it will be used to reach our arbitrary call primitive in the exploit. We will even look at it in assembly (because of offsets)! Better to understand it now...

The thread_info Structure

Just like the struct task_struct, the struct thread_info structure is very important that one must understand in order to exploit bugs in the Linux kernel.

This structure is architecture dependent. In the x86-64 case, the definition is:

// [arch/x86/include/asm/thread_info.h]

struct thread_info {
    struct task_struct    *task;
    struct exec_domain    *exec_domain;
    __u32                 flags;
    __u32                 status;
    __u32                 cpu;
    int                   preempt_count;
    mm_segment_t          addr_limit;
    struct restart_block  restart_block;
    void __user           *sysenter_return;
#ifdef CONFIG_X86_32
    unsigned long         previous_esp;
    __u8                  supervisor_stack[0];
#endif
    int                   uaccess_err;
};

The most important fields being:

Using Kernel Thread Stack Pointer

In general, if you've got access to a task_struct pointer, you can retrieve lots of other kernel structures by dereferencing pointers from it. For instance, we will use it in our case to find the address of the file descriptor table during kernel reparation.

Since the task field points to the associated task_struct, retrieving current (remember Core Concept #1?) is a simple as:

#define get_current() (current_thread_info()->task)

The problem is: how to get the address of the current thread_info?

Suppose that you have a pointer in the kernel "thread stack", you can retrieve the current thread_info pointer with:

#define THREAD_SIZE (PAGE_SIZE << 2)
#define current_thread_info(ptr) (_ptr & ~(THREAD_SIZE - 1))

struct thread_info *ti = current_thread_info(leaky_stack_ptr);

The reason why this works is because the thread_info lives inside the kernel thread stack (see the "Kernel Stacks" section).

On the other hand, if you have a pointer to a task_struct, you can retrieve the current thread_info with the stack field in task_struct.

That is, if you have one of those pointers, you can retrieve each other structures.

Note that the task_struct's stack field doesn't point to the top of the (kernel thread) stack but to the thread_info!

Escaping Seccomp-Based Sandbox

Containers as well as sandboxed applications seem to be more and more widespread nowadays. Using a kernel exploit is sometimes the only way (or an easiest one) to actually escape them.

The Linux kernel's seccomp is a facility which allows programs to restrict access to syscalls. The syscall can be either fully forbidden (invoking it is impossible) or partially forbidden (parameters are filtered). It is setup using BPF rules (a "program" compiled in the kernel) called seccomp filters.

Once enabled, seccomp filters cannot be disabled by "normal" means. The API enforces it as there is no syscall for it.

When a program using seccomp makes a system call, the kernel checks if the thread_info's flags has one of the _TIF_WORK_SYSCALL_ENTRY flags set (TIF_SECCOMP is one of them). If so, it follows the syscall_trace_enter() path. At the very beginning, the function secure_computing() is called:

long syscall_trace_enter(struct pt_regs *regs)
{
    long ret = 0;

    if (test_thread_flag(TIF_SINGLESTEP))
        regs->flags |= X86_EFLAGS_TF;

    /* do the secure computing check first */
    secure_computing(regs->orig_ax);            // <----- "rax" holds the syscall number

  // ...
}

static inline void secure_computing(int this_syscall)
{
    if (unlikely(test_thread_flag(TIF_SECCOMP)))      // <----- check the flag again
        __secure_computing(this_syscall);
}

We will not explain what is going on with seccomp past this point. Long story short, if the syscall is forbidden, a SIGKILL signal will be delivered to the faulty process.

The important thing is: clearing the TIF_SECCOMP flag of the current running thread (i.e. thread_info) is "enough" to disable seccomp checks.

WARNING: This is only true for the "current" thread, forking/execve'ing from here will "re-enable" seccomp (see task_struct).

Gaining Arbitrary Read/Write

Now let's check the addr_limit field of thread_info.

If you look at various system call implementations, you will see that most of them call copy_from_user() at the very beginning to make a copy from userland data into kernel-land. Failing to do so can lead to time-of-check time-of-use (TOCTOU) bugs (e.g. change userland value after it has been checked).

In the very same way, system call code must call copy_to_user() to copy a result from kernelland into userland data.

long copy_from_user(void *to,   const void __user * from, unsigned long n);
long copy_to_user(void __user *to, const void *from, unsigned long n);

NOTE: The __user macro does nothing, this is just a hint for kernel developers that this data is a pointer to userland memory. In addition, some tools like sparse can benefit from it.

Both copy_from_user() and copy_to_user() are architecture dependent functions. On x86-64 architecture, they are implemented in arch/x86/lib/copy_user_64.S.

NOTE: If you don't like reading assembly code, there is a generic architecture that can be found in include/asm-generic/*. It can help you to figure out what an architecture-dependent function is "supposed to do".

The generic (i.e. not x86-64) code for copy_from_user() looks like this:

// from [include/asm-generic/uaccess.h]

static inline long copy_from_user(void *to,
        const void __user * from, unsigned long n)
{
    might_sleep();
    if (access_ok(VERIFY_READ, from, n))
        return __copy_from_user(to, from, n);
    else
        return n;
}

The "software" access rights checks are performed in access_ok() while __copy_from_user() unconditionally copy n bytes from from to to. In other words, if you see a __copy_from_user() where parameters havn't been checked, there is a serious security vulnerability. Let's get back to the x86-64 architecture.

Prior to executing the actual copy, the parameter marked with __user is checked against the addr_limit value of the current thread_info. If the range (from+n) is below addr_limit, the copy is performed, otherwise copy_from_user() returns a non-null value indicating an error.

The addr_limit value is set and retrieved using the set_fs() and get_fs() macros respectively:

#define get_fs()    (current_thread_info()->addr_limit)
#define set_fs(x)   (current_thread_info()->addr_limit = (x))

For instance, when you do an execve() syscall, the kernel tries to find a proper "binary loader". Assuming the binary is an ELF, the load_elf_binary() function is invoked and it ends by calling the start_thread() function:

      // from [arch/x86/kernel/process_64.c]

      void start_thread(struct pt_regs *regs, unsigned long new_ip, unsigned long new_sp)
      {
        loadsegment(fs, 0);
        loadsegment(es, 0);
        loadsegment(ds, 0);
        load_gs_index(0);
        regs->ip        = new_ip;
        regs->sp        = new_sp;
        percpu_write(old_rsp, new_sp);
        regs->cs        = __USER_CS;
        regs->ss        = __USER_DS;
        regs->flags     = 0x200;
        set_fs(USER_DS);                        // <-----
        /*
         * Free the old FP and other extended state
         */
        free_thread_xstate(current);
      }

The start_thread() function resets the current thread_info's addr_limit value to USER_DS which is defined here:

#define MAKE_MM_SEG(s)  ((mm_segment_t) { (s) })
#define TASK_SIZE_MAX   ((1UL << 47) - PAGE_SIZE)
#define USER_DS     MAKE_MM_SEG(TASK_SIZE_MAX)

That is, a userland address is valid if it is below 0x7ffffffff000 (used to be 0xc0000000 on 32-bits).

As you might already guessed, overwriting the addr_limit value leads to arbitrary read/write primitive. Ideally, we want something that does:

#define KERNEL_DS   MAKE_MM_SEG(-1UL)   // <----- 0xffffffffffffffff
set_fs(KERNEL_DS);

If we achieve to do this, we disable a software protection mechanism. Again, this is "software" only! The hardware protections are still on, accessing kernel memory directly from userland will provoke a page fault that will kill your exploit (SIGSEGV) because the running level is still CPL=3 (see the "page fault" section).

Since, we want read/write kernel memory from userland, we can actually ask the kernel to do it for us through a syscall that calls copy_{to|from}_user() function while providing a kernel pointer in "__user" marked parameter.

Final note about thread_info

As you might notice by the three examples shown here, the thread_info structure is of utter importance in general as well as for exploitation scenarios. We showed that:

Those are just a sample of things you can do with thread_info. This is a small but critical structure.

Virtual Memory Map

In the previous section, we saw that the "highest" valid userland address was:

#define TASK_SIZE_MAX   ((1UL << 47) - PAGE_SIZE) // == 0x00007ffffffff000

One might wonder where does this "47" comes from?

In the early AMD64 architecture, designers thought that addressing 2^64 memory is somehow "too big" and force to add another level of page table (performance hit). For this reason, it has been decided that only the lowest 48-bits of an address should be used to translate a virtual address into a physical address.

However, if the userland address space ranges from 0x0000000000000000 to 0x00007ffffffff000 what will the kernel address space ? The answer is: 0xffff800000000000 to 0xffffffffffffffff.

That is, the bits [48:63] are:

More specifically, AMD imposed that those [48:63] are the same as the 47 bit. Otherwise, an exception is thrown. Addresses respecting this convention are called canonical form addresses. With such model, it is still possible to address 256TB of memory (half for user, half for kernel).

The space between 0x00007ffffffff000 and 0xffff800000000000 are unused memory addresses (also called "non-canonical addresses").

NOTE: The "guard hole" address range is needed by some hypervisor (e.g. Xen).

You can get a more precise virtual memory map in the Linux kernel documentation: Documentation/x86/x86_64/mm.txt.

In the end, when you see an address starting with "0xffff8*" or higher, you can be sure that it is a kernel one.

Kernel Thread Stacks

In Linux (x86-64 architecture), there are two kinds of kernel stacks:

You may want to read the Linux kernel documentation for additional/complementary information: Documentation/x86/x86_64/kernel-stacks.

First, let's describe the thread stacks. When a new thread is created (i.e. a new task_struct), the kernel does a "fork-like" operation by calling copy_process(). The later allocates a new task_struct (remember, there is one task_struct per thread) and copies most of the parent's task_struct into the new one.

However, depending on how the task is created, some resources can be either shared (e.g. memory is shared in a multithreaded application) or "copied" (e.g. the libc's data). In the later case, if the thread modified some data a new separated version is created: this is called copy-on-write (i.e. it impacts only the current thread and not every thread importing the libc).

In other words, a process is never created "from scratch" but starts by being a copy of its parent process (be it init). The "differences" are fixed later on.

Furthermore, there is some thread specific data, one of them being the kernel thread stack. During the creation/duplication process, dup_task_struct() is called very early:

      static struct task_struct *dup_task_struct(struct task_struct *orig)
      {
        struct task_struct *tsk;
        struct thread_info *ti;
        unsigned long *stackend;
        int node = tsk_fork_get_node(orig);
        int err;

        prepare_to_copy(orig);

[0]     tsk = alloc_task_struct_node(node);
        if (!tsk)
          return NULL;

[1]     ti = alloc_thread_info_node(tsk, node);
        if (!ti) {
          free_task_struct(tsk);
          return NULL;
        }

[2]     err = arch_dup_task_struct(tsk, orig);
        if (err)
          goto out;

[3]     tsk->stack = ti;

        // ... cut ...

[4]     setup_thread_stack(tsk, orig);

        // ... cut ...
      }

      #define THREAD_ORDER  2

      #define alloc_thread_info_node(tsk, node)             \
      ({                                    \
        struct page *page = alloc_pages_node(node, THREAD_FLAGS,    \
                     THREAD_ORDER);     \
        struct thread_info *ret = page ? page_address(page) : NULL; \
                        \
        ret;                                \
      })

The previous code does the following:

One might be confused with [1]. The macro alloc_thread_info_node() is supposed to allocate a struct thread_info and yet, it allocates a thread stack. The reason being thread_info structures lives in thread stacks:

#define THREAD_SIZE  (PAGE_SIZE << THREAD_ORDER)

union thread_union {                                // <----- this is an "union"
    struct thread_info thread_info;
    unsigned long stack[THREAD_SIZE/sizeof(long)];  // <----- 16k-bytes
};

Except for the init process, thread_union is not used anymore (on x86-64)

NOTE: The KERNEL_STACK_OFFSET exists for "optimization reasons" (avoid a sub operation in some cases). You can ignore it for now.

The STACK_END_MAGIC is here to mitigate kernel thread stack overflow exploitation. As explained earlier, overwriting thread_info data can lead to nasty things (it also holds function pointers in the restart_block field).

Since thread_info is at the top of this region, you hopefully understand now why, by masking out THREAD_SIZE, you can retrieve the thread_info address from any kernel thread stack pointer.

In the previous diagram, one might notice the kernel_stack pointer. This is a "per-cpu" variable (i.e. one for each cpu) declared here:

// [arch/x86/kernel/cpu/common.c]

DEFINE_PER_CPU(unsigned long, kernel_stack) =
    (unsigned long)&init_thread_union - KERNEL_STACK_OFFSET + THREAD_SIZE;

Initially, kernel_stack points to the init thread stack (i.e. init_thread_union). However, during a Context Switch, this (per-cpu) variable is updated:

#define task_stack_page(task)   ((task)->stack)

__switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
  // ... cut ..

    percpu_write(kernel_stack,
          (unsigned long)task_stack_page(next_p) +
          THREAD_SIZE - KERNEL_STACK_OFFSET);

  // ... cut ..
}

In the end, the current thread_info is retrieved with:

static inline struct thread_info *current_thread_info(void)
{
    struct thread_info *ti;
    ti = (void *)(percpu_read_stable(kernel_stack) +
              KERNEL_STACK_OFFSET - THREAD_SIZE);
    return ti;
}

The kernel_stack pointer is used while entering a system call. It replaces the current (userland) rsp which is restored while exiting system call.

Netlink has a "global" array nl_table of type netlink_table:

// [net/netlink/af_netlink.c]

struct netlink_table {
    struct nl_pid_hash hash;        // <----- we will focus on this
    struct hlist_head mc_list;
    unsigned long *listeners;
    unsigned int nl_nonroot;
    unsigned int groups;
    struct mutex *cb_mutex;
    struct module *module;
    int registered;
};

static struct netlink_table *nl_table;  // <----- the "global" array

The nl_table array is initialized at boot-time with netlink_proto_init():

// [include/linux/netlink.h]

#define NETLINK_ROUTE       0   /* Routing/device hook              */
#define NETLINK_UNUSED      1   /* Unused number                */
#define NETLINK_USERSOCK    2   /* Reserved for user mode socket protocols  */
// ... cut ...
#define MAX_LINKS 32        

// [net/netlink/af_netlink.c]

static int __init netlink_proto_init(void)
{
  // ... cut ...

    nl_table = kcalloc(MAX_LINKS, sizeof(*nl_table), GFP_KERNEL);

  // ... cut ...
}

In other words, there is one netlink_table per protocol (NETLINK_USERSOCK being one of them). Furthermore, each of those netlink tables embedded a hash field of type struct nl_pid_hash:

// [net/netlink/af_netlink.c]

struct nl_pid_hash {
    struct hlist_head *table;
    unsigned long rehash_time;

    unsigned int mask;
    unsigned int shift;

    unsigned int entries;
    unsigned int max_shift;

    u32 rnd;
};

This structure is used to manipulate a netlink hash table. To that means the following fields are used:

Linux Hash Table API

The hash table itself is manipulated with other typical Linux data structures: struct hlist_head and struct hlist_node. Unlike struct list_head (cf. "Core Concept #3") which just uses the same type to represent either the list head and the elements, the hash list uses two types defined here:

// [include/linux/list.h]

/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).       // <----- this
 */

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev; // <----- note the "pprev" type (pointer of pointer)
};

So, the hash table is composed of one or multiple buckets. Each element in a given bucket is in a non-circular doubly linked list. It means:

The bucket itself is represented with a hlist_head which has a single pointer. In other words, we can't access the tail from a bucket's head. We need to walk the whole list (cf. the commentary).

Understanding Page Fault Trace

Let's analyze the previous trace. This kind of trace comes from a page fault exception. That is, an exception generated by the CPU itself (i.e. hardware) while trying to access memory.

Under "normal" circumstances, a page fault exception can occur when:

While being an "exception" CPU-wise, this actually occurs quite often during normal program life cycle. For instance, when you allocate memory with mmap(), the kernel does not allocate physical memory until you access it the very first time. This is called Demand Paging. This first access provokes a page fault, and it is the page fault exception handler that actually allocates a page frame. That's why you can virtually allocate more memory than the actual physical RAM (until you access it).

As we can see, if an illegal access occurs while being in Kernel Land, it can crash the kernel. This is where we are right now.

[  124.962677] BUG: unable to handle kernel paging request at 00000000004014c4
[  124.962923] IP: [<00000000004014c4>] 0x4014c4
[  124.963039] PGD 1e3df067 PUD 1abb6067 PMD 1b1e6067 PTE 111e3025
[  124.963261] Oops: 0011 [#1] SMP 
...
[  124.979369] CR2: 00000000004014c4

The previous trace has a lot of information explaining the reason of the page fault exception. The CR2 register (same as IP here) holds the faulty address.

In our case, the MMU (hardware) failed to access memory address 0x00000000004014c4 (the payload() address). Because IP also points to it, we know that an exception is generated while trying to execute the curr->func() instruction in __wake_up_common():

First, let's focus on the error code which is "0x11" in our case. The error code is a 64-bit value where the following bits can be set/clear:

// [arch/x86/mm/fault.c]

/*
 * Page fault error code bits:
 *
 *   bit 0 ==    0: no page found   1: protection fault
 *   bit 1 ==    0: read access     1: write access
 *   bit 2 ==    0: kernel-mode access  1: user-mode access
 *   bit 3 ==               1: use of reserved bit detected
 *   bit 4 ==               1: fault was an instruction fetch
 */
enum x86_pf_error_code {

    PF_PROT     =       1 << 0,
    PF_WRITE    =       1 << 1,
    PF_USER     =       1 << 2,
    PF_RSVD     =       1 << 3,
    PF_INSTR    =       1 << 4,
};

That is, our error_code is:

((PF_PROT | PF_INSTR) & ~PF_WRITE) & ~PF_USER

In other words, the page fault occurs:

Since the page where the faulty address belongs is present (PF_PROT is set), a Page Table Entry (PTE) exists. The later describes two things:

In our case, the PTE value is 0x111e3025:

[  124.963039] PGD 1e3df067 PUD 1abb6067 PMD 1b1e6067 PTE 111e3025

If we mask out the PFN part of this value, we get 0b100101 (0x25). Let's code a basic program to extract information from the PTE's flags value:

#include <stdio.h>

#define __PHYSICAL_MASK_SHIFT 46
#define __PHYSICAL_MASK ((1ULL << __PHYSICAL_MASK_SHIFT) - 1)
#define PAGE_SIZE 4096ULL
#define PAGE_MASK (~(PAGE_SIZE - 1))
#define PHYSICAL_PAGE_MASK (((signed long)PAGE_MASK) & __PHYSICAL_MASK)
#define PTE_FLAGS_MASK (~PHYSICAL_PAGE_MASK)

int main(void)
{
  unsigned long long pte = 0x111e3025;
  unsigned long long pte_flags = pte & PTE_FLAGS_MASK;

  printf("PTE_FLAGS_MASK  = 0x%llx\n", PTE_FLAGS_MASK);
  printf("pte             = 0x%llx\n", pte);
  printf("pte_flags       = 0x%llx\n\n", pte_flags);

  printf("present   = %d\n", !!(pte_flags & (1 << 0)));
  printf("writable  = %d\n", !!(pte_flags & (1 << 1)));
  printf("user      = %d\n", !!(pte_flags & (1 << 2)));
  printf("acccessed = %d\n", !!(pte_flags & (1 << 5)));
  printf("NX        = %d\n", !!(pte_flags & (1ULL << 63)));

  return 0;
}

NOTE: If you wonder where all those constants come from, search for the PTE_FLAGS_MASK and _PAGE_BIT_USER macros in arch/x86/include/asm/pgtable_types.h. It simply matches the Intel documentation (Table 4-19).

This program gives:

PTE_FLAGS_MASK  = 0xffffc00000000fff
pte             = 0x111e3025
pte_flags       = 0x25

present   = 1
writable  = 0
user      = 1
acccessed = 1
NX        = 0

Let's match this information with the previous error code:

The page is user accessible which means, the kernel can also access it

So, what's wrong?

In the previous list, the point 4) is partially true. The kernel has the right to access User Mode pages but it cannot execute it! The reason being:

Supervisor Mode Execution Prevention (SMEP).

Prior to SMEP introduction, the kernel had all rights to do anything with userland pages. In Supervisor Mode (i.e. Kernel Mode), the kernel was allowed to both read/write/execute userland AND kernel pages. This is not true anymore!

SMEP exists since the "Ivy Bridge" Intel Microarchitecture (core i7, core i5, etc.) and the Linux kernel supports it since this patch. It adds a security mechanism that is enforced in hardware.

Let's look at the section "4.6.1 - Determination of Access Rights" from Intel System Programming Guide Volume 3a which gives the complete sequence performed while checking if accessing a memory location is allowed or not. If not, a page fault exception is generated.

Since the fault occurs during the setsockopt() system call, we are in supervisor-mode:

The following items detail how paging determines access rights:

• For supervisor-mode accesses:
  ... cut ...
  — Instruction fetches from user-mode addresses.
    Access rights depend on the values of CR4.SMEP:
    • If CR4.SMEP = 0, access rights depend on the paging mode and the value of IA32_EFER.NXE:
      ... cut ...
    • If CR4.SMEP = 1, instructions may not be fetched from any user-mode address.

Let's check the status of the CR4 register. The bit in CR4 which represents the SMEP status is the bit 20:

In Linux, the following macro is used:

// [arch/x86/include/asm/processor-flags.h]

#define X86_CR4_SMEP    0x00100000 /* enable SMEP support */

Hence:

CR4 = 0x00000000001407f0
                  ^
                  +------ SMEP is enabled

That's it! SMEP just does its job denying us to return into userland code from kernel land.

Fortunately, SMAP (Supervisor Mode Access Protection), which forbids access to userland page from Kernel Mode, is disabled. It would force us to use another exploitation strategy (i.e. can't use a wait queue element in userland).

WARNING: Some virtualization software (like Virtual Box) does not support SMEP. We don't know if it supports it at the time of writing. If the SMEP flag is not enabled in your lab, you might consider using another virtualization software (hint: vmware supports it).

In this section, we analyzed in deeper detail what information can be extracted from a page fault trace. It is important to understand it as we might need to explore it again later on (e.g. prefaulting). In addition, we understood why the exception was generated because of SMEP and how to detect it. Don't worry, like any security protection mechanism, there is a workaround :-).