1 /* builder.h */ 2 3 4 /** 5 * Copyright (C) 2018-present MongoDB, Inc. 6 * 7 * This program is free software: you can redistribute it and/or modify 8 * it under the terms of the Server Side Public License, version 1, 9 * as published by MongoDB, Inc. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * Server Side Public License for more details. 15 * 16 * You should have received a copy of the Server Side Public License 17 * along with this program. If not, see 18 * <http://www.mongodb.com/licensing/server-side-public-license>. 19 * 20 * As a special exception, the copyright holders give permission to link the 21 * code of portions of this program with the OpenSSL library under certain 22 * conditions as described in each individual source file and distribute 23 * linked combinations including the program with the OpenSSL library. You 24 * must comply with the Server Side Public License in all respects for 25 * all of the code used other than as permitted herein. If you modify file(s) 26 * with this exception, you may extend this exception to your version of the 27 * file(s), but you are not obligated to do so. If you do not wish to do so, 28 * delete this exception statement from your version. If you delete this 29 * exception statement from all source files in the program, then also delete 30 * it in the license file. 31 */ 32 33 #pragma once 34 35 #include <cfloat> 36 #include <cinttypes> 37 #include <cstdint> 38 #include <sstream> 39 #include <stdio.h> 40 #include <string.h> 41 #include <string> 42 43 #include <boost/optional.hpp> 44 45 #include "mongo/base/data_type_endian.h" 46 #include "mongo/base/data_view.h" 47 #include "mongo/base/disallow_copying.h" 48 #include "mongo/base/static_assert.h" 49 #include "mongo/base/string_data.h" 50 #include "mongo/bson/bsontypes.h" 51 #include "mongo/bson/inline_decls.h" 52 #include "mongo/platform/decimal128.h" 53 #include "mongo/stdx/type_traits.h" 54 #include "mongo/util/allocator.h" 55 #include "mongo/util/assert_util.h" 56 #include "mongo/util/itoa.h" 57 #include "mongo/util/shared_buffer.h" 58 59 namespace mongo { 60 61 /* Note the limit here is rather arbitrary and is simply a standard. generally the code works 62 with any object that fits in ram. 63 64 Also note that the server has some basic checks to enforce this limit but those checks are not 65 exhaustive for example need to check for size too big after 66 update $push (append) operation 67 various db.eval() type operations 68 */ 69 const int BSONObjMaxUserSize = 16 * 1024 * 1024; 70 71 /* 72 Sometimes we need objects slightly larger - an object in the replication local.oplog 73 is slightly larger than a user object for example. 74 */ 75 const int BSONObjMaxInternalSize = BSONObjMaxUserSize + (16 * 1024); 76 77 const int BufferMaxSize = 64 * 1024 * 1024; 78 79 template <typename Allocator> 80 class StringBuilderImpl; 81 82 class SharedBufferAllocator { 83 MONGO_DISALLOW_COPYING(SharedBufferAllocator); 84 85 public: 86 SharedBufferAllocator() = default; SharedBufferAllocator(SharedBuffer buf)87 SharedBufferAllocator(SharedBuffer buf) : _buf(std::move(buf)) { 88 invariant(!_buf.isShared()); 89 } 90 91 // Allow moving but not copying. It would be an error for two SharedBufferAllocators to use the 92 // same underlying buffer. 93 SharedBufferAllocator(SharedBufferAllocator&&) = default; 94 SharedBufferAllocator& operator=(SharedBufferAllocator&&) = default; 95 malloc(size_t sz)96 void malloc(size_t sz) { 97 _buf = SharedBuffer::allocate(sz); 98 } realloc(size_t sz)99 void realloc(size_t sz) { 100 _buf.realloc(sz); 101 } free()102 void free() { 103 _buf = {}; 104 } release()105 SharedBuffer release() { 106 return std::move(_buf); 107 } 108 get()109 char* get() const { 110 return _buf.get(); 111 } 112 113 private: 114 SharedBuffer _buf; 115 }; 116 117 class StackAllocator { 118 MONGO_DISALLOW_COPYING(StackAllocator); 119 120 public: 121 StackAllocator() = default; ~StackAllocator()122 ~StackAllocator() { 123 free(); 124 } 125 126 enum { SZ = 512 }; malloc(size_t sz)127 void malloc(size_t sz) { 128 if (sz > SZ) 129 _ptr = mongoMalloc(sz); 130 } realloc(size_t sz)131 void realloc(size_t sz) { 132 if (_ptr == _buf) { 133 if (sz > SZ) { 134 _ptr = mongoMalloc(sz); 135 memcpy(_ptr, _buf, SZ); 136 } 137 } else { 138 _ptr = mongoRealloc(_ptr, sz); 139 } 140 } free()141 void free() { 142 if (_ptr != _buf) 143 ::free(_ptr); 144 _ptr = _buf; 145 } 146 147 // Not supported on this allocator. 148 void release() = delete; 149 get()150 char* get() const { 151 return static_cast<char*>(_ptr); 152 } 153 154 private: 155 char _buf[SZ]; 156 void* _ptr = _buf; 157 }; 158 159 template <class BufferAllocator> 160 class _BufBuilder { 161 public: size(initsize)162 _BufBuilder(int initsize = 512) : size(initsize) { 163 if (size > 0) { 164 _buf.malloc(size); 165 } 166 l = 0; 167 reservedBytes = 0; 168 } 169 kill()170 void kill() { 171 _buf.free(); 172 } 173 reset()174 void reset() { 175 l = 0; 176 reservedBytes = 0; 177 } reset(int maxSize)178 void reset(int maxSize) { 179 l = 0; 180 reservedBytes = 0; 181 if (maxSize && size > maxSize) { 182 _buf.free(); 183 _buf.malloc(maxSize); 184 size = maxSize; 185 } 186 } 187 188 /** leave room for some stuff later 189 @return point to region that was skipped. pointer may change later (on realloc), so for 190 immediate use only 191 */ skip(int n)192 char* skip(int n) { 193 return grow(n); 194 } 195 196 /* note this may be deallocated (realloced) if you keep writing. */ buf()197 char* buf() { 198 return _buf.get(); 199 } buf()200 const char* buf() const { 201 return _buf.get(); 202 } 203 204 /* assume ownership of the buffer */ release()205 SharedBuffer release() { 206 return _buf.release(); 207 } 208 appendUChar(unsigned char j)209 void appendUChar(unsigned char j) { 210 MONGO_STATIC_ASSERT(CHAR_BIT == 8); 211 appendNumImpl(j); 212 } appendChar(char j)213 void appendChar(char j) { 214 appendNumImpl(j); 215 } appendNum(char j)216 void appendNum(char j) { 217 appendNumImpl(j); 218 } appendNum(short j)219 void appendNum(short j) { 220 MONGO_STATIC_ASSERT(sizeof(short) == 2); 221 appendNumImpl(j); 222 } appendNum(int j)223 void appendNum(int j) { 224 MONGO_STATIC_ASSERT(sizeof(int) == 4); 225 appendNumImpl(j); 226 } appendNum(unsigned j)227 void appendNum(unsigned j) { 228 appendNumImpl(j); 229 } 230 231 // Bool does not have a well defined encoding. 232 void appendNum(bool j) = delete; 233 appendNum(double j)234 void appendNum(double j) { 235 MONGO_STATIC_ASSERT(sizeof(double) == 8); 236 appendNumImpl(j); 237 } appendNum(long long j)238 void appendNum(long long j) { 239 MONGO_STATIC_ASSERT(sizeof(long long) == 8); 240 appendNumImpl(j); 241 } 242 appendNum(Decimal128 j)243 void appendNum(Decimal128 j) { 244 BOOST_STATIC_ASSERT(sizeof(Decimal128::Value) == 16); 245 Decimal128::Value value = j.getValue(); 246 long long low = value.low64; 247 long long high = value.high64; 248 appendNumImpl(low); 249 appendNumImpl(high); 250 } 251 252 template <typename Int64_t, 253 typename = stdx::enable_if_t<std::is_same<Int64_t, int64_t>::value && 254 !std::is_same<int64_t, long long>::value>> appendNum(Int64_t j)255 void appendNum(Int64_t j) { 256 appendNumImpl(j); 257 } 258 appendNum(unsigned long long j)259 void appendNum(unsigned long long j) { 260 appendNumImpl(j); 261 } 262 appendBuf(const void * src,size_t len)263 void appendBuf(const void* src, size_t len) { 264 if (len) 265 memcpy(grow((int)len), src, len); 266 } 267 268 template <class T> appendStruct(const T & s)269 void appendStruct(const T& s) { 270 appendBuf(&s, sizeof(T)); 271 } 272 273 void appendStr(StringData str, bool includeEndingNull = true) { 274 const int len = str.size() + (includeEndingNull ? 1 : 0); 275 str.copyTo(grow(len), includeEndingNull); 276 } 277 278 /** @return length of current std::string */ len()279 int len() const { 280 return l; 281 } setlen(int newLen)282 void setlen(int newLen) { 283 l = newLen; 284 } 285 /** @return size of the buffer */ getSize()286 int getSize() const { 287 return size; 288 } 289 290 /* returns the pre-grow write position */ grow(int by)291 inline char* grow(int by) { 292 int oldlen = l; 293 int newLen = l + by; 294 int minSize = newLen + reservedBytes; 295 if (minSize > size) { 296 grow_reallocate(minSize); 297 } 298 l = newLen; 299 return _buf.get() + oldlen; 300 } 301 302 /** 303 * Reserve room for some number of bytes to be claimed at a later time. 304 */ reserveBytes(int bytes)305 void reserveBytes(int bytes) { 306 int minSize = l + reservedBytes + bytes; 307 if (minSize > size) 308 grow_reallocate(minSize); 309 310 // This must happen *after* any attempt to grow. 311 reservedBytes += bytes; 312 } 313 314 /** 315 * Claim an earlier reservation of some number of bytes. These bytes must already have been 316 * reserved. Appends of up to this many bytes immediately following a claim are 317 * guaranteed to succeed without a need to reallocate. 318 */ claimReservedBytes(int bytes)319 void claimReservedBytes(int bytes) { 320 invariant(reservedBytes >= bytes); 321 reservedBytes -= bytes; 322 } 323 324 /** 325 * Replaces the buffer backing this BufBuilder with the passed in SharedBuffer. 326 * Only legal to call when this builder is empty and when the SharedBuffer isn't shared. 327 */ useSharedBuffer(SharedBuffer buf)328 void useSharedBuffer(SharedBuffer buf) { 329 MONGO_STATIC_ASSERT(std::is_same<BufferAllocator, SharedBufferAllocator>()); 330 invariant(l == 0); // Can only do this while empty. 331 invariant(reservedBytes == 0); 332 size = buf.capacity(); 333 _buf = SharedBufferAllocator(std::move(buf)); 334 } 335 336 private: 337 template <typename T> appendNumImpl(T t)338 void appendNumImpl(T t) { 339 // NOTE: For now, we assume that all things written 340 // by a BufBuilder are intended for external use: either written to disk 341 // or to the wire. Since all of our encoding formats are little endian, 342 // we bake that assumption in here. This decision should be revisited soon. 343 DataView(grow(sizeof(t))).write(tagLittleEndian(t)); 344 } 345 /* "slow" portion of 'grow()' */ grow_reallocate(int minSize)346 void NOINLINE_DECL grow_reallocate(int minSize) { 347 if (minSize > BufferMaxSize) { 348 std::stringstream ss; 349 ss << "BufBuilder attempted to grow() to " << minSize << " bytes, past the 64MB limit."; 350 msgasserted(13548, ss.str().c_str()); 351 } 352 353 int a = 64; 354 while (a < minSize) 355 a = a * 2; 356 357 _buf.realloc(a); 358 size = a; 359 } 360 361 BufferAllocator _buf; 362 int l; 363 int size; 364 int reservedBytes; // eagerly grow_reallocate to keep this many bytes of spare room. 365 366 friend class StringBuilderImpl<BufferAllocator>; 367 }; 368 369 typedef _BufBuilder<SharedBufferAllocator> BufBuilder; 370 MONGO_STATIC_ASSERT(std::is_move_constructible<BufBuilder>::value); 371 372 /** The StackBufBuilder builds smaller datasets on the stack instead of using malloc. 373 this can be significantly faster for small bufs. However, you can not release() the 374 buffer with StackBufBuilder. 375 While designed to be a variable on the stack, if you were to dynamically allocate one, 376 nothing bad would happen. In fact in some circumstances this might make sense, say, 377 embedded in some other object. 378 */ 379 class StackBufBuilder : public _BufBuilder<StackAllocator> { 380 public: StackBufBuilder()381 StackBufBuilder() : _BufBuilder<StackAllocator>(StackAllocator::SZ) {} 382 void release() = delete; // not allowed. not implemented. 383 }; 384 MONGO_STATIC_ASSERT(!std::is_move_constructible<StackBufBuilder>::value); 385 386 /** std::stringstream deals with locale so this is a lot faster than std::stringstream for UTF8 */ 387 template <typename Allocator> 388 class StringBuilderImpl { 389 public: 390 // Sizes are determined based on the number of characters in 64-bit + the trailing '\0' 391 static const size_t MONGO_DBL_SIZE = 3 + DBL_MANT_DIG - DBL_MIN_EXP + 1; 392 static const size_t MONGO_S32_SIZE = 12; 393 static const size_t MONGO_U32_SIZE = 11; 394 static const size_t MONGO_S64_SIZE = 23; 395 static const size_t MONGO_U64_SIZE = 22; 396 static const size_t MONGO_S16_SIZE = 7; 397 static const size_t MONGO_PTR_SIZE = 19; // Accounts for the 0x prefix 398 StringBuilderImpl()399 StringBuilderImpl() {} 400 401 StringBuilderImpl& operator<<(double x) { 402 return SBNUM(x, MONGO_DBL_SIZE, "%g"); 403 } 404 StringBuilderImpl& operator<<(int x) { 405 return appendIntegral(x, MONGO_S32_SIZE); 406 } 407 StringBuilderImpl& operator<<(unsigned x) { 408 return appendIntegral(x, MONGO_U32_SIZE); 409 } 410 StringBuilderImpl& operator<<(long x) { 411 return appendIntegral(x, MONGO_S64_SIZE); 412 } 413 StringBuilderImpl& operator<<(unsigned long x) { 414 return appendIntegral(x, MONGO_U64_SIZE); 415 } 416 StringBuilderImpl& operator<<(long long x) { 417 return appendIntegral(x, MONGO_S64_SIZE); 418 } 419 StringBuilderImpl& operator<<(unsigned long long x) { 420 return appendIntegral(x, MONGO_U64_SIZE); 421 } 422 StringBuilderImpl& operator<<(short x) { 423 return appendIntegral(x, MONGO_S16_SIZE); 424 } 425 StringBuilderImpl& operator<<(const void* x) { 426 if (sizeof(x) == 8) { 427 return SBNUM(x, MONGO_PTR_SIZE, "0x%llX"); 428 } else { 429 return SBNUM(x, MONGO_PTR_SIZE, "0x%lX"); 430 } 431 } 432 StringBuilderImpl& operator<<(bool val) { 433 *_buf.grow(1) = val ? '1' : '0'; 434 return *this; 435 } 436 StringBuilderImpl& operator<<(char c) { 437 _buf.grow(1)[0] = c; 438 return *this; 439 } 440 StringBuilderImpl& operator<<(const char* str) { 441 return *this << StringData(str); 442 } 443 StringBuilderImpl& operator<<(StringData str) { 444 append(str); 445 return *this; 446 } 447 StringBuilderImpl& operator<<(BSONType type) { 448 append(typeName(type)); 449 return *this; 450 } 451 StringBuilderImpl& operator<<(ErrorCodes::Error code) { 452 append(ErrorCodes::errorString(code)); 453 return *this; 454 } 455 456 template <typename T> 457 StringBuilderImpl& operator<<(const boost::optional<T>& optional) { 458 return optional ? *this << *optional : *this << "(None)"; 459 } 460 appendDoubleNice(double x)461 void appendDoubleNice(double x) { 462 const int prev = _buf.l; 463 const int maxSize = 32; 464 char* start = _buf.grow(maxSize); 465 int z = snprintf(start, maxSize, "%.16g", x); 466 verify(z >= 0); 467 verify(z < maxSize); 468 _buf.l = prev + z; 469 if (strchr(start, '.') == 0 && strchr(start, 'E') == 0 && strchr(start, 'N') == 0) { 470 write(".0", 2); 471 } 472 } 473 write(const char * buf,int len)474 void write(const char* buf, int len) { 475 memcpy(_buf.grow(len), buf, len); 476 } 477 append(StringData str)478 void append(StringData str) { 479 str.copyTo(_buf.grow(str.size()), false); 480 } 481 482 void reset(int maxSize = 0) { 483 _buf.reset(maxSize); 484 } 485 str()486 std::string str() const { 487 return std::string(_buf.buf(), _buf.l); 488 } 489 490 /** 491 * Returns a view of this string without copying. 492 * 493 * WARNING: the view expires when this StringBuilder is modified or destroyed. 494 */ stringData()495 StringData stringData() const { 496 return StringData(_buf.buf(), _buf.l); 497 } 498 499 /** size of current std::string */ len()500 int len() const { 501 return _buf.l; 502 } 503 504 private: 505 _BufBuilder<Allocator> _buf; 506 template <typename T> appendIntegral(T val,int maxSize)507 StringBuilderImpl& appendIntegral(T val, int maxSize) { 508 MONGO_STATIC_ASSERT(!std::is_same<T, char>()); // char shouldn't append as number. 509 MONGO_STATIC_ASSERT(std::is_integral<T>()); 510 511 if (val < 0) { 512 *this << '-'; 513 append(StringData(ItoA(0 - uint64_t(val)))); // Send the magnitude to ItoA. 514 } else { 515 append(StringData(ItoA(uint64_t(val)))); 516 } 517 518 return *this; 519 } 520 521 template <typename T> SBNUM(T val,int maxSize,const char * macro)522 StringBuilderImpl& SBNUM(T val, int maxSize, const char* macro) { 523 int prev = _buf.l; 524 int z = snprintf(_buf.grow(maxSize), maxSize, macro, (val)); 525 verify(z >= 0); 526 verify(z < maxSize); 527 _buf.l = prev + z; 528 return *this; 529 } 530 }; 531 532 typedef StringBuilderImpl<SharedBufferAllocator> StringBuilder; 533 typedef StringBuilderImpl<StackAllocator> StackStringBuilder; 534 } // namespace mongo 535