Software developing>Essay>1

Share things about Robot Making and Software Deveoping 

[English][Chinese][Japanese]

[Robot Making] [Software developing] [Squeak] [Beans] [Home]

 Managed Resource Operation

Liu Xinyu
 
Dec. 2005

 

Most of C++ developers take great care of memory operation, yes, it is very easy to manipulate memories (even raw memories), however, it is also very easy to meet troubles.

There are less and less individual developer heroes in recent decades. because most projects need teamwork. the cooperated team, just like a huge machine, every member became a parts. Some team created their own discipline to normalize memory operations. those discipline can be generalized as the following 2 main ways:

  1. A global heap class to monitor, manage, and collect resources;

  2. 2 steps construction and clean stack. 

 

For the 1st methods, it is somewhat like the GC in Java. In most cases, the problems occur in release stage, but not allocat stage, for instance:

 

      MyClass* ptr=new MyClass();

     MyClass foo;

     ptr=&foo; //the resource pointed by ptr can never be released;

     

      MyClass* ptr1=new MyClass();

     MyClass* ptr2=ptr1;

    

     //

     // other process...

     //

     delete ptr1;

    

     //

     // other process...

     //

     delete ptr2;  //release conflict.

 

Considering the above cases, some team decided not to let the developers release resource by themselves, they introduced a mechanism. there are often 2 facilities in this mechanism:

  1. A HeapBuffer, this is a common heap area, all developers will allocate resources from it;

  2. A HeapBufferObject, it is a base class, all the user's class will be derived from it.

 

The program used these facilities are written like the following:

 

class MyClass : public HeapBufferObject

{

     //...

};

 

MyClass* ptr = new (HeapBuffer) MyClass;

 

Here is a special usage named as "placement new", which can be found in "Effective C++" by Scott Meyer in 1998[1].

 

A programmer only needs to do 2 works: 1st, all the class he declared must derived from HeapBufferObject; 2nd, The object should be initialized on the HeapBuffer. After these 2 jobs, the programmer can either delete it or let it be. the object will finally be released anyway.

 

Why does the method work? 1st, let us look into HeapBuffer. In normal case, when the programmer create an object by using "new" operator, the object is allocated in heap, which is maintained by operating system. The system prepare memory address space for each process. The heap gives too much freedom to the programmer. but nobody can control or monitor the heap manually except the OS its self.

 

The idea behind the HeapBuffer is that, the HeapBuffer allocates a certain areas from the heap, since this allocated memory are owned by the HeapBuffer, it can monitor it until release time. When a user tries allocation on the zone, it will record it. if the user release the memory later, this record will be removed. after all the program finished, the HeapBuffer will iterate the records and free all the unreleased items.

 

The final release code looks like the following:

 

//First allocate 1M memory

     void* HeapBuffer = std::malloc(1024);

 

     //The programmer "borrow" memory from the HeapBuffer

     MyClass* ptr = new (HeapBuffer) MyClass;

     //...

 

     //Final release

     free(HeapBuffer);

 

The next question is what will the HeapBufferObject do? Why we need this Base class? It is because some concrete class will do its unique works during construction & destruction. for example:

 

//An editor class

class Editor{

public:

     Editor(){

          _file.open(); //Open a file for recording

     }

     ~Editor(){

          _file.close(); //Close the file for saving

     }

private:

     File _file;   //a file to record the contents

};

 

//A chat tools

class Chat{

public:

     Chat(){

          _network.connect(); //connect to server

     }

     ~Potato(){

          _network.close();  //disconnect from the server

     }

private:

     ChatServer _network;     //the network facility

};

 

It can be seen that, not all the resources are memories, which can be stored in HeapBuffer. If the program just only free memories, the opened file, connected networks will not be finalized  properly.

 

The solution is providing a base class, HeapZongObject,it contains a virtual destructor (it must be virtual, refier to Scott Meyer's Effective C++ item 14). The content inside HeapBuffer is not simple a buffer of byte, but a series of HeapBufferObject.

 

Therefore, when the program closed, The HeapBufferObjects will be released one by one. Since every pointer to HeapZongObject is in fact a Up-cast concrete class object, their unique destructor will be invoked, which will release all the resources they allocated.

 

Here, is a sample implementation, For simplification, multi-thread issue isn't considered.

 

First is the declaration of HeapBufferObject, We renamed it as gc_obj

 

class gc_obj{

public:

     gc_obj():_info("noname"){ cout<<_info<<endl;}

     gc_obj(string objName):_info(objName){ cout<<_info<<endl;}

     virtual ~gc_obj(){}

 

     static void* operator new(size_t size);

     static void* operator new[](size_t size);

     static void  operator delete(void* p);

     static void  operator delete[](void*p);

private:

     string _info;

};

 

The means of gc obj is that, it can be think a garbage collector (which has no complicated strategy, it just free all things at last). We also change the name of HeapBuffer to gc. Here is a small trick, We overwrite the new operator, so the user needn't have to use the placement new if he let his class inherit from gc_obj.

 

However, a new problem occurs here, because the user may allocate array as:

Foo* p3 = new Foo[5];

 

But the thing gc recorded is just a pointer to gc_obj. The gc has no knowledge of if it is a single object pointer or an array pointer, so it doesn't know which operator should be used, delete or delete[].

 

The solution is an extra structure, a chunk, it contains 2 things, a void* pointer and a array flag.

 

struct chunk{

    chunk(void* p, bool isArray=false): ptr(p), isArray(isArray){}

    chunk(const chunk& v):ptr(v.ptr), isArray(v.isArray){}

    chunk& operator = (const chunk& v){

          ptr = v.ptr;  isArray = v.isArray;

          return *this;

     }

 

     const bool operator == (const chunk& v){ return ptr == v.ptr; }

 

     void* ptr;

     bool  isArray;

};

 

Then the gc_obj derived class will use the following 2 methods to initialize.

 

void* gc_obj::operator new(size_t size){

     return gc::instance().alloc(size);

}

 

void* gc_obj::operator new[](size_t size){

     return gc::instance().alloc(size, true);

}

 

Where the 1st method is for single object allocation, while the 2nd is for array. each implementation will invoke a singleton instance of gc class (please refer to [1][2] for the concept of singleton). it will register all allocations,

call the new or new[] and set the array flag in chunk.

 

When the user delete a pointer of gc_obj, the following 2 methods will be called.

 

void  gc_obj::operator delete(void* p) {

     gc::instance().free(p);

}

 

void  gc_obj::operator delete[](void* p) {

     gc::instance().free(p, true);

}

 

When deleting, the array flag will also pass to gc. the implementation of gc is as the follwing:

 

class gc{

private:

     gc(){}

     gc(const gc&);

     gc& operator = (const gc&);

 

     list<chunk> mem_list;

public:

     static gc& instance(){

          static gc inst;

          return inst;

     }

 

     ~gc();

 

     void* alloc(size_t size, bool isArray = false){

          gc_obj* p = (gc_obj*) (isArray?

                               ::operator new[](size) :

                               ::operator new(size));

          mem_list.push_back(chunk(p, isArray));

          cout<<"\talloc by gc at: "<<hex<<p<<dec<<" for ";

          return p;

     }

 

     void free(void* p, bool isArray = false){

          cout<<"\tfree by gc\n";

          mem_list.remove(chunk(p, isArray));

          if(isArray){

              ::operator delete[](p);

          }else{

              ::operator delete(p);

          }

     }

};

 

Singleton of gc maintains a records of allocation, when the singleton itself destroyed, it will iterate the record and free each element stored in it.

 

gc::~gc(){

     list<chunk>::iterator it;

     list<chunk> leak_list(mem_list);

     int i;

     cout<<"===============memory leak list==============\n";

     for(i=1, it=leak_list.begin(); it!=leak_list.end(); ++it, ++i){

          cout<<i<<": obj["<<hex<<it->ptr<<dec

              <<"]\tfinal release...";

     if(it->isArray)

          delete[] (gc_obj*)((char*)it->ptr+4);  //this is a trick, C++ add 4 bytes to record demension.

     else

          delete ((gc_obj*)it->ptr);

     }

}

 

For safety consideration, a copy of records is created first, it is named as leak_list, then the program print all the detail information out, and invoke delete and delete[] according to array flag. Note here is a very interesting trick, which is commented in the above. We will spend some time to explain it. first let consider the following code:

 

void* raw_ptr;

 

class Foo{

public:

     Foo(){}

     ~Foo(){}

    

     static void* operator new[](size_t size){

          raw_ptr=::operator new[](size);

          cout<<"raw addr:"<<hex<<raw_ptr<<endl;

          return raw_ptr;

     }

};

 

int main(int argc, char* argv[]){

     Foo* ptr = new Foo[5];

     cout<<"ptr addr:"<<hex<<p<<dec<<endl;

     return 0;

}

 

Can you guess the result out? it may surprise you:

raw addr:0x3d3e40

ptr addr:0x3d3e44

 

Why the addresses before new and after new are different? why there are 4 bytes offset? Let us think the following code in depth:

Foo* p1 = new Foo[3];

Foo* p2 = new Foo[5];

delete[] p1;

delete[] p2;

 

The problem is how C++ know the number of object it should released when invoking delete[]? how many object it should delete? 3 or 5? It seems that the following code is easier to understand.

delete[](3) p1;

delete[](5) p2;

 

The answer is that the compiler does this magic things behind. When the compiler processes the code new Foo[3], It will first allocate memories, in 32-bit version, the memory size will be 3 times of Foo's size plus 4 byte. The extra 4 bytes are put at the head position for recording the array size, for this example it is 3, then the compiler returns the adress of 5th byte as p1. However, when this address is stored in chunk, it is force cast to void*. When you invoke delete[] to this address, the address of 5th byte with type void*,a very important information, the element amount for the arry (which is 3 for this example) is lost. the program will crash here. Therefore, the right way is:

 

delete[] (Foo*)((char*)raw_ptr+4);

 

The story doesn't end here, if you remove the virtual dtor in Foo, the result becomes amazing:

raw addr:0x3d3e40

ptr addr:0x3d3e40

 

What does this result mean? The compiler treats the object with and without dtor in quite different way. When a array contains n objects is freed, there are 2 steps. 1st, call dtor for each elements, 2nd, return the memories to syste. so the 1st step can be omitted if there isn't any dtor at all. the compiler will perform this optimization, it will not store the element number when allocating and retuns the memories directly when deleting. Since gc_obj does have virtual dtor, the movement of 4 bytes offset before delete[] is the just the right way.

 

Now we can perform a test:

 

int main(int argc, char* argv[]){

     class Foo: public gc_obj{

     public:

          Foo(string name):gc_obj(name){}

          Foo():gc_obj("noname_Foo"){}

          ~Foo(){}

     };

 

     Foo* p1 = new Foo("obj1");

     Foo* p2 = new Foo("obj leak");

     Foo* p3 = new Foo[5];

     delete p1;

     p2 =0;  //mem leak

     p3 =0;  //array leak

 

     return 0;

}

 

The out put is as the following:

        alloc by gc at: 003A3578 for obj1

        alloc by gc at: 003A3270 for obj leak

        alloc by gc at: 003A6028 for noname_Foo

noname_Foo

noname_Foo

noname_Foo

noname_Foo

        free by gc

===============memory leak list==============

1: obj[003A3270]        final release...        free by gc

2: obj[003A6028]        final release...        free by gc

 

The following parts will discuss another resource management method, 2 step construction and clean stack.

 

The environment is somewhat different when using this method, it is the time when ISO standard is not so popular. some C++ compiler even didn't support try-catch at all. Such environment can also be found today, in some embedded OS but not PC. There are only very limited resources.

 

Therefore, the facts can be summarized as the following:

  1. All the programmers write their code very careful, they will release every allocated resource;

  2. There are limited resources, "not enough memory" is a very common case;

  3. There is no try-catch mechanism.

 

For the 3rd point, Some team create a programming level solution, for example the Symbian Trap-Leave solution. it performs trap where exception may occur. when there are something wrong, a process named leave will be invoked. for instance:

 

TRAPD(error, MyFunc());

 

if(error){

     // deal with the wrong case

}

else{

     // OK

}

 

void MyFunc(){

     // process here...

     Foo* ptr= new Foo; // a Null pointer will be returned if failed,

                        // this is the case before ISO 98, since there

                        // is no try-catch mechanism at that time.

     if(!ptr)

          User::Leave();

}

 

But TRAPD, as a MACRO, is not ensured by compiler. For try-catch, block, you can put all the doubted parts in the block, but for TRAPD MACRO, you have to put them into a function, of course this function can also call other functions which may leave. When leave occurs, a clean stack will collect all allocated resources and return them to system.

 

The idea of clean stack is that, clean stack will record every allocation operations. Those allocated pointers will be pushed into the stack and popped in future. When there are exception, clean stack will iterate all its elements and perform destroy for them.

 

Clean stack can be implemented just as gc, here is a example:

class CleanupStack{

public:

     static void _push(Base* ptr){

          instance()._cleanStack.push(ptr);

     }

 

     static void pop(Base* ptr){

          instance()._cleanStack.pop();

     }

 

     static void pop_and_destroy(){

          delete (instance()._cleanStack.top());

          pop();

     }

 

     static CleanupStack& instance(){

          static CleanupStack inst;

          return inst;

     }

 

     ~CleanupStack(){

          while(!_cleanStack.empty()){

              delete (_cleanStack.top());

              _cleanStack.pop();

          }

     }

private:

     CleanupStack(){}

     CleanupStack(const CleanupStack&);

     CleanupStack& operator = (const CleanupStack&);

 

     stack<Base*> _cleanStack;

};

 

Although it is very simple, it works. The requirement for the programmer is that, he must take care of the order for push and pop, because the stack is LIFO data structure. the codes using trap-leave is like the following:

 

Foo* ptr= new Foo;

     CleanupStack::_push(ptr);

 

     // do something with ptr...

 

     CleanupStack::pop_and_destroy();

 

But here comes a new problem, consider the following codes:

 

class MyClass{

public:

     MyClass(){

          _file= new File;

          _network = new Network;    //What will happen if failed in this line?

     }

 

     ~MyClass(){

          delete _file;

          delete _network;

     }

private:

     File*     _file;

     Network*  _network;

}

 

MyClass* ptr= new MyClass;

 

As shown in the above, what will happen if the ctor failed inside?

 

In fact, when operator new is invoked, there are 2 jobs need to do: 1st, allocate memories, 2nd, call ctor. Now we can point out the precision position of failure, after memory allocation OK and inside ctor. but the result is very sad. we can not tell the failure in detail, because we only have a ptr.

 

The failure inside ctor drove people mad, so some team introduce an extreme way, disable ctor. All the classes with data member can not have public ctor! they must be initialized in 2 steps as the following:

 

class Foo:public Base{

public:

     static Foo* _new(int data){

          Foo* self = Foo::_new_and_construct(data);

          CleanupStack::pop(self);

          return self;

     }

    

     static Foo* _new_and_construct(int data){

          Foo* self = new Foo;

          CleanupStack::_push(self);

          self->_construct(data);

          return self;

     }

    

     ~Foo(){}

    

private:

     Foo(){}   //disable init.

 

     void _construct(int data){

          _data=data;

     }

 

     int _data;

};

 

Foo* ptr = Foo::_new(5);

 

This is the 2 steps construction, the 1st step only allocate memories, since the ctor is empty, there will not be any further operations for the data member. then it enter the 2nd risk step, which may cause exception. the member function _construct will initialize all data members, the code convention forces all "doubted risk function" start with a prefix "_". If there are any pointer typed data members, they should be also initialized by using 2 steps construction.

 

The other rule is that, all such classes (which use 2 steps contraction) can not be instanced in stack, because they don't provide public ctor.

 

All the 2 methods explained in this essay are created by very clever and experienced people. What's the result? Yes, the resource allocated by programmer is managed while the system becomes somewhat more complicated. In recent days some great developers suggest to use RAII. It bring us a new idea.

 

Reference

[1] Scott Meyer, Effective C++.

[2] Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Pattern Applied. Addison Wesley, Feb. 2001

[3] Leigh Edwards, Richard Barker, etc. Developing series 60 Applications: A guide for symbian OS C++ developers. Addison Wesly.


[Chinese][Next][Index][Home][Contact us: liuxinyu95@gmail.com]