[libc++] Don't return alloc_size - 1 in __recommend to add 1 when allocating

[philnik]

Summary

For some reason __recommend returns the recommended allocation size minus one, and at almost every call site one is added to the returned value.

[philnik]

ping

[• Quuxplusone]

ping

It seems like the CI doesn't like this at all. I assumed there's a missing +1 (or an extra +1) somewhere, so I haven't looked at it at all — waiting for the CI to be green before we think about whether this is a good idea or not.

I do think you should eliminate the _VSTD and HIDE_FROM_ABI diffs from this PR; this is subtle enough that fewer distractions will be better.

[philnik]

• Fix ASAN

[philnik]

ping

[• Quuxplusone]

libcxx/include/string

1547

Clang-format strikes again. (If you must clang-format, please remember to sanity-check the code when it's finished.)

3246–3249

This diff strikes me as questionable (which probably means the entire patch is questionable). The logic here previously was, "If the target capacity is equal to our current capacity, nothing to do, return. Otherwise, shrink or extend to the target capacity." Now the logic is, "If the target capacity is one greater than our current capacity, do nothing! Otherwise, shrink or extend to one less than the target capacity." Regardless of whether the arithmetic works out in practice, that logic seems very wrong. Maybe it can be saved by renaming some variables, e.g. maybe __target_capacity doesn't actually represent a capacity? Or maybe prior to line 3239 it's a capacity but after line 3239 it's a one-greater-than-a-capacity?

[philnik]

• Remove more ones

libcxx/include/string

1547

That wasn't clang-format, but hey.

[ldionne]

I think we need to understand the situation with reserve and shrink_to_fit before moving forward with this, otherwise I think we might just be making the code more difficult to understand.

Also, this is pretty tricky because it's possible that already compiled code has the old definition of e.g. __init inlined, and hence the capacity of the string is set to N + 1. If such a string is passed to code compiled with the new definition, the new code would think that the capacity represents N, not N + 1, and would most likely mis-behave. In other words, I think this is ABI breaking.

libcxx/include/string

3246–3249

I agree, this looks fishy to me. Are you certain this wasn't a bug previously and that it should instead be if (__target_capacity == capacity()) return; *even* in the new diff? Do we have a test for that?

[philnik]

In D119628#3348916, @ldionne wrote:

I think we need to understand the situation with reserve and shrink_to_fit before moving forward with this, otherwise I think we might just be making the code more difficult to understand.

Also, this is pretty tricky because it's possible that already compiled code has the old definition of e.g. __init inlined, and hence the capacity of the string is set to N + 1. If such a string is passed to code compiled with the new definition, the new code would think that the capacity represents N, not N + 1, and would most likely mis-behave. In other words, I think this is ABI breaking.

I'm not changing what is saved in long cap. That has always been the capacity including the null terminator AFAICT. Or is there another potential ABI break that I'm not seeing?

libcxx/include/string

3246–3249

IIUC basic_string::capacity() returns the number of characters without the null terminator while __recommend() (with this patch) returns the number of characters including the null terminator.

[EricWF]

I'm not OK with this change given that the description indicates a lack of understanding of the current situation.

[EricWF]

libcxx/include/string

1547

Please don't request whitespace changes on reviews.

[EricWF]

I also agree with @ldionne's comment about this being potentially ABI breaking because of how std::string is externally instantiated.

[philnik]

In D119628#3357180, @EricWF wrote:

I'm not OK with this change given that the description indicates a lack of understanding of the current situation.

Then tell me what I'm not understanding.

In D119628#3357187, @EricWF wrote:

I also agree with @ldionne's comment about this being potentially ABI breaking because of how std::string is externally instantiated.

Can you give a scenario where that is the case? Just saying 'could be an ABI break' isn't an argument.

[• Quuxplusone]

In D119628#3356907, @philnik wrote:

In D119628#3348916, @ldionne wrote:

it's possible that already compiled code has the old definition of e.g. __init inlined, and hence the capacity of the string is set to N + 1. If such a string is passed to code compiled with the new definition, the new code would think that the capacity represents N, not N + 1, and would most likely mis-behave. In other words, I think this is ABI breaking.

I'm not changing what is saved in long cap. That has always been the capacity including the null terminator AFAICT. Or is there another potential ABI break that I'm not seeing?

I believe what Louis is getting at is that any time you change the meaning of a function's arguments (where the function is called across an ABI boundary), that can be an ABI break. For example, if f is calling arctan(a, b), and then the maintainer changes the prototype of arctan from arctan(int x, int y) to arctan(int y, int x), that's an ABI break. Or if f is calling __set_long_cap(n+1), and then the maintainer changes the prototype of __set_long_cap from __set_long_cap(int nplus1) to __set_long_cap(int n), that's an ABI break. But in this case I've double-checked that both __set_long_cap and __recommend are hide-from-abi, thus never called across an ABI boundary, so I think that's not a concern here; and if we were really really paranoid, we could even change the names of some of these helper functions.

libcxx/include/string

3246–3249

FWIW, I would bet that this is not a "real bug"; I would bet the machine code is correct. But I feel moderately strongly that we shouldn't ship source code that looks this confusing.

It is also possible that there is a bug in this vicinity after all. See https://llvm.org/pr51816 .

[ldionne]

! In D119628#3356907, @philnik wrote:

! In D119628#3348916, @ldionne wrote:
it's possible that already compiled code has the old definition of e.g. __init inlined, and hence the capacity of the string is set to N + 1. If such a string is passed to code compiled with the new definition, the new code would think that the capacity represents N, not N + 1, and would most likely mis-behave. In other words, I think this is ABI breaking.

I'm not changing what is saved in long cap. That has always been the capacity including the null terminator AFAICT. Or is there another potential ABI break that I'm not seeing?

Ahhhhhh, that's actually what I missed. I saw the change from __set_long_cap(__cap+1); to __set_long_cap(__cap);, and I went "hmm this changes the meaning of the capacity held inside the string, so that's an ABI break". But in reality, it doesn't, because __recommend returns 1 more than it used to after applying your patch. So in both cases we are setting the capacity to the same value. Please double-check my reasoning, and if we're on the same page, then thanks for correcting me -- I don't think there's any ABI break in this patch.

libcxx/include/string

3246–3249

Let me reformulate my ask: @philnik (or someone else), can you please explain why this is correct:

if (__target_capacity == capacity() + 1)
  return;

It seems to me that it should instead be

if (__target_capacity == capacity())
  return;

I suspect I'll be much happier shipping this patch once I understand it (and it will probably mandate a comment since it's not trivial to understand).

[ldionne]

@philnik explained what I was misunderstanding on Discord. I believe this patch is correct, and the code might be easier to understand if we clarify a few things in the code, like I suggest below.

Basically, what I understand is that when Howard initially wrote string, he made __recommend() exclude the null terminator so that it is consistent with capacity(). However, the capacity stored in the string object always included the null-terminator, which led to having to adjust the result of __recommend() in a bunch of places. This patch moves the inconsistency: it makes __recommend() and the stored capacity consistent, at the cost of making __recommend() and capacity() inconsistent with each other, needing a couple of adjustments (two to be exact, where I requested some comments). Given this, I don't think this patch is an absolute must-do -- we're just shifting complexity around. However, I do feel like it does reduce the complexity overall, so I'm favourable.

libcxx/include/string

933–938

1498

We should add a comment here (I would have added it to the actual data member, but it's hard because it's defined in the weirdest way) saying something like this:

// Note that the capacity we store always includes the null-terminator.

1542–1544

Can you please add a comment explaining what this returns? I.e. something like

// Returns the recommended capacity to store a string of size __s, including the null-terminator.
// Note that unlike __recommend(), string::capacity() returns the capacity *excluding* the null-terminator.

3246–3247

WDYT?

3258–3259

[philnik]

• Address comments

[ldionne]

This looks correct to me, and I think it's an improvement in clarity over the status quo. LGTM, but I'd like someone else to also take a close look since this is std::string, i.e. one of the most used classes in the library.

[• Quuxplusone]

libcxx/include/string

2261–2264

(1) I'm still very unsure that this is correct. @philnik, can you maybe make up a cheat-sheet that shows which of these numbers will include +1 for the null terminator and which won't?

• x = capacity()
• __set_long_cap(x)
• x = __recommend(...)
• __grow_by(x, ...)
• __grow_by_and_replace(x, ...)

Ideally, in the end, they'd all use the same meaning for "capacity" — which means it should not include the null terminator, because capacity() doesn't include the null terminator.

(2) On this diff in particular, aren't you accidentally failing to +1 the capacity when (__old_cap < __ms / 2 - __alignment)? Please investigate and add a regression test for what you find.

[philnik]

libcxx/include/string

2261–2264

(1)

function	x includes null-terminator?
x = capacity()	N
__set_long_cap(x)	Y
x = __recommend()	Y
__grow_by(x, ...)	N
__grow_by_and_replace(x, ...)	N
x = __get_long_cap()	Y

It's not possible for all of these to have the same meaning, because of ABI. We can't change __grow_by{, _and_replace} and __{get, set}_long_cap() because of ABI and capacity() because the standard demands different behavior.

(2) Do you mean the false branch? In that case I think it should be __ms. I'll add a regression test.

libcxx/include/string

const_reverse_iterator crbegin() const _NOEXCEPT
         {return rbegin();}
     _LIBCPP_INLINE_VISIBILITY
     const_reverse_iterator crend() const _NOEXCEPT
         {return rend();}
 
     _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT
         {return __is_long() ? __get_long_size() : __get_short_size();}
     _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();}
     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT;
-    _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT
-        {return (__is_long() ? __get_long_cap()
-                             : static_cast<size_type>(__min_cap)) - 1;}
+
+    _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT {
+        // We store the capacity including the null-terminator, but capacity() does not include the null-terminator.
+        return (__is_long() ? __get_long_cap() : static_cast<size_type>(__min_cap)) - 1;
+    }
 
     void resize(size_type __n, value_type __c);
     _LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {resize(__n, value_type());}
 
     void reserve(size_type __requested_capacity);
 
 #if _LIBCPP_STD_VER > 20
     template <class _Op>
void __set_long_size(size_type __s) _NOEXCEPT
         {__r_.first().__l.__size_ = __s;}
     _LIBCPP_INLINE_VISIBILITY
     size_type __get_long_size() const _NOEXCEPT
         {return __r_.first().__l.__size_;}
     _LIBCPP_INLINE_VISIBILITY
     void __set_size(size_type __s) _NOEXCEPT
         {if (__is_long()) __set_long_size(__s); else __set_short_size(__s);}
 
+    // Note that the capacity we store always includes the null-terminator.
     _LIBCPP_INLINE_VISIBILITY
     void __set_long_cap(size_type __s) _NOEXCEPT
         {__r_.first().__l.__cap_  = __long_mask | __s;}
     _LIBCPP_INLINE_VISIBILITY
     size_type __get_long_cap() const _NOEXCEPT
         {return __r_.first().__l.__cap_ & size_type(~__long_mask);}
 
     _LIBCPP_INLINE_VISIBILITY
     void __set_long_pointer(pointer __p) _NOEXCEPT
         {__r_.first().__l.__data_ = __p;}
void __zero() _NOEXCEPT
                 __a[__i] = 0;
         }
 
     template <size_type __a> static
         _LIBCPP_INLINE_VISIBILITY
         size_type __align_it(size_type __s) _NOEXCEPT
             {return (__s + (__a-1)) & ~(__a-1);}
     enum {__alignment = 16};
+
+    // Returns the recommended capacity to store a string of size __s, *including* the null-terminator
+    // Note that, unlike __recommend(), basic_string::capacity() returns the capacity *excluding* the null-terminator
     static _LIBCPP_INLINE_VISIBILITY
     size_type __recommend(size_type __s) _NOEXCEPT
-        {
-        if (__s < __min_cap) return static_cast<size_type>(__min_cap) - 1;
-        size_type __guess = __align_it<sizeof(value_type) < __alignment ?
-                     __alignment/sizeof(value_type) : 1 > (__s+1) - 1;
-        if (__guess == __min_cap) ++__guess;
+        if (__s < __min_cap)
+            return static_cast<size_type>(__min_cap);
+        size_type __guess = __align_it<sizeof(value_type) < __alignment ? __alignment / sizeof(value_type) : 1>(__s + 1);
+        if (__guess == __min_cap + 1)
+            ++__guess;
         return __guess;
-        }
 
     inline
     void __init(const value_type* __s, size_type __sz, size_type __reserve);
     inline
     void __init(const value_type* __s, size_type __sz);
     inline
     void __init(size_type __n, value_type __c);
 
void basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s,
     if (__fits_in_sso(__reserve))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__reserve);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        __p = __alloc_traits::allocate(__alloc(), __cap);
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__cap);
         __set_long_size(__sz);
     }
     traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
     traits_type::assign(__p[__sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz)
 {
     if (__sz > max_size())
         __throw_length_error();
     pointer __p;
     if (__fits_in_sso(__sz))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__sz);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        __p = __alloc_traits::allocate(__alloc(), __cap);
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__cap);
         __set_long_size(__sz);
     }
     traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
     traits_type::assign(__p[__sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 template <class>
void basic_string<_CharT, _Traits, _Allocator>::__init_copy_ctor_external(
   pointer __p;
   if (__fits_in_sso(__sz)) {
     __p = __get_short_pointer();
     __set_short_size(__sz);
   } else {
     if (__sz > max_size())
       __throw_length_error();
     size_t __cap = __recommend(__sz);
-    __p = __alloc_traits::allocate(__alloc(), __cap + 1);
+    __p = __alloc_traits::allocate(__alloc(), __cap);
     __set_long_pointer(__p);
-    __set_long_cap(__cap + 1);
+    __set_long_cap(__cap);
     __set_long_size(__sz);
   }
   traits_type::copy(_VSTD::__to_address(__p), __s, __sz + 1);
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
     if (__fits_in_sso(__n))
     {
         __set_short_size(__n);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__n);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        __p = __alloc_traits::allocate(__alloc(), __cap);
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__cap);
         __set_long_size(__n);
     }
     traits_type::assign(_VSTD::__to_address(__p), __n, __c);
     traits_type::assign(__p[__n], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
     if (__fits_in_sso(__sz))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__sz);
-        __p = __alloc_traits::allocate(__alloc(), __cap+1);
+        __p = __alloc_traits::allocate(__alloc(), __cap);
         __set_long_pointer(__p);
-        __set_long_cap(__cap+1);
+        __set_long_cap(__cap);
         __set_long_size(__sz);
     }
 
 #ifndef _LIBCPP_NO_EXCEPTIONS
     try
     {
 #endif  // _LIBCPP_NO_EXCEPTIONS
     for (; __first != __last; ++__first, (void) ++__p)

 {
     size_type __ms = max_size();
     if (__delta_cap > __ms - __old_cap - 1)
         __throw_length_error();
     pointer __old_p = __get_pointer();
     size_type __cap = __old_cap < __ms / 2 - __alignment ?
                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                           __ms - 1;
-    pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
+    pointer __p = __alloc_traits::allocate(__alloc(), __cap);
     __invalidate_all_iterators();
     if (__n_copy != 0)
         traits_type::copy(_VSTD::__to_address(__p),
                           _VSTD::__to_address(__old_p), __n_copy);
     if (__n_add != 0)
         traits_type::copy(_VSTD::__to_address(__p) + __n_copy, __p_new_stuff, __n_add);
     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
     if (__sec_cp_sz != 0)
         traits_type::copy(_VSTD::__to_address(__p) + __n_copy + __n_add,
                           _VSTD::__to_address(__old_p) + __n_copy + __n_del, __sec_cp_sz);
     if (__old_cap+1 != __min_cap)
         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
     __set_long_pointer(__p);
-    __set_long_cap(__cap+1);
+    __set_long_cap(__cap);
     __old_sz = __n_copy + __n_add + __sec_cp_sz;
     __set_long_size(__old_sz);
     traits_type::assign(__p[__old_sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                                      size_type __n_copy,  size_type __n_del,     size_type __n_add)
 {
     size_type __ms = max_size();
     if (__delta_cap > __ms - __old_cap)
         __throw_length_error();
     pointer __old_p = __get_pointer();
     size_type __cap = __old_cap < __ms / 2 - __alignment ?
                           __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                           __ms - 1;
-    pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
+    pointer __p = __alloc_traits::allocate(__alloc(), __cap);
     __invalidate_all_iterators();
     if (__n_copy != 0)
         traits_type::copy(_VSTD::__to_address(__p),
                           _VSTD::__to_address(__old_p), __n_copy);
     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
     if (__sec_cp_sz != 0)
         traits_type::copy(_VSTD::__to_address(__p) + __n_copy + __n_add,
                           _VSTD::__to_address(__old_p) + __n_copy + __n_del,
                           __sec_cp_sz);
     if (__old_cap+1 != __min_cap)
         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
     __set_long_pointer(__p);
-    __set_long_cap(__cap+1);
+    __set_long_cap(__cap);
 }
 
 // assign
 
 template <class _CharT, class _Traits, class _Allocator>
 template <bool __is_short>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::__assign_no_alias(
basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __requested_capacity)
     // Make sure reserve(n) never shrinks. This is technically only required in C++20
     // and later (since P0966R1), however we provide consistent behavior in all Standard
     // modes because this function is instantiated in the shared library.
     if (__requested_capacity <= capacity())
         return;
 
     size_type __target_capacity = _VSTD::max(__requested_capacity, size());
     __target_capacity = __recommend(__target_capacity);
-    if (__target_capacity == capacity()) return;
+    if (__target_capacity == capacity() + 1) // __recommend() includes the null-terminator, while capacity() doesn't
+        return;
 
     __shrink_or_extend(__target_capacity);
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
 void
 basic_string<_CharT, _Traits, _Allocator>::shrink_to_fit() _NOEXCEPT
 {
     size_type __target_capacity = __recommend(size());
-    if (__target_capacity == capacity()) return;
+    if (__target_capacity == capacity() + 1) // __recommend() includes the null-terminator, while capacity() doesn't
+        return;
 
     __shrink_or_extend(__target_capacity);
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
 void
 basic_string<_CharT, _Traits, _Allocator>::__shrink_or_extend(size_type __target_capacity)
 {
     size_type __cap = capacity();
     size_type __sz = size();
 
     pointer __new_data, __p;
     bool __was_long, __now_long;
-    if (__target_capacity == __min_cap - 1)
+    if (__target_capacity == __min_cap)
     {
         __was_long = true;
         __now_long = false;
         __new_data = __get_short_pointer();
         __p = __get_long_pointer();
     }
     else
     {
         if (__target_capacity > __cap)
-            __new_data = __alloc_traits::allocate(__alloc(), __target_capacity+1);
+            __new_data = __alloc_traits::allocate(__alloc(), __target_capacity);
         else
         {
         #ifndef _LIBCPP_NO_EXCEPTIONS
             try
             {
         #endif // _LIBCPP_NO_EXCEPTIONS
-                __new_data = __alloc_traits::allocate(__alloc(), __target_capacity+1);
+                __new_data = __alloc_traits::allocate(__alloc(), __target_capacity);
         #ifndef _LIBCPP_NO_EXCEPTIONS
             }
             catch (...)
             {
                 return;
             }
         #else  // _LIBCPP_NO_EXCEPTIONS
             if (__new_data == nullptr)
                 return;
         #endif // _LIBCPP_NO_EXCEPTIONS
         }
         __now_long = true;
         __was_long = __is_long();
         __p = __get_pointer();
     }
     traits_type::copy(_VSTD::__to_address(__new_data),
                         _VSTD::__to_address(__p), size()+1);
     if (__was_long)
         __alloc_traits::deallocate(__alloc(), __p, __cap+1);
     if (__now_long)
     {
-        __set_long_cap(__target_capacity+1);
+        __set_long_cap(__target_capacity);
         __set_long_size(__sz);
         __set_long_pointer(__new_data);
     }
     else
         __set_short_size(__sz);
     __invalidate_all_iterators();
 }