Linux內(nèi)核中的位數(shù)組和位操作

這篇文章主要介紹“Linux內(nèi)核中的位數(shù)組和位操作”，在日常操作中，相信很多人在Linux內(nèi)核中的位數(shù)組和位操作問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對(duì)大家解答”Linux內(nèi)核中的位數(shù)組和位操作”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

Linux 內(nèi)核中的位數(shù)組和位操作

除了不同的基于鏈?zhǔn)胶蜆涞臄?shù)據(jù)結(jié)構(gòu)以外，Linux 內(nèi)核也為位數(shù)組(或稱為位圖(bitmap))提供了 API。位數(shù)組在 Linux  內(nèi)核里被廣泛使用，并且在以下的源代碼文件中包含了與這樣的結(jié)構(gòu)搭配使用的通用 API：

• lib/bitmap.c

• include/linux/bitmap.h

除了這兩個(gè)文件之外，還有體系結(jié)構(gòu)特定的頭文件，它們?yōu)樘囟ǖ捏w系結(jié)構(gòu)提供優(yōu)化的位操作。我們將探討 x86_64 體系結(jié)構(gòu)，因此在我們的例子里，它會(huì)是

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

頭文件。正如我上面所寫的，位圖在 Linux 內(nèi)核中被廣泛地使用。例如，位數(shù)組常常用于保存一組在線/離線處理器，以便系統(tǒng)支持熱插拔的 CPU(你可以在  cpumasks 部分閱讀更多相關(guān)知識(shí) )，一個(gè)位數(shù)組(bit array)可以在 Linux 內(nèi)核初始化等期間保存一組已分配的中斷處理。

因此，本部分的主要目的是了解位數(shù)組(bit array)是如何在 Linux 內(nèi)核中實(shí)現(xiàn)的。讓我們現(xiàn)在開始吧。

位數(shù)組聲明

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

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 宏使用兩個(gè)參數(shù)：

• name - 位圖名稱;

• bits - 位圖中位數(shù);

并且只是使用 BITS_TO_LONGS(bits) 元素展開 unsigned long 數(shù)組的定義。 BITS_TO_LONGS  宏將一個(gè)給定的位數(shù)轉(zhuǎn)換為 long 的個(gè)數(shù)，換言之，就是計(jì)算 bits 中有多少個(gè) 8 字節(jié)元素：

#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) 將產(chǎn)生：

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

與：

unsigned long my_bitmap[1];

在能夠聲明一個(gè)位數(shù)組之后，我們便可以使用它了。

體系結(jié)構(gòu)特定的位操作

我們已經(jīng)看了上面提及的一對(duì)源文件和頭文件，它們提供了位數(shù)組操作的 API。其中重要且廣泛使用的位數(shù)組 API 是體系結(jié)構(gòu)特定的且位于已提及的頭文件中  arch/x86/include/asm/bitops.h。

首先讓我們查看兩個(gè)最重要的函數(shù)：

• set_bit;

• clear_bit.

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

簡而言之，原子操作保證兩個(gè)或以上的操作不會(huì)并發(fā)地執(zhí)行同一數(shù)據(jù)。x86 體系結(jié)構(gòu)提供了一系列原子指令，例如， xchg、cmpxchg  等指令。除了原子指令，一些非原子指令可以在 lock 指令的幫助下具有原子性。現(xiàn)在你已經(jīng)對(duì)原子操作有了足夠的了解，我們可以接著探討 set_bit 和  clear_bit 函數(shù)的實(shí)現(xiàn)。

我們先考慮函數(shù)的非原子性(non-atomic)變體。非原子性的 set_bit 和 clear_bit  的名字以雙下劃線開始。正如我們所知道的，所有這些函數(shù)都定義于 arch/x86/include/asm/bitops.h 頭文件，并且***個(gè)函數(shù)就是  __set_bit:

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

正如我們所看到的，它使用了兩個(gè)參數(shù)：

• nr - 位數(shù)組中的位號(hào)(LCTT 譯注：從 0 開始)

• addr - 我們需要置位的位數(shù)組地址

注意，addr 參數(shù)使用 volatile 關(guān)鍵字定義，以告訴編譯器給定地址指向的變量可能會(huì)被修改。 __set_bit  的實(shí)現(xiàn)相當(dāng)簡單。正如我們所看到的，它僅包含一行內(nèi)聯(lián)匯編代碼。在我們的例子中，我們使用 bts 指令，從位數(shù)組中選出一個(gè)***操作數(shù)(我們的例子中的  nr)所指定的位，存儲(chǔ)選出的位的值到 CF 標(biāo)志寄存器并設(shè)置該位(LCTT 譯注：即 nr 指定的位置為 1)。

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

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

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

• +m - 表示內(nèi)存操作數(shù)，這里的 + 表明給定的操作數(shù)為輸入輸出操作數(shù);

• I - 表示整型常量;

• r - 表示寄存器操作數(shù)

除了這些約束之外，我們也能看到 memory  關(guān)鍵字，其告訴編譯器這段代碼會(huì)修改內(nèi)存中的變量。到此為止，現(xiàn)在我們看看相同的原子性(atomic)變體函數(shù)。它看起來比非原子性(non-atomic)變體更加復(fù)雜：

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 為字節(jié)按位或。)

首先注意，這個(gè)函數(shù)使用了與 __set_bit 相同的參數(shù)集合，但額外地使用了 __always_inline 屬性標(biāo)記。 __always_inline  是一個(gè)定義于 include/linux/compiler-gcc.h 的宏，并且只是展開為 always_inline 屬性：

#define __always_inline inline __attribute__((always_inline))

其意味著這個(gè)函數(shù)總是內(nèi)聯(lián)的，以減少 Linux 內(nèi)核映像的大小?，F(xiàn)在讓我們?cè)囍私庀?set_bit 函數(shù)的實(shí)現(xiàn)。首先我們?cè)?set_bit  函數(shù)的開頭檢查給定的位的數(shù)量。IS_IMMEDIATE 宏定義于相同的頭文件，并展開為 gcc 內(nèi)置函數(shù)的調(diào)用：

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

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

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

展開為帶有到包含給定位的字節(jié)偏移的給定地址，例如，我們擁有地址 0x1000 和位號(hào) 0x9。因?yàn)?0x9 代表 一個(gè)字節(jié) + 一位，所以我們的地址是  addr + 1:

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

CONST_MASK 宏將我們給定的位號(hào)表示為字節(jié)，位號(hào)對(duì)應(yīng)位為高位 1，其他位為 0：

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

>>> bin(1 << (0x9 & 7)) '0b10'

***，我們應(yīng)用 按位或 運(yùn)算到這些變量上面，因此，假如我們的地址是 0x4097 ，并且我們需要置位號(hào)為 9 的位為 1：

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

第 9 位 將會(huì)被置位。(LCTT 譯注：這里的 9 是從 0 開始計(jì)數(shù)的，比如0010，按照作者的意思，其中的 1 是第 1 位)

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

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

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

沒錯(cuò)，正如我們所見，__clear_bit 使用相同的參數(shù)集合，并包含極其相似的內(nèi)聯(lián)匯編代碼塊。它只是使用 btr 指令替換了  bts。正如我們從函數(shù)名所理解的一樣，通過給定地址，它清除了給定的位。btr 指令表現(xiàn)得像 bts(LCTT 譯注：原文這里為 btr，可能為筆誤，修正為  bts)。該指令選出***操作數(shù)所指定的位，存儲(chǔ)它的值到 CF 標(biāo)志寄存器，并且清除第二操作數(shù)指定的位數(shù)組中的對(duì)應(yīng)位。

__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 使用否定的位掩碼和 按位與 在給定的字節(jié)上置位，而 set_bit 使用 按位或 指令。

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

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

#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 函數(shù)的調(diào)用，而其他情況則為  variable_test_bit?，F(xiàn)在讓我們看看這些函數(shù)的實(shí)現(xiàn)，讓我們從 variable_test_bit 開始看起：

static inline int variable_test_bit(long nr, volatile const unsigned long *addr) {     int oldbit;     asm volatile("bt %2,%1\n\t"              "sbb %0,%0"              : "=r" (oldbit)              : "m" (*(unsigned long *)addr), "Ir" (nr));     return oldbit; }

variable_test_bit 函數(shù)使用了與 set_bit 及其他函數(shù)使用的相似的參數(shù)集合。我們也可以看到執(zhí)行 bt 和 sbb  指令的內(nèi)聯(lián)匯編代碼。bt (或稱 bit test)指令從第二操作數(shù)指定的位數(shù)組選出***操作數(shù)指定的一個(gè)指定位，并且將該位的值存進(jìn)標(biāo)志寄存器的 CF  位。第二個(gè)指令 sbb 從第二操作數(shù)中減去***操作數(shù)，再減去 CF 的值。因此，這里將一個(gè)從給定位數(shù)組中的給定位號(hào)的值寫進(jìn)標(biāo)志寄存器的 CF 位，并且執(zhí)行  sbb 指令計(jì)算： 00000000 - CF，并將結(jié)果寫進(jìn) oldbit 變量。

constant_test_bit 函數(shù)做了和我們?cè)?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; }

它生成了一個(gè)位號(hào)對(duì)應(yīng)位為高位 1，而其他位為 0 的字節(jié)(正如我們?cè)?CONST_MASK 所看到的)，并將 按位與 應(yīng)用于包含給定位號(hào)的字節(jié)。

下一個(gè)被廣泛使用的位數(shù)組相關(guān)操作是改變一個(gè)位數(shù)組中的位。為此，Linux 內(nèi)核提供了兩個(gè)輔助函數(shù)：

• __change_bit;

• change_bit.

你可能已經(jīng)猜測(cè)到，就拿 set_bit 和 __set_bit 例子說，這兩個(gè)變體分別是原子和非原子版本。首先，讓我們看看 __change_bit  函數(shù)的實(shí)現(xiàn)：

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

相當(dāng)簡單，不是嗎? __change_bit 的實(shí)現(xiàn)和 __set_bit 一樣，只是我們使用 btc 替換 bts 指令而已。  該指令從一個(gè)給定位數(shù)組中選出一個(gè)給定位，將該為位的值存進(jìn) CF 并使用求反操作改變它的值，因此值為 1 的位將變?yōu)?0，反之亦然：

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

__change_bit 的原子版本為 change_bit 函數(shù)：

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 函數(shù)很相似，但也存在兩點(diǎn)不同。***處差異為 xor 操作而不是 or。第二處差異為 btc( LCTT 譯注：原文為  bts，為作者筆誤) 而不是 bts。

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

通用位操作

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

首先我們看看以下 4 個(gè) 宏：

• for_each_set_bit

• for_each_set_bit_from

• for_each_clear_bit

• for_each_clear_bit_from

所有這些宏都提供了遍歷位數(shù)組中某些位集合的迭代器。***個(gè)宏迭代那些被置位的位。第二個(gè)宏也是一樣，但它是從某一個(gè)確定的位開始。***兩個(gè)宏做的一樣，但是迭代那些被清位的位。讓我們看看  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))

正如我們所看到的，它使用了三個(gè)參數(shù)，并展開為一個(gè)循環(huán)，該循環(huán)從作為 find_first_bit  函數(shù)返回結(jié)果的***個(gè)置位開始，到小于給定大小的***一個(gè)置位為止。

除了這四個(gè)宏， arch/x86/include/asm/bitops.h 也提供了 64-bit 或 32-bit 變量循環(huán)的 API 等等。

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

• bitmap_zero;

• bitmap_fill.

它們分別可以清除一個(gè)位數(shù)組和用 1 填充位數(shù)組。讓我們看看 bitmap_zero 函數(shù)的實(shí)現(xiàn)：

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);     } }

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

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

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

bitmap_fill 函數(shù)的實(shí)現(xiàn)和 biramp_zero 函數(shù)很相似，除了我們需要在給定的位數(shù)組中填寫 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 這點(diǎn)差異而已。它也提供了位數(shù)組的按位操作，像 bitmap_and,  bitmap_or,  bitamp_xor等等。我們不會(huì)探討這些函數(shù)的實(shí)現(xiàn)了，因?yàn)槿绻憷斫饬吮静糠值乃袃?nèi)容，這些函數(shù)的實(shí)現(xiàn)是很容易理解的。無論如何，如果你對(duì)這些函數(shù)是如何實(shí)現(xiàn)的感興趣，你可以打開并研究  include/linux/bitmap.h 頭文件。

到此，關(guān)于“Linux內(nèi)核中的位數(shù)組和位操作”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！