ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
{
+ // Original free space disposition (start chunk, count):
+ // <NC/2, NC/2>
size_t to_release = 2 * _1m + 0x1000;
// release 2M + 4K at the beginning
interval_vector_t r;
ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <0, 513>, <NC / 2, NC / 2>
// allocate 4K within the deallocated range
uint64_t allocated4 = 0;
interval_vector_t a4;
ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
- // allocate 1M - should go to the second 1M chunk
+ // Original free space disposition (start chunk, count):
+ // <1, 512>, <NC / 2, NC / 2>
+ // allocate 1M - should go to offset 4096
uint64_t allocated4 = 0;
interval_vector_t a4;
al2.allocate_l2(_1m, _1m, &allocated4, &a4);
ASSERT_EQ(a4.size(), 1u);
ASSERT_EQ(allocated4, _1m);
- ASSERT_EQ(a4[0].offset, _1m);
+ ASSERT_EQ(a4[0].offset, 4096);
ASSERT_EQ(a4[0].length, _1m);
bins_overall.clear();
al2.collect_stats(bins_overall);
- ASSERT_EQ(bins_overall.size(), 3u);
- ASSERT_EQ(bins_overall[0], 1u);
- ASSERT_EQ(bins_overall[cbits((_1m - 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits(_1m / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <257, 256>, <NC / 2, NC / 2>
// and allocate yet another 8K within the deallocated range
uint64_t allocated4 = 0;
interval_vector_t a4;
al2.allocate_l2(0x2000, 0x1000, &allocated4, &a4);
ASSERT_EQ(a4.size(), 1u);
ASSERT_EQ(allocated4, 0x2000u);
- ASSERT_EQ(a4[0].offset, 0x1000u);
+ ASSERT_EQ(a4[0].offset, _1m + 0x1000u);
ASSERT_EQ(a4[0].length, 0x2000u);
bins_overall.clear();
al2.collect_stats(bins_overall);
- ASSERT_EQ(bins_overall[0], 1u);
- ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
- // release just allocated 1M
+ // Original free space disposition (start chunk, count):
+ // <259, 254>, <NC / 2, NC / 2>
+ // release 4K~1M
interval_vector_t r;
- r.emplace_back(_1m, _1m);
+ r.emplace_back(0x1000, _1m);
al2.free_l2(r);
bins_overall.clear();
al2.collect_stats(bins_overall);
- ASSERT_EQ(bins_overall.size(), 2u);
- ASSERT_EQ(bins_overall[cbits((2 * _1m - 0x3000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall.size(), 3u);
+ //ASSERT_EQ(bins_overall[cbits((2 * _1m - 0x3000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits(_1m / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
- // allocate 3M - should go to the second 1M chunk and @capacity/2
+ // Original free space disposition (start chunk, count):
+ // <1, 257>, <259, 254>, <NC / 2, NC / 2>
+ // allocate 3M - should go to the first 1M chunk and @capacity/2
uint64_t allocated4 = 0;
interval_vector_t a4;
al2.allocate_l2(3 * _1m, _1m, &allocated4, &a4);
ASSERT_EQ(a4.size(), 2u);
ASSERT_EQ(allocated4, 3 * _1m);
- ASSERT_EQ(a4[0].offset, _1m);
+ ASSERT_EQ(a4[0].offset, 0x1000);
ASSERT_EQ(a4[0].length, _1m);
ASSERT_EQ(a4[1].offset, capacity / 2);
ASSERT_EQ(a4[1].length, 2 * _1m);
bins_overall.clear();
al2.collect_stats(bins_overall);
- ASSERT_EQ(bins_overall.size(), 3u);
- ASSERT_EQ(bins_overall[0], 1u);
- ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits((num_chunks - 512) / 2) - 1], 1u);
}
{
- // release allocated 1M in the second meg chunk except
+ // Original free space disposition (start chunk, count):
+ // <259, 254>, <NC / 2 - 512, NC / 2 - 512>
+ // release allocated 1M in the first meg chunk except
// the first 4K chunk
interval_vector_t r;
- r.emplace_back(_1m + 0x1000, _1m);
+ r.emplace_back(0x1000, _1m);
al2.free_l2(r);
bins_overall.clear();
al2.collect_stats(bins_overall);
ASSERT_EQ(bins_overall.size(), 3u);
ASSERT_EQ(bins_overall[cbits(_1m / 0x1000) - 1], 1u);
- ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits((num_chunks - 512) / 2) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <1, 256>, <259, 254>, <NC / 2 - 512, NC / 2 - 512>
// release 2M @(capacity / 2)
interval_vector_t r;
r.emplace_back(capacity / 2, 2 * _1m);
al2.collect_stats(bins_overall);
ASSERT_EQ(bins_overall.size(), 3u);
ASSERT_EQ(bins_overall[cbits(_1m / 0x1000) - 1], 1u);
- ASSERT_EQ(bins_overall[cbits((_1m - 0x3000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits((num_chunks) / 2) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <1, 256>, <259, 254>, <NC / 2, NC / 2>
// allocate 4x512K - should go to the second halves of
// the first and second 1M chunks and @(capacity / 2)
uint64_t allocated4 = 0;
al2.allocate_l2(2 * _1m, _1m / 2, &allocated4, &a4);
ASSERT_EQ(a4.size(), 3u);
ASSERT_EQ(allocated4, 2 * _1m);
- ASSERT_EQ(a4[0].offset, _1m / 2);
+ ASSERT_EQ(a4[1].offset, 0x1000);
+ ASSERT_EQ(a4[1].length, _1m);
+ ASSERT_EQ(a4[0].offset, _1m + 0x3000);
ASSERT_EQ(a4[0].length, _1m / 2);
- ASSERT_EQ(a4[1].offset, _1m + _1m / 2);
- ASSERT_EQ(a4[1].length, _1m / 2);
ASSERT_EQ(a4[2].offset, capacity / 2);
- ASSERT_EQ(a4[2].length, _1m);
+ ASSERT_EQ(a4[2].length, _1m / 2);
bins_overall.clear();
al2.collect_stats(bins_overall);
- ASSERT_EQ(bins_overall.size(), 3u);
- ASSERT_EQ(bins_overall[0], 1u);
- // below we have 512K - 4K & 512K - 12K chunks which both fit into
- // the same bin = 6
- ASSERT_EQ(bins_overall[6], 2u);
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000 - 0x80000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits((num_chunks - 256) / 2) - 1], 1u);
}
{
- // cleanup first 2M except except the last 4K chunk
+ // Original free space disposition (start chunk, count):
+ // <387, 126>, <NC / 2 + 128, NC / 2 - 128>
+ // cleanup first 1536K except the last 4K chunk
interval_vector_t r;
- r.emplace_back(0, 2 * _1m - 0x1000);
+ r.emplace_back(0, _1m + _1m / 2 - 0x1000);
al2.free_l2(r);
bins_overall.clear();
al2.collect_stats(bins_overall);
ASSERT_EQ(bins_overall.size(), 3u);
- ASSERT_EQ(bins_overall[0], 1u);
- ASSERT_EQ(bins_overall[cbits((_2m - 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m + _1m / 2 - 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000 - 0x80000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits((num_chunks - 256) / 2) - 1], 1u);
}
{
- // release 2M @(capacity / 2)
+ // Original free space disposition (start chunk, count):
+ // <0, 383> <387, 126>, <NC / 2 + 128, NC / 2 - 128>
+ // release 512K @(capacity / 2)
interval_vector_t r;
- r.emplace_back(capacity / 2, 2 * _1m);
+ r.emplace_back(capacity / 2, _1m / 2);
al2.free_l2(r);
bins_overall.clear();
al2.collect_stats(bins_overall);
ASSERT_EQ(bins_overall.size(), 3u);
- ASSERT_EQ(bins_overall[0], 1u);
- ASSERT_EQ(bins_overall[cbits((_2m - 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m + _1m / 2 - 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000 - 0x80000) / 0x1000) - 1], 1u);
ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
- // allocate 132M using 4M granularity should go to (capacity / 2)
+ // Original free space disposition (start chunk, count):
+ // <0, 383> <387, 126>, <NC / 2, NC / 2>
+ // allocate 132M (=33792*4096) = using 4M granularity should go to (capacity / 2)
uint64_t allocated4 = 0;
interval_vector_t a4;
al2.allocate_l2(132 * _1m, 4 * _1m , &allocated4, &a4);
bins_overall.clear();
al2.collect_stats(bins_overall);
ASSERT_EQ(bins_overall.size(), 3u);
+ ASSERT_EQ(bins_overall[cbits((_1m + _1m / 2 - 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits((_1m - 0x2000 - 0x80000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2 - 33792) - 1], 1u);
}
{
- // cleanup left 4K chunk in the first 2M
+ // Original free space disposition (start chunk, count):
+ // <0, 383> <387, 126>, <NC / 2 + 33792, NC / 2 - 33792>
+ // cleanup remaining 4*4K chunks in the first 2M
interval_vector_t r;
- r.emplace_back(2 * _1m - 0x1000, 0x1000);
+ r.emplace_back(383 * 4096, 4 * 0x1000);
al2.free_l2(r);
bins_overall.clear();
al2.collect_stats(bins_overall);
ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits((2 * _1m + 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2 - 33792) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <0, 513>, <NC / 2 + 33792, NC / 2 - 33792>
// release 132M @(capacity / 2)
interval_vector_t r;
r.emplace_back(capacity / 2, 132 * _1m);
al2.free_l2(r);
+ bins_overall.clear();
+ al2.collect_stats(bins_overall);
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits((2 * _1m + 0x1000) / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <0, 513>, <NC / 2, NC / 2>
// allocate 132M using 2M granularity should go to the first chunk and to
// (capacity / 2)
uint64_t allocated4 = 0;
ASSERT_EQ(a4[0].length, 2 * _1m);
ASSERT_EQ(a4[1].offset, capacity / 2);
ASSERT_EQ(a4[1].length, 130 * _1m);
+
+ bins_overall.clear();
+ al2.collect_stats(bins_overall);
+
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits(0)], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2 - 33792) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <512, 1>, <NC / 2 + 33792, NC / 2 - 33792>
// release 130M @(capacity / 2)
interval_vector_t r;
r.emplace_back(capacity / 2, 132 * _1m);
al2.free_l2(r);
+ bins_overall.clear();
+ al2.collect_stats(bins_overall);
+
+ ASSERT_EQ(bins_overall.size(), 2u);
+ ASSERT_EQ(bins_overall[cbits(0)], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
+ // Original free space disposition (start chunk, count):
+ // <512,1>, <NC / 2, NC / 2>
// release 4K~16K
// release 28K~32K
// release 68K~24K
r.emplace_back(0x7000, 0x8000);
r.emplace_back(0x11000, 0x6000);
al2.free_l2(r);
+
+ bins_overall.clear();
+ al2.collect_stats(bins_overall);
+
+ ASSERT_EQ(bins_overall.size(), 4u);
+ ASSERT_EQ(bins_overall[cbits(0)], 1u);
+ ASSERT_EQ(bins_overall[cbits(0x4000 / 0x1000) - 1], 2u); // accounts both 0x4000 & 0x6000
+ ASSERT_EQ(bins_overall[cbits(0x8000 / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2) - 1], 1u);
}
{
- // allocate 32K using 16K granularity - should bypass the first
- // unaligned extent, use the second free extent partially given
- // the 16K alignment and then fallback to capacity / 2
+ // Original free space disposition (start chunk, count):
+ // <1, 4>, <7, 8>, <17, 6> <512,1>, <NC / 2, NC / 2>
+ // allocate 80K using 16K granularity
uint64_t allocated4 = 0;
interval_vector_t a4;
- al2.allocate_l2(0x8000, 0x4000, &allocated4, &a4);
- ASSERT_EQ(a4.size(), 2u);
- ASSERT_EQ(a4[0].offset, 0x8000u);
- ASSERT_EQ(a4[0].length, 0x4000u);
- ASSERT_EQ(a4[1].offset, capacity / 2);
+ al2.allocate_l2(0x14000, 0x4000, &allocated4, &a4);
+
+ ASSERT_EQ(a4.size(), 4);
+ ASSERT_EQ(a4[1].offset, 0x1000u);
ASSERT_EQ(a4[1].length, 0x4000u);
- }
+ ASSERT_EQ(a4[0].offset, 0x7000u);
+ ASSERT_EQ(a4[0].length, 0x8000u);
+ ASSERT_EQ(a4[2].offset, 0x11000u);
+ ASSERT_EQ(a4[2].length, 0x4000u);
+ ASSERT_EQ(a4[3].offset, capacity / 2);
+ ASSERT_EQ(a4[3].length, 0x4000u);
+
+ bins_overall.clear();
+ al2.collect_stats(bins_overall);
+ ASSERT_EQ(bins_overall.size(), 3u);
+ ASSERT_EQ(bins_overall[cbits(0)], 1u);
+ ASSERT_EQ(bins_overall[cbits(0x2000 / 0x1000) - 1], 1u);
+ ASSERT_EQ(bins_overall[cbits(num_chunks / 2 - 1) - 1], 1u);
+ }
+ {
+ // Original free space disposition (start chunk, count):
+ // <21, 2> <512,1>, <NC / 2 + 1, NC / 2 - 1>
+ }
}
std::cout << "Done L2 cont aligned" << std::endl;
}
al2.allocate_l2(0x3e000000, _1m, &allocated4, &a4);
ASSERT_EQ(a4.size(), 2u);
ASSERT_EQ(allocated4, 0x3e000000u);
- ASSERT_EQ(a4[0].offset, 0x5fed00000u);
+ ASSERT_EQ(a4[0].offset, 0x5fec30000u);
ASSERT_EQ(a4[0].length, 0x1300000u);
ASSERT_EQ(a4[1].offset, 0x628000000u);
ASSERT_EQ(a4[1].length, 0x3cd00000u);