1// Copyright (c) 2008, 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: Sanjay Ghemawat <opensource@google.com> 32// 33// A Span is a contiguous run of pages. 34 35#ifndef TCMALLOC_SPAN_H_ 36#define TCMALLOC_SPAN_H_ 37 38#include <config.h> 39#include "common.h" 40 41namespace tcmalloc { 42 43// Information kept for a span (a contiguous run of pages). 44struct Span { 45 PageID start; // Starting page number 46 Length length; // Number of pages in span 47 Span* next; // Used when in link list 48 Span* prev; // Used when in link list 49 void* objects; // Linked list of free objects 50 unsigned int refcount : 16; // Number of non-free objects 51 unsigned int sizeclass : 8; // Size-class for small objects (or 0) 52 unsigned int location : 2; // Is the span on a freelist, and if so, which? 53 unsigned int sample : 1; // Sampled object? 54 55#undef SPAN_HISTORY 56#ifdef SPAN_HISTORY 57 // For debugging, we can keep a log events per span 58 int nexthistory; 59 char history[64]; 60 int value[64]; 61#endif 62 63 // What freelist the span is on: IN_USE if on none, or normal or returned 64 enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST }; 65}; 66 67#ifdef SPAN_HISTORY 68void Event(Span* span, char op, int v = 0); 69#else 70#define Event(s,o,v) ((void) 0) 71#endif 72 73// Allocator/deallocator for spans 74Span* NewSpan(PageID p, Length len); 75void DeleteSpan(Span* span); 76 77// ------------------------------------------------------------------------- 78// Doubly linked list of spans. 79// ------------------------------------------------------------------------- 80 81// Initialize *list to an empty list. 82void DLL_Init(Span* list); 83 84// Remove 'span' from the linked list in which it resides, updating the 85// pointers of adjacent Spans and setting span's next and prev to NULL. 86void DLL_Remove(Span* span); 87 88// Return true iff "list" is empty. 89inline bool DLL_IsEmpty(const Span* list) { 90 return list->next == list; 91} 92 93// Add span to the front of list. 94void DLL_Prepend(Span* list, Span* span); 95 96// Return the length of the linked list. O(n) 97int DLL_Length(const Span* list); 98 99} // namespace tcmalloc 100 101#endif // TCMALLOC_SPAN_H_ 102