tcmalloc doubly-linked free-lists for thread caches

Added the ability for free lists to be built out of doubly-linked lists in tcalloc. TCMALLOC_USE_DOUBLYLINKED_FREELIST flag must be set in order for doubly-linked lists to be used. By default flag is only set in Debug builds.

BUG=None
TEST=None

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=99515

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=100074

Review URL: http://codereview.chromium.org/7671034

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@100525 0039d316-1c4b-4281-b951-d872f2087c98

9 files changed, 359 insertions, 39 deletions

diff --git a/third_party/tcmalloc/chromium/src/central_freelist.cc b/third_party/tcmalloc/chromium/src/central_freelist.cc
index 6b3be06..fff1260 100644
--- a/third_party/tcmalloc/chromium/src/central_freelist.cc
+++ b/third_party/tcmalloc/chromium/src/central_freelist.cc
@@ -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;
   }
@@ -94,7 +93,7 @@ void CentralFreeList::ReleaseToSpans(void* object) {
   if (false) {
     // Check that object does not occur in list
     int got = 0;
-    for (void* p = span->objects; p != NULL; p = *((void**) p)) {
+    for (void* p = span->objects; p != NULL; p = FL_Next(p)){
       ASSERT(p != object);
       got++;
     }
@@ -119,8 +118,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 +237,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 +268,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,19 +306,18 @@ 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, ptr);
     ptr += size;
     num++;
   }
   ASSERT(ptr <= limit);
-  *tail = NULL;
+  span->objects = list;
   span->refcount = 0; // No sub-object in use yet
 
   // Add span to list of non-empty spans
diff --git a/third_party/tcmalloc/chromium/src/common.cc b/third_party/tcmalloc/chromium/src/common.cc
index b92e988..7460010 100644
--- a/third_party/tcmalloc/chromium/src/common.cc
+++ b/third_party/tcmalloc/chromium/src/common.cc
@@ -106,7 +106,7 @@ void SizeMap::Init() {
   int alignment = kAlignment;
   CHECK_CONDITION(kAlignment <= 16);
   int last_lg = -1;
-  for (size_t size = kAlignment; size <= kMaxSize; size += alignment) {
+  for (size_t size = kMinClassSize; size <= kMaxSize; size += alignment) {
     int lg = LgFloor(size);
     if (lg > last_lg) {
       // Increase alignment every so often to reduce number of size classes.
diff --git a/third_party/tcmalloc/chromium/src/common.h b/third_party/tcmalloc/chromium/src/common.h
index a3df8de..78cdc03 100644
--- a/third_party/tcmalloc/chromium/src/common.h
+++ b/third_party/tcmalloc/chromium/src/common.h
@@ -31,7 +31,6 @@
 // Author: Sanjay Ghemawat <opensource@google.com>
 //
 // Common definitions for tcmalloc code.
-
 #ifndef TCMALLOC_COMMON_H_
 #define TCMALLOC_COMMON_H_
 
@@ -40,6 +39,7 @@
 #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
@@ -61,19 +61,30 @@ typedef uintptr_t Length;
 // central lists.  Also, larger pages are less likely to get freed.
 // These two factors cause a bounded increase in memory use.
 
+static const size_t kAlignment  = 8;
+
+// Constants dependant on tcmalloc configuration and archetecture.
+// We need to guarantee the smallest class size is big enough to hold the
+// pointers that form the free list.
+static const size_t kNumFreeListPointers = 
+  (tcmalloc::kSupportsDoublyLinkedList ? 2 : 1);
+static const size_t kLinkSize = kNumFreeListPointers * sizeof(void *);
+static const size_t kMinClassSize = 
+  (kLinkSize > kAlignment ? kLinkSize : kAlignment);
+static const size_t kSkippedClasses = (kAlignment < kMinClassSize ? 1 : 0);
+
 #if defined(TCMALLOC_LARGE_PAGES)
 static const size_t kPageShift  = 15;
-static const size_t kNumClasses = 95;
+static const size_t kNumClasses = 95 - kSkippedClasses;
 static const size_t kMaxThreadCacheSize = 4 << 20;
 #else
 static const size_t kPageShift  = 12;
-static const size_t kNumClasses = 61;
+static const size_t kNumClasses = 61 - kSkippedClasses;
 static const size_t kMaxThreadCacheSize = 2 << 20;
 #endif
 
 static const size_t kPageSize   = 1 << kPageShift;
 static const size_t kMaxSize    = 8u * kPageSize;
-static const size_t kAlignment  = 8;
 // For all span-lengths < kMaxPages we keep an exact-size list.
 static const size_t kMaxPages = 1 << (20 - kPageShift);
 
diff --git a/third_party/tcmalloc/chromium/src/free_list.cc b/third_party/tcmalloc/chromium/src/free_list.cc
new file mode 100644
index 0000000..26243c6
--- /dev/null
+++ b/third_party/tcmalloc/chromium/src/free_list.cc
@@ -0,0 +1,219 @@
+// 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
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// 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: Rebecca Shapiro <bxx@google.com>
+//
+// This file contains functions that implement doubly linked and
+// singly linked lists.  The singly linked lists are null terminated,
+// use raw pointers to link neighboring elements, and these pointers
+// are stored at the start of each element, independently of the
+// elements's size.  Because pointers are stored within each element,
+// each element must be large enough to store two raw pointers if
+// doubly linked lists are employed, or one raw pointer if singly
+// linked lists are employed.  On machines with 64 bit pointers, this
+// means elements must be at least 16 bytes in size for doubly linked
+// list support, and 8 bytes for singly linked list support.  No
+// attempts are made to preserve the data in elements stored in the
+// list.
+//
+// Given a machine with pointers of size N (on a 64bit machine N=8, on
+// a 32bit machine, N=4), the list pointers are stored in the
+// following manner:
+// -In doubly linked lists, the |next| pointer is stored in the first N
+// bytes of the node and the |previous| pointer is writtend into the
+// second N bytes.
+// -In singly linked lists, the |next| pointer is stored in the first N
+// bytes of the node.
+//
+// For both types of lists: when a pop operation is performed on a non
+// empty list, the new list head becomes that which is pointed to by
+// the former head's |next| pointer.  If the list is doubly linked, the
+// new head |previous| pointer gets changed from pointing to the former
+// head to NULL.
+
+
+#ifdef TCMALLOC_USE_DOUBLYLINKED_FREELIST
+
+#include <stddef.h>
+#include "internal_logging.h" //for ASSERT
+
+#define MEMORY_CHECK(v1, v2) \
+  if (v1 != v2) CRASH("Memory corruption detected.\n")
+
+namespace {
+// Returns value of the |previous| pointer w/out running a sanity
+// check.
+inline void *FL_Previous_No_Check(void *t) {
+  return reinterpret_cast<void**>(t)[1];
+}
+
+// Returns value of the |next| pointer w/out running a sanity check.
+inline void *FL_Next_No_Check(void *t) {
+  return reinterpret_cast<void**>(t)[0];
+}
+
+void *FL_Previous(void *t) {
+  void *previous = FL_Previous_No_Check(t);
+  if (previous) {
+    MEMORY_CHECK(FL_Next_No_Check(previous), t);
+  }
+  return previous;
+}
+
+inline void FL_SetPrevious(void *t, void *n) {
+  reinterpret_cast<void**>(t)[1] = n;
+}
+
+inline void FL_SetNext(void *t, void *n) {
+  reinterpret_cast<void**>(t)[0] = n;
+}
+
+} // namespace
+
+namespace tcmalloc {
+
+void *FL_Next(void *t) {
+  void *next = FL_Next_No_Check(t);
+  if (next) {
+    MEMORY_CHECK(FL_Previous_No_Check(next), t);
+  }
+  return next;
+}
+
+// Makes the element at |t| a singleton doubly linked list.
+void FL_Init(void *t) {
+  FL_SetPrevious(t, NULL);
+  FL_SetNext(t, NULL);
+}
+
+// Pushes element to a linked list whose first element is at
+// |*list|. When this call returns, |list| will point to the new head
+// of the linked list.
+void FL_Push(void **list, void *element) {
+  void *old = *list;
+  if (old == NULL) { // Builds singleton list.
+    FL_Init(element);
+  } else {
+    ASSERT(FL_Previous_No_Check(old) == NULL);
+    FL_SetNext(element, old);
+    FL_SetPrevious(old, element);
+    FL_SetPrevious(element, NULL);
+  }
+  *list = element;
+}
+
+// Pops the top element off the linked list whose first element is at
+// |*list|, and updates |*list| to point to the next element in the
+// list.  Returns the address of the element that was removed from the
+// linked list.  |list| must not be NULL.
+void *FL_Pop(void **list) {
+  void *result = *list;
+  ASSERT(FL_Previous_No_Check(result) == NULL);
+  *list = FL_Next(result);
+  if (*list != NULL) {
+    FL_SetPrevious(*list, NULL);
+  }
+  return result;
+}
+
+// Remove |n| elements from linked list at whose first element is at
+// |*head|.  |head| will be modified to point to the new head.
+// |start| will point to the first node of the range, |end| will point
+// to the last node in the range. |n| must be <= FL_Size(|*head|)
+// If |n| > 0, |head| must not be NULL.
+void FL_PopRange(void **head, int n, void **start, void **end) {
+  if (n == 0) {
+    *start = NULL;
+    *end = NULL;
+    return;
+  }
+
+  *start = *head; // Remember the first node in the range.
+  void *tmp = *head;
+  for (int i = 1; i < n; ++i) { // Find end of range.
+    tmp = FL_Next(tmp);
+  }
+  *end = tmp; // |end| now set to point to last node in range.
+  *head = FL_Next(*end);
+  FL_SetNext(*end, NULL); // Unlink range from list.
+
+  if (*head ) { // Fixup popped list.
+    FL_SetPrevious(*head, NULL);
+  }
+}
+
+// Pushes the nodes in the list begginning at |start| whose last node
+// is |end| into the linked list at |*head|. |*head| is updated to
+// point be the new head of the list.  |head| must not be NULL.
+void FL_PushRange(void **head, void *start, void *end) {
+  if (!start) return;
+
+  // Sanity checking of ends of list to push is done by calling
+  // FL_Next and FL_Previous.
+  FL_Next(start);
+  FL_Previous(end);
+  ASSERT(FL_Previous_No_Check(start) == NULL);
+  ASSERT(FL_Next_No_Check(end) == NULL);
+
+  if (*head) {
+    MEMORY_CHECK(FL_Previous_No_Check(*head), NULL);
+    FL_SetNext(end, *head);
+    FL_SetPrevious(*head, end);
+  }
+  *head = start;
+}
+
+// Calculates the size of the list that begins at |head|.
+size_t FL_Size(void *head){
+  int count = 0;
+  if (head) {
+    MEMORY_CHECK(FL_Previous_No_Check(head), NULL);
+  }
+  while (head) {
+    count++;
+    head = FL_Next(head);
+  }
+  return count;
+}
+
+} // namespace tcmalloc
+
+#else
+#include "linked_list.h" // for SLL_SetNext
+
+namespace {
+
+inline void FL_SetNext(void *t, void *n) {
+  tcmalloc::SLL_SetNext(t,n);
+}
+
+}
+
+#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
diff --git a/third_party/tcmalloc/chromium/src/free_list.h b/third_party/tcmalloc/chromium/src/free_list.h
new file mode 100644
index 0000000..e5b9bfd
--- /dev/null
+++ b/third_party/tcmalloc/chromium/src/free_list.h
@@ -0,0 +1,99 @@
+// 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
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// 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: Rebecca Shapiro <bxx@google.com>
+//
+// This file contains declarations of functions that implement doubly
+// linked lists and definitions of functions that implement singly
+// linked lists.  It also contains macros to tell the SizeMap class
+// how much space a node in the freelist needs so that SizeMap can
+// create large enough size classes.
+
+#ifndef TCMALLOC_FREE_LIST_H_
+#define TCMALLOC_FREE_LIST_H_
+
+#include <stddef.h>
+#include "linked_list.h"
+
+namespace tcmalloc {
+
+#ifdef TCMALLOC_USE_DOUBLYLINKED_FREELIST
+
+// size class information for common.h.
+static const bool kSupportsDoublyLinkedList = true;
+
+void *FL_Next(void *t);
+void FL_Init(void *t);
+void FL_Push(void **list, void *element);
+void *FL_Pop(void **list);
+void FL_PopRange(void **head, int n, void **start, void **end);
+void FL_PushRange(void **head, void *start, void *end);
+size_t FL_Size(void *head);
+
+#else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined
+static const bool kSupportsDoublyLinkedList = false;
+
+inline void *FL_Next(void *t) {
+  return SLL_Next(t);
+}
+
+inline void FL_Init(void *t) {
+  SLL_SetNext(t, NULL);
+}
+
+inline void FL_Push(void **list, void *element) {
+  SLL_Push(list,element);
+}
+
+inline void *FL_Pop(void **list) {
+  return SLL_Pop(list);
+}
+
+// Removes |N| elements from a linked list to which |head| points.
+// |head| will be modified to point to the new |head|.  |start| and
+// |end| will point to the first and last nodes of the range.  Note
+// that |end| will point to NULL after this function is called.
+inline void FL_PopRange(void **head, int n, void **start, void **end) {
+  SLL_PopRange(head, n, start, end);
+}
+
+inline void FL_PushRange(void **head, void *start, void *end) {
+  SLL_PushRange(head,start,end);
+}
+
+inline size_t FL_Size(void *head) {
+  return SLL_Size(head);
+}
+
+#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
+
+} // namespace tcmalloc
+
+#endif // TCMALLOC_FREE_LIST_H_
diff --git a/third_party/tcmalloc/chromium/src/page_heap_allocator.h b/third_party/tcmalloc/chromium/src/page_heap_allocator.h
index bcff8b3..e27ea04 100644
--- a/third_party/tcmalloc/chromium/src/page_heap_allocator.h
+++ b/third_party/tcmalloc/chromium/src/page_heap_allocator.h
@@ -36,6 +36,7 @@
 #include <stddef.h>                     // for NULL, size_t
 
 #include "common.h"            // for MetaDataAlloc
+#include "free_list.h"          // for FL_Push/FL_Pop
 #include "internal_logging.h"  // for ASSERT, CRASH
 
 namespace tcmalloc {
@@ -62,8 +63,7 @@ class PageHeapAllocator {
     // Consult free list
     void* result;
     if (free_list_ != NULL) {
-      result = free_list_;
-      free_list_ = *(reinterpret_cast<void**>(result));
+      result = FL_Pop(&free_list_);
     } else {
       if (free_avail_ < sizeof(T)) {
         // Need more room. We assume that MetaDataAlloc returns
@@ -85,8 +85,7 @@ class PageHeapAllocator {
   }
 
   void Delete(T* p) {
-    *(reinterpret_cast<void**>(p)) = free_list_;
-    free_list_ = p;
+    FL_Push(&free_list_, p);
     inuse_--;
   }
 
diff --git a/third_party/tcmalloc/chromium/src/tcmalloc.cc b/third_party/tcmalloc/chromium/src/tcmalloc.cc
index e88f983..4afe5e7 100644
--- a/third_party/tcmalloc/chromium/src/tcmalloc.cc
+++ b/third_party/tcmalloc/chromium/src/tcmalloc.cc
@@ -122,8 +122,8 @@
 #include "base/spinlock.h"              // for SpinLockHolder
 #include "central_freelist.h"  // for CentralFreeListPadded
 #include "common.h"            // for StackTrace, kPageShift, etc
+#include "free_list.h"         // for FL_Init
 #include "internal_logging.h"  // for ASSERT, TCMalloc_Printer, etc
-#include "linked_list.h"       // for SLL_SetNext
 #include "malloc_hook-inl.h"       // for MallocHook::InvokeNewHook, etc
 #include "page_heap.h"         // for PageHeap, PageHeap::Stats
 #include "page_heap_allocator.h"  // for PageHeapAllocator
@@ -1227,7 +1227,7 @@ inline void do_free_with_callback(void* ptr, void (*invalid_free_fn)(void*)) {
       heap->Deallocate(ptr, cl);
     } else {
       // Delete directly into central cache
-      tcmalloc::SLL_SetNext(ptr, NULL);
+      tcmalloc::FL_Init(ptr);
       Static::central_cache()[cl].InsertRange(ptr, ptr, 1);
     }
   } else {
diff --git a/third_party/tcmalloc/chromium/src/thread_cache.cc b/third_party/tcmalloc/chromium/src/thread_cache.cc
index b00e3b4..a951f77 100644
--- a/third_party/tcmalloc/chromium/src/thread_cache.cc
+++ b/third_party/tcmalloc/chromium/src/thread_cache.cc
@@ -153,7 +153,10 @@ void* ThreadCache::FetchFromCentralCache(size_t cl, size_t byte_size) {
   ASSERT((start == NULL) == (fetch_count == 0));
   if (--fetch_count >= 0) {
     size_ += byte_size * fetch_count;
-    list->PushRange(fetch_count, SLL_Next(start), end);
+    // Pop the top of the list and add the rest to the freelist.
+    void *second = start;
+    start = FL_Pop(&second);
+    list->PushRange(fetch_count, second, end);
   }
 
   // Increase max length slowly up to batch_size.  After that,
diff --git a/third_party/tcmalloc/chromium/src/thread_cache.h b/third_party/tcmalloc/chromium/src/thread_cache.h
index 1742d5b..9220aab 100644
--- a/third_party/tcmalloc/chromium/src/thread_cache.h
+++ b/third_party/tcmalloc/chromium/src/thread_cache.h
@@ -42,16 +42,10 @@
 #include <stdint.h>                     // for uint32_t, uint64_t
 #endif
 #include <sys/types.h>                  // for ssize_t
-#include "common.h"
-#include "linked_list.h"
-#include "maybe_threads.h"
-#include "page_heap_allocator.h"
-#include "sampler.h"
-#include "static_vars.h"
-
 #include "common.h"            // for SizeMap, kMaxSize, etc
+#include "free_list.h"  // for FL_Pop, FL_PopRange, etc
 #include "internal_logging.h"  // for ASSERT, etc
-#include "linked_list.h"       // for SLL_Pop, SLL_PopRange, etc
+#include "maybe_threads.h"
 #include "page_heap_allocator.h"  // for PageHeapAllocator
 #include "sampler.h"           // for Sampler
 #include "static_vars.h"       // for Static
@@ -198,7 +192,7 @@ class ThreadCache {
     void clear_lowwatermark() { lowater_ = length_; }
 
     void Push(void* ptr) {
-      SLL_Push(&list_, ptr);
+      FL_Push(&list_, ptr);
       length_++;
     }
 
@@ -206,16 +200,16 @@ class ThreadCache {
       ASSERT(list_ != NULL);
       length_--;
       if (length_ < lowater_) lowater_ = length_;
-      return SLL_Pop(&list_);
+      return FL_Pop(&list_);
     }
 
     void PushRange(int N, void *start, void *end) {
-      SLL_PushRange(&list_, start, end);
+      FL_PushRange(&list_, start, end);
       length_ += N;
     }
 
     void PopRange(int N, void **start, void **end) {
-      SLL_PopRange(&list_, N, start, end);
+      FL_PopRange(&list_, N, start, end);
       ASSERT(length_ >= N);
       length_ -= N;
       if (length_ < lowater_) lowater_ = length_;