Re: [PATCH net-next v2 4/9] hsr: Implement more robust duplicate discard for PRP

[Sebastian Andrzej Siewior <bigeasy@linutronix.de>]

On 2026-01-22 15:56:59 [+0100], Felix Maurer wrote:
> The PRP duplicate discard algorithm does not work reliably with certain
…
> The idea of the new algorithm is to store the seen sequence numbers in a
> bitmap. To keep the size of the bitmap in control, we store it as a "sparse
> bitmap" where the bitmap is split into blocks and not all blocks exist at
> the same time. The sparse bitmap is implemented using an xarray that keeps
> the references to the individual blocks and a backing ring buffer that
…

My idea was to keep track of say the last 64 sequence numbers but I had
no idea how to efficiently implement it with all the "forget" parts and
so on. What you did here is quite nice.

> @@ -280,6 +301,59 @@ struct hsr_node *hsr_get_node(struct hsr_port *port, struct list_head *node_db,
…
> +/* Get the currently active sequence number block. If there is no block yet, or
> + * the existing one is expired, a new block is created. The idea is to maintain
> + * a "sparse bitmap" where a bitmap for the whole sequence number space is
> + * split into blocks and not all blocks exist all the time. The blocks can
> + * expire after time (in low traffic situations) or when they are replaced in
> + * the backing fixed size buffer (in high traffic situations).
                                    HSR_MAX_SEQ_BLOCKS, 
> + */
> +static struct hsr_seq_block *hsr_get_seq_block(struct hsr_node *node,
> +					       u16 block_idx)
> +{
> +	struct hsr_seq_block *block, *res;
> +
> +	block = xa_load(&node->seq_blocks, block_idx);
> +
> +	if (block && hsr_seq_block_is_old(block)) {
> +		hsr_forget_seq_block(node, block);
> +		block = NULL;
> +	}
> +
> +	if (!block) {
> +		block = &node->block_buf[node->next_block];
> +		hsr_forget_seq_block(node, block);
> +
> +		memset(block, 0, sizeof(*block));
> +		block->time = jiffies;

So we assign ->time here while the block is created and it expires after
HSR_ENTRY_FORGET_TIME (400ms). *Maybe* it should be updated in
hsr_check_duplicate() if we set a bit. The difference would be that the
last sequence in the block would get it whole life time while now the
lifetime starts with the first entry in the block. The downside
of course would be that the first entry gets more than the initialy
expected lifetime.
Not sure if this matters in reality, just wanted to mention.

> +		block->block_idx = block_idx;
> +
> +		res = xa_store(&node->seq_blocks, block_idx, block, GFP_ATOMIC);
> +		if (xa_is_err(res))
> +			return NULL;
> +
> +		node->next_block =
> +			(node->next_block + 1) & (HSR_MAX_SEQ_BLOCKS - 1);
> +	}
> +
> +	return block;
> +}
> +
>  /* Use the Supervision frame's info about an eventual macaddress_B for merging
>   * nodes that has previously had their macaddress_B registered as a separate
>   * node.
> @@ -545,47 +631,26 @@ int prp_register_frame_out(struct hsr_port *port, struct hsr_frame_info *frame)
…
> +
> +	seq_bit = hsr_seq_block_bit(sequence_nr);
> +	if (test_and_set_bit(seq_bit, block->seq_nrs))

the access happens under ::seq_out_lock so you don't need to be atomic
here. You could safe a cycle and use __test_and_set_bit() instead.

> +		goto out_seen;
>  
>  	node->time_out[port->type] = jiffies;
>  	node->seq_out[port->type] = sequence_nr;
> +out_new:
>  	spin_unlock_bh(&node->seq_out_lock);
>  	return 0;
> +
> +out_seen:
> +	spin_unlock_bh(&node->seq_out_lock);
> +	return 1;
>  }
>  
>  #if IS_MODULE(CONFIG_PRP_DUP_DISCARD_KUNIT_TEST)

Sebastian