Nim: Program SIGSEGV when using '--gc:orc'

Created on 27 Oct 2020 · 9Comments · Source: nim-lang/Nim

Program uses data structure with ref objects with cycles. I decided to recompile it with --gc:orc. Program works correctly with default GC but aborts with SIGSEGV: Illegal storage access. (Attempt to read from nil?) when compiled with --gc:orc.

Example

Program is composed of 2 files: sudoku.nim + dlx.nim
bug.zip

Current Output

 $ ./sudoku2 1
Problem:
P @ O @ @ @ S D @ @ @ J @ @ V L U @ Q @ @ Y A B @ 
M @ @ @ D G A @ @ @ @ I @ @ P C H F Y @ @ @ @ N V 
Y @ @ U @ @ @ @ @ @ T G A @ Q W @ @ B N @ @ L @ F 
@ @ X K @ @ @ @ V @ @ H @ @ @ I @ P @ @ @ O @ @ T 
S W F B @ @ U @ T J Y @ @ @ O @ @ @ A K C @ R @ @ 
@ H J @ @ A @ V X O @ U P @ B @ @ C M D W G N I @ 
@ @ @ @ T @ B @ H Q @ @ J @ @ G Y A @ @ @ M @ U S 
K D @ @ @ @ @ M @ @ @ @ @ @ F @ X @ @ U @ @ Q @ @ 
G @ @ @ B J C W E N R V S @ D K T @ @ @ O @ @ @ @ 
I @ L @ @ K @ @ @ R @ C M @ @ @ N J @ @ T @ E @ Y 
X @ H M @ D @ R @ @ B @ O N @ J @ @ T @ @ Q C @ @ 
B @ @ L C @ @ S @ X @ Y V @ @ @ @ G @ @ M @ I @ D 
@ O G I @ @ @ T @ @ U @ C @ X @ @ H @ @ @ E F P @ 
V @ Y @ W @ @ P @ @ @ @ H D @ X @ U @ @ G A @ @ J 
@ @ R N @ @ G @ @ I @ L K @ A @ @ Q @ S @ U V @ W 
C @ N @ K @ @ B D @ @ @ I F @ S @ @ @ R @ @ X @ U 
@ @ @ @ J @ @ @ C T D @ X B S F Q K V H I @ @ @ N 
@ @ T @ @ M @ @ J @ C @ @ @ @ @ @ L @ @ @ @ @ R B 
U V @ Y @ @ @ F S A @ @ L @ @ M W @ I @ J @ @ @ @ 
@ L P X O I R N @ @ V @ Y E @ U C D @ B @ @ W S @ 
@ @ D @ M X I @ @ @ H @ @ @ R Q K @ G @ @ C U J A 
R @ @ J @ @ @ A @ U @ @ @ C @ @ L @ @ @ @ S T @ @ 
H @ K @ @ Y E @ @ B G @ Q P J @ @ @ @ @ @ V @ @ O 
O A @ @ @ @ K G M V L @ @ X @ @ @ @ U J F @ @ @ P 
@ F V Q @ @ H @ P D N @ @ T @ @ @ O E @ @ @ K @ I 

Traceback (most recent call last)
.../bug/sudoku2.nim(495) sudoku2
.../bug/dlx.nim(472) initDLX
.../bug/dlx.nim(452) createDLXList
.../bug/dlx.nim(215) newDancingNode
.../bug/dlx.nim(203) newDancingNode
.../.choosenim/toolchains/nim-#head/lib/system/arc.nim(85) nimNewObj
.../.choosenim/toolchains/nim-#head/lib/system/alloc.nim(958) alloc0
.../.choosenim/toolchains/nim-#head/lib/system/alloc.nim(955) alloc
.../.choosenim/toolchains/nim-#head/lib/system/alloc.nim(787) rawAlloc
SIGSEGV: Illegal storage access. (Attempt to read from nil?)

Expected Output

