FAQ
Good Morning,

I wonder If I am completely missing the point, but the following piece
of code seems fishy to me:

ZEND_API int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint
nKeyLength, ulong h, int flag)
{
uint nIndex;
Bucket *p;

...

while (p != NULL) {
if ((p->h == h) && ((p->nKeyLength == 0) || /* Numeric
index */
((p->nKeyLength == nKeyLength) &&
(!memcmp(p->arKey, arKey, nKeyLength))))) {
HANDLE_BLOCK_INTERRUPTIONS();
...

If I am not completely mistaken this means: If this is a bucket with a
numeric index with the hash value of the key we want to delete, then
delete it, even when we wanted to delete a key with a string as index.

Stefan

Search Discussions

  • Sara Golemon at Jan 30, 2006 at 1:14 am

    I wonder If I am completely missing the point, but the following piece
    of code seems fishy to me:

    ZEND_API int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint
    nKeyLength, ulong h, int flag)
    {
    uint nIndex;
    Bucket *p;

    ...

    while (p != NULL) {
    if ((p->h == h) && ((p->nKeyLength == 0) || /* Numeric
    index */
    ((p->nKeyLength == nKeyLength) &&
    (!memcmp(p->arKey, arKey, nKeyLength))))) {
    HANDLE_BLOCK_INTERRUPTIONS();
    ...

    If I am not completely mistaken this means: If this is a bucket with a
    numeric index with the hash value of the key we want to delete, then
    delete it, even when we wanted to delete a key with a string as index.
    There's a fairly important bit in that first ...:
    if (flag == HASH_DEL_KEY) {
    h = zend_inline_hash_func(arKey, nKeyLength);
    }

    When deleting a numeric index nKeyLength is passed as zero and h contains
    the numeric index so this if only matches when p->h == h and p->nKeyLength
    == 0 (indicating a numericly keyed bucket).

    When deleting a string index, nKeyLength is non-zero and h as passed is
    unimportant since it's overridden with the actual hash of arKey and
    nKeyLength. The if then only evaluates true when the bucket hash matches
    the computed hash and the real key data in the bucket matches the real key
    data passed.

    Yes, comparing p->h to h seems unnecessary since p->arKey is being compared
    to arKey anyway, but that seemingly redundant comparison saves a more costly
    memcmp() when the hashes differ.

    -Sara
  • Andi Gutmans at Jan 30, 2006 at 3:49 am
    Yep correct. We always prefer to also check p->h so that we minimize
    the chances for reaching the memcmp()...
    At 04:33 PM 1/29/2006, Sara Golemon wrote:
    I wonder If I am completely missing the point, but the following piece
    of code seems fishy to me:

    ZEND_API int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint
    nKeyLength, ulong h, int flag)
    {
    uint nIndex;
    Bucket *p;

    ...

    while (p != NULL) {
    if ((p->h == h) && ((p->nKeyLength == 0) || /* Numeric
    index */
    ((p->nKeyLength == nKeyLength) &&
    (!memcmp(p->arKey, arKey, nKeyLength))))) {
    HANDLE_BLOCK_INTERRUPTIONS();
    ...

    If I am not completely mistaken this means: If this is a bucket with a
    numeric index with the hash value of the key we want to delete, then
    delete it, even when we wanted to delete a key with a string as index.
    There's a fairly important bit in that first ...:
    if (flag == HASH_DEL_KEY) {
    h = zend_inline_hash_func(arKey, nKeyLength);
    }

    When deleting a numeric index nKeyLength is passed as zero and h
    contains the numeric index so this if only matches when p->h == h
    and p->nKeyLength == 0 (indicating a numericly keyed bucket).

    When deleting a string index, nKeyLength is non-zero and h as passed
    is unimportant since it's overridden with the actual hash of arKey
    and nKeyLength. The if then only evaluates true when the bucket
    hash matches the computed hash and the real key data in the bucket
    matches the real key data passed.

    Yes, comparing p->h to h seems unnecessary since p->arKey is being
    compared to arKey anyway, but that seemingly redundant comparison
    saves a more costly memcmp() when the hashes differ.

    -Sara
    --
    PHP Internals - PHP Runtime Development Mailing List
    To unsubscribe, visit: http://www.php.net/unsub.php
  • Stefan Esser at Jan 30, 2006 at 9:08 am
    Hello Sara,

    you are missing my point. My point is that when a hashtable contains
    these two elements

    example:

    BUCKET_ENTRY for h=15
    --- Bucket1 : key == numeric -> h= numeric hash value == 15
    \-------- Bucket2: key == some string key, with a hash value equal
    to 15

    Lets assume we want to delete the key "THI_HASH_A_HASH_FUNCTION_VALUE_OF_15"
    then the code in question will first hash it and gets h==15. The next
    thing it will do is go through the linked list of buckets for h==15.
    Unfortunately the check there is broken. It will first check, that p->h
    is == 15 and then check if p->nKeyLength==0 which obviously
    is for our Bucket1. Unfortunately this is already enough to evaluate to
    true. But it is not what we intended. We wanted to delete bucket2.
    But we end up with Bucket1 deleted.

    Stefan
  • Jared Williams at Jan 30, 2006 at 1:08 pm

    you are missing my point. My point is that when a hashtable
    contains these two elements

    example:

    BUCKET_ENTRY for h=15
    --- Bucket1 : key == numeric -> h= numeric hash value == 15
    \-------- Bucket2: key == some string key, with a hash
    value equal to 15

    Lets assume we want to delete the key
    "THI_HASH_A_HASH_FUNCTION_VALUE_OF_15"
    then the code in question will first hash it and gets h==15.
    The next thing it will do is go through the linked list of
    buckets for h==15.
    Unfortunately the check there is broken. It will first check,
    that p->h is == 15 and then check if p->nKeyLength==0 which
    obviously is for our Bucket1. Unfortunately this is already
    enough to evaluate to true. But it is not what we intended.
    We wanted to delete bucket2.
    But we end up with Bucket1 deleted.
    /* original */
    if ((p->h == h) && ((p->nKeyLength == 0) || /* Numeric index */
    ((p->nKeyLength == nKeyLength) && (!memcmp(p->arKey, arKey, nKeyLength))))) {

    Vs.

    /* rearranged */
    if ((p->h == h) && (p->nKeyLength == nKeyLength)
    && ((nKeyLength == 0) || (!memcmp(p->arKey, arKey, nKeyLength))))

    Jared
  • Stanislav Malyshev at Jan 30, 2006 at 7:02 pm
    JW>> /* rearranged */
    JW>> if ((p->h == h) && (p->nKeyLength == nKeyLength)
    JW>> && ((nKeyLength == 0) || (!memcmp(p->arKey, arKey, nKeyLength))))

    This doesn't seem to be good - there's still a case when p->nKeyLength !=
    nKeyLength but the match should happen - when p is 15 (integer) and
    incoming key is "15" (string).

    --
    Stanislav Malyshev, Zend Products Engineer
    stas@zend.com http://www.zend.com/ +972-3-6139665 ext.115
  • Sara Golemon at Jan 30, 2006 at 5:06 pm

    you are missing my point. My point is that when a hashtable contains
    these two elements

    example:

    BUCKET_ENTRY for h=15
    --- Bucket1 : key == numeric -> h= numeric hash value == 15
    \-------- Bucket2: key == some string key, with a hash value equal
    to 15

    Lets assume we want to delete the key
    "THI_HASH_A_HASH_FUNCTION_VALUE_OF_15"
    then the code in question will first hash it and gets h==15. The next
    thing it will do is go through the linked list of buckets for h==15.
    Unfortunately the check there is broken. It will first check, that p->h
    is == 15 and then check if p->nKeyLength==0 which obviously
    is for our Bucket1. Unfortunately this is already enough to evaluate to
    true. But it is not what we intended. We wanted to delete bucket2.
    But we end up with Bucket1 deleted.
    Ah, yes, well, when you put it that way. I can absolutely see that taking
    place. What's worse, since DJBX33A isn't collision resistant (just
    collision avoidant) it'd be possible (in theory) to deliberately clobber a
    record by taking advantage of this (though not trivial).

    -Sara

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupphp-internals @
categoriesphp
postedJan 29, '06 at 9:01p
activeJan 30, '06 at 7:02p
posts7
users5
websitephp.net

People

Translate

site design / logo © 2022 Grokbase