X-Git-Url: http://git.tuebingen.mpg.de/?a=blobdiff_plain;f=buffer_tree.c;h=aff03444cc8cc3d0181812fc677c03bfa132e3b0;hb=59df964251d4e6b71b4ce6d02fdbb6e11643acab;hp=7180149ee49ade68b6310bb2f596562cb8ff08a8;hpb=b8caed98bbe13587dfb3f59d5c53746a6c6f70a8;p=paraslash.git diff --git a/buffer_tree.c b/buffer_tree.c index 7180149e..aff03444 100644 --- a/buffer_tree.c +++ b/buffer_tree.c @@ -8,6 +8,7 @@ #include "error.h" #include "sched.h" +/* whead = NULL means area full */ struct btr_pool { char *name; char *area_start; @@ -16,16 +17,12 @@ struct btr_pool { char *whead; }; -enum btr_buffer_flags { - /* changes the way the buffer is deallocated */ - BTR_BF_BTR_POOL = 1, -}; - struct btr_buffer { char *buf; size_t size; /** The number of references to this buffer. */ int refcount; + /* NULL means no buffer pool but a malloced buffer. */ struct btr_pool *pool; }; @@ -56,6 +53,17 @@ struct btr_node { void *context; }; +/** + * Create a new buffer pool. + * + * \param name The name of the new buffer pool. + * + * \param area The size in bytes of the pool area. + * + * \return An opaque pointer to the newly created buffer pool. It must be + * passed to btr_pool_free() after it is no longer used to deallocate all + * resources. + */ struct btr_pool *btr_pool_new(const char *name, size_t area_size) { struct btr_pool *btrp; @@ -70,8 +78,11 @@ struct btr_pool *btr_pool_new(const char *name, size_t area_size) return btrp; } -/* whead = NULL means area full */ - +/** + * Dellocate resources used by a buffer pool. + * + * \param btrp A pointer obtained via btr_pool_new(). + */ void btr_pool_free(struct btr_pool *btrp) { if (!btrp) @@ -81,6 +92,14 @@ void btr_pool_free(struct btr_pool *btrp) free(btrp); } +/** + * Return the size of the buffer pool area. + * + * \param btrp The buffer pool. + * + * \return The same value which was passed during creation time to + * btr_pool_new(). + */ size_t btr_pool_size(struct btr_pool *btrp) { return btrp->area_end - btrp->area_start; @@ -95,6 +114,18 @@ size_t btr_pool_filled(struct btr_pool *btrp) return btr_pool_size(btrp) - (btrp->rhead - btrp->whead); } +/** + * Get the number of unused bytes in the buffer pool. + * + * \param btrp The pool. + * + * \return The number of bytes that can currently be allocated. + * + * Note that in general the returned number of bytes is not available as a + * single contiguous buffer. Use btr_pool_available() to obtain the length of + * the largest contiguous buffer that can currently be allocated from the + * buffer pool. + */ size_t btr_pool_unused(struct btr_pool *btrp) { return btr_pool_size(btrp) - btr_pool_filled(btrp); @@ -113,6 +144,15 @@ size_t btr_pool_available(struct btr_pool *btrp) return btrp->rhead - btrp->whead; } +/** + * Obtain the current write head. + * + * \param btrp The buffer pool. + * \param result The write head is returned here. + * + * \return The maximal amount of bytes that may be written to the returned + * buffer. + */ size_t btr_pool_get_buffer(struct btr_pool *btrp, char **result) { if (result) @@ -120,7 +160,16 @@ size_t btr_pool_get_buffer(struct btr_pool *btrp, char **result) return btr_pool_available(btrp); } -void btr_pool_allocate(struct btr_pool *btrp, size_t size) +/** + * Mark a part of the buffer pool area as allocated. + * + * \param btrp The buffer pool. + * \param size The amount of bytes to be allocated. + * + * This is usually called after the caller wrote to the buffer obtained by + * btr_pool_get_buffer(). + */ +static void btr_pool_allocate(struct btr_pool *btrp, size_t size) { char *end; @@ -168,14 +217,15 @@ static void btr_pool_deallocate(struct btr_pool *btrp, size_t size) #define FOR_EACH_BUFFER_REF_SAFE(_br, _tmp, _btrn) \ list_for_each_entry_safe((_br), (_tmp), &(_btrn)->input_queue, node) -/* - (parent, child): - (NULL, NULL): new, isolated node. - (NULL, c): new node becomes root, c must be old root - (p, NULL): new leaf node - (p, c): new internal node, ch must be child of p - -*/ +/** + * Create a new buffer tree node. + * + * \param bnd Specifies how to create the new node. + * + * This function always succeeds (or calls exit()). The returned pointer + * must be freed using btr_free_node() after it has been removed from + * the buffer tree via btr_remove_node(). + */ struct btr_node *btr_new_node(struct btr_node_description *bnd) { struct btr_node *btrn = para_malloc(sizeof(*btrn)); @@ -186,14 +236,31 @@ struct btr_node *btr_new_node(struct btr_node_description *bnd) btrn->context = bnd->context; btrn->start.tv_sec = 0; btrn->start.tv_usec = 0; - if (bnd->parent) - list_add_tail(&btrn->node, &bnd->parent->children); INIT_LIST_HEAD(&btrn->children); INIT_LIST_HEAD(&btrn->input_queue); - if (bnd->parent) - PARA_INFO_LOG("added %s as child of %s\n", bnd->name, bnd->parent->name); - else - PARA_INFO_LOG("added %s as btr root\n", bnd->name); + if (!bnd->child) { + if (bnd->parent) { + list_add_tail(&btrn->node, &bnd->parent->children); + PARA_INFO_LOG("new leaf node: %s (child of %s)\n", + bnd->name, bnd->parent->name); + } else + PARA_INFO_LOG("added %s as btr root\n", bnd->name); + goto out; + } + if (!bnd->parent) { + assert(!bnd->child->parent); + PARA_INFO_LOG("new root: %s (was %s)\n", + bnd->name, bnd->child->name); + btrn->parent = NULL; + list_add_tail(&bnd->child->node, &btrn->children); + /* link it in */ + bnd->child->parent = btrn; + goto out; + } + PARA_EMERG_LOG("inserting internal nodes not yet supported.\n"); + exit(EXIT_FAILURE); + assert(bnd->child->parent == bnd->parent); +out: return btrn; } @@ -262,6 +329,20 @@ static void add_btrb_to_children(struct btr_buffer *btrb, } } +/** + * Insert a malloced buffer into the buffer tree. + * + * \param buf The buffer to insert. + * \param size The size of \a buf in bytes. + * \param btrn Position in the buffer tree to create the output. + * + * This creates references to \a buf and adds these references to each child of + * \a btrn. The buffer will be freed using standard free() once no buffer tree + * node is referencing it any more. + * + * Note that this function must not be used if \a buf was obtained from a + * buffer pool. Use btr_add_output_pool() in this case. + */ void btr_add_output(char *buf, size_t size, struct btr_node *btrn) { struct btr_buffer *btrb; @@ -275,6 +356,18 @@ void btr_add_output(char *buf, size_t size, struct btr_node *btrn) add_btrb_to_children(btrb, btrn, 0); } +/** + * Feed data to child nodes of a buffer tree node. + * + * \param btrp The buffer pool. + * \param size The number of bytes to be allocated and fed to each child. + * \param btrn The node whose children are to be fed. + * + * This function allocates the amount of bytes from the buffer pool area, + * starting at the current value of the write head, and creates buffer + * references to the resulting part of the buffer pool area, one for each child + * of \a btrn. The references are then fed into the input queue of each child. + */ void btr_add_output_pool(struct btr_pool *btrp, size_t size, struct btr_node *btrn) { @@ -293,6 +386,17 @@ void btr_add_output_pool(struct btr_pool *btrp, size_t size, add_btrb_to_children(btrb, btrn, 0); } +/** + * Copy data to write head of a buffer pool and feed it to all children nodes. + * + * \param src The source buffer. + * \param n The size of the source buffer in bytes. + * \param btrp The destination buffer pool. + * \param btrn Add the data as output of this node. + * + * This is expensive. The caller must make sure the data fits into the buffer + * pool area. + */ void btr_copy(const void *src, size_t n, struct btr_pool *btrp, struct btr_node *btrn) { @@ -339,12 +443,28 @@ int btr_pushdown_one(struct btr_node *btrn) return 1; } -/* Return true if this node has no children. */ -bool btr_no_children(struct btr_node *btrn) +/* + * Find out whether a node is a leaf node. + * + * \param btrn The node to check. + * + * \return True if this node has no children. False otherwise. + */ +static bool btr_no_children(struct btr_node *btrn) { return list_empty(&btrn->children); } +/** + * Find out whether a node is an orphan node. + * + * \param btrn The buffer tree node. + * + * \return True if \a btrn has no parent. + * + * This function will always return true for the root node. However in case + * nodes have been removed from the tree, other nodes may become orphans too. + */ bool btr_no_parent(struct btr_node *btrn) { return !btrn->parent; @@ -370,7 +490,13 @@ size_t btr_get_buffer_by_reference(struct btr_buffer_reference *br, char **buf) } /** - * \return zero if the input buffer queue is empty. + * Obtain the next buffer of the input queue of a buffer tree node. + * + * \param btrn The node whose input queue is to be queried. + * \param bufp Result pointer. + * + * \return The number of bytes that can be read from buf. Zero if the input + * buffer queue is empty. In this case the value of \a bufp is undefined. */ size_t btr_next_buffer(struct btr_node *btrn, char **bufp) { @@ -398,6 +524,21 @@ size_t btr_next_buffer(struct btr_node *btrn, char **bufp) return rv; } +/** + * Deallocate the given number of bytes from the input queue. + * + * \param btrn The buffer tree node. + * \param numbytes The number of bytes to be deallocated. + * + * This function must be used to get rid of existing buffer references in the + * node's input queue. If no references to a buffer remain, the underlying + * buffers are either freed (in the non-buffer tree case) or the read head of + * the buffer pool is being advanced. + * + * Note that \a numbytes may be smaller than the buffer size. In this case the + * buffer is not deallocated and subsequent calls to btr_next_buffer() return + * the remaining part of the buffer. + */ void btr_consume(struct btr_node *btrn, size_t numbytes) { struct btr_buffer_reference *br, *tmp; @@ -425,16 +566,14 @@ void btr_consume(struct btr_node *btrn, size_t numbytes) assert(true); } /* - - We have a wrap buffer, consume from it. If in total, - i.e. including previous calls to brt_consume(), less than - wrap_count has been consumed, there's nothing more we can do. - - Otherwise we drop the wrap buffer and consume from subsequent - buffers of the input queue the correct amount of bytes. This - is the total number of bytes that have been consumed from the - wrap buffer. -*/ + * We have a wrap buffer, consume from it. If in total, i.e. including + * previous calls to brt_consume(), less than wrap_count has been + * consumed, there's nothing more we can do. + * + * Otherwise we drop the wrap buffer and consume from subsequent + * buffers of the input queue the correct amount of bytes. This is the + * total number of bytes that have been consumed from the wrap buffer. + */ PARA_DEBUG_LOG("consuming %zu/%zu bytes from wrap buffer\n", numbytes, br_available_bytes(br)); @@ -479,6 +618,17 @@ void btr_remove_node(struct btr_node *btrn) list_del(&btrn->node); } +/** + * Return the amount of available input bytes of a buffer tree node. + * + * \param btrn The node whose input size should be computed. + * + * \return The total number of bytes available in the node's input + * queue. + * + * This simply iterates over all buffer references in the input queue and + * returns the sum of the sizes of all references. + */ size_t btr_get_input_queue_size(struct btr_node *btrn) { struct btr_buffer_reference *br; @@ -520,7 +670,7 @@ void btr_splice_out_node(struct btr_node *btrn) * * Iterates over all children of the given node. */ -size_t btr_bytes_pending(struct btr_node *btrn) +static size_t btr_bytes_pending(struct btr_node *btrn) { size_t max_size = 0; struct btr_node *ch; @@ -541,6 +691,9 @@ int btr_exec(struct btr_node *btrn, const char *command, char **value_result) return btrn->execute(btrn, command, value_result); } +/** + * Execute a inter-node command. + */ int btr_exec_up(struct btr_node *btrn, const char *command, char **value_result) { int ret; @@ -652,7 +805,6 @@ next: para_list_add(&br->node, &btrn->input_queue); return; } - PARA_DEBUG_LOG("increasing wrap buffer, sz1: %zu, sz2: %zu\n", sz1, sz2); /* * We already have a wrap buffer, but it is too small. It might be * partially used. @@ -661,6 +813,8 @@ next: if (wbr->wrap_count == sz1 && wbr->btrb->size >= sz1 + sz2) /* nothing we can do about it */ return; sz = sz1 + sz2 - wbr->btrb->size; /* amount of new data */ + PARA_DEBUG_LOG("increasing wrap buffer %zu -> %zu\n", wbr->btrb->size, + wbr->btrb->size + sz); wbr->btrb->size += sz; wbr->btrb->buf = para_realloc(wbr->btrb->buf, wbr->btrb->size); /* copy the new data to the end of the reallocated buffer */ @@ -695,6 +849,7 @@ static int merge_input(struct btr_node *btrn) if (i == 2) break; } + assert(i == 2); /* make a new btrb that combines the two buffers and a br to it. */ sz = szs[0] + szs[1]; buf = para_malloc(sz);