Linux内存管理:SLAB分配器

May 15th, 2015 by JasonLe's Tech 400 views

之前学习过linux物理内存管理中的伙伴系统,他的分配单位是以page为单位分配。对于远远小于page的内存分配请求,比如几个字节~几百个字节,如果分配一个页框,那就是极大地浪费,会产生内部碎片,这时SLAB分配器就派上用场了。

与slab有相同地位的有slob(simple linked list of block)与slub两种备用类型的内存分配器,slob主要是使用内存块链表展开,使用最先适配算法,主要是使用在嵌入式系统,对于内存分配紧张的的系统。对于拥有大量物理内存的并行系统,slab会占用非常大的内存来存储元数据,而slub会将page打包成组,所以这里主要使用slub作为大型系统的内存分配方案。

slab、slob、slub 三者都拥有相同的内核分配函数接口。三者的选择主要在编译时就要选择确定下来。我们以slab作为下面说明的,slab会将某种特定类型的数据集中分配在一起,并且将这些对象放到高速缓存中,方便存取。

举例:进程描述符,当新进程创建时,内核直接从slab中获取一个初始化好的对象,当释放后,这个page不会放到伙伴系统,而是放入slab中。

slab分配器在最上层拥有节点是struct kmem_cache,他是slab分配器的核心结构体

struct kmem_cache {
    struct array_cache __percpu *cpu_cache;
/* 1) Cache tunables. Protected by slab_mutex */
    unsigned int batchcount;
    unsigned int limit;
    unsigned int shared;
    unsigned int size;
    struct reciprocal_value reciprocal_buffer_size;
/* 2) touched by every alloc & free from the backend */
    unsigned int flags;     /* constant flags */
    unsigned int num;       /* # of objs per slab */
/* 3) cache_grow/shrink */       

    /* order of pgs per slab (2^n) */
    unsigned int gfporder;
    /* force GFP flags, e.g. GFP_DMA */  

    gfp_t allocflags;
    size_t colour;          /* cache colouring range */
    unsigned int colour_off;    /* colour offset */
    struct kmem_cache *freelist_cache;
    unsigned int freelist_size;                                                                   

    /* constructor func */
    void (*ctor)(void *obj);
/* 4) cache creation/removal */
    const char *name;
    struct list_head list;
    int refcount;
    int object_size;
    int align;

/* 5) statistics */
#ifdef CONFIG_DEBUG_SLAB
.....
#endif /* CONFIG_DEBUG_SLAB */
#ifdef CONFIG_MEMCG_KMEM
    struct memcg_cache_params *memcg_params;
#endif

    struct kmem_cache_node *node[MAX_NUMNODES];
};

这里至于管理slab的节点的数据结构就是struct kmem_cache_node,每个kmem_cache结构中并不包含对具体slab的描述,而是通过kmem_cache_node结构组织各个slab。该结构的定义如下:

struct kmem_cache_node {
    spinlock_t list_lock;

#ifdef CONFIG_SLAB
    struct list_head slabs_partial; /* partial list first, better asm code */
    struct list_head slabs_full;
    struct list_head slabs_free;
    unsigned long free_objects;
    unsigned int free_limit;
    unsigned int colour_next;   /* Per-node cache coloring */
    struct array_cache *shared; /* shared per node */
    struct alien_cache **alien; /* on other nodes */
    unsigned long next_reap;    /* updated without locking */
    int free_touched;       /* updated without locking */
#endif
...
};

可以看到,该结构将当前缓存中的所有slab分为三个部分:空闲对象的slab链表slabs_free,非空闲对象的slab链表slabs_full以及部分空闲对象的slab链表slabs_partial。至于在链上的结构体,在kernel 3.11前后发生了重大变化,在3.11前的版本。使用struct slab来管理slab资源。

struct slab {
    union {
        struct {
            struct list_head list;
            unsigned long colouroff;
            void *s_mem;        /* including colour offset */
            unsigned int inuse; /* num of objs active in slab */
            kmem_bufctl_t free;
            unsigned short nodeid;
        };
        struct slab_rcu __slab_cover_slab_rcu;
    };
}

在3.11之后Joonsoo Kim 提出方案认为大量的slab对象严重占用内存,所以之后struct slab融合进struct page结构体。显著降低了元数据的内存使用量,具体查看 。他并对修改后的struct page 进行了介绍 。

