CernVM-FS  2.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
MallocArena Class Reference

#include <malloc_arena.h>

Collaboration diagram for MallocArena:

Classes

struct  AvailBlockCtl
 
struct  AvailBlockTag
 
struct  ReservedBlockCtl
 

Public Member Functions

 MallocArena (unsigned arena_size)
 
 ~MallocArena ()
 
void * Malloc (const uint32_t size)
 
void Free (void *ptr)
 
bool Contains (void *ptr) const
 
uint32_t GetSize (void *ptr) const
 
bool IsEmpty () const
 

Static Public Member Functions

static MallocArenaGetMallocArena (void *ptr, unsigned arena_size)
 
static MallocArenaCreateInitialized (unsigned arena_size, unsigned char pattern)
 

Static Public Attributes

static const int kMinBlockSize = 24
 

Private Member Functions

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

Private Attributes

char * arena_
 The memory block. More...
 
AvailBlockCtlhead_avail_
 
AvailBlockCtlrover_
 The free block where the next search starts. More...
 
uint32_t no_reserved_
 
unsigned arena_size_
 

Static Private Attributes

static const char kTagAvail = 0
 
static const char kTagReserved = 1
 

Detailed Description

This file is part of the CernVM File System. An mmap'd block of general purpose memory for malloc/free in sqlite. Uses the "boundary-tag system" as described in TAOCP vol 1 section 2.5. Not thread-safe.

Returned pointers are 8-byte aligned. Since a reserved block has a 4 bytes prefix, all reserved blocks must start addresses that end with binary 100. We round up all allocation requests to a multiple of 8. Reserved blocks are always placed at the upper bound of a free block. The first block of the arena is appropriately padded and because the upper bound of the initial large free block is at an address that ends on binary 100, all reserved blocks will be aligned correctly.

The tag layouts are as follows. Size is a signed 4 byte integer, previous and next are 4 byte offsets into the arena, linking to the previous and next free blocks in the list of free blocks.

Available (free) block: Reserved (used) block:

  +--------+--------+                             +--------+--------+

upper | size | 00| upper | | 01| +-----—+-----—+ +-----—+-----—+ | ... | | ... | +--------------—+ +--------------—+ |previous| | | ... | +--------------—+ +--------------—+ lower | size | next | lower | -size | | +-----—+-----—+ +-----—+-----—+ B0 B7 B0 B7

First block of arena_: Last "block" of arena_: in the free list but blocked for merging

  +--------+#########

upper | 01| arena # +-----—+-----—+ |previous| | +--------------—+ multiple of 8 | int(0) | next | <- head_avail_ | +--------------—+ +-----—+######## lower | this [+ pad@32] | lower |int(-1) |outside# +-----—+-----—+ +-----—+######## B0 B7 B0 B4

The arena size has to be a power of 2MB. It also has to be a multiple of 8 for alignment reasons. It needs to be <= 512MB.

Definition at line 66 of file malloc_arena.h.

Constructor & Destructor Documentation

MallocArena::MallocArena ( unsigned  arena_size)
explicit

The arena starts with a pointer to this followed by the AvailBlockCtl of head_avail_, followed by a reserved tag to prevent it from being merged, followed by a free block spanning the arena until the end tag. The end tag is a single negative int, which mimics another reserved block.

Definition at line 161 of file malloc_arena.cc.

Referenced by CreateInitialized().

Here is the call graph for this function:

Here is the caller graph for this function:

MallocArena::~MallocArena ( )

Definition at line 224 of file malloc_arena.cc.

Member Function Documentation

bool MallocArena::Contains ( void *  ptr) const
inline

Definition at line 90 of file malloc_arena.h.

Here is the call graph for this function:

MallocArena * MallocArena::CreateInitialized ( unsigned  arena_size,
unsigned char  pattern 
)
static

Initializes the arena with repeated copies of the given pattern. Used for testing.

Definition at line 206 of file malloc_arena.cc.

Here is the call graph for this function:

void MallocArena::EnqueueAvailBlock ( AvailBlockCtl block)
private

Inserts an avilable block at the end of the free list.

Definition at line 106 of file malloc_arena.cc.

Here is the call graph for this function:

MallocArena::AvailBlockCtl * MallocArena::FindAvailBlock ( const int32_t  block_size)
private

Walks through the free list starting at rover_ and looks for the first block larger than block_size. Returns NULL if no such block exists.

Definition at line 24 of file malloc_arena.cc.

Here is the call graph for this function:

