| // Copyright (c) 2011, Google Inc. |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following disclaimer |
| // in the documentation and/or other materials provided with the |
| // distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived from |
| // this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| // --- |
| // Author: Rebecca Shapiro <bxx@google.com> |
| // |
| // This file contains declarations of functions that implement doubly |
| // linked lists and definitions of functions that implement singly |
| // linked lists. It also contains macros to tell the SizeMap class |
| // how much space a node in the freelist needs so that SizeMap can |
| // create large enough size classes. |
| |
| #ifndef TCMALLOC_FREE_LIST_H_ |
| #define TCMALLOC_FREE_LIST_H_ |
| |
| #include <stddef.h> |
| #include "internal_logging.h" |
| #include "linked_list.h" |
| #include "system-alloc.h" |
| |
| // Remove to enable singly linked lists (the default for open source tcmalloc). |
| #define TCMALLOC_USE_DOUBLYLINKED_FREELIST |
| |
| namespace tcmalloc { |
| |
| #if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST) |
| |
| // size class information for common.h. |
| static const bool kSupportsDoublyLinkedList = true; |
| |
| void FL_PopRange(void **head, int n, void **start, void **end); |
| void FL_PushRange(void **head, void *start, void *end); |
| size_t FL_Size(void *head); |
| |
| template <typename T> inline void FL_EqualityCheck(const T& v0, |
| const T& v1, |
| const char* file, |
| int line) { |
| if (v0 != v1) Log(kCrash, file, line, "Memory corruption detected."); |
| } |
| |
| inline void EnsureNonLoop(void* node, void* next) { |
| // We only have time to do minimal checking. We don't traverse the list, but |
| // only look for an immediate loop (cycle back to ourself). |
| if (node != next) return; |
| Log(kCrash, __FILE__, __LINE__, "Circular loop in list detected: ", next); |
| } |
| |
| inline void* MaskPtr(void* p) { |
| // Maximize ASLR entropy and guarantee the result is an invalid address. |
| const uintptr_t mask = ~(reinterpret_cast<uintptr_t>(TCMalloc_SystemAlloc) |
| >> 13); |
| return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(p) ^ mask); |
| } |
| |
| inline void* UnmaskPtr(void* p) { |
| return MaskPtr(p); |
| } |
| |
| // Returns value of the |previous| pointer w/out running a sanity |
| // check. |
| inline void *FL_Previous_No_Check(void *t) { |
| return UnmaskPtr(reinterpret_cast<void**>(t)[1]); |
| } |
| |
| // Returns value of the |next| pointer w/out running a sanity check. |
| inline void *FL_Next_No_Check(void *t) { |
| return UnmaskPtr(reinterpret_cast<void**>(t)[0]); |
| } |
| |
| inline void *FL_Previous(void *t) { |
| void *previous = FL_Previous_No_Check(t); |
| if (previous) { |
| FL_EqualityCheck(FL_Next_No_Check(previous), t, __FILE__, __LINE__); |
| } |
| return previous; |
| } |
| |
| inline void FL_SetPrevious(void *t, void *n) { |
| EnsureNonLoop(t, n); |
| reinterpret_cast<void**>(t)[1] = MaskPtr(n); |
| } |
| |
| inline void FL_SetNext(void *t, void *n) { |
| EnsureNonLoop(t, n); |
| reinterpret_cast<void**>(t)[0] = MaskPtr(n); |
| } |
| |
| inline void *FL_Next(void *t) { |
| void *next = FL_Next_No_Check(t); |
| if (next) { |
| FL_EqualityCheck(FL_Previous_No_Check(next), t, __FILE__, __LINE__); |
| } |
| return next; |
| } |
| |
| // Pops the top element off the linked list whose first element is at |
| // |*list|, and updates |*list| to point to the next element in the |
| // list. Returns the address of the element that was removed from the |
| // linked list. |list| must not be NULL. |
| inline void *FL_Pop(void **list) { |
| void *result = *list; |
| ASSERT(FL_Previous_No_Check(result) == NULL); |
| *list = FL_Next(result); |
| if (*list != NULL) { |
| FL_SetPrevious(*list, NULL); |
| } |
| return result; |
| } |
| |
| // Makes the element at |t| a singleton doubly linked list. |
| inline void FL_Init(void *t) { |
| FL_SetPrevious(t, NULL); |
| FL_SetNext(t, NULL); |
| } |
| |
| // Pushes element to a linked list whose first element is at |
| // |*list|. When this call returns, |list| will point to the new head |
| // of the linked list. |
| inline void FL_Push(void **list, void *element) { |
| void *old = *list; |
| if (old == NULL) { // Builds singleton list. |
| FL_Init(element); |
| } else { |
| ASSERT(FL_Previous_No_Check(old) == NULL); |
| FL_SetNext(element, old); |
| FL_SetPrevious(old, element); |
| FL_SetPrevious(element, NULL); |
| } |
| *list = element; |
| } |
| |
| #else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined |
| static const bool kSupportsDoublyLinkedList = false; |
| |
| inline void *FL_Next(void *t) { |
| return SLL_Next(t); |
| } |
| |
| inline void FL_Init(void *t) { |
| SLL_SetNext(t, NULL); |
| } |
| |
| inline void FL_Push(void **list, void *element) { |
| if(*list != element) { |
| SLL_Push(list,element); |
| return; |
| } |
| Log(kCrash, __FILE__, __LINE__, "Double Free of %p detected", element); |
| } |
| |
| inline void *FL_Pop(void **list) { |
| return SLL_Pop(list); |
| } |
| |
| // Removes |N| elements from a linked list to which |head| points. |
| // |head| will be modified to point to the new |head|. |start| and |
| // |end| will point to the first and last nodes of the range. Note |
| // that |end| will point to NULL after this function is called. |
| inline void FL_PopRange(void **head, int n, void **start, void **end) { |
| SLL_PopRange(head, n, start, end); |
| } |
| |
| inline void FL_PushRange(void **head, void *start, void *end) { |
| SLL_PushRange(head,start,end); |
| } |
| |
| inline size_t FL_Size(void *head) { |
| return SLL_Size(head); |
| } |
| |
| #endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST |
| |
| } // namespace tcmalloc |
| |
| #endif // TCMALLOC_FREE_LIST_H_ |