$ ./sudoku2 1
Problem:
P @ O @ @ @ S D @ @ @ J @ @ V L U @ Q @ @ Y A B @ 
M @ @ @ D G A @ @ @ @ I @ @ P C H F Y @ @ @ @ N V 
Y @ @ U @ @ @ @ @ @ T G A @ Q W @ @ B N @ @ L @ F 
@ @ X K @ @ @ @ V @ @ H @ @ @ I @ P @ @ @ O @ @ T 
S W F B @ @ U @ T J Y @ @ @ O @ @ @ A K C @ R @ @ 
@ H J @ @ A @ V X O @ U P @ B @ @ C M D W G N I @ 
@ @ @ @ T @ B @ H Q @ @ J @ @ G Y A @ @ @ M @ U S 
K D @ @ @ @ @ M @ @ @ @ @ @ F @ X @ @ U @ @ Q @ @ 
G @ @ @ B J C W E N R V S @ D K T @ @ @ O @ @ @ @ 
I @ L @ @ K @ @ @ R @ C M @ @ @ N J @ @ T @ E @ Y 
X @ H M @ D @ R @ @ B @ O N @ J @ @ T @ @ Q C @ @ 
B @ @ L C @ @ S @ X @ Y V @ @ @ @ G @ @ M @ I @ D 
@ O G I @ @ @ T @ @ U @ C @ X @ @ H @ @ @ E F P @ 
V @ Y @ W @ @ P @ @ @ @ H D @ X @ U @ @ G A @ @ J 
@ @ R N @ @ G @ @ I @ L K @ A @ @ Q @ S @ U V @ W 
C @ N @ K @ @ B D @ @ @ I F @ S @ @ @ R @ @ X @ U 
@ @ @ @ J @ @ @ C T D @ X B S F Q K V H I @ @ @ N 
@ @ T @ @ M @ @ J @ C @ @ @ @ @ @ L @ @ @ @ @ R B 
U V @ Y @ @ @ F S A @ @ L @ @ M W @ I @ J @ @ @ @ 
@ L P X O I R N @ @ V @ Y E @ U C D @ B @ @ W S @ 
@ @ D @ M X I @ @ @ H @ @ @ R Q K @ G @ @ C U J A 
R @ @ J @ @ @ A @ U @ @ @ C @ @ L @ @ @ @ S T @ @ 
H @ K @ @ Y E @ @ B G @ Q P J @ @ @ @ @ @ V @ @ O 
O A @ @ @ @ K G M V L @ @ X @ @ @ @ U J F @ @ @ P 
@ F V Q @ @ H @ P D N @ @ T @ @ @ O E @ @ @ K @ I 


Solution #1:
P C O G H F S D I K X J N W V L U R Q T E Y A B M 
M T Q R D G A X L E S I B K P C H F Y O U W J N V 
Y J E U V C O H R P T G A M Q W S X B N D I L K F 
A N X K L B M Y V W F H R U C I J P D E Q O S G T 
S W F B I N U Q T J Y D E L O V G M A K C P R X H 
E H J S Y A T V X O K U P Q B R F C M D W G N I L 
N R C F T P B I H Q E X J O L G Y A W V K M D U S 
K D W O P S L M Y G A N T I F B X E H U R J Q V C 
G U M A B J C W E N R V S Y D K T I L Q O H P F X 
I Q L V X K D U F R W C M G H O N J S P T B E A Y 
X E H M A D Y R U F B P O N G J V W T I S Q C L K 
B K U L C O J S W X Q Y V R T E P G F A M N I H D 
J O G I Q V N T A M U W C S X D B H K L Y E F P R 
V S Y T W L Q P K C I F H D E X R U N M G A B O J 
D P R N F H G E B I M L K J A Y O Q C S X U V T W 
C G N H K E V B D L J Q I F W S A Y O R P T X M U 
W M A E J U P O C T D R X B S F Q K V H I L G Y N 
Q I T D S M W K J Y C O G A U N E L P X V F H R B 
U V B Y R Q X F S A P K L H N M W T I G J D O C E 
F L P X O I R N G H V T Y E M U C D J B A K W S Q 
T Y D P M X I L O S H E F V R Q K B G W N C U J A 
R B I J N W F A Q U O M D C K P L V X Y H S T E G 
H X K W U Y E C N B G A Q P J T I S R F L V M D O 
O A S C E T K G M V L B W X I H D N U J F R Y Q P 
L F V Q G R H J P D N S U T Y A M O E C B X K W I 

Solution verified to be correct!

Possible Solution

Stay with default GC for the moment...

Additional Information

$ nim -v
Nim Compiler Version 1.5.1 [Linux: amd64]
Compiled at 2020-10-27
Copyright (c) 2006-2020 by Andreas Rumpf

