Page MenuHomePhabricator

[String] Allow fancy pointer as pointer type of basic_string allocator
Needs ReviewPublic

Authored by bemeryesr on Aug 18 2022, 10:49 AM.

Details

Reviewers
philnik
Group Reviewers
Restricted Project
Summary

Currently, basic_string does not support custom allocators which use fancy pointers that are not trivially constructible and destructible as the pointer type. This is due to requirements of the internal string representation, __rep. In order to use a pointer type which is not trivially constructible, __rep should:

  • be a literal type (required by the implementation). This requires that __rep has at least one constexpr constructor and that its destructor is trivial.
  • provide an explicit constructor, copy constructor and copy assignment operator (default special member functions are deleted since __long, a variant member of __rep, is not trivially constructible as it contains a fancy pointer as a member variable).

This change allows the use of fancy pointers which are not trivially constructible by adding an explicit and constexpr constructor, copy constructor and copy assignment operator. It also adds a static assert which will fail if the fancy pointer is not trivially destructible.

Addresses bug report: https://bugs.llvm.org/show_bug.cgi?id=20508

Implementation details:

Constant evaluation: From above, we have the requirement that __rep has at least one constexpr constructor. This means that we cannot use non-const functions such as memcpy or memset in the copy constructor / copy assigment operators. Additionally, the active element of a union is not allowed to be changed inside a constexpr constructor. Since during constant evaluation, short string optimization is disabled for basic_string, the active element of the __rep union can be __l and we can manually copy values from other.__l to this->__l.

Non-constant evaluation: During non-constant evaluation, the active member of __rep can be __rep.__s or __rep.__l i.e. a short or long string. In this case, we rely on type punning in the copy constructor and copy assignment operators to read the value of other.__l, even if it isn't the active member. This appears to be legal and also follows the same rationale used when reading / writing memory in __rep.__r.

C++03 / C++11 and on support:

The C++11 standard says "If any non-static data member of a union has a non-trivial default constructor (12.1), copy constructor (12.8), move constructor (12.8), copy assignment operator (12.8), move assignment operator (12.8), or destructor (12.4), the corresponding member function of the union must be user-provided or it will be implicitly deleted (8.4.3) for the union." (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf, 9.5.2).

However, the C++03 standard says "An object of a class with a non-trivial default constructor (12.1), a non-trivial copy constructor (12.8), a non-trivial destructor (12.4), or a non-trivial copy assignment operator (13.5.3, 12.8) cannot be a member of a union". Since the __long contains a fancy pointer which is not trivially constructible, __long itself is not trivially constructible and therefore __rep cannot include it as a member in C++03. Therefore, fancy pointers can only be supported for C++11 and later.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
bemeryesr edited the summary of this revision. (Show Details)Aug 18 2022, 10:53 AM
bemeryesr edited the summary of this revision. (Show Details)Aug 18 2022, 10:57 AM
bemeryesr edited the summary of this revision. (Show Details)Aug 18 2022, 11:17 AM
bemeryesr edited the summary of this revision. (Show Details)
bemeryesr edited the summary of this revision. (Show Details)Aug 18 2022, 11:49 AM
bemeryesr edited the summary of this revision. (Show Details)

Use regular instead of curly braces in member initializer list

bemeryesr updated this revision to Diff 453931.Aug 19 2022, 1:56 AM

Change noexcept specifier to _NOEXCEPT macro to support c++03

bemeryesr updated this revision to Diff 453939.Aug 19 2022, 3:17 AM

Fix clang tidy formatting issues

bemeryesr updated this revision to Diff 454047.Aug 19 2022, 9:27 AM

Support fancy pointers only for C++11 and later

The C++03 standard says "An object of a class with a non-trivial default constructor,
a non-trivial copy constructor or a non-trivial copy assignment operator cannot be a
member of a union. Therefore, we cannot support fancy pointers in C++03.

bemeryesr edited the summary of this revision. (Show Details)Aug 19 2022, 9:32 AM
bemeryesr updated this revision to Diff 454401.Aug 22 2022, 1:04 AM

Include string before checking preprocessor macro definition

limdor added a subscriber: limdor.Aug 22 2022, 1:16 AM
bemeryesr updated this revision to Diff 454412.Aug 22 2022, 1:40 AM

