C Implement Memory Allocator - Implicit Free List

  C  Comments

前言

由前篇文章可以知道，使用 stack data structure 是最簡單的 memory allocator 入門寫法，但是卻會造成一些問題，例如不能任意順序 free 等。既然如此，我們就換成 list 來實作 memory allocator，解決使用 stack 實作的問題。

除了實作之外，也會討論到幾個實作 allocator 上遇到的問題，例如 sbrk，以及 minimum alignment。

Memory allocator 要素

在實作之前，先歸納一下 allocator 需求。 Computer Systems(book) 與 CS 4400 – Computer Systems 說明幾個 allocator 要素，包含：

  1. Handling arbitrary request sequences
  2. Aligning blocks (8 bytes on 32-bit and 16 bytes on 64-bit)
  3. Not modifying allocated blocks (compaction is not allowed)
  4. How does free know an allocated block’s size?
  5. How is unallocated space represented?
  6. How do we keep track of free blocks?
  7. How do we choose an appropriate free block?

依照上列條件，可以知道 stack 形態的 allocator 其實並不能滿足基本 allocator 需求(例如：arbitrary request sequences)，因此後續在實作 implicit free list 的時候，也會根據上列來一一檢視是否有達成需求。

基本 Implicit Free List

起初概念，將一個連續性記憶體分成好幾個 blocks ，使用 block header 來標示每個 block 的 size 和 allocated 狀態，並且透過 header 的 size 得知道下一個 block 的初始位置，如此一來就可以遍歷所有的 blocks。

Block format

Block size 應包含 header + payload size (除了最後一個用為終止線的 block 之外)，例如：header struct 是 8 bytes 而要 allocate 的 data size 是 16 bytes，那 block size = 8 + 16(尚未考慮 alignment)。Block size 數字會影響後續進行合併 (coalesce) 計算，所以很重要。

![study]({{ site.url }}/assets/images/memory-allocator-1.png)

Aligning blocks

malloc 應該遵守 alignment 規定：8 bytes on 32-bit and 16 bytes on 64-bit。(其原因在下方補充內容中會提及)，所以當我們在計算 block size 時，要加入 alignment 條件，即：

1#define HEADER_SIZE 8
2#define ALIGNMENT 16
3#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
4
5
6size_t block_size(size_t payload_size)
7{
8  return ALIGN(HEADER_SIZE + payload_size);
9}

重點：align 所有 block size，而不是只有 payload size。

另外一個重點，malloc return 的 payload address 必須符合 16-byte-aligned，因此必要時應調整第一個 header 的起始位置，讓 payload address & 0xF 等於 0。

e.g. 整個 heap 的起始位置是: 0xc000 第一個 header 的起始位置應為：0xc000 + 8 如此一來， payload 的起始位置就會為：0xc008 + 8(header size)

初始化 allocator

首先，先跟 kernel 索取需要的空間大小 (sbrk or mmap)，然後建立一個 header 包含可使用的 bytes 數量，以及最後一個代表終止 header。

![study]({{ site.url }}/assets/images/memory-allocator-3.png)

假設 header struct size 是 8 byte，那圖示中總共的 heap 需求空間就是 128 + 8 header size。

Allocate

如果需要一個 size 為 16 bytes 的空間，則會從第一個 block 開始查找有沒有適合的空block，如果有的話，則將該 block 的 allocated 改成 1。

![study]({{ site.url }}/assets/images/memory-allocator-4.png)

假如 block 的 size > allocate 所需求的 size + Header size，則會計算出剩餘的 size 大小，並且新建一個 header 在 block 後方位置(將原先的 block 拆分成兩個)。

最後回傳 block address + header size bytes 的memory 位置(payload 的起始位置)。

Free

當執行 free 的時候，只要將 object address - header size bytes 來找到 header address，並且將 header 的 allocated 設為 0 即可。

![study]({{ site.url }}/assets/images/memory-allocator-5.png)

當然這樣會導致原先一個大 block 被拆分成很多零碎的小 blocks，進而造成 external fragmentation 問題。後面會說明將這些因為 free 行為而產生的零碎 blocks 合併(coalesce)的方式。

Traveling all blocks

從頭開始遍歷所有的 blocks，然後在 block size 為 0 的地方終止。

![study]({{ site.url }}/assets/images/memory-allocator-6.png)

檢視

完成了基本版的 implicit free list 後，來檢視一下一開始提及的條件是否有滿足：

1.Handling arbitrary request sequences (O)

從實作方式可以得知 free 和 allocate 不受順序限制。

2.Aligning blocks (8 bytes on 32-bit and 16 bytes on 64-bit) (O)

3.Not modifying allocated blocks (compaction is not allowed)(O)

4.How does free know an allocated block’s size?

使用 block header 來得知 size。

5.How is unallocated space represented?

用 block 中的 allocated 來標示此 block 目前狀態。

6.How do we keep track of free blocks?

使用 block chain 結合 header 中的 allocated 來追蹤所有 free blocks。

7.How do we choose an appropriate free block?

透過遍歷所有 blocks 找出適合 size 的 block。

改善 Implicit Free List

上面提到基本的 implicit free list 作法，接下來說明幾種可以改善的方向：

1. 調整 header 格式

![study]({{ site.url }}/assets/images/memory-allocator-7.png)

原先的 header struct 是

1typedef struct {
2  size_t size;
3  size_t allocated;
4} block_header;

但是由於 alignment 關係，一開始的幾個 bit 值皆為 0 ，因此可以直接使用這些 bit 來表示 allocated 值即可。(e.g. alignment 為 8 bytes，則 0-2 bits 皆為 0)

2. 改善 - Coalesce

在基本版本的 implicit free list 中，有可能因為 allocate 和 free 的連續操作，造成原先大塊的 block 被拆分成小塊的 blocks，進而導致再次 allocate 大 size 的 object 時會找不到適合的 block。

![study]({{ site.url }}/assets/images/memory-allocator-9.png)

為了解決這個問題，在 free object 步驟時，需要適時合併前後空的 block，以回復成較大的 block。

![study]({{ site.url }}/assets/images/memory-allocator-10.png)

但在合併時會有一個問題，從 block header 中可以知道下一個 block 的 size 和 allocated 狀態，但該如何知道上一個 block header 的值呢？我們可以在 block 尾端加入 footer，然後即可透過 (char *)header - FOOTER_SIZE 的方式來取得前一個 block 的狀態。

![study]({{ site.url }}/assets/images/memory-allocator-8.png)

3. 改善 - 當 block 為 unallocated 狀態時才加入 footer

雖然在 block 尾端加入 footer 是一個不錯的辦法，但是卻會減少可以分配的空間，所以我們調整一下方式，改成只有當 block 為 unallocated 狀態時才加入 footer 值，而 footer 與 payload 空間共用，這樣就不會造成浪費。

![study]({{ site.url }}/assets/images/memory-allocator-11.png)

Advantges

Implicit free list 最大的優點就是易於實作，邏輯相較起來比較簡單。

Problems

花費較多時間在找尋適合的 block

由於 implicit free list 是 allocated 以及 unallocated blocks 混雜在一起，因此在找尋適合大小的 block 時會花費比較多時間。此外，如果我們是使用 first fit 策略(找到第一個有足夠大小的 block 即返回)，那就有可能造成額外的 external fragmenation 問題。但如果改用 best fit策略(找到最適合的大小 block)，那就要遍歷所有的 blocks 進行 size 比較，因此而花費更多尋找時間。

實作

