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

third_party/tcmalloc/chromium/src/free_list.h

+// 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
+// definitions of functions that implement doubly linked lists and
+// functions that implement singly linked lists.  The basic singly
+// linked list functions use void * as storage.  The original author
+// of that code is Sanjay Ghemawat <opensource@google.com> The basic
+// doubly linked list functions store pointers to other nodes as void
+// * pointers directly inline.  A node of this list needs to be big
+// enough to hold 2 void * pointers, this generally means that each
+// node needs at least 16 byes (on a 64 bit machine). The next pointer
+// is written into the first 8 bytes of the node and the previous
+// pointer is writtend into the second 8 bytes.  All pointers point to
+// the first byte of the next/previous node.  The meaning of
+// "previous" and "next" is fairly arbitrary, but consistent.  It
+// turns out that when the head is popped, the new head becomes
+// whatever is pointed to by the previous head's next pointer. The
+// head's previous pointer points to NULL, the node at the end of the
+// list has a next pointer that also poitns to NULL.
+#ifndef TCMALLOC_FREE_LIST_H_
+#define TCMALLOC_FREE_LIST_H_
+
+#include <stddef.h>
+
+namespace tcmalloc {
+
+#ifdef TCMALLOC_USE_DOUBLYLINKED_FREELIST
+static const int kPointerSize = sizeof(void *);
+
+// size class information for common.h/common.cc.
+#if defined _LP64

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

For windows I'm pretty sure you'll need something like this:
#if defined(_LP64) || defined(_WIN64)

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

Done. As a general question: if the binaries we compile for 64bit windows are
actually 32 bit applications, are the void * pointers 8 bytes?

+// 8 byte pointers require that min class size holds at least 16 bytes.
+#define AVOID_8_BYTE_CLASSES 1

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

I really dislike this macro name. Maybe something like IS_64_BIT_POINTERS. Or,
is this macro just redundant with the class size macro?

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

Done.

+#define FIRST_USABLE_SIZE_CLASS 2

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

I don't like this one either. Maybe something like MINIMUM_CLASS_SIZE would be
better?

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

I need to allow for a size class for size 0 mallocs in all versions of the code,
MIMIMUM_CLASS_SIZE doesn't seem to be what we really mean.
On 2011/08/24 17:22:30, Justin Schuh wrote:

+#else
+#define AVOID_8_BYTE_CLASSES 0
+#define FIRST_USABLE_SIZE_CLASS 1
+#endif
+
+void *FL_Previous(void *t);
+void *FL_Next(void *t);
+void *FL_SetPrevious(void *t, void *n);
+void *FL_SetNext(void *t, void *n);
+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);
+
+#else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined
+
+// size class information for common.h/common.cc.
+#define AVOID_8_BYTE_CLASSES 0
+#define FIRST_USABLE_SIZE_CLASS 1
+
+inline void *FL_Next(void *t) {
+  return *(reinterpret_cast<void**>(t));
+}
+
+inline void FL_SetNext(void *t, void *n) {
+  *(reinterpret_cast<void**>(t)) = n;
+}
+
+inline void FL_Init(void *t) {
+  FL_SetNext(t, NULL);
+}
+
+inline void FL_Push(void **list, void *element) {
+  FL_SetNext(element, *list);
+  *list = element;
+}
+
+inline void *FL_Pop(void **list) {
+  void *result = *list;
+  *list = FL_Next(*list);
+  return result;
+}
+
+// Remove 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) {
+  if (N == 0) {
+    *start = NULL;
+    *end = NULL;
+    return;
+  }
+
+  *start = *head;
+  void *tmp = *head;
+  for (int i = 1; i < N; ++i) { // Find the Nth element to pop.
+    tmp = FL_Next(tmp);
+  }
+  *end = tmp;
+
+  *head = FL_Next(tmp); // Unlink range from original list.
+  FL_SetNext(tmp, NULL);
+}
+
+inline void FL_PushRange(void **head, void *start, void *end) {
+  if (!start) return;
+  FL_SetNext(end, *head);
+  *head = start;
+}
+
+#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
+
+inline size_t FL_Size(void *head) {
+  int count = 0;
+  while (head) {
+    count++;
+    head = FL_Next(head);
+  }
+  return count;
+}
+
+} // namespace tcmalloc
+
+#endif // TCMALLOC_FREE_LIST_H_