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 (at) 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 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 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 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 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. 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. 93 inline void *FL_Next_No_Check(void *t) { 94 return UnmaskPtr(reinterpret_cast<void**>(t)[0]); 95 } 96 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 105 inline void FL_SetPrevious(void *t, void *n) { 106 EnsureNonLoop(t, n); 107 reinterpret_cast<void**>(t)[1] = MaskPtr(n); 108 } 109 110 inline void FL_SetNext(void *t, void *n) { 111 EnsureNonLoop(t, n); 112 reinterpret_cast<void**>(t)[0] = MaskPtr(n); 113 } 114 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. 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. 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. 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