void MallocArena::Free ( void *  ptr)

Creates a free block at the place of the reserved block ptr points into. The free block might need to be merged with adjacent lower and/or upper blocks. In these cases, the corresponding blocks are removed from the list of available blocks. Every allocated block has a predecessor and a successor in the arena. The newly created free block is added to the end of the list of available blocks.

Definition at line 55 of file malloc_arena.cc.

Referenced by ItemAllocator::Free(), and SqliteMemoryManager::PutMemory().

Here is the call graph for this function:

Here is the caller graph for this function:

static MallocArena* MallocArena::GetMallocArena ( void *  ptr,
unsigned  arena_size 
)
inlinestatic

Returns the MallocArena that houses the destination of ptr.

Definition at line 77 of file malloc_arena.h.

Referenced by Contains(), ItemAllocator::Free(), SqliteMemoryManager::GetMemorySize(), and SqliteMemoryManager::PutMemory().

Here is the caller graph for this function:

uint32_t MallocArena::GetSize ( void *  ptr) const

The ptr points to the result of Malloc(). The size of the area is stored a few bytes before ptr.

Definition at line 120 of file malloc_arena.cc.

Referenced by SqliteMemoryManager::GetMemorySize().

Here is the call graph for this function:

Here is the caller graph for this function:

bool MallocArena::IsEmpty ( ) const
inline

Definition at line 94 of file malloc_arena.h.

Referenced by ItemAllocator::Free(), and SqliteMemoryManager::PutMemory().

Here is the caller graph for this function:

void * MallocArena::Malloc ( const uint32_t  size)

Walks the list of available blocks starting from rover and allocates the first available spot that's large enough. Puts the reserved block at the end of the available one and, if necessary, removes the available one from the list of free blocks.

Definition at line 137 of file malloc_arena.cc.

Referenced by SqliteMemoryManager::GetMemory(), and ItemAllocator::Malloc().

Here is the call graph for this function:

Here is the caller graph for this function:

void * MallocArena::ReserveBlock ( AvailBlockCtl block,
int32_t  block_size 
)
private

Given the free block "block", cuts out a new reserved block of size block_size at the end of the free block. Returns a pointer usable by the application.

Definition at line 234 of file malloc_arena.cc.

Here is the call graph for this function:

void MallocArena::UnlinkAvailBlock ( AvailBlockCtl block)
private

Removes the given block from the doubly linked free block list. This happens when two adjacent free blocks are created in Free() and then merged. Or if a block gets fully used in Malloc().

Definition at line 267 of file malloc_arena.cc.

Referenced by ReserveBlock().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

char* MallocArena::arena_
private

The memory block.

Starts with the address of the MallocArena object followed by a head_avail_ block and ends with a -1 guard integer to mimic a reserved end block. The arena is aligned at a multiple of arena_size. Therefore, a pointer pointing into it can get the corresponding MallocArena object in O(1).

Definition at line 165 of file malloc_arena.h.

Referenced by CreateInitialized(), MallocArena(), UnlinkAvailBlock(), and ~MallocArena().

unsigned MallocArena::arena_size_
private

Definition at line 175 of file malloc_arena.h.

Referenced by Contains(), MallocArena(), and ~MallocArena().

AvailBlockCtl* MallocArena::head_avail_
private

Head of the list of available blocks. Located at the beginning of the arena_. The only "available" block with size 0 and with the upper tag field set to "reserved", so that it is not merged with another free'd block.

Definition at line 172 of file malloc_arena.h.

Referenced by CreateInitialized(), and MallocArena().

const int MallocArena::kMinBlockSize = 24
static

Avoid very small free blocks. This must be a larger than sizeof(AvailBlockCtl) + sizeof(AvailBlockTag) and a multiple of 8.

Definition at line 72 of file malloc_arena.h.

Referenced by ReserveBlock().

const char MallocArena::kTagAvail = 0
staticprivate

Definition at line 97 of file malloc_arena.h.

const char MallocArena::kTagReserved = 1
staticprivate

Definition at line 98 of file malloc_arena.h.

Referenced by MallocArena(), and MallocArena::ReservedBlockCtl::ReservedBlockCtl().

uint32_t MallocArena::no_reserved_
private

Definition at line 174 of file malloc_arena.h.

Referenced by IsEmpty().

AvailBlockCtl* MallocArena::rover_
private

The free block where the next search starts.

Definition at line 173 of file malloc_arena.h.


The documentation for this class was generated from the following files: