| 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 |
|
53172 |
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 |
|
316288 |
inline uint64_t GetSize() { |
| 83 |
2/2
✓ Branch 0 taken 208942 times.
✓ Branch 1 taken 107346 times.
|
316288 |
if (size < 0) return -size; |
| 84 |
|
107346 |
return size; |
| 85 |
|
|
} |
| 86 |
|
264361 |
inline bool IsFree() { return size < 0; } |
| 87 |
|
159269 |
inline Tag *JumpToNext() { |
| 88 |
|
|
return reinterpret_cast<Tag *>( |
| 89 |
|
159269 |
reinterpret_cast<unsigned char *>(this) + sizeof(Tag) + GetSize()); |
| 90 |
|
|
} |
| 91 |
|
159516 |
inline unsigned char *GetBlock() { |
| 92 |
|
159516 |
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 |
|
|
|