2 Unix SMB/CIFS implementation.
3 new hash based name mangling implementation
4 Copyright (C) Andrew Tridgell 2002
5 Copyright (C) Simo Sorce 2002
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.
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.
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/>.
22 this mangling scheme uses the following format
26 where nnnnn is a base 36 hash, and A represents characters from the original string
28 The hash is taken of the leading part of the long filename, in uppercase
30 for simplicity, we only allow ascii characters in 8.3 names
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
39 ===============================================================================
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
48 please don't convert this file to use the *_m() functions!!
49 ===============================================================================
56 #define M_DEBUG(level, x) DEBUG(level, x)
58 #define M_DEBUG(level, x)
61 /* these flags are used to mark characters in as having particular
63 #define FLAG_BASECHAR 1
65 #define FLAG_ILLEGAL 4
66 #define FLAG_WILDCARD 8
68 /* the "possible" flags are used as a fast way to find possible DOS
70 #define FLAG_POSSIBLE1 16
71 #define FLAG_POSSIBLE2 32
72 #define FLAG_POSSIBLE3 64
73 #define FLAG_POSSIBLE4 128
75 /* by default have a max of 4096 entries in the cache. */
76 #ifndef MANGLE_CACHE_SIZE
77 #define MANGLE_CACHE_SIZE 4096
80 #define FNV1_PRIME 0x01000193
81 /*the following number is a fnv1 of the string: idra@samba.org 2002 */
82 #define FNV1_INIT 0xa6b93095
84 /* these tables are used to provide fast tests for characters */
85 static unsigned char char_flags[256];
87 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
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.
94 static unsigned mangle_prefix;
96 /* we will use a very simple direct mapped prefix cache. The big
97 advantage of this cache structure is speed and low memory usage
99 The cache is indexed by the low-order bits of the hash, and confirmed by
100 hashing the resulting cache entry to match the known hash
102 static char **prefix_cache;
103 static unsigned int *prefix_cache_hashes;
105 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
106 static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
107 static unsigned char base_reverse[256];
108 #define base_forward(v) basechars[v]
110 /* the list of reserved dos names - all of these are illegal */
111 static const char *reserved_names[] =
112 { "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4",
113 "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
116 hash a string of the specified length. The string does not need to be
119 this hash needs to be fast with a low collision rate (what hash doesn't?)
121 static unsigned int mangle_hash(const char *key, unsigned int length)
127 /* we have to uppercase here to ensure that the mangled name
128 doesn't depend on the case of the long name. Note that this
129 is the only place where we need to use a multi-byte string
131 length = MIN(length,sizeof(fstring)-1);
132 strncpy(str, key, length);
136 /* the length of a multi-byte string can change after a strupper_m */
137 length = strlen(str);
139 /* Set the initial value from the key size. */
140 for (value = FNV1_INIT, i=0; i < length; i++) {
141 value *= (unsigned int)FNV1_PRIME;
142 value ^= (unsigned int)(str[i]);
145 /* note that we force it to a 31 bit hash, to keep within the limits
146 of the 36^6 mangle space */
147 return value & ~0x80000000;
151 initialise (ie. allocate) the prefix cache
153 static bool cache_init(void)
159 prefix_cache = SMB_CALLOC_ARRAY(char *,MANGLE_CACHE_SIZE);
164 prefix_cache_hashes = SMB_CALLOC_ARRAY(unsigned int, MANGLE_CACHE_SIZE);
165 if (!prefix_cache_hashes) {
166 SAFE_FREE(prefix_cache);
174 insert an entry into the prefix cache. The string might not be null
176 static void cache_insert(const char *prefix, int length, unsigned int hash)
178 int i = hash % MANGLE_CACHE_SIZE;
180 if (prefix_cache[i]) {
181 free(prefix_cache[i]);
184 prefix_cache[i] = SMB_STRNDUP(prefix, length);
185 prefix_cache_hashes[i] = hash;
189 lookup an entry in the prefix cache. Return NULL if not found.
191 static const char *cache_lookup(unsigned int hash)
193 int i = hash % MANGLE_CACHE_SIZE;
195 if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
199 /* yep, it matched */
200 return prefix_cache[i];
205 determine if a string is possibly in a mangled format, ignoring
208 In this algorithm, mangled names use only pure ascii characters (no
209 multi-byte) so we can avoid doing a UCS2 conversion
211 static bool is_mangled_component(const char *name, size_t len)
215 M_DEBUG(10,("is_mangled_component %s (len %lu) ?\n", name, (unsigned long)len));
217 /* check the length */
218 if (len > 12 || len < 8)
221 /* the best distinguishing characteristic is the ~ */
225 /* check extension */
229 for (i=9; name[i] && i < len; i++) {
230 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
236 /* check lead characters */
237 for (i=0;i<mangle_prefix;i++) {
238 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
243 /* check rest of hash */
244 if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
247 for (i=mangle_prefix;i<6;i++) {
248 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
253 M_DEBUG(10,("is_mangled_component %s (len %lu) -> yes\n", name, (unsigned long)len));
261 determine if a string is possibly in a mangled format, ignoring
264 In this algorithm, mangled names use only pure ascii characters (no
265 multi-byte) so we can avoid doing a UCS2 conversion
267 NOTE! This interface must be able to handle a path with unix
268 directory separators. It should return true if any component is
271 static bool is_mangled(const char *name, const struct share_params *parm)
276 M_DEBUG(10,("is_mangled %s ?\n", name));
278 for (s=name; (p=strchr(s, '/')); s=p+1) {
279 if (is_mangled_component(s, PTR_DIFF(p, s))) {
284 /* and the last part ... */
285 return is_mangled_component(s,strlen(s));
290 see if a filename is an allowable 8.3 name.
292 we are only going to allow ascii characters in 8.3 names, as this
293 simplifies things greatly (it means that we know the string won't
294 get larger when converted from UNIX to DOS formats)
296 static bool is_8_3(const char *name, bool check_case, bool allow_wildcards, const struct share_params *p)
301 /* as a special case, the names '.' and '..' are allowable 8.3 names */
302 if (name[0] == '.') {
303 if (!name[1] || (name[1] == '.' && !name[2])) {
308 /* the simplest test is on the overall length of the
309 filename. Note that we deliberately use the ascii string
310 length (not the multi-byte one) as it is faster, and gives us
311 the result we need in this case. Using strlen_m would not
312 only be slower, it would be incorrect */
317 /* find the '.'. Note that once again we use the non-multibyte
319 dot_p = strchr(name, '.');
322 /* if the name doesn't contain a '.' then its length
323 must be less than 8 */
328 int prefix_len, suffix_len;
330 /* if it does contain a dot then the prefix must be <=
331 8 and the suffix <= 3 in length */
332 prefix_len = PTR_DIFF(dot_p, name);
333 suffix_len = len - (prefix_len+1);
335 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
339 /* a 8.3 name cannot contain more than 1 '.' */
340 if (strchr(dot_p+1, '.')) {
345 /* the length are all OK. Now check to see if the characters themselves are OK */
346 for (i=0; name[i]; i++) {
347 /* note that we may allow wildcard petterns! */
348 if (!FLAG_CHECK(name[i], FLAG_ASCII|(allow_wildcards ? FLAG_WILDCARD : 0)) && name[i] != '.') {
353 /* it is a good 8.3 name */
359 reset the mangling cache on a smb.conf reload. This only really makes sense for
360 mangling backends that have parameters in smb.conf, and as this backend doesn't
361 this is a NULL operation
363 static void mangle_reset(void)
370 try to find a 8.3 name in the cache, and if found then
371 replace the string with the original long name.
373 static bool lookup_name_from_8_3(TALLOC_CTX *ctx,
375 char **pp_out, /* talloced on the given context. */
376 const struct share_params *p)
378 unsigned int hash, multiplier;
385 /* make sure that this is a mangled name from this cache */
386 if (!is_mangled(name, p)) {
387 M_DEBUG(10,("lookup_name_from_8_3: %s -> not mangled\n", name));
391 /* we need to extract the hash from the 8.3 name */
392 hash = base_reverse[(unsigned char)name[7]];
393 for (multiplier=36, i=5;i>=mangle_prefix;i--) {
394 unsigned int v = base_reverse[(unsigned char)name[i]];
395 hash += multiplier * v;
399 /* now look in the prefix cache for that hash */
400 prefix = cache_lookup(hash);
402 M_DEBUG(10,("lookup_name_from_8_3: %s -> %08X -> not found\n",
407 /* we found it - construct the full name */
408 if (name[8] == '.') {
409 strncpy(extension, name+9, 3);
416 M_DEBUG(10,("lookup_name_from_8_3: %s -> %s.%s\n",
417 name, prefix, extension));
418 *pp_out = talloc_asprintf(ctx, "%s.%s", prefix, extension);
420 M_DEBUG(10,("lookup_name_from_8_3: %s -> %s\n", name, prefix));
421 *pp_out = talloc_strdup(ctx, prefix);
425 M_DEBUG(0,("talloc_fail"));
433 look for a DOS reserved name
435 static bool is_reserved_name(const char *name)
437 if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
438 FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
439 FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
440 FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
441 /* a likely match, scan the lot */
443 for (i=0; reserved_names[i]; i++) {
444 int len = strlen(reserved_names[i]);
445 /* note that we match on COM1 as well as COM1.foo */
446 if (strnequal(name, reserved_names[i], len) &&
447 (name[len] == '.' || name[len] == 0)) {
457 See if a filename is a legal long filename.
458 A filename ending in a '.' is not legal unless it's "." or "..". JRA.
459 A filename ending in ' ' is not legal either. See bug id #2769.
462 static bool is_legal_name(const char *name)
464 const char *dot_pos = NULL;
469 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
470 /* Possible start of mb character. */
473 * Note that if CH_UNIX is utf8 a string may be 3
474 * bytes, but this is ok as mb utf8 characters don't
475 * contain embedded ascii bytes. We are really checking
476 * for mb UNIX asian characters like Japanese (SJIS) here.
479 if (convert_string(CH_UNIX, CH_UTF16LE, name, 2, mbc, 2, False) == 2) {
480 /* Was a good mb string. */
486 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
489 if (name[0] == '.') {
495 if ((name[0] == ' ') && (name[1] == '\0')) {
496 /* Can't end in ' ' */
503 if (alldots && (numdots == 1 || numdots == 2))
504 return True; /* . or .. is a valid name */
506 /* A valid long name cannot end in '.' */
507 if (dot_pos[1] == '\0')
513 static bool must_mangle(const char *name,
514 const struct share_params *p)
516 if (is_reserved_name(name)) {
519 return !is_legal_name(name);
523 the main forward mapping function, which converts a long filename to
526 if cache83 is not set then we don't cache the result
529 static bool hash2_name_to_8_3(const char *name,
533 const struct share_params *p)
538 unsigned int extension_length, i;
539 unsigned int prefix_len;
540 unsigned int hash, v;
542 /* reserved names are handled specially */
543 if (!is_reserved_name(name)) {
544 /* if the name is already a valid 8.3 name then we don't need to
546 if (is_legal_name(name) && is_8_3(name, False, False, p)) {
547 safe_strcpy(new_name, name, 12);
552 /* find the '.' if any */
553 dot_p = strrchr(name, '.');
556 /* if the extension contains any illegal characters or
557 is too long or zero length then we treat it as part
559 for (i=0; i<4 && dot_p[i+1]; i++) {
560 if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
565 if (i == 0 || i == 4) {
570 /* the leading characters in the mangled name is taken from
571 the first characters of the name, if they are ascii otherwise
574 for (i=0;i<mangle_prefix && name[i];i++) {
575 lead_chars[i] = name[i];
576 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
579 lead_chars[i] = toupper_ascii(lead_chars[i]);
581 for (;i<mangle_prefix;i++) {
585 /* the prefix is anything up to the first dot */
587 prefix_len = PTR_DIFF(dot_p, name);
589 prefix_len = strlen(name);
592 /* the extension of the mangled name is taken from the first 3
593 ascii chars after the dot */
594 extension_length = 0;
596 for (i=1; extension_length < 3 && dot_p[i]; i++) {
598 if (FLAG_CHECK(c, FLAG_ASCII)) {
599 extension[extension_length++] =
605 /* find the hash for this prefix */
606 v = hash = mangle_hash(name, prefix_len);
608 /* now form the mangled name. */
609 for (i=0;i<mangle_prefix;i++) {
610 new_name[i] = lead_chars[i];
612 new_name[7] = base_forward(v % 36);
614 for (i=5; i>=mangle_prefix; i--) {
616 new_name[i] = base_forward(v % 36);
619 /* add the extension */
620 if (extension_length) {
622 memcpy(&new_name[9], extension, extension_length);
623 new_name[9+extension_length] = 0;
629 /* put it in the cache */
630 cache_insert(name, prefix_len, hash);
633 M_DEBUG(10,("hash2_name_to_8_3: %s -> %08X -> %s (cache=%d)\n",
634 name, hash, new_name, cache83));
639 /* initialise the flags table
641 we allow only a very restricted set of characters as 'ascii' in this
642 mangling backend. This isn't a significant problem as modern clients
643 use the 'long' filenames anyway, and those don't have these
646 static void init_tables(void)
650 memset(char_flags, 0, sizeof(char_flags));
652 for (i=1;i<128;i++) {
654 /* Control characters. */
655 char_flags[i] |= FLAG_ILLEGAL;
658 if ((i >= '0' && i <= '9') ||
659 (i >= 'a' && i <= 'z') ||
660 (i >= 'A' && i <= 'Z')) {
661 char_flags[i] |= (FLAG_ASCII | FLAG_BASECHAR);
663 if (strchr("_-$~", i)) {
664 char_flags[i] |= FLAG_ASCII;
667 if (strchr("*\\/?<>|\":", i)) {
668 char_flags[i] |= FLAG_ILLEGAL;
671 if (strchr("*?\"<>", i)) {
672 char_flags[i] |= FLAG_WILDCARD;
676 memset(base_reverse, 0, sizeof(base_reverse));
678 base_reverse[(unsigned char)base_forward(i)] = i;
681 /* fill in the reserved names flags. These are used as a very
682 fast filter for finding possible DOS reserved filenames */
683 for (i=0; reserved_names[i]; i++) {
684 unsigned char c1, c2, c3, c4;
686 c1 = (unsigned char)reserved_names[i][0];
687 c2 = (unsigned char)reserved_names[i][1];
688 c3 = (unsigned char)reserved_names[i][2];
689 c4 = (unsigned char)reserved_names[i][3];
691 char_flags[c1] |= FLAG_POSSIBLE1;
692 char_flags[c2] |= FLAG_POSSIBLE2;
693 char_flags[c3] |= FLAG_POSSIBLE3;
694 char_flags[c4] |= FLAG_POSSIBLE4;
695 char_flags[tolower_ascii(c1)] |= FLAG_POSSIBLE1;
696 char_flags[tolower_ascii(c2)] |= FLAG_POSSIBLE2;
697 char_flags[tolower_ascii(c3)] |= FLAG_POSSIBLE3;
698 char_flags[tolower_ascii(c4)] |= FLAG_POSSIBLE4;
700 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
705 the following provides the abstraction layer to make it easier
706 to drop in an alternative mangling implementation */
707 static struct mangle_fns mangle_fns = {
712 lookup_name_from_8_3,
716 /* return the methods for this mangling implementation */
717 struct mangle_fns *mangle_hash2_init(void)
719 /* the mangle prefix can only be in the mange 1 to 6 */
720 mangle_prefix = lp_mangle_prefix();
721 if (mangle_prefix > 6) {
724 if (mangle_prefix < 1) {
738 static void posix_mangle_reset(void)
741 static bool posix_is_mangled(const char *s, const struct share_params *p)
746 static bool posix_must_mangle(const char *s, const struct share_params *p)
751 static bool posix_is_8_3(const char *fname,
753 bool allow_wildcards,
754 const struct share_params *p)
759 static bool posix_lookup_name_from_8_3(TALLOC_CTX *ctx,
761 char **out, /* talloced on the given context. */
762 const struct share_params *p)
767 static bool posix_name_to_8_3(const char *in,
771 const struct share_params *p)
773 memset(out, '\0', 13);
777 /* POSIX paths backend - no mangle. */
778 static struct mangle_fns posix_mangle_fns = {
783 posix_lookup_name_from_8_3,
787 struct mangle_fns *posix_mangle_init(void)
789 return &posix_mangle_fns;