Linux 內核里的數據結構——位數組

除了不同的基於鏈式和樹的數據結構以外，Linux 內核也為位數組（或稱為 點陣圖 （ bitmap ） ）提供了 API。位數組在 Linux 內核里被廣泛使用，並且在以下的源代碼文件中包含了與這樣的結構搭配使用的通用 API：

• lib/bitmap.c
• include/linux/bitmap.h

除了這兩個文件之外，還有體系結構特定的頭文件，它們為特定的體系結構提供優化的位操作。我們將探討 x86_64 體系結構，因此在我們的例子里，它會是

• arch/x86/include/asm/bitops.h

頭文件。正如我上面所寫的，點陣圖在 Linux 內核中被廣泛地使用。例如，位數組常常用於保存一組在線/離線處理器，以便系統支持熱插拔的 CPU（你可以在 cpumasks 部分閱讀更多相關知識 ），一個 位數組 （ bit array ） 可以在 Linux 內核初始化等期間保存一組已分配的中斷處理。

因此，本部分的主要目的是了解 位數組 （ bit array ） 是如何在 Linux 內核中實現的。讓我們現在開始吧。

位數組聲明

在我們開始查看點陣圖操作的 API 之前，我們必須知道如何在 Linux 內核中聲明它。有兩種聲明位數組的通用方法。第一種簡單的聲明一個位數組的方法是，定義一個 unsigned long 的數組，例如：

unsigned long my_bitmap[8]

第二種方法，是使用 DECLARE_BITMAP 宏，它定義於 include/linux/types.h 頭文件：

#define DECLARE_BITMAP(name,bits) 
    unsigned long name[BITS_TO_LONGS(bits)]

我們可以看到 DECLARE_BITMAP 宏使用兩個參數：

• name - 點陣圖名稱;
• bits - 點陣圖中位數;

並且只是使用 BITS_TO_LONGS(bits) 元素展開 unsigned long 數組的定義。 BITS_TO_LONGS 宏將一個給定的位數轉換為 long 的個數，換言之，就是計算 bits 中有多少個 8 位元組元素：

#define BITS_PER_BYTE           8
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

因此，例如 DECLARE_BITMAP(my_bitmap, 64) 將產生：

>>> (((64) + (64) - 1) / (64))
1

與：

unsigned long my_bitmap[1];

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

體系結構特定的位操作

我們已經看了上面提及的一對源文件和頭文件，它們提供了位數組操作的 API。其中重要且廣泛使用的位數組 API 是體系結構特定的且位於已提及的頭文件中 arch/x86/include/asm/bitops.h。

首先讓我們查看兩個最重要的函數：

• set_bit;
• clear_bit.

我認為沒有必要解釋這些函數的作用。從它們的名字來看，這已經很清楚了。讓我們直接查看它們的實現。如果你瀏覽 arch/x86/include/asm/bitops.h 頭文件，你將會注意到這些函數中的每一個都有原子性和非原子性兩種變體。在我們開始深入這些函數的實現之前，首先，我們必須了解一些有關 原子 （ atomic ） 操作的知識。

簡而言之，原子操作保證兩個或以上的操作不會並發地執行同一數據。x86 體系結構提供了一系列原子指令，例如， xchg、cmpxchg 等指令。除了原子指令，一些非原子指令可以在 lock 指令的幫助下具有原子性。現在你已經對原子操作有了足夠的了解，我們可以接著探討 set_bit 和 clear_bit 函數的實現。

我們先考慮函數的 非原子性 （ non-atomic ） 變體。非原子性的 set_bit 和 clear_bit 的名字以雙下劃線開始。正如我們所知道的，所有這些函數都定義於 arch/x86/include/asm/bitops.h 頭文件，並且第一個函數就是 __set_bit:

static inline void __set_bit(long nr, volatile unsigned long *addr)
{
    asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
}

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

• nr - 位數組中的位號（LCTT 譯註：從 0 開始）
• addr - 我們需要置位的位數組地址

注意，addr 參數使用 volatile 關鍵字定義，以告訴編譯器給定地址指向的變數可能會被修改。 __set_bit 的實現相當簡單。正如我們所看到的，它僅包含一行內聯彙編代碼。在我們的例子中，我們使用 bts 指令，從位數組中選出一個第一操作數（我們的例子中的 nr）所指定的位，存儲選出的位的值到 CF 標誌寄存器並設置該位（LCTT 譯註：即 nr 指定的位置為 1）。

注意，我們了解了 nr 的用法，但這裡還有一個參數 addr 呢！你或許已經猜到秘密就在 ADDR。 ADDR 是一個定義在同一個頭文件中的宏，它展開為一個包含給定地址和 +m 約束的字元串：

#define ADDR                BITOP_ADDR(addr)
#define BITOP_ADDR(x) "+m" (*(volatile long *) (x))

除了 +m 之外，在 __set_bit 函數中我們可以看到其他約束。讓我們查看並試著理解它們所表示的意義：

• +m - 表示內存操作數，這裡的 + 表明給定的操作數為輸入輸出操作數；
• I - 表示整型常量；
• r - 表示寄存器操作數

除了這些約束之外，我們也能看到 memory 關鍵字，其告訴編譯器這段代碼會修改內存中的變數。到此為止，現在我們看看相同的 原子性 （ atomic ） 變體函數。它看起來比 非原子性 （ non-atomic ） 變體更加複雜：

static __always_inline void
set_bit(long nr, volatile unsigned long *addr)
{
    if (IS_IMMEDIATE(nr)) {
        asm volatile(LOCK_PREFIX "orb %1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" ((u8)CONST_MASK(nr))
            : "memory");
    } else {
        asm volatile(LOCK_PREFIX "bts %1,%0"
            : BITOP_ADDR(addr) : "Ir" (nr) : "memory");
    }
}

（LCTT 譯註：BITOP_ADDR 的定義為：#define BITOP_ADDR(x) "=m" (*(volatile long *) (x))，ORB 為位元組按位或。）

首先注意，這個函數使用了與 __set_bit 相同的參數集合，但額外地使用了 __always_inline 屬性標記。 __always_inline 是一個定義於 include/linux/compiler-gcc.h 的宏，並且只是展開為 always_inline 屬性：

#define __always_inline inline __attribute__((always_inline))

其意味著這個函數總是內聯的，以減少 Linux 內核映像的大小。現在讓我們試著了解下 set_bit 函數的實現。首先我們在 set_bit 函數的開頭檢查給定的位的數量。IS_IMMEDIATE 宏定義於相同的頭文件，並展開為 gcc 內置函數的調用：

#define IS_IMMEDIATE(nr)        (__builtin_constant_p(nr))

如果給定的參數是編譯期已知的常量，__builtin_constant_p 內置函數則返回 1，其他情況返回 0。假若給定的位數是編譯期已知的常量，我們便無須使用效率低下的 bts 指令去設置位。我們可以只需在給定地址指向的位元組上執行 按位或 操作，其位元組包含給定的位，掩碼位數表示高位為 1，其他位為 0 的掩碼。在其他情況下，如果給定的位號不是編譯期已知常量，我們便做和 __set_bit 函數一樣的事。CONST_MASK_ADDR 宏：

#define CONST_MASK_ADDR(nr, addr)   BITOP_ADDR((void *)(addr) + ((nr)>>3))

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

>>> hex(0x1000 + (0x9 >> 3))
'0x1001'

CONST_MASK 宏將我們給定的位號表示為位元組，位號對應位為高位 1，其他位為 0：

#define CONST_MASK(nr)          (1 << ((nr) & 7))

>>> bin(1 << (0x9 & 7))
&apos;0b10&apos;

最後，我們應用 按位或 運算到這些變數上面，因此，假如我們的地址是 0x4097 ，並且我們需要置位號為 9 的位為 1：

>>> bin(0x4097)
'0b100000010010111'
>>> bin((0x4097 >> 0x9) | (1 << (0x9 & 7)))
&apos;0b100010&apos;

