source: branches/samba-3.5.x/source3/smbd/mangle_hash2.c

Last change on this file was 414, checked in by Herwig Bauernfeind, 15 years ago

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