1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Bitmap based in-memory allocator unit test cases.
5 * Author: Ramesh Chander, Ramesh.Chander@sandisk.com
8 #include "include/Context.h"
9 #include "os/bluestore/BitAllocator.h"
14 #include <gtest/gtest.h>
17 //#define bmap_test_assert(x) ASSERT_EQ(true, (x))
18 #define bmap_test_assert(x) assert((x))
19 #define NUM_THREADS 16
20 #define MAX_BLOCKS (1024 * 1024 * 1)
22 TEST(BitAllocator, test_bmap_iter)
31 void init(int index) {
37 BmapEntityTmp(int num) {
45 bool is_allocated(int64_t s, int64_t num)
50 BmapEntityTmp *obj = NULL;
52 mempool::bluestore_alloc::vector<BmapEntityTmp> *arr = new mempool::bluestore_alloc::vector<BmapEntityTmp>(num_items);
53 for (i = 0; i < num_items; i++) {
56 BitMapEntityIter<BmapEntityTmp> iter = BitMapEntityIter<BmapEntityTmp>(arr, off, false);
60 int64_t last_idx = off;
61 while ((obj = iter.next())) {
62 bmap_test_assert(obj->get_index() == last_idx);
63 bmap_test_assert(obj->get_index() == i);
64 bmap_test_assert(obj == &(*arr)[i]);
65 last_idx = iter.index();
69 bmap_test_assert(i == num_items);
70 bmap_test_assert(count == num_items - off);
72 iter = BitMapEntityIter<BmapEntityTmp>(arr, off, true);
77 while ((obj = iter.next())) {
78 bmap_test_assert(obj->get_index() == last_idx);
79 bmap_test_assert(obj->get_index() == i);
80 bmap_test_assert(obj == &(*arr)[i]);
81 last_idx = iter.index();
83 i = (i + 1) % num_items;
86 bmap_test_assert(i == off + 1);
87 bmap_test_assert(count == num_items + 1);
94 arr = new mempool::bluestore_alloc::vector<BmapEntityTmp>(num_items);
95 for (i = 0; i < num_items; i++) {
98 iter = BitMapEntityIter<BmapEntityTmp>(arr, off, true);
102 while ((obj = static_cast<BmapEntityTmp*>(iter.next()))) {
103 bmap_test_assert(obj->get_index() == last_idx);
104 bmap_test_assert(obj->get_index() == i);
105 bmap_test_assert(obj == &(*arr)[i]);
106 last_idx = iter.index();
107 i = (i + 1) % num_items;
110 bmap_test_assert(i == (off + 1)%num_items);
111 bmap_test_assert(count == num_items + 1);
116 * BitMapArea Iter tests.
118 BitMapArea *area = nullptr;
119 std::vector<BitMapArea*> children;
120 children.reserve(num_items);
121 for (i = 0; i < num_items; i++) {
122 children.emplace_back(new BitMapAreaLeaf(
124 BitMapArea::get_span_size(g_ceph_context), i, false));
128 BitMapAreaList *area_list = \
129 new BitMapAreaList(std::vector<BitMapArea*>(children));
130 BmapEntityListIter area_iter = BmapEntityListIter(
131 area_list, (int64_t) 0);
135 while ((area = area_iter.next())) {
136 bmap_test_assert(area->get_index() == last_idx);
137 bmap_test_assert(area->get_index() == i);
138 bmap_test_assert(area == children[i]);
139 last_idx = area_iter.index();
140 i = (i + 1) % num_items;
143 bmap_test_assert(i == off);
144 bmap_test_assert(count == num_items);
147 area_iter = BmapEntityListIter(area_list, off, true);
151 while ((area = area_iter.next())) {
152 bmap_test_assert(area->get_index() == last_idx);
153 bmap_test_assert(area->get_index() == i);
154 bmap_test_assert(area == children[i]);
155 last_idx = area_iter.index();
156 i = (i + 1) % num_items;
159 bmap_test_assert(i == (off + 1)%num_items);
160 bmap_test_assert(count == num_items + 1);
162 for (i = 0; i < num_items; i++)
168 TEST(BitAllocator, test_bmap_entry)
173 int64_t allocated = 0;
174 int size = BmapEntry::size();
176 BmapEntry *bmap = new BmapEntry(g_ceph_context, true);
178 // Clear bits one by one and check they are cleared
179 for (i = 0; i < size; i++) {
181 bmap_test_assert(!bmap->check_bit(i));
184 // Set all bits again using set_bits
185 bmap->set_bits(0, size);
187 // clear 4 bits at a time and then check allocated
188 for (i = 0; i < size/4; i++) {
189 bmap->clear_bits(i * 4, 4);
190 bmap_test_assert(!bmap->is_allocated(i * 4, 4));
193 // set all bits again
194 bmap->set_bits(0, size);
196 // clear alternate bits, check and set those bits
197 for (i = 0; i < size/2; i++) {
198 bmap->clear_bit(i * 2 + 1);
199 bmap_test_assert(!bmap->check_bit(i * 2 + 1));
200 bmap_test_assert(bmap->check_n_set_bit(i * 2 + 1));
203 // free 1, 2 and size bits at a time and try to find n cont bits
204 for (i = 0; i < size / 4; i++) {
205 bmap->clear_bits(i * 2 + 1, i + 1);
206 bmap_test_assert(!bmap->check_bit(i * 2 + 1));
207 bmap_test_assert(bmap->find_n_cont_bits(i * 2 + 1, i + 1) ==
211 // free 1, 2 and size bits at a time and try to find any cont bits
212 for (i = 0; i < size / 4; i++) {
213 bmap->clear_bits(i * 2 + 1, i + 1);
214 bmap_test_assert(!bmap->is_allocated(i * 2 + 1, i + 1));
217 for (i = 0; i < size / 4; i++) {
218 bmap->clear_bits(i * 2 + 1, i + 1);
219 allocated = bmap->find_first_set_bits(i + 1, 0, &start, &scanned);
221 bmap_test_assert(allocated == i + 1);
222 bmap_test_assert(scanned == ((i * 2 + 1) + (i + 1)));
223 bmap_test_assert(start == i * 2 + 1);
224 bmap->set_bits(0, BmapEntry::size());
230 // Find few bits at end of bitmap and find those
231 bmap->clear_bits(0, 4);
232 bmap->clear_bits(BmapEntry::size() - 12, 5);
233 bmap->clear_bits(BmapEntry::size() - 6, 6);
234 allocated = bmap->find_first_set_bits(6, 0, &start, &scanned);
236 bmap_test_assert(allocated == 6);
237 bmap_test_assert(scanned == BmapEntry::size() - 6 + 6);
238 bmap_test_assert(start == BmapEntry::size() - 6);
239 bmap_test_assert(bmap->is_allocated(start, 6));
245 bmap = new BmapEntry(g_ceph_context, false);
249 allocated = bmap->find_first_set_bits(1, 1, &start, &scanned);
250 bmap_test_assert(allocated == 1);
251 bmap_test_assert(start == 1);
253 allocated = bmap->find_first_set_bits(1, BmapEntry::size() - 2, &start, &scanned);
254 bmap_test_assert(allocated == 1);
255 bmap_test_assert(start == BmapEntry::size() - 2);
257 bmap->clear_bits(0, BmapEntry::size());
258 bmap->set_bits(0, BmapEntry::size() / 4);
259 allocated = bmap->find_first_set_bits(4, 2, &start, &scanned);
260 bmap_test_assert(allocated == 4);
261 bmap_test_assert(start == BmapEntry::size() / 4);
265 bmap = new BmapEntry(g_ceph_context, false);
266 bmap->set_bits(4, BmapEntry::size() - 4);
267 bmap_test_assert(bmap->is_allocated(4, BmapEntry::size() - 4));
268 bmap_test_assert(!bmap->is_allocated(0, 4));
269 bmap->set_bits(0, 4);
270 bmap_test_assert(bmap->is_allocated(0, BmapEntry::size()));
275 TEST(BitAllocator, test_zone_alloc)
277 int total_blocks = 1024;
278 int64_t allocated = 0;
280 BitMapZone *zone = new BitMapZone(g_ceph_context, total_blocks, 0);
282 // Allocate all blocks and see that it is allocating in order.
283 bool lock = zone->lock_excl_try();
284 bmap_test_assert(lock);
286 int64_t blk_size = 1024;
287 AllocExtentVector extents;
288 ExtentList *block_list = new ExtentList(&extents, blk_size);
289 allocated = zone->alloc_blocks_dis(zone->size() / 2, 1, 0, 0, block_list);
290 bmap_test_assert(allocated == zone->size() / 2);
294 int64_t blk_size = 1024;
295 AllocExtentVector extents;
296 ExtentList *block_list = new ExtentList(&extents, blk_size);
298 zone = new BitMapZone(g_ceph_context, total_blocks, 0);
299 lock = zone->lock_excl_try();
300 bmap_test_assert(lock);
301 for (int i = 0; i < zone->size(); i += 4) {
303 allocated = zone->alloc_blocks_dis(1, 1, i, 0, block_list);
304 bmap_test_assert(allocated == 1);
305 EXPECT_EQ(extents[0].offset, (uint64_t) i * blk_size);
308 for (int i = 0; i < zone->size(); i += 4) {
309 zone->free_blocks(i, 1);
314 * Min alloc size cases.
317 int64_t blk_size = 1;
318 AllocExtentVector extents;
320 for (int i = 1; i <= total_blocks - BmapEntry::size(); i = i << 1) {
321 for (int64_t j = 0; j <= BmapEntry::size(); j = 1 << j) {
323 ExtentList *block_list = new ExtentList(&extents, blk_size);
324 zone = new BitMapZone(g_ceph_context, total_blocks, 0);
325 lock = zone->lock_excl_try();
326 bmap_test_assert(lock);
329 int64_t need_blks = (((total_blocks - j) / i) * i);
330 allocated = zone->alloc_blocks_dis(need_blks, i, j, 0, block_list);
331 bmap_test_assert(allocated == need_blks);
332 bmap_test_assert(extents[0].offset == (uint64_t) j);
341 ExtentList *block_list = new ExtentList(&extents, blk_size);
342 zone = new BitMapZone(g_ceph_context, total_blocks, 0);
343 lock = zone->lock_excl_try();
345 for (int iter = 1; iter < 5; iter++) {
346 for (int i = 1; i <= total_blocks; i = i << 1) {
347 for (int j = 0; j < total_blocks; j +=i) {
348 bmap_test_assert(lock);
350 int64_t need_blks = i;
351 allocated = zone->alloc_blocks_dis(need_blks, i, 0, 0, block_list);
352 bmap_test_assert(allocated == need_blks);
353 bmap_test_assert(extents[0].offset == (uint64_t) j);
357 allocated = zone->alloc_blocks_dis(1, 1, 0, 0, block_list);
358 bmap_test_assert(allocated == 0);
362 for (int j = 0; j < total_blocks; j +=i) {
363 zone->free_blocks(j, i);
373 ExtentList *block_list = new ExtentList(&extents, blk_size);
374 zone = new BitMapZone(g_ceph_context, total_blocks, 0);
375 lock = zone->lock_excl_try();
376 bmap_test_assert(lock);
379 allocated = zone->alloc_blocks_dis(total_blocks + 1, total_blocks + 1, 0, 1024, block_list);
380 bmap_test_assert(allocated == 0);
383 allocated = zone->alloc_blocks_dis(total_blocks, total_blocks, 1, 1024, block_list);
384 bmap_test_assert(allocated == 0);
387 allocated = zone->alloc_blocks_dis(total_blocks, total_blocks, 0, 0, block_list);
388 bmap_test_assert(allocated == total_blocks);
389 bmap_test_assert(extents[0].offset == 0);
391 zone->free_blocks(extents[0].offset, allocated);
395 block_list = new ExtentList(&extents, blk_size, total_blocks / 4 * blk_size);
396 allocated = zone->alloc_blocks_dis(total_blocks, total_blocks / 4, 0, 0, block_list);
397 bmap_test_assert(allocated == total_blocks);
398 for (int i = 0; i < 4; i++) {
399 bmap_test_assert(extents[i].offset == (uint64_t) i * (total_blocks / 4));
405 TEST(BitAllocator, test_bmap_alloc)
407 const int max_iter = 3;
409 for (int round = 0; round < 3; round++) {
410 // Test zone of different sizes: 512, 1024, 2048
411 int64_t zone_size = 512ull << round;
414 g_conf->set_val("bluestore_bitmapallocator_blocks_per_zone", val.str());
416 // choose randomized span_size
417 int64_t span_size = 512ull << (rand() % 4);
420 g_conf->set_val("bluestore_bitmapallocator_span_size", val.str());
421 g_ceph_context->_conf->apply_changes(NULL);
423 int64_t total_blocks = zone_size * 4;
424 int64_t allocated = 0;
426 BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks,
427 zone_size, CONCURRENT);
428 int64_t alloc_size = 2;
429 for (int64_t iter = 0; iter < max_iter; iter++) {
430 for (int64_t j = 0; alloc_size <= total_blocks; j++) {
431 int64_t blk_size = 1024;
432 AllocExtentVector extents;
433 ExtentList *block_list = new ExtentList(&extents, blk_size, alloc_size);
434 for (int64_t i = 0; i < total_blocks; i += alloc_size) {
435 bmap_test_assert(alloc->reserve_blocks(alloc_size) == true);
436 allocated = alloc->alloc_blocks_dis_res(alloc_size, MIN(alloc_size, zone_size),
438 bmap_test_assert(alloc_size == allocated);
439 bmap_test_assert(block_list->get_extent_count() ==
440 (alloc_size > zone_size? alloc_size / zone_size: 1));
441 bmap_test_assert(extents[0].offset == (uint64_t) i * blk_size);
442 bmap_test_assert((int64_t) extents[0].length ==
443 ((alloc_size > zone_size? zone_size: alloc_size) * blk_size));
446 for (int64_t i = 0; i < total_blocks; i += alloc_size) {
447 alloc->free_blocks(i, alloc_size);
453 int64_t blk_size = 1024;
454 AllocExtentVector extents;
456 ExtentList *block_list = new ExtentList(&extents, blk_size);
458 ASSERT_EQ(alloc->reserve_blocks(alloc->size() / 2), true);
459 allocated = alloc->alloc_blocks_dis_res(alloc->size()/2, 1, 0, block_list);
460 ASSERT_EQ(alloc->size()/2, allocated);
463 ASSERT_EQ(alloc->reserve_blocks(1), true);
464 allocated = alloc->alloc_blocks_dis_res(1, 1, 0, block_list);
465 bmap_test_assert(allocated == 1);
467 alloc->free_blocks(alloc->size()/2, 1);
470 ASSERT_EQ(alloc->reserve_blocks(1), true);
471 allocated = alloc->alloc_blocks_dis_res(1, 1, 0, block_list);
472 bmap_test_assert(allocated == 1);
474 bmap_test_assert((int64_t) extents[0].offset == alloc->size()/2 * blk_size);
481 // restore to typical value
482 g_conf->set_val("bluestore_bitmapallocator_blocks_per_zone", "1024");
483 g_conf->set_val("bluestore_bitmapallocator_span_size", "1024");
484 g_ceph_context->_conf->apply_changes(NULL);
487 bool alloc_extents_max_block(BitAllocator *alloc,
491 int64_t blk_size = 1;
492 int64_t allocated = 0;
493 int64_t verified = 0;
495 AllocExtentVector extents;
497 ExtentList *block_list = new ExtentList(&extents, blk_size, max_alloc);
499 EXPECT_EQ(alloc->reserve_blocks(total_alloc), true);
500 allocated = alloc->alloc_blocks_dis_res(total_alloc, blk_size, 0, block_list);
501 EXPECT_EQ(allocated, total_alloc);
503 max_alloc = total_alloc > max_alloc? max_alloc: total_alloc;
505 for (auto &p: extents) {
507 EXPECT_EQ(p.length, max_alloc);
508 verified += p.length;
509 if (verified >= total_alloc) {
514 EXPECT_EQ(total_alloc / max_alloc, count);
518 TEST(BitAllocator, test_bmap_alloc2)
520 int64_t total_blocks = 1024 * 4;
521 int64_t zone_size = 1024;
522 BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks,
523 zone_size, CONCURRENT);
525 alloc_extents_max_block(alloc, 1, 16);
526 alloc_extents_max_block(alloc, 4, 16);
527 alloc_extents_max_block(alloc, 16, 16);
528 alloc_extents_max_block(alloc, 32, 16);
534 do_work_dis(BitAllocator *alloc)
538 int64_t num_blocks = alloc->size() / NUM_THREADS;
540 AllocExtentVector extents;
541 ExtentList *block_list = new ExtentList(&extents, 4096);
543 while (num_iters--) {
544 alloc_assert(alloc->reserve_blocks(num_blocks));
545 alloced = alloc->alloc_blocks_dis_res(num_blocks, 1, 0, block_list);
546 alloc_assert(alloced == num_blocks);
548 alloc_assert(alloc->is_allocated_dis(block_list, num_blocks));
549 alloc->free_blocks_dis(num_blocks, block_list);
555 static bool cont = true;
560 my_tid = __sync_fetch_and_add(&tid, 1);
561 BitAllocator *alloc = (BitAllocator *) args;
562 printf("Starting thread %d", my_tid);
568 TEST(BitAllocator, test_bmap_alloc_concurrent)
570 int64_t total_blocks = MAX_BLOCKS;
571 int64_t zone_size = 1024;
572 pthread_t pthreads[NUM_THREADS] = {0};
574 bmap_test_assert(total_blocks <= MAX_BLOCKS);
576 BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks,
577 zone_size, CONCURRENT);
579 for (int k = 0; k < 2; k++) {
581 printf("Spawning %d threads for parallel test. Mode Cont = %d.....\n", NUM_THREADS, cont);
582 for (int j = 0; j < NUM_THREADS; j++) {
583 if (pthread_create(&pthreads[j], NULL, worker, alloc)) {
584 printf("Unable to create worker thread.\n");
589 for (int j = 0; j < NUM_THREADS; j++) {
590 pthread_join(pthreads[j], NULL);