Ways to keep track of allocated RAM

[TheChuckster]

The line is marked in the code via a comment:

Code: Select all

int blocks[1792];

void* kmalloc(int size)
{
    void *ret=NULL;
    int searchedsize=0;
    int currentpos=0;
    int forloopcounter=0;
    int beginningbytes;

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

    // 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 = searchedsize + 8192;
        } else {
            searchedsize = 0;

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

        if (currentpos > 1792)
        {
          return 0;
        }
    }

    // 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.

    beginningbytes = (unsigned int)ret / 8192;
   
    for (forloopcounter = beginningbytes; forloopcounter < currentpos; forloopcounter++)
    {
        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 to change header to searchedsize.

    *(int*)(ret) = searchedsize; // THIS LINE.

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

    // Increase ret by where it starts in the memory and return it.
    ret = ret + 2097152;

    return ret;
}

I did tests using kprintf statements to narrow it down to that line. Also, the searchedsize variable is the correct size of the block in bytes. Commenting it out works good but there is no header. I would like to write the value of searchedsize at that address so that I can recall the size of the block in the soon-to-be-written free() function. Hope that helps.

[Schol-R-LEA]

Another way to handle it is to separate system-wide memory management from application-level MM; this way, the kernel memory allocator only deals with the coarse-grained memory tracking (8k blocks, in this case, though I would recommend larger blocks if you use this approach), letting the process handle the fine-grain allocations. Ownership of the system-level blocks would be recorded with each process' task record, so that the task itself would know what it had available, and also allow all the allocated blocks to be automatically recovered when a process is closed, even if it wasn't free()'ed correctly.

To illustrate, let's say that process A is created, and requests 1M of code space, 512K of stack space, and 256K of heap space to start. The scheduler would call the kernel memory allocator, kmem(), would allocate a task record from kernel memory (possibly calling sysalloc(), the system memory allocator, to allocate another block for the kernel), then calls sysalloc() to allocate the 7 blocks (assuming 256K blocks) for the process. then sysalloc() returns a pointer for each allocated block, which goes into the process' task record. When the process begins, the process' own malloc() would then set aside memory from out of those blocks for the code and the globals.

As process A runs, it creates a linked list of 24 byte nodes, the allocation requests for which are handled by the local malloc() routine. The system memory allocator doesn't see this, and does not need to keep track of them individually. If the initial 256K of heap is expended, then the malloc() routine would issue a system call to sysalloc(), which would allocate another 256K to the process. If all the memory in the allocated block is subsequently free()'ed, then the local memory manager would call sysfree() to release it for the system.

If the stack overflows the original 512K stack space, the page fault would cause sysalloc() to be called, and stack extended into the newly allocated block; assuming that paging and virtual memory are used, this should be transparent to the user process.

This approach has a number of faults, most notably added overhead and reduced memory protection with a given process, but it simplifies the system-wide memory management, reduces external fragmentation (though at the risk of internal fragmentation within the processes) and reduces the number of system calls required for memory handling. It also allows user processes to have their own memory management policy, which is especially useful for garbage-collecting languages.

[TheChuckster]

Thanks, Schol-R-LEA, but I've already chosen a method and written a malloc for it that works, except for one line. Please see if you know what the problem might be.

[Schol-R-LEA]

Ah, sorry if I misunderstood.

From just looking at the code, I can't see any problems. However, It might be useful to separate the cast from the indirected assignment, using a temporary variable like so:

Code: Select all

 int* header;  // add this to the declarations
...  // body of the function

headerpos = (int *)ret;
*headerpos = searchedsize;

This may help isolate the exact point of fault.

Oh, and one other thing: I compiled the code with Dev-C++ 5.0 beta (which uses the mingw version of gcc 3.2, IIRC), and it gave a warning on this line:

Code: Select all

              ret = currentpos * 8192; // Set ret to the address of the current position.

This can be fixed with a cast, as here:

Code: Select all

              ret = (void *)(currentpos * 8192); 

Whether this is relevant, I cannot say; it should do the conversion correctly regardless, the warning being just to cofirm that this was intentional. Still, it is probably better to be on the safe side and add the cast.

It also gave an error stating that NULL was not defined, but I am assuming that this function is just a section of a larger source file.

I'll take a closer look at the code shortly. HTH.

[TheChuckster]

I got part of the problem solved. Heh. I didn't increment ret by 2 MB before writing the header, so I ended up overwriting part of my kernel. Not good at all!

Thanks for all of your help!!! ;D You guys are the best!

[Schol-R-LEA]

Oh, so that explains it. I went over the code extensively - even rewriting it in my own idiom so that I understood it better - and I still missed that. Now that you've explained it, it seems so clear all of a sudden.

BTW, you may want to check to see if you have an off-by-one error in the code that calculates the return value as well; in the existing code, it looks as if it returns the last byte of the header, not the byte following it.

This is the version I re-wrote (including that last correction that you found), if it makes any difference. I mostly just set all the constants into [tt]#define[/tt]s and changed a few names for my own benefit, but I did make one change with how it calculates the return pointer that I think makes the code considerably simpler and probably marginally faster (since it reduces the amount of code in a loop).

Code: Select all

#include "kmem.h"

BIT blocks[MAXBLOCKS];

void* kmalloc(int size)
{
    int* allocmem=NULL;    // the pointer to the allocated memory
    int searchedsize=0;    // the size of the free blocks currently being tested 
    int blockpos=0;        // the first marker for the allocated block 
    int currentpos=0;    // the block flag currently being tested
    int setblock=0;        // current block to set

    // Reserve room before the allocated space for storing the header.
    size += HEADERSIZE;

    // 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 (CLEAR == blocks[currentpos])
        {
            // If blockpos is zero, then this is the 
            // beginning of a free block.
            if (0 == blockpos)
            {
              // Set blockpos to the current position.
              blockpos = currentpos;
            }

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

            // We didn't find anything yet, clear blockpos
            blockpos = 0;
        }
        currentpos++;

        // if we have run passed the total physical memory, 
        // return an error
        if (currentpos > MAXBLOCKS)
        {
          return NULL;
        }
    }

    // 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.
  
    for (setblock = blockpos; setblock < currentpos; setblock++)
    {
        blocks[setblock] = SET;
    }

    // set the allocated memory pointer to 
    // the beginning of the memory block, 
    // with the appropriate offset for the system memory
    allocmem = (int *)((blockpos * BLOCKSIZE) + RESERVED_MEM);

    // Now we must write our header. The header contains searchedsize, 
    // the length of our block in bytes. Set the address of header to
    // allocmem to change header to searchedsize.
    *allocmem = searchedsize;

    // Last, increase allocmem by HEADERSIZE+1 so that the
    // allocated space begins at the byte following the header.
    // Note that allocmem has to be cast to void* BEFORE the
    // calculations, so that the pointer arithmetic is in 
    // bytes rather than in ints.

    return (HEADERSIZE + 1 + (void*)(allocmem));
}

The header file kmem.h contains

Code: Select all

// kmmem.h - header file for the system memory allocator 

#ifndef ___KMEM_H___
#define ___KMEM_H___

#ifndef NULL
#define NULL '\000'
#endif

typedef enum {CLEAR = 0, SET = 1} BIT;

// basic constants

#define KILOBYTE 1024
#define MEGABYTE (KILOBYTE * 1024)

// physical memory size in megabytes
#define MEMSIZE 16

// size of starting memory reserved by the system
#define RESERVED_MEM (2 * MEGABYTE)

// size of a basic allocation block
#define BLOCKSIZE (8 * KILOBYTE)

// Total number of blocks available for allocation
#define MAXBLOCKS (((MEMSIZE * MEGABYTE) - RESERVED_MEM) / BLOCKSIZE)

// size of the allocated memory header
#define HEADERSIZE 20

void* kmalloc(int);
void kfree(void*);

#endif

Since the [tt]#define[/tt]s are all based on constants, the compiler should be smart enough to precalculate them rather than have them calculated at runtime.

Let me know if this helps at all or not. Since I don't have the rest of your code, I don't know if it would work or not as it is, but I do know it compiles correctly under Dev-C++ 5.0beta.

EDIT: Replaced [tt]BOOL[/tt], [tt]TRUE[/tt] and [tt]FALSE[/tt] with the [tt]BIT[/tt] enumeration.

I can't seem to leave well enough alone; now I keep thinking of how I could implement [tt]blocks[[]][/tt] as bit strings. If only I could put so much effort into my own projects...

[Schol-R-LEA]

Obsessive compulsive that I am, I went ahead and reworked a version of the code to use a packed bitmap (see attachment), without even finding out if Chuckster even wanted it. Weird. I hope that there's no hard feelings about this, Chuckster; I feel as if I've stepped all over your prerogatives, but I never meant it that way.

Oh, in doing so, I found a bug in my code: allocmem has to be cast to char* first, and then only cast to void* after the calculations are done. I forgot that you can't use pointer arithmetic on void pointers, and didn't test it until now. Here's the correct code with commentary:

Code: Select all

    // Last, increase allocmem by HEADERSIZE+1 so that the
    // allocated space begins at the byte following the header.
    // Note that allocmem has to be cast to char* BEFORE the
    // calculations, so that the pointer arithmetic is in 
    // bytes rather than in ints, and then cast to void* only
    // once it has been calculated.

    return (void*)(HEADERSIZE + 1 + (char*)(allocmem));

Whether this means anything to anyone but myself remains to be seen. After all these changes, it hardly resembles the original anymore. I know the code compiles correctly, but I haven't been able to test it for the same reasons mentioned before, so whther it actually works is anyones guess.

EDIT: I found a bug in the clearbit() functions, which is now fixed; I also added kmeminit() and kfree() functions, and redesigned it so that it initializes the memory size at runtime (and can handle up to 4G memory). Why I am doing this, I don't know...

[attachment deleted by admin]

[TheChuckster]

That's all right. You are free to do what ever you would like with my code. ;D If you would like me to post my realloc, free, and calloc please notify me. (These have all been tested extensively and work.) I would be glad to provide source to the OS development community.