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