A Lock Free Doubly Linked List With Safe Memory Reclamation

• Download lockfreedoublylinkedlist.zip - 16.2 KB

Introduction

In the previous article, I presented a lock free doubly linked list.  In a garbage-collected environment, memory reclamation is automatic. Without garbage collection, however, we need to be care full in reclaiming memory because it can give rise to dangling reference (a reference to a reclaimed memory cell). We use Hazard Pointers [Michael 2004] for safe memory reclamation. The hazard pointer methodology at an abstract level is that a thread sets a global (hazard) pointer equal to a shared pointers value before using this value in ABA prone comparison And make sure that when the value of the shared pointer is set to a new value using CAS then that value is not among those values that shared pointer previously attained and a hazard pointer has that value. This ensures that if a thread has set a hazard pointer to the value of a shared pointer then that value cannot be involved in an ABA prone comparison because the function that calculates the new value of shared pointer will not return that value. We have applied the hazard pointer methodology to lock free doubly linked list. 

Background

Doubly Linked list is a list of items where items can be anywhere in memory. Each item contains two fields. Next field points to next item in the list. Prev field points to prev item in the list. These two fields allow list traversal in either direction. Doubly Linked List support insert and delete operation. These operations are trivial to implement. But in a multithreaded environment most common method is mutual exclusion which suffers from deadlocks and priority inversion scenarios. The answer to these problems is lock freedom. In lock free system, when a thread takes few steps then the system as a whole makes progress. By definition lock free system are free from deadlocks. However there is a risk of starvation. Wait free systems are lock free and moreover they avoid the starvations as well. For further readings you can go through my previous article.

Hazard Pointers

The main shared data structure (HPRecType) is the linked list of hazard pointer (HP) struct. The linked list is initialized to contain one HP array for each of the N participating threads. The total number of hazard pointers is N*K where K is the maximum number of hazard pointers 

struct HPRecType
{
	Node *HP[K];
	HPRecType *Next;
};

The linked list data structure is augmented with rlist array (retired list) and rcount array(retired count), to maintain a list of retired nodes per thread.

__declspec(align(InterLockedAlign))struct LinkedList
{
	volatile AnnounceOp *announce;//current announcement
	Node *first;//first node
	Node *end;//end node	
	list <Node* >	rlist[THREADCOUNT];
	int rcount[THREADCOUNT];
	HPRecType *HeadHPRec;
};

The RetireNode routine is where the retired node is inserted into rlist and the rcount is updated. Whenever rcount reaches a threshold R, the thread scans the list of hazard pointers using the Scan routine.

void RetireNode(HPRecType*HeadHPRec,  Node *node,list < Node* > &	rlist,int &	rcount)
{
	rlist.push_back(node);
	rcount++;
	if(rcount>=THREADCOUNT*K)
	{
		Scan(HeadHPRec,rlist,rcount);
	}
}

The scan consists of two parts. The first part involves scanning the HP linked list for non null values. Whenever a non null value is encountered, it is inserted in a local list plist.

The second part of Scan involves looking up each node in rlist against the pointers in plist. If the lookup fails, the node is identified to be ready for de-allocation. Otherwise, it is retained in rlist until the next scan by the current thread.

void Scan(HPRecType *head,list<Node*> & rlist,int & rcount)
{
	list < Node* > plist;
	HPRecType *hprec=head;
	while(hprec!=NULL)
	{
		for(int i=0;i < K;i++)
		{
			Node *hptr=hprec-> HP[i];
			if(hptr!=NULL)
			{
				plist.push_back(hptr);
			}
		}
		hprec=hprec-> Next;
	}

	list <Node*> tmplist=rlist;
	rlist.clear();
	rcount=0;

	Node *node=tmplist.back();
	tmplist.pop_back();
	while(node!=NULL)
	{
		if(Lookup(plist,node))
		{
			rlist.push_back(node);
			rcount++;
		}
		else
		{
			_aligned_free(node);
		}
		if(tmplist.empty()==false)
		{
			node=tmplist.back();
			tmplist.pop_back();
		}
		else
		{
			node=NULL;
		}
	}
	plist.clear();
}