實作部分可以參考 Github allocator-example，這其實是 CS 4400 – Computer Systems 的程式作業XD 而實作結合了上面所提到的三個改善方式。可以透過 make test60 來進行測試。

  1#include <stdint.h>
  2#include <stdio.h> 
  3#include <unistd.h>
  4#include <errno.h>
  5#include <stdbool.h>
  6#include <stdint.h>
  7#include <sys/mman.h>
  8
  9#include "mm.h"
 10
 11typedef uint64_t header;
 12
 13#define HEADER_SIZE sizeof(header)
 14#define ALIGNMENT 16
 15#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
 16#define BLOCK_SIZE(header_ptr) (*(uint64_t *) header_ptr & ~0xF)
 17#define BLOCK_ALLOCATED(header_ptr) (*(uint64_t *) header_ptr & 1)
 18#define BLOCK_FOOTER(header_ptr) ((char *)(header_ptr) + BLOCK_SIZE(header_ptr) - HEADER_SIZE)
 19#define PREV_BLOCK_ALLOCATED(header_ptr) ((*(uint64_t *) header_ptr & 2) >> 1)
 20#define NEXT_BLOCK(header_ptr)((char *)(header_ptr) + BLOCK_SIZE(header_ptr))
 21
 22void *area;
 23
 24void set_header(void *header, int size, bool allocated, bool prev_allocated)
 25{
 26    *(uint64_t *)header = size | allocated | (prev_allocated << 1);
 27}
 28
 29void set_footer(void *footer, int size)
 30{
 31    *(uint64_t *)footer = size;
 32}
 33
 34void mm_init(void *heap, size_t heap_size)
 35{ 
 36  area = heap + HEADER_SIZE;
 37  heap_size = heap_size - 2 * HEADER_SIZE;
 38  set_header(area, heap_size, false, true);
 39  set_header(NEXT_BLOCK(area), 0, true, true);
 40
 41}
 42
 43void *find_free_block(void *heap, size_t size)
 44{
 45    bool allocated;
 46    size_t block_size;
 47    void *block = heap;
 48
 49    while(1)
 50    {
 51        allocated = BLOCK_ALLOCATED(block);
 52        block_size = BLOCK_SIZE(block);
 53
 54        if (block_size == 0)
 55        {
 56            return NULL;
 57        } else if (allocated == true || block_size < size)
 58        {
 59            block = NEXT_BLOCK(block);
 60        } else {
 61            return block;
 62        }
 63    };
 64}
 65
 66void print_fragment(void *heap)
 67{
 68    void *head = heap;
 69    size_t fragment_size;
 70    bool allocated;
 71
 72    while(1)
 73    {  
 74        fragment_size = BLOCK_SIZE(head);
 75        allocated = BLOCK_ALLOCATED(head);
 76
 77        if(fragment_size == 0)
 78        {
 79            break;
 80        }
 81
 82        printf(" [%zu, %d] ", fragment_size, allocated);
 83        head = NEXT_BLOCK(head);
 84    }
 85    printf("\n");
 86}
 87
 88void *mm_malloc(size_t size)
 89{
 90  if (size == 0)
 91  {
 92    return NULL;
 93  }
 94
 95  int aligned_size = ALIGN(size + HEADER_SIZE);
 96  void *block = find_free_block(area, aligned_size);
 97
 98  if (block == NULL)
 99  {
100      printf("space is not enough \n");
101      return NULL;
102  }
103
104  size_t block_size = BLOCK_SIZE(block);
105  
106  size_t remainder_size = block_size - aligned_size;
107
108  if (remainder_size > ALIGN(HEADER_SIZE))
109  {
110    set_header(block, aligned_size, true, PREV_BLOCK_ALLOCATED(block));
111    set_header(NEXT_BLOCK(block), remainder_size, false, true);
112  } else {
113    void *next_header = NEXT_BLOCK(block);
114    set_header(block, BLOCK_SIZE(block), true, PREV_BLOCK_ALLOCATED(block));
115    set_header(next_header, BLOCK_SIZE(next_header), BLOCK_ALLOCATED(next_header), true);
116  }
117
118  return (char *)(block) + HEADER_SIZE;
119}
120
121
122void coalesce_blocks(void *block)
123{
124    size_t size, prev_size, next_size;
125    bool prev = PREV_BLOCK_ALLOCATED(block);
126    bool next = BLOCK_ALLOCATED(NEXT_BLOCK(block));
127
128    size = BLOCK_SIZE(block);
129
130    if (prev == false && next == false)
131    {
132      void *prev_footer = (char *)block - HEADER_SIZE;
133      prev_size = BLOCK_SIZE(prev_footer);
134      next_size = BLOCK_SIZE(NEXT_BLOCK(block));
135
136      void *prev_header = (char *)block - prev_size;
137      int new_size = prev_size + next_size + size;
138      set_header(prev_header, new_size, false, PREV_BLOCK_ALLOCATED(prev_header));
139      set_footer(BLOCK_FOOTER(prev_header), new_size);
140
141      block = prev_header;
142
143    } else if (prev == false)
144    {
145      void *prev_footer = (char *)block - HEADER_SIZE;
146      prev_size = BLOCK_SIZE(prev_footer);
147      void *prev_header = (char *)block - prev_size;
148
149      int new_size = prev_size + size;
150      set_header(prev_header, new_size, false, PREV_BLOCK_ALLOCATED(prev_header));
151      set_footer(BLOCK_FOOTER(prev_header), new_size);
152
153      block = prev_header;
154
155    } else if (next == false)
156    {
157      next_size = BLOCK_SIZE(NEXT_BLOCK(block));
158
159      int new_size = next_size + size;
160      set_header(block, new_size, false, PREV_BLOCK_ALLOCATED(block));
161      set_footer(BLOCK_FOOTER(block), new_size);
162      
163    } else {
164    }
165}
166
167void mm_free(void *payload)
168{
169  if (payload == NULL)
170  {
171      return;
172  }
173  void *header = (char *)payload - HEADER_SIZE;
174  set_header(header, BLOCK_SIZE(header), false, PREV_BLOCK_ALLOCATED(header));
175  
176  void *footer = BLOCK_FOOTER(header);
177  set_footer(footer, BLOCK_SIZE(header));
178
179  void *next = NEXT_BLOCK(header);
180  set_header(next, BLOCK_SIZE(next), BLOCK_ALLOCATED(next), false);
181
182  coalesce_blocks(header);
183}

