Logo Search packages:      
Sourcecode: lcrash version File versions  Download package

alloc.c

/*
 * $Id: alloc.c,v 1.1 2004/12/21 23:26:19 tjm Exp $
 *
 * This file is part of liballoc.
 * A library which provides memory allocation facilities.
 *
 * Created by Silicon Graphics, Inc.
 *
 * Copyright (C) 2004 Silicon Graphics, Inc. All rights reserved.
 *
 * This code is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version. See the file COPYING for more
 * information.
 */
#include <stdio.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/param.h>
#ifdef ALLOC_DEBUG
#include <assert.h>
#endif
#include <kl_lib.h>
#include <alloc.h>

int alloc_debug = 0;

/* All chunks of memory are strung together via the next and prev
 * links.
 */
typedef struct chunk_s {
      struct chunk_s  *next;     /* Must be first */
      struct chunk_s  *prev;     /* Must be second */
      void        *addr;
      struct bucket_s   *bucketp;
      uint32_t     chunksz;  /* size of memory chunk (via malloc()) */
      uint32_t     blksz;    /* Not including header */
      short        blkcount; /* Number of blksz blocks in chunk */
#ifdef ALLOC_DEBUG
      short        blksfree; /* On bucket freelist */
      uint64_t     chunk_magic;
#endif
} chunk_t;

#ifdef ALLOC_DEBUG
#define CHUNK_MAGIC     0x1baddeed
#endif

/* Header struct used when chaining free blocks together. The chunkp
 * pointer always contains a pointer to the chunk the block was allocated
 * from even when the block is on a freelist.
 */
typedef struct blkhdr_s {
      struct blkhdr_s   *next;      
      union {
            struct blkhdr_s *prev;
            chunk_t           *chunkp;
      } b_un;
      int          flg;
      int          size;
#ifdef ALLOC_DEBUG
      void        *alloc_pc; /* program counter of calling function */
#endif
} blkhdr_t;
#define b_chunkp  b_un.chunkp

/* Flag value that is placed in the block header to indicate if a block
 * was allocated as a B_PERM or B_TEMP block.
 */ 
#define PERMBLK   0x00123456
#define TEMPBLK   0x00654321
#define FREEFLG 0x10000000

#define IS_PERMBLK(blk) (((unsigned long)blk->flg & 0xffffff) == PERMBLK) 
#define IS_TEMPBLK(blk) (((unsigned long)blk->flg & 0xffffff) == TEMPBLK) 

#ifdef ALLOC_DEBUG
static blkhdr_t *permblk_list = (blkhdr_t *)NULL;
#endif

/* Make sure the block header size is 64-bit aligned 
 */
#define BLKHDR_SZ ((sizeof(blkhdr_t)/8 * 8) + (sizeof(blkhdr_t)%8 ? 8 : 0))

static int blkhdr_sz = BLKHDR_SZ;

/* Macros that return pointers to various parts of block 
 */
#define BLK_DATA(blk)   ((void *)((unsigned long)blk + blkhdr_sz))
#define BLK_HDR(blk)    ((blkhdr_t*)((unsigned long)blk - blkhdr_sz))
#define LASTBLK(cp) ((blkhdr_t *)((unsigned long)cp->addr + \
      ((cp->blkcount - 1) * (cp->blksz + blkhdr_sz))))
#define NEXTBLK(blk, cp) ((blkhdr_t *)((unsigned long)blk + \
      (cp->blksz + blkhdr_sz)))     

typedef struct bucket_s {
      int          blksize;
      int          chunkcnt;
      chunk_t           *chunk_list;
      blkhdr_t    *freeblks;
#ifdef ALLOC_DEBUG
      int          blks_alloced;
      int          bad_allocs;
      int          blks_high;
      int          alloc_calls;
      int          free_calls;
#endif
} bucket_t;

typedef struct bucket_rec_s {
      int         size;
      int         blks_per_chunk;
} bucket_rec_t;

