概述 极客时间 26 | 内核态内存映射：如何找到正确的会议室？ 一道课后问题
伙伴内存分配技术是一种内存分配算法，它将内存划分为多个分区，以尝试尽可能适当地满足内存请求。 该系统利用将内存分成两半来尝试提供最佳匹配。 当Linux内核态和用户态进程申请内存时， 分配的物理页面需要转化为虚拟地址供上层访问。
下面通过内核代码看下Linux内核态的kmalloc和vmalloc和用户态的mmap和malloc地址转换的时机。
内核态-kmalloc kmalloc 伙伴系统地址转换时机: __kmalloc申请空间小于2个页面大小时，申请发起后通过SLAB分配器进行分配, 依次检查 per cpu freelist per cpu partial per node partial链表是否有满足的的缓冲，没有就通过伙伴系统重新申请， 在申请的时候完成后page_address进行地址转换。
过程如下：
申请空间大于两个页面大小内存直接通过伙伴系统申请，小于这个值使用SLUB分配器(当然最终还是从伙伴系统申请内存) /include/linux/slab.h static __always_inline void *kmalloc(size_t size, gfp_t flags) { ... if (size > KMALLOC_MAX_CACHE_SIZE) return kmalloc_large(size, flags); ... return __kmalloc(size, flags); } ... #define KMALLOC_MAX_CACHE_SIZE (1UL << KMALLOC_SHIFT_HIGH) /* * SLUB directly allocates requests fitting in to an order-1 page * (PAGE_SIZE*2). Larger requests are passed to the page allocator. */ #define KMALLOC_SHIFT_HIGH (PAGE_SHIFT + 1) 通过slab_alloc进入具体的内存申请流程. void *__kmalloc(size_t size, gfp_t flags) { struct kmem_cache *s; void *ret; if (unlikely(size > KMALLOC_MAX_CACHE_SIZE)) return kmalloc_large(size, flags); s = kmalloc_slab(size, flags); if (unlikely(ZERO_OR_NULL_PTR(s))) return s; ret = slab_alloc(s, flags, _RET_IP_); trace_kmalloc(_RET_IP_, ret, size, s->size, flags); ret = kasan_kmalloc(s, ret, size, flags); return ret; } 之后就从 <1> . per cpu freelist查找 static __always_inline void *slab_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node, unsigned long addr) { ... redo: ... do { tid = this_cpu_read(s->cpu_slab->tid); c = raw_cpu_ptr(s->cpu_slab); } while (IS_ENABLED(CONFIG_PREEMPTION) && unlikely(tid != READ_ONCE(c->tid))); ... object = c->freelist; page = c->page; ... if (unlikely(!object || !node_match(page, node))) { object = __slab_alloc(s, gfpflags, node, addr, c); stat(s, ALLOC_SLOWPATH); } else { ... } ... return object; } 然后从 <2> . per cpu partial查找 static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node, unsigned long addr, struct kmem_cache_cpu *c) { ... new_slab: if (slub_percpu_partial(c)) { page = c->page = slub_percpu_partial(c); slub_set_percpu_partial(c, page); ... } ... } 然后从 <3> . per node partial查找 static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu **pc) { void *freelist; struct kmem_cache_cpu *c = *pc; struct page *page; WARN_ON_ONCE(s->ctor && (flags & __GFP_ZERO)); freelist = get_partial(s, flags, node, c); ... } /* * Get a partial page, lock it and return it. */ static void *get_partial(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu *c) { void *object; int searchnode = node; if (node == NUMA_NO_NODE) searchnode = numa_mem_id(); object = get_partial_node(s, get_node(s, searchnode), c, flags); if (object || node != NUMA_NO_NODE) return object; return get_any_partial(s, flags, c); } 上面的经历了本地缓存池分配per cpu freelist,per cpu partial, 其他节点缓冲 per node partial, 逐一查找,但是一开始肯定要从伙伴系统分配的，下面看下伙伴系统分配，关注地址转换部分, 可以看到在申请slab时，通过page_address进行了物理地址到虚拟地址转换。 > 如果支持CONFIG_SLAB_FREELIST_RANDOM打乱了free_list中object顺序，减少堆栈溢出可预测性， 并有利于改善缓冲冲突 (Randomize free memory),对应 shuffle_freelist函数里也可看到相关地址映射的操作。 static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu **pc) { ... page = new_slab(s, flags, node); if (page) { ... } return freelist; } static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node) { ... return allocate_slab(s, flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node); } static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node) { page = alloc_slab_page(s, alloc_gfp, node, oo); start = page_address(page); shuffle = shuffle_freelist(s, page); if (!shuffle) { ... page->freelist = start; ... } ... return page; } static bool shuffle_freelist(struct kmem_cache *s, struct page *page) { ... start = fixup_red_left(s, page_address(page)); ... cur = next_freelist_entry(s, page, &pos, start, page_limit, freelist_count); cur = setup_object(s, page, cur); page->freelist = cur; ... return true; } __kmalloc申请空间大于2个页面大小时，申请发起后, 直接就通过伙伴系统申请页了, 这里看到了熟悉的order
...