CS 252 malloc implementation

malloc.c

#include <errno.h>
#include <pthread.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "myMalloc.h"
#include "printing.h"

/* Due to the way assert() prints error messges we use out own assert function
 * for deteminism when testing assertions
 */
#ifdef TEST_ASSERT
  inline static void assert(int e) {
    if (!e) {
      const char* msg = "Assertion Failed!\n";
      write(2, msg, strlen(msg));
      exit(1);
    }
  }
#else
  #include <assert.h>
#endif

/*
 * Mutex to ensure thread safety for the freelist
 */
static pthread_mutex_t mutex;

/*
 * Array of sentinel nodes for the freelists
 */
header freelistSentinels[N_LISTS];

/*
 * Pointer to the second fencepost in the most recently allocated chunk from
 * the OS. Used for coalescing chunks
 */
header* lastFencePost;

/*
 * Pointer to maintian the base of the heap to allow printing based on the
 * distance from the base of the heap
 */
void* base;

/*
 * List of chunks allocated by  the OS for printing boundary tags
 */
header* osChunkList [MAX_OS_CHUNKS];
size_t numOsChunks = 0;

/*
 * direct the compiler to run the init function before running main
 * this allows initialization of required globals
 */
static void init (void) __attribute__ ((constructor));

// Helper functions for manipulating pointers to headers
static inline header* get_header_from_offset(void* ptr, ptrdiff_t off);
static inline header* get_left_header(header* h);
static inline header* ptr_to_header(void* p);

// Helper functions for allocating more memory from the OS
static inline void initialize_fencepost(header* fp, size_t left_size);
static inline void insert_os_chunk(header* hdr);
static inline void insert_fenceposts(void* raw_mem, size_t size);
static header* allocate_chunk(size_t size);

// Helper functions for freeing a block
static inline void deallocate_object(void* p);

// Helper functions for allocating a block
static inline header* allocate_object(size_t raw_size);

// Helper functions for verifying that the data structures are structurally
// valid
static inline header* detect_cycles();
static inline header* verify_pointers();
static inline bool verify_freelist();
static inline header* verify_chunk(header* chunk);
static inline bool verify_tags();

static void init();

static bool isMallocInitialized;

/**
 * @brief Helper function to retrieve a header pointer from a pointer and an
 *        offset
 *
 * @param ptr base pointer
 * @param off number of bytes from base pointer where header is located
 *
 * @return a pointer to a header offset bytes from pointer
 */
static inline header* get_header_from_offset(void* ptr, ptrdiff_t off) {
	return (header*)((char*) ptr + off);
}

/**
 * @brief Helper function to get the header to the right of a given header
 *
 * @param h original header
 *
 * @return header to the right of h
 */
header* get_right_header(header* h) {
	return get_header_from_offset(h, get_size(h));
}

/**
 * @brief Helper function to get the header to the left of a given header
 *
 * @param h original header
 *
 * @return header to the right of h
 */
inline static header* get_left_header(header* h) {
  return get_header_from_offset(h, -h->left_size);
}

/**
 * @brief Fenceposts are marked as always allocated and may need to have
 * a left object size to ensure coalescing happens properly
 *
 * @param fp a pointer to the header being used as a fencepost
 * @param left_size the size of the object to the left of the fencepost
 */
inline static void initialize_fencepost(header* fp, size_t left_size) {
	set_state(fp,FENCEPOST);
	set_size(fp, ALLOC_HEADER_SIZE);
	fp->left_size = left_size;
}

/**
 * @brief Helper function to maintain list of chunks from the OS for debugging
 *
 * @param hdr the first fencepost in the chunk allocated by the OS
 */
inline static void insert_os_chunk(header* hdr) {
  if (numOsChunks < MAX_OS_CHUNKS) {
    osChunkList[numOsChunks++] = hdr;
  }
}

/**
 * @brief given a chunk of memory insert fenceposts at the left and
 * right boundaries of the block to prevent coalescing outside of the
 * block
 *
 * @param raw_mem a void pointer to the memory chunk to initialize
 * @param size the size of the allocated chunk
 */
inline static void insert_fenceposts(void* raw_mem, size_t size) {
  // Convert to char* before performing operations
  char* mem = (char*) raw_mem;

  // Insert a fencepost at the left edge of the block
  header* leftFencePost = (header*) mem;
  initialize_fencepost(leftFencePost, ALLOC_HEADER_SIZE);

  // Insert a fencepost at the right edge of the block
  header* rightFencePost = get_header_from_offset(mem, size - ALLOC_HEADER_SIZE);
  initialize_fencepost(rightFencePost, size - 2 * ALLOC_HEADER_SIZE);
}

/**
 * @brief Allocate another chunk from the OS and prepare to insert it
 * into the free list
 *
 * @param size The size to allocate from the OS
 *
 * @return A pointer to the allocable block in the chunk (just after the
 * first fencpost)
 */
static header* allocate_chunk(size_t size) {
  void* mem = sbrk(size);

  insert_fenceposts(mem, size);
  header* hdr = (header*) ((char*)mem + ALLOC_HEADER_SIZE);
  set_state(hdr, UNALLOCATED);
  set_size(hdr, size - 2 * ALLOC_HEADER_SIZE);
  hdr->left_size = ALLOC_HEADER_SIZE;
  return hdr;
}

/**
 * @brief Helper function to get freelist index from size
 *
 * @param sz size of block
 *
 * @return the appropriate freelist index
 */
static size_t get_fl_idx(size_t sz) {
  /* subtract 3 to get 32 byte blocks in index 1 */
  size_t idx = (sz / 8) - 3;
  return idx >= N_LISTS ? N_LISTS - 1 : idx;
}

static void insert_into_fl(size_t fl_idx, header* node) {
  header* sentinel = &freelistSentinels[fl_idx];
  node->next = sentinel->next;
  node->prev = sentinel;
  sentinel->next = node;
  node->next->prev = node;
}
static void remove_from_fl(header* node) {
  node->prev->next = node->next;
  node->next->prev = node->prev;
}

/**
 * @brief Helper allocate an object given a raw request size from the user
 *
 * @param raw_size number of bytes the user needs
 *
 * @return A block satisfying the user's request
 */
static inline header* allocate_object(size_t raw_size) {
  /* determine request size */
  size_t alloc_size = raw_size + ALLOC_HEADER_SIZE;
  /* round request size to nearest 8 byte modulo */
  if (alloc_size % 8) alloc_size += 8 - (alloc_size % 8);
  /* ensure there is room for free list pointers later */
  alloc_size = sizeof(header) > alloc_size ? sizeof(header) : alloc_size;
  size_t fl_idx = get_fl_idx(alloc_size);
  header* node;
  for (size_t i = fl_idx; i < N_LISTS; i++) {
    node = &freelistSentinels[i];
    if (i == N_LISTS - 1) {
      /* final list: check all nodes for one large enough to satisfy request */
      header* sentinel = node;
      while (node->next != sentinel) {
        /* found big enough block */
        if (get_size(node) >= alloc_size) break;
        node = node->next;
      }
    /* check that there's a free block in list */
    } else if (node->next != node) {
      node = node->next;
      break;
    }
  }
  if (node->next == node || get_size(node) == 0 || get_size(node) < alloc_size) { /* sentinel or block too small; request more memory from OS */
    header* block = allocate_chunk(ARENA_SIZE);

    header* prevFencePost = get_header_from_offset(block, -ALLOC_HEADER_SIZE);

    if (get_header_from_offset(prevFencePost, -ALLOC_HEADER_SIZE) == lastFencePost) { /* adjacent chunks; coalesce */
      header* new_header;
      if (get_state(get_left_header(lastFencePost)) == UNALLOCATED) { /* unallocated memory at the end of last chunk to coalesce with */
        new_header = get_left_header(lastFencePost);
        set_size(new_header, get_size(new_header) + (2 * ALLOC_HEADER_SIZE) + get_size(block));
        /* move to appropriately sized freelist */
        remove_from_fl(new_header);
        insert_into_fl(get_fl_idx(get_size(new_header)), new_header);
      } else { /* just clobber last fence post */
        new_header = lastFencePost;
        set_size_and_state(new_header, 2*ALLOC_HEADER_SIZE + get_size(block), UNALLOCATED);
        /* and then insert into freelist */
        insert_into_fl(N_LISTS - 1, new_header);
      }
      // numOsChunks--;
      lastFencePost = get_header_from_offset(new_header, get_size(new_header));
    } else { /* can't coalesce; just insert */
      insert_os_chunk(prevFencePost);
      lastFencePost = get_header_from_offset(block, get_size(block));

      /* insert chunk into the free list */
      insert_into_fl(N_LISTS - 1, block);
    }
    return allocate_object(raw_size);
    // return NULL;
  } else { /* block at least big enough to satisfy request */
    /* if block is right size or remainder is too small, allocate full block */
    if (get_size(node) == alloc_size || (ptrdiff_t)(get_size(node) - alloc_size) < sizeof(header)) {
      set_state(node, ALLOCATED);
      /* remove from freelist */
      remove_from_fl(node);

      return node;
    } else { /* block is big and remainder is enough to split */
      /* left from the perspective of the new header */
      size_t left_size = get_size(node) - alloc_size;
      set_size(node, left_size);
      /* carve out new header in block */
      header* new_header = get_right_header(node);
      set_size_and_state(new_header, alloc_size, ALLOCATED);
      new_header->left_size = left_size;
      /* update left size in next header */
      get_right_header(new_header)->left_size = get_size(new_header);

      /* move left block to appropriate freelist */
      remove_from_fl(node);
      insert_into_fl(get_fl_idx(left_size), node);

      return new_header;
    }
  }
}

