You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Julian Foad <ju...@apache.org> on 2015/12/10 17:14:45 UTC
apr_hash_overlay returns hash with duplicate keys
APR devs, Subversion devs:
On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
sometimes returns a hash containing duplicate keys, which (as I
understand it) should be impossible.
We had an issue where some 'svnmover' tests were failing only on Mac
OS buildbots. I added some debugging in Subversion commits r1719056,
r1719067, r1719072, r1719074.
Buildbot result:
https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
--> debug output in 'faillog' shows duplicate keys in hash:
"union_children={A, iota, foo, boozle, boozle, iota}"
I replaced apr_hash_overlay() with my own simple re-implementation:
http://svn.apache.org/r1719089 -- re-implement hash overlay
Buildbot result:
https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/486/steps/Test%20ra_svn%2Bbdb
--> tests pass
(in this step 5 of the buildbot; other tests still fail in steps 4 and 6)
The bot's config-log shows APR v1.4.5, APR-util v1.3.12.
Next questions should be: Is this a known bug? Can we reproduce it in
a small test case?
- Julian
RE: apr_hash_overlay returns hash with duplicate keys
Posted by Bert Huijben <be...@qqmail.nl>.
Are both hash tables created with the same hash function? (I think stefan2 introduced some variants).
Otherwise I would expect some key values to be changed somewhere after adding to the first hashtable… But I don’t think this is really a likely scenario.
Bert
Sent from Outlook Mail for Windows 10 phone
From: Julian Foad
Sent: donderdag 10 december 2015 17:15
To: APR devel
Cc: dev
Subject: apr_hash_overlay returns hash with duplicate keys
APR devs, Subversion devs:
On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
sometimes returns a hash containing duplicate keys, which (as I
understand it) should be impossible.
We had an issue where some 'svnmover' tests were failing only on Mac
OS buildbots. I added some debugging in Subversion commits r1719056,
r1719067, r1719072, r1719074.
Buildbot result:
https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
--> debug output in 'faillog' shows duplicate keys in hash:
"union_children={A, iota, foo, boozle, boozle, iota}"
I replaced apr_hash_overlay() with my own simple re-implementation:
http://svn.apache.org/r1719089 -- re-implement hash overlay
Buildbot result:
https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/486/steps/Test%20ra_svn%2Bbdb
--> tests pass
(in this step 5 of the buildbot; other tests still fail in steps 4 and 6)
The bot's config-log shows APR v1.4.5, APR-util v1.3.12.
Next questions should be: Is this a known bug? Can we reproduce it in
a small test case?
- Julian
RE: apr_hash_overlay returns hash with duplicate keys
Posted by Bert Huijben <be...@qqmail.nl>.
Are both hash tables created with the same hash function? (I think stefan2 introduced some variants).
Otherwise I would expect some key values to be changed somewhere after adding to the first hashtable… But I don’t think this is really a likely scenario.
Bert
Sent from Outlook Mail for Windows 10 phone
From: Julian Foad
Sent: donderdag 10 december 2015 17:15
To: APR devel
Cc: dev
Subject: apr_hash_overlay returns hash with duplicate keys
APR devs, Subversion devs:
On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
sometimes returns a hash containing duplicate keys, which (as I
understand it) should be impossible.
We had an issue where some 'svnmover' tests were failing only on Mac
OS buildbots. I added some debugging in Subversion commits r1719056,
r1719067, r1719072, r1719074.
Buildbot result:
https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
--> debug output in 'faillog' shows duplicate keys in hash:
"union_children={A, iota, foo, boozle, boozle, iota}"
I replaced apr_hash_overlay() with my own simple re-implementation:
http://svn.apache.org/r1719089 -- re-implement hash overlay
Buildbot result:
https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/486/steps/Test%20ra_svn%2Bbdb
--> tests pass
(in this step 5 of the buildbot; other tests still fail in steps 4 and 6)
The bot's config-log shows APR v1.4.5, APR-util v1.3.12.
Next questions should be: Is this a known bug? Can we reproduce it in
a small test case?
- Julian
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <ch...@gmail.com>.
On 11 December 2015 at 06:18, William A Rowe Jr <wr...@rowe-clan.net> wrote:
> Which public API, APR's or svn's?
>
Subversion's. Sorry I forgot that dev@a.a.o list is in cc.
--
Ivan Zhakov
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <ch...@gmail.com>.
On 11 December 2015 at 06:18, William A Rowe Jr <wr...@rowe-clan.net> wrote:
> Which public API, APR's or svn's?
>
Subversion's. Sorry I forgot that dev@a.a.o list is in cc.
--
Ivan Zhakov
Re: apr_hash_overlay returns hash with duplicate keys
Posted by William A Rowe Jr <wr...@rowe-clan.net>.
Which public API, APR's or svn's?
On Dec 10, 2015 11:24 AM, "Ivan Zhakov" <ch...@gmail.com> wrote:
> On 10 December 2015 at 20:20, Julian Foad <ju...@apache.org> wrote:
> > Ivan Zhakov wrote:
> >> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org>
> wrote:
> >>> APR devs, Subversion devs:
> >>>
> >>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
> >>> sometimes returns a hash containing duplicate keys, which (as I
> >>> understand it) should be impossible.
> >>>
> >>> We had an issue where some 'svnmover' tests were failing only on Mac
> >>> OS buildbots. I added some debugging in Subversion commits r1719056,
> >>> r1719067, r1719072, r1719074.
> >>>
> >>> Buildbot result:
> >>>
> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
> >>> --> debug output in 'faillog' shows duplicate keys in hash:
> >>> "union_children={A, iota, foo, boozle, boozle, iota}"
> >>>
> >>> I replaced apr_hash_overlay() with my own simple re-implementation:
> >>>
> >>> http://svn.apache.org/r1719089 -- re-implement hash overlay
> >>>
> >> Hi Julian,
> >>
> >> That could be possible if two hashes uses different hash functions.
> >> This could happen if you're using svn_hash__make() directly or
> >> indirectly: for example RA get_dirent for svn:// protocol returns hash
> >> with non-standard hash-function.
> >
> > Ugh. Yes, that is probably the cause. Thanks.
> >
> > I can see now that the doc string of apr_hash_overlay() does say "Both
> > hash tables must use the same hash function" but that was not obvious,
> > and I had totally forgotten that our Subversion code was using more
> > than one hash function.
> >
> > I will use my own hash overlay function from now on.
> >
> I don't think this is proper fix for this problem. I think returning
> hash with non-standard hash function from public API is a bug (and API
> regression). Other API users may get to the same situation. So proper
> fix would be revert these optimizations from public API imo.
>
>
> --
> Ivan Zhakov
>
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Stefan Fuhrmann <eq...@web.de>.
On 10.12.2015 18:23, Ivan Zhakov wrote:
> On 10 December 2015 at 20:20, Julian Foad <ju...@apache.org> wrote:
>> Ivan Zhakov wrote:
>>> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
>>>> APR devs, Subversion devs:
>>>>
>>>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
>>>> sometimes returns a hash containing duplicate keys, which (as I
>>>> understand it) should be impossible.
>>>>
>>>> We had an issue where some 'svnmover' tests were failing only on Mac
>>>> OS buildbots. I added some debugging in Subversion commits r1719056,
>>>> r1719067, r1719072, r1719074.
>>>>
>>>> Buildbot result:
>>>> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
>>>> --> debug output in 'faillog' shows duplicate keys in hash:
>>>> "union_children={A, iota, foo, boozle, boozle, iota}"
>>>>
>>>> I replaced apr_hash_overlay() with my own simple re-implementation:
>>>>
>>>> http://svn.apache.org/r1719089 -- re-implement hash overlay
>>>>
>>> Hi Julian,
>>>
>>> That could be possible if two hashes uses different hash functions.
>>> This could happen if you're using svn_hash__make() directly or
>>> indirectly: for example RA get_dirent for svn:// protocol returns hash
>>> with non-standard hash-function.
>>
>> Ugh. Yes, that is probably the cause. Thanks.
>>
>> I can see now that the doc string of apr_hash_overlay() does say "Both
>> hash tables must use the same hash function" but that was not obvious,
>> and I had totally forgotten that our Subversion code was using more
>> than one hash function.
That API restriction has been removed in 1.4.6.
When APR introduced "randomized" hash functions for
each hash instance, they could no longer simply reuse
the hash values across instances.
>> I will use my own hash overlay function from now on.
You could add a version check and call the APR
library function for newer APR releases.
> I don't think this is proper fix for this problem. I think returning
> hash with non-standard hash function from public API is a bug (and API
> regression).
We always return a standard hash. What is different
is that we don't instantiate it with the *default*
hash function.
> Other API users may get to the same situation. So proper
> fix would be revert these optimizations from public API imo.
It is up to the APR API user to use that API correctly.
For instance, there is no guarantee anywhere that any
two apr_hash_t instances use the same hash function.
Furthermore, it is up to the APR project to keep their
API documentation in sync with the code such that users
won't jump through hoops needlessly.
-- Stefan^2.
Re: apr_hash_overlay returns hash with duplicate keys
Posted by William A Rowe Jr <wr...@rowe-clan.net>.
Which public API, APR's or svn's?
On Dec 10, 2015 11:24 AM, "Ivan Zhakov" <ch...@gmail.com> wrote:
> On 10 December 2015 at 20:20, Julian Foad <ju...@apache.org> wrote:
> > Ivan Zhakov wrote:
> >> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org>
> wrote:
> >>> APR devs, Subversion devs:
> >>>
> >>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
> >>> sometimes returns a hash containing duplicate keys, which (as I
> >>> understand it) should be impossible.
> >>>
> >>> We had an issue where some 'svnmover' tests were failing only on Mac
> >>> OS buildbots. I added some debugging in Subversion commits r1719056,
> >>> r1719067, r1719072, r1719074.
> >>>
> >>> Buildbot result:
> >>>
> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
> >>> --> debug output in 'faillog' shows duplicate keys in hash:
> >>> "union_children={A, iota, foo, boozle, boozle, iota}"
> >>>
> >>> I replaced apr_hash_overlay() with my own simple re-implementation:
> >>>
> >>> http://svn.apache.org/r1719089 -- re-implement hash overlay
> >>>
> >> Hi Julian,
> >>
> >> That could be possible if two hashes uses different hash functions.
> >> This could happen if you're using svn_hash__make() directly or
> >> indirectly: for example RA get_dirent for svn:// protocol returns hash
> >> with non-standard hash-function.
> >
> > Ugh. Yes, that is probably the cause. Thanks.
> >
> > I can see now that the doc string of apr_hash_overlay() does say "Both
> > hash tables must use the same hash function" but that was not obvious,
> > and I had totally forgotten that our Subversion code was using more
> > than one hash function.
> >
> > I will use my own hash overlay function from now on.
> >
> I don't think this is proper fix for this problem. I think returning
> hash with non-standard hash function from public API is a bug (and API
> regression). Other API users may get to the same situation. So proper
> fix would be revert these optimizations from public API imo.
>
>
> --
> Ivan Zhakov
>
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <iv...@apache.org>.
On 11 December 2015 at 04:12, Branko Čibej <br...@apache.org> wrote:
> On 10.12.2015 18:23, Ivan Zhakov wrote:
>> I think returning
>> hash with non-standard hash function from public API is a bug (and API
>> regression). Other API users may get to the same situation. So proper
>> fix would be revert these optimizations from public API imo.
>
> I really can't agree with this. A user of the APR public API cannot
> assume which hash function is used by any instance of apr_hash_t that
> she did not create herself. In other words, no-one should be calling
> apr_hash_overlay() (with APR <= 1.4.5) unless they know that the hashes
> use the same hash function.
>
> The only "bug" here is a design bug in older versions of
> apr_hash_overlay() (and apr_hash_merge()), and even that is debatable.
>
This sounds good in theory, but in reality even Subversion developers
encounters this really weird behavior.
Btw is it possible to backport apr_hash_overlay()/apr_hash_merge() fix
to APR 1.3.x?
> As far as the Subversion code is concerned, we should, IMO, be using
> svn_hash__make() everywhere, since we have it.
>
We cannot use svn_hash__make() everywhere at least it doesn't immune
to hash-collision attacks like CVE-2012-0840 [1]
[1] https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2012-0840
--
Ivan Zhakov
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Branko Čibej <br...@apache.org>.
On 10.12.2015 18:23, Ivan Zhakov wrote:
> I think returning
> hash with non-standard hash function from public API is a bug (and API
> regression). Other API users may get to the same situation. So proper
> fix would be revert these optimizations from public API imo.
I really can't agree with this. A user of the APR public API cannot
assume which hash function is used by any instance of apr_hash_t that
she did not create herself. In other words, no-one should be calling
apr_hash_overlay() (with APR <= 1.4.5) unless they know that the hashes
use the same hash function.
The only "bug" here is a design bug in older versions of
apr_hash_overlay() (and apr_hash_merge()), and even that is debatable.
As far as the Subversion code is concerned, we should, IMO, be using
svn_hash__make() everywhere, since we have it.
-- Brane
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <ch...@gmail.com>.
On 10 December 2015 at 20:20, Julian Foad <ju...@apache.org> wrote:
> Ivan Zhakov wrote:
>> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
>>> APR devs, Subversion devs:
>>>
>>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
>>> sometimes returns a hash containing duplicate keys, which (as I
>>> understand it) should be impossible.
>>>
>>> We had an issue where some 'svnmover' tests were failing only on Mac
>>> OS buildbots. I added some debugging in Subversion commits r1719056,
>>> r1719067, r1719072, r1719074.
>>>
>>> Buildbot result:
>>> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
>>> --> debug output in 'faillog' shows duplicate keys in hash:
>>> "union_children={A, iota, foo, boozle, boozle, iota}"
>>>
>>> I replaced apr_hash_overlay() with my own simple re-implementation:
>>>
>>> http://svn.apache.org/r1719089 -- re-implement hash overlay
>>>
>> Hi Julian,
>>
>> That could be possible if two hashes uses different hash functions.
>> This could happen if you're using svn_hash__make() directly or
>> indirectly: for example RA get_dirent for svn:// protocol returns hash
>> with non-standard hash-function.
>
> Ugh. Yes, that is probably the cause. Thanks.
>
> I can see now that the doc string of apr_hash_overlay() does say "Both
> hash tables must use the same hash function" but that was not obvious,
> and I had totally forgotten that our Subversion code was using more
> than one hash function.
>
> I will use my own hash overlay function from now on.
>
I don't think this is proper fix for this problem. I think returning
hash with non-standard hash function from public API is a bug (and API
regression). Other API users may get to the same situation. So proper
fix would be revert these optimizations from public API imo.
--
Ivan Zhakov
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <ch...@gmail.com>.
On 10 December 2015 at 20:20, Julian Foad <ju...@apache.org> wrote:
> Ivan Zhakov wrote:
>> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
>>> APR devs, Subversion devs:
>>>
>>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
>>> sometimes returns a hash containing duplicate keys, which (as I
>>> understand it) should be impossible.
>>>
>>> We had an issue where some 'svnmover' tests were failing only on Mac
>>> OS buildbots. I added some debugging in Subversion commits r1719056,
>>> r1719067, r1719072, r1719074.
>>>
>>> Buildbot result:
>>> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
>>> --> debug output in 'faillog' shows duplicate keys in hash:
>>> "union_children={A, iota, foo, boozle, boozle, iota}"
>>>
>>> I replaced apr_hash_overlay() with my own simple re-implementation:
>>>
>>> http://svn.apache.org/r1719089 -- re-implement hash overlay
>>>
>> Hi Julian,
>>
>> That could be possible if two hashes uses different hash functions.
>> This could happen if you're using svn_hash__make() directly or
>> indirectly: for example RA get_dirent for svn:// protocol returns hash
>> with non-standard hash-function.
>
> Ugh. Yes, that is probably the cause. Thanks.
>
> I can see now that the doc string of apr_hash_overlay() does say "Both
> hash tables must use the same hash function" but that was not obvious,
> and I had totally forgotten that our Subversion code was using more
> than one hash function.
>
> I will use my own hash overlay function from now on.
>
I don't think this is proper fix for this problem. I think returning
hash with non-standard hash function from public API is a bug (and API
regression). Other API users may get to the same situation. So proper
fix would be revert these optimizations from public API imo.
--
Ivan Zhakov
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Julian Foad <ju...@apache.org>.
Ivan Zhakov wrote:
> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
>> APR devs, Subversion devs:
>>
>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
>> sometimes returns a hash containing duplicate keys, which (as I
>> understand it) should be impossible.
>>
>> We had an issue where some 'svnmover' tests were failing only on Mac
>> OS buildbots. I added some debugging in Subversion commits r1719056,
>> r1719067, r1719072, r1719074.
>>
>> Buildbot result:
>> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
>> --> debug output in 'faillog' shows duplicate keys in hash:
>> "union_children={A, iota, foo, boozle, boozle, iota}"
>>
>> I replaced apr_hash_overlay() with my own simple re-implementation:
>>
>> http://svn.apache.org/r1719089 -- re-implement hash overlay
>>
> Hi Julian,
>
> That could be possible if two hashes uses different hash functions.
> This could happen if you're using svn_hash__make() directly or
> indirectly: for example RA get_dirent for svn:// protocol returns hash
> with non-standard hash-function.
Ugh. Yes, that is probably the cause. Thanks.
I can see now that the doc string of apr_hash_overlay() does say "Both
hash tables must use the same hash function" but that was not obvious,
and I had totally forgotten that our Subversion code was using more
than one hash function.
I will use my own hash overlay function from now on.
- Julian
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Julian Foad <ju...@apache.org>.
Ivan Zhakov wrote:
> On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
>> APR devs, Subversion devs:
>>
>> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
>> sometimes returns a hash containing duplicate keys, which (as I
>> understand it) should be impossible.
>>
>> We had an issue where some 'svnmover' tests were failing only on Mac
>> OS buildbots. I added some debugging in Subversion commits r1719056,
>> r1719067, r1719072, r1719074.
>>
>> Buildbot result:
>> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
>> --> debug output in 'faillog' shows duplicate keys in hash:
>> "union_children={A, iota, foo, boozle, boozle, iota}"
>>
>> I replaced apr_hash_overlay() with my own simple re-implementation:
>>
>> http://svn.apache.org/r1719089 -- re-implement hash overlay
>>
> Hi Julian,
>
> That could be possible if two hashes uses different hash functions.
> This could happen if you're using svn_hash__make() directly or
> indirectly: for example RA get_dirent for svn:// protocol returns hash
> with non-standard hash-function.
Ugh. Yes, that is probably the cause. Thanks.
I can see now that the doc string of apr_hash_overlay() does say "Both
hash tables must use the same hash function" but that was not obvious,
and I had totally forgotten that our Subversion code was using more
than one hash function.
I will use my own hash overlay function from now on.
- Julian
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <ch...@gmail.com>.
On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
> APR devs, Subversion devs:
>
> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
> sometimes returns a hash containing duplicate keys, which (as I
> understand it) should be impossible.
>
> We had an issue where some 'svnmover' tests were failing only on Mac
> OS buildbots. I added some debugging in Subversion commits r1719056,
> r1719067, r1719072, r1719074.
>
> Buildbot result:
> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
> --> debug output in 'faillog' shows duplicate keys in hash:
> "union_children={A, iota, foo, boozle, boozle, iota}"
>
> I replaced apr_hash_overlay() with my own simple re-implementation:
>
> http://svn.apache.org/r1719089 -- re-implement hash overlay
>
Hi Julian,
That could be possible if two hashes uses different hash functions.
This could happen if you're using svn_hash__make() directly or
indirectly: for example RA get_dirent for svn:// protocol returns hash
with non-standard hash-function.
--
Ivan Zhakov
Re: apr_hash_overlay returns hash with duplicate keys
Posted by Ivan Zhakov <ch...@gmail.com>.
On 10 December 2015 at 19:14, Julian Foad <ju...@apache.org> wrote:
> APR devs, Subversion devs:
>
> On Subversion's Mac OS buildbots it appears that apr_hash_overlay()
> sometimes returns a hash containing duplicate keys, which (as I
> understand it) should be impossible.
>
> We had an issue where some 'svnmover' tests were failing only on Mac
> OS buildbots. I added some debugging in Subversion commits r1719056,
> r1719067, r1719072, r1719074.
>
> Buildbot result:
> https://ci.apache.org/builders/svn-x64-macosx-bdb/builds/485/steps/Test%20ra_svn%2Bbdb
> --> debug output in 'faillog' shows duplicate keys in hash:
> "union_children={A, iota, foo, boozle, boozle, iota}"
>
> I replaced apr_hash_overlay() with my own simple re-implementation:
>
> http://svn.apache.org/r1719089 -- re-implement hash overlay
>
Hi Julian,
That could be possible if two hashes uses different hash functions.
This could happen if you're using svn_hash__make() directly or
indirectly: for example RA get_dirent for svn:// protocol returns hash
with non-standard hash-function.
--
Ivan Zhakov