| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "base/basictypes.h" | |
| 6 #include "base/logging.h" | |
| 7 #include "net/disk_cache/blockfile/addr.h" | |
| 8 #include "net/disk_cache/blockfile/disk_format_v3.h" | |
| 9 #include "net/disk_cache/blockfile/index_table_v3.h" | |
| 10 #include "testing/gtest/include/gtest/gtest.h" | |
| 11 | |
| 12 using disk_cache::EntryCell; | |
| 13 using disk_cache::IndexCell; | |
| 14 using disk_cache::IndexTable; | |
| 15 using disk_cache::IndexTableInitData; | |
| 16 | |
| 17 namespace { | |
| 18 | |
| 19 int GetChecksum(const IndexCell& source) { | |
| 20 // Only the cell pointer is relevant. | |
| 21 disk_cache::Addr addr; | |
| 22 IndexCell* cell = const_cast<IndexCell*>(&source); | |
| 23 EntryCell entry = EntryCell::GetEntryCellForTest(0, 0, addr, cell, false); | |
| 24 | |
| 25 IndexCell result; | |
| 26 entry.SerializaForTest(&result); | |
| 27 return result.last_part >> 6; | |
| 28 } | |
| 29 | |
| 30 class MockIndexBackend : public disk_cache::IndexTableBackend { | |
| 31 public: | |
| 32 MockIndexBackend() : grow_called_(false), buffer_len_(-1) {} | |
| 33 ~MockIndexBackend() override {} | |
| 34 | |
| 35 bool grow_called() const { return grow_called_; } | |
| 36 int buffer_len() const { return buffer_len_; } | |
| 37 | |
| 38 void GrowIndex() override { grow_called_ = true; } | |
| 39 void SaveIndex(net::IOBuffer* buffer, int buffer_len) override { | |
| 40 buffer_len_ = buffer_len; | |
| 41 } | |
| 42 void DeleteCell(EntryCell cell) override {} | |
| 43 void FixCell(EntryCell cell) override {} | |
| 44 | |
| 45 private: | |
| 46 bool grow_called_; | |
| 47 int buffer_len_; | |
| 48 }; | |
| 49 | |
| 50 class TestCacheTables { | |
| 51 public: | |
| 52 // |num_entries| is the capacity of the main table. The extra table is half | |
| 53 // the size of the main table. | |
| 54 explicit TestCacheTables(int num_entries); | |
| 55 ~TestCacheTables() {} | |
| 56 | |
| 57 void GetInitData(IndexTableInitData* result); | |
| 58 void CopyFrom(const TestCacheTables& other); | |
| 59 base::Time start_time() const { return start_time_; } | |
| 60 | |
| 61 private: | |
| 62 scoped_ptr<uint64[]> main_bitmap_; | |
| 63 scoped_ptr<disk_cache::IndexBucket[]> main_table_; | |
| 64 scoped_ptr<disk_cache::IndexBucket[]> extra_table_; | |
| 65 base::Time start_time_; | |
| 66 int num_bitmap_bytes_; | |
| 67 | |
| 68 DISALLOW_COPY_AND_ASSIGN(TestCacheTables); | |
| 69 }; | |
| 70 | |
| 71 TestCacheTables::TestCacheTables(int num_entries) { | |
| 72 DCHECK_GE(num_entries, 1024); | |
| 73 DCHECK_EQ(num_entries, num_entries / 1024 * 1024); | |
| 74 main_table_.reset(new disk_cache::IndexBucket[num_entries]); | |
| 75 extra_table_.reset(new disk_cache::IndexBucket[num_entries / 2]); | |
| 76 memset(main_table_.get(), 0, num_entries * sizeof(*main_table_.get())); | |
| 77 memset(extra_table_.get(), 0, num_entries / 2 * sizeof(*extra_table_.get())); | |
| 78 | |
| 79 // We allow IndexBitmap smaller than a page because the code should not really | |
| 80 // depend on that. | |
| 81 num_bitmap_bytes_ = (num_entries + num_entries / 2) / 8; | |
| 82 size_t required_size = sizeof(disk_cache::IndexHeaderV3) + num_bitmap_bytes_; | |
| 83 main_bitmap_.reset(new uint64[required_size / sizeof(uint64)]); | |
| 84 memset(main_bitmap_.get(), 0, required_size); | |
| 85 | |
| 86 disk_cache::IndexHeaderV3* header = | |
| 87 reinterpret_cast<disk_cache::IndexHeaderV3*>(main_bitmap_.get()); | |
| 88 | |
| 89 header->magic = disk_cache::kIndexMagicV3; | |
| 90 header->version = disk_cache::kVersion3; | |
| 91 header->table_len = num_entries + num_entries / 2; | |
| 92 header->max_bucket = num_entries / 4 - 1; | |
| 93 | |
| 94 start_time_ = base::Time::Now(); | |
| 95 header->create_time = start_time_.ToInternalValue(); | |
| 96 header->base_time = | |
| 97 (start_time_ - base::TimeDelta::FromDays(20)).ToInternalValue(); | |
| 98 | |
| 99 if (num_entries < 64 * 1024) | |
| 100 header->flags = disk_cache::SMALL_CACHE; | |
| 101 } | |
| 102 | |
| 103 void TestCacheTables::GetInitData(IndexTableInitData* result) { | |
| 104 result->index_bitmap = | |
| 105 reinterpret_cast<disk_cache::IndexBitmap*>(main_bitmap_.get()); | |
| 106 | |
| 107 result->main_table = main_table_.get(); | |
| 108 result->extra_table = extra_table_.get(); | |
| 109 | |
| 110 result->backup_header.reset(new disk_cache::IndexHeaderV3); | |
| 111 memcpy(result->backup_header.get(), result->index_bitmap, | |
| 112 sizeof(result->index_bitmap->header)); | |
| 113 | |
| 114 result->backup_bitmap.reset(new uint32[num_bitmap_bytes_ / sizeof(uint32)]); | |
| 115 memcpy(result->backup_bitmap.get(), result->index_bitmap->bitmap, | |
| 116 num_bitmap_bytes_); | |
| 117 } | |
| 118 | |
| 119 void TestCacheTables::CopyFrom(const TestCacheTables& other) { | |
| 120 disk_cache::IndexBitmap* this_bitmap = | |
| 121 reinterpret_cast<disk_cache::IndexBitmap*>(main_bitmap_.get()); | |
| 122 disk_cache::IndexBitmap* other_bitmap = | |
| 123 reinterpret_cast<disk_cache::IndexBitmap*>(other.main_bitmap_.get()); | |
| 124 | |
| 125 DCHECK_GE(this_bitmap->header.table_len, other_bitmap->header.table_len); | |
| 126 DCHECK_GE(num_bitmap_bytes_, other.num_bitmap_bytes_); | |
| 127 | |
| 128 memcpy(this_bitmap->bitmap, other_bitmap->bitmap, other.num_bitmap_bytes_); | |
| 129 | |
| 130 int main_table_buckets = (other_bitmap->header.table_len * 2 / 3) / 4; | |
| 131 int extra_table_buckets = (other_bitmap->header.table_len * 1 / 3) / 4; | |
| 132 memcpy(main_table_.get(), other.main_table_.get(), | |
| 133 main_table_buckets * sizeof(disk_cache::IndexBucket)); | |
| 134 memcpy(extra_table_.get(), other.extra_table_.get(), | |
| 135 extra_table_buckets * sizeof(disk_cache::IndexBucket)); | |
| 136 | |
| 137 this_bitmap->header.num_entries = other_bitmap->header.num_entries; | |
| 138 this_bitmap->header.used_cells = other_bitmap->header.used_cells; | |
| 139 this_bitmap->header.max_bucket = other_bitmap->header.max_bucket; | |
| 140 this_bitmap->header.create_time = other_bitmap->header.create_time; | |
| 141 this_bitmap->header.base_time = other_bitmap->header.base_time; | |
| 142 this_bitmap->header.flags = other_bitmap->header.flags; | |
| 143 start_time_ = other.start_time_; | |
| 144 } | |
| 145 | |
| 146 } // namespace | |
| 147 | |
| 148 TEST(DiskCacheIndexTable, EntryCell) { | |
| 149 uint32 hash = 0x55aa6699; | |
| 150 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, 0x4531); | |
| 151 bool small_table = true; | |
| 152 int cell_num = 88; | |
| 153 int reuse = 6; | |
| 154 int timestamp = 123456; | |
| 155 disk_cache::EntryState state = disk_cache::ENTRY_MODIFIED; | |
| 156 disk_cache::EntryGroup group = disk_cache::ENTRY_HIGH_USE; | |
| 157 | |
| 158 for (int i = 0; i < 4; i++) { | |
| 159 SCOPED_TRACE(i); | |
| 160 EntryCell entry = EntryCell::GetEntryCellForTest(cell_num, hash, addr, NULL, | |
| 161 small_table); | |
| 162 EXPECT_EQ(disk_cache::ENTRY_NO_USE, entry.GetGroup()); | |
| 163 EXPECT_EQ(disk_cache::ENTRY_NEW, entry.GetState()); | |
| 164 | |
| 165 entry.SetGroup(group); | |
| 166 entry.SetState(state); | |
| 167 entry.SetReuse(reuse); | |
| 168 entry.SetTimestamp(timestamp); | |
| 169 | |
| 170 EXPECT_TRUE(entry.IsValid()); | |
| 171 EXPECT_EQ(hash, entry.hash()); | |
| 172 EXPECT_EQ(cell_num, entry.cell_num()); | |
| 173 EXPECT_EQ(addr.value(), entry.GetAddress().value()); | |
| 174 | |
| 175 EXPECT_EQ(group, entry.GetGroup()); | |
| 176 EXPECT_EQ(state, entry.GetState()); | |
| 177 EXPECT_EQ(reuse, entry.GetReuse()); | |
| 178 EXPECT_EQ(timestamp, entry.GetTimestamp()); | |
| 179 | |
| 180 // Store the data and read it again. | |
| 181 IndexCell cell; | |
| 182 entry.SerializaForTest(&cell); | |
| 183 | |
| 184 EntryCell entry2 = EntryCell::GetEntryCellForTest(cell_num, hash, addr, | |
| 185 &cell, small_table); | |
| 186 | |
| 187 EXPECT_EQ(addr.value(), entry2.GetAddress().value()); | |
| 188 | |
| 189 EXPECT_EQ(group, entry2.GetGroup()); | |
| 190 EXPECT_EQ(state, entry2.GetState()); | |
| 191 EXPECT_EQ(reuse, entry2.GetReuse()); | |
| 192 EXPECT_EQ(timestamp, entry2.GetTimestamp()); | |
| 193 | |
| 194 small_table = !small_table; | |
| 195 if (i == 1) { | |
| 196 hash = ~hash; | |
| 197 cell_num *= 5; | |
| 198 state = disk_cache::ENTRY_USED; | |
| 199 group = disk_cache::ENTRY_EVICTED; | |
| 200 addr = disk_cache::Addr(disk_cache::BLOCK_EVICTED, 1, 6, 0x18a5); | |
| 201 reuse = 15; // 4 bits | |
| 202 timestamp = 0xfffff; // 20 bits. | |
| 203 } | |
| 204 } | |
| 205 } | |
| 206 | |
| 207 // Goes over some significant values for a cell's sum. | |
| 208 TEST(DiskCacheIndexTable, EntryCellSum) { | |
| 209 IndexCell source; | |
| 210 source.Clear(); | |
| 211 EXPECT_EQ(0, GetChecksum(source)); | |
| 212 | |
| 213 source.first_part++; | |
| 214 EXPECT_EQ(1, GetChecksum(source)); | |
| 215 | |
| 216 source.Clear(); | |
| 217 source.last_part = 0x80; | |
| 218 EXPECT_EQ(0, GetChecksum(source)); | |
| 219 | |
| 220 source.last_part = 0x55; | |
| 221 EXPECT_EQ(3, GetChecksum(source)); | |
| 222 | |
| 223 source.first_part = 0x555555; | |
| 224 EXPECT_EQ(2, GetChecksum(source)); | |
| 225 | |
| 226 source.last_part = 0; | |
| 227 EXPECT_EQ(1, GetChecksum(source)); | |
| 228 | |
| 229 source.first_part = GG_UINT64_C(0x8000000080000000); | |
| 230 EXPECT_EQ(0, GetChecksum(source)); | |
| 231 | |
| 232 source.first_part = GG_UINT64_C(0x4000000040000000); | |
| 233 EXPECT_EQ(2, GetChecksum(source)); | |
| 234 | |
| 235 source.first_part = GG_UINT64_C(0x200000020000000); | |
| 236 EXPECT_EQ(1, GetChecksum(source)); | |
| 237 | |
| 238 source.first_part = GG_UINT64_C(0x100000010010000); | |
| 239 EXPECT_EQ(3, GetChecksum(source)); | |
| 240 | |
| 241 source.first_part = 0x80008000; | |
| 242 EXPECT_EQ(0, GetChecksum(source)); | |
| 243 | |
| 244 source.first_part = GG_UINT64_C(0x800000008000); | |
| 245 EXPECT_EQ(1, GetChecksum(source)); | |
| 246 | |
| 247 source.first_part = 0x8080; | |
| 248 EXPECT_EQ(0, GetChecksum(source)); | |
| 249 | |
| 250 source.first_part = 0x800080; | |
| 251 EXPECT_EQ(1, GetChecksum(source)); | |
| 252 | |
| 253 source.first_part = 0x88; | |
| 254 EXPECT_EQ(0, GetChecksum(source)); | |
| 255 | |
| 256 source.first_part = 0x808; | |
| 257 EXPECT_EQ(1, GetChecksum(source)); | |
| 258 | |
| 259 source.first_part = 0xA; | |
| 260 EXPECT_EQ(0, GetChecksum(source)); | |
| 261 | |
| 262 source.first_part = 0x22; | |
| 263 EXPECT_EQ(1, GetChecksum(source)); | |
| 264 } | |
| 265 | |
| 266 TEST(DiskCacheIndexTable, Basics) { | |
| 267 TestCacheTables cache(1024); | |
| 268 IndexTableInitData init_data; | |
| 269 cache.GetInitData(&init_data); | |
| 270 | |
| 271 IndexTable index(NULL); | |
| 272 index.Init(&init_data); | |
| 273 | |
| 274 // Write some entries. | |
| 275 disk_cache::CellList entries; | |
| 276 for (int i = 0; i < 250; i++) { | |
| 277 SCOPED_TRACE(i); | |
| 278 uint32 hash = i * i * 1111 + i * 11; | |
| 279 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 13 + 1); | |
| 280 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 281 EXPECT_TRUE(entry.IsValid()); | |
| 282 | |
| 283 disk_cache::CellInfo info = { hash, addr }; | |
| 284 entries.push_back(info); | |
| 285 } | |
| 286 | |
| 287 // Read them back. | |
| 288 for (size_t i = 0; i < entries.size(); i++) { | |
| 289 SCOPED_TRACE(i); | |
| 290 uint32 hash = entries[i].hash; | |
| 291 disk_cache::Addr addr = entries[i].address; | |
| 292 | |
| 293 disk_cache::EntrySet found_entries = index.LookupEntries(hash); | |
| 294 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 295 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 296 EXPECT_EQ(hash, found_entries.cells[0].hash()); | |
| 297 EXPECT_EQ(addr.value(), found_entries.cells[0].GetAddress().value()); | |
| 298 | |
| 299 EntryCell entry = index.FindEntryCell(hash, addr); | |
| 300 EXPECT_TRUE(entry.IsValid()); | |
| 301 EXPECT_EQ(hash, entry.hash()); | |
| 302 EXPECT_EQ(addr.value(), entry.GetAddress().value()); | |
| 303 | |
| 304 // Delete the first 100 entries. | |
| 305 if (i < 100) | |
| 306 index.SetSate(hash, addr, disk_cache::ENTRY_DELETED); | |
| 307 } | |
| 308 | |
| 309 // See what we have now. | |
| 310 for (size_t i = 0; i < entries.size(); i++) { | |
| 311 SCOPED_TRACE(i); | |
| 312 uint32 hash = entries[i].hash; | |
| 313 disk_cache::Addr addr = entries[i].address; | |
| 314 | |
| 315 disk_cache::EntrySet found_entries = index.LookupEntries(hash); | |
| 316 if (i < 100) { | |
| 317 EXPECT_EQ(0u, found_entries.cells.size()); | |
| 318 } else { | |
| 319 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 320 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 321 EXPECT_EQ(hash, found_entries.cells[0].hash()); | |
| 322 EXPECT_EQ(addr.value(), found_entries.cells[0].GetAddress().value()); | |
| 323 } | |
| 324 } | |
| 325 } | |
| 326 | |
| 327 // Tests handling of multiple entries with the same hash. | |
| 328 TEST(DiskCacheIndexTable, SameHash) { | |
| 329 TestCacheTables cache(1024); | |
| 330 IndexTableInitData init_data; | |
| 331 cache.GetInitData(&init_data); | |
| 332 | |
| 333 IndexTable index(NULL); | |
| 334 index.Init(&init_data); | |
| 335 | |
| 336 disk_cache::CellList entries; | |
| 337 uint32 hash = 0x55aa55bb; | |
| 338 for (int i = 0; i < 6; i++) { | |
| 339 SCOPED_TRACE(i); | |
| 340 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 13 + 1); | |
| 341 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 342 EXPECT_TRUE(entry.IsValid()); | |
| 343 | |
| 344 disk_cache::CellInfo info = { hash, addr }; | |
| 345 entries.push_back(info); | |
| 346 } | |
| 347 | |
| 348 disk_cache::EntrySet found_entries = index.LookupEntries(hash); | |
| 349 EXPECT_EQ(0, found_entries.evicted_count); | |
| 350 ASSERT_EQ(6u, found_entries.cells.size()); | |
| 351 | |
| 352 for (size_t i = 0; i < found_entries.cells.size(); i++) { | |
| 353 SCOPED_TRACE(i); | |
| 354 EXPECT_EQ(entries[i].address, found_entries.cells[i].GetAddress()); | |
| 355 } | |
| 356 | |
| 357 // Now verify handling of entries on different states. | |
| 358 index.SetSate(hash, entries[0].address, disk_cache::ENTRY_DELETED); | |
| 359 index.SetSate(hash, entries[1].address, disk_cache::ENTRY_DELETED); | |
| 360 index.SetSate(hash, entries[2].address, disk_cache::ENTRY_USED); | |
| 361 index.SetSate(hash, entries[3].address, disk_cache::ENTRY_USED); | |
| 362 index.SetSate(hash, entries[4].address, disk_cache::ENTRY_USED); | |
| 363 | |
| 364 found_entries = index.LookupEntries(hash); | |
| 365 EXPECT_EQ(0, found_entries.evicted_count); | |
| 366 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 367 | |
| 368 index.SetSate(hash, entries[3].address, disk_cache::ENTRY_OPEN); | |
| 369 index.SetSate(hash, entries[4].address, disk_cache::ENTRY_OPEN); | |
| 370 | |
| 371 found_entries = index.LookupEntries(hash); | |
| 372 EXPECT_EQ(0, found_entries.evicted_count); | |
| 373 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 374 | |
| 375 index.SetSate(hash, entries[4].address, disk_cache::ENTRY_MODIFIED); | |
| 376 | |
| 377 found_entries = index.LookupEntries(hash); | |
| 378 EXPECT_EQ(0, found_entries.evicted_count); | |
| 379 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 380 | |
| 381 index.SetSate(hash, entries[1].address, disk_cache::ENTRY_FREE); | |
| 382 | |
| 383 found_entries = index.LookupEntries(hash); | |
| 384 EXPECT_EQ(0, found_entries.evicted_count); | |
| 385 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 386 | |
| 387 // FindEntryCell should not see deleted entries. | |
| 388 EntryCell entry = index.FindEntryCell(hash, entries[0].address); | |
| 389 EXPECT_FALSE(entry.IsValid()); | |
| 390 | |
| 391 // A free entry is gone. | |
| 392 entry = index.FindEntryCell(hash, entries[1].address); | |
| 393 EXPECT_FALSE(entry.IsValid()); | |
| 394 | |
| 395 // Locate a used entry, and evict it. This is not really a correct operation | |
| 396 // in that an existing cell doesn't transition to evicted; instead a new cell | |
| 397 // for the evicted entry (on a different block file) should be created. Still, | |
| 398 // at least evicted_count would be valid. | |
| 399 entry = index.FindEntryCell(hash, entries[2].address); | |
| 400 EXPECT_TRUE(entry.IsValid()); | |
| 401 entry.SetGroup(disk_cache::ENTRY_EVICTED); | |
| 402 index.Save(&entry); | |
| 403 | |
| 404 found_entries = index.LookupEntries(hash); | |
| 405 EXPECT_EQ(1, found_entries.evicted_count); | |
| 406 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 407 | |
| 408 // Now use the proper way to get an evicted entry. | |
| 409 disk_cache::Addr addr2(disk_cache::BLOCK_EVICTED, 1, 6, 6); // Any address. | |
| 410 entry = index.CreateEntryCell(hash, addr2); | |
| 411 EXPECT_TRUE(entry.IsValid()); | |
| 412 EXPECT_EQ(disk_cache::ENTRY_EVICTED, entry.GetGroup()); | |
| 413 | |
| 414 found_entries = index.LookupEntries(hash); | |
| 415 EXPECT_EQ(2, found_entries.evicted_count); | |
| 416 ASSERT_EQ(5u, found_entries.cells.size()); | |
| 417 } | |
| 418 | |
| 419 TEST(DiskCacheIndexTable, Timestamps) { | |
| 420 TestCacheTables cache(1024); | |
| 421 IndexTableInitData init_data; | |
| 422 cache.GetInitData(&init_data); | |
| 423 | |
| 424 IndexTable index(NULL); | |
| 425 index.Init(&init_data); | |
| 426 | |
| 427 // The granularity should be 1 minute. | |
| 428 int timestamp1 = index.CalculateTimestamp(cache.start_time()); | |
| 429 int timestamp2 = index.CalculateTimestamp(cache.start_time() + | |
| 430 base::TimeDelta::FromSeconds(59)); | |
| 431 EXPECT_EQ(timestamp1, timestamp2); | |
| 432 | |
| 433 int timestamp3 = index.CalculateTimestamp(cache.start_time() + | |
| 434 base::TimeDelta::FromSeconds(61)); | |
| 435 EXPECT_EQ(timestamp1 + 1, timestamp3); | |
| 436 | |
| 437 int timestamp4 = index.CalculateTimestamp(cache.start_time() + | |
| 438 base::TimeDelta::FromSeconds(119)); | |
| 439 EXPECT_EQ(timestamp1 + 1, timestamp4); | |
| 440 | |
| 441 int timestamp5 = index.CalculateTimestamp(cache.start_time() + | |
| 442 base::TimeDelta::FromSeconds(121)); | |
| 443 EXPECT_EQ(timestamp1 + 2, timestamp5); | |
| 444 | |
| 445 int timestamp6 = index.CalculateTimestamp(cache.start_time() - | |
| 446 base::TimeDelta::FromSeconds(30)); | |
| 447 EXPECT_EQ(timestamp1 - 1, timestamp6); | |
| 448 | |
| 449 // The base should be 20 days in the past. | |
| 450 int timestamp7 = index.CalculateTimestamp(cache.start_time() - | |
| 451 base::TimeDelta::FromDays(20)); | |
| 452 int timestamp8 = index.CalculateTimestamp(cache.start_time() - | |
| 453 base::TimeDelta::FromDays(35)); | |
| 454 EXPECT_EQ(timestamp7, timestamp8); | |
| 455 EXPECT_EQ(0, timestamp8); | |
| 456 | |
| 457 int timestamp9 = index.CalculateTimestamp(cache.start_time() - | |
| 458 base::TimeDelta::FromDays(19)); | |
| 459 EXPECT_NE(0, timestamp9); | |
| 460 } | |
| 461 | |
| 462 // Tests GetOldest and GetNextCells. | |
| 463 TEST(DiskCacheIndexTable, Iterations) { | |
| 464 TestCacheTables cache(1024); | |
| 465 IndexTableInitData init_data; | |
| 466 cache.GetInitData(&init_data); | |
| 467 | |
| 468 IndexTable index(NULL); | |
| 469 index.Init(&init_data); | |
| 470 | |
| 471 base::Time time = cache.start_time(); | |
| 472 | |
| 473 // Write some entries. | |
| 474 disk_cache::CellList entries; | |
| 475 for (int i = 0; i < 44; i++) { | |
| 476 SCOPED_TRACE(i); | |
| 477 uint32 hash = i; // The entries will be ordered on the table. | |
| 478 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 13 + 1); | |
| 479 if (i < 10 || i == 40) | |
| 480 addr = disk_cache::Addr(disk_cache::BLOCK_EVICTED, 1, 6, i * 13 + 1); | |
| 481 | |
| 482 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 483 EXPECT_TRUE(entry.IsValid()); | |
| 484 | |
| 485 disk_cache::CellInfo info = { hash, addr }; | |
| 486 entries.push_back(info); | |
| 487 | |
| 488 if (i < 10 || i == 40) { | |
| 489 // Do nothing. These are ENTRY_EVICTED by default. | |
| 490 } else if (i < 20 || i == 41) { | |
| 491 entry.SetGroup(disk_cache::ENTRY_HIGH_USE); | |
| 492 index.Save(&entry); | |
| 493 } else if (i < 30 || i == 42) { | |
| 494 entry.SetGroup(disk_cache::ENTRY_LOW_USE); | |
| 495 index.Save(&entry); | |
| 496 } | |
| 497 | |
| 498 // Entries [30,39] and 43 are marked as ENTRY_NO_USE (the default). | |
| 499 | |
| 500 if (!(i % 10)) | |
| 501 time += base::TimeDelta::FromMinutes(1); | |
| 502 | |
| 503 index.UpdateTime(hash, addr, time); | |
| 504 } | |
| 505 | |
| 506 // Get the oldest entries of each group. | |
| 507 disk_cache::IndexIterator no_use, low_use, high_use; | |
| 508 index.GetOldest(&no_use, &low_use, &high_use); | |
| 509 ASSERT_EQ(10u, no_use.cells.size()); | |
| 510 ASSERT_EQ(10u, low_use.cells.size()); | |
| 511 ASSERT_EQ(10u, high_use.cells.size()); | |
| 512 | |
| 513 EXPECT_EQ(entries[10].hash, high_use.cells[0].hash); | |
| 514 EXPECT_EQ(entries[19].hash, high_use.cells[9].hash); | |
| 515 EXPECT_EQ(entries[20].hash, low_use.cells[0].hash); | |
| 516 EXPECT_EQ(entries[29].hash, low_use.cells[9].hash); | |
| 517 EXPECT_EQ(entries[30].hash, no_use.cells[0].hash); | |
| 518 EXPECT_EQ(entries[39].hash, no_use.cells[9].hash); | |
| 519 | |
| 520 // Now start an iteration from the head (most recent entry). | |
| 521 disk_cache::IndexIterator iterator; | |
| 522 iterator.timestamp = index.CalculateTimestamp(time) + 1; | |
| 523 iterator.forward = false; // Back in time. | |
| 524 | |
| 525 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 526 ASSERT_EQ(3u, iterator.cells.size()); | |
| 527 EXPECT_EQ(entries[41].hash, iterator.cells[0].hash); | |
| 528 EXPECT_EQ(entries[42].hash, iterator.cells[1].hash); | |
| 529 EXPECT_EQ(entries[43].hash, iterator.cells[2].hash); | |
| 530 | |
| 531 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 532 ASSERT_EQ(10u, iterator.cells.size()); | |
| 533 EXPECT_EQ(entries[30].hash, iterator.cells[0].hash); | |
| 534 EXPECT_EQ(entries[39].hash, iterator.cells[9].hash); | |
| 535 | |
| 536 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 537 ASSERT_EQ(10u, iterator.cells.size()); | |
| 538 EXPECT_EQ(entries[20].hash, iterator.cells[0].hash); | |
| 539 EXPECT_EQ(entries[29].hash, iterator.cells[9].hash); | |
| 540 | |
| 541 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 542 ASSERT_EQ(10u, iterator.cells.size()); | |
| 543 EXPECT_EQ(entries[10].hash, iterator.cells[0].hash); | |
| 544 EXPECT_EQ(entries[19].hash, iterator.cells[9].hash); | |
| 545 | |
| 546 ASSERT_FALSE(index.GetNextCells(&iterator)); | |
| 547 | |
| 548 // Now start an iteration from the tail (oldest entry). | |
| 549 iterator.timestamp = 0; | |
| 550 iterator.forward = true; | |
| 551 | |
| 552 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 553 ASSERT_EQ(10u, iterator.cells.size()); | |
| 554 EXPECT_EQ(entries[10].hash, iterator.cells[0].hash); | |
| 555 EXPECT_EQ(entries[19].hash, iterator.cells[9].hash); | |
| 556 | |
| 557 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 558 ASSERT_EQ(10u, iterator.cells.size()); | |
| 559 EXPECT_EQ(entries[20].hash, iterator.cells[0].hash); | |
| 560 EXPECT_EQ(entries[29].hash, iterator.cells[9].hash); | |
| 561 | |
| 562 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 563 ASSERT_EQ(10u, iterator.cells.size()); | |
| 564 EXPECT_EQ(entries[30].hash, iterator.cells[0].hash); | |
| 565 EXPECT_EQ(entries[39].hash, iterator.cells[9].hash); | |
| 566 | |
| 567 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 568 ASSERT_EQ(3u, iterator.cells.size()); | |
| 569 EXPECT_EQ(entries[41].hash, iterator.cells[0].hash); | |
| 570 EXPECT_EQ(entries[42].hash, iterator.cells[1].hash); | |
| 571 EXPECT_EQ(entries[43].hash, iterator.cells[2].hash); | |
| 572 } | |
| 573 | |
| 574 // Tests doubling of the table. | |
| 575 TEST(DiskCacheIndexTable, Doubling) { | |
| 576 IndexTable index(NULL); | |
| 577 int size = 1024; | |
| 578 scoped_ptr<TestCacheTables> cache(new TestCacheTables(size)); | |
| 579 int entry_id = 0; | |
| 580 disk_cache::CellList entries; | |
| 581 | |
| 582 // Go from 1024 to 256k cells. | |
| 583 for (int resizes = 0; resizes <= 8; resizes++) { | |
| 584 scoped_ptr<TestCacheTables> old_cache(cache.Pass()); | |
| 585 cache.reset(new TestCacheTables(size)); | |
| 586 cache.get()->CopyFrom(*old_cache.get()); | |
| 587 | |
| 588 IndexTableInitData init_data; | |
| 589 cache.get()->GetInitData(&init_data); | |
| 590 index.Init(&init_data); | |
| 591 | |
| 592 // Write some entries. | |
| 593 for (int i = 0; i < 250; i++, entry_id++) { | |
| 594 SCOPED_TRACE(entry_id); | |
| 595 uint32 hash = entry_id * i * 321 + entry_id * 13; | |
| 596 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, entry_id * 17 + 1); | |
| 597 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 598 EXPECT_TRUE(entry.IsValid()); | |
| 599 | |
| 600 disk_cache::CellInfo info = { hash, addr }; | |
| 601 entries.push_back(info); | |
| 602 } | |
| 603 size *= 2; | |
| 604 } | |
| 605 | |
| 606 // Access all the entries. | |
| 607 for (size_t i = 0; i < entries.size(); i++) { | |
| 608 SCOPED_TRACE(i); | |
| 609 disk_cache::EntrySet found_entries = index.LookupEntries(entries[i].hash); | |
| 610 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 611 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 612 } | |
| 613 } | |
| 614 | |
| 615 // Tests bucket chaining when growing the index. | |
| 616 TEST(DiskCacheIndexTable, BucketChains) { | |
| 617 IndexTable index(NULL); | |
| 618 int size = 1024; | |
| 619 scoped_ptr<TestCacheTables> cache(new TestCacheTables(size)); | |
| 620 disk_cache::CellList entries; | |
| 621 | |
| 622 IndexTableInitData init_data; | |
| 623 cache.get()->GetInitData(&init_data); | |
| 624 index.Init(&init_data); | |
| 625 | |
| 626 // Write some entries. | |
| 627 for (int i = 0; i < 8; i++) { | |
| 628 SCOPED_TRACE(i); | |
| 629 uint32 hash = i * 256; | |
| 630 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 7 + 1); | |
| 631 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 632 EXPECT_TRUE(entry.IsValid()); | |
| 633 | |
| 634 disk_cache::CellInfo info = { hash, addr }; | |
| 635 entries.push_back(info); | |
| 636 } | |
| 637 | |
| 638 // Double the size. | |
| 639 scoped_ptr<TestCacheTables> old_cache(cache.Pass()); | |
| 640 cache.reset(new TestCacheTables(size * 2)); | |
| 641 cache.get()->CopyFrom(*old_cache.get()); | |
| 642 | |
| 643 cache.get()->GetInitData(&init_data); | |
| 644 index.Init(&init_data); | |
| 645 | |
| 646 // Write more entries, starting with the upper half of the table. | |
| 647 for (int i = 9; i < 11; i++) { | |
| 648 SCOPED_TRACE(i); | |
| 649 uint32 hash = i * 256; | |
| 650 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 7 + 1); | |
| 651 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 652 EXPECT_TRUE(entry.IsValid()); | |
| 653 | |
| 654 disk_cache::CellInfo info = { hash, addr }; | |
| 655 entries.push_back(info); | |
| 656 } | |
| 657 | |
| 658 // Access all the entries. | |
| 659 for (size_t i = 0; i < entries.size(); i++) { | |
| 660 SCOPED_TRACE(i); | |
| 661 disk_cache::EntrySet found_entries = index.LookupEntries(entries[i].hash); | |
| 662 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 663 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 664 } | |
| 665 } | |
| 666 | |
| 667 // Tests that GrowIndex is called. | |
| 668 TEST(DiskCacheIndexTable, GrowIndex) { | |
| 669 TestCacheTables cache(1024); | |
| 670 IndexTableInitData init_data; | |
| 671 cache.GetInitData(&init_data); | |
| 672 MockIndexBackend backend; | |
| 673 | |
| 674 IndexTable index(&backend); | |
| 675 index.Init(&init_data); | |
| 676 | |
| 677 // Write some entries. | |
| 678 for (int i = 0; i < 512; i++) { | |
| 679 SCOPED_TRACE(i); | |
| 680 uint32 hash = 0; | |
| 681 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i + 1); | |
| 682 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 683 EXPECT_TRUE(entry.IsValid()); | |
| 684 } | |
| 685 | |
| 686 EXPECT_TRUE(backend.grow_called()); | |
| 687 } | |
| 688 | |
| 689 TEST(DiskCacheIndexTable, SaveIndex) { | |
| 690 TestCacheTables cache(1024); | |
| 691 IndexTableInitData init_data; | |
| 692 cache.GetInitData(&init_data); | |
| 693 MockIndexBackend backend; | |
| 694 | |
| 695 IndexTable index(&backend); | |
| 696 index.Init(&init_data); | |
| 697 | |
| 698 uint32 hash = 0; | |
| 699 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, 6); | |
| 700 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 701 EXPECT_TRUE(entry.IsValid()); | |
| 702 | |
| 703 index.OnBackupTimer(); | |
| 704 int expected = (1024 + 512) / 8 + sizeof(disk_cache::IndexHeaderV3); | |
| 705 EXPECT_EQ(expected, backend.buffer_len()); | |
| 706 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master