狠狠撸

dm-thin実装調査
Akira Hayakawa
(@akiradeveloper)
2014/5/28
Tuesday, May 27, 2014

dm-thinとは？
? device-mapperターゲットの一種.
? device-mapper: ブロックレイヤの仮想
化技術
? Thin-Provisioningというストレージの仮
想化技術を実装する.

なぜ今,
dm-thinなのか
? 今流行りのDockerのイメージ管理に使っている.
? 使ってみた系ブログは数件あるけど, 実装を解説
しているブログが存在しない.
? dm-writeboost関係で良くメールしているJoe(RH)
が作ったコードを読みたい.
? 自分のコードを理解してもらうためにはまず相
手のコードを理解する. ( )

dm-thin 機能紹介
? Thin-Provioning: 仮想メモリのようなもの. 実際のブロック
をオンデマンドで割り当てる(例: 300GBのHDDしかない
けど, 300TBのストレージを仮想的に作り上げる). 物理が
足りなくなったらあとで継ぎ足す => スモールスタート可
能
? Snapshot: ある時点でのブロックのイメージを保存出来る.
保存したスナップショットに対する書き込み時にはCoW
が起こる. シンプロにおけるマッピングをそのまま流用し
て実現. dm-thinでは多段的スナップショットが可能.

dm-thin 用語紹介
? プール: 物理的なストレージを物理ブロック(64KB-1G)に分
割して, 仮想ブロックに割り当てる. 物理的なストレージは
data_devという.
? マッピング: 仮想ブロックがどの物理ブロックに対応してい
るか保存する. metadata_devの上に永続的に実装.
? thinデバイス: 仮想的なデバイス. プールから割り当てを行う.
? snapshotデバイス: 実装上はthinデバイス. thinデバイスをorigin
として派生する.

Snapshotにwriteしたら
CoWしたケース
論物
0 0
1 1
0 2
thin0
thin1snapshot
of thin0
(1) detain write
metadata_dev
(3) data copy
(2) alloc new block
W
(5) release write and ackcell
(4)remap

今回の焦点
? dm-thinに関わるコードは密度が濃い上に1
万行以上あるため, 完全理解は早々に断念.
? 幹(以下2点)に絞って読むことにする.
? (幹1) CoW時の動作
? (幹2) データ構造の関係

やったこと
1. Documentation/を読んだ.
2. ソースコードのコメントをざっくり読んだ.
3. Joeに何か実装メモないのって聞いたら「コード
のコメントがすべてだね. ところでおれ来週全休
するわ」
4. とりあえず動かすコードを書いてみて, ポイント
だけftrace使って処理を追ってみよう.

スクリプトはここで公開
https://github.com/akiradeveloper/thin-test

スクリプト(1)
pool作成 -> thinデバイス作成
# Need to zero the first 4k of metadata device
# to indicate "empty" metadata.
# Metadata is 48 bytes for each data block.
dd if=/dev/zero of=$metadata_dev bs=4k count=1
# Create /dev/mapper/pool
echo > $TRACE/trace
dmsetup create pool --table "0 `blockdev --getsz $data_dev` thin-pool $metadata_dev
$data_dev $data_block_size $low_water_mark"
cat $TRACE/trace > data/create-pool-ftrace
# Create a thin device
id0=0
echo > $TRACE/trace
dmsetup message /dev/mapper/pool 0 "create_thin $id0"
# Then activate
dmsetup create thin --table "0 $thindevsize thin /dev/mapper/pool $id0"
cat $TRACE/trace > data/create-thin-ftrace
$HEXDUMP /dev/mapper/thin > data/thin-dump # It's zeroed out on newly creating a thin dev

スクリプト(2)
スナップショット作成 -> ライト
# Create a snapshot (1->0)
# Need to suspend the parent thin device otherwise snapshot corrupts
id1=1
echo > $TRACE/trace
dmsetup suspend /dev/mapper/thin
dmsetup message /dev/mapper/pool 0 "create_snap $id1 $id0"
dmsetup resume /dev/mapper/thin
# Then activate
dmsetup create snap1 --table "0 $thindevsize thin /dev/mapper/pool $id1"
# echo 0 > $TRACE/tracing_on
cat $TRACE/trace > data/create-snap1-ftrace
echo > $TRACE/trace
dd if=/dev/urandom of=/dev/mapper/snap1 count=1
cat $TRACE/trace > data/snap1-cow-ftrace
$HEXDUMP /dev/mapper/snap1 > data/snap1-dump

CoW動作の関数トレース
あまり役に立たなかった
-> 5. 気合で読むしかない
# tracer: function_graph
#
# CPU DURATION FUNCTION CALLS
# | | | | | | |
3) | thin_map() {
3) | thin_bio_map.isra.40() {
3) 0.151 us | __check_holder();
3) | __add_holder() {
3) 0.030 us | __find_holder();
3) 0.307 us | }
3) 0.037 us | dm_bm_validate_buffer.isra.4();
3) | __add_holder() {
3) 0.277 us | }
3) 0.080 us | dm_bm_validate_buffer.isra.4();
3) | bl_up_read() {
3) 0.450 us | }
3) | bl_up_read() {
3) 0.407 us | }
3) | thin_defer_bio() {
3) + 17.630 us | wake_worker();
3) + 18.305 us | }
3) + 28.918 us | }
3) + 29.319 us | }
1) | do_worker() {
1) 0.365 us | process_prepared();
1) 0.162 us | process_prepared();
1) 0.038 us | thin_put();
1) | process_bio() {
1) + 15.402 us | bio_detain.isra.26();
...

(幹1) CoW時の動作
ポイント
? WorkQueueを使ってbioの遅延処理をしている. その関数で
あるdo_worker()が呼ばれた時にどういう状態かを追う.
? コードとしては, dm_kcopyd_copyの実装に似ている. リ
ストいじり + workerがリストを処理という実装パター
ン.
? bio prisonという実装を使って, bioを一旦留めておき, シン
プロのマッピングを変更したあとに新しいブロックにラ
イトするという処理をしている.

