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 */
42typedef 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 */
59int 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 */
67void ngtcp2_rob_gap_del(ngtcp2_rob_gap *g, const ngtcp2_mem *mem);
68
69/*
70 * ngtcp2_rob_data holds the buffered stream data.
71 */
72typedef 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 */
95int 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 */
103void 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 */
109typedef 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 */
132int 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 */
137void 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 */
149int 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 */
162int 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 */
170size_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 */
184void 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 */
190uint64_t ngtcp2_rob_first_gap_offset(ngtcp2_rob *rob);
191
192/*
193 * ngtcp2_rob_data_buffered returns nonzero if any data is buffered.
194 */
195int ngtcp2_rob_data_buffered(ngtcp2_rob *rob);
196
197#endif /* NGTCP2_ROB_H */
198