Cover image for Linux Memory Management

Linux Memory Management

(Updated: )
Linux
,
Timeline

Timeline

2025-11-20

init

This article introduces the core mechanisms of Linux memory management, including the concepts of segmentation and paging, address concepts, and process address space layout. It further discusses virtual memory area management, physical memory initialization, and common data structures, and summarizes the multi-level page table mapping principles and address translation processes under ARM32 and ARM64 architectures.

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 of 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 the pages needed are allocated, i.e., on-demand allocation; 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 segments)

  • Linear Address(Intel-specific term, an intermediate layer in converting logical addresses to physical addresses; in segmentation, the logical address is the segment offset, and adding the base address yields the linear address)

  • Virtual Address(Logical addresses and linear addresses are collectively referred to as virtual addresses)

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

  • Process Address Space

Memory Management Hardware Structure Diagram
Memory Management Hardware Structure Diagram

TLB, also known as the translation lookaside buffer, caches page table entries for page table translations

Memory Management Overview

Linux Memory Management Module Diagram
Linux Memory Management Module Diagram

Memory Management from the Process Perspective:

Memory Management from the Process Perspective
Memory Management from the Process Perspective

  1. Typical Virtual Address Space Layout of a 32-bit Linux System:

    • User Space (0-3G)：
      • Code Segment & Data Segment: Stores the program’s executable instructions and initialized data.
      • Heap Space: Used for dynamic memory allocation (e.g.,malloc), grows towards higher addresses.
      • mmap Space: Used for file mapping, shared memory, etc., grows towards lower addresses.
      • Stack Space: Used for function calls and local variables, grows towards lower addresses.
    • Kernel Space (3G-4G)：
      • All processes share this portion of address space, used for kernel code, data, and temporary mappings.

    Virtual Address Memory Layout
    Virtual Address Memory Layout

  2. Physical Memory Mapping：

    • Linear Mapping: The kernel maps low-end physical memory (e.g.,ZONE_NORMAL) is directly and linearly mapped to a fixed region of the kernel address space, offering fast access.

    • High-end mapping: For high-end physical memory (e.g.,ZONE_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 thevm_area_structstructure to describe a contiguous virtual address space. Each VMA represents a segment of virtual memory with the same attributes (e.g., readable, writable, executable), such as code segment, data segment, heap, stack, mmap mapping area, etc.

    • mm_structthroughmmapMembers organize all VMAs, 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, where each element is astruct pagestructure, 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 Diagram
Memory Allocator Diagram

Common Data Structures

Relationship of Common Data Structures in Linux Memory Management
Relationship of Common Data Structures in Linux Memory Management

Data StructureMain Definition FileSupplementary Notes
mm_structinclude/linux/mm_types.halso appears ininclude/linux/mm.hwidely referenced and manipulated in
vm_area_struct(VMA)include/linux/mm_types.hdescribes a contiguous virtual memory area
struct pageinclude/linux/mm_types.hdefined in early kernel versions ininclude/linux/mm.h, moved to in newer versionsmm_types.h
struct zoneinclude/linux/mmzone.hdescribes physical memory zones (e.g., DMA, NORMAL, HIGHMEM)
struct pglist_data(pgdata)include/linux/mmzone.hmemory descriptor for a NUMA node, managing all zones under that node
mem_map[]mm/memory.cglobal physical page array, its address determined during kernel initialization, each NUMA node also has its ownnode_mem_map
pte_t/ page table entryarch/arm64/include/asm/pgtable-types.hpage table entry types and page table operations are architecture-dependent

struct mm_struct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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);

Initialization of Linux physical memory

  1. How does the ARM Linux kernel know the size of memory in the system during boot?
  2. In a 32-bit Linux kernel, the user space to kernel space ratio 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 by one or in powers of two?

Introduction to DDR

  • Bank
  • row
  • Column

DDR Bank
DDR Bank

DDR
DDR

Page table mapping

