gpu/command_buffer/common/id_allocator_test.cc

   1 // Copyright (c) 2011 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 // This file has the unit tests for the IdAllocator class.
   6
   7 #include "gpu/command_buffer/common/id_allocator.h"
   8 #include "testing/gtest/include/gtest/gtest.h"
   9
  10 namespace gpu {
  11
  12 class IdAllocatorTest : public testing::Test {
  13  protected:
  14   void SetUp() override {}
  15   void TearDown() override {}
  16
  17   IdAllocator* id_allocator() { return &id_allocator_; }
  18
  19  private:
  20   IdAllocator id_allocator_;
  21 };
  22
  23 // Checks basic functionality: AllocateID, FreeID, InUse.
  24 TEST_F(IdAllocatorTest, TestBasic) {
  25   IdAllocator *allocator = id_allocator();
  26   // Check that resource 1 is not in use
  27   EXPECT_FALSE(allocator->InUse(1));
  28
  29   // Allocate an ID, check that it's in use.
  30   ResourceId id1 = allocator->AllocateID();
  31   EXPECT_TRUE(allocator->InUse(id1));
  32
  33   // Allocate another ID, check that it's in use, and different from the first
  34   // one.
  35   ResourceId id2 = allocator->AllocateID();
  36   EXPECT_TRUE(allocator->InUse(id2));
  37   EXPECT_NE(id1, id2);
  38
  39   // Free one of the IDs, check that it's not in use any more.
  40   allocator->FreeID(id1);
  41   EXPECT_FALSE(allocator->InUse(id1));
  42
  43   // Frees the other ID, check that it's not in use any more.
  44   allocator->FreeID(id2);
  45   EXPECT_FALSE(allocator->InUse(id2));
  46 }
  47
  48 // Checks that the resource IDs are re-used after being freed.
  49 TEST_F(IdAllocatorTest, TestAdvanced) {
  50   IdAllocator *allocator = id_allocator();
  51
  52   // Allocate the highest possible ID, to make life awkward.
  53   allocator->AllocateIDAtOrAbove(~static_cast<ResourceId>(0));
  54
  55   // Allocate a significant number of resources.
  56   const unsigned int kNumResources = 100;
  57   ResourceId ids[kNumResources];
  58   for (unsigned int i = 0; i < kNumResources; ++i) {
  59     ids[i] = allocator->AllocateID();
  60     EXPECT_TRUE(allocator->InUse(ids[i]));
  61   }
  62
  63   // Check that a new allocation re-uses the resource we just freed.
  64   ResourceId id1 = ids[kNumResources / 2];
  65   allocator->FreeID(id1);
  66   EXPECT_FALSE(allocator->InUse(id1));
  67   ResourceId id2 = allocator->AllocateID();
  68   EXPECT_TRUE(allocator->InUse(id2));
  69   EXPECT_EQ(id1, id2);
  70 }
  71
  72 // Checks that we can choose our own ids and they won't be reused.
  73 TEST_F(IdAllocatorTest, MarkAsUsed) {
  74   IdAllocator* allocator = id_allocator();
  75   ResourceId id = allocator->AllocateID();
  76   allocator->FreeID(id);
  77   EXPECT_FALSE(allocator->InUse(id));
  78   EXPECT_TRUE(allocator->MarkAsUsed(id));
  79   EXPECT_TRUE(allocator->InUse(id));
  80   ResourceId id2 = allocator->AllocateID();
  81   EXPECT_NE(id, id2);
  82   EXPECT_TRUE(allocator->MarkAsUsed(id2 + 1));
  83   ResourceId id3 = allocator->AllocateID();
  84   // Checks our algorithm. If the algorithm changes this check should be
  85   // changed.
  86   EXPECT_EQ(id3, id2 + 2);
  87 }
  88
  89 // Checks AllocateIdAtOrAbove.
  90 TEST_F(IdAllocatorTest, AllocateIdAtOrAbove) {
  91   const ResourceId kOffset = 123456;
  92   IdAllocator* allocator = id_allocator();
  93   ResourceId id1 = allocator->AllocateIDAtOrAbove(kOffset);
  94   EXPECT_EQ(kOffset, id1);
  95   ResourceId id2 = allocator->AllocateIDAtOrAbove(kOffset);
  96   EXPECT_GT(id2, kOffset);
  97   ResourceId id3 = allocator->AllocateIDAtOrAbove(kOffset);
  98   EXPECT_GT(id3, kOffset);
  99 }
 100
 101 // Checks that AllocateIdAtOrAbove wraps around at the maximum value.
 102 TEST_F(IdAllocatorTest, AllocateIdAtOrAboveWrapsAround) {
 103   const ResourceId kMaxPossibleOffset = ~static_cast<ResourceId>(0);
 104   IdAllocator* allocator = id_allocator();
 105   ResourceId id1 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset);
 106   EXPECT_EQ(kMaxPossibleOffset, id1);
 107   ResourceId id2 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset);
 108   EXPECT_EQ(1u, id2);
 109   ResourceId id3 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset);
 110   EXPECT_EQ(2u, id3);
 111 }
 112
 113 TEST_F(IdAllocatorTest, RedundantFreeIsIgnored) {
 114   IdAllocator* allocator = id_allocator();
 115   ResourceId id1 = allocator->AllocateID();
 116   allocator->FreeID(0);
 117   allocator->FreeID(id1);
 118   allocator->FreeID(id1);
 119   allocator->FreeID(id1 + 1);
 120
 121   ResourceId id2 = allocator->AllocateID();
 122   ResourceId id3 = allocator->AllocateID();
 123   EXPECT_NE(id2, id3);
 124   EXPECT_NE(kInvalidResource, id2);
 125   EXPECT_NE(kInvalidResource, id3);
 126 }
 127
 128 TEST_F(IdAllocatorTest, AllocateIDRange) {
 129   const ResourceId kMaxPossibleOffset = std::numeric_limits<ResourceId>::max();
 130
 131   IdAllocator* allocator = id_allocator();
 132
 133   ResourceId id1 = allocator->AllocateIDRange(1);
 134   EXPECT_EQ(1u, id1);
 135   ResourceId id2 = allocator->AllocateIDRange(2);
 136   EXPECT_EQ(2u, id2);
 137   ResourceId id3 = allocator->AllocateIDRange(3);
 138   EXPECT_EQ(4u, id3);
 139   ResourceId id4 = allocator->AllocateID();
 140   EXPECT_EQ(7u, id4);
 141   allocator->FreeID(3);
 142   ResourceId id5 = allocator->AllocateIDRange(1);
 143   EXPECT_EQ(3u, id5);
 144   allocator->FreeID(5);
 145   allocator->FreeID(2);
 146   allocator->FreeID(4);
 147   ResourceId id6 = allocator->AllocateIDRange(2);
 148   EXPECT_EQ(4u, id6);
 149   ResourceId id7 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset);
 150   EXPECT_EQ(kMaxPossibleOffset, id7);
 151   ResourceId id8 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset);
 152   EXPECT_EQ(2u, id8);
 153   ResourceId id9 = allocator->AllocateIDRange(50);
 154   EXPECT_EQ(8u, id9);
 155   ResourceId id10 = allocator->AllocateIDRange(50);
 156   EXPECT_EQ(58u, id10);
 157   // Remove all the low-numbered ids.
 158   allocator->FreeID(1);
 159   allocator->FreeID(15);
 160   allocator->FreeIDRange(2, 107);
 161   ResourceId id11 = allocator->AllocateIDRange(100);
 162   EXPECT_EQ(1u, id11);
 163   allocator->FreeID(kMaxPossibleOffset);
 164   ResourceId id12 = allocator->AllocateIDRange(100);
 165   EXPECT_EQ(101u, id12);
 166
 167   ResourceId id13 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset - 2u);
 168   EXPECT_EQ(kMaxPossibleOffset - 2u, id13);
 169   ResourceId id14 = allocator->AllocateIDRange(3);
 170   EXPECT_EQ(201u, id14);
 171 }
 172
 173 TEST_F(IdAllocatorTest, AllocateIDRangeEndNoEffect) {
 174   const ResourceId kMaxPossibleOffset = std::numeric_limits<ResourceId>::max();
 175
 176   IdAllocator* allocator = id_allocator();
 177   ResourceId id1 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset - 2u);
 178   EXPECT_EQ(kMaxPossibleOffset - 2u, id1);
 179   ResourceId id3 = allocator->AllocateIDRange(3);
 180   EXPECT_EQ(1u, id3);
 181   ResourceId id2 = allocator->AllocateIDRange(2);
 182   EXPECT_EQ(4u, id2);
 183 }
 184
 185 TEST_F(IdAllocatorTest, AllocateFullIDRange) {
 186   const uint32_t kMaxPossibleRange = std::numeric_limits<uint32_t>::max();
 187   const ResourceId kFreedId = 555u;
 188   IdAllocator* allocator = id_allocator();
 189
 190   ResourceId id1 = allocator->AllocateIDRange(kMaxPossibleRange);
 191   EXPECT_EQ(1u, id1);
 192   ResourceId id2 = allocator->AllocateID();
 193   EXPECT_EQ(0u, id2);
 194   allocator->FreeID(kFreedId);
 195   ResourceId id3 = allocator->AllocateID();
 196   EXPECT_EQ(kFreedId, id3);
 197   ResourceId id4 = allocator->AllocateID();
 198   EXPECT_EQ(0u, id4);
 199   allocator->FreeID(kFreedId + 1u);
 200   allocator->FreeID(kFreedId + 4u);
 201   allocator->FreeID(kFreedId + 3u);
 202   allocator->FreeID(kFreedId + 5u);
 203   allocator->FreeID(kFreedId + 2u);
 204   ResourceId id5 = allocator->AllocateIDRange(5);
 205   EXPECT_EQ(kFreedId + 1u, id5);
 206 }
 207
 208 TEST_F(IdAllocatorTest, AllocateIDRangeNoWrapInRange) {
 209   const uint32_t kMaxPossibleRange = std::numeric_limits<uint32_t>::max();
 210   const ResourceId kAllocId = 10u;
 211   IdAllocator* allocator = id_allocator();
 212
 213   ResourceId id1 = allocator->AllocateIDAtOrAbove(kAllocId);
 214   EXPECT_EQ(kAllocId, id1);
 215   ResourceId id2 = allocator->AllocateIDRange(kMaxPossibleRange - 5u);
 216   EXPECT_EQ(0u, id2);
 217   ResourceId id3 = allocator->AllocateIDRange(kMaxPossibleRange - kAllocId);
 218   EXPECT_EQ(kAllocId + 1u, id3);
 219 }
 220
 221 TEST_F(IdAllocatorTest, AllocateIdMax) {
 222   const uint32_t kMaxPossibleRange = std::numeric_limits<uint32_t>::max();
 223
 224   IdAllocator* allocator = id_allocator();
 225   ResourceId id = allocator->AllocateIDRange(kMaxPossibleRange);
 226   EXPECT_EQ(1u, id);
 227   allocator->FreeIDRange(id, kMaxPossibleRange - 1u);
 228   ResourceId id2 = allocator->AllocateIDRange(kMaxPossibleRange);
 229   EXPECT_EQ(0u, id2);
 230   allocator->FreeIDRange(id, kMaxPossibleRange);
 231   ResourceId id3 = allocator->AllocateIDRange(kMaxPossibleRange);
 232   EXPECT_EQ(1u, id3);
 233 }
 234
 235 TEST_F(IdAllocatorTest, ZeroIdCases) {
 236   IdAllocator* allocator = id_allocator();
 237   EXPECT_FALSE(allocator->InUse(0));
 238   ResourceId id1 = allocator->AllocateIDAtOrAbove(0);
 239   EXPECT_NE(0u, id1);
 240   EXPECT_FALSE(allocator->InUse(0));
 241   allocator->FreeID(0);
 242   EXPECT_FALSE(allocator->InUse(0));
 243   EXPECT_TRUE(allocator->InUse(id1));
 244   allocator->FreeID(id1);
 245   EXPECT_FALSE(allocator->InUse(id1));
 246 }
 247 }  // namespace gpu