src/dirhash_collide.c

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