Report: feat negot state

Report: feat negot state

[Arnaldo Carvalho de Melo]

With the current patch, available at:

http://oops.ghostprotocols.net:81/acme/dccp_minisock.patch

Simple ttcp session transmitting 5 packets:

127.0.0.1.4496 > 127.0.0.1.5001: request  <change_l ack_ratio 2,
change_r ccid 2, change_l ccid 2>
127.0.0.1.5001 > 127.0.0.1.4496: response <change_l ack_ratio 2,
confirm_l ccid 2, confirm_r ccid 2, confirm_r ack_ratio 2>
127.0.0.1.4496 > 127.0.0.1.5001: ack      <nop, confirm_r ack_ratio 2,
ack_vector0 0x00, elapsed_time 108>
127.0.0.1.4496 > 127.0.0.1.5001: dataack  <nop, nop, ack_vector0 0x00,
elapsed_time 16857, ndp_count 1>
127.0.0.1.5001 > 127.0.0.1.4496: ack      <nop, ack_vector0 0x01,
elapsed_time 20>
127.0.0.1.4496 > 127.0.0.1.5001: dataack  <nop, ack_vector0 0x00,
elapsed_time 2495>
127.0.0.1.5001 > 127.0.0.1.4496: ack      <nop, nop, ack_vector0 0x00,
elapsed_time 15, ndp_count 1>
127.0.0.1.4496 > 127.0.0.1.5001: dataack  <nop, ack_vector0 0x00,
elapsed_time 2404>
127.0.0.1.5001 > 127.0.0.1.4496: ack      <nop, nop, ack_vector0 0x00,
elapsed_time 13, ndp_count 2>
127.0.0.1.4496 > 127.0.0.1.5001: dataack  <nop, ack_vector0 0x00,
elapsed_time 2327>
127.0.0.1.5001 > 127.0.0.1.4496: ack      <nop, nop, ack_vector0 0x00,
elapsed_time 14, ndp_count 3>
127.0.0.1.4496 > 127.0.0.1.5001: dataack  <nop, ack_vector0 0x00,
elapsed_time 2077>
127.0.0.1.5001 > 127.0.0.1.4496: ack      <nop, nop, ack_vector0 0x00,
elapsed_time 13, ndp_count 4>
127.0.0.1.4496 > 127.0.0.1.5001: close    <nop, ack_vector0 0x00,
elapsed_time 8425>
127.0.0.1.5001 > 127.0.0.1.4496: reset    <nop, nop, ack_vector0 0x00,
elapsed_time 1121, ndp_count 5>

Still work in progress, requires more testing, but gets feature
negotiation down to
dccp_request_sock level, still need to possibly move more stuff to
dccp_minisock, that
is (or should) be the bare minimum needed to do feature negotiation
when we still don't
have a full blown socket (struct dccp_sock), the previous code is
wrong as we can't use
the listening sock to do feature negotiation at all, so we have to
store the feat negot
state in the minisock that represents the embryonic connection (struct
dccp_request_sock),
and later move this state (in dccp_create_openreq_child) to the newly
inet_csk_cloned
full socket.

And I don't like the many allocations still present, even having
reduced some of the
previous ones I think perhaps we should use a buffer like when we encode the
options in a dccp packet, will try this later.

I'm going to have some sleep now, so this is just for you guys to take
a look at the
current status, more work is needed and the patch has unrelated
changes, will split
when I get satisfied with this stuff.

G'night,

- Arnaldo

Re: Report: feat negot state

[Ian McDonald]

On 3/7/06, Arnaldo Carvalho de Melo <acme@ghostprotocols.net> wrote:
> With the current patch, available at:
>
> http://oops.ghostprotocols.net:81/acme/dccp_minisock.patch
>
Looks good from having a quick read of code and I like some of the
other little tidyups too (int to u32 for example, checking sk value).

Ian
--
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand

Re: Report: feat negot state

[Andrea Bittau]

On Tue, Mar 07, 2006 at 12:05:51AM -0300, Arnaldo Carvalho de Melo wrote:
> With the current patch, available at:
> 
> http://oops.ghostprotocols.net:81/acme/dccp_minisock.patch


Great work.  I see you've been busy lately =D  Anyway, I'll comment inline, and
then write a bunch of random thoughts at the end.


