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