• C

~~~CODING malloc()~~~

All Experts,
Hi, I'm having an assignmnet on Operating System Class, my task is to create our own malloc function, the interface are
extern int mm_init (void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);

We are not allowed to change the interface and use any system routines such as malloc(), free(), sbrk(),
And can't create any global variable to store any data
but it given file memlib.h and memlib.c where the interface are
#define DSEG_MAX 20*1024*1024  /* 20 Mb */
extern char *dseg_lo, *dseg_hi;
extern long dseg_size;
extern int mem_init (void);
extern int mem_reinit (long size);
extern void *mem_sbrk (ptrdiff_t increment);
extern int mem_pagesize (void);
extern long mem_usage (void);
I'm not asking people to do my assignment, but I want to know how can I work with the heap area (like how can i store things on heap) just like malloc()
Also, Is there any source code of malloc()? So that I have more understand how to deal with memory allocation!

ps. If you want more information on memlib.c, I can post all the code.

Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

One of the links for malloc various implementations



Hi joeyoungkc,

no we wont need the entire code, as we will not be helping you with code ;o)
However, it would have been nice if you would have posted some information regarding the interface functions...
what do they do ? what are the parameters etc.... I am deriving their functionality from their names for the following explanation... so there may be a few inaccuracies but you should be able to easily correct them and fit them into your case

you need some kind of mechanism to keep track of free and allocated memory... first step would be to devise data structures to represent memory and keep track of the desired information... I guess mem_init would be responsible for initializing the memory, so all these data structs come into existence here.... from the kind of declarations, I guess that you will be having a 20MB chunk of system memory which you will be treating as your memory and managing it

next for dynamic allocation/implementation of malloc, you need to take atleast the requested amount of memory and return a pointer to it. From the 20Mb chunk take out the desired amount of memory and pass a pointer to it... keep track of the memory that you have allocated ...

to free the memory, you will be given the pointer to the memory... look up this address in the data structures where you store the information... free that block, i.e. move it to the free list

the general strategy used my most operating systems is to keep blocks of different sizes all of which are powers of two...
e.g. an OS may decide to keep lists of blocks of 64bytes, 256 bytes, 512 bytes, and 1024 bytes ... when a request arrives, it selects the minimum size of block which will satisfy the request and allocates it. Some information may be added to the begining and ending of the block to indicate that it has been allocated.. alternatively you may use a table...

I hope that this is enough to get you started... In case you have any queries, post them

Just listening to follow the conversation..

Sarcastic answer below.

[Some teachers might give you a good mark for this! - I'd think it was clever :o) ]

void *mm_malloc (size_t size)
 return NULL;

.... would probably adhere to all the requirements of the function specifications, though it isn't a particually useful memory manager :-)
High-tech healthcare

From AI to wearables, telehealth to genomics to 3D printing — healthcare technology is seeing rapid advancement. Experts believe that this technological advancement will save money and save lives. Healthcare is changing dramatically, and emerging technology drives that change.

Hmmm, we answered this a while back but I cant find the thread...

Here's some general pointers:  (HA!)

Allocate a chunk of memory by calling the operating system API.

Put a little struct at the beginning of the block that holds some information.
Useful info would be things like:  a flag stating whether this block is allocated or free, the block length, and maybe a heap check password.

Ten when a request comes in to YourMalloc. say YourMalloc( 100 ), check your struct, see if it is free, if not,
skip forward to the next struct (at thisstruct + struct.size).  Skip any blocks you've alreadty allocated.  When you find a free block that's big enough, change the header struct to show "allocated", set the block size, and plunk down another struct just after this allocated one, marked "free", and with the right size.

Oh, and keep a pointer to the first and last such structs.

"YourFree()" does the opposite-- it takes the pointer passed in, subtracts the headerstruct's size, checks the password to make sure this is a valid header, then it marks the ehader as "free" and links it into the list (probably havingf to start at the head to find the struct previous to this one).

That's about it.    Be sure to use at least one pasword field in the header.  Expect to do alot of debugging to get all the boundary conditions just right.   It wouldnt hurt to look in Knuth volume I to see how he did it ina very clever way.

Kent OlsenDBACommented:

Hi Joe,

Some more things.....

Since this is C and not C++, you MUST have at least one global variable to make this work.  The global variable will contain the pointer to the start of your allocatable memory region.  All requests for memory (and for freeing memory) will start at the pointer and scan your structure.

Your structure will be a linked list or table of memory control structures.  As has been pointed out, each structure will contain at least two fields:  The length of the user data and a flag to indicate whether the block is free or assigned.

Eventually, you'll need to write code for memory cleanup.  When a block is freed, you need to check and see if either of the adjacent blocks are free.  If so, merge them into a larger, contiguous block.  (This may not be required for the first assignment.  But since this is an Operating System class, you WILL have to do this! :)  )

The amount of code that you need to write is quite small.  If the code for any of the required functions won't fit on a page, rethink your approach.

Good Luck -- you'll enjoy this class!

joeyoungkcAuthor Commented:
Thanks for all your comments!

In order to keep track of the free block, we have to create a doubly-linked list to link the free block together as a linklist.
However, this is what the prof post on the newsgroup:
> For example, I have a global variable: char *head which points to the head
> of my (free)linked list.  The linked list is stored in my heap.  Is this
> okay? I also use local variables in malloc and free.
"ABSOLUTELY NO GLOBAL VARIABLES!!!  You must store any persistent variables
in your heap.  You may use local variables within the functions."

So I don't know how to do it without any global variables.


For more detail on memlib():
//To my understanding, mem_init create a 20mb + 2* page size memory allcoation
//perform any necessary initialization, include allocation of initial heap area
int mem_init (void)
    struct sigaction segv_act;

    /* Get system page size */
    page_size = (int) getpagesize();

    /* Allocate heap */
    dseg_lo = (char *) malloc(DSEG_MAX + 2*page_size);
    if (!dseg_lo)
        return -1;

    /* align heap to the next page boundary */
    dseg_lo = (char *) PAGE_ALIGN_UP(dseg_lo);

    /* Install SEGV handler to tell the students the
       type and address of the offending access */
#if defined(LINUX)
    segv_act.sa_handler = (void (*)()) segv_handler;
    segv_act.sa_flags = 0;
    if (sigaction(SIGSEGV, &segv_act, NULL) < 0)
        return -1;

    mp = NULL;

    return 0;
//expand the heap area, the lower and upper boundaries of the heap are dseg_lo and dseg_hi
void *mem_sbrk (ptrdiff_t increment)
    char *new_hi = dseg_hi + increment;
    char *old_hi = dseg_hi;
    long dseg_cursize = dseg_hi - dseg_lo + 1;

    assert(increment > 0);

    /* Resize data segment, if the memory is available */
    if (new_hi > dseg_lo + dseg_size)
        return NULL;
    dseg_hi = new_hi;
    dseg_cursize = dseg_hi - dseg_lo + 1;

    /* Logging */
    dump_printf("s %ld\n", (long)increment);

    return (void *)(old_hi + 1);
int mem_pagesize (void){    return page_size;}
long mem_usage (void){    return dseg_hi - dseg_lo;} // the current size of the heap in bytes

If calls p0 = malloc(4)
then at the first byte, i have to store the length of the block (header field) and then the given 4 words, so make it total of 5 words...
If i free the block, i have to link it the free linked-list....but..

I'm still confused about how to "write" things on my heap, is it the memlib is my heap??
like (given malloc(4) with words (1,2,3,4)
*(dseg_lo ) = 4
*(dseg_lo +1) = 1
*(dseg_lo +2) = 2
*(dseg_lo +3) = 3
*(dseg_lo +4) = 4

Thanks all, I'm the newbie in memory allocation... sorry for all the stupid question...and bad grammer..!

> is it the memlib is my heap??
yes the memory chink returned by mem_init is on the system heap

your way of writing the values is also correct but remember that desg_lo is a char *
Kent OlsenDBACommented:

Making the first element of your memory region be the address of your memory region won't help you.  Neither will putting the address on the heap since you won't know where on the heap that you've placed the value.  Since your functions will be working under an already executing program you will have no way to know what's already on the heap.

But there may be a subtle compromise.

Compile all of your memory managment functions into a single module.  Remember to build a header file that includes all of the correct function prototypes so that you can include it in other programs.

Then in your memory management routine create a variable that is common to the memory functions but is NOT globally available to other programs.  Do that like this:

static char *Head = NULL;

int mem_init (void)
  /*  program code here  */

void *mem_sbrk (ptrdiff_t increment)
  /*  program code here  */

The "static" operator tells the compiler that the variable is common to the routines in this module, but does NOT make the variable global.

I think there is a bit of confusion here
joeyoungkc when you talk about memory management and heap do you mean that from the allocated 20 Mb, you need to create heap and stack etc. on your own in your routines or are you referring to system heap (memory allocated by mem_init is on system heap)

I guess that you have some kind of half done OS (like NACHOS) and have to implement management functions for dynamic memory allocation presuming that you are given a heap of 20 Mb ... am I right ?

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
joeyoungkcAuthor Commented:
Yea, you are right. in memlib - init(), it call malloc() to allocate 20mb for us and i have to use that memory to manage the blocks, free the block and keep track free block.

Now I know how to do it, Thanks all
One last question:
I have this warning alot.
malloc.c:122: warning: assignment from incompatible pointer type
malloc.c:129: warning: assignment from incompatible pointer type
malloc.c: In function `mm_free':
malloc.c:138: warning: assignment from incompatible pointer type
malloc.c: In function `AddToFreeList':
malloc.c:172: warning: assignment makes integer from pointer without a cast
malloc.c:173: warning: assignment makes integer from pointer without a cast

172: *last = (size_t *)ptr;
joeyoungkcAuthor Commented:
122: temp = dseg_lo;
size_t **temp; and
char* dseg_lo

But I don't know how to cast it! I tried all the possibility.

you cannot cast them without a warning
size_t is unsigned long while desg_lo is a char *

temp is supposed to point to a pointer while desg_lo is supposed to point to a char !!!
This looks suspicious to me ... are you sure this is what you want?
joeyoungkcAuthor Commented:
I don't know if I"m doing correctly ( althrough the outcome is what I want)
Because in memlib.c, it allocate 20mb and it use two char pointer to point the lower and higher bound of the heap
dseg_lo and dseg_hi
However, it my malloc(), i need to store an address to dseg_lo, which is the lowest memory space, so i need to
point it with temp,
temp = dseg_lo;
then store things in
*temp = 0X4014a810
So is my method correct?
from whatI could gather, temp points to a location which you wish to return... then why the delaration size_t **temp;
perhaps you want char * temp or char ** temp depending on your implementation
in latter case, you need to have a char * on the heap to which temp points and then carry out the assignment as
*temp = desg_lo;
joeyoungkcAuthor Commented:
In the heap, I need to store a WORD in each block, each word need 4 byte, if I use char *, I can't store 4 byte but 1 byte. So that is why I can't use char.  So I just use size_t pointer to point at the char and write data in  in 4 bytes.

I would call it a hack but will do ... learn to put up with those warnings if you are going to to do it that way ;o)
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.