[haiku-bugs] Re: [Haiku] #13927: gpgme KDL's when test are enabled
- From: "Haiku" <trac@xxxxxxxxxxxx>
- To: undisclosed-recipients: ;
- Date: Tue, 28 Jan 2020 22:56:27 -0000
#13927: gpgme KDL's when test are enabled
--------------------------------------+----------------------------
Reporter: Begasus | Owner: axeld
Type: bug | Status: new
Priority: normal | Milestone: Unscheduled
Component: Network & Internet/TCP | Version: R1/Development
Resolution: | Keywords:
Blocked By: | Blocking:
Has a Patch: 0 | Platform: All
--------------------------------------+----------------------------
Comment (by ambroff):
Thanks for the reply waddlesplash,
If the hash table doesn't support duplicate insertions properly in any
case at all, then we probably should just always panic on this case so we
detect it rather than corrupting memory, right?
Yeah that's what I wanted to do at first. BOpenHashTable actually has a
non-type template parameter "CheckDuplicates" which does exactly that. It
defaults to false, but if you set it to true then duplicates are checked
upon insertion or removal, and the presence of a duplicate will trap in
the debugger (or panic in kernel mode).
So on the surface it seems like the right default is to just remove the
CheckDuplicates option and always perform this duplicate check, since
allowing duplicates is not possible.
The big problem with this is the design of the BOpenHashTable template, in
that it isn't an open hash table at all. It's a chained hash table using
the classic linked-list for each bucket approach. That means that if you
modify BOpenHashTable to always perform this duplicate check, the cost of
insertion goes from O(1) to O(N).
Now this duplicate problem isn't really even that big of an issue for a
simpler chained hash table implementation. The problem is that this
implementation uses an intrusive linked list, which is the real source of
the problem here.
So when I said,
But now that I've read through that code carefully I don't think that's
the right thing to do, since it adds some non-trivial cost for other uses
of that container where it isn't necessary.
What I meant was that if a user of BOpenHashTable as it is implemented
today knows for certain that a duplicate insertion is not possible, then
the default of CheckDuplicates=false is advantageous, because it cuts down
on the cost of insertion.
It is pretty sketchy though, and I think this data structure is pretty
difficult to use correctly.
So there are two issues in play at this point:
As a bandaid for the tcp add-on, I think it makes sense to add a
fConnectionHash.RemoveUnchecked(endpoint) right before insertion in
SetConnection() to handle the case where sockets are being reused. I'm
about to submit a patch that does this.
As a followup I think BOpenHashTable should have some work done, and that
should probably be a separate ticket that I can follow. There are a bunch
of possible approaches to making this container easier to user.
1. Make BOpenHashTable a true open hash table. This means potentially
more copying as the buffer resizes, but may perform better for some
workloads, and removes the need for the intrusive linked list.
2. OR Maintain the chained hash table design but don't use an intrusive
linked list, which would mean more allocations but would also mean more
safety.
3. OR Replace the intrusive linked list with a random access collection
like a vector or a search tree. This means that you could maintain some
invariants for each bucket, for example that the items are sorted so that
you can always find duplicates in < O(N) time.
Thanks for spending the time investigating this!!
Sure! Thanks for all of the hard work you guys have done over the years.
--
Ticket URL: <
https://dev.haiku-os.org/ticket/13927#comment:16>
Haiku <
https://dev.haiku-os.org>
The Haiku operating system.
Other related posts:
