mirror of
https://github.com/nim-lang/Nim.git
synced 2026-08-01 04:59:05 +00:00
85 lines
2.8 KiB
Nim
85 lines
2.8 KiB
Nim
discard """
|
|
cmd: "nim c --mm:yrc -d:useMalloc --threads:on $file"
|
|
output: "ok"
|
|
disabled: "windows"
|
|
disabled: "freebsd"
|
|
disabled: "openbsd"
|
|
"""
|
|
|
|
# Deterministic port of dumpster's `fuzz` test
|
|
# (https://claytonwramsey.com/blog/dumpster/): drive a mutable object graph
|
|
# through a long random sequence of node/edge inserts and removals, then drop
|
|
# every root and assert that *every allocation ever made is destroyed exactly
|
|
# once* -- no leak (count 0) and no double free (count > 1). The graph grows
|
|
# thick with overlapping and self cycles, so only the cycle collector can wind
|
|
# it down. A fixed LCG seed makes the shape reproducible across runs.
|
|
|
|
type
|
|
DropCount = object
|
|
id: int
|
|
live: bool # false in any moved-from temporary -> never miscounts
|
|
Node = ref object
|
|
refs: seq[Node]
|
|
dc: DropCount
|
|
|
|
var counts: seq[int] # counts[id] == times allocation `id` was destroyed
|
|
|
|
proc `=destroy`(x: DropCount) =
|
|
if x.live: inc counts[x.id]
|
|
|
|
var nextId = 0
|
|
proc newNode(): Node =
|
|
counts.add 0
|
|
result = Node(refs: @[], dc: DropCount(id: nextId, live: true))
|
|
inc nextId
|
|
|
|
# `child` is a by-value borrow (dumpster's `Gc::clone`): storing it copies the
|
|
# reference, leaving the caller's root slot still owning. Using `.refs.add`
|
|
# directly would move the root at its last read and change the graph shape.
|
|
proc link(parent, child: Node) = parent.refs.add child
|
|
|
|
# Small fixed-seed LCG (Numerical Recipes constants) for reproducible shape.
|
|
var rngState: uint32 = 12345
|
|
proc rnd(n: int): int =
|
|
rngState = rngState * 1664525'u32 + 1013904223'u32
|
|
int((rngState shr 16) mod uint32(n))
|
|
|
|
proc run =
|
|
const N = 20_000
|
|
var roots: seq[Node]
|
|
for i in 0 ..< 50: roots.add newNode()
|
|
|
|
for _ in 0 ..< N:
|
|
if roots.len == 0: roots.add newNode()
|
|
case rnd(4)
|
|
of 0: # allocate a fresh root
|
|
roots.add newNode()
|
|
of 1: # add edge from -> to (may self-loop)
|
|
let a = rnd(roots.len)
|
|
let b = rnd(roots.len)
|
|
link(roots[a], roots[b])
|
|
of 2: # drop a root handle (swap-remove)
|
|
let i = rnd(roots.len)
|
|
roots[i] = roots[roots.high]
|
|
roots.setLen roots.len - 1
|
|
else: # drop one outgoing edge of a root
|
|
let a = rnd(roots.len)
|
|
if roots[a].refs.len > 0:
|
|
let j = rnd(roots[a].refs.len)
|
|
roots[a].refs[j] = roots[a].refs[roots[a].refs.high]
|
|
roots[a].refs.setLen roots[a].refs.len - 1
|
|
|
|
roots.setLen 0 # release every remaining root
|
|
GC_fullCollect()
|
|
GC_fullCollect()
|
|
|
|
run()
|
|
|
|
var missing = 0
|
|
for id in 0 ..< nextId:
|
|
if counts[id] != 1:
|
|
inc missing
|
|
doAssert missing == 0, "graph not fully reclaimed: " & $missing & " of " &
|
|
$nextId & " allocations leaked or double-freed"
|
|
echo "ok"
|