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..ee9ca549db253b1d631974ec6f919c2a4742321c 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,8 +92,9 @@ 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;

[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++;
     }
@@ -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);
   }
 }
 
@@ -239,13 +238,12 @@ int CentralFreeList::RemoveRange(void **start, void **end, int N) {
   // 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++;
     }
   }
@@ -271,8 +269,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);
@@ -310,20 +307,19 @@ void CentralFreeList::Populate() {
 
   // 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();