(Click the public account above to quickly follow)

Compiled by: Joraku Online – Qiao Yongqi

Click → Learn how to join as a column author

If you need to reprint, send the word “reprint” to see the instructions

This series:

• “Linux Kernel Data Structures: Radix Tree”

• “Linux Kernel Data Structures: Doubly Linked List”

Bitmap and Bit Operations

In addition to various linked and tree data structures, the Linux kernel also provides bitmap interfaces. Bitmaps are widely used in the Linux kernel. The following source code files contain the common interfaces for these structures:

• lib/bitmap.c

• include/linux/bitmap.h

In addition to these two files, there is a specific architecture header file that optimizes bit operations for specific architectures. For the x86_64 architecture, use the following header file:

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

As I mentioned earlier, bitmaps are widely used in the Linux kernel. For example, bitmaps can be used to store the online/offline processors of the system to support CPU hot-plugging; furthermore, bitmaps store allocated interrupt requests during the initialization process of the Linux kernel.

Therefore, this article focuses on analyzing the specific implementation of bitmaps in the Linux kernel.

Bitmap Declaration

Before using the bitmap interface, it is important to understand how the Linux kernel declares bitmaps. One simple way to declare a bitmap is to use an unsigned long array. For example:

unsigned long my_bitmap[8]

The second way is to use the DECLARE_BITMAP macro, which is located in the header file include/linux/types.h:

#define DECLARE_BITMAP(name,bits)

unsigned long name[BITS_TO_LONGS(bits)]

The DECLARE_BITMAP macro has two parameters:

• name – the name of the bitmap;

• bits – the total number of bits in the bitmap

It expands to an array of type unsigned long with a size of BITS_TO_LONGS(bits), where the BITS_TO_LONGS macro converts bits to long type, or calculates how many byte elements are contained in bits:

#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))

For example: DECLARE_BITMAP(my_bitmap, 64) results in:

>>> (((64) + (64) – 1) / (64))

1

And:

unsigned long my_bitmap[1];

After declaring the bitmap, we can use it.

Architecture-Specific Bit Operations

We have looked at the two source code files and one header file that operate on the bitmap interface. The most important and widely used application interface for bitmaps is architecture-specific, located in the header file arch/x86/include/asm/bitops.h.

First, let’s look at two important functions:

• set_bit;

• clear_bit.

I believe it is unnecessary to introduce what these functions do; their names are self-explanatory. Let’s look at the implementation of the functions. Enter the header file arch/x86/include/asm/bitops.h, and you will notice that each function has two types: atomic and non-atomic. Before delving into the implementation of these functions, we need to understand some atomic operations.

In short, atomic operations ensure that two or more operations on the same data cannot be executed concurrently. The x86 architecture provides a set of atomic instructions, such as the xchg instruction and the cmpxchg instruction. In addition to atomic instructions, some non-atomic instructions can use the lock prefix to perform atomic operations. For now, it is sufficient to understand these atomic operations; we can now start considering the set_bit and clear_bit functions.

Let’s start with the non-atomic type functions, which begin with double underscores. As you know, all function definitions are in the header file arch/x86/include/asm/bitops.h, the first function __set_bit:

static inline void __set_bit(long nr, volatile unsigned long *addr)

{

asm volatile(“bts %1,%0” : ADDR : “Ir” (nr) : “memory”);

}

It has two parameters:

• nr – the number of bits in the bitmap

• addr – the address of the bit in the bitmap that needs to be set

Note that the addr parameter is defined as volatile, which tells the compiler that this value may be changed by some address. The __set_bit function is easy to implement. As you can see, it contains a single line of inline assembly code. In this example, the bts instruction selects a specific bit value in the bitmap as the first operand, stores the selected bit value in the CF register, and sets this bit.

Here we can see the usage of nr; what about addr? You may have guessed that the secret lies in ADDR. And ADDR is defined in the header file as a macro that expands the string, adding the +m constraint in front of that address:

#define ADDR BITOP_ADDR(addr)

#define BITOP_ADDR(x) “+m” (*(volatile long *) (x))

In addition to +m, we can see other constraints in the __set_bit function. Let’s take a look at these constraints and try to understand their meanings:

