Coding Standards Deprecated

Page
Test TestTestTestTestTestTestTestTestTestTestTest
Test Test Test Test Test Test
Test Test Test Test Test Test Test Test Test
Test Test Test Test Test Test
Test Test Test Test Test Test Test Test Test
Test Test Test Test Test Test

This is the top
[bottom]

  1. Yada Yada Yada
  2. /******************************************************************************/
    /*!
    \file   ObjectAllocator.cpp
    \author Alejandro Hitti
    \par    email: alejandro.hitti\@digipen.edu
    \par    DigiPen login: alejandro.hitti
    \par    Course: CS280
    \par    Assignment #1
    \date   01/23/2014
    \brief
      This is the implementation file of a simple memory manager, which includes
      three types of header blocks, padding and debug checks. It also contains
      the OAException class and 4 structs: OAStats, OAConfig, GenericObject and
      MemBlockInfo. http://alejandrohitti.com
    
      Functions include:
        - Constructor
        - Destructor
        - Allocate
        - Free
        - DumpMemoryInUse
        - ValidatePages
        - FreeEmptyPages
        - SetDebugState
        - GetFreeList
        - GetPageList
        - GetConfig
        - GetStats
    */
    /******************************************************************************/
    #include "ObjectAllocator.h"
    #include <cstring> // memset
    
    /******************************************************************************/
    /*!
      \brief
        Creates the ObjectManager per the specified values
        Throws an exception if the construction fails. (Memory allocation problem)
    
      \param ObjectSize
        Size of the actual data for each block
    
      \param config
        Config struct specifying all the characteristics of the Object Allocator
    */
    /******************************************************************************/
    ObjectAllocator::ObjectAllocator(size_t ObjectSize, const OAConfig& config) throw(OAException)
      : mFreeList(NULL), mPageList(NULL), mConfig(config)
    {
      // Initializes all variables for stats and config
      initialize(ObjectSize);
    
      // Allocates the first page
      MakePage();
    }
    
    /******************************************************************************/
    /*!
      \brief
        Destroys the ObjectManager (never throws)
    */
    /******************************************************************************/
    ObjectAllocator::~ObjectAllocator() throw()
    {
      GenericObject* temp;
    
      // While there are pages allocated
      while (mPageList)
      {
        // Pop Front of PageList
        temp = mPageList->Next;
        delete [] reinterpret_cast<char*>(mPageList);
        mPageList = temp;
      }
    }
    
    /******************************************************************************/
    /*!
      \brief
        Take an object from the free list and give it to the client (simulates new)
        Throws an exception if the object can't be allocated. (Memory allocation problem)
    
      \param label
        Character pointer to the user defined data for External HB
    
      \return
        Pointer to the allocated memory block
    */
    /******************************************************************************/
    void *ObjectAllocator::Allocate(const char *label) throw(OAException)
    {
      // Wrapper around new
      if (mConfig.UseCPPMemManager_)
      {
        char* newObject;
    
        try
        {
          newObject = new char[mStats.ObjectSize_];
        }
    
        catch (std::bad_alloc)
        {
          throw OAException(OAException::E_NO_MEMORY, "System out of memory.");
        }
    
        // Update stats
        ++mStats.Allocations_;
        ++mStats.ObjectsInUse_;
        --mStats.FreeObjects_;
    
        // Check for most number of objects
        if (mStats.ObjectsInUse_ > mStats.MostObjects_)
          mStats.MostObjects_ = mStats.ObjectsInUse_;
    
        return reinterpret_cast<void*>(newObject);
      }
    
      // If all pages are full
      if (mFreeList == NULL && mStats.PagesInUse_ < mConfig.MaxPages_)
        MakePage();
    
      // Reached max number of pages
      else if (mFreeList == NULL && mStats.PagesInUse_ >= mConfig.MaxPages_)
        throw OAException(OAException::E_NO_PAGES, "No more pages can be allocated. Max number of pages reached.");
    
      // Give the first element of the FreeList to the user
      GenericObject* newObject = mFreeList;
      mFreeList = mFreeList->Next;           // Move ahead on the list
      std::memset(newObject, ALLOCATED_PATTERN, mStats.ObjectSize_);
    
      // Update stats
      ++mStats.Allocations_;
      ++mStats.ObjectsInUse_;
      --mStats.FreeObjects_;
    
      // Check for most number of objects
      if (mStats.ObjectsInUse_ > mStats.MostObjects_)
        mStats.MostObjects_ = mStats.ObjectsInUse_;
    
    
      // Update Header Blocks
      char *header = reinterpret_cast<char*>(newObject) -
                     (mConfig.PadBytes_ + mConfig.HBlockInfo_.size_);
    
      // Every time you see pointer arithmetic from here on, it's jumping over
      // the previously updated variable
      switch (mConfig.HBlockInfo_.type_)
      {
        case OAConfig::hbNone :
          break;
    
        case OAConfig::hbBasic :
          (*reinterpret_cast<int*>(header)) = mStats.Allocations_; // Set number of allocs
          header += sizeof(int);
          *header |= 1; // Turn last bit to 1
          break;
    
        case OAConfig::hbExtended :
          header += mConfig.HBlockInfo_.additional_;
          ++(*reinterpret_cast<short*>(header)); // Increase number of uses
          header += sizeof(short);
          (*reinterpret_cast<int*>(header)) = mStats.Allocations_; // Set number of allocs
          header += sizeof(int);
          *header |= 1; // Turn last bit to 1
          break;
    
        case OAConfig::hbExternal :
          MemBlockInfo** mem = reinterpret_cast<MemBlockInfo**>(header);
          *mem = new MemBlockInfo();
          (*mem)->alloc_num = mStats.Allocations_; // Set number of allocs
          (*mem)->in_use = true;                   // Set in use flag
          if (label)  // If user provided a label
          {
            (*mem)->label = new char[strlen(label) + 1]; // Dynamically allocate it
            strcpy((*mem)->label, label);
          }
          else
            (*mem)->label = NULL;
          break;
      }
    
      return newObject;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Returns an object to the free list for the client (simulates delete)
        Throws an exception if the the object can't be freed. (Invalid object)
    
      \param Object
        Pointer to the object to free
    */
    /******************************************************************************/
    void ObjectAllocator::Free(void *Object) throw(OAException)
    {
      // Wrapper around delete
      if (mConfig.UseCPPMemManager_)
      {
        // Update stats
        ++mStats.FreeObjects_;
        ++mStats.Deallocations_;
        --mStats.ObjectsInUse_;
    
        delete [] reinterpret_cast<char*>(Object);
        return;
      }
      
      // Checks for OutOfBounds and DoubleFree
      if (mConfig.DebugOn_)
        DebugExceptions(Object);
    
      // Check for corruption
      if (CheckCorruption(Object))
        throw OAException(OAException::E_CORRUPTED_BLOCK, "Memory block is corrupted.");
    
      // Put the new block in the front of the FreeList
      GenericObject *temp = reinterpret_cast<GenericObject*>(Object);
    
      // Set the free pattern
      if (mConfig.DebugOn_)
        std::memset(temp, FREED_PATTERN, mStats.ObjectSize_);
    
      temp->Next = mFreeList;
      mFreeList = temp;
    
      // Update stats
      ++mStats.FreeObjects_;
      ++mStats.Deallocations_;
      --mStats.ObjectsInUse_;
    
      // Update Header Blocks
      char *header = reinterpret_cast<char*>(Object) - 
                     (mConfig.PadBytes_ + mConfig.HBlockInfo_.size_);
    
      // Every time you see pointer arithmetic from here on, it's jumping over
      // the previously updated variable
      switch (mConfig.HBlockInfo_.type_)
      {
        case OAConfig::hbNone :
          break;
    
        case OAConfig::hbBasic :
          (*reinterpret_cast<int*>(header)) = 0; // Number of allocations
          header += sizeof(unsigned);
          *header &= 0;                          // In use flag to false
          break;
    
        case OAConfig::hbExtended :
          header += mConfig.HBlockInfo_.additional_; // User defined memory
          header += sizeof(short);
          (*reinterpret_cast<int*>(header)) = 0;     // Number of allocations
          header += sizeof(int);
          *header &= 0;                              // In use flag to false
          break;
    
        case OAConfig::hbExternal :
          MemBlockInfo** mem = reinterpret_cast<MemBlockInfo**>(header);
          (*mem)->alloc_num = 0;        // Number of allocations
          (*mem)->in_use = false;       // In use flag to false
          if ((*mem)->label)            // Check if label was dynamically allocated
            delete [] (*mem)->label;    // Delete it
          delete (*mem);                // Delete the external header block
          *mem = NULL;
          break;
      }
    }
    
    /******************************************************************************/
    /*!
      \brief
        Calls the callback fn for each block still in use
    
      \param fn
        Function pointer to the function that will be called if there is a memory
        block that is still in use
    
      \return
        Number of blocks still in use when freeing the OA
    */
    /******************************************************************************/
    unsigned ObjectAllocator::DumpMemoryInUse(DUMPCALLBACK fn) const
    {
      GenericObject *pagePointer = mPageList;
      unsigned inUse = 0;
    
      // Checks every page
      while(pagePointer)
      {
        // Checks every object in a page
        for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
        {
              char *pos = reinterpret_cast<char*>(pagePointer) + mOffset + i * mSkipSize; // Position
    
              if (CheckInUse(pos)) // If the mem block is in use
              {
                fn(pos, mStats.ObjectSize_); // Callback function
                ++inUse;
              }
        }
    
        pagePointer = pagePointer->Next;
      }
    
      return inUse;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Calls the callback fn for each block that is potentially corrupted
    
      \param fn
        Function pointer to the function that will be called if there is memory
        corruption in a memory block
    
      \return
        Number of corruptions found. Returns 0 if debug is off or if padding is 0
    */
    /******************************************************************************/
    unsigned ObjectAllocator::ValidatePages(VALIDATECALLBACK fn) const
    {
      // Return if debug is off or if the padding size is zero
      if (!mConfig.DebugOn_ || (mConfig.PadBytes_ == 0))
        return 0;
    
      GenericObject *pagePointer = mPageList;
      unsigned corruptions = 0;
    
      // Checks every page
      while(pagePointer)
      {
        // Checks every object in a page
        for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
        {
              char *pos = reinterpret_cast<char*>(pagePointer) + mOffset + i * mSkipSize; // Position
    
              if (CheckCorruption(reinterpret_cast<void*>(pos))) // If the mem block is corrupted
              {
                fn(pos, mStats.ObjectSize_); // Callback function
                ++corruptions;
              }
        }
    
        pagePointer = pagePointer->Next;
      }
    
      return corruptions;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Frees all empty pages (extra credit)
    
      \return
        Number of pages freed.
    */
    /******************************************************************************/
    unsigned ObjectAllocator::FreeEmptyPages(void)
    {
      // Pointers to walk the pagelist and freelist
      GenericObject *pagePointer = mPageList;
      GenericObject *prevPage    = NULL;
      GenericObject *listPointer;
      GenericObject *nextNode;
      GenericObject *prevList    = mFreeList;
      GenericObject *head        = pagePointer;
    
      // Counter of pages freed
      unsigned pagesFreed = 0;
    
      // Walks pages
      while(pagePointer)
      {
        bool isEmpty = true; // Initial value
        char *pos = (reinterpret_cast<char*>(pagePointer) + mOffset); // Position/object
    
        // Walks each object in a page
        for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
        {
              // If one object is in use, the page isn't empty
              if (CheckInUse(reinterpret_cast<void*>(pos)))
              {
                isEmpty = false;
                break;
              }
              
              // Prevents past-one check
              if (i != mConfig.ObjectsPerPage_ - 1)
                pos += mSkipSize;
        }
    
        // If the current page is empty
        if (isEmpty)
        {
          // Update stats
          mStats.FreeObjects_ -= mConfig.ObjectsPerPage_;
          --mStats.PagesInUse_;
          ++pagesFreed;
    
          // Update the freelist pointer
          listPointer = mFreeList;
    
          // Remove items from the freelist that are in the empty page
          // While inside the empty page
          while (listPointer > pagePointer && 
          (reinterpret_cast<char*>(listPointer) < (reinterpret_cast<char*>(pagePointer) + mStats.PageSize_)))
          {
            listPointer = listPointer->Next;
            prevList    = listPointer;
          }
    
          while (listPointer)
          {
            nextNode = listPointer->Next;
    
            while (nextNode > pagePointer &&
            (reinterpret_cast<char*>(nextNode) < (reinterpret_cast<char*>(pagePointer) + mStats.PageSize_)))
              nextNode = nextNode->Next;
    
            listPointer->Next = nextNode;
            listPointer = listPointer->Next;
          }
    
          // Set new head for the freelist
          mFreeList = prevList;
    
          // Delete the page if it's the first one
          if (prevPage == NULL)
          {
            // Rearrange pointers
            GenericObject* temp = pagePointer->Next;
            delete [] reinterpret_cast<char*>(pagePointer);
            pagePointer = temp;
            head = pagePointer;
            mPageList = head;
          }
    
          // Not the first page
          else
          {
            // Rearrange pointers
            prevPage->Next = pagePointer->Next;
            delete [] reinterpret_cast<char*>(pagePointer);
            pagePointer = prevPage->Next;
            mPageList = head;
          }
        }
    
        else
        {
          prevPage = pagePointer;
          pagePointer = pagePointer->Next;
        }
      }
    
      return pagesFreed;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Returns true if FreeEmptyPages and alignments are implemented
    
      \return
        True or False
    */
    /******************************************************************************/
    bool ObjectAllocator::ImplementedExtraCredit(void)
    {
      return false;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Testing/Debugging/Statistic methods
    
      \param State
        Changes the state of the DebugOn flag.
        true=enable, false=disable
    */
    /******************************************************************************/
    void ObjectAllocator::SetDebugState(bool State)
    {
      mConfig.DebugOn_ = State;
    } 
    
    /******************************************************************************/
    /*!
      \brief
        Returns a pointer to the internal free list
    
      \return 
        Pointer to the free list
    */
    /******************************************************************************/
    const void *ObjectAllocator::GetFreeList(void) const
    {
      return mFreeList;
    } 
    
    /******************************************************************************/
    /*!
      \brief
        Returns a pointer to the internal page list
    
      \return 
        Pointer to the page list
    */
    /******************************************************************************/
    const void *ObjectAllocator::GetPageList(void) const
    {
      return mPageList;
    } 
    
    /******************************************************************************/
    /*!
      \brief
        Returns the configuration parameters
    
      \return 
        Configuration struct
    */
    /******************************************************************************/
    OAConfig ObjectAllocator::GetConfig(void) const
    {
      return mConfig;
    } 
    
    /******************************************************************************/
    /*!
      \brief
        Returns the statistics for the allocator
    
      \return 
        Stats struct
    */
    /******************************************************************************/
    OAStats ObjectAllocator::GetStats(void) const
    {
      return mStats;
    } 
    
    /******************************************************************************/
    /*!
      \brief
        Helper Function.
        Creates a page, adds it to the page list and divides it into blocks that
        are also added to the free list.
    */
    /******************************************************************************/
    void ObjectAllocator::MakePage() throw (OAException)
    {
      char *heap;
    
      // Dynamically allocate the page
      try
      {
        heap = new char[mStats.PageSize_];
      }
    
      catch (std::bad_alloc)
      {
        throw OAException(OAException::E_NO_MEMORY, "System out of memory.");
      }
    
      // Set all bytes to AA
      if (mConfig.DebugOn_)
        std::memset(heap, UNALLOCATED_PATTERN, mStats.PageSize_);
    
      // Push Front of PageList
      GenericObject* temp = mPageList;
      mPageList = reinterpret_cast<GenericObject*>(heap);
      mPageList->Next = temp;
    
      // Left Alignment
      if (mConfig.DebugOn_)
        std::memset(heap + sizeof(void*), ALIGN_PATTERN, mConfig.LeftAlignSize_);
    
      // Creates a linked list from the allocated block of memory
      for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
      {
        char *pos = heap + mOffset + i * mSkipSize; // Position
    
        // Push front of FreeList
        temp = mFreeList;
        mFreeList = reinterpret_cast<GenericObject*>(pos);
        mFreeList->Next = temp;
        
        if (mConfig.DebugOn_)
        {
          // Padding
          std::memset(pos - mConfig.PadBytes_,  PAD_PATTERN, mConfig.PadBytes_);
          std::memset(pos + mStats.ObjectSize_, PAD_PATTERN, mConfig.PadBytes_);
    
          // Header Block
          std::memset(pos - mConfig.PadBytes_ - mConfig.HBlockInfo_.size_, 0, mConfig.HBlockInfo_.size_);
    
          // Inter Alignment
          if (i < mConfig.ObjectsPerPage_ - 1)
            std::memset(pos + mConfig.PadBytes_ + mStats.ObjectSize_, ALIGN_PATTERN, mConfig.InterAlignSize_);
        }
      }
    
      // Update Stats
      ++mStats.PagesInUse_;
      mStats.FreeObjects_ = mConfig.ObjectsPerPage_;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Helper Function.
        Runs the checks for double free and out of bounds and throws exceptions
        if required.
    
      \param Object
        Pointer to the object to check.
    */
    /******************************************************************************/
    void ObjectAllocator::DebugExceptions(void *Object) throw (OAException)
    {
      GenericObject* temp = mPageList;
      GenericObject* tObject = reinterpret_cast<GenericObject*>(Object);
    
      // Walk the PageList
      while (temp)
      {
        // If the object is out of bounds of the current page
        if (tObject < temp || tObject > (temp + mStats.PageSize_))
        {
          // If this is the last page, throw
          if (!temp->Next)
            throw OAException(OAException::E_BAD_BOUNDARY, "The block of memory provided is out of bounds.");
    
          // If there are more pages, keep walking the PageList
          else
            temp = temp->Next;
        }
        
        // Inside of page bounds
        else
        {
          // Calculates the distance from the start of the page minus the PageList Pointer
          long int dist = reinterpret_cast<char*>(Object) - 
                          reinterpret_cast<char*>(temp) - mOffset;
    
          // If distance if positive and the distance mod the size of the object 
          if ((dist % mSkipSize) == 0)
            break;
          else
            throw OAException(OAException::E_BAD_BOUNDARY, "The block of memory provided is not a valid one.");
        }
      }
    
      // Check for Double free (optimized)
      if (*(reinterpret_cast<char*>(Object) + sizeof(void*)) == static_cast<char>(FREED_PATTERN))
        throw OAException(OAException::E_MULTIPLE_FREE, "This block of memory is already freed.");
    
      //// Checks for Double free (Walks the whole FreeList)
      //temp = mFreeList;
    
      //while (temp)
      //{
      //  if (reinterpret_cast<GenericObject*>(Object) == temp)
      //    throw OAException(OAException::E_MULTIPLE_FREE, "This block of memory is already freed.");
    
      //  temp = temp->Next;
      //}
    }
    
    /******************************************************************************/
    /*!
      \brief
        Helper Function.
        Checks if the memory block at the given address is corrupter by checking
        the pad bytes.
    
      \param Object
        Pointer to the object to check.
    
      \return
        True if block is corurpted
        False if it is not corrupted
    */
    /******************************************************************************/
    bool ObjectAllocator::CheckCorruption(void* Object) const
    {
      // Check all padbytes
      for (unsigned i = 0; i < mConfig.PadBytes_; ++i)
      {
        // If padbytes where modified, return true
        if  (*(reinterpret_cast<char*>(Object) - i - sizeof(char)) != static_cast<char>(PAD_PATTERN) ||
            (*(reinterpret_cast<char*>(Object) + mStats.ObjectSize_ + i)) != static_cast<char>(PAD_PATTERN))
          return true;
      }
    
      return false;
    }
    
    /******************************************************************************/
    /*!
      \brief
        Helper Function.
        Checks if the memory block at the given address is in use. Different
        checks get run depending on the type of header block being used.
    
      \param Object
        Pointer to the object to check.
    
      \return
        True if block is in use
        False if it is not in use
    */
    /******************************************************************************/
    bool ObjectAllocator::CheckInUse(void *Object) const
    {
      unsigned type = mConfig.HBlockInfo_.type_;
    
      // If header is basic or extended, you check the "in use" flag
      if (type == OAConfig::hbBasic || 
          type == OAConfig::hbExtended)
      {
        if (*(reinterpret_cast<char*>(Object) - sizeof(char) - mConfig.PadBytes_) == 1)
          return true;
        else
          return false;
      }
    
      // If header is external, check if the MemBlockInfo struct exists
      else if (type == OAConfig::hbExternal)
      {
        char *temp = reinterpret_cast<char*>(Object) - mConfig.HBlockInfo_.size_ - mConfig.PadBytes_;
        MemBlockInfo** mem = reinterpret_cast<MemBlockInfo**>(temp);
    
        if ((*mem))
          return true;
        else
          return false;
      }
    
      // If no header blocks are being used
      else
      {
        GenericObject* listPointer = mFreeList;
    
        // Walk the free list
        while (listPointer)
        {
          // And compare it to the object. Return true if the object is on the free list
          if (listPointer == Object)
            return true;
    
          listPointer = listPointer->Next;
        }
    
        // False otherwise
        return false;
      }
    }
    
    /******************************************************************************/
    /*!
      \brief
        Helper Function.
        Initializes all the varibales for mConfig and mStats at the creation of
        the Object Allocator
    
      \param ObjectSize
        Size of the objects to be allocated
    */
    /******************************************************************************/
    void ObjectAllocator::Initialize(size_t ObjectSize)
    {
      // Set values for Stats variables
      mStats.ObjectSize_    = ObjectSize;
    
      // Initialize to Zero
      mStats.Allocations_   = 0;
      mStats.Deallocations_ = 0;
      mStats.FreeObjects_   = 0;
      mStats.MostObjects_   = 0;
      mStats.ObjectsInUse_  = 0;
      mStats.PagesInUse_    = 0;
    
      // Calculate skip size
      mSkipSize = mStats.ObjectSize_         + // Objects
                  2 * mConfig.PadBytes_      + // Padding
                  mConfig.HBlockInfo_.size_;   // Header Block
    
      // Initial mOffset
      mOffset = sizeof(void*)             + // PageList Pointer
                mConfig.PadBytes_         + // Padding
                mConfig.HBlockInfo_.size_;  // Header Block
    
      if (mConfig.Alignment_ > 1)
      {
        // Alignment
        mConfig.LeftAlignSize_  = static_cast<unsigned>(mConfig.Alignment_ - (mOffset % mConfig.Alignment_));
        mConfig.InterAlignSize_ = static_cast<unsigned>(mConfig.Alignment_ - (mSkipSize % mConfig.Alignment_));
    
        // Update offsets
        mOffset   += mConfig.LeftAlignSize_;
        mSkipSize += mConfig.InterAlignSize_;
      }
    
      // Update Page size
      mStats.PageSize_ = sizeof(void*)             +  // PageList pointer
                         mConfig.LeftAlignSize_    -  // Initial Alignment
                         mConfig.InterAlignSize_   +  // Minus the last alignment (not set)
                         mConfig.ObjectsPerPage_   *  // This multiplies everything below
                        (mStats.ObjectSize_        +  // Objects
                        (mConfig.PadBytes_ * 2)    +  // Padding(x2) (before and after)
                         mConfig.HBlockInfo_.size_ +  // Header Blocks
                         mConfig.InterAlignSize_  );  // Inter Alignment
    }
    

[top]

Advertisements

Share your thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s