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