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

third_party/tcmalloc/chromium/src/tcmalloc.cc

-// Copyright (c) 2005, 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 69 matching lines @@
 // TODO: implement mallinfo/mallopt
 // TODO: Better testing
 //
 // 9/28/2003 (new page-level allocator replaces ptmalloc2):
 // * malloc/free of small objects goes from ~300 ns to ~50 ns.
 // * allocation of a reasonably complicated struct
 //   goes from about 1100 ns to about 300 ns.
 
 #include "config.h"
 #include <google/tcmalloc.h>
 

[jar (doing other things), 2011/08/20 02:40:30]

nit: don't add extra line.

[bxx, 2011/08/24 00:19:24]

Done.

+
 #include <errno.h>                      // for ENOMEM, EINVAL, errno
 #ifdef HAVE_SYS_CDEFS_H
 #include <sys/cdefs.h>                  // for __THROW
 #endif
 #ifdef HAVE_FEATURES_H
 #include <features.h>                   // for __GLIBC__
 #endif
 #if defined HAVE_STDINT_H
 #include <stdint.h>
 #elif defined HAVE_INTTYPES_H
@@ skipping 13 matching lines @@
 #include <vector>                       // for vector
 
 #include <google/malloc_extension.h>
 #include <google/malloc_hook.h>         // for MallocHook
 #include "base/basictypes.h"            // for int64
 #include "base/commandlineflags.h"      // for RegisterFlagValidator, etc
 #include "base/dynamic_annotations.h"   // for RunningOnValgrind
 #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
 #include "span.h"              // for Span, DLL_Prepend, etc
 #include "stack_trace_table.h"  // for StackTraceTable
 #include "static_vars.h"       // for Static
 #include "system-alloc.h"      // for DumpSystemAllocatorStats, etc
 #include "tcmalloc_guard.h"    // for TCMallocGuard
 #include "thread_cache.h"      // for ThreadCache
 
@@ skipping 1083 matching lines @@
 
   ValidateAllocatedRegion(ptr, cl);
 
   if (cl != 0) {
     ASSERT(!Static::pageheap()->GetDescriptor(p)->sample);
     ThreadCache* heap = GetCacheIfPresent();
     if (heap != NULL) {
       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 {
     SpinLockHolder h(Static::pageheap_lock());
     ASSERT(reinterpret_cast<uintptr_t>(ptr) % kPageSize == 0);
     ASSERT(span != NULL && span->start == p);
     if (span->sample) {
       StackTrace* st = reinterpret_cast<StackTrace*>(span->objects);
       tcmalloc::DLL_Remove(span);
       Static::stacktrace_allocator()->Delete(st);
@@ skipping 685 matching lines @@
   *mark = ~allocated_mark;  //  Distinctively not allocated.
 }
 
 static void MarkAllocatedRegion(void* ptr) {
   if (ptr == NULL) return;
   MarkType* mark = GetMarkLocation(ptr);
   *mark = GetMarkValue(ptr, mark);
 }
 
 #endif  // TCMALLOC_VALIDATION