src/lib/data-stack.c

	data-stack.c revision e2588872c1fe79642589b805aaab9fbb6750771b
45312f52ff3a3d4c137447be4c7556500c2f8bf2Timo Sirainen/* Copyright (c) 2002-2016 Dovecot authors, see the included COPYING file */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen/* @UNSAFE: whole file */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#include "lib.h"
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#include "data-stack.h"
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#ifdef HAVE_GC_GC_H
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#  include <gc/gc.h>
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#elif defined (HAVE_GC_H)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#  include <gc.h>
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#endif
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen/* Initial stack size - this should be kept in a size that doesn't exceed
f6c1297c26b355c4aec2a08978f51ec3efecb351Timo Sirainen   in a normal use to avoid extra malloc()ing. */
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen#ifdef DEBUG
f6c1297c26b355c4aec2a08978f51ec3efecb351Timo Sirainen#  define INITIAL_STACK_SIZE (1024*10)
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#else
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define INITIAL_STACK_SIZE (1024*32)
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#endif
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#ifdef DEBUG
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define CLEAR_CHR 0xD5               /* D5 is mnemonic for "Data 5tack" */
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define SENTRY_COUNT (4*8)
ef2b2ef2e6a6eb5e4667f2e63faae8a3b646e8baTimo Sirainen#  define BLOCK_CANARY ((void *)0xBADBADD5BADBADD5)      /* contains 'D5' */
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define BLOCK_CANARY_CHECK(block) i_assert((block)->canary == BLOCK_CANARY)
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define ALLOC_SIZE(size) (MEM_ALIGN(sizeof(size_t)) + MEM_ALIGN(size + SENTRY_COUNT))
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#else
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define CLEAR_CHR 0
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define BLOCK_CANARY NULL
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#  define BLOCK_CANARY_CHECK(block) do { ; } while(0)
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#  define ALLOC_SIZE(size) MEM_ALIGN(size)
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#endif
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainenstruct stack_block {
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    struct stack_block *next;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    size_t size, left, lowwater;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    /* NULL or a poison value, just in case something accesses
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen       the memory in front of an allocated area */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    void *canary;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    /* unsigned char data[]; */
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen};
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#define SIZEOF_MEMBLOCK MEM_ALIGN(sizeof(struct stack_block))
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#define STACK_BLOCK_DATA(block) \
4ea6c43a08b37f270bd54b5809142246fd118263Timo Sirainen    ((unsigned char *) (block) + SIZEOF_MEMBLOCK)
bf9ea5404a0094a8fb8199b677d81f803512c44eTimo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen/* current_frame_block contains last t_push()ed frames. After that new
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen   stack_frame_block is created and it's ->prev is set to
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen   current_frame_block. */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#define BLOCK_FRAME_COUNT 32
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstruct stack_frame_block {
4ea6c43a08b37f270bd54b5809142246fd118263Timo Sirainen    struct stack_frame_block *prev;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
bf9ea5404a0094a8fb8199b677d81f803512c44eTimo Sirainen    struct stack_block *block[BLOCK_FRAME_COUNT];
bf9ea5404a0094a8fb8199b677d81f803512c44eTimo Sirainen    size_t block_space_used[BLOCK_FRAME_COUNT];
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    size_t last_alloc_size[BLOCK_FRAME_COUNT];
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#ifdef DEBUG
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    const char *marker[BLOCK_FRAME_COUNT];
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    /* Fairly arbitrary profiling data */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    unsigned long long alloc_bytes[BLOCK_FRAME_COUNT];
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    unsigned int alloc_count[BLOCK_FRAME_COUNT];
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen#endif
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen};
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
0df9428baed48afaff90b4d4f03792d2fd756a43Timo Sirainendata_stack_frame_t data_stack_frame = 0;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainenstatic bool data_stack_initialized = FALSE;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic int frame_pos = BLOCK_FRAME_COUNT-1; /* in current_frame_block */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic struct stack_frame_block *current_frame_block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic struct stack_frame_block *unused_frame_blocks;
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic struct stack_block *current_block; /* block now used for allocation */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic struct stack_block *unused_block; /* largest unused block is kept here */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic struct stack_block *last_buffer_block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic size_t last_buffer_size;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#ifdef DEBUG
2769eecf814bd243033dcbf5bdc38f4162d3202dTimo Sirainenstatic bool clean_after_pop = TRUE;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#else
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic bool clean_after_pop = FALSE;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#endif
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic bool outofmem = FALSE;
63110c906fdb5b4e8c870e76fa3f244dac4b043dTimo Sirainen
63110c906fdb5b4e8c870e76fa3f244dac4b043dTimo Sirainenstatic union {
63110c906fdb5b4e8c870e76fa3f244dac4b043dTimo Sirainen    struct stack_block block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    unsigned char data[512];
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen} outofmem_area;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic inline
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenunsigned char *data_stack_after_last_alloc(struct stack_block *block)
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen{
ef2b2ef2e6a6eb5e4667f2e63faae8a3b646e8baTimo Sirainen    return STACK_BLOCK_DATA(block) + (block->size - block->left);
e17d463c0d18233d1184f5b9237ff3f514f031ceTimo Sirainen}
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic void data_stack_last_buffer_reset(bool preserve_data ATTR_UNUSED)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen{
ef2b2ef2e6a6eb5e4667f2e63faae8a3b646e8baTimo Sirainen    if (last_buffer_block != NULL) {
ef2b2ef2e6a6eb5e4667f2e63faae8a3b646e8baTimo Sirainen#ifdef DEBUG
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen        unsigned char *last_alloc_end, *p, *pend;
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen        last_alloc_end = data_stack_after_last_alloc(current_block);
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen        p = last_alloc_end + MEM_ALIGN(sizeof(size_t)) + last_buffer_size;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        pend = last_alloc_end + ALLOC_SIZE(last_buffer_size);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#endif
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        /* reset t_buffer_get() mark - not really needed but makes it
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen           easier to notice if t_malloc()/t_push()/t_pop() is called
2769eecf814bd243033dcbf5bdc38f4162d3202dTimo Sirainen           between t_buffer_get() and t_buffer_alloc().
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen           do this before we get to i_panic() to avoid recursive
d23c747de9d33966483fbdd41f08ad7766da7c5cTimo Sirainen           panics. */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        last_buffer_block = NULL;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#ifdef DEBUG
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen        while (p < pend)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            if (*p++ != CLEAR_CHR)
bd7b1a9000b12349e2a99bb43b3ce8b96a18e92bTimo Sirainen                i_panic("t_buffer_get(): buffer overflow");
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        if (!preserve_data) {
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            p = last_alloc_end;
d23c747de9d33966483fbdd41f08ad7766da7c5cTimo Sirainen            memset(p, CLEAR_CHR, SENTRY_COUNT);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        }
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#endif
bd7b1a9000b12349e2a99bb43b3ce8b96a18e92bTimo Sirainen    }
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen}
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainendata_stack_frame_t t_push(const char *marker)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen{
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    struct stack_frame_block *frame_block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen    frame_pos++;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    if (frame_pos == BLOCK_FRAME_COUNT) {
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen        /* frame block full */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        if (unlikely(!data_stack_initialized)) {
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen            /* kludgy, but allow this before initialization */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            frame_pos = 0;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            data_stack_init();
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            return t_push(marker);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        }
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
d23c747de9d33966483fbdd41f08ad7766da7c5cTimo Sirainen        frame_pos = 0;
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen        if (unused_frame_blocks == NULL) {
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen            /* allocate new block */
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#ifndef USE_GC
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen            frame_block = calloc(sizeof(*frame_block), 1);
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#else
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen            frame_block = GC_malloc(sizeof(*frame_block));
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen#endif
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen            if (frame_block == NULL) {
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen                i_fatal_status(FATAL_OUTOFMEM,
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen                           "t_push(): Out of memory");
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen            }
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        } else {
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            /* use existing unused frame_block */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            frame_block = unused_frame_blocks;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            unused_frame_blocks = unused_frame_blocks->prev;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        }
a443e5aaf632257bfd1e7aa9b3c42c09512bbe43Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        frame_block->prev = current_frame_block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        current_frame_block = frame_block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    }
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    data_stack_last_buffer_reset(FALSE);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    /* mark our current position */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    current_frame_block->block[frame_pos] = current_block;
f1e9611e93dcb3b745c1904029084fa81644e1b3Timo Sirainen    current_frame_block->block_space_used[frame_pos] = current_block->left;
bf9ea5404a0094a8fb8199b677d81f803512c44eTimo Sirainen    current_frame_block->last_alloc_size[frame_pos] = 0;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#ifdef DEBUG
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    current_frame_block->marker[frame_pos] = marker;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    current_frame_block->alloc_bytes[frame_pos] = 0ULL;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    current_frame_block->alloc_count[frame_pos] = 0;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#else
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    (void)marker; /* only used for debugging */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#endif
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    return data_stack_frame++;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen}
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainendata_stack_frame_t t_push_named(const char *format, ...)
d23c747de9d33966483fbdd41f08ad7766da7c5cTimo Sirainen{
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    data_stack_frame_t ret = t_push(NULL);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#ifdef DEBUG
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    va_list args;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    va_start(args, format);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    current_frame_block->marker[frame_pos] = p_strdup_vprintf(unsafe_data_stack_pool, format, args);
7c7a364a72d4edd1701df72fee835c09db19d933Timo Sirainen    va_end(args);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#else
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    (void)format; /* unused in non-DEBUG builds */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#endif
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    return ret;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen}
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainenstatic void free_blocks(struct stack_block *block)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen{
bf9ea5404a0094a8fb8199b677d81f803512c44eTimo Sirainen    struct stack_block *next;
bf9ea5404a0094a8fb8199b677d81f803512c44eTimo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    /* free all the blocks, except if any of them is bigger than
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen       unused_block, replace it */
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    while (block != NULL) {
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        BLOCK_CANARY_CHECK(block);
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        next = block->next;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen        if (clean_after_pop)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen            memset(STACK_BLOCK_DATA(block), CLEAR_CHR, block->size);
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen        if (unused_block == NULL || block->size > unused_block->size) {
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen#ifndef USE_GC
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen            free(unused_block);
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen#endif
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen            unused_block = block;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen        } else {
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen#ifndef USE_GC
f8da06de93e28b5d3e039a427cdde7e1e15daec8Timo Sirainen            if (block != &outofmem_area.block)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen                free(block);
66a872b4569c048e804f0731680d89c6042d8890Timo Sirainen#endif
66a872b4569c048e804f0731680d89c6042d8890Timo Sirainen        }
66a872b4569c048e804f0731680d89c6042d8890Timo Sirainen
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen        block = next;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen    }
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen}
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen#ifdef DEBUG
f8da06de93e28b5d3e039a427cdde7e1e15daec8Timo Sirainenstatic void t_pop_verify(void)
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen{
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    struct stack_block *block;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    unsigned char *p;
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    size_t pos, max_pos, used_size;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen    block = current_frame_block->block[frame_pos];
1795e934ebcd58175d3b5bbdd811b13c7889efa3Timo Sirainen    pos = block->size - current_frame_block->block_space_used[frame_pos];
    while (block != NULL) {
        BLOCK_CANARY_CHECK(block);
        used_size = block->size - block->left;
        p = STACK_BLOCK_DATA(block);
        while (pos < used_size) {
            size_t requested_size = *(size_t *)(p + pos);
            if (used_size - pos < requested_size)
                i_panic("data stack[%s]: saved alloc size broken",
                    current_frame_block->marker[frame_pos]);
            max_pos = pos + ALLOC_SIZE(requested_size);
            pos += MEM_ALIGN(sizeof(size_t)) + requested_size;

            for (; pos < max_pos; pos++) {
                if (p[pos] != CLEAR_CHR)
                    i_panic("data stack[%s]: buffer overflow",
                        current_frame_block->marker[frame_pos]);
            }
        }

        /* if we had used t_buffer_get(), the rest of the buffer
           may not contain CLEAR_CHRs. but we've already checked all
           the allocations, so there's no need to check them anyway. */
        block = block->next;
        pos = 0;
    }
}
#endif

