teaching machines

CS 330 Lecture 14 – Jeff’s Malloc

February 24, 2014 by Chris Johnson. Filed under cs330, lectures, spring 2014.

Agenda

• what ?s
• finish jmalloc
• what happens when

TODO

• Optional: check out the section of the C FAQ on memory allocation: http://c-faq.com/malloc/index.html.
• Really optional: check out the GNU implementation of malloc.

What Happens When…

• You malloc but you don’t free?
• You write beyond your allocation?
• You free a pointer twice?
• You free memory that’s not your own?
• You free NULL?
• You never malloc?

Code

sizeof.c

#include <stdio.h>
#include <stdlib.h>

#define PRINTSIZE(type) printf("sizeof(" # type "): %ld\n", sizeof(type))

int main(int argc, char **argv) {
  PRINTSIZE(char);
  PRINTSIZE(unsigned char);
  PRINTSIZE(short);
  PRINTSIZE(unsigned short);
  PRINTSIZE(int);
  PRINTSIZE(unsigned int);
  PRINTSIZE(long);
  PRINTSIZE(unsigned long);
  PRINTSIZE(long long);
  PRINTSIZE(unsigned long long);
  PRINTSIZE(float);
  PRINTSIZE(double);
  PRINTSIZE(long double);
  PRINTSIZE(char *);
  PRINTSIZE(short *);
  PRINTSIZE(int *);
  PRINTSIZE(long *);
  PRINTSIZE(float *);
  PRINTSIZE(double *);
  PRINTSIZE(void *);
  return 0;
}

jmalloc.h

#ifndef JMALLOC_H
#define JMALLOC_H

void *jmalloc(int nbytes_requested);
void jfree(void *p);

#endif

jmalloc.c

#include <stdio.h>
#include <string.h>

#include "jmalloc.h"

#define HEAP_SIZE 8192
char heap[HEAP_SIZE];

struct block_t {
  int size;
  struct block_t *next;
  struct block_t *prev;
};

struct block_t *head = NULL;

void show_blocks() {
  for (struct block_t *block = head; block != NULL; block = block->next) {
    printf("%p has %d bytes | ", block, block->size);
  }
  printf("\n");
}

void *jmalloc(int nbytes_requested) {
  // One-time startup costs of initializing free list.
  if (!head) {
    head = (struct block_t *) heap;
    head->size = HEAP_SIZE;
    head->next = NULL;
    head->prev = NULL;
  }
  show_blocks();

  // Assert that we have enough room to put a freed block_t structure.
  // Each requested block will be preceded by its size.
  int nbytes_needed = nbytes_requested + sizeof(int);
  if (nbytes_needed < sizeof(struct block_t)) {
    nbytes_needed = sizeof(struct block_t);
  }

  // Make sure blocks are always a multiple of 16.
  if (nbytes_needed % 16) {
    nbytes_needed += 16 - nbytes_needed % 16;
  }

  // Find a block that has enough capacity to satisfy the request.
  struct block_t *big_enough_block = head;
  while (big_enough_block != NULL && /* stop when we hit the end of the list */
         big_enough_block->size != nbytes_needed && /* stop when we hit a block that's exactly the right size */
         big_enough_block->size < nbytes_needed + sizeof(struct block_t) /* stop when we hit a block that has enough space for the request and a new block node in the free list */) {
    big_enough_block = big_enough_block->next;
  }

  // Hey, fellas. This doesn't look good. No block satisfies.
  if (!big_enough_block) {
    return NULL;
  } else {

    // Either the block was exactly the right size. In this case, there's no new link. We just give back the whole block.
    if (big_enough_block->size == nbytes_needed) {
      if (big_enough_block->prev) {
        big_enough_block->prev->next = big_enough_block->next;
      } else {
        head = big_enough_block->next;
      }

      if (big_enough_block->next) {
        big_enough_block->next->prev = big_enough_block->prev;
      }
    }

    // Or it had some extra space. In this case the new link is going to appear after the reservation.
    else {
      struct block_t *leftovers_block = (struct block_t *) ((char *) big_enough_block + nbytes_needed);
      leftovers_block->size = big_enough_block->size - nbytes_needed;
      leftovers_block->prev = big_enough_block->prev;
      leftovers_block->next = big_enough_block->next;

      if (leftovers_block->prev) {
        leftovers_block->prev->next = leftovers_block;
      }

      if (leftovers_block->next) {
        leftovers_block->next->prev = leftovers_block;
      }

      if (big_enough_block == head) {
        head = leftovers_block;
      }
    }

    // big_enough_block gets sent back, but not before we write its size so that freeing becomes easier.
    int *block_as_int_pointer = (int *) big_enough_block;
    *block_as_int_pointer = nbytes_needed;
    return &block_as_int_pointer[1];
  }
}

void jfree(void *p) {
  // We's gonna prepend the freed block onto the free list. Yes we is!

  // The block starts an int back.
  struct block_t *freed_block = (struct block_t *) ((int *) p - 1);
  /* freed_block->size =  */ // We don't need to write size! It's already there. Hee hee hee!
  freed_block->prev = NULL;
  freed_block->next = head;

  // Make successor know about the new block on the block.
  if (freed_block->next) {
    freed_block->next->prev = freed_block;
  }

  head = freed_block;
  show_blocks();
}

malloc_test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "jmalloc.h"

int main(int argc, char **argv) {
  char *s1 = (char *) jmalloc(sizeof(char) * 25); 
  char *s2 = (char *) jmalloc(sizeof(char) * 72); 
  char *s3 = (char *) jmalloc(sizeof(char) * 37); 
  strcpy(s1, "foo bag");
  strcpy(s2, "carnival");
  strcpy(s3, "parabola");
  printf("s1: %s\n", s1);
  printf("s2: %s\n", s2);
  printf("s3: %s\n", s3);
  jfree(s1);
  jfree(s2);
  jfree(s3);
  /* show_blocks(); */
  s1 = (char *) jmalloc(sizeof(char) * 25); 
  return 0;
}

Haiku