"Buddy Memory Allocation" Question

This is a discussion on "Buddy Memory Allocation" Question within the C++ Programming forums, part of the General Programming Boards category; Hello All I wanted to play around with some memory pool techniques, and do some testing/benchmarking with an application of ...

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    2

    "Buddy Memory Allocation" Question

    Hello All

    I wanted to play around with some memory pool techniques, and do some testing/benchmarking with an application of ours (a small embedded application). I'm a little hung up on the "Buddy Memory Allocation" techinque.

    http://en.wikipedia.org/wiki/Buddy_memory_allocation

    I found some code at:

    http://www.brpreiss.com/books/opus4/html/page431.html

    Which spells, most of, it out in no-uncertain terms. However, there is one function missing (an exercise for the reader I suppose =): BuddyPool::Buddy().

    I was trying to figure out an intelligent way of writing this function, but I'm not really having alot of success. I guess, I'm a little confused about how the Buddy() function returns the location of it's "buddy". Correct me if I'm wrong, but the parameter that is passed into Buddy() is the beginning of the block. Given this beginning of the block, I'm not certain how to find the end of the block. And without the end of the block, I can't take 1/2 of it and return that as the buddy.

    I'm sure I'm missing something obvious, but it's not coming to me. Does anyone have any suggestions?

    Below is the code. Thanks!

    --BuddyPool.h--
    Code:
    #ifndef  BUDDYPOOL_INC
    #define  BUDDYPOOL_INC
    
    class BuddyPool
    {
        public:
            enum Status { free, reserved };
            struct Header
            {
                Status status: 1;
    //            unsigned int k : bitsizeof(unsigned int) - 1U;
                unsigned int k : 31;
    
    		};
            struct Block : public Header
            {
    //            enum { size = 16 };
                enum { size = 64 };
    			struct Links
                {
                    Block *next;
                    Block *prev;
                };
                union
                {
                    Links link;
                    char userPart [size - sizeof(Header)];
                };
            };
    
        private:
            unsigned int m;
            unsigned int numberOfBlocks;
            Block *pool;
            Block *sentinel;
    
            static void Unlink(Block &);
            static void InsertAfter(Block &, Block &);
            Block &Buddy(Block &) const;
    
        public:
            BuddyPool(size_t);
            ~BuddyPool();
    
            void *Acquire(size_t);
            void Release(void *);
    };
    
    #endif   /* ----- #ifndef BUDDYPOOL_INC  ----- */
    --BuddyPool.cpp--
    Code:
    #include <WinDef.h>
    
    #include "BuddyPool.h"
    
    //------------------------------------------------------------------------------
    // Log2Ceil
    //------------------------------------------------------------------------------
    unsigned int Log2Ceil(unsigned int val)
    {
        unsigned int L;
        for (L = 0; (1ul<<L) < val; L++);
    
        return L;
    }
    
    //------------------------------------------------------------------------------
    // BuddyPool
    //------------------------------------------------------------------------------
    BuddyPool::BuddyPool(size_t bytes) :
        m(Log2Ceil(bytes)),
        numberOfBlocks( (1 << m) / sizeof(Block)),
        pool (new Block[numberOfBlocks + m +1]),
        sentinel(pool + numberOfBlocks)
    {
        for (unsigned int i = 0; i <= m; ++i) {
            sentinel[i].link.next = &sentinel[i];
            sentinel[i].link.prev = &sentinel[i];
        }
    
        Block &head = pool[0];
        head.status = free;
        head.k = m;
        InsertAfter(sentinel[m], head);
    }
    
    //------------------------------------------------------------------------------
    // ~BuddyPool
    //------------------------------------------------------------------------------
    BuddyPool::~BuddyPool()
    {
        delete [] pool;
    }
    
    //------------------------------------------------------------------------------
    // Acquire
    //------------------------------------------------------------------------------
    void *BuddyPool::Acquire(size_t bytes)
    {
        unsigned int kPrime = Log2Ceil(bytes + sizeof(Header));
    
        unsigned int i = kPrime;
        while (i <= m && sentinel[i].link.next == &sentinel[i]) {
            ++i;
        }
        if (i > m) {
            return NULL;    // throw bad_alloc("out of memory");
        }
    
        Block &block = *sentinel[i].link.next;
        Unlink(block);
        while (block.k > kPrime) {
            block.k -= 1;
            Block &buddy = Buddy(block);
            buddy.status = free;
            buddy.k = block.k;
            InsertAfter(sentinel[buddy.k], buddy);
        }
        block.status = reserved;
        return block.userPart;
    }
    
    //------------------------------------------------------------------------------
    // Release
    //------------------------------------------------------------------------------
    void BuddyPool::Release(void *arg)
    {
        Block &block = *reinterpret_cast<Block *>(
                reinterpret_cast<Header *>(arg) - 1U);
    
        if (&block < pool || &block >= pool + numberOfBlocks) {
            return; // throw invalid_argument("invalid pointer");
        }
    
        block.status = free;
        Block *ptr;
        for (ptr = &block; ptr->k < m; ptr->k += 1) {
            Block &buddy = Buddy(*ptr);
            if (buddy.status == reserved || buddy.k != ptr->k) {
                break;
            }
            Unlink(buddy);
            if (&buddy < ptr) {
                ptr = &buddy;
            }
        }
    
        InsertAfter(sentinel[ptr->k], *ptr);
    }
    
    //------------------------------------------------------------------------------
    // Buddy
    //------------------------------------------------------------------------------
    BuddyPool::Block &BuddyPool::Buddy(Block &block) const
    {
    }
    
    //------------------------------------------------------------------------------
    // Unlink
    //------------------------------------------------------------------------------
    void BuddyPool::Unlink(Block &block)
    {
        if (block.link.next) {
            block.link.next->link.prev = block.link.prev;
        }
        if (block.link.prev) {
            block.link.prev->link.next = block.link.next;
        }
        block.link.next = block.link.prev = &block;
    }
    
    //------------------------------------------------------------------------------
    // InsertAfter
    //------------------------------------------------------------------------------
    void BuddyPool::InsertAfter(Block &src, Block &block)
    {
        block.link.next = src.link.next;
        block.link.prev = &src;
    
        if (src.link.next) {
            src.link.next->link.prev = &block;
        }
        src.link.next = &block;
    }

  2. #2
    Registered User
    Join Date
    Jul 2007
    Posts
    2

    I got the solution..

    ...for anyone who's interested:

    Code:
    //------------------------------------------------------------------------------
    // Buddy
    //------------------------------------------------------------------------------
    BuddyPool::Block &BuddyPool::Buddy(Block &block) const
    {
    	unsigned int addr = reinterpret_cast<unsigned int>(&block) + (1 << block.k);
    	return *(reinterpret_cast<Block *>(addr));
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap vs stack memory question
    By donglee in forum C++ Programming
    Replies: 4
    Last Post: 01-23-2009, 03:34 PM
  2. Pointer memory question
    By Edo in forum C++ Programming
    Replies: 5
    Last Post: 01-21-2009, 02:36 AM
  3. Memory quiz, question 2
    By pheres in forum C++ Programming
    Replies: 4
    Last Post: 06-08-2008, 05:46 AM
  4. Memory question
    By John_L in forum Tech Board
    Replies: 8
    Last Post: 06-02-2008, 10:06 PM
  5. Another Dynamic Memory Question
    By SirCrono6 in forum C++ Programming
    Replies: 6
    Last Post: 03-02-2005, 11:10 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21