#define NBUCKETS 14
#define OVERSZ -1
#ifdef ALLOC_DEBUG
bucket_t bucket[NBUCKETS] =  { 
      { /*     0 */        8, 0, NULL, NULL, 0, 0, 0, 0, 0 },
      { /*     1 */       16, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     2 */       24, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     3 */       32, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     4 */       48, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     5 */       64, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     6 */       96, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     7 */      128, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     8 */      192, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*     9 */      256, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*    10 */      384, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*    11 */      512, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*    12 */     1024, 0, NULL, NULL, 0, 0, 0, 0, 0 },  
      { /*    13 */   OVERSZ, 0, NULL, NULL, 0, 0, 0, 0, 0 } 
};
#else
bucket_t bucket[NBUCKETS] =  { 
      { /*     0 */        8, 0, NULL, NULL }, 
      { /*     1 */       16, 0, NULL, NULL },  
      { /*     2 */       24, 0, NULL, NULL },  
      { /*     3 */       32, 0, NULL, NULL },  
      { /*     4 */       48, 0, NULL, NULL },  
      { /*     5 */       64, 0, NULL, NULL },  
      { /*     6 */       96, 0, NULL, NULL },  
      { /*     7 */      128, 0, NULL, NULL },  
      { /*     8 */      192, 0, NULL, NULL },  
      { /*     9 */      256, 0, NULL, NULL },  
      { /*    10 */      384, 0, NULL, NULL },  
      { /*    11 */      512, 0, NULL, NULL },  
      { /*    12 */     1024, 0, NULL, NULL },  
      { /*    13 */   OVERSZ, 0, NULL, NULL } 
};
#endif
                         
bucket_rec_t bucket_size[] = { 
        /* INDEX       BLKSZ   BLKS/CHUNK */
      { /*     0 */        8,             64 },  
      { /*     1 */       16,             64 },  
      { /*     2 */       24,             32 },  
      { /*     3 */       32,             16 },  
      { /*     4 */       48,             16 },  
      { /*     5 */       64,             16 },  
      { /*     6 */       96,               16 },  
      { /*     7 */      128,             16 },  
      { /*     8 */      192,             16 },  
      { /*     9 */      256,              8 },  
      { /*    10 */      384,              4 },  
      { /*    11 */      512,              4 },  
      { /*    12 */     1024,              2 },  
      { /*    13 */   OVERSZ,              1 } 
};

/* set_aloc_debug()
 */
int 
set_alloc_debug(int adb)
{
      alloc_debug = adb;
}

/* Forward declarations
 */
void print_blk_data(char *, blkhdr_t *);

/*
 * hold_signals() -- Hold signals in critical blocks of code
 */
static void
hold_signals(void)
{
        sighold((int)SIGINT);
        sighold((int)SIGPIPE);
}

/*
 * release_signals() -- Allow signals again
 */
static void
release_signals(void)
{
        sigrelse((int)SIGINT);
        sigrelse((int)SIGPIPE);
}

/*
 * setup_chunk()
 */
static void
setup_chunk(chunk_t *cp)
{
      int i = 0;
      blkhdr_t *blk, *nextblk;

#ifdef ALLOC_DEBUG
      cp->blksfree = cp->blkcount;
#endif
      memset(cp->addr, 0, cp->chunksz);
      blk = cp->addr;
      while (i < cp->blkcount) {
            blk->b_chunkp = cp;
            nextblk = NEXTBLK(blk, cp);
            i++;
            if (i < cp->blkcount) {
                  blk->next = nextblk;
            } else {
                  blk->next = NULL;
            }
            blk = nextblk;
      }
}

/* 
 * alloc_chunk()
 */
static chunk_t *
alloc_chunk(int index, int size)
{
      chunk_t *cp;

      cp = (chunk_t *)malloc(sizeof(chunk_t));
      memset(cp, 0, sizeof(chunk_t));
      if (size) {
            cp->blksz = size;
      } else {
            cp->blksz = bucket_size[index].size;
      }
      cp->blkcount = bucket_size[index].blks_per_chunk;
#ifdef ALLOC_DEBUG
      cp->blksfree = cp->blkcount;
      cp->chunk_magic = CHUNK_MAGIC;
#endif
      cp->bucketp = &bucket[index];
      cp->chunksz = ((cp->blksz + blkhdr_sz) * cp->blkcount);
      cp->addr = (void *)malloc(cp->chunksz);
      setup_chunk(cp);
      ENQUEUE(&bucket[index].chunk_list, cp);
      bucket[index].chunkcnt++;
      return(cp);
}

#ifdef NOTYET
/*
 * free_chunk()
 */
static void
free_chunk(chunk_t *cp)
{
#ifdef ALLOC_DEBUG
      if (!cp || (cp->chunk_magic != CHUNK_MAGIC)) {
            return;
      }
#endif
      if (cp->addr) {
            free(cp->addr);
      }
      free(cp);
}
#endif

