CernVM-FS  2.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
malloc_arena.h
Go to the documentation of this file.
1 
5 #ifndef CVMFS_MALLOC_ARENA_H_
6 #define CVMFS_MALLOC_ARENA_H_
7 
8 #include <inttypes.h>
9 #include <stdint.h>
10 
11 #include <cassert>
12 #include <new>
13 
14 // TODO(jblomer): the arena size could be a template parameter. In order to
15 // reduce code duplication, all functions not requiring the arena size could be
16 // moved to a base class.
17 
66 class MallocArena {
67  public:
72  static const int kMinBlockSize = 24;
73 
77  static inline MallocArena *GetMallocArena(void *ptr, unsigned arena_size) {
78  // NOLINTNEXTLINE(performance-no-int-to-ptr)
79  void *arena = reinterpret_cast<void *>(
80  uintptr_t(ptr) & ~(uintptr_t(arena_size) - uintptr_t(1)));
81  return *reinterpret_cast<MallocArena **>(arena);
82  }
83 
84  explicit MallocArena(unsigned arena_size);
85  static MallocArena *CreateInitialized(unsigned arena_size,
86  unsigned char pattern);
87  ~MallocArena();
88 
89  void *Malloc(const uint32_t size);
90  void Free(void *ptr);
91  inline bool Contains(void *ptr) const {
92  return GetMallocArena(ptr, arena_size_) == this;
93  }
94  uint32_t GetSize(void *ptr) const;
95  bool IsEmpty() const { return no_reserved_ == 0; }
96 
97  private:
98  static const char kTagAvail = 0;
99  static const char kTagReserved = 1;
100 
105  struct AvailBlockCtl {
106  AvailBlockCtl *GetNextPtr(char *base) {
107  return reinterpret_cast<AvailBlockCtl *>(base + link_next);
108  }
109  AvailBlockCtl *GetPrevPtr(char *base) {
110  return reinterpret_cast<AvailBlockCtl *>(base + link_prev);
111  }
112  int32_t ConvertToLink(char *base) {
113  return static_cast<int>(reinterpret_cast<char *>(this) - base);
114  }
115  void ShrinkTo(int32_t smaller_size) {
116  size = smaller_size;
117  new (AvailBlockTag::GetTagLocation(this)) AvailBlockTag(smaller_size);
118  }
119  int32_t size; // always positive
120  int32_t link_next; // offset in the arena; saves 4 bytes on 64bit archs
121  int32_t link_prev; // offset in the arena; saves 4 bytes on 64bit archs
122  };
123 
127  struct AvailBlockTag {
128  explicit AvailBlockTag(int32_t s) : size(s), tag(kTagAvail) { }
129  static void *GetTagLocation(AvailBlockCtl *block) {
130  return
131  reinterpret_cast<char *>(block) + block->size - sizeof(AvailBlockTag);
132  }
133  int32_t size;
134  char padding[3];
135  char tag;
136  };
137 
143  public:
144  explicit ReservedBlockCtl(int32_t s) : size_(-s) {
145  char *base = reinterpret_cast<char *>(this);
146  *(base + s - 1) = kTagReserved;
147  }
148  int32_t size() const { assert(size_ <= 0); return -size_; }
149 
150  private:
151  int32_t size_; // always negative
152  };
153 
154  void UnlinkAvailBlock(AvailBlockCtl *block);
155  void EnqueueAvailBlock(AvailBlockCtl *block);
156  AvailBlockCtl *FindAvailBlock(const int32_t block_size);
157  void *ReserveBlock(AvailBlockCtl *block, int32_t block_size);
158 
166  char *arena_;
167 
175  uint32_t no_reserved_;
176  unsigned arena_size_;
177 }; // class MallocArena
178 
179 #endif // CVMFS_MALLOC_ARENA_H_
MallocArena(unsigned arena_size)
AvailBlockCtl * FindAvailBlock(const int32_t block_size)
Definition: malloc_arena.cc:24
static MallocArena * GetMallocArena(void *ptr, unsigned arena_size)
Definition: malloc_arena.h:77
void ShrinkTo(int32_t smaller_size)
Definition: malloc_arena.h:115
AvailBlockCtl * rover_
The free block where the next search starts.
Definition: malloc_arena.h:174
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
static const char kTagAvail
Definition: malloc_arena.h:98
unsigned arena_size_
Definition: malloc_arena.h:176
AvailBlockCtl * GetPrevPtr(char *base)
Definition: malloc_arena.h:109
void Free(void *ptr)
Definition: malloc_arena.cc:55
bool IsEmpty() const
Definition: malloc_arena.h:95
bool Contains(void *ptr) const
Definition: malloc_arena.h:91
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
uint32_t no_reserved_
Definition: malloc_arena.h:175