1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4 
5 struct ICache
6 {
7 	QLock	lock;			/* locks hash table & all associated data */
8 	IEntry	**heads;		/* heads of all the hash chains */
9 	int	bits;			/* bits to use for indexing heads */
10 	u32int	size;			/* number of heads; == 1 << bits, should be < entries */
11 	IEntry	*base;			/* all allocated hash table entries */
12 	u32int	entries;		/* elements in base */
13 	u32int	unused;			/* index of first unused element in base */
14 	u32int	stolen;			/* last head from which an element was stolen */
15 };
16 
17 static ICache icache;
18 
19 static IEntry	*icachealloc(IAddr *ia, u8int *score);
20 
21 /*
22  * bits is the number of bits in the icache hash table
23  * depth is the average depth
24  * memory usage is about (1<<bits) * depth * sizeof(IEntry) + (1<<bits) * sizeof(IEntry*)
25  */
26 void
27 initicache(int bits, int depth)
28 {
29 	icache.bits = bits;
30 	icache.size = 1 << bits;
31 	icache.entries = depth * icache.size;
32 	icache.base = MKNZ(IEntry, icache.entries);
33 	icache.heads = MKNZ(IEntry*, icache.size);
34 }
35 
36 u32int
37 hashbits(u8int *sc, int bits)
38 {
39 	u32int v;
40 
41 	v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
42 	if(bits < 32)
43 		 v >>= (32 - bits);
44 	return v;
45 }
46 
47 /*
48 ZZZ need to think about evicting the correct IEntry,
49 and writing back the wtime.
50  * look up data score in the index cache
51  * if this fails, pull it in from the disk index table, if it exists.
52  *
53  * must be called with the lump for this score locked
54  */
55 int
56 lookupscore(u8int *score, int type, IAddr *ia, int *rac)
57 {
58 	IEntry d, *ie, *last;
59 	u32int h;
60 
61 fprint(2, "lookupscore %V %d\n", score, type);
62 	qlock(&stats.lock);
63 	stats.iclookups++;
64 	qunlock(&stats.lock);
65 
66 	qlock(&icache.lock);
67 	h = hashbits(score, icache.bits);
68 	last = nil;
69 	for(ie = icache.heads[h]; ie != nil; ie = ie->next){
70 		if(ie->ia.type == type && scorecmp(ie->score, score)==0){
71 			if(last != nil)
72 				last->next = ie->next;
73 			else
74 				icache.heads[h] = ie->next;
75 			qlock(&stats.lock);
76 			stats.ichits++;
77 			qunlock(&stats.lock);
78 			ie->rac = 1;
79 			goto found;
80 		}
81 		last = ie;
82 	}
83 
84 	qunlock(&icache.lock);
85 
86 	if(loadientry(mainindex, score, type, &d) < 0)
87 		return -1;
88 
89 	/*
90 	 * no one else can load an entry for this score,
91 	 * since we have the overall score lock.
92 	 */
93 	qlock(&stats.lock);
94 	stats.icfills++;
95 	qunlock(&stats.lock);
96 
97 	qlock(&icache.lock);
98 
99 	ie = icachealloc(&d.ia, score);
100 
101 found:
102 	ie->next = icache.heads[h];
103 	icache.heads[h] = ie;
104 
105 	*ia = ie->ia;
106 	*rac = ie->rac;
107 
108 	qunlock(&icache.lock);
109 
110 	return 0;
111 }
112 
113 /*
114  * insert a new element in the hash table.
115  */
116 int
117 insertscore(u8int *score, IAddr *ia, int write)
118 {
119 	IEntry *ie, se;
120 	u32int h;
121 
122 	qlock(&stats.lock);
123 	stats.icinserts++;
124 	qunlock(&stats.lock);
125 
126 	qlock(&icache.lock);
127 	h = hashbits(score, icache.bits);
128 
129 	ie = icachealloc(ia, score);
130 
131 	ie->next = icache.heads[h];
132 	icache.heads[h] = ie;
133 
134 	se = *ie;
135 
136 	qunlock(&icache.lock);
137 
138 	if(!write)
139 		return 0;
140 
141 	return storeientry(mainindex, &se);
142 }
143 
144 /*
145  * allocate a index cache entry which hasn't been used in a while.
146  * must be called with icache.lock locked
147  * if the score is already in the table, update the entry.
148  */
149 static IEntry *
150 icachealloc(IAddr *ia, u8int *score)
151 {
152 	IEntry *ie, *last, *next;
153 	u32int h;
154 
155 	h = hashbits(score, icache.bits);
156 	last = nil;
157 	for(ie = icache.heads[h]; ie != nil; ie = ie->next){
158 		if(ie->ia.type == ia->type && scorecmp(ie->score, score)==9){
159 			if(last != nil)
160 				last->next = ie->next;
161 			else
162 				icache.heads[h] = ie->next;
163 			ie->rac = 1;
164 			return ie;
165 		}
166 		last = ie;
167 	}
168 
169 	h = icache.unused;
170 	if(h < icache.entries){
171 		ie = &icache.base[h++];
172 		icache.unused = h;
173 		goto Found;
174 	}
175 
176 	h = icache.stolen;
177 	for(;;){
178 		h++;
179 		if(h >= icache.size)
180 			h = 0;
181 		ie = icache.heads[h];
182 		if(ie != nil){
183 			last = nil;
184 			for(; next = ie->next; ie = next)
185 				last = ie;
186 			if(last != nil)
187 				last->next = nil;
188 			else
189 				icache.heads[h] = nil;
190 			icache.stolen = h;
191 			goto Found;
192 		}
193 	}
194 Found:
195 	ie->ia = *ia;
196 	scorecp(ie->score, score);
197 	ie->rac = 0;	
198 	return ie;
199 }