名词

• DSA： dynamic storage allocator
• TLSA：Two Level Segregated Fit memory allocator
• RTOS：real-time operating system
• WCET：worst-case execution time

介绍

• 对于real-time system来说，知道操作时间的边界是很重要的。可以用来分析系统的规模。比如需要多少内存。
• 一般来说，一些算法被设计为good average respone times，也就是平均响应时间比较好。但是对于引擎来写，是需要知道allocation和deallocation的边界的。
• 通常设计RTOS的人都避免使用动态内存，因为动态内存分配的worst-case execute time 没有边界。说白了，不可控，实时系统可能因为内存分配过久而卡住。

Real-Time requirements for DSA

• 动态的内存分配可以归纳为以下一些点：
• Bounded response time：相应时间是有边界的。最坏的内存分配和回收时间应该是可以被知道的，而且这个时间是与数据无关的。
• Fast response time：内存分配时间要够快，如果非常慢就不具备可使用性了。
• Memory requests need to be always satisfied：内存请求必须总是被满足。虽然内存终会被耗尽，但是好的DSA应该尽量减少耗尽的概率，办法就是用最少的内存碎片。

DSA算法

• 在内存分配算法中，空闲内存块的管理是算法的核心。根据寻找空闲内存块的策略，可以将内存分配算法分为以下几种：
  • Sequential Fit：将所有的空闲内存块，放入到一个单向/双向链表中。这是最基础的管理策略。算法非常简单，但寻找空闲内存块的效率依赖于链表的大小。
  • Segregated Fit：将所有的空闲块，放入到一组链表中，每一个链表中只包含某一个大小范围的空闲块。例如最典型的dlmalloc算法。
  • Buddy System： Segregate Fit算法的变种，具有更好的切割和合并效率，又很多变种，如Binary Buddies，Fibonacci Buddies， Weighted Buddies等。通常这类算法的内部碎片化问题比较严重。
  • Indexed Fit：通过一些高阶的数据结构来索引（Index）空闲的内存块。例如基于平衡树的“Best Fit”算法。
  • Bitmap Fit： Indexed Fit算法的变种，通过一小段内存的位图来标记对应的内存是空闲的还是使用中。

DSA操作模型

多数DSA如何管理内存块

• 初始化时，DSA管理的是一个单独的，比较大的内存块。一般称为：initial pool。分配器依赖底层的操作系统（或者硬件的MMU，虚拟内存）去申请新的内存。
• 第一批allocate request会 fulfilled（十分愉快）的从initial pool中拿到内存，然后pool变小
• 上一个被分配的块释放时，有两种事情可能会发生，依赖于被释放块的物理位置
  • 被释放的memory block可能与initial pool合并，或者与相邻的block合并
  • 这个block周围的block都被allocate了，无法合并
  • 第一种情况下，DSA算法会合并block，或者将它会还到initial pool。第二种情况，DAS将这个block放入一个freeblock的数据结构中。
  • PS：这个很好理解，能合并的话等于减少碎片。不能合并的，也有个结构管理者，可以被reuse。
• 再次申请内存时，可以愉快的从initial pool中获取内存，或者在freeblock中搜索一个合适的。freeblock的存储和搜索算法是DSA的核心，决定了性能。如果freeblock给出的内存大于请求的内存，那么这个block就会被分割，多余的返还给freeblock structure。

DSA操作

• Insert a free block
  • 这个操作会在malloc和free的时候发生。
  • free时出现了一个被释放的内存，则需要insert到freeblock，或者free后合并成了一个新的更大的block，然后insert。
  • malloc对应了上面说的，从freeblock拿到一个size过大的block后，会进行split操作。多余的部分会被执行insert。
• Search for a free block of a given size or larger
  • 寻找一个指定size的block，或更大的
• Search for a block adjacent to another
  • 为了合并block，需要找到一个与其相邻的block
• Remove a free block
  • malloc & free时发生
  • free时因为合并的原因，可能某个block被合并了因此需要remove
  • malloc很好理解，这个free block被分配出去了

Design Criteria of TLSF（设计标准）

• 满足对于实时系统最重要的需求：有边界的，很短的响应时间；有边界的，低碎片化

• 还要考虑嵌入式系统

  • 可信任的环境，数据保护不是程序要考虑的
  • 很小的内存
  • 不支持虚拟内存

