ia64/xen-unstable

view tools/xenstore/xs_random.c @ 8740:3d7ea7972b39

Update patches for linux 2.6.15.

Signed-off-by: Christian Limpach <Christian.Limpach@cl.cam.ac.uk>
author cl349@firebug.cl.cam.ac.uk
date Thu Feb 02 17:16:00 2006 +0000 (2006-02-02)
parents b3a255e88810
children
line source
1 /* Random tests.
3 We check that the results from a real filesystem are the same.
4 */
5 #include <sys/types.h>
6 #include <stdio.h>
7 #include <stdarg.h>
8 #include <stdlib.h>
9 #include <dirent.h>
10 #include <errno.h>
11 #include <sys/stat.h>
12 #include <unistd.h>
13 #include <fcntl.h>
14 #include <signal.h>
15 #include <sys/wait.h>
16 #include "xs.h"
17 #include "talloc.h"
18 #include "utils.h"
20 struct ops
21 {
22 char *name;
24 char **(*dir)(void *h, const char *path, unsigned int *num);
26 void *(*read)(void *h, const char *path, unsigned int *len);
28 bool (*write)(void *h, const char *path, const void *data,
29 unsigned int len);
31 bool (*mkdir)(void *h, const char *path);
33 bool (*rm)(void *h, const char *path);
35 struct xs_permissions *(*get_perms)(void *h,
36 const char *path,
37 unsigned int *num);
39 bool (*set_perms)(void *h,
40 const char *path,
41 struct xs_permissions *perms,
42 unsigned int num);
44 bool (*transaction_start)(void *h);
45 bool (*transaction_end)(void *h, bool abort);
47 /* Create and destroy a new handle. */
48 void *(*handle)(const char *path);
49 void (*close)(void *);
50 };
52 struct file_ops_info
53 {
54 const char *base;
55 char *transact_base;
56 };
58 static void convert_to_dir(const char *dirname)
59 {
60 char *tmpname = talloc_asprintf(dirname, "%s.tmp", dirname);
61 if (rename(dirname, tmpname) != 0)
62 barf_perror("Failed to rename %s to %s", dirname, tmpname);
63 if (mkdir(dirname, 0700) != 0)
64 barf_perror("Failed to mkdir %s", dirname);
65 if (rename(tmpname,talloc_asprintf(dirname, "%s/.DATA", dirname)) != 0)
66 barf_perror("Failed to rename into %s", dirname);
67 /* If perms exists, move it in. */
68 rename(talloc_asprintf(dirname, "%s.perms", dirname),
69 talloc_asprintf(dirname, "%s/.perms", dirname));
70 }
72 /* Files can be used as dirs, too. Convert them when they are. */
73 static void maybe_convert_to_directory(const char *filename)
74 {
75 struct stat st;
76 char *dirname = talloc_asprintf(
77 filename, "%.*s",
78 (int)(strrchr(filename, '/') - filename), filename);
79 if (lstat(dirname, &st) == 0 && S_ISREG(st.st_mode))
80 convert_to_dir(dirname);
81 }
83 static char *get_name(struct file_ops_info *info, const char *path)
84 {
85 if (info->transact_base)
86 return talloc_asprintf(path, "%s%s", info->transact_base,
87 path);
88 return talloc_asprintf(path, "%s%s", info->base, path);
89 }
91 static char *path_to_name(struct file_ops_info *info, const char *path)
92 {
93 char *filename = get_name(info, path);
94 maybe_convert_to_directory(filename);
95 return filename;
96 }
98 static char **file_directory(struct file_ops_info *info,
99 const char *path, unsigned int *num)
100 {
101 char **ret;
102 DIR *dir;
103 struct dirent *dirent;
104 char *p, *dirname = path_to_name(info, path);
105 unsigned int i, len = 0;
106 struct stat st;
108 /* If it exists, but isn't a directory, we convert it. */
109 if (lstat(dirname, &st) == 0 && !S_ISDIR(st.st_mode))
110 convert_to_dir(dirname);
112 *num = 0;
113 dir = opendir(dirname);
114 if (!dir)
115 return NULL;;
117 /* Once to count them. */
118 while ((dirent = readdir(dir)) != NULL) {
119 if (strchr(dirent->d_name, '.'))
120 continue;
121 len += strlen(dirent->d_name) + 1;
122 (*num)++;
123 }
124 rewinddir(dir);
126 /* Now allocate and fill in. */
127 ret = malloc(sizeof(char *) * *num + len);
128 p = (char *)&ret[*num];
129 i = 0;
130 while ((dirent = readdir(dir)) != NULL) {
131 if (strchr(dirent->d_name, '.'))
132 continue;
133 ret[i] = p;
134 strcpy(p, dirent->d_name);
135 p += strlen(p) + 1;
136 i++;
137 }
138 closedir(dir);
140 return ret;
141 }
143 static char *filename_to_data(const char *filename)
144 {
145 struct stat st;
147 if (lstat(filename, &st) == 0 && S_ISDIR(st.st_mode))
148 return talloc_asprintf(filename, "%s/.DATA", filename);
149 return (char *)filename;
150 }
152 static void *file_read(struct file_ops_info *info,
153 const char *path, unsigned int *len)
154 {
155 void *ret;
156 char *filename = filename_to_data(path_to_name(info, path));
157 unsigned long size;
159 ret = grab_file(filename, &size);
160 /* Directory exists, .DATA doesn't. */
161 if (!ret && errno == ENOENT && strends(filename, ".DATA")) {
162 ret = strdup("");
163 size = 0;
164 }
165 *len = size;
166 return ret;
167 }
169 static struct xs_permissions *file_get_perms(struct file_ops_info *info,
170 const char *path,
171 unsigned int *num)
172 {
173 void *perms;
174 struct xs_permissions *ret;
175 char *filename = path_to_name(info, path);
176 char *permfile;
177 unsigned long size;
178 struct stat st;
180 if (lstat(filename, &st) != 0)
181 return NULL;
183 if (S_ISDIR(st.st_mode))
184 permfile = talloc_asprintf(path, "%s/.perms", filename);
185 else
186 permfile = talloc_asprintf(path, "%s.perms", filename);
188 perms = grab_file(permfile, &size);
189 if (!perms)
190 barf("Grabbing permissions for %s", permfile);
191 *num = xs_count_strings(perms, size);
193 ret = new_array(struct xs_permissions, *num);
194 if (!xs_strings_to_perms(ret, *num, perms))
195 barf("Reading permissions from %s", permfile);
196 release_file(perms, size);
197 return ret;
198 }
200 static void do_command(const char *cmd)
201 {
202 int ret;
204 ret = system(cmd);
205 if (ret == -1 || !WIFEXITED(ret) || WEXITSTATUS(ret) != 0)
206 barf_perror("Failed '%s': %i", cmd, ret);
207 }
209 static void init_perms(const char *filename)
210 {
211 struct stat st;
212 char *permfile, *command;
214 if (lstat(filename, &st) != 0)
215 barf_perror("Failed to stat %s", filename);
217 if (S_ISDIR(st.st_mode))
218 permfile = talloc_asprintf(filename, "%s/.perms", filename);
219 else
220 permfile = talloc_asprintf(filename, "%s.perms", filename);
222 /* Leave permfile if it already exists. */
223 if (lstat(permfile, &st) == 0)
224 return;
226 /* Copy permissions from parent */
227 command = talloc_asprintf(filename, "cp %.*s/.perms %s",
228 (int)(strrchr(filename, '/') - filename),
229 filename, permfile);
230 do_command(command);
231 }
233 static bool file_set_perms(struct file_ops_info *info,
234 const char *path,
235 struct xs_permissions *perms,
236 unsigned int num)
237 {
238 unsigned int i;
239 char *filename = path_to_name(info, path);
240 char *permfile;
241 int fd;
242 struct stat st;
244 if (num < 1) {
245 errno = EINVAL;
246 return false;
247 }
249 /* Check non-perm file exists/ */
250 if (lstat(filename, &st) != 0)
251 return false;
253 if (S_ISDIR(st.st_mode))
254 permfile = talloc_asprintf(path, "%s/.perms", filename);
255 else
256 permfile = talloc_asprintf(path, "%s.perms", filename);
258 fd = open(permfile, O_WRONLY|O_CREAT|O_TRUNC, 0600);
259 if (fd < 0)
260 return false;
262 for (i = 0; i < num; i++) {
263 char buffer[100];
265 if (!xs_perm_to_string(&perms[i], buffer)) {
266 int saved_errno = errno;
267 close(fd);
268 errno = saved_errno;
269 return false;
270 }
271 if (write(fd, buffer, strlen(buffer) + 1)
272 != (int)strlen(buffer) + 1)
273 barf_perror("Failed to write perm");
274 }
275 close(fd);
276 return true;
277 }
279 static char *parent_filename(const char *name)
280 {
281 char *slash = strrchr(name + 1, '/');
282 if (!slash)
283 return talloc_strdup(name, "/");
284 return talloc_asprintf(name, "%.*s", (int)(slash-name), name);
285 }
287 static void make_dirs(const char *filename)
288 {
289 struct stat st;
291 if (lstat(filename, &st) == 0 && S_ISREG(st.st_mode))
292 convert_to_dir(filename);
294 if (mkdir(filename, 0700) == 0) {
295 init_perms(filename);
296 return;
297 }
298 if (errno == EEXIST)
299 return;
301 make_dirs(parent_filename(filename));
302 if (mkdir(filename, 0700) != 0)
303 barf_perror("Failed to mkdir %s", filename);
304 init_perms(filename);
305 }
307 static bool file_write(struct file_ops_info *info,
308 const char *path, const void *data,
309 unsigned int len)
310 {
311 char *filename = filename_to_data(path_to_name(info, path));
312 int fd;
314 make_dirs(parent_filename(filename));
315 fd = open(filename, O_CREAT|O_TRUNC|O_WRONLY, 0600);
316 if (fd < 0)
317 return false;
319 if (write(fd, data, len) != (int)len)
320 barf_perror("Bad write to %s", filename);
322 init_perms(filename);
323 close(fd);
324 return true;
325 }
327 static bool file_mkdir(struct file_ops_info *info, const char *path)
328 {
329 char *dirname = path_to_name(info, path);
331 make_dirs(parent_filename(dirname));
332 if (mkdir(dirname, 0700) != 0)
333 return (errno == EEXIST);
335 init_perms(dirname);
336 return true;
337 }
339 static bool file_rm(struct file_ops_info *info, const char *path)
340 {
341 char *filename = path_to_name(info, path);
342 struct stat st;
344 if (lstat(filename, &st) != 0) {
345 if (lstat(parent_filename(filename), &st) != 0)
346 return false;
347 return true;
348 }
350 if (streq(path, "/")) {
351 errno = EINVAL;
352 return false;
353 }
355 do_command(talloc_asprintf(path, "rm -f %s.perms; rm -r %s",
356 filename, filename));
357 return true;
358 }
360 static bool file_transaction_start(struct file_ops_info *info)
361 {
362 char *cmd;
364 if (info->transact_base) {
365 errno = EBUSY;
366 return false;
367 }
369 info->transact_base = talloc_asprintf(NULL, "%s.transact", info->base);
370 cmd = talloc_asprintf(NULL, "cp -r %s %s",
371 info->base, info->transact_base);
372 do_command(cmd);
373 talloc_free(cmd);
374 return true;
375 }
377 static bool file_transaction_end(struct file_ops_info *info, bool abort)
378 {
379 char *old, *cmd;
381 if (!info->transact_base) {
382 errno = ENOENT;
383 return false;
384 }
386 if (abort) {
387 cmd = talloc_asprintf(NULL, "rm -rf %s", info->transact_base);
388 do_command(cmd);
389 goto success;
390 }
392 old = talloc_asprintf(NULL, "rm -rf %s", info->base);
393 do_command(old);
394 talloc_free(old);
396 cmd = talloc_asprintf(NULL, "mv %s %s",
397 info->transact_base, info->base);
398 do_command(cmd);
400 success:
401 talloc_free(cmd);
402 talloc_free(info->transact_base);
403 info->transact_base = NULL;
404 return true;
405 }
407 static struct file_ops_info *file_handle(const char *dir)
408 {
409 struct file_ops_info *info = talloc(NULL, struct file_ops_info);
411 info->base = dir;
412 info->transact_base = NULL;
413 return info;
414 }
416 static void file_close(struct file_ops_info *handle)
417 {
418 talloc_free(handle);
419 }
421 static struct xs_handle *xs_handle(const char *dir __attribute__((unused)))
422 {
423 struct xs_handle *h;
425 h = xs_daemon_open();
426 if (!h)
427 barf_perror("Connecting to xs daemon");
428 return h;
429 }
431 static void xs_close(struct xs_handle *handle)
432 {
433 xs_daemon_close(handle);
434 }
436 struct ops file_ops = {
437 .name = "FILE",
438 .dir = (void *)file_directory,
439 .read = (void *)file_read,
440 .write = (void *)file_write,
441 .mkdir = (void *)file_mkdir,
442 .rm = (void *)file_rm,
443 .get_perms = (void *)file_get_perms,
444 .set_perms = (void *)file_set_perms,
445 .transaction_start = (void *)file_transaction_start,
446 .transaction_end = (void *)file_transaction_end,
447 .handle = (void *)file_handle,
448 .close = (void *)file_close,
449 };
451 struct ops xs_ops = {
452 .name = "XS",
453 .dir = (void *)xs_directory,
454 .read = (void *)xs_read,
455 .write = (void *)xs_write,
456 .mkdir = (void *)xs_mkdir,
457 .rm = (void *)xs_rm,
458 .get_perms = (void *)xs_get_permissions,
459 .set_perms = (void *)xs_set_permissions,
460 .transaction_start = (void *)xs_transaction_start,
461 .transaction_end = (void *)xs_transaction_end,
462 .handle = (void *)xs_handle,
463 .close = (void *)xs_close,
464 };
466 static int strptrcmp(const void *a, const void *b)
467 {
468 return strcmp(*(char **)a, *(char **)b);
469 }
471 static void sort_dir(char **dir, unsigned int num)
472 {
473 qsort(dir, num, sizeof(char *), strptrcmp);
474 }
476 static char *dump_dir(struct ops *ops,
477 void *h,
478 const char *node,
479 char **dir,
480 unsigned int numdirs,
481 unsigned int depth)
482 {
483 char *ret = talloc_strdup(node, "");
484 unsigned int i;
485 char spacing[depth+1];
487 memset(spacing, ' ', depth);
488 spacing[depth] = '\0';
490 sort_dir(dir, numdirs);
492 for (i = 0; i < numdirs; i++) {
493 struct xs_permissions *perms;
494 unsigned int j, numperms;
495 unsigned int len;
496 char *contents;
497 unsigned int subnum;
498 char **subdirs;
499 char *subret;
500 char *subnode = talloc_asprintf(node, "%s/%s", node, dir[i]);
502 perms = ops->get_perms(h, subnode, &numperms);
503 if (!perms)
504 return NULL;
505 ret = talloc_asprintf_append(ret, "%s%s: ", spacing, dir[i]);
506 for (j = 0; j < numperms; j++) {
507 char buffer[100];
508 if (!xs_perm_to_string(&perms[j], buffer))
509 barf("perm to string");
510 ret = talloc_asprintf_append(ret, "%s ", buffer);
511 }
512 free(perms);
513 ret = talloc_asprintf_append(ret, "\n");
515 /* Even directories can have contents. */
516 contents = ops->read(h, subnode, &len);
517 if (!contents) {
518 if (errno != EISDIR)
519 return NULL;
520 } else {
521 ret = talloc_asprintf_append(ret, " %s(%.*s)\n",
522 spacing, len, contents);
523 free(contents);
524 }
526 /* Every node is a directory. */
527 subdirs = ops->dir(h, subnode, &subnum);
528 if (!subdirs)
529 return NULL;
530 subret = dump_dir(ops, h, subnode, subdirs, subnum, depth+1);
531 if (!subret)
532 return NULL;
533 ret = talloc_asprintf_append(ret, "%s", subret);
534 free(subdirs);
535 }
536 return ret;
537 }
539 static char *dump(struct ops *ops, void *h)
540 {
541 char **subdirs;
542 unsigned int subnum;
543 char *ret = NULL, *root = talloc_strdup(NULL, "/");
545 subdirs = ops->dir(h, root, &subnum);
546 if (subdirs) {
547 ret = dump_dir(ops, h, talloc_strdup(root, ""), subdirs,
548 subnum, 0);
549 free(subdirs);
550 if (ret)
551 talloc_steal(NULL, ret);
552 }
553 talloc_free(root);
554 return ret;
555 }
557 /* jhash.h: Jenkins hash support.
558 *
559 * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
560 *
561 * http://burtleburtle.net/bob/hash/
562 *
563 * These are the credits from Bob's sources:
564 *
565 * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
566 * hash(), hash2(), hash3, and mix() are externally useful functions.
567 * Routines to test the hash are included if SELF_TEST is defined.
568 * You can use this free for any purpose. It has no warranty.
569 *
570 * Copyright (C) 2003 David S. Miller (davem@redhat.com)
571 *
572 * I've modified Bob's hash to be useful in the Linux kernel, and
573 * any bugs present are surely my fault. -DaveM
574 */
576 /* NOTE: Arguments are modified. */
577 #define __jhash_mix(a, b, c) \
578 { \
579 a -= b; a -= c; a ^= (c>>13); \
580 b -= c; b -= a; b ^= (a<<8); \
581 c -= a; c -= b; c ^= (b>>13); \
582 a -= b; a -= c; a ^= (c>>12); \
583 b -= c; b -= a; b ^= (a<<16); \
584 c -= a; c -= b; c ^= (b>>5); \
585 a -= b; a -= c; a ^= (c>>3); \
586 b -= c; b -= a; b ^= (a<<10); \
587 c -= a; c -= b; c ^= (b>>15); \
588 }
590 /* The golden ration: an arbitrary value */
591 #define JHASH_GOLDEN_RATIO 0x9e3779b9
593 /* The most generic version, hashes an arbitrary sequence
594 * of bytes. No alignment or length assumptions are made about
595 * the input key.
596 */
597 static inline uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
598 {
599 uint32_t a, b, c, len;
600 const uint8_t *k = key;
602 len = length;
603 a = b = JHASH_GOLDEN_RATIO;
604 c = initval;
606 while (len >= 12) {
607 a += (k[0] +((uint32_t)k[1]<<8) +((uint32_t)k[2]<<16) +((uint32_t)k[3]<<24));
608 b += (k[4] +((uint32_t)k[5]<<8) +((uint32_t)k[6]<<16) +((uint32_t)k[7]<<24));
609 c += (k[8] +((uint32_t)k[9]<<8) +((uint32_t)k[10]<<16)+((uint32_t)k[11]<<24));
611 __jhash_mix(a,b,c);
613 k += 12;
614 len -= 12;
615 }
617 c += length;
618 switch (len) {
619 case 11: c += ((uint32_t)k[10]<<24);
620 case 10: c += ((uint32_t)k[9]<<16);
621 case 9 : c += ((uint32_t)k[8]<<8);
622 case 8 : b += ((uint32_t)k[7]<<24);
623 case 7 : b += ((uint32_t)k[6]<<16);
624 case 6 : b += ((uint32_t)k[5]<<8);
625 case 5 : b += k[4];
626 case 4 : a += ((uint32_t)k[3]<<24);
627 case 3 : a += ((uint32_t)k[2]<<16);
628 case 2 : a += ((uint32_t)k[1]<<8);
629 case 1 : a += k[0];
630 };
632 __jhash_mix(a,b,c);
634 return c;
635 }
637 /* A special optimized version that handles 1 or more of uint32_ts.
638 * The length parameter here is the number of uint32_ts in the key.
639 */
640 static inline uint32_t jhash2(uint32_t *k, uint32_t length, uint32_t initval)
641 {
642 uint32_t a, b, c, len;
644 a = b = JHASH_GOLDEN_RATIO;
645 c = initval;
646 len = length;
648 while (len >= 3) {
649 a += k[0];
650 b += k[1];
651 c += k[2];
652 __jhash_mix(a, b, c);
653 k += 3; len -= 3;
654 }
656 c += length * 4;
658 switch (len) {
659 case 2 : b += k[1];
660 case 1 : a += k[0];
661 };
663 __jhash_mix(a,b,c);
665 return c;
666 }
669 /* A special ultra-optimized versions that knows they are hashing exactly
670 * 3, 2 or 1 word(s).
671 *
672 * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
673 * done at the end is not done here.
674 */
675 static inline uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
676 {
677 a += JHASH_GOLDEN_RATIO;
678 b += JHASH_GOLDEN_RATIO;
679 c += initval;
681 __jhash_mix(a, b, c);
683 return c;
684 }
686 static inline uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
687 {
688 return jhash_3words(a, b, 0, initval);
689 }
691 static inline uint32_t jhash_1word(uint32_t a, uint32_t initval)
692 {
693 return jhash_3words(a, 0, 0, initval);
694 }
696 static unsigned int get_randomness(int *state)
697 {
698 return jhash_1word((*state)++, *state * 1103515243);
699 }
701 static char *random_path(int *state)
702 {
703 unsigned int i;
704 char *ret = NULL;
706 if (get_randomness(state) % 20 == 0)
707 return talloc_strdup(NULL, "/");
709 for (i = 0; i < 1 || (get_randomness(state) % 2); i++) {
710 ret = talloc_asprintf_append(ret, "/%i",
711 get_randomness(state) % 15);
712 }
713 return ret;
714 }
716 static char *bool_to_errstring(bool result)
717 {
718 if (result)
719 return talloc_strdup(NULL, "OK");
721 /* Real daemon can never return this. */
722 if (errno == ENOTDIR)
723 errno = ENOENT;
724 return talloc_asprintf(NULL, "FAILED:%s", strerror(errno));
725 }
727 static char *linearize_dir(char **dir, unsigned int *num)
728 {
729 char *result = NULL;
730 unsigned int i;
732 if (!dir)
733 return bool_to_errstring(false);
735 if (!*num) {
736 free(dir);
737 return talloc_strdup(NULL, "");
738 }
740 sort_dir(dir, *num);
741 for (i = 0; i < *num; i++)
742 result = talloc_asprintf_append(result, "%s\n", dir[i]);
743 free(dir);
744 return result;
745 }
747 static char *linearize_read(char *read, unsigned int *size)
748 {
749 char *ret;
751 if (!read)
752 return bool_to_errstring(false);
754 ret = talloc_asprintf(NULL, "%i:%.*s", *size, *size, read);
755 free(read);
756 return ret;
757 }
759 static char *linearize_perms(struct xs_permissions *perms, unsigned int *size)
760 {
761 char *ret = NULL;
762 unsigned int i;
764 if (!perms)
765 return bool_to_errstring(false);
767 for (i = 0; i < *size; i++)
768 ret = talloc_asprintf_append(ret, "(%u %u)",
769 perms[i].id, perms[i].perms);
771 free(perms);
772 return ret;
773 }
775 /* Do the next operation, return the results. */
776 static char *do_next_op(struct ops *ops, void *h, int state, bool verbose)
777 {
778 char *name;
779 unsigned int num;
780 char *ret;
782 if (verbose)
783 printf("State %i: ", state);
785 name = random_path(&state);
786 switch (get_randomness(&state) % 9) {
787 case 0:
788 if (verbose)
789 printf("DIR %s\n", name);
790 ret = linearize_dir(ops->dir(h, name, &num), &num);
791 break;
792 case 1:
793 if (verbose)
794 printf("READ %s\n", name);
795 ret = linearize_read(ops->read(h, name, &num), &num);
796 break;
797 case 2: {
798 char *contents = talloc_asprintf(NULL, "%i",
799 get_randomness(&state));
800 unsigned int len = get_randomness(&state)%(strlen(contents)+1);
801 if (verbose)
802 printf("WRITE %s %.*s\n", name, len, contents);
803 ret = bool_to_errstring(ops->write(h, name, contents, len));
804 talloc_steal(ret, contents);
805 break;
806 }
807 case 3:
808 if (verbose)
809 printf("MKDIR %s\n", name);
810 ret = bool_to_errstring(ops->mkdir(h, name));
811 break;
812 case 4:
813 if (verbose)
814 printf("RM %s\n", name);
815 ret = bool_to_errstring(ops->rm(h, name));
816 break;
817 case 5:
818 if (verbose)
819 printf("GETPERMS %s\n", name);
820 ret = linearize_perms(ops->get_perms(h, name, &num),
821 &num);
822 break;
823 case 6: {
824 unsigned int i, num = get_randomness(&state)%8;
825 struct xs_permissions perms[num];
827 if (verbose)
828 printf("SETPERMS %s: ", name);
829 for (i = 0; i < num; i++) {
830 perms[i].id = get_randomness(&state)%8;
831 perms[i].perms = get_randomness(&state)%4;
832 if (verbose)
833 printf("%i%c ", perms[i].id,
834 perms[i].perms == XS_PERM_WRITE ? 'W'
835 : perms[i].perms == XS_PERM_READ ? 'R'
836 : perms[i].perms ==
837 (XS_PERM_READ|XS_PERM_WRITE) ? 'B'
838 : 'N');
839 }
840 if (verbose)
841 printf("\n");
842 ret = bool_to_errstring(ops->set_perms(h, name, perms,
843 num));
844 break;
845 }
846 case 7: {
847 if (verbose)
848 printf("START %s\n", name);
849 ret = bool_to_errstring(ops->transaction_start(h));
850 if (streq(ret, "OK")) {
851 talloc_free(ret);
852 ret = talloc_asprintf(NULL, "OK:START-TRANSACT");
853 }
855 break;
856 }
857 case 8: {
858 bool abort = (get_randomness(&state) % 2);
860 if (verbose)
861 printf("STOP %s\n", abort ? "ABORT" : "COMMIT");
862 ret = bool_to_errstring(ops->transaction_end(h, abort));
863 if (streq(ret, "OK")) {
864 talloc_free(ret);
865 ret = talloc_strdup(NULL, "OK:STOP-TRANSACT");
866 }
867 break;
868 }
869 default:
870 barf("Impossible randomness");
871 }
873 talloc_steal(ret, name);
874 return ret;
875 }
877 static int daemon_pid;
879 static void cleanup_xs_ops(void)
880 {
881 char *cmd;
883 if (daemon_pid) {
884 kill(daemon_pid, SIGTERM);
885 waitpid(daemon_pid, NULL, 0);
886 daemon_pid = 0;
887 }
889 cmd = talloc_asprintf(NULL, "rm -rf testsuite/tmp/*");
890 do_command(cmd);
891 talloc_free(cmd);
892 }
894 static void cleanup_file_ops(const char *dir)
895 {
896 char *cmd;
898 cmd = talloc_asprintf(NULL, "rm -rf %s %s.transact", dir, dir);
899 do_command(cmd);
900 talloc_free(cmd);
901 }
903 static void cleanup(const char *dir)
904 {
905 cleanup_xs_ops();
906 cleanup_file_ops(dir);
907 }
909 static void setup_file_ops(const char *dir)
910 {
911 struct xs_permissions perm = { .id = 0, .perms = XS_PERM_READ };
912 struct file_ops_info *h = file_handle(dir);
913 if (mkdir(dir, 0700) != 0)
914 barf_perror("Creating directory %s", dir);
915 if (mkdir(talloc_asprintf(h, "%s/tool", dir), 0700) != 0)
916 barf_perror("Creating directory %s/tool", dir);
917 if (!file_set_perms(h, talloc_strdup(h, "/"), &perm, 1))
918 barf_perror("Setting root perms in %s", dir);
919 if (!file_set_perms(h, talloc_strdup(h, "/tool"), &perm, 1))
920 barf_perror("Setting root perms in %s/tool", dir);
921 file_close(h);
922 }
924 static void setup_xs_ops(void)
925 {
926 int fds[2];
928 /* Start daemon. */
929 pipe(fds);
930 if ((daemon_pid = fork())) {
931 /* Child writes PID when its ready: we wait for that. */
932 char buffer[20];
933 close(fds[1]);
934 if (read(fds[0], buffer, sizeof(buffer)) < 0)
935 barf("Failed to summon daemon");
936 close(fds[0]);
937 } else {
938 dup2(fds[1], STDOUT_FILENO);
939 close(fds[0]);
940 #if 1
941 execlp("valgrind", "valgrind", "-q", "--suppressions=testsuite/vg-suppressions", "xenstored_test", "--output-pid",
942 "--no-fork", NULL);
943 #else
944 execlp("./xenstored_test", "xenstored_test", "--output-pid",
945 "--no-fork", NULL);
946 #endif
947 exit(1);
948 }
949 }
951 static void setup(const char *dir)
952 {
953 setup_file_ops(dir);
954 setup_xs_ops();
955 };
957 struct simple_data
958 {
959 unsigned int seed;
960 bool print_progress;
961 bool fast;
962 struct ops *ops;
963 const char *dir;
964 };
966 /* Just a random test. Don't care about results, just that it doesn't
967 * go boom. */
968 static unsigned int try_simple(const bool *trymap,
969 unsigned int number,
970 bool verbose,
971 void *_data)
972 {
973 unsigned int i, print;
974 void *h;
975 char *snapshot = NULL;
976 struct simple_data *data = _data;
978 if (data->ops == &xs_ops) {
979 cleanup_xs_ops();
980 setup_xs_ops();
981 } else {
982 cleanup_file_ops(data->dir);
983 setup_file_ops(data->dir);
984 }
985 h = data->ops->handle(data->dir);
987 print = number / 76;
988 if (!print)
989 print = 1;
991 for (i = 0; i < number; i++) {
992 char *ret;
994 if (data->print_progress) {
995 if (i % print == 0) {
996 printf(".");
997 fflush(stdout);
998 }
999 }
1001 if (trymap && !trymap[i])
1002 continue;
1004 ret = do_next_op(data->ops, h, i + data->seed, verbose);
1005 if (verbose)
1006 printf("-> %.*s\n",
1007 (int)(strchr(ret, '\n') - ret), ret);
1008 if (streq(ret, "FAILED:Bad file descriptor"))
1009 goto out;
1010 if (kill(daemon_pid, 0) != 0)
1011 goto out;
1013 if (!data->fast) {
1014 if (streq(ret, "OK:START-TRANSACT")) {
1015 void *pre = data->ops->handle(data->dir);
1017 snapshot = dump(data->ops, pre);
1018 if (!snapshot)
1019 goto out;
1020 data->ops->close(pre);
1021 } else if (streq(ret, "OK:STOP-TRANSACT")) {
1022 talloc_free(snapshot);
1023 snapshot = NULL;
1027 talloc_free(ret);
1029 if (snapshot) {
1030 void *pre = data->ops->handle(data->dir);
1031 char *contents;
1033 contents = dump(data->ops, pre);
1034 if (!contents)
1035 goto out;
1037 if (!streq(contents, snapshot))
1038 goto out;
1040 talloc_free(contents);
1041 data->ops->close(pre);
1044 out:
1045 data->ops->close(h);
1046 return i;
1049 /* Binary elimination: try eliminating all of them, then reduce. */
1050 static void reduce(bool *map,
1051 unsigned int number,
1052 unsigned int try_start, unsigned int try_num,
1053 unsigned int (*try)(const bool *map,
1054 unsigned int number,
1055 bool verbose,
1056 void *),
1057 void *data)
1059 bool newmap[number];
1061 if (try_num == 0)
1062 return;
1064 /* Try skipping everything between start and end. */
1065 memcpy(newmap, map, sizeof(newmap));
1066 memset(newmap + try_start, 0, try_num * sizeof(bool));
1068 /* We want the *same* failure: must fail at "number-1". */
1069 if (try(newmap, number, false, data) == number - 1) {
1070 memset(map + try_start, 0, try_num * sizeof(bool));
1071 return;
1074 if (try_num == 1)
1075 return;
1077 /* Try each half... */
1078 reduce(map, number, try_start, try_num/2, try, data);
1079 reduce(map, number, try_start + try_num/2, try_num - try_num/2,
1080 try, data);
1083 static void reduce_problem(unsigned int failed,
1084 unsigned int (*try)(const bool *map,
1085 unsigned int number,
1086 bool verbose,
1087 void *data),
1088 void *data)
1090 bool map[failed];
1092 memset(map, 1, sizeof(map));
1093 reduce(map, failed, 0, failed-1, try, data);
1095 printf("Cut down:\n");
1096 if (try(map, failed, true, data) != failed - 1) {
1097 printf("Except, that didn't actually fail. Bugger!");
1098 exit(2);
1100 exit(1);
1103 /* Just a random test. Don't care about results, just that it doesn't
1104 * go boom. */
1105 static void simple_test(const char *dir,
1106 unsigned int iters, unsigned int seed,
1107 bool fast, bool verbose)
1109 struct simple_data data;
1110 unsigned int try;
1112 data.seed = seed;
1113 data.print_progress = !verbose;
1114 data.fast = fast;
1115 data.ops = &xs_ops;
1116 data.dir = dir;
1118 try = try_simple(NULL, iters, verbose, &data);
1119 if (try == iters) {
1120 cleanup_xs_ops();
1121 exit(0);
1123 printf("Failed on iteration %u of seed %u\n", try + 1, seed);
1124 data.print_progress = false;
1125 reduce_problem(try + 1, try_simple, &data);
1128 static bool ops_equal(struct ops *a, void *ah,
1129 struct ops *b, void *bh,
1130 const char *node,
1131 struct ops **fail)
1133 char **dira = NULL, **dirb = NULL;
1134 char *dataa = NULL, *datab = NULL;
1135 unsigned int i, numa, numb, lena, lenb;
1136 struct xs_permissions *permsa = NULL, *permsb = NULL;
1137 unsigned int numpermsa, numpermsb;
1138 char *nodename;
1139 bool ret = false;
1141 /* Ignore tool/ dir. */
1142 if (streq(node, "/tool"))
1143 return true;
1145 /* FILE backend expects talloc'ed pointer. */
1146 nodename = talloc_strdup(NULL, node);
1147 permsa = a->get_perms(ah, nodename, &numpermsa);
1148 if (!permsa) {
1149 *fail = a;
1150 goto out;
1152 permsb = b->get_perms(bh, nodename, &numpermsb);
1153 if (!permsb) {
1154 *fail = b;
1155 goto out;
1157 if (numpermsa != numpermsb)
1158 goto out;
1159 for (i = 0; i < numpermsa; i++) {
1160 if (permsa[i].perms != permsb[i].perms)
1161 goto out;
1162 if (permsa[i].id != permsb[i].id)
1163 goto out;
1166 /* Non-pure-directory nodes contain data. */
1167 dataa = a->read(ah, nodename, &lena);
1168 if (!dataa && errno != EISDIR) {
1169 *fail = a;
1170 goto out;
1172 datab = b->read(bh, nodename, &lenb);
1173 if (!datab && errno != EISDIR) {
1174 *fail = b;
1175 goto out;
1178 if (dataa) {
1179 if (!datab)
1180 goto out;
1181 if (lena != lenb)
1182 goto out;
1184 if (memcmp(dataa, datab, lena) != 0)
1185 goto out;
1186 } else
1187 if (datab)
1188 goto out;
1190 /* Everything is a directory. */
1191 dira = a->dir(ah, nodename, &numa);
1192 if (!dira) {
1193 *fail = a;
1194 goto out;
1196 dirb = b->dir(bh, nodename, &numb);
1197 if (!dirb) {
1198 *fail = b;
1199 goto out;
1201 if (numa != numb)
1202 goto out;
1203 sort_dir(dira, numa);
1204 sort_dir(dirb, numb);
1205 for (i = 0; i < numa; i++) {
1206 char subnode[strlen(node) + 1 + strlen(dira[i]) + 1];
1208 if (!streq(dira[i], dirb[i]))
1209 goto out;
1211 strcpy(subnode, node);
1212 if (!streq(node, "/"))
1213 strcat(subnode, "/");
1214 strcat(subnode, dira[i]);
1215 if (!ops_equal(a, ah, b, bh, subnode, fail))
1216 goto out;
1219 ret = true;
1220 out:
1221 free(permsa);
1222 free(permsb);
1223 free(dataa);
1224 free(datab);
1225 free(dira);
1226 free(dirb);
1227 talloc_free(nodename);
1228 return ret;
1231 struct diff_data
1233 unsigned int seed;
1234 bool print_progress;
1235 bool fast;
1236 const char *dir;
1237 };
1239 /* Differential: try both file and xs backend, watch for differences. */
1240 static unsigned int try_diff(const bool *trymap,
1241 unsigned int number,
1242 bool verbose,
1243 void *_data)
1245 void *fileh, *xsh;
1246 bool transact = false;
1247 struct ops *fail;
1248 struct diff_data *data = _data;
1249 unsigned int i, print;
1251 cleanup(data->dir);
1252 setup(data->dir);
1254 fileh = file_handle(data->dir);
1255 xsh = xs_handle(data->dir);
1257 print = number / 76;
1258 if (!print)
1259 print = 1;
1261 for (i = 0; i < number; i++) {
1262 char *file, *xs;
1264 if (data->print_progress) {
1265 if (i % print == 0) {
1266 printf(".");
1267 fflush(stdout);
1270 if (trymap && !trymap[i])
1271 continue;
1273 if (verbose)
1274 printf("FILE: ");
1276 file = do_next_op(&file_ops, fileh, i+data->seed, verbose);
1277 if (verbose)
1278 printf("-> %.*s\n",
1279 (int)(strchr(file, '/') - file), file);
1281 if (verbose)
1282 printf("XS: ");
1283 xs = do_next_op(&xs_ops, xsh, i+data->seed, verbose);
1284 if (verbose)
1285 printf("-> %.*s\n", (int)(strchr(xs, '/') - xs), xs);
1287 if (!streq(file, xs))
1288 goto out;
1290 if (strstarts(file, "OK:START-TRANSACT:"))
1291 transact = true;
1292 else if (streq(file, "OK:STOP-TRANSACT"))
1293 transact = false;
1295 talloc_free(file);
1296 talloc_free(xs);
1298 if (data->fast)
1299 continue;
1301 fail = NULL;
1302 if (!ops_equal(&xs_ops, xsh, &file_ops, fileh, "/", &fail)) {
1303 if (fail)
1304 barf("%s failed during test\n", fail->name);
1305 if (verbose)
1306 printf("Trees differ:\nXS:%s\nFILE%s\n",
1307 dump(&xs_ops, xsh),
1308 dump(&file_ops, fileh));
1309 goto out;
1312 if (transact) {
1313 void *fileh_pre = file_handle(data->dir);
1314 void *xsh_pre = xs_handle(data->dir);
1316 fail = NULL;
1317 if (!ops_equal(&xs_ops, xsh_pre, &file_ops, fileh_pre,
1318 "/", &fail)) {
1319 if (fail)
1320 barf("%s failed during transact\n",
1321 fail->name);
1323 xs_daemon_close(xsh_pre);
1324 talloc_free(fileh_pre);
1325 goto out;
1327 xs_daemon_close(xsh_pre);
1328 talloc_free(fileh_pre);
1332 fail = NULL;
1333 if (data->fast)
1334 if (!ops_equal(&xs_ops, xsh, &file_ops, fileh, "/", &fail))
1335 barf("Final result not the same: try without --fast");
1336 out:
1337 file_ops.close(fileh);
1338 xs_ops.close(xsh);
1339 return i;
1342 /* Differential random test: compare results against file backend. */
1343 static void diff_test(const char *dir,
1344 unsigned int iters, unsigned int seed, bool fast,
1345 bool verbose)
1347 struct diff_data data;
1348 unsigned int try;
1350 data.seed = seed;
1351 data.print_progress = !verbose;
1352 data.fast = fast;
1353 data.dir = dir;
1355 try = try_diff(NULL, iters, verbose, &data);
1356 if (try == iters) {
1357 cleanup_xs_ops();
1358 exit(0);
1360 printf("Failed on iteration %u of seed %u\n", try + 1, seed);
1361 data.print_progress = false;
1362 reduce_problem(try + 1, try_diff, &data);
1365 struct fail_data
1367 unsigned int seed;
1368 bool print_progress;
1369 const char *dir;
1370 };
1372 /* Try xs with inserted failures: every op should either succeed or fail. */
1373 static unsigned int try_fail(const bool *trymap,
1374 unsigned int number,
1375 bool verbose,
1376 void *_data)
1378 unsigned int i, print, tried = 0, aborted = 0;
1379 struct fail_data *data = _data;
1380 struct xs_handle *tmpxsh;
1381 struct file_ops_info *tmpfileh;
1382 void *fileh, *xsh;
1383 struct ops *fail;
1384 char seed[20];
1386 /* Make sure failures off to shut down. */
1387 if (daemon_pid)
1388 kill(daemon_pid, SIGUSR1);
1389 cleanup(data->dir);
1390 setup(data->dir);
1392 fileh = file_handle(data->dir);
1393 xsh = xs_handle(data->dir);
1395 print = number / 76;
1396 if (!print)
1397 print = 1;
1399 for (i = 0; i < number; i++) {
1400 unsigned int limit, failed;
1401 char *ret;
1403 /* A few times we fail due to other end OOM. */
1404 limit = 0;
1405 while (!xsh) {
1406 xsh = xs_handle(data->dir);
1407 if (!xsh && errno == ECONNREFUSED) {
1408 if (verbose)
1409 printf("Daemon refused connection\n");
1410 goto out;
1412 if (!xsh && limit++ == 5) {
1413 printf("Daemon failed conn 5 times\n");
1414 goto out;
1418 if (data->print_progress) {
1419 if (i % print == 0) {
1420 printf(".");
1421 fflush(stdout);
1424 if (trymap && !trymap[i])
1425 continue;
1427 /* Turn on failure. */
1428 sprintf(seed, "%i", data->seed + i);
1429 free(xs_debug_command(xsh, "failtest",seed,strlen(seed)+1));
1431 if (verbose)
1432 printf("(%i) seed %s ", i, seed);
1433 ret = do_next_op(&xs_ops, xsh, i + data->seed, verbose);
1434 if (streq(ret, "FAILED:Connection reset by peer")
1435 || streq(ret, "FAILED:Bad file descriptor")
1436 || streq(ret, "FAILED:Broken pipe")) {
1437 xs_close(xsh);
1438 xsh = NULL;
1439 failed = 2;
1440 } else if (strstarts(ret, "OK"))
1441 failed = 0;
1442 else
1443 failed = 1;
1445 tried++;
1446 if (xsh)
1447 aborted++;
1449 if (verbose)
1450 printf("-> %.*s\n",
1451 (int)(strchr(ret, '\n') - ret), ret);
1453 talloc_free(ret);
1455 /* Turn off failures using signal. */
1456 if (kill(daemon_pid, SIGUSR1) != 0) {
1457 if (verbose)
1458 printf("Failed to signal daemon\n");
1459 goto out;
1462 if (failed == 0) {
1463 /* Succeeded? Do same thing to file backend
1464 * to compare */
1465 try_applying:
1466 ret = do_next_op(&file_ops, fileh, i + data->seed,
1467 false);
1468 if (!strstarts(ret, "OK")) {
1469 if (!verbose)
1470 printf("File op failed on %i\n",
1471 i + data->seed);
1472 talloc_free(ret);
1473 goto out;
1475 talloc_free(ret);
1478 tmpxsh = xs_handle(data->dir);
1479 if (!tmpxsh) {
1480 if (verbose)
1481 printf("Failed to open signalled daemon");
1482 goto out;
1484 tmpfileh = file_handle(data->dir);
1486 fail = NULL;
1487 if (!ops_equal(&xs_ops, tmpxsh, &file_ops, tmpfileh, "/",
1488 &fail)) {
1489 if (fail) {
1490 if (verbose)
1491 printf("%s failed\n", fail->name);
1492 goto out;
1494 /* Maybe op succeeded: try comparing after local op? */
1495 if (failed == 2) {
1496 failed = 0;
1497 if (verbose)
1498 printf("(Looks like it succeeded)\n");
1499 xs_close(tmpxsh);
1500 file_close(tmpfileh);
1501 goto try_applying;
1503 if (verbose)
1504 printf("Trees differ:\nXS:%s\nFILE:%s\n",
1505 dump(&xs_ops, tmpxsh),
1506 dump(&file_ops, tmpfileh));
1507 xs_close(tmpxsh);
1508 file_close(tmpfileh);
1509 goto out;
1512 /* If we lost the xs handle, that ended the transaction */
1513 if (!xsh)
1514 file_transaction_end(fileh, true);
1516 xs_close(tmpxsh);
1517 file_close(tmpfileh);
1519 out:
1520 if (xsh)
1521 xs_close(xsh);
1522 return i;
1525 static void fail_test(const char *dir,
1526 unsigned int iters, unsigned int seed,
1527 bool fast __attribute__((unused)), bool verbose)
1529 struct fail_data data;
1530 unsigned int try;
1532 data.seed = seed;
1533 data.print_progress = !verbose;
1534 data.dir = dir;
1536 try = try_fail(NULL, iters, verbose, &data);
1537 if (try == iters) {
1538 cleanup_xs_ops();
1539 exit(0);
1541 printf("Failed on iteration %u of seed %u\n", try + 1, seed);
1542 fflush(stdout);
1543 data.print_progress = false;
1544 reduce_problem(try + 1, try_fail, &data);
1547 int main(int argc, char *argv[])
1549 bool verbose = false;
1550 bool simple = false;
1551 bool fast = false;
1552 bool fail = false;
1554 if (argv[1] && streq(argv[1], "--fail")) {
1555 fail = true;
1556 argv++;
1557 argc--;
1560 if (argv[1] && streq(argv[1], "--simple")) {
1561 simple = true;
1562 argv++;
1563 argc--;
1566 if (argv[1] && streq(argv[1], "--fast")) {
1567 fast = true;
1568 argv++;
1569 argc--;
1572 if (argv[1] && streq(argv[1], "--verbose")) {
1573 verbose = true;
1574 argv++;
1575 argc--;
1578 if (argc != 4)
1579 barf("Usage: xs_random [--fail|--simple] [--fast] [--verbose] <directory> <iterations> <seed>");
1581 talloc_enable_null_tracking();
1583 if (fail)
1584 fail_test(argv[1], atoi(argv[2]), atoi(argv[3]), fast, verbose);
1585 else if (simple)
1586 simple_test(argv[1], atoi(argv[2]), atoi(argv[3]), fast, verbose);
1587 else
1588 diff_test(argv[1], atoi(argv[2]), atoi(argv[3]), fast, verbose);
1589 exit(2);