Harden hashes against hash seed discovery by randomizing hash iteration

Adds:

S_ptr_hash() - A new static function in hv.c which can be used to
hash a pointer or integer.

PL_hash_rand_bits - A new interpreter variable used as a cheap
provider of "semi-random" state for use by the hash infrastructure.

xpvhv_aux.xhv_rand - Used as a mask which is xored against the
xpvhv_aux.riter during iteration to randomize the order the actual
buckets are visited.

PL_hash_rand_bits is initialized as interpreter start from the random
hash seed, and then modified by "mixing in" the result of ptr_hash()
on the bucket array pointer in the hv (HvARRAY(hv)) every time
hv_auxinit() allocates a new iterator structure.

The net result is that every hash has its own iteration order, which
should make it much more difficult to determine what the current hash
seed is.

This required some test to be restructured, as they tested for something
that was not necessarily true, we never guaranteed that two hashes with
the same keys would produce the same key order, we merely promised that
using keys(), values(), or each() on the same hash, without any
insertions in between, would produce the same order of visiting the
key/values.

1 files changed, 43 insertions, 18 deletions

diff --git a/t/op/smartkve.t b/t/op/smartkve.t
index 7e5d67e7c1..abd6abfd53 100644
--- a/t/op/smartkve.t
+++ b/t/op/smartkve.t
@@ -23,12 +23,19 @@ sub j { join(":",@_) }
 # match the inserted order. So we declare one hash
 # and then make all our copies from that, which should
 # mean all the copies have the same internal structure.
+#
+# And these days, even if all that weren't true, we now
+# per-hash randomize keys/values. So, we cant expect two
+# hashes with the same internal structure to return the
+# same thing at all. All we *can* expect is that keys()
+# and values() use the same ordering.
 our %base_hash;
 
 BEGIN { # in BEGIN for "use constant ..." later
-  %base_hash= (  pi => 3.14, e => 2.72, i => -1 );
+  # values match keys here so we can easily check that keys(%hash) == values(%hash)
+  %base_hash= (  pi => 'pi', e => 'e', i => 'i' );
   $array = [ qw(pi e i) ];
-  $values = [ 3.14, 2.72, -1 ];
+  $values = [ qw(pi e i) ];
   $hash  = { %base_hash } ;
   $data = {
     hash => { %base_hash },
@@ -118,16 +125,25 @@ is(keys $obj->array     ,3, 'Scalar: keys $obj->array');
 
 # Keys -- list
 
-$h_expect = j(keys %$hash);
+$h_expect = j(sort keys %base_hash);
 $a_expect = j(keys @$array);
 
-is(j(keys $hash)                ,$h_expect, 'List: keys $hash');
-is(j(keys $data->{hash})        ,$h_expect, 'List: keys $data->{hash}');
-is(j(keys CONST_HASH)           ,$h_expect, 'List: keys CONST_HASH');
-is(j(keys CONST_HASH())         ,$h_expect, 'List: keys CONST_HASH()');
-is(j(keys hash_sub)             ,$h_expect, 'List: keys hash_sub');
-is(j(keys hash_sub())           ,$h_expect, 'List: keys hash_sub()');
-is(j(keys $obj->hash)           ,$h_expect, 'List: keys $obj->hash');
+is(j(sort keys $hash)           ,$h_expect, 'List: sort keys $hash');
+is(j(sort keys $data->{hash})   ,$h_expect, 'List: sort keys $data->{hash}');
+is(j(sort keys CONST_HASH)      ,$h_expect, 'List: sort keys CONST_HASH');
+is(j(sort keys CONST_HASH())    ,$h_expect, 'List: sort keys CONST_HASH()');
+is(j(sort keys hash_sub)        ,$h_expect, 'List: sort keys hash_sub');
+is(j(sort keys hash_sub())      ,$h_expect, 'List: sort keys hash_sub()');
+is(j(sort keys $obj->hash)      ,$h_expect, 'List: sort keys $obj->hash');
+
+is(j(keys $hash)                ,j(values $hash),           'List: keys $hash == values $hash');
+is(j(keys $data->{hash})        ,j(values $data->{hash}),   'List: keys $data->{hash} == values $data->{hash}');
+is(j(keys CONST_HASH)           ,j(values CONST_HASH),      'List: keys CONST_HASH == values CONST_HASH');
+is(j(keys CONST_HASH())         ,j(values CONST_HASH()),    'List: keys CONST_HASH() == values CONST_HASH()');
+is(j(keys hash_sub)             ,j(values hash_sub),        'List: keys hash_sub == values hash_sub');
+is(j(keys hash_sub())           ,j(values hash_sub()),      'List: keys hash_sub() == values hash_sub()');
+is(j(keys $obj->hash)           ,j(values $obj->hash),      'List: keys $obj->hash == values obj->hash');
+
 is(j(keys $array)               ,$a_expect, 'List: keys $array');
 is(j(keys $data->{array})       ,$a_expect, 'List: keys $data->{array}');
 is(j(keys CONST_ARRAY)          ,$a_expect, 'List: keys CONST_ARRAY');
@@ -221,16 +237,25 @@ is(values $obj->array     ,3, 'Scalar: values $obj->array');
 
 # Values -- list
 
-$h_expect = j(values %$hash);
+$h_expect = j(sort values %base_hash);
 $a_expect = j(values @$array);
 
-is(j(values $hash)                ,$h_expect, 'List: values $hash');
-is(j(values $data->{hash})        ,$h_expect, 'List: values $data->{hash}');
-is(j(values CONST_HASH)           ,$h_expect, 'List: values CONST_HASH');
-is(j(values CONST_HASH())         ,$h_expect, 'List: values CONST_HASH()');
-is(j(values hash_sub)             ,$h_expect, 'List: values hash_sub');
-is(j(values hash_sub())           ,$h_expect, 'List: values hash_sub()');
-is(j(values $obj->hash)           ,$h_expect, 'List: values $obj->hash');
+is(j(sort values $hash)                ,$h_expect, 'List: sort values $hash');
+is(j(sort values $data->{hash})        ,$h_expect, 'List: sort values $data->{hash}');
+is(j(sort values CONST_HASH)           ,$h_expect, 'List: sort values CONST_HASH');
+is(j(sort values CONST_HASH())         ,$h_expect, 'List: sort values CONST_HASH()');
+is(j(sort values hash_sub)             ,$h_expect, 'List: sort values hash_sub');
+is(j(sort values hash_sub())           ,$h_expect, 'List: sort values hash_sub()');
+is(j(sort values $obj->hash)           ,$h_expect, 'List: sort values $obj->hash');
+
+is(j(values $hash)                ,j(keys $hash),           'List: values $hash == keys $hash');
+is(j(values $data->{hash})        ,j(keys $data->{hash}),   'List: values $data->{hash} == keys $data->{hash}');
+is(j(values CONST_HASH)           ,j(keys CONST_HASH),      'List: values CONST_HASH == keys CONST_HASH');
+is(j(values CONST_HASH())         ,j(keys CONST_HASH()),    'List: values CONST_HASH() == keys CONST_HASH()');
+is(j(values hash_sub)             ,j(keys hash_sub),        'List: values hash_sub == keys hash_sub');
+is(j(values hash_sub())           ,j(keys hash_sub()),      'List: values hash_sub() == keys hash_sub()');
+is(j(values $obj->hash)           ,j(keys $obj->hash),      'List: values $obj->hash == keys $obj->hash');
+
 is(j(values $array)               ,$a_expect, 'List: values $array');
 is(j(values $data->{array})       ,$a_expect, 'List: values $data->{array}');
 is(j(values CONST_ARRAY)          ,$a_expect, 'List: values CONST_ARRAY');