第 12 回 ICN 研究会ワークショップ Cefore で キャッシュプラグイン開発 2018 年 8 月 30 日 ( 木 )
キャッシュプラグイン csmgrd は起動時に使用するキャッシュプラグインを指定 Cache plugin: キャッシュデータ保存方式 Cache algorithm: キャッシュ選択 / 置換アルゴリズム Cache Plugin Cache algorithm csmgrd csmgrd.conf CACHE_TYPE=memory CACHE_ALGORITHM= libcsmgrd_fifo File System Cache Memory Cache Cache Plugin X Cache Plugin Y LRU LFU FIFO Cache algorithm X 設定ファイルから利用するプラグイン ライブラリを指定 開発者は独自の Cache Plugin/Algorithm を実装可能 2018/8/30 ( 木 )
ハンズオンの目標 キャッシュアルゴリズム FIFO を自作してみよう! Cache Plugin Cache algorithm csmgrd csmgrd.conf CACHE_TYPE=memory CACHE_ALGORITHM= libcsmgrd_fifo File System Cache Memory Cache Cache Plugin X Cache Plugin Y LRU LFU FIFO Cache algorithm X 設定ファイルから利用するプラグイン ライブラリを指定 開発者は独自の Cache Plugin/Algorithm を実装可能 2018/8/30 ( 木 )
FIFO (first-in, first-out) の概要 最初に入ったエントリーが最初に削除される方式 ccn:/f.txt FIFO (capacity: 5) tail head cache ccn:/f.txt ccn:/e.txt ccn:/d.txt ccn:/c.txt ccn:/b.txt ccn:/a.txt remove キャッシュがいっぱいになると head からエントリーが削除されて tail に新しいエントリーが追加される
今回実装する FIFO のデータ構造 配列にデータを保存 置換の度にエントリ用のメモリを確保 解放しなくていい head=0 FIFO (capacity: 5) 0 1 2 3 4 ccn:/a.txt ccn:/b.txt ccn:/c.txt ccn:/d.txt ccn:/e.txt 置換時は head が示すエントリを削除 置換後は head を 1 だけ進める ccn:/f.txt cache 新しくエントリをキャッシュ head=1 0 1 ccn:/f.txt ccn:/b.txt remove
cefore のファイル構造 cefore-0.7.2a/: 親ディレクトリ configure.ac: ライブラリを make するときに編集が必要 src/ csmgrd/ plugin/ filesystem_cache/, mem_cache/ : csmgrd プラグインのディレクトリ lib/ Makefile.am: ライブラリを make するときに編集が必要 lru/: LRU のライブラリ lru.c, lru.h, Makefile.am: LRU のソースコード /src/csmrd/plugin/lib 下にキャッシュ置換ライブラリを作成
cefore のファイル構造 cefore-0.7.2a/: 親ディレクトリ configure.ac: ライブラリを make するときに編集が必要 src/ csmgrd/ plugin/ filesystem_cache/, mem_cache/ : csmgrd プラグインのディレクトリ lib/ Makefile.am: ライブラリを make するときに編集が必要 lru/: LRU のライブラリ lru.c, lru.h, Makefile.am: LRU のソースコード wsfifo/ wsfifo.c 今回作成するファイル wsfifo.h Makefile.am
実装手順 ソースコード ヘッダーファイルの作成 src/csmgrd/plugin/lib/wsfifo/wsfifo.c, wsfifo.h 必要な API の実装 init(), destroy(), insert(), erase(), hit(), miss(), status() おまじない src/csmgrd/plugin/lib/wsfifo/makefile.am src/csmgrd/plugin/lib/makefile.am configure.ac ビルド autoconf automake make sudo make install
ソースコード ヘッダーファイルの作成 cefore:~/cefore-0.7.2a$ ls LICENSE Makefile.in aclocal.m4 autotools config.h.in configure.ac src utils Makefile.am README.md apps config configure m4 tools cefore:~/cefore-0.7.2a$ cd src/csmgrd/plugin/lib cefore:~/cefore-0.7.2a/src/csmgrd/plugin/lib$ ls fifo lfu lru Makefile.in Makefile.am cefore:~/cefore-0.7.2a/src/csmgrd/plugin/lib$ mkdir wsfifo cefore:~/cefore-0.7.2a/src/csmgrd/plugin/lib$ cp lru/makefile.am wsfifo cefore:~/cefore-0.7.2a/src/csmgrd/plugin/lib$ cd wsfifo cefore:~/cefore-0.7.2a/src/csmgrd/plugin/lib/wsfifo$ touch wsfifo.c wsfifo.h cefore:~/cefore-0.7.2a/src/csmgrd/plugin/lib/wsfifo$ ls Makefile.am wsfifo.c wsfifo.h ビルド時に編集 ビルド時に編集 今回作成 編集するファイル
ヘッダーファイル wsfifo.h #include <stdio.h> #include <stdlib.h> #include <csmgrd/csmgrd_plugin.h> Init API int /* If the error occurs, this value is a negative value */ init ( int capacity, /* Maximum number of entries that can be */ /* listed (it is the same value as the */ /* maximum value of the cache table) */ int (*store)(csmgrdt_content_entry*), /* store a content entry API */ void (*remove)(unsigned char*, int) /* remove a content entry API */ ); Destroy API void destroy ( void ); Insert API void insert ( CsmgrdT_Content_Entry* entry /* content entry */ ); Erase API void erase ( unsigned char* key, /* key of content entry removed from cache */ /* table */ int key_len /* length of the key */ ); Hit API void hit ( unsigned char* key, /* key of the content entry hits in the */ /* cache table */ int key_len /* length of the key */ ); Miss API void miss ( unsigned char* key, /* key of the content entry fails to hit */ /* in the cache table */ int key_len /* length of the key */ ); Status API void status ( void* arg /* state information */ ); init() 関数 destroy() 関数 insert() 関数 erase() 関数 hit() 関数 miss() 関数 status() 関数
ソースコード wsfifo.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <csmgrd/csmgrd_plugin.h> #include <cefore/cef_hash.h> /***** structure for listing content entries *****/ typedef struct _FifoT_Entry { unsigned char key[csmgrdc_key_max]; /* key of content entry */ int key_len; /* length of key */ int valid; FifoT_Entry; /***** State Variables *****/ static int cache_cap = 0; static int (*store_api)(csmgrdt_content_entry*); static void (*remove_api)(unsigned char*, int); static int fifo_head; static int cache_count; static FifoT_Entry* cache_entry_list; static CefT_Hash_Handle lookup_table; Init API int init ( int capacity, init() 関数 int (*store)(csmgrdt_content_entry*), void (*remove)(unsigned char*, int) ) { /* Check arguments */ if ((capacity < 1) (store == NULL) (remove == NULL)) { fprintf (stderr, "Invalid Arguments. n"); return (-1); /* Initialize variables */ cache_cap = capacity; store_api = store; remove_api = remove; fifo_head = 0; cache_count = 0; cache_entry_list = (FifoT_Entry*) calloc(cache_cap, sizeof(fifot_entry)); memset(cache_entry_list, 0, sizeof(fifot_entry) * cache_cap); lookup_table = cef_lhash_tbl_create(cache_cap); return (0); Destroy API void destroy() { destroy() 関数 fifo_head = 0; cache_count = 0; cache_cap = 0; store_api = NULL; remove_api = NULL; free(cache_entry_list); cef_lhash_tbl_destroy(lookup_table); Insert API void insert(csmgrdt_content_entry* entry) { insert() 関数 unsigned char key[csmgrdc_key_max]; int key_len; FifoT_Entry* tmp_entry; tmp_entry = &cache_entry_list[fifo_head]; /* When cache is full, remove an entry */ if (tmp_entry->valid) { cef_lhash_tbl_item_remove(lookup_table, tmp_entry->key, tmp_entry->key_len); (*remove_api)(tmp_entry->key, tmp_entry->key_len); memset(tmp_entry, 0, sizeof(fifot_entry)); cache_count--; /* Cache an entry */ key_len = csmgrd_name_chunknum_concatenate( entry->name, entry->name_len, entry->chnk_num, key); tmp_entry->key_len = key_len; memcpy(tmp_entry->key, key, key_len); tmp_entry->valid = 1; cef_lhash_tbl_item_set(lookup_table, tmp_entry->key, tmp_entry->key_len, tmp_entry); (*store_api)(entry); cache_count++; /* Proceed a hand */ fifo_head++; if (fifo_head >= cache_cap) fifo_head = 0; Erase API void erase(unsigned char* key, int key_len) { erase() 関数 /* Remove an entry */ FifoT_Entry* entry = (FifoT_Entry*)cef_lhash_tbl_item_get(lookup_table, key, key_len); cef_lhash_tbl_item_remove(lookup_table, entry->key, entry->key_len); memset(entry, 0, sizeof(fifot_entry)); cache_count--; /***** Don't call remove_api because the entry is already removed *****/ // (*remove_api)(entry->key, entry->key_len); Hit API void hit(unsigned char* key, int key_len) { fprintf(stderr, "hit n"); return; hit() 関数 miss() 関数 Miss API void miss(unsigned char* key, int key_len) { fprintf(stderr, "miss n"); return; Status API void status(void* arg) { status() 関数 return;
各関数の概要 関数名引数概要 init capacity: キャッシュ容量 store: プラグインにキャッシュ追加をさせるための関数ポインタ remove: プラグインにキャッシュ削除をさせるための関数ポインタ キャッシュアルゴリズムライブラリ初期化用の関数 プラグインの初期化時 (csmgrd の起動時 ) に呼び出される destroy insert erase entry: キャッシュ対象のコンテンツ情報 (CsmgrdT_Content_Entry 構造体 ) key: 削除されたコンテンツの name key_len: name 長 ライブラリ終了時の処理用の関数 プラグインの終了時に呼び出される プラグインがコンテンツをキャッシュしようとするときに呼び出される関数 ライブラリは自身のデータ構造にコンテンツの情報を登録し store 関数を呼び出してキャッシュする キャッシュがいっぱいのときは削除するコンテンツを決定し remove 関数を呼び出してキャッシュから削除する プラグインが期限切れなどの理由でキャッシュからコンテンツを削除したときに 削除したコンテンツを通知する関数 ライブラリは自身のデータ構造からコンテンツの情報を削除する (remove 関数を呼び出す必要はない ) hit miss key: ヒットしたコンテンツの name key_len: name 長 key: ミスしたコンテンツの name key_len: name 長 キャッシュヒット時に呼び出される関数 キャッシュミス時に呼び出される関数
データ構造 CsmgrdT_Content_Entry 構造体 /src/csmgrd/include/csmgrd/csmgrd_plugin.h で定義 メンバー変数型概要 name unsigned char[] 受信したコンテンツの名前 name_len uint16_t コンテンツの名前長 chnk_num uint32_t チャンク番号 msg unsigned char[] msg_len uint16_t メッセージ長 cefnetd から受信したメッセージ pay_len uint16_t ペイロード長 cache_time uint64_t キャッシュ時間 expiry uint64_t キャッシュ期限 node struct in_addr IP アドレス
有用な関数 関数名引数概要 cef_lhash_tbl_create cef_lhash_tbl_destroy cef_lhash_tbl_item_get cef_lhash_tbl_item_set cef_lhash_tbl_item_remove csmgrd_name_chunknum_ concatenate capacity: 容量 CefT_Hash_Handle ht: ハッシュテーブル CefT_Hash_Handle ht key: キー key_len: キー長 CefT_Hash_Handle ht key: キー key_len: キー長 void* value: 登録する値 CefT_Hash_Handle ht key: キー key_len: キー長 name: 名前 name_len: 名前長 chunk_num: チャンク番号 dst: 書込先 文字列をキーとして void のポインタを返すハッシュテーブルを作成する ハッシュテーブルを表す構造体 CefT_Hash_Handle を返す ハッシュテーブルの後処理を行う ハッシュテーブル ht から key をキーとしてデータを検索し void のポインタを返す ハッシュテーブル ht に key をキーとするデータ value を登録する ハッシュテーブル ht から key をキーとするデータを削除する 名前と URL を接続したバイト列を作成し dst に書き込む dst に書き込んだ新たなバイト列の長さを int で返す エントリー CsmgrdT_Content_Entry の name と chnk_num からハッシュテーブル用のキーを作るのに有用
変数定義 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <csmgrd/csmgrd_plugin.h> #include <cefore/cef_hash.h> /***** structure for listing content entries *****/ typedef struct _FifoT_Entry { unsigned char key[csmgrdc_key_max]; /* key of content entry */ int key_len; /* length of key */ int valid; FifoT_Entry; /***** State Variables *****/ static int cache_cap = 0; static int (*store_api)(csmgrdt_content_entry*); static void (*remove_api)(unsigned char*, int); static int fifo_head; static int cache_count; static FifoT_Entry* cache_entry_list; static CefT_Hash_Handle lookup_table;
init() 関数 : 穴埋め問題 int init ( int capacity, int (*store)(csmgrdt_content_entry*), void (*remove)(unsigned char*, int) ) { /* Check arguments */ if ((capacity < 1) (store == NULL) (remove == NULL)) { fprintf (stderr, "Invalid Arguments. n"); return (-1); /* Initialize variables */ cache_cap = capacity; store_api = store; remove_api = remove; fifo_head = 0; cache_count = 0; cache_entry_list = (FifoT_Entry*) calloc(cache_cap, sizeof(fifot_entry)); memset(cache_entry_list, 0, sizeof(fifot_entry) * cache_cap); lookup_table = cef_lhash_tbl_create(cache_cap); return (0);
init() 関数 : 答え int init ( int capacity, int (*store)(csmgrdt_content_entry*), void (*remove)(unsigned char*, int) ) { /* Check arguments */ if ((capacity < 1) (store == NULL) (remove == NULL)) { fprintf (stderr, "Invalid Arguments. n"); return (-1); /* Initialize variables */ cache_cap = capacity; store_api = store; remove_api = remove; fifo_head = 0; cache_count = 0; cache_entry_list = (FifoT_Entry*) calloc(cache_cap, sizeof(fifot_entry)); memset(cache_entry_list, 0, sizeof(fifot_entry) * cache_cap); lookup_table = cef_lhash_tbl_create(cache_cap); return (0);
destroy() 関数 void destroy() { fifo_head = 0; cache_count = 0; cache_cap = 0; store_api = NULL; remove_api = NULL; free(cache_entry_list); cef_lhash_tbl_destroy(lookup_table);
insert() 関数 : 穴埋め問題 void insert(csmgrdt_content_entry* entry) { unsigned char key[csmgrdc_key_max]; int key_len; FifoT_Entry* tmp_entry; tmp_entry = &cache_entry_list[fifo_head]; /* When cache is full, remove an entry */ if (tmp_entry->valid) { cef_lhash_tbl_item_remove(lookup_table, tmp_entry->key, tmp_entry->key_len); (*remove_api)(tmp_entry->key, tmp_entry->key_len); memset(tmp_entry, 0, sizeof(fifot_entry)); cache_count--; /* Cache an entry */ key_len = csmgrd_name_chunknum_concatenate( entry->name, entry->name_len, entry->chnk_num, key); tmp_entry->key_len = key_len; memcpy(tmp_entry->key, key, key_len); tmp_entry->valid = 1; cef_lhash_tbl_item_set(lookup_table, tmp_entry->key, tmp_entry->key_len, tmp_entry); (*store_api)(entry); cache_count++; /* Proceed a hand */ fifo_head++; if (fifo_head >= cache_cap) fifo_head = 0;
insert() 関数 : 答え void insert(csmgrdt_content_entry* entry) { unsigned char key[csmgrdc_key_max]; int key_len; FifoT_Entry* tmp_entry; tmp_entry = &cache_entry_list[fifo_head]; /* When cache is full, remove an entry */ if (tmp_entry->valid) { cef_lhash_tbl_item_remove(lookup_table, tmp_entry->key, tmp_entry->key_len); (*remove_api)(tmp_entry->key, tmp_entry->key_len); memset(tmp_entry, 0, sizeof(fifot_entry)); cache_count--; /* Cache an entry */ key_len = csmgrd_name_chunknum_concatenate( entry->name, entry->name_len, entry->chnk_num, key); tmp_entry->key_len = key_len; memcpy(tmp_entry->key, key, key_len); tmp_entry->valid = 1; cef_lhash_tbl_item_set(lookup_table, tmp_entry->key, tmp_entry->key_len, tmp_entry); (*store_api)(entry); cache_count++; /* Proceed a hand */ fifo_head++; if (fifo_head >= cache_cap) fifo_head = 0;
erase() 関数 : 穴埋め問題 void erase(unsigned char* key, int key_len) { /* Remove an entry */ FifoT_Entry* entry = (FifoT_Entry*)cef_lhash_tbl_item_get( lookup_table, key, key_len); cef_lhash_tbl_item_remove(lookup_table, entry->key, entry->key_len); memset(entry, 0, sizeof(fifot_entry)); cache_count--; /***** Don't call remove_api because the entry is already removed *****/ // (*remove_api)(entry->key, entry->key_len);
erase() 関数 : 答え void erase(unsigned char* key, int key_len) { /* Remove an entry */ FifoT_Entry* entry = (FifoT_Entry*)cef_lhash_tbl_item_get( lookup_table, key, key_len); cef_lhash_tbl_item_remove(lookup_table, entry->key, entry->key_len); memset(entry, 0, sizeof(fifot_entry)); cache_count--; /***** Don't call remove_api because the entry is already removed *****/ // (*remove_api)(entry->key, entry->key_len);
hit(), miss(), status() 関数 void hit(unsigned char* key, int key_len) { fprintf(stderr, "hit n"); return; void miss(unsigned char* key, int key_len) { fprintf(stderr, "miss n"); return; void status(void* arg) { return;
ソースコード fifo.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <csmgrd/csmgrd_plugin.h> #include <cefore/cef_hash.h> /***** structure for listing content entries *****/ typedef struct _FifoT_Entry { unsigned char key[csmgrdc_key_max]; /* key of content entry */ int key_len; /* length of key */ int valid; FifoT_Entry; /***** State Variables *****/ static int cache_cap = 0; static int (*store_api)(csmgrdt_content_entry*); static void (*remove_api)(unsigned char*, int); static int fifo_head; static int cache_count; static FifoT_Entry* cache_entry_list; static CefT_Hash_Handle lookup_table; Init API int init ( int capacity, init() 関数 int (*store)(csmgrdt_content_entry*), void (*remove)(unsigned char*, int) ) { /* Check arguments */ if ((capacity < 1) (store == NULL) (remove == NULL)) { fprintf (stderr, "Invalid Arguments. n"); return (-1); /* Initialize variables */ cache_cap = capacity; store_api = store; remove_api = remove; fifo_head = 0; cache_count = 0; cache_entry_list = (FifoT_Entry*) calloc(cache_cap, sizeof(fifot_entry)); memset(cache_entry_list, 0, sizeof(fifot_entry) * cache_cap); lookup_table = cef_lhash_tbl_create(cache_cap); return (0); Destroy API void destroy() { destroy() 関数 fifo_head = 0; cache_count = 0; cache_cap = 0; store_api = NULL; remove_api = NULL; free(cache_entry_list); cef_lhash_tbl_destroy(lookup_table); Insert API void insert(csmgrdt_content_entry* entry) { insert() 関数 unsigned char key[csmgrdc_key_max]; int key_len; FifoT_Entry* tmp_entry; tmp_entry = &cache_entry_list[fifo_head]; /* When cache is full, remove an entry */ if (tmp_entry->valid) { cef_lhash_tbl_item_remove(lookup_table, tmp_entry->key, tmp_entry->key_len); (*remove_api)(tmp_entry->key, tmp_entry->key_len); memset(tmp_entry, 0, sizeof(fifot_entry)); cache_count--; /* Cache an entry */ key_len = csmgrd_name_chunknum_concatenate( entry->name, entry->name_len, entry->chnk_num, key); tmp_entry->key_len = key_len; memcpy(tmp_entry->key, key, key_len); tmp_entry->valid = 1; cef_lhash_tbl_item_set(lookup_table, tmp_entry->key, tmp_entry->key_len, tmp_entry); (*store_api)(entry); cache_count++; /* Proceed a hand */ fifo_head++; if (fifo_head >= cache_cap) fifo_head = 0; Erase API void erase(unsigned char* key, int key_len) { erase() 関数 /* Remove an entry */ FifoT_Entry* entry = (FifoT_Entry*)cef_lhash_tbl_item_get(lookup_table, key, key_len); cef_lhash_tbl_item_remove(lookup_table, entry->key, entry->key_len); memset(entry, 0, sizeof(fifot_entry)); cache_count--; /***** Don't call remove_api because the entry is already removed *****/ // (*remove_api)(entry->key, entry->key_len); Hit API void hit(unsigned char* key, int key_len) { fprintf(stderr, "hit n"); return; hit() 関数 miss() 関数 Miss API void miss(unsigned char* key, int key_len) { fprintf(stderr, "miss n"); return; Status API void status(void* arg) { status() 関数 return;
おまじない (1) 1. src/csmgrd/plugin/lib/lru の Makefile.am を wsfifo にコピー 2. コピーした Makefile.am の lru をすべて wsfifo に置換 3. libcef_wsfifo_la_sources で wsfifo.c wsfifo.h のみ指定 ( それ以外は削除 )
おまじない (2) wsfifo wsfifo wsfifo/makefile 3. src/csmgrd/plugin/lib の Makefile.am の SUBDIRS に wsfifo を追加 4. configure.ac の check csmgr というコメントがある箇所の下のリストに src/csmgrd/plugin/lib/wsfifo/makefile という一行を追加
リビルド 以下のコマンドを実行 1. autoconf 2. automake 3. make 4. sudo make install 5. sudo ldconfig 必要なら最初に make clean を実行 csmgrd.conf に自作アルゴリズムを指定 CACHE_ALGORITHM=libcsmgrd_wsfifo /usr/local/lib 中のファイル名と合わせる