Sascha Hauer <s.hauer@xxxxxxxxxxxxxx> 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
