Multi-Word Compare-and-Swap on SBCL
Paul Khuong (pvk@pvk.ca)

December 14, 2009

(SB-)MCAS

I

http://www.discontinuity.info/~pkhuong/mcas/

I

Based on: “A Practical Multi-Word Compare-and-Swap
Operation”, Harris, Fraser & Pratt (2002)

I

“Atomic” CAS across an arbitrary set of locations

I

(Long-term) Goal: build a toolkit for lock-free [at the user’s
level] protocols

Why lock-free?

I

Safe

I

Stable

I

Hidden locks still ok?!

Interface

READ /place/
SCAS /place/ /old/ /new/

ITH-MCAS (&key /initial-size/ /plan-name/) /body.../
CAS /place/ /old/ &optional /new/
RUN
Liveness guaranteed!

And a DSL!

DO (/variables/*) (/value/*) /statement/*
EVAL /variable/ /form/
GET /variable/ /place/
CAS /place/ /old/ &optional /new/
GUARD /form/
FAIL
Easy to get livelocks

Chopping a circular double-linked list in two (almost)
(defun cut (from to)
"Cut the sub-list between (and including) from and to."
(declare (type 2list from to))
(loop
(multiple-value-bind (successp rest)
(mcas:do (left right) (left)
(mcas:get left (2list.left from))
(mcas:cas (2list.left from)
left to)
(mcas:get right (2list.right to))
(mcas:cas (2list.right to)
right from)
(mcas:cas (2list.right left) from right)
(mcas:cas (2list.left right) to
left))
(when successp
(return (values from rest))))))