#understanding linux

This is a multi-part blog post series.

Part 1 was based on Gustavo Duarte’s blog posts on Anatomy of a Program in Memory and How the Kernel Manages Your Memory. Part 2 talks about different memory caches, based on Gustavo Duarte’s post on Page Cache, the Affair Between Memory and Files. Part 3 is an high level description of memory allocation.

References

figures: UnderstandingLinuxEd3, 2005

www.livegrep.com (the best!)

Memory Allocation

A user application might request memory from the kernel. Or, the kernel might need to allocate memory to itself, to set up some data structure (like a vma for a process). The kernel allocates memory in units of the ‘page’. For a vma (vm_area_struct), for example, it searches for consecutive page frames that are at least as large as the vma size. Where does the kernel look?

The Allocators:

The Zoned Page Frame Allocator

There are a hierarchy of allocators. The top level of the hierarchy is the Zoned Page Frame Allocator (ZPFA), shown in the Figure: Zoned Page Frame Allocator. It iterates through each zone, looking for enough contiguous page frames to satisfy a kernel request (alloc_pages). If the kernel only needs to allocate a single page frame, then, within each zone, it iterates through each cpu, looking in the cpu caches for a single page frame. If it finds one, great. Otherwise, the kernel requests the page frames from the buddy system in that zone. If the kernel succeeds, great. Otherwise, it continues to the next zone. If it does not succeed, then the kernel, if it is able to, triggers the subsystem to reclaim page frames. After page frames are reclaimed, the kernel continues to search for free page frames to allocate.

Figure: Zoned Page Frame Allocator

The Slab Allocator

The Slab Allocator requests page frames from the ZPFA. It stores commonly-used objects, like vm_area_structS, that can be used and re-used by the kernel, rather than having the system reclaim and re-allocate the page frames, and re-init the vma objects. The Slab Allocator is called ‘Slab’ because its page frames are organized into ‘slabs’. Each slab stores objects of the same type. An object store is called a ‘cache’. Figure: Slab Allocator puts all the pieces together.

Figure: Slab Allocator

The kernel represents a cache and a slab as a descriptor data type. Figure Caches+Slabs shows how slabs are organized into caches.

Empty slab: no page frames (and thereby no objects)

Full slab: no free objects (all objects are in-use)

Partially-full slab: has some free (i.e., unused) objects that are ready to be re-used

Note: The Slab Allocator’s ‘free’ object is not free in the same way that memory is free in the ZPFA. A ‘free’ page in the ZPFA is unallocated. A ‘free’ page in the Slab Allocator is allocated to it by the ZPFA but contains no objects. A free object in the Slab Allocator is not currently in-use and is free (ready) to be re-used. Only after the Slab Allocator releases a page frame to the ZPFA (’released to the buddy system’) and the page frame is on the buddy system’s free list, is the page frame truly free (unallocated)

Figure: Caches+Slabs

Kernelshark Visualization of Memory Allocator in Action

The kernelshark output shows the kernel trying to allocate memory for a mm_struct data type. 

Figure: mm_alloc with slab and zone allocation

# allocate an address space object (mm_struct) from a cache

mm_alloc -> kmem_cache_alloc

# initialize the mm_struct object

mm_init -> pgd_alloc -> __get_free_pages

/* The kernel must allocate memory for the page table, which it does by requesting free page frames from the ZPFA. The kernel iterates through each zone. For each zone, it looks for enough contiguous pages from the free list to satisfy the request. */

get_page_from_freelist -> __rmqueue

__rmqueue is the request to the buddy system of the ZPFA for a single page frame. It is repeated as many times as necessary to all all requested page frames.

Figure below shows the kernel can request objects from the Slab Allocator or page frames from the ZPFA. A user process has access to the ZPFA but not to the Slab allocator.

When necessary, the Slab Allocator requests pages from the ZPFA.

When pages cannot be allocated, pages must be reclaimed.

The kernel keeps a reserved memory pool so it can satisfy requests that cannot be blocked, and therefore, cannot wait for the page reclaim process.

Part 1 of my blog post was based on Gustavo Duarte’s 2 blog posts: Anatomy of a program in memory and How the Kernel Manages Your Memory .

This post is based on Gustavo’s post Page Cache: The Affair Between Memory and Files, with additional pictures and kernelshark output.

Gustavo’s posts are amazing because of his wonderfully and carefully detailed figures. (I’ve found them in several university class slides.)

Part 3 is a high-level view of memory allocation.

My added value:

introducing the swap cache

clarification of terminology and concepts

extra figures [source: Understanding Unix, Ed. 3, 2005 (sort of old)]

kernelshark output (sort of like watching memory management in action).

The page cache refers to a collection of page frames used to store device I/O that are not owned by a user process plus the page frames used for tmpfs. If the underlying data is stored as sequential device blocks, it is just called a page. If the underlying data is stored as individual device blocks (that may not be sequential), the page is called a buffer page. Buffer cache refers to a subset of the page cache that contain buffer pages.

tmpfs: a filesystem whose files are stored in virtual memory. No data is written to disk. See documentation in Documentation folder of the kernel tree.

Why bring up the details of buffer cache? Because older documentation refers to it as a cache separate from the page cache. Not true anymore. It is now implemented as part of the page cache.

Bottom Line:

Page Cache caches file-backed pages:

   kernel writes back data to a file on disk

Swap Cache caches anonymous pages and in-memory filesystem pages (like tmpfs)

[There are other caches, such as the caches that are part of the Slab Allocator. Those caches will be discussed in Part 3: allocation].

See Figure: Swap Cache for a description of how the PTE (page table entry), swap cache and swap area (on disk) are used together to swap out and swap in anonymous (non file-backed) pages.

Not all caches are equal. When the kernel is low on memory, and needs to reclaim pages, it prefers to writeback pages from the page cache rather than swap out pages to the swap area. The swappiness variable, which influences this bias, ranges from 0 to 100. If set to 100, the kernel treats writebacks and swap outs equally. The default value is 60.

The kernel’s first choice for reclaiming pages are pages in the page cache that are not referenced by any process. The kernel’s second choice are clean pages in the page cache: pages that do not need to be written back to disk before being reclaimed.

For a discussion on swappiness, see Reconsidering Swappiness [June 7, 2016, lwn.net.]

Definitions/Clarifications:

writeback vs swap out

writeback: refers to writing pages in the page cache to a file on disk

swap out: refers to writing anonymous pages to the swap area on disk

file object vs file on disk (inode)

file object: also called a file descriptor; the representation in the kernel of an open file, opened by a given process

inode object: represents a file on disk; many file objects can point to the same underlying file; interface between the application-facing file and the raw data sectors on disk

file access vs block access

file access: application accesses data using the file abstraction; data in file consists of contiguous segments on disk (contiguous ‘disk blocks’)

block access: application accesses the raw sector data (also known as ‘device blocks’) directly (block-device + index of the block on the device)

page vs buffer page

buffer: a representation, in the kernel, of data stored in a device block

buffer head: describes the physical location of the data underlying a buffer; one descriptor per buffer

buffer page: a page frame containing buffers; each buffer contains data from a specific device block

Figure: Buffer Page+ shows how page frame, buffer, and buffer head are related in the big picture.

Figure: Process+File Descriptor+Inode+Disk File

Figure: A Buffer Page+Buffer Head

Figure: Swap Cache+Swap Area+Page Table Entries (PTEs)

Kernelshark Output

The kernelshark visualizations show an animation of the process id (pid) 3302.

Figure: Add page to cache

[A reference to the kernel code is here.]

# write to a file on disk

generic_perform_write ->

# look for page in page cache

grab_cache_page_write_begin -> pagecache_get_page         

# can’t find page; allocate a page frame

__pagecache_alloc           

# iterate through each zone, looking for a free (unallocated) page frame

next_zones_zonelist -> get_page_from_freelist    

# kernel allocates a page frame from the free list

# kernel adds the page to the page cache

add_to_page_cache_lru

# mm_filemap_add_to_page_cache completes in 6 us.

The file-backed data underlying this page is described in the info column of the kernelshark output:

Wouldn't it be great to learn the story of linux MM through pictures? Together with some animation, we can follow the flow of what MM is doing on running programs. Of course we need words and definitions, but it sure helps to visualize some of the "black magic" that is going on under the hood. (This blog series is in multiple parts. Part 2 gives an overview of page cache and swap cache. Part 3 introduces memory allocation.)

My starting point for this linux MM adventure was the Round 12 Outreachy application in March 2016.

I picked the linux kernel project and the mentor, Rik Riel, posted two "small" tasks:

Cause the system to swap, and use ftrace and the trace points in mm/page_alloc.c and mm/vmscan.c to determine how long it takes to allocate (and free) pages.

Repeat the same exercise when the system is under heavy filesystem read IO, and when doing lots of filesystem writes (enough to fill up memory).

Use kernelshark to visually examine the observed latencies.

Where to start?

Let's parse these "simple" tasks. One path of learning is related to tools:    ftrace, trace points, kernelshark Another path of learning is related to MM concepts:    to swap, the swap cache, the swap area, a swap file    to allocate memory, to free (meaning 'to release') memory, free (meaning 'not allocated') memory    filesystem: how does the kernel represent a filesystem?    file: how does the kernel represent a file?    "fill up memory": what is "full"? what part of memory can "fill up"?

Baseline

Let’s see how much we know now. In a terminal window, run the meminfo command.

>$ cat /proc/meminfo

The output lists types of page frames like Anon and Mapped. This post covers those types. The next post covers Buffers, Cached, SwapCached, Active (file or anon), Inactive (file or anon), inevictable, dirty, clean, private, shared. (All terms in meminfo are explained here.)

>$ cat vmstat -s

provides statistics  on memory since your last boot. It includes pages swapped in and out, and paged in and out. This information should make more sense as you read on.

The Big Picture One day I found Gustavo Duarte's blog (from a link on a university professor's slides) called 'brain food for hackers', which includes great pictures for telling the MM story. This post refers to two of his posts: Anatomy of a program in memory and How the Kernel Manages Your Memory.

Lesson 1: Anatomy of a program in memory concepts:   -- modes: kernel, user        -- kernel mode process, user mode process

  -- physical memory segments        -- memory-mapped segment (file-backed, anonymous, shared, private)   -- physical memory: used (allocated) memory, free (unallocated) memory   -- page tables

The figure below shows the relationship between a user mode process and kernel mode processes.

Figure: User Mode+Kernel Mode

The data type mm_struct represents a process’s address space, including its virtual memory areas (vmaS). The page tables (referred to as a single ’page table’) map a virtual address to the address of a page descriptor, which describes and points to a physical page frame.

Figure: Virtual Address+Page Tables shows how a virtual address is divided into fields of bits. Each field is used to calculate an offset into a table. 

Figure: Virtual Address+Page Tables

Figure Page Tables shows more detail with respect to the page tables (page global directory (PGD), page middle directory (PMD), page table entries (PTE)) and includes the page descriptor (struct page).

Figure: Page Tables (PGD, PMD, PTE)

    Lesson 2:     How the Kernel Manages Your Memory

     process: a program managed by the kernel; it is either running, ready to run, or waiting for some event before it can resume

process (task_struct): The kernel represents a process as a process descriptor. The process address space is described by its memory descriptor, mm_struct.

process address space (mm_struct)

Figure:  process descriptor shows the mm field pointing to the address space of the process. (mm->mm_struct). The mm_struct, in turn, points to the head of a list of virtual memory areas (vm_area_structS).

Other task_struct fields to notice, since they are important in writing device drivers (Part 5 of blog post):

  -- fs: points to fs_struct, which holds filesystem data

 -- files: points to files_struct, which stores a collection of file descriptors (1 file descriptor (struct file) for each file opened by this process)

