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 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
35 SilcUInt32 snum_malloc;
36 SilcUInt32 sbytes_malloc;
37 SilcUInt32 snum_errors;
38 #endif /* SILC_DIST_INPLACE */
41 /************************ Static utility functions **************************/
43 /* Compute stack block index for the `size'. */
45 static SilcUInt32 silc_stack_get_index(SilcUInt32 size, SilcUInt32 *ret_bsize)
49 if (size < SILC_STACK_DEFAULT_SIZE)
50 size = SILC_STACK_DEFAULT_SIZE;
52 bsize = SILC_STACK_DEFAULT_SIZE;
53 while (bsize < size) {
63 /* Get stack from `stack' or allocate new one. */
65 static SilcStackDataEntry silc_stack_ref_stack(SilcStack stack,
68 SilcUInt32 *ret_bsize)
73 /* Get stack block index and block size for requested size */
74 si = silc_stack_get_index(size, &bsize);
78 SILC_ST_DEBUG(("Get stack block, si %d, size %lu", si, bsize));
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))) {
86 silc_list_del(stack->stacks, e);
87 SILC_ST_DEBUG(("Got stack blocks %p from stack %p", e->data, stack));
91 SILC_ST_DEBUG(("Allocate new stack blocks"));
93 /* Allocate new stack blocks */
94 e = silc_calloc(1, sizeof(*e));
97 e->data[si] = silc_malloc(bsize + SILC_STACK_ALIGN(sizeof(*e->data[0]),
103 e->data[si]->bytes_left = bsize;
107 SILC_ST_DEBUG(("Got stack blocks %p from stack %p", e->data, stack));
111 /* Return the `data' back to the `stack'. */
113 static void silc_stack_unref_stack(SilcStack stack, SilcStackDataEntry e)
117 SILC_LOG_DEBUG(("Release stack blocks %p to stack %p, si %d",
118 e->data, stack, e->si));
120 /* Release all blocks from allocations */
121 for (i = e->si; i < SILC_STACK_BLOCK_NUM; i++) {
125 e->data[i]->bytes_left = e->bsize;
127 e->data[i]->bytes_left = SILC_STACK_BLOCK_SIZE(stack, i);
130 silc_list_add(stack->stacks, e);
133 /* Allocate memory from a specific stack block */
135 static void *silc_stack_alloc_block(SilcStack stack, SilcStackDataEntry e,
136 SilcUInt32 items, SilcUInt32 size)
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);
150 /***************************** SilcStack API ********************************/
152 /* Allocate the stack */
154 SilcStack silc_stack_alloc(SilcUInt32 stack_size, SilcStack parent)
157 SilcStackDataEntry e;
158 SilcUInt32 si = 0, bsize = 0;
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;
165 /* Get stack from parent. The stack itself is allocated from the
167 e = silc_stack_ref_stack(parent, stack_size, &si, &bsize);
171 /* Allocate stack from the parent */
172 stack = silc_stack_alloc_block(parent, e, 1, sizeof(*stack));
174 silc_stack_unref_stack(parent, e);
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);
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);
191 /* Set the initial stack */
194 /* Dynamically allocate new stack */
195 stack = silc_calloc(1, sizeof(*stack));
199 stack->stack_size = stack_size;
200 stack->alignment = SILC_STACK_DEFAULT_ALIGN;
201 silc_list_init(stack->stacks, struct SilcStackDataEntryStruct, next);
203 /* Create initial stack */
204 stack->stack = silc_calloc(1, sizeof(*stack->stack));
209 stack->stack->data[0] =
210 silc_malloc(stack->stack_size +
211 SILC_STACK_ALIGN(sizeof(*stack->stack->data[0]),
213 if (!stack->stack->data[0]) {
214 silc_free(stack->stack);
218 stack->stack->data[0]->bytes_left = stack->stack_size;
219 stack->stack->si = 0;
220 stack->stack->bsize = stack->stack_size;
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);
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;
241 SILC_LOG_DEBUG(("New stack %p, size %d bytes", stack, stack->stack_size));
246 /* Frees the stack and all allocated memory */
248 void silc_stack_free(SilcStack stack)
250 SilcStackDataEntry e;
253 SILC_LOG_DEBUG(("Free stack %p", stack));
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]);
263 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++)
264 silc_free(stack->stack->data[i]);
265 silc_free(stack->stack);
269 silc_list_start(stack->stacks);
270 while ((e = silc_list_get(stack->stacks)))
271 silc_stack_unref_stack(stack->parent, e);
273 silc_stack_unref_stack(stack->parent, stack->stack);
277 /* Push to next stack frame */
279 SilcUInt32 silc_stack_push(SilcStack stack, SilcStackFrame *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",
289 return stack->frame->sp;
292 frame = &stack->frames[stack->frame->sp];
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;
302 SILC_ST_DEBUG(("Push %p: sp %d -> %d, si %d", stack, frame->prev->sp,
303 frame->sp, frame->si));
305 return stack->frame->sp;
308 /* Pop to previous stack frame */
310 SilcUInt32 silc_stack_pop(SilcStack stack)
314 if (!stack || !stack->frame->prev)
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);
324 stack->stack->data[si]->bytes_left = stack->frame->bytes_used;
325 stack->frame = stack->frame->prev;
327 SILC_ST_DEBUG(("Pop %p: sp %d -> %d, si %d", stack, stack->frame->sp + 1,
328 stack->frame->sp, stack->frame->si));
330 return stack->frame->sp + 1;
333 /* Allocate memory. Returns pointer to the memory or NULL on error. */
335 void *silc_stack_malloc(SilcStack stack, SilcUInt32 size)
338 SilcUInt32 bsize, bsize2;
339 SilcUInt32 si = stack->frame->si;
341 SILC_STACK_STAT(stack, num_malloc, 1);
342 SILC_ST_DEBUG(("Allocating %d bytes from %p", size, stack));
344 if (silc_unlikely(!size)) {
345 SILC_LOG_ERROR(("Allocation by zero (0)"));
346 SILC_STACK_STAT(stack, num_errors, 1);
350 if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
351 SILC_LOG_ERROR(("Allocating too much"));
352 SILC_STACK_STAT(stack, num_errors, 1);
357 size = SILC_STACK_ALIGN(size, stack->alignment);
359 /* Compute the size of current stack block */
360 bsize = SILC_STACK_BLOCK_SIZE(stack, si);
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);
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;
376 bsize2 = SILC_STACK_DEFAULT_SIZE;
378 while (bsize2 < bsize) {
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);
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] =
393 SILC_STACK_ALIGN(sizeof(**stack->stack->data),
395 if (silc_unlikely(!stack->stack->data[si])) {
396 SILC_STACK_STAT(stack, num_errors, 1);
399 stack->stack->data[si]->bytes_left = bsize2;
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);
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. */
420 void *silc_stack_realloc(SilcStack stack, SilcUInt32 old_size,
421 void *ptr, SilcUInt32 size)
423 SilcUInt32 si = stack->frame->si;
428 return silc_stack_malloc(stack, size);
430 SILC_STACK_STAT(stack, num_malloc, 1);
431 SILC_ST_DEBUG(("Reallocating %d bytes (%d) from %p", size, old_size, stack));
433 if (silc_unlikely(!size || !old_size)) {
434 SILC_LOG_ERROR(("Allocation by zero (0)"));
435 SILC_STACK_STAT(stack, num_errors, 1);
439 if (silc_unlikely(size > SILC_STACK_MAX_ALLOC)) {
440 SILC_LOG_ERROR(("Allocating too much"));
441 SILC_STACK_STAT(stack, num_errors, 1);
446 old_size = SILC_STACK_ALIGN(old_size, stack->alignment);
448 /* Compute the size of current stack block */
449 bsize = SILC_STACK_BLOCK_SIZE(stack, si);
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);
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));
470 SILC_LOG_DEBUG(("Cannot reallocate in this block"));
471 SILC_STACK_STAT(stack, num_errors, 1);
475 /* Set default alignment */
477 void silc_stack_set_alignment(SilcStack stack, SilcUInt32 alignment)
479 SILC_LOG_DEBUG(("Set stack %p alignment to %d bytes", stack, alignment));
480 stack->alignment = alignment;
483 /* Get default alignment */
485 SilcUInt32 silc_stack_get_alignment(SilcStack stack)
487 return stack->alignment;
490 #ifdef SILC_DIST_INPLACE
491 /* Statistics dumping. */
493 void silc_stack_stats(SilcStack stack)
495 SilcStackDataEntry e;
496 SilcUInt32 stack_size = 0;
499 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
500 if (!stack->stack->data[i])
502 stack_size += SILC_STACK_BLOCK_SIZE(stack, i);
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));
526 silc_list_start(stack->stacks);
527 while ((e = silc_list_get(stack->stacks))) {
530 for (i = 0; i < SILC_STACK_BLOCK_NUM; i++) {
533 stack_size += e->data[i]->bytes_left;
536 fprintf(stdout, "\n Size of stack : %u\n",
537 (unsigned int)stack_size);
538 fprintf(stdout, " Number of blocks : %u\n", c);
541 #endif /* SILC_DIST_INPLACE */