linux-stable.git/net/tipc/bcast.c, branch linux-4.2.y

tipc: purge backlog queue counters when broadcast link is reset

2015-06-28T23:43:02+00:00

In commit 1f66d161ab3d8b518903fa6c3f9c1f48d6919e74
("tipc: introduce starvation free send algorithm")
we introduced a counter per priority level for buffers
in the link backlog queue. We also introduced a new
function tipc_link_purge_backlog(), to reset these
counters to zero when the link is reset.

Unfortunately, we missed to call this function when
the broadcast link is reset, with the result that the
values of these counters might be permanently skewed
when new nodes are attached. This may in the worst case
lead to permananent, but spurious, broadcast link
congestion, where no broadcast packets can be sent at
all.

We fix this bug with this commit.

Signed-off-by: Jon Maloy 
Signed-off-by: David S. Miller

tipc: add packet sequence number at instant of transmission

2015-05-14T16:24:46+00:00

Currently, the packet sequence number is updated and added to each
packet at the moment a packet is added to the link backlog queue.
This is wasteful, since it forces the code to traverse the send
packet list packet by packet when adding them to the backlog queue.
It would be better to just splice the whole packet list into the
backlog queue when that is the right action to do.

In this commit, we do this change. Also, since the sequence numbers
cannot now be assigned to the packets at the moment they are added
the backlog queue, we do instead calculate and add them at the moment
of transmission, when the backlog queue has to be traversed anyway.
We do this in the function tipc_link_push_packet().

Reviewed-by: Erik Hugne 
Reviewed-by: Ying Xue 
Signed-off-by: Jon Maloy 
Signed-off-by: David S. Miller

tipc: rename fields in struct tipc_link

2015-05-14T16:24:46+00:00

We rename some fields in struct tipc_link, in order to give them more
descriptive names:

next_in_no -> rcv_nxt
next_out_no-> snd_nxt
fsm_msg_cnt-> silent_intv_cnt
cont_intv  -> keepalive_intv
last_retransmitted -> last_retransm

There are no functional changes in this commit.

Reviewed-by: Erik Hugne 
Reviewed-by: Ying Xue 
Signed-off-by: Jon Maloy 
Signed-off-by: David S. Miller

tipc: add broadcast link window set/get to nl api

2015-05-09T20:40:02+00:00

Add the ability to get or set the broadcast link window through the
new netlink API. The functionality was unintentionally missing from
the new netlink API. Adding this means that we also fix the breakage
in the old API when coming through the compat layer.

Fixes: 37e2d4843f9e (tipc: convert legacy nl link prop set to nl compat)
Reported-by: Tomi Ollila 
Signed-off-by: Richard Alpe 
Reviewed-by: Erik Hugne 
Reviewed-by: Ying Xue 
Signed-off-by: David S. Miller

tipc: simplify link mtu negotiation

2015-04-02T20:27:12+00:00

When a link is being established, the two endpoints advertise their
respective interface MTU in the transmitted RESET and ACTIVATE messages.
If there is any difference, the lower of the two MTUs will be selected
for use by both endpoints.

However, as a remnant of earlier attempts to introduce TIPC level
routing. there also exists an MTU discovery mechanism. If an intermediate
node has a lower MTU than the two endpoints, they will discover this
through a bisectional approach, and finally adopt this MTU for common use.

Since there is no TIPC level routing, and probably never will be,
this mechanism doesn't make any sense, and only serves to make the
link level protocol unecessarily complex.

In this commit, we eliminate the MTU discovery algorithm,and fall back
to the simple MTU advertising approach. This change is fully backwards
compatible.

Reviewed-by: Ying Xue 
Signed-off-by: Jon Maloy 
Signed-off-by: David S. Miller

tipc: involve reference counter for node structure

2015-03-29T19:40:28+00:00

TIPC node hash node table is protected with rcu lock on read side.
tipc_node_find() is used to look for a node object with node address
through iterating the hash node table. As the entire process of what
tipc_node_find() traverses the table is guarded with rcu read lock,
it's safe for us. However, when callers use the node object returned
by tipc_node_find(), there is no rcu read lock applied. Therefore,
this is absolutely unsafe for callers of tipc_node_find().

Now we introduce a reference counter for node structure. Before
tipc_node_find() returns node object to its caller, it first increases
the reference counter. Accordingly, after its caller used it up,
it decreases the counter again. This can prevent a node being used by
one thread from being freed by another thread.

Reviewed-by: Erik Hugne 
Reviewed-by: Jon Maloy 
Signed-off-by: Ying Xue 
Signed-off-by: David S. Miller

tipc: fix potential deadlock when all links are reset

2015-03-29T19:40:27+00:00

[   60.988363] ======================================================
[   60.988754] [ INFO: possible circular locking dependency detected ]
[   60.989152] 3.19.0+ #194 Not tainted
[   60.989377] -------------------------------------------------------
[   60.989781] swapper/3/0 is trying to acquire lock:
[   60.990079]  (&(&n_ptr->lock)->rlock){+.-...}, at: [] tipc_link_retransmit+0x1aa/0x240 [tipc]
[   60.990743]
[   60.990743] but task is already holding lock:
[   60.991106]  (&(&bclink->lock)->rlock){+.-...}, at: [] tipc_bclink_lock+0x8e/0xa0 [tipc]
[   60.991738]
[   60.991738] which lock already depends on the new lock.
[   60.991738]
[   60.992174]
[   60.992174] the existing dependency chain (in reverse order) is:
[   60.992174]
-> #1 (&(&bclink->lock)->rlock){+.-...}:
[   60.992174]        [] lock_acquire+0x9c/0x140
[   60.992174]        [] _raw_spin_lock_bh+0x3f/0x50
[   60.992174]        [] tipc_bclink_lock+0x8e/0xa0 [tipc]
[   60.992174]        [] tipc_bclink_add_node+0x97/0xf0 [tipc]
[   60.992174]        [] tipc_node_link_up+0xf5/0x110 [tipc]
[   60.992174]        [] link_state_event+0x2b3/0x4f0 [tipc]
[   60.992174]        [] tipc_link_proto_rcv+0x24c/0x418 [tipc]
[   60.992174]        [] tipc_rcv+0x827/0xac0 [tipc]
[   60.992174]        [] tipc_l2_rcv_msg+0x73/0xd0 [tipc]
[   60.992174]        [] __netif_receive_skb_core+0x746/0x980
[   60.992174]        [] __netif_receive_skb+0x21/0x70
[   60.992174]        [] netif_receive_skb_internal+0x35/0x130
[   60.992174]        [] napi_gro_receive+0x158/0x1d0
[   60.992174]        [] e1000_clean_rx_irq+0x155/0x490
[   60.992174]        [] e1000_clean+0x267/0x990
[   60.992174]        [] net_rx_action+0x150/0x360
[   60.992174]        [] __do_softirq+0x123/0x360
[   60.992174]        [] irq_exit+0x8e/0xb0
[   60.992174]        [] do_IRQ+0x65/0x110
[   60.992174]        [] ret_from_intr+0x0/0x13
[   60.992174]        [] arch_cpu_idle+0xf/0x20
[   60.992174]        [] cpu_startup_entry+0x2f6/0x3f0
[   60.992174]        [] start_secondary+0x13a/0x150
[   60.992174]
-> #0 (&(&n_ptr->lock)->rlock){+.-...}:
[   60.992174]        [] __lock_acquire+0x163d/0x1ca0
[   60.992174]        [] lock_acquire+0x9c/0x140
[   60.992174]        [] _raw_spin_lock_bh+0x3f/0x50
[   60.992174]        [] tipc_link_retransmit+0x1aa/0x240 [tipc]
[   60.992174]        [] tipc_bclink_rcv+0x611/0x640 [tipc]
[   60.992174]        [] tipc_rcv+0x616/0xac0 [tipc]
[   60.992174]        [] tipc_l2_rcv_msg+0x73/0xd0 [tipc]
[   60.992174]        [] __netif_receive_skb_core+0x746/0x980
[   60.992174]        [] __netif_receive_skb+0x21/0x70
[   60.992174]        [] netif_receive_skb_internal+0x35/0x130
[   60.992174]        [] napi_gro_receive+0x158/0x1d0
[   60.992174]        [] e1000_clean_rx_irq+0x155/0x490
[   60.992174]        [] e1000_clean+0x267/0x990
[   60.992174]        [] net_rx_action+0x150/0x360
[   60.992174]        [] __do_softirq+0x123/0x360
[   60.992174]        [] irq_exit+0x8e/0xb0
[   60.992174]        [] do_IRQ+0x65/0x110
[   60.992174]        [] ret_from_intr+0x0/0x13
[   60.992174]        [] arch_cpu_idle+0xf/0x20
[   60.992174]        [] cpu_startup_entry+0x2f6/0x3f0
[   60.992174]        [] start_secondary+0x13a/0x150
[   60.992174]
[   60.992174] other info that might help us debug this:
[   60.992174]
[   60.992174]  Possible unsafe locking scenario:
[   60.992174]
[   60.992174]        CPU0                    CPU1
[   60.992174]        ----                    ----
[   60.992174]   lock(&(&bclink->lock)->rlock);
[   60.992174]                                lock(&(&n_ptr->lock)->rlock);
[   60.992174]                                lock(&(&bclink->lock)->rlock);
[   60.992174]   lock(&(&n_ptr->lock)->rlock);
[   60.992174]
[   60.992174]  *** DEADLOCK ***
[   60.992174]
[   60.992174] 3 locks held by swapper/3/0:
[   60.992174]  #0:  (rcu_read_lock){......}, at: [] __netif_receive_skb_core+0x71/0x980
[   60.992174]  #1:  (rcu_read_lock){......}, at: [] tipc_l2_rcv_msg+0x5/0xd0 [tipc]
[   60.992174]  #2:  (&(&bclink->lock)->rlock){+.-...}, at: [] tipc_bclink_lock+0x8e/0xa0 [tipc]
[   60.992174]

