Thuật toán tạo khóa băm trong bộ nhớ cache của firefox

Question

Có a bug in Firefox (ngay cả trong bản beta mới và trong bản phát hành mỏ) ngăn chặn bộ nhớ đệm của một số tệp nhất định vì thuật toán tạo khóa trong băm bộ nhớ cache của chúng. Here is a link to the source code of the function.

Tôi muốn đảm bảo rằng tất cả các tệp trên trang web của tôi có thể được lưu vào bộ nhớ cache. Tuy nhiên, tôi không hiểu tại sao hàm băm của họ không tạo được khóa duy nhất cho các url riêng biệt. Tôi hy vọng ai đó có thể mô tả hàm này mal trong mã psuedo hoặc java.

Sẽ rất hữu ích khi tạo tiện ích cho nhà phát triển để đảm bảo url duy nhất cho đến khi lỗi này được khắc phục.

---

EDIT: Đã có một số câu trả lời rất hữu ích, tuy nhiên, tôi cần thêm bước-by-step giúp đỡ để tạo ra một tiện ích để kiểm tra những mixups cache. Nó sẽ là tuyệt vời để có được một số mã java mà có thể sao chép các phím mà firefox đang tạo ra. Do đó, việc mở một tiền thưởng cho câu hỏi này.

---

EDIT 2: Đây là một cổng java làm việc một phần (viết bằng processing). Lưu ý các bài kiểm tra ở phía dưới; ba công việc đầu tiên như mong đợi, nhưng những người khác thì không. Tôi nghi ngờ một cái gì đó liên quan đến ints ký/unsigned. Gợi ý?

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

Sau đây là cách các thuật toán hoạt động:

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

trực quan (16 -bit phiên bản):

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 

Điều này có nghĩa là nếu bạn có các chuỗi có cùng chiều dài và hầu hết là giống nhau, sau đó trong ít nhất một trường hợp, thấp hơn 4 bit của một char và trên 4 bit char xor tiếp theo phải là duy nhất. Tuy nhiên, phương pháp gắn số 32 bit vào một bảng có thể yếu hơn, nghĩa là nó yêu cầu lower4 xor upper4 của một vị trí cụ thể trong chuỗi (mod 8 chars) là duy nhất.

Answer 2

Từ những gì tôi hiểu chỉ đọc entry bugzilla, lỗi biểu hiện khi hai vấn đề riêng biệt xảy ra:

1. thuật toán hash của họ tạo ra va chạm cho các url mà là "đủ tương tự". Từ lỗi "tương tự đủ" có nghĩa là mỗi 4 ký tự (hoặc có thể là 8) các url giống nhau, và
2. Logic của chúng để xử lý các xung đột băm không thành công vì chúng chưa xóa url trước đó với cùng giá trị băm vào đĩa.

Về cơ bản, nếu bạn có một trang có hai url rất giống nhau, điều này có thể xảy ra trên một số phiên bản của Firefox. Nó thường sẽ không xảy ra trên các trang khác nhau, tôi sẽ mong đợi, kể từ đó FF sẽ có thời gian để tuôn ra các mục vào đĩa tránh vấn đề thời gian.

Vì vậy, nếu bạn có nhiều tài nguyên (tập lệnh, hình ảnh, v.v.) được tải từ cùng một trang, hãy đảm bảo chúng có 9 ký tự hoàn toàn khác nhau. Một cách để bạn có thể đảm bảo điều này là bằng cách thêm một chuỗi truy vấn (mà bạn bỏ qua) với một chút ngẫu nhiên của dữ liệu, một cái gì đó như:

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

Answer 3

Đầu tiên , bạn không thể băm duy nhất tất cả các chuỗi thành số nguyên (rõ ràng, có nhiều chuỗi hơn (kích thước cố định) số nguyên, do đó, phải có va chạm). Bạn có thể có một hashtable có thể chứa tất cả các bộ dữ liệu (ví dụ: tất cả các tệp của bạn), nhưng để có được nó, bạn cần phải thay đổi mã của hashtable, không phải là hàm băm.

Thứ hai, tôi thấy một vấn đề với chức năng băm bạn được đăng, trong phần này:

PR_ROTATE_LEFT32(h, 4) 

Nếu nó thực sự quay của h (tôi đã không kiểm tra về vấn đề này), xoay 4 phương tiện đó các chuỗi có hai phần 8 byte (tôi giả định 32 bit băm) được hoán đổi (ví dụ: xxxxxxxxyyyyyyyy so với yyyyyyyyxxxxxxxx) sẽ có băm bằng nhau. Nếu bạn thay đổi nó một cái gì đó tố cùng nhau với kích thước băm (ví dụ 5.), Điều này sẽ chỉ xảy ra cho các bộ phận đổi chiều dài 32.

Answer 4

Có vẻ như bạn đã nhầm lẫn về lỗi thực sự. Chắc chắn, có những va chạm băm do sự lựa chọn không đáng ngờ xấu của một thuật toán băm. Nhưng ngay cả hash (x) = 1 sẽ không gây ra các vấn đề được mô tả. Nó sẽ chỉ biến một tra cứu O (1) thành một tìm kiếm danh sách được liên kết với O (N) thông qua nhóm đầu tiên.

Vấn đề thực sự là Firefox không xử lý được các xung đột băm. Do đó, nó đòi hỏi một băm hoàn hảo của tất cả các URL. "Tất cả URL" không may là một bộ ngoài tầm kiểm soát của bạn.

Answer 5

Lỗi này là một vấn đề lớn đối với trang web của tôi: http://worldofsolitaire.com

tôi làm việc xung quanh nó một thời gian dài trước đây bằng cách sử dụng một quy tắc có điều kiện trong một tập tin .htaccess sẽ vô hiệu hóa tất cả bộ nhớ đệm của hình ảnh trên trang web cho người dùng Firefox . Đây là một điều khủng khiếp cần phải làm, nhưng vào thời điểm đó tôi không thể theo dõi lỗi trong Firefox và việc trang web hơi chậm hơn là hiển thị hình ảnh bị trùng lặp/bị hỏng.

Khi tôi đọc trong lỗi được liên kết đã được sửa trong bản phát hành Firefox mới nhất, tôi đã thay đổi điều kiện vào ngày 19 tháng 4 năm 2009 (ngày hôm qua) để chỉ vô hiệu bộ nhớ đệm cho người dùng Firefox 2.

Một vài giờ sau, tôi đã nhận được hơn 10 e-mail từ người dùng Firefox 3 (đã xác nhận) rằng họ đã nhìn thấy hình ảnh trùng lặp. Vì vậy, vấn đề này là STILL một vấn đề trong Firefox 3.

Tôi quyết định tạo một chương trình thử nghiệm Linux đơn giản cho phép tôi kiểm tra URL để xem chúng có tạo ra các khóa băm bộ nhớ cache giống nhau hay không.

Để biên dịch trong bất kỳ hệ thống Linux: g ++ -o ffgenhash ffgenhash.cpp

Đây là mã (save to file 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; 
} 

Như bạn có thể thấy, đây là hai thực tế đời sống của URL mà tạo ra cùng một khóa bộ nhớ cache băm:

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

Vì tôi trước tải những hình ảnh này trong một vòng lặp Javascript, cố gắng sử dụng một số loại trống rỗng <script> không thể thực hiện được ở đây.

Thật vậy, tôi nghĩ giải pháp thực sự duy nhất của tôi là sửa đổi URL cho người dùng Firefox theo cách nào đó để tạo khóa băm bộ nhớ cache duy nhất. Vì vậy, đó là cách tiếp cận tôi sẽ sử dụng.

Nhân tiện, tôi bị cám dỗ khi tạo một bản bổ sung Firebug sẽ kiểm tra tất cả các tài nguyên được tải bởi một trang web và đưa ra một lỗi lớn nếu hai tài nguyên trên trang chia sẻ một khóa băm thông thường để nhà phát triển biết. Nó sẽ là tuyệt vời để chạy các trang web như Google bản đồ thông qua này như tôi đã nhìn thấy những điều kỳ lạ với những hình ảnh trong vài năm qua :)

Answer 6

Đây là phiên bản sửa đổi của máy phát băm Sembiance hoạt động chính xác ngay cả khi biên dịch trên 64- nền tảng bit:

#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; 
}