source3/smbd/mangle_hash2.c

   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 */
  86 static 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 */
  95 static 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 */
 103 static char **prefix_cache;
 104 static u32 *prefix_cache_hashes;
 105
 106 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
 107 static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 108 static 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 */
 112 static 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 */
 122 static 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  */
 154 static BOOL cache_init(void)
 155 {
 156         if (prefix_cache) return True;
 157
 158         prefix_cache = calloc(MANGLE_CACHE_SIZE, sizeof(char *));
 159         if (!prefix_cache) return False;
 160
 161         prefix_cache_hashes = calloc(MANGLE_CACHE_SIZE, sizeof(u32));
 162         if (!prefix_cache_hashes) return False;
 163
 164         return True;
 165 }
 166
 167 /*
 168   insert an entry into the prefix cache. The string might not be null
 169   terminated */
 170 static void cache_insert(const char *prefix, int length, u32 hash)
 171 {
 172         int i = hash % MANGLE_CACHE_SIZE;
 173
 174         if (prefix_cache[i]) {
 175                 free(prefix_cache[i]);
 176         }
 177
 178         prefix_cache[i] = strndup(prefix, length);
 179         prefix_cache_hashes[i] = hash;
 180 }
 181
 182 /*
 183   lookup an entry in the prefix cache. Return NULL if not found.
 184 */
 185 static const char *cache_lookup(u32 hash)
 186 {
 187         int i = hash % MANGLE_CACHE_SIZE;
 188
 189         if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
 190                 return NULL;
 191         }
 192
 193         /* yep, it matched */
 194         return prefix_cache[i];
 195 }
 196
 197
 198 /*
 199    determine if a string is possibly in a mangled format, ignoring
 200    case
 201
 202    In this algorithm, mangled names use only pure ascii characters (no
 203    multi-byte) so we can avoid doing a UCS2 conversion
 204  */
 205 static BOOL is_mangled_component(const char *name, size_t len)
 206 {
 207         unsigned int i;
 208
 209         M_DEBUG(10,("is_mangled_component %s (len %u) ?\n", name, (unsigned int)len));
 210
 211         /* check the length */
 212         if (len > 12 || len < 8)
 213                 return False;
 214
 215         /* the best distinguishing characteristic is the ~ */
 216         if (name[6] != '~')
 217                 return False;
 218
 219         /* check extension */
 220         if (len > 8) {
 221                 if (name[8] != '.')
 222                         return False;
 223                 for (i=9; name[i] && i < len; i++) {
 224                         if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
 225                                 return False;
 226                         }
 227                 }
 228         }
 229
 230         /* check lead characters */
 231         for (i=0;i<mangle_prefix;i++) {
 232                 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
 233                         return False;
 234                 }
 235         }
 236
 237         /* check rest of hash */
 238         if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
 239                 return False;
 240         }
 241         for (i=mangle_prefix;i<6;i++) {
 242                 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
 243                         return False;
 244                 }
 245         }
 246
 247         M_DEBUG(10,("is_mangled_component %s (len %u) -> yes\n", name, (unsigned int)len));
 248
 249         return True;
 250 }
 251
 252
 253
 254 /*
 255    determine if a string is possibly in a mangled format, ignoring
 256    case
 257
 258    In this algorithm, mangled names use only pure ascii characters (no
 259    multi-byte) so we can avoid doing a UCS2 conversion
 260
 261    NOTE! This interface must be able to handle a path with unix
 262    directory separators. It should return true if any component is
 263    mangled
 264  */
 265 static BOOL is_mangled(const char *name)
 266 {
 267         const char *p;
 268         const char *s;
 269
 270         M_DEBUG(10,("is_mangled %s ?\n", name));
 271
 272         for (s=name; (p=strchr(s, '/')); s=p+1) {
 273                 if (is_mangled_component(s, PTR_DIFF(p, s))) {
 274                         return True;
 275                 }
 276         }
 277
 278         /* and the last part ... */
 279         return is_mangled_component(s,strlen(s));
 280 }
 281
 282
 283 /*
 284    see if a filename is an allowable 8.3 name.
 285
 286    we are only going to allow ascii characters in 8.3 names, as this
 287    simplifies things greatly (it means that we know the string won't
 288    get larger when converted from UNIX to DOS formats)
 289 */
 290 static BOOL is_8_3(const char *name, BOOL check_case, BOOL allow_wildcards)
 291 {
 292         int len, i;
 293         char *dot_p;
 294
 295         /* as a special case, the names '.' and '..' are allowable 8.3 names */
 296         if (name[0] == '.') {
 297                 if (!name[1] || (name[1] == '.' && !name[2])) {
 298                         return True;
 299                 }
 300         }
 301
 302         /* the simplest test is on the overall length of the
 303          filename. Note that we deliberately use the ascii string
 304          length (not the multi-byte one) as it is faster, and gives us
 305          the result we need in this case. Using strlen_m would not
 306          only be slower, it would be incorrect */
 307         len = strlen(name);
 308         if (len > 12)
 309                 return False;
 310
 311         /* find the '.'. Note that once again we use the non-multibyte
 312            function */
 313         dot_p = strchr(name, '.');
 314
 315         if (!dot_p) {
 316                 /* if the name doesn't contain a '.' then its length
 317                    must be less than 8 */
 318                 if (len > 8) {
 319                         return False;
 320                 }
 321         } else {
 322                 int prefix_len, suffix_len;
 323
 324                 /* if it does contain a dot then the prefix must be <=
 325                    8 and the suffix <= 3 in length */
 326                 prefix_len = PTR_DIFF(dot_p, name);
 327                 suffix_len = len - (prefix_len+1);
 328
 329                 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
 330                         return False;
 331                 }
 332
 333                 /* a 8.3 name cannot contain more than 1 '.' */
 334                 if (strchr(dot_p+1, '.')) {
 335                         return False;
 336                 }
 337         }
 338
 339         /* the length are all OK. Now check to see if the characters themselves are OK */
 340         for (i=0; name[i]; i++) {
 341                 /* note that we may allow wildcard petterns! */
 342                 if (!FLAG_CHECK(name[i], FLAG_ASCII|(allow_wildcards ? FLAG_WILDCARD : 0)) && name[i] != '.') {
 343                         return False;
 344                 }
 345         }
 346
 347         /* it is a good 8.3 name */
 348         return True;
 349 }
 350
 351
 352 /*
 353   reset the mangling cache on a smb.conf reload. This only really makes sense for
 354   mangling backends that have parameters in smb.conf, and as this backend doesn't
 355   this is a NULL operation
 356 */
 357 static void mangle_reset(void)
 358 {
 359         /* noop */
 360 }
 361
 362
 363 /*
 364   try to find a 8.3 name in the cache, and if found then
 365   replace the string with the original long name.
 366 */
 367 static BOOL check_cache(char *name, size_t maxlen)
 368 {
 369         u32 hash, multiplier;
 370         unsigned int i;
 371         const char *prefix;
 372         char extension[4];
 373
 374         /* make sure that this is a mangled name from this cache */
 375         if (!is_mangled(name)) {
 376                 M_DEBUG(10,("check_cache: %s -> not mangled\n", name));
 377                 return False;
 378         }
 379
 380         /* we need to extract the hash from the 8.3 name */
 381         hash = base_reverse[(unsigned char)name[7]];
 382         for (multiplier=36, i=5;i>=mangle_prefix;i--) {
 383                 u32 v = base_reverse[(unsigned char)name[i]];
 384                 hash += multiplier * v;
 385                 multiplier *= 36;
 386         }
 387
 388         /* now look in the prefix cache for that hash */
 389         prefix = cache_lookup(hash);
 390         if (!prefix) {
 391                 M_DEBUG(10,("check_cache: %s -> %08X -> not found\n", name, hash));
 392                 return False;
 393         }
 394
 395         /* we found it - construct the full name */
 396         if (name[8] == '.') {
 397                 strncpy(extension, name+9, 3);
 398                 extension[3] = 0;
 399         } else {
 400                 extension[0] = 0;
 401         }
 402
 403         if (extension[0]) {
 404                 M_DEBUG(10,("check_cache: %s -> %s.%s\n", name, prefix, extension));
 405                 slprintf(name, maxlen, "%s.%s", prefix, extension);
 406         } else {
 407                 M_DEBUG(10,("check_cache: %s -> %s\n", name, prefix));
 408                 safe_strcpy(name, prefix, maxlen);
 409         }
 410
 411         return True;
 412 }
 413
 414
 415 /*
 416   look for a DOS reserved name
 417 */
 418 static BOOL is_reserved_name(const char *name)
 419 {
 420         if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
 421             FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
 422             FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
 423             FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
 424                 /* a likely match, scan the lot */
 425                 int i;
 426                 for (i=0; reserved_names[i]; i++) {
 427                         int len = strlen(reserved_names[i]);
 428                         /* note that we match on COM1 as well as COM1.foo */
 429                         if (strnequal(name, reserved_names[i], len) &&
 430                             (name[len] == '.' || name[len] == 0)) {
 431                                 return True;
 432                         }
 433                 }
 434         }
 435
 436         return False;
 437 }
 438
 439 /*
 440  See if a filename is a legal long filename.
 441  A filename ending in a '.' is not legal unless it's "." or "..". JRA.
 442 */
 443
 444 static BOOL is_legal_name(const char *name)
 445 {
 446         const char *dot_pos = NULL;
 447         BOOL alldots = True;
 448         size_t numdots = 0;
 449
 450         while (*name) {
 451                 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
 452                         /* Possible start of mb character. */
 453                         char mbc[2];
 454                         /*
 455                          * Note that if CH_UNIX is utf8 a string may be 3
 456                          * bytes, but this is ok as mb utf8 characters don't
 457                          * contain embedded ascii bytes. We are really checking
 458                          * for mb UNIX asian characters like Japanese (SJIS) here.
 459                          * JRA.
 460                          */
 461                         if (convert_string(CH_UNIX, CH_UCS2, name, 2, mbc, 2, False) == 2) {
 462                                 /* Was a good mb string. */
 463                                 name += 2;
 464                                 continue;
 465                         }
 466                 }
 467
 468                 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
 469                         return False;
 470                 }
 471                 if (name[0] == '.') {
 472                         dot_pos = name;
 473                         numdots++;
 474                 } else {
 475                         alldots = False;
 476                 }
 477                 name++;
 478         }
 479
 480         if (dot_pos) {
 481                 if (alldots && (numdots == 1 || numdots == 2))
 482                         return True; /* . or .. is a valid name */
 483
 484                 /* A valid long name cannot end in '.' */
 485                 if (dot_pos[1] == '\0')
 486                         return False;
 487         }
 488
 489         return True;
 490 }
 491
 492 /*
 493   the main forward mapping function, which converts a long filename to
 494   a 8.3 name
 495
 496   if need83 is not set then we only do the mangling if the name is illegal
 497   as a long name
 498
 499   if cache83 is not set then we don't cache the result
 500
 501   the name parameter must be able to hold 13 bytes
 502 */
 503 static void name_map(fstring name, BOOL need83, BOOL cache83, int default_case)
 504 {
 505         char *dot_p;
 506         char lead_chars[7];
 507         char extension[4];
 508         unsigned int extension_length, i;
 509         unsigned int prefix_len;
 510         u32 hash, v;
 511         char new_name[13];
 512
 513         /* reserved names are handled specially */
 514         if (!is_reserved_name(name)) {
 515                 /* if the name is already a valid 8.3 name then we don't need to
 516                    do anything */
 517                 if (is_8_3(name, False, False)) {
 518                         return;
 519                 }
 520
 521                 /* if the caller doesn't strictly need 8.3 then just check for illegal
 522                    filenames */
 523                 if (!need83 && is_legal_name(name)) {
 524                         return;
 525                 }
 526         }
 527
 528         /* find the '.' if any */
 529         dot_p = strrchr(name, '.');
 530
 531         if (dot_p) {
 532                 /* if the extension contains any illegal characters or
 533                    is too long or zero length then we treat it as part
 534                    of the prefix */
 535                 for (i=0; i<4 && dot_p[i+1]; i++) {
 536                         if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
 537                                 dot_p = NULL;
 538                                 break;
 539                         }
 540                 }
 541                 if (i == 0 || i == 4) dot_p = NULL;
 542         }
 543
 544         /* the leading characters in the mangled name is taken from
 545            the first characters of the name, if they are ascii otherwise
 546            '_' is used
 547         */
 548         for (i=0;i<mangle_prefix && name[i];i++) {
 549                 lead_chars[i] = name[i];
 550                 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
 551                         lead_chars[i] = '_';
 552                 }
 553                 lead_chars[i] = toupper(lead_chars[i]);
 554         }
 555         for (;i<mangle_prefix;i++) {
 556                 lead_chars[i] = '_';
 557         }
 558
 559         /* the prefix is anything up to the first dot */
 560         if (dot_p) {
 561                 prefix_len = PTR_DIFF(dot_p, name);
 562         } else {
 563                 prefix_len = strlen(name);
 564         }
 565
 566         /* the extension of the mangled name is taken from the first 3
 567            ascii chars after the dot */
 568         extension_length = 0;
 569         if (dot_p) {
 570                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
 571                         char c = dot_p[i];
 572                         if (FLAG_CHECK(c, FLAG_ASCII)) {
 573                                 extension[extension_length++] = toupper(c);
 574                         }
 575                 }
 576         }
 577
 578         /* find the hash for this prefix */
 579         v = hash = mangle_hash(name, prefix_len);
 580
 581         /* now form the mangled name. */
 582         for (i=0;i<mangle_prefix;i++) {
 583                 new_name[i] = lead_chars[i];
 584         }
 585         new_name[7] = base_forward(v % 36);
 586         new_name[6] = '~';
 587         for (i=5; i>=mangle_prefix; i--) {
 588                 v = v / 36;
 589                 new_name[i] = base_forward(v % 36);
 590         }
 591
 592         /* add the extension */
 593         if (extension_length) {
 594                 new_name[8] = '.';
 595                 memcpy(&new_name[9], extension, extension_length);
 596                 new_name[9+extension_length] = 0;
 597         } else {
 598                 new_name[8] = 0;
 599         }
 600
 601         if (cache83) {
 602                 /* put it in the cache */
 603                 cache_insert(name, prefix_len, hash);
 604         }
 605
 606         M_DEBUG(10,("name_map: %s -> %08X -> %s (cache=%d)\n",
 607                    name, hash, new_name, cache83));
 608
 609         /* and overwrite the old name */
 610         fstrcpy(name, new_name);
 611
 612         /* all done, we've managed to mangle it */
 613 }
 614
 615
 616 /* initialise the flags table
 617
 618   we allow only a very restricted set of characters as 'ascii' in this
 619   mangling backend. This isn't a significant problem as modern clients
 620   use the 'long' filenames anyway, and those don't have these
 621   restrictions.
 622 */
 623 static void init_tables(void)
 624 {
 625         int i;
 626
 627         memset(char_flags, 0, sizeof(char_flags));
 628
 629         for (i=1;i<128;i++) {
 630                 if ((i >= '0' && i <= '9') ||
 631                     (i >= 'a' && i <= 'z') ||
 632                     (i >= 'A' && i <= 'Z')) {
 633                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
 634                 }
 635                 if (strchr("_-$~", i)) {
 636                         char_flags[i] |= FLAG_ASCII;
 637                 }
 638
 639                 if (strchr("*\\/?<>|\":", i)) {
 640                         char_flags[i] |= FLAG_ILLEGAL;
 641                 }
 642
 643                 if (strchr("*?\"<>", i)) {
 644                         char_flags[i] |= FLAG_WILDCARD;
 645                 }
 646         }
 647
 648         memset(base_reverse, 0, sizeof(base_reverse));
 649         for (i=0;i<36;i++) {
 650                 base_reverse[(unsigned char)base_forward(i)] = i;
 651         }
 652
 653         /* fill in the reserved names flags. These are used as a very
 654            fast filter for finding possible DOS reserved filenames */
 655         for (i=0; reserved_names[i]; i++) {
 656                 unsigned char c1, c2, c3, c4;
 657
 658                 c1 = (unsigned char)reserved_names[i][0];
 659                 c2 = (unsigned char)reserved_names[i][1];
 660                 c3 = (unsigned char)reserved_names[i][2];
 661                 c4 = (unsigned char)reserved_names[i][3];
 662
 663                 char_flags[c1] |= FLAG_POSSIBLE1;
 664                 char_flags[c2] |= FLAG_POSSIBLE2;
 665                 char_flags[c3] |= FLAG_POSSIBLE3;
 666                 char_flags[c4] |= FLAG_POSSIBLE4;
 667                 char_flags[tolower(c1)] |= FLAG_POSSIBLE1;
 668                 char_flags[tolower(c2)] |= FLAG_POSSIBLE2;
 669                 char_flags[tolower(c3)] |= FLAG_POSSIBLE3;
 670                 char_flags[tolower(c4)] |= FLAG_POSSIBLE4;
 671
 672                 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
 673         }
 674 }
 675
 676
 677 /*
 678   the following provides the abstraction layer to make it easier
 679   to drop in an alternative mangling implementation */
 680 static struct mangle_fns mangle_fns = {
 681         is_mangled,
 682         is_8_3,
 683         mangle_reset,
 684         check_cache,
 685         name_map
 686 };
 687
 688 /* return the methods for this mangling implementation */
 689 struct mangle_fns *mangle_hash2_init(void)
 690 {
 691         /* the mangle prefix can only be in the mange 1 to 6 */
 692         mangle_prefix = lp_mangle_prefix();
 693         if (mangle_prefix > 6) {
 694                 mangle_prefix = 6;
 695         }
 696         if (mangle_prefix < 1) {
 697                 mangle_prefix = 1;
 698         }
 699
 700         init_tables();
 701         mangle_reset();
 702
 703         if (!cache_init()) {
 704                 return NULL;
 705         }
 706
 707         return &mangle_fns;
 708 }