src/allocator.h

   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 {
  58   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
  66   ~BlockAllocator() { reset(); }
  67
  68   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
  88   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
  99   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
 110   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().
 139   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.
 151   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>
 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().
 193 inline 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>
 199 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().
 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>
 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>
 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>
 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>
 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