Add support for much faster hash algorithms (e.g. xxHash)

[rico-chet]

Currently, SCons only supports hash algorithms which are provided by the hashlib, but those are rather slow (in the ballpark of 1-2 GB/s).

There are much faster alternatives available, e.g. xxHash which runs at the speed of RAM (an order of magnitude faster than MD5, up to ~30 times, according to xxHash developers). xxHash is readily available as a C and Python3 library via Debian repositories, so e.g. Ubuntu/Debian users can install it with ease. The hash is not cryptographic, but it's acceptable according to the comments I found in SCons code.

[bdbaddog]

I've moved this to a discussion.

If you've read the docs, SCons thus far hasn't required any other packages besides what's in the python distribution to run.
Thus the current limitation.

Feel free to develop this in the scons-contrib repo if you'd like to see if you can get this working with SCons.

[rico-chet]

I get that SCons shouldn't impose such an exotic library as a dependency on its users, but what about it being a soft dependency, i.e. only be used when present? It would correspond to a suggested package in Debian parlance.

In the code I saw, there was a certain level of coupling to the hashlib which I didn't immediately grasped, so I didn't pursue it, in favor of another topics (which are done now). I'll see if I can find some time to bring it on.

[mwichmann]

We'd need to get more clever... what if several devs share a build tree or a cachedir, and one of them installs xxhash in their environment. Now everything she writes will be using xxhash signatures, and the other devs will have their builds break because their run of scons won't recognize those. At the least, we'd want to switch to a multihash scheme so scons could recognize the kind of hash and emit a sane message if it's one it can't deal with at that time.

[rico-chet]

Wouldn't such issues arise today when state is shared between FIPS-compliant (MD5) and FIPS-incompliant (SHA*) environments? Or even when a group member explicily chooses the hash algorithm (e.g. because they want to use hardware-accelerated SHA on their new machine)?

[rico-chet]

A rough sketch can be found here https://github.com/rico-chet/scons/commits/add-xxhash-support.
It prioritizes xxhash when available, saving half a second per GB of input+output data (without a cache dir, on my machine).

[rico-chet]

This might start with providing boilerplate code which users can integrate into their SConstruct files to boost their builds. It's not easy though because unlike documented, SCons.Util.hashes.set_hash_format() does not support hashlib_used value other than hashlib.

E.g. this should work (but doesn't):

import SCons.Util as scons_util
import xxhash

scons_util.set_hash_format('xxh128', xxhash)

https://scons.org/doc/latest/HTML/scons-api/SCons.Util#SCons.Util.hashes.set_hash_format

[mwichmann]

you have to get it into ALLOWED_HASH_FORMATS somehow

[rico-chet]

Adding a scons_util.ALLOWED_HASH_FORMATS.append("xxh128") brings me further but the faulty special handling for Python 3.9+ makes me hit the wall, i.e. to have to modify SCons.

SCons expects all hash libraries to add an argument when run under Python 3.9+:

scons/SCons/Util/hashes.py

Line 57 in ebf4678

return hash_function_object(usedforsecurity=False)

which raises a TypeError because the argument is absent with XXHash (and it makes no sense there).

[mwichmann]

That story was kind of weird - we got some complaints that if you ran SCons in a FIPS-compliant environment (essentially, RHEL in a US-Govt setting), it failed because md5 was disabled in Python by policy. SCons doesn't use the hash for any cryptographic purpose, only for hashing. After adding other hash options than md5, a contributor figured out that Python as of 3.9 had added the option to declare that, with the new usedforsecurity argument, and so made it possible for SCons to use that. If the xxhash Python interface doesn't accept that argument, it's not conforming to current hashlib behavior - which nobody can force it to, since it's an external package, but it would be better if it did, for compatibility.

[ListsOfArrays]

Yup. I'm on my alt, but the TLDR was in order to get SCons to work in FIPS mode I implemented the weird patch in #4047 .

I haven't touched SCons in a while, but if you add the new hash to the first element of the list, then it should work in order of preference from most preferred to least preferred. Iirc I set it to implement md5 first 'cause that's how it was originally implemented, and if that failed then it switches to SHA1 and then SHA2-256.

[jcassagnol-public]

I'm back :D

[mwichmann]

Is there anything here we {could,should} improve?

[ListsOfArrays]

I'm sorry October and September have been a super busy month. I can check tonight. 😅

[jcassagnol-public]

@rico-chet

Ok I'm back on my primary account 😂

Looking at the code, I do recommend you review #4047 : there's sections of the code that (assuming they're still the same) that you haven't patched to support the new hash algorithm. The good news is that most of the PR was spent fixing cases where the unit tests had accidental hardcoded dependencies on the .sconsign format... so most of those changes won't be needed in your PR.

When I integrated SHA I added a .sconsign_<alg> extension format for the new hashes. In theory, using the .sconsign_<alg> format it shouldn't break a current install (the .sconsign file is currently set as md5 and if we alter the contents folks expecting md5 won't "break" but will auto-rebuild everything I think -> two people sharing the same checkout would force each other to rebuild every time). If you add in your custom .sconsign_xx128 file it shouldn't break a currently existent build (the build should add extra .sconsign_xx128 files but the original .sconsign files will remain for md5 builds).

The other thing is once you do that... it's a good idea to also integrate into the test cases modified by #4047 . Those testcases test for implicit fallback to SHA currently, but it's a similar mocking structure when you want to test for implicit fallback of xx hashing.

When I implemented my first pass of #4047 ... I actually did the same thing: only integrated in the one point. When I started poking in the code I was surprised actually by how little I needed to change in the primary repo (38 files in a project as big as SCons... was a win LOL).

Poke me if you need any additional tips!

[mwichmann]

Unrelated other than that looking at this again took me there:
Ugh, the doc entry comes out ugly, Sphinx is expanding and providing more information:

SCons.Util.hashes.set_hash_format(hash_format, hashlib_used=<module 'hashlib' from '/opt/local/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/hashlib.py'>, sys_used=<module 'sys' (built-in)>)

would have been preferable to just leave at hashlib_used=hashlib, sys_used=sys. Not sure how to force that.

[mwichmann]

So a few questions at the edges:

• If the developer requests xxhash, and it's not available, is that a fatal error or would you fall back to an available format?
• "xxhash is used if support found" seems palatable, but what do you do if the project is set up in a virtualenv and the user forgets to use the virtualenv? SCons doesn't currently look for an sconsign in a format that the algorithm/arguments have not selected, so they coexist completely independently. That's great for testing, but would the ordinary use case want to let you know there's an unusual situation?
• It's too bad the momentum for using multihashes didn't go anywhere. It would be a lot nicer if the hash itself encoded the hash format so we don't have to play this file-switching dance (that's not specific to xxhash being added, but xxhash as optional seems to increase the chance of dfferent hashes being in use). The IPFS folks were really hot on this, but the scheme never made it beyond an IETF draft and the implementations seem to have been largely abandoned (search multihash on PyPi - I used this library 8 or so years ago but there have been no updates for 10 and the github project is gone).
• We still have vauge plans to actually use a database for what's called the "signature database" though it's only a flat file of pickles. Further propagating different files with different hash styles doesn't make this any easier.

These may be too nitpicky to worry about a lot but wanted to get people thinking about it.

[bdbaddog]

I think if the user explicitly requests something which is not available, that should be a "fatal" error and exit with message.
If scons is just walking the default options and one isn't' available, then no need to error, and likely not even worth messaging.. unless the existing SConstruct used a hash not available.