| // 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. |
| void* FetchFromSpans() 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. |
| void* FetchFromSpansSafe() 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_ |