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