Introduction to spinlocks

PreviousSynchronization primitives NextQueued spinlocks

Last updated 4 years ago

Was this helpful?

Introduction to spinlocks

Introduction

This part opens a new chapter in the book. Timers and time management related stuff was described in the previous . Now it's time to move on to the next topic. As you probably recognized from the title, this chapter will describe the primitives in the Linux kernel.

As always, we will try to know what a synchronization primitive in general is before we deal with any synchronization-related issues. Actually, a synchronization primitive is a software mechanism, that ensures that two or more processes or threads are not running simultaneously on the same code segment. For example, let's look at the following piece of code:

mutex_lock(&clocksource_mutex);
...
...
...
clocksource_enqueue(cs);
clocksource_enqueue_watchdog(cs);
clocksource_select();
...
...
...
mutex_unlock(&clocksource_mutex);

from the source code file. This code is from the __clocksource_register_scale function which adds the given to the clock sources list. This function produces different operations on a list with registered clock sources. For example, the clocksource_enqueue function adds the given clock source to the list with registered clocksources - clocksource_list. Note that these lines of code wrapped to two functions: mutex_lock and mutex_unlock which takes one parameter - the clocksource_mutex in our case.

These functions represent locking and unlocking based on synchronization primitive. As mutex_lock will be executed, it allows us to prevent the situation when two or more threads will execute this code while the mutex_unlock will not be executed by process-owner of the mutex. In other words, we prevent parallel operations on a clocksource_list. Why do we need mutex here? What if two parallel processes will try to register a clock source. As we already know, the clocksource_enqueue function adds the given clock source to the clocksource_list list right after a clock source in the list which has the biggest rating (a registered clock source which has the highest frequency in the system):

static void clocksource_enqueue(struct clocksource *cs)
{
    struct list_head *entry = &clocksource_list;
    struct clocksource *tmp;

    list_for_each_entry(tmp, &clocksource_list, list) {
        if (tmp->rating < cs->rating)
            break;
        entry = &tmp->list;
    }
    list_add(&cs->list, entry);
}

mutex;
semaphores;
seqlocks;
atomic operations;
etc.

We will start this chapter from the spinlock.

Spinlocks in the Linux kernel.

The spinlock is a low-level synchronization mechanism which in simple words, represents a variable which can be in two states:

acquired;
released.

typedef struct spinlock {
        union {
              struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
                struct {
                        u8 __padding[LOCK_PADSIZE];
                        struct lockdep_map dep_map;
                };
#endif
        };
} spinlock_t;

typedef struct spinlock {
        union {
              struct raw_spinlock rlock;
        };
} spinlock_t;

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

typedef struct qspinlock {
        union {
        atomic_t val;
        struct {
            u8    locked;
            u8    pending;
        };
        struct {
            u16    locked_pending;
            u16    tail;
        };
        };
} arch_spinlock_t;

We will not stop on this structures for now. Let's look at the operations on a spinlock. The Linux kernel provides following main operations on a spinlock:

spin_lock_init - produces initialization of the given spinlock;
spin_lock - acquires given spinlock;
spin_lock_irqsave and spin_lock_irq - disable interrupts on local processor, preserve/not preserve previous interrupt state in the flags and acquire given spinlock;
spin_unlock - releases given spinlock;
spin_unlock_bh - releases given spinlock and enables software interrupts;
spin_is_locked - returns the state of the given spinlock;
and etc.

#define spin_lock_init(_lock)            \
do {                        \
    spinlock_check(_lock);                \
    raw_spin_lock_init(&(_lock)->rlock);    \
} while (0)

As we may see, the spin_lock_init macro takes a spinlock and executes two operations: check the given spinlock and execute the raw_spin_lock_init. The implementation of the spinlock_check is pretty easy, this function just returns the raw_spinlock_t of the given spinlock to be sure that we got exactly normal raw spinlock:

static __always_inline raw_spinlock_t *spinlock_check(spinlock_t *lock)
{
    return &lock->rlock;
}

The raw_spin_lock_init macro:

# define raw_spin_lock_init(lock)        \
do {                        \
    *(lock) = __RAW_SPIN_LOCK_UNLOCKED(lock);    \
} while (0)                    \

#define __RAW_SPIN_LOCK_UNLOCKED(lockname)      \
         (raw_spinlock_t) __RAW_SPIN_LOCK_INITIALIZER(lockname)

#define __RAW_SPIN_LOCK_INITIALIZER(lockname)            \
         {                                                      \
             .raw_lock = __ARCH_SPIN_LOCK_UNLOCKED,             \
             SPIN_DEBUG_INIT(lockname)                          \
             SPIN_DEP_MAP_INIT(lockname)                        \
         }

As I already wrote above, we will not consider stuff which is related to debugging of synchronization primitives. In this case we will not consider the SPIN_DEBUG_INIT and the SPIN_DEP_MAP_INIT macros. So the __RAW_SPINLOCK_UNLOCKED macro will be expanded to the:

*(&(_lock)->rlock) = __ARCH_SPIN_LOCK_UNLOCKED;

where the __ARCH_SPIN_LOCK_UNLOCKED is:

#define __ARCH_SPIN_LOCK_UNLOCKED       { { .val = ATOMIC_INIT(0) } }

static __always_inline void spin_lock(spinlock_t *lock)
{
    raw_spin_lock(&lock->rlock);
}

function which allows us to acquire a spinlock. The raw_spin_lock macro is defined in the same header file and expands to the call of _raw_spin_lock:

#define raw_spin_lock(lock)    _raw_spin_lock(lock)

#define _raw_spin_lock(lock)    __LOCK(lock)

#define _raw_spin_lock(lock) __raw_spin_lock(lock)

void __lockfunc _raw_spin_lock(raw_spinlock_t *lock)
{
    __raw_spin_lock(lock);
}

Here we will consider the latter form of _raw_spin_lock. The __raw_spin_lock function looks:

static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
        preempt_disable();
        spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
        LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
        ...
        ...
        ...
        preempt_enable();
}

We need to do this to prevent the process from other processes to preempt it while it is spinning on a lock. The spin_acquire macro which through a chain of other macros expands to the call of the:

#define spin_acquire(l, s, t, i)                lock_acquire_exclusive(l, s, t, NULL, i)
#define lock_acquire_exclusive(l, s, t, n, i)           lock_acquire(l, s, t, 0, 1, n, i)

The lock_acquire function:

void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
                  int trylock, int read, int check,
                  struct lockdep_map *nest_lock, unsigned long ip)
{
         unsigned long flags;

         if (unlikely(current->lockdep_recursion))
                return;

         raw_local_irq_save(flags);
         check_flags(flags);

         current->lockdep_recursion = 1;
         trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
         __lock_acquire(lock, subclass, trylock, read, check,
                        irqs_disabled_flags(flags), nest_lock, ip, 0, 0);
         current->lockdep_recursion = 0;
         raw_local_irq_restore(flags);
}

LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);

#define LOCK_CONTENDED(_lock, try, lock) \
         lock(_lock)

static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock)
{
        __acquire(lock);
         arch_spin_lock(&lock->raw_lock);
}

#define arch_spin_lock(l)               queued_spin_lock(l)

We stop here for this part. In the next part, we'll dive into how queued spinlocks works and related concepts.

Conclusion

This concludes the first part covering synchronization primitives in the Linux kernel. In this part, we met first synchronization primitive spinlock provided by the Linux kernel. In the next part we will continue to dive into this interesting theme and will see other synchronization related stuff.

Links

PreviousSynchronization primitives NextQueued spinlocks

Last updated 4 years ago

Was this helpful?