Linux physical memory allocation and malloc internals
Topic: boot-time physical memory detection → memblock → zones/NUMA → buddy allocator → SLUB/kmalloc → user-space malloc boundary → glibc/tcmalloc/jemalloc/mimalloc comparison
Assumed baseline: current upstream Linux mainline source style, x86_64 examples, generic MM where possible.
Language note: Korean explanations with English technical terms preserved.
0. Scope, assumptions, and reading strategy
이 문서는 Linux latest mainline source를 읽는 방식으로 physical memory allocation을 따라간다. 기준 architecture는 가장 자료와 path가 명확한 x86_64이고, 공통 MM layer는 architecture-independent code를 중심으로 설명한다. arm64/EFI/DT 기반 machine도 큰 구조는 비슷하지만 firmware memory map 전달 방식, early page table setup, DMA zone constraints가 다를 수 있다.
핵심 질문은 네 가지다.
- 부팅 때 kernel이 physical memory를 어떻게 발견하고, 어떤 영역을 reserved로 둔 뒤 allocator에 넘기는가?
alloc_page()/alloc_pages()가 호출되면 buddy allocator 안에서 어떤 순서로 page frame이 선택되는가?kmalloc()/ object allocation은 SLUB allocator에서 어떻게 fastpath/slowpath를 타고, 언제 buddy로 내려가는가?- user-space
malloc()은 어디까지가 libc allocator이고 어디서 kernel로 넘어가며,sbrk()/mmap()/page fault/physical page allocation이 어떻게 만나는가?
문서의 “page”는 Markdown logical page다. PDF로 변환하면 font, margins, code block wrapping에 따라 실제 page count가 달라진다. 각 logical page는 <!-- pagebreak --> marker로 나뉜다.
Source path 중심 map
Kernel physical memory boot:
arch/x86/kernel/e820.carch/x86/kernel/setup.cmm/memblock.cmm/mm_init.cmm/page_alloc.cinclude/linux/mmzone.hinclude/linux/gfp_types.h
Kernel allocation:
mm/page_alloc.cmm/compaction.cmm/vmscan.cmm/oom_kill.c
Kernel object allocation:
mm/slub.cinclude/linux/slab.hinclude/linux/slub_def.h
User-space allocators:
- glibc:
malloc/malloc.c - TCMalloc: front-end / middle-end / back-end design docs and source
- jemalloc: arena/bin/tcache/extent design and mallctl docs
- mimalloc: page/local free-list/sharded free-list design docs
1. One mental model: physical pages, virtual mappings, and allocators
가장 먼저 구분해야 할 layer는 세 개다.
Physical page allocator는 kernel 내부에서 page frame을 관리한다. 보통 unit은 struct page로 표현되는 physical page이고, allocation unit은 order 기반이다. order n은 2^n개의 contiguous base pages를 뜻한다. 예를 들어 4 KiB page system에서 order 0은 4 KiB, order 9는 2 MiB다.
Kernel virtual/object allocator는 kernel code가 object 단위 memory를 요청할 때 쓰는 layer다. 대표적으로 kmalloc(96, GFP_KERNEL) 또는 kmem_cache_alloc()이다. 이 layer는 small object를 SLUB cache에서 꺼내고, 새 slab page가 필요할 때 physical page allocator로 내려간다. 큰 kmalloc()은 내부적으로 page allocator에 더 직접적으로 가까워진다.
User-space allocator는 process heap 안에서 malloc()/free() API를 구현한다. glibc malloc()은 먼저 userspace metadata와 bins/tcache/arena를 본다. 더 이상 heap chunk를 공급할 수 없으면 brk() 또는 mmap() system call로 kernel에게 virtual address range를 요청한다. 그러나 brk()/mmap()이 성공했다고 해서 항상 즉시 physical page가 할당되는 것은 아니다. anonymous virtual page는 보통 first-touch page fault 때 zero page 또는 fresh page allocation으로 materialize된다.
따라서 “malloc이 physical memory를 allocate한다”는 표현은 절반만 맞다. 정확히는 다음처럼 나눠야 한다.
user malloc()
-> userspace chunk bookkeeping
-> maybe brk()/mmap() syscall
-> kernel creates/extends VMA
-> later CPU access triggers page fault
-> kernel fault handler allocates physical page
-> buddy allocator supplies struct page
반대로 kernel 안에서 alloc_page(GFP_KERNEL)을 부르면 userspace allocator는 끼지 않는다. 바로 kernel MM의 zoned buddy allocator fastpath/slowpath를 탄다.
이 문서에서는 두 세계를 연결하되, “어디서부터 kernel인가?”를 항상 system call boundary와 page fault boundary로 표시한다.
2. Boot overview: from firmware memory map to usable pages
부팅 초기에 kernel은 아직 정상적인 kmalloc()도, buddy allocator도, full page table도 믿고 쓸 수 없다. 그런데 allocator를 초기화하려면 physical memory map이 필요하다. 그래서 Linux는 early boot 전용 allocator인 memblock을 사용한다.
x86에서 firmware/bootloader가 전달하는 대표적인 physical memory description은 E820 memory map이다. UEFI boot 환경에서도 kernel은 최종적으로 “어떤 physical range가 RAM이고, 어떤 range가 reserved인지”를 early boot data structure로 정리한다. arch/x86/kernel/e820.c에는 type string으로 System RAM, reserved, ACPI Tables, ACPI Non-volatile Storage, Unusable memory 같은 E820 type이 드러난다.
High-level boot memory pipeline은 다음과 같다.
firmware / bootloader
-> physical memory map 전달
-> arch setup code parses map
-> memblock_add(memory ranges)
-> memblock_reserve(kernel image, initrd, firmware tables, cmdline, page tables, etc.)
-> architecture + generic MM initialize nodes/zones
-> struct page array initialized
-> free usable PFNs to buddy allocator
-> memblock mostly discarded after mem_init()
여기서 중요한 점은 memory detection과 memory allocation availability가 다르다는 것이다. firmware map이 “이 range는 RAM”이라고 말해도, kernel image가 올라간 곳, initrd, ACPI table, early page table, crashkernel, DMA reserved area, memblock allocation으로 이미 잡힌 영역은 바로 buddy free list에 들어가면 안 된다.
즉 boot 초기의 목표는 단순히 RAM 크기를 아는 것이 아니라, 다음 집합을 정확히 만드는 것이다.
usable RAM for general allocation
= firmware-reported RAM
- kernel/reserved/firmware/special-purpose ranges
- architecture constraints
- command-line reserved regions
- memory hotplug/offline policy constraints
이 결과가 나중에 zone->managed_pages, free_area[order], per-cpu pageset 등의 형태로 변환된다.
3. x86_64 physical memory detection: E820 and friends
x86_64에서 “physical memory detection”의 classic entry point는 E820 table이다. E820은 BIOS/firmware/bootloader가 제공하는 physical address ranges와 type을 담는다. Linux source의 arch/x86/kernel/e820.c는 raw table, firmware table, modified table 등을 다루며, range add/update/print/sanitize logic을 가진다.
개념적으로 E820 entry는 다음 형태라고 보면 된다.
struct e820_entry {
u64 addr;
u64 size;
enum e820_type type;
};
실제 source에서는 kernel internal representation과 boot protocol representation이 조금 다르지만 핵심은 addr, size, type이다. type이 E820_TYPE_RAM이면 일반 RAM 후보이고, E820_TYPE_RESERVED이면 kernel allocator가 일반 allocation에 쓰면 안 되는 range다.
중요한 subtlety는 E820 map이 kernel에서 그대로 사용되지 않는다는 점이다. kernel은 다음 과정을 거친다.
- firmware-provided map을 받는다.
- overlapping/invalid/unsorted range를 sanitize한다.
- command line option, architecture quirk, crashkernel, initrd, setup data, ACPI/NVS 같은 reserved region을 반영한다.
- memblock에 usable memory와 reserved memory를 등록한다.
- final zones/node layout에 맞춰 generic MM에게 넘긴다.
x86 source reading hints:
arch/x86/kernel/e820.c
e820__range_add()
e820__update_table()
e820__print_table()
e820__memblock_setup()
arch/x86/kernel/setup.c
setup_arch()
setup_arch()는 architecture-specific early init의 큰 coordinator다. memory map parsing, early reservations, early page table work, memblock setup이 이 근처에 모인다.
arm64는 E820이 아니라 Device Tree /memory node 또는 UEFI memory map을 통해 RAM ranges를 얻는다. 그러나 이후 memblock_add()/memblock_reserve()로 generic early allocator에 feeding한다는 구조는 비슷하다.
4. memblock: why an allocator before the allocator exists?
memblock은 boot-time physical memory allocator다. “allocator를 만들기 위한 allocator”라고 생각하면 쉽다. boot early stage에는 다음 제약이 있다.
struct pagearray가 완전히 초기화되어 있지 않을 수 있다.- buddy free lists가 아직 없다.
kmalloc()/SLUB가 사용할 slab page를 공급받을 수 없다.- page tables, per-cpu areas, memory maps, bootmem-like metadata 자체를 allocate해야 한다.
- allocation이 대부분 permanent 또는 init-only라서 free pattern이 단순하다.
그래서 memblock은 복잡한 general-purpose allocator가 아니라 range list 기반 allocator다. Linux documentation 기준으로 memblock은 주로 다음 collections를 관리한다.
memblock.memory : available physical memory ranges
memblock.reserved : reserved physical memory ranges
memblock.physmem : architecture-specific physical memory ranges if enabled
memblock allocation의 본질은 “available range 중 reserved와 충돌하지 않는 aligned physical range를 찾고, 그 range를 reserved에 추가한다”이다.
Pseudo model:
memblock_alloc(size, align):
for each candidate range in memblock.memory:
subtract memblock.reserved
respect limit, node, bottom-up/top-down policy
find aligned gap
mark gap as reserved
return virtual mapping for that physical range
memblock의 중요한 invariant는 reserved range는 나중에 buddy로 풀리면 안 된다는 것이다. 그래서 boot memory release 단계에서 memblock은 memory - reserved에 해당하는 pages만 free한다.
옛날 Linux에는 bootmem allocator가 있었지만, 현대 Linux에서는 memblock이 boot-time memory management의 중심이다. source reading은 mm/memblock.c와 architecture-specific setup code를 함께 봐야 한다.
5. Early reservations: kernel image, initrd, page tables, ACPI, crashkernel
부팅 중 “RAM이지만 일반 allocation에 쓰면 안 되는 영역”은 생각보다 많다. 대표적인 reserved regions는 다음과 같다.
kernel text/data/bss
initrd / initramfs
boot parameters and command line
setup_data linked list
early page tables
ACPI tables / EFI runtime regions
reserved firmware regions
crashkernel reservation
CMA reserved area
device memory windows or unusable RAM
memblock allocator metadata
이 영역들은 대개 memblock_reserve() 또는 architecture wrapper를 통해 memblock.reserved에 들어간다. 이후 memblock_free_all() 또는 mem_init() 단계에서 reserved가 아닌 RAM만 buddy allocator로 넘어간다.
중요한 distinction:
- Reserved forever: kernel image text/data, firmware tables 일부, device reserved range.
- Reserved until init:
__inittext/data, initrd unpack 후 release 가능한 memory, early page tables 일부. - Reserved for subsystem: CMA, crashkernel, hugepage reservation, device-specific pool.
Kernel source를 읽을 때는 “이 range가 왜 reserved인가?”를 추적해야 한다. 단순히 E820 type만 보면 부족하고, boot parameter와 subsystem reservation까지 봐야 한다.
Example mental trace:
E820 says [1 GiB, 8 GiB) is RAM
kernel command line says crashkernel=512M
CMA reserves 256M
initrd occupies 80M
kernel image occupies another range
=> only the remainder enters buddy as general free pages
이 단계에서 실수하면 allocator bug는 매우 치명적이다. reserved memory를 buddy에 넣으면 kernel text overwrite, firmware table corruption, initrd corruption, DMA memory conflict 같은 early boot crash가 난다.
6. PFN, struct page, and the physical memory database
Linux는 physical page frame을 보통 PFN(Page Frame Number)로 다룬다.
pfn = physical_address >> PAGE_SHIFT
physical_address = pfn << PAGE_SHIFT
각 physical page에 대한 metadata는 struct page다. 모든 PFN이 항상 valid struct page를 갖는 것은 architecture/model에 따라 다르지만, 일반 RAM range의 managed pages는 struct page database에 의해 관리된다.
struct page는 매우 dense하고 overloaded된 structure다. 같은 memory word가 LRU, slab, page cache, compound page, buddy state 등 여러 mode에서 다르게 해석된다. buddy allocator 관점에서 중요한 bit/field는 다음과 같다.
PageBuddy flag : 이 page가 buddy free list의 head임
page_private(page) : free block order를 저장하는 데 사용
_refcount : allocated/free 상태와 lifetime에 중요
compound metadata : high-order compound page일 때 head/tail 관계
현대 kernel에서는 folio abstraction도 중요하다. folio는 page cache와 compound page handling을 개선하려는 higher-level abstraction이다. 그러나 buddy allocator의 physical frame allocation 기본 단위는 여전히 order와 struct page로 이해하면 된다.
Boot 중 해야 하는 일:
- physical memory ranges를 PFN range로 변환한다.
- valid PFN에 대한
struct pagearray를 준비한다. - node/zone membership을 설정한다.
- reserved PFN은 free하지 않는다.
- usable PFN은
__free_pages_core()같은 path를 통해 buddy에 추가한다.
이것이 완료되어야 alloc_pages()가 정상 작동할 수 있다.
7. NUMA nodes and zones: why buddy is “zoned”
Linux page allocator는 단순한 global free list가 아니다. source comment에서도 “zoned buddy allocator”라고 부른다. 이유는 physical memory가 다음 constraints를 갖기 때문이다.
NUMA node는 CPU와 memory locality를 나타낸다. 각 node는 pg_data_t로 표현되고, node마다 여러 zone을 가진다.
Zone은 addressability/mobility/device constraints를 나타낸다. 주요 zone은 다음과 같다.
ZONE_DMA : legacy DMA address limit에 맞는 low memory
ZONE_DMA32 : 32-bit DMA 가능한 memory, x86_64에서 흔함
ZONE_NORMAL : 일반 kernel direct-map managed memory
ZONE_HIGHMEM : 32-bit highmem system에서 direct map되지 않는 memory
ZONE_MOVABLE : migration 가능한 pages 위주, memory hotplug/fragmentation 관리
ZONE_DEVICE : device memory / pmem / HMM 등 special memory
Allocator는 GFP flags와 allocation context에 따라 어떤 zone까지 사용할 수 있는지 결정한다. 예를 들어 GFP_DMA32는 DMA32-capable memory를 요구한다. 평범한 GFP_KERNEL은 보통 ZONE_NORMAL을 선호하지만, system configuration에 따라 fallback path가 달라질 수 있다.
Logical structure:
node 0 (pg_data_t)
zone DMA
free_area[0..MAX_ORDER]
per-cpu pagesets
watermarks
zone DMA32
zone NORMAL
node 1
zone NORMAL
zone MOVABLE
zonelist는 allocation fallback order를 encoding한다. NUMA policy, cpuset, allowed nodemask, GFP zone constraints가 결합되어 “어떤 zone을 어떤 순서로 scan할지”가 정해진다.
즉 alloc_pages()는 “global memory에서 하나 뽑기”가 아니라 “현재 context에서 허용되는 zonelist를 따라 watermarks를 만족하는 zone을 찾고, 그 zone의 per-cpu cache 또는 buddy free_area에서 order block을 얻기”다.
8. Zone metadata: watermarks, reserves, and managed pages
struct zone은 page allocator의 핵심 accounting structure다. 중요한 field categories는 다음과 같다.
free_area[MAX_ORDER] : buddy free lists, order별/migratetype별
per_cpu_pageset : order-0 중심 per-cpu page cache
watermark/min/low/high : reclaim/kswapd/direct reclaim threshold
managed_pages : buddy가 관리할 수 있는 pages
spanned_pages : zone physical span
present_pages : physically present pages
lowmem_reserve[] : lower zone protection
lock : zone-level buddy lock
Watermark는 allocator가 “이 zone에서 지금 page를 빼도 되는가?”를 판단하는 기준이다. 예를 들어 get_page_from_freelist()는 candidate zone마다 zone_watermark_fast()를 호출한다. watermark check가 실패하면 reclaim, compaction, fallback, slowpath로 이동한다.
Watermark의 목적은 memory가 완전히 고갈되기 전에 reclaim/compaction을 시작하게 하는 것이다.
free pages high enough
-> fast allocation
below low/high watermark
-> kswapd wakeup, maybe still allocate depending flags
below min watermark
-> direct reclaim/compaction or fail
managed_pages는 단순한 total physical pages가 아니다. firmware reserved, kernel reserved, memblock reserved, device memory, holes 등을 뺀 “buddy allocator가 실제로 관리하는 page 수”다.
Low memory reserves는 DMA/DMA32 같은 lower zones가 일반 allocation에 의해 고갈되지 않도록 보호한다. 그렇지 않으면 나중에 진짜 DMA-constrained allocation이 실패할 수 있다.
Source를 볼 때는 zone_watermark_fast(), __zone_watermark_ok(), lowmem_reserve, watermark_boost, kswapd wakeup path를 함께 봐야 한다.
9. Pageblocks and migratetypes: fragmentation policy inside buddy
Buddy allocator는 order별 free block을 관리하지만, modern Linux는 fragmentation을 줄이기 위해 migratetype도 함께 사용한다. 각 free list는 order뿐 아니라 migratetype별로 나뉜다.
대표 migratetype:
MIGRATE_UNMOVABLE : kernel objects, pinned pages 등 이동 어려운 pages
MIGRATE_MOVABLE : page cache, anonymous pages 등 migration 가능한 pages
MIGRATE_RECLAIMABLE : reclaim 가능한 slab/page cache 성격
MIGRATE_CMA : CMA reserved region
MIGRATE_HIGHATOMIC : atomic high-order reserve
MIGRATE_ISOLATE : memory isolation/hotremove/compaction
Pageblock은 migratetype tagging의 granularity다. 보통 high-order block 크기와 관련되며, compaction과 huge page allocation에 중요하다.
왜 이게 필요한가? Pure buddy만 쓰면 movable/unmovable objects가 섞이면서 high-order contiguous range가 빨리 사라진다. Linux는 movable pages를 비슷한 pageblock에 몰아넣고, unmovable pages도 별도 pageblock에 두려고 한다. 그러면 나중에 compaction으로 movable pages를 옮겨 contiguous free range를 만들 가능성이 높아진다.
Allocation path에서는 원하는 migratetype list를 먼저 보고, 부족하면 fallback migratetype에서 가져온다. fallback은 단순히 아무 list나 훑는 것이 아니라 fragmentation cost를 고려한다.
Mental model:
alloc order-0 GFP_KERNEL for kernel object
-> migratetype likely UNMOVABLE or RECLAIMABLE
alloc anonymous user page
-> migratetype likely MOVABLE
alloc CMA page
-> MIGRATE_CMA region only or special path
compaction
-> isolate movable pages from pageblocks
-> migrate them
-> create high-order free block
이 migratetype layer가 있어서 Linux buddy allocator는 classic textbook buddy보다 훨씬 복잡하다.
10. GFP flags: allocation contract between caller and allocator
Kernel allocation API는 size/order만 받지 않는다. 거의 항상 GFP flags를 받는다. GFP는 “어디서 allocate할 수 있는가, block/reclaim/I/O를 해도 되는가, 어떤 zone을 써야 하는가”를 담는 contract다.
흔한 flags:
GFP_KERNEL // normal kernel allocation; may sleep, may reclaim
GFP_ATOMIC // cannot sleep; interrupt/atomic context; emergency reserves possible
GFP_NOWAIT // do not sleep; limited reclaim
GFP_NOIO // avoid starting I/O reclaim
GFP_NOFS // avoid filesystem recursion during reclaim
GFP_USER // user allocation
GFP_HIGHUSER_MOVABLE
GFP_DMA
GFP_DMA32
__GFP_ZERO // zero fill
__GFP_NORETRY / __GFP_RETRY_MAYFAIL / __GFP_NOFAIL
__GFP_COMP // compound page
예를 들어 kmalloc(size, GFP_KERNEL)은 sleep 가능한 process context에서 부르는 일반 allocation이다. allocator는 reclaim/compaction을 수행할 수 있다. 반대로 interrupt handler에서 GFP_KERNEL을 쓰면 안 된다. 그 context는 sleep할 수 없기 때문에 GFP_ATOMIC 등이 필요하다.
GFP flags는 크게 세 가지로 작동한다.
- Zone selection: DMA/DMA32/NORMAL/MOVABLE 중 어디까지 가능한지.
- Behavior policy: reclaim, compaction, I/O, filesystem recursion, retry policy.
- Post-processing: zeroing, accounting, compound page handling, memcg accounting.
실제 path에서는 gfp_t가 alloc_flags, highest_zoneidx, migratetype, alloc_context 등으로 해석된다. source에서 prepare_alloc_pages(), gfp_zone(), gfp_migratetype(), current_gfp_context()를 보면 이 변환이 드러난다.
11. Public page allocation APIs: what exactly is requested?
Kernel code가 physical page를 요청할 때 흔히 쓰는 API는 다음과 같다.
struct page *alloc_page(gfp_t gfp);
struct page *alloc_pages(gfp_t gfp, unsigned int order);
unsigned long __get_free_page(gfp_t gfp);
unsigned long __get_free_pages(gfp_t gfp, unsigned int order);
void free_page(unsigned long addr);
void __free_pages(struct page *page, unsigned int order);
alloc_page(gfp)는 order 0 alloc_pages(gfp, 0)의 wrapper라고 보면 된다. __get_free_pages()는 virtual address를 반환한다. alloc_pages()는 struct page *를 반환한다.
Order semantics:
order 0 -> 1 page
order 1 -> 2 contiguous pages
order 2 -> 4 contiguous pages
...
order n -> 2^n contiguous pages
“contiguous”는 physical contiguity다. DMA buffer, huge page, compound page, page table allocation 등에서 중요하다. vmalloc()은 virtually contiguous지만 physical pages는 흩어져 있을 수 있다.
API selection rule:
need one/few pages and physical contiguity?
-> alloc_pages()
need small kernel object?
-> kmalloc()
need many pages but only virtual contiguity?
-> vmalloc()
need user virtual memory?
-> mmap/brk/VMA/page fault path
need object cache with constructors/alignment?
-> kmem_cache_create + kmem_cache_alloc()
Page allocator는 struct page 단위 allocator라서, small object allocation에 직접 쓰면 internal fragmentation이 크다. 그래서 kmalloc(64) 같은 request는 page allocator가 아니라 SLUB cache를 거친다.
12. Main call graph: alloc_page(GFP_KERNEL)
현대 Linux source에서 exact symbol name은 config/profiling/noinstr options에 따라 wrapper가 붙을 수 있다. 그러나 core flow는 다음과 같이 읽으면 된다.
alloc_page(gfp)
-> alloc_pages(gfp, order=0)
-> alloc_pages_noprof()
-> __alloc_pages_noprof()
-> __alloc_pages()
-> __alloc_frozen_pages_noprof(gfp, order, preferred_nid, nodemask)
// core zoned buddy allocator
-> prepare_alloc_pages()
-> get_page_from_freelist(gfp, order, alloc_flags, ac)
-> for_each_zone_zonelist_nodemask(...)
-> zone_watermark_fast()
-> rmqueue()
-> rmqueue_pcplist() // order-0 fast/common path
or rmqueue_buddy()
-> __rmqueue()
-> __rmqueue_smallest()
-> expand()
-> prep_new_page()
-> if fastpath fails:
__alloc_pages_slowpath()
-> reclaim / compaction / OOM / retry policy
핵심은 fastpath와 slowpath의 분리다. 대부분 order-0 allocation은 per-cpu pageset(PCP)에서 빠르게 처리된다. PCP가 비어 있으면 zone lock을 잡고 buddy에서 batch로 가져와 PCP를 refill한다.
High-order allocation은 PCP를 거치지 않고 buddy path로 갈 가능성이 높다. 왜냐하면 high-order contiguous block은 per-cpu cache에 오래 잡아두면 fragmentation/availability 문제가 커질 수 있기 때문이다.
GFP_KERNEL order 0 common fastpath는 대략 다음과 같다.
prepare allocation context
-> scan zonelist
-> watermark check passes
-> try PCP list for migratetype
-> if PCP empty, rmqueue_bulk from buddy
-> pop page from PCP
-> prep_new_page
-> return struct page
실패하면 slowpath로 내려가며, 여기서 memory reclaim, compaction, retry, OOM killer가 등장한다.
13. __alloc_frozen_pages_noprof: the heart of zoned buddy allocation
Source comment는 __alloc_frozen_pages_noprof() 계열 function을 “heart of the zoned buddy allocator”라고 설명한다. 이름의 frozen/noprof는 profiling/frozen page handling wrapper 때문에 붙은 것이고, conceptual role은 core allocation이다.
주요 단계는 다음과 같다.
struct page *__alloc_frozen_pages_noprof(gfp_t gfp,
unsigned int order,
int preferred_nid,
nodemask_t *nodemask)
{
gfp = current_gfp_context(gfp);
prepare_alloc_pages(..., &ac, ...);
page = get_page_from_freelist(gfp, order, alloc_flags, &ac);
if (likely(page))
return page;
return __alloc_pages_slowpath(gfp, order, &ac);
}
실제 source는 훨씬 복잡하다. sanitization, allocation flags, memcg, cpuset retry, should_fail_alloc_page(), nodemask validation 등이 있다. 하지만 핵심은 fast freelist scan first, slowpath second다.
alloc_context에는 다음 정보가 들어간다.
preferred_zoneref
zonelist
nodemask
highest_zoneidx
migratetype
spread_dirty_pages / dirty zone policy
이 context는 get_page_from_freelist()가 zone scan을 할 때 필요한 모든 constraints를 담는다.
current_gfp_context()는 current task의 memalloc_noio, memalloc_nofs 같은 context를 반영한다. 예를 들어 filesystem reclaim recursion을 피하기 위해 caller가 GFP_KERNEL을 줘도 effective GFP가 더 제한될 수 있다.
이 단계의 reading point:
- caller의 GFP flags가 그대로 쓰이지 않는다.
- zonelist/zoneidx/migratetype으로 해석된다.
- fastpath 실패 시 slowpath policy는 GFP retry flags에 크게 좌우된다.
14. get_page_from_freelist: scanning zones
get_page_from_freelist()는 allocation context에 맞는 zone들을 순서대로 보면서 page를 얻으려 한다. 핵심 loop는 for_next_zone_zonelist_nodemask()류 macro로 표현된다.
Pseudo-code:
for each zone in zonelist allowed by nodemask/highest_zoneidx:
if cpuset / mempolicy / dirty limits reject:
continue
if !zone_watermark_fast(zone, order, mark, highest_zoneidx, alloc_flags, gfp):
maybe wake kswapd
maybe try reclaim/compaction variants
continue
page = rmqueue(zone, order, migratetype, alloc_flags)
if page:
prep_new_page(page, order, gfp, alloc_flags)
return page
return NULL
여기서 allocation success는 단순히 free pages가 있느냐가 아니라 “watermark + reserve + zone constraints를 만족하느냐”다. 예를 들어 zone에 free pages가 있어도 min watermark 아래로 내려가면 일반 allocation은 실패하고 reclaim path를 타야 할 수 있다.
Zone scan order는 NUMA locality와 fallback policy가 섞인다.
preferred node local zone
-> fallback zones in same node
-> fallback nodes by zonelist order
하지만 cpuset, mempolicy, nodemask가 있으면 후보가 더 제한된다.
get_page_from_freelist()는 fastpath인 동시에 정책이 많이 들어간 function이다. page allocator bug를 읽을 때 이 function의 alloc_flags와 gfp_mask interpretation을 잘 봐야 한다. ALLOC_NO_WATERMARKS, ALLOC_HIGH, ALLOC_HARDER, ALLOC_OOM, ALLOC_CMA 같은 internal flags가 watermark behavior를 바꾼다.
15. Watermark check: why free pages can still be unavailable
zone_watermark_fast()는 “이 zone에서 allocation해도 reserve를 침범하지 않는가?”를 빠르게 판단한다. Order-0 allocation은 fast check가 특히 중요하다.
Conceptual formula는 다음과 같다.
usable_free = zone_free_pages
- highatomic_reserve_if_needed
- cma_pages_if_not_allowed
- lowmem_reserve[highest_zoneidx]
needed = watermark + (1 << order) + fragmentation/order adjustment
usable_free >= needed ?
yes -> allocation can proceed
no -> zone considered insufficient
실제 source는 high-order allocation에 대해 free_area[order..]를 확인해서 suitable free block이 있는지도 본다. Order-0은 free page count만으로 빠르게 판단할 수 있지만, high-order는 total free pages가 많아도 contiguous block이 없으면 실패한다.
Watermark level은 상황에 따라 다르다.
WMARK_MIN : minimum reserve
WMARK_LOW : kswapd wake threshold
WMARK_HIGH : kswapd target
Fast allocation은 보통 low/min watermark와 internal flags를 이용한다. GFP_ATOMIC은 emergency reserve 접근 가능성이 있고, GFP_KERNEL은 reclaim/compaction으로 돌 수 있다.
이 단계에서 중요한 misconception 하나:
/proc/meminfo에 free memory가 있어도 allocation이 실패할 수 있다.이유는 다음과 같다.
- 원하는 zone에 free pages가 없을 수 있다.
- watermark reserve를 침범해야 할 수 있다.
- high-order contiguous block이 없을 수 있다.
- cpuset/nodemask/mempolicy가 후보 node를 제한할 수 있다.
GFP_ATOMIC같은 context는 slowpath가 제한된다.- CMA/highatomic/isolated pageblock이 일반 allocation에 열려 있지 않을 수 있다.
16. Per-CPU pageset: order-0 allocation fastpath
Order-0 page allocation은 매우 빈번하다. 매번 zone lock을 잡고 buddy free list를 조작하면 scalability가 나쁘다. 그래서 Linux는 per-cpu pageset(PCP)을 둔다.
PCP는 각 CPU별 작은 page cache다. Common path:
alloc order-0:
local_lock pcp
if pcp list for migratetype not empty:
pop page
unlock
return
else:
refill pcp from buddy in batch
pop one page
unlock
return
PCP 장점:
- zone lock contention 감소
- cache locality 개선
- interrupt disable/local lock 범위로 빠른 order-0 allocation/free 처리
- batch refill/drain으로 buddy lock 횟수 감소
PCP는 무한히 page를 들고 있지 않는다. high/low/batch threshold가 있고, free path에서도 PCP가 너무 많아지면 buddy로 batch drain한다.
Simplified allocation flow:
rmqueue()
if order == 0 and pcp_allowed:
return rmqueue_pcplist()
else:
return rmqueue_buddy()
rmqueue_pcplist()는 PCP lock을 잡고 __rmqueue_pcplist()를 호출한다. PCP list가 비어 있으면 rmqueue_bulk()가 zone buddy에서 여러 page를 가져와 PCP list를 채운다.
이때 migratetype별 list가 중요하다. MIGRATE_MOVABLE request가 계속 오면 movable list에서 page를 꺼내려고 한다. 부족하면 buddy fallback에서 다른 migratetype block을 가져올 수 있다.
PCP 때문에 “free page가 buddy free_area에 바로 보이지 않는다”는 현상도 생긴다. /proc/buddyinfo는 buddy free area 중심이고 PCP에 잡힌 page는 별도 accounting이 필요하다.
17. Buddy free lists: orders, blocks, and PageBuddy
Buddy allocator는 power-of-two contiguous block을 관리한다. 각 zone은 order별 free list를 갖는다.
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
개념적으로:
zone->free_area[0] : 1-page blocks
zone->free_area[1] : 2-page blocks
zone->free_area[2] : 4-page blocks
...
zone->free_area[MAX_ORDER-1]
Free block의 first page에는 PageBuddy flag가 세팅되고, page_private(page)에 order가 저장된다. 같은 block 안의 나머지 pages는 head가 아니므로 free list node 역할을 하지 않는다.
Buddy relation:
buddy_pfn = pfn ^ (1 << order)
예를 들어 order 3 block은 8 pages다. PFN 64의 order 3 buddy는 64 ^ 8 = 72다. 두 buddy block이 모두 free이고 같은 order/migratetype 조건을 만족하면 merge해서 order 4 block이 된다.
Allocation은 큰 block을 쪼갠다.
need order 0
free_area[0] empty
free_area[1] empty
free_area[2] has block B (4 pages)
remove B from order 2
split into:
one order 1 buddy goes to free_area[1]
split remaining order 1 into:
one order 0 buddy goes to free_area[0]
one order 0 returned to caller
Free는 반대로 merge한다.
free order 0 page P
if buddy order 0 is free:
remove buddy
merge to order 1
if order 1 buddy free:
merge ...
insert final block into free_area[final_order]
이 textbook algorithm 위에 Linux는 migratetype, pageblock, PCP, watermark, compaction, isolation policy를 얹는다.
18. rmqueue_buddy() and __rmqueue(): getting a block from buddy
PCP에서 처리되지 않는 allocation은 buddy path로 내려간다. 대표적으로 high-order allocation, PCP refill, 또는 PCP를 사용할 수 없는 context가 그렇다.
Simplified call graph:
rmqueue()
-> rmqueue_buddy(preferred_zone, zone, order, alloc_flags, migratetype)
lock zone
page = __rmqueue(zone, order, migratetype, alloc_flags)
unlock zone
return page
__rmqueue()는 zone lock이 잡힌 상태에서 실제 buddy free list를 조작한다. 먼저 requested migratetype/order에서 block을 찾고, 실패하면 fallback strategy를 적용한다.
High-level pseudo-code:
__rmqueue(zone, order, migratetype, alloc_flags):
page = __rmqueue_smallest(zone, order, migratetype)
if page:
return page
if highatomic reserve applicable:
try MIGRATE_HIGHATOMIC
for fallback migratetype in fallback_order:
page = __rmqueue_smallest(zone, order, fallback)
if page:
maybe steal pageblock / change migratetype
return page
return NULL
__rmqueue_smallest()는 requested order 이상에서 가장 작은 available block을 찾는다. 찾으면 del_page_from_free_list()로 free list에서 제거하고, expand()로 필요한 order까지 split한다.
핵심 invariant:
- free list에 있는 page는
PageBuddy상태다. - allocated page는
PageBuddy가 clear되어야 한다. - order metadata는 free block head에만 의미 있다.
- zone free counters와 migratetype counters가 일관되어야 한다.
Buddy allocator corruption bug는 대개 double free, wrong order free, page flag corruption, use-after-free가 원인이다. DEBUG_VM/page_owner/KASAN 같은 tool이 이 지점을 잡는 데 중요하다.
19. expand(): splitting a higher-order block
expand()는 high-order free block을 caller가 원하는 lower order로 쪼갠다. Textbook buddy의 split operation이다.
Example:
request order = 1
found block order = 4 // 16 pages
split order 4 -> two order 3 blocks
keep first half for further split
put second half into free_area[3]
split order 3 -> two order 2 blocks
keep first half
put second half into free_area[2]
split order 2 -> two order 1 blocks
return first half to caller
put second half into free_area[1]
Pseudo-code:
while (high > low) {
high--;
size >>= 1;
buddy = page + size;
add_to_free_list(buddy, zone, high, migratetype);
set_buddy_order(buddy, high);
}
return page;
Split된 buddy들은 free list에 들어가고 PageBuddy + order metadata를 가진다. 반환되는 block은 final order에 맞는 allocated block이므로 PageBuddy가 clear된 상태여야 한다.
이 splitting 때문에 high-order allocation은 fragmentation에 민감하다. System에 free memory가 많아도 order 9 block이 없으면 2 MiB contiguous allocation은 실패할 수 있다. THP, hugeTLB, large DMA buffer, high-order kmalloc() 등은 compaction이나 reserved pool 없이 실패 가능성이 있다.
Linux는 migratetype/pageblock policy로 fragmentation을 완화하지만 완전히 없애지는 못한다. 따라서 driver에서 큰 physically contiguous allocation을 runtime에 요구하는 것은 위험하다. 가능한 경우 scatter-gather DMA, vmalloc(), dma_alloc_coherent()의 proper API, CMA reservation 등을 고려해야 한다.
20. Allocation post-processing: prep_new_page()
Buddy/PCP에서 page를 꺼냈다고 바로 caller에게 주는 것은 아니다. prep_new_page() 계열 function이 allocation된 page를 정리한다.
대표 작업:
post_alloc_hook()
-> debugging hooks
-> page poisoning / init-on-alloc
-> KASAN/KMSAN/KFENCE interaction
-> set page owner / page table checks if enabled
compound page setup if high-order + __GFP_COMP
pfmemalloc flag handling
reference count initialization
zeroing if __GFP_ZERO
__GFP_ZERO가 있으면 page content를 zero-fill한다. User anonymous page fault path에서는 보안상 zeroed page가 필요하다. Kernel allocation도 caller가 zeroing을 요청할 수 있다.
Debug/security options에 따라 allocation cost가 크게 달라질 수 있다.
CONFIG_DEBUG_PAGEALLOC
CONFIG_PAGE_POISONING
CONFIG_KASAN
CONFIG_KMSAN
CONFIG_KFENCE
CONFIG_PAGE_OWNER
init_on_alloc=1
init_on_free=1
이 옵션들은 memory bug detection과 info leak mitigation에 유용하지만, allocator fastpath overhead를 늘릴 수 있다.
Important subtlety:
- Buddy allocator는 physical page block을 공급한다.
prep_new_page()는 그 page를 safe/consistent allocated state로 만든다.- SLUB나 page fault path는 그 위에서 object/user page initialization을 추가로 수행한다.
따라서 alloc_page() cost를 분석할 때 free list operation만 보면 안 되고 post-allocation hooks도 봐야 한다.
21. Slowpath: reclaim, compaction, retry, and OOM
Fastpath가 실패하면 __alloc_pages_slowpath()로 들어간다. Slowpath는 Linux MM의 복잡함이 집중된 곳이다.
Slowpath가 시도하는 일:
1. Wake kswapd
2. Try direct reclaim if allowed
3. Try compaction for high-order allocation
4. Retry depending on GFP retry policy
5. Access reserves if allocation class allows
6. Invoke OOM killer if appropriate
7. Fail and return NULL if policy permits
GFP flags가 slowpath behavior를 결정한다.
GFP_KERNEL
-> sleep/reclaim/compaction 가능
GFP_ATOMIC
-> sleep 불가, slowpath 제한, reserves 사용 가능성
__GFP_NORETRY
-> aggressive retry 안 함
__GFP_RETRY_MAYFAIL
-> 어느 정도 retry하지만 OOM까지 강하게 가지 않을 수 있음
__GFP_NOFAIL
-> 실패를 caller에게 반환하지 않으려 함; 매우 조심해서 써야 함
High-order allocation은 slowpath에서 compaction이 특히 중요하다. reclaim은 free pages를 늘리지만 contiguous block을 보장하지 않는다. compaction은 movable pages를 이동시켜 큰 contiguous range를 만들려고 한다.
OOM killer는 “system 전체 memory 부족”일 때만 단순히 실행되는 것이 아니다. cpuset, mempolicy, memcg limit, nodemask 때문에 local OOM이 발생할 수 있다. memcg OOM은 cgroup limit 내에서 task kill을 유발할 수 있다.
Slowpath reading hints:
mm/page_alloc.c
__alloc_pages_slowpath()
should_reclaim_retry()
should_compact_retry()
__alloc_pages_direct_reclaim()
__alloc_pages_direct_compact()
__alloc_pages_may_oom()
Allocator를 이해하려면 fastpath call graph만이 아니라 “왜 fastpath가 실패했고 slowpath가 어떤 권한을 갖는지”를 함께 봐야 한다.
22. Free path: __free_pages() back to PCP or buddy
Allocation의 반대는 free다. Caller가 __free_pages(page, order) 또는 wrapper를 호출하면 page allocator는 page block을 free state로 돌린다.
Simplified flow:
__free_pages(page, order)
-> put_page_testzero / refcount handling
-> free_unref_page() or __free_pages_ok()
-> free_pages_prepare()
// debug checks, poisoning, page flags cleanup
-> if order == 0 and PCP allowed:
free_unref_page_commit()
add to per-cpu list
drain if high
else:
free_one_page()
-> __free_one_page()
-> merge with buddy if possible
-> add final block to free_area[order]
Free path에서 매우 중요한 것은 order correctness다. order 2로 allocated된 4-page block을 order 0으로 네 번 free하면 allocator metadata가 깨진다. 반대로 order 0 page를 order 2로 free하면 unrelated pages를 free list에 넣는 catastrophic corruption이 생긴다.
free_pages_prepare()는 다음을 확인/처리한다.
bad page flags
mapcount/refcount sanity
debug poisoning
KASAN/KMSAN hooks
page owner info update
Buddy merge condition은 대략 다음과 같다.
while order < MAX_ORDER:
buddy = find_buddy(page, order)
if buddy is not free with same order:
break
remove buddy from free list
page = combined_block_head(page, buddy)
order++
insert page into free_area[order]
Migratetype/pageblock isolation 조건 때문에 merge가 제한될 수도 있다. 예를 들어 MIGRATE_ISOLATE pageblock은 일반 free block과 섞이면 안 된다.
PCP free는 allocation fastpath와 마찬가지로 scalability를 위한 것이다. 너무 많은 page가 PCP에 쌓이면 batch로 buddy에 반환된다.
23. Boot handoff: from memblock to buddy
Boot early allocator인 memblock은 영원히 주 allocator로 남지 않는다. mem_init() 근처에서 usable pages가 buddy allocator로 넘어간다.
High-level handoff:
memblock.memory = all RAM ranges
memblock.reserved = kernel/initrd/firmware/etc.
for each PFN in memory ranges:
if PFN valid and not reserved:
initialize struct page
set zone/node
free to buddy
Source path는 architecture마다 wrapper가 다르지만 generic work는 mm/mm_init.c, mm/page_alloc.c, architecture mem_init() 주변에서 확인할 수 있다.
__free_pages_core()는 boot memory / hotplug memory를 buddy에 넣을 때 사용되는 path 중 하나다. 일반 runtime free와 달리, 처음으로 managed page로 편입하는 initialization이 포함된다.
Boot handoff에서 조심해야 하는 것:
memblock.reservedrange는 free하지 않는다.PageReservedflag 처리가 정확해야 한다.- zone
managed_pagesaccounting이 맞아야 한다. - deferred struct page initialization을 쓰는 large-memory system에서는 모든
struct page가 즉시 fully initialized되지 않을 수 있다. - memory hotplug와 boot init path가 일부 logic을 공유한다.
Large memory machine에서는 boot time을 줄이기 위해 deferred page initialization이 사용될 수 있다. 이 경우 일부 struct page initialization이 boot 후 background/threaded 방식으로 진행된다. 그럼에도 allocator가 접근하는 page는 사용 전에 safe state여야 한다.
이 지점이 끝나면 kernel은 이제 regular allocation API를 신뢰할 수 있다. 즉 SLUB allocator가 slab pages를 buddy에서 가져올 수 있고, 일반 kernel subsystems가 kmalloc()을 본격적으로 사용할 수 있다.
24. kmalloc() vs alloc_pages() vs vmalloc()
Kernel memory API 선택은 allocation semantics를 결정한다.
alloc_pages()
returns struct page*
physical contiguous
order-based
good for page-level structures, page tables, DMA-like needs with correct API
kmalloc()
returns void*
virtually contiguous and physically contiguous for small/medium allocations
object-size allocation through SLUB
common kernel heap API
vmalloc()
returns void*
virtually contiguous
physical pages may be non-contiguous
uses page tables to map scattered pages
good for large buffers not requiring physical contiguity
kmalloc()은 small allocations에서 SLUB cache를 사용한다. 예를 들어 kmalloc(96, GFP_KERNEL)은 96 또는 128 byte size class cache에서 object 하나를 꺼낸다. 해당 slab에 free object가 없으면 SLUB가 새 slab page를 buddy allocator에서 allocation한다.
큰 kmalloc()은 allocator configuration에 따라 page allocator path로 더 직접적으로 간다. 그러나 kmalloc()은 여전히 physically contiguous memory를 요구한다는 점이 중요하다. 큰 contiguous allocation은 fragmentation 때문에 실패할 수 있다. 큰 buffer가 physical contiguity를 요구하지 않으면 kvzalloc()/kvmalloc()/vmalloc()을 고려한다.
kvmalloc()류 API는 작은 size는 kmalloc()을 시도하고, 실패하거나 큰 size는 vmalloc()로 fallback할 수 있다.
Rule of thumb:
small kernel object:
kmalloc / kmem_cache_alloc
many same-size objects:
kmem_cache_create + kmem_cache_alloc
large buffer, no physical contiguity:
vmalloc / kvmalloc
DMA buffer:
dma_alloc_coherent / dma_map_* APIs, not raw kmalloc assumptions
raw pages:
alloc_pages
Physical memory allocation을 추적할 때 kmalloc()은 SLUB를 거쳐 결국 buddy로 내려간다는 점이 핵심이다.
25. SLUB overview: the current slab allocator path
Linux의 slab family는 historically SLAB, SLUB, SLOB가 있었다. 현대 mainline에서는 SLUB가 중심이다. SLUB는 small kernel objects를 efficient하게 allocation/free하기 위한 allocator다.
SLUB의 기본 idea:
kmem_cache = same-size objects cache
slab = one or more pages carved into objects
object = caller에게 반환되는 allocation unit
예:
kmalloc-64 cache
slab page A: 64-byte objects 여러 개
slab page B: 64-byte objects 여러 개
...
SLUB는 per-CPU fastpath를 강하게 최적화한다. 각 CPU는 current slab/freelist를 가지고, object allocation은 가능하면 lock 없이 CPU-local freelist에서 pop한다.
Conceptual flow:
kmalloc(80)
-> choose kmalloc-96 or kmalloc-128 size class
-> kmem_cache_alloc(cache)
-> slab_alloc_node()
-> CPU-local freelist has object?
yes: pop object and return
no: slowpath __slab_alloc()
-> partial slab?
-> new slab from buddy?
SLUB가 buddy allocator와 만나는 지점은 new slab allocation이다. Cache에 free object가 충분하면 buddy는 호출되지 않는다. Slab page가 필요할 때 allocate_slab() 계열 function이 alloc_slab_page()를 통해 page allocator를 호출한다.
따라서 small kmalloc()의 common case는 physical page allocation이 아니라 이미 확보된 slab page 안에서 object를 꺼내는 operation이다.
26. kmalloc() size classes and bucket-like behavior
User가 말한 “libc malloc의 bucket”과 kernel kmalloc() size class는 비슷한 면이 있다. 둘 다 arbitrary size request를 fixed size class로 round up한다.
Kernel kmalloc()은 size에 따라 kmalloc-* cache를 선택한다. Typical examples:
kmalloc-8
kmalloc-16
kmalloc-32
kmalloc-64
kmalloc-96
kmalloc-128
kmalloc-192
kmalloc-256
...
Exact size class set은 architecture/config에 따라 달라질 수 있다. Alignment, cacheline, DMA constraints, CONFIG_SLAB_MERGE_DEFAULT, hardened usercopy, randomization, debug options 등이 영향을 줄 수 있다.
kmalloc(100)은 보통 128 byte class 같은 더 큰 bucket에 들어간다. 이때 internal fragmentation이 생긴다.
requested = 100
allocated object size = 128
internal waste = 28 bytes
왜 이렇게 하는가?
- Metadata overhead 감소
- Fast O(1)-ish lookup
- 동일 size object reuse
- Cache locality
- Low fragmentation in common case
- Per-cache debugging/hardening 가능
kmalloc_slab(size, flags) 계열 logic은 request size를 cache로 mapping한다. __do_kmalloc_node() path는 대략 다음을 한다.
if size > KMALLOC_MAX_CACHE_SIZE or large:
__kmalloc_large_node_noprof()
else:
s = kmalloc_slab(size, flags, caller)
ret = slab_alloc_node(s, ...)
즉 kernel heap도 “bucketed allocator”지만, physical page allocation은 slab page replenishment 때 발생한다는 점이 user-space malloc과 다르다.
27. SLUB fastpath: CPU-local freelist
SLUB fastpath는 매우 짧아야 한다. Object allocation이 kernel hot path에 많기 때문이다.
Conceptual fastpath:
slab_alloc_node(cache, gfp, node, addr, orig_size):
c = this_cpu_ptr(cache->cpu_slab)
object = c->freelist
if likely(object):
c->freelist = get_freepointer(cache, object)
return object
return __slab_alloc(...)
실제 source는 freelist hardening, KASAN, debugging, memcg accounting, NUMA node checks, sheaves optimization 등이 추가된다. 하지만 핵심은 per-CPU freelist pop이다.
SLUB는 object 내부에 free pointer를 저장한다. Object가 free 상태일 때 그 memory는 next pointer 역할을 한다. Allocated 상태일 때는 caller data다. 이것은 대부분 allocator가 쓰는 common trick이다.
Security/hardening options:
CONFIG_SLAB_FREELIST_HARDENED
CONFIG_SLAB_FREELIST_RANDOM
CONFIG_INIT_ON_ALLOC_DEFAULT_ON
CONFIG_INIT_ON_FREE_DEFAULT_ON
KASAN/KMSAN/KFENCE
Free pointer encoding/randomization은 use-after-free exploitation을 어렵게 만든다. Debug options는 redzone, poisoning, stack trace tracking 등을 제공할 수 있다.
Fastpath가 실패하는 경우:
- CPU-local freelist empty
- current slab absent
- NUMA node mismatch
- cache debug requiring slowpath
- allocation flags requiring special handling
- per-cpu sheaf empty and refill needed
이 경우 __slab_alloc() slowpath로 가서 partial slab list나 new slab allocation을 시도한다.
28. SLUB slowpath: partial slabs and new slabs from buddy
SLUB slowpath는 free object가 있는 slab을 찾거나 새 slab을 만든다.
Simplified logic:
__slab_alloc(cache, gfp, node):
try CPU partial slabs
try node partial list
if found partial slab:
take slab
update CPU freelist
return object
new = allocate_slab(cache, gfp, node)
if new:
initialize objects/freelist
install as CPU slab
return first object
fail
Partial slab은 일부 object는 allocated, 일부 object는 free인 slab이다. Full slab은 free object가 없다. Empty slab은 모든 object가 free다. SLUB는 empty slab을 계속 들고 있을지, release해서 buddy에 돌려줄지 policy를 가진다.
allocate_slab()은 cache의 object size, alignment, order, flags를 보고 몇 page짜리 slab을 할당한다. 내부적으로 page allocator를 호출한다.
allocate_slab()
-> alloc_slab_page()
-> alloc_pages_node(..., order)
-> buddy allocator
SLUB는 fragmentation을 고려해 higher-order slab allocation이 실패하면 lower order로 fallback할 수 있다. 큰 object cache는 order가 커질 수 있고, 이때 buddy fragmentation 영향이 커진다.
New slab initialization:
set slab metadata
calculate object count
build freelist
apply poisoning/redzone if debug
assign slab->slab_cache
set frozen/partial state
Object allocation 하나가 slowpath에서 새 slab을 만들면, 실제 physical allocation은 page 단위로 일어난다. 이후 같은 slab에서 나오는 여러 object allocation은 buddy를 호출하지 않는다.
29. SLUB free path: object returns, slabs may return pages
kfree(ptr) 또는 kmem_cache_free(cache, ptr)는 object를 SLUB cache에 돌려준다.
Simplified flow:
kfree(ptr)
-> find slab/cache from object address
-> slab_free(cache, slab, object)
-> if CPU-local slab:
push object to CPU freelist
else:
put into slab freelist with proper synchronization
-> if slab becomes empty and policy says release:
discard slab
free pages back to buddy
SLUB free도 allocation처럼 fastpath/slowpath가 있다. CPU-local slab에 속한 object이면 빠르게 freelist에 push할 수 있다. Cross-CPU free, frozen slabs, partial list transition, debug checks가 있으면 slowpath가 된다.
Free object는 다시 free pointer storage로 바뀐다. Hardened freelist가 켜져 있으면 pointer encoding이 적용될 수 있다.
Slab page lifecycle:
buddy page allocated
-> SLUB initializes slab with N objects
-> objects allocated/freed many times
-> slab becomes empty
-> SLUB may keep as partial/empty cache
-> eventually free pages to buddy
따라서 kfree()가 항상 physical page를 free하는 것은 아니다. 대부분은 SLUB freelist에 object를 반환할 뿐이다. Physical memory pressure가 있거나 slab cache shrinker가 동작하거나 empty slab release policy가 triggered될 때 buddy로 page가 돌아간다.
이 점은 user-space malloc과도 비슷하다. free()가 항상 kernel에 memory를 반환하지 않는 것처럼, kfree()도 항상 buddy에 page를 반환하지 않는다.
30. Kernel allocation trace: kmalloc(100, GFP_KERNEL)
Concrete trace를 보자.
void *p = kmalloc(100, GFP_KERNEL);
Likely fastpath:
kmalloc
-> __kmalloc_noprof
-> __do_kmalloc_node(size=100)
-> kmalloc_slab(100)
chooses kmalloc-128 cache // example
-> slab_alloc_node(cache=kmalloc-128)
CPU-local freelist non-empty
pop object
maybe init/harden/debug hooks
-> return p
이 경우 buddy allocator는 호출되지 않는다. 이미 kmalloc-128 slab page가 있었기 때문이다.
If CPU freelist empty:
slab_alloc_node
-> __slab_alloc
-> try CPU partial
-> try node partial
-> found partial slab
-> load freelist into CPU slab
-> return object
아직 buddy는 호출되지 않을 수 있다.
If no partial slab:
__slab_alloc
-> allocate_slab
-> alloc_slab_page
-> alloc_pages_node(gfp, order)
-> __alloc_pages
-> get_page_from_freelist
-> PCP/buddy
-> initialize slab objects
-> return one object
이때 physical page allocation이 발생한다. Allocation size는 100 byte가 아니라 slab order 단위다. 예를 들어 one page slab이면 4 KiB page 하나가 buddy에서 나온다. 그 page 안에 128 byte objects가 여러 개 들어간다.
Free side:
kfree(p);
Likely:
kfree
-> slab_free
-> push object to freelist
Buddy free는 slab 전체가 empty/released될 때만 발생한다.
31. Observing kernel allocators in a running system
Allocator를 이해하려면 source reading과 runtime observation을 같이 해야 한다.
Useful files:
cat /proc/buddyinfo
cat /proc/pagetypeinfo
cat /proc/zoneinfo
cat /proc/slabinfo
cat /proc/meminfo
/proc/buddyinfo는 node/zone/order별 free block 수를 보여준다. High-order fragmentation을 볼 때 유용하다.
Node 0, zone Normal 1234 567 89 10 ...
order0 order1 order2 ...
/proc/pagetypeinfo는 migratetype별 free blocks와 pageblock info를 보여준다. Fragmentation debugging에 더 좋다.
/proc/slabinfo는 slab cache별 object size, active objects, slabs 등을 보여준다. slabtop도 편하다.
Tracepoints/perf/ftrace:
sudo trace-cmd record -e kmem:mm_page_alloc -e kmem:mm_page_free sleep 5
sudo trace-cmd report
sudo trace-cmd record -e kmem:kmalloc -e kmem:kfree sleep 5
sudo trace-cmd report
sudo perf record -e kmem:mm_page_alloc -a sleep 5
sudo perf script
Kernel config에 따라 tracepoint availability가 다르다. page_owner를 켜면 page allocation stack trace를 얻을 수 있다.
# boot param
page_owner=on
cat /sys/kernel/debug/page_owner
SLUB debugging:
# boot param examples
slub_debug
slub_debug=FZPU
주의: allocator tracing/debugging은 overhead가 크고 timing을 바꿀 수 있다. Production machine에서 사용할 때는 신중해야 한다.
32. User-space boundary: malloc() is not a syscall
중요한 사실: malloc()은 system call이 아니다. malloc()은 libc function이다. 대부분의 calls는 user-space allocator metadata만 만지고 return한다.
User program:
void *p = malloc(64);
free(p);
Possible path:
malloc(64)
-> glibc tcache has 64-byte-ish chunk
-> pop chunk
-> return
이 경우 kernel은 전혀 개입하지 않는다. syscall도 없고 page fault도 없을 수 있다.
Kernel이 개입하는 경우는 크게 두 가지다.
- Allocator가 heap/arena를 확장해야 해서
brk()또는mmap()을 호출한다. - Process가 previously mapped but not physically backed virtual page를 access해서 page fault가 발생한다.
brk()/mmap()은 virtual address space를 조작한다. Anonymous memory mapping은 보통 lazy allocation이라서, system call return 시점에 physical page가 다 붙지 않는다.
Example:
void *p = malloc(1 << 20); // maybe mmap or brk extension
// no touch yet
p[0] = 1; // page fault; physical page allocated here
물론 allocator metadata write나 calloc() zeroing, malloc() internal initialization 때문에 일부 pages가 즉시 touched될 수 있다. 하지만 principle은 virtual reservation과 physical allocation을 분리하는 것이다.
CS:APP malloc lab의 mem_sbrk() model은 teaching용으로 heap을 monotonically extend하는 단순 model이다. Real glibc는 brk만 쓰지 않고 mmap, multiple arenas, tcache, fastbins, small/large bins, trimming, thresholds, thread-local cache 등을 사용한다.
33. brk()/sbrk() and mmap(): what the kernel sees
brk()는 process의 program break를 변경한다. Traditional heap은 data segment 끝에서 위로 자란다.
low addresses
text
data/bss
heap via brk/sbrk ---- grows upward
...
mmap region
stack ---- grows downward
high addresses
sbrk(increment)는 old program break를 반환하고 break를 increment만큼 이동시키는 libc wrapper다. Modern portable application은 직접 sbrk()를 쓰면 안 되고 malloc()을 사용해야 한다.
mmap()은 새로운 VMA를 만든다. Anonymous private mapping이면 file backing 없이 zero-initialized memory처럼 동작한다.
void *p = mmap(NULL, len,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS,
-1, 0);
glibc malloc은 보통 다음처럼 선택한다.
small/medium allocations:
arena heap에서 chunk를 찾음
부족하면 main arena는 brk로 top chunk 확장 가능
non-main arena는 mmap 기반 heap segments 사용 가능
large allocations:
mmap threshold 이상이면 direct mmap 사용 가능
정확한 threshold는 glibc tunable와 dynamic adjustment에 따라 달라진다. 단순히 “128 KiB 이상은 항상 mmap” 같은 fixed rule로 외우면 위험하다.
Kernel 관점:
brk syscall:
mm_struct의 brk range 확장/축소
VMA 조정
physical page는 보통 lazy
mmap syscall:
new VMA 생성
page table entry는 initially not present
physical page는 first touch fault에서 allocation
munmap()은 mapping을 제거한다. 이미 physical pages가 있었다면 unmap/release path를 통해 page refcount가 줄고 buddy로 돌아갈 수 있다.
34. Page fault path: when user virtual memory becomes physical memory
User-space malloc()이 kernel에게 virtual memory를 얻은 뒤, 실제 physical page allocation은 page fault에서 일어나는 경우가 많다.
Simplified anonymous write fault:
CPU store to address p
-> PTE not present
-> page fault exception
-> arch page fault handler
-> handle_mm_fault()
-> VMA lookup and permission check
-> anonymous fault handler
-> alloc_zeroed_user_highpage_movable() or equivalent
-> alloc_pages(GFP_HIGHUSER_MOVABLE, order=0)
-> buddy allocator
-> install PTE
-> return to user instruction
-> store retries and succeeds
Read fault는 zero page mapping으로 최적화될 수 있다. Anonymous read-only zero page는 physical zero page를 share해서 map할 수 있고, write가 발생하면 COW fault로 private page를 allocate한다.
Copy-on-write fork case:
parent has anonymous page
fork()
-> parent/child PTE read-only COW
child writes
-> write fault
-> allocate new page
-> copy old content
-> install writable PTE
이 path도 결국 buddy allocator로 내려간다. 하지만 caller는 user program의 single store instruction일 뿐이다.
따라서 “malloc이 언제 physical memory를 먹는가?”의 답은 workload dependent다.
malloc()내부에서 metadata를 touch하면 일부 page fault 발생 가능calloc()은 allocator/kernel optimization에 따라 zero pages lazily/actively 처리 가능- 실제 payload를 쓰는 순간 page fault로 physical page allocation
mmap(MAP_POPULATE)나mlock()등은 prefault/populate를 유도할 수 있음
이 separation은 Linux overcommit, lazy allocation, COW efficiency의 핵심이다.
35. glibc malloc overview: ptmalloc lineage
glibc malloc은 ptmalloc 계열 allocator다. dlmalloc에서 출발해 multi-thread arenas, tcache 등 glibc-specific features가 추가되었다. Source는 glibc/malloc/malloc.c에 큰 단일 implementation으로 존재한다.
Major components:
chunk : allocator metadata + user payload
arena : heap state with bins and top chunk
tcache : per-thread cache for small chunks
fastbins : singly-linked lists for small recently freed chunks
small bins : exact-size doubly-linked bins
large bins : size-ordered larger free chunks
unsorted bin : freshly freed/coalesced chunks staging area
top chunk : wilderness chunk at end of arena heap
mmap chunks : large allocations directly backed by mmap
glibc malloc은 size request를 internal chunk size로 변환한다. Alignment, minimum chunk size, header overhead가 반영된다.
Simple request:
p = malloc(24);
Possible internal size:
request 24
+ header/alignment
-> chunk size maybe 32 or 48 depending ABI/alignment
Thread-local tcache가 있으면 small allocation/free의 common path는 lock-free 또는 low-lock userspace operation이다.
malloc(size)
-> checked_request2size
-> tcache bin lookup
-> if hit: pop and return
-> else arena path _int_malloc
Free:
free(ptr)
-> if small and tcache bin has room:
push to tcache
else:
arena _int_free path
이 구조 때문에 malloc()/free() 대부분은 kernel syscall 없이 끝난다.
36. glibc chunk format: metadata in front of payload
glibc malloc은 user pointer 바로 앞에 chunk metadata를 둔다. Conceptual layout:
chunk base:
prev_size // previous chunk size if previous is free
size // current chunk size + flag bits
fd/bk // free chunk list pointers, when free
fd_nextsize/bk_nextsize // large bin pointers, when large free
user pointer:
payload...
Allocated chunk에서는 payload 영역을 program이 쓴다. Free chunk에서는 payload의 앞부분이 bin linked-list pointer로 재사용된다.
size field low bits에는 flags가 들어간다.
PREV_INUSE : previous adjacent chunk is in use
IS_MMAPPED : chunk allocated via mmap
NON_MAIN_ARENA : belongs to non-main arena
PREV_INUSE bit는 coalescing optimization에 중요하다. 현재 chunk가 free될 때 previous chunk가 free인지 빠르게 알 수 있다. Previous가 free이면 prev_size를 이용해 backward coalescing한다.
Boundary-tag style coalescing:
free current chunk C
if previous chunk free:
merge prev + C
if next chunk free:
merge C + next
insert merged chunk into appropriate bin
Allocated chunk에는 footer를 두지 않아 overhead를 줄인다. Free chunk에서 필요한 metadata를 payload area에 둔다.
Security hardening:
- safe-linking for singly-linked lists such as tcache/fastbins
- pointer mangling using ASLR-derived bits
- consistency checks for bin unlink
- double-free detection in tcache path
Allocator metadata corruption은 classic heap exploitation target이기 때문에 modern glibc는 많은 integrity checks를 갖는다.
37. glibc tcache: per-thread buckets
glibc의 tcache는 “bucket”이라는 표현에 가장 가까운 구조다. Tcache는 thread-local small chunk cache다.
Conceptually:
tcache->entries[bin_index] // singly-linked list
tcache->counts[bin_index] // number of chunks in bin
각 bin은 특정 size class를 담당한다. Free된 small chunk는 가능하면 tcache bin에 들어간다. 이후 같은 size allocation이 오면 arena lock 없이 tcache에서 pop한다.
Pseudo allocation:
malloc(size):
tbytes = request2size(size)
tc_idx = csize2tidx(tbytes)
if tcache exists and tcache->entries[tc_idx] non-empty:
return tcache_get(tc_idx)
else:
return _int_malloc(arena, size)
Pseudo free:
free(ptr):
size = chunksize(ptr)
tc_idx = csize2tidx(size)
if size eligible and tcache count < tcache_count:
tcache_put(ptr, tc_idx)
return
else:
_int_free(arena, ptr)
Tcache의 장점:
- Arena lock contention 감소
- Small allocation/free fastpath
- Cache locality 개선
- Multi-thread workloads에서 scalable
단점/tradeoff:
- Thread별 cache 때문에 memory footprint 증가 가능
- Free된 memory가 arena/system으로 즉시 돌아가지 않음
- Security hardening 필요
- Long-lived idle thread가 tcache에 memory를 들고 있을 수 있음
Tcache bin count와 max size는 glibc tunable로 조정 가능하다. Default values는 glibc version/config에 따라 달라질 수 있으므로 source/tunables를 확인해야 한다.
38. glibc fastbins: small, no-immediate-coalescing lists
Fastbins는 tcache 이전부터 있던 small chunk fastpath다. Fastbin은 작은 recently freed chunks를 singly-linked list에 보관한다. 중요한 특징은 즉시 coalescing하지 않는다는 것이다.
왜 coalescing을 미루는가?
- Small malloc/free churn에서 adjacent merge/split cost를 줄임
- Fast O(1) push/pop
- Later consolidation 시 bulk coalescing
Conceptual structure:
fastbinsY[0] -> chunks of size class A
fastbinsY[1] -> chunks of size class B
...
Free path:
if chunk size <= max_fast and not going to tcache:
push into fastbin
mark chunk as in-use from neighbor perspective
return
“Mark as in-use”가 subtle하다. Fastbin chunk는 logical free지만 adjacent chunk coalescing 관점에서는 아직 in-use처럼 취급된다. 나중에 malloc_consolidate()가 fastbins를 비우며 real coalescing을 수행한다.
Allocation path:
if request size matches fastbin and bin non-empty:
pop chunk from fastbin
return
Tcache가 enabled인 modern glibc에서는 many small frees/allocs가 tcache를 먼저 탄다. Fastbin은 tcache miss/overflow, arena path에서 여전히 중요하다.
Security 측면에서 fastbin은 classic double-free / freelist corruption attack surface였다. Modern glibc는 safe-linking, consistency checks, tcache double-free detection 등으로 방어한다.
39. glibc small bins, large bins, unsorted bin, top chunk
Tcache/fastbin으로 처리되지 않는 free chunks는 arena bins로 들어간다.
Unsorted bin은 freshly freed/coalesced chunks가 먼저 들어가는 staging area다. 다음 malloc에서 unsorted bin을 검사하며 immediate reuse 가능성을 본다. 맞지 않으면 size에 따라 small/large bin으로 분류된다.
Small bins는 exact size class doubly-linked lists다. 같은 size chunks끼리 모여 있어서 allocation이 빠르다.
Large bins는 큰 chunks를 size-ordered 방식으로 관리한다. Exact fit이 드문 큰 allocation에서 적절한 fit을 찾기 위한 구조다.
Top chunk는 arena heap의 끝, 즉 wilderness chunk다. Arena에서 적절한 free chunk를 찾지 못하면 top chunk를 split해서 allocation할 수 있다. Top chunk가 부족하면 system memory를 더 얻는다.
Main arena growth:
top chunk insufficient
-> sysmalloc
-> maybe brk/MORECORE to extend heap
-> maybe mmap for large request
Non-main arena:
arena heap segments often mmap-backed
grow_heap/new_heap path
Large allocation:
if size >= mmap_threshold and mmap available:
mmap direct chunk
free -> munmap possible
mmap_threshold, trim_threshold, arena count, tcache parameters 등은 tunable이다. glibc는 workload에 맞춰 일부 threshold를 dynamic하게 조정할 수 있다.
이 구조는 CS:APP malloc lab의 implicit/explicit free list보다 훨씬 복잡하지만, 핵심 원리는 같다.
- size classing
- splitting
- coalescing
- segregated free lists
- top chunk / heap extension
- large allocation special path
40. glibc _int_malloc: high-level allocation path
glibc __libc_malloc()의 top-level path는 대략 다음과 같다.
__libc_malloc(bytes)
-> if tcache initialized and size eligible:
try tcache bin
if hit return
-> if single-thread:
use main_arena without full arena_get overhead
else:
arena_get
-> _int_malloc(arena, bytes)
-> if fail maybe retry with another arena
-> return pointer
_int_malloc() 내부 conceptual order:
1. Normalize request size
2. If fastbin size:
try fastbin
3. If smallbin size:
try exact smallbin
4. Process unsorted bin
maybe exact/useful chunk found
otherwise bin chunks
5. For large request:
search large bins
6. Try top chunk split
7. sysmalloc for more memory
Tcache interactions:
- tcache hit이면
_int_malloc()에 들어가지 않는다. - arena path에서 chunks를 찾을 때 tcache prefill이 일어날 수 있다.
- free path에서도 tcache가 먼저 chunks를 흡수한다.
sysmalloc()은 kernel boundary 근처다. 여기서 glibc는 mmap() 또는 brk()/MORECORE를 통해 process address space를 늘리려 한다. 그러나 sysmalloc()이 곧 physical page allocation이라는 뜻은 아니다. Kernel VMA 생성 후 실제 physical pages는 page fault에서 붙을 수 있다.
Allocation result가 mmapped chunk인지 arena chunk인지에 따라 free path도 다르다.
arena chunk:
free -> bins/tcache/fastbin, maybe trim later
mmap chunk:
free -> munmap directly possible
이 차이가 large allocation RSS behavior에 큰 영향을 준다.
41. glibc _int_free: high-level free path
free(ptr)는 pointer가 NULL이면 no-op이다. Non-NULL이면 chunk metadata를 찾아 size/flags를 보고 path를 결정한다.
Top-level conceptual flow:
__libc_free(ptr):
if ptr == NULL:
return
chunk = mem2chunk(ptr)
if chunk is mmapped:
munmap_chunk(chunk)
return
maybe tcache_put(chunk)
if tcache accepted:
return
arena = arena_for_chunk(chunk)
_int_free(arena, chunk)
_int_free() path:
if fastbin-eligible:
push fastbin
return
else:
consolidate with previous/next free chunks
if reaches top chunk:
merge into top
maybe trim to system if large enough
else:
put merged chunk into unsorted bin
Tcache 때문에 많은 small frees는 arena lock도 잡지 않고 끝난다. Tcache가 full이거나 size가 eligible하지 않으면 arena path로 간다.
Coalescing cases:
prev in-use, next in-use:
insert C into unsorted bin
prev free, next in-use:
unlink prev, merge prev+C, unsorted
prev in-use, next free:
unlink next, merge C+next, unsorted
prev free, next free:
unlink both, merge prev+C+next, unsorted
Top chunk merge:
if freed chunk adjacent to top:
top = merged chunk
if top size > trim_threshold:
brk shrink or madvise/trim path
But free() does not guarantee memory returns to OS. Tcache/fastbins/bins/top chunk may keep it for reuse. Direct mmap chunks are more likely to be returned via munmap().
42. Arenas and multi-threading in glibc malloc
Multi-threaded allocation needs concurrency control. glibc uses multiple arenas to reduce lock contention.
Conceptually:
main_arena
arena 1
arena 2
...
Each arena has bins, top chunk, mutex, and heap segments. Threads are assigned arenas; if contention occurs or thread count grows, additional arenas may be created up to limits.
Tcache is per-thread and sits above arenas. So common small allocation/free does not need arena lock.
thread local tcache hit:
no arena lock
tcache miss:
acquire arena
_int_malloc
maybe refill tcache
Tradeoffs:
- More arenas reduce lock contention.
- More arenas can increase memory footprint and fragmentation.
- Memory freed by one thread may remain in that thread’s tcache/arena and not be immediately reusable by another thread.
- Long-running services can show RSS growth due to arena/tcache retention.
Relevant tunables/environment knobs include:
MALLOC_ARENA_MAX
MALLOC_ARENA_TEST
glibc.malloc.tcache_count
glibc.malloc.tcache_max
glibc.malloc.trim_threshold
glibc.malloc.mmap_threshold
Exact names/behavior can vary across glibc versions; consult mallopt, tunables, and source.
Performance implication:
few threads, moderate allocation:
glibc often fine
many threads, high small-object churn:
arena lock and fragmentation can matter
tcmalloc/jemalloc/mimalloc may perform better
memory footprint sensitive:
tcache/arena tuning can help
glibc malloc is a general-purpose default allocator, not always the fastest allocator for every workload.
43. Does glibc still use sbrk() like CS:APP malloc lab?
Answer: yes, but not only sbrk()/brk(), and not in the simple CS:APP way.
CS:APP malloc lab typically gives a fake mem_sbrk() interface. Student allocator extends one contiguous heap and manages blocks inside it. That model teaches boundary tags, free lists, coalescing, splitting, and placement policy.
glibc reality:
small/medium allocations:
may come from arena heap
main arena can grow with brk/MORECORE
large allocations:
may use mmap directly
multi-thread:
non-main arenas often use mmap-backed heap segments
free:
usually returns chunk to allocator, not kernel
direct mmap chunks can munmap
top chunk may be trimmed via brk shrink
So the CS:APP model maps to glibc’s main arena top chunk growth, but misses:
- multiple arenas
- tcache
- fastbins
- segregated small/large bins
- mmap threshold
- dynamic tuning
- security hardening
- thread contention
- lazy physical allocation
- page fault path
- interaction with kernel overcommit
A useful comparison:
CS:APP mem_sbrk:
allocator asks simulated kernel for more heap bytes
memory immediately available in lab array
glibc brk/mmap:
allocator asks real kernel for virtual address space
physical pages may appear later on page fault
allocator metadata and pages interact with VMAs
따라서 “malloc lab처럼 sbrk를 쓰나요?”에 대한 정확한 답은 “main arena growth에는 brk 계열을 쓸 수 있지만, modern malloc은 mmap도 적극적으로 쓰고, 대부분의 malloc/free는 syscall 없이 userspace에서 처리된다”이다.
44. TCMalloc: front-end, middle-end, back-end
TCMalloc은 Google 계열 allocator로, multi-thread scalability와 small allocation fastpath를 강하게 최적화한다. 이름은 Thread-Caching Malloc에서 왔지만 현대 TCMalloc은 per-thread mode뿐 아니라 per-CPU cache mode가 중요하다.
Architecture:
front-end
per-thread or per-CPU cache
small object allocation fastpath
middle-end
TransferCache
CentralFreeList
size-class shared pools
back-end
PageHeap
obtains/release memory from OS
manages spans of pages
Small allocation flow:
malloc(size <= small_max):
size class lookup
per-CPU cache has object?
yes -> pop and return
no -> refill from TransferCache/CentralFreeList
Large allocation:
malloc(large):
go to PageHeap/back-end
allocate span of pages
TCMalloc maps object pointer to size/span metadata using pagemap-like structure. On free, it can identify whether object is small and which size class/span it belongs to.
Strengths:
- Very fast uncontended small allocation
- Per-CPU cache reduces lock contention
- Good for highly multi-threaded services
- Sampling profiler support
- Aggressive central cache design
Tradeoffs:
- Per-CPU/per-thread caches can retain memory
- Behavior depends on cache sizing and release policy
- Replacement allocator integration needs care
- Security hardening profile differs from hardened allocators
TCMalloc’s “page” is allocator-internal page size, not necessarily hardware page size. It manages spans in units that may be 4 KiB, 8 KiB, 32 KiB, etc., depending on build/config.
45. jemalloc: arenas, bins, extents, and decay
jemalloc is another widely used general-purpose allocator, originally associated with FreeBSD/Firefox and used in many server workloads. Its design emphasizes fragmentation control, scalable arenas, profiling, and predictable behavior.
Major concepts:
arena : independent allocation domain
bin : small size class allocator inside arena
slab : page run divided into same-size regions
extent : larger contiguous virtual memory region
tcache : thread cache for small/medium allocations
decay : dirty/muzzy page purging policy
mallctl : runtime control/query interface
Small allocation:
malloc(size):
size class lookup
tcache bin hit?
yes -> return region
no -> arena bin/slab path
Large allocation:
large size:
allocate extent
manage dirty/muzzy state
jemalloc has strong introspection via mallctl and stats. You can query arenas, bins, tcache, extents, decay settings, profiling stats, etc. This makes it attractive for production tuning.
Decay model:
dirty pages : unused pages still containing old data, can be reused quickly
muzzy pages : decommitted/purged-ish state depending platform
decay time : controls when pages are returned/purged
Strengths:
- Good multi-thread scalability
- Often lower fragmentation than naive allocators
- Rich profiling/stats/tuning
- Mature production behavior
- Fine-grained arenas and size classes
Tradeoffs:
- Larger code/config complexity
- Memory retention depends on decay/tcache settings
- Tuning can be nontrivial
- Not always fastest in microbenchmarks against per-CPU TCMalloc/mimalloc variants
jemalloc is often chosen when profiling/fragmentation observability matters as much as raw allocation speed.
46. mimalloc: per-page free-list sharding and secure mode
mimalloc is a modern allocator from Microsoft Research. It emphasizes small code size, consistent performance, locality, and a distinctive page-based design.
Major ideas:
heap : usually thread-local allocation state
segment : larger memory region
page : mimalloc page, contains blocks of one size class
block : allocated object
free list : per-page free lists
mimalloc uses free-list sharding at the page level. Instead of one global list per size class, each mimalloc page has local free lists. This improves locality and reduces contention.
Cross-thread free is handled carefully. If thread A allocates an object and thread B frees it, mimalloc can put it on a concurrent free list with low synchronization overhead, often a single CAS-style operation. Later the owning heap/page collects it.
Strengths:
- Fast small allocations
- Good locality
- Low fragmentation in many workloads
- Simple integration as drop-in allocator
- Secure mode options with guard pages, encoded freelists, randomization
Tradeoffs:
- Different memory retention behavior than glibc/jemalloc
- Secure mode can add overhead
- Production ecosystem may be smaller than glibc/jemalloc/TCMalloc in some environments
- Like all replacement allocators, interaction with language runtimes and libraries must be tested
mimalloc’s design is worth comparing to SLUB: both carve same-size objects from page-like units and rely heavily on local freelists. But mimalloc is user-space and gets virtual memory from OS via mmap/platform APIs, while SLUB is kernel-space and gets physical pages from buddy.
47. Allocator comparison table
아래 table은 common Linux server context에서의 rough comparison이다. “Best”는 workload에 따라 달라진다.
| Allocator | Layer | Small allocation fastpath | Large allocation | Concurrency model | Returns memory to OS | Observability | Typical strengths |
|---|---|---|---|---|---|---|---|
| Linux buddy | kernel physical pages | PCP order-0 | high-order buddy/compaction | per-zone locks + PCP | n/a | /proc/buddyinfo, tracepoints |
page frame management |
| Linux SLUB | kernel object allocator | per-CPU freelist | new slabs from buddy | per-CPU + node partial locks | empty slabs to buddy | /proc/slabinfo, tracepoints |
kernel object allocation |
| glibc malloc | user-space libc | tcache | mmap or arena/top chunk | tcache + arenas | mmap chunks, trimming | mallinfo/malloc_info/limited | default compatibility |
| TCMalloc | user-space replacement | per-CPU/per-thread cache | PageHeap spans | front/middle/back-end | release policy | heap profiler/sampling | multi-thread throughput |
| jemalloc | user-space replacement | tcache bins | extents | arenas + tcaches | decay/purge | mallctl rich stats | fragmentation/stats/tuning |
| mimalloc | user-space replacement | thread/page local free lists | segments/pages | local heaps + concurrent frees | purge/reset policy | stats options | low-latency/locality/simple use |
Key distinctions:
kernel buddy:
physical page frames, privileged, no libc
kernel SLUB:
kernel virtual objects, backed by buddy pages
glibc/tcmalloc/jemalloc/mimalloc:
user virtual memory allocators
obtain address space from kernel
physical pages usually via page faults
Replacement allocators do not replace kernel buddy/SLUB. They replace the user-space implementation behind malloc()/free() in a process. The kernel still handles VMAs, page faults, physical page allocation, reclaim, and cgroups.
48. Workload-driven allocator choices
Allocator choice should be based on allocation profile.
glibc malloc is usually enough when:
- allocation rate is moderate
- compatibility matters
- memory footprint is acceptable
- you do not want allocator dependency/risk
TCMalloc often helps when:
- many threads do frequent small allocations
- allocator lock contention appears in profiles
- service throughput matters
- heap profiling/sampling is useful
jemalloc often helps when:
- fragmentation/RSS observability matters
- you need rich runtime stats/tuning
- workload has many size classes and long-running behavior
- arenas/decay tuning can be exploited
mimalloc often helps when:
- low-latency small allocations matter
- simple drop-in deployment is desired
- cross-thread free patterns exist
- secure mode/locality tradeoffs are attractive
But benchmark with your actual workload. Allocator microbenchmarks can mislead because real performance depends on:
allocation size distribution
lifetime distribution
thread ownership and cross-thread frees
working set size
NUMA locality
page fault rate
RSS limits / cgroup memory.max
transparent huge pages
language runtime behavior
cache/TLB pressure
fragmentation over hours/days
In C++/Rust systems, you may also have layer-specific allocators:
C++ std::pmr / custom pool allocators
Rust GlobalAlloc / jemallocator / mimalloc
object pools
slab-like arenas
bump allocators
region allocators
A specialized allocator at application layer can beat any general-purpose malloc if lifetime/size pattern is known.
49. Where exactly is the kernel boundary for malloc?
A precise boundary table:
| Operation | User-space only? | Kernel syscall? | Physical page allocation? |
|---|---|---|---|
malloc(64) tcache hit |
yes | no | no |
free(64) tcache push |
yes | no | no |
malloc() arena bin hit |
yes, with locks | no | no |
| arena needs more top chunk | no | brk/maybe mmap |
maybe later |
large malloc() via mmap |
no | mmap |
usually later on touch |
| first write to new heap page | no | page fault trap | yes, via buddy |
free() of mmap chunk |
no | munmap |
releases mapped pages if present |
| allocator trims top chunk | no | brk shrink / madvise |
may release |
malloc_trim() |
no | brk/madvise |
may release |
| cgroup reclaim pressure | kernel | no direct user syscall | reclaim pages |
The kernel boundary is not just syscalls. Page fault is also a kernel entry.
malloc call boundary:
user -> maybe syscall
memory access boundary:
user instruction -> page fault -> kernel
This is why measuring only strace can be misleading. strace shows brk, mmap, munmap, madvise, but does not directly show page faults unless you use perf/fault counters.
Useful commands:
strace -e brk,mmap,munmap,madvise ./a.out
perf stat -e page-faults,minor-faults,major-faults ./a.out
/usr/bin/time -v ./a.out
Minor page faults often correspond to anonymous page allocation or mapping existing page cache without disk I/O. Major faults involve I/O.
50. End-to-end trace A: malloc(64) satisfied from tcache
Scenario:
void *p = malloc(64);
Assume current thread’s tcache has a cached chunk for the size class.
Trace:
user code
-> __libc_malloc(64)
-> request2size
-> tcache index
-> tcache_get
-> pop linked-list head
-> return payload pointer
-> user code receives p
Kernel involvement:
syscall? no
page fault? no, unless allocator metadata/chunk page not resident
buddy? no
SLUB? no
Cost center:
- A few userspace loads/stores
- Safe-linking decode
- Possible branch checks
- No arena lock
This is why malloc microbenchmarks can show extremely low latency after warmup.
Now free:
free(p);
Trace:
__libc_free(p)
-> chunk metadata
-> size eligible for tcache
-> tcache bin not full
-> tcache_put
-> return
Again no kernel. RSS does not drop. The memory is retained in thread-local cache for future allocation.
This is analogous to SLUB per-CPU freelist in spirit: a local cache absorbs hot allocation/free churn and avoids global locks. But glibc tcache is process userspace metadata, while SLUB is kernel allocator metadata backed by physical pages.
51. End-to-end trace B: malloc(10 MiB) via mmap and first touch
Scenario:
char *p = malloc(10 * 1024 * 1024);
Assume glibc decides to use direct mmap.
Trace:
user code
-> __libc_malloc
-> size >= mmap_threshold
-> sysmalloc
-> mmap(NULL, length, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0)
-> syscall entry
-> kernel creates VMA
-> returns virtual address
-> return p
At this point, physical memory may not be fully allocated. Page tables may contain no present PTEs for most of the mapping.
First touch:
for (i = 0; i < len; i += 4096)
p[i] = 1;
For each page:
CPU store
-> page fault
-> kernel handle_mm_fault
-> anonymous write fault
-> alloc page from buddy
maybe PCP order-0
-> zero page / clear highpage
-> install writable PTE
-> return to user
Free:
free(p);
If it is an mmapped chunk:
__libc_free
-> munmap_chunk
-> munmap syscall
-> unmap VMA
-> release present pages
-> free pages eventually back to buddy
This path explains why large allocations often return memory to OS more promptly than small arena allocations.
52. End-to-end trace C: kernel alloc_page(GFP_KERNEL)
Scenario:
struct page *page = alloc_page(GFP_KERNEL);
Likely order-0 fastpath:
alloc_page
-> alloc_pages(gfp, 0)
-> __alloc_pages
-> __alloc_frozen_pages_noprof
-> current_gfp_context
-> prepare_alloc_pages
-> get_page_from_freelist
-> scan zonelist
-> zone_watermark_fast
-> rmqueue
-> rmqueue_pcplist
-> pop page from CPU pageset
-> prep_new_page
-> return struct page
If PCP empty:
rmqueue_pcplist
-> rmqueue_bulk
-> zone lock
-> __rmqueue
-> __rmqueue_smallest
-> maybe expand split higher-order block
-> put batch into PCP
-> pop one page
If watermark fails:
get_page_from_freelist returns NULL
-> __alloc_pages_slowpath
-> wake kswapd
-> direct reclaim
-> compaction
-> retry/fail/OOM depending GFP
No user-space allocator is involved. This is pure kernel physical page allocator.
Free:
__free_page(page);
Likely:
free_unref_page
-> put into PCP list
-> maybe drain batch to buddy
Again, buddy coalescing may be delayed until PCP drain.
53. End-to-end trace D: kernel kmalloc(96, GFP_KERNEL)
Scenario:
void *p = kmalloc(96, GFP_KERNEL);
Likely path:
kmalloc
-> __kmalloc_noprof
-> __do_kmalloc_node(size=96)
-> kmalloc_slab(96)
-> choose kmalloc-96 or nearest cache
-> slab_alloc_node(cache)
-> CPU freelist has object
-> pop object
-> return p
No buddy call if slab has free objects.
If no free objects:
slab_alloc_node
-> __slab_alloc
-> get partial slab from CPU/node partial list
-> or allocate_slab
-> alloc_slab_page
-> alloc_pages_node
-> buddy allocator
-> initialize slab freelist
-> return object
Free:
kfree(p)
-> find slab/cache
-> slab_free
-> push object to freelist
-> maybe slab becomes empty
-> maybe release pages to buddy
Important comparison:
kmalloc(96)
request granularity = bytes
actual physical allocation = page(s) only when slab refill needed
alloc_page()
request granularity = page/order
directly consumes physical page allocator
malloc(96)
user-space bytes
may be tcache/arena only
kernel sees nothing unless heap extension or page fault occurs
이 세 traces를 구분하면 “physical allocation이 언제 일어나는가?”가 명확해진다.
54. Fragmentation: internal, external, virtual, and physical
Allocator discussion에서 fragmentation은 여러 종류가 있다.
Internal fragmentation:
request보다 큰 block/object를 준다.
malloc(33) -> 48-byte chunk
kmalloc(100) -> 128-byte object
alloc_pages(order=1) for 6 KiB need -> 8 KiB physical
External fragmentation:
free memory total은 충분하지만 원하는 contiguous block을 만들 수 없다.
many order-0 free pages
no order-9 block
THP allocation fails
Virtual fragmentation:
process virtual address space가 fragmented되어 large contiguous VMA를 만들기 어렵다. 64-bit에서는 보통 덜 심하지만, ASLR/mmap patterns와 long-running process에서 의미가 있다.
Physical fragmentation:
buddy allocator의 high-order blocks가 부족해진다. Kernel high-order allocation, THP, CMA, hugeTLB 등에 중요하다.
Mitigations:
size classes
coalescing
segregated free lists
migratetypes/pageblocks
compaction
reclaim
CMA reserved regions
per-cpu/thread caches with drain policies
decay/purge/trimming
application-level pooling
Tradeoff:
- Caches improve speed but can retain memory.
- Coalescing reduces fragmentation but costs CPU/locks.
- High-order allocation reduces page table/TLB overhead but increases failure risk.
- Returning memory to OS reduces RSS but may hurt future allocation latency.
Allocator design is mostly about balancing these tradeoffs under real workload distributions.
55. NUMA implications
NUMA changes allocation behavior significantly.
Kernel page allocator:
alloc_pages_node(nid, gfp, order)
-> prefer node nid
-> fallback by zonelist if allowed
alloc_pages(gfp, order)
-> current CPU/task memory policy influences preferred node
User-space:
malloc()
-> user allocator chooses virtual chunk
-> first-touch page fault determines physical NUMA placement by default
Default Linux NUMA policy is often first-touch. That means a thread that first writes a page tends to get a page from its local NUMA node. Allocator metadata and application initialization pattern can therefore determine memory locality.
TCMalloc/jemalloc/mimalloc have their own per-thread/per-CPU arenas/caches. These can interact with NUMA locality positively or negatively.
Example issue:
Thread A on node 0 mallocs and initializes buffer
Thread B on node 1 uses buffer heavily
=> memory may remain on node 0, remote accesses from node 1
Mitigations:
numactl --cpunodebind=0 --membind=0 ./app
numactl --interleave=all ./app
Kernel APIs:
alloc_pages_node(nid, gfp, order);
kmalloc_node(size, gfp, nid);
kmem_cache_alloc_node(cache, gfp, nid);
NUMA debugging:
numactl -H
numastat -p <pid>
cat /proc/<pid>/numa_maps
perf c2c / numa profiling tools
For OS research/performance work, always separate allocator latency from NUMA remote-memory latency.
56. Memory cgroups and accounting
Modern Linux systems often run under cgroup v2 memory limits. This changes allocation failure/reclaim behavior.
User-space anonymous page allocation:
page fault
-> allocate physical page
-> charge page to memcg
-> if charge exceeds memory.max:
reclaim within cgroup
maybe memcg OOM
Kernel memory can also be accounted depending on allocation type and configuration. Slab pages may be memcg-accounted. This means a process/cgroup can hit limit even when system-wide free memory exists.
Important files:
cat /sys/fs/cgroup/<cg>/memory.current
cat /sys/fs/cgroup/<cg>/memory.max
cat /sys/fs/cgroup/<cg>/memory.high
cat /sys/fs/cgroup/<cg>/memory.events
Allocator interpretation:
malloc succeeds
but first touch faults later
memcg charge may fail
process may get killed by memcg OOM
This surprises people: malloc() can return non-NULL due to overcommit, but writing to memory later can trigger OOM kill.
Kernel allocations with __GFP_ACCOUNT can be charged to kmem. Slab caches can have memcg variants. This is important for container isolation because kernel memory used on behalf of a cgroup should not be unbounded.
When comparing malloc implementations under containers, measure:
RSS
cgroup memory.current
page faults
allocator retained memory
dirty/muzzy/purged pages
arena/tcache caches
A replacement allocator that improves throughput may increase retained memory and hit cgroup limits sooner if not tuned.
57. Overcommit, RSS, and why malloc() can lie
Linux overcommit means virtual memory allocation success does not always imply physical memory availability.
Modes are controlled by:
cat /proc/sys/vm/overcommit_memory
cat /proc/sys/vm/overcommit_ratio
cat /proc/sys/vm/overcommit_kbytes
Common modes:
0 heuristic overcommit
1 always overcommit
2 strict commit limit
Example:
char *p = malloc(100UL * 1024 * 1024 * 1024);
if (!p) fail();
p[0] = 1; // maybe OK
touch all pages; // may OOM later
Metrics:
VSZ / VIRT:
virtual address space reserved/mapped
RSS:
resident physical pages
PSS:
proportional share of shared pages
Committed_AS:
committed virtual memory estimate
cgroup memory.current:
actual charged memory for cgroup
malloc() returning non-NULL usually means allocator obtained or found virtual heap space. Physical memory pressure appears later via page faults, reclaim, or OOM.
calloc() nuance:
- It returns zeroed memory.
- For large allocations, kernel can provide zero-filled anonymous pages lazily.
- Allocator may avoid explicitly writing all bytes if it relies on fresh zero pages.
- For reused chunks, allocator must ensure zeroing itself.
Therefore, benchmark malloc() alone is often meaningless. Measure malloc + touch + use + free and observe page faults/RSS.
58. Source-reading checklist for latest Linux
When following latest Linux source, use this checklist.
Boot memory detection:
arch/x86/kernel/setup.c
arch/x86/kernel/e820.c
drivers/firmware/efi/
mm/memblock.c
Documentation/core-api/boot-time-mm.rst
Physical memory model:
include/linux/mmzone.h
include/linux/mm_types.h
include/linux/page-flags.h
Documentation/mm/physical_memory.rst
Page allocator:
mm/page_alloc.c
include/linux/gfp_types.h
include/linux/gfp.h
include/trace/events/kmem.h
Reclaim/compaction/OOM:
mm/vmscan.c
mm/compaction.c
mm/oom_kill.c
mm/memcontrol.c
SLUB:
mm/slub.c
include/linux/slab.h
include/linux/slub_def.h
Documentation/mm/slub.rst or admin-guide/mm/slab.rst
User-space glibc:
glibc/malloc/malloc.c
glibc manual: malloc tunables
man 2 brk
man 2 mmap
Runtime observation:
/proc/buddyinfo
/proc/pagetypeinfo
/proc/zoneinfo
/proc/slabinfo
/proc/vmstat
/proc/<pid>/smaps
/proc/<pid>/numa_maps
perf stat -e page-faults,minor-faults,major-faults
trace-cmd record -e kmem:*
Always read source with config in mind. CONFIG_NUMA, CONFIG_TRANSPARENT_HUGEPAGE, CONFIG_MEMCG, CONFIG_SLUB_DEBUG, CONFIG_CMA, CONFIG_KASAN, CONFIG_PREEMPT_RT, and architecture options can materially change paths.
59. Common misconceptions and corrected versions
Misconception 1: malloc() allocates physical memory.
Correct:malloc() manages user virtual heap chunks. Kernel physical page allocation often happens later on page fault.
Misconception 2: free() returns memory to OS.
Correct:
Usually it returns chunk to user-space allocator cache/bin. Direct mmap chunks may munmap; top chunk trimming may return some heap memory.
Misconception 3: kmalloc() directly calls buddy every time.
Correct:
Small kmalloc() usually pops object from SLUB cache. Buddy is used when new slab pages are needed.
Misconception 4: free memory means high-order allocation succeeds.
Correct:
High-order needs contiguous free block and watermark/zone constraints. Fragmentation can cause failure.
Misconception 5: sbrk() is obsolete so malloc never uses brk.
Correct:
Applications should not use sbrk() directly, but glibc main arena can still use brk/MORECORE. Large allocations often use mmap.
Misconception 6: TCMalloc/jemalloc replace kernel allocator.
Correct:
They replace user-space malloc implementation. Kernel buddy/SLUB still handle physical pages/kernel objects.
Misconception 7: RSS drops immediately after free.
Correct:
Allocator caches, arenas, dirty pages, and kernel reclaim policy may retain memory.
Misconception 8: mmap() immediately consumes RAM.
Correct:
Anonymous mmap usually creates virtual mapping. Physical pages are typically allocated on first touch unless populated/locked.
Misconception 9: all page allocation failures mean OOM.
Correct:
Failures can be zone-specific, order-specific, GFP-context-specific, cpuset/memcg-specific, or fragmentation-related.
60. Compact end-to-end diagrams
Kernel page allocation
alloc_page(GFP_KERNEL)
-> alloc_pages(order=0)
-> __alloc_pages
-> get_page_from_freelist
zonelist scan
watermark check
rmqueue
PCP fastpath
or buddy + split
prep_new_page
-> struct page*
Kernel object allocation
kmalloc(100, GFP_KERNEL)
-> kmalloc_slab(100)
-> slab_alloc_node(kmalloc-128)
CPU freelist pop
or partial slab
or allocate_slab
-> alloc_pages
-> void*
User malloc tcache hit
malloc(64)
-> glibc tcache bin
-> return chunk
// no syscall, no kernel allocator
User malloc heap extension
malloc(large or arena exhausted)
-> glibc sysmalloc
-> brk or mmap syscall
-> kernel VMA update
-> user pointer
-> later first touch
-> page fault
-> alloc_pages
Free paths
free(ptr small)
-> tcache/fastbin/bin
-> maybe no kernel
free(ptr mmap chunk)
-> munmap
-> unmap pages
-> buddy eventually
kfree(obj)
-> SLUB freelist
-> maybe slab page returned to buddy
__free_page(page)
-> PCP
-> maybe buddy merge later
The key unifying idea:
User allocators manage virtual chunks.
Kernel SLUB manages kernel objects.
Kernel buddy manages physical page frames.
Page faults and slab refills are the bridges down to buddy.
61. Practical experiments
1. Watch brk/mmap behavior
cat > malloc_trace.c <<'EOF'
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int main() {
void *a = malloc(64);
void *b = malloc(1024 * 1024 * 10);
memset(b, 1, 1024 * 1024 * 10);
free(a);
free(b);
return 0;
}
EOF
gcc -O2 malloc_trace.c -o malloc_trace
strace -e brk,mmap,munmap,madvise ./malloc_trace
2. Separate virtual allocation from physical touch
perf stat -e page-faults,minor-faults,major-faults ./malloc_trace
/usr/bin/time -v ./malloc_trace
Modify program to malloc() but not memset(). Compare page faults/RSS.
3. Observe buddy state
cat /proc/buddyinfo
cat /proc/pagetypeinfo | less
Run memory pressure workload, then compare high-order free blocks.
4. Observe SLUB
cat /proc/slabinfo | head
slabtop
Look for kmalloc-* caches.
5. Trace kernel allocation events
sudo trace-cmd record -e kmem:mm_page_alloc -e kmem:mm_page_free sleep 3
sudo trace-cmd report | head -100
sudo trace-cmd record -e kmem:kmalloc -e kmem:kfree sleep 3
sudo trace-cmd report | head -100
6. Compare malloc implementations
# glibc default
/usr/bin/time -v ./your_workload
# jemalloc, if installed
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 /usr/bin/time -v ./your_workload
# tcmalloc, if installed
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libtcmalloc.so /usr/bin/time -v ./your_workload
# mimalloc, if installed
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libmimalloc.so /usr/bin/time -v ./your_workload
Measure throughput, tail latency, RSS, page faults, cgroup memory, and fragmentation over time.
62. References and source anchors
This document was written as a source-guided reading note. Important upstream anchors:
Linux kernel
Documentation/core-api/boot-time-mm.rstDocumentation/mm/physical_memory.rstarch/x86/kernel/e820.carch/x86/kernel/setup.cmm/memblock.cmm/page_alloc.cmm/slub.cmm/vmscan.cmm/compaction.cmm/oom_kill.cinclude/linux/mmzone.hinclude/linux/gfp_types.hinclude/linux/slab.hinclude/trace/events/kmem.h
glibc
malloc/malloc.cmanual/tunables.teximallopt(3)malloc_info(3)
man pages
brk(2)mmap(2)munmap(2)madvise(2)
Alternative allocators
- TCMalloc design docs: front-end / middle-end / back-end, spans, pagemap
- jemalloc manual: arenas, bins, tcache, mallctl, decay/purge stats
- mimalloc docs: page-local free lists, secure mode, concurrent free handling
Suggested source reading order
1. Documentation/core-api/boot-time-mm.rst
2. arch/x86/kernel/e820.c and setup.c
3. mm/memblock.c
4. Documentation/mm/physical_memory.rst
5. include/linux/mmzone.h
6. mm/page_alloc.c: __alloc_pages -> get_page_from_freelist -> rmqueue
7. mm/page_alloc.c: free path and buddy merge
8. mm/slub.c: kmalloc -> slab_alloc_node -> allocate_slab
9. glibc malloc/malloc.c: __libc_malloc, _int_malloc, _int_free, sysmalloc
10. TCMalloc/jemalloc/mimalloc docs for contrast
One-sentence summary
Linux physical memory allocation starts with firmware memory maps and memblock, becomes node/zone/pageblock-organized buddy allocation, feeds SLUB for kernel objects, and is reached from user-space malloc only indirectly through heap-expanding syscalls and page faults.