1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 #pragma once
10
11 #include <algorithm>
12 #include "port/port.h"
13
14 namespace ROCKSDB_NAMESPACE {
15
16 // This file contains utilities to handle the alignment of pages and buffers.
17
18 // Truncate to a multiple of page_size, which is also a page boundary. This
19 // helps to figuring out the right alignment.
20 // Example:
21 // TruncateToPageBoundary(5000, 4096) => 4096
22 // TruncateToPageBoundary(10000, 4096) => 8192
TruncateToPageBoundary(size_t page_size,size_t s)23 inline size_t TruncateToPageBoundary(size_t page_size, size_t s) {
24 s -= (s & (page_size - 1));
25 assert((s % page_size) == 0);
26 return s;
27 }
28
29 // Round up x to a multiple of y.
30 // Example:
31 // Roundup(13, 5) => 15
32 // Roundup(201, 16) => 208
Roundup(size_t x,size_t y)33 inline size_t Roundup(size_t x, size_t y) {
34 return ((x + y - 1) / y) * y;
35 }
36
37 // Round down x to a multiple of y.
38 // Example:
39 // Rounddown(13, 5) => 10
40 // Rounddown(201, 16) => 192
Rounddown(size_t x,size_t y)41 inline size_t Rounddown(size_t x, size_t y) { return (x / y) * y; }
42
43 // AlignedBuffer manages a buffer by taking alignment into consideration, and
44 // aligns the buffer start and end positions. It is mainly used for direct I/O,
45 // though it can be used other purposes as well.
46 // It also supports expanding the managed buffer, and copying whole or part of
47 // the data from old buffer into the new expanded buffer. Such a copy especially
48 // helps in cases avoiding an IO to re-fetch the data from disk.
49 //
50 // Example:
51 // AlignedBuffer buf;
52 // buf.Alignment(alignment);
53 // buf.AllocateNewBuffer(user_requested_buf_size);
54 // ...
55 // buf.AllocateNewBuffer(2*user_requested_buf_size, /*copy_data*/ true,
56 // copy_offset, copy_len);
57 class AlignedBuffer {
58 size_t alignment_;
59 std::unique_ptr<char[]> buf_;
60 size_t capacity_;
61 size_t cursize_;
62 char* bufstart_;
63
64 public:
AlignedBuffer()65 AlignedBuffer()
66 : alignment_(),
67 capacity_(0),
68 cursize_(0),
69 bufstart_(nullptr) {
70 }
71
AlignedBuffer(AlignedBuffer && o)72 AlignedBuffer(AlignedBuffer&& o) ROCKSDB_NOEXCEPT {
73 *this = std::move(o);
74 }
75
76 AlignedBuffer& operator=(AlignedBuffer&& o) ROCKSDB_NOEXCEPT {
77 alignment_ = std::move(o.alignment_);
78 buf_ = std::move(o.buf_);
79 capacity_ = std::move(o.capacity_);
80 cursize_ = std::move(o.cursize_);
81 bufstart_ = std::move(o.bufstart_);
82 return *this;
83 }
84
85 AlignedBuffer(const AlignedBuffer&) = delete;
86
87 AlignedBuffer& operator=(const AlignedBuffer&) = delete;
88
isAligned(const void * ptr,size_t alignment)89 static bool isAligned(const void* ptr, size_t alignment) {
90 return reinterpret_cast<uintptr_t>(ptr) % alignment == 0;
91 }
92
isAligned(size_t n,size_t alignment)93 static bool isAligned(size_t n, size_t alignment) {
94 return n % alignment == 0;
95 }
96
Alignment()97 size_t Alignment() const {
98 return alignment_;
99 }
100
Capacity()101 size_t Capacity() const {
102 return capacity_;
103 }
104
CurrentSize()105 size_t CurrentSize() const {
106 return cursize_;
107 }
108
BufferStart()109 const char* BufferStart() const {
110 return bufstart_;
111 }
112
BufferStart()113 char* BufferStart() { return bufstart_; }
114
Clear()115 void Clear() {
116 cursize_ = 0;
117 }
118
Alignment(size_t alignment)119 void Alignment(size_t alignment) {
120 assert(alignment > 0);
121 assert((alignment & (alignment - 1)) == 0);
122 alignment_ = alignment;
123 }
124
125 // Allocates a new buffer and sets the start position to the first aligned
126 // byte.
127 //
128 // requested_capacity: requested new buffer capacity. This capacity will be
129 // rounded up based on alignment.
130 // copy_data: Copy data from old buffer to new buffer. If copy_offset and
131 // copy_len are not passed in and the new requested capacity is bigger
132 // than the existing buffer's capacity, the data in the exising buffer is
133 // fully copied over to the new buffer.
134 // copy_offset: Copy data from this offset in old buffer.
135 // copy_len: Number of bytes to copy.
136 //
137 // The function does nothing if the new requested_capacity is smaller than
138 // the current buffer capacity and copy_data is true i.e. the old buffer is
139 // retained as is.
140 void AllocateNewBuffer(size_t requested_capacity, bool copy_data = false,
141 uint64_t copy_offset = 0, size_t copy_len = 0) {
142 assert(alignment_ > 0);
143 assert((alignment_ & (alignment_ - 1)) == 0);
144
145 copy_len = copy_len > 0 ? copy_len : cursize_;
146 if (copy_data && requested_capacity < copy_len) {
147 // If we are downsizing to a capacity that is smaller than the current
148 // data in the buffer -- Ignore the request.
149 return;
150 }
151
152 size_t new_capacity = Roundup(requested_capacity, alignment_);
153 char* new_buf = new char[new_capacity + alignment_];
154 char* new_bufstart = reinterpret_cast<char*>(
155 (reinterpret_cast<uintptr_t>(new_buf) + (alignment_ - 1)) &
156 ~static_cast<uintptr_t>(alignment_ - 1));
157
158 if (copy_data) {
159 assert(bufstart_ + copy_offset + copy_len <= bufstart_ + cursize_);
160 memcpy(new_bufstart, bufstart_ + copy_offset, copy_len);
161 cursize_ = copy_len;
162 } else {
163 cursize_ = 0;
164 }
165
166 bufstart_ = new_bufstart;
167 capacity_ = new_capacity;
168 buf_.reset(new_buf);
169 }
170
171 // Append to the buffer.
172 //
173 // src : source to copy the data from.
174 // append_size : number of bytes to copy from src.
175 // Returns the number of bytes appended.
176 //
177 // If append_size is more than the remaining buffer size only the
178 // remaining-size worth of bytes are copied.
Append(const char * src,size_t append_size)179 size_t Append(const char* src, size_t append_size) {
180 size_t buffer_remaining = capacity_ - cursize_;
181 size_t to_copy = std::min(append_size, buffer_remaining);
182
183 if (to_copy > 0) {
184 memcpy(bufstart_ + cursize_, src, to_copy);
185 cursize_ += to_copy;
186 }
187 return to_copy;
188 }
189
190 // Read from the buffer.
191 //
192 // dest : destination buffer to copy the data to.
193 // offset : the buffer offset to start reading from.
194 // read_size : the number of bytes to copy from the buffer to dest.
195 // Returns the number of bytes read/copied to dest.
Read(char * dest,size_t offset,size_t read_size)196 size_t Read(char* dest, size_t offset, size_t read_size) const {
197 assert(offset < cursize_);
198
199 size_t to_read = 0;
200 if(offset < cursize_) {
201 to_read = std::min(cursize_ - offset, read_size);
202 }
203 if (to_read > 0) {
204 memcpy(dest, bufstart_ + offset, to_read);
205 }
206 return to_read;
207 }
208
209 // Pad to the end of alignment with "padding"
PadToAlignmentWith(int padding)210 void PadToAlignmentWith(int padding) {
211 size_t total_size = Roundup(cursize_, alignment_);
212 size_t pad_size = total_size - cursize_;
213
214 if (pad_size > 0) {
215 assert((pad_size + cursize_) <= capacity_);
216 memset(bufstart_ + cursize_, padding, pad_size);
217 cursize_ += pad_size;
218 }
219 }
220
PadWith(size_t pad_size,int padding)221 void PadWith(size_t pad_size, int padding) {
222 assert((pad_size + cursize_) <= capacity_);
223 memset(bufstart_ + cursize_, padding, pad_size);
224 cursize_ += pad_size;
225 }
226
227 // After a partial flush move the tail to the beginning of the buffer.
RefitTail(size_t tail_offset,size_t tail_size)228 void RefitTail(size_t tail_offset, size_t tail_size) {
229 if (tail_size > 0) {
230 memmove(bufstart_, bufstart_ + tail_offset, tail_size);
231 }
232 cursize_ = tail_size;
233 }
234
235 // Returns a place to start appending.
236 // WARNING: Note that it is possible to write past the end of the buffer if
237 // the buffer is modified without using the write APIs or encapsulation
238 // offered by AlignedBuffer. It is up to the user to guard against such
239 // errors.
Destination()240 char* Destination() {
241 return bufstart_ + cursize_;
242 }
243
Size(size_t cursize)244 void Size(size_t cursize) {
245 cursize_ = cursize;
246 }
247 };
248 } // namespace ROCKSDB_NAMESPACE
249