/**
 * @brief Helper to get the header from a pointer allocated with malloc
 *
 * @param p pointer to the data region of the block
 *
 * @return A pointer to the header of the block
 */
static inline header* ptr_to_header(void* p) {
  return (header*)((char*) p - ALLOC_HEADER_SIZE); //sizeof(header));
}

/**
 * @brief Helper to manage deallocation of a pointer returned by the user
 *
 * @param p The pointer returned to the user by a call to malloc
 */
static inline void deallocate_object(void* p) {
  if (!p) return;
  header* block = ptr_to_header(p);
  if (get_state(block) == UNALLOCATED) {
    puts("Double Free Detected");
    assert(false);
  }
  set_state(block, UNALLOCATED);

  // get info about the left
  header* left = get_left_header(block);
  enum state left_state = get_state(left);

  // get info about the right
  header* right = get_right_header(block);
  enum state right_state = get_state(right);

  // pointer to block that needs to be inserted to freelist
  header* coalesced;
  if (left_state == UNALLOCATED || right_state == UNALLOCATED) { // one or both are free: coalesce
    if (left_state == UNALLOCATED && right_state == UNALLOCATED) { // coalesce both
      // remove right from freelist
      remove_from_fl(right);
      // right->prev->next = right->next;
      // right->next->prev = right->prev;
      // set size of left block to toal size of the three
      set_size(left, get_size(left) + get_size(block) + get_size(right));
      // update left size of next block
      get_right_header(left)->left_size = get_size(left);
      // update final pointer
      coalesced = left;
      // TODO: spec says block should remain where left block was (if staying in the same list)
      //       but how do we determine if the list is appropriate?
    } else if (left_state == UNALLOCATED) { // coalesce left only
      // set size of left block to total size of left and center
      set_size(left, get_size(left) + get_size(block));
      // update left size of right block
      right->left_size = get_size(left);
      // update final pointer
      coalesced = left;
      // TODO: spec says block should remain where left block was (if staying in the same list)
      //       but how do we determine if the list is appropriate?
    } else if (right_state == UNALLOCATED) { // coalese right only
      // set size of center block to total size of center and right
      set_size(block, get_size(block) + get_size(right));
      // update left size of next block
      get_right_header(block)->left_size = get_size(block);
      // copy right position in freelist to block
      block->prev = right->prev;
      block->next = right->next;
      block->prev->next = block;
      block->next->prev = block;
      // update final pointer
      coalesced = block;
      // TODO: spec says block should remain where right block was (if staying in the same list)
      //       but how do we determine if the list is appropriate?
    } else { // should never happen
      assert(false);
      exit(1);
    }
    // TODO: check if there's a size difference
  } else { // neither are free: only insert
    coalesced = block;
  }
  size_t fl_idx = get_fl_idx(get_size(coalesced));
  if (coalesced->prev || coalesced->next) { // header has old freelist pointers that need to be removed
    remove_from_fl(coalesced);
    // coalesced->prev->next = coalesced->next;
    // coalesced->next->prev = coalesced->prev;
  }
  insert_into_fl(fl_idx, coalesced);
  // header* sentinel = &freelistSentinels[fl_idx];
  // coalesced->prev = sentinel;
  // coalesced->next = sentinel->next;
  // coalesced->next->prev = coalesced;
  // sentinel->next = coalesced;
}

/**
 * @brief Helper to detect cycles in the free list
 * https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare
 *
 * @return One of the nodes in the cycle or NULL if no cycle is present
 */
static inline header* detect_cycles() {
  for (int i = 0; i < N_LISTS; i++) {
    header* freelist = &freelistSentinels[i];
    for (header* slow = freelist->next, * fast = freelist->next->next;
         fast != freelist;
         slow = slow->next, fast = fast->next->next) {
      if (slow == fast) {
        return slow;
      }
    }
  }
  return NULL;
}

/**
 * @brief Helper to verify that there are no unlinked previous or next pointers
 *        in the free list
 *
 * @return A node whose previous and next pointers are incorrect or NULL if no
 *         such node exists
 */
static inline header* verify_pointers() {
  for (int i = 0; i < N_LISTS; i++) {
    header* freelist = &freelistSentinels[i];
    for (header* cur = freelist->next; cur != freelist; cur = cur->next) {
      if (cur->next->prev != cur || cur->prev->next != cur) {
        return cur;
      }
    }
  }
  return NULL;
}

