Shulou(Shulou.com)06/01 Report--

This article mainly introduces the "bit array and bit operation in the Linux kernel". In the daily operation, I believe that many people have doubts about the bit array and bit operation in the Linux kernel. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about the bit array and bit operation in the Linux kernel. Next, please follow the editor to study!

Bit array and bit operation in Linux kernel

In addition to different chained and tree-based data structures, the Linux kernel also provides API for bitmaps (or bitmaps). Bit arrays are widely used in the Linux kernel, and the following source code files contain a generic API for use with such a structure:

Lib/bitmap.c

Include/linux/bitmap.h

In addition to these two files, there are architecture-specific header files that provide optimized bit operations for a particular architecture. We will explore the x86room64 architecture, so in our example, it will be

Arch/x86/include/asm/bitops.h

Header file. As I wrote above, bitmaps are widely used in the Linux kernel. For example, a bit array is often used to hold a set of online / offline processors so that the system supports hot-swappable CPU (you can read more about it in the cpumasks section), and a bit array (bit array) can save a set of allocated interrupt processing during Linux kernel initialization, etc.

Therefore, the main purpose of this section is to understand how bit arrays (bit array) are implemented in the Linux kernel. Let's start now.

Bit array declaration

Before we start looking at the API of a bitmap operation, we must know how to declare it in the Linux kernel. There are two general ways to declare an array of bits. * A simple way to declare an array of bits is to define an array of unsigned long, for example:

Unsigned long my_bitmap [8]

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

# define DECLARE_BITMAP (name,bits)\ unsigned long name [bits _ TO_LONGS (bits)]

We can see that the DECLARE_BITMAP macro uses two parameters:

Name-Bitmap name

Bits-Bitmap median

And simply use the BITS_TO_LONGS (bits) element to expand the definition of the unsigned long array. The BITS_TO_LONGS macro converts a given number of bits to the number of long, in other words, to calculate how many 8-byte elements are in the bits:

# define BITS_PER_BYTE 8 # define DIV_ROUND_UP (n) ((n) + (d)-1) / (d) # define BITS_TO_LONGS (nr) DIV_ROUND_UP (nr, BITS_PER_BYTE * sizeof (long))

Therefore, for example, DECLARE_BITMAP (my_bitmap, 64) will produce:

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

And:

Unsigned long my_bitmap [1]

Once we are able to declare an array of bits, we can use it.

Architecture-specific bit operations

We have looked at the pair of source and header files mentioned above, which provide API for bit array operations. The important and widely used bit array API is architecture-specific and is located in the mentioned header file arch/x86/include/asm/bitops.h.

First, let's look at the two most important functions:

Set_bit

Clear_bit.

I don't think it's necessary to explain the functions of these functions. Judging from their names, this is clear. Let's look directly at their implementation. If you browse the arch/x86/include/asm/bitops.h header file, you will notice that each of these functions has both atomic and non-atomic variants. Before we start digging into the implementation of these functions, we must first know something about atomic operations.

In short, atomic operations ensure that two or more operations do not execute the same data concurrently. The x86 architecture provides a series of atomic instructions, such as xchg, cmpxchg, and so on. In addition to atomic instructions, some non-atomic instructions can be atomic with the help of lock instructions. Now that you know enough about atomic operations, we can move on to the implementation of the set_bit and clear_bit functions.

Let's first consider the non-atomic variant of the function. The names of non-atomic set_bit and clear_bit begin with a double underscore. As we know, all of these functions are defined in the arch/x86/include/asm/bitops.h header file, and the * functions are _ _ set_bit:

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

As we can see, it uses two parameters:

Nr-tags in an array of digits (LCTT: starting with 0)

Addr-the address of the array of bits we need to set

Note that the addr parameter is defined using the volatile keyword to tell the compiler that the variable pointed to at the given address may be modified. The implementation of _ _ set_bit is fairly simple. As we can see, it contains only one line of inline assembly code. In our example, we use the bts instruction to select the bit specified by a * Operand (nr in our example) from the bit array, store the value of the selected bit into the CF flag register and set that bit. (that is, the position specified by nr is 1).

Notice that we've learned how to use nr, but here's another parameter, addr! You may have guessed that the secret is in ADDR. ADDR is a macro defined in the same header file that expands into a string containing a given address and + m constraint:

# 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 look at and try to understand what they mean:

+ m-represents memory operands, where + indicates that the given operands are input and output operands

I-denotes integer constant

R-represents register Operand

In addition to these constraints, we can also see the memory keyword, which tells the compiler that this code modifies variables in memory. So far, now let's look at the same atomic variant function. It looks more complex than a non-atomic (non-atomic) variant:

Static _ always_inline void set_bit (long nr, volatile unsigned long * addr) {if (IS_IMMEDIATE (nr)) {asm volatile (LOCK_PREFIX "orb% 1 orb% 0": CONST_MASK_ADDR (nr, addr): "iq" ((U8) CONST_MASK (nr)): "memory") } else {asm volatile (LOCK_PREFIX "bts% 1 Magi% 0": BITOP_ADDR (addr): "Ir" (nr): "memory");}}

LCTT: BITOP_ADDR is defined as # define BITOP_ADDR (x) "= m" (* (volatile long *) (x)), and ORB is byte bitwise or.)

First of all, notice that this function uses the same set of parameters as _ _ set_bit, but with the extra _ _ always_inline attribute tag. _ _ always_inline is a macro defined in include/linux/compiler-gcc.h and is simply expanded to the always_inline property:

# define _ always_inline inline _ attribute__ ((always_inline))

This means that this function is always inline to reduce the size of the Linux kernel image. Now let's try to understand the implementation of the set_bit function. First we check the number of bits given at the beginning of the set_bit function. The IS_IMMEDIATE macro is defined in the same header file and expanded as a call to the gcc built-in function:

# define IS_IMMEDIATE (nr) (_ _ builtin_constant_p (nr))

If the given parameter is a constant known at compile time, the _ _ builtin_constant_p built-in function returns 1 and 0 otherwise. If the given number of bits is a constant known at compile time, we do not need to use inefficient bts instructions to set bits. We can simply perform a bitwise or operation on the byte pointed to by a given address, whose byte contains a given bit, and the number of mask bits represents a mask with a high bit of 1 and other bits of 0. In other cases, if the given tag is not a constant known at compile time, we do the same thing as the _ _ set_bit function. CONST_MASK_ADDR macros:

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

Expand to a given address with an offset to the byte that contains the location, for example, we have the address 0x1000 and the tag 0x9. Because 0x9 stands for one byte + one bit, our address is addr + 1:

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

The CONST_MASK macro represents our given tag as bytes, the corresponding bit of the tag is the high bit 1, and the other bits are 0:

# define CONST_MASK (nr) (1 > > bin (1 > > bin (0x4097) '0b100000010010111' > bin ((0x4097 > > 0x9) | (1 _ BITOPS_LONG_SHIFT]))! = 0;}

It generates a byte with a tag corresponding to the high bit 1 and the other bits with 0 (as we can see in CONST_MASK) and applies bitwise to the byte containing the given bit.

The next widely used bit array related operation is to change the bits in a bit array. To do this, the Linux kernel provides two helper functions:

_ _ change_bit

Change_bit.

As you may have guessed, take the examples of set_bit and _ _ set_bit, which are atomic and non-atomic versions, respectively. First, let's look at the implementation of the _ _ change_bit function:

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

It's pretty simple, isn't it? the implementation of _ _ change_bit is the same as _ _ set_bit, except that we replace the bts instruction with btc. The instruction selects a location from a given location array, stores the value of the bit in CF and changes its value using an inverse operation, so that the bit with a value of 1 becomes 0, and vice versa:

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

The atomic version of _ _ change_bit 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 addr% 0": CONST_MASK_ADDR (nr, addr): "iq" ((U8) CONST_MASK (nr) } else {asm volatile (LOCK_PREFIX "btc% 1 Magi% 0": BITOP_ADDR (addr): "Ir" (nr));}}

It is very similar to the set_bit function, but there are two differences. The difference is a xor operation rather than an or. The second difference is "btc" rather than "bts". The second difference is btc.

Now that we understand the most important system-specific bitarray operations, it's time to take a look at the general bitmap API.

Universal bit operation

In addition to the system-specific API in arch/x86/include/asm/bitops.h, the Linux kernel provides a generic API for manipulating an array of bits. As we learned at the beginning of this section, we can find it in the include/linux/bitmap.h header file and the lib/bitmap.c source file. But before looking at these source files, let's take a look at the include/linux/bitops.h header file, which provides a series of useful macros, and let's take a look at some of them.

First, let's take a look at the following four macros:

For_each_set_bit

For_each_set_bit_from

For_each_clear_bit

For_each_clear_bit_from

All of these macros provide iterators that iterate through certain sets of bits in the bit array. * Macro iterates over the bits that are set. The same is true for the second macro, but it starts with a certain bit. * * the two macros do the same, but iterate over the bits that have been cleared. Let's look at 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 we can see, it takes three parameters and expands into a loop that starts with * settings that are returned as a result of the find_first_bit function and ends with * settings less than a given size.

In addition to these four macros, arch/x86/include/asm/bitops.h also provides API for 64-bit or 32-bit variable loops, and so on.

The next header file provides the API for the array of operands. For example, it provides the following two functions:

Bitmap_zero

Bitmap_fill.

They can clear an array of bits and fill an array of bits with 1, respectively. 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);}}

First of all, we can see the inspection of nbits. Small_const_nbits is a macro defined in the same header file:

# define small_const_nbits (nbits)\ (_ _ builtin_constant_p (nbits) & & (nbits)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.