Frame Allocator

[Ananta98]

Hello I'm new in rust osdev. In your article about paging, frame allocation using Area frame allocator. I want to use bitmap allocator, but the problem is memory region not in u32 so how to convert Area Frame allocator to bitmap allocator so i can implement deallocation in frame allocator.

[phil-opp]

For a bitmap allocator, you first need to reserve a portion of memory to store the bitmap. If one bit represents one physical frame, you need max_phys_memory_addr / 4096 / 8 bytes for this. Then you iterate through all available frames and set the corresponding bits in that memory area (e.g. true if the frame is unused).

For allocating, you can then iterate through this bitmap to look for a bit that is true. From the address of the bit, you can then calculate the corresponding frame address. To speed things up, you can look at 64 bits at once instead of iterating through the bits one by one. To do that, you interpret a part of the bitmap as u64 number. If the number is zero it means that no bits are set in this part of the bitmap. If it's non-zero, there are some bits set to true. For example, the number 9 means that bit 0 and bit 3 are set.

To free a frame again, you need to calculate the corresponding bit number in the bitmap and set that bit to true again.

[Ananta98]

impl FrameDeallocator for BootInfoFrameAllocator{ unsafe fn deallocate_frame(&mut self, frame: PhysFrame) { let index = frame.start_address().as_u64() / Size4KiB::SIZE; if index == 0 { self.next = 0; } else { self.next = index as usize - 1; } } }
is that correct my code to deallocate frame from your blog post? Because i still confuse to deallocate frame from your code.

[phil-opp]

The problem is that the frames might be freed in an arbitrary order. So frame 0 might be freed while frame 3 is still in use. So you can only move the next counter back when it's really the last allocated frame that's being freed. Otherwise, you need some additional data structure (such as a bitmap or the Vec I mentioned) to keep track of the freed frame.

[GuillaumeDIDIER]

Perhaps a data structure like those used to implement heap management can be efficient ?
Like this I could use a bitmap (to easily lookup if a page is free or not) + doubly linked lists of free page extents.

When freeing a page you flip a bit in the bitmap, then look at adjacent page bits. If some of those are free, then you can alter your linked list (I'd store it within the pages) to merge the extents. When you seek a extent long enough for x pages, you can go through the linked lists (you can have different size bins) until you find a suitable one. (And otherwise is probably time to complain about being out of memory or swap someone to to disk).

[Ananta98]

Maybe I want to start with bitmap allocator thanks for this. Hmmm... I want to ask when blog version 3 release @phil-opp ? Do you teach Filesystem like simple FAT or EXT-2, more thread and processes, and basic GUI. Seriously I love your blog. I've looked osdev wiki for me confusing, and many OSdev Blog like brokenthorn which is really great but not updated for so long. Thank you.

[phil-opp]

I'm only writing on the blog in my free time, so I can't give you an estimate when it will be ready. However, it will probably take some longer time until I can tackle threads and processes. I don't have any plans for filesystems yet, but it sure is an interesting topic.

Great to hear that you like the blog :).

[Ananta98]

Maybe I want to ask again about frame allocator. I've finally create frame allocator but is that correct ? (Code link : https://github.com/Ananta98/PetraOS/tree/master/src). Frame Allocator code in folder "mm/frame_allocator.rs". And I still confuse with my ATA, in identify function i've got error double fault exception why ? For my ATA code in "drivers/ata.rs". Thank you if you want to help.

[phil-opp]

I don't have the time to look through your code at the moment, sorry! But perhaps someone else will take a look.