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
  52 #define FLAG_BASECHAR 1
  53 #define FLAG_ASCII 2
  54 #define FLAG_ILLEGAL 4
  55 #define FLAG_POSSIBLE1 8
  56 #define FLAG_POSSIBLE2 16
  57 #define FLAG_POSSIBLE3 32
  58
  59 #define CACHE_SIZE 8192
  60
  61 /* these tables are used to provide fast tests for characters */
  62 static unsigned char char_flags[256];
  63
  64 /* we will use a very simple direct mapped prefix cache. The big
  65    advantage of this cache structure is speed and low memory usage
  66
  67    The cache is indexed by the low-order bits of the hash, and confirmed by
  68    hashing the resulting cache entry to match the known hash
  69 */
  70 static char **prefix_cache;
  71
  72 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
  73 const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  74 static unsigned char base_reverse[256];
  75 #define base_forward(v) basechars[v]
  76
  77 /* the list of reserved dos names - all of these are illegal */
  78 const char *reserved_names[] = { "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4",
  79                                  "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
  80
  81 /*
  82    hash a string of the specified length. The string does not need to be
  83    null terminated
  84
  85    this hash needs to be fast with a low collision rate (what hash doesn't?)
  86 */
  87 static u32 mangle_hash(const char *key, unsigned length)
  88 {
  89         u32 value;
  90         u32   i;
  91         fstring str;
  92
  93         strncpy(str, key, length);
  94         str[length] = 0;
  95         strupper_m(str);
  96
  97         /* the length of a multi-byte string can change after a strupper */
  98         length = strlen(str);
  99
 100         /* Set the initial value from the key size. */
 101         for (value = 0x238F13AF * length, i=0; i < length; i++) {
 102                 value = (value + (((unsigned char)str[i]) << (i*5 % 24)));
 103         }
 104
 105         return (1103515243 * value + 12345);
 106 }
 107
 108 /*
 109    initialise the prefix cache
 110  */
 111 static BOOL cache_init(void)
 112 {
 113         if (prefix_cache) return True;
 114
 115         prefix_cache = malloc(sizeof(char *) * CACHE_SIZE);
 116         if (!prefix_cache) return False;
 117
 118         memset(prefix_cache, 0, sizeof(char *) * CACHE_SIZE);
 119         return True;
 120 }
 121
 122 /*
 123   insert an entry into the prefix cache. The string may not be null terminated
 124 */
 125 static void cache_insert(const char *prefix, int length, u32 hash)
 126 {
 127         int i = hash % CACHE_SIZE;
 128
 129         if (prefix_cache[i]) {
 130                 free(prefix_cache[i]);
 131         }
 132
 133         prefix_cache[i] = strndup(prefix, length);
 134 }
 135
 136 /*
 137   lookup an entry in the prefix cache. Return NULL if not found.
 138 */
 139 static const char *cache_lookup(u32 hash)
 140 {
 141         int i = hash % CACHE_SIZE;
 142
 143         if (!prefix_cache[i]) return NULL;
 144
 145         /* we have a possible match - compute the hash to confirm */
 146         if (hash != mangle_hash(prefix_cache[i], strlen(prefix_cache[i]))) {
 147                 return NULL;
 148         }
 149
 150         /* yep, it matched */
 151         return prefix_cache[i];
 152 }
 153
 154
 155 /*
 156    determine if a string is possibly in a mangled format, ignoring
 157    case
 158
 159    In this algorithm, mangled names use only pure ascii characters (no
 160    multi-byte) so we can avoid doing a UCS2 conversion
 161 */
 162 static BOOL is_mangled(const char *name)
 163 {
 164         /* the best distinguishing characteristic is the ~ */
 165         if (name[6] != '~') return False;
 166
 167         /* check extension */
 168         /* check first character */
 169         /* check rest of hash */
 170
 171         return True;
 172 }
 173
 174
 175 /*
 176    see if a filename is an allowable 8.3 name.
 177
 178    we are only going to allow ascii characters in 8.3 names, as this
 179    simplifies things greatly (it means that we know the string won't
 180    get larger when converted from UNIX to DOS formats)
 181 */
 182 static BOOL is_8_3(const char *name, BOOL check_case)
 183 {
 184         int len, i;
 185         char *dot_p;
 186
 187         /* as a special case, the names '.' and '..' are allowable 8.3 names */
 188         if (name[0] == '.') {
 189                 if (!name[1] || (name[1] == '.' && !name[2])) {
 190                         return True;
 191                 }
 192         }
 193
 194         /* the simplest test is on the overall length of the
 195          filename. Note that we deliberately use the ascii string
 196          length (not the multi-byte one) as it is faster, and gives us
 197          the result we need in this case. Using strlen_m would not
 198          only be slower, it would be incorrect */
 199         len = strlen(name);
 200         if (len > 12) return False;
 201
 202         /* find the '.'. Note that once again we use the non-multibyte
 203            function */
 204         dot_p = strchr(name, '.');
 205
 206         if (!dot_p) {
 207                 /* if the name doesn't contain a '.' then its length
 208                    must be less than 8 */
 209                 if (len > 8) {
 210                         return False;
 211                 }
 212         } else {
 213                 int prefix_len, suffix_len;
 214
 215                 /* if it does contain a dot then the prefix must be <=
 216                    8 and the suffix <= 3 in length */
 217                 prefix_len = PTR_DIFF(dot_p, name);
 218                 suffix_len = len - (prefix_len+1);
 219
 220                 if (prefix_len > 8 || suffix_len > 3) {
 221                         return False;
 222                 }
 223
 224                 /* a 8.3 name cannot contain more than 1 '.' */
 225                 if (strchr(dot_p+1, '.')) {
 226                         return False;
 227                 }
 228         }
 229
 230         /* the length are all OK. Now check to see if the characters themselves are OK */
 231         for (i=0; name[i]; i++) {
 232                 if (!(char_flags[(unsigned)(name[i])] & FLAG_ASCII)) {
 233                         return False;
 234                 }
 235         }
 236
 237         /* it is a good 8.3 name */
 238         return True;
 239 }
 240
 241
 242 /*
 243   reset the mangling cache on a smb.conf reload. This only really makes sense for
 244   mangling backends that have parameters in smb.conf, and as this backend doesn't
 245   this is a NULL operation
 246 */
 247 static void mangle_reset(void)
 248 {
 249         /* noop */
 250 }
 251
 252
 253 /*
 254   try to find a 8.3 name in the cache, and if found then
 255   replace the string with the original long name.
 256
 257   The filename must be able to hold at least sizeof(fstring)
 258 */
 259 static BOOL check_cache(char *name)
 260 {
 261         u32 hash, multiplier;
 262         int i;
 263         const char *prefix;
 264         char extension[4];
 265
 266         /* make sure that this is a mangled name from this cache */
 267         if (!is_mangled(name)) {
 268                 return False;
 269         }
 270
 271         /* we need to extract the hash from the 8.3 name */
 272         hash = base_reverse[(unsigned char)name[7]];
 273         for (multiplier=36, i=5;i>=1;i--) {
 274                 u32 v = base_reverse[(unsigned char)name[i]];
 275                 hash += multiplier * v;
 276                 multiplier *= 36;
 277         }
 278
 279         /* now look in the prefix cache for that hash */
 280         prefix = cache_lookup(hash);
 281         if (!prefix) {
 282                 return False;
 283         }
 284
 285         /* we found it - construct the full name */
 286         strncpy(extension, name+9, 3);
 287
 288         if (extension[0]) {
 289                 slprintf(name, sizeof(fstring), "%s.%s", prefix, extension);
 290         } else {
 291                 fstrcpy(name, prefix);
 292         }
 293         return True;
 294 }
 295
 296
 297 /*
 298   look for a DOS reserved name
 299 */
 300 static BOOL is_reserved_name(const char *name)
 301 {
 302         if ((char_flags[(unsigned char)name[0]] & FLAG_POSSIBLE1) &&
 303             (char_flags[(unsigned char)name[1]] & FLAG_POSSIBLE2) &&
 304             (char_flags[(unsigned char)name[2]] & FLAG_POSSIBLE3)) {
 305                 /* a likely match, scan the lot */
 306                 int i;
 307                 for (i=0; reserved_names[i]; i++) {
 308                         int len = strlen(reserved_names[i]);
 309                         /* note that we match on COM1 as well as COM1.foo */
 310                         if (strncasecmp(name, reserved_names[i], len) == 0 &&
 311                             (name[len] == '.' || name[len] == 0)) {
 312                                 return True;
 313                         }
 314                 }
 315         }
 316
 317         return False;
 318 }
 319
 320 /*
 321   see if a filename is a legal long filename
 322 */
 323 static BOOL is_legal_name(const char *name)
 324 {
 325         while (*name) {
 326                 if (char_flags[(unsigned char)*name] & FLAG_ILLEGAL) {
 327                         return False;
 328                 }
 329                 name++;
 330         }
 331
 332         return True;
 333 }
 334
 335 /*
 336   the main forward mapping function, which converts a long filename to
 337   a 8.3 name
 338
 339   if need83 is not set then we only do the mangling if the name is illegal
 340   as a long name
 341
 342   if cache83 is not set then we don't cache the result
 343
 344   the name parameter must be able to hold 13 bytes
 345 */
 346 static BOOL name_map(char *name, BOOL need83, BOOL cache83)
 347 {
 348         char *dot_p;
 349         char lead_char;
 350         char extension[4];
 351         int extension_length, i;
 352         int prefix_len;
 353         u32 hash, v;
 354         char new_name[13];
 355
 356         /* reserved names are handled specially */
 357         if (!is_reserved_name(name)) {
 358                 /* if the name is already a valid 8.3 name then we don't need to
 359                    do anything */
 360                 if (is_8_3(name, False)) {
 361                         return True;
 362                 }
 363
 364                 /* if the caller doesn't strictly need 8.3 then just check for illegal
 365                    filenames */
 366                 if (!need83 && is_legal_name(name)) {
 367                         return True;
 368                 }
 369         }
 370
 371         /* find the '.' if any */
 372         dot_p = strchr(name, '.');
 373
 374         /* the leading character in the mangled name is taken from
 375            the first character of the name, if it is ascii
 376            otherwise '_' is used
 377         */
 378         lead_char = name[0];
 379         if (! (char_flags[(unsigned char)lead_char] & FLAG_ASCII)) {
 380                 lead_char = '_';
 381         }
 382
 383         /* the prefix is anything up to the first dot */
 384         if (dot_p) {
 385                 prefix_len = PTR_DIFF(dot_p, name);
 386         } else {
 387                 prefix_len = strlen(name);
 388         }
 389
 390         /* the extension of the mangled name is taken from the first 3
 391            ascii chars after the dot */
 392         extension_length = 0;
 393         if (dot_p) {
 394                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
 395                         char c = dot_p[i];
 396                         if (char_flags[(unsigned char)c] & FLAG_ASCII) {
 397                                 extension[extension_length++] = c;
 398                         }
 399                 }
 400         }
 401
 402         /* find the hash for this prefix */
 403         v = hash = mangle_hash(name, prefix_len);
 404
 405         /* now form the mangled name */
 406         new_name[0] = lead_char;
 407         new_name[7] = base_forward(v % 36);
 408         new_name[6] = '~';
 409         for (i=5; i>=1; i--) {
 410                 v = v / 36;
 411                 new_name[i] = base_forward(v % 36);
 412         }
 413
 414         /* add the extension */
 415         if (extension_length) {
 416                 new_name[8] = '.';
 417                 memcpy(&new_name[9], extension, extension_length);
 418                 new_name[9+extension_length] = 0;
 419         } else {
 420                 new_name[8] = 0;
 421         }
 422
 423         if (cache83) {
 424                 /* put it in the cache */
 425                 cache_insert(name, prefix_len, hash);
 426         }
 427
 428         /* and overwrite the old name */
 429         fstrcpy(name, new_name);
 430
 431         /* all done, we've managed to mangle it */
 432         return True;
 433 }
 434
 435
 436 /* initialise the flags table
 437
 438   we allow only a very restricted set of characters as 'ascii' in this
 439   mangling backend. This isn't a significant problem as modern clients
 440   use the 'long' filenames anyway, and those don't have these
 441   restrictions.
 442 */
 443 static void init_tables(void)
 444 {
 445         int i;
 446
 447         memset(char_flags, 0, sizeof(char_flags));
 448
 449         for (i=0;i<128;i++) {
 450                 if ((i >= '0' && i <= '9') ||
 451                     (i >= 'a' && i <= 'z') ||
 452                     (i >= 'A' && i <= 'Z')) {
 453                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
 454                 }
 455                 if (strchr("._-$~", i)) {
 456                         char_flags[i] |= FLAG_ASCII;
 457                 }
 458
 459                 if (strchr("*\\/?<>|\":", i)) {
 460                         char_flags[i] |= FLAG_ILLEGAL;
 461                 }
 462         }
 463
 464         memset(base_reverse, 0, sizeof(base_reverse));
 465         for (i=0;i<36;i++) {
 466                 base_reverse[(unsigned char)base_forward(i)] = i;
 467         }
 468
 469         /* fill in the reserved names flags. These are used as a very
 470            fast filter for finding possible DOS reserved filenames */
 471         for (i=0; reserved_names[i]; i++) {
 472                 unsigned char c1, c2, c3;
 473
 474                 c1 = (unsigned char)reserved_names[i][0];
 475                 c2 = (unsigned char)reserved_names[i][1];
 476                 c3 = (unsigned char)reserved_names[i][2];
 477
 478                 char_flags[c1] |= FLAG_POSSIBLE1;
 479                 char_flags[c2] |= FLAG_POSSIBLE2;
 480                 char_flags[c3] |= FLAG_POSSIBLE3;
 481                 char_flags[tolower(c1)] |= FLAG_POSSIBLE1;
 482                 char_flags[tolower(c2)] |= FLAG_POSSIBLE2;
 483                 char_flags[tolower(c3)] |= FLAG_POSSIBLE3;
 484         }
 485 }
 486
 487
 488 /*
 489   the following provides the abstraction layer to make it easier
 490   to drop in an alternative mangling implementation */
 491 static struct mangle_fns mangle_fns = {
 492         is_mangled,
 493         is_8_3,
 494         mangle_reset,
 495         check_cache,
 496         name_map
 497 };
 498
 499 /* return the methods for this mangling implementation */
 500 struct mangle_fns *mangle_hash2_init(void)
 501 {
 502         init_tables();
 503         mangle_reset();
 504
 505         if (!cache_init()) {
 506                 return NULL;
 507         }
 508
 509         return &mangle_fns;
 510 }