1// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22#pragma once
23
24#if defined(__GNUC__) && !defined(CAPNP_HEADER_WARNINGS)
25#pragma GCC system_header
26#endif
27
28#ifndef CAPNP_PRIVATE
29#error "This header is only meant to be included by Cap'n Proto's own source code."
30#endif
31
32#include <kj/common.h>
33#include <kj/mutex.h>
34#include <kj/exception.h>
35#include <kj/vector.h>
36#include <kj/units.h>
37#include "common.h"
38#include "message.h"
39#include "layout.h"
40#include <kj/map.h>
41
42#if !CAPNP_LITE
43#include "capability.h"
44#endif // !CAPNP_LITE
45
46namespace capnp {
47
48#if !CAPNP_LITE
49class ClientHook;
50#endif // !CAPNP_LITE
51
52namespace _ { // private
53
54class SegmentReader;
55class SegmentBuilder;
56class Arena;
57class BuilderArena;
58class ReadLimiter;
59
60class Segment;
61typedef kj::Id<uint32_t, Segment> SegmentId;
62
63class ReadLimiter {
64 // Used to keep track of how much data has been processed from a message, and cut off further
65 // processing if and when a particular limit is reached. This is primarily intended to guard
66 // against maliciously-crafted messages which contain cycles or overlapping structures. Cycles
67 // and overlapping are not permitted by the Cap'n Proto format because in many cases they could
68 // be used to craft a deceptively small message which could consume excessive server resources to
69 // process, perhaps even sending it into an infinite loop. Actually detecting overlaps would be
70 // time-consuming, so instead we just keep track of how many words worth of data structures the
71 // receiver has actually dereferenced and error out if this gets too high.
72 //
73 // This counting takes place as you call getters (for non-primitive values) on the message
74 // readers. If you call the same getter twice, the data it returns may be double-counted. This
75 // should not be a big deal in most cases -- just set the read limit high enough that it will
76 // only trigger in unreasonable cases.
77 //
78 // This class is "safe" to use from multiple threads for its intended use case. Threads may
79 // overwrite each others' changes to the counter, but this is OK because it only means that the
80 // limit is enforced a bit less strictly -- it will still kick in eventually.
81
82public:
83 inline explicit ReadLimiter(); // No limit.
84 inline explicit ReadLimiter(WordCount64 limit); // Limit to the given number of words.
85
86 inline void reset(WordCount64 limit);
87
88 KJ_ALWAYS_INLINE(bool canRead(WordCount64 amount, Arena* arena));
89
90 void unread(WordCount64 amount);
91 // Adds back some words to the limit. Useful when the caller knows they are double-reading
92 // some data.
93
94private:
95 volatile uint64_t limit;
96 // Current limit, decremented each time catRead() is called. Volatile because multiple threads
97 // could be trying to modify it at once. (This is not real thread-safety, but good enough for
98 // the purpose of this class. See class comment.)
99
100 KJ_DISALLOW_COPY(ReadLimiter);
101};
102
103#if !CAPNP_LITE
104class BrokenCapFactory {
105 // Callback for constructing broken caps. We use this so that we can avoid arena.c++ having a
106 // link-time dependency on capability code that lives in libcapnp-rpc.
107
108public:
109 virtual kj::Own<ClientHook> newBrokenCap(kj::StringPtr description) = 0;
110 virtual kj::Own<ClientHook> newNullCap() = 0;
111};
112#endif // !CAPNP_LITE
113
114class SegmentReader {
115public:
116 inline SegmentReader(Arena* arena, SegmentId id, const word* ptr, SegmentWordCount size,
117 ReadLimiter* readLimiter);
118
119 KJ_ALWAYS_INLINE(const word* checkOffset(const word* from, ptrdiff_t offset));
120 // Adds the given offset to the given pointer, checks that it is still within the bounds of the
121 // segment, then returns it. Note that the "end" pointer of the segment (which technically points
122 // to the word after the last in the segment) is considered in-bounds for this purpose, so you
123 // can't necessarily dereference it. You must call checkObject() next to check that the object
124 // you want to read is entirely in-bounds.
125 //
126 // If `from + offset` is out-of-range, this returns a pointer to the end of the segment. Thus,
127 // any non-zero-sized object will fail `checkObject()`. We do this instead of throwing to save
128 // some code footprint.
129
130 KJ_ALWAYS_INLINE(bool checkObject(const word* start, WordCountN<31> size));
131 // Assuming that `start` is in-bounds for this segment (probably checked using `checkOffset()`),
132 // check that `start + size` is also in-bounds, and hence the whole area in-between is valid.
133
134 KJ_ALWAYS_INLINE(bool amplifiedRead(WordCount virtualAmount));
135 // Indicates that the reader should pretend that `virtualAmount` additional data was read even
136 // though no actual pointer was traversed. This is used e.g. when reading a struct list pointer
137 // where the element sizes are zero -- the sender could set the list size arbitrarily high and
138 // cause the receiver to iterate over this list even though the message itself is small, so we
139 // need to defend against DoS attacks based on this.
140
141 inline Arena* getArena();
142 inline SegmentId getSegmentId();
143
144 inline const word* getStartPtr();
145 inline SegmentWordCount getOffsetTo(const word* ptr);
146 inline SegmentWordCount getSize();
147
148 inline kj::ArrayPtr<const word> getArray();
149
150 inline void unread(WordCount64 amount);
151 // Add back some words to the ReadLimiter.
152
153private:
154 Arena* arena;
155 SegmentId id;
156 kj::ArrayPtr<const word> ptr; // size guaranteed to fit in SEGMENT_WORD_COUNT_BITS bits
157 ReadLimiter* readLimiter;
158
159 KJ_DISALLOW_COPY(SegmentReader);
160
161 friend class SegmentBuilder;
162
163 static void abortCheckObjectFault();
164 // Called in debug mode in cases that would segfault in opt mode. (Should be impossible!)
165};
166
167class SegmentBuilder: public SegmentReader {
168public:
169 inline SegmentBuilder(BuilderArena* arena, SegmentId id, word* ptr, SegmentWordCount size,
170 ReadLimiter* readLimiter, SegmentWordCount wordsUsed = ZERO * WORDS);
171 inline SegmentBuilder(BuilderArena* arena, SegmentId id, const word* ptr, SegmentWordCount size,
172 ReadLimiter* readLimiter);
173 inline SegmentBuilder(BuilderArena* arena, SegmentId id, decltype(nullptr),
174 ReadLimiter* readLimiter);
175
176 KJ_ALWAYS_INLINE(word* allocate(SegmentWordCount amount));
177
178 KJ_ALWAYS_INLINE(void checkWritable());
179 // Throw an exception if the segment is read-only (meaning it is a reference to external data).
180
181 KJ_ALWAYS_INLINE(word* getPtrUnchecked(SegmentWordCount offset));
182 // Get a writable pointer into the segment. Throws an exception if the segment is read-only (i.e.
183 // a reference to external immutable data).
184
185 inline BuilderArena* getArena();
186
187 inline kj::ArrayPtr<const word> currentlyAllocated();
188
189 inline void reset();
190
191 inline bool isWritable() { return !readOnly; }
192
193 inline void tryTruncate(word* from, word* to);
194 // If `from` points just past the current end of the segment, then move the end back to `to`.
195 // Otherwise, do nothing.
196
197 inline bool tryExtend(word* from, word* to);
198 // If `from` points just past the current end of the segment, and `to` is within the segment
199 // boundaries, then move the end up to `to` and return true. Otherwise, do nothing and return
200 // false.
201
202private:
203 word* pos;
204 // Pointer to a pointer to the current end point of the segment, i.e. the location where the
205 // next object should be allocated.
206
207 bool readOnly;
208
209 void throwNotWritable();
210
211 KJ_DISALLOW_COPY(SegmentBuilder);
212};
213
214class Arena {
215public:
216 virtual ~Arena() noexcept(false);
217
218 virtual SegmentReader* tryGetSegment(SegmentId id) = 0;
219 // Gets the segment with the given ID, or return nullptr if no such segment exists.
220
221 virtual void reportReadLimitReached() = 0;
222 // Called to report that the read limit has been reached. See ReadLimiter, below. This invokes
223 // the VALIDATE_INPUT() macro which may throw an exception; if it returns normally, the caller
224 // will need to continue with default values.
225};
226
227class ReaderArena final: public Arena {
228public:
229 explicit ReaderArena(MessageReader* message);
230 ~ReaderArena() noexcept(false);
231 KJ_DISALLOW_COPY(ReaderArena);
232
233 // implements Arena ------------------------------------------------
234 SegmentReader* tryGetSegment(SegmentId id) override;
235 void reportReadLimitReached() override;
236
237private:
238 MessageReader* message;
239 ReadLimiter readLimiter;
240
241 // Optimize for single-segment messages so that small messages are handled quickly.
242 SegmentReader segment0;
243
244 typedef kj::HashMap<uint, kj::Own<SegmentReader>> SegmentMap;
245 kj::MutexGuarded<kj::Maybe<SegmentMap>> moreSegments;
246 // We need to mutex-guard the segment map because we lazily initialize segments when they are
247 // first requested, but a Reader is allowed to be used concurrently in multiple threads. Luckily
248 // this only applies to large messages.
249 //
250 // TODO(perf): Thread-local thing instead? Some kind of lockless map? Or do sharing of data
251 // in a different way, where you have to construct a new MessageReader in each thread (but
252 // possibly backed by the same data)?
253
254 ReaderArena(MessageReader* message, kj::ArrayPtr<const word> firstSegment);
255 ReaderArena(MessageReader* message, const word* firstSegment, SegmentWordCount firstSegmentSize);
256};
257
258class BuilderArena final: public Arena {
259 // A BuilderArena that does not allow the injection of capabilities.
260
261public:
262 explicit BuilderArena(MessageBuilder* message);
263 BuilderArena(MessageBuilder* message, kj::ArrayPtr<MessageBuilder::SegmentInit> segments);
264 ~BuilderArena() noexcept(false);
265 KJ_DISALLOW_COPY(BuilderArena);
266
267 inline SegmentBuilder* getRootSegment() { return &segment0; }
268
269 kj::ArrayPtr<const kj::ArrayPtr<const word>> getSegmentsForOutput();
270 // Get an array of all the segments, suitable for writing out. This only returns the allocated
271 // portion of each segment, whereas tryGetSegment() returns something that includes
272 // not-yet-allocated space.
273
274 inline CapTableBuilder* getLocalCapTable() {
275 // Return a CapTableBuilder that merely implements local loopback. That is, you can set
276 // capabilities, then read the same capabilities back, but there is no intent ever to transmit
277 // these capabilities. A MessageBuilder that isn't imbued with some other CapTable uses this
278 // by default.
279 //
280 // TODO(cleanup): It's sort of a hack that this exists. In theory, perhaps, unimbued
281 // MessageBuilders should throw exceptions on any attempt to access capability fields, like
282 // unimbued MessageReaders do. However, lots of code exists which uses MallocMessageBuilder
283 // as a temporary holder for data to be copied in and out (without being serialized), and it
284 // is expected that such data can include capabilities, which is admittedly reasonable.
285 // Therefore, all MessageBuilders must have a cap table by default. Arguably we should
286 // deprecate this usage and instead define a new helper type for this exact purpose.
287
288 return &localCapTable;
289 }
290
291 SegmentBuilder* getSegment(SegmentId id);
292 // Get the segment with the given id. Crashes or throws an exception if no such segment exists.
293
294 struct AllocateResult {
295 SegmentBuilder* segment;
296 word* words;
297 };
298
299 AllocateResult allocate(SegmentWordCount amount);
300 // Find a segment with at least the given amount of space available and allocate the space.
301 // Note that allocating directly from a particular segment is much faster, but allocating from
302 // the arena is guaranteed to succeed. Therefore callers should try to allocate from a specific
303 // segment first if there is one, then fall back to the arena.
304
305 SegmentBuilder* addExternalSegment(kj::ArrayPtr<const word> content);
306 // Add a new segment to the arena which points to some existing memory region. The segment is
307 // assumed to be completley full; the arena will never allocate from it. In fact, the segment
308 // is considered read-only. Any attempt to get a Builder pointing into this segment will throw
309 // an exception. Readers are allowed, however.
310 //
311 // This can be used to inject some external data into a message without a copy, e.g. embedding a
312 // large mmap'd file into a message as `Data` without forcing that data to actually be read in
313 // from disk (until the message itself is written out). `Orphanage` provides the public API for
314 // this feature.
315
316 // implements Arena ------------------------------------------------
317 SegmentReader* tryGetSegment(SegmentId id) override;
318 void reportReadLimitReached() override;
319
320private:
321 MessageBuilder* message;
322 ReadLimiter dummyLimiter;
323
324 class LocalCapTable: public CapTableBuilder {
325#if !CAPNP_LITE
326 public:
327 kj::Maybe<kj::Own<ClientHook>> extractCap(uint index) override;
328 uint injectCap(kj::Own<ClientHook>&& cap) override;
329 void dropCap(uint index) override;
330
331 private:
332 kj::Vector<kj::Maybe<kj::Own<ClientHook>>> capTable;
333#endif // ! CAPNP_LITE
334 };
335
336 LocalCapTable localCapTable;
337
338 SegmentBuilder segment0;
339 kj::ArrayPtr<const word> segment0ForOutput;
340
341 struct MultiSegmentState {
342 kj::Vector<kj::Own<SegmentBuilder>> builders;
343 kj::Vector<kj::ArrayPtr<const word>> forOutput;
344 };
345 kj::Maybe<kj::Own<MultiSegmentState>> moreSegments;
346
347 SegmentBuilder* segmentWithSpace = nullptr;
348 // When allocating, look for space in this segment first before resorting to allocating a new
349 // segment. This is not necessarily the last segment because addExternalSegment() may add a
350 // segment that is already-full, in which case we don't update this pointer.
351
352 template <typename T> // Can be `word` or `const word`.
353 SegmentBuilder* addSegmentInternal(kj::ArrayPtr<T> content);
354};
355
356// =======================================================================================
357
358inline ReadLimiter::ReadLimiter()
359 : limit(kj::maxValue) {}
360
361inline ReadLimiter::ReadLimiter(WordCount64 limit): limit(unbound(limit / WORDS)) {}
362
363inline void ReadLimiter::reset(WordCount64 limit) { this->limit = unbound(limit / WORDS); }
364
365inline bool ReadLimiter::canRead(WordCount64 amount, Arena* arena) {
366 // Be careful not to store an underflowed value into `limit`, even if multiple threads are
367 // decrementing it.
368 uint64_t current = limit;
369 if (KJ_UNLIKELY(unbound(amount / WORDS) > current)) {
370 arena->reportReadLimitReached();
371 return false;
372 } else {
373 limit = current - unbound(amount / WORDS);
374 return true;
375 }
376}
377
378// -------------------------------------------------------------------
379
380inline SegmentReader::SegmentReader(Arena* arena, SegmentId id, const word* ptr,
381 SegmentWordCount size, ReadLimiter* readLimiter)
382 : arena(arena), id(id), ptr(kj::arrayPtr(ptr, unbound(size / WORDS))),
383 readLimiter(readLimiter) {}
384
385inline const word* SegmentReader::checkOffset(const word* from, ptrdiff_t offset) {
386 ptrdiff_t min = ptr.begin() - from;
387 ptrdiff_t max = ptr.end() - from;
388 if (offset >= min && offset <= max) {
389 return from + offset;
390 } else {
391 return ptr.end();
392 }
393}
394
395inline bool SegmentReader::checkObject(const word* start, WordCountN<31> size) {
396 auto startOffset = intervalLength(ptr.begin(), start, MAX_SEGMENT_WORDS);
397#ifdef KJ_DEBUG
398 if (startOffset > bounded(ptr.size()) * WORDS) {
399 abortCheckObjectFault();
400 }
401#endif
402 return startOffset + size <= bounded(ptr.size()) * WORDS &&
403 readLimiter->canRead(size, arena);
404}
405
406inline bool SegmentReader::amplifiedRead(WordCount virtualAmount) {
407 return readLimiter->canRead(virtualAmount, arena);
408}
409
410inline Arena* SegmentReader::getArena() { return arena; }
411inline SegmentId SegmentReader::getSegmentId() { return id; }
412inline const word* SegmentReader::getStartPtr() { return ptr.begin(); }
413inline SegmentWordCount SegmentReader::getOffsetTo(const word* ptr) {
414 KJ_IREQUIRE(this->ptr.begin() <= ptr && ptr <= this->ptr.end());
415 return intervalLength(this->ptr.begin(), ptr, MAX_SEGMENT_WORDS);
416}
417inline SegmentWordCount SegmentReader::getSize() {
418 return assumeBits<SEGMENT_WORD_COUNT_BITS>(ptr.size()) * WORDS;
419}
420inline kj::ArrayPtr<const word> SegmentReader::getArray() { return ptr; }
421inline void SegmentReader::unread(WordCount64 amount) { readLimiter->unread(amount); }
422
423// -------------------------------------------------------------------
424
425inline SegmentBuilder::SegmentBuilder(
426 BuilderArena* arena, SegmentId id, word* ptr, SegmentWordCount size,
427 ReadLimiter* readLimiter, SegmentWordCount wordsUsed)
428 : SegmentReader(arena, id, ptr, size, readLimiter),
429 pos(ptr + wordsUsed), readOnly(false) {}
430inline SegmentBuilder::SegmentBuilder(
431 BuilderArena* arena, SegmentId id, const word* ptr, SegmentWordCount size,
432 ReadLimiter* readLimiter)
433 : SegmentReader(arena, id, ptr, size, readLimiter),
434 // const_cast is safe here because the member won't ever be dereferenced because it appears
435 // to point to the end of the segment anyway.
436 pos(const_cast<word*>(ptr + size)), readOnly(true) {}
437inline SegmentBuilder::SegmentBuilder(BuilderArena* arena, SegmentId id, decltype(nullptr),
438 ReadLimiter* readLimiter)
439 : SegmentReader(arena, id, nullptr, ZERO * WORDS, readLimiter),
440 pos(nullptr), readOnly(false) {}
441
442inline word* SegmentBuilder::allocate(SegmentWordCount amount) {
443 if (intervalLength(pos, ptr.end(), MAX_SEGMENT_WORDS) < amount) {
444 // Not enough space in the segment for this allocation.
445 return nullptr;
446 } else {
447 // Success.
448 word* result = pos;
449 pos = pos + amount;
450 return result;
451 }
452}
453
454inline void SegmentBuilder::checkWritable() {
455 if (KJ_UNLIKELY(readOnly)) throwNotWritable();
456}
457
458inline word* SegmentBuilder::getPtrUnchecked(SegmentWordCount offset) {
459 return const_cast<word*>(ptr.begin() + offset);
460}
461
462inline BuilderArena* SegmentBuilder::getArena() {
463 // Down-cast safe because SegmentBuilder's constructor always initializes its SegmentReader base
464 // class with an Arena pointer that actually points to a BuilderArena.
465 return static_cast<BuilderArena*>(arena);
466}
467
468inline kj::ArrayPtr<const word> SegmentBuilder::currentlyAllocated() {
469 return kj::arrayPtr(ptr.begin(), pos - ptr.begin());
470}
471
472inline void SegmentBuilder::reset() {
473 word* start = getPtrUnchecked(ZERO * WORDS);
474 memset(start, 0, (pos - start) * sizeof(word));
475 pos = start;
476}
477
478inline void SegmentBuilder::tryTruncate(word* from, word* to) {
479 if (pos == from) pos = to;
480}
481
482inline bool SegmentBuilder::tryExtend(word* from, word* to) {
483 // Careful about overflow.
484 if (pos == from && to <= ptr.end() && to >= from) {
485 pos = to;
486 return true;
487 } else {
488 return false;
489 }
490}
491
492} // namespace _ (private)
493} // namespace capnp
494