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/index-block.h"
16
17 #include "icing/text_classifier/lib3/utils/base/status.h"
18 #include "gmock/gmock.h"
19 #include "gtest/gtest.h"
20 #include "icing/file/filesystem.h"
21 #include "icing/file/memory-mapped-file.h"
22 #include "icing/index/main/posting-list-used.h"
23 #include "icing/testing/common-matchers.h"
24 #include "icing/testing/tmp-directory.h"
25
26 namespace icing {
27 namespace lib {
28
29 namespace {
30
31 static constexpr int kBlockSize = 4096;
32
CreateFileWithSize(const Filesystem & filesystem,const std::string & file,int size)33 bool CreateFileWithSize(const Filesystem& filesystem, const std::string& file,
34 int size) {
35 size_t parent_dir_end = file.find_last_of('/');
36 if (parent_dir_end == std::string::npos) {
37 return false;
38 }
39 std::string file_dir = file.substr(0, parent_dir_end);
40 return filesystem.CreateDirectoryRecursively(file_dir.c_str()) &&
41 filesystem.Grow(file.c_str(), size);
42 }
43
44 using ::testing::ElementsAreArray;
45 using ::testing::Eq;
46
TEST(IndexBlockTest,CreateFromUninitializedRegionProducesEmptyBlock)47 TEST(IndexBlockTest, CreateFromUninitializedRegionProducesEmptyBlock) {
48 constexpr int kPostingListBytes = 20;
49
50 Filesystem filesystem;
51 std::string flash_file = GetTestTempDir() + "/flash/0";
52 // Grow the file by one block for the IndexBlock to use.
53 ASSERT_TRUE(CreateFileWithSize(filesystem, flash_file, kBlockSize));
54
55 {
56 // Create an IndexBlock from this newly allocated file block.
57 ICING_ASSERT_OK_AND_ASSIGN(
58 IndexBlock block, IndexBlock::CreateFromUninitializedRegion(
59 filesystem, flash_file, /*offset=*/0, kBlockSize,
60 kPostingListBytes));
61 EXPECT_TRUE(block.has_free_posting_lists());
62 }
63 }
64
TEST(IndexBlockTest,SizeAccessorsWorkCorrectly)65 TEST(IndexBlockTest, SizeAccessorsWorkCorrectly) {
66 constexpr int kPostingListBytes1 = 20;
67
68 Filesystem filesystem;
69 std::string flash_file = GetTestTempDir() + "/flash/0";
70 // Grow the file by one block for the IndexBlock to use.
71 ASSERT_TRUE(CreateFileWithSize(filesystem, flash_file, kBlockSize));
72
73 // Create an IndexBlock from this newly allocated file block.
74 ICING_ASSERT_OK_AND_ASSIGN(
75 IndexBlock block, IndexBlock::CreateFromUninitializedRegion(
76 filesystem, flash_file, /*offset=*/0, kBlockSize,
77 kPostingListBytes1));
78 EXPECT_THAT(block.get_posting_list_bytes(), Eq(kPostingListBytes1));
79 // There should be (4096 - 12) / 20 = 204 posting lists
80 // (sizeof(BlockHeader)==12). We can store a PostingListIndex of 203 in only 8
81 // bits.
82 EXPECT_THAT(block.max_num_posting_lists(), Eq(204));
83 EXPECT_THAT(block.posting_list_index_bits(), Eq(8));
84
85 constexpr int kPostingListBytes2 = 200;
86
87 // Create an IndexBlock from this newly allocated file block.
88 ICING_ASSERT_OK_AND_ASSIGN(block, IndexBlock::CreateFromUninitializedRegion(
89 filesystem, flash_file, /*offset=*/0,
90 kBlockSize, kPostingListBytes2));
91 EXPECT_THAT(block.get_posting_list_bytes(), Eq(kPostingListBytes2));
92 // There should be (4096 - 12) / 200 = 20 posting lists
93 // (sizeof(BlockHeader)==12). We can store a PostingListIndex of 19 in only 5
94 // bits.
95 EXPECT_THAT(block.max_num_posting_lists(), Eq(20));
96 EXPECT_THAT(block.posting_list_index_bits(), Eq(5));
97 }
98
TEST(IndexBlockTest,IndexBlockChangesPersistAcrossInstances)99 TEST(IndexBlockTest, IndexBlockChangesPersistAcrossInstances) {
100 constexpr int kPostingListBytes = 2000;
101
102 Filesystem filesystem;
103 std::string flash_file = GetTestTempDir() + "/flash/0";
104 // Grow the file by one block for the IndexBlock to use.
105 ASSERT_TRUE(CreateFileWithSize(filesystem, flash_file, kBlockSize));
106
107 std::vector<Hit> test_hits{
108 Hit(/*section_id=*/2, /*document_id=*/0, Hit::kDefaultTermFrequency),
109 Hit(/*section_id=*/1, /*document_id=*/0, Hit::kDefaultTermFrequency),
110 Hit(/*section_id=*/5, /*document_id=*/1, /*term_frequency=*/99),
111 Hit(/*section_id=*/3, /*document_id=*/3, /*term_frequency=*/17),
112 Hit(/*section_id=*/10, /*document_id=*/10, Hit::kDefaultTermFrequency),
113 };
114 PostingListIndex allocated_index;
115 {
116 // Create an IndexBlock from this newly allocated file block.
117 ICING_ASSERT_OK_AND_ASSIGN(
118 IndexBlock block, IndexBlock::CreateFromUninitializedRegion(
119 filesystem, flash_file,
120 /*offset=*/0,
121 /*block_size=*/kBlockSize, kPostingListBytes));
122 // Add hits to the first posting list.
123 ICING_ASSERT_OK_AND_ASSIGN(allocated_index, block.AllocatePostingList());
124 ICING_ASSERT_OK_AND_ASSIGN(PostingListUsed pl_used,
125 block.GetAllocatedPostingList(allocated_index));
126 for (const Hit& hit : test_hits) {
127 ICING_ASSERT_OK(pl_used.PrependHit(hit));
128 }
129 EXPECT_THAT(pl_used.GetHits(), IsOkAndHolds(ElementsAreArray(
130 test_hits.rbegin(), test_hits.rend())));
131 }
132 {
133 // Create an IndexBlock from the previously allocated file block.
134 ICING_ASSERT_OK_AND_ASSIGN(
135 IndexBlock block,
136 IndexBlock::CreateFromPreexistingIndexBlockRegion(
137 filesystem, flash_file, /*offset=*/0, kBlockSize));
138 ICING_ASSERT_OK_AND_ASSIGN(PostingListUsed pl_used,
139 block.GetAllocatedPostingList(allocated_index));
140 EXPECT_THAT(pl_used.GetHits(), IsOkAndHolds(ElementsAreArray(
141 test_hits.rbegin(), test_hits.rend())));
142 EXPECT_TRUE(block.has_free_posting_lists());
143 }
144 }
145
TEST(IndexBlockTest,IndexBlockMultiplePostingLists)146 TEST(IndexBlockTest, IndexBlockMultiplePostingLists) {
147 constexpr int kPostingListBytes = 2000;
148
149 Filesystem filesystem;
150 std::string flash_file = GetTestTempDir() + "/flash/0";
151 // Grow the file by one block for the IndexBlock to use.
152 ASSERT_TRUE(CreateFileWithSize(filesystem, flash_file, kBlockSize));
153
154 std::vector<Hit> hits_in_posting_list1{
155 Hit(/*section_id=*/2, /*document_id=*/0, Hit::kDefaultTermFrequency),
156 Hit(/*section_id=*/1, /*document_id=*/0, Hit::kDefaultTermFrequency),
157 Hit(/*section_id=*/5, /*document_id=*/1, /*term_frequency=*/99),
158 Hit(/*section_id=*/3, /*document_id=*/3, /*term_frequency=*/17),
159 Hit(/*section_id=*/10, /*document_id=*/10, Hit::kDefaultTermFrequency),
160 };
161 std::vector<Hit> hits_in_posting_list2{
162 Hit(/*section_id=*/12, /*document_id=*/220, /*term_frequency=*/88),
163 Hit(/*section_id=*/17, /*document_id=*/265, Hit::kDefaultTermFrequency),
164 Hit(/*section_id=*/0, /*document_id=*/287, /*term_frequency=*/2),
165 Hit(/*section_id=*/11, /*document_id=*/306, /*term_frequency=*/12),
166 Hit(/*section_id=*/10, /*document_id=*/306, Hit::kDefaultTermFrequency),
167 };
168 PostingListIndex allocated_index_1;
169 PostingListIndex allocated_index_2;
170 {
171 // Create an IndexBlock from this newly allocated file block.
172 ICING_ASSERT_OK_AND_ASSIGN(
173 IndexBlock block, IndexBlock::CreateFromUninitializedRegion(
174 filesystem, flash_file, /*offset=*/0, kBlockSize,
175 kPostingListBytes));
176
177 // Add hits to the first posting list.
178 ICING_ASSERT_OK_AND_ASSIGN(allocated_index_1, block.AllocatePostingList());
179 ICING_ASSERT_OK_AND_ASSIGN(
180 PostingListUsed pl_used_1,
181 block.GetAllocatedPostingList(allocated_index_1));
182 for (const Hit& hit : hits_in_posting_list1) {
183 ICING_ASSERT_OK(pl_used_1.PrependHit(hit));
184 }
185 EXPECT_THAT(pl_used_1.GetHits(),
186 IsOkAndHolds(ElementsAreArray(hits_in_posting_list1.rbegin(),
187 hits_in_posting_list1.rend())));
188
189 // Add hits to the second posting list.
190 ICING_ASSERT_OK_AND_ASSIGN(allocated_index_2, block.AllocatePostingList());
191 ICING_ASSERT_OK_AND_ASSIGN(
192 PostingListUsed pl_used_2,
193 block.GetAllocatedPostingList(allocated_index_2));
194 for (const Hit& hit : hits_in_posting_list2) {
195 ICING_ASSERT_OK(pl_used_2.PrependHit(hit));
196 }
197 EXPECT_THAT(pl_used_2.GetHits(),
198 IsOkAndHolds(ElementsAreArray(hits_in_posting_list2.rbegin(),
199 hits_in_posting_list2.rend())));
200
201 EXPECT_THAT(block.AllocatePostingList(),
202 StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
203 EXPECT_FALSE(block.has_free_posting_lists());
204 }
205 {
206 // Create an IndexBlock from the previously allocated file block.
207 ICING_ASSERT_OK_AND_ASSIGN(
208 IndexBlock block,
209 IndexBlock::CreateFromPreexistingIndexBlockRegion(
210 filesystem, flash_file, /*offset=*/0, kBlockSize));
211 ICING_ASSERT_OK_AND_ASSIGN(
212 PostingListUsed pl_used_1,
213 block.GetAllocatedPostingList(allocated_index_1));
214 EXPECT_THAT(pl_used_1.GetHits(),
215 IsOkAndHolds(ElementsAreArray(hits_in_posting_list1.rbegin(),
216 hits_in_posting_list1.rend())));
217 ICING_ASSERT_OK_AND_ASSIGN(
218 PostingListUsed pl_used_2,
219 block.GetAllocatedPostingList(allocated_index_2));
220 EXPECT_THAT(pl_used_2.GetHits(),
221 IsOkAndHolds(ElementsAreArray(hits_in_posting_list2.rbegin(),
222 hits_in_posting_list2.rend())));
223 EXPECT_THAT(block.AllocatePostingList(),
224 StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
225 EXPECT_FALSE(block.has_free_posting_lists());
226 }
227 }
228
TEST(IndexBlockTest,IndexBlockReallocatingPostingLists)229 TEST(IndexBlockTest, IndexBlockReallocatingPostingLists) {
230 constexpr int kPostingListBytes = 2000;
231
232 Filesystem filesystem;
233 std::string flash_file = GetTestTempDir() + "/flash/0";
234 // Grow the file by one block for the IndexBlock to use.
235 ASSERT_TRUE(CreateFileWithSize(filesystem, flash_file, kBlockSize));
236
237 // Create an IndexBlock from this newly allocated file block.
238 ICING_ASSERT_OK_AND_ASSIGN(
239 IndexBlock block,
240 IndexBlock::CreateFromUninitializedRegion(
241 filesystem, flash_file, /*offset=*/0, kBlockSize, kPostingListBytes));
242
243 // Add hits to the first posting list.
244 std::vector<Hit> hits_in_posting_list1{
245 Hit(/*section_id=*/2, /*document_id=*/0, Hit::kDefaultTermFrequency),
246 Hit(/*section_id=*/1, /*document_id=*/0, Hit::kDefaultTermFrequency),
247 Hit(/*section_id=*/5, /*document_id=*/1, /*term_frequency=*/99),
248 Hit(/*section_id=*/3, /*document_id=*/3, /*term_frequency=*/17),
249 Hit(/*section_id=*/10, /*document_id=*/10, Hit::kDefaultTermFrequency),
250 };
251 ICING_ASSERT_OK_AND_ASSIGN(PostingListIndex allocated_index_1,
252 block.AllocatePostingList());
253 ICING_ASSERT_OK_AND_ASSIGN(PostingListUsed pl_used_1,
254 block.GetAllocatedPostingList(allocated_index_1));
255 for (const Hit& hit : hits_in_posting_list1) {
256 ICING_ASSERT_OK(pl_used_1.PrependHit(hit));
257 }
258 EXPECT_THAT(pl_used_1.GetHits(),
259 IsOkAndHolds(ElementsAreArray(hits_in_posting_list1.rbegin(),
260 hits_in_posting_list1.rend())));
261
262 // Add hits to the second posting list.
263 std::vector<Hit> hits_in_posting_list2{
264 Hit(/*section_id=*/12, /*document_id=*/220, /*term_frequency=*/88),
265 Hit(/*section_id=*/17, /*document_id=*/265, Hit::kDefaultTermFrequency),
266 Hit(/*section_id=*/0, /*document_id=*/287, /*term_frequency=*/2),
267 Hit(/*section_id=*/11, /*document_id=*/306, /*term_frequency=*/12),
268 Hit(/*section_id=*/10, /*document_id=*/306, Hit::kDefaultTermFrequency),
269 };
270 ICING_ASSERT_OK_AND_ASSIGN(PostingListIndex allocated_index_2,
271 block.AllocatePostingList());
272 ICING_ASSERT_OK_AND_ASSIGN(PostingListUsed pl_used_2,
273 block.GetAllocatedPostingList(allocated_index_2));
274 for (const Hit& hit : hits_in_posting_list2) {
275 ICING_ASSERT_OK(pl_used_2.PrependHit(hit));
276 }
277 EXPECT_THAT(pl_used_2.GetHits(),
278 IsOkAndHolds(ElementsAreArray(hits_in_posting_list2.rbegin(),
279 hits_in_posting_list2.rend())));
280
281 EXPECT_THAT(block.AllocatePostingList(),
282 StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
283 EXPECT_FALSE(block.has_free_posting_lists());
284
285 // Now free the first posting list. Then, reallocate it and fill it with a
286 // different set of hits.
287 block.FreePostingList(allocated_index_1);
288 EXPECT_TRUE(block.has_free_posting_lists());
289
290 std::vector<Hit> hits_in_posting_list3{
291 Hit(/*section_id=*/12, /*document_id=*/0, /*term_frequency=*/88),
292 Hit(/*section_id=*/17, /*document_id=*/1, Hit::kDefaultTermFrequency),
293 Hit(/*section_id=*/0, /*document_id=*/2, /*term_frequency=*/2),
294 };
295 ICING_ASSERT_OK_AND_ASSIGN(PostingListIndex allocated_index_3,
296 block.AllocatePostingList());
297 EXPECT_THAT(allocated_index_3, Eq(allocated_index_1));
298 ICING_ASSERT_OK_AND_ASSIGN(pl_used_1,
299 block.GetAllocatedPostingList(allocated_index_3));
300 for (const Hit& hit : hits_in_posting_list3) {
301 ICING_ASSERT_OK(pl_used_1.PrependHit(hit));
302 }
303 EXPECT_THAT(pl_used_1.GetHits(),
304 IsOkAndHolds(ElementsAreArray(hits_in_posting_list3.rbegin(),
305 hits_in_posting_list3.rend())));
306 EXPECT_THAT(block.AllocatePostingList(),
307 StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
308 EXPECT_FALSE(block.has_free_posting_lists());
309 }
310
TEST(IndexBlockTest,IndexBlockNextBlockIndex)311 TEST(IndexBlockTest, IndexBlockNextBlockIndex) {
312 constexpr int kPostingListBytes = 2000;
313 constexpr int kSomeBlockIndex = 22;
314
315 Filesystem filesystem;
316 std::string flash_file = GetTestTempDir() + "/flash/0";
317 // Grow the file by one block for the IndexBlock to use.
318 ASSERT_TRUE(CreateFileWithSize(filesystem, flash_file, kBlockSize));
319
320 {
321 // Create an IndexBlock from this newly allocated file block and set the
322 // next block index.
323 ICING_ASSERT_OK_AND_ASSIGN(
324 IndexBlock block, IndexBlock::CreateFromUninitializedRegion(
325 filesystem, flash_file, /*offset=*/0, kBlockSize,
326 kPostingListBytes));
327 EXPECT_THAT(block.next_block_index(), Eq(kInvalidBlockIndex));
328 block.set_next_block_index(kSomeBlockIndex);
329 EXPECT_THAT(block.next_block_index(), Eq(kSomeBlockIndex));
330 }
331 {
332 // Create an IndexBlock from this previously allocated file block and make
333 // sure that next_block_index is still set properly.
334 ICING_ASSERT_OK_AND_ASSIGN(
335 IndexBlock block,
336 IndexBlock::CreateFromPreexistingIndexBlockRegion(
337 filesystem, flash_file, /*offset=*/0, kBlockSize));
338 EXPECT_THAT(block.next_block_index(), Eq(kSomeBlockIndex));
339 }
340 {
341 // Create an IndexBlock, treating this file block as uninitialized. This
342 // reset the next_block_index to kInvalidBlockIndex.
343 ICING_ASSERT_OK_AND_ASSIGN(
344 IndexBlock block, IndexBlock::CreateFromUninitializedRegion(
345 filesystem, flash_file, /*offset=*/0, kBlockSize,
346 kPostingListBytes));
347 EXPECT_THAT(block.next_block_index(), Eq(kInvalidBlockIndex));
348 }
349 }
350
351 } // namespace
352
353 } // namespace lib
354 } // namespace icing
355