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