/*
 * alloc_temp_blk()
 */
static blkhdr_t *
alloc_temp_blk(int size, void *ra)
{
      int i;
      chunk_t *cp;
      blkhdr_t *blk = NULL;

      /* Find the bucket with the closest fit (next largest) block 
       * size. Then, get a block from that bucket. Note that we do 
       * not search into the OVERSZ bucket.
       */
      for (i = 0; i < (NBUCKETS - 1); i++) {
            if (bucket[i].blksize < size) {
                  continue;
            }
            break;
      }

      /* Check to see if this is an oversize block. If it isn't then
       * check to see if there are any blocks on the freelist. If there
       * aren't, then get the next new block from the chunk.
       */
      if (bucket[i].blksize == OVERSZ) {
            blkhdr_t *lastblk = NULL;

            if ((blk = bucket[i].freeblks)) {
                  while (blk) {
                        cp = blk->b_chunkp;
                        if (cp->chunksz >= size) {
                              break;
                        }
                        lastblk = blk;
                        blk = blk->next;
                  }
            }
            if (blk) {
                  if (lastblk) {
                        lastblk->next = blk->next;
                  } else {
                        bucket[i].freeblks = blk->next;
                  }
            } else {
                  cp = alloc_chunk(i, size);
                  blk = (blkhdr_t *)cp->addr;
            }
      } else if ((blk = bucket[i].freeblks)) {
            cp = blk->b_chunkp;
            bucket[i].freeblks = blk->next;
      } else {
            /* We have to allocate a new chunk 
             */
            cp = alloc_chunk(i, 0);
            blk = (blkhdr_t *)cp->addr;
            bucket[i].freeblks = blk->next;
      }

      /* If we got a block, fill in the rest of the details
       */
      if (blk) {
            memset(blk, 0, (cp->blksz + blkhdr_sz));
            blk->b_chunkp = cp;
            blk->flg = TEMPBLK;
            blk->size = size;
#ifdef ALLOC_DEBUG
            cp->blksfree--;
            blk->alloc_pc = ra;
            bucket[i].alloc_calls++;
            bucket[i].blks_alloced++;
            if (bucket[i].blks_alloced > bucket[i].blks_high) {
                  bucket[i].blks_high = bucket[i].blks_alloced;
            }
      } else {
            bucket[i].bad_allocs++;
            if (alloc_debug) {
                  fprintf(stderr, "alloc_temp_block: Could not allocate "
                        "a block of size %d\n", size);
            }
#endif
      }
      return(blk);
}

/*
 * alloc_block() -- Allocate a block of memory. 
 * 
 */
void *
alloc_block(int size, int flag, void *ra)
{
      blkhdr_t *blk;
      void *b;

      if (size == 0) {
            return((void *)NULL);
      }

      hold_signals();

      if (flag == B_PERM) {
            blk = (void*)malloc(size + blkhdr_sz);
            memset(blk, 0, (size + blkhdr_sz));
            blk->flg = PERMBLK;
            blk->size = size;
#ifdef ALLOC_DEBUG
            blk->alloc_pc = ra;
            ENQUEUE(&permblk_list, blk);
#endif
      } else {
            blk = alloc_temp_blk(size, ra);
      }
      if (blk) {
            if (alloc_debug > 1) {
                  print_blk_data("alloc_block", blk); 
            }
            b = BLK_DATA(blk);
      }
      release_signals();
      return(b);
}

/*
 * realloc_block()
 */
void *
realloc_block(void *b, int new_size, int flag, void *ra)
{
      void *b2;
      blkhdr_t *blk = BLK_HDR(b);

      if ((b2 = alloc_block(new_size, flag, ra))) {
            bcopy(b, b2, blk->size);
            free_block(b);
      }
      return(b2);
}

/*
 * dup_block()
 */
void *
dup_block(void *b, int flag, void *ra)
{
      void *b2;
      blkhdr_t *blk = BLK_HDR(b);
      
      if ((b2 = alloc_block(blk->size, flag, ra))) {
            bcopy(b, b2, blk->size);
      }
      return(b2);
}

/*
 * str_to_block()
 */
void *
str_to_block(char *s, int flag, void *ra)
{
      int size;
      void *b;

      size = strlen(s) + 1;
      b = alloc_block(size, flag, ra);
      bcopy(s, b, size);
      return(b);
}

/*
 * free_block()
 */
void
free_block(void *b)
{
      chunk_t *cp;
      blkhdr_t *blk = BLK_HDR(b);

      if (alloc_debug > 1) {
            print_blk_data("free_block", blk);  
      }
      if (IS_PERMBLK(blk)) {
#ifdef ALLOC_DEBUG
            if (blk->flg & FREEFLG) {
                  print_blk_data("free_block (perm)", blk);
            } else {
                  blk->flg |= FREEFLG;
            }
            REMQUEUE(&permblk_list, blk); 
#endif
            free((void*)blk);
      } else if (IS_TEMPBLK(blk)) {
            cp = blk->b_chunkp;
#ifdef ALLOC_DEBUG
            if (blk->flg & FREEFLG) {
                  print_blk_data("free_block (temp)", blk);
                  assert(!(blk->flg & FREEFLG));
            } else {
                  blk->flg |= FREEFLG;
            }
            cp->bucketp->free_calls++;
            cp->bucketp->blks_alloced--;
#endif
            blk->next = cp->bucketp->freeblks;
            cp->bucketp->freeblks = blk;
#ifdef ALLOC_DEBUG
            cp->blksfree++;
#endif
      } else {
            print_blk_data("free_block", blk);
      }
}

/*
 * print_blk_data()
 */
void
print_blk_data(char *s, blkhdr_t *blk)
{
#ifdef ALLOC_DEBUG
      if (alloc_debug) {
            fprintf(stdout, "%s: blk=0x%lx: flg=0x%lx, alloc_pc=0x%lx\n", 
                  s, blk, blk->flg, blk->alloc_pc);
      }
#endif
}

/*
 * free_temp_blocks() -- Free all temporarily allocated blocks
 */
void
free_temp_blocks(void)
{
      int i;
      blkhdr_t *blk;
      chunk_t *cp;

      /* Now walk through the buckets and clean things up there
       */
      for (i = 0; i < NBUCKETS; i++) {

            /* Clean up the chunks for this bucket and rechain all 
             * of the blocks onto a linked list.
             */
            cp = bucket[i].chunk_list;    
            while(cp) {
#ifdef ALLOC_DEBUG
                  /* Walk through the blocks in this chunk and
                   * print out details for any blocks that had not
                   * been freed properly
                   */
                  blk = cp->addr;
                  while (1) {
                        if (blk->flg == TEMPBLK) {
                              print_blk_data("free_temp_blocks", blk);
                        }
                        if (blk == LASTBLK(cp)) {
                              break;
                        }
                        blk = NEXTBLK(blk, cp);
                  } 
#endif
                  setup_chunk(cp);
                  if ((cp = cp->next) == bucket[i].chunk_list) {
                        break;
                  }
            }

            if (bucket[i].blksize == OVERSZ) {
                  /* Make sure all the oversize bloks are linked
                   * on the freelist.
                   */
                  cp = bucket[i].chunk_list;
                  bucket[i].freeblks = NULL;
                  blk = (blkhdr_t *)NULL;
                  while (cp) {
                        if(blk) {
                              blk->next = cp->addr;
                              blk = blk->next;
                        } else {
                              bucket[i].freeblks = cp->addr;
                              blk = cp->addr;
                        }
                        cp = cp->next;
                        if (cp == bucket[i].chunk_list) {
                              break;
                        }
                  }
                  if (blk) {
                        blk->next = NULL;
                  }
                  continue;
            }
            bucket[i].freeblks = NULL;
            if ((cp = bucket[i].chunk_list)) {
                  bucket[i].freeblks = cp->addr;
                  while (cp->next != bucket[i].chunk_list) {
                        LASTBLK(cp)->next = cp->next->addr;
                        cp = cp->next;
                  }           
            } 
      }
}

/*
 * is_temp_block()
 */
int
is_temp_block(void *p)
{
      blkhdr_t *blk = BLK_HDR(p);

#ifdef ALLOC_DEBUG
      if ((blk->flg == TEMPBLK) &&
            (blk->b_chunkp->chunk_magic == CHUNK_MAGIC)) {
#else
      if (blk->flg == TEMPBLK) {
#endif
            return(1);
      }
      return(0);
}

Generated by  Doxygen 1.6.0   Back to index