Re: [boost] Re: Threads: Atomic Counter

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-08-31 23:20:05

From: Valentin Bonnard <Bonnard.V_at_[hidden]>
> On Thu, Aug 31, 2000 at 12:30:22PM -0400, David Abrahams wrote:
> > 
> > From: "William Kempf" <sirwillard_at_[hidden]>
> > > > The following Win32 functions don't work right on Win95:
> > > >
> > > > InterlockedCompareExchange
> > > > InterlockedCompareExchangePointer
> > > > InterlockedExchangeAdd
> > >
> > > But they do on Win98.  Tricky issue here.  I included the
> > > compare_exchange() only to bring up debate about its usefulness.
> > > I've never found a need for them, but didn't want to eliminate them
> > > just because I've never needed them, nor because Win95 didn't support
> > > them.  Obviously they can be added to Win95 in the form of some
> > > assembler instructions.
> > 
> > Just an additional data point: if I remember correctly, the Motorola 680x0,
> > where x > 2, includes atomic instructions for linking list elements in/out
> > of singly- and doubly-linked lists! These are called something like
> > "Atomic-compare-and-exchange" IIRC.
> 
> Insert in singly linked list:
> 
> inserted->next = pos->next;
> pos->next = inserted;
> 
> This can't be done atomically, even which get_and_set (but each assignment 
> can be done atomically)
> 
> 
> Remove from singly linked list:
> 
> // at this point removed_prev.next == removed
> removed_prev->next = removed->next;
> 
> MOVE (next,removed), (next,removed_prev)
> 
> (Atomic on every 68k)
> 
> 
> Remove from doubly linked list:
> 
> removed->prev->next = removed->next;
> removed->next->prev = removed->prev;
> 
> IMO this can't be done atomically (but each assignment can be done
> atomically).

I looked in my 68020 manual and couldn't figure out how to
do it either, but there maybe a trick I don't know.

Here is how I once did it for a singly-linked list with
compare/exhange for an x86 memory manager:

   static inline MemCell* PopFreeCell(MemCell** ppFree) 
   {
      // while free list available spin until free cell is obtained
      _asm {
         mov            edi,     ppFree
         mov            eax,     [edi]
      spin:
         test           eax,      eax
         jz             done
         mov            esi,     [eax]
         lock cmpxchg   [edi],   esi
         jnz            spin
      done:
      }
   }

   static inline void PushFreeCell(MemCell** ppFree,void* p) 
   {
      // spin until cell put at head of free list
      _asm {
         mov            edi,     ppFree
         mov            eax,     [edi]
         mov            esi,     p      
      spin:
         mov            [esi],   eax
         lock cmpxchg   [edi],   esi
         jnz            spin  
      }
   }

The VAX has some instructions for the purpose as well.