On Thu, 21 Dec 2023 17:15:41 +1100
David Gibson <david(a)gibson.dropbear.id.au> wrote:

...
  tcp_defer_handler(), amongst other things, scans the
flow table and does
 some processing for each TCP connection.  When we add other protocols to
 the flow table, they're likely to want some similar scanning.  It makes
 more sense for cache friendliness to perform a single scan of the flow
 table and dispatch to the protocol specific handlers, rather than having
 each protocol separately scan the table.
 
 To that end, add a new flow_defer_handler() handling all flow-linked
 deferred operations.
 
 Signed-off-by: David Gibson <david(a)gibson.dropbear.id.au>
 ---
  flow.c     | 23 +++++++++++++++++++++++
  flow.h     |  1 +
  passt.c    |  1 +
  tcp.c      | 19 ++-----------------
  tcp_conn.h |  1 +
  5 files changed, 28 insertions(+), 17 deletions(-)
 
 diff --git a/flow.c b/flow.c
 index a1c0a34..0a0402d 100644
 --- a/flow.c
 +++ b/flow.c
 @@ -83,3 +83,26 @@ void flow_log_(const struct flow_common *f, int pri, const char *fmt,
...)
  
  	logmsg(pri, "Flow %u (%s): %s", flow_idx(f), FLOW_TYPE(f), msg);
  }
 +
 +/**
 + * flow_defer_handler() - Handler for per-flow deferred tasks
 + * @c:		Execution context
 + */
 +void flow_defer_handler(struct ctx *c)
 +{
 +	union flow *flow;
 +
 +	for (flow = flowtab + c->flow_count - 1; flow >= flowtab; flow--) {
 +		switch (flow->f.type) {
 +		case FLOW_TCP:
 +			tcp_flow_defer(c, flow);
 +			break;
 +		case FLOW_TCP_SPLICE:
 +			tcp_splice_flow_defer(c, flow);
 +			break;
 +		default:
 +			/* Assume other flow types don't need any handling */
 +			;
 +		}
 +	}
 +}
 diff --git a/flow.h b/flow.h
 index 959b461..6b17fa8 100644
 --- a/flow.h
 +++ b/flow.h
 @@ -67,6 +67,7 @@ static inline bool flow_sidx_eq(flow_sidx_t a, flow_sidx_t b)
  union flow;
  
  void flow_table_compact(struct ctx *c, union flow *hole);
 +void flow_defer_handler(struct ctx *c);
  
  void flow_log_(const struct flow_common *f, int pri, const char *fmt, ...)
  	__attribute__((format(printf, 3, 4)));
 diff --git a/passt.c b/passt.c
 index 0246b04..5f72a28 100644
 --- a/passt.c
 +++ b/passt.c
 @@ -103,6 +103,7 @@ static void post_handler(struct ctx *c, const struct timespec *now)
  	/* NOLINTNEXTLINE(bugprone-branch-clone): intervals can be the same */
  	CALL_PROTO_HANDLER(c, now, icmp, ICMP);
  
 +	flow_defer_handler(c);
  #undef CALL_PROTO_HANDLER
  }
  
 diff --git a/tcp.c b/tcp.c
 index ad1a70d..9230d80 100644
 --- a/tcp.c
 +++ b/tcp.c
 @@ -1306,7 +1306,7 @@ static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c,
   * @c:		Execution context
   * @flow:	Flow table entry for this connection
   */
 -static void tcp_flow_defer(struct ctx *c, union flow *flow)
 +void tcp_flow_defer(struct ctx *c, union flow *flow)
  {
  	const struct tcp_tap_conn *conn = &flow->tcp;
  
 @@ -1364,26 +1364,11 @@ static void tcp_l2_data_buf_flush(const struct ctx *c)
   * tcp_defer_handler() - Handler for TCP deferred tasks
   * @c:		Execution context
   */
 +/* cppcheck-suppress constParameterPointer */ 
This needs to be:

  /* cppcheck-suppress [constParameterPointer, unmatchedSuppression] */

otherwise we get warnings with cppcheck 2.10, and we'll get warnings if
cppcheck's behaviour ever changes again.

-- 
Stefano

On Sun, 31 Dec 2023 16:56:30 +1100
David Gibson <david(a)gibson.dropbear.id.au> wrote:

...
  On Thu, Dec 28, 2023 at 07:24:46PM +0100, Stefano
Brivio wrote:
  On Thu, 21 Dec 2023 17:15:41 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  tcp_defer_handler(), amongst other things, scans
the flow table and does
 some processing for each TCP connection.  When we add other protocols to
 the flow table, they're likely to want some similar scanning.  It makes
 more sense for cache friendliness to perform a single scan of the flow
 table and dispatch to the protocol specific handlers, rather than having
 each protocol separately scan the table.
 
 To that end, add a new flow_defer_handler() handling all flow-linked
 deferred operations.
 
 Signed-off-by: David Gibson <david(a)gibson.dropbear.id.au>
 ---
  flow.c     | 23 +++++++++++++++++++++++
  flow.h     |  1 +
  passt.c    |  1 +
  tcp.c      | 19 ++-----------------
  tcp_conn.h |  1 +
  5 files changed, 28 insertions(+), 17 deletions(-)
 
 diff --git a/flow.c b/flow.c
 index a1c0a34..0a0402d 100644
 --- a/flow.c
 +++ b/flow.c
 @@ -83,3 +83,26 @@ void flow_log_(const struct flow_common *f, int pri, const char *fmt,
...)
  
  	logmsg(pri, "Flow %u (%s): %s", flow_idx(f), FLOW_TYPE(f), msg);
  }
 +
 +/**
 + * flow_defer_handler() - Handler for per-flow deferred tasks
 + * @c:		Execution context
 + */
 +void flow_defer_handler(struct ctx *c)
 +{
 +	union flow *flow;
 +
 +	for (flow = flowtab + c->flow_count - 1; flow >= flowtab; flow--) {
 +		switch (flow->f.type) {
 +		case FLOW_TCP:
 +			tcp_flow_defer(c, flow);
 +			break;
 +		case FLOW_TCP_SPLICE:
 +			tcp_splice_flow_defer(c, flow);
 +			break;
 +		default:
 +			/* Assume other flow types don't need any handling */
 +			;
 +		}
 +	}
 +}
 diff --git a/flow.h b/flow.h
 index 959b461..6b17fa8 100644
 --- a/flow.h
 +++ b/flow.h
 @@ -67,6 +67,7 @@ static inline bool flow_sidx_eq(flow_sidx_t a, flow_sidx_t b)
  union flow;
  
  void flow_table_compact(struct ctx *c, union flow *hole);
 +void flow_defer_handler(struct ctx *c);
  
  void flow_log_(const struct flow_common *f, int pri, const char *fmt, ...)
  	__attribute__((format(printf, 3, 4)));
 diff --git a/passt.c b/passt.c
 index 0246b04..5f72a28 100644
 --- a/passt.c
 +++ b/passt.c
 @@ -103,6 +103,7 @@ static void post_handler(struct ctx *c, const struct timespec *now)
  	/* NOLINTNEXTLINE(bugprone-branch-clone): intervals can be the same */
  	CALL_PROTO_HANDLER(c, now, icmp, ICMP);
  
 +	flow_defer_handler(c);
  #undef CALL_PROTO_HANDLER
  }
  
 diff --git a/tcp.c b/tcp.c
 index ad1a70d..9230d80 100644
 --- a/tcp.c
 +++ b/tcp.c
 @@ -1306,7 +1306,7 @@ static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c,
   * @c:		Execution context
   * @flow:	Flow table entry for this connection
   */
 -static void tcp_flow_defer(struct ctx *c, union flow *flow)
 +void tcp_flow_defer(struct ctx *c, union flow *flow)
  {
  	const struct tcp_tap_conn *conn = &flow->tcp;
  
 @@ -1364,26 +1364,11 @@ static void tcp_l2_data_buf_flush(const struct ctx *c)
   * tcp_defer_handler() - Handler for TCP deferred tasks
   * @c:		Execution context
   */
 +/* cppcheck-suppress constParameterPointer */   
 
 This needs to be:
 
   /* cppcheck-suppress [constParameterPointer, unmatchedSuppression] */
 
 otherwise we get warnings with cppcheck 2.10,   
 
 Drat, do we?  I was hoping this was a new warning type with the newer
 cppcheck, and it would ignore the suppression if it was for a warning
 type it didn't know about. 
Yeah... go figure. On the other hand it's not really a new type in the
sense that this _should_ have been covered by a "constParameter"
warning, before 2.11.

...
 
  and we'll
get warnings if
 cppcheck's behaviour ever changes again.   
 
 That's actually a good thing.  This one isn't a workaround for a
 cppcheck false positive or weird semantic that we hope will go away.
 Rhe warning is real and correct as far as it goes.  The problem is
 that the signature needs to match that of other deferred handlers
 because of how we generate the calls from a macro.  Some of those
 others need write access to the context. 
Oops, I didn't realise. Well, in any case, then we don't expect
cppcheck's behaviour to ever change in this regard, so I don't see any
advantage omitting unmatchedSuppression here.

-- 
Stefano

On Thu, Dec 28, 2023 at 07:25:18PM +0100, Stefano Brivio wrote:
...
  On Thu, 21 Dec 2023 17:15:46 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  In general, the passt code is a bit haphazard
about what's a true global
 variable and what's in the quasi-global 'context structure'.  The
 flow_count field is one such example: it's in the context structure,
 although it's really part of the same data structure as flowtab[], which
 is a genuine global. 
 
 Well, the reason is that flow_tab[FLOW_MAX] might be problematically
 too big to live on the stack, unlike flow_count.
 
 But anyway, as far as thoughts of multithreading are concerned, both
 should probably be global. And sure, it's more consistent this way.
 
  Move flow_count to be a regular global to match. 
For now it needs to be
 public, rather than static, but we expect to be able to change that in
 future. 
 
 If it's not static, it should be initialised, and that's not done here. 
Uh... what?  "static" here is meaning module-global rather than
global-global, which has no bearing on initialisation.  AFAIK globals
are zero-initialised whether they're static or not.

...
  This becomes 'flow_first_free' in 13/13, but
it's not initialised
 either, and that should also start off as zero.
  
-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Tue, Jan 02, 2024 at 07:13:35PM +0100, Stefano Brivio wrote:
...
  On Sun, 31 Dec 2023 16:58:39 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  On Thu, Dec 28, 2023 at 07:25:18PM +0100, Stefano
Brivio wrote:
  On Thu, 21 Dec 2023 17:15:46 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  In general, the passt code is a bit haphazard
about what's a true global
 variable and what's in the quasi-global 'context structure'.  The
 flow_count field is one such example: it's in the context structure,
 although it's really part of the same data structure as flowtab[], which
 is a genuine global.   
 
 Well, the reason is that flow_tab[FLOW_MAX] might be problematically
 too big to live on the stack, unlike flow_count.
 
 But anyway, as far as thoughts of multithreading are concerned, both
 should probably be global. And sure, it's more consistent this way.
   
  Move flow_count to be a regular global to match. 
For now it needs to be
 public, rather than static, but we expect to be able to change that in
 future.   
 
 If it's not static, it should be initialised, and that's not done here.  
 
 Uh... what?  "static" here is meaning module-global rather than
 global-global, which has no bearing on initialisation.  AFAIK globals
 are zero-initialised whether they're static or not. 
 
 ...and to my utter surprise, I just discovered that if you talk C11,
 you're right. From the N1570 draft (ISO/IEC 9899:201x), Section 6.7.9
 "Initialization", clause 10:
 
   If an object that has automatic storage duration is not initialized
   explicitly, its value is indeterminate. If an object that has static
   or thread storage duration is not initialized explicitly, then:
 
   [...]
 
   — if it has arithmetic type, it is initialized to (positive or
     unsigned) zero;
 
 And 'flow_count' has thread storage duration. 
No.. I don't think it does.  AFAICT only thread-local variables have
thread storage duration.  As a global flow_count will have static
storage duration, even without the static keyword.

...
  In C99, however (draft
 N1256), Section 6.7.8 "Initialization", clause 10:
 
   If an object that has automatic storage duration is not initialized
   explicitly, its value is indeterminate. If an object that has static
   storage duration is not initialized explicitly, then:
 
   [...]
 
 note the missing "or thread storage duration".
 
 C89, the one I was actually basing my observation on, says, at 3.5.7
 "Initialization":
 
   If an object that has static storage duration is not initialized
   explicitly, it is initialized implicitly as if every member that has
   arithmetic type were assigned 0 and every member that has pointer type
   were assigned a null pointer constant.  If an object that has
   automatic storage duration is not initialized explicitly, its value is
   indeterminate.
 
 so... um. We won't go back to C99. But to me, and maybe others, not
 having a "= 0;" for a "global" means pretty much that we don't
rely on
 any particular initial value. 
Again, I'm pretty sure that's not true, even for C99 and C89.  AIUI,
'static' locals and *all* globals have "static storage diration".

I'm not sure where to get the actual text of the standards but see for
example

https://en.cppreference.com/w/c/language/static_storage_duration

Here 'flow_count' has external linkage, thus satisfying the conditions
for static storage duration.

Fwiw, I'm pretty sure the kernel has relied on zero-initialization of
non-static globals for many years.

...
  If you're strongly against it, fine, C11 says
it's zero... but it makes
 me a bit nervous nevertheless.
  
-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Wed, Jan 03, 2024 at 08:08:34AM +0100, Stefano Brivio wrote:
...
  On Wed, 3 Jan 2024 14:54:27 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  I'm not sure where to get the actual text of
the standards 
 
 Let me answer this first: one (the?) trick is to use so-called final
 drafts, which are made freely available (same as working drafts) by the
 Working Group.
 
 Those are not the same as the standards, but differences from the final
 draft are also published... and they are usually not substantial.
 
 This is _very_ informative:
  
https://stackoverflow.com/questions/81656/where-do-i-find-the-current-c-or-…

Ah, thanks.

...
  Wikipedia also has the links, by the way. Anyway, in
practice:
 
 - C11: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
 - C99: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
 - C89:
  
https://web.archive.org/web/20200909074736if_/https://www.pdf-archive.com/2…
 
  On Tue, Jan 02, 2024 at 07:13:35PM +0100, Stefano
Brivio wrote:
  On Sun, 31 Dec 2023 16:58:39 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  On Thu, Dec 28, 2023 at 07:25:18PM +0100, Stefano
Brivio wrote:  
 > On Thu, 21 Dec 2023 17:15:46 +1100
 > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 >     
 > > In general, the passt code is a bit haphazard about what's a true global
 > > variable and what's in the quasi-global 'context structure'. 
The
 > > flow_count field is one such example: it's in the context structure,
 > > although it's really part of the same data structure as flowtab[], which
 > > is a genuine global.    
 > 
 > Well, the reason is that flow_tab[FLOW_MAX] might be problematically
 > too big to live on the stack, unlike flow_count.
 > 
 > But anyway, as far as thoughts of multithreading are concerned, both
 > should probably be global. And sure, it's more consistent this way.
 >     
 > > Move flow_count to be a regular global to match.  For now it needs to be
 > > public, rather than static, but we expect to be able to change that in
 > > future.    
 > 
 > If it's not static, it should be initialised, and that's not done here.   

 
 Uh... what?  "static" here is meaning module-global rather than
 global-global, which has no bearing on initialisation.  AFAIK globals
 are zero-initialised whether they're static or not.   
 
 ...and to my utter surprise, I just discovered that if you talk C11,
 you're right. From the N1570 draft (ISO/IEC 9899:201x), Section 6.7.9
 "Initialization", clause 10:
 
   If an object that has automatic storage duration is not initialized
   explicitly, its value is indeterminate. If an object that has static
   or thread storage duration is not initialized explicitly, then:
 
   [...]
 
   — if it has arithmetic type, it is initialized to (positive or
     unsigned) zero;
 
 And 'flow_count' has thread storage duration.   
 
 No.. I don't think it does.  AFAICT only thread-local variables have
 thread storage duration.  As a global flow_count will have static
 storage duration, even without the static keyword. 
 
 So, C11 defines static storage duration here:
 
   6.2.4 Storage durations of objects
 
   [...]
 
   3 An object whose identifier is declared without the storage-class
   specifier _Thread_local, and either with external or internal linkage
   or with the storage-class specifier static, has static storage
   duration. Its lifetime is the entire execution of the program and its
   stored value is initialized only once, prior to program startup.
 
 do we have any linkage here? I would have said no -- but, going back
 to C99 for this, "6.2.2 Linkages of identifiers":
 
   5 [...] If the declaration of an identifier for an object has file
   scope and no storage-class specifier, its linkage is external.
 
 which supports your paragraph below. 
Right.

...
  By the way, C11 now says:
 
   6.11.2 Linkages of identifiers
 
   1 Declaring an identifier with internal linkage at file scope without
   the static storage-class specifier is an obsolescent feature 
Ok.  I'm not even sure how you would do that.

...
 
 
  In C99, however (draft
 N1256), Section 6.7.8 "Initialization", clause 10:
 
   If an object that has automatic storage duration is not initialized
   explicitly, its value is indeterminate. If an object that has static
   storage duration is not initialized explicitly, then:
 
   [...]
 
 note the missing "or thread storage duration".
 
 C89, the one I was actually basing my observation on, says, at 3.5.7
 "Initialization":
 
   If an object that has static storage duration is not initialized
   explicitly, it is initialized implicitly as if every member that has
   arithmetic type were assigned 0 and every member that has pointer type
   were assigned a null pointer constant.  If an object that has
   automatic storage duration is not initialized explicitly, its value is
   indeterminate.
 
 so... um. We won't go back to C99. But to me, and maybe others, not
 having a "= 0;" for a "global" means pretty much that we don't
rely on
 any particular initial value.   
 
 Again, I'm pretty sure that's not true, even for C99 and C89.  AIUI,
 'static' locals and *all* globals have "static storage diration".
 
 I'm not sure where to get the actual text of the standards but see for
 example
 
 https://en.cppreference.com/w/c/language/static_storage_duration
 
 Here 'flow_count' has external linkage, thus satisfying the conditions
 for static storage duration. 
 
 Right. Well, for C99 and C11 at least. For C89 things are slightly
 different:
 
   6.1.2.4 Storage durations of objects
 
   [...]
 
   An object whose identifier is declared with external or internal
   linkage. or with the storage-class specifier static has static storage
   duration.
 
   [...]
 
   An object whose identifier is declared with no linkage and without the
   storage-class specifier static has automatic storage duration.
 
 You might say it has external linkage. But it was not *declared with*
 external linkage -- it just happens to have it (C89 and C99 don't
 differ here). 
Hrm.  We do have:
	extern unsigned flow_first_free;
in flow_table.h.  Does that cound as declaring with external linkage?

...
 
  Fwiw, I'm
pretty sure the kernel has relied on zero-initialization of
 non-static globals for many years. 
 
 True, and the opposite is even considered as a style issue since 2007,
 commit f0a594c1c74f ("update checkpatch.pl to version 0.08"). I also
 found a discussion similar to this one:
   https://lore.kernel.org/all/20201102184147.GA42288@localhost/#r
 
 Anyway... a couple of years before that, it must have been a gcc version
 in the late 2.x, I actually hit an issue with it. Was it a compiler
 issue, or the correct interpretation of C89? Or maybe something on the
 lines of:
   https://www.thegoodpenguin.co.uk/blog/u-boot-relocation-bss-hang/ 
If it was an embedded setup, that last one is certainly possible.
Zeroing the BSS is typically the loader's job, and I've certainly seen
loader implementations - particularly in embedded firmware - that got
this wrong.

...
  ? I'll never know/remember. And then, after
reading the standard, I
 started obsessively adding those = 0. Well, good to know I can stop
 doing it now. :)
  
