鴻蒙輕內(nèi)核A核源碼分析系列二：數(shù)據(jù)結(jié)構(gòu)-位圖操作
想了解更多內(nèi)容，請(qǐng)?jiān)L問(wèn)：
51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)
在進(jìn)一步分析之前，本文我們先來(lái)熟悉下OpenHarmony鴻蒙輕內(nèi)核提供的位操作模塊，在互斥鎖等模塊對(duì)位操作有使用。位操作是指對(duì)二進(jìn)制數(shù)的bit位進(jìn)行操作。程序可以設(shè)置某一變量為狀態(tài)字，狀態(tài)字中的每一bit位(標(biāo)志位)可以具有自定義的含義。
1 位操作的宏定義
位操作模塊提供對(duì)32位無(wú)符號(hào)整數(shù)數(shù)值的bit位進(jìn)行操作，bit位取值為0-31，以0開(kāi)始計(jì)算，從左向右，第0位，第1位。。。第31位等。⑴處定義的宏OS_BITMAP_MASK如下，也就是十進(jìn)制31。如果傳入的比特位pos大于31，會(huì)通過(guò)邏輯與運(yùn)算截?cái)?pos & OS_BITMAP_MASK)，只取低5位，確保不會(huì)大于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計(jì)算出需要操作第幾個(gè)狀態(tài)字，由于計(jì)算狀態(tài)字的使用的是UINTPTR，狀態(tài)字可以是32位、也可以是64位。后文，我們默認(rèn)以32位進(jìn)行講解。宏BITMAP_FIRST_WORD_MASK傳入的參數(shù)是位操作的開(kāi)始bit位數(shù)，用于計(jì)算需要進(jìn)行位操作的掩碼，從開(kāi)始位全部是1，宏BITMAP_LAST_WORD_MASK傳入的參數(shù)是位操作的結(jié)束bit位數(shù)，用于計(jì)算需要進(jìn)行位操作的掩碼，結(jié)束位之前全部是1。宏BITMAP_NUM_WORDS傳入位數(shù)，計(jì)算狀態(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)核的位操作模塊提供標(biāo)志位的置1和清0操作，可以改變標(biāo)志位的內(nèi)容，同時(shí)還提供獲取狀態(tài)字中標(biāo)志位為1的最高位和最低位的功能。用戶也可以對(duì)系統(tǒng)的寄存器進(jìn)行位操作。位操作提供了7個(gè)API，進(jìn)行置1、清0、獲取為1的最高、最低位等操作，如下：
下面，我們剖析下位操作的源代碼。
2.1 LOS_BitmapSet()對(duì)狀態(tài)字的某一標(biāo)志位進(jìn)行置1操作
對(duì)狀態(tài)字的某一標(biāo)志位進(jìn)行置1操作。我們先看看傳入的參數(shù)，需要的2個(gè)參數(shù)分別是：需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，需要改變的bit位位數(shù)UINT16 pos。
代碼很簡(jiǎn)單，首先進(jìn)行基礎(chǔ)的校驗(yàn)，如果狀態(tài)字為空，則返回。然后計(jì)算pos & OS_BITMAP_MASK，只取二進(jìn)制的低5位，最大位值為31，避免左移的時(shí)候發(fā)生溢出。1U << (pos & OS_BITMAP_MASK)就是需要改變內(nèi)容的狀態(tài)字的bit位，通過(guò)按位或運(yùn)算設(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()對(duì)狀態(tài)字的某一標(biāo)志位進(jìn)行清0操作
對(duì)狀態(tài)字的某一標(biāo)志位進(jìn)行清0操作，代碼和置1操作對(duì)應(yīng)，比較簡(jiǎn)單，~(1U << (pos & OS_BITMAP_MASK))表示需要改變內(nèi)容的狀態(tài)字的bit位為0，其余位為1，然后通過(guò)按位與運(yùn)算設(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)是宏，展開(kāi)為(__builtin_clz(bitmap))，這是編譯器內(nèi)置的高效位運(yùn)算的庫(kù)函數(shù)，clz是count leading zeros的縮寫，就是統(tǒng)計(jì)二進(jìn)制數(shù)值中高位區(qū)開(kāi)頭的全是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)是宏，展開(kāi)為(__builtin_ctz(value))，這是編譯器內(nèi)置的高效位運(yùn)算的庫(kù)函數(shù)，ctz是count trailing zeros的縮寫，就是統(tǒng)計(jì)二進(jìn)制數(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()對(duì)狀態(tài)字的連續(xù)標(biāo)志位進(jìn)行置1操作
可以使用LOS_BitmapSetNBits()函數(shù)對(duì)狀態(tài)字的連續(xù)比特位進(jìn)行置1操作，第一個(gè)參數(shù)是需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，第二個(gè)參數(shù)是需要置1的bit位開(kāi)始數(shù)start，第三個(gè)參數(shù)是需要置1的數(shù)量numsSet。由于bit位開(kāi)始數(shù)start并沒(méi)有限制在[0,31]，所以實(shí)際上設(shè)置的可能是UINT32 *bitmap狀態(tài)字后面的狀態(tài)字，需要根據(jù)業(yè)務(wù)實(shí)際情況進(jìn)行設(shè)置，避免覆寫其他內(nèi)存。同樣，需要置1的數(shù)量numsSet也可能跨多個(gè)狀態(tài)字。如圖所示：
我們看下代碼，
⑴處計(jì)算出需要操作的狀態(tài)字，其中BITMAP_WORD(start)計(jì)算相對(duì)狀態(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后面的第一個(gè)狀態(tài)字，以此類推。
⑵處size可以和bit位開(kāi)始數(shù)start結(jié)合來(lái)理解，size就是需要置1的bit位結(jié)束位數(shù)。
⑶處需要置1操作的bit位的位數(shù)。
⑷是對(duì)應(yīng)需要置1操作的bit位的掩碼。
⑸處如果條件成立，說(shuō)明需要置1操作需要跨多個(gè)狀態(tài)字進(jìn)行操作，代碼會(huì)一個(gè)狀態(tài)字處理完畢，再去處理下一個(gè)狀態(tài)字。
⑹處把當(dāng)前狀態(tài)字的相應(yīng)的bit位進(jìn)行置1操作，然后執(zhí)行⑺把剩余需要置1的位數(shù)減去已經(jīng)置1的位數(shù)。
⑻處更新bitsToSet和maskToSet，然后指針p指向下一個(gè)狀態(tài)字。
⑼處如果需要置1的位數(shù)大于0，并且此時(shí)已經(jīng)可以在一個(gè)狀態(tài)字內(nèi)完成操作，執(zhí)行⑽處計(jì)算需要置1操作的掩碼，從bit開(kāi)始位到結(jié)束位需要進(jìn)行置1。
⑾處代碼執(zhí)行置1操作，完成對(duì)狀態(tài)字的連續(xù)標(biāo)志位進(jìn)行置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()對(duì)狀態(tài)字的連續(xù)標(biāo)志位進(jìn)行清0操作
可以使用LOS_BitmapClrNBits()函數(shù)對(duì)狀態(tài)字的連續(xù)比特位進(jìn)行清0操作，第一個(gè)參數(shù)是需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，第二個(gè)參數(shù)是需要清0的bit位開(kāi)始數(shù)start，第三個(gè)參數(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()獲取從最低有效位開(kāi)始的第一個(gè)0的bit位
可以使用LOS_BitmapFfz()函數(shù)獲取從最低有效位開(kāi)始的第一個(gè)0的bit位位數(shù)，第一個(gè)參數(shù)是需要改變bit位內(nèi)容的狀態(tài)字UINT32 *bitmap，第二個(gè)參數(shù)numBits表示最大的位數(shù)，對(duì)返回值進(jìn)行限制，需要在指定的位數(shù)內(nèi)找到符合條件的位數(shù)，否則返回-1。
在看函數(shù)代碼之前，先了解下Ffz()函數(shù)，如下：調(diào)用內(nèi)嵌函數(shù)__builtin_ffsl()可以獲取一個(gè)unsigned long類型數(shù)字的二進(jìn)制形式的從左開(kāi)始的第一個(gè)1的位數(shù)，這個(gè)位數(shù)從1開(kāi)始計(jì)數(shù)。比如對(duì)于二進(jìn)制數(shù)字0110，該函數(shù)會(huì)返回2。在下面的函數(shù)中，給函數(shù)__builtin_ffsl()傳入的參數(shù)進(jìn)行了取反，并減去了1，所以Ffz()函數(shù)返回一個(gè)數(shù)字從左開(kāi)始的第一個(gè)0的位數(shù)，這個(gè)位數(shù)從0開(kāi)始計(jì)數(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計(jì)算出對(duì)應(yīng)的狀態(tài)字的數(shù)量，然后依次循環(huán)每一個(gè)狀態(tài)字，⑵處如果狀態(tài)字全為1，則繼續(xù)循環(huán)，否則執(zhí)行⑶。執(zhí)行到⑶說(shuō)明，，前面有i個(gè)狀態(tài)字的各個(gè)位全為1。i * BITMAP_BITS_PER_WORD + Ffz(bitmap[i])就表示各個(gè)狀態(tài)字的二進(jìn)制位中，從左到右第一個(gè)0的位置。⑷處如果獲取的位數(shù)小于第二個(gè)參數(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;
- }
小結(jié)
本文帶領(lǐng)大家一起剖析了鴻蒙輕內(nèi)核的位操作模塊的源代碼。
想了解更多內(nèi)容，請(qǐng)?jiān)L問(wèn)：
51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)
