1405795 - Clean-up LifoAlloc single-linked lists of BumpChunk.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Nicolas B. Pierron [:nbp]]

The goal of this bug is to clean-up a bit our LifoAlloc code to ensure that it is safe.  So far it does not seems to have issues, but the first/last/latest fields are a bit harder to reason about, and the fields of the BumpChunk are not necessary obvious.

The first idea here is to use UniquePtr to represent the single linked list of the LifoAlloc, such that we can ensure that no BumpChunk is used twice in 2 different LifoAlloc.

The second idea is to rename BumpChunk fields to make it look more like a vector of bytes, with a begin(), end() and a capacity.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Use UniquePtr for the single-linked list of the LifoAlloc.

This patch does multiple things:
 - Rename BumpChunk::limit to BumpChunk::capcity_, to make it look more like
   a vector of bytes.
 - Add a SingleLinkedList using UniquePtr.
 - Split LifoAlloc  first/last/latest into 2 list of chunks, one for the
   ordered allocated chunks, and a second one for the set of unused chunks.
 - getOrCreateChunk now look for the first unused chunk which fit the next
   allocation, instead of pulling larger number of unused empty chunks in
   the list of used chunks.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=6df4842cf0e50ba2ca8c93457e5414599f9447e8

Comment 2

[Luke Wagner [:luke]]

Comment on attachment 8915267 [details] [diff] [review]
Use UniquePtr for the single-linked list of the LifoAlloc.

Review of attachment 8915267 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good!

::: js/src/ds/LifoAlloc.h
@@ +75,5 @@
> +        assertInvariants();
> +    }
> +
> +    SingleLinkedList(SingleLinkedList&& other)
> +      : head_(mozilla::Move(other.head_)), last_(mozilla::Move(other.last_))

nit: don't need Move() on last_.

@@ +150,5 @@
> +    }
> +
> +    void pushFront(UniquePtr<T>&& elem) {
> +        if (!head_)
> +            last_ = elem.get();

nit: I think it'd be a tad bit simpler to say "if (!last_)" since that's what we're assigning and since that is how empty() is defined.

@@ +166,5 @@
> +            last_ = head_.get();
> +        }
> +        assertInvariants();
> +    }
> +    void appendAll(SingleLinkedList& list) {

I think this should take a SingleLinkedList&& given that the contents are moved from list

@@ +230,5 @@
> +        MOZ_ASSERT(end() <= capacity_);
> +    }
> +
> +    BumpChunk(BumpChunk&) = delete;
> +    BumpChunk(const BumpChunk&) = delete;

I don't think you have to delete 'BumpChunk(BumpChunk&)' since there's no default there.  Instead, can you delete op=, which does have a default?

@@ +304,5 @@
> +
> +    // Space reserved for the BumpChunk internal data, and the alignment of the
> +    // first allocation content.  This can be used to ensure there is enough
> +    // space for the next allocation. (see LifoAlloc::newChunkWithCapacity)
> +    static const size_t reservedSpace;

I think the initializer is a constexpr and could be computed in the .h which I think will avoid a load.

@@ +442,5 @@
>          MOZ_ASSERT(mozilla::RoundUpPow2(defaultChunkSize) == defaultChunkSize);
> +        while (!chunks_.empty())
> +            chunks_.popFirst();
> +        while (!unused_.empty())
> +            unused_.popFirst();

Wow, the previous version of this function was super-dangerous and atypical.

Comment 3

[Jan de Mooij [:jandem]]

Comment on attachment 8915267 [details] [diff] [review]
Use UniquePtr for the single-linked list of the LifoAlloc.

Review of attachment 8915267 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM.

::: js/src/ds/LifoAlloc.cpp
@@ +15,5 @@
>  
>  namespace js {
>  namespace detail {
>  
> +const size_t BumpChunk::reservedSpace =

Yes would be nice to have this in the header file.

::: js/src/ds/LifoAlloc.h
@@ +129,5 @@
> +    Iterator begin() const { return Iterator(head_.get()); }
> +    Iterator end() const { return Iterator(nullptr); }
> +    Iterator last() const { return Iterator(last_); }
> +
> +    // Split the list in 2 single linked list after the element given as

Nit: s/list/lists/ (the second one)

@@ +794,4 @@
>          }
>  
> +        // Return a pointer to the item at the current position. This returns a
> +        // pointer to the inline storage, not a copy, and move the read-head by

Nit: moves

Comment 4

[Nicolas B. Pierron [:nbp]]

(In reply to Luke Wagner [:luke] from comment #2)
> @@ +304,5 @@
> > +
> > +    // Space reserved for the BumpChunk internal data, and the alignment of the
> > +    // first allocation content.  This can be used to ensure there is enough
> > +    // space for the next allocation. (see LifoAlloc::newChunkWithCapacity)
> > +    static const size_t reservedSpace;
> 
> I think the initializer is a constexpr and could be computed in the .h which
> I think will avoid a load.

The reason I initially moved to the cpp file was because we cannot assign "sizeof(BumpChunk)" to a const or constexpr within the BumpChunk scope.

I tried to move the "const" definition to the header, but I ended up with a linking issue as the linker see one definition per .o file.

I tried to define it after, but I cannot make it a constexpr because AlignBytes has a MOZ_ASSERT which I prefer to keep.

Thus I changed it to

    static constexpr size_t reservedSpace = 4 * sizeof(uintptr_t);

and added the previous expression as a MOZ_ASSERT in the BumpChunk constructor.

Comment 5

[Luke Wagner [:luke]]

Ah, I was worried it was something like that and, yeah, the sizeof(uintptr_t) + static assert seems like the best way to go.

Comment 6

[Nicolas B. Pierron [:nbp]]

Tested on Try, since the previous push did not trigger any build:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=8bb2c501adb75a6f7f38810cbe652d8c3386e678

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/80d704c66781
Use UniquePtr for the single-linked lists of LifoAlloc. r=jandem,luke

Comment 8

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/80d704c66781