ceph/src/test/objectstore/fastbmap_allocator_test.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include <iostream>
   5 #include <gtest/gtest.h>
   6
   7 #include "os/bluestore/fastbmap_allocator_impl.h"
   8
   9 class TestAllocatorLevel01 : public AllocatorLevel01Loose
  10 {
  11 public:
  12   void init(uint64_t capacity, uint64_t alloc_unit)
  13   {
  14     _init(capacity, alloc_unit);
  15   }
  16   interval_t allocate_l1_cont(uint64_t length, uint64_t min_length,
  17     uint64_t pos_start, uint64_t pos_end)
  18   {
  19     return _allocate_l1_contiguous(length, min_length, 0, pos_start, pos_end);
  20   }
  21   void free_l1(const interval_t& r)
  22   {
  23     _free_l1(r.offset, r.length);
  24   }
  25 };
  26
  27 class TestAllocatorLevel02 : public AllocatorLevel02<AllocatorLevel01Loose>
  28 {
  29 public:
  30   void init(uint64_t capacity, uint64_t alloc_unit)
  31   {
  32     _init(capacity, alloc_unit);
  33   }
  34   void allocate_l2(uint64_t length, uint64_t min_length,
  35     uint64_t* allocated0,
  36     interval_vector_t* res)
  37   {
  38     uint64_t allocated = 0;
  39     uint64_t hint = 0; // trigger internal l2 hint support
  40     _allocate_l2(length, min_length, 0, hint, &allocated, res);
  41     *allocated0 += allocated;
  42   }
  43   void free_l2(const interval_vector_t& r)
  44   {
  45     _free_l2(r);
  46   }
  47   void mark_free(uint64_t o, uint64_t len)
  48   {
  49     _mark_free(o, len);
  50   }
  51   void mark_allocated(uint64_t o, uint64_t len)
  52   {
  53     _mark_allocated(o, len);
  54   }
  55 };
  56
  57 const uint64_t _1m = 1024 * 1024;
  58 const uint64_t _2m = 2 * 1024 * 1024;
  59
  60 TEST(TestAllocatorLevel01, test_l1)
  61 {
  62   TestAllocatorLevel01 al1;
  63   uint64_t num_l1_entries = 3 * 256;
  64   uint64_t capacity = num_l1_entries * 512 * 4096;
  65   al1.init(capacity, 0x1000);
  66   ASSERT_EQ(capacity, al1.debug_get_free());
  67
  68   auto i1 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
  69   ASSERT_EQ(i1.offset, 0u);
  70   ASSERT_EQ(i1.length, 0x1000u);
  71   ASSERT_EQ(capacity - 0x1000, al1.debug_get_free());
  72
  73   auto i2 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
  74   ASSERT_EQ(i2.offset, 0x1000u);
  75   ASSERT_EQ(i2.length, 0x1000u);
  76   al1.free_l1(i2);
  77   al1.free_l1(i1);
  78   i1 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
  79   ASSERT_EQ(i1.offset, 0u);
  80   ASSERT_EQ(i1.length, 0x1000u);
  81   i2 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
  82   ASSERT_EQ(i2.offset, 0x1000u);
  83   ASSERT_EQ(i2.length, 0x1000u);
  84   al1.free_l1(i1);
  85   al1.free_l1(i2);
  86
  87   i1 = al1.allocate_l1_cont(0x2000, 0x1000, 0, num_l1_entries);
  88   ASSERT_EQ(i1.offset, 0u);
  89   ASSERT_EQ(i1.length, 0x2000u);
  90
  91   i2 = al1.allocate_l1_cont(0x3000, 0x1000, 0, num_l1_entries);
  92   ASSERT_EQ(i2.offset, 0x2000u);
  93   ASSERT_EQ(i2.length, 0x3000u);
  94
  95   al1.free_l1(i1);
  96   al1.free_l1(i2);
  97
  98   i1 = al1.allocate_l1_cont(0x2000, 0x1000, 0, num_l1_entries);
  99   ASSERT_EQ(i1.offset, 0u);
 100   ASSERT_EQ(i1.length, 0x2000u);
 101
 102   i2 = al1.allocate_l1_cont(2 * 1024 * 1024, 0x1000, 0, num_l1_entries);
 103   ASSERT_EQ(i2.offset, 2u * 1024u * 1024u);
 104   ASSERT_EQ(i2.length, 2u * 1024u * 1024u);
 105
 106   al1.free_l1(i1);
 107   i1 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
 108   ASSERT_EQ(i1.offset, 0u);
 109   ASSERT_EQ(i1.length, 1024u * 1024u);
 110
 111   auto i3 = al1.allocate_l1_cont(1024 * 1024 + 0x1000, 0x1000, 0, num_l1_entries);
 112   ASSERT_EQ(i3.offset, 2u * 2u * 1024u * 1024u);
 113   ASSERT_EQ(i3.length, 1024u * 1024u + 0x1000u);
 114
 115   // here we have the following layout:
 116   // Alloc: 0~1M, 2M~2M, 4M~1M+4K
 117   // Free: 1M~1M, 4M+4K ~ 2M-4K, 6M ~...
 118   //
 119   auto i4 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
 120   ASSERT_EQ(1 * 1024 * 1024u, i4.offset);
 121   ASSERT_EQ(1024 * 1024u, i4.length);
 122   al1.free_l1(i4);
 123
 124   i4 = al1.allocate_l1_cont(1024 * 1024 - 0x1000, 0x1000, 0, num_l1_entries);
 125   ASSERT_EQ(i4.offset, 5u * 1024u * 1024u + 0x1000u);
 126   ASSERT_EQ(i4.length, 1024u * 1024u - 0x1000u);
 127   al1.free_l1(i4);
 128
 129   i4 = al1.allocate_l1_cont(1024 * 1024 + 0x1000, 0x1000, 0, num_l1_entries);
 130   ASSERT_EQ(i4.offset, 6u * 1024u * 1024u);
 131   //ASSERT_EQ(i4.offset, 5 * 1024 * 1024 + 0x1000);
 132   ASSERT_EQ(i4.length, 1024u * 1024u + 0x1000u);
 133
 134   al1.free_l1(i1);
 135   al1.free_l1(i2);
 136   al1.free_l1(i3);
 137   al1.free_l1(i4);
 138
 139   i1 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
 140   ASSERT_EQ(i1.offset, 0u);
 141   ASSERT_EQ(i1.length, 1024u * 1024u);
 142
 143   i2 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
 144   ASSERT_EQ(i2.offset, 1u * 1024u * 1024u);
 145   ASSERT_EQ(i2.length, 1024u * 1024u);
 146
 147   i3 = al1.allocate_l1_cont(512 * 1024, 0x1000, 0, num_l1_entries);
 148   ASSERT_EQ(i3.offset, 2u * 1024u * 1024u);
 149   ASSERT_EQ(i3.length, 512u * 1024u);
 150
 151   i4 = al1.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries);
 152   ASSERT_EQ(i4.offset, (2u * 1024u + 512u) * 1024u);
 153   ASSERT_EQ(i4.length, 1536u * 1024u);
 154   // making a hole 1.5 Mb length
 155   al1.free_l1(i2);
 156   al1.free_l1(i3);
 157   // and trying to fill it
 158   i2 = al1.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries);
 159   ASSERT_EQ(i2.offset, 1024u * 1024u);
 160   ASSERT_EQ(i2.length, 1536u * 1024u);
 161
 162   al1.free_l1(i2);
 163   // and trying to fill it partially
 164   i2 = al1.allocate_l1_cont(1528 * 1024, 0x1000, 0, num_l1_entries);
 165   ASSERT_EQ(i2.offset, 1024u * 1024u);
 166   ASSERT_EQ(i2.length, 1528u * 1024u);
 167
 168   i3 = al1.allocate_l1_cont(8 * 1024, 0x1000, 0, num_l1_entries);
 169   ASSERT_EQ(i3.offset, 2552u * 1024u);
 170   ASSERT_EQ(i3.length, 8u * 1024u);
 171
 172   al1.free_l1(i2);
 173   // here we have the following layout:
 174   // Alloc: 0~1M, 2552K~8K, num_l1_entries0K~1.5M
 175   // Free: 1M~1528K, 4M ~...
 176   //
 177   i2 = al1.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries);
 178   ASSERT_EQ(i2.offset, 4u * 1024u * 1024u);
 179   ASSERT_EQ(i2.length, 1536u * 1024u);
 180
 181   al1.free_l1(i1);
 182   al1.free_l1(i2);
 183   al1.free_l1(i3);
 184   al1.free_l1(i4);
 185   ASSERT_EQ(capacity, al1.debug_get_free());
 186
 187   for (uint64_t i = 0; i < capacity; i += _2m) {
 188     i1 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
 189     ASSERT_EQ(i1.offset, i);
 190     ASSERT_EQ(i1.length, _2m);
 191   }
 192   ASSERT_EQ(0u, al1.debug_get_free());
 193   i2 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
 194   ASSERT_EQ(i2.length, 0u);
 195   ASSERT_EQ(0u, al1.debug_get_free());
 196
 197   al1.free_l1(i1);
 198   i2 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
 199   ASSERT_EQ(i2, i1);
 200   al1.free_l1(i2);
 201   i2 = al1.allocate_l1_cont(_1m, _1m, 0, num_l1_entries);
 202   ASSERT_EQ(i2.offset, i1.offset);
 203   ASSERT_EQ(i2.length, _1m);
 204
 205   i3 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
 206   ASSERT_EQ(i3.length, 0u);
 207
 208   i3 = al1.allocate_l1_cont(_2m, _1m, 0, num_l1_entries);
 209   ASSERT_EQ(i3.length, _1m);
 210
 211   i4 = al1.allocate_l1_cont(_2m, _1m, 0, num_l1_entries);
 212   ASSERT_EQ(i4.length, 0u);
 213
 214   al1.free_l1(i2);
 215   i2 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
 216   ASSERT_EQ(i2.length, 0u);
 217
 218   i2 = al1.allocate_l1_cont(_2m, 0x1000, 0, num_l1_entries);
 219   ASSERT_EQ(i2.length, _1m);
 220
 221   al1.free_l1(i2);
 222   al1.free_l1(i3);
 223   ASSERT_EQ(_2m, al1.debug_get_free());
 224
 225   i1 = al1.allocate_l1_cont(_2m - 3 * 0x1000, 0x1000, 0, num_l1_entries);
 226   i2 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
 227   i3 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
 228   i4 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
 229   ASSERT_EQ(0u, al1.debug_get_free());
 230
 231   al1.free_l1(i2);
 232   al1.free_l1(i4);
 233
 234   i2 = al1.allocate_l1_cont(0x4000, 0x2000, 0, num_l1_entries);
 235   ASSERT_EQ(i2.length, 0u);
 236   i2 = al1.allocate_l1_cont(0x4000, 0x1000, 0, num_l1_entries);
 237   ASSERT_EQ(i2.length, 0x1000u);
 238
 239   al1.free_l1(i3);
 240   i3 = al1.allocate_l1_cont(0x6000, 0x3000, 0, num_l1_entries);
 241   ASSERT_EQ(i3.length, 0u);
 242   i3 = al1.allocate_l1_cont(0x6000, 0x1000, 0, num_l1_entries);
 243   ASSERT_EQ(i3.length, 0x2000u);
 244   ASSERT_EQ(0u, al1.debug_get_free());
 245
 246   std::cout << "Done L1" << std::endl;
 247 }
 248
 249 TEST(TestAllocatorLevel01, test_l2)
 250 {
 251   TestAllocatorLevel02 al2;
 252   uint64_t num_l2_entries = 64;// *512;
 253   uint64_t capacity = num_l2_entries * 256 * 512 * 4096;
 254   al2.init(capacity, 0x1000);
 255   std::cout << "Init L2" << std::endl;
 256
 257   uint64_t allocated1 = 0;
 258   interval_vector_t a1;
 259   al2.allocate_l2(0x2000, 0x2000, &allocated1, &a1);
 260   ASSERT_EQ(allocated1, 0x2000u);
 261   ASSERT_EQ(a1[0].offset, 0u);
 262   ASSERT_EQ(a1[0].length, 0x2000u);
 263
 264   // limit query range in debug_get_free for the sake of performance
 265   ASSERT_EQ(0x2000u, al2.debug_get_allocated(0, 1));
 266   ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
 267
 268   uint64_t allocated2 = 0;
 269   interval_vector_t a2;
 270   al2.allocate_l2(0x2000, 0x2000, &allocated2, &a2);
 271   ASSERT_EQ(allocated2, 0x2000u);
 272   ASSERT_EQ(a2[0].offset, 0x2000u);
 273   ASSERT_EQ(a2[0].length, 0x2000u);
 274   // limit query range in debug_get_free for the sake of performance
 275   ASSERT_EQ(0x4000u, al2.debug_get_allocated(0, 1));
 276   ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
 277
 278   al2.free_l2(a1);
 279
 280   allocated2 = 0;
 281   a2.clear();
 282   al2.allocate_l2(0x1000, 0x1000, &allocated2, &a2);
 283   ASSERT_EQ(allocated2, 0x1000u);
 284   ASSERT_EQ(a2[0].offset, 0x0000u);
 285   ASSERT_EQ(a2[0].length, 0x1000u);
 286   // limit query range in debug_get_free for the sake of performance
 287   ASSERT_EQ(0x3000u, al2.debug_get_allocated(0, 1));
 288   ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
 289
 290   uint64_t allocated3 = 0;
 291   interval_vector_t a3;
 292   al2.allocate_l2(0x2000, 0x1000, &allocated3, &a3);
 293   ASSERT_EQ(allocated3, 0x2000u);
 294   ASSERT_EQ(a3.size(), 2u);
 295   ASSERT_EQ(a3[0].offset, 0x1000u);
 296   ASSERT_EQ(a3[0].length, 0x1000u);
 297   ASSERT_EQ(a3[1].offset, 0x4000u);
 298   ASSERT_EQ(a3[1].length, 0x1000u);
 299   // limit query range in debug_get_free for the sake of performance
 300   ASSERT_EQ(0x5000u, al2.debug_get_allocated(0, 1));
 301   ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
 302   {
 303     interval_vector_t r;
 304     r.emplace_back(0x0, 0x5000);
 305     al2.free_l2(r);
 306   }
 307
 308   a3.clear();
 309   allocated3 = 0;
 310   al2.allocate_l2(_1m, _1m, &allocated3, &a3);
 311   ASSERT_EQ(a3.size(), 1u);
 312   ASSERT_EQ(a3[0].offset, 0u);
 313   ASSERT_EQ(a3[0].length, _1m);
 314
 315   al2.free_l2(a3);
 316
 317   a3.clear();
 318   allocated3 = 0;
 319   al2.allocate_l2(4 * _1m, _1m, &allocated3, &a3);
 320   ASSERT_EQ(a3.size(), 1u);
 321   ASSERT_EQ(a3[0].offset, 0u);
 322   ASSERT_EQ(a3[0].length, 4 * _1m);
 323
 324   al2.free_l2(a3);
 325
 326 #ifndef _DEBUG
 327   for (uint64_t i = 0; i < capacity; i += 0x1000) {
 328     uint64_t allocated4 = 0;
 329     interval_vector_t a4;
 330     al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 331     ASSERT_EQ(a4.size(), 1u);
 332     ASSERT_EQ(a4[0].offset, i);
 333     ASSERT_EQ(a4[0].length, 0x1000u);
 334     if (0 == (i % (1 * 1024 * _1m))) {
 335       std::cout << "alloc1 " << i / 1024 / 1024 << " mb of "
 336         << capacity / 1024 / 1024 << std::endl;
 337     }
 338   }
 339 #else
 340   for (uint64_t i = 0; i < capacity; i += _2m) {
 341     uint64_t allocated4 = 0;
 342     interval_vector_t a4;
 343     al2.allocate_l2(_2m, _2m, &allocated4, &a4);
 344     ASSERT_EQ(a4.size(), 1);
 345     ASSERT_EQ(a4[0].offset, i);
 346     ASSERT_EQ(a4[0].length, _2m);
 347     if (0 == (i % (1 * 1024 * _1m))) {
 348       std::cout << "alloc1 " << i / 1024 / 1024 << " mb of "
 349                 << capacity / 1024 / 1024 << std::endl;
 350     }
 351   }
 352 #endif
 353
 354   ASSERT_EQ(0u, al2.debug_get_free());
 355   for (uint64_t i = 0; i < capacity; i += _1m) {
 356     interval_vector_t r;
 357     r.emplace_back(i, _1m);
 358     al2.free_l2(r);
 359     if (0 == (i % (1 * 1024 * _1m))) {
 360       std::cout << "free1 " << i / 1024 / 1024 << " mb of "
 361         << capacity / 1024 / 1024 << std::endl;
 362     }
 363   }
 364   ASSERT_EQ(capacity, al2.debug_get_free());
 365
 366   for (uint64_t i = 0; i < capacity; i += _1m) {
 367     uint64_t allocated4 = 0;
 368     interval_vector_t a4;
 369     al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 370     ASSERT_EQ(a4.size(), 1u);
 371     ASSERT_EQ(allocated4, _1m);
 372     ASSERT_EQ(a4[0].offset, i);
 373     ASSERT_EQ(a4[0].length, _1m);
 374     if (0 == (i % (1 * 1024 * _1m))) {
 375       std::cout << "alloc2 " << i / 1024 / 1024 << " mb of "
 376         << capacity / 1024 / 1024 << std::endl;
 377     }
 378   }
 379   ASSERT_EQ(0u, al2.debug_get_free());
 380   uint64_t allocated4 = 0;
 381   interval_vector_t a4;
 382   al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 383   ASSERT_EQ(a4.size(), 0u);
 384   al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 385   ASSERT_EQ(a4.size(), 0u);
 386
 387   for (uint64_t i = 0; i < capacity; i += 0x2000) {
 388     interval_vector_t r;
 389     r.emplace_back(i, 0x1000);
 390     al2.free_l2(r);
 391     if (0 == (i % (1 * 1024 * _1m))) {
 392       std::cout << "free2 " << i / 1024 / 1024 << " mb of "
 393         << capacity / 1024 / 1024 << std::endl;
 394     }
 395   }
 396   ASSERT_EQ(capacity / 2, al2.debug_get_free());
 397
 398   // unable to allocate due to fragmentation
 399   al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 400   ASSERT_EQ(a4.size(), 0u);
 401
 402   for (uint64_t i = 0; i < capacity; i += 2 * _1m) {
 403     a4.clear();
 404     allocated4 = 0;
 405     al2.allocate_l2(_1m, 0x1000, &allocated4, &a4);
 406     ASSERT_EQ(a4.size(), _1m / 0x1000);
 407     ASSERT_EQ(allocated4, _1m);
 408     ASSERT_EQ(a4[0].offset, i);
 409     ASSERT_EQ(a4[0].length, 0x1000u);
 410     if (0 == (i % (1 * 1024 * _1m))) {
 411       std::cout << "alloc3 " << i / 1024 / 1024 << " mb of "
 412         << capacity / 1024 / 1024 << std::endl;
 413     }
 414   }
 415   ASSERT_EQ(0u, al2.debug_get_free());
 416
 417   std::cout << "Done L2" << std::endl;
 418 }
 419
 420 TEST(TestAllocatorLevel01, test_l2_huge)
 421 {
 422   TestAllocatorLevel02 al2;
 423   uint64_t num_l2_entries = 4 * 512;
 424   uint64_t capacity = num_l2_entries * 256 * 512 * 4096; // 1 TB
 425   al2.init(capacity, 0x1000);
 426   std::cout << "Init L2 Huge" << std::endl;
 427
 428   for (uint64_t i = 0; i < capacity; i += _1m) {
 429     uint64_t allocated4 = 0;
 430     interval_vector_t a4;
 431     al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 432     ASSERT_EQ(a4.size(), 1u);
 433     ASSERT_EQ(allocated4, 0x1000u);
 434     ASSERT_EQ(a4[0].offset, i);
 435     ASSERT_EQ(a4[0].length, 0x1000u);
 436
 437     allocated4 = 0;
 438     a4.clear();
 439     al2.allocate_l2(_1m - 0x1000, 0x1000, &allocated4, &a4);
 440     ASSERT_EQ(a4.size(), 1u);
 441     ASSERT_EQ(allocated4, _1m - 0x1000);
 442     ASSERT_EQ(a4[0].offset, i + 0x1000);
 443     ASSERT_EQ(a4[0].length, _1m - 0x1000);
 444     if (0 == (i % (1 * 1024 * _1m))) {
 445       std::cout << "allocH " << i / 1024 / 1024 << " mb of "
 446         << capacity / 1024 / 1024 << std::endl;
 447     }
 448   }
 449   for (uint64_t i = 0; i < capacity; i += _1m) {
 450     interval_vector_t a4;
 451     a4.emplace_back(i, 0x1000);
 452     al2.free_l2(a4);
 453     if (0 == (i % (1 * 1024 * _1m))) {
 454       std::cout << "freeH1 " << i / 1024 / 1024 << " mb of "
 455         << capacity / 1024 / 1024 << std::endl;
 456     }
 457   }
 458   {
 459     std::cout << "Try" << std::endl;
 460     time_t t = time(NULL);
 461     for (int i = 0; i < 10; ++i) {
 462       uint64_t allocated = 0;
 463       interval_vector_t a;
 464       al2.allocate_l2(0x2000, 0x2000, &allocated, &a);
 465       ASSERT_EQ(a.size(), 0u);
 466     }
 467     std::cout << "End try in " << time(NULL) - t << " seconds" << std::endl;
 468   }
 469   {
 470     std::cout << "Try" << std::endl;
 471     time_t t = time(NULL);
 472     for (int i = 0; i < 10; ++i) {
 473       uint64_t allocated = 0;
 474       interval_vector_t a;
 475       al2.allocate_l2(_2m, _2m, &allocated, &a);
 476       ASSERT_EQ(a.size(), 0u);
 477     }
 478     std::cout << "End try in " << time(NULL) - t << " seconds" << std::endl;
 479   }
 480
 481   ASSERT_EQ((capacity / _1m) * 0x1000, al2.debug_get_free());
 482
 483   std::cout << "Done L2 Huge" << std::endl;
 484 }
 485
 486 TEST(TestAllocatorLevel01, test_l2_unaligned)
 487 {
 488   {
 489     TestAllocatorLevel02 al2;
 490     uint64_t num_l2_entries = 3;
 491     uint64_t capacity = num_l2_entries * 256 * 512 * 4096; // 3x512 MB
 492     al2.init(capacity, 0x1000);
 493     std::cout << "Init L2 Unaligned" << std::endl;
 494
 495     for (uint64_t i = 0; i < capacity; i += _1m / 2) {
 496       uint64_t allocated4 = 0;
 497       interval_vector_t a4;
 498       al2.allocate_l2(_1m / 2, _1m / 2, &allocated4, &a4);
 499       ASSERT_EQ(a4.size(), 1u);
 500       ASSERT_EQ(allocated4, _1m / 2);
 501       ASSERT_EQ(a4[0].offset, i);
 502       ASSERT_EQ(a4[0].length, _1m / 2);
 503       if (0 == (i % (1 * 1024 * _1m))) {
 504         std::cout << "allocU " << i / 1024 / 1024 << " mb of "
 505           << capacity / 1024 / 1024 << std::endl;
 506       }
 507     }
 508     ASSERT_EQ(0u, al2.debug_get_free());
 509     {
 510       // no space to allocate
 511       uint64_t allocated4 = 0;
 512       interval_vector_t a4;
 513       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 514       ASSERT_EQ(a4.size(), 0u);
 515     }
 516   }
 517   {
 518     TestAllocatorLevel02 al2;
 519     uint64_t capacity = 500 * 512 * 4096; // 500x2 MB
 520     al2.init(capacity, 0x1000);
 521     std::cout << ("Init L2 Unaligned2\n");
 522     for (uint64_t i = 0; i < capacity; i += _1m / 2) {
 523       uint64_t allocated4 = 0;
 524       interval_vector_t a4;
 525       al2.allocate_l2(_1m / 2, _1m / 2, &allocated4, &a4);
 526       ASSERT_EQ(a4.size(), 1u);
 527       ASSERT_EQ(allocated4, _1m / 2);
 528       ASSERT_EQ(a4[0].offset, i);
 529       ASSERT_EQ(a4[0].length, _1m / 2);
 530       if (0 == (i % (1 * 1024 * _1m))) {
 531         std::cout << "allocU2 " << i / 1024 / 1024 << " mb of "
 532           << capacity / 1024 / 1024 << std::endl;
 533       }
 534     }
 535     ASSERT_EQ(0u, al2.debug_get_free());
 536     {
 537       // no space to allocate
 538       uint64_t allocated4 = 0;
 539       interval_vector_t a4;
 540       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 541       ASSERT_EQ(a4.size(), 0u);
 542     }
 543   }
 544
 545   {
 546     TestAllocatorLevel02 al2;
 547     uint64_t capacity = 100 * 512 * 4096 + 127 * 4096;
 548     al2.init(capacity, 0x1000);
 549     std::cout << "Init L2 Unaligned2" << std::endl;
 550     for (uint64_t i = 0; i < capacity; i += 0x1000) {
 551       uint64_t allocated4 = 0;
 552       interval_vector_t a4;
 553       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 554       ASSERT_EQ(a4.size(), 1u);
 555       ASSERT_EQ(allocated4, 0x1000u);
 556       ASSERT_EQ(a4[0].offset, i);
 557       ASSERT_EQ(a4[0].length, 0x1000u);
 558     }
 559     ASSERT_EQ(0u, al2.debug_get_free());
 560     {
 561       // no space to allocate
 562       uint64_t allocated4 = 0;
 563       interval_vector_t a4;
 564       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 565       ASSERT_EQ(a4.size(), 0u);
 566     }
 567   }
 568   {
 569     TestAllocatorLevel02 al2;
 570     uint64_t capacity = 3 * 4096;
 571     al2.init(capacity, 0x1000);
 572     std::cout << "Init L2 Unaligned2" << std::endl;
 573     for (uint64_t i = 0; i < capacity; i += 0x1000) {
 574       uint64_t allocated4 = 0;
 575       interval_vector_t a4;
 576       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 577       ASSERT_EQ(a4.size(), 1u);
 578       ASSERT_EQ(allocated4, 0x1000u);
 579       ASSERT_EQ(a4[0].offset, i);
 580       ASSERT_EQ(a4[0].length, 0x1000u);
 581     }
 582     ASSERT_EQ(0u, al2.debug_get_free());
 583     {
 584       // no space to allocate
 585       uint64_t allocated4 = 0;
 586       interval_vector_t a4;
 587       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 588       ASSERT_EQ(a4.size(), 0u);
 589     }
 590   }
 591
 592   std::cout << "Done L2 Unaligned" << std::endl;
 593 }
 594
 595 TEST(TestAllocatorLevel01, test_l2_contiguous_alignment)
 596 {
 597   {
 598     TestAllocatorLevel02 al2;
 599     uint64_t num_l2_entries = 3;
 600     uint64_t capacity = num_l2_entries * 256 * 512 * 4096; // 3x512 MB
 601     uint64_t num_chunks = capacity / 4096;
 602     al2.init(capacity, 4096);
 603     std::cout << "Init L2 cont aligned" << std::endl;
 604
 605     std::map<size_t, size_t> bins_overall;
 606     al2.collect_stats(bins_overall);
 607     ASSERT_EQ(bins_overall.size(), 1u);
 608 //    std::cout<<bins_overall.begin()->first << std::endl;
 609     ASSERT_EQ(bins_overall[cbits(num_chunks) - 1], 1u);
 610
 611     for (uint64_t i = 0; i < capacity / 2; i += _1m) {
 612       uint64_t allocated4 = 0;
 613       interval_vector_t a4;
 614       al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 615       ASSERT_EQ(a4.size(), 1u);
 616       ASSERT_EQ(allocated4, _1m);
 617       ASSERT_EQ(a4[0].offset, i);
 618       ASSERT_EQ(a4[0].length, _1m);
 619     }
 620     ASSERT_EQ(capacity / 2, al2.debug_get_free());
 621
 622     bins_overall.clear();
 623     al2.collect_stats(bins_overall);
 624     ASSERT_EQ(bins_overall.size(), 1u);
 625     ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 626
 627     {
 628       size_t to_release = 2 * _1m + 0x1000;
 629       // release 2M + 4K at the beginning
 630       interval_vector_t r;
 631       r.emplace_back(0, to_release);
 632       al2.free_l2(r);
 633       bins_overall.clear();
 634       al2.collect_stats(bins_overall);
 635       ASSERT_EQ(bins_overall.size(), 2u);
 636       ASSERT_EQ(bins_overall[cbits(to_release / 0x1000) - 1], 1u);
 637       ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 638     }
 639     {
 640       // allocate 4K within the deallocated range
 641       uint64_t allocated4 = 0;
 642       interval_vector_t a4;
 643       al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
 644       ASSERT_EQ(a4.size(), 1u);
 645       ASSERT_EQ(allocated4, 0x1000u);
 646       ASSERT_EQ(a4[0].offset, 0u);
 647       ASSERT_EQ(a4[0].length, 0x1000u);
 648       bins_overall.clear();
 649       al2.collect_stats(bins_overall);
 650       ASSERT_EQ(bins_overall.size(), 2u);
 651       ASSERT_EQ(bins_overall[cbits(2 * _1m / 0x1000) - 1], 1u);
 652       ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 653     }
 654     {
 655       // allocate 1M - should go to the second 1M chunk
 656       uint64_t allocated4 = 0;
 657       interval_vector_t a4;
 658       al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 659       ASSERT_EQ(a4.size(), 1u);
 660       ASSERT_EQ(allocated4, _1m);
 661       ASSERT_EQ(a4[0].offset, _1m);
 662       ASSERT_EQ(a4[0].length, _1m);
 663       bins_overall.clear();
 664       al2.collect_stats(bins_overall);
 665       ASSERT_EQ(bins_overall.size(), 3u);
 666       ASSERT_EQ(bins_overall[0], 1u);
 667       ASSERT_EQ(bins_overall[cbits((_1m - 0x1000) / 0x1000) - 1], 1u);
 668       ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 669     }
 670     {
 671       // and allocate yet another 8K within the deallocated range
 672       uint64_t allocated4 = 0;
 673       interval_vector_t a4;
 674       al2.allocate_l2(0x2000, 0x1000, &allocated4, &a4);
 675       ASSERT_EQ(a4.size(), 1u);
 676       ASSERT_EQ(allocated4, 0x2000u);
 677       ASSERT_EQ(a4[0].offset, 0x1000u);
 678       ASSERT_EQ(a4[0].length, 0x2000u);
 679       bins_overall.clear();
 680       al2.collect_stats(bins_overall);
 681       ASSERT_EQ(bins_overall[0], 1u);
 682       ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
 683       ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 684     }
 685     {
 686       // release just allocated 1M
 687       interval_vector_t r;
 688       r.emplace_back(_1m, _1m);
 689       al2.free_l2(r);
 690       bins_overall.clear();
 691       al2.collect_stats(bins_overall);
 692       ASSERT_EQ(bins_overall.size(), 2u);
 693       ASSERT_EQ(bins_overall[cbits((2 * _1m - 0x3000) / 0x1000) - 1], 1u);
 694       ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 695     }
 696     {
 697       // allocate 3M - should go to the second 1M chunk and @capacity/2
 698       uint64_t allocated4 = 0;
 699       interval_vector_t a4;
 700       al2.allocate_l2(3 * _1m, _1m, &allocated4, &a4);
 701       ASSERT_EQ(a4.size(), 2u);
 702       ASSERT_EQ(allocated4, 3 * _1m);
 703       ASSERT_EQ(a4[0].offset, _1m);
 704       ASSERT_EQ(a4[0].length, _1m);
 705       ASSERT_EQ(a4[1].offset, capacity / 2);
 706       ASSERT_EQ(a4[1].length, 2 * _1m);
 707       bins_overall.clear();
 708       al2.collect_stats(bins_overall);
 709       ASSERT_EQ(bins_overall.size(), 3u);
 710       ASSERT_EQ(bins_overall[0], 1u);
 711       ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
 712       ASSERT_EQ(bins_overall[cbits((num_chunks - 512) / 2) - 1], 1u);
 713     }
 714     {
 715       // release allocated 1M in the second meg chunk except
 716       // the first 4K chunk
 717       interval_vector_t r;
 718       r.emplace_back(_1m + 0x1000, _1m);
 719       al2.free_l2(r);
 720       bins_overall.clear();
 721       al2.collect_stats(bins_overall);
 722       ASSERT_EQ(bins_overall.size(), 3u);
 723       ASSERT_EQ(bins_overall[cbits(_1m / 0x1000) - 1], 1u);
 724       ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
 725       ASSERT_EQ(bins_overall[cbits((num_chunks - 512) / 2) - 1], 1u);
 726     }
 727     {
 728       // release 2M @(capacity / 2)
 729       interval_vector_t r;
 730       r.emplace_back(capacity / 2, 2 * _1m);
 731       al2.free_l2(r);
 732       bins_overall.clear();
 733       al2.collect_stats(bins_overall);
 734       ASSERT_EQ(bins_overall.size(), 3u);
 735       ASSERT_EQ(bins_overall[cbits(_1m / 0x1000) - 1], 1u);
 736       ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
 737       ASSERT_EQ(bins_overall[cbits((num_chunks) / 2) - 1], 1u);
 738     }
 739     {
 740       // allocate 4x512K - should go to the second halves of
 741       // the first and second 1M chunks and @(capacity / 2)
 742       uint64_t allocated4 = 0;
 743       interval_vector_t a4;
 744       al2.allocate_l2(2 * _1m, _1m / 2, &allocated4, &a4);
 745       ASSERT_EQ(a4.size(), 3u);
 746       ASSERT_EQ(allocated4, 2 * _1m);
 747       ASSERT_EQ(a4[0].offset, _1m / 2);
 748       ASSERT_EQ(a4[0].length, _1m / 2);
 749       ASSERT_EQ(a4[1].offset, _1m + _1m / 2);
 750       ASSERT_EQ(a4[1].length, _1m / 2);
 751       ASSERT_EQ(a4[2].offset, capacity / 2);
 752       ASSERT_EQ(a4[2].length, _1m);
 753
 754       bins_overall.clear();
 755       al2.collect_stats(bins_overall);
 756       ASSERT_EQ(bins_overall.size(), 3u);
 757       ASSERT_EQ(bins_overall[0], 1u);
 758       // below we have 512K - 4K & 512K - 12K chunks which both fit into
 759       // the same bin = 6
 760       ASSERT_EQ(bins_overall[6], 2u);
 761       ASSERT_EQ(bins_overall[cbits((num_chunks - 256) / 2) - 1], 1u);
 762
 763     }
 764     {
 765       // cleanup first 2M except except the last 4K chunk
 766       interval_vector_t r;
 767       r.emplace_back(0, 2 * _1m - 0x1000);
 768       al2.free_l2(r);
 769       bins_overall.clear();
 770       al2.collect_stats(bins_overall);
 771
 772       ASSERT_EQ(bins_overall.size(), 3u);
 773       ASSERT_EQ(bins_overall[0], 1u);
 774       ASSERT_EQ(bins_overall[cbits((_2m - 0x1000) / 0x1000) - 1], 1u);
 775       ASSERT_EQ(bins_overall[cbits((num_chunks - 256) / 2) - 1], 1u);
 776     }
 777     {
 778       // release 2M @(capacity / 2)
 779       interval_vector_t r;
 780       r.emplace_back(capacity / 2, 2 * _1m);
 781       al2.free_l2(r);
 782       bins_overall.clear();
 783       al2.collect_stats(bins_overall);
 784
 785       ASSERT_EQ(bins_overall.size(), 3u);
 786       ASSERT_EQ(bins_overall[0], 1u);
 787       ASSERT_EQ(bins_overall[cbits((_2m - 0x1000) / 0x1000) - 1], 1u);
 788       ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
 789     }
 790     {
 791       // allocate 132M using 4M granularity should go to (capacity / 2)
 792       uint64_t allocated4 = 0;
 793       interval_vector_t a4;
 794       al2.allocate_l2(132 * _1m, 4 * _1m , &allocated4, &a4);
 795       ASSERT_EQ(a4.size(), 1u);
 796       ASSERT_EQ(a4[0].offset, capacity / 2);
 797       ASSERT_EQ(a4[0].length, 132 * _1m);
 798
 799       bins_overall.clear();
 800       al2.collect_stats(bins_overall);
 801       ASSERT_EQ(bins_overall.size(), 3u);
 802     }
 803     {
 804       // cleanup left 4K chunk in the first 2M
 805       interval_vector_t r;
 806       r.emplace_back(2 * _1m - 0x1000, 0x1000);
 807       al2.free_l2(r);
 808       bins_overall.clear();
 809       al2.collect_stats(bins_overall);
 810
 811       ASSERT_EQ(bins_overall.size(), 2u);
 812     }
 813     {
 814       // release 132M @(capacity / 2)
 815       interval_vector_t r;
 816       r.emplace_back(capacity / 2, 132 * _1m);
 817       al2.free_l2(r);
 818     }
 819     {
 820       // allocate 132M using 2M granularity should go to the first chunk and to
 821       // (capacity / 2)
 822       uint64_t allocated4 = 0;
 823       interval_vector_t a4;
 824       al2.allocate_l2(132 * _1m, 2 * _1m , &allocated4, &a4);
 825       ASSERT_EQ(a4.size(), 2u);
 826       ASSERT_EQ(a4[0].offset, 0u);
 827       ASSERT_EQ(a4[0].length, 2 * _1m);
 828       ASSERT_EQ(a4[1].offset, capacity / 2);
 829       ASSERT_EQ(a4[1].length, 130 * _1m);
 830     }
 831     {
 832       // release 130M @(capacity / 2)
 833       interval_vector_t r;
 834       r.emplace_back(capacity / 2, 132 * _1m);
 835       al2.free_l2(r);
 836     }
 837     {
 838       // release 4K~16K
 839       // release 28K~32K
 840       // release 68K~24K
 841       interval_vector_t r;
 842       r.emplace_back(0x1000, 0x4000);
 843       r.emplace_back(0x7000, 0x8000);
 844       r.emplace_back(0x11000, 0x6000);
 845       al2.free_l2(r);
 846     }
 847     {
 848       // allocate 32K using 16K granularity - should bypass the first
 849       // unaligned extent, use the second free extent partially given
 850       // the 16K alignment and then fallback to capacity / 2
 851       uint64_t allocated4 = 0;
 852       interval_vector_t a4;
 853       al2.allocate_l2(0x8000, 0x4000, &allocated4, &a4);
 854       ASSERT_EQ(a4.size(), 2u);
 855       ASSERT_EQ(a4[0].offset, 0x8000u);
 856       ASSERT_EQ(a4[0].length, 0x4000u);
 857       ASSERT_EQ(a4[1].offset, capacity / 2);
 858       ASSERT_EQ(a4[1].length, 0x4000u);
 859     }
 860
 861   }
 862   std::cout << "Done L2 cont aligned" << std::endl;
 863 }
 864
 865 TEST(TestAllocatorLevel01, test_4G_alloc_bug)
 866 {
 867   {
 868     TestAllocatorLevel02 al2;
 869     uint64_t capacity = 0x8000 * _1m; // = 32GB
 870     al2.init(capacity, 0x10000);
 871     std::cout << "Init L2 cont aligned" << std::endl;
 872
 873       uint64_t allocated4 = 0;
 874       interval_vector_t a4;
 875       al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 876       ASSERT_EQ(a4.size(), 1u); // the bug caused no allocations here
 877       ASSERT_EQ(allocated4, _1m);
 878       ASSERT_EQ(a4[0].offset, 0u);
 879       ASSERT_EQ(a4[0].length, _1m);
 880   }
 881 }
 882
 883 TEST(TestAllocatorLevel01, test_4G_alloc_bug2)
 884 {
 885   {
 886     TestAllocatorLevel02 al2;
 887     uint64_t capacity = 0x8000 * _1m; // = 32GB
 888     al2.init(capacity, 0x10000);
 889
 890     for (uint64_t i = 0; i < capacity; i += _1m) {
 891       uint64_t allocated4 = 0;
 892       interval_vector_t a4;
 893       al2.allocate_l2(_1m, _1m, &allocated4, &a4);
 894       ASSERT_EQ(a4.size(), 1u);
 895       ASSERT_EQ(allocated4, _1m);
 896       ASSERT_EQ(a4[0].offset, i);
 897       ASSERT_EQ(a4[0].length, _1m);
 898     }
 899     ASSERT_EQ(0u , al2.debug_get_free());
 900
 901     interval_vector_t r;
 902     r.emplace_back(0x5fec30000, 0x13d0000);
 903     r.emplace_back(0x628000000, 0x80000000);
 904     r.emplace_back(0x6a8000000, 0x80000000);
 905     r.emplace_back(0x728100000, 0x70000);
 906     al2.free_l2(r);
 907
 908     std::map<size_t, size_t> bins_overall;
 909     al2.collect_stats(bins_overall);
 910
 911     uint64_t allocated4 = 0;
 912     interval_vector_t a4;
 913     al2.allocate_l2(0x3e000000, _1m, &allocated4, &a4);
 914     ASSERT_EQ(a4.size(), 2u);
 915     ASSERT_EQ(allocated4, 0x3e000000u);
 916     ASSERT_EQ(a4[0].offset, 0x5fed00000u);
 917     ASSERT_EQ(a4[0].length, 0x1300000u);
 918     ASSERT_EQ(a4[1].offset, 0x628000000u);
 919     ASSERT_EQ(a4[1].length, 0x3cd00000u);
 920   }
 921 }
 922
 923 TEST(TestAllocatorLevel01, test_4G_alloc_bug3)
 924 {
 925   {
 926     TestAllocatorLevel02 al2;
 927     uint64_t capacity = 0x8000 * _1m; // = 32GB
 928     al2.init(capacity, 0x10000);
 929     std::cout << "Init L2 cont aligned" << std::endl;
 930
 931       uint64_t allocated4 = 0;
 932       interval_vector_t a4;
 933       al2.allocate_l2(4096ull * _1m, _1m, &allocated4, &a4);
 934       ASSERT_EQ(a4.size(), 2u); // allocator has to split into 2 allocations
 935       ASSERT_EQ(allocated4, 4096ull * _1m);
 936       ASSERT_EQ(a4[0].offset, 0u);
 937       ASSERT_EQ(a4[0].length, 2048ull * _1m);
 938       ASSERT_EQ(a4[1].offset, 2048ull * _1m);
 939       ASSERT_EQ(a4[1].length, 2048ull * _1m);
 940   }
 941 }
 942
 943 TEST(TestAllocatorLevel01, test_claim_free_l2)
 944 {
 945   TestAllocatorLevel02 al2;
 946   uint64_t num_l2_entries = 64;// *512;
 947   uint64_t capacity = num_l2_entries * 256 * 512 * 4096;
 948   al2.init(capacity, 0x1000);
 949   std::cout << "Init L2" << std::endl;
 950
 951   uint64_t max_available = 0x20000;
 952   al2.mark_allocated(max_available, capacity - max_available);
 953
 954   uint64_t allocated1 = 0;
 955   interval_vector_t a1;
 956   al2.allocate_l2(0x2000, 0x2000, &allocated1, &a1);
 957   ASSERT_EQ(allocated1, 0x2000u);
 958   ASSERT_EQ(a1[0].offset, 0u);
 959   ASSERT_EQ(a1[0].length, 0x2000u);
 960
 961   uint64_t allocated2 = 0;
 962   interval_vector_t a2;
 963   al2.allocate_l2(0x2000, 0x2000, &allocated2, &a2);
 964   ASSERT_EQ(allocated2, 0x2000u);
 965   ASSERT_EQ(a2[0].offset, 0x2000u);
 966   ASSERT_EQ(a2[0].length, 0x2000u);
 967
 968   uint64_t allocated3 = 0;
 969   interval_vector_t a3;
 970   al2.allocate_l2(0x3000, 0x3000, &allocated3, &a3);
 971   ASSERT_EQ(allocated3, 0x3000u);
 972   ASSERT_EQ(a3[0].offset, 0x4000u);
 973   ASSERT_EQ(a3[0].length, 0x3000u);
 974
 975   al2.free_l2(a1);
 976   al2.free_l2(a3);
 977   ASSERT_EQ(max_available - 0x2000, al2.debug_get_free());
 978
 979   auto claimed = al2.claim_free_to_right(0x4000);
 980   ASSERT_EQ(max_available - 0x4000u, claimed);
 981   ASSERT_EQ(0x2000, al2.debug_get_free());
 982
 983   claimed = al2.claim_free_to_right(0x4000);
 984   ASSERT_EQ(0, claimed);
 985   ASSERT_EQ(0x2000, al2.debug_get_free());
 986
 987   claimed = al2.claim_free_to_left(0x2000);
 988   ASSERT_EQ(0x2000u, claimed);
 989   ASSERT_EQ(0, al2.debug_get_free());
 990
 991   claimed = al2.claim_free_to_left(0x2000);
 992   ASSERT_EQ(0, claimed);
 993   ASSERT_EQ(0, al2.debug_get_free());
 994
 995
 996   al2.mark_free(0x3000, 0x4000);
 997   ASSERT_EQ(0x4000, al2.debug_get_free());
 998
 999   claimed = al2.claim_free_to_right(0x7000);
1000   ASSERT_EQ(0, claimed);
1001   ASSERT_EQ(0x4000, al2.debug_get_free());
1002
1003   claimed = al2.claim_free_to_right(0x6000);
1004   ASSERT_EQ(0x1000, claimed);
1005   ASSERT_EQ(0x3000, al2.debug_get_free());
1006
1007   claimed = al2.claim_free_to_right(0x6000);
1008   ASSERT_EQ(0, claimed);
1009   ASSERT_EQ(0x3000, al2.debug_get_free());
1010
1011   claimed = al2.claim_free_to_left(0x3000);
1012   ASSERT_EQ(0u, claimed);
1013   ASSERT_EQ(0x3000, al2.debug_get_free());
1014
1015   claimed = al2.claim_free_to_left(0x4000);
1016   ASSERT_EQ(0x1000, claimed);
1017   ASSERT_EQ(0x2000, al2.debug_get_free());
1018
1019   // extend allocator space up to 64M
1020   auto max_available2 = 64 * 1024 * 1024;
1021   al2.mark_free(max_available, max_available2 - max_available);
1022   ASSERT_EQ(max_available2 - max_available + 0x2000, al2.debug_get_free());
1023
1024   // pin some allocations
1025   al2.mark_allocated(0x400000 + 0x2000, 1000);
1026   al2.mark_allocated(0x400000 + 0x5000, 1000);
1027   al2.mark_allocated(0x400000 + 0x20000, 1000);
1028   ASSERT_EQ(max_available2 - max_available - 0x1000, al2.debug_get_free());
1029
1030   claimed = al2.claim_free_to_left(0x403000);
1031   ASSERT_EQ(0x0, claimed);
1032
1033   claimed = al2.claim_free_to_left(0x404000);
1034   ASSERT_EQ(0x1000, claimed);
1035   ASSERT_EQ(max_available2 - max_available - 0x2000, al2.debug_get_free());
1036
1037   claimed = al2.claim_free_to_left(max_available);
1038   ASSERT_EQ(0, claimed);
1039
1040   claimed = al2.claim_free_to_left(0x400000);
1041   ASSERT_EQ(0x3e0000, claimed);
1042   ASSERT_EQ(max_available2 - max_available - 0x3e2000, al2.get_available());
1043   ASSERT_EQ(max_available2 - max_available - 0x3e2000, al2.debug_get_free());
1044
1045   claimed = al2.claim_free_to_right(0x407000);
1046   ASSERT_EQ(0x19000, claimed);
1047   ASSERT_EQ(max_available2 - max_available - 0x3e2000 - 0x19000,
1048     al2.get_available());
1049   ASSERT_EQ(max_available2 - max_available - 0x3e2000 - 0x19000,
1050     al2.debug_get_free());
1051
1052   claimed = al2.claim_free_to_right(0x407000);
1053   ASSERT_EQ(0, claimed);
1054
1055   claimed = al2.claim_free_to_right(0x430000);
1056   ASSERT_EQ(max_available2 - 0x430000, claimed);
1057   ASSERT_EQ(0x15000,
1058     al2.get_available());
1059   ASSERT_EQ(0x15000,
1060     al2.debug_get_free());
1061 }