# Dynamically allocate space Note
---
自幹一個普通的malloc
---
* 最普通的malloc實做，就是sbrk(size)，增加sbrk來得到記憶體，然後因爲sbrk是回傳原本的起始位置：
* sbrk(0)回傳heap的終點
* sbrk(size)回傳(目前的終點位置-size)，就是增加size之前的終點位置
```c=
void *malloc(size_t size)
{
void *ptr = sbrk(size);
if(!ptr)
return NULL; //sbrk failed
else
return ptr;
}
```
接下來，來談一談free的部分，爲了確保heap裏面的記憶體是連續的，所以不能隨便將中間的記憶體還給OS。因此需要一個東西來確認說，heap裏的某個部分的記憶體是否爲free。有了這個機制就能確保在free後，heap裏的記憶體還是連續的。
還有另一個好處就是每次在進行malloc時不需要動到sbrk，而是只需去到heap裏尋找能否有空閒且足夠的記憶體就行了，也就是所謂的重用機制。
爲了這個機制，我們需要一個結構在每塊記憶體的前面，size用來知道這塊block meta所管理的記憶體大小，next則連接到下一塊block meta，然後我們需要一個指標==global_base==來記錄頭節點：
```c=
typedef struct __BLOCK_META {
size_t size; // 這塊block meta後面的記憶體大小
struct __BLOCK_META *next; //連接到下一塊block meta
int free; //是否爲free
}block_meta
#define META_SIZE sizeof(block_meta)
void *global_base = NULL; // 記錄頭節點
```
每塊記憶體前面都必須要有這塊block meta，因此每次malloc時都需要更動爲：
```c=
sbrk(size + META_SIZE)
```
接下來，來實做一個在所有block裏尋找能否使用的空間，last用來記錄最後的block在哪裏（看下個實做）：
```c=
block_meta *find_free_block(block_meta **last, size_t size)
{
block_meta *cur = global_base;
while (cur && !(cur->free && cur->size >= size)) {
*last = cur;
cur = cur->next;
}
return cur;
}
```
如果在目前的heap中找不到一塊空閒且足夠大小的空間，那就必須申請sbrk增加heap的大小了，在上面的`find_free_block`時已經將last找到了，因此申請新的block時，只需將last跟block連接在一起就好：
```c=
block_meta *request_space(block_meta *last, size_t size)
{
block_meta *block;
block = sbrk(0);
void *request = sbrk(size + META_SIZE);
assert((void*)block == request); // Not thread safe.
if (request == (void*)-1)
return NULL; //sbrk failed
if (last) // 第一次malloc時last爲空，不需要連接
last->next;
block->size = size;
block->next = NULL; //新的一塊，最後面的
block->free = 0;
return block;
}
```
準備工作都完成了，最後利用上面的function來實做malloc本身吧，malloc(0)爲了在free時可以安全通過，因此每次malloc(0)都回傳一個NULL。：
```c=
void *malloc(size_t size)
{
if(size <= 0)
return NULL;
block_meta block;
if(!global_base) { //第一次malloc
block = request_space(NULL,size);
if (!block)
return NULL;
global_base = block;
}
else {
block_meta *last = global_base;
block = find_free_block(&last, size);
if (!block) { //尋找失敗，申請sbrk
block = request_space(last, size);
if (!block)
return NULL;
}
else //尋找成功，設定block爲unfree
block->free = 0;
}
/* block的大小爲block_meta size
因此block+1 = block+META_SIZE
回傳的記憶體不需要包括meta information */
return (block+1);
}
```
這樣一個普通簡單的malloc就大功告成了。
---
malloc完成後，再來是實做free的部分，很簡單，就是得到記憶體前面的那塊block_meta，然後設定free爲true就可：
```c=
block_meta *get_meta_block(void *ptr)
{
return ((block_meta*)ptr - 1);
}
void free(void *ptr)
{
if (!ptr) //之前如果malloc<=0，就會回傳NULL
return NULL;
block_meta *block = get_meta_block(ptr);
block->free = 1;
}
```
這樣free的部分就完成了。
---
最後，來看看關於realloc跟calloc的部分。
* calloc
* 很簡單，就是利用memset，將malloc的記憶體初始化爲0
* realloc
* 如果realloc的大小是減少，那就不動它
* 如果realloc的大小是增加原本的，那就malloc一塊新的給它，然後利用memcpy將之前的資料copy去新的記憶體區塊
```c=
/* nelem 爲要allocate的數量，elsize爲每塊數量的大小 */
void *calloc(size_t nelem, size_t elsize)
{
size_t size = nelem * elsize;
void *ptr = malloc(size);
memset(ptr, 0, size);
return ptr;
}
```
```c=
void *realloc(void *ptr, size_t size)
{
if (!ptr)
return malloc(size);
block_meta *block = get_meta_block(ptr);
if (block->size <= size)
return ptr;
void *new_ptr;
new_ptr = malloc(size);
if (!new_ptr)
return NULL;
memcpy(new_ptr, ptr, sizeof(block->size));
free(ptr);
return new_ptr;
}
```
參考資料：
* [malloc tutorial](http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf)
* [A quick tutorial on implementing malloc, free, calloc, and realloc](http://danluu.com/malloc-tutorial/)
---
## Two-Level Segregated Fit (TLSF) 論文閱讀
[TLSF: a New Dynamic Memory Allocator for Real-Time Systems∗](http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf)
#### DSA algorithms
* Sequential fit
* 不做任何規劃，將所有free或是nonfree的block用linked list連接起來。在RTSs的系統下是非常沒有效率的，因爲尋找free block需要拜訪所有block（worst case）
* Segregated Free Lists:
* 利用一個array list保管不同大小的free blocks。當一個block被釋放後，它會根據自己的size被加入到對應的array位置。這種做法是邏輯上的segregate而不是物理上的（就是實際上它們並沒有分離，只是在邏輯上看起來是分離了）。有兩種：Simple Segregated Storage and Segregated Fits。對RTOSs的系統來說挺不錯的，因爲不需要拜訪每個block
*
## TIPS:
* 每次通過sbrk申請時要加上meta information，賦值給meta information後，只需要回傳meta information後的第一個位置，後面就是申請malloc的大小
* DSA algorithm has to minimise the chance of exhausting the memory pool by minimising the amount of fragmetation and wasted memory. 爲了減少memory pool耗盡的可能性，DSA必須降低fragmentation跟避免記憶體被浪費
* 有兩種memory allocation會失敗的原因：
* 超出系統的記憶體範圍
* DSA演算法在freelist找不到合適的區塊來重用
* internal fragmentation
* external fragmentation
* Fragementation的結論：
* “the fragmentation problem is really a problem of poor allocator implementations”
* best-fit 跟 physical first-fit 可以減少fragmentation
* 每塊記憶體應該要在釋放的時候合並
* 優先選擇最近的被釋放的記憶體，然後才到很久前被釋放
* 計算First level bin的時候取：下高斯[log2(size)]。
* 只需要計算最後的1,前面有幾個bit就好了。
```
size = 460 = 0000 0001 1100 1100
最高位的1爲9, 而2^9 = 512，一定超過460,所以取8
```
Sign in with Wallet
Connect another wallet