malloc_arena.h

Go to the documentation of this file.

#ifndef CVMFS_MALLOC_ARENA_H_
#define CVMFS_MALLOC_ARENA_H_

#include <inttypes.h>
#include <stdint.h>

#include <cassert>
#include <new>

// TODO(jblomer): the arena size could be a template parameter.  In order to
// reduce code duplication, all functions not requiring the arena size could be
// moved to a base class.

class MallocArena {
 public:
  static const int kMinBlockSize = 24;

  static inline MallocArena *GetMallocArena(void *ptr, unsigned arena_size) {
    // NOLINTNEXTLINE(performance-no-int-to-ptr)
    void *arena = reinterpret_cast<void *>(
      uintptr_t(ptr) & ~(uintptr_t(arena_size) - uintptr_t(1)));
    return *reinterpret_cast<MallocArena **>(arena);
  }

  explicit MallocArena(unsigned arena_size);
  static MallocArena *CreateInitialized(unsigned arena_size,
                                        unsigned char pattern);
  ~MallocArena();

  void *Malloc(const uint32_t size);
  void Free(void *ptr);
  inline bool Contains(void *ptr) const {
    return GetMallocArena(ptr, arena_size_) == this;
  }
  uint32_t GetSize(void *ptr) const;
  bool IsEmpty() const { return no_reserved_ == 0; }

 private:
  static const char kTagAvail = 0;
  static const char kTagReserved = 1;

  struct AvailBlockCtl {
    AvailBlockCtl *GetNextPtr(char *base) {
      return reinterpret_cast<AvailBlockCtl *>(base + link_next);
    }
    AvailBlockCtl *GetPrevPtr(char *base) {
      return reinterpret_cast<AvailBlockCtl *>(base + link_prev);
    }
    int32_t ConvertToLink(char *base) {
      return static_cast<int>(reinterpret_cast<char *>(this) - base);
    }
    void ShrinkTo(int32_t smaller_size) {
      size = smaller_size;
      new (AvailBlockTag::GetTagLocation(this)) AvailBlockTag(smaller_size);
    }
    int32_t size;  // always positive
    int32_t link_next;  // offset in the arena; saves 4 bytes on 64bit archs
    int32_t link_prev;  // offset in the arena; saves 4 bytes on 64bit archs
  };

  struct AvailBlockTag {
    explicit AvailBlockTag(int32_t s) : size(s), tag(kTagAvail) { }
    static void *GetTagLocation(AvailBlockCtl *block) {
      return
        reinterpret_cast<char *>(block) + block->size - sizeof(AvailBlockTag);
    }
    int32_t size;
    char padding[3];
    char tag;
  };

  struct ReservedBlockCtl {
   public:
    explicit ReservedBlockCtl(int32_t s) : size_(-s) {
      char *base = reinterpret_cast<char *>(this);
      *(base + s - 1) = kTagReserved;
    }
    int32_t size() const { assert(size_ <= 0);  return -size_; }

   private:
    int32_t size_;  // always negative
  };

  void UnlinkAvailBlock(AvailBlockCtl *block);
  void EnqueueAvailBlock(AvailBlockCtl *block);
  AvailBlockCtl *FindAvailBlock(const int32_t block_size);
  void *ReserveBlock(AvailBlockCtl *block, int32_t block_size);

  char *arena_;  

  AvailBlockCtl *head_avail_;
  AvailBlockCtl *rover_;  
  uint32_t no_reserved_;
  unsigned arena_size_;
};  // class MallocArena

#endif  // CVMFS_MALLOC_ARENA_H_