michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "ds/LifoAlloc.h"
michael@0: 
michael@0: #include "mozilla/MathAlgorithms.h"
michael@0: 
michael@0: using namespace js;
michael@0: 
michael@0: using mozilla::RoundUpPow2;
michael@0: using mozilla::tl::BitSize;
michael@0: 
michael@0: namespace js {
michael@0: namespace detail {
michael@0: 
michael@0: BumpChunk *
michael@0: BumpChunk::new_(size_t chunkSize)
michael@0: {
michael@0:     JS_ASSERT(RoundUpPow2(chunkSize) == chunkSize);
michael@0:     void *mem = js_malloc(chunkSize);
michael@0:     if (!mem)
michael@0:         return nullptr;
michael@0:     BumpChunk *result = new (mem) BumpChunk(chunkSize - sizeof(BumpChunk));
michael@0: 
michael@0:     // We assume that the alignment of sAlign is less than that of
michael@0:     // the underlying memory allocator -- creating a new BumpChunk should
michael@0:     // always satisfy the sAlign alignment constraint.
michael@0:     JS_ASSERT(AlignPtr(result->bump) == result->bump);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: void
michael@0: BumpChunk::delete_(BumpChunk *chunk)
michael@0: {
michael@0: #ifdef DEBUG
michael@0:     // Part of the chunk may have been marked as poisoned/noaccess.  Undo that
michael@0:     // before writing the 0xcd bytes.
michael@0:     size_t size = sizeof(*chunk) + chunk->bumpSpaceSize;
michael@0:     MOZ_MAKE_MEM_UNDEFINED(chunk, size);
michael@0:     memset(chunk, 0xcd, size);
michael@0: #endif
michael@0:     js_free(chunk);
michael@0: }
michael@0: 
michael@0: bool
michael@0: BumpChunk::canAlloc(size_t n)
michael@0: {
michael@0:     char *aligned = AlignPtr(bump);
michael@0:     char *bumped = aligned + n;
michael@0:     return bumped <= limit && bumped > headerBase();
michael@0: }
michael@0: 
michael@0: } // namespace detail
michael@0: } // namespace js
michael@0: 
michael@0: void
michael@0: LifoAlloc::freeAll()
michael@0: {
michael@0:     while (first) {
michael@0:         BumpChunk *victim = first;
michael@0:         first = first->next();
michael@0:         decrementCurSize(victim->computedSizeOfIncludingThis());
michael@0:         BumpChunk::delete_(victim);
michael@0:     }
michael@0:     first = latest = last = nullptr;
michael@0: 
michael@0:     // Nb: maintaining curSize_ correctly isn't easy.  Fortunately, this is an
michael@0:     // excellent sanity check.
michael@0:     JS_ASSERT(curSize_ == 0);
michael@0: }
michael@0: 
michael@0: LifoAlloc::BumpChunk *
michael@0: LifoAlloc::getOrCreateChunk(size_t n)
michael@0: {
michael@0:     if (first) {
michael@0:         // Look for existing, unused BumpChunks to satisfy the request.
michael@0:         while (latest->next()) {
michael@0:             latest = latest->next();
michael@0:             latest->resetBump();    // This was an unused BumpChunk on the chain.
michael@0:             if (latest->canAlloc(n))
michael@0:                 return latest;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     size_t defaultChunkFreeSpace = defaultChunkSize_ - sizeof(BumpChunk);
michael@0:     size_t chunkSize;
michael@0:     if (n > defaultChunkFreeSpace) {
michael@0:         size_t allocSizeWithHeader = n + sizeof(BumpChunk);
michael@0: 
michael@0:         // Guard for overflow.
michael@0:         if (allocSizeWithHeader < n ||
michael@0:             (allocSizeWithHeader & (size_t(1) << (BitSize<size_t>::value - 1)))) {
michael@0:             return nullptr;
michael@0:         }
michael@0: 
michael@0:         chunkSize = RoundUpPow2(allocSizeWithHeader);
michael@0:     } else {
michael@0:         chunkSize = defaultChunkSize_;
michael@0:     }
michael@0: 
michael@0:     // If we get here, we couldn't find an existing BumpChunk to fill the request.
michael@0:     BumpChunk *newChunk = BumpChunk::new_(chunkSize);
michael@0:     if (!newChunk)
michael@0:         return nullptr;
michael@0:     if (!first) {
michael@0:         latest = first = last = newChunk;
michael@0:     } else {
michael@0:         JS_ASSERT(latest && !latest->next());
michael@0:         latest->setNext(newChunk);
michael@0:         latest = last = newChunk;
michael@0:     }
michael@0: 
michael@0:     size_t computedChunkSize = newChunk->computedSizeOfIncludingThis();
michael@0:     JS_ASSERT(computedChunkSize == chunkSize);
michael@0:     incrementCurSize(computedChunkSize);
michael@0: 
michael@0:     return newChunk;
michael@0: }
michael@0: 
michael@0: void
michael@0: LifoAlloc::transferFrom(LifoAlloc *other)
michael@0: {
michael@0:     JS_ASSERT(!markCount);
michael@0:     JS_ASSERT(!other->markCount);
michael@0: 
michael@0:     if (!other->first)
michael@0:         return;
michael@0: 
michael@0:     incrementCurSize(other->curSize_);
michael@0:     if (other->isEmpty())
michael@0:         appendUnused(other->first, other->last);
michael@0:     else
michael@0:         appendUsed(other->first, other->latest, other->last);
michael@0:     other->first = other->last = other->latest = nullptr;
michael@0:     other->curSize_ = 0;
michael@0: }
michael@0: 
michael@0: void
michael@0: LifoAlloc::transferUnusedFrom(LifoAlloc *other)
michael@0: {
michael@0:     JS_ASSERT(!markCount);
michael@0:     JS_ASSERT(latest == first);
michael@0: 
michael@0:     if (other->markCount || !other->first)
michael@0:         return;
michael@0: 
michael@0:     // Transfer all chunks *after* |latest|.
michael@0: 
michael@0:     if (other->latest->next()) {
michael@0:         if (other->latest == other->first) {
michael@0:             // We're transferring everything except the first chunk.
michael@0:             size_t delta = other->curSize_ - other->first->computedSizeOfIncludingThis();
michael@0:             other->decrementCurSize(delta);
michael@0:             incrementCurSize(delta);
michael@0:         } else {
michael@0:             for (BumpChunk *chunk = other->latest->next(); chunk; chunk = chunk->next()) {
michael@0:                 size_t size = chunk->computedSizeOfIncludingThis();
michael@0:                 incrementCurSize(size);
michael@0:                 other->decrementCurSize(size);
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         appendUnused(other->latest->next(), other->last);
michael@0:         other->latest->setNext(nullptr);
michael@0:         other->last = other->latest;
michael@0:     }
michael@0: }