也就是slabs_partial 链接的是一个个struct page结构体。根据这几个结构体的关系,我们可以总结出slab的结构

slab

在kernel 3.11 以前,结构图是:

1339687849_2988

最后还要说明struct array_cache 也是一个重要的结构体,cpu首先分配一项专有object是通过struct array_cache来进行分配,这个结构体是每个cpu都会存在一个。

struct array_cache {
	unsigned int avail;/*本地高速缓存中可用的空闲对象数*/
	unsigned int limit;/*空闲对象的上限*/
	unsigned int batchcount;/*一次转入和转出的对象数量*/
	unsigned int touched;   /*标识本地CPU最近是否被使用*/
	spinlock_t lock;
	void *entry[];	/*这是一个伪数组,便于对后面用于跟踪空闲对象的指针数组的访问
			 * Must have this definition in here for the proper
			 * alignment of array_cache. Also simplifies accessing
			 * the entries.
			 */
};

在每个array_cache的末端都用一个指针数组记录了slab中的空闲对象,分配对象时,采用LIFO方式,也就是将该数组中的最后一个索引对应的对象分配出去,以保证该对象还驻留在高速缓存中的可能性。实际上,每次分配内存都是直接与本地CPU高速缓存进行交互,只有当其空闲内存不足时,才会从kmem_list中的slab中引入一部分对象到本地高速缓存中,而kmem_list中的空闲对象也不足了,那么就要从伙伴系统中引入新的页来建立新的slab了,这一点也和伙伴系统的每CPU页框高速缓存很类似。

slab高速缓存分为两类,普通高速缓存和专用高速缓存。

  • 普通高速缓存并不针对内核中特定的对象,它首先会为kmem_cache结构本身提供高速缓存,这类缓存保存在cache_cache变量中,该变量即代表的是cache_chain链表中的第一个元素;
  • 专用高速缓存为内核提供了一种通用高速缓存。专用高速缓存是根据内核所需,通过指定具体的对象而创建。

最后使用这种slab分配非常简单

1.创建

struct kmem_cache *cachep = NULL;
cachep = kmem_cache_create("cache_name", sizeof(struct yourstruct), 0, SLAB_HWCACHE_ALIGN, NULL, NULL);

2.分配一个struct yourstruct的结构体空间时

调用kmem_cache_alloc函数,就可以获得一个足够使用的空间的指针(SLAB_HWCACHE_ALIGN,这个标志会让分配的空间对于硬件来说是对齐的,而不一定恰好等于sizeof(struct yourstruct)的结果)。范例代码如下:

struct yourstruct *bodyp = NULL;
bodyp = (struct yourstruct *) kmem_cache_alloc(cachep, GFP_ATOMIC & ~__GFP_DMA);

3.销毁

kmem_cache_free(cachep, bodyp);

 

参考:

http://lwn.net/Articles/570504/
https://lwn.net/Articles/565097/
https://lwn.net/Articles/335768/
http://blog.csdn.net/vanbreaker/article/details/7664296

由lxc-checkpoint想到的 …

May 12th, 2015 by JasonLe's Tech 378 views

在 LXC 1.1版本以后,lxc整合了criu的功能,使得可以checkpoint一个正在运行的容器。但是有时候我们会出现lxc.tty must be 0的文字,这个就意味着我们必须在lxc 的config中加入特定的选项

cat | sudo tee -a /var/lib/lxc/u1/config << EOF
# hax for criu
lxc.console = none
lxc.tty = 0
lxc.cgroup.devices.deny = c 5:1 rwm
EOF

但是我发现了一个问题:到底什么是tty,他是由什么管理的?

我们都知道在unix下有非常多的终端:bash、zsh、sh、ssh等,这些终端程序就是我们输入命令的窗口,至于配置用户的终端,当然是在/etc/passwd下面。

但是是哪个程序调用了/bin/bash呢?使用strace跟踪这个/bin/login(strace -f -o /tmp/strace.log /bin/login),可以发现里面存在execve系统调用,这个调用执行了 /bin/login程序。而login又是谁调用的呢?经过查看是getty。getty是在自己的主进程里头直接执行了/bin/login,这样/bin/login将把getty的进程空间替换掉。

而init需要读取/etc/inittab来做,inittab,目前不再被systemd使用,这里就有/etc/rc.d/一系列脚本完成。
根据系统启动原理,我们可以发现调用过程:

