有哪些算法惊艳到了你？

说工作中一个同事的精彩算法。

我们在开发一个内核块设备的驱动，需要一块内存记录块设备的改变，假设一个块设备的大小是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。