src/memchunk.h

   1 /*
   2  * nghttp2 - HTTP/2 C Library
   3  *
   4  * Copyright (c) 2014 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 MEMCHUNK_H
  26 #define MEMCHUNK_H
  27
  28 #include "nghttp2_config.h"
  29
  30 #include <sys/uio.h>
  31
  32 #include <cassert>
  33 #include <cstring>
  34 #include <memory>
  35 #include <array>
  36 #include <algorithm>
  37
  38 #include "template.h"
  39
  40 namespace nghttp2 {
  41
  42 template <size_t N> struct Memchunk {
  43   Memchunk(std::unique_ptr<Memchunk> next_chunk)
  44       : pos(std::begin(buf)), last(pos), knext(std::move(next_chunk)),
  45         kprev(nullptr), next(nullptr) {
  46     if (knext) {
  47       knext->kprev = this;
  48     }
  49   }
  50   size_t len() const { return last - pos; }
  51   size_t left() const { return std::end(buf) - last; }
  52   void reset() { pos = last = std::begin(buf); }
  53   std::array<uint8_t, N> buf;
  54   uint8_t *pos, *last;
  55   std::unique_ptr<Memchunk> knext;
  56   Memchunk *kprev;
  57   Memchunk *next;
  58   static const size_t size = N;
  59 };
  60
  61 template <typename T> struct Pool {
  62   Pool() : pool(nullptr), freelist(nullptr), poolsize(0) {}
  63   T *get() {
  64     if (freelist) {
  65       auto m = freelist;
  66       freelist = freelist->next;
  67       m->next = nullptr;
  68       m->reset();
  69       return m;
  70     }
  71
  72     pool = make_unique<T>(std::move(pool));
  73     poolsize += T::size;
  74     return pool.get();
  75   }
  76   void recycle(T *m) {
  77     if (freelist) {
  78       m->next = freelist;
  79     } else {
  80       m->next = nullptr;
  81     }
  82     freelist = m;
  83   }
  84   void shrink(size_t max) {
  85     auto m = freelist;
  86     for (; m && poolsize > max;) {
  87       auto next = m->next;
  88       poolsize -= T::size;
  89       auto p = m->kprev;
  90       if (p) {
  91         p->knext = std::move(m->knext);
  92         if (p->knext) {
  93           p->knext->kprev = p;
  94         }
  95       } else {
  96         pool = std::move(m->knext);
  97         if (pool) {
  98           pool->kprev = nullptr;
  99         }
 100       }
 101       m = next;
 102     }
 103     freelist = m;
 104   }
 105   void clear() {
 106     freelist = nullptr;
 107     pool = nullptr;
 108     poolsize = 0;
 109   }
 110   using value_type = T;
 111   std::unique_ptr<T> pool;
 112   T *freelist;
 113   size_t poolsize;
 114 };
 115
 116 template <typename Memchunk> struct Memchunks {
 117   Memchunks(Pool<Memchunk> *pool)
 118       : pool(pool), head(nullptr), tail(nullptr), len(0) {}
 119   ~Memchunks() {
 120     if (!pool) {
 121       return;
 122     }
 123     for (auto m = head; m;) {
 124       auto next = m->next;
 125       pool->recycle(m);
 126       m = next;
 127     }
 128   }
 129   size_t append(const void *src, size_t count) {
 130     if (count == 0) {
 131       return 0;
 132     }
 133
 134     auto first = static_cast<const uint8_t *>(src);
 135     auto last = first + count;
 136
 137     if (!tail) {
 138       head = tail = pool->get();
 139     }
 140
 141     for (;;) {
 142       auto n = std::min(static_cast<size_t>(last - first), tail->left());
 143       tail->last = std::copy_n(first, n, tail->last);
 144       first += n;
 145       len += n;
 146       if (first == last) {
 147         break;
 148       }
 149
 150       tail->next = pool->get();
 151       tail = tail->next;
 152     }
 153
 154     return count;
 155   }
 156   template <size_t N> size_t append(const char (&s)[N]) {
 157     return append(s, N - 1);
 158   }
 159   size_t remove(void *dest, size_t count) {
 160     if (!tail || count == 0) {
 161       return 0;
 162     }
 163
 164     auto first = static_cast<uint8_t *>(dest);
 165     auto last = first + count;
 166
 167     auto m = head;
 168
 169     while (m) {
 170       auto next = m->next;
 171       auto n = std::min(static_cast<size_t>(last - first), m->len());
 172
 173       assert(m->len());
 174       first = std::copy_n(m->pos, n, first);
 175       m->pos += n;
 176       len -= n;
 177       if (m->len() > 0) {
 178         break;
 179       }
 180       pool->recycle(m);
 181       m = next;
 182     }
 183     head = m;
 184     if (head == nullptr) {
 185       tail = nullptr;
 186     }
 187
 188     return first - static_cast<uint8_t *>(dest);
 189   }
 190   size_t drain(size_t count) {
 191     auto ndata = count;
 192     auto m = head;
 193     while (m) {
 194       auto next = m->next;
 195       auto n = std::min(count, m->len());
 196       m->pos += n;
 197       count -= n;
 198       len -= n;
 199       if (m->len() > 0) {
 200         break;
 201       }
 202
 203       pool->recycle(m);
 204       m = next;
 205     }
 206     head = m;
 207     if (head == nullptr) {
 208       tail = nullptr;
 209     }
 210     return ndata - count;
 211   }
 212   int riovec(struct iovec *iov, int iovcnt) {
 213     if (!head) {
 214       return 0;
 215     }
 216     auto m = head;
 217     int i;
 218     for (i = 0; i < iovcnt && m; ++i, m = m->next) {
 219       iov[i].iov_base = m->pos;
 220       iov[i].iov_len = m->len();
 221     }
 222     return i;
 223   }
 224   size_t rleft() const { return len; }
 225
 226   Pool<Memchunk> *pool;
 227   Memchunk *head, *tail;
 228   size_t len;
 229 };
 230
 231 using Memchunk16K = Memchunk<16384>;
 232 using MemchunkPool = Pool<Memchunk16K>;
 233 using DefaultMemchunks = Memchunks<Memchunk16K>;
 234
 235 #define DEFAULT_WR_IOVCNT 16
 236
 237 #if defined(IOV_MAX) && IOV_MAX < DEFAULT_WR_IOVCNT
 238 #define MAX_WR_IOVCNT IOV_MAX
 239 #else // !defined(IOV_MAX) || IOV_MAX >= DEFAULT_WR_IOVCNT
 240 #define MAX_WR_IOVCNT DEFAULT_WR_IOVCNT
 241 #endif // !defined(IOV_MAX) || IOV_MAX >= DEFAULT_WR_IOVCNT
 242
 243 inline int limit_iovec(struct iovec *iov, int iovcnt, size_t max) {
 244   if (max == 0) {
 245     return 0;
 246   }
 247   for (int i = 0; i < iovcnt; ++i) {
 248     auto d = std::min(max, iov[i].iov_len);
 249     iov[i].iov_len = d;
 250     max -= d;
 251     if (max == 0) {
 252       return i + 1;
 253     }
 254   }
 255   return iovcnt;
 256 }
 257
 258 } // namespace nghttp2
 259
 260 #endif // MEMCHUNK_H