thin_map ->
deferred_biosいじり
r = dm_thin_find_block(td, block, 0, &result);
/*
* Note that we defer readahead too.
*/
switch (r) {
case 0:
if (unlikely(result.shared)) {
thin_defer_bio(tc, bio);
return DM_MAPIO_SUBMITTED;
}
static void thin_defer_bio(struct thin_c *tc, struct bio *bio)
{
spin_lock_irqsave(&pool->lock, flags);
bio_list_add(&pool->deferred_bios, bio);
spin_unlock_irqrestore(&pool->lock, flags);
wake_worker(pool);
}
static void do_worker(struct work_struct *ws)
{
process_prepared(pool, &pool->prepared_mappings, &pool->process_prepared_mapping);
process_prepared(pool, &pool->prepared_discards, &pool->process_prepared_discard);
process_deferred_bios(pool);
}
struct pool {
...
struct bio_list deferred_bios;
struct bio_list deferred_flush_bios;
struct list_head prepared_mappings;
struct list_head prepared_discards;
sharedの場合:
deferred_biosに
つないでworkerを叩き起こして抜ける.
DM_MAPIO_SUBMITTEDが上に返る.
このライトについては
prepared_*が入ってないので
この2つはスルーされる.
foregroundでlookupする.

(補足) dm_kcopyd_copyの
dispatch_job (リストいじり) + do_worker (リストの処理)
static void do_work(struct work_struct *work)
{
struct dm_kcopyd_client *kc = container_of(work,
struct dm_kcopyd_client, kcopyd_work);
struct blk_plug plug;
/*
* The order that these are called is *very* important.
* complete jobs can free some pages for pages jobs.
* Pages jobs when successful will jump onto the io jobs
* list. io jobs call wake when they complete and it all
* starts again.
*/
blk_start_plug(&plug);
process_jobs(&kc->complete_jobs, kc, run_complete_job);
process_jobs(&kc->pages_jobs, kc, run_pages_job);
process_jobs(&kc->io_jobs, kc, run_io_job);
blk_finish_plug(&plug);
}
static void dispatch_job(struct kcopyd_job *job)
{
struct dm_kcopyd_client *kc = job->kc;
atomic_inc(&kc->nr_jobs);
if (unlikely(!job->source.count))
push(&kc->complete_jobs, job);
else if (job->pages == &zero_page_list)
push(&kc->io_jobs, job);
else
push(&kc->pages_jobs, job);
wake(kc);
}
リスト(complete_jobs, io_jobs, pages_jobs)をいじってworker
を叩き起こして抜ける.
それぞれのリストに入ってるjobを処理する.
(順番がとても重要だとコメントに書いてある)

process_bio -> process_shared_bio
-> break_sharing
static void process_deferred_bios(struct pool *pool)
{
bio_list_init(&bios);
bio_list_merge(&bios, &pool->deferred_bios);
bio_list_init(&pool->deferred_bios);
while ((bio = bio_list_pop(&bios))) {
if (bio->bi_rw & REQ_DISCARD)
pool->process_discard(tc, bio);
else
pool->process_bio(tc, bio);
}
static void break_sharing(struct thin_c *tc, struct bio *bio, dm_block_t block,
struct dm_cell_key *key,
struct dm_thin_lookup_result *lookup_result,
struct dm_bio_prison_cell *cell)
{
r = alloc_data_block(tc, &data_block);
switch (r) {
case 0:
schedule_internal_copy(tc, block, lookup_result->block,
data_block, cell, bio);
static void process_bio(struct thin_c *tc, struct bio *bio)
{
r = dm_thin_find_block(tc->td, block, 1, &lookup_result);
switch (r) {
case 0:
if (lookup_result.shared) {
process_shared_bio(tc, bio, block, &lookup_result);
static void process_shared_bio(struct thin_c *tc, struct bio *bio,
dm_block_t block,
struct dm_thin_lookup_result *lookup_result)
{
struct dm_cell_key key;
/*
* If cell is already occupied, then sharing is already in the process
* of being broken so we have nothing further to do here.
*/
build_data_key(tc->td, lookup_result->block, &key);
if (bio_detain(pool, &key, bio, &cell))
return;
if (bio_data_dir(bio) == WRITE && bio->bi_iter.bi_size)
break_sharing(tc, bio, block, &key, lookup_result, cell);
deferred_biosからbiosに全部引っこ抜いて,
while文で回す(実装パターン)
bio_detain: このbioは, remap後に処理される必要
がある. それまでack返さない. ここで拘留
新しい物理ブロック(data_block)を拝受して,
その物理ブロックにcopyを行う.
一見重複っぽいが,
backgroundでも
ここでもう一度lookupが
行われる.
(意味はあとで分かる)

schedule_copy
-> (callback) prepared_remappingsいじり
schedule_copy
/*
* IO to pool_dev remaps to the pool target's data_dev.
*
* If the whole block of data is being overwritten, we can issue the
* bio immediately. Otherwise we use kcopyd to clone the data first.
*/
if (io_overwrites_block(pool, bio)) {
...
} else {
from.bdev = origin->bdev;
from.sector = data_origin * pool->sectors_per_block;
from.count = pool->sectors_per_block;
to.bdev = tc->pool_dev->bdev;
to.sector = data_dest * pool->sectors_per_block;
to.count = pool->sectors_per_block;
r = dm_kcopyd_copy(pool->copier, &from, 1, &to,
0, copy_complete, m);
static void copy_complete(int read_err, unsigned long write_err, void *context)
{
m->prepared = true;
__maybe_add_mapping(m);
}
static void __maybe_add_mapping(struct dm_thin_new_mapping *m)
{
if (m->quiesced && m->prepared) {
list_add_tail(&m->list, &pool->prepared_mappings);
wake_worker(pool);
}
}
ライトがブロック大(例:64KB)ならば, 新しいブ
ロックにそのままライトすれば良い. 省略
パーシャルならば, コピーしてから勾留中のbio
を流す. dm_kcopyd_copyでコピーする.
callback(copy_complete)でprepared_mappingを追
加する(__maybe_add_mapping)

もう一度do_worker ->
process_prepared_mappings
static void process_prepared_mapping(struct dm_thin_new_mapping *m)
{
bio = m->bio;
if (bio) {
bio->bi_end_io = m->saved_bi_end_io;
atomic_inc(&bio->bi_remaining);
}
/*
* Commit the prepared block into the mapping btree.
* Any I/O for this block arriving after this point will get
* remapped to it directly.
*/
r = dm_thin_insert_block(tc->td, m->virt_block, m->data_block);
/*
* Release any bios held while the block was being provisioned.
* If we are processing a write bio that completely covers the block,
* we already processed it so can ignore it now when processing
* the bios in the cell.
*/
if (bio) {
cell_defer_no_holder(tc, m->cell);
bio_endio(bio, 0);
} else
cell_defer(tc, m->cell);
}
/*
* This sends the bios in the cell back to the deferred_bios list.
*/
static void cell_defer(struct thin_c *tc, struct dm_bio_prison_cell *cell)
process_prepared_mappingの中で勾留中のbioを解
放(もう一度defereed_biosにつなぐ).
process_deferred_bios以下process_bioでもう一度
lookupが行われて, 見つかった新しい物理ページは
sharedでないのでライトしてack(拝承)して終わり
// 再掲
static void do_worker(struct work_struct *ws)
{
process_prepared(pool, &pool->prepared_mappings, &pool->process_prepared_mapping);
process_prepared(pool, &pool->prepared_discards, &pool->process_prepared_discard);
process_deferred_bios(pool);
}

(幹2) データ構造の関係
ポイント
? 細かいところは捨てて, lookupに関係す
る構造だけを読みとって満足する.
? データ構造の関係を見るには初期化の
コードを追うのが良い.

まずは
コメントを読んでみる
(dm-thin-metadata.c)
? (A) metadata管理構造:
? 512バイト以下(atomic writeのため)のスーパーブロック
? メタデータブロックのためのspace map
? データブロックのためのspace map
? Two-level btree. (thin dev id, virt block) -> (time, block)をマップする.
? (B) space mapは2つのbtreeを持つ:
? uint64_tをindex_entryにマップする. そこからポイントされるbitmapから, freeエントリ
がいくつかあるかなどが分かる.
? bitmapブロックはヘッダ(checksumあり)を持つ. そして, 残りのブロックは2bit-列であ
る. 値の0-2は単純にref countを表すが, 3は2より大きいことを表す.
? もしcountが2より大きい場合, ref countはsecond btree (block_address -> utin32_t ref
count) に格納される.

(A) metadata管理構造
space mapなど補助的な情報を使いながら,
マッピングを管理する
struct dm_pool_metadata {
struct hlist_node hash;
struct block_device *bdev;
struct dm_block_manager *bm;
struct dm_space_map *metadata_sm;
struct dm_space_map *data_sm;
struct dm_transaction_manager *tm;
struct dm_transaction_manager *nb_tm;
/*
* Two-level btree.
* First level holds thin_dev_t.
* Second level holds mappings.
*/
struct dm_btree_info info;
int dm_thin_find_block(struct dm_thin_device *td, dm_block_t block,
int can_block, struct dm_thin_lookup_result *result)
{
if (can_block) {
down_read(&pmd->root_lock);
info = &pmd->info;
} else if (down_read_trylock(&pmd->root_lock))
info = &pmd->nb_info;
else
return -EWOULDBLOCK;
if (pmd->fail_io)
goto out;
r = dm_btree_lookup(info, pmd->root, keys, &value);
pmd->infoを使ってlookupを行っている.
これが, マッピングを保存しているもっとも重要な構造に違
いない.Two-level btreeと書いてある.
今回は, bm (bm=block manager), metadata_sm, data_sm
(sm=space map), tm (tm=transaction manager)について関連を調
査する.
nb_* というのはnon-blockingのことらしいが, 性能のための実
装だろうから今回は無視する.

(B) space map
ブロックごとのref countを管理する
/*
* struct dm_space_map keeps a record of how many times each block in a device
* is referenced. It needs to be fixed on disk as part of the transaction.
*/
struct dm_space_map {
void (*destroy)(struct dm_space_map *sm);
int (*extend)(struct dm_space_map *sm, dm_block_t extra_blocks);
int (*get_nr_blocks)(struct dm_space_map *sm, dm_block_t *count);
int (*get_nr_free)(struct dm_space_map *sm, dm_block_t *count);
....
struct ll_disk {
struct dm_transaction_manager *tm;
struct dm_btree_info bitmap_info;
struct dm_btree_info ref_count_info;
load_ie_fn load_ie;
save_ie_fn save_ie;
init_index_fn init_index;
open_index_fn open_index;
struct sm_disk {
struct dm_space_map sm;
struct ll_disk ll;
};
struct sm_metadata {
struct dm_space_map sm;
struct ll_disk ll;
};
(想像. 詳しく読んでいない)
ll_disk (ll=low level)は実質的にデータを持っているところ.
space_mapは, これを利用して処理を行う.
ともに, 関数ポインタをメンバとして持っていて, sm_metadata向け, sm_disk向けの実装がある.
smが渡されたら, container_ofでsm_*を引いている.

初期化コード概要
? pool_ctrの下, dm_pool_metadataで初期
化を行っている.
? 本質的なところは,?
__create_persistent_data_object

__create_persistent_data_objects
(bm, sm * 2, tmを初期化する)
static int __create_persistent_data_objects(struct dm_pool_metadata *pmd, bool format_device)
{
int r;
pmd->bm = dm_block_manager_create(pmd->bdev, THIN_METADATA_BLOCK_SIZE << SECTOR_SHIFT,
THIN_METADATA_CACHE_SIZE,
r = __open_or_format_metadata(pmd, format_device);
}
static int __format_metadata(struct dm_pool_metadata *pmd)
{
int r;
r = dm_tm_create_with_sm(pmd->bm, THIN_SUPERBLOCK_LOCATION,
&pmd->tm, &pmd->metadata_sm);
if (r < 0) {
DMERR("tm_create_with_sm failed");
return r;
}
pmd->data_sm = dm_sm_disk_create(pmd->tm, 0);
r = dm_btree_empty(&pmd->info, &pmd->root);
pmd->bdevはmetadata_dev
block managerの実質はdm-bu?o. こ
れは, カーネル内でRAMキャッシュ
を明示的に管理するクラス.
pmd->metadata_smの初期化
関数ポインタを設定したりする.
pmd->tmの初期化(tm->bm, tm->sm
の初期化)
pmd->data_smの初期化

結果, こうなる
(関係図)
pmd->bdev
RAM
data_sm
metadata_sm
bm
sm
tm
bitmap_info
refcount_info
struct sm_metadata
dm_block_manager
(実質はdm_bu?o)
metadata_devへのr/wを担当
struct dm_pool_metadata (pmd)
info (btree)
tm
struct ll_disk
struct sm_disk

dm_transaction_manager
? space map (ref countを管理)とbm (r/wを行う)を持っている
? コメントを読む (dm-transaction-manager.h)
? 2-phaseコミットを行う:
? i) block managerは?ushを命じられる. そして, space mapの変更はdiskに
書かれる.
? ii) rootは最後にコミットされる. rootの先頭512Bしか使ってはならな
い. さもなくばpower-failureで死ぬ.
? どうやらマッピング情報などを正しい順序(まずはマッピングを作成し,
その後, 張り替える)で保存するためのものらしい(rootのコミットが張り
替えに相当する)

まとめ
? dm-thinについて, 以下の2点に絞ってコードリーディングを
行った.
? 1) CoW時の動作
? 2) データ構造の関係
? dm-thinは使うのは簡単だけど, コードを理解するのはとて
も難しいことが分かった.
? CoWの処理”は”とても美しい.
? さらに読み進めていくための叩き台を作ったはず.

今後
? この資料の英語化と公開. DM業界的に
は叩き台として嬉しいのでは.
? 階層化の機能をdm-thinに実装する気は
ないのかJoe聞いてみる.
? 階層化実装の観点からdm-thinをさらに
調査はあるかも.

狠狠撸

dm-thin-internal-ja

More Related Content

dm-thin-internal-ja