arena.h 19.5 KB
Newer Older
Kenton Varda's avatar
Kenton Varda committed
1 2
// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
// Licensed under the MIT License:
3
//
Kenton Varda's avatar
Kenton Varda committed
4 5 6 7 8 9
// 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:
10
//
Kenton Varda's avatar
Kenton Varda committed
11 12
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
13
//
Kenton Varda's avatar
Kenton Varda committed
14 15 16 17 18 19 20
// 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.
21

22
#pragma once
23

24
#if defined(__GNUC__) && !defined(CAPNP_HEADER_WARNINGS)
25 26 27
#pragma GCC system_header
#endif

Kenton Varda's avatar
Kenton Varda committed
28
#ifndef CAPNP_PRIVATE
29 30
#error "This header is only meant to be included by Cap'n Proto's own source code."
#endif
31

Kenton Varda's avatar
Kenton Varda committed
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

46
namespace capnp {
47

48
#if !CAPNP_LITE
49
class ClientHook;
50
#endif  // !CAPNP_LITE
51

52
namespace _ {  // private
53 54 55 56 57 58 59

class SegmentReader;
class SegmentBuilder;
class Arena;
class BuilderArena;
class ReadLimiter;

Kenton Varda's avatar
Kenton Varda committed
60
class Segment;
61
typedef kj::Id<uint32_t, Segment> SegmentId;
Kenton Varda's avatar
Kenton Varda committed
62

63 64 65 66 67 68 69 70 71 72 73 74 75 76
class ReadLimiter {
  // Used to keep track of how much data has been processed from a message, and cut off further
  // processing if and when a particular limit is reached.  This is primarily intended to guard
  // against maliciously-crafted messages which contain cycles or overlapping structures.  Cycles
  // and overlapping are not permitted by the Cap'n Proto format because in many cases they could
  // be used to craft a deceptively small message which could consume excessive server resources to
  // process, perhaps even sending it into an infinite loop.  Actually detecting overlaps would be
  // time-consuming, so instead we just keep track of how many words worth of data structures the
  // receiver has actually dereferenced and error out if this gets too high.
  //
  // This counting takes place as you call getters (for non-primitive values) on the message
  // readers.  If you call the same getter twice, the data it returns may be double-counted.  This
  // should not be a big deal in most cases -- just set the read limit high enough that it will
  // only trigger in unreasonable cases.
77 78 79 80
  //
  // This class is "safe" to use from multiple threads for its intended use case.  Threads may
  // overwrite each others' changes to the counter, but this is OK because it only means that the
  // limit is enforced a bit less strictly -- it will still kick in eventually.
81 82 83 84 85

public:
  inline explicit ReadLimiter();                     // No limit.
  inline explicit ReadLimiter(WordCount64 limit);    // Limit to the given number of words.

86 87
  inline void reset(WordCount64 limit);

88
  KJ_ALWAYS_INLINE(bool canRead(WordCount64 amount, Arena* arena));
89

90 91 92 93
  void unread(WordCount64 amount);
  // Adds back some words to the limit.  Useful when the caller knows they are double-reading
  // some data.

94
private:
95 96 97 98
  volatile uint64_t limit;
  // Current limit, decremented each time catRead() is called.  Volatile because multiple threads
  // could be trying to modify it at once.  (This is not real thread-safety, but good enough for
  // the purpose of this class.  See class comment.)
99

100
  KJ_DISALLOW_COPY(ReadLimiter);
101 102
};

103
#if !CAPNP_LITE
104 105 106 107 108 109
class BrokenCapFactory {
  // Callback for constructing broken caps.  We use this so that we can avoid arena.c++ having a
  // link-time dependency on capability code that lives in libcapnp-rpc.

public:
  virtual kj::Own<ClientHook> newBrokenCap(kj::StringPtr description) = 0;
110
  virtual kj::Own<ClientHook> newNullCap() = 0;
111
};
112
#endif  // !CAPNP_LITE
113

114 115
class SegmentReader {
public:
116
  inline SegmentReader(Arena* arena, SegmentId id, const word* ptr, SegmentWordCount size,
117 118
                       ReadLimiter* readLimiter);

119 120 121 122 123 124 125 126 127 128 129 130 131 132
  KJ_ALWAYS_INLINE(const word* checkOffset(const word* from, ptrdiff_t offset));
  // Adds the given offset to the given pointer, checks that it is still within the bounds of the
  // segment, then returns it. Note that the "end" pointer of the segment (which technically points
  // to the word after the last in the segment) is considered in-bounds for this purpose, so you
  // can't necessarily dereference it. You must call checkObject() next to check that the object
  // you want to read is entirely in-bounds.
  //
  // If `from + offset` is out-of-range, this returns a pointer to the end of the segment. Thus,
  // any non-zero-sized object will fail `checkObject()`. We do this instead of throwing to save
  // some code footprint.

