src/dirhash_collide.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Generates files or directories with hash collisions on a XFS filesystem
   4  * Copyright (C) 2014 Hannes Frederic Sowa
   5  */
   6
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <stdint.h>
  10 #include <stdbool.h>
  11 #include <string.h>
  12
  13 #include <sys/stat.h>
  14 #include <sys/time.h>
  15 #include <unistd.h>
  16 #include <errno.h>
  17 #include <fcntl.h>
  18
  19 static enum {
  20         ILLEGAL,
  21         DIRECTORY,
  22         FILENAME,
  23 } touch_mode = ILLEGAL;
  24
  25 static bool one_hash = false;
  26
  27 static uint32_t rol32(uint32_t word, unsigned int shift)
  28 {
  29         return (word << shift) | (word >> (32 - shift));
  30 }
  31
  32 static uint32_t xfs_da_hashname(const uint8_t *name, int namelen)
  33 {
  34         uint32_t hash;
  35
  36         for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
  37                 hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
  38                        (name[3] << 0) ^ rol32(hash, 7 * 4);
  39
  40         if (namelen) {
  41                 fprintf(stderr,
  42                         "internal error: "
  43                         "misbalanced input buffer to xfs_da_hashname - "
  44                         "overlapping %d bytes\n", namelen);
  45                 exit(1);
  46         }
  47
  48         return hash;
  49 }
  50
  51 static uint8_t gen_rand(void)
  52 {
  53         uint8_t r;
  54         while (!(r = rand()));
  55         return r;
  56 }
  57
  58 static uint8_t buffer[252+1] = {0};
  59
  60 static void gen_name(void)
  61 {
  62         int idx;
  63         uint32_t hash, last;
  64
  65 again:
  66         for (idx = 0; idx < 252-4; idx+=4) {
  67                 buffer[idx + 0] = gen_rand();
  68                 buffer[idx + 1] = gen_rand();
  69                 buffer[idx + 2] = gen_rand();
  70                 buffer[idx + 3] = gen_rand();
  71         }
  72
  73         hash = rol32(xfs_da_hashname(buffer, 248), 7 * 4);
  74         last = hash ^ ~0U;
  75
  76         if (last == 0)
  77                 goto again;
  78
  79         buffer[idx + 3] = last & 0x7fU;
  80         buffer[idx + 2] = (last >> 7)  & 0x7fU;
  81         buffer[idx + 1] = (last >> 14) & 0x7fU;
  82         buffer[idx + 0] = ((last >> 21) & 0xffU);
  83
  84         if (memchr(buffer, '.', sizeof(buffer)) ||
  85             memchr(buffer, '/', sizeof(buffer)))
  86                 goto again;
  87
  88         if (one_hash) {
  89                 /* very poor - can be improved later */
  90                 static bool done = false;
  91                 static uint32_t filter;
  92
  93                 if (!done) {
  94                         filter = xfs_da_hashname(buffer, 252);
  95                         done = true;
  96                         return;
  97                 }
  98
  99                 if (filter != xfs_da_hashname(buffer, 252))
 100                         goto again;
 101         }
 102 }
 103
 104 static int touch(const char *buffer)
 105 {
 106         if (touch_mode == DIRECTORY) {
 107                 if (mkdir(buffer, S_IRWXU)) {
 108                         /* ignore if directory is already present */
 109                         if (errno == EEXIST)
 110                                 return 0;
 111                         perror("mkdir with random directory name");
 112                         return 1;
 113                 }
 114         } else if (touch_mode == FILENAME) {
 115                 int fd = creat(buffer, S_IRWXU);
 116                 if (fd == -1) {
 117                         /* ignore duplicate files */
 118                         if (errno == EEXIST)
 119                                 return 0;
 120                         perror("creat with random directory name");
 121                         return 1;
 122                 }
 123                 if (close(fd)) {
 124                         perror("close is leaking a file descriptor");
 125                         return 1;
 126                 }
 127                 return 0;
 128         }
 129         return 0;
 130 }
 131
 132 static void do_seed(void)
 133 {
 134         struct timeval tv;
 135         if (gettimeofday(&tv, NULL)) {
 136                 perror("gettimeofday");
 137                 exit(1);
 138         }
 139         srand(tv.tv_sec ^ tv.tv_usec ^ getpid());
 140 }
 141
 142 static void usage_and_exit(const char *pname)
 143 {
 144         fprintf(stderr, "usage: %s [-d] [-f] [-n num] [-s] directory\n"
 145                         "\t-f\tcreate files (the default)\n"
 146                         "\t-d\tcreate directories\n"
 147                         "\t-n num\tcreate num directories or files (default 200000)\n"
 148                         "\t-s\tonly generate one hash\n"
 149                         "\tdirectory\tthe directory to chdir() to\n",
 150                 pname);
 151         exit(1);
 152 }
 153
 154 int main(int argc, char **argv)
 155 {
 156         const char allopts[] = "hsdfn:";
 157         int c, orig_cycles, errors = 0, cycles = 200000;
 158
 159         while ((c = getopt(argc, argv, allopts)) != -1) {
 160                 switch (c) {
 161                 case 'd':
 162                         if (touch_mode != ILLEGAL)
 163                                 usage_and_exit(argv[0]);
 164                         touch_mode = DIRECTORY;
 165                         break;
 166                 case 'f':
 167                         if (touch_mode != ILLEGAL)
 168                                 usage_and_exit(argv[0]);
 169                         touch_mode = FILENAME;
 170                         break;
 171                 case 'n':
 172                         errno = 0;
 173                         if (sscanf(optarg, "%d", &cycles) != 1 ||
 174                             errno == ERANGE) {
 175                                 fputs("could not parse number of iterations", stderr);
 176                                 exit(1);
 177                         }
 178                         break;
 179                 case 's':
 180                         one_hash = true;
 181                         break;
 182                 default:
 183                         usage_and_exit(argv[0]);
 184                         break;
 185                 }
 186         }
 187
 188         if (argc <= optind || touch_mode == ILLEGAL)
 189                 usage_and_exit(argv[0]);
 190
 191         if (chdir(argv[optind])) {
 192                 perror("chdir");
 193                 exit(1);
 194         }
 195
 196         orig_cycles = cycles;
 197
 198         do_seed();
 199
 200         while (cycles--) {
 201                 gen_name();
 202                 errors += touch((char *)buffer);
 203         }
 204
 205         if (errors)
 206                 fprintf(stderr, "creating %d %s caused %d errors\n",
 207                         orig_cycles, touch_mode == FILENAME ? "files" : "directories",
 208                         errors);
 209
 210         return 0;
 211 }