Linux 任务调度简介

吞吐 和 响应 是评估一个计算机系统性能的主要参数,比较典型的就是在IO系统中,Linux为了提高IO吞吐而将IO先缓存到内存中,这在本质上是牺牲了对某个IO的响应过程并以此来提高吞吐率。这种设计思路在Linux调度器的设计也可以看到,Linux并没有追求硬实时系统的高响应,而是在吞吐和响应之间取得一个平衡。

在Linux中,任务(或者说task_struct,由于Linux中进程和线程没有明显的界限,本文使用任务来描述一个可调度实例)一共有0-139个优先级,其中0-99是给RT 任务使用,100-140给普通任务使用,前者即实时调度策略,进一步又分为SCHED_FIFO和SCHED_RR,后者即普通任务,即SCHED_NORMAL。作为优先级更高的实时任务,SCHED_FIFO和SCHED_RR的任务一旦处于RUNNING(就绪)状态,就可以无条件抢占SCHED_NORMAL的CPU,而只要系统中有RT的任务在运行,SCHED_NORMAL就没有运行的机会。当然,即便是RT 任务,其也会有优先级高低的区别,对于不同优先级的RT任务,显然要严格按照高优先级优先运行的原则,而对于相同优先级的两个RT任务,如果使用SCHED_FIFO,就按照”先来后到”的顺序,只要先运行的任务没有放弃CPU,后来的任务不会被调度到; 如果使用SCHED_RR,同优先级的任务会”周期性”的都被执行到。

Linux中每一个SCHED_NORMAL任务都有一个nice值(-20~+19,缺省为0),这个nice值表示这个任务对于其他任务的”容忍”程度,nice值越大,表示这个任务越好说话,结果是这个任务占用的资源就会减少。早期的Linux通过动态的调整一个动态nice来平衡IO消耗型任务和CPU消耗型任务,不过如今这个工作已经被巧妙的CFS替代了

vruntime = pruntime/weight * delta

上图就是CFS的运作公式,pruntime表示当前任务实际运行的时间,weight是一个与nice值相关的权重,share是系统级/cgroup的调整参数。整个CFS基于红黑树实现进程调度。如下图所示:

上图的数字就是每个任务的vruntime,CFS在进行任务调度的时候,总是调度红黑树中vruntime最小的那个任务,由于IO消耗型的任务本身pruntime就比CPU消耗型的pruntime小,所以整体上IO消耗型的任务的vruntime更小,也就能够获得更多的被调度的机会,这样就能提高系统整体的吞吐。

Continue reading

Linux 内存管理 VI

内存统计是资源评估的重要方面,本文从进程和系统两个视角讨论smem和free两个常用的内存统计工具,Linux进程虚拟地址空间和物理内存的关系如下。

进程视角

进程内存消耗通常使用VSS、RSS、PSS、USS来表征,需要注意的是,进程的这些指标的统计是不包括内核地址空间的。
VSS = 1 + 2 + 3 virtual set size,进程的虚拟地址空间都是通过 task_struct->mm_struct ->mmap->vm_area_struct 来管理其虚拟地址空间,每一个VMA都对应一个Section,所有的VMA对应到进程的内存消5就是VSS,以下两点需要注意:

  1. VSS不是真的体现进程物理内存的消耗,而是虚拟地址空间的消耗。
  2. 对于共享库来说,代码段只有一份,数据段是数据调用进程的,每个进程一份

可以通过如下方式查看VSS(VSZ字段)


$ps aux|more
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root         1  0.0  0.0 185552  5512 ?        Ss   2月16   0:01 /sbin/init noprompt persistent splash
root         2  0.0  0.0      0     0 ?        S    2月16   0:00 [kthreadd]
root         3  0.0  0.0      0     0 ?        S    2月16   0:01 [ksoftirqd/0]

RSS = 4 + 5 + 6,resident set size,只进程实际占用的内存,对于Lib,其所占内存完整的体现在每一个调用的进程RSS中
PSS = 4/3 + 5/2 + 6, proportional set size,同样是体现进程实际占用的内存,不同是对于多进程公共的Lib,按照比例将其占用内存摊派到每一个进程的PSS中
USS = 6 unique set size ,进程独占的内存,比如进程的Heap,分析内存泄漏时通常使用USS。
可以通过如下方式查看USS、PSS、RSS,smem工具通过读取**/proc//smaps和maps**两个文件整理输入如下。


$smem -P ^chromium
  PID User     Command                         Swap      USS      PSS      RSS 
16317 jiang    /usr/lib/chromium-browser/c        0      164     2022    13764
Continue reading

Linux 内存管理 V

严格意义上讲,Linux并不严格区分进程和线程,众所周知,进程是资源分配的基本单位而线程是系统调度的基本单位,但是在Linux中,task_struct作为内核调度的实体,即一个线程,如果其使用的资源完全独立于其他task_struct,那就可以看作一个”进程”,如果其使用的资源完全是另一个task_struct,那就可以看作一个”线程”,如果其使用的资源部分是自己的,部分是其他task_struct的,那就可以看作一个”X程”,扯远了,下图中的task_struct表示一个进程。

当我们malloc一块内存的时候,本质上是调用brk()移动当前进程的堆指针,在内核中的表现为构建相应的虚拟内存结构vm_area_struct,这个vm_area_struct描述了一块虚拟地址空间,其中还保存着相应的权限信息,这些结构构建好之后变使malloc()返回,当用户去写这块分配出来的内存的时候,MMU会发现进程的PT并没有相应的映射表项,进而触发PageFault,内核的PageFault核心处理函数是do_page_fault(),这个函数会检查相应的vm_area_struct权限是否正确,如果检查通过,就会通过buddy分配器(注意不是slab,slab只给内核用)分配相应的内存并修改PT,如此这块虚拟地址空间才真正可用。

Linux 内存管理 IV

