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

third_party/tcmalloc/chromium/src/central_freelist.cc

-// 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 13 matching lines @@
 // 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>
 
 #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
 
 namespace tcmalloc {
 
 void CentralFreeList::Init(size_t cl) {
   size_class_ = cl;
   tcmalloc::DLL_Init(&empty_);
   tcmalloc::DLL_Init(&nonempty_);
   counter_ = 0;
 
 #ifdef TCMALLOC_SMALL_BUT_SLOW
   // Disable the transfer cache for the small footprint case.
   cache_size_ = 0;
 #else
   cache_size_ = 16;
 #endif
   used_slots_ = 0;
   ASSERT(cache_size_ <= kNumTransferEntries);
 }
 
 void CentralFreeList::ReleaseListToSpans(void* start) {
   while (start) {
-    void *next = SLL_Next(start);
+    void *next = FL_Next(start);
     ReleaseToSpans(start);
     start = next;
   }
 }
 
 // MapObjectToSpan should logically be part of ReleaseToSpans.  But
 // this triggers an optimization bug in gcc 4.5.0.  Moving to a
 // separate function, and making sure that function isn't inlined,
 // seems to fix the problem.  It also should be fixed for gcc 4.5.1.
 static
@@ skipping 14 matching lines @@
   // If span is empty, move it to non-empty list
   if (span->objects == NULL) {
     tcmalloc::DLL_Remove(span);
     tcmalloc::DLL_Prepend(&nonempty_, span);
     Event(span, 'N', 0);
   }
 
   // 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 ==
            (span->length<<kPageShift) /
            Static::sizemap()->ByteSizeForClass(span->sizeclass));
   }
 
   counter_++;
   span->refcount--;
   if (span->refcount == 0) {
     Event(span, '#', 0);
     counter_ -= ((span->length<<kPageShift) /
                  Static::sizemap()->ByteSizeForClass(span->sizeclass));
     tcmalloc::DLL_Remove(span);
 
     // Release central list lock while operating on pageheap
     lock_.Unlock();
     {
       SpinLockHolder h(Static::pageheap_lock());
       Static::pageheap()->Delete(span);
     }
     lock_.Lock();
   } else {
-    *(reinterpret_cast<void**>(object)) = span->objects;
-    span->objects = object;
+    FL_Push(&(span->objects), object);
   }
 }
 
 bool CentralFreeList::EvictRandomSizeClass(
     int locked_size_class, bool force) {
   static int race_counter = 0;
   int t = race_counter++;  // Updated without a lock, but who cares.
   if (t >= kNumClasses) {
     while (t >= kNumClasses) {
       t -= kNumClasses;
@@ skipping 96 matching lines @@
     *start = entry->head;
     *end = entry->tail;
     lock_.Unlock();
     return N;
   }
 
   int result = 0;
   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;
 }
 
 
 void* CentralFreeList::FetchFromSpansSafe() {
   void *t = FetchFromSpans();
   if (!t) {
     Populate();
     t = FetchFromSpans();
   }
   return t;
 }
 
 void* CentralFreeList::FetchFromSpans() {
   if (tcmalloc::DLL_IsEmpty(&nonempty_)) return NULL;
   Span* span = nonempty_.next;
 
   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);
     tcmalloc::DLL_Prepend(&empty_, span);
     Event(span, 'E', 0);
   }
   counter_--;
   return result;
 }
 
@@ skipping 22 matching lines @@
     Static::pageheap()->CacheSizeClass(span->start + i, size_class_);
   }
 
   // Split the block into pieces and add to the free-list
   // TODO: coloring of objects to avoid cache conflicts?
   void** tail = &span->objects;
   char* ptr = reinterpret_cast<char*>(span->start << kPageShift);
   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();
   tcmalloc::DLL_Prepend(&nonempty_, span);
   counter_ += num;
 }
 
 int CentralFreeList::tc_length() {
   SpinLockHolder h(&lock_);
   return used_slots_ * Static::sizemap()->num_objects_to_move(size_class_);
 }
 
 }  // namespace tcmalloc