Semaphores Part 1

Sempahores is one of the dark arts of the xkrn1; and as such, I will go over the semaphore and spinlocks, in detail over a few tutorials.

Spinlocks are the at the core of locking primitives. Sempahores are implemented in terms of spinlocks, and even further, spinlocks are implemented in terms of a "raw" lock. Let's look at the definition of a raw lock:

typedef struct raw_spinlock {
unsigned int slock;
} raw_spinlock_t

Currently, the xkrn1 uses the ticket algorithm. It uses 16-bits to represent the datastructure. Bits 0-7 are called the "owner"; bits 8-15 are called the "waiting" bits. When owner == waiting, it will mean that the current thread holds the lock.

A spinlock structure contains a spinlock and miscellaneous data for housekeeping and status information:

typedef struct {
raw_spinlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
unsigned int break_lock;
#endif
#ifdef CONFIG_DEBUG_SPINLOCK
unsigned int magic, owner_cpu;
void *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
} spinlock_t

We will look at struct lockdep_map in the next article; however, it will be very important and is very complex.

But the structure for the semaphore is as follows:

struct semaphore {
spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};

Therefore, we see that the semaphore is composed of the spinock, the count, as well as the wait_list. The wait_list uses the technique described in previous articles, the list_head structure. Therefore, we can get to the containing struct seamphore if we have a reference to the wait_list.

Basically, the spinlock is dependent upon the raw_spinlock_t.
The _raw_spin_lock, calls __ticket_spin_lock, looks likes this:

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
short inc = 0x0100;

asm volatile (
LOCK_PREFIX "xaddw %w0, %1\n"
"1:\t"
"cmpb %h0, %b0\n\t"
"je 2f\n\t"
"rep ; nop\n\t"
"movb %1, %b0\n\t"
"jmp 1b\n"
"2:"
: "+Q" (inc), "+m" (lock->slock)
:
: "memory", "cc");
}

In summary, a semaphore is composed of a spinlock, which will get checked from assembler code via _raw_spin_lock, i.e. __ticket_spin_lock. The ticketing algorithm can be seen in many articles online; however, we will go over the algorithm in the reference articles, detailed later this month.

In the next article, we will go over the semaphore's interface of _raw_spin_lock, namely, spin_lock_irq.