Pp. 15–24 of the Proceedings

Composing Special Memory Allocators in C++

The nature of complex, high performance system software imposes constraints on the nature and operation of memory allocation or requires special properties to be true for the memory. Often multiple constraints or properties must hold at once. It is desirable to express these constraints and properties as classes and methods. This paper presents a technique for expressing and composing special memory allocation mechanisms in C++.

Introduction

• support for variable sized objects
• data caching
• storage recycling
• allocation from special (physical) memory areas
• dynamic grouping
• real-time memory management
• memory resource control
• debugging

Special Allocation Needs

Buffer Objects

struct foo {...; char buf[1];};

Debugging

Pool Allocation

Per-Thread Caching

Dynamic Grouping

Memory Resource Control

Language Defined Memory Allocators

T *	 Tp = new(Nargs) T(Cargs);

T::operator new(sizeof(T), Nargs)
T::T(Cargs)

delete Xp;

T::~T()
T::operator delete(void *)

Generalizing Allocation Information

Composing Special Allocation Properties

Buffer Object

Recyclable Storage

Combining Allocators

MK++ Evaluation

Uses

Buffer Objects

Storage Recycling

Memory Resource Control

Performance

Summary

Class Definitions

class allocation {
public:
	allocation(): alloc_data(allocrec::record(dynamic_cast<void *>(this))) {	}
	void * operator new(size_t obj_size) {
		return allocrec::alloc(obj_size);
	}
	void operator delete(void * item_base) {
		allocrec::record(item_base)->discard();
	}
	virtual ~allocation() {	}
protected:
	allocrec * const alloc_data;				// allocation record base
};

class allocrec {
public:
	allocrec(size_t rec_size, size_t extra_size):
		object(((char *)dynamic_cast<void *>(this))+ rec_size+ extra_size+ sizeof(allocrec *)) {
		*(((allocrec **)object)-1) = this;			// set back pointer
	}
	static void * alloc(size_t obj_size) {				// "allocate"
		return (new(obj_size, 0) allocrec())->object;
	}
	virtual void discard() {				// "de-allocate"
		delete this;
	}
	void * operator new(size_t rec_size, size_t obj_size, size_t extra_size) {
		return 	malloc(rec_size+ obj_size+ extra_size+ sizeof(allocrec *));
	}
	void operator delete(void * alloc_base) {
		free(alloc_base);
	}
	static allocrec * record(void * item_base) {
		return *(allocrec **)(((char *)item_base)- sizeof(allocrec *));
	}
	virtual ~allocrec() {	}
	void * const object;				// most derived object class
protected:
	allocrec(): // virtual bases require this definition
		object(((char *)dynamic_cast<void *>(this))+ sizeof(allocrec)+ sizeof(allocrec *)) {
		*(((allocrec **)object)-1) = this;		
	}
};

class buf_allocrec: public virtual allocrec {
public:
	buf_allocrec(size_t rec_size, size_t buf_size): allocrec(rec_size, buf_size), buf(((char *)dynamic_cast<void *>(this))+rec_size) {	}
	static void * alloc(size_t obj_size, size_t buf_size) {
		return (new(obj_size, buf_size)
			buf_allocrec(sizeof(buf_allocrec), buf_size))->object;
	}
	void * const buf;
};

class buffer: public virtual allocation {
public:
	buffer(): allocation(),
		buf(dynamic_cast<buf_allocrec *>(alloc_data)->buf) {	}
	void * operator new(size_t obj_size, size_t buf_size) {
		return buf_allocrec::alloc(obj_size, buf_size);
	}
	void * const buf;
};

class message: public buffer {
public:
	message(destination & a_target):
		allocation(), buffer(), target(a_target) {	}
protected:
	destination & target;
};

