malloc.c

Go to the documentation of this file.

/*--------------------------------------------------------------------
 *
 * (C) Copyright Koninklijke Philips Electronics NV 2006. 
 * All rights reserved. This software is licensed under the terms of
 * version 2.1 of the GNU Lesser General Public License as published 
 * by the Free Software Foundation. For licensing and warranty
 * information, see the file COPYING in the main directory.
 *
 *------------------------------------------------------------------*/

 *  If the size of the space requested is zero, return NULL.
 *
 * Uses the boundary-tag allocation method (first fit) with roving pointer.
 * Calls sbrk() as necessary to grow the memory arena by grabbing from the heap,
 * but does not assume that successive sbrk() calls return contiguous memory.
 *
 * Each block (p) in the arena is marked with a size word (p->size)
 * with its low bit (MARKBIT) set if the block is in use.
 * The size|mark word is replicated in the losize word of the successor block
 * to facilitate joining adjacent freed blocks and thus avoid fragmentation.
 * The block can hold a malloc'ed block of up to p->size - OVERHEAD bytes.
 * The free list is maintained as a doubly linked list:
 * each free block contains pointers to previous free and next free block,
 * to facilitate simple addition and deletion of free blocks.
 * The bottom losize word and top size word of each allocated arena contain
 * a 0 | MARKBIT word to indicate a used block of size 0.
 *
 * Reference:
 *  Harry R. Lewis and Larry Denenberg, "Data Structures and
 *  Their Algorithms," Harper Collins, 1991, Chapter 10, pp. 361ff.
 */

#include "trt.h"

#if TRT_MIPSTM

#define EXCL_START()    ien = acquire_lock(trt_heap.lock, 1)
#define EXCL_END()    release_lock(trt_heap.lock, ien)
#define EXCL_END_NO_IEN() release_lock_no_ien(trt_heap.lock)

typedef unsigned int uint;

#define offsetof(s, m)  (size_t)(&(((s *)0)->m))

/* Memory block structure. */
typedef struct  block {
  uint    losize;   /* size | MARKBIT of predecessor */
  uint    size;   /* size | MARKBIT   */
  struct  block *prev;    /* previous free block (if free) */
  struct  block *next;    /* next free block (if free)  */
} BLOCK;

/* Manifest constants. */
#define MARKBIT   1   /* used mark for size field */
#define MINBLOCK  (sizeof(BLOCK)) /* minimum block size   */
#define OVERHEAD  (offsetof(BLOCK, prev)) /* block overhead (if used) */

/*
 * Tuneable manifest constants.
 * N.B. grow_free() forces each allocated BLOCK *p to be ALIGNMENT-aligned,
 * but then the code below currently implicitly assumes the resulting
 * malloc pointer memory(p) to be ALIGNMENT-aligned too.
 * Changing ALIGNMENT here to a larger value here will ->not<- guarantee
 * ALIGNMENT-aligned malloc values unless the code is modified.
 */
#define ALIGNMENT (sizeof(uint))    /* result alignment (2^n) */
#define SBRK_ROUNDUP  2048      /* sbrk() arg roundup (2^n) */

/*
 * Macros:
 *  add(p)    add p to doubly linked freelist
 *  blockp(vp)  convert void * malloc pointer to BLOCK *
 *  bump(p, n)  bump pointer p by n bytes; result is BLOCK *
 *  clearmarks(p) clear the used marks of p
 *  delete(p) delete p from doubly linked list
 *  is_free(p)  iff p is free
 *  is_predfree(p)  iff predecessor of p is free
 *  memory(p) convert BLOCK * to void * malloc pointer
 *  needed(n) min allocation block size for n byte malloc
 *  pred(p)   predecessor of p
 *  pred_size(p)  size of predecessor of p
 *  roundup(n, m) round n up to size m; assumes m is power of 2
 *  setmarks(p) set used marks of p
 *  setsizes(p, n)  set size of p and losize of successor of p to n
 *  succ(p)   successor of p
 */
#define add(p)    (p)->prev = trt_heap.freelist;    \
      (p)->next = trt_heap.freelist->next;  \
      trt_heap.freelist->next = trt_heap.freelist->next->prev = (p);
#define blockp(vp)  bump(vp, -OVERHEAD)
#define bump(p, n)  ((BLOCK *)(((char *)(p)) + (n)))
#define clearmarks(p) (p)->size &= ~MARKBIT; succ(p)->losize &= ~MARKBIT
#define delete(p) (p)->prev->next = (p)->next;  \
      (p)->next->prev = (p)->prev;
#define is_free(p)  (((p)->size & MARKBIT) == 0)
#define is_predfree(p)  (((p)->losize & MARKBIT) == 0)
#define memory(p) ((void *)bump(p, OVERHEAD))
#define needed(n) (((n) + OVERHEAD < MINBLOCK) ? MINBLOCK : (n)+OVERHEAD)
#define pred(p)   bump((p), -pred_size(p))
#define pred_size(p)  ((p)->losize & ~MARKBIT)
#define roundup(n, m) (((n) + (m) - 1) & ~((m) - 1))
#define setmarks(p) (succ(p)->losize = (p)->size = (p)->size | MARKBIT)
#define setsizes(p, n)  (p)->size = (n); succ(p)->losize = (p)->size
#define succ(p)   bump((p), ((p)->size & ~MARKBIT))

/* Static locals. */
static  BLOCK freelist0 = { 0, 0, &freelist0, &freelist0 };

struct heap
{
  volatile int init;  /* initialized?? */
  volatile int lock;  
  BLOCK *freelist;
  BLOCK *rover;
  void *base;
}; 

extern struct heap trt_heap;
/* note: initially locked. mem_init() unlocks it. */

/* Global functions. */

/*
 * Add a non-malloc'ed piece of memory to the free list.
 * Does not check for overlap with the existing arena, caveat utilitor!
 * If we kept a list of the blocks added by this routine,
 * we could modify _alloc_check() to check everything correctly.
 * Instead, _alloc_check() currently only checks the arena grown by
 * grow_free(), and its checks are relaxed once _add_free() is called.
 */
void add_free(void *ptr, size_t size)
{
  BLOCK *p;

  /* Force the memory to be ALIGNMENT-aligned. */
  while (size > 0 && (((uint)ptr) & (ALIGNMENT - 1)) != 0) {
    ptr = (void *)((uint)ptr + 1);
    --size;
  }

  /* Make sure the block is large enough to matter. */
  if (size < MINBLOCK + OVERHEAD)
    return;

  /* Mark the block appropriately and add it to the free list. */
  p = (BLOCK *)ptr;
  size -= OVERHEAD;   /* for empty marker at end */
  p->losize = 0 | MARKBIT;  /* predecessor size 0 */
  setsizes(p, size);    /* size of added block */
  succ(p)->size = 0 | MARKBIT;  /* successor size 0 */
  add(p);       /* add to free list */
}

/* Allocate and clear memory. */
void *calloc(size_t nmemb, size_t size)
{
  void *malloc(size_t size);
  void *s;

  size *= nmemb;
  if ((s = malloc(size)) == NULL)
    return NULL;
  memset(s, 0, size);
  return s;
}

/*
 * Free allocated memory.
 * Avoid fragmentation of the memory arena by joining all adjacent freed blocks.
 */
void free(void *ptr)
{
  BLOCK *p, *q;
  size_t  n;
  int ien;

  if (ptr == NULL)
    return;     /* ANSI says so */

  /* Make sure the block is currently allocated. */
  p = blockp(ptr);
  if (is_free(p)) {   /* block is not allocated */
    return;     /* ignore */
  }
  EXCL_START();
  clearmarks(p);      /* mark this block as free */

  /* Coalese with predecessor block if free. */
  if (is_predfree(p)) {
    /* Coalese this block with free predecessor block. */
    n = p->size;
    p = pred(p);
    setsizes(p, p->size + n);
    delete(p);    /* delete p from the free list */
          /* (it gets put back again below...) */
  }

  /* Coalese with successor block if free. */
  q = succ(p);
  if (is_free(q)) {
    /* Coalese p with successor free block q. */
    setsizes(p, p->size + q->size);
    if (trt_heap.rover == q)
      trt_heap.rover = p;
    delete(q);    /* delete q from the free list */
  }
  add(p);       /* add p to freelist */
  EXCL_END();
}

/* Allocate memory. */
void *malloc(size_t size)
{
  BLOCK *p, *q;
  size_t  m, n;
  int ien;

  if (size == (size_t)0)
    return NULL;    /* implementation-defined behavior */

  /* Search the freelist for a big enough block. */
  EXCL_START();
  n = roundup(needed(size), ALIGNMENT); /* needed memory block size */
  p = trt_heap.rover;
  do {
    if (p->size >= n)
      break;    /* block p is large enough */
    p = p->next;
  } while (p != trt_heap.rover);

  if (p->size < n) {
    EXCL_END();
    return NULL;    /* allocation failed */
  }

  /* Found or allocated a suitable free block p. */
  trt_heap.rover = p->next;
  m = p->size;
  if (m - n >= MINBLOCK) {
    /*
     * Split block p into free and used parts.
     * Rather than leaving the bottom block free
     * and just leaving it on the free list,
     * this leaves the top part free.  This requires an
     * extra add() and delete(), but leaving the top part free
     * helps avoid fragmentation when grow_arena() adds memory,
     * because the top of the previous arena is often free.
     */
    setsizes(p, n);
    q = succ(p);
    setsizes(q, m - n);
    add(q);
  }
  delete(p);    /* delete p from free list */
  setmarks(p);    /* mark p as used */
  EXCL_END();

  return (void *)memory(p);
}

/* Reallocate memory. */
void *realloc(void *ptr, size_t size)
{
  BLOCK *p;
  size_t  old, new;
  void  *vp;
  int ien;

  if (ptr == NULL)
    return malloc(size);  /* ANSI says so */
  if (size == (size_t)0) {
    free(ptr);    /* ANSI says so */
    return NULL;    /* implementation-defined */
  }

  /* Make sure the block is currently allocated. */
  p = blockp(ptr);
  if (is_free(p)) {   /* block is not allocated */
    return NULL;    /* ignore */
  }

  EXCL_START();
  old = (p->size & ~MARKBIT);
  new = roundup(needed(size), ALIGNMENT);
  if (new <= old) {
    /* Shrink the block: either return unchanged or split it. */
    if (old - new < MINBLOCK) {
      EXCL_END();
      return ptr; /* return block unchanged */
    }

    /* Shrink the block by splitting it. */
    setsizes(p, new);
    setmarks(p);
    p = succ(p);
    setsizes(p, old - new);
    add(p);
    EXCL_END();
    return ptr;
  } else {
    /* Grow the block. */
    /* N.B. Could check if enough space in start of next block... */
    EXCL_END();
    if ((vp = malloc(size)) == NULL)
      return NULL;
    memcpy(vp, ptr, old - OVERHEAD);
    free(ptr);
    return vp;
  }
}


void *dsm_ddr_start();
unsigned int dsm_ddr_size();

void mem_init()
{
#ifdef HEAP_IN_STATIC_ARRAY
  static int heap[2 * 1024 * 1024];

  if(atomic_add(trt_heap.init, 1) == 0)
        {
                trt_heap.freelist = &freelist0;
                trt_heap.rover = &freelist0;

    add_free(heap, sizeof(heap));

                serial_out("mem_init: heap = %dMB\n", sizeof(heap) >> 20);

                EXCL_END_NO_IEN();
        }
#else
  /* heap in memory between end of executable and end of memory */

  unsigned int heap_size;
  char *ddr_end, *heap_base;

  if(atomic_add(trt_heap.init, 1) == 0)
  {
    trt_heap.freelist = &freelist0;
    trt_heap.rover = &freelist0;

    ddr_end = (char *) dsm_ddr_start() + dsm_ddr_size();

    heap_base = trt_heap.base;
    heap_size = ddr_end - heap_base;

    add_free(heap_base, heap_size);

    serial_out("mem_init: heap = %dMB\n", heap_size >> 20);

    EXCL_END_NO_IEN();
  }
#endif
}

void mem_update_heap_base(void *new_base)
{
  new_base = (char *) new_base + TRT_BLOCK_SIZE;

  if(trt_heap.base < new_base)
    trt_heap.base = new_base;
}

#endif

---