根据Memory Hierarchy,系统总是希望将活跃的数据放在更快(通常也更小)的存储介质中来提升系统IO性能,在当代计算机体系中,位于Memory Hierarchy顶端的就是CPU中、负责缓存主存数据的cache,其缓存算法由硬件实现,OS无法插手,但OS可以管理自主存开始剩下的所有的存储介质,基于同样的思想,OS也希望将活跃的数据放在所能控制的最快介质——主存中,将数据从慢介质移动到快介质的Cache replacement policy有很多种,Linux通常使用LRU作为指导思想进行设计,即假设”当前正在使用的有很大可能将来也能用到,而许久不用的将来被用到的可能性很低“。基于这样的思想,Linux中使用Page Fault机制将活跃的数据从Backing Device中缓存到更快的主存中。同样,基于LRU,Linux仍需要将不活跃的数据移出主存,这就是Memory Reclaim——内存回收。

Mapped Page/Anonymous Page

在Linux中,按照Page的background不同将内存页分为两类: Mapped Page和Anonymous Page。Mapped Page即映射页,也可以称之为File Cache、Page Cache,其实质是File-backed Page,file即文件系统中的”file”,比如执行a.out,每个ELF文件的格式头都会记录代码段的位置,内核将代码段映射到(可以理解为mmap)到page中,并赋予其R-X权限,这种Page以File为background,Dirty Flush或Swap Out时就以该位于Backing Device上的File为目标操作,可以看出,对于内核来说,文件就是一块内存。老版本的内核还将Mapped Page区分为两种形式:buffers用于缓存裸设备的数据、cached用于缓存文件系统下文件的数据,不过新版本已经不做区分。Anonymous Page即匿名页,指那些没有明确”文件背景”的page,比如一个进程的Stack、Heap以及COW生成的数据段,这些页在swap out的时候没有一个backed-file供其写入,需要写入swap分区/文件。如果从空间维度考察Swap,Mapped Page和Anonymous Page都是Swap回收的范围

Linux 内存管理 III

DRAM作为Memory Hierarchy 中除CPU内Cache外最快的一级,对于内核性能来说是稀缺资源,所以Linux内核对于物理内存相关的数据结构设计地十分精巧,比如常见的用于分配内存的buddy、Slab分配器、用于规整内存的KSM、用于快速回收内存的RMAP等等,无论哪种精巧的技术,都离不开本文需要讨论的几个与物理内存管理的基础类:node、zone和page。

node

多CPU的硬件架构可以分为两种:UMA和NUMA,前者由多个CPU共享一个内存控制器,这样主板上的所有内存对于所有的CPU都是一样的,缺点是内存控制器容易称为系统瓶颈。NUMA架构中每个CPU使用自己的DRAM Controller,即每个CPU都有接在自己本地的内存控制下的LOCAL内存区间和接在其他CPU内存控制器下的REMOTE内存,显然,对于任何一个CPU而言,访问LOCAL内核要比访问REMOTE的内存要快很多,这样的设计就造成了地址空间中一个物理地址使用不同的CPU的访问不同,即物理地址空间的不均匀,NUMA架构通常可以更好的发挥硬件性能,是当下服务器的主流架构,缺点是系统对内核的内存管理提出了新的挑战。

Continue reading

Linux 内存管理 II

本文主要讨论Linux对物理地址空间的分页机制的实现。

分页机制说来也简单,借助MMU来实现进程虚拟地址空间到物理地址空间的映射,在x86平台中,PGD的基地址存放在CR3寄存器,对于ARM平台,在TIBRx寄存器,每当切换进程上下文的时候,Linux都会将本进程的PGD基地址写入相应的寄存器,如此便更换了虚拟地址到物理地址的映射关系,其产生的结果的就是不同进程中的同一个虚拟地址,经过PageGlobleDentry->PageUpperDentry->PageMiddleDentry->PageTableEntry的映射,找到的是不同的物理页框pfn,也就找到了不同的物理地址。

上图是比较典型的32bit CPU中3级页表模型,在64bit视物理地址总线宽度的不同(eg ARM64采用48bit寻址)可能会采用更多级的页表,但其基本原来都是一样的。

MMU除了要完成相应地址的映射,还要进行权限检查,由于地址映射都是以页为单位的,所以权限检查也是以页为单位的。具体地,每种CPU的MMU支持的权限标志位可能都不一样,以ARM Linux为例,其使用在权限定义在arch/arm/include/asm/pgtable*.h中,包括标记页面是否在主存中的L_PTE_PRESENT、标记页面是否是脏页的L_PTE_DIRTY、以及页面是否可执行的PAGE_SHARED_EXEC等。当Linux触发Page Fault时,就会准备好平台相关的MMU表项结构:映射关系和权限,放在相应的页目录中以供MMU使用。

PHYS_OFFSET,PAGE_OFFSET

这两个宏是系统对于物理地址空间划分很常用的两个宏,由于内核的虚拟地址空间和物理地址空间存在线性映射的关系,通过这两个宏,就可以很快地完成转换

Macro含义备注
PHYS_OFFSETRAM偏移物理地址空间RAM的起始地址
PAGE_OFFSETkernel space偏移虚拟地址空间中内核地址空间的起始地址

pgd_t, pud_t, pmd_t

这几个变量的类型分别是PGD,PUD,PMD的基地址,主要注意的是,作为物理地址,它们的本质是unsigned long, 而不是指针。

*_SHIFT, *_MASK

这两类宏在内存管理也很常见,前者是用于计算相应空间的大小的对数,比如,对于页来说

#define PAGE_SHIFT 12
#define PAGE_SIZE (1<<PAGE_SHIFT)

类似的还有PMD_SHIFT,PUD_SHIFT,PGDIR_SHIFT等。

后者用于计算屏蔽低位的掩码。

#define PAGE_MASK   (~(PAGE_SIZE-1))

ALIGN()

要解释这个宏,就需要看看x&~(2^n -1 )的计算结果。对于一个2的指数,其二进制假设为0x10000,则0x10000 – 1 = 0x01111, ~0x01111 = 0x1111111…0000,可见任何一个数x与该数做”与”运算,低位都会被掩掉,也就是向下对齐的效果,即

#define ALIGN(x,a) (x&~(a-1))

同理,对于向上对齐,我们只需要的使用(x+(a-1))&~(a-1)即可,这就是ALIGN。

ALLIGN(x,a)用于x以a为标准向上对齐的值,a必须是2的次方,定义如下:

#define ALIGN(x,a)              __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask)    (((x)+(mask))&~(mask))

Linux 内存管理 I

CPU的内存空间指由CPU地址总线张成的地址空间,即物理地址空间。这个空间中,借助地址总线,CPU可以进行”字节级”的寻址。

上图是一个主板硬件拓扑的例子(实际开发中用的可能完全不是这个样子,比如全闪主板通常直接从CPU中出SSD控制器),我们以该图为例说明内存管理的基本概念。

视不同架构的CPU,接入物理地址空间的硬件有所不同。对于ARM等RISC处理器,通常将内存条(物理内存),和设备、外设控制器一并接入物理地址空间。这样可以令CPU使用统一的方式访问物理内存和设备IO,这种设备IO方式称之为映射IO,此时,物理地址空间可以被看作分成两部分: 物理内存区间设备IO区间。而在x86体系中,设备IO不占用物理地址空间,intel的CPU为设备单独开辟了16bit的IO空间,在硬件上通过拉低/拉高作为flag的某个引脚或寄存器来区分一个地址是位于内存空间还是IO空间,表现在软件上就是在内核态中使用不同接口函数来操作不同的空间。

对映射IO来说,本质上是CPU将需要访问的地址发给北桥,由北桥决定这个地址是发给DRAM控制器来访问内存,还是将相应的指令发给某个设备。总之,CPU的物理地址空间布局和与之相应的操作方法是BSP级的。

在内核通过启动参数解析了BSP信息之后,CPU看到的就只是一个unified的地址空间,在开启了MMU的情况下,这个地址空间就是虚拟地址空间,否则就是物理地址空间。此外,需要注意的是,低端的DMA引擎通常不能实现对整个DRAM的寻址,这也就是内核将低端内存设置为ZONE_DMA的原因,此外,没有IOMMU的DMA引擎接收一次指令只能将一块连续的内存传递到二级存储介质,而配备了IOMMU的DMA引擎可以实现Scatter/Gatter,即IOMMU负责将DRAM中离散的地址区间映射为DMA引擎中的连续的地址。

其中,CPU与DRAM之间通过MMU连接进而实现虚拟地址到物理地址的转换,而设备通过IOMMU和DRAM连接进而实现IO总线地址到物理地址的转换。

Linux VFS V

一个文件系统获得了内核的支持,仅仅是功能上的可能性,如果要使用,还需要将其mount到rootfs下,才能可见并进而被使用,本文主要讨论mount的实现过程。

SYSCALL_DEFINE5(mount...)	//namespace.c
	do_mount()
		user_path()
		do_remount()
		do_loopback()
		do_change_type()
		do_move_mount()
		do_new_mount()
			struct file_system_type *type
			struct vfs_mount *mnt
			mnt = vfs_kern_mount()
				struct mount * mnt
				mnt = alloc_vfsmnt()
				root = mount_fs()
					struct super_block *sb
					root = type->mount()		//回调file_system_type的mount方法
					sb = root ->d_sb
					security_sb_kern_mount()
					up_write()
				init mnt
				list_add_tail(&mnt->mnt_instance, &root->d_sb->s_mounts)
			do_add_mount(real_mount(mnt),path,mnt_flags)
ext4_mnt()		//ext4
	mount_bdev(...ext4_fill_super)
		struct block_device *bdev
		struct super_block *s
		bdev = blkdev_get_by_path()
		s = sget(...test_bdev_super,set_bdev_super...)		//find or create a superblock
			alloc_super()
				kzalloc()
				init_waitqueue_head()
				s->s_bdi = &noop_backing_dev_info
				...other initialization of s
			set()							//set_bdev_super()
				s->s_bdev = data;
				s->s_dev = s->s_bdev->bd_dev;
				s->s_bdi = &bdev_get_queue(s->s_bdev)->backing_dev_info;
					bdev->bd_disk->queue;
			list_add_tail(...&super_blocks)
			hlist_add_head()
			get_filesystem()
				__module_get()
		sb_set_blocksize()
		fill_super()						//ext4_fill_super()
			struct ext4_sb_info *sbi
			sbi = kzalloc()
			... init sbi...
			ext4_msg()
			setup_timer()
			sb->s_op = &ext4_sops
			sb->s_export_op = &ext4_export_ops
			sb->s_xattr = ext4_xattr_handlers
			sb->s_root = d_make_root()
			ext4_setup_super()
			ext4_ext_init()
			ext4_mb_init()
			sbi->s_kobj.kset = ext4_kset
			init_completion()
			kobject_init_and_add(&sbi->s_kobj, &ext4_ktype...)
		s->s_flags|=MS_ACTIVE
		bdev->bd_super = s
		dget()

bdev文件系统在其初始化时就已经挂载到内核。

bdev_mount()		//bdev	
	mount_pseudo(...&bdev_sops...)
sysfs_mount()		//sysfs
	struct dentry* root
	void * ns
	ns = kobj_ns_grab_current(KOBJ_NS_TYPE_NET);
	root = kernfs_mount_ns

Linux VFS IV

在Linux内核中,一个文件系统包括两部分,一部分是位于磁盘上的管理数据,即文件系统的本体,另一部分是位于内核中的代码,即对VFS中相应接口的实现,没有这部分实现,内核无法识别该文件系统,如此mount、读写等操作也就无从谈起了。

向内核中添加一个文件系统的支持,与其实例无关,即两个分区都是ext4文件系统,但内核对于ext4的支持的代码只需要执行一次,而且,此时也没有从磁盘读取任何数据,这是mount的工作。

本文主要整理内核对各个文件系统的初始化代码

devtmpfs

//devtmpfs
__init devtmpfs_init()		//drivers/base/devtmpfs.c
	register_filesystem($dev_fs_type)
	thread = kthread_run()

sysfs

sysfs_init()		//fs/sysfs/mount.c
	sysfs_root = kernfs_create_root()
	sysfs_root_kn = sysfs_root->kn;
	register_filesystem(&sysfs_fs_type);