arm32

  • Supports four-level mapping
    • Global directory entryPGD （Page Global Directory）
    • Upper directory entryPUD （Page Upper Directory）
    • Middle directory entryPMD （Page Middle Directory）
    • Page table entry (Page Table）

The Linux kernel was originally based on x86, so the kernel code commonly uses the above terms to refer to first-level page tables, second-level page tables, etc.

Translation from virtual address to physical address

Translation from virtual address to physical address
Translation from virtual address to physical address

First-level page table entry

First-level page table entry
First-level page table entry

  • Fault
    • Invalid entry
  • Page table
    • Entry of the first-level page table
    • bit[0~1]: Used to indicate whether this page table entry is a first-level page table entry or a segment mapping entry
    • PXN: Whether PL1 can execute this code, 0 means executable, 1 means not executable
    • NS: non security bit indicates the bit for security extension
    • Domain: Indicates the domain it belongs to, Linux only uses 3 domains
    • bits[31:10] Page table base address points to the base address of the second-level page table

Some macros defined by Linux for page tables
Some macros defined by Linux for page tables

  • Section
    • Segment table entry for segment mapping

Second-level page table entry

Second-level page table entry
Second-level page table entry

  • bit0 Execute Never flag, 1 means execute never, 0 means executable
  • bit1 Distinguishes between large pages and small pages
  • C/B bit: Memory region attributes
  • TEX[2:0]: Memory region attributes
  • AP[1:0]: Access permissions
  • S: Whether shareable
  • nG: Used for TLB

arm64

ARMv8-AArchitecture

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

ARMv8 has two page table base addresses, one for user space and one for kernel space, selected by bit 63

4KB page size + 4-level mapping

4KB page size + 4-level mapping
4KB page size + 4-level mapping

TODO

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

static void __init create_mapping(struct map_desc *md)

Establish page table mapping for the kernel image region and linear mapping region

Study how to establish kernel page table mapping

  1. int remap_pfn_range() Study how to establish page table mapping using vma, virtual address, and physical address pfn
  2. static int do_anonymous_page Study this page fault handler to observe: how to set up the user process page table given vma, virtual address vaddr, and page table entries

Comparison of x86 and ARM32 page tables
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
ARM32 implementation: parallel page tables

Page allocation mechanism

Buddy system

  • The buddy algorithm allocates memory blocks in powers of two, and these blocks are called buddies
  • What is a buddy
    • Two blocks of the same size
    • Two blocks with contiguous addresses
    • Two blocks must be split from the same larger block

Buddy system
Buddy system

Migration types

  • 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, such as memory allocated by the kernel
    • MIGRATE_MOVABLE: can be moved arbitrarily, such as memory allocated by user-space applications
    • MIGRATE_RECLAIMABLE: cannot be moved but can be deleted and reclaimed, such as file mappings
  • Generation of memory fragmentation

Generation of memory fragmentation
Generation of memory fragmentation

Page 3 is used by functions allocated by the kernel itself, such as alloc_page(GPF_KERNEL), so it belongs to non-movable pages. Although other pages are free, pages 0 to 7 cannot be combined into a large memory block

Page allocation and allocation mask

Core page allocation function

1
2
3
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_maskFlag bits

gfp_mask flag bits
gfp_mask flag bits

gfp_mask flag bits
gfp_mask flag bits

  • The page allocator is designed based on zones, so it is necessary to determine which zones can be used for this page allocation. The system will prioritize using ZONE_HIGHMEM, followed by ZONE_NORMAL
  • During page allocation, it is also necessary to know from which migration type the memory is to be allocated

Zone watermarks

Zone watermarks
Zone watermarks

Defined in the Linux kernel:

1
2
3
4
5
6
enum zone_watermarks {
	WMARK_MIN,
	WMARK_LOW,
	WMARK_HIGH,
	NR_WMARK
};

Page release function

1
2
3
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 single page frames, such as for network card drivers, etc.

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

    • To improve the efficiency of requesting and releasing single page frames, the kernel establishes a per-CPU page cache pool
    • It stores several pre-allocated page frames

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

    • No need to acquire a lock
    • No need to perform complex page frame allocation operations

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

per-CPU data structure

  • In the zone, there is a member field ‘pageset’ pointing to the per-CPU cache
  • struct per_cpu_pages data structure
1
2
3
4
5
6
7
8
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

When needing to allocate small chunks of memory of a few dozen bytes in the kernel, what to do?

slab
slab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
 * 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 per CPU
    • Used to create a local object cache pool, one per CPU, which helps:
      • Allows objects to use the cache on the same CPU as much as possible, improving efficiency
      • No additional spin locks needed, avoiding lock contention
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
 * 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 the entity of free objects
	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 to the local cache pool
  • limit: When the number of free objects in the local 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 that can be in one slab
  • gfporder: A slab occupies multiple physical pages of 2 to the power of order
  • colour: Indicates that a slab has multiple cache lines for coloring
  • 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
composition of a slab

slab operation mechanism

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 back to the system?
    • using kmem_cache_When freeing an object, if the number of free objects in the local and shared object buffer pool (ac->avail) is greater than or equal to the pool’s 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 order of 2 for memory blocks
    • void *kmalloc(size_t size, gfp_t flags)
    • void kfree(const void*)

vmalloc

virtual address space
virtual address space

vmalloc area
vmalloc area

vmalloc interface function

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

vmalloc can sleep during allocation, so it cannot be used in interrupt context

VMA operations

VMA operations
VMA operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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
VMA management

1
2
3
4
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
find_vma

1
2
3
4
5
6
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
vma_merge

malloc

  • malloc stands for memory allocation, Chinese name dynamic allocation, an API mainly used in user space to allocate virtual memory

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

  • realloc modifies the size of a previously allocated memory block, allowing it to be expanded or shrunk

  • malloc is an API encapsulated in the C library, ultimately calling 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 from this small warehouse. If the warehouse stock is insufficient, it wholesales from the kernel through the agent brk

  • Think of malloc() as retail, then brk is the agent

  • brk system call

1
SYSCALL_DEFINE1(brk, unsigned long, brk)

The place where malloc/brk allocates virtual memory
The place where malloc/brk allocates virtual memory

malloc call
malloc call

  • The above diagram searches for a free space in the heap area of the process’s address space, then creates a VMA, and then returns
  • on-demand page
    • Memory allocated by malloc may not be used for a long time, so it is actually not a good idea to immediately allocate physical space when a process allocates memory.
    • Solution: page fault interrupt, where physical memory is created only when the process truly needs to access these virtual pages, as a last resort.

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 the virtual memory.
  • This will prevent Linux from swapping this memory page to swap space.
  • In the implementation of the brk function, 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 it is set, then mm_populate() needs to be called to immediately allocate physical memory and establish the mapping.
    • The general case is: the work of allocating physical pages is always deferred until the user process needs to access these virtual pages, and only when a page fault occurs is physical memory allocated and a mapping established with the virtual address.

mlock system call
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-space programs.

get_user_pages function
get_user_pages function

follow_page() function

  • Returns the struct page data structure of a normal mapping page that has already been mapped in the VMA of the user process address space

vm_normal_page() function

  • This function divides pages into two categories: normal pages and special pages
    • Normal pages typically refer to pages with normal mappings, such as anonymous pages, page cache, and shared memory pages
    • Special pages typically refer to pages with abnormal mappings; these pages are not intended to participate in memory management’s reclamation or merging functions, such as pages mapped with the following characteristics:
      • VM_IO: Maps memory for I/O devices
      • VM_PEN_MAP: Pure PFN mapping
      • VM_MIXEDMAP: Fixed mapping

Summary

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

malloc
malloc

mmap

1
2
3
#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 for mapping into the process address space. For application portability, it is usually set to NULL, allowing the kernel to choose an appropriate address.
  • length: Indicates the size of the mapping into the process address space.
  • prot: Used to set the read/write permissions of the memory-mapped 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 the attributes of the memory mapping, such as shared mapping, private mapping, etc.
    • MAP_SHARED: Creates a shared mapping region. Multiple processes can map a file via shared mapping, so other processes can see changes to the mapped content, and modifications are synchronized to the disk file.
    • MAP_PRIVATE: Creates a private copy-on-write mapping. Multiple processes can map a file via private mapping, so other processes do not see changes to the mapped content, and modifications are not synchronized to the disk file.
    • MAP_ANONYMOUS: Creates an anonymous mapping, i.e., a mapping not associated with a file.
    • MAP_MAP_FIXED: Creates a mapping using the parameter addr. If the kernel cannot map the specified address addr, mmap will fail. The parameter addr must be page-aligned. If the process address space specified by addr and length overlaps with an existing VMA region, the kernel will call do_munmap() to destroy the overlapping region and then remap the new content.
    • MAP_POPULATE: For file mappings, it pre-reads the file content into the mapped region in advance. This feature only supports private mappings.
  • fd: indicates this is a file mapping, fd is the open file handle
  • offset: indicates the file offset during file mapping

File mapping and anonymous mapping

  • Anonymous mapping: no corresponding file is mapped, the content of this mapped memory region is initialized to 0
  • File mapping: the mapping is associated with an actual file, typically mapping the file’s content into the address space so that applications can read and write the file like operating system process space

Private mapping and shared mapping

  • Private mapping: the created mapping is only visible to 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, modified content is synchronized to the disk file

Private mapping and shared
Private mapping and shared

mmap
mmap

Page fault

  • Paging mechanism

    • MMU
    • PTE_PRESENT bit in page table entry

    PTE 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)
    • Data Fault Address Register (FAR)

  • The ARMv7 assembly processing flow isvectors_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
