The allocator described here gives you a simple, yet effective interface to manage the virtual memory API of Windows NT. In the following sections we describe classes for the layout of a memory chunk, for the layout of a memory page, for an allocator of fixed sized chunks and for an integrating segregated allocator. This system allocator was mainly developed as part of our general allocator.
Return codes signalling an error are thrown as exceptions. List management in the allocator is implemented using intrusive lists. Sometimes there is a need to determine the binary logarithm of a number. Memory for management information is allocated using a special internal allocation interface.
The first stage designing our allocator is to layout a chunk of memory. A chunk contains a back pointer to a page, to which the chunk belongs, a pointer to the managed memory zone, the size of the managed memory zone and a list entry for free list management. A back pointer to the chunk is stored at the start of the managed memory zone.
Dereferencing an application pointer in the GetChunk
method contains multiple guards. The back pointer to the chunk
must be writable, the chunk must be writable and the pointer to
the managed memory zone must correspond to the application
pointer.
The method Allocate rounds the requested size to
the size of an operating system memory page (here platform
dependent 4096 bytes for Intel and 8192 bytes for Alpha) and
commits the requested virtual memory. The method Deallocate
uses the size information to guard against double deallocation
and decommits the committed virtual memory.
#define ROUND(size,to) ((((size)+(to)-1)/(to))*(to))
#ifdef _M_IX86
#define OS_CHUNK_SIZE (1<<12)
#endif
#ifdef _M_ALPHA
#define OS_CHUNK_SIZE (1<<13)
#endif
class COSPage;
class COSChunk;
typedef SListEntry< COSChunk > COSChunkListEntry;
typedef SListHead< COSChunk > COSChunkListHead;
class COSChunk {
private:
COSPage *m_page;
void *m_ptr;
unsigned m_size;
COSChunkListEntry m_list_entry;
public:
COSChunk (COSPage *page, void *ptr):
m_page (page), m_ptr (ptr), m_size (0), m_list_entry () {}
~COSChunk (void) {}
static COSChunk *GetThis (COSChunkListEntry *list_entry) {
return (COSChunk *)((char *) list_entry - (char *) &((COSChunk *) 0)->m_list_entry);
}
COSPage *GetPage (void) const {
return m_page;
}
void *GetPtr (void) const {
return m_ptr;
}
unsigned GetSize (void) const {
return m_size;
}
COSChunkListEntry *GetListEntry (void) {
return &m_list_entry;
}
static COSChunk *GetChunk (void *ptr) {
COSChunk **chunk = (COSChunk **) ptr - 1;
if (IsBadWritePtr (chunk, sizeof (COSChunk *)))
return 0;
if (IsBadWritePtr (*chunk, sizeof (COSChunk)))
return 0;
if ((*chunk)->m_ptr != chunk)
return 0;
return *chunk;
}
void *Allocate (unsigned size) {
size = ROUND (size, OS_CHUNK_SIZE);
void *ptr = ::VirtualAlloc (m_ptr, size, MEM_COMMIT, PAGE_READWRITE);
if (ptr != m_ptr)
return 0;
m_size = size;
COSChunk **chunk = (COSChunk **) m_ptr;
*chunk = this;
return chunk + 1;
}
void *Reallocate (unsigned size) {
if (! m_size)
return 0;
size = ROUND (size, OS_CHUNK_SIZE);
if (size > m_size) {
void *ptr = (COSChunk **) ::VirtualAlloc ((char *) m_ptr + m_size, size - m_size , MEM_COMMIT, PAGE_READWRITE);
if (ptr != (char *) m_ptr + m_size)
return 0;
} else if (size < m_size) {
if (! ::VirtualFree ((char *) m_ptr + size, m_size - size , MEM_DECOMMIT))
throw COSException (__FILE__, __LINE__);
}
m_size = size;
COSChunk **chunk = (COSChunk **) m_ptr;
return chunk + 1;
}
void Deallocate (void) {
if (! m_size)
return;
if (! ::VirtualFree (m_ptr, m_size, MEM_DECOMMIT))
throw COSException (__FILE__, __LINE__);
m_size = 0;
}
};The second stage designing our allocator is to layout a page of memory. A page collects a number of chunks in a contiguous memory zone. The describing attributes of a page include count and size of the chunks, a pointer to a chunk array, a pointer to the the managed memory zone, a bool concerning the state of that pointer, the maximum number of recently used chunks, a list head for free list management of chunks and a list entry for page list management.
The method Allocate checks, whether the page is
full. If not, it tries to use the free list to recycle the first
free chunk. If there is no such free chunk, it initializes an
unused chunk using operator placement new. The
method Deallocate links a chunk into the free list.
The method Reserve reserves the virtual memory
zone for the page using the Windows NT function VirtualAlloc.
The method Release reinitializes the management
information of the page calling the destructor and releases the
virtual memory zone for the page using the Windows NT function VirtualFree.
The static method Create reserves a new page
using internal allocation with operator
placement new and the calling it's Reserve method
. The static method Destroy releases a
page calling it's Release method and freeing the
associated memory.
#ifdef _M_IX86
#define OS_PAGE_SIZE (1<<16)
#endif
#ifdef _M_ALPHA
#define OS_PAGE_SIZE (1<<16)
#endif
class COSPage;
typedef DListEntry< COSPage > COSPageListEntry;
typedef DListHead< COSPage > COSPageListHead;
class COSPage {
private:
unsigned m_count;
unsigned m_size;
void *m_chunk_ptr;
void *m_ptr;
bool m_ptr_valid;
unsigned m_max_used;
COSChunkListHead m_free_list_head;
COSPageListEntry m_list_entry;
public:
COSPage (unsigned count, unsigned size, void *chunk_ptr):
m_count (count), m_size (size),
m_chunk_ptr (chunk_ptr),
m_ptr (0), m_ptr_valid (false),
m_max_used (0), m_free_list_head (),
m_list_entry () {}
~COSPage (void) {
COSChunkListEntry *list_entry = m_free_list_head.GetFirst ();
while (list_entry) {
m_free_list_head.Unlink (list_entry);
list_entry = m_free_list_head.GetFirst ();
}
while (m_max_used > 0) {
-- m_max_used;
COSChunk *chunk = operator [] (m_max_used);
chunk->~COSChunk ();
}
}
COSChunk *operator [] (int i) const {
return (COSChunk *) ((char *) m_chunk_ptr + i * sizeof (COSChunk));
}
static COSPage *GetThis (COSPageListEntry *list_entry) {
return (COSPage *)((char *) list_entry - (char *) &((COSPage *) 0)->m_list_entry);
}
unsigned GetChunkCount (void) const {
return m_count;
}
unsigned GetUsed (void) const {
return m_max_used - m_free_list_head.GetCount ();
}
unsigned GetMaxUsed (void) const {
return m_max_used;
}
COSPageListEntry *GetListEntry (void) {
return &m_list_entry;
}
static unsigned GetChunkCount (unsigned size) {
return size <= OS_PAGE_SIZE ? OS_PAGE_SIZE / size : 1;
}
void *Allocate (unsigned size) {
if (GetUsed () < m_count) {
COSChunk *chunk = 0;
COSChunkListEntry *list_entry = m_free_list_head.GetFirst ();
if (list_entry) {
chunk = COSChunk::GetThis (list_entry);
m_free_list_head.Unlink (list_entry);
} else {
chunk = new (operator [] (m_max_used)) COSChunk (this, (char *) m_ptr + m_max_used * m_size);
++ m_max_used;
}
return chunk->Allocate (size);
}
return 0;
}
bool Deallocate (COSChunk *chunk) {
if (((char *) chunk->GetPtr () - (char *) m_ptr) / m_size < m_max_used) {
chunk->Deallocate ();
m_free_list_head.Link (chunk->GetListEntry ());
return true;
}
return false;
}
bool Reserve (void) {
for (int i = 0; i < 2; i ++) {
m_ptr = ::VirtualAlloc (m_ptr, m_count * m_size, MEM_RESERVE, PAGE_NOACCESS);
if (m_ptr) {
m_ptr_valid = true;
break;
}
}
return m_ptr_valid;
}
static COSPage *Create (unsigned count, unsigned size) {
void *ptr = imalloc (sizeof (COSPage) + count * sizeof (COSChunk));
if (! ptr)
return 0;
COSPage *page = new (ptr) COSPage (count, size, (char *) ptr + sizeof (COSPage));
if (! page)
return 0;
if (! page->Reserve ())
return 0;
return page;
}
void Release (void) {
this->~COSPage ();
if (m_ptr_valid) {
if (! ::VirtualFree (m_ptr, 0, MEM_RELEASE))
throw COSException (__FILE__, __LINE__);
m_ptr_valid = false;
}
}
static void Destroy (COSPage *page) {
page->Release ();
ifree (page);
}
};The third stage implementing our allocator is the description of a fixed size allocator. Its task is to manage a linked list of pages for chunks of a certain size. The describing attributes of a fixed size allocator include count and size of the chunks and list heads for list management of pages.
Pages are flipped forth and back between a used and a free list, corresponding whether they are full or partially full. This ensures constant time lookup for a page containing free chunks.
A tricky part hereby is, that the fixed size allocator uses the maximum number of recently used chunks in a page to decide, whether an empty page is released to the operating system. If a page is empty and had not been completely filled, it is not released.
class COSFixedAllocator {
private:
unsigned m_count;
unsigned m_size;
COSPageListHead m_free_list_head;
COSPageListHead m_used_list_head;
COSPageListHead m_released_list_head;
public:
COSFixedAllocator (void):
m_count (0), m_size (0),
m_free_list_head (), m_used_list_head (), m_released_list_head () {}
~COSFixedAllocator (void) {
COSPageListEntry *list_entry;
while ((list_entry = m_free_list_head.GetFirst ()) != 0) {
COSPage *page = COSPage::GetThis (list_entry);
m_free_list_head.Unlink (list_entry);
COSPage::Destroy (page);
}
while ((list_entry = m_used_list_head.GetFirst ()) != 0) {
COSPage *page = COSPage::GetThis (list_entry);
m_free_list_head.Unlink (list_entry);
COSPage::Destroy (page);
}
while ((list_entry = m_released_list_head.GetFirst ()) != 0) {
COSPage *page = COSPage::GetThis (list_entry);
m_released_list_head.Unlink (list_entry);
COSPage::Destroy (page);
}
}
void SetNetSize (unsigned size) {
m_count = COSPage::GetChunkCount (size);
m_size = size;
}
void *Allocate (unsigned size) {
COSPageListEntry *list_entry = m_free_list_head.GetFirst ();
if (! list_entry) {
list_entry = m_released_list_head.GetFirst ();
if ( ! list_entry) {
COSPage *page = COSPage::Create (m_count, m_size);
if (! page)
return 0;
list_entry = page->GetListEntry ();
} else {
m_released_list_head.Unlink (list_entry);
COSPage *page = COSPage::GetThis (list_entry);
if (! page->Reserve ())
return 0;
}
m_free_list_head.Link (list_entry);
}
COSPage *page = COSPage::GetThis (list_entry);
void *ptr = page->Allocate (size);
if (page->GetUsed () == page->GetChunkCount ()) {
m_free_list_head.Unlink (list_entry);
m_used_list_head.Link (list_entry);
}
return ptr;
}
void Deallocate (COSChunk *chunk) {
COSPage *page = chunk->GetPage ();
if (page->Deallocate (chunk)) {
if (page->GetUsed () + 1 == page->GetChunkCount ()) {
COSPageListEntry *list_entry = page->GetListEntry ();
m_used_list_head.Unlink (list_entry);
m_free_list_head.Link (list_entry);
}
}
if (page->GetUsed () == 0 &&
page->GetMaxUsed () == page->GetChunkCount ()) {
page->Release ();
COSPageListEntry *list_entry = page->GetListEntry ();
m_free_list_head.Unlink (list_entry);
m_released_list_head.Link (list_entry);
}
}
};The fourth and last stage implementing our allocator is the description of a segregated allocator. It dispatches the allocation and deallocation requests to the appropriate fixed size allocator.
The method Deallocate guards against double
deallocation checking the chunks size. If its size is 0 due to a
recent deallocation, the actual request is ignored and the
internal lists are guarded.
class COSSegregatedAllocator {
private:
COSFixedAllocator m_fixed_allocator [32];
public:
COSSegregatedAllocator (void) {
for (int i = 0; i < 32; ++ i)
m_fixed_allocator [i].SetNetSize (1 << i);
}
~COSSegregatedAllocator (void) {}
void *Allocate (unsigned size) {
if (size == 0)
size = 1;
int j = CEIL_ILOGB (size);
return m_fixed_allocator [j].Allocate (size);
}
void *Reallocate (void *ptr, unsigned size) {
COSChunk *chunk = COSChunk::GetChunk (ptr);
if (! chunk)
return 0;
int i = CEIL_ILOGB (chunk->GetSize ());
if (i < 0)
return 0;
if (size == 0)
size = 1;
int j = CEIL_ILOGB (size);
if (i == j)
return chunk->Reallocate (size);
ptr = m_fixed_allocator [j].Allocate (size);
if (! ptr)
return 0;
memmove (ptr, chunk->GetPtr (), min (size, chunk->GetSize ()));
m_fixed_allocator [i].Deallocate (chunk);
return ptr;
}
void Deallocate (void *ptr) {
COSChunk *chunk = COSChunk::GetChunk (ptr);
if (! chunk)
return;
int i = CEIL_ILOGB (chunk->GetSize ());
if (i < 0)
return;
m_fixed_allocator [i].Deallocate (chunk);
}
};To test distinct operating system allocation mechanisms, we
implemented a procedural interface for page allocation. This also
allows proper initialization of a singleton segregated allocator.
The initialization of the singleton works using internal allocation with operator placement
new.
#define PAGE_OWN 0
#define PAGE_MS_HEAP 1
#define PAGE_MS_VIRTUAL 2
int ptype = PAGE_OWN;
COSSegregatedAllocator *g_os_segregated_allocator;
void *pmalloc (unsigned size) {
switch (ptype) {
case PAGE_OWN:
if (! g_os_segregated_allocator) {
void *ptr = imalloc (sizeof (COSSegregatedAllocator));
if (! ptr)
return 0;
g_os_segregated_allocator = new (ptr) COSSegregatedAllocator;
}
return g_os_segregated_allocator->Allocate (size);
case PAGE_MS_HEAP:
return ::HeapAlloc (::GetProcessHeap (), 0, size);
case PAGE_MS_VIRTUAL:
return ::VirtualAlloc (0, size, MEM_COMMIT | MEM_TOP_DOWN, PAGE_READWRITE);
}
return 0;
}
void pfree (void *ptr) {
switch (ptype) {
case PAGE_OWN:
if (! g_os_segregated_allocator)
return;
g_os_segregated_allocator->Deallocate (ptr);
return;
case PAGE_MS_HEAP:
if (! ::HeapFree (::GetProcessHeap (), 0, ptr))
throw COSException (__FILE__, __LINE__);
return;
case PAGE_MS_VIRTUAL:
if (! ::VirtualFree (ptr, 0, MEM_RELEASE))
throw COSException (__FILE__, __LINE__);
return;
}
}© 2000-2002 GeNeSys
mbH & Co. KG
Last revised: 12/14/2000