GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/kvstore.cc
Date: 2026-04-05 02:35:23
Exec Total Coverage
Lines: 193 249 77.5%
Branches: 112 258 43.4%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 */
4
5 #include "kvstore.h"
6
7 #include <assert.h>
8 #include <errno.h>
9 #include <limits.h>
10 #include <string.h>
11 #include <unistd.h>
12
13 #include <algorithm>
14
15 #include "util/async.h"
16 #include "util/concurrency.h"
17 #include "util/logging.h"
18
19 using namespace std; // NOLINT
20
21 namespace {
22
23 3365698 static inline uint32_t hasher_any(const shash::Any &key) {
24 // We'll just do the same thing as hasher_md5, since every hash is at
25 // least as large.
26 return static_cast<uint32_t>(
27 3365698 *(reinterpret_cast<const uint32_t *>(key.digest) + 1));
28 }
29
30 } // anonymous namespace
31
32 const double MemoryKvStore::kCompactThreshold = 0.8;
33
34
35 2447 MemoryKvStore::MemoryKvStore(unsigned int cache_entries,
36 MemoryAllocator alloc,
37 unsigned alloc_size,
38 2447 perf::StatisticsTemplate statistics)
39 2447 : allocator_(alloc)
40 2447 , used_bytes_(0)
41 2447 , entry_count_(0)
42 2447 , max_entries_(cache_entries)
43
2/4
✓ Branch 1 taken 2447 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2447 times.
✗ Branch 5 not taken.
 2447 , entries_(cache_entries, shash::Any(), hasher_any,
44
2/4
✓ Branch 2 taken 2447 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2447 times.
✗ Branch 6 not taken.
 4894 perf::StatisticsTemplate("lru", statistics))
