關於 Aligned Memory Allocation

起源

由於在這個東西上吃了大悶虧，至於是什麼虧就不細究了，總之是我當初在看到這東西的時候沒有認真摸透，就趁著這個機會好好還債了我想要用一個超級白話的方式讓人快速可以理解，下次遇到這個議題再回來看就能快速回憶起來

什麼是 Aligned Memory Allocation？

設想一個情況，今天程式運行到一個地方，如果我需要一些額外的記憶體來儲存新的資料，在 C 語言中我們一定會用到 malloc() 來跟系統要額外的記憶體空間

舉個例子，我現在突然需要 32 bytes 的空間，所以我就使出 malloc()，然後系統就翻啊翻找啊找，最後在記憶體中找到了 32 bytes 的空間，並把起始的記憶體位置傳回來。這個起始的位置可能很隨機，像是 0x08004321，不過這也無傷大雅，總之我現在有了 32 bytes 空間，我現在想對他幹嘛就幹嘛。

然而然而，在某些情況（至於是哪些情況後面再講），我們會希望我們得到的記憶體的起始位置是「對齊」的。那什麼叫做對齊呢？

舉個例子，如果你用一些 Hex 檔案的預覽工具，你會看到左邊的起始位置很整齊以 32 bytes 間隔，像下面這樣：

1
2
3
4
5
6
7
8
9
一般隨機分配 (未對齊):
0x08004321  |  Data...
            ^ 起始位置很隨意

32-byte Alignment (對齊):
0x08000000  |  Data...
0x08000020  |  Data...  <-- 0x20 就是 32
0x08000040  |  Data...  <-- 0x40 就是 64
            ^ 起始位置都可以被 32 整除

所謂的 Aligned Memory Allocation，就是我在要新的記憶體空間時，想要拿到一個起始位置可以被 32（或是其他數字）整除的記憶體空間

OK，所以說到這邊應該對這個 Aligned Memory Allocation 是什麼應該有點概念了，這樣就成功了一半了。因為大多數人第一次聽到應該都比較難想到這是什麼，又或者知道這是什麼，但不知道有什麼用

所以，這個有什麼用呢？

為什麼需要 Alignment？

會需要 Alignment 大多是受到硬體設計的限制，例如：

向量指令集 (如 AVX)，當執行這類指令集的時候，會要求目標的記憶體位置是對齊的，沒有對齊的話得要拆成兩步去處理，或是直接出現錯誤，那為什麼不設計成指令集可以讀取任意位置起始的記憶體呢？我覺得大多是成本考量，如果能從驅動程式端去解決，又何必浪費昂貴的硬體空間呢

其他像是 CUDA 中 GPU 透過 PCIe 抓取資料時，使用 DMA 也會要求記憶體要對齊，又或者 GPU 指令抓取他自己記憶體的資料也會要求對齊，另外在 STM32 這類單晶片上使用 DMA 時，buffer 的記憶體位置也會要求對齊，才能夠被 DMA 正確寫入或讀取

這時候一定有人跳出來說：「我平常用 CUDA 或是在 STM32 上用 DMA 都沒遇到這問題啊！」

那是因為 CUDA driver 或是 HAL library 之類的會幫你處理好，所以當然沒感覺，反過來說，如果你今天寫的是 driver 或是 bare metal 開發，那一定要小心記憶體對齊這東西，不然可能連動都動不起來

所以該怎麼做到 Alignment？

前面說了這麼多，那要怎麼才能做到記憶體分配時 Alignment 呢？

設想今天我們目標要一塊新的 64 bytes 記憶體，並且要求 32-byte 對齊。如果今天 malloc 給的起始位置剛剛好就是 0x08000040，是 alignment block 的起始位置，這樣就中大獎了，但實際上當然不會那麼幸運，他可能給你的起始位置是 0x08000041（偏移了 1 個 byte），也可能起始是 0x0800005F（偏移了 31 個 bytes）

但沒關係，這時候就會想到，只要malloc的記憶體夠長，從中找到一個 Alignment Block 的起點並從那邊開始存資料，這樣也算對齊吧

那麼問題就回到，我們該要多長的記憶體呢？觀察前面的例子，如果做 32 bytes 的 alignment，偏移的量最多就是 0 ~ 31 bytes。所以我們要 malloc() 的空間至少要是 size + alignment - 1

等等，好像少了什麼？這樣的話要怎麼才能 free 掉 alignment 起始位址前面的那些空間呢？我們需要紀錄真正原本 malloc 出來的起始位址，所以還需要再多一個位置去存這個指標，這個需要的空間是 sizeof(void*)

總結來說，我們真正要 malloc() 的長度是： size + alignment - 1 + sizeof(void*)

記憶體結構示意圖：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
實際 malloc 得到的區塊 (Original)
|
v
+-------------+---------------------+-------------------------+
| padding ... | 原始指標 (Stored)   | 使用者拿到的指標 (Aligned)|
+-------------+---------------------+-------------------------+
              ^                     ^
              |                     |
              這格存著 original     符合 32-byte 對齊
              的地址                我們回傳這個地址

然後我們只要找到這裡面 alignment 的起始位址，並且把「原始的起始位址」存在 alignment 起始的前一格。這樣在 free memory 時，只要從 alignment 位址往前找一格，就可以找到我們應該要釋放的記憶體起點。

原理概念上就是這樣了，那麼就來看看要怎麼實作吧。

C 語言實作

以下用 32-byte alignment 為例子，可以把 32 換成任意想要的正整數 alignment（通常是 2 的次方）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdlib.h>
#include <stdint.h> // 為了使用 uintptr_t

void* aligned_malloc(size_t size) {
    // 1. 計算需要的總空間：
    //    size + (alignment - 1) 的調整空間 + 存放原始指標的空間
    void *original = malloc(size + 32 - 1 + sizeof(void*));
    
    if (!original) return NULL;

    // 2. 算出 alignment 的起始位置
    //    先預留一個 pointer 的空間給我們存地址
    uintptr_t raw = (uintptr_t)original + sizeof(void*);
    
    //    利用 Bitwise 操作進行對齊
    //    原理：(address + mask) & ~mask
    //    注意：這裡要用 ~(32 - 1) 也就是 ~31 才能遮掉後五位達到 32 對齊
    uintptr_t aligned = (raw + (32 - 1)) & ~(32 - 1);
    
    //    其實也可以用(void*)(original - (original % 32));去算
    //    只是用bit manipulation感覺比較優雅

    // 3. 把原本 malloc() 的起始位址存到 alignment 位址的前一格
    ((void**)aligned)[-1] = original;

    // 4. 最後回傳 alignment 的起始
    return (void*)aligned;
}

void aligned_free(void *ptr) {
    if (!ptr) return;
    
    // free 的時候，去找到 alignment 位址前一格存的原來 malloc 的位址
    void *original = ((void**)ptr)[-1];
    
    // 然後把它釋放就行了
    free(original);
}

結語

總之就是這樣，Aligned Memory Allocation這個東西重要又有一些實作小細節，藉由這個機會算是有搞懂他了，以後忘了也可以快速回來複習一下

起源

什麼是 Aligned Memory Allocation？

為什麼需要 Alignment？

所以該怎麼做到 Alignment？

C 語言實作

結語

Reference