1 /*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2016 Tatsuhiro Tsujikawa
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 ALLOCATOR_H
26 #define ALLOCATOR_H
27
28 #include "nghttp2_config.h"
29
30 #ifndef _WIN32
31 # include <sys/uio.h>
32 #endif // !_WIN32
33
34 #include <cassert>
35 #include <utility>
36
37 #include "template.h"
38
39 namespace nghttp2 {
40
41 struct MemBlock {
42 // The next MemBlock to chain them. This is for book keeping
43 // purpose to free them later.
44 MemBlock *next;
45 // begin is the pointer to the beginning of buffer. last is the
46 // location of next write. end is the one beyond of the end of the
47 // buffer.
48 uint8_t *begin, *last, *end;
49 };
50
51 // BlockAllocator allocates memory block with given size at once, and
52 // cuts the region from it when allocation is requested. If the
53 // requested size is larger than given threshold (plus small internal
54 // overhead), it will be allocated in a distinct buffer on demand.
55 // The |isolation_threshold| must be less than or equal to
56 // |block_size|.
57 struct BlockAllocator {
BlockAllocatorBlockAllocator58 BlockAllocator(size_t block_size, size_t isolation_threshold)
59 : retain(nullptr),
60 head(nullptr),
61 block_size(block_size),
62 isolation_threshold(std::min(block_size, isolation_threshold)) {
63 assert(isolation_threshold <= block_size);
64 }
65
~BlockAllocatorBlockAllocator66 ~BlockAllocator() { reset(); }
67
BlockAllocatorBlockAllocator68 BlockAllocator(BlockAllocator &&other) noexcept
69 : retain{std::exchange(other.retain, nullptr)},
70 head{std::exchange(other.head, nullptr)},
71 block_size(other.block_size),
72 isolation_threshold(other.isolation_threshold) {}
73
74 BlockAllocator &operator=(BlockAllocator &&other) noexcept {
75 reset();
76
77 retain = std::exchange(other.retain, nullptr);
78 head = std::exchange(other.head, nullptr);
79 block_size = other.block_size;
80 isolation_threshold = other.isolation_threshold;
81
82 return *this;
83 }
84
85 BlockAllocator(const BlockAllocator &) = delete;
86 BlockAllocator &operator=(const BlockAllocator &) = delete;
87
resetBlockAllocator88 void reset() {
89 for (auto mb = retain; mb;) {
90 auto next = mb->next;
91 delete[] reinterpret_cast<uint8_t *>(mb);
92 mb = next;
93 }
94
95 retain = nullptr;
96 head = nullptr;
97 }
98
alloc_mem_blockBlockAllocator99 MemBlock *alloc_mem_block(size_t size) {
100 auto block = new uint8_t[sizeof(MemBlock) + size];
101 auto mb = reinterpret_cast<MemBlock *>(block);
102
103 mb->next = retain;
104 mb->begin = mb->last = block + sizeof(MemBlock);
105 mb->end = mb->begin + size;
106 retain = mb;
107 return mb;
108 }
109
allocBlockAllocator110 void *alloc(size_t size) {
111 if (size + sizeof(size_t) >= isolation_threshold) {
112 auto len = std::max(static_cast<size_t>(16), size);
113 // We will store the allocated size in size_t field.
114 auto mb = alloc_mem_block(len + sizeof(size_t));
115 auto sp = reinterpret_cast<size_t *>(mb->begin);
116 *sp = len;
117 mb->last = mb->end;
118 return mb->begin + sizeof(size_t);
119 }
120
121 if (!head ||
122 head->end - head->last < static_cast<ssize_t>(size + sizeof(size_t))) {
123 head = alloc_mem_block(block_size);
124 }
125
126 // We will store the allocated size in size_t field.
127 auto res = head->last + sizeof(size_t);
128 auto sp = reinterpret_cast<size_t *>(head->last);
129 *sp = size;
130
131 head->last = reinterpret_cast<uint8_t *>(
132 (reinterpret_cast<intptr_t>(res + size) + 0xf) & ~0xf);
133
134 return res;
135 }
136
137 // Returns allocated size for memory pointed by |ptr|. We assume
138 // that |ptr| was returned from alloc() or realloc().
get_alloc_lengthBlockAllocator139 size_t get_alloc_length(void *ptr) {
140 return *reinterpret_cast<size_t *>(static_cast<uint8_t *>(ptr) -
141 sizeof(size_t));
142 }
143
144 // Allocates memory of at least |size| bytes. If |ptr| is nullptr,
145 // this is equivalent to alloc(size). If |ptr| is not nullptr,
146 // obtain the allocated size for |ptr|, assuming that |ptr| was
147 // returned from alloc() or realloc(). If the allocated size is
148 // greater than or equal to size, |ptr| is returned. Otherwise,
149 // allocates at least |size| bytes of memory, and the original
150 // content pointed by |ptr| is copied to the newly allocated memory.
reallocBlockAllocator151 void *realloc(void *ptr, size_t size) {
152 if (!ptr) {
153 return alloc(size);
154 }
155 auto alloclen = get_alloc_length(ptr);
156 auto p = reinterpret_cast<uint8_t *>(ptr);
157 if (size <= alloclen) {
158 return ptr;
159 }
160
161 auto nalloclen = std::max(size + 1, alloclen * 2);
162
163 auto res = alloc(nalloclen);
164 std::copy_n(p, alloclen, static_cast<uint8_t *>(res));
165
166 return res;
167 }
168
169 // This holds live memory block to free them in dtor.
170 MemBlock *retain;
171 // Current memory block to use.
172 MemBlock *head;
173 // size of single memory block
174 size_t block_size;
175 // if allocation greater or equal to isolation_threshold bytes is
176 // requested, allocate dedicated block.
177 size_t isolation_threshold;
178 };
179
180 // Makes a copy of |src|. The resulting string will be
181 // NULL-terminated.
182 template <typename BlockAllocator>
make_string_ref(BlockAllocator & alloc,const StringRef & src)183 StringRef make_string_ref(BlockAllocator &alloc, const StringRef &src) {
184 auto dst = static_cast<uint8_t *>(alloc.alloc(src.size() + 1));
185 auto p = dst;
186 p = std::copy(std::begin(src), std::end(src), p);
187 *p = '\0';
188 return StringRef{dst, src.size()};
189 }
190
191 // private function used in concat_string_ref. this is the base
192 // function of concat_string_ref_count().
concat_string_ref_count(size_t acc)193 inline constexpr size_t concat_string_ref_count(size_t acc) { return acc; }
194
195 // private function used in concat_string_ref. This function counts
196 // the sum of length of given arguments. The calculated length is
197 // accumulated, and passed to the next function.
198 template <typename... Args>
concat_string_ref_count(size_t acc,const StringRef & value,Args &&...args)199 constexpr size_t concat_string_ref_count(size_t acc, const StringRef &value,
200 Args &&...args) {
201 return concat_string_ref_count(acc + value.size(),
202 std::forward<Args>(args)...);
203 }
204
205 // private function used in concat_string_ref. this is the base
206 // function of concat_string_ref_copy().
concat_string_ref_copy(uint8_t * p)207 inline uint8_t *concat_string_ref_copy(uint8_t *p) { return p; }
208
209 // private function used in concat_string_ref. This function copies
210 // given strings into |p|. |p| is incremented by the copied length,
211 // and returned. In the end, return value points to the location one
212 // beyond the last byte written.
213 template <typename... Args>
concat_string_ref_copy(uint8_t * p,const StringRef & value,Args &&...args)214 uint8_t *concat_string_ref_copy(uint8_t *p, const StringRef &value,
215 Args &&...args) {
216 p = std::copy(std::begin(value), std::end(value), p);
217 return concat_string_ref_copy(p, std::forward<Args>(args)...);
218 }
219
220 // Returns the string which is the concatenation of |args| in the
221 // given order. The resulting string will be NULL-terminated.
222 template <typename BlockAllocator, typename... Args>
concat_string_ref(BlockAllocator & alloc,Args &&...args)223 StringRef concat_string_ref(BlockAllocator &alloc, Args &&...args) {
224 size_t len = concat_string_ref_count(0, std::forward<Args>(args)...);
225 auto dst = static_cast<uint8_t *>(alloc.alloc(len + 1));
226 auto p = dst;
227 p = concat_string_ref_copy(p, std::forward<Args>(args)...);
228 *p = '\0';
229 return StringRef{dst, len};
230 }
231
232 // Returns the string which is the concatenation of |value| and |args|
233 // in the given order. The resulting string will be NULL-terminated.
234 // This function assumes that the pointer value value.c_str() was
235 // obtained from alloc.alloc() or alloc.realloc(), and attempts to use
236 // unused memory region by using alloc.realloc(). If value is empty,
237 // then just call concat_string_ref().
238 template <typename BlockAllocator, typename... Args>
realloc_concat_string_ref(BlockAllocator & alloc,const StringRef & value,Args &&...args)239 StringRef realloc_concat_string_ref(BlockAllocator &alloc,
240 const StringRef &value, Args &&...args) {
241 if (value.empty()) {
242 return concat_string_ref(alloc, std::forward<Args>(args)...);
243 }
244
245 auto len =
246 value.size() + concat_string_ref_count(0, std::forward<Args>(args)...);
247 auto dst = static_cast<uint8_t *>(
248 alloc.realloc(const_cast<uint8_t *>(value.byte()), len + 1));
249 auto p = dst + value.size();
250 p = concat_string_ref_copy(p, std::forward<Args>(args)...);
251 *p = '\0';
252
253 return StringRef{dst, len};
254 }
255
256 struct ByteRef {
257 // The pointer to the beginning of the buffer.
258 uint8_t *base;
259 // The length of the buffer.
260 size_t len;
261 };
262
263 // Makes a buffer with given size. The resulting byte string might
264 // not be NULL-terminated.
265 template <typename BlockAllocator>
make_byte_ref(BlockAllocator & alloc,size_t size)266 ByteRef make_byte_ref(BlockAllocator &alloc, size_t size) {
267 auto dst = static_cast<uint8_t *>(alloc.alloc(size));
268 return {dst, size};
269 }
270
271 } // namespace nghttp2
272
273 #endif // ALLOCATOR_H
274