src/third_party/tcmalloc/chromium/src/free_list.h

   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
  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_