1/* 2 * Copyright (c) 2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20/* 21 FreeList.h 22 Free list for memory allocator 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#pragma once 27#ifndef __AUTO_FREE_LIST__ 28#define __AUTO_FREE_LIST__ 29 30#include "Configuration.h" 31#include "Definitions.h" 32#include "Range.h" 33 34namespace Auto { 35 36 // Forward declarations 37 // 38 class Subzone; 39 40 41 //----- FreeListNode -----// 42 43 class FreeListNode : public Preallocated { 44 private: 45 46 FreeListNode *_prev; // previous node or NULL for head 47 FreeListNode *_next; // next node or NULL for tail 48 usword_t _size; // number of free bytes 49 bool _purged; // note: this field must only be used for nodes > 2 quanta (see Admin::purge_free_space()). 50 // WARNING: No more fields. Must fit in a 16 byte quantum and size is 51 // always stuffed in last word of free bytes. 52 //usword_t _size_again; // at end of free block 53 54 // _prev/_next pointers are bitwise complemented to make them look less like valid data. 55 static FreeListNode *flip(FreeListNode *node) { return (FreeListNode *)(uintptr_t(node) ^ all_ones); } 56 57 public: 58 59 // 60 // Constructor 61 // 62 FreeListNode(FreeListNode *prev, FreeListNode *next, usword_t size) { 63 set_prev(prev); 64 set_next(next); 65 set_size(size); 66 if (size >= allocate_quantum_medium) _purged = false; 67 } 68 69 FreeListNode() { 70 // reconstruct a free list node in place 71 set_prev(NULL); 72 set_next(NULL); 73 ASSERTION(size() == size_again()); 74 } 75 76 // 77 // Accessors 78 // 79 FreeListNode *prev() const { return flip(_prev); } 80 FreeListNode *next() const { return flip(_next); } 81 usword_t size() const { return _size; } 82 usword_t size_again() { return *(usword_t *)displace(this, _size - sizeof(usword_t)); } 83 void set_prev(FreeListNode *prev) { _prev = flip(prev); } 84 void set_next(FreeListNode *next) { _next = flip(next); } 85 86 // 87 // The following are only used by by Admin::purge_free_space() for medium quanta nodes. 88 // 89 bool is_purged() const { ASSERTION(_size >= allocate_quantum_medium); return _purged; } 90 void set_purged(bool purged) { ASSERTION(_size >= allocate_quantum_medium); _purged = purged; } 91 92 // 93 // Consistency 94 // 95 void validate() { ASSERTION(size() == size_again()); } 96 97 98 // 99 // address 100 // 101 // Return address of free block. Some hocus pocus here. Returns NULL 102 // if the node is NULL. 103 // 104 void *address() const { return (void *)this; } 105 106 107 // 108 // set_size 109 // 110 // Set size field and place size in last word of free block so that it 111 // can be found to merge prior blocks. 112 // 113 void set_size(usword_t size) { 114 // set size field 115 _size = size; 116 // set size at end of free block 117 *(usword_t *)displace(this, _size - sizeof(usword_t)) = size; 118 } 119 120 121 // 122 // prior_node 123 // 124 // Return the prior adjacent free block. 125 // 126 FreeListNode *prior_node() { 127 // get address of last word in prior free block 128 usword_t *end_size = (usword_t *)displace(this, -sizeof(usword_t)); 129 // return size from prior free block 130 return (FreeListNode *)displace(this, -(*end_size)); 131 } 132 133 134 // 135 // next_block 136 // 137 // Return the next adjacent block. 138 // 139 void *next_block() { return displace(this, _size); } 140 141 // 142 // purgeable_range 143 // 144 // Returns the address range of this node that can be safely passed to uncommit_memory(). 145 // 146 Range purgeable_range() { 147 Range r(align_up(displace(this, sizeof(FreeListNode))), align_down(displace(this, _size - sizeof(usword_t) - 1))); 148 return r; 149 } 150 }; 151 152 153 //----- FreeList -----// 154 155 class FreeList { 156 private: 157 158 // 159 // Constructor 160 // 161 FreeListNode *_head; // head of free list 162 FreeListNode *_tail; // tail of free list 163 164 public: 165 166 FreeList() 167 : _head(NULL), _tail(NULL) 168 {} 169 170 171 // 172 // Accessors 173 // 174 FreeListNode *head() const { return _head; } 175 176 177 // 178 // pop 179 // 180 // Pop the first node from the list. 181 // 182 FreeListNode *pop() { 183 // get first node 184 FreeListNode *node = _head; 185 186 // If there is a node and there is a next node 187 if (node) { 188 _head = node->next(); 189 if (_head) { 190 // update the next node's previous 191 _head->set_prev(NULL); 192 } else { 193 _tail = NULL; 194 } 195 } 196 197 return node; 198 } 199 200 201 // 202 // push 203 // 204 // Push an node onto the head of the list 205 // 206 void push(void *address, usword_t size) { 207 // apply FreeListNode template to address 208 FreeListNode *node = new(address) FreeListNode(NULL, _head, size); 209 // if there is a next node its previous 210 if (_head) { 211 _head->set_prev(node); 212 } else { 213 _tail = node; 214 } 215 // update list 216 _head = node; 217 } 218 219 220 // 221 // append 222 // 223 // append a node onto the tail of the list 224 // 225 void append(FreeListNode *node) { 226 node->set_prev(_tail); 227 if (!_head) { 228 _head = node; 229 } else { 230 _tail->set_next(node); 231 } 232 _tail = node; 233 } 234 235 236 // 237 // remove 238 // 239 // Remove a node from the list. 240 // 241 void remove(FreeListNode *node) { 242 FreeListNode *prev = node->prev(); 243 244 // if not front of list 245 if (prev) { 246 // link the previous node to the next 247 FreeListNode *next = node->next(); 248 prev->set_next(next); 249 // link the next node to the previous 250 if (next) { 251 next->set_prev(prev); 252 } else { 253 _tail = prev; 254 } 255 } else { 256 // pop the list 257 pop(); 258 } 259 } 260 261 262 // 263 // insert 264 // 265 // Inserts a newly constructed node into an already sorted list. 266 // 267 void insert(void *address, usword_t size) { 268 // keep list sorted. 269 FreeListNode *prevNode = NULL, *nextNode = _head; 270 while (nextNode != NULL) { 271 if (uintptr_t(address) < uintptr_t(nextNode)) break; 272 prevNode = nextNode; 273 nextNode = nextNode->next(); 274 } 275 FreeListNode *node = new(address) FreeListNode(prevNode, nextNode, size); 276 if (nextNode) nextNode->set_prev(node); 277 if (prevNode) prevNode->set_next(node); 278 if (_head == nextNode) _head = node; 279 if (_tail == prevNode) _tail = node; 280 } 281 282 283 // 284 // reset 285 // 286 // Reset the free list to empty. Nodes on the list are simply dropped. 287 // 288 void reset() { 289 _head = NULL; 290 _tail = NULL; 291 } 292 }; 293 294}; 295 296 297#endif // __AUTO_FREE_LIST__ 298