The hazard pointers are initialized in following routine.

void Initialize(LinkedList *l)
{

	l->HeadHPRec=new HPRecType;
	HPRecType *currHPRec=l->HeadHPRec;
	for(int i=0;i<THREADCOUNT;i++)
	{
		for(int i=0;i<K;i++)
		{
			currHPRec->HP[i]=0;
		}
		currHPRec->Next=new HPRecType;

		currHPRec=currHPRec->Next;
	}
	currHPRec->Next=0;
}

A hazardous reference is an address that without further validation of safety will be used to access possibly unsafe memory and/or as a target address or an expected value of an ABA-prone comparison.

First we examine thread that traverses linked list to identify hazards and hazardous reference

for(i=0;i<iterations;i++)
{
Node *p=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );//new Node;
	assert(p);
	p->data=i;
	do
	{
		insertCount++;
		x=first->rlink;
		while(1)
		{
			if(rand()%2==0)
				break;
			else
			{
				if(x->rlink==l.end)
					x=first->rlink;
				else if(x->rlink!=0)
					x=x->rlink;
				else
					x=first->rlink;
			}

		}
		
	}while(!Insert(p,x));
}

x=first->rlink;

The above access is an access hazard because the second node in the linked list may have been removed and reclaimed by another thread.

x->rlink==l.end

The above access (x->rlink) is an access hazard because the node x may have been removed and reclaimed by another thread.

x=x->rlink;

The above access (x->rlink) is an access hazard because the node x may have been removed and reclaimed by another thread.

For each hazardous reference, we insert the following steps in the above routine:

Write the address of the node that is the target of the reference to an available hazard pointer.

Validate that the node is safe (the node might have been already removed). If the validation succeeds, follow the normal flow of control of the target algorithm. Otherwise, retry. The following is the code augmented with hazard pointer.

for(i=0;i<iterations;i++)
{
	Node *p=(Node *)_aligned_malloc(sizeof(struct Node),InterLockedAlign );//new Node;
	assert(p);
	p->data=i;
	bool inserted=false;
	do
	{
		x=first->rlink;
		hPrec->HP[0]=x;
		if(first->rlink!=x) continue;

		Node *x_rlink=x->rlink;
		hPrec->HP[1]=x_rlink;
		if(x->rlink!=x_rlink) continue;
		bool safe=true;
		while(1)
		{
			if(rand()%2==0)
				break;
			else
			{
				Node *x_rlink=x->rlink;

				if(x_rlink!=0)
				{
					hPrec->HP[0]=x_rlink;
					if(x->rlink!=x_rlink)
					{
						safe=false;
						break;
					}
					x=x->rlink;
					x_rlink=x->rlink;
					hPrec->HP[1]=x_rlink;
					if(x->rlink!=x_rlink)
					{
						safe=false;
						break;
					}
				}
				else
				{
					x=first->rlink;
					hPrec->HP[0]=x;
					if(first->rlink!=x) {
						safe=false;
						break;
					}
						
					Node *x_rlink=x->rlink;
					hPrec->HP[1]=x_rlink;
					if(x->rlink!=x_rlink) {
						safe=false;
						break;
					}

				}
			}

		}
		if(safe==false)
			continue;
			inserted=Insert(&l,p,x,hPrec,l.rlist[threadNum],l.rcount[threadNum]);
		
	}while(!inserted);
}

Next we examine Insert to identify hazards and hazardous reference

int Insert(Node *p,Node *x)
{
	if(p==0||x==0) return 0;
	AnnounceOp *curAnnouncedOp;
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );//To announce an insert operation.
	assert(nextAnnounceOp);
	while(1)
	{		
		curAnnouncedOp=(AnnounceOp *)l.announce;
		if(curAnnouncedOp->opName==NONE)
		{
			try
			{
				if(l.first==x||l.end==x||l.end->llink==x)
				{
					_aligned_free(nextAnnounceOp);
					return 0;
				}
				p->llink=x;
				p->rlink=x->rlink;
				if(p->rlink==0||p->llink==0)  goto label;
				nextAnnounceOp->opName=INSERT;
				nextAnnounceOp->insert.args.p=p;
				nextAnnounceOp->insert.args.x=x;
				
				nextAnnounceOp->insert.lv.x_rlink=x->rlink;
				if(nextAnnounceOp->insert.lv.x_rlink==0)  goto label;
				
				nextAnnounceOp->insert.lv.x_rlink_address=&x->rlink;

				nextAnnounceOp->insert.lv.x_rlink_llink=nextAnnounceOp->insert.lv.x_rlink->llink;
				if(nextAnnounceOp->insert.lv.x_rlink_llink==0)  goto label;
				nextAnnounceOp->insert.lv.x_rlink_llink_address=&nextAnnounceOp->insert.lv.x_rlink->llink;

				void *v1=reinterpret_cast<void *>(nextAnnounceOp);
				void *v2=reinterpret_cast<void *>(curAnnouncedOp);
				void *res=(void *)InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(&l.announce),(LONG)v1,(LONG)v2);
				if(res==v2)
				{
					InsertHelper(nextAnnounceOp);
					return 1;
				}
			}
			catch(...)
			{
				printf("Exception in Insert\n");
				_aligned_free(nextAnnounceOp);
				return 0;
			}
		}
		else if(curAnnouncedOp->opName==INSERT)
		{
			InsertHelper(curAnnouncedOp);
		}
		else if(curAnnouncedOp->opName==DELET)
		{
			DeleteHelper(curAnnouncedOp);
		}
	}
label:
	_aligned_free(nextAnnounceOp);
	return 0;
}

 

curAnnouncedOp=(AnnounceOp *)l->announce;
 

The above access (l->announce) is an access hazard because the structure may have been removed and reclaimed by another thread.

nextAnnounceOp->insert.lv.x_rlink=x->rlink;
 

The above access (x->rlink) is an access hazard because the node x may have been removed and reclaimed by another thread.

nextAnnounceOp->insert.lv.x_rlink_address=&x->rlink;
 

The above access (x->rlink) is an access hazard because the node x may have been removed and reclaimed by another thread.

nextAnnounceOp->insert.lv.x_rlink_llink=nextAnnounceOp->insert.lv.x_rlink->llink;
 

The above access (x_rlink->llink) is an access hazard because the node x may have been removed and reclaimed by another thread.

nextAnnounceOp will become a hazardous reference if CAS succeeds

The InterlockedCompareExchange in the code above is ABA hazard.

The following is the code augmented with hazard pointer that ensures safe memory reclamation and ABA prevention.

int Insert(LinkedList *l,Node *p,Node *x,HPRecType *hPrec,list<Node*>&rlist,int &rcount)
{
	if(p==0||x==0) return 0;
	AnnounceOp *curAnnouncedOp;
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );
	assert(nextAnnounceOp);
	while(1)
	{		
		curAnnouncedOp=(AnnounceOp *)l->announce;
		hPrec->HP[2]=(Node*)curAnnouncedOp;
		if(l->announce!=curAnnouncedOp) continue;
		if(curAnnouncedOp->opName==NONE)
		{
			try
			{
				if(l->first==x||l->end==x||l->end->llink==x)
				{
					_aligned_free(nextAnnounceOp);
					return 0;
				}
				p->llink=x;
				p->rlink=x->rlink;
				if(p->rlink==0||p->llink==0)  goto label;
				nextAnnounceOp->opName=INSERT;
				nextAnnounceOp->insert.args.p=p;
				nextAnnounceOp->insert.args.x=x;
				
				nextAnnounceOp->insert.lv.x_rlink=x->rlink;
				hPrec->HP[3]=nextAnnounceOp->insert.lv.x_rlink;
				nextAnnounceOp->insert.lv.x_rlink_address=&x->rlink;
				if(nextAnnounceOp->insert.lv.x_rlink!=x->rlink) goto label;
				if(nextAnnounceOp->insert.lv.x_rlink==0)  goto label;

				

				nextAnnounceOp->insert.lv.x_rlink_llink=nextAnnounceOp->insert.lv.x_rlink->llink;
				hPrec->HP[4]=nextAnnounceOp->insert.lv.x_rlink_llink;
				nextAnnounceOp->insert.lv.x_rlink_llink_address=&nextAnnounceOp->insert.lv.x_rlink->llink;
				if(nextAnnounceOp->insert.lv.x_rlink->llink!=nextAnnounceOp->insert.lv.x_rlink_llink) goto label;
				if(nextAnnounceOp->insert.lv.x_rlink_llink==0)  goto label;//node next to node x is unlinked
				
				hPrec->HP[5]=(Node*)nextAnnounceOp;

				void *v1=reinterpret_cast<void *>(nextAnnounceOp);
				void *v2=reinterpret_cast<void *>(curAnnouncedOp);
				void *res=(void *)InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(&l->announce),(LONG)v1,(LONG)v2);
				if(res==v2)
				{
					RetireNode(l->HeadHPRec,(Node*)v2,rlist,rcount);
					
					InsertHelper(l,nextAnnounceOp,rlist,rcount);
					return 1;
				}
			}
			catch(...)
			{
				printf("Exception in Insert\n");
				_aligned_free(nextAnnounceOp);
				return 0;
			}
		}
		else if(curAnnouncedOp->opName==INSERT)
		{
			InsertHelper(l,curAnnouncedOp,rlist,rcount);
		}
	}
