#To free pagecache echo 1 > /proc/sys/vm/drop_caches #To free dentry and inode cache echo 2 > /proc/sys/vm/drop_caches #To free pagecache,dentry cache,inode cache echo 3 > /proc/sys/vm/drop_caches dentry cache struct dentry反映的是文件系统对象（包括目录、文件）在内核中所在文件系统树的位置，在文件系统对文件的操作中inode是对应文件处理的核心对象，而要找到inode就需要先找到dentry，dentry对象内容指向了inode。因此在文件系统做dentry的搜索效率也一定程度上决定着文件系统操作效率，在linux系统中为了提高dentry的处理效率，实现了dentry高速缓存，dentry cache简称dcache。 在3.1.3章节中我们列出了dentry的数据结构组成，其中对于搜索的提升有两个关键数据结构。 struct dentry { struct hlist_bl_node d_hash; strcut list_head d_lru; } 在文件系统初始化时，调用vfs_caches_init->dcache_init为对dcache进行初始化，先创建一个dentry的slab，用于后续dentry对象的分配，同时还分配了一个dentry_hashtable用于管理dentry的全局hash表。 static void __init dcache_init(void) { /* * A constructor could be added for stable state like the lists, * but it is probably not worth it because of the cache nature * of the dcache. */ dentry_cache = KMEM_CACHE_USERCOPY(dentry, SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD|SLAB_ACCOUNT, d_iname); /* Hash may have been set up in dcache_init_early */ if (!hashdist) return; dentry_hashtable = alloc_large_system_hash("Dentry cache", sizeof(struct hlist_bl_head), dhash_entries, 13, HASH_ZERO, &d_hash_shift, NULL, 0, 0); d_hash_shift = 32 - d_hash_shift; } 可以cat /proc/slabinfo | grep dentry查看dentry的情况。 dcache在kmem_cache_alloc的基础上定义了两个高层分配接口：d_alloc和d_alloc_root函数，用来从dentry_cache slab中分配dentry对象。d_alloc_root时用来为文件系统跟目录分配dentry对象的。 dentry释放后并不会马上清除掉，而是不缓存起来，所以通常有3种状态，而其中unused和negative是可以在主动触发释放是可以进行回收的。 inuse：正在被使用，引用技术d_lockref>0。 unused：未被内核使用，引用技术d_lockref为0，d_inode为空。 negative:相应的磁盘inode已经被删除，d_inode为空。 dentry结构通常在路径查找被创建，常用的有以下2种管理方式 哈希链表：static struct hlist_bl_head *dentry_hashtable __read_mostly，以dentry->name作为索引在dentry全局hash表中管理，用于提高路径查找效率。 LRU链表：处于unused和negative状态不再使用的dentry都通过其dentry->d_lru指针链接到super_block->s_dentry_lru中，当需要内存回收时，由prune_dcache_sb回收使用较少的dentry。 在linux系统中定义了dentry_stat_t数据结构来统计dcache信息。 struct dentry_stat_t { int nr_dentry; dentry的数量 int nr_unused; dentry为使用的数量 int age_limit;/* age in seconds */ int want_pages;/* pages requested by system */ int dummy[2]; }; extern struct dentry_stat_t dentry_stat; 可以通过节点/proc/sys/fs/dentry-state来获取，可以发现dentry-state的nr_dentry:15227与slab info中已经分配出去的对象15229差不多，16957表示当前dentry cache中一共还有多少个对象包括使用和为使用的，528表示每个对象的大小，单位是字节，可以看出一个对象是528字节，对应struct dentry数据结构的大小。 当系统使用echo 2 > /proc/sys/vm/drop_caches可以释放dentry和inode的缓存。 #To free dentry and inode cache echo 2 > /proc/sys/vm/drop_caches 执行上面的命令后，可以查看节点/proc/sys/fs/dentry-state或cat /proc/slabinfo | grep dentry可以看出dentry的数量变少了，系统回收了。 inode cache Inode是用于描述一个文件的，通常有一个或多个dentry与之对应，dentry已经描述了系统的目录树，提供了路径查找的方法，所以inode就不需要在搜索查询上处理复杂关系，管理方式也相对简单不少。 struct inode { ... /* Stat data, not accessed from path walking */ unsigned long i_ino; //与其i_sb一起计算hash作为在inode_hashtable中的索引 struct hlist_node i_hash; //inode_hashtable全局hash表中的节点 struct list_head i_lru; /* inode LRU list */ //其i_sb->s_inode_lru中的节点 ... } 与dentry类似，在内核初始化阶段，会调用inode_init初始化一个inode_cache的slab对象，用于inode的分配。同时还创建了一个用于管理inode的全局哈希表inode_hashtable。 void __init inode_init(void) { /* inode slab cache */ inode_cachep = kmem_cache_create("inode_cache", sizeof(struct inode), 0, (SLAB_RECLAIM_ACCOUNT|SLAB_PANIC| SLAB_MEM_SPREAD|SLAB_ACCOUNT), init_once); /* Hash may have been set up in inode_init_early */ if (!hashdist) return; inode_hashtable = alloc_large_system_hash("Inode-cache", sizeof(struct hlist_head), ihash_entries, 14, HASH_ZERO, &i_hash_shift, &i_hash_mask, 0, 0); } Inode结构主要涉及两种管理方式 inode哈希表：inode_hashtable， super_block和i_ino作为索引在inode在全局inode_hashtable中管理，主要通过i_ino查找到inode。 LRU链表：通过inode->i_lru链接到super_block->s_inode_lru上，表示不再使用的空闲inode，当需要内存回收是，从中选取最少使用的inode进行回收。 struct inodes_stat_t { long nr_inodes; long nr_unused; long dummy[5]; /* padding for sysctl ABI compatibility */ }; struct inodes_stat_t inodes_stat; 与dentry类似，inode也定义了一个inodes_stat用于统计inode信息，可以通过cat /proc/sys/fs/inode-state来查询。 page cache free显示中的buff和cache怎么理解，使用free -w会将buff和cache分开，字面上buffer缓冲，而cache是缓存。 free的数据来源与/proc/meminfo之间的关系。 buffers：内核缓冲区的内存，对应的是/proc/meminfo中的Buffers cache:是内核页缓存和slab用到的内存，对应的是/proc/meminfo中cached+SReclainmable之和。 buff/cache:则是buffers和cache之和。 所以要理解free中buff/cache的关键是要理解buffers、cached、SReclaimable三个的概念，下面是man proc的意思。 Buffers %lu Relatively temporary storage for raw disk blocks that shouldn't get tremendously large (20MB or so). Cached %lu In-memory cache for files read from the disk (the page cache). Doesn't include SwapCached. SReclaimable %lu (since Linux 2.6.19) Part of Slab, that might be reclaimed, such as caches. Buffers:是对原始磁盘块的零时存储，用于缓存磁盘的数据，通常不会特别大（20MB左右），因为对应用户来说读写数据可能是几个字节，但是对应磁盘来说是按block来操作的，这样内核就可以把分散写集中起来，如把多次小的写集合并成单次大的写。 Cached：是磁盘读取文件的页缓存，也就是用来缓存从文件读取的数据，这样下次访问这些文件数据时，旧可以直接从内存快速获取，而不需要再次访问缓慢的磁盘，但是不包括交互到swap分区的。 SReclaimable:是slab的一部分。Slab包含可回收和不可回收两部分，可回收的用SReclaimable记录（dentry cache、inode cache属于slab的一部分），不可回收的用SUnrecalaim记录。 从上面buffers和cached的来看，buffer是对磁盘的，而cache是针对文件页缓存读的，看起来是分开的，但实际上buffers和cached并没有分开，都是page cache，下面将来进行阐述。 CPU的读写速度与磁盘的读写速度是有很大差距的，因此文件系统在访问磁盘时，并不会直接与磁盘进行交互，而是在具体的文件系统与磁盘之间申请一段缓冲buffer，这段缓冲buffer实际就是申请了一块内存，将磁盘的数据缓存到这块内存中，具体的文件系统对磁盘的读写就转换为对缓冲buffer的读写这样就可以提高处理的速度，系统负责定期的将缓冲buff与磁盘进行数据同步，当然也可以手动sync的方式进行同步。 早期linux0.11阶段，buffer cache在linux中对应的数据结构是struct buffer_head，简称bh，顾名思义，表示缓冲区头部，这个缓冲区缓冲的是磁盘块设备数据，早期阶段为了提高磁盘的读写消息，在磁盘之上增加了一个缓冲，磁盘的读写单位是block，一般block的大小是1KB，每个block就对应一个bh，而bh的内存申请是以原始的内存分配方式，还没有基于page来分配内存。 strcut buffer_head { char *b_data; /* pointer to data block (1024 bytes) *///指针。 unsigned long b_blocknr; /* block number */// 块号。 unsigned short b_dev; /* device (0 = free) */// 数据源的设备号。 unsigned char b_uptodate; // 更新标志：表示数据是否已更新。 unsigned char b_dirt; /* 0-clean,1-dirty *///修改标志:0 未修改,1 已修改. unsigned char b_count; /* users using this block */// 使用的用户数。 unsigned char b_lock; /* 0 - ok, 1 -locked */// 缓冲区是否被锁定。 struct task_struct *b_wait; // 指向等待该缓冲区解锁的任务。 struct buffer_head *b_prev; // hash 队列上前一块（这四个指针用于缓冲区的管理）。 struct buffer_head *b_next; // hash 队列上下一块。 struct buffer_head *b_prev_free; // 空闲表上前一块。 struct buffer_head *b_next_free; // 空闲表上下一块。 }; 发展到中间阶段时linux2.2版本，buffer 就基于page来分配内存，但是page cache和buffer没有什么直接连续，是各自独立的作用，page cache只用于负责mmap的部分处理，buffer 依旧负责对磁盘IO的访问缓冲，如下图。但这样就会出现一个问题，由于read/write是绕过了page cache，就会导致mmap和read/write操作同步问题，磁盘的同一份数据在page cache中有一份，在buffer中也有一份，这样分离的设计还会导致浪费内存。 struct buffer_head { /* First cache line: */ struct buffer_head * b_next; /* Hash queue list */ unsigned long b_blocknr; /* block number */ unsigned long b_size; /* block size */ kdev_t b_dev; /* device (B_FREE = free) */ kdev_t b_rdev; /* Real device */ unsigned long b_rsector; /* Real buffer location on disk */ struct buffer_head * b_this_page; /* circular list of buffers in one page */ unsigned long b_state; /* buffer state bitmap (see above) */ struct buffer_head * b_next_free; unsigned int b_count; /* users using this block */ /* Non-performance-critical data follows. */ char * b_data; /* pointer to data block (1024 bytes) */ unsigned int b_list; /* List that this buffer appears */ unsigned long b_flushtime; /* Time when this (dirty) buffer * should be written */ struct wait_queue * b_wait; struct buffer_head ** b_pprev; /* doubly linked list of hash-queue */ struct buffer_head * b_prev_free; /* doubly linked list of buffers */ struct buffer_head * b_reqnext; /* request queue */ /* * I/O completion */ void (*b_end_io)(struct buffer_head *bh, int uptodate); void *b_dev_id; }; 发展到第三阶段linux 2.4版本，对cache和buffer进行了融合，因为buffer的申请也是基于page的，那这两个为什么不融合在一起了，融合后buffer cache就直接存储在page cache中，但是依旧保留了buffer cache的描述。 struct buffer_head { unsigned long b_state; /* buffer state bitmap (see above) */ struct buffer_head *b_this_page;/* circular list of page's buffers */ struct page *b_page; /* the page this bh is mapped to */ sector_t b_blocknr; /* start block number */ size_t b_size; /* size of mapping */ char *b_data; /* pointer to data within the page */ struct block_device *b_bdev; bh_end_io_t *b_end_io; /* I/O completion */ void *b_private; /* reserved for b_end_io */ struct list_head b_assoc_buffers; /* associated with another mapping */ struct address_space *b_assoc_map; /* mapping this buffer is associated with */ atomic_t b_count; /* users using this buffer_head */ spinlock_t b_uptodate_lock; /* Used by the first bh in a page, to * serialise IO completion of other * buffers in the page */ }; 至此page cache和buffer 两者的关系融合了。磁盘的读写是按block为单位操作，一个block对应一个buffer_head缓冲，如块单位是1KB，那么1个page cache就有4个buffer_head。 对于文件系统的操作来说，buffer和cache都是page cache，对应的是进程打开文件内存的缓存，缓存在address_space::i_pages的xarray上，缓存的数量为address_space::nrpages。 Buffer_head的原义是与block对应，按照磁盘的布局分为元数据区和数据区域，元数据是用于管理磁盘的如supper_block、inode等，数据区域才是正在的对应文件系统操作的数据。所以的对于cache和buffer的区别，buffer还存储了对磁盘管理的元数据缓存，这部分 再后来在linux2.4版本之后，新的文件系统开始引入了bio结构来替换buffer_head，但是原有的一些文件系统并没有完全替换使用bio，所以了就需要做bio兼容buffer_head，在磁盘操作前会调用到submit_bh_wbc函数，该函数会将buffer_head组装成bio，因此最终对磁盘的操作都会转为bio的方式，新的文件系统就直接使用bio。 static int submit_bh_wbc(int op, int op_flags, struct buffer_head *bh, enum rw_hint write_hint, struct writeback_control *wbc) { struct bio *bio; BUG_ON(!buffer_locked(bh)); BUG_ON(!buffer_mapped(bh)); BUG_ON(!bh->b_end_io); BUG_ON(buffer_delay(bh)); BUG_ON(buffer_unwritten(bh)); /* * Only clear out a write error when rewriting */ if (test_set_buffer_req(bh) && (op == REQ_OP_WRITE)) clear_buffer_write_io_error(bh); bio = bio_alloc(GFP_NOIO, 1); fscrypt_set_bio_crypt_ctx_bh(bio, bh, GFP_NOIO); bio->bi_iter.bi_sector = bh->b_blocknr * (bh->b_size >> 9); bio_set_dev(bio, bh->b_bdev); bio->bi_write_hint = write_hint; bio_add_page(bio, bh->b_page, bh->b_size, bh_offset(bh)); BUG_ON(bio->bi_iter.bi_size != bh->b_size); bio->bi_end_io = end_bio_bh_io_sync; bio->bi_private = bh; if (buffer_meta(bh)) op_flags |= REQ_META; if (buffer_prio(bh)) op_flags |= REQ_PRIO; bio_set_op_attrs(bio, op, op_flags); /* Take care of bh's that straddle the end of the device */ guard_bio_eod(bio); if (wbc) { wbc_init_bio(wbc, bio); wbc_account_cgroup_owner(wbc, bh->b_page, bh->b_size); } submit_bio(bio); return 0; } 以上的page cache和buffer cache的融合是针对使用文件系统的方式访问块设备的场景。但是如果以下的两个方式访问磁盘①使用文件②使用块设备节点，这两种方式对应的page cache是不同的，文件的方式是buff/cache，而块设备节点是buff（实际也是page cache分配），这种情况下一个物理磁盘的block数据仍然对应linux内核的两份page，一个是通过通用文件层访问的文件page cache（page cache），另一个是通过块设备节点访问的page cache（buffer cache）。另外需要注意的是，如果通过块设备节点访问声明了O_DIRECT，将会直接访问磁盘不会经过buff。 上图如果分别使用文件系统方式/mnt/test的方式或者裸设备/dev/sda的方式去写磁盘，即使是一个位置，但是将会有两份page cache，前者的page cache对应的就是free中的cache，而后边的page cache对应的是free中的buff。 可以从/proc/meminfo的实现来研究一下buff和cache的区别。 static int meminfo_proc_show(struct seq_file *m, void *v) { struct sysinfo i; unsigned long committed; long cached; long available; unsigned long pages[NR_LRU_LISTS]; unsigned long sreclaimable, sunreclaim; int lru; si_meminfo(&i); si_swapinfo(&i); committed = vm_memory_committed(); cached = global_node_page_state(NR_FILE_PAGES) - total_swapcache_pages() - i.bufferram; if (cached < 0) cached = 0; for (lru = LRU_BASE; lru < NR_LRU_LISTS; lru++) pages[lru] = global_node_page_state(NR_LRU_BASE + lru); available = si_mem_available(); sreclaimable = global_node_page_state_pages(NR_SLAB_RECLAIMABLE_B); sunreclaim = global_node_page_state_pages(NR_SLAB_UNRECLAIMABLE_B); show_val_kb(m, "MemTotal: ", i.totalram); show_val_kb(m, "MemFree: ", i.freeram); show_val_kb(m, "MemAvailable: ", available); show_val_kb(m, "Buffers: ", i.bufferram); //show_val_kb会将page数量转化为kb。 show_val_kb(m, "Cached: ", cached); show_val_kb(m, "SwapCached: ", total_swapcache_pages()); ...... } 先来看看buff，buffers为i.bufferram，而该值在si_meminfo(&i)中计算而来，在该函数中调用nr_blockdev_pages计算而来。 void si_meminfo(struct sysinfo *val) { val->totalram = totalram_pages(); val->sharedram = global_node_page_state(NR_SHMEM); val->freeram = global_zone_page_state(NR_FREE_PAGES); val->bufferram = nr_blockdev_pages(); val->totalhigh = totalhigh_pages(); val->freehigh = nr_free_highpages(); val->mem_unit = PAGE_SIZE; } 再看看下面的函数调用，buffers是遍历所有的块设备，累加address->i_mapping上nrpages值，该值就是xarray树上对应的page数量，对应上图中直接操作磁盘节点读写的方式 “open /dev/sda”。 long nr_blockdev_pages(void) { struct inode *inode; long ret = 0; spin_lock(&blockdev_superblock->s_inode_list_lock); list_for_each_entry(inode, &blockdev_superblock->s_inodes, i_sb_list) ret += inode->i_mapping->nrpages; spin_unlock(&blockdev_superblock->s_inode_list_lock); return ret; } 再来看看cached的计算cached = global_node_page_state(NR_FILE_PAGES) -total_swapcache_pages() - i.bufferram，其中 global_node_page_state(NR_FILE_PAGES) 为vm_node_stat[NR_FILE_PAGES]的值。内核中定义了一个全局变量atomic_long_t vm_node_stat[]，用于统计全局内存的信息，搜索内核中关于NR_FILE_PAGES的标志，主要有以下三个函数修改。 __mod_lruvec_page_state(item,val) //对全局变量vm_node_stat[item]增加val __dec_lruvec_page_state()//对全局变量vm_node_stat[item]减1 __inc_lruvec_page_state()//对全局变量vm_node_stat[item]加1 示例 __mod_lruvec_page_state(page, NR_FILE_PAGES, -nr) __mod_node_page_state(page_pgdat(page), idx, val) node_page_state_add(delta, pgdat, item) //delta=-nr atomic_long_add(x, &pgdat->vm_stat[item]); atomic_long_add(x, &vm_node_stat[item]); 从上面的函数调用，__mod_lruvec_page_state(struct page *page,enum node_stat_item idx, int val)的作用就是根据item类型（这里是NR_FILE_PAGES）对全局变量vm_node_stat[item]增加val。 从上的函数调用流程可知，无论是文件系统的写还是读，当分配新的page时，会调用add_to_page_cache_lru将page添加到xarray树上，并调用__inc_lruvec_page_state增加page计数，同时会添加到LRU链表用于后续回收。除了调用generic_file_read/write读写文件系统会修改vm_node_stat[NR_FILE_PAGES]外，还有不少操作也会让vm_node_stat[NR_FILE_PAGES]会增加，如通过dev节点直接对磁盘的操作（buffers），以及匿名页交换到swap分区的也会修改。因此vm_node_stat[NR_FILE_PAGES]是一个总的值，实际在计算cached的时候会把交换到swap分区、以及buffers的值减去。cached = global_node_page_state(NR_FILE_PAGES) -total_swapcache_pages() - i.bufferram。 总结下： 对于文件系统的操作方式来说(如/mnt/UDISK/test)，大部分是cached（buffers和cached以及合并了），会占用少部分的buffer，主要是存储一些元数据的存储是划到buffer中。 对于磁盘的操作方式来说(如/dev/sda)，只有buffers。 可以使用测试使用vmstat观察buff和cache的变化情况。 通过文件系统的方式 写入到文件系统中 echo 3 > /proc/sys/vm/drop_caches dd if=/dev/urandom of=/mnt/UDISK/test bs=1M count=5 从文件系统中读 echo 3 > /proc/sys/vm/drop_caches dd if=/mnt/UDISK/test4 of=/tmp/test bs=1M count=10 通过vmstat统计来看，写入到文件系统ext4上或从文件系统读，基本都是cache在变化。 通过磁盘的方式操作 echo 3 > /proc/sys/vm/drop_caches dd if=/dev/urandom of=/dev/mmcblk0p9 bs=1M count=8 echo 3 > /proc/sys/vm/drop_caches dd if=/dev/mmcblk0p9 of=/dev/null bs=1M count=8 通过磁盘的方式操作，可以发现buff和cache都有变化（这里的cache还包括了slab可以回收部分，如果查询/proc/meminfo下的cached变化会更少些），但是buff变化更大些，然后突然又降回去了（被系统回收了）读磁盘数据会缓存到buffer中。 Direct IO写 dd if=/dev/urandom of=/dev/mmcblk0p9 bs=1M count=10 oflag=direct 可以发现buff，cache基本没变化。

地址空间 虚拟地址：程序使用的内存地址；物理地址：硬件的地址空间。虚拟地址通过MMU转化为物理地址，虚拟地址的长度与实际的物理内存容量没有关系，从系统中每个进程的角度看，地址空间的进程无法感知其他进程的存在。 32位cpu处理的地址空间为2^32=4G，所以虚拟地址空间为4G，分为用户空间和内核空间。用户空间的范围0~TASK_SIZE（可配置）通常为0x00000000~0xBFFFFFFF，内核空间的地址范围0xC0000000~0xFFFFFFF。由于地址空间虚拟化的结果，每个用户进程都认为自身有3G内存，而内核空间总是同样的，无论当前执行的是那个进程。 64位的cpu寻址空间为2^64，但实际只使用了47位，即寻址范围位2^48=256TB，多出的高16位就形成了地址空洞。内核空间的高16位全为1，用户空间的高16位全为0，可以直接方便判断是用户空间地址还是内核空间地址。 虚拟与物理地址 虚拟地址空间和物理内存被划分为很多等长的部分，称之为页，物理内存页被称为页帧。 进程1的页3和进程2的页1同时指向了物理页帧3，这种情况是可能的，因为两个虚拟地址空间的页可以映射到同一物理内存页，内核负责讲虚拟地址空间映射到物理地址空间，可以决定那些内存区域在进程之间共享，那些不共享。 进程的虚拟地址空间不是所有的页都映射到物理内存页帧上，因为没有这么大的一个物理内存供所有进程都一一映射完（一个进程3G，10个进程就是30G），因此只需要将当前使用的页进行映射（加载到内存中）。主要分为一些地址空间完全没有使用，另外就是有一些页被暂时换出到磁盘上，需要的时候再换回。当程序执行虚拟地址没有映射到物理地址，将运行缺页异常处理。 页表 将虚拟地址空间映射到物理地址空间的数据结构称为页表。实现两个地址空间的管理最容易的方法是使用数组，对虚拟地址空间的每一页，都分配一个数组项。该数组项指向与之关联的页帧。 二级页表 把虚拟地址分为3部分，PGD+PT+Offset组成。 为什么要使用多级页表？ （1）一级页表 一个进程4GB的虚拟地址空间需要4GB/4KB=1MB个页表项，每个页表项占用4字节，每个一级页表需要4MB的存储空间，一个进程需要4MB的内存来存储页表，那100个进程需要400MB。 （2）二级页表 一级页表PGD：一共4096项，每个页表项4字节，一共16KB。 二级页表PTE：一共4096个PTE页表，每个二级页表包含256个页表项，大小为1KB（256 * 4字节），所有的二级页表大小一共是4K * 1KB=4MB。 一个进程需要4MB+16KB的内存来存储页表。 根据linux内核局部性原理，不是所有的地址空间都需要映射到物理内存，所以二级页表实际的页表占用内存大小为（16KB+1KB * n） * m，其中n表示PTE的个数，m表示进程的数目。 因此对比一级页表，一个进程最少需要4MB的空间，而二级页表最少需要17KB的空间。 多级页表 PGD: page global directory，页全局目录 PUD: page upper directory，页上级目录 PMD:page middle directory，页中间目录 PT:page table，直接页表 linux 4.11之后，页表拓展到5级，在页全局目录和页上级目录之间增加了页四级目录。各个处理器架构可以选择5级、4级、3级、2级，使用CONFIG_PGTABLE_LEVELS来配置页表级数。页表级数越多，存储空间越小，主要是利用了内存管理的局部性原理，但是相应的硬件结构越复杂，访问的速度也会降低。针对访问速度的问题，CPU试图通过以下两种方法加速其转换过程。 （1）CPU中有一个专门的部分MMU（Memory Management Unit，内存管理单元），该单元优化了内存访问的操作。（通过硬件来负责转化，所有的页表都是存储在物理内存中，由软件按照要求先填写好，然后给一级页表的起始地址给TTBRx，后续虚拟地址到物理地址的转换就由MMU自动完成） （2）地址转换中出现最频繁的那些地址，保存到地址转换缓冲器中（TLB，Translation Lookaside Buffer），下次访问直接从缓存器中获得地址数据，不在进行地址转换。 物理内存分配 物理内存被均匀的分配为多个相等长度的页（页帧），通常大小为4KB。内核在分配内存时，必须要记录页帧的状态（是否已分配），以免两个进程使用同样的内存区域。由于内存分配和释放非常的频繁，内核还必须保证相关的操作尽快完成。 伙伴系统 内核中很多时候要求分配连续的页，快速检测内存中连续区域，内核使用伙伴系统。 内核对所有大小相同的伙伴，都放置到同一个列表中管理。空闲内存块总是两两分组，每组中的两个内存块称为伙伴。 如果系统中需要8个页帧，则将16个页帧组成的块分成两个伙伴，其中一块用户满足应用程序使用，剩余的8个页帧则放置到对应8页大小内存块列表中。 如果两个伙伴都是空闲的，内核会可以将其合并为一个更大的内存块，作为下一层上某个内存块的伙伴。 slab缓存 物理页帧的大小为4KB，但是内核本身经常需要分配比4KB小的内存块。由于内核无法使用标准库的函数，因而在伙伴系统的基础上自行定义额外的内存管理层，将伙伴系统提供的页划分为更小的部分。该方法不仅可以分配内存，还为频繁使用的小对象实现一个一般性的缓存-slab缓存。可以通过两种方法分配内存： （1）频繁使用的对象，内存定义了只包含所需类型对象的示例缓存。每次需要某种对象时，可以从对应的缓存快速分配。Slab缓存自动维护与伙伴系统的交互，在缓存用完时会请求新的页帧。 （2）通常情况下小内存的分配，内核针对不同大小的对象定义了一组slab缓存，可以像用户空间编程一样，使用类似的函数获取，如kmalloc和kfree。 页面交换和页面回收 页面交换：通过利用磁盘空间作为扩展内存，从而增大可用的内存。在内核需要更多内存时，不经常使用的页可以写入到磁盘中，如果再访问相关数据时，内核再将相应的页切换会内存。 页面回收：内存映射被修改的内容与底层的块设备同步，此时也称为数据写回。数据刷出后，内核即可将页帧用于其他用途。

实验环境 准备 kernel version: linux 5.15 kernel module: 块设备：simpleblk.ko 文件系统：simplefs.ko application： 制作文件系统：mkfs.simplefs 步骤 1.加载块设备驱动：insmod simpleblk.ko 2.加载文件系统：insmod simplefs.ko 3.查看文件系统类型：cat /proc/filesystems | grep simplefs 4.格式化块设备为simplefs：./mkfs.simplefs /dev/sblkdev1 5.挂载文件系统： 5.1创建挂载目录：mkdir simplefs 5.2格式化为simplefs：mount -t simplefs /dev/sblkdev1 /simplefs 块设备带文件系统方式读写 写数据 有具体文件系统的写与上一章节无文件系统的写主要的区别是，def_blk_fops和def_blk_aops依次替换为simplefs_file_ops和simplefs_aops。前者直接裸写方式使用了系统注册实现的bdev文件系统，而后者主要使用的是自定义注册的文件系统，在流程上没有太大的差异。数据打包成bio递交到块设备层后就一样的实现了，这里就不再赘述了。 读数据 读数据也是类似，def_blk_fops和def_blk_aops依次替换为simplefs_file_ops和simplefs_aops。主要流程上与上一章节无太大差异。

