How does the C++ delete operator find the memory location of a polymorphic object?

Question

I would like to know how the delete operator figures out the memory location that needs to be freed when it is given a base class pointer that is different from the true memory location of the object.

I want to duplicate this behavior in my own custom allocator/deallocator.

Consider the following hierarchy:

struct A
{
    unsigned a;
    virtual ~A() { }
};

struct B
{
    unsigned b;
    virtual ~B() { }
};

struct C : public A, public B
{
    unsigned c;
};

I want to allocate an object of type C and delete it through a pointer of type B. As far as I can tell this is a valid use of operator delete, and it works under Linux/GCC:

C* c = new C;
B* b = c;

delete b;

The interesting thing is that the pointers 'b' and 'c' actually point to different addresses because of how the object is laid out in memory, and the delete operator "knows" how to find and free the correct memory location.

I know that, in general, it is not possible to find the size of a polymorphic object given a base class pointer: Find out the size of a polymorphic object. I suspect that it is not generally possible to find the true memory location of the object either.

Notes:

• My question is not related to how new[] and delete[] work. I am interested in the single object allocation case. How does delete[] "know" the size of the operand array?.
• I am not concerned about how the destructor is called either. I am interested in the deallocation of the memory itself. How 'delete' works when I delete a pointer of base class
• I tested using -fno-rtti and -fno-exceptions, so G++ should not have access to runtime type information.

Answer 1

This is clearly implementation specific. In practice there are a relatively small number of sensible ways to implement things. Conceptually there are a few problems here:

1. You need to be able to get a pointer to the most derived object, that is the object that (conceptually) encompasses all of the other types.

   In standard C++ you can do this with a dynamic_cast:

   void *derrived = dynamic_cast<void*>(some_ptr);
   

   Which gets the C* back from just a B*, for example:

   #include <iostream>
   
   struct A
   {
       unsigned a;
       virtual ~A() { }
   };
   
   struct B
   {
       unsigned b;
       virtual ~B() { }
   };
   
   struct C : public A, public B
   {
       unsigned c;
   };
   
   int main() {
     C* c = new C;
     std::cout << static_cast<void*>(c) << "\n";
     B* b = c;
     std::cout << static_cast<void*>(b) << "\n";
     std::cout << dynamic_cast<void*>(b) << "\n";
   
     delete b;
   }
   

   Gave the following on my system

   0x912c008
   0x912c010
   0x912c008
   

2. Once that's done it then becomes a standard memory allocation tracking problem. Usually that's done in one of two ways, either a) record the size of the allocation just before the allocated memory, finding the size is just a pointer subtraction then or b) record allocations and free memory in a data structure of some sort. For more details see this question, which has a good reference.

   With glibc you can query the size of a given allocation fairly sensibly:

   #include <iostream>
   #include <stdlib.h>
   #include <malloc.h>
   
   int main() {
     char *test = (char*)malloc(50);
     std::cout << malloc_usable_size(test) << "\n";
   }
   

   That information is available to free/delete similarly and used to figure out what to do with the returned chunk of memory.

The exact details of the implementation of malloc_useable_size are given in the libc source code, in malloc/malloc.c:

(The following includes lightly edited explanations by Colin Plumb.)

Chunks of memory are maintained using a `boundary tag' method as described in e.g., Knuth or Standish. (See the paper by Paul Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such techniques.) Sizes of free chunks are stored both in the front of each chunk and at the end. This makes consolidating fragmented chunks into bigger chunks very fast. The size fields also hold bits representing whether chunks are free or in use.

An allocated chunk looks like this:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if allocated            | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  
            |             User data starts here...                          .  
            .                                                               .  
            .             (malloc_usable_size() bytes)                      .  
            .                                                               |   
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+     
            |             Size of chunk                                     |  
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  

Answer 2

Destroying a base class pointer requires that you've implemented a virtual destructor. If you didn't do that, all bets are off.

The first destructor called will be the one for the most derived object as determined by the virtual mechanism (vtable). This destructor knows the size of the object! It can squirrel that information away someplace, or pass it down the chain of destructors.

Answer 3

Its implementation defined, but one common implementation technique is that operator delete is actually called by the destructor (rather than the code with the delete in it), and there's a hidden parameter to the destructor that controls whether operator delete is called.

With this implementation, most calls to the destructor (all explicit dtor calls, calls for auto and static variables, and calls to base destructors from derived destructors) will have that extra hidden arg set to false (so operator delete will not be called). When there's a delete expression, however, it calls the top-level destructor for the object with the hidden arg true. In your example, this will be C::~C(), so it will know to reclaim the memory for the entire object

Answer 4

The usual implementation (theoretically, there can be others, I doubt there are in practice) is that there is a vtable per base object (if not, base objects aren't polymorph and can't be used for deleting). That vtable contains not only pointer to virtual functions, but also what is needed for the whole RTTI, included offset from the current object to the most derived one.

In order to explain (there are probably differences in any true implementation and I may have made some errors), here is what is really used:

struct A_VTable_Desc {
   int offset;
   void* (destructor)();
} AVTable = { 0, A::~A };

struct A_impl {
   unsigned a;
   A_VTable_Desc* vptr;
};

struct B_VTable_Desc {
   int offset;
   void* (destructor)();
} BVtable = { 0, &B::~B };

struct B_impl {
   unsigned b;
   B_VTable_Desc* __vptr;
};

A_VTable_Desc CAVtable = { 0, &C::~C_as_A };
B_VTable_Desc CBVtable = { -8, &C::~C_as_B };

struct C {
   A_impl __aimpl;
   B_impl __bimpl;
   unsigned c;
};

and the constructors of C implicitly do something like

this->__aimpl->__vptr = &CAVtable;
this->__bimpl->__vptr = &CBVtable;

Answer 5

When compiling the delete operator, the compiler needs to determines a 'deallocation' function to call after the destructor is executed. Note that the destructor doesn't have anything directly to do with the deallocation call, but it does have an effect on how the deallocation function is looked up by the compiler.

In the usual case, there is no type-specific deallocation function for the object, in which case the global deallocation function is used and which is always implicitly declared (C++03 3.7.3/2):

void operator delete(void*) throw();

Note that this function doesn't even take a size argument. It needs to determine the allocation size based on nothing but the pointer's value. That might be done by storing the allocation's size just prior to the address (is there an implementation that does it some other way?).

However, before deciding to use that deallocation function, the compiler performs a lookup to see if a type-specific deallocation function should be used. That function can have either single parameter (a void*) or two parameters (a void* and a size_t).

When looking up the deallocation function, if the static type of the pointer used as the operand to delete has a virtual destructor, then (C++03 12.5/4):

the deallocation function is the one found by the lookup in the definition of the dynamic type’s virtual destructor

In effect, any operator delete() deallocation function is virtual for types that have a virtual destructor, even though the actual function must be static (the standard notes this in 12.5/7). In this case, the compiler can pass the size of object if it needs to because it has access to the object's dynamic type (any necessary adjustment to the object pointer can be found the same way).

If the static type of the operand to delete is static, then the the lookup for the operator delete() deallocation function follows the usual rules. Again, if the compiler selects a deallocation function that needs a size parameter, it can do so because the it knows the static type of the object at compile time.

The final situation is one that results in undefined behavior: if the pointer's static type doesn't have a virtual destructor but points to a derived type object, then the compiler will potentially lookup the wrong deallocation function and pass the wrong size. But since that's the result of undefined behavior, it doesn't matter.

Answer 6

a pointer to a polymorphic object is usually implemented as a pointer to the object and the virtual table, which contains information about the underlying class of the object. delete will know these implementation details and find the right destructor

Answer 7

It can do this the same way malloc does. Some mallocs record the size just preceding the object itself. Most modern mallocs are a lot more sophisticated. See tcmalloc, a fast allocator that keeps objects of the same size together on pages so that it need only keep size information on a page granularity.