test/object_heap_test.cpp

   1 /*
   2  * Copyright (C) 2016 Intel Corporation. All Rights Reserved.
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sub license, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the
  13  * next paragraph) shall be included in all copies or substantial portions
  14  * of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  19  * IN NO EVENT SHALL PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR
  20  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  21  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  22  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23  */
  24
  25 #include "test.h"
  26
  27 extern "C" {
  28     #include "object_heap.h"
  29 }
  30
  31 #include <algorithm>
  32 #include <cstdlib>
  33 #include <ctime>
  34 #include <iomanip>
  35 #include <vector>
  36
  37 TEST(ObjectHeapTest, Init)
  38 {
  39     struct test_object {
  40         struct object_base base;
  41         int i;
  42     };
  43
  44     struct object_heap heap = {
  45         object_size: -1,
  46         id_offset: -1,
  47         next_free: -1,
  48         heap_size: -1,
  49         heap_increment: -1,
  50         mutex: {},
  51         bucket: NULL,
  52         num_buckets: -1,
  53     };
  54
  55     EXPECT_EQ(0, object_heap_init(&heap, sizeof(test_object), 0xffffffff));
  56
  57     EXPECT_EQ(sizeof(test_object), (size_t)heap.object_size);
  58     EXPECT_EQ(OBJECT_HEAP_OFFSET_MASK, heap.id_offset);
  59     EXPECT_EQ(0, heap.next_free);
  60     EXPECT_LE(1, heap.heap_increment);
  61     EXPECT_EQ(heap.heap_increment, heap.heap_size);
  62     EXPECT_PTR(heap.bucket);
  63     EXPECT_LE(1, heap.num_buckets);
  64
  65     object_heap_destroy(&heap);
  66
  67     EXPECT_PTR_NULL(heap.bucket);
  68     EXPECT_EQ(0, heap.heap_size);
  69     EXPECT_GT(0, heap.next_free);
  70
  71     EXPECT_EQ(0, object_heap_init(&heap, sizeof(test_object), 0x0));
  72
  73     EXPECT_EQ(sizeof(test_object), (size_t)heap.object_size);
  74     EXPECT_EQ(0, heap.id_offset);
  75     EXPECT_EQ(0, heap.next_free);
  76     EXPECT_LE(1, heap.heap_increment);
  77     EXPECT_EQ(heap.heap_increment, heap.heap_size);
  78     EXPECT_PTR(heap.bucket);
  79     EXPECT_LE(1, heap.num_buckets);
  80
  81     object_heap_destroy(&heap);
  82
  83     EXPECT_PTR_NULL(heap.bucket);
  84     EXPECT_EQ(0, heap.heap_size);
  85     EXPECT_GT(0, heap.next_free);
  86 }
  87
  88 TEST(ObjectHeapTest, AllocateAndLookup)
  89 {
  90     struct object_heap heap = {};
  91
  92     ASSERT_EQ(0, object_heap_init(&heap, sizeof(object_base), 0));
  93
  94     int nbuckets = heap.num_buckets;
  95
  96     for (int i(0); i < heap.heap_increment * nbuckets * 2; ++i)
  97     {
  98         int id = object_heap_allocate(&heap);
  99         EXPECT_EQ(i, id);
 100         int expect(i+1);
 101         if (expect % heap.heap_increment == 0)
 102             expect = -1;
 103         EXPECT_EQ(expect, heap.next_free);
 104     }
 105
 106     EXPECT_EQ(nbuckets * 2, heap.num_buckets);
 107
 108     for (int i(0); i < heap.heap_increment * nbuckets * 2; ++i)
 109     {
 110         object_base_p obj = object_heap_lookup(&heap, i);
 111         EXPECT_PTR(obj);
 112         object_heap_free(&heap, obj);
 113         obj = object_heap_lookup(&heap, i);
 114         EXPECT_PTR_NULL(obj);
 115     }
 116
 117     object_heap_destroy(&heap);
 118 }
 119
 120 TEST(ObjectHeapTest, Iterate)
 121 {
 122     struct object_heap heap = {};
 123     object_heap_iterator iter;
 124
 125     ASSERT_EQ(0, object_heap_init(&heap, sizeof(object_base), 0));
 126
 127     EXPECT_PTR_NULL(object_heap_first(&heap, &iter));
 128     EXPECT_PTR_NULL(object_heap_next(&heap, &iter));
 129
 130     std::vector<object_base_p> objects(256, NULL);
 131     std::generate(objects.begin(), objects.end(),
 132         [&]{ return object_heap_lookup(&heap, object_heap_allocate(&heap)); });
 133
 134     // iterate all objects starting at first
 135     object_base_p current = object_heap_first(&heap, &iter);
 136     EXPECT_EQ(0, current->id);
 137     EXPECT_TRUE(objects.front() == current);
 138     size_t i(1);
 139     while ((current = object_heap_next(&heap, &iter)) && i < objects.size())
 140     {
 141         EXPECT_EQ(i, (size_t)current->id);
 142         EXPECT_TRUE(objects[i++] == current);
 143     }
 144     EXPECT_PTR_NULL(current);
 145     EXPECT_EQ(i, objects.size());
 146     EXPECT_PTR_NULL(object_heap_next(&heap, &iter));
 147
 148     // get "first" and free it
 149     current = object_heap_first(&heap, &iter);
 150     ASSERT_TRUE(objects[0] == current);
 151     object_heap_free(&heap, current);
 152     objects[0] = NULL;
 153
 154     // get "first" again and ensure it's our second allocated object
 155     current = object_heap_first(&heap, &iter);
 156     EXPECT_TRUE(objects[1] == current);
 157
 158     // free the object after "current" and ensure "next"
 159     // returns the one after it.
 160     object_heap_free(&heap, objects[2]);
 161     objects[2] = NULL;
 162     current = object_heap_next(&heap, &iter);
 163     EXPECT_TRUE(objects[3] == current);
 164
 165     // free all objects
 166     std::for_each(objects.begin(), objects.end(),
 167         [&](object_base_p o){ object_heap_free(&heap, o); });
 168
 169     object_heap_destroy(&heap);
 170 }
 171
 172 TEST(ObjectHeapTest, DataIntegrity)
 173 {
 174     struct test_object {
 175         struct object_base base;
 176         int i;
 177     };
 178
 179     typedef test_object *test_object_p;
 180     struct object_heap heap = {};
 181
 182     ASSERT_EQ(0, object_heap_init(&heap, sizeof(test_object), 0));
 183
 184     std::time_t seed = std::time(0);
 185     std::srand(seed);
 186     RecordProperty("seed", seed);
 187
 188     std::vector<int> values;
 189
 190     auto generator = [&]{
 191         int id = object_heap_allocate(&heap);
 192         object_base_p base = object_heap_lookup(&heap, id);
 193         test_object_p object = (test_object_p)base;
 194         object->i = std::rand();
 195         values.push_back(object->i);
 196         return object;
 197     };
 198
 199     std::vector<test_object*> objects(71, NULL);
 200     std::generate(objects.begin(), objects.end(), generator);
 201
 202     ASSERT_EQ(objects.size(), values.size());
 203
 204     auto validator = [&](test_object_p object) {
 205         object_base_p base = object_heap_lookup(&heap, object->base.id);
 206         EXPECT_TRUE(&object->base == base);
 207         EXPECT_EQ(object->base.id, base->id);
 208         test_object_p lo = (test_object_p)base;
 209         ASSERT_GT(values.size(), (size_t)lo->base.id);
 210         EXPECT_EQ(values[lo->base.id], lo->i);
 211     };
 212
 213     std::for_each(objects.begin(), objects.end(), validator);
 214
 215     std::for_each(objects.begin(), objects.end(),
 216         [&](test_object_p o){ object_heap_free(&heap, &o->base); });
 217     object_heap_destroy(&heap);
 218 }
 219
 220 TEST(ObjectHeapTest, OffsetID)
 221 {
 222     ASSERT_LT(0, (OBJECT_HEAP_OFFSET_MASK >> 24));
 223     for (int i(0); i <= (OBJECT_HEAP_OFFSET_MASK >> 24); ++i)
 224     {
 225         struct object_heap heap = {};
 226         int offset = i << 24;
 227
 228         SCOPED_TRACE(
 229             ::testing::Message()
 230             << "offset=0x" << std::hex << std::setfill('0')
 231             << std::setw(8) << offset << std::dec);
 232
 233         ASSERT_EQ(0, object_heap_init(&heap, sizeof(object_base), offset));
 234
 235         EXPECT_EQ(offset & OBJECT_HEAP_OFFSET_MASK, heap.id_offset);
 236
 237         std::vector<object_base_p> objects(1024, NULL);
 238         std::generate(objects.begin(), objects.end(),
 239             [&]{ return object_heap_lookup(&heap, object_heap_allocate(&heap)); });
 240
 241         for (int idx(0); (size_t)idx < objects.size(); ++idx)
 242             EXPECT_EQ(offset + idx, objects[idx]->id);
 243
 244         std::for_each(objects.begin(), objects.end(),
 245             [&](object_base_p o){ object_heap_free(&heap, o); });
 246         object_heap_destroy(&heap);
 247     }
 248 }