1// Copyright 2017 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include <assert.h>
6#include <errno.h>
7#include <fcntl.h>
8#include <limits.h>
9#include <sched.h>
10#include <stdbool.h>
11#include <stdint.h>
12#include <stdio.h>
13#include <stdlib.h>
14#include <string.h>
15#include <threads.h>
16#include <time.h>
17#include <unistd.h>
18
19#include <sys/stat.h>
20#include <sys/types.h>
21
22#include <zircon/compiler.h>
23#include <zircon/listnode.h>
24#include <zircon/types.h>
25
26#include "filesystems.h"
27
28#define FAIL -1
29#define DONE 0
30
31#define BLKSIZE 8192
32#define FBUFSIZE 65536
33
34typedef struct worker worker_t;
35typedef struct random_op random_op_t;
36
37typedef struct env {
38    worker_t* all_workers;
39
40    mtx_t log_timer_lock;
41    cnd_t log_timer_cnd;
42
43    random_op_t* ops;
44    unsigned n_ops;
45
46    bool tests_finished;
47
48    list_node_t threads;
49
50    bool debug;
51} env_t;
52
53typedef struct worker {
54    worker_t* next;
55
56    env_t* env;
57
58    int fd;
59    ssize_t size;
60
61    char name[PATH_MAX];
62    unsigned seed;
63
64    unsigned opcnt;
65} worker_t;
66
67static bool init_environment(env_t*);
68static void add_random_ops(env_t* env);
69
70typedef struct thread_list {
71    list_node_t node;
72    thrd_t t;
73} thread_list_t;
74
75static bool worker_new(env_t* env, const char* fn, uint32_t size) {
76    worker_t* w = calloc(1, sizeof(worker_t));
77    ASSERT_NE(w, NULL, "");
78
79    // per-thread random seed
80    struct timespec ts;
81    clock_gettime(CLOCK_REALTIME, &ts);
82    w->seed = (int)ts.tv_nsec;
83
84    w->env = env;
85
86    snprintf(w->name, sizeof(w->name), "%s", fn);
87    w->size = size;
88    w->fd = -1;
89
90    w->opcnt = 0;
91
92    w->next = env->all_workers;
93    env->all_workers = w;
94
95    return true;
96}
97
98static void free_workers(env_t* env) {
99    worker_t* all_workers = env->all_workers;
100    for (worker_t* w = all_workers; w != NULL;) {
101        worker_t* next = w->next;
102        free(w);
103        w = next;
104    }
105}
106
107#define KB(n) ((n) * 1024)
108#define MB(n) ((n) * 1024 * 1024)
109
110static struct {
111    const char* name;
112    uint32_t size;
113} WORK[] = {
114    // one thread per work entry
115    { "thd0000", KB(5)},
116    { "thd0001", MB(10)},
117    { "thd0002", KB(512)},
118    { "thd0003", KB(512)},
119    { "thd0004", KB(512)},
120    { "thd0005", MB(20)},
121    { "thd0006", KB(512)},
122    { "thd0007", KB(512)},
123};
124
125static bool init_environment(env_t* env) {
126    // tests are run repeatedly, so reinitialize each time
127    env->all_workers = NULL;
128
129    list_initialize(&env->threads);
130
131    mtx_init(&env->log_timer_lock, mtx_plain);
132    cnd_init(&env->log_timer_cnd);
133
134    env->tests_finished = false;
135    env->debug = false;
136
137    add_random_ops(env);
138
139    // assemble the work
140    for (unsigned n = 0; n < countof(WORK); n++) {
141        ASSERT_TRUE(worker_new(env, WORK[n].name, WORK[n].size), "");
142    }
143
144    return true;
145}
146
147// wait until test finishes or timer suggests we may be hung
148static const unsigned TEST_MAX_RUNTIME = 120; // 120 sec max
149static int log_timer(void* arg) {
150    env_t* env = arg;
151    struct timespec ts;
152    clock_gettime(CLOCK_REALTIME, &ts);
153    ts.tv_sec += TEST_MAX_RUNTIME;
154
155    mtx_lock(&env->log_timer_lock);
156    cnd_timedwait(&env->log_timer_cnd, &env->log_timer_lock, &ts);
157    if (!env->tests_finished) {
158        exit(1); // causes remaining threads to abort
159    }
160    mtx_unlock(&env->log_timer_lock);
161    return 0;
162}
163
164static void task_debug_op(worker_t* w, const char* fn) {
165    env_t* env = w->env;
166
167    w->opcnt++;
168    if (env->debug) {
169        fprintf(stderr, "%s[%d] %s\n", w->name, w->opcnt, fn);
170    }
171}
172
173static void task_error(worker_t* w, const char* fn, const char* msg) {
174    int errnum = errno;
175    char buf[128];
176    strerror_r(errnum, buf, sizeof(buf));
177    fprintf(stderr, "%s ERROR %s(%s): %s(%d)\n", w->name, fn,
178            msg, buf, errnum);
179}
180
181static int task_create_a(worker_t* w) {
182    // put a page of data into ::/a
183    task_debug_op(w, "t: create_a");
184    int fd = open("::/a", O_RDWR+O_CREAT, 0666);
185    if (fd < 0) {
186        // errno may be one of EEXIST
187        if (errno != EEXIST) {
188            task_error(w, "t: create_a", "open");
189            return FAIL;
190        }
191    } else {
192        char buf[BLKSIZE];
193        memset(buf, 0xab, sizeof(buf));
194        ssize_t len = write(fd, buf, sizeof(buf));
195        if (len < 0) {
196            task_error(w, "t: create_a", "write");
197            return FAIL;
198        }
199        assert(len == sizeof(buf));
200        EXPECT_EQ(close(fd), 0, "");
201    }
202    return DONE;
203}
204
205static int task_create_b(worker_t* w) {
206    // put a page of data into ::/b
207    task_debug_op(w, "t: create_b");
208    int fd = open("::/b", O_RDWR+O_CREAT, 0666);
209    if (fd < 0) {
210        // errno may be one of EEXIST
211        if (errno != EEXIST) {
212            task_error(w, "t: create_b", "open");
213            return FAIL;
214        }
215    } else {
216        char buf[BLKSIZE];
217        memset(buf, 0xba, sizeof(buf));
218        ssize_t len = write(fd, buf, sizeof(buf));
219        if (len < 0) {
220            task_error(w, "t: create_a", "write");
221            return FAIL;
222        }
223        assert(len == sizeof(buf));
224        EXPECT_EQ(close(fd), 0, "");
225    }
226    return DONE;
227}
228
229static int task_rename_ab(worker_t* w) {
230    // rename ::/a -> ::/b
231    task_debug_op(w, "t: rename_ab");
232    int rc = rename("::/a", "::/b");
233    if (rc < 0) {
234        // errno may be one of ENOENT
235        if (errno != ENOENT) {
236            task_error(w, "t: rename_ab", "rename");
237            return FAIL;
238        }
239    }
240    return DONE;
241}
242
243static int task_rename_ba(worker_t* w) {
244    // rename ::/b -> ::/a
245    task_debug_op(w, "t: rename_ba");
246    int rc = rename("::/b", "::/a");
247    if (rc < 0) {
248        // errno may be one of ENOENT
249        if (errno != ENOENT) {
250            task_error(w, "t: rename_ba", "rename");
251            return FAIL;
252        }
253    }
254    return DONE;
255}
256
257static int task_make_private_dir(worker_t* w) {
258    // mkdir ::/threadname
259    task_debug_op(w, "t: make_private_dir");
260    char fname[PATH_MAX];
261    snprintf(fname, sizeof(fname), "::/%s", w->name);
262    int rc = mkdir(fname, 0755);
263    if (rc < 0) {
264        // errno may be one of EEXIST, ENOENT
265        if (errno != ENOENT && errno != EEXIST) {
266            task_error(w, "t: make_private_dir", "mkdir");
267            return FAIL;
268        }
269    }
270    return DONE;
271}
272
273static int task_rmdir_private_dir(worker_t* w) {
274    // unlink ::/threadname
275    task_debug_op(w, "t: remove_private_dir");
276    char fname[PATH_MAX];
277    snprintf(fname, sizeof(fname), "::/%s", w->name);
278    int rc = rmdir(fname);
279    if (rc < 0) {
280        // errno may be one of ENOENT, ENOTEMPTY,
281        if (errno != ENOENT && errno != ENOTEMPTY) {
282            task_error(w, "t: remove_private_dir", "rmdir");
283            return FAIL;
284        }
285    }
286    return DONE;
287}
288
289static int task_unlink_a(worker_t* w) {
290    // unlink ::/a
291    task_debug_op(w, "t: unlink_a");
292    int rc = unlink("::/a");
293    if (rc < 0) {
294        // errno may be one of ENOENT
295        if (errno != ENOENT) {
296            task_error(w, "t: unlink_a", "unlink");
297            return FAIL;
298        }
299    }
300    return DONE;
301}
302
303static int task_unlink_b(worker_t* w) {
304    // unlink ::/b
305    task_debug_op(w, "t: unlink_b");
306    int rc = unlink("::/b");
307    if (rc < 0) {
308        // errno may be one of ENOENT
309        if (errno != ENOENT) {
310            task_error(w, "t: unlink_b", "unlink");
311            return FAIL;
312        }
313    }
314    return DONE;
315}
316
317static int task_mkdir_private_b(worker_t* w) {
318    // mkdir ::/threadname/b
319    task_debug_op(w, "t: mkdir_private_b");
320    char fname[PATH_MAX];
321    snprintf(fname, sizeof(fname), "::/%s/b", w->name);
322    int rc = mkdir(fname, 0755);
323    if (rc < 0) {
324        // errno may be one of EEXIST, ENOENT, ENOTDIR
325        if (errno != ENOENT && errno != ENOENT && errno != ENOTDIR) {
326            task_error(w, "t: mkdir_private_b", "mkdir");
327            return FAIL;
328        }
329    }
330    return DONE;
331}
332
333static int task_rmdir_private_b(worker_t* w) {
334    // unlink ::/threadname/b
335    task_debug_op(w, "t: rmdir_private_b");
336    char fname[PATH_MAX];
337    snprintf(fname, sizeof(fname), "::/%s/b", w->name);
338    int rc = rmdir(fname);
339    if (rc < 0) {
340        // errno may be one of ENOENT, ENOTDIR, ENOTEMPTY
341        if (errno != ENOENT && errno != ENOTDIR && errno != ENOTDIR) {
342            task_error(w, "t: rmdir_private_b", "rmdir");
343            return FAIL;
344        }
345    }
346    return DONE;
347}
348
349static int task_move_a_to_private(worker_t* w) {
350    // mv ::/a -> ::/threadname/a
351    task_debug_op(w, "t: mv_a_to__private");
352    char fname[PATH_MAX];
353    snprintf(fname, sizeof(fname), "::/%s/a", w->name);
354    int rc = rename("::/a", fname);
355    if (rc < 0) {
356        // errno may be one of EEXIST, ENOENT, ENOTDIR
357        if (errno != EEXIST && errno != ENOENT && errno != ENOTDIR) {
358            task_error(w, "t: mv_a_to__private", "rename");
359            return FAIL;
360        }
361    }
362    return DONE;
363}
364
365static int task_write_private_b(worker_t* w) {
366    // put a page of data into ::/threadname/b
367    task_debug_op(w, "t: write_private_b");
368    char fname[PATH_MAX];
369    snprintf(fname, sizeof(fname), "::/%s/b", w->name);
370    int fd = open(fname, O_RDWR+O_EXCL+O_CREAT, 0666);
371    if (fd < 0) {
372        // errno may be one of ENOENT, EISDIR, ENOTDIR, EEXIST
373        if (errno != ENOENT && errno != EISDIR &&
374            errno != ENOTDIR && errno != EEXIST) {
375            task_error(w, "t: write_private_b", "open");
376            return FAIL;
377        }
378    } else {
379        char buf[BLKSIZE];
380        memset(buf, 0xba, sizeof(buf));
381        ssize_t len = write(fd, buf, sizeof(buf));
382        if (len < 0) {
383            task_error(w, "t: write_private_b", "write");
384            return FAIL;
385        }
386        assert(len == sizeof(buf));
387        EXPECT_EQ(close(fd), 0, "");
388    }
389    return DONE;
390}
391
392static int task_rename_private_ba(worker_t* w) {
393    // move ::/threadname/b -> ::/a
394    task_debug_op(w, "t: rename_private_ba");
395    char fname[PATH_MAX];
396    snprintf(fname, sizeof(fname), "::/%s/b", w->name);
397    int rc = rename(fname, "::/a");
398    if (rc < 0) {
399        // errno may be one of EEXIST, ENOENT
400        if (errno != EEXIST && errno != ENOENT) {
401            task_error(w, "t: rename_private_ba", "rename");
402            return FAIL;
403        }
404    }
405    return DONE;
406}
407
408static int task_rename_private_ab(worker_t* w) {
409    // move ::/threadname/a -> ::/b
410    task_debug_op(w, "t: rename_private_ab");
411    char fname[PATH_MAX];
412    snprintf(fname, sizeof(fname), "::/%s/a", w->name);
413    int rc = rename(fname, "::/b");
414    if (rc < 0) {
415        // errno may be one of EEXIST, ENOENT
416        if (errno != EEXIST && errno != ENOENT) {
417            task_error(w, "t: rename_private_ab", "rename");
418            return FAIL;
419        }
420    }
421    return DONE;
422}
423
424static int task_open_private_a(worker_t* w) {
425    // close(fd); fd <- open("::/threadhame/a")
426    task_debug_op(w, "t: open_private_a");
427    if (w->fd >= 0) {
428        EXPECT_EQ(close(w->fd), 0, "");
429    }
430    char fname[PATH_MAX];
431    snprintf(fname, sizeof(fname), "::/%s/a", w->name);
432    w->fd = open(fname, O_RDWR+O_CREAT+O_EXCL, 0666);
433    if (w->fd < 0) {
434        if (errno == EEXIST) {
435            w->fd = open(fname, O_RDWR+O_EXCL);
436            if (w->fd < 0) {
437                task_error(w, "t: open_private_a", "open-existing");
438                return FAIL;
439            }
440        } else {
441            // errno may be one of EEXIST, ENOENT
442            if (errno != ENOENT) {
443                task_error(w, "t: open_private_a", "open");
444                return FAIL;
445            }
446        }
447    }
448    return DONE;
449}
450
451static int task_close_fd(worker_t* w) {
452    // close(fd)
453    task_debug_op(w, "t: close_fd");
454    if (w->fd >= 0) {
455        int rc = close(w->fd);
456        if (rc < 0) {
457            // errno may be one of ??
458            task_error(w, "t: close_fd", "close");
459            return FAIL;
460        }
461        w->fd = -1;
462    }
463    return DONE;
464}
465
466static int task_write_fd_big(worker_t* w) {
467    // write(fd, big buffer, ...)
468    task_debug_op(w, "t: write_fd_big");
469    if (w->fd >= 0) {
470        char buf[FBUFSIZE];
471        memset(buf, 0xab, sizeof(buf));
472        ssize_t len = write(w->fd, buf, sizeof(buf));
473        if (len < 0) {
474            // errno may be one of ??
475            task_error(w, "t: write_fd_small", "write");
476            return FAIL;
477        } else {
478            assert(len == sizeof(buf));
479            off_t off = lseek(w->fd, 0, SEEK_CUR);
480            assert(off >= 0);
481            if (off >= w->size) {
482                off = lseek(w->fd, 0, SEEK_SET);
483                assert(off == 0);
484            }
485        }
486    }
487    return DONE;
488}
489
490static int task_write_fd_small(worker_t* w) {
491    // write(fd, small buffer, ...)
492    task_debug_op(w, "t: write_fd_small");
493    if (w->fd >= 0) {
494        char buf[BLKSIZE];
495        memset(buf, 0xab, sizeof(buf));
496        ssize_t len = write(w->fd, buf, sizeof(buf));
497        if (len < 0) {
498            // errno may be one of ??
499            task_error(w, "t: write_fd_small", "write");
500            return FAIL;
501        } else {
502            assert(len == sizeof(buf));
503            off_t off = lseek(w->fd, 0, SEEK_CUR);
504            assert(off >= 0);
505            if (off >= w->size) {
506                off = lseek(w->fd, 0, SEEK_SET);
507                assert(off == 0);
508            }
509        }
510    }
511    return DONE;
512}
513
514static int task_truncate_fd(worker_t* w) {
515    // ftruncate(fd)
516    task_debug_op(w, "t: truncate_fd");
517    if (w->fd >= 0) {
518        int rc = ftruncate(w->fd, 0);
519        if (rc < 0) {
520            // errno may be one of ??
521            task_error(w, "t: truncate_fd", "truncate");
522            return FAIL;
523        }
524    }
525    return DONE;
526}
527
528static int task_utime_fd(worker_t* w) {
529    // utime(fd)
530    task_debug_op(w, "t: utime_fd");
531    if (w->fd >= 0) {
532        struct timespec ts[2] = {
533            { .tv_nsec = UTIME_OMIT }, // no atime
534            { .tv_nsec = UTIME_NOW }, // mtime == now
535        };
536        int rc = futimens(w->fd, ts);
537        if (rc < 0) {
538            task_error(w, "t: utime_fd", "futimens");
539            return FAIL;
540        }
541    }
542    return DONE;
543}
544
545static int task_seek_fd_end(worker_t* w) {
546    task_debug_op(w, "t: seek_fd_end");
547    if (w->fd >= 0) {
548        int rc = lseek(w->fd, 0, SEEK_END);
549        if (rc < 0) {
550            // errno may be one of ??
551            task_error(w, "t: seek_fd_end", "lseek");
552            return FAIL;
553        }
554    }
555    return DONE;
556}
557
558static int task_seek_fd_start(worker_t* w) {
559    // fseek(fd, SEEK_SET, 0)
560    task_debug_op(w, "t: seek_fd_start");
561    if (w->fd >= 0) {
562        int rc = lseek(w->fd, 0, SEEK_SET);
563        if (rc < 0) {
564            // errno may be one of ??
565            task_error(w, "t: seek_fd_start", "lseek");
566            return FAIL;
567        }
568    }
569    return DONE;
570}
571
572static int task_truncate_a(worker_t* w) {
573    // truncate("::/a")
574    int rc = truncate("::/a", 0);
575    if (rc < 0) {
576        // errno may be one of ENOENT
577        if (errno != ENOENT) {
578            task_error(w, "t: truncate_a", "truncate");
579            return FAIL;
580        }
581    }
582    return DONE;
583}
584
585static struct random_op {
586    const char* name;
587    int (*fn)(worker_t*);
588    unsigned weight;
589} OPS[] = {
590    {"task_create_a", task_create_a, 1},
591    {"task_create_b", task_create_b, 1},
592    {"task_rename_ab", task_rename_ab, 4},
593    {"task_rename_ba", task_rename_ba, 4},
594    {"task_make_private_dir", task_make_private_dir, 4},
595    {"task_move_a_to_private", task_move_a_to_private, 1},
596    {"task_write_private_b", task_write_private_b, 1},
597    {"task_rename_private_ba", task_rename_private_ba, 1},
598    {"task_rename_private_ab", task_rename_private_ab, 1},
599    {"task_open_private_a", task_open_private_a, 5},
600    {"task_close_fd", task_close_fd, 2},
601    {"task_write_fd_big", task_write_fd_big, 20},
602    {"task_write_fd_small", task_write_fd_small, 20},
603    {"task_truncate_fd", task_truncate_fd, 2},
604    {"task_utime_fd", task_utime_fd, 2},
605    {"task_seek_fd", task_seek_fd_start, 2},
606    {"task_seek_fd_end", task_seek_fd_end, 2},
607    {"task_truncate_a", task_truncate_a, 1},
608};
609
610// create a weighted list of operations for each thread
611static void add_random_ops(env_t* env) {
612    // expand the list of n*countof(OPS) operations weighted appropriately
613    int n_ops = 0;
614    for (unsigned i=0; i<countof(OPS); i++) {
615        n_ops += OPS[i].weight;
616    }
617    random_op_t* ops_list = malloc(n_ops * sizeof(random_op_t));
618    assert(ops_list != NULL);
619
620    unsigned op = 0;
621    for (unsigned i=0; i<countof(OPS); i++) {
622        unsigned n_op = OPS[i].weight;
623        for (unsigned j=0; j<n_op; j++) {
624            ops_list[op++] = OPS[i];
625        }
626    }
627    env->ops = ops_list;
628    env->n_ops = n_ops;
629}
630
631static const unsigned N_SERIAL_OPS = 4; // yield every 1/n ops
632
633static const unsigned MAX_OPS = 1000;
634static int do_random_ops(void* arg) {
635    worker_t* w = arg;
636    env_t* env = w->env;
637
638    // for some big number of operations
639    // do an operation and yield, repeat
640    for (unsigned i=0; i<MAX_OPS; i++) {
641        unsigned idx = rand_r(&w->seed) % env->n_ops;
642        random_op_t* op = env->ops+idx;
643
644        if (op->fn(w) != DONE) {
645            fprintf(stderr, "%s: op %s failed\n", w->name, op->name);
646            exit(1);
647        }
648        if ((idx % N_SERIAL_OPS) != 0)
649            thrd_yield();
650    }
651
652    // Close the worker's personal fd (if it is open) and
653    // unlink the worker directory.
654    fprintf(stderr, "work thread(%s) done\n", w->name);
655    task_close_fd(w);
656    unlink(w->name);
657
658    // currently, threads either return DONE or exit the test
659    return DONE;
660}
661
662bool test_random_op_multithreaded(void) {
663    BEGIN_TEST;
664
665    env_t env;
666    ASSERT_TRUE(init_environment(&env), "");
667
668    for (worker_t* w = env.all_workers; w != NULL; w = w->next) {
669        // start the workers on separate threads
670        thrd_t t;
671        ASSERT_EQ(thrd_create(&t, do_random_ops, w), thrd_success, "");
672
673        thread_list_t* thread = malloc(sizeof(thread_list_t));
674        ASSERT_NE(thread, NULL, "");
675        thread->t = t;
676        list_add_tail(&env.threads, &thread->node);
677    }
678
679    thrd_t timer_thread;
680    ASSERT_EQ(thrd_create(&timer_thread, log_timer, &env), thrd_success, "");
681
682    thread_list_t* next;
683    thread_list_t* prev = NULL;
684    list_for_every_entry(&env.threads, next, thread_list_t, node) {
685        int rc;
686        ASSERT_EQ(thrd_join(next->t, &rc), thrd_success, "");
687        ASSERT_EQ(rc, DONE, "Background thread joined, but failed");
688        if (prev) {
689            free(prev);
690        }
691        prev = next;
692    }
693    if (prev) {
694        free(prev);
695    }
696
697    // signal to timer that all threads have finished
698    mtx_lock(&env.log_timer_lock);
699    env.tests_finished = true;
700    mtx_unlock(&env.log_timer_lock);
701
702    ASSERT_EQ(cnd_broadcast(&env.log_timer_cnd), thrd_success, "");
703
704    int rc;
705    ASSERT_EQ(thrd_join(timer_thread, &rc), thrd_success, "");
706    ASSERT_EQ(rc, 0, "Timer thread failed");
707
708    free(env.ops);
709    free_workers(&env);
710
711    END_TEST;
712}
713
714RUN_FOR_ALL_FILESYSTEMS(random_ops_tests,
715    RUN_TEST_LARGE(test_random_op_multithreaded)
716)
717