mail archive of the barebox mailing list
 help / color / mirror / Atom feed
* [PATCH 0/3] tftp updates
@ 2022-09-16 12:52 Sascha Hauer
  2022-09-16 12:52 ` [PATCH 1/3] tftp: remove selftest Sascha Hauer
                   ` (2 more replies)
  0 siblings, 3 replies; 6+ messages in thread
From: Sascha Hauer @ 2022-09-16 12:52 UTC (permalink / raw)
  To: Barebox List; +Cc: Enrico Scholz

This series has some updates for the recently introduced RFC7440
support.

Also I found it useful to increase the number of receive packets in the
network driver I am currently using. Other drivers might be adjusted as
well accordingly.

Sascha

Sascha Hauer (3):
  tftp: remove selftest
  tftp: implement UDP reorder cache using lists
  net: designware_eqos: Allocate more receive buffers

 drivers/net/designware_eqos.c |   2 +-
 fs/Kconfig                    |  22 ---
 fs/tftp.c                     | 344 ++++------------------------------
 test/self/Kconfig             |   7 -
 4 files changed, 37 insertions(+), 338 deletions(-)

-- 
2.30.2




^ permalink raw reply	[flat|nested] 6+ messages in thread

* [PATCH 1/3] tftp: remove selftest
  2022-09-16 12:52 [PATCH 0/3] tftp updates Sascha Hauer