proc

proc_root_init()	//fs/proc/root.c
	proc_init_inodecache()
	register_file_system(&proc_fs_type)
	proc_self_init()
	proc_thread_self_init()
	proc_net_init()
	proc_mkdir("fs)
	proc_mkdir("driver")
	proc_mkdir("fs/nfsd")
	proc_tty_init()
	proc_mkdir("bus")
	proc_sys_init()

ext4

__init ext4_init_fs()			//fs/ext4/super.c
	ext4_init_es()
	ext4_init_pageio()
	ext4_init_system_zone()
	kset_create_and_add()
	proc_mkdir("fs/ext4")
	init_inodecache()
	register_filesystem(&ext4_fs_type)	//fs/filesystems.c
		find_filesystem()			
			for (p=&file_systems; *p; p=&(*p)->next)...

bdev

注意到bdev文件系统在初始化时已经挂载

static struct file_system_type bd_type = {
        .name           = "bdev",
        .mount          = bd_mount,
        .kill_sb        = kill_anon_super,
};

__init bdev_cache_init()				//fs/block_dev.c
	struct vfsmount * bd_mnt
	bdev_cachep = kmem_cache_create("bdev_cache")
	register_filesystem(&bd_type)
	bd_mnt = kern_mount(&bd_type)
		kern_mount_data()
			vfs_kern_mount()
				mnt = alloc_vfsmnt(name)
				root = mount_fs(type, flags, name, data);
					 root = type->mount()		//bd_mount	
					 sb = root->d_sb
				mnt->mnt = ...
				list_add_tail(&mnt->mnt_instance, &root->d_sb->s_mounts);
			real_mount()->mnt_ns = MNT_NS_INTERNAL
	blockdev_superblock = bd_mnt->mnt_sb	//for writeback

Linux VFS III

open()的最终目的是:准备好file以及依赖的数据结构。为此,open()主要做了以下几方面工作:

  1. PathWalk找到目标文件
  2. 构造并初始化inode
  3. 构造并初始化file

其中,PathWalk已经讨论过,本文主要聚焦inode和file的构造和初始化


SYSCALL_DEFINE3(open...)	//open.c +1038
	do_sys_open()
		build_open_flags()
		struct filename *tmp = getname()
			getname_flags()
				kname = (char*)result + sizeof(*result)
				result->name = kname
				strncpy_from_user(kname, filename,max)
				result->uptr = filename
		fd = get_unused_fd_flags()
			__alloc_fd()
		struct file *f = do_filp_open()
			struct nameidata nd
			path_openat()
				file = get_empty_filp()
				file->f_flags = op->open_flag
				path_init()
					link_path_walk()
						may_lookup()
						walk_component()
							handle_dots()
							lookup_fast()	
							lookup_slow()	//
								__lookup_hash()
									lookup_dcache()
									lookup_real()
										dir->i_op->lookup()	//ext4_lookup
											inode = ext4_iget_normal()
												ext4_iget()
													struct ext4_inode * raw_inode
													struct inode *inode
													inode = iget_locked()
														inode = find_inode_fast()
														inode = alloc_inode()
														inode->i_ino = ino
														inode->i_state = I_NEW
														hlist_add_head()
														inode_sb_list_add()
													__ext4_get_inode_loc()
														stuct buffer_head *bh
														struct ext4_group_desc *gdp
														ext4_inode_table()
														iloc->block_group = ...
														iloc->offset = ...
														get_bh(bh)
														bh->b_endio = end_buffer_read_sync
														submit_bh*()
															submit_bio()
														wait_on_buffer()
														iloc->bh = ...
													raw_inode = ext4_raw_inode()
													inode->i_blocks = ext4_inode_blocks()
													inode->isize = ext4_isize()
													inode->i_op=...
													inode->i_fop= ...
							inode = path->dentry->d_inode
							nd->inode = inode
				do_last()
					handle_dots()
					lookup_fast()
					complete_walk()
						dentry->d_op->d_weak_revalidate()
					lookup_open()
						struct dentry *dir = nd->path.dentry
						struct inode *dir_inode = dir->d_inode
						lookup_dcache()
						atomic_open()
						lookup_real()
						vfs_create()
					audit_inode()
					mnt_want_write()
					may_open()
					vfs_open()
						struct inode *inode = path->dentry->d_inode
						inode->i_op->dentry_open()
						do_dentry_open()
							inode = f->f_inode = f->f_path.dentry->d_inode
							f->f_mapping = inode->i_mapping
							f->f_op=fops_get(inode->i_fop)
							open = f->f_op->open
							open(inode,f)
					terminate_walk()
		fsnotity_open()

Linux VFS II

PathWalk,顾名思义,就是根据路径找到目标的文件或目录,作为每次open()或opendir()都要执行的过程,其重要性不言而喻。

PathWalk中的很重要的一个概念就是nameidata,这个对象可以看作是PathWalk过程的上下文的封装,记录当前查找所用的路径,如果查找结束,则记录最终的目标路径。作为”上下文”,其主要工作就是封装了在一个过程中各个子逻辑都需要的信息,并随着过程的进行贯穿于各个子过程供其在需要时使用。

在内核中,PathWalk的主要逻辑整理如下


path_init(name, nd)		//根据name初始化nd
lookup_last(nd, &path)	//此时path还是空的
	walk_component()
		handle_dots()
		lookup_fast(nd, path, &inode)
			__d_lookup_rcu()
			struct vfsmount *mnt = nd->path.mnt
			path->mnt = mnt
			path->dentry = dentry
			__follow_mount_rcu(nd, path, inode)
				mounted = __lookup_mnt()
				path->mnt = &mounted->mnt
				//用下溯文件系统的mounted来更新path
				path->dentry = mounted->mnt.mnt_root;
				return 0 ;	//不需look_up时
				return 1 ; 	//仍需look_up时
		lookup_slow()
			__lookup_hash()
				lookup_dcache()
					d_lookup()
					d_alloc()
				lookup_real()
			path->mnt = nd->path.mnt
			path->dentry = dentry
			follow_managed()
		path_to_nameidate(path,nd)	//根据新path设置nameidata
			nd->path.mnt = path->mnt
		nd->inode = inode

这段逻辑使用上下文nameidata对象作为PathWalk过程中局部的全局变量,实现递归的目录搜索。

Linux VFS I

为了实现VFS的设计目的 – 抽象出文件系统的共性,作为抽象,VFS不但打通了上下的通道,还打通了文件系统之间的通道,就像当下流行的”云”,将各种设备(文件系统)和系统联系到一起。在VFS中,有6个关键类:inode,dentry,file,super_block,vfs_mount和file_system_type,整个VFS”大厦”的建造都是围绕这6个”支柱”的。

这几个数据结构的实现都**“include/linux/fs.h”**中,下面这张图简要的描述了本文介绍这几个对象及其关系

super_block

–1326–>s_blocksize_bits;当块大于256byte时,块大小是2的多少次幂,比如块大小是512时,就是9
–1327–>s_blocksize;块的大小,这两个域参见sb_set_blocksize()
–1328–>file_system_type对象指针,该super_block对象表示的具体的文件系统类型,内核使用指针链表管理所有的file_system_type对象,其中有将一个mount一个文件系统回调接口
–1330–>和inode,file,dentry等一样, super_block”类”也封装了自己的操作方法集
–1334–>这个文件系统挂载到根目录时的flag,比如MS_RDONLY表示只读挂载etc。同样定义在fs.h
–1336–>不同文件系统的魔幻数,比如ramfs的RAMFS_MAGIC,ext4的EXT4_SUPER_MAGIC,定义在“include/linux/magic.h”
–1337–>文件系统的根目录,即mount一个目录到目录树时,该文件系统的挂载点在目录树的dentry对象
–1348–>使用NFS时的导出dentry
–1350–>文件系统的block_device对象指针
–1351–>文件系统的backing_dev_info对象指针
–1352–>MTD设备的。。。
–1362–>文件系统私有数据
–1380–>
–1427–>文件系统stack的深度
–1431–>该super_block管理的所有的inode对象链表
–1434–>该super_block管理的所有的回写inode对象链表

实际磁盘的文件都是由文件系统管理的,文件系统挂载到VFS上之后,内核想要从磁盘上获取这个文件,就要按照事前的约定,从磁盘头读取相应文件系统的信息,比如类型,分区,校验码等,叫做文件系统的super block信息,可以看作是整个文件系统的元数据的容器,只有读取到super block,内核才能正确的进行接下来的操作。对于ext4文件系统,super block按照内核struct ext4_super_block的格式存储在相应分区,内核使用struct ext4_super_block描述该super block信息并进一步将其封装到VFS super_block中。

inode

Continue reading

Linux Block IO V

Block IO 层的请求完成在整个IO完成的路径上紧接SCSI CMD完成之后,相应的回调函数在biorequest以及request_queue初始化时被注册。


blk_done_softirq()
	rq->q->softirq_done_fn(rq);     //scsi_softirq_done()
		case SUCCESS:
		scsi_finish_command()	
			scsi_end_request()
				blk_update_request()
					req_bio_endio()
						bio_endio()
							bio->bi_end_io()	//submit_bio_wait_endio etc
				blk_finish_request()
					req->end_io()   		//发自SCSI层的命令会有这个回调:blk_end_sync_rq()

Linux Block IO IV

内核使用大量的缓存、异步、优化机制来提高IO性能,这一点Block IO子系统也不例外。以最常见的buffered IO为例,所有需要写入磁盘的数据起初都是存在Page Cache中,由文件系统来管理,显然,这样的IO是基于task_struct的,在当前版本中,内核使用task_struct->buffer_head来管理task_struct提交的IO请求。然后,借助write_back机制,在合适的时机将存储了task_struct IO数据的脏页下刷到磁盘,即write_back线程调用Block IO子系统提供的submit_bio()接口。然而,这样的bio也不是直接转换为CDB直接落盘,Block IO子系统也有自己的异步、优化机制,这就是本文要讨论的重点,具体的,IO路径中Block层路段有以下几个重要的话题:

  1. pluging /unpluging 机制
  2. IO Scheduler的优化策略
  3. Block层与SCSI层衔接

pluging/unpluging机制使通用块层的request批量下发到Blk-core层,并进一步下发到底层设备。这个机制说起来也简单,FS下发的bio描述了一个IO的源头与目的地,Block层想要对其进行优化,上层提交一次request就发送一次CDB显然是不行的。而要优化,无非两种前提:池(缓存)使用空间为优化提供机会,异步使用时间为优化提供机会。这里,数据已经在内核空间的主存中,再缓存一次显然是浪费资源,所以,为了优化,Block层使用了异步机制为优化创造条件,也就是pluging/unpluging机制。

具体地,每个设备都有自己的水位线:BLK_MAX_REQUEST_COUNT,表示该设备一次性可以处理的request数量,为了最大限度的提高硬件性能,同时为IO调度器提供优化的机会,绝大多数意欲下发到底层设备的request(IO barrier request除外)都会先进入到task_struct->plug->list缓存起来,待request数量足够的时候,一次性蓄在其中的request加入到elv中优化,再转变为CDB下发到设备,而这掌控蓄放的塞子plug,就由下发线程负责,每下发一个request,都会检查是否达到了警戒水位,如此,便实现了异步下发。对下发的bio/request来说,核心函数是blk_queue_bio().

Continue reading

Linux Page IO

page IO,顾名思义,一端连接着内存,一端连接着IO系统,可以看作内存子系统和IO子系统的中间层,部分资料把这部分划归到Block层, 但我觉得虽然这部分上和IO强相关, 但同时又涉及到很多内存页的数据结构, 所以还是单独划归到一层比较好. 通常,对一个文件的回写IO数据首先通过文件系统写入到Page Cache中,之后,就通过Page IO层,以异步的方式下发到Block IO子系统。当然,文件系统的数据也可以直接写入到Block IO子系统(Direct IO)。

Page IO层的核心工作就是构造并管理bio, bio作为IO的基本单位,描述了IO从内存到磁盘的映射,bio的构造借助了内存管理中的buffer_head结构完成其构造。 buffer_head负责page到扇区的固定映射,在此基础上,bio只需了解IO的内存端,即可计算出它的磁盘端位置

在IO路径中,构造bio的代码流程如下:

Continue reading

Linux Block IO III

Block IO中关键对象通常在发现存储设备的时候已经构造好,其中,最关键的是gendisk及其关联request_queue的构造,二者的构造同样遵循**“分配->初始化->注册”**的流程。由于设备对象的初始化是从软件栈的底层到上层的, 即初始阶段Block层只是准备好相关的代码,供更底层的SCSI子系统或IDE子系统来”调用”,完成Block层相关对象的构造。

以SCSI磁盘驱动为例,其在SCSI LLDD的扫描并构造设备对象时,已经完成了request_queue中相应接口的注册,供Block层使用:

scsi_probe_add_add_lun()
	scsi_alloc_sdev()
		sdev->request_queue = scsi_alloc_queue(sdev)
			__scsi_alloc_queue(sdev->host, scsi_request_fn);
				blk_init_queue(request_fn, NULL)
					blk_init_queue_node()
						blk_init_allocated_queue()
							q->request_fn = rfn;		//scsi_request_fn
							blk_queue_make_request(q, blk_queue_bio)
								 q->make_request_fn = mfn;	//blk_queue_bio
			blk_queue_prep_rq(q, scsi_prep_fn);
				q->prep_rq_fn = pfn						//scsi_prep_fn
			blk_queue_unprep_rq(q, scsi_unprep_fn);
				q->softirq_done_fn = fn					//scsi_unprep_fn
			blk_queue_softirq_done(q, scsi_softirq_done);
				q->softirq_done_fn = fn
			blk_queue_rq_timed_out(q, scsi_times_out);
				q->rq_timed_out_fn = fn					//scsi_times_out
			blk_queue_lld_busy(q, scsi_lld_busy);
				q->lld_busy_fn = fn						//scsi_lld_busy

当位于SCSI HLDD的sd驱动匹配到已经注册到内核的SCSI磁盘对象时,即开始在内核中构造相应的对象,而gendisk等Block层中的对象是在其”同步”阶段分配以及缺省初始化,并在 “异步”阶段初始化并注册的,。


scsi_alloc_sdev()
	 sdev->request_queue = scsi_alloc_queue(sdev);

同步阶段


sd_probe()
	gd = alloc_disk(SD_MINORS)	//分配gendisk对象
		alloc_disk_node(minors, NUMA_NO_NODE)
			kzalloc_node()
			init_part_stats()
			disk_expand_part_tbl()
			hd_ref_init()
			rand_initialize_disk()
			disk_to_dev(disk)->class = &block_class	
			disk_to_dev(disk)->type = &disk_type
			device_initialize(disk_to_dev(disk))

异步阶段


sd_probe_async()
	init sdp sdkp
	gendisk gd=sdkp->disk
	gd->major = sd_major((index & 0xf0) >> 4);
	gd->first_minor = ((index & 0xf) << 4) | (index & 0xfff00);
	gd->minors = SD_MINORS;
	gd->fops = &sd_fops;						//注册gendisk对象的操作方法集
	gd->private_data = &sdkp->driver;
	gd->queue = sdkp->device->request_queue;	//gendisk使用LLDD已经准备好的request_queue
	add_disk(gd)								//注册gendisk对象到内核
		bdi_register_dev()
		blk_register_region()
		register_disk()
		blk_register_queue()
		disk_add_events()
		blk_integrity_add()
	sd_revalidate_disk(gd)
		sd_spinup_disk()            			//转动磁盘
			scsi_execute_req()
		sd_readcapacity()
		set_capacity(disk)

至此,在Block层上使用一个磁盘的工作就准备就绪了

Linux Block IO II

本文主要讨论Block IO子系统核心类。下图是Block子系统软件栈示意图,和很多子系统(驱动尤甚)一样,Block由一个承上启下的core层和分布于其周围的诸多模块组成,通常来讲,Block子系统可以被分为3层:Generic Block Layer、Block core、Block Device Driver。


Generic Block Layer主要是提供对设备(gendisk)的抽象,在提交一个请求到Core之前,显然要知道这个请求是提交给谁的,这个谁可以通过文件的inode获取,是构造请求(bio)的必需步骤。一个Block Device在注册到内核的时候需要注册相应的gendisk到Generic Block Layer
Block Core对上要接收上层提交的bio,通过plug机制以及IO调度算法,对请求进行合并和排序,再派发到底层驱动
Block Device Driver主要是一些块设备驱动。
此外,IO路径的所有逻辑都是为IO服务的,而bio和request作为承载IO请求的直接类,request_queue作为各个层操作IO请求的入口,它们的重要性不言而喻,对于这几个家伙,有很多种形象的比喻,如果每一层IO路径上的每一层逻辑是一个工位,那么它们就是流水线;如果每一层逻辑是一个山楂球,它们就是冰糖葫芦杆…

gendisk

通用块层提供了对设备请求的抽象,系统中的任何BlockDevice在注册的时候都要分配、初始化、注册一个gendisk对象及其必要数据结构到内核。该层主要由以下的对象组成gendisk、hd_struct,其中gendisk是整个通用块层的核心类,围绕着gendisk,通用块层的主要对象的关系如下图所示:

gendisk对象作为对块设备的抽象,用于描述整块磁盘、整个MMC芯片等,这种设计可以很好的体现OOP中的”多态”,gendisk本身封装了块设备的”共性”部分,而对于”个性”的部分,使用Kernel中的常见伎俩——private_data来解决。

对于共性的部分,块设备常用的”分区”的管理对象hd_structdisk_part_tbl必然封装在gendisk中。具体地,在gendisk眼中,如果一个块设备没有分区,那么就只有一个0号分区,该分区由gendisk直接内嵌的hd_struct描述,如果一个块设备有了分区,那么就用disk_part_tbl描述其分区表,该分区表的第一项仍旧是gendisk的0号分区。gendisk通过0号分区hd_struct的device接入sysfs,同理,非0号分区也通过相应的hd_struct接入sysfs
对于个性的部分,对于scsi磁盘,private_data指向scsi_disk->scsi_driver(driver/scsi/sd.c +2904),对于RAID,指向struct mddev(drivers/md/md.c +4850),对于Device Mapper,private_data指向struct mapped_device(drivers/md/dm.c +2194)。此外,fops同样是”多态”,视情况被赋值为sd_fops(drivers/scsi/sd.c +2903)、lsi_fops(drivers/scsi/megaraid_mm.c +85)等

关于gendisk域的更详细解释,参见下表。

Continue reading

Linux Block IO I

块IO子系统上承文件系统,下启SCSI等具体的存储设备子系统,对下层的诸多设备进行统一的抽象,以向上提供统一的块存储视图,同时,也使得deviceMapper,RAID等模块的设计变得容易。在内核IO路径中,块IO子系统到交通枢纽的作用,其在内核中的相对位置如下

对上,Block子系统位于文件系统层的下方,通过bdev伪文件系统管理系统中的所有磁盘抽象,使得其他文件系统等访问接口可以找到一个磁盘的抽象

对下,为具体的存储设备提供通用的服务,包括磁盘和分区抽象、IO请求优化、重映射等。

就块设备本身来说,可以分为三层

  1. 通用块层位于最上,对存储设备的设备和分区进行文件系统可用的抽象
  2. IO调度层位于中间,负责对上层下发的IO的合并优化等工作,提供NOOP,CFQ,DeadLine,Anticipatory 4种IO调度器
  3. 块设备驱动层,将通用块设备作为操作对象的”驱动”,MultiDisk子系统就是工作在这一层。

在内核源码中,块IO子系统的文件主要分布在block/目录下,相关文件的简介如下:

filedescription
include/linux/genhd.h通用块层,封装了gendisk、hd_struct等对象,对所有的设备进行统一的抽象,io下发必须经过这一层,在设备初始化的时候被构造进内核
block/genhd.cregister_blkdev
include/linux/blk_types.hbio定义和相关宏
include/linux/blkdev.hrequest、request_queue及其在block设备上的操作方法
block/blk-core.cblkdev.h ->blk-core.c
include/linux/fs.hinode,file,super_block,file_operations以及block_device的定义
fs/block_dev.c块设备和文件系统的接口部分,eg,bdev文件系统
block/partition-generic.c分区partition的相关操作
block/blk-merge.c和include/linux/elevator.h block/elevator.c一同构成了通用块层到块核心层的边界
blk-sysfs.c封装了块设备在sysfs中输出的信息
blk-setting.c封装了对块设备进行设置(队列深度,DMA地址)的方法
block/bio.h、block/bio.cbio操作函数
include/linux/blk-mq.h、block/blk-mq.c与MultiDisk子系统相关的操作
block/blk-lib.c封装了一下helper类的函数
block/blk-flush.c封装了下刷request相关函数

Linux SCSI 子系统 V

不论请求来自Block层还是SCSI层,当请求完成时的入口只有一个:SCSI设备上报到内核的中断处理函数,请求完成逐级向上传递,直到应用层。和很多的request-response模型一样,IO请求的完成分为以下3类4种:

  1. 请求完成+请求成功
  2. 请求完成+请求失败+重试
  3. 请求完成+请求失败+错误处理
  4. 请求响应超时

Init

以megasas的PCIe RAID卡为例,其在SCSI子系统中的请求完成的初始化如下,

准备硬件中断handler和tasklet结构到scsi_host_template:

static struct megasas_instance_template megasas_instance_template_gen2 = {
  .service_isr = megasas_isr,     
  .tasklet = megasas_complete_cmd_dpc,
};

注册工作队列和硬件中断handler,当磁盘完成SCSI请求时会上报该中断

megasas_probe_one()
	INIT_WORK(&instance->work_init, process_fw_state_change_wq);
	megasas_init_fw()
		tasklet_init(&instance->isr_tasklet, instance->instancet->tasklet);
	request_irq(service_isr)

系统还为Block层的request的完成注册了softirq:

blk_softirq_init()
	INIT_LIST_HEAD(&per_cpu(blk_cpu_done, i));
	open_softirq(BLOCK_SOFTIRQ, blk_done_softirq);
	register_hotcpu_notifier(&blk_cpu_notifier);

做好了准备工作,开始讨论请求完成的这三种情况

Complete

当磁盘完成SCSI请求时会上报中断,内核最终会执行注册的handler,请求完成的传递路径如下所示,经由**硬件中断->work_struct + tasklet->软件中断-(->完成量)**逐层传递。

megasas_isr()
	megasas_deplete_reply_queue()
		some work in top half
		schedule_work(&instance->work_init)
		tasklet_schedule(&instance->isr_tasklet)

系统在合适的时机调度到该tasklet,其流程如下:

megasas_complete_cmd_dpc()
	megasas_complete_cmd()
		cmd->scmd->result =					//设置result,在blk_done_softirq()中需要读取执行结果
		cmd->scmd->scsi_done(cmd->scmd);	//scsi_request_fn()中构造scsi_cmnd时注册为scsi_done()
		blk_complete_request()
			__blk_complete_request()
				raise_softirq_irqoff(BLOCK_SOFTIRQ)

Success

作为该softirq的handler的blk_done_softirq()的流程如下:

blk_done_softirq()
    rq->q->softirq_done_fn(rq);     //scsi_softirq_done()
    	disposition = scsi_decide_disposition(cmd)
    		host_byte(scmd->result)			//读取result
    	case SUCCESS:
        scsi_finish_command()
            scsi_cmd_to_driver()
            drv->done(cmd)          //sd_done()
            	sd_dif_complete()	//回收bio内存
            scsi_io_completion()    //Completion processing for block device I/O requests
            scsi_end_request()
                blk_update_request()
              		req_bio_endio()
                blk_finish_request()
                    req->end_io()   		//blk_end_sync_rq()
                        complete(waiting)	//唤醒队列中发自SCSI层的命令,发自Block层的命令不需要
          		scsi_release_buffers(cmd);
          			scsi_free_sgtable()		//回收SG数据
          		scsi_put_command(cmd);
                scsi_run_queue()
            __scsi_queue_insert()

Failed – retry


blk_done_softirq()
    rq->q->softirq_done_fn(rq);     //scsi_softirq_done()
        disposition = scsi_decide_disposition(cmd)
    		host_byte(scmd->result)			//读取result
    	case NEEDS_RETRY:
    	case ADD_TO_MLQUEUE:
    		scsi_queue_insert()
    			__scsi_queue_insert()
    			blk_requeue_request(q, cmd->request)	//进入Block层
    				blk_delete_timer(rq)
    				blk_clear_rq_complete(rq)
    				elv_requeue_request(q, rq)
    			kblockd_schedule_work(&device->requeue_work)
    				queue_work(kblockd_workqueue, work)

Failed – eh


scsi_host_alloc()    
	shost->ehandler = kthread_run(scsi_error_handler, shost);
blk_done_softirq()
    rq->q->softirq_done_fn(rq);     //scsi_softirq_done()
        disposition = scsi_decide_disposition(cmd)
    		host_byte(scmd->result)			//读取result
    	default:
        	scsi_eh_scmd_add()
        		scsi_host_set_state()
        		list_add_tail(&scmd->eh_entry, &shost->eh_cmd_q);
        		scsi_eh_wakeup(shost)
        			wakeup(shost->ehandler)
        	scsi_finish_command()
scsi_error_handler()
	while(true)
	shost->transportt->eh_strategy_handler(shost);
	scsi_unjam_host(shost);
		scsi_eh_get_sense()
			list_for_each_entry_safe()
			scsi_request_sense(scmd)
				scsi_send_eh_cmnd()
					scsi_eh_prep_cmnd()
					scmd->scsi_done = scsi_eh_done
					shost->hostt->queuecommand(shost, scmd)
					scsi_eh_restore_cmnd(scmd, &ses)
					wait_for_completion_timeout(&done, timeout)
					scsi_eh_completed_normally(scmd)
					scsi_eh_restore_cmnd(scmd, &ses)
			scsi_decide_disposition(scmd)
			scsi_eh_finish_cmd(scmd, done_q)
				list_move_tail(&scmd->eh_entry, done_q)
		scsi_eh_abort_cmds(&eh_work_q, &eh_done_q))
		scsi_eh_ready_devs(shost, &eh_work_q, &eh_done_q);
		scsi_eh_flush_done_q(&eh_done_q);

