caché de Firefox algoritmo de generación de clave hash error

Question

Hay a bug in Firefox (incluso en las versiones nuevas y en el campo de minas) que impide el almacenamiento en caché de ciertos archivos debido al algoritmo para crear una clave en su hash de caché. Here is a link to the source code of the function.

Quiero asegurarme de que todos los archivos de mi sitio puedan almacenarse en caché. Sin embargo, no entiendo por qué su función de hash no puede crear claves únicas para URL distintas. Espero que alguien pueda describir esta función mal en código psuedo o java.

Sería bueno crear una utilidad para los desarrolladores para garantizar direcciones URL únicas hasta que se solucione este error.

---

EDIT: Ha habido algunas respuestas muy útiles, sin embargo, necesito más ayuda paso a paso para crear una utilidad para comprobar si estas confusiones caché. Sería genial obtener algún código de Java que pueda reproducir las claves que Firefox está creando. Por lo tanto, la apertura de una recompensa en esta pregunta.

---

EDIT 2: Aquí es un puerto java parcialmente de trabajo (escrito usando processing). Tenga en cuenta las pruebas en la parte inferior; los primeros tres funcionan como se esperaba, pero los otros no. Sospecho algo con respecto a las entradas firmadas/sin firmar. Sugerencias?

// 
// 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 

} 

Answer 1

Aquí es cómo funciona el algoritmo:

initialize hash to 0 
for each byte 
    shift hash 4 bits to left (with rotate) 
    hash = hash XOR character 

visualmente (16 versión bits):

00110000    = '0' 
    00110001   = '1' 
     00110010  = '2' 
      00110011 = '3' 
0100   0011 = '4' 
00110101    = '5' 
==================== 
01000110001000010000 (and then this will be 'rotated' 
         so that it lines up with the end) 
giving: 
     00100001000001000110 

lo que esto significa es que si usted tiene cadenas de la misma longitud y son en su mayoría de la misma, a continuación, en al menos un caso, los 4 bits más bajos de un char y 4 bits superiores de el próximo char xor entre ellos debe ser único. Sin embargo, el método de pegar el número de 32 bits en una tabla podría ser cada vez más débil, lo que significa que requiere que el lower4 xor4 de una ubicación particular en la cadena (mod 8 chars) sea único.

Answer 2

Por lo que entiendo de sólo leer la entrada Bugzilla, el problema se manifiesta cuando se producen dos problemas distintos:

1. Su algoritmo de hash genera colisiones de direcciones URL que son "suficientemente similares". Desde el error "similar" parece significar que cada 4 caracteres (o tal vez 8) las URL son las mismas, y
2. Su lógica para lidiar con las colisiones hash falla porque no han limpiado la URL anterior con el mismo valor hash al disco todavía.

Así que, básicamente, si tiene una página con dos direcciones URL muy similares, esto podría ocurrir en algunas versiones de Firefox. Por lo general, no sucederá en páginas diferentes, supongo, ya que entonces FF tendrá tiempo para vaciar las entradas en el disco evitando el problema del tiempo.

Así que si tiene múltiples recursos (scripts, imágenes, etc.) que están cargados desde la misma página, asegúrese de que tengan una ejecución de 9 caracteres que son completamente diferentes. Una manera es posible asegurar esto es añadiendo una cadena de consulta (que se ignora) con un poco aleatoria de datos, algo así como:?

• http://foo.com/resource.jsr = dn # @ JdsK #

Answer 3

Primera , no puede hash únicamente todas las cadenas de enteros (obviamente, hay más cadenas que enteros (tamaño fijo), por lo que tiene que haber colisiones). Puede tener una tabla hash que pueda contener todos los conjuntos de datos (por ejemplo, todos sus archivos), pero para obtenerla, debe cambiar el código de la tabla hash, no la función hash.

En segundo lugar, veo un problema con la función hash informados, en esta parte:

PR_ROTATE_LEFT32(h, 4) 

Si lo que realmente hace la rotación de h (No he comprobado en esto), que gira por 4 significa que las cadenas que tienen dos partes de 8 bytes (supongo que hash de 32 bits) intercambiadas (por ejemplo, xxxxxxxxyyyyyyyy frente a yyyyyyyyxxxxxxxx) tendrán el hash igual. Si lo cambia a algo relativamente primos con el tamaño de hash (por ejemplo 5.), Esto sólo ocurrirá para las piezas intercambiadas de longitud 32.

Answer 4

Aparentemente está confundido con el error real. Claro, hay colisiones hash debido a la increíblemente mala elección de un algoritmo hash. Pero incluso hash (x) = 1 no causaría los problemas descritos. Simplemente convertiría una búsqueda O (1) en una búsqueda de lista enlazada O (N) a través del primer segmento.

El verdadero problema es que Firefox no se ocupa de las colisiones hash. Por lo tanto, requiere un hash perfecto de todas las URL. "Desafortunadamente, todas las URL" se encuentran fuera de su control.

Answer 5

Este error fue un problema importante para mi sitio: http://worldofsolitaire.com

trabajé alrededor de él hace mucho tiempo mediante el uso de una regla condicional en un archivo .htaccess que deshabilitar el almacenamiento en caché de imágenes en el sitio por los usuarios de Firefox . Esto era algo horrible que tenía que hacer, pero en ese momento no pude rastrear el error dentro de Firefox y hacer que el sitio sea un poco más lento es mejor que mostrar imágenes duplicadas/dañadas.

Cuando leí en el error vinculado que se había solucionado en los últimos lanzamientos de Firefox, cambié el condicional el 19 de abril de 2009 (ayer) para desactivar el almacenamiento en caché solo para los usuarios de Firefox 2.

Unas horas más tarde he recibido más de 10 correos electrónicos de usuarios de Firefox 3 (confirmados) de que estaban viendo imágenes duplicadas. Así que este problema es TODAVÍA un problema en Firefox 3.

Decidí crear un programa de prueba de Linux simple que me permitiera comprobar las URL para ver si están generando las mismas claves hash de caché.

recopilar en cualquier sistema Linux: g ++ -o ffgenhash ffgenhash.cpp

Aquí está el código (guardar en el archivo ffgenhash.CPP)

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

#define ULONG_MAX 0xFFFFFFFF 
#define PR_ROTATE_LEFT32(a, bits) (((a) << (bits)) | ((a) >> (32 - (bits)))) 

unsigned long ffgenhash(const char * key) 
{ 
    unsigned long h=0; 

    for(const unsigned char * s = (unsigned char *) key; *s != '\0'; ++s) 
    { 
     h = PR_ROTATE_LEFT32(h, 4)^*s; 
    } 

    return (h==0 ? ULONG_MAX : h); 
} 

int main(int argc, char ** argv) 
{ 
    printf("%d\n", ffgenhash(argv[1])); 
    return 0; 
} 

Como se puede ver, aquí hay dos URL de la vida real que generan la misma clave hash de la caché:

./ffgenhash "http://worldofsolitaire.com/decks/paris/5/12c.png" 
1087949033 
./ffgenhash "http://worldofsolitaire.com/decks/paris/5/13s.png" 
1087949033 

Desde que pre-cargar estas imágenes en un bucle Javascript, tratando de utilizar algún tipo de secuencia de comandos < > script vacía no es posible aquí.

De hecho, creo que mi única solución real es modificar las URL para los usuarios de Firefox de alguna manera para generar una clave de hash de caché única. Entonces ese es el enfoque que usaré. Por cierto, estoy medio tentado de crear una adición de Firebug que verifique todos los recursos cargados por un sitio y genere un gran error si dos recursos en el sitio comparten una clave hash común para que el desarrollador tenga conocimiento. Sería genial ejecutar sitios como Google maps a través de esto, ya que he visto cosas raras con esas imágenes en los últimos años :)

Answer 6

Esta es una versión modificada del generador hash de Sembiance que funciona correctamente incluso cuando se compila en 64- Plataforma de bits:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

#define ULONG_MAX 0xFFFFFFFF 
#define PR_ROTATE_LEFT32(a, bits) (((a) << (bits)) | ((a) >> (32 - (bits)))) 

unsigned int ffgenhash(const char * key) { 
    unsigned int h=0; 
    for(const unsigned char * s = (unsigned char *) key; *s != '\0'; ++s) { 
     h = PR_ROTATE_LEFT32(h, 4)^*s; 
    } 
    return (h==0 ? ULONG_MAX : h); 
} 

int main(int argc, char ** argv) { 
    printf("%u\n", ffgenhash(argv[1])); 
    return 0; 
}