Dos Memory Management

[VolTeK]

Would anyone have a link to where i could find how DOS's Memory manager worked or similar? Wanting to write one for under 1mb

Ill take suggestions too. I was going to use a first fit system with a giant list of entries of memory allocated for all programs, and when more memory is allocated to go through and find an open entry and open memory. To me, and a friend of mines understanding it will be very slow.
I know this should not be the route to go, but its all i can think of.



Please note, i only want to use the first mb or 640k. (0x00000 - 0x9FFFF).

[bubach]

It kind of depends on your OS.... For a 32/64 bit OS with memory requirements > 2mb there's no need to use anything below 1mb except for rare kernel cases. You will have plenty of other RAM for "normal" allocations. For DMA or other such uses where you actually need to have memory below 1mb you could set up a simple bit- or byte-map. I have a bytemap of 1kb blocks below 1mb, which "wastes" 1kb to hold information on what is used or not. Smallest block you can allocate is of course 1kb in this case, but I don't need more precision or optimization. KISS - Keep It Simple Stupid.

[Brendan]

Hi,

Would anyone have a link to where i could find how DOS's Memory manager worked or similar? Wanting to write one for under 1mb

If I remember correctly, at the beginning of each (allocated or free) block of memory DOS stored a 16-bit "size of block in 16-byte units" value. It was bad for 5 reasons:

• it probably wasted 16 bytes of each allocated block (which would really suck for lots of small allocations - you'd waste more RAM than you used)
• free space fragmentation (e.g. you want to allocate 2 KiB but you've got hundreds of 1 KiB free areas that are all too small).
• searching the list for means touching (possibly many) cache lines
• searching the list would mean constantly adding "size of block in 16-byte units" values to a segment register (where modifying a segment register is slow)
• Because the data stored in allocated areas was preceded by metadata for the allocated area and followed by metadata for the next area in the list, the chance of the metadata being corrupted (due to programmer mistakes, like buffer overflows) was high.

Ill take suggestions too.

Suggestions:

• Have a list in a special area of memory away for the memory being managed. That way you could have 2 bytes of metadata for each block without any padding/alignment.
• Use paging to avoid problems with free space fragmentation. Alternatively use protected mode segments so you can relocate allocated areas and adjust the GDT entry to suit, so that application's "far pointers" still work correctly.
• Have a list in a special area of memory that packs as much info into each cache line as possible (e.g. 2 bytes of metadata per block with the metadata for 32 blocks packed into each 64-byte cache line)
• Have a list in a special area of memory that packs metadata in the smallest space possible, so you can access all of it without changing segment registers. E.g. depending on how it's done, you'd be able to access all metadata in one segment and get rid of lots of segment register loads.
• Have a list in a special area of memory that is away from the memory being managed. That way if software screws something up (e.g. buffer overflow) it corrupts the next block of data and doesn't corrupt the memory management metadata.

There's 2 ways to do "2 bytes per block". The first way is to have a fixed size array of 2 byte entries, where each entry contains a 15-bit "size of the block" and the highest bit is used as an "allocated/free" flag. In this case searching would mean doing something like this in a loop "entry_for_next_block = entry_for_this_block + (memory_management_array[entry_for_this_block] & 0x7FFF);". Each block would be limited to 512 KiB in size, and a 64 KiB array (32768 2-byte entries) would manage 512 KiB of RAM.

The other way is to have a variable length array of 2 byte entries, where you'd do something like "entry_for_next_block = entry_for_this_block++;". This would be better (you'd pack more metadata into a smaller space) but it'd also be worse (you'd need to "memmove()" metadata around when inserting/removing blocks).

Finally, don't forget about the "high memory area" - the 65520 bytes of usable RAM at 0x00100000 that you can access in real mode by enabling A20 and loading 0xFFFF into a segment register. This RAM is a little awkward to use because you can't set a segment register such that the first byte in the segment is usable RAM (e.g. the real mode address 0x10000:0x0000 won't fit in a segment register and 0xFFFF:0x0000 is ROM). However, you could use these 65520 bytes for your memory management metadata. For example, for the first method, you could have a "32760 entry" array that manages 511.875 KiB of RAM. There'd be a maximum of 640 KiB of RAM to manage, so if your kernel (and IVT, BIOS data area, etc) consumes the first 128.125 KiB of RAM (e.g. from 0x0000000 to 0x0002007F) then those 65520 bytes would be enough to handle all memory management needed (for the area from 0x00020080 to 0x0009FFFF).


Cheers,

Brendan

[rdos]

If I remember correctly, at the beginning of each (allocated or free) block of memory DOS stored a 16-bit "size of block in 16-byte units" value.

It was a little more than that. It had a block ID with two possible values (others indicated corruption), owning PSP and size (in 16-byte paragraphs) + possibly something else

searching the list would mean constantly adding "size of block in 16-byte units" values to a segment register (where modifying a segment register is slow)

I don't think that was slow back in the days of real mode. Loading a real mode segment register was very simple back then.

Have a list in a special area of memory away for the memory being managed. That way you could have 2 bytes of metadata for each block without any padding/alignment.

The Clib I use (OpenWatcom) still uses in-place links rather than a special area. I don't know if other compilers do the same, but they might.

Use paging to avoid problems with free space fragmentation. Alternatively use protected mode segments so you can relocate allocated areas and adjust the GDT entry to suit, so that application's "far pointers" still work correctly.

Absolutely

Have a list in a special area of memory that is away from the memory being managed. That way if software screws something up (e.g. buffer overflow) it corrupts the next block of data and doesn't corrupt the memory management metadata.

Disagree. It is much worse if data buffer overflow siliently kills something else in the program rather than memory allocation links, because memory allocation links would likely pagefault if overwritten, so will tell you something is wrong. I'd implement some kind of checking for overwrites instead, at least during debug-phase. You can for instance allocate all requests page-aligned, and fill-in default patterns outside of bounds. If those have been modified when you free the block, you know something is wrong.

[VolTeK]

Thank you all for your responses,

I have taken them all into consideration as to what im going to use, and have chosen what i plan to implement.


I have run into one problem upon developing this, (you may have already posted this, if you have, im very sorry for missing it) where to store the word's of data (each containing an id to a block of data allocated) to the block of memory that the program is using. I want to store it after, or before a loaded program calling it, but with every block allocated at run time, means more space being over-written (possibly the program loaded next to it).


Should i just allocate enough space for a master list and names and limit the amount of programs that can be loaded along with limiting how many allocations each can do?