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 #include "MFSCommunication.h"
34
35 #define HASH_FUNCTIONS 4
36 #define HASH_BUCKET_SIZE 16
37 #define HASH_BUCKETS 6257
38
39 // entries in cache = HASH_FUNCTIONS*HASH_BUCKET_SIZE*HASH_BUCKETS
40 // 4 * 16 * 6257 = 400448
41 // Symlink cache capacity can be easly changed by altering HASH_BUCKETS value.
42 // Any number should work but it is better to use prime numbers here.
43
44 typedef struct _hashbucket {
45 uint32_t inode[HASH_BUCKET_SIZE];
46 double time[HASH_BUCKET_SIZE];
47 uint8_t* path[HASH_BUCKET_SIZE];
48 // uint16_t multihit;
49 } hashbucket;
50
51 static const uint32_t primes[HASH_FUNCTIONS] = {1072573589U,3465827623U,2848548977U,748191707U};
52 static hashbucket *symlinkhash = NULL;
53 static pthread_mutex_t slcachelock = PTHREAD_MUTEX_INITIALIZER;
54 static double timeout;
55
56 enum {
57 INSERTS = 0,
58 SEARCH_HITS,
59 SEARCH_MISSES,
60 LINKS,
61 STATNODES
62 };
63
64 static void *statsptr[STATNODES];
65
symlink_cache_statsptr_init(void)66 static inline void symlink_cache_statsptr_init(void) {
67 void *s;
68 s = stats_get_subnode(NULL,"symlink_cache",0,0);
69 statsptr[INSERTS] = stats_get_subnode(s,"inserts",0,1);
70 statsptr[SEARCH_HITS] = stats_get_subnode(s,"search_hits",0,1);
71 statsptr[SEARCH_MISSES] = stats_get_subnode(s,"search_misses",0,1);
72 statsptr[LINKS] = stats_get_subnode(s,"#links",1,1);
73 }
74
symlink_cache_stats_inc(uint8_t id)75 static inline void symlink_cache_stats_inc(uint8_t id) {
76 if (id<STATNODES) {
77 stats_counter_inc(statsptr[id]);
78 }
79 }
80
symlink_cache_stats_dec(uint8_t id)81 static inline void symlink_cache_stats_dec(uint8_t id) {
82 if (id<STATNODES) {
83 stats_counter_dec(statsptr[id]);
84 }
85 }
86
symlink_cache_insert(uint32_t inode,const uint8_t * path)87 void symlink_cache_insert(uint32_t inode,const uint8_t *path) {
88 hashbucket *hb,*fhb;
89 uint8_t h,i,fi;
90 double t;
91 double mint;
92
93 t = monotonic_seconds();
94 mint = t;
95 fi = 0;
96 fhb = NULL;
97
98 symlink_cache_stats_inc(INSERTS);
99 zassert(pthread_mutex_lock(&slcachelock));
100 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
101 hb = symlinkhash + ((inode*primes[h])%HASH_BUCKETS);
102 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
103 if (hb->inode[i]==inode) {
104 if (hb->path[i]) {
105 free(hb->path[i]);
106 }
107 hb->path[i]=(uint8_t*)strdup((const char *)path);
108 hb->time[i]=t;
109 zassert(pthread_mutex_unlock(&slcachelock));
110 return;
111 }
112 if (hb->time[i]<mint) {
113 fhb = hb;
114 fi = i;
115 mint = hb->time[i];
116 }
117 }
118 }
119 if (fhb) { // just sanity check
120 if (fhb->time[fi]==0) {
121 symlink_cache_stats_inc(LINKS);
122 }
123 if (fhb->path[fi]) {
124 free(fhb->path[fi]);
125 }
126 fhb->inode[fi]=inode;
127 fhb->path[fi]=(uint8_t*)strdup((const char *)path);
128 fhb->time[fi]=t;
129 }
130 zassert(pthread_mutex_unlock(&slcachelock));
131 }
132
symlink_cache_search(uint32_t inode)133 uint8_t* symlink_cache_search(uint32_t inode) {
134 hashbucket *hb;
135 uint8_t h,i;
136 double t;
137 uint8_t *path;
138
139 t = monotonic_seconds();
140
141 zassert(pthread_mutex_lock(&slcachelock));
142 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
143 hb = symlinkhash + ((inode*primes[h])%HASH_BUCKETS);
144 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
145 if (hb->inode[i]==inode) {
146 if (hb->time[i]+timeout<t) {
147 if (hb->path[i]) {
148 free(hb->path[i]);
149 hb->path[i]=NULL;
150 }
151 hb->time[i] = 0.0;
152 hb->inode[i] = 0;
153 zassert(pthread_mutex_unlock(&slcachelock));
154 symlink_cache_stats_dec(LINKS);
155 symlink_cache_stats_inc(SEARCH_MISSES);
156 return NULL;
157 }
158 path = (uint8_t*)strdup((const char *)(hb->path[i]));
159 zassert(pthread_mutex_unlock(&slcachelock));
160 symlink_cache_stats_inc(SEARCH_HITS);
161 return path;
162 }
163 }
164 }
165 zassert(pthread_mutex_unlock(&slcachelock));
166 symlink_cache_stats_inc(SEARCH_MISSES);
167 return NULL;
168 }
169
symlink_cache_init(double to)170 void symlink_cache_init(double to) {
171 hashbucket *hb;
172 uint8_t i;
173 uint32_t hi;
174
175 symlinkhash = malloc(sizeof(hashbucket)*HASH_BUCKETS);
176 passert(symlinkhash);
177 for (hi=0 ; hi<HASH_BUCKETS ; hi++) {
178 hb = symlinkhash + hi;
179 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
180 hb->inode[i] = 0;
181 hb->time[i] = 0.0;
182 hb->path[i] = NULL;
183 }
184 }
185 timeout = to;
186 symlink_cache_statsptr_init();
187 }
188
symlink_cache_term(void)189 void symlink_cache_term(void) {
190 hashbucket *hb;
191 uint8_t i;
192 uint32_t hi;
193
194 zassert(pthread_mutex_lock(&slcachelock));
195 for (hi=0 ; hi<HASH_BUCKETS ; hi++) {
196 hb = symlinkhash + hi;
197 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
198 if (hb->path[i]) {
199 free(hb->path[i]);
200 }
201 hb->path[i] = NULL;
202 }
203 }
204 free(symlinkhash);
205 symlinkhash = NULL;
206 zassert(pthread_mutex_unlock(&slcachelock));
207 }
208