Memory Management

Linux’s physical memory-management system deals with allocating and freeing pages, groups of pages, and small blocks of memory.

It has additional mechanisms for handling virtual memory, memory mapped into the address space of running processes.

Splitting of Memory in a Buddy Heap

Managing Physical Memory

The page allocator allocates and frees all physical pages; it  can allocate ranges of physically-contiguous pages on request.

The allocator uses a buddy-heap algorithm to keep track of available physical pages.

    1. Each allocatable memory region is paired with an adjacent partner.

    2. Whenever two allocated partner regions are both freed up they are combined to form a larger region.

    3. If a small memory request cannot be satisfied by allocating an existing small free region, then a larger

        free region will be subdivided into two partners to satisfy the request.

Memory allocations in the Linux kernel occur either statically (drivers reserve a contiguous area of memory during system boot time) or dynamically (via the page allocator).

Virtual Memory

The VM system maintains the address space visible to each process: It creates pages of virtual memory on demand, and manages the loading of those pages from disk or their swapping back out to disk as required.

The VM manager maintains two separate views of a process’s address space:

      1. A logical view describing instructions concerning the layout of the address space.

The address space consists of a set of non overlapping regions, each representing a continuous, page-aligned subset of the address space.

      2. A physical view of each address space which is stored in the hardware page tables for the process.

Virtual memory regions are characterized by:

      1.The backing store, which describes from where the pages for a region come; regions are usually

          backed by a file or by nothing (demand-zero memory)

      2. The region’s reaction to writes (page sharing or copy-on write).

The kernel creates a new virtual address space

      1. When a process runs a new program with the exec system call

      2. Upon creation of a new process by the fork system call

On executing a new program, the process is given a new, completely empty virtual-address space; the program loading routines populate the address space with virtual memory regions.

Creating a new process with fork involves creating a complete copy of the existing process’s virtual address space.

      1. The kernel copies the parent process’s VMA descriptors, then creates a new set of page tables for

           the child.

      2. The parent’s page tables are copies directly into the child’s, with the reference count of each page

           covered being incremented.

      3.  After the fork, the parent and child share the same physical pages of memory in their address 

           spaces.

The VM paging system relocates pages of memory from physical memory out to disk when the memory is needed for something else.

The VM paging system can be divided into two sections:

      1. The page out-policy algorithm decides which pages to write out to disk, and when.

      2. The paging mechanism actually carries out the transfer, and pages data back into physical memory

           as needed.

The Linux kernel reserves a constant, architecture dependent region of the virtual address space of every

process for its own internal use.

This kernel virtual-memory area contains two regions:

      1. A static area that contains page table references to every available physical page of memory in the

          system, so that there is a simple translation from physical to virtual addresses when running kernel

          code.

     2. The reminder of the reserved section is not reserved for any specific purpose; its page-table entries

          can be modified to point to any other areas of memory.

Executing and Loading User Programs

Linux maintains a table of functions for loading programs;

it gives each function the opportunity to try loading the given file when an exec system call is made.

The registration of multiple loader routines allows Linux to support both the ELF and a. out binary formats.

Initially, binary-file pages are mapped into virtual memory; only when a program tries to access a given page will a page fault result in that page being loaded into physical memory.

An ELF-format binary file consists of a header followed by several page-aligned sections; the ELF loader works by reading the header and mapping the sections of the file into separate regions of virtual memory.

Memory Layout for ELF Programs

Static and Dynamic Linking

A program whose necessary library functions are embedded directly in the program’s executable binary file is statically linked to its libraries.

The main disadvantage of static linkage is that every program generated must contain copies of exactly the same common system library functions.

Dynamic linking is more efficient in terms of both physical memory and disk-space usage because it loads the system libraries into memory only once.