Library issue: Exception propagation and other requirements of allocator's construct member function

82 views
Skip to first unread message

dyp

unread,
May 31, 2014, 11:22:25 AM5/31/14
to std-dis...@isocpp.org
There is an issue related to the `construct` member function of custom
allocators vs the exception safety guarantees of vector, which has
already been described in those two topics:

https://groups.google.com/a/isocpp.org/d/topic/std-discussion/yZLnYy_y2z0/discussion

https://groups.google.com/a/isocpp.org/d/topic/std-discussion/BcM7ya8JeqY/discussion

Since it seems that there's currently no related issue in the current
issues list, I want to open one.
However, it turns out there might be several ways to fix the problem.
It would be my first issue so I might need some guidance and I'd also
like to discuss the possible solutions first.

Unfortunately, my attempt at accurately describing the issue lead to a
very long e-mail.


--------------------------


= Abstract =

When resizing a vector, the accessibility and exception specification
of the value type's constructors determines whether the elements are
copied or moved to the new buffer.
However, the copy/move is performed via the allocator's construct
member function, which is assumed, but not required, to call the
copy/move constructor and propagate only exceptions from the value
type's copy/move constructor.
The issue might also affect other classes.


= Current wording in n3797 =

Table 28 - Allocator requirements in [allocator.requirements]

a, a1, a2 values of type X&
c a pointer of type C* through which indirection is valid
Args a template parameter pack
args a function parameter pack with the pattern Args&&

a.construct(c, args)
Effect: Constructs an object of type C at c
Default:
::new((void*)c) C(forward<Args>(args)...)

[allocator.requirements]/5
An allocator may constrain the types on which it can be
instantiated and the arguments for which its construct member may be
called.
If a type cannot be used with a particular allocator, the
allocator class or the call to construct may fail to instantiate.

== Issues ==

1. The allocator is not required to call the copy constructor if the
arguments (args) is a single (potentially const) lvalue of the value
type. Similarly for a non-const rvalue + move constructor. See also
[container.requirements.general]/13 which seems to try to require
this, but is not sufficient (see code example below).

2. The allocator may throw exceptions in addition to constructors of
the value type; it can also throw exceptions from other constructors
as a copy/move constructor.


[vector.modifiers]
[insert and emplace member functions omitted]
void push_back(T&& x);

1 Remarks:
Causes reallocation if the new size is greater than the old capacity.
If no reallocation happens, all the iterators and references
before the insertion point remain valid.

If an exception is thrown other than by the copy constructor, move
constructor, assignment operator, or move assignment operator of T or
by any InputIterator operation there are no effects. [side remark: no
effects on the container object?]

[*]If an exception is thrown by the move constructor of a
non-CopyInsertable T, the effects are unspecified.

== Issues ==

1. Copy and move assignment are invoked directly from vector. However,
construction is invoked via the allocator abstraction. As discussed
above, the allocator currently is not required to call the copy/move
constructor.

2. The sentence [*] is the same as the remarks for the resize member
function. In the resize member function, where do not deal with
inserting in the middle of the vector (which leads to the requirements
on the assignment operators in [vector.modifiers]), it might be
clearer that an allocator calling the copy constructor for an rvalue
argument of a nothrow-MoveConstructible value type invalidates the
usefulnes of move_if_noexcept in this context.


= Code example =

template<class T>
class allocator;

class pot_reg_type // a type which creates
// potentially registered instances
{
private:
friend class allocator<pot_reg_type>;
struct register_t {};

static std::set<pot_reg_type*>& get_registry()
{
static std::set<pot_reg_type*> registry;
return registry;
}
void enregister() noexcept(false)
{
get_registry().insert(this);
}
void deregister()
{
get_registry().erase(this);
}

public:
pot_reg_type(void ) noexcept(true) {}
pot_reg_type(pot_reg_type const&) noexcept(true) {}
pot_reg_type(pot_reg_type&& ) noexcept(true) {}

private:
pot_reg_type(register_t ) noexcept(false)
{ enregister(); }
pot_reg_type(register_t, pot_reg_type const&) noexcept(false)
{ enregister(); }
pot_reg_type(register_t, pot_reg_type&& ) noexcept(false)
{ enregister(); }
};

template<class T>
class allocator
{
public:
using value_type = T;

value_type* allocate(std::size_t p)
{ return (value_type*) ::operator new(p); }

void deallocate(value_type* p, std::size_t)
{ ::operator delete(p); }

void construct(pot_reg_type* pos)
{
new((void*)pos) pot_reg_type((pot_reg_type::register_t()));
}
void construct(pot_reg_type* pos, pot_reg_type const& source)
{
new((void*)pos) pot_reg_type(pot_reg_type::register_t(),
source);
}

template<class... Args>
void construct(T* p, Args&&... args)
{
new((void*)p) T(std::forward<Args>(args)...);
}
};

The construct member function template is only required for rebinding,
which can be required e.g. to store additional debug information in
the allocated memory (e.g. VS2013).

Even though the value type has an accessible and noexcept(true) move
constructor, this allocator won't call that constructor for rvalue
arguments.
In any case, it does not call a constructor for which vector has
formulated its requirements.
An exception thrown by a constructor called by this allocator is not
covered by the exceptions in [vector.modifiers] and therefore is
guaranteed not to have any effect on the vector object when resizing.

For an example how this might invalidate the exception safety
guarantees, see:
https://groups.google.com/a/isocpp.org/d/topic/std-discussion/BcM7ya8JeqY/discussion

Another problem arises for value types whose constructors are private,
but may be called by the allocator.
Those value types are not MoveConstructible (is_move_constructible is
false), yet they can be MoveInsertable.


= Possible solutions =

== 1st Solution ==
Suggested by Howard Hinnant in a comment on StackOverflow:
http://stackoverflow.com/questions/23859112/cost-of-stdvectorpush-back-either-succeeding-or-having-no-effect/23859368?noredirect=1#comment36723190_23859368

Add the following requirements to the allocator's construct member
function:

a) For a CopyInsertable value type, if the argument is a single
lvalue of the (potentially const) value type, it must call the copy
constructor.

b) For a MoveInsertable and nothrow-MoveConstructible value type, if
the argument is a single non-const rvalue of the value type, it must
call the move constructor.

c) If the argument is a single value type (rvalue or lvalue), it may
only propagate the exceptions of the value type's constructor.

This could also be formulated only via c), by demanding that the
allocator only propagates exceptions that could have been thrown by
the copy ctor (for lvalues) or move ctor (for non-const rvalues).


== 2nd Solution ==
Slightly change the guarantees of vector's modifiers etc:

a) Formulate vector's exception safety guarantees in terms of
calling the construct member function of the allocator.

b) Make it UB when the allocator's construct throws for a
nothrow-MoveConstructible type. (This allows keeping
is_move_constructible as the criterion whether or not to move when
resizing.)


== 3rd Solution ==
Change vector's criterion whether or not to move when resizing:

Instead of testing the value type's constructors via
is_move_constructible, check if the allocator's construct member
function is noexcept when passing a single non-const rvalue of the
value type (noexcept-operator).


== A short discussion of the three solutions ==

Solution 1 seems to me to express most clearly the current intent of
the Standard.
It does (probably) not require changes in current library
implementations. However, it restricts what can be done inside the
construct member function.
Essentially, the construct member function now may only use the
default placement-new plus functions that either don't throw or whose
error can be handled or ignored (for copy/move, not in the other
emplace cases).

Solution 2 does not restrict the allocator as heavily.
It does (probably) not require changes to current library
implementations either, however it does introduce UB.

Solution 3 requires changing both the implementation of the default
allocator (add a conditional noexcept) and vector (replace
is_move_constructible with an allocator-targeted check).
It does not impose restrictions on the allocator (other than
[container.requirements.general]/13).
This is the only solution (of these three) that works nicely with
private move constructors combined with befriended allocators.


Kind regards,

dyp

Ville Voutilainen

unread,
May 31, 2014, 11:54:05 AM5/31/14
to std-dis...@isocpp.org
On 31 May 2014 18:22, dyp <dyp...@gmx.net> wrote:
> There is an issue related to the `construct` member function of custom
> allocators vs the exception safety guarantees of vector, which has
> already been described in those two topics:
>
> https://groups.google.com/a/isocpp.org/d/topic/std-discussion/yZLnYy_y2z0/discussion
>
> https://groups.google.com/a/isocpp.org/d/topic/std-discussion/BcM7ya8JeqY/discussion
>
> Since it seems that there's currently no related issue in the current
> issues list, I want to open one.

Have you read
https://isocpp.org/std/submit-a-library-issue ?

> However, it turns out there might be several ways to fix the problem.
> It would be my first issue so I might need some guidance and I'd also
> like to discuss the possible solutions first.
> Unfortunately, my attempt at accurately describing the issue lead to a
> very long e-mail.


That would perhaps indicate that it should be written up as a paper.

Casey Carter

unread,
Nov 21, 2014, 2:45:05 PM11/21/14
to std-dis...@isocpp.org, dyp...@gmx.net
On Saturday, May 31, 2014 10:22:25 AM UTC-5, dyp wrote:
== 1st Solution ==
Suggested by Howard Hinnant in a comment on StackOverflow:
http://stackoverflow.com/questions/23859112/cost-of-stdvectorpush-back-either-succeeding-or-having-no-effect/23859368?noredirect=1#comment36723190_23859368

Add the following requirements to the allocator's construct member
function:

  a) For a CopyInsertable value type, if the argument is a single
lvalue of the (potentially const) value type, it must call the copy
constructor.

  b) For a MoveInsertable and nothrow-MoveConstructible value type, if
the argument is a single non-const rvalue of the value type, it must
call the move constructor.

  c) If the argument is a single value type (rvalue or lvalue), it may
only propagate the exceptions of the value type's constructor.

This could also be formulated only via c), by demanding that the
allocator only propagates exceptions that could have been thrown by
the copy ctor (for lvalues) or move ctor (for non-const rvalues).


Solution 1 points (a) and (b) are overly restrictive, they make it impossible to implement e.g. std::scoped_allocator_adaptor that adds an allocator to the set of arguments passed to the value type's constructor. I think a solution to this problem should focus on constraining the allowable exception propagation and not on specifying required allocator behavior.
Reply all
Reply to author
Forward
0 new messages