Linux Memory Management

Pages

The processor’s smallest addressable unit is a byte or a word, but the memory management unit (MMU) usually works with pages. The MMU maintains page tables with page-sized granularity for virtual to physical address translations.
Each architecture defines its own page size. Many architectures even support multiple page sizes. Most 32-bit architectures have 4KB pages, whereas most 64-bit architectures have 8KB pages.
The kernel represents every physical page on the system with a struct page structure. This structure is defined in <linux/mm_types.h>.
```
struct page {
	unsigned long         flags;
	atomic_t              _count;
	atomic_t              _mapcount;
	unsigned long         private;
  struct address_space  *mapping;
  pgoff_t               index;
	struct list_head      lru;
	void                  *virtual;
};
```
- flags field stores the status of the page, e.g. dirty, locked, etc.
- _count field stores the usage count of the page—that is, how many references there are to this page. When this count reaches negative one, no one is using the page, and it becomes available for use in a new allocation.
  - Check page count using function call page_count(): Although internally _count is -1 when the page is free, page_count() returns zero to indicate free and a positive nonzero integer when the page is in use.
- A page may be used by the page cache (in which case the mapping field points to the address_space object associated with this page), as private data (pointed at by private), or as a mapping in a process’s page table.
- The virtual field is the page’s virtual address
- Kernel uses this structure to keep track of all the pages in the system
The page structure is tied to physical pages, not virtual pages. This means that what structure describes is transient at best. The data in a page may continue to exist, but it might not always be associated with the same page structure due to swapping and other factors. The kernel uses this data structure to describe the physical page it’s associated with, with the goal of describing physical memory rather than the data it contains.

Page Allocation

Interfaces that kernel implements to enable you to allocate and free memory.

Getting Pages

All interfaces allocate memory with page-sized granularity and are declared in <linux/gfp.h>.

Allocate pages with page struct pointer return
```
struct page * alloc_pages(gfp_t gfp_mask, unsigned int order)
```
- This function 2^order (that is,1 << order) contiguous physical pages and returns a pointer to the first page’s page structure.
- This function allocates page from high memory returns a struct page and not a pointer to a logical address. Because high memory might not be mapped.
Convert given pages to its logical address
```
void * page_address(struct page *page)
```

Allocate pages with logical address return

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)

Getting Zeroed Pages

Allocates a single page, zero its contents and returns a pointer to its logical address.

unsigned long get_zeroed_page(unsigned int gfp_mask)

This is useful for pages given to user-space because the random garbage in an allocated page is not so random; it might contain sensitive data.

Freeing Pages

You must be careful to free only pages you allocate. Passing the wrong struct page or address, or the incorrect order, can result in corruption.

void __free_pages(struct page *page, unsigned int order)
void free_pages(unsigned long addr, unsigned int order)
void free_page(unsigned long addr)

These low-level page functions are useful when you need page-sized chunks of physically contiguous pages. For more general byte-sized allocations, the kernel provides kmalloc().

Zones

ZONE_DMA—This zone contains pages that can undergo DMA (Direct Memory Access)
ZONE_DMA32—Like ZOME_DMA, this zone contains pages that can undergo DMA. Unlike ZONE_DMA, these pages are accessible only by 32-bit devices. On some architectures, this zone is a larger subset of memory.
ZONE_NORMAL—This zone contains normal, regularly mapped, pages.
ZONE_HIGHMEM—This zone contains “high memory,” which are pages not permanently mapped into the kernel’s address space.

The actual usage and layout of the memory zones are architecture-dependent. The values in the four zones depends on the different kinds of architecture.
Linux partitions the system’s pages into zones to have a pooling in place to satisfy allocations as needed.
- For example, having a ZONE_DMA pool gives the kernel the capability to satisfy memory allocations needed for DMA.

`kmalloc`

void * kmalloc(size_t size, gfp_t flags)

In the C, size_t is an unsigned integer type that is commonly used to represent sizes and counts of objects. The size_t type is guaranteed to be able to represent the maximum size of any object that can be allocated in memory. Its size can vary depending on the platform and the implementation, but it is usually defined as an unsigned long or unsigned long long.

The function returns a pointer to a region of memory that is at least size bytes in
length. The region of memory allocated is physically contiguous.

gfp_mask Flags

Three categories: action modifiers, zone modifiers, and types.

Action modifiers: Action modifiers specify how the kernel is supposed to allocate the requested memory. In certain situations, only certain methods can be employed to allocate memory.
- For example, interrupt handlers must instruct the kernel not to sleep (because interrupt handlers cannot reschedule) in during allocating memory.
  
  Action Modifiers Flags
```
// This call instructs the page allocator (ultimately alloc_pages()) that the allocation can block, perform I/O, and perform filesystem operations, if needed.
ptr = kmalloc(size, __GFP_WAIT | __GFP_IO | __GFP_FS);
```
Zone modifiers specify from where to allocate memory.
Type flags specify the required action and zone modifiers to fulfill a particular type of transaction.

