說工作中一個同事的精彩演算法。
我們在開發一個內核塊裝置的驅動，需要一塊記憶體記錄塊裝置的改變，假設一個塊裝置的大小是4k，每次發生改變就在記憶體對應bit位置1。這樣，1M記憶體就能記錄32G大小的塊裝置（1b-->4K, 1B-->32K, 1K-->32M, 4K-->128M ..）。我們把這塊記憶體叫做DBM(Disk Bitmap)。
DBM也需要定時或者其他方式觸發寫到磁盤上某塊空間，防止系統crash時，無法記錄改變。在內核裏寫磁盤，仍然是按照4K的塊大小去操作。也就是說128M的磁盤修改了一塊內容，就需要把它對應的4K DBM寫到磁盤裏。為了減少磁盤操作，我們一般只寫修改的DBM。
那麽問題來了，如何跟蹤哪些DBM被修改了呢？同時，如果DBM被修改，然後被flush到磁盤上，這個過程怎麽保證原子操作，也是一個麻煩的事情。
當時我的想法是，給DBM再設定一個bit位來記錄其改變，就是1個bit位對應4k的DBM的改變，然後每次遍歷DBM的bitmap來確定哪些DBM發生了變化，並寫入磁盤。但是如果原始磁盤容量太大的話（當時我們需要支持到TB級），這樣的遍歷效率就非常低，而且鎖的時間就會變得很長，這在內核裏是不可以接受的。
另外一個解決方法是，增加一個連結串列(struct list_head)或者hash表(hlist)，把變化過的dbm加到連結串列或者hash表裏，但是這樣在設定dbm bit的時候，需要驗證該dbm block是否已經在連結串列或者hash 表裏，這也是一筆開銷。
當時一個同事給了下面這個精彩的演算法，
假設我們的DBM是按照PAGE（4k）連續分配的，
struct dbm_record {
union {
struct {
uint64_t page_number;
struct page *page;
struct dbm_record *next;
};
char data<32>;
};
};
在每條dbm的記錄後面，增加一個next指標，當該dbm的block發生變化時，就把這條記錄加到一個連結串列裏，具體的操作就是
//當dbm_record->next不為空時，說明該dbm block已經被修改過(dirty)
#define dbm_record_is_dirt(dbm_record) (dbm_record->next != NULL)
static void __dbm_dirty_record(struct dbm *dbm, struct dbm_record *dbm_record)
{
//如果dbm block已經dirty了，不處理
if (dbm_record_is_dirt(dbm_record))
return;
//如果dbm block之前沒有被修改，那麽此次修改，就標記為dirty，把他加入到dirty dbm block的連結串列裏
if (dbm->last_dirty_record) {
dbm_record->next = dbm->last_dirty_record->next;
dbm->last_dirty_record->next = dbm_record;
dbm->last_dirty_record = dbm_record;
} else {
dbm->last_dirty_record = dbm_record;
dbm_record->next = dbm_record;
}
}
//在dbm裏設定被修改標誌位
int dbm_set_bit(struct dbm *dbm, uint64_t bit)
{
int nr_bit, ret = 0;
struct dbm_record *dbm_record;
unsigned long flags;
if ((bit * DBM_BDEV_SIZE_PER_BIT) > dbm->disk_size) {
//dump_stack();
log_err("%s try set bit %llu beyond %s scope.\n", __FUNCTION__, bit, dbm->node->hadmdev->name);
return -1;
}
dbm_record = dbm_find_record(dbm, bit >> (DBM_SHIFT + BYTE_SHIFT));
if(dbm_record == NULL){
return -1;
}
nr_bit = bit & PAGE_BIT_MASK;
spin_lock_irqsave(&dbm->dbm_lock, flags);
if (!test_and_set_bit(nr_bit, page_address(dbm_record->page))) {
__dbm_dirty_record(dbm, dbm_record);
atomic_inc(&dbm->nr_bit);
ret = 1;
}
spin_unlock_irqrestore(&dbm->dbm_lock, flags);
return ret;
}
這種做法的好處是，每次flush dirty dbm block時，只需要遍歷dbm->last_dirty_record這個連結串列即可，而無需遍歷一整塊記憶體的bit位，這個降低的spin_lock的上鎖時間效果很明顯。而且實作起來相比再加一套bitmap的機制要簡單得多，同時，在flush dirty dbm block時，可以每次取一個block來submit bio，非常方便。
內核裏使用list_head來組織連結串列的很多。但是透過連結串列指標實作狀態資訊的，我印象裏沒碰到過。這裏next為空，表示該dbm block沒有被汙染，next指標非空，表示dbm block 為dirty，並能透過遍歷連結串列來獲取所有dirty dbm block。演算法相當精巧，也充分利用了C指標和連結串列的特性，效能提升非常大，確實很nb。