  KJ_ALWAYS_INLINE(bool checkObject(const word* start, WordCountN<31> size));
  // Assuming that `start` is in-bounds for this segment (probably checked using `checkOffset()`),
  // check that `start + size` is also in-bounds, and hence the whole area in-between is valid.
133

134 135 136 137 138
  KJ_ALWAYS_INLINE(bool amplifiedRead(WordCount virtualAmount));
  // Indicates that the reader should pretend that `virtualAmount` additional data was read even
  // though no actual pointer was traversed. This is used e.g. when reading a struct list pointer
  // where the element sizes are zero -- the sender could set the list size arbitrarily high and
  // cause the receiver to iterate over this list even though the message itself is small, so we
Andrew Murray's avatar
Andrew Murray committed
139
  // need to defend against DoS attacks based on this.
140

141 142 143 144
  inline Arena* getArena();
  inline SegmentId getSegmentId();

  inline const word* getStartPtr();
145 146
  inline SegmentWordCount getOffsetTo(const word* ptr);
  inline SegmentWordCount getSize();
147

148
  inline kj::ArrayPtr<const word> getArray();
149

150 151 152
  inline void unread(WordCount64 amount);
  // Add back some words to the ReadLimiter.

153 154 155
private:
  Arena* arena;
  SegmentId id;
156
  kj::ArrayPtr<const word> ptr;  // size guaranteed to fit in SEGMENT_WORD_COUNT_BITS bits
157 158
  ReadLimiter* readLimiter;

159
  KJ_DISALLOW_COPY(SegmentReader);
160 161

  friend class SegmentBuilder;
162 163 164

  static void abortCheckObjectFault();
  // Called in debug mode in cases that would segfault in opt mode. (Should be impossible!)
165 166 167 168
};

class SegmentBuilder: public SegmentReader {
public:
169 170 171
  inline SegmentBuilder(BuilderArena* arena, SegmentId id, word* ptr, SegmentWordCount size,
                        ReadLimiter* readLimiter, SegmentWordCount wordsUsed = ZERO * WORDS);
  inline SegmentBuilder(BuilderArena* arena, SegmentId id, const word* ptr, SegmentWordCount size,
172 173 174
                        ReadLimiter* readLimiter);
  inline SegmentBuilder(BuilderArena* arena, SegmentId id, decltype(nullptr),
                        ReadLimiter* readLimiter);
175

176
  KJ_ALWAYS_INLINE(word* allocate(SegmentWordCount amount));
177 178 179 180

  KJ_ALWAYS_INLINE(void checkWritable());
  // Throw an exception if the segment is read-only (meaning it is a reference to external data).

181
  KJ_ALWAYS_INLINE(word* getPtrUnchecked(SegmentWordCount offset));
182 183
  // Get a writable pointer into the segment.  Throws an exception if the segment is read-only (i.e.
  // a reference to external immutable data).
184 185 186

  inline BuilderArena* getArena();

187
  inline kj::ArrayPtr<const word> currentlyAllocated();
188

189 190
  inline void reset();

191 192
  inline bool isWritable() { return !readOnly; }

193 194 195 196
  inline void tryTruncate(word* from, word* to);
  // If `from` points just past the current end of the segment, then move the end back to `to`.
  // Otherwise, do nothing.

197 198 199 200 201
  inline bool tryExtend(word* from, word* to);
  // If `from` points just past the current end of the segment, and `to` is within the segment
  // boundaries, then move the end up to `to` and return true. Otherwise, do nothing and return
  // false.

202
private:
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 208 209 210
  bool readOnly;

  void throwNotWritable();

211
  KJ_DISALLOW_COPY(SegmentBuilder);
212 213
};

214 215
class Arena {
public:
216
  virtual ~Arena() noexcept(false);
217 218 219 220 221

  virtual SegmentReader* tryGetSegment(SegmentId id) = 0;
  // Gets the segment with the given ID, or return nullptr if no such segment exists.

  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
};

227
class ReaderArena final: public Arena {
228
public:
229
  explicit ReaderArena(MessageReader* message);
230 231 232
  ~ReaderArena() noexcept(false);
  KJ_DISALLOW_COPY(ReaderArena);

233 234
  size_t sizeInWords();

235 236 237 238 239
  // implements Arena ------------------------------------------------
  SegmentReader* tryGetSegment(SegmentId id) override;
  void reportReadLimitReached() override;

private:
240
  MessageReader* message;
241
  ReadLimiter readLimiter;
242 243 244 245

  // Optimize for single-segment messages so that small messages are handled quickly.
  SegmentReader segment0;

246 247
  typedef kj::HashMap<uint, kj::Own<SegmentReader>> SegmentMap;
  kj::MutexGuarded<kj::Maybe<SegmentMap>> moreSegments;
248 249 250 251 252 253 254
  // We need to mutex-guard the segment map because we lazily initialize segments when they are
  // first requested, but a Reader is allowed to be used concurrently in multiple threads.  Luckily
  // this only applies to large messages.
  //
  // TODO(perf):  Thread-local thing instead?  Some kind of lockless map?  Or do sharing of data
  //   in a different way, where you have to construct a new MessageReader in each thread (but
  //   possibly backed by the same data)?
255 256 257

  ReaderArena(MessageReader* message, kj::ArrayPtr<const word> firstSegment);
  ReaderArena(MessageReader* message, const word* firstSegment, SegmentWordCount firstSegmentSize);
258 259
};

260 261
class BuilderArena final: public Arena {
  // A BuilderArena that does not allow the injection of capabilities.
262

263
public:
264 265
  explicit BuilderArena(MessageBuilder* message);
  BuilderArena(MessageBuilder* message, kj::ArrayPtr<MessageBuilder::SegmentInit> segments);
266 267
  ~BuilderArena() noexcept(false);
  KJ_DISALLOW_COPY(BuilderArena);
268

269 270
  size_t sizeInWords();

271
  inline SegmentBuilder* getRootSegment() { return &segment0; }
272

273 274 275 276
  kj::ArrayPtr<const kj::ArrayPtr<const word>> getSegmentsForOutput();
  // Get an array of all the segments, suitable for writing out.  This only returns the allocated
  // portion of each segment, whereas tryGetSegment() returns something that includes
  // not-yet-allocated space.
277

278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
  inline CapTableBuilder* getLocalCapTable() {
    // Return a CapTableBuilder that merely implements local loopback. That is, you can set
    // capabilities, then read the same capabilities back, but there is no intent ever to transmit
    // these capabilities. A MessageBuilder that isn't imbued with some other CapTable uses this
    // by default.
    //
    // TODO(cleanup): It's sort of a hack that this exists. In theory, perhaps, unimbued
    //   MessageBuilders should throw exceptions on any attempt to access capability fields, like
    //   unimbued MessageReaders do. However, lots of code exists which uses MallocMessageBuilder
    //   as a temporary holder for data to be copied in and out (without being serialized), and it
    //   is expected that such data can include capabilities, which is admittedly reasonable.
    //   Therefore, all MessageBuilders must have a cap table by default. Arguably we should
    //   deprecate this usage and instead define a new helper type for this exact purpose.

    return &localCapTable;
  }
294

295 296 297 298
  kj::Own<_::CapTableBuilder> releaseLocalCapTable() {
    return kj::heap<LocalCapTable>(kj::mv(localCapTable));
  }

299
  SegmentBuilder* getSegment(SegmentId id);
300 301
  // Get the segment with the given id.  Crashes or throws an exception if no such segment exists.

302 303 304 305 306
  struct AllocateResult {
    SegmentBuilder* segment;
    word* words;
  };

307
  AllocateResult allocate(SegmentWordCount amount);
308 309 310 311
  // Find a segment with at least the given amount of space available and allocate the space.
  // Note that allocating directly from a particular segment is much faster, but allocating from
  // the arena is guaranteed to succeed.  Therefore callers should try to allocate from a specific
  // segment first if there is one, then fall back to the arena.
312

313 314 315 316 317 318 319 320 321 322 323
  SegmentBuilder* addExternalSegment(kj::ArrayPtr<const word> content);
  // Add a new segment to the arena which points to some existing memory region.  The segment is
  // assumed to be completley full; the arena will never allocate from it.  In fact, the segment
  // is considered read-only.  Any attempt to get a Builder pointing into this segment will throw
  // an exception.  Readers are allowed, however.
  //
  // This can be used to inject some external data into a message without a copy, e.g. embedding a
  // large mmap'd file into a message as `Data` without forcing that data to actually be read in
  // from disk (until the message itself is written out).  `Orphanage` provides the public API for
  // this feature.

324 325 326 327 328
  // implements Arena ------------------------------------------------
  SegmentReader* tryGetSegment(SegmentId id) override;
  void reportReadLimitReached() override;

private:
329
  MessageBuilder* message;
330
  ReadLimiter dummyLimiter;
331

Kenton Varda's avatar
Kenton Varda committed
332
  class LocalCapTable final: public CapTableBuilder {
333
#if !CAPNP_LITE
334 335 336 337 338 339 340
  public:
    kj::Maybe<kj::Own<ClientHook>> extractCap(uint index) override;
    uint injectCap(kj::Own<ClientHook>&& cap) override;
    void dropCap(uint index) override;

  private:
    kj::Vector<kj::Maybe<kj::Own<ClientHook>>> capTable;
341
#endif // ! CAPNP_LITE
342 343 344
  };

  LocalCapTable localCapTable;
345

346
  SegmentBuilder segment0;
347
  kj::ArrayPtr<const word> segment0ForOutput;
348

349
  struct MultiSegmentState {
350
    kj::Vector<kj::Own<SegmentBuilder>> builders;
351
    kj::Vector<kj::ArrayPtr<const word>> forOutput;
352
  };
353
  kj::Maybe<kj::Own<MultiSegmentState>> moreSegments;
354 355 356 357 358 359 360 361

  SegmentBuilder* segmentWithSpace = nullptr;
  // When allocating, look for space in this segment first before resorting to allocating a new
  // segment.  This is not necessarily the last segment because addExternalSegment() may add a
  // segment that is already-full, in which case we don't update this pointer.

  template <typename T>  // Can be `word` or `const word`.
  SegmentBuilder* addSegmentInternal(kj::ArrayPtr<T> content);
362 363 364 365 366
};

// =======================================================================================

inline ReadLimiter::ReadLimiter()
367
    : limit(kj::maxValue) {}
368

369
inline ReadLimiter::ReadLimiter(WordCount64 limit): limit(unbound(limit / WORDS)) {}
370

371
inline void ReadLimiter::reset(WordCount64 limit) { this->limit = unbound(limit / WORDS); }
372

373
inline bool ReadLimiter::canRead(WordCount64 amount, Arena* arena) {
374 375 376
  // Be careful not to store an underflowed value into `limit`, even if multiple threads are
  // decrementing it.
  uint64_t current = limit;
377
  if (KJ_UNLIKELY(unbound(amount / WORDS) > current)) {
378 379 380
    arena->reportReadLimitReached();
    return false;
  } else {
381
    limit = current - unbound(amount / WORDS);
382 383 384 385 386 387
    return true;
  }
}

// -------------------------------------------------------------------

388 389
inline SegmentReader::SegmentReader(Arena* arena, SegmentId id, const word* ptr,
                                    SegmentWordCount size, ReadLimiter* readLimiter)
390
    : arena(arena), id(id), ptr(kj::arrayPtr(ptr, unbound(size / WORDS))),
391
      readLimiter(readLimiter) {}
392

393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411
inline const word* SegmentReader::checkOffset(const word* from, ptrdiff_t offset) {
  ptrdiff_t min = ptr.begin() - from;
  ptrdiff_t max = ptr.end() - from;
  if (offset >= min && offset <= max) {
    return from + offset;
  } else {
    return ptr.end();
  }
}

inline bool SegmentReader::checkObject(const word* start, WordCountN<31> size) {
  auto startOffset = intervalLength(ptr.begin(), start, MAX_SEGMENT_WORDS);
#ifdef KJ_DEBUG
  if (startOffset > bounded(ptr.size()) * WORDS) {
    abortCheckObjectFault();
  }
#endif
  return startOffset + size <= bounded(ptr.size()) * WORDS &&
      readLimiter->canRead(size, arena);
412 413
}

414 415 416 417
inline bool SegmentReader::amplifiedRead(WordCount virtualAmount) {
  return readLimiter->canRead(virtualAmount, arena);
}

418 419 420
inline Arena* SegmentReader::getArena() { return arena; }
inline SegmentId SegmentReader::getSegmentId() { return id; }
inline const word* SegmentReader::getStartPtr() { return ptr.begin(); }
421
inline SegmentWordCount SegmentReader::getOffsetTo(const word* ptr) {
422 423
  KJ_IREQUIRE(this->ptr.begin() <= ptr && ptr <= this->ptr.end());
  return intervalLength(this->ptr.begin(), ptr, MAX_SEGMENT_WORDS);
424 425 426
}
inline SegmentWordCount SegmentReader::getSize() {
  return assumeBits<SEGMENT_WORD_COUNT_BITS>(ptr.size()) * WORDS;
427
}
428
inline kj::ArrayPtr<const word> SegmentReader::getArray() { return ptr; }
429
inline void SegmentReader::unread(WordCount64 amount) { readLimiter->unread(amount); }
430 431 432 433

// -------------------------------------------------------------------

inline SegmentBuilder::SegmentBuilder(
434 435 436 437
    BuilderArena* arena, SegmentId id, word* ptr, SegmentWordCount size,
    ReadLimiter* readLimiter, SegmentWordCount wordsUsed)
    : SegmentReader(arena, id, ptr, size, readLimiter),
      pos(ptr + wordsUsed), readOnly(false) {}
438
inline SegmentBuilder::SegmentBuilder(
439 440 441
    BuilderArena* arena, SegmentId id, const word* ptr, SegmentWordCount size,
    ReadLimiter* readLimiter)
    : SegmentReader(arena, id, ptr, size, readLimiter),
442 443
      // const_cast is safe here because the member won't ever be dereferenced because it appears
      // to point to the end of the segment anyway.
444
      pos(const_cast<word*>(ptr + size)), readOnly(true) {}
445 446
inline SegmentBuilder::SegmentBuilder(BuilderArena* arena, SegmentId id, decltype(nullptr),
                                      ReadLimiter* readLimiter)
447 448
    : SegmentReader(arena, id, nullptr, ZERO * WORDS, readLimiter),
      pos(nullptr), readOnly(false) {}
449

450
inline word* SegmentBuilder::allocate(SegmentWordCount amount) {
451
  if (intervalLength(pos, ptr.end(), MAX_SEGMENT_WORDS) < amount) {
452
    // Not enough space in the segment for this allocation.
453 454
    return nullptr;
  } else {
455
    // Success.
456 457
    word* result = pos;
    pos = pos + amount;
458 459 460 461
    return result;
  }
}

462 463 464 465
inline void SegmentBuilder::checkWritable() {
  if (KJ_UNLIKELY(readOnly)) throwNotWritable();
}

466
inline word* SegmentBuilder::getPtrUnchecked(SegmentWordCount offset) {
467 468 469 470 471 472 473 474 475
  return const_cast<word*>(ptr.begin() + offset);
}

inline BuilderArena* SegmentBuilder::getArena() {
  // Down-cast safe because SegmentBuilder's constructor always initializes its SegmentReader base
  // class with an Arena pointer that actually points to a BuilderArena.
  return static_cast<BuilderArena*>(arena);
}

476
inline kj::ArrayPtr<const word> SegmentBuilder::currentlyAllocated() {
477
  return kj::arrayPtr(ptr.begin(), pos - ptr.begin());
478 479
}

480
inline void SegmentBuilder::reset() {
481
  word* start = getPtrUnchecked(ZERO * WORDS);
482 483
  memset(start, 0, (pos - start) * sizeof(word));
  pos = start;
484 485
}

486 487 488 489
inline void SegmentBuilder::tryTruncate(word* from, word* to) {
  if (pos == from) pos = to;
}

490 491 492 493 494 495 496 497 498 499
inline bool SegmentBuilder::tryExtend(word* from, word* to) {
  // Careful about overflow.
  if (pos == from && to <= ptr.end() && to >= from) {
    pos = to;
    return true;
  } else {
    return false;
  }
}

500
}  // namespace _ (private)
501
}  // namespace capnp