Slob分配器的数据结构和分配逻辑

Slob分配器的数据结构和分配逻辑slob分配器:1.数据链表结构构造;2.分配与释放的逻辑分析;

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

Slob分配器的数据结构和分配逻辑

我们知道OS提供很多机制保证内存的管理,而分配器则是空闲的内存以一定的数据结构组织起来,通过合适的算法进行分配;

slob(simple list of blocks)分配器,与slab、slub设计思路基本一致,而数据结构并不复杂,我们作为基础首先学习,后续拓展到slub和slab;

1. 数据结构

使用三个链表分别记录管理当前的freelist,依据其size不同进行划分:

  1. 0 ~ 256 Bytes,添加到small list中,后续分配即在此list中查询;
  2. 256 ~ 1024 Bytes,添加到medium list中,后续分配即在此list中查询;
  3. 1024 ~ PageSize,添加到large list中,后续分配即在此list中查询;

超过一个page大小的size直接通过buddy分配,不需要经过slob分配器;

#define SLOB_BREAK1 256
#define SLOB_BREAK2 1024
static LIST_HEAD(free_slob_small);
static LIST_HEAD(free_slob_medium);
static LIST_HEAD(free_slob_large);

Jetbrains全家桶1年46,售后保障稳定

1.1 slob_list链

1.1.1 slob_list 整体结构

我们已经知道slob分配器中创建了三条链表,其数据结构保持一致:

  1. slob_list是一个双向量表,每次节点插入在head之后;
  2. 其中每个node是list_head结构,实际填充为page中的lru结构体;
  3. 遍历slob_list时通过container_of 获取到page地址;

整体如下图:

image-20211211093239368

具体将next和prev体现出来则是:

image-20211211093253843

相关插入逻辑:

set_slob_page_free(sp, slob_list);//将申请到的page(sp)加入到slob_list中
static void set_slob_page_free(struct page *sp, struct list_head *list)
{ 
   
	list_add(&sp->lru, list);
	__SetPageSlobFree(sp);
}

1.1.2 slob_list 分配后移动

分配后移动链表头,构成lru的处理:

  1. 判断当前分配节点是否需要移动
    1. 当前分配节点为slob_list -> next的时候不需要移动
    2. 另外只有一个节点的时候不需要移动
  2. 将slob_list从slob_list中移除;
  3. 将slob_list插入到当前分配page的前序;
//每次分配后会修改slob_list的顺序:
prev = sp->lru.prev;
//prev即当前分配页的前序(比如在page2上分配,prev即page3,prev->next = page2)
//slob_list即链表头,其prev是page1,其next是page3
if (prev != slob_list->prev && slob_list->next != prev->next)
    list_move_tail(slob_list, prev->next);