The correct the sequence of grabbing n_ptr->lock and bclink->lock
should be that the former is first held and the latter is then taken,
which exactly happened on CPU1. But especially when the retransmission
of broadcast link is failed, bclink->lock is first held in
tipc_bclink_rcv(), and n_ptr->lock is taken in link_retransmit_failure()
called by tipc_link_retransmit() subsequently, which is demonstrated on
CPU0. As a result, deadlock occurs.

If the order of holding the two locks happening on CPU0 is reversed, the
deadlock risk will be relieved. Therefore, the node lock taken in
link_retransmit_failure() originally is moved to tipc_bclink_rcv()
so that it's obtained before bclink lock. But the precondition of
the adjustment of node lock is that responding to bclink reset event
must be moved from tipc_bclink_unlock() to tipc_node_unlock().

Reviewed-by: Erik Hugne 
Signed-off-by: Ying Xue 
Signed-off-by: David S. Miller

tipc: introduce starvation free send algorithm

2015-03-25T18:05:56+00:00

Currently, we only use a single counter; the length of the backlog
queue, to determine whether a message should be accepted to the queue
or not. Each time a message is being sent, the queue length is compared
to a threshold value for the message's importance priority. If the queue
length is beyond this threshold, the message is rejected. This algorithm
implies a risk of starvation of low importance senders during very high
load, because it may take a long time before the backlog queue has
decreased enough to accept a lower level message.

We now eliminate this risk by introducing a counter for each importance
priority. When a message is sent, we check only the queue level for that
particular message's priority. If that is ok, the message can be added
to the backlog, irrespective of the queue level for other priorities.
This way, each level is guaranteed a certain portion of the total
bandwidth, and any risk of starvation is eliminated.

Reviewed-by: Ying Xue 
Reviewed-by: Erik Hugne 
Signed-off-by: Jon Maloy 
Signed-off-by: David S. Miller

tipc: fix a link reset issue due to retransmission failures

2015-03-25T15:43:32+00:00

When a node joins a cluster while we are transmitting a fragment
stream over the broadcast link, it's missing the preceding fragments
needed to build a meaningful message. As a result, the node has to
drop it. However, as the fragment message is not acknowledged to
its sender before it's dropped, it accidentally causes link reset
of retransmission failure on the node.

Reported-by: Erik Hugne 
Signed-off-by: Ying Xue 
Reviewed-by: Erik Hugne 
Tested-by: Erik Hugne 
Signed-off-by: David S. Miller

tipc: clean up handling of message priorities

2015-03-14T18:38:32+00:00

Messages transferred by TIPC are assigned an "importance priority", -an
integer value indicating how to treat the message when there is link or
destination socket congestion.

There is no separate header field for this value. Instead, the message
user values have been chosen in ascending order according to perceived
importance, so that the message user field can be used for this.

This is not a good solution. First, we have many more users than the
needed priority levels, so we end up with treating more priority
levels than necessary. Second, the user field cannot always
accurately reflect the priority of the message. E.g., a message
fragment packet should really have the priority of the enveloped
user data message, and not the priority of the MSG_FRAGMENTER user.
Until now, we have been working around this problem in different ways,
but it is now time to implement a consistent way of handling such
priorities, although still within the constraint that we cannot
allocate any more bits in the regular data message header for this.

In this commit, we define a new priority level, TIPC_SYSTEM_IMPORTANCE,
that will be the only one used apart from the four (lower) user data
levels. All non-data messages map down to this priority. Furthermore,
we take some free bits from the MSG_FRAGMENTER header and allocate
them to store the priority of the enveloped message. We then adjust
the functions msg_importance()/msg_set_importance() so that they
read/set the correct header fields depending on user type.

This small protocol change is fully compatible, because the code at
the receiving end of a link currently reads the importance level
only from user data messages, where there is no change.

Reviewed-by: Erik Hugne 
Signed-off-by: Jon Maloy 
Signed-off-by: David S. Miller