第 9 位 將會被置位。（LCTT 譯註：這裡的 9 是從 0 開始計數的，比如0010，按照作者的意思，其中的 1 是第 1 位）

注意，所有這些操作使用 LOCK_PREFIX 標記，其展開為 lock 指令，保證該操作的原子性。

正如我們所知，除了 set_bit 和 __set_bit 操作之外，Linux 內核還提供了兩個功能相反的函數，在原子性和非原子性的上下文中清位。它們是 clear_bit 和 __clear_bit。這兩個函數都定義於同一個頭文件 並且使用相同的參數集合。不僅參數相似，一般而言，這些函數與 set_bit 和 __set_bit 也非常相似。讓我們查看非原子性 __clear_bit 的實現吧：

static inline void __clear_bit(long nr, volatile unsigned long *addr)
{
    asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
}

沒錯，正如我們所見，__clear_bit 使用相同的參數集合，並包含極其相似的內聯彙編代碼塊。它只是使用 btr 指令替換了 bts。正如我們從函數名所理解的一樣，通過給定地址，它清除了給定的位。btr 指令表現得像 bts（LCTT 譯註：原文這裡為 btr，可能為筆誤，修正為 bts）。該指令選出第一操作數所指定的位，存儲它的值到 CF 標誌寄存器，並且清除第二操作數指定的位數組中的對應位。

__clear_bit 的原子性變體為 clear_bit：

static __always_inline void
clear_bit(long nr, volatile unsigned long *addr)
{
    if (IS_IMMEDIATE(nr)) {
        asm volatile(LOCK_PREFIX "andb %1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" ((u8)~CONST_MASK(nr)));
    } else {
        asm volatile(LOCK_PREFIX "btr %1,%0"
            : BITOP_ADDR(addr)
            : "Ir" (nr));
    }
}

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

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

在 Linux 內核中對位數組最廣泛使用的操作是設置和清除位，但是除了這兩個操作外，位數組上其他操作也是非常有用的。Linux 內核里另一種廣泛使用的操作是知曉位數組中一個給定的位是否被置位。我們能夠通過 test_bit 宏的幫助實現這一功能。這個宏定義於 arch/x86/include/asm/bitops.h 頭文件，並根據位號分別展開為 constant_test_bit 或 variable_test_bit 調用。

#define test_bit(nr, addr)          
    (__builtin_constant_p((nr))                 
     ? constant_test_bit((nr), (addr))          
     : variable_test_bit((nr), (addr)))

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

static inline int variable_test_bit(long nr, volatile const unsigned long *addr)
{
    int oldbit;

    asm volatile("bt %2,%1nt"
             "sbb %0,%0"
             : "=r" (oldbit)
             : "m" (*(unsigned long *)addr), "Ir" (nr));

    return oldbit;
}

variable_test_bit 函數使用了與 set_bit 及其他函數使用的相似的參數集合。我們也可以看到執行 bt 和 sbb 指令的內聯彙編代碼。bt （或稱 bit test）指令從第二操作數指定的位數組選出第一操作數指定的一個指定位，並且將該位的值存進標誌寄存器的 CF 位。第二個指令 sbb 從第二操作數中減去第一操作數，再減去 CF 的值。因此，這裡將一個從給定位數組中的給定位號的值寫進標誌寄存器的 CF 位，並且執行 sbb 指令計算： 00000000 - CF，並將結果寫進 oldbit 變數。

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

