上海网站设计首选刻,汕头网站推广seo,wordpress默认主题下载,微网站制作方案1.分页#xff0c;页表
linux启动阶段#xff0c;最初运行于实模式#xff0c;此阶段利用段寄存器#xff0c;段内偏移#xff0c;计算得到物理地址直接访问物理内存。 内核启动后期会切换到保护模式#xff0c;此阶段会开启分页机制。一旦开启分页机制后#xff0c;内…1.分页页表
linux启动阶段最初运行于实模式此阶段利用段寄存器段内偏移计算得到物理地址直接访问物理内存。 内核启动后期会切换到保护模式此阶段会开启分页机制。一旦开启分页机制后内核采用的是线性地址线性地址通过页表转换得到物理地址再通过物理地址访问物理内存。
采用分页机制的意义在于可以为每个进程提供一个独立的页表这样每个进程将拥有一个独立的线性地址区域。通过页表在两个进程里使用同一个线性地址由于页表的作用可能分别映射到两个不同的物理地址。这样可使得每个进程可独立管理其线性地址空间的使用彼此不干扰。分页的另一个好处是通过页表我们可以将一片连续的线性地址区域映射到若干个不连续的物理地址区域。
值得注意的是每个进程的线性地址空间会划分成用户态线性地址空间内核态线性地址空间。 用户态线性地址空间可供用户态进程自主管理和使用。 内核态线性地址空间在该进程需要切换到内核态遭遇中断系统调用异常时使用。值得注意的是对内核态线性地址空间对系统所有进程是共享的。共享的意思是对系统任一一个进程给定一个属于内核态空间的线性地址该线性地址均对应到同一个物理地址。
2.内核态线性地址空间划分
我们分别讨论经典32位内核64位内核下内核态线性地址空间划分。 上图是线性地址空间的整体视图无论在32位还是64位系统下线性地址空间均划分为用户态内核态两个部分。
2.1.32位内核下内核态线性地址空间划分 值得注意的是32位下直接映射区域尺寸一般是896MB。 2.2.64位内核下内核态线性地址空间划分 值得注意的是64位下直接映射区域一般尺寸可达64T没有持久映射固定映射。
2.3.针对直接映射区域的处理 (1). 在系统启动阶段对直接映射区域内所有线性地址会设置好页表。 (2). 直接映射区域会映射到物理地址空间起始部分。
上述处理的意义在于对于直接映射区域内的线性地址其线性地址和物理地址的关系是固定的。 假设此区域内某个线性地址vaddr。其物理地址固定为vaddr - __PAGE_OFFSET。 由于启动阶段已经为此区域的所有线性地址设置好了页表所以后续通过伙伴系统分配得到此区域的页框后无需执行页表注册。即可得到对应的线性地址使用线性地址访问内存。
2.4.针对持久映射区域的处理 (1). 在系统启动阶段对持久映射区域会在多级页表中分别设置好线性地址对应的顶级页表项上级页表项中间页表项。这样后续使用分配页框并为其映射到持久映射区域时只需单独准备页表并设置页表项即可完成页表映射。
内核通过设置一个哈希表保存映射到此区域的每个page对象及其线性地址。 对某个页框建立持久映射过程可能会阻塞。阻塞一般发生在持久映射区域暂时无空闲区域可供使用时。
2.5.针对固定映射区域的处理 (1).在系统启动阶段对持久映射区域会在多级页表中分别设置好线性地址对应的顶级页表项上级页表项中间页表项。这样后续使用分配页框并为其映射到持久映射区域时只需单独准备页表并设置页表项即可完成页表映射。 此区域为每个cpu准备了一个窗口一个窗口可包含固定数量的页。这样每个cpu需要对页框执行固定映射时总是可以在自身窗口内寻找一个区域建立映射。
固定映射的分配保证是不阻塞的分配时不会检测指定的线性区域是否已被使用。 一般只用于临时性为页框建立映射如中断处理中使用后立即撤销映射的场景。
3.利用伙伴系统分配页框释放页框
3.1.大的背景 从大的层次可以将内核所管理的内存区域抽象为节点每个节点下的内存区域又可被划分为不同类型的区域。 现代NUMA系统通过多节点每个节点内封装指定数量的内存处理器来提高并行能力。不支持NUMA的系统视为拥有一个节点即可。 每个节点下的内存区域划分为不同类型是因为由于历史原因某些硬件使用DMA技术只能使用物理地址范围前16M的物理内存。32位系统下直接映射区域和非直接映射区域由于处理方式不同也需分为不同类型。这样典型的32位系统区域一般由DMANORMALHIGH三种类型。
我们利用伙伴系统进程页框分配时首先的指定要在那个节点的那个区域进行分配。 这样伙伴系统先在此节点此区域下进行分配处理。若无法完成分配通过设置我们也可继续在备选区域尝试分配。直到分配成功或最终失败。
3.2.伙伴系统的结构
struct free_area {struct list_head free_list;unsigned long nr_free;
};struct zone {unsigned long free_pages;spinlock_t lock;struct free_area free_area[MAX_ORDER];struct pglist_data *zone_pgdat;struct page *zone_mem_map;unsigned long zone_start_pfn;unsigned long spanned_pages; /* total size, including holes */unsigned long present_pages; /* amount of memory (excluding holes) */char *name;
} ____cacheline_maxaligned_in_smp;struct page {page_flags_t flags; /* Atomic flags, some possibly updated asynchronously */atomic_t _count; /* Usage count, see below. */unsigned long private; /* Mapping-private opaque data:* usually used for buffer_heads if PagePrivate set;* used for swp_entry_t if PageSwapCache* When page is free, this indicates order in the buddy system. */struct list_head lru; /* Pageout list, eg. active_list protected by zone-lru_lock! */
#if defined(WANT_PAGE_VIRTUAL)void *virtual; /* Kernel virtual address (NULL if not kmapped, ie. highmem) */
#endif /* WANT_PAGE_VIRTUAL */
};伙伴系统分配页框是在指定类型区域里分配。页框是此区域内的页框。 为了保证频繁的页框分配和释放后依然有较大的连续物理区域可用伙伴系统对区域内空间的页框按阶管理。
3.3.伙伴系统页框分配示例 假设我们在一个拥有8个空闲页框的区域使用伙伴系统。 假设伙伴系统使用MAX_ORDER4进行页框管理。 假设区域内首个页框的物理地址换算得到的页框编号可被8整除。 假设初始时刻zone对象的free_area[0]free_area[1]free_area[2]代表的链表均为空。free_area[3]代表的链表有一个元素此元素指向代表1页框的page对象。
对1页框的page对象在伙伴系统管理下其flags将包含SLAB标记其_count将为-1因为此page是free_area链表中的元素所以其flags还将包含PRIVATE标记其private将为所在链表的阶这里是3。 其余各个页框对应的page对象虽在伙伴系统管理下但不是free_area链表的元素所以其flags将包含SLAB标记其_count将为-1。
3.3.1.向伙伴系统申请2个空闲页框 向伙伴系统申请页框时只能申请 2 o r d e r 2^{order} 2order个页框。对2个页框order为1。 伙伴系统的处理策略是对free_area数组从order开始依次判断数组元素代表的链表是否存在空闲元素。 若存在假设对应元素的索引为cur_order。 我们要做的是 (1). 从链表移除首元素。此元素是一个page指针这个指针会作为结果返回。表示从此page开始连续 2 o r d e r 2^{order} 2order个page均已经被分配。 (2). 若cur_orderorder意味着此page代表了一个连续尺寸为 2 c u r o r d e r 2^cur_order 2curorder的空闲物理区域。对多余部分我们将按对半切分策略依次将多余部分加入free_area对应阶数的链表。并相应更新各个字段。 这样处理后free_area[3]对应的链表为空。free_area[2]对应的链表包含一个元素即页框5对应的page。free_area[1]对应的链表包含一个元素即页框3对应的page。
对页框1由于其不再是对应阶的列表元素了其page的flags将不再包含PRIVATE标记其private被设置为0。 对页框1页框2从伙伴系统返回给外部时会设置每个page的private为0_count为0。
对页框3由于其加入了free_area[1]所在链表所以所以其flags还将包含PRIVATE标记其private将为所在链表的阶这里是1。 对页框5由于其加入了free_area[2]所在链表所以所以其flags还将包含PRIVATE标记其private将为所在链表的阶这里是2。 伙伴系统对free_area[n]链表内每个元素的要求是此page在区域内索引可被 2 o r d e r 2^order 2order整除。 page在区域内索引page-区域内首个page。指针相减得到的是指针间距离
3.3.2.向伙伴系统释放2个页框 释放页框时需要提供起始页框的page指针order。order表示从page开始连续 2 o r d e r 2^order 2order个页框需要释放。 释放过程先递减起始页框page的_count当其_count递减后变为-1时实际执行释放流程。
阶为order的连续页框释放需要经过一个与伙伴合并构成更大阶的过程。 直到无法找到伙伴时才结束。 该过程会将被合并的伙伴从其原来所在阶的链表中移除并最终在合并后阶的链表里加入合并后阶的首个page。 对由于合并而不再位于链表的page会令其flags将不再包含PRIVATE标记其private被设置为0。 对最终合并阶的首个page会令其flags包含PRIVATE标记其private被设置为最终的阶。
合并的依据是对于阶为order的链表里每个page要求此page-区域起始page后得到的索引可被 2 o r d e r 2^order 2order整除。 关键是对阶为order的page确定其伙伴的位置。
上述是确定阶为order的page_idx的伙伴的方法。 上述方法的正确性 (1). 首先我们知道由于一致性要求page_idx必然可被 2 o r d e r 2^order 2order整除。 (2). 再次我们对page_idx它的伙伴有两个。一个是起始page的区域内索引位page_idx$2^order$阶为order的page代表的区域。一个是起始page的区域内索引为page_idx-$2^order$阶为order的page代表的一个区域。 (3). 但我们选取伙伴的目的是为了合并且对于合并后区域的起始page要求该page的区域内索引需能被 2 o r d e r 1 2^{order1} 2order1整除。 (4). 由于(3)的限制我们只能选择
buddy_idx (page_idx ^ (1 order));作为合并的伙伴。
若选取的伙伴符合要求即对应的page位于伙伴系统阶为order的链表。通过page的PRIVATE标志与private可判断 则我们需与此伙伴合并得到阶为order1的新的连续空闲区域。新区域首个page的区域内索引为
page_idx buddy_idx;释放页框经过合并处理后free_area[1]free_area[2]链表将为空。 free_area[3]将包含单个元素为页框1的page。
3.4.提升伙伴系统性能 linux在伙伴系统使用者和伙伴系统之间额外引入一个中间层。
struct page {struct list_head lru; /* Pageout list, eg. active_list protected by zone-lru_lock! */
};struct per_cpu_pages {int count; /* number of pages in the list */int low; /* low watermark, refill needed */int high; /* high watermark, emptying needed */int batch; /* chunk size for buddy add/remove */struct list_head list; /* the list of pages */
};struct per_cpu_pageset {struct per_cpu_pages pcp[2]; /* 0: hot. 1: cold */
} ____cacheline_aligned_in_smp;struct zone {struct per_cpu_pageset pageset[NR_CPUS];char *name;
} ____cacheline_maxaligned_in_smp;每次向伙伴系统申请阶为0的空闲页框时先向中间层申请。中间层无法完成申请时再向伙伴系统申请。 区域对象为每个cpu准备了一个per_cpu_pageset对象此对象针对每个cpu支持两类列表一类列表存储热页集合一类列表存储冷页集合。page对象的lru可用于构建链表。
3.4.1.申请单独页框的逻辑 依据当前cpu及申请标志取得区域相应per_cpu_pageset 的相应per_cpu_pages 对象。 若链表现有元素不足low时一次向伙伴系统申请batch个单独页框来补充。 若链表存在可用元素取首个元素。将其移除链表。对应的page作为结果返回。 对返回的page其_count将为0其private被设置为0。
3.4.2.释放单独页框的逻辑 页框的page结合其flags字段可以得到此页所属区域对象的指针。 释放的页框需要满足page的_count为-1。 依据当前cpu及申请标志取得区域相应per_cpu_pageset 的相应per_cpu_pages 对象。 若链表现有元素已经达到high一次向伙伴系统释放batch个单独页框。 将释放的page加入到per_cpu_pages的链表结构即可完成释放。
3.5.页框管理过程一些一致性要求 a. 位于伙伴系统冷热列表的页框的page的_count均为-1。 b. 页框被分配出去初始时刻各个页框的page的_count均为0。 c. 位于伙伴系统各个阶的列表的page其flags中需要包含PRIVATE其private需要设置为所在的阶。 d. 位于伙伴系统各个阶的列表的page其在区域内索引需要可被 2 o r d e r 2^order 2order整除。 e. 伙伴系统内不在各个阶的列表的page及冷热热页列表的page其flags不应包含PRIVATE其private应该为0。
3.6.伙伴系统存在必要性 伙伴系统用于实现内核页框分配器。 内核线性区域的绝大部分都是直接映射的这意味着分配连续的线性区域要求对应的物理区域也得是连续的。 伙伴系统实现的页框分配可以有效保证始终存在较大的连续物理区域可供分配。
4.利用VMALLOC区域实现vmallocvfree
4.1.背景 内核线性区域的绝大部分是直接映射的但直接映射下要求连续的线性地址必须映射到连续的物理地址且直接映射的物理区域是固定的物理区域起始部分。
为了解除上述两个限制我们需要vmalloc区域。vmalloc区域的每个线性页可通过页表映射到任意的物理页。这样一方面解除了连续的线性区域需要连续的物理区域的限制另一方面也解除了物理区域必须是物理区域起始部分的限制。
4.2.结构
struct vm_struct {void *addr;// 起始线性地址unsigned long size;// 区域尺寸unsigned long flags;// 标志。VM_ALLOCVM_MAPVM_IOREMAPstruct page **pages;// 页面集合unsigned int nr_pages;// 数量unsigned long phys_addr;// ioremap时需要struct vm_struct *next;
};我们只考虑VM_ALLOC下的使用。 4.3.vmalloc 利用vmalloc从vmalloc区域的指定区间申请一个尺寸为size的可用区域并完成页表注册的步骤如下 (1). 首先vmalloc分配尺寸以页框为单位所以对size会按页框取整。 (2). 由于内核会将VMALLOC区域所有已经分配出去的区域加入一个单向链表结构。对链表内每个区域内核保证区域之间无重叠部分。区域按起始地址递增有序组织。所以我们很容易可以利用此链表寻找在我们要求的区间内是否存在一个可满足要求尺寸的空间区域。 (3).若区域存在我们利用内核小块内存分配器为管理此区域的vm_struct 结构分配空间。 a. 进一步我们为此vm_struct结构内的pages数组分配空间。 b. 进一步通过伙伴系统完成指定数量页框的分配。 c. 进一步对vm_struct各个字段进行初始化设置。 d. 进一步将vm_struct结构加入内核单向链表合适位置。 e. 进一步执行页表注册以便建立线性地址和物理地址间的映射关系。页表更新后需相应的刷新TLB。 f. 用分配区域的起始线性地址作为结果返回。 (4). 若区域不存在则无法完成分配。
4.4.vfree 利用vfree向vmalloc区域释放起始线性地址为addr的一片已经分配区域。 (1). 首先内核从单向链表结构寻找匹配的区域对象。 (2). 找到时执行释放流程 a. 从单向链表移除指定vm_struct实例。 b. 对释放区域执行页表映射取消。页表更新后需相应的刷新TLB。 c. 向伙伴系统释放pages数组中的每个页框。 d. 释放vm_struct实例的pages数组的空间。 e. 释放vm_struct实例的空间。 (3). 找不到时无需释放。
5.内核中的小块内存分配器
5.1.背景 无论是伙伴系统还是vmallocvfree这些内核中的空间分配器执行空间分配和释放时对尺寸的要求均是页框的倍数。但实际上绝大部分空间分配场景要求的尺寸都小于一个页框。为了避免空间的浪费我们需要实现小块内存分配器来满足小块空间的分配需求。 5.2.结构 5.2.1.分配器结构
struct kmem_list3 {// 将服务于分配器的slab对象分成三类分别放置到三个链表struct list_head slabs_partial; // 此链表中slab内的对象部分已经分配部分可供继续分配struct list_head slabs_full; // 此链表中slab内的对象已全部分配出去struct list_head slabs_free;// 此链表中slab内的对象全部可供继续分配unsigned long free_objects;// 分配器整体的可供继续分配对象数
};// 固定尺寸空间分配器类型
struct kmem_cache_s {struct kmem_list3 lists;unsigned int objsize; // 对象尺寸unsigned int flags; // 标志信息unsigned int num; // 服务于此分配器的slab所包含的对象数量unsigned int free_limit; // 分配器内空闲对象数量限制spinlock_t spinlock;unsigned int gfporder; // 服务于此分配器的每个slab对象需要$2^gfporder$个页框unsigned int gfpflags; // 用于指示从NORMAL还是DMA区域类型获取页框size_t colour; // 颜色数 unsigned int colour_off; // 颜色偏移unsigned int colour_next; // 分配器内下个slab应该采用的颜色索引kmem_cache_t *slabp_cache; // 当服务此分配器的slab对象的管理区域需要在外部分配空间时所需采用的分配器对象指针unsigned int slab_size; // 服务于此分配器的slab对象的管理区域尺寸void (*ctor)(void *, kmem_cache_t *, unsigned long);// 允许提供构造函数对此分配器的slab下每个对象通过构造初始化void (*dtor)(void *, kmem_cache_t *, unsigned long);// 允许提供析构函数对此分配器的slab下每个对象在释放阶段析构来清理const char *name; // 分配器的名称struct list_head next; // linux内核所有分配器对象实例均位于单一链表
};5.2.2.服务于分配器的slab结构
typedef unsigned short kmem_bufctl_t;
struct slab {struct list_head list;// 用于链表组织unsigned long colouroff;// 页框空间内首个数据对象的相对于页框空间起始的偏移void *s_mem;// slab内首个对象线性地址unsigned int inuse;// slab内已分配对象数kmem_bufctl_t free;// slab内首个空闲对象索引。从0开始。
};5.2.3.linux内核的cache_cache linux内核static struct list_head cache_chain;是持有系统所有分配器对象的链表哨兵节点。 我们为了使用linux内核的小块内存分配器首先需要一个分配器用于动态分配尺寸为sizeof(kmem_cache_s)的对象这个分配器是
static kmem_cache_t cache_cache {.lists LIST3_INIT(cache_cache.lists),.batchcount 1,.limit BOOT_CPUCACHE_ENTRIES,.objsize sizeof(kmem_cache_t),.flags SLAB_NO_REAP,.spinlock SPIN_LOCK_UNLOCKED,.name kmem_cache
};该分配器对象要正常使用首先得进行正确的初始化
// 全局的固定尺寸分配器后续初始u哈
cache_cache.colour_off cache_line_size();// 缓存行大小
cache_cache.objsize ALIGN(cache_cache.objsize, cache_line_size());
// 取得slab可容纳对象数扣除管理区域数据区域后剩余部分尺寸
cache_estimate(0, cache_cache.objsize, cache_line_size(), 0, left_over, cache_cache.num);
// 可用颜色数--剩余部分/缓存行。
cache_cache.colour left_over/cache_cache.colour_off;
// 分配器下个颜色
cache_cache.colour_next 0;
// 这是将slab放在所管理页框内时候管理区域尺寸
cache_cache.slab_size ALIGN(cache_cache.num*sizeof(kmem_bufctl_t) sizeof(struct slab), cache_line_size());其中cache_estimate为
static void cache_estimate (unsigned long gfporder, size_t size, size_t align, int flags, size_t *left_over, unsigned int *num)
{int i;size_t wastage PAGE_SIZEgfporder;size_t extra 0;size_t base 0;if (!(flags CFLGS_OFF_SLAB)) {// 不含此标志表示slab管理信息放在slab管理的页框里。base sizeof(struct slab);extra sizeof(kmem_bufctl_t);}i 0;// 这是在试探一个slab内可容纳的对象数量while (i*size ALIGN(basei*extra, align) wastage)i;if (i 0)i--;// 一个slab内对象数量存在上限if (i SLAB_LIMIT)i SLAB_LIMIT;*num i;// slab内可放置的对象数量wastage - i*size;wastage - ALIGN(basei*extra, align);*left_over wastage;// 扣掉管理区域数据区域后剩余部分尺寸。
}上述过程的意思是针对此分配器对象 (1). 将其objsize设置为ALIGN(cache_cache.objsize, cache_line_size())。 这样的目的是我们可以保证此分配器对象的slab内的每个对象的起始地址无论线性地址还是物理地址均是高速缓存行对齐的。这有助于高效利用硬件高速缓存。 (2). 通过不断试探的方式试探出来在服务于此分配器的每个slab的 2 0 2^0 20个页框构成的可用空间里可容纳多少个对象。 这样试探的结果就是尽可能利用每个slab内的可用空间来放置尽可能多的对象。 分配器的slab支持将管理区域空间放在服务于自身的页框空间内或外对cache_cache我们选择将其放在所管理页框空间内。 这样针对服务此分配器的一个颜色索引为2的slab其所管理的页框空间的划分细节就是 上图是一个完整的slab所管理页框空间的划分。 a.最开始是2*colour_off 构成的颜色偏移区域。为slab引入颜色偏移机制是为了使得服务于分配器的各个slab通过不同的偏移获得更好的硬件高速缓存使用效果降低硬件高速缓存冲突的概率。 b.接下来是容纳一个slab对象实例的区域再接下来是num个kmem_bufctl_t对象构成的区域。每个slab用于slab自身的管理。num个kmem_bufctl_t对象则用于将数据区域的空闲对象组织成单向链表以便快速实现slab内对象释放对象分配逻辑。 c. 接下来是数据区域。用于存储num个此slab所管理的对象。 值得注意的是 a. 黄色部分结尾和红色部分开始可能存在间隙。 这主要由于sizeof(slab)num*sizeof(kmem_bufctl_t)不可被cache_line_size()整除。而我们又需要数据区域内每个对象起始地址可被cache_line_size()整除时的填充。 b. 红色部分结尾和页框空间尾部可能存在间隙。 这主要由于我们的页框空间尺寸 - 对齐后的管理区域 - 数据区域 - 颜色偏移区域后依然存在余量造成余量部分。 (3). 一旦完成num的设置相应的便可算出余量部分并依据余量部分计算并设置colour 也能算出slab_size 。
5.2.4.linux内核的通用尺寸分配器 linux内核提供了一组通用尺寸分配器用于尽可能覆盖到每种尺寸
#if (PAGE_SIZE 4096)CACHE(32)
#endifCACHE(64)
#if L1_CACHE_BYTES 64CACHE(96)
#endifCACHE(128)
#if L1_CACHE_BYTES 128CACHE(192)
#endifCACHE(256)CACHE(512)CACHE(1024)CACHE(2048)CACHE(4096)CACHE(8192)CACHE(16384)CACHE(32768)CACHE(65536)CACHE(131072)
#ifndef CONFIG_MMUCACHE(262144)CACHE(524288)CACHE(1048576)
#ifdef CONFIG_LARGE_ALLOCSCACHE(2097152)CACHE(4194304)CACHE(8388608)CACHE(16777216)CACHE(33554432)
#endif /* CONFIG_LARGE_ALLOCS */
#endif /* CONFIG_MMU */linux会为每个尺寸提供一个分配器用于对应尺寸的空间分配。
5.2.5.分配器初始化 一个分配器实例需要先正确初始化才能用于执行空间分配和释放。前面5.2.2里面我们介绍了linux内核cache_cache这个分配器实例的初始化过程。
更一般化的现在我们分析一个对象尺寸为cs_size希望对象满足高速缓存对齐的分配器的初始化流程。 (1). 确立分配器内对象的对齐要求 前面对于cache_cache其对齐要求为cache_line_size()即对齐硬件高速缓存行尺寸。 但考虑如果我们现在要分配的对象尺寸为32高速缓存行尺寸为128。 如果将对齐要求定位128很明显造成极大的空间浪费。 我们既希望高效的利用硬件高速缓存杜绝一个对象部分存在于高速缓存行的情况又希望尽可能的避免空间浪费。两者结合我们对尺寸cs_size我们采用如下方式确定对齐要求
ralign cache_line_size();
while (size ralign/2)ralign / 2;这样对我们的例子最终得到的对齐要求将是32。这个对齐要求下我们既保证了空间的高效使用有保证了硬件高速缓存的高效。 如我们要分配的尺寸为12高速缓存行尺寸为128则得到对齐要求将是16。依然是既可保证空间的高效使用又保证硬件高速缓存高效的最优选择。 (2). 调整对象尺寸 为了保证每个对象均满足对齐要求需调整对象尺寸为
size ALIGN(size, align);(3). 决定slab的管理区域是位于所管理页框空间的外部还是内部 策略是
if (size (PAGE_SIZE3))flags | CFLGS_OFF_SLAB;即对象尺寸达到页框/8时就应将管理区域放在外部。 当对象尺寸较小时按照用户选择的方式放置。这样考量主要是为了避免因为在内部放置了管理区域而影响内部可放的对象数量。在单个对象尺寸较大时影响造成的空间浪费也越明显。 (4). 接下来我们需要确定gfporder 即确定每个服务于此分配器的slab需要多少个页框来提供空间支持。 我们的策略依然是逐步尝试先试探gfporder为0再逐步增加直到找到一个满意的选择。 这里选择时必须满足的是 gfporder下可使得页框空间至少可容纳一个对象。 其他限制考量是 gfporder不能超过限制。 为了更好搭配伙伴系统在能容纳一个对象下gfporder几乎总是在01间选择。 当gfporder选举下余量空间不足页框空间1/8时也应选择此gfporder停止试探。 (5). 现在我们确定了以下信息 a. 此分配器下slab里所需页框数量的阶gfporder。 b. 此分配器下slab的管理区域放置在外部还是内部。 c. 此分配器下slab的页框空间可分配对象数。 d. 此分配器下slab的页框空间里对象对齐值。 e. 此分配器下slab的页框空间里颜色数。 f. 此分配器下slab的管理区域尺寸。 g. 此分配器下可分配对象的尺寸。 有了以上信息我们即可完成分配器对象的初始化。一旦外层分配器对象的初始化就可通过其分配对象空间了。
5.3.分配 5.3.1.通过分配器分配指定数量对象空间 现在我们分析外部向分配器申请数量为batchcount的对象空间的场景。 策略是从分配器对象的lists的部分空闲链表取slab节点从取得的slab节点执行对象分配。
slabp-s_mem slabp-free*cachep-objsize;// 这样可以快速得到此slab内首个空闲对象地址
slabp-inuse;
next slab_bufctl(slabp)[slabp-free];
slabp-free next;// 这样在对象分配后更新slab中首个空闲对象索引。若已经分配了batchcount个对象则结束。 若未分配到继续对链表其余slab节点执行分配处理。 对分配处理中slab节点由存在部分对象可分配变为不存在可分配对象的情况需将其从部分链表移除加入满链表。 若部分链表全部节点处理完依然未分配到指定数量继续对空闲链表每个节点执行分配处理。 分配后需要将节点从空闲链表移除移入部分链表。
当空闲链表全部处理完依然未分配到指定数量时我们需要为此分配器分配新的slab对象分配后再次尝试上述分配逻辑直到分配了直到数量对象为止。 5.3.2.为分配器分配新的slab对象 首先我们需从分配器得到此slab的颜色数计算颜色偏移。
spin_lock(cachep-spinlock);
/* Get colour for the slab, and cal the next value. */
offset cachep-colour_next;
cachep-colour_next;// 颜色的意义在于为服务于同一缓存对象的多个slab确定不同的对象起始偏移。
if (cachep-colour_next cachep-colour)cachep-colour_next 0;
offset * cachep-colour_off;// 这样得到起始对象偏移
spin_unlock(cachep-spinlock);然后我们借助伙伴系统为其分配 2 g f p o r d e r 2^gfporder 2gfporder个连续页框。对分配给slab的每个页框需在page的flags中添加SLAB标记。 然后我们需要为slab的管理区域分配空间和初始化。 针对管理区域在外部的情况需借助分配器中slabp_cache指定的分配器为管理区域分配空间。 针对管理区域在外部的情况直接在slab的页框空间内为其分配空间。 然后对slab内的每个页框对其page我们设置其lru.next指向隶属的分配器对象我们设置其lru.prev指向隶属的slab对象。 然后对slab内每个对象初始化将管理区域的空闲对象链表初始化
static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
{return (kmem_bufctl_t *)(slabp1);
}int i;
for (i 0; i cachep-num; i) {void* objp slabp-s_memcachep-objsize*i;if (cachep-ctor)cachep-ctor(objp, cachep, ctor_flags);// 缓存对象支持对每个slab内对象通过构造初始化slab_bufctl(slabp)[i] i1;// 管理区域中空闲链表初始化
}
slab_bufctl(slabp)[i-1] BUFCTL_END;// 下以空闲对象索引为BUFCTL_END时表示不存在。
slabp-free 0;// 首个空闲对象索引。最后将此slab加入隶属分配对象的对应链表结构。
这样我们便为分配器对象新分配了一个slab对象并完成了初始化。一旦完成初始化我们通过此slab执行对象分配和回收了。
5.4.释放 5.4.1.向分配器释放对象 现在我们分析外部向分配器释放数量为batchcount的对象空间的场景。
cachep-lists.free_objects nr_objects;
for (i 0; i nr_objects; i) {void *objp objpp[i];struct slab *slabp;unsigned int objnr;slabp GET_PAGE_SLAB(virt_to_page(objp));// 从对象地址找到隶属的page再找到隶属的slablist_del(slabp-list);objnr (objp - slabp-s_mem) / cachep-objsize;// 定位到对象在slab内的索引slab_bufctl(slabp)[objnr] slabp-free;// 释放的对象成为空闲链表首个元素。链表头插法。slabp-free objnr;// 首个空闲对象索引。slabp-inuse--;if (slabp-inuse 0) {// 这是释放后使得slab变为完全空闲。// 当slab因释放变为完全空闲且缓存对象里空闲对象数又很多时。if (cachep-lists.free_objects cachep-free_limit) {cachep-lists.free_objects - cachep-num;// 释放此空闲的slab对象。slab_destroy(cachep, slabp);} else {list_add(slabp-list, list3_data_ptr(cachep, objp)-slabs_free);// 否则将slab加入空闲链表}} else {list_add_tail(slabp-list, list3_data_ptr(cachep, objp)-slabs_partial);// 将slab加入部分空闲链表}
}整个过程是 首先由于slab下的页框均位于内核直接映射区域。所以易于基于对象线性地址得到对象所在页框起始线性地址由页框起始线性地址易于得到此页框的page对象为止通过page对象的lru.prev易于找到隶属的slab对象。 然后就可计算出分配对象在slab对象页框空间中的索引并更新slab的空闲对象链表。 再向slab释放对象引起其从部分可分配到空闲变化时需将其从分配器的部分空闲链表移除移入分配器的空闲链表。 若变为空闲后发现分配器内空闲对象数量过多则直接释放此slab对象即可。 5.4.2.销毁slab对象
void *addr slabp-s_mem - slabp-colouroff;
if (cachep-dtor) {int i;for (i 0; i cachep-num; i) {void* objp slabp-s_memcachep-objsize*i;(cachep-dtor)(objp, cachep, 0);// 释放时允许对每个对象执行析构来清理}
}
kmem_freepages(cachep, addr);// 先是将slab下的页框释放到伙伴系统
if (OFF_SLAB(cachep))kmem_cache_free(cachep-slabp_cache, slabp);// 若服务区域在外部需单独释放。首先对slab内每个对象执行析构。 然后向伙伴系统释放此slab的页框空间。 如果此slab的管理区域位于外部还需向对应分配器释放此部分空间。
5.5.小块内存分配器和用户的中间层 为了提升小块内存分配器的使用效率。linux中为小块内存分配器提供了两级缓存机制。 一级是cpu独占缓存一级是cpu共享缓存最底层才是内存分配器。
5.5.1.结构
struct array_cache {unsigned int avail;unsigned int limit;unsigned int batchcount;
};#define BOOT_CPUCACHE_ENTRIES 1
struct arraycache_init {struct array_cache cache;// 控制区域void * entries[BOOT_CPUCACHE_ENTRIES];// 数据区域
};struct kmem_cache_s {struct array_cache *array[NR_CPUS];struct kmem_list3 lists;
};struct kmem_list3 {struct array_cache *shared;
};上述结构里kmem_cache_s 的array用于实现每cpu缓存。 kmem_cache_s 的lists的shared用于实现cpu共享缓存。
针对每个array和shared中指向array_cache的指针指向区域先是一个array_cache实例对象再是一个对象指针数组用于缓存释放的对象和用于分配。
针对array_cache其各个字段含义如下 limit表示实例后紧跟的对象指针数组的容量。 avail表示数组最后一个有效元素索引。向指针数组释放对象总是放到avail之后从指针数组取元素总是取avail位置的。 batchcount表示当数组为空时向下级缓存一次请求填充的空闲对象数。数组满时需一次性向下级缓存释放的空闲对象数。
以下是linux中一些对象尺寸下limit和batch设置的经验值
if (cachep-objsize 131072)limit 1;else if (cachep-objsize PAGE_SIZE)limit 8;else if (cachep-objsize 1024)limit 24;else if (cachep-objsize 256)limit 54;elselimit 120;
batch (limit1)/2;针对shared设置limit和batch时应放大适当倍数。 5.5.2.动作 5.5.2.1.初始化 我们需要在完成对象分配器初始化后为对象分配器的array和lists中的shared按分配器支持的分配尺寸进行空间分配和初始化。
5.5.2.3.在分配对象中插入缓存 分配过程将现在一级缓存分配一级缓存为空时先补充一级缓存再分配
/*static inline struct array_cache *ac_data(kmem_cache_t *cachep)
{return cachep-array[smp_processor_id()];
}*/
local_irq_save(save_flags);// 保存标志禁止中断
ac ac_data(cachep);
if (likely(ac-avail)) {STATS_INC_ALLOCHIT(cachep);ac-touched 1;objp ac_entry(ac)[--ac-avail];
} else {STATS_INC_ALLOCMISS(cachep);objp cache_alloc_refill(cachep, flags);
}
local_irq_restore(save_flags);// 恢复标志一级缓存不足时会在共享缓存有空闲对象下使用共享缓存中空闲对象来填充一级缓存。 在共享缓存没有空闲对象下直接使用对象分配器下的slab来完成一级缓存的填充。
// 多次缓存
spin_lock(cachep-spinlock);
if (l3-shared) {struct array_cache *shared_array l3-shared;if (shared_array-avail) {if (batchcount shared_array-avail)batchcount shared_array-avail;shared_array-avail - batchcount;ac-avail batchcount;memcpy(ac_entry(ac), ac_entry(shared_array)[shared_array-avail], sizeof(void*)*batchcount);shared_array-touched 1;goto alloc_done;}
}
spin_unlock(cachep-spinlock);上述是尝试采用共享缓存来填充一级缓存的逻辑实现。 5.5.2.4.在对象释放中插入缓存 一级缓存未满时先释放到一级缓存 一级缓存满了先清理一部分空间再释放。
local_irq_save(flags);
if (likely(ac-avail ac-limit)) {STATS_INC_FREEHIT(cachep);ac_entry(ac)[ac-avail] objp;// 向中间层释放对象return;
} else {STATS_INC_FREEMISS(cachep);cache_flusharray(cachep, ac);ac_entry(ac)[ac-avail] objp;// 向中间层释放对象
}
local_irq_restore(flags);// 恢复标志以下是清理逻辑
// 多核下防止并发用自旋锁互斥锁
spin_lock(cachep-spinlock);
// 先释放到下一级
if (cachep-lists.shared) {struct array_cache *shared_array cachep-lists.shared;int max shared_array-limit-shared_array-avail;// 最多可放入的if (max) {if (batchcount max)batchcount max;// 释放多余资源memcpy(ac_entry(shared_array)[shared_array-avail], ac_entry(ac)[0], sizeof(void*)*batchcount);shared_array-avail batchcount;goto free_done;// 允许释放数不足batchcount}
}
free_block(cachep, ac_entry(ac)[0], batchcount);// 这里是下一级不存在或已经满了时直接释放到slab
free_done:spin_unlock(cachep-spinlock);ac-avail - batchcount;// 完成了释放// 保证缓存中数据永远存储在起始部分memmove(ac_entry(ac)[0], ac_entry(ac)[batchcount], sizeof(void*)*ac-avail);5.5.3.多级缓存引入意义 (1). 每cpu缓存引入意义 由于每cpu缓存的并发保护只要关中断即可。无需引入自旋锁来保护并发访问。所以降低锁竞争开销。 (2). 共享cpu缓存引入意义 共享cpu缓存直接采用指针数组管理管理策略上相比slab更简单。有注意提升速度。
