data-stack.c revision fd9972c1a2a630f3800ba4c73dd16cf03628cd50
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen data-stack.c : Data stack implementation
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen Copyright (c) 2001-2002 Timo Sirainen
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen Permission is hereby granted, free of charge, to any person obtaining
c0a87e5f3316a57e6f915882fa1951d0fbb74a61Timo Sirainen a copy of this software and associated documentation files (the
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen "Software"), to deal in the Software without restriction, including
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen without limitation the rights to use, copy, modify, merge, publish,
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen distribute, sublicense, and/or sell copies of the Software, and to
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen permit persons to whom the Software is furnished to do so, subject to
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen the following conditions:
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen The above copyright notice and this permission notice shall be
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen included in all copies or substantial portions of the Software.
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainen OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainen MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainen IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen/* @UNSAFE: whole file */
88dc563319efecd6e68bad16b0d92672da05584aTimo Sirainen/* Use malloc() and free() for all memory allocations. Useful for debugging
85a4ae7e8df7ea45a7665828e5edf48a5fc85730Timo Sirainen memory corruption. */
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainen/* #define DISABLE_DATA_STACK */
1b0cfbf3cc77a670b92fff5c30f7b1eb17a63ab1Timo Sirainen/* Initial stack size - this should be kept in a size that doesn't exceed
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen in a normal use to avoid extra malloc()ing. */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* unsigned char data[]; */
0fd246126fece57712566c725d6353f255f5fcfaTimo Sirainen#define SIZEOF_MEMBLOCK MEM_ALIGN(sizeof(struct stack_block))
d0ef8bc2b961a68dd0f75662c2160bd296b9476bTimo Sirainen/* current_frame_block contains last t_push()ed frames. After that new
f4616f1875297fb2f583d913c0f01b075bdecd5bTimo Sirainen stack_frame_block is created and it's ->prev is set to
f4616f1875297fb2f583d913c0f01b075bdecd5bTimo Sirainen current_frame_block. */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenunsigned int data_stack_frame = 0;
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenstatic int frame_pos = BLOCK_FRAME_COUNT-1; /* in current_frame_block */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenstatic struct stack_frame_block *current_frame_block;
bc93929cdd9000ca560a5f42a27f50ab307f1efbTimo Sirainenstatic struct stack_frame_block *unused_frame_blocks;
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenstatic struct stack_block *current_block; /* block now used for allocation */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenstatic struct stack_block *unused_block; /* largest unused block is kept here */
bc93929cdd9000ca560a5f42a27f50ab307f1efbTimo Sirainenunsigned int t_push(void)
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* frame block full */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* kludgy, but allow this before initialization */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* allocate new block */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen frame_block = calloc(sizeof(*frame_block), 1);
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* use existing unused frame_block */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen unused_frame_blocks = unused_frame_blocks->prev;
eef4ba0cc3e78f8c26804c1c9251a76580a41f0cTimo Sirainen /* mark our current position */
eef4ba0cc3e78f8c26804c1c9251a76580a41f0cTimo Sirainen current_frame_block->block[frame_pos] = current_block;
88dc563319efecd6e68bad16b0d92672da05584aTimo Sirainen current_frame_block->block_space_used[frame_pos] = current_block->left;
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = 0;
88dc563319efecd6e68bad16b0d92672da05584aTimo Sirainenstatic void free_blocks(struct stack_block *block)
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* free all the blocks, except if any of them is bigger than
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen unused_block, replace it */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen if (unused_block == NULL || block->size > unused_block->size) {
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenunsigned int t_pop(void)
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* update the current block */
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen current_block = current_frame_block->block[frame_pos];
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen current_block->left = current_frame_block->block_space_used[frame_pos];
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen (current_block->size - current_block->left), 0xde,
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen /* free unused blocks */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* frame block is now unused, add it to unused list */
d54ab8987e482a8df250615b44f41fa040c38741Timo Sirainenstatic struct stack_block *mem_block_alloc(size_t min_size)
88dc563319efecd6e68bad16b0d92672da05584aTimo Sirainen prev_size = current_block == NULL ? 0 : current_block->size;
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen alloc_size = nearest_power(prev_size + min_size);
437a8b0fe254057b0c1f1723d689bafa91cae2abTimo Sirainen "Out of memory when allocating %"PRIuSIZE_T" bytes",
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainenstatic void *t_malloc_real(size_t size, int permanent)
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen i_panic("Trying to allocate %"PRIuSIZE_T" bytes", size);
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* reset t_buffer_get() mark - not really needed but makes it easier
1b0cfbf3cc77a670b92fff5c30f7b1eb17a63ab1Timo Sirainen to notice if t_malloc() is called between t_buffer_get() and
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen t_buffer_alloc() */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* allocate only aligned amount of memory so alignment comes
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen always properly */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* used for t_try_realloc() */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = size;
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* enough space in current block, use it */
2793e3bd31d212d6506686aa70773e13d9d98195Timo Sirainen /* current block is full, see if we can use the unused_block */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen if (unused_block != NULL && unused_block->size >= size) {
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen /* warn later, so that if i_warning() wants to allocate more
ecdce39e5ef4b62eefa9f5818f17d153fd5d710aTimo Sirainen memory we don't go to infinite loop */
ecdce39e5ef4b62eefa9f5818f17d153fd5d710aTimo Sirainen i_warning("Growing data stack with: %"PRIuSIZE_T, block->size);
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen i_panic("Trying to allocate %"PRIuSIZE_T" bytes", size);
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen last_alloc_size = current_frame_block->last_alloc_size[frame_pos];
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen /* see if we're trying to grow the memory we allocated last */
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen /* yeah, see if we have space to grow */
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen if (current_block->left >= size - last_alloc_size) {
a0c453a8edaec90fb0d945c874de0b1845bc7d7eTimo Sirainen /* just shrink the available size */
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen current_block->left -= size - last_alloc_size;
fde0b1793a2842da00eaa105d5e13fec465f0443Timo Sirainen current_frame_block->last_alloc_size[frame_pos] = size;
fda168427e1950518acd6d600f1a10a29a5baef0Timo Sirainenvoid *t_buffer_reget(void *buffer, size_t size)
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainen /* we've already reserved the space, now we just mark it used */
85a4ae7e8df7ea45a7665828e5edf48a5fc85730Timo Sirainen current_block = mem_block_alloc(INITIAL_STACK_SIZE);
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen struct stack_frame_block *frame_block = unused_frame_blocks;
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainen unused_frame_blocks = unused_frame_blocks->prev;
64b61cd24d630223478ccbe1934b9f60f0881f59Timo Sirainenunsigned int t_push(void)
8d587838c414c48a331f0b54cd7ffd97e5024abdTimo Sirainenunsigned int t_pop(void)
539977f9257bd8985be5a8093658da266ae9cd19Timo Sirainenint t_try_realloc(void *mem __attr_unused__, size_t size __attr_unused__)