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/index/main/flash-index-storage.h"
16
17 #include <errno.h>
18 #include <inttypes.h>
19 #include <sys/types.h>
20
21 #include <algorithm>
22 #include <cstdint>
23 #include <memory>
24 #include <unordered_set>
25
26 #include "icing/absl_ports/canonical_errors.h"
27 #include "icing/absl_ports/str_cat.h"
28 #include "icing/file/memory-mapped-file.h"
29 #include "icing/index/main/index-block.h"
30 #include "icing/index/main/posting-list-free.h"
31 #include "icing/index/main/posting-list-utils.h"
32 #include "icing/legacy/core/icing-string-util.h"
33 #include "icing/util/logging.h"
34 #include "icing/util/math-util.h"
35 #include "icing/util/status-macros.h"
36
37 namespace icing {
38 namespace lib {
39
40 namespace {
41
SelectBlockSize()42 uint32_t SelectBlockSize() {
43 // This should be close to the flash page size.
44 static constexpr uint32_t kMinBlockSize = 4096;
45
46 // Determine a good block size.
47 uint32_t page_size = getpagesize();
48 uint32_t block_size = std::max(kMinBlockSize, page_size);
49
50 // Align up to the nearest page size.
51 return math_util::RoundUpTo(block_size, page_size);
52 }
53
54 } // namespace
55
Create(const std::string & index_filename,const Filesystem * filesystem,bool in_memory)56 libtextclassifier3::StatusOr<FlashIndexStorage> FlashIndexStorage::Create(
57 const std::string& index_filename, const Filesystem* filesystem,
58 bool in_memory) {
59 ICING_RETURN_ERROR_IF_NULL(filesystem);
60 FlashIndexStorage storage(index_filename, filesystem, in_memory);
61 if (!storage.Init()) {
62 return absl_ports::InternalError(
63 "Unable to successfully read header block!");
64 }
65 return storage;
66 }
67
FlashIndexStorage(const std::string & index_filename,const Filesystem * filesystem,bool has_in_memory_freelists)68 FlashIndexStorage::FlashIndexStorage(const std::string& index_filename,
69 const Filesystem* filesystem,
70 bool has_in_memory_freelists)
71 : index_filename_(index_filename),
72 num_blocks_(0),
73 filesystem_(filesystem),
74 has_in_memory_freelists_(has_in_memory_freelists) {}
75
~FlashIndexStorage()76 FlashIndexStorage::~FlashIndexStorage() {
77 if (header_block_ != nullptr) {
78 FlushInMemoryFreeList();
79 PersistToDisk();
80 }
81 }
82
Init()83 bool FlashIndexStorage::Init() {
84 block_fd_ = ScopedFd(filesystem_->OpenForWrite(index_filename_.c_str()));
85 if (!block_fd_.is_valid()) {
86 return false;
87 }
88
89 // Read in or create the header.
90 return InitHeader();
91 }
92
InitHeader()93 bool FlashIndexStorage::InitHeader() {
94 // Look for an existing file size.
95 int64_t file_size = filesystem_->GetFileSize(block_fd_.get());
96 if (file_size == Filesystem::kBadFileSize) {
97 ICING_LOG(ERROR) << "Could not initialize main index. Bad file size.";
98 return false;
99 }
100
101 if (file_size == 0) {
102 if (!CreateHeader()) {
103 ICING_LOG(ERROR)
104 << "Could not initialize main index. Unable to create header.";
105 return false;
106 }
107 } else {
108 if (!OpenHeader(file_size)) {
109 ICING_LOG(ERROR)
110 << "Could not initialize main index. Unable to open header.";
111 return false;
112 }
113 }
114 in_memory_freelists_.resize(header_block_->header()->num_index_block_infos);
115
116 return true;
117 }
118
CreateHeader()119 bool FlashIndexStorage::CreateHeader() {
120 uint32_t block_size = SelectBlockSize();
121 header_block_ = std::make_unique<HeaderBlock>(filesystem_, block_size);
122 // Initialize.
123 header_block_->header()->magic = HeaderBlock::Header::kMagic;
124 header_block_->header()->block_size = block_size;
125 header_block_->header()->last_indexed_docid = kInvalidDocumentId;
126
127 // Work down from the largest posting list that fits in
128 // block_size. We don't care about locality of blocks because this
129 // is a flash index.
130 for (uint32_t posting_list_bytes =
131 IndexBlock::CalculateMaxPostingListBytes(block_size);
132 posting_list_bytes >= posting_list_utils::min_posting_list_size();
133 posting_list_bytes /= 2) {
134 uint32_t aligned_posting_list_bytes =
135 (posting_list_bytes / sizeof(Hit) * sizeof(Hit));
136 ICING_VLOG(1) << IcingStringUtil::StringPrintf(
137 "Block size %u: %u", header_block_->header()->num_index_block_infos,
138 aligned_posting_list_bytes);
139
140 // Initialize free list to empty.
141 HeaderBlock::Header::IndexBlockInfo* block_info =
142 header_block_->AddIndexBlockInfo();
143 if (block_info == nullptr) {
144 // This should never happen anyways. Min block size is 4k, so adding these
145 // IndexBlockInfos should never exceed the block size.
146 return false;
147 }
148 block_info->posting_list_bytes = aligned_posting_list_bytes;
149 block_info->free_list_block_index = kInvalidBlockIndex;
150 }
151
152 // Write the header.
153 if (!header_block_->Write(block_fd_.get())) {
154 filesystem_->Truncate(block_fd_.get(), 0);
155 return false;
156 }
157 num_blocks_ = 1;
158 return true;
159 }
160
OpenHeader(int64_t file_size)161 bool FlashIndexStorage::OpenHeader(int64_t file_size) {
162 uint32_t block_size = SelectBlockSize();
163 // Read and validate header.
164 ICING_ASSIGN_OR_RETURN(
165 HeaderBlock read_header,
166 HeaderBlock::Read(filesystem_, block_fd_.get(), block_size), false);
167 if (read_header.header()->magic != HeaderBlock::Header::kMagic) {
168 ICING_LOG(ERROR) << "Index header block wrong magic";
169 return false;
170 }
171 if (file_size % read_header.header()->block_size != 0) {
172 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
173 "Index size %" PRIu64 " not a multiple of block size %u", file_size,
174 read_header.header()->block_size);
175 return false;
176 }
177
178 if (file_size < static_cast<int64_t>(read_header.header()->block_size)) {
179 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
180 "Index size %" PRIu64 " shorter than block size %u", file_size,
181 read_header.header()->block_size);
182 return false;
183 }
184
185 if (read_header.header()->block_size % getpagesize() != 0) {
186 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
187 "Block size %u is not a multiple of page size %d",
188 read_header.header()->block_size, getpagesize());
189 return false;
190 }
191 num_blocks_ = file_size / read_header.header()->block_size;
192 if (block_size != read_header.header()->block_size) {
193 // The block_size changed? That's weird. But the old block_size is still
194 // valid (it must be some multiple of the new block_size). So reinitialize
195 // with that old block size. Using the old block size means that we can
196 // still use the main index, but reads/writes won't be as efficient in terms
197 // of flash IO because the 'blocks' that we're reading are actually multiple
198 // pages long.
199 ICING_LOG(ERROR) << "Block size of existing header ("
200 << read_header.header()->block_size
201 << ") does not match the requested block size ("
202 << block_size << "). Defaulting to existing block size "
203 << read_header.header()->block_size;
204 ICING_ASSIGN_OR_RETURN(HeaderBlock read_header,
205 HeaderBlock::Read(filesystem_, block_fd_.get(),
206 read_header.header()->block_size),
207 false);
208 }
209 header_block_ = std::make_unique<HeaderBlock>(std::move(read_header));
210
211 // Check for memory alignment on posting_list_bytes. See b/29983315.
212 // The issue of potential corruption to the header could also be handled by
213 // checksumming the header block.
214 for (int i = 0; i < header_block_->header()->num_index_block_infos; ++i) {
215 int posting_list_bytes =
216 header_block_->header()->index_block_infos[i].posting_list_bytes;
217 if (posting_list_bytes % sizeof(Hit) != 0) {
218 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
219 "Posting list size misaligned, index %u, size %u, hit %zu, "
220 "file_size %" PRIu64,
221 i, header_block_->header()->index_block_infos[i].posting_list_bytes,
222 sizeof(Hit), file_size);
223 return false;
224 }
225 }
226 return true;
227 }
228
PersistToDisk()229 bool FlashIndexStorage::PersistToDisk() {
230 // First, write header.
231 if (!header_block_->Write(block_fd_.get())) {
232 ICING_LOG(ERROR) << IcingStringUtil::StringPrintf(
233 "Write index header failed: %s", strerror(errno));
234 return false;
235 }
236
237 // Then sync.
238 return filesystem_->DataSync(block_fd_.get());
239 }
240
Reset()241 libtextclassifier3::Status FlashIndexStorage::Reset() {
242 // Reset in-memory members to default values.
243 num_blocks_ = 0;
244 header_block_.reset();
245 block_fd_.reset();
246 in_memory_freelists_.clear();
247
248 // Delete the underlying file.
249 if (!filesystem_->DeleteFile(index_filename_.c_str())) {
250 return absl_ports::InternalError(
251 absl_ports::StrCat("Unable to delete file: ", index_filename_));
252 }
253
254 // Re-initialize.
255 if (!Init()) {
256 return absl_ports::InternalError(
257 "Unable to successfully read header block!");
258 }
259 return libtextclassifier3::Status::OK;
260 }
261
262 libtextclassifier3::StatusOr<PostingListHolder>
GetPostingList(PostingListIdentifier id) const263 FlashIndexStorage::GetPostingList(PostingListIdentifier id) const {
264 ICING_ASSIGN_OR_RETURN(IndexBlock block, GetIndexBlock(id.block_index()));
265 ICING_ASSIGN_OR_RETURN(
266 PostingListUsed posting_list,
267 block.GetAllocatedPostingList(id.posting_list_index()));
268 PostingListHolder holder = {std::move(posting_list), std::move(block), id};
269 return holder;
270 }
271
GetIndexBlock(int block_index) const272 libtextclassifier3::StatusOr<IndexBlock> FlashIndexStorage::GetIndexBlock(
273 int block_index) const {
274 if (block_index >= num_blocks_) {
275 return absl_ports::OutOfRangeError(IcingStringUtil::StringPrintf(
276 "Unable to create an index block at index %d when only %d blocks have "
277 "been allocated.",
278 block_index, num_blocks_));
279 }
280 off_t offset = static_cast<off_t>(block_index) * block_size();
281 return IndexBlock::CreateFromPreexistingIndexBlockRegion(
282 *filesystem_, index_filename_, offset, block_size());
283 }
284
CreateIndexBlock(int block_index,uint32_t posting_list_size) const285 libtextclassifier3::StatusOr<IndexBlock> FlashIndexStorage::CreateIndexBlock(
286 int block_index, uint32_t posting_list_size) const {
287 if (block_index >= num_blocks_) {
288 return absl_ports::OutOfRangeError(IcingStringUtil::StringPrintf(
289 "Unable to create an index block at index %d when only %d blocks have "
290 "been allocated.",
291 block_index, num_blocks_));
292 }
293 off_t offset = static_cast<off_t>(block_index) * block_size();
294 return IndexBlock::CreateFromUninitializedRegion(
295 *filesystem_, index_filename_, offset, block_size(), posting_list_size);
296 }
297
FindBestIndexBlockInfo(uint32_t posting_list_bytes) const298 int FlashIndexStorage::FindBestIndexBlockInfo(
299 uint32_t posting_list_bytes) const {
300 int i = header_block_->header()->num_index_block_infos - 1;
301 for (; i >= 0; i--) {
302 if (header_block_->header()->index_block_infos[i].posting_list_bytes >=
303 posting_list_bytes) {
304 return i;
305 }
306 }
307 return i;
308 }
309
310 libtextclassifier3::StatusOr<PostingListHolder>
GetPostingListFromInMemoryFreeList(int block_info_index)311 FlashIndexStorage::GetPostingListFromInMemoryFreeList(int block_info_index) {
312 // Get something from in memory free list.
313 ICING_ASSIGN_OR_RETURN(PostingListIdentifier posting_list_id,
314 in_memory_freelists_[block_info_index].TryPop());
315 // Remember, posting lists stored on the in-memory free list were never
316 // actually freed. So it will still contain a valid PostingListUsed. First, we
317 // need to free this posting list.
318 ICING_ASSIGN_OR_RETURN(IndexBlock block,
319 GetIndexBlock(posting_list_id.block_index()));
320 block.FreePostingList(posting_list_id.posting_list_index());
321
322 // Now, we can allocate a posting list from the same index block. It may not
323 // be the same posting list that was just freed, but that's okay.
324 ICING_ASSIGN_OR_RETURN(PostingListIndex posting_list_index,
325 block.AllocatePostingList());
326 posting_list_id =
327 PostingListIdentifier(posting_list_id.block_index(), posting_list_index,
328 posting_list_id.posting_list_index_bits());
329 ICING_ASSIGN_OR_RETURN(
330 PostingListUsed posting_list,
331 block.GetAllocatedPostingList(posting_list_id.posting_list_index()));
332 PostingListHolder holder = {std::move(posting_list), std::move(block),
333 posting_list_id};
334 return holder;
335 }
336
337 libtextclassifier3::StatusOr<PostingListHolder>
GetPostingListFromOnDiskFreeList(int block_info_index)338 FlashIndexStorage::GetPostingListFromOnDiskFreeList(int block_info_index) {
339 // Get something from the free list.
340 uint32_t block_index = header_block_->header()
341 ->index_block_infos[block_info_index]
342 .free_list_block_index;
343 if (block_index == kInvalidBlockIndex) {
344 return absl_ports::NotFoundError("No available entry in free list.");
345 }
346
347 // Get the index block
348 ICING_ASSIGN_OR_RETURN(IndexBlock block, GetIndexBlock(block_index));
349 ICING_ASSIGN_OR_RETURN(PostingListIndex posting_list_index,
350 block.AllocatePostingList());
351 PostingListIdentifier posting_list_id = PostingListIdentifier(
352 block_index, posting_list_index, block.posting_list_index_bits());
353 ICING_ASSIGN_OR_RETURN(
354 PostingListUsed posting_list,
355 block.GetAllocatedPostingList(posting_list_id.posting_list_index()));
356 if (!block.has_free_posting_lists()) {
357 RemoveFromOnDiskFreeList(block_index, block_info_index, &block);
358 }
359 PostingListHolder holder = {std::move(posting_list), std::move(block),
360 posting_list_id};
361 return holder;
362 }
363
364 libtextclassifier3::StatusOr<PostingListHolder>
AllocateNewPostingList(int block_info_index)365 FlashIndexStorage::AllocateNewPostingList(int block_info_index) {
366 uint32_t block_index = GrowIndex();
367 if (block_index == kInvalidBlockIndex) {
368 return absl_ports::ResourceExhaustedError(
369 "Unable to grow the index further!");
370 }
371 ICING_ASSIGN_OR_RETURN(
372 IndexBlock block,
373 CreateIndexBlock(block_index, header_block_->header()
374 ->index_block_infos[block_info_index]
375 .posting_list_bytes));
376 ICING_ASSIGN_OR_RETURN(PostingListIndex posting_list_index,
377 block.AllocatePostingList());
378 PostingListIdentifier posting_list_id = PostingListIdentifier(
379 block_index, posting_list_index, block.posting_list_index_bits());
380 ICING_ASSIGN_OR_RETURN(
381 PostingListUsed posting_list,
382 block.GetAllocatedPostingList(posting_list_id.posting_list_index()));
383 if (block.has_free_posting_lists()) {
384 AddToOnDiskFreeList(block_index, block_info_index, &block);
385 }
386 PostingListHolder holder = {std::move(posting_list), std::move(block),
387 posting_list_id};
388 return holder;
389 }
390
391 libtextclassifier3::StatusOr<PostingListHolder>
AllocatePostingList(uint32_t min_posting_list_bytes)392 FlashIndexStorage::AllocatePostingList(uint32_t min_posting_list_bytes) {
393 int max_block_size = IndexBlock::CalculateMaxPostingListBytes(block_size());
394 if (min_posting_list_bytes > max_block_size) {
395 return absl_ports::InvalidArgumentError(IcingStringUtil::StringPrintf(
396 "Requested posting list size %d exceeds max posting list size %d",
397 min_posting_list_bytes, max_block_size));
398 }
399 int best_block_info_index = FindBestIndexBlockInfo(min_posting_list_bytes);
400
401 auto holder_or = GetPostingListFromInMemoryFreeList(best_block_info_index);
402 if (holder_or.ok()) {
403 return std::move(holder_or).ValueOrDie();
404 }
405
406 // Nothing in memory. Look for something in the block file.
407 holder_or = GetPostingListFromOnDiskFreeList(best_block_info_index);
408 if (holder_or.ok()) {
409 return std::move(holder_or).ValueOrDie();
410 }
411
412 return AllocateNewPostingList(best_block_info_index);
413 }
414
AddToOnDiskFreeList(uint32_t block_index,int block_info_index,IndexBlock * index_block)415 void FlashIndexStorage::AddToOnDiskFreeList(uint32_t block_index,
416 int block_info_index,
417 IndexBlock* index_block) {
418 index_block->set_next_block_index(header_block_->header()
419 ->index_block_infos[block_info_index]
420 .free_list_block_index);
421 header_block_->header()
422 ->index_block_infos[block_info_index]
423 .free_list_block_index = block_index;
424 }
425
RemoveFromOnDiskFreeList(uint32_t block_index,int block_info_index,IndexBlock * index_block)426 void FlashIndexStorage::RemoveFromOnDiskFreeList(uint32_t block_index,
427 int block_info_index,
428 IndexBlock* index_block) {
429 // Cannot be used anymore. Move free ptr to the next block.
430 header_block_->header()
431 ->index_block_infos[block_info_index]
432 .free_list_block_index = index_block->next_block_index();
433 index_block->set_next_block_index(kInvalidBlockIndex);
434 }
435
FreePostingList(PostingListHolder holder)436 void FlashIndexStorage::FreePostingList(PostingListHolder holder) {
437 uint32_t posting_list_bytes = holder.block.get_posting_list_bytes();
438 int best_block_info_index = FindBestIndexBlockInfo(posting_list_bytes);
439
440 // It *should* be guaranteed elsewhere that FindBestIndexBlockInfo will not
441 // return a value in >= in_memory_freelists_, but check regardless. If it
442 // doesn't fit for some reason, then put it in the Header free list instead.
443 if (has_in_memory_freelists_ &&
444 best_block_info_index < in_memory_freelists_.size()) {
445 in_memory_freelists_[best_block_info_index].Push(holder.id);
446 } else {
447 bool was_full = !holder.block.has_free_posting_lists();
448 holder.block.FreePostingList(holder.id.posting_list_index());
449 // If this block was not already full, then it is already in the free list.
450 if (was_full) {
451 AddToOnDiskFreeList(holder.id.block_index(), best_block_info_index,
452 &holder.block);
453 }
454 }
455 }
456
GrowIndex()457 int FlashIndexStorage::GrowIndex() {
458 if (num_blocks_ >= kMaxBlockIndex) {
459 ICING_VLOG(1) << IcingStringUtil::StringPrintf("Reached max block index %u",
460 kMaxBlockIndex);
461 return kInvalidBlockIndex;
462 }
463
464 // Grow the index file.
465 if (!filesystem_->Grow(
466 block_fd_.get(),
467 static_cast<uint64_t>(num_blocks_ + 1) * block_size())) {
468 ICING_VLOG(1) << IcingStringUtil::StringPrintf(
469 "Error growing index file: %s", strerror(errno));
470 return kInvalidBlockIndex;
471 }
472
473 return num_blocks_++;
474 }
475
FlushInMemoryFreeList()476 void FlashIndexStorage::FlushInMemoryFreeList() {
477 for (int i = 0; i < in_memory_freelists_.size(); ++i) {
478 FreeList& freelist = in_memory_freelists_.at(i);
479 auto freelist_elt_or = freelist.TryPop();
480 while (freelist_elt_or.ok()) {
481 PostingListIdentifier freelist_elt = freelist_elt_or.ValueOrDie();
482 // Remember, posting lists stored on the in-memory free list were never
483 // actually freed. So it will still contain a valid PostingListUsed.
484 // First, we need to free this posting list.
485 auto block_or = GetIndexBlock(freelist_elt.block_index());
486 if (!block_or.ok()) {
487 // Can't read the block. Nothing to do here. This posting list will have
488 // to leak. Just proceed to the next freelist element.
489 freelist_elt_or = freelist.TryPop();
490 continue;
491 }
492 IndexBlock block = std::move(block_or).ValueOrDie();
493 bool was_full = !block.has_free_posting_lists();
494 block.FreePostingList(freelist_elt.posting_list_index());
495 // If this block was not already full, then it is already in the free
496 // list.
497 if (was_full) {
498 AddToOnDiskFreeList(freelist_elt.block_index(), /*block_info_index=*/i,
499 &block);
500 }
501 freelist_elt_or = freelist.TryPop();
502 }
503 }
504 }
505
GetDebugInfo(int verbosity,std::string * out) const506 void FlashIndexStorage::GetDebugInfo(int verbosity, std::string* out) const {
507 // Dump and check integrity of the index block free lists.
508 out->append("Free lists:\n");
509 for (size_t i = 0; i < header_block_->header()->num_index_block_infos; ++i) {
510 // TODO(tjbarron) Port over StringAppendFormat to migrate off of this legacy
511 // util.
512 IcingStringUtil::SStringAppendF(
513 out, 100, "Posting list bytes %u: ",
514 header_block_->header()->index_block_infos[i].posting_list_bytes);
515 uint32_t block_index =
516 header_block_->header()->index_block_infos[i].free_list_block_index;
517 int count = 0;
518 while (block_index != kInvalidBlockIndex) {
519 auto block_or = GetIndexBlock(block_index);
520 IcingStringUtil::SStringAppendF(out, 100, "%u ", block_index);
521 ++count;
522
523 if (block_or.ok()) {
524 block_index = block_or.ValueOrDie().next_block_index();
525 } else {
526 block_index = kInvalidBlockIndex;
527 }
528 }
529 IcingStringUtil::SStringAppendF(out, 100, "(count=%d)\n", count);
530 }
531
532 out->append("In memory free lists:\n");
533 if (in_memory_freelists_.size() ==
534 header_block_->header()->num_index_block_infos) {
535 for (size_t i = 0; i < in_memory_freelists_.size(); ++i) {
536 IcingStringUtil::SStringAppendF(
537 out, 100, "Posting list bytes %u %s\n",
538 header_block_->header()->index_block_infos[i].posting_list_bytes,
539 in_memory_freelists_.at(i).DebugString().c_str());
540 }
541 } else {
542 IcingStringUtil::SStringAppendF(
543 out, 100,
544 "In memory free list size %zu doesn't match index block infos size "
545 "%d\n",
546 in_memory_freelists_.size(),
547 header_block_->header()->num_index_block_infos);
548 }
549 }
550
551 // FreeList.
Push(PostingListIdentifier id)552 void FlashIndexStorage::FreeList::Push(PostingListIdentifier id) {
553 if (free_list_.size() >= kMaxSize) {
554 ICING_LOG(WARNING)
555 << "Freelist for posting lists of size (block_size / "
556 << (1u << id.posting_list_index_bits())
557 << ") has reached max size. Dropping freed posting list [block_index:"
558 << id.block_index()
559 << ", posting_list_index:" << id.posting_list_index() << "]";
560 ++num_dropped_free_list_entries_;
561 return;
562 }
563
564 free_list_.push_back(id);
565 free_list_size_high_watermark_ = std::max(
566 free_list_size_high_watermark_, static_cast<int>(free_list_.size()));
567 }
568
569 libtextclassifier3::StatusOr<PostingListIdentifier>
TryPop()570 FlashIndexStorage::FreeList::TryPop() {
571 if (free_list_.empty()) {
572 return absl_ports::NotFoundError("No available entry in free list.");
573 }
574
575 PostingListIdentifier id = free_list_.back();
576 free_list_.pop_back();
577 return id;
578 }
579
DebugString() const580 std::string FlashIndexStorage::FreeList::DebugString() const {
581 return IcingStringUtil::StringPrintf(
582 "size %zu max %d dropped %d", free_list_.size(),
583 free_list_size_high_watermark_, num_dropped_free_list_entries_);
584 }
585
586 } // namespace lib
587 } // namespace icing
588