Allocating Paragraphs

[Firestryke31]

This isn't exactly OS development specific, but if the mods feel it's better put elsewhere it won't hurt my feelings (unless, of course, it's the trash...).

In case you didn't know, I've decided to make my first O.S. a DOS++. Basically it's a simple DOS with a few extra features. I'm getting to the point where I might want to have my int 21h AH=48h, AH=49h and AH=4Ah (allocate a block, free a block, and resize a block) working to make my life a bit easier. Obviously with a block being a multiple of 16 bytes using segments is the way to go for accessing them, but what I'm having trouble with is figuring out the best way to mark these blocks as allocated/freed. A bitmap seems a bit wasteful, but so does using 16 bytes immediately before the block to store allocation structures (assuming allocations have to be on a 16-byte boundary).

I can see 2 options:
1) A bitmap which would be best for lots of small allocations
2) A linked-list type structure before the allocated block which would be best for a few big allocations

Using a bitmap, assuming I fill memory with a bunch of single-paragraph allocations, would use a constant 5KB of RAM, whereas with the linked-list approach it would waste about 50% of RAM. (5KB == 640KB / 16 Bytes per paragraph / 8 bits per byte in bitmap)

Assuming I fill memory with a single all-of-RAM allocation a bitmap would waste most of the 5KB but the linked-list would use only 16 bytes.

My question is which should I use, and are there any other options that I might want to consider but am missing?

[bewing]

I would make a block 255+n*256 bytes instead of 16, use 1 byte instead of 16 for my linked list "information structure" (length/256) and then allocate my structures so that they always start 1 byte below a 256 byte boundary.

[Firestryke31]

Of course, with DOS, a paragraph (I'm pretty sure) has to be 16 bytes in order to maintain compatibility with other DOSes, and you can only allocate paragraphs with DOS. I'm thinking I should just go ahead and use some of the 64K I reserved for the kernel for the bitmap since it will mean merging 2 adjacent free blocks is as simple as setting a bit. Checking for a free block the size I need will be a bit hard...

I also just remembered I'm going to have to store the size of each allocated block somewhere if I do use the bitmap...

[bewing]

For 16b allocs you would need two overhead bytes instead of one, but I'd guess that method is still superior.

[Firestryke31]

Does a DOS paragraph have to be on a 16-byte boundary? I think they do because you're supposed to use the segment registers to free them (but I may be wrong), so using a 2-byte header would waste the other 14 bytes (since you can't allocate them). It's almost like managing pages except 16B instead of 4K (and they're in a fixed location instead of remapable).

[earlz]

So are you not going to try to get unreal mode in your dos++?

[Firestryke31]

I might, but it still has to work with existing DOS programs. I was thinking of just having a fancy UI and a few extra system calls for Socks-specific programs. I may implement a DOS extender too, but I just want to get the original goal of DOS working right now.

[thooot]

Here's how I would do it: Instead of having a regular linked list, have it so that the first couple bytes of a free block are used to keep track of the number of free contiguous free blocks AND the number of allocated contiguous blocks following the free block. This way when you get to a free block you can skip past it and the next sequence of allocated blocks to get to the free block beyond it. This won't use up any memory as the entire list is kept track of within the free blocks. The one exception is the initial block in the list as you will need a global variable to keep track of it.

For freeing memory you either need to have the application specify the starting address and the number of blocks to free or have a separate structure that tracks each allocation and how many blocks are in it. For this I would use a regular linked list initially (you may want to switch to a tree or hash table eventually if you find its too slow). When you need to expand this list you can use your regular allocator, just make sure you allocate a block of list entries otherwise you'll waste memory and end up having one internal allocation for every user allocation.

[Firestryke31]

Here are the API functions I'm trying to implement:
Allocate
Free
Resize

I think that I might try something like this (due to the multiple-of-16 nature of the allocator):

Code: Select all

// Pseudo code

struct allocation
{
  u16 prevSegPtr;
  u16 block1Start;
  u16 block1Size;
  u16 block2Start;
  u16 block2Size;
  u16 block3Start;
  u16 block3Size;
  u16 nextSegPtr;
};

Then just use that for both the free list and the allocated list. Any other suggestions or ideas?