OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 4:28 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 17 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: malloc etc.
PostPosted: Fri Feb 25, 2005 5:22 am 
I don't really get it anymore... I've now pages support (with a bitmap it allocates them etc.), but now I want to implemement malloc and free. For every malloc using one page would be most of the time quite a waste of memory.. do I have to use linked lists then for the free places of memory then? But where did I create the page support for then...

hope somebody can explain all this to me.. thanx in advance.


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 6:25 am 
Sounds like you're thinking malloc/free are something controlled by the kernel, they usually aren't. Malloc asks the kernel for a chunk of memory, the kernel maps in an appropriate number of pages, and then malloc manages that memory (Using linked lists or whatever) on behalf of the application. Malloc is part of the application, not the kernel, so it can safely allocate memory of less than page size within the space it requested from the kernel. A quick look through the dmalloc code will most likely answer all your questions.


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 6:30 am 
thanx.. but the code in the kernel, gives it out pages then and that the malloc function uses the same page when it isn't full yet?
Also, should I just give out the first empty page I can find, or later when my OS runs programs that it increases the size in memory and gets that page?


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 9:34 am 
anyone ???
i think that i have an idea how to do it (didn't begin on it yet).. malloc asks for the pages.. fills it with the asked amount of memory and keeps track of it how much of the page is used in a linked list.. only the chicken-and-the-egg problem.. how can I create a linked list when i've no malloc function ???


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 9:43 am 
Offline
Member
Member

Joined: Wed Dec 21, 2005 12:00 am
Posts: 193
Location: South Africa
Well you can ask the kernel directly for the initial memory to set up your structures and then ask for more later on when you have a a request.

Obviously malloc can't use malloc.. so it must get all of it's memory from the kernel.

Set up your structures with memory from the kernel.
Pre-request memory from the kernel to allocate to applications.

Then an application calls malloc, malloc slices up it's pre-requested memory and keeps track of everything in it's structures.


Top
 Profile  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 10:36 am 
Offline
Member
Member
User avatar

Joined: Tue Oct 17, 2006 11:33 pm
Posts: 3882
Location: Eindhoven
Malloc allocates a brick of space, say, 32k. It marks it in full (at start & end) as empty. It then considers itself set up.


Top
 Profile  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 11:28 am 
Ok, here's a very, very simplified explanation of a dynamic memory scheme (C gurus feel free to correct at will :)). A real world scheme would be far more sophisticated.

To ease explanation I'll use two lists (These are application data, nothing to do with the operating system):
The first list (The Free List) keeps track of holes by indicating the start and length of each hole.
The second list (The Allocated List) keeps track of allocated space by indicating the start and length of each allocation.

The heap represents the unallocated dynamic memory available to a program.
Visual is just me trying to show what's going on (o = used, . = free).

I'll make the assumptions that the dynamic memory routines will use the first hole big enough to satisfy a request, that it will request a full page of memory from the operating system whenever a large enough hole cannot be found and that my lists are sorted by address.

***

Let our program begin with no dynamic memory available or allocated.

Free List: empty
Allocated List: empty
Heap: 0 bytes
Visual: []

Now let's allocate some space.

Code:
SPACE1 = malloc (1024);


malloc checks the Free List.
There is no 1024 byte hole available (The list is empty).
malloc asks the operating system to give it a page of memory (4096 bytes).
The operating system maps an extra page of memory into the program's page tables (Usually by extending the program's data area) and gives malloc a pointer to the new page of memory (I'll call the address this pointer indicates Address1).
A new entry is placed on the Free List indicating a hole of 4096 bytes starting at Address1.

Free List: [Address1, 4096]
Allocated List: empty
Heap: 4096 bytes
Visual: [..4096..]

The allocation is now performed.

malloc checks the Free List.
A hole of 4096 bytes starting at Address1 is found, which is large enough to satisfy the request.
This entry is removed from the Free List.
A new entry is placed on the Allocated List indicating an allocated space of 1024 bytes starting at Address1.
A new entry is placed on the Free List indicating a hole of 3072 bytes starting at Address2.
The pointer SPACE1 now points at Address1.

Free List: [Address2, 3072]
Allocated List: [Address1, 1024]
Heap: 3072
Visual: [oo1024oo|..3072..]

Now let's allocate some more space

Code:
SPACE2 = malloc(256);


malloc checks the Free List.
A hole of 3072 bytes starting at Address2 is found, which is large enough to satisfy the request.
This entry is removed from the Free List.
A new entry is placed on the Allocated List indicating an allocated space of 256 bytes starting at Address2.
A new entry is placed on the Free List indicating a hole of 2816 bytes starting at Address3.
The pointer SPACE2 now points at Address2.

Free List: [Address3, 2816]
Allocated List: [Address1, 1024], [Address2, 256]
Heap: 2816
Visual: [oo1024oo|oo256oo|..2816..]

Now let's free up some space.

Code:
free(SPACE1);


free checks the Allocated List.
A space of 1024 bytes is found to have been allocated starting at Address1 (Which SPACE1 points at).
This entry is removed from the Allocated List.
A new entry is placed on the Free List indicating a hole of 1024 bytes starting at Address1.

Free List: [Address1, 1024], [Address3, 2816]
Allocated List: [Address2, 256]
Heap: 3840
Visual: [..1024..|oo256oo|..2816..]


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 11:29 am 
Now let's allocate some more space

Code:
SPACE3 = malloc(512);


malloc checks the Free List.
A hole of 1024 bytes starting at Address1 is found, which is large enough to satisfy the request.
This entry is removed from the Free List.
A new entry is placed on the Allocated List indicating an allocated space of 512 bytes starting at Address1.
A new entry is placed on the Free List indicating a hole of 512 bytes starting at Address4.
The pointer SPACE3 now points at Address1.

Free List: [Address4, 512], [Address3, 2816]
Allocated List: [Address1, 512], [Address2, 256]
Heap: 3328
Visual: [oo512oo|..512..|oo256oo|..2816..]

Finally let's increase the space allocated to SPACE3

Code:
SPACE3 = realloc(SPACE3, 1256);


realloc checks the Allocated List.
A space of 512 bytes is found to have been allocated starting at Address1 (Which SPACE3 points at).
realloc now checks the Free List for a hole of at least 744 bytes following that 512 bytes.
It can't find one, so the space allocated to SPACE3 can't simply be extended.
realloc checks the Free List again.
A hole of 2816 bytes starting at Address3 is found, which is large enough to satisfy the request.
This entry is removed from the Free List.
A new entry is placed on the Allocated List indicating an allocated space of 1256 bytes starting at Address3.
512 bytes is copied from Address1 to Address3.
A new entry is placed on the Free List indicating a hole of 512 bytes starting at Address1.
A new entry is placed on the Free List indicating a hole of 1560 bytes starting at Address5.
The pointer SPACE3 now points at Address3.

Free List: [Address4, 512], [Address1, 512], [Address5, 1560]
Allocated List: [Address2, 256], [Address3, 1256]
Heap: 2584
Visual: [..512..|..512..|oo256oo|ooo1256ooo|..1560..]

realloc realises that it can combine the two 512 byte holes into a single hole of 1024 bytes starting at Address1.

Free List: [Address1, 1024], [Address5, 1560]
Allocated List: [Address2, 256], [Address3, 1256]
Heap: 2584
Visual: [..1024..|oo256oo|ooo1256ooo|..1560..]

***

As you can see the only time new pages are required from the operating system is if there isn't a big enough hole to fulfil the request. Deciding when to return empty pages to the operating system is up to the dynamic memory system.

This example is just for explanation purposes. If you were making a real system you'd probably want to combine the lists (The example's Free List is just an inversion of the Allocated List), used linked lists, page colouring, etc. Getting everything working well is quite a challenge.

Hope that helps someone, somewhere :)


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 11:45 am 
wow.. thanx :D
i was already getting the idea of doing it in this way, but this makes it complete ;D
as list.. shall i make it as a linked list and just put an extra entry in the space requested for a piece of memory, or is that not safe because a program writes before its piece of memory and that the whole thing is broken down..
thanx again


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 1:30 pm 
I've created this code:

Code:
struct _alloc_t {
    unsigned long address;
    unsigned long size;        // bytes
    BOOL used;
    struct _alloc_t *next;             // next struct
};


typedef struct _alloc_t alloc_t;
#define BIALLOC sizeof(alloc_t)

alloc_t lAlloc;
alloc_t *alloc_curr = &lAlloc;
alloc_t *alloc_top = &lAlloc;

int heap = 0;

void AddMem(size_t bytes);

void *malloc(size_t bytes) {
    unsigned long tempsize, retaddr;
    alloc_curr = alloc_top;
   
    do { // loop as long as there is a next entry
        if (bytes + BIALLOC < alloc_curr->size && alloc_curr->used == FALSE) {  // is this free and enough space?
            tempsize = alloc_curr->size;                      // save the size of the free block in a temporary variable
           
            alloc_curr->next = (alloc_t *) alloc_curr->address;      // point next to the next list
            alloc_curr->address = retaddr = alloc_curr->address + BIALLOC;   // before it there comes a new entry for the linked list
            alloc_curr->size = bytes;                            // put the size in size
            alloc_curr->used = TRUE;                           // raise the used flag
           
            alloc_curr = alloc_curr->next;                 // create free space block
            alloc_curr->address = retaddr + bytes + BIALLOC;                    // and put the space for the linked list before it again..
            alloc_curr->size = tempsize - bytes - BIALLOC;
            alloc_curr->used = FALSE;
           
            heap -= bytes + BIALLOC;                      // substract the used bytes from the heap
            return (void *) retaddr;                          // return the address
        }
       
        alloc_curr = alloc_curr->next;
    } while (alloc_curr != 0);
   
    // if we didn't succeed, ask for extra money and try it again
    AddMem(bytes);
    return malloc(bytes);
}   

