array_cache在slab管理中有什么用？

joyhappy

最近在看slab内存管理，看到在kem_cache_s结构中的如下成员：
struct kmem_cache_s {
/* 1) per-cpu data, touched during every alloc/free */
        struct array_cache      *array[NR_CPUS];
        unsigned int            batchcount;
        unsigned int            limit;

有些不解：

1。array_cache(abbr. ac)分配是好像是从通用cache中取对象，那么通用cache结构中也有ac结构，那个ac结构由谁分配呢？（chicken－egg problem）
   专用cache有全局cache_cache，通用有malloc_cache，是不是这个malloc_cache链中的cache中的ac没什么用？
   是不是ac只用来缓存专用cache中的对象（也就是内核中常用的struct结构等）？

2。 per cpu缓存的目的是为了减少spin_lock操作。可是，ac结构的下一地址开始存放指向对象的指针数组。是不是每个CPU只能访问自己ac中指向的对象？也就是说ac中只是缓存了指向对象的指针，真正访问对象还是需要访问对象所在的slab，需要spinlock。这样一来，又有什么意义呢？
是不是per cpu 缓存并没有真正缓存对象数据？

3。怎么知道一个对象是否被当前cpu缓存了？这和ac 有什么关系。

那位大虾指教一二

[ 本帖最后由 joyhappy 于 2006-1-19 15:12 编辑 ]

joyhappy

在ULK3中有一些解释，但好像细节还是没有说得更清晰。ULVMM中是2.4内核的。

xiaozhaoz

内存管理没看几天，欢迎指正错误。
第一个问题：
slab子系统的初始化, kmem_cache_init()的过程，这个初始化必须在其它CPU起来之前完成，也就是说，当前系统只有一个CPU在运行：
1. 初始化kmem_cache链表和锁
2. 完全手动设置cache_cache和cache_cache中的head array
3. 完全手动分配第一个通用kmem_cache size = 32, 半手动分配后续通用kmem_cache
4. 用3中分配的通用slab cache 替换2中的head array
5. 调整所有的ac，使他们成为一个ac head + array的内存块
6. 挂载CPU通告函数，后续的CPU UP后，会调用这个回调函数

每个kmem_cache 中的ac都是从通用kmem_cache中获取的，这涉及到你说的chicken－egg 问题，他们是按照上面的步骤解决的，
第二步: 在还没有cache_cache的情况下，不能用kmem_cache_create创建kmem_cache这时第一个chicken_egg问题。 所以完全手动设置cache_cache的kmem_cache，cache_cache只能是一个静态分配的内存，所以只需要设置就可以。 而他的ac是通过静态的initarray_cache获取的，这个cache不能存放cache
第三步：因为ac是通过通用kmem_cache获得的，这是第二个chicken_egg问题，这个问题通用记录状态来解决，用g_cpucache_up来表明当前slab 子系统的状态，当通用kmem_cache的第一个（size ＝32)的cache初始化之前，这个g_cpucache_up ＝ NONE，跟踪kmem_cache_init()以下代码：
        /* 循环初始化所有通用cache */
        while (sizes->cs_size != ULONG_MAX) {
                /* 第一个kmem_cache创建的时候，g_cpucache_up ＝ none */
                sizes->cs_cachep = kmem_cache_create(names->name,
                        sizes->cs_size, ARCH_KMALLOC_MINALIGN,
                        (ARCH_KMALLOC_FLAGS | SLAB_PANIC), NULL, NULL);

                /* Inc off-slab bufctl limit until the ceiling is hit. */
                if (!(OFF_SLAB(sizes->cs_cachep))) {
                        offslab_limit = sizes->cs_size-sizeof(struct slab);
                        offslab_limit /= sizeof(kmem_bufctl_t);
                }
                /* 初始化dma通用size chache */
                sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
                        sizes->cs_size, ARCH_KMALLOC_MINALIGN,
                        (ARCH_KMALLOC_FLAGS | SLAB_CACHE_DMA | SLAB_PANIC),
                        NULL, NULL);

                sizes++;
                names++;
        }

