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