<experimental/memory_resource>: Implement monotonic_buffer_resource.

[• Quuxplusone]

Summary

(D47090 included this in <memory_resource>; at Eric's request, I've split this out into its own patch applied to the existing <experimental/memory_resource> instead.)

Depends on D46806 D47109 D47344

[• Quuxplusone]

Fix one visibility macro.

[EricWF]

FYI I have a full implementation of this laying around as D27402 (https://reviews.llvm.org/D27402). But I have never taken the time to resolve merge conflicts.
Feel free to steal any of the tests if they're still relevant.

include/experimental/memory_resource

429

I can't imagine we'll need more than 1 byte to represent the alignment.

474

Lets add override to these functions.

src/experimental/memory_resource.cpp

217

Drop the braces for conditionals and loops with single statements.

[• Quuxplusone]

include/experimental/memory_resource

429

Even assuming for the sake of argument that that's right, it wouldn't buy us anything here because of padding, would it?

At the moment, __alignment_ needs to have enough range to store the align parameter passed to monotonic_buffer_resource::do_allocate. In an SSE world we should not blithely assume that align < 256. We could store lg(align) in a single byte since align is always a power of two and less than 2^64 — but then we're back to the first argument, which is that it'll be padded to 8 bytes anyway so what do we gain.

474

I grepped for "override" in include/ and saw exactly one (accidental?) use in experimental/filesystem, so I thought probably libc++ had a policy not to use it for portability reasons. I'll add it throughout, but would like someone to explicitly confirm that

(A) it's okay to use in this header and wouldn't need to be guarded with a _LIBCPP_OVERRIDE macro or anything

(B) Arthur should not bother trying to add it to any other headers, not even "for consistency"

src/experimental/memory_resource.cpp

217

*shiver* but okay.

237

For reference, here is where we ask the upstream for a block aligned according to the user's align.
It occurs to me that the upstream might not be able to satisfy such a request (actually, new_delete_resource works that way for me because libc++ doesn't support aligned new and delete on OSX), which would make the upstream throw bad_alloc. We handle this by passing along the exception. We could conceivably handle it by retrying with

aligned_capacity += align;
__res_->allocate(aligned_capacity, alignof(max_align_t));
header->__alignment_ = alignof(max_align_t);

but I'm not sure that that's any of monotonic_buffer_resource's business. Happy to make the patch if you think it ought to be.

[EricWF]

include/experimental/memory_resource

428

Can't we determine the capacity in most cases simply using static_cast<char*>(this) - static_cast<char*>(__start_)?

429

Even assuming for the sake of argument that that's right, it wouldn't buy us anything here because of padding, would it?

It could. (A) we don't actually need to include the types trailing padding when tail allocating it as a part of a buffer.
and less importantly (B) I'm not sure all ABI's require the trailing padding of a type be included when that type is a data member of another type (I might just be wrong on this).

I'm also looking into other ways of improving the way your implementation packs data, which may cause this to be beneficial.

474

The header already assumes a full C++11 implementation (it uses std::tuple), the override keyword will bi available. No need for a special macro.

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic_buffer.pass.cpp

1 ↗

(On Diff #148542)

Instead of testing the whole of monotonic_buffer in a single file, this test should be broken up into separate files. Roughly one per function, or when it makes sense, one per subsection for the lowest level of heading (For example a single test for all constructors under memory.buffer.ctor ).

[EricWF]

src/experimental/memory_resource.cpp

237

I was initially thinking of storing lg(align).

[• Quuxplusone]

Add override; disintegrate the unit test; adopt some tests from Eric's D27402.
Also fix one QOI issue discovered by Eric's tests: if the user passes an initial_size to the constructor, then they are probably intending that our first upstream-allocation be big enough to serve at least initial_size 1-byte allocations (or one initial_size-byte allocation with a suitably small alignment). This is explicitly not mandated by the Standard (it merely requires that our next upstream-allocation be of size at least initial_size), but it's probably a healthy choice.

[• Quuxplusone]

Refactor to remove unused fields from the header structs.

Before this change, sizeof(monotonic_buffer_resource) == 56 and the overhead per allocated chunk was 40 bytes.
After this change, sizeof(monotonic_buffer_resource) == 48 and the overhead per allocated chunk is 24 bytes.

Eric suggests replacing size_t __align_ with uint8_t __log2_align_. I'm amenable to this idea, but I'd want to know what's the best way to compute the log2 of a user-supplied number.

[• Quuxplusone]

include/experimental/memory_resource

489

I've discovered that Boost.Container does not bother to preserve this state across calls to release(). If that's legal, then we can save 8 bytes here. I've asked for an LWG issue to be opened on the subject of "what the heck is release() supposed to do anyway."

[• Quuxplusone]

• Shrink monotonic_buffer_resource, and make release() not "leak" allocation size.
  
  Repeatedly calling allocate() and release() in a loop should not blow up. I originally thought this was required by the Standard, and maybe it is, but that was before I discovered this terrible effect, and before Pablo Halpern told me that it was not his actual intent.
  
  Since the only purpose of storing __next_buffer_size_ in the object was to implement the "looping blows up" misfeature, we can now get rid of that field, which shrinks monotonic_buffer_resource from 56 bytes down to 48 bytes, matching Boost.Container's implementation.

• Add REQUIRES: c++experimental to all tests (oops).

[• Quuxplusone]

include/experimental/memory_resource

489

On discussion with Ion Gaztañaga, Pablo Halpern, and Casey Carter, I've come to the conclusion that we *must not* preserve this state across calls to release, no matter what the Standard currently says, because that leads to insanely high memory usage when calling mr.release() in a loop. (Casey implies that MSVC's implementation has this issue; Pablo confirms that he never intended it.)

Fixed my implementation and added a regression test in test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp.

[• Quuxplusone]

Minor cosmetic changes.

[EricWF]

In D47111#1114284, @Quuxplusone wrote:

Refactor to remove unused fields from the header structs.

Before this change, sizeof(monotonic_buffer_resource) == 56 and the overhead per allocated chunk was 40 bytes.
After this change, sizeof(monotonic_buffer_resource) == 48 and the overhead per allocated chunk is 24 bytes.

Woo! This is looking great!

I'm done looking at the implementation, I'll take a pass at the tests tomorrow. Some pointers in general:

1. Tests should be named after the component they test, not how they're testing it.
2. All the tests for a single component should be in the same file.
3. You can use LIBCPP_ASSERT to check specific implementation details, like exactly how much our allocation sizes grow.

(1) and (2) are important for maintaining the tests. (3) will probably be useful for actually writing meaningful tests despite
most observable behavior being implementation specific.

include/experimental/memory_resource

425

Can these classes be members of monotonic_buffer_resource?

451

Lets keep these constructors inline.

467

Need _LIBCPP_FUNC_VIS

471

I think it would be nice for release to be inline. What do you think?

489

__previous_allocation_size isn't used in the header, so it shouldn't be declared there. We don't want to expose more symbols than we need to.

src/experimental/memory_resource.cpp

212

In general, please wrap to 80 characters.

test/std/experimental/memory/memory.resource.monotonic.buffer/nothing_to_do.pass.cpp

2

We don't actually need this file, though older libc++ tests will often include it.

It's only needed to keep empty directories around, but this one has children.

[• Quuxplusone]

I'll take a pass at the tests tomorrow. Some pointers in general:

• Tests should be named after the component they test, not how they're testing it.
• All the tests for a single component should be in the same file.

I'm certain I'm doing it fairly wrong and you'll have to give me specific handholds like "merge these two tests into one file", "rename this file to x.cpp", etc.
The current large number of files is only because *last* iteration, you told me to split up the tests from "one big monotonic_buffer.pass.cpp" into one file per test!
The problem with "one file per component" is that I don't understand what a "component" is in this context. From last iteration, I know that "all of monotonic_buffer_resource" is too big of a component! I also know that it's impossible to test deallocate without also calling allocate, but the reverse is not true.

include/experimental/memory_resource

471

Good point. It does pull a ton of stuff into the public header, but it's probably worth it.
I'm also moving the virtual destructor into the public header, so it can be inlined. (do_allocate becomes the new key function.)

test/std/experimental/memory/memory.resource.monotonic.buffer/nothing_to_do.pass.cpp

2

I was starting to wonder about this! Removed.

[• Quuxplusone]

Massive changes based on Eric's feedback. Moved constructors and destructors of monotonic_buffer_resource into the header so they can be completely inlined. Renamed struct __monotonic_buffer_foo_header to nested types monotonic_buffer_resource::__foo_header. Refactored for 80-column lines.

[EricWF]

In D47111#1151714, @Quuxplusone wrote:

I'll take a pass at the tests tomorrow. Some pointers in general:

• Tests should be named after the component they test, not how they're testing it.
• All the tests for a single component should be in the same file.

I'm certain I'm doing it fairly wrong and you'll have to give me specific handholds like "merge these two tests into one file", "rename this file to x.cpp", etc.
The current large number of files is only because *last* iteration, you told me to split up the tests from "one big monotonic_buffer.pass.cpp" into one file per test!

I'm sorry, I don't mean to jerk you around. I'm still learning to be a reviewer. I'll provide some specific examples to avoid the ambiguity from before.

The problem with "one file per component" is that I don't understand what a "component" is in this context. From last iteration, I know that "all of monotonic_buffer_resource" is too big of a component! I also know that it's impossible to test deallocate without also calling allocate, but the reverse is not true.

Again, my apologies.

[• Quuxplusone]

Oops, my previous diff had a stray ) in it, somehow.

[• Quuxplusone]

Long-delayed ping!

[• Quuxplusone]

Rebased on master. @EricWF @ldionne ping please?

[EricWF]

LGTM. The tests might need some XFAIL'ing, but otherwise I think this looks good.

Sorry for the wait.

[• Quuxplusone]

@EricWF ping? This still needs someone to land it; I don't have commit privs. Thanks!

[EricWF]

Some of the tests aren't passing with Trunk clang. Please fix these.

include/experimental/memory_resource

427

constexpr these constants if they're const?

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp

33

This check isn't passing with ToT clang.

44

Either remove this or uncomment them. Preferably the latter. More test coverage is better.

[• Quuxplusone]

@EricWF ping!

[• Quuxplusone]

Updated and addressed review comments.
test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp is now XFAILed on OSX platforms, using code copied-and-pasted from test/libcxx/language.support/support.dynamic/libcpp_deallocate.sh.cpp.

@EricWF ping!

[• Quuxplusone]

@EricWF ping!
and oops, I never submitted these comments, I guess.

include/experimental/memory_resource

427

Compare <ios>, which has "constexpr" in the synopsis comment but "static const" in the code.
However, I updated the diff to follow <random>'s example and use static _LIBCPP_CONSTEXPR const everywhere.

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp

33

Agreed, it won't pass unless the underlying new_delete_resource supports overaligned alignments, which isn't true unless the underlying runtime supports aligned new. Which isn't true on my MacBook.

I think the fix would be for me to copy all the XFAIL lines from test/libcxx/language.support/support.dynamic/libcpp_deallocate.sh.cpp, is that right?

[• Quuxplusone]

Rebased on master. @EricWF (cc @AlisdairM) ping!

[• Quuxplusone]

Rebased on master. Added _NOEXCEPT to the resource() method (this is OK per [res.on.exception.handling]/5).

@ckennelly ping!

[• Quuxplusone]

Rebased on master.

[strager]

include/experimental/memory_resource

428

Nit: Why isn't __default_buffer_alignment set to alignof(max_align_t) (which I think is 16)? I think alignof(max_align_t) is a good, portable default.

432–433

Nit: Would it make sense to use std::byte instead of char?

test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp

33

Nit: This test is named allocate_in_geometric_progression. I don't see any multiplication or anything happening in this test case. Did you mean to call this test something else, like release_deletes_upstream_memory?

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_deallocate.pass.cpp

29

Nit: What is the purpose of the r1 variable? Why not use mono1 everywhere instead (and rename mono1 to r1 if you like r1 better than mono1 as a name)?

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_exception_safety.pass.cpp

49–50

Nit: These assertions look unrelated to exception safety to me. (The test is named allocate_exception_safety.) I'd delete these assertions.

53–55

(Same comment as on lines 48-49 above. I'd delete these assertions.)

68–69

Question about the intended behavior of monotonic_buffer_resource:

If line 68 instead allocated 1 byte, and the byte could fit in the original heap allocation (line 51), should monotonic_buffer_resource return a byte from that original resource? In other words, should the following test pass?

repointable_resource upstream(std::experimental::pmr::new_delete_resource());
std::experimental::pmr::monotonic_buffer_resource mono1(&upstream);

globalMemCounter.reset();
mono1.allocate(1, 1);
const size_t first_new_size = globalMemCounter.last_new_size;
bool mono1_has_spare_capacity = first_new_size == 1;

upstream.which = std::experimental::pmr::null_memory_resource();
try {
    mono1.allocate(first_new_size, 1); // Force allocation from upstream.
    assert(false);
} catch (const std::bad_alloc&) {
    // we expect this
}

globalMemCounter.reset();
mono1.allocate(1, 1);
if (mono1_has_spare_capacity) {
  assert(globalMemCounter.checkNewCalledEq(0));
} else {
  assert(globalMemCounter.checkNewCalledEq(1));
}

Similarly, if monotonic_buffer_resource was given a buffer, and that buffer still has spare capacity, should that capacity be reused? In other words, should the following test pass?

int first_allocation_size = 20;
int second_allocation_size = 30;

auto *upstream = std::experimental::pmr::null_memory_resource();
char buffer[64];
assert(sizeof buffer >= first_allocation_size + second_allocation_size);
std::experimental::pmr::monotonic_buffer_resource mono1(buffer, sizeof buffer, upstream);

globalMemCounter.reset();
void *first_allocation = mono1.allocate(first_allocation_size, 1);
assert(first_allocation == &buffer[0]);

try {
    mono1.allocate(sizeof buffer, 1); // Force allocation from upstream.
    assert(false);
} catch (const std::bad_alloc&) {
    // we expect this
}

void *second_allocation = mono1.allocate(second_allocation_size, 1);
assert(second_allocation == &buffer[second_allocation_size]);

I think these scenarios would be useful to test, in addition to the scenario in your test here.

[strager]

include/experimental/memory_resource

434

Eric suggests replacing size_t align_ with uint8_t log2_align_. I'm amenable to this idea, but I'd want to know what's the best way to compute the log2 of a user-supplied number.

Perhaps std::log2p1 could help: https://en.cppreference.com/w/cpp/numeric/log2p1

[• Quuxplusone]

include/experimental/memory_resource

428

Will users be more upset if __default_buffer_alignment is 16-instead-of-??? on exotic platform ???; or more upset if __default_buffer_alignment is usually 16 but then sometimes is ???-instead-of-16 on exotic platforms? I tend to think that "usually 16, sometimes something else" is worse behavior software-engineering-wise than "always 16, even when something else might arguably be better on exotic platform ???."

432–433

IMHO "strong no"; char is the standard core-language type that takes up one byte. std::byte is an enum type that we'd have to drag in from a header (cost), and otherwise behaves just like char (no benefit). But it's certainly a non-functional nit and I would not put up a fight if libc++ wanted it that way. :)

434

Yes, but that's C++2a; I imagine some fiddliness would be needed to use it in C++17 library code (which in turn is actually compiled as C++11 or '14, I forget).

