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 <limits.h>
  31 #ifdef _WIN32
  32 /* Structure for scatter/gather I/O.  */
  33 struct iovec {
  34   void *iov_base; /* Pointer to data.  */
  35   size_t iov_len; /* Length of data.  */
  36 };
  37 #else // !_WIN32
  38 #  include <sys/uio.h>
  39 #endif // !_WIN32
  40
  41 #include <cassert>
  42 #include <cstring>
  43 #include <memory>
  44 #include <array>
  45 #include <algorithm>
  46 #include <string>
  47 #include <utility>
  48
  49 #include "template.h"
  50
  51 namespace nghttp2 {
  52
  53 #define DEFAULT_WR_IOVCNT 16
  54
  55 #if defined(IOV_MAX) && IOV_MAX < DEFAULT_WR_IOVCNT
  56 #  define MAX_WR_IOVCNT IOV_MAX
  57 #else // !defined(IOV_MAX) || IOV_MAX >= DEFAULT_WR_IOVCNT
  58 #  define MAX_WR_IOVCNT DEFAULT_WR_IOVCNT
  59 #endif // !defined(IOV_MAX) || IOV_MAX >= DEFAULT_WR_IOVCNT
  60
  61 template <size_t N> struct Memchunk {
  62   Memchunk(Memchunk *next_chunk)
  63       : pos(std::begin(buf)), last(pos), knext(next_chunk), next(nullptr) {}
  64   size_t len() const { return last - pos; }
  65   size_t left() const { return std::end(buf) - last; }
  66   void reset() { pos = last = std::begin(buf); }
  67   std::array<uint8_t, N> buf;
  68   uint8_t *pos, *last;
  69   Memchunk *knext;
  70   Memchunk *next;
  71   static const size_t size = N;
  72 };
  73
  74 template <typename T> struct Pool {
  75   Pool() : pool(nullptr), freelist(nullptr), poolsize(0) {}
  76   ~Pool() { clear(); }
  77   T *get() {
  78     if (freelist) {
  79       auto m = freelist;
  80       freelist = freelist->next;
  81       m->next = nullptr;
  82       m->reset();
  83       return m;
  84     }
  85
  86     pool = new T{pool};
  87     poolsize += T::size;
  88     return pool;
  89   }
  90   void recycle(T *m) {
  91     m->next = freelist;
  92     freelist = m;
  93   }
  94   void clear() {
  95     freelist = nullptr;
  96     for (auto p = pool; p;) {
  97       auto knext = p->knext;
  98       delete p;
  99       p = knext;
 100     }
 101     pool = nullptr;
 102     poolsize = 0;
 103   }
 104   using value_type = T;
 105   T *pool;
 106   T *freelist;
 107   size_t poolsize;
 108 };
 109
 110 template <typename Memchunk> struct Memchunks {
 111   Memchunks(Pool<Memchunk> *pool)
 112       : pool(pool), head(nullptr), tail(nullptr), len(0) {}
 113   Memchunks(const Memchunks &) = delete;
 114   Memchunks(Memchunks &&other) noexcept
 115       : pool{other.pool}, // keep other.pool
 116         head{std::exchange(other.head, nullptr)},
 117         tail{std::exchange(other.tail, nullptr)},
 118         len{std::exchange(other.len, 0)} {}
 119   Memchunks &operator=(const Memchunks &) = delete;
 120   Memchunks &operator=(Memchunks &&other) noexcept {
 121     if (this == &other) {
 122       return *this;
 123     }
 124
 125     reset();
 126
 127     pool = other.pool;
 128     head = std::exchange(other.head, nullptr);
 129     tail = std::exchange(other.tail, nullptr);
 130     len = std::exchange(other.len, 0);
 131
 132     return *this;
 133   }
 134   ~Memchunks() {
 135     if (!pool) {
 136       return;
 137     }
 138     for (auto m = head; m;) {
 139       auto next = m->next;
 140       pool->recycle(m);
 141       m = next;
 142     }
 143   }
 144   size_t append(char c) {
 145     if (!tail) {
 146       head = tail = pool->get();
 147     } else if (tail->left() == 0) {
 148       tail->next = pool->get();
 149       tail = tail->next;
 150     }
 151     *tail->last++ = c;
 152     ++len;
 153     return 1;
 154   }
 155   size_t append(const void *src, size_t count) {
 156     if (count == 0) {
 157       return 0;
 158     }
 159
 160     auto first = static_cast<const uint8_t *>(src);
 161     auto last = first + count;
 162
 163     if (!tail) {
 164       head = tail = pool->get();
 165     }
 166
 167     for (;;) {
 168       auto n = std::min(static_cast<size_t>(last - first), tail->left());
 169       tail->last = std::copy_n(first, n, tail->last);
 170       first += n;
 171       len += n;
 172       if (first == last) {
 173         break;
 174       }
 175
 176       tail->next = pool->get();
 177       tail = tail->next;
 178     }
 179
 180     return count;
 181   }
 182   template <size_t N> size_t append(const char (&s)[N]) {
 183     return append(s, N - 1);
 184   }
 185   size_t append(const std::string &s) { return append(s.c_str(), s.size()); }
 186   size_t append(const StringRef &s) { return append(s.c_str(), s.size()); }
 187   size_t append(const ImmutableString &s) {
 188     return append(s.c_str(), s.size());
 189   }
 190   size_t copy(Memchunks &dest) {
 191     auto m = head;
 192     while (m) {
 193       dest.append(m->pos, m->len());
 194       m = m->next;
 195     }
 196     return len;
 197   }
 198   size_t remove(void *dest, size_t count) {
 199     if (!tail || count == 0) {
 200       return 0;
 201     }
 202
 203     auto first = static_cast<uint8_t *>(dest);
 204     auto last = first + count;
 205
 206     auto m = head;
 207
 208     while (m) {
 209       auto next = m->next;
 210       auto n = std::min(static_cast<size_t>(last - first), m->len());
 211
 212       assert(m->len());
 213       first = std::copy_n(m->pos, n, first);
 214       m->pos += n;
 215       len -= n;
 216       if (m->len() > 0) {
 217         break;
 218       }
 219       pool->recycle(m);
 220       m = next;
 221     }
 222     head = m;
 223     if (head == nullptr) {
 224       tail = nullptr;
 225     }
 226
 227     return first - static_cast<uint8_t *>(dest);
 228   }
 229   size_t remove(Memchunks &dest, size_t count) {
 230     if (!tail || count == 0) {
 231       return 0;
 232     }
 233
 234     auto left = count;
 235     auto m = head;
 236
 237     while (m) {
 238       auto next = m->next;
 239       auto n = std::min(left, m->len());
 240
 241       assert(m->len());
 242       dest.append(m->pos, n);
 243       m->pos += n;
 244       len -= n;
 245       left -= n;
 246       if (m->len() > 0) {
 247         break;
 248       }
 249       pool->recycle(m);
 250       m = next;
 251     }
 252     head = m;
 253     if (head == nullptr) {
 254       tail = nullptr;
 255     }
 256
 257     return count - left;
 258   }
 259   size_t remove(Memchunks &dest) {
 260     assert(pool == dest.pool);
 261
 262     if (head == nullptr) {
 263       return 0;
 264     }
 265
 266     auto n = len;
 267
 268     if (dest.tail == nullptr) {
 269       dest.head = head;
 270     } else {
 271       dest.tail->next = head;
 272     }
 273
 274     dest.tail = tail;
 275     dest.len += len;
 276
 277     head = tail = nullptr;
 278     len = 0;
 279
 280     return n;
 281   }
 282   size_t drain(size_t count) {
 283     auto ndata = count;
 284     auto m = head;
 285     while (m) {
 286       auto next = m->next;
 287       auto n = std::min(count, m->len());
 288       m->pos += n;
 289       count -= n;
 290       len -= n;
 291       if (m->len() > 0) {
 292         break;
 293       }
 294
 295       pool->recycle(m);
 296       m = next;
 297     }
 298     head = m;
 299     if (head == nullptr) {
 300       tail = nullptr;
 301     }
 302     return ndata - count;
 303   }
 304   int riovec(struct iovec *iov, int iovcnt) const {
 305     if (!head) {
 306       return 0;
 307     }
 308     auto m = head;
 309     int i;
 310     for (i = 0; i < iovcnt && m; ++i, m = m->next) {
 311       iov[i].iov_base = m->pos;
 312       iov[i].iov_len = m->len();
 313     }
 314     return i;
 315   }
 316   size_t rleft() const { return len; }
 317   void reset() {
 318     for (auto m = head; m;) {
 319       auto next = m->next;
 320       pool->recycle(m);
 321       m = next;
 322     }
 323     len = 0;
 324     head = tail = nullptr;
 325   }
 326
 327   Pool<Memchunk> *pool;
 328   Memchunk *head, *tail;
 329   size_t len;
 330 };
 331
 332 // Wrapper around Memchunks to offer "peeking" functionality.
 333 template <typename Memchunk> struct PeekMemchunks {
 334   PeekMemchunks(Pool<Memchunk> *pool)
 335       : memchunks(pool),
 336         cur(nullptr),
 337         cur_pos(nullptr),
 338         cur_last(nullptr),
 339         len(0),
 340         peeking(true) {}
 341   PeekMemchunks(const PeekMemchunks &) = delete;
 342   PeekMemchunks(PeekMemchunks &&other) noexcept
 343       : memchunks{std::move(other.memchunks)},
 344         cur{std::exchange(other.cur, nullptr)},
 345         cur_pos{std::exchange(other.cur_pos, nullptr)},
 346         cur_last{std::exchange(other.cur_last, nullptr)},
 347         len{std::exchange(other.len, 0)},
 348         peeking{std::exchange(other.peeking, true)} {}
 349   PeekMemchunks &operator=(const PeekMemchunks &) = delete;
 350   PeekMemchunks &operator=(PeekMemchunks &&other) noexcept {
 351     if (this == &other) {
 352       return *this;
 353     }
 354
 355     memchunks = std::move(other.memchunks);
 356     cur = std::exchange(other.cur, nullptr);
 357     cur_pos = std::exchange(other.cur_pos, nullptr);
 358     cur_last = std::exchange(other.cur_last, nullptr);
 359     len = std::exchange(other.len, 0);
 360     peeking = std::exchange(other.peeking, true);
 361
 362     return *this;
 363   }
 364   size_t append(const void *src, size_t count) {
 365     count = memchunks.append(src, count);
 366     len += count;
 367     return count;
 368   }
 369   size_t remove(void *dest, size_t count) {
 370     if (!peeking) {
 371       count = memchunks.remove(dest, count);
 372       len -= count;
 373       return count;
 374     }
 375
 376     if (count == 0 || len == 0) {
 377       return 0;
 378     }
 379
 380     if (!cur) {
 381       cur = memchunks.head;
 382       cur_pos = cur->pos;
 383     }
 384
 385     // cur_last could be updated in append
 386     cur_last = cur->last;
 387
 388     if (cur_pos == cur_last) {
 389       assert(cur->next);
 390       cur = cur->next;
 391     }
 392
 393     auto first = static_cast<uint8_t *>(dest);
 394     auto last = first + count;
 395
 396     for (;;) {
 397       auto n = std::min(last - first, cur_last - cur_pos);
 398
 399       first = std::copy_n(cur_pos, n, first);
 400       cur_pos += n;
 401       len -= n;
 402
 403       if (first == last) {
 404         break;
 405       }
 406       assert(cur_pos == cur_last);
 407       if (!cur->next) {
 408         break;
 409       }
 410       cur = cur->next;
 411       cur_pos = cur->pos;
 412       cur_last = cur->last;
 413     }
 414     return first - static_cast<uint8_t *>(dest);
 415   }
 416   size_t rleft() const { return len; }
 417   size_t rleft_buffered() const { return memchunks.rleft(); }
 418   void disable_peek(bool drain) {
 419     if (!peeking) {
 420       return;
 421     }
 422     if (drain) {
 423       auto n = rleft_buffered() - rleft();
 424       memchunks.drain(n);
 425       assert(len == memchunks.rleft());
 426     } else {
 427       len = memchunks.rleft();
 428     }
 429     cur = nullptr;
 430     cur_pos = cur_last = nullptr;
 431     peeking = false;
 432   }
 433   void reset() {
 434     memchunks.reset();
 435     cur = nullptr;
 436     cur_pos = cur_last = nullptr;
 437     len = 0;
 438     peeking = true;
 439   }
 440   Memchunks<Memchunk> memchunks;
 441   // Pointer to the Memchunk currently we are reading/writing.
 442   Memchunk *cur;
 443   // Region inside cur, we have processed to cur_pos.
 444   uint8_t *cur_pos, *cur_last;
 445   // This is the length we have left unprocessed.  len <=
 446   // memchunk.rleft() must hold.
 447   size_t len;
 448   // true if peeking is enabled.  Initially it is true.
 449   bool peeking;
 450 };
 451
 452 using Memchunk16K = Memchunk<16_k>;
 453 using MemchunkPool = Pool<Memchunk16K>;
 454 using DefaultMemchunks = Memchunks<Memchunk16K>;
 455 using DefaultPeekMemchunks = PeekMemchunks<Memchunk16K>;
 456
 457 inline int limit_iovec(struct iovec *iov, int iovcnt, size_t max) {
 458   if (max == 0) {
 459     return 0;
 460   }
 461   for (int i = 0; i < iovcnt; ++i) {
 462     auto d = std::min(max, iov[i].iov_len);
 463     iov[i].iov_len = d;
 464     max -= d;
 465     if (max == 0) {
 466       return i + 1;
 467     }
 468   }
 469   return iovcnt;
 470 }
 471
 472 // MemchunkBuffer is similar to Buffer, but it uses pooled Memchunk
 473 // for its underlying buffer.
 474 template <typename Memchunk> struct MemchunkBuffer {
 475   MemchunkBuffer(Pool<Memchunk> *pool) : pool(pool), chunk(nullptr) {}
 476   MemchunkBuffer(const MemchunkBuffer &) = delete;
 477   MemchunkBuffer(MemchunkBuffer &&other) noexcept
 478       : pool(other.pool), chunk(other.chunk) {
 479     other.chunk = nullptr;
 480   }
 481   MemchunkBuffer &operator=(const MemchunkBuffer &) = delete;
 482   MemchunkBuffer &operator=(MemchunkBuffer &&other) noexcept {
 483     if (this == &other) {
 484       return *this;
 485     }
 486
 487     pool = other.pool;
 488     chunk = other.chunk;
 489
 490     other.chunk = nullptr;
 491
 492     return *this;
 493   }
 494
 495   ~MemchunkBuffer() {
 496     if (!pool || !chunk) {
 497       return;
 498     }
 499     pool->recycle(chunk);
 500   }
 501
 502   // Ensures that the underlying buffer is allocated.
 503   void ensure_chunk() {
 504     if (chunk) {
 505       return;
 506     }
 507     chunk = pool->get();
 508   }
 509
 510   // Releases the underlying buffer.
 511   void release_chunk() {
 512     if (!chunk) {
 513       return;
 514     }
 515     pool->recycle(chunk);
 516     chunk = nullptr;
 517   }
 518
 519   // Returns true if the underlying buffer is allocated.
 520   bool chunk_avail() const { return chunk != nullptr; }
 521
 522   // The functions below must be called after the underlying buffer is
 523   // allocated (use ensure_chunk).
 524
 525   // MemchunkBuffer provides the same interface functions with Buffer.
 526   // Since we has chunk as a member variable, pos and last are
 527   // implemented as wrapper functions.
 528
 529   uint8_t *pos() const { return chunk->pos; }
 530   uint8_t *last() const { return chunk->last; }
 531
 532   size_t rleft() const { return chunk->len(); }
 533   size_t wleft() const { return chunk->left(); }
 534   size_t write(const void *src, size_t count) {
 535     count = std::min(count, wleft());
 536     auto p = static_cast<const uint8_t *>(src);
 537     chunk->last = std::copy_n(p, count, chunk->last);
 538     return count;
 539   }
 540   size_t write(size_t count) {
 541     count = std::min(count, wleft());
 542     chunk->last += count;
 543     return count;
 544   }
 545   size_t drain(size_t count) {
 546     count = std::min(count, rleft());
 547     chunk->pos += count;
 548     return count;
 549   }
 550   size_t drain_reset(size_t count) {
 551     count = std::min(count, rleft());
 552     std::copy(chunk->pos + count, chunk->last, std::begin(chunk->buf));
 553     chunk->last = std::begin(chunk->buf) + (chunk->last - (chunk->pos + count));
 554     chunk->pos = std::begin(chunk->buf);
 555     return count;
 556   }
 557   void reset() { chunk->reset(); }
 558   uint8_t *begin() { return std::begin(chunk->buf); }
 559   uint8_t &operator[](size_t n) { return chunk->buf[n]; }
 560   const uint8_t &operator[](size_t n) const { return chunk->buf[n]; }
 561
 562   Pool<Memchunk> *pool;
 563   Memchunk *chunk;
 564 };
 565
 566 using DefaultMemchunkBuffer = MemchunkBuffer<Memchunk16K>;
 567
 568 } // namespace nghttp2
 569
 570 #endif // MEMCHUNK_H