git hash: 3bdc0005211b0d543e0ff48ccf6bc5a9f2a2a30b
active boot switches: -d:release
```

ARORC Showstopper

Source

pmetras

Most helpful comment

@Araq this is what I reduced it to, needs to be run with -d:nimStressOrc. Seems to be very sensitive to rootsThreshold, so this seems to only crash with rootsThreshold = 10 (as with nimStressOrc)

type
  NodeKind = enum
    nkDancing,
    nkColumn

  DancingNode = ref object
    right, top, bottom: DancingNode
    column: DancingNode
    case kind: NodeKind
    of nkDancing, nkColumn:
      discard


proc newColumnNode(): DancingNode =
  result = DancingNode(kind: nkColumn)
  result.right = result
  result.top = result
  result.bottom = result
  result.column = result

proc createDLXList(): DancingNode =
  result = newColumnNode()
  var columnNodes: seq[DancingNode] = @[]

  template initWeird() =
    let n = newColumnNode()
    columnNodes.add(n)
    n.right = result.right
    result = n

  for i in 0 .. 7:
    initWeird()

  template weirdCycles(col: DancingNode) = 
    let newNode = DancingNode(kind: nkDancing)
    newNode.bottom = newNode # !!!! works without this line
    newNode.bottom = col.top.bottom
    newNode.bottom.top = newNode

  let col1 = columnNodes[0]
  let col2 = columnNodes[1]
  # hand-unrolled simplified loop...
  weirdCycles(col1)
  weirdCycles(col2)
  weirdCycles(col2)

var dlxlist = createDLXList()

Yardanico on 6 Nov 2020

🚀1 👍1

All 9 comments

Please try to compile with --cursorInference:off --sinkInference:off and let us know if it works this way.

cooldome on 28 Oct 2020

Same crash behaviour:

$ nim c --gc:orc --cursorInference:off --sinkInference:off sudoku2.nim 
...
 $ ./sudoku2 1
...
Traceback (most recent call last)
.../bug/sudoku2.nim(495) sudoku2
.../bug/dlx.nim(472) initDLX
.../bug/dlx.nim(452) createDLXList
.../bug/dlx.nim(215) newDancingNode
.../bug/dlx.nim(203) newDancingNode
.../.choosenim/toolchains/nim-#head/lib/system/arc.nim(85) nimNewObj
.../.choosenim/toolchains/nim-#head/lib/system/alloc.nim(958) alloc0
.../.choosenim/toolchains/nim-#head/lib/system/alloc.nim(955) alloc
.../.choosenim/toolchains/nim-#head/lib/system/alloc.nim(787) rawAlloc
SIGSEGV: Illegal storage access. (Attempt to read from nil?)

pmetras on 28 Oct 2020

What is strange is that the program can be compiled in two modes, depending on the value of the ALPHA constant. When ALPHA = true, it works on 25x25 alphabetic sudokus while when ALPHA = false it does with 9x9 numeric sudokus. I can't make the program crash on the numeric ones.

The ALPHA constant is only used as a switch to initialize other constant values:

when ALPHA:
  # 25x25 alphabetic Sudoku
  const
    SIZE = 25
    EMPTY = '@'
    MAX_VALUE = 'Y'
    MIN_VALUE = 'A'
    BOX = int(sqrt(float(SIZE)))
    NB_VALUES = ord(MAX_VALUE) - ord(MIN_VALUE) + 1
else:
  # 9x9 numeric Sudoku
  const
    SIZE = 9
    EMPTY = 0
    MAX_VALUE = 9
    MIN_VALUE = 1
    BOX = int(sqrt(float(SIZE)))
    NB_VALUES = MAX_VALUE - MIN_VALUE + 1

As a consequence, it changes the Value type from int to char but it should not influence the change in behaviour.

Another particularity of the DancingNode data structure is that it creates references to itself in the left, right, top and bottom fields when it is initialized, instead of having default nil values.

DancingNode = ref object
    left, right, top, bottom: DancingNode

Could it be that orc cycles detector does not like self-cycles?

And I just tried compiling with arc: the program executes correctly, even if the compilation reports numerous cycle detected!

$ nim c --gc:arc sudoku2
Hint: used config file '.../.choosenim/toolchains/nim-#head/config/nim.cfg' [Conf]
Hint: used config file '.../.choosenim/toolchains/nim-#head/config/config.nims' [Conf]
....................
.../bug/sudoku2.nim(454, 62) Warning: Cannot prove that 'value' is initialized. This will become a compile time error in the future. [ProveInit]
.../bug/dlx.nim(227, 15) Warning: 'result.left = result' creates an uncollectable ref cycle; annotate 'left' with .cursor [CycleCreated]
.../bug/dlx.nim(228, 16) Warning: 'result.right = result' creates an uncollectable ref cycle; annotate 'right' with .cursor [CycleCreated]
.../bug/dlx.nim(229, 14) Warning: 'result.top = result' creates an uncollectable ref cycle; annotate 'top' with .cursor [CycleCreated]
.../bug/dlx.nim(230, 17) Warning: 'result.bottom = result' creates an uncollectable ref cycle; annotate 'bottom' with .cursor [CycleCreated]
.../bug/dlx.nim(231, 17) Warning: 'result.column = result' creates an uncollectable ref cycle; annotate 'column' with .cursor [CycleCreated]
.../bug/dlx.nim(258, 20) Warning: 'node2.right.left = node2' creates an uncollectable ref cycle; annotate 'right' with .cursor [CycleCreated]
.../bug/dlx.nim(204, 15) Warning: 'result.left = result' creates an uncollectable ref cycle; annotate 'left' with .cursor [CycleCreated]
.../bug/dlx.nim(205, 16) Warning: 'result.right = result' creates an uncollectable ref cycle; annotate 'right' with .cursor [CycleCreated]
.../bug/dlx.nim(206, 14) Warning: 'result.top = result' creates an uncollectable ref cycle; annotate 'top' with .cursor [CycleCreated]
.../bug/dlx.nim(207, 17) Warning: 'result.bottom = result' creates an uncollectable ref cycle; annotate 'bottom' with .cursor [CycleCreated]
.../bug/dlx.nim(243, 20) Warning: 'node2.bottom.top = node2' creates an uncollectable ref cycle; annotate 'bottom' with .cursor [CycleCreated]
.../bug/dlx.nim(309, 19) Warning: 'node.top.bottom = node' creates an uncollectable ref cycle; annotate 'top' with .cursor [CycleCreated]
.../bug/dlx.nim(310, 19) Warning: 'node.bottom.top = node' creates an uncollectable ref cycle; annotate 'bottom' with .cursor [CycleCreated]
.../bug/dlx.nim(284, 19) Warning: 'node.left.right = node' creates an uncollectable ref cycle; annotate 'left' with .cursor [CycleCreated]
.../bug/dlx.nim(285, 19) Warning: 'node.right.left = node' creates an uncollectable ref cycle; annotate 'right' with .cursor [CycleCreated]
CC: stdlib_system.nim
CC: stdlib_strutils.nim
CC: dlx.nim
CC: sudoku2.nim
Hint:  [Link]
Hint: 45259 lines; 1.256s; 61.059MiB peakmem; Debug build; proj: .../bug/sudoku2; out: .../bug/sudoku2 [SuccessX]

pmetras on 28 Oct 2020

Hmm, a self cycle is usually the first test case I come up with but sure, it's possible, we'll see.

Araq on 29 Oct 2020

This is a most subtle bug, please reduce this test program as much possible.

Araq on 2 Nov 2020

Trying to reduce the test program makes the bug disappear as it is the case when I set the ALPHA constant to false. The program does not crash too when compiled with nim c --gc:orc -d:useMalloc sudoku2, though valgrind is not happy...

pmetras on 6 Nov 2020

I'll try to reduce the test case, doesn't seem to be too hard

Yardanico on 6 Nov 2020

type
  NodeKind = enum
    nkDancing,
    nkColumn

  DancingNode = ref object
    right, top, bottom: DancingNode
    column: DancingNode
    case kind: NodeKind
    of nkDancing, nkColumn:
      discard


proc newColumnNode(): DancingNode =
  result = DancingNode(kind: nkColumn)
  result.right = result
  result.top = result
  result.bottom = result
  result.column = result

proc createDLXList(): DancingNode =
  result = newColumnNode()
  var columnNodes: seq[DancingNode] = @[]

  template initWeird() =
    let n = newColumnNode()
    columnNodes.add(n)
    n.right = result.right
    result = n

  for i in 0 .. 7:
    initWeird()

  template weirdCycles(col: DancingNode) = 
    let newNode = DancingNode(kind: nkDancing)
    newNode.bottom = newNode # !!!! works without this line
    newNode.bottom = col.top.bottom
    newNode.bottom.top = newNode

  let col1 = columnNodes[0]
  let col2 = columnNodes[1]
  # hand-unrolled simplified loop...
  weirdCycles(col1)
  weirdCycles(col2)
  weirdCycles(col2)

var dlxlist = createDLXList()

Yardanico on 6 Nov 2020

🚀1 👍1

Further reduced:

type
  NodeKind = enum
    nkDancing,
    nkColumn

  DancingNode = ref object
    right: DancingNode
    column: DancingNode
    kind: NodeKind

proc newColumnNode(): DancingNode =
  result = DancingNode(kind: nkColumn)
  result.right = result
  result.column = result

proc createDLXList(): DancingNode =
  result = newColumnNode()

  for i in 0 .. 10:
    stderr.write "A\n"
    let n = newColumnNode()
    stderr.write "B\n"
    stderr.write "C\n"
    n.right = result.right # <-- Problem!!
    stderr.write "D\n"
    result = n
    stderr.write "E\n"

var dlxlist = createDLXList()

Araq on 13 Nov 2020

👍1

Was this page helpful?

0 / 5 - 0 ratings