New Heap Location

[Tolga]

Hi. I want to put heap to end of stack like in attachment. But im new in paging. So, when i design segments like this, can stack rise? I design like this to heap rising. What do you think about it?

[AJ]

I've said it before and I'll say it again - nice images

Anyway - It looks to me like what you intend to do is ok. Personally, I tend to have a single 4 gig DS and a single 4 gig CS, but that needn't matter. Also, I believe that convention dictates putting the stack above the heap - again this doesn't matter so long as you are happy that your stack will not clash with code.

If you are starting out using paging, heap management is fairly simple. All you need to do is define a range which your kernel knows is 'valid' heap space - you don't even need to page it in yet.

Next, set up a tree or list containing the start and length of the heap. Your kmalloc function (or equivalent) can then assign virtual memory as and when it is called. It simply subtracts the amount of assigned RAM from the 'free space list' and returns the start of the assigned range. Often, it will put some kind of descriptor before the start of this block, so when free() is called, it knows how much space to return to the heap.

The next step is a Page Fault Exception handler. In its simplest form, this will check the address of the page fault (in CR2) and page in if the page in question has been allocated. If not, you can terminate the faulting process or display some kind of BSOD.

When I started out with this, I made the mistake of over-complicating it. Remember - keep it simple to start with.

Hope this helps,
Adam

[Solar]

The disadvantage of this approach is this:

If you put code - heap - stack, heap and stack grow towards each other, and if one grows faster than the other, you can rather easily move the boundary.

In your design, you set the maximum size for both heap and stack at the beginning, and changing that afterwards will be very difficult if at all possible.

PS: It's just me, but I find your avatar rather... disturbing. I'd rather not look at an exploded face (mask or natural doesn't matter) whenever I visit a thread with posts from you...

[Tolga]

I changed my avatar

Now i will create a linked list to keep heap item informations.

Code: Select all

struct TLinkedList{
	TLinkedList *PrevItem;
	TLinkedList *NextItem;
	UNSIGNED LONG INT Offset;
	UNSIGNED LONG INT Size;
};

This struct size is 16 byte. Where can i keep this TLinkedList items. Is in Stack? or Is in another page? or Is in Heap?

# if in stack, this is bad idea. Because, i can't know how many heap item to create.

# if in another page (i will create a page for each task for heap list), this maybe good idea.

# if in heap, this cant be. Because heap cant keep heap list. Is this possible?

Thanks.

[AJ]

Hi,

I keep my linked list in the heap. If you think about it (it may sound a bit convoluted at first!), you only need to store one list item statically.

As free space in your heap gets fragmented, you will need to assign memory dynamically but fragmentation isn't a problem until you start freeing. Remember - in the linked list you are tracking free space. (At least, that's how I do it.)

Cheers,
Adam

[Tolga]

But there is a problem. When a created any dynamic object, i will create a LinkedList struct in heap. To store this LinkedList informations, i will create another LinkedList. To store ...

Do i think wrong?

[Combuster]

Do i think wrong?

No, you can indeed get a variation to the chicken-and-egg problem if you take the wrong approach. However, by introducing both the allocated memory and the linked list entry as one, you can save yourself the trouble of having two separate structures (and which is powerful enough to save your MM's day).

I'll give you a quick overview of how pdclib implements its memory management (that is, how i remember it was). Credits for it go to Solar:

When you allocate a piece of memory, you allocate the memory + the size of the structure, and put the structure first in the list. what you get is a linked list of the following kind:

(pointer to next entry, payload size, payload) - (pointer, size, payload) - (pointer, size, payload) - etc etc

and you keep a separate pointer to the base of the heap (pointer to the first entry).
Free memory can be detected by checking that subsequent items in the linked list are more apart than the payload + structure size together. (i.e. there's unused space between the end of the payload and the next entry in the linked list)
The size of the heap can be found by getting the last entry (which has a null pointer to the next item) and comparing the end to the base of the heap.
Allocating memory is done by inserting a new entry consisting of linked list structure + area for payload as one block, and returning a pointer to the memory directly after the structure.
Deallocating memory is done by subtracting the size of the structure from the address which gives the base of the structure, after which it can be removed, or its payload set to 0.

As you see, there is no infinite recursion of information structures down the heap.

[AJ]

But there is a problem. When a created any dynamic object, i will create a LinkedList struct in heap. To store this LinkedList informations, i will create another LinkedList. To store ...

Hi,

Currently, my MM is very simple and I think it needs to be this way to start with - you don't want MM problems i when you are debugging other parts of your system - it makes tracking errors much more difficult!

What I was suggesting was as follows:

1. Set up a *single* linked list, storing just free space - to get the ball rolling, you just need 1 item, which you can assign statically. This linked list may be something like:

Code: Select all

struct mylinkedlist
{
  base;
  limit;
  *next;
  (*prev; - if you want a doubly-linked list)
};

So, the base may be set at 0xD0000000 and the limit at 0xDFFFFFFF, for example.

2. When I request n bytes, your allocation routine actually assigns n+4 bytes. To do this, simply increase 'base' by n+4, thus removing the space from the linked list.

3. At 0xD0000000, place a double word containing how many bytes you just assigned.

4. Your kmalloc(bytes) function returns 0xD0000004.

5. Your kfree(void*ptr) function simply has do do a (ptr-4) to find out how many bytes it needs to free.

*This* is where it gets a little (but not much) more complex!

If You have assigned more free space, you cannot simply amend the 'base' of your heap linked list to free the space you have assigned, and you will need another structure in your linked list. All you have to do is a :

Code: Select all

kmalloc(sizeof(struct mylinkedlist));

and fill the values with the base and limit of your newly freed area.

This is not as chicken and egg as it first seems as your kmalloc will *never* need to create more new structures - you are simply amending an existing structure (until you start worrying about alignment and fragmentation - but that comes much later...).

That's how my basic MM works. I thought I was creating an algorithm to see me through some of the earlier stages of kernel development but it has proven more robust than I imagined!

[edit]Sorry - I didn't fully read the previous post which says kind of the same thing, but I'll leave this here as an alternative answer anyway [/edit]

Cheers,
Adam

[Solar]

I'll give you a quick overview of how pdclib implements its memory management (that is, how i remember it was). Credits for it go to Solar:

Much as I like to be referenced, the idea was taken from Doug Lea's A Memory Allocator.

If you want to go beyond elementary functionality, check out that site, because the algorithm described there is much more sophisticated than that in PDCLib v0.4, which is a primitive exact fit / first fit without any way to return memory to the system. (It's a placeholder until I get the basics done and start optimizing PDCLib.)