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

third_party/tcmalloc/chromium/src/central_freelist.cc

Index: third_party/tcmalloc/chromium/src/central_freelist.cc
diff --git a/third_party/tcmalloc/chromium/src/central_freelist.cc b/third_party/tcmalloc/chromium/src/central_freelist.cc
index 6b3be0644090bb19034c6d99cb10d6808699e0b5..0c52d2fca3fdf037297d919505b16227ea1664a1 100644
--- a/third_party/tcmalloc/chromium/src/central_freelist.cc
+++ b/third_party/tcmalloc/chromium/src/central_freelist.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2008, Google Inc.
+// Copyright (c) 2011, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
@@ -32,9 +32,8 @@
 
 #include "config.h"
 #include "central_freelist.h"
-
+#include "free_list.h"         // for FL_Next, FL_Push, etc
 #include "internal_logging.h"  // for ASSERT, MESSAGE
-#include "linked_list.h"       // for SLL_Next, SLL_Push, etc
 #include "page_heap.h"         // for PageHeap
 #include "static_vars.h"       // for Static
 
@@ -58,7 +57,7 @@ void CentralFreeList::Init(size_t cl) {
 
 void CentralFreeList::ReleaseListToSpans(void* start) {
   while (start) {
-    void *next = SLL_Next(start);
+    void *next = FL_Next(start);
     ReleaseToSpans(start);
     start = next;
   }
@@ -93,9 +92,10 @@ void CentralFreeList::ReleaseToSpans(void* object) {
   // The following check is expensive, so it is disabled by default
   if (false) {
     // Check that object does not occur in list
+    void *next = span->objects;
     int got = 0;
-    for (void* p = span->objects; p != NULL; p = *((void**) p)) {

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

Minimalist changes are better. Merging etc. is easier. Style should comply with
surrounding code.

You could have merely written:

for (void* p = span->objects; p != NULL; p = FL_NEXT(p))) {

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

Done.

-      ASSERT(p != object);
+    while (next = FL_Next(next)) {
+      ASSERT(next != object);
       got++;
     }
     ASSERT(got + span->refcount ==
@@ -119,8 +119,7 @@ void CentralFreeList::ReleaseToSpans(void* object) {
     }
     lock_.Lock();
   } else {
-    *(reinterpret_cast<void**>(object)) = span->objects;
-    span->objects = object;
+    FL_Push(&(span->objects), object);
   }
 }
 
@@ -237,21 +236,21 @@ int CentralFreeList::RemoveRange(void **start, void **end, int N) {
   void* head = NULL;
   void* tail = NULL;
   // TODO: Prefetch multiple TCEntries?
-  tail = FetchFromSpansSafe();
+  tail = FetchFromSpansSafe();  // makes freelist and returns pointer to start

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

Minimalst: Comment here is not critical, and adds to diff.

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

Done.

   if (tail != NULL) {
-    SLL_SetNext(tail, NULL);
-    head = tail;
+    FL_Push(&head, tail);
     result = 1;
     while (result < N) {
       void *t = FetchFromSpans();
       if (!t) break;
-      SLL_Push(&head, t);
+      FL_Push(&head, t);
       result++;
     }
   }
   lock_.Unlock();
   *start = head;
   *end = tail;
+

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

nit: Remove extra line.

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

Done.

   return result;
 }
 
@@ -271,8 +270,7 @@ void* CentralFreeList::FetchFromSpans() {
 
   ASSERT(span->objects != NULL);
   span->refcount++;
-  void* result = span->objects;
-  span->objects = *(reinterpret_cast<void**>(result));
+  void *result = FL_Pop(&(span->objects));
   if (span->objects == NULL) {
     // Move to empty list
     tcmalloc::DLL_Remove(span);
@@ -315,15 +313,14 @@ void CentralFreeList::Populate() {
   char* limit = ptr + (npages << kPageShift);
   const size_t size = Static::sizemap()->ByteSizeForClass(size_class_);
   int num = 0;
+  span->objects = NULL;

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

This might be a tad more readable (and connect with the while loop action in
line 318) if it were:
*tail = NULL;

(see next comment about changing its name).

This should probably be another macro or function. Perhaps something like:
FL_InitList(tail);

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

Done.

   while (ptr + size <= limit) {
-    *tail = ptr;
-    tail = reinterpret_cast<void**>(ptr);
+    tcmalloc::FL_Push(tail, static_cast<void*>(ptr));

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

I think the change is ok, but it is good to note that you changed the semantics,
and now we create a list with the reverse order. The word "tail" is especially
deceptive.  I really think you have to change it to something like "list" to
make this readable (even if it does touch line 311.. and hurt my minimalist
mantra).

Perf is slightly degraded(?), as we touch (update) span->objects in each
iteration. This could (for example) cause a cache line conflict.  Truth is, we
just did a super-slow OS call... so perhaps it is in the noise... but you
*could* form the list with only a local pointer pointing at it, and then (in
line 325) make the only setting change to span->objects.  That might(?) be more
in line with the current code.

nit: remove "tcmalloc::"

Also, I'd rather stick with reinterpret_cast<> in all places throughout, rather
than changing to static_cast<>.  This copies the surrounding style, and prevents
the reader form thinking there is something subtle afoot.

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

I think I fixed it properly.  Just to make sure I understand the perf-related
issue: what I am reading from this is that perf-related issues may stem from the
fact that span->objects is not located on the stack and that this point we are
mostly operating on stack variables.  Is this approximately the right idea?
On 2011/08/20 02:40:30, jar wrote:

     ptr += size;
     num++;
   }
   ASSERT(ptr <= limit);
-  *tail = NULL;
-  span->refcount = 0; // No sub-object in use yet
+  span->refcount = 0;  // No sub-object in use yet

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

Minimalist: Don't correct with today's style.  Leave it as one space.

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

Done.

 
   // Add span to list of non-empty spans
   lock_.Lock();