test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp

33

Prior to the resolution of LWG 3120, this test had tested something else. I guess now it should be more like "release_resets_initial_buffer.pass.cpp".

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_deallocate.pass.cpp

29

r1 has a different static type. For example, here it's testing that r1.allocate(50) actually makes a virtual call to monotonic_buffer_resource::do_allocate. But I guess it doesn't really matter; I could use mono1 for everything just as well.

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_exception_safety.pass.cpp

49–50

Depends on your test-overfitting philosophy. These assertions are still expected to pass 100% of the time — if they fail, then something is definitely wrong. And they're cheap to execute. So IMHO they might as well be there, as "self-documenting code."

68–69

If [the request] could fit in the original heap allocation, should monotonic_buffer_resource return a byte from that original allocation?
Similarly, if monotonic_buffer_resource was given a buffer, and that buffer still has spare capacity, should that capacity be reused?

In both cases, the Standard says "absolutely not": mem.res.monotonic.buffer.mem#5. I can add these tests.

[ldionne]

Can we please close this review as it's been superseded by D89057?

[• Quuxplusone]

Sure; not that D89057 is making any more progress... :)

include/experimental/memory_resource

private:
     }
 };
 
 template <class _Alloc>
 using resource_adaptor = __resource_adaptor_imp<
     typename allocator_traits<_Alloc>::template rebind_alloc<char>
   >;
 