label:
	_aligned_free(nextAnnounceOp);
	return 0;
}

 

Next we examine InsertHelper routine

void InsertHelper(AnnounceOp *curAnnouncedOp)
{	
	InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(curAnnouncedOp->insert.lv.x_rlink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink);
	InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(curAnnouncedOp->insert.lv.x_rlink_llink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink_llink);	
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );
	assert(nextAnnounceOp);
	nextAnnounceOp->opName=NONE;
	void *v1=reinterpret_cast<void *>(nextAnnounceOp);
	void *v2=reinterpret_cast<void *>(curAnnouncedOp);
	if(InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(&l.announce),(LONG)v1,(LONG)v2)==(LONG)v2)
	{
	}
	else
	{
		_aligned_free(nextAnnounceOp);
	}
}

 

InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(curAnnouncedOp->insert.lv.x_rlink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink);

The above access (curAnnouncedOp->insert.lv.x_rlink_address) is also an access hazard because the node x may have been removed and reclaimed by another thread.

InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(curAnnouncedOp->insert.lv.x_rlink_llink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink_llink);	

The above access (curAnnouncedOp->insert.lv.x_rlink_llink_address) is also an access hazard because the node right to x may have been removed and reclaimed by another thread.

The following is the code augmented with hazard pointer that ensures safe memory reclamation and ABA prevention.

void InsertHelper(LinkedList *l,AnnounceOp *curAnnouncedOp,list<Node*>&rlist,int &rcount)
{	
	InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(curAnnouncedOp->insert.lv.x_rlink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink);
	InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(curAnnouncedOp->insert.lv.x_rlink_llink_address),(LONG)curAnnouncedOp->insert.args.p,(LONG)curAnnouncedOp->insert.lv.x_rlink_llink);	
	AnnounceOp *nextAnnounceOp=(AnnounceOp*)_aligned_malloc(sizeof(struct AnnounceOp),InterLockedAlign );
	assert(nextAnnounceOp);
	nextAnnounceOp->opName=NONE;
	void *v1=reinterpret_cast<void *>(nextAnnounceOp);
	void *v2=reinterpret_cast<void *>(curAnnouncedOp);
	if(InterlockedCompareExchange(reinterpret_cast<volatile LONG *>(&l->announce),(LONG)v1,(LONG)v2)==(LONG)v2)
	{
		RetireNode(l->HeadHPRec, (Node*)v2,rlist,rcount);
	}
	else
	{
		_aligned_free(nextAnnounceOp);
	}
}

I checked the memory leaks using _CrtMemCheckpoint and _CrtMemDifference and didn't find any.

In the next article, I will apply hazard pointer methodology to delete routine (which deletes node from doubly linked list).

Reference

• [Michael 2004]Michael, M.M. “Hazard pointers: Safe memory reclamation for lock-free objects,” IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 8, Aug. 2004.
• A Lock Free Doubly Linked List by Muhammad Sarmad Asghar published in codeproject.