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

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

I suspect (not sure) this code would be a lot cleaner if you defined a struct,
and routinely cast to pointer to that struct for manipulation.  

struct Node {
  Node* next;
  Node* prev;
};

You might even have helper functions:
void* VoidPointer(Node*);
Node* NodePointer(void*);

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

I am currently following the style in which the singly-linked list
implementation accesses pointers.  Would it be better to be consistent with
their implementation or do it this way?
On 2011/08/20 02:40:30, jar wrote:

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

This file is entirely written by you, so things like spacing and comments and
such should IMO be "current code style" compliant.

Across files, I've never seen much style tainting, beyond header vs cc file,
which use the same names for arguments, even in older styles IMO.

A a general rule, I hate casts, as they tend to hide errors (being a C coder of
the distant past... I've been burned too many times to count).  As a result, I
vastly prefer (if not forced by style compatibility) to minimize the number of
places I have to cast.  For instance, having a lone pair of helper functions
that do the pair of casts you need, would be nicer.  It would also have caught
(via type checking!) the duplicate cast I noticed.

If you want to hold with the other files style, that is ok, but when allowed,
I'd opt for newer and better style.



On 2011/08/24 00:19:24, bxx wrote:

+}
+
+// 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)
+    ASSERT(FL_Next_No_Check(previous) ==  t);

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

I would expect these to be places where we validate memory, and crash otherwise.
 Why are you just doing a debug check?

I think you should have two kinds of getters.  One that does the check, and one
that doesn't.  With the current code, many checks are repeated 3-5 times in
debug, and sometimes, you miss a check in release mode.  Since you are really
hardening this, I'd suggest that the first pass create code that does all the
critical checking exactly once (per push or pop operation).  If you decide you
want more (in Debug?), then add that on top.

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

Done.

+  return previous;
+}
+
+void *FL_Next(void *t) {
+  void *next = FL_Next_No_Check(t);
+  if (next)
+    ASSERT(FL_Previous_No_Check(next) == t);

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

Again, this this should IMO definitely be MEMORY_CHECK(), and not merely a debug
assertion.

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

Done.

+  return next;
+}
+
+inline void FL_SetPrevious(void *t, void *n) {
+  *(reinterpret_cast<void**> (static_cast<void **>(t) + 1)) = n;

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

I don't think the second cast (on the left) is needed.

You should probably standardize on reinterpret_cast<>, and also it would be much
better to have a struct, and not have to do explicit pointer arithmetic (re: "..
+ 1").

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

Done.

+}
+
+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.

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

nit: use 80 characters of width so you don't need so many lines.  Please do this
throughout the file.

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

Done.

+void FL_Push(void **list, void *element) {
+  void *old = *list;
+  if (old == NULL) {  // build singleton list

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

nit: Comments should start with caps, be a complete sentence, and end with a
period.

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

I have been fixing this in my code, but I see that many of the existing shorter
comments don't have a period at the end.
On 2011/08/20 02:40:30, jar wrote:

+    FL_Init(element);
+  } else {
+    if (FL_Next(old))

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

This is going deeper into the list than any pointers we really need to depend on
or touch, so I don't know that you want to go there.  You end up wondering where
you should stop.  IMO, you should keep it to a minimum. This means you should
note every redundant value (back pointer) you set as the list takes possession
of the data, and be sure you check it (once) as it releases the data.

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

Done.

+      MEMORY_CHECK(FL_Previous(FL_Next(old)), old);

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

At best, you should use the *_No_Check versions in all MEMORY_CHECK() calls, as
the above repeats the same test effectively three times (currently in debug
mode).  Additionally, line 99 does this test also in debug mode (making a total
of 4 runs).

I think the test that was needed here and is missing is:
MEMORY_CHECK(FL_Prev_No_Check(old), NULL);
That ensures that the element that leads the list has not been placed into
another list since being pushed.

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

The potential issue I see with these NULL checks and all of the ones you mention
below is that nothing in the original implementation requires any of these
checks to pass.  I agree that these checks are a good idea, however it forces us
to make stronger assumptions.  I'll add these in as an ASSERT for the time
being.
On 2011/08/20 02:40:30, jar wrote:

+    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 address of the element that
+// was removed from the linked list.  *list must not be NULL.
+void *FL_Pop(void **list) {
+  void *result = *list;

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

Here again I'd suggest the test:

MEMORY_CHECK(FL_Prev_No_Check(result), NULL);

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

using ASSERT
On 2011/08/20 02:40:30, jar wrote:

+  if (result && FL_Next(result))  // pointer sanity check

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

result is always non-null (unless we make a mistake in a pop).

In fact, if result is null, then line 117 would segv.

Line 117 would then be clearer on this point if it read:
*list = FL_Next(result);

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

Done.

+    MEMORY_CHECK(FL_Previous(FL_Next(result)), result);

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

Again, the above does this same test for 3 times (plus one in line 114) in
debug.

I think you should instead rely on line 117, which currently does this test a
5th time, and make sure it does the test in non-debug mode.

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

Done.

+
+  *list = FL_Next(*list);  // Fix remainder of list
+  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);

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

This code is definitely a place to do validation, and that is why I thought that
Fl_Next() should be doing it in non-debug mode.   The cost is nothing, since
we're reading the other field of each block (cache lines should load both
addresses all the time).

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

Done.

+
+  *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 && FL_Next(*head)) {   // fixup popped list
+    MEMORY_CHECK(FL_Previous(FL_Next(*head)), *head);

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

This is again going one step too far in the checking, as we have no dependency
on the next of the head.

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

Done.

+    FL_SetPrevious(*head, NULL);

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

This is seemingly a bug.  We don't need to condition it on head having a next
value (as tested in line 145).  We need to always set prev to NULL at the start
of the list.

I'd suggest deleting line 146, and removing the condition FL_Next(*head) from
line 145.

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

Done.

+  }
+}
+
+// Pushes the nodes of the doubly linked list that begins at the
+// node located at start and ends at the node end
+// into the linked list at 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;

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

