Series directory

  • introductory
  • The preparatory work
  • BIOS starts in real mode
  • GDT and Protected Mode
  • Exploration of Virtual Memory
  • Load and enter the kernel
  • Display and print
  • The global descriptor table GDT
  • Interrupt handling
  • Virtual memory improvement
  • Implement heap and malloc
  • The first kernel thread
  • Multithreading switch
  • The lock is synchronized with multithreading
  • Implementation of a process
  • Enter user mode
  • A simple file system
  • Load the executable program
  • Implementation of system calls
  • The keyboard driver
  • To run a shell

Black box malloc

So far, all memory has been allocated statically, which is obviously not an efficient way to meet the requirements of subsequent kernel development. Dynamic memory allocation, also known as malloc, is a function that we must implement.

You’ve probably used malloc in C programming before. You know that it allocates a specified amount of memory to return to you, and then you have to manually free it. If you’re still a mystery about what’s going on inside it, or don’t even know where the memory it allocates is, or what the abbreviation for malloc is, you need to take a look.

Don’t worry, the point of this program is to take you through the underlying knowledge and principles. Malloc is really something we use all the time, but probably never really look at in detail. This article will explore and implement a simple malloc library function.

Heap heap

The heap allocated by malloc is on the heap heap, which is not a large top heap but a small top heap. It is simply an area of memory. For example, the heap in user space is between the stack and the program load area:

Implementing malloc in kernel space also requires operating on a large heap. Returning to our kernel space, its current state looks like this:

The first three 4MB have been occupied, starting from 0xC0C00000 is free space, we might as well deldelineate the kernel heap space from here to somewhere, that is, the pink area in the figure, here is our happy planet for memory.

Heap on malloc

The heap is a large pool. What malloc does is dig up memory in the heap. For example, if you need 32 bytes of memory, it finds an unused 32 bytes of memory in the heap and gives it to you.

This seems very simple, but it’s actually a very large and complex subject. There are several core issues that need to be addressed:

  • Set up a data structure to manage the allocation and release of memory blocks, making sure everything is in order.
  • Fast speed, less memory fragmentation;

Starting with the first problem, building a data structure to manage this chunk of memory is not as easy as it looks. The data structure here is not created extra somewhere else, but is itself sitting on the heap, which means it is built in, because this is still an egg problem. Normally, data structures such as linked lists, trees, and hash tables require dynamic memory allocation, but the heap is designed to solve the problem of dynamic memory allocation, which brings the heap back to where it started. So managing the heap’s own data structure is self-weaving within the heap, much like the disk file system we’ll talk about later.

The second problem, which is essentially a performance issue, is not the focus of our project. The first thing we need to ensure is correctness, otherwise all performance is out of the question. Dynamic memory allocation management is a very large and complex topic, and there are various technical papers and implementations dealing with it. The implementation of malloc in the C standard library alone is extremely complex. We are limited to time and our own level, and will not dig too deep in this area, but take the simplest possible approach to implementation.

Kmalloc design ideas

This is the kernel malloc function. This is the kernel malloc function. The core API has the following:

void* kmalloc(uint32 size);
void* kmalloc_aligned(uint32 size);
void free(void* ptr);

KMALLOC_ALIGNED represents a block of memory that is allocated, and the starting address is Page ALIGNED, which is a common requirement in kernel development.

The way I’ve done it here is to follow the recommended approach of the JamesM’s Kernel Development Tutorials, as this should really be the simplest and most retarded approach. However, the above tutorial code I measured down should be a problem, so I use it completely their own ideas to achieve again, and with the test, it is no big problem at present, of course, if there is a bug is inevitable, welcome to correct, the code in SRC /mem/kheap.c.

The idea is simple: store all empty space positions in an ordered array:

This way, when you need to allocate a chunk of memory of a specified size t, you can find the first space in the array that is larger than t, and you can cut a chunk of space of size t from it, and then you can return the rest of the space and keep the array in order.

In fact, arrays do not require order, the purpose of order is to find the appropriate blank block more efficiently. You can go through it one by one, or you can use binary search.

When you want to free a chunk of memory that has been allocated, just put it back in the array. Of course, there are some special cases, such as free areas where neighbors happen to be white space, so you can combine them into one large white space. In the heap, large white space is preferred, of course, because large white space is more sharable, which means fewer fragments, and fragments are annoying.

Therefore, our heap can be planned into two regions:

  1. The ordered array mentioned aboveordered array;
  2. The large area of memory that is used to actually allocate memory is called the memory poolmemory pool;

