)]}' { "commit": "c4282ca76c5b81ed73ef4c5eb5c07ee397e51642", "tree": "b2bcb2655f527aef6226cf1836952e44ece0feba", "parents": [ "8fa956e32c998289c5bc0bc06eb3dc7a5cc11ce8" ], "author": { "name": "Jon Paul Maloy", "email": "jon.maloy@ericsson.com", "time": "Wed Jun 08 12:00:04 2016 -0400" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Wed Jun 08 11:27:01 2016 -0700" }, "message": "tipc: correct error in node fsm\n\ncommit 88e8ac7000dc (\"tipc: reduce transmission rate of reset messages\nwhen link is down\") revealed a flaw in the node FSM, as defined in\nthe log of commit 66996b6c47ed (\"tipc: extend node FSM\").\n\nWe see the following scenario:\n1: Node B receives a RESET message from node A before its link endpoint\n is fully up, i.e., the node FSM is in state SELF_UP_PEER_COMING. This\n event will not change the node FSM state, but the (distinct) link FSM\n will move to state RESETTING.\n2: As an effect of the previous event, the local endpoint on B will\n declare node A lost, and post the event SELF_DOWN to the its node\n FSM. This moves the FSM state to SELF_DOWN_PEER_LEAVING, meaning\n that no messages will be accepted from A until it receives another\n RESET message that confirms that A\u0027s endpoint has been reset. This\n is wasteful, since we know this as a fact already from the first\n received RESET, but worse is that the link instance\u0027s FSM has not\n wasted this information, but instead moved on to state ESTABLISHING,\n meaning that it repeatedly sends out ACTIVATE messages to the reset\n peer A.\n3: Node A will receive one of the ACTIVATE messages, move its link FSM\n to state ESTABLISHED, and start repeatedly sending out STATE messages\n to node B.\n4: Node B will consistently drop these messages, since it can only accept\n accept a RESET according to its node FSM.\n5: After four lost STATE messages node A will reset its link and start\n repeatedly sending out RESET messages to B.\n6: Because of the reduced send rate for RESET messages, it is very\n likely that A will receive an ACTIVATE (which is sent out at a much\n higher frequency) before it gets the chance to send a RESET, and A\n may hence quickly move back to state ESTABLISHED and continue sending\n out STATE messages, which will again be dropped by B.\n7: GOTO 5.\n8: After having repeated the cycle 5-7 a number of times, node A will\n by chance get in between with sending a RESET, and the situation is\n resolved.\n\nUnfortunately, we have seen that it may take a substantial amount of\ntime before this vicious loop is broken, sometimes in the order of\nminutes.\n\nWe correct this by making a small correction to the node FSM: When a\nnode in state SELF_UP_PEER_COMING receives a SELF_DOWN event, it now\nmoves directly back to state SELF_DOWN_PEER_DOWN, instead of as now\nSELF_DOWN_PEER_LEAVING. This is logically consistent, since we don\u0027t\nneed to wait for RESET confirmation from of an endpoint that we alread\nknow has been reset. It also means that node B in the scenario above\nwill not be dropping incoming STATE messages, and the link can come up\nimmediately.\n\nFinally, a symmetry comparison reveals that the FSM has a similar\nerror when receiving the event PEER_DOWN in state PEER_UP_SELF_COMING.\nInstead of moving to PERR_DOWN_SELF_LEAVING, it should move directly\nto SELF_DOWN_PEER_DOWN. Although we have never seen any negative effect\nof this logical error, we choose fix this one, too.\n\nThe node FSM looks as follows after those changes:\n\n +----------------------------------------+\n | PEER_DOWN_EVT|\n | |\n +------------------------+----------------+ |\n |SELF_DOWN_EVT | | |\n | | | |\n | +-----------+ +-----------+ |\n | |NODE_ | |NODE_ | |\n | +----------|FAILINGOVER|\u003c---------|SYNCHING |-----------+ |\n | |SELF_ +-----------+ FAILOVER_+-----------+ PEER_ | |\n | |DOWN_EVT | A BEGIN_EVT A | DOWN_EVT| |\n | | | | | | | |\n | | | | | | | |\n | | |FAILOVER_ |FAILOVER_ |SYNCH_ |SYNCH_ | |\n | | |END_EVT |BEGIN_EVT |BEGIN_EVT|END_EVT | |\n | | | | | | | |\n | | | | | | | |\n | | | +--------------+ | | |\n | | +--------\u003e| SELF_UP_ |\u003c-------+ | |\n | | +-----------------| PEER_UP |----------------+ | |\n | | |SELF_DOWN_EVT +--------------+ PEER_DOWN_EVT| | |\n | | | A A | | |\n | | | | | | | |\n | | | PEER_UP_EVT| |SELF_UP_EVT | | |\n | | | | | | | |\n V V V | | V V V\n+------------+ +-----------+ +-----------+ +------------+\n|SELF_DOWN_ | |SELF_UP_ | |PEER_UP_ | |PEER_DOWN |\n|PEER_LEAVING| |PEER_COMING| |SELF_COMING| |SELF_LEAVING|\n+------------+ +-----------+ +-----------+ +------------+\n | | A A | |\n | | | | | |\n | SELF_ | |SELF_ |PEER_ |PEER_ |\n | DOWN_EVT| |UP_EVT |UP_EVT |DOWN_EVT |\n | | | | | |\n | | | | | |\n | | +--------------+ | |\n |PEER_DOWN_EVT +---\u003e| SELF_DOWN_ |\u003c---+ SELF_DOWN_EVT|\n +-------------------\u003e| PEER_DOWN |\u003c--------------------+\n +--------------+\n\nAcked-by: Ying Xue \u003cying.xue@windriver.com\u003e\nSigned-off-by: Jon Maloy \u003cjon.maloy@ericsson.com\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "e01e2c71b5a16fde975b6e87bd134ae57cd57326", "old_mode": 33188, "old_path": "net/tipc/node.c", "new_id": "c7985b2cb759648f3dcecc0dbb694f68f6c333f5", "new_mode": 33188, "new_path": "net/tipc/node.c" } ] }