+// 23.12.6, mem.res.monotonic.buffer
+
+struct __monotonic_buffer_chunk_header;
+
+struct __monotonic_buffer_initial_header {
+    char *__start_;
+    char *__cur_;
+    union {
+        char *__end_;
+        size_t __size_;
+    };
+    void *try_allocate_from_chunk(size_t, size_t);
+};
+
+class _LIBCPP_TYPE_VIS monotonic_buffer_resource : public memory_resource
+{
+    static const size_t __default_buffer_capacity = 1024;
+    static const size_t __default_buffer_alignment = 16;
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    explicit monotonic_buffer_resource(memory_resource* __upstream)
+        : monotonic_buffer_resource(nullptr, __default_buffer_capacity, __upstream) {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    monotonic_buffer_resource(size_t __initial_size, memory_resource* __upstream)
+        : monotonic_buffer_resource(nullptr, __initial_size, __upstream) {}
+
+    monotonic_buffer_resource(void* __buffer, size_t __buffer_size, memory_resource* __upstream);
+
+    _LIBCPP_INLINE_VISIBILITY
+    monotonic_buffer_resource()
+        : monotonic_buffer_resource(get_default_resource()) {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit monotonic_buffer_resource(size_t __initial_size)
+        : monotonic_buffer_resource(__initial_size, get_default_resource()) {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    monotonic_buffer_resource(void* __buffer, size_t __buffer_size)
+        : monotonic_buffer_resource(__buffer, __buffer_size, get_default_resource()) {}
+
+    monotonic_buffer_resource(const monotonic_buffer_resource&) = delete;
+
+    ~monotonic_buffer_resource() override; // key function
+
+    monotonic_buffer_resource& operator=(const monotonic_buffer_resource&) = delete;
+
+    void release();
+
+    _LIBCPP_INLINE_VISIBILITY
+    memory_resource* upstream_resource() const
+        { return __res_; }
+
+protected:
+    void* do_allocate(size_t __bytes, size_t __alignment) override;
+
+    _LIBCPP_INLINE_VISIBILITY
+    void do_deallocate(void*, size_t, size_t) override
+        {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool do_is_equal(const memory_resource& __other) const _NOEXCEPT override
+        { return this == _VSTD::addressof(__other); }
+
+private:
+    size_t __previous_allocation_size() const;
+
+    __monotonic_buffer_initial_header __initial_;
+    __monotonic_buffer_chunk_header *__chunks_;
+    memory_resource* __res_;
+};
+
 _LIBCPP_END_NAMESPACE_LFTS_PMR
 
 _LIBCPP_POP_MACROS
 
 #endif /* _LIBCPP_EXPERIMENTAL_MEMORY_RESOURCE */

src/experimental/memory_resource.cpp

memory_resource * get_default_resource() _NOEXCEPT
     return __default_memory_resource();
 }
 
 memory_resource * set_default_resource(memory_resource * __new_res) _NOEXCEPT
 {
     return __default_memory_resource(true, __new_res);
 }
 
+// 23.12.6, mem.res.monotonic.buffer
+
+static size_t roundup(size_t count, size_t alignment)
+{
+    size_t mask = alignment - 1;
+    return (count + mask) & ~mask;
+}
+
+void *__monotonic_buffer_initial_header::try_allocate_from_chunk(size_t bytes, size_t align)
+{
+    if (!__cur_)
+        return nullptr;
+    void *new_ptr = static_cast<void*>(__cur_);
+    size_t new_capacity = (__end_ - __cur_);
+    void *aligned_ptr = _VSTD::align(align, bytes, new_ptr, new_capacity);
+    if (aligned_ptr != nullptr) {
+        __cur_ = static_cast<char*>(new_ptr) + bytes;
+    }
+    return aligned_ptr;
+}
+
+struct __monotonic_buffer_chunk_header {
+    __monotonic_buffer_chunk_header *__next_;
+    char *__start_;
+    char *__cur_;
+    size_t __align_;
+    size_t allocation_size() {
+        return (reinterpret_cast<char*>(this) - __start_) + sizeof(*this);
+    }
+    void *try_allocate_from_chunk(size_t bytes, size_t align);
+    void deallocate_self(memory_resource *upstream);
+};
+
+void *__monotonic_buffer_chunk_header::try_allocate_from_chunk(size_t bytes, size_t align)
+{
+    void *new_ptr = static_cast<void*>(__cur_);
+    size_t new_capacity = (reinterpret_cast<char*>(this) - __cur_);
+    void *aligned_ptr = _VSTD::align(align, bytes, new_ptr, new_capacity);
+    if (aligned_ptr != nullptr) {
+        __cur_ = static_cast<char*>(new_ptr) + bytes;
+    }
+    return aligned_ptr;
+}
+
+void __monotonic_buffer_chunk_header::deallocate_self(memory_resource *upstream)
+{
+    upstream->deallocate(__start_, allocation_size(), __align_);
+}
+
+monotonic_buffer_resource::monotonic_buffer_resource(void* buffer, size_t buffer_size, memory_resource* upstream)
+    : __res_(upstream)
+{
+    __initial_.__start_ = static_cast<char *>(buffer);
+    if (buffer != nullptr) {
+        __initial_.__cur_ = static_cast<char *>(buffer);
+        __initial_.__end_ = static_cast<char *>(buffer) + buffer_size;
+    } else {
+        __initial_.__cur_ = nullptr;
+        __initial_.__size_ = buffer_size;
+    }
+    __chunks_ = nullptr;
+}
+
+monotonic_buffer_resource::~monotonic_buffer_resource()
+{
+    release();
+}
+
+void monotonic_buffer_resource::release()
+{
+    __initial_.__cur_ = __initial_.__start_;
+    while (__chunks_ != nullptr) {
+        __monotonic_buffer_chunk_header *next = __chunks_->__next_;
+        __chunks_->deallocate_self(__res_);
+        __chunks_ = next;
+    }
+}
+
+void* monotonic_buffer_resource::do_allocate(size_t bytes, size_t align)
+{
+    if (void *result = __initial_.try_allocate_from_chunk(bytes, align))
+        return result;
+    if (__chunks_ != nullptr) {
+        if (void *result = __chunks_->try_allocate_from_chunk(bytes, align))
+            return result;
+    }
+
+    // Allocate a brand-new chunk.
+    const size_t header_size = sizeof(__monotonic_buffer_chunk_header);
+    const size_t header_align = alignof(__monotonic_buffer_chunk_header);
+
+    if (align < header_align)
+        align = header_align;
+
+    size_t aligned_capacity = roundup(bytes, header_align) + header_size;
+    size_t previous_capacity = __previous_allocation_size();
+
+    if (aligned_capacity <= previous_capacity)
+        aligned_capacity = roundup(2 * (previous_capacity - header_size), header_align) + header_size;
+
+    char *start = (char *)__res_->allocate(aligned_capacity, align);
+    __monotonic_buffer_chunk_header *header = (__monotonic_buffer_chunk_header *)(start + aligned_capacity - header_size);
+    header->__next_ = __chunks_;
+    header->__start_ = start;
+    header->__cur_ = start;
+    header->__align_ = align;
+    __chunks_ = header;
+
+    return __chunks_->try_allocate_from_chunk(bytes, align);
+}
+
+size_t monotonic_buffer_resource::__previous_allocation_size() const
+{
+    const size_t header_size = sizeof(__monotonic_buffer_chunk_header);
+    const size_t header_align = alignof(__monotonic_buffer_chunk_header);
+
+    if (__chunks_ != nullptr) {
+        return __chunks_->allocation_size();
+    } else if (__initial_.__start_ != nullptr) {
+        return roundup(__initial_.__end_ - __initial_.__start_, header_align) + header_size;
+    } else {
+        return roundup(__initial_.__size_, header_align) + header_size;
+    }
+}
+
 _LIBCPP_END_NAMESPACE_LFTS_PMR

test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    globalMemCounter.reset();
+    std::experimental::pmr::monotonic_buffer_resource mono;
+
+    for (int i=0; i < 100; ++i) {
+        mono.allocate(1);
+        assert(globalMemCounter.last_new_size < 1000000000);
+        mono.release();
+        assert(globalMemCounter.checkOutstandingNewEq(0));
+    }
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.ctor/copy_move.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// monotonic_buffer_resource(monotonic_buffer_resource const&) = delete;
+// monotonic_buffer_resource& operator=(monotonic_buffer_resource const&) = delete;
+
+#include <experimental/memory_resource>
+#include <type_traits>
+#include <cassert>
+
+int main()
+{
+    using MBR = std::experimental::pmr::monotonic_buffer_resource;
+    static_assert(!std::is_copy_constructible<MBR>::value, "");
+    static_assert(!std::is_move_constructible<MBR>::value, "");
+    static_assert(!std::is_copy_assignable<MBR>::value, "");
+    static_assert(!std::is_move_assignable<MBR>::value, "");
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.ctor/with_default_resource.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+int main()
+{
+    std::experimental::pmr::memory_resource *expected = std::experimental::pmr::null_memory_resource();
+    std::experimental::pmr::set_default_resource(expected);
+    {
+        char buffer[16];
+        std::experimental::pmr::monotonic_buffer_resource r1;
+        std::experimental::pmr::monotonic_buffer_resource r2(16);
+        std::experimental::pmr::monotonic_buffer_resource r3(buffer, sizeof buffer);
+        assert(r1.upstream_resource() == expected);
+        assert(r2.upstream_resource() == expected);
+        assert(r3.upstream_resource() == expected);
+    }
+
+    expected = std::experimental::pmr::new_delete_resource();
+    std::experimental::pmr::set_default_resource(expected);
+    {
+        char buffer[16];
+        std::experimental::pmr::monotonic_buffer_resource r1;
+        std::experimental::pmr::monotonic_buffer_resource r2(16);
+        std::experimental::pmr::monotonic_buffer_resource r3(buffer, sizeof buffer);
+        assert(r1.upstream_resource() == expected);
+        assert(r2.upstream_resource() == expected);
+        assert(r3.upstream_resource() == expected);
+    }
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.ctor/without_buffer.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    // Constructing a monotonic_buffer_resource should not cause allocations
+    // by itself; the resource should wait to allocate until an allocation is
+    // requested.
+
+    globalMemCounter.reset();
+    std::experimental::pmr::set_default_resource(std::experimental::pmr::new_delete_resource());
+
+    std::experimental::pmr::monotonic_buffer_resource r1;
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    std::experimental::pmr::monotonic_buffer_resource r2(1024);
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    std::experimental::pmr::monotonic_buffer_resource r3(1024, std::experimental::pmr::new_delete_resource());
+    assert(globalMemCounter.checkNewCalledEq(0));
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_deallocate.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    {
+        globalMemCounter.reset();
+
+        std::experimental::pmr::monotonic_buffer_resource mono1(std::experimental::pmr::new_delete_resource());
+        std::experimental::pmr::memory_resource & r1 = mono1;
+
+        void *ret = r1.allocate(50);
+        assert(ret);
+        assert(globalMemCounter.checkNewCalledGreaterThan(0));
+        assert(globalMemCounter.checkDeleteCalledEq(0));
+
+        // mem.res.monotonic.buffer 1.2
+        // A call to deallocate has no effect, thus the amount of memory
+        // consumed increases monotonically until the resource is destroyed.
+        // Check that deallocate is a no-op
+        r1.deallocate(ret, 50);
+        assert(globalMemCounter.checkDeleteCalledEq(0));
+
+        mono1.release();
+        assert(globalMemCounter.checkDeleteCalledEq(1));
+        assert(globalMemCounter.checkOutstandingNewEq(0));
+
+        globalMemCounter.reset();
+
+        ret = r1.allocate(500);
+        assert(ret);
+        assert(globalMemCounter.checkNewCalledGreaterThan(0));
+        assert(globalMemCounter.checkDeleteCalledEq(0));
+
+        // Check that the destructor calls release()
+    }
+    assert(globalMemCounter.checkDeleteCalledEq(1));
+    assert(globalMemCounter.checkOutstandingNewEq(0));
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_exception_safety.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+struct repointable_resource : public std::experimental::pmr::memory_resource
+{
+    std::experimental::pmr::memory_resource *which;
+
+    explicit repointable_resource(std::experimental::pmr::memory_resource *res) : which(res) {}
+
+protected:
+    virtual void *do_allocate(size_t size, size_t align)
+    { return which->allocate(size, align); }
+
+    virtual void do_deallocate(void *p, size_t size, size_t align)
+    { return which->deallocate(p, size, align); }
+
+    virtual bool do_is_equal(std::experimental::pmr::memory_resource const &rhs) const noexcept
+    { return which->is_equal(rhs); }
+};
+
+int main()
+{
+    globalMemCounter.reset();
+    repointable_resource upstream(std::experimental::pmr::new_delete_resource());
+    alignas(16) char buffer[64];
+    std::experimental::pmr::monotonic_buffer_resource mono1(buffer, sizeof buffer, &upstream);
+    std::experimental::pmr::memory_resource & r1 = mono1;
+
+    void *res = r1.allocate(64, 16);
+    assert(res == buffer);
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    res = r1.allocate(64, 16);
+    assert(res != buffer);
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.checkDeleteCalledEq(0));
+    const size_t last_new_size = globalMemCounter.last_new_size;
+
+    upstream.which = std::experimental::pmr::null_memory_resource();
+    try {
+        res = r1.allocate(last_new_size, 16);
+        assert(false);
+    } catch (const std::bad_alloc&) {
+        // we expect this
+    }
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.checkDeleteCalledEq(0));
+
+    upstream.which = std::experimental::pmr::new_delete_resource();
+    res = r1.allocate(last_new_size, 16);
+    assert(res != buffer);
+    assert(globalMemCounter.checkNewCalledEq(2));
+    assert(globalMemCounter.checkDeleteCalledEq(0));
+
+    mono1.release();
+    assert(globalMemCounter.checkNewCalledEq(2));
+    assert(globalMemCounter.checkDeleteCalledEq(2));
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_from_initial_buffer.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    globalMemCounter.reset();
+    char buffer[100];
+    std::experimental::pmr::monotonic_buffer_resource mono1((void *)buffer, sizeof buffer, std::experimental::pmr::new_delete_resource());
+    std::experimental::pmr::memory_resource & r1 = mono1;
+
+    // Check that construction with a buffer does not allocate anything from the upstream
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    // Check that an allocation that fits in the buffer does not allocate anything from the upstream
+    void *ret = r1.allocate(50);
+    assert(ret);
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    // Check a second allocation
+    ret = r1.allocate(20);
+    assert(ret);
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    r1.deallocate(ret, 50);
+    assert(globalMemCounter.checkDeleteCalledEq(0));
+
+    // Check an allocation that doesn't fit in the original buffer
+    ret = r1.allocate(50);
+    assert(ret);
+    assert(globalMemCounter.checkNewCalledEq(1));
+
+    r1.deallocate(ret, 50);
+    assert(globalMemCounter.checkDeleteCalledEq(0));
+
+    mono1.release();
+    assert(globalMemCounter.checkDeleteCalledEq(1));
+    assert(globalMemCounter.checkOutstandingNewEq(0));
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    globalMemCounter.reset();
+    {
+        alignas(4) char buffer[17];
+        std::experimental::pmr::monotonic_buffer_resource mono1(buffer + 1, 16, std::experimental::pmr::new_delete_resource());
+        std::experimental::pmr::memory_resource & r1 = mono1;
+
+        void *ret = r1.allocate(1, 1);
+        assert(ret == buffer + 1);
+        mono1.release();
+
+        ret = r1.allocate(1, 2);
+        assert(ret == buffer + 2);
+        mono1.release();
+
+        ret = r1.allocate(1, 4);
+        assert(ret == buffer + 4);
+        mono1.release();
+
+        // Test a size that is just big enough to fit in the buffer,
+        // but can't fit if it's aligned.
+        ret = r1.allocate(16, 1);
+        assert(ret == buffer + 1);
+        mono1.release();
+
+        assert(globalMemCounter.checkNewCalledEq(0));
+        ret = r1.allocate(16, 2);
+        assert(globalMemCounter.checkNewCalledEq(1));
+        assert(globalMemCounter.last_new_size >= 16);
+        // assert(globalMemCounter.last_new_align >= 2);
+        mono1.release();
+        assert(globalMemCounter.checkDeleteCalledEq(1));
+        // assert(globalMemCounter.last_new_align == globalMemCounter.last_delete_align);
+    }
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_from_zero_sized_buffer.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    globalMemCounter.reset();
+    {
+        char buffer[100];
+        std::experimental::pmr::monotonic_buffer_resource mono1((void *)buffer, 0, std::experimental::pmr::new_delete_resource());
+        std::experimental::pmr::memory_resource & r1 = mono1;
+
+        void *ret = r1.allocate(1, 1);
+        assert(ret != nullptr);
+        assert(globalMemCounter.checkNewCalledEq(1));
+    }
+    assert(globalMemCounter.checkDeleteCalledEq(1));
+
+    globalMemCounter.reset();
+    {
+        std::experimental::pmr::monotonic_buffer_resource mono1(nullptr, 0, std::experimental::pmr::new_delete_resource());
+        std::experimental::pmr::memory_resource & r1 = mono1;
+
+        void *ret = r1.allocate(1, 1);
+        assert(ret != nullptr);
+        assert(globalMemCounter.checkNewCalledEq(1));
+    }
+    assert(globalMemCounter.checkDeleteCalledEq(1));
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+void test_geometric_progression()
+{
+    // mem.res.monotonic.buffer 1.3
+    // Each additional buffer is larger than the previous one, following a
+    // geometric progression.
+
+    globalMemCounter.reset();
+    std::experimental::pmr::monotonic_buffer_resource mono1(100, std::experimental::pmr::new_delete_resource());
+    std::experimental::pmr::memory_resource & r1 = mono1;
+
+    assert(globalMemCounter.checkNewCalledEq(0));
+    size_t next_buffer_size = 100;
+    void *ret = r1.allocate(10, 1);
+    assert(ret != nullptr);
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.last_new_size >= next_buffer_size);
+    next_buffer_size = globalMemCounter.last_new_size + 1;
+
+    int new_called = 1;
+    while (new_called < 5) {
+        ret = r1.allocate(10, 1);
+        if (globalMemCounter.new_called > new_called) {
+            assert(globalMemCounter.new_called == new_called + 1);
+            assert(globalMemCounter.last_new_size >= next_buffer_size);
+            next_buffer_size = globalMemCounter.last_new_size + 1;
+            new_called += 1;
+        }
+    }
+}
+
+int main()
+{
+    test_geometric_progression();
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+int main()
+{
+    globalMemCounter.reset();
+    std::experimental::pmr::monotonic_buffer_resource mono1(1024, std::experimental::pmr::new_delete_resource());
+    std::experimental::pmr::memory_resource & r1 = mono1;
+
+    constexpr size_t big_alignment = 8 * alignof(std::max_align_t);
+    static_assert(big_alignment > 4);
+
+    void *ret = r1.allocate(2048, big_alignment);
+    assert(ret != nullptr);
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.last_new_size >= 2048);
+    // assert(globalMemCounter.last_new_align >= big_alignment);
+
+    // Check that a single highly aligned allocation request doesn't
+    // permanently "poison" the resource to allocate only super-aligned
+    // blocks of memory.
+    ret = r1.allocate(globalMemCounter.last_new_size, 4);
+    assert(ret != nullptr);
+    assert(globalMemCounter.checkNewCalledEq(2));
+    // assert(globalMemCounter.last_new_align >= 4);
+    // assert(globalMemCounter.last_new_align < big_alignment);
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_with_initial_size.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <cassert>
+
+#include "count_new.hpp"
+
+void test(size_t initial_buffer_size)
+{
+    globalMemCounter.reset();
+
+    std::experimental::pmr::monotonic_buffer_resource mono1(
+        initial_buffer_size,
+        std::experimental::pmr::new_delete_resource()
+    );
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    mono1.allocate(1, 1);
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.last_new_size >= initial_buffer_size);
+
+    mono1.allocate(initial_buffer_size - 1, 1);
+    assert(globalMemCounter.checkNewCalledEq(1));
+}
+
+int main()
+{
+    test(1);
+    test(8);
+    test(10);
+    test(100);
+    test(256);
+    test(1000);
+    test(1024);
+    test(1000000);
+    assert(globalMemCounter.checkOutstandingNewEq(0));
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/equality.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: c++experimental
+// UNSUPPORTED: c++98, c++03
+
+// <experimental/memory_resource>
+
+// class monotonic_buffer_resource
+
+#include <experimental/memory_resource>
+#include <new>
+#include <type_traits>
+#include <cassert>
+
+struct assert_on_compare : public std::experimental::pmr::memory_resource
+{
+protected:
+    virtual void * do_allocate(size_t, size_t)
+    { assert(false); }
+
+    virtual void do_deallocate(void *, size_t, size_t)
+    { assert(false); }
+
+    virtual bool do_is_equal(std::experimental::pmr::memory_resource const &) const noexcept
+    { assert(false); }
+};
+
+int main()
+{
+    // Same object
+    {
+        std::experimental::pmr::monotonic_buffer_resource r1;
+        std::experimental::pmr::monotonic_buffer_resource r2;
+        assert(r1 == r1);
+        assert(r1 != r2);
+
+        std::experimental::pmr::memory_resource & p1 = r1;
+        std::experimental::pmr::memory_resource & p2 = r2;
+        assert(p1 == p1);
+        assert(p1 != p2);
+        assert(p1 == r1);
+        assert(r1 == p1);
+        assert(p1 != r2);
+        assert(r2 != p1);
+    }
+    // Different types
+    {
+        std::experimental::pmr::monotonic_buffer_resource mono1;
+        std::experimental::pmr::memory_resource & r1 = mono1;
+        assert_on_compare c;
+        std::experimental::pmr::memory_resource & r2 = c;
+        assert(r1 != r2);
+        assert(!(r1 == r2));
+    }
+}

test/std/experimental/memory/memory.resource.monotonic.buffer/nothing_to_do.pass.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+int main()
+{
+}