source: branches/samba-3.2.x/source/smbd/mangle_hash2.c

Last change on this file was 133, checked in by Paul Smedley, 17 years ago

Update trunk to 3.2.0pre3
File size: 18.6 KB
Line 
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 */
85static 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*/
94static unsigned mangle_prefix;
95
96/* these are the characters we use in the 8.3 hash. Must be 36 chars long */
97static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
98static 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 */
102static 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*/
112static 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 */
144static 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*/
161static 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 */
184static 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 */
244static 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*/
269static 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*/
336static 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*/
346static 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*/
410static 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
437static 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
488static 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*/
504static 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*/
621static 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 */
682static 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 */
692struct 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
709static void posix_mangle_reset(void)
710{;}
711
712static bool posix_is_mangled(const char *s, const struct share_params *p)
713{
714 return False;
715}
716
717static bool posix_must_mangle(const char *s, const struct share_params *p)
718{
719 return False;
720}
721
722static 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
730static 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
738static 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. */
749static 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
758struct mangle_fns *posix_mangle_init(void)
759{
760 return &posix_mangle_fns;
761}
Note: See TracBrowser for help on using the repository browser.