1 /*
2 * Copyright (C) 2021 Jakub Kruszona-Zawadzki, Core Technology Sp. z o.o.
3 *
4 * This file is part of MooseFS.
5 *
6 * MooseFS is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, version 2 (only).
9 *
10 * MooseFS is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with MooseFS; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301, USA
18 * or visit http://www.gnu.org/licenses/gpl-2.0.html
19 */
20
21 #ifdef HAVE_CONFIG_H
22 #include "config.h"
23 #endif
24
25 #include <stdlib.h>
26 #include <string.h>
27 #include <inttypes.h>
28 #include <pthread.h>
29
30 #include "stats.h"
31 #include "clocks.h"
32 #include "massert.h"
33
34 #define HASH_FUNCTIONS 4
35 #define HASH_BUCKET_SIZE 16
36 #define HASH_BUCKETS 6257
37
38 // entries in cache = HASH_FUNCTIONS*HASH_BUCKET_SIZE*HASH_BUCKETS
39 // // 4 * 16 * 6257 = 400448
40 // // Symlink cache capacity can be easly changed by altering HASH_BUCKETS value.
41 // // Any number should work but it is better to use prime numbers here.
42
43 typedef struct _hashbucket {
44 uint32_t inode[HASH_BUCKET_SIZE];
45 uint8_t nleng[HASH_BUCKET_SIZE];
46 uint8_t *name[HASH_BUCKET_SIZE];
47 double time[HASH_BUCKET_SIZE];
48 } hashbucket;
49
50
51 static hashbucket *negentryhash = NULL;
52 static double lastvalidentry = 0.0;
53 static double NegEntryTimeOut = 1.0;
54 static pthread_mutex_t necachelock = PTHREAD_MUTEX_INITIALIZER;
55
56 enum {
57 INSERTS = 0,
58 REMOVALS,
59 SEARCH_HITS,
60 SEARCH_MISSES,
61 ENTRIES,
62 STATNODES
63 };
64
65 static void *statsptr[STATNODES];
66
negentry_cache_statsptr_init(void)67 static inline void negentry_cache_statsptr_init(void) {
68 void *s;
69 s = stats_get_subnode(NULL,"negentry_cache",0,0);
70 statsptr[INSERTS] = stats_get_subnode(s,"inserts",0,1);
71 statsptr[REMOVALS] = stats_get_subnode(s,"removals",0,1);
72 statsptr[SEARCH_HITS] = stats_get_subnode(s,"search_hits",0,1);
73 statsptr[SEARCH_MISSES] = stats_get_subnode(s,"search_misses",0,1);
74 statsptr[ENTRIES] = stats_get_subnode(s,"#entries",1,1);
75 }
76
negentry_cache_stats_inc(uint8_t id)77 static inline void negentry_cache_stats_inc(uint8_t id) {
78 if (id<STATNODES) {
79 stats_counter_inc(statsptr[id]);
80 }
81 }
82
negentry_cache_stats_dec(uint8_t id)83 static inline void negentry_cache_stats_dec(uint8_t id) {
84 if (id<STATNODES) {
85 stats_counter_dec(statsptr[id]);
86 }
87 }
88
negentry_cache_hash(uint8_t n,uint32_t inode,uint8_t nleng,const uint8_t * name)89 static inline uint32_t negentry_cache_hash(uint8_t n,uint32_t inode,uint8_t nleng,const uint8_t *name) {
90 static const uint32_t primes[HASH_FUNCTIONS] = {1072573589U,3465827623U,2848548977U,748191707U};
91 uint32_t hash;
92 uint8_t i;
93
94 hash = inode;
95 hash *= primes[n];
96 hash += nleng;
97 #if defined(FAST_DATAPACK)
98 for (i=0 ; i<nleng/4 ; i++) {
99 hash *= primes[n];
100 hash += ((const uint32_t*)name)[i];
101 }
102 for (i=0 ; i<nleng%4 ; i++) {
103 hash *= primes[n];
104 hash += name[(nleng&~3)+i];
105 }
106 #else
107 for (i=0 ; i<nleng ; i++) {
108 hash *= primes[n];
109 hash += name[i];
110 }
111 #endif
112 return hash;
113 }
114
negentry_cache_insert(uint32_t inode,uint8_t nleng,const uint8_t * name)115 void negentry_cache_insert(uint32_t inode,uint8_t nleng,const uint8_t *name) {
116 hashbucket *hb,*fhb;
117 uint8_t h,i,fi;
118 double t;
119 double mint;
120
121 if (NegEntryTimeOut<=0.0) {
122 return;
123 }
124 t = monotonic_seconds();
125 mint = t;
126 fi = 0;
127 fhb = NULL;
128
129 negentry_cache_stats_inc(INSERTS);
130 zassert(pthread_mutex_lock(&necachelock));
131 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
132 hb = negentryhash + (negentry_cache_hash(h,inode,nleng,name)%HASH_BUCKETS);
133 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
134 if (hb->inode[i]==inode && hb->nleng[i]==nleng && memcmp(hb->name[i],name,nleng)==0) {
135 hb->time[i] = t;
136 zassert(pthread_mutex_unlock(&necachelock));
137 return;
138 }
139 if (hb->time[i]<mint) {
140 fhb = hb;
141 fi = i;
142 mint = hb->time[i];
143 }
144 }
145 }
146 if (fhb) {
147 if (fhb->time[fi]==0.0) {
148 negentry_cache_stats_inc(ENTRIES);
149 }
150 fhb->inode[fi]=inode;
151 fhb->nleng[fi]=nleng;
152 if (fhb->name[fi]) {
153 free(fhb->name[fi]);
154 }
155 fhb->name[fi] = malloc(nleng);
156 passert(fhb->name[fi]);
157 memcpy(fhb->name[fi],name,nleng);
158 fhb->time[fi]=t;
159 }
160 zassert(pthread_mutex_unlock(&necachelock));
161 }
162
negentry_cache_remove(uint32_t inode,uint8_t nleng,const uint8_t * name)163 void negentry_cache_remove(uint32_t inode,uint8_t nleng,const uint8_t *name) {
164 hashbucket *hb;
165 uint8_t h,i;
166 uint8_t f;
167 double t;
168
169 if (NegEntryTimeOut<=0.0) {
170 return;
171 }
172 t = monotonic_seconds();
173
174 negentry_cache_stats_inc(REMOVALS);
175 zassert(pthread_mutex_lock(&necachelock));
176 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
177 f = 0;
178 hb = negentryhash + (negentry_cache_hash(h,inode,nleng,name)%HASH_BUCKETS);
179 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
180 if (hb->inode[i]==inode && hb->nleng[i]==nleng && memcmp(hb->name[i],name,nleng)==0) {
181 f = 2;
182 }
183 if (hb->time[i]>0.0 && (hb->time[i] + NegEntryTimeOut < t || hb->time[i] < lastvalidentry || f==2)) {
184 hb->inode[i] = 0;
185 hb->nleng[i] = 0;
186 if (hb->name[i]) {
187 free(hb->name[i]);
188 }
189 hb->name[i] = NULL;
190 hb->time[i] = 0.0;
191 negentry_cache_stats_dec(ENTRIES);
192 }
193 if (f==2) {
194 f = 1;
195 }
196 }
197 if (f) {
198 zassert(pthread_mutex_unlock(&necachelock));
199 return;
200 }
201 }
202 zassert(pthread_mutex_unlock(&necachelock));
203 return;
204 }
205
negentry_cache_search(uint32_t inode,uint8_t nleng,const uint8_t * name)206 uint8_t negentry_cache_search(uint32_t inode,uint8_t nleng,const uint8_t *name) {
207 hashbucket *hb;
208 uint8_t h,i;
209 uint8_t f;
210 double t;
211
212 if (NegEntryTimeOut<=0.0) {
213 return 0;
214 }
215 t = monotonic_seconds();
216
217 zassert(pthread_mutex_lock(&necachelock));
218 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
219 f = 0;
220 hb = negentryhash + (negentry_cache_hash(h,inode,nleng,name)%HASH_BUCKETS);
221 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
222 if (hb->time[i]>0.0 && (hb->time[i] + NegEntryTimeOut < t || hb->time[i] < lastvalidentry)) {
223 hb->inode[i] = 0;
224 hb->nleng[i] = 0;
225 if (hb->name[i]) {
226 free(hb->name[i]);
227 }
228 hb->name[i] = NULL;
229 hb->time[i] = 0.0;
230 negentry_cache_stats_dec(ENTRIES);
231 } else if (hb->inode[i]==inode && hb->nleng[i]==nleng && memcmp(hb->name[i],name,nleng)==0) {
232 f = 1;
233 }
234 }
235 if (f) {
236 zassert(pthread_mutex_unlock(&necachelock));
237 negentry_cache_stats_inc(SEARCH_HITS);
238 return 1;
239 }
240 }
241 zassert(pthread_mutex_unlock(&necachelock));
242 negentry_cache_stats_inc(SEARCH_MISSES);
243 return 0;
244 }
245
negentry_cache_clear(void)246 void negentry_cache_clear(void) {
247 double t = monotonic_seconds();
248 zassert(pthread_mutex_lock(&necachelock));
249 lastvalidentry = t;
250 zassert(pthread_mutex_unlock(&necachelock));
251 }
252
negentry_cache_init(double to)253 void negentry_cache_init(double to) {
254 hashbucket *hb;
255 uint8_t i;
256 uint32_t hi;
257
258 NegEntryTimeOut = to;
259 if (to<=0.0) {
260 return;
261 }
262 negentryhash = malloc(sizeof(hashbucket)*HASH_BUCKETS);
263 passert(negentryhash);
264 for (hi=0 ; hi<HASH_BUCKETS ; hi++) {
265 hb = negentryhash + hi;
266 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
267 hb->inode[i] = 0;
268 hb->nleng[i] = 0;
269 hb->name[i] = NULL;
270 hb->time[i] = 0.0;
271 }
272 }
273 negentry_cache_statsptr_init();
274 }
275
negentry_cache_term(void)276 void negentry_cache_term(void) {
277 hashbucket *hb;
278 uint8_t i;
279 uint32_t hi;
280
281 if (NegEntryTimeOut<=0.0 || negentryhash==NULL) {
282 return;
283 }
284 pthread_mutex_lock(&necachelock);
285 for (hi=0 ; hi<HASH_BUCKETS ; hi++) {
286 hb = negentryhash + hi;
287 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
288 if (hb->name[i]) {
289 free(hb->name[i]);
290 }
291 hb->name[i]=NULL;
292 }
293 }
294 free(negentryhash);
295 negentryhash = NULL;
296 pthread_mutex_unlock(&necachelock);
297 }
298