lib/silcutil/silcstack.c

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