Everything

php

zend_hash.c fishy code

php.internals

Stefan Esser

20 years ago

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

Sara Golemon

20 years ago

> 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

20 years ago

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:

Stefan Esser

20 years ago

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

20 years ago

> 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

20 years ago

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

20 years ago

> 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