static __always_inline int constant_test_bit(long nr, const volatile unsigned long *addr)
{
    return ((1UL << (nr & (BITS_PER_LONG-1))) &
        (addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
}

它生成了一個位號對應位為高位 1，而其他位為 0 的位元組（正如我們在 CONST_MASK 所看到的），並將 按位與 應用於包含給定位號的位元組。

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

• __change_bit;
• change_bit.

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

static inline void __change_bit(long nr, volatile unsigned long *addr)
{
    asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
}

相當簡單，不是嗎？ __change_bit 的實現和 __set_bit 一樣，只是我們使用 btc 替換 bts 指令而已。 該指令從一個給定位數組中選出一個給定位，將該為位的值存進 CF 並使用求反操作改變它的值，因此值為 1 的位將變為 0，反之亦然：

>>> int(not 1)
0
>>> int(not 0)
1

__change_bit 的原子版本為 change_bit 函數：

static inline void change_bit(long nr, volatile unsigned long *addr)
{
    if (IS_IMMEDIATE(nr)) {
        asm volatile(LOCK_PREFIX "xorb %1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" ((u8)CONST_MASK(nr)));
    } else {
        asm volatile(LOCK_PREFIX "btc %1,%0"
            : BITOP_ADDR(addr)
            : "Ir" (nr));
    }
}

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

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

通用位操作

除了 arch/x86/include/asm/bitops.h 中體系特定的 API 外，Linux 內核提供了操作位數組的通用 API。正如我們本部分開頭所了解的一樣，我們可以在 include/linux/bitmap.h 頭文件和 lib/bitmap.c 源文件中找到它。但在查看這些源文件之前，我們先看看 include/linux/bitops.h 頭文件，其提供了一系列有用的宏，讓我們看看它們當中一部分。

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

• for_each_set_bit
• for_each_set_bit_from
• for_each_clear_bit
• for_each_clear_bit_from

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

#define for_each_set_bit(bit, addr, size) 
    for ((bit) = find_first_bit((addr), (size));        
         (bit) < (size);                    
         (bit) = find_next_bit((addr), (size), (bit) + 1))

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

除了這四個宏， arch/x86/include/asm/bitops.h 也提供了 64-bit 或 32-bit 變數循環的 API 等等。

下一個 頭文件 提供了操作位數組的 API。例如，它提供了以下兩個函數：

• bitmap_zero;
• bitmap_fill.

它們分別可以清除一個位數組和用 1 填充位數組。讓我們看看 bitmap_zero 函數的實現：

static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
{
    if (small_const_nbits(nbits))
        *dst = 0UL;
    else {
        unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
        memset(dst, 0, len);
    }
}

首先我們可以看到對 nbits 的檢查。 small_const_nbits 是一個定義在同一個頭文件 的宏：

#define small_const_nbits(nbits) 
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

正如我們可以看到的，它檢查 nbits 是否為編譯期已知常量，並且其值不超過 BITS_PER_LONG 或 64。如果位數目沒有超過一個 long 變數的位數，我們可以僅僅設置為 0。在其他情況，我們需要計算有多少個需要填充位數組的 long 變數並且使用 memset 進行填充。

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

static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
{
    unsigned int nlongs = BITS_TO_LONGS(nbits);
    if (!small_const_nbits(nbits)) {
        unsigned int len = (nlongs - 1) * sizeof(unsigned long);
        memset(dst, 0xff,  len);
    }
    dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}

除了 bitmap_fill 和 bitmap_zero，include/linux/bitmap.h 頭文件也提供了和 bitmap_zero 很相似的 bitmap_copy，只是僅僅使用 memcpy 而不是 memset 這點差異而已。它也提供了位數組的按位操作，像 bitmap_and, bitmap_or, bitamp_xor等等。我們不會探討這些函數的實現了，因為如果你理解了本部分的所有內容，這些函數的實現是很容易理解的。無論如何，如果你對這些函數是如何實現的感興趣，你可以打開並研究 include/linux/bitmap.h 頭文件。

本部分到此為止。

鏈接

• bitmap
• linked data structures
• tree data structures
• hot-plug
• cpumasks
• IRQs
• API
• atomic operations
• xchg instruction
• cmpxchg instruction
• lock instruction
• bts instruction
• btr instruction
• bt instruction
• sbb instruction
• btc instruction
• man memcpy
• man memset
• CF
• inline assembler
• gcc

via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/bitmap.md

作者：0xAX 譯者：cposture 校對：wxy

本文由 LCTT 原創翻譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive