1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 /* 3 * Copyright 2014 Couchbase, Inc. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 #ifndef NETBUF_MBLOCK_H 19 #define NETBUF_MBLOCK_H 20 21 #include "netbuf-defs.h" 22 23 #ifdef __cplusplus 24 extern "C" { 25 #endif 26 27 /** 28 * @file 29 * 30 * @ingroup netbufs 31 * @defgroup netbufs-mblock Netbuf Block Allocator 32 * @details 33 * 34 * Managed block in-order allocator. 35 * 36 * This allocator attempts to provide unaligned segments of memory in the 37 * order they were allocated in contiguous memory 38 * 39 * @verbatim 40 * 41 * LEGEND 42 * In the following comments (and within the source as well) we will try to 43 * display diagrams of blocks. The following symbols will be used: 44 * 45 * {$:NN} = This represents a position marker, $ will be the position type, 46 * and NN is the offset value. 47 * 48 * The following are the position types: 49 * 50 * [S]tart Start of the buffer (block->start) 51 * [W]rap Wrapping and end of the first segment (block->wrap) 52 * [C]ursor End of the current segment (block->cursor) 53 * [A]lloc Allocation limit of the buffer (block->nalloc) 54 * [F]lush Flush cursor (block->flushcur) 55 * 56 * Note that in some cases two position types may share the same offset. 57 * 58 * Between any of the offsets, there are data bytes (or just "Data"). These 59 * may be one of the following: 60 * 61 * [x] Used data. This data is owned by a span 62 * [o] Unused data, but available for usage 63 * [-] Unreachable data. This is not used but cannot be reserved 64 * 65 * A block contains a single allocated buffer. The buffer itself may be 66 * divided among multiple spans. We divide our buffers like so: 67 * 68 * Initially: 69 * 70 * [ {FS:0}xxxxxxx{CW:10}ooo{A:12} ] 71 * 72 * After flushing some data: 73 * 74 * [ {S:0}xx{F:5}xxxx{CW:10}oo{A:12} ] 75 * Note how the flush cursor is incremented 76 * 77 * 78 * Typically, once data is flushed, the user will release the segment, and thus 79 * will look something like this: 80 * 81 * [ ooo{SF:6}xxxx{CW:10}oooo{A:12} ] 82 * 83 * Appending data to a buffer (or reserving a span) depends on the span 84 * size requirements. In this case, if a span's size is 2 bytes or lower, 85 * it is appended at the end of the first segment, like so: 86 * [ ooo{SF:16}xxxxxx{CWA:12} ] 87 * 88 * Otherwise, it is wrapped around, like so: 89 * 90 * [ xx{C:3}oo{SF:6}xxxx{W:10}--{A:12} ] 91 * 92 * Note that [C] has been wrapped around to start at 3. 93 * 94 * 95 * The total size of the block's used portion is as follows: 96 * 97 * (1) The number of bytes between [S]tart and [Wrap] 98 * (2) If [C] != [W], then also add the value of [C] 99 * @endverbatim 100 * @addtogroup netbufs-mblock 101 * @{ 102 */ 103 104 struct netbuf_mblock_st; 105 struct netbuf_st; 106 struct netbuf_mblock_dealloc_queue_st; 107 108 /** 109 * Small header for larger structures to more efficiently find the block 110 * they were allocated in. 111 * 112 * Note that it is possible to also determine this information by traversing 113 * the list of all blocks, but this is naturally less efficient. 114 */ 115 typedef struct { 116 /** The parent block */ 117 struct netbuf_mblock_st *parent; 118 /** The allocation offset */ 119 nb_SIZE offset; 120 } nb_ALLOCINFO; 121 122 /** 123 * @brief Structure for an out-of-order dealloc 124 */ 125 typedef struct { 126 sllist_node slnode; 127 nb_SIZE offset; /**< Offset into the nb_MBLOCK to release */ 128 nb_SIZE size; /**< Size to release */ 129 } nb_QDEALLOC; 130 131 /** 132 * @brief Data Block 133 * This structure represents the head of an `MBLOCK`. 134 */ 135 typedef struct { 136 sllist_node slnode; 137 138 /** Start position for data */ 139 nb_SIZE start; 140 141 /** 142 * Wrap/End position for data. If the block has only one segment, 143 * this is always equal to cursor (see below) 144 * and will mark the position at which the unused portion of the 145 * buffer begins. 146 * 147 * If the block has two segments, this marks the end of the first segment. 148 * 149 * In both cases 150 * 1. `wrap` is always `> start` 151 * 2. `wrap-start` is the length of the first segment of data 152 */ 153 nb_SIZE wrap; 154 155 /** 156 * End position for data. This always contains the position at which 157 * the unused data begins. 158 * 159 * If the block only has a single segment then both the following are true: 160 * 161 * 1. `cursor == wrap` 162 * 2. `cursor > start` (if not empty) 163 * 164 * If the block has two segments, then both the following are true: 165 * 166 * 1. `cursor != wrap` 167 * 2. `cursor < start` 168 * 169 * If the block is empty: 170 * - `cursor == start` 171 */ 172 nb_SIZE cursor; 173 174 /** 175 * Total number of bytes allocated in `root`. This represents the absolute 176 * limit on how much data can be supplied 177 */ 178 nb_SIZE nalloc; 179 180 /** 181 * Actual allocated buffer. This remains constant for the duration of the 182 * block's lifetime 183 */ 184 char *root; 185 186 /** 187 * Pointer to a nb_DEALLOC_QUEUE structure. This is only valid if an 188 * out-of-order dealloc has been performed on this block. 189 */ 190 struct netbuf_mblock_dealloc_queue_st *deallocs; 191 struct netbuf_mblock_st *parent; 192 } nb_MBLOCK; 193 194 /** 195 * @brief pool of nb_MBLOCK structures 196 */ 197 typedef struct netbuf_mblock_st { 198 /** Active blocks that have at least one reserved span */ 199 sllist_root active; 200 201 /** Available blocks with data */ 202 sllist_root avail; 203 204 /** Allocation size */ 205 nb_SIZE basealloc; 206 207 /** Maximum number of non-cached blocks */ 208 unsigned int maxblocks; 209 210 /** Current number of non-cached blocks */ 211 unsigned int curblocks; 212 213 nb_MBLOCK *cacheblocks; 214 nb_SIZE ncacheblocks; 215 216 struct netbuf_st *mgr; 217 } nb_MBPOOL; 218 219 /** 220 * @brief List of out-of-order deallocs 221 * This is attached to an nb_MBLOCK structure if allocations have been performed 222 * on it in an out-of-order fashion 223 */ 224 typedef struct netbuf_mblock_dealloc_queue_st { 225 sllist_root pending; 226 nb_SIZE min_offset; /**< The first offset contained in the list */ 227 nb_MBPOOL qpool; /**< Used to allcate the nb_QDEALLOC structures themselves*/ 228 } nb_DEALLOC_QUEUE; 229 230 /**@}*/ 231 232 #ifdef __cplusplus 233 } 234 #endif 235 #endif 236