Type Flags

Which Flag to Use When

`kfree`

void kfree(const void *ptr)

`vmalloc`

// declared in <linux/vmalloc.h>
// defined in mm/vmalloc.c
void * vmalloc(unsigned long size)
void vfree(const void *addr)

Despite the fact that physically contiguous memory is required in only certain cases, most kernel code uses kmalloc() and not vmalloc() to obtain memory. Primarily, this is for performance.

Performance issue: vmalloc() function, to make nonphysically contiguous pages contiguous in the virtual address space, must specifically set up the page table entries.
Thus, vmalloc() is used only when absolutely necessary—typically, to obtain large regions of memory. For example, when modules are dynamically inserted into the kernel, they are loaded into memory created via vmalloc().

Slab Layer

Motivation & Definition

One background and one issue about kernel memory allocation.

To remedy this, the Linux kernel provides the slab layer (also called the slab allocator).The slab layer acts as a generic data structure → caching layer.

Generic data structure is a structure that can be used to store any type of data.

The slab layer divides different objects into groups called caches, each of which stores a different type of object. There is one cache per object type.

For example, one cache is for process descriptors (a free list of task_struct structures), another cache is for inode objects (struct inode).

The caches are then divided into slabs. The slabs are composed of one or more physically contiguous pages. Typically, slabs are composed of only a single page. Each cache may consist of multiple slabs.

The slab layer works by first allocating a big block of memory, called a slab, from the page allocator. The slab is then divided into smaller objects of the same size, which are linked together. When an object is needed, the slab layer searches the linked list for an available one. If it finds one, it’s returned. If no available objects are found, the slab layer creates a new object and adds it to the linked list. When an object is no longer needed, it’s returned to the slab layer, which marks it as free and adds it to the end of the linked list.

Tenets of Design

Cache frequently used structures → Frequently used data structures tend to be allocated and freed often, so cache them.
Prevent memory fragmentation → Frequent allocation and deallocation can result in memory fragmentation (the inability to find large contiguous chunks of available memory). To prevent this, the cached free lists are arranged contiguously. Because freed data structures return to the free list, there is no resulting fragmentation.
Performance → The free list provides improved performance during frequent allocation and deallocation because a freed object can be immediately returned to the next allocation.

Slab Layer Structure

Each slab is in one of three states: full, partial, or empty.

A full slab has no free objects. (All objects in the slab are allocated)
An empty slab has no allocated objects (All objects in the slab are free)
A partial slab has some allocated objects and some free objects

Each cache is represented by a kmem_cache structure.This structure contains three lists—slabs_full, slabs_partial, and slabs_empty—stored inside a kmem_list3 structure, which is defined in mm/slab.c.

A slab descriptor,struct slab, represents each slab is:

The slab allocator creates new slabs by interfacing with the low-level kernel page allocator via __get_free_pages().

For educational purposes, we can ignore the NUMA-aware code and write a simple kmem_getpages():

In the Linux kernel, gfporder is an unsigned integer that represents the base 2 logarithm of the number of pages to allocate for each slab.

Memory is then freed by kmem_freepages(), which calls free_pages() on the given cache’s pages. The freeing function is called only when available memory grows low and the system is attempting to free memory, or when a cache is explicitly destroyed.

Slab Layer Interface

cache create function

First parameter is a string storing the name of the cache.
Second parameter is the size of each element in the cache.
Third parameter is the offset of the first object within a slab. This is done to ensure a particular alignment within the page. Normally, zero is sufficient, which results in the standard alignment.
Flags parameter specifies optional settings controlling the cache’s behavior.
- It can be zero, specifying no special behavior, or one or more of the following flags OR’ed together:
  - SLAB_HWCACHE_ALIGN: Aligns each object within a slab to a cache line. This prevents “false sharing” (two or more objects mapping to the same cache line despite existing at different addresses in memory). This improves performance but comes at a cost of increased memory footprint.
  - SLAB_POISON: Causes the slab layer to fill the slab with a known value (a5a5a5a5). This is called poisoning and is useful for catching access to uninitialized memory.
  - SLAB_RED_ZONE: Causes the slab layer to insert “red zones” around the allocated memory to help detect buffer overruns.
  - SLAB_PANIC: Causes the slab layer to panic if the allocation fails.
  - SLAB_CACHE_DMA: Instructs the slab layer to allocate each slab in DMA-able memory.
Final parameter, ctor, is a constructor for the cache.The constructor is called whenever new pages are added to the cache.$

After a cache is created, an object is obtained from the cache via:

void * kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)

This function returns a pointer to an object from the given cache cachep. If no free objects are in any slabs in the cache, and the slab layer must obtain new pages via kmem_getpages(), the value of flags is passed to __get_free_pages().

