[PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Xufeng Zhang]

sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
was sent on, if not found in the active_path transport, then go search
all the other transports in the peer's transport_addr_list, however, we
should continue to the next entry rather than break the loop when meet
the active_path transport.

Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
---
 net/sctp/associola.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/net/sctp/associola.c b/net/sctp/associola.c
index 43cd0dd..d2709e2 100644
--- a/net/sctp/associola.c
+++ b/net/sctp/associola.c
@@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
 			transports) {
 
 		if (transport == active)
-			break;
+			continue;
 		list_for_each_entry(chunk, &transport->transmitted,
 				transmitted_list) {
 			if (key == chunk->subh.data_hdr->tsn) {
-- 
1.7.0.2

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Neil Horman]

On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
> was sent on, if not found in the active_path transport, then go search
> all the other transports in the peer's transport_addr_list, however, we
> should continue to the next entry rather than break the loop when meet
> the active_path transport.
> 
> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
> ---
>  net/sctp/associola.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 43cd0dd..d2709e2 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>  			transports) {
>  
>  		if (transport == active)
> -			break;
> +			continue;
>  		list_for_each_entry(chunk, &transport->transmitted,
>  				transmitted_list) {
>  			if (key == chunk->subh.data_hdr->tsn) {
> -- 
> 1.7.0.2
> 
> 

This works, but what might be better would be if we did a move to front
heuristic in sctp_assoc_set_primary.  E.g. when we set the active_path, move the
requisite transport to the front of the transport_addr_list.  If we did that,
then we could just do one for loop in sctp_assoc_lookup_tsn and wind up
implicitly check the active path first without having to check it seprately and
skip it in the second for loop.  

Neil

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Xufeng Zhang]

On 3/8/13, Neil Horman <nhorman@tuxdriver.com> wrote:
> On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
>> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
>> was sent on, if not found in the active_path transport, then go search
>> all the other transports in the peer's transport_addr_list, however, we
>> should continue to the next entry rather than break the loop when meet
>> the active_path transport.
>>
>> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
>> ---
>>  net/sctp/associola.c |    2 +-
>>  1 files changed, 1 insertions(+), 1 deletions(-)
>>
>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>> index 43cd0dd..d2709e2 100644
>> --- a/net/sctp/associola.c
>> +++ b/net/sctp/associola.c
>> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
>> sctp_association *asoc,
>>  			transports) {
>>
>>  		if (transport == active)
>> -			break;
>> +			continue;
>>  		list_for_each_entry(chunk, &transport->transmitted,
>>  				transmitted_list) {
>>  			if (key == chunk->subh.data_hdr->tsn) {
>> --
>> 1.7.0.2
>>
>>
>
> This works, but what might be better would be if we did a move to front
> heuristic in sctp_assoc_set_primary.  E.g. when we set the active_path, move
> the
> requisite transport to the front of the transport_addr_list.  If we did
> that,
> then we could just do one for loop in sctp_assoc_lookup_tsn and wind up
> implicitly check the active path first without having to check it seprately
> and
> skip it in the second for loop.

Thanks for your review, Neil!

I know what you mean, yes, it's most probably that the searched TSN was
transmitted in the currently active_path, but what should we do if not.

Check the comment in sctp_assoc_lookup_tsn() function:
/* Let's be hopeful and check the active_path first. */
/* If not found, go search all the other transports. */

It has checked the active_path first and then traverse all the other
transports in
the transport_addr_list except the active_path.

So what I want to fix here is the inconsistency between the function
should do and
the code actually does.



Thanks,
Xufeng


>
> Neil
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Neil Horman]

On Mon, Mar 11, 2013 at 10:14:50AM +0800, Xufeng Zhang wrote:
> On 3/8/13, Neil Horman <nhorman@tuxdriver.com> wrote:
> > On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
> >> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
> >> was sent on, if not found in the active_path transport, then go search
> >> all the other transports in the peer's transport_addr_list, however, we
> >> should continue to the next entry rather than break the loop when meet
> >> the active_path transport.
> >>
> >> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
> >> ---
> >>  net/sctp/associola.c |    2 +-
> >>  1 files changed, 1 insertions(+), 1 deletions(-)
> >>
> >> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> >> index 43cd0dd..d2709e2 100644
> >> --- a/net/sctp/associola.c
> >> +++ b/net/sctp/associola.c
> >> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
> >> sctp_association *asoc,
> >>  			transports) {
> >>
> >>  		if (transport == active)
> >> -			break;
> >> +			continue;
> >>  		list_for_each_entry(chunk, &transport->transmitted,
> >>  				transmitted_list) {
> >>  			if (key == chunk->subh.data_hdr->tsn) {
> >> --
> >> 1.7.0.2
> >>
> >>
> >
> > This works, but what might be better would be if we did a move to front
> > heuristic in sctp_assoc_set_primary.  E.g. when we set the active_path, move
> > the
> > requisite transport to the front of the transport_addr_list.  If we did
> > that,
> > then we could just do one for loop in sctp_assoc_lookup_tsn and wind up
> > implicitly check the active path first without having to check it seprately
> > and
> > skip it in the second for loop.
> 
> Thanks for your review, Neil!
> 
> I know what you mean, yes, it's most probably that the searched TSN was
> transmitted in the currently active_path, but what should we do if not.
> 
> Check the comment in sctp_assoc_lookup_tsn() function:
> /* Let's be hopeful and check the active_path first. */
> /* If not found, go search all the other transports. */
> 
> It has checked the active_path first and then traverse all the other
> transports in
> the transport_addr_list except the active_path.
> 
> So what I want to fix here is the inconsistency between the function
> should do and
> the code actually does.
> 
I understand what you're doing, and I agree that the fix is functional (Hence
my "This works" statement in my last note).  What I'm suggesting is that, since
you're messing about in that code anyway that you clean it up while your at it,
so that we don't need to have the if (transport == active) check at all.  We
trade in some extra work in a non-critical path (sctp_assoc_set_primary), for
the removal of an extra for loop operation and a conditional check in a much
hotter path.  Something like this (completely untested), is what I was thinking


diff --git a/net/sctp/associola.c b/net/sctp/associola.c
index 43cd0dd..8ae873c 100644
--- a/net/sctp/associola.c
+++ b/net/sctp/associola.c
@@ -505,6 +505,9 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
 
 	asoc->peer.primary_path = transport;
 
+	list_del_rcu(&transport->transports);
+	list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
+
 	/* Set a default msg_name for events. */
 	memcpy(&asoc->peer.primary_addr, &transport->ipaddr,
 	       sizeof(union sctp_addr));
@@ -1040,7 +1043,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
 struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
 					     __u32 tsn)
 {
-	struct sctp_transport *active;
 	struct sctp_transport *match;
 	struct sctp_transport *transport;
 	struct sctp_chunk *chunk;
@@ -1057,29 +1059,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
 	 * The general strategy is to search each transport's transmitted
 	 * list.   Return which transport this TSN lives on.
 	 *
-	 * Let's be hopeful and check the active_path first.
-	 * Another optimization would be to know if there is only one
-	 * outbound path and not have to look for the TSN at all.
+	 * Note, that sctp_assoc_set_primary does a move to front operation
+	 * on the active_path transport, so this code implicitly checks
+	 * the active_path first, as we most commonly expect to find our TSN
+	 * there.
 	 *
 	 */
 
-	active = asoc->peer.active_path;
-
-	list_for_each_entry(chunk, &active->transmitted,
-			transmitted_list) {
-
-		if (key == chunk->subh.data_hdr->tsn) {
-			match = active;
-			goto out;
-		}
-	}
-
-	/* If not found, go search all the other transports. */
 	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
 			transports) {
 
-		if (transport == active)
-			break;
 		list_for_each_entry(chunk, &transport->transmitted,
 				transmitted_list) {
 			if (key == chunk->subh.data_hdr->tsn) {

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Xufeng Zhang]

>>
>> Thanks for your review, Neil!
>>
>> I know what you mean, yes, it's most probably that the searched TSN was
>> transmitted in the currently active_path, but what should we do if not.
>>
>> Check the comment in sctp_assoc_lookup_tsn() function:
>> /* Let's be hopeful and check the active_path first. */
>> /* If not found, go search all the other transports. */
>>
>> It has checked the active_path first and then traverse all the other
>> transports in
>> the transport_addr_list except the active_path.
>>
>> So what I want to fix here is the inconsistency between the function
>> should do and
>> the code actually does.
>>
> I understand what you're doing, and I agree that the fix is functional
> (Hence
> my "This works" statement in my last note).  What I'm suggesting is that,
> since
> you're messing about in that code anyway that you clean it up while your at
> it,
> so that we don't need to have the if (transport == active) check at all.
> We
> trade in some extra work in a non-critical path (sctp_assoc_set_primary),
> for
> the removal of an extra for loop operation and a conditional check in a
> much
> hotter path.  Something like this (completely untested), is what I was
> thinking

Aha, seems I have some misunderstanding previously, now I got your point.
Yeah, it's better to do the clean up by this way, and this fix looks fine to me,
but I didn't have a test case to test this, actually this problem was detected
by code review, so I would like to leave the rest of this work to
determine by you.

Thank you very much for your clarification!


Thanks,
Xufeng

>
>
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 43cd0dd..8ae873c 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -505,6 +505,9 @@ void sctp_assoc_set_primary(struct sctp_association
> *asoc,
>
>  	asoc->peer.primary_path = transport;
>
> +	list_del_rcu(&transport->transports);
> +	list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> +
>  	/* Set a default msg_name for events. */
>  	memcpy(&asoc->peer.primary_addr, &transport->ipaddr,
>  	       sizeof(union sctp_addr));
> @@ -1040,7 +1043,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct
> sctp_association *asoc)
>  struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association
> *asoc,
>  					     __u32 tsn)
>  {
> -	struct sctp_transport *active;
>  	struct sctp_transport *match;
>  	struct sctp_transport *transport;
>  	struct sctp_chunk *chunk;
> @@ -1057,29 +1059,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
> sctp_association *asoc,
>  	 * The general strategy is to search each transport's transmitted
>  	 * list.   Return which transport this TSN lives on.
>  	 *
> -	 * Let's be hopeful and check the active_path first.
> -	 * Another optimization would be to know if there is only one
> -	 * outbound path and not have to look for the TSN at all.
> +	 * Note, that sctp_assoc_set_primary does a move to front operation
> +	 * on the active_path transport, so this code implicitly checks
> +	 * the active_path first, as we most commonly expect to find our TSN
> +	 * there.
>  	 *
>  	 */
>
> -	active = asoc->peer.active_path;
> -
> -	list_for_each_entry(chunk, &active->transmitted,
> -			transmitted_list) {
> -
> -		if (key == chunk->subh.data_hdr->tsn) {
> -			match = active;
> -			goto out;
> -		}
> -	}
> -
> -	/* If not found, go search all the other transports. */
>  	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
>  			transports) {
>
> -		if (transport == active)
> -			break;
>  		list_for_each_entry(chunk, &transport->transmitted,
>  				transmitted_list) {
>  			if (key == chunk->subh.data_hdr->tsn) {
>

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Neil Horman]

On Tue, Mar 12, 2013 at 10:24:02AM +0800, Xufeng Zhang wrote:
> >>
> >> Thanks for your review, Neil!
> >>
> >> I know what you mean, yes, it's most probably that the searched TSN was
> >> transmitted in the currently active_path, but what should we do if not.
> >>
> >> Check the comment in sctp_assoc_lookup_tsn() function:
> >> /* Let's be hopeful and check the active_path first. */
> >> /* If not found, go search all the other transports. */
> >>
> >> It has checked the active_path first and then traverse all the other
> >> transports in
> >> the transport_addr_list except the active_path.
> >>
> >> So what I want to fix here is the inconsistency between the function
> >> should do and
> >> the code actually does.
> >>
> > I understand what you're doing, and I agree that the fix is functional
> > (Hence
> > my "This works" statement in my last note).  What I'm suggesting is that,
> > since
> > you're messing about in that code anyway that you clean it up while your at
> > it,
> > so that we don't need to have the if (transport == active) check at all.
> > We
> > trade in some extra work in a non-critical path (sctp_assoc_set_primary),
> > for
> > the removal of an extra for loop operation and a conditional check in a
> > much
> > hotter path.  Something like this (completely untested), is what I was
> > thinking
> 
> Aha, seems I have some misunderstanding previously, now I got your point.
> Yeah, it's better to do the clean up by this way, and this fix looks fine to me,
> but I didn't have a test case to test this, actually this problem was detected
> by code review, so I would like to leave the rest of this work to
> determine by you.
> 
> Thank you very much for your clarification!
> 
Ok, I'll try set up a test for this today
Neil

> 
> Thanks,
> Xufeng
> 
> >
> >
> > diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> > index 43cd0dd..8ae873c 100644
> > --- a/net/sctp/associola.c
> > +++ b/net/sctp/associola.c
> > @@ -505,6 +505,9 @@ void sctp_assoc_set_primary(struct sctp_association
> > *asoc,
> >
> >  	asoc->peer.primary_path = transport;
> >
> > +	list_del_rcu(&transport->transports);
> > +	list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> > +
> >  	/* Set a default msg_name for events. */
> >  	memcpy(&asoc->peer.primary_addr, &transport->ipaddr,
> >  	       sizeof(union sctp_addr));
> > @@ -1040,7 +1043,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct
> > sctp_association *asoc)
> >  struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association
> > *asoc,
> >  					     __u32 tsn)
> >  {
> > -	struct sctp_transport *active;
> >  	struct sctp_transport *match;
> >  	struct sctp_transport *transport;
> >  	struct sctp_chunk *chunk;
> > @@ -1057,29 +1059,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
> > sctp_association *asoc,
> >  	 * The general strategy is to search each transport's transmitted
> >  	 * list.   Return which transport this TSN lives on.
> >  	 *
> > -	 * Let's be hopeful and check the active_path first.
> > -	 * Another optimization would be to know if there is only one
> > -	 * outbound path and not have to look for the TSN at all.
> > +	 * Note, that sctp_assoc_set_primary does a move to front operation
> > +	 * on the active_path transport, so this code implicitly checks
> > +	 * the active_path first, as we most commonly expect to find our TSN
> > +	 * there.
> >  	 *
> >  	 */
> >
> > -	active = asoc->peer.active_path;
> > -
> > -	list_for_each_entry(chunk, &active->transmitted,
> > -			transmitted_list) {
> > -
> > -		if (key == chunk->subh.data_hdr->tsn) {
> > -			match = active;
> > -			goto out;
> > -		}
> > -	}
> > -
> > -	/* If not found, go search all the other transports. */
> >  	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
> >  			transports) {
> >
> > -		if (transport == active)
> > -			break;
> >  		list_for_each_entry(chunk, &transport->transmitted,
> >  				transmitted_list) {
> >  			if (key == chunk->subh.data_hdr->tsn) {
> >
> 

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Vlad Yasevich]

On 03/11/2013 09:31 AM, Neil Horman wrote:
> On Mon, Mar 11, 2013 at 10:14:50AM +0800, Xufeng Zhang wrote:
>> On 3/8/13, Neil Horman <nhorman@tuxdriver.com> wrote:
>>> On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
>>>> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
>>>> was sent on, if not found in the active_path transport, then go search
>>>> all the other transports in the peer's transport_addr_list, however, we
>>>> should continue to the next entry rather than break the loop when meet
>>>> the active_path transport.
>>>>
>>>> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
>>>> ---
>>>>   net/sctp/associola.c |    2 +-
>>>>   1 files changed, 1 insertions(+), 1 deletions(-)
>>>>
>>>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>>>> index 43cd0dd..d2709e2 100644
>>>> --- a/net/sctp/associola.c
>>>> +++ b/net/sctp/associola.c
>>>> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
>>>> sctp_association *asoc,
>>>>   			transports) {
>>>>
>>>>   		if (transport == active)
>>>> -			break;
>>>> +			continue;
>>>>   		list_for_each_entry(chunk, &transport->transmitted,
>>>>   				transmitted_list) {
>>>>   			if (key == chunk->subh.data_hdr->tsn) {
>>>> --
>>>> 1.7.0.2
>>>>
>>>>
>>>
>>> This works, but what might be better would be if we did a move to front
>>> heuristic in sctp_assoc_set_primary.  E.g. when we set the active_path, move
>>> the
>>> requisite transport to the front of the transport_addr_list.  If we did
>>> that,
>>> then we could just do one for loop in sctp_assoc_lookup_tsn and wind up
>>> implicitly check the active path first without having to check it seprately
>>> and
>>> skip it in the second for loop.
>>
>> Thanks for your review, Neil!
>>
>> I know what you mean, yes, it's most probably that the searched TSN was
>> transmitted in the currently active_path, but what should we do if not.
>>
>> Check the comment in sctp_assoc_lookup_tsn() function:
>> /* Let's be hopeful and check the active_path first. */
>> /* If not found, go search all the other transports. */
>>
>> It has checked the active_path first and then traverse all the other
>> transports in
>> the transport_addr_list except the active_path.
>>
>> So what I want to fix here is the inconsistency between the function
>> should do and
>> the code actually does.
>>
> I understand what you're doing, and I agree that the fix is functional (Hence
> my "This works" statement in my last note).  What I'm suggesting is that, since
> you're messing about in that code anyway that you clean it up while your at it,
> so that we don't need to have the if (transport == active) check at all.  We
> trade in some extra work in a non-critical path (sctp_assoc_set_primary), for
> the removal of an extra for loop operation and a conditional check in a much
> hotter path.  Something like this (completely untested), is what I was thinking
>
>
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 43cd0dd..8ae873c 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -505,6 +505,9 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
>
>   	asoc->peer.primary_path = transport;
>
> +	list_del_rcu(&transport->transports);
> +	list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> +
>   	/* Set a default msg_name for events. */
>   	memcpy(&asoc->peer.primary_addr, &transport->ipaddr,
>   	       sizeof(union sctp_addr));
> @@ -1040,7 +1043,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
>   struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>   					     __u32 tsn)
>   {
> -	struct sctp_transport *active;
>   	struct sctp_transport *match;
>   	struct sctp_transport *transport;
>   	struct sctp_chunk *chunk;
> @@ -1057,29 +1059,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>   	 * The general strategy is to search each transport's transmitted
>   	 * list.   Return which transport this TSN lives on.
>   	 *
> -	 * Let's be hopeful and check the active_path first.
> -	 * Another optimization would be to know if there is only one
> -	 * outbound path and not have to look for the TSN at all.
> +	 * Note, that sctp_assoc_set_primary does a move to front operation
> +	 * on the active_path transport, so this code implicitly checks
> +	 * the active_path first, as we most commonly expect to find our TSN
> +	 * there.
>   	 *
>   	 */

Neil, active_patch != primary_path all the time.  In fact, when you have 
path primary path failure, active path will change while primary
may only change when the user says so.

So, you may still get into a situation where primary and active paths 
are different.

The optimization here may not work at all under those circumstances.

-vlad

>
> -	active = asoc->peer.active_path;
> -
> -	list_for_each_entry(chunk, &active->transmitted,
> -			transmitted_list) {
> -
> -		if (key == chunk->subh.data_hdr->tsn) {
> -			match = active;
> -			goto out;
> -		}
> -	}
> -
> -	/* If not found, go search all the other transports. */
>   	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
>   			transports) {
>
> -		if (transport == active)
> -			break;
>   		list_for_each_entry(chunk, &transport->transmitted,
>   				transmitted_list) {
>   			if (key == chunk->subh.data_hdr->tsn) {
>

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Neil Horman]

On Tue, Mar 12, 2013 at 08:11:34AM -0400, Vlad Yasevich wrote:
> On 03/11/2013 09:31 AM, Neil Horman wrote:
> >On Mon, Mar 11, 2013 at 10:14:50AM +0800, Xufeng Zhang wrote:
> >>On 3/8/13, Neil Horman <nhorman@tuxdriver.com> wrote:
> >>>On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
> >>>>sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
> >>>>was sent on, if not found in the active_path transport, then go search
> >>>>all the other transports in the peer's transport_addr_list, however, we
> >>>>should continue to the next entry rather than break the loop when meet
> >>>>the active_path transport.
> >>>>
> >>>>Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
> >>>>---
> >>>>  net/sctp/associola.c |    2 +-
> >>>>  1 files changed, 1 insertions(+), 1 deletions(-)
> >>>>
> >>>>diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> >>>>index 43cd0dd..d2709e2 100644
> >>>>--- a/net/sctp/associola.c
> >>>>+++ b/net/sctp/associola.c
> >>>>@@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
> >>>>sctp_association *asoc,
> >>>>  			transports) {
> >>>>
> >>>>  		if (transport == active)
> >>>>-			break;
> >>>>+			continue;
> >>>>  		list_for_each_entry(chunk, &transport->transmitted,
> >>>>  				transmitted_list) {
> >>>>  			if (key == chunk->subh.data_hdr->tsn) {
> >>>>--
> >>>>1.7.0.2
> >>>>
> >>>>
> >>>
> >>>This works, but what might be better would be if we did a move to front
> >>>heuristic in sctp_assoc_set_primary.  E.g. when we set the active_path, move
> >>>the
> >>>requisite transport to the front of the transport_addr_list.  If we did
> >>>that,
> >>>then we could just do one for loop in sctp_assoc_lookup_tsn and wind up
> >>>implicitly check the active path first without having to check it seprately
> >>>and
> >>>skip it in the second for loop.
> >>
> >>Thanks for your review, Neil!
> >>
> >>I know what you mean, yes, it's most probably that the searched TSN was
> >>transmitted in the currently active_path, but what should we do if not.
> >>
> >>Check the comment in sctp_assoc_lookup_tsn() function:
> >>/* Let's be hopeful and check the active_path first. */
> >>/* If not found, go search all the other transports. */
> >>
> >>It has checked the active_path first and then traverse all the other
> >>transports in
> >>the transport_addr_list except the active_path.
> >>
> >>So what I want to fix here is the inconsistency between the function
> >>should do and
> >>the code actually does.
> >>
> >I understand what you're doing, and I agree that the fix is functional (Hence
> >my "This works" statement in my last note).  What I'm suggesting is that, since
> >you're messing about in that code anyway that you clean it up while your at it,
> >so that we don't need to have the if (transport == active) check at all.  We
> >trade in some extra work in a non-critical path (sctp_assoc_set_primary), for
> >the removal of an extra for loop operation and a conditional check in a much
> >hotter path.  Something like this (completely untested), is what I was thinking
> >
> >
> >diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> >index 43cd0dd..8ae873c 100644
> >--- a/net/sctp/associola.c
> >+++ b/net/sctp/associola.c
> >@@ -505,6 +505,9 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
> >
> >  	asoc->peer.primary_path = transport;
> >
> >+	list_del_rcu(&transport->transports);
> >+	list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> >+
> >  	/* Set a default msg_name for events. */
> >  	memcpy(&asoc->peer.primary_addr, &transport->ipaddr,
> >  	       sizeof(union sctp_addr));
> >@@ -1040,7 +1043,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
> >  struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
> >  					     __u32 tsn)
> >  {
> >-	struct sctp_transport *active;
> >  	struct sctp_transport *match;
> >  	struct sctp_transport *transport;
> >  	struct sctp_chunk *chunk;
> >@@ -1057,29 +1059,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
> >  	 * The general strategy is to search each transport's transmitted
> >  	 * list.   Return which transport this TSN lives on.
> >  	 *
> >-	 * Let's be hopeful and check the active_path first.
> >-	 * Another optimization would be to know if there is only one
> >-	 * outbound path and not have to look for the TSN at all.
> >+	 * Note, that sctp_assoc_set_primary does a move to front operation
> >+	 * on the active_path transport, so this code implicitly checks
> >+	 * the active_path first, as we most commonly expect to find our TSN
> >+	 * there.
> >  	 *
> >  	 */
> 
> Neil, active_patch != primary_path all the time.  In fact, when you
> have path primary path failure, active path will change while
> primary
> may only change when the user says so.
Thats a good point, thank you Vlad.  We would need to only update the
transport_addr_list in set_primary if its state is ACTIVE or UNKNOWN.  We would
also need to update it if the active path changes in
sctp_assoc_control_transport, if the new active path is different from the old.
Both of those paths however are not intended to be run frequently, so I think
this is still a viable optimization.  I'm working on it now.
Neil

> 
> So, you may still get into a situation where primary and active
> paths are different.
> 
> The optimization here may not work at all under those circumstances.
> 
> -vlad
> 
> >
> >-	active = asoc->peer.active_path;
> >-
> >-	list_for_each_entry(chunk, &active->transmitted,
> >-			transmitted_list) {
> >-
> >-		if (key == chunk->subh.data_hdr->tsn) {
> >-			match = active;
> >-			goto out;
> >-		}
> >-	}
> >-
> >-	/* If not found, go search all the other transports. */
> >  	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
> >  			transports) {
> >
> >-		if (transport == active)
> >-			break;
> >  		list_for_each_entry(chunk, &transport->transmitted,
> >  				transmitted_list) {
> >  			if (key == chunk->subh.data_hdr->tsn) {
> >
> 
> 

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Vlad Yasevich]

On 03/12/2013 11:44 AM, Neil Horman wrote:
> On Tue, Mar 12, 2013 at 08:11:34AM -0400, Vlad Yasevich wrote:
>> On 03/11/2013 09:31 AM, Neil Horman wrote:
>>> On Mon, Mar 11, 2013 at 10:14:50AM +0800, Xufeng Zhang wrote:
>>>> On 3/8/13, Neil Horman <nhorman@tuxdriver.com> wrote:
>>>>> On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
>>>>>> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
>>>>>> was sent on, if not found in the active_path transport, then go search
>>>>>> all the other transports in the peer's transport_addr_list, however, we
>>>>>> should continue to the next entry rather than break the loop when meet
>>>>>> the active_path transport.
>>>>>>
>>>>>> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
>>>>>> ---
>>>>>>   net/sctp/associola.c |    2 +-
>>>>>>   1 files changed, 1 insertions(+), 1 deletions(-)
>>>>>>
>>>>>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>>>>>> index 43cd0dd..d2709e2 100644
>>>>>> --- a/net/sctp/associola.c
>>>>>> +++ b/net/sctp/associola.c
>>>>>> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct
>>>>>> sctp_association *asoc,
>>>>>>   			transports) {
>>>>>>
>>>>>>   		if (transport == active)
>>>>>> -			break;
>>>>>> +			continue;
>>>>>>   		list_for_each_entry(chunk, &transport->transmitted,
>>>>>>   				transmitted_list) {
>>>>>>   			if (key == chunk->subh.data_hdr->tsn) {
>>>>>> --
>>>>>> 1.7.0.2
>>>>>>
>>>>>>
>>>>>
>>>>> This works, but what might be better would be if we did a move to front
>>>>> heuristic in sctp_assoc_set_primary.  E.g. when we set the active_path, move
>>>>> the
>>>>> requisite transport to the front of the transport_addr_list.  If we did
>>>>> that,
>>>>> then we could just do one for loop in sctp_assoc_lookup_tsn and wind up
>>>>> implicitly check the active path first without having to check it seprately
>>>>> and
>>>>> skip it in the second for loop.
>>>>
>>>> Thanks for your review, Neil!
>>>>
>>>> I know what you mean, yes, it's most probably that the searched TSN was
>>>> transmitted in the currently active_path, but what should we do if not.
>>>>
>>>> Check the comment in sctp_assoc_lookup_tsn() function:
>>>> /* Let's be hopeful and check the active_path first. */
>>>> /* If not found, go search all the other transports. */
>>>>
>>>> It has checked the active_path first and then traverse all the other
>>>> transports in
>>>> the transport_addr_list except the active_path.
>>>>
>>>> So what I want to fix here is the inconsistency between the function
>>>> should do and
>>>> the code actually does.
>>>>
>>> I understand what you're doing, and I agree that the fix is functional (Hence
>>> my "This works" statement in my last note).  What I'm suggesting is that, since
>>> you're messing about in that code anyway that you clean it up while your at it,
>>> so that we don't need to have the if (transport == active) check at all.  We
>>> trade in some extra work in a non-critical path (sctp_assoc_set_primary), for
>>> the removal of an extra for loop operation and a conditional check in a much
>>> hotter path.  Something like this (completely untested), is what I was thinking
>>>
>>>
>>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>>> index 43cd0dd..8ae873c 100644
>>> --- a/net/sctp/associola.c
>>> +++ b/net/sctp/associola.c
>>> @@ -505,6 +505,9 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
>>>
>>>   	asoc->peer.primary_path = transport;
>>>
>>> +	list_del_rcu(&transport->transports);
>>> +	list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
>>> +
>>>   	/* Set a default msg_name for events. */
>>>   	memcpy(&asoc->peer.primary_addr, &transport->ipaddr,
>>>   	       sizeof(union sctp_addr));
>>> @@ -1040,7 +1043,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
>>>   struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>>>   					     __u32 tsn)
>>>   {
>>> -	struct sctp_transport *active;
>>>   	struct sctp_transport *match;
>>>   	struct sctp_transport *transport;
>>>   	struct sctp_chunk *chunk;
>>> @@ -1057,29 +1059,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>>>   	 * The general strategy is to search each transport's transmitted
>>>   	 * list.   Return which transport this TSN lives on.
>>>   	 *
>>> -	 * Let's be hopeful and check the active_path first.
>>> -	 * Another optimization would be to know if there is only one
>>> -	 * outbound path and not have to look for the TSN at all.
>>> +	 * Note, that sctp_assoc_set_primary does a move to front operation
>>> +	 * on the active_path transport, so this code implicitly checks
>>> +	 * the active_path first, as we most commonly expect to find our TSN
>>> +	 * there.
>>>   	 *
>>>   	 */
>>
>> Neil, active_patch != primary_path all the time.  In fact, when you
>> have path primary path failure, active path will change while
>> primary
>> may only change when the user says so.
> Thats a good point, thank you Vlad.  We would need to only update the
> transport_addr_list in set_primary if its state is ACTIVE or UNKNOWN.  We would
> also need to update it if the active path changes in
> sctp_assoc_control_transport, if the new active path is different from the old.
> Both of those paths however are not intended to be run frequently, so I think
> this is still a viable optimization.  I'm working on it now.
> Neil

You also need to take special care if an active transport is removed. 
The active path will get reassigned then.  I am not sure if it is worth 
doing all these changes to address a corner case optimization (CWR is a 
corner case).

-vlad

>
>>
>> So, you may still get into a situation where primary and active
>> paths are different.
>>
>> The optimization here may not work at all under those circumstances.
>>
>> -vlad
>>
>>>
>>> -	active = asoc->peer.active_path;
>>> -
>>> -	list_for_each_entry(chunk, &active->transmitted,
>>> -			transmitted_list) {
>>> -
>>> -		if (key == chunk->subh.data_hdr->tsn) {
>>> -			match = active;
>>> -			goto out;
>>> -		}
>>> -	}
>>> -
>>> -	/* If not found, go search all the other transports. */
>>>   	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
>>>   			transports) {
>>>
>>> -		if (transport == active)
>>> -			break;
>>>   		list_for_each_entry(chunk, &transport->transmitted,
>>>   				transmitted_list) {
>>>   			if (key == chunk->subh.data_hdr->tsn) {
>>>
>>
>>

[PATCH] sctp: optimize searching the active path for tsns

[Neil Horman]

SCTP currently attempts to optimize the search for tsns on a transport by first
checking the active_path, then searching alternate transports.  This operation
however is a bit convoluted, as we explicitly search the active path, then serch
all other transports, skipping the active path, when its detected.  Lets
optimize this by preforming a move to front on the transport_addr_list every
time the active_path is changed.  The active_path changes occur in relatively
non-critical paths, and doing so allows us to just search the
transport_addr_list in order, avoiding an extra conditional check in the
relatively hot tsn lookup path.  This also happens to fix a bug where we break
out of the for loop early in the tsn lookup.

CC: Xufeng Zhang <xufengzhang.main@gmail.com>
CC: vyasevich@gmail.com
CC: davem@davemloft.net
CC: netdev@vger.kernel.org
---
 net/sctp/associola.c | 31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)

diff --git a/net/sctp/associola.c b/net/sctp/associola.c
index 43cd0dd..7af96b3 100644
--- a/net/sctp/associola.c
+++ b/net/sctp/associola.c
@@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
 	 * user wants to use this new path.
 	 */
 	if ((transport->state == SCTP_ACTIVE) ||
-	    (transport->state == SCTP_UNKNOWN))
+	    (transport->state == SCTP_UNKNOWN)) {
+		list_del_rcu(&transport->transports);
+		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
 		asoc->peer.active_path = transport;
+	}
 
 	/*
 	 * SFR-CACC algorithm:
@@ -964,6 +967,10 @@ void sctp_assoc_control_transport(struct sctp_association *asoc,
 	}
 
 	/* Set the active and retran transports.  */
+	if (asoc->peer.active_path != first) {
+		list_del_rcu(first);
+		list_add_rcu(first, &asoc->peer.transport_addr_list);
+	}
 	asoc->peer.active_path = first;
 	asoc->peer.retran_path = second;
 }
@@ -1040,7 +1047,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
 struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
 					     __u32 tsn)
 {
-	struct sctp_transport *active;
 	struct sctp_transport *match;
 	struct sctp_transport *transport;
 	struct sctp_chunk *chunk;
@@ -1057,29 +1063,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
 	 * The general strategy is to search each transport's transmitted
 	 * list.   Return which transport this TSN lives on.
 	 *
-	 * Let's be hopeful and check the active_path first.
-	 * Another optimization would be to know if there is only one
-	 * outbound path and not have to look for the TSN at all.
+	 * Note, that sctp_assoc_set_primary does a move to front operation
+	 * on the active_path transport, so this code implicitly checks
+	 * the active_path first, as we most commonly expect to find our TSN
+	 * there.
 	 *
 	 */
 
-	active = asoc->peer.active_path;
-
-	list_for_each_entry(chunk, &active->transmitted,
-			transmitted_list) {
-
-		if (key == chunk->subh.data_hdr->tsn) {
-			match = active;
-			goto out;
-		}
-	}
-
-	/* If not found, go search all the other transports. */
 	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
 			transports) {
 
-		if (transport == active)
-			break;
 		list_for_each_entry(chunk, &transport->transmitted,
 				transmitted_list) {
 			if (key == chunk->subh.data_hdr->tsn) {
-- 
1.7.11.7

Re: [PATCH] sctp: optimize searching the active path for tsns

[Vlad Yasevich]

Hi Neil

On 03/12/2013 01:29 PM, Neil Horman wrote:
> SCTP currently attempts to optimize the search for tsns on a transport by first
> checking the active_path, then searching alternate transports.  This operation
> however is a bit convoluted, as we explicitly search the active path, then serch
> all other transports, skipping the active path, when its detected.  Lets
> optimize this by preforming a move to front on the transport_addr_list every
> time the active_path is changed.  The active_path changes occur in relatively
> non-critical paths, and doing so allows us to just search the
> transport_addr_list in order, avoiding an extra conditional check in the
> relatively hot tsn lookup path.  This also happens to fix a bug where we break
> out of the for loop early in the tsn lookup.
>
> CC: Xufeng Zhang <xufengzhang.main@gmail.com>
> CC: vyasevich@gmail.com
> CC: davem@davemloft.net
> CC: netdev@vger.kernel.org
> ---
>   net/sctp/associola.c | 31 ++++++++++++-------------------
>   1 file changed, 12 insertions(+), 19 deletions(-)
>
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 43cd0dd..7af96b3 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
>   	 * user wants to use this new path.
>   	 */
>   	if ((transport->state == SCTP_ACTIVE) ||
> -	    (transport->state == SCTP_UNKNOWN))
> +	    (transport->state == SCTP_UNKNOWN)) {
> +		list_del_rcu(&transport->transports);
> +		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
>   		asoc->peer.active_path = transport;
> +	}

What would happen if at the same time someone is walking the list 
through the proc interfaces?

Since you are effectively changing the .next pointer, I think it is 
possible to get a duplicate transport output essentially corrupting the 
output.

Personally, I don't think that this particular case is worth the 
optimization since we are trying to optimize a TSN search that only 
happens when ECNE chunk is received.  You say that it is a hot path.
Is ECNE really such a common occurrence?

Additionally, I don't think this is really an optimization as the 
current and new code do exactly the same thing:
  1) look at active path
  2) look at the rest of the paths

This just makes cleaner code at the expense of list shuffling.

-vlad
>
>   	/*
>   	 * SFR-CACC algorithm:
> @@ -964,6 +967,10 @@ void sctp_assoc_control_transport(struct sctp_association *asoc,
>   	}
>
>   	/* Set the active and retran transports.  */
> +	if (asoc->peer.active_path != first) {
> +		list_del_rcu(first);
> +		list_add_rcu(first, &asoc->peer.transport_addr_list);
> +	}
>   	asoc->peer.active_path = first;
>   	asoc->peer.retran_path = second;
>   }
> @@ -1040,7 +1047,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
>   struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>   					     __u32 tsn)
>   {
> -	struct sctp_transport *active;
>   	struct sctp_transport *match;
>   	struct sctp_transport *transport;
>   	struct sctp_chunk *chunk;
> @@ -1057,29 +1063,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>   	 * The general strategy is to search each transport's transmitted
>   	 * list.   Return which transport this TSN lives on.
>   	 *
> -	 * Let's be hopeful and check the active_path first.
> -	 * Another optimization would be to know if there is only one
> -	 * outbound path and not have to look for the TSN at all.
> +	 * Note, that sctp_assoc_set_primary does a move to front operation
> +	 * on the active_path transport, so this code implicitly checks
> +	 * the active_path first, as we most commonly expect to find our TSN
> +	 * there.
>   	 *
>   	 */
>
> -	active = asoc->peer.active_path;
> -
> -	list_for_each_entry(chunk, &active->transmitted,
> -			transmitted_list) {
> -
> -		if (key == chunk->subh.data_hdr->tsn) {
> -			match = active;
> -			goto out;
> -		}
> -	}
> -
> -	/* If not found, go search all the other transports. */
>   	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
>   			transports) {
>
> -		if (transport == active)
> -			break;
>   		list_for_each_entry(chunk, &transport->transmitted,
>   				transmitted_list) {
>   			if (key == chunk->subh.data_hdr->tsn) {
>

Re: [PATCH] sctp: optimize searching the active path for tsns

[Neil Horman]

On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
> Hi Neil
> 
> On 03/12/2013 01:29 PM, Neil Horman wrote:
> >SCTP currently attempts to optimize the search for tsns on a transport by first
> >checking the active_path, then searching alternate transports.  This operation
> >however is a bit convoluted, as we explicitly search the active path, then serch
> >all other transports, skipping the active path, when its detected.  Lets
> >optimize this by preforming a move to front on the transport_addr_list every
> >time the active_path is changed.  The active_path changes occur in relatively
> >non-critical paths, and doing so allows us to just search the
> >transport_addr_list in order, avoiding an extra conditional check in the
> >relatively hot tsn lookup path.  This also happens to fix a bug where we break
> >out of the for loop early in the tsn lookup.
> >
> >CC: Xufeng Zhang <xufengzhang.main@gmail.com>
> >CC: vyasevich@gmail.com
> >CC: davem@davemloft.net
> >CC: netdev@vger.kernel.org
> >---
> >  net/sctp/associola.c | 31 ++++++++++++-------------------
> >  1 file changed, 12 insertions(+), 19 deletions(-)
> >
> >diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> >index 43cd0dd..7af96b3 100644
> >--- a/net/sctp/associola.c
> >+++ b/net/sctp/associola.c
> >@@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
> >  	 * user wants to use this new path.
> >  	 */
> >  	if ((transport->state == SCTP_ACTIVE) ||
> >-	    (transport->state == SCTP_UNKNOWN))
> >+	    (transport->state == SCTP_UNKNOWN)) {
> >+		list_del_rcu(&transport->transports);
> >+		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> >  		asoc->peer.active_path = transport;
> >+	}
> 
> What would happen if at the same time someone is walking the list
> through the proc interfaces?
> 
> Since you are effectively changing the .next pointer, I think it is
> possible to get a duplicate transport output essentially corrupting
> the output.
> 
It would be the case, but you're using the rcu variants of the list_add macros
at all the points where we modify the list (some of which we do at call sites
right before we call set_primary, see sctp_assoc_add_peer, where
list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
problem without this patch.  In fact looking at it, our list access to
transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
apis to traverse the list.  I'll need to fix that first.

> Personally, I don't think that this particular case is worth the
> optimization since we are trying to optimize a TSN search that only
> happens when ECNE chunk is received.  You say that it is a hot path.
> Is ECNE really such a common occurrence?
> 
Not particularly, but I'm guessing its more used than the path that switches the
active path.  Plus its just more elegant, modifying the list so we don't have to
have two identical for loops in the lookup_tsn function, plus a check for the
transport that we already checked.

> Additionally, I don't think this is really an optimization as the
> current and new code do exactly the same thing:
>  1) look at active path
>  2) look at the rest of the paths
> 
Thats not the optimization, its trading where we do work in the interests of
making the more used path faster (we drop an if condition, and remove some
duplicated code).

> This just makes cleaner code at the expense of list shuffling.
> 
Yes, that sounds like a good trade to me. But as noted above, we probably need
to fix the transport_addr_list access first.
Neil

> -vlad
> >
> >  	/*
> >  	 * SFR-CACC algorithm:
> >@@ -964,6 +967,10 @@ void sctp_assoc_control_transport(struct sctp_association *asoc,
> >  	}
> >
> >  	/* Set the active and retran transports.  */
> >+	if (asoc->peer.active_path != first) {
> >+		list_del_rcu(first);
> >+		list_add_rcu(first, &asoc->peer.transport_addr_list);
> >+	}
> >  	asoc->peer.active_path = first;
> >  	asoc->peer.retran_path = second;
> >  }
> >@@ -1040,7 +1047,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
> >  struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
> >  					     __u32 tsn)
> >  {
> >-	struct sctp_transport *active;
> >  	struct sctp_transport *match;
> >  	struct sctp_transport *transport;
> >  	struct sctp_chunk *chunk;
> >@@ -1057,29 +1063,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
> >  	 * The general strategy is to search each transport's transmitted
> >  	 * list.   Return which transport this TSN lives on.
> >  	 *
> >-	 * Let's be hopeful and check the active_path first.
> >-	 * Another optimization would be to know if there is only one
> >-	 * outbound path and not have to look for the TSN at all.
> >+	 * Note, that sctp_assoc_set_primary does a move to front operation
> >+	 * on the active_path transport, so this code implicitly checks
> >+	 * the active_path first, as we most commonly expect to find our TSN
> >+	 * there.
> >  	 *
> >  	 */
> >
> >-	active = asoc->peer.active_path;
> >-
> >-	list_for_each_entry(chunk, &active->transmitted,
> >-			transmitted_list) {
> >-
> >-		if (key == chunk->subh.data_hdr->tsn) {
> >-			match = active;
> >-			goto out;
> >-		}
> >-	}
> >-
> >-	/* If not found, go search all the other transports. */
> >  	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
> >  			transports) {
> >
> >-		if (transport == active)
> >-			break;
> >  		list_for_each_entry(chunk, &transport->transmitted,
> >  				transmitted_list) {
> >  			if (key == chunk->subh.data_hdr->tsn) {
> >
> 
> 

Re: [PATCH] sctp: optimize searching the active path for tsns

[Vlad Yasevich]

On 03/12/2013 09:20 PM, Neil Horman wrote:
> On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
>> Hi Neil
>>
>> On 03/12/2013 01:29 PM, Neil Horman wrote:
>>> SCTP currently attempts to optimize the search for tsns on a transport by first
>>> checking the active_path, then searching alternate transports.  This operation
>>> however is a bit convoluted, as we explicitly search the active path, then serch
>>> all other transports, skipping the active path, when its detected.  Lets
>>> optimize this by preforming a move to front on the transport_addr_list every
>>> time the active_path is changed.  The active_path changes occur in relatively
>>> non-critical paths, and doing so allows us to just search the
>>> transport_addr_list in order, avoiding an extra conditional check in the
>>> relatively hot tsn lookup path.  This also happens to fix a bug where we break
>>> out of the for loop early in the tsn lookup.
>>>
>>> CC: Xufeng Zhang <xufengzhang.main@gmail.com>
>>> CC: vyasevich@gmail.com
>>> CC: davem@davemloft.net
>>> CC: netdev@vger.kernel.org
>>> ---
>>>   net/sctp/associola.c | 31 ++++++++++++-------------------
>>>   1 file changed, 12 insertions(+), 19 deletions(-)
>>>
>>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>>> index 43cd0dd..7af96b3 100644
>>> --- a/net/sctp/associola.c
>>> +++ b/net/sctp/associola.c
>>> @@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
>>>   	 * user wants to use this new path.
>>>   	 */
>>>   	if ((transport->state == SCTP_ACTIVE) ||
>>> -	    (transport->state == SCTP_UNKNOWN))
>>> +	    (transport->state == SCTP_UNKNOWN)) {
>>> +		list_del_rcu(&transport->transports);
>>> +		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
>>>   		asoc->peer.active_path = transport;
>>> +	}
>>
>> What would happen if at the same time someone is walking the list
>> through the proc interfaces?
>>
>> Since you are effectively changing the .next pointer, I think it is
>> possible to get a duplicate transport output essentially corrupting
>> the output.
>>
> It would be the case, but you're using the rcu variants of the list_add macros
> at all the points where we modify the list (some of which we do at call sites
> right before we call set_primary, see sctp_assoc_add_peer, where
> list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
> problem without this patch.  In fact looking at it, our list access to
> transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
> apis to traverse the list.  I'll need to fix that first.

As long as we are under lock, we don't need rcu variants for traversal. 
  The traversals done by the sctp_seq_ functions already use correct rcu 
variants.

I don't see this as a problem right now since we either delete the
transport, or add it.  We don't move it to a new location in the list.
With the move, what could happen is that while sctp_seq_ is printing
a transport, you might move it to another spot, and the when you grab
the .next pointer on the next iteration, it points to a completely 
different spot.

-vlad

>
>> Personally, I don't think that this particular case is worth the
>> optimization since we are trying to optimize a TSN search that only
>> happens when ECNE chunk is received.  You say that it is a hot path.
>> Is ECNE really such a common occurrence?
>>
> Not particularly, but I'm guessing its more used than the path that switches the
> active path.  Plus its just more elegant, modifying the list so we don't have to
> have two identical for loops in the lookup_tsn function, plus a check for the
> transport that we already checked.
>
>> Additionally, I don't think this is really an optimization as the
>> current and new code do exactly the same thing:
>>   1) look at active path
>>   2) look at the rest of the paths
>>
> Thats not the optimization, its trading where we do work in the interests of
> making the more used path faster (we drop an if condition, and remove some
> duplicated code).
>
>> This just makes cleaner code at the expense of list shuffling.
>>
> Yes, that sounds like a good trade to me. But as noted above, we probably need
> to fix the transport_addr_list access first.
> Neil
>
>> -vlad
>>>
>>>   	/*
>>>   	 * SFR-CACC algorithm:
>>> @@ -964,6 +967,10 @@ void sctp_assoc_control_transport(struct sctp_association *asoc,
>>>   	}
>>>
>>>   	/* Set the active and retran transports.  */
>>> +	if (asoc->peer.active_path != first) {
>>> +		list_del_rcu(first);
>>> +		list_add_rcu(first, &asoc->peer.transport_addr_list);
>>> +	}
>>>   	asoc->peer.active_path = first;
>>>   	asoc->peer.retran_path = second;
>>>   }
>>> @@ -1040,7 +1047,6 @@ struct sctp_chunk *sctp_get_ecne_prepend(struct sctp_association *asoc)
>>>   struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>>>   					     __u32 tsn)
>>>   {
>>> -	struct sctp_transport *active;
>>>   	struct sctp_transport *match;
>>>   	struct sctp_transport *transport;
>>>   	struct sctp_chunk *chunk;
>>> @@ -1057,29 +1063,16 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>>>   	 * The general strategy is to search each transport's transmitted
>>>   	 * list.   Return which transport this TSN lives on.
>>>   	 *
>>> -	 * Let's be hopeful and check the active_path first.
>>> -	 * Another optimization would be to know if there is only one
>>> -	 * outbound path and not have to look for the TSN at all.
>>> +	 * Note, that sctp_assoc_set_primary does a move to front operation
>>> +	 * on the active_path transport, so this code implicitly checks
>>> +	 * the active_path first, as we most commonly expect to find our TSN
>>> +	 * there.
>>>   	 *
>>>   	 */
>>>
>>> -	active = asoc->peer.active_path;
>>> -
>>> -	list_for_each_entry(chunk, &active->transmitted,
>>> -			transmitted_list) {
>>> -
>>> -		if (key == chunk->subh.data_hdr->tsn) {
>>> -			match = active;
>>> -			goto out;
>>> -		}
>>> -	}
>>> -
>>> -	/* If not found, go search all the other transports. */
>>>   	list_for_each_entry(transport, &asoc->peer.transport_addr_list,
>>>   			transports) {
>>>
>>> -		if (transport == active)
>>> -			break;
>>>   		list_for_each_entry(chunk, &transport->transmitted,
>>>   				transmitted_list) {
>>>   			if (key == chunk->subh.data_hdr->tsn) {
>>>
>>
>>

Re: [PATCH] sctp: optimize searching the active path for tsns

[Neil Horman]

On Tue, Mar 12, 2013 at 09:43:20PM -0400, Vlad Yasevich wrote:
> On 03/12/2013 09:20 PM, Neil Horman wrote:
> >On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
> >>Hi Neil
> >>
> >>On 03/12/2013 01:29 PM, Neil Horman wrote:
> >>>SCTP currently attempts to optimize the search for tsns on a transport by first
> >>>checking the active_path, then searching alternate transports.  This operation
> >>>however is a bit convoluted, as we explicitly search the active path, then serch
> >>>all other transports, skipping the active path, when its detected.  Lets
> >>>optimize this by preforming a move to front on the transport_addr_list every
> >>>time the active_path is changed.  The active_path changes occur in relatively
> >>>non-critical paths, and doing so allows us to just search the
> >>>transport_addr_list in order, avoiding an extra conditional check in the
> >>>relatively hot tsn lookup path.  This also happens to fix a bug where we break
> >>>out of the for loop early in the tsn lookup.
> >>>
> >>>CC: Xufeng Zhang <xufengzhang.main@gmail.com>
> >>>CC: vyasevich@gmail.com
> >>>CC: davem@davemloft.net
> >>>CC: netdev@vger.kernel.org
> >>>---
> >>>  net/sctp/associola.c | 31 ++++++++++++-------------------
> >>>  1 file changed, 12 insertions(+), 19 deletions(-)
> >>>
> >>>diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> >>>index 43cd0dd..7af96b3 100644
> >>>--- a/net/sctp/associola.c
> >>>+++ b/net/sctp/associola.c
> >>>@@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
> >>>  	 * user wants to use this new path.
> >>>  	 */
> >>>  	if ((transport->state == SCTP_ACTIVE) ||
> >>>-	    (transport->state == SCTP_UNKNOWN))
> >>>+	    (transport->state == SCTP_UNKNOWN)) {
> >>>+		list_del_rcu(&transport->transports);
> >>>+		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> >>>  		asoc->peer.active_path = transport;
> >>>+	}
> >>
> >>What would happen if at the same time someone is walking the list
> >>through the proc interfaces?
> >>
> >>Since you are effectively changing the .next pointer, I think it is
> >>possible to get a duplicate transport output essentially corrupting
> >>the output.
> >>
> >It would be the case, but you're using the rcu variants of the list_add macros
> >at all the points where we modify the list (some of which we do at call sites
> >right before we call set_primary, see sctp_assoc_add_peer, where
> >list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
> >problem without this patch.  In fact looking at it, our list access to
> >transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
> >apis to traverse the list.  I'll need to fix that first.
> 
> As long as we are under lock, we don't need rcu variants for
> traversal.  The traversals done by the sctp_seq_ functions already
> use correct rcu variants.
> 
> I don't see this as a problem right now since we either delete the
> transport, or add it.  We don't move it to a new location in the list.
> With the move, what could happen is that while sctp_seq_ is printing
> a transport, you might move it to another spot, and the when you grab
> the .next pointer on the next iteration, it points to a completely
> different spot.
> 
Ok, I see what you're saying, and looking at the seq code, with your description
I see how we're using half the rcu code to allow the proc interface to avoid
grabbing the socket lock.  But this just strikes me a poor coding.  Its
confusing to say the least, and begging for mistakes like the one I just made to
be made again.  Regardless of necessisty, it seems to me the code would be both
more readable and understandible if we modified it so that we used the rcu api
consistently to access that list.
Neil

Re: [PATCH] sctp: optimize searching the active path for tsns

[Vlad Yasevich]

On 03/13/2013 09:28 AM, Neil Horman wrote:
> On Tue, Mar 12, 2013 at 09:43:20PM -0400, Vlad Yasevich wrote:
>> On 03/12/2013 09:20 PM, Neil Horman wrote:
>>> On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
>>>> Hi Neil
>>>>
>>>> On 03/12/2013 01:29 PM, Neil Horman wrote:
>>>>> SCTP currently attempts to optimize the search for tsns on a transport by first
>>>>> checking the active_path, then searching alternate transports.  This operation
>>>>> however is a bit convoluted, as we explicitly search the active path, then serch
>>>>> all other transports, skipping the active path, when its detected.  Lets
>>>>> optimize this by preforming a move to front on the transport_addr_list every
>>>>> time the active_path is changed.  The active_path changes occur in relatively
>>>>> non-critical paths, and doing so allows us to just search the
>>>>> transport_addr_list in order, avoiding an extra conditional check in the
>>>>> relatively hot tsn lookup path.  This also happens to fix a bug where we break
>>>>> out of the for loop early in the tsn lookup.
>>>>>
>>>>> CC: Xufeng Zhang <xufengzhang.main@gmail.com>
>>>>> CC: vyasevich@gmail.com
>>>>> CC: davem@davemloft.net
>>>>> CC: netdev@vger.kernel.org
>>>>> ---
>>>>>   net/sctp/associola.c | 31 ++++++++++++-------------------
>>>>>   1 file changed, 12 insertions(+), 19 deletions(-)
>>>>>
>>>>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>>>>> index 43cd0dd..7af96b3 100644
>>>>> --- a/net/sctp/associola.c
>>>>> +++ b/net/sctp/associola.c
>>>>> @@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
>>>>>   	 * user wants to use this new path.
>>>>>   	 */
>>>>>   	if ((transport->state == SCTP_ACTIVE) ||
>>>>> -	    (transport->state == SCTP_UNKNOWN))
>>>>> +	    (transport->state == SCTP_UNKNOWN)) {
>>>>> +		list_del_rcu(&transport->transports);
>>>>> +		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
>>>>>   		asoc->peer.active_path = transport;
>>>>> +	}
>>>>
>>>> What would happen if at the same time someone is walking the list
>>>> through the proc interfaces?
>>>>
>>>> Since you are effectively changing the .next pointer, I think it is
>>>> possible to get a duplicate transport output essentially corrupting
>>>> the output.
>>>>
>>> It would be the case, but you're using the rcu variants of the list_add macros
>>> at all the points where we modify the list (some of which we do at call sites
>>> right before we call set_primary, see sctp_assoc_add_peer, where
>>> list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
>>> problem without this patch.  In fact looking at it, our list access to
>>> transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
>>> apis to traverse the list.  I'll need to fix that first.
>>
>> As long as we are under lock, we don't need rcu variants for
>> traversal.  The traversals done by the sctp_seq_ functions already
>> use correct rcu variants.
>>
>> I don't see this as a problem right now since we either delete the
>> transport, or add it.  We don't move it to a new location in the list.
>> With the move, what could happen is that while sctp_seq_ is printing
>> a transport, you might move it to another spot, and the when you grab
>> the .next pointer on the next iteration, it points to a completely
>> different spot.
>>
> Ok, I see what you're saying, and looking at the seq code, with your description
> I see how we're using half the rcu code to allow the proc interface to avoid
> grabbing the socket lock.  But this just strikes me a poor coding.  Its
> confusing to say the least, and begging for mistakes like the one I just made to
> be made again.  Regardless of necessisty, it seems to me the code would be both
> more readable and understandible if we modified it so that we used the rcu api
> consistently to access that list.
> Neil
>

Can you elaborate a bit on why you believe we are using half of the rcu 
code?

I think to support the move operation you are proposing here, you need 
something like
	list_for_each_entry_safe_rcu()

where the .next pointer is fetched through rcu_dereference() to guard 
against its possible.

But even that would only work if the move happens to the the earlier 
spot (like head) of the list.  If the move happens to the later part
of the list (like tail), you may end up visiting the same list node
twice.

I think rcu simply can't guard against this.

-vlad

Re: [PATCH] sctp: optimize searching the active path for tsns

[Neil Horman]

On Wed, Mar 13, 2013 at 10:06:43AM -0400, Vlad Yasevich wrote:
> On 03/13/2013 09:28 AM, Neil Horman wrote:
> >On Tue, Mar 12, 2013 at 09:43:20PM -0400, Vlad Yasevich wrote:
> >>On 03/12/2013 09:20 PM, Neil Horman wrote:
> >>>On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
> >>>>Hi Neil
> >>>>
> >>>>On 03/12/2013 01:29 PM, Neil Horman wrote:
> >>>>>SCTP currently attempts to optimize the search for tsns on a transport by first
> >>>>>checking the active_path, then searching alternate transports.  This operation
> >>>>>however is a bit convoluted, as we explicitly search the active path, then serch
> >>>>>all other transports, skipping the active path, when its detected.  Lets
> >>>>>optimize this by preforming a move to front on the transport_addr_list every
> >>>>>time the active_path is changed.  The active_path changes occur in relatively
> >>>>>non-critical paths, and doing so allows us to just search the
> >>>>>transport_addr_list in order, avoiding an extra conditional check in the
> >>>>>relatively hot tsn lookup path.  This also happens to fix a bug where we break
> >>>>>out of the for loop early in the tsn lookup.
> >>>>>
> >>>>>CC: Xufeng Zhang <xufengzhang.main@gmail.com>
> >>>>>CC: vyasevich@gmail.com
> >>>>>CC: davem@davemloft.net
> >>>>>CC: netdev@vger.kernel.org
> >>>>>---
> >>>>>  net/sctp/associola.c | 31 ++++++++++++-------------------
> >>>>>  1 file changed, 12 insertions(+), 19 deletions(-)
> >>>>>
> >>>>>diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> >>>>>index 43cd0dd..7af96b3 100644
> >>>>>--- a/net/sctp/associola.c
> >>>>>+++ b/net/sctp/associola.c
> >>>>>@@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
> >>>>>  	 * user wants to use this new path.
> >>>>>  	 */
> >>>>>  	if ((transport->state == SCTP_ACTIVE) ||
> >>>>>-	    (transport->state == SCTP_UNKNOWN))
> >>>>>+	    (transport->state == SCTP_UNKNOWN)) {
> >>>>>+		list_del_rcu(&transport->transports);
> >>>>>+		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> >>>>>  		asoc->peer.active_path = transport;
> >>>>>+	}
> >>>>
> >>>>What would happen if at the same time someone is walking the list
> >>>>through the proc interfaces?
> >>>>
> >>>>Since you are effectively changing the .next pointer, I think it is
> >>>>possible to get a duplicate transport output essentially corrupting
> >>>>the output.
> >>>>
> >>>It would be the case, but you're using the rcu variants of the list_add macros
> >>>at all the points where we modify the list (some of which we do at call sites
> >>>right before we call set_primary, see sctp_assoc_add_peer, where
> >>>list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
> >>>problem without this patch.  In fact looking at it, our list access to
> >>>transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
> >>>apis to traverse the list.  I'll need to fix that first.
> >>
> >>As long as we are under lock, we don't need rcu variants for
> >>traversal.  The traversals done by the sctp_seq_ functions already
> >>use correct rcu variants.
> >>
> >>I don't see this as a problem right now since we either delete the
> >>transport, or add it.  We don't move it to a new location in the list.
> >>With the move, what could happen is that while sctp_seq_ is printing
> >>a transport, you might move it to another spot, and the when you grab
> >>the .next pointer on the next iteration, it points to a completely
> >>different spot.
> >>
> >Ok, I see what you're saying, and looking at the seq code, with your description
> >I see how we're using half the rcu code to allow the proc interface to avoid
> >grabbing the socket lock.  But this just strikes me a poor coding.  Its
> >confusing to say the least, and begging for mistakes like the one I just made to
> >be made again.  Regardless of necessisty, it seems to me the code would be both
> >more readable and understandible if we modified it so that we used the rcu api
> >consistently to access that list.
> >Neil
> >
> 
> Can you elaborate a bit on why you believe we are using half of the
> rcu code?
> 
We're using the rcu list add/del apis on the write side when
we modify the transport_addr_list, but we're using the non-rcu primitives on the
read side, save for the proc interface.  Granted that generally safe, exepct for
any case in which you do exactly what we were speaking about above.  I know were
not doing that now, but it seems to me it would be better to use the rcu
primitives consistently, so that it was clear how to access the list.  It would
prevent mistakes like the one I just made, as well as other possible mistakes,
in which future coding errors.

> I think to support the move operation you are proposing here, you
> need something like
> 	list_for_each_entry_safe_rcu()
> 
Not to the best of my knoweldge.  Consistent use of the rcu list access
primitives is safe against rcu list mutation primitives, as long as the read
side is protected by the rcu_read_lock.  As long as thats locked, any mutations
won't be seen by the read context until after we exit the read side critical
section.

> where the .next pointer is fetched through rcu_dereference() to
> guard against its possible.
> 
You won't see the updated next pointer until the read critical side ends.  Thats
why you need to do an rcu_read_lock in addition to grabbing the socket lock.

> But even that would only work if the move happens to the the earlier
> spot (like head) of the list.  If the move happens to the later part
> of the list (like tail), you may end up visiting the same list node
> twice.
> 
Again, not if you hold the rcu_read_lock.  Doing so creates a quiescent point in
which the status of the list is held until such time as read side critical
section exits.  The move (specifically the delete and the add) won't be seen by
the reading context until that quiescent point completes, which by definition is
when that reader is done reading.

Neil

> I think rcu simply can't guard against this.
> 
> -vlad
> 
> 

Re: [PATCH] sctp: optimize searching the active path for tsns

[Vlad Yasevich]

On 03/13/2013 10:21 AM, Neil Horman wrote:
> On Wed, Mar 13, 2013 at 10:06:43AM -0400, Vlad Yasevich wrote:
>> On 03/13/2013 09:28 AM, Neil Horman wrote:
>>> On Tue, Mar 12, 2013 at 09:43:20PM -0400, Vlad Yasevich wrote:
>>>> On 03/12/2013 09:20 PM, Neil Horman wrote:
>>>>> On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
>>>>>> Hi Neil
>>>>>>
>>>>>> On 03/12/2013 01:29 PM, Neil Horman wrote:
>>>>>>> SCTP currently attempts to optimize the search for tsns on a transport by first
>>>>>>> checking the active_path, then searching alternate transports.  This operation
>>>>>>> however is a bit convoluted, as we explicitly search the active path, then serch
>>>>>>> all other transports, skipping the active path, when its detected.  Lets
>>>>>>> optimize this by preforming a move to front on the transport_addr_list every
>>>>>>> time the active_path is changed.  The active_path changes occur in relatively
>>>>>>> non-critical paths, and doing so allows us to just search the
>>>>>>> transport_addr_list in order, avoiding an extra conditional check in the
>>>>>>> relatively hot tsn lookup path.  This also happens to fix a bug where we break
>>>>>>> out of the for loop early in the tsn lookup.
>>>>>>>
>>>>>>> CC: Xufeng Zhang <xufengzhang.main@gmail.com>
>>>>>>> CC: vyasevich@gmail.com
>>>>>>> CC: davem@davemloft.net
>>>>>>> CC: netdev@vger.kernel.org
>>>>>>> ---
>>>>>>>   net/sctp/associola.c | 31 ++++++++++++-------------------
>>>>>>>   1 file changed, 12 insertions(+), 19 deletions(-)
>>>>>>>
>>>>>>> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
>>>>>>> index 43cd0dd..7af96b3 100644
>>>>>>> --- a/net/sctp/associola.c
>>>>>>> +++ b/net/sctp/associola.c
>>>>>>> @@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
>>>>>>>   	 * user wants to use this new path.
>>>>>>>   	 */
>>>>>>>   	if ((transport->state == SCTP_ACTIVE) ||
>>>>>>> -	    (transport->state == SCTP_UNKNOWN))
>>>>>>> +	    (transport->state == SCTP_UNKNOWN)) {
>>>>>>> +		list_del_rcu(&transport->transports);
>>>>>>> +		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
>>>>>>>   		asoc->peer.active_path = transport;
>>>>>>> +	}
>>>>>>
>>>>>> What would happen if at the same time someone is walking the list
>>>>>> through the proc interfaces?
>>>>>>
>>>>>> Since you are effectively changing the .next pointer, I think it is
>>>>>> possible to get a duplicate transport output essentially corrupting
>>>>>> the output.
>>>>>>
>>>>> It would be the case, but you're using the rcu variants of the list_add macros
>>>>> at all the points where we modify the list (some of which we do at call sites
>>>>> right before we call set_primary, see sctp_assoc_add_peer, where
>>>>> list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
>>>>> problem without this patch.  In fact looking at it, our list access to
>>>>> transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
>>>>> apis to traverse the list.  I'll need to fix that first.
>>>>
>>>> As long as we are under lock, we don't need rcu variants for
>>>> traversal.  The traversals done by the sctp_seq_ functions already
>>>> use correct rcu variants.
>>>>
>>>> I don't see this as a problem right now since we either delete the
>>>> transport, or add it.  We don't move it to a new location in the list.
>>>> With the move, what could happen is that while sctp_seq_ is printing
>>>> a transport, you might move it to another spot, and the when you grab
>>>> the .next pointer on the next iteration, it points to a completely
>>>> different spot.
>>>>
>>> Ok, I see what you're saying, and looking at the seq code, with your description
>>> I see how we're using half the rcu code to allow the proc interface to avoid
>>> grabbing the socket lock.  But this just strikes me a poor coding.  Its
>>> confusing to say the least, and begging for mistakes like the one I just made to
>>> be made again.  Regardless of necessisty, it seems to me the code would be both
>>> more readable and understandible if we modified it so that we used the rcu api
>>> consistently to access that list.
>>> Neil
>>>
>>
>> Can you elaborate a bit on why you believe we are using half of the
>> rcu code?
>>
> We're using the rcu list add/del apis on the write side when
> we modify the transport_addr_list, but we're using the non-rcu primitives on the
>  read side, save for the proc interface.

What other lockless read side do we have?


>  Granted that generally safe, exepct for
> any case in which you do exactly what we were speaking about above.  I know were
> not doing that now, but it seems to me it would be better to use the rcu
> primitives consistently, so that it was clear how to access the list.  It would
> prevent mistakes like the one I just made, as well as other possible mistakes,
> in which future coding errors.

It would cost extra barriers that are completely unnecessary.

>
>> I think to support the move operation you are proposing here, you
>> need something like
>> 	list_for_each_entry_safe_rcu()
>>
> Not to the best of my knoweldge.  Consistent use of the rcu list access
> primitives is safe against rcu list mutation primitives, as long as the read
> side is protected by the rcu_read_lock.  As long as thats locked, any mutations
> won't be seen by the read context until after we exit the read side critical
> section.

Not the way I understand rcu.  rcu_read_lock will not prevent access to 
new contents.  This is why list_del_rcu() is careful not to change the 
.next pointer.
In the case you are proposing, if the reader is current processing entry 
X, and the writer, at the same time moves X to another place, then
at the time the reader looks at X.next, it may point to the new place. 
If that happens, you've now corrupted output.

>
>> where the .next pointer is fetched through rcu_dereference() to
>> guard against its possible.
>>
> You won't see the updated next pointer until the read critical side ends.  Thats
> why you need to do an rcu_read_lock in addition to grabbing the socket lock.
>

No, that's now how it works.  It's based on memory barriers at the time 
of deletion/addition and dereference.

-vlad

>> But even that would only work if the move happens to the the earlier
>> spot (like head) of the list.  If the move happens to the later part
>> of the list (like tail), you may end up visiting the same list node
>> twice.
>>
> Again, not if you hold the rcu_read_lock.  Doing so creates a quiescent point in
> which the status of the list is held until such time as read side critical
> section exits.  The move (specifically the delete and the add) won't be seen by
> the reading context until that quiescent point completes, which by definition is
> when that reader is done reading.
>
> Neil
>
>> I think rcu simply can't guard against this.
>>
>> -vlad
>>
>>
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [PATCH] sctp: optimize searching the active path for tsns

[Paul E. McKenney]

On Wed, Mar 13, 2013 at 09:28:09AM -0400, Neil Horman wrote:
> On Tue, Mar 12, 2013 at 09:43:20PM -0400, Vlad Yasevich wrote:
> > On 03/12/2013 09:20 PM, Neil Horman wrote:
> > >On Tue, Mar 12, 2013 at 05:01:50PM -0400, Vlad Yasevich wrote:
> > >>Hi Neil
> > >>
> > >>On 03/12/2013 01:29 PM, Neil Horman wrote:
> > >>>SCTP currently attempts to optimize the search for tsns on a transport by first
> > >>>checking the active_path, then searching alternate transports.  This operation
> > >>>however is a bit convoluted, as we explicitly search the active path, then serch
> > >>>all other transports, skipping the active path, when its detected.  Lets
> > >>>optimize this by preforming a move to front on the transport_addr_list every
> > >>>time the active_path is changed.  The active_path changes occur in relatively
> > >>>non-critical paths, and doing so allows us to just search the
> > >>>transport_addr_list in order, avoiding an extra conditional check in the
> > >>>relatively hot tsn lookup path.  This also happens to fix a bug where we break
> > >>>out of the for loop early in the tsn lookup.
> > >>>
> > >>>CC: Xufeng Zhang <xufengzhang.main@gmail.com>
> > >>>CC: vyasevich@gmail.com
> > >>>CC: davem@davemloft.net
> > >>>CC: netdev@vger.kernel.org
> > >>>---
> > >>>  net/sctp/associola.c | 31 ++++++++++++-------------------
> > >>>  1 file changed, 12 insertions(+), 19 deletions(-)
> > >>>
> > >>>diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> > >>>index 43cd0dd..7af96b3 100644
> > >>>--- a/net/sctp/associola.c
> > >>>+++ b/net/sctp/associola.c
> > >>>@@ -513,8 +513,11 @@ void sctp_assoc_set_primary(struct sctp_association *asoc,
> > >>>  	 * user wants to use this new path.
> > >>>  	 */
> > >>>  	if ((transport->state == SCTP_ACTIVE) ||
> > >>>-	    (transport->state == SCTP_UNKNOWN))
> > >>>+	    (transport->state == SCTP_UNKNOWN)) {
> > >>>+		list_del_rcu(&transport->transports);
> > >>>+		list_add_rcu(&transport->transports, &asoc->peer.transport_addr_list);
> > >>>  		asoc->peer.active_path = transport;
> > >>>+	}
> > >>
> > >>What would happen if at the same time someone is walking the list
> > >>through the proc interfaces?
> > >>
> > >>Since you are effectively changing the .next pointer, I think it is
> > >>possible to get a duplicate transport output essentially corrupting
> > >>the output.
> > >>
> > >It would be the case, but you're using the rcu variants of the list_add macros
> > >at all the points where we modify the list (some of which we do at call sites
> > >right before we call set_primary, see sctp_assoc_add_peer, where
> > >list_add_tail_rcu also modifies a next pointer).  So if this is a problem, its a
> > >problem without this patch.  In fact looking at it, our list access to
> > >transport_addr_list is broken, as we use rcu apis to modify the list but non-rcu
> > >apis to traverse the list.  I'll need to fix that first.
> > 
> > As long as we are under lock, we don't need rcu variants for
> > traversal.  The traversals done by the sctp_seq_ functions already
> > use correct rcu variants.
> > 
> > I don't see this as a problem right now since we either delete the
> > transport, or add it.  We don't move it to a new location in the list.
> > With the move, what could happen is that while sctp_seq_ is printing
> > a transport, you might move it to another spot, and the when you grab
> > the .next pointer on the next iteration, it points to a completely
> > different spot.
> > 
> Ok, I see what you're saying, and looking at the seq code, with your description
> I see how we're using half the rcu code to allow the proc interface to avoid
> grabbing the socket lock.  But this just strikes me a poor coding.  Its
> confusing to say the least, and begging for mistakes like the one I just made to
> be made again.  Regardless of necessisty, it seems to me the code would be both
> more readable and understandible if we modified it so that we used the rcu api
> consistently to access that list.

Not sure exactly what the desired behavior is, but if the idea is to be
able to move an element within an RCU-protected list without dragging
RCU readers along (and thus having the readers possibly traverse parts
of the list multiple times), here are some ways of accomplishing this:

o	Insert a synchronize_rcu() between the removal and the
	reinsertion (which means upgrading any spinlocks to mutexes
	or some such).

o	Instead of moving the object, insert a copy after removing
	the old version.  Any readers referencing the old copy would
	continue down the list.  A reader traversing the list between
	the removal of the original and the insertion of the copy might
	miss the moving element.

	You could instead insert the copy before removing the original,
	so that both copies are in the list for a bit, in which case a
	concurrent reader might see both.

o	If it is OK to miss elements but bad to repeat them, instead
	of moving the selected element to the beginning of the list,
	move all items preceding that element to the end of the list.

o	Have a pair of list_heads in each object, along with an index
	telling which of them pair readers should use.  Make the change
	using the non-current set of list_heads.  Flip the index.
	Wait for a grace period before allowing the next update.

On the off-chance that any of this is helpful...  There are probably
other ways of making this work as well.

							Thanx, Paul

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Neil Horman]

On Fri, Mar 08, 2013 at 03:39:37PM +0800, Xufeng Zhang wrote:
> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
> was sent on, if not found in the active_path transport, then go search
> all the other transports in the peer's transport_addr_list, however, we
> should continue to the next entry rather than break the loop when meet
> the active_path transport.
> 
> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
> ---
>  net/sctp/associola.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 43cd0dd..d2709e2 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>  			transports) {
>  
>  		if (transport == active)
> -			break;
> +			continue;
>  		list_for_each_entry(chunk, &transport->transmitted,
>  				transmitted_list) {
>  			if (key == chunk->subh.data_hdr->tsn) {
> -- 
> 1.7.0.2
> 
Based on discussion with Vlad, it seems theres arguably some work to do on
access to the transport_addr_list before my solution is viable, so until I get
to that I'm acking this patch.

Acked-by: Neil Horman <nhorman@tuxdriver.com>

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[Vlad Yasevich]

On 03/08/2013 02:39 AM, Xufeng Zhang wrote:
> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
> was sent on, if not found in the active_path transport, then go search
> all the other transports in the peer's transport_addr_list, however, we
> should continue to the next entry rather than break the loop when meet
> the active_path transport.
>
> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
> ---
>   net/sctp/associola.c |    2 +-
>   1 files changed, 1 insertions(+), 1 deletions(-)
>
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 43cd0dd..d2709e2 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -1079,7 +1079,7 @@ struct sctp_transport *sctp_assoc_lookup_tsn(struct sctp_association *asoc,
>   			transports) {
>
>   		if (transport == active)
> -			break;
> +			continue;
>   		list_for_each_entry(chunk, &transport->transmitted,
>   				transmitted_list) {
>   			if (key == chunk->subh.data_hdr->tsn) {
>

Acked-by: Vlad Yasevich <vyasevich@gmail.com>

-vlad

Re: [PATCH] sctp: don't break the loop while meeting the active_path so as to find the matched transport

[David Miller]

From: Vlad Yasevich <vyasevich@gmail.com>
Date: Wed, 13 Mar 2013 09:52:48 -0400

> On 03/08/2013 02:39 AM, Xufeng Zhang wrote:
>> sctp_assoc_lookup_tsn() function searchs which transport a certain TSN
>> was sent on, if not found in the active_path transport, then go search
>> all the other transports in the peer's transport_addr_list, however,
>> we
>> should continue to the next entry rather than break the loop when meet
>> the active_path transport.
>>
>> Signed-off-by: Xufeng Zhang <xufeng.zhang@windriver.com>
 ...
> Acked-by: Neil Horman <nhorman@tuxdriver.com>
...
> Acked-by: Vlad Yasevich <vyasevich@gmail.com>

Applied, thanks everyone.