[PATCH 2/3] tftp: implement UDP reorder cache using lists

[Enrico Scholz]

Sascha Hauer <s.hauer at pengutronix.de> writes:

> The UDP reorder cache can be much easier implemented using lists.
> As a bonus the cache grows and shrinks on demand and no fixed size
> has to be configured at compile time.

There are three variants of the cache

- small, fixed sized array with linear search (very first
  implementation)  -->  O(n)
- list --> O(n) on insert, O(1) on lookup
- bitmap --> O(1)


Performance wise, I think the list implementation is the slowest one
(although the fixed sized array is O(n) on every operation, this should
be still faster for small n than the list operations and the related
memory management).

>From code size, the list implementation is in the middle.

I am not sure whether dynamic shrinking/growing of the cache is so
important or whether a small, fixed sized cache suffices.  In my
experience, only the first couple of packets really matter regarding
reordering.

Of course, the 'kfifo' could be replaced completely by a custom buffer
implementation where packets are inserted at the correct position.  O(1)
for every operation + zero additional memory.


> -static inline bool is_block_before(uint16_t a, uint16_t b)
> -{
> -	return (int16_t)(b - a) > 0;
> -}
> -
> ....
>  static int tftp_window_cache_insert(struct tftp_cache *cache, uint16_t id,
>  				    void const *data, size_t len)
>  {
> ...
> +	list_for_each_entry(block, &cache->blocks, list) {

fwiw, iterating in the reverse direction will find the position probably
faster


> +		if (block->id == id)
> +			return 0;
> +		if (block->id < id)

This will break when wrapping at 65535; the removed 'is_block_before()'
function was written for this case.


> @@ -614,12 +431,26 @@ static void tftp_apply_window_cache(struct file_priv *priv)
>  		if (priv->state != STATE_RDATA)
>  			return;
>  
> -		block = tftp_window_cache_pop(cache);
> +		if (list_empty(&cache->blocks))
> +			return;
>  
> -		debug_assert(block);
> -		debug_assert(block->id == (uint16_t)(priv->last_block + 1));
> +		block = list_first_entry(&cache->blocks, struct tftp_block, list);
> +
> +		if (block->id < priv->last_block + 1) {

ditto; wrapping at 65535


> +			/* shouldn't happen, but be sure */
> +			list_del(&block->list);
> +			free(block);
> +			continue;
> +		}
> +
> +		if (block->id != priv->last_block + 1)

ditto; wrapping at 65535.  Resp. should be written as

|		if (block->id != (uint16_t)(priv->last_block + 1))



Enrico