前言

編寫 C 語(yǔ)言代碼時(shí)，指針無(wú)處不在。我們可以稍微額外利用指針，在它們內(nèi)部暗中存儲(chǔ)一些額外信息。為實(shí)現(xiàn)這一技巧，我們利用了數(shù)據(jù)在內(nèi)存中的自然對(duì)齊特性。

內(nèi)存中的數(shù)據(jù)并非保存在任意地址。處理器通常按照其字大小相同的塊讀取內(nèi)存數(shù)據(jù)；那么考慮到效率因素，編譯器會(huì)按照塊大小的整數(shù)倍對(duì)內(nèi)存中的實(shí)體進(jìn)行地址對(duì)齊。因此在 32 位的處理器上，一個(gè) 4 字節(jié)整型數(shù)據(jù)肯定存放在內(nèi)存地址能被4整除的地方。

下面，假設(shè)系統(tǒng)中整型數(shù)據(jù)和指針大小均為 4 字節(jié)。

現(xiàn)在有一個(gè)指向整型的指針。如上所述，整型數(shù)據(jù)可以存放在內(nèi)存地址 0x1000 或者 0x1004 或者 0x1008，但是決不會(huì)存放在 0x1001 或者0x1002 或者 0x1003 或者其他不能被4整除的任何地址。所有是4整數(shù)倍的二進(jìn)制數(shù)都是以 00 結(jié)尾。實(shí)際上，這意味著對(duì)于所有指向整型的指針，它的最后兩位總是 0。

那么有 2 比特沒有承載任何信息。此處的技巧是將我們的數(shù)據(jù)放置到這兩個(gè)比特中，在需要時(shí)使用，并在通過指針解引用來訪問內(nèi)存前刪除它們。

由于 C 標(biāo)準(zhǔn)對(duì)指針位操作的支持不是很好，所以我們將指針保存為一個(gè)無(wú)符號(hào)整型數(shù)據(jù)。

下面是一段簡(jiǎn)短的簡(jiǎn)單代碼片段。完整的代碼查看 github 代碼倉(cāng)庫(kù)中的hide-data-in-ptr。

void put_data(int *p, unsigned int data)
{
	assert(data < 4);
	*p |= data;
}
unsigned int get_data(unsigned int p)
{
	return (p & 3);
}
void cleanse_pointer(int *p)
{
	*p &= ~3;
}
int main(void)
{
	unsigned int x = 701;
	unsigned int p = (unsigned int) &x;
	printf("Original ptr: %un", p);
	put_data(&p, 3);
	printf("ptr with data: %un", p);
	printf("data stored in ptr: %un", get_data(p));
	cleanse_pointer(&p);
	printf("Cleansed ptr: %un", p);
	printf("Dereferencing cleansed ptr: %un", *(int*)p);
	return 0;
}

代碼輸出如下:

Original ptr:  3216722220
ptr with data: 3216722223
data stored in ptr: 3
Cleansed ptr:  3216722220
Dereferencing cleansed ptr: 701

我們可以在指針中存儲(chǔ)任何可以用兩個(gè)比特位表示的數(shù)據(jù)。使用 put_data() 函數(shù)，設(shè)置指針的最低兩位為要存儲(chǔ)的數(shù)據(jù)。該數(shù)據(jù)可以使用get_data() 函數(shù)獲取。此處除了最后兩位所有的位都被覆蓋為零，于是我們隱藏的數(shù)據(jù)就顯示出來。

cleanse_pointer() 函數(shù)將最低兩位置零，保證指針安全地解引用。注意雖然有些 CPU（像 Intel 允許我們?cè)L問未對(duì)齊內(nèi)存地址，但其余 CPU（像 ARM）會(huì)出現(xiàn)訪問錯(cuò)誤。所以，要牢記在解引用前保證指針指向已對(duì)齊內(nèi)存地址。

這在實(shí)際中有應(yīng)用嗎？

是的，有應(yīng)用。查看 Linux 內(nèi)核中紅黑樹的實(shí)現(xiàn)（鏈接：https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h）。

樹的結(jié)點(diǎn)定義如下：

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

此處 unsigned long __rb_parent_color 存儲(chǔ)了如下信息：

父節(jié)點(diǎn)的地址

結(jié)點(diǎn)的顏色

色彩的表示用 0 代表紅色，1 代表黑色。

和前面的例子一樣，該數(shù)據(jù)隱藏在父指針“無(wú)用的”比特位中。

下面看一下父指針和色彩信息是如何獲取的：

/* in rbtree.h */
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
/* in rbtree_augmented.h */
#define __rb_color(pc)  ((pc) & 1)
#define rb_color(rb)  __rb_color((rb)->__rb_parent_color)

內(nèi)存中每一比特都很珍貴，咱們永遠(yuǎn)不要浪費(fèi)?！ū疚淖髡撸?/p>

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論