《LINUX3.0内核源代码分析》第四章：内存管理(7)

摘要：本文主要讲述linux如何处理ARM cortex A9多核处理器的内存管理部分。包括对vmalloc、vfree函数的分析。

其实现在写的东西，几年前在看老版本代码时就注释过了。目前在看3.0代码，将以前的东西复习一下，顺便发表到CU上与大家共享，大家在看博客的时候，如果觉得有不清楚的地方，请先阅读《深入理解linux内核》一书。

 

法律声明：《LINUX3.0内核源代码分析》系列文章由谢宝友（）发表于http://xiebaoyou.blog.chinaunix.net，文章中的LINUX3.0源代码遵循GPL协议。除此以外，文档中的其他内容由作者保留所有版权。谢绝转载。

 

    在伙伴系统中多次分配页面后，可能造成伙伴系统中的页面被分割成较小的非连续页面。这些非连续页面被称为外碎片。虽然其总量还比较多，但是由于在内核线性地址空间不连续，因此通过alloc_pages可能无法分配大块的内存空间，造成内存分配失败。解决这个问题的办法就是将这些不连续的内存通过pte页表重新映射。这样，即使其物理地址不连续，也可以用一段连续的虚拟地址进行访问。

    这个工作是由vmalloc完成的。听起来这是一个不错的办法，充分利用了物理内存。其实不然，内核开发者已经建立驱动尽量少用这个函数。这是有理由的：因为外碎片可以随着内存分配释放过程而得到解决，最终，这些小的非连续物理内存可以与释放的页面合并到大的伙伴区中，以满足大块连续内存的分配。但是如果这些非连续物理内存被vmalloc使用后，即使与这些非连续物理内存相邻的伙伴区域被释放，也无法再组成大的区域了，也就是说，这会在伙伴区域中形成空洞。这对伙伴管理系统的伤害的巨大的。

    不过，既然内核提供了这个函数，并且内核中也有某些地方使用了这个东西，那我们还是介绍一下它吧，其定义是：

 

void *vmalloc(unsigned long size)
{
    return __vmalloc_node_flags(size, -1, GFP_KERNEL | __GFP_HIGHMEM);
}

    在分析__vmalloc_node_flags之前，我们需要先了解数据结构vm_struct。我们知道，在内核地址空间中，为kmap和vmalloc各保留了一段地址空间。由于vmalloc可以指定映射的地址空间长度，那么就需要使用一个数据结构来表示已经被vmalloc占用的地址空间，这就是vm_struct结构。它被组织在链表vmlist中。

 

/**
 * 非连续内存区的描述符
 */
struct vm_struct {
    /**
     * 指向下一个vm_struct结构的指针。
     */
    struct vm_struct    *next;
    /**
     * 内存区内第一个内存单元的线性地址。
     */
    void            *addr;
    /**
     * 内存区大小加4096(内存区之间的安全区的大小)
     */
    unsigned long        size;
    /**
     * 非连续内存区映射的内存的类型。
     * VM_ALLOC表示使用vmalloc得到的页.
     * VM_MAP表示使用vmap映射的已经被分配的页。
     * VM_IOREMAP表示使用ioremap映射的硬件设备内存。
     */
    unsigned long        flags;
    /**
     * 指向nr_pages数组的指针，该数组由指向页描述符的指针组成。
     */
    struct page        **pages;
    /**
     * 内存区包含的页面的个数。
     */
    unsigned int        nr_pages;
    /**
     * 一般为0,除非内存已经被创建来映射一个硬件设备IO共享内存。
     */
    phys_addr_t        phys_addr;
    /**
     * 调用vmalloc函数的上层函数地址。调试用。
     */
    void            *caller;
};

保护vmlist链表的读写锁是vmlist_lock。

   

真正干实事的函数是__vmalloc_node_range：

