注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

内核中一些不定长动态资源管理  

2013-12-07 18:49:23|  分类: Linux内核 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、动态资源
在任何一个动态运行的系统中,资源绝对是一个绕不开的概念。在内核中,最为重要和基础的就是一个动态内存的管理,由于内核虽然作为一个通用的基础软件而存在,但是它有很多特定的、频繁操作的功能和结构。例如对于文件结构的操作使用的file结构,对于进程管理使用的task_struct,对于进程内存区域管理使用的vm_area_struct,这些结构大小确定,也就是说它们是一些定长的特定结构,为了加快这些结构的申请和释放,内核会为这些基础的、高频使用的结构建立自己使用的专用cache结构。
和定长结构对应,还有一些资源,它的长度并不确定而是和不同场景中的不同应用有随机的联系。这一点在用户态的应用程序中通常样存在,例如最为常见的malloc申请内存大小。在内核中同样存在动态资源的管理,这里将会尝试讨论下内核中一些常见的动态资源管理场景,看下内核的实现方式及改进。
二、vmalloc分配内核动态页面
从Linux内核开始到现在,内核使用的逻辑地址都是页面的物理地址加上3G逻辑地址偏移量,这一点对于内核页面的管理具有非常方便的实现方式。随着PC的发展,系统中配备的物理内存数量越来越多,如果内核将所有的物理页面都映射到自己3G以上地址空间,在32位4G空间情况下,大于1G的物理内存无法在内核使用的1G中被直接映射。另一方面,很多场景下,内核也只是需要一些逻辑地址连续而不需要物理地址连续的页面。如果全部使用对等映射,在物理页面使用被碎片化的情况下,即使总量够用,也无法分配出一片特定大小空间的可用地址。
内核通过vmalloc/vfree来完成逻辑页面地址的申请和释放,此时分配地址空间在内核的3G+896M地址空间以上,这段地址空间通过vmalloc.c文件来实现。具体实现中,内核动态管理了这段逻辑地址空间,所有“被使用”(已经被分配出去)的内存区间段中均在vmlist引导的链表中对应一个结构,并且链表中存储的区间段按照起始地址从小到大的顺序排列,系统刚刚启动之后,这个链表内容为空,表示这段逻辑地址空间处于未被使用状态。这个接口分配的内存都是以页面单位为粒度,都是大手笔。
1、逻辑地址空间分配
vmalloc-->>__vmalloc--->>__vmalloc_node--->>get_vm_area_node--->>__get_vm_area_node
    /*
     * We always allocate a guard page.
     */
    size += PAGE_SIZE;
    //vmlist表示已经被分配出去的内存区域列表,初始值为空
    write_lock(&vmlist_lock);
    for (p = &vmlist; (tmp = *p) != NULL ;p = &tmp->next) {//链表中区间按照起始地址从小到大排列。
        if ((unsigned long)tmp->addr < addr) {//当前起始地址大于某个已分配区间起始地址
            if((unsigned long)tmp->addr + tmp->size >= addr)//并且当前起始地址在该已分配区间之上
                addr = ALIGN(tmp->size +
                         (unsigned long)tmp->addr, align);//越过整个区间,从该区间的结束地址开始继续查找。
            continue;
        }
        if ((size + addr) < addr)//地址溢出了,返回错误
            goto out;
        if (size + addr <= (unsigned long)tmp->addr)//[addr,addr+size]均在某区间备用区间之下
            goto found;
        addr = ALIGN(tmp->size + (unsigned long)tmp->addr, align);//走到这里,说明两个在用区间空隙不足以容纳size
        if (addr > end - size)
            goto out;
    }
2、空间释放
vfree--->>__vunmap--->>remove_vm_area--->>__remove_vm_area
    struct vm_struct **p, *tmp;

    for (p = &vmlist ; (tmp = *p) != NULL ;p = &tmp->next) {//tmp只是为了修改地址
         if (tmp->addr == addr)
             goto found;
    }
    return NULL;

found:
    unmap_vm_area(tmp);
    *p = tmp->next;//单向链表,将前像指针的位置指向自己的下一个,直接从链表中删除。
释放的代码相对比较简单,由于所有分配出去的空间都会被记录在vmlist中,所以在释放时根据起始地址找到对应的vm_struct结构,从链表中删除该结构即可。
3、映射的建立
上面说的都是内核中动态逻辑地址空间的申请,而没有为这些逻辑地址空间分配物理页面,真正物理页面的申请则是在上层函数的另外一个流程中处理。
vmalloc-->>__vmalloc--->>__vmalloc_node
    for (i = 0; i < area->nr_pages; i++) {
        if (node < 0)
            area->pages[i] = alloc_page(gfp_mask);//这里页面是逐个分配的,每次申请一个物理页面。
        else
            area->pages[i] = alloc_pages_node(node, gfp_mask, 0);
        if (unlikely(!area->pages[i])) {
            /* Successfully allocated i pages, free them in __vunmap() */
            area->nr_pages = i;
            goto fail;
        }
    }

    if (map_vm_area(area, prot, &pages))//将所有申请的物理页面和申请的动态逻辑空间建立起映射。
        goto fail;
三、小于页面大小空间申请释放kmalloc/kfree(slob)
和vmaloc相比,kmalloc和C库的malloc更加类似,它通常用在一些粒度更小结构的动态使用中,它们的大小通常小于或者远小于一个页面(当然kmalloc是支持大于页面的内存分配的)。在slob.c文件的开始,作为贴心的给出了很多注释,说明了该功能的大致实现方法:即按照传统的(经典的)K&R动态内存管理方式。在每个被分配出去的动态资源之前,加上一个隐含的header结构,从而在释放的时候知道这个被释放空间的长度(可以看到,kfree是没有长度参数的);对于可用的(free)地址空间,它们会被已分配空间分割为不连续的区间。
在资源分配时,系统又需要遍历所有这些可用的空间链表,所以这些空间的链表中就需要保存自己的长度和下一个空闲链表的地址(由于一个空间区间和下一个空闲区间之间可能有已分配区间,size结束的地方和下一个空间区间的起始地址通常不同)。对于可用空间的链表,它的每个header中包含的结构为下面的一个数据结构
struct slob_block {
    int units;
    struct slob_block *next;
};
其中的units表达了该空闲区间的大小,next指向下一个空闲区间的起始地址。
1、空间分配
static void *slob_alloc(size_t size, gfp_t gfp, int align)
{
    slob_t *prev, *cur, *aligned = 0;
    int delta = 0, units = SLOB_UNITS(size);
    unsigned long flags;

    spin_lock_irqsave(&slob_lock, flags);
    prev = slobfree;
    for (cur = prev->next; ; prev = cur, cur = cur->next) {
        if (align) {//对于一些有起始地址对齐要求的申请,此处进行对齐处理
            aligned = (slob_t *)ALIGN((unsigned long)cur, align);
            delta = aligned - cur;
        }
        if (cur->units >= units + delta) { /* room enough? */
            if (delta) { /* need to fragment head to align? */如果有对齐要求,对齐之前的空间被分割出去,成为一个新的blobk。例如我们要求一个地址是32对齐,该block起始地址为10,从起始地址到对齐处空出的22个字节被切出来作为一个新的空闲block。
                aligned->units = cur->units - delta;
                aligned->next = cur->next;
                cur->next = aligned;
                cur->units = delta;
                prev = cur;
                cur = aligned;
            }

            if (cur->units == units) /* exact fit? */如果刚好相等,则直接从空闲链表中摘除,单项链表删除操作。
                prev->next = cur->next; /* unlink */
            else { /* fragment */如果有剩余,多出的部分独立为新的block
                prev->next = cur + units;
                prev->next->units = cur->units - units;
                prev->next->next = cur->next;
                cur->units = units;
            }

            slobfree = prev;
            spin_unlock_irqrestore(&slob_lock, flags);
            return cur;
        }
        if (cur == slobfree) {//遍历整个空闲链表,没有找到可用空间,此时需要申请新的页面。
            spin_unlock_irqrestore(&slob_lock, flags);

            if (size == PAGE_SIZE) /* trying to shrink arena? */特殊情况,如果size为页面大小,可能是页面回收的特殊情况,不用真正申请,直接返回即可。
                return 0;

            cur = (slob_t *)__get_free_page(gfp);
            if (!cur)
                return 0;

            slob_free(cur, PAGE_SIZE);
            spin_lock_irqsave(&slob_lock, flags);
            cur = slobfree;
        }
    }
}
对于slob_block的units字段,它的大小包含了slob_block自己本身的大小。再具体的说,slob_alloc函数返回的地址空间中,地址开始的slob_block的大小是包含在传入参数size中的。这一点主要是由于所谓的bigblocks引起的,它们事实上并不需要有这样的一个header结构,它们被返回之后,被用来填充
struct bigblock {
    int order;
    void *pages;
    struct bigblock *next;
};
typedef struct bigblock bigblock_t;
类型的结构,并且它们的管理和vmlist中的管理类似。当释放一个页面时,通过遍历bigblocks链表,找到某个bigblock.pages和被释放地址相同的block即可。
2、空间释放 kfree
这里值得注意的是空闲空间的合并问题。当一个空间被释放之后,系统需要扫描看下前后是否有空间空间可以合并,以组合为一个更大的地址空间,这是避免多次分配之后碎片化的关键。
static void slob_free(void *block, int size)
{
    slob_t *cur, *b = (slob_t *)block;
    unsigned long flags;

    if (!block)
        return;

    if (size)
        b->units = SLOB_UNITS(size);

    /* Find reinsertion point */
    spin_lock_irqsave(&slob_lock, flags);
    for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next)//终止时b > cur && b < cur->next,即b在cur和cur->next之间
        if (cur >= cur->next && (b > cur || b < cur->next))//b在环形链表的最大值或者最小值处情况的特殊处理
            break;

    if (b + b->units == cur->next) {//新释放的block和后面空闲block逻辑空间连续,可以合并为一个新的block。
        b->units += cur->next->units;
        b->next = cur->next->next;
    } else
        b->next = cur->next;

    if (cur + cur->units == b) {//新释放block和前一个block地址空间连续,合并为一个新的block。
        cur->units += b->units;
        cur->next = b->next;
    } else
        cur->next = b;

    slobfree = cur;//slobfree为一个环形链表,同样是按照地址从高到低顺序排列。

    spin_unlock_irqrestore(&slob_lock, flags);
}
3、页面释放
在上面的kfree函数中,并没有判断是否会有一整个页面被空闲出来。在kmalloc中申请的页面会在什么时候什么地方释放呢?在slob.c的最后,可以看到有一个定时器:
static void slob_timer_cbk(void)
{
    void *p = slob_alloc(PAGE_SIZE, 0, PAGE_SIZE-1);

    if (p)
        free_page((unsigned long)p);

    mod_timer(&slob_timer, jiffies + HZ);
}
它调用slob_alloc申请一个大小为PAGE_SIZE的页面。此时如果也个页面被整个空闲出来,此时就可以找到这个页面并返回,定时器slob_time_cbk中在得到这个页面之后会把该页面释放回去。这样是一个比较好的防治抖动的方法,每隔一段时间从中踢出一个页面,即保持了一定量的空闲页面,也不会有太多空闲。
4、一些细节
①页面大小空间释放
在slob_alloc一个页面大小的空间,如果其中没有这样的空闲空间,此时函数不会真正分配物理页面,而是直接返回,这一点在函数中有注释
if (cur == slobfree) {
            spin_unlock_irqrestore(&slob_lock, flags);

            if (size == PAGE_SIZE) /* trying to shrink arena? */
                return 0;
②页面大小申请
__kmalloc
    if (size < PAGE_SIZE - SLOB_UNIT) {
        m = slob_alloc(size + SLOB_UNIT, gfp, 0);
        return m ? (void *)(m + 1) : 0;
    }
……
if (bb->pages) {
        spin_lock_irqsave(&block_lock, flags);
        bb->next = bigblocks;
        bigblocks = bb;
        spin_unlock_irqrestore(&block_lock, flags);
        return bb->pages;
    }
四、更高版本对kmalloc实现
观察上面两个版本的实现,它们的特点和缺点就是在申请/释放的时候需要遍历某个链表结构,从中找到一个位置,这遍历从前到后,对于靠后的页面来说,效率较低。在较高的内核版本实现中进行了改进,以避免这种查找的低效问题。
1、对struct page的重用
struct slob_page {
    union {
        struct {
            unsigned long flags;    /* mandatory */
            atomic_t _count;    /* mandatory */
            slobidx_t units;    /* free units left in page */整个page中所有freelist中units总和。
            unsigned long pad[2];
            slob_t *free;        /* first free slob_t in page */页面内空闲slob链表,和早期版本中的slob_free对应
            struct list_head list;    /* linked list of free pages */所有页面链接在256 1204及更大三个链表中,不同page通过该list连接。
        };
        struct page page;
    };
};
即使在最早期的内容中,每个物理页面都对应一个struct page结构,所有的page结构组成一个数组,通过特定的逻辑地址可以直接映射到它对应的struct page结构,反之亦然。如果一个页面被分配给slob作为动态内存管理,此时就可以对该页面对应的page结构进行一些扩展定义,复用/转义其中的字段来管理该页面中动态内存的布局情况。它的优点在于将内存的管理局部化在了一个更小的页面范围内,而不用在整个链表中遍历。
这里的slob_page使用的就是页面page结构的内存空间,只是在作为slob_page时,slob对其中的字段做了自己的定义。作者注释中说了,定义一个新的结构就是为了避免在page中再次添加新的union类型,可以在mm_types.h中看到,page的定义已经相当凌乱。
2、一些特殊的结构
/*
 * slob_block has a field 'units', which indicates size of block if +ve,
 * or offset of next block if -ve (in SLOB_UNITs)
.这里作者的+ve和-ve没有找到确切的含义,但是可以认为+ve应该是paositVE,-ve应该是NegatiVE的缩写,只是为了简单,通过正负号表示数值为整数或者负数
 *
 * Free blocks of size 1 unit simply contain the offset of the next block.
 * Those with larger size contain their size in the first SLOB_UNIT of
 * memory, and the offset of the next free block in the second SLOB_UNIT.
 */
#if PAGE_SIZE <= (32767 * 2)
typedef s16 slobidx_t;
#else
typedef s32 slobidx_t;
#endif

struct slob_block {
    slobidx_t units;
};
/*
 * Return the next free slob block pointer after this one.
 */
static slob_t *slob_next(slob_t *s)
{
    slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
    slobidx_t next;

    if (s[0].units < 0)
        next = -s[0].units;
    else
        next = s[1].units;
    return base+next;
}
五、文件夹目录项
一个文件夹的目录项作为一个数组结构存放在文件夹结构使用的页面中,常见的ext2文件系统目录项结构为
/*
 * The new version of the directory entry.  Since EXT2 structures are
 * stored in intel byte order, and the name_len field could never be
 * bigger than 255 chars, it's safe to reclaim the extra byte for the
 * file_type field.
 */
struct ext2_dir_entry_2 {
    __le32    inode;            /* Inode number */
    __le16    rec_len;        /* Directory entry length */
    __u8    name_len;        /* Name length */
    __u8    file_type;
    char    name[EXT2_NAME_LEN];    /* File name */
};
目录项的创建和删除其实和物理内存的删除和创建相同,也会有碎片的出现。对于ext2的文件目录项,它有两个看似重复的结构,name_len和rec_len,当文件夹目录项频繁删除创建之后,一个文件夹下目录项的rec_len会大于name_len。假设说一个目录项被删除,该目录项的前一项会吞并(记录)该目录项的空间,实现的方式就是将删除目录项的大小记录在自己的rec_len中,注意:此时name_len没有变化。
1、目录项的添加
int ext2_add_link (struct dentry *dentry, struct inode *inode)
            if (ext2_match (namelen, name, de))
                goto out_unlock;
            name_len = EXT2_DIR_REC_LEN(de->name_len);
            rec_len = ext2_rec_len_from_disk(de->rec_len);
            if (!de->inode && rec_len >= reclen) inode为零,表示该目录项已经被删除。
                goto got_it;
            if (rec_len >= name_len + reclen)//该目录项中剩余长度足够容纳新的dentry
                goto got_it;
            de = (ext2_dirent *) ((char *) de + rec_len);//每次增加以record len为单位增加。
2、目录项的删除
ext2_delete_entry
while ((char*)de < (char*)dir) {
        if (de->rec_len == 0) {
            ext2_error(inode->i_sb, __func__,
                "zero-length directory entry");
            err = -EIO;
            goto out;
        }
        pde = de;
        de = ext2_next_entry(de);
    }
    if (pde)
        from = (char*)pde - (char*)page_address(page);
    pos = page_offset(page) + from;
    lock_page(page);
    err = __ext2_write_begin(NULL, page->mapping, pos, to - from, 0,
                            &page, NULL);
    BUG_ON(err);
    if (pde)
        pde->rec_len = ext2_rec_len_to_disk(to - from);
    dir->inode = 0; inode清零。
    err = ext2_commit_chunk(page, pos, to - from);
    inode->i_ctime = inode->i_mtime = CURRENT_TIME_SEC;
    EXT2_I(inode)->i_flags &= ~EXT2_BTREE_FL;
    mark_inode_dirty(inode);
和动态内存管理不同,目录项并没有进行后向合并,但是dentry中有一个确定结构header,并且inode值表示该结构是否处于被删除状态。
3、一个直观的例子
tsecer:/home/tsecer #mkdir direntrytest
tsecer:/home/tsecer #cd direntrytest
tsecer:/home/tsecer/direntrytest #touch first
tsecer:/home/tsecer/direntrytest #touch alongnametocontainolotoffbullshit
tsecer:/home/tsecer/direntrytest #touch third
tsecer:/home/tsecer/direntrytest #/bin/ls -f
..  .  first  alongnametocontainolotoffbullshit  third
tsecer:/home/tsecer/direntrytest #rm alongnametocontainolotoffbullshit
tsecer:/home/tsecer/direntrytest #touch a
tsecer:/home/tsecer/direntrytest #touch b
tsecer:/home/tsecer/direntrytest #/bin/ls -f
..  .  first  a  b  third
tsecer:/home/tsecer/direntrytest #
可以看到,创建的a和b文件由于文件名比较短,所以被现实在中间。
  评论这张
 
阅读(740)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017