Bitmap page allocator in C

Question

Bitmap page allocator that scans the bitmap linearly looking for size amount of pages. Everytime it founds a free page, it check if the next size pages are also free, if yes it marks them as allocated and returns a pointer to the first page

uint64_t *bitmap;
#define setpage(p, x) bitmap[p / 64] = x << (p % 64) | bitmap[p / 64]
#define getpage(p) bitmap[p / 64] & ((1 << (p % 64)))
void *palloc(int size) {
 struct limine_hhdm_response *hhdm_res = hhdm_req.response;
 int page = PGSIZE, p = 0;
 while (1) {
 // if free 
 if ((getpage(page)) == 0) {
 // check that there are 'size' amount of pages free 
 for (p = page; p < (size + page); ++p) {
 if ((getpage(p)) == 1)
 break;
 }
 // mark the pages as used
 if (p == size + page) {
 for (p = page; p < (size + page); ++p) 
 setpage(p, 1);
 return (void*) hhdm_res + (page * PGSIZE);
 }
 };
 page++;
 };
} 
```

Answer 1

There are several issues with this code:

• Avoid macros where possible: setpage() and getpage() can easily be implemented as regular functions. See this StackOverflow question for an overview of the issues with macros.
• Buffer overflows: you never check if you are accessing past the end of the bitmap. If you are out of memory, or even if you have enough memory but it is so fragmented you can't find a large enough bit of contiguous free space, you will read and write past the end of bitmap[] and probably return a pointer to memory which doesn't exist or is already in use by something else.
• It can be made more efficient: checking the bitmap bit for bit is slow for large allocations. There are several ways to check many bits at a time. For example, if a given uint64_t is 0, you know that block of 64 pages is completely free, and if it is UINT64_MAX, you know every page in that block is in use. You also have functions like ffs() that allow you to find the first non-zero bit in one go (or you can write your own using compiler builtins, intrinsics or inline assembly).
• If you have a lot of pages, linearly scanning the bitmap can become a bottleneck for allocations.
• The cast in the return statement is not necessary.

• runningupthatroad: why avoid macros?
• G. Sliepen: I added a link to my answer to another post discussing macros vs. functions. In short, there are several issues with macros that make mistakes easy, and they are harder to debug.