idris-lang/Idris-dev — pull request #1602 by evanrinehart (2014-10-07 14:20:26+00:00)
Title: fix to some "obvious" bugs in BitsN primops

Ok, so many primops on 8, 16, 32, 64 bit machine words in the C runtime operate
by passing arg pointers to functions that begin by allocating a new VAL cell to
hold the result. If this allocation results in a GC collection then the
argument pointers may be pointing into the old heap, to a cell whose contents
has been overwritten with a forwarding pointer. While the collection algorithm
should update any references to these forwarding cells to the new cell, it
can't fixup the pointer you are holding onto right now "between instructions".

This bug happens when your operation is interrupted by the GC and you use the
forwarding pointer(s) as the arguments, resulting in incorrect results. This
would be hard to reproduce because it depends on the timing of the GC.

But the package idris-tf-random nonetheless can reproduce this if it runs long
enough, because it makes extensive use of BitsN operations. My canary program
at http://lpaste.net/112132 dumps the output of a Bits32 generator with a
static seed, but after a certain number of iterations (depending on GC timing)
the sequence will act differently from previous runs (depending on the value of
the forwarding pointers it is erroneously using). This commit makes the program
apparently deterministic again.

If you look at the GMP operations in rts/idris_gmp.c you will see in the
corresponding gmp ops, after the allocation of the result, the arguments are
retrieved using GETBIG which may follow this forwarding pointer.

Similarly I added four GETBITSN macros which either get these bits value
directly or get it from the forwarded VAL cell by testing if ty = FWD.
Operations in rts/idris_bitstring.c that do not do an allocation did not get
wrapped in this macro.

I'm planning to review GETBIG too, since it is recursive and the shortcut case
for INT (which does allocation) may suffer from this bug too.