@ 2022-09-16 12:52 ` Sascha Hauer
  2022-09-16 12:52 ` [PATCH 2/3] tftp: implement UDP reorder cache using lists Sascha Hauer
  2022-09-16 12:52 ` [PATCH 3/3] net: designware_eqos: Allocate more receive buffers Sascha Hauer
  2 siblings, 0 replies; 6+ messages in thread
From: Sascha Hauer @ 2022-09-16 12:52 UTC (permalink / raw)
  To: Barebox List; +Cc: Enrico Scholz

The out-of-order packet caching will be reworked in the next commit and
most of the functions the self test tests will vanish, so nothing to
test anymore.

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
 fs/tftp.c         | 102 ----------------------------------------------
 test/self/Kconfig |   7 ----
 2 files changed, 109 deletions(-)

diff --git a/fs/tftp.c b/fs/tftp.c
index e0886c49d2..f089e2f693 100644
--- a/fs/tftp.c
+++ b/fs/tftp.c
@@ -1237,105 +1237,3 @@ static int tftp_init(void)
 	return register_fs_driver(&tftp_driver);
 }
 coredevice_initcall(tftp_init);
-
-
-BSELFTEST_GLOBALS();
-
-static int __maybe_unused tftp_window_cache_selftest(void)
-{
-	struct tftp_cache	*cache = malloc(sizeof *cache);
-
-	if (!cache)
-		return -ENOMEM;
-
-	(void)skipped_tests;
-
-	expect_it( is_block_before(0, 1));
-	expect_it(!is_block_before(1, 0));
-	expect_it( is_block_before(65535, 0));
-	expect_it(!is_block_before(0, 65535));
-
-	expect_eq(get_block_delta(0, 1),     1);
-	expect_eq(get_block_delta(65535, 0), 1);
-	expect_eq(get_block_delta(65535, 1), 2);
-
-	expect_it(!in_window(0, 1, 3));
-	expect_it( in_window(1, 1, 3));
-	expect_it( in_window(2, 1, 3));
-	expect_it( in_window(3, 1, 3));
-	expect_it(!in_window(4, 1, 3));
-
-	expect_it(!in_window(65534, 65535, 1));
-	expect_it( in_window(65535, 65535, 1));
-	expect_it( in_window(    0, 65535, 1));
-	expect_it( in_window(    1, 65535, 1));
-	expect_it(!in_window(    2, 65535, 1));
-
-
-	tftp_window_cache_init(cache, 512, 5);
-
-	if (tftp_window_cache_size(cache) < 4)
-		goto out;
-
-	expect_eq(tftp_window_cache_size(cache), 4);
-
-	/* sequence 1 */
-	expect_ok (tftp_window_cache_insert(cache, 20, "20", 2));
-	expect_ok (tftp_window_cache_insert(cache, 22, "22", 2));
-	expect_ok (tftp_window_cache_insert(cache, 21, "21", 2));
-	expect_ok (tftp_window_cache_insert(cache, 23, "23", 2));
-	expect_err(tftp_window_cache_insert(cache, 24, "24", 2));
-	expect_err(tftp_window_cache_insert(cache, 19, "19", 2));
-	expect_ok (tftp_window_cache_insert(cache, 22, "22", 2));
-	expect_ok (tftp_window_cache_insert(cache, 20, "20", 2));
-
-	expect_eq(tftp_window_cache_pop(cache)->id, 20);
-	expect_eq(tftp_window_cache_pop(cache)->id, 21);
-	expect_eq(tftp_window_cache_pop(cache)->id, 22);
-	expect_eq(tftp_window_cache_pop(cache)->id, 23);
-	expect_eq(cache->id, TFTP_CACHE_NO_ID);
-
-	/* sequence 2 */
-	expect_ok (tftp_window_cache_insert(cache, 30, "30", 2));
-	expect_ok (tftp_window_cache_insert(cache, 32, "32", 2));
-	expect_err(tftp_window_cache_insert(cache, 34, "34", 2));
-
-	expect_it(tftp_window_cache_starts_with(cache, 30));
-	expect_eq(tftp_window_cache_pop(cache)->id, 30);
-
-	expect_ok (tftp_window_cache_insert(cache, 34, "34", 2));
-	expect_err(tftp_window_cache_insert(cache, 35, "35", 2));
-
-	expect_it(!tftp_window_cache_starts_with(cache, 30));
-	expect_it(!tftp_window_cache_starts_with(cache, 31));
-	expect_it(!tftp_window_cache_starts_with(cache, 32));
-	expect_NULL(tftp_window_cache_pop(cache));
-
-	expect_it(tftp_window_cache_starts_with(cache, 32));
-	expect_eq(tftp_window_cache_pop(cache)->id, 32);
-
-	expect_NULL(tftp_window_cache_pop(cache));
-	expect_eq(tftp_window_cache_pop(cache)->id, 34);
-
-	expect_eq(cache->id, TFTP_CACHE_NO_ID);
-
-	/* sequence 3 */
-	expect_ok(tftp_window_cache_insert(cache, 40, "40", 2));
-	expect_ok(tftp_window_cache_insert(cache, 42, "42", 2));
-	expect_ok(tftp_window_cache_insert(cache, 43, "43", 2));
-
-	expect_it(!tftp_window_cache_remove_id(cache, 30));
-	expect_it(!tftp_window_cache_remove_id(cache, 41));
-	expect_it(!tftp_window_cache_remove_id(cache, 44));
-
-	expect_it( tftp_window_cache_remove_id(cache, 42));
-	expect_it(!tftp_window_cache_remove_id(cache, 42));
-
-out:
-	tftp_window_cache_free(cache);
-
-	return 0;
-}
-#ifdef CONFIG_SELFTEST_TFTP
-bselftest(core, tftp_window_cache_selftest);
-#endif
diff --git a/test/self/Kconfig b/test/self/Kconfig
index 03cfa89987..680196a4fe 100644
--- a/test/self/Kconfig
+++ b/test/self/Kconfig
@@ -32,7 +32,6 @@ config SELFTEST_ENABLE_ALL
 	select SELFTEST_PROGRESS_NOTIFIER
 	select SELFTEST_OF_MANIPULATION
 	select SELFTEST_ENVIRONMENT_VARIABLES if ENVIRONMENT_VARIABLES
-	imply SELFTEST_TFTP
 	help
 	  Selects all self-tests compatible with current configuration
 
@@ -58,10 +57,4 @@ config SELFTEST_PROGRESS_NOTIFIER
 config SELFTEST_ENVIRONMENT_VARIABLES
 	bool "environment variable selftest"
 
-config SELFTEST_TFTP
-	bool "tftp selftest"
-	depends on FS_TFTP
-	help
-	  Tests tftp functionality
-
 endif
-- 
2.30.2




^ permalink raw reply	[flat|nested] 6+ messages in thread

* [PATCH 2/3] tftp: implement UDP reorder cache using lists
  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 ` Sascha Hauer
  2022-09-16 14:12   ` Enrico Scholz
  2022-09-16 12:52 ` [PATCH 3/3] net: designware_eqos: Allocate more receive buffers Sascha Hauer
  2 siblings, 1 reply; 6+ messages in thread
From: Sascha Hauer @ 2022-09-16 12:52 UTC (permalink / raw)
  To: Barebox List; +Cc: Enrico Scholz

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.

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
 fs/Kconfig |  22 -----
 fs/tftp.c  | 242 ++++++++---------------------------------------------
 2 files changed, 36 insertions(+), 228 deletions(-)

diff --git a/fs/Kconfig b/fs/Kconfig
index cf884e0646..0c49342859 100644
--- a/fs/Kconfig
+++ b/fs/Kconfig
@@ -57,28 +57,6 @@ config FS_TFTP_MAX_WINDOW_SIZE
 	  Requires tftp "windowsize" (RFC 7440) support on server side
 	  to have an effect.
 
-config FS_TFTP_REORDER_CACHE_SIZE
-	int
-	prompt "number of out-of-order tftp packets to be cached"
-	depends on FS_TFTP
-	default 16 if FS_TFTP_MAX_WINDOW_SIZE > 16
-	default  0 if FS_TFTP_MAX_WINDOW_SIZE = 1
-        ## TODO: it should be 'FS_TFTP_MAX_WINDOW_SIZE - 1' but this
-        ## is not supported by Kconfig
-	default FS_TFTP_MAX_WINDOW_SIZE
-	range 0 FS_TFTP_MAX_WINDOW_SIZE
-	help
-	  UDP allows reordering of datagrams; with this option,
-	  unexpected tftp packets will be cached and later
-	  reassembled.  This increases stability of the tftp download
-	  with the cost of memory (around 1440 bytes per cache
-	  element) and barebox binary size (around 700 bytes).
-
-	  A value of 0 disables caching.
-
-	  Requires tftp "windowsize" (RFC 7440) support on server side
-	  to have an effect.
-
 config FS_OMAP4_USBBOOT
 	bool
 	prompt "Filesystem over usb boot"
diff --git a/fs/tftp.c b/fs/tftp.c
index f089e2f693..0094825217 100644
--- a/fs/tftp.c
+++ b/fs/tftp.c
@@ -78,9 +78,6 @@
 /* allocate this number of blocks more than needed in the fifo */
 #define TFTP_EXTRA_BLOCKS	2
 
-/* size of cache which deals with udp reordering */
-#define TFTP_WINDOW_CACHE_NUM	CONFIG_FS_TFTP_REORDER_CACHE_SIZE
-
 /* marker for an emtpy 'tftp_cache' */
 #define TFTP_CACHE_NO_ID	(-1)
 
@@ -101,24 +98,12 @@ struct tftp_block {
 	uint16_t id;
 	uint16_t len;
 
-	struct list_head head;
+	struct list_head list;
 	uint8_t data[];
 };
 
 struct tftp_cache {
-	/* The id located at @pos or TFTP_CACHE_NO_ID when cache is empty.  It
-	   is possible that the corresponding bit in @used is NOT set. */
-	unsigned int		id;
-	unsigned int		pos;
-
-	/* bitmask */
-	unsigned long		used[BITS_TO_LONGS(TFTP_WINDOW_CACHE_NUM)];
-
-	/* size of the cache; is limited by TFTP_WINDOW_CACHE_NUM and the
-	   actual window size */
-	unsigned int		size;
-	unsigned int		block_len;
-	struct tftp_block	*blocks[TFTP_WINDOW_CACHE_NUM];
+	struct list_head	blocks;
 };
 
 struct file_priv {
@@ -145,18 +130,6 @@ struct tftp_priv {
 	IPaddr_t server;
 };
 
-static inline bool is_block_before(uint16_t a, uint16_t b)
-{
-	return (int16_t)(b - a) > 0;
-}
-
-static inline uint16_t get_block_delta(uint16_t a, uint16_t b)
-{
-	debug_assert(!is_block_before(b, a));
-
-	return b - a;
-}
-
 static bool in_window(uint16_t block, uint16_t start, uint16_t end)
 {
 	/* handle the three cases:
@@ -169,191 +142,37 @@ static bool in_window(uint16_t block, uint16_t start, uint16_t end)
 		(end   <= start && start <= block));
 }
 
-static inline size_t tftp_window_cache_size(struct tftp_cache const *cache)
-{
-	/* allows to optimize away the cache code when TFTP_WINDOW_CACHE_SIZE
-	   is 0 */
-	return TFTP_WINDOW_CACHE_NUM == 0 ? 0 : cache->size;
-}
-
-static void tftp_window_cache_init(struct tftp_cache *cache,
-				   uint16_t block_len, uint16_t window_size)
-{
-	debug_assert(window_size > 0);
-
-	*cache = (struct tftp_cache) {
-		.id		= TFTP_CACHE_NO_ID,
-		.block_len	= block_len,
-		.size		= min_t(uint16_t, window_size - 1,
-					ARRAY_SIZE(cache->blocks)),
-	};
-}
-
 static void tftp_window_cache_free(struct tftp_cache *cache)
 {
-	size_t	cache_size = tftp_window_cache_size(cache);
-	size_t	i;
+	struct tftp_block *block, *tmp;
 
-	for (i = 0; i < cache_size; ++i) {
-		free(cache->blocks[i]);
-		cache->blocks[i] = NULL;
-	}
-}
-
-static void tftp_window_cache_reset(struct tftp_cache *cache)
-{
-	cache->id = TFTP_CACHE_NO_ID;
-	memset(cache->used, 0, sizeof cache->used);
-}
-
-static int tftp_window_cache_get_pos(struct tftp_cache const *cache, uint16_t id)
-{
-	size_t		cache_size = tftp_window_cache_size(cache);
-	unsigned int	pos;
-
-	if (cache_size == 0)
-		return -1;
-
-	if (cache->id == TFTP_CACHE_NO_ID)
-		return -1;
-
-	if (!in_window(id, cache->id, cache->id + cache_size - 1))
-		return -1;
-
-	pos  = cache->pos + get_block_delta(cache->id, id);
-	pos %= cache_size;
-
-	return pos;
-}
-
-/* returns whether the first cached element has the given @id */
-static bool tftp_window_cache_starts_with(struct tftp_cache const *cache,
-					  uint16_t id)
-{
-	return (TFTP_WINDOW_CACHE_NUM > 0 &&
-		cache->id != TFTP_CACHE_NO_ID &&
-		cache->id == id &&
-		test_bit(cache->pos, cache->used));
-}
-
-static bool tftp_window_cache_is_empty(struct tftp_cache const *cache)
-{
-	/* use this indirection to avoid warnings about a '0 < 0' comparison
-	   in the loop condition when TFTP_WINDOW_CACHE_NUM is zero */
-	size_t	cache_size = ARRAY_SIZE(cache->used);
-	size_t	i;
-
-	for (i = 0; i < cache_size; ++i) {
-		if (cache->used[i] != 0)
-			return false;
-	}
-
-	return true;
+	list_for_each_entry_safe(block, tmp, &cache->blocks, list)
+		free(block);
 }
 
 static int tftp_window_cache_insert(struct tftp_cache *cache, uint16_t id,
 				    void const *data, size_t len)
 {
-	size_t const		cache_size = tftp_window_cache_size(cache);
-	int			pos;
-	struct tftp_block	*block;
-
-	if (cache_size == 0)
-		return -ENOSPC;
-
-	if (cache->id == TFTP_CACHE_NO_ID) {
-		/* initialize cache when it does not contain elements yet */
-		cache->id = id;
-		cache->pos = 0;
-
-		/* sanity check; cache is expected to be empty */
-		debug_assert(tftp_window_cache_is_empty(cache));
-	}
-
-	pos = tftp_window_cache_get_pos(cache, id);
-	if (pos < 0)
-		return -ENOSPC;
-
-	debug_assert(pos < cache_size);
-
-	if (test_bit(pos, cache->used))
-		/* block already cached */
-		return 0;
+	struct tftp_block *block, *new;
 
-	block = cache->blocks[pos];
-	if (!block) {
-		/* allocate space for the block; after being released, this
-		   memory can be reused for other blocks during the same tftp
-		   transfer */
-		block = malloc(sizeof *block + cache->block_len);
-		if (!block)
-			return -ENOMEM;
+	list_for_each_entry(block, &cache->blocks, list) {
+		if (block->id == id)
+			return 0;
+		if (block->id < id)
+			continue;
 
-		cache->blocks[pos] = block;
+		break;
 	}
 
-	__set_bit(pos, cache->used);
-	memcpy(block->data, data, len);
-	block->id = id;
-	block->len = len;
+	new = xzalloc(sizeof(*new) + len);
+	memcpy(new->data, data, len);
+	new->id = id;
+	new->len = len;
+	list_add_tail(&new->list, &block->list);
 
 	return 0;
 }
 
-/* Marks the element at 'pos' as unused and updates internal cache information.
-   Returns true iff element at pos was valid. */
-static bool tftp_window_cache_remove(struct tftp_cache *cache, unsigned int pos)
-{
-	size_t const	cache_size = tftp_window_cache_size(cache);
-	bool		res;
-
-	if (cache_size == 0)
-		return 0;
-
-	res = __test_and_clear_bit(pos, cache->used);
-
-	if (tftp_window_cache_is_empty(cache)) {
-		/* cache has been cleared; reset pointers */
-		cache->id = TFTP_CACHE_NO_ID;
-	} else if (pos != cache->pos) {
-		/* noop; elements has been removed from the middle of cache */
-	} else {
-		/* first element of cache has been removed; proceed to the
-		   next one */
-		cache->id  += 1;
-		cache->pos += 1;
-		cache->pos %= cache_size;
-	}
-
-	return res;
-}
-
-/* Releases the first element from the cache and returns its content.
- *
- * Function can return NULL when the element is not cached
- */
-static struct tftp_block *tftp_window_cache_pop(struct tftp_cache *cache)
-{
-	unsigned int	pos = cache->pos;
-
-	debug_assert(cache->id != TFTP_CACHE_NO_ID);
-
-	if (!tftp_window_cache_remove(cache, pos))
-		return NULL;
-
-	return cache->blocks[pos];
-}
-
-static bool tftp_window_cache_remove_id(struct tftp_cache *cache, uint16_t id)
-{
-	int		pos = tftp_window_cache_get_pos(cache, id);
-
-	if (pos < 0)
-		return false;
-
-	return tftp_window_cache_remove(cache, pos);
-}
-
 static int tftp_truncate(struct device_d *dev, FILE *f, loff_t size)
 {
 	return 0;
@@ -444,7 +263,6 @@ static int tftp_send(struct file_priv *priv)
 		priv->ack_block += priv->windowsize;
 		pkt = (unsigned char *)s;
 		len = pkt - xp;
-		tftp_window_cache_reset(&priv->cache);
 		break;
 	}
 
@@ -562,8 +380,7 @@ static int tftp_allocate_transfer(struct file_priv *priv)
 			goto err;
 		}
 	} else {
-		tftp_window_cache_init(&priv->cache,
-				       priv->blocksize, priv->windowsize);
+		INIT_LIST_HEAD(&priv->cache.blocks);
 	}
 
 	return 0;
