C++ Sized Deallocation

ISO/IEC JTC1 SC22 WG21 N3663 - 2013-04-30

Lawrence Crowl, crowl@google.com, Lawrence@Crowl.org

Problem
Solution
    Size Unavailable
    Backwards Compatiblity
Implementation
Wording
    3.7.4 Dynamic storage duration [basic.stc.dynamic]
    3.7.4.2 Deallocation functions [basic.stc.dynamic.deallocation]
    5.3.4 New [expr.new]
    5.3.5 Delete [expr.delete]
    12.5 Free store [class.free]
    17.6.4.6 Replacement functions [replacement.functions]
    18.6 Dynamic memory management [support.dynamic]
    18.6.1.1 Single-object forms [new.delete.single]
    18.6.1.2 Array forms [new.delete.array]
    C.?.? Clause 3: Basic concepts [diff.cpp11.basic]
Revision History
References

Problem

With C++11, programmers may define a static member function operator delete that takes a size parameter indicating the size of the object to be deleted. The equivalent global operator delete is not available. This omission has unfortunate performance consequences.

Modern memory allocators often allocate in size categories, and, for space efficiency reasons, do not store the size of the object near the object. Deallocation then requires searching for the size category store that contains the object. This search can be expensive, particularly as the search data structures are often not in memory caches.

Solution

Permit implementations and programmers to define sized versions of the global operator delete. The compiler shall call the sized version in preference to the unsized version when the sized version is available.

There are two potential problems with this solution.

Size Unavailable

When deleting an incomplete type, there is no size available. In this case, the unsized version must be used. This observation implies that calls to one version must be effectively equivalent to calls to the other version. Excepting the specific deallocation function called, we believe that any programs that would change behavior already have undefined behavior within the standard.

Backwards Compatiblity

Existing programs use only the unsized version. Linking them with a new system allocation library that provides the sized version is safe because the unsized version is equivalent. Interposing a new user allocation library on old code is safe for the same reason.

New programs using the sized version linking against an old system allocation library would fail to link. This can be fixed with the addition of a small shim, in which a sized version simply forwards to the unsized version. Likewise with new binaries linked against a new application allocation library.

The primary problem occurs when the system allocation library is new, but an interposed user allocation library is old. In new programs, calls to the unsized version would go to the user library, but calls to the sized version would go to the system library. Again, this can be fixed with a shim interposed on the system library.

The remaining issue is diagnosing the latter case. Since interposition is often done at the binary level, there appears to be no diagnostic solution other than changing the signature of all allocation functions. The pain of the ABI change would be larger than the pain of adding shims at the appropriate places.

Implementation

Google has implemented much of this proposal within GCC (at the library level) and TCMalloc [TCM]. It has obtained significant performance improvements.

Wording

The proposed wording changes are relative to N3485.

There are no direct inconsistencies with N3396 Dynamic memory allocation for over-aligned data. However, the final paper adopted must address the issue of sized deallocation of over-aligned types.

Editorial, resolutions to core issue 255 might affect the proposed text.

3.7.4 Dynamic storage duration [basic.stc.dynamic]

Edit within paragraph 2 as follows.

.... 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) throw(std::bad_alloc);
void* operator new[](std::size_t) throw(std::bad_alloc);
void operator delete(void*) noexcept;
void operator delete[](void*) noexcept;

Furthermore, the implementation may implicitly declare the following functions in global scope in each translation unit of a program.

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

These implicit declarations introduce only the function names operator new, operator new[], operator delete, operator delete[]. ....

3.7.4.2 Deallocation functions [basic.stc.dynamic.deallocation]

Edit paragraph 2 as follows.

