]> git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blame - db/hash.c
xfsprogs: Release v6.15.0
[thirdparty/xfsprogs-dev.git] / db / hash.c
CommitLineData
959ef981 1// SPDX-License-Identifier: GPL-2.0
2bd0ea18 2/*
da23017d
NS
3 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
4 * All Rights Reserved.
2bd0ea18
NS
5 */
6
6b803e5a 7#include "libxfs.h"
c51c8c85 8#include "init.h"
2bd0ea18
NS
9#include "addr.h"
10#include "command.h"
11#include "type.h"
12#include "io.h"
13#include "output.h"
4a87b332 14#include "hash.h"
c51c8c85
DW
15#include "obfuscate.h"
16#include <sys/xattr.h>
2bd0ea18
NS
17
18static int hash_f(int argc, char **argv);
19static void hash_help(void);
20
47560612
DW
21static 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};
2bd0ea18
NS
30
31static void
32hash_help(void)
33{
9ee7055c 34 dbprintf(_(
2bd0ea18
NS
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"
40a59ddd 39" Usage: \"hash [-d|-p parent_ino] <string>\"\n"
2bd0ea18 40"\n"
9ee7055c 41));
2bd0ea18
NS
42
43}
44
40a59ddd
DW
45enum hash_what {
46 ATTR,
47 DIRECTORY,
48 PPTR,
49};
50
2bd0ea18
NS
51/* ARGSUSED */
52static int
53hash_f(
54 int argc,
55 char **argv)
56{
40a59ddd 57 xfs_ino_t p_ino = 0;
2bd0ea18 58 xfs_dahash_t hashval;
40a59ddd 59 enum hash_what what = ATTR;
47560612
DW
60 int c;
61
40a59ddd 62 while ((c = getopt(argc, argv, "dp:")) != EOF) {
47560612
DW
63 switch (c) {
64 case 'd':
40a59ddd
DW
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;
47560612
DW
75 break;
76 default:
77 exitcode = 1;
78 hash_help();
79 return 0;
80 }
81 }
82
83 for (c = optind; c < argc; c++) {
2c7fe3b3
CH
84 struct xfs_name xname = {
85 .name = (uint8_t *)argv[c],
86 .len = strlen(argv[c]),
87 };
47560612 88
40a59ddd
DW
89 switch (what) {
90 case DIRECTORY:
47560612 91 hashval = libxfs_dir2_hashname(mp, &xname);
40a59ddd
DW
92 break;
93 case PPTR:
94 hashval = libxfs_parent_hashval(mp, xname.name,
95 xname.len, p_ino);
96 break;
97 case ATTR:
6db2bc3d 98 hashval = libxfs_attr_hashname(xname.name, xname.len);
40a59ddd
DW
99 break;
100 }
47560612
DW
101 dbprintf("0x%x\n", hashval);
102 }
2bd0ea18 103
2bd0ea18
NS
104 return 0;
105}
106
c51c8c85
DW
107static void
108hashcoll_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
125struct name_dup {
126 struct name_dup *next;
127 uint32_t crc;
128 uint8_t namelen;
2c7fe3b3 129 char name[];
c51c8c85
DW
130};
131
132static inline size_t
133name_dup_sizeof(
134 unsigned int namelen)
135{
136 return sizeof(struct name_dup) + namelen;
137}
138
139#define MAX_DUP_TABLE_BUCKETS (1048575)
140
141struct dup_table {
142 unsigned int nr_buckets;
143 struct name_dup *buckets[];
144};
145
146static inline size_t
147dup_table_sizeof(
148 unsigned int nr_buckets)
149{
150 return sizeof(struct dup_table) +
151 (nr_buckets * sizeof(struct name_dup *));
152}
153
154static int
155dup_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
176static void
177dup_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
198static struct name_dup *
199dup_table_find(
200 struct dup_table *tab,
2c7fe3b3 201 char *name,
c51c8c85
DW
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
220static int
221dup_table_store(
222 struct dup_table *tab,
2c7fe3b3 223 char *name,
c51c8c85
DW
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 {
2c7fe3b3 235 ret = find_alternate(namelen, (uint8_t *)name, seq++);
c51c8c85
DW
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
254static int
255collide_dirents(
256 unsigned long nr,
2c7fe3b3 257 char *name,
c51c8c85
DW
258 size_t namelen,
259 int fd)
260{
261 struct xfs_name dname = {
2c7fe3b3 262 .name = (uint8_t *)name,
c51c8c85
DW
263 .len = namelen,
264 };
2c7fe3b3 265 char direntname[MAXNAMELEN + 1];
c51c8c85
DW
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
2c7fe3b3 294 dname.name = (uint8_t *)direntname;
c51c8c85
DW
295 for (i = 0; i < nr; i++) {
296 strncpy(direntname, name, MAXNAMELEN);
2c7fe3b3 297 obfuscate_name(old_hash, namelen, (uint8_t *)direntname, true);
c51c8c85
DW
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
320static int
321collide_xattrs(
322 unsigned long nr,
2c7fe3b3 323 char *name,
c51c8c85
DW
324 size_t namelen,
325 int fd)
326{
2c7fe3b3 327 char xattrname[MAXNAMELEN + 5];
c51c8c85
DW
328 struct dup_table *tab = NULL;
329 xfs_dahash_t old_hash;
330 unsigned long i;
a3e126d5 331 int error = 0;
c51c8c85 332
6db2bc3d 333 old_hash = libxfs_attr_hashname((uint8_t *)name, namelen);
c51c8c85
DW
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);
2c7fe3b3
CH
356 obfuscate_name(old_hash, namelen, (uint8_t *)xattrname + 5,
357 false);
6db2bc3d
DW
358 ASSERT(old_hash == libxfs_attr_hashname(
359 (uint8_t *)xattrname + 5, namelen));
c51c8c85
DW
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
381static int
382hashcoll_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
465done:
466 if (fd >= 0)
467 close(fd);
468 return 0;
469}
470
471static 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
2bd0ea18
NS
481void
482hash_init(void)
483{
484 add_command(&hash_cmd);
c51c8c85 485 add_command(&hashcoll_cmd);
2bd0ea18 486}