89465 - Infinite loop in PL_HashEnumerateEntries

Status: RESOLVED FIXED

(Core :: Preferences: Backend, defect)

Description

[Conrad Carlen (not reading bugmail)]

This came from bug 89160. From that:

The problem is, with certain data sets, calling PL_HashEnumerateEntries
can go into an infinite loop if HT_ENUMERATE_REMOVE is returned from the
callback.

Comment 1

[Conrad Carlen (not reading bugmail)]

Wan-Teh, any status on this? The code I checked into prefs (bug 89160) to avoid
this problem in PL_HashEnumerateEntries has a side-effect. I would like to be
able to go back to the way it was (removing entries during enumeration) but
can't unless this is fixed.

Comment 2

[Wan-Teh Chang]

I did not work on this.

Could you explain again how we can get into an
infinite loop?  Do you have a fix?

Comment 3

[Conrad Carlen (not reading bugmail)]

Wan-Teh, It's difficult to reproduce this. Here is an account of the problem
from mail I sent to you:


It is possible for PL_HashTableEnumerateEntries to go into an infinite loop. If
the callback function returns HT_ENUMERATE_NEXT, the pointer is advanced to the
next entry ( http://lxr.mozilla.org/seamonkey/source/nsprpub/lib/ds/plhash.c#422)
At that point, if he->next->next == he, it will loop forever. In this case, n >
ht->nentries which should be impossible.

I'm using PL_HashTableEnumerateEntries from here:
http://lxr.mozilla.org/seamonkey/source/modules/libpref/src/prefapi.c#1132
Notice in the callback function, I don't ever return HT_ENUMERATE_STOP because
I'm relying on the enumeration to stop when there are no more elements.

I think PL_HashTableEnumerateEntries should guard against going into an infinite
loop.

-Conrad

Comment 4

[Conrad Carlen (not reading bugmail)]

The code for which there was a link in prefapi.c was changed to not cause this
problem. Here's that checkin so you can see what was done:

http://bonsai.mozilla.org/cvsview2.cgi?diff_mode=context&whitespace_mode=show&file=prefapi.c&root=/cvsroot&subdir=mozilla/modules/libpref/src&command=DIFF_FRAMESET&rev1=3.92&rev2=3.93

Comment 5

[Wan-Teh Chang]

Brendan: I'd appreciate it if you could look at this
PLHashTable bug.

Conrad:  Thanks for the account of the problem.  I've
stared at the PL_HashTableEnumerateEntries source code
several times and failed to see anything wrong.  I don't
think he->next->next == he could be true for a good hash
table.  So if he->next->next == he, the hash table is
already inconsistent.  Even if I add a check to
PL_HashTableEnumerateEntries to prevent it from going
into an infinite loop, any further use of the corrupted
hash table will be problematic and we are just hiding
an error.

Do you know how we could get into a state where
he->next->next == he?

Comment 6

[Brendan Eich [:brendan]]

Yeah, how did you get a cycle in a singly-linked, null terminated hash chain?
That "can't happen".  Did someone call PL_HashTableRemove from within the pref
callback called from the enumerator?

/be

Comment 7

[Conrad Carlen (not reading bugmail)]

> Did someone call PL_HashTableRemove from within the pref callback called from
> the enumerator?

I'll look and see if anything is doing this.

Comment 8

[Judson Valeski]

what did you find Conrad?

Comment 9

[Conrad Carlen (not reading bugmail)]

It's difficult to know whether anything is calling PL_HashTableRemove from a
callback. I haven't been able to make this happen again and looking at every
callback in lxr is laborious.

Since it's hard to rule out a call to PL_HashTableRemove during enumeration,
this clearing operation could be done in two passes:
1st enumeration:
  Clear the has_user_value bit, make the callback, set a doom_entry bit, leave
entry in table
2nd enumeration:
  Remove entries with the doom_entry bit set

Comment 10

[Brendan Eich [:brendan]]

Actually, Remove seems to me not problematic, but Add and even Lookup (which
reorganizes hash chains for MRU order, unlike PL_HashTable(Raw)LookupConst) are
problematic.  My money's on Lookup.

This is a "feature" of plhash, always has been.  The advice in the doctor joke
applies ("it hurts when i do that" -- "don't do that"), but if you can't keep
different layers in a large system from doing that, you will have to defend in
the layer that uses plhash, as Conrad sketches.  xpcom/ds/nsHashtable defends, IIRC.

/be

Comment 11

[Conrad Carlen (not reading bugmail)]

> My money's on Lookup.

I believe that. I think most, if not all, callbacks do a PREF_Get...Pref which
leads to a PR_HashTableLookup.

Comment 12

[Brendan Eich [:brendan]]

You could do what nsHashtable.cpp does: keep an mEnumerating flag and if true,
use PL_HashTableLookupConst instead of PL_HashTableLookup.

/be

Comment 13

[Conrad Carlen (not reading bugmail)]

Attachment: patch for safe lookup during enumeraton

Comment 14

[Conrad Carlen (not reading bugmail)]

The patch uses the flag to do the right kind of lookup during enumeration. In
order to avoid spreading the use of this flag out all over this C/C++ code, I
made two wrapper functions.

If only this code was all C++, it could have just used nsHashTable and not had
this problem. Brian, any chance of that?

Comment 15

[Brendan Eich [:brendan]]

Conrad, can you use PL_ prefixed names throughout?  The PR_ ones are deprecated
for plhash.h-exported functions.  Other than that, r/sr=[e-mail].

/be

Comment 16

[Conrad Carlen (not reading bugmail)]

Attachment: same patch but PR -> PL

Comment 17

[Brian Nesse (gone)]

Conrad, I'm pretty sure there is a bug open for that, though I can't find it
right now. No unfortunately it isn't likely to change in the near future, which
is what I expect you are hoping for.

Comment 18

[Conrad Carlen (not reading bugmail)]

Argh - this one fell off in the no-milestone abyss. -> 0.9.6
Brian - can  you review it? Maybe this would help with bug 98736?

Comment 19

[Brian Nesse (gone)]

Comment on attachment 47830 [details] [diff] [review]
same patch but PR -> PL

Looks good to me. r=bnesse.

Comment 20

[Brian Nesse (gone)]

You could be right about bug 98736, I don't know. We aren't going into an
infinite loop, but we do seem to be getting a bad hashtable entry. We can try
having Gagan and Sol test against a build with this patch in it...

Comment 21

[Conrad Carlen (not reading bugmail)]

Fix checked in.