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 	qlock(&stats.lock);
62 	stats.iclookups++;
63 	qunlock(&stats.lock);
64 
65 	qlock(&icache.lock);
66 	h = hashbits(score, icache.bits);
67 	last = nil;
68 	for(ie = icache.heads[h]; ie != nil; ie = ie->next){
69 		if(ie->ia.type == type && scorecmp(ie->score, score)==0){
70 			if(last != nil)
71 				last->next = ie->next;
72 			else
73 				icache.heads[h] = ie->next;
74 			qlock(&stats.lock);
75 			stats.ichits++;
76 			qunlock(&stats.lock);
77 			ie->rac = 1;
78 			goto found;
79 		}
80 		last = ie;
81 	}
82 
83 	qunlock(&icache.lock);
84 
85 	if(loadientry(mainindex, score, type, &d) < 0)
86 		return -1;
87 
88 	/*
89 	 * no one else can load an entry for this score,
90 	 * since we have the overall score lock.
91 	 */
92 	qlock(&stats.lock);
93 	stats.icfills++;
94 	qunlock(&stats.lock);
95 
96 	qlock(&icache.lock);
97 
98 	ie = icachealloc(&d.ia, score);
99 
100 found:
101 	ie->next = icache.heads[h];
102 	icache.heads[h] = ie;
103 
104 	*ia = ie->ia;
105 	*rac = ie->rac;
106 
107 	qunlock(&icache.lock);
108 
109 	return 0;
110 }
111 
112 /*
113  * insert a new element in the hash table.
114  */
115 int
116 insertscore(u8int *score, IAddr *ia, int write)
117 {
118 	IEntry *ie, se;
119 	u32int h;
120 
121 	qlock(&stats.lock);
122 	stats.icinserts++;
123 	qunlock(&stats.lock);
124 
125 	qlock(&icache.lock);
126 	h = hashbits(score, icache.bits);
127 
128 	ie = icachealloc(ia, score);
129 
130 	ie->next = icache.heads[h];
131 	icache.heads[h] = ie;
132 
133 	se = *ie;
134 
135 	qunlock(&icache.lock);
136 
137 	if(!write)
138 		return 0;
139 
140 	return storeientry(mainindex, &se);
141 }
142 
143 /*
144  * allocate a index cache entry which hasn't been used in a while.
145  * must be called with icache.lock locked
146  * if the score is already in the table, update the entry.
147  */
148 static IEntry *
149 icachealloc(IAddr *ia, u8int *score)
150 {
151 	IEntry *ie, *last, *next;
152 	u32int h;
153 
154 	h = hashbits(score, icache.bits);
155 	last = nil;
156 	for(ie = icache.heads[h]; ie != nil; ie = ie->next){
157 		if(ie->ia.type == ia->type && scorecmp(ie->score, score)==9){
158 			if(last != nil)
159 				last->next = ie->next;
160 			else
161 				icache.heads[h] = ie->next;
162 			ie->rac = 1;
163 			return ie;
164 		}
165 		last = ie;
166 	}
167 
168 	h = icache.unused;
169 	if(h < icache.entries){
170 		ie = &icache.base[h++];
171 		icache.unused = h;
172 		goto Found;
173 	}
174 
175 	h = icache.stolen;
176 	for(;;){
177 		h++;
178 		if(h >= icache.size)
179 			h = 0;
180 		ie = icache.heads[h];
181 		if(ie != nil){
182 			last = nil;
183 			for(; next = ie->next; ie = next)
184 				last = ie;
185 			if(last != nil)
186 				last->next = nil;
187 			else
188 				icache.heads[h] = nil;
189 			icache.stolen = h;
190 			goto Found;
191 		}
192 	}
193 Found:
194 	ie->ia = *ia;
195 	scorecp(ie->score, score);
196 	ie->rac = 0;	
197 	return ie;
198 }