doubly-linked free-lists for thread caches and page heaps

third_party/tcmalloc/chromium/src/common.h

-// Copyright (c) 2008, Google Inc.
+// Copyright (c) 2011, 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
@@ skipping 12 matching lines @@
 // 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>
 //
 // Common definitions for tcmalloc code.
-
+ 

[jar (doing other things), 2011/08/20 02:40:30]

nit: remove trailing whitespace.

[bxx, 2011/08/24 00:19:24]

Done.

 #ifndef TCMALLOC_COMMON_H_
 #define TCMALLOC_COMMON_H_
 
 #include "config.h"
+

[jar (doing other things), 2011/08/20 02:40:30]

nit: remove extra newline.

[bxx, 2011/08/24 00:19:24]

Done.

 #include <stddef.h>                     // for size_t
 #ifdef HAVE_STDINT_H
 #include <stdint.h>                     // for uintptr_t, uint64_t
 #endif
+
+#include "free_list.h"  // for SIZE_CLASS macros
 #include "internal_logging.h"  // for ASSERT, etc
 
 // Type that can hold a page number
 typedef uintptr_t PageID;
 
 // Type that can hold the length of a run of pages
 typedef uintptr_t Length;
 
 //-------------------------------------------------------------------
 // Configuration
@@ skipping 97 matching lines @@
   // So for these larger sizes we have an array indexed by ceil(size/128).
   //
   // We flatten both logical arrays into one physical array and use
   // arithmetic to compute an appropriate index.  The constants used by
   // ClassIndex() were selected to make the flattening work.
   //
   // Examples:
   //   Size       Expression                      Index
   //   -------------------------------------------------------
   //   0          (0 + 7) / 8                     0
   //   1          (1 + 7) / 8                     1

[jar (doing other things), 2011/08/20 02:40:30]

Note that they were distinguishing a class 0 for 0 length allocations, vs a
class 1 for 8 byte allocations.  There are some subtlies in malloc about whether
we return a null pointer for a requested zero length allocation, vs a unique
pointer.  I *think* tcmalloc goes with the standard of a unique pointer... so
I'm not sure why they distinguish this way... but you should be careful to watch
for checking where they might have optionally tried to support the other (NULL
return) standard, and can't (with the changes you made here).

[bxx, 2011/08/24 00:19:24]

My edit to ClassIndex() in common.h should address this.  I also had to change
how class_to_size_ is initialized to prevent an 8 byte class size from being
chosen later on.
On 2011/08/20 02:40:30, jar wrote:

   //   ...
   //   1024       (1024 + 7) / 8                  128
   //   1025       (1025 + 127 + (120<<7)) / 128   129
   //   ...
   //   32768      (32768 + 127 + (120<<7)) / 128  376
   static const int kMaxSmallSize = 1024;
   static const size_t kClassArraySize =
       (((1 << kPageShift) * 8u + 127 + (120 << 7)) >> 7) + 1;
   unsigned char class_array_[kClassArraySize];
 
   // Compute index of the class_array[] entry for a given size
   static inline int ClassIndex(int s) {
     ASSERT(0 <= s);
     ASSERT(s <= kMaxSize);
     const bool big = (s > kMaxSmallSize);
     const int add_amount = big ? (127 + (120<<7)) : 7;
     const int shift_amount = big ? 7 : 3;
-    return (s + add_amount) >> shift_amount;
+    const int size_class = (s + add_amount) >> shift_amount;
+    return  (size_class < MIN_SIZE_CLASS) ? MIN_SIZE_CLASS : size_class;

[jar (doing other things), 2011/08/20 02:40:30]

I assume this was added to preclude 8 byte allocations on a 64bit architecture. 


As written, it adds a perf(?) hit near what looks to be highly optimized code. 
My guess is that this was written expecting (hoping) to be inlined and they
wanted to stay really short and sweet.

I like that you avoided broader changes (minimalist!), but perhaps it could be
written so that an optimizer could remove it when not active.  Note that s and
the return value are both signed ints, so it is (I think) hard to tell when the
compiler needn't bother.  

Suggest you change line 182 to something like:
if (!AVOID_8_BYTE_CLASSES || size > 8)
  return size_class;
return 2;  // The smallest class that needs more than 8 bytes.

That would allow the compiler to discard the comparison unless the macro was
set, and would have the fast-path(?) for the common case of returning size class
directly.

I don't really know if this is perf critical... but it sure (to me) looks a bit
hand-tuned... and it is nice to have zero impact (guaranteed) when we are not
doing this twiddling.  We know we have some perf impact when we are active (more
broadly)... and we can tune that case better if need be in the future.

[bxx, 2011/08/24 00:19:24]

Done.

   }
 
   int NumMoveSize(size_t size);
 
   // Mapping from size class to max size storable in that class
   size_t class_to_size_[kNumClasses];
 
   // Mapping from size class to number of pages to allocate at a time
   size_t class_to_pages_[kNumClasses];
 
@@ skipping 55 matching lines @@
 static const int kMaxStackDepth = 31;
 struct StackTrace {
   uintptr_t size;          // Size of object
   uintptr_t depth;         // Number of PC values stored in array below
   void*     stack[kMaxStackDepth];
 };
 
 }  // namespace tcmalloc
 
 #endif  // TCMALLOC_COMMON_H_