lib/silcutil/silcstack.c

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