lib/silcutil/silcstack.c

   1 /*
   2
   3   silcstack.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2003 - 2007 Pekka Riikonen
   8
   9   This program is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation; version 2 of the License.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18 */
  19
  20 /* #define SILC_STACK_DEBUG 1 */
  21
  22 #include "silc.h"
  23
  24 /* Allocate the stack */
  25
  26 SilcStack silc_stack_alloc(SilcUInt32 stack_size)
  27 {
  28   SilcStack stack;
  29
  30   stack = silc_calloc(1, sizeof(*stack));
  31   if (!stack)
  32     return NULL;
  33
  34   stack->frames = silc_calloc(SILC_STACK_DEFAULT_NUM,
  35                               sizeof(*stack->frames));
  36   if (!stack->frames) {
  37     silc_free(stack);
  38     return NULL;
  39   }
  40   stack->alignment = SILC_STACK_DEFAULT_ALIGN;
  41
  42   /* Create initial stack */
  43   stack->stack_size = stack_size ? stack_size : SILC_STACK_DEFAULT_SIZE;
  44   stack->stack[0] = silc_malloc(stack->stack_size +
  45                                 SILC_STACK_ALIGN(sizeof(*stack->stack[0]),
  46                                                  stack->alignment));
  47   if (!stack->stack[0]) {
  48     silc_free(stack->frames);
  49     silc_free(stack);
  50     return NULL;
  51   }
  52   stack->stack[0]->bytes_left = stack->stack_size;
  53
  54   /* Use the allocated stack in first stack frame */
  55   stack->frame = &stack->frames[0];
  56   stack->frame->prev = NULL;
  57   stack->frame->bytes_used = stack->stack_size;
  58   stack->frame->sp = 1;
  59   stack->frame->si = 0;
  60
  61   return stack;
  62 }
  63
  64 /* Frees the stack and all allocated memory */
  65
  66 void silc_stack_free(SilcStack stack)
  67 {
  68   int i;
  69
  70   silc_free(stack->frames);
  71   for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
  72     silc_free(stack->stack[i]);
  73   silc_free(stack);
  74 }
  75
  76 /* Push to next stack frame */
  77
  78 SilcUInt32 silc_stack_push(SilcStack stack, SilcStackFrame *frame)
  79 {
  80   if (!stack)
  81     return 0;
  82
  83   if (!frame) {
  84     /* See if all frames are in use, and allocate SILC_STACK_DEFAULT_NUM
  85        many new frames if needed. */
  86     if (stack->frame->sp >= SILC_STACK_ALIGN(stack->frame->sp,
  87                                              SILC_STACK_DEFAULT_NUM)) {
  88       int i = stack->frame->sp;
  89       SILC_LOG_DEBUG(("Allocating more stack frames"));
  90       frame = silc_realloc(stack->frames,
  91                            SILC_STACK_ALIGN(i + 1, SILC_STACK_DEFAULT_NUM) *
  92                            sizeof(*stack->frames));
  93       if (!frame)
  94         return 0;
  95       stack->frames = frame;
  96       stack->frame = &stack->frames[i - 1];
  97
  98       /* The prev pointers may become invalid in silc_realloc() */
  99       for (i = 1; i < stack->frame->sp; i++)
 100         stack->frames[i].prev = &stack->frames[i - 1];
 101     }
 102
 103     frame = &stack->frames[stack->frame->sp];
 104   }
 105
 106   /* Push */
 107   frame->prev = stack->frame;
 108   frame->sp = stack->frame->sp + 1;
 109   frame->si = stack->frame->si;
 110   frame->bytes_used = stack->stack[frame->si]->bytes_left;
 111   stack->frame = frame;
 112
 113   SILC_ST_DEBUG(("Push %p: sp %d -> %d, si %d", stack, frame->prev->sp,
 114                  frame->sp, frame->si));
 115
 116   return stack->frame->sp;
 117 }
 118
 119 /* Pop to previous stack frame */
 120
 121 SilcUInt32 silc_stack_pop(SilcStack stack)
 122 {
 123   SilcUInt32 si;
 124
 125   if (!stack)
 126     return 0;
 127
 128   /* Pop */
 129   assert(stack->frame->prev);
 130   si = stack->frame->si;
 131   while (si > stack->frame->prev->si) {
 132     if (stack->stack[si])
 133       stack->stack[si]->bytes_left = SILC_STACK_BLOCK_SIZE(stack, si);
 134     si--;
 135   }
 136   stack->stack[si]->bytes_left = stack->frame->bytes_used;
 137   stack->frame = stack->frame->prev;
 138
 139   SILC_ST_DEBUG(("Pop %p: sp %d -> %d, si %d", stack, stack->frame->sp + 1,
 140                  stack->frame->sp, stack->frame->si));
 141
 142   return stack->frame->sp + 1;
 143 }
 144
 145 /* Allocate memory.  Returns pointer to the memory or NULL on error. */
 146
 147 void *silc_stack_malloc(SilcStack stack, SilcUInt32 size)
 148 {
 149   void *ptr;
 150   SilcUInt32 bsize, bsize2;
 151   SilcUInt32 si = stack->frame->si;
 152
 153   SILC_STACK_STAT(stack, num_malloc, 1);
 154   SILC_ST_DEBUG(("Allocating %d bytes from %p", size, stack));
 155
 156   if (silc_unlikely(!size)) {
 157     SILC_LOG_ERROR(("Allocation by zero (0)"));
 158     SILC_STACK_STAT(stack, num_errors, 1);
 159     return NULL;
 160   }
 161
 162   if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
 163     SILC_LOG_ERROR(("Allocating too much"));
 164     SILC_STACK_STAT(stack, num_errors, 1);
 165     return NULL;
 166   }
 167
 168   /* Align properly  */
 169   size = SILC_STACK_ALIGN(size, stack->alignment);
 170
 171   /* Compute the size of current stack block */
 172   bsize = SILC_STACK_BLOCK_SIZE(stack, si);
 173
 174   /* See if there is space in the current stack block */
 175   if (stack->stack[si]->bytes_left >= size) {
 176     /* Get pointer to the memory */
 177     ptr = SILC_STACK_DATA(stack, si, bsize);
 178     stack->stack[si]->bytes_left -= size;
 179     SILC_STACK_STAT(stack, bytes_malloc, size);
 180     return ptr;
 181   }
 182
 183   /* There is not enough space in this block.  Find the spot to stack
 184      block that can handle this size memory. */
 185   if (bsize < SILC_STACK_DEFAULT_SIZE)
 186     bsize = SILC_STACK_DEFAULT_SIZE;
 187   bsize += size;
 188   bsize2 = SILC_STACK_DEFAULT_SIZE;
 189   si = 0;
 190   while (bsize2 < bsize) {
 191     bsize2 <<= 1;
 192     si++;
 193   }
 194   if (silc_unlikely(si >= SILC_STACK_BLOCK_NUM)) {
 195     SILC_LOG_ERROR(("Allocating too large block"));
 196     SILC_STACK_STAT(stack, num_errors, 1);
 197     return NULL;
 198   }
 199
 200   /* Allocate the block if it doesn't exist yet */
 201   if (!stack->stack[si]) {
 202     SILC_ST_DEBUG(("Allocating new stack block, %d bytes", bsize2));
 203     stack->stack[si] = silc_malloc(bsize2 +
 204                                    SILC_STACK_ALIGN(sizeof(**stack->stack),
 205                                                     stack->alignment));
 206     if (silc_unlikely(!stack->stack[si])) {
 207       SILC_STACK_STAT(stack, num_errors, 1);
 208       return NULL;
 209     }
 210     stack->stack[si]->bytes_left = bsize2;
 211   }
 212
 213   /* Now return memory from this new block.  It is guaranteed that in this
 214      block there is enough space for this memory. */
 215   assert(stack->stack[si]->bytes_left >= size);
 216   ptr = SILC_STACK_DATA(stack, si, bsize2);
 217   stack->stack[si]->bytes_left -= size;
 218   stack->frame->si = si;
 219   SILC_STACK_STAT(stack, bytes_malloc, size);
 220
 221   return ptr;
 222 }
 223
 224 /* Attempts to reallocate memory by changing the size of the `ptr' into
 225    `size'.  This routine works only if the previous allocation to `stack'
 226    was `ptr'.  If there is another memory allocation between allocating
 227    `ptr' and this call this routine will return NULL.  NULL is also returned
 228    if the `size' does not fit into the current block.  If NULL is returned
 229    the old memory remains intact. */
 230
 231 void *silc_stack_realloc(SilcStack stack, SilcUInt32 old_size,
 232                          void *ptr, SilcUInt32 size)
 233 {
 234   SilcUInt32 si = stack->frame->si;
 235   SilcUInt32 bsize;
 236   void *sptr;
 237
 238   if (!ptr)
 239     return silc_stack_malloc(stack, size);
 240
 241   SILC_STACK_STAT(stack, num_malloc, 1);
 242   SILC_ST_DEBUG(("Reallocating %d bytes (%d) from %p", size, old_size, stack));
 243
 244   if (silc_unlikely(!size || !old_size)) {
 245     SILC_LOG_ERROR(("Allocation by zero (0)"));
 246     SILC_STACK_STAT(stack, num_errors, 1);
 247     return NULL;
 248   }
 249
 250   if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
 251     SILC_LOG_ERROR(("Allocating too much"));
 252     SILC_STACK_STAT(stack, num_errors, 1);
 253     return NULL;
 254   }
 255
 256   /* Align properly */
 257   old_size = SILC_STACK_ALIGN(old_size, stack->alignment);
 258
 259   /* Compute the size of current stack block */
 260   bsize = SILC_STACK_BLOCK_SIZE(stack, si);
 261
 262   /* Check that `ptr' is last allocation */
 263   sptr = (unsigned char *)stack->stack[si] +
 264     SILC_STACK_ALIGN(sizeof(**stack->stack), stack->alignment);
 265   if (stack->stack[si]->bytes_left + old_size +
 266       ((unsigned char *)ptr - (unsigned char *)sptr) != bsize) {
 267     SILC_LOG_DEBUG(("Cannot reallocate"));
 268     SILC_STACK_STAT(stack, num_errors, 1);
 269     return NULL;
 270   }
 271
 272   /* Now check that the new size fits to this block */
 273   if (stack->stack[si]->bytes_left >= size) {
 274     /* It fits, so simply return the old pointer */
 275     size = SILC_STACK_ALIGN(size, stack->alignment);
 276     stack->stack[si]->bytes_left -= (size - old_size);
 277     SILC_STACK_STAT(stack, bytes_malloc, (size - old_size));
 278     return ptr;
 279   }
 280
 281   SILC_LOG_DEBUG(("Cannot reallocate in this block"));
 282   SILC_STACK_STAT(stack, num_errors, 1);
 283   return NULL;
 284 }
 285
 286 /* Set default alignment */
 287
 288 void silc_stack_set_alignment(SilcStack stack, SilcUInt32 alignment)
 289 {
 290   SILC_LOG_DEBUG(("Set stack %p alignment to %d bytes", stack, alignment));
 291   stack->alignment = alignment;
 292 }
 293
 294 /* Get default alignment */
 295
 296 SilcUInt32 silc_stack_get_alignment(SilcStack stack)
 297 {
 298   return stack->alignment;
 299 }
 300
 301 #ifdef SILC_DIST_INPLACE
 302 /* Statistics dumping. */
 303
 304 void silc_stack_stats(SilcStack stack)
 305 {
 306   SilcUInt32 stack_size = 0;
 307   int i, c = 0;
 308
 309   for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
 310     if (!stack->stack[i])
 311       continue;
 312     stack_size += SILC_STACK_BLOCK_SIZE(stack, i);
 313     c++;
 314   }
 315
 316   fprintf(stdout, "\nSilcStack %p statistics :\n\n", stack);
 317   fprintf(stdout, "  Size of stack           : %u\n",
 318           (unsigned int)stack_size);
 319   fprintf(stdout, "  Stack alignment         : %d\n",
 320           (int)stack->alignment);
 321   fprintf(stdout, "  Number of allocs        : %u\n",
 322           (unsigned int)stack->snum_malloc);
 323   fprintf(stdout, "  Bytes allocated         : %u\n",
 324           (unsigned int)stack->sbytes_malloc);
 325   fprintf(stdout, "  Average alloc size      : %.2f\n",
 326           (double)((double)stack->sbytes_malloc / (double)stack->snum_malloc));
 327   fprintf(stdout, "  Number of alloc errors  : %u\n",
 328           (unsigned int)stack->snum_errors);
 329   fprintf(stdout, "  Number of frames        : %u\n",
 330           (unsigned int)SILC_STACK_ALIGN(stack->frame->sp,
 331                                          SILC_STACK_DEFAULT_NUM));
 332   fprintf(stdout, "  Number of blocks        : %u\n", c);
 333 }
 334 #endif /* SILC_DIST_INPLACE */