It is similar to the cmpxchg, but it compares and swaps full 8 bytes in one go! // lock cmpxchg8b //Now try to xchgĬmpxchg8b compares combination of edx and eax registers with its operand. mov ebx, //ebx := Result.Nextįinally, we can use cmpxchg8b instruction to do the swap. First we need an address of the second node in the ebx register. Now we're getting ready for the pointer swap. inc ecx //Now we are ready to cmpxchg8b mov eax, //eax := chain.Headīecause of the same reason there is no guarantee that chainSpin is indeed equal to spinRef+1 so this is now checked for. Another thread may have been invoked between those two movs and it could call PopLink on the same chain and modify the header. This is a non-atomic fetch and doesn't guarantee that both values really belong to the same state of the chain record. Then we fetch current chain.Head and chain.Spin and store them into the Result ( eax) and chainSpin ( edx), respectively. Xadd instructions stores first operand (, which equals to chain.Spin) into the second operand ( ecx) and sum of both operands (original value of the second operand is used for summation) into the first operand. mov ecx, 1 //Increment spin reference for 1 With a little help of locked xadd, current version of the header spin value is loaded into the spinRef ( ecx register) and is incremented in the header. In the beginning, a little housekeeping is done (two registers stored away because Delphi compiler expects us not to modify them) and address of the chain record is loaded into the edi register. If (Result = chain.Head) and (chainSpin = chain.Spin) then begin lock xadd, ecx //Get old spin reference to ecx mov edi, eax //edi = mov ecx, 1 //Increment spin reference for 1 class function TOmniBaseContainer.PopLink( var chain: TOmniHeadAndSpin): POmniLinkedData I'll write an approximation of the PopLink in Delphi. Also, the code is much longer and not very easy to understand, so I'll try the trick that helped in the previous installment. That made more sense as it needs no information from the class - it only works on a chain, which is passed as a parameter. You may have noticed that this is now a class function (a class static function, to be more precise). Lock xadd, ecx //Get old spin reference to ecx Mov ecx, 1 //Increment spin reference for 1 (Of course, assembler is still provided by the ‘GJ’, I had nothing to do with it.) class function TOmniBaseContainer.PopLink( var chain: TOmniHeadAndSpin): POmniLinkedData This is the new version in all its glory. typeĪs the problem lied in the PopLink method, we'll start today's exploration just there. This second part will make sure that the ABA problem cannot occur. Instead of containing only a pointer to the first node, each chain head is now composed of two parts - a pointer to the first node and a 4-byte spin count. That's exactly what was done in the OTL, except that we didn't use just few measly bits, but a 4-byte counter. You can read more about it in the Wikipedia, where you'll also learn that ABA problem is commonly solved by adding ‘tag’ bits. In the initial implementation lied an excellent example of the ABA problem. I've also mentioned that the problem was fixed in the meantime and that the working implementation is already available in the repository and as a snapshot, but I haven't said a word about the new implementation. You've learned how the lock-free stack was implemented in the first place and which problem was hidden in that implementation. This is the third post in the mini-series on a lock-free stack, included in the OmniThreadLibrary.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |