Computer Sciences Department

University of Wisconsin-Madison

R&D Engineer at VMware

December 2008; updated January 2009

`http://www.cs.wisc.edu/~markhill/racey.html`

This page links to a C program called

.
**RACEY**

is useful for testing methods for deterministic
execution or record/reply.
**RACEY**

computes a signature whose value
is exceedingly sensitive to the order of unsynchronized data races.
On a non-deterministic system, each of tens of thousands of **RACEY**

runs produces a unique signature value.
**RACEY**

To test an allegedly deterministic system,
run

so that the instructions of multiple threads
run concurrently.
Repeat many times and, if possible, intentionally perturb
execution timing.
If **RACEY**

ever produces different
signature values, then the system is non-deterministic.
If **RACEY**

repeatedly produces the same
signature value, your system **RACEY***may be* deterministic.

The kernel of

uses
a multiplicative congruential pseudo-random number generator [Knu]
named **RACEY**

:
**mix()**

Each thread races with other concurrent threads to:#define PRIME1 103072243 #define PRIME2 103995407 unsigned mix(unsigned i, unsigned j) { return (i + j * PRIME2) % PRIME1; }

- take its component of a signature

,**sig[threadId]** -

values in an integer array**mix**

(padded to have one element per cache block),**m[...].value** - obtain a new

,**sig[threadId]** - and repeat many times.

#define MAX_LOOP 1000 #define MAX_ELEM 64 for(i = 0 ; i < MAX_LOOP; i++) { unsigned num = sig[threadId]; unsigned index1 = num%MAX_ELEM; unsigned index2; num = mix(num, m[index1].value); index2 = num%MAX_ELEM; num = mix(num, m[index2].value); m[index2].value = num; sig[threadId] = num; }

Since

is exceedingly NON-associative, any reordering
of conflicting accesses (reads/writes or writes/writes) will
change the final signature value with high probability.
**mix()**

was developed in 2002 to test the
**RACEY***Flight Data Recorder* [FDR]. It was written by Min Xu, then a
Ph.D. student at Wisconsin. It is based on ideas of Prof. Mark D. Hill
with number theory advice from Prof. Eric Bach, both at Wisconsin.

We hereby offer

as public domain software.
To download **RACEY**

, click:
**racey.c**

- Slightly updated 2009 code (recommended, e.g., compiles under linux)
- Original 2002 code

**References**

[FDR] Min Xu, Rastislav Bodik and Mark D. Hill, A "Flight Data Recorder" for Enabling Full-system Multiprocessor Deterministic Replay, International Symposium on Computer Architecture (ISCA), June 2003.

[HX] Mark D. Hill and Min Xu, Racey: A Stress Test for Deterministic Execution, web page: http://www.cs.wisc.edu/~markhill/racey.html.

[Knu] Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, third edition, 1997.