Two types of fragmentation:

1. External Fragmentation:
   - Free memory is scattered across multiple locations
   - Total free space is sufficient, but contiguous space is not
   - The Buddy System can help (merge adjacent blocks)
   - But large allocations (order > 4) can still fail

2. Internal Fragmentation:
   - Allocated memory is larger than requested
   - Example: requesting 100 bytes, actually allocating 128 bytes (SLAB)
   - The wasted 28 bytes is internal fragmentation
   - Reduced through finer-grained object pools

Example of external fragmentation:

  Physical memory (256MB) after allocation:
  | 64MB | 32MB | 64MB | 16MB | 80MB |
  Used       Free

  Request 128MB:
  → Total free: 192MB (>128MB)
  → But max contiguous is only 80MB (not enough)
  → Allocation fails!

  Even though total memory is sufficient, fragmentation prevents meeting the large request.

Linux compaction mechanism:

When a large allocation (order >= 1) fails, the kernel starts compaction:

1. Principle of compaction:
   - Scan memory, move allocated pages to one side
   - Gather free pages on the other side
   - Ultimately produce large contiguous free areas

2. Compaction trigger:
   - alloc_pages fails (order >= 1)
   - Watermark check fails
   - Calls compact_zone(order)

3. Compaction process:
   - sync: Pause other operations, scan the zone
   - isolate: Isolate movable pages
   - migrate: Move pages to new locations
   - Update page tables (remap)

4. Cost of compaction:
   - Page migration requires copying content
   - Requires TLB flushes
   - Involves extensive locking
   - Pause time can be very long

Key compaction functions:

compact_zone(order):
  → compact_zone_order(order)
      → isolate_migratepages()
          → Scan LRU, find movable pages
          → Movable = anonymous (swap) or file-backed (can be written back)
          → Dirty file pages must be written back before moving

migrate_pages():
  → For each page:
      → Allocate new page
      → Copy content
      → Update all process page tables (remap)
      → Free old page

Failure reasons:
  - Pages that cannot be moved (locked, hwpoisoned)
  - Pages undergoing I/O (writeback in progress)
  - Lock contention causing migration timeout

Scenarios where large memory allocations fail:

1. Huge Page Allocation:
   - Request 2MB (or 1GB) huge pages
   - Compaction fails
   - /proc/sys/vm/nr_hugepages shows allocation failure

   $ echo 16 > /proc/sys/vm/nr_hugepages
   $ cat /proc/sys/vm/nr_hugepages
   0    // Failed!

2. vmalloc allocation (non-contiguous physical pages):
   - vmalloc requires contiguous virtual addresses
   - But does not require physical contiguity
   - Compaction only affects physical contiguity

3. Direct I/O:
   - Requires physically contiguous buffers
   - May fail under severe fragmentation

Fragmentation timeline:
  - Early in program run: little fragmentation
  - After hours of operation: fragmentation begins
  - After days: fragmentation may become severe
  - Mitigation: periodic compaction, memory cgroup limits, huge page reserving

Linux anti-fragmentation measures:

1. Migrate types (since Linux 2.6.24):
   - Pages are classified into migrate types:
     MIGRATE_UNMOVABLE  (kernel allocations, page tables)
     MIGRATE_RECLAIMABLE (slab caches)
     MIGRATE_MOVABLE    (anonymous pages, file cache)
     MIGRATE_RESERVE    (reserve, emergency)
   - Same-type pages are clustered together
   - Compaction can concentrate movable pages

2. THP (Transparent Huge Pages):
   - khugepaged kernel thread does background compaction
   - Merges 4KB small pages into 2MB huge pages
   - Reduces TLB pressure and page table overhead

3. CMA (Contiguous Memory Allocator):
   - Reserves a contiguous memory area at boot
   - Can be used by regular allocations when not in use
   - Quickly reserved for DMA/GPU when needed

4. Memory cgroup limits:
   - Limit per-cgroup memory usage
   - Prevent a single process from fragmenting all memory