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;

[jschuh, 2011/08/24 17:22:30]

It looks like you left some debugging code behind. Shouldn't this line be
removed, with "void* p = span->objects" in the loop initialization?

[bxx, 2011/08/24 22:02:09]

Good catch.  I don't even remember needing to debug this part.
On 2011/08/24 17:22:30, Justin Schuh wrote:

     int got = 0;
-    for (void* p = span->objects; p != NULL; p = *((void**) p)) {
+    for (void* p = next; p != NULL; p = FL_Next(p)){
       ASSERT(p != 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 98 matching lines @@
     lock_.Unlock();
     return N;
   }
 
   int result = 0;
   void* head = NULL;
   void* tail = NULL;
   // TODO: Prefetch multiple TCEntries?
   tail = FetchFromSpansSafe();
   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;
   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 17 matching lines @@
   ASSERT(span->length == npages);
   // Cache sizeclass info eagerly.  Locking is not necessary.
   // (Instead of being eager, we could just replace any stale info
   // about this span, but that seems to be no better in practice.)
   for (int i = 0; i < npages; i++) {
     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;
+  void* list = NULL;
   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;
   while (ptr + size <= limit) {
-    *tail = ptr;
-    tail = reinterpret_cast<void**>(ptr);
+    FL_Push(&list, reinterpret_cast<void*>(ptr));

[jschuh, 2011/08/24 17:22:30]

Shouldn't need the reinterpret cast here.

[bxx, 2011/08/24 22:02:09]

Done.   I assumed I needed it because ptr is of type char*.

     ptr += size;
     num++;
   }
   ASSERT(ptr <= limit);
-  *tail = NULL;
   span->refcount = 0; // No sub-object in use yet
+  span->objects = list;
 
   // 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