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