diff --git a/etc/mtree/BSD.tests.dist b/etc/mtree/BSD.tests.dist index 1b2c94f42a6b..eb62812bfcd8 100644 --- a/etc/mtree/BSD.tests.dist +++ b/etc/mtree/BSD.tests.dist @@ -1,1154 +1,1156 @@ # $FreeBSD$ # # Please see the file src/etc/mtree/README before making changes to this file. # /set type=dir uname=root gname=wheel mode=0755 tags=package=tests . bin cat .. chflags .. chmod .. cp .. date .. dd .. echo .. expr .. ln .. ls .. mkdir .. mv .. pax .. pkill .. pwait .. rm .. rmdir .. sh builtins .. errors .. execution .. expansion .. invocation .. parameters .. parser .. set-e .. .. sleep .. test .. timeout .. .. cddl lib .. sbin .. usr.bin ctfconvert .. ztest .. .. usr.sbin dtrace common aggs .. arithmetic .. arrays .. assocs .. begin .. bitfields .. buffering .. builtinvar .. cg .. clauses .. cpc .. decls .. drops .. dtraceUtil .. end .. env .. enum .. error .. exit .. fbtprovider .. funcs .. grammar .. include .. inline .. io .. ip .. java_api .. json .. lexer .. llquantize .. mdb .. mib .. misc .. multiaggs .. offsetof .. operators .. pid .. plockstat .. pointers .. pragma .. predicates .. preprocessor .. print .. printa .. printf .. privs .. probes .. proc .. profile-n .. providers .. raise .. rates .. safety .. scalars .. sched .. scripting .. sdt .. sizeof .. speculation .. stability .. stack .. stackdepth .. stop .. strlen .. strtoll .. struct .. sugar .. syscall .. sysevent .. tick-n .. trace .. tracemem .. translators .. typedef .. types .. uctf .. union .. usdt .. ustack .. vars .. version .. .. i386 arrays .. funcs .. pid .. ustack .. .. amd64 arrays .. .. .. zfsd .. .. .. etc rc.d .. .. examples .. games .. gnu lib .. usr.bin diff .. .. .. lib atf libatf-c detail .. .. libatf-c++ detail .. .. test-programs .. .. csu dynamic .. dynamiclib .. static .. .. googletest gmock .. gmock_main .. gtest .. gtest_main .. .. libarchive .. libbe .. libc c063 .. db .. gen execve .. posix_spawn .. .. hash data .. .. iconv .. inet .. locale .. net getaddrinfo data .. .. .. nss .. regex data .. .. resolv .. rpc .. ssp .. setjmp .. stdio .. stdlib .. string .. sys .. time .. tls dso .. .. termios .. ttyio .. .. libcam .. libcasper services cap_dns .. cap_grp .. cap_pwd .. cap_sysctl .. .. .. libcrypt .. libdevdctl .. libexecinfo .. libkvm .. libmp .. libnv .. libproc .. libregex data .. .. librt .. libsbuf .. libsysdecode .. libthr dlopen .. .. libutil .. libxo .. msun .. .. libexec atf atf-check .. atf-pytest-wrapper .. atf-sh .. .. rtld-elf .. tftpd .. .. sbin bectl .. dhclient .. devd .. growfs .. ifconfig .. md5 .. mdconfig .. newfs_msdos .. nvmecontrol .. pfctl files .. .. ping .. route .. .. secure lib .. libexec .. usr.bin .. usr.sbin .. .. share examples tests atf .. googletest .. plain .. tap .. .. .. zoneinfo .. .. sys acl .. aio .. audit .. auditpipe .. capsicum .. cddl zfs bin .. include .. tests acl cifs .. nontrivial .. trivial .. .. atime .. bootfs .. cache .. cachefile .. clean_mirror .. cli_root zfs_upgrade .. zfs_promote .. zfs_clone .. zfs_property .. zfs_destroy .. zpool_create .. zpool_history .. zpool_expand .. zpool_remove .. zfs_mount .. zfs_unshare .. zdb .. zpool_online .. zpool_get .. zpool_export .. zfs_copies .. zfs_get .. zfs .. zpool_clear .. zpool_import blockfiles .. .. zpool .. zpool_offline .. zpool_replace .. zfs_rollback .. zpool_set .. zfs_send .. zfs_set .. zpool_detach .. zfs_diff .. zpool_scrub .. zfs_inherit .. zfs_snapshot .. zfs_share .. zpool_destroy .. zpool_status .. zfs_unmount .. zfs_receive .. zfs_create .. zpool_upgrade blockfiles .. .. zpool_add .. zfs_rename .. zpool_attach .. zfs_reservation .. .. cli_user misc .. zfs_list .. zpool_iostat .. zpool_list .. .. compression .. ctime .. delegate .. devices .. exec .. grow_pool .. grow_replicas .. history .. hotplug .. hotspare .. inheritance .. interop .. inuse .. iscsi .. large_files .. largest_pool .. link_count .. migration .. mmap .. mount .. mv_files .. nestedfs .. no_space .. online_offline .. pool_names .. poolversion .. quota .. redundancy .. refquota .. refreserv .. rename_dirs .. replacement .. reservation .. rootpool .. rsend .. scrub_mirror .. slog .. snapshot .. snapused .. sparse .. threadsappend .. truncate .. txg_integrity .. userquota .. utils_test .. write_dirs .. xattr .. zfsd .. zil .. zinject .. zones .. zvol zvol_ENOSPC .. zvol_cli .. zvol_misc .. zvol_swap .. .. zvol_thrash .. .. .. .. devrandom .. dtrace .. fifo .. file .. fs fusefs .. tmpfs .. .. geom class concat .. eli .. gate .. gpt .. mirror .. multipath .. nop .. part .. raid3 .. shsec .. stripe .. uzip etalon .. .. .. .. kern acct .. execve .. pipe .. .. kqueue libkqueue .. .. mac bsdextended .. portacl .. .. mqueue .. net routing .. .. netgraph .. netinet .. netinet6 frag6 .. .. netipsec tunnel .. .. netlink .. netmap .. netpfil common .. pf ioctl .. .. .. opencrypto .. pjdfstest chflags .. chmod .. chown .. ftruncate .. granular .. link .. mkdir .. mkfifo .. mknod .. open .. rename .. rmdir .. symlink .. truncate .. unlink .. utimensat .. .. posixshm .. sys .. vfs .. vm .. vmm .. .. usr.bin apply .. awk .. basename .. bmake archives fmt_44bsd .. fmt_44bsd_mod .. fmt_oldbsd .. .. basic t0 .. t1 .. t2 .. t3 .. .. execution ellipsis .. empty .. joberr .. plus .. .. shell builtin .. meta .. path .. path_select .. replace .. select .. .. suffixes basic .. src_wild1 .. src_wild2 .. .. syntax directive-t0 .. enl .. funny-targets .. semi .. .. sysmk t0 2 1 .. .. mk .. .. t1 2 1 .. .. mk .. .. t2 2 1 .. .. mk .. .. .. variables modifier_M .. modifier_t .. opt_V .. t0 .. .. .. bsdcat .. calendar .. cmp .. compress .. cpio .. col .. comm .. csplit .. cut .. dc .. diff .. diff3 .. dirname .. du .. file2c .. file .. find .. fold .. getconf .. gh-bc .. grep .. gzip .. head .. hexdump .. ident .. indent .. join .. jot .. lastcomm .. limits .. locale .. m4 .. mkimg .. mktemp .. ncal .. opensm .. patch .. pr .. printf .. procstat .. renice .. rs .. sdiff .. sed regress.multitest.out .. .. seq .. soelim .. sort .. split .. stat .. tail .. tar .. tr .. truncate .. + tsort + .. units .. uudecode .. uuencode .. unifdef .. uniq .. vmstat .. xargs .. xinstall .. xo .. yacc yacc .. .. .. usr.sbin chown .. daemon .. etcupdate .. extattr .. fstyp .. jail .. makefs .. mixer .. newsyslog .. nmtree .. praudit .. pw .. rpcbind .. sa .. .. .. # vim: set expandtab ts=4 sw=4: diff --git a/usr.bin/tsort/Makefile b/usr.bin/tsort/Makefile index b0d353e4d8f7..c0933dac2de1 100644 --- a/usr.bin/tsort/Makefile +++ b/usr.bin/tsort/Makefile @@ -1,6 +1,11 @@ # @(#)Makefile 8.1 (Berkeley) 6/9/93 # $FreeBSD$ +.include + PROG= tsort +HAS_TESTS= +SUBDIR.${MK_TESTS}= tests + .include diff --git a/usr.bin/tsort/tests/Makefile b/usr.bin/tsort/tests/Makefile new file mode 100644 index 000000000000..ab16c2842dd0 --- /dev/null +++ b/usr.bin/tsort/tests/Makefile @@ -0,0 +1,6 @@ +PACKAGE= tests + +ATF_TESTS_SH= tsort_test +BINDIR= ${TESTSDIR} + +.include diff --git a/usr.bin/tsort/tests/tsort_test.sh b/usr.bin/tsort/tests/tsort_test.sh new file mode 100755 index 000000000000..88d4efaf2b9f --- /dev/null +++ b/usr.bin/tsort/tests/tsort_test.sh @@ -0,0 +1,66 @@ +# +# Copyright (c) 2023 Klara, Inc. +# +# SPDX-License-Identifier: BSD-2-Clause +# + +atf_test_case basic +basic_head() +{ + atf_set "descr" "Sort a basic graph" +} +basic_body() +{ + cat >input <output <input <output< __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include /* * Topological sort. Input is a list of pairs of strings separated by * white space (spaces, tabs, and/or newlines); strings are written to * standard output in sorted order, one per line. * * usage: * tsort [-dlq] [inputfile] * If no input file is specified, standard input is read. * * Should be compatible with AT&T tsort HOWEVER the output is not identical * (i.e. for most graphs there is more than one sorted order, and this tsort * usually generates a different one then the AT&T tsort). Also, cycle * reporting seems to be more accurate in this version (the AT&T tsort * sometimes says a node is in a cycle when it isn't). * * Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90 */ #define NF_MARK 0x1 /* marker for cycle detection */ #define NF_ACYCLIC 0x2 /* this node is cycle free */ #define NF_NODEST 0x4 /* Unreachable */ typedef struct node_str NODE; struct node_str { NODE **n_prevp; /* pointer to previous node's n_next */ NODE *n_next; /* next node in graph */ NODE **n_arcs; /* array of arcs to other nodes */ int n_narcs; /* number of arcs in n_arcs[] */ int n_arcsize; /* size of n_arcs[] array */ int n_refcnt; /* # of arcs pointing to this node */ int n_flags; /* NF_* */ char n_name[1]; /* name of this node */ }; typedef struct _buf { char *b_buf; int b_bsize; } BUF; static DB *db; static NODE *graph, **cycle_buf, **longest_cycle; static int debug, longest, quiet; static void add_arc(char *, char *); static int find_cycle(NODE *, NODE *, int, int); static NODE *get_node(char *); static void *grow_buf(void *, size_t); static void remove_node(NODE *); static void clear_cycle(void); static void tsort(void); static void usage(void); int main(int argc, char *argv[]) { BUF *b; int c, n; FILE *fp; int bsize, ch, nused; BUF bufs[2]; fp = NULL; while ((ch = getopt(argc, argv, "dlq")) != -1) switch (ch) { case 'd': debug = 1; break; case 'l': longest = 1; break; case 'q': quiet = 1; break; case '?': default: usage(); } argc -= optind; argv += optind; switch (argc) { case 0: fp = stdin; break; case 1: if ((fp = fopen(*argv, "r")) == NULL) err(1, "%s", *argv); break; default: usage(); } for (b = bufs, n = 2; --n >= 0; b++) b->b_buf = grow_buf(NULL, b->b_bsize = 1024); /* parse input and build the graph */ for (n = 0, c = getc(fp);;) { while (c != EOF && isspace(c)) c = getc(fp); if (c == EOF) break; nused = 0; b = &bufs[n]; bsize = b->b_bsize; do { b->b_buf[nused++] = c; if (nused == bsize) b->b_buf = grow_buf(b->b_buf, bsize *= 2); c = getc(fp); } while (c != EOF && !isspace(c)); b->b_buf[nused] = '\0'; b->b_bsize = bsize; if (n) add_arc(bufs[0].b_buf, bufs[1].b_buf); n = !n; } (void)fclose(fp); if (n) errx(1, "odd data count"); /* do the sort */ tsort(); + if (ferror(stdout) != 0 || fflush(stdout) != 0) + err(1, "stdout"); exit(0); } /* double the size of oldbuf and return a pointer to the new buffer. */ static void * grow_buf(void *bp, size_t size) { if ((bp = realloc(bp, size)) == NULL) err(1, NULL); return (bp); } /* * add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in * the graph, then add them. */ static void add_arc(char *s1, char *s2) { NODE *n1; NODE *n2; int bsize, i; n1 = get_node(s1); if (!strcmp(s1, s2)) return; n2 = get_node(s2); /* * Check if this arc is already here. */ for (i = 0; i < n1->n_narcs; i++) if (n1->n_arcs[i] == n2) return; /* * Add it. */ if (n1->n_narcs == n1->n_arcsize) { if (!n1->n_arcsize) n1->n_arcsize = 10; bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2; n1->n_arcs = grow_buf(n1->n_arcs, bsize); n1->n_arcsize = bsize / sizeof(*n1->n_arcs); } n1->n_arcs[n1->n_narcs++] = n2; ++n2->n_refcnt; } /* Find a node in the graph (insert if not found) and return a pointer to it. */ static NODE * get_node(char *name) { DBT data, key; NODE *n; if (db == NULL && (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL) err(1, "db: %s", name); key.data = name; key.size = strlen(name) + 1; switch ((*db->get)(db, &key, &data, 0)) { case 0: - bcopy(data.data, &n, sizeof(n)); + memcpy(&n, data.data, sizeof(n)); return (n); case 1: break; default: case -1: err(1, "db: %s", name); } if ((n = malloc(sizeof(NODE) + key.size)) == NULL) err(1, NULL); n->n_narcs = 0; n->n_arcsize = 0; n->n_arcs = NULL; n->n_refcnt = 0; n->n_flags = 0; - bcopy(name, n->n_name, key.size); + memcpy(n->n_name, name, key.size); /* Add to linked list. */ if ((n->n_next = graph) != NULL) graph->n_prevp = &n->n_next; n->n_prevp = &graph; graph = n; /* Add to hash table. */ data.data = &n; data.size = sizeof(n); if ((*db->put)(db, &key, &data, 0)) err(1, "db: %s", name); return (n); } /* * Clear the NODEST flag from all nodes. */ static void clear_cycle(void) { NODE *n; for (n = graph; n != NULL; n = n->n_next) n->n_flags &= ~NF_NODEST; } /* do topological sort on graph */ static void tsort(void) { NODE *n, *next; int cnt, i; while (graph != NULL) { /* * Keep getting rid of simple cases until there are none left, * if there are any nodes still in the graph, then there is * a cycle in it. */ do { for (cnt = 0, n = graph; n != NULL; n = next) { next = n->n_next; if (n->n_refcnt == 0) { remove_node(n); ++cnt; } } } while (graph != NULL && cnt); if (graph == NULL) break; if (!cycle_buf) { /* * Allocate space for two cycle logs - one to be used * as scratch space, the other to save the longest * cycle. */ for (cnt = 0, n = graph; n != NULL; n = n->n_next) ++cnt; cycle_buf = malloc(sizeof(NODE *) * cnt); longest_cycle = malloc(sizeof(NODE *) * cnt); if (cycle_buf == NULL || longest_cycle == NULL) err(1, NULL); } for (n = graph; n != NULL; n = n->n_next) if (!(n->n_flags & NF_ACYCLIC)) { if ((cnt = find_cycle(n, n, 0, 0))) { if (!quiet) { warnx("cycle in data"); for (i = 0; i < cnt; i++) warnx("%s", longest_cycle[i]->n_name); } remove_node(n); clear_cycle(); break; } else { /* to avoid further checks */ n->n_flags |= NF_ACYCLIC; clear_cycle(); } } if (n == NULL) errx(1, "internal error -- could not find cycle"); } } /* print node and remove from graph (does not actually free node) */ static void remove_node(NODE *n) { NODE **np; int i; (void)printf("%s\n", n->n_name); for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++) --(*np)->n_refcnt; n->n_narcs = 0; *n->n_prevp = n->n_next; if (n->n_next) n->n_next->n_prevp = n->n_prevp; } /* look for the longest? cycle from node from to node to. */ static int find_cycle(NODE *from, NODE *to, int longest_len, int depth) { NODE **np; int i, len; /* * avoid infinite loops and ignore portions of the graph known * to be acyclic */ if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC)) return (0); from->n_flags |= NF_MARK; for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) { cycle_buf[depth] = *np; if (*np == to) { if (depth + 1 > longest_len) { longest_len = depth + 1; (void)memcpy((char *)longest_cycle, (char *)cycle_buf, longest_len * sizeof(NODE *)); } } else { if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST)) continue; len = find_cycle(*np, to, longest_len, depth + 1); if (debug) (void)printf("%*s %s->%s %d\n", depth, "", from->n_name, to->n_name, len); if (len == 0) (*np)->n_flags |= NF_NODEST; if (len > longest_len) longest_len = len; if (len > 0 && !longest) break; } } from->n_flags &= ~NF_MARK; return (longest_len); } static void usage(void) { (void)fprintf(stderr, "usage: tsort [-dlq] [file]\n"); exit(1); }