Introduction
This article is an overview of bitmaps, which is a data-structure heavily used in the kernel. NanoVMs provides a dedicated API to handle bitmaps. In the following, we present the API to instantiate bitmaps and how this API is adapted to deal with different use-cases. Also, we present the kernel’s data-structures that are represented by using bitmaps.
Overview
Before going deeper into bitmaps, we overview some of the characteristics of this data-structure. Generally speaking, a bitmap is an array of bits to store binary variables. A binary variable can be either ‘0’ or ‘1’. In C language, a ‘0’ is identified as “False” whereas any value greater than ‘0’ is identified as “True”. Bits are stored in groups of bytes in which each byte contains 8 bits. For a bitmap with only 1 bit, we require to allocate at least one byte of memory to store it.
Bitmaps are often used to keep track of variables that can be either True or False. For example, the kernel may keep track of the processors that are idle by simply defining a bitmap in which each bit represents a processor. In this case, elements that are set, identify an idle processor. As we can see, we only require one bit per processor thus eight processors take one byte of memory. Generally speaking, an array of N binary variables requires only (N / 8) bytes of memory. In this sense, bitmaps are interesting because they consume little memory and you can access them very quickly.
Let’s overview the typical operations over a bitmap. To do this, let’s assume a one byte bitmap that contains eight bits with index from [0..7]. Operations over bit rely on bitwise operators like AND(&), OR(|) and SHIFT (<< and>>). For example, to set the i-th bit in a bitmap, we only need to do:
Bitmap = Bitmap | ( 1 << i)
Similarly, to clear the i-th bit in a bitmap, we have only to:
Bitmap = Bitmap & (~(1 << i));
To check if a bit is set, we can simple do it by:
If ((Bitmap >> i) & 1) {
// true
Else {
// false
}
As we see, operations over a bitmap are always O(1). The only operation that is O(n) is when we look for an element.
Bitmaps in the Kernel
Bitmaps are used in many places in the components that make a kernel like the scheduler or the filesystem. In this section, we just review some of them:
- When a thread is created, a bitmap named affinity is created in the thread structure to track the processors the thread has affinity to. Then, when the scheduler has to choose which processor schedules the thread, it first checks this bitmap depending on what processor is free.
- The scheduler keeps track of the processors that are present by using a bitmap named idle_cpu_mask (see src/kernel/schedule.c:288). This prevents the scheduler from choosing a processor that is disabled.
- Bitmaps are often used to represent resources that require to be allocated dynamically. For example, context switching by hardware requires a TSS descriptor per process. Each TSS descriptor needs an entry in the Global Descriptor Table (GDT). The kernel may keep track of the entries that are busy by using a bitmap. When a new entry is required, the kernel just looks for the first clear bit in the bitmap and sets it to mark it busy.
- Bitmaps are also often used when implementing a filesystem. For example, EXT3 keeps a bitmap for the state of the inodes. The inodes that have been assigned are set whereas those free are clear.
API
When using bitmaps in the kernel code, the implementation is a bit more complicated than we have just shown. This is because bitmaps may be larger and operations like allocation and access need to be fast. In the following, we present the current API that is implemented in NanoVMs to handle bitmaps. We begin by presenting the API to build a bitmap and then the different possible operations on it.
To instantiate a new bitmap, we use the function:
bitmap_allocate_bitmap(u64 length)
*bitmap
pepe = allocate_bitmap(present_processors);
The function returns a bitmap that has all its bits cleared. Note that to optimise the access to the bitmap, the actual number of bits allocated is always rounded up to the nearest cache-line length. For example, if present_processors is 100 and the cache-line is 64 bits, the function would allocate 128 bits.
After a bitmap is created, we may be interested to initialise it by setting a range of the bitmap to ‘1’. To do this, there are two functions:
u64 bitmap_alloc(bitmap b, u64 size);
u64 bitmap_alloc_within_range(bitmap b, u64 nbits, u64 start, u64 end);
bitmap_alloc searches a bitmap for a range of nbits consecutive bits that are all cleared, and if such a range is found, sets all bits in the range and returns the first bit of the range. For example, to initialise to ‘1’ the bitmap that we have just created, we write:
bitmap_alloc (pepe, present_processors)
This is the same that using bitmap_alloc_within_range:
bitmap_alloc_within_range(pepe, present_processors, 0, pepe->maxbits)
After a bitmap is created and initialised, we often require to set a bit or get a bit. These operations are done by the following functions:
static inline void bitmap_set(bitmap b, u64 i, int val);
static inline boolean bitmap_get(bitmap b, u64 i);
bitmap_set just sets or clears the i-th bit depending on the value of val. If val is True, the bit is set; otherwise, the bit is clear. For example, if we want to clear the bit 0 of the pepe bitmap, we just do:
bitmap_set(pepe, 0, 0);
bitmap_get allows us to get the value of the i-th bit, we let the reader experiment with this function. In case we require to set or get a bit atomically, the API provides the functions
bitmap_set_atomic
bitmap_test_and_set_atomic
bitmap_foreach_set(pepe, j) {
if (bitmap_get(pepe, j)) {
printf(‘processor: %d is presented\n’, i);
}
}
Conversely, instead of iterating over the whole bitmap, we may require to get the first processor that is present. To do this, we use the function bitmap_range_get_first() to get the first bit that is set:
p = bitmap_range_get_first(pepe, 0, present_processors);
In p, we get the position of the first bit that is set in the pepe bitmap. For some use-cases, we may require to extend the length of an existing bitmap to add a new element. For example, if a new processor is turned on, the number of presented_processor is incremented by one so the bitmap needs to be one bit longer. To do this, we can simply use the following function:
bitmap_extended(pepe, presented_processor + 1);
This function allows a developer to extend a bitmap only limited by available memory. During extension, the bitmap is reallocated with a size that is a multiple of ALLOC_EXTEND_BITS, i.e., 4096 bits.
In the kernel, we may also need to clone and to copy a bitmap. This is done by the functions:
bitmap_clone(bitmap b)
bitmap_copy(bitmap dst, bitmap src)
In some cases, the bitmap already exists and we would like to reuse it. This is done with
bitmap_bitmap_wrap(heap h, u64 * map, u64 length)
bitmap_unwrap(bitmap b)
To release the memory allocated for a bitmap, the developer uses the function:
deallocate_bitmap()
More resources
In this article, we have presented a brief overview of bitmaps and how they are used by different components of the kernel to efficiently store binary information. We have shown the nanoVMs API to manipulate bitmaps. This API allows users to deal with different use-cases. If you want to understand better how to use bitmaps in nanoVMs, you can check the source code of the unit tests for bitmaps at /test/unit/bitmap_test.c.
Matias E. Vara Larsen