Lumiera  0.pre.03
»edit your freedom«
allocation-cluster-test.cpp
Go to the documentation of this file.
1 /*
2  AllocationCluster(Test) - verify bulk (de)allocating a family of objects
3 
4  Copyright (C)
5  2008, Hermann Vosseler <Ichthyostega@web.de>
6 
7   **Lumiera** is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 2 of the License, or (at your
10   option) any later version. See the file COPYING for further details.
11 
12 * *****************************************************************/
13 
20 #include "lib/test/run.hpp"
21 #include "lib/test/test-helper.hpp"
24 #include "lib/format-util.hpp"
25 #include "lib/iter-explorer.hpp"
26 #include "lib/util.hpp"
27 
28 #include <functional>
29 #include <limits>
30 #include <vector>
31 #include <array>
32 #include <set>
33 
34 using ::Test;
35 using lib::explore;
36 using lib::test::showSizeof;
37 using util::getAdr;
38 using util::isnil;
39 
40 using std::numeric_limits;
41 using std::function;
42 using std::vector;
43 using std::array;
44 using std::byte;
45 
46 
47 
48 namespace lib {
49 namespace test {
50 
51  namespace { // a family of test dummy classes
52 
53  const uint NUM_CLUSTERS = 5;
54  const uint NUM_TYPES = 20;
55  const uint NUM_OBJECTS = 500;
56 
57  const size_t EXTSIZ = AllocationCluster::EXTENT_SIZ;
58 
59  int64_t checksum = 0; // validate proper pairing of ctor/dtor calls
60 
61  template<uint i>
62  class Dummy
63  {
64  static_assert (0 < i);
65  array<uchar,i> content_;
66 
67  public:
68  Dummy (uchar id=1)
69  {
70  content_.fill(id);
71  checksum += explore(content_).resultSum();
72  }
73 
74  ~Dummy()
75  {
76  checksum -= explore(content_).resultSum();
77  }
78 
79  uint getID() { return content_[0]; }
80  };
81 
82 
83  template<uint i>
84  void
85  place_object (AllocationCluster& clu, uchar id)
86  {
87  clu.create<Dummy<i>> (id);
88  }
89 
90 
91  inline array<function<void(AllocationCluster&, uchar)>, NUM_TYPES>
92  buildTrampoline()
93  {
94  return { place_object<1>
95  , place_object<2>
96  , place_object<3>
97  , place_object<5>
98  , place_object<10>
99  , place_object<13>
100  , place_object<14>
101  , place_object<15>
102  , place_object<16>
103  , place_object<17>
104  , place_object<18>
105  , place_object<19>
106  , place_object<20>
107  , place_object<25>
108  , place_object<30>
109  , place_object<35>
110  , place_object<40>
111  , place_object<50>
112  , place_object<100>
113  , place_object<200>
114  };
115  }
116 
117  void
118  fill (AllocationCluster& clu)
119  {
120  auto invoker = buildTrampoline();
121  for (uint i=0; i<NUM_OBJECTS; ++i)
122  invoker[rani (NUM_TYPES)] (clu, uchar(i));
123  }
124 
125  inline uint
126  sum (uint n)
127  {
128  return n*(n+1) / 2;
129  }
130  }
131 
132 
133 
134  /*********************************************************************/
139  class AllocationCluster_test : public Test
140  {
141  virtual void
142  run (Arg)
143  {
144  seedRand();
145 
146  simpleUsage();
147  checkLifecycle();
148  verifyInternals();
149  use_as_Allocator();
150  dynamicAdjustment();
151  }
152 
153 
154  void
155  simpleUsage()
156  {
157  AllocationCluster clu;
158  CHECK (0 == clu.numExtents());
159 
160  char c1(123), c2(45);
161  Dummy<66>& ref1 = clu.create<Dummy<66>> ();
162  Dummy<77>& ref2 = clu.create<Dummy<77>> (c1);
163  Dummy<77>& ref3 = clu.create<Dummy<77>> (c2);
164 
165  //returned references actually point at the objects we created
166  CHECK (1 ==ref1.getID());
167  CHECK (123==ref2.getID());
168  CHECK (45 ==ref3.getID());
169 
170  CHECK (0 < clu.numExtents());
171 
172  // now use objects and just let them go;
173  }
174 
175 
183  void
185  {
186  CHECK (0==checksum);
187  {
188  vector<AllocationCluster> clusters (NUM_CLUSTERS);
189  for (auto& clu : clusters)
190  fill(clu);
191  CHECK (0!=checksum);
192  }
193  CHECK (0==checksum);
194 
195  int64_t allSum;
196  {// can also be used without invoking any destructors
197  AllocationCluster clu;
198  for (uint i=0; i<NUM_OBJECTS; ++i)
199  clu.createDisposable<Dummy<223>>();
200 
201  CHECK (clu.numExtents() == NUM_OBJECTS);
202  CHECK (checksum == NUM_OBJECTS * 223);
203  allSum = checksum;
204  }// Memory discarded here without invoking any destructor....
205  CHECK (allSum == checksum);
206  checksum = 0;
207  }
208 
209 
210 
218  void
220  {
221  CHECK (0==checksum);
222  long markSum;
223  {
224  AllocationCluster clu;
225  // no allocation happened yet
226  CHECK (0 == clu.numExtents());
227  CHECK (0 == clu.numBytes());
228  CHECK (nullptr == clu.storage_.pos);
229  CHECK ( 0 == clu.storage_.rest);
230 
231  // build a simple object
232  auto& i1 = clu.create<uint16_t> (1 + uint16_t(rani()));
233  CHECK (i1 > 0);
234  CHECK (1 == clu.numExtents());
235  CHECK (2 == clu.numBytes());
236  CHECK (clu.storage_.pos != nullptr);
237  CHECK (clu.storage_.pos == (& i1) + 1 ); // points directly behind the allocated integer
238  CHECK (clu.storage_.rest == EXTSIZ - (2*sizeof(void*) + sizeof(uint16_t)));
239 
240  // Demonstration: how to reconstruct the start of the current extent
241  byte* blk = static_cast<std::byte*>(clu.storage_.pos);
242  blk += clu.storage_.rest - EXTSIZ;
243  CHECK(size_t(blk) < size_t(clu.storage_.pos));
244 
245  // some abbreviations for navigating the raw storage blocks...
246  auto currBlock = [&]{
247  byte* blk = static_cast<std::byte*>(clu.storage_.pos);
248  blk += clu.storage_.rest - EXTSIZ;
249  return blk;
250  };
251  auto posOffset = [&]{
252  return size_t(clu.storage_.pos) - size_t(currBlock());
253  };
254  auto slot = [&](size_t i)
255  {
256  size_t* slot = reinterpret_cast<size_t*> (currBlock());
257  return slot[i];
258  };
259 
260  CHECK (blk == currBlock());
261  // current storage pos: 2 »slots« of admin overhead plus the first allocated element
262  CHECK (posOffset() == 2 * sizeof(void*) + sizeof(uint16_t));
263  CHECK (slot(0) == 0); // only one extent, thus next-* is NULL
264 
265  // allocate another one
266  uint16_t i1pre = i1;
267  auto& i2 = clu.create<uint16_t> (55555);
268  CHECK (posOffset() == 2 * sizeof(void*) + 2 * sizeof(uint16_t));
269  CHECK (clu.storage_.rest == EXTSIZ - posOffset());
270  // existing storage unaffected
271  CHECK (i1 == i1pre);
272  CHECK (i2 == 55555);
273  CHECK (slot(0) == 0); // no administrative data yet...
274  CHECK (slot(1) == 0);
275 
276  // alignment is handled properly
277  char& c1 = clu.create<char> ('X');
278  CHECK (posOffset() == 2 * sizeof(void*) + 2 * sizeof(uint16_t) + sizeof(char));
279  auto& i3 = clu.create<int32_t> (42);
280  CHECK (posOffset() == 2 * sizeof(void*) + 2 * sizeof(uint16_t) + sizeof(char) + 3*sizeof(byte) + sizeof(int32_t));
281  CHECK (i1 == i1pre); // ^^^^Alignment
282  CHECK (i2 == 55555);
283  CHECK (c1 == 'X');
284  CHECK (i3 == 42);
285  CHECK (slot(0) == 0);
286 
287  // deliberately fill up the first extent completely
288  for (uint i=clu.storage_.rest; i>0; --i)
289  clu.create<uchar> (i);
290  CHECK (clu.storage_.rest == 0); // no space left in current extent
291  CHECK (posOffset() == EXTSIZ);
292  CHECK (clu.numBytes() == EXTSIZ - 2*sizeof(void*)); // now using all the rest behind the admin »slots«
293  CHECK (clu.numExtents() == 1);
294  CHECK (slot(0) == 0);
295  CHECK (blk == currBlock()); // but still in the initial extent
296 
297  // trigger overflow and allocation of second extent
298  char& c2 = clu.create<char> ('U');
299  CHECK (blk != currBlock()); // allocation moved to a new extent
300  CHECK (getAdr(c2) == currBlock() + 2*sizeof(void*)); // c2 resides immediately after the two administrative »slots«
301  CHECK (clu.storage_.rest == EXTSIZ - posOffset());
302  CHECK (clu.numBytes() == EXTSIZ - 2*sizeof(void*) + 1); // accounted allocation for the full first block + one byte
303  CHECK (clu.numExtents() == 2); // we have two extents now
304  CHECK (slot(0) == size_t(blk)); // first »slot« of the current block points back to previous block
305  CHECK (i1 == i1pre);
306  CHECK (i2 == 55555);
307  CHECK (c1 == 'X');
308  CHECK (c2 == 'U');
309  CHECK (i3 == 42);
310 
311  // allocate a "disposable" object (dtor will not be called)
312  size_t pp = posOffset();
313  auto& o1 = clu.createDisposable<Dummy<2>> (4);
314  CHECK (o1.getID() == 4);
315  markSum = checksum;
316  CHECK (checksum == 4+4);
317  CHECK (alignof(Dummy<2>) == alignof(char));
318  CHECK (posOffset() - pp == sizeof(Dummy<2>)); // for disposable objects only the object storage itself plus alignment
319 
320  // allocate a similar object,
321  // but this time also enrolling the destructor
322  pp = posOffset();
323  auto& o2 = clu.create<Dummy<2>> (8);
324  CHECK (o2.getID() == 8);
325  CHECK (checksum == markSum + 8+8);
326  CHECK (posOffset() - pp > sizeof(Dummy<2>) + 2*sizeof(void*));
327  CHECK (slot(1) > 0);
328  CHECK (size_t(&o2) - slot(1) == 2*sizeof(void*)); // Object resides in a Destructor frame,
329  using Dtor = AllocationCluster::Destructor; // ... which has been hooked up into admin-slot-1 of the current extent
330  auto dtor = (Dtor*)slot(1);
331  CHECK (dtor->next == nullptr);
332 
333  // any other object with non-trivial destructor....
334  string rands = lib::test::randStr(9);
335  pp = posOffset();
336  string& s1 = clu.create<string> (rands); // a string that fits into the small-string optimisation
337  CHECK (s1 == rands);
338 
339  CHECK (posOffset() - pp >= sizeof(string) + 2*sizeof(void*));
340  CHECK (size_t(&s1) - slot(1) == 2*sizeof(void*)); // again the Destructor frame is placed immediately before the object
341  auto dtor2 = (Dtor*)slot(1); // and it has been prepended to the destructors-list in current extent
342  CHECK (dtor2->next == dtor); // with the destructor of o2 hooked up behind
343  CHECK (dtor->next == nullptr);
344 
345  // provoke overflow into a new extent
346  // by placing an object that does not fit
347  // into the residual space in current one
348  auto& o3 = clu.create<Dummy<223>> (3);
349  CHECK (clu.numExtents() == 3); // a third extent has been opened to accommodate this object
350  CHECK (checksum == markSum + 8+8 + uchar(223*3));
351  auto dtor3 = (Dtor*)slot(1);
352  CHECK (dtor3->next == nullptr); // Destructors are chained for each extent separately
353  CHECK (dtor3 != dtor2);
354  CHECK (dtor2->next == dtor); // the destructor chain from previous extent is also still valid
355  CHECK (dtor->next == nullptr);
356 
357  CHECK (i1 == i1pre); // all data is intact (no corruption)
358  CHECK (s1 == rands);
359  CHECK (i2 == 55555);
360  CHECK (c1 == 'X');
361  CHECK (c2 == 'U');
362  CHECK (i3 == 42);
363  CHECK (o1.getID() == 4);
364  CHECK (o2.getID() == 8);
365  CHECK (o3.getID() == 3);
366  }
367  CHECK (checksum == markSum); // only the destructor of the "disposable" object o1 was not invoked
368  }
369 
370 
371 
372  template<typename X>
374 
383  void
385  {
386  using VecI = std::vector<uint16_t, Allo<uint16_t>>;
387  using Strg = std::basic_string<char, std::char_traits<char>, Allo<char>>;
388  using SetS = std::set<Strg, std::less<Strg>, Allo<Strg>>;
389 
390  AllocationCluster clu;
391  CHECK (clu.numExtents() == 0);
392 
393  VecI vecI{clu.getAllocator<uint16_t>()};
394 
395  // Since vector needs a contiguous allocation,
396  // the maximum number of elements is limited by the Extent size (256 bytes - 2*sizeof(void*))
397  // Moreover, the vector grows its capacity; AllocationCluster does not support re-allocation,
398  // and thus the initial smaller memory chunks will just be abandoned.
399  const uint MAX = 64;
400 
401  for (uint i=1; i<=MAX; ++i)
402  vecI.push_back(i);
403  CHECK (clu.numExtents() == 2);
404  CHECK (vecI.capacity() == 64);
405 
406  // fill a set with random strings...
407  SetS setS{clu.getAllocator<Strg>()};
408 
409  for (uint i=0; i<NUM_OBJECTS; ++i)
410  setS.emplace (test::randStr(32), clu.getAllocator<char>());
411  CHECK (setS.size() > 0.9 * NUM_OBJECTS);
412  CHECK (clu.numExtents() > 200);
413 
414  // verify the data in the first allocation is intact
415  CHECK (explore(vecI).resultSum() == sum(64));
416  }
417 
418 
421  void
423  {
424  AllocationCluster clu;
425  auto& l1 = clu.create<array<uchar,12>>();
426  CHECK (clu.numExtents() == 1);
427  CHECK (clu.numBytes() == 12);
428 
429  auto& l2 = clu.create<array<uchar,5>>();
430  CHECK (clu.numExtents() == 1);
431  CHECK (clu.numBytes() == 17);
432 
433  CHECK ( clu.canAdjust (&l2, 5, 8)); // possible since l2 is verifiable as last allocation
434  CHECK ( clu.canAdjust (&l2, 5, 5)); // arbitrary adjustments are then possible
435  CHECK ( clu.canAdjust (&l2, 5, 2));
436  CHECK ( clu.canAdjust (&l2, 5, 0)); // even shrinking to zero
437  CHECK (not clu.canAdjust (&l1, 12,24)); // but the preceding allocation can not be changed anymore
438  CHECK (not clu.canAdjust (&l2, 6, 8)); // similarly, reject requests when passing wrong original size
439  CHECK (not clu.canAdjust (&l2, 4, 8));
440  CHECK (not clu.canAdjust (&l2, 5, 1000)); // also requests exceeding the remaining extent space are rejected
441  CHECK ( clu.canAdjust (&l1, 17,24)); // however, can not detect if a passed wrong size accidentally matches
442 
443  CHECK (clu.numExtents() == 1);
444  CHECK (clu.numBytes() == 17);
445  l1[11] = 11; // put some marker values into the storage
446  l2[0] = 5;
447  l2[1] = 4;
448  l2[2] = 3;
449  l2[3] = 2;
450  l2[4] = 1;
451  l2[5] = 55; // yes, even behind the valid range (subscript is unchecked)
452  l2[6] = 66;
453 
454  using LERR_(INVALID);
455 
456  VERIFY_ERROR (INVALID, clu.doAdjust(&l1, 12,24) );
457  CHECK (clu.numExtents() == 1);
458  CHECK (clu.numBytes() == 17);
459 
460  // perform a size adjustment on the latest allocation
461  clu.doAdjust (&l2, 5,12);
462  CHECK (clu.numExtents() == 1);
463  CHECK (clu.numBytes() == 24);
464  // no memory corruption
465  CHECK (l1[11] == 11);
466  CHECK (l2[0] == 5);
467  CHECK (l2[1] == 4);
468  CHECK (l2[2] == 3);
469  CHECK (l2[3] == 2);
470  CHECK (l2[4] == 1);
471  CHECK (l2[5] == 55);
472  CHECK (l2[6] == 66);
473 
474  // scale down the latest allocation completely
475  clu.doAdjust (&l2, 12,0);
476  CHECK (clu.numExtents() == 1);
477  CHECK (clu.numBytes() == 12);
478  // no memory corruption
479  CHECK (l1[11] == 11);
480  CHECK (l2[0] == 5);
481  CHECK (l2[1] == 4);
482  CHECK (l2[2] == 3);
483  CHECK (l2[3] == 2);
484  CHECK (l2[4] == 1);
485  CHECK (l2[5] == 55);
486  CHECK (l2[6] == 66);
487  }
488  };
489 
490  LAUNCHER (AllocationCluster_test, "unit common");
491 
492 
493 }} // namespace lib::test
static size_t constexpr EXTENT_SIZ
hard wired size of storage extents
auto explore(IT &&srcSeq)
start building a IterExplorer by suitably wrapping the given iterable source.
void doAdjust(void *loc, size_t oldSiz, size_t newSiz)
Adjust the size of the latest raw memory allocation dynamically.
Definition: run.hpp:40
Memory management for the low-level model (render nodes network).
int rani(uint bound=_iBOUND())
Definition: random.hpp:135
#define VERIFY_ERROR(ERROR_ID, ERRONEOUS_STATEMENT)
Macro to verify that a statement indeed raises an exception.
Helpers typically used while writing tests.
#define MAX(A, B)
the inevitable MAX macro, sometimes still necessary in template code
Definition: util.hpp:518
Implementation namespace for support and library code.
string randStr(size_t len)
create garbage string of given length
Definition: test-helper.cpp:61
Simplistic test class runner.
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
A collection of frequently used helper functions to support unit testing.
A Dummy object for tests.
A pile of objects sharing common allocation and lifecycle.
Collection of small helpers and convenience shortcuts for diagnostics & formatting.
Building tree expanding and backtracking evaluations within hierarchical scopes.