p5pRT
commented
13 years ago From perl@ton.iguana.be
Created by perl@ton.iguana.be
When debuging a core dump in some XS code i reduced it to what seems to indicate a long standing bug in deleting elements in a HASH that is being iterated over.
Internally a perl HASH is an array of single linked chains of entries. Deleting an element means removing the correct chain entry by replacing the pointer to the removed entry with a pointer to the next entry and then freeing the deleted entry
However\, if the deleted element is the current entry the deleted entry is kept after removing it from the chain and the LAZYDEL flag is set. Only on the next iteration is the element actually removed and the iterator is set to the next entry.
However\, if you delete the current iterator and then delete the next element in the same chain the "next" pointer of the iterator is not updated because the iterator is not on the chain anymore. That means that when the next iteration looks up the iterator next pointer it will point to the freed memory of the second element.
This is easily demonstrated with the next program. It first uses Devel::Peek to find a chain with at least two elements\, then iterates there and deletes these two elements. The next iteration then causes a freed memory warning (in my real code more had happened with the memory at that point and I ended up with a core dump).
======================================================== #!/usr/bin/perl -w use strict; use Devel::Peek; use File::Temp qw(tempdir);
my %hash = ("a".."z");
my $tmp_dir = tempdir(CLEANUP => 1);
sub riter { local *OLDERR; open(OLDERR\, ">&STDERR") || die "Can't dup STDERR: $!"; open(STDERR\, ">"\, "$tmp_dir/dump") || die "Could not open '$tmp_dir/dump' for write: $^E"; Dump(\%hash); open(STDERR\, ">&OLDERR") || die "Can't dup OLDERR: $!"; open(my $fh\, "\<"\, "$tmp_dir/dump") || die "Could not open '$tmp_dir/dump' for read: $^E"; local $/; my $dump = \<$fh>; my ($riter) = $dump =~ /^\s*RITER\s*=\s*(\d+)/m or die "No plain RITER in dump '$dump'"; return $riter; }
my @riters; while (my $key = each %hash) { push @{$riters[riter()]}\, $key; }
my ($first_key\, $second_key); my $riter = 0; for my $chain (@riters) { if ($chain && @$chain >= 2) { $first_key = $chain->[0]; $second_key = $chain->[1]; last; } $riter++; } $first_key || die "No 2 element chains. Please retry with a different intial HASH"; $| = 1;
# Ok all preparation is done print \<\<"EOF" Found keys '$first_key' and '$second_key' on chain $riter Will now iterato to key '$first_key' then delete '$first_key' and '$second_key'. EOF ; 1 until $first_key eq each %hash; delete $hash{$first_key}; delete $hash{$second_key};
print "Now iterating into freed memory\n"; 1 for each %hash; print "Done (not reached)\n";
Most of that code above is to analyze the HASH chains. But once you know the keys on a 2-element (or more) chain the problem can be demonstrated directly too. E.g. on my system the HASH function works out so that the following code:
perl -wle '%a=("a".."z"); each %a; delete $a{w}; delete $a{e}; 1 for each %a'
will give:
Use of freed value in iteration at -e line 1
The fix is not so clear. Ideas would be: - Don't remove lazydel elements from the entry chain. Then its next pointer would always be upto date. But all iteration code would have to be fixed to skip the deleted iterator and getting the PL_sv_placeholder code right could be a bit tricky for restricted hashes. Still\, I think this would be the cleanest fix\, but it will break existing code that thinks it knows howe to iterate hash entries by itself - Fix hv_free_ent This is good because it would put all the fixup in one place. But it would implicitely assume that by the time an entry is passed to hv_free_ent its next pointer should still be valid. It also means doing the extra test even though the place it gets called is one where the lazydel problem can't happen (which is quite common) - Fix the places where the delete is done Drawback is that you may never forget to do the lazydel fixup in at any place where the entry chain gets shortened Anyways\, this is what I used in my sample fix. - Always delete the current entry but if it is the one in the iterator\, replace EITER by the next address \, and LAZYDEL just means that the EITER poiner is already increased. That still needs code to update the EITER pointer if THAT entry is deleted\, but it still leads to simpler code needing less HeNEXT()
Looking at the delete code I see another strange thing. If the delete of the current iterator is done with the G_DISCARD flag\, the corresponding value is not freed and survives until the lazy deleted entry gets removed on the next hash iteration. This is easily demonstrated like this:
perl -wle ' sub DESTROY { print "DESTROY" } %a=(a=>bless[]); each %a; delete $a{a}; print "END" '
This prints:
END DESTROY
notice the difference with:
perl -wle ' sub DESTROY { print "DESTROY" } %hash = (a => bless[]); each %hash; $dummy = delete $hash{a}; $dummy = 0; print "END" '
This prints:
DESTROY END
This is easily solved by always replacing the deleted entry value with &PL_sv_placeholder. It actually simplifies the code a bit except for the fact that the mro_method_changed from free_hash_ent now has to be done in hv_delete
A further note: while debugging this issue it was annoying that Devel::Peek::Dump doesb't actually dump the HASH elements when an iterator is active. Also added is a patch that does the iteration to dump the HASH contents by iterating over it by hand (not disturbing any active iterator). With that it also doesn't activate hash magic during iteration\, which I think is a feature
Next a few proposed patches solving all this. They are for perl 5.10.1\, (a quick look at blead indicates the code there seems unchanged\, so I think all this is still relevant)
Patch for deleting the element after a delete iterator
Inline Patch
```diff --- /home/ton/src/perl-5.10.1/hv.c 2009-06-10 14:36:34.000000000 +0200 +++ hv.c 2011-02-27 14:46:28.622503735 +0100 @@ -1060,8 +1060,12 @@ } if (SvOOK(hv) && entry == HvAUX(hv)->xhv_eiter /* HvEITER(hv) */) HvLAZYDEL_on(hv); - else + else { + if (SvOOK(hv) && HvLAZYDEL(hv) && + entry == HeNEXT(HvAUX(hv)->xhv_eiter)) + HeNEXT(HvAUX(hv)->xhv_eiter) = HeNEXT(entry); hv_free_ent(hv, entry); + } xhv->xhv_keys--; /* HvTOTALKEYS(hv)-- */ if (xhv->xhv_keys == 0) HvHASKFLAGS_off(hv); @@ -1611,8 +1615,12 @@ HvFILL(hv)--; /* This linked list is now empty. */ if (entry == HvEITER_get(hv)) HvLAZYDEL_on(hv); - else + else { + if (SvOOK(hv) && HvLAZYDEL(hv) && + entry == HeNEXT(HvAUX(hv)->xhv_eiter)) + HeNEXT(HvAUX(hv)->xhv_eiter) = HeNEXT(entry); hv_free_ent(hv, entry); + } if (--items == 0) { /* Finished. */ ```============================================================
Patch to delete the current iterator value when using G_DISCARD:
Inline Patch
```diff --- hv.c.old 2011-02-27 16:18:34.666306057 +0100 +++ hv.c 2011-02-27 17:11:05.540720971 +0100 @@ -1034,12 +1034,17 @@ if (k_flags & HVhek_FREEKEY) Safefree(key); - if (d_flags & G_DISCARD) - sv = NULL; - else { - sv = sv_2mortal(HeVAL(entry)); - HeVAL(entry) = &PL_sv_placeholder; - } + if (d_flags & G_DISCARD) { + sv = HeVAL(entry); + if (sv) { + /* deletion of method from stash */ + if (isGV(sv) && isGV_with_GP(sv) && GvCVu(sv) && HvNAME_get(hv)) + mro_method_changed_in(hv); + SvREFCNT_dec(sv); + sv = NULL; + } + } else sv = sv_2mortal(HeVAL(entry)); + HeVAL(entry) = &PL_sv_placeholder; /* * If a restricted hash, rather than really deleting the entry, put @@ -1047,13 +1052,11 @@ * we can still access via not-really-existing key without raising * an error. */ - if (SvREADONLY(hv)) { - SvREFCNT_dec(HeVAL(entry)); - HeVAL(entry) = &PL_sv_placeholder; + if (SvREADONLY(hv)) /* We'll be saving this slot, so the number of allocated keys * doesn't go down, but the number placeholders goes up */ HvPLACEHOLDERS(hv)++; - } else { + else { *oentry = HeNEXT(entry); if(!*first_entry) { xhv->xhv_fill--; /* HvFILL(hv)-- */ ```============================================================
Migrated from rt.perl.org#85026 (status was 'resolved')
Searchable as RT85026$