void *__vmalloc_node_range(unsigned long size, unsigned long align,
            unsigned long start, unsigned long end, gfp_t gfp_mask,
            pgprot_t prot, int node, void *caller)
{
    struct vm_struct *area;
    void *addr;
    unsigned long real_size = size;

    /* vmalloc分配的大小必须是页面的整数倍，这里将长度对齐到页面 */
    size = PAGE_ALIGN(size);
    /* 分配长度为0，或者长度大于限制数，都返回失败 */
    if (!size || (size >> PAGE_SHIFT) > totalram_pages)
        return NULL;

    /* 在vmalloc地址区间中找到合适的区域，这是通过遍历vmlist链表来实现的 */
    area = __get_vm_area_node(size, align, VM_ALLOC, start, end, node,
                 gfp_mask, caller);

    /* vmalloc虚拟地址空间不足，可能是分配的长度太大，返回失败 */
    if (!area)
        return NULL;

    /* 这里分配物理页面，并进行pte页表项映射 */
    addr = __vmalloc_area_node(area, gfp_mask, prot, node, caller);

    /*
     * A ref_count = 3 is needed because the vm_struct and vmap_area
     * structures allocated in the __get_vm_area_node() function contain
     * references to the virtual address of the vmalloc'ed block.
     */
    /* 调试代码，内核内存泄漏检测 */
    kmemleak_alloc(addr, real_size, 3, gfp_mask);

    /* 返回映射的虚拟地址 */
    return addr;
}

__vmalloc_node_range函数也仅仅是一层简单的封装，接下来我们分析__get_vm_area_node函数和__vmalloc_area_node函数。

 

 

/* 为vmalloc分配一段可用的虚拟地址空间 */
static struct vm_struct *__get_vm_area_node(unsigned long size,
        unsigned long align, unsigned long flags, unsigned long start,
        unsigned long end, int node, gfp_t gfp_mask, void *caller)
{
    static struct vmap_area *va;
    struct vm_struct *area;

    /**
     * 由于虚拟地址空间分配过程中可能由于地址空间紧张而导致进程被阻塞，因此vmalloc函数不能用于中断上下文
     * 这里检查是否处于中断上下文，如果是则进入crash
     */
    BUG_ON(in_interrupt());
    if (flags & VM_IOREMAP) {/* 如果上层调用是通过ioremap进入的 */
        int bit = fls(size);/* 根据长度计算它的最高位，也就是计算log2(size) */

        if (bit > IOREMAP_MAX_ORDER)/* 超过2^1024 * 4个页面，即超过16M */
            bit = IOREMAP_MAX_ORDER;/* 以16M为边界对齐ioremap虚拟地址 */
        else if (bit < PAGE_SHIFT)/* 小于1个页面 */
            bit = PAGE_SHIFT;/* 计算边界用，至少以页面为边界 */

        align = 1ul << bit;/* 起始地址以分配大小的边界对齐，也就是说，如果分配1M到2M之间的内存，则以1M为边界对齐 */
    }

    /* 分配长度至少以页面为单位 */
    size = PAGE_ALIGN(size);
    if (unlikely(!size))/* 参数不合法 */
        return NULL;

    /* 分配一个vm_struct数据结构，它代表一段vmalloc地址空间 */
    area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
    if (unlikely(!area))/* 分配vm_struct失败，退出 */
        return NULL;

    /*
     * We always allocate a guard page.
     */
    /**
     * 这里将长度增加一个页面，是为了在多个vmalloc地址空间之间，增加一段空洞
     * 这些空洞没有分配实际的物理页面，也没有进行虚拟地址映射，如果有进程访问vmalloc分配的内存越界，则会触段错误。
     * 我想这可能是由于vmalloc多用于驱动中，内核开发者对驱动开发者还是有那么一点点不放心。
     */
    size += PAGE_SIZE;

    /**
     * 这里才真正操作vmap_area_root红黑树，在其中搜索满足条件的地址块
     * 老版本是通过链表管理vm_struct，新版本改成红黑树了
     */
    va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
    if (IS_ERR(va)) {/* 没有满足条件的地址空间，退出 */
        kfree(area);/* 退出前释放刚才分配的vm_struct结构 */
        return NULL;
    }

    /* 将分配的地址空间插入到vmlist链表，这个链表与老版本是一样的 */
    insert_vmalloc_vm(area, va, flags, caller);
    return area;
}

 我们接下来看看内核如何从KVA地址空间中分配一段可用的地址区域：

 

