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 #include "silc.h"
  21
  22 /************************** Types and definitions ***************************/
  23
  24 /* The SilcStack context */
  25 struct SilcStackStruct {
  26   SilcStack parent;                           /* Parent stack */
  27   SilcList stacks;                            /* List of stacks */
  28   SilcStackDataEntry stack;                   /* Allocated stack blocks */
  29   SilcStackFrame *frames;                     /* Allocated stack frames */
  30   SilcStackFrame *frame;                      /* Current stack frame */
  31   SilcUInt32 stack_size;                      /* Default stack size */
  32   SilcUInt32 alignment;                       /* Memory alignment */
  33 #ifdef SILC_DIST_INPLACE
  34   /* Statistics */
  35   SilcUInt32 snum_malloc;
  36   SilcUInt32 sbytes_malloc;
  37   SilcUInt32 snum_errors;
  38 #endif /* SILC_DIST_INPLACE */
  39 };
  40
  41 /************************ Static utility functions **************************/
  42
  43 /* Compute stack block index for the `size'. */
  44
  45 static SilcUInt32 silc_stack_get_index(SilcUInt32 size, SilcUInt32 *ret_bsize)
  46 {
  47   SilcUInt32 bsize, si;
  48
  49   if (size < SILC_STACK_DEFAULT_SIZE)
  50     size = SILC_STACK_DEFAULT_SIZE;
  51   si = 0;
  52   bsize = SILC_STACK_DEFAULT_SIZE;
  53   while (bsize < size) {
  54     bsize <<= 1;
  55     si++;
  56   }
  57
  58   *ret_bsize = bsize;
  59
  60   return si;
  61 }
  62
  63 /* Get stack from `stack' or allocate new one. */
  64
  65 static SilcStackDataEntry silc_stack_ref_stack(SilcStack stack,
  66                                                SilcUInt32 size,
  67                                                SilcUInt32 *ret_si,
  68                                                SilcUInt32 *ret_bsize)
  69 {
  70   SilcStackDataEntry e;
  71   SilcUInt32 si, bsize;
  72
  73   /* Get stack block index and block size for requested size */
  74   si = silc_stack_get_index(size, &bsize);
  75   *ret_si = si;
  76   *ret_bsize = bsize;
  77
  78   SILC_ST_DEBUG(("Get stack block, si %d, size %lu", si, bsize));
  79
  80   /* Get stack that has block that can house our size requirement. */
  81   silc_list_start(stack->stacks);
  82   while ((e = silc_list_get(stack->stacks))) {
  83     if (!e->data[si])
  84       continue;
  85
  86     silc_list_del(stack->stacks, e);
  87     SILC_ST_DEBUG(("Got stack blocks %p from stack %p", e->data, stack));
  88     return e;
  89   }
  90
  91   SILC_ST_DEBUG(("Allocate new stack blocks"));
  92
  93   /* Allocate new stack blocks */
  94   e = silc_calloc(1, sizeof(*e));
  95   if (!e)
  96     return NULL;
  97   e->data[si] = silc_malloc(bsize + SILC_STACK_ALIGN(sizeof(*e->data[0]),
  98                                                      stack->alignment));
  99   if (!e->data[si]) {
 100     silc_free(e);
 101     return NULL;
 102   }
 103   e->data[si]->bytes_left = bsize;
 104   e->si = si;
 105   e->bsize = bsize;
 106
 107   SILC_ST_DEBUG(("Got stack blocks %p from stack %p", e->data, stack));
 108   return e;
 109 }
 110
 111 /* Return the `data' back to the `stack'. */
 112
 113 static void silc_stack_unref_stack(SilcStack stack, SilcStackDataEntry e)
 114 {
 115   int i;
 116
 117   SILC_LOG_DEBUG(("Release stack blocks %p to stack %p, si %d",
 118                   e->data, stack, e->si));
 119
 120   /* Release all blocks from allocations */
 121   for (i = e->si; i < SILC_STACK_BLOCK_NUM; i++) {
 122     if (!e->data[i])
 123       continue;
 124     if (!i)
 125       e->data[i]->bytes_left = e->bsize;
 126     else
 127       e->data[i]->bytes_left = SILC_STACK_BLOCK_SIZE(stack, i);
 128   }
 129
 130   silc_list_add(stack->stacks, e);
 131 }
 132
 133 /* Allocate memory from a specific stack block */
 134
 135 static void *silc_stack_alloc_block(SilcStack stack, SilcStackDataEntry e,
 136                                     SilcUInt32 items, SilcUInt32 size)
 137 {
 138   SilcUInt32 asize;
 139   void *ptr;
 140
 141   /* Get pointer and consume the stack block */
 142   asize = SILC_STACK_ALIGN(items * size, stack->alignment);
 143   ptr = SILC_STACK_DATA_EXT(e->data, e->si, e->bsize, stack->alignment);
 144   e->data[e->si]->bytes_left -= asize;
 145   memset(ptr, 0, items * size);
 146
 147   return ptr;
 148 }
 149
 150 /***************************** SilcStack API ********************************/
 151
 152 /* Allocate the stack */
 153
 154 SilcStack silc_stack_alloc(SilcUInt32 stack_size, SilcStack parent)
 155 {
 156   SilcStack stack;
 157   SilcStackDataEntry e;
 158   SilcUInt32 si = 0, bsize = 0;
 159
 160   stack_size = stack_size ? stack_size : SILC_STACK_DEFAULT_SIZE;
 161   if (stack_size < SILC_STACK_DEFAULT_SIZE)
 162     stack_size = SILC_STACK_DEFAULT_SIZE;
 163
 164   if (parent) {
 165     /* Get stack from parent.  The stack itself is allocated from the
 166        parent. */
 167     e = silc_stack_ref_stack(parent, stack_size, &si, &bsize);
 168     if (!e)
 169       return NULL;
 170
 171     /* Allocate stack from the parent */
 172     stack = silc_stack_alloc_block(parent, e, 1, sizeof(*stack));
 173     if (!stack) {
 174       silc_stack_unref_stack(parent, e);
 175       return NULL;
 176     }
 177
 178     stack->parent = parent;
 179     stack->stack_size = stack_size;
 180     stack->alignment = SILC_STACK_DEFAULT_ALIGN;
 181     silc_list_init(stack->stacks, struct SilcStackDataEntryStruct, next);
 182
 183     /* Allocate stack frames from the parent */
 184     stack->frames = silc_stack_alloc_block(parent, e, SILC_STACK_BLOCK_NUM,
 185                                            sizeof(*stack->frames));
 186     if (!stack->frames) {
 187       silc_stack_unref_stack(parent, e);
 188       return NULL;
 189     }
 190
 191     /* Set the initial stack */
 192     stack->stack = e;
 193   } else {
 194     /* Dynamically allocate new stack */
 195     stack = silc_calloc(1, sizeof(*stack));
 196     if (!stack)
 197       return NULL;
 198
 199     stack->stack_size = stack_size;
 200     stack->alignment = SILC_STACK_DEFAULT_ALIGN;
 201     silc_list_init(stack->stacks, struct SilcStackDataEntryStruct, next);
 202
 203     /* Create initial stack */
 204     stack->stack = silc_calloc(1, sizeof(*stack->stack));
 205     if (!stack->stack) {
 206       silc_free(stack);
 207       return NULL;
 208     }
 209     stack->stack->data[0] =
 210       silc_malloc(stack->stack_size +
 211                   SILC_STACK_ALIGN(sizeof(*stack->stack->data[0]),
 212                                    stack->alignment));
 213     if (!stack->stack->data[0]) {
 214       silc_free(stack->stack);
 215       silc_free(stack);
 216       return NULL;
 217     }
 218     stack->stack->data[0]->bytes_left = stack->stack_size;
 219     stack->stack->si = 0;
 220     stack->stack->bsize = stack->stack_size;
 221
 222     /* Allocate stack frames from the stack itself */
 223     stack->frames = silc_stack_alloc_block(stack, stack->stack,
 224                                            SILC_STACK_DEFAULT_NUM,
 225                                            sizeof(*stack->frames));
 226     if (!stack->frames) {
 227       silc_free(stack->stack->data[0]);
 228       silc_free(stack->stack);
 229       silc_free(stack);
 230       return NULL;
 231     }
 232   }
 233
 234   /* Use the allocated stack in first stack frame */
 235   stack->frame = &stack->frames[0];
 236   stack->frame->prev = NULL;
 237   stack->frame->bytes_used = stack->stack_size;
 238   stack->frame->sp = 1;
 239   stack->frame->si = si;
 240
 241   SILC_LOG_DEBUG(("New stack %p, size %d bytes", stack, stack->stack_size));
 242
 243   return stack;
 244 }
 245
 246 /* Frees the stack and all allocated memory */
 247
 248 void silc_stack_free(SilcStack stack)
 249 {
 250   SilcStackDataEntry e;
 251   int i;
 252
 253   SILC_LOG_DEBUG(("Free stack %p", stack));
 254
 255   if (!stack->parent) {
 256     silc_list_start(stack->stacks);
 257     while ((e = silc_list_get(stack->stacks))) {
 258       for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
 259         silc_free(e->data[i]);
 260       silc_free(e);
 261     }
 262
 263     for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
 264       silc_free(stack->stack->data[i]);
 265     silc_free(stack->stack);
 266
 267     silc_free(stack);
 268   } else {
 269     silc_list_start(stack->stacks);
 270     while ((e = silc_list_get(stack->stacks)))
 271       silc_stack_unref_stack(stack->parent, e);
 272
 273     silc_stack_unref_stack(stack->parent, stack->stack);
 274   }
 275 }
 276
 277 /* Push to next stack frame */
 278
 279 SilcUInt32 silc_stack_push(SilcStack stack, SilcStackFrame *frame)
 280 {
 281   if (!stack)
 282     return 0;
 283
 284   if (!frame) {
 285     if (stack->frame->sp >= SILC_STACK_ALIGN(stack->frame->sp,
 286                                              SILC_STACK_DEFAULT_NUM)) {
 287       SILC_LOG_DEBUG(("SilcStack %p running out of frames, cannot push",
 288                       stack));
 289       return stack->frame->sp;
 290     }
 291
 292     frame = &stack->frames[stack->frame->sp];
 293   }
 294
 295   /* Push */
 296   frame->prev = stack->frame;
 297   frame->sp = stack->frame->sp + 1;
 298   frame->si = stack->frame->si;
 299   frame->bytes_used = stack->stack->data[frame->si]->bytes_left;
 300   stack->frame = frame;
 301
 302   SILC_ST_DEBUG(("Push %p: sp %d -> %d, si %d", stack, frame->prev->sp,
 303                  frame->sp, frame->si));
 304
 305   return stack->frame->sp;
 306 }
 307
 308 /* Pop to previous stack frame */
 309
 310 SilcUInt32 silc_stack_pop(SilcStack stack)
 311 {
 312   SilcUInt32 si;
 313
 314   if (!stack || !stack->frame->prev)
 315     return 0;
 316
 317   /* Pop */
 318   si = stack->frame->si;
 319   while (si > stack->frame->prev->si) {
 320     if (stack->stack->data[si])
 321       stack->stack->data[si]->bytes_left = SILC_STACK_BLOCK_SIZE(stack, si);
 322     si--;
 323   }
 324   stack->stack->data[si]->bytes_left = stack->frame->bytes_used;
 325   stack->frame = stack->frame->prev;
 326
 327   SILC_ST_DEBUG(("Pop %p: sp %d -> %d, si %d", stack, stack->frame->sp + 1,
 328                  stack->frame->sp, stack->frame->si));
 329
 330   return stack->frame->sp + 1;
 331 }
 332
 333 /* Allocate memory.  Returns pointer to the memory or NULL on error. */
 334
 335 void *silc_stack_malloc(SilcStack stack, SilcUInt32 size)
 336 {
 337   void *ptr;
 338   SilcUInt32 bsize, bsize2;
 339   SilcUInt32 si = stack->frame->si;
 340
 341   SILC_STACK_STAT(stack, num_malloc, 1);
 342   SILC_ST_DEBUG(("Allocating %d bytes from %p", size, stack));
 343
 344   if (silc_unlikely(!size)) {
 345     SILC_LOG_ERROR(("Allocation by zero (0)"));
 346     SILC_STACK_STAT(stack, num_errors, 1);
 347     return NULL;
 348   }
 349
 350   if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
 351     SILC_LOG_ERROR(("Allocating too much"));
 352     SILC_STACK_STAT(stack, num_errors, 1);
 353     return NULL;
 354   }
 355
 356   /* Align properly  */
 357   size = SILC_STACK_ALIGN(size, stack->alignment);
 358
 359   /* Compute the size of current stack block */
 360   bsize = SILC_STACK_BLOCK_SIZE(stack, si);
 361
 362   /* See if there is space in the current stack block */
 363   if (stack->stack->data[si]->bytes_left >= size) {
 364     /* Get pointer to the memory */
 365     ptr = SILC_STACK_DATA(stack, si, bsize);
 366     stack->stack->data[si]->bytes_left -= size;
 367     SILC_STACK_STAT(stack, bytes_malloc, size);
 368     return ptr;
 369   }
 370
 371   /* There is not enough space in this block.  Find the spot to stack
 372      block that can handle this size memory. */
 373   if (bsize < SILC_STACK_DEFAULT_SIZE)
 374     bsize = SILC_STACK_DEFAULT_SIZE;
 375   bsize += size;
 376   bsize2 = SILC_STACK_DEFAULT_SIZE;
 377   si = 0;
 378   while (bsize2 < bsize) {
 379     bsize2 <<= 1;
 380     si++;
 381   }
 382   if (silc_unlikely(si >= SILC_STACK_BLOCK_NUM)) {
 383     SILC_LOG_ERROR(("Allocating too large block"));
 384     SILC_STACK_STAT(stack, num_errors, 1);
 385     return NULL;
 386   }
 387
 388   /* Allocate the block if it doesn't exist yet */
 389   if (!stack->stack->data[si]) {
 390     SILC_ST_DEBUG(("Allocating new stack block, %d bytes", bsize2));
 391     stack->stack->data[si] =
 392       silc_malloc(bsize2 +
 393                   SILC_STACK_ALIGN(sizeof(**stack->stack->data),
 394                                    stack->alignment));
 395     if (silc_unlikely(!stack->stack->data[si])) {
 396       SILC_STACK_STAT(stack, num_errors, 1);
 397       return NULL;
 398     }
 399     stack->stack->data[si]->bytes_left = bsize2;
 400   }
 401
 402   /* Now return memory from this new block.  It is guaranteed that in this
 403      block there is enough space for this memory. */
 404   assert(stack->stack->data[si]->bytes_left >= size);
 405   ptr = SILC_STACK_DATA(stack, si, bsize2);
 406   stack->stack->data[si]->bytes_left -= size;
 407   stack->frame->si = si;
 408   SILC_STACK_STAT(stack, bytes_malloc, size);
 409
 410   return ptr;
 411 }
 412
 413 /* Attempts to reallocate memory by changing the size of the `ptr' into
 414    `size'.  This routine works only if the previous allocation to `stack'
 415    was `ptr'.  If there is another memory allocation between allocating
 416    `ptr' and this call this routine will return NULL.  NULL is also returned
 417    if the `size' does not fit into the current block.  If NULL is returned
 418    the old memory remains intact. */
 419
 420 void *silc_stack_realloc(SilcStack stack, SilcUInt32 old_size,
 421                          void *ptr, SilcUInt32 size)
 422 {
 423   SilcUInt32 si = stack->frame->si;
 424   SilcUInt32 bsize;
 425   void *sptr;
 426
 427   if (!ptr)
 428     return silc_stack_malloc(stack, size);
 429
 430   SILC_STACK_STAT(stack, num_malloc, 1);
 431   SILC_ST_DEBUG(("Reallocating %d bytes (%d) from %p", size, old_size, stack));
 432
 433   if (silc_unlikely(!size || !old_size)) {
 434     SILC_LOG_ERROR(("Allocation by zero (0)"));
 435     SILC_STACK_STAT(stack, num_errors, 1);
 436     return NULL;
 437   }
 438
 439   if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
 440     SILC_LOG_ERROR(("Allocating too much"));
 441     SILC_STACK_STAT(stack, num_errors, 1);
 442     return NULL;
 443   }
 444
 445   /* Align properly */
 446   old_size = SILC_STACK_ALIGN(old_size, stack->alignment);
 447
 448   /* Compute the size of current stack block */
 449   bsize = SILC_STACK_BLOCK_SIZE(stack, si);
 450
 451   /* Check that `ptr' is last allocation */
 452   sptr = (unsigned char *)stack->stack->data[si] +
 453     SILC_STACK_ALIGN(sizeof(**stack->stack->data), stack->alignment);
 454   if (stack->stack->data[si]->bytes_left + old_size +
 455       ((unsigned char *)ptr - (unsigned char *)sptr) != bsize) {
 456     SILC_LOG_DEBUG(("Cannot reallocate"));
 457     SILC_STACK_STAT(stack, num_errors, 1);
 458     return NULL;
 459   }
 460
 461   /* Now check that the new size fits to this block */
 462   if (stack->stack->data[si]->bytes_left >= size) {
 463     /* It fits, so simply return the old pointer */
 464     size = SILC_STACK_ALIGN(size, stack->alignment);
 465     stack->stack->data[si]->bytes_left -= (size - old_size);
 466     SILC_STACK_STAT(stack, bytes_malloc, (size - old_size));
 467     return ptr;
 468   }
 469
 470   SILC_LOG_DEBUG(("Cannot reallocate in this block"));
 471   SILC_STACK_STAT(stack, num_errors, 1);
 472   return NULL;
 473 }
 474
 475 /* Set default alignment */
 476
 477 void silc_stack_set_alignment(SilcStack stack, SilcUInt32 alignment)
 478 {
 479   SILC_LOG_DEBUG(("Set stack %p alignment to %d bytes", stack, alignment));
 480   stack->alignment = alignment;
 481 }
 482
 483 /* Get default alignment */
 484
 485 SilcUInt32 silc_stack_get_alignment(SilcStack stack)
 486 {
 487   return stack->alignment;
 488 }
 489
 490 #ifdef SILC_DIST_INPLACE
 491 /* Statistics dumping. */
 492
 493 void silc_stack_stats(SilcStack stack)
 494 {
 495   SilcStackDataEntry e;
 496   SilcUInt32 stack_size = 0;
 497   int i, c = 0;
 498
 499   for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
 500     if (!stack->stack->data[i])
 501       continue;
 502     stack_size += SILC_STACK_BLOCK_SIZE(stack, i);
 503     c++;
 504   }
 505
 506   fprintf(stdout, "\nSilcStack %p statistics :\n\n", stack);
 507   fprintf(stdout, "  Size of stack           : %u\n",
 508           (unsigned int)stack_size);
 509   fprintf(stdout, "  Stack alignment         : %d\n",
 510           (int)stack->alignment);
 511   fprintf(stdout, "  Number of allocs        : %u\n",
 512           (unsigned int)stack->snum_malloc);
 513   fprintf(stdout, "  Bytes allocated         : %u\n",
 514           (unsigned int)stack->sbytes_malloc);
 515   fprintf(stdout, "  Average alloc size      : %.2f\n",
 516           (double)((double)stack->sbytes_malloc / (double)stack->snum_malloc));
 517   fprintf(stdout, "  Number of alloc errors  : %u\n",
 518           (unsigned int)stack->snum_errors);
 519   fprintf(stdout, "  Number of frames        : %u\n",
 520           (unsigned int)SILC_STACK_ALIGN(stack->frame->sp,
 521                                          SILC_STACK_DEFAULT_NUM));
 522   fprintf(stdout, "  Number of blocks        : %u\n", c);
 523   fprintf(stdout, "  Number of stacks        : %d\n",
 524           silc_list_count(stack->stacks));
 525
 526   silc_list_start(stack->stacks);
 527   while ((e = silc_list_get(stack->stacks))) {
 528     stack_size = 0;
 529     c = 0;
 530     for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
 531       if (!e->data[i])
 532         continue;
 533       stack_size += e->data[i]->bytes_left;
 534       c++;
 535     }
 536     fprintf(stdout, "\n  Size of stack           : %u\n",
 537             (unsigned int)stack_size);
 538     fprintf(stdout, "  Number of blocks        : %u\n", c);
 539   }
 540 }
 541 #endif /* SILC_DIST_INPLACE */