TLSF 代码实现分析:1、创建内存池

创建内存池

  • 内存池的开启是从new函数开始的

GetMemory

  • 可以看出最开始sTLSF是nullptr,所以会走InitMemory
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static tlsf_t sTLSF = nullptr;
......
extern "C" void InitMemory() {
#if USE_POOL
if (sTLSF == nullptr) {
void*buffer = malloc(mReservedSize);
sTLSF = tlsf_create_with_pool(buffer, mReservedSize);
}
#endif
}

static void*GetMemory(size_t size) {
if (sTLSF==nullptr){
InitMemory();
}
void * ptrMemory = tlsf_malloc(sTLSF, size);
while (ptrMemory == nullptr) {
void*add_pool = malloc(104857600);//100MB
tlsf_add_pool(sTLSF, add_pool, 104857600);
ptrMemory = tlsf_malloc(sTLSF, size);
}
return ptrMemory;
}

InitMemory

  • 内容比较简单,先malloc一块内存,然后call tlsf_create_with_pool
1
2
3
4
5
6
7
8
tlsf_t tlsf_create_with_pool(void* mem, size_t bytes)
{
// mem是直接malloc出来的,没做偏移
tlsf_t tlsf = tlsf_create(mem);
// (char*)mem + tlsf_size() 原始位置做Controller大小的偏移,size也是一样,减去Controller的大小
tlsf_add_pool(tlsf, (char*)mem + tlsf_size(), bytes - tlsf_size());
return tlsf;
}

tlsf_create

  • 里面做了fls和ffs测试,看看当前平台支持这种指令集,然后就进入了control_construct
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
tlsf_t tlsf_create(void* mem)
{
#if _DEBUG
if (test_ffs_fls())
{
return 0;
}
#endif

if (((tlsfptr_t)mem % ALIGN_SIZE) != 0)
{
printf("tlsf_create: Memory must be aligned to %u bytes.\n",
(unsigned int)ALIGN_SIZE);
return 0;
}
// mem是直接malloc出来的,没做偏移
control_construct((control_t*)mem);

return (tlsf_t*)mem;
}

control_construct

  • 干的事情就是在整个内存的开始创建了control_t对象,它就是整个内存的管理器。可以看出此处使用二维数组完成了一级和二级的构建,这与论文是不一样的。但是因为还是要算两个维度的index,所以仍旧是O1
  • control_t内部的block_null,起到了一个统一指针的作用,以往如果我们想让某个指针不指向具体的对象,一般都是赋值为nullptr。但是在这里它专门做了一个block_null,起到了一样的作用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* The TLSF control structure. */
typedef struct control_t
{
/* Empty lists point at this block to indicate they are free. */
block_header_t block_null;

/* Bitmaps for free lists. */
unsigned int fl_bitmap;
unsigned int sl_bitmap[FL_INDEX_COUNT];

/* Head of free lists. */
block_header_t* blocks[FL_INDEX_COUNT][SL_INDEX_COUNT];//segrageted lists
} control_t;

---------------------------------------

/* Clear structure and point all empty lists at the null block. */
// 在内存最前面初始化了control_t
static void control_construct(control_t* control)
{
int i, j;

control->block_null.next_free = &control->block_null;
control->block_null.prev_free = &control->block_null;

control->fl_bitmap = 0;
for (i = 0; i < FL_INDEX_COUNT; ++i)
{
control->sl_bitmap[i] = 0;
for (j = 0; j < SL_INDEX_COUNT; ++j)
{
control->blocks[i][j] = &control->block_null;
}
}
}

tlsf_add_pool

  • 这个函数做的事情很多
  • 首先在传参时已经内存位置做了偏移,单位是control_t的大小。本来这块内存真正用来分配的也就是control_t之后的部分
  • 然后在计算内存对齐后size的时候,又减去了2*4=8字节的内存,所以 pool_bytes = malloc - sizeof(control_t) - pool_overhead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// (char*)mem + tlsf_size() 原始位置做Controller大小的偏移,size也是一样,减去Controller的大小
tlsf_add_pool(tlsf, (char*)mem + tlsf_size(), bytes - tlsf_size());

------------------------------------------------------------------------------------------------

/*
** Since block sizes are always at least a multiple of 4, the two least
** significant bits of the size field are used to store the block status:
** - bit 0: whether block is busy or free
** - bit 1: whether previous block is busy or free
*/
static const size_t block_header_free_bit = 1 << 0;//0
static const size_t block_header_prev_free_bit = 1 << 1;//1 1:free 0:busy

------------------------------------------------------------------------------------------------