在kmem_cache_create()中，
        /* 当slab系统初始化完成后，用标准方法初始化cache，后面详细分析初始化过程 */
        if (g_cpucache_up == FULL) {
                enable_cpucache(cachep);
        } else {
                /* 当状态=none的时候，手动分配 */
                if (g_cpucache_up == NONE) {
                        /* Note: the first kmem_cache_create must create
                         * the cache that's used by kmalloc(24), otherwise
                         * the creation of further caches will BUG().
                         */
                        cachep->array[cpu] = &initarray_generic.cache;
                        g_cpucache_up = PARTIAL;
                } else {
                /* 除size=32以外，其它通用cache的初始化执行这个,kmalloc 将会从size=32的kmem_cache_t中获得内存 */
                        cachep->array[cpu] = kmalloc(sizeof(struct arraycache_init),GFP_KERNEL);
                }
                /* 当slab系统没有完全初始化完成时，手动设置ac中的内容，这些内容会在后续的第5步中覆盖 */
                BUG_ON(!ac_data(cachep, cpu));
                ac_data(cachep, cpu)->avail = 0;
                ac_data(cachep, cpu)->limit = BOOT_CPUCACHE_ENTRIES;
                ac_data(cachep, cpu)->batchcount = 1;
                ac_data(cachep, cpu)->touched = 0;
                cachep->batchcount = 1;
                cachep->limit = BOOT_CPUCACHE_ENTRIES;
                cachep->free_limit = (1+num_online_cpus())*cachep->batchcount
                                        + cachep->num;
        }


第5步，用标准方法替换所有初始化时分配的kmem_cache 中的ac
                kmem_cache_t *cachep;
                down(&cache_chain_sem);
                list_for_each_entry(cachep, &cache_chain, next)
                /* 用标准方法分配所有kmem_cache 中的ac */
                        enable_cpucache(cachep);
                up(&cache_chain_sem);

enable_cpucache分析：
static void enable_cpucache(kmem_cache_t *cachep)
{
        int err;
        int limit, shared;
        /* 根据每个obj的大小，确定ac cache的个数 */
        if (cachep->objsize > 131072)
                limit = 1;
        else if (cachep->objsize > PAGE_SIZE)
                limit = 8;
        else if (cachep->objsize > 1024)
                limit = 24;
        else if (cachep->objsize > 256)
                limit = 54;
        else
                limit = 120;

        shared = 0;
#ifdef CONFIG_SMP
        if (cachep->objsize <= PAGE_SIZE)
                shared = 8;
#endif

#if DEBUG
        if (limit > 32)
                limit = 32;
#endif
/* 如果设置了抢占，内存的缓存不要很大，因为内存很容易过期 */
#ifdef CONFIG_PREEMPT
        if (limit > 16)
                limit = 16;
#endif
        /* 分配ac */
        err = do_tune_cpucache(cachep, limit, (limit+1)/2, shared);
        if (err)
                printk(KERN_ERR "enable_cpucache failed for %s, error %d.\n",
                                        cachep->name, -err);
}

do_tune_cpucache中调用下面函数，为每个cpu分配一个以下大小的内存，这个内存当然也是通过通用kmem_cache获得的。当CPU 没有初始化完成，如上面的第五步骤，只会初试化一个CPU的ac，后续的CPU当 UP或者热插拔的时候通过回调函数cpuup_callback()分配或者删除对应的ac

static struct array_cache *alloc_arraycache(int cpu, int entries,
                                                int batchcount)
{
        int memsize = sizeof(void*)*entries+sizeof(struct array_cache);
        struct array_cache *nc = NULL;

                /* kmalloc将会从通用size kmem_cache_t中获得内存 */
        if (cpu == -1)
                nc = kmalloc(memsize, GFP_KERNEL);
        else
                nc = kmalloc_node(memsize, GFP_KERNEL, cpu_to_node(cpu));

        if (nc) {
                nc->avail = 0;
                nc->limit = entries;
                nc->batchcount = batchcount;
                nc->touched = 0;
        }
        return nc;
}

