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