multibuffer: Evict lower blocks first after inserting multiple blocks

media/blink/multibuffer_unittest.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <stddef.h>
 #include <stdint.h>
 
 #include <deque>
 #include <string>
 #include <vector>
@@ skipping 430 matching lines @@
 
   // Make the rest of the packets pruneable.
   lru_->IncrementMaxSize(-max_size);
 
   // After another 30 seconds, everything should be pruned.
   task_runner_->Sleep(base::TimeDelta::FromSeconds(30));
   EXPECT_EQ(0, lru_->Size());
   EXPECT_FALSE(lru_->Pruneable());
 }
 
+// When seeking, multiple blocks may enter the LRU at once.  Make sure that
+// afterwards, the eviction order is lower-position-first.
+TEST_F(MultiBufferTest, LRUOnSeek) {
+  const size_t file_size = 1000 << kBlockSizeShift;
+  multibuffer_.SetFileSize(file_size);
+  multibuffer_.SetMaxWriters(2);
+  lru_->IncrementMaxSize(6);
+
+  // Choose a value that will result in a gap between "present" blocks.
+  const int64_t seek_position = kMaxWaitForWriterOffset + 4;
+
+  MultiBufferReader reader(&multibuffer_, 0, file_size,
+                           base::Callback<void(int64_t, int64_t)>());
+  reader.SetPinRange(seek_position << kBlockSizeShift, (2 * seek_position)
+                                                           << kBlockSizeShift);
+  reader.SetPreload(10000, 10000);
+
+  // Provide the first 3 blocks.  Initially, they will be pinned.
+  for (size_t block = 0; block < 3; ++block)
+    CHECK(AdvanceAll());
+  for (size_t block = 0; block < 3; ++block)
+    ASSERT_FALSE(lru_->Contains(&multibuffer_, block));
+
+  // Move the reader and create a new writer.  When providing further blocks,
+  // there will now be two ranges of "present" blocks.
+  reader.Seek(seek_position << kBlockSizeShift);
+  for (size_t block = seek_position; block < seek_position + 3; ++block)
+    CHECK(AdvanceAll());
+  for (size_t block = seek_position; block < seek_position + 3; ++block)
+    ASSERT_FALSE(lru_->Contains(&multibuffer_, block));
+
+  // Advance the reader far enough to unpin both "present" ranges.  The 6
+  // previously pinned blocks, in two ranges, will move into the LRU.
+  const auto new_seek_position = seek_position * 3;
+  reader.Seek(new_seek_position << kBlockSizeShift);
+  for (size_t block = 0; block < 3; ++block)
+    ASSERT_TRUE(lru_->Contains(&multibuffer_, block));
+  for (size_t block = seek_position; block < seek_position + 3; ++block)
+    ASSERT_TRUE(lru_->Contains(&multibuffer_, block));
+
+  // As further blocks are provided, older blocks will gradually move out of
+  // the LRU.  Make sure the lowest position blocks leave the LRU first.
+  const char* expected_order[] = {
+    "011 111",
+    "001 111",
+    "000 111",
+    "000 011",
+    "000 001",
+    "000 000",
+  };
+  for (size_t i = 0; i < 6; ++i) {
+    CHECK(AdvanceAll());
+    std::string order;
+    for (size_t block = 0; block < 3; ++block) {
+      order += lru_->Contains(&multibuffer_, block) ? "1" : "0";
+    }
+    order += " ";
+    for (size_t block = seek_position; block < seek_position + 3; ++block) {
+      order += lru_->Contains(&multibuffer_, block) ? "1" : "0";
+    }
+    EXPECT_EQ(expected_order[i], order);
+  }
+
+  lru_->IncrementMaxSize(-6);
+}
+
 class ReadHelper {
  public:
   ReadHelper(size_t end,
              size_t max_read_size,
              MultiBuffer* multibuffer,
              TestRandom* rnd)
       : pos_(0),
         end_(end),
         max_read_size_(max_read_size),
         read_size_(0),
@@ skipping 106 matching lines @@
     multibuffer_.CheckLRUState();
   }
   multibuffer_.CheckPresentState();
   while (!read_helpers.empty()) {
     delete read_helpers.back();
     read_helpers.pop_back();
   }
 }
 
 }  // namespace media