init –> init –> /sbin/getty –> /bin/login –> /bin/login –> /bin/bash

这里的execve调用以后,后者将直接替换前者,我们要知道一点:因为终端程序之间有父子关系的存在,当子进程exit之后,父进程要进行处理,否则就是zombie进程。因此当我们键入exit退出/bin/bash以后,也就相当于/sbin/getty都已经结束了, 因此最前面的init程序判断/sbin/getty退出了,又会创建一个子进程把/sbin/getty启动,进而又启动了/bin/login,又看 到了那个”XXX login:”

一般情况下,系统内置程序会比自己编写的更加优先被执行,按照系统内置规则,一般首先是程序别名,然后是shell function,之后是系统内置函数(builtin ),最后才是自己编写的函数(program )!

总的来说:先    alias –> shell function –> builtin –> program   后 

 

参考:

[1] man boot-scripts Linux启动过程
[2] man bootparam  Linux内核启动参数
[3] man 5 passwd
[4] man shadow

DFS通用解法

May 8th, 2015 by JasonLe's Tech 425 views

最近在刷一些算法题,发现DFS在单链表,二叉树,图,集合的解题比较多,具有一定的通用规律,现在讲通用方法记录下。拿二叉树举例,比如我们需要从根走到叶子节点才能得到一个解,这种类型非常适合是用DFS,再以二维数组举例,我们可以将二维数组当成一个图,进行搜索,在搜索的同事满足一定的匹配等。

一般情况下Wide-FS只要求有一个解,而且需要将整个中间状态存储到内存中,而DFS只存储一条路径,非常时候解决一些问题。

在DFS中我们需要一个收敛条件,也就是合法解。这时我们就需要把这个中间状态保存到最后的结果中。为了加快深搜,我们可以剪枝,常用方式使用状态数组表示,提前return,可以大大加快递归速度。

通用dfs模板:

/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[out] path 当前路径,也是中间结果,可以是一维数组
* @param[out] result 存放最终结果,二维数组
* @param[inout] cur or gap 标记当前位置或距离目标的距离,或者可以
* 是start end等标记
* @return 路径长度,如果是求路径本身,则不需要返回长度
* 可以返回bool等,依照题目要求来实现。
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

这里我举一个例子:列举所有set可能的子集合,比如S=[1,2,3],那么结果是[[3],[2],[1],[1,2,3],[1,3],[2,3],[1,2],[]]
解决这个问题,需要首先按照上面的这种模板构建,首先是这个dfs的input 也就是这个S,中间路径path与S类型相同。结果应该是一个二维数组,也就是vector< vector > result,最后我们需要一个step作为收敛条件。

void dfs(const vector<int> &S, vector<int> &path, vector<vector<int> > &result,int step) {
     if (step == S.size()) {//到达S.size()收敛
           result.push_back(path);
           return;
     }
     //这里没有剪枝
     // 不选S[step]
     subsets(S, path, step + 1, result);
     // 选S[step]
     path.push_back(S[step]);
     subsets(S, path, step + 1, result);
     path.pop_back();
}
 void dfs(vector<int>& nums,vector<int> &path,vector<vector<int>> &result,
                     vector<int>::iterator start){
 
     result.push_back(path);
 
     for(auto i = start;i<nums.end();i++)
     {
          path.push_back(*i);
          dfs(nums,path,result,i+1);
          path.pop_back(); 
     }
 }

深度搜索比较难以理解,层层递归会让我迷失,不过进行断点认真跟踪是可行的。最后跟踪断点结果是:

[]
3
2
2,3
1,
1,3
1,2
1,2,3

还有很多场景,比如二维数组寻路,都会用到上下左右的移动,还要使用flag来标示,具体查看
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/word-search/

物理内存管理:伙伴系统释放页框

April 24th, 2015 by JasonLe's Tech 373 views

相对与页框慢速分配快速分配而言。页框释放函数非常简单,主要的函数就是__free_pages()和__free_page()。很明显,类似于之前page分配的上层函数,也是层层wrapper。这里__free_page()是__free_pages()的包装。

#define __free_page(page) __free_pages((page), 0)

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

通过代码我们发现当要释放的页order==0,直接使用per-cpu缓存释放,大于0使用__free_pages_ok(page, order)释放。