data_stack_frame_t t_pop(void)
{
    struct stack_frame_block *frame_block;

    if (unlikely(frame_pos < 0))
        i_panic("t_pop() called with empty stack");

    data_stack_last_buffer_reset(FALSE);
#ifdef DEBUG
    t_pop_verify();
#endif

    /* update the current block */
    current_block = current_frame_block->block[frame_pos];
    BLOCK_CANARY_CHECK(current_block);
    if (clean_after_pop) {
        size_t pos, used_size;

        pos = current_block->size -
            current_frame_block->block_space_used[frame_pos];
        used_size = current_block->size - current_block->lowwater;
        i_assert(used_size >= pos);
        memset(STACK_BLOCK_DATA(current_block) + pos, CLEAR_CHR,
               used_size - pos);
    }
    current_block->left = current_frame_block->block_space_used[frame_pos];
    current_block->lowwater = current_block->left;

    if (current_block->next != NULL) {
        /* free unused blocks */
        free_blocks(current_block->next);
        current_block->next = NULL;
    }

    if (frame_pos > 0)
        frame_pos--;
    else {
        /* frame block is now unused, add it to unused list */
        frame_pos = BLOCK_FRAME_COUNT-1;

        frame_block = current_frame_block;
        current_frame_block = frame_block->prev;

        frame_block->prev = unused_frame_blocks;
        unused_frame_blocks = frame_block;
    }

    return --data_stack_frame;
}

void t_pop_check(data_stack_frame_t *id)
{
    if (unlikely(t_pop() != *id))
        i_panic("Leaked t_pop() call");
    *id = 0;
}

static struct stack_block *mem_block_alloc(size_t min_size)
{
    struct stack_block *block;
    size_t prev_size, alloc_size;

    prev_size = current_block == NULL ? 0 : current_block->size;
    alloc_size = nearest_power(prev_size + min_size);

#ifndef USE_GC
    block = malloc(SIZEOF_MEMBLOCK + alloc_size);
#else
    block = GC_malloc(SIZEOF_MEMBLOCK + alloc_size);
#endif
    if (unlikely(block == NULL)) {
        if (outofmem) {
            if (min_size > outofmem_area.block.left)
                abort();
            return &outofmem_area.block;
        }
        outofmem = TRUE;
        i_panic("data stack: Out of memory when allocating %"
            PRIuSIZE_T" bytes", alloc_size + SIZEOF_MEMBLOCK);
    }
    block->size = alloc_size;
    block->left = 0;
    block->lowwater = block->size;
    block->next = NULL;
    block->canary = BLOCK_CANARY;

#ifdef DEBUG
    memset(STACK_BLOCK_DATA(block), CLEAR_CHR, alloc_size);
#endif
    return block;
}

static void *t_malloc_real(size_t size, bool permanent)
{
    void *ret;
    size_t alloc_size;
#ifdef DEBUG
    bool warn = FALSE;
    int old_errno = errno;
#endif

    if (unlikely(size == 0 || size > SSIZE_T_MAX))
        i_panic("Trying to allocate %"PRIuSIZE_T" bytes", size);

    if (unlikely(!data_stack_initialized)) {
        /* kludgy, but allow this before initialization */
        data_stack_init();
    }
    BLOCK_CANARY_CHECK(current_block);

    /* allocate only aligned amount of memory so alignment comes
       always properly */
    alloc_size = ALLOC_SIZE(size);
#ifdef DEBUG
    if(permanent) {
        current_frame_block->alloc_bytes[frame_pos] += alloc_size;
        current_frame_block->alloc_count[frame_pos]++;
    }
#endif
    data_stack_last_buffer_reset(TRUE);

    /* used for t_try_realloc() */
    current_frame_block->last_alloc_size[frame_pos] = alloc_size;

    if (current_block->left < alloc_size) {
        struct stack_block *block;

        /* current block is full, see if we can use the unused_block */
        if (unused_block != NULL && unused_block->size >= alloc_size) {
            block = unused_block;
            unused_block = NULL;
        } else {
            block = mem_block_alloc(alloc_size);
#ifdef DEBUG
            warn = TRUE;
#endif
        }

        block->left = block->size;
        block->next = NULL;
        current_block->next = block;
        current_block = block;
    }

    /* enough space in current block, use it */
    ret = data_stack_after_last_alloc(current_block);

    if (current_block->left - alloc_size < current_block->lowwater)
        current_block->lowwater = current_block->left - alloc_size;
    if (permanent)
        current_block->left -= alloc_size;

#ifdef DEBUG
    if (warn && getenv("DEBUG_SILENT") == NULL) {
        /* warn after allocation, so if i_debug() wants to
           allocate more memory we don't go to infinite loop */
        i_debug("Growing data stack by %"PRIuSIZE_T" as "
              "'%s' reaches %llu bytes from %u allocations.",
              current_block->size,
              current_frame_block->marker[frame_pos],
              current_frame_block->alloc_bytes[frame_pos],
              current_frame_block->alloc_count[frame_pos]);
    }
    memcpy(ret, &size, sizeof(size));
    ret = PTR_OFFSET(ret, MEM_ALIGN(sizeof(size)));
    /* make sure the sentry contains CLEAR_CHRs. it might not if we
       had used t_buffer_get(). */
    memset(PTR_OFFSET(ret, size), CLEAR_CHR,
           MEM_ALIGN(size + SENTRY_COUNT) - size);

    /* we rely on errno not changing. it shouldn't. */
    i_assert(errno == old_errno);
#endif
    return ret;
}

