We've seen this nasty little issue. The following code
class C { mapping options = ([1:1]);
void create() { werror("%O\n\n", options); } }
void main() { C c = C(); c->options[3] = 3; C cc = C(); }
will result in
nilsson@riaa:~$ pike --dumpversion 7.9.5 nilsson@riaa:~$ uname -a Linux riaa 2.6.38-10-generic #46-Ubuntu SMP Tue Jun 28 15:07:17 UTC 2011 x86_64 x86_64 x86_64 GNU/Linux nilsson@riaa:~$ pike test.pike ([ /* 1 element */ 1: 1 ])
([ /* 2 elements */ 1: 1, 3: 3 ])
thought it works fine on
nilsson@khora:~$ pike --dumpversion 7.9.5 nilsson@khora:~$ uname -a Linux khora 2.6.32-28-generic #55-Ubuntu SMP Mon Jan 10 21:21:01 UTC 2011 i686 GNU/Linux nilsson@khora:~$ pike test.pike ([ /* 1 element */ 1: 1 ])
([ /* 1 element */ 1: 1 ])
We've seen this nasty little issue. The following code
[...]
Thanks for the testcase. Registered as [bug 6062].
will result in
[...]
thought it works fine on
nilsson@khora:~$ pike --dumpversion 7.9.5 nilsson@khora:~$ uname -a Linux khora 2.6.32-28-generic #55-Ubuntu SMP Mon Jan 10 21:21:01 UTC 2011 i686 GNU/Linux
[...]
Actually it doesn't; the reason it works is that the pike binary is from before April 2011.
According to git bisect (and your testcase), the bug was introduced in commit 90314251db074fc740a2a2b01a9aca1939cd91a4.
No. It's comparing the hashtable size with the minimum required number of keypairs, these two usually differ by a factor of AVG_LINK_LENGTH.
And you don't know how it got into the state where this optimization is applicable?
And you don't know how it got into the state where this optimization is applicable?
I believe that Arne already has answered this question; the patch caused the minimum hashtable size to shrink to 4, which means that the realloc size (old_sz * 2 + 2) matched the hashtable size for the case where the old size was 1 and the hashtable size was 4 and the number of mapping_data references were > 1.
On Sun, 4 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum wrote:
No. It's comparing the hashtable size with the minimum required number of keypairs, these two usually differ by a factor of AVG_LINK_LENGTH.
One optimization we should probably do is to check if the mapping size is already at the minimum before rehashing to a smaller one. Currently it seems like it would rehash to the same size when removing an element from a mapping thats already at the minimum.
Here is a patch. Maybe someone can ack this, before I push it.
diff --git a/src/mapping.c b/src/mapping.c index def183a..ef693b2 100644 --- a/src/mapping.c +++ b/src/mapping.c @@ -27,6 +27,7 @@
#define AVG_LINK_LENGTH 4 #define MIN_LINK_LENGTH 1 +#define MIN_HASHSIZE 32 #define MAP_SLOTS(X) ((X)?((X)+((X)>>4)+8):0)
struct mapping *first_mapping; @@ -182,7 +183,7 @@ static void init_mapping(struct mapping *m, if(size) { hashsize = size / AVG_LINK_LENGTH + 1; - hashsize = (hashsize <= 32) ? 32 : find_next_power(hashsize); + hashsize = (hashsize <= MIN_HASHSIZE) ? MIN_HASHSIZE : find_next_power(hashsize);
e=MAPPING_DATA_SIZE(hashsize, size);
@@ -1017,7 +1018,7 @@ PMOD_EXPORT void map_delete_no_free(struct mapping *m, m->debug_size--; #endif
- if(md->size < (md->hashsize + 1) * MIN_LINK_LENGTH) + if((md->hashsize > MIN_HASHSIZE) && (md->size < (md->hashsize + 1) * MIN_LINK_LENGTH)) { debug_malloc_touch(m); rehash(m, MAP_SLOTS(m->data->size)); @@ -1092,7 +1093,7 @@ PMOD_EXPORT void check_mapping_for_destruct(struct mapping *m) md->val_types = val_types; md->ind_types = ind_types;
- if(MAP_SLOTS(md->size) < md->hashsize * MIN_LINK_LENGTH) + if((md->hashsize > MIN_HASHSIZE) && (MAP_SLOTS(md->size) < md->hashsize * MIN_LINK_LENGTH)) { debug_malloc_touch(m); rehash(m, MAP_SLOTS(md->size));
On Sun, 4 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum wrote:
According to git bisect (and your testcase), the bug was introduced in commit 90314251db074fc740a2a2b01a9aca1939cd91a4.
Thanks for bisecting. The reason why my change triggered this one is that I somehow overlooked the fact that the previous hash size initialization had a minimum. I fixed that now.
On Sun, 4 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum wrote:
According to git bisect (and your testcase), the bug was introduced in commit 90314251db074fc740a2a2b01a9aca1939cd91a4.
Thanks for bisecting. The reason why my change triggered this one is that I somehow overlooked the fact that the previous hash size initialization had a minimum. I fixed that now.
It looks like your "fix" broke the testsuite:
| $ ./pike -mmaster.pike -x test_pike testsuite | Forked watchdog pid 21681. | Begin tests at Mon Sep 5 19:40:13 2011 (pid 21680) | Doing tests in testsuite (11333 tests) | /home/grubba/src/Pike/7.9/src/mapping.c:2366: Fatal error: | Pretty mean hashtable there buster 32 > 11 (2)! | Pretty mean hashtable there buster 32 > 11 (2)! | Backtrace at time of fatal: | testsuite:1: testsuite()->a() | /home/grubba/src/Pike/7.9/lib/modules/Tools.pmod/Standalone.pmod/test_pike.pike:1059: | Tools.Standalone.test_pike()->main(2,({"/home/grubba/src/Pike/7.9/lib/modu | les/Tools.pmod/Standalone.pmod/test_pike.pike","testsuite"})) | Abort (core dumped)
If I revert the "fix", it works again. It looks like the complaint is that there are too few keypairs allocated compared to the size of the hashtable.
On Mon, 5 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum wrote:
On Sun, 4 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum wrote:
According to git bisect (and your testcase), the bug was introduced in commit 90314251db074fc740a2a2b01a9aca1939cd91a4.
Thanks for bisecting. The reason why my change triggered this one is that I somehow overlooked the fact that the previous hash size initialization had a minimum. I fixed that now.
It looks like your "fix" broke the testsuite:
| $ ./pike -mmaster.pike -x test_pike testsuite | Forked watchdog pid 21681. | Begin tests at Mon Sep 5 19:40:13 2011 (pid 21680) | Doing tests in testsuite (11333 tests) | /home/grubba/src/Pike/7.9/src/mapping.c:2366: Fatal error: | Pretty mean hashtable there buster 32 > 11 (2)! | Pretty mean hashtable there buster 32 > 11 (2)! | Backtrace at time of fatal: | testsuite:1: testsuite()->a() | /home/grubba/src/Pike/7.9/lib/modules/Tools.pmod/Standalone.pmod/test_pike.pike:1059: | Tools.Standalone.test_pike()->main(2,({"/home/grubba/src/Pike/7.9/lib/modu | les/Tools.pmod/Standalone.pmod/test_pike.pike","testsuite"})) | Abort (core dumped)
If I revert the "fix", it works again. It looks like the complaint is that there are too few keypairs allocated compared to the size of the hashtable..
sigh, i should stay out of this. And there never was a minimum, just my bad reading of the old code. Sorry for that. Buster indeed.
On Mon, 5 Sep 2011, Arne Goedeke wrote:
It looks like your "fix" broke the testsuite:
| $ ./pike -mmaster.pike -x test_pike testsuite | Forked watchdog pid 21681. | Begin tests at Mon Sep 5 19:40:13 2011 (pid 21680) | Doing tests in testsuite (11333 tests) | /home/grubba/src/Pike/7.9/src/mapping.c:2366: Fatal error: | Pretty mean hashtable there buster 32 > 11 (2)! | Pretty mean hashtable there buster 32 > 11 (2)! | Backtrace at time of fatal: | testsuite:1: testsuite()->a() | /home/grubba/src/Pike/7.9/lib/modules/Tools.pmod/Standalone.pmod/test_pike.pike:1059: | Tools.Standalone.test_pike()->main(2,({"/home/grubba/src/Pike/7.9/lib/modu | les/Tools.pmod/Standalone.pmod/test_pike.pike","testsuite"})) | Abort (core dumped)
If I revert the "fix", it works again. It looks like the complaint is that there are too few keypairs allocated compared to the size of the hashtable..
sigh, i should stay out of this. And there never was a minimum, just my bad reading of the old code. Sorry for that. Buster indeed.
Ok, i reverted that commit. Sorry again.
pike-devel@lists.lysator.liu.se
-
Arne Goedeke -
Henrik Grubbstr�m (Lysator) ＠ Pike (-) developers forum -
Martin Nilsson (Opera Mini - AFK!) ＠ Pike (-) developers forum