鴻蒙輕內(nèi)核A核源碼分析系列二：數(shù)據(jù)結(jié)構(gòu)-位圖操作

作者：zhushangyuan 2021-06-17 09:36:07

文章由鴻蒙社區(qū)產(chǎn)出，想要了解更多內(nèi)容請前往：51CTO和華為官方戰(zhàn)略合作共建的鴻蒙技術(shù)社區(qū)https://harmonyos.51cto.com

https://harmonyos.51cto.com

在進一步分析之前，本文我們先來熟悉下OpenHarmony鴻蒙輕內(nèi)核提供的位操作模塊，在互斥鎖等模塊對位操作有使用。位操作是指對二進制數(shù)的bit位進行操作。程序可以設(shè)置某一變量為狀態(tài)字，狀態(tài)字中的每一bit位(標志位)可以具有自定義的含義。

1 位操作的宏定義

位操作模塊提供對32位無符號整數(shù)數(shù)值的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中定義了常用的位操作相關(guān)的宏。宏BITMAP_WORD根據(jù)參數(shù)x計算出需要操作第幾個狀態(tài)字，由于計算狀態(tài)字的使用的是UINTPTR，狀態(tài)字可以是32位、也可以是64位。后文，我們默認以32位進行講解。宏BITMAP_FIRST_WORD_MASK傳入的參數(shù)是位操作的開始bit位數(shù)，用于計算需要進行位操作的掩碼，從開始位全部是1，宏BITMAP_LAST_WORD_MASK傳入的參數(shù)是位操作的結(jié)束bit位數(shù)，用于計算需要進行位操作的掩碼，結(jié)束位之前全部是1。宏BITMAP_NUM_WORDS傳入位數(shù)，計算狀態(tài)字的數(shù)量。

#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鴻蒙輕內(nèi)核的位操作模塊提供標志位的置1和清0操作，可以改變標志位的內(nèi)容，同時還提供獲取狀態(tài)字中標志位為1的最高位和最低位的功能。用戶也可以對系統(tǒng)的寄存器進行位操作。位操作提供了7個API，進行置1、清0、獲取為1的最高、最低位等操作，如下：

下面，我們剖析下位操作的源代碼。

2.1 LOS_BitmapSet()對狀態(tài)字的某一標志位進行置1操作

對狀態(tài)字的某一標志位進行置1操作。我們先看看傳入的參數(shù)，需要的2個參數(shù)分別是：需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，需要改變的bit位位數(shù)UINT16 pos。

代碼很簡單，首先進行基礎(chǔ)的校驗，如果狀態(tài)字為空，則返回。然后計算pos & OS_BITMAP_MASK，只取二進制的低5位，最大位值為31，避免左移的時候發(fā)生溢出。1U << (pos & OS_BITMAP_MASK)就是需要改變內(nèi)容的狀態(tài)字的bit位，通過按位或運算設(shè)置狀態(tài)字UINT32 *bitmap的指定bit位的內(nèi)容為1。

VOID LOS_BitmapSet(UINT32 *bitmap, UINT16 pos) 
{ 
    if (bitmap == NULL) { 
        return; 
    } 
 
    *bitmap |= 1U << (pos & OS_BITMAP_MASK); 
}

2.2 LOS_BitmapClr()對狀態(tài)字的某一標志位進行清0操作

對狀態(tài)字的某一標志位進行清0操作，代碼和置1操作對應(yīng)，比較簡單，~(1U << (pos & OS_BITMAP_MASK))表示需要改變內(nèi)容的狀態(tài)字的bit位為0，其余位為1，然后通過按位與運算設(shè)置狀態(tài)字UINT32 *bitmap的指定bit位的內(nèi)容為0。

VOID LOS_BitmapClr(UINT32 *bitmap, UINT16 pos) 
{ 
    if (bitmap == NULL) { 
        return; 
    } 
 
    *bitmap &= ~(1U << (pos & OS_BITMAP_MASK)); 
}

2.3 LOS_HighBitGet()獲取狀態(tài)字中為1的最高位

代碼中CLZ(bitmap)是宏，展開為(__builtin_clz(bitmap))，這是編譯器內(nèi)置的高效位運算的庫函數(shù)，clz是count leading zeros的縮寫，就是統(tǒng)計二進制數(shù)值中高位區(qū)開頭的全是0的數(shù)目。使用OS_BITMAP_MASK減去該值，結(jié)果就是狀態(tài)字中的1的最高位。

UINT16 LOS_HighBitGet(UINT32 bitmap) 
{ 
    if (bitmap == 0) { 
        return LOS_INVALID_BIT_INDEX; 
    } 
 
    return (OS_BITMAP_MASK - CLZ(bitmap)); 
}

2.4 LOS_LowBitGet()獲取狀態(tài)字中為1的最低位

代碼其中CTZ(bitmap)是宏，展開為(__builtin_ctz(value))，這是編譯器內(nèi)置的高效位運算的庫函數(shù)，ctz是count trailing zeros的縮寫，就是統(tǒng)計二進制數(shù)值中低位區(qū)結(jié)尾的全是0的數(shù)目，該結(jié)果就是狀態(tài)字中的1的最低位。

UINT16 LOS_LowBitGet(UINT32 bitmap) 
{ 
    if (bitmap == 0) { 
        return LOS_INVALID_BIT_INDEX; 
    } 
 
    return CTZ(bitmap); 
}

2.5 LOS_BitmapSetNBits()對狀態(tài)字的連續(xù)標志位進行置1操作

可以使用LOS_BitmapSetNBits()函數(shù)對狀態(tài)字的連續(xù)比特位進行置1操作，第一個參數(shù)是需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，第二個參數(shù)是需要置1的bit位開始數(shù)start，第三個參數(shù)是需要置1的數(shù)量numsSet。由于bit位開始數(shù)start并沒有限制在[0,31]，所以實際上設(shè)置的可能是UINT32 *bitmap狀態(tài)字后面的狀態(tài)字，需要根據(jù)業(yè)務(wù)實際情況進行設(shè)置，避免覆寫其他內(nèi)存。同樣，需要置1的數(shù)量numsSet也可能跨多個狀態(tài)字。如圖所示：

我們看下代碼，

⑴處計算出需要操作的狀態(tài)字，其中BITMAP_WORD(start)計算相對狀態(tài)字bitmap需要偏移的數(shù)量，如果start處于區(qū)間[0,31]，BITMAP_WORD(start)等于0，操作的就是狀態(tài)字bitmap。如果start處于區(qū)間[32,63]，BITMAP_WORD(start)等于1，操作的就是狀態(tài)字bitmap后面的第一個狀態(tài)字，以此類推。

⑵處size可以和bit位開始數(shù)start結(jié)合來理解，size就是需要置1的bit位結(jié)束位數(shù)。

⑶處需要置1操作的bit位的位數(shù)。

⑷是對應(yīng)需要置1操作的bit位的掩碼。

⑸處如果條件成立，說明需要置1操作需要跨多個狀態(tài)字進行操作，代碼會一個狀態(tài)字處理完畢，再去處理下一個狀態(tài)字。

⑹處把當前狀態(tài)字的相應(yīng)的bit位進行置1操作，然后執(zhí)行⑺把剩余需要置1的位數(shù)減去已經(jīng)置1的位數(shù)。

⑻處更新bitsToSet和maskToSet，然后指針p指向下一個狀態(tài)字。

⑼處如果需要置1的位數(shù)大于0，并且此時已經(jīng)可以在一個狀態(tài)字內(nèi)完成操作，執(zhí)行⑽處計算需要置1操作的掩碼，從bit開始位到結(jié)束位需要進行置1。

⑾處代碼執(zhí)行置1操作，完成對狀態(tài)字的連續(xù)標志位進行置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()對狀態(tài)字的連續(xù)標志位進行清0操作

可以使用LOS_BitmapClrNBits()函數(shù)對狀態(tài)字的連續(xù)比特位進行清0操作，第一個參數(shù)是需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，第二個參數(shù)是需要清0的bit位開始數(shù)start，第三個參數(shù)是需要清0的數(shù)量numsClear。該函數(shù)是函數(shù)LOS_BitmapSetNBits()的反向操作，代碼解釋可以參考函數(shù)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()函數(shù)獲取從最低有效位開始的第一個0的bit位位數(shù)，第一個參數(shù)是需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，第二個參數(shù)numBits表示最大的位數(shù)，對返回值進行限制，需要在指定的位數(shù)內(nèi)找到符合條件的位數(shù)，否則返回-1。

在看函數(shù)代碼之前，先了解下Ffz()函數(shù)，如下：調(diào)用內(nèi)嵌函數(shù)__builtin_ffsl()可以獲取一個unsigned long類型數(shù)字的二進制形式的從左開始的第一個1的位數(shù)，這個位數(shù)從1開始計數(shù)。比如對于二進制數(shù)字0110，該函數(shù)會返回2。在下面的函數(shù)中，給函數(shù)__builtin_ffsl()傳入的參數(shù)進行了取反，并減去了1，所以Ffz()函數(shù)返回一個數(shù)字從左開始的第一個0的位數(shù)，這個位數(shù)從0開始計數(shù)。

/* find first zero bit starting from LSB */ 
STATIC INLINE UINT16 Ffz(UINTPTR x) 
{ 
    return __builtin_ffsl(~x) - 1; 
}

我們接著看下函數(shù)LOS_BitmapFfz()的代碼。⑴處根據(jù)位數(shù)numBits計算出對應(yīng)的狀態(tài)字的數(shù)量，然后依次循環(huán)每一個狀態(tài)字，⑵處如果狀態(tài)字全為1，則繼續(xù)循環(huán)，否則執(zhí)行⑶。執(zhí)行到⑶說明，，前面有i個狀態(tài)字的各個位全為1。i * BITMAP_BITS_PER_WORD + Ffz(bitmap[i])就表示各個狀態(tài)字的二進制位中，從左到右第一個0的位置。⑷處如果獲取的位數(shù)小于第二個參數(shù)，則返回獲取的位數(shù)，否則返回-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; 
}