src/libsphinxbase/util/listelem_alloc.c

   1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 /* ====================================================================
   3  * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
   4  * reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * This work was supported in part by funding from the Defense Advanced
  19  * Research Projects Agency and the National Science Foundation of the
  20  * United States of America, and the CMU Sphinx Speech Consortium.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
  23  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  24  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  25  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
  26  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  27  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  28  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  32  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * ====================================================================
  35  *
  36  */
  37
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40
  41 #include "sphinxbase/err.h"
  42 #include "sphinxbase/ckd_alloc.h"
  43 #include "sphinxbase/listelem_alloc.h"
  44 #include "sphinxbase/glist.h"
  45
  46 /**
  47  * Fast linked list allocator.
  48  *
  49  * We keep a separate linked list for each element-size.  Element-size
  50  * must be a multiple of pointer-size.
  51  *
  52  * Initially a block of empty elements is allocated, where the first
  53  * machine word in each element points to the next available element.
  54  * To allocate, we use this pointer to move the freelist to the next
  55  * element, then return the current element.
  56  *
  57  * The last element in the list starts with a NULL pointer, which is
  58  * used as a signal to allocate a new block of elements.
  59  *
  60  * In order to be able to actually release the memory allocated, we
  61  * have to add a linked list of block pointers.  This shouldn't create
  62  * much overhead since we never access it except when freeing the
  63  * allocator.
  64  */
  65 struct listelem_alloc_s {
  66     char **freelist;            /**< ptr to first element in freelist */
  67     glist_t blocks;             /**< Linked list of blocks allocated. */
  68     glist_t blocksize;          /**< Number of elements in each block */
  69     size_t elemsize;            /**< Number of (char *) in element */
  70     size_t blk_alloc;           /**< Number of alloc operations before increasing blocksize */
  71     size_t n_blocks;
  72     size_t n_alloc;
  73     size_t n_freed;
  74 };
  75
  76 #define MIN_ALLOC       50      /**< Minimum number of elements to allocate in one block */
  77 #define BLKID_SHIFT     16      /**< Bit position of block number in element ID */
  78 #define BLKID_MASK ((1<<BLKID_SHIFT)-1)
  79
  80 /**
  81  * Allocate a new block of elements.
  82  */
  83 static void listelem_add_block(listelem_alloc_t *list,
  84                                char *caller_file, int caller_line);
  85
  86 listelem_alloc_t *
  87 listelem_alloc_init(size_t elemsize)
  88 {
  89     listelem_alloc_t *list;
  90
  91     if ((elemsize % sizeof(void *)) != 0) {
  92         size_t rounded = (elemsize + sizeof(void *) - 1) & ~(sizeof(void *)-1);
  93         E_WARN
  94             ("List item size (%lu) not multiple of sizeof(void *), rounding to %lu\n",
  95              (unsigned long)elemsize,
  96              (unsigned long)rounded);
  97         elemsize = rounded;
  98     }
  99     list = ckd_calloc(1, sizeof(*list));
 100     list->freelist = NULL;
 101     list->blocks = NULL;
 102     list->elemsize = elemsize;
 103     /* Intent of this is to increase block size once we allocate
 104      * 256KiB (i.e. 1<<18). If somehow the element size is big enough
 105      * to overflow that, just fail, people should use malloc anyway. */
 106     list->blk_alloc = (1 << 18) / (MIN_ALLOC * elemsize);
 107     if (list->blk_alloc <= 0) {
 108         E_ERROR("Element size * block size exceeds 256k, use malloc instead.\n");
 109         ckd_free(list);
 110         return NULL;
 111     }
 112     list->n_alloc = 0;
 113     list->n_freed = 0;
 114
 115     /* Allocate an initial block to minimize latency. */
 116     listelem_add_block(list, __FILE__, __LINE__);
 117     return list;
 118 }
 119
 120 void
 121 listelem_alloc_free(listelem_alloc_t *list)
 122 {
 123     gnode_t *gn;
 124     if (list == NULL)
 125         return;
 126     for (gn = list->blocks; gn; gn = gnode_next(gn))
 127         ckd_free(gnode_ptr(gn));
 128     glist_free(list->blocks);
 129     glist_free(list->blocksize);
 130     ckd_free(list);
 131 }
 132
 133 static void
 134 listelem_add_block(listelem_alloc_t *list, char *caller_file, int caller_line)
 135 {
 136     char **cpp, *cp;
 137     size_t j;
 138     int32 blocksize;
 139
 140     blocksize = list->blocksize ? gnode_int32(list->blocksize) : MIN_ALLOC;
 141     /* Check if block size should be increased (if many requests for this size) */
 142     if (list->blk_alloc == 0) {
 143         /* See above.  No sense in allocating blocks bigger than
 144          * 256KiB (well, actually, there might be, but we'll worry
 145          * about that later). */
 146         blocksize <<= 1;
 147         if (blocksize * list->elemsize > (1 << 18))
 148             blocksize = (1 << 18) / list->elemsize;
 149         list->blk_alloc = (1 << 18) / (blocksize * list->elemsize);
 150     }
 151
 152     /* Allocate block */
 153     cpp = list->freelist =
 154         (char **) __ckd_calloc__(blocksize, list->elemsize,
 155                                  caller_file, caller_line);
 156     list->blocks = glist_add_ptr(list->blocks, cpp);
 157     list->blocksize = glist_add_int32(list->blocksize, blocksize);
 158     cp = (char *) cpp;
 159     /* Link up the blocks via their first machine word. */
 160     for (j = blocksize - 1; j > 0; --j) {
 161         cp += list->elemsize;
 162         *cpp = cp;
 163         cpp = (char **) cp;
 164     }
 165     /* Make sure the last element's forward pointer is NULL */
 166     *cpp = NULL;
 167     --list->blk_alloc;
 168     ++list->n_blocks;
 169 }
 170
 171
 172 void *
 173 __listelem_malloc__(listelem_alloc_t *list, char *caller_file, int caller_line)
 174 {
 175     char **ptr;
 176
 177     /* Allocate a new block if list empty */
 178     if (list->freelist == NULL)
 179         listelem_add_block(list, caller_file, caller_line);
 180
 181     /* Unlink and return first element in freelist */
 182     ptr = list->freelist;
 183     list->freelist = (char **) (*(list->freelist));
 184     (list->n_alloc)++;
 185
 186     return (void *)ptr;
 187 }
 188
 189 void *
 190 __listelem_malloc_id__(listelem_alloc_t *list, char *caller_file,
 191                        int caller_line, int32 *out_id)
 192 {
 193     char **ptr;
 194
 195     /* Allocate a new block if list empty */
 196     if (list->freelist == NULL)
 197         listelem_add_block(list, caller_file, caller_line);
 198
 199     /* Unlink and return first element in freelist */
 200     ptr = list->freelist;
 201     list->freelist = (char **) (*(list->freelist));
 202     (list->n_alloc)++;
 203
 204     if (out_id) {
 205         int32 blksize, blkidx, ptridx;
 206         gnode_t *gn, *gn2;
 207         char **block;
 208
 209         gn2 = list->blocksize;
 210         block = NULL;
 211         blkidx = 0;
 212         for (gn = list->blocks; gn; gn = gnode_next(gn)) {
 213             block = gnode_ptr(gn);
 214             blksize = gnode_int32(gn2) * list->elemsize / sizeof(*block);
 215             if (ptr >= block && ptr < block + blksize)
 216                 break;
 217             gn2 = gnode_next(gn2);
 218             ++blkidx;
 219         }
 220         if (gn == NULL) {
 221             E_ERROR("Failed to find block index for pointer %p!\n", ptr);
 222         }
 223         ptridx = (ptr - block) / (list->elemsize / sizeof(*block));
 224         E_DEBUG(4,("ptr %p block %p blkidx %d ptridx %d\n",
 225                    ptr, block, list->n_blocks - blkidx - 1, ptridx));
 226         *out_id = ((list->n_blocks - blkidx - 1) << BLKID_SHIFT) | ptridx;
 227     }
 228
 229     return ptr;
 230 }
 231
 232 void *
 233 listelem_get_item(listelem_alloc_t *list, int32 id)
 234 {
 235     int32 blkidx, ptridx, i;
 236     gnode_t *gn;
 237
 238     blkidx = (id >> BLKID_SHIFT) & BLKID_MASK;
 239     ptridx = id & BLKID_MASK;
 240
 241     i = 0;
 242     blkidx = list->n_blocks - blkidx;
 243     for (gn = list->blocks; gn; gn = gnode_next(gn)) {
 244         if (++i == blkidx)
 245             break;
 246     }
 247     if (gn == NULL) {
 248         E_ERROR("Failed to find block index %d\n", blkidx);
 249         return NULL;
 250     }
 251
 252     return (void *)((char **)gnode_ptr(gn)
 253                     + ptridx * (list->elemsize / sizeof(void *)));
 254 }
 255
 256 void
 257 __listelem_free__(listelem_alloc_t *list, void *elem,
 258                   char *caller_file, int caller_line)
 259 {
 260     char **cpp;
 261
 262     /*
 263      * Insert freed item at head of list.
 264      */
 265     cpp = (char **) elem;
 266     *cpp = (char *) list->freelist;
 267     list->freelist = cpp;
 268     (list->n_freed)++;
 269 }
 270
 271
 272 void
 273 listelem_stats(listelem_alloc_t *list)
 274 {
 275     gnode_t *gn, *gn2;
 276     char **cpp;
 277     size_t n;
 278
 279     E_INFO("Linklist stats:\n");
 280     for (n = 0, cpp = list->freelist; cpp;
 281          cpp = (char **) (*cpp), n++);
 282     E_INFO
 283         ("elemsize %lu, #alloc %lu, #freed %lu, #freelist %lu\n",
 284          (unsigned long)list->elemsize,
 285          (unsigned long)list->n_alloc,
 286          (unsigned long)list->n_freed,
 287          (unsigned long)n);
 288     E_INFO("Allocated blocks:\n");
 289     gn2 = list->blocksize;
 290     for (gn = list->blocks; gn; gn = gnode_next(gn)) {
 291         E_INFO("%p (%d * %d bytes)\n", gnode_ptr(gn), gnode_int32(gn2), list->elemsize);
 292         gn2 = gnode_next(gn2);
 293     }
 294 }