上面解释的使你提到的第一个问题。

第二个问题：
内存的分配和删除：
内存的释放：内存不会直接释放，不光是因为slab，而且是因为slab中的kmem_cache_t中的ac cache，当某个任务运行在CPU 1上释放了内存，内存直接缓存在ac中，而且slab链表都不会知道这个内存已经释放，这个slab obj在kmem_cache_t->lists->中的slabs_partial或者slabs_full 链表中，没有更新。
分配内存首先找kmem_cache_t->ac中的cache， 这个cache中保存了最近刚释放内存的地址，是每个CPU有一个的，获得内存后可以直接使用，而不用像你说得更新slab，因为：1. 这个内存直接可以使用 2.slab只是管理这块内存，而这块内存当时释放的时候就没有更新slab，所以slab依然认为这个obj处于used状态。

如果没有per cpu结构，获取ac中的某个obj，可能需要以下代码：
spin_lock_irqsave(lock,flag)
        ac = ac_data(cachep, cpu);
        objp = ac_entry(ac)[--ac->avail];
spin_unlock_irqrestore(lock, flag)

而现在只需要：
local_irq_save_nort(save_flags);
        ac = ac_data(cachep, cpu);
        objp = ac_entry(ac)[--ac->avail];
local_irq_restore_nort(save_flags);

也就是说，其它CPU可以同时分配同一种类型的内存，而上面的代码是不行的。

第三个问题没看懂，你能详细解释一下吗？

内核版本：2.6.15-rt6

[ 本帖最后由 xiaozhaoz 于 2006-1-23 12:24 编辑 ]

joyhappy

首先赞一个，另外我也还在看code。完全看懂之后再和老兄你的帖子探讨。我的速度比较慢。

我觉得要完全弄懂这个问题，是不是得把smp下的cache cosistency看一看，觉得ac这一块和硬件以及smp的一致性算法关系很密切。

我的问题是，ac只是缓存对象的指针。对象的内容是不是CPU的L1等硬件cache真正缓存了？这样一来，会不会出现指向同一个对象的指针有多个，而这多个指针被缓存在不同CPU的ac中呢？而且会不会出现，CPU1的硬件cache中缓存了修改过的对象内容，在cpu2的硬件cache中的相同对象内容出现dirty。这时，是不是首先需要cpu1将硬件cache中的对象内容更新到slab中，cpu2接着更新自己硬件cache中的内容。

另外，如果不同CPU中ac的对象指针都不相同？那么通过什么样的机制来保证每个CPU的ac中的对象指针都不相同？

xiaozhaoz

是否会在多个CPU的cache中，我觉得不太可能，
1. 内核中的内存通过指针访问一般要用引用计数机制，如果有运行在不同CPU或者多个任务保存了地址指针，这块内存不会进入kfree函数。
2. 如果进入了kfree(), 我觉得一个obj不可能 在多个CPU的ac中，因为，将obj 存放到ac中在kfree中完成，kfree必须要锁中断。代码如下：

void kfree(const void *objp)
{
        kmem_cache_t *c;
        unsigned long flags;

        if (unlikely(!objp))
                return;
                /* 必须要锁中断。设想一下，如果不锁中断，被时钟中断抢占，可能导致任务被重新调度，
              或者rebalance到其它CPU上执行，就可能出现你说的问题。 */
        local_irq_save_nort(flags);
        kfree_debugcheck(objp);
        c = page_get_cache(virt_to_page(objp));
#ifdef CONFIG_DEBUG_DEADLOCKS
        if (check_no_locks_freed(objp, objp+cache_size(c)))
                printk("slab %s[%p] (%d), obj: %p\n",
                        c->name, c, c->objsize, objp);
#endif
        __cache_free(c, (void*)objp);
        local_irq_restore_nort(flags);
}

