GCC Code Coverage Report

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