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