Note

sbrk() is deprecated

網路上會看到很多範例使用 sbrk ，來延伸 heap 大小，不過卻被人詬病是比較不好的做法，原因是延伸後的 memory range 可能會被使用到 (shared memory)。不過這樣的情形是有機率會出現在 virtual memory 有限的 32 bit 架構上，但對於 virtual memory 很充足的 64 bit 架構來說，每個 process 會有各自的 memory space，不太會發生這樣情形。

針對將 sbrk 換成 mmap 的建議，在A new malloc(3) for OpenBSD 中有提出不錯的看法，而Predictability 是其中一個重要因素，使用 mmap 能夠獲得隨意位置的可用 memory，相對於 sbrk 所產生的連續性記憶位置，更能夠降低因連續位置而造成的潛在問題，例如記憶體位置預測攻擊等。

Minimum alignment of allocation

聽到 alignment 這個詞，可能第一個聯想到 Data structure alignment，由於 CPU 設計，為了讓 CPU 在讀取或寫入 data 時有較好地表現，因此需要 alignment。

而 malloc 也需要 alignment，不過跟上述所提到的 alignment 目的有所不同。以 C libs 的 malloc 來說，64 bits 架構下為 16 bytes alignment，這聽起來有些奇怪，因為依照 Data structure alignment 的概念，64 bits 其實只需要 8 bytes 就好，為何需要到 16 bytes alignment？

在 Minimum alignment of allocation across platforms 文章中有提到此問題，文章中提及過去因為 minimum allocation size 而導致的 crash bug，並且查找各大平台的 minimum alignment 需求皆為 16 bytes alignment on 64-bit，其原因主要是有益於執行效率，例如使用到 SSE instructions 就需要 16-byte-aligned data。