+	struct list_head	     dccpms_pend;
+	struct list_head	     dccpms_conf;

good.  only 2 queues:  one for "pending changes" and one for confirms.  You
might have wondered why i had a "confirm" inside the pending change queue
itself, and then a seperate confirm queue.

Basically, because i coded server priority features first, and then
non-negotiable.  With NN features, you need to send confirms even for stuff you
don't know about [or something like that] so i didn't know where to shove the
confirm =D

Anyway, it's much better like this [i was planning to do it at some point, but i
just "died"]
 
 
 	/* Check if nothing is being changed. */
-	if (ccid_nr = new_ccid_nr)
+	/* XXX handle multibyte values */
+	if (ccid_nr = *val)
 		return 0;


ccid can only be 1 byte.  kill comment.  assert(len = 1);

-
-	new_ccid = ccid_new(new_ccid_nr, sk, rx, GFP_ATOMIC);
+#if 0
+	new_ccid = ccid_new(*val, sk, rx, GFP_ATOMIC);
 	if (new_ccid = NULL)
 		return -ENOMEM;


that if 0 is only for your debug right?
		
 	
 	switch (feat) {
 	case DCCPF_CCID:
-		return dccp_feat_update_ccid(sk, type, val);
+		return dccp_feat_update_ccid(dmsk, type, val, len);

update_ccid() shouldn't care about len.  it knows the length of ccid.  Well I
guess it depends on who you leave it to do sanity checks.  But by the time the
option is "negotiated", errors would have been spotted by upper layers.  [For
example when doing server priority reconciliation.]

+	feat->dccpf_conf_idx = sidx;
+	feat->dccpf_conf_len = rlen;

conf_len should be the length of the option itself, not the length of the
feature list.  I guess this will be sorted when we work on the multi-byte patch.

 	
 	/* update the option on our side [we are about to send the confirm] */
-	rc = dccp_feat_update(sk, opt->dccpop_type, opt->dccpop_feat, *res);
+	rc = dccp_feat_update(dmsk, feat->dccpf_type, feat->dccpf_feat,
+			      spref + sidx, 1);

similar problem.  Hardcoded feature length of 1.  perhaps it should be
feat->dccpf_conf_len.

 

+			feat->dccpf_conf_idx = 0;
+			feat->dccpf_conf_len = 1;

should the index be sidx?  Also, same problem with legnth.


-	/* generate the confirm [if required] */
-	dccp_feat_flush_confirm(sk);
-
+	/* Confirms will be sent on the next packet */

yea but what if the next packet is never sent?  I.e. uni-directional connection.
There should be a mechanism to  force an ack after X amount of time if the dude
doesn't talk.


+	list_for_each_entry(feat, &dmsk->dccpms_pend, dccpf_node) {
+		if (!dccp_feat_negotiated(feat) &&
+		    feat->dccpf_type = t &&
+		    feat->dccpf_feat = feature) {
+			feat->dccpf_conf_idx = 0;
+			feat->dccpf_conf_len = len;

is the index correct?  Also, len should be length of option not of preference
list.  Confirms will contain confirmed value + pref list.

+			/* We got a confirmation: change the option */
+			dccp_feat_update(dmsk, feat->dccpf_type,
+					 feat->dccpf_feat, val, len);

i'm not sure feat_update should care about length [unless IT sanity checks].  If
so, len should be of value, not pref list.

-	if (all_confirmed) {
-		dccp_pr_debug("clear feat negotiation timer %p\n", sk);
-		inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS);
 	}

so what's the story with timers?  Did you kill them?  Will changes be
re-transmitted?

 
+	rc = dccp_feat_change(dmsk, DCCPO_CHANGE_L, DCCPF_ACK_RATIO,
+			      &dmsk->dccpms_ack_ratio, 1, gfp);

ack ratio is 2 bytes i think.


+	case DCCPF_CCID:
+		return len >= sizeof(__u8);

should it also have an && <= number_of_ccids at this point?  Breaks modular
architecture =D  But you hardcoded MAX_FEATURE_VALUE or whatever it's called
anyway =D


 	/* confirm any options [NN opts] */
-	list_for_each_entry_safe(opt, next, &dp->dccps_options.dccpo_conf,
-				 dccpop_node) {
-		dccp_insert_feat_opt(skb, opt->dccpop_type,
-				     opt->dccpop_feat, opt->dccpop_val,
-				     opt->dccpop_len);
-		/* fear empty confirms */
-		if (opt->dccpop_val)
-			kfree(opt->dccpop_val);
-		kfree(opt);

I belive the "confirm queue" now contains confirms for SP and NN options... so
you can probably kill the [] in the comment.
 
 		
-		inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
-					  inet_csk(sk)->icsk_rto, DCCP_RTO_MAX);
-	}

again... change requests are reliable.


==========
OK I think it's a great tidy up and addition of very good code.  I would suggest
the following:

1) Merge it
2) I'll try to re-write the multi-byte feature support patch.  I believe this is
   important functionality which is missing.


