GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
121 / 124
97.6%
Branches:
54 / 94
57.4%
Functions:
14 / 14
100.0%
storage/allocator/ssd/ssd_buddy_allocator.h
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cstring>
5 #include <mutex>
6 #include <stdexcept>
7 #include <unordered_set>
8 #include <vector>
9
10 #include "storage/allocator/ssd/ssd_block_allocator.h"
11 #include "storage/io_backend/io_backend.h"
12
13 class SsdBuddyAllocator : public SsdBlockAllocator {
14 public:
15 678 SsdBuddyAllocator(IOBackend* backend,
16 int min_block_size,
17 int num_levels,
18 uint64_t capacity_bytes,
19 uint64_t base_byte_offset)
20 1356 : backend_(backend),
21 678 min_block_size_(min_block_size),
22 678 num_levels_(num_levels),
23 678 total_min_blocks_(capacity_bytes / min_block_size),
24 678 base_byte_offset_(base_byte_offset) {
25
3/6
✓ Branch 0 taken 678 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 678 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 678 times.
 678 if (backend_ == nullptr || min_block_size_ <= 0 || num_levels_ <= 0) {
26
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ throw std::invalid_argument("invalid SsdBuddyAllocator config");
27 }
28
1/2
✓ Branch 1 taken 678 times.
✗ Branch 2 not taken.
 678 free_lists_.resize(num_levels_);
29 678 const uint64_t max_block_min_units = uint64_t{1} << (num_levels_ - 1);
30
2/2
✓ Branch 0 taken 1828914 times.
✓ Branch 1 taken 678 times.
 1829592 for (uint64_t block = 1; block + max_block_min_units <= total_min_blocks_;
31 1828914 block += max_block_min_units) {
32
1/2
✓ Branch 2 taken 1828914 times.
✗ Branch 3 not taken.
 1828914 free_lists_.back().insert(block);
33 }
34 678 }
35
36 8487472 uint64_t Alloc(size_t data_size) override {
37
1/2
✓ Branch 1 taken 8487472 times.
✗ Branch 2 not taken.
 8487472 std::lock_guard<std::mutex> lock(mu_);
38
2/2
✓ Branch 1 taken 8487470 times.
✓ Branch 2 taken 2 times.
 8487472 const int level = LevelFor(data_size);
39
1/2
✓ Branch 1 taken 8487470 times.
✗ Branch 2 not taken.
 16974940 return AllocAtLevel(level);
40 8487472 }
41
42 41986 void Free(uint64_t block_addr) override {
43
2/4
✓ Branch 0 taken 41986 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 41986 times.
 41986 if (block_addr == kInvalidHandle || block_addr == 0) {
44 ✗ return;
45 }
46 41986 uint32_t data_size = 0;
47 41986 uint32_t level = 0;
48
1/2
✓ Branch 1 taken 41986 times.
✗ Branch 2 not taken.
 41986 ReadHeader(block_addr, data_size, level);
49
1/2
✓ Branch 1 taken 41986 times.
✗ Branch 2 not taken.
 41986 std::lock_guard<std::mutex> lock(mu_);
50
1/2
✓ Branch 1 taken 41986 times.
✗ Branch 2 not taken.
 41986 FreeAtLevel(block_addr, static_cast<int>(level));
51 41986 }
52
53 98768 void Write(uint64_t block_addr, const void* data, size_t data_size) override {
54 98768 const int level = LevelFor(data_size);
55 98768 WriteWithLevel(block_addr, level, data, data_size);
56 98768 }
57
58 73602 size_t Read(uint64_t block_addr, void* out_buf, size_t buf_size) override {
59
1/2
✓ Branch 1 taken 73602 times.
✗ Branch 2 not taken.
 73602 std::lock_guard<std::mutex> lock(io_mu_);
60 73602 uint32_t data_size = 0;
61 73602 uint32_t level = 0;
62
1/2
✓ Branch 1 taken 73602 times.
✗ Branch 2 not taken.
 73602 ReadHeaderUnlocked(block_addr, data_size, level);
63 73602 const uint64_t block_size = static_cast<uint64_t>(min_block_size_) << level;
64 73602 const PageID_t start = BlockByteOffset(block_addr) / PAGE_SIZE;
65 73602 const uint64_t page_off = BlockByteOffset(block_addr) % PAGE_SIZE;
66 73602 const uint64_t pages = (page_off + block_size + PAGE_SIZE - 1) / PAGE_SIZE;
67
1/2
✓ Branch 1 taken 73602 times.
✗ Branch 2 not taken.
 73602 char* buf = backend_->AllocateBuffer(pages);
68
2/4
✓ Branch 2 taken 73602 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 73602 times.
✗ Branch 6 not taken.
 73602 backend_->BatchReadPages({{start, buf, pages}});
69 73602 const size_t actual = std::min(buf_size, static_cast<size_t>(data_size));
70 73602 std::memcpy(out_buf, buf + page_off + kHeaderSize, actual);
71
1/2
✓ Branch 1 taken 73602 times.
✗ Branch 2 not taken.
 73602 backend_->FreeBuffer(buf);
72 73602 return actual;
73 73602 }
74
75 98768 uint64_t AllocAndWrite(const void* data, size_t data_size) override {
76 98768 const uint64_t handle = Alloc(data_size);
77
1/2
✓ Branch 0 taken 98768 times.
✗ Branch 1 not taken.
 98768 if (handle != kInvalidHandle) {
78 98768 Write(handle, data, data_size);
79 }
80 98768 return handle;
81 }
82
83 95216 size_t SlotCapacity(uint64_t block_addr) const override {
84
2/4
✓ Branch 0 taken 95216 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 95216 times.
 95216 if (block_addr == 0 || block_addr == kInvalidHandle) {
85 ✗ return 0;
86 }
87
1/2
✓ Branch 1 taken 95216 times.
✗ Branch 2 not taken.
 95216 std::lock_guard<std::mutex> lock(io_mu_);
88 95216 uint32_t data_size = 0;
89 95216 uint32_t level = 0;
90
1/2
✓ Branch 1 taken 95216 times.
✗ Branch 2 not taken.
 95216 const_cast<SsdBuddyAllocator*>(this)->ReadHeaderUnlocked(
91 block_addr, data_size, level);
92 95216 return (static_cast<uint64_t>(min_block_size_) << level) - kHeaderSize;
93 95216 }
94
95 static constexpr int kHeaderSize = 8;
96
97 private:
98 8586240 int LevelFor(size_t data_size) const {
99 8586240 const uint64_t needed = static_cast<uint64_t>(data_size) + kHeaderSize;
100
2/2
✓ Branch 0 taken 17172066 times.
✓ Branch 1 taken 2 times.
 17172068 for (int level = 0; level < num_levels_; ++level) {
101
2/2
✓ Branch 0 taken 8586238 times.
✓ Branch 1 taken 8585828 times.
 17172066 if ((static_cast<uint64_t>(min_block_size_) << level) >= needed) {
102 8586238 return level;
103 }
104 }
105
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 throw std::invalid_argument("SsdBuddyAllocator value too large");
106 }
107
108 8487470 uint64_t AllocAtLevel(int level) {
109
2/2
✓ Branch 0 taken 16410088 times.
✓ Branch 1 taken 6 times.
 16410094 for (int cur = level; cur < num_levels_; ++cur) {
110
2/2
✓ Branch 2 taken 7922624 times.
✓ Branch 3 taken 8487464 times.
 16410088 if (free_lists_[cur].empty()) {
111 7922624 continue;
112 }
113 8487464 uint64_t block = *free_lists_[cur].begin();
114
1/2
✓ Branch 2 taken 8487464 times.
✗ Branch 3 not taken.
 8487464 free_lists_[cur].erase(block);
115
2/2
✓ Branch 0 taken 7922602 times.
✓ Branch 1 taken 8487464 times.
 16410066 while (cur > level) {
116 7922602 --cur;
117 7922602 const uint64_t buddy = block + (uint64_t{1} << cur);
118
1/2
✓ Branch 2 taken 7922602 times.
✗ Branch 3 not taken.
 7922602 free_lists_[cur].insert(buddy);
119 }
120 8487464 return block;
121 }
122 6 return kInvalidHandle;
123 }
124
125 41986 void FreeAtLevel(uint64_t block, int level) {
126
1/2
✓ Branch 0 taken 42126 times.
✗ Branch 1 not taken.
 42126 while (level + 1 < num_levels_) {
127 42126 const uint64_t buddy = block ^ (uint64_t{1} << level);
128
1/2
✓ Branch 2 taken 42126 times.
✗ Branch 3 not taken.
 42126 auto it = free_lists_[level].find(buddy);
129
2/2
✓ Branch 3 taken 41986 times.
✓ Branch 4 taken 140 times.
 42126 if (it == free_lists_[level].end()) {
130 41986 break;
131 }
132
1/2
✓ Branch 2 taken 140 times.
✗ Branch 3 not taken.
 140 free_lists_[level].erase(it);
133 140 block = std::min(block, buddy);
134 140 ++level;
135 }
136 41986 free_lists_[level].insert(block);
137 41986 }
138
139 456776 uint64_t BlockByteOffset(uint64_t block_addr) const {
140 456776 return base_byte_offset_ + block_addr * min_block_size_;
141 }
142
143 98768 void WriteWithLevel(
144 uint64_t block_addr, int level, const void* data, size_t data_size) {
145
1/2
✓ Branch 1 taken 98768 times.
✗ Branch 2 not taken.
 98768 std::lock_guard<std::mutex> lock(io_mu_);
146 98768 const uint64_t block_size = static_cast<uint64_t>(min_block_size_) << level;
147 98768 const uint64_t byte_offset = BlockByteOffset(block_addr);
148 98768 const PageID_t start = byte_offset / PAGE_SIZE;
149 98768 const uint64_t page_off = byte_offset % PAGE_SIZE;
150 98768 const uint64_t pages = (page_off + block_size + PAGE_SIZE - 1) / PAGE_SIZE;
151
1/2
✓ Branch 1 taken 98768 times.
✗ Branch 2 not taken.
 98768 char* buf = backend_->AllocateBuffer(pages);
152
2/4
✓ Branch 2 taken 98768 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 98768 times.
✗ Branch 6 not taken.
 98768 backend_->BatchReadPages({{start, buf, pages}});
153 98768 const uint32_t n = static_cast<uint32_t>(data_size);
154 98768 const uint32_t l = static_cast<uint32_t>(level);
155 98768 std::memcpy(buf + page_off, &n, sizeof(n));
156 98768 std::memcpy(buf + page_off + sizeof(n), &l, sizeof(l));
157 98768 std::memcpy(buf + page_off + kHeaderSize, data, data_size);
158
2/4
✓ Branch 2 taken 98768 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 98768 times.
✗ Branch 6 not taken.
 98768 backend_->BatchWritePages({{start, buf, pages}});
159
1/2
✓ Branch 1 taken 98768 times.
✗ Branch 2 not taken.
 98768 backend_->FreeBuffer(buf);
160 98768 }
161
162 41986 void ReadHeader(uint64_t block_addr, uint32_t& data_size, uint32_t& level) {
163
1/2
✓ Branch 1 taken 41986 times.
✗ Branch 2 not taken.
 41986 std::lock_guard<std::mutex> lock(io_mu_);
164
1/2
✓ Branch 1 taken 41986 times.
✗ Branch 2 not taken.
 41986 ReadHeaderUnlocked(block_addr, data_size, level);
165 41986 }
166
167 210804 void ReadHeaderUnlocked(
168 uint64_t block_addr, uint32_t& data_size, uint32_t& level) {
169 210804 const uint64_t byte_offset = BlockByteOffset(block_addr);
170 210804 const PageID_t start = byte_offset / PAGE_SIZE;
171 210804 const uint64_t page_off = byte_offset % PAGE_SIZE;
172 210804 char* buf = backend_->AllocateBuffer();
173 210804 backend_->ReadPage(start, buf);
174 210804 std::memcpy(&data_size, buf + page_off, sizeof(data_size));
175 210804 std::memcpy(&level, buf + page_off + sizeof(data_size), sizeof(level));
176 210804 backend_->FreeBuffer(buf);
177 210804 }
178
179 IOBackend* backend_;
180 const int min_block_size_;
181 const int num_levels_;
182 const uint64_t total_min_blocks_;
183 const uint64_t base_byte_offset_;
184 std::mutex mu_;
185 mutable std::mutex io_mu_;
186 std::vector<std::unordered_set<uint64_t>> free_lists_;
187 };
188
189 FACTORY_REGISTER(
190 SsdBlockAllocator,
191 SSD_BUDDY,
192 SsdBuddyAllocator,
193 IOBackend*,
194 int,
195 int,
196 uint64_t,
197 uint64_t);
198