3 ms·

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 d

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.

o11c 2y ago
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?
- samatman 2y ago
  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.
- tialaramex 2y ago
  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.
  - rurban 2y ago
    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
    - tialaramex 2y ago
      Where in the code is this "no disaster" routine you describe?
      - rurban 2y ago
        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.
- bufferoverflow 2y ago
  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.
  - tialaramex 2y ago
    "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.
    - mst 2y ago
      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)
- tubs 2y ago
  They resize the top level array and rehash items into their new buckets.
  - tialaramex 2y ago
    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.
    - tubs 2y ago
      They go to the same bucket because their hash *mod the size of the top array* collides.
      - tialaramex 2y ago
        This whole sub-thread is about the case where the entire hash collides Changing which bits we use changes nothing for this problem case.
        tubs 2y ago
        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.

o11c 2y ago

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?

samatman 2y ago
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.
tialaramex 2y ago
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.
- rurban 2y ago
  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
  - tialaramex 2y ago
    Where in the code is this "no disaster" routine you describe?
    - rurban 2y ago
      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.
bufferoverflow 2y ago
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.
- tialaramex 2y ago
  "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.
  - mst 2y ago
    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)
tubs 2y ago
They resize the top level array and rehash items into their new buckets.
- tialaramex 2y ago
  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.
  - tubs 2y ago
    They go to the same bucket because their hash *mod the size of the top array* collides.
    - tialaramex 2y ago
      This whole sub-thread is about the case where the entire hash collides Changing which bits we use changes nothing for this problem case.
      - tubs 2y ago
        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.