鴻蒙輕內核A核源碼分析系列二：數據結構-位圖操作
在進一步分析之前，本文我們先來熟悉下OpenHarmony鴻蒙輕內核提供的位操作模塊，在互斥鎖等模塊對位操作有使用。位操作是指對二進制數的bit位進行操作。程序可以設置某一變量為狀態字，狀態字中的每一bit位(標志位)可以具有自定義的含義。
1 位操作的宏定義
位操作模塊提供對32位無符號整數數值的bit位進行操作，bit位取值為0-31，以0開始計算，從左向右，第0位，第1位。。。第31位等。⑴處定義的宏OS_BITMAP_MASK如下，也就是十進制31。如果傳入的比特位pos大于31，會通過邏輯與運算截斷(pos & OS_BITMAP_MASK)，只取低5位，確保不會大于31，避免溢出。⑵處定義的位圖掩碼全是1。
- ⑴ #define OS_BITMAP_MASK 0x1FU
- ⑵ #define OS_BITMAP_WORD_MASK ~0UL
在文件kernel\include\los_bitmap.h中定義了常用的位操作相關的宏。宏BITMAP_WORD根據參數x計算出需要操作第幾個狀態字，由于計算狀態字的使用的是UINTPTR，狀態字可以是32位、也可以是64位。后文，我們默認以32位進行講解。宏BITMAP_FIRST_WORD_MASK傳入的參數是位操作的開始bit位數，用于計算需要進行位操作的掩碼，從開始位全部是1，宏BITMAP_LAST_WORD_MASK傳入的參數是位操作的結束bit位數，用于計算需要進行位操作的掩碼，結束位之前全部是1。宏BITMAP_NUM_WORDS傳入位數，計算狀態字的數量。
- #define _ONE(x) (1 + ((x) - (x)))
- #define BIT(n) (1U << (n))
- #define BIT_GET(x, bit) ((x) & (_ONE(x) << (bit)))
- #define BIT_SHIFT(x, bit) (((x) >> (bit)) & 1)
- #define BITS_GET(x, high, low) ((x) & (((_ONE(x) << ((high) + 1)) - 1) & ~((_ONE(x) << (low)) - 1)))
- #define BITS_SHIFT(x, high, low) (((x) >> (low)) & ((_ONE(x) << ((high) - (low) + 1)) - 1))
- #define BIT_SET(x, bit) (((x) & (_ONE(x) << (bit))) ? 1 : 0)
- #define BITMAP_BITS_PER_WORD (sizeof(UINTPTR) * 8)
- #define BITMAP_NUM_WORDS(x) (((x) + BITMAP_BITS_PER_WORD - 1) / BITMAP_BITS_PER_WORD)
- #define BITMAP_WORD(x) ((x) / BITMAP_BITS_PER_WORD)
- #define BITMAP_BIT_IN_WORD(x) ((x) & (BITMAP_BITS_PER_WORD - 1))
- #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITMAP_BITS_PER_WORD))
- #define BITMAP_LAST_WORD_MASK(nbits) \
- (((nbits) % BITMAP_BITS_PER_WORD) ? (1UL << ((nbits) % BITMAP_BITS_PER_WORD)) - 1 : ~0UL)
- #define BITMAP_BITS_PER_INT (sizeof(INTPTR) * 8)
- #define BITMAP_BIT_IN_INT(x) ((x) & (BITMAP_BITS_PER_INT - 1))
- #define BITMAP_INT(x) ((x) / BITMAP_BITS_PER_INT)
- #define BIT_MASK(x) (((x) >= sizeof(UINTPTR) * 8) ? (0UL - 1) : ((1UL << (x)) - 1))
2 位操作常用功能
OpenHarmony鴻蒙輕內核的位操作模塊提供標志位的置1和清0操作，可以改變標志位的內容，同時還提供獲取狀態字中標志位為1的最高位和最低位的功能。用戶也可以對系統的寄存器進行位操作。位操作提供了7個API，進行置1、清0、獲取為1的最高、最低位等操作，如下：
下面，我們剖析下位操作的源代碼。
2.1 LOS_BitmapSet()對狀態字的某一標志位進行置1操作
對狀態字的某一標志位進行置1操作。我們先看看傳入的參數，需要的2個參數分別是：需要改變bit位內容的狀態字UINT32 *bitmap，需要改變的bit位位數UINT16 pos。
代碼很簡單，首先進行基礎的校驗，如果狀態字為空，則返回。然后計算pos & OS_BITMAP_MASK，只取二進制的低5位，最大位值為31，避免左移的時候發生溢出。1U << (pos & OS_BITMAP_MASK)就是需要改變內容的狀態字的bit位，通過按位或運算設置狀態字UINT32 *bitmap的指定bit位的內容為1。
- VOID LOS_BitmapSet(UINT32 *bitmap, UINT16 pos)
- {
- if (bitmap == NULL) {
- return;
- }
- *bitmap |= 1U << (pos & OS_BITMAP_MASK);
- }
2.2 LOS_BitmapClr()對狀態字的某一標志位進行清0操作
對狀態字的某一標志位進行清0操作，代碼和置1操作對應，比較簡單，~(1U << (pos & OS_BITMAP_MASK))表示需要改變內容的狀態字的bit位為0，其余位為1，然后通過按位與運算設置狀態字UINT32 *bitmap的指定bit位的內容為0。
- VOID LOS_BitmapClr(UINT32 *bitmap, UINT16 pos)
- {
- if (bitmap == NULL) {
- return;
- }
- *bitmap &= ~(1U << (pos & OS_BITMAP_MASK));
- }
2.3 LOS_HighBitGet()獲取狀態字中為1的最高位
代碼中CLZ(bitmap)是宏，展開為(__builtin_clz(bitmap))，這是編譯器內置的高效位運算的庫函數，clz是count leading zeros的縮寫，就是統計二進制數值中高位區開頭的全是0的數目。使用OS_BITMAP_MASK減去該值，結果就是狀態字中的1的最高位。
- UINT16 LOS_HighBitGet(UINT32 bitmap)
- {
- if (bitmap == 0) {
- return LOS_INVALID_BIT_INDEX;
- }
- return (OS_BITMAP_MASK - CLZ(bitmap));
- }
2.4 LOS_LowBitGet()獲取狀態字中為1的最低位
代碼其中CTZ(bitmap)是宏，展開為(__builtin_ctz(value))，這是編譯器內置的高效位運算的庫函數，ctz是count trailing zeros的縮寫，就是統計二進制數值中低位區結尾的全是0的數目，該結果就是狀態字中的1的最低位。
- UINT16 LOS_LowBitGet(UINT32 bitmap)
- {
- if (bitmap == 0) {
- return LOS_INVALID_BIT_INDEX;
- }
- return CTZ(bitmap);
- }
2.5 LOS_BitmapSetNBits()對狀態字的連續標志位進行置1操作
可以使用LOS_BitmapSetNBits()函數對狀態字的連續比特位進行置1操作，第一個參數是需要改變bit位內容的狀態字UINT32 *bitmap，第二個參數是需要置1的bit位開始數start，第三個參數是需要置1的數量numsSet。由于bit位開始數start并沒有限制在[0,31]，所以實際上設置的可能是UINT32 *bitmap狀態字后面的狀態字，需要根據業務實際情況進行設置，避免覆寫其他內存。同樣，需要置1的數量numsSet也可能跨多個狀態字。如圖所示：
我們看下代碼，
⑴處計算出需要操作的狀態字，其中BITMAP_WORD(start)計算相對狀態字bitmap需要偏移的數量，如果start處于區間[0,31]，BITMAP_WORD(start)等于0，操作的就是狀態字bitmap。如果start處于區間[32,63]，BITMAP_WORD(start)等于1，操作的就是狀態字bitmap后面的第一個狀態字，以此類推。
⑵處size可以和bit位開始數start結合來理解，size就是需要置1的bit位結束位數。
⑶處需要置1操作的bit位的位數。
⑷是對應需要置1操作的bit位的掩碼。
⑸處如果條件成立，說明需要置1操作需要跨多個狀態字進行操作，代碼會一個狀態字處理完畢，再去處理下一個狀態字。
⑹處把當前狀態字的相應的bit位進行置1操作，然后執行⑺把剩余需要置1的位數減去已經置1的位數。
⑻處更新bitsToSet和maskToSet，然后指針p指向下一個狀態字。
⑼處如果需要置1的位數大于0，并且此時已經可以在一個狀態字內完成操作，執行⑽處計算需要置1操作的掩碼，從bit開始位到結束位需要進行置1。
⑾處代碼執行置1操作，完成對狀態字的連續標志位進行置1操作。
- VOID LOS_BitmapSetNBits(UINTPTR *bitmap, UINT32 start, UINT32 numsSet)
- {
- ⑴ UINTPTR *p = bitmap + BITMAP_WORD(start);
- ⑵ const UINT32 size = start + numsSet;
- ⑶ UINT16 bitsToSet = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD);
- ⑷ UINTPTR maskToSet = BITMAP_FIRST_WORD_MASK(start);
- ⑸ while (numsSet > bitsToSet) {
- ⑹ *p |= maskToSet;
- ⑺ numsSet -= bitsToSet;
- ⑻ bitsToSet = BITMAP_BITS_PER_WORD;
- maskToSet = OS_BITMAP_WORD_MASK;
- p++;
- }
- ⑼ if (numsSet) {
- ⑽ maskToSet &= BITMAP_LAST_WORD_MASK(size);
- *p |= maskToSet;
- }
- }
2.6 LOS_BitmapClrNBits()對狀態字的連續標志位進行清0操作
可以使用LOS_BitmapClrNBits()函數對狀態字的連續比特位進行清0操作，第一個參數是需要改變bit位內容的狀態字UINT32 *bitmap，第二個參數是需要清0的bit位開始數start，第三個參數是需要清0的數量numsClear。該函數是函數LOS_BitmapSetNBits()的反向操作，代碼解釋可以參考函數LOS_BitmapSetNBits()。
- VOID LOS_BitmapClrNBits(UINTPTR *bitmap, UINT32 start, UINT32 numsClear)
- {
- UINTPTR *p = bitmap + BITMAP_WORD(start);
- const UINT32 size = start + numsClear;
- UINT16 bitsToClear = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD);
- UINTPTR maskToClear = BITMAP_FIRST_WORD_MASK(start);
- while (numsClear >= bitsToClear) {
- *p &= ~maskToClear;
- numsClear -= bitsToClear;
- bitsToClear = BITMAP_BITS_PER_WORD;
- maskToClear = OS_BITMAP_WORD_MASK;
- p++;
- }
- if (numsClear) {
- maskToClear &= BITMAP_LAST_WORD_MASK(size);
- *p &= ~maskToClear;
- }
- }
2.7 LOS_BitmapFfz()獲取從最低有效位開始的第一個0的bit位
可以使用LOS_BitmapFfz()函數獲取從最低有效位開始的第一個0的bit位位數，第一個參數是需要改變bit位內容的狀態字UINT32 *bitmap，第二個參數numBits表示最大的位數，對返回值進行限制，需要在指定的位數內找到符合條件的位數，否則返回-1。
在看函數代碼之前，先了解下Ffz()函數，如下：調用內嵌函數__builtin_ffsl()可以獲取一個unsigned long類型數字的二進制形式的從左開始的第一個1的位數，這個位數從1開始計數。比如對于二進制數字0110，該函數會返回2。在下面的函數中，給函數__builtin_ffsl()傳入的參數進行了取反，并減去了1，所以Ffz()函數返回一個數字從左開始的第一個0的位數，這個位數從0開始計數。
- /* find first zero bit starting from LSB */
- STATIC INLINE UINT16 Ffz(UINTPTR x)
- {
- return __builtin_ffsl(~x) - 1;
- }
我們接著看下函數LOS_BitmapFfz()的代碼。⑴處根據位數numBits計算出對應的狀態字的數量，然后依次循環每一個狀態字，⑵處如果狀態字全為1，則繼續循環，否則執行⑶。執行到⑶說明，，前面有i個狀態字的各個位全為1。i * BITMAP_BITS_PER_WORD + Ffz(bitmap[i])就表示各個狀態字的二進制位中，從左到右第一個0的位置。⑷處如果獲取的位數小于第二個參數，則返回獲取的位數，否則返回-1。如下圖所示：
源代碼如下：
- INT32 LOS_BitmapFfz(UINTPTR *bitmap, UINT32 numBits)
- {
- INT32 bit, i;
- ⑴ for (i = 0; i < BITMAP_NUM_WORDS(numBits); i++) {
- ⑵ if (bitmap[i] == OS_BITMAP_WORD_MASK) {
- continue;
- }
- ⑶ bit = i * BITMAP_BITS_PER_WORD + Ffz(bitmap[i]);
- ⑷ if (bit < numBits) {
- return bit;
- }
- return -1;
- }
- return -1;
- }
小結
本文帶領大家一起剖析了鴻蒙輕內核的位操作模塊的源代碼。
