Today I realized that the kernel will evnetually need a way to allocate memory in a unit of pages. So, naturally, I made a special memory allocator that allots memory in the unit of page. It's based on special bitmap algorithm that I come up with, which only takes 512kBs of bitmap memory to manage the entire 8GBs of memory in 4KB page size.(That's only 0.061% of the entire 8GBs of memory!)

Basically, the gist of it is this: stripping out all the unnecessary information, we only need a indicator that the page is allocated, and another indicator that tells the difference between one contiguous allocated region and another. That's all there is to govern all the pages.

And because we only need to distinguish the region by its adjacent regions(which is only two in this case), we only need three distinguisher(because the adjacent regions are only two, and all of them are linearly placed) to separate out the regions.

Like this :

     |>====== one byte =======<|  |>====== one byte =======<|  |>====== one byte =======<|  |>====== one byte =======<|
Bit   0  1   2  3   4  5   6  7    0  1   2  3   4  5   6  7    0  1   2  3   4  5   6  7    0  1   2  3   4  5   6  7  
    +------+------+------+------++------+------+------+------++------+------+------+------++------+------+------+------+
    |  01  |  01  |  01  |  10  ||  10  |  10  |  10  |  10  ||  11  |  11  |  11  |  11  ||  11  |  00  |  00  |  00  |
    +------+------+------+------++------+------+------+------++------+------+------+------++------+------+------+------+
     <==================> <=================================>  <=================================> <==================>
         one allocated         another allocated region               yet another allocated              Free Area
            region                                                           region

    +--------------------+-----------------------------------+------------------------------------+--------------------+
    |      region 1      |              region 2             |              region 3              |        Free        |
    +--------------------+-----------------------------------+------------------------------------+--------------------+

In the physical memory, this bitmap will look like(in a little-endian architecture) : 
0x95        0xAA        0xff        0x03
0b10010101  0b10101010  0b11111111  0b00000011

You can think of it as painting the regions without having same colors touching each other, but in this case, those colors are small bitmaps!

Problem in my implementation

As of writing this journal(Yes, I'm lazy and I'm writing this like 10 months ago), I realized that I only used two distinguisher(0b01, 0b10) to indicate the difference between the region. This wouldn't work, since having only two "colors" can't account for a situation like this :

Say, in the given bitmap below, you are given a request to allocate new page with size of two :

    +------+------+------+------+------+------+------+------+
    |  01     01     01  |  00     00  |  10     10     10  |
    +------+------+------+------+------+------+------+------+
                          <===========>
                    This region will be given

In this situation, if you have only two colors that you can paint, none of the two "colors" would make the distinction between the adjacent regions. Also, my implementation of this algorithm only checked the adjacent page block on the only one side, which inadvertently "merges" the newly allocated page into another, like shown in the picture :

Aside from this apparent issue that I found out like 10 months after coming up with this algorithm.. I think this works fine for spatially efficient page allocator! I'm thinking of using this as a general page allocator for the kernel. Check out the github for detailed implementation! It's not really that complicated than it seems.. (I hope)