5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2003 - 2007 Pekka Riikonen
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.
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.
22 /************************** Types and definitions ***************************/
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
38 SilcUInt32 snum_malloc;
39 SilcUInt32 sbytes_malloc;
40 SilcUInt32 snum_errors;
41 #endif /* SILC_DIST_INPLACE */
44 /************************ Static utility functions **************************/
46 /* Compute stack block index for the `size'. */
48 static SilcUInt32 silc_stack_get_index(SilcUInt32 size, SilcUInt32 *ret_bsize)
52 if (size < SILC_STACK_DEFAULT_SIZE)
53 size = SILC_STACK_DEFAULT_SIZE;
55 bsize = SILC_STACK_DEFAULT_SIZE;
56 while (bsize < size) {
66 /* Get stack from `stack' or allocate new one. */
68 static SilcStackDataEntry silc_stack_ref_stack(SilcStack stack,
71 SilcUInt32 *ret_bsize)
76 /* Get stack block index and block size for requested size */
77 si = silc_stack_get_index(size, &bsize);
81 SILC_ST_DEBUG(("Get stack block, si %d, size %lu, stack %p",
84 silc_mutex_lock(stack->lock);
86 /* Get stack that has block that can house our size requirement. */
87 silc_list_start(stack->stacks);
88 while ((e = silc_list_get(stack->stacks))) {
92 silc_list_del(stack->stacks, e);
93 SILC_ST_DEBUG(("Got stack blocks %p from stack %p", e->data, stack));
94 silc_mutex_unlock(stack->lock);
98 silc_mutex_unlock(stack->lock);
100 /* If we are child, get block from parent */
102 return silc_stack_ref_stack(stack->parent, size, ret_si, ret_bsize);
104 SILC_ST_DEBUG(("Allocate new stack blocks"));
106 /* Allocate new stack blocks */
107 e = silc_calloc(1, sizeof(*e));
110 e->data[si] = silc_malloc(bsize + SILC_STACK_ALIGN(sizeof(*e->data[0]),
116 e->data[si]->bytes_left = bsize;
120 SILC_ST_DEBUG(("Got stack blocks %p from stack %p", e->data, stack));
125 /* Return the `data' back to the `stack'. */
127 static void silc_stack_unref_stack(SilcStack stack, SilcStackDataEntry e)
131 SILC_LOG_DEBUG(("Release stack blocks %p to stack %p, si %d",
132 e->data, stack, e->si));
134 /* Release all blocks from allocations */
135 for (i = e->si; i < SILC_STACK_BLOCK_NUM; i++) {
139 e->data[i]->bytes_left = e->bsize;
141 e->data[i]->bytes_left = SILC_STACK_BLOCK_SIZE(stack, i);
144 silc_mutex_lock(stack->lock);
145 silc_list_add(stack->stacks, e);
146 silc_mutex_unlock(stack->lock);
149 /* Allocate memory from a specific stack block */
151 static void *silc_stack_alloc_block(SilcStack stack, SilcStackDataEntry e,
152 SilcUInt32 items, SilcUInt32 size)
157 /* Get pointer and consume the stack block */
158 asize = SILC_STACK_ALIGN(items * size, stack->alignment);
159 ptr = SILC_STACK_DATA_EXT(e->data, e->si, e->bsize, stack->alignment);
160 e->data[e->si]->bytes_left -= asize;
161 memset(ptr, 0, items * size);
166 /***************************** SilcStack API ********************************/
168 /* Allocate the stack */
170 SilcStack silc_stack_alloc(SilcUInt32 stack_size, SilcStack parent)
173 SilcStackDataEntry e;
174 SilcUInt32 si = 0, bsize = 0;
176 stack_size = stack_size ? stack_size : SILC_STACK_DEFAULT_SIZE;
177 if (stack_size < SILC_STACK_DEFAULT_SIZE)
178 stack_size = SILC_STACK_DEFAULT_SIZE;
181 stack_size += ((-stack_size) % 8);
184 /* Get stack from parent. The stack itself is allocated from the
185 parent (but does not consume parent's own stack). */
186 e = silc_stack_ref_stack(parent, stack_size, &si, &bsize);
190 /* Allocate stack from the returned stack. We allocate ourselves from
192 stack = silc_stack_alloc_block(parent, e, 1, sizeof(*stack));
194 silc_stack_unref_stack(parent, e);
198 stack->parent = parent;
199 stack->stack_size = stack_size;
200 stack->alignment = SILC_STACK_DEFAULT_ALIGN;
201 stack->oom_handler = parent->oom_handler;
202 stack->oom_context = parent->oom_context;
203 stack->lock = parent->lock;
204 silc_list_init(stack->stacks, struct SilcStackDataEntryStruct, next);
206 /* Allocate stack frames from the stack itself */
207 stack->frames = silc_stack_alloc_block(stack, e, SILC_STACK_BLOCK_NUM,
208 sizeof(*stack->frames));
209 if (!stack->frames) {
210 silc_stack_unref_stack(parent, e);
214 /* Set the initial stack */
217 /* Dynamically allocate new stack */
218 stack = silc_calloc(1, sizeof(*stack));
222 stack->stack_size = stack_size;
223 stack->alignment = SILC_STACK_DEFAULT_ALIGN;
224 silc_list_init(stack->stacks, struct SilcStackDataEntryStruct, next);
226 /* Create initial stack */
227 stack->stack = silc_calloc(1, sizeof(*stack->stack));
232 stack->stack->data[0] =
233 silc_malloc(stack->stack_size +
234 SILC_STACK_ALIGN(sizeof(*stack->stack->data[0]),
236 if (!stack->stack->data[0]) {
237 silc_free(stack->stack);
241 stack->stack->data[0]->bytes_left = stack->stack_size;
242 stack->stack->si = 0;
243 stack->stack->bsize = stack->stack_size;
245 /* Allocate stack frames from the stack itself */
246 stack->frames = silc_stack_alloc_block(stack, stack->stack,
247 SILC_STACK_DEFAULT_NUM,
248 sizeof(*stack->frames));
249 if (!stack->frames) {
250 silc_free(stack->stack->data[0]);
251 silc_free(stack->stack);
257 silc_mutex_alloc(&stack->lock);
260 /* Use the allocated stack in first stack frame */
261 stack->frame = &stack->frames[0];
262 stack->frame->prev = NULL;
263 stack->frame->bytes_used = stack->stack_size;
264 stack->frame->sp = 1;
265 stack->frame->si = si;
267 SILC_LOG_DEBUG(("New stack %p, size %d bytes", stack, stack->stack_size));
272 /* Frees the stack and all allocated memory */
274 void silc_stack_free(SilcStack stack)
276 SilcStackDataEntry e;
282 SILC_LOG_DEBUG(("Free stack %p", stack));
284 if (!stack->parent) {
285 silc_list_start(stack->stacks);
286 while ((e = silc_list_get(stack->stacks))) {
287 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
288 silc_free(e->data[i]);
292 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
293 silc_free(stack->stack->data[i]);
294 silc_free(stack->stack);
297 silc_mutex_free(stack->lock);
301 /* Return all stack blocks to the parent */
302 silc_list_start(stack->stacks);
303 while ((e = silc_list_get(stack->stacks)))
304 silc_stack_unref_stack(stack->parent, e);
306 silc_stack_unref_stack(stack->parent, stack->stack);
310 /* Push to next stack frame */
312 SilcUInt32 silc_stack_push(SilcStack stack, SilcStackFrame *frame)
318 if (stack->frame->sp >= SILC_STACK_ALIGN(stack->frame->sp,
319 SILC_STACK_DEFAULT_NUM)) {
320 SILC_LOG_DEBUG(("SilcStack %p running out of frames, cannot push",
322 return stack->frame->sp;
325 frame = &stack->frames[stack->frame->sp];
329 frame->prev = stack->frame;
330 frame->sp = stack->frame->sp + 1;
331 frame->si = stack->frame->si;
332 frame->bytes_used = stack->stack->data[frame->si]->bytes_left;
333 stack->frame = frame;
335 SILC_ST_DEBUG(("Push %p: sp %d -> %d, si %d", stack, frame->prev->sp,
336 frame->sp, frame->si));
338 return stack->frame->sp;
341 /* Pop to previous stack frame */
343 SilcUInt32 silc_stack_pop(SilcStack stack)
347 if (!stack || !stack->frame->prev)
351 si = stack->frame->si;
352 while (si > stack->frame->prev->si) {
353 if (stack->stack->data[si])
354 stack->stack->data[si]->bytes_left = SILC_STACK_BLOCK_SIZE(stack, si);
357 stack->stack->data[si]->bytes_left = stack->frame->bytes_used;
358 stack->frame = stack->frame->prev;
360 SILC_ST_DEBUG(("Pop %p: sp %d -> %d, si %d", stack, stack->frame->sp + 1,
361 stack->frame->sp, stack->frame->si));
363 return stack->frame->sp + 1;
366 /* Allocate memory. Returns pointer to the memory or NULL on error. */
368 void *silc_stack_malloc(SilcStack stack, SilcUInt32 size)
371 SilcUInt32 bsize, bsize2;
372 SilcUInt32 si = stack->frame->si;
374 SILC_STACK_STAT(stack, num_malloc, 1);
375 SILC_ST_DEBUG(("Allocating %d bytes from %p", size, stack));
377 if (silc_unlikely(!size)) {
378 SILC_LOG_DEBUG(("Allocation by zero (0)"));
379 silc_set_errno_nofail(SILC_ERR_ZERO_ALLOCATION);
380 SILC_STACK_STAT(stack, num_errors, 1);
384 if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
385 SILC_LOG_DEBUG(("Allocating too much"));
386 silc_set_errno_nofail(SILC_ERR_TOO_LARGE_ALLOCATION);
387 SILC_STACK_STAT(stack, num_errors, 1);
388 if (stack->oom_handler)
389 stack->oom_handler(stack, stack->oom_context);
394 size = SILC_STACK_ALIGN(size, stack->alignment);
396 /* Compute the size of current stack block */
397 bsize = SILC_STACK_BLOCK_SIZE(stack, si);
399 /* See if there is space in the current stack block */
400 if (stack->stack->data[si]->bytes_left >= size) {
401 /* Get pointer to the memory */
402 ptr = SILC_STACK_DATA(stack, si, bsize);
403 stack->stack->data[si]->bytes_left -= size;
404 SILC_STACK_STAT(stack, bytes_malloc, size);
408 /* There is not enough space in this block. Find the spot to stack
409 block that can handle this size memory. */
410 if (bsize < SILC_STACK_DEFAULT_SIZE)
411 bsize = SILC_STACK_DEFAULT_SIZE;
413 bsize2 = SILC_STACK_DEFAULT_SIZE;
415 while (bsize2 < bsize) {
419 if (silc_unlikely(si >= SILC_STACK_BLOCK_NUM)) {
420 SILC_LOG_DEBUG(("Allocating too large block"));
421 silc_set_errno_nofail(SILC_ERR_TOO_LARGE_ALLOCATION);
422 SILC_STACK_STAT(stack, num_errors, 1);
423 if (stack->oom_handler)
424 stack->oom_handler(stack, stack->oom_context);
428 /* Allocate the block if it doesn't exist yet */
429 if (!stack->stack->data[si]) {
430 SILC_ST_DEBUG(("Allocating new stack block, %d bytes", bsize2));
431 stack->stack->data[si] =
433 SILC_STACK_ALIGN(sizeof(**stack->stack->data),
435 if (silc_unlikely(!stack->stack->data[si])) {
436 SILC_STACK_STAT(stack, num_errors, 1);
437 if (stack->oom_handler)
438 stack->oom_handler(stack, stack->oom_context);
441 stack->stack->data[si]->bytes_left = bsize2;
444 /* Now return memory from this new block. It is guaranteed that in this
445 block there is enough space for this memory. */
446 assert(stack->stack->data[si]->bytes_left >= size);
447 ptr = SILC_STACK_DATA(stack, si, bsize2);
448 stack->stack->data[si]->bytes_left -= size;
449 stack->frame->si = si;
450 SILC_STACK_STAT(stack, bytes_malloc, size);
455 /* Attempts to reallocate memory by changing the size of the `ptr' into
456 `size'. This routine works only if the previous allocation to `stack'
457 was `ptr'. If there is another memory allocation between allocating
458 `ptr' and this call this routine will return NULL. NULL is also returned
459 if the `size' does not fit into the current block. If NULL is returned
460 the old memory remains intact. */
462 void *silc_stack_realloc(SilcStack stack, SilcUInt32 old_size,
463 void *ptr, SilcUInt32 size)
465 SilcUInt32 si = stack->frame->si;
470 return silc_stack_malloc(stack, size);
472 SILC_STACK_STAT(stack, num_malloc, 1);
473 SILC_ST_DEBUG(("Reallocating %d bytes (%d) from %p", size, old_size, stack));
475 if (silc_unlikely(!size || !old_size)) {
476 SILC_LOG_DEBUG(("Allocation by zero (0)"));
477 silc_set_errno_nofail(SILC_ERR_ZERO_ALLOCATION);
478 SILC_STACK_STAT(stack, num_errors, 1);
482 if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
483 SILC_LOG_DEBUG(("Allocating too much"));
484 silc_set_errno_nofail(SILC_ERR_TOO_LARGE_ALLOCATION);
485 SILC_STACK_STAT(stack, num_errors, 1);
486 if (stack->oom_handler)
487 stack->oom_handler(stack, stack->oom_context);
492 old_size = SILC_STACK_ALIGN(old_size, stack->alignment);
494 /* Compute the size of current stack block */
495 bsize = SILC_STACK_BLOCK_SIZE(stack, si);
497 /* Check that `ptr' is last allocation */
498 sptr = (unsigned char *)stack->stack->data[si] +
499 SILC_STACK_ALIGN(sizeof(**stack->stack->data), stack->alignment);
500 if (stack->stack->data[si]->bytes_left + old_size +
501 ((unsigned char *)ptr - (unsigned char *)sptr) != bsize) {
502 SILC_LOG_DEBUG(("Cannot reallocate"));
503 silc_set_errno_nofail(SILC_ERR_INVALID_ARGUMENT);
504 SILC_STACK_STAT(stack, num_errors, 1);
508 /* Now check that the new size fits to this block */
509 if (stack->stack->data[si]->bytes_left >= size) {
510 /* It fits, so simply return the old pointer */
511 size = SILC_STACK_ALIGN(size, stack->alignment);
512 stack->stack->data[si]->bytes_left -= (size - old_size);
513 SILC_STACK_STAT(stack, bytes_malloc, (size - old_size));
517 SILC_LOG_DEBUG(("Cannot reallocate in this block"));
518 silc_set_errno_reason_nofail(SILC_ERR_TOO_LARGE_ALLOCATION,
519 "Cannot reallocate in this memory block");
520 SILC_STACK_STAT(stack, num_errors, 1);
524 /* Set OOM handler */
526 void silc_stack_set_oom_handler(SilcStack stack,
527 SilcStackOomHandler oom_handler,
530 stack->oom_handler = oom_handler;
531 stack->oom_context = context;
534 /* Set default alignment */
536 void silc_stack_set_alignment(SilcStack stack, SilcUInt32 alignment)
538 SILC_LOG_DEBUG(("Set stack %p alignment to %d bytes", stack, alignment));
539 stack->alignment = alignment;
542 /* Get default alignment */
544 SilcUInt32 silc_stack_get_alignment(SilcStack stack)
546 return stack->alignment;
551 SilcBool silc_stack_purge(SilcStack stack)
553 SilcStackDataEntry e;
554 SilcBool ret = FALSE;
557 SILC_LOG_DEBUG(("Purge stack %p", stack));
559 /* Go through the default stack */
560 for (i = SILC_STACK_BLOCK_NUM - 1; i > 3; i--) {
561 if (stack->stack->data[i] &&
562 stack->stack->data[i]->bytes_left == SILC_STACK_BLOCK_SIZE(stack, i)) {
563 SILC_LOG_DEBUG(("Purge %d bytes",
564 SILC_STACK_BLOCK_SIZE(stack, i)));
565 silc_free(stack->stack->data[i]);
566 stack->stack->data[i] = NULL;
571 silc_mutex_lock(stack->lock);
573 /* Remove one child stack */
574 if (silc_list_count(stack->stacks) > 2) {
575 silc_list_start(stack->stacks);
576 e = silc_list_get(stack->stacks);
578 SILC_LOG_DEBUG(("Remove stack blocks %p", e->data));
579 silc_list_del(stack->stacks, e);
582 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
583 silc_free(e->data[i]);
587 /* Go through the child stacks */
588 silc_list_start(stack->stacks);
589 while ((e = silc_list_get(stack->stacks))) {
590 for (i = SILC_STACK_BLOCK_NUM - 1; i > 3; i--) {
592 SILC_LOG_DEBUG(("Purge %d bytes",
593 SILC_STACK_BLOCK_SIZE(stack, i)));
594 silc_free(e->data[i]);
601 silc_mutex_unlock(stack->lock);
606 #ifdef SILC_DIST_INPLACE
607 /* Statistics dumping. */
609 void silc_stack_stats(SilcStack stack)
611 SilcStackDataEntry e;
612 SilcUInt32 stack_size = 0;
615 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
616 if (!stack->stack->data[i])
618 stack_size += SILC_STACK_BLOCK_SIZE(stack, i);
622 fprintf(stdout, "\nSilcStack %p statistics :\n\n", stack);
623 fprintf(stdout, " Size of stack : %u\n",
624 (unsigned int)stack_size);
625 fprintf(stdout, " Stack alignment : %d\n",
626 (int)stack->alignment);
627 fprintf(stdout, " Number of allocs : %u\n",
628 (unsigned int)stack->snum_malloc);
629 fprintf(stdout, " Bytes allocated : %u\n",
630 (unsigned int)stack->sbytes_malloc);
631 fprintf(stdout, " Average alloc size : %.2f\n",
632 (double)((double)stack->sbytes_malloc / (double)stack->snum_malloc));
633 fprintf(stdout, " Number of alloc errors : %u\n",
634 (unsigned int)stack->snum_errors);
635 fprintf(stdout, " Number of frames : %u\n",
636 (unsigned int)SILC_STACK_ALIGN(stack->frame->sp,
637 SILC_STACK_DEFAULT_NUM));
638 fprintf(stdout, " Number of blocks : %u\n", c);
639 fprintf(stdout, " Number of stacks : %d\n",
640 silc_list_count(stack->stacks));
642 silc_list_start(stack->stacks);
643 while ((e = silc_list_get(stack->stacks))) {
646 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
649 stack_size += e->data[i]->bytes_left;
652 fprintf(stdout, "\n Size of stack : %u\n",
653 (unsigned int)stack_size);
654 fprintf(stdout, " Number of blocks : %u\n", c);
657 #endif /* SILC_DIST_INPLACE */