Each deallocation function shall return void and its first parameter shall be void*. A deallocation function can have more than one parameter. The global operator delete with exactly one parameter is a usual (non-placement) deallocation function. If there is a declaration of global operator delete with exactly two parameters, the second of which has type std::size_t, then this function is a usual deallocation function. Similarly, the global operator delete[] with exactly one parameter is a usual deallocation function. If there is a declaration of global operator delete[] with exactly two parameters, the second of which has type std::size_t, then this function is a usual deallocation function. [Footnote: This deallocation function precludes use of the global void operator delete(void*, std::size_t) noexcept; as a placement new allocator (C.?.? [diff.cpp11.basic]). —end footnote] If a class T has a member deallocation function named operator delete with exactly one parameter, then that function is a usual (non-placement) deallocation function. If class T does not declare such an operator delete but does declare a member deallocation function named operator delete with exactly two parameters, the second of which has type std::size_t (18.2), then this function is a usual deallocation function. Similarly, if a class T has a member deallocation function named operator delete[] with exactly one parameter, then that function is a usual (non-placement) deallocation function. If class T does not declare such an operator delete[] but does declare a member deallocation function named operator delete[] with exactly two parameters, the second of which has type std::size_t, then this function is a usual deallocation function. A deallocation function can be an instance of a function template. Neither the first parameter nor the return type shall depend on a template parameter. [Note: that is, a deallocation function template shall have a first parameter of type void* and a return type of void (as specified above). —end note] A deallocation function template shall have two or more function parameters. A template instance is never a usual deallocation function, regardless of its signature.

5.3.4 New [expr.new]

Paragraph 11 is unchanged. This paragraph is relevant because one possible global placement new function may become unavailable.

The new-placement syntax is used to supply additional arguments to an allocation function. If used, overload resolution is performed on a function call created by assembling an argument list consisting of the amount of space requested (the first argument) and the expressions in the new-placement part of the new-expression (the second and succeeding arguments). The first of these arguments has type std::size_t and the remaining arguments have the corresponding types of the expressions in the new-placement.

Paragraph 12 is unchanged.

[Example:

• new T results in a call of operator new(sizeof(T)),

• new(2,f) T results in a call of operator new(sizeof(T),2,f),

• new T[5] results in a call of operator new[](sizeof(T)*5+x), and

• new(2,f) T[5] results in a call of operator new[](sizeof(T)*5+y,2,f).

Here, x and y are non-negative unspecified values representing array allocation overhead; the result of the new-expression will be offset by this amount from the value returned by operator new[]. This overhead may be applied in all array new-expressions, including those referencing the library function operator new[](std::size_t, void*) and other placement allocation functions. The amount of overhead may vary from one invocation of new to another. —end example]

Paragraph 20 is unchanged. This paragraph is relevant because the example now applies at global scope as well as at class scope.

A declaration of a placement deallocation function matches the declaration of a placement allocation function if it has the same number of parameters and, after parameter transformations (8.3.5), all parameter types except the first are identical. Any non-placement deallocation function matches a non-placement allocation function. If the lookup finds a single matching deallocation function, that function will be called; otherwise, no deallocation function will be called. If the lookup finds the two-parameter form of a usual deallocation function (3.7.4.2) and that function, considered as a placement deallocation function, would have been selected as a match for the allocation function, the program is ill-formed. [Example:

struct S {
  // Placement allocation function:
  static void* operator new(std::size_t, std::size_t);
  // Usual (non-placement) deallocation function:
  static void operator delete(void*, std::size_t);
};

S* p = new (0) S; // ill-formed: non-placement deallocation function matches
                  // placement allocation function

—end example]

5.3.5 Delete [expr.delete]

Paragraph 1 remains unchanged, though note the restrictions on the delete operand.

.... The operand shall be of pointer to object type of of class type. If of class type, the operand is contextually implicitly converted (Clause 4) to a pointer to object type. The delete-expression's result has type void. [Footnote: This implies that an object cannot be deleted using a pointer of type void* because void is not an object type. —end footnote]

Paragraph 2 remains unchanged, though note the restriction on inheritance with respect to the delete operand.

.... In the first alternative (delete object), the value of the operand of delete may be a null pointer value, a pointer to a non-array object created by a previous new-expression, or a pointer to a subobject (1.8) representing a base class of such an object (Clause 10). If not, the behavior is undefined. In the second alternative (delete array), the value of the operand of delete may be a null pointer value or a pointer value that resulted from a previous array new-expression. [Footnote: For non-zero-length arrays, this is the same as a pointer to the first element of the array created by that new-expression. Zero-length arrays do not have a first element. —end footnote] If not, the behavior is undefined. [Note: this means that the syntax of the delete-expression must match the type of the object allocated by new, not the syntax of the new-expression. —end note] ....

Paragraph 3 remains unchanged, though note the further restriction on inheritance.

In the first alternative (delete object), if the static type of the object to be deleted is different from its dynamic type, the static type shall be a base class of the dynamic type of the object to be deleted and the static type shall have a virtual destructor or the behavior is undefined. In the second alternative (delete array) if the dynamic type of the object to be deleted differs from its static type, the behavior is undefined.

Paragraph 5 remains unchanged.

If the object being deleted has incomplete class type at the point of deletion and the complete class has a non-trivial destructor or a deallocation function, the behavior is undefined.

Edit paragraph 9 as follows.

When the keyword delete in a delete-expression is preceded by the unary :: operator, the global deallocation function is used to deallocate the storage. the deallocation function's name is looked up in global scope. Otherwise, the lookup considers class-specific deallocations (12.5 [class.free]). If no class-specific deallocation is found, the deallocation function's name is looked up in global scope. If the lookup selects a placement deallocation function, the program is ill-formed.

Add a new paragraph as follows.

If the type is complete and if deallocation function lookup finds both a usual deallocation function with only a pointer parameter and a usual deallocation function with both a pointer parameter and a size parameter, then the selected deallocation function shall be the one with two parameters. Otherwise, the selected deallocation function shall be the function with one parameter.

Add a new paragraph as follows. This paragraph is edited as follows from the existing 12.5/5.

When a delete-expression is executed, the selected deallocation function is called with the address of the block of storage to be reclaimed as its first argument, and if the two parameter style is used, the size of the block as its second argument. [Footnote: If the static type of the object to be deleted is complete and is different from the dynamic type and the destructor is not virtual the size might be incorrect, but that case is already undefined, as stated above. —end footnote]

12.5 Free store [class.free]

Edit paragraph 4 as follows.

Class-specific deallocation function lookup is a part of general deallocation function lookup (5.3.5 [expr.delete]) and occurs as follows. If a delete-expression begins with a unary :: operator, the deallocation function's name is looked up in global scope. Otherwise, if If the delete-expression is used to deallocate a class object whose static type has a virtual destructor, the deallocation function is the one selected at the point of definition of the dynamic type's virtual destructor (12.4). [Footnote: A similar provision is not needed for the array version of operator delete because 5.3.5 requires that in this situation, the static type of the object to be deleted be the same as its dynamic type. —end footnote] Otherwise, if the delete-expression is used to deallocate an object of class T or array thereof, the static and dynamic types of the object shall be identical and the deallocation function's name is looked up in the scope of T. If this lookup fails to find the name, the name is looked up in the global scope. the class-specific deallocation function lookup has failed and general deallocation function lookup (5.3.5 [expr.delete]) continues. If the result of the lookup is ambiguous or inaccessible, or if the lookup selects a placement deallocation function, the program is ill-formed.

Remove paragraph 5 as follows. This paragraph moves to 5.3.5/9++.

When a delete-expression is executed, the selected deallocation function shall be called with the address of the block of storage to be reclaimed as its first argument and (if the two-parameter style is used) the size of the block as its second argument. [Footnote: If the static type of the object to be deleted is different from the dynamic type and the destructor is not virtual the size might be incorrect, but that case is already undefined; see 5.3.5. —end footnote]

17.6.4.6 Replacement functions [replacement.functions]

Edit paragraph 2 as follows.

A C++ program may provide the definition for any of eight dynamic memory allocation function signatures declared in header <new> (3.7.4, Clause 18 18.4 [support.dynamic]):

• operator new(std::size_t)
• operator new(std::size_t, const std::nothrow_t&)
• operator new[](std::size_t)
• operator new[](std::size_t, const std::nothrow_t&)
• operator delete(void*)
• operator delete(void*, const std::nothrow_t&)
• operator delete[](void*)
• operator delete[](void*, const std::nothrow_t&)

Furthermore, a C++ program may provide the definition for any of the four dynamic memory sized deallocation function signatures that implementations may choose to declare in header <new>:

• operator delete(void*, std::size_t)
• operator delete(void*, std::size_t, const std::nothrow_t&)
• operator delete[](void*, std::size_t)
• operator delete[](void*, std::size_t, const std::nothrow_t&)

18.6 Dynamic memory management [support.dynamic]

At the end of the synopsis add the following.

The implementation may, but need not, provide the following additional group of functions.

void operator delete(void* ptr, std::size_t size) noexcept;
void operator delete(void* ptr, std::size_t size,
                     const std::nothrow_t&) noexcept;
void operator delete[](void* ptr, std::size_t size) noexcept;
void operator delete[](void* ptr, std::size_t size,
                       const std::nothrow_t&) noexcept;

18.6.1.1 Single-object forms [new.delete.single]

Edit the synopsis before paragraph 10 as follows.

void operator delete(void* ptr) noexcept;
void operator delete(void* ptr, std::size_t size) noexcept;

After paragraph 13, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 13, insert a new paragraph as follows.

Required behavior: Calls to operator delete(void* ptr, std::size_t size) may be changed to calls to operator delete(void* ptr) without affecting memory allocation. [Note: A conforming implementation is for operator delete(void* ptr, std::size_t size) to simply call operator delete(void* ptr). —end note]

Edit the synopsis before paragraph 16 as follows.

void operator delete(void* ptr, const std::nothrow_t&) noexcept;
void operator delete(void* ptr, std::size_t size, const std::nothrow_t&) noexcept;

After paragraph 18, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 18, insert a new paragraph as follows.

Required behavior: Calls to operator delete(void* ptr, std::size_t size, const std::nothrow_t&) may be changed to calls to operator delete(void* ptr, const std::nothrow_t&) without affecting memory allocation. [Note: A conforming implementation is for operator delete(void* ptr, std::size_t size, const std::nothrow_t&) to simply call operator delete(void* ptr, const std::nothrow_t&). —end note]

18.6.1.2 Array forms [new.delete.array]

Edit the synopsis before paragraph 9 as follows.

void operator delete[](void* ptr) noexcept;
void operator delete[](void* ptr, std::size_t size) noexcept;

After paragraph 11, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 11, insert a new paragraph as follows.

Required behavior: Calls to operator delete[](void* ptr, std::size_t size) may be changed to calls to operator delete[](void* ptr) without affecting memory allocation. [Note: A conforming implementation is for operator delete[](void* ptr, std::size_t size) to simply call operator delete[](void* ptr). —end note]

Edit the synopsis before paragraph 14 as follows.

void operator delete[](void* ptr, const std::nothrow_t&) noexcept;
void operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) noexcept;

After paragraph 16, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 16, insert a new paragraph as follows.

Required behavior: Calls to operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) may be changed to calls to operator delete[](void* ptr, const std::nothrow_t&) without affecting memory allocation. [Note: A conforming implementation is for operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) to simply call operator delete[](void* ptr, const std::nothrow_t&). —end note]

C.?.? Clause 3: Basic concepts [diff.cpp11.basic]

Add a new paragraph as follows.

Change: New usual (non-placement) deallocator
Rationale: Required for new features. Effect on original feature: In C++ 2011, one could declare a global placement allocator and deallocator as follows.

void operator new(std::size_t, std::size_t) throw(std::bad_alloc);
void operator delete(void*, std::size_t) noexcept;

Now, however, the declaration of operator delete might match a predefined usual (non-placement) operator delete (3.7.4 [basic.stc.dynamic]). If so, the program is ill-formed, as it was for class member allocators and deallocators (5.3.4 [new.expr]).

Revision History

This paper revises N3536 - 2013-03-05 as follows.

• Revise and clarify the backwards compatibility discussion. Remove the constraint that programs defining one deallocator version and not the other are ill-formed.

• Revise and clarify the library sections.

• Add a discussion on placement new compatibility.

• Change no-throw declarations to no-except declarations.

N3536 revised N3432 - 2012-09-23 as follows.

• Provide names for potential solution problems.

• Clarify compatibility concerns.

• Require a diagnostic when an incompatiblity is detected.

• Add a 'Revision History' section.

References

[TCM]

TCMalloc : Thread-Caching Malloc, http://goog-perftools.sourceforge.net/doc/tcmalloc.html.