device mapper

调度模块得先说说Device Mapper

device mapper简介

• Device Mapper（DM）是Linux2.6全面引入的块设备新构架，通过DM可以灵活地管理系统中所有的真实或虚拟的块设备。
• Device mapper在内核中作为一个块设备驱动被注册,包含三个重要的对象概念

1. mapped device

   逻辑抽象,内核向外提供的逻辑设备，它通过映射表描述的映射关系和target device建立映射。

2. target device

   Target device 表示的是mapped device所映射的物理空间段，对mapped device所表示的逻辑设备来说，就是该逻辑设备映射到的一个物理设备。

3. 映射表

   从Mapped device到一个target device的映射表由一个多元组表示，该多元组由表示mappeddevice逻辑的起始地址、范围、和表示在targetdevice所在物理设备的地址偏移量以及target类型等变量组成

具体如下图

device mapper创建过程

1、根据内核向用户空间提供的ioctl 接口传来的参数，用dm-ioctl.c文件中的dev_create函数创建相应的mapped device结构。这个过程很简单，主要是向内核申请必要的内存资源，包括mapped device和为进行IO操作预申请的内存池，通过内核提供的blk_queue_make_request函数注册该mapped device对应的请求队列dm_request。并将该mapped device作为磁盘块设备注册到内核中。

2、调用dm_hash_insert将创建好的mapped device插入到device mapper中的一个全局hash表中，该表中保存了内核中当前创建的所有mapped device。

3、用户空间命令通过ioctl调用table_load函数，该函数根据用户空间传来的参数构建指定mapped device的映射表和所映射的target device。该函数先构建相应的dm_table、dm_target结构，再调用dm-table.c中的dm_table_add_target函数根据用户传入的参数初始化这些结构，并且根据参数所指定的target类型，调用相应的target类型的构建函数ctr在内存中构建target device对应的结构，然后再根据所建立的dm_target结构更新dm_table中维护的B树。上述过程完毕后，再将建立好的dm_table添加到mapped device的全局hash表对应的hash_cell结构中。

4、最后通过ioctl调用do_resume函数建立mapped device和映射表之间的绑定关系，事实上该过程就是通过dm_swap_table函数将当前dm_table结构指针值赋予mapped_device相应的map域中，然后再修改mapped_device表示当前状态的域。
通过上述的4个主要步骤，device mapper在内核中就建立一个可以提供给用户使用的mapped device逻辑块设备。

device mapper具体结构

IO流程

下面这一段转载自斯巴达第二季博客

一般来说，我们对磁盘的read和write最后都会走到kernel里的submit_bio函数，也就是把io请求变成一个个的bio（bio的介绍看这里），bio是linux内核里文件系统层和block层之间沟通的数据结构（有点像sk_buffer之于网络），到了block层以后，一般是先做generic_make_request把bio变成request，怎么个变法？如果几个bio要读写的区域是连续的，就攒成一个request（一个request下挂多个连续bio，就是通常说的“合并bio请求”）；如果这个bio跟其它bio都连不上，那它自己就创建一个新的request，把自己挂到这个request下。合并bio请求也是有限度的，如果这些连续bio的访问区域加起来超过了一定的大小（在/sys/block/xxx/queue/max_sectors_kb里设置）,那么就不能再合并成一个request了。

合并后的request会放入每个device对应的queue（一个机械硬盘即使有多个分区，也只有一个queue），之后，磁盘设备驱动程序通过调用peek_request从queue里取出request，进行下一步的处理。

之所以要把多个bio合并成一个request，是因为机械硬盘在顺序读写时吞吐最大。如果我们换成SSD盘，合并这事儿就没那么必要了，这一点是可选的，在实现设备驱动时，厂商可以选择从kernel的queue里取request，也可以选择自己实现queue的make_request_fn方法，直接拿文件系统层传过来的bio来进行处理（fusionio好像就是这么做的）。

我曾经弱弱的问过涛哥：既然bio有bio_vec结构指向多个page，那么为什么不干脆把多个bio合并成一个bio呢？何必要多一个request数据结构那么麻烦？
涛哥答曰：每个bio有自己的end_io回调，一个bio结束，就会做自己对应的收尾工作，如果你合并成一个bio了，就丧失了这种灵活性。

linux kernel有一个device mapper框架（以下简称dm框架），linux上的软RAID、multipath等都是通过此框架实现的。dm可以将多个设备聚合成一个虚拟设备提供给用户使用，其原理就是把这个虚拟设备的make_request_fn方法实现成了自己的dm_request，这样所有发往这个虚拟设备的bio都会走进dm_request，然后dm通过判断这个虚拟设备是基于request（request based）的还是基于bio（bio based）的来分别处理：

如果虚拟设备是request based，则和磁盘设备一样走generic_make_request把bio合并成request（如上），注意这些request最后放到的是虚拟设备的queue里，等到虚拟设备通过kblockd调用dm_request_fn时，dm_request_fn里会调用peek_request，从虚拟设备的queue里拿出request，将其clone（clone后的request里的bio指向的page是同一个page，只是分配了新的bio和新的request），然后调用map_request对request做映射（map_request里把map_rq接口暴露给了使用dm框架的开发者），最后把clone后的request发向低层的真实设备。

如果虚拟设备是bio based，就更简单了，调用_dm_request函数，一样要clone bio，然后调用map_bio对bio做映射（map_bio里把map暴露给了使用dm框架的开发者），最后把clone后的bio也是通过generic_make_request发向低层的真实设备，这次generic_make_request生成的request就是放在真实设备的queue里了，这是与request based的不同之处。

flashcache是基于dm框架实现的，很自然的，是把一个SSD盘和一个机械硬盘聚合成一个虚拟设备供用户使用。
flashcache把cache（指SSD盘）分为多个set，每个set里有多个block（默认一个block是4KB，一个set包含512个block，即2MB），set里的block是用lru链表组织起来的，每个block还记录了自己存放的是disk的哪个sector起始的位置里对应的内容（这个起始的sector编号在flashcache的文档里被称为dbn）。
disk（这里指机械硬盘）也虚拟的分为多个set只是为了方便做hash。hash算法非常简单，先看访问的是disk的什么位置，相当于在disk的哪个set里，然后模上cache里的set数，结果就是在cache里对应的set编号了。找到cache对应的set后，继续在set的lru表里挨个儿block的比对dbn号，对上了就成功，对不上说明cache里没有缓存要读取的disk内容。

例如cache大小为10G，disk大小为100G，用户要读取磁盘上偏移54321MB处的2K内容，那么首先对54321MB这个位置做hash，2MB一个set，对应的set number是27160，cache的总set数为5120，那么 27160 mod 5120 结果为1560，也就是说应该去cache的第1560个set中去找，然后来到cache的1560 set里用 dbn 111249408 遍历查找lru。
其实，新版本的flashcache在组相联算法上做了改进，如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/*
 * Map a block from the source device to a block in the cache device.
 */
unsigned long 
hash_block(struct cache_c *dmc, sector_t dbn)
{
	unsigned long set_number, value;
        int num_cache_sets = dmc->size >> dmc->assoc_shift;
	/*
	 * Starting in Flashcache SSD Version 3 :
	 * We map a sequential cluster of disk_assoc blocks onto a given set.
	 * But each disk_assoc cluster can be randomly placed in any set.
	 * But if we are running on an older on-ssd cache, we preserve old
	 * behavior.
	 */
	if (dmc->on_ssd_version < 3 || dmc->disk_assoc == 0) {
		value = (unsigned long)
			(dbn >> (dmc->block_shift + dmc->assoc_shift));
	} else {//新版本对flashcache组相联的改进
		/* Shift out the low disk_assoc bits */
		value = (unsigned long) (dbn >> dmc->disk_assoc_shift);
		/* Then place it in a random set */
		value = jhash_1word(value, 0xbeef);
	}
	set_number = value % num_cache_sets;
	DPRINTK("Hash: %llu(%lu)->%lu", dbn, value, set_number);
	return set_number;
}

flashcache主要是实现了dm框架暴露出来的map接口（参考flashcache_map函数），收到bio后，先做hash，然后在cache（这里指SSD盘）里查找:

A. 如果是读bio
1 如果查找成功，直接将结果返回
2 如果查找失败，则找set内空闲的block（如果没有空闲的，则用最“旧”的block），直接读取disk里对应的内容返回给用户，返给用户后设置延时任务将读取的内容放入这个空闲block里

B. 如果是写bio（我们仅列举writeback情况）
1 如果查找成功，拿到对应的block
2 如果查找失败，拿到对应set里最“旧”的block
直接将数据写入此block，返回给用户（用户的write系统调用就可以返回了），完成后将该block的状态设为DIRTY并设置延时任务，任务内容为将cache里的内容写往disk（这样既能让用户的写请求迅速完成，又能一定程度保证数据最终被写往disk）。延时任务完成后，便可以去掉DIRTY标记了。

flashcache还会不时的将cache的set里长期没被访问的DIRTY的block写往disk，以保证有足够多的干净的block供以后使用。这个“不时的”不是靠定时器实现的，而是通过在flashcache_write_miss、flashcache_read_miss等函数里调用flashcache_clean_set来做到的。

补充两个问题

最后补充一下相关的代码

• dm.c 代码可以参见
• dm-io.h、bio.h以及device-mapper.h等头文件一般在
  /usr/src/$(shell uname -r)/include/linux文件夹下

我们进一步看一下上述三个对象在代码中的具体实现，dm.c 文件定义的 mapped_device 结构用于表示 mapped device，它主要包括该 mapped device 相关的锁，注册的请求队列和一些内存池以及指向它所对应映射表的指针等域。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*
 * Work processed by per-device workqueue.
 */
struct mapped_device {
	struct rw_semaphore io_lock;
	struct mutex suspend_lock;
	rwlock_t map_lock;
	atomic_t holders;
	atomic_t open_count;
	unsigned long flags;
	struct request_queue *queue;
	unsigned type;
	/* Protect queue and type against concurrent access. */
	struct mutex type_lock;
	struct target_type *immutable_target_type;
	struct gendisk *disk;
	char name[16];
	void *interface_ptr;
	/*
	 * A list of ios that arrived while we were suspended.
	 */
	atomic_t pending[2];
	wait_queue_head_t wait;
	struct work_struct work;
	struct bio_list deferred;
	spinlock_t deferred_lock;
	/*
	 * Processing queue (flush)
	 */
	struct workqueue_struct *wq;
	/*
	 * The current mapping.
	 */
	struct dm_table *map;
	/*
	 * io objects are allocated from here.
	 */
	mempool_t *io_pool;
	struct bio_set *bs;
	/*
	 * Event handling.
	 */
	atomic_t event_nr;
	wait_queue_head_t eventq;
	atomic_t uevent_seq;
	struct list_head uevent_list;
	spinlock_t uevent_lock; /* Protect access to uevent_list */
	/*
	 * freeze/thaw support require holding onto a super block
	 */
	struct super_block *frozen_sb;
	struct block_device *bdev;
	/* forced geometry settings */
	struct hd_geometry geometry;
	/* sysfs handle */
	struct kobject kobj;
	/* zero-length flush that will be cloned and submitted to targets */
	struct bio flush_bio;
};

Mapped device 对应的映射表是由 dm_table.c 文件中定义的 dm_table 结构表示的，该结构中包含一个 dm_target结构数组，在 dm_table 结构中将这些dm_target 按照 B 树的方式组织起来方便 IO 请求映射时的查找操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

struct dm_table {  
    struct mapped_device *md;  
    atomic_t holders;  
    unsigned type;  
  
    /* btree table */  
    unsigned int depth;  
    unsigned int counts[MAX_DEPTH]; /* in nodes */  
    sector_t *index[MAX_DEPTH];  
  
    unsigned int num_targets;  
    unsigned int num_allocated;  
    sector_t *highs;  
    struct dm_target *targets;  
  
    /* 
     * Indicates the rw permissions for the new logical 
     * device.  This should be a combination of FMODE_READ 
     * and FMODE_WRITE. 
     */  
    fmode_t mode;  
  
    /* a list of devices used by this table */  
    struct list_head devices;  
  
    /* events get handed up using this callback */  
    void (*event_fn)(void *);  
    void *event_context;  
  
    struct dm_md_mempools *mempools;  
}

dm_target 结构描述了 mapped_device 到它某个 target device 的映射关系，具体记录该结构对应 target device 所映射的 mapped device 逻辑区域的开始地址和范围，同时还包含指向具体 target device 相关操作的 target_type 结构的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct dm_target {  
    struct dm_table *table;  
    struct target_type *type;  
  
    /* target limits */  
    sector_t begin;  
    sector_t len;  
  
    /* Always a power of 2 */  
    sector_t split_io;  
  
    /* 
     * A number of zero-length barrier requests that will be submitted 
     * to the target for the purpose of flushing cache. 
     * 
     * The request number will be placed in union map_info->flush_request. 
     * It is a responsibility of the target driver to remap these requests 
     * to the real underlying devices. 
     */  
    unsigned num_flush_requests;  
  
    /* target specific data */  
    void *private;  
  
    /* Used to provide an error string from the ctr */  
    char *error;  
}

flashcache中target类型对应target device的结构是struct cache_c

赏

嘘寒问暖不如来笔巨款

支付宝

微信