December 19, 2014
Hot Topics:

Small Memory Allocation-Part 2

  • March 9, 2004
  • By Radu Braniste
  • Send Email »
  • More Articles »

Introduction

Last time [1], the reader was introduced to the memory fragmentation problem in the more general perspective of the small memory allocation subject. Now, we'll shift our focus to memory deallocation and memory exhaustion, presenting useful techniques such as smart pointers [2, 3, 5]. Examples of POD and non-POD smart pointers are enclosed.

Memory Exhaustion

Because memory is a scarce resource in BREW, you can easily end up in situations when an allocation fails, despite all attempts to deal with MEMORY FRAGMENTATION [1]. What's the best strategy to follow in this case? First of all, the program has to be "rolled back" in a safe state, releasing all the resources linked to the failure. Once at this point, it should continue in a "degraded mode"—and what this state means is application dependant: Less important resources might be released, the user might be warned and asked to quit the application, cached values used instead of real ones, and so forth. An interesting technique is the so-called RAINY DAY FUND—basically pre-allocate memory to be used in exceptional situations. For example, raising an exception and displaying a warning are actions necessitating memory that might be unavailable otherwise.

Safely releasing resources is our next topic.

Memory Deallocation

Now is time to introduce smart pointers. Usually, memory allocation/deallocation is accompanied by a plethora of possible problems:

  • Uninitialized memory
  • Memory leaks
  • Dangling pointers

Smart pointers might provide a possible cure. They wrap pointers and behave like pointers (expose the same interface) but provide:

  • Automatic initialization via constructors
  • Automatic destruction via the RAII idiom [3]
  • Different strategies to fight the "dangling pointer" problem

Of course, one size doesn't fit all and there is a variety of small pointers, better adapted to a certain situation than the others. A notorious example is auto_ptr, well suited for local variables but not for STL containers [4].

As a more BREW-specific example, an AutoPtr and an AutoPtrPOD class are introduced, both exhibiting the following characteristics:

  • Support allocators directly—meaning that they automatically manipulate pointers retrieved from allocators.
  • Intended to be used for POD and non-POD wrapping. AutoPtrPOD is an autonomous class intended for programmers considering using "C++ as a better C" [3] to improve the efficiency and the exception safety of their code.
  • Both AutoPtr and AutoPtrPOD have direct support for arrays.
  • There are no assignment operator and copy constructor provided, making them more suitable for local variables manipulation.
template <class T, class A=Allocator>
class AutoPtr
{
public:
   explicit AutoPtr(T * p , A* allocator = 0): owns_( p != 0 ),
      allocator_(allocator),  ptr_( p ) , sz_(0)
   {  }
   explicit AutoPtr(size_t sz, A* allocator=0): owns_(false),
      allocator_(allocator),  ptr_( 0 ) , sz_(sz)
   {
      if (allocator_)
         {
            ptr_ = (T*)allocator_->allocate(sizeof(T) * sz_);
         if (ptr_)
         {
            for (int i = 0 ;i < sz_; ++i)
               new (&ptr_[i]) T;
         }
         }
      else
         ptr_ = new T[sz_];
      owns_ = (ptr_!=0);
   }
   ~AutoPtr()
   {
      kill();
   }
   T& operator*()
   {
      return *ptr_;
   }
   T* operator->()
   {
      return ptr_;
   }
   T* get()
   {
      return ptr_;
   }
   bool operator !() const
   {
      return ptr_!=0;
   }
   T& operator[](size_t i)
   {
      if (sz_)
         return ptr_[i];
      else
         return *ptr_;
   }
   T* release()
   {
      owns_ = false;
      return ptr_;
   }
   AutoPtr &
      set (T * inPtr, size_t sz = 0)
   {
      if (ptr_ != inPtr)
      {
         kill();
         owns_ = (inPtr != 0);
         sz_ = sz;
         ptr_ = inPtr;
      }
      return *this;
   }
private:
   void kill()
   {
      if (owns_)
      {
         if (allocator_)
         {
            if (allocator_->isInPool(ptr_))
            {
               if (sz_)
               {
                  for (size_t h=0; h < sz_; ++h)
                     ptr_[h].~T();
               }
               else
               {
                  ptr_->~T();
               }
               allocator_->deallocate(ptr_);
            }
            else
            {
               killPD();
            }
         }
         else
         {
            killPD();
         }
      }
      owns_ = false;
      sz_ = 0;
      ptr_ = 0;
   }
   void killPD()
   {
      if (sz_)
         delete[] ptr_;
      else
         delete ptr_;
   }
private:
   AutoPtr(const AutoPtr<T,A>& rhs) ;
   const AutoPtr& operator=(const AutoPtr<T,A>&);
private:
   bool owns_;
   A* allocator_;
   T *    ptr_;
   size_t sz_;
};

AutoPtr can be used with an existing allocator, such as:

