summaryrefslogtreecommitdiffstats
path: root/src/memchunk.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/memchunk.h664
1 files changed, 664 insertions, 0 deletions
diff --git a/src/memchunk.h b/src/memchunk.h
new file mode 100644
index 0000000..7a7f2e9
--- /dev/null
+++ b/src/memchunk.h
@@ -0,0 +1,664 @@
+/*
+ * nghttp2 - HTTP/2 C Library
+ *
+ * Copyright (c) 2014 Tatsuhiro Tsujikawa
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#ifndef MEMCHUNK_H
+#define MEMCHUNK_H
+
+#include "nghttp2_config.h"
+
+#include <limits.h>
+#ifdef _WIN32
+/* Structure for scatter/gather I/O. */
+struct iovec {
+ void *iov_base; /* Pointer to data. */
+ size_t iov_len; /* Length of data. */
+};
+#else // !_WIN32
+# include <sys/uio.h>
+#endif // !_WIN32
+
+#include <cassert>
+#include <cstring>
+#include <memory>
+#include <array>
+#include <algorithm>
+#include <string>
+#include <utility>
+
+#include "template.h"
+
+namespace nghttp2 {
+
+#define DEFAULT_WR_IOVCNT 16
+
+#if defined(IOV_MAX) && IOV_MAX < DEFAULT_WR_IOVCNT
+# define MAX_WR_IOVCNT IOV_MAX
+#else // !defined(IOV_MAX) || IOV_MAX >= DEFAULT_WR_IOVCNT
+# define MAX_WR_IOVCNT DEFAULT_WR_IOVCNT
+#endif // !defined(IOV_MAX) || IOV_MAX >= DEFAULT_WR_IOVCNT
+
+template <size_t N> struct Memchunk {
+ Memchunk(Memchunk *next_chunk)
+ : pos(std::begin(buf)), last(pos), knext(next_chunk), next(nullptr) {}
+ size_t len() const { return last - pos; }
+ size_t left() const { return std::end(buf) - last; }
+ void reset() { pos = last = std::begin(buf); }
+ std::array<uint8_t, N> buf;
+ uint8_t *pos, *last;
+ Memchunk *knext;
+ Memchunk *next;
+ static const size_t size = N;
+};
+
+template <typename T> struct Pool {
+ Pool() : pool(nullptr), freelist(nullptr), poolsize(0), freelistsize(0) {}
+ ~Pool() { clear(); }
+ T *get() {
+ if (freelist) {
+ auto m = freelist;
+ freelist = freelist->next;
+ m->next = nullptr;
+ m->reset();
+ freelistsize -= T::size;
+ return m;
+ }
+
+ pool = new T{pool};
+ poolsize += T::size;
+ return pool;
+ }
+ void recycle(T *m) {
+ m->next = freelist;
+ freelist = m;
+ freelistsize += T::size;
+ }
+ void clear() {
+ freelist = nullptr;
+ freelistsize = 0;
+ for (auto p = pool; p;) {
+ auto knext = p->knext;
+ delete p;
+ p = knext;
+ }
+ pool = nullptr;
+ poolsize = 0;
+ }
+ using value_type = T;
+ T *pool;
+ T *freelist;
+ size_t poolsize;
+ size_t freelistsize;
+};
+
+template <typename Memchunk> struct Memchunks {
+ Memchunks(Pool<Memchunk> *pool)
+ : pool(pool),
+ head(nullptr),
+ tail(nullptr),
+ len(0),
+ mark(nullptr),
+ mark_pos(nullptr),
+ mark_offset(0) {}
+ Memchunks(const Memchunks &) = delete;
+ Memchunks(Memchunks &&other) noexcept
+ : pool{other.pool}, // keep other.pool
+ head{std::exchange(other.head, nullptr)},
+ tail{std::exchange(other.tail, nullptr)},
+ len{std::exchange(other.len, 0)},
+ mark{std::exchange(other.mark, nullptr)},
+ mark_pos{std::exchange(other.mark_pos, nullptr)},
+ mark_offset{std::exchange(other.mark_offset, 0)} {}
+ Memchunks &operator=(const Memchunks &) = delete;
+ Memchunks &operator=(Memchunks &&other) noexcept {
+ if (this == &other) {
+ return *this;
+ }
+
+ reset();
+
+ pool = other.pool;
+ head = std::exchange(other.head, nullptr);
+ tail = std::exchange(other.tail, nullptr);
+ len = std::exchange(other.len, 0);
+ mark = std::exchange(other.mark, nullptr);
+ mark_pos = std::exchange(other.mark_pos, nullptr);
+ mark_offset = std::exchange(other.mark_offset, 0);
+
+ return *this;
+ }
+ ~Memchunks() {
+ if (!pool) {
+ return;
+ }
+ for (auto m = head; m;) {
+ auto next = m->next;
+ pool->recycle(m);
+ m = next;
+ }
+ }
+ size_t append(char c) {
+ if (!tail) {
+ head = tail = pool->get();
+ } else if (tail->left() == 0) {
+ tail->next = pool->get();
+ tail = tail->next;
+ }
+ *tail->last++ = c;
+ ++len;
+ return 1;
+ }
+ size_t append(const void *src, size_t count) {
+ if (count == 0) {
+ return 0;
+ }
+
+ auto first = static_cast<const uint8_t *>(src);
+ auto last = first + count;
+
+ if (!tail) {
+ head = tail = pool->get();
+ }
+
+ for (;;) {
+ auto n = std::min(static_cast<size_t>(last - first), tail->left());
+ tail->last = std::copy_n(first, n, tail->last);
+ first += n;
+ len += n;
+ if (first == last) {
+ break;
+ }
+
+ tail->next = pool->get();
+ tail = tail->next;
+ }
+
+ return count;
+ }
+ template <size_t N> size_t append(const char (&s)[N]) {
+ return append(s, N - 1);
+ }
+ size_t append(const std::string &s) { return append(s.c_str(), s.size()); }
+ size_t append(const StringRef &s) { return append(s.c_str(), s.size()); }
+ size_t append(const ImmutableString &s) {
+ return append(s.c_str(), s.size());
+ }
+ size_t copy(Memchunks &dest) {
+ auto m = head;
+ while (m) {
+ dest.append(m->pos, m->len());
+ m = m->next;
+ }
+ return len;
+ }
+ size_t remove(void *dest, size_t count) {
+ assert(mark == nullptr);
+
+ if (!tail || count == 0) {
+ return 0;
+ }
+
+ auto first = static_cast<uint8_t *>(dest);
+ auto last = first + count;
+
+ auto m = head;
+
+ while (m) {
+ auto next = m->next;
+ auto n = std::min(static_cast<size_t>(last - first), m->len());
+
+ assert(m->len());
+ first = std::copy_n(m->pos, n, first);
+ m->pos += n;
+ len -= n;
+ if (m->len() > 0) {
+ break;
+ }
+ pool->recycle(m);
+ m = next;
+ }
+ head = m;
+ if (head == nullptr) {
+ tail = nullptr;
+ }
+
+ return first - static_cast<uint8_t *>(dest);
+ }
+ size_t remove(Memchunks &dest, size_t count) {
+ assert(mark == nullptr);
+
+ if (!tail || count == 0) {
+ return 0;
+ }
+
+ auto left = count;
+ auto m = head;
+
+ while (m) {
+ auto next = m->next;
+ auto n = std::min(left, m->len());
+
+ assert(m->len());
+ dest.append(m->pos, n);
+ m->pos += n;
+ len -= n;
+ left -= n;
+ if (m->len() > 0) {
+ break;
+ }
+ pool->recycle(m);
+ m = next;
+ }
+ head = m;
+ if (head == nullptr) {
+ tail = nullptr;
+ }
+
+ return count - left;
+ }
+ size_t remove(Memchunks &dest) {
+ assert(pool == dest.pool);
+ assert(mark == nullptr);
+
+ if (head == nullptr) {
+ return 0;
+ }
+
+ auto n = len;
+
+ if (dest.tail == nullptr) {
+ dest.head = head;
+ } else {
+ dest.tail->next = head;
+ }
+
+ dest.tail = tail;
+ dest.len += len;
+
+ head = tail = nullptr;
+ len = 0;
+
+ return n;
+ }
+ size_t drain(size_t count) {
+ assert(mark == nullptr);
+
+ auto ndata = count;
+ auto m = head;
+ while (m) {
+ auto next = m->next;
+ auto n = std::min(count, m->len());
+ m->pos += n;
+ count -= n;
+ len -= n;
+ if (m->len() > 0) {
+ break;
+ }
+
+ pool->recycle(m);
+ m = next;
+ }
+ head = m;
+ if (head == nullptr) {
+ tail = nullptr;
+ }
+ return ndata - count;
+ }
+ size_t drain_mark(size_t count) {
+ auto ndata = count;
+ auto m = head;
+ while (m) {
+ auto next = m->next;
+ auto n = std::min(count, m->len());
+ m->pos += n;
+ count -= n;
+ len -= n;
+ mark_offset -= n;
+
+ if (m->len() > 0) {
+ assert(mark != m || m->pos <= mark_pos);
+ break;
+ }
+ if (mark == m) {
+ assert(m->pos <= mark_pos);
+
+ mark = nullptr;
+ mark_pos = nullptr;
+ mark_offset = 0;
+ }
+
+ pool->recycle(m);
+ m = next;
+ }
+ head = m;
+ if (head == nullptr) {
+ tail = nullptr;
+ }
+ return ndata - count;
+ }
+ int riovec(struct iovec *iov, int iovcnt) const {
+ if (!head) {
+ return 0;
+ }
+ auto m = head;
+ int i;
+ for (i = 0; i < iovcnt && m; ++i, m = m->next) {
+ iov[i].iov_base = m->pos;
+ iov[i].iov_len = m->len();
+ }
+ return i;
+ }
+ int riovec_mark(struct iovec *iov, int iovcnt) {
+ if (!head || iovcnt == 0) {
+ return 0;
+ }
+
+ int i = 0;
+ Memchunk *m;
+ if (mark) {
+ if (mark_pos != mark->last) {
+ iov[0].iov_base = mark_pos;
+ iov[0].iov_len = mark->len() - (mark_pos - mark->pos);
+
+ mark_pos = mark->last;
+ mark_offset += iov[0].iov_len;
+ i = 1;
+ }
+ m = mark->next;
+ } else {
+ i = 0;
+ m = head;
+ }
+
+ for (; i < iovcnt && m; ++i, m = m->next) {
+ iov[i].iov_base = m->pos;
+ iov[i].iov_len = m->len();
+
+ mark = m;
+ mark_pos = m->last;
+ mark_offset += m->len();
+ }
+
+ return i;
+ }
+ size_t rleft() const { return len; }
+ size_t rleft_mark() const { return len - mark_offset; }
+ void reset() {
+ for (auto m = head; m;) {
+ auto next = m->next;
+ pool->recycle(m);
+ m = next;
+ }
+ len = 0;
+ head = tail = mark = nullptr;
+ mark_pos = nullptr;
+ mark_offset = 0;
+ }
+
+ Pool<Memchunk> *pool;
+ Memchunk *head, *tail;
+ size_t len;
+ Memchunk *mark;
+ uint8_t *mark_pos;
+ size_t mark_offset;
+};
+
+// Wrapper around Memchunks to offer "peeking" functionality.
+template <typename Memchunk> struct PeekMemchunks {
+ PeekMemchunks(Pool<Memchunk> *pool)
+ : memchunks(pool),
+ cur(nullptr),
+ cur_pos(nullptr),
+ cur_last(nullptr),
+ len(0),
+ peeking(true) {}
+ PeekMemchunks(const PeekMemchunks &) = delete;
+ PeekMemchunks(PeekMemchunks &&other) noexcept
+ : memchunks{std::move(other.memchunks)},
+ cur{std::exchange(other.cur, nullptr)},
+ cur_pos{std::exchange(other.cur_pos, nullptr)},
+ cur_last{std::exchange(other.cur_last, nullptr)},
+ len{std::exchange(other.len, 0)},
+ peeking{std::exchange(other.peeking, true)} {}
+ PeekMemchunks &operator=(const PeekMemchunks &) = delete;
+ PeekMemchunks &operator=(PeekMemchunks &&other) noexcept {
+ if (this == &other) {
+ return *this;
+ }
+
+ memchunks = std::move(other.memchunks);
+ cur = std::exchange(other.cur, nullptr);
+ cur_pos = std::exchange(other.cur_pos, nullptr);
+ cur_last = std::exchange(other.cur_last, nullptr);
+ len = std::exchange(other.len, 0);
+ peeking = std::exchange(other.peeking, true);
+
+ return *this;
+ }
+ size_t append(const void *src, size_t count) {
+ count = memchunks.append(src, count);
+ len += count;
+ return count;
+ }
+ size_t remove(void *dest, size_t count) {
+ if (!peeking) {
+ count = memchunks.remove(dest, count);
+ len -= count;
+ return count;
+ }
+
+ if (count == 0 || len == 0) {
+ return 0;
+ }
+
+ if (!cur) {
+ cur = memchunks.head;
+ cur_pos = cur->pos;
+ }
+
+ // cur_last could be updated in append
+ cur_last = cur->last;
+
+ if (cur_pos == cur_last) {
+ assert(cur->next);
+ cur = cur->next;
+ }
+
+ auto first = static_cast<uint8_t *>(dest);
+ auto last = first + count;
+
+ for (;;) {
+ auto n = std::min(last - first, cur_last - cur_pos);
+
+ first = std::copy_n(cur_pos, n, first);
+ cur_pos += n;
+ len -= n;
+
+ if (first == last) {
+ break;
+ }
+ assert(cur_pos == cur_last);
+ if (!cur->next) {
+ break;
+ }
+ cur = cur->next;
+ cur_pos = cur->pos;
+ cur_last = cur->last;
+ }
+ return first - static_cast<uint8_t *>(dest);
+ }
+ size_t rleft() const { return len; }
+ size_t rleft_buffered() const { return memchunks.rleft(); }
+ void disable_peek(bool drain) {
+ if (!peeking) {
+ return;
+ }
+ if (drain) {
+ auto n = rleft_buffered() - rleft();
+ memchunks.drain(n);
+ assert(len == memchunks.rleft());
+ } else {
+ len = memchunks.rleft();
+ }
+ cur = nullptr;
+ cur_pos = cur_last = nullptr;
+ peeking = false;
+ }
+ void reset() {
+ memchunks.reset();
+ cur = nullptr;
+ cur_pos = cur_last = nullptr;
+ len = 0;
+ peeking = true;
+ }
+ Memchunks<Memchunk> memchunks;
+ // Pointer to the Memchunk currently we are reading/writing.
+ Memchunk *cur;
+ // Region inside cur, we have processed to cur_pos.
+ uint8_t *cur_pos, *cur_last;
+ // This is the length we have left unprocessed. len <=
+ // memchunk.rleft() must hold.
+ size_t len;
+ // true if peeking is enabled. Initially it is true.
+ bool peeking;
+};
+
+using Memchunk16K = Memchunk<16_k>;
+using MemchunkPool = Pool<Memchunk16K>;
+using DefaultMemchunks = Memchunks<Memchunk16K>;
+using DefaultPeekMemchunks = PeekMemchunks<Memchunk16K>;
+
+inline int limit_iovec(struct iovec *iov, int iovcnt, size_t max) {
+ if (max == 0) {
+ return 0;
+ }
+ for (int i = 0; i < iovcnt; ++i) {
+ auto d = std::min(max, iov[i].iov_len);
+ iov[i].iov_len = d;
+ max -= d;
+ if (max == 0) {
+ return i + 1;
+ }
+ }
+ return iovcnt;
+}
+
+// MemchunkBuffer is similar to Buffer, but it uses pooled Memchunk
+// for its underlying buffer.
+template <typename Memchunk> struct MemchunkBuffer {
+ MemchunkBuffer(Pool<Memchunk> *pool) : pool(pool), chunk(nullptr) {}
+ MemchunkBuffer(const MemchunkBuffer &) = delete;
+ MemchunkBuffer(MemchunkBuffer &&other) noexcept
+ : pool(other.pool), chunk(other.chunk) {
+ other.chunk = nullptr;
+ }
+ MemchunkBuffer &operator=(const MemchunkBuffer &) = delete;
+ MemchunkBuffer &operator=(MemchunkBuffer &&other) noexcept {
+ if (this == &other) {
+ return *this;
+ }
+
+ pool = other.pool;
+ chunk = other.chunk;
+
+ other.chunk = nullptr;
+
+ return *this;
+ }
+
+ ~MemchunkBuffer() {
+ if (!pool || !chunk) {
+ return;
+ }
+ pool->recycle(chunk);
+ }
+
+ // Ensures that the underlying buffer is allocated.
+ void ensure_chunk() {
+ if (chunk) {
+ return;
+ }
+ chunk = pool->get();
+ }
+
+ // Releases the underlying buffer.
+ void release_chunk() {
+ if (!chunk) {
+ return;
+ }
+ pool->recycle(chunk);
+ chunk = nullptr;
+ }
+
+ // Returns true if the underlying buffer is allocated.
+ bool chunk_avail() const { return chunk != nullptr; }
+
+ // The functions below must be called after the underlying buffer is
+ // allocated (use ensure_chunk).
+
+ // MemchunkBuffer provides the same interface functions with Buffer.
+ // Since we has chunk as a member variable, pos and last are
+ // implemented as wrapper functions.
+
+ uint8_t *pos() const { return chunk->pos; }
+ uint8_t *last() const { return chunk->last; }
+
+ size_t rleft() const { return chunk->len(); }
+ size_t wleft() const { return chunk->left(); }
+ size_t write(const void *src, size_t count) {
+ count = std::min(count, wleft());
+ auto p = static_cast<const uint8_t *>(src);
+ chunk->last = std::copy_n(p, count, chunk->last);
+ return count;
+ }
+ size_t write(size_t count) {
+ count = std::min(count, wleft());
+ chunk->last += count;
+ return count;
+ }
+ size_t drain(size_t count) {
+ count = std::min(count, rleft());
+ chunk->pos += count;
+ return count;
+ }
+ size_t drain_reset(size_t count) {
+ count = std::min(count, rleft());
+ std::copy(chunk->pos + count, chunk->last, std::begin(chunk->buf));
+ chunk->last = std::begin(chunk->buf) + (chunk->last - (chunk->pos + count));
+ chunk->pos = std::begin(chunk->buf);
+ return count;
+ }
+ void reset() { chunk->reset(); }
+ uint8_t *begin() { return std::begin(chunk->buf); }
+ uint8_t &operator[](size_t n) { return chunk->buf[n]; }
+ const uint8_t &operator[](size_t n) const { return chunk->buf[n]; }
+
+ Pool<Memchunk> *pool;
+ Memchunk *chunk;
+};
+
+using DefaultMemchunkBuffer = MemchunkBuffer<Memchunk16K>;
+
+} // namespace nghttp2
+
+#endif // MEMCHUNK_H
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-03 17:17:27 +0000