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. The next

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

On a 32 bit platform, you don't need anything more than 8 bytes to hold two
pointers.
On a 64 bit machine, this will require 16 bytes (as you noted).  

It would probably be nice if you used that fact to reduce the amount of change
(i.e., continued to support classes with an 8 byte size on 32 bit
architectures).

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

What would be the proper way to check the type of architecture? (#ifdef
ARCH_CPU_64_BITS ?)
On 2011/08/20 02:40:30, jar wrote:

+// 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
+
+// size class information for common.h/common.cc
+#define MIN_SIZE_CLASS 2

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

This should really depend on 64 vs 32 bit architectures.

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

Done.

+#define FIRST_SIZE_CLASS MIN_SIZE_CLASS
+
+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 MIN_SIZE_CLASS 0
+#define FIRST_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;

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

It is not a big deal... but this assignment to *end seems useless.  I only
noticed it reading the changed code.  When start is null, the end value is never
consulted (see line 124).

In addition, I *think* we never pop a range of 0 items, so this whole block may
be wasteful (and at best should be coded as the uncommon path).  It could have a
debug assertion... and I'm trying to check on use cases in chrome, but perhaps
in google3 it is used in more scenarios.

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

I included this check because I wanted to be consistent with the original code
and provide the same guarantees.  The original implementation of FL_PopRange is
in free_list.h contains this code block.
On 2011/08/20 02:40:30, jar wrote:

+    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_