Handle table中CAS操作与A-B-A Problem解析

     在研究handle table的时候顺便研究的东西。Baidu了下，发现国内这方面的资料几乎没得，然后就准备瞎bb下，为下面的一篇介绍handle table的结构做准备。
  
  关于lock-free data structure。以及解决这个问题中使用的CAS（compare and swap）操作。以及使用CAS操作的时候出现的A-B-A Problem。
  
  对于lock-free data structure问题的解决，一般是使用流行的CAS操作。来防止需要读写的区域的数值和预期的数值不一样的情况。
  
  Shared,non-blocking的数据结构，和shared blocking的数据结构相比，采用了比较原始的同步方法。咱讨论最多的一个同步方法，就是CAS（compare and swap）。
  
  
  
   关于CAS操作的伪代码如下：
  
  CAS(A,B,C)
  
  BEGIN ATOMIC
  
  if (A==C) {A=B; return TRUE; }
  
  else { return FALSE; }
  
  END ATOMIC
  
  
  
  在使用CAS操作的时候，在计算之前，首先记录下一个变量的值。经常是记录一个shared data structure 实现的pointer。然后把这个变量的值存起来。这个时候，当得到了这个变量的新的值，需要update这个共享变量的数值的时候，就需要采用CAS操作来自动update这个共享变量的值。
  
  CAS操作首先检查shared var的值和已经保存起来的值是不是一样的，如果是一样的，就执行update操作。如果不是一样的，就报错。
  
  如果操作失败了的话，就使用这个shared var的新的值来重新做一次计算操作。这个原理，和数据库管理系统里面的并发控制是非常类似的。然后，就把这个shared var所在的link list里面相关的节点，指向一个新的node。这个过程就叫做swap。
  
  就如上面的伪代码里面给出的实现，下面给一个代码实现：
  
  
  
  bool cas(volatile word* memory, word newValue, word expectedValue)
  
  {
  
   atomically
  
   {
  
   if(*memory == expectedValue)
  
   {
  
   *memory = newValue;
  
   return true;
  
   }
  
   return false;
  
   }
  
  }
  
  
  
  这里介绍了对共享变量的最常用的CAS操作，那么使用这个操作的时候，会出现一个比较经典的问题，叫做A-B-A Problem。
  
  ABA Problem就是譬如一个共享变量A，需要update到一个新的值C，而记录这个变量的值是B，此时A=B；在记录和update的这段时间中，这个共享变量被其余的job或者是thread操作修改了很多次，但是在update之前，还是回到了最开始的值。这就叫做ABA Problem。在构造一个特定的程序的时候，就会出现问题。
  
  
  
  下面是在一个调用stack里面的ABA Problem：
  
  
   class members
   foo (thread stack)
  
  foo: pop till 1.
   head_ = a
   current = a
  
  
   head_->next_ = b
   current->next_ = b
  
  bar: pop node a
   head_ = b
  
  
  
   head_.next_ = c
  
  
  bar: pop node b
   head_ = c
  
  
  
   head_.next_ = d
  
  
  bar: push node a
   head_ = a
  
  
  
   head_.next_ = c
  
  
  foo: pop 2. cas
   head_ = a
   current = a
  
  
   head_.next_ = c
   current->next_ = b
  
  
  
  
  其中，foo为一个操作head节点的作业，bar为一个中间操作shared var(head_)的作业。
  
  
  
  对与CAS产生的这个ABA的问题，通常的解决方案是采用CAS的一个变种DCAS。
  
  DCAS，是对于每一个shared var增加了一个引用的表示修改次数的标记符。对于每个shared var，如果引用修改了一次，这个计数器就增加一个。然后在这个变量需要update的时候，就同时检查变量的值和计数器的值。
  
  
  
  DCAS的伪代码如下：
  
  DCAS(A1,A2,B1,B2,C1,C2)
  
  BEGIN ATOMIC
  
  if ((A1==B1) && (A2==B2)) { A1=C1; A2=C2; return TRUE; }
  
  else { return FALSE; }
  
  END ATOMIC
  
  
  
  另外，还有NON-BLOCKING LINK LIST及其改进算法，不扯远了。如果想继续研究，请找University of Manitoba, Canada的一篇叫做“MANAGING LONG LINKED LISTS USING LOCK FREE TECHNIQUES”的论文。
  
  
  
  在handle table中，就定义了一个link list：
  
  EX_PUSH_LOCK HandleTableLock[HANDLE_TABLE_LOCKS]
  
  来防止在handle allocation的时候出现的ABA Problem。再看看这个结构体的定义，里面用了一个ActiveCount来标识引用了多少次：
  
  
  
  +1c struct _ERESOURCE HandleTableLock
  
  +1c struct _LIST_ENTRY SystemResourcesList
  
  +1c struct _LIST_ENTRY *Flink
  
  +20 struct _LIST_ENTRY *Blink
  
  +24 struct _OWNER_ENTRY *OwnerTable
  
  +28 int16 ActiveCount
  
  +2a uint16 Flag
  
  +2c struct _KSEMAPHORE *SharedWaiters
  
  +30 struct _KEVENT *ExclusiveWaiters
  
  +34 struct _OWNER_ENTRY OwnerThreads[2]
  
   uint32 OwnerThread
  
   int32 OwnerCount
  
   uint32 TableSize