• +m – indicates a memory operand, + indicates that this operand is both an input and output operand;

• I – indicates an integer constant;

• r – indicates a register operand

In addition to these constraints, we also see the keyword memory, which informs the compiler that this code will change values in memory. Next, let’s look at the atomic type function that performs the same function. It appears to be much more complex than the non-atomic type function:

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

}

}

Note that it has the same parameter list as the __set_bit function, but the function is marked with the __always_inline attribute. The __always_inline is a macro defined in include/linux/compiler-gcc.h that simply expands to the always_inline attribute:

#define __always_inline inline __attribute__((always_inline))

This means that the function will be inlined to reduce the size of the Linux kernel image. Next, let’s try to understand the implementation of the set_bit function. The set_bit function begins by checking the number of bits. IS_IMMEDIATE is a macro defined in the same header file that expands to the built-in gcc function:

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

The built-in function __builtin_constant_p returns 1 if this parameter is a constant at compile time; otherwise, it returns 0. There is no need to use the bts instruction to set the bit value because the number of bits is a constant at compile time. Instead, a bitwise OR operation is performed on the known byte address, and the number of bits is masked to make its high bit 1 and others 0. If the number of bits is not a constant at compile time, the operation in the __set_bit function is the same.

The macro CONST_MASK_ADDR:

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

It extends a certain address with an offset to include the known bits. For example, if the address is 0x1000 and the number of bits is 0x9. 0x9 equals one byte plus one bit, the address would be addr+1:

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

‘0x1001’

The macro CONST_MASK represents a known number of bits viewed as bytes, with the high bit being 1 and others being 0:

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

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

‘0b10

Finally, we use a bitwise OR operation. Suppose the address is 0x4097, and we need to set the 0x9 bit:

>>> bin(0x4097)

‘0b100000010010111’

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

‘0b100010’

The ninth bit will be set

Note that all operations are marked with LOCK_PREFIX, which expands to the lock instruction, ensuring that the operation is performed atomically.

As we know, in addition to the set_bit and __set_bit operations, the Linux kernel also provides two inverse functions to clear bits atomically or non-atomically, clear_bit and __clear_bit. These two functions are defined in the same header file and have the same parameter list. Of course, not only are the parameters similar, but the functions themselves are also very similar to set_bit and __set_bit. Let’s first look at the non-atomic function __clear_bit:

static inline void __clear_bit(long nr, volatile unsigned long *addr)

{

asm volatile(“btr %1,%0” : ADDR : “Ir” (nr));

}

As we can see, it has the same parameter list and similar inline assembly function block. The difference is that __clear_bit uses the btr instruction instead of the bts instruction. From the function name, we can see that the function is used to clear a specific bit value at a certain address. The btr instruction is similar to the bts instruction, selecting a specific bit value as the first operand, storing its value in the CF register, and clearing this bit value in the bitmap, with the bitmap as the second operand of the instruction.

The atomic type of __clear_bit is 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));

}

}

As we can see, it is similar to set_bit, with only two differences. The first difference is that it uses the btr instruction to clear the bit, while set_bit uses the bts instruction to store the bit. The second difference is that it uses a mask to clear the bit value in a byte, while set_bit uses the or instruction.

So far, we can set, clear, or perform bitwise operations on any bitmap.

The most common operations for bitmaps are setting and clearing bit values in the Linux kernel. In addition to these operations, it is also necessary to add additional operations for bitmaps. Another widely used operation in the Linux kernel is to determine whether a bitmap has a set bit value. This can be determined using the test_bit macro, which is defined in the header file arch/x86/include/asm/bitops.h, and based on the number of bits, it chooses to call constant_test_bit or variable_test_bit:

#define test_bit(nr, addr)

(__builtin_constant_p((nr))

? constant_test_bit((nr), (addr))

: variable_test_bit((nr), (addr)))

If nr is a constant at compile time, the test_bit function calls constant_test_bit; otherwise, it calls variable_test_bit. Let’s look at the implementation of these functions, starting with 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;

}

