1 2 /** 3 * Copyright (C) 2018-present MongoDB, Inc. 4 * 5 * This program is free software: you can redistribute it and/or modify 6 * it under the terms of the Server Side Public License, version 1, 7 * as published by MongoDB, Inc. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * Server Side Public License for more details. 13 * 14 * You should have received a copy of the Server Side Public License 15 * along with this program. If not, see 16 * <http://www.mongodb.com/licensing/server-side-public-license>. 17 * 18 * As a special exception, the copyright holders give permission to link the 19 * code of portions of this program with the OpenSSL library under certain 20 * conditions as described in each individual source file and distribute 21 * linked combinations including the program with the OpenSSL library. You 22 * must comply with the Server Side Public License in all respects for 23 * all of the code used other than as permitted herein. If you modify file(s) 24 * with this exception, you may extend this exception to your version of the 25 * file(s), but you are not obligated to do so. If you do not wish to do so, 26 * delete this exception statement from your version. If you delete this 27 * exception statement from all source files in the program, then also delete 28 * it in the license file. 29 */ 30 31 #pragma once 32 33 #include <algorithm> 34 #include <cstddef> 35 #include <cstring> 36 #include <limits> 37 #include <memory> 38 39 #include "mongo/base/data_range_cursor.h" 40 #include "mongo/util/allocator.h" 41 42 namespace mongo { 43 44 /** 45 * DataBuilder provides a reallocing buffer underneath the DataRangeCursor API. 46 * This allows consumers to write() or writeAndAdvance() without first ensuring 47 * they have the correct amount of space pre-allocated. 48 * 49 * The underlying strategy is optimistic, specifically it blindly tries all 50 * writes once. For any failure, we then call the store api with a null output 51 * ptr, which returns what space would have been used. That amount is used to 52 * guide growth in the buffer, after which we attempt the write again. 53 */ 54 class DataBuilder { 55 /** 56 * The dtor type used in the unique_ptr which holds the buffer 57 */ 58 struct FreeBuf { operatorFreeBuf59 void operator()(char* buf) { 60 std::free(buf); 61 } 62 }; 63 64 static const std::size_t kInitialBufferSize = 64; 65 66 public: 67 DataBuilder() = default; 68 69 /** 70 * Construct a DataBuilder with a specified initial capacity 71 */ DataBuilder(std::size_t bytes)72 explicit DataBuilder(std::size_t bytes) { 73 if (bytes) 74 resize(bytes); 75 } 76 DataBuilder(DataBuilder && other)77 DataBuilder(DataBuilder&& other) { 78 *this = std::move(other); 79 } 80 81 DataBuilder& operator=(DataBuilder&& other) { 82 _buf = std::move(other._buf); 83 _capacity = other._capacity; 84 _unwrittenSpaceCursor = {_buf.get(), _buf.get() + other.size()}; 85 86 other._capacity = 0; 87 other._unwrittenSpaceCursor = {nullptr, nullptr}; 88 89 return *this; 90 } 91 92 /** 93 * Write a value at an offset into the buffer. 94 */ 95 template <typename T> 96 Status write(const T& value, std::size_t offset = 0) { 97 _ensureStorage(); 98 99 auto status = _unwrittenSpaceCursor.write(value, offset); 100 101 if (!status.isOK()) { 102 reserve(_getSerializedSize(value)); 103 status = _unwrittenSpaceCursor.write(value, offset); 104 } 105 106 return status; 107 } 108 109 /** 110 * Write a value and advance to the byte past the last byte written. 111 */ 112 template <typename T> writeAndAdvance(const T & value)113 Status writeAndAdvance(const T& value) { 114 _ensureStorage(); 115 116 // TODO: We should offer: 117 // 118 // 1. A way to check if the type has a constant size 119 // 2. A way to perform a runtime write which can fail with "too little 120 // size" without status generation 121 auto status = _unwrittenSpaceCursor.writeAndAdvance(value); 122 123 if (!status.isOK()) { 124 reserve(_getSerializedSize(value)); 125 status = _unwrittenSpaceCursor.writeAndAdvance(value); 126 } 127 128 return status; 129 } 130 131 /** 132 * Get a writable cursor that covers the range of the currently written 133 * bytes 134 */ getCursor()135 DataRangeCursor getCursor() { 136 return {_buf.get(), _buf.get() + size()}; 137 } 138 139 /** 140 * Get a read-only cursor that covers the range of the currently written 141 * bytes 142 */ getCursor()143 ConstDataRangeCursor getCursor() const { 144 return {_buf.get(), _buf.get() + size()}; 145 } 146 147 /** 148 * The size of the currently written region 149 */ size()150 std::size_t size() const { 151 if (!_buf) { 152 return 0; 153 } 154 155 return _capacity - _unwrittenSpaceCursor.length(); 156 } 157 158 /** 159 * The total size of the buffer, including reserved but not written bytes. 160 */ capacity()161 std::size_t capacity() const { 162 return _capacity; 163 } 164 165 /** 166 * Resize the buffer to exactly newSize bytes. This can shrink the range or 167 * grow it. 168 */ resize(std::size_t newSize)169 void resize(std::size_t newSize) { 170 if (newSize == _capacity) 171 return; 172 173 if (newSize == 0) { 174 *this = DataBuilder{}; 175 return; 176 } 177 178 std::size_t oldSize = size(); 179 180 auto ptr = _buf.release(); 181 182 _buf.reset(static_cast<char*>(mongoRealloc(ptr, newSize))); 183 184 _capacity = newSize; 185 186 // If we downsized, truncate. If we upsized keep the old size 187 _unwrittenSpaceCursor = {_buf.get() + std::min(oldSize, _capacity), _buf.get() + _capacity}; 188 } 189 190 /** 191 * Reserve needed bytes. If there are already enough bytes in the buffer, 192 * it will not be changed. If there aren't enough bytes, we'll grow the 193 * buffer to meet the requirement by expanding along a 1.5^n curve. 194 */ reserve(std::size_t needed)195 void reserve(std::size_t needed) { 196 std::size_t oldSize = size(); 197 198 std::size_t newSize = _capacity ? _capacity : kInitialBufferSize; 199 200 while ((newSize < oldSize) || (newSize - oldSize < needed)) { 201 // growth factor of about 1.5 202 203 newSize = ((newSize * 3) + 1) / 2; 204 } 205 206 invariant(newSize >= oldSize); 207 208 resize(newSize); 209 } 210 211 /** 212 * Clear the buffer. This retains the existing buffer, merely resetting the 213 * internal data pointers. 214 */ clear()215 void clear() { 216 _unwrittenSpaceCursor = {_buf.get(), _buf.get() + _capacity}; 217 } 218 219 /** 220 * Release the buffer. After this the builder is left in the default 221 * constructed state. 222 */ release()223 std::unique_ptr<char, FreeBuf> release() { 224 auto buf = std::move(_buf); 225 226 *this = DataBuilder{}; 227 228 return buf; 229 } 230 231 private: 232 /** 233 * Returns the serialized size of a T. We verify this by using the 234 * DataType::store invocation without an output pointer, which asks for the 235 * number of bytes that would have been written. 236 */ 237 template <typename T> _getSerializedSize(const T & value)238 std::size_t _getSerializedSize(const T& value) { 239 std::size_t advance = 0; 240 DataType::store(value, nullptr, std::numeric_limits<std::size_t>::max(), &advance, 0) 241 .transitional_ignore(); 242 243 return advance; 244 } 245 246 /** 247 * If any writing methods are called on a default constructed or moved from 248 * DataBuilder, we use this method to initialize the buffer. 249 */ _ensureStorage()250 void _ensureStorage() { 251 if (!_buf) { 252 resize(kInitialBufferSize); 253 } 254 } 255 256 std::unique_ptr<char, FreeBuf> _buf; 257 std::size_t _capacity = 0; 258 DataRangeCursor _unwrittenSpaceCursor = {nullptr, nullptr}; 259 }; 260 261 } // namespace mongo 262