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 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 ✗ 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 8487504 uint64_t Alloc(size_t data_size) override {
37
1/2
✓ Branch 1 taken 8487504 times.
✗ Branch 2 not taken.
 8487504 std::lock_guard<std::mutex> lock(mu_);
38
2/2
✓ Branch 1 taken 8487502 times.
✓ Branch 2 taken 2 times.
 8487504 const int level = LevelFor(data_size);
39
1/2
✓ Branch 1 taken 8487502 times.
✗ Branch 2 not taken.
 16975004 return AllocAtLevel(level);
40 8487504 }
41
42 41982 void Free(uint64_t block_addr) override {
43
2/4
✓ Branch 0 taken 41982 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 41982 times.
 41982 if (block_addr == kInvalidHandle || block_addr == 0) {
44 ✗ return;
45 }
46 41982 uint32_t data_size = 0;
47 41982 uint32_t level = 0;
48
1/2
✓ Branch 1 taken 41982 times.
✗ Branch 2 not taken.
 41982 ReadHeader(block_addr, data_size, level);
49
1/2
✓ Branch 1 taken 41982 times.
✗ Branch 2 not taken.
 41982 std::lock_guard<std::mutex> lock(mu_);
50
1/2
✓ Branch 1 taken 41982 times.
✗ Branch 2 not taken.
 41982 FreeAtLevel(block_addr, static_cast<int>(level));
51 41982 }
52
53 98800 void Write(uint64_t block_addr, const void* data, size_t data_size) override {
54 98800 const int level = LevelFor(data_size);
55 98800 WriteWithLevel(block_addr, level, data, data_size);
56 98800 }
57
58 73720 size_t Read(uint64_t block_addr, void* out_buf, size_t buf_size) override {
59
1/2
✓ Branch 1 taken 73720 times.
✗ Branch 2 not taken.
 73720 std::lock_guard<std::mutex> lock(io_mu_);
60 73720 uint32_t data_size = 0;
61 73720 uint32_t level = 0;
62
1/2
✓ Branch 1 taken 73720 times.
✗ Branch 2 not taken.
 73720 ReadHeaderUnlocked(block_addr, data_size, level);
63 73720 const uint64_t block_size = static_cast<uint64_t>(min_block_size_) << level;
64 73720 const PageID_t start = BlockByteOffset(block_addr) / PAGE_SIZE;
65 73720 const uint64_t page_off = BlockByteOffset(block_addr) % PAGE_SIZE;
66 73720 const uint64_t pages = (page_off + block_size + PAGE_SIZE - 1) / PAGE_SIZE;
67
1/2
✓ Branch 1 taken 73720 times.
✗ Branch 2 not taken.
 73720 char* buf = backend_->AllocateBuffer(pages);
68
2/4
✓ Branch 2 taken 73720 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 73720 times.
✗ Branch 6 not taken.
 73720 backend_->BatchReadPages({{start, buf, pages}});
69 73720 const size_t actual = std::min(buf_size, static_cast<size_t>(data_size));
70 73720 std::memcpy(out_buf, buf + page_off + kHeaderSize, actual);
71
1/2
✓ Branch 1 taken 73720 times.
✗ Branch 2 not taken.
 73720 backend_->FreeBuffer(buf);
72 73720 return actual;
73 73720 }
74
75 98800 uint64_t AllocAndWrite(const void* data, size_t data_size) override {
76 98800 const uint64_t handle = Alloc(data_size);
77
1/2
✓ Branch 0 taken 98800 times.
✗ Branch 1 not taken.
 98800 if (handle != kInvalidHandle) {
78 98800 Write(handle, data, data_size);
79 }
80 98800 return handle;
81 }
82
83 95226 size_t SlotCapacity(uint64_t block_addr) const override {
84
2/4
✓ Branch 0 taken 95226 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 95226 times.
 95226 if (block_addr == 0 || block_addr == kInvalidHandle) {
85 ✗ return 0;
86 }
87
1/2
✓ Branch 1 taken 95226 times.
✗ Branch 2 not taken.
 95226 std::lock_guard<std::mutex> lock(io_mu_);
88 95226 uint32_t data_size = 0;
89 95226 uint32_t level = 0;
90
1/2
✓ Branch 1 taken 95226 times.
✗ Branch 2 not taken.
 95226 const_cast<SsdBuddyAllocator*>(this)->ReadHeaderUnlocked(
91 block_addr, data_size, level);
92 95226 return (static_cast<uint64_t>(min_block_size_) << level) - kHeaderSize;
93 95226 }
94
95 static constexpr int kHeaderSize = 8;
96
97 private:
98 8586304 int LevelFor(size_t data_size) const {
99 8586304 const uint64_t needed = static_cast<uint64_t>(data_size) + kHeaderSize;
100
2/2
✓ Branch 0 taken 17172194 times.
✓ Branch 1 taken 2 times.
 17172196 for (int level = 0; level < num_levels_; ++level) {
101
2/2
✓ Branch 0 taken 8586302 times.
✓ Branch 1 taken 8585892 times.
 17172194 if ((static_cast<uint64_t>(min_block_size_) << level) >= needed) {
102 8586302 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 8487502 uint64_t AllocAtLevel(int level) {
109
2/2
✓ Branch 0 taken 16410130 times.
✓ Branch 1 taken 6 times.
 16410136 for (int cur = level; cur < num_levels_; ++cur) {
110
2/2
✓ Branch 2 taken 7922634 times.
✓ Branch 3 taken 8487496 times.
 16410130 if (free_lists_[cur].empty()) {
111 7922634 continue;
112 }
113 8487496 uint64_t block = *free_lists_[cur].begin();
114
1/2
✓ Branch 2 taken 8487496 times.
✗ Branch 3 not taken.
 8487496 free_lists_[cur].erase(block);
115
2/2
✓ Branch 0 taken 7922612 times.
✓ Branch 1 taken 8487496 times.
 16410108 while (cur > level) {
116 7922612 --cur;
117 7922612 const uint64_t buddy = block + (uint64_t{1} << cur);
118
1/2
✓ Branch 2 taken 7922612 times.
✗ Branch 3 not taken.
 7922612 free_lists_[cur].insert(buddy);
119 }
120 8487496 return block;
121 }
122 6 return kInvalidHandle;
123 }
124
125 41982 void FreeAtLevel(uint64_t block, int level) {
126
1/2
✓ Branch 0 taken 42098 times.
✗ Branch 1 not taken.
 42098 while (level + 1 < num_levels_) {
127 42098 const uint64_t buddy = block ^ (uint64_t{1} << level);
128
1/2
✓ Branch 2 taken 42098 times.
✗ Branch 3 not taken.
 42098 auto it = free_lists_[level].find(buddy);
129
2/2
✓ Branch 3 taken 41982 times.
✓ Branch 4 taken 116 times.
 42098 if (it == free_lists_[level].end()) {
130 41982 break;
131 }
132
1/2
✓ Branch 2 taken 116 times.
✗ Branch 3 not taken.
 116 free_lists_[level].erase(it);
133 116 block = std::min(block, buddy);
134 116 ++level;
135 }
136 41982 free_lists_[level].insert(block);
137 41982 }
138
139 457168 uint64_t BlockByteOffset(uint64_t block_addr) const {
140 457168 return base_byte_offset_ + block_addr * min_block_size_;
141 }
142
143 98800 void WriteWithLevel(
144 uint64_t block_addr, int level, const void* data, size_t data_size) {
145
1/2
✓ Branch 1 taken 98800 times.
✗ Branch 2 not taken.
 98800 std::lock_guard<std::mutex> lock(io_mu_);
146 98800 const uint64_t block_size = static_cast<uint64_t>(min_block_size_) << level;
147 98800 const uint64_t byte_offset = BlockByteOffset(block_addr);
148 98800 const PageID_t start = byte_offset / PAGE_SIZE;
149 98800 const uint64_t page_off = byte_offset % PAGE_SIZE;
150 98800 const uint64_t pages = (page_off + block_size + PAGE_SIZE - 1) / PAGE_SIZE;
151
1/2
✓ Branch 1 taken 98800 times.
✗ Branch 2 not taken.
 98800 char* buf = backend_->AllocateBuffer(pages);
152
2/4
✓ Branch 2 taken 98800 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 98800 times.
✗ Branch 6 not taken.
 98800 backend_->BatchReadPages({{start, buf, pages}});
153 98800 const uint32_t n = static_cast<uint32_t>(data_size);
154 98800 const uint32_t l = static_cast<uint32_t>(level);
155 98800 std::memcpy(buf + page_off, &n, sizeof(n));
156 98800 std::memcpy(buf + page_off + sizeof(n), &l, sizeof(l));
157 98800 std::memcpy(buf + page_off + kHeaderSize, data, data_size);
158
2/4
✓ Branch 2 taken 98800 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 98800 times.
✗ Branch 6 not taken.
 98800 backend_->BatchWritePages({{start, buf, pages}});
159
1/2
✓ Branch 1 taken 98800 times.
✗ Branch 2 not taken.
 98800 backend_->FreeBuffer(buf);
160 98800 }
161
162 41982 void ReadHeader(uint64_t block_addr, uint32_t& data_size, uint32_t& level) {
163
1/2
✓ Branch 1 taken 41982 times.
✗ Branch 2 not taken.
 41982 std::lock_guard<std::mutex> lock(io_mu_);
164
1/2
✓ Branch 1 taken 41982 times.
✗ Branch 2 not taken.
 41982 ReadHeaderUnlocked(block_addr, data_size, level);
165 41982 }
166
167 210928 void ReadHeaderUnlocked(
168 uint64_t block_addr, uint32_t& data_size, uint32_t& level) {
169 210928 const uint64_t byte_offset = BlockByteOffset(block_addr);
170 210928 const PageID_t start = byte_offset / PAGE_SIZE;
171 210928 const uint64_t page_off = byte_offset % PAGE_SIZE;
172 210928 char* buf = backend_->AllocateBuffer();
173 210928 backend_->ReadPage(start, buf);
174 210928 std::memcpy(&data_size, buf + page_off, sizeof(data_size));
175 210928 std::memcpy(&level, buf + page_off + sizeof(data_size), sizeof(level));
176 210928 backend_->FreeBuffer(buf);
177 210928 }
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