Re: [PATCH v3 13/13] flow: Avoid moving flow entries to compact table

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

...
 
  On Thu, 21 Dec
2023 17:15:49 +1100
 David Gibson <david(a)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