On Mon, 6 Jun 2022 11:01:21 +0200
Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> wrote:
> On Fri, Jun 03, 2022 at 03:04:45PM +0200, Stefano Brivio wrote:
> > On Wed, 1 Jun 2022 13:15:08 +0200
> > Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> wrote:
> >
> > > On Wed, May 25, 2022 at 02:15:07PM +0200, Stefano Brivio wrote:
> > > > On Mon, 23 May 2022 16:59:30 +0200
> > > > Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> wrote:
> > > [...]
> > > > > Another possibility? Maintain two trees, one for the existing
> > > > > generation (this is read-only) and another for the next generation
> > > > > (insertion/removals are performed on it), then swap them when commit
> > > > > happens?
> > > >
> > > > It sounded like a good idea and I actually started sketching it, but
> > > > there's one fundamental issue: it doesn't help with overlap detection
> > > > because we also want to check insertions that will be part of the live
> > > > copy. If, within one transaction, you delete and create elements, the
> > > > "dirty" copy is still dirty for the purposes of overlaps.
> > >
> > > Updates on the copy could be done without using the deactivate/active
> > > logic since it is not exposed to the packet path. Then, you use the
> > > copy (next generation of the datastructure) to check for overlaps? We
> > > need keep pointer to two sets in the rbtree private data area, the
> > > generation ID would point to the current set that is being used from
> > > the packet path. The stale tree is released from the commit phase (see
> > > below).
> >
> > Oh, right, I guess that would work. But at a first glance it looks more
> > complicated than the other idea:
>
> Yes, my idea would trigger a larger rewrite.
>
> > > > For the lookup, that might help. Is it worth it right now, though? At
> > > > the moment I would go back and try to get overlap detection work
> > > > properly, at least, with my previous idea.
> > >
> > > If your idea is still in planning phase, could you summarize again the
> > > idea? You mentioned about using gc you mentioned, if it is more simple
> > > than my proposal, then it should be good to go too.
> >
> > ...hmm, no, forget about gc, that was flawed. I'm just "walking" the
> > tree (going through elements as a list, instead of descending it),
> > noting down closest left and right elements to what we're inserting,
> > and check it with similar criteria to what we already have (but much
> > simpler, because we don't have to infer anything from what might be in
> > other leaves/nodes).
> >
> > That is, if you have elements 3 (start), 5 (end), 7 (start), 8 (end),
> > and you're inserting 6 as a start, we'll end up the tree walk with 5
> > (end) on the left and 7 (start) on the right, so we know it's not
> > overlapping.
> >
> > If you insert 4 (as start or end), we know we have 3 and 5 around, so
> > it overlaps.
> >
> > It's essentially the same as it is now, just dropping a lot of corner
> > cases and changing the way we go through the tree.
> >
> > I kind of implemented it, I still need a bit to make it working.
>
> That sounds an incremental fix, I prefer this too.
...finally posted now.
> > > > > pipapo has similar requirements, currently it is relying on a
> > > > > workqueue to make some postprocess after the commit phase. At the
> > > > > expense of consuming more memory.
> > > >
> > > > Well, it keeps two copies already: all the insertions and removals are
> > > > done on the dirty copy. The two problems we have there are:
> > > >
> > > > - the clean copy might also contain inactive elements (because on a
> > > > "commit" operation the API doesn't guarantee that all inserted
> > > > elements are active), so we need to check for those during lookup,
> > > > which is quite heavy (in my tests that was 4% of the clock cycles
> > > > needed for lookup in a set with 30 000 "port, protocol" entries)
> > > >
> > > > - on every _activate() call, we also need to commit the dirty copy onto
> > > > a clean one, instead of having one commit per transaction (because if
> > > > there's a newly activated item, we need to see it from the lookup),
> > > > so every transaction translates to a number of commit operations for
> > > > the back-end.
> > > >
> > > > That also makes things a bit complicated and it might very well be
> > > > related to point 3. below
> > > >
> > > > ...there's no actual workqueue: garbage collection (for timed out
> > > > entries) only happens on commit, I don't see a particular problem with
> > > > it.
> > > >
> > > > I think both issues would be solved if we had a more natural API, that
> > > > is, having a single call to the back-end implementing a commit
> > > > operation, instead of separately activating single entries. I don't
> > > > know how complicated this change would be.
> > >
> > > It should be possible to add a ->commit operation to set->ops, then
> > > call it at the end of the commit phase, ie. iterate over the list of
> > > existing sets in the table and call set->ops->commit().
> >
> > That sounds good, but when would we call it? Can it be independent of
> > the userspace version? Could we then obsolete the "activate" operation
> > (of course, by implementing commit() in all the sets)?
>
> Call it from nf_tables_commit().
>
> I don't see how we can obsolete "activate" operation, though, the
> existing approach works at set element granularity.
Yes, and that's what I'm arguing against: it would be more natural, in
a transaction, to have a single commit operation for all the elements
at hand -- otherwise it's not so much of a transaction.
To the user it's atomic (minus bugs) because we have tricks to ensure
it, but to the set back-ends it's absolutely not. I think we have this
kind of situation:
nft <-> core <-> set back-end <-> storage
| | |
hash: transaction commit element commit element commit
rbtree: transaction commit element commit element commit
^ problematic to the
point we're
considering a
transaction approach
pipapo: transaction commit element commit transaction commit
The single advantage I see of the current approach is that with the
hash back-ends we don't need two copies of the hash table, but that
also has the downside of the nft_set_elem_active(&he->ext, genmask)
check in the lookup function, which should be, in relative terms, even
more expensive than it is in the pipapo implementation, given that hash
back-ends are (in most cases) faster.
--
Stefano
