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