fs_info array

find_vma
find_vma

  • Question 1: What is an anonymous page?

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

  • Question 2: Why is a page fault for anonymous pages needed?

    • Without the page fault for anonymous pages, 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 issue is waste, because often applications allocate virtual memory but do not use it immediately, so there is no need to satisfy the application’s demand right away.

  • Question 3: What are the conditions for a page fault on anonymous pages?

    • 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 these three conditions are met, we determine it is a page fault for anonymous pages, and the handling function is: do_anonymous_page

do_anonymous_page
do_anonymous_page

  • Question 1: What is a file mapping?
    • A mapping associated with a file is essentially a file mapping, which corresponds to anonymous mapping. It maps the content of a file into the process address space.
  • Question 2: What types of mappings cause page faults for file mappings?
    • The corresponding file mapping mainly involves mapping ordinary files, such as a video player reading a video file.
    • Another case is when a device driver maps a device DMA buffer into the process address space via mmap.
  • In the 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 is empty
    • The VMA defines the fault method function (vma->vm_ops->fault())

Write page fault

  • Write page fault is the most complex case and also the most common scenario.
  • Copy-on-Write (COW) technology
    • 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 allows the parent and child processes to share the parent’s address space, saving the time-consuming copy operation and only copying the page tables.
    • When either the parent or child process needs to write, the data is copied, so that each process has its own copy. Therefore, the do_wp_page function here handles this sharing issue.
  • do_wp_What are the judgment conditions for page()?
    • When the PTE_PRESENT bit is set, and then the page fault handling flags indicate a write protection error (this write protection error is usually reported by hardware).

