827
100%
master: 100%

Ran 12 Jun 2015 10:49PM UTC

Jobs 2

Files 114

Run time 2min

Badge

Embed ▾

pending completion

Build # 827

Build Type

push

travis-ci

Committed by

mossblaser

Commit Message

Fix infinite loop in NER routing algorithm.

In the initial route-generating code, the NER routing algorithm had a bug meant
that new routes could be inserted into a routing tree which overlapped existing
tree segments sometimes resulting in cycles being added to the routing tree.
These cycles would then cause later stages of the algorithm to get stuck in an
infinite loop.

To resolve the bug, new route segments are truncated at the first point they
come into contact with the rest of the routing tree. A fuzzing test designed to
maximise the chances of similar bugs being manifested has been added. This test
reliably finds the above bug when the fix is reverted.

Note that though this bug is severe it requires very peculiar nets to manifest
itself. In particular to make the bug likely to manifest, nets must be extremely
high fan-out (but *not* connect to all chips) and the pattern must be such that
NER ends up inserting highly serpentine routes. As such most applications are
likely not to encounter this bug in normal operation.

This commit also fixes a test which failed to account for some legal hops in
routes (found by the fuzzing test).

Run Details

9850 of 9850 relevant lines covered (100.0%)

1.46 hits per line

Jobs

ID	Job ID	Ran	Files	Coverage
1	827.1	12 Jun 2015 10:49PM UTC	0	100.0	Travis Job 827.1
2	827.2	12 Jun 2015 10:51PM UTC	0	100.0	Travis Job 827.2

Source Files on build 827

Detailed source file information is not available for this build.

project-rig / rig / 827
100%
master: 100%

README BADGES
x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 827

project-rig / rig / 827 100% master: 100%

README BADGES x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 827

project-rig / rig / 827
100%
master: 100%

README BADGES
x