2018年8月30日（木）
第12回ICN研究会ワークショップ
Ceforeで
キャッシュプラグイン
csmgrdは起動時に使用するキャッシュプラグインを指定
• Cache plugin: キャッシュデータ保存方式
• Cache algorithm: キャッシュ選択/置換アルゴリズム
csmgrd
File System Cache
Memory Cache
Cache Plugin X
Cache Plugin Y
Cache Plugin
LRU
Cache algorithm X
Cache algorithm
LFU
FIFO
開発者は独自のCache
Plugin/Algorithmを実装可能
2018/8/30 (木)
第12回 ICN研究会ワークショップ ハンズオン
csmgrd.conf
CACHE_TYPE=
memory
CACHE_ALGORITHM=
libcsmgrd_fifo
設定ファイルから
利用するプラグイン・
ライブラリを指定
ハンズオンの目標
キャッシュアルゴリズムFIFOを自作してみよう！
csmgrd
File System Cache
Memory Cache
Cache Plugin X
Cache Plugin Y
Cache Plugin
LRU
Cache algorithm X
Cache algorithm
LFU
FIFO
開発者は独自のCache
Plugin/Algorithmを実装可能
2018/8/30 (木)
第12回 ICN研究会ワークショップ ハンズオン
csmgrd.conf
CACHE_TYPE=
memory
CACHE_ALGORITHM=
libcsmgrd_fifo
設定ファイルから
利用するプラグイン・
ライブラリを指定
• 最初に入ったエントリーが最初に削除される方式
FIFO (first-in, first-out) の概要
head
tail
ccn:/E.txt
ccn:/D.txt
ccn:/C.txt
ccn:/B.txt
ccn:/F.txt
FIFO (capacity: 5)
ccn:/A.txt
ccn:/F.txt
cache
remove
キャッシュがいっぱいになると
head
からエントリーが削除されて
tail に新しいエントリーが追加される
• 配列にデータを保存
• 置換の度にエントリ
用のメモリを確保・
解放しなくていい
• 置換時は head が示す
エントリを削除
• 置換後は head を
１だけ進める
今回実装する FIFO のデータ構造
0
1
2
3
4
FIFO (capacity: 5)
ccn:/A.txt ccn:/B.txt ccn:/C.txt ccn:/D.txt ccn:/E.txt
head=0
0
1
⋯
⋯
ccn:/F.txt ccn:/B.txt
head=1
ccn:/F.txt
cache
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 のソースコード
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
ソースコード・ヘッダーファイルの作成
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, 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() { 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) {
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) {
/* 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; } /*---Miss API ---*/ void miss(unsigned char* key, int key_len) {
fprintf(stderr, "miss¥n"); return; } /*---Status API ---*/ void status(void* arg) {
return; }
init() 関数
destroy() 関数
insert() 関数
erase() 関数
hit() 関数
miss() 関数
status() 関数
各関数の概要
関数名
引数
概要
init
• capacity: キャッシュ容量。
• store: プラグインにキャッシュ追加
をさせるための関数ポインタ。
• remove: プラグインにキャッシュ削
除をさせるための関数ポインタ
キャッシュアルゴリズムライブラリ初期化用の関数。
プラグインの初期化時（csmgrdの起動時）に呼び出される。
destroy
ライブラリ終了時の処理用の関数。
プラグインの終了時に呼び出される。
insert
• entry: キャッシュ対象のコンテンツ
情報（CsmgrdT_Content_Entry 構造
体）。
プラグインがコンテンツをキャッシュしようとするときに呼
び出される関数。
ライブラリは自身のデータ構造にコンテンツの情報を登録し、
store 関数を呼び出してキャッシュする。
キャッシュがいっぱいのときは削除するコンテンツを決定し、
remove 関数を呼び出してキャッシュから削除する。
erase
• key: 削除されたコンテンツの name
• key_len: name 長
プラグインが期限切れなどの理由でキャッシュからコンテン
ツを削除したときに、削除したコンテンツを通知する関数。
ライブラリは自身のデータ構造からコンテンツの情報を削除
する（remove 関数を呼び出す必要はない）。
hit
• key: ヒットしたコンテンツの name
• key_len: name 長
キャッシュヒット時に呼び出される関数。
miss
• 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[]
cefnetdから受信したメッセージ。
msg_len
uint16_t
メッセージ長。
pay_len
uint16_t
ペイロード長。
cache_time
uint64_t
キャッシュ時間。
expiry
uint64_t
キャッシュ期限。
有用な関数
関数名
引数
概要
cef_lhash_tbl_create
• capacity: 容量
文字列をキーとしてvoidのポインタを返すハッシュ
テーブルを作成する。ハッシュテーブルを表す構造
体CefT_Hash_Handleを返す。
cef_lhash_tbl_destroy
• CefT_Hash_Handle ht:
ハッシュテーブル
ハッシュテーブルの後処理を行う。
cef_lhash_tbl_item_get
• CefT_Hash_Handle ht
• key: キー
• key_len: キー長
ハッシュテーブルhtからkeyをキーとしてデータを
検索し、voidのポインタを返す。
cef_lhash_tbl_item_set
• CefT_Hash_Handle ht
• key: キー
• key_len: キー長
• void* value: 登録する値
ハッシュテーブルhtに、keyをキーとするデータ
valueを登録する。
cef_lhash_tbl_item_remove
• CefT_Hash_Handle ht
• key: キー
• key_len: キー長
ハッシュテーブルhtから、keyをキーとするデータ
を削除する。
csmgrd_name_chunknum_
concatenate
• name: 名前
• name_len: 名前長
• chunk_num: チャンク番号
• dst: 書込先
名前と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, 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() { 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) {
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) {
/* 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; } /*---Miss API ---*/ void miss(unsigned char* key, int key_len) {
fprintf(stderr, "miss¥n"); return; } /*---Status API ---*/ void status(void* arg) {
return; }
