data-stack.c revision 395a730fac26f68dd1e197a168d07edbcb436730
45312f52ff3a3d4c137447be4c7556500c2f8bf2Timo Sirainen/* Copyright (c) 2002-2014 Dovecot authors, see the included COPYING file */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen/* @UNSAFE: whole file */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen/* Initial stack size - this should be kept in a size that doesn't exceed
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen in a normal use to avoid extra malloc()ing. */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen# define CLEAR_CHR 0xD5 /* D5 is mnemonic for "Data 5tack" */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen# define BLOCK_CANARY ((void *)0xBADBADD5BADBADD5) /* contains 'D5' */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen# define BLOCK_CANARY_CHECK(block) i_assert((block)->canary == BLOCK_CANARY)
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen# define ALLOC_SIZE(size) (MEM_ALIGN(sizeof(size_t)) + MEM_ALIGN(size + SENTRY_COUNT))
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen# define BLOCK_CANARY_CHECK(block) do { ; } while(0)
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* NULL or a poison value, just in case something accesses
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen the memory in front of an allocated area */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* unsigned char data[]; */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define SIZEOF_MEMBLOCK MEM_ALIGN(sizeof(struct stack_block))
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen/* current_frame_block contains last t_push()ed frames. After that new
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen stack_frame_block is created and it's ->prev is set to
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_frame_block. */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* Fairly arbitrary profiling data */
3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen unsigned long long alloc_bytes[BLOCK_FRAME_COUNT];
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenunsigned int data_stack_frame = 0;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic int frame_pos = BLOCK_FRAME_COUNT-1; /* in current_frame_block */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic struct stack_frame_block *current_frame_block;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic struct stack_frame_block *unused_frame_blocks;
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic struct stack_block *current_block; /* block now used for allocation */
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic struct stack_block *unused_block; /* largest unused block is kept here */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic union {
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenunsigned char *data_stack_after_last_alloc(struct stack_block *block)
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return STACK_BLOCK_DATA(block) + (block->size - block->left);
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic void data_stack_last_buffer_reset(bool preserve_data ATTR_UNUSED)
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned char *last_alloc_end, *p;
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen last_alloc_end = data_stack_after_last_alloc(current_block);
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen p = last_alloc_end + MEM_ALIGN(sizeof(size_t)) + MEM_ALIGN(last_buffer_size);
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* reset t_buffer_get() mark - not really needed but makes it
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen easier to notice if t_malloc()/t_push()/t_pop() is called
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen between t_buffer_get() and t_buffer_alloc().
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen do this before we get to i_panic() to avoid recursive
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0; i < SENTRY_COUNT; i++) {
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* frame block full */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* kludgy, but allow this before initialization */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* allocate new block */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen frame_block = calloc(sizeof(*frame_block), 1);
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen frame_block = GC_malloc(sizeof(*frame_block));
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen "t_push(): Out of memory");
7e209b78ca757294dbbc15604c88673b3a6b0c39Timo Sirainen /* use existing unused frame_block */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen unused_frame_blocks = unused_frame_blocks->prev;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* mark our current position */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_frame_block->block[frame_pos] = current_block;
939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen current_frame_block->block_space_used[frame_pos] = current_block->left;
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = 0;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_frame_block->marker[frame_pos] = marker;
939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen current_frame_block->alloc_bytes[frame_pos] = 0ULL;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_frame_block->alloc_count[frame_pos] = 0;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenunsigned int t_push_named(const char *format, ...)
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_frame_block->marker[frame_pos] = p_strdup_vprintf(unsafe_data_stack_pool, format, args);
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen (void)format; /* unused in non-DEBUG builds */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic void free_blocks(struct stack_block *block)
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* free all the blocks, except if any of them is bigger than
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen unused_block, replace it */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen memset(STACK_BLOCK_DATA(block), CLEAR_CHR, block->size);
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (unused_block == NULL || block->size > unused_block->size) {
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic void t_pop_verify(void)
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen unsigned char *p;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen block = current_frame_block->block[frame_pos];
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen pos = block->size - current_frame_block->block_space_used[frame_pos];
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_panic("data stack[%s]: saved alloc size broken",
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen pos += MEM_ALIGN(sizeof(size_t)) + requested_size;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* if we had used t_buffer_get(), the rest of the buffer
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen may not contain CLEAR_CHRs. but we've already checked all
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen the allocations, so there's no need to check them anyway. */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenunsigned int t_pop(void)
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* update the current block */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_block = current_frame_block->block[frame_pos];
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_frame_block->block_space_used[frame_pos];
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen used_size = current_block->size - current_block->lowwater;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen memset(STACK_BLOCK_DATA(current_block) + pos, CLEAR_CHR,
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_block->left = current_frame_block->block_space_used[frame_pos];
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_block->lowwater = current_block->left;
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* free unused blocks */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* frame block is now unused, add it to unused list */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic struct stack_block *mem_block_alloc(size_t min_size)
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen prev_size = current_block == NULL ? 0 : current_block->size;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen alloc_size = nearest_power(prev_size + min_size);
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen block = GC_malloc(SIZEOF_MEMBLOCK + alloc_size);
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_panic("data stack: Out of memory when allocating %"
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen PRIuSIZE_T" bytes", alloc_size + SIZEOF_MEMBLOCK);
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memset(STACK_BLOCK_DATA(block), CLEAR_CHR, alloc_size);
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic void *t_malloc_real(size_t size, bool permanent)
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (unlikely(size == 0 || size > SSIZE_T_MAX))
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_panic("Trying to allocate %"PRIuSIZE_T" bytes", size);
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* kludgy, but allow this before initialization */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* allocate only aligned amount of memory so alignment comes
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen always properly */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_frame_block->alloc_bytes[frame_pos] += alloc_size;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_frame_block->alloc_count[frame_pos]++;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* used for t_try_realloc() */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = alloc_size;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* current block is full, see if we can use the unused_block */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (unused_block != NULL && unused_block->size >= alloc_size) {
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* enough space in current block, use it */
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ret = data_stack_after_last_alloc(current_block);
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (current_block->left - alloc_size < current_block->lowwater)
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_block->lowwater = current_block->left - alloc_size;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* warn after allocation, so if i_warning() wants to
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen allocate more memory we don't go to infinite loop */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_warning("Growing data stack by %"PRIuSIZE_T" as "
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen "'%s' reaches %llu bytes from %u allocations.",
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen ret = PTR_OFFSET(ret, MEM_ALIGN(sizeof(size)));
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* make sure the sentry contains CLEAR_CHRs. it might not if we
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen had used t_buffer_get(). */
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* we rely on errno not changing. it shouldn't. */
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (unlikely(size == 0 || size > SSIZE_T_MAX))
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_panic("Trying to allocate %"PRIuSIZE_T" bytes", size);
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen last_alloc_size = current_frame_block->last_alloc_size[frame_pos];
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* see if we're trying to grow the memory we allocated last */
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen after_last_alloc = data_stack_after_last_alloc(current_block);
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (after_last_alloc - last_alloc_size == mem) {
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* yeah, see if we have space to grow */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (current_block->left >= size - last_alloc_size) {
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* just shrink the available size */
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_block->left -= size - last_alloc_size;
24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = size;
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen const unsigned int extra = MEM_ALIGN_SIZE-1 + SENTRY_COUNT +
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return current_block->left < extra ? current_block->left :
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenvoid *t_buffer_reget(void *buffer, size_t size)
fb7dd075cf883e5e7defbc0c8fb8326e30bdccdeTimo Sirainen /* we've already reserved the space, now we just mark it used */
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenvoid data_stack_set_clean_after_pop(bool enable ATTR_UNUSED)
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* already initialized (we did auto-initialization in
a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen outofmem_area.block.size = outofmem_area.block.left =
dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen sizeof(outofmem_area) - sizeof(outofmem_area.block);
4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen current_block = mem_block_alloc(INITIAL_STACK_SIZE);
e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainen struct stack_frame_block *frame_block = unused_frame_blocks;