project-rig / rig

100%

master: 100%

LAST BUILD ON BRANCH router-infinate-loop-fix

branch: router-infinate-loop-fix

CHANGE BRANCH

x

Reset

• router-infinate-loop-fix
• __ne__
• add-free-commands
• add_coveralls
• alloc_and_clear
• app-stop
• better-dependency-checking
• bitfield-get-tags
• bitfield-subclassing
• bitfield_namespacing
• bmp-power-on-bug-workaround
• bmp_support
• board-geometry-functions
• boot-parameters
• bugfix-same-chip-constraint
• bugfix_open_aplx_read_only
• ci_hardware_support
• coalesced-writes
• coalesced-writes-simpler-buffer
• common-signals
• contexts-all-arguments
• contexts-can-set-all-arguments
• count-cores-in-states
• development-docs
• doc-neaten
• doc-seek-fix
• documentation-improvements
• even-faster-scp-rw
• even-faster-scp-rw2
• even-faster-scp-rw2-select
• faster-app-load
• faster-rw
• faster-scp-rw
• fault-tollerant-rig-ps
• find-a-board
• fix-#116
• fix-#133
• fix-#149
• fix-#35
• fix-#37
• fix-#47
• fix-#48
• fix-#51
• fix-#56
• fix-#57
• fix-90
• fix-a-star-return-type
• fix-across-link-tests
• fix-buffering
• fix-build-routing-tables
• fix-doc-function-signatures
• fix-expand-entry
• fix-live-get_machine-test
• fix-load_routing_tables-cross-ref
• fix-minimisation-bug
• fix-nondeterminism-in-c-kernel
• fix-pypi-bad
• fix-pypi-badge
• fix-readme
• fix-routing-table-entry-str
• fix-scamp-app-stop
• fix-system-info-docs
• fix-timestamps
• fix-to-float
• fix_2x2_from_vector
• fix_34
• fix_bitfield_edgecase
• fix_vcpu_struct1
• fix_vcpu_struct2
• fixes_from_the_past
• flake8
• flood-fill-core-select
• full_test_coverage
• get_location_and_length
• high-throughput-io
• hpsr-2016
• improve-memoryio
• indeterminate_numpy_python_os_fix
• iobuf
• link-read-write
• machine-relative-comparison
• machine_control_docs
• make-sa-callback-test-deterministic
• master
• mindless-changes
• minimize-in-out-pairs
• missing_file
• multiple-ethernet
• multisource_nets_option_3
• naive-placement-refactor
• neaten-region-tree
• ner_dead_code_removal
• new_makefile
• no-np
• no-py33
• nonblocking-io
• np-fix
• only-use-idle-cores
• optimise_interpreter_performance
• overview-docs
• processor_status
• pure_vanity
• pypi-desc
• pypi-desc-2
• pytest-flake8
• random-placer
• real-ints-from-geometry-functions
• reduce_debug
• remove-regions
• remove-slots
• rename-util-to-utils
• rename_keyspace
• requirements-docs-enum-compat
• rig-boot-num-boards
• rig-commands
• rig-counters
• rig-scripts-docs-polish
• rig_sa
• routes-metadata
• routing-table-tools
• routing-tree-fix
• rtr_diag
• same-chip-constraint
• scp_refactor2
• sdram-alloc
• sdram-alloc-error-msg
• simplify-scp-packet
• simplify-scp-packet-fix-docs
• simulated_annealing
• smarter-boot
• stringy-signals
• subscript-memoryio
• test-tag
• travis-flake8
• travis-py35
• typecast-docs
• update-current-context
• update-oc
• v0.0.2.dev
• v0.1.0.dev
• v0.1.1.dev
• v0.1.2
• v0.1.3
• v0.1.4
• v0.1.5
• v0.10.0
• v0.10.1
• v0.11.0
• v0.11.1
• v0.12.1
• v0.12.2
• v0.13.0
• v0.13.1
• v0.13.2
• v0.13.3
• v0.13.4
• v0.14.0
• v0.2.0
• v0.2.1
• v0.2.2
• v0.2.3
• v0.3.0
• v0.3.1
• v0.4.0
• v0.5.0
• v0.5.1
• v0.5.2
• v0.5.3
• v0.5.4
• v0.5.5
• v0.5.6
• v0.6.1
• v0.6.2
• v0.6.3
• v0.6.4
• v0.7.0
• v0.8.0
• v0.8.1
• v0.8.2
• v0.9.0
• vanity-fix-2
• version_number_consistency
• wait-for-signals
• write-struct-fields

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