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