BuddyAllocator.h

Go to the documentation of this file.

/*
 * /phoenix/include/common/BuddyAllocator.h
 *
 * This file is a part of Phoenix operating system.
 * Copyright (c) 2011-2012, Artyom Lebedev <artyom.lebedev@gmail.com>
 * All rights reserved.
 * See COPYING file for copyright details.
 */

#ifndef BUDDYALLOCATOR_H_
#define BUDDYALLOCATOR_H_

class BuddyAllocatorBase {
public:
    typedef uintptr_t Addr;

    enum :size_t {
        MAX_ORDER = sizeof(Addr) * NBBY,
        MAX_CACHE_SIZE = U16_MAX,
    };

    BuddyAllocatorBase();

    ~BuddyAllocatorBase();

    RetCode Initialize(Addr startAddress, Addr endAddress, int minOrder = 0,
                       int maxOrder = -1, size_t cacheSize = 8192);

private:
    bool _isInitialized = false;
    Addr _startAddress, _endAddress;
    int _minOrder, _maxOrder;

    class CacheEntry {
    public:
        typedef u16 Index; 
        typedef Index ListHead; 
        static const Index NONE = ~0;

        int Compare(CacheEntry &e) { return address - e.address; }
        int Compare(Addr &address) { return address - this->address; }
        typedef RBTree<CacheEntry, &CacheEntry::Compare, Addr, &CacheEntry::Compare> Tree;

        Addr address;  
        Index next = NONE, 
              prev = NONE; 
        Tree::Entry treeEntry;

        inline CacheEntry *GetPtr(CacheEntry *cache, Index idx) { return &cache[idx]; }
        inline Index GetIdx(CacheEntry *cache) { return this - cache; }

        void Insert(CacheEntry *cache, ListHead &head);

        void Delete(CacheEntry *cache, ListHead &head);
    };

    CacheEntry *_cache = 0;
    size_t _cacheSize;
    CacheEntry::ListHead _freeCacheEntries = CacheEntry::NONE;
    CacheEntry::Tree _cacheTree;

    class OrderPool {
    public:
        RetCode Initialize(size_t numBlocks);
        ~OrderPool() {/* XXX */}
    private:
        u8 *_bitmapData = 0; 
        BitString<> _bitmap; 
        CacheEntry::ListHead _freeBlocks; 
    };

    OrderPool *_pool = 0;

    inline int _GetOrder(Addr size) {
        int order = 0;
        Addr osize = 1;
        while (osize < size) {
            order++;
            osize <<= 1;
        }
        return order;
    }

    inline Addr _GetOrderSize(int order) {
        ASSERT(order >= 0);
        return 1 << order;
    }

    void _Free();
};

template <class AddrType>
class BuddyAllocator : public BuddyAllocatorBase {
public:
    inline BuddyAllocator() : BuddyAllocatorBase() { }

    inline RetCode Initialize(AddrType startAddress, AddrType endAddress,
                              int minOrder = 0,  int maxOrder = -1,
                              size_t cacheSize = 8192)
    {
        return BuddyAllocatorBase::Initialize(startAddress, endAddress,
                                              minOrder, maxOrder, cacheSize);
    }
};


#endif /* BUDDYALLOCATOR_H_ */