GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/glue_buffer.h
Date: 2025-11-02 02:35:35
Exec Total Coverage
Lines: 302 427 70.7%
Branches: 117 304 38.5%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 *
4 * This module provides the inode tracker in order to remember inodes
5 * and their parents that are in use by the kernel.
6 *
7 * These objects have to survive reloading of the library, so no virtual
8 * functions.
9 */
10
11 #include "duplex_testing.h"
12 #include <pthread.h>
13 #include <sched.h>
14 #include <stdint.h>
15
16 #include <cassert>
17 #include <cstring>
18 #include <map>
19 #include <string>
20 #include <vector>
21
22 #include "bigqueue.h"
23 #include "bigvector.h"
24 #include "crypto/hash.h"
25 #include "directory_entry.h"
26 #include "shortstring.h"
27 #include "smallhash.h"
28 #include "util/atomic.h"
29 #include "util/exception.h"
30 #include "util/mutex.h"
31 #include "util/platform.h"
32 #include "util/posix.h"
33 #include "util/smalloc.h"
34 #include "util/string.h"
35
36 #ifndef CVMFS_GLUE_BUFFER_H_
37 #define CVMFS_GLUE_BUFFER_H_
38
39 namespace glue {
40
41 /**
42 * Inode + file type. Stores the file type in the 4 most significant bits
43 * of the 64 bit unsigned integer representing the inode. That makes the class
44 * compatible with a pure 64bit inode used in previous cvmfs versions in the
45 * inode tracker. The file type is stored using the POSIX representation in
46 * the inode's mode field.
47 * Note that InodeEx, used as a hash table key, hashes only over the inode part.
48 */
49 class InodeEx {
50 private:
51 // Extracts the file type bits from the POSIX mode field and shifts them to
52 // the right so that they align with EFileType constants.
53 144 static inline uint64_t ShiftMode(unsigned mode) { return (mode >> 12) & 017; }
54
55 public:
56 enum EFileType {
57 kUnknownType = 0,
58 kRegular = 010,
59 kSymlink = 012,
60 kDirectory = 004,
61 kFifo = 001,
62 kSocket = 014,
63 kCharDev = 002,
64 kBulkDev = 006,
65 };
66
67 327428 InodeEx() : inode_ex_(0) { }
68 72288 InodeEx(uint64_t inode, EFileType type)
69 72288 : inode_ex_(inode | (static_cast<uint64_t>(type) << 60)) { }
70 36 InodeEx(uint64_t inode, unsigned mode)
71 36 : inode_ex_(inode | (ShiftMode(mode) << 60)) { }
72
73 1664584 inline uint64_t GetInode() const { return inode_ex_ & ~(uint64_t(15) << 60); }
74 420 inline EFileType GetFileType() const {
75 420 return static_cast<EFileType>(inode_ex_ >> 60);
76 }
77
78 566746 inline bool operator==(const InodeEx &other) const {
79 566746 return GetInode() == other.GetInode();
80 }
81 151662 inline bool operator!=(const InodeEx &other) const {
82 151662 return GetInode() != other.GetInode();
83 }
84
85 108 inline bool IsCompatibleFileType(unsigned mode) const {
86 108 return (static_cast<uint64_t>(GetFileType()) == ShiftMode(mode))
87
4/4
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 36 times.
✓ Branch 3 taken 36 times.
✓ Branch 4 taken 36 times.
 108 || (GetFileType() == kUnknownType);
88 }
89
90 private:
91 uint64_t inode_ex_;
92 };
93
94 407204 static inline uint32_t hasher_md5(const shash::Md5 &key) {
95 // Don't start with the first bytes, because == is using them as well
96 return static_cast<uint32_t>(
97 407204 *(reinterpret_cast<const uint32_t *>(key.digest) + 1));
98 }
99
100 350350 static inline uint32_t hasher_inode(const uint64_t &inode) {
101 350350 return MurmurHash2(&inode, sizeof(inode), 0x07387a4f);
102 }
103
104 186424 static inline uint32_t hasher_inode_ex(const InodeEx &inode_ex) {
105 186424 return hasher_inode(inode_ex.GetInode());
106 }
107
108
109 //------------------------------------------------------------------------------
110
111
112 /**
113 * Pointer to a 2 byte length information followed by the characters
114 */
115 class StringRef {
116 public:
117 399354 StringRef() { length_ = NULL; }
118
119 216 uint16_t length() const { return *length_; }
120 ✗ uint16_t size() const { return sizeof(uint16_t) + *length_; }
121 41104 static uint16_t size(const uint16_t length) {
122 41104 return sizeof(uint16_t) + length;
123 }
124 216 char *data() const { return reinterpret_cast<char *>(length_ + 1); }
125 41104 static StringRef Place(const uint16_t length, const char *str, void *addr) {
126 41104 StringRef result;
127 41104 result.length_ = reinterpret_cast<uint16_t *>(addr);
128 41104 *result.length_ = length;
129
2/2
✓ Branch 0 taken 41028 times.
✓ Branch 1 taken 76 times.
 41104 if (length > 0)
130 41028 memcpy(result.length_ + 1, str, length);
131 41104 return result;
132 }
133
134 private:
135 uint16_t *length_;
136 };
137
138
139 //------------------------------------------------------------------------------
140
141
142 /**
143 * Manages memory bins with immutable strings (deleting is a no-op).
144 * When the fraction of garbage is too large, the user of the StringHeap
145 * can copy the entire contents to a new heap.
146 */
147 class StringHeap : public SingleCopy {
148 public:
149 1050 StringHeap() {
150
1/2
✓ Branch 1 taken 1050 times.
✗ Branch 2 not taken.
 1050 Init(128 * 1024); // 128kB (should be >= 64kB+2B which is largest string)
151 1050 }
152
153
1/2
✓ Branch 3 taken 109 times.
✗ Branch 4 not taken.
 109 explicit StringHeap(const uint64_t minimum_size) { Init(minimum_size); }
154
155 1159 void Init(const uint64_t minimum_size) {
156 1159 size_ = 0;
157 1159 used_ = 0;
158
159 // Initial bin: 128kB or smallest power of 2 >= minimum size
160 1159 uint64_t pow2_size = 128 * 1024;
161
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 1159 times.
 1210 while (pow2_size < minimum_size)
162 51 pow2_size *= 2;
163 1159 AddBin(pow2_size);
164 1159 }
165
166 1156 ~StringHeap() {
167
2/2
✓ Branch 1 taken 1156 times.
✓ Branch 2 taken 1156 times.
 2312 for (unsigned i = 0; i < bins_.size(); ++i) {
168 1156 smunmap(bins_.At(i));
169 }
170 1156 }
171
172 41104 StringRef AddString(const uint16_t length, const char *str) {
173 41104 const uint16_t str_size = StringRef::size(length);
174 41104 const uint64_t remaining_bin_size = bin_size_ - bin_used_;
175 // May require opening of new bin
176
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 41104 times.
 41104 if (remaining_bin_size < str_size) {
177 ✗ size_ += remaining_bin_size;
178 ✗ AddBin(2 * bin_size_);
179 }
180 41104 StringRef result = StringRef::Place(
181 length, str,
182 41104 static_cast<char *>(bins_.At(bins_.size() - 1)) + bin_used_);
183 41104 size_ += str_size;
184 41104 used_ += str_size;
185 41104 bin_used_ += str_size;
186 41104 return result;
187 }
188
189 ✗ void RemoveString(const StringRef str_ref) { used_ -= str_ref.size(); }
190
191 ✗ double GetUsage() const {
192 ✗ if (size_ == 0)
193 ✗ return 1.0;
194 ✗ return static_cast<double>(used_) / static_cast<double>(size_);
195 }
196
197 ✗ uint64_t used() const { return used_; }
198
199 // mmap'd bytes, used for testing
200 145 uint64_t GetSizeAlloc() const {
201 145 uint64_t s = bin_size_;
202 145 uint64_t result = 0;
203
2/2
✓ Branch 1 taken 145 times.
✓ Branch 2 taken 145 times.
 290 for (unsigned i = 0; i < bins_.size(); ++i) {
204 145 result += s;
205 145 s /= 2;
206 }
207 145 return result;
208 }
209
210 private:
211 1159 void AddBin(const uint64_t size) {
212 1159 void *bin = smmap(size);
213
1/2
✓ Branch 1 taken 1159 times.
✗ Branch 2 not taken.
 1159 bins_.PushBack(bin);
214 1159 bin_size_ = size;
215 1159 bin_used_ = 0;
216 1159 }
217
218 uint64_t size_;
219 uint64_t used_;
220 uint64_t bin_size_;
221 uint64_t bin_used_;
222 BigVector<void *> bins_;
223 };
224
225
226 //------------------------------------------------------------------------------
227
228
229 class PathStore {
230 public:
231 /**
232 * Used to enumerate all paths
233 */
234 struct Cursor {
235 192 Cursor() : idx(0) { }
236 uint32_t idx;
237 };
238
239
240 1014 PathStore() {
241
3/6
✓ Branch 2 taken 1014 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1014 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1014 times.
✗ Branch 10 not taken.
 1014 map_.Init(16, shash::Md5(shash::AsciiPtr("!")), hasher_md5);
242
2/4
✓ Branch 1 taken 1014 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1014 times.
✗ Branch 5 not taken.
 1014 string_heap_ = new StringHeap();
243 1014 }
244
245
1/2
✓ Branch 0 taken 1012 times.
✗ Branch 1 not taken.
 1012 ~PathStore() { delete string_heap_; }
246
247 explicit PathStore(const PathStore &other);
248 PathStore &operator=(const PathStore &other);
249
250 82132 void Insert(const shash::Md5 &md5path, const PathString &path) {
251
1/2
✓ Branch 1 taken 82132 times.
✗ Branch 2 not taken.
 82132 PathInfo info;
252
1/2
✓ Branch 1 taken 82132 times.
✗ Branch 2 not taken.
 82132 const bool found = map_.Lookup(md5path, &info);
253
2/2
✓ Branch 0 taken 41028 times.
✓ Branch 1 taken 41104 times.
 82132 if (found) {
254 41028 info.refcnt++;
255
1/2
✓ Branch 1 taken 41028 times.
✗ Branch 2 not taken.
 41028 map_.Insert(md5path, info);
256 41104 return;
257 }
258
259
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 PathInfo new_entry;
260
3/4
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 76 times.
✓ Branch 4 taken 41028 times.
 41104 if (path.IsEmpty()) {
261
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 new_entry.name = string_heap_->AddString(0, "");
262
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 map_.Insert(md5path, new_entry);
263 76 return;
264 }
265
266
1/2
✓ Branch 1 taken 41028 times.
✗ Branch 2 not taken.
 41028 const PathString parent_path = GetParentPath(path);
267
1/2
✓ Branch 3 taken 41028 times.
✗ Branch 4 not taken.
 41028 new_entry.parent = shash::Md5(parent_path.GetChars(),
268 parent_path.GetLength());
269
1/2
✓ Branch 1 taken 41028 times.
✗ Branch 2 not taken.
 41028 Insert(new_entry.parent, parent_path);
270
271 41028 const uint16_t name_length = path.GetLength() - parent_path.GetLength() - 1;
272 41028 const char *name_str = path.GetChars() + parent_path.GetLength() + 1;
273
1/2
✓ Branch 1 taken 41028 times.
✗ Branch 2 not taken.
 41028 new_entry.name = string_heap_->AddString(name_length, name_str);
274
1/2
✓ Branch 1 taken 41028 times.
✗ Branch 2 not taken.
 41028 map_.Insert(md5path, new_entry);
275 41028 }
276
277 108 bool Lookup(const shash::Md5 &md5path, PathString *path) {
278
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 PathInfo info;
279
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 bool retval = map_.Lookup(md5path, &info);
280
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 108 times.
 108 if (!retval)
281 ✗ return false;
282
283
2/2
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 72 times.
 108 if (info.parent.IsNull())
284 36 return true;
285
286
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 retval = Lookup(info.parent, path);
287
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 assert(retval);
288
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 path->Append("/", 1);
289
1/2
✓ Branch 3 taken 72 times.
✗ Branch 4 not taken.
 72 path->Append(info.name.data(), info.name.length());
290 72 return true;
291 }
292
293 ✗ void Erase(const shash::Md5 &md5path) {
294 ✗ PathInfo info;
295 ✗ const bool found = map_.Lookup(md5path, &info);
296 ✗ if (!found)
297 ✗ return;
298
299 ✗ info.refcnt--;
300 ✗ if (info.refcnt == 0) {
301 ✗ map_.Erase(md5path);
302 ✗ string_heap_->RemoveString(info.name);
303 ✗ if (string_heap_->GetUsage() < 0.75) {
304 ✗ StringHeap *new_string_heap = new StringHeap(string_heap_->used());
305 ✗ const shash::Md5 empty_path = map_.empty_key();
306 ✗ for (unsigned i = 0; i < map_.capacity(); ++i) {
307 ✗ if (map_.keys()[i] != empty_path) {
308 ✗ (map_.values() + i)->name = new_string_heap->AddString(
309 ✗ map_.values()[i].name.length(), map_.values()[i].name.data());
310 }
311 }
312 ✗ delete string_heap_;
313 ✗ string_heap_ = new_string_heap;
314 }
315 ✗ Erase(info.parent);
316 } else {
317 ✗ map_.Insert(md5path, info);
318 }
319 }
320
321 void Clear() {
322 map_.Clear();
323 delete string_heap_;
324 string_heap_ = new StringHeap();
325 }
326
327 192 Cursor BeginEnumerate() { return Cursor(); }
328
329 252 bool Next(Cursor *cursor, shash::Md5 *parent, StringRef *name) {
330 252 const shash::Md5 empty_key = map_.empty_key();
331
2/2
✓ Branch 1 taken 1512 times.
✓ Branch 2 taken 108 times.
 1620 while (cursor->idx < map_.capacity()) {
332
2/2
✓ Branch 2 taken 1368 times.
✓ Branch 3 taken 144 times.
 1512 if (map_.keys()[cursor->idx] == empty_key) {
333 1368 cursor->idx++;
334 1368 continue;
335 }
336 144 *parent = map_.values()[cursor->idx].parent;
337 144 *name = map_.values()[cursor->idx].name;
338 144 cursor->idx++;
339 144 return true;
340 }
341 108 return false;
342 }
343
344 private:
345 struct PathInfo {
346 357998 PathInfo() { refcnt = 1; }
347 shash::Md5 parent;
348 uint32_t refcnt;
349 StringRef name;
350 };
351
352 void CopyFrom(const PathStore &other);
353
354 SmallHashDynamic<shash::Md5, PathInfo> map_;
355 StringHeap *string_heap_;
356 };
357
358
359 //------------------------------------------------------------------------------
360
361
362 /**
363 * A vector of stat structs. When removing items, the empty slot is swapped
364 * with the last element so that there are no gaps in the vector. The memory
365 * allocation of the vector grows and shrinks with the size.
366 * Removal of items returns the inode of the element swapped with the gap so
367 * that the page entry tracker can update its index.
368 */
369 class StatStore {
370 public:
371 36174 int32_t Add(const struct stat &info) {
372 // We don't support more that 2B open files
373
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 36174 times.
 36174 assert(store_.size() < (1LU << 31));
374 36174 const int32_t index = static_cast<int>(store_.size());
375 36174 store_.PushBack(info);
376 36174 return index;
377 }
378
379 // Note that that if the last element is removed, no swap has taken place
380 36139 uint64_t Erase(int32_t index) {
381 36139 struct stat const info_back = store_.At(store_.size() - 1);
382 36139 store_.Replace(index, info_back);
383 36139 store_.SetSize(store_.size() - 1);
384
1/2
✓ Branch 1 taken 36139 times.
✗ Branch 2 not taken.
 36139 store_.ShrinkIfOversized();
385 36139 return info_back.st_ino;
386 }
387
388 71890 struct stat Get(int32_t index) const { return store_.At(index); }
389
390 private:
391 BigVector<struct stat> store_;
392 };
393
394
395 //------------------------------------------------------------------------------
396
397
398 class PathMap {
399 public:
400
4/8
✓ Branch 2 taken 1014 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1014 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 1014 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1014 times.
✗ Branch 14 not taken.
 1014 PathMap() { map_.Init(16, shash::Md5(shash::AsciiPtr("!")), hasher_md5); }
401
402 36 bool LookupPath(const shash::Md5 &md5path, PathString *path) {
403 36 const bool found = path_store_.Lookup(md5path, path);
404 36 return found;
405 }
406
407 36 uint64_t LookupInodeByPath(const PathString &path) {
408 uint64_t inode;
409
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 const bool found = map_.Lookup(
410
1/2
✓ Branch 3 taken 36 times.
✗ Branch 4 not taken.
 36 shash::Md5(path.GetChars(), path.GetLength()), &inode);
411
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 if (found)
412 36 return inode;
413 ✗ return 0;
414 }
415
416 108 uint64_t LookupInodeByMd5Path(const shash::Md5 &md5path) {
417 uint64_t inode;
418
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 const bool found = map_.Lookup(md5path, &inode);
419
1/2
✓ Branch 0 taken 108 times.
✗ Branch 1 not taken.
 108 if (found)
420 108 return inode;
421 ✗ return 0;
422 }
423
424 41104 shash::Md5 Insert(const PathString &path, const uint64_t inode) {
425 41104 shash::Md5 md5path(path.GetChars(), path.GetLength());
426
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 if (!map_.Contains(md5path)) {
427 41104 path_store_.Insert(md5path, path);
428 41104 map_.Insert(md5path, inode);
429 }
430 41104 return md5path;
431 }
432
433 ✗ void Erase(const shash::Md5 &md5path) {
434 ✗ const bool found = map_.Contains(md5path);
435 ✗ if (found) {
436 ✗ path_store_.Erase(md5path);
437 ✗ map_.Erase(md5path);
438 }
439 }
440
441 ✗ void Replace(const shash::Md5 &md5path, uint64_t new_inode) {
442 ✗ map_.Insert(md5path, new_inode);
443 }
444
445 void Clear() {
446 map_.Clear();
447 path_store_.Clear();
448 }
449
450 // For enumerating
451 444 PathStore *path_store() { return &path_store_; }
452
453 private:
454 SmallHashDynamic<shash::Md5, uint64_t> map_;
455 PathStore path_store_;
456 };
457
458
459 //------------------------------------------------------------------------------
460
461
462 /**
463 * This class has the same memory layout than the previous "InodeMap" class,
464 * therefore there is no data structure migration during reload required.
465 */
466 class InodeExMap {
467 public:
468
1/2
✓ Branch 3 taken 1014 times.
✗ Branch 4 not taken.
 1014 InodeExMap() { map_.Init(16, InodeEx(), hasher_inode_ex); }
469
470 72 bool LookupMd5Path(InodeEx *inode_ex, shash::Md5 *md5path) {
471 72 const bool found = map_.LookupEx(inode_ex, md5path);
472 72 return found;
473 }
474
475 41104 void Insert(const InodeEx inode_ex, const shash::Md5 &md5path) {
476 41104 map_.Insert(inode_ex, md5path);
477 41104 }
478
479 ✗ void Erase(const uint64_t inode) {
480 ✗ map_.Erase(InodeEx(inode, InodeEx::kUnknownType));
481 }
482
483 void Clear() { map_.Clear(); }
484
485 private:
486 SmallHashDynamic<InodeEx, shash::Md5> map_;
487 };
488
489
490 //------------------------------------------------------------------------------
491
492
493 class InodeReferences {
494 public:
495 /**
496 * Used to enumerate all inodes
497 */
498 struct Cursor {
499 192 Cursor() : idx(0) { }
500 uint32_t idx;
501 };
502
503
1/2
✓ Branch 2 taken 1014 times.
✗ Branch 3 not taken.
 1014 InodeReferences() { map_.Init(16, 0, hasher_inode); }
504
505 41104 bool Get(const uint64_t inode, const uint32_t by) {
506 41104 uint32_t refcounter = 0;
507
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 const bool found = map_.Lookup(inode, &refcounter);
508 41104 const bool new_inode = !found;
509 41104 refcounter += by; // This is 0 if the inode is not found
510
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 map_.Insert(inode, refcounter);
511 41104 return new_inode;
512 }
513
514 ✗ bool Put(const uint64_t inode, const uint32_t by) {
515 uint32_t refcounter;
516 ✗ const bool found = map_.Lookup(inode, &refcounter);
517 ✗ if (!found) {
518 // May happen if a retired inode is cleared, i.e. if a file with
519 // outdated content is closed
520 ✗ return false;
521 }
522
523 ✗ if (refcounter < by) {
524 ✗ PANIC(kLogSyslogErr | kLogDebug,
525 "inode tracker refcount mismatch, inode % " PRIu64
526 ", refcounts %u / %u",
527 inode, refcounter, by);
528 }
529
530 ✗ if (refcounter == by) {
531 ✗ map_.Erase(inode);
532 ✗ return true;
533 }
534 ✗ refcounter -= by;
535 ✗ map_.Insert(inode, refcounter);
536 ✗ return false;
537 }
538
539 ✗ void Replace(const uint64_t old_inode, const uint64_t new_inode) {
540 ✗ map_.Erase(old_inode);
541 ✗ map_.Insert(new_inode, 0);
542 }
543
544 void Clear() { map_.Clear(); }
545
546 192 Cursor BeginEnumerate() { return Cursor(); }
547
548 123216 bool Next(Cursor *cursor, uint64_t *inode) {
549 123216 const uint64_t empty_key = map_.empty_key();
550
2/2
✓ Branch 1 taken 324072 times.
✓ Branch 2 taken 192 times.
 324264 while (cursor->idx < map_.capacity()) {
551
2/2
✓ Branch 1 taken 201048 times.
✓ Branch 2 taken 123024 times.
 324072 if (map_.keys()[cursor->idx] == empty_key) {
552 201048 cursor->idx++;
553 201048 continue;
554 }
555 123024 *inode = map_.keys()[cursor->idx];
556 123024 cursor->idx++;
557 123024 return true;
558 }
559 192 return false;
560 }
561
562 private:
563 SmallHashDynamic<uint64_t, uint32_t> map_;
564 };
565
566
567 //------------------------------------------------------------------------------
568
569
570 /**
571 * Tracks inode reference counters as given by Fuse.
572 */
573 class InodeTracker {
574 public:
575 /**
576 * Used to actively evict all known paths from kernel caches
577 */
578 struct Cursor {
579 192 explicit Cursor(const PathStore::Cursor &p,
580 const InodeReferences::Cursor &i)
581 192 : csr_paths(p), csr_inos(i) { }
582 PathStore::Cursor csr_paths;
583 InodeReferences::Cursor csr_inos;
584 };
585
586 /**
587 * To avoid taking the InodeTracker mutex multiple times, the fuse
588 * forget_multi callback releases inodes references through this RAII object.
589 * Copy and assign operator should be deleted but that would require
590 * all compilers to use RVO. TODO(jblomer): fix with C++11
591 */
592 class VfsPutRaii {
593 public:
594 ✗ explicit VfsPutRaii(InodeTracker *t) : tracker_(t) { tracker_->Lock(); }
595 ✗ ~VfsPutRaii() { tracker_->Unlock(); }
596
597 ✗ bool VfsPut(const uint64_t inode, const uint32_t by) {
598 ✗ const bool removed = tracker_->inode_references_.Put(inode, by);
599 ✗ if (removed) {
600 // TODO(jblomer): pop operation (Lookup+Erase)
601 ✗ shash::Md5 md5path;
602 ✗ InodeEx inode_ex(inode, InodeEx::kUnknownType);
603 ✗ const bool found = tracker_->inode_ex_map_.LookupMd5Path(&inode_ex,
604 &md5path);
605 ✗ if (!found) {
606 ✗ PANIC(kLogSyslogErr | kLogDebug,
607 "inode tracker ref map and path map out of sync: %" PRIu64,
608 inode);
609 }
610 ✗ tracker_->inode_ex_map_.Erase(inode);
611 ✗ tracker_->path_map_.Erase(md5path);
612 ✗ atomic_inc64(&tracker_->statistics_.num_removes);
613 }
614 ✗ atomic_xadd64(&tracker_->statistics_.num_references, -int32_t(by));
615 ✗ return removed;
616 }
617
618 private:
619 InodeTracker *tracker_;
620 };
621
622 // Cannot be moved to the statistics manager because it has to survive
623 // reloads. Added manually in the fuse module initialization and in talk.cc.
624 struct Statistics {
625 1014 Statistics() {
626 1014 atomic_init64(&num_inserts);
627 1014 atomic_init64(&num_removes);
628 1014 atomic_init64(&num_references);
629 1014 atomic_init64(&num_hits_inode);
630 1014 atomic_init64(&num_hits_path);
631 1014 atomic_init64(&num_misses_path);
632 1014 }
633 std::string Print() {
634 return "inserts: " + StringifyInt(atomic_read64(&num_inserts))
635 + " removes: " + StringifyInt(atomic_read64(&num_removes))
636 + " references: " + StringifyInt(atomic_read64(&num_references))
637 + " hits(inode): " + StringifyInt(atomic_read64(&num_hits_inode))
638 + " hits(path): " + StringifyInt(atomic_read64(&num_hits_path))
639 + " misses(path): "
640 + StringifyInt(atomic_read64(&num_misses_path));
641 }
642 atomic_int64 num_inserts;
643 atomic_int64 num_removes;
644 atomic_int64 num_references;
645 atomic_int64 num_hits_inode;
646 atomic_int64 num_hits_path;
647 atomic_int64 num_misses_path;
648 };
649 ✗ Statistics GetStatistics() { return statistics_; }
650
651 InodeTracker();
652 explicit InodeTracker(const InodeTracker &other);
653 InodeTracker &operator=(const InodeTracker &other);
654 ~InodeTracker();
655
656 41104 void VfsGetBy(const InodeEx inode_ex, const uint32_t by,
657 const PathString &path) {
658 41104 const uint64_t inode = inode_ex.GetInode();
659 41104 Lock();
660
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 const bool is_new_inode = inode_references_.Get(inode, by);
661
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 const shash::Md5 md5path = path_map_.Insert(path, inode);
662
1/2
✓ Branch 1 taken 41104 times.
✗ Branch 2 not taken.
 41104 inode_ex_map_.Insert(inode_ex, md5path);
663 41104 Unlock();
664
665 41104 atomic_xadd64(&statistics_.num_references, by);
666
1/2
✓ Branch 0 taken 41104 times.
✗ Branch 1 not taken.
 41104 if (is_new_inode)
667 41104 atomic_inc64(&statistics_.num_inserts);
668 41104 }
669
670 41104 void VfsGet(const InodeEx inode_ex, const PathString &path) {
671 41104 VfsGetBy(inode_ex, 1, path);
672 41104 }
673
674 ✗ VfsPutRaii GetVfsPutRaii() { return VfsPutRaii(this); }
675
676 ✗ bool FindPath(InodeEx *inode_ex, PathString *path) {
677 ✗ Lock();
678 ✗ shash::Md5 md5path;
679 ✗ bool found = inode_ex_map_.LookupMd5Path(inode_ex, &md5path);
680 ✗ if (found) {
681 ✗ found = path_map_.LookupPath(md5path, path);
682 ✗ assert(found);
683 }
684 ✗ Unlock();
685
686 ✗ if (found) {
687 ✗ atomic_inc64(&statistics_.num_hits_path);
688 } else {
689 ✗ atomic_inc64(&statistics_.num_misses_path);
690 }
691 ✗ return found;
692 }
693
694 ✗ uint64_t FindInode(const PathString &path) {
695 ✗ Lock();
696 ✗ const uint64_t inode = path_map_.LookupInodeByPath(path);
697 ✗ Unlock();
698 ✗ atomic_inc64(&statistics_.num_hits_inode);
699 ✗ return inode;
700 }
701
702 72 bool FindDentry(uint64_t ino, uint64_t *parent_ino, NameString *name) {
703 72 PathString path;
704 72 InodeEx inodex(ino, InodeEx::kUnknownType);
705
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 shash::Md5 md5path;
706
707 72 Lock();
708
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 bool found = inode_ex_map_.LookupMd5Path(&inodex, &md5path);
709
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 36 times.
 72 if (found) {
710
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 found = path_map_.LookupPath(md5path, &path);
711
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 assert(found);
712
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 *name = GetFileName(path);
713
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 path = GetParentPath(path);
714
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 *parent_ino = path_map_.LookupInodeByPath(path);
715 }
716 72 Unlock();
717 72 return found;
718 72 }
719
720 /**
721 * The new inode has reference counter 0. Returns true if the inode was
722 * found and replaced
723 */
724 ✗ bool ReplaceInode(uint64_t old_inode, const InodeEx &new_inode) {
725 ✗ shash::Md5 md5path;
726 ✗ InodeEx old_inode_ex(old_inode, InodeEx::kUnknownType);
727 ✗ Lock();
728 ✗ const bool found = inode_ex_map_.LookupMd5Path(&old_inode_ex, &md5path);
729 ✗ if (found) {
730 ✗ inode_references_.Replace(old_inode, new_inode.GetInode());
731 ✗ path_map_.Replace(md5path, new_inode.GetInode());
732 ✗ inode_ex_map_.Erase(old_inode);
733 ✗ inode_ex_map_.Insert(new_inode, md5path);
734 }
735 ✗ Unlock();
736 ✗ return found;
737 }
738
739 192 Cursor BeginEnumerate() {
740 192 Lock();
741 192 return Cursor(path_map_.path_store()->BeginEnumerate(),
742 384 inode_references_.BeginEnumerate());
743 }
744
745 252 bool NextEntry(Cursor *cursor, uint64_t *inode_parent, NameString *name) {
746
1/2
✓ Branch 1 taken 252 times.
✗ Branch 2 not taken.
 252 shash::Md5 parent_md5;
747 252 StringRef name_ref;
748
1/2
✓ Branch 2 taken 252 times.
✗ Branch 3 not taken.
 252 const bool result = path_map_.path_store()->Next(&(cursor->csr_paths),
749 &parent_md5, &name_ref);
750
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 144 times.
 252 if (!result)
751 108 return false;
752
2/2
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 108 times.
 144 if (parent_md5.IsNull())
753 36 *inode_parent = 0;
754 else
755
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 *inode_parent = path_map_.LookupInodeByMd5Path(parent_md5);
756
1/2
✓ Branch 3 taken 144 times.
✗ Branch 4 not taken.
 144 name->Assign(name_ref.data(), name_ref.length());
757 144 return true;
758 }
759
760 123216 bool NextInode(Cursor *cursor, uint64_t *inode) {
761 123216 return inode_references_.Next(&(cursor->csr_inos), inode);
762 }
763
764 192 void EndEnumerate(Cursor *cursor) { Unlock(); }
765
766 private:
767 static const unsigned kVersion = 4;
768
769 void InitLock();
770 void CopyFrom(const InodeTracker &other);
771 41368 inline void Lock() const {
772 41368 const int retval = pthread_mutex_lock(lock_);
773
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 41368 times.
 41368 assert(retval == 0);
774 41368 }
775 41368 inline void Unlock() const {
776 41368 const int retval = pthread_mutex_unlock(lock_);
777
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 41368 times.
 41368 assert(retval == 0);
778 41368 }
779
780 unsigned version_;
781 pthread_mutex_t *lock_;
782 PathMap path_map_;
783 InodeExMap inode_ex_map_;
784 InodeReferences inode_references_;
785 Statistics statistics_;
786 }; // class InodeTracker
787
788
789 /**
790 * Tracks fuse name lookup replies for active cache eviction.
791 * Class renamed from previous name NentryTracker
792 */
793 class DentryTracker {
794 FRIEND_TEST(T_GlueBuffer, DentryTracker);
795
796 private:
797 struct Entry {
798 Entry() : expiry(0), inode_parent(0) { }
799 82058 Entry(uint64_t e, uint64_t p, const char *n)
800 82058 : expiry(e), inode_parent(p), name(n, strlen(n)) { }
801 uint64_t expiry;
802 uint64_t inode_parent;
803 NameString name;
804 };
805
806 public:
807 struct Cursor {
808 360 explicit Cursor(Entry *h) : head(h), pos(0) { }
809 Entry *head;
810 size_t pos;
811 };
812
813 // Cannot be moved to the statistics manager because it has to survive
814 // reloads. Added manually in the fuse module initialization and in talk.cc.
815 struct Statistics {
816 884 Statistics() : num_insert(0), num_remove(0), num_prune(0) { }
817 int64_t num_insert;
818 int64_t num_remove;
819 int64_t num_prune;
820 };
821 210 Statistics GetStatistics() { return statistics_; }
822
823 static void *MainCleaner(void *data);
824
825 DentryTracker();
826 DentryTracker(const DentryTracker &other);
827 DentryTracker &operator=(const DentryTracker &other);
828 ~DentryTracker();
829
830 /**
831 * Lock object during copy
832 */
833 DentryTracker *Move();
834
835 82126 void Add(const uint64_t inode_parent, const char *name, uint64_t timeout_s) {
836
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 82092 times.
 82126 if (!is_active_)
837 34 return;
838
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 82058 times.
 82092 if (timeout_s == 0)
839 34 return;
840
841 82058 const uint64_t now = platform_monotonic_time();
842 82058 Lock();
843
1/2
✓ Branch 2 taken 82058 times.
✗ Branch 3 not taken.
 82058 entries_.PushBack(Entry(now + timeout_s, inode_parent, name));
844 82058 statistics_.num_insert++;
845 82058 DoPrune(now);
846 82058 Unlock();
847 }
848
849 void Prune();
850 /**
851 * The nentry tracker is only needed for active cache eviction and can
852 * otherwise ignore new entries.
853 */
854 34 void Disable() { is_active_ = false; }
855 ✗ bool is_active() const { return is_active_; }
856
857 void SpawnCleaner(unsigned interval_s);
858
859 Cursor BeginEnumerate();
860 bool NextEntry(Cursor *cursor, uint64_t *inode_parent, NameString *name);
861 void EndEnumerate(Cursor *cursor);
862
863 private:
864 static const unsigned kVersion = 0;
865
866 void CopyFrom(const DentryTracker &other);
867
868 void InitLock();
869 82836 inline void Lock() const {
870 82836 const int retval = pthread_mutex_lock(lock_);
871
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 82836 times.
 82836 assert(retval == 0);
872 82836 }
873 82836 inline void Unlock() const {
874 82836 const int retval = pthread_mutex_unlock(lock_);
875
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 82836 times.
 82836 assert(retval == 0);
876 82836 }
877
878 82356 void DoPrune(uint64_t now) {
879 Entry *entry;
880
3/4
✓ Branch 1 taken 82460 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 82278 times.
✓ Branch 4 taken 182 times.
 82460 while (entries_.Peek(&entry)) {
881
2/2
✓ Branch 0 taken 82174 times.
✓ Branch 1 taken 104 times.
 82278 if (entry->expiry >= now)
882 82174 break;
883
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 entries_.PopFront();
884 104 statistics_.num_remove++;
885 }
886 82356 statistics_.num_prune++;
887 82356 }
888
889 pthread_mutex_t *lock_;
890 unsigned version_;
891 Statistics statistics_;
892 bool is_active_;
893 BigQueue<Entry> entries_;
894
895 int pipe_terminate_[2];
896 int cleaning_interval_ms_;
897 pthread_t thread_cleaner_;
898 }; // class DentryTracker
899
900 /**
901 * Tracks the content hash associated to inodes of regular files whose content
902 * may be in the page cache. It is used in cvmfs_open() and cvmfs_close().
903 */
904 class PageCacheTracker {
905 private:
906 struct Entry {
907 13575 Entry() : nopen(0), idx_stat(-1) { }
908 Entry(int32_t n, int32_t i, const shash::Any &h)
909 : nopen(n), idx_stat(i), hash(h) { }
910 /**
911 * Reference counter for currently open files with a given inode. If the
912 * sign bit is set, the entry is in the transition phase from one hash to
913 * another. The sign will be cleared on Close() in this case.
914 */
915 int32_t nopen;
916 /**
917 * Points into the list of stat structs; >= 0 only for open files.
918 */
919 int32_t idx_stat;
920 /**
921 * The content hash of the data stored in the page cache. For chunked files,
922 * hash contains an artificial hash over all the chunk hash values.
923 */
924 shash::Any hash;
925 };
926
927 public:
928 /**
929 * In the fuse file handle, use bit 62 to indicate that the file was opened
930 * with a direct I/O setting and cvmfs_release() should not call Close().
931 * Note that the sign bit (bit 63) indicates chunked files.
932 */
933 static const unsigned int kBitDirectIo = 62;
934
935 /**
936 * Instruct cvmfs_open() on how to handle the page cache.
937 */
938 struct OpenDirectives {
939 /**
940 * Flush the page cache; logically, the flush takes place some time between
941 * cvmfs_open() and cvmfs_close(). That's important in case we have two
942 * open() calls on stale page cache data.
943 */
944 bool keep_cache;
945 /**
946 * Don't use the page cache at all (neither write nor read). If this is set
947 * on cvmfs_open(), don't call Close() on cvmfs_close().
948 * Direct I/O prevents shared mmap on the file. Private mmap, however,
949 * which includes loading binaries, still works.
950 */
951 bool direct_io;
952
953 // Defaults to the old (pre v2.10) behavior: always flush the cache, never
954 // use direct I/O.
955 420 OpenDirectives() : keep_cache(false), direct_io(false) { }
956
957 ✗ OpenDirectives(bool k, bool d) : keep_cache(k), direct_io(d) { }
958 };
959
960 /**
961 * To avoid taking the PageCacheTracker mutex multiple times, the
962 * fuse forget_multi callback evicts inodes through this RAII object.
963 * Copy and assign operator should be deleted but that would require
964 * all compilers to use RVO. TODO(jblomer): fix with C++11
965 */
966 class EvictRaii {
967 public:
968 explicit EvictRaii(PageCacheTracker *t);
969 ~EvictRaii();
970 void Evict(uint64_t inode);
971
972 private:
973 PageCacheTracker *tracker_;
974 };
975
976 // Cannot be moved to the statistics manager because it has to survive
977 // reloads. Added manually in the fuse module initialization and in talk.cc.
978 struct Statistics {
979 612 Statistics()
980 612 : n_insert(0)
981 612 , n_remove(0)
982 612 , n_open_direct(0)
983 612 , n_open_flush(0)
984 612 , n_open_cached(0) { }
985 uint64_t n_insert;
986 uint64_t n_remove;
987 uint64_t n_open_direct;
988 uint64_t n_open_flush;
989 uint64_t n_open_cached;
990 };
991 ✗ Statistics GetStatistics() { return statistics_; }
992
993 PageCacheTracker();
994 explicit PageCacheTracker(const PageCacheTracker &other);
995 PageCacheTracker &operator=(const PageCacheTracker &other);
996 ~PageCacheTracker();
997
998 OpenDirectives Open(uint64_t inode, const shash::Any &hash,
999 const struct stat &info);
1000 /**
1001 * Forced direct I/O open. Used when the corresponding flag is set in the
1002 * file catalogs. In this case, we don't need to track the inode.
1003 */
1004 OpenDirectives OpenDirect();
1005 void Close(uint64_t inode);
1006
1007 68 bool GetInfoIfOpen(uint64_t inode, shash::Any *hash, struct stat *info) {
1008 68 const MutexLockGuard guard(lock_);
1009
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 Entry entry;
1010
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 const bool retval = map_.Lookup(inode, &entry);
1011
3/4
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 34 times.
 68 if (retval && (entry.nopen != 0)) {
1012
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34 times.
 34 assert(entry.idx_stat >= 0);
1013 34 *hash = entry.hash;
1014
1/2
✓ Branch 0 taken 34 times.
✗ Branch 1 not taken.
 34 if (info != NULL)
1015
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 *info = stat_store_.Get(entry.idx_stat);
1016 34 return true;
1017 }
1018 34 return false;
1019 68 }
1020
1021 /**
1022 * Checks if the dirent's inode is registered in the page cache tracker and
1023 * if
1024 * - it is currently open and has a different content than dirent
1025 * - it has been previously found stale (no matter if now open or not)
1026 */
1027 ✗ bool IsStale(const catalog::DirectoryEntry &dirent) {
1028 ✗ Entry entry;
1029 ✗ const MutexLockGuard guard(lock_);
1030
1031 ✗ const bool retval = map_.Lookup(dirent.inode(), &entry);
1032 ✗ if (!retval)
1033 ✗ return false;
1034 ✗ if (entry.hash.IsNull()) {
1035 // A previous call to IsStale() returned true (see below)
1036 ✗ return true;
1037 }
1038 ✗ if (entry.nopen == 0)
1039 ✗ return false;
1040 ✗ if (entry.hash == dirent.checksum())
1041 ✗ return false;
1042
1043 ✗ bool is_stale = true;
1044 ✗ if (dirent.IsChunkedFile()) {
1045 // Shortcut for chunked files: go by last modified timestamp
1046 ✗ is_stale = stat_store_.Get(entry.idx_stat).st_mtime != dirent.mtime();
1047 }
1048 ✗ if (is_stale) {
1049 // We mark that inode as "stale" by setting its hash to NULL.
1050 // When we check next time IsStale(), it is returned stale even
1051 // if it is not open.
1052 // The call to GetInfoIfOpen() will from now on return the null hash.
1053 // That works, the caller will still assume that the version in the
1054 // page cache tracker is different from any inode in the catalogs.
1055 ✗ entry.hash = shash::Any();
1056 ✗ map_.Insert(dirent.inode(), entry);
1057 }
1058 ✗ return is_stale;
1059 }
1060
1061 70 EvictRaii GetEvictRaii() { return EvictRaii(this); }
1062
1063 // Used in RestoreState to prevent using the page cache tracker from a
1064 // previous version after hotpatch
1065 36 void Disable() { is_active_ = false; }
1066
1067 private:
1068 static const unsigned kVersion = 0;
1069
1070 void InitLock();
1071 void CopyFrom(const PageCacheTracker &other);
1072
1073 pthread_mutex_t *lock_;
1074 unsigned version_;
1075 /**
1076 * The page cache tracker only works correctly if it is used from the start
1077 * of the mount. If the instance is hot-patched from a previous version, the
1078 * page cache tracker remains turned off.
1079 */
1080 bool is_active_;
1081 Statistics statistics_;
1082 SmallHashDynamic<uint64_t, Entry> map_;
1083 StatStore stat_store_;
1084 };
1085
1086
1087 } // namespace glue
1088
1089 #endif // CVMFS_GLUE_BUFFER_H_
1090