A pointer to void shall have the same representation and alignment requirements as a pointer to a character type.
A pointer to void may be converted to or from a pointer to any object type. A pointer to any object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.
int *intptr = NULL;
void *dvoidptr = &intptr; /* 6.3.2.3 (1) */
*(void **) dvoidptr = malloc(sizeof *intptr);
int **
轉型為 void *
: void *
轉型為 void **
: void *
為任意型態後,再轉換回原本的型態void *
的設計,導致開發者必須透過 explicit (顯式) 或強制轉型,才能存取最終的 object,否則就會丟出編譯器的錯誤訊息,從而避免危險的指標操作。也就是說,我們無法在 ISO C 中直接對 void *
做數值操作void *p = ...;
void *p2 = p + 1; /* what exactly is the size of void? */
在 GNU C Extension 中,可以對 void * 做數值操作,單位為 1
void *
存在的目的就是為了強迫使用者使用 顯式轉型 或是 強制轉型,以避免 Undefined behavior 產生*ptr
)malloc_stats()
和 malloc_info()
函式,可顯示 process 的 heap 資訊參照 What a C programmer should know about memory (簡記)
The virtual memory allocator (VMA) may give you a memory it doesn’t have, all in a vain hope that you’re not going to use it. Just like banks today
This is how variable-length arrays (VLA), and also alloca() work, with one difference - VLA validity is limited by the scope, alloca’d memory persists until the current function returns (or unwinds if you’re feeling sophisticated).
C99 的 variable length array (VLA) 的運作是因為 stack frame的特性,反正你要多少,stack 在調整時順便加一加。malloc 一樣的原則
有的時候程式會allocate並使用多個不連續的記憶體區塊,如樹狀的資料結構。這時候對於系統來說有幾個問題,一是fragment、二是因為不連續,無法使用cache增快效能。
Linux系統提供一系列的記憶體管理API
Copy-on-write
有些情況是一個process要吃別的process已經map到記憶體的內容,而不要把自己改過的資料放回原本的記憶體。也就是說最終會有兩塊記憶體(兩份資料)。當然每次都複製有點多餘,因此系統使用了Copy-on-write機制。要怎麼做呢?就是在mmap使用MAP_PRIVATE參數即可。
延伸閱讀:
"heap" 的中文翻譯
動態配置產生,系統會存放在另外一塊空間,稱之為 "Heap"。
依據 Why are two different concepts both called "heap"?
Donald Knuth 在《The Art of Computer Programming》(Third Ed., Vol. 1, p. 435) 提到:
Several authors began about 1975 to call the pool of available memory a "heap."
He doesn't say which authors and doesn't give references to any specific papers, but does say that the use of the term "heap" in relation to priority queues is the traditional sense of the word.
一個 data object 具有兩個特性:
data alignment 的意思就是, data 的 address 可以公平的被 1, 2, 4, 8,這些數字整除,從這些數字可以發現他們都是 2 的冪 (power of 2),亦即這些 data object 可以用 1, 2, 4, 8 byte 去 alignment。
CPU 擷取資料時不會一次只抓取 1 byte 的資料,畢竟這樣太慢。假設某個變數的型態為 int
,若 CPU 每次都只抓取 1 byte,就必須要抓 4 次 (int
為 4 byte),效率低落,於是 CPU 通常一次擷取 4 或 8 byte (要看電腦的規格,32 位元的 CPU 一次可讀取 32 bit 的資料,64 位元一次可讀取 64 bit,以此類推),並依序存取。
如果你的資料分布在第 0-3 byte,那麼可以直接取:
但如果你的資料是分布在第 1-4 byte(上圖右側例子),那麼事情就不太一樣了:
可見如果資料位址不在 4 的倍數,會導致存取速度降低,編譯器在分配記憶體時,會按照宣告的型態去做 alignment。
舉個例子,int
的大小普遍為 4 byte,因此普遍做 4 byte alignment,這代表,就算其真正使用的大小只有 1 byte,電腦也會給他 4 byte 的空間,如此一來才能將記憶體位址對齊在 4 的倍數。
struct s1 {
char c;
int a;
};
原本推論 char 為 1 byte,而 int 為 4 byte ,兩個加起來應該為 5 byte,然而實際上為 8 byte,由於 int 為 4 byte ,所以 char 為了要能 alignment 4 byte 就多加了 3 byte 進去 ,使得 cpu 存取速度不會因 address 不是在 4 的倍數上,存取變慢。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _s1 {
char a[5];
} s1;
int main() {
s1 p[10];
printf("struct s1 size: %ld byte\n", sizeof(s1));
for(int i = 0; i < 10; i++) {
printf("the struct p[%d] address =%p\n", i, p + i);
}
}
得到執行結果為
struct s1 size: 5 byte
the struct p[0] address =0x7ffc14c80170
the struct p[1] address =0x7ffc14c80175
the struct p[2] address =0x7ffc14c8017a
the struct p[3] address =0x7ffc14c8017f
the struct p[4] address =0x7ffc14c80184
the struct p[5] address =0x7ffc14c80189
the struct p[6] address =0x7ffc14c8018e
the struct p[7] address =0x7ffc14c80193
the struct p[8] address =0x7ffc14c80198
the struct p[9] address =0x7ffc14c8019d
由於 char type 的 data 大小只佔 1 byte 所以只要 1 byte alignment ,也就是不用使用 padding 讓其變成 4 的倍數。由於編譯器會自動幫我們以 data 的大小做 alignment ,假設有 int type(4 byte) 在配置時,已是 4 byte alignment。
重新設計實驗
#pragma pack(push, 1)
typedef struct _test1 {
char c[3];
int num[256];
} test1;
#pragma pack(pop)
typedef struct _test2 {
char c[3];
int num[256];
} test2;
sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
清除 pagecache、dentries 及 inodes
這段程式碼執行 200 次 看是否平均起來的執行時間相仿
for i in `seq 0 1 200`; do \
echo 3 > /proc/sys/vm/drop_caches ;\
printf "%d," $i;\
./pointer; \
done > clock_gettime.txt
效能分佈:
malloc 本來配置出來的記憶體位置就有做 alignment,根據 malloc 的 man page 裡提到 :
The malloc() and calloc() functions return a pointer to the allocated memory, which is
suitably aligned for any built-in type.
實際上到底 malloc 做了怎樣的 data alignment,繼續翻閱 The GNU C Library - Malloc Example,裡面特別提到:
In the GNU system, the address is always a multiple of eight on most systems, and a multiple of 16 on 64-bit systems.
在大多數系統下,malloc 會以 8 bytes 進行對齊;而在 64-bit 的系統下,malloc 則會以 16 bytes 進行對齊。
對應的實驗,malloc 在 Linux x86_64 以 16 bytes 對齊:
for (int i = 0; i < 10000; ++i) {
char *z;
z = malloc(sizeof(char));
}
結果用 gdb 測過之後,發現位址的結尾的確都是 0 結尾,表示真的是以 16-byte 做對齊。
Unaligned memory access
An unaligned memory access is a load/store that is trying to access an address location which is not aligned to the access size.
e.g: A load instruction trying to access 4 bytes from address 0x1 is an unaligned access. This typically gets split into two internal operations as shows in the following diagram and merges into one.
Note that in case of systems with caches, there can also be cases of addresses crossing a cache line boundary (a.k.a misaligned access) and some times accesses can also be crossing a page boundary.
Then you can also have other complexities like one half of the memory access is hit in cache while the other half is a miss in the cache. The load store execution unit along with cache controllers deals with these complexities but in summary it follows the same basic principle of merging two access
Some architectures (like Intel x86) also has alignment interrupts that help in detecting unaligned memory access.
考慮以下 unaligned_get32
函式的實作: (假設硬體架構為 32-bits)
#include <stdint.h>
#include <stddef.h>
uint8_t unaligned_get8(void *src)
{
uintptr_t csrc = (uintptr_t) src;
uint32_t v = *(uint32_t *) (csrc & 0xfffffffc);
v = (v >> (((uint32_t) csrc & 0x3) * 8)) & 0x000000ff;
return v;
}
uint32_t unaligned_get32(void *src) {
uint32_t d = 0;
uintptr_t csrc = (uintptr_t) src;
for (int n = 0; n < 4; n++) {
uint32_t v = unaligned_get8((void *) csrc);
v = v << (n * 8);
d = d | v;
csrc++;
}
return d;
}
對應的 unaligned_set32
函式:
void unaligned_set8(void *dest, uint8_t value)
{
uintptr_t cdest = (uintptr_t) dest;
uint32_t d = *(uint32_t *) (cdest & 0xfffffffc);
uint32_t v = value;
for (int n = 0; n < 4; n++) {
uint32_t v = unaligned_get8((void *) csrc);
v = v << (n * 8);
d = d | v;
csrc++;
}
return d;
}
void unaligned_set32(void *dest, uint32_t value) {
uintptr_t cdest = (uintptr_t) dest;
for (int n = 0; n < 4; n++) {
unaligned_set8((void *) cdest, value & 0x000000ff);
value = value >> 8;
cdest++;
}
}
參考資料:
這個實作的基礎是 A Pragmatic Implementation of Non-Blocking Linked Lists 這篇論文。
文中首先提到對「天真版」的鏈結串列進行插入與刪除,就算直接用 compare-and-swap 這個最小操作 (atomic operation) 改寫,也沒有辦法保證結果正確。在只有 insert 的狀況下可以成立,但如果加上 delete 的話,如果 insert 跟 delete 發生時機很接近,有可能會發生以下的狀況:
情境是這樣:準備插入 20, 並且刪除 10。這是做到一半的狀況。
delete 做的事情是這樣:
CAS(&(H->next), head_next, head->next->next)
insert 準備執行的動作是這樣:
CAS(&(node_10->next), node_10->next, node_20)
但是兩個 CAS 的動作的先後是無法確定的。如果 insert 的先發生,那結果是正確的。但是如果 delete 的先發生,就會變成下面這個樣子:
結果顯然不正確,因為本來沒有要刪除 20 那個節點。那到底要怎麼辦呢?這篇文章提到一個作法:刪除時不要真的刪除,而是掛一個牌子說「此路段即將刪除」,但是還是過得去,像這樣:
然後等到真的要拆它的時候(比如說需要插入的時候),再把它拆掉。
所以需要有個方法標示「不需要的節點」,然後要有 atomic operation.
不過看了一陣子,發現了幾個問題:為什麼只用位元運算就可以做到「邏輯上」刪除節點?
答案是用 data alignment。首先是 C99 的規格中 6.7.2.1 提到:
Each non-bit-field member of a structure or union object is aligned in an implementation- defined manner appropriate to its type.
Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.
所以這個東西是 implementation-defined. 查看 gcc 的文件 怎麼說:
The alignment of non-bit-field members of structures (C90 6.5.2.1, C99 and C11 6.7.2.1).
Determined by ABI.
先回去翻 C99 的規格,裡面提到關於 intptr_t
這個資料型態:
7.18.1.4 Integer types capable of holding object pointers
The following type designates a signed integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer: intptr_t
所以 intptr_t
是個 integral type, 要至少可以裝得下 pointer
然後對照 /usr/include/stdint.h
, 查到以下內容:
/* Types for `void *' pointers. */
#if __WORDSIZE == 64
# ifndef __intptr_t_defined
typedef long int intptr_t;
# define __intptr_t_defined
# endif
typedef unsigned long int uintptr_t;
#else
# ifndef __intptr_t_defined
typedef int intptr_t;
# define __intptr_t_defined
# endif
typedef unsigned int uintptr_t;
#endif
繼續找 x86_64 ABI,裡面其中一個附表:
然後又說:
因此可推論結構:
typedef intptr_t val_t;
typedef struct node {
val_t data;
struct node *next;
} node_t;
的定址當中,不會發生位址的最後一個 bit 被使用到的狀況(因為都是 4 的倍數 + 必須對齊)。所以就把最後一個 bit 設成 1 當作是刪掉這個節點的 mark. 而把最後一個 bit 設成 0, 就表示恢復原狀。
背景考量: Deterministic Memory Allocation for Mission-Critical Linux
Memory request size
arena 發音為 [əˋrinə]
arena and thread
arena 即為 malloc 從系統取得的連續記憶體區域,分為 main arena 與 thread arena 兩種:
每個 thread 在呼叫 malloc()時,會分配到一個 arena,在開始時 thread 與 arena 是一對一的(per-thread arena),但 arena 的總數有限制,超過時 threads 會開始共用 arena:
此設計是為了減少多 threads 記憶體浪費,但也因此 glibc malloc 不是 lockless allocator,對於有許多 threads 的 server 端程式來說,很有可能影響效能
Heap data structures
Main arena vs Thread arena :
multiple heap Thread arena :
Chunks
Allocated chunk :
Free Chunk:
prev_size : 因兩個 free chunk 會合併,只會出現在 fast bin 的情況下
fast bin 的 chunk 在 free 時不會做合併,只有在 malloc 步驟中的 consolidate fastbin(fast /small bin miss) 才會合併
下一個 chunk 的 PREV_INUSE flag 平時是不 set 的
fd(Forward pointer) : 指向在同一個 bin 中的下一個 chunk
bk(Backward pointer) : 指向在同一個 bin 中的上一個 chunk
Bins
bins 是紀錄 free chunks 的資料結構(freelist),依據其大小和特性分成4種 :
(以下的數值為 32bit 系統,64bit *2)
Fast Bin:
PREV_INUSE
flagUnsorted Bin:
Small Bin:
Large Bin:
Top chunk
在 arena 邊界的 chunk,若所有 bin 皆無法配置則由這裡取得,若仍不夠則用 brk / mmap 延展
Last Remainder Chunk
最近一次分割的 large chunk,被用來滿足 small request 所剩下的部分
malloc 流程
檢查 : 檢查 pointer 位址、alignment、flag 等等,以確認是可 free 的 memory
合併(consolidate)
ref : allocation過程
簡單測試 : malloc(40 * sizeof(int));
Total non-mmapped bytes (arena): 135168
# of free chunks (ordblks): 1
# of free fastbin blocks (smblks): 0
# of mapped regions (hblks): 0
Bytes in mapped regions (hblkhd): 0
Max. total allocated space (usmblks): 0
Free bytes held in fastbins (fsmblks): 0
Total allocated space (uordblks): 176
Total free space (fordblks): 134992
Topmost releasable block (keepcost): 134992