Chris@63: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors Chris@63: // Licensed under the MIT License: Chris@63: // Chris@63: // Permission is hereby granted, free of charge, to any person obtaining a copy Chris@63: // of this software and associated documentation files (the "Software"), to deal Chris@63: // in the Software without restriction, including without limitation the rights Chris@63: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell Chris@63: // copies of the Software, and to permit persons to whom the Software is Chris@63: // furnished to do so, subject to the following conditions: Chris@63: // Chris@63: // The above copyright notice and this permission notice shall be included in Chris@63: // all copies or substantial portions of the Software. Chris@63: // Chris@63: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR Chris@63: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, Chris@63: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE Chris@63: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER Chris@63: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, Chris@63: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN Chris@63: // THE SOFTWARE. Chris@63: Chris@63: #ifndef CAPNP_ARENA_H_ Chris@63: #define CAPNP_ARENA_H_ Chris@63: Chris@63: #if defined(__GNUC__) && !defined(CAPNP_HEADER_WARNINGS) Chris@63: #pragma GCC system_header Chris@63: #endif Chris@63: Chris@63: #ifndef CAPNP_PRIVATE Chris@63: #error "This header is only meant to be included by Cap'n Proto's own source code." Chris@63: #endif Chris@63: Chris@63: #include Chris@63: #include Chris@63: #include Chris@63: #include Chris@63: #include Chris@63: #include "common.h" Chris@63: #include "message.h" Chris@63: #include "layout.h" Chris@63: #include Chris@63: Chris@63: #if !CAPNP_LITE Chris@63: #include "capability.h" Chris@63: #endif // !CAPNP_LITE Chris@63: Chris@63: namespace capnp { Chris@63: Chris@63: #if !CAPNP_LITE Chris@63: class ClientHook; Chris@63: #endif // !CAPNP_LITE Chris@63: Chris@63: namespace _ { // private Chris@63: Chris@63: class SegmentReader; Chris@63: class SegmentBuilder; Chris@63: class Arena; Chris@63: class BuilderArena; Chris@63: class ReadLimiter; Chris@63: Chris@63: class Segment; Chris@63: typedef kj::Id SegmentId; Chris@63: Chris@63: class ReadLimiter { Chris@63: // Used to keep track of how much data has been processed from a message, and cut off further Chris@63: // processing if and when a particular limit is reached. This is primarily intended to guard Chris@63: // against maliciously-crafted messages which contain cycles or overlapping structures. Cycles Chris@63: // and overlapping are not permitted by the Cap'n Proto format because in many cases they could Chris@63: // be used to craft a deceptively small message which could consume excessive server resources to Chris@63: // process, perhaps even sending it into an infinite loop. Actually detecting overlaps would be Chris@63: // time-consuming, so instead we just keep track of how many words worth of data structures the Chris@63: // receiver has actually dereferenced and error out if this gets too high. Chris@63: // Chris@63: // This counting takes place as you call getters (for non-primitive values) on the message Chris@63: // readers. If you call the same getter twice, the data it returns may be double-counted. This Chris@63: // should not be a big deal in most cases -- just set the read limit high enough that it will Chris@63: // only trigger in unreasonable cases. Chris@63: // Chris@63: // This class is "safe" to use from multiple threads for its intended use case. Threads may Chris@63: // overwrite each others' changes to the counter, but this is OK because it only means that the Chris@63: // limit is enforced a bit less strictly -- it will still kick in eventually. Chris@63: Chris@63: public: Chris@63: inline explicit ReadLimiter(); // No limit. Chris@63: inline explicit ReadLimiter(WordCount64 limit); // Limit to the given number of words. Chris@63: Chris@63: inline void reset(WordCount64 limit); Chris@63: Chris@63: KJ_ALWAYS_INLINE(bool canRead(WordCount64 amount, Arena* arena)); Chris@63: Chris@63: void unread(WordCount64 amount); Chris@63: // Adds back some words to the limit. Useful when the caller knows they are double-reading Chris@63: // some data. Chris@63: Chris@63: private: Chris@63: volatile uint64_t limit; Chris@63: // Current limit, decremented each time catRead() is called. Volatile because multiple threads Chris@63: // could be trying to modify it at once. (This is not real thread-safety, but good enough for Chris@63: // the purpose of this class. See class comment.) Chris@63: Chris@63: KJ_DISALLOW_COPY(ReadLimiter); Chris@63: }; Chris@63: Chris@63: #if !CAPNP_LITE Chris@63: class BrokenCapFactory { Chris@63: // Callback for constructing broken caps. We use this so that we can avoid arena.c++ having a Chris@63: // link-time dependency on capability code that lives in libcapnp-rpc. Chris@63: Chris@63: public: Chris@63: virtual kj::Own newBrokenCap(kj::StringPtr description) = 0; Chris@63: virtual kj::Own newNullCap() = 0; Chris@63: }; Chris@63: #endif // !CAPNP_LITE Chris@63: Chris@63: class SegmentReader { Chris@63: public: Chris@63: inline SegmentReader(Arena* arena, SegmentId id, const word* ptr, SegmentWordCount size, Chris@63: ReadLimiter* readLimiter); Chris@63: Chris@63: KJ_ALWAYS_INLINE(const word* checkOffset(const word* from, ptrdiff_t offset)); Chris@63: // Adds the given offset to the given pointer, checks that it is still within the bounds of the Chris@63: // segment, then returns it. Note that the "end" pointer of the segment (which technically points Chris@63: // to the word after the last in the segment) is considered in-bounds for this purpose, so you Chris@63: // can't necessarily dereference it. You must call checkObject() next to check that the object Chris@63: // you want to read is entirely in-bounds. Chris@63: // Chris@63: // If `from + offset` is out-of-range, this returns a pointer to the end of the segment. Thus, Chris@63: // any non-zero-sized object will fail `checkObject()`. We do this instead of throwing to save Chris@63: // some code footprint. Chris@63: Chris@63: KJ_ALWAYS_INLINE(bool checkObject(const word* start, WordCountN<31> size)); Chris@63: // Assuming that `start` is in-bounds for this segment (probably checked using `checkOffset()`), Chris@63: // check that `start + size` is also in-bounds, and hence the whole area in-between is valid. Chris@63: Chris@63: KJ_ALWAYS_INLINE(bool amplifiedRead(WordCount virtualAmount)); Chris@63: // Indicates that the reader should pretend that `virtualAmount` additional data was read even Chris@63: // though no actual pointer was traversed. This is used e.g. when reading a struct list pointer Chris@63: // where the element sizes are zero -- the sender could set the list size arbitrarily high and Chris@63: // cause the receiver to iterate over this list even though the message itself is small, so we Chris@63: // need to defend against DoS attacks based on this. Chris@63: Chris@63: inline Arena* getArena(); Chris@63: inline SegmentId getSegmentId(); Chris@63: Chris@63: inline const word* getStartPtr(); Chris@63: inline SegmentWordCount getOffsetTo(const word* ptr); Chris@63: inline SegmentWordCount getSize(); Chris@63: Chris@63: inline kj::ArrayPtr getArray(); Chris@63: Chris@63: inline void unread(WordCount64 amount); Chris@63: // Add back some words to the ReadLimiter. Chris@63: Chris@63: private: Chris@63: Arena* arena; Chris@63: SegmentId id; Chris@63: kj::ArrayPtr ptr; // size guaranteed to fit in SEGMENT_WORD_COUNT_BITS bits Chris@63: ReadLimiter* readLimiter; Chris@63: Chris@63: KJ_DISALLOW_COPY(SegmentReader); Chris@63: Chris@63: friend class SegmentBuilder; Chris@63: Chris@63: static void abortCheckObjectFault(); Chris@63: // Called in debug mode in cases that would segfault in opt mode. (Should be impossible!) Chris@63: }; Chris@63: Chris@63: class SegmentBuilder: public SegmentReader { Chris@63: public: Chris@63: inline SegmentBuilder(BuilderArena* arena, SegmentId id, word* ptr, SegmentWordCount size, Chris@63: ReadLimiter* readLimiter, SegmentWordCount wordsUsed = ZERO * WORDS); Chris@63: inline SegmentBuilder(BuilderArena* arena, SegmentId id, const word* ptr, SegmentWordCount size, Chris@63: ReadLimiter* readLimiter); Chris@63: inline SegmentBuilder(BuilderArena* arena, SegmentId id, decltype(nullptr), Chris@63: ReadLimiter* readLimiter); Chris@63: Chris@63: KJ_ALWAYS_INLINE(word* allocate(SegmentWordCount amount)); Chris@63: Chris@63: KJ_ALWAYS_INLINE(void checkWritable()); Chris@63: // Throw an exception if the segment is read-only (meaning it is a reference to external data). Chris@63: Chris@63: KJ_ALWAYS_INLINE(word* getPtrUnchecked(SegmentWordCount offset)); Chris@63: // Get a writable pointer into the segment. Throws an exception if the segment is read-only (i.e. Chris@63: // a reference to external immutable data). Chris@63: Chris@63: inline BuilderArena* getArena(); Chris@63: Chris@63: inline kj::ArrayPtr currentlyAllocated(); Chris@63: Chris@63: inline void reset(); Chris@63: Chris@63: inline bool isWritable() { return !readOnly; } Chris@63: Chris@63: inline void tryTruncate(word* from, word* to); Chris@63: // If `from` points just past the current end of the segment, then move the end back to `to`. Chris@63: // Otherwise, do nothing. Chris@63: Chris@63: inline bool tryExtend(word* from, word* to); Chris@63: // If `from` points just past the current end of the segment, and `to` is within the segment Chris@63: // boundaries, then move the end up to `to` and return true. Otherwise, do nothing and return Chris@63: // false. Chris@63: Chris@63: private: Chris@63: word* pos; Chris@63: // Pointer to a pointer to the current end point of the segment, i.e. the location where the Chris@63: // next object should be allocated. Chris@63: Chris@63: bool readOnly; Chris@63: Chris@63: void throwNotWritable(); Chris@63: Chris@63: KJ_DISALLOW_COPY(SegmentBuilder); Chris@63: }; Chris@63: Chris@63: class Arena { Chris@63: public: Chris@63: virtual ~Arena() noexcept(false); Chris@63: Chris@63: virtual SegmentReader* tryGetSegment(SegmentId id) = 0; Chris@63: // Gets the segment with the given ID, or return nullptr if no such segment exists. Chris@63: Chris@63: virtual void reportReadLimitReached() = 0; Chris@63: // Called to report that the read limit has been reached. See ReadLimiter, below. This invokes Chris@63: // the VALIDATE_INPUT() macro which may throw an exception; if it returns normally, the caller Chris@63: // will need to continue with default values. Chris@63: }; Chris@63: Chris@63: class ReaderArena final: public Arena { Chris@63: public: Chris@63: explicit ReaderArena(MessageReader* message); Chris@63: ~ReaderArena() noexcept(false); Chris@63: KJ_DISALLOW_COPY(ReaderArena); Chris@63: Chris@63: // implements Arena ------------------------------------------------ Chris@63: SegmentReader* tryGetSegment(SegmentId id) override; Chris@63: void reportReadLimitReached() override; Chris@63: Chris@63: private: Chris@63: MessageReader* message; Chris@63: ReadLimiter readLimiter; Chris@63: Chris@63: // Optimize for single-segment messages so that small messages are handled quickly. Chris@63: SegmentReader segment0; Chris@63: Chris@63: typedef std::unordered_map> SegmentMap; Chris@63: kj::MutexGuarded>> moreSegments; Chris@63: // We need to mutex-guard the segment map because we lazily initialize segments when they are Chris@63: // first requested, but a Reader is allowed to be used concurrently in multiple threads. Luckily Chris@63: // this only applies to large messages. Chris@63: // Chris@63: // TODO(perf): Thread-local thing instead? Some kind of lockless map? Or do sharing of data Chris@63: // in a different way, where you have to construct a new MessageReader in each thread (but Chris@63: // possibly backed by the same data)? Chris@63: Chris@63: ReaderArena(MessageReader* message, kj::ArrayPtr firstSegment); Chris@63: ReaderArena(MessageReader* message, const word* firstSegment, SegmentWordCount firstSegmentSize); Chris@63: }; Chris@63: Chris@63: class BuilderArena final: public Arena { Chris@63: // A BuilderArena that does not allow the injection of capabilities. Chris@63: Chris@63: public: Chris@63: explicit BuilderArena(MessageBuilder* message); Chris@63: BuilderArena(MessageBuilder* message, kj::ArrayPtr segments); Chris@63: ~BuilderArena() noexcept(false); Chris@63: KJ_DISALLOW_COPY(BuilderArena); Chris@63: Chris@63: inline SegmentBuilder* getRootSegment() { return &segment0; } Chris@63: Chris@63: kj::ArrayPtr> getSegmentsForOutput(); Chris@63: // Get an array of all the segments, suitable for writing out. This only returns the allocated Chris@63: // portion of each segment, whereas tryGetSegment() returns something that includes Chris@63: // not-yet-allocated space. Chris@63: Chris@63: inline CapTableBuilder* getLocalCapTable() { Chris@63: // Return a CapTableBuilder that merely implements local loopback. That is, you can set Chris@63: // capabilities, then read the same capabilities back, but there is no intent ever to transmit Chris@63: // these capabilities. A MessageBuilder that isn't imbued with some other CapTable uses this Chris@63: // by default. Chris@63: // Chris@63: // TODO(cleanup): It's sort of a hack that this exists. In theory, perhaps, unimbued Chris@63: // MessageBuilders should throw exceptions on any attempt to access capability fields, like Chris@63: // unimbued MessageReaders do. However, lots of code exists which uses MallocMessageBuilder Chris@63: // as a temporary holder for data to be copied in and out (without being serialized), and it Chris@63: // is expected that such data can include capabilities, which is admittedly reasonable. Chris@63: // Therefore, all MessageBuilders must have a cap table by default. Arguably we should Chris@63: // deprecate this usage and instead define a new helper type for this exact purpose. Chris@63: Chris@63: return &localCapTable; Chris@63: } Chris@63: Chris@63: SegmentBuilder* getSegment(SegmentId id); Chris@63: // Get the segment with the given id. Crashes or throws an exception if no such segment exists. Chris@63: Chris@63: struct AllocateResult { Chris@63: SegmentBuilder* segment; Chris@63: word* words; Chris@63: }; Chris@63: Chris@63: AllocateResult allocate(SegmentWordCount amount); Chris@63: // Find a segment with at least the given amount of space available and allocate the space. Chris@63: // Note that allocating directly from a particular segment is much faster, but allocating from Chris@63: // the arena is guaranteed to succeed. Therefore callers should try to allocate from a specific Chris@63: // segment first if there is one, then fall back to the arena. Chris@63: Chris@63: SegmentBuilder* addExternalSegment(kj::ArrayPtr content); Chris@63: // Add a new segment to the arena which points to some existing memory region. The segment is Chris@63: // assumed to be completley full; the arena will never allocate from it. In fact, the segment Chris@63: // is considered read-only. Any attempt to get a Builder pointing into this segment will throw Chris@63: // an exception. Readers are allowed, however. Chris@63: // Chris@63: // This can be used to inject some external data into a message without a copy, e.g. embedding a Chris@63: // large mmap'd file into a message as `Data` without forcing that data to actually be read in Chris@63: // from disk (until the message itself is written out). `Orphanage` provides the public API for Chris@63: // this feature. Chris@63: Chris@63: // implements Arena ------------------------------------------------ Chris@63: SegmentReader* tryGetSegment(SegmentId id) override; Chris@63: void reportReadLimitReached() override; Chris@63: Chris@63: private: Chris@63: MessageBuilder* message; Chris@63: ReadLimiter dummyLimiter; Chris@63: Chris@63: class LocalCapTable: public CapTableBuilder { Chris@63: #if !CAPNP_LITE Chris@63: public: Chris@63: kj::Maybe> extractCap(uint index) override; Chris@63: uint injectCap(kj::Own&& cap) override; Chris@63: void dropCap(uint index) override; Chris@63: Chris@63: private: Chris@63: kj::Vector>> capTable; Chris@63: #endif // ! CAPNP_LITE Chris@63: }; Chris@63: Chris@63: LocalCapTable localCapTable; Chris@63: Chris@63: SegmentBuilder segment0; Chris@63: kj::ArrayPtr segment0ForOutput; Chris@63: Chris@63: struct MultiSegmentState { Chris@63: kj::Vector> builders; Chris@63: kj::Vector> forOutput; Chris@63: }; Chris@63: kj::Maybe> moreSegments; Chris@63: Chris@63: SegmentBuilder* segmentWithSpace = nullptr; Chris@63: // When allocating, look for space in this segment first before resorting to allocating a new Chris@63: // segment. This is not necessarily the last segment because addExternalSegment() may add a Chris@63: // segment that is already-full, in which case we don't update this pointer. Chris@63: Chris@63: template // Can be `word` or `const word`. Chris@63: SegmentBuilder* addSegmentInternal(kj::ArrayPtr content); Chris@63: }; Chris@63: Chris@63: // ======================================================================================= Chris@63: Chris@63: inline ReadLimiter::ReadLimiter() Chris@63: : limit(kj::maxValue) {} Chris@63: Chris@63: inline ReadLimiter::ReadLimiter(WordCount64 limit): limit(unbound(limit / WORDS)) {} Chris@63: Chris@63: inline void ReadLimiter::reset(WordCount64 limit) { this->limit = unbound(limit / WORDS); } Chris@63: Chris@63: inline bool ReadLimiter::canRead(WordCount64 amount, Arena* arena) { Chris@63: // Be careful not to store an underflowed value into `limit`, even if multiple threads are Chris@63: // decrementing it. Chris@63: uint64_t current = limit; Chris@63: if (KJ_UNLIKELY(unbound(amount / WORDS) > current)) { Chris@63: arena->reportReadLimitReached(); Chris@63: return false; Chris@63: } else { Chris@63: limit = current - unbound(amount / WORDS); Chris@63: return true; Chris@63: } Chris@63: } Chris@63: Chris@63: // ------------------------------------------------------------------- Chris@63: Chris@63: inline SegmentReader::SegmentReader(Arena* arena, SegmentId id, const word* ptr, Chris@63: SegmentWordCount size, ReadLimiter* readLimiter) Chris@63: : arena(arena), id(id), ptr(kj::arrayPtr(ptr, unbound(size / WORDS))), Chris@63: readLimiter(readLimiter) {} Chris@63: Chris@63: inline const word* SegmentReader::checkOffset(const word* from, ptrdiff_t offset) { Chris@63: ptrdiff_t min = ptr.begin() - from; Chris@63: ptrdiff_t max = ptr.end() - from; Chris@63: if (offset >= min && offset <= max) { Chris@63: return from + offset; Chris@63: } else { Chris@63: return ptr.end(); Chris@63: } Chris@63: } Chris@63: Chris@63: inline bool SegmentReader::checkObject(const word* start, WordCountN<31> size) { Chris@63: auto startOffset = intervalLength(ptr.begin(), start, MAX_SEGMENT_WORDS); Chris@63: #ifdef KJ_DEBUG Chris@63: if (startOffset > bounded(ptr.size()) * WORDS) { Chris@63: abortCheckObjectFault(); Chris@63: } Chris@63: #endif Chris@63: return startOffset + size <= bounded(ptr.size()) * WORDS && Chris@63: readLimiter->canRead(size, arena); Chris@63: } Chris@63: Chris@63: inline bool SegmentReader::amplifiedRead(WordCount virtualAmount) { Chris@63: return readLimiter->canRead(virtualAmount, arena); Chris@63: } Chris@63: Chris@63: inline Arena* SegmentReader::getArena() { return arena; } Chris@63: inline SegmentId SegmentReader::getSegmentId() { return id; } Chris@63: inline const word* SegmentReader::getStartPtr() { return ptr.begin(); } Chris@63: inline SegmentWordCount SegmentReader::getOffsetTo(const word* ptr) { Chris@63: KJ_IREQUIRE(this->ptr.begin() <= ptr && ptr <= this->ptr.end()); Chris@63: return intervalLength(this->ptr.begin(), ptr, MAX_SEGMENT_WORDS); Chris@63: } Chris@63: inline SegmentWordCount SegmentReader::getSize() { Chris@63: return assumeBits(ptr.size()) * WORDS; Chris@63: } Chris@63: inline kj::ArrayPtr SegmentReader::getArray() { return ptr; } Chris@63: inline void SegmentReader::unread(WordCount64 amount) { readLimiter->unread(amount); } Chris@63: Chris@63: // ------------------------------------------------------------------- Chris@63: Chris@63: inline SegmentBuilder::SegmentBuilder( Chris@63: BuilderArena* arena, SegmentId id, word* ptr, SegmentWordCount size, Chris@63: ReadLimiter* readLimiter, SegmentWordCount wordsUsed) Chris@63: : SegmentReader(arena, id, ptr, size, readLimiter), Chris@63: pos(ptr + wordsUsed), readOnly(false) {} Chris@63: inline SegmentBuilder::SegmentBuilder( Chris@63: BuilderArena* arena, SegmentId id, const word* ptr, SegmentWordCount size, Chris@63: ReadLimiter* readLimiter) Chris@63: : SegmentReader(arena, id, ptr, size, readLimiter), Chris@63: // const_cast is safe here because the member won't ever be dereferenced because it appears Chris@63: // to point to the end of the segment anyway. Chris@63: pos(const_cast(ptr + size)), readOnly(true) {} Chris@63: inline SegmentBuilder::SegmentBuilder(BuilderArena* arena, SegmentId id, decltype(nullptr), Chris@63: ReadLimiter* readLimiter) Chris@63: : SegmentReader(arena, id, nullptr, ZERO * WORDS, readLimiter), Chris@63: pos(nullptr), readOnly(false) {} Chris@63: Chris@63: inline word* SegmentBuilder::allocate(SegmentWordCount amount) { Chris@63: if (intervalLength(pos, ptr.end(), MAX_SEGMENT_WORDS) < amount) { Chris@63: // Not enough space in the segment for this allocation. Chris@63: return nullptr; Chris@63: } else { Chris@63: // Success. Chris@63: word* result = pos; Chris@63: pos = pos + amount; Chris@63: return result; Chris@63: } Chris@63: } Chris@63: Chris@63: inline void SegmentBuilder::checkWritable() { Chris@63: if (KJ_UNLIKELY(readOnly)) throwNotWritable(); Chris@63: } Chris@63: Chris@63: inline word* SegmentBuilder::getPtrUnchecked(SegmentWordCount offset) { Chris@63: return const_cast(ptr.begin() + offset); Chris@63: } Chris@63: Chris@63: inline BuilderArena* SegmentBuilder::getArena() { Chris@63: // Down-cast safe because SegmentBuilder's constructor always initializes its SegmentReader base Chris@63: // class with an Arena pointer that actually points to a BuilderArena. Chris@63: return static_cast(arena); Chris@63: } Chris@63: Chris@63: inline kj::ArrayPtr SegmentBuilder::currentlyAllocated() { Chris@63: return kj::arrayPtr(ptr.begin(), pos - ptr.begin()); Chris@63: } Chris@63: Chris@63: inline void SegmentBuilder::reset() { Chris@63: word* start = getPtrUnchecked(ZERO * WORDS); Chris@63: memset(start, 0, (pos - start) * sizeof(word)); Chris@63: pos = start; Chris@63: } Chris@63: Chris@63: inline void SegmentBuilder::tryTruncate(word* from, word* to) { Chris@63: if (pos == from) pos = to; Chris@63: } Chris@63: Chris@63: inline bool SegmentBuilder::tryExtend(word* from, word* to) { Chris@63: // Careful about overflow. Chris@63: if (pos == from && to <= ptr.end() && to >= from) { Chris@63: pos = to; Chris@63: return true; Chris@63: } else { Chris@63: return false; Chris@63: } Chris@63: } Chris@63: Chris@63: } // namespace _ (private) Chris@63: } // namespace capnp Chris@63: Chris@63: #endif // CAPNP_ARENA_H_