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

[jar (doing other things), 2011/08/25 02:07:50]

wording nit: I think you meant to say "declarations" of doubly linked list
functions, and "definitions" of singly linked list functionality.

[bxx, 2011/08/25 20:23:18]

Done.

+// linked list functions use void * as storage.  The original author

[jar (doing other things), 2011/08/25 02:07:50]

wording nit: "The basic singly linked list functions use void * as storage."  

The phrase "as storage" doesn't seem meaningful, and there is no mention that
these lists are null terminated.

better might be something like:

"The singly linked lists are null terminated, and use raw to pointers to link to
successive elements, and the pointers are held at the start of each element,
independent of the element's size."

[bxx, 2011/08/25 20:23:18]

Done.

+// of that code is Sanjay Ghemawat <opensource@google.com> The basic

[jar (doing other things), 2011/08/25 02:07:50]

nit: Period before "The basic"

[bxx, 2011/08/25 20:23:18]

Done.

+// doubly linked list functions store pointers to other nodes as void
+// * pointers directly inline.  A node of this list needs to be big

[jar (doing other things), 2011/08/25 02:07:50]

wording nit: the phrase "directly inline" is also unclear to me.

Better might be something like:

"The doubly linked lists are null terminated at both ends, and use raw pointers
to point to adjacent elements." 

To be honest, I don't think this prose needs any mention of "void* pointers" and
should just say "pointers."  I think the mention of void* is an implementation
detail that probably will only add confusion to the prose.

[bxx, 2011/08/25 20:23:18]

Done.

+// enough to hold 2 void * pointers, this generally means that each

[jar (doing other things), 2011/08/25 02:07:50]

nit: We always put the * next to the type, with no intervening spaces.  

You also use passive voice when discussing what a "list needs."  

Suggest wording like:

"As a result, elements in doubly linked lists are required to be large enough to
hold two raw pointers if doubly linked lists are employed, and to hold one
pointer if singly linked lists are employed.  On machines with 64bit 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."

[bxx, 2011/08/25 20:23:18]

Done.

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

[jar (doing other things), 2011/08/25 02:07:50]

nit: this sentence has facts only applicable to 64 bit machines... but there is
no qualifier (i.e., next pointer is written to first 4 bytes on a 32 bit machine
discussed).

Please clean this up in some way.  You might put the doubly-linked list
description atop the section for them.  

Please try to use prose, but be terse and to the point. For instance, the
comment on line 42 about "fairly arbitrary, but consistent" doesn't seem to
carry much information.

[bxx, 2011/08/25 20:23:18]

Done.

+// 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) || defined(_WIN64)
+// 8 byte pointers require that min class size holds at least 16 bytes.
+#define IS_64_BIT_POINTERS 1
+#define FIRST_USABLE_SIZE_CLASS 2
+#else
+#define IS_64_BIT_POINTERS 0
+#define FIRST_USABLE_SIZE_CLASS 1

[jar (doing other things), 2011/08/25 02:07:50]

This name is still a bit odd, as there is a size class of 0 that is usable (or
is it??). 
Perhaps something like:
ALLOW_8_BYTE_SIZE_CLASS.
or:
ALLOW_8_BYTE_SIZE_CLASS_1

[bxx, 2011/08/25 20:23:18]

Done.

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