Linux Kernel vs. Memory Fragmentation (Part I)

A brief history of defragmentation

Before I start, I want to recommend some good reads. The following articles show you all the efforts of improving high-level memory allocation during Linux kernel development.

Linux buddy memory allocator

Linux uses the buddy algorithm as a page allocator, which is simple and efficient. Linux has made some extensions to the classic algorithm:

  • Per-CPU pageset
  • Group by migration types

Group by migration types

First, you need to understand the memory address space layout. Each processor architecture has a definition. For example, the definition of x86_64 is in mm.txt.

  • Level 1: Direct page table index
  • Level 2: Page middle directory index
  • Level 3: Page upper directory index
  • Level 4: Page 4-level directory index
  • Level 5: Page global index
Intel 5-level paging — Wikipedia
  1. Copy the data of the old page to the new one.
  2. Modify the value of the direct page table entry to the new page frame number.

Analyze external memory fragmentation events

My previous article Why We Disable Linux’s THP Feature for Databases mentioned that you can use ftrace events provided by the kernel to analyze external memory fragmentation events. The procedure is as follows:

echo 1> /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable
cat /sys/kernel/debug/tracing/trace_pipe> ~/extfrag.log
echo 0> /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
PingCAP

PingCAP

PingCAP is the team behind TiDB, an open-source MySQL compatible NewSQL database. Official website: https://pingcap.com/ GitHub: https://github.com/pingcap