GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/malloc_heap.h
Date: 2025-06-22 02:36:02
Exec Total Coverage
Lines: 17 19 89.5%
Branches: 2 2 100.0%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 */
4
5 #ifndef CVMFS_MALLOC_HEAP_H_
6 #define CVMFS_MALLOC_HEAP_H_
7
8 #include <inttypes.h>
9 #include <stdint.h>
10
11 #include <cstdlib>
12
13 #include "util/async.h"
14
15 /**
16 * Fills an ever-growing heap. Free calls simply mark a block as free but
17 * allocation continues to take place at the top of the heap. Hence Realloc()
18 * is inefficient. For the common pattern of doubling a buffer with realloc,
19 * twice the final buffer size is required.
20 *
21 * The allocator is copying and can collect garbage. In order to react on the
22 * move of a block, a callback can be registered that gets called with the new
23 * pointer address. The user of the MallocHeap has to make sure to identify
24 * any block based on the first bytes. Therefore, allocation requires these
25 * first bytes, a user-defined "header" if you will.
26 * Note that during a Compact() not even reading from any of the pointers is
27 * allowed!
28 *
29 * MallocHeap is used by the in-memory object cache. The header is the
30 * object's content hash, so the cache manager can identify any block in its
31 * hash table and move the pointers when MallocHeap runs a garbage collection.
32 *
33 * All memory blocks are 8-byte aligned and they have an 8-byte header
34 * containing their size. The size is negative for free blocks.
35 */
36 class MallocHeap {
37 public:
38 struct BlockPtr {
39 BlockPtr() : pointer(NULL) { }
40 106232 explicit BlockPtr(void *p) : pointer(p) { }
41 void *pointer;
42 };
43
44 // Pointer to the callback method invoked for each memory block that gets
45 // compacted.
46 typedef Callbackable<BlockPtr>::CallbackTN *CallbackPtr;
47
48 MallocHeap(uint64_t capacity, CallbackPtr callback_ptr);
49 ~MallocHeap();
50
51 void *Allocate(uint64_t size, void *header, unsigned header_size);
52 void *Expand(void *block, uint64_t new_size);
53 void MarkFree(void *block);
54 uint64_t GetSize(void *block);
55 void Compact();
56
57 6 inline uint64_t num_blocks() { return num_blocks_; }
58 6 inline uint64_t used_bytes() { return gauge_; }
59 6 inline uint64_t stored_bytes() { return stored_; }
60 9 inline uint64_t compacted_bytes() {
61 9 return stored_ + num_blocks_ * sizeof(Tag);
62 }
63 1 inline uint64_t capacity() { return capacity_; }
64 ✗ inline double utilization() {
65 ✗ return static_cast<double>(stored_) / static_cast<double>(gauge_);
66 }
67 bool HasSpaceFor(uint64_t nbytes);
68
69 private:
70 /**
71 * Minimum number of bytes of the heap.
72 */
73 static const unsigned kMinCapacity = 1024;
74
75 /**
76 * Prepends every block. The size does not include the size of the tag. The
77 * size of the Tag structure has to be a multiple of 8 for alignment.
78 */
79 struct Tag {
80 Tag() : size(0) { }
81 212250 explicit Tag(int64_t s) : size(s) { }
82 632576 inline uint64_t GetSize() {
83
2/2
✓ Branch 0 taken 418108 times.
✓ Branch 1 taken 214468 times.
 632576 if (size < 0)
84 418108 return -size;
85 214468 return size;
86 }
87 528610 inline bool IsFree() { return size < 0; }
88 318426 inline Tag *JumpToNext() {
89 return reinterpret_cast<Tag *>(reinterpret_cast<unsigned char *>(this)
90 318426 + sizeof(Tag) + GetSize());
91 }
92 318696 inline unsigned char *GetBlock() {
93 318696 return reinterpret_cast<unsigned char *>(this) + sizeof(Tag);
94 }
95 /**
96 * Positive for reserved blocks, negative for free blocks.
97 */
98 int64_t size;
99 };
100
101 /**
102 * Invoked when a block is moved during compact.
103 */
104 CallbackPtr callback_ptr_;
105 /**
106 * Total size of mmap'd arena.
107 */
108 uint64_t capacity_;
109 /**
110 * End of the area of reserved blocks, used for the next allocation.
111 */
112 uint64_t gauge_;
113 /**
114 * Sum of the non-free block sizes.
115 */
116 uint64_t stored_;
117 /**
118 * Number of reserved blocks
119 */
120 uint64_t num_blocks_;
121 /**
122 * The big mmap'd memory block used to serve allocation requests.
123 */
124 unsigned char *heap_;
125 }; // class MallocHeap
126
127 #endif // CVMFS_MALLOC_HEAP_H_
128