The variable_test_bit function has a parameter list similar to that of set_bit. Similarly, we see inline assembly code that executes the bt and sbb instructions. The bt instruction or bit test selects a specific bit value from the bitmap as the first operand, while the bitmap is the second operand, and stores the selected bit value in the CF register. The sbb instruction will remove the first operand from the second operand and remove the CF register value. The specific bit value of the bitmap is written into the CF register, and the sbb instruction calculates CF to be 00000000, and finally writes the result into oldbit.

The constant_test_bit function is similar to 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;

}

It generates a byte with the high bit being 1 and others being 0, and performs a bitwise AND operation on this byte containing the number of bits.

The next widely used bitmap operation is changing the bit values in the bitmap. For this, the Linux kernel provides two helper functions:

• __change_bit;

• change_bit.

You may have guessed that, similar to set_bit and __set_bit, there are two types: atomic and non-atomic. Let’s first look at the implementation of the __change_bit function:

static inline void __change_bit(long nr, volatile unsigned long *addr)

{

asm volatile(“btc %1,%0” : ADDR : “Ir” (nr));

}

It’s easy, isn’t it? The __change_bit function has a similar implementation to __set_bit, with the difference being that the former uses the btc instruction instead of bts. The instruction selects a specific bit value in the bitmap, then places this value into the CF register, and then uses the complement operation to change its value. If the bit value is 1, the changed value will be 0; conversely, it will be 1:

>>> int(not 1)

0

>>> int(not 0)

1

The atomic version of the __change_bit function is the change_bit function:

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

}

}

Similar to the set_bit function, but with two differences. The first difference is that it uses xor operation instead of or; the second difference is that it uses btc instead of bts.

At this point, we have learned the most important bitmap architecture-related operations. Next, let’s take a look at the general bitmap interface.

General Bit Operations

In addition to the architecture-specific interfaces from the header file arch/x86/include/asm/bitops.h, the Linux kernel also provides a general interface for bitmaps. As mentioned earlier, the header file include/linux/bitmap.h, as well as the lib/bitmap.c source code file. However, before looking at the source code file, let’s first look at the header file include/linux/bitops.h, which provides a set of useful macros. Let’s look at some of them:

First, let’s look at the following four macros:

• for_each_set_bit

• for_each_set_bit_from

• for_each_clear_bit

• for_each_clear_bit_from

These macros provide bitmap iterators; the first macro iterates over the set, the second macro does the same but starts from the specified bit in the set. The last two macros do the same but iterate over the cleared bits. Let’s first look at the implementation of the for_each_set_bit macro:

#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))

As you can see, this macro has three parameters, and the loop iterates from the first bit in the set to the last bit, iterating while the bit number is less than the last size, and the loop finally returns the find_first_bit function.

In addition to these four macros, arch/x86/include/asm/bitops.h also provides equivalent iterations for 64-bit or 32-bit.

Similarly, the header file also provides other interfaces for bitmaps. For example, the following two functions:

• bitmap_zero;

• bitmap_fill.

These functions clear the bitmap and fill it with 1. Let’s look at the implementation of the bitmap_zero function:

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

}

}

Similarly, it first checks nbits, the function small_const_nbits is defined in the same header file as follows:

#define small_const_nbits(nbits)

(__builtin_constant_p(nbits) && (nbits <= BITS_PER_LONG))

As you can see, it checks whether nbits is a constant at compile time and whether the value of nbits exceeds BITS_PER_LONG or 64. If the number of bits does not exceed the total amount of long type, it sets it to 0. Otherwise, it calculates how many long type values need to be filled into the bitmap, and of course, we use memset to fill it.

The implementation of the bitmap_fill function is similar to bitmap_zero, except that the bitmap is filled with 0xff or 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);

}

In addition to the functions bitmap_fill and bitmap_zero, the header file include/linux/bitmap.h also provides the function bitmap_copy, which is similar to bitmap_zero, except that it uses memcpy instead of memset. At the same time, it also provides functions such as bitmap_and, bitmap_or, and bitmap_xor for bitwise operations. Considering that the implementation of these functions is easy to understand, we will not elaborate on them here; readers interested in these functions can open the header file include/linux/bitmap.h for study.

Do you find this article helpful? Please share it with more people

Follow “Linux Enthusiasts”

See more Linux technical articles