45 2447 , heap_(NULL)
46
2/4
✓ Branch 2 taken 2447 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2447 times.
✗ Branch 6 not taken.
 4894 , counters_(statistics) {
47 2447 const int retval = pthread_rwlock_init(&rwlock_, NULL);
48
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2447 times.
 2447 assert(retval == 0);
49
2/2
✓ Branch 0 taken 752 times.
✓ Branch 1 taken 1695 times.
 2447 switch (alloc) {
50 752 case kMallocHeap:
51 752 heap_ = new MallocHeap(
52
3/6
✓ Branch 1 taken 752 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 752 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 752 times.
✗ Branch 8 not taken.
 752 alloc_size, this->MakeCallback(&MemoryKvStore::OnBlockMove, this));
53 752 break;
54 1695 default:
55 1695 break;
56 }
57 2447 }
58
59
60 2447 MemoryKvStore::~MemoryKvStore() {
61
2/2
✓ Branch 0 taken 752 times.
✓ Branch 1 taken 1695 times.
 2447 delete heap_;
62 2447 pthread_rwlock_destroy(&rwlock_);
63 2447 }
64
65
66 ✗ void MemoryKvStore::OnBlockMove(const MallocHeap::BlockPtr &ptr) {
67 bool ok;
68 ✗ struct AllocHeader a;
69 ✗ MemoryBuffer buf;
70
71 // must be locked by caller
72 ✗ assert(ptr.pointer);
73 ✗ memcpy(&a, ptr.pointer, sizeof(a));
74 ✗ LogCvmfs(kLogKvStore, kLogDebug, "compaction moved %s to %p",
75 ✗ a.id.ToString().c_str(), ptr.pointer);
76 ✗ assert(a.version == 0);
77 ✗ const bool update_lru = false;
78 ✗ ok = entries_.Lookup(a.id, &buf, update_lru);
79 ✗ assert(ok);
80 ✗ buf.address = static_cast<char *>(ptr.pointer) + sizeof(a);
81 ✗ ok = entries_.UpdateValue(buf.id, buf);
82 ✗ assert(ok);
83 }
84
85
86 1511 bool MemoryKvStore::Contains(const shash::Any &id) {
87
1/2
✓ Branch 1 taken 1511 times.
✗ Branch 2 not taken.
 1511 MemoryBuffer buf;
88 // LogCvmfs(kLogKvStore, kLogDebug, "check buffer %s", id.ToString().c_str());
89 1511 const bool update_lru = false;
90
1/2
✓ Branch 1 taken 1511 times.
✗ Branch 2 not taken.
 3022 return entries_.Lookup(id, &buf, update_lru);
91 }
92
93
94 3836 int MemoryKvStore::DoMalloc(MemoryBuffer *buf) {
95
1/2
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
 3836 MemoryBuffer tmp;
96
1/2
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
 3836 AllocHeader a;
97
98
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3836 times.
 3836 assert(buf);
99 3836 memcpy(&tmp, buf, sizeof(tmp));
100
101 3836 tmp.address = NULL;
102
1/2
✓ Branch 0 taken 3836 times.
✗ Branch 1 not taken.
 3836 if (tmp.size > 0) {
103
1/3
✓ Branch 0 taken 3836 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 3836 switch (allocator_) {
104 3836 case kMallocLibc:
105 3836 tmp.address = malloc(tmp.size);
106
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3836 times.
 3836 if (!tmp.address)
107 ✗ return -errno;
108 3836 break;
109 ✗ case kMallocHeap:
110 ✗ assert(heap_);
111 ✗ a.id = tmp.id;
112 ✗ tmp.address = heap_->Allocate(tmp.size + sizeof(a), &a, sizeof(a));
113 ✗ if (!tmp.address)
114 ✗ return -ENOMEM;
115 ✗ tmp.address = static_cast<char *>(tmp.address) + sizeof(a);
116 ✗ break;
117 ✗ default:
118 ✗ abort();
119 }
120 }
121
122 3836 memcpy(buf, &tmp, sizeof(*buf));
123 3836 return 0;
124 }
125
126
127 2498 void MemoryKvStore::DoFree(MemoryBuffer *buf) {
128
1/2
✓ Branch 1 taken 2498 times.
✗ Branch 2 not taken.
 2498 const AllocHeader a;
129
130
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2498 times.
 2498 assert(buf);
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2498 times.
 2498 if (!buf->address)
132 ✗ return;
133
1/3
✓ Branch 0 taken 2498 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 2498 switch (allocator_) {
134 2498 case kMallocLibc:
135 2498 free(buf->address);
136 2498 return;
137 ✗ case kMallocHeap:
138 ✗ heap_->MarkFree(static_cast<char *>(buf->address) - sizeof(a));
139 ✗ return;
140 ✗ default:
141 ✗ abort();
142 }
143 }
144
145
146 3836 bool MemoryKvStore::CompactMemory() {
147 double utilization;
148
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3836 times.
 3836 switch (allocator_) {
149 ✗ case kMallocHeap:
150 ✗ utilization = heap_->utilization();
151 ✗ LogCvmfs(kLogKvStore, kLogDebug, "compact requested (%f)", utilization);
152 ✗ if (utilization < kCompactThreshold) {
153 ✗ LogCvmfs(kLogKvStore, kLogDebug, "compacting heap");
154 ✗ heap_->Compact();
155 ✗ if (heap_->utilization() > utilization)
156 ✗ return true;
157 }
158 ✗ return false;
159 3836 default:
160 // the others can't do any compact, so just ignore
161 3836 LogCvmfs(kLogKvStore, kLogDebug, "compact requested");
162 3836 return false;
163 }
164 }
165
166
167 249 int64_t MemoryKvStore::GetSize(const shash::Any &id) {
168
1/2
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
 249 MemoryBuffer mem;
169 249 perf::Inc(counters_.n_getsize);
170 249 const bool update_lru = false;
171
3/4
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 228 times.
✓ Branch 4 taken 21 times.
 249 if (entries_.Lookup(id, &mem, update_lru)) {
172 // LogCvmfs(kLogKvStore, kLogDebug, "%s is %u B", id.ToString().c_str(),
173 // mem.size);
174 228 return mem.size;
175 } else {
176
1/2
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
 21 LogCvmfs(kLogKvStore, kLogDebug, "miss %s on GetSize",
177
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 42 id.ToString().c_str());
178 21 return -ENOENT;
179 }
180 }
181
182
183 105 int64_t MemoryKvStore::GetRefcount(const shash::Any &id) {
184
1/2
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
 105 MemoryBuffer mem;
185 105 perf::Inc(counters_.n_getrefcount);
186 105 const bool update_lru = false;
187
2/4
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 105 times.
✗ Branch 4 not taken.
 105 if (entries_.Lookup(id, &mem, update_lru)) {
188 // LogCvmfs(kLogKvStore, kLogDebug, "%s has refcount %u",
189 // id.ToString().c_str(), mem.refcount);
190 105 return mem.refcount;
191 } else {
192 ✗ LogCvmfs(kLogKvStore, kLogDebug, "miss %s on GetRefcount",
193 ✗ id.ToString().c_str());
194 ✗ return -ENOENT;
195 }
196 }
197
198
199 540939 bool MemoryKvStore::IncRef(const shash::Any &id) {
200 540939 perf::Inc(counters_.n_incref);
201 540939 const WriteLockGuard guard(rwlock_);
202
1/2
✓ Branch 1 taken 540939 times.
✗ Branch 2 not taken.
 540939 MemoryBuffer mem;
203
3/4
✓ Branch 1 taken 540939 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 540918 times.
✓ Branch 4 taken 21 times.
 540939 if (entries_.Lookup(id, &mem)) {
204
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 540918 times.
 540918 assert(mem.refcount < UINT_MAX);
205 540918 ++mem.refcount;
206
1/2
✓ Branch 1 taken 540918 times.
✗ Branch 2 not taken.
 540918 entries_.Insert(id, mem);
207
1/2
✓ Branch 2 taken 540918 times.
✗ Branch 3 not taken.
 540918 LogCvmfs(kLogKvStore, kLogDebug, "increased refcount of %s to %u",
208
1/2
✓ Branch 1 taken 540918 times.
✗ Branch 2 not taken.
 1081836 id.ToString().c_str(), mem.refcount);
209 540918 return true;
210 } else {
211
1/2
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
 21 LogCvmfs(kLogKvStore, kLogDebug, "miss %s on IncRef",
212
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 42 id.ToString().c_str());
213 21 return false;
214 }
215 540939 }
216
217
218 540645 bool MemoryKvStore::Unref(const shash::Any &id) {
219 540645 perf::Inc(counters_.n_unref);
220 540645 const WriteLockGuard guard(rwlock_);
221
1/2
✓ Branch 1 taken 540645 times.
✗ Branch 2 not taken.
 540645 MemoryBuffer mem;
222
3/4
✓ Branch 1 taken 540645 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 540624 times.
✓ Branch 4 taken 21 times.
 540645 if (entries_.Lookup(id, &mem)) {
223
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 540624 times.
 540624 assert(mem.refcount > 0);
224 540624 --mem.refcount;
225
1/2
✓ Branch 1 taken 540624 times.
✗ Branch 2 not taken.
 540624 entries_.Insert(id, mem);
226
1/2
✓ Branch 2 taken 540624 times.
✗ Branch 3 not taken.
 540624 LogCvmfs(kLogKvStore, kLogDebug, "decreased refcount of %s to %u",
227
1/2
✓ Branch 1 taken 540624 times.
✗ Branch 2 not taken.
 1081248 id.ToString().c_str(), mem.refcount);
228 540624 return true;
229 } else {
230
2/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 21 times.
✗ Branch 6 not taken.
 21 LogCvmfs(kLogKvStore, kLogDebug, "miss %s on Unref", id.ToString().c_str());
231 21 return false;
232 }
233 540645 }
234
235
236 172 int64_t MemoryKvStore::Read(const shash::Any &id,
237 void *buf,
238 size_t size,
239 size_t offset) {
240
1/2
✓ Branch 1 taken 172 times.
✗ Branch 2 not taken.
 172 MemoryBuffer mem;
241 172 perf::Inc(counters_.n_read);
242 172 const ReadLockGuard guard(rwlock_);
243
2/4
✓ Branch 1 taken 172 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 172 times.
 172 if (!entries_.Lookup(id, &mem)) {
244 ✗ LogCvmfs(kLogKvStore, kLogDebug, "miss %s on Read", id.ToString().c_str());
245 ✗ return -ENOENT;
246 }
247
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 172 times.
 172 if (offset > mem.size) {
248 ✗ LogCvmfs(kLogKvStore, kLogDebug, "out of bounds read (%zu>%zu) on %s",
249 ✗ offset, mem.size, id.ToString().c_str());
250 ✗ return 0;
251 }
252 172 const uint64_t copy_size = std::min(mem.size - offset, size);
253 // LogCvmfs(kLogKvStore, kLogDebug, "copy %u B from offset %u of %s",
254 // copy_size, offset, id.ToString().c_str());
255 172 memcpy(buf, static_cast<char *>(mem.address) + offset, copy_size);
256 172 perf::Xadd(counters_.sz_read, copy_size);
257 172 return copy_size;
258 172 }
259
260
261 3836 int MemoryKvStore::Commit(const MemoryBuffer &buf) {
262 3836 const WriteLockGuard guard(rwlock_);
263
1/2
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
 7672 return DoCommit(buf);
264 3836 }
265
266
267 3836 int MemoryKvStore::DoCommit(const MemoryBuffer &buf) {
268 // we need to be careful about refcounts. If another thread wants to read
269 // a cache entry while it's being written (OpenFromTxn put partial data in
270 // the kvstore, will be committed again later) the refcount in the kvstore
271 // will differ from the refcount in the cache transaction. To avoid leaks,
272 // either the caller needs to fetch the cache entry before every write to
273 // find the current refcount, or the kvstore can ignore the passed-in
274 // refcount if the entry already exists. This implementation does the latter,
275 // and as a result it's not possible to directly modify the refcount
276 // without a race condition. This is a hint that callers should use the
277 // refcount like a lock and not directly modify the numeric value.
278
279
1/2
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
 3836 CompactMemory();
280
281
1/2
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
 3836 MemoryBuffer mem;
282 3836 perf::Inc(counters_.n_commit);
283
2/4
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3836 times.
✗ Branch 6 not taken.
 3836 LogCvmfs(kLogKvStore, kLogDebug, "commit %s", buf.id.ToString().c_str());
284
3/4
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 90 times.
✓ Branch 4 taken 3746 times.
 3836 if (entries_.Lookup(buf.id, &mem)) {
285
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 LogCvmfs(kLogKvStore, kLogDebug, "commit overwrites existing entry");
286 90 const size_t old_size = mem.size;
287
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 DoFree(&mem);
288 90 used_bytes_ -= old_size;
289 90 counters_.sz_size->Set(used_bytes_);
290 90 --entry_count_;
291 } else {
292 // since this is a new entry, the caller can choose the starting
293 // refcount (starting at 1 for pinning, for example)
294 3746 mem.refcount = buf.refcount;
295 }
296 3836 mem.object_flags = buf.object_flags;
297 3836 mem.id = buf.id;
298 3836 mem.size = buf.size;
299
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3836 times.
 3836 if (entry_count_ == max_entries_) {
300 ✗ LogCvmfs(kLogKvStore, kLogDebug, "too many entries in kvstore");
301 ✗ return -ENFILE;
302 }
303
2/4
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 3836 times.
 3836 if (DoMalloc(&mem) < 0) {
304 ✗ LogCvmfs(kLogKvStore, kLogDebug, "failed to allocate %s",
305 ✗ buf.id.ToString().c_str());
306 ✗ return -EIO;
307 }
308
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3836 times.
 3836 assert(SSIZE_MAX - mem.size > used_bytes_);
309 3836 memcpy(mem.address, buf.address, mem.size);
310
1/2
✓ Branch 1 taken 3836 times.
✗ Branch 2 not taken.
 3836 entries_.Insert(buf.id, mem);
311 3836 ++entry_count_;
312 3836 used_bytes_ += mem.size;
313 3836 counters_.sz_size->Set(used_bytes_);
314 3836 perf::Xadd(counters_.sz_committed, mem.size);
315 3836 return 0;
316 }
317
318
319 126 bool MemoryKvStore::Delete(const shash::Any &id) {
320 126 perf::Inc(counters_.n_delete);
321 126 const WriteLockGuard guard(rwlock_);
322
1/2
✓ Branch 1 taken 126 times.
✗ Branch 2 not taken.
 252 return DoDelete(id);
323 126 }
324
325
326 126 bool MemoryKvStore::DoDelete(const shash::Any &id) {
327
1/2
✓ Branch 1 taken 126 times.
✗ Branch 2 not taken.
 126 MemoryBuffer buf;
328
3/4
✓ Branch 1 taken 126 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 42 times.
✓ Branch 4 taken 84 times.
 126 if (!entries_.Lookup(id, &buf)) {
329
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 LogCvmfs(kLogKvStore, kLogDebug, "miss %s on Delete",
330
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 84 id.ToString().c_str());
331 42 return false;
332 }
333
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 84 times.
 84 if (buf.refcount > 0) {
334 ✗ LogCvmfs(kLogKvStore, kLogDebug, "can't delete %s, nonzero refcount",
335 ✗ id.ToString().c_str());
336 ✗ return false;
337 }
338
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 84 times.
 84 assert(entry_count_ > 0);
339 84 --entry_count_;
340 84 used_bytes_ -= buf.size;
341 84 counters_.sz_size->Set(used_bytes_);
342 84 perf::Xadd(counters_.sz_deleted, buf.size);
343
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 DoFree(&buf);
344
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 entries_.Forget(id);
345
2/4
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 84 times.
✗ Branch 6 not taken.
 84 LogCvmfs(kLogKvStore, kLogDebug, "deleted %s", id.ToString().c_str());
346 84 return true;
347 }
348
349
350 665 bool MemoryKvStore::ShrinkTo(size_t size) {
351 665 perf::Inc(counters_.n_shrinkto);
352 665 const WriteLockGuard guard(rwlock_);
353
1/2
✓ Branch 1 taken 665 times.
✗ Branch 2 not taken.
 665 shash::Any key;
354
1/2
✓ Branch 1 taken 665 times.
✗ Branch 2 not taken.
 665 MemoryBuffer buf;
355
356
2/2
✓ Branch 0 taken 287 times.
✓ Branch 1 taken 378 times.
 665 if (used_bytes_ <= size) {
357
1/2
✓ Branch 1 taken 287 times.
✗ Branch 2 not taken.
 287 LogCvmfs(kLogKvStore, kLogDebug, "no need to shrink");
358 287 return true;
359 }
360
361
1/2
✓ Branch 1 taken 378 times.
✗ Branch 2 not taken.
 378 LogCvmfs(kLogKvStore, kLogDebug, "shrinking to %zu B", size);
362
1/2
✓ Branch 1 taken 378 times.
✗ Branch 2 not taken.
 378 entries_.FilterBegin();
363
3/4
✓ Branch 1 taken 3080 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2863 times.
✓ Branch 4 taken 217 times.
 3080 while (entries_.FilterNext()) {
364
2/2
✓ Branch 0 taken 161 times.
✓ Branch 1 taken 2702 times.
 2863 if (used_bytes_ <= size)
365 161 break;
366
1/2
✓ Branch 1 taken 2702 times.
✗ Branch 2 not taken.
 2702 entries_.FilterGet(&key, &buf);
367
2/2
✓ Branch 0 taken 378 times.
✓ Branch 1 taken 2324 times.
 2702 if (buf.refcount > 0) {
368
1/2
✓ Branch 2 taken 378 times.
✗ Branch 3 not taken.
 378 LogCvmfs(kLogKvStore, kLogDebug, "skip %s, nonzero refcount",
369
1/2
✓ Branch 1 taken 378 times.
✗ Branch 2 not taken.
 756 key.ToString().c_str());
370 378 continue;
371 }
372
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2324 times.
 2324 assert(entry_count_ > 0);
373 2324 --entry_count_;
374
1/2
✓ Branch 1 taken 2324 times.
✗ Branch 2 not taken.
 2324 entries_.FilterDelete();
375 2324 used_bytes_ -= buf.size;
376 2324 perf::Xadd(counters_.sz_shrunk, buf.size);
377 2324 counters_.sz_size->Set(used_bytes_);
378
1/2
✓ Branch 1 taken 2324 times.
✗ Branch 2 not taken.
 2324 DoFree(&buf);
379
2/4
✓ Branch 1 taken 2324 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 2324 times.
✗ Branch 6 not taken.
 2324 LogCvmfs(kLogKvStore, kLogDebug, "delete %s", key.ToString().c_str());
380 }
381
1/2
✓ Branch 1 taken 378 times.
✗ Branch 2 not taken.
 378 entries_.FilterEnd();
382
1/2
✓ Branch 1 taken 378 times.
✗ Branch 2 not taken.
 378 LogCvmfs(kLogKvStore, kLogDebug, "shrunk to %zu B", used_bytes_);
383 378 return used_bytes_ <= size;
384 665 }
385