Kernel Synchronization – Part 1

With the previous chapter and the one preceding it (Chapters 11 and 10, respectively), you learned a good deal about CPU (or task) scheduling on the Linux OS. In this chapter and the following one, we shall dive into the – at times necessarily complex – topic of kernel synchronization.

As any developer familiar with programming in a multithreaded environment is well aware, there is a need for synchronization whenever two or more threads (code paths in general) may work upon a shared writable data item. Without synchronization (or mutual exclusion) in accessing the shared data, they can race; that is, the outcome cannot be predicted. This is called a data race. (In fact, data races can even occur when multiple single-threaded processes work on any kind of shared memory object, or where interrupts are a possibility.) Pure code itself is never an issue as its permissions are read+execute (r-x); reading and executing code simultaneously...

Technical requirements

I assume you have gone through Online Chapter, Kernel Workspace Setup, and have appropriately prepared a guest Virtual Machine (VM) running Ubuntu 22.04 LTS (or a later stable release, or a recent Fedora distro) and installed all the required packages. If not, I highly recommend you do this first.

To get the most out of this book, I strongly recommend you first set up the workspace environment, including cloning this book’s GitHub repository for the code, and work on it in a hands-on fashion. The repository can be found here: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E.

In this and the following chapter, we refer to small (and simple) device driver examples now and then. If you’re not familiar with the basic Linux driver concepts, though not a required prerequisite, may I again suggest the Linux Kernel Programming – Part 2 – Char Device Drivers and Kernel Synchronization book; this is explained in the first...

Critical sections, exclusive execution, and atomicity

Imagine you’re writing software for a multicore system (well, nowadays, it’s typical that you will work on multicore systems, even on most embedded projects). As we mentioned in the introduction, running multiple code paths in parallel is not only safe but also desirable (why spend those dollars otherwise, right?). On the other hand, concurrent (parallel and simultaneous) code paths within which shared writable data (also known as shared state) is accessed in any manner is where you are required to guarantee that, at any given point in time, only one thread can work on that data at a time! This is key. Why? Think about it: if you allow multiple concurrent code paths to work in parallel on shared writable data, you’re asking for trouble: data corruption (a “data race”) can occur as a result. The following section, after covering some key points, will clearly illustrate the data race concept with...

Concurrency concerns within the Linux kernel

Recognizing critical sections within a piece of kernel code is of critical importance; how can you protect it if you can’t even see it? The following are a few guidelines to help you, as a budding kernel/driver developer, recognize where concurrency concerns – and thus critical sections – may arise:

• The presence of Symmetric Multi-Processor (SMP) systems (CONFIG_SMP=y)
• The presence of a preemptible kernel (CONFIG_PREEMPTION=y)
• Blocking I/O
• Hardware interrupts (on both SMP and/or UP systems)

These are critical points to understand, and we will discuss each in this section.

Multicore SMP systems and data races

This first point is pretty obvious; take a look at the pseudocode shown in Figure 12.6:

Figure 12.6: Pseudocode – a critical section (time t2 to t3) within a (fictional) driver’s read method; it’s potentially buggy as there’s no locking...

Mutex or spinlock? Which to use when

The exact semantics of learning to use the mutex lock and the spinlock are quite simple (with appropriate abstraction within the kernel API set making it even easier for the typical driver developer or module author). The critical question in this situation is a conceptual one: what really is the difference between these two lock types? More to the point, under which circumstances should you use which lock? You will learn the answers to these questions in this section.

Taking our previous driver read method’s pseudocode (Figure 12.6) as a base example, let’s say that three threads – tA, tB, and tC – are running in parallel (on an SMP system) through this code. We shall solve this concurrency issue, while avoiding any data races, by taking (acquiring) a lock prior to the start of the critical section (time t2), and releasing the lock (unlock) just after the end of the critical section code path (time t3). Let’...

Using the mutex lock

Mutexes are also called sleepable or blocking mutual exclusion (mutex) locks. As you have learned, they are used in process context if the critical section can sleep (block). They must not be used within any kind of atomic or interrupt context (top halves, bottom halves such as tasklets or softirqs, and so on), kernel timers, or in process context where blocking is not allowed.

Initializing the mutex lock

Prior to usage, every lock must be initialized to the “unlocked” state. A mutex lock “object” is represented in the kernel as a struct mutex data structure. Consider the following code:

#include <linux/mutex.h>
struct mutex mymtx;