• 为了满足各种约束条件和需求，TLSF有以下的指导方针

  • Immediate coalesce：及时合并

    • 被释放的block会被立即的与邻近的block合并
    • 有些DSA算法会做延迟合并或者不合并，这个适用于频繁请求同样大小的内存的情况。这个时候立即合并，然后又立马来了一个内存请求，会造成频繁的split，然后走insert block。
    • 延迟合并会造成不确定性，请求频繁时可能会造成需要合并很多小的freeblock来满足block请求。举个例子：本来有两个block合并后就可以满足需求了，但是因为延迟，导致某一时刻需要合并很多小的block才行。这就造成两个问题：1、耗时（合并肯定是耗时的）。2、增加了碎片，合并的过程中可能出现碎片，本该合并的没合并，也是碎片。

  • Splitting threshold：分割的临界值（阈值）

    • 论文里是最小的block 16kb，这样设计有几点考虑：
    • 一般block存的不是整数这样的小数据类型，通常都是复杂的结构。因此设计的会比较大。
    • 限制在16k（这里的想表达的是16k不小了），这样用于管理block的信息就可以存储在block中了（太小的话还不够放这些管理信息的），这些信息有：list of free blocks point。这个后面有详细的说明。

  • Good-fit strategy：

    • TLSF试着返回能后满足大小需求的block
    • 因为很多程序使用的都是很小size的block，相较于first-fit，Best-Fit策略是可以满足的，而且造成的碎片更小。Best-Fit策略可以使用segregated free list实现。
    • First-fit和Next-fit先要用可预测的方式来实现太困难
    • TLSF使用Good-fit策略，它使用一组free list，每个list都是一个non-ordered list of free block。这个list上的block的size在一个size class（大小分类）和next class之间，每个list所包含的block都是这个size class。用人话说就是每个list管理一个size区间内所有的block。

  • No reallocation

    • 分配内存后，不会重新去分配一个新size的内存

  • Same strategy fro all block sizes

    • 使用相同的策略
    • 不同的策略会导致行为不一致，而且WCET很高，而且难以获知。

  • Memory is not cleaned-up

    • 不会做memset(0)这样的擦除操作
    • 多用户环境，DSA策略会擦除内存，避免安全问题。
    • TLFS认为运行环境安全，出于性能考虑不会做内存初始化（擦除操作）。

LTSF数据结构

• 从论文的角度说就是用两套索引来确定一个链表，这个链表是空闲内存块连接起来的。
• 这样的方式的好处是什么？目前看主要是搜索复杂度上有巨大的优势，按照作者的设计搜索复杂度为0，后面会说。

实现代码

• 注意：代码可以体现算法设计的思想，但是无法完全的映射到算法上。

1
2
3
4
5
6
7
8
9
10
11
12
13

/* 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;

具体结构

• First Level

  • 从图中可以看出，每一块代表着它所指向的最终内存的size区间，注意是区间。2^4，意味着从这深入进去，不管是在SL的哪一个链表上，size的范围是（2^4 ~ 2^4-1）。
  • 图中右上角那一串01，是一个掩码。它的作用是标记某一区间上是否还有free block。以图为例，2^4、2^5两个区间下面是没有free bloc，而2^6因为掩码是1，所以代表它下面有free block。
  • 从实现上将其实就是个int，这是因为可以利用CPU指令来快速实现从低位到高位查找第一个1或者反之从高位到低位的第一个1。比如在Windows系统上的_BitScanReverse、_BitScanForward

• Second Level

  • 是对FL确定区间的再分割，分割多少快由一个SLI参数决定，按照论文里的描述SLI=4，分割了16条链表。

  • SLI is expressed as the log2 of the number of second-level division

  • SLI = log 2 16(number of second-level division)，所以 SLI = 4

  • SL每个格子的具体区间是 ( 2^n + 2^(n-1) * x ) ~ ( 2^n + 2^(n-1) * (x+1) )，可以看出FL下的SL的区间是按照 2^(n-1)为增量增加的，那么显然N越大增量越大。也就是约往高位走，内存区间越大。

  • 同样，每一SL也都有一个int类型的掩码，作用是一样的。这也决定了，SL中搜索的复杂度是1

    

• block header定义

  • 每个被TLSF管理的block中都会有一块区域保存这一个struct，用来记录这个block的各种信息。

  • size：block的大小

  • F：标记这个block是否是free

  • prev_phys_block，记录物理上，上一个block的位置。这个是用来合并block的，但是显然它只记录了向前的一个block的位置。这里在具体实现的时候可以做变种，比如记录前后。试想一下，如果前面的block不是free的，那么就不合并了，但是有可能物理上的后一个block是free可以合并呢？

  • next、prev这两个指针没啥特别说的，双链表的基本构成吧

    

• 计算first index & second index的公式，但是实际实现的时候用的也不是这个方法啊。感觉就是论文为了凑公式用的。

  

• 公式的举例说明。

  

TLFS中的函数

• Initialise：初始化，需要三个参数，pool的内存地址，这个pool还是malloc出来的；size of pool； SLI的值。实际的实现中也是这3个参数，但是SLI写死了。
• Get Free block：这里的就是搜索策略
  • 首先按照公式或者说掩码找到f和s，然后看看链表是不是空的，如果不是直接把第一个free block返回给请求。这里需要注意，它其实不使用Best-fit，因此才能做到复杂度是1。
  • 如果找不到，就去下一个较大的区间的list里面找。如果找到了，就要切分，然后该返回给请求的分会，剩下的部分insert到一个合适的list里面。
  • 最坏的情况是完全找不到，那就返回错误。可以想象，最坏的查找次数是FLI*SLI次，是个常数。

复杂度分析

• 这块按照论文的伪代码介绍，确实可以看出来是复杂度为1，这就保证了执行时间是可控的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void *malloc(size){
	int fl, sl, fl2, sl2;
	void *found_block, *remaining_block;
	mapping (size, &fl, &sl); // O(1)
	found_block=search_suitable_block(size,fl,sl);// O(1)
	remove (found_block); // O(1)
	if (sizeof(found_block)>size) {
	remaining_block = split (found_block, size);
	mapping (sizeof(remaining_block),&fl2,&sl2);
	insert (remaining_block, fl2, sl2); // O(1)
	}
	remove (found_block); // O(1)
	return found_block;
}

void free(block){
	int fl, sl;
	void *big_free_block;
	big_free_block = merge(block); // O(1)
	mapping (sizeof(big_free_block), &fl, &sl);
	insert (big_free_block, fl, sl); // O(1)
}

Link

• http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf