Linux Memory Management

---

Timeline

Timeline

2025-11-20

init

2026-07-25

This article introduces the core concepts of Linux memory management and the hardware interaction process, including address space isolation issues, segmentation and paging mechanisms, as well as the differences between logical addresses, linear addresses, virtual addresses, and physical addresses. The article elaborates on the roles of key hardware modules such as CPU, MMU, TLB, Cache, main memory, page tables, and Swap, and explains the processing flow of address translation, data reading, and page fault interrupts. In addition, it summarizes the memory management mechanisms of user space and kernel space, such as system calls, VMA management, delayed allocation, anonymous pages, page cache, page reclamation, and SLAB allocators.

About Addresses

Address space not isolated

1. Malicious processes can arbitrarily modify the memory of other processes

2. Memory usage efficiency is very low; for example, when memory is scarce, all data in a process must be swapped to the swap partition

Early memory usage methods

• Segmentation(Main idea: map the virtual address space to the physical address space one-to-one; the entire program must be loaded into memory to run)
• Paging(Main idea: when a program runs, only allocate the page that is needed, i.e., allocate on demand; pages not needed for a long time can be swapped to disk)

Address Concepts：

• Logical address(Intel-specific term; the part that generates the offset address related to the segment)

• Linear address(Intel-specific term; an intermediate layer in converting logical addresses to physical addresses. In segmentation, the logical address is the segment offset address, and adding the base address turns it into a linear address)

• virtual address (Logical addresses and linear addresses are collectively called virtual addresses)

• Physical address(The address required by the CPU to access physical memory through the external bus)

• Process address space

Memory management hardware structure diagram

• Core hardware modules

  • CPU: The main body that executes program instructions. What the CPU’s internal registers and computing units process are allvirtual address(Virtual Address), and cannot directly operate on physical memory modules.

  • MMU (Memory Management Unit): Hardware located inside the CPU chip, specifically responsible for converting what is issued by the CPU Virtual address translation to physical address。

  • TLB (Translation Lookaside Buffer, page table cache): An extremely high-speed cache inside the MMU, specifically used to cache recently used “virtual address $\rightarrow$ physical address” mapping relationships, also known as a fast table.

  • L1 Cache & L2 Cache: High-speed SRAM memory located between the CPU and main memory.

    • L1 Cache: Fastest, located right next to the MMU.
    • Physical Index / Physical Tag: As indicated in the figure, physical addresses (or physical index/tag) are used for addressing and data verification between the L1 and L2 caches.

  • Main Memory (DRAM): That is, the physical memory modules in the system, used to store instructions and data for the system and running processes.

    • Page Table: Stored inmain memoryThe mapping data structure in main memory (multi-level page table). When the TLB misses, the MMU needs to query the page table in main memory to find the address mapping.

  • Swap (swap space / disk swap area): A storage area located on the disk/SSD. When main memory space is insufficient, the kernel temporarily swaps out infrequently used memory pages to this area; when needed, they are swapped in to main memory.

• Hardware operation and interaction flow

  • Address translation flow (MMU $\rightarrow$ TLB / page table)

    1. CPU issues a virtual address: The CPU executes a memory access instruction and sends the virtual address to the MMU.

    2. TLB Hit：

       • The MMU first queries the TLB. If the mapping for this virtual address exists in the TLB, it is called TLB Hit, the MMU can directly obtain the physical address in a very short time (usually within 1 CPU clock cycle).

    3. TLB Miss：

       • If the mapping is not in the TLB, it is called TLB Miss。

       • The MMU must traverse downward along the arrow to accessthe page table in main memory(through the Page Table Walk mechanism), find the corresponding physical address, and update it to the TLB in passing, so that it can be accessed quickly next time.

  • Data read process (MMU $\rightarrow$ Cache $\rightarrow$ main memory)

    1. Access Cache: After the MMU obtains the translated physical address, it queriesL1 CacheandL2 cache。

       • If the cache hits (Cache Hit), the data is returned directly to the CPU without accessing the actual physical memory.

    2. Access main memory: If the cache misses (Cache Miss), the hardware will accessmain memory, load the data into the cache and return it to the CPU.

    3. Data exchange between main memory and disk (main memory $\leftrightarrow$ Swap）

       • If the page table entry accessed by the CPU shows that the pageis not in physical memory(for example, it has been swapped to disk, or no physical page has been allocated yet), it triggers Page Fault。

       • After the operating system intervenes, it reads the data from the disk’s swap area and reloads it back intomain memory, update the page table, and then the CPU re-executes the memory access instruction.

Memory Management Overview

Memory Management Module Overview

Memory Management Overview

• User Space

  • User Process: An application instance running in user mode. User processes cannot directly access physical memory; they must perform memory operations through the virtual address space.

  • malloc / mmap / mlock / madvise / mremap / ...: Memory management API exposed to developers by the C standard library (e.g., glibc).

    • malloc/free: Common dynamic memory allocation and deallocation interfaces (underlying based onbrkormmap）。
    • mmap: Maps a file or device into a process’s virtual address space, and can also be used to allocate large blocks of anonymous memory.
    • mlock: Locks a specified range of virtual memory in physical memory to prevent it from being swapped to disk.
    • madvise: Provides memory usage advice to the kernel (e.g., sequential read, random read, reclaimable, etc.), assisting the kernel in optimizing management.
    • mremap: Expands or shrinks an existing virtual memory mapping region.

• Kernel Space

  • System Calls: The bridge connecting user space and kernel space. Through CPU interrupt/exception mechanisms (e.g.,syscallinstruction) switches from user mode to kernel mode.
    • sys_brk: Modifies the boundary value at the top of the process data segment (heap) to expand or shrink small blocks of heap memory.
    • sys_mmap: Creates and establishes a new virtual memory area mapping (VMA) in the kernel.
    • sys_madvise: Receives memory advice from user mode and changes the corresponding VMA flags.
  • vmaManagement (Virtual Memory Area):
    • The kernel usesstruct vm_area_structdata structure to manage a contiguous virtual address space of a process (e.g., code segment, data segment, heap, stack, etc.).
    • responsible for checking the validity of virtual addresses, access permissions (read/write/execute), and mapping types.
  • Page Fault Handler：
    • Lazy Allocation Mechanism: When a process requests memory, the kernel only allocates a virtual address (VMA) and does not immediately allocate physical memory.
    • When the CPU first accesses a virtual address that has no physical mapping, it triggers a page fault exception, and the kernel intercepts through this module, allocates a real physical page frame, and then establishes the page table mapping.
  • Anonymous Page：
    • Memory pages without file backing (e.g., a process’s heap, stack, BSS segment,mallocand requested memory).
    • When swapped, they are written to the swap partition/file.
  • page cache(Page Cache):
    • Memory pages used to cache disk file data, such as video caches.
    • By keeping file contents in memory, it greatly improves disk I/O read/write performance; when memory is insufficient, they can be written back to disk and released directly.
  • Page Reclamation：
    • When the system’s physical memory is tight, it is triggered by kernel threads (such askswapd) or the Direct Reclaim mechanism.
    • responsible for releasing dirty pages (writing back to disk), reclaimingpage cacheand swapping anonymous pages to disk, to free up available physical pages.
  • slab(SLAB / SLUB / SLOB Allocator):
    • Forkernel small objects(such astask_struct,mm_structand other structures) memory allocator.
    • It requests a large block of physical pages from the buddy system at once, then subdivides them into fixed-size small memory blocks for reuse, avoiding memory fragmentation and improving allocation efficiency (in the kernel,kmalloci.e., depends on this).
  • Buddy System (Page Allocator)：
    • Linux kernel managementPhysical memoryThe core algorithm at the lowest level.
    • In $2^n$ Contiguous physical pages (Page Frames) as the unit to manage physical memory, specifically solving the external fragmentation problem of physical memory. All upper-layer (SLAB, VMA page faults, etc.) physical page requests ultimately fall on the buddy system.
  • Page table management (kernel page tables and process page tables)：
    • Data structures that maintain the mapping from virtual addresses (VA) to physical addresses (PA) (e.g., four-level or five-level page tables: PGD $\rightarrow$ P4D $\rightarrow$ PUD $\rightarrow$ PMD $\rightarrow$ PTE）。
    • including all per-processuser-space page tablesand the system-wide sharedkernel-space page tables。
  • Reverse mapping (RMAP - Reverse Mapping)：
    • The conventional mapping is “virtual address $\rightarrow$ physical address”. Reverse mapping allows the kernel, through a physical page (struct page) to quickly reverse-lookupwhich virtual addresses of which processesare mapped to this page. It is critical during page reclaim, page migration, and swap.
  • KSM (Kernel Samepage Merging - kernel same-page merging)：
    • A memory deduplication mechanism. The kernel periodically scans anonymous physical pages with identical content and merges them into a read-only shared page (using Copy-on-Write mechanism). Commonly used in virtual machine (KVM) scenarios to save memory.
  • Huge Page (Large Page/Giant Page)：
    • Standard physical pages are typically 4KB. Huge pages (e.g., 2MB or 1GB) can significantly reduce the number of page table entries, improve TLB hit rate, and lower address translation overhead for high-memory-consuming applications (such as databases and high-performance computing).
  • Page Migration：
    • Moves the contents of one physical page to another physical page and updates all related page table mappings. Commonly used for memory balancing on NUMA nodes, memory hotplug, and memory compaction.
  • Memory Compaction：
    • Solves the buddy system’sexternal fragmentationProblem. By moving scattered used physical pages together, contiguous large blocks of free physical pages are pieced together to meet the allocation requirements for large pages or contiguous memory.
  • OOM (Out-of-Memory Killer)：
    • The system’s last line of defense. When physical memory and Swap are completely exhausted and cannot be reclaimed, the OOM Killer will select and kill the process with the highest score (usually the one occupying the most memory) based on the scoring algorithm, to prevent the entire system from crashing.

• Hardware Layer

  • MMU (Memory Management Unit) & TLB (Translation Lookaside Buffer)：

    • MMU (Memory Management Unit): The hardware circuit inside the CPU, responsible for automatically converting the virtual address (VA) issued by the CPU into a physical address (PA) at runtime.
    • TLB (page table cache): The cache inside the MMU, used to cache recently used “virtual addresses” $\rightarrow$ physical address” mapping relationship, thereby accelerating address translation speed.

  • cache(CPU L1 / L2 / L3 cache):

    • A high-speed SRAM cache located between the CPU and physical memory, which automatically caches recently and frequently accessed physical memory data, greatly reducing the CPU’s access latency to DRAM.

  • Physical Memory (Physical Memory / DRAM)：

    • The actual memory module hardware (RAM) installed in the computer. The buddy system divides this physical entity into multiple Nodes and Zones (such as Zone DMA, Zone Normal, Zone HighMem, etc.) for coordinated management.

Memory management from a process perspective

Memory Management from the Process Perspective

1. Typical 32-bit Linux system virtual address space layout:

   • User space (0-3G)：

     • Code Segment & Data SegmentStores the program’s executable instructions and initialization data.
     • heap space: used for dynamic memory allocation (such asmalloc), growing in the direction of higher addresses.
     • mmap space: Used for file mapping, shared memory, etc., growing towards lower addresses.
     • stack space: Used for function calls and local variables, grows toward lower addresses.

   • Kernel space (3G-4G)：

     • All processes share this portion of the address space, used for kernel code, data, and temporary mappings.

     

     Virtual address layout

2. Physical memory mapping：

   • Linear mapping: The kernel maps low-end physical memory (such asZONE_NORMAL) directly and linearly to a fixed region of the kernel address space, offering fast access.

   • High-end mapping: For high-end physical memory (such asZONE_HIGHMEM), the kernel temporarily maps it to the high-end part of the kernel address space only when needed.

3. Process level：task_structandmm_struct

   • task_struct: Each process in the kernel is described by atask_structstructure, which contains all information about the process, and itsmmmember points to the process’s memory descriptor.

   • mm_struct: This is the process’s memory descriptor, the core data structure for managing the process’s virtual address space. It mainly contains two key members:

     • mmap: Points to the root of the process’s virtual memory area (VMA) linked list or red-black tree.
     • pgd: Points to the process’s Page Global Directory, the top-level entry of the page table.

4. Virtual Memory Area (VMA) management

   • VMA（Virtual Memory Area）: The kernel uses avm_area_structstructure to describe a contiguous virtual address space. Each VMA represents a segment of virtual memory with the same attributes (such as readable, writable, executable), e.g., code segment, data segment, heap, stack, mmap mapping region, etc.

   • mm_structThrough themmapmember, all VMAs are organized, making it convenient for the kernel to search, manage, and operate.

5. mem_map[]array: The kernel uses a globalmem_maparray to manage all physical memory pages, and each element in the array is astruct pageA structure representing a physical page frame.

6. ZONE management: Physical memory is divided into different memory management zones (ZONE), such asZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEMetc., each zone has different purposes and management methods.

Memory allocator

Memory allocation diagram

Memory management from the perspective of data structure relationships

Memory management data structure.drawio

Data structure	Main definition files	Supplementary notes
mm_struct	include/linux/mm_types.h	will also beinclude/linux/mm.hwidely referenced and manipulated in
vm_area_struct(VMA)	include/linux/mm_types.h	Describes a contiguous virtual memory region
struct page	include/linux/mm_types.h	In early kernel versions, defined ininclude/linux/mm.h, and in newer versions moved tomm_types.h
struct zone	include/linux/mmzone.h	Describes physical memory management zones (such as DMA, NORMAL, HIGHMEM)
struct pglist_data(pgdata)	include/linux/mmzone.h	Memory descriptor for a NUMA node, managing all zones under that node
mem_map[]	mm/memory.c	Global physical page array, whose address is determined during kernel initialization; each NUMA node also has its ownnode_mem_map
pte_t/ page table entry	arch/arm64/include/asm/pgtable-types.h	Page table entry types and page table operations are architecture-specific

struct mm_struct

// include/linux/mm_types.h
struct mm_struct {
	struct {
		struct vm_area_struct *mmap;		/* list of VMAs */
		struct rb_root mm_rb;
		u64 vmacache_seqnum;                   /* per-thread vmacache */
#ifdef CONFIG_MMU
		unsigned long (*get_unmapped_area) (struct file *filp,
				unsigned long addr, unsigned long len,
				unsigned long pgoff, unsigned long flags);
#endif
		unsigned long mmap_base;	/* base of mmap area */
		unsigned long mmap_legacy_base;	/* base of mmap area in bottom-up allocations */
#ifdef CONFIG_HAVE_ARCH_COMPAT_MMAP_BASES
		/* Base addresses for compatible mmap() */
		unsigned long mmap_compat_base;
		unsigned long mmap_compat_legacy_base;
#endif
		unsigned long task_size;	/* size of task vm space */
		unsigned long highest_vm_end;	/* highest vma end address */
		pgd_t * pgd;

#ifdef CONFIG_MEMBARRIER
		/**
		 * @membarrier_state: Flags controlling membarrier behavior.
		 *
		 * This field is close to @pgd to hopefully fit in the same
		 * cache-line, which needs to be touched by switch_mm().
		 */
		atomic_t membarrier_state;
#endif

		/**
		 * @mm_users: The number of users including userspace.
		 *
		 * Use mmget()/mmget_not_zero()/mmput() to modify. When this
		 * drops to 0 (i.e. when the task exits and there are no other
		 * temporary reference holders), we also release a reference on
		 * @mm_count (which may then free the &struct mm_struct if
		 * @mm_count also drops to 0).
		 */
		atomic_t mm_users;

		/**
		 * @mm_count: The number of references to &struct mm_struct
		 * (@mm_users count as 1).
		 *
		 * Use mmgrab()/mmdrop() to modify. When this drops to 0, the
		 * &struct mm_struct is freed.
		 */
		atomic_t mm_count;

#ifdef CONFIG_MMU
		atomic_long_t pgtables_bytes;	/* PTE page table pages */
#endif
		int map_count;			/* number of VMAs */

		spinlock_t page_table_lock; /* Protects page tables and some
					     * counters
					     */
		/*
		 * With some kernel config, the current mmap_lock's offset
		 * inside 'mm_struct' is at 0x120, which is very optimal, as
		 * its two hot fields 'count' and 'owner' sit in 2 different
		 * cachelines,  and when mmap_lock is highly contended, both
		 * of the 2 fields will be accessed frequently, current layout
		 * will help to reduce cache bouncing.
		 *
		 * So please be careful with adding new fields before
		 * mmap_lock, which can easily push the 2 fields into one
		 * cacheline.
		 */
		struct rw_semaphore mmap_lock;

		struct list_head mmlist; /* List of maybe swapped mm's.	These
					  * are globally strung together off
					  * init_mm.mmlist, and are protected
					  * by mmlist_lock
					  */


		unsigned long hiwater_rss; /* High-watermark of RSS usage */
		unsigned long hiwater_vm;  /* High-water virtual memory usage */

		unsigned long total_vm;	   /* Total pages mapped */
		unsigned long locked_vm;   /* Pages that have PG_mlocked set */
		atomic64_t    pinned_vm;   /* Refcount permanently increased */
		unsigned long data_vm;	   /* VM_WRITE & ~VM_SHARED & ~VM_STACK */
		unsigned long exec_vm;	   /* VM_EXEC & ~VM_WRITE & ~VM_STACK */
		unsigned long stack_vm;	   /* VM_STACK */
		unsigned long def_flags;

		/**
		 * @write_protect_seq: Locked when any thread is write
		 * protecting pages mapped by this mm to enforce a later COW,
		 * for instance during page table copying for fork().
		 */
		seqcount_t write_protect_seq;

		spinlock_t arg_lock; /* protect the below fields */

		unsigned long start_code, end_code, start_data, end_data;
		unsigned long start_brk, brk, start_stack;
		unsigned long arg_start, arg_end, env_start, env_end;

		unsigned long saved_auxv[AT_VECTOR_SIZE]; /* for /proc/PID/auxv */

		/*
		 * Special counters, in some configurations protected by the
		 * page_table_lock, in other configurations by being atomic.
		 */
		struct mm_rss_stat rss_stat;

		struct linux_binfmt *binfmt;

		/* Architecture-specific MM context */
		mm_context_t context;

		unsigned long flags; /* Must use atomic bitops to access */

		struct core_state *core_state; /* coredumping support */

#ifdef CONFIG_AIO
		spinlock_t			ioctx_lock;
		struct kioctx_table __rcu	*ioctx_table;
#endif
#ifdef CONFIG_MEMCG
		/*
		 * "owner" points to a task that is regarded as the canonical
		 * user/owner of this mm. All of the following must be true in
		 * order for it to be changed:
		 *
		 * current == mm->owner
		 * current->mm != mm
		 * new_owner->mm == mm
		 * new_owner->alloc_lock is held
		 */
		struct task_struct __rcu *owner;
#endif
		struct user_namespace *user_ns;

		/* store ref to file /proc/<pid>/exe symlink points to */
		struct file __rcu *exe_file;
#ifdef CONFIG_MMU_NOTIFIER
		struct mmu_notifier_subscriptions *notifier_subscriptions;
#endif
#if defined(CONFIG_TRANSPARENT_HUGEPAGE) && !USE_SPLIT_PMD_PTLOCKS
		pgtable_t pmd_huge_pte; /* protected by page_table_lock */
#endif
#ifdef CONFIG_NUMA_BALANCING
		/*
		 * numa_next_scan is the next time that the PTEs will be marked
		 * pte_numa. NUMA hinting faults will gather statistics and
		 * migrate pages to new nodes if necessary.
		 */
		unsigned long numa_next_scan;

		/* Restart point for scanning and setting pte_numa */
		unsigned long numa_scan_offset;

		/* numa_scan_seq prevents two threads setting pte_numa */
		int numa_scan_seq;
#endif
		/*
		 * An operation with batched TLB flushing is going on. Anything
		 * that can move process memory needs to flush the TLB when
		 * moving a PROT_NONE or PROT_NUMA mapped page.
		 */
		atomic_t tlb_flush_pending;
#ifdef CONFIG_ARCH_WANT_BATCHED_UNMAP_TLB_FLUSH
		/* See flush_tlb_batched_pending() */
		bool tlb_flush_batched;
#endif
		struct uprobes_state uprobes_state;
#ifdef CONFIG_HUGETLB_PAGE
		atomic_long_t hugetlb_usage;
#endif
		struct work_struct async_put_work;

#ifdef CONFIG_IOMMU_SUPPORT
		u32 pasid;
#endif
	} __randomize_layout;

	/*
	 * The mm_cpumask needs to be at the end of mm_struct, because it
	 * is dynamically sized based on nr_cpu_ids.
	 */
	unsigned long cpu_bitmap[];
};

struct vm_area_struct

// include/linux/mm_types.h
/*
 * This struct describes a virtual memory area. There is one of these
 * per VM-area/task. A VM area is any part of the process virtual memory
 * space that has a special rule for the page-fault handlers (ie a shared
 * library, the executable area etc).
 */
struct vm_area_struct {
	/* The first cache line has the info for VMA tree walking. */

	unsigned long vm_start;		/* Our start address within vm_mm. */
	unsigned long vm_end;		/* The first byte after our end address
					   within vm_mm. */

	/* linked list of VM areas per task, sorted by address */
	struct vm_area_struct *vm_next, *vm_prev;

	struct rb_node vm_rb;

	/*
	 * Largest free memory gap in bytes to the left of this VMA.
	 * Either between this VMA and vma->vm_prev, or between one of the
	 * VMAs below us in the VMA rbtree and its ->vm_prev. This helps
	 * get_unmapped_area find a free area of the right size.
	 */
	unsigned long rb_subtree_gap;

	/* Second cache line starts here. */

	struct mm_struct *vm_mm;	/* The address space we belong to. */

	/*
	 * Access permissions of this VMA.
	 * See vmf_insert_mixed_prot() for discussion.
	 */
	pgprot_t vm_page_prot;
	unsigned long vm_flags;		/* Flags, see mm.h. */

	/*
	 * For areas with an address space and backing store,
	 * linkage into the address_space->i_mmap interval tree.
	 */
	struct {
		struct rb_node rb;
		unsigned long rb_subtree_last;
	} shared;

	/*
	 * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
	 * list, after a COW of one of the file pages.	A MAP_SHARED vma
	 * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
	 * or brk vma (with NULL file) can only be in an anon_vma list.
	 */
	struct list_head anon_vma_chain; /* Serialized by mmap_lock &
					  * page_table_lock */
	struct anon_vma *anon_vma;	/* Serialized by page_table_lock */

	/* Function pointers to deal with this struct. */
	const struct vm_operations_struct *vm_ops;

	/* Information about our backing store: */
	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
					   units */
	struct file * vm_file;		/* File we map to (can be NULL). */
	void * vm_private_data;		/* was vm_pte (shared mem) */

#ifdef CONFIG_SWAP
	atomic_long_t swap_readahead_info;
#endif
#ifndef CONFIG_MMU
	struct vm_region *vm_region;	/* NOMMU mapping region */
#endif
#ifdef CONFIG_NUMA
	struct mempolicy *vm_policy;	/* NUMA policy for the VMA */
#endif
	struct vm_userfaultfd_ctx vm_userfaultfd_ctx;
} __randomize_layout;

struct page

// include/linux/mm_types.h

/*
 * Each physical page in the system has a struct page associated with
 * it to keep track of whatever it is we are using the page for at the
 * moment. Note that we have no way to track which tasks are using
 * a page, though if it is a pagecache page, rmap structures can tell us
 * who is mapping it.
 *
 * If you allocate the page using alloc_pages(), you can use some of the
 * space in struct page for your own purposes.  The five words in the main
 * union are available, except for bit 0 of the first word which must be
 * kept clear.  Many users use this word to store a pointer to an object
 * which is guaranteed to be aligned.  If you use the same storage as
 * page->mapping, you must restore it to NULL before freeing the page.
 *
 * If your page will not be mapped to userspace, you can also use the four
 * bytes in the mapcount union, but you must call page_mapcount_reset()
 * before freeing it.
 *
 * If you want to use the refcount field, it must be used in such a way
 * that other CPUs temporarily incrementing and then decrementing the
 * refcount does not cause problems.  On receiving the page from
 * alloc_pages(), the refcount will be positive.
 *
 * If you allocate pages of order > 0, you can use some of the fields
 * in each subpage, but you may need to restore some of their values
 * afterwards.
 *
 * SLUB uses cmpxchg_double() to atomically update its freelist and
 * counters.  That requires that freelist & counters be adjacent and
 * double-word aligned.  We align all struct pages to double-word
 * boundaries, and ensure that 'freelist' is aligned within the
 * struct.
 */
#ifdef CONFIG_HAVE_ALIGNED_STRUCT_PAGE
#define _struct_page_alignment	__aligned(2 * sizeof(unsigned long))
#else
#define _struct_page_alignment
#endif

struct page {
	unsigned long flags;		/* Atomic flags, some possibly
					 * updated asynchronously */
	/*
	 * Five words (20/40 bytes) are available in this union.
	 * WARNING: bit 0 of the first word is used for PageTail(). That
	 * means the other users of this union MUST NOT use the bit to
	 * avoid collision and false-positive PageTail().
	 */
	union {
		struct {	/* Page cache and anonymous pages */
			/**
			 * @lru: Pageout list, eg. active_list protected by
			 * lruvec->lru_lock.  Sometimes used as a generic list
			 * by the page owner.
			 */
			struct list_head lru;
			/* See page-flags.h for PAGE_MAPPING_FLAGS */
			struct address_space *mapping;
			pgoff_t index;		/* Our offset within mapping. */
			/**
			 * @private: Mapping-private opaque data.
			 * Usually used for buffer_heads if PagePrivate.
			 * Used for swp_entry_t if PageSwapCache.
			 * Indicates order in the buddy system if PageBuddy.
			 */
			unsigned long private;
		};
		struct {	/* page_pool used by netstack */
			/**
			 * @pp_magic: magic value to avoid recycling non
			 * page_pool allocated pages.
			 */
			unsigned long pp_magic;
			struct page_pool *pp;
			unsigned long _pp_mapping_pad;
			unsigned long dma_addr;
			union {
				/**
				 * dma_addr_upper: might require a 64-bit
				 * value on 32-bit architectures.
				 */
				unsigned long dma_addr_upper;
				/**
				 * For frag page support, not supported in
				 * 32-bit architectures with 64-bit DMA.
				 */
				atomic_long_t pp_frag_count;
			};
		};
		struct {	/* slab, slob and slub */
			union {
				struct list_head slab_list;
				struct {	/* Partial pages */
					struct page *next;
#ifdef CONFIG_64BIT
					int pages;	/* Nr of pages left */
					int pobjects;	/* Approximate count */
#else
					short int pages;
					short int pobjects;
#endif
				};
			};
			struct kmem_cache *slab_cache; /* not slob */
			/* Double-word boundary */
			void *freelist;		/* first free object */
			union {
				void *s_mem;	/* slab: first object */
				unsigned long counters;		/* SLUB */
				struct {			/* SLUB */
					unsigned inuse:16;
					unsigned objects:15;
					unsigned frozen:1;
				};
			};
		};
		struct {	/* Tail pages of compound page */
			unsigned long compound_head;	/* Bit zero is set */

			/* First tail page only */
			unsigned char compound_dtor;
			unsigned char compound_order;
			atomic_t compound_mapcount;
			unsigned int compound_nr; /* 1 << compound_order */
		};
		struct {	/* Second tail page of compound page */
			unsigned long _compound_pad_1;	/* compound_head */
			atomic_t hpage_pinned_refcount;
			/* For both global and memcg */
			struct list_head deferred_list;
		};
		struct {	/* Page table pages */
			unsigned long _pt_pad_1;	/* compound_head */
			pgtable_t pmd_huge_pte; /* protected by page->ptl */
			unsigned long _pt_pad_2;	/* mapping */
			union {
				struct mm_struct *pt_mm; /* x86 pgds only */
				atomic_t pt_frag_refcount; /* powerpc */
			};
#if ALLOC_SPLIT_PTLOCKS
			spinlock_t *ptl;
#else
			spinlock_t ptl;
#endif
		};
		struct {	/* ZONE_DEVICE pages */
			/** @pgmap: Points to the hosting device page map. */
			struct dev_pagemap *pgmap;
			void *zone_device_data;
			/*
			 * ZONE_DEVICE private pages are counted as being
			 * mapped so the next 3 words hold the mapping, index,
			 * and private fields from the source anonymous or
			 * page cache page while the page is migrated to device
			 * private memory.
			 * ZONE_DEVICE MEMORY_DEVICE_FS_DAX pages also
			 * use the mapping, index, and private fields when
			 * pmem backed DAX files are mapped.
			 */
		};

		/** @rcu_head: You can use this to free a page by RCU. */
		struct rcu_head rcu_head;
	};

	union {		/* This union is 4 bytes in size. */
		/*
		 * If the page can be mapped to userspace, encodes the number
		 * of times this page is referenced by a page table.
		 */
		atomic_t _mapcount;

		/*
		 * If the page is neither PageSlab nor mappable to userspace,
		 * the value stored here may help determine what this page
		 * is used for.  See page-flags.h for a list of page types
		 * which are currently stored here.
		 */
		unsigned int page_type;

		unsigned int active;		/* SLAB */
		int units;			/* SLOB */
	};

	/* Usage count. *DO NOT USE DIRECTLY*. See page_ref.h */
	atomic_t _refcount;

#ifdef CONFIG_MEMCG
	unsigned long memcg_data;
#endif

	/*
	 * On machines where all RAM is mapped into kernel address space,
	 * we can simply calculate the virtual address. On machines with
	 * highmem some memory is mapped into kernel virtual memory
	 * dynamically, so we need a place to store that address.
	 * Note that this field could be 16 bits on x86 ... ;)
	 *
	 * Architectures with slow multiplication can define
	 * WANT_PAGE_VIRTUAL in asm/page.h
	 */
#if defined(WANT_PAGE_VIRTUAL)
	void *virtual;			/* Kernel virtual address (NULL if
					   not kmapped, ie. highmem) */
#endif /* WANT_PAGE_VIRTUAL */

#ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
	int _last_cpupid;
#endif
} _struct_page_alignment;

struct zone

// include/linux/mmzone.h
struct zone {
	/* Read-mostly fields */

	/* zone watermarks, access with *_wmark_pages(zone) macros */
	unsigned long _watermark[NR_WMARK];
	unsigned long watermark_boost;

	unsigned long nr_reserved_highatomic;

	/*
	 * We don't know if the memory that we're going to allocate will be
	 * freeable or/and it will be released eventually, so to avoid totally
	 * wasting several GB of ram we must reserve some of the lower zone
	 * memory (otherwise we risk to run OOM on the lower zones despite
	 * there being tons of freeable ram on the higher zones).  This array is
	 * recalculated at runtime if the sysctl_lowmem_reserve_ratio sysctl
	 * changes.
	 */
	long lowmem_reserve[MAX_NR_ZONES];

#ifdef CONFIG_NUMA
	int node;
#endif
	struct pglist_data	*zone_pgdat;
	struct per_cpu_pages	__percpu *per_cpu_pageset;
	struct per_cpu_zonestat	__percpu *per_cpu_zonestats;
	/*
	 * the high and batch values are copied to individual pagesets for
	 * faster access
	 */
	int pageset_high;
	int pageset_batch;

#ifndef CONFIG_SPARSEMEM
	/*
	 * Flags for a pageblock_nr_pages block. See pageblock-flags.h.
	 * In SPARSEMEM, this map is stored in struct mem_section
	 */
	unsigned long		*pageblock_flags;
#endif /* CONFIG_SPARSEMEM */

	/* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
	unsigned long		zone_start_pfn;

	/*
	 * spanned_pages is the total pages spanned by the zone, including
	 * holes, which is calculated as:
	 * 	spanned_pages = zone_end_pfn - zone_start_pfn;
	 *
	 * present_pages is physical pages existing within the zone, which
	 * is calculated as:
	 *	present_pages = spanned_pages - absent_pages(pages in holes);
	 *
	 * present_early_pages is present pages existing within the zone
	 * located on memory available since early boot, excluding hotplugged
	 * memory.
	 *
	 * managed_pages is present pages managed by the buddy system, which
	 * is calculated as (reserved_pages includes pages allocated by the
	 * bootmem allocator):
	 *	managed_pages = present_pages - reserved_pages;
	 *
	 * cma pages is present pages that are assigned for CMA use
	 * (MIGRATE_CMA).
	 *
	 * So present_pages may be used by memory hotplug or memory power
	 * management logic to figure out unmanaged pages by checking
	 * (present_pages - managed_pages). And managed_pages should be used
	 * by page allocator and vm scanner to calculate all kinds of watermarks
	 * and thresholds.
	 *
	 * Locking rules:
	 *
	 * zone_start_pfn and spanned_pages are protected by span_seqlock.
	 * It is a seqlock because it has to be read outside of zone->lock,
	 * and it is done in the main allocator path.  But, it is written
	 * quite infrequently.
	 *
	 * The span_seq lock is declared along with zone->lock because it is
	 * frequently read in proximity to zone->lock.  It's good to
	 * give them a chance of being in the same cacheline.
	 *
	 * Write access to present_pages at runtime should be protected by
	 * mem_hotplug_begin/end(). Any reader who can't tolerant drift of
	 * present_pages should get_online_mems() to get a stable value.
	 */
	atomic_long_t		managed_pages;
	unsigned long		spanned_pages;
	unsigned long		present_pages;
#if defined(CONFIG_MEMORY_HOTPLUG)
	unsigned long		present_early_pages;
#endif
#ifdef CONFIG_CMA
	unsigned long		cma_pages;
#endif

	const char		*name;

#ifdef CONFIG_MEMORY_ISOLATION
	/*
	 * Number of isolated pageblock. It is used to solve incorrect
	 * freepage counting problem due to racy retrieving migratetype
	 * of pageblock. Protected by zone->lock.
	 */
	unsigned long		nr_isolate_pageblock;
#endif

#ifdef CONFIG_MEMORY_HOTPLUG
	/* see spanned/present_pages for more description */
	seqlock_t		span_seqlock;
#endif

	int initialized;

	/* Write-intensive fields used from the page allocator */
	ZONE_PADDING(_pad1_)

	/* free areas of different sizes */
	struct free_area	free_area[MAX_ORDER];

	/* zone flags, see below */
	unsigned long		flags;

	/* Primarily protects free_area */
	spinlock_t		lock;

	/* Write-intensive fields used by compaction and vmstats. */
	ZONE_PADDING(_pad2_)

	/*
	 * When free pages are below this point, additional steps are taken
	 * when reading the number of free pages to avoid per-cpu counter
	 * drift allowing watermarks to be breached
	 */
	unsigned long percpu_drift_mark;

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
	/* pfn where compaction free scanner should start */
	unsigned long		compact_cached_free_pfn;
	/* pfn where compaction migration scanner should start */
	unsigned long		compact_cached_migrate_pfn[ASYNC_AND_SYNC];
	unsigned long		compact_init_migrate_pfn;
	unsigned long		compact_init_free_pfn;
#endif

#ifdef CONFIG_COMPACTION
	/*
	 * On compaction failure, 1<<compact_defer_shift compactions
	 * are skipped before trying again. The number attempted since
	 * last failure is tracked with compact_considered.
	 * compact_order_failed is the minimum compaction failed order.
	 */
	unsigned int		compact_considered;
	unsigned int		compact_defer_shift;
	int			compact_order_failed;
#endif

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
	/* Set to true when the PG_migrate_skip bits should be cleared */
	bool			compact_blockskip_flush;
#endif

	bool			contiguous;

	ZONE_PADDING(_pad3_)
	/* Zone statistics */
	atomic_long_t		vm_stat[NR_VM_ZONE_STAT_ITEMS];
	atomic_long_t		vm_numa_event[NR_VM_NUMA_EVENT_ITEMS];
} ____cacheline_internodealigned_in_smp;

struct pglist_data

// include/linux/mmzone.h
/*
 * On NUMA machines, each NUMA node would have a pg_data_t to describe
 * it's memory layout. On UMA machines there is a single pglist_data which
 * describes the whole memory.
 *
 * Memory statistics and page replacement data structures are maintained on a
 * per-zone basis.
 */
typedef struct pglist_data {
	/*
	 * node_zones contains just the zones for THIS node. Not all of the
	 * zones may be populated, but it is the full list. It is referenced by
	 * this node's node_zonelists as well as other node's node_zonelists.
	 */
	struct zone node_zones[MAX_NR_ZONES];

	/*
	 * node_zonelists contains references to all zones in all nodes.
	 * Generally the first zones will be references to this node's
	 * node_zones.
	 */
	struct zonelist node_zonelists[MAX_ZONELISTS];

	int nr_zones; /* number of populated zones in this node */
#ifdef CONFIG_FLATMEM	/* means !SPARSEMEM */
	struct page *node_mem_map;
#ifdef CONFIG_PAGE_EXTENSION
	struct page_ext *node_page_ext;
#endif
#endif
#if defined(CONFIG_MEMORY_HOTPLUG) || defined(CONFIG_DEFERRED_STRUCT_PAGE_INIT)
	/*
	 * Must be held any time you expect node_start_pfn,
	 * node_present_pages, node_spanned_pages or nr_zones to stay constant.
	 * Also synchronizes pgdat->first_deferred_pfn during deferred page
	 * init.
	 *
	 * pgdat_resize_lock() and pgdat_resize_unlock() are provided to
	 * manipulate node_size_lock without checking for CONFIG_MEMORY_HOTPLUG
	 * or CONFIG_DEFERRED_STRUCT_PAGE_INIT.
	 *
	 * Nests above zone->lock and zone->span_seqlock
	 */
	spinlock_t node_size_lock;
#endif
	unsigned long node_start_pfn;
	unsigned long node_present_pages; /* total number of physical pages */
	unsigned long node_spanned_pages; /* total size of physical page
					     range, including holes */
	int node_id;
	wait_queue_head_t kswapd_wait;
	wait_queue_head_t pfmemalloc_wait;
	struct task_struct *kswapd;	/* Protected by
					   mem_hotplug_begin/end() */
	int kswapd_order;
	enum zone_type kswapd_highest_zoneidx;

	int kswapd_failures;		/* Number of 'reclaimed == 0' runs */

#ifdef CONFIG_COMPACTION
	int kcompactd_max_order;
	enum zone_type kcompactd_highest_zoneidx;
	wait_queue_head_t kcompactd_wait;
	struct task_struct *kcompactd;
	bool proactive_compact_trigger;
#endif
	/*
	 * This is a per-node reserve of pages that are not available
	 * to userspace allocations.
	 */
	unsigned long		totalreserve_pages;

#ifdef CONFIG_NUMA
	/*
	 * node reclaim becomes active if more unmapped pages exist.
	 */
	unsigned long		min_unmapped_pages;
	unsigned long		min_slab_pages;
#endif /* CONFIG_NUMA */

	/* Write-intensive fields used by page reclaim */
	ZONE_PADDING(_pad1_)

#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
	/*
	 * If memory initialisation on large machines is deferred then this
	 * is the first PFN that needs to be initialised.
	 */
	unsigned long first_deferred_pfn;
#endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */

#ifdef CONFIG_TRANSPARENT_HUGEPAGE
	struct deferred_split deferred_split_queue;
#endif

	/* Fields commonly accessed by the page reclaim scanner */

	/*
	 * NOTE: THIS IS UNUSED IF MEMCG IS ENABLED.
	 *
	 * Use mem_cgroup_lruvec() to look up lruvecs.
	 */
	struct lruvec		__lruvec;

	unsigned long		flags;

	ZONE_PADDING(_pad2_)

	/* Per-node vmstats */
	struct per_cpu_nodestat __percpu *per_cpu_nodestats;
	atomic_long_t		vm_stat[NR_VM_NODE_STAT_ITEMS];
} pg_data_t;

mem_map

// mm/memory.c
#ifndef CONFIG_NUMA
unsigned long max_mapnr;
EXPORT_SYMBOL(max_mapnr);

struct page *mem_map;
EXPORT_SYMBOL(mem_map);
#endif

/*
 * A number of key systems in x86 including ioremap() rely on the assumption
 * that high_memory defines the upper bound on direct map memory, then end
 * of ZONE_NORMAL.  Under CONFIG_DISCONTIG this means that max_low_pfn and
 * highstart_pfn must be the same; there must be no gap between ZONE_NORMAL
 * and ZONE_HIGHMEM.
 */
void *high_memory;
EXPORT_SYMBOL(high_memory);

Linux physical memory initialization

1. When the system starts, how does the ARM Linux kernel know how much memory space the system has?
2. In a 32-bit Linux kernel, the ratio of user space to kernel space is usually 3:1. Can it be changed to 2:2?
3. How are physical memory pages added to the buddy system? Are they added one page at a time or in powers of 2?

Introduction to DDR

• Bank
• row
• column

DDR Bank

DDR

memory node

Memory storage model:

• UMA (uniform memory access) Uniform Memory Access
• NUMA (non-uniform memory access) Non-Uniform Memory Access

Use struct pglist_data to describe

Memory management area ZONE

• Why do we need zones?
• zone_type
• struct zone

Page table mapping

arm32

• Support four-level mapping
  • Global directory entry PGD （Page Global Directory）
  • Upper directory entry PUD （Page Upper Directory）
  • Middle directory entry PMD （Page Middle Directory）
  • Page table entry (Page Table）

The Linux kernel was originally based on x86, so the above term is commonly used in kernel code to refer to first-level page tables, second-level page tables, and so on.

Translation from virtual address to physical address

Translation from virtual address to physical address

First-level page table entry

First-level page table entry

• Fault
  • Invalid entry
• Page table
  • First-level page table entry
  • bit[0~1]: used to indicate whether this page table entry is a first-level page table entry or a section mapping entry.
  • PXN: whether PL1 can execute this code; 0 means executable, 1 means non-executable.
  • NS: non-security bit, indicating the security extension bit.
  • Domain: indicates the domain it belongs to; Linux only uses 3 domains.
  • bits[31:10] Page table base address, pointing to the base address of the second-level page table.

Some Linux macros for page table definitions.

• Section
  • Section table entry for section mapping

Second-level page table entry

Second-level page table entry

• bit0 Execute-never flag: 1 means execute prohibited, 0 means executable
• bit1: distinguishes large pages from small pages
• C/B bit: memory region attributes
• TEX[2:0]: memory region attributes
• AP[1:0]: access permissions
• S: whether it is shareable
• nG: used for TLB

arm64

ARMv8-AArchitecture

• Supports 48 address lines
• Access region is divided into two parts (kernel area and user space area), each region 256TB
• Supports 4KB, 16KB, and 64KB pages, and supports 3-level or 4-level mapping

ARMv8 has two page table base addresses, one for user area and one for kernel area, selected by bit63

4KB pages + 4-level mapping

4KB page 4-level mapping.drawio

TODO

1. Summarize macros related to page table operations
2. start_kernel()->setup_arch()->paging_init()->map_lowmem()

static void __init create_mapping(struct map_desc *md)

Create page table mapping for kernel image region, create page table mapping for linear mapping region

Study how to create kernel page table mappings

3. int remap_pfn_range() Study how to create page table mappings based on vma, virtual address, and physical address pfn
4. static int do_anonymous_page Study this page fault handler to observe: given vma, virtual address vaddr, and page table entries, how to set up the user process page table

Comparison of x86 and ARM32 page tables

ARM32 implementation: parallel page tables

Two sets of page tables, one to accommodate hardware, one to accommodate the Linux kernel

ARM32 implementation: parallel page tables

Page allocation mechanism

Buddy system

• The buddy algorithm allocates memory blocks in sizes that are powers of 2; these memory blocks are called buddies.
• What is a buddy?
  • Two blocks have the same size.
  • Two blocks have contiguous addresses.
  • The two blocks must be split from the same larger block.

Buddy system

Migration type

• To solve the fragmentation problem, migration types were introduced into the buddy system.
  • MIGRATE_UNMOVABLE: has a fixed position in memory and cannot be moved arbitrarily, e.g., memory allocated by the kernel.
  • MIGRATE_MOVABLE: can be moved arbitrarily; memory allocated by user-space applications.
  • MIGRATE_RECLAIMABLE: cannot be moved but can be deleted and reclaimed, e.g., file mappings.
• Generation of memory fragmentation

Generation of memory fragmentation

page3 is used by a function allocated by the kernel itself, such as alloc._page(GPF_KERNEL), so it belongs to an unmovable page. Although the other pages are free, page0 to page7 cannot be combined into a large memory block.

Page allocation and allocation mask

Core page allocation function

struct page *alloc_pages(gfp_t gfp_mask,unsigned int order)
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
alloc_page(gfp_mask)

gfp_maskFlags

gfp_mask flag bits

gfp_mask flag bits

• The page allocator is designed based on zones, so for page allocation it is necessary to determine which zones can be used for this allocation. The system will preferentially use ZONE._NORMAL，ZONE_HIGHMEM as a last resort (32-bit systems only)
• When allocating pages, it is also necessary to know from which migration type the current allocation should obtain memory.

zone watermarks

zone watermarks

Defined in the Linux kernel:

enum zone_watermarks {
	WMARK_MIN,
	WMARK_LOW,
	WMARK_HIGH,
	NR_WMARK
};

Page release function

void free_pages(unsigned long addr,unsigned int order)
__free_page(page)
 free_page(addr)

per-CPU high-speed page cache

• The kernel frequently requests and releases individual page frames, such as network card drivers, etc.

• When the page allocator allocates and releases pages, it needs to acquire a lock: zone->lock

  • To improve the efficiency of allocating and releasing individual page frames, the kernel establishes a per-CPU high-speed page cache pool.
  • It stores a number of pre-allocated page frames.

• When a single page frame is requested, the page frame is taken directly from the local CPU’s page frame cache pool.

  • No lock acquisition is required.
  • No complex page frame allocation operations are required.

(This reflects the advantage of pre-establishing a cache pool, and each CPU has an independent cache.)

per-CPU data structure

• In zone, there is a member field ‘pageset’ that points to the per-CPU cache.
• struct per_cpu_pages data structure

struct per_cpu_pages {
	int count;		/* number of pages in the list */
	int high;		/* high watermark, emptying needed */
	int batch;		/* chunk size for buddy add/remove */

	/* Lists of pages, one per migrate type stored on the pcp-lists */
	struct list_head lists[MIGRATE_PCPTYPES];
};

slab mechanism

What to do when the kernel needs to allocate small chunks of memory of a few dozen bytes?

slab

/*
 * Definitions unique to the original Linux SLAB allocator.
 */

struct kmem_cache {
	struct array_cache __percpu *cpu_cache;

/* 1) Cache tunables. Protected by slab_mutex */
	unsigned int batchcount;
	unsigned int limit;
	unsigned int shared;

	unsigned int size;
	struct reciprocal_value reciprocal_buffer_size;
/* 2) touched by every alloc & free from the backend */

	unsigned int flags;		/* constant flags */
	unsigned int num;		/* # of objs per slab */

/* 3) cache_grow/shrink */
	/* order of pgs per slab (2^n) */
	unsigned int gfporder;

	/* force GFP flags, e.g. GFP_DMA */
	gfp_t allocflags;

	size_t colour;			/* cache colouring range */
	unsigned int colour_off;	/* colour offset */
	struct kmem_cache *freelist_cache;
	unsigned int freelist_size;

	/* constructor func */
	void (*ctor)(void *obj);

/* 4) cache creation/removal */
	const char *name;
	struct list_head list;
	int refcount;
	int object_size;
	int align;

/* 5) statistics */
#ifdef CONFIG_DEBUG_SLAB
	unsigned long num_active;
	unsigned long num_allocations;
	unsigned long high_mark;
	unsigned long grown;
	unsigned long reaped;
	unsigned long errors;
	unsigned long max_freeable;
	unsigned long node_allocs;
	unsigned long node_frees;
	unsigned long node_overflow;
	atomic_t allochit;
	atomic_t allocmiss;
	atomic_t freehit;
	atomic_t freemiss;

	/*
	 * If debugging is enabled, then the allocator can add additional
	 * fields and/or padding to every object. size contains the total
	 * object size including these internal fields, the following two
	 * variables contain the offset to the user object and its size.
	 */
	int obj_offset;
#endif /* CONFIG_DEBUG_SLAB */
#ifdef CONFIG_MEMCG_KMEM
	struct memcg_cache_params memcg_params;
#endif

	struct kmem_cache_node *node[MAX_NUMNODES];
};

• array_cache: This refers to the per-CPU object cache pool, one for each CPU.
  • Used to establish a local object cache pool, one per CPU, which is beneficial for:
    • Allowing objects to use the cache on the same CPU as much as possible, which helps improve efficiency.
    • No additional spinlock is needed, avoiding lock contention.

/*
 * struct array_cache
 *
 * Purpose:
 * - LIFO ordering, to hand out cache-warm objects from _alloc
 * - reduce the number of linked list operations
 * - reduce spinlock operations
 *
 * The limit is stored in the per-cpu structure to reduce the data cache
 * footprint.
 *
 */
struct array_cache {
	unsigned int avail;
	unsigned int limit;
	unsigned int batchcount;
	unsigned int touched;
    // entry is used to store free object entities.
	void *entry[];	/*
			 * Must have this definition in here for the proper
			 * alignment of array_cache. Also simplifies accessing
			 * the entries.
			 *
			 * Entries should not be directly dereferenced as
			 * entries belonging to slabs marked pfmemalloc will
			 * have the lower bits set SLAB_OBJ_PFMEMALLOC
			 */
};


#ifndef CONFIG_SLOB
/*
 * The slab lists for all objects.
 */
struct kmem_cache_node {
	spinlock_t list_lock;

#ifdef CONFIG_SLAB
	struct list_head slabs_partial;	/* partial list first, better asm code */
	struct list_head slabs_full;
	struct list_head slabs_free;
	unsigned long free_objects;
	unsigned int free_limit;
	unsigned int colour_next;	/* Per-node cache coloring */
	struct array_cache *shared;	/* shared per node */
	struct alien_cache **alien;	/* on other nodes */
	unsigned long next_reap;	/* updated without locking */
	int free_touched;		/* updated without locking */
#endif

#ifdef CONFIG_SLUB
	unsigned long nr_partial;
	struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
	atomic_long_t nr_slabs;
	atomic_long_t total_objects;
	struct list_head full;
#endif
#endif

};

• batchcount: Indicates that when the local object cache pool is empty, batchcount objects need to be fetched from the shared cache pool into the local cache pool.
• limit: When the number of free objects in the local object cache pool exceeds limit, some objects need to be released.
• shared: Used for multi-core systems.
• size: Indicates the length of the object.
• flags: object allocation mask
• num: number of objects in a slab
• gfporder: a slab occupies 2^order physical pages
• colour: number of cache lines used for colouring (cache colouring) in a slab
• freelist_size: each object occupies 1 byte to store the freelist
• name: name of the descriptor
• object_size: actual size of the object
• align: alignment length

Composition of a slab

Composition of a slab

slab operation mechanism

slab operation mechanism

slab reclamation

• If a slab descriptor has many free objects, should the system reclaim some free cached objects to release memory and return it to the system?
  • Using kmem_cache_When free releases an object, if the number of free objects in the local and shared object buffer pools, ac->avail, is greater than or equal to the pool limit ac->limit, the system actively releases batchcount objects.
  • The slab system also registers a timer to periodically scan all slab descriptors and reclaim some free objects.

kmalloc function

• The core of the kmalloc() function is the slab mechanism.
• Create multiple slab descriptors according to the 2^order of memory blocks.
  • void *kmalloc(size_t size, gfp_t flags)
  • void kfree(const void*)

vmalloc

Virtual address space

vmalloc area

vmalloc interface function

void *vmalloc(unsigned long size);
void vfree(const void *addr);

The vmalloc allocation process can sleep, so it cannot be used in interrupt context.

VMA operation

VMA operation

struct vm_area_struct {
	/* The first cache line has the info for VMA tree walking. */

	unsigned long vm_start;		/* Our start address within vm_mm. */
	unsigned long vm_end;		/* The first byte after our end address
					   within vm_mm. */

	/* linked list of VM areas per task, sorted by address */
	struct vm_area_struct *vm_next, *vm_prev;

	struct rb_node vm_rb;

	/*
	 * Largest free memory gap in bytes to the left of this VMA.
	 * Either between this VMA and vma->vm_prev, or between one of the
	 * VMAs below us in the VMA rbtree and its ->vm_prev. This helps
	 * get_unmapped_area find a free area of the right size.
	 */
	unsigned long rb_subtree_gap;

	/* Second cache line starts here. */

	struct mm_struct *vm_mm;	/* The address space we belong to. */
	pgprot_t vm_page_prot;		/* Access permissions of this VMA. */
	unsigned long vm_flags;		/* Flags, see mm.h. */

	/*
	 * For areas with an address space and backing store,
	 * linkage into the address_space->i_mmap interval tree.
	 */
	struct {
		struct rb_node rb;
		unsigned long rb_subtree_last;
	} shared;

	/*
	 * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
	 * list, after a COW of one of the file pages.	A MAP_SHARED vma
	 * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
	 * or brk vma (with NULL file) can only be in an anon_vma list.
	 */
	struct list_head anon_vma_chain; /* Serialized by mmap_sem &
					  * page_table_lock */
	struct anon_vma *anon_vma;	/* Serialized by page_table_lock */

	/* Function pointers to deal with this struct. */
	const struct vm_operations_struct *vm_ops;

	/* Information about our backing store: */
	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
					   units, *not* PAGE_CACHE_SIZE */
	struct file * vm_file;		/* File we map to (can be NULL). */
	void * vm_private_data;		/* was vm_pte (shared mem) */

#ifndef CONFIG_MMU
	struct vm_region *vm_region;	/* NOMMU mapping region */
#endif
#ifdef CONFIG_NUMA
	struct mempolicy *vm_policy;	/* NUMA policy for the VMA */
#endif
};

VMA management

struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr);
struct vm_area_struct * find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr);
struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
					     struct vm_area_struct **pprev);

find_vma

int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
struct vm_area_struct *vma_merge(struct mm_struct *mm,
			struct vm_area_struct *prev, unsigned long addr,
			unsigned long end, unsigned long vm_flags,
			struct anon_vma *anon_vma, struct file *file,
			pgoff_t pgoff, struct mempolicy *policy)

vma_merge

malloc

• malloc, whose full name is memory allocation, is called dynamic allocation in Chinese, and is an API mainly used in user space to allocate virtual memory.

• calloc automatically initializes the allocated memory space to 0 after dynamic allocation, while malloc does not initialize it, and the data inside is random garbage data.

• realloc changes the size of a previously allocated memory block, which can enlarge or shrink a block of memory.

• malloc is an API wrapped by the C library, and ultimately calls the brk system call.

• glibc maintains a small warehouse. The implementation of the malloc function maintains a local small warehouse for the user process. When the process needs more memory, it requests goods from this small warehouse. When the small warehouse’s stock is insufficient, it wholesales from the kernel through the agent brk.

• If malloc() is imagined as retail, then brk is the agent.

• brk system call

SYSCALL_DEFINE1(brk, unsigned long, brk)

The place where malloc/brk allocates virtual memory

malloc call

• The figure above finds a free space in the heap area of the process’s address space, then creates a VMA, and then returns.
• On-demand allocation (on-demand page)
  • The memory allocated by malloc may not be used for a long time, so it is actually not a good idea to allocate physical space immediately when a process allocates memory.
  • Solution: page fault. When the process really needs to access these virtual pages, only then does it have to create physical memory.

mlock system call

• The mlock system call allows a program to lock part or all of its address space in physical memory. Calling mlock immediately allocates physical memory for virtual memory.
• This prevents Linux from swapping this memory page to swap space.
• In the brk function implementation, when finally returning the virtual memory address, it checks a variable VM._LOCKED, this VM_LOCKED is usually set from the mlock system call.
  • If so, it needs to call mm_populate() to immediately allocate physical memory and establish the mapping.
  • The general case is: the work of allocating physical pages is deferred until the user process needs to access these virtual pages. Only when a page fault occurs is physical memory allocated and a mapping relationship established with virtual addresses.

mlock system call

get_user_pages() function

• A very important interface function for allocating physical memory. Many drivers use this API to allocate physical memory for user-mode programs.

get_user_pages function

follow_page() function

• Returns the struct page data structure of normal mapping pages already mapped in the VMA of the user process address space.

vm_normal_page() function

• This function divides pages into two camps: normal pages and special pages.
  • Normal pages usually refer to normally mapped pages, such as anonymous pages, page cache, and shared memory pages.
  • Special pages usually refer to abnormally mapped pages. These pages are not intended to participate in memory management’s reclaim or merge functionality, for example, pages mapped with the following characteristics:
    • VM_IO: Map memory for I/O devices
    • VM_PEN_MAP: Pure PFN mapping
    • VM_MIXEDMAP: Fixed mapping

Summary

• The malloc function actually allocates process address space for user space. In kernel terms, it allocates a VMA, which is equivalent to an empty cardboard box. So when do you put things into the box? Two ways:
  • One is to put things into the box only when the box is actually used.
  • The other is to put what you want into the box at the time of allocation.
• If two processes allocate the same virtual address via malloc, will they conflict?
  • Each user process has its own page table. Each process has an mm_struct data structure, which contains a page table belonging to the process itself, and a red-black tree and linked list for managing VMAs.
  • Even if process A and process B get the same virtual address returned by malloc, they are actually two different VMAs, managed by two different sets of page tables.

malloc

mmap

#include <sys/mman.h>
void *mmap(void *addr,size_t length,int prot,int flags,int fd,off_t offset);
int munmap(void *addr,size_t length);

• addr: Used to specify the starting address mapped into the process address space. For application portability, it is usually set to NULL, letting the kernel choose an appropriate address.
• length: Indicates the size of the mapping into the process address space.
• prot: Used to set the read/write attributes of the memory mapping region.
  • PROT_EXEC: Indicates that the mapped pages are executable.
  • PROT_READ: Indicates that the mapped pages are readable.
  • PROT_WRITE: Indicates that the mapped pages are writable.
  • PROT_NONE: Indicates that the mapped pages are inaccessible.
• flags: Used to set attributes of the memory mapping, such as shared mapping, private mapping, etc.
  • MAP_SHARED: Create a shared mapping region. Multiple processes can map a file via shared mapping, so other processes can also see changes to the mapped content, and modified content will be synchronized to the disk file.
  • MAP_PRIVATE: Create a private copy-on-write mapping. Multiple processes can map a file via private mapping, so other processes will not see changes to the mapped content, and modified content will not be synchronized to the disk file.
  • MAP_ANONYMOUS: Create an anonymous mapping, i.e., a mapping not associated with a file.
  • MAP_FIXED: Use the parameter addr to create the mapping. If the specified address addr cannot be mapped in the kernel, mmap returns failure. The parameter addr is required to be page-aligned. If the process address space specified by addr and length overlaps with an existing VMA region, the kernel will call do_The munmap() function destroys the overlapping region, and then remaps the new content.
  • MAP_POPULATE: For file mappings, it pre-reads file content into the mapping region in advance. This feature only supports private mappings.
• fd: Indicates that this is a file mapping; fd is the open file handle.
• offset: For file mappings, it represents the file offset.

File mapping and anonymous mapping

• Anonymous mapping: There is no associated file for the mapping; the contents of the memory region of this mapping are initialized to 0.
• File mapping: The mapping is associated with an actual file. Usually, the file content is mapped into the address space, so applications can read and write the file as if it were in the process address space.

Private mapping and shared mapping

• Private mapping: The created mapping can only be seen by itself; other processes cannot see changes to the mapped content.
• Shared mapping: Other processes can see changes to the mapped content. If a file is opened in shared mode, the modified content will be synchronized to the disk file.

Private mapping and sharing

mmap

Page fault

• Paging mechanism

  • MMU
  • The PTE_PRESENT bit in the page table entry

  

  PTE page table entry

• The ARM32 MMU has the following two registers related to memory access faults.

  • Fault Status Register (Data Fault Status Register, FSR)
  • Fault Address Register (Data Fault Address Register, FAR)

• The ARMv7 assembly processing flow is vectors_start -> vector_dabt -> datb_user / dabt_svc -> dabt_helpper -> v7_early_abort

• The struct fsr_info data structure is used to describe the handling scheme corresponding to a fault status.

• The fs_info[] array lists common address fault handling schemes.

fs_info array

find_vma

• Question 1: What is an anonymous page?

  • In the Linux kernel, pages that are not associated with file mappings are called anonymous pages (Anonymous Page, abbreviated as anon page). For example, pages allocated by malloc.

• Question 2: Why do we need page faults for anonymous pages?

  • If there were no anonymous page faults, then when you use the malloc() API in user space to allocate virtual memory, the kernel would have to actually allocate physical memory for it. The main problem is waste, because in many cases applications do not use the allocated virtual memory immediately, so there is no need to satisfy the application’s demand right away.

• Question 3: What are the conditions for an anonymous page fault to occur?

  • When the PRESENT bit in the PTE page table entry is not set.
  • The PTE content is empty.
  • The vma->vm_ops->fault() function pointer is not specified.

  When the above three conditions are met, we determine that it is an anonymous page fault, and the processing function is: do_anonymous_page

do_anonymous_page

• Question 1: What is a file mapping?
  • A mapping associated with a file is actually a file mapping, which corresponds to anonymous mapping. It maps the contents of a file into the process address space.
• Question 2: What types of mappings produce file mapping page faults?
  • The corresponding file mapping is mainly the mapping of ordinary files, such as a video player reading a video file.
  • There is also the case where a device driver maps a device DMA buffer into the process address space via mmap.
• In handle_pte_How to determine if it is a file mapping in the fault() function?
  • When the page is not in memory.
  • The page table entry content is empty.
  • The VMA defines the fault method function (vma->vm_ops->fault()).

Write page fault.

• The write page fault is the most complex case and also the most common situation.
• Copy-on-write technology (COW).
  • When forking a child process, the kernel does not need to copy the entire user space content of the parent process to the child process; instead, it lets the parent and child processes share the parent’s address space. This saves the very time-consuming copy operation, and only the page tables need to be copied.
  • When either the parent or child process needs to write, the data is copied, so that the parent and child processes each have their own copy. Therefore, the do-wp-page function here handles this sharing problem.
• do_wp_What are the conditions for page() to be determined?
  • When the PTE_PRESENT bit is set, and then the page fault handling flags indicate a write protection fault (this write protection fault is usually reported by hardware).

Page fault

• Overall, this process is quite complex and needs to handle many situations:
  • normal mapping pages and special mapping pages
  • Pure anonymous pages, this term is coined, i.e., anonymous pages excluding KSM.
  • Single anonymous pages, this term is also coined, meaning that only one process’s virtual page maps this anonymous page, i.e., mapcount=0.
  • Non-single anonymous pages
  • Writable shared anonymous pages, this usually refers to pages that have writable attributes and are shared, usually page cache.

Summary

• After a page fault occurs, according to conditions such as the PRESENT bit of the PTE page table entry, whether the PTE content is empty (the pte_none() macro), and whether it is a file mapping, the corresponding handling functions are as follows:
  • Anonymous page fault do_anonymous_page()
    • Conditions
      • The PRESENT bit in the PTE page table entry is not set.
      • The PTE content is empty.
      • The vma->vm_ops->fault() function pointer is not specified.
    • Use case: malloc() allocates memory.
  • File mapping page fault do_fault()
    • Conditions
      • The PRESENT bit in the PTE page table is not set.
      • The PTE content is empty and the vma->vm_ops->fault() function pointer is specified.
      • do_fault() belongs to the case of page faults occurring in file mappings.
      • If only a read fault occurs, then call do_read_fault() function to read this page.
      • If a write protection fault occurs in a private mapping VMA, then copy-on-write occurs: a new page new_page is allocated, the contents of the old page are copied to the new page, a PTE entry is generated from the new page and set into the hardware page table entry. This is the so-called copy-on-write (COW).
      • If a write protection fault occurs in a shared mapping VMA, then a dirty page is generated, and the system’s writeback mechanism is called to write back this dirty page.
    • Application scenarios:
      • Use mmap to read file contents, for example, drivers use mmap to map device memory to user space.
      • Dynamic library mapping, for example, different processes can share a dynamic library through file mapping.
  • do_swap_page for swap page fault_swap_page()
  • do_wp_page for COW page fault_wp_page()
    • do_wp_page() ultimately has two cases
      • reuse old_page: single anonymous pages and writable shared pages
      • gotten COW: non-single anonymous pages, read-only or non-shared file-mapped pages
    • Condition: the PRESENT bit in the PTE is set and a write-protection page fault occurs.
    • Application scenario: fork. The parent process forks a child process, and both parent and child share the parent’s anonymous pages. When one of them needs to modify the content, COW occurs.

pages data structure

When the MMU is enabled, the smallest unit of memory accessed by the CPU is a page.

pages data structure

• flag field: PG_* flag bits
  • Defined in include/linux/page-flags.h

flag field

ARM Versatile Express platform

page->flags layout on the ARM Versatile Express platform

• _count field
  • When the value of _count is 0, it indicates that the page is free or about to be released.
  • When the value of _count is greater than 0, it indicates that the page has been allocated and is in use by the kernel, and will not be released for the time being.

static inline void get_page(struct page *page);
void put_page(struct page *page);
#define page_cache_get(page)  get_page(page)
#define page_cache_release(page) put_page(page)

• _mapcount field

  _The mapcount reference count indicates the number of processes mapping this page, i.e., how many user PTEs have mapped it. In a 32-bit Linux kernel, each user process has a 3GB virtual address space and an independent page table, so it is possible for multiple user process address spaces to map the same physical page simultaneously. The RMAP reverse mapping system takes advantage of this feature._The mapcount reference count is mainly used in the RMAP reverse mapping system.

  • _mapcount == -1 indicates that no PTE maps to the page.
  • _mapcount==0 indicates the initial state when an anonymous page is just allocated (not yet mapped to a user process)

Usage:

• Kernel code does not directly check the count and mapcount values, but instead uses two macros

• static inline int page_mapcount(struct page *page)

• static inline int page_count(struct page *page)

• mapping field

  • When this page is used for file cache, i.e., page cache, mapping points to the address associated with this page cache_space object, this address_The space object belongs to a memory object (such as the page collection of an inode)
  • When this page is used for an anonymous page, mapping points to an anon_vma data structure, mainly used for reverse mapping.

• lru field

  • Used in the LRU list algorithm for page reclaim, the LRU list algorithm defines multiple lists.
  • When the page is used for slab, this field is reused to add a slab to the slab full list, slab free list, and slab partial list.

• virtual field

  • A pointer to the virtual address corresponding to the page.

• The meaning of struct page

  • The kernel knows the current state of the page (via the flags field).
  • The kernel needs to know whether a page is free, i.e., whether it has been allocated, and how many processes or memory paths are using this page (using count and mapcount reference counts).
  • The kernel knows who is using this page, for example, whether it is used by an anonymous page of a user-space process or by page cache (via the mapping field).
  • The kernel knows whether this page is used by the slab mechanism (via fields such as lru, s_mem).
  • The kernel knows whether this page is linearly mapped (via the virtual field).

Correspondence between physical memory and the mem_map array

• Page lock PG_Locked
  • The flags member of the struct page data structure defines a flag bit PG_locked, the kernel usually uses PG_locked to set a page lock
    • The lock_page() function is used to acquire the page lock. If the page lock is held by another process, it will sleep and wait.
    • If trylock_page() returns false, it means the lock acquisition failed; if it returns true, it means the lock acquisition succeeded.
    • trylock_page() does not sleep or wait; it is only used to make a judgment.

RMAP reverse mapping mechanism

• Forward mapping

  • From virtual addresses to physical addresses, following the footsteps of MMU hardware.

  

  RMAP reverse mapping

• When physical memory is in short supply?

  • Virtual memory is often larger than physical memory.
  • Swap temporarily unused physical memory to the swap partition.

• How to determine which physical memory is temporarily unused?

  • LRU algorithm
  • Second chance algorithm

• The approach of the Linux 2.4 kernel

  • Traverse the VMAs of all processes to determine the PTE mapped to a physical page.

• Design goals of reverse mapping:

Design goals of reverse mapping

Data structures used in reverse mapping:

Data structures used in reverse mapping

RMAP in four steps (using Linux 2.6.11 as an example)

1. The parent process allocates an anonymous page.

   1. do_anonymous_page()->page_add_anon_rmap()
   2. page_add_anon_rmap()
      1. page->mapping points to the anon_vma data structure of the VMA.
      2. Calculate page->index.

2. The parent process creates a child process.

   1. do_fork()->copy_mm()->dump_mm() copies all VMAs of the parent process to the corresponding VMAs of the child process.
   2. anon_vma_link(): adds the child process’s VMA to the parent process’s vma->anon_vma->head linked list.

3. COW occurs in the child process

   1. When parent and child processes share anonymous pages, COW occurs on the child process’s VMA

   Page fault -> handle_pte_fault()->do_wp_page() -> allocate a new anonymous page -> page_add_anon_rmap()

   The newly allocated anonymous page’s ->mapping points to the parent process’s vma->anon_vma

4. RMAP applications

   1. Page reclaim: must break all mapped user PTEs to reclaim the page
   2. Page migration: break all mapped user PTEs

RMAP applications

Defects:

Defect

Optimization: reduce lock granularity

Optimization: reduce lock granularity

• Reverse mapping summary
  • Improve page reclaim efficiency
  • Consumes some memory space, a typical space-for-time tradeoff
  • A bridge connecting virtual memory management and physical memory management

Page reclaim

• Page replacement

• Page reclaim

• Other examples of page replacement

  • Processor cache
  • Web server

• Introduction to page reclaim algorithms

  • Optimal page replacement algorithm
  • First-In First-Out page replacement algorithm
  • Not Recently Used page replacement algorithm
  • LRU algorithm (Least Recently Used page replacement algorithm)
    • Exploiting the principle of locality
    • Maintain a linked list
    • New pages are added to the head of the linked list
    • Whenever a page in the linked list is accessed, that page is moved to the head of the linked list
    • Whenever page replacement is needed, a page is taken from the tail of the linked list
  • Second chance algorithm
    • Give the page a second chance to be accessed
  • Clock page replacement algorithm
  • Working set algorithm

• Page reclaim algorithm used in the Linux kernel

  • LRU linked list
    • Inactive anonymous page LRU list_INACTIVE_ANON
    • Active anonymous page LRU list_ACTIVE_ANON
    • Inactive file-mapped page LRU list_INACTIVE_FILE
    • Active file-mapped page LRU list_ACTIVE_FILE
    • Unevictable page LRU list (LRU_UNEVICTABLE)

LRU

• LRU is implemented on a per-zone basis. Each zone has a complete set of LRU lists.

• Second chance algorithm

  • Disadvantage of the LRU algorithm: it does not consider how frequently a page is used, and pages may still be evicted from the LRU list.
  • Second chance algorithm:
    • Set an access status bit (a hardware-controlled bit)
    • Check the page’s access bit.
      • If it is 0, immediately evict it from the LRU list.
      • If it is 1, it means it has been accessed again during this period. At this point, clear this access status bit, then re-add the page to the head of the list, just like a newly added page.
  • The Linux kernel uses the following status bits to implement the second-chance method:
    • PTE_YOUNG: hardware bit. When a page has been accessed, the hardware automatically sets this bit.
    • PG_active: software bit
    • PG_referenced: software bit

Linux page reclaim diagram

Linux page reclaim diagram

Watermark diagram

Anonymous page reclaim process:

Anonymous page reclaim process

Page cache page reclaim process

Page cache page reclaim process

LRU list migration

• LRU lists can migrate between the active list and the inactive list.
• Main software and hardware bits used
  • PTE_YOUNG: hardware bit. When a page has been accessed, the hardware automatically sets this bit.
  • PG_active: software bit
  • PG_referenced: software bit
• Main helper functions
  • mark_page_accessed(): mainly used to mark that the page has been accessed, then set PG_active and PG_referenced
  • page_referenced(): determines whether the page has been accessed or referenced, returns the number of accessed/referenced PTEs, and uses the reverse mapping RMAP system to count the number of accessed/referenced PTEs.
  • page_check_references()

kswapd kernel thread

• Responsible for asynchronously reclaiming pages when memory is insufficient.
• Each NUMA memory node creates a kswapd kernel thread.
• alloc_pages() at low watermark (ALLOC_WMARK_LOW) cannot allocate memory, then the memory allocation function calls wakeup_kswapd() to wake up the kswapd kernel thread

kswapd kernel thread

• When the zone is at high watermarks, kswapd is put to sleep

Detailed flowchart of page reclamation

Detailed flowchart of page reclamation

Lifecycle of anonymous pages

• Memory allocated via the malloc/mmap interface -> do_anonymous_page()
• Copy-on-write: when a page fault occurs with a write-protection error, the newly allocated page is an anonymous page
• do_swap_page() When reading data back from the swap partition, a new anonymous page is allocated
• Page migration

Allocation

• do_anonymous_page() allocates an anonymous page anon_Taking page as an example, anon_The state of page just after allocation is as follows:
  • page->_count = 1
  • page->_mapcount=0
  • Set the PG_swapbacked flag
  • Add to LRU_ACTIVE_in the ANON list
  • page->mapping points to the anon_vma data structure in the VMA

use

• After the anonymous page is allocated during the page fault, the mapping relationship between the process virtual address space VMA and the physical page is established. When a user process accesses the virtual address, it accesses the content of the anonymous page.

Swap out

• Active list -> inactive list

• First scan of the inactive list

  • add_to_The swap() function allocates swap space for the page.

  

  add_to_swap

  • try_to_unmap()

  

  try_to_unmap

  • pageout()

pageout

• Second scan of the inactive list

  • Assume that when the second scan of the inactive list occurs, the page has already been written to the swap partition. The block layer callback function end_swap_bio_write()->end_page_writeback() will perform the following actions:

    • Clear the PG_writeback flag
    • Wake up the threads waiting on the page’s PG_writeback threads, see wake_up_page(page,PG_writeback) function

  • shrink_page_list()->__remove_The mapping() function works as follows

    • page_freeze_refs(page, 2) checks whether the current page->_count is 2, and sets the count to 0
    • Clear the PG_swapcache flag
    • Clear the PG_locked flag

    

    __remove_mapping

Finally, add the page to the free_page list, release the page, so the anon_The state of the page is that the page’s content has been written to the swap partition, and the actual physical page has been released

Swap-in of anonymous pages

• After an anonymous page is swapped out to the swap partition, if the application needs to read or write this page, a page fault occurs. Because the present bit in the PTE indicates that the page is not in memory, but the PTE entry is not empty, indicating that the page is in the swap partition, so it calls do_swap_page() function reads the content of the page back in

Release of anonymous pages

• When a user process is closed or exits, all VMAs of the user process are scanned and cleaned up. If they meet the release criteria, the related pages will be released.

Page release

Page migration

NUMA: Non-Uniform Memory Access (NUMA)

• Each processor hasits own local memory (Node Local Memory)。

• It can also access other processors’ memory (Remote Memory), but at a slower speed.

• Common inmulti-socket servers, large multi-core systems。

NUMA System

UMA: Uniform Memory Access

• All processors share a single block of physical memory。

• Access speed is consistent, that is, The latency of accessing any memory is the same。

• Common insmall multi-core systems、Symmetric multiprocessing system (SMP)。

libnuma

libnuma

Migrate all pages of a process from one memory node to another memory node

pid: the PID of the process

maxnode: the maximum number of nodes

old_nodes: a bit mask pointing to nodes, which are the nodes where the process resides

new_nodes: a node mask pointing to the migration destination

move_pages

Migrate some pages of the process to new memory nodes

migrae_pages

migrate_pages

Core function for page migration

migrate_mode

MIGRATE_ASYNC: asynchronous mode, does not block

MIGRATE_SYNC: synchronous mode, the process will block

migrate_reason

Page migration process

Page migration process

Memory compaction

memory compaction

Causes of memory fragmentation

• The physical memory of the Linux kernel is managed by the buddy system
• The buddy system consists of 11 linked lists of 2^order, with order ranging from 0 to 10.
• The buddy system has a cake-cutting habit.
• The buddy system can have a magical repair function.

Memory fragmentation

memory compaction

KSM

KSM

How to use KSM

• Enable KSM:
  • madvise(addr,length,MADV_MERGEABLE)
• Disable KSM:
  • madvise(addr,length,MADV_UNMERGEABLE)
• The mmap function in Android’s bionic library enables KSM by default.

KSM

KSM statistics counters

• run: Writing 1 to this node starts the ksmd kernel thread, writing 0 stops the ksmd kernel thread.
• pages_to_scan: The number of pages scanned in a single scan, i.e., how many pages the ksmd kernel thread scans each time it is woken up.
• sleep_millisecs: How long ksmd sleeps before the next scan, in milliseconds.
• pages_shared: The number of shared pages. If 1000 pages all have the same content and are merged into one page, here pages_shared equals 1
• pages_sharing: The number of shareable pages. If 1000 pages are merged into one page, then pages_sharing is 1000
• pages_unshared: The number of pages currently not merged, usually the number of unstable pages.
• full_scans: The number of scans from start to finish.