精华内容
下载资源
问答
  • 3.5 Linux 的内存分配和管理 下面我们来讨论内存管理的... 被申请占用的内存块没有有效利用,存在浪费称为内部碎片如何解决? 每次申请完内存之后是否需要刷新进程页表,是否有性能问题? 内存申请是...

    3.5 Linux 的内存分配和管理

    下面我们来讨论内存管理的相关问题,通过前面的分析,我认为内存管理需要考虑以下几个问题:

    • 内存经过频繁申请归还之后,会出现碎片,称为外部碎片,导致没有足够大的连续内存空间,如何解决该问题?

    • 被申请占用的内存块没有有效利用,存在浪费称为内部碎片,如何解决?

    • 每次申请完内存之后是否需要刷新进程页表,是否有性能问题?

    • 内存申请是基于物理地址还是线性地址?

    3.5.1 物理内存分配算法

    我们已经知道,对于物理内存,经过频繁地申请和释放后会产生外部碎片,为了解决该问题,Linux 通过伙伴系统来解决外部碎片的问题。

    假如仅仅解决外部碎片的问题,我们可以考虑内存分配的时候不提供连续的内存,但是在内核我们已经提前分配了 DMA 和 NORMAL 区域的页表,假如分配的物理地址不连续,但分配的线性地址总得连续吧?这就牵涉到页表刷新的问题了,在内核态频繁需要使用内存,这个方案对性能影响太大了,不能接受。为了解决这个问题,出现了伙伴系统。

    下面我们来具体聊聊伙伴系统的实现:

    从思路上来讲,伙伴系统在申请内存的时候让最小的块满足申请的需求,在归还的时候,尽量让连续的小块内存伙伴合并成大块,降低外部碎片出现的可能性。

    在 Linux 中伙伴系统算法的实现方法为:

    伙伴系统维护了11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续的物理页。对1024个页的最大请求对应着 4MB 大小的连续 RAM 块。每个块的第一个页框的物理地址是该块大小的整数倍。例如,大小为16个页框的块,其起始地址是16×212(212=4KB,这是一个常规页的大小)的倍数。

    满足以下条件的两个块称为伙伴:

    • 具有相同的大小。

    • 物理地址是连续的。

    申请的过程是从最接近大小的链表上找一个空闲块,释放的过程则会触发伙伴(假如找到空闲的伙伴)的合并。

    下面我们来介绍一下 Linux 中和伙伴系统相关的数据结构(参见图3-15)。在前文中已经介绍了 pg_data 作为一个内存节点,在 node_mem_map 中维护了所有的物理内存页(page),另外在 pg_data 下维护了所有内存区域 node_zones,每个内存区域(zone)中维护了伙伴系统的空闲内存块 free_area。

    图3-15 Linux 伙伴系统数据结构

    free_area 维护了11个链表,链表中存储每个块的起始 page,块当中的 page 通过 page 的 lru 指针连接,page 当中的 private 代表了这个块属于哪个链表。

    此外在 pg_data 的 node_mem_map 中保存了连续物理地址的 page 指针,所以用 page-node_mem_map 就能计算出该物理页的 pfn。

    现在我们已经知道,在 Linux 中要使用物理内存(当然,这是在系统启动之后,启动前的事情就不在这里论述了)就得通过伙伴系统。那么在使用伙伴系统时,好歹得先初始化 free_area 链表吧?

    前面我们已经知道系统在启动的时候通过 start_kernel()->paging_init()->free_area_init_node()来初始化节点、区域、page,在该过程中 free_area_init_node()->free_area_init_core()->init_currently_empty_zone()-->zone_init_free_lists()把 free_area 的链表初始化为空:

    static void __meminit zone_init_free_lists(struct zone *zone)
    {
        unsigned int order, t;
        for_each_migratetype_order(order, t) {
            INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
            zone->free_area[order].nr_free = 0;
        }
    }
    

    然后通过 start_kernel()-->mm_init()-->mem_init(),负责统计所有可用的低端内存和高端内存,并释放到伙伴系统中,这个过程分为两个部分,详情可以从源码中去寻找:

    1)通过 free_all_bootmem 释放低端内存(ZONE_DMA 和 ZONE_NORMAL)到伙伴系统中去。

    2)通过 set_highmem_pages_init 将高端内存(ZONE_HIGHMEM)释放到伙伴系统中去。

    这两个过程最终都会调用 _free_page()进行释放。

    下面我们先来分析释放页的过程 _free_page()函数:

    void __free_pages(struct page *page, unsigned int order)
    {
        if (put_page_testzero(page)) {
            if (order == 0)
                free_hot_cold_page(page, false);
            else
                __free_pages_ok(page, order);
        }
    }
    

    释放流程分为两个部分:

    • 假如 order==0,则说明是单页,直接存入 per-cpu 页高速缓存当中。

    • 否则通过 _free_pages_ok 释放到伙伴系统中去,其最终调用 _free_one_page 函数:

    static inline void __free_one_page(struct page *page,
            unsigned long pfn,
            struct zone *zone, unsigned int order,
            int migratetype)
    {
        unsigned long page_idx;
        unsigned long combined_idx;
        unsigned long uninitialized_var(buddy_idx);
        struct page *buddy;
        unsigned int max_order;
        max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
    …
        // 先找到最大块链表中的偏移
        page_idx = pfn & ((1 << MAX_ORDER) - 1);
    …
    continue_merging:
        while (order < max_order - 1) {                    // 假如 order 小于 max_order-1 就有可能进行合并
                                                      (合并本来就是从小变大的过程,最大块当然没法合并了)
            buddy_idx = __find_buddy_index(page_idx, order);  // 寻找伙伴在链表中的偏移
            buddy = page + (buddy_idx - page_idx);            // 伙伴之间是连续的,所以通过该方式找到 page 页面
            if (!page_is_buddy(page, buddy, order))           // 假如该伙伴非空闲,则没法合并,跳出
                goto done_merging;
            …
            if (page_is_guard(buddy)) {
                clear_page_guard(zone, buddy, order, migratetype);
            } else {
                list_del(&buddy->lru);                 // 合并之后就要去 order+1 那层了,把伙伴从现在这层链表中删掉
                zone->free_area[order].nr_free--;
                rmv_page_order(buddy);
            }
            combined_idx = buddy_idx & page_idx;          // 因为 page_idx 和 buddy_idx 仅差异在 1<<order 位是否为1,那么可以理解为 combined_idx 取 page_idx 和 buddy_idx 的最小值
            page = page + (combined_idx - page_idx);
            page_idx = combined_idx;
            order++;
        }
        …
    done_merging:
        set_page_order(page, order);                          // 合并完成,重新设置块的 order
    …
        list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
                                                              // 将新块添加到对应的 free_area 链表中
    out:
        zone->free_area[order].nr_free++;
    }
    

    其中寻找伙伴的函数 _find_buddy_index 实现为:

    static inline unsigned long
    __find_buddy_index(unsigned long page_idx, unsigned int order)
    {
        return page_idx ^ (1 << order);  // page_idx 为2的 order 次的倍数,2的 order 以上的位和 1<<order 进行异或运算,伙伴在左还是在右取决于 1<<order 位是0还是1。假如是0则伙伴在后面;否则伙伴在前面,因为异或1变成0了。
    }
    

    这个内存释放的过程还是很好理解的,在把内存归还给伙伴系统的时候,首先检查这个内存区的伙伴是否是空闲的,如果是则进行合并,转移到更高阶的链表,直到无法合并为止。关键是理解如何寻找伙伴以及找到最后块 page 的过程,在以上代码中都已经做出了解释。

    内存归还完毕之后,伙伴系统也就初始化完毕了,下面就可以进入内存的申请过程了,伙伴算法的分配通过 alloc_pages->alloc_pages_node->_alloc_pages_node->_alloc_pages->_alloc_pages_nodemask 来进行物理内存申请。我们这里仅关心从伙伴系统申请的主要路径,忽略细枝末节的干扰,_alloc_pages_nodemask的关键步骤为 get_page_from_freelist:

    …
    /* 从指定的 zone 开始寻找,直到找到一个拥有足够空间的管理区为止。例如,如果 high_zoneidx 对应的 ZONE_HIGHMEM,则遍历顺序为HIGHMEM-->NORMAL-->DMA,如果 high_zoneidx 对应 ZONE_NORMAL,则遍历顺序为 NORMAL-->DMA*/
    for_each_zone_zonelist_nodemask(zone, z, zonelist, ac->high_zoneidx,
                        ac->nodemask) {
    …
        page = buffered_rmqueue(ac->preferred_zone, zone, order,
                gfp_mask, alloc_flags, ac->migratetype);
            …
            return page;
        }
    }
    

    buffered_rmqueue 函数假如申请的是单页则会从 per-cpu 缓存链表中找一个缓存的热页或者冷页。否则通过 _rmqueue 函数真正从伙伴系统中申请2的 order 次个页面,伙伴系统的申请在 _rmqueue_smallest 中实现:

    static inline
    struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                                    int migratetype)
    {
        unsigned int current_order;
        struct free_area *area;
        struct page *page;
    
        // 从指定的 order 一层一层往上寻找合适的块
        for (current_order = order; current_order < MAX_ORDER; ++current_order) {
            area = &(zone->free_area[current_order]);
            page = list_first_entry_or_null(&area->free_list[migratetype],
                        struct page, lru);
            if (!page)
                continue;
            list_del(&page->lru);        // 找到后从该空闲链表中删除
            rmv_page_order(page);
            area->nr_free--;
            expand(zone, page, order, current_order, area, migratetype);
                                                // 假如 current_order 大于申请的 order,则进行 expand 拆分内存块
            set_pcppage_migratetype(page, migratetype);
            return page;
        }
        return NULL;
    }
    

    拆分函数 expand 的实现为:

    static inline void expand(struct zone *zone, struct page *page,
        int low, int high, struct free_area *area,
        int migratetype)
    {
        unsigned long size = 1 << high;
    
        while (high > low) {
            area--;
            high--;
            size >>= 1;                        // 对半拆分,右移一次相当于除以2
            …
            list_add(&page[size].lru, &area->free_list[migratetype]);
                                                     // 一半拿来使用,另外一半拿来放入 area-- 的链表中
            area->nr_free++;
            set_page_order(&page[size], high);   // 设置不使用的一半 order 为 high--
        }
    }
    

    这个申请的过程和之前介绍的伙伴系统实现思路是一致的,尽量从满足大小的 area 链表中申请内存块,假如大小不够则往上层链表查找,由此每上升一次,内存块大小就会扩展两倍,所以假如 current_order 大于 order 的时候,必然存在一半的内存浪费,因此通过 expand 操作进行拆分,另一半存入 current_order-1 的链表中。

    最后我们对伙伴系统进行一下总结(如图3-16所示),在系统初始化的时候,会把内存节点各区域(zone)都释放到伙伴系统中,每个区域还维护了 per-cpu 高速缓存来处理单页的分配,各个区域都通过伙伴算法进行物理内存的分配。

    图3-16 Linux 伙伴系统实现

    3.5.2 slab 分配器

    我们已经了解到,上一节介绍的伙伴算法是用来解决外部碎片的问题,但是,如果不解决内部碎片的问题,还是会存在大量浪费内存的问题。所以 Linux 提供了 slab 分配器来解决内部碎片的问题。slab 分配器的概念如下:

    slab 分配器其实也是一种内存预分配的机制,是一种空间换时间的做法,并且其假定从 slab 分配器中获取的内存都是比页还小的小块内存。

    关于 slab 分配器的源码实现较为复杂,牵涉概念也较多,理解起来有些困难,但是只要抓住核心概念,化繁为简,其实也是可以理解的。

    为了便于理解,我们首先来介绍一下 slab 分配器相关的概念(见图3-17)。在系统启动后,维护了一个全局的结构 struct kmem_cache,在 kmem_cache 中的 list 维护了所有的 slab 缓存列表,关联的全局结构为 LIST_HEAD(slab_caches),维护了所有的 kmem_cache 缓存列表,该列表中的缓存按照对象的大小,从小到大来构建的。

    图3-17 Linux slab 分配器核心概念

    kmem_cache 中的 kmem_cache_node 维护了三个 slab 链表,分别为:

    • slabs_full:该链表中的 slab 已经完全被分配出去了。

    • slabs_free:该链表中的 slab 都为空闲可分配状态。

    • slabs_partial:该链表中的 slab 部分被分配了出去。

    其中,slab 代表物理地址连续的内存块,由 1~N 个物理内存页面(page)组成,在一个 slab 中,可以分配多个 object 对象。

    在了解了关于 slab 分配器的基本概念后,下面我们来分析从缓存到 slab 的初始化过程。

    1.创建缓存 kmem_cache_create

    创建代码如下:

    kmem_cache_create(const char *name, size_t size, size_t align,
        unsigned long flags, void (*ctor)(void *))
    

    其中参数如下:

    • name:缓存名称。

    • size:缓存中分配的对象大小。

    • align:对象对齐的大小。

    • flags:slab 相关标志位。

    • ctor:对象构造函数。

    kmem_cache_create 主要通过 create_cache 来完成分配:

    s = create_cache(cache_name, size, size,
        calculate_alignment(flags, align, size),
        flags, ctor, NULL, NULL);
    

    下面是 create_cache 函数的实现:

    static struct kmem_cache *create_cache(const char *name,
        size_t object_size, size_t size, size_t align,
        unsigned long flags, void (*ctor)(void *),
        struct mem_cgroup *memcg, struct kmem_cache *root_cache)
    {
        struct kmem_cache *s;
        int err;
        err = -ENOMEM;
        s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);
        if (!s)
            goto out;
        s->name = name;
        s->object_size = object_size;
        s->size = size;
        s->align = align;
        s->ctor = ctor;
    …
        err = __kmem_cache_create(s, flags);
    …
        s->refcount = 1;
        list_add(&s->list, &slab_caches);
    …
        return s;
    …
    }
    

    create_cache 首先通过 kmem_cache_zalloc 从系统初始化之后确定的 kmem_cache 为新创建的 kmem_cache 结构体分配空间,然后进行属性的初始化,其中 s->object_size 和 size 传入的时候是同一个值,最后通过 _kmem_cache_create 进行后续的操作,分为几个部分进行:

    1)进行对象对齐操作:

    if (size & (BYTES_PER_WORD - 1)) {
        size += (BYTES_PER_WORD - 1);
        size &= ~(BYTES_PER_WORD - 1);
    }
    …
    

    2)确定 slab 管理对象存储方式为内置还是外置:

    if (size >= OFF_SLAB_MIN_SIZE && !slab_early_init &&
            !(flags & SLAB_NOLEAKTRACE))
            flags |= CFLGS_OFF_SLAB;
        size = ALIGN(size, cachep->align);
    

    3)通过 calculate_slab_order 函数计算 slab 由几个页面组成,每个 slab 有多少个对象:

    static size_t calculate_slab_order(struct kmem_cache *cachep,
                size_t size, size_t align, unsigned long flags)
    {
        unsigned long offslab_limit;
        size_t left_over = 0;
        int gfporder;
    
        for (gfporder = 0; gfporder <= KMALLOC_MAX_ORDER; gfporder++) {
            unsigned int num;
            size_t remainder;
            //  计算每个 slab 中的对象数量,浪费空间大小,参数如下:
            gfporder: slab 大小为 2^gfporder 个页面
            buffer_size: 对象大小
            align: 对象的对齐方式
            flags: 是外置 slab 还是内置 slab
            remainder: slab 中浪费的空间(碎片)是多少
            num: slab 中对象个数
            cache_estimate(gfporder, size, align, flags, &remainder, &num);
            if (!num)        // 假如对象数量小于等于0,则进入下一个 order 继续尝试
                continue;
    …
            cachep->num = num;
            cachep->gfporder = gfporder;
            left_over = remainder;
            // 假如 slab 超过最大页面限制,也跳出循环
            if (gfporder >= slab_max_order)
                break;
    
            // slab 占用页面大小是碎片的8倍以上,说明利用率较高,该 order 可以接受
            if (left_over * 8 <= (PAGE_SIZE << gfporder))
                break;
        }
        return left_over;// 返回的是 slab 中的浪费空间大小
    }
    

    其中 cache_estimate 的计算过程如下:

    static void cache_estimate(unsigned long gfporder, size_t buffer_size,
                size_t align, int flags, size_t *left_over,
                unsigned int *num)
    {
        int nr_objs;
        size_t mgmt_size;
        size_t slab_size = PAGE_SIZE << gfporder;        // slab 大小为 2^gfporder 个页面
    …
        if (flags & CFLGS_OFF_SLAB) {                      // 外置 slab 情况
            mgmt_size = 0;                                            // 没有管理对象
            nr_objs = slab_size / buffer_size;                    // 对象个数为 slab 大小除以对象大小
    } else {                                                               // 内置 slab 管理区的场景
            nr_objs = calculate_nr_objs(slab_size, buffer_size,
                    sizeof(freelist_idx_t), align);
            mgmt_size = calculate_freelist_size(nr_objs, align); // 管理区就是对齐后的空闲链表大小
        }
        *num = nr_objs;// 返回对象数量
        *left_over = slab_size - nr_objs*buffer_size - mgmt_size; // slab大小-所有对象占用空间-管理区(空闲链表)
    }
    

    calculate_nr_objs 计算过程如下:

    static int calculate_nr_objs(size_t slab_size, size_t buffer_size,
                size_t idx_size, size_t align)
    {
        int nr_objs;
        size_t remained_size;
        size_t freelist_size;
        int extra_space = 0;
        ...
        nr_objs = slab_size / (buffer_size + idx_size + extra_space);  // 算上空闲链表中占用的大小
        remained_size = slab_size - nr_objs * buffer_size;
        freelist_size = calculate_freelist_size(nr_objs, align); // 空闲链表对齐后的总长度
        if (remained_size < freelist_size) // 剩余空间比空闲链表需要的小,则减去一个对象的空间
            nr_objs--;
        return nr_objs;
    }
    

    4)针对 slab 管理区是否外置,进行相应设置:

    freelist_size = calculate_freelist_size(cachep->num, cachep->align); // 对齐后的空闲管理区大小
        if (flags & CFLGS_OFF_SLAB && left_over >= freelist_size) {
                                            // 剩余空间大于管理区,则把外置 slab 方式转换成内置的
            flags &= ~CFLGS_OFF_SLAB;
            left_over -= freelist_size;
        }
        if (flags & CFLGS_OFF_SLAB) {
            freelist_size = calculate_freelist_size(cachep->num, 0); // 外部管理区不需要对齐
    

    5)对前面计算完的结果,设置 kmem_cache 的相关值:

    cachep->colour_off = cache_line_size();                            // 着色块大小为 cache line 的大小
        /* Offset must be a multiple of the alignment. */
        if (cachep->colour_off < cachep->align)
            cachep->colour_off = cachep->align;              // 着色块大小必须是对齐大小的整数倍
        cachep->colour = left_over / cachep->colour_off;     // 计算着色区域包含着色块个数
        cachep->freelist_size = freelist_size;                  // 空闲对象管理区大小
        cachep->flags = flags;
        cachep->allocflags = __GFP_COMP;
        if (CONFIG_ZONE_DMA_FLAG && (flags & SLAB_CACHE_DMA))
            cachep->allocflags |= GFP_DMA;
        cachep->size = size;                                    // slab 对象大小
        cachep->reciprocal_buffer_size = reciprocal_value(size);
    
        if (flags & CFLGS_OFF_SLAB) {
            cachep->freelist_cache = kmalloc_slab(freelist_size, 0u);
                                                                  // 外置管理区通过 kmalloc_slab 从 kmem_caches 中分配一块空间
        }
    

    6)setup_cpu_cache 进行 kmem_cache 中的三链节点初始化工作:

    static int __init_refok setup_cpu_cache(struct kmem_cache *cachep, gfp_t gfp)
    {
        if (slab_state >= FULL)
            return enable_cpucache(cachep, gfp);        // cpucache 已经初始化完毕
        cachep->cpu_cache = alloc_kmem_cache_cpus(cachep, 1, 1);
                                    // 为 cachep->cpu_cache 分配空间,其为 per-cpu 变量
        if (!cachep->cpu_cache)
            return 1;
        if (slab_state == DOWN) {
            set_up_node(kmem_cache, CACHE_CACHE);        // 给全局 kmem_cache 的三链节点分配空间
        } else if (slab_state == PARTIAL) {
            set_up_node(cachep, SIZE_NODE);                // 为 cachep 的三链节点分配空间
        } else {
            int node;
            for_each_online_node(node) {        // 通过 kmalloc 给三链节点分配空间并且初始化
                cachep->node[node] = kmalloc_node(
                    sizeof(struct kmem_cache_node), gfp, node);
                BUG_ON(!cachep->node[node]);
                kmem_cache_node_init(cachep->node[node]);
            }
        }
        cachep->node[numa_mem_id()]->next_reap =
                jiffies + REAPTIMEOUT_NODE +
                ((unsigned long)cachep) % REAPTIMEOUT_NODE;
        // 进行初始化,目前还没有从伙伴系统中进行空间分配
        cpu_cache_get(cachep)->avail = 0;
        cpu_cache_get(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
        cpu_cache_get(cachep)->batchcount = 1;
        cpu_cache_get(cachep)->touched = 0;
        cachep->batchcount = 1;
        cachep->limit = BOOT_CPUCACHE_ENTRIES;
        return 0;
    }
    

    最开始 cachep->node 的空间没法从 slab 分配器中进行分配,因为系统还未初始化,所以通过 set_up_node 从全局的 init_kme_cache_node 中静态分配,然后再通过 kmalloc 分配后进行替换并且初始化。

    在了解了 kmem_cache 的初始化完成之后,我们再来回顾一下 kmem_cache 的结构:

    struct kmem_cache {
        struct array_cache __percpu *cpu_cache;// slab 分配缓存
        unsigned int batchcount;        // 从 slab 中批量获取的对象数量,用于放入 cpu_cache 中
        unsigned int limit;             // 本地高速缓存中空闲对象的数量
        unsigned int shared;            // 是否存在共享 CPU 高速缓存
        unsigned int size;              // 缓存分配对象大小
        struct reciprocal_value reciprocal_buffer_size;
        unsigned int flags;
        unsigned int num;               // 每个 slab 中的对象数量
        /* order of pgs per slab (2^n) */
        unsigned int gfporder;
        /* force GFP flags, e.g. GFP_DMA */
        gfp_t allocflags;
        size_t colour;                  // 着色区域数量
        unsigned int colour_off;        // 着色偏移大小
        struct kmem_cache *freelist_cache;
        unsigned int freelist_size;
        void (*ctor)(void *obj);        // 对象构造函数
        const char *name;               // 缓存名称
        struct list_head list;          // kmem_cache 缓存链表
        int refcount;
        int object_size;                // 对象大小
        int align;                      // 对齐大小
        ...
        struct kmem_cache_node *node[MAX_NUMNODES];// slab 三链节点
    };
    

    2.slab 分配机制

    在具体分析 slab 分配机制实现之前,先介绍一下 slab 分配的思路,便于后续理解:

    在分配过程中,首先从 cpu_cache 中获取 slab,假如这个 array 成员里边没有 slab,则从 cache 的 slab 三链中把内存转给 array,如果 slab 三链也没有 slab,那么就让 slab 三链从伙伴系统中获取物理内存再转给 array。

    从实现上来看,slab 分配的入口为 slab_alloc,通过 slab_alloc->_do_cache_alloc->___cache_alloc 来进行分配,下面分析 ___cache_alloc 实现,其主要流程分为以下几步。

    1)假如缓存中有空闲的对象,则从缓存中获取:

    if (likely(ac->avail)) {
        ac->touched = 1;
        objp = ac_get_obj(cachep, ac, flags, false);        // 从缓存中寻找空闲对象空间
    …
    

    其中 ac_get_obj 的主要逻辑为:

    objp = ac->entry[--ac->avail];
    

    我们可以发现,一直是从最后一个对象开始分配的,这样 avail 对应的空闲对象是最热的,即最近释放出来的,更有可能驻留在 CPU 高速缓存中。

    2)假如无法从缓存中分配对象,则为缓存增加空间:

    objp = cache_alloc_refill(cachep, flags, force_refill):
    static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags,
                                    bool force_refill)
    {
        int batchcount;
        struct kmem_cache_node *n;
        struct array_cache *ac;
        int node;
        ...
        node = numa_mem_id();        // 取 numa 本地节点
        if (unlikely(force_refill))        // 假如要强制增长 force_refill 为 true,就执行 force_grow
            goto force_grow;
    retry:
        ac = cpu_cache_get(cachep);        // 获取本地 CPU 的缓存
        batchcount = ac->batchcount;
        ...
        n = get_node(cachep, node);        // 针对每个 node 的 slab 三链结构
        ...
        // 如果有共享本地高速缓存,则从共享本地高速缓存填充仅用于多核,多个 CPU 共享的高速缓存(3链 node 中也有高速缓存)
        if (n->shared && transfer_objects(ac, n->shared, batchcount)) {
            n->shared->touched = 1;
            goto alloc_done;
        }
        while (batchcount > 0) {
            struct page *page;
            page = get_first_slab(n);// 从 slabs_partial和slabs_free 中找可用的 slab 页面
            if (!page)                // 如果获取不到,那么必须增长了
                goto must_grow;
            ...
            BUG_ON(page->active >= cachep->num);  // active 代表已经使用的对象数量,必然不能超过 num
            // 节省了 slab 结构体的开销
            while (page->active < cachep->num && batchcount--) {
                                            // 将新找到的 slab 中的 batchcount 个对象放入 cpu cache 中
                ...
                ac_put_obj(cachep, ac, slab_get_obj(cachep, page,
                    node));
            }
            list_del(&page->lru);        // 将从中分配对象的 slab(此 slab 可能在 partial 或 free 的链表中)重新加入到合适的列表中
            if (page->active == cachep->num)
                list_add(&page->lru, &n->slabs_full); // 如果没有空闲对象了,那么就把该页面加入到 full 链表中
            else
                list_add(&page->lru, &n->slabs_partial); // 如果该 slab 中还有空闲对象,则加入 partial 链表中
        }
    must_grow:
        n->free_objects -= ac->avail;
    alloc_done:
        …
        if (unlikely(!ac->avail)) {
            int x;
    force_grow:
            // partial 和 free 链表中都没有可用的 slab 了,则必须新分配内存对 kmem_cache 进行扩充
            x = cache_grow(cachep, gfp_exact_node(flags), node, NULL);
            ac = cpu_cache_get(cachep);
            node = numa_mem_id();
            ...
            // 第一次 grow 后,通常 ac->avail 为0,然后会跳转到 retry,重新从链表中选择 slab,
             然后重新将其添加到 ac 中
            if (!ac->avail)
                goto retry;
        }
        ac->touched = 1;
        // grow 的流程中,由于前面已经 retry,所以这里能保证 ac 中一定有需要的对象。另外没有 grow 的流程也会从这返回,此时 ac 中也一定是有对象可用的
        return ac_get_obj(cachep, ac, flags, force_refill);
    }
    

    这个过程中 CPU cache 优先会从 slabs_partial 和 slabs_free 中找可用的 slab 页面,然后把可用对象放入 CPU cache 中。假如没有可用对象,那只能通过 cache_grow 从伙伴系统中进行分配了。

    注意 

    page->active 代表该 slab 中已经被使用的对象数量,所以它不能大于 cachep->num 即一个 slab 中的最大可用对象数量。

    此外,上述过程中有三个函数比较重要:slab_get_obj、ac_put_obj、cache_grow。

    slab_get_obj 函数的作用是为了从 slab 中找到可用的对象:

    static void *slab_get_obj(struct kmem_cache *cachep, struct page *page,
            int nodeid)
    {
        void *objp;
        objp = index_to_obj(cachep, page, get_free_obj(page, page->active));
        page->active++;
        ...
        return objp;
    }
    
    static inline void *index_to_obj(struct kmem_cache *cache, struct page *page,
            unsigned int idx)
    {
        return page->s_mem + cache->size * idx;
    }
    
    static inline freelist_idx_t get_free_obj(struct page *page, unsigned int idx)
    {
        return ((freelist_idx_t *)page->freelist)[idx];
    }
    

    slab_get_obj 通过 freelist 找到可用的对象 idx,然后通过 index_to_obj 计算出相对 slab 内存开始地址(page->s_mem)的偏移。

    ac_put_obj 是把找到的空闲对象放入到 per-CPU 缓存列表中:

    ac->entry[ac->avail++] = objp;
    

    cache_grow 是从伙伴系统中分配内存给 slab:

    static int cache_grow(struct kmem_cache *cachep,
            gfp_t flags, int nodeid, struct page *page)
    {
        void *freelist;
        size_t offset;
        gfp_t local_flags;
        struct kmem_cache_node *n;
        ...
        // 获取指定 node 对应的 slab 链表管理对象
        n = get_node(cachep, nodeid);
        ...
        // 着色计算
        offset = n->colour_next;
        n->colour_next++;
        if (n->colour_next >= cachep->colour)
            n->colour_next = 0;
        ...
        offset *= cachep->colour_off;
        ...
        if (!page)
            // 从伙伴系统中分配物理内存页,用于 slab,根据 cachep->gfporder
            page = kmem_getpages(cachep, local_flags, nodeid);
        if (!page)
            goto failed;
            // 创建 slab 空闲对象列表,内置方式从 page 起始地址开始,外置则通过 kmallocl 来分配
        freelist = alloc_slabmgmt(cachep, page, offset,
                local_flags & ~GFP_CONSTRAINT_MASK, nodeid);
        ...
        // 设置 slab 与 slab 缓冲区(kmem_cache)之间的关联
        slab_map_pages(cachep, page, freelist);
        // 调用各 slab 对象的构造函数(如果有的话),初始化新 slab 中的对象。通常都没有。
        cache_init_objs(cachep, page);
        ...
        // 将新分配的 slab 加入到 free 链表中
        list_add_tail(&page->lru, &(n->slabs_free));
        ...
        n->free_objects += cachep->num;
        ...
        return 1;
        ...
    }
    

    通过上面分析,我们可以发现,在新版的内核中已经没有 slab 结构体,slab 的数据都是存在 page 结构中的,降低了 slab 结构数据的额外维护,图3-18总结了新版内核中的 slab 组织形式。

    图3-18 slab 的组织形式

    在 cache_grow 过程中,着色计算之后的 slab 倾向于把大小相同的对象放在同一个 cache line 中,这也是通过空间换时间提升访问速度的解决方案。

    3.slab 通用缓存的初始化

    这里有个悖论,在 slab 分配器还没初始化完成的时候,像 kmem_cache、kmem_cache_node(三链管理节点)这些结构又是如何初始化的呢?答案是系统一开始是静态分配的,然后再通过 kmalloc 向伙伴系统中申请内存后进行替换。在 start_kernel->mm_init 后调用 kmem_cache_init:

    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_boot_cache(kmem_cache, "kmem_cache",
            offsetof(struct kmem_cache, node) +
                        nr_node_ids * sizeof(struct kmem_cache_node *),
                        SLAB_HWCACHE_ALIGN);// 通过 kmem_cache_create 初始化全局的 kmem_cache
        list_add(&kmem_cache->list, &slab_caches);
        slab_state = PARTIAL;
        ...
        {
            int nid;
    
            for_each_online_node(nid) {
              init_list(kmem_cache, &init_kmem_cache_node[CACHE_CACHE + nid], nid);                                                                // 把三链管理节点用 kmalloc 申请后替换
            ...
            }
        }
        // 通过 kmalloc 创建8到67108864的26个长度分档的通用 cache
        create_kmalloc_caches(ARCH_KMALLOC_FLAGS);
    }
    

    3.5.3 内核态内存管理

    现在我们已经知道了内核对于内存的管理方式,即伙伴系统和 slab 分配器,下面我们再来介绍内核中两种内存分配的函数。

    1.连续物理地址的内存分配

    Linux 在 slab 分配器上提供了 kmalloc 函数,可以为内核申请连续的内存空间,由于 kmalloc 是基于 slab 分配器的,所以比较适合小块内存的申请,图3-19描述了 kmalloc 与 slab 分配器以及伙伴系统的关系。

    图3-19 kmalloc 与 slab 分配器和伙伴系统的关系

    kmalloc 函数在实现的时候调用过程为 kmalloc->__kmalloc->__do_kmalloc,其中__do_kmalloc 的实现主要分为两步:

    1)通过 kmalloc_slab 找到一个大小合适的 kmem_cache 缓存,该缓存在上一节中介绍过,在 kmem_cache_init 函数中进行初始化。

    2)通过 slab_alloc 向 slab 分配器申请对象内存空间。

    2.非连续物理地址的内存分配

    很多时候连续的物理内存地址空间不一定能申请到,而且也不是必须的。Linux 提供 vmalloc 函数来获得连续的线性地址空间,但是其物理内存不一定是连续的。我们可以猜测一下,这样的实现必然是利用了 MMU 来修改页表搞定的。下面我们通过分析 vmalloc 的实现来验证一下。

    vmalloc 函数的调用过程为:vmalloc->__vmalloc_node_flags->__vmalloc_node->__vmalloc_node_range,__vmalloc_node_range 分为两个步骤:

    1)__get_vm_area_node 分配一个可用的线性地址空间,其核心调用为 alloc_vmap_area:

    static struct vmap_area *alloc_vmap_area(unsigned long size,
                                             unsigned long align,
                                             unsigned long vstart, unsigned long vend,
                                             int node, gfp_t gfp_mask)
    {
        struct vmap_area *va;
        struct rb_node *n;
        unsigned long addr;
        int purged = 0;
        struct vmap_area *first;
        ...
            addr = ALIGN(vstart, align);
            if (addr + size < addr)
                goto overflow;
            n = vmap_area_root.rb_node;
            first = NULL;
            while (n) {
                struct vmap_area *tmp;
                tmp = rb_entry(n, struct vmap_area, rb_node);
                if (tmp->va_end >= addr) {        // 该虚拟区域结束地址大于希望分配的开始地址
                    first = tmp;
                    if (tmp->va_start <= addr)        // 虚拟区域起始地址小于希望分配的开始地址,证明找到了这么一块区域
                        break;
                    n = n->rb_left;        // 左子树,往小地址空间寻找
                } else
                    n = n->rb_right;// 右子树,往大地址空间寻找
            }
            if (!first)                // 找到了一块需要寻找的起始地址落在该区域内
                goto found;
        }
        // 检查该区域内是否有空洞存在
        while (addr + size > first->va_start && addr + size <= vend) {
                                                    // 需要分配的结束地址(addr+size)落在该区域内
            if (addr + cached_hole_size < first->va_start)
                cached_hole_size = first->va_start - addr;
            addr = ALIGN(first->va_end, align); // 结束地址+size 小于结束地址,表示溢出了
            if (addr + size < addr)
                goto overflow;
    
                if (list_is_last(&first->list, &vmap_area_list)) // 最后一个区域也没有空洞,那就证明没问题了
                goto found;
            first = list_next_entry(first, list);
        }
    found:
        if (addr + size > vend)
            goto overflow;
        // 下面开始赋值了
        va->va_start = addr;
        va->va_end = addr + size;
        va->flags = 0;
        __insert_vmap_area(va);        // 插入红黑树和链表中
        free_vmap_cache = &va->rb_node;
        ...
        return va;
    
    overflow:        // 溢出
        ...
    }
    

    上述代码就是在 VMALLOC_START 和 VMACLLOC_END 的线性地址空间中,寻找一块连续并且“无空洞”的地址空间的过程。通过图3-20再结合之前内核对线性地址空间管理的知识,在32位系统中,进程的线性地址空间 3GB~4GB 之间是用来映射物理内存 0~1GB 之间的区域的。在这个区域中。3GB~3GB+896MB 直接和物理地址 0~896MB 映射。而在 8MB 空隙之后,就是我们用来给 VMALLOC 映射高端物理内存的 VMALLOC_START~VMALLOC_END 区域。

    图3-20 vmalloc 线性地址空间映射原理

    2)__vmalloc_area_node 为刚才申请的线性地址空间分配物理页面进行页表映射:

    static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
                    pgprot_t prot, int node)
    {
        const int order = 0;
        struct page **pages;
        unsigned int nr_pages, array_size, i;
        const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
                                                                    // 分配的内存页初始化为0
        const gfp_t alloc_mask = gfp_mask | __GFP_NOWARN;
        nr_pages = get_vm_area_size(area) >> PAGE_SHIFT;        // 获取总共需要的页数
        array_size = (nr_pages * sizeof(struct page *));        // page 结构数组所需要的空间大小
        area->nr_pages = nr_pages;
        if (array_size > PAGE_SIZE) { // page 结构数组大于一个页面,则用 vmalloc 来申请,这里会成为递归
            pages = __vmalloc_node(array_size, 1, nested_gfp|__GFP_HIGHMEM,
                    PAGE_KERNEL, node, area->caller);
        } else {
            pages = kmalloc_node(array_size, nested_gfp, node); // 否则通过 kmalloc 来分配
        }
        area->pages = pages;
        ...
        for (i = 0; i < area->nr_pages; i++) {
            struct page *page;
    
            // 通过 alloc_pages 来申请物理页面
            if (node == NUMA_NO_NODE)
                page = alloc_kmem_pages(alloc_mask, order);
            else
                page = alloc_kmem_pages_node(node, alloc_mask, order);
            ...
            area->pages[i] = page;
            ...
        }
    
        if (map_vm_area(area, prot, pages))        // 利用页表项来建立映射
            goto fail;
        return area->addr;
        ...
    }
    

    这个过程较为简单,就是通过 alloc_pages 一页一页申请物理内存,然后和线性地址空间进行映射。

    3.5.4 用户态内存申请

    之前介绍的 kmalloc 和 vmalloc 都是针对内核态的内存分配,针对用户态的内核分配,有 libc 的 malloc 库,或是其他方法,限于篇幅交给读者自己去做探究。这里我仅介绍 malloc 实现原理。

    以32位系统为例,进程线性地址空间的组织形式如图3-21所示。在线性地址空间的底部维护了 text、data、bss 段,在高端维护了栈地址空间。中间则有 heap 区域和 mmap 区域。其中 heap 区域的 start_brk 为 heap 区域的起始,brk 则是通过 sys_brk 系统调用对 heap 区域的伸缩进行控制,而 mmap 区域则通过 mmap 调用随机分配线性地址空间。

    图3-21 进程地址空间组织形式

    无论是 mmap 还是 sys_brk,最终分配的都是线性地址空间,物理内存都是没有分配的。当进程使用到该区域内存的时候,会发生缺页异常。这时候,异常中断响应程序会调用 __do_page_fault->handle_mm_fault->handle_pte_fault->do_fault,最终通过 alloc_pages 分配物理地址空间。

    注意 

    malloc 有多种实现,有 libc 的 ptmalloc,有 jmalloc,有谷歌的 tcmalloc 等。

    3.6 栈内存分配和管理

    进程的切换、函数的调用通常都要使用到栈(stack),进程的栈一般有两个,分别是内核态栈和用户态栈。其中,用户态栈就是上一节中介绍的线性地址空间中的栈地址空间,用户可以通过 mmap 来分配。

    图3-22 进程内核态栈

    每个进程都有自己的内核态栈,用于进程在内核代码中执行期间进行内存分配控制,见图3-22。其所在线性地址中的位置由该进程 TSS 段中 ss0 和 esp0 两个字段指定。ss0 是进程内核态栈的段选择符,esp0 是栈底指针。因此每当进程从用户代码转移进入内核代码中执行时,进程的内核态栈总是空的。进程内核态栈被设置在位于其进程数据结构所在页面的末端,即与进程的任务数据结构(task_struct)放在同一页面内。这是在建立新进程时,fork()程序在任务 TSS 段的内核级栈字段(tss.esp0 和 tss.ss0)中设置的,在前面1.3.2节也已经介绍过。

    3.7 内存管理案例分析

    之前我们分析的是 Linux 内核对内存的管理方式,下面,我们来分析两个应用程序 Memcached 和 Redis 分别是如何来管理内存的。

    虽然内核本身已经有对内存的分配和管理机制,但是假如动不动就通过内核去分配内存,对系统整体性能影响较大,而且不同的业务场景,对内存的需求也不一样,很容易因频繁申请产生大量碎片。所以,很多时候,我们需要在用户态去管理内存。

    3.7.1 Memcached 内存管理机制分析

    Memcached 对内存的管理有点类似内核的 slab 分配器,如图3-23所示。Memcached 根据 slab 内存块的大小,把内存分为不同的 slabclass,每个 slabclass 维护的 slab 是一样大的,slab 在 slab_list 链表中被管理。每个 slab 中被格式化成相同大小的 chunk,可以用来存储 item。

    图3-23 Memcached 内存管理结构

    其中 tails 和 heads 队列用来管理被分配出去的针对相应 slabclass 的 item,而被回收回来的 item 空间由 slots 来维护。

    下面是 slabclass 和 item 的数据结构:

    typedef struct {
        unsigned int size;            //  每个 item 大小
        unsigned int perslab;         //  每个 slab 中包含多少个 item
        void **slots;                 //  空闲的 item 指针
        unsigned int sl_total;        //  已分配空闲的 item 个数
        unsigned int sl_curr;         //  当前空闲的 item 位置(也就是实际空闲 item 个数),从后往前数
        void *end_page_ptr;           //  指向最后一个页面中空闲的 item 开始位置
        unsigned int end_page_free;   //  最后一个页面,item 个数
        unsigned int slabs;           //  实际使用 slab 个数
        void **slab_list;             //  slab 数组指针
        unsigned int list_size;       //  已经分配 slab 个数
        …
        size_t requested;             //  所有使用内存的大小
    } slabclass_t;
    
    typedef struct _stritem {
        struct _stritem *next;// item 在 slab 中存储时,是以双链表的形式存储的,next 是后向指针
        struct _stritem *prev;        // prev 为前向指针
        struct _stritem *h_next;      // hash 桶中元素的链接指针
        rel_time_t      time;         // 最近访问时间
        rel_time_t      exptime;      // 过期时间
        int             nbytes;       // 数据大小
        unsigned short  refcount;     // 引用次数
        uint8_t         nsuffix;
        uint8_t         it_flags;
        uint8_t         slabs_clsid;  // 标记 item 属于哪个 slabclass 下
        uint8_t         nkey;         // key 的长度
        union {
            uint64_t cas;
            char end;
        } data[];                     // 真实的数据信息
    } item;
    

    在系统初始化的时候,会通过 slabs_init 函数为 slabclass 分配空间:

    void slabs_init(const size_t limit, const double factor, const bool prealloc) {
        int i = POWER_SMALLEST - 1;
        unsigned int size = sizeof(item) + settings.chunk_size;  // item 的大小应该是 item 结构 +chunk_size
        mem_limit = limit;
    
        if (prealloc) {
            mem_base = malloc(mem_limit);        // 预分配内存, 先通过 malloc 来申请
            if (mem_base != NULL) {
                mem_current = mem_base;
                mem_avail = mem_limit;
            ...
        }
        memset(slabclass, 0, sizeof(slabclass));
        // 下面计算每个 slabclass 中 slab 的大小,根据 factor 递增
        while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {
            // items 已经根据 n 字节对齐
            if (size % CHUNK_ALIGN_BYTES)
                size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
            slabclass[i].size = size;
            slabclass[i].perslab = settings.item_size_max / slabclass[i].size;
            size *= factor;
            ...
        }
        // 最后一个 slabclass 中的 slab 仅有1个 chunk,大小为 item\_size_max
        power_largest = i;
        slabclass[power_largest].size = settings.item_size_max;
        slabclass[power_largest].perslab = 1;
        ...
        if (prealloc) {
            slabs_preallocate(power_largest);
        }
    }
    

    slabs_init 主要用于初始化 slabclass 的规则(slab 中的 chunk 大小以及每个 slab 中 chunk 的个数)。

    假如内存是预分配的,则会先初始化一下每个 slabclass 中的 slab,该实现较为简单,读者可以自己分析 slabs_preallocate 函数,其最终会调用 do_slabs_alloc->do_slabs_newslab 初始化一个 slab,然后把该 slab 挂载到 slabclass 的 slab_list 队列中。

    假如需要对某个 item 申请内存,则通过 do_item_alloc 来实现:

    item *do_item_alloc(char *key, const size_t nkey, const int flags,
                const rel_time_t exptime, const int nbytes,
                const uint32_t cur_hv) {
        uint8_t nsuffix;
        item *it = NULL;
        char suffix[40];
        size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix,
             &nsuffix);
        ...
        unsigned int id = slabs_clsid(ntotal);
        ...
        search = tails[id];
        ...
        if (!tried_alloc && (tries == 0 || search == NULL))
            it = slabs_alloc(ntotal, id);
        // 下面代码对item进行初始化
        ...
        it->refcount = 1;
        mutex_unlock(&cache_lock);
        it->next = it->prev = it->h_next = 0;
        it->slabs_clsid = id;
    
        DEBUG_REFCNT(it, '*');
        it->it_flags = settings.use_cas ? ITEM_CAS : 0;
        it->nkey = nkey;
        it->nbytes = nbytes;
        memcpy(ITEM_key(it), key, nkey);
        it->exptime = exptime;
        memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);
        it->nsuffix = nsuffix;
        return it;
    }
    

    在 do_item_alloc 中,先通过 item 的总大小找到合适的 slabclass,然后再到 tails 等队列中去找是否有可用的空间,最后,假如没有可用空间了,通过 slabs_alloc 再申请一块 slab 挂到 slabclass 上去(通过 do_slabs_alloc)。

    通过分析可以发现,Memcached 的内存分配机制非常类似于内核的 slab 分配器,也是避免内部碎片的一种解决方案。

    3.7.2 Redis 内存管理机制分析

    在 Redis 中,zmalloc 对内存分配函数进行封装,允许按配置使用 tcmalloc、jemalloc 等库,它们速度快内存使用率高,并支持统计内存使用率。

    在 Redis 的 zmalloc.c 源码中,我们可以看到如下代码:

    #if defined(USE_TCMALLOC)
    #define malloc(size) tc_malloc(size)
    #define calloc(count,size) tc_calloc(count,size)
    #define realloc(ptr,size) tc_realloc(ptr,size)
    #define free(ptr) tc_free(ptr)
    #elif defined(USE_JEMALLOC)
    #define malloc(size) je_malloc(size)
    #define calloc(count,size) je_calloc(count,size)
    #define realloc(ptr,size) je_realloc(ptr,size)
    #define free(ptr) je_free(ptr)
    #endif
    

    从上面的代码中我们可以看到,Redis 在编译时,会先判断是否使用 tcmalloc,如果是,会用 tcmalloc 对应的函数替换掉标准的 libc 中的函数实现。然后判断 jemalloc 是否使用,最后如果都没有使用才会用标准的 libc 中的内存管理函数。

    在2.4以上的 Redis 版本中,jemalloc 已经作为源码包的一部分了,所以可以直接使用。而如果你要使用 tcmalloc 的话,是需要自己安装的。

    Redis 通过 info 命令就能看到使用的内存分配器了。

    对于 tcmalloc、jemalloc 和 libc 对应的三个内存分配器,它们的性能和碎片率如何呢?下面是一个简单测试结果,使用 Redis 自带的 redis-benchmark 写入等量数据进行测试,数据摘自采用不同分配器时 Redis info 信息。我们可以看到,采用 tcmalloc 时碎片率是最低的,为1.01,jemalloc 为1.02,而 libc 的分配器碎片率为1.31,如下所示:

    used_memory:708391440
    used_menory_human:675.57M
    used_memory_rss:715169792
    used_memory_peak:708814040
    used_memory_peak_human:675.98M
    mem_fragmentation_ratio:1.01
    mem_allocator:tcmalloc-1.7
    used_memory:708381168
    used_menory_human:675.56M
    used_memory_rss:723587072
    used_memory_peak:708803768
    used_memory_peak_human:675.97M
    mem_fragmentation_ratio:1.02
    mem_allocator:jemalloc-2.2.1
    used_memory:869000400
    used_menory_human:828.74M
    used_memory_rss:1136689152
    used_memory_peak:868992208
    used_memory_peak_human:828.74M
    mem_fragmentation_ratio:1.31
    mem_allocator:libc
    

    上面的测试数据都是小数据,也就是说单条数据量并不大,下面我们尝试设置 benchmark 的 -d 参数,将 value 值调整为 1k 大小,则测试结果发生了一些变化:

    used_memory:830573680
    used_memory_human:792.10M
    used_memory_rss:849068032
    used_memory_peak:831436048
    used_memory_peak_human:792.92M
    mem_fragmentation_ratio:1.02
    mem_allocator:tcmalloc-1.7
    used_memory:915911024
    used_memory_human:873.48M
    used_memory_rss:927047680
    used_memory_peak:916773392
    used_memory_peak_human:874.30M
    mem_fragmentation_ratio:1.01
    mem_allocator:jemalloc-2.2.1
    used_memory:771963304
    used_memory_human:736.20M
    used_memory_rss:800583680
    used_memory_peak:772784056
    used_memory_peak_human:736.98M
    mem_fragmentation_ratio:1.04
    mem_allocator:libc
    

    可以看出,在分配大块内存和小块内存上,几种分配器的碎片率差距还是比较大的。所以在使用 Redis 的时候,还是尽量用自己真实的数据去做测试,以选择最适合自己数据的分配器。

    3.8 本章小结

    要理解操作系统是如何管理内存的,首先需要了解 MMU 的内存管理机制,其核心还是分段和分页的机制,其中会涉及几个重要地址:线性地址、物理地址、虚拟地址。

    本章以内存在体系结构中的作用为切入点,首先介绍了内存在使用中会遇到的问题,为什么需要管理等,然后介绍了 MMU 以及相关地址空间的核心概念。

    有了底层硬件层面提供的概念和管理能力后,Linux 操作系统就是针对这些能力在上层进行了更加有针对性的建模和封装。开头我们已经提到,内存的管理主要围绕堆和栈来进行。Linux 内核对堆的管理核心还是围绕伙伴算法、slab 分配器来展开的,并且提供了相关的能力:kmalloc、vmalloc、malloc 等。对于栈的管理,我们需要区分内核栈和用户栈。

    最后,为了便于更加深入理解内存管理,我们还介绍了 Memcached 和 Redis 是如何管理内存的。

    内存管理的话题其实还有另一部分,比如系统启动时,内存分配器还没初始化时,系统是如何来分配管理内存的?malloc 有不同实现,细节是怎样的?内存和磁盘之间的交换又是如何实现的?这些问题就交给读者自己去解决了。

    展开全文
  • Netty 作为一款高性能的网络框架,需要处理海量的字节数据,而且 Netty 默认提供了池化对象的内存分配,使用完后归还到...如何减少内存碎片,提高内存的有效利用率? 内存规格介绍 Netty 保留了内存规格分类的设计

    Netty 作为一款高性能的网络框架,需要处理海量的字节数据,而且 Netty 默认提供了池化对象的内存分配,使用完后归还到内存池,所以一套高性能的内存管理机制是 Netty 必不可少的。在上节课中我们介绍了原生 jemalloc 的基本原理,而 Netty 高性能的内存管理也是借鉴 jemalloc 实现的,它同样需要解决两个经典的核心问题:

    • 在单线程或者多线程的场景下,如何高效地进行内存分配和回收?

    • 如何减少内存碎片,提高内存的有效利用率?

    内存规格介绍

    Netty 保留了内存规格分类的设计理念,不同大小的内存块采用的分配策略是不同的,具体内存规格的分类情况如下图所示。

    在这里插入图片描述
    上图中 Tiny 代表 0 ~ 512B 之间的内存块,Samll 代表 512B ~ 8K 之间的内存块,Normal 代表 8K ~ 16M 的内存块,Huge 代表大于 16M 的内存块。在 Netty 中定义了一个 SizeClass 类型的枚举,用于描述上图中的内存规格类型,分别为 Tiny、Small 和 Normal。但是图中 Huge 并未在代码中定义,当分配大于 16M 时,可以归类为 Huge 场景,Netty 会直接使用非池化的方式进行内存分配。

    Netty 在每个区域内又定义了更细粒度的内存分配单位,分别为 Chunk、Page、Subpage,我们将逐一对其进行介绍。

    Chunk 是 Netty 向操作系统申请内存的单位,所有的内存分配操作也是基于 Chunk 完成的,Chunk 可以理解为 Page 的集合,每个 Chunk 默认大小为 16M。

    Page 是 Chunk 用于管理内存的单位,Netty 中的 Page 的大小为 8K,不要与 Linux 中的内存页 Page 相混淆了。假如我们需要分配 64K 的内存,需要在 Chunk 中选取 4 个 Page 进行分配。

    Subpage 负责 Page 内的内存分配,假如我们分配的内存大小远小于 Page,直接分配一个 Page 会造成严重的内存浪费,所以需要将 Page 划分为多个相同的子块进行分配,这里的子块就相当于 Subpage。按照 Tiny 和 Small 两种内存规格,SubPage 的大小也会分为两种情况。在 Tiny 场景下,最小的划分单位为 16B,按 16B 依次递增,16B、32B、48B … 496B;在 Small 场景下,总共可以划分为 512B、1024B、2048B、4096B 四种情况。Subpage 没有固定的大小,需要根据用户分配的缓冲区大小决定,例如分配 1K 的内存时,Netty 会把一个 Page 等分为 8 个 1K 的 Subpage。

    了解了 Netty 不同粒度的内存的分配单位后,我们接下来看看 Netty 中的 jemalloc 是如何实现的。

    在这里插入图片描述

    基于上图的内存池模型,Netty 抽象出一些核心组件,如 PoolArena、PoolChunk、PoolChunkList、PoolSubpage、PoolThreadCache、MemoryRegionCache 等,可以看出与 jemalloc 中的核心概念有些是类似的,接下来我们逐一进行介绍。

    PoolArena

    Netty 借鉴了 jemalloc 中 Arena 的设计思想,采用固定数量的多个 Arena 进行内存分配,Arena 的默认数量与 CPU 核数有关,通过创建多个 Arena 来缓解资源竞争问题,从而提高内存分配效率。线程在首次申请分配内存时,会通过 round-robin 的方式轮询 Arena 数组,选择一个固定的 Arena,在线程的生命周期内只与该 Arena 打交道,所以每个线程都保存了 Arena 信息,从而提高访问效率。

    根据分配内存的类型,ByteBuf 可以分为 Heap 和 Direct,同样 PoolArena 抽象类提供了 HeapArena 和 DirectArena 两个子类。首先看下 PoolArena 的数据结构,如下图所示。

    在这里插入图片描述
    PoolArena 的数据结构包含两个 PoolSubpage 数组和六个 PoolChunkList,两个 PoolSubpage 数组分别存放 Tiny 和 Small 类型的内存块,六个 PoolChunkList 分别存储不同利用率的 Chunk,构成一个双向循环链表。

    之前我们介绍了 Netty 内存规格的分类,PoolArena 对应实现了 Subpage 和 Chunk 中的内存分配,其 中 PoolSubpage 用于分配小于 8K 的内存,PoolChunkList 用于分配大于 8K 的内存。

    PoolSubpage 也是按照 Tiny 和 Small 两种内存规格,设计了tinySubpagePools 和 smallSubpagePools 两个数组,根据关于 Subpage 的介绍,我们知道 Tiny 场景下,内存单位最小为 16B,按 16B 依次递增,共 32 种情况,Small 场景下共分为 512B、1024B、2048B、4096B 四种情况,分别对应两个数组的长度大小,每种粒度的内存单位都由一个 PoolSubpage 进行管理。假如我们分配 20B 大小的内存空间,也会向上取整找到 32B 的 PoolSubpage 节点进行分配。

    PoolChunkList 用于 Chunk 场景下的内存分配,PoolArena 中初始化了六个 PoolChunkList,分别为 qInit、q000、q025、q050、q075、q100,这与 jemalloc 中 run 队列思路是一致的,它们分别代表不同的内存使用率,如下所示:

    qInit,内存使用率为 0 ~ 25% 的 Chunk。

    q000,内存使用率为 1 ~ 50% 的 Chunk。

    q025,内存使用率为 25% ~ 75% 的 Chunk。

    q050,内存使用率为 50% ~ 100% 的 Chunk。

    q075,内存使用率为 75% ~ 100% 的 Chunk。

    q100,内存使用率为 100% 的 Chunk。

    六种类型的 PoolChunkList 除了 qInit,它们之间都形成了双向链表,如下图所示。

    在这里插入图片描述
    随着 Chunk 内存使用率的变化,Netty 会重新检查内存的使用率并放入对应的 PoolChunkList,所以 PoolChunk 会在不同的 PoolChunkList 移动。

    我在刚开始学习 PoolChunkList 的时候的一个疑问就是,qInit 和 q000 为什么需要设计成两个,是否可以合并成一个?其实它们各有用处。

    qInit 用于存储初始分配的 PoolChunk,因为在第一次内存分配时,PoolChunkList 中并没有可用的 PoolChunk,所以需要新创建一个 PoolChunk 并添加到 qInit 列表中。qInit 中的 PoolChunk 即使内存被完全释放也不会被回收,避免 PoolChunk 的重复初始化工作。

    q000 则用于存放内存使用率为 1 ~ 50% 的 PoolChunk,q000 中的 PoolChunk 内存被完全释放后,PoolChunk 从链表中移除,对应分配的内存也会被回收。

    还有一点需要注意的是,在分配大于 8K 的内存时,其链表的访问顺序是 q050->q025->q000->qInit->q075,遍历检查 PoolChunkList 中是否有 PoolChunk 可以用于内存分配,源码如下:

    private void allocateNormal(PooledByteBuf<T> buf, int reqCapacity, int normCapacity) {
    
        if (q050.allocate(buf, reqCapacity, normCapacity) || q025.allocate(buf, reqCapacity, normCapacity) ||
    
            q000.allocate(buf, reqCapacity, normCapacity) || qInit.allocate(buf, reqCapacity, normCapacity) ||
    
            q075.allocate(buf, reqCapacity, normCapacity)) {
    
            return;
    
        }
    
        PoolChunk<T> c = newChunk(pageSize, maxOrder, pageShifts, chunkSize);
    
        boolean success = c.allocate(buf, reqCapacity, normCapacity);
    
        assert success;
    
        qInit.add(c);
    
    }
    
    

    这里你或许有了疑问,为什么会优先选择 q050,而不是从 q000 开始呢?

    可以说这是一个折中的选择,在频繁分配内存的场景下,如果从 q000 开始,会有大部分的 PoolChunk 面临频繁的创建和销毁,造成内存分配的性能降低。如果从 q050 开始,会使 PoolChunk 的使用率范围保持在中间水平,降低了 PoolChunk 被回收的概率,从而兼顾了性能。

    PoolArena 是 Netty 内存分配中非常重要的部分,我们花了较多篇幅进行讲解,对之后理解内存分配的实现原理会有所帮助。

    PoolChunkList

    PoolChunkList 负责管理多个 PoolChunk 的生命周期,同一个 PoolChunkList 中存放内存使用率相近的 PoolChunk,这些 PoolChunk 同样以双向链表的形式连接在一起,PoolChunkList 的结构如下图所示。因为 PoolChunk 经常要从 PoolChunkList 中删除,并且需要在不同的 PoolChunkList 中移动,所以双向链表是管理 PoolChunk 时间复杂度较低的数据结构。

    在这里插入图片描述
    每个 PoolChunkList 都有内存使用率的上下限:minUsage 和 maxUsage,当 PoolChunk 进行内存分配后,如果使用率超过 maxUsage,那么 PoolChunk 会从当前 PoolChunkList 移除,并移动到下一个 PoolChunkList。同理,PoolChunk 中的内存发生释放后,如果使用率小于 minUsage,那么 PoolChunk 会从当前 PoolChunkList 移除,并移动到前一个 PoolChunkList。

    回过头再看下 Netty 初始化的六个 PoolChunkList,每个 PoolChunkList 的上下限都有交叉重叠的部分,如下图所示。因为 PoolChunk 需要在 PoolChunkList 不断移动,如果每个 PoolChunkList 的内存使用率的临界值都是恰好衔接的,例如 1 ~ 50%、50% ~ 75%,那么如果 PoolChunk 的使用率一直处于 50% 的临界值,会导致 PoolChunk 在两个 PoolChunkList 不断移动,造成性能损耗。

    在这里插入图片描述

    PoolChunk

    Netty 内存的分配和回收都是基于 PoolChunk 完成的,PoolChunk 是真正存储内存数据的地方,每个 PoolChunk 的默认大小为 16M,首先我们看下 PoolChunk 数据结构的定义:

    final class PoolChunk<T> implements PoolChunkMetric {
    
        final PoolArena<T> arena;
    
        final T memory; // 存储的数据
    
        private final byte[] memoryMap; // 满二叉树中的节点是否被分配,数组大小为 4096
    
        private final byte[] depthMap; // 满二叉树中的节点高度,数组大小为 4096
    
        private final PoolSubpage<T>[] subpages; // PoolChunk 中管理的 2048 个 8K 内存块
    
        private int freeBytes; // 剩余的内存大小
    
        PoolChunkList<T> parent;
    
        PoolChunk<T> prev;
    
        PoolChunk<T> next;
    
        // 省略其他代码
    
    }
    
    

    PoolChunk 可以理解为 Page 的集合,Page 只是一种抽象的概念,实际在 Netty 中 Page 所指的是 PoolChunk 所管理的子内存块,每个子内存块采用 PoolSubpage 表示。Netty 会使用伙伴算法将 PoolChunk 分配成 2048 个 Page,最终形成一颗满二叉树,二叉树中所有子节点的内存都属于其父节点管理,如下图所示。

    在这里插入图片描述
    结合 PoolChunk 的结构图,我们介绍一下 PoolChunk 中几个重要的属性:

    depthMap 用于存放节点所对应的高度。例如第 2048 个节点 depthMap[1025] = 10。

    memoryMap 用于记录二叉树节点的分配信息,memoryMap 初始值与 depthMap 是一样的,随着节点被分配,不仅节点的值会改变,而且会递归遍历更新其父节点的值,父节点的值取两个子节点中最小的值。

    subpages 对应上图中 PoolChunk 内部的 Page0、Page1、Page2 … Page2047,Netty 中并没有 Page 的定义,直接使用 PoolSubpage 表示。当分配的内存小于 8K 时,PoolChunk 中的每个 Page 节点会被划分成为更小粒度的内存块进行管理,小内存块同样以 PoolSubpage 管理。从图中可以看出,小内存的分配场景下,会首先找到对应的 PoolArena ,然后根据计算出对应的 tinySubpagePools 或者 smallSubpagePools 数组对应的下标,如果对应数组元素所包含的 PoolSubpage 链表不存在任何节点,那么将创建新的 PoolSubpage 加入链表中。

    PoolSubpage

    目前大家对 PoolSubpage 应该有了一些认识,在小内存分配的场景下,即分配的内存大小小于一个 Page 8K,会使用 PoolSubpage 进行管理。首先看下 PoolSubpage 的定义:

    final class PoolSubpage<T> implements PoolSubpageMetric {
    
        final PoolChunk<T> chunk;
    
        private final int memoryMapIdx; // 对应满二叉树节点的下标
    
        private final int runOffset; // PoolSubpage 在 PoolChunk 中 memory 的偏移量
    
        private final long[] bitmap; // 记录每个小内存块的状态
    
        // 与 PoolArena 中 tinySubpagePools 或 smallSubpagePools 中元素连接成双向链表
    
        PoolSubpage<T> prev;
    
        PoolSubpage<T> next;
    
        int elemSize; // 每个小内存块的大小
    
        private int maxNumElems; // 最多可以存放多少小内存块:8K/elemSize
    
        private int numAvail; // 可用于分配的内存块个数
    
        // 省略其他代码
    
    }
    
    

    PoolSubpage 中每个属性的含义都比较清晰易懂,我都以注释的形式标出,在这里就不一一赘述了,只指出其中比较重点的两个知识点:

    第一个就是 PoolSubpage 是如何记录内存块的使用状态的呢?PoolSubpage 通过位图 bitmap 记录子内存是否已经被使用,bit 的取值为 0 或者 1,如下图所示。
    在这里插入图片描述
    第二个就是 PoolSubpage 和 PoolArena 之间是如何联系起来的?

    通过之前的介绍,我们知道 PoolArena 在创建是会初始化 tinySubpagePools 和 smallSubpagePools 两个 PoolSubpage 数组,数组的大小分别为 32 和 4。

    假如我们现在需要分配 20B 大小的内存,会向上取整为 32B,从满二叉树的第 11 层找到一个 PoolSubpage 节点,并把它等分为 8KB/32B = 256B 个小内存块,然后找到这个 PoolSubpage 节点对应的 PoolArena,将 PoolSubpage 节点与 tinySubpagePools[1] 对应的 head 节点连接成双向链表,形成下图所示的结构。
    在这里插入图片描述
    下次再有 32B 规格的内存分配时,会直接查找 PoolArena 中 tinySubpagePools[1] 元素的 next 节点是否存在可用的 PoolSubpage,如果存在将直接使用该 PoolSubpage 执行内存分配,从而提高了内存分配效率,其他内存规格的分配原理类似。

    PoolThreadCache & MemoryRegionCache

    PoolThreadCache 顾名思义,对应的是 jemalloc 中本地线程缓存的意思。那么 PoolThreadCache 是如何被使用的呢?它可以缓存哪些类型的数据呢?

    当内存释放时,与 jemalloc 一样,Netty 并没有将缓存归还给 PoolChunk,而是使用 PoolThreadCache 缓存起来,当下次有同样规格的内存分配时,直接从 PoolThreadCache 取出使用即可。PoolThreadCache 缓存 Tiny、Small、Normal 三种类型的数据,而且根据堆内和堆外内存的类型进行了区分,如 PoolThreadCache 的源码定义所示:

    final class PoolThreadCache {
    
        final PoolArena<byte[]> heapArena;
    
        final PoolArena<ByteBuffer> directArena;
    
        private final MemoryRegionCache<byte[]>[] tinySubPageHeapCaches;
    
        private final MemoryRegionCache<byte[]>[] smallSubPageHeapCaches;
    
        private final MemoryRegionCache<ByteBuffer>[] tinySubPageDirectCaches;
    
        private final MemoryRegionCache<ByteBuffer>[] smallSubPageDirectCaches;
    
        private final MemoryRegionCache<byte[]>[] normalHeapCaches;
    
        private final MemoryRegionCache<ByteBuffer>[] normalDirectCaches;
    
        // 省略其他代码
    
    }
    
    

    PoolThreadCache 中有一个重要的数据结构:MemoryRegionCache。MemoryRegionCache 有三个重要的属性,分别为 queue,sizeClass 和 size,下图是不同内存规格所对应的 MemoryRegionCache 属性取值范围。

    在这里插入图片描述
    MemoryRegionCache 实际就是一个队列,当内存释放时,将内存块加入队列当中,下次再分配同样规格的内存时,直接从队列中取出空闲的内存块。

    PoolThreadCache 将不同规格大小的内存都使用单独的 MemoryRegionCache 维护,如下图所示,图中的每个节点都对应一个 MemoryRegionCache,例如 Tiny 场景下对应的 32 种内存规格会使用 32 个 MemoryRegionCache 维护,所以 PoolThreadCache 源码中 Tiny、Small、Normal 类型的 MemoryRegionCache 数组长度分别为 32、4、3。

    在这里插入图片描述
    到此为止,Netty 中内存管理所涉及的核心组件都介绍完毕,推荐你回头再梳理一遍 jemalloc 的核心概念,与 Netty 做一个简单的对比,思路会更加清晰。

    展开全文
  • Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有...

    伙伴系统的概述

    Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两种:一种是之前介绍过的利用非连续内存的分配;另外一种则是用一种有效的方法来监视内存,保证在内核只要申请一小块内存的情况下,不会从大块的连续空闲内存中截取一段过来,从而保证了大块内存的连续性和完整性。显然,前者不能成为解决问题的普遍方法,一来用来映射非连续内存线性地址空间有限,二来每次映射都要改写内核的页表,进而就要刷新TLB,这使得分配的速度大打折扣,这对于要频繁申请内存的内核显然是无法忍受的。因此Linux采用后者来解决外部碎片的问题,也就是著名的伙伴系统。

    什么是伙伴系统?

    伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求。在最初,只有一个块,也就是整个内存,假如为1M大小,而允许的最小块为64K,那么当我们申请一块200K大小的内存时,就要先将1M的块分裂成两等分,各为512K,这两分之间的关系就称为伙伴,然后再将第一个512K的内存块分裂成两等分,各位256K,将第一个256K的内存块分配给内存,这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。
    在这里插入图片描述

    1. 初始化时,系统拥有1M的连续内存,允许的最小的内存块为64K,图中白色的部分为空闲的内存块,着色的代表分配出去了得内存块。

    2. 程序A申请一块大小为34K的内存,对应的order为0,即2^0=1个最小内存块。
      2.1. 系统中不存在order 0(64K)的内存块,因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)。
      2.2. 仍然没有order 0的内存块,因此order 3的内存块分裂成两个order 2的内存块(256K)。
      2.3 仍然没有order 0的内存块,因此order 2的内存块分裂成两个order 1的内存块(128K)。
      2.4. 仍然没有order 0的内存块,因此order 1的内存块分裂成两个order 0的内存块(64K)
      2.5. 找到了order 0的内存块,将其中的一个分配给程序A,现在伙伴系统的内存为一个order 0的内存块,一个order1的内存块,一个order 2的内存块以及一个order 3的内存块

    3. 程序B申请一块大小为66K的内存,对应的order为1,即2^1=2个最小内存块,由于系统中正好存在一个order 1的内 存块,所以直接用来分配。

    4. 程序C申请一块大小为35K的内存,对应的order为0,同样由于系统中正好存在一个order 0的内存块,直接用来分配。

    5. 程序D申请一块大小为67K的内存,对应的order为1
      5.1 系统中不存在order 1的内存块,于是将order 2的内存块分裂成两块order 1的内存块。
      5.2 找到order 1的内存块,进行分配。

    6. 程序B释放了它申请的内存,即一个order 1的内存块。

    7. 程序D释放了它申请的内存
      7.1 一个order 1的内存块回收到内存当中
      7.2由于该内存块的伙伴也是空闲的,因此两个order 1的内存块合并成一个order 2的内存块

    8. 程序A释放了它申请的内存,即一个order 0的内存块

    9. 程序C释放了它申请的内存。
      9.1 一个order 0的内存块被释放。
      9.2 两个order 0伙伴块都是空闲的,进行合并,生成一个order 1的内存块m。
      9.3 两个order 1伙伴块都是空闲的,进行合并,生成一个order 2的内存块。
      9.4 两个order 2伙伴块都是空闲的,进行合并,生成一个order 3的内存块。
      9.5 两个order 3伙伴块都是空闲的,进行合并,生成一个order 4的内存块。

    相关的数据结构

     在前面的文章中已经简单的介绍过struct zone这个结构,对于每个管理区都有自己的struct zone,而struct zone中的struct free_area则是用来描述该管理区伙伴系统的空闲内存块的
    
    <mmzone.h>
    
    struct zone {
    	...
             ...	
    	struct free_area	free_area[MAX_ORDER];
    	...
    	...
    }
     
    
    <mmzone.h>
    
    struct free_area {
    	struct list_head	free_list[MIGRATE_TYPES];
    	unsigned long		nr_free;
    };
    

    free_area共有MAX_ORDER个元素,其中第order个元素记录了2^order
    的空闲块,这些空闲块在free_list中以双向链表的形式组织起来,对于同等大小的空闲块,其类型不同,将组织在不同的free_list中,nr_free记录了该free_area中总共的空闲内存块的数量。MAX_ORDER的默认值为11,这意味着最大内存块的大小为2^10=1024个页框。对于同等大小的内存块,每个内存块的起始页框用于链表的节点进行相连,这些节点对应的着struct page中的lru域

    struct page {
    	
    	...
    	...
    	struct list_head lru;		/* Pageout list, eg. active_list
    					 * protected by zone->lru_lock !
    					 */
    	...
    }
    

    连接示意图如下:
    在这里插入图片描述
    在2.6.24之前的内核版本中,free_area结构中只有一个free_list数组,而从2.6.24开始,free_area结构中存有MIGRATE_TYPES个free_list,这些数组是根据页框的移动性来划分的,为什么要进行这样的划分呢?实际上也是为了减少碎片而提出的,我们考虑下面的情况:

    在这里插入图片描述
    图中一共有32个页,只分配出了4个页框,但是能够分配的最大连续内存也只有8个页框(因为伙伴系统分配出去的内存必须是2的整数次幂个页框),内核解决这种问题的办法就是将不同类型的页进行分组。分配出去的页面可分为三种类型:

    • 不可移动页(Non-movable pages):这类页在内存当中有固定的位置,不能移动。内核的核心分配的内存大多属于这种类型
    • 可回收页(Reclaimable
      pages):这类页不能直接移动,但可以删除,其内容页可以从其他地方重新生成,例如,映射自文件的数据属于这种类型,针对这种页,内核有专门的页面回收处理
    • 可移动页:这类页可以随意移动,用户空间应用程序所用到的页属于该类别。它们通过页表来映射,如果他们复制到新的位置,页表项也会相应的更新,应用程序不会注意到任何改变。

    假如上图中大部分页都是可移动页,而分配出去的四个页都是不可移动页,由于不可移动页插在了其他类型页的中间,就导致了无法从原本空闲的连续内存区中分配较大的内存块。考虑下图的情况:

    在这里插入图片描述

    将可回收页和不可移动页分开,这样虽然在不可移动页的区域当中无法分配大块的连续内存,但是可回收页的区域却没有受其影响,可以分配大块的连续内存。

    内核对于迁移类型的定义如下:

    <mmzone.h>
    
    #define MIGRATE_UNMOVABLE     0
    #define MIGRATE_RECLAIMABLE   1
    #define MIGRATE_MOVABLE       2
    #define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */
    #define MIGRATE_RESERVE       3
    #define MIGRATE_ISOLATE       4 /* can't allocate from here */
    #define MIGRATE_TYPES         5
    

    前三种类型已经介绍过

    • MIGRATE_PCPTYPES是per_cpu_pageset,即用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目
    • MIGRATE_RESERVE是在前三种的列表中都没用可满足分配的内存块时,就可以从MIGRATE_RESERVE分配
    • MIGRATE_ISOLATE用于跨越NUMA节点移动物理内存页,在大型系统上,它有益于将物理内存页移动到接近于是用该页最频繁地CPU

    MIGRATE_TYPES表示迁移类型的数目

    当一个指定的迁移类型所对应的链表中没有空闲块时,将会按以下定义的顺序到其他迁移类型的链表中寻找

    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 */
    }
    

    ————————————————
    版权声明:本文为CSDN博主「橙色逆流」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/vanbreaker/article/details/7605367

    展开全文
  • 操作系统(内存管理)

    热门讨论 2009-09-20 12:55:25
    文中将为您提供如何管理内存的细节,然后将进一步展示如何手工管理内存如何使用引用计数或者内存池来半手工地管理内存,以及如何使用垃圾收集自动管理内存。 为什么必须管理内存 内存管理是计算机编程最为基本的...
  • 解读: InnoDB支持事物、行级锁、并发性能更好,CPU及内存缓存页优化使得资源利用率更高。 【强制】(2)每张表必须设置一个主键ID,且这个主键ID使用自增主键(在满足需要的情况下尽量短),除非在分库分表环境下。...

    本篇文章作为从0开始建立数据库系列的补充,详细说明了一些数据库建表/SQL语句/索引规范

    一、建表规约

    【强制】(1) 存储引擎必须使用InnoDB
    解读: InnoDB支持事物、行级锁、并发性能更好,CPU及内存缓存页优化使得资源利用率更高。

    【强制】(2)每张表必须设置一个主键ID,且这个主键ID使用自增主键(在满足需要的情况下尽量短),除非在分库分表环境下。
    解读: 由于InnoDB组织数据的方式决定了需要有一个主键,而且若是这个主键ID是单调递增的可以有效提高插入的性能,避免过多的页分裂、减少表碎片提高空间的使用率。而在分库分表环境下,则需要统一来分配各个表中的主键值,从而避免整个逻辑表中主键重复。

    【强制】(3)必须使用utf8mb4字符集
    解读: 在Mysql中的UTF-8并非“真正的UTF-8”,而utf8mb4”才是真正的“UTF-8”。

    【强制】(4) 数据库表、表字段必须加入中文注释
    解读: 大家都别懒

    【强制】(5) 库名、表名、字段名均小写,下划线风格,不超过32个字符,必须见名知意,禁止拼音英文混用。
    解读: 约定

    【强制】(6)单表列数目必须小于30,若超过则应该考虑将表拆分
    解读: 单表列数太多使得Mysql服务器处理InnoDB返回数据之间的映射成本太高

    【强制】(7)禁止使用外键,如果有外键完整性约束,需要应用程序控制
    解读: 外键会导致表与表之间耦合,UPDATE与DELETE操作都会涉及相关联的表,十分影响SQL的性能,甚至会造成死锁。

    【强制】(8)必须把字段定义为NOT NULL并且提供默认值
    解读: a、NULL的列使索引/索引统计/值比较都更加复杂,对MySQL来说更难优化 b、NULL这种类型Msql内部需要进行特殊处理,增加数据库处理记录的复杂性;同等条件下,表中有较多空字段的时候,数据库的处理性能会降低很多 c、NULL值需要更多的存储空,无论是表还是索引中每行中的NULL的列都需要额外的空间来标识

    【强制】(9)禁用保留字,如DESC、RANGE、MARCH等,请参考Mysql官方保留字。

    【强制】( 10)如果存储的字符串长度几乎相等,使用CHAR定长字符串类型。
    解读: 能够减少空间碎片,节省存储空间。

    【建议】(11)在一些场景下,考虑使用TIMESTAMP代替DATETIME。
    解读: a、这两种类型的都能表达"yyyy-MM-dd HH:mm:ss"格式的时间,TIMESTAMP只需要占用4个字节的长度,可以存储的范围为(1970-2038)年,在各个时区,所展示的时间是不一样的;b、而DATETIME类型占用8个字节,对时区不敏感,可以存储的范围为(1001-9999)年。

    【建议】(12)当心自动生成的Schema,建议所有的Schema手动编写。
    解读: 对于一些数据库客户端不要太过信任。

    二、SQL规约

    【建议】 (1) 为了充分利用缓存,不允许使用自定义函数、存储函数、用户变量。
    解读: 如果查询中包含任何用户自定义函数、存储函数、用户变量、临时表、Mysql库中的系统表,其查询结果都不会被缓存。比如函数NOW()或者CURRENT_DATE()会因为不同的查询时间,返回不同的查询结果。

    【强制】(2)在查询中指定所需的列,而不是直接使用“ * ”返回所有的列
    解读: a)读取不需要的列会增加CPU、IO、NET消耗 b)不能有效的利用覆盖索引

    【强制】(3)不允许使用属性隐式转换
    解读: 假设我们在手机号列上添加了索引,然后执行下面的SQL会发生什么?explain SELECT user_name FROM parent WHERE phone=13812345678;很明显就是索引不生效,会全表扫描。

    【建议】(4)在WHERE条件的属性上使用函数或者表达式
    解读: Mysql无法自动解析这种表达式,无法使用到索引。

    【强制】(5)禁止使用外键与级联,一切外键概念必须在应用层解决。
    解读: 外键与级联更新适用于单机低并发,不适合分布式、高并发集群;级联更新是强阻塞,存在数据库更新风暴的风险;外键影响数据库的插入速度。

    【建议】(6)应尽量避免在WHERE子句中使用or作为连接条件
    解读: 根据情况可以选择使用UNION ALL来代替OR

    【强制】(7)不允许使用%开头的模糊查询
    解读: 根据索引的最左前缀原理,%开头的模糊查询无法使用索引,可以使用ES来做检索。

    三、索引规约

    【建议】(1)避免在更新比较频繁、区分度不高的列上单独建立索引
    解读: 区分度不高的列单独创建索引的优化效果很小,但是较为频繁的更新则会让索引的维护成本更高

    【强制】(2) JOIN的表不允许超过五个。需要JOIN的字段,数据类型必须绝对一致; 多表关联查询时,保证被关联的字段需要有索引。
    解读: 太多表的JOIN会让Mysql的优化器更难权衡出一个“最佳”的执行计划(可能性为表数量的阶乘),同时要注意关联字段的类型、长度、字符编码等等是否一致。

    【强制】(3)在一个联合索引中,若第一列索引区分度等于1,那么则不需要建立联合索引。
    解读: 索引通过第一列就能够完全定位的数据,所以联合索引的后边部分是不需要的。

    【强制】(4)建立联合索引时,必须将区分度更高的字段放在左边
    解读: 区分度更高的列放在左边,能够在一开始就有效的过滤掉无用数据。提高索引的效率,相应我们在Mapper中编写SQL的WHERE条件中有多个条件时,需要先看看当前表是否有现成的联合索引直接使用,注意各个条件的顺序尽量和索引的顺序一致。

    【建议】(5)利用覆盖索引来进行查询操作,避免回表
    解读: 覆盖查询即是查询只需要通过索引即可拿到所需DATA,而不再需要再次回表查询,所以效率相对很高。我们在使用EXPLAIN的结果,extra列会出现:“using index”。这里也要强调一下不要使用“SELECT * ”,否则几乎不可能使用到覆盖索引。

    【建议】(6)在较长VARCHAR字段,例如VARCHAR(100)上建立索引时,应指定索引长度,没必要对全字段建立索引,根据实际文本区分度决定索引长度即可。
    解读: 索引的长度与区分度是一对矛盾体,一般对字符串类型数据,若长度为20的索引,区分度会高达90%以上,则可以考虑创建长度例为20的索引,而非全字段索引。例如可以使用SELECT COUNT(DISTINCT LEFT(lesson_code, 20)) / COUNT(*) FROM lesson;来确定lesson_code字段字符长度为20时文本区分度。

    【建议】(7)如果有ORDER BY的场景,请注意利用索引的有序性。ORDER BY最后的字段是联合索引的一部分,并且放在索引组合顺序的最后,避免出现file_sort的情况,影响查询性能。
    解读: 1、假设有查询条件为WHERE a=? and b=? ORDER BY c; 存在索引:a_b_c,则此时可以利用索引排序。2、反例:在查询条件中包含了范围查询,那么索引有序性无法利用,如:WHERE a>10 ORDER BY b; 索引a_b无法排序。

    【建议】(8)在where中索引的列不能某个表达式的一部分,也不能是函数的参数。
    解读: 即是某列上已经添加了索引,但是若此列成为表达式的一部分、或者是函数的参数,Mysql无法将此列单独解析出来,索引也不会生效。

    【建议】 (9)我们在where条件中使用范围查询时,索引最多用于一个范围条件,超过一个则后边的不走索引。
    解读: Mysql能够使用多个范围条件里边的最左边的第一个范围查询,但是后边的范围查询则无法使用。

    【建议】 (10)在多个表进行外连接时,表之间的关联字段类型必须完全一致
    解读: 当两个表进行Join时,字段类型若没有完全一致,则加索引也不会生效,这里的完全一致包括但不限于字段类型、字段长度、字符集、collection等等

    参考

    《High.Performance.MySQL.3rd.Edition》
    《阿里巴巴java开发手册》

    个人公众号:Smilecoc的杂货铺,欢迎关注!
    在这里插入图片描述

    展开全文
  • Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两...
  • Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两...
  • Linux伙伴系统

    2015-08-04 22:27:07
    Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两...
  • 伙伴系统的概述 (一)

    2016-03-28 17:31:14
     Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有...
  •  Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有...
  • Linux伙伴系统1

    2014-05-14 14:53:00
    Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两...
  • 因为Matlab用堆管理内存,所以运行时会产生内存碎片,使内存产生很多闲置的空间,当闲置空间太多时,就没有足够的内存保存新的大型变量,并导致“Out of memory”错误产生,此时,可使用pack函数把数据压入内存,...
  • delphi 开发经验技巧宝典源码

    热门讨论 2010-08-12 16:47:23
    0025 有效利用条件语句和嵌套条件语句 20 0026 有效利用循环语句和嵌套循环语句 21 0027 使用GoTo跳转语句 21 0028 有效使用Case Else语句 22 0029 保证数组循环的安全性 22 0030 获取枚举值列表 23 ...
  • 0025 有效利用条件语句和嵌套条件语句 20 0026 有效利用循环语句和嵌套循环语句 21 0027 使用GoTo跳转语句 21 0028 有效使用Case Else语句 22 0029 保证数组循环的安全性 22 0030 获取枚举值列表 23 ...
  • 0025 有效利用条件语句和嵌套条件语句 20 0026 有效利用循环语句和嵌套循环语句 21 0027 使用GoTo跳转语句 21 0028 有效使用Case Else语句 22 0029 保证数组循环的安全性 22 0030 获取枚举值列表 23 ...
  • 0025 有效利用条件语句和嵌套条件语句 20 0026 有效利用循环语句和嵌套循环语句 21 0027 使用GoTo跳转语句 21 0028 有效使用Case Else语句 22 0029 保证数组循环的安全性 22 0030 获取枚举值列表 23 ...
  • 0025 有效利用条件语句和嵌套条件语句 20 0026 有效利用循环语句和嵌套循环语句 21 0027 使用GoTo跳转语句 21 0028 有效使用Case Else语句 22 0029 保证数组循环的安全性 22 0030 获取枚举值列表 23 ...
  • 0025 有效利用条件语句和嵌套条件语句 20 0026 有效利用循环语句和嵌套循环语句 21 0027 使用GoTo跳转语句 21 0028 有效使用Case Else语句 22 0029 保证数组循环的安全性 22 0030 获取枚举值列表 23 ...
  • •不要求作业连续存放,有效地解决了“碎片”问题。与分区式相比,不需移动作业;与多重分区比,无零星碎片产生。 缺点: •要处理页面中断、缺页中断处理等,系统开销较大; •有可能产生“抖动”...
  • 8.3.1 在内存中进行全部或大部分排序 8.3.2 最小化排序时的空间管理开销 8.3.3 使用多个 TEMP 表空间分布排序 8.4 优化数据存储的技术 8.4.1 使行链接和行迁移最小化 8.4.2 检测行链接/迁移 8.4.3 确定模式中...
  • 编辑推荐通过学习《Oracle Database 10g 性能调整与优化》,读者可以了解到如何选择最优化的索引选项,有效地管理驱动器和磁盘阵列,对查询执行故障检修,以及可靠地预测将来的性能。《Oracle Database 10g 性能调整...
  • 此外,它还对事件日志和 Windows 2000/XP 休眠文件(当休眠笔记本电脑时保存系统内存的地方)进行碎片整理。  Process Monitor  进程监视器,这是一个高级的Windows监视工具,不但可以监视进程/线程,还可以关注到...
  • 8.4.5 备注——有效地探索多项计划 349 8.5 统计信息、基数估计和开销 350 8.5.1 统计信息设计 351 8.5.2 密度/频度信息 353 8.5.3 筛选的统计信息 355 8.5.4 字符串统计信息 356 8.5.5 基数估计细节 ...
  • 8.4.5 备注——有效地探索多项计划 349 8.5 统计信息、基数估计和开销 350 8.5.1 统计信息设计 351 8.5.2 密度/频度信息 353 8.5.3 筛选的统计信息 355 8.5.4 字符串统计信息 356 8.5.5 基数估计细节 ...
  • 8.4.5 备注——有效地探索多项计划 349 8.5 统计信息、基数估计和开销 350 8.5.1 统计信息设计 351 8.5.2 密度/频度信息 353 8.5.3 筛选的统计信息 355 8.5.4 字符串统计信息 356 8.5.5 基数估计细节 ...
  • 值范围: Oracle8i National Language Support Guide 中指定的任何有效的10 字节字符串。 默认值: BINARY nls_currency: 说明: 为 L 数字格式元素指定用作本地货币符号的字符串。该参数的默认值由 NLS_TERRITORY ...

空空如也

空空如也

1 2
收藏数 34
精华内容 13
关键字:

内存碎片如何有效利用