OSDev.org

The Place to Start for Operating System Developers
It is currently Wed Apr 26, 2017 4:05 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 23 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 7:10 am 
I am currently writing malloc and free implementations from scratch due to the low quality of existing source code and tutorials.

However, I am faced with problems using linked lists or bitmaps. Linked lists require an allocator to add new entries to the list. But I can't use an allocator to write an allocator...

Bitmaps on the other hand are great except for one problem. Well, I decided to split my remaining 14 MB (segementation) into 8kb chunks and declared an array for each 8kb. However, there is no way of keeping track how large each block is.

Let's say I have [Block A] [Free] [Block B] and Block A is freed. The deallocator will search to the free space and mark each 8 kb chunk as free in the bitmap.

Now let's say I have [Block A] [Block B] [Free]. Without a way of knowing how large block A is, the deallocator will keep searching and mark block B as free until it reaches the free. This, of course, is not good.

What method do your malloc()s and free()s use to keep track of allocated and free blocks?


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 7:42 am 
One common way is to reserve few bytes from the beginning of all allocations for "malloc headers". When user requests 20 bytes you actually allocate 24 bytes, so you can put the size in there. You can then return a pointer after the header. By substracting the header size from the pointer received by free() you can then find the headers again.

You might also want to have another 4 bytes to have a pointer, so you can construct the linked-list directly from the allocated regions. It's also possible to have some flag to indicate if a region is still allocated, or another pointer to make the list doubly-linked.. or whatever you want. I would personally forget about the bitmaps though.

One trick is to put the size both at the beginning and at the end of the region, so that you can scan backwards in memory to find the size of the previous region, and calculate position of it's header, thus being able to check if it's possible to join the two regions together.

There are other ways, like keeping the headers in some separate space, or splitting regions of certain size (like a page) and keeping the headers at the end of the large region. If you want to be truly efficient, you probably need a different policy for small and large blocks.

One decent malloc is so called "dlmalloc" http://gee.cs.oswego.edu/dl/html/malloc.html which is available as source code, and is public domain. Might or might not be usable for kernel code though..

added: I strongly suggest that you test your malloc outside your kernel. It's very easy to not get it right the first time. I'd even suggest that you test it with some normal application.

If you are using some unix-like system (like Linux) you can compile it as a shared library and use LD_PRELOAD to get applications to use it without any recompile. If (when) they crash, you can try to reproduce the problem with a little test and debug the library without getting any nasty triple faults.


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 9:39 am 
dlmalloc, aka Doug Lea's Malloc, is the one Mobius now uses. It provides slot-in implementation for all the malloc/free/realloc/etc. functions, and it doesn't have any external OS dependencies. It even has hooks which let you surround calls to malloc etc. with spinlocks/mutexes. I just downloaded Doug Lea's malloc.c, tweaked it, compiled it, and forgot about it (that is, until I realised that my own locking functions weren't working ;) ).


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 11:00 am 
Here is my First fit malloc using bitmaps posted to save others from the headaches I've experienced trying to write it. My free and realloc are coming shortly. Please help me solve the compiliation errors I wrote in the comments as I have never written code in C before (don't get me wrong, though, I have plenty of past programming experience). Also, if you spot any errors beyond those reported by the compiler please notify me.

Code:
/* This code is Copyright (c) 2003 Chuck Moyes.
You must leave this comment in if you would wish
to use this code as public domain in your project. */
void* free = 0x200000; // 2 MB
void* end_of_free_mem = 0x1000000; // 16 MB

int blocks[1792];

