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

third_party/tcmalloc/chromium/src/free_list.cc

+// 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
+// linked lists.
+
+#ifdef TCMALLOC_USE_DOUBLYLINKED_FREELIST
+
+#include <stddef.h>
+#include "internal_logging.h" //for ASSERT
+
+#define MEMORY_CHECK(v1, v2) if (v1 != v2) DieFromMemoryCorruption();
+namespace {
+// Intentionally cause a segmentation fault.
+inline void DieFromMemoryCorruption() {
+  char *p = NULL;
+  *p += 1; // Segfault.
+}
+
+// Returns value of the Previous pointer w/out running a sanity check.
+inline void *FL_Previous_No_Check(void *t) {
+  return *(reinterpret_cast<void**> (reinterpret_cast<void **>(t) + 1));

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

The second cast, on the left, appears redundant, and should be removed.  You
already had the desired type... and had just incremented the pointer... but
still had the same type as a result.

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

Done.

+}
+
+// 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));
+}
+
+} // namespace
+
+namespace tcmalloc {
+void *FL_Previous(void *t) {
+  void *previous = FL_Previous_No_Check(t);
+  if (previous)
+    MEMORY_CHECK(FL_Next_No_Check(previous),  t);
+  return previous;
+}
+
+void *FL_Next(void *t) {
+  void *next = FL_Next_No_Check(t);
+  if (next)
+    MEMORY_CHECK(FL_Previous_No_Check(next), t);
+  return next;
+}
+
+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)) = n;
+}
+
+// Makes the memory pointed at t a singleton doubly linked list.
+inline void FL_Init(void *t) {
+  FL_SetPrevious(t, NULL);
+  FL_SetNext(t, NULL);
+}
+
+// Pushes element to a linked list located 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 that begins at *list, and
+// upates *list to point to the next element in the list.  Return the

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

typo: upates-->updates

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

Done.

+// 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); // Fixes remainder of list.

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

Not sure what comment means... probably you should delete it.

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

Done.

+  if (*list != NULL)
+    FL_SetPrevious(*list, NULL);
+
+  return result;
+}
+
+// Remove N elements from a linked list to which head points.  head will be
+// modified to point to the new head.  start will point to the first
+// node of the range, end points to last node in range
+// This function assumes that you aren't trying to pop N > FL_Size(*head)
+// nodes, and that *head is not 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 of the doubly linked list that begins at the node
+// located at start and ends at he node end into the linked list at

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

typo: "at he node" --> "at the node"

IMO, you should put vertical bars around variable names in comments.  It will
make all the comments in this file much more readable.  You'll probably get away
with fewer words as well.  For instance, the above comment would become:

"Pushes the nodes of the doubly linked list beginning at |start| and ending at
|end| into the linked list at |*head|.  |*head| is updated to point to the new
head of the list.  |head| must not be null."

Note that as I rewrote it, I also realized the last sentence was mistaken, as
|head| must not be null, but |*head| can be null, and this fact is handled on
line 158.

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

Done.

+// location *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 before pushing is done
+  // when calling FL_Next, FL_Previous.
+  FL_Next(start);
+  FL_Previous(end);
+  ASSERT(FL_Previous_No_Check(start) == NULL);
+  ASSERT(FL_Next_No_Check(end) == NULL);
+
+  if (*head) {
+    ASSERT(FL_Previous_No_Check(*head) == NULL);

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

This is a critical check, and should not be debug only.  Suggest:
MEMORY_CHECK(FL_Previous_No_Check(*head), NULL);

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

Done.

+    FL_Next(*head);

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

IMO, you shouldn't bother with this interior check of the list, other than in
debug mode (at most).  Once you start to drift into the list, the question is
how far should you go?  This test is also far from free, as it refers to memory
that would not have to be touched during this call.

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

Done.

+    FL_SetNext(end, *head);
+    FL_SetPrevious(*head, end);
+  }
+  *head = start;
+}
+
+} // namespace tcmalloc
+
+#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST