free_list.cc revision 5821806d5e7f356e8fa4b058a389a808ea183019
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 functions that implement doubly linked and 34// singly linked lists. The singly linked lists are null terminated, 35// use raw pointers to link neighboring elements, and these pointers 36// are stored at the start of each element, independently of the 37// elements's size. Because pointers are stored within each element, 38// each element must be large enough to store two raw pointers if 39// doubly linked lists are employed, or one raw pointer if singly 40// linked lists are employed. On machines with 64 bit pointers, this 41// means elements must be at least 16 bytes in size for doubly linked 42// list support, and 8 bytes for singly linked list support. No 43// attempts are made to preserve the data in elements stored in the 44// list. 45// 46// Given a machine with pointers of size N (on a 64bit machine N=8, on 47// a 32bit machine, N=4), the list pointers are stored in the 48// following manner: 49// -In doubly linked lists, the |next| pointer is stored in the first N 50// bytes of the node and the |previous| pointer is writtend into the 51// second N bytes. 52// -In singly linked lists, the |next| pointer is stored in the first N 53// bytes of the node. 54// 55// For both types of lists: when a pop operation is performed on a non 56// empty list, the new list head becomes that which is pointed to by 57// the former head's |next| pointer. If the list is doubly linked, the 58// new head |previous| pointer gets changed from pointing to the former 59// head to NULL. 60 61 62#include <limits> 63#include <stddef.h> 64#include "free_list.h" 65#include "system-alloc.h" 66 67#if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST) 68 69using tcmalloc::kCrash; 70 71// TODO(jar): We should use C++ rather than a macro here. 72#define MEMORY_CHECK(v1, v2) \ 73 if (v1 != v2) Log(kCrash, __FILE__, __LINE__, "Memory corruption detected.") 74 75namespace { 76void EnsureNonLoop(void* node, void* next) { 77 // We only have time to do minimal checking. We don't traverse the list, but 78 // only look for an immediate loop (cycle back to ourself). 79 if (node != next) return; 80 Log(kCrash, __FILE__, __LINE__, "Circular loop in list detected: ", next); 81} 82 83inline void* MaskPtr(void* p) { 84 // Maximize ASLR entropy and guarantee the result is an invalid address. 85 const uintptr_t mask = ~(reinterpret_cast<uintptr_t>(TCMalloc_SystemAlloc) 86 >> 13); 87 return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(p) ^ mask); 88} 89 90inline void* UnmaskPtr(void* p) { 91 return MaskPtr(p); 92} 93 94// Returns value of the |previous| pointer w/out running a sanity 95// check. 96inline void *FL_Previous_No_Check(void *t) { 97 return UnmaskPtr(reinterpret_cast<void**>(t)[1]); 98} 99 100// Returns value of the |next| pointer w/out running a sanity check. 101inline void *FL_Next_No_Check(void *t) { 102 return UnmaskPtr(reinterpret_cast<void**>(t)[0]); 103} 104 105void *FL_Previous(void *t) { 106 void *previous = FL_Previous_No_Check(t); 107 if (previous) { 108 MEMORY_CHECK(FL_Next_No_Check(previous), t); 109 } 110 return previous; 111} 112 113inline void FL_SetPrevious(void *t, void *n) { 114 EnsureNonLoop(t, n); 115 reinterpret_cast<void**>(t)[1] = MaskPtr(n); 116} 117 118inline void FL_SetNext(void *t, void *n) { 119 EnsureNonLoop(t, n); 120 reinterpret_cast<void**>(t)[0] = MaskPtr(n); 121} 122 123} // namespace 124 125namespace tcmalloc { 126 127void *FL_Next(void *t) { 128 void *next = FL_Next_No_Check(t); 129 if (next) { 130 MEMORY_CHECK(FL_Previous_No_Check(next), t); 131 } 132 return next; 133} 134 135// Makes the element at |t| a singleton doubly linked list. 136void FL_Init(void *t) { 137 FL_SetPrevious(t, NULL); 138 FL_SetNext(t, NULL); 139} 140 141// Pushes element to a linked list whose first element is at 142// |*list|. When this call returns, |list| will point to the new head 143// of the linked list. 144void FL_Push(void **list, void *element) { 145 void *old = *list; 146 if (old == NULL) { // Builds singleton list. 147 FL_Init(element); 148 } else { 149 ASSERT(FL_Previous_No_Check(old) == NULL); 150 FL_SetNext(element, old); 151 FL_SetPrevious(old, element); 152 FL_SetPrevious(element, NULL); 153 } 154 *list = element; 155} 156 157// Pops the top element off the linked list whose first element is at 158// |*list|, and updates |*list| to point to the next element in the 159// list. Returns the address of the element that was removed from the 160// linked list. |list| must not be NULL. 161void *FL_Pop(void **list) { 162 void *result = *list; 163 ASSERT(FL_Previous_No_Check(result) == NULL); 164 *list = FL_Next(result); 165 if (*list != NULL) { 166 FL_SetPrevious(*list, NULL); 167 } 168 return result; 169} 170 171// Remove |n| elements from linked list at whose first element is at 172// |*head|. |head| will be modified to point to the new head. 173// |start| will point to the first node of the range, |end| will point 174// to the last node in the range. |n| must be <= FL_Size(|*head|) 175// If |n| > 0, |head| must not be NULL. 176void FL_PopRange(void **head, int n, void **start, void **end) { 177 if (n == 0) { 178 *start = NULL; 179 *end = NULL; 180 return; 181 } 182 183 *start = *head; // Remember the first node in the range. 184 void *tmp = *head; 185 for (int i = 1; i < n; ++i) { // Find end of range. 186 tmp = FL_Next(tmp); 187 } 188 *end = tmp; // |end| now set to point to last node in range. 189 *head = FL_Next(*end); 190 FL_SetNext(*end, NULL); // Unlink range from list. 191 192 if (*head ) { // Fixup popped list. 193 FL_SetPrevious(*head, NULL); 194 } 195} 196 197// Pushes the nodes in the list begginning at |start| whose last node 198// is |end| into the linked list at |*head|. |*head| is updated to 199// point be the new head of the list. |head| must not be NULL. 200void FL_PushRange(void **head, void *start, void *end) { 201 if (!start) return; 202 203 // Sanity checking of ends of list to push is done by calling 204 // FL_Next and FL_Previous. 205 FL_Next(start); 206 FL_Previous(end); 207 ASSERT(FL_Previous_No_Check(start) == NULL); 208 ASSERT(FL_Next_No_Check(end) == NULL); 209 210 if (*head) { 211 MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); 212 FL_SetNext(end, *head); 213 FL_SetPrevious(*head, end); 214 } 215 *head = start; 216} 217 218// Calculates the size of the list that begins at |head|. 219size_t FL_Size(void *head){ 220 int count = 0; 221 if (head) { 222 MEMORY_CHECK(FL_Previous_No_Check(head), NULL); 223 } 224 while (head) { 225 count++; 226 head = FL_Next(head); 227 } 228 return count; 229} 230 231} // namespace tcmalloc 232 233#else 234#include "linked_list.h" // for SLL_SetNext 235 236namespace { 237 238inline void FL_SetNext(void *t, void *n) { 239 tcmalloc::SLL_SetNext(t,n); 240} 241 242} 243 244#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST 245