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