{
Allocator* a = CPPApp::getAllocator<Allocator>();
        AutoPtr<AA> b(2, a);            // array of 2 AAs
        AutoPtr<AA> c(new(a) AA, a);    // one AA
        AutoPtr<AA> d (1000, a);        // 1000 AAs
        AutoPtr<Test> t (new(a) Test(10), a);
          //a new Test using a non-default constructor
        int val = t->getValueAt(7);
}

or without an allocator:

{
        AutoPtr<AA> b(2);           // array of 2 AAs
        AutoPtr<AA> c(new AA);      // one AA
        AutoPtr<AA> d (1000, a);    // 1000 AAs
        AutoPtr<Test> t (new Test(10));
          //a new Test using a non-default constructor
        int val = t->getValueAt(7);
}

Once exiting, the enclosing scope a, b, c, d, and t are automatically deallocated.

One word about CPPApp::getAllocator<Allocator>():

As mentioned before [1], a singleton can be implemented in BREW only by using CPPApp as a context. But instead of passing a reference to CPPApp all the time to all the interested parties, another technique is to use GETAPPINSTANCE(). An example can be found in appclasses implementation [1]. GETAPPINSTANCE() is the only way to get a static reference of the applet and can be used like this:

template <class T>
   static T* getAllocator()
   {
      CPPApp* p = (CPPApp*)GETAPPINSTANCE();
      if (!p->al_)
         p->al_ = new T;
      return p->al_;
   }

al_ is the allocator, a private member of CPPApp, that can be used now in a static context. A more generic approach, allowing families of singletons and based on specialization, is possible too:

      ...//other members
public:
   template <class T>
   static T* getSingleton()
   {
      CPPApp* p = (CPPApp*)GETAPPINSTANCE();
      return p->getInstance();
   }
private:
   template <class T>
   T* getInstance()
   {
      return 0;
   }
   Allocator* getInstance()
   {
      if (!al_)
         al_ = new Allocator;
      return al_;
   }
      OtherSingleton* getInstance()
   {
      ...
      return anInstanceOfAnotherSingleton;
   }
...

AutoPtrPOD is almost similarly implemented:

template <class T, class A=Allocator>
class AutoPtrPOD
{
   enum {IS_POD=sizeof(POD_DISCRIMINANT<T>)};
public:
   explicit AutoPtrPOD(size_t sz, A* allocator=0): owns_(false),
   allocator_(allocator), ptr_(0)
   {
      if (allocator_)
         ptr_ =  static_cast<T*>(allocator_->allocate
                                 (sz*sizeof(T)));
      else
         ptr_ = static_cast<T*>(MALLOC(sz*sizeof(T)));
      owns_ = (ptr_!=0);
   }
   explicit AutoPtrPOD(T * p) : owns_( p != 0 ),
      allocator_(0), ptr_(p)
   {  }
   explicit AutoPtrPOD(void * p) : owns_( p != 0 ),
      allocator_(0), ptr_(static_cast<T*>(p))
   {  }
... // other members
};

Of course, AutoPtrPOD uses MALLOC and FREE, somehow simplifying the internal management of resources. One notable feature is how AutoPtrPOD achieves compile time safeness:

AutoPtrPOD<AA> c (100, a);    //fails - AA is non-POD
AutoPtrPOD contains the following enumeration:
enum {IS_POD=sizeof(POD_DISCRIMINANT<T>)};

where POD_DISCRIMINANT is a union:

template <class K>
union POD_DISCRIMINANT
{
   K t;
   int i;
};

Because a union cannot contain a class [3], sizeof(POD_DISCRIMINANT<T>) fails at compile time. Otherwise, AutoPtrPOD can be used like this:

AutoPtrPOD<char> c (100, a );    // char[100]
   if (c)
   {
   STRCPY(c,"A VERY LONG STRING ");
   char ch  = c[5];
   }
AutoPtrPOD<TST> t (1, a );       // TST* t using allocator a

Final Remarks

Placement operator new[], even if defined in [1], is not used. The reason is that C++ compilers add size information, confusing the allocator. That's why AutoPtr uses the following sequence:

ptr_ = (T*)allocator_->allocate(sizeof(T) * sz_);
   if (ptr_)
   {
      for (int i = 0 ;i < sz_; ++i)
         new (&ptr_[i]) T;
   }

instead of:

ptr_ = new(allocator_) T[sz_];

Allocators have to guarantee that all the returned pointers are properly aligned, meaning that, if necessary, extra padding has to be added and/or CHUNK_SZ has to be properly adjusted. BrewAllocator takes an extra parameter in the template list, to make small allocators easy to implement:

template <typename T, T CHUNKS , T CHUNK_SZ = 4,
size_t POOL_SIZE = CHUNKS*CHUNK_SZ>
BrewAllocator;
typedef BrewAllocator<unsigned char, 128> Allocator;

What's Next?

In the next and last installment dedicated to memory, we will discuss about REFRENCE COUNTING and COMPACTION and present a reference-counted smart pointer wrapping BREW interfaces. A comparison of some of the mentioned techniques will be provided too.

Downloads

Download the accompanying code here.

References






Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Rocket Fuel