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 2 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, write to the Free Software 19 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 20*/ 21 22/* 23 this mangling scheme uses the following format 24 25 Annnn~n.AAA 26 27 where nnnnn is a base 36 hash, and A represents characters from the original string 28 29 The hash is taken of the leading part of the long filename, in uppercase 30 31 for simplicity, we only allow ascii characters in 8.3 names 32 */ 33 34 /* hash alghorithm changed to FNV1 by idra@samba.org (Simo Sorce). 35 * see http://www.isthe.com/chongo/tech/comp/fnv/index.html for a 36 * discussion on Fowler / Noll / Vo (FNV) Hash by one of it's authors 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#include "includes.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/* these tables are used to provide fast tests for characters */ 86static unsigned char char_flags[256]; 87 88#define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag)) 89 90/* 91 this determines how many characters are used from the original filename 92 in the 8.3 mangled name. A larger value leads to a weaker hash and more collisions. 93 The largest possible value is 6. 94*/ 95static unsigned mangle_prefix; 96 97/* we will use a very simple direct mapped prefix cache. The big 98 advantage of this cache structure is speed and low memory usage 99 100 The cache is indexed by the low-order bits of the hash, and confirmed by 101 hashing the resulting cache entry to match the known hash 102*/ 103static char **prefix_cache; 104static u32 *prefix_cache_hashes; 105 106/* these are the characters we use in the 8.3 hash. Must be 36 chars long */ 107static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 108static unsigned char base_reverse[256]; 109#define base_forward(v) basechars[v] 110 111/* the list of reserved dos names - all of these are illegal */ 112static const char *reserved_names[] = 113{ "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4", 114 "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL }; 115 116/* 117 hash a string of the specified length. The string does not need to be 118 null terminated 119 120 this hash needs to be fast with a low collision rate (what hash doesn't?) 121*/ 122static u32 mangle_hash(const char *key, unsigned int length) 123{ 124 u32 value; 125 u32 i; 126 fstring str; 127 128 /* we have to uppercase here to ensure that the mangled name 129 doesn't depend on the case of the long name. Note that this 130 is the only place where we need to use a multi-byte string 131 function */ 132 length = MIN(length,sizeof(fstring)-1); 133 strncpy(str, key, length); 134 str[length] = 0; 135 strupper_m(str); 136 137 /* the length of a multi-byte string can change after a strupper_m */ 138 length = strlen(str); 139 140 /* Set the initial value from the key size. */ 141 for (value = FNV1_INIT, i=0; i < length; i++) { 142 value *= (u32)FNV1_PRIME; 143 value ^= (u32)(str[i]); 144 } 145 146 /* note that we force it to a 31 bit hash, to keep within the limits 147 of the 36^6 mangle space */ 148 return value & ~0x80000000; 149} 150 151/* 152 initialise (ie. allocate) the prefix cache 153 */ 154static BOOL cache_init(void) 155{ 156 if (prefix_cache) { 157 return True; 158 } 159 160 prefix_cache = SMB_CALLOC_ARRAY(char *,MANGLE_CACHE_SIZE); 161 if (!prefix_cache) { 162 return False; 163 } 164 165 prefix_cache_hashes = SMB_CALLOC_ARRAY(u32, MANGLE_CACHE_SIZE); 166 if (!prefix_cache_hashes) { 167 return False; 168 } 169 170 return True; 171} 172 173/* 174 insert an entry into the prefix cache. The string might not be null 175 terminated */ 176static void cache_insert(const char *prefix, int length, u32 hash) 177{ 178 int i = hash % MANGLE_CACHE_SIZE; 179 180 if (prefix_cache[i]) { 181 free(prefix_cache[i]); 182 } 183 184 prefix_cache[i] = SMB_STRNDUP(prefix, length); 185 prefix_cache_hashes[i] = hash; 186} 187 188/* 189 lookup an entry in the prefix cache. Return NULL if not found. 190*/ 191static const char *cache_lookup(u32 hash) 192{ 193 int i = hash % MANGLE_CACHE_SIZE; 194 195 if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) { 196 return NULL; 197 } 198 199 /* yep, it matched */ 200 return prefix_cache[i]; 201} 202 203 204/* 205 determine if a string is possibly in a mangled format, ignoring 206 case 207 208 In this algorithm, mangled names use only pure ascii characters (no 209 multi-byte) so we can avoid doing a UCS2 conversion 210 */ 211static BOOL is_mangled_component(const char *name, size_t len) 212{ 213 unsigned int i; 214 215 M_DEBUG(10,("is_mangled_component %s (len %u) ?\n", name, (unsigned int)len)); 216 217 /* check the length */ 218 if (len > 12 || len < 8) 219 return False; 220 221 /* the best distinguishing characteristic is the ~ */ 222 if (name[6] != '~') 223 return False; 224 225 /* check extension */ 226 if (len > 8) { 227 if (name[8] != '.') 228 return False; 229 for (i=9; name[i] && i < len; i++) { 230 if (! FLAG_CHECK(name[i], FLAG_ASCII)) { 231 return False; 232 } 233 } 234 } 235 236 /* check lead characters */ 237 for (i=0;i<mangle_prefix;i++) { 238 if (! FLAG_CHECK(name[i], FLAG_ASCII)) { 239 return False; 240 } 241 } 242 243 /* check rest of hash */ 244 if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) { 245 return False; 246 } 247 for (i=mangle_prefix;i<6;i++) { 248 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) { 249 return False; 250 } 251 } 252 253 M_DEBUG(10,("is_mangled_component %s (len %u) -> yes\n", name, (unsigned int)len)); 254 255 return True; 256} 257 258 259 260/* 261 determine if a string is possibly in a mangled format, ignoring 262 case 263 264 In this algorithm, mangled names use only pure ascii characters (no 265 multi-byte) so we can avoid doing a UCS2 conversion 266 267 NOTE! This interface must be able to handle a path with unix 268 directory separators. It should return true if any component is 269 mangled 270 */ 271static BOOL is_mangled(const char *name) 272{ 273 const char *p; 274 const char *s; 275 276 M_DEBUG(10,("is_mangled %s ?\n", name)); 277 278 for (s=name; (p=strchr(s, '/')); s=p+1) { 279 if (is_mangled_component(s, PTR_DIFF(p, s))) { 280 return True; 281 } 282 } 283 284 /* and the last part ... */ 285 return is_mangled_component(s,strlen(s)); 286} 287 288 289/* 290 see if a filename is an allowable 8.3 name. 291 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) 295*/ 296static BOOL is_8_3(const char *name, BOOL check_case, BOOL allow_wildcards) 297{ 298 int len, i; 299 char *dot_p; 300 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])) { 304 return True; 305 } 306 } 307 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 */ 313 len = strlen(name); 314 if (len > 12) 315 return False; 316 317 /* find the '.'. Note that once again we use the non-multibyte 318 function */ 319 dot_p = strchr(name, '.'); 320 321 if (!dot_p) { 322 /* if the name doesn't contain a '.' then its length 323 must be less than 8 */ 324 if (len > 8) { 325 return False; 326 } 327 } else { 328 int prefix_len, suffix_len; 329 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); 334 335 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) { 336 return False; 337 } 338 339 /* a 8.3 name cannot contain more than 1 '.' */ 340 if (strchr(dot_p+1, '.')) { 341 return False; 342 } 343 } 344 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] != '.') { 349 return False; 350 } 351 } 352 353 /* it is a good 8.3 name */ 354 return True; 355} 356 357 358/* 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 362*/ 363static void mangle_reset(void) 364{ 365 /* noop */ 366} 367 368 369/* 370 try to find a 8.3 name in the cache, and if found then 371 replace the string with the original long name. 372*/ 373static BOOL check_cache(char *name, size_t maxlen) 374{ 375 u32 hash, multiplier; 376 unsigned int i; 377 const char *prefix; 378 char extension[4]; 379 380 /* make sure that this is a mangled name from this cache */ 381 if (!is_mangled(name)) { 382 M_DEBUG(10,("check_cache: %s -> not mangled\n", name)); 383 return False; 384 } 385 386 /* we need to extract the hash from the 8.3 name */ 387 hash = base_reverse[(unsigned char)name[7]]; 388 for (multiplier=36, i=5;i>=mangle_prefix;i--) { 389 u32 v = base_reverse[(unsigned char)name[i]]; 390 hash += multiplier * v; 391 multiplier *= 36; 392 } 393 394 /* now look in the prefix cache for that hash */ 395 prefix = cache_lookup(hash); 396 if (!prefix) { 397 M_DEBUG(10,("check_cache: %s -> %08X -> not found\n", name, hash)); 398 return False; 399 } 400 401 /* we found it - construct the full name */ 402 if (name[8] == '.') { 403 strncpy(extension, name+9, 3); 404 extension[3] = 0; 405 } else { 406 extension[0] = 0; 407 } 408 409 if (extension[0]) { 410 M_DEBUG(10,("check_cache: %s -> %s.%s\n", name, prefix, extension)); 411 slprintf(name, maxlen, "%s.%s", prefix, extension); 412 } else { 413 M_DEBUG(10,("check_cache: %s -> %s\n", name, prefix)); 414 safe_strcpy(name, prefix, maxlen); 415 } 416 417 return True; 418} 419 420 421/* 422 look for a DOS reserved name 423*/ 424static BOOL is_reserved_name(const char *name) 425{ 426 if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) && 427 FLAG_CHECK(name[1], FLAG_POSSIBLE2) && 428 FLAG_CHECK(name[2], FLAG_POSSIBLE3) && 429 FLAG_CHECK(name[3], FLAG_POSSIBLE4)) { 430 /* a likely match, scan the lot */ 431 int i; 432 for (i=0; reserved_names[i]; i++) { 433 int len = strlen(reserved_names[i]); 434 /* note that we match on COM1 as well as COM1.foo */ 435 if (strnequal(name, reserved_names[i], len) && 436 (name[len] == '.' || name[len] == 0)) { 437 return True; 438 } 439 } 440 } 441 442 return False; 443} 444 445/* 446 See if a filename is a legal long filename. 447 A filename ending in a '.' is not legal unless it's "." or "..". JRA. 448*/ 449 450static BOOL is_legal_name(const char *name) 451{ 452 const char *dot_pos = NULL; 453 BOOL alldots = True; 454 size_t numdots = 0; 455 456 while (*name) { 457 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) { 458 /* Possible start of mb character. */ 459 char mbc[2]; 460 /* 461 * Note that if CH_UNIX is utf8 a string may be 3 462 * bytes, but this is ok as mb utf8 characters don't 463 * contain embedded ascii bytes. We are really checking 464 * for mb UNIX asian characters like Japanese (SJIS) here. 465 * JRA. 466 */ 467 if (convert_string(CH_UNIX, CH_UCS2, name, 2, mbc, 2, False) == 2) { 468 /* Was a good mb string. */ 469 name += 2; 470 continue; 471 } 472 } 473 474 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) { 475 return False; 476 } 477 if (name[0] == '.') { 478 dot_pos = name; 479 numdots++; 480 } else { 481 alldots = False; 482 } 483 name++; 484 } 485 486 if (dot_pos) { 487 if (alldots && (numdots == 1 || numdots == 2)) 488 return True; /* . or .. is a valid name */ 489 490 /* A valid long name cannot end in '.' */ 491 if (dot_pos[1] == '\0') 492 return False; 493 } 494 495 return True; 496} 497 498/* 499 the main forward mapping function, which converts a long filename to 500 a 8.3 name 501 502 if need83 is not set then we only do the mangling if the name is illegal 503 as a long name 504 505 if cache83 is not set then we don't cache the result 506 507 the name parameter must be able to hold 13 bytes 508*/ 509static void name_map(fstring name, BOOL need83, BOOL cache83, int default_case) 510{ 511 char *dot_p; 512 char lead_chars[7]; 513 char extension[4]; 514 unsigned int extension_length, i; 515 unsigned int prefix_len; 516 u32 hash, v; 517 char new_name[13]; 518 519 /* reserved names are handled specially */ 520 if (!is_reserved_name(name)) { 521 /* if the name is already a valid 8.3 name then we don't need to 522 do anything */ 523 if (is_8_3(name, False, False)) { 524 return; 525 } 526 527 /* if the caller doesn't strictly need 8.3 then just check for illegal 528 filenames */ 529 if (!need83 && is_legal_name(name)) { 530 return; 531 } 532 } 533 534 /* find the '.' if any */ 535 dot_p = strrchr(name, '.'); 536 537 if (dot_p) { 538 /* if the extension contains any illegal characters or 539 is too long or zero length then we treat it as part 540 of the prefix */ 541 for (i=0; i<4 && dot_p[i+1]; i++) { 542 if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) { 543 dot_p = NULL; 544 break; 545 } 546 } 547 if (i == 0 || i == 4) dot_p = NULL; 548 } 549 550 /* the leading characters in the mangled name is taken from 551 the first characters of the name, if they are ascii otherwise 552 '_' is used 553 */ 554 for (i=0;i<mangle_prefix && name[i];i++) { 555 lead_chars[i] = name[i]; 556 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) { 557 lead_chars[i] = '_'; 558 } 559 lead_chars[i] = toupper(lead_chars[i]); 560 } 561 for (;i<mangle_prefix;i++) { 562 lead_chars[i] = '_'; 563 } 564 565 /* the prefix is anything up to the first dot */ 566 if (dot_p) { 567 prefix_len = PTR_DIFF(dot_p, name); 568 } else { 569 prefix_len = strlen(name); 570 } 571 572 /* the extension of the mangled name is taken from the first 3 573 ascii chars after the dot */ 574 extension_length = 0; 575 if (dot_p) { 576 for (i=1; extension_length < 3 && dot_p[i]; i++) { 577 char c = dot_p[i]; 578 if (FLAG_CHECK(c, FLAG_ASCII)) { 579 extension[extension_length++] = toupper(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,("name_map: %s -> %08X -> %s (cache=%d)\n", 613 name, hash, new_name, cache83)); 614 615 /* and overwrite the old name */ 616 fstrcpy(name, new_name); 617 618 /* all done, we've managed to mangle it */ 619} 620 621 622/* initialise the flags table 623 624 we allow only a very restricted set of characters as 'ascii' in this 625 mangling backend. This isn't a significant problem as modern clients 626 use the 'long' filenames anyway, and those don't have these 627 restrictions. 628*/ 629static void init_tables(void) 630{ 631 int i; 632 633 memset(char_flags, 0, sizeof(char_flags)); 634 635 for (i=1;i<128;i++) { 636 if ((i >= '0' && i <= '9') || 637 (i >= 'a' && i <= 'z') || 638 (i >= 'A' && i <= 'Z')) { 639 char_flags[i] |= (FLAG_ASCII | FLAG_BASECHAR); 640 } 641 if (strchr("_-$~", i)) { 642 char_flags[i] |= FLAG_ASCII; 643 } 644 645 if (strchr("*\\/?<>|\":", i)) { 646 char_flags[i] |= FLAG_ILLEGAL; 647 } 648 649 if (strchr("*?\"<>", i)) { 650 char_flags[i] |= FLAG_WILDCARD; 651 } 652 } 653 654 memset(base_reverse, 0, sizeof(base_reverse)); 655 for (i=0;i<36;i++) { 656 base_reverse[(unsigned char)base_forward(i)] = i; 657 } 658 659 /* fill in the reserved names flags. These are used as a very 660 fast filter for finding possible DOS reserved filenames */ 661 for (i=0; reserved_names[i]; i++) { 662 unsigned char c1, c2, c3, c4; 663 664 c1 = (unsigned char)reserved_names[i][0]; 665 c2 = (unsigned char)reserved_names[i][1]; 666 c3 = (unsigned char)reserved_names[i][2]; 667 c4 = (unsigned char)reserved_names[i][3]; 668 669 char_flags[c1] |= FLAG_POSSIBLE1; 670 char_flags[c2] |= FLAG_POSSIBLE2; 671 char_flags[c3] |= FLAG_POSSIBLE3; 672 char_flags[c4] |= FLAG_POSSIBLE4; 673 char_flags[tolower(c1)] |= FLAG_POSSIBLE1; 674 char_flags[tolower(c2)] |= FLAG_POSSIBLE2; 675 char_flags[tolower(c3)] |= FLAG_POSSIBLE3; 676 char_flags[tolower(c4)] |= FLAG_POSSIBLE4; 677 678 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4; 679 } 680} 681 682 683/* 684 the following provides the abstraction layer to make it easier 685 to drop in an alternative mangling implementation */ 686static struct mangle_fns mangle_fns = { 687 is_mangled, 688 is_8_3, 689 mangle_reset, 690 check_cache, 691 name_map 692}; 693 694/* return the methods for this mangling implementation */ 695struct mangle_fns *mangle_hash2_init(void) 696{ 697 /* the mangle prefix can only be in the mange 1 to 6 */ 698 mangle_prefix = lp_mangle_prefix(); 699 if (mangle_prefix > 6) { 700 mangle_prefix = 6; 701 } 702 if (mangle_prefix < 1) { 703 mangle_prefix = 1; 704 } 705 706 init_tables(); 707 mangle_reset(); 708 709 if (!cache_init()) { 710 return NULL; 711 } 712 713 return &mangle_fns; 714} 715