After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 758078 - plugin: Dependency hash does not work with 32 or more files
plugin: Dependency hash does not work with 32 or more files
Product: GStreamer
Classification: Platform
Component: gstreamer (core)
git master
Other Linux
: Normal normal
: 1.7.1
Assigned To: GStreamer Maintainers
GStreamer Maintainers
Depends on:
Blocks: 758085
Reported: 2015-11-13 20:47 UTC by Nicolas Dufresne (ndufresne)
Modified: 2015-11-25 19:29 UTC
See Also:
GNOME target: ---
GNOME version: ---

plugin: Don't do lossy shift on hash (2.72 KB, patch)
2015-11-13 21:36 UTC, Nicolas Dufresne (ndufresne)
committed Details | Review

Description Nicolas Dufresne (ndufresne) 2015-11-13 20:47:44 UTC
A good example is frei0r. Remove /usr/lib64/frei0r-1/ and run gst-inspect again, the plugin is still listed (the cache is not invalidated).

The problem, is that the hash of each file is added and shift to the left.

  hash = (hash + fhash) << 1;

This shifting is also used at many other places. Passed 32 shift, the first item that was hash, no longer have weigth in the resulting hash.
Comment 1 Nicolas Dufresne (ndufresne) 2015-11-13 21:04:23 UTC
I'm coming from far, but I have the impression that this shift was meant to make the addition non-commutative. So if the orders of files changes, you'll get a different hash. If this is exact, the implementation is incorrect, you need to rotate the hash, that means saving the last bit, shifting, and adding back that bit.

Though, when I look at what it is doing, what we really care about is that hash, the order in which files are listed shall not matter. For this reason, I suggest to simply drop that shifting.
Comment 2 Sebastian Dröge (slomo) 2015-11-13 21:10:18 UTC
Just xor the hashes together :)
Comment 3 Nicolas Dufresne (ndufresne) 2015-11-13 21:36:03 UTC
Created attachment 315434 [details] [review]
plugin: Don't do lossy shift on hash

In plugin is responsible for calculating a hash of the dependencies
in order to determine if the cache should be invalidated or not.
Currently, the hash combining method removes a bit of the original
have before combining with an addition. As we use 32bits for our hash
and shift 1 bit for each file and directory, that resulting hash only
account for the last 32 files. And is more affected by the last file.

Rotating technique (shifting, and adding back the ending bit), can be
use to make the addition non-commutative. In a way that different order
gives different hashes. In this case, I don't preserve this behaviour
because the order in which the files are provided by the OS is

In most cases, the XOR operation is used to combine hashes. In this
code we use the addition. I decided to preserve the addition because
we make use of non-random hash ((guint) -1) in the algorithm for
matching files that are not really part of the hash (symlinks, special
files). Doing successive XOR on this value, will simply switch from
full ones, to full zero. The XOR used with whitelist has been preserved
as it's based on a fairly randomized hash (g_str_hash).
Comment 4 Nicolas Dufresne (ndufresne) 2015-11-25 19:28:23 UTC
Attachment 315434 [details] pushed as 446b3e6 - plugin: Don't do lossy shift on hash