2 a0d146ed 2005-07-12 devnull * Bloom filter tracking which scores are present in our arenas
3 a0d146ed 2005-07-12 devnull * and (more importantly) which are not.
6 a0d146ed 2005-07-12 devnull #include "stdinc.h"
7 a0d146ed 2005-07-12 devnull #include "dat.h"
8 a0d146ed 2005-07-12 devnull #include "fns.h"
11 a0d146ed 2005-07-12 devnull bloominit(Bloom *b, vlong vsize, u8int *data)
13 a0d146ed 2005-07-12 devnull ulong size;
15 a0d146ed 2005-07-12 devnull size = vsize;
16 a0d146ed 2005-07-12 devnull if(size != vsize){ /* truncation */
17 a0d146ed 2005-07-12 devnull werrstr("bloom data too big");
18 a0d146ed 2005-07-12 devnull return -1;
21 a0d146ed 2005-07-12 devnull b->size = size;
22 a0d146ed 2005-07-12 devnull b->nhash = 32; /* will be fixed by caller on initialization */
23 a0d146ed 2005-07-12 devnull if(data != nil)
24 a0d146ed 2005-07-12 devnull if(unpackbloomhead(b, data) < 0)
25 a0d146ed 2005-07-12 devnull return -1;
27 a0d146ed 2005-07-12 devnull b->mask = b->size-1;
28 a0d146ed 2005-07-12 devnull b->data = data;
29 a0d146ed 2005-07-12 devnull return 0;
33 a0d146ed 2005-07-12 devnull wbbloomhead(Bloom *b)
35 a0d146ed 2005-07-12 devnull packbloomhead(b, b->data);
39 a0d146ed 2005-07-12 devnull readbloom(Part *p)
41 a0d146ed 2005-07-12 devnull int i, n;
42 a0d146ed 2005-07-12 devnull uint ones;
43 a0d146ed 2005-07-12 devnull uchar buf[512];
44 a0d146ed 2005-07-12 devnull uchar *data;
45 a0d146ed 2005-07-12 devnull u32int *a;
46 a0d146ed 2005-07-12 devnull Bloom *b;
48 a0d146ed 2005-07-12 devnull b = vtmallocz(sizeof *b);
49 a0d146ed 2005-07-12 devnull if(readpart(p, 0, buf, sizeof buf) < 0)
50 a0d146ed 2005-07-12 devnull return nil;
51 a0d146ed 2005-07-12 devnull if(bloominit(b, 0, buf) < 0){
52 a0d146ed 2005-07-12 devnull vtfree(b);
53 a0d146ed 2005-07-12 devnull return nil;
55 a0d146ed 2005-07-12 devnull data = vtmallocz(b->size);
56 a0d146ed 2005-07-12 devnull if(readpart(p, 0, data, b->size) < 0){
57 a0d146ed 2005-07-12 devnull vtfree(b);
58 a0d146ed 2005-07-12 devnull vtfree(data);
59 a0d146ed 2005-07-12 devnull return nil;
61 a0d146ed 2005-07-12 devnull b->data = data;
62 a0d146ed 2005-07-12 devnull b->part = p;
64 a0d146ed 2005-07-12 devnull a = (u32int*)b->data;
65 a0d146ed 2005-07-12 devnull n = b->size/4;
66 a0d146ed 2005-07-12 devnull ones = 0;
67 a0d146ed 2005-07-12 devnull for(i=0; i<n; i++)
68 a0d146ed 2005-07-12 devnull ones += countbits(a[i]);
69 a0d146ed 2005-07-12 devnull addstat(StatBloomOnes, ones);
71 a0d146ed 2005-07-12 devnull if(b->size == MaxBloomSize) /* 2^32 overflows ulong */
72 a0d146ed 2005-07-12 devnull addstat(StatBloomBits, b->size*8-1);
74 a0d146ed 2005-07-12 devnull addstat(StatBloomBits, b->size*8);
76 a0d146ed 2005-07-12 devnull return b;
80 a0d146ed 2005-07-12 devnull writebloom(Bloom *b)
82 a0d146ed 2005-07-12 devnull wbbloomhead(b);
83 a0d146ed 2005-07-12 devnull return writepart(b->part, 0, b->data, b->size);
87 a0d146ed 2005-07-12 devnull * Derive two random 32-bit quantities a, b from the score
88 a0d146ed 2005-07-12 devnull * and then use a+b*i as a sequence of bloom filter indices.
89 a0d146ed 2005-07-12 devnull * Michael Mitzenmacher has a recent (2005) paper saying this is okay.
90 a0d146ed 2005-07-12 devnull * We reserve the bottom bytes (BloomHeadSize*8 bits) for the header.
92 a0d146ed 2005-07-12 devnull static void
93 a0d146ed 2005-07-12 devnull gethashes(u8int *score, ulong *h)
96 a0d146ed 2005-07-12 devnull u32int a, b;
100 a0d146ed 2005-07-12 devnull for(i=4; i+8<=VtScoreSize; i+=8){
101 a0d146ed 2005-07-12 devnull a ^= *(u32int*)(score+i);
102 a0d146ed 2005-07-12 devnull b ^= *(u32int*)(score+i+4);
104 a0d146ed 2005-07-12 devnull if(i+4 <= VtScoreSize) /* 20 is not 4-aligned */
105 a0d146ed 2005-07-12 devnull a ^= *(u32int*)(score+i);
106 a0d146ed 2005-07-12 devnull for(i=0; i<BloomMaxHash; i++, a+=b)
107 a0d146ed 2005-07-12 devnull h[i] = a < BloomHeadSize*8 ? BloomHeadSize*8 : a;
110 a0d146ed 2005-07-12 devnull static void
111 a0d146ed 2005-07-12 devnull _markbloomfilter(Bloom *b, u8int *score)
113 a0d146ed 2005-07-12 devnull int i, nnew;
114 a0d146ed 2005-07-12 devnull ulong h[BloomMaxHash];
115 a0d146ed 2005-07-12 devnull u32int x, *y, z, *tab;
117 a0d146ed 2005-07-12 devnull trace("markbloomfilter", "markbloomfilter %V", score);
118 a0d146ed 2005-07-12 devnull gethashes(score, h);
119 a0d146ed 2005-07-12 devnull nnew = 0;
120 a0d146ed 2005-07-12 devnull tab = (u32int*)b->data;
121 a0d146ed 2005-07-12 devnull for(i=0; i<b->nhash; i++){
122 a0d146ed 2005-07-12 devnull x = h[i];
123 a0d146ed 2005-07-12 devnull y = &tab[(x&b->mask)>>5];
124 a0d146ed 2005-07-12 devnull z = 1<<(x&31);
125 a0d146ed 2005-07-12 devnull if(!(*y&z)){
127 a0d146ed 2005-07-12 devnull *y |= z;
130 a0d146ed 2005-07-12 devnull if(nnew)
131 a0d146ed 2005-07-12 devnull addstat(StatBloomOnes, nnew);
133 a0d146ed 2005-07-12 devnull trace("markbloomfilter", "markbloomfilter exit");
136 a0d146ed 2005-07-12 devnull static int
137 a0d146ed 2005-07-12 devnull _inbloomfilter(Bloom *b, u8int *score)
140 a0d146ed 2005-07-12 devnull ulong h[BloomMaxHash], x;
141 a0d146ed 2005-07-12 devnull u32int *tab;
143 a0d146ed 2005-07-12 devnull gethashes(score, h);
144 a0d146ed 2005-07-12 devnull tab = (u32int*)b->data;
145 a0d146ed 2005-07-12 devnull for(i=0; i<b->nhash; i++){
146 a0d146ed 2005-07-12 devnull x = h[i];
147 a0d146ed 2005-07-12 devnull if(!(tab[(x&b->mask)>>5] & (1<<(x&31))))
148 a0d146ed 2005-07-12 devnull return 0;
150 a0d146ed 2005-07-12 devnull return 1;
154 a0d146ed 2005-07-12 devnull inbloomfilter(Bloom *b, u8int *score)
157 a0d146ed 2005-07-12 devnull uint ms;
159 a0d146ed 2005-07-12 devnull if(b == nil)
160 a0d146ed 2005-07-12 devnull return 1;
162 a0d146ed 2005-07-12 devnull ms = msec();
163 a0d146ed 2005-07-12 devnull rlock(&b->lk);
164 a0d146ed 2005-07-12 devnull r = _inbloomfilter(b, score);
165 a0d146ed 2005-07-12 devnull runlock(&b->lk);
166 a0d146ed 2005-07-12 devnull ms = ms - msec();
167 a0d146ed 2005-07-12 devnull addstat2(StatBloomLookup, 1, StatBloomLookupTime, ms);
169 a0d146ed 2005-07-12 devnull addstat(StatBloomMiss, 1);
171 a0d146ed 2005-07-12 devnull addstat(StatBloomHit, 1);
172 a0d146ed 2005-07-12 devnull return r;
176 a0d146ed 2005-07-12 devnull markbloomfilter(Bloom *b, u8int *score)
178 a0d146ed 2005-07-12 devnull if(b == nil)
181 a0d146ed 2005-07-12 devnull rlock(&b->lk);
182 a0d146ed 2005-07-12 devnull qlock(&b->mod);
183 a0d146ed 2005-07-12 devnull _markbloomfilter(b, score);
184 a0d146ed 2005-07-12 devnull qunlock(&b->mod);
185 a0d146ed 2005-07-12 devnull runlock(&b->lk);
188 a0d146ed 2005-07-12 devnull static void
189 a0d146ed 2005-07-12 devnull bloomwriteproc(void *v)
191 a0d146ed 2005-07-12 devnull Bloom *b;
194 a0d146ed 2005-07-12 devnull for(;;){
195 a0d146ed 2005-07-12 devnull recv(b->writechan, 0);
196 a0d146ed 2005-07-12 devnull if(writebloom(b) < 0)
197 a0d146ed 2005-07-12 devnull fprint(2, "oops! writing bloom: %r\n");
198 a0d146ed 2005-07-12 devnull send(b->writedonechan, 0);
203 a0d146ed 2005-07-12 devnull startbloomproc(Bloom *b)
205 a0d146ed 2005-07-12 devnull b->writechan = chancreate(sizeof(void*), 0);
206 a0d146ed 2005-07-12 devnull b->writedonechan = chancreate(sizeof(void*), 0);
207 a0d146ed 2005-07-12 devnull vtproc(bloomwriteproc, b);