Figure: process descriptor

virtual memory

vma (virutal memory area) descriptor (vm_area_struct): identifies a contiguous region of virtual memory addresses . In the figure below (p. 440, Figure 9-2), a vma is represented as a gray region in the linear address space (linear is synonymous with virtual). The mm_struct points to the head of a list of vm_area_structS.

Figure: Virtual Memory

memory mapping

file-backed: memory is associated with a file or device

               example: shared library, text segment, data segment

anonymous: data is not associated with a file or device

               example: stack, heap, bss segment

In Figure: Data Structures+Memory Mapping, notice the VMAs (vm_area_struct). The virtual addresses in the left vma are translated to physical addresses in (mapped to) 2 page frames in the file represented by struct inode. The right vma is mapped to one page frame in the same file. The set of vm_area_structS represent the virtual address space of a user process. If the vm_file member of a vma is not NULL, then the vma is said to be file-backed. In the Figure, both vmaS are file-backed and point to the same file. (In the current version of linux, struct file (an open file object) points directly to struct inode (the underlying file). The kernel manages physical memory in units of page frames (PAGE_SIZE is typically 4096 bytes). Each page frame is described by its own descriptor (struct page).

Bottom Line: when a process accesses a virtual address, the address is mapped to an offset in a page frame. The page frame is associated with an offset into a specific file on disk. The part of the file associated with the page frame is said to be “memory-mapped”. The vma is said to be “memory-mapped” with memory allocated to the vma.

If the vm_file member of a vma is NULL, the vma is said to be anonymous, (not file-backed).

file-backed vs anonymous: determines where the kernel writes the page frame to disk. A file-backed page frame is written to the blocks associated with the file’s inode. An anonymous page frame is written to a swap area on disk.

Figure: Data Structures+Memory Mapping

PAGE_SIZE: typically 4096 bytes

page vs page frame

page: a contiguous sequence of virtual addresses; the first byte has a virtual address that is a multiple of PAGE_SIZE; this term refers to the memory cells as well as the data contents of the memory

page frame: a contiguous sequence of PAGE_SIZE physical memory cells; the first byte has a physical address that is a multiple of

page descriptor (struct page): the kernel’s representation of a page frame

demand paging:

the kernel allocates a page frame to a process only at the time that the process accesses a virtual address that is contained in a valid vma; think of this as lazy page frame allocation

page fault:

           the mechanism used by the kernel to allocate a page of memory            to a process on demand

Here is the kernelshark visualization of how the kernel handles a page fault.

These pages show the beginning and ending of the function graph for do_page_fault -> find_vma -> vmacache_find -> handle_mm_fault -> filemap_map_pages -> do_set_pte -> do_set_pte -> ... -> do_set_pte

The vmacache_find checks the vma corresponding to the last virtual address accessed. In Figure: Virtual Memory, mmap_cache is vmacache.

Quiz:

Now that we have come this far, let’s measure how far we have come.

1. Run the commands again, and see how much of the output you understand.

>$ cat /proc/meminfo

>$ vmstat -s

 2. Can you understand the following excerpts from LWN.net ?

2a. Memory used for file-backed data can be accessed by direct reads and writes and can be mapped concurrently by multiple processes, which may request differently sized mappings. [ May 11, 2016]

2b. Anonymous memory is only accessed by memory mapping (i.e. with mmap()) and the size of this mapping is usually fixed on allocation. [ May 11, 2016]

2c. ..[W]hat to do if all of the system's memory is tied up in the tmpfs filesystem (which has no backing store and only stores files in memory). [Improving the OOM killer, 4/27/2016]

3. Extra Credit:

The SLOB support extracted from grsecurity seems entirely broken. I  have no idea what's going on there, I spent my time testing SLAB and  SLUB. Having someone else look at SLOB would be nice, but this series  doesn't depend on it. [mm: Hardened usercopy, 7/6/2016]

"Understanding Linux : Micro-Kernel Through User-Level in Simple Terms."