Kernel Memory Allocation for Module Authors – Part 1

In the previous two chapters, one on the kernel’s internal aspects and architecture and the other on the essentials of memory management internals, we covered key aspects that serve to provide the required background information for this and the following chapter. In this and the next chapter, we will get down to the actual allocation and freeing of kernel memory by various means. We will demonstrate this via kernel modules that you can test and tweak, elaborate on the whys and hows of allocation, and provide many real-world tips and tricks to enable a kernel or driver developer like you to gain maximum efficiency when working with memory within your kernel module.

In this chapter, we will cover the kernel’s two primary memory allocators – the Page Allocator (PA) (aka the Buddy System Allocator (BSA)) and the slab allocator. We will delve into the nitty-gritty of working with their APIs within kernel...

Technical requirements

I assume that 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) and installed all the required packages. If not, I highly recommend you to do this first.

To get the most out of this book, I strongly recommend first setting up the workspace environment, including cloning this book’s GitHub repository (https://github.com/PacktPublishing/Linux-Kernel-Programming_2E) for the code, and working on it in a hands-on fashion.

The topics covered here assume you have at least basic familiarity with the process Virtual Address Space (VAS) and virtual memory basics (including physical memory layout concepts like UMA and NUMA); we covered these areas in Chapter 6, Kernel Internals Essentials – Processes and Threads, and Chapter 7, Memory Management Internals – Essentials. Ensuring you understand them before going into the...

Introducing kernel memory allocators

Dynamically allocating, and subsequently freeing, kernel memory – both physical and virtual – is the key topic area here. The Linux kernel, like any other OS, requires a sturdy algorithm and implementation to perform this really key task. The primary (de)allocator engine in the Linux OS is referred to as the PA, or the BSA. Internally, it uses a so-called buddy system algorithm to efficiently organize and parcel out free chunks of system RAM. You will find more on the algorithm in the Understanding and using the kernel page allocator (or BSA) section of this chapter.

In this chapter and throughout this book, when we use the notation (de)allocate, please read it as both words: allocate and deallocate.

Of course, being imperfect, the page allocator is not the only or always the best way to obtain and subsequently release system memory. Other technologies exist within the Linux kernel to do so. High on the list of...

Understanding and using the kernel page allocator (or BSA)

In this section, you will learn about two aspects of the Linux kernel’s primary (de)allocator engine, the page allocator (or BSA):

• First, we will cover the fundamentals of the algorithm behind this software (called the “buddy system”).
• Secondly, we will cover the actual and practical usage of the APIs it exposes to the kernel or driver developer.

Understanding the basics of the algorithm behind the page allocator is important. You will then be able to understand the pros and cons of it, and thus, when and which APIs to use in which situation. Let’s begin with its inner workings. Again, remember that the scope of this book with regard to the internal memory management details is limited. We shall cover it to a depth deemed sufficient for a typical module/driver author and no more.

The fundamental workings of the page allocator

We will break up this discussion into...

Understanding and using the kernel slab allocator

As seen in the first section of this chapter, Introducing kernel memory allocators, the slab allocator or slab cache is layered above the page allocator (or BSA; refer back to Figure 8.1). The slab allocator justifies its very existence with two primary ideas or purposes:

• Object caching: Here, it serves as a cache of common “objects”; these are the frequently allocated data structures within the Linux kernel. This idea – which we’ll of course expand upon – has the slab cache allocate (and subsequently freeing) these objects on demand, resulting in higher performance.
• Mitigate the high wastage (internal fragmentation) of the page allocator by providing small, conveniently sized caches, of various sizes that are typically fragments of a page.

Let’s now examine these ideas in a more detailed manner.

The object caching idea

Okay, we begin with the first of these...

Size limitations of the kmalloc API

One of the key advantages of both the page and slab allocators is that the memory chunk they provide upon allocation is not only virtually contiguous (obviously) but is also guaranteed to be physically contiguous memory. Now that is a big deal and will certainly help performance.

But (there’s always a but, isn’t there!), precisely because of this guarantee, it becomes impossible to serve up any given large (memory) size when performing an allocation. In other words, there must be a limit to the amount of memory you can obtain from the slab allocator with a single call to our dear k{m|z}alloc() APIs. What is the limit? (This is indeed a really frequently asked question).

Firstly, you should understand that, technically, this limit is determined by two factors:

• One, the system page size (determined by the PAGE_SIZE macro).
• Two, the number of “orders” (determined by the MAX_ORDER macro); that is...

Slab allocator – a few additional details

A few more key points remain to be explored. First, we’ll divulge some information on using the kernel’s resource-managed versions of the memory allocator APIs, followed by a few additionally available slab helper routines within the kernel, and then have a brief look at cgroups and memory. We recommend you go through these sections as well. Please, do read on!

Using the kernel’s resource-managed memory allocation APIs

Especially useful when working on device drivers, the kernel provides a few managed APIs for memory allocation. These are formally referred to as the device resource-managed or devres APIs (the link to the official kernel documentation on this is https://www.kernel.org/doc/html/latest/driver-api/driver-model/devres.html). All these APIs are prefixed with devm_; though there are several of them, we will focus on only one common use case here – that of using the resource-managed versions...

Caveats when using the slab allocator

We will split up this discussion into three parts. We will first re-examine some necessary background (which we covered earlier), then actually flesh out the problem that we’re getting at with two use cases – the first being very simple; the second being a more real-world case of the issue at hand.

Background details and conclusions

So far, you have learned some key points:

• The page (or buddy system) allocator allocates pages to the caller in powers of 2 pages; in other words, the granularity of an allocation request is a page (typically 4K). The power to raise 2 is called the order; it typically ranges from 0 to 10 (on both x86[_64] and ARM[_64], assuming a page size of 4K and MAX_ORDER of 11).
• This is fine, except when it’s not. When the amount of memory requested is very small, or just over a certain threshold, the wastage (or internal fragmentation) can be huge.
• In the day-to-day operation...

Summary

In this chapter, you learned – to a good level of detail – how both the page (or buddy system) and the slab allocators work. Recall that the actual “engine” of allocating (and freeing) RAM within the kernel is ultimately the page (or buddy system) allocator, with the slab allocator being layered on top of it to provide optimization for typical less-than-a-page-in-size allocation requests, and to efficiently allocate several well-known kernel data structures (‘objects’).

You learned how to efficiently use the APIs exposed by both the page and slab allocators, with several demo kernel modules to help show this in a hands-on manner. A good deal of focus was (quite rightly) given to the real issue of the developer issuing a (slab) memory request for a certain N number of bytes, but you learned that it can be very sub-optimal, with the kernel actually allocating much more (the wastage can climb very close to 100%)! You now know how...

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/ch8_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/master/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/master/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