Re: [PATCH ipsec-next v12 15/16] xfrm: iptfs: handle reordering of received packets

[Christian Hopps <chopps@chopps.org>]

[-- Attachment #1: Type: text/plain, Size: 7722 bytes --]


Steffen Klassert <steffen.klassert@secunet.com> writes:

> On Mon, Oct 07, 2024 at 09:59:27AM -0400, Christian Hopps wrote:
>> From: Christian Hopps <chopps@labn.net>
>>
>> +static u32 __reorder_drop(struct xfrm_iptfs_data *xtfs, struct list_head *list)
>> +
>> +{
>> +	struct skb_wseq *s, *se;
>> +	const u32 savedlen = xtfs->w_savedlen;
>> +	time64_t now = ktime_get_raw_fast_ns();
>> +	u32 count = 0;
>> +	u32 scount = 0;
>> +
>> +	WARN_ON_ONCE(!savedlen);
>> +	if (xtfs->w_saved[0].drop_time > now)
>> +		goto set_timer;
>> +
>> +	++xtfs->w_wantseq;
>> +
>> +	/* Keep flushing packets until we reach a drop time greater than now. */
>> +	s = xtfs->w_saved;
>> +	se = s + savedlen;
>> +	do {
>> +		/* Walking past empty slots until we reach a packet */
>> +		for (; s < se && !s->skb; s++)
>> +			if (s->drop_time > now)
>> +				goto outerdone;
>
> Please use braces if there is more that one line in the loop.

Done.

>> +
>> +static void __reorder_future_shifts(struct xfrm_iptfs_data *xtfs,
>> +				    struct sk_buff *inskb,
>> +				    struct list_head *list,
>> +				    struct list_head *freelist)
>
> freelist is unused in this function.

Removed.

>> +{
>> +	const u32 nslots = xtfs->cfg.reorder_win_size + 1;
>> +	const u64 inseq = __esp_seq(inskb);
>> +	u32 savedlen = xtfs->w_savedlen;
>> +	u64 wantseq = xtfs->w_wantseq;
>> +	struct sk_buff *slot0 = NULL;
>> +	struct skb_wseq *wnext;
>> +	u32 beyond, shifting, slot;
>> +	u64 distance;
>> +
>> +	WARN_ON_ONCE(inseq <= wantseq);
>
> Do we really need this warning? You checked exactly this before calling
> __reorder_future_shifts.
>
>> +	distance = inseq - wantseq;
>> +	WARN_ON_ONCE(distance <= nslots - 1);
>
> Same here. There are a lot of these WARN_ON_ONCE all over the
> place. I don't think we need it at places where it is clear
> that the warn condition will never be true.

Removed.

>> +	beyond = distance - (nslots - 1);
>> +
>> +	/* Handle future sequence number received.
>> +	 *
>> +	 * IMPORTANT: we are at least advancing w_wantseq (i.e., wantseq) by 1
>> +	 * b/c we are beyond the window boundary.
>> +	 *
>> +	 * We know we don't have the wantseq so that counts as a drop.
>> +	 */
>> +
>> +	/* ex: slot count is 4, array size is 3 savedlen is 2, slot 0 is the
>
> What means 'ex:'?

"Example" - expanded.

>> +	 * missing sequence number.
>> +	 *
>> +	 * the final slot at savedlen (index savedlen - 1) is always occupied.
>> +	 *
>> +	 * beyond is "beyond array size" not savedlen.
>> +	 *
>> +	 *          +--------- array length (savedlen == 2)
>> +	 *          |   +----- array size (nslots - 1 == 3)
>> +	 *          |   |   +- window boundary (nslots == 4)
>> +	 *          V   V | V
>
> window boundary points to seq number 6 here. In all other
> examples, it points between 5 and 6. Is that intentional?

Fixed to match others.

>> +	 *                |
>> +	 *  0   1   2   3 |   slot number
>> +	 * ---  0   1   2 |   array index
>
> This looks odd. I guess this is because slot0 does
> not belong to the array. Why is that?

the slots are the logical window, the array implements the physical data structure requirements for holding received future packets. This never includes the missing "next in line" required packet by definition (slot 0 in the window).

> Can we have slot0 integrated in the array? This would make
> the counting much simpler IMO.

We don't want to do this b/c then simple shifting logic doesn't work as slot0 is, by definition, always missing, the code will actually get more complex with an always missing initial array item to be special cased.

>> +	 *     [b] [c] : :|   array
>> +	 *                |
>> +	 * "2" "3" "4" "5"|*6*  seq numbers
>
> Is it so that in the example above packet [a] with seq number 2
> is missing and we have packet [b] with seq number 3 in slot 1
> and packet [c] with seq number 4 in slot 2?

Yes.

>> +	 *
>> +	 * We receive seq number 6
>> +	 * distance == 4 [inseq(6) - w_wantseq(2)]
>> +	 * newslot == distance
>> +	 * index == 3 [distance(4) - 1]
>> +	 * beyond == 1 [newslot(4) - lastslot((nslots(4) - 1))]
>> +	 * shifting == 1 [min(savedlen(2), beyond(1)]
>> +	 * slot0_skb == [b], and should match w_wantseq
>
> We don't have slot0_skb, I guess this is slot0.
>
> How will the example above look like after shifting?
> Is it this:
>
> 	 *  0   1   2   3 |   slot number
> 	 * ---  0   1   2 |   array index
> 	 * [b] [c] : : [e]|   array
> 	 *                |
> 	 * "3" "4" "5" "6"|  seq numbers
>
> Whereby [e] is the packet with seq number 6.

Yes.

>> +	 *
>> +	 *                +--- window boundary (nslots == 4)
>> +	 *  0   1   2   3 | 4   slot number
>> +	 * ---  0   1   2 | 3   array index
>> +	 *     [b] : : : :|     array
>> +	 * "2" "3" "4" "5" *6*  seq numbers
>
> What's the difference to the first example? Is it
> the same but packet [c] is missing?

Yes.

>> +	 *
>> +	 * We receive seq number 6
>> +	 * distance == 4 [inseq(6) - w_wantseq(2)]
>> +	 * newslot == distance
>> +	 * index == 3 [distance(4) - 1]
>> +	 * beyond == 1 [newslot(4) - lastslot((nslots(4) - 1))]
>> +	 * shifting == 1 [min(savedlen(1), beyond(1)]
>> +	 * slot0_skb == [b] and should match w_wantseq
>> +	 *
>> +	 *                +-- window boundary (nslots == 4)
>> +	 *  0   1   2   3 | 4   5   6   slot number
>> +	 * ---  0   1   2 | 3   4   5   array index
>> +	 *     [-] [c] : :|             array
>
> What does [-] mean? Is it the [b] is missing?

Yes. empty (NULL) array item.

>> +	 * "2" "3" "4" "5" "6" "7" *8*  seq numbers
>> +	 *
>> +	 * savedlen = 2, beyond = 3
>> +	 * iter 1: slot0 == NULL, missed++, lastdrop = 2 (2+1-1), slot0 = [-]
>> +	 * iter 2: slot0 == NULL, missed++, lastdrop = 3 (2+2-1), slot0 = [c]
>> +	 * 2 < 3, extra = 1 (3-2), missed += extra, lastdrop = 4 (2+2+1-1)
>> +	 *
>> +	 * We receive seq number 8
>> +	 * distance == 6 [inseq(8) - w_wantseq(2)]
>> +	 * newslot == distance
>> +	 * index == 5 [distance(6) - 1]
>> +	 * beyond == 3 [newslot(6) - lastslot((nslots(4) - 1))]
>> +	 * shifting == 2 [min(savedlen(2), beyond(3)]
>> +	 *
>> +	 * slot0_skb == NULL changed from [b] when "savedlen < beyond" is true.
>> +	 */
>> +
>> +	/* Now send any packets that are being shifted out of saved, and account
>> +	 * for missing packets that are exiting the window as we shift it.
>> +	 */
>
> Documentation is in genaral good, but it must be clear what's
> documented here. It took me quite a while to figure out what
> these examples mean, and I'm still not absoluely sure if
> I'm correct. All that might be clear to you when you wrote
> that, but it is very hard to guess what you thought when
> writing this :)

You understood everything correctly. Sliding window code is by nature complex, and as you noted I really wanted to document the crap out of it to try and help. You got it all right so I think I accomplished the goal. :)

>> +	/* If savedlen > beyond we are shifting some, else all. */
>> +	shifting = min(savedlen, beyond);
>> +
>> +	/* slot0 is the buf that just shifted out and into slot0 */
>> +	slot0 = NULL;
>
> slot0 was set to NULL already at the beginning of this function.
>
> It is just hard to notice because of the huge coment in the middle
> of the function. It might make sense to put all that bigger comments
> to a central place. It would make the functions more readable,
> at least.

That was the intention. :) I removed the redundant assignment above, and moved 2 others below to join the rest.

>> @@ -2222,6 +2700,11 @@ static void iptfs_destroy_state(struct xfrm_state *x)
>>  	if (xtfs->ra_newskb)
>>  		kfree_skb(xtfs->ra_newskb);
>>
>> +	for (s = xtfs->w_saved, se = s + xtfs->w_savedlen; s < se; s++)
>> +		if (s->skb)
>> +			kfree_skb(s->skb);
>
> Braces please.

Done.

Thanks,
Chris.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 857 bytes --]