db/hash.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6
   7 #include "libxfs.h"
   8 #include "init.h"
   9 #include "addr.h"
  10 #include "command.h"
  11 #include "type.h"
  12 #include "io.h"
  13 #include "output.h"
  14 #include "hash.h"
  15 #include "obfuscate.h"
  16 #include <sys/xattr.h>
  17
  18 static int hash_f(int argc, char **argv);
  19 static void hash_help(void);
  20
  21 static const cmdinfo_t hash_cmd = {
  22         .name           = "hash",
  23         .cfunc          = hash_f,
  24         .argmin         = 1,
  25         .argmax         = -1,
  26         .args           = N_("string"),
  27         .oneline        = N_("calculate hash value"),
  28         .help           = hash_help,
  29 };
  30
  31 static void
  32 hash_help(void)
  33 {
  34         dbprintf(_(
  35 "\n"
  36 " 'hash' prints out the calculated hash value for a string using the\n"
  37 "directory/attribute code hash function.\n"
  38 "\n"
  39 " Usage:  \"hash [-d|-p parent_ino] <string>\"\n"
  40 "\n"
  41 ));
  42
  43 }
  44
  45 enum hash_what {
  46         ATTR,
  47         DIRECTORY,
  48         PPTR,
  49 };
  50
  51 /* ARGSUSED */
  52 static int
  53 hash_f(
  54         int             argc,
  55         char            **argv)
  56 {
  57         xfs_ino_t       p_ino = 0;
  58         xfs_dahash_t    hashval;
  59         enum hash_what  what = ATTR;
  60         int             c;
  61
  62         while ((c = getopt(argc, argv, "dp:")) != EOF) {
  63                 switch (c) {
  64                 case 'd':
  65                         what = DIRECTORY;
  66                         break;
  67                 case 'p':
  68                         errno = 0;
  69                         p_ino = strtoull(optarg, NULL, 0);
  70                         if (errno) {
  71                                 perror(optarg);
  72                                 return 1;
  73                         }
  74                         what = PPTR;
  75                         break;
  76                 default:
  77                         exitcode = 1;
  78                         hash_help();
  79                         return 0;
  80                 }
  81         }
  82
  83         for (c = optind; c < argc; c++) {
  84                 struct xfs_name xname = {
  85                         .name   = (uint8_t *)argv[c],
  86                         .len    = strlen(argv[c]),
  87                 };
  88
  89                 switch (what) {
  90                 case DIRECTORY:
  91                         hashval = libxfs_dir2_hashname(mp, &xname);
  92                         break;
  93                 case PPTR:
  94                         hashval = libxfs_parent_hashval(mp, xname.name,
  95                                         xname.len, p_ino);
  96                         break;
  97                 case ATTR:
  98                         hashval = libxfs_attr_hashname(xname.name, xname.len);
  99                         break;
 100                 }
 101                 dbprintf("0x%x\n", hashval);
 102         }
 103
 104         return 0;
 105 }
 106
 107 static void
 108 hashcoll_help(void)
 109 {
 110         printf(_(
 111 "\n"
 112 " Generate obfuscated variants of the provided name.  Each variant will have\n"
 113 " the same dahash value.  Names are written to stdout with a NULL separating\n"
 114 " each name.\n"
 115 "\n"
 116 " -a -- create extended attributes.\n"
 117 " -i -- read standard input for the name, up to %d bytes.\n"
 118 " -n -- create this many names.\n"
 119 " -p -- create directory entries or extended attributes in this file.\n"
 120 " -s -- seed the rng with this value.\n"
 121 "\n"),
 122                         MAXNAMELEN - 1);
 123 }
 124
 125 struct name_dup {
 126         struct name_dup *next;
 127         uint32_t        crc;
 128         uint8_t         namelen;
 129         char            name[];
 130 };
 131
 132 static inline size_t
 133 name_dup_sizeof(
 134         unsigned int    namelen)
 135 {
 136         return sizeof(struct name_dup) + namelen;
 137 }
 138
 139 #define MAX_DUP_TABLE_BUCKETS   (1048575)
 140
 141 struct dup_table {
 142         unsigned int    nr_buckets;
 143         struct name_dup *buckets[];
 144 };
 145
 146 static inline size_t
 147 dup_table_sizeof(
 148         unsigned int    nr_buckets)
 149 {
 150         return sizeof(struct dup_table) +
 151                                 (nr_buckets * sizeof(struct name_dup *));
 152 }
 153
 154 static int
 155 dup_table_alloc(
 156         unsigned long           nr_names,
 157         struct dup_table        **tabp)
 158 {
 159         struct dup_table        *t;
 160
 161         *tabp = NULL;
 162
 163         if (nr_names == 1)
 164                 return 0;
 165
 166         nr_names = min(MAX_DUP_TABLE_BUCKETS, nr_names);
 167         t = calloc(1, dup_table_sizeof(nr_names));
 168         if (!t)
 169                 return ENOMEM;
 170
 171         t->nr_buckets = nr_names;
 172         *tabp = t;
 173         return 0;
 174 }
 175
 176 static void
 177 dup_table_free(
 178         struct dup_table        *tab)
 179 {
 180         struct name_dup         *ent, *next;
 181         unsigned int            i;
 182
 183         if (!tab)
 184                 return;
 185
 186         for (i = 0; i < tab->nr_buckets; i++) {
 187                 ent = tab->buckets[i];
 188
 189                 while (ent) {
 190                         next = ent->next;
 191                         free(ent);
 192                         ent = next;
 193                 }
 194         }
 195         free(tab);
 196 }
 197
 198 static struct name_dup *
 199 dup_table_find(
 200         struct dup_table        *tab,
 201         char                    *name,
 202         size_t                  namelen)
 203 {
 204         struct name_dup         *ent;
 205         uint32_t                crc = crc32c(~0, name, namelen);
 206
 207         ent = tab->buckets[crc % tab->nr_buckets];
 208         while (ent) {
 209                 if (ent->crc == crc &&
 210                     ent->namelen == namelen &&
 211                     !memcmp(ent->name, name, namelen))
 212                         return ent;
 213
 214                 ent = ent->next;
 215         }
 216
 217         return NULL;
 218 }
 219
 220 static int
 221 dup_table_store(
 222         struct dup_table        *tab,
 223         char                    *name,
 224         size_t                  namelen)
 225 {
 226         struct name_dup         *dup;
 227         uint32_t                seq = 1;
 228
 229         ASSERT(namelen < MAXNAMELEN);
 230
 231         while ((dup = dup_table_find(tab, name, namelen)) != NULL) {
 232                 int             ret;
 233
 234                 do {
 235                         ret = find_alternate(namelen, (uint8_t *)name, seq++);
 236                 } while (ret == 0);
 237                 if (ret < 0)
 238                         return EEXIST;
 239         }
 240
 241         dup = malloc(name_dup_sizeof(namelen));
 242         if (!dup)
 243                 return ENOMEM;
 244
 245         dup->crc = crc32c(~0, name, namelen);
 246         dup->namelen = namelen;
 247         memcpy(dup->name, name, namelen);
 248         dup->next = tab->buckets[dup->crc % tab->nr_buckets];
 249
 250         tab->buckets[dup->crc % tab->nr_buckets] = dup;
 251         return 0;
 252 }
 253
 254 static int
 255 collide_dirents(
 256         unsigned long           nr,
 257         char                    *name,
 258         size_t                  namelen,
 259         int                     fd)
 260 {
 261         struct xfs_name         dname = {
 262                 .name           = (uint8_t *)name,
 263                 .len            = namelen,
 264         };
 265         char                    direntname[MAXNAMELEN + 1];
 266         struct dup_table        *tab = NULL;
 267         xfs_dahash_t            old_hash;
 268         unsigned long           i;
 269         int                     error = 0;
 270
 271         old_hash = libxfs_dir2_hashname(mp, &dname);
 272
 273         if (fd >= 0) {
 274                 int             newfd;
 275
 276                 /*
 277                  * User passed in a fd, so we'll use the directory to detect
 278                  * duplicate names.  First create the name that we are passed
 279                  * in; the new names will be hardlinks to the first file.
 280                  */
 281                 newfd = openat(fd, name, O_CREAT, 0600);
 282                 if (newfd < 0)
 283                         return errno;
 284                 close(newfd);
 285         } else if (nr > 1) {
 286                 /*
 287                  * Track every name we create so that we don't emit duplicates.
 288                  */
 289                 error = dup_table_alloc(nr, &tab);
 290                 if (error)
 291                         return error;
 292         }
 293
 294         dname.name = (uint8_t *)direntname;
 295         for (i = 0; i < nr; i++) {
 296                 strncpy(direntname, name, MAXNAMELEN);
 297                 obfuscate_name(old_hash, namelen, (uint8_t *)direntname, true);
 298                 ASSERT(old_hash == libxfs_dir2_hashname(mp, &dname));
 299
 300                 if (fd >= 0) {
 301                         error = linkat(fd, name, fd, direntname, 0);
 302                         if (error && errno != EEXIST)
 303                                 return errno;
 304
 305                         /* don't print names to stdout */
 306                         continue;
 307                 } else if (tab) {
 308                         error = dup_table_store(tab, direntname, namelen);
 309                         if (error)
 310                                 break;
 311                 }
 312
 313                 printf("%s%c", direntname, 0);
 314         }
 315
 316         dup_table_free(tab);
 317         return error;
 318 }
 319
 320 static int
 321 collide_xattrs(
 322         unsigned long           nr,
 323         char                    *name,
 324         size_t                  namelen,
 325         int                     fd)
 326 {
 327         char                    xattrname[MAXNAMELEN + 5];
 328         struct dup_table        *tab = NULL;
 329         xfs_dahash_t            old_hash;
 330         unsigned long           i;
 331         int                     error = 0;
 332
 333         old_hash = libxfs_attr_hashname((uint8_t *)name, namelen);
 334
 335         if (fd >= 0) {
 336                 /*
 337                  * User passed in a fd, so we'll use the xattr structure to
 338                  * detect duplicate names.  First create the attribute that we
 339                  * are passed in.
 340                  */
 341                 snprintf(xattrname, MAXNAMELEN + 5, "user.%s", name);
 342                 error = fsetxattr(fd, xattrname, "1", 1, 0);
 343                 if (error)
 344                         return errno;
 345         } else if (nr > 1) {
 346                 /*
 347                  * Track every name we create so that we don't emit duplicates.
 348                  */
 349                 error = dup_table_alloc(nr, &tab);
 350                 if (error)
 351                         return error;
 352         }
 353
 354         for (i = 0; i < nr; i++) {
 355                 snprintf(xattrname, MAXNAMELEN + 5, "user.%s", name);
 356                 obfuscate_name(old_hash, namelen, (uint8_t *)xattrname + 5,
 357                                 false);
 358                 ASSERT(old_hash == libxfs_attr_hashname(
 359                                         (uint8_t *)xattrname + 5, namelen));
 360
 361                 if (fd >= 0) {
 362                         error = fsetxattr(fd, xattrname, "1", 1, 0);
 363                         if (error)
 364                                 return errno;
 365
 366                         /* don't print names to stdout */
 367                         continue;
 368                 } else if (tab) {
 369                         error = dup_table_store(tab, xattrname, namelen + 5);
 370                         if (error)
 371                                 break;
 372                 }
 373
 374                 printf("%s%c", xattrname, 0);
 375         }
 376
 377         dup_table_free(tab);
 378         return error;
 379 }
 380
 381 static int
 382 hashcoll_f(
 383         int             argc,
 384         char            **argv)
 385 {
 386         const char      *path = NULL;
 387         bool            read_stdin = false;
 388         bool            create_xattr = false;
 389         unsigned long   nr = 1, seed = 0;
 390         int             fd = -1;
 391         int             c;
 392         int             error;
 393
 394         while ((c = getopt(argc, argv, "ain:p:s:")) != EOF) {
 395                 switch (c) {
 396                 case 'a':
 397                         create_xattr = true;
 398                         break;
 399                 case 'i':
 400                         read_stdin = true;
 401                         break;
 402                 case 'n':
 403                         nr = strtoul(optarg, NULL, 10);
 404                         break;
 405                 case 'p':
 406                         path = optarg;
 407                         break;
 408                 case 's':
 409                         seed = strtoul(optarg, NULL, 10);
 410                         break;
 411                 default:
 412                         exitcode = 1;
 413                         hashcoll_help();
 414                         return 0;
 415                 }
 416         }
 417
 418         if (path) {
 419                 int     oflags = O_RDWR;
 420
 421                 if (!create_xattr)
 422                         oflags = O_RDONLY | O_DIRECTORY;
 423
 424                 fd = open(path, oflags);
 425                 if (fd < 0) {
 426                         perror(path);
 427                         exitcode = 1;
 428                         return 0;
 429                 }
 430         }
 431
 432         if (seed)
 433                 srandom(seed);
 434
 435         if (read_stdin) {
 436                 char    buf[MAXNAMELEN];
 437                 size_t  len;
 438
 439                 len = fread(buf, 1, MAXNAMELEN - 1, stdin);
 440
 441                 if (create_xattr)
 442                         error = collide_xattrs(nr, buf, len, fd);
 443                 else
 444                         error = collide_dirents(nr, buf, len, fd);
 445                 if (error) {
 446                         printf(_("hashcoll: %s\n"), strerror(error));
 447                         exitcode = 1;
 448                 }
 449                 goto done;
 450         }
 451
 452         for (c = optind; c < argc; c++) {
 453                 size_t  len = strlen(argv[c]);
 454
 455                 if (create_xattr)
 456                         error = collide_xattrs(nr, argv[c], len, fd);
 457                 else
 458                         error = collide_dirents(nr, argv[c], len, fd);
 459                 if (error) {
 460                         printf(_("hashcoll: %s\n"), strerror(error));
 461                         exitcode = 1;
 462                 }
 463         }
 464
 465 done:
 466         if (fd >= 0)
 467                 close(fd);
 468         return 0;
 469 }
 470
 471 static cmdinfo_t        hashcoll_cmd = {
 472         .name           = "hashcoll",
 473         .cfunc          = hashcoll_f,
 474         .argmin         = 0,
 475         .argmax         = -1,
 476         .args           = N_("[-a] [-s seed] [-n nr] [-p path] -i|names..."),
 477         .oneline        = N_("create names that produce dahash collisions"),
 478         .help           = hashcoll_help,
 479 };
 480
 481 void
 482 hash_init(void)
 483 {
 484         add_command(&hash_cmd);
 485         add_command(&hashcoll_cmd);
 486 }