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 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 < len; 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)
 308                 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 || suffix_len == 0) {
 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 (strnequal(name, reserved_names[i], len) &&
 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 (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
 453                         /* Possible start of mb character. */
 454                         char mbc[2];
 455                         /*
 456                          * Note that if CH_UNIX is utf8 a string may be 3
 457                          * bytes, but this is ok as mb utf8 characters don't
 458                          * contain embedded ascii bytes. We are really checking
 459                          * for mb UNIX asian characters like Japanese (SJIS) here.
 460                          * JRA.
 461                          */
 462                         if (convert_string(CH_UNIX, CH_UCS2, name, 2, mbc, 2, False) == 2) {
 463                                 /* Was a good mb string. */
 464                                 name += 2;
 465                                 continue;
 466                         }
 467                 }
 468
 469                 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
 470                         return False;
 471                 }
 472                 if (name[0] == '.') {
 473                         dot_pos = name;
 474                         numdots++;
 475                 } else {
 476                         alldots = False;
 477                 }
 478                 name++;
 479         }
 480
 481         if (dot_pos) {
 482                 if (alldots && (numdots == 1 || numdots == 2))
 483                         return True; /* . or .. is a valid name */
 484
 485                 /* A valid long name cannot end in '.' */
 486                 if (dot_pos[1] == '\0')
 487                         return False;
 488         }
 489
 490         return True;
 491 }
 492
 493 /*
 494   the main forward mapping function, which converts a long filename to
 495   a 8.3 name
 496
 497   if need83 is not set then we only do the mangling if the name is illegal
 498   as a long name
 499
 500   if cache83 is not set then we don't cache the result
 501
 502   the name parameter must be able to hold 13 bytes
 503 */
 504 static void name_map(fstring name, BOOL need83, BOOL cache83)
 505 {
 506         char *dot_p;
 507         char lead_chars[7];
 508         char extension[4];
 509         unsigned int extension_length, i;
 510         unsigned int prefix_len;
 511         u32 hash, v;
 512         char new_name[13];
 513
 514         /* reserved names are handled specially */
 515         if (!is_reserved_name(name)) {
 516                 /* if the name is already a valid 8.3 name then we don't need to
 517                    do anything */
 518                 if (is_8_3(name, False, False)) {
 519                         return;
 520                 }
 521
 522                 /* if the caller doesn't strictly need 8.3 then just check for illegal
 523                    filenames */
 524                 if (!need83 && is_legal_name(name)) {
 525                         return;
 526                 }
 527         }
 528
 529         /* find the '.' if any */
 530         dot_p = strrchr(name, '.');
 531
 532         if (dot_p) {
 533                 /* if the extension contains any illegal characters or
 534                    is too long or zero length then we treat it as part
 535                    of the prefix */
 536                 for (i=0; i<4 && dot_p[i+1]; i++) {
 537                         if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
 538                                 dot_p = NULL;
 539                                 break;
 540                         }
 541                 }
 542                 if (i == 0 || i == 4) dot_p = NULL;
 543         }
 544
 545         /* the leading characters in the mangled name is taken from
 546            the first characters of the name, if they are ascii otherwise
 547            '_' is used
 548         */
 549         for (i=0;i<mangle_prefix && name[i];i++) {
 550                 lead_chars[i] = name[i];
 551                 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
 552                         lead_chars[i] = '_';
 553                 }
 554                 lead_chars[i] = toupper(lead_chars[i]);
 555         }
 556         for (;i<mangle_prefix;i++) {
 557                 lead_chars[i] = '_';
 558         }
 559
 560         /* the prefix is anything up to the first dot */
 561         if (dot_p) {
 562                 prefix_len = PTR_DIFF(dot_p, name);
 563         } else {
 564                 prefix_len = strlen(name);
 565         }
 566
 567         /* the extension of the mangled name is taken from the first 3
 568            ascii chars after the dot */
 569         extension_length = 0;
 570         if (dot_p) {
 571                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
 572                         char c = dot_p[i];
 573                         if (FLAG_CHECK(c, FLAG_ASCII)) {
 574                                 extension[extension_length++] = toupper(c);
 575                         }
 576                 }
 577         }
 578
 579         /* find the hash for this prefix */
 580         v = hash = mangle_hash(name, prefix_len);
 581
 582         /* now form the mangled name. */
 583         for (i=0;i<mangle_prefix;i++) {
 584                 new_name[i] = lead_chars[i];
 585         }
 586         new_name[7] = base_forward(v % 36);
 587         new_name[6] = '~';
 588         for (i=5; i>=mangle_prefix; i--) {
 589                 v = v / 36;
 590                 new_name[i] = base_forward(v % 36);
 591         }
 592
 593         /* add the extension */
 594         if (extension_length) {
 595                 new_name[8] = '.';
 596                 memcpy(&new_name[9], extension, extension_length);
 597                 new_name[9+extension_length] = 0;
 598         } else {
 599                 new_name[8] = 0;
 600         }
 601
 602         if (cache83) {
 603                 /* put it in the cache */
 604                 cache_insert(name, prefix_len, hash);
 605         }
 606
 607         M_DEBUG(10,("name_map: %s -> %08X -> %s (cache=%d)\n",
 608                    name, hash, new_name, cache83));
 609
 610         /* and overwrite the old name */
 611         fstrcpy(name, new_name);
 612
 613         /* all done, we've managed to mangle it */
 614 }
 615
 616
 617 /* initialise the flags table
 618
 619   we allow only a very restricted set of characters as 'ascii' in this
 620   mangling backend. This isn't a significant problem as modern clients
 621   use the 'long' filenames anyway, and those don't have these
 622   restrictions.
 623 */
 624 static void init_tables(void)
 625 {
 626         int i;
 627
 628         memset(char_flags, 0, sizeof(char_flags));
 629
 630         for (i=1;i<128;i++) {
 631                 if ((i >= '0' && i <= '9') ||
 632                     (i >= 'a' && i <= 'z') ||
 633                     (i >= 'A' && i <= 'Z')) {
 634                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
 635                 }
 636                 if (strchr("_-$~", i)) {
 637                         char_flags[i] |= FLAG_ASCII;
 638                 }
 639
 640                 if (strchr("*\\/?<>|\":", i)) {
 641                         char_flags[i] |= FLAG_ILLEGAL;
 642                 }
 643
 644                 if (strchr("*?\"<>", i)) {
 645                         char_flags[i] |= FLAG_WILDCARD;
 646                 }
 647         }
 648
 649         memset(base_reverse, 0, sizeof(base_reverse));
 650         for (i=0;i<36;i++) {
 651                 base_reverse[(unsigned char)base_forward(i)] = i;
 652         }
 653
 654         /* fill in the reserved names flags. These are used as a very
 655            fast filter for finding possible DOS reserved filenames */
 656         for (i=0; reserved_names[i]; i++) {
 657                 unsigned char c1, c2, c3, c4;
 658
 659                 c1 = (unsigned char)reserved_names[i][0];
 660                 c2 = (unsigned char)reserved_names[i][1];
 661                 c3 = (unsigned char)reserved_names[i][2];
 662                 c4 = (unsigned char)reserved_names[i][3];
 663
 664                 char_flags[c1] |= FLAG_POSSIBLE1;
 665                 char_flags[c2] |= FLAG_POSSIBLE2;
 666                 char_flags[c3] |= FLAG_POSSIBLE3;
 667                 char_flags[c4] |= FLAG_POSSIBLE4;
 668                 char_flags[tolower(c1)] |= FLAG_POSSIBLE1;
 669                 char_flags[tolower(c2)] |= FLAG_POSSIBLE2;
 670                 char_flags[tolower(c3)] |= FLAG_POSSIBLE3;
 671                 char_flags[tolower(c4)] |= FLAG_POSSIBLE4;
 672
 673                 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
 674         }
 675 }
 676
 677
 678 /*
 679   the following provides the abstraction layer to make it easier
 680   to drop in an alternative mangling implementation */
 681 static struct mangle_fns mangle_fns = {
 682         is_mangled,
 683         is_8_3,
 684         mangle_reset,
 685         check_cache,
 686         name_map
 687 };
 688
 689 /* return the methods for this mangling implementation */
 690 struct mangle_fns *mangle_hash2_init(void)
 691 {
 692         /* the mangle prefix can only be in the mange 1 to 6 */
 693         mangle_prefix = lp_mangle_prefix();
 694         if (mangle_prefix > 6) {
 695                 mangle_prefix = 6;
 696         }
 697         if (mangle_prefix < 1) {
 698                 mangle_prefix = 1;
 699         }
 700
 701         init_tables();
 702         mangle_reset();
 703
 704         if (!cache_init()) {
 705                 return NULL;
 706         }
 707
 708         return &mangle_fns;
 709 }