Each piece of the memory pool (white or gray) is not 100% out to the user, it also contains some information about the color block:

Each area in the memory pool is called a block, which is enlarged as shown in the figure above. It has a header, which is defined as:

struct kheap_block_header {
  uint32 magic;
  uint8 is_hole;
  uint32 size;
} __attribute__((packed));

Among them:

  • magicIt identifies the header;
  • is_holeIndicates whether the block is used (gray) or free (white);
  • sizeIs the actual memory allocated in the block, which is the blue slash in the figure.

Instead, the block has a footer:

struct kheap_block_footer {
  uint32 magic;
  kheap_block_header_t* header;
} __attribute__((packed));

Among them:

  • magicIt’s the same as in the header;
  • headerIt’s a pointer to the header, because in some cases we need to go from footer to the location of the header;

Okay, that’s the end of the design idea part, and then the implementation.

Kmalloc implementation

The ordered array ordered_array

First we need to implement the structure of Ordered Array. We can encapsulate it as an abstract class. My code implementation is in SRC /utils/ Ordered_Array.c for reference.

typedef void* type_t;

typedef struct ordered_array {
  type_t array;
  uint32 size;
  uint32 max_size;
  comparator_t comparator;
} ordered_array_t;

The core concept to realize for this class is that this is an array of Pointers, and the field array represents that array, so it’s a generic type. The class also needs to pass in a Comparator to sort the array:

// An comparator function is used to sort elements.
//
// Returns -1, 0 or 1 if the first element
// is <, == or > the second, respectively.
typedef int32 (*comparator_t)(type_t, type_t);

Specific implementation details are not much said, relatively simple, is the insertion sort;

Also note that the size of this array is dynamically variable, starting at 0 and changing as elements are inserted and removed. The maximum capacity is controlled by max_size;

Heap structure

Next, define the structure of Kheap:

typedef struct kernel_heap {
  ordered_array_t index;
  uint32 start_address;
  uint32 end_address;
  uint32 size;
  uint32 max_address;
} kheap_t;

A few fields about the size of the heap are defined here: start_address and end_address represent the start and end positions of the current heap. Note that the heap starts out small and can grow larger as it is used. Expand the current heap when you can’t find a suitable blank area to allocate memory:

Next, we have the ordered_array field named index, which is used to store all blank blocks in order. Note how index is initialized here. Its internal pointer array starts at the start of the heap. Kheap_Block_Comparator compares the size of two blocks:

kheap_t create_kheap(uint32 start,
                     uint32 end,
                     uint32 max) {
  kheap_t kheap;

  // Initialize the index array.
  kheap.index = ordered_array_create(
      (type_t*)start, KHEAP_INDEX_NUM, &kheap_block_comparator);
  
  // ...

  make_block(start, end - start - BLOCK_META_SIZE, IS_HOLE);
  ordered_array_insert(&kheap.index, (type_t)start);

  // ...
}

The entire heap is initialized with only one large empty block:

The malloc implementation

With that in mind, malloc actually works. Just find a suitable white block from the index array, cut the required memory, turn it into a gray block and allocate it to the user, and then put the remaining white block back into the index array. The core function of this implementation is alloc.

The difficulty with alloc is dealing with the remainder of the cut. It is not always necessary to return the remaining portion to Kheap. At the very least, the remaining portion should be larger than the header + footer, which should be easy to understand.

Also, what’s worth discussing here is that things get complicated when page_align is called, that is, kmalloc_aligned is called. A normal free block is unlikely to happen to be Page aligned, so look inside it to find the first Page aligned location and cut from there:

Dashed lines mark points that Page aligned. One problem with such a split is that there may be areas left behind and in front of the cut, so they need to be returned to the Kheap as well. In my code implementation, the size of the reserved area in front of it must be large enough to hold a full block (larger than header + footer), otherwise cutting will begin at the next page aligned.

Free to implement

The free function can be merged into a large free block if the neighbors are also free:

conclusion

In fact, this chapter is a very independent chapter. Even if it is not included in the Kernel project, it can also be taken as a topic separately. Dynamic memory allocation is a tricky topic, and we’ve taken the simplest approach here, but even if it’s the simplest, it’s still not easy to implement correctly. It took me a few days in development, and a lot of testing, to basically tune it up. Just as with paging, Kheap must be absolutely correct, because it will be our main battleground for allocating memory in later development.