I'd suggest either asserting that end is NULL, or else not bothering to set it
on line 132.

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

We cannot make the assumption that if start is NULL then end will be null
because what ends up happening is that tcmalloc will poprange, pop *start, and
then pushrange.
See ThreadCache::FetchFromCentralCache  -> calls RemoveRange then
PushRange(count, Next(start),end) {in both the original and my version, of
course this could be changed}
  
On 2011/08/20 02:40:30, jar wrote:

+
+  // Sanity check ends of list to push before pushing
+  if (FL_Next(start))
+    MEMORY_CHECK(FL_Previous(FL_Next(start)), start);

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

I have mixed feelings about whether that test is critical... but I'm ok with it.
What you left out that is IMO significant is that
MEMORY_CHECK(FL_Previous_No_Check(start), NULL);

Perhaps you don't care about that pointer (at the start of the list, but IMO, it
is good to keep this whole structure clean.  If you want to leave it dangling,
you really need to say so up front (define the expected conditions at the ends
of the list).  Line 65 suggested to me that the data is always either valid, or
NULL.

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

Used ASSERT.
On 2011/08/20 02:40:30, jar wrote:

+  if (FL_Previous(end))
+    MEMORY_CHECK(FL_Next(FL_Previous(end)), end);

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

I'd also vote for a check here:
ASSERT(FL_Next_No_Check(end) == NULL);

You set it on line 143, but I had a hard time spotting it, and assertion would
make it easier (for me) to see correctness.

I'm fine for using assertions while we pass data between your methods, and using
the MEMORY_CHECK() when we get data back after having it out in circulation
(potentially getting overwritten) for any period of time.

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

Done.

+
+  if (*head != NULL) {
+    if (FL_Next(*head))
+      MEMORY_CHECK(FL_Previous(FL_Next(*head)), *head);
+
+    FL_SetNext(end, *head);
+    FL_SetPrevious(*head, end);

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

Again I'd like to first see a:
MEMORY_CHECK(FL_Previous_No_Check(*head), NULL);

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

Used ASSERT
On 2011/08/20 02:40:30, jar wrote:

+  }
+  *head = start;
+}
+
+}  // namespace tcmalloc
+
+#endif  // TCMALLOC_USE_DOUBLYLINKED_FREELIST