FreeList.h   [plain text]


/*
 * Copyright (c) 2011 Apple Inc. All rights reserved.
 *
 * @APPLE_APACHE_LICENSE_HEADER_START@
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 * @APPLE_APACHE_LICENSE_HEADER_END@
 */
/*
    FreeList.h
    Free list for memory allocator
    Copyright (c) 2004-2011 Apple Inc. All rights reserved.
 */

#pragma once
#ifndef __AUTO_FREE_LIST__
#define __AUTO_FREE_LIST__

#include "Configuration.h"
#include "Definitions.h"
#include "Range.h"

namespace Auto {

    // Forward declarations
    //
    class Subzone;
    
    
    //----- FreeListNode -----//
    
    class FreeListNode : public Preallocated {
      private:
      
        FreeListNode *_prev;            // previous node or NULL for head
        FreeListNode *_next;            // next node or NULL for tail
        usword_t      _size;            // number of free bytes 
        bool          _purged;          // note:  this field must only be used for nodes > 2 quanta (see Admin::purge_free_space()).
        // WARNING: No more fields.  Must fit in a 16 byte quantum and size is
        // always stuffed in last word of free bytes.
        //usword_t    _size_again;      // at end of free block
        
        // _prev/_next pointers are bitwise complemented to make them look less like valid data.
        static FreeListNode *flip(FreeListNode *node) { return (FreeListNode *)(uintptr_t(node) ^ all_ones); }
        
      public:
      
        //
        // Constructor
        //
        FreeListNode(FreeListNode *prev, FreeListNode *next, usword_t size) {
            set_prev(prev);
            set_next(next);
            set_size(size);
            if (size >= allocate_quantum_medium) _purged = false;
        }
        
        FreeListNode() {
            // reconstruct a free list node in place
            set_prev(NULL);
            set_next(NULL);
            ASSERTION(size() == size_again());
        }
        
        //
        // Accessors
        //
        FreeListNode *prev()         const { return flip(_prev); }
        FreeListNode *next()         const { return flip(_next); }
        usword_t size()              const { return _size; }
        usword_t size_again()              { return *(usword_t *)displace(this, _size - sizeof(usword_t)); }
        void set_prev(FreeListNode *prev)  { _prev = flip(prev); }
        void set_next(FreeListNode *next)  { _next = flip(next); }
        
        //
        // The following are only used by by Admin::purge_free_space() for medium quanta nodes.
        //
        bool is_purged()             const { ASSERTION(_size >= allocate_quantum_medium); return _purged; }
        void set_purged(bool purged)       { ASSERTION(_size >= allocate_quantum_medium); _purged = purged; }

        //
        // Consistency
        //
        void validate()                    { ASSERTION(size() == size_again()); }
        
        
        //
        // address
        //
        // Return address of free block.  Some hocus pocus here.  Returns NULL
        // if the node is NULL.
        //
        void *address()      const { return (void *)this; }
        
       
        //
        // set_size
        //
        // Set size field and place size in last word of free block so that it
        // can be found to merge prior blocks.
        //
        void set_size(usword_t size) {
            // set size field
            _size = size;
            // set size at end of free block
            *(usword_t *)displace(this, _size - sizeof(usword_t)) = size;
        }
        
        
        //
        // prior_node
        //
        // Return the prior adjacent free block.
        //
        FreeListNode *prior_node() {
            // get address of last word in prior free block
            usword_t *end_size = (usword_t *)displace(this, -sizeof(usword_t));
            // return size from prior free block
            return (FreeListNode *)displace(this, -(*end_size));
        }
        
        
        //
        // next_block
        //
        // Return the next adjacent block.
        //
        void *next_block() { return displace(this, _size);  }
        
        //
        // purgeable_range
        //
        // Returns the address range of this node that can be safely passed to uncommit_memory().
        //
        Range purgeable_range() {
            Range r(align_up(displace(this, sizeof(FreeListNode))), align_down(displace(this, _size - sizeof(usword_t) - 1)));
            return r;
        }
    };
    
    
    //----- FreeList -----//
    
    class FreeList {
      private:
    
        //
        // Constructor
        //
        FreeListNode *_head;            // head of free list
        FreeListNode *_tail;            // tail of free list

      public:
      
        FreeList()
        : _head(NULL), _tail(NULL)
        {}
        
        
        //
        // Accessors
        //
        FreeListNode *head() const { return _head; }
        
        
        //
        // pop
        //
        // Pop the first node from the list.
        //
        FreeListNode *pop() {
            // get first node
            FreeListNode *node = _head;
            
            // If there is a node and there is a next node
            if (node) {
                _head = node->next();
                if (_head) {
                    // update the next node's previous
                    _head->set_prev(NULL);
                } else {
                    _tail = NULL;
                }
            }
            
            return node;
        }
        
        
        //
        // push
        //
        // Push an node onto the head of the list
        //
        void push(void *address, usword_t size) {
            // apply FreeListNode template to address
            FreeListNode *node = new(address) FreeListNode(NULL, _head, size);
            // if there is a next node its previous
            if (_head) {
                _head->set_prev(node);
            } else {
                _tail = node;
            }
            // update list
            _head = node;
        }
        
        
        //
        // append
        //
        // append a node onto the tail of the list
        //
        void append(FreeListNode *node) {
            node->set_prev(_tail);
            if (!_head) {
                _head = node;
            } else {
                _tail->set_next(node);
            }
            _tail = node;
        }
        
        
        //
        // remove
        //
        // Remove a node from the list.
        //
        void remove(FreeListNode *node) {
            FreeListNode *prev = node->prev();
            
            // if not front of list
            if (prev) {
                // link the previous node to the next
                FreeListNode *next = node->next();
                prev->set_next(next);
                // link the next node to the previous
                if (next) {
                    next->set_prev(prev);
                } else {
                    _tail = prev;
                }
            } else {
                // pop the list
                pop();
            }
        }
        
        
        //
        // insert
        //
        // Inserts a newly constructed node into an already sorted list.
        //
        void insert(void *address, usword_t size) {
            // keep list sorted.
            FreeListNode *prevNode = NULL, *nextNode = _head;
            while (nextNode != NULL) {
                if (uintptr_t(address) < uintptr_t(nextNode)) break;
                prevNode = nextNode;
                nextNode = nextNode->next();
            }
            FreeListNode *node = new(address) FreeListNode(prevNode, nextNode, size);
            if (nextNode) nextNode->set_prev(node);
            if (prevNode) prevNode->set_next(node);
            if (_head == nextNode) _head = node;
            if (_tail == prevNode) _tail = node;
        }
        
        
        //
        // reset
        //
        // Reset the free list to empty. Nodes on the list are simply dropped.
        //
        void reset() {
            _head = NULL;
            _tail = NULL;
        }
    };

};


#endif // __AUTO_FREE_LIST__