#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 MallocArena *	GetMallocArena (void *ptr, unsigned arena_size)

static MallocArena *	CreateInitialized (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)

AvailBlockCtl *	FindAvailBlock (const int32_t block_size)

void *	ReserveBlock (AvailBlockCtl *block, int32_t block_size)

Private Attributes
char *	arena_
	The memory block. More...

AvailBlockCtl *	head_avail_

AvailBlockCtl *	rover_
	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

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

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 91 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 available 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 95 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 166 of file malloc_arena.h.

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

unsigned MallocArena::arena_size_

private

Definition at line 176 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 173 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 98 of file malloc_arena.h.

const char MallocArena::kTagReserved = 1

staticprivate

Definition at line 99 of file malloc_arena.h.

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

uint32_t MallocArena::no_reserved_

private

Definition at line 175 of file malloc_arena.h.

Referenced by IsEmpty().

AvailBlockCtl* MallocArena::rover_

private

The free block where the next search starts.

Definition at line 174 of file malloc_arena.h.

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

/home/sftnight/jenkins/workspace/CvmfsDoxygen/label/docker-x86_64/cvmfs/cvmfs/malloc_arena.h
/home/sftnight/jenkins/workspace/CvmfsDoxygen/label/docker-x86_64/cvmfs/cvmfs/malloc_arena.cc

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation