2 * Bloom filter tracking which scores are present in our arenas
3 * and (more importantly) which are not.
11 bloominit(Bloom *b, vlong vsize, u8int *data)
16 if(size != vsize){ /* truncation */
17 werrstr("bloom data too big");
22 b->nhash = 32; /* will be fixed by caller on initialization */
24 if(unpackbloomhead(b, data) < 0)
35 packbloomhead(b, b->data);
48 b = vtmallocz(sizeof *b);
49 if(readpart(p, 0, buf, sizeof buf) < 0)
51 if(bloominit(b, 0, buf) < 0){
55 data = vtmallocz(b->size);
56 if(readpart(p, 0, data, b->size) < 0){
68 ones += countbits(a[i]);
69 addstat(StatBloomOnes, ones);
71 if(b->size == MaxBloomSize) /* 2^32 overflows ulong */
72 addstat(StatBloomBits, b->size*8-1);
74 addstat(StatBloomBits, b->size*8);
83 return writepart(b->part, 0, b->data, b->size);
87 * Derive two random 32-bit quantities a, b from the score
88 * and then use a+b*i as a sequence of bloom filter indices.
89 * Michael Mitzenmacher has a recent (2005) paper saying this is okay.
90 * We reserve the bottom bytes (BloomHeadSize*8 bits) for the header.
93 gethashes(u8int *score, ulong *h)
100 for(i=4; i+8<=VtScoreSize; i+=8){
101 a ^= *(u32int*)(score+i);
102 b ^= *(u32int*)(score+i+4);
104 if(i+4 <= VtScoreSize) /* 20 is not 4-aligned */
105 a ^= *(u32int*)(score+i);
106 for(i=0; i<BloomMaxHash; i++, a+=b)
107 h[i] = a < BloomHeadSize*8 ? BloomHeadSize*8 : a;
111 _markbloomfilter(Bloom *b, u8int *score)
114 ulong h[BloomMaxHash];
115 u32int x, *y, z, *tab;
117 trace("markbloomfilter", "markbloomfilter %V", score);
120 tab = (u32int*)b->data;
121 for(i=0; i<b->nhash; i++){
123 y = &tab[(x&b->mask)>>5];
131 addstat(StatBloomOnes, nnew);
133 trace("markbloomfilter", "markbloomfilter exit");
137 _inbloomfilter(Bloom *b, u8int *score)
140 ulong h[BloomMaxHash], x;
144 tab = (u32int*)b->data;
145 for(i=0; i<b->nhash; i++){
147 if(!(tab[(x&b->mask)>>5] & (1<<(x&31))))
154 inbloomfilter(Bloom *b, u8int *score)
164 r = _inbloomfilter(b, score);
167 addstat2(StatBloomLookup, 1, StatBloomLookupTime, ms);
169 addstat(StatBloomMiss, 1);
171 addstat(StatBloomHit, 1);
176 markbloomfilter(Bloom *b, u8int *score)
183 _markbloomfilter(b, score);
189 bloomwriteproc(void *v)
195 recv(b->writechan, 0);
196 if(writebloom(b) < 0)
197 fprint(2, "oops! writing bloom: %r\n");
198 send(b->writedonechan, 0);
203 startbloomproc(Bloom *b)
205 b->writechan = chancreate(sizeof(void*), 0);
206 b->writedonechan = chancreate(sizeof(void*), 0);
207 vtproc(bloomwriteproc, b);