void* malloc(int size)
{
    void *ret=NULL;
    int searchedsize=0;
    int currentpos=0;
    int forloopcounter=0;
    int header;

    // Reserve 4 bytes before the allocated space for storing the header.
    size += 4;

    // Search for a block of memory greater than or equal to the size we need. We will
    // go through the RAM sequentially. If the next block is taken, reset searchedsize
    // which contains the current block's size. If the next block is free, add on to
    // searchedsize. Once we find a large enough block, move on.

    while (searchedsize <= size)
    {
        if (blocks[currentpos] == 0)
        {
            // If ret is NULL, that means we just found a free block.
            if (ret == NULL)
            {
      ret = currentpos * 8192; // Set ret to the address of the current position.
            }

            searchedsize += 8192;
        } else {
            searchedsize = 0;

            // We didn't find anything yet, set the return value to null.
            ret = NULL;
        }
        currentpos++;
    }

    // Set the block as used in the bitmap.
    // Start by searching at the beginning of the allocated block until we get past the
    // currentpos which is the end of the allocated block. Then for each part of our
    // bitmap, mark it as taken (1).
    for (forloopcounter = ret / 8192; forloopcounter < currentpos; forloopcounter++) // LINE 46
    {
        blocks[forloopcounter] = 1;
    }

    // Now we must write our header. The header contains searchedsize, the length of our block in bytes.
    // Set the address of header to ret and change header to searchedsize.
    &header = ret; // LINE 53
    header = searchedsize;

    // Last, increase ret by 4 bytes so that the allocated space is out of the way of our header.
    ret += 4;

    // Increase ret by where it starts in the memory and return it.
    ret += free; // LINE 60
    return ret;
}


The errors are:
C:/Opteron/malloc/malloc.h:46: invalid operands to binary /
C:/Opteron/malloc/malloc.h:53: invalid lvalue in assignment
C:/Opteron/malloc/malloc.h:60: invalid operands to binary +


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 5:00 pm 
No one knows what's wrong? ??? :(


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 5:28 pm 
Code:
for (forloopcounter = ret / 8192; forloopcounter < currentpos; forloopcounter++) // LINE 46

You can't use / with a pointer (ret).
Code:
&header = ret; // LINE 53

You can't do this. &header is effectively just a number; you can't assign a value to a number.
Code:
ret += free; // LINE 60

You can't use arithmetic on void* (maybe you want char*?).


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Mon Jul 28, 2003 6:54 pm 
Quote:
for (forloopcounter = ret / 8192; forloopcounter < currentpos; forloopcounter++) // LINE 46

You can't use / with a pointer (ret).

&header = ret; // LINE 53

You can't do this. &header is effectively just a number; you can't assign a value to a number.

ret += free; // LINE 60

You can't use arithmetic on void* (maybe you want char*?).


Ugh. I want the for loop to go from the start of the block list which is the address of ret divided by 8192. Also, I would header to be located at the address of ret. Last, I'd like to add the 2mb to the address of ret so that it is 2 mb into the RAM.


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Tue Jul 29, 2003 3:16 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
why not simply
Code:
*((int*)ret)=searchedsize;

?

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Tue Jul 29, 2003 7:52 am 
Well here's what I want to do but I'm not sure how.

I'd like to store an int at an address and be able to retrieve it later just by knowing the address itself.


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Tue Jul 29, 2003 10:18 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
then if the address is free for storing stuff, just use "*address" to access the int :)

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Tue Jul 29, 2003 10:56 am 
if the address you're dealing with is stored in a void*, you're probably going to still need to type-cast to an int* first and then dereference.

So:
Code:
*(int*)(address) = value


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Tue Jul 29, 2003 5:09 pm 
Thanks! That works great, but there is still one last error.

In this line, I'd like to divide the address in ret (which is the beginning of the allocated block) by 8192 in order to find its position on my bitmap.

Code:
beginningbytes = ret / 8192;


The error is: invalid operands to binary /


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Tue Jul 29, 2003 7:12 pm 
try casting it into an unsigned long first. This lets the compiler know that you *really* do whant to treat a memory address like a number and divide it.

Code:
beginningbytes = (unsigned long)ret / 8192;


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Wed Jul 30, 2003 8:29 am 
My allocation function works great except for writing the header (which I use Pype.Clicker's code for). After the 2nd time malloc is called in my OS, it appears to be thrown into an infinite loop as the screen blanks. I am positive it is this line, because commenting it out causes the malloc to work perfectly. Except without the header, I cannot write a free.


Top
  
 
 Post subject: Re:Ways to keep track of allocated RAM
PostPosted: Wed Jul 30, 2003 10:03 am 
TheChuckster wrote:
I am positive it is this line, because commenting it out causes the malloc to work perfectly.


Which specific line do you mean by this? commenting out which line causes it to work perfectly?


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

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot] and 10 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