1 // Copyright (C) 2019 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "icing/legacy/index/icing-array-storage.h"
16
17 #include <inttypes.h>
18 #include <sys/mman.h>
19
20 #include <algorithm>
21
22 #include "icing/legacy/core/icing-string-util.h"
23 #include "icing/legacy/core/icing-timer.h"
24 #include "icing/legacy/index/icing-bit-util.h"
25 #include "icing/legacy/index/icing-filesystem.h"
26 #include "icing/legacy/index/icing-mmapper.h"
27 #include "icing/util/logging.h"
28
29 using std::max;
30 using std::min;
31 using std::vector;
32
33 namespace icing {
34 namespace lib {
35
36 namespace {
37
38 // Do the cast and const dance.
MakeVoidPtr(const void * ptr)39 void *MakeVoidPtr(const void *ptr) { return const_cast<void *>(ptr); }
40
41 } // namespace
42
43 const uint32_t IcingArrayStorage::kPartialCrcLimitDiv = 8; // limit is 1/8th
44 const size_t IcingArrayStorage::kGrowElts = 1u << 14; // 16KB
45
IcingArrayStorage(const IcingFilesystem & filesystem)46 IcingArrayStorage::IcingArrayStorage(const IcingFilesystem &filesystem)
47 : mmapper_(nullptr), filesystem_(filesystem) {
48 Reset();
49 }
50
~IcingArrayStorage()51 IcingArrayStorage::~IcingArrayStorage() { delete mmapper_; }
52
Init(int fd,size_t fd_offset,bool map_shared,uint32_t elt_size,uint32_t num_elts,uint32_t max_num_elts,uint32_t * crc_ptr,bool init_crc)53 bool IcingArrayStorage::Init(int fd, size_t fd_offset, bool map_shared,
54 uint32_t elt_size, uint32_t num_elts,
55 uint32_t max_num_elts, uint32_t *crc_ptr,
56 bool init_crc) {
57 if (is_initialized()) {
58 return true;
59 }
60
61 // Compute capacity_num_.
62 uint64_t file_size = filesystem_.GetFileSize(fd);
63 if (file_size == IcingFilesystem::kBadFileSize) {
64 ICING_LOG(ERROR) << "Array storage could not get file size";
65 return false;
66 }
67 if (file_size < fd_offset) {
68 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
69 "Array storage file size %" PRIu64 " less than offset %zu", file_size,
70 fd_offset);
71 return false;
72 }
73
74 uint32_t capacity_num_elts = (file_size - fd_offset) / elt_size;
75 if (capacity_num_elts < num_elts) {
76 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
77 "Array storage num elts %u > capacity num elts %u", num_elts,
78 capacity_num_elts);
79 return false;
80 }
81
82 // Map beyond the capacity. We will grow underlying file to avoid
83 // SIGBUS.
84 mmapper_ = new IcingMMapper(fd, false, fd_offset, max_num_elts * elt_size,
85 map_shared ? MAP_SHARED : MAP_PRIVATE);
86 if (!mmapper_->is_valid()) {
87 ICING_LOG(ERROR) << "Array storage map failed";
88 delete mmapper_;
89 mmapper_ = nullptr;
90 return false;
91 }
92
93 fd_ = fd;
94 fd_offset_ = fd_offset;
95 map_shared_ = map_shared;
96 elt_size_ = elt_size;
97 // changes_end_ refers to the last element that was included in the
98 // current crc. If we change it, we must also update *crc_ptr_ to
99 // 0. Otherwise UpdateCrc will fail.
100 cur_num_ = changes_end_ = num_elts;
101 max_num_ = max_num_elts;
102 capacity_num_ = capacity_num_elts;
103 crc_ptr_ = crc_ptr;
104
105 if (crc_ptr_) {
106 uint32_t crc = IcingStringUtil::UpdateCrc32(0, array_cast<char>(),
107 cur_num_ * elt_size_);
108 if (init_crc) {
109 *crc_ptr_ = crc;
110 } else if (crc != *crc_ptr_) {
111 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
112 "Array storage bad crc %u vs %u", crc, *crc_ptr_);
113 goto failed;
114 }
115 }
116 return true;
117
118 failed:
119 Reset();
120 return false;
121 }
122
Reset()123 void IcingArrayStorage::Reset() {
124 fd_ = -1;
125 fd_offset_ = 0;
126 map_shared_ = false;
127 delete mmapper_;
128 mmapper_ = nullptr;
129 elt_size_ = 0;
130 cur_num_ = 0;
131 changes_end_ = 0;
132 max_num_ = 0;
133 capacity_num_ = 0;
134 crc_ptr_ = nullptr;
135 changes_.clear();
136 saved_orig_buf_.clear();
137 dirty_pages_.clear();
138 }
139
Truncate(uint32_t len)140 void IcingArrayStorage::Truncate(uint32_t len) {
141 if (len > cur_num_) {
142 ICING_LOG(FATAL) << "Length exceeds current size";
143 }
144
145 cur_num_ = len;
146 }
147
GetMutableMemInternal(uint32_t elt_idx,uint32_t elt_len)148 void *IcingArrayStorage::GetMutableMemInternal(uint32_t elt_idx,
149 uint32_t elt_len) {
150 uint32_t start_byte = elt_idx * elt_size_;
151 uint32_t len_bytes = elt_len * elt_size_;
152
153 if (!GrowIfNecessary(elt_idx + elt_len)) {
154 return nullptr;
155 }
156
157 cur_num_ = max(cur_num_, elt_idx + elt_len);
158
159 if (crc_ptr_) {
160 // Cache original value to update crcs.
161 if (elt_idx < changes_end_) {
162 uint32_t change_len = min(changes_end_, elt_idx + elt_len) - elt_idx;
163
164 // If we exceed kPartialCrcLimitDiv, clear changes_end_ to
165 // revert to full CRC.
166 if ((saved_orig_buf_.size() + change_len * elt_size_) *
167 kPartialCrcLimitDiv >
168 changes_end_ * elt_size_) {
169 ICING_VLOG(2) << "Array storage change tracking limit exceeded";
170 changes_.clear();
171 saved_orig_buf_.clear();
172 changes_end_ = 0;
173 *crc_ptr_ = 0;
174 } else {
175 changes_.push_back(Change(elt_idx, change_len));
176 saved_orig_buf_.append(array_cast<char>() + start_byte,
177 change_len * elt_size_);
178 }
179 }
180 }
181
182 if (!map_shared_) {
183 // Mark dirty pages.
184 int start_page = start_byte / IcingMMapper::system_page_size();
185 int end_page =
186 (start_byte + len_bytes - 1) / IcingMMapper::system_page_size();
187
188 for (int i = start_page; i <= end_page; i++) {
189 if (static_cast<size_t>(i) >= dirty_pages_.size()) {
190 dirty_pages_.resize(i + 1);
191 }
192 dirty_pages_[i] = true;
193 }
194 }
195
196 return MakeVoidPtr(&(array())[start_byte]);
197 }
198
GrowIfNecessary(uint32_t num_elts)199 bool IcingArrayStorage::GrowIfNecessary(uint32_t num_elts) {
200 if (num_elts <= capacity_num_) return true;
201 if (num_elts > max_num_) return false;
202
203 // Need to grow.
204 uint64_t new_file_size = fd_offset_ + uint64_t{num_elts} * elt_size_;
205 // Grow to kGrowElts boundary.
206 new_file_size = AlignUp(new_file_size, kGrowElts * elt_size_);
207 if (!filesystem_.Grow(fd_, new_file_size)) {
208 return false;
209 }
210 capacity_num_ = (new_file_size - fd_offset_) / elt_size_;
211 return true;
212 }
213
UpdateCrc()214 void IcingArrayStorage::UpdateCrc() {
215 if (!crc_ptr_) return;
216
217 // First apply the modified area. Keep a bitmap of already updated
218 // regions so we don't double-update.
219 vector<bool> updated(changes_end_);
220 uint32_t cur_offset = 0;
221 uint32_t cur_crc = *crc_ptr_;
222 int num_partial_crcs = 0;
223 int num_truncated = 0;
224 int num_overlapped = 0;
225 int num_duplicate = 0;
226 for (size_t i = 0; i < changes_.size(); i++) {
227 const Change &change = changes_[i];
228 if (change.elt_offset + change.elt_len > changes_end_) {
229 ICING_LOG(FATAL) << "Off " << change.elt_offset << " len "
230 << change.elt_len << " end " << changes_end_;
231 }
232
233 // Skip truncated tracked changes.
234 if (change.elt_offset >= cur_num_) {
235 ++num_truncated;
236 continue;
237 }
238
239 // Turn change buf into change^orig.
240 const char *buf_end =
241 &saved_orig_buf_[cur_offset + change.elt_len * elt_size_];
242 const char *cur_array = array_cast<char>() + change.elt_offset * elt_size_;
243 // Now xor in. SSE acceleration please?
244 for (char *cur = &saved_orig_buf_[cur_offset]; cur < buf_end;
245 cur++, cur_array++) {
246 *cur ^= *cur_array;
247 }
248
249 // Skip over already updated bytes by setting update to 0.
250 bool new_update = false;
251 bool overlap = false;
252 uint32_t cur_elt = change.elt_offset;
253 for (char *cur = &saved_orig_buf_[cur_offset]; cur < buf_end;
254 cur_elt++, cur += elt_size_) {
255 if (updated[cur_elt]) {
256 memset(cur, 0, elt_size_);
257 overlap = true;
258 } else {
259 updated[cur_elt] = true;
260 new_update = true;
261 }
262 }
263
264 // Apply update to crc.
265 if (new_update) {
266 cur_crc = IcingStringUtil::UpdateAtPositionCrc32(
267 cur_crc, changes_end_ * elt_size_, change.elt_offset * elt_size_,
268 buf_end - change.elt_len * elt_size_, change.elt_len * elt_size_);
269 num_partial_crcs++;
270 if (overlap) {
271 num_overlapped++;
272 }
273 } else {
274 num_duplicate++;
275 }
276 cur_offset += change.elt_len * elt_size_;
277 }
278 if (!changes_.empty()) {
279 ICING_VLOG(2) << IcingStringUtil::StringPrintf(
280 "Array update partial crcs %d truncated %d overlapped %d duplicate %d",
281 num_partial_crcs, num_truncated, num_overlapped, num_duplicate);
282 }
283
284 // Now update with grown area.
285 if (changes_end_ < cur_num_) {
286 cur_crc = IcingStringUtil::UpdateCrc32(
287 cur_crc, array_cast<char>() + changes_end_ * elt_size_,
288 (cur_num_ - changes_end_) * elt_size_);
289 ICING_VLOG(2) << IcingStringUtil::StringPrintf(
290 "Array update tail crc offset %u -> %u", changes_end_, cur_num_);
291 }
292
293 // Clear, now that we've applied changes.
294 changes_.clear();
295 saved_orig_buf_.clear();
296 changes_end_ = cur_num_;
297
298 // Commit new crc.
299 *crc_ptr_ = cur_crc;
300 }
301
Warm() const302 void IcingArrayStorage::Warm() const {
303 if (madvise(MakeVoidPtr(array()),
304 IcingMMapper::page_aligned_size(cur_num_ * elt_size_),
305 MADV_WILLNEED) != 0) {
306 ICING_LOG(FATAL) << "Failed to madvise()";
307 }
308 }
309
Clear()310 void IcingArrayStorage::Clear() {
311 cur_num_ = 0;
312 changes_end_ = 0;
313 changes_.clear();
314 saved_orig_buf_.clear();
315 dirty_pages_.clear();
316 if (crc_ptr_) *crc_ptr_ = 0;
317 }
318
319 // TODO(b/69383247): investigate strange behavior here
320 // If map_shared_ is false (i.e. we are using MAP_PRIVATE), dirty pages are
321 // flushed to the underlying file, but strangely a sync isn't done.
322 // If map_shared_ is true, then we call sync.
Sync()323 uint32_t IcingArrayStorage::Sync() {
324 if (!map_shared_) {
325 IcingTimer timer;
326 uint32_t num_flushed = 0; // pages flushed
327 uint32_t num_contiguous = 0; // contiguous series of pages flushed
328 uint32_t dirty_pages_size = dirty_pages_.size();
329
330 bool in_dirty = false;
331 uint32_t dirty_start = 0;
332 for (size_t i = 0; i < dirty_pages_size; i++) {
333 bool is_dirty = dirty_pages_[i];
334 if (in_dirty && !is_dirty) {
335 // Flush pages between dirty_start and this.
336 uint32_t dirty_end = i * IcingMMapper::system_page_size();
337 num_contiguous++;
338 num_flushed +=
339 (dirty_end - dirty_start) / IcingMMapper::system_page_size();
340
341 if (pwrite(fd_, array() + dirty_start, dirty_end - dirty_start,
342 fd_offset_ + dirty_start) !=
343 static_cast<ssize_t>(dirty_end - dirty_start)) {
344 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
345 "Flushing pages failed (%u, %u)", dirty_start, dirty_end);
346 }
347 in_dirty = false;
348 } else if (!in_dirty && is_dirty) {
349 dirty_start = i * IcingMMapper::system_page_size();
350 in_dirty = true;
351 }
352 }
353
354 // Flush remaining.
355 if (in_dirty) {
356 uint32_t dirty_end = dirty_pages_size * IcingMMapper::system_page_size();
357 num_contiguous++;
358 num_flushed +=
359 (dirty_end - dirty_start) / IcingMMapper::system_page_size();
360
361 if (pwrite(fd_, array() + dirty_start, dirty_end - dirty_start,
362 fd_offset_ + dirty_start) !=
363 static_cast<ssize_t>(dirty_end - dirty_start)) {
364 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
365 "Flushing pages failed (%u, %u)", dirty_start, dirty_end);
366 }
367 }
368
369 // Clear in one shot.
370 dirty_pages_.clear();
371
372 // Invalidate region so that we are rid of dirty private pages.
373 if (madvise(MakeVoidPtr(array()),
374 IcingMMapper::page_aligned_size(cur_num_ * elt_size_),
375 MADV_DONTNEED) != 0) {
376 ICING_LOG(FATAL) << "Failed to madvise()";
377 }
378
379 if (num_flushed > 0) {
380 ICING_VLOG(1) << IcingStringUtil::StringPrintf(
381 "Flushing %u/%u %u contiguous pages in %.3fms", num_flushed,
382 dirty_pages_size, num_contiguous, timer.Elapsed() * 1000.);
383 }
384
385 return num_flushed;
386 } else {
387 // Changes have been applied. msync() to ensure they are written out.
388 // Don't sync 0-length, which is an error in iOS and a no-op on Android
389 const size_t sync_length =
390 IcingMMapper::page_aligned_size(cur_num_ * elt_size_);
391 if (sync_length > 0) {
392 if (msync(MakeVoidPtr(array()), sync_length, MS_SYNC) != 0) {
393 ICING_LOG(FATAL) << "Failed to msync()";
394 }
395 }
396
397 return 0;
398 }
399 }
400
401 } // namespace lib
402 } // namespace icing
403