diff options
Diffstat (limited to 'src/ncbuf.c')
| -rw-r--r-- | src/ncbuf.c | 984 |
1 files changed, 984 insertions, 0 deletions
diff --git a/src/ncbuf.c b/src/ncbuf.c new file mode 100644 index 0000000..a96cf59 --- /dev/null +++ b/src/ncbuf.c @@ -0,0 +1,984 @@ +#include <haproxy/ncbuf.h> + +#include <string.h> + +#ifndef MIN +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) +#endif + +#ifdef STANDALONE +#include <stdarg.h> +#include <stdlib.h> +#include <stdio.h> +#include <unistd.h> + +#include <haproxy/list.h> +#endif /* STANDALONE */ + +#ifdef DEBUG_STRICT +# include <haproxy/bug.h> +#else +# include <stdio.h> +# include <stdlib.h> + +# undef BUG_ON +# define BUG_ON(x) if (x) { fprintf(stderr, "CRASH ON %s:%d\n", __func__, __LINE__); abort(); } + +# undef BUG_ON_HOT +# define BUG_ON_HOT(x) if (x) { fprintf(stderr, "CRASH ON %s:%d\n", __func__, __LINE__); abort(); } +#endif /* DEBUG_DEV */ + +#include <haproxy/compiler.h> + +/* ******** internal API ******** */ + +#define NCB_BLK_NULL ((struct ncb_blk){ .st = NULL }) + +#define NCB_BK_F_GAP 0x01 /* block represents a gap */ +#define NCB_BK_F_FIN 0x02 /* special reduced gap present at the end of the buffer */ +struct ncb_blk { + char *st; /* first byte of the block */ + char *end; /* first byte after this block */ + + char *sz_ptr; /* pointer to size element - NULL for reduced gap */ + ncb_sz_t sz; /* size of the block */ + ncb_sz_t sz_data; /* size of the data following the block - invalid for reduced GAP */ + ncb_sz_t off; /* offset of block in buffer */ + + char flag; +}; + +/* Return pointer to <off> relative to <buf> head. Support buffer wrapping. */ +static char *ncb_peek(const struct ncbuf *buf, ncb_sz_t off) +{ + char *ptr = ncb_head(buf) + off; + if (ptr >= buf->area + buf->size) + ptr -= buf->size; + return ptr; +} + +/* Returns the reserved space of <buf> which contains the size of the first + * data block. + */ +static char *ncb_reserved(const struct ncbuf *buf) +{ + return ncb_peek(buf, buf->size - NCB_RESERVED_SZ); +} + +/* Encode <off> at <st> position in <buf>. Support wrapping. */ +static forceinline void ncb_write_off(const struct ncbuf *buf, char *st, ncb_sz_t off) +{ + int i; + + BUG_ON_HOT(st >= buf->area + buf->size); + + for (i = 0; i < sizeof(ncb_sz_t); ++i) { + (*st) = off >> (8 * i) & 0xff; + + if ((++st) == ncb_wrap(buf)) + st = ncb_orig(buf); + } +} + +/* Decode offset stored at <st> position in <buf>. Support wrapping. */ +static forceinline ncb_sz_t ncb_read_off(const struct ncbuf *buf, char *st) +{ + int i; + ncb_sz_t off = 0; + + BUG_ON_HOT(st >= buf->area + buf->size); + + for (i = 0; i < sizeof(ncb_sz_t); ++i) { + off |= (unsigned char )(*st) << (8 * i); + + if ((++st) == ncb_wrap(buf)) + st = ncb_orig(buf); + } + + return off; +} + +/* Add <off> to the offset stored at <st> in <buf>. Support wrapping. */ +static forceinline void ncb_inc_off(const struct ncbuf *buf, char *st, ncb_sz_t off) +{ + const ncb_sz_t old = ncb_read_off(buf, st); + ncb_write_off(buf, st, old + off); +} + +/* Returns true if a gap cannot be inserted at <off> : a reduced gap must be used. */ +static forceinline int ncb_off_reduced(const struct ncbuf *b, ncb_sz_t off) +{ + return off + NCB_GAP_MIN_SZ > ncb_size(b); +} + +/* Returns true if <blk> is the special NULL block. */ +static forceinline int ncb_blk_is_null(const struct ncb_blk *blk) +{ + return !blk->st; +} + +/* Returns true if <blk> is the last block of <buf>. */ +static forceinline int ncb_blk_is_last(const struct ncbuf *buf, const struct ncb_blk *blk) +{ + BUG_ON_HOT(blk->off + blk->sz > ncb_size(buf)); + return blk->off + blk->sz == ncb_size(buf); +} + +/* Returns the first block of <buf> which is always a DATA. */ +static struct ncb_blk ncb_blk_first(const struct ncbuf *buf) +{ + struct ncb_blk blk; + + if (ncb_is_null(buf)) + return NCB_BLK_NULL; + + blk.st = ncb_head(buf); + + blk.sz_ptr = ncb_reserved(buf); + blk.sz = ncb_read_off(buf, ncb_reserved(buf)); + blk.sz_data = 0; + BUG_ON_HOT(blk.sz > ncb_size(buf)); + + blk.end = ncb_peek(buf, blk.sz); + blk.off = 0; + blk.flag = 0; + + return blk; +} + +/* Returns the block following <prev> in the buffer <buf>. */ +static struct ncb_blk ncb_blk_next(const struct ncbuf *buf, + const struct ncb_blk *prev) +{ + struct ncb_blk blk; + + BUG_ON_HOT(ncb_blk_is_null(prev)); + + if (ncb_blk_is_last(buf, prev)) + return NCB_BLK_NULL; + + blk.st = prev->end; + blk.off = prev->off + prev->sz; + blk.flag = ~prev->flag & NCB_BK_F_GAP; + + if (blk.flag & NCB_BK_F_GAP) { + if (ncb_off_reduced(buf, blk.off)) { + blk.flag |= NCB_BK_F_FIN; + blk.sz_ptr = NULL; + blk.sz = ncb_size(buf) - blk.off; + blk.sz_data = 0; + + /* A reduced gap can only be the last block. */ + BUG_ON_HOT(!ncb_blk_is_last(buf, &blk)); + } + else { + blk.sz_ptr = ncb_peek(buf, blk.off + NCB_GAP_SZ_OFF); + blk.sz = ncb_read_off(buf, blk.sz_ptr); + blk.sz_data = ncb_read_off(buf, ncb_peek(buf, blk.off + NCB_GAP_SZ_DATA_OFF)); + BUG_ON_HOT(blk.sz < NCB_GAP_MIN_SZ); + } + } + else { + blk.sz_ptr = ncb_peek(buf, prev->off + NCB_GAP_SZ_DATA_OFF); + blk.sz = prev->sz_data; + blk.sz_data = 0; + + /* only first DATA block can be empty. If this happens, a GAP + * merge should have been realized. + */ + BUG_ON_HOT(!blk.sz); + } + + BUG_ON_HOT(blk.off + blk.sz > ncb_size(buf)); + blk.end = ncb_peek(buf, blk.off + blk.sz); + + return blk; +} + +/* Returns the block containing offset <off>. Note that if <off> is at the + * frontier between two blocks, this function will return the preceding one. + * This is done to easily merge blocks on insertion/deletion. + */ +static struct ncb_blk ncb_blk_find(const struct ncbuf *buf, ncb_sz_t off) +{ + struct ncb_blk blk; + + if (ncb_is_null(buf)) + return NCB_BLK_NULL; + + BUG_ON_HOT(off >= ncb_size(buf)); + + for (blk = ncb_blk_first(buf); off > blk.off + blk.sz; + blk = ncb_blk_next(buf, &blk)) { + } + + return blk; +} + +/* Transform absolute offset <off> to a relative one from <blk> start. */ +static forceinline ncb_sz_t ncb_blk_off(const struct ncb_blk *blk, ncb_sz_t off) +{ + BUG_ON_HOT(off < blk->off || off > blk->off + blk->sz); + BUG_ON_HOT(off - blk->off > blk->sz); + return off - blk->off; +} + +/* Simulate insertion in <buf> of <data> of length <len> at offset <off>. This + * ensures that minimal block size are respected for newly formed gaps. <blk> + * must be the block where the insert operation begins. If <mode> is + * NCB_ADD_COMPARE, old and new overlapped data are compared to validate the + * insertion. + * + * Returns NCB_RET_OK if insertion can proceed. + */ +static enum ncb_ret ncb_check_insert(const struct ncbuf *buf, + const struct ncb_blk *blk, ncb_sz_t off, + const char *data, ncb_sz_t len, + enum ncb_add_mode mode) +{ + struct ncb_blk next; + ncb_sz_t off_blk = ncb_blk_off(blk, off); + ncb_sz_t to_copy; + ncb_sz_t left = len; + + /* If insertion starts in a gap, it must leave enough space to keep the + * gap header. + */ + if (left && (blk->flag & NCB_BK_F_GAP)) { + if (off_blk < NCB_GAP_MIN_SZ) + return NCB_RET_GAP_SIZE; + } + + next = *blk; + while (left) { + off_blk = ncb_blk_off(&next, off); + to_copy = MIN(left, next.sz - off_blk); + + if (next.flag & NCB_BK_F_GAP && off_blk + to_copy < next.sz) { + /* Insertion must leave enough space for a new gap + * header if stopped in a middle of a gap. + */ + const ncb_sz_t gap_sz = next.sz - (off_blk + to_copy); + if (gap_sz < NCB_GAP_MIN_SZ && !ncb_blk_is_last(buf, &next)) + return NCB_RET_GAP_SIZE; + } + else if (!(next.flag & NCB_BK_F_GAP) && mode == NCB_ADD_COMPARE) { + /* Compare memory of data block in NCB_ADD_COMPARE mode. */ + const ncb_sz_t off_blk = ncb_blk_off(&next, off); + char *st = ncb_peek(buf, off); + + to_copy = MIN(left, next.sz - off_blk); + if (st + to_copy > ncb_wrap(buf)) { + const ncb_sz_t sz1 = ncb_wrap(buf) - st; + if (memcmp(st, data, sz1)) + return NCB_RET_DATA_REJ; + if (memcmp(ncb_orig(buf), data + sz1, to_copy - sz1)) + return NCB_RET_DATA_REJ; + } + else { + if (memcmp(st, data, to_copy)) + return NCB_RET_DATA_REJ; + } + } + + left -= to_copy; + data += to_copy; + off += to_copy; + + next = ncb_blk_next(buf, &next); + } + + return NCB_RET_OK; +} + +/* Fill new <data> of length <len> inside an already existing data <blk> at + * offset <off>. Offset is relative to <blk> so it cannot be greater than the + * block size. <mode> specifies if old data are preserved or overwritten. + */ +static ncb_sz_t ncb_fill_data_blk(const struct ncbuf *buf, + const struct ncb_blk *blk, ncb_sz_t off, + const char *data, ncb_sz_t len, + enum ncb_add_mode mode) +{ + const ncb_sz_t to_copy = MIN(len, blk->sz - off); + char *ptr = NULL; + + BUG_ON_HOT(off > blk->sz); + /* This can happens due to previous ncb_blk_find() usage. In this + * case the current fill is a noop. + */ + if (off == blk->sz) + return 0; + + if (mode == NCB_ADD_OVERWRT) { + ptr = ncb_peek(buf, blk->off + off); + + if (ptr + to_copy >= ncb_wrap(buf)) { + const ncb_sz_t sz1 = ncb_wrap(buf) - ptr; + memcpy(ptr, data, sz1); + memcpy(ncb_orig(buf), data + sz1, to_copy - sz1); + } + else { + memcpy(ptr, data, to_copy); + } + } + + return to_copy; +} + +/* Fill the gap <blk> starting at <off> with new <data> of length <len>. <off> + * is relative to <blk> so it cannot be greater than the block size. + */ +static ncb_sz_t ncb_fill_gap_blk(const struct ncbuf *buf, + const struct ncb_blk *blk, ncb_sz_t off, + const char *data, ncb_sz_t len) +{ + const ncb_sz_t to_copy = MIN(len, blk->sz - off); + char *ptr; + + BUG_ON_HOT(off > blk->sz); + /* This can happens due to previous ncb_blk_find() usage. In this + * case the current fill is a noop. + */ + if (off == blk->sz) + return 0; + + /* A new gap must be created if insertion stopped before gap end. */ + if (off + to_copy < blk->sz) { + const ncb_sz_t gap_off = blk->off + off + to_copy; + const ncb_sz_t gap_sz = blk->sz - off - to_copy; + + BUG_ON_HOT(!ncb_off_reduced(buf, gap_off) && + blk->off + blk->sz - gap_off < NCB_GAP_MIN_SZ); + + /* write the new gap header unless this is a reduced gap. */ + if (!ncb_off_reduced(buf, gap_off)) { + char *gap_ptr = ncb_peek(buf, gap_off + NCB_GAP_SZ_OFF); + char *gap_data_ptr = ncb_peek(buf, gap_off + NCB_GAP_SZ_DATA_OFF); + + ncb_write_off(buf, gap_ptr, gap_sz); + ncb_write_off(buf, gap_data_ptr, blk->sz_data); + } + } + + /* fill the gap with new data */ + ptr = ncb_peek(buf, blk->off + off); + if (ptr + to_copy >= ncb_wrap(buf)) { + ncb_sz_t sz1 = ncb_wrap(buf) - ptr; + memcpy(ptr, data, sz1); + memcpy(ncb_orig(buf), data + sz1, to_copy - sz1); + } + else { + memcpy(ptr, data, to_copy); + } + + return to_copy; +} + +/* ******** public API ******** */ + +/* Initialize or reset <buf> by clearing all data. Its size is untouched. + * Buffer is positioned to <head> offset. Use 0 to realign it. <buf> must not + * be NCBUF_NULL. + */ +void ncb_init(struct ncbuf *buf, ncb_sz_t head) +{ + BUG_ON_HOT(ncb_is_null(buf)); + + BUG_ON_HOT(head >= buf->size); + buf->head = head; + + ncb_write_off(buf, ncb_reserved(buf), 0); + ncb_write_off(buf, ncb_head(buf), ncb_size(buf)); + ncb_write_off(buf, ncb_peek(buf, sizeof(ncb_sz_t)), 0); +} + +/* Construct a ncbuf with all its parameters. */ +struct ncbuf ncb_make(char *area, ncb_sz_t size, ncb_sz_t head) +{ + struct ncbuf buf; + + /* Ensure that there is enough space for the reserved space and data. + * This is the minimal value to not crash later. + */ + BUG_ON_HOT(size <= NCB_RESERVED_SZ); + + buf.area = area; + buf.size = size; + buf.head = head; + + return buf; +} + +/* Returns the total number of bytes stored in whole <buf>. */ +ncb_sz_t ncb_total_data(const struct ncbuf *buf) +{ + struct ncb_blk blk; + int total = 0; + + for (blk = ncb_blk_first(buf); !ncb_blk_is_null(&blk); blk = ncb_blk_next(buf, &blk)) { + if (!(blk.flag & NCB_BK_F_GAP)) + total += blk.sz; + } + + return total; +} + +/* Returns true if there is no data anywhere in <buf>. */ +int ncb_is_empty(const struct ncbuf *buf) +{ + int first_data, first_gap; + + if (ncb_is_null(buf)) + return 1; + + first_data = ncb_read_off(buf, ncb_reserved(buf)); + BUG_ON_HOT(first_data > ncb_size(buf)); + /* Buffer is not empty if first data block is not nul. */ + if (first_data) + return 0; + + /* Head contains the first gap size if first data block is empty. */ + first_gap = ncb_read_off(buf, ncb_head(buf)); + BUG_ON_HOT(first_gap > ncb_size(buf)); + return first_gap == ncb_size(buf); +} + +/* Returns true if no more data can be inserted in <buf>. */ +int ncb_is_full(const struct ncbuf *buf) +{ + int first_data; + + if (ncb_is_null(buf)) + return 0; + + /* First data block must cover whole buffer if full. */ + first_data = ncb_read_off(buf, ncb_reserved(buf)); + BUG_ON_HOT(first_data > ncb_size(buf)); + return first_data == ncb_size(buf); +} + +/* Returns true if <buf> contains data fragmented by gaps. */ +int ncb_is_fragmented(const struct ncbuf *buf) +{ + struct ncb_blk data, gap; + + if (ncb_is_null(buf)) + return 0; + + /* check if buffer is empty or full */ + if (ncb_is_empty(buf) || ncb_is_full(buf)) + return 0; + + /* check that following gap is the last block */ + data = ncb_blk_first(buf); + gap = ncb_blk_next(buf, &data); + return !ncb_blk_is_last(buf, &gap); +} + +/* Returns the number of bytes of data available in <buf> starting at offset + * <off> until the next gap or the buffer end. The counted data may wrapped if + * the buffer storage is not aligned. + */ +ncb_sz_t ncb_data(const struct ncbuf *buf, ncb_sz_t off) +{ + struct ncb_blk blk; + ncb_sz_t off_blk; + + if (ncb_is_null(buf)) + return 0; + + blk = ncb_blk_find(buf, off); + off_blk = ncb_blk_off(&blk, off); + + /* if <off> at the frontier between two and <blk> is gap, retrieve the + * next data block. + */ + if (blk.flag & NCB_BK_F_GAP && off_blk == blk.sz && + !ncb_blk_is_last(buf, &blk)) { + blk = ncb_blk_next(buf, &blk); + off_blk = ncb_blk_off(&blk, off); + } + + if (blk.flag & NCB_BK_F_GAP) + return 0; + + return blk.sz - off_blk; +} + +/* Add a new block at <data> of size <len> in <buf> at offset <off>. + * + * Returns NCB_RET_OK on success. On error the following codes are returned : + * - NCB_RET_GAP_SIZE : cannot add data because the gap formed is too small + * - NCB_RET_DATA_REJ : old data would be overwritten by different ones in + * NCB_ADD_COMPARE mode. + */ +enum ncb_ret ncb_add(struct ncbuf *buf, ncb_sz_t off, + const char *data, ncb_sz_t len, enum ncb_add_mode mode) +{ + struct ncb_blk blk; + ncb_sz_t left = len; + enum ncb_ret ret; + char *new_sz; + + if (!len) + return NCB_RET_OK; + + BUG_ON_HOT(off + len > ncb_size(buf)); + + /* Get block where insertion begins. */ + blk = ncb_blk_find(buf, off); + + /* Check if insertion is possible. */ + ret = ncb_check_insert(buf, &blk, off, data, len, mode); + if (ret != NCB_RET_OK) + return ret; + + if (blk.flag & NCB_BK_F_GAP) { + /* Reduce gap size if insertion begins in a gap. Gap data size + * is reset and will be recalculated during insertion. + */ + const ncb_sz_t gap_sz = off - blk.off; + BUG_ON_HOT(gap_sz < NCB_GAP_MIN_SZ); + + /* pointer to data size to increase. */ + new_sz = ncb_peek(buf, blk.off + NCB_GAP_SZ_DATA_OFF); + + ncb_write_off(buf, blk.sz_ptr, gap_sz); + ncb_write_off(buf, new_sz, 0); + } + else { + /* pointer to data size to increase. */ + new_sz = blk.sz_ptr; + } + + /* insert data */ + while (left) { + struct ncb_blk next; + const ncb_sz_t off_blk = ncb_blk_off(&blk, off); + ncb_sz_t done; + + /* retrieve the next block. This is necessary to do this + * before overwriting a gap. + */ + next = ncb_blk_next(buf, &blk); + + if (blk.flag & NCB_BK_F_GAP) { + done = ncb_fill_gap_blk(buf, &blk, off_blk, data, left); + + /* update the inserted data block size */ + if (off + done == blk.off + blk.sz) { + /* merge next data block if insertion reached gap end */ + ncb_inc_off(buf, new_sz, done + blk.sz_data); + } + else { + /* insertion stopped before gap end */ + ncb_inc_off(buf, new_sz, done); + } + } + else { + done = ncb_fill_data_blk(buf, &blk, off_blk, data, left, mode); + } + + BUG_ON_HOT(done > blk.sz || done > left); + left -= done; + data += done; + off += done; + + blk = next; + } + + return NCB_RET_OK; +} + +/* Advance the head of <buf> to the offset <adv>. Data at the start of buffer + * will be lost while some space will be formed at the end to be able to insert + * new data. + * + * Returns NCB_RET_OK on success. It may return NCB_RET_GAP_SIZE if operation + * is rejected due to the formation of a too small gap in front. If advance is + * done only inside a data block it is guaranteed to succeed. + */ +enum ncb_ret ncb_advance(struct ncbuf *buf, ncb_sz_t adv) +{ + struct ncb_blk start, last; + ncb_sz_t off_blk; + ncb_sz_t first_data_sz; + + BUG_ON_HOT(adv > ncb_size(buf)); + if (!adv) + return NCB_RET_OK; + + /* Special case if adv is full size. This is equivalent to a reset. */ + if (adv == ncb_size(buf)) { + ncb_init(buf, buf->head); + return NCB_RET_OK; + } + + start = ncb_blk_find(buf, adv); + + /* Special case if advance until the last block which is a GAP. The + * buffer will be left empty and is thus equivalent to a reset. + */ + if (ncb_blk_is_last(buf, &start) && (start.flag & NCB_BK_F_GAP)) { + ncb_sz_t new_head = buf->head + adv; + if (new_head >= buf->size) + new_head -= buf->size; + + ncb_init(buf, new_head); + return NCB_RET_OK; + } + + last = start; + while (!ncb_blk_is_last(buf, &last)) + last = ncb_blk_next(buf, &last); + + off_blk = ncb_blk_off(&start, adv); + + if (start.flag & NCB_BK_F_GAP) { + /* If advance in a GAP, its new size must be big enough. */ + if (start.sz == off_blk) { + /* GAP removed. Buffer will start with following DATA block. */ + first_data_sz = start.sz_data; + } + else if (start.sz - off_blk < NCB_GAP_MIN_SZ) { + return NCB_RET_GAP_SIZE; + } + else { + /* Buffer will start with this GAP block. */ + first_data_sz = 0; + } + } + else { + /* If off_blk less than start.sz, the data block will becomes the + * first block. If equal, the data block is completely removed + * and thus the following GAP will be the first block. + */ + first_data_sz = start.sz - off_blk; + } + + if (last.flag & NCB_BK_F_GAP) { + /* Extend last GAP unless this is a reduced gap. */ + if (!(last.flag & NCB_BK_F_FIN) || last.sz + adv >= NCB_GAP_MIN_SZ) { + /* use .st instead of .sz_ptr which can be NULL if reduced gap */ + ncb_write_off(buf, last.st, last.sz + adv); + ncb_write_off(buf, ncb_peek(buf, last.off + NCB_GAP_SZ_DATA_OFF), 0); + } + } + else { + /* Insert a GAP after the last DATA block. */ + if (adv >= NCB_GAP_MIN_SZ) { + ncb_write_off(buf, ncb_peek(buf, last.off + last.sz + NCB_GAP_SZ_OFF), adv); + ncb_write_off(buf, ncb_peek(buf, last.off + last.sz + NCB_GAP_SZ_DATA_OFF), 0); + } + } + + /* Advance head and update reserved header with new first data size. */ + buf->head += adv; + if (buf->head >= buf->size) + buf->head -= buf->size; + ncb_write_off(buf, ncb_reserved(buf), first_data_sz); + + /* If advance in a GAP, reduce its size. */ + if (start.flag & NCB_BK_F_GAP && !first_data_sz) { + ncb_write_off(buf, ncb_head(buf), start.sz - off_blk); + /* Recopy the block sz_data at the new position. */ + ncb_write_off(buf, ncb_peek(buf, NCB_GAP_SZ_DATA_OFF), start.sz_data); + } + + return NCB_RET_OK; +} + +/* ******** testing API ******** */ +/* To build it : + * gcc -Wall -DSTANDALONE -lasan -I./include -o ncbuf src/ncbuf.c + */ +#ifdef STANDALONE + +int ncb_print = 0; + +static void ncbuf_printf(char *str, ...) +{ + va_list args; + + va_start(args, str); + if (ncb_print) + vfprintf(stderr, str, args); + va_end(args); +} + +struct rand_off { + struct list el; + ncb_sz_t off; + ncb_sz_t len; +}; + +static struct rand_off *ncb_generate_rand_off(const struct ncbuf *buf) +{ + struct rand_off *roff; + roff = calloc(1, sizeof(*roff)); + BUG_ON(!roff); + + roff->off = rand() % (ncb_size(buf)); + if (roff->off > 0 && roff->off < NCB_GAP_MIN_SZ) + roff->off = 0; + + roff->len = rand() % (ncb_size(buf) - roff->off + 1); + + return roff; +} + +static void ncb_print_blk(const struct ncb_blk *blk) +{ + if (ncb_print) { + fprintf(stderr, "%s(%s): %2u/%u.\n", + blk->flag & NCB_BK_F_GAP ? "GAP " : "DATA", + blk->flag & NCB_BK_F_FIN ? "F" : "-", blk->off, blk->sz); + } +} + +static int ncb_is_null_blk(const struct ncb_blk *blk) +{ + return !blk->st; +} + +static void ncb_loop(const struct ncbuf *buf) +{ + struct ncb_blk blk; + + blk = ncb_blk_first(buf); + do { + ncb_print_blk(&blk); + blk = ncb_blk_next(buf, &blk); + } while (!ncb_is_null_blk(&blk)); + + ncbuf_printf("\n"); +} + +static void ncbuf_print_buf(struct ncbuf *b, ncb_sz_t len, + unsigned char *area, int line) +{ + int i; + + ncbuf_printf("buffer status at line %d\n", line); + for (i = 0; i < len; ++i) { + ncbuf_printf("%02x.", area[i]); + if (i && i % 32 == 31) ncbuf_printf("\n"); + else if (i && i % 8 == 7) ncbuf_printf(" "); + } + ncbuf_printf("\n"); + + ncb_loop(b); + + if (ncb_print) + getchar(); +} + +static struct ncbuf b; +static unsigned char *bufarea = NULL; +static ncb_sz_t bufsize = 16384; +static ncb_sz_t bufhead = 15; + +#define NCB_INIT(buf) \ + if ((reset)) { memset(bufarea, 0xaa, bufsize); } \ + ncb_init(buf, bufhead); \ + ncbuf_print_buf(&b, bufsize, bufarea, __LINE__); + +#define NCB_ADD_EQ(buf, off, data, sz, mode, ret) \ + BUG_ON(ncb_add((buf), (off), (data), (sz), (mode)) != (ret)); \ + ncbuf_print_buf(buf, bufsize, bufarea, __LINE__); + +#define NCB_ADD_NEQ(buf, off, data, sz, mode, ret) \ + BUG_ON(ncb_add((buf), (off), (data), (sz), (mode)) == (ret)); \ + ncbuf_print_buf(buf, bufsize, bufarea, __LINE__); + +#define NCB_ADVANCE_EQ(buf, off, ret) \ + BUG_ON(ncb_advance((buf), (off)) != (ret)); \ + ncbuf_print_buf(buf, bufsize, bufarea, __LINE__); + +#define NCB_TOTAL_DATA_EQ(buf, data) \ + BUG_ON(ncb_total_data((buf)) != (data)); + +#define NCB_DATA_EQ(buf, off, data) \ + BUG_ON(ncb_data((buf), (off)) != (data)); + +static int ncbuf_test(ncb_sz_t head, int reset, int print_delay) +{ + char *data0, data1[] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f }; + struct list list = LIST_HEAD_INIT(list); + struct rand_off *roff, *roff_tmp; + enum ncb_ret ret; + + data0 = malloc(bufsize); + memset(data0, 0xff, bufsize); + + bufarea = malloc(bufsize); + + fprintf(stderr, "running unit tests\n"); + + b = NCBUF_NULL; + BUG_ON(!ncb_is_null(&b)); + NCB_DATA_EQ(&b, 0, 0); + NCB_TOTAL_DATA_EQ(&b, 0); + BUG_ON(ncb_size(&b) != 0); + BUG_ON(!ncb_is_empty(&b)); + BUG_ON(ncb_is_full(&b)); + BUG_ON(ncb_is_fragmented(&b)); + + b.area = (char *)bufarea; + b.size = bufsize; + b.head = head; + NCB_INIT(&b); + + /* insertion test suite */ + NCB_INIT(&b); + NCB_DATA_EQ(&b, 0, 0); NCB_DATA_EQ(&b, bufsize - NCB_RESERVED_SZ - 1, 0); /* first and last offset */ + NCB_ADD_EQ(&b, 24, data0, 9, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 24, 9); + /* insert new data at the same offset as old */ + NCB_ADD_EQ(&b, 24, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 24, 16); + + NCB_INIT(&b); NCB_DATA_EQ(&b, 0, 0); + NCB_ADD_EQ(&b, 0, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 0, 16); + BUG_ON(ncb_is_fragmented(&b)); + NCB_ADD_EQ(&b, 24, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 0, 16); + BUG_ON(!ncb_is_fragmented(&b)); + /* insert data overlapping two data blocks and a gap */ + NCB_ADD_EQ(&b, 12, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 0, 40); + BUG_ON(ncb_is_fragmented(&b)); + + NCB_INIT(&b); + NCB_ADD_EQ(&b, 32, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 0, 0); NCB_DATA_EQ(&b, 16, 0); NCB_DATA_EQ(&b, 32, 16); + BUG_ON(!ncb_is_fragmented(&b)); + NCB_ADD_EQ(&b, 0, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 0, 16); NCB_DATA_EQ(&b, 16, 0); NCB_DATA_EQ(&b, 32, 16); + BUG_ON(!ncb_is_fragmented(&b)); + /* insert data to exactly cover a gap between two data blocks */ + NCB_ADD_EQ(&b, 16, data0, 16, NCB_ADD_PRESERVE, NCB_RET_OK); NCB_DATA_EQ(&b, 0, 48); NCB_DATA_EQ(&b, 16, 32); NCB_DATA_EQ(&b, 32, 16); + BUG_ON(ncb_is_fragmented(&b)); + + NCB_INIT(&b); + NCB_ADD_EQ(&b, 0, data0, 8, NCB_ADD_PRESERVE, NCB_RET_OK); + /* this insertion must be rejected because of minimal gap size */ + NCB_ADD_EQ(&b, 10, data0, 8, NCB_ADD_PRESERVE, NCB_RET_GAP_SIZE); + + /* Test reduced gap support */ + NCB_INIT(&b); + /* this insertion will form a reduced gap */ + NCB_ADD_EQ(&b, 0, data0, bufsize - (NCB_GAP_MIN_SZ - 1), NCB_ADD_COMPARE, NCB_RET_OK); + + /* Test the various insertion mode */ + NCB_INIT(&b); + NCB_ADD_EQ(&b, 10, data1, 16, NCB_ADD_PRESERVE, NCB_RET_OK); + NCB_ADD_EQ(&b, 12, data1, 16, NCB_ADD_COMPARE, NCB_RET_DATA_REJ); + NCB_ADD_EQ(&b, 12, data1, 16, NCB_ADD_PRESERVE, NCB_RET_OK); BUG_ON(*ncb_peek(&b, 12) != data1[2]); + NCB_ADD_EQ(&b, 12, data1, 16, NCB_ADD_OVERWRT, NCB_RET_OK); BUG_ON(*ncb_peek(&b, 12) == data1[2]); + + /* advance test suite */ + NCB_INIT(&b); + NCB_ADVANCE_EQ(&b, 10, NCB_RET_OK); /* advance in an empty buffer; this ensures we do not leave an empty DATA in the middle of the buffer */ + NCB_ADVANCE_EQ(&b, ncb_size(&b) - 2, NCB_RET_OK); + + NCB_INIT(&b); + /* first fill the buffer */ + NCB_ADD_EQ(&b, 0, data0, bufsize - NCB_RESERVED_SZ, NCB_ADD_COMPARE, NCB_RET_OK); + /* delete 2 bytes : a reduced gap must be created */ + NCB_ADVANCE_EQ(&b, 2, NCB_RET_OK); NCB_TOTAL_DATA_EQ(&b, ncb_size(&b) - 2); + /* delete 1 byte : extend the reduced gap */ + NCB_ADVANCE_EQ(&b, 1, NCB_RET_OK); NCB_TOTAL_DATA_EQ(&b, ncb_size(&b) - 3); + /* delete 5 bytes : a full gap must be present */ + NCB_ADVANCE_EQ(&b, 5, NCB_RET_OK); NCB_TOTAL_DATA_EQ(&b, ncb_size(&b) - 8); + /* completely clear the buffer */ + NCB_ADVANCE_EQ(&b, bufsize - NCB_RESERVED_SZ, NCB_RET_OK); NCB_TOTAL_DATA_EQ(&b, 0); + + + NCB_INIT(&b); + NCB_ADD_EQ(&b, 10, data0, 10, NCB_ADD_PRESERVE, NCB_RET_OK); + NCB_ADVANCE_EQ(&b, 2, NCB_RET_OK); /* reduce a gap in front of the buffer */ + NCB_ADVANCE_EQ(&b, 1, NCB_RET_GAP_SIZE); /* reject */ + NCB_ADVANCE_EQ(&b, 8, NCB_RET_OK); /* remove completely the gap */ + NCB_ADVANCE_EQ(&b, 8, NCB_RET_OK); /* remove inside the data */ + NCB_ADVANCE_EQ(&b, 10, NCB_RET_OK); /* remove completely the data */ + + fprintf(stderr, "first random pass\n"); + NCB_INIT(&b); + + /* generate randon data offsets until the buffer is full */ + while (!ncb_is_full(&b)) { + roff = ncb_generate_rand_off(&b); + LIST_INSERT(&list, &roff->el); + + ret = ncb_add(&b, roff->off, data0, roff->len, NCB_ADD_COMPARE); + BUG_ON(ret == NCB_RET_DATA_REJ); + ncbuf_print_buf(&b, bufsize, bufarea, __LINE__); + usleep(print_delay); + } + + fprintf(stderr, "buf full, prepare for reverse random\n"); + ncbuf_print_buf(&b, bufsize, bufarea, __LINE__); + + /* insert the previously generated random offsets in the reverse order. + * At the end, the buffer should be full. + */ + NCB_INIT(&b); + list_for_each_entry_safe(roff, roff_tmp, &list, el) { + int full = ncb_is_full(&b); + if (!full) { + ret = ncb_add(&b, roff->off, data0, roff->len, NCB_ADD_COMPARE); + BUG_ON(ret == NCB_RET_DATA_REJ); + ncbuf_print_buf(&b, bufsize, bufarea, __LINE__); + usleep(print_delay); + } + + LIST_DELETE(&roff->el); + free(roff); + } + + if (!ncb_is_full(&b)) + abort(); + + fprintf(stderr, "done\n"); + + free(bufarea); + free(data0); + + return 1; +} + +int main(int argc, char **argv) +{ + int reset = 0; + int print_delay = 100000; + char c; + + opterr = 0; + while ((c = getopt(argc, argv, "h:s:rp::")) != -1) { + switch (c) { + case 'h': + bufhead = atoi(optarg); + break; + case 's': + bufsize = atoi(optarg); + if (bufsize < 64) { + fprintf(stderr, "bufsize should be at least 64 bytes for unit test suite\n"); + exit(127); + } + break; + case 'r': + reset = 1; + break; + case 'p': + if (optarg) + print_delay = atoi(optarg); + ncb_print = 1; + break; + case '?': + default: + fprintf(stderr, "usage: %s [-r] [-s bufsize] [-h bufhead] [-p <delay_msec>]\n", argv[0]); + exit(127); + } + } + + ncbuf_test(bufhead, reset, print_delay); + return EXIT_SUCCESS; +} + +#endif /* STANDALONE */ |