Add a in-memory cache
[nivanova/samba-autobuild/.git] / source3 / smbd / mangle_hash2.c
1 /* 
2    Unix SMB/CIFS implementation.
3    new hash based name mangling implementation
4    Copyright (C) Andrew Tridgell 2002
5    Copyright (C) Simo Sorce 2002
6    
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3 of the License, or
10    (at your option) any later version.
11    
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16    
17    You should have received a copy of the GNU General Public License
18    along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 /*
22   this mangling scheme uses the following format
23
24   Annnn~n.AAA
25
26   where nnnnn is a base 36 hash, and A represents characters from the original string
27
28   The hash is taken of the leading part of the long filename, in uppercase
29
30   for simplicity, we only allow ascii characters in 8.3 names
31  */
32
33  /* hash alghorithm changed to FNV1 by idra@samba.org (Simo Sorce).
34   * see http://www.isthe.com/chongo/tech/comp/fnv/index.html for a
35   * discussion on Fowler / Noll / Vo (FNV) Hash by one of it's authors
36   */
37
38 /*
39   ===============================================================================
40   NOTE NOTE NOTE!!!
41
42   This file deliberately uses non-multibyte string functions in many places. This
43   is *not* a mistake. This code is multi-byte safe, but it gets this property
44   through some very subtle knowledge of the way multi-byte strings are encoded 
45   and the fact that this mangling algorithm only supports ascii characters in
46   8.3 names.
47
48   please don't convert this file to use the *_m() functions!!
49   ===============================================================================
50 */
51
52
53 #include "includes.h"
54
55 #if 1
56 #define M_DEBUG(level, x) DEBUG(level, x)
57 #else
58 #define M_DEBUG(level, x)
59 #endif
60
61 /* these flags are used to mark characters in as having particular
62    properties */
63 #define FLAG_BASECHAR 1
64 #define FLAG_ASCII 2
65 #define FLAG_ILLEGAL 4
66 #define FLAG_WILDCARD 8
67
68 /* the "possible" flags are used as a fast way to find possible DOS
69    reserved filenames */
70 #define FLAG_POSSIBLE1 16
71 #define FLAG_POSSIBLE2 32
72 #define FLAG_POSSIBLE3 64
73 #define FLAG_POSSIBLE4 128
74
75 /* by default have a max of 4096 entries in the cache. */
76 #ifndef MANGLE_CACHE_SIZE
77 #define MANGLE_CACHE_SIZE 4096
78 #endif
79
80 #define FNV1_PRIME 0x01000193
81 /*the following number is a fnv1 of the string: idra@samba.org 2002 */
82 #define FNV1_INIT  0xa6b93095
83
84 /* these tables are used to provide fast tests for characters */
85 static unsigned char char_flags[256];
86
87 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
88
89 /*
90   this determines how many characters are used from the original filename
91   in the 8.3 mangled name. A larger value leads to a weaker hash and more collisions.
92   The largest possible value is 6.
93 */
94 static unsigned mangle_prefix;
95
96 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
97 static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
98 static unsigned char base_reverse[256];
99 #define base_forward(v) basechars[v]
100
101 /* the list of reserved dos names - all of these are illegal */
102 static const char *reserved_names[] = 
103 { "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4",
104   "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
105
106 /* 
107    hash a string of the specified length. The string does not need to be
108    null terminated 
109
110    this hash needs to be fast with a low collision rate (what hash doesn't?)
111 */
112 static unsigned int mangle_hash(const char *key, unsigned int length)
113 {
114         unsigned int value;
115         unsigned int   i;
116         fstring str;
117
118         /* we have to uppercase here to ensure that the mangled name
119            doesn't depend on the case of the long name. Note that this
120            is the only place where we need to use a multi-byte string
121            function */
122         length = MIN(length,sizeof(fstring)-1);
123         strncpy(str, key, length);
124         str[length] = 0;
125         strupper_m(str);
126
127         /* the length of a multi-byte string can change after a strupper_m */
128         length = strlen(str);
129
130         /* Set the initial value from the key size. */
131         for (value = FNV1_INIT, i=0; i < length; i++) {
132                 value *= (unsigned int)FNV1_PRIME;
133                 value ^= (unsigned int)(str[i]);
134         }
135
136         /* note that we force it to a 31 bit hash, to keep within the limits
137            of the 36^6 mangle space */
138         return value & ~0x80000000;  
139 }
140
141 /*
142   insert an entry into the prefix cache. The string might not be null
143   terminated */
144 static void cache_insert(const char *prefix, int length, unsigned int hash)
145 {
146         char *str = SMB_STRNDUP(prefix, length);
147
148         if (str == NULL) {
149                 return;
150         }
151
152         memcache_add(smbd_memcache(), MANGLE_HASH2_CACHE,
153                      data_blob_const(&hash, sizeof(hash)),
154                      data_blob_const(str, length+1));
155         SAFE_FREE(str);
156 }
157
158 /*
159   lookup an entry in the prefix cache. Return NULL if not found.
160 */
161 static char *cache_lookup(TALLOC_CTX *mem_ctx, unsigned int hash)
162 {
163         DATA_BLOB value;
164
165         if (!memcache_lookup(smbd_memcache(), MANGLE_HASH2_CACHE,
166                              data_blob_const(&hash, sizeof(hash)), &value)) {
167                 return NULL;
168         }
169
170         SMB_ASSERT((value.length > 0)
171                    && (value.data[value.length-1] == '\0'));
172
173         return talloc_strdup(mem_ctx, (char *)value.data);
174 }
175
176
177 /* 
178    determine if a string is possibly in a mangled format, ignoring
179    case 
180
181    In this algorithm, mangled names use only pure ascii characters (no
182    multi-byte) so we can avoid doing a UCS2 conversion 
183  */
184 static bool is_mangled_component(const char *name, size_t len)
185 {
186         unsigned int i;
187
188         M_DEBUG(10,("is_mangled_component %s (len %lu) ?\n", name, (unsigned long)len));
189
190         /* check the length */
191         if (len > 12 || len < 8)
192                 return False;
193
194         /* the best distinguishing characteristic is the ~ */
195         if (name[6] != '~')
196                 return False;
197
198         /* check extension */
199         if (len > 8) {
200                 if (name[8] != '.')
201                         return False;
202                 for (i=9; name[i] && i < len; i++) {
203                         if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
204                                 return False;
205                         }
206                 }
207         }
208         
209         /* check lead characters */
210         for (i=0;i<mangle_prefix;i++) {
211                 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
212                         return False;
213                 }
214         }
215         
216         /* check rest of hash */
217         if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
218                 return False;
219         }
220         for (i=mangle_prefix;i<6;i++) {
221                 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
222                         return False;
223                 }
224         }
225
226         M_DEBUG(10,("is_mangled_component %s (len %lu) -> yes\n", name, (unsigned long)len));
227
228         return True;
229 }
230
231
232
233 /* 
234    determine if a string is possibly in a mangled format, ignoring
235    case 
236
237    In this algorithm, mangled names use only pure ascii characters (no
238    multi-byte) so we can avoid doing a UCS2 conversion 
239
240    NOTE! This interface must be able to handle a path with unix
241    directory separators. It should return true if any component is
242    mangled
243  */
244 static bool is_mangled(const char *name, const struct share_params *parm)
245 {
246         const char *p;
247         const char *s;
248
249         M_DEBUG(10,("is_mangled %s ?\n", name));
250
251         for (s=name; (p=strchr(s, '/')); s=p+1) {
252                 if (is_mangled_component(s, PTR_DIFF(p, s))) {
253                         return True;
254                 }
255         }
256         
257         /* and the last part ... */
258         return is_mangled_component(s,strlen(s));
259 }
260
261
262 /* 
263    see if a filename is an allowable 8.3 name.
264
265    we are only going to allow ascii characters in 8.3 names, as this
266    simplifies things greatly (it means that we know the string won't
267    get larger when converted from UNIX to DOS formats)
268 */
269 static bool is_8_3(const char *name, bool check_case, bool allow_wildcards, const struct share_params *p)
270 {
271         int len, i;
272         char *dot_p;
273
274         /* as a special case, the names '.' and '..' are allowable 8.3 names */
275         if (name[0] == '.') {
276                 if (!name[1] || (name[1] == '.' && !name[2])) {
277                         return True;
278                 }
279         }
280
281         /* the simplest test is on the overall length of the
282          filename. Note that we deliberately use the ascii string
283          length (not the multi-byte one) as it is faster, and gives us
284          the result we need in this case. Using strlen_m would not
285          only be slower, it would be incorrect */
286         len = strlen(name);
287         if (len > 12)
288                 return False;
289
290         /* find the '.'. Note that once again we use the non-multibyte
291            function */
292         dot_p = strchr(name, '.');
293
294         if (!dot_p) {
295                 /* if the name doesn't contain a '.' then its length
296                    must be less than 8 */
297                 if (len > 8) {
298                         return False;
299                 }
300         } else {
301                 int prefix_len, suffix_len;
302
303                 /* if it does contain a dot then the prefix must be <=
304                    8 and the suffix <= 3 in length */
305                 prefix_len = PTR_DIFF(dot_p, name);
306                 suffix_len = len - (prefix_len+1);
307
308                 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
309                         return False;
310                 }
311
312                 /* a 8.3 name cannot contain more than 1 '.' */
313                 if (strchr(dot_p+1, '.')) {
314                         return False;
315                 }
316         }
317
318         /* the length are all OK. Now check to see if the characters themselves are OK */
319         for (i=0; name[i]; i++) {
320                 /* note that we may allow wildcard petterns! */
321                 if (!FLAG_CHECK(name[i], FLAG_ASCII|(allow_wildcards ? FLAG_WILDCARD : 0)) && name[i] != '.') {
322                         return False;
323                 }
324         }
325
326         /* it is a good 8.3 name */
327         return True;
328 }
329
330
331 /*
332   reset the mangling cache on a smb.conf reload. This only really makes sense for
333   mangling backends that have parameters in smb.conf, and as this backend doesn't
334   this is a NULL operation
335 */
336 static void mangle_reset(void)
337 {
338         /* noop */
339 }
340
341
342 /*
343   try to find a 8.3 name in the cache, and if found then
344   replace the string with the original long name.
345 */
346 static bool lookup_name_from_8_3(TALLOC_CTX *ctx,
347                         const char *name,
348                         char **pp_out, /* talloced on the given context. */
349                         const struct share_params *p)
350 {
351         unsigned int hash, multiplier;
352         unsigned int i;
353         char *prefix;
354         char extension[4];
355
356         *pp_out = NULL;
357
358         /* make sure that this is a mangled name from this cache */
359         if (!is_mangled(name, p)) {
360                 M_DEBUG(10,("lookup_name_from_8_3: %s -> not mangled\n", name));
361                 return False;
362         }
363
364         /* we need to extract the hash from the 8.3 name */
365         hash = base_reverse[(unsigned char)name[7]];
366         for (multiplier=36, i=5;i>=mangle_prefix;i--) {
367                 unsigned int v = base_reverse[(unsigned char)name[i]];
368                 hash += multiplier * v;
369                 multiplier *= 36;
370         }
371
372         /* now look in the prefix cache for that hash */
373         prefix = cache_lookup(ctx, hash);
374         if (!prefix) {
375                 M_DEBUG(10,("lookup_name_from_8_3: %s -> %08X -> not found\n",
376                                         name, hash));
377                 return False;
378         }
379
380         /* we found it - construct the full name */
381         if (name[8] == '.') {
382                 strncpy(extension, name+9, 3);
383                 extension[3] = 0;
384         } else {
385                 extension[0] = 0;
386         }
387
388         if (extension[0]) {
389                 M_DEBUG(10,("lookup_name_from_8_3: %s -> %s.%s\n",
390                                         name, prefix, extension));
391                 *pp_out = talloc_asprintf(ctx, "%s.%s", prefix, extension);
392         } else {
393                 M_DEBUG(10,("lookup_name_from_8_3: %s -> %s\n", name, prefix));
394                 *pp_out = talloc_strdup(ctx, prefix);
395         }
396
397         TALLOC_FREE(prefix);
398
399         if (!pp_out) {
400                 M_DEBUG(0,("talloc_fail"));
401                 return False;
402         }
403
404         return True;
405 }
406
407 /*
408   look for a DOS reserved name
409 */
410 static bool is_reserved_name(const char *name)
411 {
412         if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
413             FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
414             FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
415             FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
416                 /* a likely match, scan the lot */
417                 int i;
418                 for (i=0; reserved_names[i]; i++) {
419                         int len = strlen(reserved_names[i]);
420                         /* note that we match on COM1 as well as COM1.foo */
421                         if (strnequal(name, reserved_names[i], len) &&
422                             (name[len] == '.' || name[len] == 0)) {
423                                 return True;
424                         }
425                 }
426         }
427
428         return False;
429 }
430
431 /*
432  See if a filename is a legal long filename.
433  A filename ending in a '.' is not legal unless it's "." or "..". JRA.
434  A filename ending in ' ' is not legal either. See bug id #2769.
435 */
436
437 static bool is_legal_name(const char *name)
438 {
439         const char *dot_pos = NULL;
440         bool alldots = True;
441         size_t numdots = 0;
442
443         while (*name) {
444                 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
445                         /* Possible start of mb character. */
446                         char mbc[2];
447                         /*
448                          * Note that if CH_UNIX is utf8 a string may be 3
449                          * bytes, but this is ok as mb utf8 characters don't
450                          * contain embedded ascii bytes. We are really checking
451                          * for mb UNIX asian characters like Japanese (SJIS) here.
452                          * JRA.
453                          */
454                         if (convert_string(CH_UNIX, CH_UTF16LE, name, 2, mbc, 2, False) == 2) {
455                                 /* Was a good mb string. */
456                                 name += 2;
457                                 continue;
458                         }
459                 }
460
461                 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
462                         return False;
463                 }
464                 if (name[0] == '.') {
465                         dot_pos = name;
466                         numdots++;
467                 } else {
468                         alldots = False;
469                 }
470                 if ((name[0] == ' ') && (name[1] == '\0')) {
471                         /* Can't end in ' ' */
472                         return False;
473                 }
474                 name++;
475         }
476
477         if (dot_pos) {
478                 if (alldots && (numdots == 1 || numdots == 2))
479                         return True; /* . or .. is a valid name */
480
481                 /* A valid long name cannot end in '.' */
482                 if (dot_pos[1] == '\0')
483                         return False;
484         }
485         return True;
486 }
487
488 static bool must_mangle(const char *name,
489                         const struct share_params *p)
490 {
491         if (is_reserved_name(name)) {
492                 return True;
493         }
494         return !is_legal_name(name);
495 }
496
497 /*
498   the main forward mapping function, which converts a long filename to 
499   a 8.3 name
500
501   if cache83 is not set then we don't cache the result
502
503 */
504 static bool hash2_name_to_8_3(const char *name,
505                         char new_name[13],
506                         bool cache83,
507                         int default_case,
508                         const struct share_params *p)
509 {
510         char *dot_p;
511         char lead_chars[7];
512         char extension[4];
513         unsigned int extension_length, i;
514         unsigned int prefix_len;
515         unsigned int hash, v;
516
517         /* reserved names are handled specially */
518         if (!is_reserved_name(name)) {
519                 /* if the name is already a valid 8.3 name then we don't need to
520                  * change anything */
521                 if (is_legal_name(name) && is_8_3(name, False, False, p)) {
522                         safe_strcpy(new_name, name, 12);
523                         return True;
524                 }
525         }
526
527         /* find the '.' if any */
528         dot_p = strrchr(name, '.');
529
530         if (dot_p) {
531                 /* if the extension contains any illegal characters or
532                    is too long or zero length then we treat it as part
533                    of the prefix */
534                 for (i=0; i<4 && dot_p[i+1]; i++) {
535                         if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
536                                 dot_p = NULL;
537                                 break;
538                         }
539                 }
540                 if (i == 0 || i == 4) {
541                         dot_p = NULL;
542                 }
543         }
544
545         /* the leading characters in the mangled name is taken from
546            the first characters of the name, if they are ascii otherwise
547            '_' is used
548         */
549         for (i=0;i<mangle_prefix && name[i];i++) {
550                 lead_chars[i] = name[i];
551                 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
552                         lead_chars[i] = '_';
553                 }
554                 lead_chars[i] = toupper_ascii(lead_chars[i]);
555         }
556         for (;i<mangle_prefix;i++) {
557                 lead_chars[i] = '_';
558         }
559
560         /* the prefix is anything up to the first dot */
561         if (dot_p) {
562                 prefix_len = PTR_DIFF(dot_p, name);
563         } else {
564                 prefix_len = strlen(name);
565         }
566
567         /* the extension of the mangled name is taken from the first 3
568            ascii chars after the dot */
569         extension_length = 0;
570         if (dot_p) {
571                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
572                         char c = dot_p[i];
573                         if (FLAG_CHECK(c, FLAG_ASCII)) {
574                                 extension[extension_length++] =
575                                         toupper_ascii(c);
576                         }
577                 }
578         }
579
580         /* find the hash for this prefix */
581         v = hash = mangle_hash(name, prefix_len);
582
583         /* now form the mangled name. */
584         for (i=0;i<mangle_prefix;i++) {
585                 new_name[i] = lead_chars[i];
586         }
587         new_name[7] = base_forward(v % 36);
588         new_name[6] = '~';
589         for (i=5; i>=mangle_prefix; i--) {
590                 v = v / 36;
591                 new_name[i] = base_forward(v % 36);
592         }
593
594         /* add the extension */
595         if (extension_length) {
596                 new_name[8] = '.';
597                 memcpy(&new_name[9], extension, extension_length);
598                 new_name[9+extension_length] = 0;
599         } else {
600                 new_name[8] = 0;
601         }
602
603         if (cache83) {
604                 /* put it in the cache */
605                 cache_insert(name, prefix_len, hash);
606         }
607
608         M_DEBUG(10,("hash2_name_to_8_3: %s -> %08X -> %s (cache=%d)\n",
609                    name, hash, new_name, cache83));
610
611         return True;
612 }
613
614 /* initialise the flags table
615
616   we allow only a very restricted set of characters as 'ascii' in this
617   mangling backend. This isn't a significant problem as modern clients
618   use the 'long' filenames anyway, and those don't have these
619   restrictions.
620 */
621 static void init_tables(void)
622 {
623         int i;
624
625         memset(char_flags, 0, sizeof(char_flags));
626
627         for (i=1;i<128;i++) {
628                 if (i <= 0x1f) {
629                         /* Control characters. */
630                         char_flags[i] |= FLAG_ILLEGAL;
631                 }
632
633                 if ((i >= '0' && i <= '9') ||
634                     (i >= 'a' && i <= 'z') ||
635                     (i >= 'A' && i <= 'Z')) {
636                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
637                 }
638                 if (strchr("_-$~", i)) {
639                         char_flags[i] |= FLAG_ASCII;
640                 }
641
642                 if (strchr("*\\/?<>|\":", i)) {
643                         char_flags[i] |= FLAG_ILLEGAL;
644                 }
645
646                 if (strchr("*?\"<>", i)) {
647                         char_flags[i] |= FLAG_WILDCARD;
648                 }
649         }
650
651         memset(base_reverse, 0, sizeof(base_reverse));
652         for (i=0;i<36;i++) {
653                 base_reverse[(unsigned char)base_forward(i)] = i;
654         }
655
656         /* fill in the reserved names flags. These are used as a very
657            fast filter for finding possible DOS reserved filenames */
658         for (i=0; reserved_names[i]; i++) {
659                 unsigned char c1, c2, c3, c4;
660
661                 c1 = (unsigned char)reserved_names[i][0];
662                 c2 = (unsigned char)reserved_names[i][1];
663                 c3 = (unsigned char)reserved_names[i][2];
664                 c4 = (unsigned char)reserved_names[i][3];
665
666                 char_flags[c1] |= FLAG_POSSIBLE1;
667                 char_flags[c2] |= FLAG_POSSIBLE2;
668                 char_flags[c3] |= FLAG_POSSIBLE3;
669                 char_flags[c4] |= FLAG_POSSIBLE4;
670                 char_flags[tolower_ascii(c1)] |= FLAG_POSSIBLE1;
671                 char_flags[tolower_ascii(c2)] |= FLAG_POSSIBLE2;
672                 char_flags[tolower_ascii(c3)] |= FLAG_POSSIBLE3;
673                 char_flags[tolower_ascii(c4)] |= FLAG_POSSIBLE4;
674
675                 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
676         }
677 }
678
679 /*
680   the following provides the abstraction layer to make it easier
681   to drop in an alternative mangling implementation */
682 static struct mangle_fns mangle_fns = {
683         mangle_reset,
684         is_mangled,
685         must_mangle,
686         is_8_3,
687         lookup_name_from_8_3,
688         hash2_name_to_8_3
689 };
690
691 /* return the methods for this mangling implementation */
692 struct mangle_fns *mangle_hash2_init(void)
693 {
694         /* the mangle prefix can only be in the mange 1 to 6 */
695         mangle_prefix = lp_mangle_prefix();
696         if (mangle_prefix > 6) {
697                 mangle_prefix = 6;
698         }
699         if (mangle_prefix < 1) {
700                 mangle_prefix = 1;
701         }
702
703         init_tables();
704         mangle_reset();
705
706         return &mangle_fns;
707 }
708
709 static void posix_mangle_reset(void)
710 {;}
711
712 static bool posix_is_mangled(const char *s, const struct share_params *p)
713 {
714         return False;
715 }
716
717 static bool posix_must_mangle(const char *s, const struct share_params *p)
718 {
719         return False;
720 }
721
722 static bool posix_is_8_3(const char *fname,
723                         bool check_case,
724                         bool allow_wildcards,
725                         const struct share_params *p)
726 {
727         return False;
728 }
729
730 static bool posix_lookup_name_from_8_3(TALLOC_CTX *ctx,
731                                 const char *in,
732                                 char **out, /* talloced on the given context. */
733                                 const struct share_params *p)
734 {
735         return False;
736 }
737
738 static bool posix_name_to_8_3(const char *in,
739                                 char out[13],
740                                 bool cache83,
741                                 int default_case,
742                                 const struct share_params *p)
743 {
744         memset(out, '\0', 13);
745         return True;
746 }
747
748 /* POSIX paths backend - no mangle. */
749 static struct mangle_fns posix_mangle_fns = {
750         posix_mangle_reset,
751         posix_is_mangled,
752         posix_must_mangle,
753         posix_is_8_3,
754         posix_lookup_name_from_8_3,
755         posix_name_to_8_3
756 };
757
758 struct mangle_fns *posix_mangle_init(void)
759 {
760         return &posix_mangle_fns;
761 }