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

third_party/tcmalloc/chromium/src/free_list.cc

Index: third_party/tcmalloc/chromium/src/free_list.cc
diff --git a/third_party/tcmalloc/chromium/src/free_list.cc b/third_party/tcmalloc/chromium/src/free_list.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d6d7b2a955430221674319b058677dc3461a5093
--- /dev/null
+++ b/third_party/tcmalloc/chromium/src/free_list.cc
@@ -0,0 +1,178 @@
+// 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 causes 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**>(t)[1];
+}
+
+// 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)[0];
+}
+
+} // 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)[0] = n;
+}
+
+// Makes the element 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 whose first element is 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 whose first element is at
+// |*list|, and updates |*list| to point to the next element in the
+// list.  Returns the 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);
+  if (*list != NULL)
+    FL_SetPrevious(*list, NULL);
+
+  return result;
+}
+
+// Remove |n| elements from linked list at whose first element is at
+// |*head|.  |head| will be modified to point to the new head.
+// |start| will point to the first node of the range, |end| will point
+// to the last node in the range. |n| must be <= FL_Size(|*head|)
+// If |n| > 0, |head| must not be 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 in the list begginning at |start| whose last node
+// is |end| into the linked list at |*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 is done by calling
+  // FL_Next and FL_Previous.
+  FL_Next(start);
+  FL_Previous(end);
+  ASSERT(FL_Previous_No_Check(start) == NULL);
+  ASSERT(FL_Next_No_Check(end) == NULL);
+
+  if (*head) {
+    MEMORY_CHECK(FL_Previous_No_Check(*head), NULL);
+    FL_SetNext(end, *head);
+    FL_SetPrevious(*head, end);
+  }
+  *head = start;
+}
+
+size_t FL_Size(void *head){
+  int count = 0;

[jar (doing other things), 2011/08/29 20:55:21]

Please validate:
MEMORY_CHECK(FL_Previous_No_Check(*head), NULL);

[bxx, 2011/08/29 21:38:13]

Used assert because original implementation doesn't require Size() to be called
on head of list.

[jar (doing other things), 2011/08/29 21:54:33]

The original implementation (via SLL_*) appears to be more generic, and hence
may need to service other users in such strange contexts.  Your implementation
is specifically only for the allocator (at least currently).

If you agree enough that you would put in an assert, then you have established
the "contract" and no caller should ever pass in anything but the head of a
list... which means the MEMORY_CHECK is appropriate (and actually cost free...
since the reading of the "next" pointer will load the cache line, facilitating
reading of the "prev" pointer, and vice versa).

I thought the only use was when called with the head of the list.  Looking
closer, I don't see any uses of it at all in the codebase.  

IMO, you should use MEMORY_CHECK() to validate the list maximally at runtime (in
conformance to your ASSERT stated contract).

On 2011/08/29 21:38:13, bxx wrote:

[bxx, 2011/08/29 22:17:12]

Fair enough.

+  while (head) {
+    count++;
+    head = FL_Next(head);
+  }
+  return count;
+}
+
+} // namespace tcmalloc
+
+#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST