mail archive of the barebox mailing list
 help / color / mirror / Atom feed
From: Sascha Hauer <s.hauer@pengutronix.de>
To: Enrico Scholz <enrico.scholz@sigma-chemnitz.de>
Cc: Barebox List <barebox@lists.infradead.org>
Subject: Re: [PATCH 2/3] tftp: implement UDP reorder cache using lists
Date: Mon, 19 Sep 2022 09:33:45 +0200	[thread overview]
Message-ID: <20220919073345.GA6477@pengutronix.de> (raw)
In-Reply-To: <lypmfv8l3c.fsf@ensc-pc.intern.sigma-chemnitz.de>

Hi Enrico,

On Fri, Sep 16, 2022 at 04:12:07PM +0200, Enrico Scholz wrote:
> Sascha Hauer <s.hauer@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.

I don't think that the performance of the cache limits the tftp
performance, given the low number of entries in the cache. You may prove
me wrong here, I don't have any setup here where I could test packet
reordering. What happens here instead is that packets get dropped
because of the RX queue of the network interface get overwhelmed by
packets, see my patch reducing the windowsize setting for i.MX. Packets
get cached then, but the missing packets come in later when retransmits
are triggered. Performance is very bad then anyway.

What counts for me here is the simplicity of the implementation and
the ability to check it for correctness. Here the list implementation
has clear advantages.

The dynamic shrinking/growing of the cache hasn't been a goal for me,
it's just easier to implement then having to maintain a fixed size
pool.

> 
> 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.

Yes, that could be a next step, although the kfifo makes it easy to
decouple the fixed sized blocks coming in from the read() call with
varying sizes.

> 
> 
> > -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.

Oh, yes, I missed this. I'll fix it here and elsewhere. Thanks for
noting.

Sascha

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |



  reply	other threads:[~2022-09-19  7:36 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-16 12:52 [PATCH 0/3] tftp updates Sascha Hauer
2022-09-16 12:52 ` [PATCH 1/3] tftp: remove selftest Sascha Hauer
2022-09-16 12:52 ` [PATCH 2/3] tftp: implement UDP reorder cache using lists Sascha Hauer
2022-09-16 14:12   ` Enrico Scholz
2022-09-19  7:33     ` Sascha Hauer [this message]
2022-09-16 12:52 ` [PATCH 3/3] net: designware_eqos: Allocate more receive buffers Sascha Hauer

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20220919073345.GA6477@pengutronix.de \
    --to=s.hauer@pengutronix.de \
    --cc=barebox@lists.infradead.org \
    --cc=enrico.scholz@sigma-chemnitz.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox