- Swap() was not necessary as all uses merely required Merge()
- Remove unused empty Local ctor
- Use refrence for backref as it's always supposed to be non-null

Bug: v8:13193
Change-Id: Ide0a0de15185a67d028890371ae30528fd55a058
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3846863Reviewed-by: Dominik Inführ <dinfuehr@chromium.org>
Reviewed-by: Anton Bikineev <bikineev@chromium.org>
Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
Cr-Commit-Position: refs/heads/main@{#82648}

This is a reland of commit a19316d9

- Revert malloc_usable_size() changes temporarily to land them in
  isolation.
- Add cosmetics from https://crrev.com/c/3827876

Original change's description:
> [heap] Rework Worklist base type
>
> Worklist uses a singly-linked list of segments to hold entries.
> Segment size was based on a compile-time constant but already stored
> in the segment itself.
>
> Rework the segments to query `malloc_usable_size()` on allocation and
> adjust the capacity properly. For PartitionAlloc, it turns out that
> there's ~20% more capacity available for the 64-element segments.
>
> This slows down actual allocation of the segments with the upside of
> improving utilization and requiring 20% less segments.
>
> Change-Id: Ib8595c3fb9fb75b02e4022f6c525bb59a2df7ab7
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3826047
> Commit-Queue: Anton Bikineev <bikineev@chromium.org>
> Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
> Reviewed-by: Anton Bikineev <bikineev@chromium.org>
> Cr-Commit-Position: refs/heads/main@{#82432}

Change-Id: Ic8c5257cfe3c347b11eea5c513ca7f62e09f637f
Bug: v8:13193
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3829475Reviewed-by: Anton Bikineev <bikineev@chromium.org>
Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
Cr-Commit-Position: refs/heads/main@{#82493}

This reverts commit a19316d9.

Reason for revert: https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Linux64%20UBSan/22670/overview

Original change's description:
> [heap] Rework Worklist base type
>
> Worklist uses a singly-linked list of segments to hold entries.
> Segment size was based on a compile-time constant but already stored
> in the segment itself.
>
> Rework the segments to query `malloc_usable_size()` on allocation and
> adjust the capacity properly. For PartitionAlloc, it turns out that
> there's ~20% more capacity available for the 64-element segments.
>
> This slows down actual allocation of the segments with the upside of
> improving utilization and requiring 20% less segments.
>
> Change-Id: Ib8595c3fb9fb75b02e4022f6c525bb59a2df7ab7
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3826047
> Commit-Queue: Anton Bikineev <bikineev@chromium.org>
> Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
> Reviewed-by: Anton Bikineev <bikineev@chromium.org>
> Cr-Commit-Position: refs/heads/main@{#82432}

Change-Id: I14994e11ff5ffaba70b93d977d40dd2f6e9e5d35
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3829474
Owners-Override: Nico Hartmann <nicohartmann@chromium.org>
Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Auto-Submit: Nico Hartmann <nicohartmann@chromium.org>
Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Cr-Commit-Position: refs/heads/main@{#82438}

Worklist uses a singly-linked list of segments to hold entries.
Segment size was based on a compile-time constant but already stored
in the segment itself.

Rework the segments to query `malloc_usable_size()` on allocation and
adjust the capacity properly. For PartitionAlloc, it turns out that
there's ~20% more capacity available for the 64-element segments.

This slows down actual allocation of the segments with the upside of
improving utilization and requiring 20% less segments.

Change-Id: Ib8595c3fb9fb75b02e4022f6c525bb59a2df7ab7
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3826047
Commit-Queue: Anton Bikineev <bikineev@chromium.org>
Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
Reviewed-by: Anton Bikineev <bikineev@chromium.org>
Cr-Commit-Position: refs/heads/main@{#82432}

Instead of using the high water mark for determining this metric, we use
a bitset for all active/used system pages on a V8 heap page. Each time
when allocating a LAB on a page, we add the pages of that memory range
to that bitset. During sweeping we rebuild that bitset from scratch and
replace it with the old one in case free pages are discarded by the GC.
We DCHECK here that the sweeper only ever removes pages. This has the
nice benefit of ensuring that we don't miss any allocations (like we
do now for concurrent allocations).

CommittedPhysicalMemory for a page is then calculated by counting the
set bits in the bitset and multiplying it with the system page size.
This should be simpler to verify and track the "real" effective size
more precisely.

One case where we are partially less precise than the current
implementation is for LABs. In order to reduce complexity we now treat
all pages of a LAB allocation as active immediately. In the current
implementation we tried to only account the actual used part of the LAB
when changing the LAB later. This is more complex to track correctly
but also doesn't account the currently used LAB in effective size.

Change-Id: Ia83df9ad5fbb852f0717c4c396b5074604bd21e9
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3497363Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
Commit-Queue: Dominik Inführ <dinfuehr@chromium.org>
Cr-Commit-Position: refs/heads/main@{#79428}

- Removes the unused Worklist implementation. All uses now refer to
  ::heap::base::Worklist.
- Renames CppgcWorklistTest -> WorklistTest
- Add test for Swap()

Bug: v8:12426
Change-Id: I62c3472c030b853a846cf13ab48597ea1af8f700
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3306507Reviewed-by: Dominik Inführ <dinfuehr@chromium.org>
Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
Cr-Commit-Position: refs/heads/main@{#78208}

Bug: v8:10990
Change-Id: I5166d9ecd6d8d8c55ecb17015d99d88ed60effa2
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2488680
Commit-Queue: Omer Katz <omerkatz@chromium.org>
Commit-Queue: Michael Lippautz <mlippautz@chromium.org>
Auto-Submit: Omer Katz <omerkatz@chromium.org>
Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
Cr-Commit-Position: refs/heads/master@{#70668}

This is a reland of f25cb50a

Removed the problematic tests.
The problem with the test was that we try to pop from an empty segment.
GCC flags that as accessing beyond the array (i.e. index is uint16_t
equivalent of -1). Preceding the actual pop is a DCHECK that asserts
the segment isn't empty. In practice, since we have the DCHECK and
access to the segment is always via a Local, this shouldn't be a
problem.
Unfortunately, GCC flags the access regardless. The DCHECK goes through
a function pointer so GCC cannot determine that in our unittest the
DCHECK would crash if index is 0 and the access would not happen (The
indirection was added to allow for test DCHECK handlers that don't
crash, so we can't mark the function pointer as noreturn).

Drive-by: Segment::Pop and Segment::Push rely on the their Local
counterparts checking of emptiness/fullness, so we should always
access segments via Locals. Making the Segment ctor private.

Original change's description:
> Reland "cppgc, heap: Don't eagerly allocate worklist segments"
>
> This is a reland of c99147c6
>
> Original change's description:
> > cppgc, heap: Don't eagerly allocate worklist segments
> >
> > Bug: chromium:1056170
> > Change-Id: I75a6b5f52bfe8dd71abc086e5d1e060759ad7fc0
> > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2391254
> > Commit-Queue: Omer Katz <omerkatz@chromium.org>
> > Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
> > Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
> > Cr-Commit-Position: refs/heads/master@{#69778}
>
> Bug: chromium:1056170
> Change-Id: I4633da065976a6b2710d2f23b946fd2af0e65c83
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2401425
> Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
> Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
> Commit-Queue: Omer Katz <omerkatz@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#69806}

Bug: chromium:1056170
Change-Id: I7a122d1a2d20cd4e7c824d249975b4d3df30e03e
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2403251Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
Commit-Queue: Omer Katz <omerkatz@chromium.org>
Cr-Commit-Position: refs/heads/master@{#69829}

This reverts commit f25cb50a.

Reason for revert: Fails compilation on gcc https://ci.chromium.org/p/v8/builders/ci/V8%20Linux64%20gcc%20-%20debug/9026?

Original change's description:
> Reland "cppgc, heap: Don't eagerly allocate worklist segments"
> 
> This is a reland of c99147c6
> 
> Original change's description:
> > cppgc, heap: Don't eagerly allocate worklist segments
> >
> > Bug: chromium:1056170
> > Change-Id: I75a6b5f52bfe8dd71abc086e5d1e060759ad7fc0
> > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2391254
> > Commit-Queue: Omer Katz <omerkatz@chromium.org>
> > Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
> > Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
> > Cr-Commit-Position: refs/heads/master@{#69778}
> 
> Bug: chromium:1056170
> Change-Id: I4633da065976a6b2710d2f23b946fd2af0e65c83
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2401425
> Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
> Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
> Commit-Queue: Omer Katz <omerkatz@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#69806}

TBR=ulan@chromium.org,mlippautz@chromium.org,omerkatz@chromium.org

Change-Id: I004173e2a82518a88e68eae3a6f7e96656c0ad7e
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: chromium:1056170
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2403249Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#69809}

This is a reland of c99147c6

Original change's description:
> cppgc, heap: Don't eagerly allocate worklist segments
>
> Bug: chromium:1056170
> Change-Id: I75a6b5f52bfe8dd71abc086e5d1e060759ad7fc0
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2391254
> Commit-Queue: Omer Katz <omerkatz@chromium.org>
> Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
> Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#69778}

Bug: chromium:1056170
Change-Id: I4633da065976a6b2710d2f23b946fd2af0e65c83
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2401425Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
Commit-Queue: Omer Katz <omerkatz@chromium.org>
Cr-Commit-Position: refs/heads/master@{#69806}

Bug: chromium:1056170
Change-Id: Ibf561b663c74f9448139fd99945e5f4aea26419b
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2390776
Commit-Queue: Omer Katz <omerkatz@chromium.org>
Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
Cr-Commit-Position: refs/heads/master@{#69774}