Add a -d option to ps to display descendant info with the output.

This is similar to linux's -H (or -f) switch.

MFC after:	3 weeks

4 files changed, 167 insertions, 15 deletions

diff --git a/bin/ps/print.c b/bin/ps/print.c
index 3ae37fc..1bfce04 100644
--- a/bin/ps/print.c
+++ b/bin/ps/print.c
@@ -130,9 +130,11 @@ command(KINFO *k, VARENT *ve)
 	if (cflag) {
 		/* If it is the last field, then don't pad */
 		if (STAILQ_NEXT(ve, next_ve) == NULL) {
+			if (k->ki_d.prefix)
+				(void)printf("%s", k->ki_d.prefix);
 			(void)printf("%s", k->ki_p->ki_comm);
 			if (showthreads && k->ki_p->ki_numthreads > 1)
-				printf("/%s", k->ki_p->ki_ocomm);
+				(void)printf("/%s", k->ki_p->ki_ocomm);
 		} else
 			(void)printf("%-*s", v->width, k->ki_p->ki_comm);
 		return;
@@ -140,16 +142,22 @@ command(KINFO *k, VARENT *ve)
 	if ((vis_args = malloc(strlen(k->ki_args) * 4 + 1)) == NULL)
 		errx(1, "malloc failed");
 	strvis(vis_args, k->ki_args, VIS_TAB | VIS_NL | VIS_NOSLASH);
-	if (k->ki_env) {
-		if ((vis_env = malloc(strlen(k->ki_env) * 4 + 1)) == NULL)
-			errx(1, "malloc failed");
-		strvis(vis_env, k->ki_env, VIS_TAB | VIS_NL | VIS_NOSLASH);
-	} else
-		vis_env = NULL;
 
 	if (STAILQ_NEXT(ve, next_ve) == NULL) {
 		/* last field */
+
+		if (k->ki_env) {
+			if ((vis_env = malloc(strlen(k->ki_env) * 4 + 1))
+			    == NULL)
+				errx(1, "malloc failed");
+			strvis(vis_env, k->ki_env,
+			    VIS_TAB | VIS_NL | VIS_NOSLASH);
+		} else
+			vis_env = NULL;
+
 		if (termwidth == UNLIMITED) {
+			if (k->ki_d.prefix)
+				(void)printf("%s", k->ki_d.prefix);
 			if (vis_env)
 				(void)printf("%s ", vis_env);
 			(void)printf("%s", vis_args);
@@ -157,6 +165,9 @@ command(KINFO *k, VARENT *ve)
 			left = termwidth - (totwidth - v->width);
 			if (left < 1) /* already wrapped, just use std width */
 				left = v->width;
+			if ((cp = k->ki_d.prefix) != NULL)
+				while (--left >= 0 && *cp)
+					(void)putchar(*cp++);
 			if ((cp = vis_env) != NULL) {
 				while (--left >= 0 && *cp)
 					(void)putchar(*cp++);
@@ -166,12 +177,12 @@ command(KINFO *k, VARENT *ve)
 			for (cp = vis_args; --left >= 0 && *cp != '\0';)
 				(void)putchar(*cp++);
 		}
+		if (vis_env != NULL)
+			free(vis_env);
 	} else
-		/* XXX env? */
+		/* ki_d.prefix & ki_env aren't shown for interim fields */
 		(void)printf("%-*.*s", v->width, v->width, vis_args);
 	free(vis_args);
-	if (vis_env != NULL)
-		free(vis_env);
 }
 
 void
@@ -182,6 +193,8 @@ ucomm(KINFO *k, VARENT *ve)
 
 	v = ve->var;
 	if (STAILQ_NEXT(ve, next_ve) == NULL) {	/* last field, don't pad */
+		if (k->ki_d.prefix)
+			(void)printf("%s", k->ki_d.prefix);
 		(void)printf("%s", k->ki_p->ki_comm);
 		if (showthreads && k->ki_p->ki_numthreads > 1)
 			printf("/%s", k->ki_p->ki_ocomm);
diff --git a/bin/ps/ps.1 b/bin/ps/ps.1
index 01e654e..ebd70d0 100644
--- a/bin/ps/ps.1
+++ b/bin/ps/ps.1
@@ -29,7 +29,7 @@
 .\"     @(#)ps.1	8.3 (Berkeley) 4/18/94
 .\" $FreeBSD$
 .\"
-.Dd August 21, 2006
+.Dd May 16, 2009
 .Dt PS 1
 .Os
 .Sh NAME
@@ -37,7 +37,7 @@
 .Nd process status
 .Sh SYNOPSIS
 .Nm
-.Op Fl aCcefHhjlmrSTuvwXxZ
+.Op Fl aCcdefHhjlmrSTuvwXxZ
 .Op Fl O Ar fmt | Fl o Ar fmt
 .Op Fl G Ar gid Ns Op , Ns Ar gid Ns Ar ...
 .Op Fl M Ar core
@@ -122,6 +122,15 @@ CPU calculation that ignores
 .Dq resident
 time (this normally has
 no effect).
+.It Fl d
+Arrange processes into descendancy order and prefix each command with
+indentation text showing sibling and parent/child relationships.
+If either of the
+.Fl m
+and
+.Fl r
+options are also used, they control how sibling processes are sorted
+relative to eachother.
 .It Fl e
 Display the environment as well.
 .It Fl f
diff --git a/bin/ps/ps.c b/bin/ps/ps.c
index a3a1986..99c16d7 100644
--- a/bin/ps/ps.c
+++ b/bin/ps/ps.c
@@ -138,6 +138,7 @@ static int	 addelem_pid(struct listinfo *, const char *);
 static int	 addelem_tty(struct listinfo *, const char *);
 static int	 addelem_uid(struct listinfo *, const char *);
 static void	 add_list(struct listinfo *, const char *);
+static void	 descendant_sort(KINFO *, int);
 static void	 dynsizevars(KINFO *);
 static void	*expand_list(struct listinfo *);
 static const char *
@@ -163,7 +164,7 @@ static char vfmt[] = "pid,state,time,sl,re,pagein,vsz,rss,lim,tsiz,"
 			"%cpu,%mem,command";
 static char Zfmt[] = "label";
 
-#define	PS_ARGS	"AaCce" OPT_LAZY_f "G:gHhjLlM:mN:O:o:p:rSTt:U:uvwXxZ"
+#define	PS_ARGS	"AaCcde" OPT_LAZY_f "G:gHhjLlM:mN:O:o:p:rSTt:U:uvwXxZ"
 
 int
 main(int argc, char *argv[])
@@ -177,7 +178,7 @@ main(int argc, char *argv[])
 	const char *nlistf, *memf;
 	char *cols;
 	int all, ch, elem, flag, _fmt, i, lineno;
-	int nentries, nkept, nselectors;
+	int descendancy, nentries, nkept, nselectors;
 	int prtheader, wflag, what, xkeep, xkeep_implied;
 	char errbuf[_POSIX2_LINE_MAX];
 
@@ -201,7 +202,7 @@ main(int argc, char *argv[])
 	if (argc > 1)
 		argv[1] = kludge_oldps_options(PS_ARGS, argv[1], argv[2]);
 
-	all = _fmt = nselectors = optfatal = 0;
+	all = descendancy = _fmt = nselectors = optfatal = 0;
 	prtheader = showthreads = wflag = xkeep_implied = 0;
 	xkeep = -1;			/* Neither -x nor -X. */
 	init_list(&gidlist, addelem_gid, sizeof(gid_t), "group");
@@ -233,6 +234,9 @@ main(int argc, char *argv[])
 		case 'c':
 			cflag = 1;
 			break;
+		case 'd':
+			descendancy = 1;
+			break;
 		case 'e':			/* XXX set ufmt */
 			needenv = 1;
 			break;
@@ -575,6 +579,8 @@ main(int argc, char *argv[])
 		keepit:
 			next_KINFO = &kinfo[nkept];
 			next_KINFO->ki_p = kp;
+			next_KINFO->ki_d.level = 0;
+			next_KINFO->ki_d.prefix = NULL;
 			next_KINFO->ki_pcpu = getpcpu(next_KINFO);
 			if (sortby == SORTMEM)
 				next_KINFO->ki_memsize = kp->ki_tsize +
@@ -599,6 +605,13 @@ main(int argc, char *argv[])
 	 * sort proc list
 	 */
 	qsort(kinfo, nkept, sizeof(KINFO), pscomp);
+
+	/*
+	 * We want things in descendant order
+	 */
+	if (descendancy)
+		descendant_sort(kinfo, nkept);
+
 	/*
 	 * For each process, call each variable output function.
 	 */
@@ -622,6 +635,9 @@ main(int argc, char *argv[])
 	free_list(&sesslist);
 	free_list(&ttylist);
 	free_list(&uidlist);
+	for (i = 0; i < nkept; i++)
+		free(kinfo[i].ki_d.prefix);
+	free(kinfo);
 
 	exit(eval);
 }
@@ -890,6 +906,116 @@ add_list(struct listinfo *inf, const char *argp)
 	}
 }
 
+static void
+descendant_sort(KINFO *ki, int items)
+{
+	int dst, lvl, maxlvl, n, ndst, nsrc, siblings, src;
+	unsigned char *path;
+	KINFO kn;
+
+	/*
+	 * First, sort the entries by descendancy, tracking the descendancy
+	 * depth in the ki_d.level field.
+	 */
+	src = 0;
+	maxlvl = 0;
+	while (src < items) {
+		if (ki[src].ki_d.level) {
+			src++;
+			continue;
+		}
+		for (nsrc = 1; src + nsrc < items; nsrc++)
+			if (!ki[src + nsrc].ki_d.level)
+				break;
+
+		for (dst = 0; dst < items; dst++) {
+			if (ki[dst].ki_p->ki_pid == ki[src].ki_p->ki_pid)
+				continue;
+			if (ki[dst].ki_p->ki_pid == ki[src].ki_p->ki_ppid)
+				break;
+		}
+
+		if (dst == items) {
+			src += nsrc;
+			continue;
+		}
+
+		for (ndst = 1; dst + ndst < items; ndst++)
+			if (ki[dst + ndst].ki_d.level <= ki[dst].ki_d.level)
+				break;
+
+		for (n = src; n < src + nsrc; n++) {
+			ki[n].ki_d.level += ki[dst].ki_d.level + 1;
+			if (maxlvl < ki[n].ki_d.level)
+				maxlvl = ki[n].ki_d.level;
+		}
+
+		while (nsrc) {
+			if (src < dst) {
+				kn = ki[src];
+				memmove(ki + src, ki + src + 1,
+				    (dst - src + ndst - 1) * sizeof *ki);
+				ki[dst + ndst - 1] = kn;
+				nsrc--;
+				dst--;
+				ndst++;
+			} else if (src != dst + ndst) {
+				kn = ki[src];
+				memmove(ki + dst + ndst + 1, ki + dst + ndst,
+				    (src - dst - ndst) * sizeof *ki);
+				ki[dst + ndst] = kn;
+				ndst++;
+				nsrc--;
+				src++;
+			} else {
+				ndst += nsrc;
+				src += nsrc;
+				nsrc = 0;
+			}
+		}
+	}
+
+	/*
+	 * Now populate ki_d.prefix (instead of ki_d.level) with the command
+	 * prefix used to show descendancies.
+	 */
+	path = malloc((maxlvl + 7) / 8);
+	memset(path, '\0', (maxlvl + 7) / 8);
+	for (src = 0; src < items; src++) {
+		if ((lvl = ki[src].ki_d.level) == 0) {
+			ki[src].ki_d.prefix = NULL;
+			continue;
+		}
+		if ((ki[src].ki_d.prefix = malloc(lvl * 2 + 1)) == NULL)
+			errx(1, "malloc failed");
+		for (n = 0; n < lvl - 2; n++) {
+			ki[src].ki_d.prefix[n * 2] =
+			    path[n / 8] & 1 << (n % 8) ? '|' : ' ';
+			ki[src].ki_d.prefix[n * 2 + 1] = ' ';
+				
+		}
+		if (n == lvl - 2) {
+			/* Have I any more siblings? */
+			for (siblings = 0, dst = src + 1; dst < items; dst++) {
+				if (ki[dst].ki_d.level > lvl)
+					continue;
+				if (ki[dst].ki_d.level == lvl)
+					siblings = 1;
+				break;
+			}
+			if (siblings)
+				path[n / 8] |= 1 << (n % 8);
+			else
+				path[n / 8] &= ~(1 << (n % 8));
+			ki[src].ki_d.prefix[n * 2] = siblings ? '|' : '`';
+			ki[src].ki_d.prefix[n * 2 + 1] = '-';
+			n++;
+		}
+		strcpy(ki[src].ki_d.prefix + n * 2, "- ");
+	}
+	free(path);
+}
+
 static void *
 expand_list(struct listinfo *inf)
 {
diff --git a/bin/ps/ps.h b/bin/ps/ps.h
index 03adc0a..ddaebed 100644
--- a/bin/ps/ps.h
+++ b/bin/ps/ps.h
@@ -42,6 +42,10 @@ typedef struct kinfo {
 	int ki_valid;		/* 1 => uarea stuff valid */
 	double	 ki_pcpu;	/* calculated in main() */
 	segsz_t	 ki_memsize;	/* calculated in main() */
+	union {
+		int level;	/* used in decendant_sort() */
+		char *prefix;	/* calculated in decendant_sort() */
+	} ki_d;
 } KINFO;
 
 /* Variables. */