C|內存管理|Memory Allocation
本文續上文，其中提到new在malloc之外做了額外的工作。在這裡我們繼續深入malloc/free。
朝聞君：C++|內存管理|數組內存分配機制
SBRK（break）
從某種意義上來說，heap和stack很接近，也有一個sbrk標識堆頂。在沒有free的情況下，sbrk的行為和rsp很接近，每次申請一塊內存，sbrk增大，增大的部分作為分配的內存。然而，由於free由用戶控制，釋放內存不像棧一樣始終在棧頂，這就造成了複雜度。新分配的內存可能在sbrk附近，也有可能在已經被釋放的內存上。因此，我們malloc時會先尋找是否有已經存在的被釋放的內存，如果沒有，再增加sbrk。
Fragmentation
External Fragmentation
釋放了五個單位的空間，又申請了四個單位的空間，則原空間只能分配一個單位，而不能被更大的分配需求利用。
Internal Fragmentation
記錄的額外空間或者內存對齊，導致零碎的空間產生。
Mechanism
我們把每一個分配的區塊以及其中的信息稱為一個chunk,在表頭我們需要記錄這些信息
記錄分配空間的大小: size（word）
記錄是否被分配： allocation bit（由於size後三位必定為0（word對齊）,因此可以放在size末位）
分配時額外的信息：payload
通過head指針和offset可以計算出下一個chunk，因此堆實際上是隱式鏈表。通過遍歷並求其中的allocation bit，我們可以獲得其中未被分配的內存。
Starategy
First Fit（√）
從頭開始，第一個空間足夠的chunk直接分配:
缺陷： 頭部碎片化
Next Fit
從上次搜索的地址開始，第一個空間足夠的chunk直接分配：
缺陷: 效率更糟糕
Best Fit
整個列表中空間足夠且最小的chunk分配。
缺陷：固定的線性時間
Free
假設我們free了一塊內存，由於malloc造成的碎片化，因此我們需要在free時進行反碎片化，例如附近有未分配的空間，我們應該把未分配的空間合併到一起。由於存儲了size，我們很容易後遍歷，但是向前遍歷就難了。
因此，我們需要額外的信息，讓他成為雙向鏈表，在chunk的最後也存儲一份size+allocation的信息，這樣下一個chunk頭的前一個word就能反查上一個chunk了。
需要注意的是，這裡是不需要考慮循環的，因為free本身保證了free的空間連續，因此只需要考慮上下一塊即可。（參見數學歸納）
如果free的內存在sbrk附近（表尾），那麼直接收縮堆。
Malloc
遍歷尋找可分配的chunk，然後找到size大於需求的，直接修改size+allocation bit即可。這時我們要注意，分配完之後，剩餘的空間可能能容納一個chunk，也可能不能，如果不能的話，我們直接把整塊空間都給malloc，以充分利用空間。
Extension
很明顯，為了避免碎片化，Best Fit是最好的，但是線性遍歷開銷太大。那麼我們自然地想到了查找的數據結構，hash。我們可以把free chunk根據size映射到不同的鏈表，每次free都插入表頭，下次malloc時根據size直接能查到。如此一來，查找的時間變為常數。
不過，由於不再是彼此連續的chunk，原本的size之外又得存儲指針，這也算是典型的時空交換了。
推薦閱讀：
