1// Copyright (c) 2011, Google Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright
9// notice, this list of conditions and the following disclaimer.
10//     * Redistributions in binary form must reproduce the above
11// copyright notice, this list of conditions and the following disclaimer
12// in the documentation and/or other materials provided with the
13// distribution.
14//     * Neither the name of Google Inc. nor the names of its
15// contributors may be used to endorse or promote products derived from
16// this software without specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30// ---
31// Author: Rebecca Shapiro <bxx@google.com>
32//
33// This file contains declarations of functions that implement doubly
34// linked lists and definitions of functions that implement singly
35// linked lists.  It also contains macros to tell the SizeMap class
36// how much space a node in the freelist needs so that SizeMap can
37// create large enough size classes.
38
39#ifndef TCMALLOC_FREE_LIST_H_
40#define TCMALLOC_FREE_LIST_H_
41
42#include <stddef.h>
43#include "internal_logging.h"
44#include "linked_list.h"
45#include "system-alloc.h"
46
47// Remove to enable singly linked lists (the default for open source tcmalloc).
48#define TCMALLOC_USE_DOUBLYLINKED_FREELIST
49
50namespace tcmalloc {
51
52#if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST)
53
54// size class information for common.h.
55static const bool kSupportsDoublyLinkedList = true;
56
57void FL_PopRange(void **head, int n, void **start, void **end);
58void FL_PushRange(void **head, void *start, void *end);
59size_t FL_Size(void *head);
60
61template <typename T> inline void FL_EqualityCheck(const T& v0,
62                                                   const T& v1,
63                                                   const char* file,
64                                                   int line) {
65  if (v0 != v1) Log(kCrash, file, line, "Memory corruption detected.");
66}
67
68inline void EnsureNonLoop(void* node, void* next) {
69  // We only have time to do minimal checking.  We don't traverse the list, but
70  // only look for an immediate loop (cycle back to ourself).
71  if (node != next) return;
72  Log(kCrash, __FILE__, __LINE__, "Circular loop in list detected: ", next);
73}
74
75inline void* MaskPtr(void* p) {
76  // Maximize ASLR entropy and guarantee the result is an invalid address.
77  const uintptr_t mask = ~(reinterpret_cast<uintptr_t>(TCMalloc_SystemAlloc)
78                           >> 13);
79  return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(p) ^ mask);
80}
81
82inline void* UnmaskPtr(void* p) {
83  return MaskPtr(p);
84}
85
86// Returns value of the |previous| pointer w/out running a sanity
87// check.
88inline void *FL_Previous_No_Check(void *t) {
89  return UnmaskPtr(reinterpret_cast<void**>(t)[1]);
90}
91
92// Returns value of the |next| pointer w/out running a sanity check.
93inline void *FL_Next_No_Check(void *t) {
94  return UnmaskPtr(reinterpret_cast<void**>(t)[0]);
95}
96
97inline void *FL_Previous(void *t) {
98  void *previous = FL_Previous_No_Check(t);
99  if (previous) {
100    FL_EqualityCheck(FL_Next_No_Check(previous), t, __FILE__, __LINE__);
101  }
102  return previous;
103}
104
105inline void FL_SetPrevious(void *t, void *n) {
106  EnsureNonLoop(t, n);
107  reinterpret_cast<void**>(t)[1] = MaskPtr(n);
108}
109
110inline void FL_SetNext(void *t, void *n) {
111  EnsureNonLoop(t, n);
112  reinterpret_cast<void**>(t)[0] = MaskPtr(n);
113}
114
115inline void *FL_Next(void *t) {
116  void *next = FL_Next_No_Check(t);
117  if (next) {
118    FL_EqualityCheck(FL_Previous_No_Check(next), t, __FILE__, __LINE__);
119  }
120  return next;
121}
122
123// Pops the top element off the linked list whose first element is at
124// |*list|, and updates |*list| to point to the next element in the
125// list.  Returns the address of the element that was removed from the
126// linked list.  |list| must not be NULL.
127inline void *FL_Pop(void **list) {
128  void *result = *list;
129  ASSERT(FL_Previous_No_Check(result) == NULL);
130  *list = FL_Next(result);
131  if (*list != NULL) {
132    FL_SetPrevious(*list, NULL);
133  }
134  return result;
135}
136
137// Makes the element at |t| a singleton doubly linked list.
138inline void FL_Init(void *t) {
139  FL_SetPrevious(t, NULL);
140  FL_SetNext(t, NULL);
141}
142
143// Pushes element to a linked list whose first element is at
144// |*list|. When this call returns, |list| will point to the new head
145// of the linked list.
146inline void FL_Push(void **list, void *element) {
147  void *old = *list;
148  if (old == NULL) { // Builds singleton list.
149    FL_Init(element);
150  } else {
151    ASSERT(FL_Previous_No_Check(old) == NULL);
152    FL_SetNext(element, old);
153    FL_SetPrevious(old, element);
154    FL_SetPrevious(element, NULL);
155  }
156  *list = element;
157}
158
159#else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined
160static const bool kSupportsDoublyLinkedList = false;
161
162inline void *FL_Next(void *t) {
163  return SLL_Next(t);
164}
165
166inline void FL_Init(void *t) {
167  SLL_SetNext(t, NULL);
168}
169
170inline void FL_Push(void **list, void *element) {
171  if(*list != element) {
172    SLL_Push(list,element);
173    return;
174  }
175  Log(kCrash, __FILE__, __LINE__, "Double Free of %p detected", element);
176}
177
178inline void *FL_Pop(void **list) {
179  return SLL_Pop(list);
180}
181
182// Removes |N| elements from a linked list to which |head| points.
183// |head| will be modified to point to the new |head|.  |start| and
184// |end| will point to the first and last nodes of the range.  Note
185// that |end| will point to NULL after this function is called.
186inline void FL_PopRange(void **head, int n, void **start, void **end) {
187  SLL_PopRange(head, n, start, end);
188}
189
190inline void FL_PushRange(void **head, void *start, void *end) {
191  SLL_PushRange(head,start,end);
192}
193
194inline size_t FL_Size(void *head) {
195  return SLL_Size(head);
196}
197
198#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
199
200} // namespace tcmalloc
201
202#endif // TCMALLOC_FREE_LIST_H_
203