This is the mail archive of the cygwin-patches@cygwin.com mailing list for the Cygwin project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Probably unnecessary InterlockedCompareExchangePointer inList_remove in thread.h


I think that the InterlockedCompareExchangePointer had some meaning there. I
have been studying this problem a bit more and I think that I have found the
reason it should be present:

Suppose there are two threads. One is trying to insert a new node and the
second is trying to remove head, both using the same list. Now what if we have
this scenario:

1. List_remove executes up to the point where it has value of head->next
prepared to be stored to head (line 20) but has not done so yet.

2. List_insert executes the atomic compare and exchange of the
head with the new node making the new node into new head (line 8).

3. List_remove stores the value of head->next that it has computed in step 1 to
head variable (line 20).

4. At this point both the new head inserted by List_insert and the old head
have been lost because we have overwritten the head variable with pointer to
to the element that was at the beginning next to head.

The InterlockedCompareExchangePointer prevents this situation for the price of
double synchronization. The problem is that List_insert employs what is called
lock-free approach. It doesn't honor the lock in List_remove and changes state
behind Lock_remove's back even if it has the list locked.

After all the way it was before my patch seems to be the best because it allows
for concurency in List_insert.


     1  template <class list_node> inline void
     2  List_insert (list_node *&head, list_node *node)
     3  {
     4    if (!node)
     5      return;
     6    do
     7      node->next = head;
     8    while (InterlockedCompareExchangePointer (&head, node, node->next) !=
node->next);
     9  }
    10
    11  template <class list_node> inline void
    12  List_remove (fast_mutex &mx, list_node *&head, list_node const *node)
    13  {
    14    if (!node)
    15      return;
    16    mx.lock ();
    17    if (head)
    18      {
    19        if (head == node)
    20          head = head->next;
    21        else
    22          {
    23            list_node *cur = head;
    24
    25            while (cur->next && node != cur->next)
    26              cur = cur->next;
    27            if (node == cur->next)
    28              cur->next = cur->next->next;
    29          }
    30      }
    31    mx.unlock ();
    32  }



VH


On Mon, 30 May 2005, Christopher Faylor wrote:

> On Mon, May 30, 2005 at 02:33:30PM -0400, Christopher Faylor wrote:
> >I think this patch should be ok to apply.
>
> So I applied it.  I beefed up the ChangeLog entry a little more
> descriptive about the reason for the change (even though that may not be
> 100% GNU compliant).
>
> Thanks.
>
> cgf
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]