void *t_malloc_no0(size_t size)
{
    return t_malloc_real(size, TRUE);
}

void *t_malloc0(size_t size)
{
    void *mem;

    mem = t_malloc_real(size, TRUE);
    memset(mem, 0, size);
    return mem;
}

bool t_try_realloc(void *mem, size_t size)
{
    size_t debug_adjust = 0, last_alloc_size;
    unsigned char *after_last_alloc;

    if (unlikely(size == 0 || size > SSIZE_T_MAX))
        i_panic("Trying to allocate %"PRIuSIZE_T" bytes", size);
    BLOCK_CANARY_CHECK(current_block);

    last_alloc_size = current_frame_block->last_alloc_size[frame_pos];

    /* see if we're trying to grow the memory we allocated last */
    after_last_alloc = data_stack_after_last_alloc(current_block);
#ifdef DEBUG
    debug_adjust = MEM_ALIGN(sizeof(size_t));
#endif
    if (after_last_alloc - last_alloc_size + debug_adjust == mem) {
        /* yeah, see if we have space to grow */
        size_t new_alloc_size, alloc_growth;

        new_alloc_size = ALLOC_SIZE(size);
        alloc_growth = (new_alloc_size - last_alloc_size);
#ifdef DEBUG
        size_t old_raw_size; /* sorry, non-C99 users - add braces if you need them */
        old_raw_size = *(size_t *)PTR_OFFSET(mem, -(ptrdiff_t)MEM_ALIGN(sizeof(size_t)));
        i_assert(ALLOC_SIZE(old_raw_size) == last_alloc_size);
        /* Only check one byte for over-run, that catches most
           offenders who are likely to use t_try_realloc() */
        i_assert(((unsigned char*)mem)[old_raw_size] == CLEAR_CHR);
#endif

        if (current_block->left >= alloc_growth) {
            /* just shrink the available size */
            current_block->left -= alloc_growth;
            if (current_block->left < current_block->lowwater)
                current_block->lowwater = current_block->left;
            current_frame_block->last_alloc_size[frame_pos] =
                new_alloc_size;
#ifdef DEBUG
            /* All reallocs are permanent by definition
               However, they don't count as a new allocation */
            current_frame_block->alloc_bytes[frame_pos] += alloc_growth;
            *(size_t *)PTR_OFFSET(mem, -(ptrdiff_t)MEM_ALIGN(sizeof(size_t))) = size;
            memset(PTR_OFFSET(mem, size), CLEAR_CHR,
                   new_alloc_size - size - MEM_ALIGN(sizeof(size_t)));
#endif
            return TRUE;
        }
    }

    return FALSE;
}

