Re: CVS commit: src/sys/net

[Taylor R Campbell <campbell+netbsd-source-changes-d%mumble.net@localhost>]

   Date: Tue, 16 Feb 2016 08:38:55 +0000
   From: Roy Marples <roy%marples.name@localhost>

   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.)