Page fault interrupt
Page fault interrupt

  • 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 fabricated, meaning anonymous pages excluding KSM.
    • Single anonymous pages, this term is also fabricated, meaning 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 with writable attributes and are shared, typically page cache.

Summary

  • After a page fault occurs, based on the PRESENT bit of the PTE entry, whether the PTE content is empty (pte_none() macro), and whether it is a file mapping, the corresponding handling functions are as follows:
    • Anonymous page fault handling do_anonymous_page()
      • Judgment condition
        • The PRESENT bit in the PTE entry is not set
        • The PTE content is empty
        • The vma->vm_ops->fault() function pointer is not specified
      • Application scenario: malloc() allocates memory
    • File mapping page fault handler do_fault()
      • Judgment condition
        • 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 error occurs, then call do_read_fault() function to read this page
        • If a write-protection error occurs in a private mapping VMA, copy-on-write occurs: a new page new_page is allocated, the content of the old page is 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 error occurs in a shared mapping VMA, a dirty page is generated, and the system’s writeback mechanism is called to write back this dirty page
      • Application scenarios:
        • Using mmap to read file content, for example, using mmap in a driver to map device memory to user space
        • Dynamic library mapping, for example, different processes can share a dynamic library through file mapping
    • Swap page fault handler do_swap_page()
    • Copy-on-write (COW) page fault handler do_wp_page()
      • do_wp_There are two cases for the final processing of page()
        • Reuse old_page: single anonymous pages and writable shared pages
        • Copy-on-write: non-single anonymous pages, read-only or non-shared file-mapped pages
      • Judgment condition: the PRESENT bit in the PTE is set and a write fault page fault occurs
      • Application scenario: fork, the parent process forks a child process, both share the parent’s anonymous pages; when one needs to modify 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
pages data structure

  • Flag: PG_* flags
    • Defined in include/linux/page-flags.h

Flag
Flag

ARM Versatile Express platform

ARM Versatile Express platform page->flags layout
ARM Versatile Express platform page->flags layout

  • _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 0, it indicates that the page has been allocated and is being used by the kernel, and will not be released temporarily.
1
2
3
4
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 process mappings to this page, i.e., how many user PTE page tables have mapped it. In a 32-bit Linux kernel, each user process has 3GB of virtual space and an independent page table, so it is possible for multiple user process address spaces to map to the same physical page simultaneously. The RMAP reverse mapping system leverages 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 == -1 indicates that only the parent process has mapped the page. When an anonymous page is first allocated,_The mapcount reference count is initialized to 0.

Usage:

  • The kernel code does not directly check the count and mapcount values; instead, it 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 space associated with this page cache._space object, this address_The address space object belongs to a memory object (such as a collection of pages for an inode).
    • When this page is used as an anonymous page, mapping points to an anon_vma data structure, primarily used for reverse mapping.

  • lru field

    • Used in the LRU list algorithm for page reclamation, the LRU list algorithm defines multiple lists
    • Used 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 significance 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, such as whether the user is an anonymous page from a user-space process or a page cache (via the mapping field)
    • The kernel knows whether this page is used by the slab mechanism (via fields such as lru and s_mem)
    • The kernel knows whether this page is linearly mapped (via the virtual field)

Correspondence between physical memory and the mem_map array
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 typically uses PG_locked to set a page lock
      • The lock_page() function is used to acquire a page lock. If the page lock is held by another process, it will sleep and wait.
      • If trylock_page() returns false, it means acquiring the lock failed; if it returns true, it means acquiring the lock succeeded.
      • trylock_page() does not sleep and wait; it is only used for checking.

RMAP Reverse Mapping Mechanism

  • Forward Mapping

    • From virtual address to physical address, following the steps of the MMU hardware.

    RMAP Reverse Mapping
    RMAP Reverse Mapping

  • When physical memory is insufficient?

    • 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

  • Linux 2.4 kernel approach

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

  • Design goals of reverse mapping:

Design goals of reverse mapping
Design goals of reverse mapping

Data structures used in reverse mapping:

Data structures used in reverse mapping
Data structures used in reverse mapping

The RMAP tetralogy (using Linux 2.6.11 as an example)

  1. Parent process allocates anonymous pages

    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. Parent process creates 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. Child process undergoes COW

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

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

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

  1. RMAP Applications

    1. Page Reclamation: Disconnect all mapped user PTEs to reclaim the page
    2. Page Migration: Disconnect all mapped user PTEs

RMAP Applications
RMAP Applications

Disadvantages:

Disadvantages
Disadvantages

Optimization: Reduce lock granularity

Optimization: Reduce lock granularity
Optimization: Reduce lock granularity

  • Reverse Mapping Summary
    • Improve page reclamation efficiency
    • Consumes some memory space, a typical trade-off of space for time
    • A bridge connecting virtual memory management and physical memory management

Page Reclamation

  • 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 locality principle
      • maintaining a linked list
      • new page 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 reclamation 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
      • Non-reclaimable page LRU list (LRU_UNEVICTABLE)

LRU
LRU

  • LRU is implemented based on zones. Each zone has a complete set of LRU lists

  • Second chance method

    • Disadvantage of LRU algorithm: It does not consider the frequent usage of the page, and the page may still be evicted from the LRU list
    • Second chance method:
      • An access status bit (hardware-controlled bit) is set
      • Check the access bit of the page
        • If it is 0, immediately evict it from the LRU list
        • If it is 1, it means the page has been accessed again during this period. Clear the 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 algorithm:
      • PTE_YONG: a hardware bit. When a page is accessed, the hardware automatically sets this bit
      • PG_active: a software bit
      • PG_referenced: a software bit

