GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/malloc_arena.cc
Date: 2026-08-16 02:40:26
Exec Total Coverage
Lines: 121 121 100.0%
Branches: 39 54 72.2%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 */
4
5 #include "malloc_arena.h"
6
7 #include <cassert>
8 #include <cstddef>
9 #include <cstring>
10 #include <new>
11
12 #include "util/smalloc.h"
13
14 using namespace std; // NOLINT
15
16
17 /**
18 * Walks through the free list starting at rover_ and looks for the first block
19 * larger than block_size. Returns NULL if no such block exists.
20 */
21 282007123 MallocArena::AvailBlockCtl *MallocArena::FindAvailBlock(
22 const int32_t block_size) {
23 282007123 bool wrapped = false;
24 // Generally: p = LINK(q)
25 282007123 AvailBlockCtl *q = rover_;
26 AvailBlockCtl *p;
27 do {
28 99331221901 p = q->GetNextPtr(arena_);
29
2/2
✓ Branch 0 taken 209958323 times.
✓ Branch 1 taken 99121263578 times.
 99331221901 if (p->size >= block_size) {
30 209958323 rover_ = p->GetNextPtr(arena_);
31 209958323 return p;
32 }
33
2/2
✓ Branch 0 taken 154105123 times.
✓ Branch 1 taken 98967158455 times.
 99121263578 if (p == head_avail_) {
34
2/2
✓ Branch 0 taken 72048800 times.
✓ Branch 1 taken 82056323 times.
 154105123 if (wrapped)
35 72048800 return NULL;
36 82056323 wrapped = true;
37 }
38 99049214778 q = p;
39 } while (true);
40 }
41
42
43 /**
44 * Creates a free block at the place of the reserved block ptr points into.
45 * The free block might need to be merged with adjacent lower and/or upper
46 * blocks. In these cases, the corresponding blocks are removed from the list
47 * of available blocks. Every allocated block has a predecessor and a
48 * successor in the arena. The newly created free block is added to the end of
49 * the list of available blocks.
50 */
51 208503256 void MallocArena::Free(void *ptr) {
52
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 208503256 times.
 208503256 assert(Contains(ptr));
53
54 208503256 no_reserved_--;
55
56 208503256 ReservedBlockCtl *block_ctl = reinterpret_cast<ReservedBlockCtl *>(
57 reinterpret_cast<char *>(ptr) - sizeof(ReservedBlockCtl));
58 208503256 const char prior_tag = *(reinterpret_cast<char *>(block_ctl) - 1);
59
3/4
✓ Branch 0 taken 128911992 times.
✓ Branch 1 taken 79591264 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 128911992 times.
 208503256 assert((prior_tag == kTagAvail) || (prior_tag == kTagReserved));
60
61 208503256 int32_t new_size = block_ctl->size();
62
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 208503256 times.
 208503256 assert(new_size > 0);
63 208503256 AvailBlockCtl *new_avail = reinterpret_cast<AvailBlockCtl *>(block_ctl);
64
65
2/2
✓ Branch 0 taken 79591264 times.
✓ Branch 1 taken 128911992 times.
 208503256 if (prior_tag == kTagAvail) {
66 // Merge with block before and remove the block from the list
67 79591264 const int32_t prior_size = reinterpret_cast<AvailBlockTag *>(
68 reinterpret_cast<char *>(block_ctl)
69 - sizeof(AvailBlockTag))
70 ->size;
71
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 79591264 times.
 79591264 assert(prior_size > 0);
72 79591264 new_size += prior_size;
73 79591264 new_avail = reinterpret_cast<AvailBlockCtl *>(
74 79591264 reinterpret_cast<char *>(block_ctl) - prior_size);
75 // new_avail points now to the prior block
76 79591264 UnlinkAvailBlock(new_avail);
77
2/2
✓ Branch 0 taken 951921 times.
✓ Branch 1 taken 78639343 times.
 79591264 if (rover_ == new_avail)
78 951921 rover_ = head_avail_;
79 }
80
81 208503256 const int32_t succ_size = *reinterpret_cast<int32_t *>(
82 208503256 reinterpret_cast<char *>(new_avail) + new_size);
83
2/2
✓ Branch 0 taken 118790054 times.
✓ Branch 1 taken 89713202 times.
 208503256 if (succ_size >= 0) {
84 // Merge with succeeding block and remove the block from the list
85 118790054 AvailBlockCtl *succ_avail = reinterpret_cast<AvailBlockCtl *>(
86 118790054 reinterpret_cast<char *>(new_avail) + new_size);
87 118790054 UnlinkAvailBlock(succ_avail);
88 118790054 new_size += succ_size;
89
2/2
✓ Branch 0 taken 1566616 times.
✓ Branch 1 taken 117223438 times.
 118790054 if (rover_ == succ_avail)
90 1566616 rover_ = head_avail_;
91 }
92
93 // Set new free block's boundaries
94 208503256 new_avail->size = new_size;
95 208503256 new (AvailBlockTag::GetTagLocation(new_avail)) AvailBlockTag(new_size);
96
97 208503256 EnqueueAvailBlock(new_avail);
98 208503256 }
99
100
101 /**
102 * Inserts an available block at the end of the free list.
103 */
104 208503256 void MallocArena::EnqueueAvailBlock(AvailBlockCtl *block) {
105 208503256 AvailBlockCtl *next = head_avail_;
106 208503256 AvailBlockCtl *prev = head_avail_->GetPrevPtr(arena_);
107 208503256 next->link_prev = block->ConvertToLink(arena_);
108 208503256 prev->link_next = block->ConvertToLink(arena_);
109 208503256 block->link_next = head_avail_->ConvertToLink(arena_);
110 208503256 block->link_prev = prev->ConvertToLink(arena_);
111 208503256 }
112
113
114 /**
115 * The ptr points to the result of Malloc(). The size of the area is stored
116 * a few bytes before ptr.
117 */
118 370418793 uint32_t MallocArena::GetSize(void *ptr) const {
119
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 370418793 times.
 370418793 assert(Contains(ptr));
120
121 370418793 ReservedBlockCtl *block_ctl = reinterpret_cast<ReservedBlockCtl *>(
122 reinterpret_cast<char *>(ptr) - sizeof(ReservedBlockCtl));
123 370418793 const int32_t size = block_ctl->size();
124
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 370418793 times.
 370418793 assert(size > 1);
125 370418793 return size - sizeof(ReservedBlockCtl) - 1;
126 }
127
128
129 /**
130 * Walks the list of available blocks starting from rover and allocates the
131 * first available spot that's large enough. Puts the reserved block at the end
132 * of the available one and, if necessary, removes the available one from the
133 * list of free blocks.
134 */
135 282007123 void *MallocArena::Malloc(const uint32_t size) {
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 282007123 times.
 282007123 assert(size > 0);
137
138 // Control word first, block type tag last
139 282007123 int32_t total_size = sizeof(ReservedBlockCtl) + size + 1;
140 282007123 total_size = RoundUp8(total_size);
141
2/2
✓ Branch 0 taken 1212335 times.
✓ Branch 1 taken 280794788 times.
 282007123 if (total_size < kMinBlockSize)
142 1212335 total_size = kMinBlockSize;
143
144 282007123 AvailBlockCtl *p = FindAvailBlock(total_size);
145
2/2
✓ Branch 0 taken 72048800 times.
✓ Branch 1 taken 209958323 times.
 282007123 if (p == NULL)
146 72048800 return NULL;
147
148 209958323 no_reserved_++;
149 209958323 return ReserveBlock(p, total_size);
150 }
151
152
153 /**
154 * The arena starts with a pointer to this followed by the AvailBlockCtl of
155 * head_avail_, followed by a reserved tag to prevent it from being merged,
156 * followed by a free block spanning the arena until the end tag. The end tag
157 * is a single negative int, which mimics another reserved block.
158 */
159 4735 MallocArena::MallocArena(unsigned arena_size)
160 4735 : arena_(reinterpret_cast<char *>(sxmmap_align(arena_size)))
161 4735 , head_avail_(reinterpret_cast<AvailBlockCtl *>(arena_ + sizeof(uint64_t)))
162 4735 , rover_(head_avail_)
163 4735 , no_reserved_(0)
164 4735 , arena_size_(arena_size) {
165
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4735 times.
 4735 assert(arena_size_ > 0);
166
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4735 times.
 4735 assert((arena_size_ % (2 * 1024 * 1024)) == 0); // Multiple of 2MB
167
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4735 times.
 4735 assert(arena_size_ <= (512 * 1024 * 1024)); // <= 512MB
168
169 4735 const unsigned char padding = 7;
170 // Size of the initial free block: everything minus arena boundaries
171 4735 const int32_t usable_size = arena_size_
172 4735 - (sizeof(uint64_t) + sizeof(AvailBlockCtl)
173 + padding + 1 + sizeof(int32_t));
174
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4735 times.
 4735 assert((usable_size % 8) == 0);
175
176 // First 8 bytes of arena: this pointer (occupies only 4 bytes on 32bit
177 // architectures, in which case the second 4 bytes are unused.)
178 4735 *reinterpret_cast<MallocArena **>(arena_) = this;
179
180 // The initial large free block
181 4735 AvailBlockCtl *free_block = new (arena_ + sizeof(uint64_t)
182 + sizeof(AvailBlockCtl) + padding + 1)
183 4735 AvailBlockCtl();
184 4735 free_block->size = usable_size;
185 4735 free_block->link_next = free_block->link_prev = head_avail_->ConvertToLink(
186 arena_);
187 4735 new (AvailBlockTag::GetTagLocation(free_block)) AvailBlockTag(usable_size);
188
189 4735 head_avail_->size = 0;
190 4735 head_avail_->link_next = head_avail_->link_prev = free_block->ConvertToLink(
191 arena_);
192
193 // Prevent succeeding blocks from merging
194 4735 *(reinterpret_cast<char *>(free_block) - 1) = kTagReserved;
195 // Final tag: reserved block marker
196 4735 *reinterpret_cast<int32_t *>(arena_ + arena_size_ - sizeof(int32_t)) = -1;
197 4735 }
198
199
200 /**
201 * Initializes the arena with repeated copies of the given pattern. Used for
202 * testing.
203 */
204 1 MallocArena *MallocArena::CreateInitialized(unsigned arena_size,
205 unsigned char pattern) {
206 1 MallocArena *result = new MallocArena(arena_size);
207 // At this point, there is one big free block linked to by head_avail_
208 1 AvailBlockCtl *free_block = result->head_avail_->GetNextPtr(result->arena_);
209
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(free_block != result->head_avail_);
210
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(free_block->size > 0);
211 // Strip control information at both ends of the block
212 1 const int usable_size = free_block->size
213 1 - (sizeof(AvailBlockCtl) + sizeof(AvailBlockTag));
214
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(usable_size > 0);
215 1 memset(free_block + 1, pattern, usable_size);
216 1 return result;
217 }
218
219
220 4730 MallocArena::~MallocArena() { sxunmap(arena_, arena_size_); }
221
222
223 /**
224 * Given the free block "block", cuts out a new reserved block of size
225 * block_size at the end of the free block. Returns a pointer usable by the
226 * application.
227 */
228 209958323 void *MallocArena::ReserveBlock(AvailBlockCtl *block, int32_t block_size) {
229
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 209958323 times.
 209958323 assert(block->size >= block_size);
230
231 209958323 int32_t remaining_size = block->size - block_size;
232 // Avoid creation of very small blocks
233
2/2
✓ Branch 0 taken 9619817 times.
✓ Branch 1 taken 200338506 times.
 209958323 if (remaining_size < kMinBlockSize) {
234 9619817 block_size += remaining_size;
235 9619817 remaining_size = 0;
236 }
237
238 // Update the list of available blocks
239
2/2
✓ Branch 0 taken 9619817 times.
✓ Branch 1 taken 200338506 times.
 209958323 if (remaining_size == 0) {
240 // Remove free block p from the list of available blocks
241 9619817 UnlinkAvailBlock(block);
242 } else {
243 200338506 block->ShrinkTo(remaining_size);
244 }
245
246 // Place the new allocation, which also sets the block type tag at the end
247 209958323 char *new_block = reinterpret_cast<char *>(block) + remaining_size;
248 209958323 new (new_block) ReservedBlockCtl(block_size);
249 209958323 return new_block + sizeof(ReservedBlockCtl);
250 }
251
252
253 /**
254 * Removes the given block from the doubly linked free block list. This happens
255 * when two adjacent free blocks are created in Free() and then merged. Or if
256 * a block gets fully used in Malloc().
257 */
258 208001135 void MallocArena::UnlinkAvailBlock(AvailBlockCtl *block) {
259 208001135 AvailBlockCtl *next = block->GetNextPtr(arena_);
260 208001135 AvailBlockCtl *prev = block->GetPrevPtr(arena_);
261 208001135 prev->link_next = block->link_next;
262 208001135 next->link_prev = block->link_prev;
263 208001135 }
264