kfree関数をスラブから獲得したオブジェクト（メモリー）を解放するのですが、kmallocではオブジェクトを獲得するというより、スラブからオブジェクトを借り受けると言うものでした。従ってkfreeにおいては解放というより、スラブにオブジェクト返すと言った案配です。ではスラブのどこに返すか？と言うことですが、そのオブジェクトが属しているスラブでしょうか？

このオブジェクトはキャッシュに乗っている可能性が高いわけで、再度kmallocでオブジェクトを要求された時、このオブジェクトをそのメモリーとして返した方がパフォーマンスがいい訳です。従ってこのオブジェクトはスラブオブジェクトをプールしている配列 kmem_cache->array_cache->entry[]に戻します。

なお、エントリー全てが未使用状態であった場合でも（オブジェクトを返す領域が無い。）、わざわざ既に配列に登録している空きオブジェクトを戻し、空きを作ってそこに解放するオブジェクトをセットするようにしています。

virt_to_cache関数で解放するオブジェクトアドレスからstruct kmem_cacheを取得します。オブジェクトアドレスをページアライメントすれば、そのページが求められ、ページのpage->lru.nextには、そのページをスラブに割り当てる時、struct kmem_cacheをセットされています。

そして、struct kmem_cache、解放するオブジェクトのアドレスで__cache_free関数を呼んでその実処理となっています。

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

       if (unlikely(ZERO_OR_NULL_PTR(objp)))
               return;
       local_irq_save(flags);
       kfree_debugcheck(objp);
       c = virt_to_cache(objp);
       debug_check_no_locks_freed(objp, obj_size(c));
       debug_check_no_obj_freed(objp, obj_size(c));
       __cache_free(c, (void *)objp);
       local_irq_restore(flags);
}

static inline struct kmem_cache *virt_to_cache(const void *obj)
{
       struct page *page = virt_to_head_page(obj);
       return page_get_cache(page);
}

__cache_freeはオブジェクトをac->entry[]に戻すわけです。ac->availはac->entry[]の空き要素のインデックスで、ac->limitはac->entry[]の最大要素です。なお、ac->entry[]は後ろから前に向かって使用されます。この事は以下の処理を実現する上で重要です。

|未使用1|未使用2|未使用3|使用1|使用2|の場合、ac->availは2、ac->limitは5となります。

if (likely(ac->avail < ac->limit))の時、ac->entry[]内の使用オブジェクトを解放オブジェクトのアドレスに差し替えます。上の例では使用1に解放オブジェクトのアドレスをセットするわけです。

もし、全て未使用状態で返す場所がなかったら、ac->entry[]の先頭から所定の数（ac->batchcount）で、そのオブジェクトをスラブに返すことで、ac->entry[]に空きを作成した上で、解放オブジェクトのアドレスをac->entry[]にセットします。

補足
使用中のエントリーに上書きしたら、上書きされたオブジェクトを解放する時大丈夫か？と言う疑問がでてきます。（当初このことで悩みました。）実際のオブジェクトが使用されているかどうかは、スラブアロケータではどうでもいいことで、返却されたオブジェクトはただ別のkmallocで貸し出す対象にするだけのことです。実際kfreeしてもそのオブジェクトそのものは解放されているわけでなく、他で利用されている可能性はあるものの、さらに参照できるということです。（たぶん）

static inline void __cache_free(struct kmem_cache *cachep, void *objp)
{
       struct array_cache *ac = cpu_cache_get(cachep);

       check_irq_off();
       objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));

       if (numa_platform && cache_free_alien(cachep, objp))
               return;

       if (likely(ac->avail < ac->limit)) {
               STATS_INC_FREEHIT(cachep);
               ac->entry[ac->avail++] = objp;
               return;
       } else {
               STATS_INC_FREEMISS(cachep);
               cache_flusharray(cachep, ac);
               ac->entry[ac->avail++] = objp;
       }
}

cache_flusharray関数で、オブジェクトをプールしているac->entry[]をスラブに戻します。まず、if (l3->shared)で共有プール配列に戻せるか試みます。このチェックはキャッシュディスクリプターが共有配列を有していて、しかも、使用している要素が有る場合、その数だけ戻しています。その数はint max = shared_array->limit - shared_array->availです。もし、共有プール配列プールに戻せない場合、free_block関数で、リスト上のスラブそのもに戻します。

