Solved

~~~CODING malloc()~~~

Posted on 2003-11-06
16
1,320 Views
Last Modified: 2007-12-19
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.


Thanks
Joe
0
Comment
Question by:joeyoungkc
  • 6
  • 5
  • 2
  • +3
16 Comments
 
LVL 10

Expert Comment

by:Sys_Prog
ID: 9698844
One of the links for malloc various implementations

http://www.cs.colorado.edu/~zorn/Malloc.html


HTH

Amit
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9699011
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

Cheers!
Sunny:o)
0
 
LVL 12

Expert Comment

by:andrewjb
ID: 9700242
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 :-)
0
 
LVL 22

Expert Comment

by:grg99
ID: 9701066
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.

 
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9703017

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!
Kent


0
 

Author Comment

by:joeyoungkc
ID: 9705766
Thanks for all your comments!
1)

Kent,
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.

2)

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;
    sigemptyset(&segv_act.sa_mask);
    segv_act.sa_flags = 0;
    if (sigaction(SIGSEGV, &segv_act, NULL) < 0)
        return -1;
#endif

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

3)
Examples:
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..


4)
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..!
Joe

0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9706922
> 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 *
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9711329

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.


Kent
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 45

Accepted Solution

by:
sunnycoder earned 250 total points
ID: 9712614
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 ?
0
 

Author Comment

by:joeyoungkc
ID: 9720035
Snnycoder,
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;
1
0
 

Author Comment

by:joeyoungkc
ID: 9720047
122: temp = dseg_lo;
where
size_t **temp; and
char* dseg_lo

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

Thanks
Joe
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9720146
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?
0
 

Author Comment

by:joeyoungkc
ID: 9720219
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
etc.
So is my method correct?
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9720324
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;
0
 

Author Comment

by:joeyoungkc
ID: 9723473
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.

0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9728366
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)
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now