Peter Krempa <pkrempa(a)redhat.com&gt; [2017-08-02, 05:39PM +0200]: This does fix the issue on S390. Anyways, I'd also like to see the tests fixed that rely on the ordering of the hash table. And code that uses the hash table should be tested that it does NOT rely on the ordering. Tested-by: Bjoern Walk <bwalk(a)linux.vnet.ibm.com&gt;

Peter Krempa <pkrempa(a)redhat.com&gt; [2017-08-03, 09:47AM +0200]: No, the test is still dependent on the ordering. Just now the mocked hash table has deterministic ordering. This is not the same. Although it is improbable that this will bite us somewhere, I'd still prefer a clean solution. Yes, and I think it would be a good idea to test for this (no idea how to do this though). Like with all mocks, we now test a different version of code in the test suite. We test the code under the assumption that the hash table is ordered deterministically. However, the real code doesn't fulfill this assumption (rightly so, because ordering is not a property of the hash table). There's a discrepancy. For example, let's assume we have code that writes out an XML file from a hash table. We do this similar to the test code in testBlockNodeNameDetect. Writing a test against this will never fail, because we test against the mocked hash table. However, the actual code produces results that is dependent on the ordering. I know this is nitpicky, but if someone down the road runs into any problems with this it is nasty do understand. -- IBM Systems Linux on z Systems & Virtualization Development ------------------------------------------------------------------------ IBM Deutschland Schönaicher Str. 220 71032 Böblingen Phone: +49 7031 16 1819 E-Mail: bwalk(a)de.ibm.com ------------------------------------------------------------------------ IBM Deutschland Research & Development GmbH Vorsitzende des Aufsichtsrats: Martina Koederitz Geschäftsführung: Dirk Wittkopp Sitz der Gesellschaft: Böblingen Registergericht: Amtsgericht Stuttgart, HRB 243294

On 08/03/2017 04:50 AM, Peter Krempa wrote: NB: I didn't dig into the qemumonitorjsontest algorithm, but... While going through the common object changes, I ended up looking at and thinking about the hash table algorithms, initially it was just the "grow" algorithm as I think it is a bit "aggressive" (perhaps wasteful) since as soon as 1 bucket chain exceeds 8 elements, the table is resized by 8 unless the new size is 8 * 2048 - at which time no matter how full a bucket is we don't resize the table. The next thing I considered was using a prime number as the table bucket size and it seems by just doing that will cause qemumonitorjsontest to fail. Easy enough to reproduce by changing the virHashCreate call in qemuBlockNodeNameGetBackingChain to use 53 instead of 50 (even 49 causes failure). It doesn't matter if the test source also adjusts the initial hash size. Of course this makes sense given that virHashCodeGen is the backend of the virHashComputeKey algorithm that uses the return value % table->size. So if "size" changes, then obviously order changes. While I get the code bloat conundrum, but if the order doesn't matter then I wonder what other variables could change that would affect this test and whether we really want to be constantly altering the mocks "just" to get the right answer for this test. John

On 08/15/2017 02:01 PM, Peter Krempa wrote: Because if your hash function is stupid it can cluster all the keys together. Primes, however, have way fewer divisors, therefore clustering is harder to achieve. Of course, you can construct a hash function so that it's utterly stupid (e.g. {return 4;}) and then all of our optimizations are thrown out of the window. But I believe that using prime numbers for table size is advised in the literature too. Apparently, wiki mentions this fact too: https://en.wikipedia.org/wiki/Hash_table#Choosing_a_hash_function Michal

On Tue, Aug 15, 2017 at 03:03:07PM +0200, Michal Privoznik wrote: If your hash function has a problem with clustering, then you really should replace the hash function with a better one - which we already did a few years back now :-) Incidentally, we should replace our murmurhash funtion with siphash at some point, because people have found attacks against murmurhash, and so most devs have migrated over to siphash. Regards, Daniel [1] https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-do... -- |: https://berrange.com -o- https://www.flickr.com/photos/dberrange :| |: https://libvirt.org -o- https://fstop138.berrange.com :| |: https://entangle-photo.org -o- https://www.instagram.com/dberrange :|

On Tue, Aug 15, 2017 at 10:02:38AM -0400, John Ferlan wrote: For any sensible hash algorithm, such a "predictable" naming convention is not a realk problem - indeed if it were a problem it would be considered a security vulnerability these days. While murmurhash is not a cryptographic hash, a single bit difference in names should still produce a very different hashcode value. If we switch to siphash though, which is a cryptographic hash, we will have a strong guarantee of a completely different hash code for such names. So again I don't think bucket size is vs primes is important here - the choice of hash function more directly determines the collision resistance we have. Regards, Daniel -- |: https://berrange.com -o- https://www.flickr.com/photos/dberrange :| |: https://libvirt.org -o- https://fstop138.berrange.com :| |: https://entangle-photo.org -o- https://www.instagram.com/dberrange :|

