mail archive of the barebox mailing list
 help / color / mirror / Atom feed
From: Sascha Hauer <s.hauer@pengutronix.de>
To: Barebox List <barebox@lists.infradead.org>
Cc: Enrico Scholz <enrico.scholz@sigma-chemnitz.de>
Subject: [PATCH 2/3] tftp: implement UDP reorder cache using lists
Date: Fri, 16 Sep 2022 14:52:31 +0200	[thread overview]
Message-ID: <20220916125232.3775559-3-s.hauer@pengutronix.de> (raw)
In-Reply-To: <20220916125232.3775559-1-s.hauer@pengutronix.de>

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




  parent reply	other threads:[~2022-09-16 12:54 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 ` Sascha Hauer [this message]
2022-09-16 14:12   ` [PATCH 2/3] tftp: implement UDP reorder cache using lists 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

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=20220916125232.3775559-3-s.hauer@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