1. Principle introduction
In the linux system, the slab allocator is used to allocate memory smaller than the page. The kmem_cache structure is used to manage the small memory objects on the memory page corresponding to the page, and then the page points to kmem_cache, and the kmem_cache_node structure manages multiple pages.
In the SLAB allocator, it divides a memory page or a group of contiguous memory pages into blocks of the same size, of which this small memory block is the SLAB object, but this group of contiguous memory pages is not only the SLAB object , and SLAB manages the header and shader area.
2. Data structure
1. Management header kmem_cache
struct array_cache { unsigned int avail; // The number of currently available objects unsigned int limit; // Maximum number of objects allowed void *entry[]; // pointer to an array of objects }; struct kmem_cache { struct array_cache __percpu *cpu_cache; // __precpu type, there is one variable for each CPU unsigned int size; // cache size slab_flags_t flags; // slab flag unsigned int num; // number of objects unsigned int gfporder; // The order of allocating memory pages gfp_t allocflags; size_t colour; // Shading area size unsigned int colour_off; // start offset of shaded area const char *name; // The name of this SLAB struct list_head list; // All SLAB s are linked int refcount; // reference counting int object_size; // object size int align; // Align size struct kmem_cache_node *node[MAX_NUMNODES]; // Points to the superstructure that manages kmemcache };
2. Initialize kmem_cache
// global static definition static struct kmem_cache kmem_cache_boot = { .batchcount = 1, .limit = BOOT_CPUCACHE_ENTRIES, .shared = 1, .size = sizeof(struct kmem_cache), .name = "kmem_cache", }; void __init kmem_cache_init(void) { int i; kmem_cache = &kmem_cache_boot; for (i = 0; i < NUM_INIT_LISTS; i++) kmem_cache_node_init(&init_kmem_cache_node[i]); // Create a kmem_cache that holds the kmem_cache structure create_boot_cache(kmem_cache, "kmem_cache", offsetof(struct kmem_cache, node) + nr_node_ids * sizeof(struct kmem_cache_node *), SLAB_HWCACHE_ALIGN, 0, 0); // Add to the global slab_caches list list_add(&kmem_cache->list, &slab_caches); { int nid; for_each_online_node(nid) { init_list(kmem_cache, &init_kmem_cache_node[CACHE_CACHE + nid], nid); init_list(kmalloc_caches[KMALLOC_NORMAL][INDEX_NODE], &init_kmem_cache_node[SIZE_NODE + nid], nid); } } // Create the kmem_cache used by the kmalloc function create_kmalloc_caches(ARCH_KMALLOC_FLAGS); }
3. Memory node kmem_cache_node
#define NUM_INIT_LISTS (2 * MAX_NUMNODES) static struct kmem_cache_node __initdata init_kmem_cache_node[NUM_INIT_LISTS]; struct kmem_cache_node { spinlock_t list_lock; // spin lock struct list_head slabs_partial; // kmem_cache structure with some free objects struct list_head slabs_full; // kmem_cache structure without free objects struct list_head slabs_free; // Objects are all free kmem_cache structures unsigned long total_slabs; // How many kmem_cache structures in total unsigned long free_slabs; // Free kmem_cache structure unsigned long free_objects; // free object unsigned int free_limit; }; static void __init init_list(struct kmem_cache *cachep, struct kmem_cache_node *list, int nodeid) { struct kmem_cache_node *ptr; // Allocate space for the new kmem_cache_node structure ptr = kmalloc_node(sizeof(struct kmem_cache_node), GFP_NOWAIT, nodeid); BUG_ON(!ptr); // Copy the initial static kmem_cache_node structure memcpy(ptr, list, sizeof(struct kmem_cache_node)); spin_lock_init(&ptr->list_lock); MAKE_ALL_LISTS(cachep, ptr, nodeid); // Set the address of kmem_cache_node cachep->node[nodeid] = ptr; }
4. Get the memory page
The cache_grow_begin function will allocate a page for storing objects to the kmem_cache structure, and then call the corresponding cache_grow_end function to mount the page into the linked list of the kmem_cache_node structure, and make the page point to the kmem_cache structure.
static void slab_map_pages(struct kmem_cache *cache, struct page *page,void *freelist) { // The page structure points to the kmem_cache structure page->slab_cache = cache; // a linked list of free objects page->freelist = freelist; } static struct page *cache_grow_begin(struct kmem_cache *cachep, gfp_t flags, int nodeid) { void *freelist; size_t offset; gfp_t local_flags; int page_node; struct kmem_cache_node *n; struct page *page; WARN_ON_ONCE(cachep->ctor && (flags & __GFP_ZERO)); local_flags = flags & (GFP_CONSTRAINT_MASK|GFP_RECLAIM_MASK); // get page page = kmem_getpages(cachep, local_flags, nodeid); // Get the memory node number where the page is located page_node = page_to_nid(page); // Obtain the corresponding kmem_cache_node structure according to the memory node n = get_node(cachep, page_node); // Allocate data structures that manage free objects freelist = alloc_slabmgmt(cachep, page, offset, local_flags & ~GFP_CONSTRAINT_MASK, page_node); // Let the relevant fields in the page point to kmem_cache and free objects slab_map_pages(cachep, page, freelist); // Initialize idle object management data cache_init_objs(cachep, page); return page; } static void cache_grow_end(struct kmem_cache *cachep, struct page *page) { struct kmem_cache_node *n; void *list = NULL; if (!page) return; // Initialize the slab_list linked list of the page structure INIT_LIST_HEAD(&page->slab_list); // Obtain the corresponding kmem_cache_node structure according to the memory node. n = get_node(cachep, page_to_nid(page)); spin_lock(&n->list_lock); // slab count increase n->total_slabs++; if (!page->active) { // Add this page structure to the free list of the kmem_cache_node structure list_add_tail(&page->slab_list, &n->slabs_free); n->free_slabs++; } spin_unlock(&n->list_lock); }
3. Distribution process
The process of slab allocation object is as follows: find the corresponding kmem_cache structure according to the allocation request, then obtain the arry_cache structure, and finally allocate the object;
If it is not found, look for the kmem_cache with free objects in the kmem_cache_node structure corresponding to kmem_cache;
If it has not been found, allocate a memory page to add a kmem_cache structure.
1. Allocation function entry: kmalloc
The kmalloc function, the SLAB allocation interface, is used to allocate small buffers, or to allocate instance space for data structures.
The kmalloc function calls slab_alloc to allocate objects after finding the kmem_cache corresponding to size.
static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,unsigned long caller) { struct kmem_cache *cachep; void *ret; if (unlikely(size > KMALLOC_MAX_CACHE_SIZE)) return NULL; // Find the kmem_cache corresponding to size cachep = kmalloc_slab(size, flags); if (unlikely(ZERO_OR_NULL_PTR(cachep))) return cachep; // assign object ret = slab_alloc(cachep, flags, caller); return ret; } void *__kmalloc(size_t size, gfp_t flags) { return __do_kmalloc(size, flags, _RET_IP_); } static __always_inline void *kmalloc(size_t size, gfp_t flags) { return __kmalloc(size, flags); }
2. Find kmem_cache: kmalloc_slab
According to size and flags as the subscript of the global array, return the contents of the array as kmem_cache.
enum kmalloc_cache_type { KMALLOC_NORMAL = 0, KMALLOC_RECLAIM, #ifdef CONFIG_ZONE_DMA KMALLOC_DMA, #endif NR_KMALLOC_TYPES }; struct kmem_cache *kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init = { static u8 size_index[24] __ro_after_init = { 3, /* 8 */ 4, /* 16 */ 5, /* 24 */ 5, /* 32 */ 6, /* 40 */ 6, /* 48 */ 6, /* 56 */ 6, /* 64 */ 1, /* 72 */ 1, /* 80 */ 1, /* 88 */ 1, /* 96 */ 7, /* 104 */ 7, /* 112 */ 7, /* 120 */ 7, /* 128 */ 2, /* 136 */ 2, /* 144 */ 2, /* 152 */ 2, /* 160 */ 2, /* 168 */ 2, /* 176 */ 2, /* 184 */ 2 /* 192 */ }}; //Return enum type based on assignment flag static __always_inline enum kmalloc_cache_type kmalloc_type(gfp_t flags) { #ifdef CONFIG_ZONE_DMA if (likely((flags & (__GFP_DMA | __GFP_RECLAIMABLE)) == 0)) return KMALLOC_NORMAL; return flags & __GFP_DMA ? KMALLOC_DMA : KMALLOC_RECLAIM; #else return flags & __GFP_RECLAIMABLE ? KMALLOC_RECLAIM : KMALLOC_NORMAL; #endif } // Calculate the index from size, and determine the array subscript together with flags struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags) { unsigned int index; //calculate index if (size <= 192) { if (!size) return ZERO_SIZE_PTR; index = size_index[size_index_elem(size)]; } else { if (WARN_ON_ONCE(size > KMALLOC_MAX_CACHE_SIZE)) return NULL; index = fls(size - 1); } return kmalloc_caches[kmalloc_type(flags)][index]; }
The establishment process of the global array kmalloc_caches is as follows:
struct kmem_cache *__init create_kmalloc_cache(const char *name, unsigned int size, slab_flags_t flags, unsigned int useroffset, unsigned int usersize) { // Allocate an object from the first kmem_cache and put it in kmem_cache struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT); if (!s) panic("Out of memory when creating slab %s\n", name); // Set the alignment parameter of s, and the freelist for processing s is arr_cache create_boot_cache(s, name, size, flags, useroffset, usersize); list_add(&s->list, &slab_caches); s->refcount = 1; return s; } // Create a new kmem_cache static void __init new_kmalloc_cache(int idx, enum kmalloc_cache_type type, slab_flags_t flags) { if (type == KMALLOC_RECLAIM) flags |= SLAB_RECLAIM_ACCOUNT; //Create a kmem_cache based on the information in kmalloc_info kmalloc_caches[type][idx] = create_kmalloc_cache( kmalloc_info[idx].name[type], kmalloc_info[idx].size, flags, 0, kmalloc_info[idx].size); } //Build all kmalloc_caches in kmem_cache void __init create_kmalloc_caches(slab_flags_t flags) { int i; enum kmalloc_cache_type type; for (type = KMALLOC_NORMAL; type <= KMALLOC_RECLAIM; type++) { for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++) { if (!kmalloc_caches[type][i]) //Create a new kmem_cache new_kmalloc_cache(i, type, flags); if (KMALLOC_MIN_SIZE <= 32 && i == 6 && !kmalloc_caches[type][1]) new_kmalloc_cache(1, type, flags); if (KMALLOC_MIN_SIZE <= 64 && i == 7 && !kmalloc_caches[type][2]) new_kmalloc_cache(2, type, flags); } } }
3. Allocation object: slab_alloc
The first parameter of the slab_alloc function is a pointer to the kmem_cache structure, indicating that objects are allocated from the kmem_cache structure.
First, obtain the pointer to the array_cache structure in the current kmem_cache structure. If the address of the free object is found, take out a free object address in the array_cache structure and return it, that is, the allocation is successful.
When no free object is found, get the kmem_cache_node to which the first cache belongs, and then call get_first_slab to get the kmem_cache_node structure to check whether the kmem_cache of the free object is included;
If the kmem_cache_node structure does not contain the kmem_cache of free objects, call the cache_grow_begin function, find the partner system to allocate a new memory page, perform the necessary initialization, and finally call the cache_grow_end function to mount the allocated page to the slabs_list linked list of the kmem_cache_node structure.
The interface calling process is as follows:
slab_alloc __do_cache_alloc ____cache_alloc cpu_cache_get // Get the pointer to the array_cache structure of the current cpu in the cachep structure // After a free object is found, the object address is returned, and the allocation process ends // When no free object is found cache_alloc_refill numa_mem_id cpu_cache_get get_node // Get kmem_cache_node // no kmem_cache containing free objects get_first_slab alloc_block // Get other kmem_cache in the kmem_cache_node structure, cache_grow_begin // Allocate new kmem_cache and initialize cpu_cache_get cache_grow_end // Mount the page to the slabs_list linked list of the kmem_cache_node structure
The detailed process is as follows:
static __always_inline void *slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller) { unsigned long save_flags; void *objp; //Turn off interrupts local_irq_save(save_flags); //assign object objp = __do_cache_alloc(cachep, flags); //resume interruption local_irq_restore(save_flags); return objp; } // object allocation process static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags) { void *objp; struct array_cache *ac; //Get the pointer to the array_cache structure of the current cpu in the cachep structure ac = cpu_cache_get(cachep); //If the avail in ac is not 0, it means that there are free objects in the freelist in the current kmem_cache structure if (likely(ac->avail)) { ac->touched = 1; //The address of the space object is stored in ac->entry objp = ac->entry[--ac->avail]; goto out; } // No free object found objp = cache_alloc_refill(cachep, flags); out: return objp; } static __always_inline void *__do_cache_alloc(struct kmem_cache *cachep, gfp_t flags) { return ____cache_alloc(cachep, flags); } static struct page *get_first_slab(struct kmem_cache_node *n, bool pfmemalloc) { struct page *page; assert_spin_locked(&n->list_lock); //First, check whether there is a page from the slabs_partial linked list in the kmem_cache_node structure page = list_first_entry_or_null(&n->slabs_partial, struct page,slab_list); if (!page) { //if there is not n->free_touched = 1; //Check whether there is a page from the slabs_free linked list in the kmem_cache_node structure page = list_first_entry_or_null(&n->slabs_free, struct page,slab_list); if (page) n->free_slabs--; //The idle slab count is decremented by one } //back to page return page; } static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags) { int batchcount; struct kmem_cache_node *n; struct array_cache *ac, *shared; int node; void *list = NULL; struct page *page; // get memory node node = numa_mem_id(); ac = cpu_cache_get(cachep); batchcount = ac->batchcount; // Get the kmem_cache_node to which the cache belongs n = get_node(cachep, node); shared = READ_ONCE(n->shared); if (!n->free_objects && (!shared || !shared->avail)) goto direct_grow; while (batchcount > 0) { // Get other kmem_cache in the kmem_cache_node structure, return the page, and the page will point to kmem_cache page = get_first_slab(n, false); if (!page) goto must_grow; batchcount = alloc_block(cachep, ac, page, batchcount); } must_grow: n->free_objects -= ac->avail; direct_grow: if (unlikely(!ac->avail)) { //Allocate new kmem_cache and initialize page = cache_grow_begin(cachep, gfp_exact_node(flags), node); ac = cpu_cache_get(cachep); if (!ac->avail && page) alloc_block(cachep, ac, page, batchcount); //Let the page be mounted on the slabs_list linked list of the kmem_cache_node structure cache_grow_end(cachep, page); if (!ac->avail) return NULL; } ac->touched = 1; //reallocate return ac->entry[--ac->avail]; }
Fourth, slab/slub/slob
Slab is the foundation, and Linux is introduced from Sun OS;
Slob is optimized for micro embedded systems;
Slub is optimized for large computer scenarios.