Special Purpose Data Structures : DynamicPackedContainer

MEngine’s internal data allocation policy heavily relies on static buffers. The DynamicPackedContainer is one of the containers used in MEngine.

This container handles allocations in a static backing buffer, with the following features:

  • Multiple object types (with different size) can coexist in the same container
  • Ability to add metadata to each allocation
  • Compact data packing in the backing buffer
  • No direct data access: container provides safe handles to data
  • Ability to trigger updates on the entire dataset (kind of foreach)

Header

#pragma once

typedef unsigned int uint;
typedef unsigned short ushort;
typedef unsigned char byte;
typedef unsigned int handle;

typedef void (*DynamicPackedContainerExecCbk) (void * const usr_arg, void * const exec_arg, byte * const data, const uint data_byte_size);
struct handleMetaData;
struct DynamicPackedContainer {
private:
	byte * const _buffer; // backing buffer storing the real data
	handleMetaData * const _metadata;
	ushort _top;
	ushort _md_alloc_back; // last element in the 'alloc' linked list
	ushort _md_free_top; // top of the 'free' stack
	uint _totalByteSize;

	const uint _md_get_id(const handleMetaData & md) const;

	// Returns an handle on a metadata object
	const handle _handle_from_md(const handleMetaData & md) const;

	// Returns the metadata object for a given handle
	handleMetaData & _md_from_handle(const handle hndl);
	const handleMetaData & _md_from_handle(const handle hndl) const;

	// Update the 'alloc' linked list and compact the backing buffer
	const void _md_rebase(handleMetaData & md);

	// Delete an element
	const void _md_delete(handleMetaData & md);

	// Create a new element of a given size
	const handleMetaData & _md_new(const uint byte_size, void * const userData);

public:
	DynamicPackedContainer(const uint buffer_byte_size, const ushort max_hndl_cnt);
	~DynamicPackedContainer();

	// return the entire backing buffer data
	byte * const GetData(uint & size) const;

	// return only the data associated to a given handle
	byte * const GetData(const handle hndl, uint & size) const;

	inline const uint GetAllocatedByteSize() const { return _totalByteSize; }

	const handle Alloc(const uint byte_size, void * const userData);
	void Release(const handle hndl);

	// execute a task on all the allocated data, using infos from the metadata objects
	void Execute(const DynamicPackedContainerExecCbk cbk, void * const exec_arg);
};

Purpose

This custom container primary use is to serve as backing buffer for an OpenGL Vertex Buffer Object that contains different objects with their own lifecycle. (for example different 3D models, or particle emitters). Like all the other reordering containers in MEngine, this custom container is NOT threadsafe.

handles

Since the position in the data block of an allocation can change during its lifecycle, the container offers a level of indirection to guaranty consistent data access. Upon successful allocation, the container returns a handle on the allocated data block. Direct access to the data block is done by passing this handle to the GetData() method.

A handle represent a specific slot in an internal indirection table, this table being updated whenever the data block referenced by this handle is moved. To guard against data corruptions and ‘update after release’ problems, handles maintain an internal allocation counter. This way, a released handle will be detected as invalid and ignored.

MetaData

The container itself is type-agnostic, only dealing with bytes arrays internally. It is however possible the tag your allocations with a metadata. This metadata is stored in the indirection table, can be queried using GetData(), and is passed as argument to the client-defined callback of the Execute() call.

Implementation


#include <assert.h>
#include <memory.h>
#include <string.h>

#include "DynamicPackedContainer.hpp"

#pragma pack(push, 2)
union metadata_link {
	struct  {
		ushort next;
		ushort prev;
	} alloc;
	struct  {
		ushort prev;
		ushort unused;
	} free;
};
#pragma pack(pop)

	struct handleMetaData {
	void * userData;
	uint counter;
	uint byte_offset;
	uint byte_size;
	metadata_link link;
	inline handleMetaData() : userData(0), counter(1), byte_offset(0), byte_size(0) {}
};

const uint DynamicPackedContainer::_md_get_id(const handleMetaData & md) const { return &md - _metadata; }
const handle DynamicPackedContainer::_handle_from_md(const handleMetaData & md) const { return (md.counter << 16) | (_md_get_id(md)); }

// handles have to following layout : 2 bytes for counter value, 2 bytes for the index
const handleMetaData & DynamicPackedContainer::_md_from_handle(const handle hndl) const {
	const uint cnt = hndl >> 16;
	const uint mdId = hndl & 0x0000FFFF;
	assert(mdId < _top);
	const handleMetaData & md = _metadata[mdId];
	assert(cnt == md.counter);
	return md;
}

handleMetaData & DynamicPackedContainer::_md_from_handle(const handle hndl) {
	const uint cnt = hndl >> 16;
	const uint mdId = hndl & 0x0000FFFF;
	assert(mdId < _top);
	handleMetaData & md = _metadata[mdId];
	assert(cnt == md.counter);
	return md;
}

/*
We are about to remove a data block from the backing buffer. Before repacking
the backing buffer, we must notify the metadata objects of a change in their data
block position.
*/
const void DynamicPackedContainer::_md_rebase(handleMetaData & md) {
	ushort nId = md.link.alloc.next;
	const uint offset = md.byte_size;
	uint size = 0;
	while(nId) {
		// each metadata pointing to data at an higher offset that the one being deleted
		// are to update their internal state before repacking then backing buffer (memmove)
		handleMetaData & nmd = _metadata[nId];
		nmd.byte_offset -= offset;
		size += nmd.byte_size;
		nId = nmd.link.alloc.next;
	}
	byte * const src = _buffer + md.byte_offset + md.byte_size;
	byte * const dst = _buffer + md.byte_offset;
	memmove(dst, src, size);
}

const void DynamicPackedContainer::_md_delete(handleMetaData & md) {
	md.counter = ((ushort)md.counter + 1);
	// remove metadata from the 'alloc' linked list
	handleMetaData & prv = _metadata[md.link.alloc.prev];
	handleMetaData & nxt = _metadata[md.link.alloc.next];
	prv.link.alloc.next = md.link.alloc.next; // note : the start of the 'alloc' linked list is always _metadata[0]
	nxt.link.alloc.prev = md.link.alloc.prev;
	if (_md_alloc_back == _md_get_id(md)) { // special case : delete on the last 'alloc' node
		_md_alloc_back = md.link.alloc.prev;
	}

	// .. and push in free stack
	md.link.free.prev = _md_free_top;
	_md_free_top = _md_get_id(md);
}

const handleMetaData & DynamicPackedContainer::_md_new(const uint byte_size, void * const userData) {
	uint newId;
	if (_md_free_top == 0) { // need to alloc new block
		newId = _top++;
	} else { // pop new metadata node from the 'free' stack
		newId = _md_free_top;
		_md_free_top = _metadata[_md_free_top].link.free.prev;
	}
	handleMetaData & md = _metadata[newId];
	md.userData = userData;

	// add new metadata to the 'alloc' linked list
	handleMetaData & alloc_prev = _metadata[_md_alloc_back];
	const uint offset = alloc_prev.byte_offset + alloc_prev.byte_size;
	alloc_prev.link.alloc.next = newId;
	md.link.alloc.prev = _md_alloc_back;
	md.link.alloc.next = 0; // force .next to zero to stop _md_rebase loop
	_md_alloc_back = newId;

	md.byte_offset = offset;
	md.byte_size = byte_size;

	return md;
}

DynamicPackedContainer::DynamicPackedContainer(const uint buffer_byte_size, const ushort max_hndl_cnt) :
	_buffer(new byte[buffer_byte_size]),
	_metadata((handleMetaData * const) memset(new handleMetaData[max_hndl_cnt + 1], 0x0, (max_hndl_cnt + 1) * sizeof(handleMetaData))),
	_top(1),
	_md_alloc_back(0),
	_md_free_top(0),
	_totalByteSize(0)
{ }

DynamicPackedContainer::~DynamicPackedContainer() {
	delete [] _buffer;
	delete [] _metadata;
}

byte * const DynamicPackedContainer::GetData(uint & size) const {
	const handleMetaData & md = _metadata[_md_alloc_back];
	size = md.byte_offset + md.byte_size;
	return _buffer;
}

byte * const DynamicPackedContainer::GetData(const handle hndl, uint & size) const {
	const handleMetaData & md = _md_from_handle(hndl);
	size = md.byte_size;
	return _buffer + md.byte_offset;
}

const handle DynamicPackedContainer::Alloc(const uint byte_size, void * const userData) {
	const handleMetaData & md = _md_new(byte_size, userData);
	const handle h = _handle_from_md(md);
	_totalByteSize += byte_size;
	return h;
}

void DynamicPackedContainer::Release(const handle hndl) {
	handleMetaData & md = _md_from_handle(hndl);
	_totalByteSize -= md.byte_size;
	_md_rebase(md);
	_md_delete(md);
}

void DynamicPackedContainer::Execute(const DynamicPackedContainerExecCbk cbk, void * const exec_arg) {
	assert(cbk);
	ushort nId = _metadata[0].link.alloc.next;
	while(nId) {
		handleMetaData & md = _metadata[nId];
		cbk(md.userData, exec_arg, _buffer + md.byte_offset, md.byte_size);
		nId = md.link.alloc.next;
	}
}

Internals

All the container ‘logic’ happens at the indirection table level. This table maintains two sorted linked lists, one containing the allocated blocks, the other for the free blocks.

An alloc list node consists in:

  • An offset in the backing buffer
  • The size of the data block in the backing buffer
  • A pointer to the client-defined metadata
  • An allocation counter to guard against invalid handle access
  • Linking information

The ‘alloc’ and ‘free’ lists share the same memory region, the ‘free’ list’s only purpose is to keep track of any reusable slot for future allocations.

The linking of the ‘alloc’ list preserve datablock ordering. This means that following the ‘alloc’ chain’s references result in a sequential access pattern of the underlying memory blocks.

Comments are closed