Programming Forums > Application Development > C

metsfan · Apr 19th, 2006, 11:18 PM

Ok, so i have to write an Explicit Free List malloc for my programmign class, and im a bit stuck. I have this function named "place". Basically what "place" does is after the malloc function has aquired a free block of memory greater than or equal to in size of the block you wish to store, it inserts the block into memory, then breaks off any additional space and inserts it back into free memory. Here is what the funciton looks like

(Toggle Plain Text)

static void place(void *bp, size_t asize)
{
  size_t csize = GET_SIZE(HDRP(bp));
  char *tempdata;
     
  if ((csize - asize) >= (DSIZE + OVERHEAD)) {
  
  	tempdata = nextdata - asize - WSIZE;
  	
	PUT(HDRP(tempdata), PACK(asize, 1));
    PUT(FTRP(tempdata), PACK(asize, 1));
    
    nextdata = tempdata;
    
    PUT(HDRP(bp), PACK(csize-asize, 0));
	PUT(FTRP(bp), PACK(csize-asize, 0));
	
	
	
    
  }
  else { 
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
  }
}

some clarifications before I go on, PUT, PACK, FTRP, HDRP, and GET_SIZE are some macros i defined. PUT inserts the value in the second paramter into the first, PACK creates the header, first parameter is the number of bytes in the block, second number is 1 or 0, 1 for allocated, 0 for free. HDRP and FTRP are pointers to the header and footer of the block, respectively. GET_SIZE, pretty self explanitory, returns the block size of a given block. WSIZE is my word size, which is 4 bytes, and DSIZE is the double word size which is 8 bytes, and OVERHEAD is a bit of padding which is also 8 bytes. asize is the size of the block to be inserted, csize is the size of the free memory block we obtained from malloc.

When the function is called, nextdata contains the address of the block in front of it. So i create a char* tempdata, put in it the address of nextdata - asize - WSIZE. I then set the header and footer of this new block as this value tempdata, move the block size into the header, move tempdata into nextdata, and chop that part off the free block, and reinsert it into memory

Now, for the life of me, i cant figure out why it doenst work out this way. Before the function call, the heap is in perfect condition, the predeccessor and successor's are right, the buffer in front, as well as the buffer in the back are all in tact, but as soon as I call this function and it executes this code, the heap doesnt update. Its really really strange, and sometimes it messes up the epilogue buffer as well. I really cant see the bug, if anyone sees it, please point it out, i think this function is the root of many many problems im having

In addition, I have debugged this code extensively. The values are all the ones i wnat them to be, but the block just isnt getting inserted into the heap, i dont know what hte problem

metsfan · Apr 20th, 2006, 12:02 AM

I figured out the solution, i feel bad i always make these long posts after scratching my head for an hour then figure out the solution 10 minutes later =P

anyway, its pretty interesting what i did, check it out

(Toggle Plain Text)

static void place(void *bp, size_t asize)
{
  size_t csize = GET_SIZE(HDRP(bp)) - asize;
     
  if (csize >= (DSIZE + OVERHEAD)) {
      
    PUT(HDRP(bp), PACK(csize, 0));
	PUT(FTRP(bp), PACK(csize, 0));
  	
  	bp = NEXT_BLKP(bp);
	
	PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    
    nextdata = bp;
    
  }
  else { 
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
  }
}

I think the problem was that im using pointers, so what i did is just made the initial value of csize the size of the free memory block minus asize. I then resized the free block, and made another macro called NEXT_BLKP which gives the pointer to the memory location directly following the end of the given block. So, after downsizing bp by asize bytes, the next block would be exactly where i want to start, and since its a different pointer than bp, it works out very nicely

nnxion · Apr 20th, 2006, 2:31 AM

Next time, before posting preprocess it first.

metsfan · Apr 20th, 2006, 11:37 AM

if anyone has any suggestions on how to speed up an explicit free list and make it a bit more memory efficient, it would be most apreciated

Apr 19th, 2006, 11:18 PM	#1
metsfan Programmer Join Date: Dec 2005 Posts: 57 Rep Power: 0	A Malloc question Ok, so i have to write an Explicit Free List malloc for my programmign class, and im a bit stuck. I have this function named "place". Basically what "place" does is after the malloc function has aquired a free block of memory greater than or equal to in size of the block you wish to store, it inserts the block into memory, then breaks off any additional space and inserts it back into free memory. Here is what the funciton looks like (Toggle Plain Text) static void place(void bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)); char tempdata; if ((csize - asize) >= (DSIZE + OVERHEAD)) { tempdata = nextdata - asize - WSIZE; PUT(HDRP(tempdata), PACK(asize, 1)); PUT(FTRP(tempdata), PACK(asize, 1)); nextdata = tempdata; PUT(HDRP(bp), PACK(csize-asize, 0)); PUT(FTRP(bp), PACK(csize-asize, 0)); } else { PUT(HDRP(bp), PACK(csize, 1)); PUT(FTRP(bp), PACK(csize, 1)); } } static void place(void bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)); char tempdata; if ((csize - asize) >= (DSIZE + OVERHEAD)) { tempdata = nextdata - asize - WSIZE; PUT(HDRP(tempdata), PACK(asize, 1)); PUT(FTRP(tempdata), PACK(asize, 1)); nextdata = tempdata; PUT(HDRP(bp), PACK(csize-asize, 0)); PUT(FTRP(bp), PACK(csize-asize, 0)); } else { PUT(HDRP(bp), PACK(csize, 1)); PUT(FTRP(bp), PACK(csize, 1)); } } some clarifications before I go on, PUT, PACK, FTRP, HDRP, and GET_SIZE are some macros i defined. PUT inserts the value in the second paramter into the first, PACK creates the header, first parameter is the number of bytes in the block, second number is 1 or 0, 1 for allocated, 0 for free. HDRP and FTRP are pointers to the header and footer of the block, respectively. GET_SIZE, pretty self explanitory, returns the block size of a given block. WSIZE is my word size, which is 4 bytes, and DSIZE is the double word size which is 8 bytes, and OVERHEAD is a bit of padding which is also 8 bytes. asize is the size of the block to be inserted, csize is the size of the free memory block we obtained from malloc. When the function is called, nextdata contains the address of the block in front of it. So i create a char* tempdata, put in it the address of nextdata - asize - WSIZE. I then set the header and footer of this new block as this value tempdata, move the block size into the header, move tempdata into nextdata, and chop that part off the free block, and reinsert it into memory Now, for the life of me, i cant figure out why it doenst work out this way. Before the function call, the heap is in perfect condition, the predeccessor and successor's are right, the buffer in front, as well as the buffer in the back are all in tact, but as soon as I call this function and it executes this code, the heap doesnt update. Its really really strange, and sometimes it messes up the epilogue buffer as well. I really cant see the bug, if anyone sees it, please point it out, i think this function is the root of many many problems im having In addition, I have debugged this code extensively. The values are all the ones i wnat them to be, but the block just isnt getting inserted into the heap, i dont know what hte problem

Apr 20th, 2006, 12:02 AM	#2
metsfan Programmer Join Date: Dec 2005 Posts: 57 Rep Power: 0	I figured out the solution, i feel bad i always make these long posts after scratching my head for an hour then figure out the solution 10 minutes later =P anyway, its pretty interesting what i did, check it out (Toggle Plain Text) static void place(void bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)) - asize; if (csize >= (DSIZE + OVERHEAD)) { PUT(HDRP(bp), PACK(csize, 0)); PUT(FTRP(bp), PACK(csize, 0)); bp = NEXT_BLKP(bp); PUT(HDRP(bp), PACK(asize, 1)); PUT(FTRP(bp), PACK(asize, 1)); nextdata = bp; } else { PUT(HDRP(bp), PACK(csize, 1)); PUT(FTRP(bp), PACK(csize, 1)); } } static void place(void bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)) - asize; if (csize >= (DSIZE + OVERHEAD)) { PUT(HDRP(bp), PACK(csize, 0)); PUT(FTRP(bp), PACK(csize, 0)); bp = NEXT_BLKP(bp); PUT(HDRP(bp), PACK(asize, 1)); PUT(FTRP(bp), PACK(asize, 1)); nextdata = bp; } else { PUT(HDRP(bp), PACK(csize, 1)); PUT(FTRP(bp), PACK(csize, 1)); } } I think the problem was that im using pointers, so what i did is just made the initial value of csize the size of the free memory block minus asize. I then resized the free block, and made another macro called NEXT_BLKP which gives the pointer to the memory location directly following the end of the given block. So, after downsizing bp by asize bytes, the next block would be exactly where i want to start, and since its a different pointer than bp, it works out very nicely

Apr 20th, 2006, 2:31 AM	#3
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	Next time, before posting preprocess it first. __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 20th, 2006, 11:37 AM	#4
metsfan Programmer Join Date: Dec 2005 Posts: 57 Rep Power: 0	if anyone has any suggestions on how to speed up an explicit free list and make it a bit more memory efficient, it would be most apreciated

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

A Malloc question