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
50 namespace tcmalloc {
51
52 #if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST)
53
54 // size class information for common.h.
55 static const bool kSupportsDoublyLinkedList = true;
56
57 void FL_PopRange(void **head, int n, void **start, void **end);
58 void FL_PushRange(void **head, void *start, void *end);
59 size_t FL_Size(void *head);
60
FL_EqualityCheck(const T & v0,const T & v1,const char * file,int line)61 template <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
EnsureNonLoop(void * node,void * next)68 inline 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
MaskPtr(void * p)75 inline 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
UnmaskPtr(void * p)82 inline void* UnmaskPtr(void* p) {
83 return MaskPtr(p);
84 }
85
86 // Returns value of the |previous| pointer w/out running a sanity
87 // check.
FL_Previous_No_Check(void * t)88 inline 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.
FL_Next_No_Check(void * t)93 inline void *FL_Next_No_Check(void *t) {
94 return UnmaskPtr(reinterpret_cast<void**>(t)[0]);
95 }
96
FL_Previous(void * t)97 inline 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
FL_SetPrevious(void * t,void * n)105 inline void FL_SetPrevious(void *t, void *n) {
106 EnsureNonLoop(t, n);
107 reinterpret_cast<void**>(t)[1] = MaskPtr(n);
108 }
109
FL_SetNext(void * t,void * n)110 inline void FL_SetNext(void *t, void *n) {
111 EnsureNonLoop(t, n);
112 reinterpret_cast<void**>(t)[0] = MaskPtr(n);
113 }
114
FL_Next(void * t)115 inline 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.
FL_Pop(void ** list)127 inline 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.
FL_Init(void * t)138 inline 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.
FL_Push(void ** list,void * element)146 inline 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
160 static const bool kSupportsDoublyLinkedList = false;
161
162 inline void *FL_Next(void *t) {
163 return SLL_Next(t);
164 }
165
166 inline void FL_Init(void *t) {
167 SLL_SetNext(t, NULL);
168 }
169
170 inline 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
178 inline 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.
186 inline void FL_PopRange(void **head, int n, void **start, void **end) {
187 SLL_PopRange(head, n, start, end);
188 }
189
190 inline void FL_PushRange(void **head, void *start, void *end) {
191 SLL_PushRange(head,start,end);
192 }
193
194 inline 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