Revert 100074 - 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.

BUG=None
TEST=None

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

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

TBR=bxx@chromium.org
Review URL: http://codereview.chromium.org/7845012

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

9 files changed, 39 insertions, 359 deletions

diff --git a/third_party/tcmalloc/chromium/src/central_freelist.cc b/third_party/tcmalloc/chromium/src/central_freelist.cc
index fff1260..6b3be06 100644
--- a/third_party/tcmalloc/chromium/src/central_freelist.cc
+++ b/third_party/tcmalloc/chromium/src/central_freelist.cc
@@ -32,8 +32,9 @@
 
 #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
 
@@ -57,7 +58,7 @@ void CentralFreeList::Init(size_t cl) {
 
 void CentralFreeList::ReleaseListToSpans(void* start) {
   while (start) {
-    void *next = FL_Next(start);
+    void *next = SLL_Next(start);
     ReleaseToSpans(start);
     start = next;
   }
@@ -93,7 +94,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 = FL_Next(p)){
+    for (void* p = span->objects; p != NULL; p = *((void**) p)) {
       ASSERT(p != object);
       got++;
     }
@@ -118,7 +119,8 @@ void CentralFreeList::ReleaseToSpans(void* object) {
     }
     lock_.Lock();
   } else {
-    FL_Push(&(span->objects), object);
+    *(reinterpret_cast<void**>(object)) = span->objects;
+    span->objects = object;
   }
 }
 
@@ -237,12 +239,13 @@ int CentralFreeList::RemoveRange(void **start, void **end, int N) {
   // TODO: Prefetch multiple TCEntries?
   tail = FetchFromSpansSafe();
   if (tail != NULL) {
-    FL_Push(&head, tail);
+    SLL_SetNext(tail, NULL);
+    head = tail;
     result = 1;
     while (result < N) {
       void *t = FetchFromSpans();
       if (!t) break;
-      FL_Push(&head, t);
+      SLL_Push(&head, t);
       result++;
     }
   }
@@ -268,7 +271,8 @@ void* CentralFreeList::FetchFromSpans() {
 
   ASSERT(span->objects != NULL);
   span->refcount++;
-  void *result = FL_Pop(&(span->objects));
+  void* result = span->objects;
+  span->objects = *(reinterpret_cast<void**>(result));
   if (span->objects == NULL) {
     // Move to empty list
     tcmalloc::DLL_Remove(span);
@@ -306,18 +310,19 @@ void CentralFreeList::Populate() {
 
   // Split the block into pieces and add to the free-list
   // TODO: coloring of objects to avoid cache conflicts?
-  void* list = NULL;
+  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;
   while (ptr + size <= limit) {
-    FL_Push(&list, ptr);
+    *tail = ptr;
+    tail = reinterpret_cast<void**>(ptr);
     ptr += size;
     num++;
   }
   ASSERT(ptr <= limit);
-  span->objects = list;
+  *tail = NULL;
   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 7460010..b92e988 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 = kMinClassSize; size <= kMaxSize; size += alignment) {
+  for (size_t size = kAlignment; 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 78cdc03..a3df8de 100644
--- a/third_party/tcmalloc/chromium/src/common.h
+++ b/third_party/tcmalloc/chromium/src/common.h
@@ -31,6 +31,7 @@
 // Author: Sanjay Ghemawat <opensource@google.com>
 //
 // Common definitions for tcmalloc code.
+
 #ifndef TCMALLOC_COMMON_H_
 #define TCMALLOC_COMMON_H_
 
@@ -39,7 +40,6 @@
 #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,30 +61,19 @@ 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 - kSkippedClasses;
+static const size_t kNumClasses = 95;
 static const size_t kMaxThreadCacheSize = 4 << 20;
 #else
 static const size_t kPageShift  = 12;
-static const size_t kNumClasses = 61 - kSkippedClasses;
+static const size_t kNumClasses = 61;
 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
deleted file mode 100644
index 26243c6..0000000
--- a/third_party/tcmalloc/chromium/src/free_list.cc
+++ /dev/null
@@ -1,219 +0,0 @@
-// 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
deleted file mode 100644
index e5b9bfd..0000000
--- a/third_party/tcmalloc/chromium/src/free_list.h
+++ /dev/null
@@ -1,99 +0,0 @@
-// 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 e27ea04..bcff8b3 100644
--- a/third_party/tcmalloc/chromium/src/page_heap_allocator.h
+++ b/third_party/tcmalloc/chromium/src/page_heap_allocator.h
@@ -36,7 +36,6 @@
 #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 {
@@ -63,7 +62,8 @@ class PageHeapAllocator {
     // Consult free list
     void* result;
     if (free_list_ != NULL) {
-      result = FL_Pop(&free_list_);
+      result = free_list_;
+      free_list_ = *(reinterpret_cast<void**>(result));
     } else {
       if (free_avail_ < sizeof(T)) {
         // Need more room. We assume that MetaDataAlloc returns
@@ -85,7 +85,8 @@ class PageHeapAllocator {
   }
 
   void Delete(T* p) {
-    FL_Push(&free_list_, p);
+    *(reinterpret_cast<void**>(p)) = free_list_;
+    free_list_ = p;
     inuse_--;
   }
 
diff --git a/third_party/tcmalloc/chromium/src/tcmalloc.cc b/third_party/tcmalloc/chromium/src/tcmalloc.cc
index 4afe5e7..e88f983 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::FL_Init(ptr);
+      tcmalloc::SLL_SetNext(ptr, NULL);
       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 a951f77..b00e3b4 100644
--- a/third_party/tcmalloc/chromium/src/thread_cache.cc
+++ b/third_party/tcmalloc/chromium/src/thread_cache.cc
@@ -153,10 +153,7 @@ 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;
-    // 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);
+    list->PushRange(fetch_count, SLL_Next(start), 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 9220aab..1742d5b 100644
--- a/third_party/tcmalloc/chromium/src/thread_cache.h
+++ b/third_party/tcmalloc/chromium/src/thread_cache.h
@@ -42,10 +42,16 @@
 #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 "maybe_threads.h"
+#include "linked_list.h"       // for SLL_Pop, SLL_PopRange, etc
 #include "page_heap_allocator.h"  // for PageHeapAllocator
 #include "sampler.h"           // for Sampler
 #include "static_vars.h"       // for Static
@@ -192,7 +198,7 @@ class ThreadCache {
     void clear_lowwatermark() { lowater_ = length_; }
 
     void Push(void* ptr) {
-      FL_Push(&list_, ptr);
+      SLL_Push(&list_, ptr);
       length_++;
     }
 
@@ -200,16 +206,16 @@ class ThreadCache {
       ASSERT(list_ != NULL);
       length_--;
       if (length_ < lowater_) lowater_ = length_;
-      return FL_Pop(&list_);
+      return SLL_Pop(&list_);
     }
 
     void PushRange(int N, void *start, void *end) {
-      FL_PushRange(&list_, start, end);
+      SLL_PushRange(&list_, start, end);
       length_ += N;
     }
 
     void PopRange(int N, void **start, void **end) {
-      FL_PopRange(&list_, N, start, end);
+      SLL_PopRange(&list_, N, start, end);
       ASSERT(length_ >= N);
       length_ -= N;
       if (length_ < lowater_) lowater_ = length_;