Add code to enforce the paralleism count (-j N) for the entire tree

of submakes spawned during processing.

We create a fifo and stuff one character into it for each job we are
allowed to run.  The name of the fifo is passed to child processes
in the MAKE_JOBS_FIFO environment variable.

A make which finds this variable on startup will open the fifo and
only spawn jobs when it managed to read a token from the fifo.
When the job completes a token is writen back to the fifo.

Slave make processes get one token for free: the one their parent
make got in order to run them.  This makes the make processes
themselves invisible in the process counts.

The net effect is that "make -j 12 -s buildworld" will start at
most 12 jobs at the same time, instead of as previously up to
65 jobs would get started.

4 files changed, 119 insertions, 31 deletions

diff --git a/usr.bin/make/job.c b/usr.bin/make/job.c
index 3979ecd..3ea0a5d 100644
--- a/usr.bin/make/job.c
+++ b/usr.bin/make/job.c
@@ -258,6 +258,9 @@ STATIC Lst	stoppedJobs;	/* Lst of Job structures describing
 				 * jobs that were stopped due to concurrency
 				 * limits or externally */
 
+STATIC int	fifoFd;		/* Fd of our job fifo */
+STATIC char	fifoName[] = "/tmp/make_fifo_XXXXXXXXX";
+STATIC int	fifoMaster;
 
 static sig_atomic_t interrupted;
 
@@ -1109,6 +1112,8 @@ JobExec(Job *job, char **argv)
 	Punt("Cannot fork");
     } else if (cpid == 0) {
 
+	if (fifoFd >= 0)
+	    close(fifoFd);
 	/*
 	 * Must duplicate the input stream down to the child's input and
 	 * reset it to the beginning (again). Since the stream was marked
@@ -1921,9 +1926,10 @@ Job_CatchChildren(Boolean block)
 	return;
     }
 
-    while ((pid = waitpid((pid_t) -1, &status,
-			  (block?0:WNOHANG)|WUNTRACED)) > 0)
-    {
+    for (;;) {
+	pid = waitpid((pid_t) -1, &status, (block?0:WNOHANG)|WUNTRACED);
+	if (pid <= 0)
+	    break;
 	DEBUGF(JOB, ("Process %d exited or stopped.\n", pid));
 
 	jnode = Lst_Find(jobs, (void *)&pid, JobCmpPid);
@@ -1945,8 +1951,17 @@ Job_CatchChildren(Boolean block)
 	    job = (Job *) Lst_Datum(jnode);
 	    (void) Lst_Remove(jobs, jnode);
 	    nJobs -= 1;
-	    DEBUGF(JOB, ("Job queue is no longer full.\n"));
-	    jobFull = FALSE;
+	    if (fifoFd >= 0 && maxJobs > 1) {
+		write(fifoFd, "+", 1);
+		maxJobs--;
+		if (nJobs >= maxJobs)
+		    jobFull = TRUE;
+		else
+		    jobFull = FALSE;
+	    } else {
+	        DEBUGF(JOB, ("Job queue is no longer full.\n"));
+	        jobFull = FALSE;
+	    }
 	}
 
 	JobFinish(job, &status);
@@ -1972,7 +1987,7 @@ Job_CatchChildren(Boolean block)
  * -----------------------------------------------------------------------
  */
 void
-Job_CatchOutput(void)
+Job_CatchOutput(int flag)
 {
     int           	  nfds;
 #ifdef USE_KQUEUE
@@ -2016,25 +2031,31 @@ Job_CatchOutput(void)
 	readfds = outputs;
 	timeout.tv_sec = SEL_SEC;
 	timeout.tv_usec = SEL_USEC;
+	if (flag && jobFull && fifoFd >= 0)
+	    FD_SET(fifoFd, &readfds);
 
-	if ((nfds = select(FD_SETSIZE, &readfds, (fd_set *) 0,
-			   (fd_set *) 0, &timeout)) <= 0) {
-	    if (interrupted)
+	nfds = select(FD_SETSIZE, &readfds, (fd_set *) 0,
+			   (fd_set *) 0, &timeout);
+	if (nfds <= 0) {
+	    if (interrupted) 
 		JobPassSig(interrupted);
 	    return;
-	} else {
-	    if (Lst_Open(jobs) == FAILURE) {
-		Punt("Cannot open job table");
-	    }
-	    while (nfds && (ln = Lst_Next(jobs)) != NULL) {
-		job = (Job *) Lst_Datum(ln);
-		if (FD_ISSET(job->inPipe, &readfds)) {
-		    JobDoOutput(job, FALSE);
-		    nfds -= 1;
-		}
+	}
+	if (fifoFd >= 0 && FD_ISSET(fifoFd, &readfds)) {
+	    if (--nfds <= 0)
+		return;
+	}
+	if (Lst_Open(jobs) == FAILURE) {
+	    Punt("Cannot open job table");
+	}
+	while (nfds && (ln = Lst_Next(jobs)) != NULL) {
+	    job = (Job *) Lst_Datum(ln);
+	    if (FD_ISSET(job->inPipe, &readfds)) {
+		JobDoOutput(job, FALSE);
+		nfds -= 1;
 	    }
-	    Lst_Close(jobs);
 	}
+	Lst_Close(jobs);
 #endif /* !USE_KQUEUE */
     }
 }
@@ -2091,20 +2112,67 @@ void
 Job_Init(int maxproc)
 {
     GNode         *begin;     /* node for commands to do at the very start */
+    const char	  *env;
     struct sigaction sa;
 
+    fifoFd =	  -1;
     jobs =  	  Lst_Init(FALSE);
     stoppedJobs = Lst_Init(FALSE);
-    maxJobs = 	  maxproc;
+    env = getenv("MAKE_JOBS_FIFO");
+
+    if (env == NULL && maxproc > 1) {
+	/*
+	 * We did not find the environment variable so we are the leader.
+	 * Create the fifo, open it, write one char per allowed job into
+	 * the pipe.
+	 */
+	mktemp(fifoName);
+        if (!mkfifo(fifoName, 0600)) {
+	    fifoFd = open(fifoName, O_RDWR | O_NONBLOCK, 0);
+	    if (fifoFd >= 0) {
+		fifoMaster = 1;
+		fcntl(fifoFd, F_SETFL, O_NONBLOCK);
+	        env = fifoName;
+	        setenv("MAKE_JOBS_FIFO", env, 1);
+	        while (maxproc-- > 0) {
+		    write(fifoFd, "+", 1);
+		}
+		/*The master make does not get a magic token */
+                jobFull = TRUE;
+		maxJobs = 0;
+	    } else {
+	        unlink(fifoName);
+	        env = NULL;
+            }
+	}
+    } else if (env != NULL) {
+	/*
+	 * We had the environment variable so we are a slave.
+	 * Open fifo and give ourselves a magic token which represents
+	 * the token our parent make has grabbed to start his make process.
+	 * Otherwise the sub-makes would gobble up tokens and the proper
+	 * number of tokens to specify to -j would depend on the depth of		 * the tree and the order of execution.
+	 */
+	fifoFd = open(env, O_RDWR, 0);
+	if (fifoFd >= 0) {
+	    fcntl(fifoFd, F_SETFL, O_NONBLOCK);
+	    maxJobs = 1;
+	    jobFull = FALSE;
+	}
+    }
+    if (fifoFd <= 0) {
+	maxJobs = maxproc;
+        jobFull = FALSE;
+    } else {
+    }
     nJobs = 	  0;
-    jobFull = 	  FALSE;
 
     aborting = 	  0;
     errors = 	  0;
 
     lastNode =	  NULL;
 
-    if (maxJobs == 1 || beVerbose == 0) {
+    if ((maxJobs == 1 && fifoFd < 0) || beVerbose == 0) {
 	/*
 	 * If only one job can run at a time, there's no need for a banner,
 	 * no is there?
@@ -2175,7 +2243,7 @@ Job_Init(int maxproc)
     if (begin != NULL) {
 	JobStart(begin, JOB_SPECIAL, (Job *)0);
 	while (nJobs) {
-	    Job_CatchOutput();
+	    Job_CatchOutput(0);
 	    Job_CatchChildren(!usePipes);
 	}
     }
@@ -2199,7 +2267,19 @@ Job_Init(int maxproc)
 Boolean
 Job_Full(void)
 {
-    return(aborting || jobFull);
+    char c;
+    int i;
+
+    if (aborting)
+	return(aborting);
+    if (fifoFd >= 0 && jobFull) {
+	i = read(fifoFd, &c, 1);
+	if (i > 0) {
+	    maxJobs++;
+	    jobFull = FALSE;
+	}
+    }
+    return(jobFull);
 }
 
 /*-
@@ -2499,7 +2579,7 @@ JobInterrupt(int runINTERRUPT, int signo)
 
 	    JobStart(interrupt, JOB_IGNDOTS, (Job *)0);
 	    while (nJobs) {
-		Job_CatchOutput();
+		Job_CatchOutput(0);
 		Job_CatchChildren(!usePipes);
 	    }
 	}
@@ -2526,11 +2606,17 @@ Job_Finish(void)
 	    JobStart(postCommands, JOB_SPECIAL | JOB_IGNDOTS, NULL);
 
 	    while (nJobs) {
-		Job_CatchOutput();
+		Job_CatchOutput(0);
 		Job_CatchChildren(!usePipes);
 	    }
 	}
     }
+    if (fifoFd >= 0) {
+	close(fifoFd);
+	fifoFd = -1;
+	if (fifoMaster)
+	    unlink(fifoName);
+    }
     return(errors);
 }
 
@@ -2553,7 +2639,7 @@ Job_Wait(void)
 {
     aborting = ABORT_WAIT;
     while (nJobs != 0) {
-	Job_CatchOutput();
+	Job_CatchOutput(0);
 	Job_CatchChildren(!usePipes);
     }
     aborting = 0;
diff --git a/usr.bin/make/job.h b/usr.bin/make/job.h
index 09fe8fe..25aa511 100644
--- a/usr.bin/make/job.h
+++ b/usr.bin/make/job.h
@@ -209,7 +209,7 @@ void Shell_Init(void);
 void Job_Touch(GNode *, Boolean);
 Boolean Job_CheckCommands(GNode *, void (*abortProc)(const char *, ...));
 void Job_CatchChildren(Boolean);
-void Job_CatchOutput(void);
+void Job_CatchOutput(int flag);
 void Job_Make(GNode *);
 void Job_Init(int);
 Boolean Job_Full(void);
diff --git a/usr.bin/make/main.c b/usr.bin/make/main.c
index 8a33fe9..d5c9694 100644
--- a/usr.bin/make/main.c
+++ b/usr.bin/make/main.c
@@ -678,6 +678,8 @@ main(int argc, char **argv)
 	Var_Set(".CURDIR", curdir, VAR_GLOBAL);
 	Var_Set(".OBJDIR", objdir, VAR_GLOBAL);
 
+	if (getenv("MAKE_JOBS_FIFO") != NULL)
+		forceJobs = TRUE;
 	/*
 	 * Be compatible if user did not specify -j and did not explicitly
 	 * turned compatibility on
diff --git a/usr.bin/make/make.c b/usr.bin/make/make.c
index 762b65a..4f85b68 100644
--- a/usr.bin/make/make.c
+++ b/usr.bin/make/make.c
@@ -637,7 +637,7 @@ MakeStartJobs (void)
 {
     GNode	*gn;
 
-    while (!Job_Full() && !Lst_IsEmpty (toBeMade)) {
+    while (!Lst_IsEmpty (toBeMade) && !Job_Full()) {
 	gn = (GNode *) Lst_DeQueue (toBeMade);
 	DEBUGF(MAKE, ("Examining %s...", gn->name));
 	/*
@@ -840,7 +840,7 @@ Make_Run (Lst targs)
      * keepgoing flag was given.
      */
     while (!Job_Empty ()) {
-	Job_CatchOutput ();
+	Job_CatchOutput (!Lst_IsEmpty (toBeMade));
 	Job_CatchChildren (!usePipes);
 	(void)MakeStartJobs();
     }