Fix alignment issue of ContiguousContainer

cc/base/contiguous_container_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 "cc/base/contiguous_container.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace cc {
 namespace {
 
 struct Point2D {
   Point2D() : Point2D(0, 0) {}
   Point2D(int x, int y) : x(x), y(y) {}
   int x, y;
 };
 
 struct Point3D : public Point2D {
   Point3D() : Point3D(0, 0, 0) {}
   Point3D(int x, int y, int z) : Point2D(x, y), z(z) {}
   int z;
 };
 
 // Maximum size of a subclass of Point2D.
 static const size_t kMaxPointSize = sizeof(Point3D);
 
-// Alignment for Point2D and its subclasses.
-static const size_t kPointAlignment = sizeof(int);
-
 // How many elements to use for tests with "plenty" of elements.
 static const size_t kNumElements = 150;
 
+}  // namespace
+
 TEST(ContiguousContainerTest, SimpleStructs) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   list.AllocateAndConstruct<Point2D>(1, 2);
   list.AllocateAndConstruct<Point3D>(3, 4, 5);
   list.AllocateAndConstruct<Point2D>(6, 7);
 
   ASSERT_EQ(3u, list.size());
   EXPECT_EQ(1, list[0].x);
   EXPECT_EQ(2, list[0].y);
   EXPECT_EQ(3, list[1].x);
   EXPECT_EQ(4, list[1].y);
   EXPECT_EQ(5, static_cast<Point3D&>(list[1]).z);
   EXPECT_EQ(6, list[2].x);
   EXPECT_EQ(7, list[2].y);
 }
 
 TEST(ContiguousContainerTest, AllocateLots) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++) {
     list.AllocateAndConstruct<Point2D>(i, i);
     list.AllocateAndConstruct<Point2D>(i, i);
     list.RemoveLast();
   }
   ASSERT_EQ(kNumElements, list.size());
   for (int i = 0; i < (int)kNumElements; i++) {
     ASSERT_EQ(i, list[i].x);
     ASSERT_EQ(i, list[i].y);
   }
@@ skipping 97 matching lines @@
   separator.Call();
   EXPECT_EQ(3u, list.size());
 
   // The remaining ones are destroyed when the test finishes.
   EXPECT_CALL(list[2], Destruct());
   EXPECT_CALL(list[1], Destruct());
   EXPECT_CALL(list[0], Destruct());
 }
 
 TEST(ContiguousContainerTest, InsertionAndIndexedAccess) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
 
   auto& point1 = list.AllocateAndConstruct<Point2D>();
   auto& point2 = list.AllocateAndConstruct<Point2D>();
   auto& point3 = list.AllocateAndConstruct<Point2D>();
 
   EXPECT_EQ(3u, list.size());
   EXPECT_EQ(&point1, &list.first());
   EXPECT_EQ(&point3, &list.last());
   EXPECT_EQ(&point1, &list[0]);
   EXPECT_EQ(&point2, &list[1]);
   EXPECT_EQ(&point3, &list[2]);
 }
 
 TEST(ContiguousContainerTest, InsertionAndClear) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   EXPECT_TRUE(list.empty());
   EXPECT_EQ(0u, list.size());
 
   list.AllocateAndConstruct<Point2D>();
   EXPECT_FALSE(list.empty());
   EXPECT_EQ(1u, list.size());
 
   list.Clear();
   EXPECT_TRUE(list.empty());
   EXPECT_EQ(0u, list.size());
 
   list.AllocateAndConstruct<Point2D>();
   EXPECT_FALSE(list.empty());
   EXPECT_EQ(1u, list.size());
 }
 
 TEST(ContiguousContainerTest, ElementAddressesAreStable) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   std::vector<Point2D*> pointers;
   for (int i = 0; i < (int)kNumElements; i++)
     pointers.push_back(&list.AllocateAndConstruct<Point2D>());
   EXPECT_EQ(kNumElements, list.size());
   EXPECT_EQ(kNumElements, pointers.size());
 
   auto listIt = list.begin();
   auto vectorIt = pointers.begin();
   for (; listIt != list.end(); ++listIt, ++vectorIt)
     EXPECT_EQ(&*listIt, *vectorIt);
 }
 
 TEST(ContiguousContainerTest, ForwardIteration) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++)
     list.AllocateAndConstruct<Point2D>(i, i);
   unsigned count = 0;
   for (Point2D& point : list) {
     EXPECT_EQ((int)count, point.x);
     count++;
   }
   EXPECT_EQ(kNumElements, count);
 
   static_assert(std::is_same<decltype(*list.begin()), Point2D&>::value,
                 "Non-const iteration should produce non-const references.");
 }
 
 TEST(ContiguousContainerTest, ConstForwardIteration) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++)
     list.AllocateAndConstruct<Point2D>(i, i);
 
   const auto& const_list = list;
   unsigned count = 0;
   for (const Point2D& point : const_list) {
     EXPECT_EQ((int)count, point.x);
     count++;
   }
   EXPECT_EQ(kNumElements, count);
 
   static_assert(
       std::is_same<decltype(*const_list.begin()), const Point2D&>::value,
       "Const iteration should produce const references.");
 }
 
 TEST(ContiguousContainerTest, ReverseIteration) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++)
     list.AllocateAndConstruct<Point2D>(i, i);
 
   unsigned count = 0;
   for (auto it = list.rbegin(); it != list.rend(); ++it) {
     EXPECT_EQ((int)(kNumElements - 1 - count), it->x);
     count++;
   }
   EXPECT_EQ(kNumElements, count);
 
@@ skipping 60 matching lines @@
   pop();
   check_equal();  // One full, one empty.
   push();
   pop();
   pop();
   ASSERT_TRUE(list.empty());
   check_equal();  // Empty.
 }
 
 TEST(ContiguousContainerTest, AppendByMovingSameList) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   list.AllocateAndConstruct<Point3D>(1, 2, 3);
 
   // Moves the Point3D to the end, and default-constructs a Point2D in its
   // place.
-  list.AppendByMoving(&list.first(), sizeof(Point3D));
+  list.AppendByMoving(&list.first(), sizeof(Point3D), Log2Alignment<Point3D>());
   EXPECT_EQ(1, list.last().x);
   EXPECT_EQ(2, list.last().y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list.last()).z);
   EXPECT_EQ(2u, list.size());
 
   // Moves that Point2D to the end, and default-constructs another in its
   // place.
   list.first().x = 4;
-  list.AppendByMoving(&list.first(), sizeof(Point2D));
+  list.AppendByMoving(&list.first(), sizeof(Point2D), Log2Alignment<Point2D>());
   EXPECT_EQ(4, list.last().x);
   EXPECT_EQ(3u, list.size());
 }
 
 TEST(ContiguousContainerTest, AppendByMovingDoesNotDestruct) {
   // GMock mock objects (e.g. MockDestructible) aren't guaranteed to be safe
   // to memcpy (which is required for AppendByMoving).
   class DestructionNotifier {
    public:
     explicit DestructionNotifier(bool* flag = nullptr) : flag_(flag) {}
     ~DestructionNotifier() {
       if (flag_)
         *flag_ = true;
     }
 
    private:
     bool* flag_;
   };
 
   bool destroyed = false;
   ContiguousContainer<DestructionNotifier> list1(sizeof(DestructionNotifier));
   list1.AllocateAndConstruct<DestructionNotifier>(&destroyed);
   {
     // Make sure destructor isn't called during AppendByMoving.
     ContiguousContainer<DestructionNotifier> list2(sizeof(DestructionNotifier));
-    list2.AppendByMoving(&list1.last(), sizeof(DestructionNotifier));
+    list2.AppendByMoving(&list1.last(), sizeof(DestructionNotifier),
+                         Log2Alignment<DestructionNotifier>());
     EXPECT_FALSE(destroyed);
   }
   // But it should be destroyed when list2 is.
   EXPECT_TRUE(destroyed);
 }
 
 TEST(ContiguousContainerTest, AppendByMovingReturnsMovedPointer) {
-  ContiguousContainer<Point2D, kPointAlignment> list1(kMaxPointSize);
-  ContiguousContainer<Point2D, kPointAlignment> list2(kMaxPointSize);
+  ContiguousContainer<Point2D> list1(kMaxPointSize);
+  ContiguousContainer<Point2D> list2(kMaxPointSize);
 
   Point2D& point = list1.AllocateAndConstruct<Point2D>();
-  Point2D& moved_point1 = list2.AppendByMoving(&point, sizeof(Point2D));
+  Point2D& moved_point1 =
+      list2.AppendByMoving(&point, sizeof(Point2D), Log2Alignment<Point2D>());
   EXPECT_EQ(&moved_point1, &list2.last());
 
-  Point2D& moved_point2 = list1.AppendByMoving(&moved_point1, sizeof(Point2D));
+  Point2D& moved_point2 = list1.AppendByMoving(&moved_point1, sizeof(Point2D),
+                                               Log2Alignment<Point2D>());
   EXPECT_EQ(&moved_point2, &list1.last());
   EXPECT_NE(&moved_point1, &moved_point2);
 }
 
 TEST(ContiguousContainerTest, AppendByMovingReplacesSourceWithNewElement) {
-  ContiguousContainer<Point2D, kPointAlignment> list1(kMaxPointSize);
-  ContiguousContainer<Point2D, kPointAlignment> list2(kMaxPointSize);
+  ContiguousContainer<Point2D> list1(kMaxPointSize);
+  ContiguousContainer<Point2D> list2(kMaxPointSize);
 
   list1.AllocateAndConstruct<Point2D>(1, 2);
   EXPECT_EQ(1, list1.first().x);
   EXPECT_EQ(2, list1.first().y);
 
-  list2.AppendByMoving(&list1.first(), sizeof(Point2D));
+  list2.AppendByMoving(&list1.first(), sizeof(Point2D),
+                       Log2Alignment<Point2D>());
   EXPECT_EQ(0, list1.first().x);
   EXPECT_EQ(0, list1.first().y);
   EXPECT_EQ(1, list2.first().x);
   EXPECT_EQ(2, list2.first().y);
 
   EXPECT_EQ(1u, list1.size());
   EXPECT_EQ(1u, list2.size());
 }
 
 TEST(ContiguousContainerTest, AppendByMovingElementsOfDifferentSizes) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   list.AllocateAndConstruct<Point3D>(1, 2, 3);
   list.AllocateAndConstruct<Point2D>(4, 5);
 
   EXPECT_EQ(1, list[0].x);
   EXPECT_EQ(2, list[0].y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list[0]).z);
   EXPECT_EQ(4, list[1].x);
   EXPECT_EQ(5, list[1].y);
 
   // Test that moving the first element actually moves the entire object, not
   // just the base element.
-  list.AppendByMoving(&list[0], sizeof(Point3D));
+  list.AppendByMoving(&list[0], sizeof(Point3D), Log2Alignment<Point3D>());
   EXPECT_EQ(1, list[2].x);
   EXPECT_EQ(2, list[2].y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list[2]).z);
   EXPECT_EQ(4, list[1].x);
   EXPECT_EQ(5, list[1].y);
 
-  list.AppendByMoving(&list[1], sizeof(Point2D));
+  list.AppendByMoving(&list[1], sizeof(Point2D), Log2Alignment<Point2D>());
   EXPECT_EQ(1, list[2].x);
   EXPECT_EQ(2, list[2].y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list[2]).z);
   EXPECT_EQ(4, list[3].x);
   EXPECT_EQ(5, list[3].y);
 }
 
 TEST(ContiguousContainerTest, Swap) {
-  ContiguousContainer<Point2D, kPointAlignment> list1(kMaxPointSize);
+  ContiguousContainer<Point2D> list1(kMaxPointSize);
   list1.AllocateAndConstruct<Point2D>(1, 2);
-  ContiguousContainer<Point2D, kPointAlignment> list2(kMaxPointSize);
+  ContiguousContainer<Point2D> list2(kMaxPointSize);
   list2.AllocateAndConstruct<Point2D>(3, 4);
   list2.AllocateAndConstruct<Point2D>(5, 6);
 
   EXPECT_EQ(1u, list1.size());
   EXPECT_EQ(1, list1[0].x);
   EXPECT_EQ(2, list1[0].y);
   EXPECT_EQ(2u, list2.size());
   EXPECT_EQ(3, list2[0].x);
   EXPECT_EQ(4, list2[0].y);
   EXPECT_EQ(5, list2[1].x);
@@ skipping 18 matching lines @@
 
   // At time of writing, removing elements from the end can cause up to 7x the
   // memory required to be consumed, in the worst case, since we can have up to
   // two trailing inner lists that are empty (for 2*size + 4*size in unused
   // memory, due to the exponential growth strategy).
   // Unfortunately, this captures behaviour of the underlying allocator as
   // well as this container, so we're pretty loose here. This constant may
   // need to be adjusted.
   const size_t max_waste_factor = 8;
 
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize,
-                                                     initial_capacity);
+  ContiguousContainer<Point2D> list(kMaxPointSize, initial_capacity);
 
   // The capacity should grow with the list.
   for (int i = 0; i < iterations; i++) {
     size_t capacity = list.GetCapacityInBytes();
     ASSERT_GE(capacity, list.size() * sizeof(Point2D));
     ASSERT_LE(capacity, std::max(list.size() * sizeof(Point2D),
                                  upper_bound_on_min_capacity) *
                             max_waste_factor);
     list.AllocateAndConstruct<Point2D>();
   }
 
   // The capacity should shrink with the list.
   for (int i = 0; i < iterations; i++) {
     size_t capacity = list.GetCapacityInBytes();
     ASSERT_GE(capacity, list.size() * sizeof(Point2D));
     ASSERT_LE(capacity, std::max(list.size() * sizeof(Point2D),
                                  upper_bound_on_min_capacity) *
                             max_waste_factor);
     list.RemoveLast();
   }
 }
 
 TEST(ContiguousContainerTest, CapacityInBytesAfterClear) {
   // Clearing should restore the capacity of the container to the same as a
   // newly allocated one (without reserved capacity requested).
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   size_t empty_capacity = list.GetCapacityInBytes();
   list.AllocateAndConstruct<Point2D>();
   list.AllocateAndConstruct<Point2D>();
   list.Clear();
   EXPECT_EQ(empty_capacity, list.GetCapacityInBytes());
 }
 
-}  // namespace
+TEST(ContiguousContainerTest, Alignment) {
+  ContiguousContainer<char> container(64, 64);
+  void* item1 = container.Allocate(21, 4);  // alignment 16
+  ASSERT_TRUE(item1);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item1) & 0x0F);
+  EXPECT_GE(21u, container.UsedCapacityInBytes());
+  // The initial gap may not be consistent among runs.
+  // |--------21-------|-------------------43-----------------------|
+  // |      item1      |                 unused                     |
+
+  void* item2 = container.Allocate(9, 3);  // alignment 8
+  ASSERT_TRUE(item2);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item2) & 7);
+  // |---------24--------|---9---|----------------31----------------|
+  // |      item1      | | item2 |             unused               |
+  EXPECT_EQ(24u + 9u, container.UsedCapacityInBytes());
+
+  void* item3 = container.Allocate(3, 2);  // alignment 4
+  ASSERT_TRUE(item3);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item3) & 3);
+  // |---------24--------|----12----|--3--|----------25-------------|
+  // |      item1      | | item2 |  |item3|        unused           |
+  EXPECT_EQ(24u + 12u + 3u, container.UsedCapacityInBytes());
+
+  void* item4 = container.Allocate(11, 0);
+  ASSERT_TRUE(item4);
+  // |---------24--------|----12----|--3--|---11---|-------14-------|
+  // |      item1      | | item2 |  |item3| item4  |     unused     |
+  EXPECT_EQ(24u + 12u + 3u + 11u, container.UsedCapacityInBytes());
+
+  // All of the above allocations should be in the initial buffer.
+  EXPECT_EQ(64u, container.GetCapacityInBytes());
+
+  // The initial buffer can't hold another object aligned at 16 bytes.
+  void* item5 = container.Allocate(8, 4);
+  ASSERT_TRUE(item5);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item5) & 0x0F);
+  EXPECT_GT(container.GetCapacityInBytes(), 64u);
+
+  container.RemoveLast();  // item5
+  // The container should retain the last empty buffer to avoid reallocation of
+  // buffer for new item allocations.
+  EXPECT_GT(container.GetCapacityInBytes(), 64u);
+
+  container.RemoveLast();  // item4
+  EXPECT_EQ(24u + 12u + 3u, container.UsedCapacityInBytes());
+  container.RemoveLast();  // item3
+  EXPECT_EQ(24u + 12u, container.UsedCapacityInBytes());
+  container.RemoveLast();  // item2
+  EXPECT_EQ(24u, container.UsedCapacityInBytes());
+  container.RemoveLast();  // item1
+  EXPECT_EQ(0u, container.UsedCapacityInBytes());
+}
+
 }  // namespace cc