そして上記の処理で空いたプール配列ac->entry[]の、memmoveで戻した分、その内容を移動すると共に、ac->avail -= batchcountで空き要素を少なくしています。処理のイメージは以下のような感じです。

ac->avail=3 |未使用1|未使用2|未使用3|使用1|使用2|
で3要素移動する。
ac->avail=0 |使用1|使用2|ゴミ1|ゴミ2|ゴミ3|

static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)
{
       int batchcount;
       struct kmem_list3 *l3;
       int node = numa_node_id();

       batchcount = ac->batchcount;

       check_irq_off();
       l3 = cachep->nodelists[node];
       spin_lock(&l3->list_lock);
       if (l3->shared) {
               struct array_cache *shared_array = l3->shared;
               int max = shared_array->limit - shared_array->avail;
               if (max) {
                       if (batchcount > max)
                               batchcount = max;
                       memcpy(&(shared_array->entry[shared_array->avail]),
                              ac->entry, sizeof(void *) * batchcount);
                       shared_array->avail += batchcount;
                       goto free_done;
               }
       }

       free_block(cachep, ac->entry, batchcount, node);
free_done:
       spin_unlock(&l3->list_lock);
       ac->avail -= batchcount;
       memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);
}

free_block関数でスラブそのものに戻す場合の処理を行います。nr_objectsは戻す数で、その数でループすることで一個ずつ所定の処理をスラブに施して戻します。

まずオブジェクトのアドレスからstruct slabを取得し、一旦そのスラブが繋がっているリストから外します。オブジェクトをスラブに返した場合、slabs_partialに繋がっていたものをslabs_freeに、またその逆に繋ぎかえる必要があるからです。

そしてslab_put_obj関数で、スラブのオブジェクトスクリプタで、そのオブジェクトのインデックスに空きのインデックスを設定します。このオブジェクトはプール配列に設定されていたため0となっているからです。そしてl3->free_objects++で空きオブジェクト数をインクリメントします。

次にスラブリストへの登録です。if (slabp->inuse == 0)は、そのスラブの全てのオブジェクトは空き（プール配列に設定されていない。）です。この場合list_addでl3->slabs_freeにリスト登録いたします。ただし、if (l3->free_objects > l3->free_limit)で、空きオブジェクト数がl3->free_limitを超えた場合、slab_destroyでスラブ自身を解放します。

if (slabp->inuse == 0)出ない場合、list_addでl3->slabs_partialにリスト登録いたします。

static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects,
                      int node)
{
       int i;
       struct kmem_list3 *l3;

       for (i = 0; i < nr_objects; i++) {
               void *objp = objpp[i];
               struct slab *slabp;

               slabp = virt_to_slab(objp);
               l3 = cachep->nodelists[node];
               list_del(&slabp->list);
               check_spinlock_acquired_node(cachep, node);
               slab_put_obj(cachep, slabp, objp, node);
               STATS_DEC_ACTIVE(cachep);
               l3->free_objects++;
               
               if (slabp->inuse == 0) {
                       if (l3->free_objects > l3->free_limit) {
                               l3->free_objects -= cachep->num;
                               slab_destroy(cachep, slabp);
                       } else {
                               list_add(&slabp->list, &l3->slabs_free);
                       }
               } else {
                       list_add_tail(&slabp->list, &l3->slabs_partial);
               }
       }
}

slab_put_obj関数は対応するオブジェクトのオブジェクトディスクリプタを、次の空きオブジェクトのインデックスで設定します。 obj_to_index関数でオブジェクトのアドレスからそのインデックスを求めます。そしてslab_bufctl(slabp)[objnr] = slabp->freeで、そのインデックスのオブジェクトディスクリプタに先の空きインデックスを、slabp->freeをこのオブジェクトのインデックスをセットし、slabp->inuse--で未使用オブジェクトをデクリメントいたします。

static void slab_put_obj(struct kmem_cache *cachep, struct slab *slabp,
                               void *objp, int nodeid)
{
       unsigned int objnr = obj_to_index(cachep, slabp, objp);

       slab_bufctl(slabp)[objnr] = slabp->free;
       slabp->free = objnr;
       slabp->inuse--;
}