/* 根据指定的长度和对齐要求，在KVA空间中分配一段可用空间 */
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;

    /**
     * 这几种情况都是不可饶恕的错误:
     *        长度为0
     *        长度不是页面的整数倍
     *        长度不是2的n次方
     */
    BUG_ON(!size);
    BUG_ON(size & ~PAGE_MASK);
    BUG_ON(!is_power_of_2(align));

    /* KVA地址空间通过vmap_area结构进行管理，这里分配一个vmap_area描述符。与vm_struct不同，vm_struct仅仅代表一个与vmalloc对应的地址空间 */
    va = kmalloc_node(sizeof(struct vmap_area),
            gfp_mask & GFP_RECLAIM_MASK, node);
    if (unlikely(!va))/* 分配失败，退出 */
        return ERR_PTR(-ENOMEM);

retry:
    /* 获得保护KVA红黑树的自旋锁 */
    spin_lock(&vmap_area_lock);
    /*
     * Invalidate cache if we have more permissive parameters.
     * cached_hole_size notes the largest hole noticed _below_
     * the vmap_area cached in free_vmap_cache: if size fits
     * into that hole, we want to scan from vstart to reuse
     * the hole instead of allocating above free_vmap_cache.
     * Note that __free_vmap_area may update free_vmap_cache
     * without updating cached_hole_size or cached_align.
     */
    if (!free_vmap_cache ||
            size < cached_hole_size ||
            vstart < cached_vstart ||
            align < cached_align) {
nocache:
        cached_hole_size = 0;
        free_vmap_cache = NULL;
    }
    /* record if we encounter less permissive parameters */
    cached_vstart = vstart;
    cached_align = align;

    /* find starting point for our search */
    if (free_vmap_cache) {/* 从上次分配的区域开始向后查找 */
        /* 得到上次分配的KVA描述符 */
        first = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
        /* 上次分配的结束地址向上对齐，得到本次可用的地址 */
        addr = ALIGN(first->va_end, align);
        if (addr < vstart)/* 可用地址小于我们的起始地址，缓存失效 */
            goto nocache;
        /**
         * 溢出，说明地址空间不足。
         * 初看似乎这里有点问题，因为从上次分配的结点开始向后查找可用空间，即使后面的可用空间不足，也不能表示真的没有可用空间了。
         * 因为前面已经分配的空间之间应该还有空洞。
         * 实际上内核这样处理是没有问题。请阅读时注意。
         */
        if (addr + size - 1 < addr)
            goto overflow;

    } else {
        /* 将虚拟地址向上对齐，对vmalloc来说，vstart表示可以使用的虚拟地址空间起始地址 */
        addr = ALIGN(vstart, align);
        if (addr + size - 1 < addr)/* 长度太长，造成整形溢出，退出。这类检查可以防止安全方面的问题 */
            goto overflow;

        /* 获取KVA(应该是指kernel vitural address)红黑树的根，从根开始遍历树 */
        n = vmap_area_root.rb_node;
        first = NULL;

        while (n) {/* 遍历红黑树 */
            struct vmap_area *tmp;
            /* 获取当前红黑树节点对应的vmap_area描述符 */
            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;
    }

    /* from the starting point, walk areas until a suitable hole is found */
    /* 运行到这里，说明我们要查找的区间位于红黑树的区域范围内，从当前节点开始，搜索合适大小的区间空洞 */
    while (addr + size > first->va_start && addr + size <= vend) {/* 要求的地址空间与当前节点重叠，说明需要向后移动节点，查找更高范围的地址空间 */
        if (addr + cached_hole_size < first->va_start)/* 根据当前地址到当前区间的起始地址之间有距离，计算空洞大小 */
            cached_hole_size = first->va_start - addr;
        /* 可用地址是当前区间结束地址向上对齐的地址 */
        addr = ALIGN(first->va_end, align);
        if (addr + size - 1 < addr)/* 整形溢出了，退出。说明空间不足。 */
            goto overflow;

        /* 取树中下一个节点进行比较 */
        n = rb_next(&first->rb_node);
        if (n)
            first = rb_entry(n, struct vmap_area, rb_node);
        else/* 如果不存在下一个节点，说明后面的地址空间完全可用，退出循环 */
            goto found;
    }

found:
    /* 可用地址加上分配长度超过了分配范围，说明地址空间不足了，退出 */
    if (addr + size > vend)
        goto overflow;

    /* 运行到这里，说明找到合适的地址区间，初始化KVA数据结构 */
    va->va_start = addr;
    va->va_end = addr + size;
    va->flags = 0;
    /* 将分配的vmap_area插入到红黑树中，代表这一段地址空间已经从KVA中分配出去了 */
    __insert_vmap_area(va);
    /* 记录下本次分配的空间，下次分配可从该节点开始搜索，提高搜索速度用 */
    free_vmap_cache = &va->rb_node;
    /* 释放KVA红黑树的自旋锁 */
    spin_unlock(&vmap_area_lock);

    BUG_ON(va->va_start & (align-1));
    BUG_ON(va->va_start < vstart);
    BUG_ON(va->va_end > vend);

    return va;

/* 运行到这里，说明地址空间不足 */
overflow:
    /* 首先释放自旋锁 */
    spin_unlock(&vmap_area_lock);
    if (!purged) {/* 如果我们还没有进行KVA地址空间清理(如果幸运的话，我们可以清理出一些可用空间) */
        /* 清理懒模式下没有及时释放的KVA空间，内核中经常用到懒模式，性能方面的原因 */
        purge_vmap_area_lazy();
        /* 设置标志，表示我们已经清理过KVA空间了 */
        purged = 1;
        /* 再试一次，如果还不行再返回错误 */
        goto retry;
    }
    /* 运行到这里，说明实在没有可用空间了，打印一下警告信息。注意这里用了printk_ratelimit，防止Dos攻击 */
    if (printk_ratelimit())
        printk(KERN_WARNING
            "vmap allocation for size %lu failed: "
            "use vmalloc= to increase size.\n", size);
    /* 没有分配到可用空间，释放临时分配的KVA描述符 */
    kfree(va);
    return ERR_PTR(-EBUSY);
}