void AddMem(size_t bytes) {
    int realaddr, pageaddr;
   
    pageaddr = palloc(bytes);                        // get free space and put it in pageaddr
    realaddr = page_to_byte(pageaddr);               // convert the page address to bytes
       
    alloc_curr->address = realaddr + BIALLOC;        // put the address of the new free block in address
    alloc_curr->size = bytes_to_pages(bytes);        // put the size of it in size
    alloc_curr->used = FALSE;                        // it is free space, so make used FALSE
       
    heap += alloc_curr->size;                        // add the new space to heap
}   


void free(void *address) {
    alloc_curr = alloc_top;
    unsigned long addr_deep;
    alloc_t *alloc_curr2;
    BOOL addr_deep_found = FALSE;
   
    do { // loop through the linked list
        if (alloc_curr->address == (unsigned long) address) { // the address is found
            addr_deep = alloc_curr->address + alloc_curr->size + BIALLOC; // what should the next address be (for joining them together)
            alloc_curr2 = alloc_top; // alloc_curr2 points to alloc_top
            addr_deep_found = FALSE; // make sure the addr_deep_found is FALSE
            /* try to find an address which begins at the end of the last one */
            do {    // loop through the linked list again
                if (alloc_curr2->address == addr_deep && alloc_curr2->used == FALSE) { // does the next address come exactly after the one to free and has used = FALSE?
                    bAddr_deep2 = TRUE; // set the flag TRUE
                    break; // leave the loop
                }
                   
                alloc_curr2 = alloc_curr2->next;
            } while (alloc_curr2 != 0);
           
            if (bAddr_deep2 == TRUE) { // next piece of memory comes exactly after the one to free
                alloc_curr->next = alloc_curr->next->next; // skip one of them, the second will get lost anyway
                alloc_curr->used = FALSE; // set the used flag FALSE
                // :o that's all! Was just thinking about what next.. lol..
            } else {
                alloc_curr->used = FALSE; // just set the flag used on false...
            }       
        }
       
        alloc_curr = alloc_curr->next;
    } while (alloc_curr != 0);
}
   



next post has an explanation...


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 2:04 pm 
malloc:
what it does is looping through the whole linked list. Every time it checks the current node is free and big enough. If so, it fills it in with a new node for the linked list and fills in the current node with the values of the new allocated piece of memory. Then it fills in the next node with the values from the free space left and creates again a new node for the linked list.
If it couldn't find any free space in the linked list, it asks for free pages and does the whole routine again.

free:
loop through the whole linked list, loop every time again through them to see there is an empty piece of memory after it. If so, skip that piece of memory by setting next to next->next, and put the used flag on FALSE. When the pieces of memory can't connect, just put used on FALSE.

If somebody finds any mistakes, please say it..:)


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Fri Feb 25, 2005 8:05 pm 
> I don't really get it anymore... I've now pages support (with
> a bitmap it allocates them etc.), but now I want to
> implemement malloc and free. For every malloc using one
> page would be most of the time quite a waste of memory..
> do I have to use linked lists then for the free places of
> memory then? But where did I create the page support for
> then...

The kernel's job is to provide free memory, not necessarily to manage it. For example, the kernel does not always have to be able to free memory.

malloc()'s job is to manage a pool of memory. That memory was provided by the kernel. malloc() should be able to reuse free()d memory. As you see, this may get quite complicated, if only because of performance.

To start simple, you should define a place in memory for your heap. For example, if could start the heap at 0x300000. Just keep a pointer to the next free byte to allocate and advance it by the number of bytes that were requested by malloc(). Of course, you won't be able to free memory, but that's ok.

The kernel function which allocates memory is usually called sbrk() and takes a size_t for the number of bytes to allocate. Usually, malloc() implementations will call sbrk() to get more memory into its pool.

Now for the malloc() implementation, you really should reuse one, such as Doug Lea's malloc (http://gee.cs.oswego.edu/dl/html/malloc.html). dlmalloc(), in particular, can be configured to use any "morecore" function, but will use sbrk() by default. You can use it without modifications.

So the only thing you must provide in your kernel is a function named "void *sbrk(std::size_t size)" which will need to return a block of memory, which is, again, very easy to implement.

And that's it.


Jonathan


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Sat Feb 26, 2005 3:06 am 
thanx.. i already knew the information you gave, but maybe the link you gave will be useful..
can anybody check my code for mistakes I made? (see last 2 posts)


Top
  
 
 Post subject: Re:malloc etc.
PostPosted: Sat Feb 26, 2005 4:22 am 
Offline
Member
Member

Joined: Wed Oct 18, 2006 11:59 am
Posts: 1600
Location: Vienna/Austria
a recursive malloc *chuckle* that's in itself a fine idea.

What do you do, if add_mem fails?

The looping throu free chunks to find one that fits is ok.

I just miss some error checking stuff to make it fault tolerant, but for a first self coded malloc library it is pretty ok.

_________________
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image


Top
 Profile  
 
 Post subject: Re:malloc etc.
PostPosted: Mon Feb 28, 2005 10:33 am 
My own malloc implementation has too much bugs etc., and because I want to continue on my kernel, and not stay hanging on a malloc implementation, I decided to use that one which Jonathan Mcdougall recommended. I've a few questions about it:

EDIT: Everything fixed, disabled the mmap functions, found where i could set the page size, but i've here 2 new questions:
does sbrk work like this?:
- When there are 100 bytes asked, sbrk allocates 1 page. When there is asked for 6000 bytes, sbrk allocates 2 pages etc.
- What does sbrk exactly return... the number of the page or something else?

Thanx in advance


Top
  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 17 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: DotBot [Bot] and 57 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group