1 /*
2 Copyright 2005-2010 Jakub Kruszona-Zawadzki, Gemius SA, 2013-2014 EditShare, 2013-2015 Skytechnology sp. z o.o..
3
4 This file was part of MooseFS and is part of LizardFS.
5
6 LizardFS 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 3.
9
10 LizardFS 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 LizardFS If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include "common/platform.h"
20 #include "mount/symlinkcache.h"
21
22 #include <ctime>
23 #include <inttypes.h>
24 #include <pthread.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <limits>
28
29 #include "protocol/MFSCommunication.h"
30 #include "mount/stats.h"
31
32 #define HASH_FUNCTIONS 4
33 #define HASH_BUCKET_SIZE 16
34 #define HASH_BUCKETS 6257
35
36 static uint32_t kCacheTimeInSeconds;
37
38 // entries in cache = HASH_FUNCTIONS*HASH_BUCKET_SIZE*HASH_BUCKETS
39 // 4 * 16 * 6257 = 400448
40 // Symlink cache capacity can be easily 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 uint32_t time[HASH_BUCKET_SIZE];
46 uint8_t* path[HASH_BUCKET_SIZE];
47 } hashbucket;
48
49 static hashbucket *symlinkhash = NULL;
50 static pthread_mutex_t slcachelock = PTHREAD_MUTEX_INITIALIZER;
51
52 enum {
53 INSERTS = 0,
54 SEARCH_HITS,
55 SEARCH_MISSES,
56 LINKS,
57 STATNODES
58 };
59
60 static uint64_t *statsptr[STATNODES];
61
symlink_cache_statsptr_init(void)62 static inline void symlink_cache_statsptr_init(void) {
63 void *s;
64 s = stats_get_subnode(NULL,"symlink_cache",0);
65 statsptr[INSERTS] = stats_get_counterptr(stats_get_subnode(s,"inserts",0));
66 statsptr[SEARCH_HITS] = stats_get_counterptr(stats_get_subnode(s,"search_hits",0));
67 statsptr[SEARCH_MISSES] = stats_get_counterptr(stats_get_subnode(s,"search_misses",0));
68 statsptr[LINKS] = stats_get_counterptr(stats_get_subnode(s,"#links",1));
69 }
70
symlink_cache_stats_inc(uint8_t id)71 static inline void symlink_cache_stats_inc(uint8_t id) {
72 if (id<STATNODES) {
73 stats_lock();
74 (*statsptr[id])++;
75 stats_unlock();
76 }
77 }
78
symlink_cache_stats_dec(uint8_t id)79 static inline void symlink_cache_stats_dec(uint8_t id) {
80 if (id<STATNODES) {
81 stats_lock();
82 (*statsptr[id])--;
83 stats_unlock();
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 uint32_t primes[HASH_FUNCTIONS] = {1072573589U,3465827623U,2848548977U,748191707U};
89 hashbucket *hb,*fhb;
90 uint8_t h,i,fi;
91 uint32_t now;
92 uint32_t mints;
93
94 now = time(NULL);
95 mints = std::numeric_limits<uint32_t>::max();
96 fi = 0;
97 fhb = NULL;
98
99 symlink_cache_stats_inc(INSERTS);
100 pthread_mutex_lock(&slcachelock);
101 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
102 hb = symlinkhash + ((inode*primes[h])%HASH_BUCKETS);
103 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
104 if (hb->inode[i]==inode) {
105 if (hb->path[i]) {
106 free(hb->path[i]);
107 }
108 hb->path[i]=(uint8_t*)strdup((const char *)path);
109 hb->time[i]=now;
110 pthread_mutex_unlock(&slcachelock);
111 return;
112 }
113 if (hb->time[i]<mints) {
114 fhb = hb;
115 fi = i;
116 mints = hb->time[i];
117 }
118 }
119 }
120 if (fhb) { // just sanity check
121 if (fhb->time[fi]==0) {
122 symlink_cache_stats_inc(LINKS);
123 }
124 if (fhb->path[fi]) {
125 free(fhb->path[fi]);
126 }
127 fhb->inode[fi]=inode;
128 fhb->path[fi]=(uint8_t*)strdup((const char *)path);
129 fhb->time[fi]=now;
130 }
131 pthread_mutex_unlock(&slcachelock);
132 }
133
symlink_cache_search(uint32_t inode,const uint8_t ** path)134 int symlink_cache_search(uint32_t inode,const uint8_t **path) {
135 uint32_t primes[HASH_FUNCTIONS] = {1072573589U,3465827623U,2848548977U,748191707U};
136 hashbucket *hb;
137 uint8_t h,i;
138 uint32_t now;
139
140 now = time(NULL);
141
142 pthread_mutex_lock(&slcachelock);
143 for (h=0 ; h<HASH_FUNCTIONS ; h++) {
144 hb = symlinkhash + ((inode*primes[h])%HASH_BUCKETS);
145 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
146 if (hb->inode[i]==inode) {
147 if (hb->time[i] + kCacheTimeInSeconds < now) {
148 if (hb->path[i]) {
149 free(hb->path[i]);
150 hb->path[i]=NULL;
151 }
152 hb->time[i]=0;
153 hb->inode[i]=0;
154 pthread_mutex_unlock(&slcachelock);
155 symlink_cache_stats_dec(LINKS);
156 symlink_cache_stats_inc(SEARCH_MISSES);
157 return 0;
158 }
159 *path = hb->path[i];
160 pthread_mutex_unlock(&slcachelock);
161 symlink_cache_stats_inc(SEARCH_HITS);
162 return 1;
163 }
164 }
165 }
166 pthread_mutex_unlock(&slcachelock);
167 symlink_cache_stats_inc(SEARCH_MISSES);
168 return 0;
169 }
170
symlink_cache_init(uint32_t cache_time)171 void symlink_cache_init(uint32_t cache_time) {
172 symlinkhash = (hashbucket*) malloc(sizeof(hashbucket)*HASH_BUCKETS);
173 memset(symlinkhash,0,sizeof(hashbucket)*HASH_BUCKETS);
174 kCacheTimeInSeconds = cache_time;
175 symlink_cache_statsptr_init();
176 }
177
symlink_cache_term(void)178 void symlink_cache_term(void) {
179 hashbucket *hb;
180 uint8_t i;
181 uint32_t hi;
182
183 pthread_mutex_lock(&slcachelock);
184 for (hi=0 ; hi<HASH_BUCKETS ; hi++) {
185 hb = symlinkhash + hi;
186 for (i=0 ; i<HASH_BUCKET_SIZE ; i++) {
187 if (hb->path[i]) {
188 free(hb->path[i]);
189 }
190 }
191 }
192 free(symlinkhash);
193 pthread_mutex_unlock(&slcachelock);
194 }
195