虚拟地址空间分配后，vmalloc会分配物理页面，并将物理页面与虚拟地址进行映射，这是通过__vmalloc_area_node函数实现的：

 

/* 为vmalloc分配物理内存并进行虚实映射 */
static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
                 pgprot_t prot, int node, void *caller)
{
    const int order = 0;
    struct page **pages;
    unsigned int nr_pages, array_size, i;
    gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;

    /* 这里计算需要分配的页面数量，减去PAGE_SIZE是因为分配虚拟地址空间时多指定了一个空洞页面防止越界 */
    nr_pages = (area->size - PAGE_SIZE) >> PAGE_SHIFT;
    /* 分配的物理页面描述符要记录到一个临时数组中去，这里计算这个数据组的长度 */
    array_size = (nr_pages * sizeof(struct page *));

    /* 记录下该区域的物理页面数，释放时要使用 */
    area->nr_pages = nr_pages;
    /* Please note that the recursion is strictly bounded. */
    if (array_size > PAGE_SIZE) {/* 如果临时数组大于一个页面 */
        /* 通过vmalloc分配这个临时数组 */
        pages = __vmalloc_node(array_size, 1, nested_gfp|__GFP_HIGHMEM,
                PAGE_KERNEL, node, caller);
        /* 该标志表示临时数组是通过vmalloc分配的，释放时要同时调用vfree释放这个临时数组 */
        area->flags |= VM_VPAGES;
    } else {
        /* 否则通过kmalloc从slab中分配这个数组 */
        pages = kmalloc_node(array_size, nested_gfp, node);
    }
    /* 记录区域物理页面数组及调用者IP */
    area->pages = pages;
    area->caller = caller;
    if (!area->pages) {/* 分配临时数组失败，归还vm虚拟地址空间 */
        remove_vm_area(area->addr);
        kfree(area);
        return NULL;
    }

    /* 分配物理页面 */
    for (i = 0; i < area->nr_pages; i++) {
        struct page *page;
        gfp_t tmp_mask = gfp_mask | __GFP_NOWARN;

        /* 没有指定在哪个NUMA节点中分配页面 */
        if (node < 0)
            page = alloc_page(tmp_mask);/* 随便分配一个页面 */
        else
            page = alloc_pages_node(node, tmp_mask, order);/* 在指定NUMA节点中分配页面 */

        if (unlikely(!page)) {/* 分配页面失败 */
            /* Successfully allocated i pages, free them in __vunmap() */
            area->nr_pages = i;/* 记录下该区域中成功分配的页面数，跳转到fail释放已经分配的页面 */
            goto fail;
        }
        /* 记录下分配的页面描述符 */
        area->pages[i] = page;
    }

    /* 进行虚实地址映射 */
    if (map_vm_area(area, prot, &pages))
        goto fail;
    return area->addr;

fail:/* 分配物理内存失败，或者虚实映射失败 */
    warn_alloc_failed(gfp_mask, order, "vmalloc: allocation failure, "
             "allocated %ld of %ld bytes\n",
             (area->nr_pages*PAGE_SIZE), area->size);
    /* 释放已经分配的页面并解除虚实映射 */
    vfree(area->addr);
    return NULL;
}

为vmalloc建立虚实地址映射的过程是由map_vm_area完成，它的实现比较简单，就是在当前进程的页表项中建立数据结构，并刷新了tlb使pte页表项生效。在此不对它进行详细分析。

 

但是需要注意一个问题：假设我们在进程A的上下文通过vmalloc分配了一个虚拟地址，可以将其保存下来，在进程B上下文中使用。这里有一个问题，就是我们在vmalloc中建立虚实地址映射的时候，修改的pte页表项中指定的asid是进程A的，进程B访问这个虚拟地址必然会产生异常，那么此时会发生什么呢?具体的代码我们留到对缺页异常处理的分析中去。

 

--------------------------------------------------------------------------------------------

到此，我们将vmalloc已经分析完毕，与vmalloc相对应的释放函数是vfree：

/* 释放由vmalloc分配的虚拟内存 */
void vfree(const void *addr)
{
    /* 与vmalloc相同的道理，这两个函数都不能在中断中被调用 */
    BUG_ON(in_interrupt());

    /* 内存泄漏检测代码，略 */
    kmemleak_free(addr);

    /* 调用__vunmap释放内存，这里传标志1表示要释放相应的物理。如果释放由vmap映射的内存，则不必释放物理内存 */
    __vunmap(addr, 1);
}

__vunmap的实现代码也比较简单：

 

static void __vunmap(const void *addr, int deallocate_pages)
{
    struct vm_struct *area;

    /* 传入的参数不合法，退出 */
    if (!addr)
        return;

    /* 传入的地址没有页对齐，也不合法，因为vmalloc和vmap的映射地址都是页面对齐的 */
    if ((PAGE_SIZE-1) & (unsigned long)addr) {
        WARN(1, KERN_ERR "Trying to vfree() bad address (%p)\n", addr);
        return;
    }

    /* 从KVA和vmlist中移除虚拟地址块 */
    area = remove_vm_area(addr);
    /* 如果虚拟地址块没有位于KVA中，那么说明调用者传入了错误的地址参数，或者多次释放同一地址。 */
    if (unlikely(!area)) {
        WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
                addr);
        return;
    }

    /* 调试相关的代码 */
    debug_check_no_locks_freed(addr, area->size);
    debug_check_no_obj_freed(addr, area->size);

    /* 调用者是vfree而不是vunmap，因此需要释放相应的物理地址 */
    if (deallocate_pages) {
        int i;

        /* 遍历物页面 */
        for (i = 0; i < area->nr_pages; i++) {
            struct page *page = area->pages[i];

            BUG_ON(!page);
            /* 将页面归还给伙伴系统 */
            __free_page(page);
        }

        if (area->flags & VM_VPAGES)/* 存放页面的指针数组超过一页，是由vmalloc分配的 */
            vfree(area->pages);/* 通过vfree释放vmalloc分配的内存 */
        else
            kfree(area->pages);/* 否则通过kfree将指针数组释放给slab管理器 */
    }

    /* 释放vm_struct描述符 */
    kfree(area);
    return;
}

 

将虚拟地址空间归还给KVA的代码也比较简单，留给读者自己分析。
 

与vmalloc类似的函数有vmap和ioremap，这里不再继续分析。

 

下一篇文章准备讲述slab相关的代码，敬请关注。