OSDev.org

Well, in the current build of my OS, I use a bitmap that defines what 4kb pages are free or used. I've also noticed that if only the last little bit of memory would be free, it would go searching through all those bits in the bitmap (32-bits at a time, however) and would waste a lot of time, especially when large amounts of memory are being allocated all at once (like when you first open a 5mb program, for instance). So I have a pointer that tells me where the last free set of pages was found, which is filled in when we pass over a free page right in front of the one we just gave out (during an allocation), as usually this will be the case.

What this lacks for speed, it makes up for in the relatively small space it takes up - for a full 4GB, only 128KB.

Now, I've decided I'd look at stack-based systems, in which it will push the addresses of all the open pages onto one big stack, and simply pop to allocate a page, or push to free a page. For 4GB, it takes up a full 4mb - that's 1024th of your memory. But it is very fast. If you were to write it in ASM, the number of clock cycles (not including the amount to do call and ring change, if needed, as the above would have to also) would probably be under 10, which is very fast.

What it lacks in efficency, it makes up for in speed.

So I think to myself, on top of all this, the second is also very easy to implement. Amongst the commenting in my implementation, it only has 21 lines of actual code. And it is very easy to follow. On top of that, it has error checking galore. Without error checking, I could get away with maybe 10 lines of code - not bad.

My question is this - Why would one want to use the bitmap system? The stack system only uses 4mb, and that's only if you've got 4GB of RAM. It's really not that big an amount, if you consider. Only 1mb for every Gigabyte. For that small penalty, you get a huge boost in speed.

I was wondering also about one other thing:
Is there any median? What algorithams could be fast and with light memory footprint? Is it actually possible to get faster than a stack-based system?

I've decided, FYI, to go with the stack-based system, but the function calls perfectly match up (I did this on purpose, and the same goes for most other things - I use a strict naming method for my functions and variables to make sure they don't have trouble between files) so I could easily swap one for the other anytime.

I've just been going through the same exercise in my OS. Look in this thread for Brendan's alternate stack scheme that has almost zero space overhead -- a little more complicated, but very cool.

The answer to why bitmaps can be useful -- sometimes you want to allocate contiguous physical frames (e.g. -- for DMA). I haven't encountered this need yet myself, I'm just repeating what others have said many times. It should also be easier (in theory) to implement a lock-free bitmap allocator, which should reduce contention in SMP systems (again, in theory...)

If the space-efficient-yet-complex version of the stack is too complex for you, bitmaps are too slow for you, and the simple stack scheme is too space-hungry for you, you might want to consider a hybrid scheme. For example, have a stack of limited size backed by a bitmap. The stack acts as a cache for free frames, speeding lookup in most cases. You'd only scan the bitmap when the stack is empty.

I was thinking hybrid was a possibility.
And actually, I don't mind the overhead in space. In fact, I had the same amount of overhead before, as in my bootloader I'm lazy. You see, the memory bitmap was mapped to the last 4mb of memory - 0xFFF00000 to 0xFFFFFFFF. But the only way I was using it was for the last 128KB, which held the bitmap. So now I'm going faster without any loss in memory space, which is good.

I haven't looked at that topic yet, but it just occured to me that I could save more space while making it a little slower and more complex. Considering that the bottom 3 nibbles are always zeros (4kb chunks), I could pack it together and then save about 3/8 of my memory - or around 1.5mb. Does that sound right? Hope so.

Also, I'd like to point out the first 16-mb of memory is 'reserved' and cannot be used by anything but the kernel, no matter what.

On top of that, the kernel only uses addresses above 0x110000 (actually, 0x100000, but that just contains data the bootloader sent to the kernel about the loaded modules etc., basically a copy of my simple FS root directory with the location on disk param.s replaced with their location in memory)

So I could easily just implement a bitmap version for the first 1mb, as I don't see myself needing much more for DMA, which (I think) is among the only things I need to worry about. If I need more space, get the DMA to copy 64KB to one area, then while it copies another 64KB to another location move the other 64kb, and switch back, etc.
You'd end up having to copy it somewhere else most the time for drivers anyway, right?
Maybe I could just have reserved locations in the first 1mb or so that are set aside for DMA, one section for each channel?
Also, from 12-16mb it is unused after the bootloader exits, so I could easily also set that area away for the 20-bit channels, no?

Hi,

The worst case for the ISA DMA controllers is four 64 KB buffers and three 128 KB buffers, all being used at the same time by different devices. This adds up to 640 KB.

The part that worries me is that I don't know enough about PCI devices. Most of them do bus mastering using "scatter-gather", where there's an index buffer and several data buffers (and all of these are 4 KB or smaller), but I don't know if all PCI bus masters do this - there may be some that also need contiguous RAM (or perhaps perform better if they can get contiguous RAM).


Cheers,

Brendan

ugg..
I don't even want to think about PCI right now...
I'm trying to get my virtual memory manager working....

And then I have to do PNP ISA, then maybe PCI PNP, maybe a driver for VESA, an app, a GUI. But most of that is 2083 . lol

[OT]
Night...it's 8am over here .
[/OT]