How does the 'delete' operator actually work behind the scenes in C++ in dynamic memory allocation (heap)?

Question

I am not getting how the "delete" operator is actually implemented behind the scenes in C++. For example:

class Node{
  int i;
  Node *left,*right;
};

int main()    {
  Node* a = new Node; // somehow the object 'a' is initialised with its data members
  delete a;
}

What exactly does delete a; do behind the scenes? Like is there any default destructor called upon or what? Also, as a contains left and right pointers, is the object a->left and a->right also deleted? What happens at the core machine level?

Answer 1

Nomenclature

According to the C++ standard §12.4 Destructors/p4,p6,p7,p8,p12 [class.dtor] (Emphasis mine):

⁴If a class has no user-declared destructor, a destructor is implicitly declared as defaulted (8.4). An implicitly declared destructor is an inline public member of its class.

⁶A destructor is trivial if it is not user-provided and if:

^(6.1) — the destructor is not virtual,

^(6.2) — all of the direct base classes of its class have trivial destructors, and

^(6.3) — for all of the non-static data members of its class that are of class type (or array thereof), each such class has a trivial destructor.

Otherwise, the destructor is non-trivial.

⁷A destructor that is defaulted and not defined as deleted is implicitly defined when it is odr-used (3.2) or when it is explicitly defaulted after its first declaration.

¹²A destructor is invoked implicitly

^(12.1) — for a constructed object with static storage duration (3.7.1) at program termination (3.6.4),

^(12.2) — for a constructed object with thread storage duration (3.7.2) at thread exit,

^(12.3) — for a constructed object with automatic storage duration (3.7.3) when the block in which an object is created exits (6.7),

^(12.4) — for a constructed temporary object when its lifetime ends (4.4, 12.2). In each case, the context of the invocation is the context of the construction of the object. A destructor is also invoked implicitly through use of a delete-expression (5.3.5) for a constructed object allocated by a new-expression (5.3.4); the context of the invocation is the delete-expression. [ Note: An array of class type contains several subobjects for each of which the destructor is invoked. — end note ] A destructor can also be invoked explicitly. A destructor is potentially invoked if it is invoked or as specified in 5.3.4, 12.6.2, and 15.1. A program is ill-formed if a destructor that is potentially invoked is deleted or not accessible from the context of the invocation.

DR;TL

In C++ if a class, struct or union doesn't have a user declared destructor, then the compiler will always implicitly declare one trivial destructor for it. That is, although you haven't declared a destructor for your Node class the compiler is obliged by the C++ standard to declare a trivial one for you.

This implicitly declared trivial destructor will be defined once upon your class is odr-used. That is, when any expression anywhere in the program takes the address of or binds a reference directly to an object of your class.

Calling delete upon a Node object that was previously allocated with new will evoke its implicitly defined destructor and the heap storage allocated for that object by new will be reclaimed (i.e., freed).

Since the implicit declared destructor is trivial, any storage pointed by member pointers left and right will not be touched at all. Meaning that, if you've allocated any memory that is being pointed only by the left and right member pointers of a Node object. After calling delete upon this object the memory that was being pointed by member pointers left and right will be orphan (i.e., you'll have a memory leak).

What Happens At Core Machine Level

What happens at core machine level may vary from vendor to vendor, from operating system to operating system and from machine to machine as the core behaviour of a delete expression is not specified by the C++ standard. Any compiler vendor can do anything it feels like it to (e.g., optimizations), as long as the observable behaviour conforms with the C++ standard.

More or less though, vendors are doing similar things. For example lets take into account the following piece of code:

class Node {
  int i;
  Node *left, *right;
};

int main() {
  Node *n = new Node;
  delete n;
}

The generated assembly code for the above piece of code for GCC version 6.2 compiler is:

main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     edi, 24
        call    operator new(unsigned long)
        mov     QWORD PTR [rbp-8], rax
        mov     rax, QWORD PTR [rbp-8]
        mov     esi, 24
        mov     rdi, rax
        call    operator delete(void*, unsigned long)
        mov     eax, 0
        leave
        ret

In the assembly code generated for our simple example, the construction of the n object is represented by the code snippet below:

sub     rsp, 16
mov     edi, 24
call    operator new(unsigned long)
mov     QWORD PTR [rbp-8], rax

Since the object is trivially constructible the only thing the compiler does is allocation of memory for the object by calling the implicitly declared global operator new.

The destruction process of the object is represented by the code snippet below:

rax, QWORD PTR [rbp-8]
mov     esi, 24
mov     rdi, rax
call    operator delete(void*, unsigned long)

Notice, that the destruction process is done in reverse order with respect the steps taken in the construction process. At the end the implicitly declared global operator delete is called to free the previously allocated memory.

In our example neither a constructor nor a destructor is called since in our case the observable behaviour of the program doesn't change if they are not called.

Now the rightfull question is where in heck operator delete is?

In order to preserve the nomenclaturstic style of this answer lets quote the C++ standard from §3.7.4 Dynamic storage duration [basic.stc.dynamic]\p1, p2 (Emphasis Mine):

¹Objects can be created dynamically during program execution (1.9), using new-expressions (5.3.4), and destroyed using delete-expressions (5.3.5). A C++ implementation provides access to, and management of, dynamic storage via the global allocation functions operator new and operator new[] and the global deallocation functions operator delete and operator delete[]. [ Note: The non-allocating forms described in 18.6.2.3 do not perform allocation or deallocation. — end note ]

²The library provides default definitions for the global allocation and deallocation functions. Some global allocation and deallocation functions are replaceable (18.6.2). A C++ program shall provide at most one definition of a replaceable allocation or deallocation function. Any such function definition replaces the default version provided in the library (17.5.4.6). The following allocation and deallocation functions (18.6) are implicitly declared in global scope in each translation unit of a program.

void* operator new(std::size_t); 
void* operator new(std::size_t, std::align_val_t); void operator delete(void*) noexcept; 
void operator delete(void*, std::size_t) noexcept;
void operator delete(void*, std::align_val_t) noexcept;
void operator delete(void*, std::size_t, std::align_val_t) noexcept;
void* operator new[](std::size_t);
void* operator new[](std::size_t, std::align_val_t);
void operator delete[](void*) noexcept;
void operator delete[](void*, std::size_t) noexcept;
void operator delete[](void*, std::align_val_t) noexcept;
void operator delete[](void*, std::size_t, std::align_val_t) noexcept;

These implicit declarations introduce only the function names operator new, operator new[], operator delete, and operator delete[]. [ Note: The implicit declarations do not introduce the names std, std::size_t, std::align_val_t, or any other names that the library uses to declare these names. Thus, a new-expression, delete-expression or function call that refers to one of these functions without including the header is well-formed. However, referring to std or std::size_t or std::align_val_t is ill-formed unless the name has been declared by including the appropriate header. — end note ] Allocation and/or deallocation functions may also be declared and defined for any class (12.5).

The answer is the delete operator is implicitly declared in global scope in each translation unit of your program.