/**
 * @brief Verify the structure of the free list is correct by checkin for
 *        cycles and misdirected pointers
 *
 * @return true if the list is valid
 */
static inline bool verify_freelist() {
  header* cycle = detect_cycles();
  if (cycle != NULL) {
    fprintf(stderr, "Cycle Detected\n");
    print_sublist(print_object, cycle->next, cycle);
    return false;
  }

  header* invalid = verify_pointers();
  if (invalid != NULL) {
    fprintf(stderr, "Invalid pointers\n");
    print_object(invalid);
    return false;
  }

  return true;
}

/**
 * @brief Helper to verify that the sizes in a chunk from the OS are correct
 *        and that allocated node's canary values are correct
 *
 * @param chunk AREA_SIZE chunk allocated from the OS
 *
 * @return a pointer to an invalid header or NULL if all header's are valid
 */
static inline header* verify_chunk(header* chunk) {
	if (get_state(chunk) != FENCEPOST) {
		fprintf(stderr, "Invalid fencepost\n");
		print_object(chunk);
		return chunk;
	}

	for (; get_state(chunk) != FENCEPOST; chunk = get_right_header(chunk)) {
		if (get_size(chunk)  != get_right_header(chunk)->left_size) {
			fprintf(stderr, "Invalid sizes\n");
			print_object(chunk);
			return chunk;
		}
	}

	return NULL;
}

/**
 * @brief For each chunk allocated by the OS verify that the boundary tags
 *        are consistent
 *
 * @return true if the boundary tags are valid
 */
static inline bool verify_tags() {
  for (size_t i = 0; i < numOsChunks; i++) {
    header* invalid = verify_chunk(osChunkList[i]);
    if (invalid != NULL) {
      return invalid;
    }
  }

  return NULL;
}

/**
 * @brief Initialize mutex lock and prepare an initial chunk of memory for allocation
 */
static void init() {
  // Initialize mutex for thread safety
  pthread_mutex_init(&mutex, NULL);

#ifdef DEBUG
  // Manually set printf buffer so it won't call malloc when debugging the allocator
  setvbuf(stdout, NULL, _IONBF, 0);
#endif // DEBUG

  // Allocate the first chunk from the OS
  header* block = allocate_chunk(ARENA_SIZE);

  header* prevFencePost = get_header_from_offset(block, -ALLOC_HEADER_SIZE);
  insert_os_chunk(prevFencePost);

  lastFencePost = get_header_from_offset(block, get_size(block));

  // Set the base pointer to the beginning of the first fencepost in the first
  // chunk from the OS
  base = ((char*) block) - ALLOC_HEADER_SIZE; //sizeof(header);

  // Initialize freelist sentinels
  for (int i = 0; i < N_LISTS; i++) {
    header* freelist = &freelistSentinels[i];
    freelist->next = freelist;
    freelist->prev = freelist;
  }

  // Insert first chunk into the free list
  header* freelist = &freelistSentinels[N_LISTS - 1];
  freelist->next = block;
  freelist->prev = block;
  block->next = freelist;
  block->prev = freelist;
}

/*
 * External interface
 */
void* my_malloc(size_t size) {
  pthread_mutex_lock(&mutex);
  if (size == 0) return NULL;
  header* hdr = allocate_object(size);
  if (!hdr) { perror("nope.avi\n"); exit(-1); }
  // if (!hdr) {
  //   header* block = allocate_chunk(ARENA_SIZE);
  //
  //   header* prevFencePost = get_header_from_offset(block, -ALLOC_HEADER_SIZE);
  //   insert_os_chunk(prevFencePost);
  //
  //   lastFencePost = get_header_from_offset(block, get_size(block));
  //   // Insert chunk into the free list
  //   header* freelist = &freelistSentinels[N_LISTS - 1];
  //   block->next = freelist->next->next;
  //   block->prev = freelist;
  //   freelist->next = block;
  //   block->next->prev = block;
  //
  //   hdr = allocate_object(size);
  // }
  pthread_mutex_unlock(&mutex);
  return hdr->data;
}

void* my_calloc(size_t nmemb, size_t size) {
  return memset(my_malloc(size * nmemb), 0, size * nmemb);
}

void* my_realloc(void* ptr, size_t size) {
  void* mem = my_malloc(size);
  memcpy(mem, ptr, size);
  my_free(ptr);
  return mem;
}

void my_free(void* p) {
  if (!p) return;
  pthread_mutex_lock(&mutex);
  deallocate_object(p);
  pthread_mutex_unlock(&mutex);
}

bool verify() {
  return verify_freelist() && verify_tags();
}