//将page2从链表中移除,插入到head->next
static inline void list_move_tail(struct list_head *list, struct list_head *head)
{ 
   
	__list_del(list->prev, list->next);//删除slob_list
	list_add_tail(list, head);//将slob_list 插入到当前分配页的前序,即下次第一个遍历的位置为当前分配页
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{ 
   //将传入节点删除,即上述传入的slob_list
    next->prev = prev;
    prev->next = next;
}
static inline void list_add_tail(struct list_head *entry, struct list_head *head)
{ 
   //将slob_list插入到page2和page3之间
    __list_add(entry, head->prev, head);
    //__list_add(slob_list, page2->prev, page2);
}
static inline void __list_add(struct list_head *entry, struct list_head *prev, struct list_head *next)
{ 
   
    next->prev = entry;
    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
}

分步图示:

  1. 删除slob_list头

    image-20211211101252393

  2. 将slob_list头插入到当前分配页(page2)的前序

    image-20211211102125642

  3. 图片示意修改:

    image-20211211102450952

操作就是将当前使用的page放到slob_list的next位置,使得下次遍历时第一个访问(总是优先访问正在使用的部分)

1.1.3 page结构

仅截取slob中使用到的部分:

struct page { 
   
	/* First double word block */
	unsigned long flags;	
    ...
   	/* Second double word */
	union { 
   
		pgoff_t index;		/* Our offset within mapping. */
		void *freelist;		/* sl[aou]b first free object */
		/* page_deferred_list().prev -- second tail page */
	};
    union { 
   
	...
		struct { 
   
			union { 
   
				...
				unsigned int active;		/* SLAB */
				struct { 
   			/* SLUB */
					unsigned inuse:16;
					unsigned objects:15;
					unsigned frozen:1;
				};
				int units;			/* SLOB */

    ...
    /* Third double word block */
	union { 
   
		struct list_head lru;   
    ...
    struct kmem_cache *slab_cache;	/* SL[AU]B: Pointer to slab */    

1.2 page中slob_block链

通过slob_list遍历可以找到空间足够的page(判断page->units),具体来看page中如何管理slob_block结构:

image-20211209223048399

  1. page中维护freelist会指向此page中第一个free的slob_block

  2. 其中对于只有一个block大小的空间,存储-offset的值,以这样的方式解决存储空间不足的问题:

    即对于每一个free node,根据其size划分为两种case:

    • 如果size为1,则存储-offset,这样则可以根据获取到的正负作为判断依据;

    • 如果size大于1,则存储,size和offset

相关结构:

#if PAGE_SIZE <= (32767 * 2)
typedef s16 slobidx_t;
#else
typedef s32 slobidx_t;
#endif

struct slob_block { 
   
	slobidx_t units;
};
typedef struct slob_block slob_t;
接口 功能
set_slob 记录当前slob_block的大小和偏移
slob_units(slob_t *s) 返回对应节点的block大小
slob_next(slob_t *s) 返回下一个节点的值,即通过当前位置添加offset
slob_last(slob_t *s) 确认当前slob是否为本页的最后一个block,即通过next地址是否在本页内判断

2. 分配与释放

在了解到其数据结构的情况下,分配与释放的逻辑就很明确了;

2.1 分配逻辑

image-20211211111215942

如下图示演示了新分配4个units大小的变化:

image-20211211111735045

code注释部分:

/* * slob_alloc: entry point into the slob allocator. */
static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
{ 

struct page *sp;
struct list_head *prev;
struct list_head *slob_list;
slob_t *b = NULL;
unsigned long flags;
if (size < SLOB_BREAK1)//根据要分配的size选择合适的链表
slob_list = &free_slob_small;
else if (size < SLOB_BREAK2)
slob_list = &free_slob_medium;
else
slob_list = &free_slob_large;
spin_lock_irqsave(&slob_lock, flags);
list_for_each_entry(sp, slob_list, lru) { 
//遍历slob_list,注意这里是通过list中的lru结构计算偏移进而找到page
/* Enough room on this page? */
if (sp->units < SLOB_UNITS(size))
continue;
/* Attempt to alloc */
prev = sp->lru.prev;
b = slob_page_alloc(sp, size, align);//页内分配slob_block
if (!b)
continue;
if (prev != slob_list->prev &&
slob_list->next != prev->next)// 将slob_list 头移动到当前分配页之前
list_move_tail(slob_list, prev->next);
break;
}
spin_unlock_irqrestore(&slob_lock, flags);
/* Not enough space: must allocate a new page */
if (!b) { 

b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node);//分配slob页
if (!b)
return NULL;
sp = virt_to_page(b);
__SetPageSlab(sp);
spin_lock_irqsave(&slob_lock, flags);
sp->units = SLOB_UNITS(PAGE_SIZE);
sp->freelist = b;
INIT_LIST_HEAD(&sp->lru);
set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
set_slob_page_free(sp, slob_list);//将page中lru加入slob_list链表,注意插入到head的下一个;
b = slob_page_alloc(sp, size, align);//页内分配slob_block
BUG_ON(!b);
spin_unlock_irqrestore(&slob_lock, flags);
}
if (unlikely((gfp & __GFP_ZERO) && b))
memset(b, 0, size);
return b;
}
/* * Allocate a slob block within a given slob_page sp. */
static void *slob_page_alloc(struct page *sp, size_t size, int align)
{ 

slob_t *prev, *cur, *aligned = NULL;
int delta = 0, units = SLOB_UNITS(size);
for (prev = NULL, cur = sp->freelist; ; prev = cur, cur = slob_next(cur)) { 
//通过偏移遍历页内slob_block
slobidx_t avail = slob_units(cur);
if (align) { 
//如果有对齐要求,则将需要对齐的部分切割出来
aligned = (slob_t *)ALIGN((unsigned long)cur, align);
delta = aligned - cur;
}
if (avail >= units + delta) { 
 /* room enough? */
slob_t *next;
if (delta) { 
 /* need to fragment head to align? */
next = slob_next(cur);
set_slob(aligned, avail - delta, next);
set_slob(cur, delta, aligned);
prev = cur;
cur = aligned;
avail = slob_units(cur);
}
next = slob_next(cur);//对齐部分处理完成
if (avail == units) { 
 //当前block空间与要分配内容大小相等
if (prev)
set_slob(prev, slob_units(prev), next);//将前边block的偏移计算到next block的位置
else
sp->freelist = next;//是页内第一块则直接将freelist指定到next
} else { 
 /* fragment */
if (prev)
set_slob(prev, slob_units(prev), cur + units);//将前边block的偏移计算到分配剩余的位置
else
sp->freelist = cur + units;//页内第一个则链接到freelist上
set_slob(cur + units, avail - units, next);//当前block计算到next的偏移,更新
}
sp->units -= units;//更新页内剩余 units的大小
if (!sp->units)//满了就从slob_list中移除
clear_slob_page_free(sp);
return cur;
}
if (slob_last(cur))//存在一种情况,页内的block均比待分配size小,则返回NULL;
return NULL;
}
}

2.2 释放逻辑

释放时主要考虑位置的不同,分为多种情况:

image-20211211120614993

code 注释:

/* * slob_free: entry point into the slob allocator. */
static void slob_free(void *block, int size)
{ 

struct page *sp;
slob_t *prev, *next, *b = (slob_t *)block;
slobidx_t units;
unsigned long flags;
struct list_head *slob_list;
if (unlikely(ZERO_OR_NULL_PTR(block)))
return;
BUG_ON(!size);
sp = virt_to_page(block);
units = SLOB_UNITS(size);
spin_lock_irqsave(&slob_lock, flags);
if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) { 
//释放掉这个block,整页都free
/* Go directly to page allocator. Do not pass slob allocator */
if (slob_page_free(sp))
clear_slob_page_free(sp);
spin_unlock_irqrestore(&slob_lock, flags);
__ClearPageSlab(sp);
page_mapcount_reset(sp);
slob_free_pages(b, 0);
return;
}
if (!slob_page_free(sp)) { 
//原来是full的,需要加入slob_list中
/* This slob page is about to become partially free. Easy! */
sp->units = units;//记录free的units
sp->freelist = b;//标记block位置
set_slob(b, units, (void *)((unsigned long)(b + SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));
//加入合适的slob_list
if (size < SLOB_BREAK1) slob_list = &free_slob_small;
else if (size < SLOB_BREAK2) slob_list = &free_slob_medium;
else slob_list = &free_slob_large;
set_slob_page_free(sp, slob_list);
goto out;
}
//原来就是部分空闲的page
sp->units += units;//标记剩余空间大小
if (b < (slob_t *)sp->freelist) { 
//释放位置在最开始,则更新freelist
if (b + units == sp->freelist) { 

units += slob_units(sp->freelist);
sp->freelist = slob_next(sp->freelist);
}
set_slob(b, units, sp->freelist);
sp->freelist = b;
} else { 
//其他情况,找到对应
prev = sp->freelist;
next = slob_next(prev);
while (b > next) { 
//先找到要释放的位置
prev = next;
next = slob_next(prev);
}
if (!slob_last(prev) && b + units == next) { 
//可以和next block连在一起不?
units += slob_units(next);
set_slob(b, units, slob_next(next));
} else //标记当前block的位置和到下一个的偏移
set_slob(b, units, next);
if (prev + slob_units(prev) == b) { 
//可以和prev block连在一起不?
units = slob_units(b) + slob_units(prev);
set_slob(prev, units, slob_next(b));
} else //标记prev到当前位置的偏移
set_slob(prev, slob_units(prev), b);
}
out:
spin_unlock_irqrestore(&slob_lock, flags);
}

slob分配器对外提供两套接口:

  1. kmalloc 指定obj size直接从链表中分配空间;
  2. kmem_cache 则维护一个kmem_cache的对象,从其中分配固定大小的空间;

附录

  1. 涉及相关文件目录

    目录 说明
    /mm/slob.c slob分配器code实现部分
    /include/linux/list.h 涉及到list操作的定义实现部分
    /include/linux/kernel.h 涉及到相关宏的依赖
    /include/linux/mm_types.h page结构体的定义
  2. 本文中code均基于kernel-4.9版本分析

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234335.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 数据库置疑修复工具未找到数据文件_sql2008数据库置疑

    数据库置疑修复工具未找到数据文件_sql2008数据库置疑本工具基于SQLServer产品设计问题,常因断电、出错、丢失文件等原因引起数据错误,此现象大部分伙伴都曾碰到且不易修复,本工具通过智能识别以快速处理置疑等数据库异常状态目前支持数据库版本有MSDE\SQL2000\SQL2005\SQL2008,适用于公司所有产品线,且针对T3|T6|T+无缝完美兼容文件:n459.com/f/25127180-479733688-1b11c9(访问密码:551685)以下内容无关:—————————————-

  • Activity工作流学习总结

    Activity工作流学习总结1.概念工作流(Workflow),就是“业务过程的部分或整体在计算机应用环境下的自动化”,它主要解决的是“使在多个参与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行,从而实现某个预期的业务目标,或者促使此目标的实现”。2.Activity介绍Activiti5是由Alfresco软件在2010年5月17日发布的业务流程管理(BPM)框架,它是覆盖了业务流程管理、工作流、…

  • tb6612fng电机驱动模块接线(单相电机接线图)

    TB6612FNG是东芝半导体公司生产的一款直流电机驱动器件,它具有大电流MOSFET-H桥结构,双通道电路输出,可同时驱动2个电机。也许大家更熟悉L298N,其实这两者的使用基本一致的。而且,相比L298N的热耗性和外围二极管续流电路,它无需外加散热片,外围电路简单,只需外接电源滤波电容就可以直接驱动电机,利于减小系统尺寸。对于PWM信号输入频率范围,高达100KHz的频率更足以满足我们大部分的要求。这个电机驱动某宝上都有卖的。VM:15V(也可以使用7.2v)电池VCC:

  • Servlet主要知识点

    Servlet主要知识点

  • 如何解决tomcat启动闪退问题

    如何解决tomcat启动闪退问题在这几天,遇到一个Tomcat启动闪退的问题,通过查阅各种资料,算是完美解决。在此分享给朋友们。    首先,确定你的问题在哪里    1.查询错误:win+R输入cmd,进入一般处理程序。通过cd找到你Tomcat的bin文件夹,在bin下面输入startup.batrun运行,运行后,如果如(图1)提示,缺少JAVA_HOME或者缺少JRE_HOME(如

  • 第一个Java程序—HelloWorld[通俗易懂]

    第一个Java程序—HelloWorld[通俗易懂]工欲善其事必先利其器,在写第一个Java程序之前,需要安装JDK以及配置环境变量,具体步骤见Windows中配置Java环境变量。环境变量搭建完成了,是不是已经迫不及待想敲几行代码跑跑看?走起!1.在英文路径下创建一个记事本文件,命名为HelloWorld.java。这个文件是存放java代码的文件,称为源文件。这里是将文件类型改为java类型,并不单单是名字。这里的.java是文件类型,有的电脑上可能文件后缀名给隐藏了,虽然文件名里有.java但不是个java文件。可以点击查看,将文件扩展

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号