Linux page reclamation block diagram

Linux page reclamation block diagram
Linux page reclamation block diagram

Watermark diagram
Watermark diagram

Anonymous page reclamation process:

Anonymous page reclamation process
Anonymous page reclamation process

Page cache reclamation process

Page cache reclamation process
Page cache reclamation process

Migration of LRU lists

  • The LRU list can migrate between the active list and the inactive list.
  • Mainly used hardware and software bits.
    • PTE_YOUNG: A hardware bit that is automatically set by the hardware when a page is accessed.
    • PG_active: A software bit.
    • PG_referenced: A software bit.
  • Main helper functions.
    • mark_page_accessed(): Mainly used to mark that a page has been accessed, then sets PG_active and PG_referenced
    • page_referenced(): Determines whether a page has been accessed or referenced, returns the number of accessed/referenced PTEs, using 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.
  • One kswapd kernel thread is created per NUMA memory node.
  • alloc_pages() at low watermark (ALLOC_WMARK_LOW) cannot allocate memory, at which point the memory allocation function calls wakeup_kswapd() to wake up the kswapd kernel thread.

kswapd kernel thread
kswapd kernel thread

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

Detailed page reclamation flow chart

Detailed page reclamation flow chart
Detailed page reclamation flow chart

Lifecycle of anonymous pages

  • Memory allocated via malloc/mmap interface -> do_anonymous_page()
  • Copy-on-write: When a page fault occurs due to a write protection error, the newly allocated page is an anonymous page
  • do_swap_When page() reads data back from the swap partition, a new anonymous page is allocated
  • Migrate page

Allocate

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

Use

  • After the anonymous page is allocated during a page fault, the mapping between the process’s 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 this page

    add_to_swap
    add_to_swap

    • try_to_unmap()

    try_to_unmap
    try_to_unmap

    • pageout()

pageout
pageout

  • Second scan of the inactive list

    • Assume that during the second scan of the inactive list, writing this page to the swap partition has completed. The callback function end of the block layer_swap_bio_write()->end_page_writeback() performs the following actions:

      • Clear the PG_writeback flag
      • Wake up threads waiting on this 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 if the current page->_count is 2, and sets the count to 0
      • Clear the PG_swapcache flag
      • Clear the PG_locked flag

      __remove_mapping
      __remove_mapping

Finally, add the page to free_In the page list, release the page, so this anon_The state of the page is that its 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 the page is not in memory, but the PTE entry is not empty, indicating the page is in the swap partition, so do is called_swap_The page() function re-reads the content of the page

Release of anonymous pages

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

Release of pages
Release of pages

Page migration

NUMA:Non-Uniform Memory Access

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

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

  • Commonly found inmulti-socket servers, large multi-core systems。

NUMA System
NUMA System

UMA: Uniform Memory Access

  • All processors share a single physical memory。

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

  • Commonly found insmall multi-core systems、Symmetric Multiprocessor Systems (SMP)。

libnuma

libnuma
libnuma

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

pid the PID of the process

maxnode: 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
move_pages

migrate some pages of the process to new memory nodes

migrae_pages

migrate_pages
migrate_pages

page migration core function
page migration core function

migrate_mode
migrate_mode

MIGRATE_ASYNC asynchronous mode, non-blocking

MIGRATE_SYNC synchronous mode, the process will block

migrate_reason
migrate_reason

page migration process

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 size 2^order, with order ranging from 0 to 10
  • the buddy system has a habit of cutting the cake
  • the buddy system can have a magical repair function

Memory fragmentation
Memory fragmentation

memory compaction
memory compaction

KSM

KSM
KSM

How to use KSM

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

KSM
KSM

KSM statistics

  • run: Writing 1 to this node starts the ksmd kernel thread, writing 0 stops it
  • pages_to_scan: Number of pages scanned per batch, 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: 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: Number of sharable pages. If 1000 pages are merged into one page, then pages_sharing is 1000
  • pages_unshared: Number of pages currently not merged, typically the number of unstable pages
  • full_scans: Number of full scans from start to end