1 /* Copyright 1998,2001-2003,2007-2009 Alain Knaff.
2 * This file is part of mtools.
3 *
4 * Mtools is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * Mtools is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with Mtools. If not, see <http://www.gnu.org/licenses/>.
16 */
17 #include "sysincludes.h"
18 #include "vfat.h"
19 #include "dirCache.h"
20 #include "dirCacheP.h"
21 #include <assert.h>
22
23
24 #define BITS_PER_INT (sizeof(unsigned int) * 8)
25
26
rol(uint32_t arg,int shift)27 static __inline__ uint32_t rol(uint32_t arg, int shift)
28 {
29 arg &= 0xffffffff; /* for 64 bit machines */
30 return (arg << shift) | (arg >> (32 - shift));
31 }
32
33
calcHash(wchar_t * name)34 static uint32_t calcHash(wchar_t *name)
35 {
36 uint32_t hash;
37 unsigned int i;
38 wint_t c;
39
40 hash = 0;
41 i = 0;
42 while(*name) {
43 /* rotate it */
44 hash = rol(hash,5); /* a shift of 5 makes sure we spread quickly
45 * over the whole width, moreover, 5 is
46 * prime with 32, which makes sure that
47 * successive letters cannot cover each
48 * other easily */
49 c = towupper((wint_t)*name);
50 hash ^= (c * (c+2)) ^ (i * (i+2));
51 hash &= 0xffffffff;
52 i++;
53 name++;
54 }
55 hash = hash * (hash + 2);
56 /* the following two xors make sure all info is spread evenly over all
57 * bytes. Important if we only keep the low order bits later on */
58 hash ^= (hash & 0xfff) << 12;
59 hash ^= (hash & 0xff000) << 24;
60 return hash;
61 }
62
addBit(unsigned int * bitmap,unsigned int hash,int checkOnly)63 static unsigned int addBit(unsigned int *bitmap,
64 unsigned int hash, int checkOnly)
65 {
66 unsigned int bit;
67 int entry;
68
69 bit = 1u << (hash % BITS_PER_INT);
70 entry = (hash / BITS_PER_INT) % DC_BITMAP_SIZE;
71
72 if(checkOnly)
73 return bitmap[entry] & bit;
74 else {
75 bitmap[entry] |= bit;
76 return 1;
77 }
78 }
79
_addHash(dirCache_t * cache,unsigned int hash,int checkOnly)80 static int _addHash(dirCache_t *cache, unsigned int hash, int checkOnly)
81 {
82 return
83 addBit(cache->bm0, hash, checkOnly) &&
84 addBit(cache->bm1, rol(hash,12), checkOnly) &&
85 addBit(cache->bm2, rol(hash,24), checkOnly);
86 }
87
88
addNameToHash(dirCache_t * cache,wchar_t * name)89 static void addNameToHash(dirCache_t *cache, wchar_t *name)
90 {
91 _addHash(cache, calcHash(name), 0);
92 }
93
hashDce(dirCache_t * cache,dirCacheEntry_t * dce)94 static void hashDce(dirCache_t *cache, dirCacheEntry_t *dce)
95 {
96 if(dce->beginSlot != cache->nrHashed)
97 return;
98 cache->nrHashed = dce->endSlot;
99 if(dce->longName)
100 addNameToHash(cache, dce->longName);
101 addNameToHash(cache, dce->shortName);
102 }
103
isHashed(dirCache_t * cache,wchar_t * name)104 int isHashed(dirCache_t *cache, wchar_t *name)
105 {
106 int ret;
107
108 ret = _addHash(cache, calcHash(name), 1);
109 return ret;
110 }
111
growDirCache(dirCache_t * cache,unsigned int slot)112 int growDirCache(dirCache_t *cache, unsigned int slot)
113 {
114 if((int) slot < 0) {
115 fprintf(stderr, "Bad slot %d\n", slot);
116 exit(1);
117 }
118
119 if( cache->nr_entries <= slot) {
120 unsigned int i;
121
122 cache->entries = realloc(cache->entries,
123 (slot+1) * 2 *
124 sizeof(dirCacheEntry_t *));
125 if(!cache->entries)
126 return -1;
127 for(i= cache->nr_entries; i < (slot+1) * 2; i++) {
128 cache->entries[i] = 0;
129 }
130 cache->nr_entries = (slot+1) * 2;
131 }
132 return 0;
133 }
134
allocDirCache(Stream_t * Stream,unsigned int slot)135 dirCache_t *allocDirCache(Stream_t *Stream, unsigned int slot)
136 {
137 dirCache_t **dcp;
138
139 if((int)slot < 0) {
140 fprintf(stderr, "Bad slot %d\n", slot);
141 exit(1);
142 }
143
144 dcp = getDirCacheP(Stream);
145 if(!*dcp) {
146 *dcp = New(dirCache_t);
147 if(!*dcp)
148 return 0;
149 (*dcp)->entries = NewArray((slot+1)*2+5, dirCacheEntry_t *);
150 if(!(*dcp)->entries) {
151 free(*dcp);
152 return 0;
153 }
154 (*dcp)->nr_entries = (slot+1) * 2;
155 memset( (*dcp)->bm0, 0, sizeof((*dcp)->bm0));
156 memset( (*dcp)->bm1, 0, sizeof((*dcp)->bm1));
157 memset( (*dcp)->bm2, 0, sizeof((*dcp)->bm1));
158 (*dcp)->nrHashed = 0;
159 } else
160 if(growDirCache(*dcp, slot) < 0)
161 return 0;
162 return *dcp;
163 }
164
165 /* Free a range of entries. The range being cleared is always aligned
166 * on the begin of an entry. Entries which are cleared entirely are
167 * free'd. Entries which are cleared half-way (can only happen at end)
168 * are "shortened" by moving its beginSlot
169 * If this was a range representing space after end-mark, return beginning
170 * of range if it had been shortened in its lifetime (which means that end
171 * mark must have moved => may need to be rewritten)
172 */
freeDirCacheRange(dirCache_t * cache,unsigned int beginSlot,unsigned int endSlot)173 static int freeDirCacheRange(dirCache_t *cache,
174 unsigned int beginSlot,
175 unsigned int endSlot)
176 {
177 dirCacheEntry_t *entry;
178 unsigned int clearBegin;
179 unsigned int clearEnd;
180 unsigned int i;
181
182 if(endSlot < beginSlot) {
183 fprintf(stderr, "Bad slots %d %d in free range\n",
184 beginSlot, endSlot);
185 exit(1);
186 }
187
188 while(beginSlot < endSlot) {
189 entry = cache->entries[beginSlot];
190 if(!entry) {
191 beginSlot++;
192 continue;
193 }
194
195 /* Due to the way this is called, we _always_ de-allocate
196 * starting from beginning... */
197 #ifdef HAVE_ASSERT_H
198 assert(entry->beginSlot == beginSlot);
199 #endif
200 clearEnd = entry->endSlot;
201 if(clearEnd > endSlot)
202 clearEnd = endSlot;
203 clearBegin = beginSlot;
204
205 for(i = clearBegin; i <clearEnd; i++)
206 cache->entries[i] = 0;
207
208 entry->beginSlot = clearEnd;
209
210 if(entry->beginSlot == entry->endSlot) {
211 int needWriteEnd = 0;
212 if(entry->endMarkPos != -1 &&
213 entry->endMarkPos < (int) beginSlot)
214 needWriteEnd = 1;
215
216 if(entry->longName)
217 free(entry->longName);
218 if(entry->shortName)
219 free(entry->shortName);
220 free(entry);
221 if(needWriteEnd) {
222 return (int) beginSlot;
223 }
224 }
225
226 beginSlot = clearEnd;
227 }
228 return -1;
229 }
230
allocDirCacheEntry(dirCache_t * cache,unsigned int beginSlot,unsigned int endSlot,dirCacheEntryType_t type)231 static dirCacheEntry_t *allocDirCacheEntry(dirCache_t *cache,
232 unsigned int beginSlot,
233 unsigned int endSlot,
234 dirCacheEntryType_t type)
235 {
236 dirCacheEntry_t *entry;
237 unsigned int i;
238
239 if(growDirCache(cache, endSlot) < 0)
240 return 0;
241
242 entry = New(dirCacheEntry_t);
243 if(!entry)
244 return 0;
245 entry->type = type;
246 entry->longName = 0;
247 entry->shortName = 0;
248 entry->beginSlot = beginSlot;
249 entry->endSlot = endSlot;
250 entry->endMarkPos = -1;
251
252 freeDirCacheRange(cache, beginSlot, endSlot);
253 for(i=beginSlot; i<endSlot; i++) {
254 cache->entries[i] = entry;
255 }
256 return entry;
257 }
258
addUsedEntry(dirCache_t * cache,unsigned int beginSlot,unsigned int endSlot,wchar_t * longName,wchar_t * shortName,struct directory * dir)259 dirCacheEntry_t *addUsedEntry(dirCache_t *cache,
260 unsigned int beginSlot,
261 unsigned int endSlot,
262 wchar_t *longName, wchar_t *shortName,
263 struct directory *dir)
264 {
265 dirCacheEntry_t *entry;
266
267 if(endSlot < beginSlot) {
268 fprintf(stderr,
269 "Bad slots %d %d in add used entry\n",
270 beginSlot, endSlot);
271 exit(1);
272 }
273
274
275 entry = allocDirCacheEntry(cache, beginSlot, endSlot, DCET_USED);
276 if(!entry)
277 return 0;
278
279 entry->beginSlot = beginSlot;
280 entry->endSlot = endSlot;
281 if(longName)
282 entry->longName = wcsdup(longName);
283 entry->shortName = wcsdup(shortName);
284 entry->dir = *dir;
285 hashDce(cache, entry);
286 return entry;
287 }
288
289 /* Try to merge free slot at position "slot" with slot at previous position
290 * After successful merge, both will point to a same DCE (the one which used
291 * to be previous)
292 * Only does something if both of these slots are actually free
293 */
mergeFreeSlots(dirCache_t * cache,unsigned int slot)294 static void mergeFreeSlots(dirCache_t *cache, unsigned int slot)
295 {
296 dirCacheEntry_t *previous, *next;
297 unsigned int i;
298
299 if(slot == 0)
300 return;
301 previous = cache->entries[slot-1];
302 next = cache->entries[slot];
303 if(next && next->type == DCET_FREE &&
304 previous && previous->type == DCET_FREE) {
305 for(i=next->beginSlot; i < next->endSlot; i++)
306 cache->entries[i] = previous;
307 previous->endSlot = next->endSlot;
308 previous->endMarkPos = next->endMarkPos;
309 free(next);
310 }
311 }
312
313 /* Create a free range extending from beginSlot to endSlot, and try to merge
314 * it with any neighboring free ranges */
addFreeEndEntry(dirCache_t * cache,unsigned int beginSlot,unsigned int endSlot,int isAtEnd)315 dirCacheEntry_t *addFreeEndEntry(dirCache_t *cache,
316 unsigned int beginSlot,
317 unsigned int endSlot,
318 int isAtEnd)
319 {
320 dirCacheEntry_t *entry;
321
322 if(beginSlot < cache->nrHashed)
323 cache->nrHashed = beginSlot;
324
325 if(endSlot < beginSlot) {
326 fprintf(stderr, "Bad slots %d %d in add free entry\n",
327 beginSlot, endSlot);
328 exit(1);
329 }
330
331 if(endSlot == beginSlot)
332 return 0;
333 entry = allocDirCacheEntry(cache, beginSlot, endSlot, DCET_FREE);
334 if(isAtEnd)
335 entry->endMarkPos = (int) beginSlot;
336 mergeFreeSlots(cache, beginSlot);
337 mergeFreeSlots(cache, endSlot);
338 return cache->entries[beginSlot];
339 }
340
addFreeEntry(dirCache_t * cache,unsigned int beginSlot,unsigned int endSlot)341 dirCacheEntry_t *addFreeEntry(dirCache_t *cache,
342 unsigned int beginSlot,
343 unsigned int endSlot)
344 {
345 return addFreeEndEntry(cache, beginSlot, endSlot, 0);
346 }
347
addEndEntry(dirCache_t * cache,unsigned int pos)348 dirCacheEntry_t *addEndEntry(dirCache_t *cache, unsigned int pos)
349 {
350 return allocDirCacheEntry(cache, pos, pos+1u, DCET_END);
351 }
352
lookupInDircache(dirCache_t * cache,unsigned int pos)353 dirCacheEntry_t *lookupInDircache(dirCache_t *cache, unsigned int pos)
354 {
355 if(growDirCache(cache, pos+1) < 0)
356 return 0;
357 return cache->entries[pos];
358 }
359
freeDirCache(Stream_t * Stream)360 void freeDirCache(Stream_t *Stream)
361 {
362 dirCache_t *cache, **dcp;
363
364 dcp = getDirCacheP(Stream);
365 cache = *dcp;
366 if(cache) {
367 int n;
368 n=freeDirCacheRange(cache, 0, cache->nr_entries);
369 if(n >= 0)
370 low_level_dir_write_end(Stream, n);
371 free(cache);
372 *dcp = 0;
373 }
374 }
375