Data Structure

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:

#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 types migrate_unmovable, migrate_reclaimable, and migrate_movable have already been introduced. migrate_reserve provides an emergency memory reserve if an allocation request cannot be fulfilled from the mobility-specific lists (it is filled during initialization of the memory subsystem with setup_zone_migrate_reserve, but I will not go into detail about this). MIGRATE_ISOLATE is 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 a migrate_type number of lists:

struct free_area {

nr_free counts the number of free pages on all lists, but a specific free list is provided for each migrate type. The macro for_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] = {

struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free;

[MIGRATE_UNMOVABLE] [MIGRATE_RECLAIMABLE] [MIGRATE_MOVABLE] [MIGRATE_RESERVE]

{ MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE }, { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE }, { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE }, { MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE }, /* Never used */

The data structure is mostly self-explanatory: When the kernel wants to allocate un-movable pages, but the corresponding list is empty, then it falls back to reclaimable pages, then to movable pages, and finally to the emergency reserve.

Continue reading here: Global Variables and Auxiliary Functions

Was this article helpful?

0 0