DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Header

Mercurial (777e60ca8853)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * 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
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "ds/LifoAlloc.h"

#include "mozilla/MathAlgorithms.h"

using namespace js;

using mozilla::RoundUpPow2;
using mozilla::tl::BitSize;

namespace js {
namespace detail {

BumpChunk*
BumpChunk::new_(size_t chunkSize)
{
    JS_ASSERT(RoundUpPow2(chunkSize) == chunkSize);
    void* mem = js_malloc(chunkSize);
    if (!mem)
        return nullptr;
    BumpChunk* result = new (mem) BumpChunk(chunkSize - sizeof(BumpChunk));

    // We assume that the alignment of sAlign is less than that of
    // the underlying memory allocator -- creating a new BumpChunk should
    // always satisfy the sAlign alignment constraint.
    JS_ASSERT(AlignPtr(result->bump) == result->bump);
    return result;
}

void
BumpChunk::delete_(BumpChunk* chunk)
{
#ifdef DEBUG
    // Part of the chunk may have been marked as poisoned/noaccess.  Undo that
    // before writing the 0xcd bytes.
    size_t size = sizeof(*chunk) + chunk->bumpSpaceSize;
    MOZ_MAKE_MEM_UNDEFINED(chunk, size);
    memset(chunk, 0xcd, size);
#endif
    js_free(chunk);
}

bool
BumpChunk::canAlloc(size_t n)
{
    char* aligned = AlignPtr(bump);
    char* bumped = aligned + n;
    return bumped <= limit && bumped > headerBase();
}

} // namespace detail
} // namespace js

void
LifoAlloc::freeAll()
{
    while (first) {
        BumpChunk* victim = first;
        first = first->next();
        decrementCurSize(victim->computedSizeOfIncludingThis());
        BumpChunk::delete_(victim);
    }
    first = latest = last = nullptr;

    // Nb: maintaining curSize_ correctly isn't easy.  Fortunately, this is an
    // excellent sanity check.
    JS_ASSERT(curSize_ == 0);
}

LifoAlloc::BumpChunk*
LifoAlloc::getOrCreateChunk(size_t n)
{
    if (first) {
        // Look for existing, unused BumpChunks to satisfy the request.
        while (latest->next()) {
            latest = latest->next();
            latest->resetBump();    // This was an unused BumpChunk on the chain.
            if (latest->canAlloc(n))
                return latest;
        }
    }

    size_t defaultChunkFreeSpace = defaultChunkSize_ - sizeof(BumpChunk);
    size_t chunkSize;
    if (n > defaultChunkFreeSpace) {
        size_t allocSizeWithHeader = n + sizeof(BumpChunk);

        // Guard for overflow.
        if (allocSizeWithHeader < n ||
            (allocSizeWithHeader & (size_t(1) << (BitSize<size_t>::value - 1)))) {
            return nullptr;
        }

        chunkSize = RoundUpPow2(allocSizeWithHeader);
    } else {
        chunkSize = defaultChunkSize_;
    }

    // If we get here, we couldn't find an existing BumpChunk to fill the request.
    BumpChunk* newChunk = BumpChunk::new_(chunkSize);
    if (!newChunk)
        return nullptr;
    if (!first) {
        latest = first = last = newChunk;
    } else {
        JS_ASSERT(latest && !latest->next());
        latest->setNext(newChunk);
        latest = last = newChunk;
    }

    size_t computedChunkSize = newChunk->computedSizeOfIncludingThis();
    JS_ASSERT(computedChunkSize == chunkSize);
    incrementCurSize(computedChunkSize);

    return newChunk;
}

void
LifoAlloc::transferFrom(LifoAlloc* other)
{
    JS_ASSERT(!markCount);
    JS_ASSERT(!other->markCount);

    if (!other->first)
        return;

    incrementCurSize(other->curSize_);
    if (other->isEmpty())
        appendUnused(other->first, other->last);
    else
        appendUsed(other->first, other->latest, other->last);
    other->first = other->last = other->latest = nullptr;
    other->curSize_ = 0;
}

void
LifoAlloc::transferUnusedFrom(LifoAlloc* other)
{
    JS_ASSERT(!markCount);
    JS_ASSERT(latest == first);

    if (other->markCount || !other->first)
        return;

    // Transfer all chunks *after* |latest|.

    if (other->latest->next()) {
        if (other->latest == other->first) {
            // We're transferring everything except the first chunk.
            size_t delta = other->curSize_ - other->first->computedSizeOfIncludingThis();
            other->decrementCurSize(delta);
            incrementCurSize(delta);
        } else {
            for (BumpChunk* chunk = other->latest->next(); chunk; chunk = chunk->next()) {
                size_t size = chunk->computedSizeOfIncludingThis();
                incrementCurSize(size);
                other->decrementCurSize(size);
            }
        }

        appendUnused(other->latest->next(), other->last);
        other->latest->setNext(nullptr);
        other->last = other->latest;
    }
}