class recyclable_allocrec: public virtual allocrec {
public:
	recyclable_allocrec(size_t rec_size, size_t extra_size, recycler & owner): allocrec(rec_size, extra_size), center(owner) {	}
	void discard() {
		if (! center.put(object))
			delete this;
	}
	static void * alloc(size_t obj_size, recycler & owner) {
		void * target = owner.get();			// see if something recycled
		return target? target: (new(obj_size, 0) recyclable_allocrec(sizeof(recyclable_allocrec), 0, owner))->object;
	}
	recycler & center;
};

class recyclable: public virtual allocation {
public:
	recyclable(): allocation() {	}
	void * operator new(size_t obj_size, recycler & owner) {
		return recyclable_allocrec::alloc(obj_size, owner);
	}
};

class recyclablebuf_allocrec: public recyclable_allocrec, public buf_allocrec {
public:
	recyclablebuf_allocrec(size_t rec_size, size_t buf_size, recycler & owner): allocrec(rec_size, buf_size), buf_allocrec(rec_size, buf_size), recyclable_allocrec(rec_size, buf_size, owner) {	}
	static void * alloc(size_t obj_size, size_t buf_size, recycler & owner) {
		void * target = owner.get();			// see if something recycled
		return target? target: (new(obj_size, buf_size) recyclablebuf_allocrec(sizeof(recyclablebuf_allocrec), buf_size, owner))->object;
	}
};

class recyclable_message: public recyclable, public message {
public:
	recyclable_message(destination & a_target): allocation(), message(a_target), recyclable() {	}
	void * operator new(size_t obj_size, size_t buf_size, recycler & owner) {
		return recyclablebuf_allocrec::alloc(obj_size, buf_size, owner);
	}
};

References

1. Jeffrey S. Chase, Henry M. Levy, Edward D. Lazowska and Miche Baker-Harvey, Lightweight Shared Objects in a 64-Bit Operating System, Proceedings OOPSLA '92, ACM SIGPLAN Notices, 1992.
2. Margaret A. Ellis and Bjarne Stroustrup, The Annotated C++ Reference Manual, Addison Wesley, 1990.
3. David Jordan, Instantiation of C++ Objects in Shared Memory, Journal of Object-Oriented Programming, Vol 4, No 1, 1991.
4. Keith Krueger, David Loftesness, Amin Vahdat and Thomas Anderson, Tools for the Development of Application-Specific Virtual Memory Management, Proceedings OOPSLA '93, ACM SIGPLAN Notices, 1993.
5. MK++ Project, MK++ Kernel High Level Design, Open Group Research Institute, 1996.
6. Robert B. Murray, C++ Strategies and Tactics, Addison Wesley, 1993.
7. Franco Travostino, Franklin Reynolds and Tim Martin, Real-Time Local and Remote MACH IPC: Architecture and Design, Operating Systems Collected Papers, Vol. 3, Open Software Foundation, 1994.
8. Ifor Williams, Mario Wolczko and Trevor Hopkins, Dynamic Grouping in an Object-Oriented Virtual Memory Hierarchy, Proceedings ECOOP '87, Springer-Verlag, 1987.

Footnotes

1. This research was supported in part by the Advanced Research Projects Agency (ARPA) and the Air Force Materiel Command (AFMC). Copyright 1996 by the Open Group Research Institute. All Rights Reserved.
2. Or the global operator if no class operators are defined.
3. This is the size of the most derived class, even if the most derived class does not define these special operators.
4. Otherwise the operator delete is chosen by the static type of Xp.
5. With dynamic_cast<void *>, a base class constructor can locate the beginning of the most derived class (the raw storage), but the converse is not true - operator new, knowing the location of the raw storage, cannot reasonably locate where any particular base class will lie within that, nor can safely store data there.
6. The examples are representative of special allocators in MK++. Various details of the actual MK++ microkernel environment are omitted; as such, these examples are a simplification and yet a generalization of the MK++ allocators.
7. Virtual base classes and methods are used within MK++, but not currently within allocation record classes.

Last Modified: 12:42am PDT, April 26, 1996