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