xiaozhaoz

上贴考虑的是ac不可能在多个CPU上有同时缓存一个obj。
如果要考虑一个地址的内容在多个CPU中缓存，他们的一致性的问题，这个我们可以另外详细讨论，这个确实和cache consistency有关。

joyhappy

1。 您的意思是初始化ac时，ac中并没有实际的obj的指针，只是系统预分配了ac的大小（包括对象指针数组）。在以后如果有任务kfree时，就将刚free的obj放入cpu1的ac中，但在slab中这个obj仍然不是free的。对吗？

此后，如果有另一个任务在cpu2上，要分配同类型obj，那么cpu2需要重新从slab分配obj；而同时，如果有任务在cpu1上需要分配同类型obj，cpu1只需要从ac中直接使用kfree放入的obj就可以了，不需要重新分配了。这样就实现了多个CPU同时分配obj了。对吗？  另， 是不是说ac只是对分配obj时起作用，对缓存数据起的作用不大？

2。如果一个obj指针在ac中被缓存，那么会不会出现其他CPU也需要访问该obj的情况？这时，应该是需要spin-lock了吧，这时ac也就对性能没有帮助了？

3。do_tune_cpucache被enable_cpucache调用，而enable_cpucache在ac初始化以后每次kmem_cache_create时都被调用。
  在do_tune_cpucache中有如下代码：
        new_shared = alloc_arraycache(-1, batchcount*shared, 0xbaadf00d);
        if (new_shared) {
                struct array_cache *old;

                spin_lock_irq(&cachep->spinlock);
                old = cachep->lists.shared;
                cachep->lists.shared = new_shared;
                if (old)
                        free_block(cachep, ac_entry(old), old->avail);
                spin_unlock_irq(&cachep->spinlock);
                kfree(old);
        }
这段代码的作用好像是扩充kmem_cache中的list结构体中的share成员（share也是个ac），让该成员的空间大小等于所有cpu的ac的大小。
其中“0xbaadf00d”不知道何意？是不是通过share可以定位obj被那个cpu的ac缓存了？

4。如果一个obj被cpu1缓存并使用，cpu2能否访问该obj？cpu2如何知道该obj是被cpu1在使用的？

xiaozhaoz

对你的第一点部分同意.

我觉得首先要把内核中关于内存分配和释放的全过程弄清楚。
我比较喜欢从释放内存开始理解：

释放内存：
如一个skb， 当这个skb指针在多处保存，需要将skb->users引用计数+1, 即用skb_get(). 这样,当任务要释放skb的时候,调用kfree_skb(),这个函数会检查引用计数 skb->users是否为1,如果不是,直接返回,并不释放这块内存,否则,最终调用kfree()释放内存,
kfree() 要做以下事情:
1. 根据内存地址查找到对应的kmem_cache_t, 这个过程有一些优化,通过内存地址所在的物理页查找到对应的kmem_cache_t,在后面的内存分配会看到,当需要增加物理内存时,必须将整页内存分配个某个slab.
2. 将内存地址存放在kmem_cache_t->ac中的指定CPU cache数组中, 这时不会更新slab和kmem_cache_t->list->shared链表,除非下面的第二种情况出现. 所以slab 链表中,依然认为这块内存处于分配状态.

每个cpu有自己的ac cache, kfree()中的两种情况:
1. 正常释放到ac cache中.
2.当某个cpu的ac cache达到设定的上限值 ac->avail >ac->limit, 必须调用cache_flusharray()将ac->batchcount个obj从 ac 数组中转存到kmem_cache_t->lists->shared cache中.所以, shared cache充当了二次cache.

内存分配,当kmem_cache_t创建好的时候, 其中没有任何slab可用,分配第一个slab,会调用对应的分页算法分配物理页,每次必须分配整数个物理页,分页算法一般采用buddy算法.
kmalloc()分配算法: 如果是标准结构,如skb,
1. 从专用kmem_cache_t中分配, 先查找ac cache, 有可用的内存,直接将最后一个分配出去,否则
2. 从kmem_cache_t->lists->shared中转移batchcount 到指定cpu的ac cache中, 如果shared cache也没有可用obj
3. 从 partial slab 或者 free slab中分配内存, 如果没有可用slab
4. 调用分页算法添加新页到slab中.

上述过程中, 2~4必须锁kmem_cache_t中的自旋锁,所以多cpu不能同时进入.

如果是通用内存分配, 唯一的不同就是先要选择合适大小的kmem_cache_t cahce, 找到对应的kmem_cache_t后,直接按照上面的算法分配. 如果上述过程都是失败了(系统没有物理内存可用),在MMU cpu中,调用kswap任务,将内存 swap到磁盘上,空出可用物理内存页. 对于nommu cpu,返回NULL, 并提示出错,或者调用OOM killer

通过上面的过程可见,
1. ac cache中的obj 地址,不可能被多个cpu共用, kfree()执行不到,除非内核有bug. 也就是说,一旦进入ac cache后,这快内存一定是需要被释放的,其他cpu应该没有保存这个指针.

2. shared cache是作为一个二级cache使用的,这级cache不会刷回到slab中, 这是为了避免象网络这样的任务,一个cpu执行内核接收任务或者软中断接收分配300个skb或者更多,而另一个cpu执行发送,释放大量的skb,导致两个ac严重不平衡, shared缓存相当于一个蓄水池. 避免直接操作slab.

3. 至于0xbaadf00d, 我觉得只是一个maggic number, 这个值不会起任何作用. 因为shared不会刷回到slab中.

但是,当系统物理内存不够用时,内核会reap 所有的kmem_cache,这时 shared中的objs可能会释放.这个需要详细分析.

cheers!

[ 本帖最后由 xiaozhaoz 于 2006-1-23 19:24 编辑 ]

joyhappy

首先狂赞一下xiaozhaoz，正是和您的讨论当中，有些细节的东西才越来越清晰。建议xiaozhaoz能够在看完mm之后，充分共享这些宝贵的资源。当然，如果需要我出一分力，我当然也会倾尽全力而为之。
   我看的是2.6.13.1
    补充一点，不论是调用kmem_cache_alloc/kmem_cache_free来分配和释放专用对象，还是调用kmalloc/kfree来分配和释放通用对象，其实最后都是通过__cache_alloc/__cache_free来完成。只不过kmem_cache_alloc/kmem_cache_free最终对针对静态cache链cache_cache进行，而__cache_alloc/__cache_free最终针对静态cache链malloc_cache中的DMA区cache或非DMA区cache进行操作。也就是传给__cache_alloc/__cache_free的cachep指针不一样。一旦，进入了__cache_alloc/__cache_free过程内部，通用cache和专用cache处理过程应该一样。专用cache和通用cache因为两者并没有本质的区别，只是一个关注于obj的大小，一个关注于obj的内容。

__cache_alloc/__cache_free其分配和释放过程xiaozhaoz说的应该正确。
   其他的象cache_grow/cache_reap, __cache_shrink等过程中对slab的其他操作。

   期待xiaozhaoz的下一个mm方面的好帖

[ 本帖最后由 joyhappy 于 2006-1-24 11:59 编辑 ]

xiaozhaoz

大家一起讨论才有进步, 其实我对内存管理这块最不熟悉, 只花了几天时间看看, 只懂内核是怎么实现的,一些细节还不是很清楚,特别是对于mm的内核同步分析.

其实我平时做得最多的是任务管理,调度和网络.

我看内核喜欢看大局的东西, 内存管理是作为一个整体来看的. LKML上经常说big picture, 就是这个了, 首先将内核和内存管理有关的东西, 各个模块的关系弄清楚, 在分析每个的细节,分析内核模块的细节一定要弄清楚各个模块的 内核同步.

要做到 知其然, 而后知其所以然,  最后才是知道如何改进和修改内核不合理的地方.