StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POfirefox cache hash key generation algorithm bug
text
Body
copied!<p>There is <a href="https://bugzilla.mozilla.org/show_bug.cgi?id=355567#c28" rel="noreferrer">a bug in Firefox</a> (even in the new betas and in minefield releases) which prevents the caching of certain files because of the algorithm for creating a key in their cache hash. <a href="http://hg.mozilla.org/mozilla-central/annotate/e74b36d547de/netwerk/cache/src/nsDiskCacheDevice.cpp#l249" rel="noreferrer">Here is a link to the source code of the function</a>. </p> <p>I want to ensure that all of my site's files can be cached. However, I do not understand why their hashing function fails to create unique keys for distinct urls. I am hoping someone can describe this <em>mal</em>function in psuedo-code or java. </p> <p>It would be good to create a utility for developers to ensure unique urls until this bug is fixed.</p> <hr> <p><strong>EDIT:</strong> There have been some very helpful answers, however, I need more step-by-step help to create a utility to check for these cache mixups. It would be great to get some java code which can reproduce the keys that firefox is creating. Therefore, the opening of a bounty on this question.</p> <hr> <p><strong>EDIT 2:</strong> Here is a partially working java port (written using <a href="http://processing.org" rel="noreferrer">processing</a>). Note the tests at the bottom; the first three work as expected, but the others do not. I suspect something regarding signed / unsigned ints. Suggestions?</p> <pre><code>// // the bad collision function // http://mxr.mozilla.org/mozilla/source/netwerk/cache/src/nsDiskCacheDevice.cpp#240 // //248 PLDHashNumber //249 nsDiskCache::Hash(const char * key) //250 { //251 PLDHashNumber h = 0; //252 for (const PRUint8* s = (PRUint8*) key; *s != '\0'; ++s) //253 h = PR_ROTATE_LEFT32(h, 4) ^ *s; //254 return (h == 0 ? ULONG_MAX : h); //255 } // // a java port... // String getHash( String url ) { //get the char array for the url string char[] cs = getCharArray( url ); int h = 0; //for (const PRUint8* s = (PRUint8*) key; *s != '\0'; ++s) for ( int i=0; i < cs.length; i++ ) { h = PR_ROTATE_LEFT32(h, 4) ^ cs[i]; } //looks like the examples above return something in hex. //if we get matching ints, that is ok by me. //but for fun, lets try to hex the return vals? String hexVal = hex( h ); return hexVal; } char[] getCharArray( String s ) { char[] cs = new char[s.length()]; for (int i=0; i<s.length(); i++) { char c = s.charAt(i); cs[i] = c; } return cs; } // // how to PR_ROTATE_LEFT32 // //110 /* //111 ** Macros for rotate left and right. The argument 'a' must be an unsigned //112 ** 32-bit integer type such as PRUint32. //113 ** //114 ** There is no rotate operation in the C Language, so the construct //115 ** (a << 4) | (a >> 28) is frequently used instead. Most compilers convert //116 ** this to a rotate instruction, but MSVC doesn't without a little help. //117 ** To get MSVC to generate a rotate instruction, we have to use the _rotl //118 ** or _rotr intrinsic and use a pragma to make it inline. //119 ** //120 ** Note: MSVC in VS2005 will do an inline rotate instruction on the above //121 ** construct. //122 */ //... //128 #define PR_ROTATE_LEFT32(a, bits) _rotl(a, bits) //return an int (32 bit). what do we do with the 'bits' parameter? ignore? int PR_ROTATE_LEFT32( int a, int bits ) { return (a << 4) | (a >> (32-bits)); } // // examples of some colliding hashes // https://bugzilla.mozilla.org/show_bug.cgi?id=290032#c5 // //$ ./hashit "ABA/xxx.aba" //8ffac222 //$ ./hashit "XyZ/xxx.xYz" //8ffac222 //$ ./hashit "CSS/xxx.css" //8ffac222 //$ ./hashit "JPG/xxx.jpg" //8ffac222 //$ ./hashit modules_newsfeeds/MenuBar/MenuBar.css //15c23729 //$ ./hashit modules_newsfeeds/ListBar/ListBar.css //15c23729 //$ ./hashit modules_newsfeeds/MenuBar/MenuBar.js //a15c23e5 //$ ./hashit modules_newsfeeds/ListBar/ListBar.js //a15c23e5 // // our attempt at porting this algorithm to java... // void setup( ) { String a = "ABA/xxx.aba"; String b = "CSS/xxx.css"; String c = "CSS/xxx.css"; String d = "JPG/xxx.jpg"; println( getHash(a) ); //yes 8ffac222 println( getHash(b) ); //yes 8ffac222 println( getHash(c) ); //yes 8ffac222 println( getHash(d) ); //no [??] FFFFFF98, not 8ffac222 println( "-----" ); String e = "modules_newsfeeds/MenuBar/MenuBar.css"; String f = "modules_newsfeeds/ListBar/ListBar.css"; println( getHash(e) ); //no [??] FFFFFF8C, not 15c23729 println( getHash(f) ); //no [??] FFFFFF8C, not 15c23729 println( "-----" ); String g = "modules_newsfeeds/MenuBar/MenuBar.js"; String h = "modules_newsfeeds/ListBar/ListBar.js"; println( getHash(g) ); //yes [??] FFFFFF8C, not a15c23e5 println( getHash(h) ); //yes [??] FFFFFF8C, not a15c23e5 } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload