灵巧指针与垃圾回收.doc

灵巧指针与内存回收
在JAVA 和 C# 中都有垃圾回收功能，程序员在分配一段内存后可以不再理会，而由垃圾回收自动回收，从而使程序员从复杂的内存管理中解脱出来。这是JAVA 和 C#的一大优点。而C++程序员在用 new 分配了一段内存后，还必须用 delete 释放，否则将造成资源泄漏。因此，一些C++ 书上经常告诫程序员：要养成好的习惯，new 与 delete 要成对出现，时刻记住将内存释放回系统。但是，事情只是这么简单吗？
经常地，在使用C++的过程中，我们会遇到下面的情形：
class A
{
public：
A（）；
~A（）；
SetNextPtr（A* Ptr）
{pNext=Ptr；}

private：
A * pNext；
}
一般地，为了不引起内存泄漏，我们会在析构函数中释放pNext，象下面这样：
A：：~A（）
{
if（pNext）
delete pNext；
pNext=NULL;
}
对于一般情况，这样就够了，但在某些情形下，这样也会出问题的，象下面这样：
A *ptrB = new A;；
A *ptrA = new A；
ptrB->SetNextPtr(ptrA);
ptrA->SetNextPtr(ptrB);

delete ptrB
这样会出问题,因为这些指针连成了一个回环,无论从那一个点开始删除,都会造成一个指针被删除两次以上,这将使得程序抛出异常。当然，也有一些方法可以用来解决这个问题，但是我要说明的是：对于C++程序员来说，养成一个好的习惯并不难，难就难在有时候这样将把你带入一种逻辑的混乱当中 ，增加一些不必要的麻烦，有时甚至不知所措。
可是如何解决这个问题呢？如果C++也具有垃圾回收的功能，那么，这个问题当然就迎刃而解了。但是C++属于编译型语言，不会具备这个功能。长期以来，我也一直在思考这个问题，想找出一种方法来使自己从这种麻烦中解脱出来。直到最近开始学习泛型编程，看到灵巧指针的介绍以后，我灵光一闪，终于找到了办法来解决这个问题。
大家知道，灵巧指针具有一些灵巧特性，如在构造时可以自动初始化，析构时可以自动释放所指的指针。我们就利用它的这些特性来实现我们的垃圾回收。
首先，我们要想办法来对我们用 new 分配的每一段内存增加引用记数，即记录下当前指向它的灵巧指针个数，当最后一个指向它的指针被释放时，我们就可以释放这段内存了。由此，我们进行了new 和 delete 的全局重载，并引入了CPtrManager 类。

void operator delete(void * p)
{

int mark=thePtrManager.GetMarkFromPtr(p);
if(mark>0)
thePtrManager.UserDelete(mark);
free(p);
}
void * operator new(size_t size)
{

return thePtrManager.MallocPtr(size);

}
class CPtrManager
{
public:
int GetCount(int mark,void * p); //得到当前的引用记数
static CPtrManager* GetPtrManager(); //得到全局唯一的CPtrManager 指针
void UserDelete(int mark); //删除 mark 标志的指针，并对指针和标志复位
void * MallocPtr(size_t size); //new（）调用它分配内存；
BOOL AddCount(int mark,void * Ptr); //增加引用记数
BOOL Release(int mark,void * Ptr); //减少引用记数
int GetMarkFromPtr(void * Ptr); //通过指针得到标志
CPtrManager();
virtual ~CPtrManager();
private:
static CPtrManager * p_this; //指向全局唯一的CPtrManager 指针
void AddPtr(void * Ptr); //增加一个新分配的内存
CPtrArray m_ptr; //存放分配的指针的可变数组
CUIntArray m_count; //存放指针的引用记数
void* pCurrent; //最近刚分配的指针
unsigned int m_mark; //最近刚分配的指针的标志
CUIntArray m_removed;//存放m_ptr中指针被删除后所空留的位置
};
顾名思义，CPtrManager 就是用来管理指针的，对于我们用new 分配的每一个指针，都存放在m_ptr[index]中，并在m_count[index]中存放它的引用记数。同时，我们对每一个指针都增加了一个标志（mark >0,<=0为无效），这个标志同时存在于灵巧指针中（后面将看到），这是为了一种双重保险，并且在这里，这个标志就等于指针在m_ptr中的索引，这也为快速查找提供了方便。
总的思路是这样的：当我们用new分配一个指针时，这个指针将被存入CPtrManager中，当一个灵巧指针开始拥有这个指针时，CPtrManager将负责对这个指针的引用记数加 1 ，反之亦然，即一个灵巧指针开始释放该指针的拥有权时，CPtrManager将负责对这个指针的引用记数减 1 ，如果引用记数为 0 ，那么这个灵巧指针将负责对该指针 delete。
下面是灵巧指针的部分介绍：
template
class auto_ptr
{
public:
auto_ptr()
{mark=0;pointee=0;}
auto_ptr(auto_ptr&rhs);
auto_ptr(T*ptr);
~auto_ptr(){Remove();}
T*operator->() const;
operator T*();
T&operator*()const;
auto_ptr&operator=(auto_ptr&rhs);
auto_ptr&operator=(T*ptr);
private:
void Remove(); //释放所指指针的拥有权
T*pointee; //所拥有的指针
int mark;//所拥有的指针的标志
};
template void auto_ptr< T>::Remove()
{
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pointee&&pMana)
{
if(pMana->Release(mark,pointee)) //减少引用记数
{
if(pMana->GetCount(mark,pointee) ==0)
delete pointee; //如果引用记数为0，delete 指针
}
else //所拥有的指针不在CPtrManager 中，有可能在栈中
{

//User decide to do
}

}
pointee=NULL; //复位
mark=0;
}
template auto_ptr< T>::auto_ptr(auto_ptr&rhs)
{
pointee=rhs.pointee;
mark=rhs.mark;
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pMana)
pMana->AddCount(mark,pointee); //增加引用记数

}
template auto_ptr< T>::auto_ptr(T*ptr)
{
mark=0;
pointee=ptr;
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pMana)
{
mark=pMana->GetMarkFromPtr(ptr); //得到指针的标志
if(mark>0)
pMana->AddCount(mark,pointee); //如果标志不为0，增加引用记数
}
}
templateauto_ptr& auto_ptr< T>::operator=(auto_ptr&rhs)
{
if(pointee!=rhs.pointee)
{
Remove(); //释放当前指针的拥有权
pointee=rhs.pointee;
mark=rhs.mark;
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pMana)
pMana->AddCount(mark,pointee);

}
return *this;

}
template auto_ptr&auto_ptr< T>::operator = (T* ptr)
{
if(pointee!=ptr)
{
Remove();
pointee=ptr;
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pMana)
{
mark=pMana->GetMarkFromPtr(ptr);
if(mark>0)
pMana->AddCount(mark,pointee);
}
}

}
当到了这里时，我便以为大功告成，忍不住摸拳搽掌，很想试一试。结果发现对于一般的情况，效果确实不错，达到了垃圾回收的效果。如下面的应用：
auto_ptr p1=new test;
auto_ptrp2 = p1;
auto_ptrp3 = new test;
但是，很快地，我在测试前面提到的回环时，就发现了问题，我是这样测试的：
class test
{
auto_ptr p;
};

auto_ptr p1=new test;
auto_ptrp2 =new test;
p1->p=p2;
p2->p=p1;
当程序执行离开作用域后，这两块内存并没有象我想象的那样被释放，而是一直保留在堆中，直到程序结束。我仔细分析造成这种现象的原因，发现了一个非常有趣的问题，我把它称之为互锁现象。
上面p1 所拥有的指针被两个灵巧指针所拥有，除p1外，还有p2所拥有的 test 类中的灵巧指针p，p2亦然。也就是说，这两块内存的指针的引用记数都为 2 。当程序执行离开作用域后，p1，p2被析构，使它们的引用记数都为1，此后再没有灵巧指针被析构而使它们的引用记数变为 0 ，因此它们将长期保留在堆中。这就象两个被锁住的箱子，其中每个箱子中都装着对方的钥匙，但却无法把彼此打开，这就是互锁现象。
可是如何解决呢？看来必须对它进行改进。同时，我也发现上面的方法不支持多线程。所以，我们改进后的方法不仅要解决互锁现象，而且还要支持多线程。下面是我改进后的方法：
首先是如何发现这种互锁现象。我们知道，互锁现象产生的根源在于拥有堆中内存的灵巧指针本身也存在于已分配的堆内存中，那么，如何发现灵巧指针是存在于堆中还是栈中就成了问题的关键。由此，我引入了一个新的类 CPtr，由它来管理用 new 分配的指针，而 CPtrManager 专门用来管理 CPtr。如下所示：
class CPtr
{
friend class CMark;
public:
int GetPtrSize(); //得到用 new 分配指针的内存的大小
CMutex * GetCMutex(); //用于线程同步
void * GetPtr(); //得到用 new 分配的指针
CPtr();
virtual ~CPtr();
int GetCount(); //得到引用记数
void AddAutoPtr(void * autoPtr,int AutoMark);//加入一个拥有该指针的灵巧指针
BOOL DeleteAutoPtr(void * autoPtr); //释放一个灵巧指针的拥有权
void SetPtr(void * thePtr,int Size, int mark,int count=0); //设置一个新的指针

void operator delete(void * p)
{
free(p);
}
void * operator new(size_t size)
{
return malloc(size);
}

private:
int m_mark; //指针标志
int m_count; //引用记数
void * m_ptr; //分配的指针
int m_size; //指针指向内存的大小
CPtrArray AutoPtrArray; //存放拥有该指针的所有灵巧指针的指针数组
CUIntArray m_AutoMark; //灵巧指针标志：0 in the stack; >0 =mark
CMutex mutex; //用于线程同步
};
class CPtrManager
{
public:
int GetAutoMark(void * ptr); //通过灵巧指针的指针，得到灵巧指针标志
CPtrManager();
virtual ~CPtrManager();
int GetMarkFromPtr(void * Ptr);
void *MallocPtr(size_t size);
BOOL bCanWrite();
void DeletePtr(int mark,void * Ptr);
void AddPtr(void *Ptr,int PtrSize);
static CPtrManager * GetPtrManager();
CPtr * GetCPtr(void * Ptr,int mark);//通过指针和指针标志得到存放该指针的 CPtr

private:
CPtrArray m_ptr; //存放 CPtr 的指针数组
void* pCurrent;
unsigned int m_mark;
CUIntArray m_removed;
BOOL bWrite; //在解决互锁现象的过程中，谢绝其它线程的处理
static CPtrManager * p_this;
CMutex mutex;//用于线程同步
CMarkTable myMarkTable;
void RemoveLockRes(); //处理互锁内存
void CopyAllMark(); //处理互锁现象前，先对所有的CPtr进行拷贝
static UINT myThreadProc(LPVOID lparm); //处理互锁现象的线程函数
CWinThread* myThread;
void BeginThread()
{ myThread=AfxBeginThread(myThreadProc,this,THREAD_PRIORITY_ABOVE_NORMAL);}
};
上面的应用中加入了灵巧指针的标志，其实，这个标志就等于该灵巧指针所存在的内存的指针的标志。例如：我们用 new 分配了一个 test 指针，假如这个指针的标志 mark=1，那么，这个 test 中的灵巧指针 auto_ptr p 的标志 automark=1。如果一个灵巧指针存在于栈中，那么它的 automark=0。反之亦然，如果一个灵巧指针的 automark 等于一个指针的 mark，那么，该灵巧指针必存在于这个指针所指的内存中。可是，如何得到这个标志呢，请看下面这个函数的实现：
int CPtrManager::GetAutoMark(void *ptr)
{
CSingleLock singleLock(&mutex);
singleLock.Lock(); //线程同步

int size =m_ptr.GetSize();
for(int i=1;iGetPtr();//得到内存的首指针
int ptrEnd=ptrFirst+theCPtr->GetPtrSize();//得到内存的尾指针
int p=(int)ptr; //灵巧指针的指针
if(p>=ptrFirst&&p<=ptrEnd)//比较灵巧指针的指针是否在首尾之间
return i;
}
}
return 0;
}
这个函数的原理就在于：如果一个灵巧指针存在于一块内存中，那么该灵巧指针的指针必在这块内存的首尾指针之间。
解决了灵巧指针的位置问题，下一步就是要找出所有被互锁的内存的指针。这个好实现，只要所有拥有这个指针的灵巧指针的 automark > 0 ，那么，这块内存就可能被互锁了(注意只是可能)，接着看下面的实现：
class CMark
{
friend class CMarkTable;
public:
CMark(){}
virtual ~CMark(){}

void operator delete(void * p)
{
free(p);
}
void * operator new(size_t size)
{
return malloc(size);
}
void CopyFromCPtr(CPtr* theCPtr); //从 CPtr 中拷贝相关信息
BOOL bIsNoneInStack(); //判断拥有该指针的所有灵巧指针是否都不在栈中
void Release(); //解除该指针的互锁
private:
int m_mark; //指针的标志
CPtrArray autoptrArray; //拥有该指针的所有灵巧指针的指针数组
CUIntArray automarkArray;//拥有该指针的所有灵巧指针的标志

};
class CMarkTable
{
public:
CMarkTable(){Init();}
virtual ~CMarkTable(){}

void AddCMark(CMark * theCMark);
BOOL FindMark(int mark);
void Init();
void DoLockMark(); //处理互锁问题
private:
CPtrArray CMarkArray; //暂存从CPtrManager 中拷贝过来的指针信息的 CMark 指针数组
CPtrArray CLockMarkArray; //存放互锁的内存
void GetLockMark(); //得到所有可能被互锁的内存的 CMark，结果存放于CLockMarkArray
BOOL FindLockMark(int mark); //判断一个灵巧指针是否存在于CLockMarkArray所包含的指针中
void RemoveUnlockMark();//去除假的互锁内存
void RemoveGroup(int automark);//对互相有联系的相互死锁的内存进行分组

};
这里又引入了两个类：CMark 和 CMarkTable ，这是为了在处理互锁问题之前，对 CPtrManager 中的 CPtr 进行快速拷贝，以防止影响其它线程的正常运行。其实，这里的 CMark 与 CPtr 没有什么区别，它只是简单地从 CPtr 中拷贝信息，也就是说，它等同于 CPtr 。
为了处理互锁问题，先要把可能被互锁的内存指针找出来，看下面函数的实现：
void CMarkTable::GetLockMark()
{
CLockMarkArray.SetSize(0);
int size=CMarkArray.GetSize();
for(int i=0;ibIsNoneInStack())
CLockMarkArray.SetAtGrowi,theMark);
}
}
}
把这些内存找出来之后，就需要把那些假锁的内存找出来，什么是假锁呢？看下面的例子：
对于指针 ptrA ，如果它的灵巧指针 autoA 存在于指针 ptrB 中，而 ptrB 的灵巧指针 autoB 又存在于 ptrA 中，那么 ptrA 和 ptrB 是真锁，但是如果ptrB 的灵巧指针 autoB 存在于指针 ptrC 中，而 ptrC的灵巧指针 autoC 存在于栈中，那么， ptrA 和 ptrB 属于假锁。怎么找出假锁的内存呢？看下面函数的实现：
void CMarkTable::RemoveUnlockMark()

{
CUIntArray UnlockMarkArray;
BOOL bNoneRemoveed;
do
{
bNoneRemoveed=TRUE;
UnlockMarkArray.SetSize(0);
int size=CLockMarkArray.GetSize();
for(int i=0;iautomarkArray).GetSize();
for(int j=0;jautomarkArray)[j];
if(!FindLockMark(mark)) //判断灵巧指针是否存在于CLockMarkArray所包含的指针中
{
UnlockMarkArray.InsertAt(0,i); //record to remove
bNoneRemoveed=FALSE;
break;
}
}
}
else
{ UnlockMarkArray.InsertAt(0,i);
bNoneRemoveed=FALSE;
}
}
int size2=UnlockMarkArray.GetSize();
for(int k=0;kCLockMarkArray所包含的指针中的指针，直到所有的指针的灵巧指针都存在于CLockMarkArray所包含的指针中。
所有被互锁的内存被找出来了，那么，下一步就是如何解锁的问题了。由此，我对灵巧指针引入了一个父类parent_autoptr 如下：
class parent_autoptr
{
public:
parent_autoptr()
{thisAutoMark=0;}
virtual ~parent_autoptr(){}
virtual void Release(){} //释放指针的拥有权
protected:
int thisAutoMark; //存放灵巧指针标志
};
在灵巧指针中，对函数 Release() 进行了重载。
template
class auto_ptr :public parent_autoptr
{
public:
virtual void Release(){Remove();}
auto_ptr()
{mark=0;pointee=0;thisAutoMark=GetAutoMark();}
auto_ptr(auto_ptr&rhs);
auto_ptr(T*ptr);
~autoptr(){Remove();}
T*operator->() const;
operator T*();
T&operator*()const;
auto_ptr&operator=(auto_ptr&rhs);
auto_ptr&operator=(T*ptr);
private:
void Remove();
int GetAutoMark();
CMutex *GetCMutex();
void ReadyWrite();
T*pointee;
int mark;

};
在 CMarkTable 和 CMark 中对互锁内存进行了释放，如下：
void CMarkTable::DoLockMark()
{
GetLockMark();
RemoveUnlockMark();

int size=CLockMarkArray.GetSize();
while(size)
{
CMark* theMark=(CMark*)CLockMarkArray[0];
CLockMarkArray.RemoveAt(0);
if(theMark)
{
int size2=(theMark->automarkArray).GetSize();
for(int i=0;iautomarkArray)[i];
RemoveGroup(automark);
}
theMark->Release();

}
size=CLockMarkArray.GetSize();
}

Init();
}

void CMark::Release()
{
int size=autoptrArray.GetSize();
for(int i=0;iRelease();
}
}

到了现在，终于算是大功告成了，我马上把它投入测试当中，发现工作得非常好，即使开辟20至30个线程，程序也工作得很好，并没有抛出异常，而且垃圾回收的功能也非常好。但是，如果线程太多，那么在 CPtrManager 中为了保证线程同步，将会造成瓶颈效应，严重者将会严重影响执行效率。同时，如果每个线程都不停地产生死锁内存，那么，垃圾回收将应接不暇，时间长了，也会造成系统的资源耗尽。
代码的使用很简单，你只需要将我所附的两个文件加入到工程中，然后，在你的 C*App 中加入如下一段代码就行了：
CPtrManager thePtrManager;
这将保证 thePtrManager 在进程最后结束的时候才被析构。
如果你是在一个新的工程中使用，这就够了，但是，如果你还要使用原来的代码，特别是有指针参数的传递时，那么，你必须注意了。
如果需要从老代码中接收一个指针，而且这个指针需要你自己释放，那么可以使用灵巧指针，如果不需要释放，那么只能使用一般指针；
如果需要传递一个指针给老代码，而且这个指针需要你自己释放，那么可以使用灵巧指针，否则，只能使用一般指针。

我将随后附上所有源代码，由于没有经过严格测试，所以大家在使用前最好再测试一遍，最好能将发现的问题公布或写信告之于我，本人表示感谢。
欢迎大家下载测试，批评指正和改进，
Email: ydshzhy@