Merge lp:~martin-lp/hipl/update_ack_handling into lp:hipl
- update_ack_handling
- Merge into trunk
Status: | Superseded |
---|---|
Proposed branch: | lp:~martin-lp/hipl/update_ack_handling |
Merge into: | lp:hipl |
Diff against target: |
112 lines (+58/-10) 2 files modified
modules/update/hipd/update.c (+50/-8) modules/update/hipd/update.h (+8/-2) |
To merge this branch: | bzr merge lp:~martin-lp/hipl/update_ack_handling |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Christof Mroz | Approve | ||
René Hummen | Approve | ||
Diego Biurrun | Approve | ||
Review via email: mp+71213@code.launchpad.net |
This proposal supersedes a proposal from 2011-08-11.
This proposal has been superseded by a proposal from 2011-08-12.
Commit message
Description of the change
This is a resubmitted proposal:
addressed issues are fixed in revisions 6048-6052 in this branch.
Old proposal description:
This is a relatively small change but it addresses dealing with update
acknowledgments and it would be fatal to introduce bugs here.
The situation: previously only acknowledgments for the most recent sent
Update packet were accepted. This is a problem when both hosts initiate
an update at the same time.
The typical update sequence between host1 <-> host2 looks like this:
U1 (SEQ x) ->
U2 (SEQ y, ACK x) <-
U3 (ACK y) ->
If both hosts initiate simultaneously things go wrong:
U1 (SEQ x) ->
U1 (SEQ y) <-
U2 (SEQ x+1, ACK y) ->
U2 (SEQ y+1, ACK x) <-
if hosts only store the most recent sent update packet SEQ it breaks now
as host1 gets an ACK for x but expects x+1 (as this is the most recent).
As a consequence the packets get dropped and the update fails.
This branch introduces a lower boundary for outgoing Update packet IDs.
Valid received ACKs are the outstanding ones in
[lower_boundary, most recent sent].
Please check if I missed anything or if there is a flaw in the logic.
Actual tests or reproduction of the problem can be done with
tcpdump + wireshark or just by debug output.
- initiate BEX between two hosts (eg. by ping)
- run tools/hipconf manual-update at the same time on both hosts
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
René Hummen (rene-hummen) : Posted in a previous version of this proposal | # |
Diego Biurrun (diego-biurrun) wrote : Posted in a previous version of this proposal | # |
On Wed, Aug 10, 2011 at 11:52:31AM +0000, René Hummen wrote:
> review needs-fixing
If your intention is to set this by email, then you need to
a) Indent that statement with a space.
b) GPG-sign the email.
Diego
David Martin (martin-lp) wrote : Posted in a previous version of this proposal | # |
Hi,
thanks for you input René!
On Wed, Aug 10, 2011 at 1:52 PM, René Hummen <email address hidden> wrote:
> On 10.08.2011, at 13:16, David Martin wrote:
>> David Martin has proposed merging lp:~martin-lp/hipl/update_ack_handling into lp:hipl.
>> === modified file 'modules/
>> --- modules/
>> +++ modules/
>
>> @@ -157,6 +158,41 @@
>> }
>>
>> /**
>> + * Verify the validity of the ACK ID of a received Update packet and update the
>> + * range in which Update packets will be accepted accordingly.
>> + *
>> + * @param state The update state of the respective HA.
>> + * @param ack_peer_update_id The received ACK ID.
>> + *
>> + * @return true if received ACK is valid
>> + * false else
>> + */
>> +static bool check_and_
>> + uint32_t ack_peer_update_id)
>
> const uint32_t ack_peer_update_id would be more const correct.
Fixed.
>> +{
>> + HIP_ASSERT(state);
>> +
>> + /* two cases:
>> + * oldest not yet acknowledged SEQ <= latest sent Update SEQ
>> + * => received ACK must be in those bounds to be valid
>> + * oldest not yet acknowledged SEQ > latest sent Update SEQ (counter overflow)
>> + * => received ACK must be greater than oldest SEQ or smaller than latest
>> + * sent Update ID to be valid
>> + */
>
> This comment is hard to understand without knowledge about your internal seq/ack data structure. Please describe how the two fields update_
See my comment below on this.
>> + if ((state-
>> + ack_peer_update_id >= state->
>> + ack_peer_update_id <= hip_update_
>> + (state-
>> + (ack_peer_update_id >= state->
>> + ack_peer_update_id <= hip_update_
>> + state->
>> + return true;
>> + } else {
>> + return false;
>> + }
>
> Please break this down into a if () ... else if () ... else for higher readability.
Is it even necessary to differentiate between the two cases? Come to think of it an overflow seems very unlikely. I would not count too much on my math skills but by my calculation it would take more than 130 years with an update every second to reach the end of that range as it is unsigned 32bit. My suggestion would be to leave it out. The part of the code dealing with the incoming UPDATE IDs does not seem to care about this either.
>> * Check if UPDATE sequence and acknowledgment numbers are as expected.
>> *
>> * @param packet_type the packet type
>> @@ -216,12 +252,12 @@
>> HIP_DEBUG("ACK parameter found with peer Update ID %u.\n",
>> ack_peer_
>>
>> - // we only want acks for our most current update
>> - ...
Diego Biurrun (diego-biurrun) wrote : Posted in a previous version of this proposal | # |
On Wed, Aug 10, 2011 at 01:58:54PM +0000, David Martin wrote:
>
> On Wed, Aug 10, 2011 at 1:52 PM, René Hummen <email address hidden> wrote:
> > On 10.08.2011, at 13:16, David Martin wrote:
> >> David Martin has proposed merging lp:~martin-lp/hipl/update_ack_handling into lp:hipl.
> >> --- modules/
> >> +++ modules/
> >> @@ -157,6 +158,41 @@
> >> + if ((state-
> >> + ack_peer_update_id >= state->
> >> + ack_peer_update_id <= hip_update_
> >> + (state-
> >> + (ack_peer_update_id >= state->
> >> + ack_peer_update_id <= hip_update_
> >> + state->
> >> + return true;
> >> + } else {
> >> + return false;
> >> + }
> >
> > Please break this down into a if () ... else if () ... else for higher readability.
>
> Is it even necessary to differentiate between the two cases? Come to
> think of it an overflow seems very unlikely. I would not count too
> much on my math skills but by my calculation it would take more than
> 130 years with an update every second to reach the end of that range
> as it is unsigned 32bit.
general comment that may or may not be relevant here: Do not calculate
based on some likely scenario. Calculate what may happen if one were
to (maliciously) hammer the daemon with update packets.
Diego
Christof Mroz (christof-mroz) wrote : Posted in a previous version of this proposal | # |
You introduce the lower bound in this branch, but other than initializing it to zero it's not updated. Don't you need to adjust it upon succesfully processing the update tagged with the smallest ID?
David Martin (martin-lp) wrote : Posted in a previous version of this proposal | # |
> On Wed, Aug 10, 2011 at 01:58:54PM +0000, David Martin wrote:
> >
> > On Wed, Aug 10, 2011 at 1:52 PM, René Hummen <email address hidden>
> wrote:
> > > On 10.08.2011, at 13:16, David Martin wrote:
> > >> David Martin has proposed merging lp:~martin-lp/hipl/update_ack_handling
> into lp:hipl.
> > >> --- modules/
> > >> +++ modules/
> > >> @@ -157,6 +158,41 @@
> > >> + if ((state-
> hip_update_
> > >> + ack_peer_update_id >= state->
> > >> + ack_peer_update_id <= hip_update_
> > >> + (state-
> &&
> > >> + (ack_peer_update_id >= state->
> > >> + ack_peer_update_id <= hip_update_
> > >> + state->
> > >> + return true;
> > >> + } else {
> > >> + return false;
> > >> + }
> > >
> > > Please break this down into a if () ... else if () ... else for higher
> readability.
> >
> > Is it even necessary to differentiate between the two cases? Come to
> > think of it an overflow seems very unlikely. I would not count too
> > much on my math skills but by my calculation it would take more than
> > 130 years with an update every second to reach the end of that range
> > as it is unsigned 32bit.
>
> general comment that may or may not be relevant here: Do not calculate
> based on some likely scenario. Calculate what may happen if one were
> to (maliciously) hammer the daemon with update packets.
Good point. I've kept it in an separated the cases for readability.
David Martin (martin-lp) wrote : Posted in a previous version of this proposal | # |
On Wed, Aug 10, 2011 at 7:40 PM, Christof Mroz <email address hidden> wrote:
> You introduce the lower bound in this branch, but other than initializing it to zero it's not updated. Don't you need to adjust it upon succesfully processing the update tagged with the smallest ID?
It gets updated in check_and_
- it gets updated before the HMAC check is performed, a retransmission would still be accepted though so this should not make trouble.
- out-of-order ACKs get dropped. Say you send two update packets with SEQ x and x+1 and you receive the ACK for x+1 first, it would update the lower bound and ACK for x would be dropped. This is non-trivial to fix though. Seems to be ok with the RFC in any case: "The semantics are such that the receiver MUST acknowledge the UPDATE, but the sender MAY choose to not care about receiving the ACK."
Diego Biurrun (diego-biurrun) wrote : Posted in a previous version of this proposal | # |
review needs-fixing
On Thu, Aug 11, 2011 at 01:46:52PM +0000, David Martin wrote:
>
> --- modules/
> +++ modules/
> @@ -157,6 +158,46 @@
>
> + if (state-
> + ack_peer_update_id >= state->
> + ack_peer_update_id <= hip_update_
> + state->
> + return true;
> + } else if (state-
> + (ack_peer_update_id >= state->
> + ack_peer_update_id <= hip_update_
> + state->
> + return true;
> + } else {
> + return false;
> + }
Geez, this is complicated. Luckily some of it is redundant, witness:
if (state-
if (ack_peer_update_id >= state->
return true;
} else {
if (ack_peer_update_id >= state->
return true;
}
return false;
Diego
David Martin (martin-lp) wrote : Posted in a previous version of this proposal | # |
On Thu, Aug 11, 2011 at 4:22 PM, Diego Biurrun <email address hidden> wrote:
> review needs-fixing
>
> On Thu, Aug 11, 2011 at 01:46:52PM +0000, David Martin wrote:
>>
>> --- modules/
>> +++ modules/
>> @@ -157,6 +158,46 @@
> Geez, this is complicated.
I know I know, but there does not seem to be much you can do about it.
> Luckily some of it is redundant, witness:
>
> if (state-
> if (ack_peer_update_id >= state->
> ack_peer_update_id <= hip_update_
> state->
> return true;
> } else {
> if (ack_peer_update_id >= state->
> ack_peer_update_id <= hip_update_
> state->
> return true;
> }
> return false;
Hah, you are awesome! Fixed it.
Diego Biurrun (diego-biurrun) wrote : | # |
review approve
On Thu, Aug 11, 2011 at 02:43:17PM +0000, David Martin wrote:
>
> --- modules/
> +++ modules/
> @@ -157,6 +158,47 @@
>
> + if (state-
> + if (ack_peer_update_id >= state->
> + ack_peer_update_id <= hip_update_
> + state->
> + return true;
> + }
> + } else {
> + if (ack_peer_update_id >= state->
> + ack_peer_update_id <= hip_update_
> + state->
> + return true;
> + }
> + }
Somebody please surprise us with a way to avoid this code duplication.
My only idea is goto.
Anyway, LGTM now.
Diego
René Hummen (rene-hummen) : | # |
Christof Mroz (christof-mroz) wrote : | # |
On Thu, 11 Aug 2011 17:01:35 +0200, Diego Biurrun <email address hidden> wrote:
>> + if (state-
>> hip_update_
>> + if (ack_peer_update_id >= state->
>> + ack_peer_update_id <= hip_update_
>> + state->
>> + return true;
>> + }
>> + } else {
>> + if (ack_peer_update_id >= state->
>> + ack_peer_update_id <= hip_update_
>> + state->
>> + return true;
>> + }
>> + }
>
> Somebody please surprise us with a way to avoid this code duplication.
> My only idea is goto.
Reversing the logic and returning false early (but it may be harder to
comprehend this way).
Christof Mroz (christof-mroz) wrote : Posted in a previous version of this proposal | # |
On Thu, 11 Aug 2011 15:43:33 +0200, David Martin
<email address hidden> wrote:
> On Wed, Aug 10, 2011 at 7:40 PM, Christof Mroz
> <email address hidden> wrote:
>> You introduce the lower bound in this branch, but other than
>> initializing it to zero it's not updated. Don't you need to adjust it
>> upon succesfully processing the update tagged with the smallest ID?
>
> It gets updated in check_and_
> valid ACK.
You are right of course. It's hard to spot where the if(...) condition
ends and the body starts IMHO. You may consider adding an empty line after
the opening brace for readability.
> The problems that may be as it is:
> - it gets updated before the HMAC check is performed, a retransmission
> would still be accepted though so this should not make trouble.
> - out-of-order ACKs get dropped. Say you send two update packets with
> SEQ x and x+1 and you receive the ACK for x+1 first, it would update the
> lower bound and ACK for x would be dropped. This is non-trivial to fix
> though. Seems to be ok with the RFC in any case: "The semantics are such
> that the receiver MUST acknowledge the UPDATE, but the sender MAY choose
> to not care about receiving the ACK."
Yes, don't bother as long as the branch solves the original problem (which
it does as far as I can tell).
Diego Biurrun (diego-biurrun) wrote : | # |
On Thu, Aug 11, 2011 at 03:18:39PM +0000, Christof Mroz wrote:
> On Thu, 11 Aug 2011 17:01:35 +0200, Diego Biurrun <email address hidden> wrote:
>
> >> + if (state-
> >> hip_update_
> >> + if (ack_peer_update_id >= state->
> >> + ack_peer_update_id <= hip_update_
> >> + state->
> >> + return true;
> >> + }
> >> + } else {
> >> + if (ack_peer_update_id >= state->
> >> + ack_peer_update_id <= hip_update_
> >> + state->
> >> + return true;
> >> + }
> >> + }
> >
> > Somebody please surprise us with a way to avoid this code duplication.
> > My only idea is goto.
>
> Reversing the logic and returning false early (but it may be harder to
> comprehend this way).
Good idea, I fully support that :)
Diego
- 6053. By David Martin
-
Invert logic of ACK checks for improved readability, avoided code duplication.
David Martin (martin-lp) wrote : | # |
On Thu, Aug 11, 2011 at 5:18 PM, Christof Mroz <email address hidden> wrote:
> On Thu, 11 Aug 2011 17:01:35 +0200, Diego Biurrun <email address hidden> wrote:
>
>>> + if (state-
>>> hip_update_
>>> + if (ack_peer_update_id >= state->
>>> + ack_peer_update_id <= hip_update_
>>> + state->
>>> + return true;
>>> + }
>>> + } else {
>>> + if (ack_peer_update_id >= state->
>>> + ack_peer_update_id <= hip_update_
>>> + state->
>>> + return true;
>>> + }
>>> + }
>>
>> Somebody please surprise us with a way to avoid this code duplication.
>> My only idea is goto.
>
> Reversing the logic and returning false early (but it may be harder to
> comprehend this way).
Nice one! Actually I think it makes it easier to comprehend as > and < are at least for me easier to imagine than >= and <=. The update of the lower bound is more visible as well.
I'll have to ask another review of the change of you though. It still seems to do the same but better safe than sorry and it's always these small things that cause the hardest to find bugs.
Unmerged revisions
Preview Diff
1 | === modified file 'modules/update/hipd/update.c' |
2 | --- modules/update/hipd/update.c 2011-08-11 13:51:14 +0000 |
3 | +++ modules/update/hipd/update.c 2011-08-12 09:58:25 +0000 |
4 | @@ -36,6 +36,7 @@ |
5 | #define _BSD_SOURCE |
6 | |
7 | #include <errno.h> |
8 | +#include <stdbool.h> |
9 | #include <stdint.h> |
10 | #include <string.h> |
11 | |
12 | @@ -157,6 +158,46 @@ |
13 | } |
14 | |
15 | /** |
16 | + * Verify the validity of the ACK ID of a received Update packet and update the |
17 | + * range in which Update packets will be accepted accordingly. |
18 | + * |
19 | + * @param state The update state of the respective HA. |
20 | + * @param ack_peer_update_id The received ACK ID. |
21 | + * |
22 | + * @return true if received ACK is valid |
23 | + * false else |
24 | + */ |
25 | +static bool check_and_update_ack_id_bounds(struct update_state *const state, |
26 | + const uint32_t ack_peer_update_id) |
27 | +{ |
28 | + HIP_ASSERT(state); |
29 | + |
30 | + /* Of the three UPDATE packets the first and second must be acknowledged. |
31 | + * hip_update_get_out_id() gets the latest outgoing UPDATE ID whereas |
32 | + * update_id_out_lower_bound stores the oldest sent UPDATE ID with an |
33 | + * outstanding acknowledgement. Together they form the window in which |
34 | + * incoming ACKs are valid. Multiple ACKs may be outstanding for example |
35 | + * when both host and peer initiate an update. In this case both |
36 | + * U1 (update initiated by the host) and U2 (response to update initiated |
37 | + * by the peer) are to be acknowledged and their IDs stored in |
38 | + * update_id_out_lower_bound and hip_update_get_out_id() respectively. |
39 | + */ |
40 | + if (state->update_id_out_lower_bound <= hip_update_get_out_id(state)) { |
41 | + if (ack_peer_update_id < state->update_id_out_lower_bound || |
42 | + ack_peer_update_id > hip_update_get_out_id(state)) { |
43 | + return false; |
44 | + } |
45 | + } else { |
46 | + if (ack_peer_update_id < state->update_id_out_lower_bound && |
47 | + ack_peer_update_id > hip_update_get_out_id(state)) { |
48 | + return false; |
49 | + } |
50 | + } |
51 | + state->update_id_out_lower_bound = ack_peer_update_id; |
52 | + return true; |
53 | +} |
54 | + |
55 | +/** |
56 | * Check if UPDATE sequence and acknowledgment numbers are as expected. |
57 | * |
58 | * @param packet_type the packet type |
59 | @@ -216,12 +257,12 @@ |
60 | HIP_DEBUG("ACK parameter found with peer Update ID %u.\n", |
61 | ack_peer_update_id); |
62 | |
63 | - // we only want acks for our most current update |
64 | - if (ack_peer_update_id != hip_update_get_out_id(localstate)) { |
65 | - HIP_DEBUG("Update ID (%u) in the ACK parameter is not " |
66 | - "equal to the last outgoing Update ID (%u). " |
67 | + if (!check_and_update_ack_id_bounds(localstate, ack_peer_update_id)) { |
68 | + HIP_DEBUG("Update ID (%u) in the ACK parameter is not in the " |
69 | + "current Update ID window (%u-%u). " |
70 | "Dropping the packet.\n", |
71 | ack_peer_update_id, |
72 | + localstate->update_id_out_lower_bound, |
73 | hip_update_get_out_id(localstate)); |
74 | err = -1; |
75 | goto out_err; |
76 | @@ -488,10 +529,11 @@ |
77 | return -1; |
78 | } |
79 | |
80 | - update_state->update_state = 0; |
81 | - update_state->valid_locators = 0; |
82 | - update_state->update_id_out = 0; |
83 | - update_state->update_id_in = 0; |
84 | + update_state->update_state = 0; |
85 | + update_state->valid_locators = 0; |
86 | + update_state->update_id_out = 0; |
87 | + update_state->update_id_out_lower_bound = 0; |
88 | + update_state->update_id_in = 0; |
89 | |
90 | res = lmod_add_state_item(state, update_state, "update"); |
91 | if (res == -1) { |
92 | |
93 | === modified file 'modules/update/hipd/update.h' |
94 | --- modules/update/hipd/update.h 2011-07-28 18:11:17 +0000 |
95 | +++ modules/update/hipd/update.h 2011-08-12 09:58:25 +0000 |
96 | @@ -81,9 +81,15 @@ |
97 | */ |
98 | unsigned valid_locators; |
99 | |
100 | - /** Stored outgoing UPDATE ID counter. */ |
101 | + /** UPDATE ID of the latest outgoing UPDATE packet. */ |
102 | uint32_t update_id_out; |
103 | - /** Stored incoming UPDATE ID counter. */ |
104 | + |
105 | + /** UPDATE ID of the oldest not yet acknowledged outgoing UPDATE packet. |
106 | + * Usually this value is equal to @c update_id_out. The only exception is |
107 | + * when more than one UPDATE packet is yet to be acknowledged by the peer. */ |
108 | + uint32_t update_id_out_lower_bound; |
109 | + |
110 | + /** UPDATE ID of the latest incoming UPDATE packet. */ |
111 | uint32_t update_id_in; |
112 | }; |
113 |
review needs-fixing
I just have a few comments inline.
On 10.08.2011, at 13:16, David Martin wrote: /code.launchpad .net/~martin- lp/hipl/ update_ ack_handling/ +merge/ 71027
> David Martin has proposed merging lp:~martin-lp/hipl/update_ack_handling into lp:hipl.
>
> Requested reviews:
> HIPL core team (hipl-core)
>
> For more details, see:
> https:/
> === modified file 'modules/ update/ hipd/update. c' update/ hipd/update. c 2011-07-18 16:41:13 +0000 update/ hipd/update. c 2011-08-10 11:16:05 +0000
> --- modules/
> +++ modules/
> @@ -157,6 +158,41 @@ update_ ack_id_ bounds( struct update_state *const state,
> }
>
> /**
> + * Verify the validity of the ACK ID of a received Update packet and update the
> + * range in which Update packets will be accepted accordingly.
> + *
> + * @param state The update state of the respective HA.
> + * @param ack_peer_update_id The received ACK ID.
> + *
> + * @return true if received ACK is valid
> + * false else
> + */
> +static bool check_and_
> + uint32_t ack_peer_update_id)
const uint32_t ack_peer_update_id would be more const correct.
> +{
> + HIP_ASSERT(state);
> +
> + /* two cases:
> + * oldest not yet acknowledged SEQ <= latest sent Update SEQ
> + * => received ACK must be in those bounds to be valid
> + * oldest not yet acknowledged SEQ > latest sent Update SEQ (counter overflow)
> + * => received ACK must be greater than oldest SEQ or smaller than latest
> + * sent Update ID to be valid
> + */
This comment is hard to understand without knowledge about your internal seq/ack data structure. Please describe how the two fields update_ id_out_ lower_bound and update_id_out are used in a normal update situation.
> + if ((state- >update_ id_out_ lower_bound <= hip_update_ get_out_ id(state) && update_ id_out_ lower_bound && get_out_ id(state) ) || >update_ id_out_ lower_bound > hip_update_ get_out_ id(state) && update_ id_out_ lower_bound || get_out_ id(state) ))) { update_ id_out_ lower_bound = ack_peer_update_id;
> + ack_peer_update_id >= state->
> + ack_peer_update_id <= hip_update_
> + (state-
> + (ack_peer_update_id >= state->
> + ack_peer_update_id <= hip_update_
> + state->
> + return true;
> + } else {
> + return false;
> + }
Please break this down into a if () ... else if () ... else for higher readability.
> * Check if UPDATE sequence and acknowledgment numbers are as expected. update_ id); get_out_ id(localstate) ) { and_update_ ack_id_ bounds( localstate, ack_peer_ update_ id)) {
> *
> * @param packet_type the packet type
> @@ -216,12 +252,12 @@
> HIP_DEBUG("ACK parameter found with peer Update ID %u.\n",
> ack_peer_
>
> - // we only want acks for our most current update
> - if (ack_peer_update_id != hip_update_
> - HIP_DEBUG("Update ID (%u) in the ACK parameter is not "
> - "equal to the last outgoing Update ID (%u). "
> + if (!check_
> + HIP_DEBUG("Update ID (%u) in the ACK parameter is not one of the "
> + "yet to be acknowledged Update IDs (%u-%u). ...