Malloc Implementation

Freelist

keep track of available memory which could be all over the heap

A linked list of all available memory block. Specifically, blocks that are NOT currently allocated

Metadata

• Each block has “metadata”—useful information about the block

• We need to keep track of the size of the block

• We also need a pointer to the next node in the list

• The address returned to the user is after the metadata

Malloc and Freelist

• User asks for block of certain size

• Malloc looks through freelist for this size

• If we find such a block, remove it from the freelist and return it to the user!

Can't find a block of the right size?

Divide the block into two parts, one of the correct size, and one with whatever’s left over

Remove and return new block with proper size

don’t have any blocks that are big enough?

• sbrk()
  • System call that gives us a large chunk of heap space to work with
  • We can add this new block to freelist and continue

• sbrk returns -1 in case of error
  • If this occurs, we have run out of heap space
  • We should simply return NULL

Out variable

• Pass in a pointer to a local variable in the calling function!

• Pick one type as your "main" return value

• Return the rest of the values by writing to "out" variables

int main(void) {
  char *s; // hello will write to this
  int len = hello(&s);
  // now 's' is "hello"
  ...
}
//Caller passes a pointer to a local variable

// Returns a string along with its length
int hello(char **out) {
  char *c = "hello";
  // how do we return 'c' in 'out'?
  return strlen(c);
}
//Callee uses the pointer to modify the caller's local 
variable