On 08/15/2017 11:47 AM, Peter Krempa wrote: I really hadn't done any analysis, I was in the wondering stage and setting up the experiment. It's a part of the code I didn't know much about, so it was also a learning exercise. I never knew anything about murmurhash nor siphash before today! Got it. You asked a question, I answered. The only reason I used this particular patch to respond was because this particular test had an error result in my example and there was some concern over the deterministic results. The whole prime number thing is just one of those I recall using a prime number for the divisor in a hashing algorithm is considered better - in this case I hadn't considered the CodeGen half of the equation. It wasn't yet on the radar. Poorly chosen "random" word by me... Perhaps unexpected or larger than supplied value. We round up in various places for various reasons - doing the same with a supplied hash table size wouldn't be out of the question especially since we can "grow" to some larger value. In this case, I just happened to alter the size to next prime for both create and grow and fell down into this rabbit hole. Fair enough. I certainly don't want to spend my days characterizing the performance of various algorithms to alter the size of a hash table that has a hash algorithm that is distributing the elements rather evenly. I still ask myself is having 1 chain longer than 8 too few to cause a grow? And at what inflection point should a grow be done. John FWIW: Since it was simple enough, here's some mostly raw data adding 50K elems to a hash table that starts out with a size of 1. For every 1000 nbElems, I figured the number of empty buckets, the number of "full" buckets (e.g. more than 8 elems), and the longest chain as follows: When the name is "#blockN": nbElems=6000 size=4096, empty=955 full=1 longest=9 <== first "full" nbElems=10000 size=4096, empty=341 full=5 longest=12 nbElems=15000 size=4096, empty=96 full=43 longest=14 inflection nbElems=16000 size=4096, empty=77 full=68 longest=14 <== between full nbElems=17000 size=4096, empty=61 full=91 longest=14 and empty nbElems=18000 size=4096, empty=43 full=131 longest=14 nbElems=19000 size=4096, empty=36 full=181 longest=14 nbElems=20000 size=4096, empty=32 full=239 longest=15 nbElems=25000 size=4096, empty=9 full=637 longest=16 nbElems=30000 size=4096, empty=2 full=1287 longest=18 nbElems=40000 size=4096, empty=1 full=2649 longest=23 nbElems=50000 size=4096, empty=0 full=3508 longest=27 FWIW: Using an algorithm to have a prime "size" value divisor allows a higher maximum size of 5779 buckets and the first "full" shows up between 13K and 14K... Somewhere around 23K is the inflection between empty and full... At 50K elems we get empty=1 full=2873 longest=22 For a randomly generated UUID: nbElems=7000 size=4096, empty=736 full=1 longest=9 <== first "full" nbElems=10000 size=4096, empty=360 full=5 longest=10 nbElems=15000 size=4096, empty=121 full=50 longest=13 nbElems=16000 size=4096, empty=99 full=80 longest=13 inflection nbElems=17000 size=4096, empty=84 full=105 longest=13 <== between full nbElems=18000 size=4096, empty=69 full=137 longest=14 and empty nbElems=19000 size=4096, empty=55 full=177 longest=14 nbElems=20000 size=4096, empty=49 full=243 longest=14 nbElems=25000 size=4096, empty=13 full=649 longest=16 nbElems=30000 size=4096, empty=3 full=1276 longest=18 nbElems=40000 size=4096, empty=1 full=2634 longest=21 nbElems=50000 size=4096, empty=0 full=3513 longest=26 FWIW: Using the prime size algorithm... Between 9K and 10K we get our first full, somewhere around 22K to 23K we get the inflection between empty and full, and at 50K elems we get empty=2 full=2903 longest=22. So the prime number does effect things a bit, but it doesn't really seem to be significant. Next, I started to tinker with the thought that perhaps not increasing the size as soon as we get 1 bucket longer than 8 elems, but rather trying to only grow when say 10% of the buckets were full or if any one bucket had more than 16 elems and not have a cap to size as well as perhaps growing the buckets more slowly once you reach certain nbElems. For the #blockN's: nbElems=10000 size=2459, empty=46 full=62 longest=14 nbElems=15000 size=3079, empty=19 full=164 longest=15 nbElems=20000 size=6029, empty=209 full=43 longest=12 nbElems=25000 size=7537, empty=273 full=52 longest=14 nbElems=30000 size=7537, empty=130 full=156 longest=15 nbElems=40000 size=9421, empty=140 full=282 longest=15 nbElems=50000 size=11777, empty=151 full=363 longest=15 @19507 elems is when we grow from 4813 to 6029 buckets @21288 elems is when we grow from 6029 to 7537 buckets @30203 elems is when we grow from 7537 to 9421 buckets @46589 elems is when we grow from 9421 to 11777 buckets For the UUID's: nbElems=10000 size=2459, empty=38 full=65 longest=13 nbElems=15000 size=3079, empty=24 full=172 longest=15 nbElems=20000 size=4813, empty=80 full=133 longest=16 nbElems=25000 size=4813, empty=27 full=412 longest=16 nbElems=30000 size=6029, empty=47 full=426 longest=15 nbElems=40000 size=9421, empty=120 full=292 longest=15 nbElems=50000 size=11777, empty=174 full=380 longest=15 @25078 elems is when we grow from 4813 to 6029 buckets @30409 elems is when we grow from 6029 to 7537 buckets @35473 elems is when we grow from 7537 to 9421 buckets @41512 elems is when we grow from 9421 to 11777 buckets FWIW: For this round I also tracked the number of items in various buckets when a resize occurred... It was a fairly standard deviation with the largest number of buckets having 4-7 elements in their chains. Furthermore the number of buckets with more than 10 elements was minimal. That made me wonder if we shouldn't grow unless there was more than perhaps 16 elems in a bucket... Taking that approach grows the table beyond 4096 buckets only when at greater than 26K elements. Space vs. time... We're not even close to needing 10's of thousands yet, but it was to a degree an interesting exercise.

On 08/02/2017 10:39 AM, Peter Krempa wrote: Series: Reviewed-by: Eric Blake <eblake(a)redhat.com&gt; -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org