To use this mutex lock, it must be explicitly initialized to the unlocked state. Initialization can be performed statically (declare and initialize the object) with the DEFINE_MUTEX() macro, or dynamically via the mutex_init() function (this is actually a macro wrapper over the __mutex_init...

Using the spinlock

In the Determining which lock to use – in practice section, you learned – practically speaking – when to use the spinlock instead of the mutex lock and vice versa. For convenience, we have reproduced the key statements we provided previously here:

• Is the critical section running in an atomic (for example, interrupt) context, or in process context where it cannot sleep? Use the spinlock.
• Is the critical section running in process context and is sleep or blocking I/O in the critical section possible? Use the mutex lock.

In this section, we shall consider that you’ve now decided to use the spinlock.

Spinlock – simple usage

For all the spinlock APIs, you must include the relevant header file, that is, #include <linux/spinlock.h>.

Similar to the mutex lock, you must declare and initialize the spinlock to the unlocked state before use. The spinlock is an “object” that’s...

Locking and interrupts

So far, we have learned how to use the mutex lock and, for the spinlock, the basic spin_[un]lock() APIs. A few other API variations on the spinlock exist, and we shall examine the more common ones here.

In this section, there’s a bit more advanced coverage, and it will definitely help if you understand at least the basics of writing a (char) device driver and hardware interrupt handling on Linux (typically in the device driver context). These topics are covered in depth in this book’s companion volume Linux Kernel Programming - Part 2, in Chapter 1, Writing a Simple misc Character Device Driver and Chapter 4, Handling Hardware Interrupts (the LKP-2 e-book is freely downloadable). Also, as a quick guide/refresher, we have provided a sub section titled: Interrupt handling on Linux - a summary of key points, that comes later in this section. (If you’re unfamiliar with interrupt handling concepts on Linux, we suggest you first take...

Locking – common mistakes and guidelines

To wrap up, a quick reference or summary, if you will, covering the typical common mistakes made when locking, and (with some repetition), locking guidelines. (Note that some of the techniques mentioned here – like lock-free programming – are covered in the following chapter).

Common mistakes

• Not recognizing critical sections:
  • “Simple” increments/decrements (of the i ++ or i -- type): As we learned in the A classic case – the global i ++ section, these too can be critical sections. In the following chapter, we show optimized and atomic ways to work with them.
  • “Hey, I’m only reading the shared data”: It’s still a critical section if the two conditions for one are met; not protecting it can result in a dirty or torn read, inconsistent or corrupted data.
  • Deadlock: A situation where forward progress is impossible; carefully design...

Solutions

These small exercises were mentioned in the What is a critical section? section.

Solution to Exercise 2. Again, ask yourself, what exactly constitutes a critical section? It’s when the code path in question both can possibly execute in parallel and works upon shared writable data. So, now, does the code in question (the lines between t1 and t2) fulfill these two pre-conditions? Well, it can run in parallel (as explicitly stated), and it does work on shared writable data (the mydrv variable is shared, as it’s a global variable, thus each and every thread within this code path will work upon that very same memory item in parallel).

So, the answer here is clearly yes, it is indeed a critical section. In other words, it should not be allowed to run without some kind of explicit protection.

Solution to Exercise 3. This one’s interesting; the second condition – does it work upon shared writable data? – is true, but the first condition...

Summary

Congratulations on completing this chapter!

Understanding concurrency and its related concerns is absolutely critical for any software professional. In this chapter, you learned key concepts regarding critical sections, the need for exclusive execution within them, and what atomicity and data races really mean. You then learned why we need to be concerned with concurrency while writing code for the Linux OS. After that, we delved into two very common locking technologies that are heavily used in the kernel – mutex locks and spinlocks – in detail. You also learned how to decide which lock to use when. Finally, and again, importantly, learning how to handle concurrency concerns when hardware interrupts (and their possible bottom halves) are in play was covered.

But we aren’t done with kernel concurrency yet! There are many more concepts and technologies we need to learn about, which is just what we will do in the next, and final, chapter of this...

Questions

As we conclude, here is a list of questions for you to test your knowledge regarding this chapter’s material: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E/blob/main/questions/ch12_qs_assignments.txt. You will find some of the questions answered in the book’s GitHub repo: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E/tree/main/solutions_to_assgn.

Further reading

To help you delve deeper into the subject with useful materials, we provide a rather detailed list of online references and links (and, at times, even books) in a Further reading document in this book’s GitHub repository. The Further reading document is available here: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E/blob/main/Further_Reading.md.

Leave a review!

Enjoying this book? Help readers like you by leaving an Amazon review. Scan the QR code below for a 20% discount code.

*Limited Offer