pool_t tlsf_add_pool(tlsf_t tlsf, void* mem, size_t bytes)
{
block_header_t* block;
block_header_t* next;

// 额外的 2 * sizeof(size_t) 字节,在头部留下的
const size_t pool_overhead = tlsf_pool_overhead();
// 字节对齐后的空间大小 pool_bytes = malloc - sizeof(control_t) - pool_overhead
const size_t pool_bytes = align_down(bytes - pool_overhead, ALIGN_SIZE);

if (((ptrdiff_t)mem % ALIGN_SIZE) != 0)
{
printf("tlsf_add_pool: Memory must be aligned by %u bytes.\n",
(unsigned int)ALIGN_SIZE);
return 0;
}

// 最大1G
if (pool_bytes < block_size_min || pool_bytes > block_size_max)
{
#if defined (TLSF_64BIT)
printf("tlsf_add_pool: Memory size must be between 0x%x and 0x%x00 bytes.\n",
(unsigned int)(pool_overhead + block_size_min),
(unsigned int)((pool_overhead + block_size_max) / 256));
#else
printf("tlsf_add_pool: Memory size must be between %u and %u bytes.\n",
(unsigned int)(pool_overhead + block_size_min),
(unsigned int)(pool_overhead + block_size_max));
#endif
return 0;
}

/*
** Create the main free block. Offset the start of the block slightly
** so that the prev_phys_block field falls outside of the pool -
** it will never be used.
*/
// 这里会减去-4byte,因为对于第一个block,prev_phys没有意义
block = offset_to_block(mem, -(tlsfptr_t)block_header_overhead);//((char*)mem-4)
block_set_size(block, pool_bytes);
block_set_free(block);
block_set_prev_used(block);
block_insert(tlsf_cast(control_t*, tlsf), block);

/* Split the block to create a zero-size sentinel block. */
next = block_link_next(block);
block_set_size(next, 0);
block_set_used(next);
block_set_prev_free(next);

return mem;
}

offset_to_block

  • 这个操作是把mem指针向前移动了4字节,其实这个时候已经指向了control_t内部了,但是因为第一个block的prev_phyx指针没有用,所以它主要做是没有问题的。反正这4个字节存的还是control_t的数据。
  • 这样的结论就是省了4字节,感觉没啥意义。
  • 最后把开始这块block转为block_header_t,也就是每块内存都有的那个header。
1
2
3
4
5
/* Return location of next block after block of given size. */
static block_header_t* offset_to_block(const void* ptr, size_t size)
{
return tlsf_cast(block_header_t*, tlsf_cast(tlsfptr_t, ptr) + size);
}

block_set_size

  • 写入block size,但是要注意这里写入的pool_bytes是经过减去pool_overhead大小,且对齐的后得到的大小。
  • 造成的后果是,原始内存块最后有至少pool_overhead(8字节)大小的内存块存在。这个内存块在后面用到了。
1
2
3
4
5
6
7
8
static void block_set_size(block_header_t* block, size_t size)
{
const size_t oldsize = block->size;

// oldsize & 0000 0000 0000 0011 ,变相的等于把size最后两位过滤出来,然后与size做或操作,等于把旧数据写入新的size最后两位
// e.g.:oldsize如果后面两位是1(前面一个block空闲)0(自己忙碌),那么无论new size第二位是怎么记录的,都会把1保留下来,也就是会保留前一个block的状态。
block->size = size | (oldsize & (block_header_free_bit | block_header_prev_free_bit));
}

block_set_free

1
2
3
4
5
static void block_set_free(block_header_t* block)
{
// block_header_free_bit = 1,与操作相当于无脑把size 0位上写入1,也就是free
block->size |= block_header_free_bit;
}

block_set_prev_used

  • 一样的为操作方式,改的是size的1位,只不过此处写入的是0,因为取反了。
1
2
3
4
static void block_set_prev_used(block_header_t* block)
{
block->size &= ~block_header_prev_free_bit;
}

block_insert

1
2
3
4
5
6
7
/* Insert a given block into the free list. */
static void block_insert(control_t* control, block_header_t* block)
{
int fl, sl;
mapping_insert(block_size(block), &fl, &sl);
insert_free_block(control, block, fl, sl);
}

mapping_insert

  • mapping_insert的核心是获得fli和sli
  • 这里的实现与论文不同,论文中是直接从2^7开始的,但是实现时前面128字节作为FLI = 0 来使用了。并且将128byte分为了32份。也就是size < SMALL_BLOCK_SIZE部分的处理。
  • 大于128后,sl是按照论文的算法得到的。可以得出fl是7,但是注意,前面的control_t内部是个数组,因此,128之后的所以其实是从1开始的。
  • 所以有了fl -= (FL_INDEX_SHIFT - 1),其中FL_INDEX_SHIF=7
  • 可以看出FL_INDEX_SHIFT - 1就是从7到1的转换,也就是把论文算法中得到的sl转为从1开始的真实的数组实现的sl。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void mapping_insert(size_t size, int* fli, int* sli)
{
int fl, sl;
if (size < SMALL_BLOCK_SIZE)
{
/* Store small blocks in first list. */
fl = 0;
sl = tlsf_cast(int, size) / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT);
}
else
{
fl = tlsf_fls_sizet(size);//find last set
sl = tlsf_cast(int, size >> (fl - SL_INDEX_COUNT_LOG2)) ^ (1 << SL_INDEX_COUNT_LOG2);
fl -= (FL_INDEX_SHIFT - 1);
}
*fli = fl;
*sli = sl;
}

insert_free_block

  • 这里实现了最初那块block进入到control_t的管理
  • 上面计算出了了fl和sl
  • 代码比较简单,就是新block的内存地址占据了control->blocks[fl][sl]的位置,原来那个block_header_t指针和新block 连接了起开。
  • 然后设置fl_bitmap 和 sl_bitmap的掩码为1,标志这某一个freelist有数据了。
  • 可以预见到,当new的时候会寻找到这块非常大的原始block,然后切走一块,剩余的部分经过计算,可能会放入新的fl sl中去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void insert_free_block(control_t* control, block_header_t* block, int fl, int sl)
{
block_header_t* current = control->blocks[fl][sl];
tlsf_assert(current && "free list cannot have a null entry");
tlsf_assert(block && "cannot insert a null entry into the free list");
block->next_free = current;
block->prev_free = &control->block_null;
current->prev_free = block;

tlsf_assert(block_to_ptr(block) == align_ptr(block_to_ptr(block), ALIGN_SIZE)
&& "block not aligned properly");
/*
** Insert the new block at the head of the list, and mark the first-
** and second-level bitmaps appropriately.
*/
control->blocks[fl][sl] = block;
control->fl_bitmap |= (1 << fl);
control->sl_bitmap[fl] |= (1 << sl);
}

block_set_used

1
2
3
4
5
6
static void block_set_used(block_header_t* block)
{
// 取反为1111 1111 1111 1101
// 与操作最终值看size本身的30位,等于保留size值,但是第二位是0 & X ,必然等于0。也就是把第二位置为0 了
block->size &= ~block_header_free_bit;
}
  • 一系列的函数调用
  • block_to_ptr这里等于把block向后偏移8字节,然后转成了void*。此时这个指针指向的位置是原来真正存储位置向后4字节,记住原来有4个字节在control_t里。这里埋个伏笔,这个操作和malloc有关。
  • block_size(block) - block_header_overhead,这里的block size是真实的,也就是不算control_t里的那4字节的,所以这块是原block的size - 4
  • offset_to_block后会发现,block指针指向了block块后的一个位置,在block_set_size函数里我们说过,至少还有8byte的内存没有被使用。而此时这个block就是指向了这块内存。
  • 到此位置,我们知道了next指针其实就是指向了紧挨着block后的那个内存块。因此next->prev_phys_block = block是完全符合内存分布情况的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#define offsetof(s,m) ((size_t)&(((s*)0)->m))

// 这里block_start_offset = 4+4 = 8
static const size_t block_start_offset =
offsetof(block_header_t, size) + sizeof(size_t);

// 这里等于把block向后偏移8字节,然后转成了void*
static void* block_to_ptr(const block_header_t* block)
{
return tlsf_cast(void*,
tlsf_cast(unsigned char*, block) + block_start_offset);
}

/* Return location of next block after block of given size. */
static block_header_t* offset_to_block(const void* ptr, size_t size)
{
return tlsf_cast(block_header_t*, tlsf_cast(tlsfptr_t, ptr) + size);
}

/* Return location of next existing block. */
static block_header_t* block_next(const block_header_t* block)
{
block_header_t* next = offset_to_block(block_to_ptr(block),block_size(block) - block_header_overhead);
tlsf_assert(!block_is_last(block));
return next;
}

/* Link a new block with its physical neighbor, return the neighbor. */
static block_header_t* block_link_next(block_header_t* block)
{
block_header_t* next = block_next(block);
next->prev_phys_block = block;
return next;
}
  • 接下来的三句代码都是在操作size那四个字节
  • 这里可以看到后面那8个字节,其实不足以支撑起一个完整的block_header_t结构体。真正用到只有prev_phys_block和size。
  • 而最后block_set_prev_free也标记了block是free状态的。
1
2
3
block_set_size(next, 0);
block_set_used(next);
block_set_prev_free(next);
  • tlsf_add_pool执行完成,同时也是tlsf_create_with_pool执行完成。
  • 在回过来看InitMemory函数,buffer和sTLSF地址是一样的。
  • 到此为止,TLSF创建完成,包括的头部的control_t、中间超大size的free block,和最后的那个8byte的next块。

Link

# Engine
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×