实验环境 kernel version: linux 5.15 kernel module: simpleblk.ko 参考上一章节 application：app_test 参考上一章节 块设备无文件系统方式读写 写数据 存储设备没有格式化挂载文件系统，那么对磁盘设备的操作会经过/dev/xxx tmpfs文件系统和bdev伪文件系统组合的方式读写磁盘。 Write系统调用经过VFS调用到def_blk_fops中的blkdev_write_iter，该函数中继续调用到__generic_file_write_iter。 如果是缓冲I/O的方式，将经过4个步骤，分别为获取page cache、从用户空间拷贝数据到page、修改的缓存标记为脏页、根据阈值是否要写回脏页。 在write_begin中会查询是否有磁盘对应的page cache，如果没有就申请一个page用于磁盘的缓冲；对于新申请的page cache，会调用ll_rw_block进行预读，将磁盘数据读取到page中，后面的操作就直接对page 操作即可。 数据写到缓存页page中（文件系统层） ksys_write -->vfs_write -->new_sync_write -->blkdev_write_iter -->blk_start_plug(&plug) -->__generic_file_write_iter -->blk_finish_plug(&plug) generic_perform_write -->a_ops->write_begin -->blkdev_write_begin -->block_write_begin --> grab_cache_page_write_begin 获取page缓存 --> __block_write_begin_int 写数据开始初始化 -->head = create_page_buffers 分配一个buffer_head -->if (!buffer_mapped(bh)) err = get_block(inode, block, bh, 1); -->blkdev_get_block 将块与buffer_head映射（把bh->b_bdev设置为inode对应的i_bdev并设置block号） -->copy_page_from_iter_atomic 用户拷贝数据到page中 -->a_ops->write_end -->blkdev_write_end 写数据结束，设置page为脏页 -->balance_dirty_pages_ratelimited(mapping) 脏页太多触发回写到磁盘 打包数据成bio递交到块设备层 直接写磁盘一般有几种方式，在建立bh和磁盘映射时，如果数据不是最新的则调用ll_rw_block进行写；另外情况就是当脏页超过一定阈值、用户关闭文件等操作触发worker回写，本小节以触发worker方式回写为例。 wb_workfn ->wb_writeback ->__writeback_inodes_wb ->writeback_sb_inodes ->__writeback_single_inode ->do_writepages ->if(mapping->a_ops->writepages) ret = mapping->a_ops->writepages(mapping, wbc) ->blkdev_writepages 调用bdev文件系统注册的写page函数 ->else ret = generic_writepages(mapping, wbc); blkdev_writepages ->generic_writepages ->blk_start_plug(&plug) ->write_cache_pages ->__writepage ->blk_finish_plug(&plug); __writepage ->mapping->a_ops->writepage(page, wbc); ->blkdev_writepage 注意与blkdev_writepages的区别（多了个s） ->block_write_full_page ->__block_write_full_page ->submit_bh_wbc submit_bh_wbc(REQ_OP_WRITE, write_flags, bh,inode->i_write_hint, wbc); 将bh转化为bio ->bio = bio_alloc(GFP_NOIO, 1); 分配一个bio ->bio->bi_iter.bi_sector = bh->b_blocknr * (bh->b_size >> 9); ->bio_set_dev(bio, bh->b_bdev); ->bio->bi_write_hint = write_hint; ->bio_add_page(bio, bh->b_page, bh->b_size, bh_offset(bh)); ->bio->bi_end_io = end_bio_bh_io_sync; ->bio->bi_private = bh; 递交bio ->submit_bio(bio); submit_bio ->submit_bio_noacct ->__submit_bio_noacct ->__submit_bio ->if (disk->fops->submit_bio) ->ret = disk->fops->submit_bio(bio); 如果块设备注册了submit_bio直接调用（一般是ramdisk使用这种方式） ->else ->blk_mq_submit_bio(bio) 如果没有注册则进入mq 创建和发送request blk_qc_t blk_mq_submit_bio(struct bio *bio) { 获取存储设备的request queue（包含blk_mq_ctx和blk_mq_hw_ctx） struct request_queue *q = bio->bi_disk->queue; 如果内存区处于高位区，则重新映射到低位区 blk_queue_bounce(q, &bio); 如果bio块太大，则对bio进行分割 __blk_queue_split(&bio, &nr_segs); if (!bio) goto queue_exit; 如果队列中没有禁用合并则尝试在task的current->plug上合并 if (!is_flush_fua && !blk_queue_nomerges(q) && blk_attempt_plug_merge(q, bio, nr_segs, &same_queue_rq)) goto queue_exit; //合并成功后直接退出 为了管理request，早期内核为每个task都定义了一个struct blk_plug，同task的request暂时都 会挂载到blk_plug.mg_list中，新增的bio到来时，会遍历blk_plug.mq_list，如果存在合适的 request直接添加，如果不存在就申请一个新的request添加。 尝试在IO调度器或软队列ctx中合并，合并成功则返回 if (blk_mq_sched_bio_merge(q, bio, nr_segs)) goto queue_exit; rq_qos_throttle(q, bio); hipri = bio->bi_opf & REQ_HIPRI; data.cmd_flags = bio->bi_opf; 如果bio没法合并到原有的request中去，则重新申请一个新的request。 rq = __blk_mq_alloc_request(&data); rq_qos_track(q, rq, bio); cookie = request_to_qc_t(data.hctx, rq); 将bio中的数据添加到新申请的request中 blk_mq_bio_to_request(rq, bio, nr_segs); 获取plug plug = blk_mq_plug(q, bio); 1. 如果是刷新flush/fua请求，则绕过调度器直接插入请求 if (unlikely(is_flush_fua)) { /* Bypass scheduler for flush requests */ blk_insert_flush(rq); blk_mq_run_hw_queue(data.hctx, true);启动请求派发 2. 当前任务正在做IO Plug && 设备硬件队列只有一个(hw_ctx?)，将request插入到当前任务的plug list } else if (plug && (q->nr_hw_queues == 1 || blk_mq_is_sbitmap_shared(rq->mq_hctx->flags) || q->mq_ops->commit_rqs || !blk_queue_nonrot(q))) { unsigned int request_count = plug->rq_count; struct request *last = NULL; if (!request_count) trace_block_plug(q); else last = list_entry_rq(plug->mq_list.prev); if (request_count >= blk_plug_max_rq_count(plug) || (last && blk_rq_bytes(last) >= BLK_PLUG_FLUSH_SIZE)) { blk_flush_plug_list(plug, false); trace_block_plug(q); } blk_add_rq_to_plug(plug, rq); 3. 如果request queue配置了调度器 } else if (q->elevator) { /* Insert the request at the IO scheduler queue */ blk_mq_sched_insert_request(rq, false, true, true); 将请求插入到调度器队列 4. 有plug && request queue没有禁止合并 走这个分支说明不是刷新请求、没有IO调度器。 } else if (plug && !blk_queue_nomerges(q)) { if (list_empty(&plug->mq_list)) same_queue_rq = NULL; if (same_queue_rq) { list_del_init(&same_queue_rq->queuelist); plug->rq_count--; } blk_add_rq_to_plug(plug, rq); trace_block_plug(q); if (same_queue_rq) { data.hctx = same_queue_rq->mq_hctx; trace_block_unplug(q, 1, true); blk_mq_try_issue_directly(data.hctx, same_queue_rq, &cookie); } 5. 设备硬件队列有多个（hw_ctx?） } else if ((q->nr_hw_queues > 1 && is_sync) || !data.hctx->dispatch_busy) { /* * There is no scheduler and we can try to send directly * to the hardware. */ blk_mq_try_issue_directly(data.hctx, rq, &cookie); } else { /* Default case. */ blk_mq_sched_insert_request(rq, false, true, true); } if (!hipri) return BLK_QC_T_NONE; return cookie; queue_exit: blk_queue_exit(q); return BLK_QC_T_NONE; } IO派发blk_mq_run_hw_queue 在mutilate queue中很多点都会触发IO请求到块设备驱动中 blk_mq_run_hw_queue ->__blk_mq_delay_run_hw_queue ->blk_mq_sched_dispatch_requests ->__blk_mq_sched_dispatch_requests ->blk_mq_do_dispatch_sched ->blk_mq_dispatch_rq_list ->ret = q->mq_ops->queue_rq(hctx, &bd); ->用户注册的回调函数.queue_rq 示例dump_stack [ 917.615686] _queue_rq+0x74/0x210 [simplefs] [ 917.620462] blk_mq_dispatch_rq_list+0x130/0x8cc [ 917.625633] blk_mq_do_dispatch_sched+0x2a8/0x32c [ 917.630902] __blk_mq_sched_dispatch_requests+0x14c/0x1b0 [ 917.636948] blk_mq_sched_dispatch_requests+0x40/0x80 [ 917.642609] __blk_mq_run_hw_queue+0x58/0x90 [ 917.647389] __blk_mq_delay_run_hw_queue+0x1d4/0x200 [ 917.652951] blk_mq_run_hw_queue+0x98/0x100 [ 917.657634] blk_mq_sched_insert_requests+0x90/0x170 [ 917.663193] blk_mq_flush_plug_list+0x130/0x1ec [ 917.668267] blk_flush_plug_list+0xec/0x120 [ 917.672950] blk_finish_plug+0x40/0xe0 [ 917.677149] wb_writeback+0x1e8/0x3b0 [ 917.681246] wb_workfn+0x39c/0x584 [ 917.685043] process_one_work+0x204/0x420 [ 917.689535] worker_thread+0x74/0x4dc [ 917.693634] kthread+0x128/0x134 [ 917.697247] ret_from_fork+0x10/0x20 读数据 预读 ksys_read ->vfs_read ->new_sync_read ->file->f_op->read_iter ->blkdev_read_iter blkdev_read_iter ->generic_file_read_iter ->filemap_read ->filemap_get_pages 获取page缓存 ->filemap_get_read_batch(mapping, index, last_index, pvec); 获取缓存页面 ->for(head = xas_load(&xas); head; head = xas_next(&xas)) 遍历xarray树，查询是否有缓存页 ->pagevec_add(pvec, head) ->if (!pagevec_count(pvec)) 如果没有获取到缓存页面，则进行页面预读 ->page_cache_sync_readahead 文件预读（文件预读会在重新自己分配page） ->page_cache_sync_ra ->ondemand_readahead ->if (!pagevec_count(pvec)) err = filemap_create_page(filp, mapping... 如果还是没有获取到缓存页面，则创建一个新的页面 ->add_to_page_cache_lru 添加页面到LRU中，便于回收 ->error = filemap_read_page(file, mapping, page); 读取数据到页面 ->page = pvec->pages[pagevec_count(pvec) - 1]; 获取批量缓存的最后一页 ->if (PageReadahead(page)) 判断最后一个页面是否需要预读 ->filemap_readahead 文件预读 ->page_cache_async_readahead ->for(i = 0; i < pagevec_count(&pvec); i++) 拷贝数据给应用 copied = copy_page_to_iter(page, offset, bytes, iter); 文件缓存页预读取 page_cache_sync_ra ->ondemand_readahead ->do_page_cache_ra ->page_cache_ra_unbounded 根据请求预读的数量遍历xarray树，如果page不存在就重新申请添加page并读取数据添加到LRU上。 ->for (i = 0; i < nr_to_read; i++) ->struct page *page = xa_load(&mapping->i_pages, index + i); ->if (page && !xa_is_value(page)) ->read_pages(ractl, &page_pool, true); ->page = __page_cache_alloc(gfp_mask); ->read_pages ->read_pages read_pages ->blk_start_plug(&plug) 在task_struct上安装一个list,用于合并多个request请求 ->if (aops->readahead) ->aops->readahead(rac) ->blkdev_readahead 1. block层预读 ------> ->else if(aops->readpages) ->aops->readpages(rac->file, rac->mapping, pages,readahead_count(rac)); ->else ->while ((page = readahead_page(rac))) ->blk_finish_plug(&plug); 2.将task_struct上合并request请求flush到存储设备队列 ->blk_flush_plug_list ->blk_mq_flush_plug_list 1.block层预读 ------>blkdev_readahead ->mpage_readahead ->mpage_bio_submit ->submit_bio(bio) submit_bio(bio) ->submit_bio_noacct ->__submit_bio ->blk_mq_submit_bio ->plug & hwqueue == 1 2.blk_mq_flush_plug_list ->blk_mq_sched_insert_requests ->blk_mq_run_hw_queue blk_mq_run_hw_queue ->__blk_mq_delay_run_hw_queue ->__blk_mq_run_hw_queue ->blk_mq_sched_dispatch_requests ->blk_mq_do_dispatch_sched ->blk_mq_dispatch_rq_list ->用户注册的回调函数.queue_rq -->read 从缓存中读取 ksys_read ->vfs_read ->new_sync_read ->file->f_op->read_iter ->blkdev_read_iter blkdev_read_iter ->generic_file_read_iter ->filemap_read ->filemap_get_pages 获取page缓存 ->filemap_get_read_batch(mapping, index, last_index, pvec); 获取缓存页面 ->for(head = xas_load(&xas); head; head = xas_next(&xas)) 遍历xarray树，查询有缓存页 ->pagevec_add(pvec, head) ->for(i = 0; i < pagevec_count(&pvec); i++) 拷贝数据给应用 copied = copy_page_to_iter(page, offset, bytes, iter); 与预读相比，如果在缓存中命中后，将直接从缓存中获取返回，在filemap_get_pages函数中获取缓存页，如果已经存在缓存页则不需要进行预读操作，接下来从缓存中拷贝数据给应用空间即可。

块设备驱动示例 #include <linux/blk_types.h> #include <linux/blkdev.h> #include <linux/device.h> #include <linux/blk-mq.h> #include <linux/list.h> #include <linux/module.h> #include <linux/hdreg.h> /* for HDIO_GETGEO */ #include <linux/cdrom.h> /* for CDROM_GET_CAPABILITY */ #define CONFIG_SBLKDEV_REQUESTS_BASED struct sblkdev_device { struct list_head link; sector_t capacity; /* Device size in sectors */ u8 *data; /* The data in virtual memory */ #ifdef CONFIG_SBLKDEV_REQUESTS_BASED struct blk_mq_tag_set tag_set; #endif struct gendisk *disk; }; struct sblkdev_device *sblkdev_add(int major, int minor, char *name, sector_t capacity); void sblkdev_remove(struct sblkdev_device *dev); extern int dump_flag; #ifdef CONFIG_SBLKDEV_REQUESTS_BASED static inline int process_request(struct request *rq, unsigned int *nr_bytes) { int ret = 0; struct bio_vec bvec; struct req_iterator iter; struct sblkdev_device *dev = rq->q->queuedata; loff_t pos = blk_rq_pos(rq) << SECTOR_SHIFT; loff_t dev_size = (dev->capacity << SECTOR_SHIFT); dump_stack(); printk("%s,%d\\n",__func__,__LINE__); rq_for_each_segment(bvec, rq, iter) { unsigned long len = bvec.bv_len; void *buf = page_address(bvec.bv_page) + bvec.bv_offset; if ((pos + len) > dev_size) len = (unsigned long)(dev_size - pos); if (rq_data_dir(rq)) { printk("%s, %d write:",__func__,__LINE__); memcpy(dev->data + pos, buf, len); /* WRITE */ } else { printk("%s, %d read:",__func__,__LINE__); memcpy(buf, dev->data + pos, len); /* READ */ } pos += len; *nr_bytes += len; } return ret; } static blk_status_t _queue_rq(struct blk_mq_hw_ctx *hctx, const struct blk_mq_queue_data *bd) { unsigned int nr_bytes = 0; blk_status_t status = BLK_STS_OK; struct request *rq = bd->rq; dump_stack(); printk("%s,%d\\n",__func__,__LINE__); //might_sleep(); cant_sleep(); /* cannot use any locks that make the thread sleep */ blk_mq_start_request(rq); if (process_request(rq, &nr_bytes)) status = BLK_STS_IOERR; pr_debug("request %llu:%d processed\\n", blk_rq_pos(rq), nr_bytes); blk_mq_end_request(rq, status); return status; } static struct blk_mq_ops mq_ops = { .queue_rq = _queue_rq, }; #else /* CONFIG_SBLKDEV_REQUESTS_BASED */ static inline void process_bio(struct sblkdev_device *dev, struct bio *bio) { struct bio_vec bvec; struct bvec_iter iter; loff_t pos = bio->bi_iter.bi_sector << SECTOR_SHIFT; loff_t dev_size = (dev->capacity << SECTOR_SHIFT); unsigned long start_time; dump_stack(); printk("%s,%d\\n",__func__,__LINE__); start_time = bio_start_io_acct(bio); bio_for_each_segment(bvec, bio, iter) { unsigned int len = bvec.bv_len; void *buf = page_address(bvec.bv_page) + bvec.bv_offset; if ((pos + len) > dev_size) { /* len = (unsigned long)(dev_size - pos);*/ bio->bi_status = BLK_STS_IOERR; break; } if (bio_data_dir(bio)) { printk("process_bio write\\n"); memcpy(dev->data + pos, buf, len); /* WRITE */ } else { printk("process_bio read\\n"); memcpy(buf, dev->data + pos, len); /* READ */ } pos += len; } bio_end_io_acct(bio, start_time); bio_endio(bio); } blk_qc_t _submit_bio(struct bio *bio) { blk_qc_t ret = BLK_QC_T_NONE; struct sblkdev_device *dev = bio->bi_bdev->bd_disk->private_data; printk("%s,%d\\n",__func__,__LINE__); might_sleep(); //cant_sleep(); /* cannot use any locks that make the thread sleep */ process_bio(dev, bio); return ret; } #endif /* CONFIG_SBLKDEV_REQUESTS_BASED */ static int _open(struct block_device *bdev, fmode_t mode) { struct sblkdev_device *dev = bdev->bd_disk->private_data; dump_flag = 1; printk("%s,%d\\n",__func__,__LINE__); if (!dev) { pr_err("Invalid disk private_data\\n"); return -ENXIO; } pr_debug("Device was opened\\n"); return 0; } static void _release(struct gendisk *disk, fmode_t mode) { struct sblkdev_device *dev = disk->private_data; printk("%s,%d\\n",__func__,__LINE__); if (!dev) { pr_err("Invalid disk private_data\\n"); return; } pr_debug("Device was closed\\n"); } static inline int ioctl_hdio_getgeo(struct sblkdev_device *dev, unsigned long arg) { struct hd_geometry geo = {0}; printk("%s,%d\\n",__func__,__LINE__); geo.start = 0; if (dev->capacity > 63) { sector_t quotient; geo.sectors = 63; quotient = (dev->capacity + (63 - 1)) / 63; if (quotient > 255) { geo.heads = 255; geo.cylinders = (unsigned short) ((quotient + (255 - 1)) / 255); } else { geo.heads = (unsigned char)quotient; geo.cylinders = 1; } } else { geo.sectors = (unsigned char)dev->capacity; geo.cylinders = 1; geo.heads = 1; } if (copy_to_user((void *)arg, &geo, sizeof(geo))) return -EINVAL; return 0; } static int _ioctl(struct block_device *bdev, fmode_t mode, unsigned int cmd, unsigned long arg) { struct sblkdev_device *dev = bdev->bd_disk->private_data; pr_debug("contol command [0x%x] received\\n", cmd); printk("%s,%d\\n",__func__,__LINE__); switch (cmd) { case HDIO_GETGEO: return ioctl_hdio_getgeo(dev, arg); case CDROM_GET_CAPABILITY: return -EINVAL; default: return -ENOTTY; } } #ifdef CONFIG_COMPAT static int _compat_ioctl(struct block_device *bdev, fmode_t mode, unsigned int cmd, unsigned long arg) { printk("%s,%d\\n",__func__,__LINE__); // CONFIG_COMPAT is to allow running 32-bit userspace code on a 64-bit kernel return -ENOTTY; // not supported } #endif static const struct block_device_operations fops = { .owner = THIS_MODULE, .open = _open, .release = _release, .ioctl = _ioctl, #ifdef CONFIG_COMPAT .compat_ioctl = _compat_ioctl, #endif #ifndef CONFIG_SBLKDEV_REQUESTS_BASED .submit_bio = _submit_bio, #endif }; /* * sblkdev_remove() - Remove simple block device */ void sblkdev_remove(struct sblkdev_device *dev) { printk("%s,%d\\n",__func__,__LINE__); del_gendisk(dev->disk); #ifdef HAVE_BLK_MQ_ALLOC_DISK #ifdef HAVE_BLK_CLEANUP_DISK blk_cleanup_disk(dev->disk); #else put_disk(dev->disk); #endif #else blk_cleanup_queue(dev->disk->queue); put_disk(dev->disk); #endif #ifdef CONFIG_SBLKDEV_REQUESTS_BASED blk_mq_free_tag_set(&dev->tag_set); #endif vfree(dev->data); kfree(dev); pr_info("simple block device was removed\\n"); } #ifdef CONFIG_SBLKDEV_REQUESTS_BASED static inline int init_tag_set(struct blk_mq_tag_set *set, void *data) { printk("%s,%d\\n",__func__,__LINE__); //设置blk_mq_ops set->ops = &mq_ops; //设置硬件队列个数 set->nr_hw_queues = 1; set->nr_maps = 1; //设置队列深度 set->queue_depth = 128; set->numa_node = NUMA_NO_NODE; set->flags = BLK_MQ_F_SHOULD_MERGE | BLK_MQ_F_STACKING; set->cmd_size = 0; set->driver_data = data; return blk_mq_alloc_tag_set(set); } #endif /* * sblkdev_add() - Add simple block device */ struct sblkdev_device *sblkdev_add(int major, int minor, char *name, sector_t capacity) { struct sblkdev_device *dev = NULL; int ret = 0; struct gendisk *disk; pr_info("add device '%s' capacity %llu sectors\\n", name, capacity); dev = kzalloc(sizeof(struct sblkdev_device), GFP_KERNEL); if (!dev) { ret = -ENOMEM; goto fail; } INIT_LIST_HEAD(&dev->link); dev->capacity = capacity; dev->data = __vmalloc(capacity << SECTOR_SHIFT, GFP_NOIO | __GFP_ZERO); if (!dev->data) { ret = -ENOMEM; goto fail_kfree; } #ifdef CONFIG_SBLKDEV_REQUESTS_BASED ret = init_tag_set(&dev->tag_set, dev); if (ret) { pr_err("Failed to allocate tag set\\n"); goto fail_vfree; } disk = blk_mq_alloc_disk(&dev->tag_set, dev); if (unlikely(!disk)) { ret = -ENOMEM; pr_err("Failed to allocate disk\\n"); goto fail_free_tag_set; } if (IS_ERR(disk)) { ret = PTR_ERR(disk); pr_err("Failed to allocate disk\\n"); goto fail_free_tag_set; } #else disk = blk_alloc_disk(NUMA_NO_NODE); if (!disk) { pr_err("Failed to allocate disk\\n"); ret = -ENOMEM; goto fail_vfree; } #endif dev->disk = disk; /* only one partition */ #ifdef GENHD_FL_NO_PART_SCAN disk->flags |= GENHD_FL_NO_PART_SCAN; #else disk->flags |= GENHD_FL_NO_PART; #endif /* removable device */ /* disk->flags |= GENHD_FL_REMOVABLE; */ disk->major = major; disk->first_minor = minor; disk->minors = 1; disk->fops = &fops; disk->private_data = dev; sprintf(disk->disk_name, name); set_capacity(disk, dev->capacity); #ifdef CONFIG_SBLKDEV_BLOCK_SIZE blk_queue_physical_block_size(disk->queue, CONFIG_SBLKDEV_BLOCK_SIZE); blk_queue_logical_block_size(disk->queue, CONFIG_SBLKDEV_BLOCK_SIZE); blk_queue_io_min(disk->queue, CONFIG_SBLKDEV_BLOCK_SIZE); blk_queue_io_opt(disk->queue, CONFIG_SBLKDEV_BLOCK_SIZE); #else blk_queue_physical_block_size(disk->queue, SECTOR_SIZE); blk_queue_logical_block_size(disk->queue, SECTOR_SIZE); #endif blk_queue_max_hw_sectors(disk->queue, BLK_DEF_MAX_SECTORS); blk_queue_flag_set(QUEUE_FLAG_NOMERGES, disk->queue); #ifdef HAVE_ADD_DISK_RESULT ret = add_disk(disk); if (ret) { pr_err("Failed to add disk '%s'\\n", disk->disk_name); goto fail_put_disk; } #else add_disk(disk); #endif pr_info("Simple block device [%d:%d] was added\\n", major, minor); return dev; #ifdef HAVE_ADD_DISK_RESULT fail_put_disk: #ifdef HAVE_BLK_MQ_ALLOC_DISK #ifdef HAVE_BLK_CLEANUP_DISK blk_cleanup_disk(dev->disk); #else put_disk(dev->disk); #endif #else blk_cleanup_queue(dev->queue); put_disk(dev->disk); #endif #endif /* HAVE_ADD_DISK_RESULT */ #ifdef CONFIG_SBLKDEV_REQUESTS_BASED fail_free_tag_set: blk_mq_free_tag_set(&dev->tag_set); #endif fail_vfree: vfree(dev->data); fail_kfree: kfree(dev); fail: pr_err("Failed to add block device\\n"); return ERR_PTR(ret); } /* * A module can create more than one block device. * The configuration of block devices is implemented in the simplest way: * using the module parameter, which is passed when the module is loaded. * Example: * modprobe sblkdev catalog="sblkdev1,2048;sblkdev2,4096" */ static int sblkdev_major; static LIST_HEAD(sblkdev_device_list); static char *sblkdev_catalog = "sblkdev1,2048;sblkdev2,4096"; /* * sblkdev_init() - Entry point 'init'. * * Executed when the module is loaded. Parses the catalog parameter and * creates block devices. */ static int __init sblkdev_init(void) { int ret = 0; int inx = 0; char *catalog; char *next_token; char *token; size_t length; sblkdev_major = register_blkdev(sblkdev_major, KBUILD_MODNAME); if (sblkdev_major <= 0) { pr_info("Unable to get major number\\n"); return -EBUSY; } length = strlen(sblkdev_catalog); if ((length < 1) || (length > PAGE_SIZE)) { pr_info("Invalid module parameter 'catalog'\\n"); ret = -EINVAL; goto fail_unregister; } catalog = kzalloc(length + 1, GFP_KERNEL); if (!catalog) { ret = -ENOMEM; goto fail_unregister; } strcpy(catalog, sblkdev_catalog); next_token = catalog; while ((token = strsep(&next_token, ";"))) { struct sblkdev_device *dev; char *name; char *capacity; sector_t capacity_value; name = strsep(&token, ","); if (!name) continue; capacity = strsep(&token, ","); if (!capacity) continue; ret = kstrtoull(capacity, 10, &capacity_value); if (ret) break; dev = sblkdev_add(sblkdev_major, inx, name, capacity_value); if (IS_ERR(dev)) { ret = PTR_ERR(dev); break; } list_add(&dev->link, &sblkdev_device_list); inx++; } kfree(catalog); if (ret == 0) return 0; fail_unregister: unregister_blkdev(sblkdev_major, KBUILD_MODNAME); return ret; } /* * sblkdev_exit() - Entry point 'exit'. * * Executed when the module is unloaded. Remove all block devices and cleanup * all resources. */ static void __exit sblkdev_exit(void) { struct sblkdev_device *dev; while ((dev = list_first_entry_or_null(&sblkdev_device_list, struct sblkdev_device, link))) { list_del(&dev->link); sblkdev_remove(dev); } if (sblkdev_major > 0) unregister_blkdev(sblkdev_major, KBUILD_MODNAME); } module_init(sblkdev_init); module_exit(sblkdev_exit); module_param_named(catalog, sblkdev_catalog, charp, 0644); MODULE_PARM_DESC(catalog, "New block devices catalog in format '<name>,<capacity sectors>;...'"); MODULE_LICENSE("GPL"); MODULE_AUTHOR("Sergei Shtepa"); 应用程序示例 #include <stdio.h> #include <unistd.h> #include <fcntl.h> void dump_f(char *buff, int len) { int i; for(i= 0; i < len ; i ++) { if(i % 21 == 0) printf("\\n"); printf("%x ", buff[i]); } printf("\\n"); } int main(int argc, char *argv[]) { int fd; char buf[4096]; int i; sleep(3); //run ./funtion.sh to trace vfs_read of this process fd = open("/dev/sblkdev1", O_RDWR); printf("fd ====:%d\\n",fd); int ch = 0; for (;;) { ch = getopt(argc, argv, "rw"); if (ch < 0) { printf("not param.\\n"); break; } switch (ch) { case 'r': printf("test read 1...............\\n"); read(fd, buf, 4096); dump_f(buf,42); sleep(2); printf("test read 2...............\\n"); read(fd, buf, 4096); dump_f(buf,42); sleep(2); printf("test read 3...............\\n"); read(fd, buf, 4096); dump_f(buf,42); sleep(2); printf("test read 4...............\\n"); read(fd, buf, 4096); dump_f(buf,42); sleep(2); printf("test read 5...............\\n"); read(fd, buf, 4096); dump_f(buf,42); while(1) sleep(4); break; case 'w': for(i=0;i<4096;i++) buf[i] = i; printf("test write 1............\\n"); write(fd, buf, 4096); sleep(3); printf("test write 2............\\n"); write(fd, buf, 4096); sleep(3); printf("test write 3............\\n"); write(fd, buf, 4096); sleep(3); printf("test write 4............\\n"); write(fd, buf, 4096); sleep(3); printf("test write 5............\\n"); write(fd, buf, 4096); sleep(3); while(1) sleep(4); break; default: printf("Not support\\n"); break; } } while(1) sleep(4); return 0; } trace脚本 debugfs=/sys/kernel/debug echo nop > $debugfs/tracing/current_tracer echo 0 > $debugfs/tracing/tracing_on echo `pidof appxxx` > $debugfs/tracing/set_ftrace_pid echo function_graph > $debugfs/tracing/current_tracer echo vfs_read > $debugfs/tracing/set_graph_function echo 1 > $debugfs/tracing/tracing_on 实验 insmod simpleblk.ko app -w & app -r & 代码分析 初始化请求队列 初始化请求队列在init_tag_set中实现，在init_tag_set函数中填充了struct blk_mq_tag_set *set数据结构，blk_mq_tag_set用于描述与存储设备相关的集合，对存储器IO特征进行的抽象。 struct blk_mq_tag_set { struct blk_mq_queue_map map[HCTX_MAX_TYPES]; 软件队列CTX到硬件队列hctx的映射表 unsigned int nr_maps; 映射表的数量 const struct blk_mq_ops *ops; 块设备驱动的mq函数操作集合 unsigned int nr_hw_queues; 块设备的硬件队列hctx数量，大多情况是1 unsigned int queue_depth; 块设备硬件队列深度 unsigned int reserved_tags; unsigned int cmd_size; 块设备驱动为每个request分配的额外空间大小 ...... }; init_tag_set中调用blk_mq_alloc_tag_set为一个或者多个请求队列分配tag和request集合。 int blk_mq_alloc_tag_set(struct blk_mq_tag_set *set) 设置硬件队列数量、映射表数量（nr_maps） ->set->nr_maps = xxx ->set->nr_hw_queues = xxx ->set->queue_depth = xxx 根据硬件队列数量拓展tags数组 ->blk_mq_alloc_tag_set_tags 更新映射表（cpu id-> hw queue id） ->ret = blk_mq_update_queue_map(set); 分配request和tag ->ret = blk_mq_alloc_map_and_requests(set); 数据处理 数据处理有两种方式，主要区别于block_device_operations中有没有实现submit_bio，如果实现了该函数文件系统下来的数据打包成bio后就直接回调该函数；如果没有实现该函数，文件系统下来的数据打包成bio后需要经过request queue进行处理，然后再派发回调到struct blk_mq_ops 注册的.queue_rq进行处理。 请求队列（request queue）里面包含一系列(request)，在reqeust里面包含bio，真正的数据就存储在bio里面，因此对数据的处理就是从request_queue中取出一个一个的reqeust，然后再从reqeust里面取出bio，在处理请求时通过blk_mq_start_request和blk_mq_end_request来开始请求和结束请求。

打开块设备 mknod 块设备同样要使用mknod创建设备节点，这与字符设备一样。会调用到init_special_inode填充inode的file_operations，只不过块设备注册的是def_blk_fops。 void init_special_inode(struct inode *inode, umode_t mode, dev_t rdev) { inode->i_mode = mode; if (S_ISCHR(mode)) { inode->i_fop = &def_chr_fops; inode->i_rdev = rdev; } else if (S_ISBLK(mode)) { inode->i_fop = &def_blk_fops; inode->i_rdev = rdev; } else if (S_ISFIFO(mode)) inode->i_fop = &pipefifo_fops; else if (S_ISSOCK(mode)) ; /* leave it no_open_fops */ else printk(KERN_DEBUG "init_special_inode: bogus i_mode (%o) for" " inode %s:%lu\\n", mode, inode->i_sb->s_id, inode->i_ino); } def_blk_fops如下，与字符设备一样，当打开块设备时，就会调用到blk_dev_open。 const struct file_operations def_blk_fops = { .open = blkdev_open, .release = blkdev_close, .llseek = blkdev_llseek, .read_iter = blkdev_read_iter, .write_iter = blkdev_write_iter, .iopoll = blkdev_iopoll, .mmap = generic_file_mmap, .fsync = blkdev_fsync, .unlocked_ioctl = block_ioctl, #ifdef CONFIG_COMPAT .compat_ioctl = compat_blkdev_ioctl, #endif .splice_read = generic_file_splice_read, .splice_write = iter_file_splice_write, .fallocate = blkdev_fallocate, } blk_dev_open blk_dev_open里面关键的操作时调用blkdev_get获取到块设备，并赋值file中f_mapping。 static int blkdev_open(struct inode *inode, struct file *filp) { struct block_device *bdev; ...... bdev = blkdev_get_by_dev(inode->i_rdev, filp->f_mode, filp); if (IS_ERR(bdev)) return PTR_ERR(bdev); filp->f_mapping = bdev->bd_inode->i_mapping; filp->f_wb_err = filemap_sample_wb_err(filp->f_mapping); return 0; } bdev文件系统 blk_dev_open调用blkdev_get_by_dev获取到块设备得bdev，获取块设备是通过bdev文件系统来查询获取，下面先来了解下bdev文件系统的注册过程。 bdev是系统注册是在系统启动初始化阶段调用bdev_cache_init注册的，每个块设备在bdev文件系统中都有一个inode，linux利用block_inode数据结构将inode和block_device进行关联起来，对设备block_device的查找转化为在bdev文件系统中对inode的查找。

块设备驱动简介 在linux系统中，有3大驱动类型，分别是：字符设备驱动、块设备驱动、网络设备驱动。块设备驱动与文件系统有着密不可分的关系，块设备是文件系统实际的数据传输单位，通常存储设备有eMMC，Nand/Nor flash，机械硬盘，固态硬盘等，这里所说的块设备驱动，实际就是这些存储设备驱动。块设备驱动与字符设备驱动有较大差异，块设备驱动是以块位单位进行读写，而字符设备驱动以字节为单位进行传输。块设备驱动可以进行随机访问，块设备驱动一般都有缓冲区来暂存数据，当对块设备进行写入时会先将数据写到缓冲区中，累计到一定数据量后才一次性刷到设备中，这样既可以提高读写的速度也可以提高快设备驱动的寿命；相对字符设备数据的操作都是字节流的方式，字符设备没有缓冲区。 关键数据结构 block_device linux系统中使用strcut block_device来表示块设备,可以表示磁盘或一个特定的分区。下面我们看一下strcut block_device数据结构，该数据结构表示块设备。 struct block_device { sector_t bd_start_sect; struct disk_stats __percpu *bd_stats; unsigned long bd_stamp; bool bd_read_only; /* read-only policy */ dev_t bd_dev; int bd_openers; struct inode * bd_inode; /* will die */ struct super_block * bd_super; void * bd_claiming; struct device bd_device; void * bd_holder; int bd_holders; bool bd_write_holder; struct kobject *bd_holder_dir; u8 bd_partno; spinlock_t bd_size_lock; /* for bd_inode->i_size updates */ struct gendisk * bd_disk; /* The counter of freeze processes */ int bd_fsfreeze_count; /* Mutex for freeze */ struct mutex bd_fsfreeze_mutex; struct super_block *bd_fsfreeze_sb; struct partition_meta_info *bd_meta_info; #ifdef CONFIG_FAIL_MAKE_REQUEST bool bd_make_it_fail; #endif } __randomize_layout; bd_dev: 该块设备（分区）的设备号 bd_inode: 设备的文件inode，bdev文件系统将通过该inode来标识块设备。 bd_disk: 指向描述整个设备的gendisk。 block_device是bdevfs伪文件系统对块设备或设备分区的抽象，它与设备号唯一对应。 gendisk linux系统中，struct gendisk是通用存储设备描述，跟具体的硬件设备关联，一个具体的硬件存储设备可以分为多个分区，而每个分区的对应用block_device描述。 struct gendisk { /* major, first_minor and minors are input parameters only, * don't use directly. Use disk_devt() and disk_max_parts(). */ int major; /* major number of driver */磁盘主设备号 int first_minor; 磁盘第一个次设备 int minors; /* maximum number of minors, =1 for 次设备的数量，也是分区数量 * disks that can't be partitioned. */ char disk_name[DISK_NAME_LEN]; /* name of major driver */ unsigned short events; /* supported events */ unsigned short event_flags; /* flags related to event processing */ struct xarray part_tbl; 对应分区表，每一项对应要给分区信息 struct block_device *part0; const struct block_device_operations *fops;磁盘操作函数集 struct request_queue *queue; 磁盘对应的请求队列，对磁盘操作的请求都放在这个队列中 void *private_data; int flags; unsigned long state; #define GD_NEED_PART_SCAN 0 #define GD_READ_ONLY 1 #define GD_DEAD 2 struct mutex open_mutex; /* open/close mutex */ unsigned open_partitions; /* number of open partitions */ struct backing_dev_info *bdi; struct kobject *slave_dir; #ifdef CONFIG_BLOCK_HOLDER_DEPRECATED struct list_head slave_bdevs; #endif struct timer_rand_state *random; atomic_t sync_io; /* RAID */ struct disk_events *ev; #ifdef CONFIG_BLK_DEV_INTEGRITY struct kobject integrity_kobj; #endif /* CONFIG_BLK_DEV_INTEGRITY */ #if IS_ENABLED(CONFIG_CDROM) struct cdrom_device_info *cdi; #endif int node_id; struct badblocks *bb; struct lockdep_map lockdep_map; u64 diskseq; } major: 存储设备的主设备号 first_minor: 存储设备的第一个次设备号 minors:存储设备的次设备号数量，也对应存储设备的分区数量。 part_tbl:存储设备对应的分区表 fops:存储设备块操作集合，与字符设备的file_operations一样。 queue:存储设备对应的请求队列，对磁盘的请求都会放到该队列中。 下面是磁盘的操作函数集合block_device_operations，与字符设备驱动file_operations类似。 struct block_device_operations { blk_qc_t (*submit_bio) (struct bio *bio); int (*open) (struct block_device *, fmode_t); void (*release) (struct gendisk *, fmode_t); int (*rw_page)(struct block_device *, sector_t, struct page *, unsigned int); int (*ioctl) (struct block_device *, fmode_t, unsigned, unsigned long); int (*compat_ioctl) (struct block_device *, fmode_t, unsigned, unsigned long); unsigned int (*check_events) (struct gendisk *disk, unsigned int clearing); void (*unlock_native_capacity) (struct gendisk *); int (*getgeo)(struct block_device *, struct hd_geometry *); int (*set_read_only)(struct block_device *bdev, bool ro); /* this callback is with swap_lock and sometimes page table lock held */ void (*swap_slot_free_notify) (struct block_device *, unsigned long); int (*report_zones)(struct gendisk *, sector_t sector, unsigned int nr_zones, report_zones_cb cb, void *data); char *(*devnode)(struct gendisk *disk, umode_t *mode); struct module *owner; const struct pr_ops *pr_ops; /* * Special callback for probing GPT entry at a given sector. * Needed by Android devices, used by GPT scanner and MMC blk * driver. */ int (*alternative_gpt_sector)(struct gendisk *disk, sector_t *sector); }; submit_bio: 对存储设备读写操作，但不一定会使用submit_bio来传输，而是通过请求队列来完成。 open: 打开指定的块设备 rw_page:读写指定的页 ioctl:块设备的I/O控制 在block_device_operations结构中不像字符设备驱动有对应的read和write函数，有些内核版本甚至没有submit_bio，对于块设备的读写操作，主要是通过request_queue，request和bio来实现的。 request_queue:内核对存储设备的读写操作会先发送到request_queue中，该队列中包含有一系列的request，在request中具体的基本单元是bio，bio保存了对存储设备读写的实际数据，包括从存储设备的那个地址读写，具体的长度等信息。 request: 存储设备的请求队列中，包含多个内核对存储设备的多个request，每个请求包含多个bio。 bio:内核对存储设备读写会构造一个或者多个的bio，bio数据结构包含了对存储设备具体的读写位置和长度等信息。 接下来将单独对三者关系进行深入描述。 bio,request,request_queue Generic Block layer 文件系统向下就是Generic Block Layer，文件系统请求读写的文件位置需要被转换到对应的存储介质的位置（如磁盘的扇区号）。如下是文件系统写过程，将写请求根据文件的pos位转化为bio。 int __block_write_begin(struct page *page, loff_t pos, unsigned len, get_block_t *get_block) -->return __block_write_begin_int(page, pos, len, get_block, NULL); -->ll_rw_block(int op, int op_flags, int nr, struct buffer_head *bhs[]) -->int submit_bh(int op, int op_flags, struct buffer_head *bh) -->submit_bio(bio) bio是块设备数据传输最小单元，下面是struct bio的数据结构。 bio_vec:标识存储设备中数据缓存在page的位置，描述IO请求在内存段的数据位置属性（page地址，页内偏移，长度）。 bvec_iter：标识操作数据在存储设备的位置，描述IO请求在存储器段的数据位置属性（起始sector，长度）。 I/O Scheduler Layer 从submit_bio调用开始，bio被block层抽象为request进行管理，request会被组织到request queue中。IO调度器的目的是在现有请求下，让尽可能少操作存储设备，提高存储设备的读写效率。在IO调度器中，从文件系统提交下来的bio被构造成request结构，一个request结构包含了多个bio，而物理存储设备都会有对应的request queue，里面存放着相关的request，新的bio可能被合并到request queue现有的request结构中，也有可能生成新的request，如何合并、插入等取决于设备驱动选择的IO调度算法。 I/O请求 早期阶段，只有一个单队列single-queue，随着多核体系结构的发展，单队列的暴露了较多劣势，如多核请求队列时，需要使用spinlock来做同步，锁的竞争带来比较高的额外开销，因此后来引入了multi-queue，将单个队列请求锁的竞争分散到多个队列中，这样就极大提高了并发IO的处理能力。 multi-queue结构分为两层队列设计，分别是Per-CPU级别的软件暂存队列（Software staging queue，Per CPU）和存储设备硬件派发队列（Hardware Dispatch queue，Per Disk Per channel）； 软件暂存队列（ctx）：对应的数据结构blk_mq_ctx,为每个cpu分配一个软件队列，将bio生成一个新的request或合并到已有的request中。bio的提交/完成处理、IO请求合并/排序/标记、调度记账等block layer操作都在该队列中进行。队列是Per CPU，所以每个CPU io请求并发的时候不存在锁竞争问题。 硬件派发队列（hctx）：对应的数据结构blk_mq_hw_ctx,每个存储设备的每个硬件队列（通常为一个）分配一个硬件派发队列，用于处理上层软件暂存队列下发的io请求。在存储设备驱动初始化时，blk-mq会将一个或多个软件暂存队列固定映射到一个硬件派发队列，后续软件队列上的io请求就会直接往映射的硬件派发队列下发,最终下发到硬件存储设备。 https://blog.csdn.net/morecrazylove/article/details/128712522 https://blog.csdn.net/juS3Ve/article/details/79890688

#include <linux/module.h> #include <linux/fs.h> #include <linux/uaccess.h> #define DEVICE_NAME "mychardev" #define BUFFER_SIZE 1024 static char device_buffer[BUFFER_SIZE]; static int open_count = 0; static int device_open(struct inode *inode, struct file *file) { if (open_count > 0) return -EBUSY; open_count++; return 0; } static int device_release(struct inode *inode, struct file *file) { open_count--; return 0; } static ssize_t device_read(struct file *file, char __user *buffer, size_t length, loff_t *offset) { int bytes_to_read; if (*offset >= BUFFER_SIZE) return 0; bytes_to_read = min(length, (size_t)(BUFFER_SIZE - *offset)); if (copy_to_user(buffer, device_buffer + *offset, bytes_to_read)) return -EFAULT; *offset += bytes_to_read; return bytes_to_read; } static ssize_t device_write(struct file *file, const char __user *buffer, size_t length, loff_t *offset) { int bytes_to_write; if (*offset >= BUFFER_SIZE) return 0; bytes_to_write = min(length, (size_t)(BUFFER_SIZE - *offset)); if (copy_from_user(device_buffer + *offset, buffer, bytes_to_write)) return -EFAULT; *offset += bytes_to_write; return bytes_to_write; } static struct file_operations fops = { .open = device_open, .release = device_release, .read = device_read, .write = device_write, }; static int __init chardev_init(void) { int ret = register_chrdev(0, DEVICE_NAME, &fops); if (ret < 0) { printk(KERN_ALERT "Failed to register char device\\n"); return ret; } printk(KERN_INFO "Char device driver registered,major:%d\\n",ret); return 0; } static void __exit chardev_exit(void) { unregister_chrdev(0, DEVICE_NAME); printk(KERN_INFO "Char device driver unregistered\\n"); } module_init(chardev_init); module_exit(chardev_exit); MODULE_LICENSE("GPL"); MODULE_AUTHOR("Your Name"); MODULE_DESCRIPTION("A simple character device driver"); 下面是一个加载字符设备驱动后的测试示例。 mknod /dev/mychardev c MAJOR_NUMBER 0 #MAJOR_NUMER为注册字符设备时获得的主设备号 echo "Hello, world!" > /dev/mychardev # 写入数据到设备 cat /dev/mychardev # 从设备读取数据 注册字符设备驱动 （1）先调用__register_chrdev_region分配一个strcut char_device_strcut的实例，这个实例表示一个字符设备驱动，在函数中会填充cd数据结构。系统为了管理设备，为每个设备编了号，每个设备又分为主设备号和次设备号，主设备号用来区分不同类似的设备，而次设备号用来区分同一类型的多个设备，如IIC驱动的主设备号是100，IIC有3个设备IIC-0，IIC-1，IIC-2，这3个设备共用一套驱动。可以通过cat /proc/devices 查看已加载的驱动设备主设备号。 static struct char_device_struct { struct char_device_struct *next; //指向下一个字符设备 unsigned int major; //主设备号 unsigned int baseminor; //次设备起始值 int minorct; //次设备数量 char name[64]; //设备或驱动的名称 struct cdev *cdev; /* will die */ } *chrdevs[CHRDEV_MAJOR_HASH_SIZE]; （2）调用cdev_alloc分配设备一个cdev实例，cdev描述了一个字符设备。 struct cdev { struct kobject kobj; //内核对象，通过他将设备统一加到设备驱动模型中管理 struct module *owner; const struct file_operations *ops; //文件系统与设备直接的操作函数集合 struct list_head list;//所有的字符设备驱动形成链表 dev_t dev; //字符设备的设备号，由主设备和次设备构成 unsigned int count; } __randomize_layout; （3）填充用户注册的驱动函数操作集合，用户注册的open/read/write等函数，这是文件系统与设备的沟通桥梁。 （4）将cdev添加到strutct kobj_map *cdev_map全局列表中，kobj_map中有255个probe，每个probe对应一个主设备，相当于字符设备的数量不能超过255。每个主设备下可以由多个次设备。 创建设备节点 insmod加载完成驱动后，通常需要使用mknod创建一个设备节点，这样用户就可以通过文件系统节点的方式访问设备，下面是mknod的使用示例。 mknod /dev/xxx 设备类型 主设备号 从设备号 从上图的流程图可知，/dev是挂载了tmpfs类型的文件系统。在系统启动初始化的时候会调用shmem_init注册一个tmpfs类型的文件系统。 在使用mknode在/dev下创建设备驱动节点，与前面文件系统创建一个新文件类似，关键点就是为文件创建一个dentry和inode，然后填充inode对应的数据，我们需要重点关注的是inode填充的i_fop的操作函数集合是def_chr_fops，这个file_operations对应的open是chardev_open，因此后续在用户打开文件时将会调用到该函数。 驱动系统调用 上一小节中，使用mknod创建设备节点时，inode->i_fop填充的是def_char_fops，在文件系统打开时就会调用到chrdev_open函数，打开的流程与前面分析的流程一致，这里就不再分析了，我们这里重点关注跟设备驱动相关的差异。chrdev_open函数如下： static int chrdev_open(struct inode *inode, struct file *filp) { const struct file_operations *fops; struct cdev *p; struct cdev *new = NULL; int ret = 0; spin_lock(&cdev_lock); p = inode->i_cdev; //获取文件对应的cdev，如果为空则需要进行查找。 if (!p) { struct kobject *kobj; int idx; spin_unlock(&cdev_lock); kobj = kobj_lookup(cdev_map, inode->i_rdev, &idx); //从cdev_map中查找kobj if (!kobj) return -ENXIO; new = container_of(kobj, struct cdev, kobj);//获取到cdev spin_lock(&cdev_lock); /* Check i_cdev again in case somebody beat us to it while we dropped the lock. */ p = inode->i_cdev; if (!p) { inode->i_cdev = p = new; //将cdev赋值给inode list_add(&inode->i_devices, &p->list);//将inode添加到设备列表中 new = NULL; } else if (!cdev_get(p)) ret = -ENXIO; } else if (!cdev_get(p)) ret = -ENXIO; spin_unlock(&cdev_lock); cdev_put(new); if (ret) return ret; ret = -ENXIO; fops = fops_get(p->ops); //获取驱动注册的file_operations if (!fops) goto out_cdev_put; replace_fops(filp, fops); //将struct file中的f_op更新跟驱动的注册的file_operations if (filp->f_op->open) { ret = filp->f_op->open(inode, filp); //调用驱动注册的open函数 if (ret) goto out_cdev_put; } return 0; out_cdev_put: cdev_put(p); return ret; } chrdev_open函数关键的作用先从cdev_map中找到设备的cdev，然后填充到inode中，这样下次操作设备文件节点时就不用再查找了，接下来非常关键的作用是将strcut file中的f_op由原来inode->i_fop指向的file_operations(def_chr_fops)替换为驱动注册的file_operations，这样后续用户在进程中再操作该文件节点时，对文件的open/read/write等操作经过VFS后就直接调用到驱动注册的file_opearations操作集合了，不会再经过def_chr_fops。

上一章节中，我们编写了没有带磁盘设备的文件系统，了解了文件系统操作的大致流程，本章节我们继续在上一章节的基础上完善文件系统，并梳理从用户空间到内核空间大致的调用流程。实验的代码我们使用开源的示例https://github.com/sysprog21/simplefs/tree/master，在启动本章节之前建议先搭建好试验环境，将simplefs挂载起来，当然有余力的也可以在上一节示例代码的基础上借鉴开源的示例补全。 mount 挂载文件系统有两个关键点 创建一个VFS struct super_block的实例，并从磁盘中读取磁盘super_block信息填充，同时分配一个根inode从磁盘中读取信息填充，并创建根inode对应的根dentry。 创建一个struct mount实例（包含了struct vfsmount）以及挂载点struct mountpoint实例，并添加到全局文件系统的hash表中，建立起文件系统树的联系。 下面是第一个关键点的流程和数据结构直接的关系。 mount_bdev主要做了3件事情，第一调用blkdev_get_by_path根据/dev/xxx名字找到相应的设备并打开它，第二调用sget根据打开的设备，查询是否有对应磁盘的supper_block，如果没有就分配一个。第三调用fill_super回调函数填充super_block。文件系统建立起来之后，对文件的读写就通过文件系统来进行。 以下是第二个关键点数据结构实例直接的联系 跨文件系统路径解析 path_lookupat link_path_walk walk_component step_into handle_mounts traverse_mounts __traverse_mounts(struct path *path, ......) { while (flags & DCACHE_MANAGED_DENTRY) { ...... if (flags & DCACHE_MOUNTED) { // 目录是挂载点？ struct vfsmount *mounted = lookup_mnt(path); //获取vfsmount if (mounted) { // ... in our namespace dput(path->dentry); if (need_mntput) mntput(path->mnt); path->mnt = mounted; //填充新的vfsmount path->dentry = dget(mounted->mnt_root);//新文件系统的根目录 // here we know it's positive flags = path->dentry->d_flags; need_mntput = true; continue; } } ...... } } 文件系统挂载后创建super_block、mount、mountpoint、根inode、根dentry对象。 一个目录可以被多个文件系统挂载，新挂载的文件系统会导致之前的挂载被隐藏。 一个目录被文件系统挂载后，原来目录的其他子目录和文件会被隐藏。 每次挂载都会有一个mount实例描述本次挂载。 open 先调用get_ununsed_fd_flags获取一个空闲的fd。 调用link_path_walk对路径名进行查找，里面是个循环会使用”/”分隔逐层处理，如果依次解析发现子目录是新的文件系统（相当于从A文件系统跨到B文件系统）则进行更新path，path中存储了vfsmount和dentry。文件/mnt/simplefs/test，link_path_walk会解析前面得路径部分/mnt/simplefs，解析完毕得时候nameidata的dentry为路径名的最后一部分的父目录/mnt/simplefs，而nameidata->filename为路径名的最后一部分”test”。再查找文件路径最后一部分对应的dentry，linux为了提高目录项目对象的处理效率，实现了一个目录项的高速换成dentry cache，查询的时候先从缓存中查找，调用的是lookup_fast，如果缓存没有找到就调用到对应的文件系统中去照，对应的是上一级目录inode的inode_operations->lookup函数，最终将找到后的新生成的dentry赋值到path中。 最后调用do_open下陷到f->f_op->open调用到具体的文件系统中，在vfs_open中也会将文件相关的信息填充到struct file中，如f->f_inode，f->f_mapping等。 write 用户空间write通过系统调用进入到内核层vfs_write，在vfs_write中判断是struct file_operations填充的是write还是write_iter，这里选择的是write_iter，在simplefs文件系统中write_iter注册的是通用写generic_file_write_iter，在这个函数中会根据标志IOCB_DIRECT判断写如是否要经过缓存。 缓存是内存中的一块内存，Linux为了进一步改进性能，默认情况下不会直接操作硬盘，而是读写都在内存中，待一定时机后在一并批量写入磁盘，以提高读写效率。根据是否使用内存作为缓存，可以把文件的I/O操作分为缓存I/O和直接I/O，直接I/O的方式是不经过缓存。 默认情况为了提高写效率都会调用generic_perform_write使用缓存I/O的方式写入，在generic_perform_write中分为四个步骤： 调用具体文件系统注册的write_begin，在该函数中，如果是日志式的文件系统会先记录相关日志，这里的simplefs文件系统不带日志系统。另外重要的事情就是获取page页，在struct file中有一个成员struct address_space，struct address_space->i_pages是一个xarray树，磁盘的内容映射到这颗树上。在准备写入数据时，会从树中查询是否有对应个page，如果有则获取到该page，如果没有则重新分配一个page，添加到树上。 获得page后，调用copy_page_from_iter_atomic将用户空间数据写到page中。 数据写到page后，将对用的page设置为脏页，脏页的数据是需要定期同步到磁盘的。 最后在balance_dirty_pages_ratelimited会检查是否要进行缓存数据的刷写，可以看出在每次写缓存时，都会调用该函数来检查一下页缓存的总容量，如果超过设定的阈值就会立即触发wb_workfn进行写入到磁盘。平时用的sync也是，将缓存与磁盘进行同步。 论O_DIRECT和O_SYNC? read 大体流程跟write的类似，我们重点看唤醒I/O读的方式，通过filemap_get_pages获取page，如果没有找到不但读取一页，还有进行预读，调用page_cache_sync_readahead函数发起预读操作，这次预读的操作应该是在原来的page缓存基础上发起预读补充，预读后再进行判断是否找到要读数据对应的page，如果还是没有则直接分配一个page添加到树上，然后从磁盘中读取数据填充，接着判断一下page的数据是否填满需要预读，如果需要则发起一次异步预读操作。最后找到要读数据对应的page后，调用copy_page_to_iter将数据拷贝到用户空间。

文件系统注册与挂载 static struct file_system_type simplefs_fs_type = { .owner = THIS_MODULE, .name = "simplefs", .mount = simplefs_mount, .kill_sb = simplefs_kill_sb, }; static int __init init_simplefs(void) { return register_filesystem(&simplefs_fs_type); } 调用register_filesystem注册一个文件系统，传入参数为file_system_type结构体，用于描述文件系统类型，其中name为文件系统的名称，在使用mount -t xxx指定文件系统类型是即为该名称，使用cat /proc/filesystems可以查询linux系统中所有注册的文件系统类型。file_system_type中mount和kill_sb分别对应mount和umount的操作。 static struct dentry *simplefs_mount(struct file_system_type *fs_type, int flags, const char *dev_name, void *data) { return mount_nodev(fs_type, flags, data, simplefs_fill_super); } 在执行mount是会触发simplefs_mount调用，该函数中调用mount_nodev来mount一个文件系统，mount_nodev表示该文件系统没有对应的磁盘，对应mount -t xxx none /xxx的命令，通常情况下对应直接使用内存作为存储空间的使用该函数来进行，类似的还有如tmpfs，devfs等。而如果挂载的文件系统存储介质对应磁盘需调用mount_bdev，对应具体的磁盘设备，对应的命令mount -t ext4 /dev/xxx /xxx命令。 上面示例中，mount_nodev中其中重要的参数simplefs_fill_super，在执行mount_nodev会回调该函数，原义为用于填充超级块对象，同时创建根目录的inode信息，完成inode和dentry的初始化关联。在挂载文件系统时，在fill_super中完成了根目录inode的初始化，填充inode的函数操作集合，后续访问数据时就可以通过该inode函数操作集合来对文件访问。 static int simplefs_fill_super(struct super_block *sb, void *data, int silent) { struct inode *root; struct dentry *root_dentry; sb->s_magic = SIMPLEFS_MAGIC_NUMBER; root = simplefs_get_inode(sb, NULL, S_IFDIR | 0755); if (!root) { printk("get inode failed\\n"); return -ENOMEM; } root_dentry = d_make_root(root); if (!root_dentry) { iput(root); printk("make root failed\\n"); return -ENOMEM; } sb->s_root = root_dentry; return 0; } 调用simplefs_get_inode获取一个新的inode节点，然后调用用d_make_root生成inode对应的dentry，再将dentry赋值给sb->s_root即可完成根目录的挂载，后续切到当前的目录，相应的操作就转为当前文件系统类型的操作。 static struct inode *simplefs_get_inode(struct super_block *sb, const struct inode *dir, umode_t mode) { struct inode *inode; inode = new_inode(sb); if (inode) { inode->i_ino = get_next_ino(); inode->i_sb = sb; inode_init_owner(&init_user_ns, inode, dir, mode); inode->i_op = &simplefs_dir_inode_ops; inode->i_atime = inode->i_mtime = inode->i_ctime = current_time(inode); switch (mode & S_IFMT) { case S_IFDIR: inode->i_fop = &simplefs_dir_ops; break; case S_IFREG: inode->i_fop = &simplefs_file_ops; default: break; } } return inode; } 上面是创建一个新的inode示例，inode用于描述一个文件或目录。调用new_node来分配一个新的inode，接着对inode进行基本的初始化，其中最重要的是填充inode->i_op和inode->i_fop。 static struct inode_operations simplefs_dir_inode_ops = { .lookup = simplefs_lookup, .create = simplefs_create, .unlink = simplefs_unlink, }; inode->i_op是inode的函数操作方法，上面示例lookup用于查找dentry是否存在，dentry是关于文件路径的描述，包括文件和目录，通过指定的文件路径名进行搜索是否存在找到对应dentry，dentry中的数据结构关联了inode，进而实现通过dentry找到对应的inode。create对应的是文件或目录的创建，unlink是文件的删除。 static struct file_operations simplefs_dir_ops = { .owner = THIS_MODULE, .iterate = simplefs_iterate, }; static struct file_operations simplefs_file_ops = { .read = simplefs_read_file, .write = simplefs_write_file, }; inode->i_fop就是实际对文件的操作，与struc file->f_op相关联。这里区分目录和文件，如果inode是目录的话，那么目录存储的是目录下各个文件或目录的信息，所以重点的操作函数是遍历目录对应上面的simplefs_iterate。而inode是文件的话，主要的操作就是对文件具体的读或者写。 文件创建与删除 在文件系统注册章节，执行mount文件系统操作后，回调了填充super函数，在该函数中创建了一个根目录，后续对应文件或目录的创建就可以基于这个根目录进行拓展。根目录对应一个inode，inode填充了i_fop操作函数，因此当我们创建文件时，就会调用对应的操作函数create。 static int simplefs_create (struct user_namespace *ns, struct inode *dir,struct dentry *dentry, umode_t mode, bool excl) { struct inode *inode; struct simplefs_file *s_file; int block = -1; if (strlen(dentry->d_name.name) > SIMPLEFS_FILENAME_LEN) return -ENAMETOOLONG; //分配一个新的inode inode = simplefs_get_inode(dir->i_sb, dir, mode); if (!inode) { printk("get new inode faild\\n"); return -ENOSPC; } block = simplefs_get_block(i_block); if (block < 0) return -ENOSPC; s_file = kmalloc(sizeof(struct simplefs_file), GFP_KERNEL); s_file->inode = inode->i_ino; s_file->mode = mode; strcpy(s_file->filename, dentry->d_name.name); i_block[block].data = s_file; dir->i_mtime = dir->i_ctime = current_time(dir); //将新分配的inode填充到当前目录项 d_instantiate(dentry, inode); return 0; } crate入参函数中，dir为父目录的inode，dentry为新创建的dentry，没有关联inode，需要在该函数中新创建一个inode，最后调用d_instantiate与新创建的inode进行关联。因此在create操作中，主要的工作就是创建一个新的inode，然后调用d_instantiate将这个inode与dentry进行关联。dentry应该是在上级调用的时候就创建了。 目录遍历 当我们在执行ll或ls命令的时候，会列出当前目录下有那些文件或目录，这个操作就会调用file_operations中iterate成员函数。 static int simplefs_iterate (struct file *dir, struct dir_context *ctx) { struct simplefs_file *f = NULL; int i; if (ctx->pos >= SIMPLEFS_BLOCK_SIZE +2) return 0; if (!dir_emit_dots(dir, ctx)) // . .. return 0; for (i = 0; i < SIMPLEFS_BLOCK_SIZE; i++) { ctx->pos ++; if (!i_block[i].use) continue; f = (struct simplefs_file *)i_block[i].data; if (f && !dir_emit(ctx, f->filename, SIMPLEFS_FILENAME_LEN, f->inode, DT_UNKNOWN)) break; } return 0; } 上面示例中，关于iterate的实现最关键的是调用dir_emit将文件名或文件列到屏幕上显示。 文件读写 文件的读写调用的是file_operations中read和write函数。 static ssize_t simplefs_write_file(struct file *f, const char __user *buf, size_t len, loff_t *ppos) { struct inode *inode = file_inode(f); struct blks_desc *blk_desc = (struct blks_desc *)inode->i_private; int newdatalen = *ppos + len; char *newdata; int i; if (!buf || len == 0) { return -EINVAL; } if (!blk_desc) { i = simplefs_get_block(d_block); if (i < 0) return -ENOSPC; else { blk_desc = inode->i_private = &d_block[i]; d_block[i].use = 1; } } newdata = krealloc(blk_desc->data, newdatalen, GFP_KERNEL); if (!newdata) return -ENOMEM; if (copy_from_user(newdata + *ppos, buf, len)) return -EFAULT; blk_desc->data = newdata; *ppos += len; blk_desc->size = *ppos; return len; } static ssize_t simplefs_read_file(struct file *f, char __user *buf, size_t len, loff_t *ppos) { struct inode *inode = file_inode(f); struct blks_desc *blk_desc = (struct blks_desc *)inode->i_private; ssize_t ret = 0; if (!blk_desc) { ret = -EINVAL; goto out; } printk("%s,%d\\n",__func__,__LINE__); if (*ppos >= blk_desc->size) return 0; len = min((size_t) blk_desc->size, len); if (copy_to_user(buf, blk_desc->data + *ppos, len)) { ret = -EFAULT; goto out; } *ppos += len; ret = len; out: return ret; } 读写函数就比较简单了，因为没有操作具体的磁盘文件，所以直接调用copy_to/from_user从用户空间到内核空间的数据搬运，实际的文件操作系统中尤其涉及磁盘的操作会复杂不少，会涉及到page cache相关的操作，本章节只是简单介绍下概念有个整体的认识，后续章节我们会具体再介绍。 小结 最后编译生成ko文件加载到内核中，就可以测试了，下面是测试命令。 insmod simplefs.ko mkdir -p /mnt/simplefs mount -t simplefs none /mnt/simplefs cd /mnt/simplefs touch a echo 11111 > a cat a ll 以下是基于linux5.15完整的测试代码: #include <linux/module.h> #include <linux/fs.h> #include <linux/pagemap.h> #include <linux/slab.h> #include <linux/init.h> #include <linux/namei.h> #define SIMPLEFS_FILENAME_LEN 255 #define SIMPLEFS_BLOCK_SIZE 255 struct simplefs_file { unsigned long inode; umode_t mode; char filename[SIMPLEFS_FILENAME_LEN]; }; struct blks_desc { void *data; uint32_t size; uint8_t use; }; static struct blks_desc i_block[SIMPLEFS_BLOCK_SIZE]; static struct blks_desc d_block[SIMPLEFS_BLOCK_SIZE]; #define SIMPLEFS_MAGIC_NUMBER 0x13131313 MODULE_IMPORT_NS(VFS_internal_I_am_really_a_filesystem_and_am_NOT_a_driver); static struct file_operations simplefs_dir_ops; static struct file_operations simplefs_file_ops; static struct inode_operations simplefs_dir_inode_ops; static int simplefs_get_block(struct blks_desc *blks) { int i; for (i = 0; i < SIMPLEFS_BLOCK_SIZE; i++) { if (!blks[i].use) { blks[i].use = 1; return i; } } return -1; } static struct inode *simplefs_get_inode(struct super_block *sb, const struct inode *dir, umode_t mode) { struct inode *inode; inode = new_inode(sb); if (inode) { inode->i_ino = get_next_ino(); inode->i_sb = sb; inode_init_owner(&init_user_ns, inode, dir, mode); inode->i_op = &simplefs_dir_inode_ops; inode->i_atime = inode->i_mtime = inode->i_ctime = current_time(inode); switch (mode & S_IFMT) { case S_IFDIR: inode->i_fop = &simplefs_dir_ops; break; case S_IFREG: inode->i_fop = &simplefs_file_ops; default: break; } } return inode; } static int simplefs_create (struct user_namespace *ns, struct inode *dir,struct dentry *dentry, umode_t mode, bool excl) { struct inode *inode; struct simplefs_file *s_file; int block = -1; if (strlen(dentry->d_name.name) > SIMPLEFS_FILENAME_LEN) return -ENAMETOOLONG; inode = simplefs_get_inode(dir->i_sb, dir, mode); if (!inode) { printk("get new inode faild\\n"); return -ENOSPC; } block = simplefs_get_block(i_block); if (block < 0) return -ENOSPC; s_file = kmalloc(sizeof(struct simplefs_file), GFP_KERNEL); s_file->inode = inode->i_ino; s_file->mode = mode; strcpy(s_file->filename, dentry->d_name.name); i_block[block].data = s_file; dir->i_mtime = dir->i_ctime = current_time(dir); d_instantiate(dentry, inode); return 0; } static int simplefs_unlink (struct inode *dir,struct dentry *dentry) { int i; struct simplefs_file *s_file; struct inode *inode = dentry->d_inode; struct blks_desc *blk_desc = (struct blks_desc *)inode->i_private; if (blk_desc && blk_desc->data) { kfree(blk_desc->data); blk_desc->use = 0; } for (i = 0; i < SIMPLEFS_BLOCK_SIZE; i++) { if (i_block[i].use) { s_file = (struct simplefs_file *) i_block[i].data; if (!strcmp(s_file->filename, dentry->d_name.name)) { kfree(s_file); i_block[i].data = NULL; i_block[i].use = 0; drop_nlink(inode); } } } return 0; } static struct dentry *simplefs_lookup (struct inode *parent_inode, struct dentry *child_dentry, unsigned int flags) { int i; for (i = 0 ; i < SIMPLEFS_BLOCK_SIZE; i ++) { struct simplefs_file *f = (struct simplefs_file *)i_block[i].data; if (f && !strcmp(f->filename, child_dentry->d_name.name)) { struct inode *inode = simplefs_get_inode(parent_inode->i_sb, parent_inode, f->mode); d_add(child_dentry, inode); return NULL; } } return NULL; } static ssize_t simplefs_read_file(struct file *f, char __user *buf, size_t len, loff_t *ppos) { struct inode *inode = file_inode(f); struct blks_desc *blk_desc = (struct blks_desc *)inode->i_private; ssize_t ret = 0; if (!blk_desc) { ret = -EINVAL; goto out; } if (*ppos >= blk_desc->size) return 0; len = min((size_t) blk_desc->size, len); if (copy_to_user(buf, blk_desc->data + *ppos, len)) { ret = -EFAULT; goto out; } *ppos += len; ret = len; out: return ret; } static ssize_t simplefs_write_file(struct file *f, const char __user *buf, size_t len, loff_t *ppos) { struct inode *inode = file_inode(f); struct blks_desc *blk_desc = (struct blks_desc *)inode->i_private; int newdatalen = *ppos + len; char *newdata; int i; if (!buf || len == 0) { return -EINVAL; } if (!blk_desc) { i = simplefs_get_block(d_block); if (i < 0) return -ENOSPC; else { blk_desc = inode->i_private = &d_block[i]; d_block[i].use = 1; } } newdata = krealloc(blk_desc->data, newdatalen, GFP_KERNEL); if (!newdata) return -ENOMEM; if (copy_from_user(newdata + *ppos, buf, len)) return -EFAULT; blk_desc->data = newdata; *ppos += len; blk_desc->size = *ppos; return len; } static int simplefs_iterate (struct file *dir, struct dir_context *ctx) { struct simplefs_file *f = NULL; int i; if (ctx->pos >= SIMPLEFS_BLOCK_SIZE +2) return 0; if (!dir_emit_dots(dir, ctx)) // . .. return 0; for (i = 0; i < SIMPLEFS_BLOCK_SIZE; i++) { ctx->pos ++; if (!i_block[i].use) continue; f = (struct simplefs_file *)i_block[i].data; if (f && !dir_emit(ctx, f->filename, SIMPLEFS_FILENAME_LEN, f->inode, DT_UNKNOWN)) break; } return 0; } static int simplefs_fill_super(struct super_block *sb, void *data, int silent) { struct inode *root; struct dentry *root_dentry; sb->s_magic = SIMPLEFS_MAGIC_NUMBER; root = simplefs_get_inode(sb, NULL, S_IFDIR | 0755); if (!root) { printk("get inode failed\\n"); return -ENOMEM; } root_dentry = d_make_root(root); if (!root_dentry) { iput(root); printk("make root failed\\n"); return -ENOMEM; } sb->s_root = root_dentry; return 0; } static struct dentry *simplefs_mount(struct file_system_type *fs_type, int flags, const char *dev_name, void *data) { return mount_nodev(fs_type, flags, data, simplefs_fill_super); } static void simplefs_kill_sb(struct super_block *sb) { kill_anon_super(sb); } static struct file_operations simplefs_dir_ops = { .owner = THIS_MODULE, .iterate = simplefs_iterate, }; static struct file_operations simplefs_file_ops = { .read = simplefs_read_file, .write = simplefs_write_file, }; static struct file_system_type simplefs_fs_type = { .owner = THIS_MODULE, .name = "simplefs", .mount = simplefs_mount, .kill_sb = simplefs_kill_sb, }; static int __init init_simplefs(void) { return register_filesystem(&simplefs_fs_type); } static void __exit exit_simplefs(void) { unregister_filesystem(&simplefs_fs_type); } module_init(init_simplefs); module_exit(exit_simplefs); MODULE_LICENSE("Dual BSD/GPL"); MODULE_AUTHOR("Laumy"); MODULE_DESCRIPTION("a simple file system"); 更完善的文件系统示例：https://github.com/sysprog21/simplefs/tree/master，一个简单的文件系统主要就是围绕四大对象进行填充描述，而超级块和inode是基础。 分配超级块结构，填充超级块信息。 定义具体文件系统inode，如struct ext4_inode。其中每个具体的文件系统inode会内嵌一个VFS inode，具体文件系统的inode在.alloc_inode中分配。 实现类型文件系统inode的操作函数集合，包括创建目录/文件。 实现file操作函数集合，包括目录遍历，文件的读写操作等。 实现文件与磁盘的映射address space操作集合。

Linux系统中支持多种不同的文件系统，为了是用户可以通过一个文件系统操作界面，对各种不同的文件系统进行操作，在具体的文件系统（ext2/ext4等）之上增加了一层抽象一个统一的虚拟文件系统界面，向上提供归一化的文件操作，这个抽象层就称为虚拟文件系统。 为了实现抽象层，Linux内核定义了4个重要的数据结构对象。 supper block: 管理文件系统的相关描述信息。 Inode:一个文件对应一个inode，包含文件的相关信息，包括文件大小、创建时间、块大小等。 Dentry:表示一个目录项。 File:进程打开的文件。 上面4个对象都有对应的函数操作方法 supper_operations:文件系统的操作方法，如read_inode inode_operations:文件的操作方法，如create、link。 dentry_operations:目录项的操作方法，如d_compare、d_delete。 file:进程打开文件后的操作方法，如read、write。 四大对象数据结构 超级块对象 超级块，用于描述设备上的文件系统的总体信息如块大小、文件大小上限、文件系统类型、挂载点信息等。在构建一个文件系统时，内核会从存储设备特定位置获取相关的控制信息来填充内存中的超级块对象，当构建完成一个文件系统时就会对应一个超级块对象。 struct super_block include/linux/fs.h struct super_block { struct list_head s_list; /* Keep this first */ dev_t s_dev; /* search index; _not_ kdev_t */ unsigned char s_blocksize_bits; unsigned long s_blocksize; loff_t s_maxbytes; //文件大小上限 struct file_system_type *s_type; //文件系统类型 const struct super_operations *s_op; //超级块的方法 const struct dquot_operations *dq_op;//磁盘限额的方法 const struct quotactl_ops *s_qcop; const struct export_operations *s_export_op; unsigned long s_flags; unsigned long s_iflags; /* internal SB_I_* flags */ unsigned long s_magic; struct dentry *s_root; //文件系统目录挂载点 struct rw_semaphore s_umount; const struct dentry_operations *s_d_op; /* default d_op for dentries */ struct block_device *s_bdev; //对应的块设备，在文件系统mount调用mount_bdev时会根据设备的 名称找到对应的bdev填充，得到块设备描述后后续就可以调用s_read/s_write等操作块设备。 ...... } struct super_operations include/linux/fs.h struct super_operations { struct inode *(*alloc_inode)(struct super_block *sb); //在给定超级块下创建并初始化一个inode，inode即对应一个目录或文件的实例。 void (*destroy_inode)(struct inode *); void (*free_inode)(struct inode *); void (*dirty_inode) (struct inode *, int flags); int (*write_inode) (struct inode *, struct writeback_control *wbc); //指定索引点写磁盘 int (*drop_inode) (struct inode *); void (*evict_inode) (struct inode *); void (*put_super) (struct super_block *); int (*sync_fs)(struct super_block *sb, int wait); //文件系统与磁盘上的数据同步 int (*freeze_super) (struct super_block *); int (*freeze_fs) (struct super_block *); int (*thaw_super) (struct super_block *); int (*unfreeze_fs) (struct super_block *); int (*statfs) (struct dentry *, struct kstatfs *); int (*remount_fs) (struct super_block *, int *, char *); void (*umount_begin) (struct super_block *); int (*show_options)(struct seq_file *, struct dentry *); int (*show_devname)(struct seq_file *, struct dentry *); int (*show_path)(struct seq_file *, struct dentry *); int (*show_stats)(struct seq_file *, struct dentry *); #ifdef CONFIG_QUOTA ssize_t (*quota_read)(struct super_block *, int, char *, size_t, loff_t); ssize_t (*quota_write)(struct super_block *, int, const char *, size_t, loff_t); struct dquot **(*get_dquots)(struct inode *); #endif long (*nr_cached_objects)(struct super_block *, struct shrink_control *); long (*free_cached_objects)(struct super_block *, struct shrink_control *); }; 索引节点对象 Inode对象代表了一个实际的文件，当文件被访问前需要先获取到该文件的inode，struct inode结构体包含了通用的属性和方法，如文件类型，文件大小，权限，创建时间等信息。 struct inode include/linux/fs.h struct inode { umode_t i_mode;//访问权限 unsigned short i_opflags; kuid_t i_uid; kgid_t i_gid; unsigned int i_flags; //文件系统标志 #ifdef CONFIG_FS_POSIX_ACL struct posix_acl *i_acl; struct posix_acl *i_default_acl; #endif const struct inode_operations *i_op; //索引节点的操作方法 struct super_block *i_sb; //所属超级块 struct address_space *i_mapping; //文件缓存 ...... union { const struct file_operations *i_fop; /* former ->i_op->default_file_ops */ void (*free_inode)(struct inode *); }; struct file_lock_context *i_flctx; struct address_space i_data; struct list_head i_devices; ...... } struct inode_operations include/linux/fs.h struct inode_operations { struct dentry * (*lookup) (struct inode *,struct dentry *, unsigned int); //在指定目录下搜索目录项，要获取inode，需要先获取dentry const char * (*get_link) (struct dentry *, struct inode *, struct delayed_call *); int (*permission) (struct user_namespace *, struct inode *, int); struct posix_acl * (*get_acl)(struct inode *, int, bool); int (*readlink) (struct dentry *, char __user *,int); int (*create) (struct user_namespace *, struct inode *,struct dentry *, umode_t, bool); //create或open系统调用创建或打开文件 int (*link) (struct dentry *,struct inode *,struct dentry *); int (*unlink) (struct inode *,struct dentry *); int (*symlink) (struct user_namespace *, struct inode *,struct dentry *, const char *); int (*mkdir) (struct user_namespace *, struct inode *,struct dentry *, umode_t);//创建目录 int (*rmdir) (struct inode *,struct dentry *);//删除目录 int (*mknod) (struct user_namespace *, struct inode *,struct dentry *, umode_t,dev_t);//创建管道、设备等特殊文件 int (*rename) (struct user_namespace *, struct inode *, struct dentry *, struct inode *, struct dentry *, unsigned int); int (*setattr) (struct user_namespace *, struct dentry *, struct iattr *); int (*getattr) (struct user_namespace *, const struct path *, struct kstat *, u32, unsigned int); ssize_t (*listxattr) (struct dentry *, char *, size_t); int (*fiemap)(struct inode *, struct fiemap_extent_info *, u64 start, u64 len); int (*update_time)(struct inode *, struct timespec64 *, int); int (*atomic_open)(struct inode *, struct dentry *, struct file *, unsigned open_flag, umode_t create_mode); int (*tmpfile) (struct user_namespace *, struct inode *, struct dentry *, umode_t); int (*set_acl)(struct user_namespace *, struct inode *, struct posix_acl *, int); int (*fileattr_set)(struct user_namespace *mnt_userns, struct dentry *dentry, struct fileattr *fa); int (*fileattr_get)(struct dentry *dentry, struct fileattr *fa); } ____cacheline_aligned; 在VFS层定义了通用的struct inode，在具体的文件系统中可能还会定义属于具体文件系统的inode，如struct ext2_inode、struct ext4_inode，这些xxx_inode是对具体文件的描述如元数据相关信息即具体文件系统磁盘信息的描述，在分配struct inode时，会将xxx_inode的值赋值到struct inode中。其他像超级块，目录等对象也类似。 目录项对象 dentry虽翻译为目录项，但和文件系统中的目录并不是同一个概念，dentry属于文件系统的对象，包括目录、文件等，反映的是文件系统对象在内核中所在文件系统树的位置。每个文件除了有inode，同时也会有一个dentry结构，记录了文件的名称，父目录，子目录等信息，形成我们看到的层级树状结构。与inode不同时，dentry只存在于内存，磁盘上并没有对应的实体文件，因此目录项目不会涉及回写磁盘的操作。 dentry其中重要的是对文件搜索找出对应的文件的inode。遍历目录时比较耗时的，为了加快遍历和查找，内核中使用hash表来缓存dentry。 一个路径的各个组成部分，不管目录还是普通的文件，都是一个dentry对象，如/home/test.c，/，home,test.c都是一个目录项。为了增加搜索效率，这些目录项目缓存到hash表中。 struct dentry include/linux/dcache.h struct dentry { /* RCU lookup touched fields */ unsigned int d_flags; /* protected by d_lock */ seqcount_spinlock_t d_seq; /* per dentry seqlock */ struct hlist_bl_node d_hash; //用于目录项目查找的hash表 struct dentry *d_parent; //父目录项 struct qstr d_name; //目录项目名称 struct inode *d_inode; //目录项关联的索引节点 unsigned char d_iname[DNAME_INLINE_LEN]; /* small names */ /* Ref lookup also touches following */ struct lockref d_lockref; /* per-dentry lock and refcount */ const struct dentry_operations *d_op; struct super_block *d_sb; /* The root of the dentry tree */ unsigned long d_time; /* used by d_revalidate */ void *d_fsdata; /* fs-specific data */ 具体文件系统中内存目录项目。 union { struct list_head d_lru; /* LRU list */ wait_queue_head_t *d_wait; /* in-lookup ones only */ }; struct list_head d_child; /* child of parent list */ struct list_head d_subdirs; /* our children */ /* * d_alias and d_rcu can share memory */ union { struct hlist_node d_alias; /* inode alias list */ struct hlist_bl_node d_in_lookup_hash; /* only for in-lookup ones */ struct rcu_head d_rcu; } d_u; ANDROID_KABI_RESERVE(1); ANDROID_KABI_RESERVE(2); } __randomize_layout; struct dentry include/linux/dcache.h struct dentry_operations { int (*d_revalidate)(struct dentry *, unsigned int); int (*d_weak_revalidate)(struct dentry *, unsigned int); int (*d_hash)(const struct dentry *, struct qstr *); //为目录项目生成hash表 int (*d_compare)(const struct dentry *, unsigned int, const char *, const struct qstr *); //比较两个文件 int (*d_delete)(const struct dentry *); int (*d_init)(struct dentry *); void (*d_release)(struct dentry *); void (*d_prune)(struct dentry *); void (*d_iput)(struct dentry *, struct inode *); char *(*d_dname)(struct dentry *, char *, int); struct vfsmount *(*d_automount)(struct path *); int (*d_manage)(const struct path *, bool); struct dentry *(*d_real)(struct dentry *, const struct inode *); void (*d_canonical_path)(const struct path *, struct path *); ANDROID_KABI_RESERVE(1); ANDROID_KABI_RESERVE(2); ANDROID_KABI_RESERVE(3); ANDROID_KABI_RESERVE(4); } ____cacheline_aligned; 文件对象 文件对象描述的是进程和文件直接的关系，对文件的操作都是由进程发起的，进程每打开一个文件，内核就创建一个文件对象，同一个文件可以被不同的进程打开，创建不同的文件对象。 struct file include/linux/fs.h struct file { union { struct llist_node fu_llist; struct rcu_head fu_rcuhead; } f_u; struct path f_path; struct inode *f_inode; /* cached value */ const struct file_operations *f_op; //文件的操作方法 /* * Protects f_ep, f_flags. * Must not be taken from IRQ context. */ spinlock_t f_lock; enum rw_hint f_write_hint; atomic_long_t f_count; unsigned int f_flags; fmode_t f_mode; struct mutex f_pos_lock; loff_t f_pos; struct fown_struct f_owner; const struct cred *f_cred; struct file_ra_state f_ra; u64 f_version; #ifdef CONFIG_SECURITY void *f_security; #endif /* needed for tty driver, and maybe others */ void *private_data; #ifdef CONFIG_EPOLL /* Used by fs/eventpoll.c to link all the hooks to this file */ struct hlist_head *f_ep; #endif /* #ifdef CONFIG_EPOLL */ struct address_space *f_mapping; errseq_t f_wb_err; errseq_t f_sb_err; /* for syncfs */ ANDROID_KABI_RESERVE(1); ANDROID_KABI_RESERVE(2); } __randomize_layout struct file_operations include/linux/fs.h struct file_operations { struct module *owner; loff_t (*llseek) (struct file *, loff_t, int); ssize_t (*read) (struct file *, char __user *, size_t, loff_t *); ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *); ssize_t (*read_iter) (struct kiocb *, struct iov_iter *); ssize_t (*write_iter) (struct kiocb *, struct iov_iter *); int (*iopoll)(struct kiocb *kiocb, bool spin); int (*iterate) (struct file *, struct dir_context *); //目录读取 int (*iterate_shared) (struct file *, struct dir_context *); __poll_t (*poll) (struct file *, struct poll_table_struct *); long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long); long (*compat_ioctl) (struct file *, unsigned int, unsigned long); int (*mmap) (struct file *, struct vm_area_struct *); unsigned long mmap_supported_flags; int (*open) (struct inode *, struct file *); int (*flush) (struct file *, fl_owner_t id); int (*release) (struct inode *, struct file *); int (*fsync) (struct file *, loff_t, loff_t, int datasync); int (*fasync) (int, struct file *, int); int (*lock) (struct file *, int, struct file_lock *); ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int); unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long); int (*check_flags)(int); int (*flock) (struct file *, int, struct file_lock *); ssize_t (*splice_write)(struct pipe_inode_info *, struct file *, loff_t *, size_t, unsigned int); ssize_t (*splice_read)(struct file *, loff_t *, struct pipe_inode_info *, size_t, unsigned int); int (*setlease)(struct file *, long, struct file_lock **, void **); long (*fallocate)(struct file *file, int mode, loff_t offset, loff_t len); void (*show_fdinfo)(struct seq_file *m, struct file *f); #ifndef CONFIG_MMU unsigned (*mmap_capabilities)(struct file *); #endif ssize_t (*copy_file_range)(struct file *, loff_t, struct file *, loff_t, size_t, unsigned int); loff_t (*remap_file_range)(struct file *file_in, loff_t pos_in, struct file *file_out, loff_t pos_out, loff_t len, unsigned int remap_flags); int (*fadvise)(struct file *, loff_t, loff_t, int); ANDROID_KABI_RESERVE(1); ANDROID_KABI_RESERVE(2); ANDROID_KABI_RESERVE(3); ANDROID_KABI_RESERVE(4); } __randomize_layout; 下面描述进程与文件操作联系 每个进程打开一个文件后，都有一个文件描述符fd。struct file *fd_array存储的就是这个进程打开的所有文件，称为文件描述符表，文件描述表的每一项都是一个指针，指向一个用于描述打开的struct file对象，struct file对象描述了文件的打开模式，当进程打开一个文件是，内核就会创建一个file对象，但是需要注意的是file对象不是专属某个进程，fd才是专属于某个进程，不同的文件描述符指针可以指向相同的file对象，表示共享打开的文件，struct file中有一个引用计数，描述了被多个进程引用的次数，只有引入计数为0时，内核才会销毁file对象。 其他数据结构 文件系统类型 Linux支持多种文件系统，内部用一个特殊的数据结构来描述每种文件系统的功能和行为。 include/linux/fs.h struct file_system_type { const char *name; //文件系统名称 int fs_flags; #define FS_REQUIRES_DEV 1 #define FS_BINARY_MOUNTDATA 2 #define FS_HAS_SUBTYPE 4 #define FS_USERNS_MOUNT 8 /* Can be mounted by userns root */ #define FS_DISALLOW_NOTIFY_PERM 16 /* Disable fanotify permission events */ #define FS_ALLOW_IDMAP 32 /* FS has been updated to handle vfs idmappings. */ #define FS_THP_SUPPORT 8192 /* Remove once all fs converted */ #define FS_RENAME_DOES_D_MOVE 32768 /* FS will handle d_move() during rename() internally. */ int (*init_fs_context)(struct fs_context *); const struct fs_parameter_spec *parameters; struct dentry *(*mount) (struct file_system_type *, int, const char *, void *);//挂载文件系统 void (*kill_sb) (struct super_block *); struct module *owner; struct file_system_type * next; struct hlist_head fs_supers; struct lock_class_key s_lock_key; struct lock_class_key s_umount_key; struct lock_class_key s_vfs_rename_key; struct lock_class_key s_writers_key[SB_FREEZE_LEVELS]; struct lock_class_key i_lock_key; struct lock_class_key i_mutex_key; struct lock_class_key invalidate_lock_key; struct lock_class_key i_mutex_dir_key; }; 文件系统挂载 Linux文件系统只有被挂载上，才能进行访问，使用一个vfsmount来描述一个挂载点。 include/linux/fs.h struct vfsmount { struct dentry *mnt_root; /* root of the mounted tree */ struct super_block *mnt_sb; /* pointer to superblock */ int mnt_flags; struct user_namespace *mnt_userns; ANDROID_KABI_RESERVE(1); ANDROID_KABI_RESERVE(2); ANDROID_KABI_RESERVE(3); ANDROID_KABI_RESERVE(4); } __randomize_layout;

磁盘空间布局 Extx将磁盘划分为等份的若干区域（最后一个区域可能会小一些），这些区域称为块组（block group）。磁盘以块组为单位进行管理。每个块组再划分为相同大小的block，这些block按功能分为原数据区和数据区。原数据区域也是占用block空间，但是是用于描述管理磁盘的信息，其中块0的原数据区域是相对比较复杂的，其包含了引导块、超级块、块组描述符、GDT、数据块位图、inode位图、inode表。出块组0外的其他块组就稍微简单些只有数据位图、inode位图、inode表。 Boot block:引导块，引导操作系统启动的区域，其并非文件系统的一部分，而是预留给操作系统使用的。 super block：超级块，文件系统的入口，记录了整个文件系统的描述信息，如格式化时指定的文件系统逻辑块大小、逻辑块的数量、inode的数量、根节点的ID和文件系统的特性相关信息。文件系统挂载时会从这里读取获取信息，可以通过dumpe2fs命令查看文件系统的超级块信息。 GDT：group descriptor table，块组描述表，紧跟在超级块之后，对块组信息的描述。块组描述符信息时以列表的形式组织，每个列表包括对应块组中数据位图的位置、inode位图的位置、inode表的位置信息。 Reserved GDT：预留块组描述表，为块组描述符预留的空间。 Block bitmap：数据块位图，标识当前块组中那些数据块被使用了，1个bit对应一个data block。 Inode bitmap：inode位图，与block bitmap类似，标识inode table中inode的使用情况。 Inode table：inode 表，inode是文件系统非常重要的概念，每个文件或目录对应一个inode来描述，inode 表中存储了inode的数据结构实体，即文件系统中有多少个文件+目录就有多少个inode的实体。 Data block：数据块，实际文件的内容，块组中出勤原数据剩余的就是数据块了，这些数据块也分为等分的大小，一般数据块的大小为1KB或2KB或4KB，由系统进行设置。 可以使用dumpe2fs来查看磁盘块信息，可以看到Group0有super block，gdt，reserved GDT。其他组没有superblock，但是可能会有backup superrblock，主要用于备份使用。大部分group只有block bitmap、inode bitmap、inode table。 文件数据管理 间接块的文件数据管理（ext2） 文件占用了磁盘中的那些空间是通过inode来进行标识，一个文件对应一个inode，在struct ext2_inode结构体有一个成员i_block[EXT2_N_BLOCKS]，该成员的作用就是标识了当前文件占用的是磁盘中那些数据块。 struct ext2_inode { __le16 i_mode; /* File mode */ __le16 i_uid; /* Low 16 bits of Owner Uid */ __le32 i_size; /* Size in bytes */ __le32 i_atime; /* Access time */ __le32 i_ctime; /* Creation time */ __le32 i_mtime; /* Modification time */ __le32 i_dtime; /* Deletion Time */ ...... __le32 i_block[EXT2_N_BLOCKS];/* Pointers to blocks */ EXT2_N_BLOCKS=15 __le32 i_generation; /* File version (for NFS) */ __le32 i_file_acl; /* File ACL */ __le32 i_dir_acl; /* Directory ACL */ ...... } #define EXT2_NDIR_BLOCKS 12 #define EXT2_IND_BLOCK EXT2_NDIR_BLOCKS #define EXT2_DIND_BLOCK (EXT2_IND_BLOCK + 1) #define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK + 1) #define EXT2_N_BLOCKS (EXT2_TIND_BLOCK + 1) 直接索引：数组的前12个索引项一一对应磁盘的某一个数据块，假设磁盘的数据块大小是4K，那么前12个索引项可支持的文件大小为12*4KB=48KB，这种索引的方式速度是最快的，但是也不能无限制的增加数组的大小来一一对应数据块，这样耗费的内存空间将是很大的。为了解决这个问题，当文件大小超过一定大小将使用间接索引的方式。 间接索引：间接索引有2级、3级间接索引，以2级间接索引为例i_block[12]指向磁盘不是实际的数据块，而是指向下一级的地址，下一级地址中的数据块内容指向的数据块才是实际的内容。相当于使用磁盘的空间来存储数据块的索引，类似于虚拟内存的多级页表。 小结：在ext2的inode节点中有i_blocks[15]元素的数组，其中前12个元素存储的是文件数据的磁盘地址，第13个元素存储的地址所指向的磁盘数据存储的不是文件内容数据而是指向下一级的地址，也就是说该数组的元素和实际存储文件数据的磁盘块多出一个磁盘块用于存储磁盘的地址，这个磁盘块称为间接块。由于文件系统中块的大小是确定的，而地址长度和数组元素也是确定的，因此可以确定文件的最大大小。同时，每个地址指向的就是一个块，这种方式的特点就是磁盘的块大小是等分的，缺点就是如果用户写入远大于文件系统块的数据，还是要切分为指定大小的块，同时文件越大需要的元数据越多，寻址的级数也会变多，效率就会变差。 基于Extent的文件数据管理（ext4） Ext2的缺点所有的数据块大小是等分的，数据块的索引也是固定大小的，每个索引只能索引一个数据块，那么对于大文件来说，比如一个电影大小几个G，那么就需要很多的索引和很多的数据块组组合存储，这样的效率是及低的，在ext4中则进行了改进，主要的核心原理就是一个索引对应的块大小是不定的，比如一个3GB的电影文件，用一个索引就解决，只要在索引中给定磁盘块地址和长度就可以检索到，如下图各索引只要给定磁盘地址加上长度就可以索引到具体的文件所划分的磁盘块。 当然实际在实现时没这么简单，上面只是一个简化版本模型便于理解，但是核心原理就是上面的方式。在ext4文件系统上引入了extent机制，extent的数据存储方式，使用B+树的方式，而inode中的i_blocks[15]就变成了B+树的树根。使用extents，用一个struct ext4_extent结构就可以映射多个数据块，减少原数据块的使用。 Extent树的每个节点可以分为内部节点和叶子节点，每个节点的构成为ext4_extent_header+内容，内容根据内部节点和叶子节点有所不同，①如果节点是内部节点（ext4_extent_header.eh_depth>0），ext4_extent_header后面紧跟的是extent_header.eh_entries个struct ext4_extent_idx，也称为索引节点。②如果节点是叶子节点（ext4_extent_header.eh_depth=0），ext4_extent_header后面紧跟的是extent_header.eh_entries个Extent项struct ext4_extent数据结构。 原inode.iblocks[15]则存储的是Extent树的根节点，一共是60字节前12字节用于存储struct ext4_extent_header，后48字节用于存储4个struct ext4_extent_idx（每个12字节）。 struct ext4_inode： struct ext4_inode { __le16 i_mode; /* File mode */ __le16 i_uid; /* Low 16 bits of Owner Uid */ __le32 i_size_lo; /* Size in bytes */ __le32 i_atime; /* Access time */ __le32 i_ctime; /* Inode Change time */ __le32 i_mtime; /* Modification time */ __le32 i_dtime; /* Deletion Time */ __le16 i_gid; /* Low 16 bits of Group Id */ __le16 i_links_count; /* Links count */ __le32 i_blocks_lo; /* Blocks count */ __le32 i_flags; /* File flags */ ...... __le32 i_block[EXT4_N_BLOCKS];/* Pointers to blocks */ EXT4_N_BLOCKS=15 ...... } #define EXT4_NDIR_BLOCKS 12 #define EXT4_IND_BLOCK EXT4_NDIR_BLOCKS #define EXT4_DIND_BLOCK (EXT4_IND_BLOCK + 1) #define EXT4_TIND_BLOCK (EXT4_DIND_BLOCK + 1) #define EXT4_N_BLOCKS (EXT4_TIND_BLOCK + 1) struct ext4_inode： ext4_extents.h struct ext4_extent_header { __le16 eh_magic; /* 支持不同的格式 */ __le16 eh_entries; /* 跟在头部后面的项目个数 */ __le16 eh_max; /* 项目中的存储容量 */ __le16 eh_depth; /* 树的深度 */ __le32 eh_generation; /* generation of the tree */ }; struct ext4_extent_idx，extent树的内部节点，也称为索引节点。 ext4_extents.h struct ext4_extent_idx { __le32 ei_block; /* index covers logical blocks from 'block' */ __le32 ei_leaf_lo; /*指向下一级的物理数据块，可以是索引节点或叶子节点 */ __le16 ei_leaf_hi; /* 物理数据块的高16位 */ __u16 ei_unused; };

mount的机制是如何实现的？ inode是如何分配的。磁盘inode和内存inode有什么区别？ dentry缓存是怎么回事？如何管理？ free命令中Cache和buff有什么区别？Page cache了？如何管理文件数据缓存？ 扇区与簇 物理块和扇区，逻辑块和簇是相同概念。扇区（物理块）是磁盘最小的存储单元，磁头从磁盘读取数据的最小单元，一般是512B，即磁头每次从磁盘读取数据，都是一个扇区一个扇区读写。但对于操作系统来说无法对数目众多的扇区进行寻址，所以操作系统对磁盘的操作是以多个扇区组成形成一个簇为单位。 物理块/扇区是对磁盘操作而言的；逻辑块/簇是对软件操作系统（或文件系统）而言的，在linux中称为块，在windows中称为簇，操作系统从磁盘中拿一块数据，即完成一次磁盘IO。 块的大小在磁盘格式化时被指定，一般有1K/2K/4K，如果块的大小设置为4K，那么磁盘要读取8个扇区之后才将数据给操作系统。如果一个文件的大小是1K，而块的大小是4K，那么文件也会占用一个块的大小，剩余3K将会被空闲处理。 什么是文件系统 文件系统是一个控制数据存取的软件系统，实现文件的增、删、查、改等操作。文件系统是可以构建在磁盘（flash、SD卡、SSD等），也可以构建在网络或内存上，甚至可以构建在一个文件上。文件系统更重要的功能是抽象了一个更加容易访问的存储空间接口，这些接口包括对于程序开发的API和用户的操作等。 底层是具体的硬件设备，硬件设备是具备存储功能的介质包括磁盘、内存、网络、甚至文件。中间层是操作系统将存储介质抽象为一个连续的线性空间，线性空间可分为大小相同的块（1KB、2KB、4KB等），抽象为连续的线性空间主要是便于顶层的文件系统管理。顶层就是文件系统，文件系统对线性空间进行管理和抽象，便于用户进行操作，文件系统一般呈现为目录树，这里的层级结构就是平常的目录、子目录和文件等元素的集合。 目录：是一种容器，可以容纳子目录和普通文件，通过目录来对文件进行分类，便于用户访问，在linux中目录也是文件。 文件：是文件系统中存储数据的实体，文件有文件名，用于标识一个文件，文件的种类很多如txt、mp3、doc等，不同的文件类型需要对应于的应用来打开。具体文件可以分为普通文件、字符设备文件、块设备文件、套接字文件。 链接：分为软链接和硬链接；软链接是文件的另一种形态，其内容指向另外一个文件的路径，软链接也称为符号链接。硬链接则不同，是一个已存在文件的附加名称，在目录中增加了一项，但是其内容与源文件内容完全相同。 在linux系统中一切都是文件，可以使用ls -l通过显示结果查看文件类型。 常见的文件系统 本地文件系统：实现对磁盘的管理，常用的用EXT4、FAT、XFS、ZFS等 伪文件系统：不是持久化的数据，对应内存的文件系统，便于用于以文件的形式与内核数据交互，如proc、sysfs、configfs、debugfs等。 网络文件系统：基于tcp/ip协议的文件系统，运行具有网络的计算机访问另外一具有网络的计算机像访问本地文件系统一样。 文件系统使用 文件内容的访问 对于普通用户来说，通过命令或鼠标就能对文件进行操作，对于程序员来说可以通过API接口来进行完成，下面是举例常用接口。 API 描述 open 打开文件 read 从文件读数据 write 从文件写数据 close 关闭文件 lseek 移动文件指针位置 lseek 删除文件 格式化文件系统与挂载 格式化文件系统是在一个存储设备上构建一个文件系统，而挂载则是将文件系统激活在文件系统的目录树中可以进行访问。 （1）文件系统的构建命令 mkfs.xxx /dev/xxx 如mkfs.ext4 /dev/sdb， 将块设备格式化为ext4文件系统 （2）文件系统挂载 文件系统只有挂载到系统中，才可以进行访问。 mount -t [fs type] -o [opt] device dir 如mount -t ext4 /dev/sdb /mnt/ext4 除了手动挂载文件系统，linux还支持自动挂载，通过配置fstab配置文件即可进行挂载对应的设备。 proc /proc proc defaults 0 0 sysfs /sys sysfs defaults 0 0 devtmpfs /dev devtmpfs defaults 0 0 tmpfs /tmp tmpfs defaults 0 0 tmpfs /var tmpfs defaults 0 0 还可以基于文件来构建文件系统，下面是示例： # 1生成一个全0的二进制文件 dd if=/dev/zero of=ext4.bin bs=1M count=100 #2 格式化为EXT4文件系统 mkfs.ext4 ext4.bin #3 使用loop设备，访问块设备,需要在内核把CONFIG_BLK_DEV_LOOP打开。 losetup /dev/loop0 ./ext4.bin #4 挂载文件系统 mkdir ext4 mount /dev/loop10 ext4 文件系统的目录下可以挂载其他文件系统。

何时均衡 在linux内核中，有一些场景会触发任务均衡的分布在系统的各个cpu上，可以分为以下几个场景： 任务放置：task placement，fork创建的任务、sched_exec的任务或者阻塞被唤醒的任务，这些任务加入就绪队列时，可以确定放置任务到那个cpu上。 主动均衡：active upmigration，一个低算力的cpu无法运行某个重载任务时（misfit task），可以主动将misfit task向上迁移到算力更高的cpu上。 周期均衡：tick load balance，周期性的触发均衡。 new idle均衡：new idle load balance，调度器在选择下一个任务时，发现cfs 就绪队列中没有可运行任务，只能指向idle任务，进入idle状态会触发负载均衡。 nohz idle均衡：某个cpu任务太重，而其他cpu都进入idle，这时候任务重cpu会唤醒idle的cpu进行均衡负载。 laod balance （1）找出最繁忙的调度组 （2）在最繁忙调度组范围CPU找出最繁忙的CPU （3）从最繁忙的CPU就绪队列中出队任务 （4）将出队的任务挂到当前的cpu上。 负载均衡总结 图来自窝蜗科技 PELT的缺陷： （1）算法迟钝，负载的变化需要一定的时间，在一些嵌入式场景如手机，在浏览网页等情况下，需要迅速识别重活来提高CPU频率或者迁移任务，保证手机流程型。 （2）对于睡眠或阻塞的进程，PELT还会继续计算其衰减负载，这些继续贡献的负载对于下一次唤醒没有实际用处，会推迟降低cpu频率的速度，导致功耗升高。 参考文献 1.蜗窝科技：http://www.wowotech.net/ 2.奔跑吧linux内核卷1基础架构

概述 从上一章节大概应该能够理解负载和利用率的区别了，当一个进程正在运行或者即使没有在cpu上运行，而在就绪队列中等待运行，那么他依旧消耗cpu的负载。这是合理的，因为cpu的就绪队列有10个任务等待着运行与5个任务等待运行，明显是10个任务的负载重。而利用率只是关注正在运行的任务而不包含在就绪队列的任务，在某个时间段内可能某个任务的cpu利用率很高，但是占用完之后一直睡眠，那么其队系统的负载贡献还是较小。 从CPU的层次划分，从大到小分为： NUMA: 多个SOC组成，通过UPI可以共享多块物理内存，常用于服务器。 SOC: system-on-a-chip，集成了多个系统组件或功能的芯片，对应DIE。 MC:multi-core，多核处理器，一个SOC集成多个核心，每个核心用于自己的缓存或寄存器资源，可以并行处理多个程序。 SMT:Simultaneous Multi-Threading，超线程，单个核心处理器同时执行多个线程，在单个核心处理器引入多个逻辑执行单元和资源共享极致，实现更好的指令集并发性。 现在的嵌入式处理器通常包含SOC+MC技术，也就是在一个SOC上集成了多核处理器，目前遇到的SMT和NUMA的还比较少，因此本章节先讨论一个SOC上集成MC的情况。 因为多核的出现，我们需要引入负载均衡，我们需要解决将SOC运行的任务均衡的分配到各个核上处理，但是并不能简单的平均分配任务到各个CPU上，从上图的架构来看，一个SOC上存在大小核的情况2个小核+2个大核，那自然大核的算力要高于小核的算力，同时我们还需要考虑CPU的频率，同样的架构核心高频的算力自然要高于低频的算力。除了配合各CPU的算力来均衡负载外，还需要考虑任务迁移的开销，上图CPU0上的任务迁移到CPU1上的开销会少于迁移到CPU2上，因为CPU0和CPU1共享L2 cache，如果迁移到L2上的话，cache就会失效，性能或许会减弱。基于上述这些因素，linux构建了相关的数据结构来处理这些问题，称为调度域和调度组。 系统为了便于负载均衡，构建调度域（sched domain，简记sd）和调度组(sched group，简记sg)。按照架构层级可以依次划分为不同的SOC、相同SOC不同的核心、相同的核心不同的超线程。我们把相同层级称为调度域，越往下层的调度域共用的缓存越多，因此在任务做迁移时，优先选择从底层的调度域中进行。先不考虑SMT，上图的调度域可以分为两级从下往上MC domain（multi core domain），DIE domain。 DIE domain：处于顶层，覆盖系统所有的CPU（CPU0~CPU3）。 MC domain：处于底层，也称为base domain，分为小核MC domain（cpu0~cpu1）和大核MC domain（CPU2~CPU3），小核MC domain是一个cluster，大核MC domain是一个cluster。 负载均衡调度的最小单元是调度组，每个调度域进行分组。对于MC域，基本可以按照一个cpu是一组，所以小核MC domain可以分为两组（一个CPU对应一组），大核MC domain也是分为两组。对于DIE域，每个分组要覆盖到其child domain，DIE 域有两个子domain，分别是小核MC domain，大核MC domain，因此DIE domain分为两个组对于小核group和大核group。 数据结构 Linux内核使用struct sched_domain_topology_level，简称SDTL来描述CPU的层次关系。 struct sched_domain_topology_level mask：函数指针，指定cpumask位图 sd_flags：函数指针，指定标志位 flags:进一步描述和设置调度域 numa_level:NUMA层级，确定该层级为NUMA的那一层 data:调度域数据结构，存储关于调度域的统计信息 name:调度域名称 以下是内核默认定义了一个层次结构，DIE是默认打开，MC和SMT是可选的。 static struct sched_domain_topology_level default_topology[] = { #ifdef CONFIG_SCHED_SMT { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) }, #endif #ifdef CONFIG_SCHED_MC { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) }, #endif { cpu_cpu_mask, SD_INIT_NAME(DIE) }, { NULL, }, }; static struct sched_domain_topology_level *sched_domain_topology = default_topology; struct sd_data,该结构体中成员都使用percpu来修饰，用于指示该指针是一个per-CPU变量，告诉编译器将变量的内存分配为每个CPU分别保留的独立内存块，如struct sched *__percpu *sd是指向struct sched_domain类型的per-CPU变量，也就是其指向的是一个数组（有cpu个数元素），数组的每个元素是指向一个struct sched_domain类型的指针，每个指针与一个特定的CPU相关联，分配数组是使用alloc_percpu来实现，该函数会分配一个具有相同大小的块，并为每个cpu都分配一个指针。 sd = alloc_percpu(struct sched_domain *)，则sd分配了per-CPU变量的内存空间，这意味着每个CPU都有自己独立的struct sched_domain指针变量，当给其每个CPU的指针变量赋值后，后续可以通过sd[cpu]来cpu上的struct sched_domain变量。 sd[]: 描述CPU的调度域，实际是一个指针数组，每个数组元素指针指向cpu所属的调度域，下同。 sds[]:存储调度域共享数据，用于描述多个CPU共享的调度域。 sg[]:每个cpu都有一个指向调度组的指针，用于描述CPU所属的调度组 sgc[]:调度组的容量信息，用于描述调度组的资源容量。 在系统中，为了避免多核之间的互斥访问影响性能，调度域sched_domain数据结构采用Per-CPU的变量来构建，每个CPU都维护一个调度域数据结构。 struct sched_domain_shared，为了降低锁竞争，sd是per-cpu的，但是有一些信息需要在per-cpu上的sd之间共享，不能在每个sd上构建，这些共享的信息就存储在sds上。 nr_busy_cpus:该sd中忙的cpu个数。 has_idle_cores:该sd中是否有idle cpu。 struct sched_group_capacity capacity: min/max_capacity: next_update: imbalance: cpumask[] struct sched_domain parent和child:调度域会形成层次结构，parent和child建立了不同层级的父子关系。对于base domain而言，其child=NULL，对于顶层domain而言，parent=NULL。 groups:一个调度域中有若干调度组，这些调到组形成一个环形的链表，groups成员就是链表头。 flags:调度域的标志，SD_BALANCE_NEWIDLE是否支持newidle balance，SD_SHARE_PKG_RESOURCES是否共享cache等资源。 span[]:调度域中cpu 核形成的cpu mask，即调度域覆盖的cpu核范围，当前调度域可使用那几个cpu核。 struct sched_group next: 调度域中的所有group都会形成一个链表，next指向下一个group。 ref:该调度组被应用的次数。 group_weight:调度组中有多少个cpu。 sgc:调度组的算力信息。 cpumask:调度组包括那些cpu。 include/linux/cpumask.h struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); //unsigned long bits[1]； } //NR_CPUS为核心数，以8核，64位系统计算为例。 #define DECLARE_BITMAP(name,bits) \\ unsigned long name[BITS_TO_LONGS(bits)] #define BITS_TO_LONGS(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(long)) #define __KERNEL_DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) #define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE) #define BITS_PER_BYTE 8 (((n) + (d) - 1) / (d)) = (((8) + (64) - 1) / (64)) = 1 struct s_data { struct sched_domain * __percpu *sd; struct root_domain *rd; }; CPU拓扑结构 Linux内核中，通过读取dts文件，建立Topology。 cpus { #address-cells = <0x02>; #size-cells = <0x00>; cpu@0 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x00>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; dynamic-power-coefficient = <0x11e>; cpu-supply = <0x06>; phandle = <0x09>; }; cpu@100 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x100>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; phandle = <0x0a>; }; cpu@200 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x200>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; phandle = <0x0b>; }; cpu@300 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x300>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x39a>; clocks = <0x04 0x01>; operating-points-v2 = <0x05>; #cooling-cells = <0x02>; phandle = <0x0c>; }; cpu@400 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x400>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; dynamic-power-coefficient = <0x162>; cpu-supply = <0x08>; phandle = <0x0d>; }; cpu@500 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x500>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; phandle = <0x0e>; }; cpu@600 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x600>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; phandle = <0x0f>; }; cpu@700 { device_type = "cpu"; compatible = "arm,cortex-a55"; reg = <0x00 0x700>; enable-method = "psci"; cpu-idle-states = <0x02 0x03>; capacity-dmips-mhz = <0x400>; clocks = <0x04 0x03>; operating-points-v2 = <0x07>; #cooling-cells = <0x02>; phandle = <0x10>; }; cpu-map { cluster0 { core0 { cpu = <0x09>; }; core1 { cpu = <0x0a>; }; core2 { cpu = <0x0b>; }; core3 { cpu = <0x0c>; }; }; cluster1 { core0 { cpu = <0x0d>; }; core1 { cpu = <0x0e>; }; core2 { cpu = <0x0f>; }; core3 { cpu = <0x10>; }; }; }; } 上面的dts描述，soc中有8个核心，分为两个cluster，cpu0~cpu3，cpu4~cpu7，因此调度域可以这样划分。 DIE: cpu 0~7 MC: cpu 0~3一组，cpu4~7一组。 可以通过 /sys/devices/system/cpu/cpuX/topology节点来获取topology相关信息。 root@TinaLinux:/sys/devices/system/cpu/cpu0/topology# cat * 01 //core_cpus 0 //core_cpus_list 0 //core_id 0f //core_siblings 0-3 //core_siblings_list 01 //die_cpus 0 //die_cpus_list -1 //die_id 0f //package_cpus 0-3 //package_cpus_list 0 //physical_package_id 01 //thread_siblings 0 //thread_siblings_list root@TinaLinux:/sys/devices/system/cpu/cpu6/topology# cat * 40 //core_cpus 6 //core_cpus_list 2 //core_id f0 //core_siblings 4-7 //core_siblings_list 40 //die_cpus 6 //die_cpus_list -1 //die_id f0 //package_cpus 4-7 //package_cpus_list 1 //physical_package_id 40 //thread_siblings 7 //thread_siblings_list 在后续章节中，我们都以当前的拓扑结构举例来说明。 创建sd和sg CPU MASK #define cpu_possible_mask ((const struct cpumask *)&__cpu_possible_mask) //系统中有多少个CPU核可以运行 #define cpu_online_mask ((const struct cpumask *)&__cpu_online_mask) //系统中有多少个CPU核正在运行 #define cpu_present_mask ((const struct cpumask *)&__cpu_present_mask) //系统中有多少个正处于运行状态的CPU核。 #define cpu_active_mask ((const struct cpumask *)&__cpu_active_mask) //系统中有多少个活跃的CPU核 #define cpu_dying_mask ((const struct cpumask *)&__cpu_dying_mask) //系统中有多少个将死的cpu核 如果没有CONFIG_HOTPULG_CPU，那么present=possible，active = online。 int sched_init_domains(const struct cpumask *cpu_map) { int err; zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL); zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL); zalloc_cpumask_var(&fallback_doms, GFP_KERNEL); arch_update_cpu_topology(); asym_cpu_capacity_scan(); ndoms_cur = 1; doms_cur = alloc_sched_domains(ndoms_cur); //创建cpumask_var_t类型，存储用于当前调度域的可用的cpu。 if (!doms_cur) doms_cur = &fallback_doms; cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN)); //cpu_map为cpu_active_mask，在active中排除掉不能用于调度域的cpu，isolcpus对某些//cpu进行的隔离，不参与调度域中，doms_cur最终保存的排除之后可用调度域的cpu。 err = build_sched_domains(doms_cur[0], NULL); //调度域建立。 return err; } 为DIE和MC分配每CPU的sd/sdc/sg/sgc空间 static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { enum s_alloc alloc_state = sa_none; struct sched_domain *sd; struct s_data d; ...... //分配DIE,MC SDTL拓扑相关数据结构，初始化一个struct s_data； alloc_state = __visit_domain_allocation_hell(&d, cpu_map); ...... } build_shed_domains函数中首先调用__visit_domain_allocation_hell为每个cpu分配各个调度域层级（DIE/MC）分配sd/sdc/sg/sgc。 struct sched_domain_topology_level { sched_domain_mask_f mask; sched_domain_flags_f sd_flags; int flags; int numa_level; struct sd_data data; #ifdef CONFIG_SCHED_DEBUG char *name; #endif }; //定义了一个static struct sched_domain_topology_level default_topology[]全局变量。 static struct sched_domain_topology_level default_topology[] = { #ifdef CONFIG_SCHED_SMT { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) }, #endif #ifdef CONFIG_SCHED_MC { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) }, #endif { cpu_cpu_mask, SD_INIT_NAME(DIE) }, { NULL, }, }; 内核定义了一个全局变量static struct sched_domain_topology_level default_topology[]，该变量根据宏配置调度域的层次，DIE调度域是默认开启的，往下是MC调度域，再到SMT调度域，由于ARM架构SMT调度目前见得还比较少，所以再不考虑，build_shed_domains得核心就是各层级得SDTL。 static enum s_alloc __visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map) { memset(d, 0, sizeof(*d)); //为全局struct sched_domain_topology_level default_topology[]的DIE和MC分配对应的 //per-CPU sd/sds/sg/sgc if (__sdt_alloc(cpu_map)) return sa_sd_storage; //为每个CPU分配了一个调度域，作用是用户存储最底层（MC）的sd，也就是每个CPU 的 //d->sd指向MC的sd，这只是临时分配，用于在建立sg的时候辅助使用，后续会销毁。 d->sd = alloc_percpu(struct sched_domain *); if (!d->sd) return sa_sd_storage; //分配一个rootdomain并进行初始化，主要用于rt的？ d->rd = alloc_rootdomain(); if (!d->rd) return sa_sd; return sa_rootdomain; } __visist_domain_allocation_hell调用__sdt_alloc，分配SDTL中的struct sd_data data并进行初始化。 struct sd_data { struct sched_domain *__percpu *sd; struct sched_domain_shared *__percpu *sds; struct sched_group *__percpu *sg; struct sched_group_capacity *__percpu *sgc; }; sd_data的成员都是__percpu类型，需要先调用alloc_percpu分配相同大小的cpu个数区域，这些区域存储的是指针，指向每个cpu对应的sd/sds/sg/sgc，以struct sched_domain *__percpu *sd为例，sdd->sd = alloc_percpu(struct sched_domain *)分配一块指针数组，数组元素的个数为cpu核个数，sd指向这个指针数组，数组中的指针用于后续每个CPU指向分配的sd空间。 static int __sdt_alloc(const struct cpumask *cpu_map) { struct sched_domain_topology_level *tl; int j; //遍历SDTL，这里有MC和DIE。 for_each_sd_topology(tl) { struct sd_data *sdd = &tl->data; //分配当前层级调度域sd Per-CPU变量（指针数组，数组元素为cpu个数指针，下同） sdd->sd = alloc_percpu(struct sched_domain *); if (!sdd->sd) return -ENOMEM; //分配当前层级sdc Per-CPU变量 sdd->sds = alloc_percpu(struct sched_domain_shared *); if (!sdd->sds) return -ENOMEM; //分配当前层级sg Per-CPU变量 sdd->sg = alloc_percpu(struct sched_group *); if (!sdd->sg) return -ENOMEM; //分配当前层级sgc Per-CPU变量 sdd->sgc = alloc_percpu(struct sched_group_capacity *); if (!sdd->sgc) return -ENOMEM; //上面已经完成当前层级Per-CPU变量，下面就遍历每个cpu分配sd/sds/sg/sgc，Per-CPU //遍历将一一对应指向。 for_each_cpu(j, cpu_map) { struct sched_domain *sd; struct sched_domain_shared *sds; struct sched_group *sg; struct sched_group_capacity *sgc; sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sd) return -ENOMEM; *per_cpu_ptr(sdd->sd, j) = sd; //如对应cpu0来说，sdd-sd[0] = sd,sdd-sd[0]是一个指针，指向当前分配的sd空间。 sds = kzalloc_node(sizeof(struct sched_domain_shared), GFP_KERNEL, cpu_to_node(j)); if (!sds) return -ENOMEM; *per_cpu_ptr(sdd->sds, j) = sds; sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sg) return -ENOMEM; sg->next = sg; *per_cpu_ptr(sdd->sg, j) = sg; sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sgc) return -ENOMEM; *per_cpu_ptr(sdd->sgc, j) = sgc; } } return 0; } 执行完__sdt_alloc，层次结构就如下所示，如对应DIE层次，sdd-sd[0~7]分别指向各自cpu分配的sd区域。 初始化调度域sd static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { enum s_alloc alloc_state = sa_none; struct sched_domain *sd; struct s_data d; struct rq *rq = NULL; int i, ret = -ENOMEM; bool has_asym = false; ........ //遍历每个CPU，从下往上初始化SDTL的sd，先初始化MC再初始化DIE。 // DIE的sd 其child指向MC的sd，MC的sd 其parent指向DIE的sd。 for_each_cpu(i, cpu_map) { struct sched_domain_topology_level *tl; sd = NULL; for_each_sd_topology(tl) { if (WARN_ON(!topology_span_sane(tl, cpu_map, i))) goto error; //初始化调度域 sd = build_sched_domain(tl, cpu_map, attr, sd, i); has_asym |= sd->flags & SD_ASYM_CPUCAPACITY; if (tl == sched_domain_topology) *per_cpu_ptr(d.sd, i) = sd; //将最低层级的sd保存到s_data.sd的per_cpu变量中，最底层为MC level的sd //为下一步建立sg做准备。 if (tl->flags & SDTL_OVERLAP) sd->flags |= SD_OVERLAP; if (cpumask_equal(cpu_map, sched_domain_span(sd))) break; //sched_domain_span(sd)用于获取给定调度域sd的范围cpu，也就是说当前调度域 //中覆盖的cpu是那几个。 //调度域都有一个范围，表示该调度域可以管理的CPU范围，这个范围通常有一 //个cpumask表示，其中每个位都对应一个cpu，调度域的范围定义了该调度域影//响的cpu集合。 } } ........ } for_each_cpu遍历每一个cpu，接着for_each_sd_topology(tl)对每个cpu从最底层依次往上构建调度域，先构建MC再DIE。build_sched_domain中会调用sd_init对调度域进行初始化，主要是struct sched_domain结构体成员赋值，同时建立起MC与DIE层级sd的父子联系，如下对于DIE层级，每cpu的sd.child指向MC层级的sd，而MC层级sd.parent指向DIE层级的sd。在初始化调度域是会设置其span，span为调度域作用的cpu范围，实际是根据span的作用范围来对当前调度域层级进行分组。如MC层级，按照4.2.1.2的拓扑结构，有两个MC调度域名，CPU0~CPU3是一组，所以CPU0~CPU3的sd->span是相同的，CPU4~CPU7是一组，所以CPU4~CPU7的sd->span相同的。sd->span非常重要，在后续章节中也会使用该信息来建立sg之间的联系。 初始化调度组sg static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { enum s_alloc alloc_state = sa_none; struct sched_domain *sd; struct s_data d; struct rq *rq = NULL; int i, ret = -ENOMEM; bool has_asym = false; ........ /* Build the groups for the domains */ for_each_cpu(i, cpu_map) { //d.sd是最底层得调度域，这里是MC，即每cpu的sd for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) { sd->span_weight = cpumask_weight(sched_domain_span(sd)); if (sd->flags & SD_OVERLAP) { if (build_overlap_sched_groups(sd, i)) goto error; } else { if (build_sched_groups(sd, i)) goto error; } } } ........ } for_each_cpu遍历每个cpu，for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent)遍历当前cpu的调度域，从MC调度域往上开始，调用build_sched_groups构建当前调度域的调度组。 static int build_sched_groups(struct sched_domain *sd, int cpu) { struct sched_group *first = NULL, *last = NULL; struct sd_data *sdd = sd->private; const struct cpumask *span = sched_domain_span(sd); //获取当前调度域的cpu作用范围，对于DIE层级，span是cpu0~cpu7而对于MC层级 //span是core_siblings，即cpu0~cpu3或cpu4~cpu7。 struct cpumask *covered; int i; lockdep_assert_held(&sched_domains_mutex); covered = sched_domains_tmpmask; cpumask_clear(covered); //从当前cpu开始遍历整个sd span。 for_each_cpu_wrap(i, span, cpu) { struct sched_group *sg; if (cpumask_test_cpu(i, covered)) //已经在coverd msk中的cpu，继续执行，与下面的cpumask_or配合，避免重复指向。 continue; //获取cpu i的调度组sg sg = get_group(i, sdd); cpumask_or(covered, covered, sched_group_span(sg)); //coverd = coverd | sched_group_span(sg) if (!first) first = sg;//每个cpu进来的第一个sg if (last) last->next = sg;//每个sg的下一个sg last = sg; } last->next = first; //最后一个sg再指向第一个sg，就形成环形链表了。 sd->groups = first; //sd->groups指向第一个sg，对于MC是自己的sg return 0; } 在MC调度域层级，根据调度域sd->span定义的cpu范围内的sg形成环形链表，下面就是两个环形链表，对应的就是MC调度域层级的两个调度域实体。 在DIE区域，sg取的是子调度域所在的第一个cpu，即cpu0所在的sg和cpu4所在的sg。 static struct sched_group *get_group(int cpu, struct sd_data *sdd) { struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu); struct sched_domain *child = sd->child; struct sched_group *sg; bool already_visited; if (child) cpu = cpumask_first(sched_domain_span(child)); //如果调度域存在子调度域，则cpu获取子调度域的第一个cpu，只有DIE层级才有子调度//域，所以这里是cpu0或cpu4 sg = *per_cpu_ptr(sdd->sg, cpu); //获取当前层级cpu上的sg sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);//获取当前层级cpu上的sgc，将sg->sgc指向sgc /* Increase refcounts for claim_allocations: */ already_visited = atomic_inc_return(&sg->ref) > 1; /* sgc visits should follow a similar trend as sg */ WARN_ON(already_visited != (atomic_inc_return(&sg->sgc->ref) > 1)); /* If we have already visited that group, it\'s already initialized. */ if (already_visited) return sg; //如果是DIE层级 if (child) { cpumask_copy(sched_group_span(sg), sched_domain_span(child)); //将子调度域的cpu范围赋值到调度组sg的cpu范围，子sd->span = 父sg->cpumask cpumask_copy(group_balance_mask(sg), sched_group_span(sg)); //将调度组sg的cpu范围赋值到sg的平衡掩码balance mask } else { cpumask_set_cpu(cpu, sched_group_span(sg)); //将cpu添加到调度组sg的cpu范围中 cpumask_set_cpu(cpu, group_balance_mask(sg)); //将cpu添加到调度组sg平衡掩码中 } sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sched_group_span(sg)); //计算调度组能力。 sg->sgc->min_capacity = SCHED_CAPACITY_SCALE; sg->sgc->max_capacity = SCHED_CAPACITY_SCALE; return sg; } MC层级基本是一个cpu对应一个调度组sg，而对于DIE层级一个cluster对应一个调度组，调度组表示一般选择每个cluster的第一个cpu，该sg代表的不是一个cpu，而是整个cluster上的cpu，所以cpu上的sg->cpumask为子调度域的sd->span。 构建调度组能力sgc static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { ...... /* Calculate CPU capacity for physical packages and nodes */ //遍历每个CPU，从大到小开始遍历，然后依次遍历MC到DIE，初始化sg的cpu_capacity for (i = nr_cpumask_bits-1; i >= 0; i--) { if (!cpumask_test_cpu(i, cpu_map)) continue; //还是从底层MC开始往上遍历，初始化sgc for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) { claim_allocations(i, sd); init_sched_groups_capacity(i, sd); } } ...... } 遍历每个cpu，然后从MC层级往上到DIE层级，初始化每cpu各层级的sgc。 static void init_sched_groups_capacity(int cpu, struct sched_domain *sd) { struct sched_group *sg = sd->groups; WARN_ON(!sg); //循环，对sg环形链表中所有的sg->group_weight进行初始化。 do { int cpu, max_cpu = -1; sg->group_weight = cpumask_weight(sched_group_span(sg)); if (!(sd->flags & SD_ASYM_PACKING)) goto next; for_each_cpu(cpu, sched_group_span(sg)) { if (max_cpu < 0) max_cpu = cpu; else if (sched_asym_prefer(cpu, max_cpu)) max_cpu = cpu; } sg->asym_prefer_cpu = max_cpu; next: sg = sg->next; } while (sg != sd->groups); if (cpu != group_balance_cpu(sg)) return; update_group_capacity(sd, cpu); //更新group 的capacity。 } 将每cpu的MC层级sd、rootdomain与cpu rq绑定 static int build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr) { ...... //遍历每个cpu，获取最底层的调度域MC，将其与d.rd以及cpu rq绑定起来 for_each_cpu(i, cpu_map) { rq = cpu_rq(i); sd = *per_cpu_ptr(d.sd, i); /* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */ if (rq->cpu_capacity_orig > READ_ONCE(d.rd->max_cpu_capacity)) WRITE_ONCE(d.rd->max_cpu_capacity, rq->cpu_capacity_orig); cpu_attach_domain(sd, d.rd, i); } ...... } for_each_cpu遍历所有cpu，sd = *per_cpu_ptr(d.sd, i)获取的是MC层级的调度域，最后调用cpu_attach_domain进行绑定。 static void cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu) { ...... sched_domain_debug(sd, cpu); rq_attach_root(rq, rd); // 将新的root domain与cpu rq绑定，rd->rd = rd。 tmp = rq->sd; rcu_assign_pointer(rq->sd, sd); //将新的sd与rd->sd 绑定 dirty_sched_domain_sysctl(cpu); destroy_sched_domains(tmp); update_top_cache_domain(cpu); } 将每个cpu的MC层级的调度域sd赋值给当前cpu调度队列的rq->sd，将root domain 赋值为当前cpu调度队列的rq->rd。 总结： 根据CPU架构的层次，从下到上，分为MC层级->DIE层级，每个层级使用struct sched_domain_topology_levels（SDTL）数据结构描述。 考虑多核的锁竞争访问，每层级SDTL为每个cpu定义了sd/sds/sg/sgc数据结构。 在同一层级（如MC层级）由SOC架构（DTS描述）来确定那些是兄弟关系(core_siblings)，兄弟关系在调度域sd中使用sd->span来描述，在调度组中sg中使用sg->cpumask来描述，属于兄弟关系的cpu核属于一个调度域。DIE层级的sg->cpumask = MC层级sd->span。 对于MC层级来说每个cpu就是一个调度组sg，兄弟关系的sg归属为一个调度域，该调度域的sg形成一个环形链表，但不同cpu指向的环形链表首元素是不同的，首元素指向的都是自己cpu所在的sg，如cpu0的链表顺序是(0,1,2,3)，cpu1的链表顺序是(1,2,3,0)。 对于DIE层级来说每个cluster是一个调度组，每个调度组有多个cpu，调度组覆盖的cpu范围子调度域的cpu覆盖范围，也可以认为是每个cluster的cpu范围。同时调度组选取的是子调度域cpu范围的第一顺序cpu作为调度组，也可以认为是每个cluster的第一个cpu。 对于DIE层其每cpu的调度域sd.child指向下一级MC层每cpu调度域sd，而MC层其每cpu调度域sd.parent指向上一级DIE层每cpu调度域sd。 负载均衡时会优先从最底层级进行均衡，从下往上意味着可选择的cpu会越来越多，但是均衡的代价也会越来越大。

各任务负载、各cpu的算力（频率+架构）、任务迁移开销（调度域，调度组）。 root@Linux:/# cat /proc/loadavg 3.49 3.43 3.54 4/131 3065 cat /proc/loadavg可以获取CPU全局平均负载，前面的三个值分别表示为1分钟、5分钟、15分钟系统平均负载，第四个字段正在运行的进程数量/总进程数量，第五个字段最后一个运行的进程ID。 公式①：CPU负载=就绪队列总权重 早期系统计算系统负载是所有CPU上就绪队列的总权重，但是使用权重来计算是比较局限的，因为负载考虑的是对CPU资源占用情况，而权重高的进程可能并不一定会一直运行，或许运行一会就一直睡眠，因此使用就绪队列的总权重并不合理。 在权重的基础上进行演化，从全局考虑整体就绪队列到追踪每一个调度实体对CPU资源的占用，从而调度器有更精细的控制。在一段时间内，将每个任务可运行时间考虑进去（可运行表示处于就绪队列中，但并不是在执行），这样就能够代表任务对CPU的资源占用情况。 公式②：load = weight * t /T 采样一段时间T，任务处于运行状态时间为t,该任务对CPU的负载可运行时间与采样时间的比值再与权重相乘。 公式②看起来是比较合理，但是仍然存在问题，考虑一些场景，假设相同优先级A任务和B任务在某天同一时刻启动，A任务运行了半天就一直睡眠，而B任务一启动就睡眠半天，然后一直运行。按照公式②的计算A和B的负载是一样的，显然不合理，在最近的这段时间内任务B的负载要高于A，因此基于公式再进行了演化，加入历史运行情况的参数。 公式③：load = weight * (t0*y^0+ t1*y^1 + t2*y^2+...+tn*y^n)/T 负载计算将历史运行因素考虑进去，但是历史因素的因素有一个衰减（decay）过程，也就是说离当前最近的影响最大，离当前时间越远影响程度越小，所以衰减因子y^32=0.5。为了便于系统计算对公式在进行了量化，采样周期为1ms，所以公式为 公式④L = L0 + L1*y^1 + L2*y^2 + L3* y^3 +.... Ln*y^n。 下面是描述调度实体或就绪队列的负载信息。 struct sched_avg { u64 last_update_time; u64 load_sum; u64 runnable_sum; u32 util_sum; u32 period_contrib; unsigned long load_avg; unsigned long runnable_avg; unsigned long util_avg; struct util_est util_est; } ____cacheline_aligned; last_update_time: 上次更新负载信息的时间点，可用于计算差值。 load_sum：调度实体来说是任务累计历史衰减总时间,包括running+runnable+blocked，对于调度队列来说是其所有任务累计工作总负载，前者统计的仅仅是时间，后者是工作负载即时间乘权重。 runnable_sum: 调度实体来说是running+runnable累计历史衰减总时间， util_sum:调度实体来说正在运行状态下的累计衰减总时间，调度队列来说其所有正在运行任务的总时间。 period_contrib: 存放着上一次时间采样时，不能凑成一个周期的剩余时间。 _avg/util_avg:根据_sum计算得到的负载均值。 util_est:辅助计算阻塞之前load avg信息。 上面是struct cfs_rq/struct sched_entity 与struct sched_avg之间的关系，也就是说在计算负载时有调度实体的负载和就绪队列的负载。 /* * sched_entity: * * task: * se_weight() = se->load.weight * se_runnable() = !!on_rq * * group: [ see update_cfs_group() ] * se_weight() = tg->weight * grq->load_avg / tg->load_avg * se_runnable() = grq->h_nr_running * * runnable_sum = se_runnable() * runnable = grq->runnable_sum * runnable_avg = runnable_sum * * load_sum := runnable * load_avg = se_weight(se) * load_sum * * cfq_rq: * * runnable_sum = \\Sum se->avg.runnable_sum * runnable_avg = \\Sum se->avg.runnable_avg * * load_sum = \\Sum se_weight(se) * se->avg.load_sum * load_avg = \\Sum se->avg.load_avg */ PELT基本原理 公式④L = L0 + L1*y^1 + L2*y^2 + L3* y^3 +.... Ln*y^n。 在计算负载时，计算时刻并不能这么精确，这次计算的时间距离上一次计算负载的时间跨越了多个周期，如上图所示，last_update_time时刻表示上一次计算负载，而这次计算的负载为now时刻。时间可以分为3段d1、d2、d3，之所以这样划分当前计算时刻与上一次计算负载的时刻并不一定落在周期点。假设last_update_time时刻的计算出来的负载为，根据划分的3段，因此系统的负载计算为：Llast，先不考虑权重，那么当前时刻负载为： 从这个公式来看，负载的计算可以分为3段。 val*y^p计算 先来看(d1+ Llast) * y^p 中代码的实现，由于y^p 的值是浮点，为了避免浮点运算可以转化为y^p = y^p * 2^32 >> 32，相当于先乘以2^32 再右移32（右移就是除），而y^p * 2^32 再系统中提前计算好了存放再数组runable_avg_yN_inv中，如下： static const u32 runnable_avg_yN_inv[] __maybe_unused = { 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6, 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85, 0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581, 0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9, 0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80, 0x85aac367, 0x82cd8698, }; //计算val * y^n，y^32 = 0.5。 static u64 decay_load(u64 val, u64 n) { unsigned int local_n; //经过LOAD_AVG_PERIOD * 63周期后，就衰减为0了 if (unlikely(n > LOAD_AVG_PERIOD * 63)) return 0; /* after bounds checking we can collapse to 32-bit */ local_n = n; //如果衰减周期大于32，则计算方式有调整如下，反之直接查表， //val * y^p =val * (y^32)^(p/32) * y^(p%32) * 2^32 >>32, p=p/32 + p%32, //而y^32=1/2,所以val * (y^32)^(p/32) =val >> (p/32), //y^(p%32) * 2^32 就先计算p%32，然后从runnable_avg_yN_inv表中查询。 if (unlikely(local_n >= LOAD_AVG_PERIOD)) { val >>= local_n / LOAD_AVG_PERIOD; //val * (y^32)^(p/32) =val >> (p/32) local_n %= LOAD_AVG_PERIOD; //p%32,便于从runnable_avg_yN_inv查询 } val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32); //val * runnable_avg_yN_inv[local_n] >> 32 return val; } 1024*(y^1 + y^2 +......+ y^p-1)计算 由等比求和公式 y^p + y^p+1 + y^P+2 +......+ y^p+n=(y^p-y^p+n+1)/(1-y), 得 y^1 + y^2 + y^3 +......+ y^p-1 =( y^1-y^p) / (1-y) =( 1-y^p) / (1-y) - (1-y)/(1-y)=( 1-y^p) / (1-y)-1 因为0<y<1，所以当趋于0（体验下什么叫做0.99^n和1.11^n），所以上面的公式再次简化为如下： 代码实现 Lnow =d3 + 1024*(y^1 + y^2 + y^3 +......+ y^p-1) + (d1+ Llast) * y^p = Llast * y^p（step1）+ [d1 * y^p + LOAD_AVG_MAX - *LOAD_AVG_MAX - 1024 + d3]（step2） accumulate_sum是计算负载的核心函数，计算的负载结果并不是会增加而有可能是减少，负载的变化都在这个函数中实现，当调度实体没有在就绪队列时，随着时间的增加其对CPU的负载会逐渐减弱，而如果调度实体在就绪队列时，对CPU的负载就会逐渐增加。 static __always_inline u32 accumulate_sum(u64 delta, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */ u64 periods; // sa->period_contrib是上次更新负载不足1024us周期的时间，delta是上次更新负载到现在要计算负载经过的时间，要计算有多少个周期需要加上period_contrib，见4.1.1的图。 delta += sa->period_contrib; periods = delta / 1024; /* A period is 1024us (~1ms) */ /* * Step 1: decay old *_sum if we crossed period boundaries. */ if (periods) { //step1: 分别计算 Llast * y^p，历史负载的衰减 sa->load_sum = decay_load(sa->load_sum, periods); sa->runnable_sum = decay_load(sa->runnable_sum, periods); sa->util_sum = decay_load((u64)(sa->util_sum), periods); /* * Step 2 */ delta %= 1024; //当load=0时，说明当前的调度实体不处于running或runnable，因此不需要计算新增负载负载贡献，而只计算负载衰减，过了一段时间周期，一直没得到运行，累计的负载衰减step1的操作就是衰减。 //step2: 计算[d1 * y^p + LOAD_AVG_MAX - *LOAD_AVG_MAX - 1024 +d3]，period即P。 //当load !=0，说明调度实体处于running或runnable，就需要计算增加的负载贡献。 if (load) { //d1= 1024 - sa->period_contrib, d3=delta % 1024。 contrib = __accumulate_pelt_segments(periods, 1024 - sa->period_contrib, delta); } } //更新不足一个周期贡献值 sa->period_contrib = delta; if (load) sa->load_sum += load * contrib; if (runnable) sa->runnable_sum += runnable * contrib << SCHED_CAPACITY_SHIFT; if (running) sa->util_sum += contrib << SCHED_CAPACITY_SHIFT; return periods; } static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) { u32 c1, c2, c3 = d3; /* y^0 == 1 */ c1 = decay_load((u64)d1, periods); //计算d1 * y^p c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; //计算LOAD_AVG_MAX - *LOAD_AVG_MAX - 1024 return c1 + c2 + c3; } 负载更新 负载使用的是struct sched结构体来进行描述，负载的描述对象分为调度实体se负载（包含group se和task se）和调度实体所在的就绪队列cfs_rq负载。cfs_rq的负载可以先简单的理解为是其队列中所有调度实体se的贡献，当然不能简单是相加关系，需要考虑权重、cpu算力等因素，顶层的cfs_rq负载实际就等于CPU的负载。 追踪调度实体se的负载是基础，当调度实体se的负载变化时进而也会影响到其所在cfs_rq队列的负载变化，cfs_rq.load = f(se.load)，负载更新的核心函数使用update_load_avg来实现，因此本小结主要就是围绕该函数进行解读。 负载的更新实际是基于某个时间刻进行计算，对于一个调度实体来说其有不同的运行状态，每个状态对CPU的负载计算是不相同的。 - 当一个任务处于running（正在运行）或runnable（就绪队列中）时，那么对系统的负载计算是贡献的，因此负载需要在原来的基础上（上一个时刻的负载衰减值）加上当前新增的贡献负载，也就是说任务处于就绪队列或者正在运行对于CPU来说就是有负荷的。 - 当一个任务没有正运行或没有处于就绪队列中如处于睡眠态，那么也要考虑其任务的历史负载，睡眠的任务必然是此前运行过因为得不到某个资源而从就绪队列中移除，而该任务此前的任务负载也需要考虑进去，只不过会随着时间的增加，任务的负载会不断的衰减，最终趋于0（要是中间没有再次运行）。 如下图负载更新可以分为四部分，触发负载更新，更新task和所属cfs_rq平均负载，负载、运行负载、利用率计算，group se负载传播，本章节会按这四个部分依次展开。 触发负载更新 en/dequeue_task_fair：任务被唤醒/睡眠、CPU/Cgroup迁移、任务调度参数变化等会导致任务出入队变化就会触发负载更新。 set_next_entity：进程切换设置下一个要运行的任务。 put_prev_entity：进程切换将被抢占的任务重新放入队列。 entity_tick：周期性的tick触发。 __sched_group_set_shares：修改task group的调度参数。 de/attach_entity_cfs_rq:唤醒新创建任务、非CFS调度类切换CFS调度类等，cfs_rq在cgroup的迁移等等。 上面列出了一部分场景会触发负载更新，如任务的出入队列、设置下一个要运行的任务、被抢占的任务重新入队、周期性调度更新等，下面以几个场景来进行说明。 （1）任务入队enqueue_task_fair->enqueue_entity。 static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) { ...... for_each_sched_entity(se) { ... if (se->on_rq) break; enqueue_entity(cfs_rq, se, flags); ... } //se入队所属cfs_rq，并向上遍历直到对应的组调度实体被加入到cfs_rq为止（se要调度，//其父实体也必须入队），enqueue_entity中会更新一次负载，见下，此次的负载更新主要//负责从下到上对应的父调度实体加入到就绪队列为止，再往上就调用下面的code来进行//更新了，如下图示例只更新到cfs_rq2层级权重。 for_each_sched_entity(se) { update_load_avg(cfs_rq, se, UPDATE_TG); se_update_runnable(se); //更新se所属cfs_rq上的任务数量，负载跟该值也有关系。 update_cfs_group(se); } //这里就是补全了再往上层级剩余部分se和cfs_rq负载信息，如下如更新cfs_rq1+cfs_rq0 //权重 .... } static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { ...... update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH); //更新load avg多传递了一个DO_ATTACH的flag，当一个任务从一个队列迁移到一个新队 //列，那么PELT的层级结构发生了变化，这时候需要负载的传播过程。 se_update_runnable(se); update_cfs_group(se); account_entity_enqueue(cfs_rq, se); .... } 当调度实体se入队时，自然调度实体se的负载是要更新的，又因为se所属的cfs_rq是其下所有se的负载和，所以当其他se变化时，那么cfs_rq的负载也需要做对应的更新，所以可以在update_load_avg函数中可以看到会先更新se再更新se所属的cfs_rq。而在一个cpu的调度队列中，由于组调度的引入，会有多个层级的情况，因此当最底层的se变化时，对应的cfs_rq变化继而在影响上一层级gse变化，再影响ges所属cfs_rq的变化直到最顶层。简而言之，最底层的se和cfs_rq负载变化会导致上一层的se（gse）和cfs_rq负载也随之变化，直至顶层的cfs_rq。 （2）任务出队dequeue_task_fair->dequeue_entity。 这是入队的逆过程， static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) { ...... for_each_sched_entity(se) { ... dequeue_entity(cfs_rq, se, flags); ... } for_each_sched_entity(se) { update_load_avg(cfs_rq, se, UPDATE_TG); se_update_runnable(se); update_cfs_group(se); } .... } static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { ...... update_load_avg(cfs_rq, se, UPDATE_TG); //更新调度实体及所属cfs_rq的负载 se_update_runnable(se); //如果是group se，任务已经出队（如进入阻塞状态），那么其runnable_weight需要更新。 //因为对于group se，只有在计算runnable_sum才会考虑任务数量，但是任务已经出队了 //就不再是runnable状态了，是block或者dead状态了。 //这里并没有更新，那么任务阻塞出队cfs rq的负载没有变化，只不 account_entity_enqueue(cfs_rq, se); //将调度实体的load weight从cfs rq中加上。 update_cfs_group(se); .... } 从上述队列出队来看，并没有将load_avg负载减去，而是变化了runnable相关的负载计算，所以即使任务出队进入阻塞状态，其负载依旧在load_avg中，只不过随着时间的增长而衰减。 task与cfs_rq平均负载 这一小节我们主要来分析一下update_load_avg函数主要的作用，直接上代码吧。 static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 now = cfs_rq_clock_pelt(cfs_rq) //获取当前的时刻，减去了空闲时间，也就是该调度实体时间运行的时刻。 int decayed; /* * Track task load average for carrying it to new CPU after migrated, and * track group sched_entity load average for task_h_load calc in migration */ //先计算调度实体的调度负载。 if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) __update_load_avg_se(now, cfs_rq, se); //计算调度实体所属cfs_rq的负载。 decayed = update_cfs_rq_load_avg(now, cfs_rq); //group se负载传播：如果调度实体是group se，其下任务有新增或移除等变化，则需要重//新更新group se所在层次的负载，group se下的cfs rq，负载变化要传播到上一层级（group se所在层级）。 decayed |= propagate_entity_load_avg(se); //se->avg.last_update_time为0且DO_ATTACH，表示任务从其他队列迁移过来新入队的。 if (!se->avg.last_update_time && (flags & DO_ATTACH)) { /* * DO_ATTACH means we\'re here from enqueue_entity(). * !last_update_time means we\'ve passed through * migrate_task_rq_fair() indicating we migrated. * * IOW we\'re enqueueing a task on a new CPU. */ //刚加入队列，计算se的负载主要是根据当前所属cfs_rq以及cpu算力等信息进行计//算，接着再将se的负载信息load、runnable、tutil传播到所属cfs_rq的负载。最后会//调用add_tg_cfs_propagate启动负载传播，只有调用了这个函数上面的//propagate_entity_load_avg才会具体执行传播动作。 attach_entity_load_avg(cfs_rq, se); //更新group的平均负载。 update_tg_load_avg(cfs_rq); } else if (decayed) { //负载有变化 cfs_rq_util_change(cfs_rq, 0); //触发是否需要调频 if (flags & UPDATE_TG) update_tg_load_avg(cfs_rq); } } 负载、运行负载、利用率计算 负载计算可以分为两类，调度实体（task se、group se）和调度实体所属的cfs_rq；调度实体的计算是调用函数__update_load_avg_se实现，cfs_rq的计算是调用__update_load_avg_cfs_rq来实现，但是最终都会调用___update_load_sum来计算，只是传入的参数不一样。但两类都使用struct sched_avg结构体来进行描述，主要的核心就是需要先计算出{load|runnable|utils}_sum|avg，计算方法总结如下，后续的代码实际也是围绕这个计算公式来执行。 {load|runnable|utils}_sum’：上一时刻计算的负载。 contrib：上一个时刻到当前时刻负载贡献。 SCHED_CAPACITY_SHIFT:归一化处理，一般是2^10=1024。 divider：LOAD_AVG_MAX - (1024 - avg->period_contrib)，最大负载。 无论load,runnable,running为任何值，只要更新负载上一时刻计算的{load|runnable|utils}_sum’都会衰减。 当load=0时，runable和running也都为0，因为load的取值为se->on_rq，该值为1就已经包含了runnable+running；若该值为0，那么就不是runnable或running，那自然runnable和running为0。 当load≠0，runnable≠0或running≠0，其对应的{load|runnable|utils}_sum会有新增负载贡献。 处于blocked状态的调度实体，不会带来新增负载贡献（load=runnable=running=0），但是会对历史负载进行衰减（step1计算的就是历史负载衰减）。 root@TinaLinux:/# cat /proc/1214/task/1214/sched wifi_daemon (1214, #threads: 2) ------------------------------------------------------------------- se.exec_start : 19745.413299 se.vruntime : 2705.836320 se.sum_exec_runtime : 0.599750 se.nr_migrations : 0 nr_switches : 1 nr_voluntary_switches : 1 nr_involuntary_switches : 0 se.load.weight : 1048576 se.avg.load_sum : 47234 se.avg.runnable_sum : 17325956 se.avg.util_sum : 17325956 se.avg.load_avg : 1024 se.avg.runnable_avg : 361 se.avg.util_avg : 361 se.avg.last_update_time : 19745214464 se.avg.util_est.ewma : 361 se.avg.util_est.enqueued : 361 policy : 0 prio : 120 clock-delta : 83 __update_load_avg_se 参数说明： - load：为se->on_rq，表示当前任务是否处于可运行态，包括runnable + running，对于调度实体来说load要么为0，要么为1。 - runnable：为se_runnable(se)，调度实体是task se则为se->on_rq，如果是group se，则为se->runnable_weight。对于group se来说只要其下有一个se是runnable或running，则group se为runnable或running。runnable_weigh等于处于runnable或running的任务数量。 - running：为cfs_rq->curr se，也就是说当前是否有任务正在运行。 对于task se来说load,runnable,running非0即1；对于group se来说，load,running非0即1，runnable为group se其下运行的任务数量。以下是传入的参数示例： task se： load=runnable=1,running=1 group se： load = 1, runnable = se->runnable_weight, running =1 从上面看出，对于task se与group se的计算，区别主要是runnabe_sum的计算方式不同，group se新增负载贡献需要乘以runnable_weight(group se其下的任务数量)。 {load|runnable|utils}_sum计算的负载只是时间没有权重，但是load_avg需要考虑权重，是权重*时间。 int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se) { //计算{load|runnable|utils}_sum，这里传入三个参数load，runnable，running。 //load：为se->on_rq，se->on_rq=1表示running+runnable //runnable：为se_runnable(se)，这里要考虑当前的调度实体是group se还是task se，如果是task se那就等于se->on_rq，但是如果是group se则为se->runnable_weight，该值实际等于该任务组中running+runnable的任务数量，对于组调度实体来说组内即使有一个任务处于running或runnable那么group se就是running或runnable。 //running：代表当前正在运行的任务。 if (___update_load_sum(now, &se->avg, !!se->on_rq, se_runnable(se), cfs_rq->curr == se)) { //计算{load|runnable|utils}_avg，其中对于load_sum需要乘以权重se_weight(se)。 ___update_load_avg(&se->avg, se_weight(se)); cfs_se_util_change(&se->avg); trace_pelt_se_tp(se); return 1; } return 0; } update_cfs_rq_load_avg load：为scale_load_down(cfs_rq->load.weight)，可以先简单理解为cfs_rq上所有任务的权重和。 runnable：为h_nr_running，表示当前在就绪队列中的任务数量，包含正在运行的任务。 running：为cfs_rq->curr != NULL，cfs_rq队列有任务运行。 下面示例对比task se与cfs_rq。 Task se: load=runnable=1,running=1 group se：load = cfs_rq->load.weight,runnable = cfs_rq->h_nr_running, running =1 从上面公式可以看出，task se和cfs-rq的差别 ① task （group）se的load_sum不考虑权重只考虑时间，而cfs_rq需要考虑整个队列的权重。 ② task se是一个任务，所以 runnable_sum新增负载贡献乘1，而task group 、cfs_rq 计算的runnable_sum需要乘以任务数量。 ③ load_avg对于cfs_rq是不需要乘以权重的，而task se需要相乘权重。 int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq) { //计算cfs_rq的{load|runnable|utils}_sum， //load = cfs_rq->load.weight为当前cfs_rq队列上的权重和，对于64为系统做了缩放。 //runnable = cfs_rq->h_nr_running，当前队列上的任务数量。 //running = cfs_rq->curr != NULL if (___update_load_sum(now, &cfs_rq->avg, scale_load_down(cfs_rq->load.weight), cfs_rq->h_nr_running, cfs_rq->curr != NULL)) { ___update_load_avg(&cfs_rq->avg, 1); trace_pelt_cfs_tp(cfs_rq); return 1; } return 0; } 实际上cfs_rq的负载初值，就是其下task （group）的和，得到初值后，如果没有任务出入队列的情况下，就按照上面的公式进行更新负载，如果说有任务出入队列那么就需要重新更新初值，这个过程叫负载传播。 static void enqueue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { cfs_rq->avg.load_avg += se->avg.load_avg; cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum; } cfs_rq->avg.util_avg += se->avg.util_avg; cfs_rq->avg.util_sum += se->avg.util_sum; cfs_rq->avg.runnable_avg += se->avg.runnable_avg; cfs_rq->avg.runnable_sum += se->avg.runnable_sum; ___update_load_sum __update_load_avg_se和__update_load_avg_cfs_rq最终都要调用___update_load_sum来计算调度实体负载。 int ___update_load_sum(u64 now, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { u64 delta; //delta为当前时刻与上一次计算负载的时间差 delta = now - sa->last_update_time; /* * This should only happen when time goes backwards, which it * unfortunately does during sched clock init when we swap over to TSC. */ if ((s64)delta < 0) { sa->last_update_time = now; return 0; } /* * Use 1024ns as the unit of measurement since it\'s a reasonable * approximation of 1us and fast to compute. */ delta >>= 10; if (!delta) return 0; sa->last_update_time += delta << 10; /* * running is a subset of runnable (weight) so running can\'t be set if * runnable is clear. But there are some corner cases where the current * se has been already dequeued but cfs_rq->curr still points to it. * This means that weight will be 0 but not running for a sched_entity * but also for a cfs_rq if the latter becomes idle. As an example, * this happens during idle_balance() which calls * update_blocked_averages(). * * Also see the comment in accumulate_sum(). */ if (!load) runnable = running = 0; //如果load=0，即cfs_rq->0为0，那么任务不会处于running、runnable，因此也不需要计 //算runnable、running的新增负载贡献。正在运行的任务即使出队了，但是cfs_rq=1。 /* * Now we know we crossed measurement unit boundaries. The *_avg * accrues by two steps: * * Step 1: accumulate *_sum since last_update_time. If we haven\'t * crossed period boundaries, finish. */ //计算*_sum负载。 if (!accumulate_sum(delta, sa, load, runnable, running)) return 0; return 1; } delta为计算当前与上一次更新负载权重的差值，用于后续计算调度负载信息。该函数中会判断load是否等于0，如果为0，说明当前调度实体没有处于running或runnable状态，没有在就绪队列中就不需要计算新增调度负载贡献（注意是贡献，表增量），同时调度实体应该要进行调度负载衰减（没得运行，那么自然对CPU的消耗要降低），因此会调用decay_load对load_sum、runnable_sum、util_sum进行衰减；反之如果load不为0，那么说明调度实体处于running或runnable，那么就需要计算调度负载贡献，最后调度负载等于衰减的负载+新增贡献负载。 负载传播 当一个新创建或从其他cpu迁移的task se加入到一个新的cfs_rq队列时，会导致整个层级的cfs_rq负载发生变化。任务的休眠导致出队的不算？ 会调用attach_entity_load_avg/detach_entity_load_avg来更新cfs_rq load_avg。本章节我们以task se从一个cpu迁移到另外一个cpu的cfs_rq为例说明，update_load_avg->attach_entity_load_avg。 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { /* * cfs_rq->avg.period_contrib can be used for both cfs_rq and se. * See ___update_load_avg() for details. */ u32 divider = get_pelt_divider(&cfs_rq->avg); // /* * When we attach the @se to the @cfs_rq, we must align the decay * window because without that, really weird and wonderful things can * happen. * * XXX illustrate */ //当前调度实体的参数从所属cfs_rq中更新 se->avg.last_update_time = cfs_rq->avg.last_update_time; se->avg.period_contrib = cfs_rq->avg.period_contrib; /* * Hell(o) Nasty stuff.. we need to recompute _sum based on the new * period_contrib. This isn\'t strictly correct, but since we\'re * entirely outside of the PELT hierarchy, nobody cares if we truncate * _sum a little. */ //重新计算utils_sum、runnable_sum、load_sum。 se->avg.util_sum = se->avg.util_avg * divider; se->avg.runnable_sum = se->avg.runnable_avg * divider; se->avg.load_sum = se->avg.load_avg * divider; if (se_weight(se) < se->avg.load_sum) se->avg.load_sum = div_u64(se->avg.load_sum, se_weight(se)); else se->avg.load_sum = 1; //将负载信息{load|runnable|util}_更新累加到cfs_rq中。 enqueue_load_avg(cfs_rq, se); cfs_rq->avg.util_avg += se->avg.util_avg; cfs_rq->avg.util_sum += se->avg.util_sum; cfs_rq->avg.runnable_avg += se->avg.runnable_avg; cfs_rq->avg.runnable_sum += se->avg.runnable_sum; //启动负载传播，使能了这个标志，对于gse类型的调度实体才能调用 //propagate_entity_load_avg进行负载传播。 add_tg_cfs_propagate(cfs_rq, se->avg.load_sum); //触发调频 cfs_rq_util_change(cfs_rq, 0); trace_pelt_cfs_tp(cfs_rq); } 对于组任务调度实体，还需要调用propagate_entity_load_avg函数更新当前层级的负载信息。 static inline int propagate_entity_load_avg(struct sched_entity *se) { struct cfs_rq *cfs_rq, *gcfs_rq; //如果时task直接返回，只有gse才需要传播和更新负载。 if (entity_is_task(se)) return 0; //获取gse其下的cfs_rq gcfs_rq = group_cfs_rq(se); //如果没有启动传播，直接返回，有变化才需要更新，没有就直接返回。 if (!gcfs_rq->propagate) return 0; gcfs_rq->propagate = 0; //获取gse所属的cfs_rq cfs_rq = cfs_rq_of(se); //将gcfs_rq上的runnable_sum传递到其所属的cfs_rq上，后续会不断的往上循环更新。 add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum); //更新gse的utis_avg/sum，所属cfs的utis_avg/sum update_tg_cfs_util(cfs_rq, se, gcfs_rq); //更新gse的runnable_avg/sum，所属cfs的runnable_avg/sum update_tg_cfs_runnable(cfs_rq, se, gcfs_rq); //更新gse的laod_avg/sum，所属cfs的load_avg/sum update_tg_cfs_load(cfs_rq, se, gcfs_rq); trace_pelt_cfs_tp(cfs_rq); trace_pelt_se_tp(se); return 1; } 在更新{utils|runnable|load}_sum|avg的时候，更新gse和所属的cfs_rq，这里的更新与__update_load_avg_se和__update_load_avg_cfs_rq的调用计算是不是重复了？毕竟调用关系是update_load_avg中先调用__update_load_avg_se和__update_load_avg_cfs_rq分别计算se和cfs_rq，然后再调用propagate_entity_load_avg进行更新。答案显然不是，这里的更新可以认为是设置初始值，因为并不是每次都会调用且必须是group se类型才会调用propagate_entity_load_avg计算。__update_load_avg_se和__update_load_avg_cfs_rq是在其初始值的基础上进行更新负载。

时间计算 vruntime与runtime static void update_curr(struct cfs_rq *cfs_rq) { struct sched_entity *curr = cfs_rq->curr; u64 now = rq_clock_task(rq_of(cfs_rq)); u64 delta_exec; if (unlikely(!curr)) return; //实际运行时间 = 当前时刻 减去上次执行时刻 delta_exec = now - curr->exec_start; if (unlikely((s64)delta_exec <= 0)) return; //重新更新开始执行时刻 curr->exec_start = now; schedstat_set(curr->statistics.exec_max, max(delta_exec, curr->statistics.exec_max)); //累计进程实际运行的时间 curr->sum_exec_runtime += delta_exec; schedstat_add(cfs_rq->exec_clock, delta_exec); //累计计算进程的虚拟时间，公式vruntime = delta_exec*（nice_0_weight/weight） curr->vruntime += calc_delta_fair(delta_exec, curr); //更新min_vruntime update_min_vruntime(cfs_rq); if (entity_is_task(curr)) { struct task_struct *curtask = task_of(curr); trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime); cgroup_account_cputime(curtask, delta_exec); account_group_exec_runtime(curtask, delta_exec); } account_cfs_rq_runtime(cfs_rq, delta_exec); } schduer_tick最终会update_curr来个更新当前进程的相关时间信息，包括进程实际运行的时间runtime，虚拟时间vruntime一级min_vruntime。 ideal_runtime 在Linux系统中，为了保证每个进程在一段时间内至少能够运行的机会，系统使用sched_period来表示系统周期，也就是将时间划分成n个sched_period，通常值时6ms，用户可以进行修改。而在这个period周期内，根据各进程的权重来进行瓜分。 Idea_runtime表示每个进程在这个period周期内，可以调度的执行的最长时间，但并不是累计值，比如在period=15ms，进程A的ideal_runtime=6ms，当进程A运行了4ms由于等待某个资源让出了调度，后续获得资源继续运行并不是说进程A只能再运行2ms了，而是运行不超过6ms就行，也就是说ideal_runtime限制的是每次运行不超过的时间，并不算累计值。 在计算ideal_runtime的时候，需要考虑当前进程是否处于任务组内，处于任务组内的进程ideal_runtime相当于是在组内进行按权重划分。在引入任务组后，进程的组织方式可以按照层次来划分，调度实体分为任务调度实体和组调度实体，当然都是使用struct sched_entity来描述。按照层次来划分后，无论调度实体处理哪一个层次，其调度实体ideal_runtime的时间在其平行层次的树中按比例来计算获取，可以简计为 A.ideal_runtime = A.weight / cfs_rqX.load，其中cfs_rqX.load为调度实体所处层级所有进程权重之和。 tse.ideal_runtime = tse.weight / cfs_rq.load = tse.weight / (tse.weight + gse.weight)。 tse3.ideal_runtime= gse2.ideal_runtime * tse3.weight / cfs_rq2.load gse2.ideal_runtime = gse.ideal_runtime * gse2.weight / cfs_rq1.load gse.ideal_runtime = period * gse.weight / cfs_rq0.load tse3.ideal_runtime = period * gse.weight / cfs_rq0.load * gse2.weight / cfs_rq1.load * tse3.weight / cfs_rq2.load 由上公式，period表示当前的运行周期的总时间，根据以上公式，因为都是相乘（ABC与CBA一样），所以计算调度实体的ideal_runtime可以从下往上进计算。 对于tse3处于最底层级L2，所以其权重先计算period * tse3.weight / cfs_rq2.load得到C，然后计算Cgse2.weight / cfs_rq1.load得到B，最后再计算Bgse.weight / cfs_rq0.load得到最终tse3的ideal_runtime。 对于tse处于最高层级L0，也可以从下往上计算，只不过上面没有了，因此就只遍历一次得到结果ideal_runtime = gse.weight / cfs_rq0.load。 在软件上的实现也就变得简单很多了，调度实体se中有一个成员parent指向其父实体，如果parent为空表示没有父实体，也就处于最高层级，不存在任务组内，因此在代码中只要根据se从下往上遍历即可。 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) { unsigned int nr_running = cfs_rq->nr_running; u64 slice; if (sched_feat(ALT_PERIOD)) nr_running = rq_of(cfs_rq)->cfs.h_nr_running; 当前层级tse与gse个数之和 slice = __sched_period(nr_running + !se->on_rq); 一个周期的运行时间period for_each_sched_entity(se) { struct load_weight *load; struct load_weight lw; cfs_rq = cfs_rq_of(se); load = &cfs_rq->load; if (unlikely(!se->on_rq)) { lw = cfs_rq->load; update_load_add(&lw, se->load.weight); load = &lw; } //slice=slice * (se->load.weight / se->cfs_rq->load.weight) //根据权重比例逐级往上计算分配到的物理时间。如果不是属于组任务，则只有一级。 slice = __calc_delta(slice, se->load.weight, load); } if (sched_feat(BASE_SLICE)) slice = max(slice, (u64)sysctl_sched_min_granularity); return slice; } 在设置抢占调度标志章节系统会调用scheduler_tick周期性的检测任务是否超过运行时间，如果超过了就会设置抢占标志位，让出调度权。 static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { unsigned long ideal_runtime, delta_exec; struct sched_entity *se; s64 delta; bool skip_preempt = false; ideal_runtime = sched_slice(cfs_rq, curr); 计算当前进程一个周期内可以运行的时间。 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; 实际运行时间。 如果运行时间超过了一个周期内可调度的时间，则设置可抢占标志。 if (delta_exec > ideal_runtime) { resched_curr(rq_of(cfs_rq)); clear_buddies(cfs_rq, curr); return; } ...... } 任务创建 任务出入列 入就绪队列 出就绪队列 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) { struct cfs_rq *cfs_rq; struct sched_entity *se = &p->se; int task_sleep = flags & DEQUEUE_SLEEP; int idle_h_nr_running = task_has_idle_policy(p); bool was_sched_idle = sched_idle_rq(rq); util_est_dequeue(&rq->cfs, p); //迭代遍历每个调度实体，其中se是当前迭代的调度实体 for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); //获取se所属的CFS实时队列cfs_rq dequeue_entity(cfs_rq, se, flags); //从CFS队列中取出当前的调度实体。 cfs_rq->h_nr_running--; //减少实时队列正在运行的任务数量 cfs_rq->idle_h_nr_running -= idle_h_nr_running; //减少空闲空闲状态下的任务数量 if (cfs_rq_is_idle(cfs_rq)) //如果实时队列变为空闲状态 idle_h_nr_running = 1; /* end evaluation on encountering a throttled cfs_rq */ if (cfs_rq_throttled(cfs_rq)) //如果实时队列被限制，则直接结束处理。 goto dequeue_throttle; //如果实时队列的负载权重大于0，则说明实时队列还有其他调度实体，将调度实体 //更新为其父调度实体，并设置接下来任务选择偏向于从当前实时队列中选择任务。 /* Don't dequeue parent if it has other entities besides us */ if (cfs_rq->load.weight) { /* Avoid re-evaluating load for this entity: */ se = parent_entity(se); //获取父调度实体 /* * Bias pick_next to pick a task from this cfs_rq, as * p is sleeping when it is within its sched_slice. */ if (task_sleep && se && !throttled_hierarchy(cfs_rq)) set_next_buddy(se); //设置下一个调度实体 break; } flags |= DEQUEUE_SLEEP; } trace_android_rvh_dequeue_task_fair(rq, p, flags); for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); //更新CFS实时队列的负载平均值 update_load_avg(cfs_rq, se, UPDATE_TG); se_update_runnable(se);//更新调度实体的可运行状态 update_cfs_group(se);//更新CFS调度组的信息 cfs_rq->h_nr_running--; cfs_rq->idle_h_nr_running -= idle_h_nr_running; if (cfs_rq_is_idle(cfs_rq)) idle_h_nr_running = 1; /* end evaluation on encountering a throttled cfs_rq */ if (cfs_rq_throttled(cfs_rq)) goto dequeue_throttle; } /* At this point se is NULL and we are at root level*/ sub_nr_running(rq, 1); /* balance early to pull high priority tasks */ if (unlikely(!was_sched_idle && sched_idle_rq(rq))) rq->next_balance = jiffies; dequeue_throttle: util_est_update(&rq->cfs, p, task_sleep); hrtick_update(rq); } 任务选择 开启CFS组调度且被抢占的任务是CFS类 struct task_struct * pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { //prev表示当前rq上正在运行的，被抢占的task。 struct cfs_rq *cfs_rq = &rq->cfs; struct sched_entity *se = NULL; struct task_struct *p = NULL; int new_tasks; bool repick = false; again: if (!sched_fair_runnable(rq)) goto idle; #ifdef CONFIG_FAIR_GROUP_SCHED //组调度处理 if (!prev || prev->sched_class != &fair_sched_class) goto simple; //如果被抢占task不属于cfs，则跳转到simple处理。 /* * Because of the set_next_buddy() in dequeue_task_fair() it is rather * likely that a next task is from the same cgroup as the current. * * Therefore attempt to avoid putting and setting the entire cgroup * hierarchy, only change the part that actually changes. */ do { struct sched_entity *curr = cfs_rq->curr; /* * Since we got here without doing put_prev_entity() we also * have to consider cfs_rq->curr. If it is still a runnable * entity, update_curr() will update its vruntime, otherwise * forget we've ever seen it. */ //如果当前cfs_rq队列中存在正在运行的调度实体，则需要更新时间，并检查当前 //cfs_rq上的时间片是否使用完（开启带宽控制），如果使用完，那么cfs_rq上所有的//任务都不能再调度，跳转simple处理。 if (curr) { if (curr->on_rq) update_curr(cfs_rq); //更新时间 else curr = NULL; //检查当前cfs_rq队列runtime是否还有剩余（cfs_rq->runtime_remaining>0） //3.4.4.1描述，如果没有剩余，那么cfs_rq下所有的任务将不再允许调度。 if (unlikely(check_cfs_rq_runtime(cfs_rq))) { cfs_rq = &rq->cfs; if (!cfs_rq->nr_running) goto idle; goto simple; } } //挑选下一个调度实体，选择红黑树最左边的 se = pick_next_entity(cfs_rq, curr); cfs_rq = group_cfs_rq(se); //当前的调度实体是一个任务组,se->my_q !=NULL } while (cfs_rq); //如果是一个任务组，则继续从该任务组从挑选合适的任务 p = task_of(se); //获取当前调度实体对应的task_struct。 trace_android_rvh_replace_next_task_fair(rq, &p, &se, &repick, false, prev); /* * Since we haven't yet done put_prev_entity and if the selected task * is a different task than we started out with, try and touch the * least amount of cfs_rqs. */ if (prev != p) { //被抢占的任务与当前挑选要允许的任务不同。 struct sched_entity *pse = &prev->se; //获取被抢占任务的调度实体。 //循环遍历，直到将要运行的调度实体与被抢占的调度实体或父实体在同一级 while (!(cfs_rq = is_same_group(se, pse))) { int se_depth = se->depth; //获取将要运行的调度实体所在层次 int pse_depth = pse->depth;//获取将被抢占任务调度实体所在层次 if (se_depth <= pse_depth) { //要运行的调度实体层次比被抢占的要浅（在上一级） put_prev_entity(cfs_rq_of(pse), pse); //将其调度实体调整重新入队（运行的时候是不在就绪队列上的，不能调度了，//因此需要加入到就绪队列） pse = parent_entity(pse); //找到其父调度实体，继续循环跟当前要运行的调度实体在同一级 } if (se_depth >= pse_depth) { //要运行的调度实体层次比被抢占的要深（在下一级） set_next_entity(cfs_rq_of(se), se); //设置将要执行的调度实体，主要动作是将当前将要调度的实体出队，要调度的实//体不应该在保存在就绪队列上，而是存储在cfs->curr上。 se = parent_entity(se); //指向其父调度实体 } } //到此时，已经找到将要调度的实体与被抢占的调度实体同一级的父调度实体 //为什么要找将要调度实体与被抢占的实体的父/祖所在同一层级的了，是因为 //调度是从上往下的，其任务组中的任务实体要能够被调度，那必须要让其父 //拿到调度权。 put_prev_entity(cfs_rq, pse); //将被抢占的调度实体（可能是父）重新入队 set_next_entity(cfs_rq, se);//设置当前的调度实体为下一个将要运行调度实体。 } goto done; 未开启CFS组调度或被抢占的任务不是CFS调度类 simple: #endif if (prev) put_prev_task(rq, prev); //将被抢占的进程重新放回就绪队列中，运行的进程是放在cfs_rq->curr上，不在就绪队列上。 trace_android_rvh_replace_next_task_fair(rq, &p, &se, &repick, true, prev); if (repick) goto done; do { //从cfs_rq中重新挑选下一个调度实体 se = pick_next_entity(cfs_rq, NULL); //将挑选的调度实体设置未将要运行的进程并移除就绪队列 set_next_entity(cfs_rq, se); //判断当前的调度实体是任务组调度实体，如果是则在任务组cfs_rq查找调度实体。 cfs_rq = group_cfs_rq(se); } while (cfs_rq); p = task_of(se); done: __maybe_unused; #ifdef CONFIG_SMP /* * Move the next running task to the front of * the list, so our cfs_tasks list becomes MRU * one. */ list_move(&p->se.group_node, &rq->cfs_tasks); #endif if (hrtick_enabled_fair(rq)) hrtick_start_fair(rq, p); update_misfit_status(p, rq); return p; 没有要运行的任务 idle: if (!rf) return NULL; new_tasks = newidle_balance(rq, rf); /* * Because newidle_balance() releases (and re-acquires) rq->lock, it is * possible for any higher priority task to appear. In that case we * must re-start the pick_next_entity() loop. */ if (new_tasks < 0) return RETRY_TASK; if (new_tasks > 0) goto again; /* * rq is about to be idle, check if we need to update the * lost_idle_time of clock_pelt */ update_idle_rq_clock_pelt(rq); return NULL; } 小结 任务的选择分为三种情况：开了组调度且被抢占的任务是CFS类，未开组调度或被抢占的任务不是CFS类，没有任务可运行。 挑选了下一个要运行的任务调用set_next_entity来设置并且把被抢占的任务调用put_prev_entity重新入队。set_next_entity和put_prev_entity两个函数可以看出是一对，当设置要运行的运行时，任务将会从就绪队列出队，用cfs_rq->curr来指向当前正在运行的任务，但是这里需要注意的时出队调用的时__dequeue_entity直接从红黑树中移除，而不是调用dequeue_entity，再去更新时间、计算负载贡献等等，这里尤其要注意的是se->on_rq这个变量，在dequeue_entity该变量se->on_rq=0，表示任务出队，而set_next_entity直接调用__dequeue_entity该值se->on_rq不会变，而是se->on_rq=1，当前正在运行的任务即使从红黑树中被移除的，但是se->on_rq依旧是1，所以该任务并不是完全意义的出队列，因此se->on_rq=1意味着任务是runnable+running（runnable表示任务处于就绪队列中，running表示任务正在运行），这对于后续负载计算的时候影响较大。put_per_entity要做的时候就是将被抢占的任务再次入队与set_next_entity所做事情相对应。 任务切换 参考： https://heapdump.cn/article/2730937

Linux系统都是支持多用户登录，如果一个Linux系统两个用户存在不同的数量的进程，假设A用户有10个进程，B用户有20个进程，如果系统对这30个进程进行平分CPU，实际上是不公平的，因此引入了组调度的概念，即A用户对CPU的占用应该跟B用对CPU的占用各自为50%，A/B用户下的进程再根据得到占用进行划分。系统中有cfs组调度和rt组调度，本小节主要以cfs调度为主。 如上图，组A的进程分别分配到了CPU0和CPU1上运行，在CPU0和CPU1上的进程各自组合成一个调度实体G1，两个组在各自的CPU上互不影响。以CPU0为例，G1和P1在一颗红黑树中进行调度，G1获得的“调度资源”，将需要“平分”给其组员（组进程）。 基本原理 使用struct task_group来描述任务组，下面是struct task_group的数据结构，后续的组用tg简称。 kernel/sched/sched.h struct task_group { struct cgroup_subsys_state css; struct sched_entity **se; //动态数组，对应每个cpu上调度实体 struct cfs_rq **cfs_rq;//动态数组，对应每个cpu上调度实体下的进程集合 unsigned long shares; //当前进程组权重 atomic_long_t load_avg; struct sched_rt_entity **rt_se; struct rt_rq **rt_rq; struct rt_bandwidth rt_bandwidth; struct list_head list; 全局所有任务组加入到全局链表task_groups上。 struct task_group *parent; 指向当前调度组的父任务组 struct list_head siblings; 将当前tg挂载到父tg的children链表上。 struct list_head children; 挂着当前tg组所有孩子的tg。 struct cfs_bandwidth cfs_bandwidth; 用于带宽控制 } 所有的任务组会以树结构来组织，在Linux系统中定义了一个全局的根节点struct task_group root_task_group;同时定义一个全局链表LIST_HEAD(task_groups)将所有任务组串在一个链表上。 如上图，G1~G4形成一颗树，根为root_task_group，并且G1~G4串联在链表上task_groups上。 上图是task_group与调度相关数据结构之间的关系。task_group有自己的调度实体struct sched_entity，与task_struct中的调度实体区别是，这里是一个指针数组，指针数组的大小为当前cpu核的个数，因为一组中有多个进程，但是这些进程可以分配到不同的cpu核上，因此每个数组se表示一个cpu核上的调度实体，也就是说当分配一个组时，就会为每个CPU都会维护一个se。同理task_group中cfs_rq红黑树用于记录组任务中在每个cpu下的进程。 上图是一个任务组的示例，任务组tg下进程分配到CPU0和CPU1上运行。全局root_task_group，其se和parent都会NULL，cfs分别指向CPU0和CPU1的cfs队列。因为任务组tg下的进程分布在两个cpu上，因此CPU0和CPU1各自对应一个任务组调度实体group se，tg中的se[0]和se[1]分别指向cpu0和cpu1上组调度实体，组调度实体group和进程调度实体task se处于第一级的平行关系，也就是调度公平。Group se中my_q和tg中cfs指向了任务组进程的队列，该队列处于调度的第二级。所以当组调度实体再与平行关系的进程获得调度机会后，将平均（再按照CFS算法）分给其组内进程进行调度。 创建组调度 权重 gse->load.weigh = tg->weight * grq->load.weight / Sum grq->load.weight tg->weight：任务组默认权重值，等于tg->shares，默认是1024。 grq->load.weight：单cpu下任务组中所有进程的权重之和。 Sum grq->load.weight：任务组中所有进程任务之后，包含分配在各cpu上的。 示例：cpu0 gse->load.weight = 1024 * (1024 + 2048) / (1024 + 2048 + 3072) = 3145728/6144 = 512 上面是理想化的公式模型，但是实际情况Sum grq->load.weight因为需要涉及访问各个CPU上的grq，会导致锁竞争的代价，因此根据上面公式做了近似计算最终得到如下： gse->load.weight = tg-weight * grq->load.weight / (tg->load_avg - grq->avg.load_avg + max (grq->load.weight,grq->avg.load_avg)) 具体演化结果可以参考kernel/sched/fair.c中calc_group_shares函数的注释，这里就不详细阐述了，calc_group_shares通过上面的公式近似计算各个gse分得的权重。 static long calc_group_shares(struct cfs_rq *cfs_rq) { long tg_weight, tg_shares, load, shares; struct task_group *tg = cfs_rq->tg; tg_shares = READ_ONCE(tg->shares); load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg); tg_weight = atomic_long_read(&tg->load_avg); /* Ensure tg_weight >= load */ tg_weight -= cfs_rq->tg_load_avg_contrib; tg_weight += load; shares = (tg_shares * load); if (tg_weight) shares /= tg_weight; return clamp_t(long, shares, MIN_SHARES, tg_shares); } 从公式可以看出，gse的权重与任务组进程个数以及cpu.shares有关系。cpu.shares则是用户节点/sys/fs/cgroup/cpu.shares可控制。 带宽管理 考虑这样的一个场景，假设一个用户只支付了0.5个CPU的费用，那么正常情况下就只能给其0.5个CPU的时间。因此为了限制用户进程对CPU资源占用情况，引入带宽控制，带宽控制是基于分组调度来实现，对一个任务组的运行带宽做限制，也就是在一个周期内，允许一个任务组最多执行多长时间，当任务组运行完了自己的时间，将会被限制不允许运行，即使没有任何任务运行，也需要等到下一个周期。 带宽限制以任务组为单位进行限制，为方便描述原理，上图是只有一个任务组，任务组中的进程被分配到CPU0和CPU1上运行。在task_group数据结构中，cfs_bandwidth成员用于全局描述当前任务组带宽限制，表示在一个period周期内，任务组可使用的时间为quota，这里的时间是任务组中进程的和，当quota使用完后，在整个周期内将会被限制运行，称为throttle操作。 在任务组tg（便于简化假设用户组中只有一个任务组，暂且也称用户组）中有cpu数量的就绪队列，对应上图的cfs_rq0和cfs_rq1，这两个就绪队列所属于任务组。就绪队列中runtime_remaining为当前队列中所有进程可运行的时间，进程运行时就会消耗runtime_remaining，当runtime_remaining被消耗小于0时，可以向全局时间池tg->cfs_b->runtime（表示任务组剩余可使用的时间）中申请，每次申请的值为sysctl_sched_cfs_bandwidth_slice（可节点配置，默认是5ms），当tg->cfs_b->runtime将被耗尽时，不能满足cfs_rqx->runtime_remaining时，cfs_rqx就绪队列将会被移除（对应的gse在上一级中被移除）。 （1）cfs_bandwidth - period: 定时器周期时间 - quota:在周期内任务组可使用的时间 - runtime:剩余时间，quota+runtime = period - period_timer:周期性定时器，定时到达后重置剩余限额runtime为quota。 - slack_timer: - throttled_cfs_rq:所有被throttle的cfs_rq挂入到次链表，用于后期unthrottle cfs_rq操作。 （2）cfs_rq中关于带宽管理描述 - runtime_enabled：该就绪队列是否开启带宽限制。 - runtime_remaining: cfs_rq会从全局时间池申请时间片，当剩余时间片小于0，需要重新申请。 - throttled:判定cfs_rq是否被throttled。 - throttled_list: 被throttled_list的cfs_rq会被挂入到cfs_bandwidth->throttled_cfs_rq链表。 任务组剩余时间 在task_group中，在每个CPU上都有一个cfs_rq红黑树，cfs_rq结构体中有一个runtime_remining用于描述当前组能够运行的时间合计，任务组中的每个任务运行都会消耗掉runtime_remining，当runtime_remaining被消耗完时会从全局时间池申请，如果全局池中的时间也用完了，那么就需要让出调度，cfs_rq就会被throttle。 runtime_remaining的更新在update_curr函数中进行。如上图所示cfs_rq->runtime_remaining-=delta_exec，每个进程将会对runtime_remainning进行消耗，当runtime_remaining不足时，调用assign_cfs_rq_runtime进行申请。 static int __assign_cfs_rq_runtime(struct cfs_bandwidth *cfs_b, struct cfs_rq *cfs_rq, u64 target_runtime) { u64 min_amount, amount = 0; lockdep_assert_held(&cfs_b->lock); /* note: this is a positive sum as runtime_remaining <= 0 */ min_amount = target_runtime - cfs_rq->runtime_remaining; //计算每次向全局时间池要申请的时间片大小，target_runtim由sched_cfs_bandwidth_slice()计算得来，默认是5ms，可以通过sched_cfs_bandwidth_slice_us节点进行修改。 if (cfs_b->quota == RUNTIME_INF) //不限制带宽，remainig可以一直申请到时间片。 amount = min_amount; else { start_cfs_bandwidth(cfs_b); //如果没有启动cfs_b->period_timer就启动 //如果全局时间池时间还有剩余，则分配给当前就绪队列。 if (cfs_b->runtime > 0) { amount = min(cfs_b->runtime, min_amount); cfs_b->runtime -= amount; //时间被瓜分出去 cfs_b->idle = 0; } } //更新当前队列的剩余时间 cfs_rq->runtime_remaining += amount; //如果没有从全局池申请到时间片，则返回0，那么当前进程将会被throttle，让出调度。 return cfs_rq->runtime_remaining > 0; } 任务组一个全局时间池，剩余全局池的时间存储在cfs_b->runtime中，其所属的就绪队列cfs_rq会从全局池中申请可使用的时间，每次申请时间大小为sched_cfs_bandwidth_slice_us（可通过节点来进行修改默认是5ms）。 cfs_rq->runtime_remaining和cfs_b->runtime的区别是？runtime为任务组的全局剩余时间，一个任务组可能包含多个cfs_rq（包含各CPU，以及子任务组等），所以runtime大于runtime_remaining。cfs_rq->runtime_remaining小于等于0时就绪队列cfs_rq的调度实体将会被移除，下次调度将不再被选择到。 限制任务组运行 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) { /* dock delta_exec before expiring quota (as it could span periods) */ cfs_rq->runtime_remaining -= delta_exec; if (likely(cfs_rq->runtime_remaining > 0)) return; if (cfs_rq->throttled) return; /* * if we're unable to extend our runtime we resched so that the active * hierarchy can be throttled */ if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr)) resched_curr(rq_of(cfs_rq)); } 当assign_cfs_rq_runtime从全局时间池中申请不到时间，就会调用resched_curr触发调度。在以下场景下，会检测是否进行限流，如果限制则调用throttle_cfs_rq将当前调度实体（组调度实体）移除就绪队列。 static bool throttle_cfs_rq(struct cfs_rq *cfs_rq) { struct rq *rq = rq_of(cfs_rq); struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); struct sched_entity *se; long task_delta, idle_task_delta, dequeue = 1; raw_spin_lock(&cfs_b->lock); //计算当前cfs_rq剩余可用的时间。 if (__assign_cfs_rq_runtime(cfs_b, cfs_rq, 1)) { dequeue = 0; } else { //如果剩余可用时间为0，则将当前cfs_rq添加到throttled_cfs_rq。 list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq); } raw_spin_unlock(&cfs_b->lock); //还有剩余可使用时间，直接返回 if (!dequeue) return false; /* Throttle no longer required. */ //获取当前cfs_rq对应的调度实体 se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))]; /* freeze hierarchy runnable averages while throttled */ rcu_read_lock(); //遍历cfs_rq子任务组，并累加cfs_rq->throttle_count++ walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq); rcu_read_unlock(); task_delta = cfs_rq->h_nr_running; idle_task_delta = cfs_rq->idle_h_nr_running; for_each_sched_entity(se) { struct cfs_rq *qcfs_rq = cfs_rq_of(se); /* throttled entity or throttle-on-deactivate */ if (!se->on_rq) goto done; //将当前调度实体出队，移除就绪队列 dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP); if (cfs_rq_is_idle(group_cfs_rq(se))) idle_task_delta = cfs_rq->h_nr_running; qcfs_rq->h_nr_running -= task_delta; qcfs_rq->idle_h_nr_running -= idle_task_delta; //如果当前调度实体的就绪队列只有一个，那么父调度实体也要被出队。 //如果调度实体就绪队列不只是一个，那么直接退出，也就只循环一次。 if (qcfs_rq->load.weight) { /* Avoid re-evaluating load for this entity: */ se = parent_entity(se); break; } } //设置被限流的标志 cfs_rq->throttled = 1; return true; } 判断一个cfs_rq是否被限流的标志，就是看cfs_rq-reamaining是否还能申请到时间。 period_time和slack_timer定时器 struct cfs_bandwith结构体中，有两个定时器：period_timer和slack_timer。period_timer计时到达时表示一个period到期（对应cfs_bandwith中的period周期），就会重新更新quota以及解除之前限制的任务。slack_timer则要解决的是全局时间池时间的浪费问题，假设一个cfs_rq从全局池申请了5ms时间片，而cfs_rq中只有一个进程，该进程运行1ms就睡眠一直睡眠了，而整个cfs_rq对应的gse会被dequeue，那么剩余的4ms需要归部分还给全局时间池，当全局池时间累计大于5ms，那么就启动slack_timer将此前ttrottle cfs_rq取消限流。 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) { raw_spin_lock_init(&cfs_b->lock); cfs_b->runtime = 0; cfs_b->quota = RUNTIME_INF; //默认=-1，无限制 cfs_b->period = ns_to_ktime(default_cfs_period()); //初始化period，默认100ms cfs_b->burst = 0; INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq); //初始化链表，被限制的cfs将挂到该链表上 hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED); cfs_b->period_timer.function = sched_cfs_period_timer; //初始化period_timer定时器 hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); cfs_b->slack_timer.function = sched_cfs_slack_timer; //初始化slack_timer定时器 cfs_b->slack_started = false; } init_cfs_bandwidth函数将初始化两个定时器，period_timer在进程入队/更新runtime时间的时候进行启动，启动period_timer后就每个period时间后重新将quota更新给任务组的runtime并将已经节流的cfs_rq重新加入队列。slack_timer是在调度实体出队的时候触发，当调度实体被移除就绪队列时，就检测cfs_rq上剩余可运行时间，如果剩余时间不足1ms就不用归还给全局时间池，否则归还cfs_rq->runtime_remaining - min_cfs_rq_runtime（默认1ms）的时间给全局时间池，归还给全局时间池后需要判断是否可以启动定时器将此前被节流的cfs_rq调度实体重新加入到就绪队列中，判断的条件是全局池中剩余的时间要大于cfs_b->runtime > sched_cfs_bandwidth_slice()（默认要大于5ms），因为cfs_rq每次申请的时间片是sched_cfs_bandwidth_slice()。 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq) { struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime; //计算归还给系统的时间，预留一点时间给就绪队列 //如果没有剩余时间，直接返回。 if (slack_runtime <= 0) return; raw_spin_lock(&cfs_b->lock); if (cfs_b->quota != RUNTIME_INF) { cfs_b->runtime += slack_runtime; //全局池的时间要大于cfs_rq每次申请的时间片并且有就绪队列被节流 if (cfs_b->runtime > sched_cfs_bandwidth_slice() && !list_empty(&cfs_b->throttled_cfs_rq)) start_cfs_slack_bandwidth(cfs_b); } raw_spin_unlock(&cfs_b->lock); //重新更新当前就绪队列的时间片 cfs_rq->runtime_remaining -= slack_runtime; } 小结 （1）cfs_b->runtime: 任务组的进程在一个period周期能可运行的时间为runtime，该值在每个周期到来时会被更新为quota值。 （2）cfs_rq->runtime_remaining:任务组所属的就绪队列cfs_rq，就绪队列中的进程运行后将会消耗runtime_remaining，调度周期会调用update_curr函数更新当前进程执行时间了多少时间即对应runtime_remaining就会被减少，当runtime_remaining不足时就会向全局cfs_b->runtime申请，如果申请不到当前的cfs_rq就绪队列上所以进程就会被节流无法再运行。 （3）节流：就绪队列无法申请到运行时间就会被节流并设置可被抢占（resched_curr），在进程切换的时候会检查被节流的调度实体，并将当前调度实体从就绪队列中移除。 （4）解除节流：下一个周期到来或者另外一个就绪队列让出了时间（slack_timer），节流的队列将会被重新加入到就绪队列得以运行。 将两个进程放到任务组，调整quota_us观察cpu占用率情况。 mkdir -p cgroup/cpu/ mount -t cgroup -ocpu cpu /cgroup/cpu/ cd /cgroup/cpu/ mkdir A cd A echo 1293 > cgroup.procs echo 1294 > cgroup.procs cat cpu.cfs_period_us echo 10000 > cpu.cfs_quota_us 将两个进程绑定到一个核上运行，调整nice观察cpu占用率。 # 将1309和1221都绑定到0核上 taskset -cp 0 1309 taskset -cp 0 1221 renice -1 1221 #动态调整1221进程的优先级 将两个进程放到任务组，并运行多个进程，调整cpu.shares，观察整体任务组分配到的cpu占用率，把相同业务的进程放到一个组，然后调整优先级。 mkdir -p cgroup/cpu/ mount -t cgroup -ocpu cpu /cgroup/cpu/ cd /cgroup/cpu/ mkdir A cd A echo 1293 > cgroup.procs echo 1294 > cgroup.procs echo 1277 > cpu.shares

上一章节中描述了Linux系统中支持多种调度，不同的调度有不同的优先级范围。对于普通进程使用的CFS调度（Completely Fair Scheduler，CFS）。完全公平调度主要核心思想就是保证在一段时间内，每个进程能够运行的时间趋于相等。 为了尽可能的保证一段时间内，每个进程能够运行的时间相等，那么系统就需要计算出每个进程每次能够运行的时间runtime，计算出每个进程的runtime后，系统总是让之前累计运行时间最少的进程先运行，累计运行时间长的进程后运行，这样让进程运行公平。 理想公平调度模型 假设单核CPU上有3个进程，这3个进程都处于就绪队列中，调度器每次调度运行会挑选一个runtime值最小的来运行。 如上图，TASK1先运行了4ms（runtime=4ms）让出调度，调度器查询就绪队列中发现TASK2和TASK3的runtime=0（没运行过），那么此次调度按顺序选择TASK2进行调度运行，TASK2运行了2ms就结束了其runtime=2ms。调度器在就绪队列中继续选择，发现此时TASK3的runtime值最小=0，那么挑选TASK3运行，TASK3运行了5ms让出调度其runtime=5ms。调度器继续从就绪队列中选择进程，发现TASK2 runtime=2ms为最小，因此选择TASK2运行，TASK2运行了4ms，因此runtime累计为=6ms。因此在T1时间内TASK1、TASK2、TASK3分别运行了4ms，5ms，6ms，随着时间的推进，调度器总是选择运行时间最小的先运行，那么各进程获得的运行时间趋于相等。 调度器选择运行时间最小的进程先运行，那是不是进程得到调度后想运行多久就运行多久？答案并不是的，而是有一定的限制。在CFS调度中，规定了一个调度周期period，每个进程能够运行的最长时间等于period/进程数量（当然还没有考虑优先级权重）。规定这样的一个调度周期用来限制每个进程最长的运行时间，避免某个进程一直运行，这样保证一段时间内，每个进程都能够得到至少运行一次。理想情况下如果period为20ms，那么有4个进程，那么平均每个进程的运行时间为5ms。在Linux系统中period并不是固定一个值，因为period固定后，当进程数量越来越多后，每个进程分配的时间就会变少，那么调度器的切换时间就会变得频繁，频繁的切换调度器也就意味着需要频繁的切换上下文，这样对于系统的开销是得不偿失的。因此Linux系统的做法是默认情况下保持一个默认值（默认值6ms），当系统就绪进程个数超过一定数量后，计算处理的运行时间小于6ms后，那么Linux系统会进行动态调整。 kernel/sched/fair.c static u64 __sched_period(unsigned long nr_running) { if (unlikely(nr_running > sched_nr_latency)) return nr_running * sysctl_sched_min_granularity; else return sysctl_sched_latency; } nr_running是系统中就绪进程数量，当超过sched_nr_latency，就无法保证调度延迟，period就转为调度最小粒度。如果没有超过，调度周期就等于调度延迟sysctl_sched_latency（6ms）。 因此根据sched_period可知，总时间固定的情况下，每个进程要运行的理想时间也是确定的。 优先级与虚拟时间 优先级 CFS想要实现的是每个进程能够平均分配时间片，但是现实并非如此，因为任务总是有优先级的，有权重之分，一些任务比较重要，所以它理论上能够运行更多时间（就好比每个人的能力不一样，产生的绩效不一样，所以公司在分配年终奖的时候会倾向于产出更多绩效的优秀员工）。基于上述的场景，引入了权重的概念，权重代表这优先级，也就是不同进程的优先级对应不同的权重，CFS调度器使用nice值来表示优先级，取值范围[-20,19]数值越小，优先级越大，每个nice值都与权重值一一对应。 kernel/sched/core.c const int sched_prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; 引入权重后，分给进程的运行时间就由一下公式计算得来： 进程运行时间=总的CPU时间*（进程权重/就绪队列所有进程权重之和） 如上假设就绪队列中有A和B两个进程，A进程的nice值是0，B的nice值-1。那么A和B各自运行的时间占比为：A=1024/（1024+1277）=44.5%。B=1277/（1024+1277）=55.5%。相当于B比A多运行了10%的时间，也就是说当nice值降低一个挡位，将多获得10%的cpu时间。 虚拟时间 理想情况下，不区分优先级和权重，那么每个进程能够平分运行时间，但是引入权重后，本身在每个进程得到运行的时长就是不一样的，优先级高的进程会得到更长的运行时间。当每个进程本身的能够得到的运行时间就不一样的情况下，按照3.2.1公平调度原则，累计运行时间少的先运行看起来就太适用了。 为了解决这个问题，引入了虚拟时间。虚拟时间用于在加入权重后，衡量每个进程在一段时间内运行是公平的，即各自能够运行的虚拟时间是相等的。 假设A、B、C的进程权重分别是1，2，3。那么A运行Nms、B运行2Nms，C运行3Nms才是公平的。虚拟时间和实际的转化公式如下： vruntime = delta_exec*（nice_0_weight/weight） delta_exec表示实际运行时间，nice_0_weight表示nice值为0的进程权重值，weight表示进程的权重值。为什么是nice_0_weight/weight了，是因为nice_0_weight对应的权重实际运行时间和虚拟运行时间相当。 当引入优先级权重中，就不用runtime值最小来判定优先运行，而是选择vruntime来判断，选择vruntime值最小的优先运行。虚拟时间等于实际运行时间乘以一定比重，这个比重根据优先级来判断。调度保证每个进程在一定时间内运行的虚拟时间相等。 就绪队列中的每个进程对应的vruntime将会被挂到红黑树中，当前CPU进行调度时，将会从左往右开始优先选择，也就是选择vruntime最小的进程先运行。之所以选择红黑树是因为查找速度是O(1)。 min_runtime 考虑这样的一个场景，就绪队列中有A,B,C进程已经各自运行了一段时间了，此时有一个新的进程加入到就绪队列，D加入的时候，runtime应该是多少？如果D从0开始计算，那么D将会一直运行指导追赶上A/B/C三个进程，因为调度的原则就是选择最小的vruntime来运行，如果A/B/C已经运行了几天了，那么当D加入的时候就要先运行几天追赶上A/B/C，这样显然是不合理的。 针对以上的场景，引入了min_runtime。min_runtime记录调度队列中，虚拟时间最小的值。因此当新进程加入的时候，其虚拟时间需要+min_runtime值，这样就能够解决上述场景的问题。

调度类别 进程调度依赖于调度策略（schedule policy），linux内核把相同的调度策略抽象成调度类（schedule class）。不同类型的进程采用不同的调度策略，目前Linux内核中默认采用5种调度类，分别是stop、deadline、realtime、CFS和idle。 Stop：最高优先级的进程，只在多核场景下启用，用于热插拔等场景下停止CPU。 Dealine：用于有严格时间要求的实时进程，优先级为-1。 Realtime：用于普通的实时进程，优先级为0~99。 CFS：完全公平调度，非实时类进程，优先级100~139。 Idle：最低优先级进程，当所有进程都没运行之后运行idle，仅供内核使用。 实际上STOP、IDLE不算是真正意义上的调度类，因为其需要在比较特殊的场景下由内核去执行，因此重点的调度主要分为三个DL,RT,CFS。 Linux用户空间程序可以使用如sched_setscheduler来设定用进程的调度策略，SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE使用CFS。SCHED_FIFO和SCHED_RR用于Realtime。SCHED_DEADLINE用于DL调度。 SCHED_FIFO和SCHED_RR使用Realtime。SCHED_FIFO和SCHED_RR的区别是，SCHED_RR按时间片循环运行，如优先级相同的进程，轮流运行固定长度时间片，而SCHED_FIFO先到先得，会一直运行直到自愿放弃或被更高优先级抢占为止。 Linux系统中，按照优先级顺序从高到低顺序遍历各个调度器，如果某个调度器成功取出了任务，则选择任务进行调度。 kernel/sched/core.c for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; } chrt -p 1234 # 可以查看 pid=1234 的进程的 调度策略 chrt -p -f 10 1234 # 修改调度策略为 SCHED_FIFO, 并且优先级为10 调度时机 调度队列 在linux系统中，定义了一个全局的struct rq类型的数组runqueues，每个CPU对应一个数组成员，定义如下： kernel/sched/core.c static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); kernel/sched/sched.h #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) 根据CPU编号获取rq #define this_rq() this_cpu_ptr(&runqueues) 获取当前进程的rq #define task_rq(p) cpu_rq(task_cpu(p)) 获取进程p所在的rq #define cpu_curr(cpu) (cpu_rq(cpu)->curr) 根据CPU编号获取正在运行的进程 上 图列出了struct rq与struct task_struct之间的关系。每个CPU都对应一个struct rq实体。rq中分别对应3个调度队列（暂不考虑stop、idle类，从数据结构也可以看出stop、idle属于特殊调度类）。 cfs_rq对应的是CFS调度，CFS就绪进程通过红黑树来组织，调度优先选择vruntime最小的进行。 rt_rq对应的是RT调度，RT就绪进程通过链表来组织，每个优先级对应一条链表，相同优先级的进程挂载到同一条链表上；每个链表对应一个bitmap，系统通过查询bitmap的位0或1来判断当前链表中是否有进程就绪。系统调度是一次从高优先级开始遍历查询对应的bitmap，进而选择对应进程运行。 dl_rq对应的是DL调度，后续再阐述。 触发调度 调度顾名思义就是选择一个进程运行，包括系统启动运行的第一个进程，以及运行过程中从当前运行进行切换到另外一个进程。在Linux系统中触发调度的可以分为两类：主动让出调度与抢占式调度（与FreeRTOS的区别，就是抢占式调度这里，FreeRTOS是systick来进行调度，有时间片的概念，而Linux不在有时间片的概念）。 主动调度是CPU主动放弃CPU，包括主动Sleep，读写IO，Mutex等。 抢占调度在Linux系统中并不是立即得到调度权，而是在需要抢占调度时设置一个标志（TIF_NEED_RESCHED），Linux系统在合适时机检测到这个标志会进行调度，因此抢占调度可以分为三个阶段设置抢占调度标志、检测抢占调度标志、选择任务调度。 无论是主动调度还是抢占调度，最终调用的都是函数schedule。 设置抢占调度标志 设置抢占调度的标志一般有以下场景： - Tick调度：Linux系统中有周期性的时钟，会周期性的检测当前的进程是否运行idle_runtime超期。 - 任务创建：新创建任务的时候，会将任务加入到就绪队列中，会根据优先级判定是否需要抢占。 - 任务唤醒：任务在获取到等待的资源从睡眠中唤醒，判定是否需要抢占。 - 任务切换：调整调度类、优先级等。 - 带宽控制：分配给当前运行的任务带宽用尽。 以上只是列出了部分设置抢占调度标志的代码流程，并未全部列出，并且代码流程做了简化。 检测抢占标志 选择任务调度