GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 97.6% 121 / 0 / 124
Functions: 100.0% 14 / 0 / 14
Branches: 57.4% 54 / 0 / 94
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 642 SsdBuddyAllocator(IOBackend* backend,
16 int min_block_size,
17 int num_levels,
18 uint64_t capacity_bytes,
19 uint64_t base_byte_offset)
20 1284 : backend_(backend),
21 642 min_block_size_(min_block_size),
22 642 num_levels_(num_levels),
23 642 total_min_blocks_(capacity_bytes / min_block_size),
24 642 base_byte_offset_(base_byte_offset) {
25
3/6
✓ Branch 0 taken 642 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 642 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 642 times.
 642 if (backend_ == nullptr || min_block_size_ <= 0 || num_levels_ <= 0) {
26 ✗ throw std::invalid_argument("invalid SsdBuddyAllocator config");
27 }
28
1/2
✓ Branch 1 taken 642 times.
✗ Branch 2 not taken.
 642 free_lists_.resize(num_levels_);
29 642 const uint64_t max_block_min_units = uint64_t{1} << (num_levels_ - 1);
30
2/2
✓ Branch 0 taken 1758606 times.
✓ Branch 1 taken 642 times.
 1759248 for (uint64_t block = 1; block + max_block_min_units <= total_min_blocks_;
31 1758606 block += max_block_min_units) {
32
1/2
✓ Branch 2 taken 1758606 times.
✗ Branch 3 not taken.
 1758606 free_lists_.back().insert(block);
33 }
34 642 }
35
36 8487342 uint64_t Alloc(size_t data_size) override {
37
1/2
✓ Branch 1 taken 8487342 times.
✗ Branch 2 not taken.
 8487342 std::lock_guard<std::mutex> lock(mu_);
38
2/2
✓ Branch 1 taken 8487340 times.
✓ Branch 2 taken 2 times.
 8487342 const int level = LevelFor(data_size);
39
1/2
✓ Branch 1 taken 8487340 times.
✗ Branch 2 not taken.
 16974680 return AllocAtLevel(level);
40 8487342 }
41
42 41834 void Free(uint64_t block_addr) override {
43
2/4
✓ Branch 0 taken 41834 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 41834 times.
 41834 if (block_addr == kInvalidHandle || block_addr == 0) {
44 ✗ return;
45 }
46 41834 uint32_t data_size = 0;
47 41834 uint32_t level = 0;
48
1/2
✓ Branch 1 taken 41834 times.
✗ Branch 2 not taken.
 41834 ReadHeader(block_addr, data_size, level);
49
1/2
✓ Branch 1 taken 41834 times.
✗ Branch 2 not taken.
 41834 std::lock_guard<std::mutex> lock(mu_);
50
1/2
✓ Branch 1 taken 41834 times.
✗ Branch 2 not taken.
 41834 FreeAtLevel(block_addr, static_cast<int>(level));
51 41834 }
52
53 98638 void Write(uint64_t block_addr, const void* data, size_t data_size) override {
54 98638 const int level = LevelFor(data_size);
55 98638 WriteWithLevel(block_addr, level, data, data_size);
56 98638 }
57
58 73936 size_t Read(uint64_t block_addr, void* out_buf, size_t buf_size) override {
59
1/2
✓ Branch 1 taken 73936 times.
✗ Branch 2 not taken.
 73936 std::lock_guard<std::mutex> lock(io_mu_);
60 73936 uint32_t data_size = 0;
61 73936 uint32_t level = 0;
62
1/2
✓ Branch 1 taken 73936 times.
✗ Branch 2 not taken.
 73936 ReadHeaderUnlocked(block_addr, data_size, level);
63 73936 const uint64_t block_size = static_cast<uint64_t>(min_block_size_) << level;
64 73936 const PageID_t start = BlockByteOffset(block_addr) / PAGE_SIZE;
65 73936 const uint64_t page_off = BlockByteOffset(block_addr) % PAGE_SIZE;
66 73936 const uint64_t pages = (page_off + block_size + PAGE_SIZE - 1) / PAGE_SIZE;
67
1/2
✓ Branch 1 taken 73936 times.
✗ Branch 2 not taken.
 73936 char* buf = backend_->AllocateBuffer(pages);
68
2/4
✓ Branch 2 taken 73936 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 73936 times.
✗ Branch 6 not taken.
 73936 backend_->BatchReadPages({{start, buf, pages}});
69 73936 const size_t actual = std::min(buf_size, static_cast<size_t>(data_size));
70 73936 std::memcpy(out_buf, buf + page_off + kHeaderSize, actual);
71
1/2
✓ Branch 1 taken 73936 times.
✗ Branch 2 not taken.
 73936 backend_->FreeBuffer(buf);
72 73936 return actual;
73 73936 }
74
75 98638 uint64_t AllocAndWrite(const void* data, size_t data_size) override {
76 98638 const uint64_t handle = Alloc(data_size);
77
1/2
✓ Branch 0 taken 98638 times.
✗ Branch 1 not taken.
 98638 if (handle != kInvalidHandle) {
78 98638 Write(handle, data, data_size);
79 }
80 98638 return handle;
81 }
82
83 95442 size_t SlotCapacity(uint64_t block_addr) const override {
84
2/4
✓ Branch 0 taken 95442 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 95442 times.
 95442 if (block_addr == 0 || block_addr == kInvalidHandle) {
85 ✗ return 0;
86 }
87
1/2
✓ Branch 1 taken 95442 times.
✗ Branch 2 not taken.
 95442 std::lock_guard<std::mutex> lock(io_mu_);
88 95442 uint32_t data_size = 0;
89 95442 uint32_t level = 0;
90
1/2
✓ Branch 1 taken 95442 times.
✗ Branch 2 not taken.
 95442 const_cast<SsdBuddyAllocator*>(this)->ReadHeaderUnlocked(
91 block_addr, data_size, level);
92 95442 return (static_cast<uint64_t>(min_block_size_) << level) - kHeaderSize;
93 95442 }
94
95 static constexpr int kHeaderSize = 8;
96
97 private:
98 8585980 int LevelFor(size_t data_size) const {
99 8585980 const uint64_t needed = static_cast<uint64_t>(data_size) + kHeaderSize;
100
2/2
✓ Branch 0 taken 17171546 times.
✓ Branch 1 taken 2 times.
 17171548 for (int level = 0; level < num_levels_; ++level) {
101
2/2
✓ Branch 0 taken 8585978 times.
✓ Branch 1 taken 8585568 times.
 17171546 if ((static_cast<uint64_t>(min_block_size_) << level) >= needed) {
102 8585978 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 8487340 uint64_t AllocAtLevel(int level) {
109
2/2
✓ Branch 0 taken 16409958 times.
✓ Branch 1 taken 6 times.
 16409964 for (int cur = level; cur < num_levels_; ++cur) {
110
2/2
✓ Branch 2 taken 7922624 times.
✓ Branch 3 taken 8487334 times.
 16409958 if (free_lists_[cur].empty()) {
111 7922624 continue;
112 }
113 8487334 uint64_t block = *free_lists_[cur].begin();
114
1/2
✓ Branch 2 taken 8487334 times.
✗ Branch 3 not taken.
 8487334 free_lists_[cur].erase(block);
115
2/2
✓ Branch 0 taken 7922602 times.
✓ Branch 1 taken 8487334 times.
 16409936 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 8487334 return block;
121 }
122 6 return kInvalidHandle;
123 }
124
125 41834 void FreeAtLevel(uint64_t block, int level) {
126
1/2
✓ Branch 0 taken 41954 times.
✗ Branch 1 not taken.
 41954 while (level + 1 < num_levels_) {
127 41954 const uint64_t buddy = block ^ (uint64_t{1} << level);
128
1/2
✓ Branch 2 taken 41954 times.
✗ Branch 3 not taken.
 41954 auto it = free_lists_[level].find(buddy);
129
2/2
✓ Branch 3 taken 41834 times.
✓ Branch 4 taken 120 times.
 41954 if (it == free_lists_[level].end()) {
130 41834 break;
131 }
132
1/2
✓ Branch 2 taken 120 times.
✗ Branch 3 not taken.
 120 free_lists_[level].erase(it);
133 120 block = std::min(block, buddy);
134 120 ++level;
135 }
136 41834 free_lists_[level].insert(block);
137 41834 }
138
139 457722 uint64_t BlockByteOffset(uint64_t block_addr) const {
140 457722 return base_byte_offset_ + block_addr * min_block_size_;
141 }
142
143 98638 void WriteWithLevel(
144 uint64_t block_addr, int level, const void* data, size_t data_size) {
145
1/2
✓ Branch 1 taken 98638 times.
✗ Branch 2 not taken.
 98638 std::lock_guard<std::mutex> lock(io_mu_);
146 98638 const uint64_t block_size = static_cast<uint64_t>(min_block_size_) << level;
147 98638 const uint64_t byte_offset = BlockByteOffset(block_addr);
148 98638 const PageID_t start = byte_offset / PAGE_SIZE;
149 98638 const uint64_t page_off = byte_offset % PAGE_SIZE;
150 98638 const uint64_t pages = (page_off + block_size + PAGE_SIZE - 1) / PAGE_SIZE;
151
1/2
✓ Branch 1 taken 98638 times.
✗ Branch 2 not taken.
 98638 char* buf = backend_->AllocateBuffer(pages);
152
2/4
✓ Branch 2 taken 98638 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 98638 times.
✗ Branch 6 not taken.
 98638 backend_->BatchReadPages({{start, buf, pages}});
153 98638 const uint32_t n = static_cast<uint32_t>(data_size);
154 98638 const uint32_t l = static_cast<uint32_t>(level);
155 98638 std::memcpy(buf + page_off, &n, sizeof(n));
156 98638 std::memcpy(buf + page_off + sizeof(n), &l, sizeof(l));
157 98638 std::memcpy(buf + page_off + kHeaderSize, data, data_size);
158
2/4
✓ Branch 2 taken 98638 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 98638 times.
✗ Branch 6 not taken.
 98638 backend_->BatchWritePages({{start, buf, pages}});
159
1/2
✓ Branch 1 taken 98638 times.
✗ Branch 2 not taken.
 98638 backend_->FreeBuffer(buf);
160 98638 }
161
162 41834 void ReadHeader(uint64_t block_addr, uint32_t& data_size, uint32_t& level) {
163
1/2
✓ Branch 1 taken 41834 times.
✗ Branch 2 not taken.
 41834 std::lock_guard<std::mutex> lock(io_mu_);
164
1/2
✓ Branch 1 taken 41834 times.
✗ Branch 2 not taken.
 41834 ReadHeaderUnlocked(block_addr, data_size, level);
165 41834 }
166
167 211212 void ReadHeaderUnlocked(
168 uint64_t block_addr, uint32_t& data_size, uint32_t& level) {
169 211212 const uint64_t byte_offset = BlockByteOffset(block_addr);
170 211212 const PageID_t start = byte_offset / PAGE_SIZE;
171 211212 const uint64_t page_off = byte_offset % PAGE_SIZE;
172 211212 char* buf = backend_->AllocateBuffer();
173 211212 backend_->ReadPage(start, buf);
174 211212 std::memcpy(&data_size, buf + page_off, sizeof(data_size));
175 211212 std::memcpy(&level, buf + page_off + sizeof(data_size), sizeof(level));
176 211212 backend_->FreeBuffer(buf);
177 211212 }
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