void kmem_cache_free(struct kmem_cache *cachep, void *objp)

Allocation on the Stack

Single-Page Kernel Stacks

Reason_1: It results in a page with less memory consumption per process
Reason_2: As uptime increases, it becomes increasingly hard to find two physically contiguous unallocated pages

Historically, interrupt handlers shared the stack of the interrupted process.When single page stacks are enabled, interrupt handlers are given their own stacks. In any case, unbounded recursion is obviously not allowed.

Stack Overflows

Stack overflows can occur silently and result in various issues. The kernel does not attempt to manage the stack, so when a stack overflow happens, the excess data spills over to whatever exists at the end of the stack.

First thing to eat it is the thread_info structure, which is allocated at the end of each process’s kernel stack.
Beyond the stack, any kernel data might lurk and leads to data curruption.

High Memory Mappings

Memory Mapping Intro

A 32-bit architecture can only address 4 GB of memory, but not all of it is available for use by the system. The address space is divided between user space and kernel space. Typically, the lower 3 GB is used for user space, while the upper 1 GB is reserved for the kernel. This means the kernel can only directly address 1 GB of physical memory.

When a system has more than this amount of physical memory, the additional memory is referred to as “high memory.” This memory is not directly mapped into the kernel’s address space, and the kernel cannot directly access it.

To use high memory, the kernel uses a technique called high memory mappings. It sets up special mappings that allow it to temporarily view a portion of the high memory in its address space. When it needs to access some data in the high memory, it creates a mapping, accesses the data, and then removes the mapping.

This process is more complex and has more overhead than accessing directly mapped memory, so it can reduce performance. But it allows systems with a 32-bit architecture to use more than 1 GB of physical memory.

In 64-bit systems, this isn’t generally a problem because the address space is vastly larger (2^64 bytes), so all of the physical memory can be directly mapped into the kernel’s address space.

High Memory Mapping x86

On an x86 architecture, any physical memory beyond 896 MB is considered high memory. Even though x86 processors can physically address up to 4GB (or up to 64GB with Physical Address Extension (PAE)), these pages need to be explicitly mapped into the kernel’s logical address space after allocation. On x86, pages in high memory are mapped somewhere between the 3GB and 4GB mark.

Permanent Mappings

Permanent mapping a given page into the kernel’s address space use function: void kmap(struct page *page). This function is capable of working with both high and low memory. If the page is in low memory, the page’s virtual address is simply returned. However, if the page is in high memory, a permanent mapping is created and the address is returned. The void kunmap(struct page *page) function is then used to unmap the high memory when it is no longer needed.

Temporary Mappings

Sometimes a context cannot sleep and needs a mapping to be created. In such cases, temporary (or atomic) mappings are used. These are a set of reserved mappings that can hold a temporary mapping. They can be set up using kmap_atomic(struct page *page, enum km_type type), and are useful in contexts that cannot be blocked, like interrupt handlers. The purpose of the temporary mapping is defined by the km_type enumeration. The temporary mapping is undone using kunmap_atomic(void *kvaddr, enum km_type type).

Per-CPU Allocation

Note that no lock is required because this data is unique to the current processor.

Kernel Preemption Issue

If your code is preempted and reschedules on another processor, the cpu variable becomes invalid since it points to the wrong processor.
If another task preempts your code, it can access my_percpu on the same processor concurrently, creating a race condition.

We do not need to worry about this issue, because the call get_cpu() disables kernel preemption.The corresponding call to put_cpu() enables kernel preemption.

Reasons for Using Per-CPU Data

Reduction in locking requirements

Note that the only safety requirement for the use of per-CPU data is disabling kernel preemption, which is much cheaper than locking, and the interface does so automatically.
per-CPU data greatly reduces cache invalidation

If one processor manipulates data held in another processor’s cache, that processor must flush or otherwise update its cache. Constant cache invalidation is called thrashing the cache and wreaks havoc on system performance. The use of per-CPU data keeps cache effects to a minimum because processors ideally access only their own data.

Summary: Allocate Memory in Kernel

Use low-level page allocators like kmalloc() for contiguous physical pages. Use the GFP_ATOMIC flag for high-priority allocation that won’t sleep, required for interrupt handlers and non-sleeping code. Use GFP_KERNEL for process context code that can sleep but doesn’t hold a spin lock.
For high-memory allocation, use alloc_pages(). This returns a struct page, not a pointer to a logical address. Use kmap() to map high memory into the kernel’s logical address space to obtain an actual pointer.
Use vmalloc() for virtually contiguous memory. Note that vmalloc() has a slight performance hit compared to kmalloc(). This function allocates kernel memory that is virtually contiguous but not physically contiguous.
For creating and destroying many large data structures, set up a slab cache. This maintains a per-processor object cache, which can greatly enhance object allocation and deallocation performance.