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