size_t t_get_bytes_available(void)
{
#ifndef DEBUG
    const unsigned int extra = MEM_ALIGN_SIZE-1;
#else
    const unsigned int extra = MEM_ALIGN_SIZE-1 + SENTRY_COUNT +
        MEM_ALIGN(sizeof(size_t));
#endif
    BLOCK_CANARY_CHECK(current_block);
    return current_block->left < extra ? current_block->left :
        current_block->left - extra;
}

void *t_buffer_get(size_t size)
{
    void *ret;

    ret = t_malloc_real(size, FALSE);

    last_buffer_size = size;
    last_buffer_block = current_block;
    return ret;
}

void *t_buffer_reget(void *buffer, size_t size)
{
    size_t old_size;
    void *new_buffer;

    old_size = last_buffer_size;
    if (size <= old_size)
        return buffer;

    new_buffer = t_buffer_get(size);
    if (new_buffer != buffer)
        memcpy(new_buffer, buffer, old_size);

    return new_buffer;
}

void t_buffer_alloc(size_t size)
{
    i_assert(last_buffer_block != NULL);
    i_assert(last_buffer_size >= size);
    i_assert(current_block->left >= size);

    /* we've already reserved the space, now we just mark it used */
    (void)t_malloc_real(size, TRUE);
}

void t_buffer_alloc_last_full(void)
{
    if (last_buffer_block != NULL)
        (void)t_malloc_real(last_buffer_size, TRUE);
}

void data_stack_set_clean_after_pop(bool enable ATTR_UNUSED)
{
#ifndef DEBUG
    clean_after_pop = enable;
#endif
}

void data_stack_init(void)
{
    if (data_stack_initialized) {
        /* already initialized (we did auto-initialization in
           t_malloc/t_push) */
        return;
    }
    data_stack_initialized = TRUE;
    data_stack_frame = 1;

    outofmem_area.block.size = outofmem_area.block.left =
        sizeof(outofmem_area) - sizeof(outofmem_area.block);

    current_block = mem_block_alloc(INITIAL_STACK_SIZE);
    current_block->left = current_block->size;
    current_block->next = NULL;

    current_frame_block = NULL;
    unused_frame_blocks = NULL;
    frame_pos = BLOCK_FRAME_COUNT-1;

    last_buffer_block = NULL;
    last_buffer_size = 0;

    (void)t_push("data_stack_init");
}

void data_stack_deinit(void)
{
    (void)t_pop();

    if (frame_pos != BLOCK_FRAME_COUNT-1)
        i_panic("Missing t_pop() call");

#ifndef USE_GC
    while (unused_frame_blocks != NULL) {
        struct stack_frame_block *frame_block = unused_frame_blocks;
        unused_frame_blocks = unused_frame_blocks->prev;

        free(frame_block);
    }

    free(current_block);
    free(unused_block);
#endif
    unused_frame_blocks = NULL;
    current_block = NULL;
    unused_block = NULL;
}