123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387 |
- // -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
- // Copyright (c) 2008, Google 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:
- //
- // * Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimer.
- // * 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.
- // * Neither the name of Google Inc. nor the names of its
- // contributors may be used to endorse or promote products derived from
- // this software without specific prior written permission.
- //
- // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- // "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 THE COPYRIGHT
- // OWNER 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.
- // ---
- // Author: Sanjay Ghemawat <opensource@google.com>
- #include "config.h"
- #include <algorithm>
- #include "central_freelist.h"
- #include "internal_logging.h" // for ASSERT, MESSAGE
- #include "linked_list.h" // for SLL_Next, SLL_Push, etc
- #include "page_heap.h" // for PageHeap
- #include "static_vars.h" // for Static
- using std::min;
- using std::max;
- namespace tcmalloc {
- void CentralFreeList::Init(size_t cl) {
- size_class_ = cl;
- tcmalloc::DLL_Init(&empty_);
- tcmalloc::DLL_Init(&nonempty_);
- num_spans_ = 0;
- counter_ = 0;
- max_cache_size_ = kMaxNumTransferEntries;
- #ifdef TCMALLOC_SMALL_BUT_SLOW
- // Disable the transfer cache for the small footprint case.
- cache_size_ = 0;
- #else
- cache_size_ = 16;
- #endif
- if (cl > 0) {
- // Limit the maximum size of the cache based on the size class. If this
- // is not done, large size class objects will consume a lot of memory if
- // they just sit in the transfer cache.
- int32_t bytes = Static::sizemap()->ByteSizeForClass(cl);
- int32_t objs_to_move = Static::sizemap()->num_objects_to_move(cl);
- ASSERT(objs_to_move > 0 && bytes > 0);
- // Limit each size class cache to at most 1MB of objects or one entry,
- // whichever is greater. Total transfer cache memory used across all
- // size classes then can't be greater than approximately
- // 1MB * kMaxNumTransferEntries.
- // min and max are in parens to avoid macro-expansion on windows.
- max_cache_size_ = (min)(max_cache_size_,
- (max)(1, (1024 * 1024) / (bytes * objs_to_move)));
- cache_size_ = (min)(cache_size_, max_cache_size_);
- }
- used_slots_ = 0;
- ASSERT(cache_size_ <= max_cache_size_);
- }
- void CentralFreeList::ReleaseListToSpans(void* start) {
- while (start) {
- void *next = SLL_Next(start);
- ReleaseToSpans(start);
- start = next;
- }
- }
- // MapObjectToSpan should logically be part of ReleaseToSpans. But
- // this triggers an optimization bug in gcc 4.5.0. Moving to a
- // separate function, and making sure that function isn't inlined,
- // seems to fix the problem. It also should be fixed for gcc 4.5.1.
- static
- #if __GNUC__ == 4 && __GNUC_MINOR__ == 5 && __GNUC_PATCHLEVEL__ == 0
- __attribute__ ((noinline))
- #endif
- Span* MapObjectToSpan(void* object) {
- const PageID p = reinterpret_cast<uintptr_t>(object) >> kPageShift;
- Span* span = Static::pageheap()->GetDescriptor(p);
- return span;
- }
- void CentralFreeList::ReleaseToSpans(void* object) {
- Span* span = MapObjectToSpan(object);
- ASSERT(span != NULL);
- ASSERT(span->refcount > 0);
- // If span is empty, move it to non-empty list
- if (span->objects == NULL) {
- tcmalloc::DLL_Remove(span);
- tcmalloc::DLL_Prepend(&nonempty_, span);
- Event(span, 'N', 0);
- }
- // The following check is expensive, so it is disabled by default
- if (false) {
- // Check that object does not occur in list
- int got = 0;
- for (void* p = span->objects; p != NULL; p = *((void**) p)) {
- ASSERT(p != object);
- got++;
- }
- ASSERT(got + span->refcount ==
- (span->length<<kPageShift) /
- Static::sizemap()->ByteSizeForClass(span->sizeclass));
- }
- counter_++;
- span->refcount--;
- if (span->refcount == 0) {
- Event(span, '#', 0);
- counter_ -= ((span->length<<kPageShift) /
- Static::sizemap()->ByteSizeForClass(span->sizeclass));
- tcmalloc::DLL_Remove(span);
- --num_spans_;
- // Release central list lock while operating on pageheap
- lock_.Unlock();
- {
- SpinLockHolder h(Static::pageheap_lock());
- Static::pageheap()->Delete(span);
- }
- lock_.Lock();
- } else {
- *(reinterpret_cast<void**>(object)) = span->objects;
- span->objects = object;
- }
- }
- bool CentralFreeList::EvictRandomSizeClass(
- int locked_size_class, bool force) {
- static int race_counter = 0;
- int t = race_counter++; // Updated without a lock, but who cares.
- if (t >= kNumClasses) {
- while (t >= kNumClasses) {
- t -= kNumClasses;
- }
- race_counter = t;
- }
- ASSERT(t >= 0);
- ASSERT(t < kNumClasses);
- if (t == locked_size_class) return false;
- return Static::central_cache()[t].ShrinkCache(locked_size_class, force);
- }
- bool CentralFreeList::MakeCacheSpace() {
- // Is there room in the cache?
- if (used_slots_ < cache_size_) return true;
- // Check if we can expand this cache?
- if (cache_size_ == max_cache_size_) return false;
- // Ok, we'll try to grab an entry from some other size class.
- if (EvictRandomSizeClass(size_class_, false) ||
- EvictRandomSizeClass(size_class_, true)) {
- // Succeeded in evicting, we're going to make our cache larger.
- // However, we may have dropped and re-acquired the lock in
- // EvictRandomSizeClass (via ShrinkCache and the LockInverter), so the
- // cache_size may have changed. Therefore, check and verify that it is
- // still OK to increase the cache_size.
- if (cache_size_ < max_cache_size_) {
- cache_size_++;
- return true;
- }
- }
- return false;
- }
- namespace {
- class LockInverter {
- private:
- SpinLock *held_, *temp_;
- public:
- inline explicit LockInverter(SpinLock* held, SpinLock *temp)
- : held_(held), temp_(temp) { held_->Unlock(); temp_->Lock(); }
- inline ~LockInverter() { temp_->Unlock(); held_->Lock(); }
- };
- }
- // This function is marked as NO_THREAD_SAFETY_ANALYSIS because it uses
- // LockInverter to release one lock and acquire another in scoped-lock
- // style, which our current annotation/analysis does not support.
- bool CentralFreeList::ShrinkCache(int locked_size_class, bool force)
- NO_THREAD_SAFETY_ANALYSIS {
- // Start with a quick check without taking a lock.
- if (cache_size_ == 0) return false;
- // We don't evict from a full cache unless we are 'forcing'.
- if (force == false && used_slots_ == cache_size_) return false;
- // Grab lock, but first release the other lock held by this thread. We use
- // the lock inverter to ensure that we never hold two size class locks
- // concurrently. That can create a deadlock because there is no well
- // defined nesting order.
- LockInverter li(&Static::central_cache()[locked_size_class].lock_, &lock_);
- ASSERT(used_slots_ <= cache_size_);
- ASSERT(0 <= cache_size_);
- if (cache_size_ == 0) return false;
- if (used_slots_ == cache_size_) {
- if (force == false) return false;
- // ReleaseListToSpans releases the lock, so we have to make all the
- // updates to the central list before calling it.
- cache_size_--;
- used_slots_--;
- ReleaseListToSpans(tc_slots_[used_slots_].head);
- return true;
- }
- cache_size_--;
- return true;
- }
- void CentralFreeList::InsertRange(void *start, void *end, int N) {
- SpinLockHolder h(&lock_);
- if (N == Static::sizemap()->num_objects_to_move(size_class_) &&
- MakeCacheSpace()) {
- int slot = used_slots_++;
- ASSERT(slot >=0);
- ASSERT(slot < max_cache_size_);
- TCEntry *entry = &tc_slots_[slot];
- entry->head = start;
- entry->tail = end;
- return;
- }
- ReleaseListToSpans(start);
- }
- int CentralFreeList::RemoveRange(void **start, void **end, int N) {
- ASSERT(N > 0);
- lock_.Lock();
- if (N == Static::sizemap()->num_objects_to_move(size_class_) &&
- used_slots_ > 0) {
- int slot = --used_slots_;
- ASSERT(slot >= 0);
- TCEntry *entry = &tc_slots_[slot];
- *start = entry->head;
- *end = entry->tail;
- lock_.Unlock();
- return N;
- }
- int result = 0;
- *start = NULL;
- *end = NULL;
- // TODO: Prefetch multiple TCEntries?
- result = FetchFromOneSpansSafe(N, start, end);
- if (result != 0) {
- while (result < N) {
- int n;
- void* head = NULL;
- void* tail = NULL;
- n = FetchFromOneSpans(N - result, &head, &tail);
- if (!n) break;
- result += n;
- SLL_PushRange(start, head, tail);
- }
- }
- lock_.Unlock();
- return result;
- }
- int CentralFreeList::FetchFromOneSpansSafe(int N, void **start, void **end) {
- int result = FetchFromOneSpans(N, start, end);
- if (!result) {
- Populate();
- result = FetchFromOneSpans(N, start, end);
- }
- return result;
- }
- int CentralFreeList::FetchFromOneSpans(int N, void **start, void **end) {
- if (tcmalloc::DLL_IsEmpty(&nonempty_)) return 0;
- Span* span = nonempty_.next;
- ASSERT(span->objects != NULL);
- int result = 0;
- void *prev, *curr;
- curr = span->objects;
- do {
- prev = curr;
- curr = *(reinterpret_cast<void**>(curr));
- } while (++result < N && curr != NULL);
- if (curr == NULL) {
- // Move to empty list
- tcmalloc::DLL_Remove(span);
- tcmalloc::DLL_Prepend(&empty_, span);
- Event(span, 'E', 0);
- }
- *start = span->objects;
- *end = prev;
- span->objects = curr;
- SLL_SetNext(*end, NULL);
- span->refcount += result;
- counter_ -= result;
- return result;
- }
- // Fetch memory from the system and add to the central cache freelist.
- void CentralFreeList::Populate() {
- // Release central list lock while operating on pageheap
- lock_.Unlock();
- const size_t npages = Static::sizemap()->class_to_pages(size_class_);
- Span* span;
- {
- SpinLockHolder h(Static::pageheap_lock());
- span = Static::pageheap()->New(npages);
- if (span) Static::pageheap()->RegisterSizeClass(span, size_class_);
- }
- if (span == NULL) {
- Log(kLog, __FILE__, __LINE__,
- "tcmalloc: allocation failed", npages << kPageShift);
- lock_.Lock();
- return;
- }
- ASSERT(span->length == npages);
- // Cache sizeclass info eagerly. Locking is not necessary.
- // (Instead of being eager, we could just replace any stale info
- // about this span, but that seems to be no better in practice.)
- for (int i = 0; i < npages; i++) {
- Static::pageheap()->CacheSizeClass(span->start + i, size_class_);
- }
- // Split the block into pieces and add to the free-list
- // TODO: coloring of objects to avoid cache conflicts?
- void** tail = &span->objects;
- char* ptr = reinterpret_cast<char*>(span->start << kPageShift);
- char* limit = ptr + (npages << kPageShift);
- const size_t size = Static::sizemap()->ByteSizeForClass(size_class_);
- int num = 0;
- while (ptr + size <= limit) {
- *tail = ptr;
- tail = reinterpret_cast<void**>(ptr);
- ptr += size;
- num++;
- }
- ASSERT(ptr <= limit);
- *tail = NULL;
- span->refcount = 0; // No sub-object in use yet
- // Add span to list of non-empty spans
- lock_.Lock();
- tcmalloc::DLL_Prepend(&nonempty_, span);
- ++num_spans_;
- counter_ += num;
- }
- int CentralFreeList::tc_length() {
- SpinLockHolder h(&lock_);
- return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_);
- }
- size_t CentralFreeList::OverheadBytes() {
- SpinLockHolder h(&lock_);
- if (size_class_ == 0) { // 0 holds the 0-sized allocations
- return 0;
- }
- const size_t pages_per_span = Static::sizemap()->class_to_pages(size_class_);
- const size_t object_size = Static::sizemap()->class_to_size(size_class_);
- ASSERT(object_size > 0);
- const size_t overhead_per_span = (pages_per_span * kPageSize) % object_size;
- return num_spans_ * overhead_per_span;
- }
- } // namespace tcmalloc
|