Small Memory Allocation, Part 3

Introduction

This article presents some other useful memory related patterns [1]: Compaction, Reference Counting, and Garbage Collection. Reference Counting is undoubtedly the star, as this is a basic and fundamental technique in BREW. An example of a smart pointer wrapping the Reference Counting mechanism ends the article.

Compaction

Compaction is an efficient mechanism of recovering memory lost to fragmentation. As the name suggests, once fragmentation occurs space can be recovered by moving the allocated blocks of memory to recreate one contiguous block. The problem is to maintain the correctness of pointer references during this process—and the legendary extra level of indirection simplifies the implementation. The basic idea is to manipulate objects prone to fragmentation via handlers—a handler being in most cases a pointer to the real address. As usual, there is a trade off—in this case:

• Additional memory has to be allocated to keep the indirection table.
• Time performance decreases when compacting many objects, the time required being unpredictable.

Usually, a handle provides a convenient access to the original pointer:

template 
struct Handle
{
   Handle( T** p) : p_(p) {}
   T* operator ->() const
{ return *p_;)
   T& operator *() const
{ return **p_;)
   operator T*() const
{ return *p_;)
private:
T** p_;
}

An interesting approach if using STL is the use of "views" [2].

Accessing objects via direct pointers adds the potential risk of using invalid pointers. Invalidation might happen every time a compaction is triggered and pointers change their references. The usual solution involves locking objects in memory during direct access.

Because there is no native support in BREW for Compaction, all the mechanisms have to be implemented entirely by the developer.

Garbage Collection

Garbage Collection is a widely used mechanism to recycle memory, made very popular due to virtual machines such as JVM. It usually requires more resources but is more time efficient than Reference Counting and tends to be less appealing for systems, such as BREW, with limited memory. Garbage Collection is an extremely vast subject well beyond the scope of this article (see [3] for a reference and possible implementations).

Reference Counting

Reference Counting addresses the problem of discarding shared objects. A shared object is a convenient form of keeping immutable data—information is no longer duplicated, reducing memory requirements. For example:

SharedString s("Some shared data");
SharedString p = s;    //p doesn't copy data, just points to data
                       //contained in s.

Contrast this with regular string implementation, where

String p = s;
copies data in p.

If any client of shared data intends to change the common information, a good strategy to use might be copy-on-write (COW) [4].

There are obvious problems in trying to delete s (or p) in a shared design. Assuming that object A uses SharedString p, deleting SharedString s brings now mayhem in our implementation: p is silently invalidated and any attempt of using it is now futile.

Now, Reference Counting comes to the rescue. A referenced count shared object is an object keeping count of all its instances. The advantage of this strategy is that any client can discard safely its share—memory management is done globally and is transparent. Implementation is fairly trivial; objects keep an internal (might be external in some implementations) counter, incremented every time the object is copied and decremented for every deletion. Once the counter reaches zero the object is destroyed, the object is not shared any more.

But, reference count manipulation might account for up to 20% of an application's running time [1].

Reference Counting had its share of fame due to technologies such as COM [5]. Because COM largely inspired BREW implementation, both expose similar features:

• Both are interface-based
• Both are reference counted

There are a number of important differences too, stemming from the fact that COM is much larger in scope—BREW is only a "COM as a better C++" [5] implementation.

• BREW is based mainly on IBase (that offers support for reference counting). By contrast, COM has IUnknown as its foundation, adding the ubiquitous QueryInterface to reference counting. BREW has a IQueryInterface but is not consistently used. Anyway, developers are encouraged to use IQueryInterface for their own classes.
• BREW is really "COM as a better C," compared with COM, which is entirely C++ inspired. This makes its use at least awkward from the C++ user's point of view: the BREW interfaces cannot be manipulated as object handles.
• BREW is not uniform in its interface creation: Not all interfaces are obtained by using ISHELL_CreateInstance.

Let's quickly review the rules for proper AddRef and Release [5]:

1. When a non-null interface pointer is copied to a different memory location, AddRef should be called to increment the reference count.
2. Release must be called to decrement the reference count when overwriting a memory location containing a non-null interface pointer.
3. Release must be called to decrement the reference count when a non-null interface pointer goes out of scope.

It's clear that Reference Counting requires programmer discipline to correctly manipulate reference counts. That's why COM provides smart interface pointers (ATL is a more comprehensive attempt to hide the implementation details of COM, providing its own flavor of smart pointers [6]), wrapping the basic interface activity. What follows is an attempt to provide a similar one for BREW:

struct COM_Policy
{
   static bool isCOM()
   {
      return true;
   }
};

struct BREW_Policy
{
   static bool isCOM()
   {
      return false;
   }
};

template <class T, class P=BREW_Policy>
class BrewIPtr
{
public:
   BrewIPtr() : p_(0)
   {}
   explicit BrewIPtr(AEECLSID uid) : p_(0)
   {
      if (!uid)     return;
      IApplet *a = GETAPPINSTANCE();
      IShell* pIShell = ((AEEApplet*)a)->m_pIShell;
      ISHELL_CreateInstance(pIShell, uid, (void **)&p_);
   }
   BrewIPtr(T *p) : p_(p) 
   {
      if (P::isCOM()) addRef();
   }
   BrewIPtr(const BrewIPtr& bp) : p_(bp.p_)
   {
      addRef();
   }
   BrewIPtr& operator = (T *p) 
   {
      copy(p, P::isCOM()) ;
      return *this;
   }
   BrewIPtr& operator = (const BrewIPtr& bp)
   {
      copy(bp.p_);
      return *this;
   }
   void attach(T* p)
   {
      release();
      p_ = p;
   }
   T* detach()
   {
      T* p = p_;
      p_ = 0;
      return p;
   }
   operator T* () const
   {
      return p_;
   }
   ~BrewIPtr()
   {
      release();
   }
private:
   void addRef()
   {
      if (p_)  IBASE_AddRef((IBase*)p_);
   }
   void release()
   {
      if (p_)
      {
         IBASE_Release((IBase*)p_);
         p_ = 0;
      }
   }
   void copy(T *p, bool isCOM = true) 
      {
         if (p_ != p) 
      {
         attach(p);
         if (isCOM) addRef();
      }
   }
private:
   T* p_;
};

There are a couple of differences from a regular COM smart pointer (CComPtr, for example [6]):

• BREW interfaces can be created by using a constructor taking UID as the only parameters. Alternative implementations, more in the spirit of CComPtr using dedicated methods or factories, are equally possible (and marginally better if considering the additional failure support).
• BrewIPtr takes immediate ownership of raw interface pointers when used with BREW_Policy. This encourages the use of smart pointers and avoids all direct reference counting manipulation. COM_Policy allows the same behavior as a smart COM pointer (that's why the attach/detach pair).
• BREW interfaces are used in the C style, making pointer operators overloading superfluous.
• Taking into account the C implementation of BREW, there is no way to prohibit the use of AddRef or Release on a BrewIPtr. BREW_Policy makes interfaces access more uniform and doesn't encourage this kind of mistakes.

The use of BrewIPtr is illustrated in two contrasting examples, one using BREW_Policy and the other COM_Policy.

Writer writer;
   BrewIPtr<IDisplay> d(writer.getDisplay());
   BrewIPtr<IDisplay> f(AEECLSID_DISPLAY);
   f = d;
   BrewIPtr<IFileMgr> fmgr(AEECLSID_FILEMGR);
   const char fn[]="tmpf39";
   IFILEMGR_Remove(fmgr, fn);
   BrewIPtr<IFile> fl( IFILEMGR_OpenFile(fmgr, fn , _OFM_CREATE));
   if (fl)
   {
      IFILE_Write(fl, fn, sizeof(fn));
   }

The preceding code uses Brew_Policy. Here's the same code using COM_Policy:

Writer writer;
   BrewIPtr<IDisplay, COM_Policy> d(writer.getDisplay());
   BrewIPtr<IDisplay, COM_Policy> f(AEECLSID_DISPLAY);
   f = d;
   BrewIPtr<IFileMgr, COM_Policy> fmgr(AEECLSID_FILEMGR);
   const char fn[]="tmpfl9";
   IFILEMGR_Remove(fmgr, fn);
   BrewIPtr<IFile, COM_Policy> fl;
   fl.attach( IFILEMGR_OpenFile(fmgr, fn , _OFM_CREATE));
   if (fl)
   {
      IFILE_Write(fl, fn, sizeof(fn));
   }

Note how we have to attach the IFile interface in this case.

Class Writer takes a BrewIPtr<IDisplay> as a member:

class Writer
{
public:
   Writer();
   ~Writer();
   BrewIPtr<IDisplay>& getDisplay()
   {
      return m_pIDisplay;
   }
............//other member functions
private:
   BrewIPtr<IDisplay>    m_pIDisplay;    // display instance
                                         // instead of
                                         // IDisplay* m_pIDisplay;
  ..........//other members
};

References

[1] James Noble. Charles Weirr: Small Memory software - Patterns for systems with limited memory, Addison Wesley. 2001

[2] Maciej Sobczak. "STL Sequences & the View Concept," C/C++ Users Journal, April 2004.

[3] Richard Jones. Rafael Lins - Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, 1997

[4] Scott Meyers. More Effective C++. Addison Wesley, 1996

[5] Don Box. Essential COM. Addison Wesley, 1998

[6] Brent Rector, Chris Sells. ATL Internals. Addison Wesley, 1999.

Download

Download the accompanying program here (14 Kb).