1 files changed, 175 insertions, 0 deletions
diff --git a/trunk/src/central_freelist.h b/trunk/src/central_freelist.h
new file mode 100644
index 0000000..2e6a31b
--- /dev/null
+++ b/trunk/src/central_freelist.h
@@ -0,0 +1,175 @@
+// 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 "base/thread_annotations.h"
+#include "base/spinlock.h"
+#include "common.h"
+#include "span.h"
+
+namespace tcmalloc {
+
+// Data kept per size-class in central cache.
+class CentralFreeList {
+ public:
+  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();
+
+ 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 kNumTransferEntries
+  // slots to put link list chains into.  To keep memory usage bounded the total
+  // number of TCEntries across size classes is fixed.  Currently each size
+  // class is initially given one TCEntry which also means that the maximum any
+  // one class can have is kNumClasses.
+  static const int kNumTransferEntries = kNumClasses;
+
+  // 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   counter_;        // Number of free objects in cache entry
+
+  // Here we reserve space for TCEntry cache slots.  Since one size class can
+  // end up getting all the TCEntries quota in the system we just preallocate
+  // sufficient number of entries here.
+  TCEntry tc_slots_[kNumTransferEntries];
+
+  // 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_;
+};
+
+// 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_