Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
#ifndef gc_ArenaList_inl_h
#define gc_ArenaList_inl_h
#include "gc/ArenaList.h"
#include "gc/Heap.h"
#include "gc/Zone.h"
bool js::gc::ArenaList::hasNonFullArenas() const {
// Non-full arenas are kept at the start so we can check the first one.
return !isEmpty() && !first()->isFull();
}
js::gc::Arena* js::gc::ArenaList::takeInitialNonFullArena() {
Arena* arena = first();
if (!arena || arena->isFull()) {
return nullptr;
}
moveFrontToBack();
return arena;
}
js::gc::SortedArenaList::SortedArenaList(js::gc::AllocKind allocKind)
: thingsPerArena_(Arena::thingsPerArena(allocKind)) {
#ifdef DEBUG
MOZ_ASSERT(thingsPerArena_ <= MaxThingsPerArena);
MOZ_ASSERT(emptyIndex() < BucketCount);
allocKind_ = allocKind;
#endif
}
size_t js::gc::SortedArenaList::index(size_t nfree, bool* frontOut) const {
// Get the bucket index to use for arenas with |nfree| free things and set
// |frontOut| to indicate whether to prepend or append to the bucket.
MOZ_ASSERT(nfree <= thingsPerArena_);
// Full arenas go in the first bucket on their own.
if (nfree == 0) {
*frontOut = false;
return 0;
}
// Empty arenas go in the last bucket on their own.
if (nfree == thingsPerArena_) {
*frontOut = false;
return emptyIndex();
}
// All other arenas are alternately added to the front and back of successive
// buckets as |nfree| increases.
*frontOut = (nfree % 2) != 0;
size_t index = (nfree + 1) / 2;
MOZ_ASSERT(index != 0);
MOZ_ASSERT(index != emptyIndex());
return index;
}
size_t js::gc::SortedArenaList::emptyIndex() const {
// Get the bucket index to use for empty arenas. This must have its own
// bucket so they can be removed with extractEmptyTo.
return bucketsUsed() - 1;
}
size_t js::gc::SortedArenaList::bucketsUsed() const {
// Get the total number of buckets used for the current alloc kind.
return HowMany(thingsPerArena_ - 1, 2) + 2;
}
void js::gc::SortedArenaList::insertAt(Arena* arena, size_t nfree) {
MOZ_ASSERT(!isConvertedToArenaList);
MOZ_ASSERT(nfree <= thingsPerArena_);
bool front;
size_t i = index(nfree, &front);
MOZ_ASSERT(i < BucketCount);
if (front) {
buckets[i].pushFront(arena);
} else {
buckets[i].pushBack(arena);
}
}
void js::gc::SortedArenaList::extractEmptyTo(Arena** destListHeadPtr) {
MOZ_ASSERT(!isConvertedToArenaList);
MOZ_ASSERT(destListHeadPtr);
check();
Bucket& bucket = buckets[emptyIndex()];
if (!bucket.isEmpty()) {
Arena* tail = *destListHeadPtr;
Arena* bucketLast = bucket.last();
*destListHeadPtr = bucket.release();
bucketLast->next = tail;
}
MOZ_ASSERT(bucket.isEmpty());
}
js::gc::ArenaList js::gc::SortedArenaList::convertToArenaList(
Arena* maybeBucketLastOut[BucketCount]) {
#ifdef DEBUG
MOZ_ASSERT(!isConvertedToArenaList);
isConvertedToArenaList = true;
check();
#endif
if (maybeBucketLastOut) {
for (size_t i = 0; i < BucketCount; i++) {
maybeBucketLastOut[i] = buckets[i].last();
}
}
// The returned ArenaList needs to contain all non-full arenas in order
// of increasing free space, followed by all full arenas.
ArenaList result;
size_t used = bucketsUsed();
for (size_t i = 1; i <= used; ++i) {
size_t bucket = i % used; // [1, used) then 0.
result.append(std::move(buckets[bucket]));
}
return result;
}
void js::gc::SortedArenaList::restoreFromArenaList(
ArenaList& list, Arena* bucketLast[BucketCount]) {
#ifdef DEBUG
MOZ_ASSERT(isConvertedToArenaList);
isConvertedToArenaList = false;
#endif
// Group the ArenaList elements into SinglyLinkedList buckets, where the
// boundaries between buckets are retrieved from |bucketLast|.
Arena* remaining = list.release();
size_t used = bucketsUsed();
for (size_t i = 1; i <= used; ++i) {
size_t bucket = i % used; // [1, used) then 0.
MOZ_ASSERT(buckets[bucket].isEmpty());
if (bucketLast[bucket]) {
MOZ_ASSERT(remaining);
Arena* first = remaining;
Arena* last = bucketLast[bucket];
remaining = last->next;
last->next = nullptr;
new (&buckets[bucket]) Bucket(first, last);
}
}
MOZ_ASSERT(!remaining);
check();
}
void js::gc::SortedArenaList::check() const {
#ifdef DEBUG
const auto& fullBucket = buckets[0];
for (auto arena = fullBucket.iter(); !arena.done(); arena.next()) {
MOZ_ASSERT(arena->getAllocKind() == allocKind());
MOZ_ASSERT(!arena->hasFreeThings());
}
for (size_t i = 1; i < emptyIndex(); i++) {
const auto& bucket = buckets[i];
size_t lastFree = 0;
for (auto arena = bucket.iter(); !arena.done(); arena.next()) {
MOZ_ASSERT(arena->getAllocKind() == allocKind());
size_t nfree = arena->countFreeCells();
MOZ_ASSERT(nfree == i * 2 - 1 || nfree == i * 2);
MOZ_ASSERT(nfree >= lastFree);
lastFree = nfree;
}
}
const auto& emptyBucket = buckets[emptyIndex()];
for (auto arena = emptyBucket.iter(); !arena.done(); arena.next()) {
MOZ_ASSERT(arena->getAllocKind() == allocKind());
MOZ_ASSERT(arena->isEmpty());
}
for (size_t i = emptyIndex() + 1; i < BucketCount; i++) {
MOZ_ASSERT(buckets[i].isEmpty());
}
#endif
}
#ifdef DEBUG
bool js::gc::FreeLists::allEmpty() const {
for (auto i : AllAllocKinds()) {
if (!isEmpty(i)) {
return false;
}
}
return true;
}
bool js::gc::FreeLists::isEmpty(AllocKind kind) const {
return freeLists_[kind]->isEmpty();
}
#endif
void js::gc::FreeLists::clear() {
for (auto i : AllAllocKinds()) {
#ifdef DEBUG
auto old = freeLists_[i];
if (!old->isEmpty()) {
old->getArena()->checkNoMarkedFreeCells();
}
#endif
freeLists_[i] = &emptySentinel;
}
}
js::gc::TenuredCell* js::gc::FreeLists::allocate(AllocKind kind) {
return freeLists_[kind]->allocate(Arena::thingSize(kind));
}
void js::gc::FreeLists::unmarkPreMarkedFreeCells(AllocKind kind) {
FreeSpan* freeSpan = freeLists_[kind];
if (!freeSpan->isEmpty()) {
freeSpan->getArena()->unmarkPreMarkedFreeCells();
}
}
JSRuntime* js::gc::ArenaLists::runtime() {
return zone_->runtimeFromMainThread();
}
JSRuntime* js::gc::ArenaLists::runtimeFromAnyThread() {
return zone_->runtimeFromAnyThread();
}
js::gc::Arena* js::gc::ArenaLists::getFirstArena(AllocKind thingKind) const {
return arenaList(thingKind).first();
}
js::gc::Arena* js::gc::ArenaLists::getFirstCollectingArena(
AllocKind thingKind) const {
return collectingArenaList(thingKind).first();
}
bool js::gc::ArenaLists::arenaListsAreEmpty() const {
for (auto i : AllAllocKinds()) {
/*
* The arena cannot be empty if the background finalization is not yet
* done.
*/
if (concurrentUse(i) == ConcurrentUse::BackgroundFinalize) {
return false;
}
if (!arenaList(i).isEmpty()) {
return false;
}
}
return true;
}
bool js::gc::ArenaLists::doneBackgroundFinalize(AllocKind kind) const {
return concurrentUse(kind) != ConcurrentUse::BackgroundFinalize;
}
bool js::gc::ArenaLists::needBackgroundFinalizeWait(AllocKind kind) const {
return concurrentUse(kind) == ConcurrentUse::BackgroundFinalize;
}
void js::gc::ArenaLists::clearFreeLists() { freeLists().clear(); }
MOZ_ALWAYS_INLINE js::gc::TenuredCell* js::gc::ArenaLists::allocateFromFreeList(
AllocKind thingKind) {
return freeLists().allocate(thingKind);
}
void js::gc::ArenaLists::unmarkPreMarkedFreeCells() {
for (auto i : AllAllocKinds()) {
freeLists().unmarkPreMarkedFreeCells(i);
}
}
void js::gc::ArenaLists::checkEmptyFreeLists() {
MOZ_ASSERT(freeLists().allEmpty());
}
void js::gc::ArenaLists::checkEmptyArenaLists() {
#ifdef DEBUG
for (auto i : AllAllocKinds()) {
checkEmptyArenaList(i);
}
#endif
}
#endif // gc_ArenaList_inl_h