Merge tcmalloc r111 (perftools v. 1.8) with the chromium/ branch.

third_party/tcmalloc/chromium/src/central_freelist.h

 // 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
@@ skipping 50 matching lines @@
 
   // 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).

[jar (doing other things), 2011/07/31 08:19:39]

This commment is confusing... but perhaps you're just porting a questionable
comment?

The example makes it sound like this is fragmentation due to left over bytes
during span carving.  The description says this has to do with freelists, which
seem very orthogonal.

Is this just a comment you merged into place?

+  size_t OverheadBytes();
+
  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.
+  // 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 kNumTransferEntries = 0;
+  static const int kMaxNumTransferEntries = 0;
 #else
-  static const int kNumTransferEntries = kNumClasses;
+  // 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
@@ skipping 38 matching lines @@
   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.  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];
+  // 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_