1 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
2 7a4ee46d 2003-11-23 devnull #include "dat.h"
3 7a4ee46d 2003-11-23 devnull #include "fns.h"
5 7a4ee46d 2003-11-23 devnull struct ICache
7 7a4ee46d 2003-11-23 devnull QLock lock; /* locks hash table & all associated data */
8 7a4ee46d 2003-11-23 devnull IEntry **heads; /* heads of all the hash chains */
9 7a4ee46d 2003-11-23 devnull int bits; /* bits to use for indexing heads */
10 7a4ee46d 2003-11-23 devnull u32int size; /* number of heads; == 1 << bits, should be < entries */
11 7a4ee46d 2003-11-23 devnull IEntry *base; /* all allocated hash table entries */
12 7a4ee46d 2003-11-23 devnull u32int entries; /* elements in base */
13 7a4ee46d 2003-11-23 devnull u32int unused; /* index of first unused element in base */
14 7a4ee46d 2003-11-23 devnull u32int stolen; /* last head from which an element was stolen */
17 7a4ee46d 2003-11-23 devnull static ICache icache;
19 7a4ee46d 2003-11-23 devnull static IEntry *icachealloc(IAddr *ia, u8int *score);
22 7a4ee46d 2003-11-23 devnull * bits is the number of bits in the icache hash table
23 7a4ee46d 2003-11-23 devnull * depth is the average depth
24 7a4ee46d 2003-11-23 devnull * memory usage is about (1<<bits) * depth * sizeof(IEntry) + (1<<bits) * sizeof(IEntry*)
27 7a4ee46d 2003-11-23 devnull initicache(int bits, int depth)
29 7a4ee46d 2003-11-23 devnull icache.bits = bits;
30 7a4ee46d 2003-11-23 devnull icache.size = 1 << bits;
31 7a4ee46d 2003-11-23 devnull icache.entries = depth * icache.size;
32 7a4ee46d 2003-11-23 devnull icache.base = MKNZ(IEntry, icache.entries);
33 7a4ee46d 2003-11-23 devnull icache.heads = MKNZ(IEntry*, icache.size);
37 7a4ee46d 2003-11-23 devnull hashbits(u8int *sc, int bits)
39 7a4ee46d 2003-11-23 devnull u32int v;
41 7a4ee46d 2003-11-23 devnull v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
42 7a4ee46d 2003-11-23 devnull if(bits < 32)
43 7a4ee46d 2003-11-23 devnull v >>= (32 - bits);
44 7a4ee46d 2003-11-23 devnull return v;
48 7a4ee46d 2003-11-23 devnull ZZZ need to think about evicting the correct IEntry,
49 7a4ee46d 2003-11-23 devnull and writing back the wtime.
50 7a4ee46d 2003-11-23 devnull * look up data score in the index cache
51 7a4ee46d 2003-11-23 devnull * if this fails, pull it in from the disk index table, if it exists.
53 7a4ee46d 2003-11-23 devnull * must be called with the lump for this score locked
56 7a4ee46d 2003-11-23 devnull lookupscore(u8int *score, int type, IAddr *ia, int *rac)
58 7a4ee46d 2003-11-23 devnull IEntry d, *ie, *last;
59 7a4ee46d 2003-11-23 devnull u32int h;
61 7a4ee46d 2003-11-23 devnull fprint(2, "lookupscore %V %d\n", score, type);
62 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
63 7a4ee46d 2003-11-23 devnull stats.iclookups++;
64 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
66 7a4ee46d 2003-11-23 devnull qlock(&icache.lock);
67 7a4ee46d 2003-11-23 devnull h = hashbits(score, icache.bits);
68 7a4ee46d 2003-11-23 devnull last = nil;
69 7a4ee46d 2003-11-23 devnull for(ie = icache.heads[h]; ie != nil; ie = ie->next){
70 7a4ee46d 2003-11-23 devnull if(ie->ia.type == type && scorecmp(ie->score, score)==0){
71 7a4ee46d 2003-11-23 devnull if(last != nil)
72 7a4ee46d 2003-11-23 devnull last->next = ie->next;
74 7a4ee46d 2003-11-23 devnull icache.heads[h] = ie->next;
75 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
76 7a4ee46d 2003-11-23 devnull stats.ichits++;
77 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
78 7a4ee46d 2003-11-23 devnull ie->rac = 1;
79 7a4ee46d 2003-11-23 devnull goto found;
81 7a4ee46d 2003-11-23 devnull last = ie;
84 7a4ee46d 2003-11-23 devnull qunlock(&icache.lock);
86 7a4ee46d 2003-11-23 devnull if(loadientry(mainindex, score, type, &d) < 0)
87 7a4ee46d 2003-11-23 devnull return -1;
90 7a4ee46d 2003-11-23 devnull * no one else can load an entry for this score,
91 7a4ee46d 2003-11-23 devnull * since we have the overall score lock.
93 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
94 7a4ee46d 2003-11-23 devnull stats.icfills++;
95 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
97 7a4ee46d 2003-11-23 devnull qlock(&icache.lock);
99 7a4ee46d 2003-11-23 devnull ie = icachealloc(&d.ia, score);
102 7a4ee46d 2003-11-23 devnull ie->next = icache.heads[h];
103 7a4ee46d 2003-11-23 devnull icache.heads[h] = ie;
105 7a4ee46d 2003-11-23 devnull *ia = ie->ia;
106 7a4ee46d 2003-11-23 devnull *rac = ie->rac;
108 7a4ee46d 2003-11-23 devnull qunlock(&icache.lock);
110 7a4ee46d 2003-11-23 devnull return 0;
114 7a4ee46d 2003-11-23 devnull * insert a new element in the hash table.
117 7a4ee46d 2003-11-23 devnull insertscore(u8int *score, IAddr *ia, int write)
119 7a4ee46d 2003-11-23 devnull IEntry *ie, se;
120 7a4ee46d 2003-11-23 devnull u32int h;
122 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
123 7a4ee46d 2003-11-23 devnull stats.icinserts++;
124 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
126 7a4ee46d 2003-11-23 devnull qlock(&icache.lock);
127 7a4ee46d 2003-11-23 devnull h = hashbits(score, icache.bits);
129 7a4ee46d 2003-11-23 devnull ie = icachealloc(ia, score);
131 7a4ee46d 2003-11-23 devnull ie->next = icache.heads[h];
132 7a4ee46d 2003-11-23 devnull icache.heads[h] = ie;
134 7a4ee46d 2003-11-23 devnull se = *ie;
136 7a4ee46d 2003-11-23 devnull qunlock(&icache.lock);
138 7a4ee46d 2003-11-23 devnull if(!write)
139 7a4ee46d 2003-11-23 devnull return 0;
141 7a4ee46d 2003-11-23 devnull return storeientry(mainindex, &se);
145 7a4ee46d 2003-11-23 devnull * allocate a index cache entry which hasn't been used in a while.
146 7a4ee46d 2003-11-23 devnull * must be called with icache.lock locked
147 7a4ee46d 2003-11-23 devnull * if the score is already in the table, update the entry.
149 7a4ee46d 2003-11-23 devnull static IEntry *
150 7a4ee46d 2003-11-23 devnull icachealloc(IAddr *ia, u8int *score)
152 7a4ee46d 2003-11-23 devnull IEntry *ie, *last, *next;
153 7a4ee46d 2003-11-23 devnull u32int h;
155 7a4ee46d 2003-11-23 devnull h = hashbits(score, icache.bits);
156 7a4ee46d 2003-11-23 devnull last = nil;
157 7a4ee46d 2003-11-23 devnull for(ie = icache.heads[h]; ie != nil; ie = ie->next){
158 7a4ee46d 2003-11-23 devnull if(ie->ia.type == ia->type && scorecmp(ie->score, score)==9){
159 7a4ee46d 2003-11-23 devnull if(last != nil)
160 7a4ee46d 2003-11-23 devnull last->next = ie->next;
162 7a4ee46d 2003-11-23 devnull icache.heads[h] = ie->next;
163 7a4ee46d 2003-11-23 devnull ie->rac = 1;
164 7a4ee46d 2003-11-23 devnull return ie;
166 7a4ee46d 2003-11-23 devnull last = ie;
169 7a4ee46d 2003-11-23 devnull h = icache.unused;
170 7a4ee46d 2003-11-23 devnull if(h < icache.entries){
171 7a4ee46d 2003-11-23 devnull ie = &icache.base[h++];
172 7a4ee46d 2003-11-23 devnull icache.unused = h;
173 7a4ee46d 2003-11-23 devnull goto Found;
176 7a4ee46d 2003-11-23 devnull h = icache.stolen;
177 7a4ee46d 2003-11-23 devnull for(;;){
179 7a4ee46d 2003-11-23 devnull if(h >= icache.size)
181 7a4ee46d 2003-11-23 devnull ie = icache.heads[h];
182 7a4ee46d 2003-11-23 devnull if(ie != nil){
183 7a4ee46d 2003-11-23 devnull last = nil;
184 7a4ee46d 2003-11-23 devnull for(; next = ie->next; ie = next)
185 7a4ee46d 2003-11-23 devnull last = ie;
186 7a4ee46d 2003-11-23 devnull if(last != nil)
187 7a4ee46d 2003-11-23 devnull last->next = nil;
189 7a4ee46d 2003-11-23 devnull icache.heads[h] = nil;
190 7a4ee46d 2003-11-23 devnull icache.stolen = h;
191 7a4ee46d 2003-11-23 devnull goto Found;
195 7a4ee46d 2003-11-23 devnull ie->ia = *ia;
196 7a4ee46d 2003-11-23 devnull scorecp(ie->score, score);
197 7a4ee46d 2003-11-23 devnull ie->rac = 0;
198 7a4ee46d 2003-11-23 devnull return ie;
