Linux 核心裡的資料結構——位數組

<a href="https://github.com/torvalds/linux/blob/master/lib/bitmap.c" target="_blank">lib/bitmap.c</a>

<a href="https://github.com/torvalds/linux/blob/master/include/linux/bitmap.h" target="_blank">include/linux/bitmap.h</a>

<a href="https://github.com/torvalds/linux/blob/master/arch/x86/include/asm/bitops.h" target="_blank">arch/x86/include/asm/bitops.h</a>

是以，本部分的主要目的是了解位數組bit array是如何在 linux 核心中實作的。讓我們現在開始吧。

在我們開始檢視<code>位圖</code>操作的 <code>api</code> 之前，我們必須知道如何在 linux 核心中聲明它。有兩種聲明位數組的通用方法。第一種簡單的聲明一個位數組的方法是，定義一個 <code>unsigned long</code> 的數組，例如：

<code>unsigned long my_bitmap[8]</code>

<code>#define declare_bitmap(name,bits) \</code>

<code>unsigned long name[bits_to_longs(bits)]</code>

我們可以看到 <code>declare_bitmap</code> 宏使用兩個參數：

<code>name</code> - 位圖名稱;

<code>bits</code> - 位圖中位數;

并且隻是使用 <code>bits_to_longs(bits)</code> 元素展開 <code>unsigned long</code> 數組的定義。 <code>bits_to_longs</code> 宏将一個給定的位數轉換為 <code>long</code> 的個數，換言之，就是計算 <code>bits</code> 中有多少個 <code>8</code> 位元組元素：

<code>#define bits_per_byte 8</code>

<code>#define div_round_up(n,d) (((n) + (d) - 1) / (d))</code>

<code>#define bits_to_longs(nr) div_round_up(nr, bits_per_byte * sizeof(long))</code>

是以，例如 <code>declare_bitmap(my_bitmap, 64)</code> 将産生：

與：

<code>unsigned long my_bitmap[1];</code>

在能夠聲明一個位數組之後，我們便可以使用它了。

首先讓我們檢視兩個最重要的函數：

<code>set_bit</code>;

<code>clear_bit</code>.

<code>static inline void __set_bit(long nr, volatile unsigned long *addr)</code>

<code>asm volatile("bts %1,%0" : addr : "ir" (nr) : "memory");</code>

正如我們所看到的，它使用了兩個參數：

<code>nr</code> - 位數組中的位号（lctt 譯注：從 0 開始）

<code>addr</code> - 我們需要置位的位數組位址

注意，我們了解了 <code>nr</code> 的用法，但這裡還有一個參數 <code>addr</code> 呢！你或許已經猜到秘密就在 <code>addr</code>。 <code>addr</code>是一個定義在同一個頭檔案中的宏，它展開為一個包含給定位址和 <code>+m</code> 限制的字元串：

<code>#define addr bitop_addr(addr)</code>

<code>#define bitop_addr(x) "+m" (*(volatile long *) (x))</code>

除了 <code>+m</code> 之外，在 <code>__set_bit</code> 函數中我們可以看到其他限制。讓我們檢視并試着了解它們所表示的意義：

<code>+m</code> - 表示記憶體操作數，這裡的 <code>+</code> 表明給定的操作數為輸入輸出操作數；

<code>i</code> - 表示整型常量；

<code>r</code> - 表示寄存器操作數

除了這些限制之外，我們也能看到 <code>memory</code> 關鍵字，其告訴編譯器這段代碼會修改記憶體中的變量。到此為止，現在我們看看相同的原子性atomic變體函數。它看起來比非原子性non-atomic變體更加複雜：

<code>static __always_inline void</code>

<code>set_bit(long nr, volatile unsigned long *addr)</code>

<code>if (is_immediate(nr)) {</code>

<code>asm volatile(lock_prefix "orb %1,%0"</code>

<code>: const_mask_addr(nr, addr)</code>

<code>: "iq" ((u8)const_mask(nr))</code>

<code>: "memory");</code>

<code>asm volatile(lock_prefix "bts %1,%0"</code>

<code>: bitop_addr(addr) : "ir" (nr) : "memory");</code>

（lctt 譯注：bitop_addr 的定義為：<code>#define bitop_addr(x) "=m" (*(volatile long *) (x))</code>，orb 為位元組按位或。）

<code>#define __always_inline inline __attribute__((always_inline))</code>

<code>#define is_immediate(nr) (__builtin_constant_p(nr))</code>

<code>#define const_mask_addr(nr, addr) bitop_addr((void *)(addr) + ((nr)>>3))</code>

展開為帶有到包含給定位的位元組偏移的給定位址，例如，我們擁有位址 <code>0x1000</code> 和位号 <code>0x9</code>。因為 <code>0x9</code> 代表 <code>一個位元組 + 一位</code>，是以我們的位址是 <code>addr + 1</code>:

<code>const_mask</code> 宏将我們給定的位号表示為位元組，位号對應位為高位 <code>1</code>，其他位為 <code>0</code>：

<code>#define const_mask(nr) (1 << ((nr) & 7))</code>

最後，我們應用 <code>按位或</code> 運算到這些變量上面，是以，假如我們的位址是 <code>0x4097</code> ，并且我們需要置位号為<code>9</code> 的位為 1：

<code>第 9 位</code> 将會被置位。（lctt 譯注：這裡的 9 是從 0 開始計數的，比如0010，按照作者的意思，其中的 1 是第 1 位）

<code>static inline void __clear_bit(long nr, volatile unsigned long *addr)</code>

<code>asm volatile("btr %1,%0" : addr : "ir" (nr));</code>

<code>__clear_bit</code> 的原子性變體為 <code>clear_bit</code>：

<code>clear_bit(long nr, volatile unsigned long *addr)</code>

<code>asm volatile(lock_prefix "andb %1,%0"</code>

<code>: "iq" ((u8)~const_mask(nr)));</code>

<code>asm volatile(lock_prefix "btr %1,%0"</code>

<code>: bitop_addr(addr)</code>

并且正如我們所看到的，它與 <code>set_bit</code> 非常相似，隻有兩處不同。第一處差異為 <code>clear_bit</code> 使用 <code>btr</code> 指令來清位，而 <code>set_bit</code> 使用 <code>bts</code> 指令來置位。第二處差異為 <code>clear_bit</code> 使用否定的位掩碼和 <code>按位與</code>在給定的位元組上置位，而 <code>set_bit</code> 使用 <code>按位或</code> 指令。

到此為止，我們可以在任意位數組置位和清位了，我們将看看位掩碼上的其他操作。

<code>#define test_bit(nr, addr) \</code>

<code>(__builtin_constant_p((nr)) \</code>

<code>? constant_test_bit((nr), (addr)) \</code>

<code>: variable_test_bit((nr), (addr)))</code>

是以，如果 <code>nr</code> 是編譯期已知常量，<code>test_bit</code> 将展開為 <code>constant_test_bit</code> 函數的調用，而其他情況則為 <code>variable_test_bit</code>。現在讓我們看看這些函數的實作，讓我們從 <code>variable_test_bit</code> 開始看起：

<code>static inline int variable_test_bit(long nr, volatile const unsigned long *addr)</code>

<code>int oldbit;</code>

<code>asm volatile("bt %2,%1\n\t"</code>

<code>: "=r" (oldbit)</code>

<code>: "m" (*(unsigned long *)addr), "ir" (nr));</code>

<code>return oldbit;</code>

<code>constant_test_bit</code> 函數做了和我們在 <code>set_bit</code> 所看到的一樣的事：

<code>static __always_inline int constant_test_bit(long nr, const volatile unsigned long *addr)</code>

<code>return ((1ul << (nr & (bits_per_long-1))) &</code>

<code>(addr[nr >> _bitops_long_shift])) != 0;</code>

下一個被廣泛使用的位數組相關操作是改變一個位數組中的位。為此，linux 核心提供了兩個輔助函數：

<code>__change_bit</code>;

<code>change_bit</code>.

你可能已經猜測到，就拿 <code>set_bit</code> 和 <code>__set_bit</code> 例子說，這兩個變體分别是原子和非原子版本。首先，讓我們看看 <code>__change_bit</code> 函數的實作：

<code>static inline void __change_bit(long nr, volatile unsigned long *addr)</code>

<code>asm volatile("btc %1,%0" : addr : "ir" (nr));</code>

<code>__change_bit</code> 的原子版本為 <code>change_bit</code> 函數：

<code>static inline void change_bit(long nr, volatile unsigned long *addr)</code>

<code>asm volatile(lock_prefix "xorb %1,%0"</code>

<code>: "iq" ((u8)const_mask(nr)));</code>

<code>asm volatile(lock_prefix "btc %1,%0"</code>

它和 <code>set_bit</code> 函數很相似，但也存在兩點不同。第一處差異為 <code>xor</code> 操作而不是 <code>or</code>。第二處差異為<code>btc</code>（ lctt 譯注：原文為 <code>bts</code>，為作者筆誤）而不是 <code>bts</code>。

目前，我們了解了最重要的體系特定的位數組操作，是時候看看一般的位圖 api 了。

首先我們看看以下 4 個宏：

<code>for_each_clear_bit</code>

<code>for_each_clear_bit_from</code>

所有這些宏都提供了周遊位數組中某些位集合的疊代器。第一個宏疊代那些被置位的位。第二個宏也是一樣，但它是從某一個确定的位開始。最後兩個宏做的一樣，但是疊代那些被清位的位。讓我們看看<code>for_each_set_bit</code> 宏：

<code>#define for_each_set_bit(bit, addr, size) \</code>

<code>for ((bit) = find_first_bit((addr), (size)); \</code>

正如我們所看到的，它使用了三個參數，并展開為一個循環，該循環從作為 <code>find_first_bit</code> 函數傳回結果的第一個置位開始，到小于給定大小的最後一個置位為止。

<code>bitmap_zero</code>;

<code>bitmap_fill</code>.

它們分别可以清除一個位數組和用 <code>1</code> 填充位數組。讓我們看看 <code>bitmap_zero</code> 函數的實作：

<code>static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)</code>

<code>if (small_const_nbits(nbits))</code>

<code>unsigned int len = bits_to_longs(nbits) * sizeof(unsigned long);</code>

<code>memset(dst, 0, len);</code>

<code>#define small_const_nbits(nbits) \</code>

<code>(__builtin_constant_p(nbits) && (nbits) <= bits_per_long)</code>

<code>bitmap_fill</code> 函數的實作和 <code>biramp_zero</code> 函數很相似，除了我們需要在給定的位數組中填寫 <code>0xff</code> 或<code>0b11111111</code>：

<code>static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)</code>

<code>unsigned int nlongs = bits_to_longs(nbits);</code>

<code>if (!small_const_nbits(nbits)) {</code>

<code>unsigned int len = (nlongs - 1) * sizeof(unsigned long);</code>

<code>memset(dst, 0xff, len);</code>

<code>dst[nlongs - 1] = bitmap_last_word_mask(nbits);</code>

原文釋出時間為：2016-08-23

本文來自雲栖社群合作夥伴“linux中國”

Linux 核心裡的資料結構——位數組

繼續閱讀

Apache (You don't have permission to access / on this server.）

debian9更新4.9.0核心到4.19.2核心過程

centOS7 配置 vsftpd 虛拟使用者及權限Vsftpd配置虛拟使用者及權限

linux-svn解除安裝與安裝

vsftp虛拟多使用者多權限一鍵部署腳本

Ubuntu14.04 LTS下安裝mongodb

httpd服務的部署、啟動、配置和簡單優化一、部署二、啟動三、配置檔案

配置網頁内容通路

手動安裝Intel network I217-LM網卡的Linux驅動

禁止ubuntu系統彈出報錯界面

Ubuntu Linux下Apache的配置檔案

samba伺服器的功能

【Linux】UDP廣播封包接收速率問題

Linux裝置模型（中）之上層容器

PowerPC平台 Linux移植三