News for hackers. Stuff that matters.
Re:A hash table by any other name by masklinn on Friday July 26, 2024 @11:50AM (#41079607)
No? From the text at least, the low bits are just used to select the bucket, this is a common technique (and reason for using power of two sizes such that you don't need a full modulo).

Once you're in a bucket, it does full hash match, then I assume (didn't look at the patch) actual key comparison.

Re:A hash table by any other name by o11c on Friday July 26, 2024 @12:25PM (#41079914)
That would be fine, except that in v2 the buckets are fixed size.

What happens when more than 20 objects end up with the exact same hash?

Re:A hash table by any other name by tialaramex on Friday July 26, 2024 @12:46PM (#41080085)
Yes it does seem like a problem, by my reading this will just endlessly try to "split" the bucket of 20 items, hoping that eventually one of the items goes into a new bucket leaving space, but if they have the same hash that never happens, disaster.

If I'm wrong I don't think this code does a good enough job of explaining what's going on, and if I'm correct it's defective and should not ship.

Even if this situation "shouldn't" happen, it clearly can happen, you just have to get unlucky, and it's difficult to compute how unlikely that is for real systems, so better to ensure that "We got unlucky" isn't a disaster for the kernel.

Re:A hash table by any other name by rurban on Friday July 26, 2024 @01:09PM (#41080308)
No desaster. On an actual attack (eg if the seed leaked) you count the collisions and return empty on some low threshold. Like 100 on 32bit
Re:A hash table by any other name by tialaramex on Friday July 26, 2024 @02:23PM (#41080936)
Where in the code is this "no disaster" routine you describe?
Re:A hash table by any other name by rurban on Monday July 29, 2024 @03:51AM (#41098647)
The code is not security hardened yet. seed attacks are not yet accustomed for. But it's no disaster, as it's trivial to prevent. They say seeds are secure, so no chance to attack it. Which is a bit childish.

It would just be a disaster if they follow Miller's networking code, which uses slower hashes to prevent seed attacks. But every other popular language/library does the very same wrong thing.

Re:A hash table by any other name by tubs on Friday July 26, 2024 @01:21PM (#41080418)
They resize the top level array and rehash items into their new buckets.
Re:A hash table by any other name by tialaramex on Friday July 26, 2024 @02:38PM (#41081079)
Sure. There were 20 items in the bucket with the same hash, we wanted to add one more.

So we grow the top level hash table and we put all of the twenty items in the same new bucket, because they have the same hash, and then we... oh, we don't have enough room. Try again? (The code presented does). Too bad, that can't help.

In your understanding, why does this not happen? That's the question. How do this code ensure this can't happen? If it doesn't, if it's just hoping to get lucky the code must not be used.

Re:A hash table by any other name by tubs on Friday July 26, 2024 @03:23PM (#41081459)
They go to the same bucket because their hash *mod the size of the top array* collides.
Re:A hash table by any other name by tialaramex on Friday July 26, 2024 @03:50PM (#41081678)
This whole sub-thread is about the case where the entire hash collides

Changing which bits we use changes nothing for this problem case.

Re:A hash table by any other name by tubs on Saturday July 27, 2024 @09:13AM (#41086366)
I see what you mean here, sorry.

I guess I'd argue if you have 20 items whose full hash collides then something is pretty seriously wrong with the hashing algorithm - raise an error/exception/panic/(whatever is appropriate for the situation) and surface it.

Re:A hash table by any other name by bufferoverflow on Friday July 26, 2024 @01:07PM (#41080285)
I think they address this in the article. They use arrays instead of linked lists. Which makes direct key comparison very fast, because it's all in CPU cache.
Re:A hash table by any other name by tialaramex on Friday July 26, 2024 @03:12PM (#41081381)
"I just use an array" doesn't solve the problem "What if the array is full?".

In fact it makes that problem acute. A linked list structure will degrade gradually as we shove more entries with the same hash into it, every look-up incurs a pointer chase down the entire list, slower is eventually unacceptable but we do get signs first -- but with arrays we're just screwed, in C it's pretty likely we end up with an illegal dereference or we lose data once there's no room.

Re:A hash table by any other name by mst on Friday July 26, 2024 @05:17PM (#41082359)
If it's designed to be used for caching, then replacing an old entry or throwing away the new one is quite possibly a perfectly reasonable "out."

If it's designed to be used for other purposes as well, not so much.

(I wasn't entirely sure which from reading the article)

Re:A hash table by any other name by samatman on Friday July 26, 2024 @12:45PM (#41080073)
If it were my hash table, the arrays would just be unrolled linked lists.

So a "twenty object" bucket would actually store 19 objects, and if the last one wasn't null it would contain a pointer to the next bucket.

I'm willing to presume these folks know what they're doing, so that's probably what's happening here.