@@ -606,7 +423,7 @@ static void tftp_apply_window_cache(struct file_priv *priv)
 {
 	struct tftp_cache *cache = &priv->cache;
 
-	while (tftp_window_cache_starts_with(cache, priv->last_block + 1)) {
+	while (1) {
 		struct tftp_block *block;
 
 		/* can be changed by tftp_put_data() below and must be
@@ -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) {
+			/* shouldn't happen, but be sure */
+			list_del(&block->list);
+			free(block);
+			continue;
+		}
+
+		if (block->id != priv->last_block + 1)
+			return;
 
 		tftp_put_data(priv, block->id, block->data, block->len);
+
+		list_del(&block->list);
+
+		free(block);
 	}
 }
 
@@ -636,7 +467,6 @@ static void tftp_handle_data(struct file_priv *priv, uint16_t block,
 		   fifo directly and try to apply cached items then */
 		tftp_timer_reset(priv);
 		tftp_put_data(priv, block, data, len);
-		tftp_window_cache_remove_id(&priv->cache, block);
 		tftp_apply_window_cache(priv);
 	} else if (!in_window(block, exp_block, priv->ack_block)) {
 		/* completely unexpected and unrelated to actual window;
-- 
2.30.2




^ permalink raw reply	[flat|nested] 6+ messages in thread

* [PATCH 3/3] net: designware_eqos: Allocate more receive buffers
  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 12:52 ` Sascha Hauer
  2 siblings, 0 replies; 6+ messages in thread
From: Sascha Hauer @ 2022-09-16 12:52 UTC (permalink / raw)
  To: Barebox List; +Cc: Enrico Scholz

With RFC7440 support in TFTP we can make good use of more receive
buffers. Increase the number.

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
 drivers/net/designware_eqos.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/net/designware_eqos.c b/drivers/net/designware_eqos.c
index 79b9979697..7ff0b8489c 100644
--- a/drivers/net/designware_eqos.c
+++ b/drivers/net/designware_eqos.c
@@ -169,7 +169,7 @@ struct eqos_dma_regs {
 /* We assume ARCH_DMA_MINALIGN >= 16; 16 is the EQOS HW minimum */
 #define EQOS_DESCRIPTOR_ALIGN	64
 #define EQOS_DESCRIPTORS_TX	4
-#define EQOS_DESCRIPTORS_RX	4
+#define EQOS_DESCRIPTORS_RX	64
 #define EQOS_DESCRIPTORS_NUM	(EQOS_DESCRIPTORS_TX + EQOS_DESCRIPTORS_RX)
 #define EQOS_DESCRIPTORS_SIZE	ALIGN(EQOS_DESCRIPTORS_NUM * \
 				      EQOS_DESCRIPTOR_SIZE, EQOS_DESCRIPTOR_ALIGN)
-- 
2.30.2




^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH 2/3] tftp: implement UDP reorder cache using lists
  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
  0 siblings, 1 reply; 6+ messages in thread
From: Enrico Scholz @ 2022-09-16 14:12 UTC (permalink / raw)
  To: Sascha Hauer; +Cc: Barebox List

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.

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



^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH 2/3] tftp: implement UDP reorder cache using lists
  2022-09-16 14:12   ` Enrico Scholz
@ 2022-09-19  7:33     ` Sascha Hauer
  0 siblings, 0 replies; 6+ messages in thread
From: Sascha Hauer @ 2022-09-19  7:33 UTC (permalink / raw)
  To: Enrico Scholz; +Cc: Barebox List

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 |



^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2022-09-19  7:36 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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
2022-09-16 12:52 ` [PATCH 3/3] net: designware_eqos: Allocate more receive buffers Sascha Hauer

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox