Skip to content
graphviz-pure

fdp (C): cluster layouts depend on heap addresses and vary run to run

Kind
Upstream C behaviour
Severity
medium
Engine
fdp
Category
layout
Cases
3
Seeds
12476, 31247, 35776
Tracking
GitHub issuewon't fix
Labels
fidelityfuzzengine:fdpupstream-cwontfix

fdp's output for graphs with clusters can change from one C run to the next on the same machine. Derived graphs orient their edges and order their ports by node address, and macOS's allocator sometimes gives the freed nodes of one derived graph back to the next one and sometimes gives fresh addresses. On the reproducer C produced two different drawings in 20 runs (16 vs 4). The port has a deterministic allocator model and always produces the more frequent one.

Reproducer

graph "G" {
layout=fdp;
subgraph "cluster_2" {
"n6";
"n32" [fixedsize="false"];
}
subgraph "cluster_6" {
"n4";
"n30" [];
}
"n4" -- "n41";
"n4" -- "n13";
"n4" -- "n6":"_" [label="e=mc²", arrowtail="crow"];
}

GVBINDIR=<pango-free plugins> dot -Kfdp -Tsvg repro.gv   # C Graphviz 16.1.0
graphviz-pure -Kfdp -Tsvg repro.gv                              # port

C output vs port

Root cause

C compares Agnode_t * pointers in lib/fdpgen/layout.c:466 (if (hd > tl) when creating derived edges), :501 (if (dn > m) for port edges) and :634 (if (n < other) in genPorts, which sets the order and angles of a multi-edge's ports). An instrumented C build (GVDBG3=1) logs the derived nodes' addresses, and its output tracks their order exactly. On the reproducer, in 24 runs, the derived graph of cluster_6 got its nodes in the order n4, n30, port... 8 times (output A) and port, n30, n4, ... 16 times (output B), always matching the output. The port models the allocator in crates/graphviz-pure-layout/src/fdpgen/layout.rs:127-160 (NodeHeap: LIFO reuse of freed slots, then fresh increasing addresses) and orients by that model at layout.rs:607,637,740.

Why the port cannot match

C's result depends on heap addresses, which vary between runs, so no deterministic port can match every run. The port follows the allocation pattern C shows most often. On the reproducer and on seed 12476 that is C's most frequent output. Seeds 31247 and 35776 have 9 and 8 different C outputs in 20 runs, and the port matches one of them. For seed 12476 the two C variants differ only in one record text coordinate (22.62 vs 22.63); the address-dependent path was not traced for that seed. A fix would have to come from upstream: order derived nodes by ND_id/creation order instead of by pointer.

Cases

3 fuzz case(s), seeds 12476, 31247, 35776. Other fdp cases also vary run to run in C, but they also needed a port fix and are listed under that fix's issue. Regenerate one with python3 -I scripts/fuzz-gen.py --seed N (byte for byte for every seed listed here).

Files

tests/fuzz-open/025-fdp-cluster-address-dependent-layout

C and the port

Comparing…
C Graphviz 16.1.0 output, cyan plategraphviz-pure output, magenta plate

C onlyport onlyboth: in register

Reproduce

repro.gv
graph "G" {
layout=fdp;
subgraph "cluster_2" {
"n6";
"n32" [fixedsize="false"];
}
subgraph "cluster_6" {
"n4";
"n30" [];
}
"n4" -- "n41";
"n4" -- "n13";
"n4" -- "n6":"_" [label="e=mc²", arrowtail="crow"];
}
cmd.txt
-Kfdp -Tsvg
cases.txt
r2/diff/s12476.gv seed=12476
r4/diff/s31247.gv seed=31247
r4/diff/s35776.gv seed=35776

Files: c.1.svg, c.2.svg, c.svg, cases.txt, cmd.txt, repro.gv, rust.svg. Source: tests/fuzz-open/025-fdp-cluster-address-dependent-layout.

All open issues