| /* |
| * Copyright (C) 2017 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #pragma once |
| |
| #include "CryptoRandom.h" |
| #include "IsoDirectory.h" |
| #include "IsoHeapImpl.h" |
| #include "IsoPage.h" |
| #include "StdLibExtras.h" |
| #include "VMAllocate.h" |
| |
| namespace bmalloc { |
| |
| template<typename Config> |
| IsoPage<Config>* IsoPage<Config>::tryCreate(IsoDirectoryBase<Config>& directory, unsigned index) |
| { |
| void* memory = allocatePageMemory(); |
| if (!memory) |
| return nullptr; |
| |
| return new (memory) IsoPage(directory, index); |
| } |
| |
| template<typename Config> |
| IsoPage<Config>::IsoPage(IsoDirectoryBase<Config>& directory, unsigned index) |
| : IsoPageBase(false) |
| , m_directory(directory) |
| , m_index(index) |
| { |
| memset(m_allocBits, 0, sizeof(m_allocBits)); |
| } |
| |
| inline IsoPageBase* IsoPageBase::pageFor(void* ptr) |
| { |
| return reinterpret_cast<IsoPageBase*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1)); |
| } |
| |
| template<typename Config> |
| IsoPage<Config>* IsoPage<Config>::pageFor(void* ptr) |
| { |
| return reinterpret_cast<IsoPage<Config>*>(IsoPageBase::pageFor(ptr)); |
| } |
| |
| template<typename Config> |
| void IsoPage<Config>::free(void* passedPtr) |
| { |
| BASSERT(!m_isShared); |
| unsigned offset = static_cast<char*>(passedPtr) - reinterpret_cast<char*>(this); |
| unsigned index = offset / Config::objectSize; |
| |
| if (!m_eligibilityHasBeenNoted) { |
| m_eligibilityTrigger.didBecome(*this); |
| m_eligibilityHasBeenNoted = true; |
| } |
| |
| unsigned wordIndex = index / 32; |
| unsigned bitIndex = index % 32; |
| |
| unsigned newWord = m_allocBits[wordIndex] &= ~(1 << bitIndex); |
| if (!newWord) { |
| if (!--m_numNonEmptyWords) |
| m_emptyTrigger.didBecome(*this); |
| } |
| } |
| |
| template<typename Config> |
| FreeList IsoPage<Config>::startAllocating() |
| { |
| static constexpr bool verbose = false; |
| |
| if (verbose) |
| fprintf(stderr, "%p: starting allocation.\n", this); |
| |
| RELEASE_BASSERT(!m_isInUseForAllocation); |
| m_isInUseForAllocation = true; |
| m_eligibilityHasBeenNoted = false; |
| |
| FreeList result; |
| if (!m_numNonEmptyWords) { |
| if (verbose) |
| fprintf(stderr, "%p: preparing to bump.\n", this); |
| |
| char* payloadEnd = reinterpret_cast<char*>(this) + numObjects * Config::objectSize; |
| result.initializeBump(payloadEnd, (numObjects - indexOfFirstObject()) * Config::objectSize); |
| |
| unsigned begin = indexOfFirstObject(); |
| unsigned end = numObjects; |
| |
| unsigned beginWord = begin >> 5; |
| unsigned endWord = end >> 5; |
| |
| if (verbose) { |
| fprintf(stderr, "begin = %u\n", begin); |
| fprintf(stderr, "end = %u\n", end); |
| fprintf(stderr, "beginWord = %u\n", beginWord); |
| fprintf(stderr, "endWord = %u\n", endWord); |
| } |
| |
| auto setSpan = [&] (unsigned word, unsigned begin, unsigned end) -> unsigned { |
| for (unsigned i = begin; i < end; ++i) |
| word |= (1 << (i & 31)); |
| return word; |
| }; |
| |
| if (beginWord == endWord) { |
| m_allocBits[beginWord] = setSpan(m_allocBits[beginWord], begin, end); |
| m_numNonEmptyWords = 1; |
| } else { |
| unsigned endBeginSlop = (begin + 31) & ~31; |
| unsigned beginEndSlop = end & ~31; |
| |
| if (verbose) { |
| fprintf(stderr, "endBeginSlop = %u\n", endBeginSlop); |
| fprintf(stderr, "beginEndSlop = %u\n", beginEndSlop); |
| } |
| |
| m_allocBits[beginWord] = setSpan(m_allocBits[beginWord], begin, endBeginSlop); |
| if (verbose) |
| fprintf(stderr, "m_allocBits[beginWord] = %u\n", m_allocBits[beginWord]); |
| if (end > beginEndSlop) { |
| m_allocBits[endWord] = setSpan(m_allocBits[endWord], beginEndSlop, end); |
| if (verbose) |
| fprintf(stderr, "m_allocBits[endWord] = %u\n", m_allocBits[endWord]); |
| } |
| |
| unsigned beginWordContiguous = endBeginSlop / 32; |
| unsigned endWordContiguous = beginEndSlop / 32; |
| if (verbose) { |
| fprintf(stderr, "beginWordContiguous = %u\n", beginWordContiguous); |
| fprintf(stderr, "endWordContiguous = %u\n", endWordContiguous); |
| } |
| |
| for (size_t i = beginWordContiguous; i < endWordContiguous; ++i) |
| m_allocBits[i] = UINT_MAX; |
| m_numNonEmptyWords = endWordContiguous - beginWordContiguous + |
| (endBeginSlop > begin) + (end > beginEndSlop); |
| } |
| |
| static constexpr bool verify = false; |
| if (verify) { |
| for (unsigned index = 0; index < indexOfFirstObject(); ++index) { |
| if (!(m_allocBits[index >> 5] & (1 << (index & 31)))) |
| continue; |
| fprintf(stderr, "Bit is set even though it should not be: %u\n", index); |
| BCRASH(); |
| } |
| for (unsigned index = indexOfFirstObject(); index < numObjects; ++index) { |
| if (m_allocBits[index >> 5] & (1 << (index & 31))) |
| continue; |
| fprintf(stderr, "Bit is not set even though it should be: %u\n", index); |
| fprintf(stderr, "Word contents: %u\n", m_allocBits[index >> 5]); |
| fprintf(stderr, "Mask: %u\n", 1 << (index & 31)); |
| BCRASH(); |
| } |
| } |
| |
| return result; |
| } |
| |
| uintptr_t secret; |
| cryptoRandom(&secret, sizeof(secret)); |
| FreeCell* head = nullptr; |
| unsigned bytes = 0; |
| |
| for (unsigned index = indexOfFirstObject(); index < numObjects; ++index) { |
| unsigned wordIndex = index >> 5; |
| unsigned word = m_allocBits[wordIndex]; |
| unsigned bitMask = 1 << (index & 31); |
| if (word & bitMask) |
| continue; |
| if (!word) |
| m_numNonEmptyWords++; |
| m_allocBits[wordIndex] = word | bitMask; |
| char* cellByte = reinterpret_cast<char*>(this) + index * Config::objectSize; |
| if (verbose) |
| fprintf(stderr, "%p: putting %p on free list.\n", this, cellByte); |
| FreeCell* cell = bitwise_cast<FreeCell*>(cellByte); |
| cell->setNext(head, secret); |
| head = cell; |
| bytes += Config::objectSize; |
| } |
| |
| result.initializeList(head, secret, bytes); |
| return result; |
| } |
| |
| template<typename Config> |
| void IsoPage<Config>::stopAllocating(FreeList freeList) |
| { |
| static constexpr bool verbose = false; |
| |
| if (verbose) |
| fprintf(stderr, "%p: stopping allocation.\n", this); |
| |
| freeList.forEach<Config>( |
| [&] (void* ptr) { |
| free(ptr); |
| }); |
| |
| RELEASE_BASSERT(m_isInUseForAllocation); |
| m_isInUseForAllocation = false; |
| |
| m_eligibilityTrigger.handleDeferral(*this); |
| m_emptyTrigger.handleDeferral(*this); |
| } |
| |
| template<typename Config> |
| template<typename Func> |
| void IsoPage<Config>::forEachLiveObject(const Func& func) |
| { |
| for (unsigned wordIndex = 0; wordIndex < bitsArrayLength(numObjects); ++wordIndex) { |
| unsigned word = m_allocBits[wordIndex]; |
| if (!word) |
| continue; |
| unsigned firstBitIndex = wordIndex * 32; |
| char* cellByte = reinterpret_cast<char*>(this) + firstBitIndex * Config::objectSize; |
| for (unsigned bitIndex = 0; bitIndex < 32; ++bitIndex) { |
| if (word & 1) |
| func(static_cast<void*>(cellByte)); |
| word >>= 1; |
| cellByte += Config::objectSize; |
| } |
| } |
| } |
| |
| template<typename Config> |
| IsoHeapImpl<Config>& IsoPage<Config>::heap() |
| { |
| return m_directory.heap(); |
| } |
| |
| } // namespace bmalloc |
| |