1 /* 2 * ngtcp2 3 * 4 * Copyright (c) 2017 ngtcp2 contributors 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining 7 * a copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sublicense, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 */ 25 #ifndef NGTCP2_ROB_H 26 #define NGTCP2_ROB_H 27 28 #ifdef HAVE_CONFIG_H 29 # include <config.h> 30 #endif /* HAVE_CONFIG_H */ 31 32 #include <ngtcp2/ngtcp2.h> 33 34 #include "ngtcp2_mem.h" 35 #include "ngtcp2_range.h" 36 #include "ngtcp2_ksl.h" 37 38 /* 39 * ngtcp2_rob_gap represents the gap, which is the range of stream 40 * data that is not received yet. 41 */ 42 typedef struct ngtcp2_rob_gap { 43 /* range is the range of this gap. */ 44 ngtcp2_range range; 45 } ngtcp2_rob_gap; 46 47 /* 48 * ngtcp2_rob_gap_new allocates new ngtcp2_rob_gap object, and assigns 49 * its pointer to |*pg|. The caller should call ngtcp2_rob_gap_del to 50 * delete it when it is no longer used. The range of the gap is 51 * [begin, end). |mem| is custom memory allocator to allocate memory. 52 * 53 * This function returns 0 if it succeeds, or one of the following 54 * negative error codes: 55 * 56 * NGTCP2_ERR_NOMEM 57 * Out of memory. 58 */ 59 int ngtcp2_rob_gap_new(ngtcp2_rob_gap **pg, uint64_t begin, uint64_t end, 60 const ngtcp2_mem *mem); 61 62 /* 63 * ngtcp2_rob_gap_del deallocates |g|. It deallocates the memory 64 * pointed by |g| it self. |mem| is custom memory allocator to 65 * deallocate memory. 66 */ 67 void ngtcp2_rob_gap_del(ngtcp2_rob_gap *g, const ngtcp2_mem *mem); 68 69 /* 70 * ngtcp2_rob_data holds the buffered stream data. 71 */ 72 typedef struct ngtcp2_rob_data { 73 /* range is the range of this gap. */ 74 ngtcp2_range range; 75 /* begin points to the buffer. */ 76 uint8_t *begin; 77 /* end points to the one beyond of the last byte of the buffer */ 78 uint8_t *end; 79 } ngtcp2_rob_data; 80 81 /* 82 * ngtcp2_rob_data_new allocates new ngtcp2_rob_data object, and 83 * assigns its pointer to |*pd|. The caller should call 84 * ngtcp2_rob_data_del to delete it when it is no longer used. 85 * |offset| is the stream offset of the first byte of this data. 86 * |chunk| is the size of the buffer. |offset| must be multiple of 87 * |chunk|. |mem| is custom memory allocator to allocate memory. 88 * 89 * This function returns 0 if it succeeds, or one of the following 90 * negative error codes: 91 * 92 * NGTCP2_ERR_NOMEM 93 * Out of memory. 94 */ 95 int ngtcp2_rob_data_new(ngtcp2_rob_data **pd, uint64_t offset, size_t chunk, 96 const ngtcp2_mem *mem); 97 98 /* 99 * ngtcp2_rob_data_del deallocates |d|. It deallocates the memory 100 * pointed by |d| itself. |mem| is custom memory allocator to 101 * deallocate memory. 102 */ 103 void ngtcp2_rob_data_del(ngtcp2_rob_data *d, const ngtcp2_mem *mem); 104 105 /* 106 * ngtcp2_rob is the reorder buffer which reassembles stream data 107 * received in out of order. 108 */ 109 typedef struct ngtcp2_rob { 110 /* gapksl maintains the range of offset which is not received 111 yet. Initially, its range is [0, UINT64_MAX). */ 112 ngtcp2_ksl gapksl; 113 /* dataksl maintains the list of buffers which store received data 114 ordered by stream offset. */ 115 ngtcp2_ksl dataksl; 116 /* mem is custom memory allocator */ 117 const ngtcp2_mem *mem; 118 /* chunk is the size of each buffer in data field */ 119 size_t chunk; 120 } ngtcp2_rob; 121 122 /* 123 * ngtcp2_rob_init initializes |rob|. |chunk| is the size of buffer 124 * per chunk. 125 * 126 * This function returns 0 if it succeeds, or one of the following 127 * negative error codes: 128 * 129 * NGTCP2_ERR_NOMEM 130 * Out of memory. 131 */ 132 int ngtcp2_rob_init(ngtcp2_rob *rob, size_t chunk, const ngtcp2_mem *mem); 133 134 /* 135 * ngtcp2_rob_free frees resources allocated for |rob|. 136 */ 137 void ngtcp2_rob_free(ngtcp2_rob *rob); 138 139 /* 140 * ngtcp2_rob_push adds new data of length |datalen| at the stream 141 * offset |offset|. 142 * 143 * This function returns 0 if it succeeds, or one of the following 144 * negative error codes: 145 * 146 * NGTCP2_ERR_NOMEM 147 * Out of memory 148 */ 149 int ngtcp2_rob_push(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data, 150 size_t datalen); 151 152 /* 153 * ngtcp2_rob_remove_prefix removes gap up to |offset|, exclusive. It 154 * also removes data buffer if it is completely included in |offset|. 155 * 156 * This function returns 0 if it succeeds, or one of the following 157 * negative error codes: 158 * 159 * NGTCP2_ERR_NOMEM 160 * Out of memory 161 */ 162 int ngtcp2_rob_remove_prefix(ngtcp2_rob *rob, uint64_t offset); 163 164 /* 165 * ngtcp2_rob_data_at stores the pointer to the buffer of stream 166 * offset |offset| to |*pdest| if it is available, and returns the 167 * valid length of available data. If no data is available, it 168 * returns 0. 169 */ 170 size_t ngtcp2_rob_data_at(ngtcp2_rob *rob, const uint8_t **pdest, 171 uint64_t offset); 172 173 /* 174 * ngtcp2_rob_pop clears data at stream offset |offset| of length 175 * |len|. 176 * 177 * |offset| must be the offset given in ngtcp2_rob_data_at. |len| 178 * must be the return value of ngtcp2_rob_data_at when |offset| is 179 * passed. 180 * 181 * Caller should call this function from offset 0 in non-decreasing 182 * order. 183 */ 184 void ngtcp2_rob_pop(ngtcp2_rob *rob, uint64_t offset, size_t len); 185 186 /* 187 * ngtcp2_rob_first_gap_offset returns the offset to the first gap. 188 * If there is no gap, it returns UINT64_MAX. 189 */ 190 uint64_t ngtcp2_rob_first_gap_offset(ngtcp2_rob *rob); 191 192 /* 193 * ngtcp2_rob_data_buffered returns nonzero if any data is buffered. 194 */ 195 int ngtcp2_rob_data_buffered(ngtcp2_rob *rob); 196 197 #endif /* NGTCP2_ROB_H */ 198