Apply clang formatting

bemeryesr updated this revision to Diff 454440.Aug 22 2022, 3:23 AM

Incorporate changes from master

bemeryesr updated this revision to Diff 454450.Aug 22 2022, 4:22 AM

Move test mains outside ifdef check

bemeryesr updated this revision to Diff 454459.Aug 22 2022, 5:13 AM

Add expected-no-diagnostics to empty fail test

Add templated copy constructor

bemeryesr updated this revision to Diff 456573.Aug 30 2022, 2:06 AM

Add pointer and iterator traits to test classes

bemeryesr updated this revision to Diff 456582.Aug 30 2022, 2:44 AM

Use remove_cv::type for c++11 compatibility.

bemeryesr updated this revision to Diff 456628.Aug 30 2022, 5:28 AM

Use add_lvalue_reference::type for c++11 compatibility.

bemeryesr published this revision for review.Aug 31 2022, 12:37 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 31 2022, 12:37 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik requested changes to this revision.Aug 31 2022, 7:00 AM
philnik added subscribers: ldionne, philnik.

Thanks for working on this! I think in general you take the right approach, but currently the implementation is broken. For example

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include <cassert>
#include <cstddef>
#include <string>

template <class T>
class alignas(std::max(alignof(T), alignof(std::ptrdiff_t))) OffsetPtr {
  std::ptrdiff_t offset;

public:
  using value_type        = T;
  using iterator_category = std::random_access_iterator_tag;
  using difference_type   = std::ptrdiff_t;
  using pointer           = OffsetPtr;
  using reference         = T&;

  OffsetPtr() = default;
  OffsetPtr(const OffsetPtr& other) : offset(other.operator->() - reinterpret_cast<T*>(this)) {}
  operator OffsetPtr<const T>() const { return OffsetPtr<const T>{reinterpret_cast<const T*>(this) + offset}; }

  OffsetPtr& operator=(const OffsetPtr& other) {
    T* ptr = other.operator->();
    offset = ptr - reinterpret_cast<T*>(this);
    return *this;
  }

  explicit OffsetPtr(T* ptr) : offset(ptr - reinterpret_cast<T*>(this)) {}
  T* operator->() const { return reinterpret_cast<T*>(const_cast<OffsetPtr*>(this)) + offset; }
  T& operator[](size_t i) { return operator->()[i]; }

  static OffsetPtr pointer_to(T& e) { return OffsetPtr(&e); }

  friend OffsetPtr operator+(const OffsetPtr& lhs, size_t rhs) { return OffsetPtr{lhs.operator->() + rhs}; }
};

static_assert(sizeof(OffsetPtr<int>) == 8);

template <class T>
class OffsetPtrAllocator {
public:
  using value_type = T;
  using pointer    = OffsetPtr<T>;

  pointer allocate(size_t n) { return pointer(std::allocator<T>{}.allocate(n)); }

  void deallocate(pointer ptr, size_t n) { std::allocator<T>{}.deallocate(ptr.operator->(), n); }
};

int main() {
  using string = std::basic_string<char, std::char_traits<char>, OffsetPtrAllocator<char>>;
  string str3 = "almost long string";
  string str4 = std::move(str3);
  assert(str4 == "almost long string");
}

was rejected before this patch, but now results in wrong results. The assert(str4 == "almost long string") fails with your current patch. While the OffsetPtr has undefined behaviour, it works and is used in a slightly different style as boost::interprocess::offset_ptr in practice. You could also use a pointer and add additional state to avoid the UB. Also, we have rejected these kinds of pointers until now, so we can still define the ABI. We should at least consider whether we want to use the alternate layout for fancy pointers. @ldionne WDYT?

libcxx/include/string
687

AFAICT pointers don't have to have trivial destructors.

libcxx/test/libcxx/strings/basic.string/allocator_with_fancy_pointer.pass.cpp
1 ↗(On Diff #456628)

Instead of having a single test, you should add the allocator to test_allocator.h and add an instantiation to all the string tests to have proper coverage.

libcxx/test/libcxx/strings/basic.string/allocator_with_fancy_pointer_non_trivial_destructor.fail.cpp
1 ↗(On Diff #456628)

This should be a .verify.cpp, not a .fail.cpp.

15 ↗(On Diff #456628)

You can just add // UNSUPPORTED: c++03 instead.

This revision now requires changes to proceed.Aug 31 2022, 7:00 AM
bemeryesr updated this revision to Diff 461216.Sep 19 2022, 8:19 AM

Update string and unit tests

bemeryesr marked 4 inline comments as done.Sep 19 2022, 9:06 AM

Thanks for the feedback! Regarding your OffsetPtr example:

  1. My initial code was broken as it was calling the copy assignment operator of __long even if __rep was a short string. For an offset pointer, the copy assignment operator recalculates the offset to the pointed-to address and so the copied value will be different to the original. Hence, it failed for short strings. So now I perform the copy depending on whether it's a short or a long string.
  2. As I think you alluded to, it seems that some of the pointer arithmetic is optimized-away by the compiler, leading to incorrect behaviour. In boost::interprocess::offset_ptr they mentioned this: "Note: using the address of a local variable to point to another address is not standard conforming and this can be optimized-away by the compiler. Non-inlining is a method to remain illegal but correct." To deal with this, we used a couple of tricks that prevent the functions from being inlined and the test passes. Would it make sense to add this code as a unit test as is? Or perhaps we should find a better way to deal with the UB? This is the code that works for me:
// main.cpp
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include <cassert>
#include <string>

#include "OffsetPtr.h"

int main()
{
    using string = std::basic_string<char, std::char_traits<char>, OffsetPtrAllocator<char>>;
    {
        string str3 = "almost long string";
        string str4 = std::move(str3);
        assert(str4 == "almost long string");
    }
}
// OffsetPtr.h
#ifndef OFFSETPTR_H
#define OFFSETPTR_H

#include <cassert>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>

namespace detail
{
using local_difference_type = std::ptrdiff_t;

local_difference_type SubtractPointersBytesImpl(const volatile void* ptr1, const volatile void* ptr2);

// Alias for checking if template types are of the same type after stripping const/volatile qualifiers.
template <typename T1, typename T2>
using cv_stripped_types_equal =
    typename std::is_same<typename std::remove_cv<T1>::type, typename std::remove_cv<T2>::type>;

template <typename T1, typename T2, typename = std::enable_if_t<cv_stripped_types_equal<T1, T2>::value>>
constexpr local_difference_type SubtractPointersBytes(T1* const ptr1, T2* const ptr2)
{
    return SubtractPointersBytesImpl(ptr1, ptr2);
}

template <typename T>
constexpr const T* __attribute__((noinline)) AddOffsetToPointer(const T* const ptr, local_difference_type offset)
{
    return reinterpret_cast<const T*>(reinterpret_cast<const std::uint8_t*>(ptr) + offset);
}

template <typename T>
constexpr const T* __attribute__((noinline)) AddOffsetToPointer(T* const ptr, local_difference_type offset)
{
    return reinterpret_cast<T*>(reinterpret_cast<std::uint8_t*>(ptr) + offset);
}

}  // namespace detail

template <class T>
class alignas(std::max(alignof(T), alignof(std::ptrdiff_t))) OffsetPtr
{
    std::ptrdiff_t offset;

  public:
    using value_type = T;
    using iterator_category = std::random_access_iterator_tag;
    using difference_type = detail::local_difference_type;
    using pointer = OffsetPtr;
    using reference = T&;

    constexpr OffsetPtr() = default;
    constexpr OffsetPtr(const OffsetPtr& other)
        : offset(detail::SubtractPointersBytes(other.operator->(), reinterpret_cast<T*>(this)))
    {
    }

    constexpr operator OffsetPtr<const T>() const
    {
        return OffsetPtr<const T>{detail::AddOffsetToPointer(reinterpret_cast<const T*>(this), offset)};
    }

    constexpr OffsetPtr& operator=(const OffsetPtr& other)
    {
        T* ptr = other.operator->();
        offset = detail::SubtractPointersBytes(ptr, reinterpret_cast<T*>(this));
        return *this;
    }

    constexpr explicit OffsetPtr(T* ptr) : offset(detail::SubtractPointersBytes(ptr, reinterpret_cast<T*>(this))) {}

    constexpr T* operator->() const
    {
        return const_cast<T*>(detail::AddOffsetToPointer(reinterpret_cast<T*>(const_cast<OffsetPtr*>(this)), offset));
    }

    constexpr T& operator[](size_t i) { return operator->()[i]; }

    static OffsetPtr pointer_to(T& e) { return OffsetPtr(&e); }

    friend OffsetPtr operator+(const OffsetPtr& lhs, size_t rhs)
    {
        return OffsetPtr{detail::AddOffsetToPointer(lhs.operator->(), rhs)};
    }
};

static_assert(sizeof(OffsetPtr<int>) == 8, "");

template <class T>
class OffsetPtrAllocator
{
  public:
    using value_type = T;
    using pointer = OffsetPtr<T>;

    pointer allocate(size_t n) { return pointer(std::allocator<T>{}.allocate(n)); }

    void deallocate(pointer ptr, size_t n) { std::allocator<T>{}.deallocate(ptr.operator->(), n); }
};

#endif  // OFFSETPTR_H
// OffsetPtr.cpp
#include "OffsetPtr.h"

namespace detail
{

local_difference_type SubtractPointersBytesImpl(const volatile void* const ptr1, const volatile void* const ptr2)
{
    return local_difference_type(reinterpret_cast<local_difference_type>(ptr1) -
                                 reinterpret_cast<local_difference_type>(ptr2));
}

}  // namespace detail
libcxx/include/string
687

Yeah, you're right. As of C++20, we can use constexpr destructors. Before C++20 they must be trivial in order for basic_string to be constexpr.

bemeryesr updated this revision to Diff 461239.Sep 19 2022, 9:48 AM
bemeryesr marked an inline comment as done.

Update failing unit tests

Manually apply formatting patch from CI

Manually apply formatting patch from CI

Update formatting

bemeryesr updated this revision to Diff 461506.Sep 20 2022, 1:52 AM

Fix failing C++03 tests

bemeryesr updated this revision to Diff 461522.Sep 20 2022, 2:28 AM

Fix broken unit tests

bemeryesr updated this revision to Diff 461535.Sep 20 2022, 4:53 AM

Fix unit tests

bemeryesr updated this revision to Diff 461549.Sep 20 2022, 5:55 AM

Fix unit tests

bemeryesr updated this revision to Diff 461567.Sep 20 2022, 7:31 AM

Fix debug unit tests

Hi @philnik. When you get a chance, could you please have a look at my PR? I made a few changes as mentioned in my comment a while ago. I also updated all the unit tests to also use a fancy pointer allocator. Thanks!

Thanks for the feedback! Regarding your OffsetPtr example:

  1. My initial code was broken as it was calling the copy assignment operator of __long even if __rep was a short string. For an offset pointer, the copy assignment operator recalculates the offset to the pointed-to address and so the copied value will be different to the original. Hence, it failed for short strings. So now I perform the copy depending on whether it's a short or a long string.
  2. As I think you alluded to, it seems that some of the pointer arithmetic is optimized-away by the compiler, leading to incorrect behaviour. In boost::interprocess::offset_ptr they mentioned this: "Note: using the address of a local variable to point to another address is not standard conforming and this can be optimized-away by the compiler. Non-inlining is a method to remain illegal but correct." To deal with this, we used a couple of tricks that prevent the functions from being inlined and the test passes. Would it make sense to add this code as a unit test as is? Or perhaps we should find a better way to deal with the UB? This is the code that works for me:
// main.cpp
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include <cassert>
#include <string>

#include "OffsetPtr.h"

int main()
{
    using string = std::basic_string<char, std::char_traits<char>, OffsetPtrAllocator<char>>;
    {
        string str3 = "almost long string";
        string str4 = std::move(str3);
        assert(str4 == "almost long string");
    }
}
// OffsetPtr.h
#ifndef OFFSETPTR_H
#define OFFSETPTR_H

#include <cassert>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>

namespace detail
{
using local_difference_type = std::ptrdiff_t;

local_difference_type SubtractPointersBytesImpl(const volatile void* ptr1, const volatile void* ptr2);

// Alias for checking if template types are of the same type after stripping const/volatile qualifiers.
template <typename T1, typename T2>
using cv_stripped_types_equal =
    typename std::is_same<typename std::remove_cv<T1>::type, typename std::remove_cv<T2>::type>;

template <typename T1, typename T2, typename = std::enable_if_t<cv_stripped_types_equal<T1, T2>::value>>
constexpr local_difference_type SubtractPointersBytes(T1* const ptr1, T2* const ptr2)
{
    return SubtractPointersBytesImpl(ptr1, ptr2);
}

template <typename T>
constexpr const T* __attribute__((noinline)) AddOffsetToPointer(const T* const ptr, local_difference_type offset)
{
    return reinterpret_cast<const T*>(reinterpret_cast<const std::uint8_t*>(ptr) + offset);
}

template <typename T>
constexpr const T* __attribute__((noinline)) AddOffsetToPointer(T* const ptr, local_difference_type offset)
{
    return reinterpret_cast<T*>(reinterpret_cast<std::uint8_t*>(ptr) + offset);
}

}  // namespace detail

template <class T>
class alignas(std::max(alignof(T), alignof(std::ptrdiff_t))) OffsetPtr
{
    std::ptrdiff_t offset;

  public:
    using value_type = T;
    using iterator_category = std::random_access_iterator_tag;
    using difference_type = detail::local_difference_type;
    using pointer = OffsetPtr;
    using reference = T&;

    constexpr OffsetPtr() = default;
    constexpr OffsetPtr(const OffsetPtr& other)
        : offset(detail::SubtractPointersBytes(other.operator->(), reinterpret_cast<T*>(this)))
    {
    }

    constexpr operator OffsetPtr<const T>() const
    {
        return OffsetPtr<const T>{detail::AddOffsetToPointer(reinterpret_cast<const T*>(this), offset)};
    }

    constexpr OffsetPtr& operator=(const OffsetPtr& other)
    {
        T* ptr = other.operator->();
        offset = detail::SubtractPointersBytes(ptr, reinterpret_cast<T*>(this));
        return *this;
    }

    constexpr explicit OffsetPtr(T* ptr) : offset(detail::SubtractPointersBytes(ptr, reinterpret_cast<T*>(this))) {}

    constexpr T* operator->() const
    {
        return const_cast<T*>(detail::AddOffsetToPointer(reinterpret_cast<T*>(const_cast<OffsetPtr*>(this)), offset));
    }

    constexpr T& operator[](size_t i) { return operator->()[i]; }

    static OffsetPtr pointer_to(T& e) { return OffsetPtr(&e); }

    friend OffsetPtr operator+(const OffsetPtr& lhs, size_t rhs)
    {
        return OffsetPtr{detail::AddOffsetToPointer(lhs.operator->(), rhs)};
    }
};

static_assert(sizeof(OffsetPtr<int>) == 8, "");

template <class T>
class OffsetPtrAllocator
{
  public:
    using value_type = T;
    using pointer = OffsetPtr<T>;

    pointer allocate(size_t n) { return pointer(std::allocator<T>{}.allocate(n)); }

    void deallocate(pointer ptr, size_t n) { std::allocator<T>{}.deallocate(ptr.operator->(), n); }
};

#endif  // OFFSETPTR_H
// OffsetPtr.cpp
#include "OffsetPtr.h"

namespace detail
{

local_difference_type SubtractPointersBytesImpl(const volatile void* const ptr1, const volatile void* const ptr2)
{
    return local_difference_type(reinterpret_cast<local_difference_type>(ptr1) -
                                 reinterpret_cast<local_difference_type>(ptr2));
}

}  // namespace detail
philnik added inline comments.Tue, Dec 6, 1:36 AM
libcxx/include/string
687

basic_string isn't constexpr before C++20. Either way, we have to support non-constexpr pointers. AFAIK nothing in the standard requires the pointer to work during constant evaluation.

778

Why is this special-casing needed? AFAICT the code below is valid in C++03.

libcxx/test/libcxx/strings/basic.string/string.access/assert.back.pass.cpp
22

Please move these test refactorings into it's own PR. This diff is really large.

libcxx/test/libcxx/strings/basic.string/string.capacity/max_size.pass.cpp
94

It doesn't seem like this change adds any coverage. The fancy_pointer_allocator doesn't change anything w.r.t. max_size, does it?

136

Could you enable the constexpr test as a drive-by?