CernVM-FS  2.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
malloc_arena.cc
Go to the documentation of this file.
1 
5 #define __STDC_FORMAT_MACROS
6 
7 #include "cvmfs_config.h"
8 #include "malloc_arena.h"
9 
10 #include <cassert>
11 #include <cstddef>
12 #include <cstring>
13 #include <new>
14 
15 #include "smalloc.h"
16 
17 using namespace std; // NOLINT
18 
19 
25  const int32_t block_size)
26 {
27  bool wrapped = false;
28  // Generally: p = LINK(q)
29  AvailBlockCtl *q = rover_;
30  AvailBlockCtl *p;
31  do {
32  p = q->GetNextPtr(arena_);
33  if (p->size >= block_size) {
34  rover_ = p->GetNextPtr(arena_);
35  return p;
36  }
37  if (p == head_avail_) {
38  if (wrapped)
39  return NULL;
40  wrapped = true;
41  }
42  q = p;
43  } while (true);
44 }
45 
46 
55 void MallocArena::Free(void *ptr) {
56  assert(Contains(ptr));
57 
58  no_reserved_--;
59 
60  ReservedBlockCtl *block_ctl = reinterpret_cast<ReservedBlockCtl *>(
61  reinterpret_cast<char *>(ptr) - sizeof(ReservedBlockCtl));
62  char prior_tag = *(reinterpret_cast<char *>(block_ctl) - 1);
63  assert((prior_tag == kTagAvail) || (prior_tag == kTagReserved));
64 
65  int32_t new_size = block_ctl->size();
66  assert(new_size > 0);
67  AvailBlockCtl *new_avail = reinterpret_cast<AvailBlockCtl *>(block_ctl);
68 
69  if (prior_tag == kTagAvail) {
70  // Merge with block before and remove the block from the list
71  int32_t prior_size = reinterpret_cast<AvailBlockTag *>(
72  reinterpret_cast<char *>(block_ctl) - sizeof(AvailBlockTag))->size;
73  assert(prior_size > 0);
74  new_size += prior_size;
75  new_avail = reinterpret_cast<AvailBlockCtl *>(
76  reinterpret_cast<char *>(block_ctl) - prior_size);
77  // new_avail points now to the prior block
78  UnlinkAvailBlock(new_avail);
79  if (rover_ == new_avail)
80  rover_ = head_avail_;
81  }
82 
83  int32_t succ_size = *reinterpret_cast<int32_t *>(
84  reinterpret_cast<char *>(new_avail) + new_size);
85  if (succ_size >= 0) {
86  // Merge with succeeding block and remove the block from the list
87  AvailBlockCtl *succ_avail = reinterpret_cast<AvailBlockCtl *>(
88  reinterpret_cast<char *>(new_avail) + new_size);
89  UnlinkAvailBlock(succ_avail);
90  new_size += succ_size;
91  if (rover_ == succ_avail)
92  rover_ = head_avail_;
93  }
94 
95  // Set new free block's boundaries
96  new_avail->size = new_size;
97  new (AvailBlockTag::GetTagLocation(new_avail)) AvailBlockTag(new_size);
98 
99  EnqueueAvailBlock(new_avail);
100 }
101 
102 
107  AvailBlockCtl *next = head_avail_;
108  AvailBlockCtl *prev = head_avail_->GetPrevPtr(arena_);
109  next->link_prev = block->ConvertToLink(arena_);
110  prev->link_next = block->ConvertToLink(arena_);
111  block->link_next = head_avail_->ConvertToLink(arena_);
112  block->link_prev = prev->ConvertToLink(arena_);
113 }
114 
115 
120 uint32_t MallocArena::GetSize(void *ptr) const {
121  assert(Contains(ptr));
122 
123  ReservedBlockCtl *block_ctl = reinterpret_cast<ReservedBlockCtl *>(
124  reinterpret_cast<char *>(ptr) - sizeof(ReservedBlockCtl));
125  int32_t size = block_ctl->size();
126  assert(size > 1);
127  return size - sizeof(ReservedBlockCtl) - 1;
128 }
129 
130 
137 void *MallocArena::Malloc(const uint32_t size) {
138  assert(size > 0);
139 
140  // Control word first, block type tag last
141  int32_t total_size = sizeof(ReservedBlockCtl) + size + 1;
142  total_size = RoundUp8(total_size);
143  if (total_size < kMinBlockSize)
144  total_size = kMinBlockSize;
145 
146  AvailBlockCtl *p = FindAvailBlock(total_size);
147  if (p == NULL)
148  return NULL;
149 
150  no_reserved_++;
151  return ReserveBlock(p, total_size);
152 }
153 
154 
161 MallocArena::MallocArena(unsigned arena_size)
162  : arena_(reinterpret_cast<char *>(sxmmap_align(arena_size)))
163  , head_avail_(reinterpret_cast<AvailBlockCtl *>(arena_ + sizeof(uint64_t)))
164  , rover_(head_avail_)
165  , no_reserved_(0)
166  , arena_size_(arena_size)
167 {
168  assert(arena_size_ > 0);
169  assert((arena_size_ % (2 * 1024 * 1024)) == 0); // Multiple of 2MB
170  assert(arena_size_ <= (512 * 1024 * 1024)); // <= 512MB
171 
172  const unsigned char padding = 7;
173  // Size of the initial free block: everything minus arena boundaries
174  int32_t usable_size = arena_size_ -
175  (sizeof(uint64_t) + sizeof(AvailBlockCtl) + padding + 1 + sizeof(int32_t));
176  assert((usable_size % 8) == 0);
177 
178  // First 8 bytes of arena: this pointer (occupies only 4 bytes on 32bit
179  // architectures, in which case the second 4 bytes are unused.)
180  *reinterpret_cast<MallocArena **>(arena_) = this;
181 
182  // The initial large free block
183  AvailBlockCtl *free_block =
184  new (arena_ + sizeof(uint64_t) + sizeof(AvailBlockCtl) + padding + 1)
185  AvailBlockCtl();
186  free_block->size = usable_size;
187  free_block->link_next = free_block->link_prev =
189  new (AvailBlockTag::GetTagLocation(free_block)) AvailBlockTag(usable_size);
190 
191  head_avail_->size = 0;
193  free_block->ConvertToLink(arena_);
194 
195  // Prevent succeeding blocks from merging
196  *(reinterpret_cast<char *>(free_block) - 1) = kTagReserved;
197  // Final tag: reserved block marker
198  *reinterpret_cast<int32_t *>(arena_ + arena_size_ - sizeof(int32_t)) = -1;
199 }
200 
201 
207  unsigned arena_size,
208  unsigned char pattern)
209 {
210  MallocArena *result = new MallocArena(arena_size);
211  // At this point, there is one big free block linked to by head_avail_
212  AvailBlockCtl *free_block = result->head_avail_->GetNextPtr(result->arena_);
213  assert(free_block != result->head_avail_);
214  assert(free_block->size > 0);
215  // Strip control information at both ends of the block
216  int usable_size = free_block->size -
217  (sizeof(AvailBlockCtl) + sizeof(AvailBlockTag));
218  assert(usable_size > 0);
219  memset(free_block + 1, pattern, usable_size);
220  return result;
221 }
222 
223 
225  sxunmap(arena_, arena_size_);
226 }
227 
228 
235  AvailBlockCtl *block,
236  int32_t block_size)
237 {
238  assert(block->size >= block_size);
239 
240  int32_t remaining_size = block->size - block_size;
241  // Avoid creation of very small blocks
242  if (remaining_size < kMinBlockSize) {
243  block_size += remaining_size;
244  remaining_size = 0;
245  }
246 
247  // Update the list of available blocks
248  if (remaining_size == 0) {
249  // Remove free block p from the list of available blocks
250  UnlinkAvailBlock(block);
251  } else {
252  block->ShrinkTo(remaining_size);
253  }
254 
255  // Place the new allocation, which also sets the block type tag at the end
256  char *new_block = reinterpret_cast<char *>(block) + remaining_size;
257  new (new_block) ReservedBlockCtl(block_size);
258  return new_block + sizeof(ReservedBlockCtl);
259 }
260 
261 
268  AvailBlockCtl *next = block->GetNextPtr(arena_);
269  AvailBlockCtl *prev = block->GetPrevPtr(arena_);
270  prev->link_next = block->link_next;
271  next->link_prev = block->link_prev;
272 }
MallocArena(unsigned arena_size)
AvailBlockCtl * FindAvailBlock(const int32_t block_size)
Definition: malloc_arena.cc:24
void ShrinkTo(int32_t smaller_size)
Definition: malloc_arena.h:115
static void * GetTagLocation(AvailBlockCtl *block)
Definition: malloc_arena.h:129
assert((mem||(size==0))&&"Out Of Memory")
void UnlinkAvailBlock(AvailBlockCtl *block)
int32_t ConvertToLink(char *base)
Definition: malloc_arena.h:112
static const int kMinBlockSize
Definition: malloc_arena.h:72
void * ReserveBlock(AvailBlockCtl *block, int32_t block_size)
AvailBlockCtl * GetNextPtr(char *base)
Definition: malloc_arena.h:106
void EnqueueAvailBlock(AvailBlockCtl *block)
static const char kTagReserved
Definition: malloc_arena.h:99
static MallocArena * CreateInitialized(unsigned arena_size, unsigned char pattern)
AvailBlockCtl * head_avail_
Definition: malloc_arena.h:173
unsigned arena_size_
Definition: malloc_arena.h:176
static uint64_t RoundUp8(const uint64_t size)
Definition: smalloc.h:37
AvailBlockCtl * GetPrevPtr(char *base)
Definition: malloc_arena.h:109
void Free(void *ptr)
Definition: malloc_arena.cc:55
void * Malloc(const uint32_t size)
char * arena_
The memory block.
Definition: malloc_arena.h:166
uint32_t GetSize(void *ptr) const
static void size_t size
Definition: smalloc.h:47