Linux Kernel Architecture

Chapter3:MemoryManagement

Data Structure Setup

Although the anti-fragmentation technique used by the kernel is highly effective, it has astonishingly little

impact on code and data structures of the buddy allocator. The kernel defines some macros to represent

the different migrate types:

<mmzone.h>

#define MIGRATE_UNMOVABLE 0

#define MIGRATE_RECLAIMABLE 1

#define MIGRATE_MOVABLE 2

#define MIGRATE_RESERVE 3

#define MIGRATE_ISOLATE 4 /* can’t allocate from here */

#define MIGRATE_TYPES 5

The typesMIGRATE_UNMOVABLE,MIGRATE_RECLAIMABLE,andMIGRATE_MOVABLEhave already been intro-

duced.MIGRATE_RESERVEprovides an emergency memory reserve if an allocation request cannot be

fulfilled from the mobility-specificlists (it is filled during initialization of the memory subsystem with

setup_zone_migrate_reserve, but I will not go into detail about this).MIGRATE_ISOLATEis a special

virtual zone that is required to move physical pages across NUMA nodes. On large systems, it can be

beneficial to bring physical pages closer to the CPUs that use them most.MIGRATE_TYPES, finally, is also

not a zone, but just denotes the number of migrate types.

The core adjustment to the buddy system data structures is that the free list is broken into aMIGRATE_TYPE

number of lists:

<mmzone.h>

struct free_area {

struct list_head free_list[MIGRATE_TYPES];

unsigned long nr_free;

};

nr_freecounts the number of free pages onalllists, but a specific free list is provided for each migrate

type. The macrofor_each_migratetype_order(order, type)can be used to iterate over the migrate

types of all allocation orders.

What happens if the kernel cannot fulfill an allocation request for a given migrate type? A similar problem

has already occurred before, namely, when we considered what happens when an allocation cannot

be fulfilled from a specific NUMA zone. The kernel proceeds similarly as in this case by providing a

fallback list regulating which migrate types should be used next if a request cannot be fulfilled from the

desired list:

mm/page_alloc.c
/*

• This array describes the order lists are fallen back to when


• the free lists for the desirable migrate type are depleted
  /
  static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
  [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
  [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
  [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
  [MIGRATE_RESERVE] = { MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE },
  / Never used */
  };