大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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地址；

整体如下图：

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

相关插入逻辑：

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头

   

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

   

3. 图片示意修改：

   

操作就是将当前使用的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结构：

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;

2. 分配与释放

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

2.1 分配逻辑

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

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 释放逻辑

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

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版本分析