L21 [Dynamic Allocation]

malloc()

malloc stands for Memory Allocation

Example Program

struct r {
    char name[40];
    double gpa;
    struct r *next;
};
struct r *rp;
rp = malloc(sizeof(struct r));

if (rp == NULL){
    /* Handle Error! */
}

What does malloc return? A generic type, since you can malloc anything!

Idiomatic Method

if(!(rp = malloc(sizeof struct r))){
    /* Handle Error Here */
}

This works because NULL == 0

Escape From Type-Checking

• malloc() returns a pointer to at least as many bytes as we requested
• But what is the type of this pointer and how do we use it to store items of a different type?
• malloc is declared as void *malloc(unsigned long)
• C uses the idiom "pointer to void" for a generic pointer
• To be safe, you should cast this pointer into the correct type

int *ip;
ip = (int *)malloc(sizeofint);

Done With a Chunk of Storage

Once you're done with a chunk of storage, use free() to make it available for reuse. Remember that C doesn't do garbage collection.

With modern C libraries, free(NULL) does nothing but isn't an error.

After free()

The variable rp still exists after you free, but it now points to garbage data. You shouldn't dereference rp again, but it is ok to assign a new value to rp.

Memory Allocation Functions

void *malloc(size_t n);

Allocates (at least) n bytes of memory on the heap, returns a pointer to it

• Assume memory contains garbage values

void *calloc(size_t num, size_t size);

Allocates (at least) num*size bytes of memory on the heap, returns a pointer to it

• Memory is zeroed out
• Slower than malloc because you have to zero out everything

void *realloc(void *ptr, size_t n);

Reallocates (at least) n bytes of memory on the heap, returns a pointer to it

• Copies the data starting at ptr that was previously allocated
• Often used to expand the memory size

What it does conceptually

• Find space for new allocation
• Copy original data into new space
• Free old space (if reallocation successful)
• Return pointer to new space

realloc may return

• New pointer
• Old pointer
• Null

Random Video

https://www.youtube.com/watch?v=5VnDaHBi8dM

Persistent Data

char *foo(void) {
    char ca[10];
    return ca;
}

Since ca was allocated on stack during function call pointer returned is now pointing to who knows what.

char *foo(void) {
    char *ca = malloc(...);
    return ca;
}

This does work, but the caller needs to know that they are responsible for the free().

Dynamic Allocation: What can go wrong?

• Allocate a block and lose it by losing the value of the pointer
• Allocate a block of memory and use the contents without initialization
• Read or write beyond the boundaries of the block
• Free a block but continue to use the contents
• Call realloc to expand a block of memory and then – once moved – keep using the old address
• FAIL TO NOTICE ERROR RETURNS

Malloc Implementation

K&R Malloc Implementation

• Headers
• Heap Layout
• Allocating the Correct Amount of Memory
• malloc(): Getting the memory for work
• free(): Recycling the memory when done
• morecore(): OS requests for real memory

LinkedList used to track free memory

• Located in the Heap
• Circular Linked List
• This is the free list
  • Contains memory available to be malloc’ed
  • Once memory is malloc’ed, we don’t track it until it is free’d

How K&R Malloc Works

void *malloc(size_t n);

• Delete a node from the free list
• Return a pointer to that node to the program

void free(void *ptr)

• Insert node ptr into the free list

Each node on the free list is available memory

• Everything on the free list is in heap memory areas that malloc has requested from the system
• Other functions can request heap space from the system, but that space will never show up on malloc’s free list
• We want each block in the free list to be as large as possible
  • Therefore when we free a block adjacent to our other memory on the heap, we should merge that block into the adjacent block.

Design Choices

• Linked List is ordered by memory address (in the heap)
• We could also order the linked list from largest to smallest size
• There are many other ways we could implement malloc()

Size in K&R malloc

• Size is in units, not number of bytes
• A block is sizeof(Header) rounded up to the strictest alignment boundary
• A block is 16 bytes in this implementation

Node In The Free List

K&R malloc()

#include <stdbool.h>

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


static Header base = {0};                /* empty list to get started */
static Header* freeptr = NULL;           /* start of free list */


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevptr;
  size_t   nunits;
  void*    result;
  bool     is_allocating;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

  prevptr = freeptr;
  if (prevptr == NULL)                   /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    prevptr     = &base;
    base.s.size = 0;
  }

  is_allocating = true;
  for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* exactly */
      {
        prevptr->s.ptr = p->s.ptr;
      }
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }

      freeptr = prevptr;
      result = p+1;
      is_allocating = false;             /* we are done */
    }

    if (p == freeptr)                    /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        result = NULL;                   /* none left */
        is_allocating = false;
      }
    }
    prevptr = p;
  } /* for */

  return result;
}

sizeof(Header)	Headersize
8	16
12	16
16	16
20	32

K&R free()

void _free(void *ap)
{
    Header *bp, *p;
    bp = (Header *)(ap - Headersize);
    /* Find p such that the freed block is between p and p->next */
    for (p = freep; !(p < bp && bp < p->next); p = p->next) {
        /* is *bp at either end of the arena? */
        if (p >= p->next && (bp > p || bp < p->next)) break;
    }
    
    /* Look to see if we're adjacent to the block after the freed block */
    if ((char *)bp + bp->size * Headersize == (char *)p->next) {
        bp->size += p->next->size;
        bp->next = p->next->next;
    }
    else bp->next = p->next;
    
    /* Look to see if we're adjacent to the block before the freed block */
    if ((char *)p + p->size * Headersize == (char *)bp) {
        /* add the freed block to the block at p */
        p->size += bp->size;
        p->next = bp->next;
    }
    else p->next = bp;
    
    freep = p;
}

morecore()

/* Don't ask for any less than NALLOC */
if (nu < NALLOC)
    nu = NALLOC;

cp = sbrk(nu * Headersize);

if (cp == (char *) -1) /* no space */
    return NULL;

/* Take the new block, add a header, and free() it */
up = (Header *) cp;
up->size = nu;

_free((char *)up + Headersize);
return freep;

• sbrk() is a Linux system call to obtain more memory.
• It returns an aligned pointer to the new space or -1 if no space is available
• The -1 is an odd historical artifact

Recitation Notes

Malloc Error Handling

int *get_array(void) {
    int *ptr = malloc(4*sizeof(int));
    if (!ptr) return NULL;
    ptr[2] = 7;
    int *new_ptr = realloc(ptr, 6*sizeof(int));
    if (!new_ptr) { free(ptr); return NULL; }
    ptr = new_ptr;
    ptr[5] = 12;
    return ptr;
}

Solution: always check the result of malloc & friends! If it returns NULL, handle it appropriately. Always assign the result of realloc to a new pointer and free the old pointer!

Remember that realloc does 2 things

1. If there is space, return new ptr, free old
2. If there is no space, return NULL, don't free old

Deep Cloning

struct dinosaur {
    char *name;
    int coolness; // scale from 1-10
}

struct dinosaur *create_dino(char *name) {
    struct dinosaur *dino = malloc(sizeof(struct dino));
    if (!dino) return NULL;
    dino->name = malloc(strlen(name) + 1);
    if (!dino->name) { free(dino); return NULL; }
    strcpy(dino->name, name);
    dino->coolness = 11;
    return dino;
}

Solution: If you want your struct’s data to be on the heap, you must deep copy any user-provided pointers (including strings) first

Recitation (11/29)

Our implementation of the malloc library must

• Give out free memory
• Take memory back when it's free
• Request more free memory from the OS when we don't have enough

Remember, we keep track of our memory in the freelist

The Freelist

The freelist is a linked list of blocks that are free

• Each block has metadata (information about the size and pointer to next node)
• Knowing this metadata is important for the final!

Basic Malloc Implementation

When the user calls malloc:

1. User asks for block of certain size
2. malloc looks through freelist for size
3. If we find such a block, remove it from the freelist and return it to the user
4. Otherwise, we split a larger block up, or request more space using sbrk (system break)

If we find a smaller block, we just skip it

If we request a size of 25, and the biggest block is a size of 23, we can't combine the remaining space, so we have to call sbrk and request more nodes for the free list.

Matching

There are two types of matching: best match and first match

1. Best Match

We will always iterate through the freelist until we find a block of the correct size

2. First Match

We find the first block with sufficient size and then split up the block

Homework 10 Implementation

Our freelist is a singly-linked, non-circular linked list

• Blocks are ordered by memory address
• Best Match

Free Semantics

What if the user were to free the block of size 20?

• Might end up with adjacent blocks of 40, 20, 60
• Merge nodes after freeing
• We can tell nodes are adjacent because our freelist is ordered by memory address

Canaries

Possibly named after miners using canaries to find gas leaks

Canaries let us ensure that the user isn't writing outside of the block given to them

• We write some pre-defined (potentially random) value to each side of the user data block, and then check that they are correct when the user calls free