Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Atomic Linked List Insert for Power-PC Multi-Processor with Large Reservation Granules

IP.com Disclosure Number: IPCOM000114335D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 4 page(s) / 65K

Publishing Venue

IBM

Related People

Kirke, WA: AUTHOR [+3]

Abstract

Disclosed is a technique for an atomic insertion into a linked list on a multiprocessor system. The ldarx (load and reserve) and stdcx (store conditional) instructions are used to serialize updates. The absence of stores between the ldarx and stdcx prevents live-lock even with large reservation granules.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Atomic Linked List Insert for Power-PC Multi-Processor with Large
Reservation Granules

      Disclosed is a technique for an atomic insertion into a linked
list on a multiprocessor system.  The ldarx (load and reserve) and
stdcx (store conditional) instructions are used to serialize updates.
The absence of stores between the ldarx and stdcx prevents live-lock
even with large reservation granules.

      In practice, the ldarx instruction creates a reservation on a
range of addresses (reservation granule) which is much larger than
the one doubleword updated by the stdcx instruction.  A store by
another processor to any location within the reservation granule will
cancel the reservation and cause the stdcx to fail.  To prevent the
possibility of live-lock due to two tasks perpetually cancelling each
other's reservations, a task must not execute any other stores
between a ldarx and stdcx.

      Insertion of an object at the head of a linked list requires
two stores, one to update the link pointer in the new object and one
to update the list's head pointer.  The head pointer update must be
done using ldarx/stdcx to guarantee serialization.  The procedure
shown below performs an atomic list insertion with no danger of
live-lock by removing all stores from inside the ldarx/stdcx loop.

      The list head pointer is copied, without a reservation, to the
object link pointer (Fig. 1).  Then the list head pointer is
re-loaded, this time using a ldarx instruction, and compared to the
value that was stored in the object.  If the old and current value of
the list head p...