GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/malloc_heap.h
Date: 2025-02-02 02:34:22
Exec Total Coverage
Lines: 16 18 88.9%
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 53092 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 3 inline uint64_t num_blocks() { return num_blocks_; }
58 3 inline uint64_t used_bytes() { return gauge_; }
59 3 inline uint64_t stored_bytes() { return stored_; }
60 5 inline uint64_t compacted_bytes() {
61 5 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 106126 explicit Tag(int64_t s) : size(s) { }
82 316290 inline uint64_t GetSize() {
83
2/2
✓ Branch 0 taken 209105 times.
✓ Branch 1 taken 107185 times.
 316290 if (size < 0) return -size;
84 107185 return size;
85 }
86 264282 inline bool IsFree() { return size < 0; }
87 159189 inline Tag *JumpToNext() {
88 return reinterpret_cast<Tag *>(
89 159189 reinterpret_cast<unsigned char *>(this) + sizeof(Tag) + GetSize());
90 }
91 159276 inline unsigned char *GetBlock() {
92 159276 return reinterpret_cast<unsigned char *>(this) + sizeof(Tag);
93 }
94 /**
95 * Positive for reserved blocks, negative for free blocks.
96 */
97 int64_t size;
98 };
99
100 /**
101 * Invoked when a block is moved during compact.
102 */
103 CallbackPtr callback_ptr_;
104 /**
105 * Total size of mmap'd arena.
106 */
107 uint64_t capacity_;
108 /**
109 * End of the area of reserved blocks, used for the next allocation.
110 */
111 uint64_t gauge_;
112 /**
113 * Sum of the non-free block sizes.
114 */
115 uint64_t stored_;
116 /**
117 * Number of reserved blocks
118 */
119 uint64_t num_blocks_;
120 /**
121 * The big mmap'd memory block used to serve allocation requests.
122 */
123 unsigned char *heap_;
124 }; // class MallocHeap
125
126 #endif // CVMFS_MALLOC_HEAP_H_
127