public inbox for passt-dev@passt.top
 help / color / mirror / code / Atom feed
From: Stefano Brivio <sbrivio@redhat.com>
To: David Gibson <david@gibson.dropbear.id.au>
Cc: passt-dev@passt.top
Subject: Re: [PATCH v3 13/13] flow: Avoid moving flow entries to compact table
Date: Sat, 30 Dec 2023 11:33:04 +0100	[thread overview]
Message-ID: <20231230113304.37c60a9a@elisabeth> (raw)
In-Reply-To: <20231228192525.7ba1ee48@elisabeth>

On Thu, 28 Dec 2023 19:25:25 +0100
Stefano Brivio <sbrivio@redhat.com> wrote:

> > On Thu, 21 Dec 2023 17:15:49 +1100
> > David Gibson <david@gibson.dropbear.id.au> wrote:
> > 
> > [...]
>
> [...]
>
> I wonder if we really have to keep track of the number of (non-)entries
> in the free "block", and if we have to be explicit about the two cases.
> 
> I'm trying to find out if we can simplify the whole thing with slightly
> different variants, for example:

So... I think the version with (explicit) blocks has this fundamental
advantage, on deletion:

> > +	flow->f.type = FLOW_TYPE_NONE;
> > +	/* Put it back in a length 1 free block, don't attempt to fully reverse
> > +	 * flow_alloc()s steps.  This will get folded together the next time
> > +	 * flow_defer_handler runs anyway() */
> > +	flow->free.n = 1;
> > +	flow->free.next = flow_first_free;
> > +	flow_first_free = FLOW_IDX(flow);

which is doable even without explicit blocks, but much harder to
follow.

Other than the comments I have, I would go ahead with your approach. My
attempt below in case you're interested. The comment at the end of
flow_del() shows the issue I'm facing:

struct flow_free_block {
	/* Must be first element */
	struct flow_common f;

	unsigned next_free;
	unsigned next_used;
};

static union flow *flow_alloc(void)
{
	union flow *flow;

	if (flow_first_free >= FLOW_MAX)
		return NULL;

	flow = flowtab + flow_first_free;

	flow_first_free = flow->free.next_free;

	memset(flow, 0, sizeof(*flow));		/* TODO: select region */
	return flow;
}

static void flow_del(union flow *del)
{
	union flow *left, *right, *next_used = NULL, *first_free;

	del->f.type = FLOW_TYPE_NONE;

	left =  (FLOW_IDX(del) > 0)            ? FLOW(FLOW_IDX(del) - 1) : NULL;
	right = (FLOW_IDX(del) < FLOW_MAX - 1) ? FLOW(FLOW_IDX(del) + 1) : NULL;

	first_free = flow_first_free < FLOW_MAX ? FLOW(flow_first_free) : NULL;

	if (right) {
		if (right->f.type == FLOW_TYPE_NONE)
			del->free.next_used = right->free.next_used;
		else
			del->free.next_used = right;
	} else {
		del->free.next_used = FLOW_MAX;
	}

	if (left && left->f.type == FLOW_TYPE_NONE) {
		left->free.next_free = FLOW_IDX(del);
		left->free.next_used = del->free.next_used;
		return;
	}

	if (flow_first_free == FLOW_MAX) {
		flow_first_free = FLOW_IDX(del);
	} else if (flow_first_free > FLOW_IDX(del)) {
		flow_first_free = FLOW_IDX(del);
		del->free.next_free = flow_first_free;
	} else if (flow_first_free < FLOW_IDX(del)) {
		;
		/* Walk free slots from flow_first_free until FLOW_IDX(del) to
		 * find insertion point... but that makes deletion at most O(n),
		 * perhaps O(log(n)), certainly not O(1).
		 *
		 * Or just link out-of-order for the moment, and fix this up in
		 * flow_next(), but then "blocks" help representing this.
		 */
	}
}

static union flow *flow_next(union flow *whence)
{
	if (FLOW_IDX(whence) >= FLOW_MAX - 1)
		return NULL;

	if (whence->f.type != FLOW_TYPE_NONE)
		whence++;

	if (whence->f.type == FLOW_TYPE_NONE)
		return whence->free.next_used;

	return whence;
}

-- 
Stefano


  reply	other threads:[~2023-12-30 10:33 UTC|newest]

Thread overview: 40+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-12-21  6:15 [PATCH v3 00/13] Manage more flow related things from generic flow code David Gibson
2023-12-21  6:15 ` [PATCH v3 01/13] flow: Make flow_table.h #include the protocol specific headers it needs David Gibson
2023-12-21  6:15 ` [PATCH v3 02/13] treewide: Standardise on 'now' for current timestamp variables David Gibson
2023-12-21  6:15 ` [PATCH v3 03/13] tcp, tcp_splice: Remove redundant handling from tcp_timer() David Gibson
2023-12-21  6:15 ` [PATCH v3 04/13] tcp, tcp_splice: Move per-type cleanup logic into per-type helpers David Gibson
2023-12-21  6:15 ` [PATCH v3 05/13] flow, tcp: Add flow-centric dispatch for deferred flow handling David Gibson
2023-12-28 18:24   ` Stefano Brivio
2023-12-31  5:56     ` David Gibson
2024-01-02 18:13       ` Stefano Brivio
2024-01-03  3:45         ` David Gibson
2023-12-21  6:15 ` [PATCH v3 06/13] flow, tcp: Add handling for per-flow timers David Gibson
2023-12-21  6:15 ` [PATCH v3 07/13] epoll: Better handling of number of epoll types David Gibson
2023-12-21  6:15 ` [PATCH v3 08/13] tcp, tcp_splice: Avoid double layered dispatch for connected TCP sockets David Gibson
2023-12-21  6:15 ` [PATCH v3 09/13] flow: Move flow_log_() to near top of flow.c David Gibson
2023-12-21  6:15 ` [PATCH v3 10/13] flow: Move flow_count from context structure to a global David Gibson
2023-12-28 18:25   ` Stefano Brivio
2023-12-31  5:58     ` David Gibson
2024-01-02 18:13       ` Stefano Brivio
2024-01-03  3:54         ` David Gibson
2024-01-03  7:08           ` Stefano Brivio
2024-01-04  9:51             ` David Gibson
2024-01-05  7:55               ` Stefano Brivio
2024-01-07  5:23                 ` David Gibson
2023-12-21  6:15 ` [PATCH v3 11/13] flow: Abstract allocation of new flows with helper function David Gibson
2023-12-21  6:15 ` [PATCH v3 12/13] flow: Enforce that freeing of closed flows must happen in deferred handlers David Gibson
2023-12-21  6:15 ` [PATCH v3 13/13] flow: Avoid moving flow entries to compact table David Gibson
2023-12-28 18:25   ` Stefano Brivio
2023-12-30 10:33     ` Stefano Brivio [this message]
2024-01-01 12:01       ` David Gibson
2024-01-02 18:13         ` Stefano Brivio
2024-01-04 10:02           ` David Gibson
2024-01-05  8:33             ` Stefano Brivio
2024-01-05  9:39               ` David Gibson
2024-01-05 10:27                 ` Stefano Brivio
2024-01-06 11:32                   ` David Gibson
2024-01-06 13:02                     ` Stefano Brivio
2024-01-07  5:20                       ` David Gibson
2024-01-01 10:44     ` David Gibson
2024-01-02 18:13       ` Stefano Brivio
2024-01-05  9:45         ` David Gibson

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=20231230113304.37c60a9a@elisabeth \
    --to=sbrivio@redhat.com \
    --cc=david@gibson.dropbear.id.au \
    --cc=passt-dev@passt.top \
    /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.
Code repositories for project(s) associated with this public inbox

	https://passt.top/passt

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for IMAP folder(s).