123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211 |
- // -*- 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>
- #ifndef TCMALLOC_CENTRAL_FREELIST_H_
- #define TCMALLOC_CENTRAL_FREELIST_H_
- #include "config.h"
- #include <stddef.h> // for size_t
- #ifdef HAVE_STDINT_H
- #include <stdint.h> // for int32_t
- #endif
- #include "base/spinlock.h"
- #include "base/thread_annotations.h"
- #include "common.h"
- #include "span.h"
- namespace tcmalloc {
- // Data kept per size-class in central cache.
- class CentralFreeList {
- public:
- // A CentralFreeList may be used before its constructor runs.
- // So we prevent lock_'s constructor from doing anything to the
- // lock_ state.
- CentralFreeList() : lock_(base::LINKER_INITIALIZED) { }
- void Init(size_t cl);
- // These methods all do internal locking.
- // Insert the specified range into the central freelist. N is the number of
- // elements in the range. RemoveRange() is the opposite operation.
- void InsertRange(void *start, void *end, int N);
- // Returns the actual number of fetched elements and sets *start and *end.
- int RemoveRange(void **start, void **end, int N);
- // Returns the number of free objects in cache.
- int length() {
- SpinLockHolder h(&lock_);
- return counter_;
- }
- // Returns the number of free objects in the transfer cache.
- int tc_length();
- // Returns the memory overhead (internal fragmentation) attributable
- // to the freelist. This is memory lost when the size of elements
- // in a freelist doesn't exactly divide the page-size (an 8192-byte
- // page full of 5-byte objects would have 2 bytes memory overhead).
- size_t OverheadBytes();
- // Lock/Unlock the internal SpinLock. Used on the pthread_atfork call
- // to set the lock in a consistent state before the fork.
- void Lock() {
- lock_.Lock();
- }
- void Unlock() {
- lock_.Unlock();
- }
- private:
- // TransferCache is used to cache transfers of
- // sizemap.num_objects_to_move(size_class) back and forth between
- // thread caches and the central cache for a given size class.
- struct TCEntry {
- void *head; // Head of chain of objects.
- void *tail; // Tail of chain of objects.
- };
- // A central cache freelist can have anywhere from 0 to kMaxNumTransferEntries
- // slots to put link list chains into.
- #ifdef TCMALLOC_SMALL_BUT_SLOW
- // For the small memory model, the transfer cache is not used.
- static const int kMaxNumTransferEntries = 0;
- #else
- // Starting point for the the maximum number of entries in the transfer cache.
- // This actual maximum for a given size class may be lower than this
- // maximum value.
- static const int kMaxNumTransferEntries = 64;
- #endif
- // REQUIRES: lock_ is held
- // Remove object from cache and return.
- // Return NULL if no free entries in cache.
- int FetchFromOneSpans(int N, void **start, void **end) EXCLUSIVE_LOCKS_REQUIRED(lock_);
- // REQUIRES: lock_ is held
- // Remove object from cache and return. Fetches
- // from pageheap if cache is empty. Only returns
- // NULL on allocation failure.
- int FetchFromOneSpansSafe(int N, void **start, void **end) EXCLUSIVE_LOCKS_REQUIRED(lock_);
- // REQUIRES: lock_ is held
- // Release a linked list of objects to spans.
- // May temporarily release lock_.
- void ReleaseListToSpans(void *start) EXCLUSIVE_LOCKS_REQUIRED(lock_);
- // REQUIRES: lock_ is held
- // Release an object to spans.
- // May temporarily release lock_.
- void ReleaseToSpans(void* object) EXCLUSIVE_LOCKS_REQUIRED(lock_);
- // REQUIRES: lock_ is held
- // Populate cache by fetching from the page heap.
- // May temporarily release lock_.
- void Populate() EXCLUSIVE_LOCKS_REQUIRED(lock_);
- // REQUIRES: lock is held.
- // Tries to make room for a TCEntry. If the cache is full it will try to
- // expand it at the cost of some other cache size. Return false if there is
- // no space.
- bool MakeCacheSpace() EXCLUSIVE_LOCKS_REQUIRED(lock_);
- // REQUIRES: lock_ for locked_size_class is held.
- // Picks a "random" size class to steal TCEntry slot from. In reality it
- // just iterates over the sizeclasses but does so without taking a lock.
- // Returns true on success.
- // May temporarily lock a "random" size class.
- static bool EvictRandomSizeClass(int locked_size_class, bool force);
- // REQUIRES: lock_ is *not* held.
- // Tries to shrink the Cache. If force is true it will relase objects to
- // spans if it allows it to shrink the cache. Return false if it failed to
- // shrink the cache. Decrements cache_size_ on succeess.
- // May temporarily take lock_. If it takes lock_, the locked_size_class
- // lock is released to keep the thread from holding two size class locks
- // concurrently which could lead to a deadlock.
- bool ShrinkCache(int locked_size_class, bool force) LOCKS_EXCLUDED(lock_);
- // This lock protects all the data members. cached_entries and cache_size_
- // may be looked at without holding the lock.
- SpinLock lock_;
- // We keep linked lists of empty and non-empty spans.
- size_t size_class_; // My size class
- Span empty_; // Dummy header for list of empty spans
- Span nonempty_; // Dummy header for list of non-empty spans
- size_t num_spans_; // Number of spans in empty_ plus nonempty_
- size_t counter_; // Number of free objects in cache entry
- // Here we reserve space for TCEntry cache slots. Space is preallocated
- // for the largest possible number of entries than any one size class may
- // accumulate. Not all size classes are allowed to accumulate
- // kMaxNumTransferEntries, so there is some wasted space for those size
- // classes.
- TCEntry tc_slots_[kMaxNumTransferEntries];
- // Number of currently used cached entries in tc_slots_. This variable is
- // updated under a lock but can be read without one.
- int32_t used_slots_;
- // The current number of slots for this size class. This is an
- // adaptive value that is increased if there is lots of traffic
- // on a given size class.
- int32_t cache_size_;
- // Maximum size of the cache for a given size class.
- int32_t max_cache_size_;
- };
- // Pads each CentralCache object to multiple of 64 bytes. Since some
- // compilers (such as MSVC) don't like it when the padding is 0, I use
- // template specialization to remove the padding entirely when
- // sizeof(CentralFreeList) is a multiple of 64.
- template<int kFreeListSizeMod64>
- class CentralFreeListPaddedTo : public CentralFreeList {
- private:
- char pad_[64 - kFreeListSizeMod64];
- };
- template<>
- class CentralFreeListPaddedTo<0> : public CentralFreeList {
- };
- class CentralFreeListPadded : public CentralFreeListPaddedTo<
- sizeof(CentralFreeList) % 64> {
- };
- } // namespace tcmalloc
- #endif // TCMALLOC_CENTRAL_FREELIST_H_
|