So now feature negotiation is moved into the minisock stuff.  I don't know what
it means exactly, but i think the minisock stuff is the socket created upon
receiving a SYN... i.e. a half open connection.  The idea is to keep as little
state as possible in order to avoid SYN floods and other lame dos attacks.

While I was writing feature negotiation, I spotted quite a nice dos attack.
Actually, probably it sucks, but here it is.

The idea is that when you send a REQUEST, you can include your CHANGE options.
The server will RESPOND with the various CONFIRM options.  Here are the nice
implications of this:

* The server must remember which CONFIRMs it sent.  [In fact, the previous code
  was bugged because of this I think---it would remember the features of ALL
  clients in a single socket... anyway.]

  This means that the server must not trash memory, it has to hold some state,
  and potentially even setup those options.  E.g. it might have to load a CCID,
  etc etc.

* The server must actually calculate the CONFIRMS.  With server priority, the
  calculation works as follows:  Given preference list C and S of the client and
  server respectively, the winning value is the first value which appears in S
  and also in C.

  Basically:

  for each s in S
    for each c in C
      if (s = c)
        w00t();

Therefore, would the following DoS DCCP:
* Send a bunch of change options for a SP option in the REQUEST.  Provide an
  ultra long feature list which will not mathc anything on the server, or maybe,
  the last byte will match or something like that.

* The server will have to scan the whole list and compare it against its own
  stuff.

I'm not sure you can write a generic "fast calculation" algorithm as it is not
mandatory to sort the preference lists in any way.  

Re: Report: feat negot state

[Arnaldo Carvalho de Melo]

On 3/8/06, Andrea Bittau <a.bittau@cs.ucl.ac.uk> wrote:
> On Tue, Mar 07, 2006 at 12:05:51AM -0300, Arnaldo Carvalho de Melo wrote:
> > With the current patch, available at:
> >
> > http://oops.ghostprotocols.net:81/acme/dccp_minisock.patch
>
>
> Great work.  I see you've been busy lately =D  Anyway, I'll comment inline, and
> then write a bunch of random thoughts at the end.
>
>
> +       struct list_head             dccpms_pend;
> +       struct list_head             dccpms_conf;
>
> good.  only 2 queues:  one for "pending changes" and one for confirms.  You
> might have wondered why i had a "confirm" inside the pending change queue
> itself, and then a seperate confirm queue.

> Basically, because i coded server priority features first, and then
> non-negotiable.  With NN features, you need to send confirms even for stuff you
> don't know about [or something like that] so i didn't know where to shove the
> confirm =D

:-)

> Anyway, it's much better like this [i was planning to do it at some point, but i
> just "died"]

Ressurrected now? :-)

>
>         /* Check if nothing is being changed. */
> -       if (ccid_nr = new_ccid_nr)
> +       /* XXX handle multibyte values */
> +       if (ccid_nr = *val)
>                 return 0;
>
>
> ccid can only be 1 byte.  kill comment.  assert(len = 1);
>
> -
> -       new_ccid = ccid_new(new_ccid_nr, sk, rx, GFP_ATOMIC);
> +#if 0
> +       new_ccid = ccid_new(*val, sk, rx, GFP_ATOMIC);
>         if (new_ccid = NULL)
>                 return -ENOMEM;
>
>
> that if 0 is only for your debug right?

Well, this part is incomplete, read on, I'll address this on my next comments

>
>         switch (feat) {
>         case DCCPF_CCID:
> -               return dccp_feat_update_ccid(sk, type, val);
> +               return dccp_feat_update_ccid(dmsk, type, val, len);
>
> update_ccid() shouldn't care about len.  it knows the length of ccid.  Well I
> guess it depends on who you leave it to do sanity checks.  But by the time the
> option is "negotiated", errors would have been spotted by upper layers.  [For
> example when doing server priority reconciliation.]

Read on...

> +       feat->dccpf_conf_idx = sidx;
> +       feat->dccpf_conf_len = rlen;
>
> conf_len should be the length of the option itself, not the length of the
> feature list.  I guess this will be sorted when we work on the multi-byte patch.

OK, the reconcile stuff needs to be reconciled with the drafts, its
buggy right now :)

>
>         /* update the option on our side [we are about to send the confirm] */
> -       rc = dccp_feat_update(sk, opt->dccpop_type, opt->dccpop_feat, *res);
> +       rc = dccp_feat_update(dmsk, feat->dccpf_type, feat->dccpf_feat,
> +                             spref + sidx, 1);
>
> similar problem.  Hardcoded feature length of 1.  perhaps it should be
> feat->dccpf_conf_len.

ditto

>
>
> +                       feat->dccpf_conf_idx = 0;
> +                       feat->dccpf_conf_len = 1;
>
> should the index be sidx?  Also, same problem with legnth.

ditto

>
> -       /* generate the confirm [if required] */
> -       dccp_feat_flush_confirm(sk);
> -
> +       /* Confirms will be sent on the next packet */
>
> yea but what if the next packet is never sent?  I.e. uni-directional connection.
> There should be a mechanism to  force an ack after X amount of time if the dude
> doesn't talk.

We need a timer on the minisock perhaps, its still experimental stuff, trying to
figure out how to do feature negotiation at the earliest possible moment at the
server side, i.e. when creating the dccp_request_sock minisock and sending the
RESPONSE packet (first packet sent by the server) without holding too much
state on the request_sock.

> +       list_for_each_entry(feat, &dmsk->dccpms_pend, dccpf_node) {
> +               if (!dccp_feat_negotiated(feat) &&
> +                   feat->dccpf_type = t &&
> +                   feat->dccpf_feat = feature) {
> +                       feat->dccpf_conf_idx = 0;
> +                       feat->dccpf_conf_len = len;
>
> is the index correct?  Also, len should be length of option not of preference
> list.  Confirms will contain confirmed value + pref list.

what I propose to sort out these things is to merge it but not push to Dave, we
work on it, then rework the sequence of csets and push to Dave, agreed?

> +                       /* We got a confirmation: change the option */
> +                       dccp_feat_update(dmsk, feat->dccpf_type,
> +                                        feat->dccpf_feat, val, len);
>
> i'm not sure feat_update should care about length [unless IT sanity checks].  If
> so, len should be of value, not pref list.

ditto

> -       if (all_confirmed) {
> -               dccp_pr_debug("clear feat negotiation timer %p\n", sk);
> -               inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS);
>         }
>
> so what's the story with timers?  Did you kill them?  Will changes be
> re-transmitted?

Well, here we have to think a bit more, REQUEST packets are already
reliably transmitted by dccp_connect using sk_send_head and ICSK_TIME_RETRANS,
and dccpms_pend feature changes are retransmitted till they are negotiated,
but not on DATA/DATAACK packets, i.e. we're almost with the infrastructure that
is needed for reliable changes, but we don't have a timer on the
minisock, it seems,
have to revisit the inet_request_sock stuff to see how to fit this.

>
> +       rc = dccp_feat_change(dmsk, DCCPO_CHANGE_L, DCCPF_ACK_RATIO,
> +                             &dmsk->dccpms_ack_ratio, 1, gfp);
>
> ack ratio is 2 bytes i think.

yeah, this needs more work

>
> +       case DCCPF_CCID:
> +               return len >= sizeof(__u8);
>
> should it also have an && <= number_of_ccids at this point?  Breaks modular
> architecture =D  But you hardcoded MAX_FEATURE_VALUE or whatever it's called
> anyway =D

Well, that also needs more work

>         /* confirm any options [NN opts] */
> -       list_for_each_entry_safe(opt, next, &dp->dccps_options.dccpo_conf,
> -                                dccpop_node) {
> -               dccp_insert_feat_opt(skb, opt->dccpop_type,
> -                                    opt->dccpop_feat, opt->dccpop_val,
> -                                    opt->dccpop_len);
> -               /* fear empty confirms */
> -               if (opt->dccpop_val)
> -                       kfree(opt->dccpop_val);
> -               kfree(opt);
>
> I belive the "confirm queue" now contains confirms for SP and NN options... so
> you can probably kill the [] in the comment.


will do

>
> -               inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
> -                                         inet_csk(sk)->icsk_rto, DCCP_RTO_MAX);
> -       }
>
> again... change requests are reliable.

yup

>
> ==========>
> OK I think it's a great tidy up and addition of very good code.  I would suggest
> the following:
>
> 1) Merge it
> 2) I'll try to re-write the multi-byte feature support patch.  I believe this is
>    important functionality which is missing.
>
>
> So now feature negotiation is moved into the minisock stuff.  I don't know what
> it means exactly, but i think the minisock stuff is the socket created upon
> receiving a SYN... i.e. a half open connection.  The idea is to keep as little
> state as possible in order to avoid SYN floods and other lame dos attacks.

yes, and dccp_minisock_move moves dreq_minisock to dccps_minisock

> While I was writing feature negotiation, I spotted quite a nice dos attack.
> Actually, probably it sucks, but here it is.
>
> The idea is that when you send a REQUEST, you can include your CHANGE options.
> The server will RESPOND with the various CONFIRM options.  Here are the nice
> implications of this:
>
> * The server must remember which CONFIRMs it sent.  [In fact, the previous code
>   was bugged because of this I think---it would remember the features of ALL
>   clients in a single socket... anyway.]

yes, we can't store the client state in the DCCP_ROLE_LISTEN socket, that is the
reason for dccp_minisock

>   This means that the server must not trash memory, it has to hold some state,
>   and potentially even setup those options.  E.g. it might have to load a CCID,
>   etc etc.

yup, I'm stuck now at this, i.e. ccid_hc_rx_init can't touch the full
socket, so we
perhaps need to instantiate the CCID in the three way handshake, where we
have just a dccp_request_sock and later, when we complete the handshake we'd
pass the full sized sock (dccp_sock) to the CCID instantiated
previously, kinda like
making what now is called ccid_hc_rx_init to ccid_hc_rx_new and reintroducing
ccid_hc_rx_init to pass the full sized sock (dccp_sock), ccid_hc_tx
doesn't needs
this as in the client side we create dccp_sock from the beggining, but
to make it
simetric with the rx case we do the same (ccid_hc_tx_new + ccid_hc_tx_init).

> * The server must actually calculate the CONFIRMS.  With server priority, the
>   calculation works as follows:  Given preference list C and S of the client and
>   server respectively, the winning value is the first value which appears in S
>   and also in C.
>
>   Basically:
>
>   for each s in S
>     for each c in C
>       if (s = c)
>         w00t();
>
> Therefore, would the following DoS DCCP:
> * Send a bunch of change options for a SP option in the REQUEST.  Provide an
>   ultra long feature list which will not mathc anything on the server, or maybe,
>   the last byte will match or something like that.
>
> * The server will have to scan the whole list and compare it against its own
>   stuff.
>
> I'm not sure you can write a generic "fast calculation" algorithm as it is not
> mandatory to sort the preference lists in any way.

Yeah, that is the main reason why I think we can't use a doubly linked
list for the
features, on 64bit arches we'd be using 16 bytes only for the list
links! So I guess
we should use an array with a sensible initial size that would expand if needed,
but somehow we must limit the number of acceptable features to grok while doing
the 3way handshake.

- Arnaldo

Re: Report: feat negot state

[Eddie Kohler]

Hi guys!

Andrea Bittau wrote:
> good.  only 2 queues:  one for "pending changes" and one for confirms.  You
> might have wondered why i had a "confirm" inside the pending change queue
> itself, and then a seperate confirm queue.
> 
> Basically, because i coded server priority features first, and then
> non-negotiable.  With NN features, you need to send confirms even for stuff you
> don't know about [or something like that] so i didn't know where to shove the
> confirm =D

I don't quite understand this.  If you don't know about the feature, then how 
can you tell whether it is NN?

> Anyway, it's much better like this [i was planning to do it at some point, but i
> just "died"]
>  
>  
>  	/* Check if nothing is being changed. */
> -	if (ccid_nr = new_ccid_nr)
> +	/* XXX handle multibyte values */
> +	if (ccid_nr = *val)
>  		return 0;
> 
> 
> ccid can only be 1 byte.  kill comment.  assert(len = 1);

It is worth pointing out here that ALL server-priority features specified in 
DCCP so far use one byte values.  So I'd just hold off implementing multi-byte 
SP features.

> +	rc = dccp_feat_change(dmsk, DCCPO_CHANGE_L, DCCPF_ACK_RATIO,
> +			      &dmsk->dccpms_ack_ratio, 1, gfp);
> 
> ack ratio is 2 bytes i think.

Yep.

> 1) Merge it
> 2) I'll try to re-write the multi-byte feature support patch.  I believe this is
>    important functionality which is missing.

For NN features, yes.

> So now feature negotiation is moved into the minisock stuff.  I don't know what
> it means exactly, but i think the minisock stuff is the socket created upon
> receiving a SYN... i.e. a half open connection.  The idea is to keep as little
> state as possible in order to avoid SYN floods and other lame dos attacks.
> 
> While I was writing feature negotiation, I spotted quite a nice dos attack.
> Actually, probably it sucks, but here it is.
> 
> The idea is that when you send a REQUEST, you can include your CHANGE options.
> The server will RESPOND with the various CONFIRM options.  Here are the nice
> implications of this:
> 
> * The server must remember which CONFIRMs it sent.  [In fact, the previous code
>   was bugged because of this I think---it would remember the features of ALL
>   clients in a single socket... anyway.]
> 
>   This means that the server must not trash memory, it has to hold some state,
>   and potentially even setup those options.  E.g. it might have to load a CCID,
>   etc etc.

The Init Cookie option lets the server package up all that state, send it to 
the client, and forget it.  The server might still have to load a CCID, but 
that doesn't worry me -- we only have 3 CCIDs.

> * The server must actually calculate the CONFIRMS.  With server priority, the
>   calculation works as follows:  Given preference list C and S of the client and
>   server respectively, the winning value is the first value which appears in S
>   and also in C.
> 
>   Basically:
> 
>   for each s in S
>     for each c in C
>       if (s = c)
>         w00t();

It's not that bad.  (1) All feature negotiation options are limited to 252 
bytes of feature value at most.  (2) All current SP features are one-byte 
valued.  So you can do this.

     uint32_t bitmap[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; // 256 bits
     for each c in C
       turn on corresponding bit in bitmap;
     for each s in S
       if corresponding bit in bitmap is true
         w00t();

O(n^2) -> O(n).

For multi-byte SP features (if they ever exist), this trick doesn't work, but 
the DOS is less serious, since the maximum preference list length is 1/2 (1/3, 
1/4...) as long.

E

Re: Report: feat negot state

[Arnaldo Carvalho de Melo]

On 3/8/06, Eddie Kohler <kohler@cs.ucla.edu> wrote:
> Hi guys!

Hi Eddie!

> > * The server must remember which CONFIRMs it sent.  [In fact, the previous code
> >   was bugged because of this I think---it would remember the features of ALL
> >   clients in a single socket... anyway.]
> >
> >   This means that the server must not trash memory, it has to hold some state,
> >   and potentially even setup those options.  E.g. it might have to load a CCID,
> >   etc etc.
>
> The Init Cookie option lets the server package up all that state, send it to
> the client, and forget it.  The server might still have to load a CCID, but
> that doesn't worry me -- we only have 3 CCIDs.

Sure, Init Cookie will be eventually implemented, but I want to
support everything
that is specified in the draft, and furthermore, reworking the core Linux INET
infrastructure to have TCP and DCCP sharing _everything_ that is not specific to
one of them, that has been my goal since day one, if I decided just to implement
Init Cookies I would have a much easier ride, but I'm stubborn on supporting all
the things specified in the draft to the best of my capacity use this
implementation
to fully validate the draft in the Real World(tm), even if takes more time 8)

If one looks at work Eric Dumazet, Ben LaHaise and others are doing on improving
TCP that _already_ are helping DCCP due to all this code sharing, its
wonderful, I
really, really didn't wanted to go the SCTP way where few things is shared with
other INET connection oriented protocols (well, at the time there was
only TCP :P).

> > * The server must actually calculate the CONFIRMS.  With server priority, the
> >   calculation works as follows:  Given preference list C and S of the client and
> >   server respectively, the winning value is the first value which appears in S
> >   and also in C.
> >
> >   Basically:
> >
> >   for each s in S
> >     for each c in C
> >       if (s = c)
> >         w00t();
>
> It's not that bad.  (1) All feature negotiation options are limited to 252
> bytes of feature value at most.  (2) All current SP features are one-byte
> valued.  So you can do this.
>
>      uint32_t bitmap[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; // 256 bits
>      for each c in C
>        turn on corresponding bit in bitmap;
>      for each s in S
>        if corresponding bit in bitmap is true
>          w00t();
>
> O(n^2) -> O(n).
>
> For multi-byte SP features (if they ever exist), this trick doesn't work, but
> the DOS is less serious, since the maximum preference list length is 1/2 (1/3,
> 1/4...) as long.

Interesting idea, will get back to this after getting what we have now
working as
a first step.

- Arnaldo

Re: Report: feat negot state

[Eddie Kohler]

Hi Arnaldo,

Arnaldo Carvalho de Melo wrote:
>>The Init Cookie option lets the server package up all that state, send it to
>>the client, and forget it.  The server might still have to load a CCID, but
>>that doesn't worry me -- we only have 3 CCIDs.
> 
> 
> Sure, Init Cookie will be eventually implemented, but I want to
> support everything
> that is specified in the draft, and furthermore, reworking the core Linux INET
> infrastructure to have TCP and DCCP sharing _everything_ that is not specific to
> one of them, that has been my goal since day one, if I decided just to implement
> Init Cookies I would have a much easier ride, but I'm stubborn on supporting all
> the things specified in the draft to the best of my capacity use this
> implementation
> to fully validate the draft in the Real World(tm), even if takes more time 8)
> 
> If one looks at work Eric Dumazet, Ben LaHaise and others are doing on improving
> TCP that _already_ are helping DCCP due to all this code sharing, its
> wonderful, I
> really, really didn't wanted to go the SCTP way where few things is shared with
> other INET connection oriented protocols (well, at the time there was
> only TCP :P).

This is a great approach!  But TCP implements syn cookies, which is very 
similar to the Init Cookie.  So Init Cookies are not totally DCCP-only.  I'm 
just saying the DOS need not be such a big deal.

Eddie

Re: Report: feat negot state

[Arnaldo Carvalho de Melo]

On 3/8/06, Eddie Kohler <kohler@cs.ucla.edu> wrote:
> Hi Arnaldo,
>
> Arnaldo Carvalho de Melo wrote:
> >>The Init Cookie option lets the server package up all that state, send it to
> >>the client, and forget it.  The server might still have to load a CCID, but
> >>that doesn't worry me -- we only have 3 CCIDs.
> >
> >
> > Sure, Init Cookie will be eventually implemented, but I want to
> > support everything
> > that is specified in the draft, and furthermore, reworking the core Linux INET
> > infrastructure to have TCP and DCCP sharing _everything_ that is not specific to
> > one of them, that has been my goal since day one, if I decided just to implement
> > Init Cookies I would have a much easier ride, but I'm stubborn on supporting all
> > the things specified in the draft to the best of my capacity use this
> > implementation
> > to fully validate the draft in the Real World(tm), even if takes more time 8)
> >
> > If one looks at work Eric Dumazet, Ben LaHaise and others are doing on improving
> > TCP that _already_ are helping DCCP due to all this code sharing, its
> > wonderful, I
> > really, really didn't wanted to go the SCTP way where few things is shared with
> > other INET connection oriented protocols (well, at the time there was
> > only TCP :P).
>
> This is a great approach!  But TCP implements syn cookies, which is very
> similar to the Init Cookie.  So Init Cookies are not totally DCCP-only.  I'm
> just saying the DOS need not be such a big deal.

Sure, my idea is to abstract TCP syncookies/DCCP Init Cookies at the
struct inet_request_sock level, then both will have the same code flow :-)

So stay tuned as after we get the feature negotiation mostly working I'll attack
this new syncookies/init cookie abstraction.

Ah, another thing in the backburner is to support DCCPv6 only, i.e. right now we
have dccp_ipv4 and dccp_ipv6 modules, but dccp_ipv6 still requires dccp_ipv4
due to v6 mapped v4 addresses, that is not selectable, but I'll rework this code
at the inet_connection_sock level to make it possible to have a IPv6 only setup,
paving the way for IPv4 retirement as I promised to DaveM 8-) :-P

- Arnaldo

Re: Report: feat negot state

[Andrea Bittau]

On Wed, Mar 08, 2006 at 08:08:53AM -0800, Eddie Kohler wrote:
> >Basically, because i coded server priority features first, and then
> >non-negotiable.  With NN features, you need to send confirms even for 
> >stuff you
> >don't know about [or something like that] so i didn't know where to shove 
> >the
> >confirm =D
> 
> I don't quite understand this.  If you don't know about the feature, then 
> how can you tell whether it is NN?

OK the issue was this.  With SP, you have a preference list, so whenever you
confirm X, you can shove the confirm in the preference list data structure for
X.

For NN, it might be possible to not have a preference for X. [?]  e.g. say you
get CHANGE_L ACK_RATIO, maybe you don't even care about ACK_RATIO yourself, so
you might not have a feature structure list for your own ack ratio, where you
could put the confirm.

This is what happens when coding without thinking / designing.  But hey, time =D

> >2) I'll try to re-write the multi-byte feature support patch.  I believe 
> >this is
> >   important functionality which is missing.
> 
> For NN features, yes.

yea, in fact i initially wrote the patch solely for ack ratios.  I wanted to see
how CCID2 would behave when ack ratios really did change =D

> The Init Cookie option lets the server package up all that state, send it 
> to the client, and forget it.  The server might still have to load a CCID, 
> but that doesn't worry me -- we only have 3 CCIDs.

I remember seeing the init cookie in the spec.  I just re-read it, yes it solves
the problem.  I didn't know it was so versatile [that you can encode ~200 bytes
of data.]  I thought it was just a 32bit number or something.

> It's not that bad.  (1) All feature negotiation options are limited to 252 
> bytes of feature value at most.  (2) All current SP features are one-byte 
> valued.  So you can do this.

yea, but I was thinking if you chain many change X in the same packet.  I'm not
sure that's legal.  But anyway, an implementation may process options from the
tail of the packet to front, and discard any previously seen feature negos for
the same option.

yea, in fact i got "scared" when I wrote the multi-byte patch.  the:
if (c = s)
became a:
if (memcmp(c, s, len) = 0)


anyway, yes, i agree with you that there is no real dos issue.  What got me
thinking about this was mereley "when will my code suck?" [apart from "in the
common case"] =D


As Arnaldo said, the goal is to get this working properly as quickly as
possible.  I don't think we are far.  From what I can see, only two big things
are missing [in feat nego]:
* Timers & Feature negotation.

Both have been written in some patch, it's just a matter of putting the puzzle
together and framing it =D

Re: Report: feat negot state

[Eddie Kohler]

Hey Andrea!

Just a couple things:

On Mar 8, 2006, at 11:01 AM, Andrea Bittau wrote:
>
>> It's not that bad.  (1) All feature negotiation options are  
>> limited to 252
>> bytes of feature value at most.  (2) All current SP features are  
>> one-byte
>> valued.  So you can do this.
>
> yea, but I was thinking if you chain many change X in the same  
> packet.  I'm not
> sure that's legal.  But anyway, an implementation may process  
> options from the
> tail of the packet to front, and discard any previously seen  
> feature negos for
> the same option.

(1) Implementations MUST process options from front to back.   
"Options MUST be processed sequentially, starting at the first option  
in the packet header."

(2) "A packet MAY contain more than one feature negotiation option,  
possibly including two options that refer to the same feature; as  
usual, the options are processed sequentially."

> yea, in fact i got "scared" when I wrote the multi-byte patch.  the:
> if (c = s)
> became a:
> if (memcmp(c, s, len) = 0)

Yep :)

Eddie