# Custom memory allocators 研讀筆記
[Custom memory allocators](https://www.rastergrid.com/blog/sw-eng/2021/03/custom-memory-allocators/) 製作自訂記憶體配置器

首先我最擔心的即是整個記憶體配置器的複雜度，但研讀完文章發現其實現在記憶體配置器的分工十分明確，所謂的自訂記憶體配置器只是在記憶體配置器的階層中插入一個元件，這個元件負責接收上一層的記憶體配置器元件並作操作：
- `allocate`：預定子分區的地址範圍
- `deallocate`：釋放子分區的地址範圍
- `resize`：可選項，用於調整已 `allocate` 的子分區的地址範圍大小，較難作的有效率。
目標是針對特地的應用製作專屬的自訂記憶體配置器，而非製作通用的記憶體配置器。


## LIFO allocator
我們會用 stack 時作分配器，因為戲通呼叫的堆積所請求的記憶體大小是固定的，但是在 [C99 standard](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 支援[可變長度陣列](https://en.wikipedia.org/wiki/Variable-length_array)可以在運作時動態分配記憶體，我們只需要一塊預定好的記憶體範圍和用來指向可用範圍的指標。
- 優點是分配和釋放記憶體都是常數時間
- 缺點是預定好的記憶體範圍可能太小，

但是我們可以裁取虛擬記憶體的策略，分配極大空間，但只按需使用已經分配的空間。
- 即使如此預定好的記憶體範圍上限依然是重要的，因為即使上一層記憶體配置器元件 `resize` 也不一定可以順利動態分配更多記憶體給預定好的記憶體範圍。

另一個方法是使用鏈結串列連結多個可用記憶體空間，維持一條分區鏈（chain of partitions），當新的記憶體分配請求來時，如果目前的分區（partition）已滿，就配置一個新的分區，然後將其鏈結到現有的分區結構中。
這樣，每個新的分區都像是一個新的「記憶體塊」，形成一條鏈，形成兩層堆疊（stack of stacks）：

第一層堆疊（first-level stack）：管理整個記憶體分區的鏈結。
第二層堆疊（second-level stack）：管理每個分區內的子區塊（sub-partitions）。

但記憶體分配策略需要在記憶體使用量、效能、靈活性之間做出權衡。

## FIFO allocator
先進先出分配器適合用來管理始放順序和執行順序相同的應用，像網路封包，多執行緒等等。
先進先出分配器除了可以使用以上的優化策略之外還可以使用環狀結構管理但缺點就是會導致碎片化，這個問題可以使用分配雙倍的虛擬記憶體改善讓虛擬記憶體看起來是連續的。分配給先進先出分配器的每個子區塊的大小只需要等於管道中任何單個階段所需的最大記憶體大小，這樣可以節省空間。

此外可以針對每一個分支都分配一個先進先出分配器，但這導致的問題就是需要額外的開銷來管理每個分配器，所以是成本和彈性的權衡。

## Size constrained allocators
前面的兩個例子都是透過限制分配器的彈性換取效率，例：如先進先出，先進後出。而大小受限分配器是透過限制子區塊大小換取效率，在應用中常常遇到分配/釋放具有特定大小的相同類型的物件實例。這樣的分配器稱為 memory pool。

而 memory pool 的管理只需要使用預先分配一塊記憶體區塊來存放多個固定大小的物件，並維護一個單向鏈表來追蹤這些可用的區塊，即可利用常數時間取出所需的記憶體子區塊，並且使用常數時間釋放。


這樣的自定義分配器可以輕鬆擴展，支持任意數量的物件。具體方法是使用兩層單向鏈表，其中第一層鏈表包含未滿的區塊，而第二層鏈表包含可用的單個區塊。當然，如果我們希望支持動態增長或縮小分區數量，那麼我們仍然需要向底層記憶體分配器發出分區分配/釋放請求，但大多數請求仍然可以在常數時間內處理。

### 實作重點
在實作上管理 free chunk 的結構和 free chunk 最好分開擺放保持記憶體空間連續。而一次分配多個 free chunk 實這些 free chunk 最好要是連續的，有時是必須連續為此需要更複雜的策略可能導致無法用常數時間完成分配，但也會接近常數時時間因為操作時間會分攤在各個 free chunk 分配中。

#### 多線程的考量
以下文章中探討到多線程的 Size constrained allocators 管理：
- 可以使用 lockless 鏈結串列保證 atomic 操作。
- 或使用每個線程使用自己的 Size constrained allocators。

#### 位元操作代替鏈結串列
此外位元操作是鏈結串列之外另一個用來管理 free chunk 的方法，在連續範圍的記憶體區叧中十分高效。當需要或偏好支持在連續記憶體中保留多個插槽時，這通常是首選的實現方法，因為使用位元掩碼可以快速找到連續的插槽並將它們保留。

#### 多物件大小的 memory pool


支持單一大小物件的單一池分配器通常不足以滿足需求。
- 可以為每個所需的物件大小使用多個池分配器，儘管這也會帶來額外的記憶體使用，就像為每個線程使用單獨的分配器一樣。
- 另外，也可以創建一個池分配器，允許從相同的區塊中服務多個物件大小的請求。顯然，這樣會有性能成本，但如果解決方案構造得當，成本可以限制在需要支持的不同大小數量的對數範圍內。

第二個策略引出了另一種常見的分配策略，也作業系統核心用於大規模的子分配： buddy allocator。buddy allocator 算法是一種分配方案，通常將大小為二次方的分區不斷分割為兩半，嘗試提供最佳匹配。控制結構實際上是一棵二元樹，每個子節點包含表示其父節點的記憶體區域前後兩半的節點。

嚴格來說，buddy allocator 只能以最小區塊大小的 2 的冪次倍來分配/釋放區塊
- 但它也可以用作通用的分配器來分配任意大小的區塊。
- 這種分配方案會產生顯著的內部碎片。

實現中通常會使用陣列來表示二元樹，這樣可以提高效率，並且可以根據預定的分區大小和最小分配大小來靜態分配內存。與早期的分配器類似，動態容量可以通過維護這些樹的鏈表來支持。

## Count constrained allocators
Size constrained allocators 是專注限制子分區個別大小，Count constrained allocators 專注於限制最大分配數量的例子。...**待補完**