GCC Code Coverage Report
Directory: cvmfs/ Exec Total Coverage
File: cvmfs/malloc_heap.h Lines: 16 18 88.9 %
Date: 2019-02-03 02:48:13 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
53365
    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
316282
    inline uint64_t GetSize() {
83
316282
      if (size < 0) return -size;
84
107735
      return size;
85
    }
86
264551
    inline bool IsFree() { return size < 0; }
87
159462
    inline Tag *JumpToNext() {
88
      return reinterpret_cast<Tag *>(
89
159462
        reinterpret_cast<unsigned char *>(this) + sizeof(Tag) + GetSize());
90
    }
91
160095
    inline unsigned char *GetBlock() {
92
160095
      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_