可以看到,该中断处理函数的工作,需要借助于request_queue中已经注册好回调函数,比如在SCSI子系统中注册的scsi_softirq_done()与sd_done(),此外,参照前文,对于发自SCSI子系统的SCSI命令,其发送线程都会等待完成量waiting的完成,这里,在request的回调函数blk_end_sync_rq()中,该完成量被完成,其线程可以被唤醒,相比之下,发自Block层的SCSI命令就不会等待这个完成量

Timeout


static struct scsi_host_template megasas_template = {
	.eh_timed_out = megasas_reset_timer
}
megasas_reset_timer()	
	instance->host->can_queue = instance->throttlequeuedepth;
	instance->last_time = jiffies;
	instance->flag |= MEGASAS_FW_BUSY;

Linux SCSI 子系统 IV

当上层业务需要和磁盘交互时,包括读写请求,以及设备对象初始化时获取磁盘信息,这些都需要将请求转化为SCSI磁盘可以识别的SCSI命令下发到磁盘,这里就涉及到了SCSI命令的转化和执行。
SCSI命令的执行可以分为两种情况:发自SCSI和发自Block,前者多指在SCSI设备对象初始化过程中,比如SCSI子系统需要转动磁盘、查询磁盘信息等,后者多指源自高层经由Block层下发到SCSI子系统读写命令。本文从这两个角度阐述。