-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Fri, Jan 05, 2024 at 08:55:13AM +0100, Stefano Brivio wrote:
...
  On Thu, 4 Jan 2024 20:51:19 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  On Wed, Jan 03, 2024 at 08:08:34AM +0100, Stefano
Brivio wrote:
  On Wed, 3 Jan 2024 14:54:27 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  I'm not sure where to get the actual text of
the standards   
 
 Let me answer this first: one (the?) trick is to use so-called final
 drafts, which are made freely available (same as working drafts) by the
 Working Group.
 
 Those are not the same as the standards, but differences from the final
 draft are also published... and they are usually not substantial.
 
 This is _very_ informative:
  
https://stackoverflow.com/questions/81656/where-do-i-find-the-current-c-or-…
  
 
 Ah, thanks.
 
  Wikipedia also has the links, by the way. Anyway,
in practice:
 
 - C11: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
 - C99: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
 - C89:
  
https://web.archive.org/web/20200909074736if_/https://www.pdf-archive.com/2…
   
  On Tue, Jan 02, 2024 at 07:13:35PM +0100, Stefano
Brivio wrote:  
 > On Sun, 31 Dec 2023 16:58:39 +1100
 > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 >     
 > > On Thu, Dec 28, 2023 at 07:25:18PM +0100, Stefano Brivio wrote:    
 > > > On Thu, 21 Dec 2023 17:15:46 +1100
 > > > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 > > >       
 > > > > In general, the passt code is a bit haphazard about what's a
