kmallocはスラブアロケータからメモリが割り当てられます。スラブとは、同じサイズのオブジェクトとして分割した、予め確保している物理的に連続するメモリー区間の事（キャシュ）をいいます。従ってkmallocでメモリーを確保すると言うより、スラブからそのメモリを借り受ける。と言ったほうが、その実装からみると的を得ているように思います。

スラブによるメモリ取得とは、まさに上で説明したものなのですが、スラブの性格上、頻度に確保/開放が繰り替えされる用途で使われます。そのためキャッシュの効用を生かすために、その実装となると、その構造体の取り扱いとか、スラブの管理の仕方なので、なかなか理解しがたいものでした。

実装の概要としては、kmallocでメモリを割り当てる時、直接スラブから（同じサイズのスラブをリスト管理している。）割り当てません。まず利用できるスラブのアドレスを前もってプール（配列にセット）し、そこから割り当てます。もしこのプールがなくなると、スラブリストから空いているスラブを先のプールしている配列にセットすることで、kmallocの割り当てとしています。

ここで、プールとなる配列はCPU毎に独自に有しています。こうすることで、この配列に空きが有る限り、その獲得/開放において、割り込みを禁止するだけで、スピンロック掛ける必要がないからです。（たぶん）なお、スラブリストからプール配列に設定する時、スピンロックが必要となります。メモリの有効利用と言う観点から、このリストをCPU毎に共通にしたほうがいいからだと思います。

実装を見る前に、これらの構造体を関係を理解しておかないと、理解しがたいです。下記は実装を理解するためにの構造体の関係の概略です。malloc_sizesはスタテックな配列変数で、管理するオブジェクトサイズに応じて、それら全てのスラブを管理しています。

kmallocでは確保するサイズに見合うmalloc_sizesを、そのメンバーcs_sizeを調べる事で取得します。そして、malloc_sizes->*array[]->entry[]をkmallocの獲得したメモリとして返していきます。

malloc_sizes->*array[]->availは、entry[]にあきスラブがあるかのインデックスです。もし空きが無ければ、struct kmem_list3 *nodelists[MAX_NUMNODES]配下でリスト管理しているスラブから、そのアドレスを*array[]にセットすることで、kmallocの要求に応えます。（MAX_NUMNODESはX86では１です。）

なお、*nodelists下に、struct array_cache *sharedがあります。これは全CPU共通として、すぜにスラブのアドレスをセットしている配列です。struct array_cache *arrayにスラブアドレスをセットする場合、まずstruct array_cache *sharedから割り当てます。割り当てはその内容を複写すればいいだけで、slabs_partial/slabs_fullから割り当てるより効率的です。（slabs_partial/slabs_fullから割り当てるとリストの繋ぎ換えが発生する。）

struct cache_sizes malloc_sizes[]
       |- size_t              cs_size
       |- struct kmem_cache   *cs_cachep;
       |                 |- struct array_cache *array[NR_CPUS];
       |                 |     |- unsigned int avail;
       |                 |     |- void *entry[];
       |                 |- struct kmem_list3 *nodelists[MAX_NUMNODES];
       |                       |- struct list_head slabs_partial; 
       |                       |- struct list_head slabs_full;
       |                       |- struct list_head slabs_free;
       |                       |- struct array_cache *shared; 
       |- struct kmem_cache   *cs_dmacachep;

__do_kmalloc関数が実際の処理の入り口となります。まず、__find_general_cachep関数で、struct kmem_cache *cachepを選出します。そして、__cache_alloc関数でそのキャッシュから空いているスラブアドレスを返します。

static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
                                         void *caller)
{
       struct kmem_cache *cachep;

       cachep = __find_general_cachep(size, flags);
       if (unlikely(ZERO_OR_NULL_PTR(cachep)))
               return cachep;
       return __cache_alloc(cachep, flags, caller);
}

__find_general_cachep関数では、while (size > csizep->cs_size)条件で、サイズに見合うキャシュをmalloc_sizes配列から選出し、そのキャッシュをgfpflags & GFP_DMAなら、csizep->cs_dmacachepを、そうでないならcsizep->cs_cachepをkmem_cache *として取得します。

static inline struct kmem_cache *__find_general_cachep(size_t size,
                                                       gfp_t gfpflags)
{
       struct cache_sizes *csizep = malloc_sizes;

       if (!size)
               return ZERO_SIZE_PTR;

       while (size > csizep->cs_size)
               csizep++;

#ifdef CONFIG_ZONE_DMA
       if (unlikely(gfpflags & GFP_DMA))
               return csizep->cs_dmacachep;
#endif
       return csizep->cs_cachep;
}

cachep = __find_general_cachep(size, flags)のcachepは、要求するサイズに応じたスラブを有するキャッシュということです。次にcachepを引数として、*____cache_alloc関数を呼び出すことで、空きスラブオブジェクトのアドレスを取得します。

ac = cpu_cache_get(cachep)で、ローカルCPUのstruct array_cache arrayを取得し、そのメンバーavailが0でないなら、空きのスラブオブジェクトがあると言うことで、objp = ac->entry[--ac->avail]で、そのアドレスを返します。インデックスを--ac->availとしているように、オブジェクトはプール配列の後ろから割り当てているようです。

空きが無いなら、cache_alloc_refillで、スラブリストから空きのスラブオブジェクトを、ac->entry[]に設定し、その一つを返します。

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
       void *objp;
       struct array_cache *ac;

       check_irq_off();

       ac = cpu_cache_get(cachep);
       if (likely(ac->avail)) {
               STATS_INC_ALLOCHIT(cachep);
               ac->touched = 1;
               objp = ac->entry[--ac->avail];
       } else {
               STATS_INC_ALLOCMISS(cachep);
               objp = cache_alloc_refill(cachep, flags);
       }
       return objp;
}

static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep)
{
       return cachep->array[smp_processor_id()];
}

cache_alloc_refill関数では、スラブリストを管理しているstruct kmem_list3を、l3 = cachep->nodelists[node]で取得し、まずl3->sharedで、共通キャッシュエントリから取得を試みます。l3->sharedに空きがあれば、transfer_objects関数で、そのメモリをac->entry[]に複写して獲得完了です。

共通キャッシュエントリに空きがない場合、entry = l3->slabs_partial.nextでまず部分的使用しているスラブリストから、if (entry == &l3->slabs_partial)でもしリスト上にスラブが無ければ、（nextが自分自身を示している。）entry = l3->slabs_free.nextからキャッシュエントリを追加しています。

なお、一回の追加の処理で追加されるスラブは、batchcount = ac->batchcountです。なお、while (slabp->inuse < cachep->num && batchcount--)はリストされているスラブにはオブジェクトを複数有しているからです。

batchcount = ac->batchcount個、ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,node)で追加します。そして追加したスラブをlist_del(&slabp->list)で削除し、そのスラブにオブジェクトが無くなったらlist_add(&slabp->list, &l3->slabs_full)で、slabs_fullに、そうでないならslabs_partialに繋ぎ換えています。
　
ここでslabs_full/slabs_partialですが、この意味はそのスラブ内のオブジェクトが実際kmallocとして利用されていると言うのでなく、ac->entry[]のローカルキャッシュ配列に登録されていると言う事です。実は当初これを理解していなくて、kfreeの実装が見えなくなってしまいました。

slabs_partial/slabs_freeに空きがない場合、cache_grow関数でスラブそのものを確保しています。

static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
       int batchcount;
       struct kmem_list3 *l3;
       struct array_cache *ac;
       int node;

retry:
       check_irq_off();
       node = numa_node_id();
       ac = cpu_cache_get(cachep);
       batchcount = ac->batchcount;
       if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
               batchcount = BATCHREFILL_LIMIT;
       }
       l3 = cachep->nodelists[node];

       BUG_ON(ac->avail > 0 || !l3);
       spin_lock(&l3->list_lock);

       if (l3->shared && transfer_objects(ac, l3->shared, batchcount))
               goto alloc_done;

       while (batchcount > 0) {
               struct list_head *entry;
               struct slab *slabp;
               entry = l3->slabs_partial.next;
               if (entry == &l3->slabs_partial) {
                       l3->free_touched = 1;
                       entry = l3->slabs_free.next;
                       if (entry == &l3->slabs_free)
                               goto must_grow;
               }

               slabp = list_entry(entry, struct slab, list);
               check_slabp(cachep, slabp);
               check_spinlock_acquired(cachep);

               BUG_ON(slabp->inuse < 0 || slabp->inuse >= cachep->num);

               while (slabp->inuse < cachep->num && batchcount--) {
                       STATS_INC_ALLOCED(cachep);
                       STATS_INC_ACTIVE(cachep);
                       STATS_SET_HIGH(cachep);

                       ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,
                                                           node);
               }
               check_slabp(cachep, slabp);

               list_del(&slabp->list);
               if (slabp->free == BUFCTL_END)
                       list_add(&slabp->list, &l3->slabs_full);
               else
                       list_add(&slabp->list, &l3->slabs_partial);
       }

must_grow:
       l3->free_objects -= ac->avail;
alloc_done:
       spin_unlock(&l3->list_lock);

       if (unlikely(!ac->avail)) {
               int x;
               x = cache_grow(cachep, flags | GFP_THISNODE, node, NULL);

               ac = cpu_cache_get(cachep);
               if (!x && ac->avail == 0)       /* no objects in sight? abort */
                       return NULL;

               if (!ac->avail)         /* objects refilled by interrupt? */
                       goto retry;
       }
       ac->touched = 1;
       return ac->entry[--ac->avail];
}

スラブ内のオブジェクトのアドレスの取得は、*slab_get_obj関数で行っています。スラブの実態は連続するメモリーの先頭に、そのオブジェクトを管理するstruct slab構造体を有し、それ以降に実メモリーとしてのオブジェクトを有する構造をとっています。*index_to_obj関数では、オブジェクトの開始アドレスにオブジェクトサイズ×空き位置で、アドレスを取得しています。

そして次の空きオブジェクトの位置をslabp->free = nextとして、slabp->freeに設定するのですが、スラブの実オブジェクトを保存するエリアの先頭に、まずstruct slabを有し、その次にスラブの空きエリアのインデックス群を有しています。このインデックスは取得したインデックスに対するこのインデックス群のインデックスは、次の空きインデックスを保持しています。

slab_bufctl関数でのreturn (kmem_bufctl_t *) (slabp + 1)で、next = slab_bufctl(slabp)[slabp->free]としているのは、先頭のstruct slabの次のアドレスを配列として処理するためです。たのこの害列の最後はBUFCTL_ENDがセットされていて、処理したスラブに空きが無いかどうかで、slabs_partial/slabs_freeのどちらのリストに繋ぎかえるかのチェックすることが可能となっています。

static void *slab_get_obj(struct kmem_cache *cachep, struct slab *slabp,
                               int nodeid)
{
       void *objp = index_to_obj(cachep, slabp, slabp->free);
       kmem_bufctl_t next;

       slabp->inuse++;
       next = slab_bufctl(slabp)[slabp->free];

       slabp->free = next;

       return objp;
}

static inline void *index_to_obj(struct kmem_cache *cache, struct slab *slab,
                                unsigned int idx)
{
       return slab->s_mem + cache->buffer_size * idx;
}

static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
{
       return (kmem_bufctl_t *) (slabp + 1);
}