1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/ds/LifoAlloc.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,170 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "ds/LifoAlloc.h"
1.11 +
1.12 +#include "mozilla/MathAlgorithms.h"
1.13 +
1.14 +using namespace js;
1.15 +
1.16 +using mozilla::RoundUpPow2;
1.17 +using mozilla::tl::BitSize;
1.18 +
1.19 +namespace js {
1.20 +namespace detail {
1.21 +
1.22 +BumpChunk *
1.23 +BumpChunk::new_(size_t chunkSize)
1.24 +{
1.25 + JS_ASSERT(RoundUpPow2(chunkSize) == chunkSize);
1.26 + void *mem = js_malloc(chunkSize);
1.27 + if (!mem)
1.28 + return nullptr;
1.29 + BumpChunk *result = new (mem) BumpChunk(chunkSize - sizeof(BumpChunk));
1.30 +
1.31 + // We assume that the alignment of sAlign is less than that of
1.32 + // the underlying memory allocator -- creating a new BumpChunk should
1.33 + // always satisfy the sAlign alignment constraint.
1.34 + JS_ASSERT(AlignPtr(result->bump) == result->bump);
1.35 + return result;
1.36 +}
1.37 +
1.38 +void
1.39 +BumpChunk::delete_(BumpChunk *chunk)
1.40 +{
1.41 +#ifdef DEBUG
1.42 + // Part of the chunk may have been marked as poisoned/noaccess. Undo that
1.43 + // before writing the 0xcd bytes.
1.44 + size_t size = sizeof(*chunk) + chunk->bumpSpaceSize;
1.45 + MOZ_MAKE_MEM_UNDEFINED(chunk, size);
1.46 + memset(chunk, 0xcd, size);
1.47 +#endif
1.48 + js_free(chunk);
1.49 +}
1.50 +
1.51 +bool
1.52 +BumpChunk::canAlloc(size_t n)
1.53 +{
1.54 + char *aligned = AlignPtr(bump);
1.55 + char *bumped = aligned + n;
1.56 + return bumped <= limit && bumped > headerBase();
1.57 +}
1.58 +
1.59 +} // namespace detail
1.60 +} // namespace js
1.61 +
1.62 +void
1.63 +LifoAlloc::freeAll()
1.64 +{
1.65 + while (first) {
1.66 + BumpChunk *victim = first;
1.67 + first = first->next();
1.68 + decrementCurSize(victim->computedSizeOfIncludingThis());
1.69 + BumpChunk::delete_(victim);
1.70 + }
1.71 + first = latest = last = nullptr;
1.72 +
1.73 + // Nb: maintaining curSize_ correctly isn't easy. Fortunately, this is an
1.74 + // excellent sanity check.
1.75 + JS_ASSERT(curSize_ == 0);
1.76 +}
1.77 +
1.78 +LifoAlloc::BumpChunk *
1.79 +LifoAlloc::getOrCreateChunk(size_t n)
1.80 +{
1.81 + if (first) {
1.82 + // Look for existing, unused BumpChunks to satisfy the request.
1.83 + while (latest->next()) {
1.84 + latest = latest->next();
1.85 + latest->resetBump(); // This was an unused BumpChunk on the chain.
1.86 + if (latest->canAlloc(n))
1.87 + return latest;
1.88 + }
1.89 + }
1.90 +
1.91 + size_t defaultChunkFreeSpace = defaultChunkSize_ - sizeof(BumpChunk);
1.92 + size_t chunkSize;
1.93 + if (n > defaultChunkFreeSpace) {
1.94 + size_t allocSizeWithHeader = n + sizeof(BumpChunk);
1.95 +
1.96 + // Guard for overflow.
1.97 + if (allocSizeWithHeader < n ||
1.98 + (allocSizeWithHeader & (size_t(1) << (BitSize<size_t>::value - 1)))) {
1.99 + return nullptr;
1.100 + }
1.101 +
1.102 + chunkSize = RoundUpPow2(allocSizeWithHeader);
1.103 + } else {
1.104 + chunkSize = defaultChunkSize_;
1.105 + }
1.106 +
1.107 + // If we get here, we couldn't find an existing BumpChunk to fill the request.
1.108 + BumpChunk *newChunk = BumpChunk::new_(chunkSize);
1.109 + if (!newChunk)
1.110 + return nullptr;
1.111 + if (!first) {
1.112 + latest = first = last = newChunk;
1.113 + } else {
1.114 + JS_ASSERT(latest && !latest->next());
1.115 + latest->setNext(newChunk);
1.116 + latest = last = newChunk;
1.117 + }
1.118 +
1.119 + size_t computedChunkSize = newChunk->computedSizeOfIncludingThis();
1.120 + JS_ASSERT(computedChunkSize == chunkSize);
1.121 + incrementCurSize(computedChunkSize);
1.122 +
1.123 + return newChunk;
1.124 +}
1.125 +
1.126 +void
1.127 +LifoAlloc::transferFrom(LifoAlloc *other)
1.128 +{
1.129 + JS_ASSERT(!markCount);
1.130 + JS_ASSERT(!other->markCount);
1.131 +
1.132 + if (!other->first)
1.133 + return;
1.134 +
1.135 + incrementCurSize(other->curSize_);
1.136 + if (other->isEmpty())
1.137 + appendUnused(other->first, other->last);
1.138 + else
1.139 + appendUsed(other->first, other->latest, other->last);
1.140 + other->first = other->last = other->latest = nullptr;
1.141 + other->curSize_ = 0;
1.142 +}
1.143 +
1.144 +void
1.145 +LifoAlloc::transferUnusedFrom(LifoAlloc *other)
1.146 +{
1.147 + JS_ASSERT(!markCount);
1.148 + JS_ASSERT(latest == first);
1.149 +
1.150 + if (other->markCount || !other->first)
1.151 + return;
1.152 +
1.153 + // Transfer all chunks *after* |latest|.
1.154 +
1.155 + if (other->latest->next()) {
1.156 + if (other->latest == other->first) {
1.157 + // We're transferring everything except the first chunk.
1.158 + size_t delta = other->curSize_ - other->first->computedSizeOfIncludingThis();
1.159 + other->decrementCurSize(delta);
1.160 + incrementCurSize(delta);
1.161 + } else {
1.162 + for (BumpChunk *chunk = other->latest->next(); chunk; chunk = chunk->next()) {
1.163 + size_t size = chunk->computedSizeOfIncludingThis();
1.164 + incrementCurSize(size);
1.165 + other->decrementCurSize(size);
1.166 + }
1.167 + }
1.168 +
1.169 + appendUnused(other->latest->next(), other->last);
1.170 + other->latest->setNext(nullptr);
1.171 + other->last = other->latest;
1.172 + }
1.173 +}