执行发自SCSI的命令

如果命令发自SCSI层,则通过scsi_execute_req()发出,下面是执行scsi_execute_req的调用关系,使用这个接口下发的命令,会被封装到一个request中插入Block层中request_queue中,通过Block层的处理逻辑择时下发,这种设计是一个低层代码调用高层代码例子。


scsi_execute_req()
    scsi_execute_req_flags()
        scsi_execute()
            req = blk_get_request(sdev->request_queue); //从设备的request_queue获取request
            blk_execute_rq()    			//insert a request into queue for execution
                blk_execute_rq_nowait(blk_end_sync_rq)  //SCSI调用Block函数,注册blk_end_sync_rq()函数
                    rq->end_io = done;      		//即blk_end_sync_rq()
                    __elv_add_request() 
                    __blk_run_queue()
                wait_for_completion_io()		//通过完成量等待IO结束,发自SCSI层的SCSI命令独有

执行发自Block的命令

发自Block层的SCSI命令多是读写请求,即Block层通过回调SCSI HLDD的scsi_request_fn()等接口,将Block层的request转化为scsi_cmnd,再通过回调queuecommand()接口下发到SCSI LLDD。然而,无论是Block还是Net等,内核中的IO执行的框架均大体相同,都可看作request-response结构,而实现这种框架,需要三部分工作:

  1. 准备完成回调,并注册之。完成回调根据返回结果将处理发送的消息,常见的有释放承载请求的buffer,相关标志置位,继续向上层通知处理结果等。
  2. 发起request。
  3. 低层执行request并根据执行结果上报response。

这一点,SCSI子系统也不无例外。

为了执行来自Block层的IO请求,SCSI子系统在构造相关对象的时候就必须要注册包括但不限于上述handler的回调接口。下面是SCSI总线扫描过程中的核心函数,可以看出,在构造scsi_device对象之时,便已经将关键的函数注册好,其中,request_queue中两个重要的回调接口:request_fn和softirq_done_fn分别在注册为scsi_request_queue和scsi_softirq_done,前者在执行request时的回调接口,后者是收到response时的回调接口。

Continue reading