Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       3             :  * This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       5             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #include "ds/LifoAlloc.h"
       8             : 
       9             : #include "mozilla/MathAlgorithms.h"
      10             : 
      11             : using namespace js;
      12             : 
      13             : using mozilla::RoundUpPow2;
      14             : using mozilla::tl::BitSize;
      15             : 
      16             : namespace js {
      17             : namespace detail {
      18             : 
      19             : BumpChunk*
      20        4042 : BumpChunk::new_(size_t chunkSize)
      21             : {
      22        4042 :     MOZ_ASSERT(RoundUpPow2(chunkSize) == chunkSize);
      23        4042 :     void* mem = js_malloc(chunkSize);
      24        4042 :     if (!mem)
      25           0 :         return nullptr;
      26        4042 :     BumpChunk* result = new (mem) BumpChunk(chunkSize - sizeof(BumpChunk));
      27             : 
      28             :     // We assume that the alignment of sAlign is less than that of
      29             :     // the underlying memory allocator -- creating a new BumpChunk should
      30             :     // always satisfy the sAlign alignment constraint.
      31        4042 :     MOZ_ASSERT(AlignPtr(result->bump) == result->bump);
      32        4042 :     return result;
      33             : }
      34             : 
      35             : void
      36        2094 : BumpChunk::delete_(BumpChunk* chunk)
      37             : {
      38             : #ifdef DEBUG
      39             :     // Part of the chunk may have been marked as poisoned/noaccess.  Undo that
      40             :     // before writing the 0xcd bytes.
      41        2094 :     size_t size = sizeof(*chunk) + chunk->bumpSpaceSize;
      42             :     MOZ_MAKE_MEM_UNDEFINED(chunk, size);
      43        2094 :     memset(chunk, 0xcd, size);
      44             : #endif
      45        2094 :     js_free(chunk);
      46        2094 : }
      47             : 
      48             : bool
      49      574238 : BumpChunk::canAlloc(size_t n)
      50             : {
      51      574238 :     char* aligned = AlignPtr(bump);
      52      574233 :     char* bumped = aligned + n;
      53      574233 :     return bumped <= limit && bumped > headerBase();
      54             : }
      55             : 
      56             : } // namespace detail
      57             : } // namespace js
      58             : 
      59             : void
      60        4109 : LifoAlloc::freeAll()
      61             : {
      62        6203 :     while (first) {
      63        2094 :         BumpChunk* victim = first;
      64        2094 :         first = first->next();
      65        2094 :         decrementCurSize(victim->computedSizeOfIncludingThis());
      66        2094 :         BumpChunk::delete_(victim);
      67             :     }
      68        2015 :     first = latest = last = nullptr;
      69             : 
      70             :     // Nb: maintaining curSize_ correctly isn't easy.  Fortunately, this is an
      71             :     // excellent sanity check.
      72        2015 :     MOZ_ASSERT(curSize_ == 0);
      73        2015 : }
      74             : 
      75             : LifoAlloc::BumpChunk*
      76        6363 : LifoAlloc::getOrCreateChunk(size_t n)
      77             : {
      78        6363 :     if (first) {
      79             :         // Look for existing, unused BumpChunks to satisfy the request.
      80        7010 :         while (latest->next()) {
      81        3377 :             latest = latest->next();
      82        3377 :             latest->resetBump();    // This was an unused BumpChunk on the chain.
      83        3377 :             if (latest->canAlloc(n))
      84        2321 :                 return latest;
      85             :         }
      86             :     }
      87             : 
      88        4042 :     size_t defaultChunkFreeSpace = defaultChunkSize_ - sizeof(BumpChunk);
      89             :     size_t chunkSize;
      90        4042 :     if (n > defaultChunkFreeSpace) {
      91           7 :         size_t allocSizeWithHeader = n + sizeof(BumpChunk);
      92             : 
      93             :         // Guard for overflow.
      94          14 :         if (allocSizeWithHeader < n ||
      95           7 :             (allocSizeWithHeader & (size_t(1) << (BitSize<size_t>::value - 1)))) {
      96           0 :             return nullptr;
      97             :         }
      98             : 
      99           7 :         chunkSize = RoundUpPow2(allocSizeWithHeader);
     100             :     } else {
     101        4035 :         chunkSize = defaultChunkSize_;
     102             :     }
     103             : 
     104             :     // If we get here, we couldn't find an existing BumpChunk to fill the request.
     105        4042 :     MOZ_ASSERT(fallibleScope_, "[OOM] Cannot allocate a new chunk in an infallible scope.");
     106        4042 :     BumpChunk* newChunk = BumpChunk::new_(chunkSize);
     107        4042 :     if (!newChunk)
     108           0 :         return nullptr;
     109        4042 :     if (!first) {
     110        1465 :         latest = first = last = newChunk;
     111             :     } else {
     112        2577 :         MOZ_ASSERT(latest && !latest->next());
     113        2577 :         latest->setNext(newChunk);
     114        2577 :         latest = last = newChunk;
     115             :     }
     116             : 
     117        4042 :     size_t computedChunkSize = newChunk->computedSizeOfIncludingThis();
     118        4042 :     MOZ_ASSERT(computedChunkSize == chunkSize);
     119        4042 :     incrementCurSize(computedChunkSize);
     120             : 
     121        4042 :     return newChunk;
     122             : }
     123             : 
     124             : void
     125         569 : LifoAlloc::transferFrom(LifoAlloc* other)
     126             : {
     127         569 :     MOZ_ASSERT(!markCount);
     128         569 :     MOZ_ASSERT(!other->markCount);
     129             : 
     130         569 :     if (!other->first)
     131           6 :         return;
     132             : 
     133         563 :     incrementCurSize(other->curSize_);
     134         563 :     if (other->isEmpty())
     135           0 :         appendUnused(other->first, other->last);
     136             :     else
     137         563 :         appendUsed(other->first, other->latest, other->last);
     138         563 :     other->first = other->last = other->latest = nullptr;
     139         563 :     other->curSize_ = 0;
     140             : }
     141             : 
     142             : void
     143           2 : LifoAlloc::transferUnusedFrom(LifoAlloc* other)
     144             : {
     145           2 :     MOZ_ASSERT(!markCount);
     146           2 :     MOZ_ASSERT(latest == first);
     147             : 
     148           2 :     if (other->markCount || !other->first)
     149           0 :         return;
     150             : 
     151             :     // Transfer all chunks *after* |latest|.
     152             : 
     153           2 :     if (other->latest->next()) {
     154           2 :         if (other->latest == other->first) {
     155             :             // We're transferring everything except the first chunk.
     156           2 :             size_t delta = other->curSize_ - other->first->computedSizeOfIncludingThis();
     157           2 :             other->decrementCurSize(delta);
     158           2 :             incrementCurSize(delta);
     159             :         } else {
     160           0 :             for (BumpChunk* chunk = other->latest->next(); chunk; chunk = chunk->next()) {
     161           0 :                 size_t size = chunk->computedSizeOfIncludingThis();
     162           0 :                 incrementCurSize(size);
     163           0 :                 other->decrementCurSize(size);
     164             :             }
     165             :         }
     166             : 
     167           2 :         appendUnused(other->latest->next(), other->last);
     168           2 :         other->latest->setNext(nullptr);
     169           2 :         other->last = other->latest;
     170             :     }
     171             : }