C++ Metadata – Part II, Inheritance, Dynamic Casting, and Allocation

In Part I in the series on C++ Metadata, I explored how to build the basics of a runtime metadata system for C++ types, including custom classes, third-party libraries' classes, and even C++ primitives. The article detailed building the low-level facilities to have metadata, but did not cover any real-world uses of metadata. Today's article is going to cover adding inheritance information to the metadata, using that information to construct a dynamic_cast<> work-alike, and adding a simple allocation helper.

Note: I consider this article to be highly out-of-date. It is a good first cut at a metadata system, but a much more complete and modern version of this article needs to be written.

Quick Review

I'm going to jump in and start with a relisting of the Metadata class I built last time.

class Metadata
{
public:
  Metadata(const char* name, size_t size) : m_Name(name), m_Size(size) {}

  const char* name() const { return m_Name; }
  size_t size() const { return m_Size; }

private:
  const char* m_Name;
  size_t m_Size;
};

The Metadata class has just enough information for some interesting demos but not much else. The m_Size member might be enough to support a memory allocation method for applications that never need to worry about extended alignment, but that might not be enough for many games that use extended-alignment for vectors and matrices that are intended to be optimized with SSE, NEON, or AltiVec.

Inheritance Metadata

Inheritance information is one of the easier things to add to our Metadata class. Especially if we limit ourselves to single-inheritance patterns, which is what I do. Multiple-inheritance has a lot of valid use cases, but the complexity for our implementation is high and the benefits of supporting multiple-inheritance with dynamic type casting in an engine that makes heavy use of component-based design are relatively limited.

The first step then is to extend Metadata with a pointer to a parent Metadata, representing the inheritance.

class Metadata
{
public:
  Metadata(const char* name, size_t size, const Metadata* parent) :    m_Name(name), m_Size(size), m_Parent(parent) {}

  const char* name() const { return m_Name; }
  size_t size() const { return m_Size; }
  const Metadata* parent() const { return m_Parent; }

  bool isa(const Metadata* base) const;

private:
  const char* m_Name;
  size_t m_Size;
  const Metadata* m_Parent;
};

Quite straight forward. You may have noticed that I also added an isa() method to Metadata. The method simply checks if the parameter is in the chain of parent pointers for the Metadata instance. It will be used for dynamic type casting/checking later on.

Actually setting the pointer require a small addition to the macros we created in the last article. The macros made use of templates and a special MetaSingleton<> class, which comes in very handy now.

#define DEFINE_META(metatype, parent) Metadata \
MetaSingleton<metatype>::s_Meta(#metatype, sizeof(metatype), parent);
#define META_TYPE(metatype) (MetaSingleton<metatype>::get())</code>

Using the macros to define metadata for types with and without parents is simple:

struct Foo {};
struct Bar : public Foo {};

DEFINE_META(Foo, NULL);
DEFINE_META(Bar, META_TYPE(Foo));</code>

It's entirely reasonable to just create two different DEFINE_META macros; one for types with parents and one for types without, with the former removing the need to explicitly invoke META_TYPE when specifying the parent type. In a later article in the series we'll cover some advanced tricks for making the definition of metadata exceedingly easy and readable (with some caveats, of course). For now, the simple macros get the trick done.

Extending the code to support multiple inheritance is not necessarily difficult, but it does require some thought. Maintaining a list or other data structure of all possible parents for a type without needing dynamic memory allocation will require a small bit of care. Initializing that list with clean, readable DEFINE_META-style macros requires even more care. All doable, but I'd recommend just skipping that unless a real need for it arises.

Dynamic Type Casting

The dynamic_cast<> operator built-in to C++ works about as efficiently as possible and supports every conceivable valid type cast C++'s type system allows. Replacing it does not make a lot of sense unless there is some value to doing so. One reason may well be that the default RTTI system in C++ has been disabled because of its redundant data; even without a replacement metadata system, many games have been known to disable RTTI, especially those targeting resource-constrained mobile gaming platforms. A simpler, lighter replacement for dynamic_cast<> that supports exactly the features needed and no more can be valuable in these cases.

Another huge value of a replacement is that dynamic_cast<> does not support specifying the target type at runtime. That is, the target type is a compile-time template parameter to dynamic_cast<>. Actually casting to a runtime-specified type makes little sense in C++, but being able to query whether such a cast would be valid has plenty of uses.

A third reason to replace dynamic_cast<> is the exception-based failure mode for dynamic_cast<>. If exceptions are disabled, or if failures are expected to be common for some particular use, it is important to use a purely pointer-based implementation that can simply return NULL on failure.

Dynamic type casting via C++'s built-in dynamic_cast<> is a fairly complicated affair. At the simplest level, C++ needs to use the RTTI's chain of inheritance, much as our system will do. At the most complicated level, C++ supports virtual inheritance, which can require a lot of black magic to do the proper pointer offset arithmetic. We're not going to even consider supporting virtual bases in this article series, so we can ignore all that complexity.

The first thing we're going to need is an implementation for the Metadata::isa() method I added to the class definition previously. All it does is walk a linked list, looking for a match.

bool Metadata::isa(const Metadata* base) const
{
  const Metadata* meta = this;
  while (meta != NULL)
  {
     if (meta == base)
       return true; // found a match
     meta = meta->parent();
  }
  return false; // no match found
}

Implementing a cast operator is now quite trivial, using a little bit of template magic and our MetaLookup<> template from the previous article.

template <typename TargetType, typename InputType>
static TargetType* MetaCast(InputType* input)
{
  const Metadata* meta = MetaLookup<InputType>::get(input);
  const Metadata* target = MetaSingleton<TargetType>::get();
  return meta != NULL && meta->isa(target) ? static_cast<TargetType>(input) : NULL;
}

template <typename TargetType, typename InputType>
static const TargetType* MetaCast(const InputType* input)
{
  const Metadata* meta = MetaLookup<InputType>::get(input);
  const Metadata* target = MetaSingleton<TargetType>::get();
  return meta != NULL && meta->isa(target) ? static_cast<const TargetType*>(input) : NULL;
}

Usage of the new "operator" is more or less identical to the dynamic_cast<> operator, except that only pointers are supported, and failure to perform the cast is signaled by a NULL return value.

Extending the operator to support multiple inheritance requires no changes to the implementation of MetaCast<>() itself, as all of the real work is performed by Metadata::isa().

Memory Allocation

A final real-world use for metadata that I'll cover in this part of the metadata series is the creation of a memory allocation helper. We already have enough information for a basic implementation, as we have the size of the type stored in the Metadata class.

For the sake of many game engines, however, it can be quite handy to have alignment support as well. This can be a teeny bit tricky to do in an automatic way as not all compilers support the new C++11 alignof operator, including both GCC and Visual C++. Thankfully, GCC does provide a nearly identical proprietary operator, and Visual C++ has an operator that can be cajoled into doing the work we need. We can wrap them up in a macro easily enough. The VC++ version has some... magic involved to work around a compiler crash bug I ran into.

#if __cplusplus >= 201103L
  /* do nothing, alignof() should be supported, or else the compiler is broken and a liar */
#elif defined(_MSC_VER)
#  define alignof(x) __alignof(decltype(*static_cast<std::remove_reference<std::remove_pointer<(x)>::type>::type*>(0)))
#elif defined(__GNUC__)
#  define alignof(x) __alignof__((x))
#else
#  error "Unsupported compiler: missing C++11 alignof() operator or known work-around"
#endif

The Visual C++ version makes use of the proprietary __alignof operator. However, I found that it will cause a compiler crash for some cases, like references to abstract classes, which we certainly want to be able to create Metadata objects for. The mess up above was something I found that worked around the bug. The GCC version uses the proprietary__alignof__ operator, which has no bugs I could detect and which works enough like the C++11 alignof that it just works for all tests I've tried. Clang 3.0 should support alignof, but I don't know if it defined __cplusplus to the appropriate version yet. I don't have a build of Clang ready locally to test with, but the code may need a simple additional check for Clang to whitelist it to using the alignof operator. Please let me know if you test and find changes are necessary. I don't use (or recommend) any other compilers, so I do not know if any need workarounds or what those might be.

That out of the way, the Metadata class can now be extended with alignment information and an allocate() method. We also can update the DEFINE_META macro to automatically generate the alignment data.

class Metadata
{
public:
  Metadata(const char* name, size_t size, size_t alignment, const Metadata* parent) :
    m_Name(name), m_Size(size), m_Alignment(alignment), m_Parent(parent) {}

  const char* name() const { return m_Name; }
  size_t size() const { return m_Size; }
  size_t alignment() const { return m_Alignment; }
  const Metadata* parent() const { return m_Parent; }

  bool isa(const Metadata* base) const;

  void* allocate() const;
  void deallocate(void*) const;

private:
  const char* m_Name;
  size_t m_Size;
  size_t m_Alignment;
  const Metadata* m_Parent;
};

#define DEFINE_META(metatype, parent) \
  Metadata MetaSingleton<metatype>::s_Meta( \
  #metatype, sizeof(metatype), alignof(metatype), parent);

The allocate() method could almost just be a simple wrapper around operator new if it weren't for C++'s embarrassing lack of alignment support in operator new (even in the new standard). We have to rely on platform-specific memory allocation routines. Unfortunately, on some platforms these also require platform-specific deallocation routines as well, hence the deallocate() method.

Implementing them is straight forward. I provide Win32/POSIX implementations here.

void* Metadata::allocate() const
{
#if defined(_WIN32)
  return _aligned_malloc(m_Size, m_Alignment);
#else
  void* mem;
  int rs = posix_memalign(&mem, m_Alignment, m_Size);
  return rs == EOK ? mem : NULL;
#endif
}

void Metadata::deallocate(void* mem) const
{
#if defined(_WIN32)
  _aligned_free(mem);
#else
  free(mem);
#endif
}

A few improvements and extensions can easily be made. Supporting array allocation and deallocation is quite trivial, for starts. Adding a bit more platform-specific logic can avoid the call to the aligned allocation functions (which may be slower than the regular allocation functions) if the type's alignment is already less than or equal to the platform's default alignment (8 on most PC platforms; 16 on OS X and Windowx x64).

Most importantly, it is quite possible to add support for custom allocator interfaces. My engine completely bans the use of default operator new or malloc(), for instance, and requires all allocations to go through a slightly more sophisticated memory management API. This API is used for custom allocator support (e.g., scratch allocators, pool allocators, etc.), handles hierarchical per-arena accounting, and ensures we have a decent general purpose allocation algorithm on platforms like Win XP which have pretty awful default allocators. Extending the allocate() API here is as easy as giving it a new parameter for the allocator and to replace the implementation with calls to that allocator.

Allocation and deallocation are not nearly enough, naturally. Objects need to be constructed and destructed. That requires a bit more work to accomplish, and will be part of the next article in the series.