[Olsr-dev] Bug in edge detection

[Hannes Gredler]

hi guys,

i have recently stumbled on a interesting problem that causes
quite some inefficiency wrt malloc churn() and SPF calculations.

it happens is when a TC message gets striped over two (or more) IP packets.
this is typically for a TC message at the MTU boundary of a OLSR packet.

e.g. the node 193.238.156.109 is advertising its neighbor set and only can
fit the header in IP packet #1.

because the edge detection granularity is bound to a TC message the input
parser thinks all neighbors are unreachable, deletes them and triggers
a SPF calculation.

Processing TC from 193.238.156.109, seq 0x9a6d
TC: del edge entry 193.238.156.109 -> 193.238.158.5, etx 1.000, neigh-etx 1.000
TC: del edge entry 193.238.156.109 -> 193.238.159.15, etx 1.000, neigh-etx 1.000
TC: del edge entry 193.238.156.109 -> 193.238.156.23, etx 0.055, neigh-etx 0.278
TC: del edge entry 193.238.156.109 -> 193.238.156.63, etx 0.557, neigh-etx 0.267
TC: del edge entry 193.238.156.109 -> 193.238.156.113, etx 1.000, neigh-etx 1.000
TC: del edge entry 193.238.156.109 -> 193.238.157.136, etx 0.529, neigh-etx 0.737
TC: del edge entry 193.238.156.109 -> 193.238.159.158, etx 0.667, neigh-etx 0.518
TC: del edge entry 193.238.156.109 -> 193.238.156.163, etx 0.529, neigh-etx 0.427
TC: del edge entry 193.238.156.109 -> 193.238.156.170, etx 0.718, neigh-etx 0.149
TC: del edge entry 193.238.156.109 -> 193.238.156.173, etx 0.043, neigh-etx 0.098
TC: del edge entry 193.238.156.109 -> 193.238.157.177, etx 0.737, neigh-etx 0.557
TC: del edge entry 193.238.156.109 -> 193.238.156.231, etx 0.667, neigh-etx 0.557

now packet #2 arrives - the TC message continues (= same seq #)
and all the neighbors are listed now ...  

Processing TC from 193.238.156.109, seq 0x9a6d
TC: add edge entry 193.238.156.109 -> 193.238.157.177, etx 0.737, neigh-etx 0.557
TC: add edge entry 193.238.156.109 -> 193.238.156.63, etx 0.557, neigh-etx 0.286
TC: add edge entry 193.238.156.109 -> 193.238.156.163, etx 0.529, neigh-etx 0.447
TC: add edge entry 193.238.156.109 -> 193.238.156.170, etx 0.718, neigh-etx 0.157
TC: add edge entry 193.238.156.109 -> 193.238.156.173, etx 0.043, neigh-etx 0.098
TC: add edge entry 193.238.156.109 -> 193.238.156.23, etx 0.055, neigh-etx 0.298
TC: add edge entry 193.238.156.109 -> 193.238.159.158, etx 0.627, neigh-etx 0.557
TC: add edge entry 193.238.156.109 -> 193.238.158.5, etx 1.000, neigh-etx 1.000
TC: add edge entry 193.238.156.109 -> 193.238.157.136, etx 0.529, neigh-etx 0.769
TC: add edge entry 193.238.156.109 -> 193.238.159.15, etx 1.000, neigh-etx 1.000
TC: add edge entry 193.238.156.109 -> 193.238.156.113, etx 1.000, neigh-etx 1.000
TC: add edge entry 193.238.156.109 -> 193.238.156.231, etx 0.667, neigh-etx 0.576

now all the edges are re-inserted and a SPF calculation is commenced.

patchset producing the debug output above is at
http://gredler.at/download/olsrd/inplace-spf-1.diff.gz

any smart thoughts for a fix ? -

/hannes