src/lib/data-stack.c

	data-stack.c revision 10b25ed61cbe92a1435b322a9c2fbda208473018
bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2002-2009 Dovecot authors, see the included COPYING file */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen/* @UNSAFE: whole file */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
bdd36cfdba3ff66d25570a9ff568d69e1eb543cfTimo Sirainen#include "lib.h"
b1f37113a5760bee842c5a7678bb5fa6f5bd8b60Timo Sirainen#include "data-stack.h"
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#include <stdlib.h>
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#ifdef HAVE_GC_GC_H
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#  include <gc/gc.h>
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#elif defined (HAVE_GC_H)
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#  include <gc.h>
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#endif
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi/* Initial stack size - this should be kept in a size that doesn't exceed
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen   in a normal use to avoid extra malloc()ing. */
530b5909a99e7575156496f1b8e4d1ff5b058484Timo Sirainen#ifdef DEBUG
530b5909a99e7575156496f1b8e4d1ff5b058484Timo Sirainen#  define INITIAL_STACK_SIZE (1024*10)
71df09024cea5f2faa93da3bb9513ee96ba6bf22Timo Sirainen#else
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#  define INITIAL_STACK_SIZE (1024*32)
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#endif
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#ifdef DEBUG
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#  define CLEAR_CHR 0xde
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#  define SENTRY_COUNT (4*8)
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#else
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#  define CLEAR_CHR 0
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#endif
efe78d3ba24fc866af1c79b9223dc0809ba26cadStephan Bosch
bd63b5b860658b01b1f46f26d406e1e4a9dc019aTimo Sirainenstruct stack_block {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    struct stack_block *next;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
70ac869db925653b57f721cd045c467612fd5ee9Timo Sirainen    size_t size, left, lowwater;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    /* unsigned char data[]; */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen};
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#define SIZEOF_MEMBLOCK MEM_ALIGN(sizeof(struct stack_block))
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#define STACK_BLOCK_DATA(block) \
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    ((unsigned char *) (block) + SIZEOF_MEMBLOCK)
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen/* current_frame_block contains last t_push()ed frames. After that new
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen   stack_frame_block is created and it's ->prev is set to
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen   current_frame_block. */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#define BLOCK_FRAME_COUNT 32
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstruct stack_frame_block {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    struct stack_frame_block *prev;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    struct stack_block *block[BLOCK_FRAME_COUNT];
2ac5f36aa7c2e7a07ba8815d43a6d7483f62e74cTimo Sirainen        size_t block_space_used[BLOCK_FRAME_COUNT];
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    size_t last_alloc_size[BLOCK_FRAME_COUNT];
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen};
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenunsigned int data_stack_frame = 0;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic int frame_pos = BLOCK_FRAME_COUNT-1; /* in current_frame_block */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic struct stack_frame_block *current_frame_block;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic struct stack_frame_block *unused_frame_blocks;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic struct stack_block *current_block; /* block now used for allocation */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic struct stack_block *unused_block; /* largest unused block is kept here */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic struct stack_block *last_buffer_block;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic size_t last_buffer_size;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic bool clean_after_pop = FALSE;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic bool outofmem = FALSE;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic union {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    struct stack_block block;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    unsigned char data[128];
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen} outofmem_area;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstatic void data_stack_last_buffer_reset(bool preserve_data ATTR_UNUSED)
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen{
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    if (last_buffer_block != NULL) {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#ifdef DEBUG
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        unsigned char *p;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        unsigned int i;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        p = STACK_BLOCK_DATA(current_block) +
b1f37113a5760bee842c5a7678bb5fa6f5bd8b60Timo Sirainen            (current_block->size - current_block->left) +
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen            MEM_ALIGN(sizeof(size_t)) + MEM_ALIGN(last_buffer_size);
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#endif
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        /* reset t_buffer_get() mark - not really needed but makes it
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen           easier to notice if t_malloc()/t_push()/t_pop() is called
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen           between t_buffer_get() and t_buffer_alloc().
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen           do this before we get to i_panic() to avoid recursive
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen           panics. */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        last_buffer_block = NULL;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#ifdef DEBUG
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        for (i = 0; i < SENTRY_COUNT; i++) {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen            if (p[i] != CLEAR_CHR)
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen                i_panic("t_buffer_get(): buffer overflow");
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        }
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        if (!preserve_data) {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen            p = STACK_BLOCK_DATA(current_block) +
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen                (current_block->size - current_block->left);
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            memset(p, CLEAR_CHR, SENTRY_COUNT);
009217abb57a24a4076092e8e4e165545747839eStephan Bosch        }
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen#endif
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen    }
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen}
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainenunsigned int t_push(void)
530b5909a99e7575156496f1b8e4d1ff5b058484Timo Sirainen{
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        struct stack_frame_block *frame_block;
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen    frame_pos++;
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen    if (frame_pos == BLOCK_FRAME_COUNT) {
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        /* frame block full */
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        if (data_stack_frame == 0) {
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            /* kludgy, but allow this before initialization */
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            frame_pos = 0;
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            data_stack_init();
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            return t_push();
530b5909a99e7575156496f1b8e4d1ff5b058484Timo Sirainen        }
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        frame_pos = 0;
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        if (unused_frame_blocks == NULL) {
009217abb57a24a4076092e8e4e165545747839eStephan Bosch            /* allocate new block */
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen#ifndef USE_GC
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            frame_block = calloc(sizeof(*frame_block), 1);
009217abb57a24a4076092e8e4e165545747839eStephan Bosch#else
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            frame_block = GC_malloc(sizeof(*frame_block));
7c925149e49f7cce41c90d562ff3835b66ddca29Timo Sirainen#endif
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            if (frame_block == NULL) {
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen                i_fatal_status(FATAL_OUTOFMEM,
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen                           "t_push(): Out of memory");
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            }
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        } else {
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen            /* use existing unused frame_block */
250a06cde50c4004ac1cc72279b75a229a7f90f5Timo Sirainen            frame_block = unused_frame_blocks;
009217abb57a24a4076092e8e4e165545747839eStephan Bosch            unused_frame_blocks = unused_frame_blocks->prev;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        }
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        frame_block->prev = current_frame_block;
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen        current_frame_block = frame_block;
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen    }
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen    data_stack_last_buffer_reset(FALSE);
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen
6a33ecc05e60b511c1ae176ef113546e1012c18fTimo Sirainen    /* mark our current position */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    current_frame_block->block[frame_pos] = current_block;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen    current_frame_block->block_space_used[frame_pos] = current_block->left;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        current_frame_block->last_alloc_size[frame_pos] = 0;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen        return data_stack_frame++;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen}
250a06cde50c4004ac1cc72279b75a229a7f90f5Timo Sirainen
250a06cde50c4004ac1cc72279b75a229a7f90f5Timo Sirainenstatic void free_blocks(struct stack_block *block)
250a06cde50c4004ac1cc72279b75a229a7f90f5Timo Sirainen{
250a06cde50c4004ac1cc72279b75a229a7f90f5Timo Sirainen    struct stack_block *next;
250a06cde50c4004ac1cc72279b75a229a7f90f5Timo Sirainen
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi    /* free all the blocks, except if any of them is bigger than
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi       unused_block, replace it */
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi    while (block != NULL) {
23bdbb7b1831785c6ba6df190f6369da882d2b9dTimo Sirainen        next = block->next;
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi        if (clean_after_pop)
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi            memset(STACK_BLOCK_DATA(block), CLEAR_CHR, block->size);
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi        if (unused_block == NULL || block->size > unused_block->size) {
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi#ifndef USE_GC
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi            free(unused_block);
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi#endif
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi            unused_block = block;
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi        } else {
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi#ifndef USE_GC
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi            free(block);
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi#endif
a23210844b06c53ebca34b162f3a268d5f1cd4d1Aki Tuomi        }
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        block = next;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    }
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi}
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi#ifdef DEBUG
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomistatic void t_pop_verify(void)
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi{
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    struct stack_block *block;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    unsigned char *p;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    size_t pos, max_pos, used_size, alloc_size;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    block = current_frame_block->block[frame_pos];
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    pos = block->size - current_frame_block->block_space_used[frame_pos];
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    while (block != NULL) {
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        used_size = block->size - block->left;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        p = STACK_BLOCK_DATA(block);
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        while (pos < used_size) {
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            alloc_size = *(size_t *)(p + pos);
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            if (used_size - pos < alloc_size)
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi                i_panic("data stack: saved alloc size broken");
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            pos += MEM_ALIGN(sizeof(alloc_size));
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            max_pos = pos + MEM_ALIGN(alloc_size + SENTRY_COUNT);
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            pos += alloc_size;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            for (; pos < max_pos; pos++) {
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi                if (p[pos] != CLEAR_CHR)
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi                    i_panic("data stack: buffer overflow");
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi            }
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        }
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        /* if we had used t_buffer_get(), the rest of the buffer
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi           may not contain CLEAR_CHRs. but we've already checked all
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi           the allocations, so there's no need to check them anyway. */
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        block = block->next;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        pos = 0;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    }
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi}
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi#endif
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomiunsigned int t_pop(void)
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi{
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    struct stack_frame_block *frame_block;
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi    if (unlikely(frame_pos < 0))
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi        i_panic("t_pop() called with empty stack");
c9dd53f7180a78668cbc1e6eb34d5b1722beccb9Aki Tuomi
    data_stack_last_buffer_reset(FALSE);
#ifdef DEBUG
    t_pop_verify();
#endif

    /* update the current block */
    current_block = current_frame_block->block[frame_pos];
    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;
        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(unsigned int *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;

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

static void *t_malloc_real(size_t size, bool permanent)
{
    struct stack_block *block;
    void *ret;
    size_t alloc_size;
#ifdef DEBUG
    bool warn = FALSE;
#endif

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

    if (unlikely(data_stack_frame == 0)) {
        /* kludgy, but allow this before initialization */
        data_stack_init();
    }

    /* allocate only aligned amount of memory so alignment comes
       always properly */
#ifndef DEBUG
    alloc_size = MEM_ALIGN(size);
#else
    alloc_size = MEM_ALIGN(sizeof(size)) + MEM_ALIGN(size + SENTRY_COUNT);
#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) {
        /* enough space in current block, use it */
        ret = STACK_BLOCK_DATA(current_block) +
            (current_block->size - current_block->left);

        if (current_block->left - alloc_size <
            current_block->lowwater) {
            current_block->lowwater =
                current_block->left - alloc_size;
        }
                if (permanent)
            current_block->left -= alloc_size;
    } else {
        /* 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;
        if (block->left - alloc_size < block->lowwater)
            block->lowwater = block->left - alloc_size;
        if (permanent)
            block->left -= alloc_size;
        block->next = NULL;

        current_block->next = block;
        current_block = block;

        ret = STACK_BLOCK_DATA(current_block);
#ifdef DEBUG
        if (warn) {
            /* warn after allocation, so if i_warning() wants to
               allocate more memory we don't go to infinite loop */
            i_warning("Growing data stack with: %"PRIuSIZE_T,
                  block->size);
        }
#endif
    }
#ifdef DEBUG
    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);
#endif
        return ret;
}

void *t_malloc(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 last_alloc_size;

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

    last_alloc_size = current_frame_block->last_alloc_size[frame_pos];

    /* see if we're trying to grow the memory we allocated last */
    if (STACK_BLOCK_DATA(current_block) +
        (current_block->size - current_block->left -
         last_alloc_size) == mem) {
        /* yeah, see if we have space to grow */
        size = MEM_ALIGN(size);
        if (current_block->left >= size - last_alloc_size) {
            /* just shrink the available size */
            current_block->left -= size - last_alloc_size;
            current_frame_block->last_alloc_size[frame_pos] = size;
            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
    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 */
    t_malloc_real(size, TRUE);
}

void t_buffer_alloc_last_full(void)
{
    if (last_buffer_block != NULL)
        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)
{
#ifdef DEBUG
    clean_after_pop = TRUE;
#endif
    if (data_stack_frame == 0) {
        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;
    }

    t_push();
}

void data_stack_deinit(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;
}