Date: Tue, 16 Feb 2016 08:38:55 +0000 From: Roy Marples <r...@marples.name>
The queue can be kept quite short because we don't care about any prior entries each time state changes to LINK_STATE_DOWN. Also, we don't care about any prior entries (other than LINK_STATE_DOWN) when setting LINK_STATE_UNKNOWN. Finally we set LINK_STATE_UP. So the queue should only ever hold a maximum of 3 items. Could even work it like so [...] Thoughts? Sounds better than my suggestion, from someone who knows better how the link state events are used! Maybe I should have looked at the list of valid states, too -- all three of them. We don't even need an array, really. If I understand correctly, we obviously have the following equivalences of queues: (1) unknown/unknown = unknown (2) unknown/down = down (3) unknown/up = down/up (4) down/unknown = down/unknown (5) down/down = down (6) down/up = down/up (7) up/unknown = up/unknown (8) up/down = up/down (9) up/up = up I can reasonably believe (10) up/down/up = down/up and (11) down/up/down = down, too. From these, we can reduce almost all 3-queues to 2-queues: unknown/unknown/unknown =(1) unknown/unknown =(1) unknown unknown/unknown/down =(1) unknown/down =(2) down unknown/unknown/up =(3) unknown/up =(2) down/up unknown/down/unknown =(2) down/unknown unknown/down/down =(2) down/down =(5) down unknown/down/up =(2) down/down/up =(5) down/up unknown/up/unknown =(3) down/up/unknown ? unknown/up/down =(3) down/up/down =(11) down unknown/up/up =(3) down/up/up =(9) down/up down/unknown/unknown =(1) down/unknown down/unknown/down =(2) down/down =(5) down down/unknown/up =(3) down/down/up =(5) down/up down/down/unknown =(5) down/unknown down/down/down =(5) down/down =(5) down down/down/up =(5) down/up down/up/unknown ? down/up/down =(11) down down/up/up =(9) down/up up/unknown/unknown =(1) up/unknown up/unknown/down =(2) up/down up/unknown/up = up/down/up =(10) down/up up/down/unknown ? up/down/down =(5) up/down up/down/up =(10) down/up up/up/unknown = up/unknown up/up/down = up/down up/up/up = up/up = up That leaves us with only two cases where a 3-queue stays a 3-queue and doesn't reduce to a 2-queue. For those cases, the possible 4-queues are: down/up/unknown/unknown =(1) down/up/unknown down/up/unknown/down =(2) down/up/down =(11) down down/up/unknown/up =(3) down/up/down/up =(10) down/up up/down/unknown/unknown =(1) up/down/unknown up/down/unknown/down =(2) up/down/down =(5) up/down up/down/unknown/up =(3) up/down/down/up =(5) up/down/up =(10) down/up Collecting all the possible queues, we get only nine possibilities: down down/unknown down/up down/up/unknown unknown up up/down up/down/unknown up/unknown We could store it as a single int (numbered densely, or by 1 << LINK_STATE_*) and write the queue-append operation all as one switch. Perhaps there are more equivalences I didn't capture, or cases that are never going to occur -- for example, do we ever actually transition from up/down to unknown, or does unknown only happen when the interface is first attached? (I'm not sure.)