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