true global
 > > > > variable and what's in the quasi-global 'context
structure'.  The
 > > > > flow_count field is one such example: it's in the context
structure,
 > > > > although it's really part of the same data structure as
flowtab[], which
 > > > > is a genuine global.      
 > > > 
 > > > Well, the reason is that flow_tab[FLOW_MAX] might be problematically
 > > > too big to live on the stack, unlike flow_count.
 > > > 
 > > > But anyway, as far as thoughts of multithreading are concerned, both
 > > > should probably be global. And sure, it's more consistent this way.
 > > >       
 > > > > Move flow_count to be a regular global to match.  For now it needs to
be
 > > > > public, rather than static, but we expect to be able to change that
in
 > > > > future.      
 > > > 
 > > > If it's not static, it should be initialised, and that's not
done here.      
 > > 
 > > Uh... what?  "static" here is meaning module-global rather than
 > > global-global, which has no bearing on initialisation.  AFAIK globals
 > > are zero-initialised whether they're static or not.    
 > 
 > ...and to my utter surprise, I just discovered that if you talk C11,
 > you're right. From the N1570 draft (ISO/IEC 9899:201x), Section 6.7.9
 > "Initialization", clause 10:
 > 
 >   If an object that has automatic storage duration is not initialized
 >   explicitly, its value is indeterminate. If an object that has static
 >   or thread storage duration is not initialized explicitly, then:
 > 
 >   [...]
 > 
 >   — if it has arithmetic type, it is initialized to (positive or
 >     unsigned) zero;
 > 
 > And 'flow_count' has thread storage duration.    
 
 No.. I don't think it does.  AFAICT only thread-local variables have
 thread storage duration.  As a global flow_count will have static
 storage duration, even without the static keyword.   
 
 So, C11 defines static storage duration here:
 
   6.2.4 Storage durations of objects
 
   [...]
 
   3 An object whose identifier is declared without the storage-class
   specifier _Thread_local, and either with external or internal linkage
   or with the storage-class specifier static, has static storage
   duration. Its lifetime is the entire execution of the program and its
   stored value is initialized only once, prior to program startup.
 
 do we have any linkage here? I would have said no -- but, going back
 to C99 for this, "6.2.2 Linkages of identifiers":
 
   5 [...] If the declaration of an identifier for an object has file
   scope and no storage-class specifier, its linkage is external.
 
 which supports your paragraph below.   
 
 Right.
 
  By the way, C11 now says:
 
   6.11.2 Linkages of identifiers
 
   1 Declaring an identifier with internal linkage at file scope without
   the static storage-class specifier is an obsolescent feature   
 
 Ok.  I'm not even sure how you would do that. 
 
 By doing what I *thought* you were doing (see below): "int x" at file
 scope (outside functions), no static, no extern declaration, nothing. 
Oh, ok.  Even without that, I think the behaviour has to be the same.
Plain "int x" at file scope is a public variable, and a linked module
could "extern" it, even if that extern isn't visible while we're
compiling this module.

...
 
 
 
  > In C99,
however (draft
 > N1256), Section 6.7.8 "Initialization", clause 10:
 > 
 >   If an object that has automatic storage duration is not initialized
 >   explicitly, its value is indeterminate. If an object that has static
 >   storage duration is not initialized explicitly, then:
 > 
 >   [...]
 > 
 > note the missing "or thread storage duration".
 > 
 > C89, the one I was actually basing my observation on, says, at 3.5.7
 > "Initialization":
 > 
 >   If an object that has static storage duration is not initialized
 >   explicitly, it is initialized implicitly as if every member that has
 >   arithmetic type were assigned 0 and every member that has pointer type
 >   were assigned a null pointer constant.  If an object that has
 >   automatic storage duration is not initialized explicitly, its value is
 >   indeterminate.
 > 
 > so... um. We won't go back to C99. But to me, and maybe others, not
 > having a "= 0;" for a "global" means pretty much that we
don't rely on
 > any particular initial value.    
 
 Again, I'm pretty sure that's not true, even for C99 and C89.  AIUI,
 'static' locals and *all* globals have "static storage diration".
 
 I'm not sure where to get the actual text of the standards but see for
 example
 
 https://en.cppreference.com/w/c/language/static_storage_duration
 
 Here 'flow_count' has external linkage, thus satisfying the conditions
 for static storage duration.   
 
 Right. Well, for C99 and C11 at least. For C89 things are slightly
 different:
 
   6.1.2.4 Storage durations of objects
 
   [...]
 
   An object whose identifier is declared with external or internal
   linkage. or with the storage-class specifier static has static storage
   duration.
 
   [...]
 
   An object whose identifier is declared with no linkage and without the
   storage-class specifier static has automatic storage duration.
 
 You might say it has external linkage. But it was not *declared with*
 external linkage -- it just happens to have it (C89 and C99 don't
 differ here).   
 
 Hrm.  We do have:
 	extern unsigned flow_first_free;
 in flow_table.h.  Does that cound as declaring with external linkage? 
 
 Gosh, sorry... yes, it also counts as me completely missing it.
 
 
 
  Fwiw, I'm pretty sure the kernel has relied on
zero-initialization of
 non-static globals for many years.   
 
 True, and the opposite is even considered as a style issue since 2007,
 commit f0a594c1c74f ("update checkpatch.pl to version 0.08"). I also
 found a discussion similar to this one:
   https://lore.kernel.org/all/20201102184147.GA42288@localhost/#r
 
 Anyway... a couple of years before that, it must have been a gcc version
 in the late 2.x, I actually hit an issue with it. Was it a compiler
 issue, or the correct interpretation of C89? Or maybe something on the
 lines of:
   https://www.thegoodpenguin.co.uk/blog/u-boot-relocation-bss-hang/   
 
 If it was an embedded setup, that last one is certainly possible.
 Zeroing the BSS is typically the loader's job, and I've certainly seen
 loader implementations - particularly in embedded firmware - that got
 this wrong. 
 
 Embedded setup, yes, but in a Linux kernel (early 2.4.x). No 'extern'
 there, though. 
Right.  Depending on platform, the kernel sometimes has a loader for a
later stage so does need to clear BSS.  Or it might need to as a
workaround for a broken firmware loader.  I'm pretty sure I've also
seem Linux bugs on some embedded platforms that involved failing to
clear the BSS.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Thu, 21 Dec 2023 17:15:49 +1100
David Gibson <david(a)gibson.dropbear.id.au> wrote:

...
  Currently we always keep the flow table maximally
compact: that is all the
 active entries are contiguous at the start of the table.  Doing this
 sometimes requires moving an entry when one is freed.  That's kind of
 fiddly, and potentially expensive: it requires updating the hash table for
 the new location, and depending on flow type, it may require EPOLL_CTL_MOD,
 system calls to update epoll tags with the new location too.
 
 Implement a new way of managing the flow table that doesn't ever move
 entries.  It attempts to maintain some compactness by always using the
 first free slot for a new connection, and mitigates the effect of non
 compactness by cheaply skipping over contiguous blocks of free entries.
 See the "theory of operation" comment in flow.c for details.
 
 Signed-off-by: David Gibson <david(a)gibson.dropbear.id.au>
 ---
  flow.c       | 177 +++++++++++++++++++++++++++++++++++++--------------
  flow.h       |   1 +
  flow_table.h |  16 ++++-
  passt.c      |   2 +
  tcp.c        |  23 -------
  tcp_conn.h   |   3 -
  tcp_splice.c |  11 ----
  7 files changed, 146 insertions(+), 87 deletions(-)
 
 diff --git a/flow.c b/flow.c
 index 7b99b58..421e6b5 100644
 --- a/flow.c
 +++ b/flow.c
 @@ -25,7 +25,7 @@ static_assert(ARRAY_SIZE(flow_type_str) == FLOW_NUM_TYPES,
  	      "flow_type_str[] doesn't match enum flow_type");
  
  /* Global Flow Table */
 -unsigned flow_count;
 +unsigned flow_first_free; 
As mentioned in the comment to 10/13: this should be initialised to
zero.

...
   union flow flowtab[FLOW_MAX];
  
  /* Last time the flow timers ran */
 @@ -49,6 +49,52 @@ void flow_log_(const struct flow_common *f, int pri, const char *fmt,
...)
  	logmsg(pri, "Flow %u (%s): %s", flow_idx(f), FLOW_TYPE(f), msg);
  }
  
 +/** 
As a general comment: interesting -- I wonder if this already has a name,
but I couldn't find anything similar in the literature. Perhaps it's
equivalent to a flattened search tree where free/busy slots can be
found by following the links.

...
  + * DOC: Theory of Operation - allocation and freeing
of flow entries 
"allocating and freeing flow entries" ...flows better for me.

I think this comment should be before the declaration of flowtab[] --
above here, with a function in between, is not exactly where I expected
to find it as I started reading the next paragraph.

...
  + *
 + * Each flow takes a single slot in flowtab[].  Moving entries in that table 
You jump right away to "moving entries", we know why, but I guess any
other reader would be lost at this point.

In general, it took me some effort to grasp this paragraph. What about:

 * Flows are entries in the flowtab[]. We need to routinely scan the whole table
 * to perform deferred bookkeeping tasks on active entries, and sparse empty
 * slots waste time and worsen data locality.
 *
 * But keeping the table compacted by moving entries on deletion is fiddly: it
 * requires updating hash tables, and the epoll references to the flows. Instead,
 * we implement the compromise described below.

?

...
  + * (which we used to do) is fiddly and possibly
expensive: it requires updating
 + * the hash table indexing flows, and may require updating epoll data which
 + * references the flow by index.  However, we also want to keep the active
 + * entries in the table compact where possible, because otherwise scanning
 + * through the entire table becomes more expensive.  This describes the
 + * compromise implemented below.
 + *
 + * Free blocks
 + *    A "free block" is a contiguous sequence of unused (FLOW_TYPE_NONE)
entries 
This gave me the idea that blocks are some kind of "bucket" with a fixed
size. I think we should either mention that the blocks have variable
size, or call them sequences, or clusters (of free slots) perhaps?

...
  + *    in flowtab.  The first entry in each block
contains metadata, specifically
 + *    the number of entries in the block, and the index of the next (non
 + *    contiguous) free block (struct flow_free_block). 
...it doesn't waste any space, but I don't think we actually need to
store the number of "entries" (slots?)... more details below.

...
  + *
 + * Free block list
 + *    flow_first_free gives the index of the first entry of the first (lowest
 + *    index) free block.  Each free block has the index of the next free block,
 + *    or MAX_FLOW if it is the last free block.  Together these form a linked
 + *    list of free blocks, in strictly increasing order of index.
 + *
 + * Allocation
 + *    When allocating a new flow, we always use the first entry of the first
 + *    free block, that is, at index flow_first_free.  If the block has more than
 + *    one entry, flow_first_free is updated to the next entry, which is updated
 + *    to represent the new smaller free block.  Otherwise the free block is
 + *    eliminated and flow_first_free is updated to the next free block.
 + *
 + * Scanning the table
 + *    Theoretically, scanning the table requires FLOW_MAX iterations.  However,
 + *    when we encounter the start of a free block, we can immediately skip to
 + *    its end, meaning that in practice we only need (number of active 
after its end

...
  + *    connections) + (number of free blocks)
iterations.
 + *
 + * Freeing
 + *    We can only free entries when scanning the whole flow table in
 + *    flow_defer_handler().  This is what lets us maintain the fee block list in 
s/fee/free/

...
  + *    index sorted order.  As we scan we keep track
of whether the previous
 + *    entry was in a free block or not.  If so when an entry is freed (its
 + *    deferred handler returns 'true'), we add it to that free block. 
Otherwise
 + *    we create a new free block for it and chain it to the last free block we
 + *    scanned.
 + */
 +
  /**
   * flow_alloc() - Allocate a new flow
   *
 @@ -56,10 +102,31 @@ void flow_log_(const struct flow_common *f, int pri, const char
*fmt, ...)
   */
  union flow *flow_alloc(void)
  {
 -	if (flow_count >= FLOW_MAX)
 +	union flow *flow = &flowtab[flow_first_free];
 +
 +	if (flow_first_free >= FLOW_MAX)
  		return NULL;
  
 -	return &flowtab[flow_count++];
 +	ASSERT(flow->f.type == FLOW_TYPE_NONE);
 +	ASSERT(flow->free.n >= 1);
 +
 +	if (flow->free.n > 1) {
 +		/* Use one entry from the block */
 +		union flow *next = &flowtab[++flow_first_free]; 
...but we just checked (flow_first_free < FLOW_MAX) above. Now you
increment flow_first_free by one.

I *guess* that if flow_first_free is FLOW_MAX - 1, then flow->free.n
should be 0, so we shouldn't end up in this case -- but it's a bit
confusing.

...
  +
 +		ASSERT(FLOW_IDX(next) < FLOW_MAX);
 +		ASSERT(next->f.type == FLOW_TYPE_NONE);
 +		ASSERT(next->free.n == 0);
 +
 +		next->free.n = flow->free.n - 1;
 +		next->free.next = flow->free.next;
 +	} else {
 +		/* Use the entire block */
 +		flow_first_free = flow->free.next;
 +	} 
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:

  struct flow_free_block {
  	[...]
  	unsigned next_free;
  	unsigned next_busy;
  };

or:

  struct flow_free_block {
  	[...]
  	unsigned next_free;
  };

or even some sort of double-linked list:

  struct flow_free_block {
  	[...]
  	unsigned prev_free;
  	unsigned next_free;
  };

but I couldn't quite find a more elegant solution yet.

...
  +
 +	memset(flow, 0, sizeof(*flow));
 +	return flow;
  }
  
  /**
 @@ -70,48 +137,15 @@ union flow *flow_alloc(void)
   */
  void flow_alloc_cancel(union flow *flow)
  {
 -	ASSERT(FLOW_IDX(flow) == flow_count - 1);
 -	memset(flow, 0, sizeof(*flow));
 -	flow_count--;
 -}
 -
 -/**
 - * flow_table_compact() - Perform compaction on flow table
 - * @c:		Execution context
 - * @hole:	Pointer to recently closed flow
 - */
 -static void flow_table_compact(const struct ctx *c, union flow *hole)
 -{
 -	union flow *from;
 -
 -	if (FLOW_IDX(hole) == --flow_count) {
 -		debug("flow: table compaction: maximum index was %u (%p)",
 -		      FLOW_IDX(hole), (void *)hole);
 -		memset(hole, 0, sizeof(*hole));
 -		return;
 -	}
 -
 -	from = flowtab + flow_count;
 -	memcpy(hole, from, sizeof(*hole));
 -
 -	switch (from->f.type) {
 -	case FLOW_TCP:
 -		tcp_tap_conn_update(c, &from->tcp, &hole->tcp);
 -		break;
 -	case FLOW_TCP_SPLICE:
 -		tcp_splice_conn_update(c, &hole->tcp_splice);
 -		break;
 -	default:
 -		die("Unexpected %s in tcp_table_compact()",
 -		    FLOW_TYPE(&from->f));
 -	}
 -
 -	debug("flow: table compaction (%s): old index %u, new index %u, "
 -	      "from: %p, to: %p",
 -	      FLOW_TYPE(&from->f), FLOW_IDX(from), FLOW_IDX(hole),
 -	      (void *)from, (void *)hole);
 -
 -	memset(from, 0, sizeof(*from));
 +	ASSERT(flow_first_free > FLOW_IDX(flow));
 +
 +	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);
  }
  
  /**
 @@ -121,18 +155,35 @@ static void flow_table_compact(const struct ctx *c, union flow
*hole)
   */
  void flow_defer_handler(const struct ctx *c, const struct timespec *now)
  {
 +	struct flow_free_block *free_head = NULL;
 +	unsigned *last_next = &flow_first_free;
  	bool timer = false;
 -	union flow *flow;
 +	unsigned idx;
  
  	if (timespec_diff_ms(now, &flow_timer_run) >= FLOW_TIMER_INTERVAL) {
  		timer = true;
  		flow_timer_run = *now;
  	}
  
 -	for (flow = flowtab + flow_count - 1; flow >= flowtab; flow--) {
 +	for (idx = 0; idx < FLOW_MAX; idx++) {
 +		union flow *flow = &flowtab[idx];
  		bool closed = false;
  
 +		if (flow->f.type == FLOW_TYPE_NONE) {
 +			/* Start of a free block */
 +			free_head = &flow->free;
 +			*last_next = idx;
 +			last_next = &free_head->next;
 +			/* Skip the rest of the block */
 +			idx += free_head->n - 1;
 +			continue;
 +		}
 +
 +		 
Stray tabs.

...
   		switch (flow->f.type) {
 +		case FLOW_TYPE_NONE:
 +			closed = true;
 +			break;
  		case FLOW_TCP:
  			closed = tcp_flow_defer(flow);
  			break;
 @@ -146,7 +197,35 @@ void flow_defer_handler(const struct ctx *c, const struct timespec
*now)
  			;
  		}
  
 -		if (closed)
 -			flow_table_compact(c, flow);
 +		if (closed) { 
Should this be a flow_del() function perhaps, possibly taking flow and
free_head as argument?

...
  +			flow->f.type = FLOW_TYPE_NONE;
 +
 +			if (free_head) {
 +				/* Add slot to current free block */
 +				ASSERT(idx == FLOW_IDX(free_head) + free_head->n);
 +				free_head->n++;
 +				flow->free.n = flow->free.next = 0;
 +			} else {
 +				/* Create new free block */
 +				free_head = &flow->free;
 +				free_head->n = 1;
 +				*last_next = idx;
 +				last_next = &free_head->next;
 +			}
 +		} else {
 +			free_head = NULL;
 +		}
  	}
 +
 +	*last_next = FLOW_MAX;
 +}
 +
 +/**
 + * flow_init() - Initialise flow related data structures
 + */
 +void flow_init(void)
 +{
 +	/* Initial state is a single free block containing the whole table */
 +	flowtab[0].free.n = FLOW_MAX;
 +	flowtab[0].free.next = FLOW_MAX;
  }
 diff --git a/flow.h b/flow.h
 index 8064f0e..48a0ab4 100644
 --- a/flow.h
 +++ b/flow.h
 @@ -68,6 +68,7 @@ static inline bool flow_sidx_eq(flow_sidx_t a, flow_sidx_t b)
  
  union flow;
  
 +void flow_init(void);
  void flow_defer_handler(const struct ctx *c, const struct timespec *now);
  
  void flow_log_(const struct flow_common *f, int pri, const char *fmt, ...)
 diff --git a/flow_table.h b/flow_table.h
 index 2773a2b..34fc679 100644
 --- a/flow_table.h
 +++ b/flow_table.h
 @@ -9,6 +9,19 @@
  
  #include "tcp_conn.h"
  
 +/**
 + * struct flow_free_block - Information about a block of free entries
 + * @f:		Generic flow information
 + * @n:		Number of entries in this free block (including this one)
 + * @next:	Index of next free block
 + */
 +struct flow_free_block {
 +	/* Must be first element */
 +	struct flow_common f;
 +	unsigned n;
 +	unsigned next;
 +};
 +
  /**
   * union flow - Descriptor for a logical packet flow (e.g. connection)
   * @f:		Fields common between all variants
 @@ -17,12 +30,13 @@
  */
  union flow {
  	struct flow_common f;
 +	struct flow_free_block free;
  	struct tcp_tap_conn tcp;
  	struct tcp_splice_conn tcp_splice;
  };
  
  /* Global Flow Table */
 -extern unsigned flow_count;
 +extern unsigned flow_first_free;
  extern union flow flowtab[];
  
  
 diff --git a/passt.c b/passt.c
 index 71bea8f..d315438 100644
 --- a/passt.c
 +++ b/passt.c
 @@ -285,6 +285,8 @@ int main(int argc, char **argv)
  
  	clock_gettime(CLOCK_MONOTONIC, &now);
  
 +	flow_init();
 +
  	if ((!c.no_udp && udp_init(&c)) || (!c.no_tcp &&
tcp_init(&c)))
  		exit(EXIT_FAILURE);
  
 diff --git a/tcp.c b/tcp.c
 index a38deb0..6aacb56 100644
 --- a/tcp.c
 +++ b/tcp.c
 @@ -1250,29 +1250,6 @@ static void tcp_hash_remove(const struct ctx *c,
  	tc_hash[b] = FLOW_SIDX_NONE;
  }
  
 -/**
 - * tcp_tap_conn_update() - Update tcp_tap_conn when being moved in the table
 - * @c:		Execution context
 - * @old:	Old location of tcp_tap_conn
 - * @new:	New location of tcp_tap_conn
 - */
 -void tcp_tap_conn_update(const struct ctx *c, struct tcp_tap_conn *old,
 -			 struct tcp_tap_conn *new)
 -
 -{
 -	unsigned b = tcp_hash_probe(c, old);
 -
 -	if (!flow_at_sidx(tc_hash[b]))
 -		return; /* Not in hash table, nothing to update */
 -
 -	tc_hash[b] = FLOW_SIDX(new, TAPSIDE);
 -
 -	debug("TCP: hash table update: old index %u, new index %u, sock %i, "
 -	      "bucket: %u", FLOW_IDX(old), FLOW_IDX(new), new->sock, b);
 -
 -	tcp_epoll_ctl(c, new);
 -}
 -
  /**
   * tcp_hash_lookup() - Look up connection given remote address and ports
   * @c:		Execution context
 diff --git a/tcp_conn.h b/tcp_conn.h
 index 636224e..a5f5cfe 100644
 --- a/tcp_conn.h
 +++ b/tcp_conn.h
 @@ -155,9 +155,6 @@ struct tcp_splice_conn {
  extern int init_sock_pool4	[TCP_SOCK_POOL_SIZE];
  extern int init_sock_pool6	[TCP_SOCK_POOL_SIZE];
  
 -void tcp_tap_conn_update(const struct ctx *c, struct tcp_tap_conn *old,
 -			 struct tcp_tap_conn *new);
 -void tcp_splice_conn_update(const struct ctx *c, struct tcp_splice_conn *new);
  bool tcp_flow_defer(union flow *flow);
  bool tcp_splice_flow_defer(union flow *flow);
  void tcp_splice_timer(const struct ctx *c, union flow *flow);
 diff --git a/tcp_splice.c b/tcp_splice.c
 index 0711b19..7aae623 100644
 --- a/tcp_splice.c
 +++ b/tcp_splice.c
 @@ -231,17 +231,6 @@ static void conn_event_do(const struct ctx *c, struct
tcp_splice_conn *conn,
  	} while (0)
  
  
 -/**
 - * tcp_splice_conn_update() - Update tcp_splice_conn when being moved in the table
 - * @c:		Execution context
 - * @new:	New location of tcp_splice_conn
 - */
 -void tcp_splice_conn_update(const struct ctx *c, struct tcp_splice_conn *new)
 -{
 -	if (tcp_splice_epoll_ctl(c, new))
 -		conn_flag(c, new, CLOSING);
 -}
 -
  /**
   * tcp_splice_flow_defer() - Deferred per-flow handling (clean up closed)
   * @flow:	Flow table entry for this connection 
-- 
Stefano

On Sat, Dec 30, 2023 at 11:33:04AM +0100, Stefano Brivio wrote:
...
  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. 
Remember this is not a general deletion, only a "cancel" of the most
recent allocation.  To reduce fragmentation we are keeping the linked
list of free clusters in strictly ascending order.  The logic above is
only correct if the entry we're freeing is before any other free entry
in the table.  That will be the case for the most recent allocation,
because we always allocatte the first free entry in the table.

...
  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; 
fg
...
  
 	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). 
Exactly.  I can't see any way (short of far more complex data
structures) around having a linear scan somewhere, although you can
kind of choose whether it happens on alloc or free.

The idea of my implementation is to have it at free time - but to
merge it with an existing linear scan so it won't have an additional
cost.

...
  		 *
 		 * 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;
 }
  
-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Tue, Jan 02, 2024 at 07:13:41PM +0100, Stefano Brivio wrote:
...
  On Mon, 1 Jan 2024 23:01:17 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  On Sat, Dec 30, 2023 at 11:33:04AM +0100, Stefano
Brivio wrote:
  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.   
 
 Remember this is not a general deletion, only a "cancel" of the most
 recent allocation. 
 
 Oh, I thought that was only the case for this series and you would use
 that as actual deletion in another pending series (which I haven't
 finished reviewing yet). 
No.  Not allowing deletion of any entry at any time is what I'm
trading off to get both O(1) allocation and (effectively) O(1)
deletion.

...
  But now I'm not sure anymore why I was thinking
this...
 
 Anyway... do we really need it, then? Can't we just mark the "failed"
 flows as whatever means "closed" for a specific protocol, and clean
 them up later, instead of calling cancel() right away? 
We could, but I'm not sure we want to.  For starters, that requires
protocol-specific behaviour whenever we need to back out an allocation
like this.  Not a big deal, since that's in protocol specific code
already, but I think it's uglier than calling cancel.

It also requires that the protocol specific deferred cleanup functions
(e.g. tcp_flow_defer()) handle partially initialised entries.  With
'cancel' we can back out just the initialisation steps we've already
done (because we know where we've failed during init), then remove the
entry.  The deferred cleanup function only needs to deal with
"complete" entries.  Again, certainly possible, but IMO uglier than
having 'cancel'.

Finally, leaving the "cancelled" entry there until the next deferred
pass means if we allocate other flows before that defer pass they'll
avoid this slot.  That works against trying to keep the entries
reasonably compact.

...
 
   To reduce
fragmentation we are keeping the linked
 list of free clusters in strictly ascending order.  The logic above is
 only correct if the entry we're freeing is before any other free entry
 in the table.  That will be the case for the most recent allocation,
 because we always allocatte the first free entry in the table. 
 
 I see now. This isn't entirely clear from the "Theory of Operation",
 on the other hand it's probably a bad idea to overload that description
 with all these details. 
I'll see what I can in terms of making that clearer in the description.

...
 
 
  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;   
 fg
  
 	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).   
 
 Exactly.  I can't see any way (short of far more complex data
 structures) around having a linear scan somewhere, although you can
 kind of choose whether it happens on alloc or free.
 
 The idea of my implementation is to have it at free time - but to
 merge it with an existing linear scan so it won't have an additional
 cost. 
 
 Right, yes, I see now. This idea is also not terribly clear from the
 description, by the way, but I don't have a good proposal right now. 
I'll see what I can come up with.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Fri, Jan 05, 2024 at 09:33:35AM +0100, Stefano Brivio wrote:
...
  On Thu, 4 Jan 2024 21:02:19 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  On Tue, Jan 02, 2024 at 07:13:41PM +0100, Stefano
Brivio wrote:
  On Mon, 1 Jan 2024 23:01:17 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  On Sat, Dec 30, 2023 at 11:33:04AM +0100, Stefano
Brivio wrote:  
 > 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.    
 
 Remember this is not a general deletion, only a "cancel" of the most
 recent allocation.   
 
 Oh, I thought that was only the case for this series and you would use
 that as actual deletion in another pending series (which I haven't
 finished reviewing yet).   
 
 No.  Not allowing deletion of any entry at any time is what I'm
 trading off to get both O(1) allocation and (effectively) O(1)
 deletion.
 
  But now I'm not sure anymore why I was
thinking this...
 
 Anyway... do we really need it, then? Can't we just mark the "failed"
 flows as whatever means "closed" for a specific protocol, and clean
 them up later, instead of calling cancel() right away?   
 
 We could, but I'm not sure we want to.  For starters, that requires
 protocol-specific behaviour whenever we need to back out an allocation
 like this.  Not a big deal, since that's in protocol specific code
 already, but I think it's uglier than calling cancel.
 
 It also requires that the protocol specific deferred cleanup functions
 (e.g. tcp_flow_defer()) handle partially initialised entries.  With
 'cancel' we can back out just the initialisation steps we've already
 done (because we know where we've failed during init), then remove the
 entry.  The deferred cleanup function only needs to deal with
 "complete" entries.  Again, certainly possible, but IMO uglier than
 having 'cancel'. 
 
 Okay, yes, I see now.
 
 Another doubt that comes to me now is: if you don't plan to use this
 alloc_cancel() thing anywhere else, the only reason why you are adding
 it is to replace the (flow_count >= FLOW_MAX) check with a flow_alloc()
 version that can fail.
 
 But at this point, speaking of ugliness, couldn't we just have a
 bool flow_may_alloc() { return flow_first_free < FLOW_MAX }; the caller
 can use to decide to abort earlier? To me it looks so much simpler and
 more robust. 
Well, we could, but there are a couple of reasons I don't love it.
The first is abstraction: this returns explicit handling of the layout
of the table to the protocol specific callers.  It's not a huge deal
right now, but once we have 4 or 5 protocols doing this, having to
change all of them if we make any tiny change to the semantics of
flow_first_free isn't great.

The other issue is that to do this (without a bunch of fairly large
and ugly temporaries) means we'd populate at least some of the fields
in flow_common before we have officially "allocated" the entry.  At
that point it becomes a bit fuzzy as to when that allocation really
occurs.  Is it when we do the FLOW_MAX tesT?  Is it when we write to
f.type?  Is it when we update flow_first_free?  If we fail somewhere
in the middle of that, what steps do we need to reverse?

For those reasons I prefer the scheme presented.  Fwiw, in an earlier
draft I did this differently with a "flow_prealloc()", which was
essentially the check against FLOW_MAX, then a later
flow_alloc_commit().  I thought it turned out pretty confusing
compared to the alloc/cancel approach.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Fri, Jan 05, 2024 at 11:27:54AM +0100, Stefano Brivio wrote:
...
  On Fri, 5 Jan 2024 20:39:50 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  On Fri, Jan 05, 2024 at 09:33:35AM +0100, Stefano
Brivio wrote:
  On Thu, 4 Jan 2024 21:02:19 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  On Tue, Jan 02, 2024 at 07:13:41PM +0100, Stefano
Brivio wrote:  
 > On Mon, 1 Jan 2024 23:01:17 +1100
 > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 >     
 > > On Sat, Dec 30, 2023 at 11:33:04AM +0100, Stefano Brivio wrote:    
 > > > 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.      
 > > 
 > > Remember this is not a general deletion, only a "cancel" of the most
 > > recent allocation.    
 > 
 > Oh, I thought that was only the case for this series and you would use
 > that as actual deletion in another pending series (which I haven't
 > finished reviewing yet).    
 
 No.  Not allowing deletion of any entry at any time is what I'm
 trading off to get both O(1) allocation and (effectively) O(1)
 deletion.
   
 > But now I'm not sure anymore why I was thinking this...
 > 
 > Anyway... do we really need it, then? Can't we just mark the
"failed"
 > flows as whatever means "closed" for a specific protocol, and clean
 > them up later, instead of calling cancel() right away?    
 
 We could, but I'm not sure we want to.  For starters, that requires
 protocol-specific behaviour whenever we need to back out an allocation
 like this.  Not a big deal, since that's in protocol specific code
 already, but I think it's uglier than calling cancel.
 
 It also requires that the protocol specific deferred cleanup functions
 (e.g. tcp_flow_defer()) handle partially initialised entries.  With
 'cancel' we can back out just the initialisation steps we've already
 done (because we know where we've failed during init), then remove the
 entry.  The deferred cleanup function only needs to deal with
 "complete" entries.  Again, certainly possible, but IMO uglier than
 having 'cancel'.   
 
 Okay, yes, I see now.
 
 Another doubt that comes to me now is: if you don't plan to use this
 alloc_cancel() thing anywhere else, the only reason why you are adding
 it is to replace the (flow_count >= FLOW_MAX) check with a flow_alloc()
 version that can fail.
 
 But at this point, speaking of ugliness, couldn't we just have a
 bool flow_may_alloc() { return flow_first_free < FLOW_MAX }; the caller
 can use to decide to abort earlier? To me it looks so much simpler and
 more robust.   
 
 Well, we could, but there are a couple of reasons I don't love it.
 The first is abstraction: this returns explicit handling of the layout
 of the table to the protocol specific callers.  It's not a huge deal
 right now, but once we have 4 or 5 protocols doing this, having to
 change all of them if we make any tiny change to the semantics of
 flow_first_free isn't great. 
 
 Hmm, I don't get the difference in terms of abstraction between
 checking the return value of flow_alloc() and checking the return value
 of flow_may_alloc(). 
Oh, sorry, I thought you were proposing open-coding the check against
FLOW_MAX, like it is at the moment.  See below for comments on a
flow_may_alloc() or similar call.

...
  In both cases the protocol handlers know that
there's a table, a
 function to reserve entries, and that reserving entries might fail...
 and not much else.
 
  The other issue is that to do this (without a
bunch of fairly large
 and ugly temporaries) means we'd populate at least some of the fields
 in flow_common before we have officially "allocated" the entry.  At
 that point it becomes a bit fuzzy as to when that allocation really
 occurs.  Is it when we do the FLOW_MAX tesT? 
 
 I would say yes -- after that we can't fail. 
Uh.. we can't fail to allocate.  We can fail for other reasons.

...
  I mean, we work with rather constrained structures for
a number of
 reasons, which comes with a number of hard problems... let's at least
 reap the benefits of it? 
I'm not sure what you're getting at here.

...
 
  Is it when we
write to
 f.type?  Is it when we update flow_first_free?  If we fail somewhere
 in the middle of that, what steps do we need to reverse? 
 
 We can't fail in the middle of it, at the moment. 
Yes we can, that's kind of the whole point of this.

...
  Of course, if the
 "allocation" function changes, we might need to change the scheme. But
 is it really likely? And anyway it's just a few lines in your current
 version...
 
  For those reasons I prefer the scheme presented. 
Fwiw, in an earlier
 draft I did this differently with a "flow_prealloc()", which was
 essentially the check against FLOW_MAX, then a later
 flow_alloc_commit().  I thought it turned out pretty confusing
 compared to the alloc/cancel approach. 
 
 The current flow_alloc_cancel() implementation is definitely simple and
 semantically clear.
 
 What worries me a bit is that you would have two different cases for
 free "blocks" of size one, depending on the order of the events. So if
 we want to debug something like that and we see a block with size one
 it might be a failed bind(), so a fake one, or also not: it might be an
 actual block with size one. 
The cluster of size one from cancel is still a valid free cluster that
satisfies all the usual invaraints, it's not "fake".  It does mean
that we could get two contiguous free clusters, which we wouldn't
otherwise.  The idea is that they'll be merged back together on the
next deferred scan, but as noted on a different subthread, that's not
currently working and I'll have to fix it.

...
  Thinking of multithreading: defining flow_may_alloc()
becomes more
 complicated because the caller can't just assume the "allocation" will
 succeed (as long as we don't cross an "epoll cycle" or something like
 that). But we'll probably need some form of locking or userspace RCU
 giving us barriers around the pair may_alloc() / alloc(). 
For multi-threaded, I really thin we'd want alloc/free semantics, not
may_alloc/alloc semantics.  We have to change state in some way at
"may alloc" time, or something else could try to allocate the same
slot.  "cancel" semantics also don't make sense here, because we can
no longer be confident that the alloc we did above is still the most
recent allloc.  So a bunch of things would need to change for
multi-threading.

...
  If we stick to the failing alloc(), this part is
simpler, but the
 interpretation of flow_first_free and block sizes becomes non-trivial. 
Again, not sure what you're getting at.

...
  Well, on the other hand, it's all simple enough
that we can change it
 as needed (for example for multithreading). If we can hope that the new
 scheme is reasonably low on bugs and we'll probably never have to guess
 why a block has size one, I'm fine with the failing alloc() as well.
  
-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Sat, Jan 06, 2024 at 02:02:01PM +0100, Stefano Brivio wrote:
...
  On Sat, 6 Jan 2024 22:32:10 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
 
  On Fri, Jan 05, 2024 at 11:27:54AM +0100, Stefano
Brivio wrote:
  On Fri, 5 Jan 2024 20:39:50 +1100
 David Gibson <david(a)gibson.dropbear.id.au> wrote:
   
  On Fri, Jan 05, 2024 at 09:33:35AM +0100, Stefano
Brivio wrote:  
 > On Thu, 4 Jan 2024 21:02:19 +1100
 > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 >     
 > > On Tue, Jan 02, 2024 at 07:13:41PM +0100, Stefano Brivio wrote:    
 > > > On Mon, 1 Jan 2024 23:01:17 +1100
 > > > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 > > >       
 > > > > On Sat, Dec 30, 2023 at 11:33:04AM +0100, Stefano Brivio wrote:     

 > > > > > 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.        
 > > > > 
 > > > > Remember this is not a general deletion, only a "cancel" of
the most
 > > > > recent allocation.      
 > > > 
 > > > Oh, I thought that was only the case for this series and you would use
 > > > that as actual deletion in another pending series (which I haven't
 > > > finished reviewing yet).      
 > > 
 > > No.  Not allowing deletion of any entry at any time is what I'm
 > > trading off to get both O(1) allocation and (effectively) O(1)
 > > deletion.
 > >     
 > > > But now I'm not sure anymore why I was thinking this...
 > > > 
 > > > Anyway... do we really need it, then? Can't we just mark the
"failed"
 > > > flows as whatever means "closed" for a specific protocol, and
clean
 > > > them up later, instead of calling cancel() right away?      
 > > 
 > > We could, but I'm not sure we want to.  For starters, that requires
 > > protocol-specific behaviour whenever we need to back out an allocation
 > > like this.  Not a big deal, since that's in protocol specific code
 > > already, but I think it's uglier than calling cancel.
 > > 
 > > It also requires that the protocol specific deferred cleanup functions
 > > (e.g. tcp_flow_defer()) handle partially initialised entries.  With
 > > 'cancel' we can back out just the initialisation steps we've
already
 > > done (because we know where we've failed during init), then remove the
 > > entry.  The deferred cleanup function only needs to deal with
 > > "complete" entries.  Again, certainly possible, but IMO uglier than
 > > having 'cancel'.    
 > 
 > Okay, yes, I see now.
 > 
 > Another doubt that comes to me now is: if you don't plan to use this
 > alloc_cancel() thing anywhere else, the only reason why you are adding
 > it is to replace the (flow_count >= FLOW_MAX) check with a flow_alloc()
 > version that can fail.
 > 
 > But at this point, speaking of ugliness, couldn't we just have a
 > bool flow_may_alloc() { return flow_first_free < FLOW_MAX }; the caller
 > can use to decide to abort earlier? To me it looks so much simpler and
 > more robust.    
 
 Well, we could, but there are a couple of reasons I don't love it.
 The first is abstraction: this returns explicit handling of the layout
 of the table to the protocol specific callers.  It's not a huge deal
 right now, but once we have 4 or 5 protocols doing this, having to
 change all of them if we make any tiny change to the semantics of
 flow_first_free isn't great.   
 
 Hmm, I don't get the difference in terms of abstraction between
 checking the return value of flow_alloc() and checking the return value
 of flow_may_alloc().   
 
 Oh, sorry, I thought you were proposing open-coding the check against
 FLOW_MAX, like it is at the moment.  See below for comments on a
 flow_may_alloc() or similar call.
 
  In both cases the protocol handlers know that
there's a table, a
 function to reserve entries, and that reserving entries might fail...
 and not much else.
   
  The other issue is that to do this (without a
bunch of fairly large
 and ugly temporaries) means we'd populate at least some of the fields
 in flow_common before we have officially "allocated" the entry.  At
 that point it becomes a bit fuzzy as to when that allocation really
 occurs.  Is it when we do the FLOW_MAX tesT?   
 
 I would say yes -- after that we can't fail.   
 
 Uh.. we can't fail to allocate.  We can fail for other reasons. 
 
 Yes, I meant, if we pass the FLOW_MAX check, then we can't fail to
 allocate -- therefore flow_may_alloc() would contain just that check. 
Right, ok.

...
 
 
  I mean, we work with rather constrained structures for
a number of
 reasons, which comes with a number of hard problems... let's at least
 reap the benefits of it?   
 
 I'm not sure what you're getting at here. 
 
 ...I'm saying that we don't actually allocate memory, which means that
 we can have a simple test (on FLOW_MAX), and then we know that, at
 least within the handling of a single epoll event, we will be able to
 allocate memory, without possible races.
 
 We couldn't do that with an actual heap allocation because that's out
 of our control.
 
 This is one of the few aspects where using statically allocated memory
 only could make our lives easier (while in general we need to spend
 more effort for other things). 
Ok, I understand.

...
 
 
 
  Is it when we
write to
 f.type?  Is it when we update flow_first_free?  If we fail somewhere
 in the middle of that, what steps do we need to reverse?   
 
 We can't fail in the middle of it, at the moment.   
 
 Yes we can, that's kind of the whole point of this. 
 
 But as of this patch flow_alloc() can only fail on the FLOW_MAX check... 
I'm not talking about allocation failure, I'm talking about the other
failures in setting up a new flow.  We can fail between checking
FLOW_MAX and "committing" to the allocation by updating
flow_first_free (or whatever).

Before the point we finally commit, we do want to write some fields of
the flow.  That's the obvious place to put the address from accept()
for example.  But there are some things we mustn't touch, because it
will mess up how the slot is interpreted as a free slot (type, and
anything in the protocol specific fields, because that will overlap
struct flow_free_cluster.

I don't like having this fragile intermediate state with subtle rules
about what we can and can't safely do to the flow entry.  With alloc
cancel, we can do whatever we like as soon as we've alloc()ed, and on
failure the cancel() will restore whatever free cluster information
needs to be there.

...
 
 
  Of course, if the
 "allocation" function changes, we might need to change the scheme. But
 is it really likely? And anyway it's just a few lines in your current
 version...
   
  For those reasons I prefer the scheme presented. 
Fwiw, in an earlier
 draft I did this differently with a "flow_prealloc()", which was
 essentially the check against FLOW_MAX, then a later
 flow_alloc_commit().  I thought it turned out pretty confusing
 compared to the alloc/cancel approach.   
 
 The current flow_alloc_cancel() implementation is definitely simple and
 semantically clear.
 
 What worries me a bit is that you would have two different cases for
 free "blocks" of size one, depending on the order of the events. So if
 we want to debug something like that and we see a block with size one
 it might be a failed bind(), so a fake one, or also not: it might be an
 actual block with size one.   
 
 The cluster of size one from cancel is still a valid free cluster that
 satisfies all the usual invaraints, it's not "fake".  It does mean
 that we could get two contiguous free clusters, which we wouldn't
 otherwise. 
 
 Okay, yes, not having contiguous free clusters is probably not a
 valuable invariant anyway. 
Right, that was my feeling.

...
 
  The idea is
that they'll be merged back together on the
 next deferred scan, but as noted on a different subthread, that's not
 currently working and I'll have to fix it. 
 
 Yes yes that part is clear to me. I don't find it very problematic, or
 in any way "wrong".
 
 
  Thinking
of multithreading: defining flow_may_alloc() becomes more
 complicated because the caller can't just assume the "allocation" will
 succeed (as long as we don't cross an "epoll cycle" or something like
 that). But we'll probably need some form of locking or userspace RCU
 giving us barriers around the pair may_alloc() / alloc().   
 
 For multi-threaded, I really thin we'd want alloc/free semantics, not
 may_alloc/alloc semantics.  We have to change state in some way at
 "may alloc" time, or something else could try to allocate the same
 slot.  "cancel" semantics also don't make sense here, because we can
 no longer be confident that the alloc we did above is still the most
 recent allloc.  So a bunch of things would need to change for
 multi-threading. 
 
 By the way, another possibility would be to just go ahead and call
 socket() and bind(), or accept() the connection from the socket, then if
 we fail to "allocate" a flow we'll close the socket. That doesn't
solve
 the synchronisation problem entirely but it makes it simpler to handle. 
We could.  But (a) the may-alloc check is much cheaper than the
syscalls and (b) that means we need to store all information from
those syscalls temporarily before copying it into the flow table,
which is kind of nasty.

...
  Now, a bound socket or an accepted connection is
visible to the user
 which is (I guess) the reason why you want to avoid this, but if we
 can't open/accept new connections it's getting pretty bad anyway... so
 should we really care? 
Right, that's certainly not my concern about it.

...
  Actually, calling accept() and then close() on a
socket (peer gets RST)
 is probably a nicer behaviour than letting a peer hang because we ran
 out of slots. 
Maybe, maybe not.  If we are persistently overloaded, then yes.
However if we just have a sudden spike of short lived connections,
then we could just "bounce" against the flow limit, but we'll still
process those other connection attempts in a little bit.

...
 
 
  If we stick to the failing alloc(), this part is
simpler, but the
 interpretation of flow_first_free and block sizes becomes non-trivial.   
 
 Again, not sure what you're getting at. 
 
 By "failing alloc()" I mean the alloc/cancel semantics, as opposed to
 an allocation function that can't fail. 
That bit I got.

...
  There, as you mentioned, we can no longer be confident
that the
 canceled allocation would be the most recent one (which changes the
 meaning of flow_first_free). 
If we're multithreading, then I think this allocation scheme needs
some revision anyway.

...
  > > Well, on the other hand, it's all
simple enough that we can change it
 > > as needed (for example for multithreading). If we can hope that the new
 > > scheme is reasonably low on bugs and we'll probably never have to guess
 > > why a block has size one, I'm fine with the failing alloc() as well.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

On Mon, 1 Jan 2024 21:44:54 +1100
David Gibson <david(a)gibson.dropbear.id.au> wrote:

...
  On Thu, Dec 28, 2023 at 07:25:25PM +0100, Stefano
Brivio wrote:
 > On Thu, 21 Dec 2023 17:15:49 +1100
 > David Gibson <david(a)gibson.dropbear.id.au> wrote:
 >   
 > [...]
 >
 > >  void flow_defer_handler(const struct ctx *c, const struct timespec *now)
 > >  {
 > > +	struct flow_free_block *free_head = NULL;
 > > +	unsigned *last_next = &flow_first_free;
 > >  	bool timer = false;
 > > -	union flow *flow;
 > > +	unsigned idx;
 > >  
 > >  	if (timespec_diff_ms(now, &flow_timer_run) >= FLOW_TIMER_INTERVAL) {
 > >  		timer = true;
 > >  		flow_timer_run = *now;
 > >  	}
 > >  
 > > -	for (flow = flowtab + flow_count - 1; flow >= flowtab; flow--) {
 > > +	for (idx = 0; idx < FLOW_MAX; idx++) {
 > > +		union flow *flow = &flowtab[idx];
 > >  		bool closed = false;
 > >  
 > > +		if (flow->f.type == FLOW_TYPE_NONE) {
 > > +			/* Start of a free block */
 > > +			free_head = &flow->free;
 > > +			*last_next = idx;
 > > +			last_next = &free_head->next;
 > > +			/* Skip the rest of the block */
 > > +			idx += free_head->n - 1;
 > > +			continue;
 > > +		}
 > > +
 > > +		  
 > 
 > Stray tabs.
 >   
 > >  		switch (flow->f.type) {
 > > +		case FLOW_TYPE_NONE:
 > > +			closed = true;
 > > +			break; 
...more important than stray tabs, I noticed only now: how would we ever
hit this switch case, if you're checking for this in the if clause just
before?

...
  > >  		case FLOW_TCP:
 > >  			closed = tcp_flow_defer(flow);
 > >  			break; 
-- 
Stefano