Linuxカーネル3.2のメモリ管理システム：Cleancache

# はじめに
<!-- 発端や概要を記載 -->
Linuxカーネルに関する包括的な書籍は[[1]](#bib1),[[2]](#bib2),[[3]](#bib3)などがありますが、その多くはバージョン2.x系（主に2.6系）のカーネルに基づいて書かれています。このシリーズでは、メモリ管理機構に焦点をあてて、バージョン3.x系以降の進化を解説します。私個人の勉強記録でもあり、[[1]](#bib1)のようなコードに基づいたできるだけ詳細な解説をめざします。ドキュメントを参照しながら読んでいますが、誤り等あれば指摘していただけると嬉しいです。

本記事ではバージョン2.6系からバージョン3.2系での進化について解説します。取り上げるのはcleancacheという機構です[^1]。本記事で解説するソースコードはバージョン3.2.29のものです。

[^1]: cleancache機構は、Linux 5.17で削除され、現在では使用されていませんが、カーネルの進化をたどるという目的から解説します。

# 目次
<!-- タイトルとアンカー名を編集 -->
- [はじめに](#はじめに)
- [目次](#目次)
- [Cleancache](#cleancache)
	- [概要](#概要)
	- [フロントエンド実装](#フロントエンド実装)
		- [データ構造](#データ構造)
	- [zcacheの実装](#zcacheの実装)
		- [データ構造](#データ構造-1)
		- [zcache\_compress](#zcache_compress)
		- [zbud\_create](#zbud_create)
	- [zcacheによるtmem実装](#zcacheによるtmem実装)
		- [データ構造](#データ構造-2)
		- [tmem\_put](#tmem_put)
	- [zcacheによるcleancache実装](#zcacheによるcleancache実装)
		- [zcacne\_put\_page](#zcacne_put_page)
- [参考文献](#参考文献)

<!-- 各チャプター -->
<a id="#Chapter1"></a>

# Cleancache
## 概要
cleancacheとは、page cacheをより有効に使うための機構です。使用されなくなった、あるいは優先度が低いと判断されたページフレームは通常PFRA (Page Frame Reclaiming Algorithm) によって回収されますが、cleancache機構を有効にしている場合、回収対象になったページフレーム中のデータはまずcleancacheと呼ばれる領域に保持されます。cleancache機構を有効にしたファイルシステムが次にデータをページインしたくなった場合、ファイルシステムはまずcleancacheを探し、該当のデータがあればそこから獲得します。これはメモリとswap areaの間をつなぐswap cacheの役割に似ていますね。

cleancacheの特徴は、短命であることです。cleancache中のページフレームはいつでもPFRAの回収対象になるため、cleancacheには決まったサイズがありませんし、カーネルもその大きさを知りません。cleancache機構がデータを保持する領域のことを 'transcendent memory' （略してtmem）と呼びます。transcendentは「超越した」というような意味で、この領域はメモリ上にありますが、カーネルから直接アクセスできないためにこのように呼ばれています。

## フロントエンド実装

### データ構造
カーネル側（フロントエンド）でcleancacheを実現するデータ構造として、cleancacheを操作するメソッド群をまとめる構造体である`cleancache_ops`があります。その定義は`include/linux/cleancache.h`に含まれ、以下のメンバからなります。
|メソッド |概要|
|---|---|
|init_fs  | 新規プールの作成を行います。|
|init_shared_fs  | 新規プールの作成を行います。|
|get_page | cleancacheからページを取得します。|
|put_page | cleancacheにページを退避します。|
|flush_page | cleancache内のページをフラッシュします。|
|flush_inode | cleancache内の、inodeで指定されたファイルを構成するページをすべてフラッシュします。|
|flush_fs | プールを破棄します。|

各用語の意味は次節以降で説明していきます。

カーネルは`cleancache_register_ops()`を呼び出すことで、バックエンドで実装されたメソッド群を`cleancache_ops`型の`cleancache_ops`という変数に登録します。以降、カーネルはこれらのメソッド群を直接呼び出さず、ラッパー関数を通して呼び出します。例えば`init_fs()`の場合は以下のようになります。

```c:mm/cleancache.c
void __cleancache_init_fs(struct super_block *sb)
{
	sb->cleancache_poolid = (*cleancache_ops.init_fs)(PAGE_SIZE);
}
EXPORT_SYMBOL(__cleancache_init_fs);
```

したがって、これらのメソッドの具体的な実装を見るには別の箇所（バックエンドにあたるtmemの実装）をあたる必要がありそうです。cleancacheの導入時点では、tmemの実装としてはXenという仮想化ソフトウェアを用いるもの、zcacheというメモリ圧縮機構を用いるものの2種類が用意されました。Xenはtype 1（ベアメタル型）のハイパーバイザで、Xenによる実装を理解するにはXenのカーネルを読む必要があります。ここではあくまでlinuxカーネルを読みたいという方針からそれは避けて、zcacheによる実装を見ていきます。

## zcacheの実装
zcacheそのものの主要な機構は、`drivers/staging/zcache/zcache-main.c`に実装されています。tmemの解説に入る前に、まずzcacheの実装について、`zcache_compress()`と`zbud_create()`という2つの関数をとりあげて解説します。
### データ構造
zcacheのデータ構造について解説します。

zcache内の物理ページは、リスト構造で管理されます。一つの物理ページは、リストの連結部、2つのヘッダ領域と一つの圧縮されたデータ領域から構成され、圧縮されたデータ領域は2つの物理ページのデータを格納できるようになっています。圧縮されたデータは、64バイトのチャンクの集まりとして並べられます。zcache内での同じ物理ページ内に圧縮された2つの物理ページのペアのことをbuddyからとってzbudと呼び、zcache内でのページをzbud pageやzbpgと呼びます。また、ヘッダ領域は圧縮されたそれぞれのデータに対応します。これは`zbud_hdr`という構造体が表現します。主要なメンバを以下に示します。

|型  |メンバ |概要 |
|---|---|---|
|unit16_t  |client_id  |オブジェクトのあるtmemのクライアントID。|
|uint16_t  |pool_id  |オブジェクトのあるtmemのプールID。|
|struct tmem_oid | oid|オブジェクトID。|
|uint32_t | index| オブジェクトが格納するデータのインデックス。|
|uint16_t | size| 圧縮後のデータサイズ（バイト単位）。|

zbpgを表現する構造体は`zbud_page`です。

|型  |メンバ |概要 |
|---|---|---|
|struct list_head |bud_list  |zbpgのリストヘッダ。|
|spinlock_t  |lock  |ロック。|
|struct zbud_hdr | buddy[2]| buddyのヘッダ。|

実際のzbpgでは、この直後に圧縮されたデータが続きます。

1つのzbpgは2つの物理ページのデータを持つことができると述べました。そこでzbpgは、格納する物理ページの数との関係から以下の3種類に分類され、それぞれ別のリストで管理されます。カッコ内は、そのリストの先頭に対応する`struct list_head`型の変数名を示します。

1. zbudをもたないもの (`zbud_unused_list`)
2. zbudを1つのみ持つもの。zbudがいくつのチャンクを使用しているかによって、`PAGE_SIZE/64`通りの場合が考えられ、それぞれ別のリストで管理されます。(`zbud_unbuddied[NCHUNKS]`)
3. zbudを2つ持つもの (`zbud_buddied_list`)

2.で使用しているチャンク数ごとにリストを分けているのは、もう一つのzbudが到着したときにどのzbpgと組み合わせればよいかを決めるためです。これは後ほど解説します。

### zcache_compress
`zcache_compress()`はデータを圧縮するための関数で、簡単に書くと以下のようになっています。`dmem`と`wmem`はCPUごとに確保されていて、それぞれ圧縮結果の保存用、作業用のメモリ領域です。
```c:drivers/staging/zcache/zcache-main.c
static int zcache_compress(struct page *from, void **out_va, size_t *out_len)
{
	char *from_va;
	from_va = kmap_atomic(from, KM_USER0);
	mb();
	ret = lzo1x_1_compress(from_va, PAGE_SIZE, dmem, out_len, wmem);
	*out_va = dmem;
	kunmap_atomic(from_va, KM_USER0);
	return 1;
}
```
`lzo1x_1_compress()`の詳細にはここでは踏み込みませんが、データ圧縮アルゴリズムの一つであるLZO1X-1アルゴリズムのLinux kernel内での実装です。ここでは先に進むために、`zcache_compress()`からreturnするとき、`*out_va`は圧縮後のメモリ領域を指し、`*out_len`には圧縮後のバイト数が格納されているということだけ言及しておきます。

### zbud_create
`zbud_create()`は、圧縮されたデータを受け取り、そこからbuddyを作成して適切なzbpgに登録する関数です。まず以下のような処理を行います。
```c:drivers/staging/zcache/zcache-main.c
	nchunks = zbud_size_to_chunks(size) ;
	for (i = MAX_CHUNK - nchunks + 1; i > 0; i--) {
		spin_lock(&zbud_budlists_spinlock);
		if (!list_empty(&zbud_unbuddied[i].list)) {
			list_for_each_entry_safe(zbpg, ztmp,
				    &zbud_unbuddied[i].list, bud_list) {
				if (spin_trylock(&zbpg->lock)) {
					found_good_buddy = i;
					goto found_unbuddied;
				}
			}
		}
		spin_unlock(&zbud_budlists_spinlock);
	}
```
`zbud_unbuddied[i]`は、すでに`i`チャンク使用されているzbpgのリストです。このループでは、圧縮したデータを格納する余裕のあるzbpgを、できるだけデータがぴったり収まるように（データを格納したときに、余りのチャンクができるだけ少なくなるように）探しています。そのようなものが見つかると、`found_unbuddied`ラベルへ飛びます。主要な処理は以下になります。

```c:drivers/staging/zcache/zcache-main.c
found_unbuddied:
	ASSERT_SPINLOCK(&zbpg->lock);
	zh0 = &zbpg->buddy[0]; zh1 = &zbpg->buddy[1];
	if (zh0->size != 0) {
		zh = zh1;
	} else if (zh1->size != 0) {
		zh = zh0;
	}
	list_del_init(&zbpg->bud_list);
	zbud_unbuddied[found_good_buddy].count--;
	list_add_tail(&zbpg->bud_list, &zbud_buddied_list);
	zcache_zbud_buddied_count++;

init_zh:
	zh->size = size;
	zh->index = index;
	zh->oid = *oid;
	zh->pool_id = pool_id;
	zh->client_id = client_id;
	to = zbud_data(zh, size);
	memcpy(to, cdata, size);
	spin_unlock(&zbpg->lock);
	spin_unlock(&zbud_budlists_spinlock);

	return zh;
```

まずzbpgのヘッダを確認し、未使用のヘッダはどちらか調べます。次にzbpgをunbuddiedリストからbuddiedリストへと付け替えます。

その後のinit_zhラベルでは、未使用のヘッダを適切に書き換え、データをzbpgに登録しています。zbpgでは、ヘッダの直後に圧縮されたデータが続くことを思い出してください。`zbud_data()`は、カーネルの`offsetof()`マクロを用いて引数として与えられたヘッダが0番目か1番目か調べたあと、その情報からデータを格納するべきアドレスを適切に計算します。この計算部分のコードが以下になります。

```c:drivers/staging/zcache/zcache-main.c
	p = (char *)zbpg;
	if (budnum == 0)
		p += ((sizeof(struct zbud_page) + CHUNK_SIZE - 1) &
							CHUNK_MASK);
	else if (budnum == 1)
		p += PAGE_SIZE - ((size + CHUNK_SIZE - 1) & CHUNK_MASK);
	return p;
```

上のコードで、`budnum`は`zbud_budnum()`という関数を用いて調べられたヘッダ番号です。ヘッダが0番目であれば`zbud_hdr`構造体の直後に、1番目であればページ最後尾から`size`バイト戻ったところに（より正確には、チャンクサイズで並べるために64バイトアラインされます）配置するようになっていることがわかります。

このアドレスを指定して`memcpy()`を呼び出せば、無事zbpgに圧縮データを格納できます。ここまでが`found_unbuddied`に飛んだあとの流れです。

最後に、unbuddiedリストから適切なzbpgを見つけられなかった場合をみてみましょう。このときは、zbpgを新しく確保する必要があります。
```c:drivers/staging/zcache/zcache-main.c
	zbpg = zbud_alloc_raw_page();
	spin_lock(&zbud_budlists_spinlock);
	spin_lock(&zbpg->lock);
	list_add_tail(&zbpg->bud_list, &zbud_unbuddied[nchunks].list);
	zbud_unbuddied[nchunks].count++;
	zh = &zbpg->buddy[0];
	goto init_zh;
```
まずはunusedリストを探しますが、それでも見つけられなければpreload（後述）しておいた空きページを使用することになっています。ここまでが`zbud_alloc_raw_page()`の仕事です。いずれにせよ、zbpgを確保したあとは`init_zh`ラベルに合流し、`zbud_create()`は新しく登録したbuddyのヘッダ`zbud_hdr`を返して終了します。

zcacheを操作する主要な関数は、他に`zbud_free()`（データの解放）、`zbud_decompress()`（データの解凍）などがありますが、ここではそれらの実装は省略し、tmem実装に進むことにします。

## zcacheによるtmem実装
ここから、ここまで説明したzcacheがどのようにtmemの実装に利用されているのかを見ていきます。tmemはput, get, flush, flush_object, new pool, destroy poolといった操作群によって制御されます。tmemの核となるこれらの関数は、`drivers/staging/zcache/tmem.c`に実装されています。ここでは`tmem_put()`をとりあげて解説します。
### データ構造
cleancacheではプールID、ファイルキー、インデックスの3つ組をhandleと呼び、それによってデータを管理していたのでした。これはcleancacheを実現するバックエンドであるtmemでも同様です。ただしファイルキーはtmemではオブジェクトIDと呼ばれ、オブジェクトという外枠の中にデータがあるという構造になっていることに注意してください。

プールは、tmem内で最も大きなデータ構造です。ふつうは一つのファイルシステムなど、独立したページの集合ごとに用意されます。それぞれのプールはプールIDとさらにハッシュテーブルを持ち、ハッシュテーブルそれぞれのバケットは赤黒木によってオブジェクトを管理しています。プールを表現する`tmem_pool`構造体の主要なメンバを以下に示します。
|型  |メンバ |概要 |
|---|---|---|
|struct list_head  | pool_list| プールどうしをつなぐリストのヘッド。|
|uint32_t |pool_id  |プールID。|
|bool | persistent | tmemの属性を示す（後述）。|
|atomic_t| obj_count | プール内のオブジェクト数。|
|atomic_t| refcount | プールへの参照カウント。|
|struct tmem_hashbucket | hashbucket[256] | オブジェクトを保持するハッシュテーブル。|

`struct tmem_hashbucket`のメンバは以下です。
|型 |メンバ |概要|
|---|---|---
|struct ro_root| obj_rb_root |オブジェクトを保持する赤黒木の根ノード。|
|spinlock_t |lock | 赤黒木に対するロック。|

あるプールの中では、 tmemはオブジェクトという単位で管理され、赤黒木につながれています。これを表現するのが構造体`struct tmem_obj`です。主要なメンバを以下に示します。

|型  |メンバ |概要 |
|---|---|---|
|struct tmem_oid  |oid  |オブジェクトID。|
|struct tmem_pool * |pool  |親となるプールへのポインタ。|
|struct rb_node | rb_tree_node| オブジェクトが所属する赤黒木のノード。 |
|struct tmem_objnode *| objnode_tree_root | objnodeの木の根ノードへのポインタ。|
|unsigned int | objnode_tree_height | objnodeの木の高さ。|
| unsigned long | objnode_count | objnodeの数。|
|long | pampd_count | pampdの数。|


新しい用語がいくつか出てきました。pampdというのはPage-Accessible Memory Page-Descriptorの略で、実際にページのデータを保持しています。これらはradix treeのような木で管理されていて、handleのインデックスを6ビットずつに区切って、それをキーとして子をたどっていきます。一つのpampdは、それぞれradix treeの葉に対応します。このradix treeの中間ノードにあたるのがobjnodeで、`struct tmem_objnode`という構造体で表現されます。

|型  |メンバ |概要 |
|---|---|---|
|struct tmem_obj *|obj  |親となるオブジェクトへのポインタ。|
|void * |slots[64]  |radix treeにおける子へのポインタを保持した配列。|
| unsigned int | slots_in_use | 使用済みのスロットの数。|

また、オブジェクトID（`struct tmem_oid`が表現）は192bitの整数で、ファイルシステム内のファイルに対して一意なIDをつけられるように大きくとられています。

### tmem_put
`tmem_put()`は、その名の通りデータをtmemにputする関数です。関数は簡単に書くと以下のようになります。
```c:drivers/staging/zcache/tmem.c
int tmem_put(struct tmem_pool *pool, struct tmem_oid *oidp, uint32_t index,
		char *data, size_t size, bool raw, bool ephemeral)
{
	struct tmem_obj *obj = NULL, *objfound = NULL, *objnew = NULL;
	void *pampd = NULL, *pampd_del = NULL;
	int ret = -ENOMEM;
	struct tmem_hashbucket *hb;

	hb = &pool->hashbucket[tmem_oid_hash(oidp)];
	spin_lock(&hb->lock);
	obj = objfound = tmem_obj_find(hb, oidp);
	if (obj != NULL) {
		pampd = tmem_pampd_lookup_in_obj(objfound, index);
		if (pampd != NULL) {
			pampd_del = tmem_pampd_delete_from_obj(obj, index);
			(*tmem_pamops.free)(pampd, pool, oidp, index);
			if (obj->pampd_count == 0) {
				objnew = obj;
				objfound = NULL;
			}
			pampd = NULL;
		}
	} else {
		obj = objnew = (*tmem_hostops.obj_alloc)(pool);
		tmem_obj_init(obj, hb, pool, oidp);
	}
	pampd = (*tmem_pamops.create)(data, size, raw, ephemeral,
					obj->pool, &obj->oid, index);
	ret = tmem_pampd_add_to_obj(obj, index, pampd);
	spin_unlock(&hb->lock);
	return ret;
}
```
突然ですが、ページをtmemにputする際、すでにそのページに対応するhandleと同一のhandleを持つオブジェクトがtmem内に存在していたらどうすればよいでしょうか？一般的には2つのアプローチが考えられます。

- すでにtmem内に保存されているデータを、新しいデータで上書きする
- すでにtmem内に保存されているデータをフラッシュし、後続のget命令ではアクセスできないようにする

前者と後者の違いがわかりにくいと思いますが、コードを読むと後者は「そのデータを誰も指さないようにする」ということだと思います。tmem/zcacheは後者のアプローチをとっています。いずれにせよ、実際のputの前に、一度tmem内に同じhandleのオブジェクトがあるか探す必要があります。

```c:drivers/staging/zcache/tmem.c
	hb = &pool->hashbucket[tmem_oid_hash(oidp)];
	spin_lock(&hb->lock);
	obj = objfound = tmem_obj_find(hb, oidp);
```
tmemのプール内では、オブジェクトは`tmem_hashbucket`というバケットからなるハッシュテーブルで管理されていて、各バケットは赤黒木でオブジェクトを検索できるようになっていたのでした。このコードでは、これから保存したいデータに対応するオブジェクトがもしすでに存在するとしたらここにある、というバケットを取得し、実際にオブジェクトがあるかどうかを調べています。

ここでもしオブジェクトが見つかれば、中のデータをフラッシュする必要があります。見つからなければ、データをしまうためのオブジェクトを新たに作成する必要があります。次の分岐がその処理にあたります。

```c:drivers/staging/zcache/tmem.c
	if (obj != NULL) {
		pampd = tmem_pampd_lookup_in_obj(objfound, index);
		if (pampd != NULL) {
			pampd_del = tmem_pampd_delete_from_obj(obj, index);
			(*tmem_pamops.free)(pampd, pool, oidp, index);
			if (obj->pampd_count == 0) {
				objnew = obj;
				objfound = NULL;
			}
			pampd = NULL;
		}
	} else {
		obj = objnew = (*tmem_hostops.obj_alloc)(pool);
		tmem_obj_init(obj, hb, pool, oidp);
	}
```

オブジェクトが見つかった場合の処理について見ていきます。まずはオブジェクト内でさらに該当するインデックスのデータが保持されているか調べます。この検索部分が`tmem_pampd_lookup_in_obj()`ですが、これも`tmem.c`に実装されていて、tmem内のオブジェクトが構造体`tmem_objnode`でradix treeを使ってページを管理していることを念頭におけば実装は難しくないので、省略します。

ここでさらにオブジェクトが該当するインデックスのデータを保持していることがわかった場合、pampdからデータをフラッシュする必要があります。`tmem_pampd_delete_from_obj()`では、radix treeをたどって該当のpampdからデータをフラッシュします（pampdがNULLを指すようにします）。その後、最終的には`kmem_cache_free()`によって`objnode`が解放されます。

オブジェクトが見つからなかった場合の処理を見ていきます。この場合、まずオブジェクト用のメモリ領域を確保します。`tmem_hostops`はのちに出てくる`tmem_pamops`と同様にカーネルの初期化時に登録されるメソッド群です。`*tmem_hostops.obj_alloc()`に登録されている`zcache_obj_alloc()`は単純な`malloc()`ではなくpreloadという仕組みを用いており、別のタイミングでCPUごとに確保しておいたオブジェクトをもらってくるような実装になっています。`tmem_obj_init()`は作成したオブジェクトをプール内の赤黒木に登録する処理などを行います。

いずれの場合も、最終的に変数`objnew`がこれからしまうページに対応するオブジェクトを保持しています。オブジェクトを作成したら、次はオブジェクト内にページのデータをしまうことになります。これは`tmem_pamops.create()`に任されています。`create`メンバに登録されているのは`zcache_pampd_create()`という関数で、`drivers/staging/zcache/zcache-main.c`に実装があります。これを見ていきましょう。

`tmem_put()`から`zcache_pampd_create()`を呼び出すときに4番目に`ephemeral`という引数を渡していますが、`zcache_pampd_create()`はこれによって処理を大きく2つに分けます。引数`ephemeral`の意味を理解するために、PAM (Page-Accessible Memory)について少し補足します。PAMという概念が導入されたとき、開発者はephemeral（短命である）か、persistent（長く存続する）か2通りの使い方があると考えていたようです。PAMがもしephemeralであった場合、putは必ず成功しますが、getのときにはすでにputされた内容が失われていることも考えられ、失敗する可能性があります。一方persistentなPAMはサイズが決まっているためputは失敗する可能性がありますが、putが成功していればgetは成功します。ここで関数の中身に戻ると、`zcache_pampd_create()`はここで使っているPAMがephemeralであるかどうかで処理を分岐させている、ということになります。本記事冒頭で説明したとおり、cleancacheはephemeralです。したがって、ここではそちらの処理を見ていくことにします。ちなみにpersistentなPAMは、frontswapという別の機構で使用されています。

```c:drivers/staging/zcache/zcache-main.c
	if (eph) {
		ret = zcache_compress(page, &cdata, &clen);
		if (ret == 0)
			goto out;
		if (clen == 0 || clen > zbud_max_buddy_size()) {
			zcache_compress_poor++;
			goto out;
		}
		pampd = (void *)zbud_create(client_id, pool->pool_id, oid,
						index, page, cdata, clen);
	}
out:
	return pampd;
```

PAMがephemeralである場合、すぐに`zcache_compress()`が呼び出されます。これはすでに説明しましたね。ここではデータを圧縮してからオブジェクトに格納しようとしています。`cdata`が圧縮後のメモリ領域を指し、`clen`には圧縮後のバイト数が格納されているということも思い出してください。

`zcache_compress()`から戻ったあとのコードを見ましょう。2つのif文は、いずれもエラー処理を行っています。`zcache_compress()`は、成功すると1を返しますから、1つ目のif文は圧縮が成功すると飛ばされます。`zbad_max_buddy_size()`は、zbudの片割れがzbpg内で持ってよいデータ領域の最大サイズを返す関数です。つまり2つ目のif文では、望ましいサイズにまで圧縮が行われたかをチェックしています。

チェックを通過すると、次に`zbud_create()`によってzbudを作成し、zbpgに登録します。これもすでに説明しました。さらに`zbud_create()`は、新しく作成したbuddyのヘッダ`zbud_hdr`へのポインタを返すのでした。データ構造の節で、pampdはデータに対応すると説明しましたが、正確には`zbud_hdr`を通してデータと結びついていたということがここで分かります。

`zcache_pampd_create()`から戻りましょう。ここまでで、オブジェクトを適切に初期化し、データを圧縮し、pampdを作成してデータを紐付けるところまで終えています。最後に`tmem_pampd_add_to_obj()`を呼び出して、pampdとオブジェクトを対応させれば完成です。この関数は、radix treeをたどって適切な葉ノードにpampdを追加します。必要があれば木の高さを増やす必要があるため、若干コードが長くなっていますが、やっていることは単純なので省略します。

以上で`tmem_put()`の説明を終わります。かなり長くなりましたので、ここで説明した範囲の関数のコールグラフをつけておきます。

```mermaid
graph TB
	tmem_put-->tmem_obj_find
	tmem_put-->A{if obj != NULL}
	A-->|True| B[ ]
	B --> tmem_pampd_lookup_in_obj
	B --> C{if pampd != NULL}
	C -->|True| tmem_pampd_delete_from_obj
	A-->|False| D[ ]
	D-->zcache_obj_alloc
	D-->zcache_obj_init
	tmem_put-->E[zcache_pampd_create]
	E-->zcache_compress
	E-->zbud_create
	tmem_put-->tmem_pampd_add_to_obj
```

## zcacheによるcleancache実装
ようやくcleancacheにたどり着きました。cleancache機構は、`drivers/staging/zcache/zcache-main.c`の`zcache_xx`という関数群が実現していますが、その本質はtmemであり、ここまでの実装を理解していればそこまで難しくありません。ここではcleancacheにページを退避する`zcache_put_page()`をとりあげます。

### zcacne_put_page
関数は簡単に書くと以下のようになります。
```c:zcache-main.c
static int zcache_put_page(int cli_id, int pool_id, struct tmem_oid *oidp,
				uint32_t index, struct page *page)
{
	struct tmem_pool *pool;
	int ret = -1;

	pool = zcache_get_pool_by_id(cli_id, pool_id); 
	if (!zcache_freeze && zcache_do_preload(pool) == 0) {
		ret = tmem_put(pool, oidp, index, (char *)(page),
				PAGE_SIZE, 0, is_ephemeral(pool));
		zcache_put_pool(pool);
		preempt_enable_no_resched();
	} else {
		zcache_put_to_flush++;
		if (atomic_read(&pool->obj_count) > 0)
			(void)tmem_flush_page(pool, oidp, index);
		zcache_put_pool(pool);
	}
out:
	return ret;
}
```

この関数に入るときには、IRQが禁止されている必要があります。これは後述する`zcache_preload()`がメモリ確保を伴うためだと思われます。

この関数では、まずデータを対比するプールを`zcache_get_pool_by_id()`によって取得します。プールはプールIDで指定できるはずなのに、`cli_id`という引数も指定されているのはなぜ？と思うかもしれませんが、実はzcacheはKVM環境を想定してプールのさらに上にクライアントという分類を持っており、各クライアントが独立してプール群を持つことができます。ここでは`LOCAL_CLIENT`という単一のクライアント（カーネルそのもの）しか扱わないので、特に気にする必要はありません。

`zcache_do_preload()`関数は、以降の処理で必要なメモリをこの段階で確保する（プリロードする）ための関数で、以降の処理の実行中に直接`malloc`を行わせないようにしています。プリロードの対象となるのは、

- 物理ページ（`zbud_create()`が使用）
- `tmem_obj`構造体（`zcache_obj_alloc()`が使用）
- `tmem_objnode`構造体（`zcache_objnode_alloc()`が使用）

で、それぞれ`zcache_preload`構造体の`page`メンバ、`obj`メンバ、`objnodes`メンバによって指されます。`zcache_preload`構造体はCPUごとに用意され、CPUごとに割り当てできるようになっています。

`zcache_do_preaload()`の内部ではページフレームアロケータ・スラブアロケータによる割り当てが行われています。引数として`pool`が渡されていますが、内部では使われていないので意図はわかりません。

いずれにせよ、プリロードが成功すれば次は`tmem_put()`が呼び出され、データをtmemのプールに退避します。データの圧縮などもここで行われているのでした。後続の`zcache_put_pool()`は、プールへのデータ退避完了による参照カウントの減算を行っています。

プリロードが失敗した場合、メモリが足りないので`tmem_put()`を読んでもデータの退避ができません。この場合、`tmem_put()`を呼び出すことはなく、`tmem_put()`が行っていた重複オブジェクトからのデータのフラッシュとオブジェクトの解放だけを`tmem_flush_page()`を呼び出して行います。この場合、`ret`には-1が格納されたままなので、`zcache_put_page()`の呼び出し元はエラーを検出することができます。

以上が`zcache_put_page()`の実装です。これらの関数は、`zcache_cleancache_xx()`というラッパー関数を通して`cleancache_ops`に登録され（フロントエンド実装の節を参照）、cleancacheから呼び出されて使用されます。

<a id="#reference"></a>
# 参考文献
<a id="#bib1"></a>
- Bovet, Daniel P., Cesati, Marco.  *Understanding the Linux Kernel, Third Edition*. O’Reilly Media, Inc, 2006.
<a id="#bib2"></a>
- 高橋 浩和、小田 逸郎、山幡 為佐久。『Linuxカーネル2.6解読室』。ソフトバンククリエイティブ、2006。
<a id="#bib3"></a>
- Love, Robert. *Linux Kernel Development, Third Edition*. Addison-Wesley Professional, 2010.