Bitmaps in NanoVMs

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)

static inline void bitmap_set(bitmap b, u64 i, int val);
static inline boolean bitmap_get(bitmap b, u64 i);

bitmap_set(pepe, 0, 0);

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

p = bitmap_range_get_first(pepe, 0, present_processors);

bitmap_extended(pepe, presented_processor + 1);

bitmap_clone(bitmap b)

bitmap_copy(bitmap dst, bitmap src)

bitmap_bitmap_wrap(heap h, u64 * map, u64 length)

bitmap_unwrap(bitmap b)

deallocate_bitmap()