这里kernel使用free_hot_cold_page() 方式释放order为0的页,这个函数只将不可移动页,可回收页和可移动页放入每个CPU页框高速缓存中,如果迁移类型不再这个范围,那么这个页要回收到伙伴系统中!这里的策略是:热页加入表头,冷页加入表尾。这个部分不在本文中叙述,查看代码便知。

来看__free_pages_ok()函数,这个函数也是一个wrapper函数,主要用来检查参数是否正确,做一些释放page前的准备工作。当一切就绪后就会调用free_one_page()函数。大致调用关系是:

static void __free_pages_ok(struct page *page, unsigned int order)
{
....
    free_one_page(page_zone(page), page, pfn, order, migratetype);
....
}
static void free_one_page(struct zone *zone,
                struct page *page, unsigned long pfn,
                unsigned int order,
                int migratetype)
{
    unsigned long nr_scanned;
    spin_lock(&zone->lock);
...
    __free_one_page(page, pfn, zone, order, migratetype);
    spin_unlock(&zone->lock);
}

在调用__free_one_page()之前,kernel换回更新当前zone下面page状态:更新当前内存管理区的空闲页面数,也就是更新zone下面的vm_stat数组,这个数组用于统计当前内存信息。

在核心函数__free_one_page()中,这个函数主要完成page的回收,完成页的合并,首先要获取要释放page的page index

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;
    int max_order = MAX_ORDER;

...
    page_idx = pfn & ((1 << max_order) - 1);
...
    while (order < max_order - 1) {
        buddy_idx = __find_buddy_index(page_idx, order);
        buddy = page + (buddy_idx - page_idx);
        if (!page_is_buddy(page, buddy, order))
            break;
        if (page_is_guard(buddy)) {
            clear_page_guard_flag(buddy);
            set_page_private(buddy, 0);
            if (!is_migrate_isolate(migratetype)) {
                __mod_zone_freepage_state(zone, 1 << order,
                              migratetype);
            }
        } else {
            list_del(&buddy->lru);
            zone->free_area[order].nr_free--;
            rmv_page_order(buddy);
        }
        combined_idx = buddy_idx & page_idx;
        page = page + (combined_idx - page_idx);
        page_idx = combined_idx;
        order++;
    }
    set_page_order(page, order);

    if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
        struct page *higher_page, *higher_buddy;
        combined_idx = buddy_idx &amp; page_idx;
        higher_page = page + (combined_idx - page_idx);
        buddy_idx = __find_buddy_index(combined_idx, order + 1);
        higher_buddy = higher_page + (buddy_idx - combined_idx);
        if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
            list_add_tail(&page->lru,
                &zone->free_area[order].free_list[migratetype]);
            goto out;
        }
    list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
    zone->free_area[order].nr_free++;
}

然遍历当前order到max-order所有阶,使用__page_find_buddy()找到当前page_idx的伙伴buddy_idx,然后根据idx偏移量,找到目标buddy。后将这个buddy从list删除,更新nr_free数量。删除buddy标记。最后使用 buddy_idx & page_idx 获取合并后的combined_idx。由于page永远都指向要释放页框块的首页框描述符,所以讲这个combined_idx赋值给page_idx。最后将order+1,然后通过set_page_order()设置这个page的各种信息。

在最新的源码里面,还会判断是否这个page是否是最大的页,如果找到则继续合并,并将合并后page放到list tail中,最后将当前order下的nr_order++。

最后我们来看__find_buddy_index()函数

static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{
      return page_idx ^ (1 << order);
}

这个函数用来查找buddy的index,这个函数非常简单。

综上所述,所以整个页框分配的核心就是那个while循环,我们可以把页框释放当成页框分裂的逆过程,也就是回收order大于0的页:
举例:

page_idx = 10 -> buddy_idx = 11 -> combined_idx = 10
page_idx = 10 -> buddy_idx = 8 -> combined_idx = 8
page_idx = 8 -> buddy_idx = 12 -> combined_idx = 8
page_idx = 8 -> buddy_idx = 0 -> combined_idx = 0
->无法继续进行->结束

这就是那些位操作的实际含义,page_idx以二倍速率寻找buddy page然后合并,至此伙伴系统回收页框完毕。

 

参考:

http://blog.csdn.net/vanbreaker/article/details/7624628

内存条物理结构分析

April 21st, 2015 by JasonLe's Tech 493 views

Update 2015-07-04

我们经常接触物理内存条,如下有一根DDR的内存条,我们可以看到这个内存条上面有8个黑色的内存颗粒,在高端服务器上面通常会带有ECC校验,所以会存在9个黑色的内存颗粒,其中一个的内存颗粒是专门做ECC校验的。

20150421160137

从概念的层次结构上面分为:Channel > DIMM > Rank > Chip > Bank > Row/Column

我们可以把DIMM作为一个内存条实体,我们知道一个内存条会有两个面,高端的内存条,两个面都有内存颗粒。所以我们把每个面叫做一个Rank,也就是说一个内存条会存在Rank0和Rank1。

拿rank0举例,上面有8个黑色颗粒,我们把每个黑色颗粒叫做chip。再向微观走,就是一个chip里面会有8个bank。每个bank就是数据存储的实体,这些bank就相当于一个二维矩阵,只要声明了column和row就可以从每个bank中取出8bit的数据。

我们之前会经常说双通道,说白了就是一个DIMM就是一个通道,两个DIMM组成双通道,分别由两个Memory Controller控制。

20150421162420

我们可以看到两个DIMM0 DIMM0组成双通道,两个DIMM1 DIMM1组成双通道。

下面先来解释memory controllers如何从rank中取数据,上面说的都是物理结构,下面说内存的逻辑结构。因为每个rank下面会有很多chip,而每个chip又包括bank0、bank1、bank2等,在memory controllers看来每次发数据,都会同时发送给所有chip下的某个bank,并声明row和col。

以从bank0为例:

20150421162433

每个chip的bank0 的同一地点(row=i col=j)都会被读出8bit,那么8个chip就会同时读出64bit,然后由memory controllers传送给cpu,也就是8byte。

在memory controllers看来,每个bank存在于每个chip中,如上图所示,可以把每个chip里面的小bank连成一行,b看作成一个大的bank。然后从大的bank中读取数据。

每个bank有一个row bufffer(这个row buffer存在于bank中,而不是在memory controller,row buffer 是以bank和row作为参数的,而读到memory controller时,又加入了col参数,也就是row buffer数据量是整整一行数据,读到memory controllers中仅仅是很小的一部分数据,而row buffer是整个程序局部性的关键!),作为一个bank page,所有bank共享地址、数据总线,但是每个channel有他们自己的地址、数据总线。正因为有buffer,所以每次bank都会预读64bit的数据。

上面看到的是分解的操作,事实上,为了加快memory的读写,体系结构中引入了流水线,也就意味着memory controllers可以同时读64byte,也就是8次这样的操作。写入到buffer中,这就是局部性原理。如果我们程序猿不尊重这个规则,也就迫使bank的buffer每次取值都必须清空当前的缓冲区,重新读数据,降低数据的访问速度。

 

 

设计弊端:

那么内存在多核平台的表现就取决于数据位于哪个bank之中,在给定的时间kernel如何访问多核之间共享的bank,最好的一种情况是每个core都只访问自己的bank,互不干扰。最坏的一种情况就是所有的core都访问同一个bank,只能同时有一个core访问该bank,其他core必须等待这个bank的,这样的话造成memory access的delay,考虑一种情况:如果多个进程在多个bank中都有自己的数据,controllers不得不每次清空row buffer,造成性能损失。而且使得时间分析变得不确定!

由于memory controllers内侧对于bank的操作对外透明,row col bank这些指令信息属于内存地址(memory controllers将physics address翻译成内存地址)。研究memory controllers向bank发送读信息的编码格式,我们会发现row与col位之间会有bank 位的介入,也就意味着对于bank的访问会分割到几个bank同时进行。

如果我们想把进程在内存中的数据限制在某个bank中,就要测试这种内存地址格式,目前可以palloc自带的工具进行测试,测试bank位到底存在于内存地址的哪几位。

目前系统都是多核,而且kernel将memory视为一个整体。不会区分分配的资源来自于哪个bank,所以数据分配的确定位置是不可预期的。而且目前memory controllers被配置为分割的bank来提高bank访问的并行度(一个程序分配的内存在每个bank中都存在)。但是这个导致一个问题:肯定有好几个进程数据存在于当前bank。当bank中出现multiple error时,我们无法准确定位这个错误来自于哪个进程!

 

[1] http://en.wikipedia.org/wiki/Memory_bank

[2] http://arxiv.org/pdf/1407.7448.pdf