Re: [dev] Make cleanup

From: Markus Wichmann <nullplan_AT_gmx.net>
Date: Sun, 30 Dec 2018 09:53:50 +0100

On Sat, Dec 29, 2018 at 08:32:13PM -0500, stephen Turner wrote:
> If one was going to rewrite a cleaner make what would be the recommended approach?
> [...]
> I am not skilled enough to start from scratch [...]
>

Maybe start with that. Make is a pretty simple algorithm: You build a
dependency graph (which is a directed acyclic graph), then you find the
target you are supposed to make (i.e. the first target or the command
line arguments), rebuild its dependencies, then rebuild the target
itself.

So you need a way to represent an acyclic directed graph where each node
has a name and a variable number of edges. You need to be able to check
if it is indeed acyclic.

Next is to handle expansion. Most make targets contain variables you
need to replace. Then you can just hand the resulting line to system().
I am ordinarily no great fan of system(), but for make it is probably
appropriate.

And finally, you should probably add parallelism. There are a few ways
to deal with it. I do have an idea, though: Each node in the graph gets
a thread ID, a mutex, and a condition. A worker thread will then grab
the mutex of its own node, iterate over its dependencies, grabbing the
mutex of the dependent node, checking if the thread of the dependent
node was spawned, spawn it if not, then wait on the condition variable
(then release the mutex, obviously). Then, once all the dependencies
are done, run the command associated with your own node, broadcast on
the condition variable, release the mutex and exit. If all the threads
are detached, there will not be a need for a pthread_join() (else you'd
need an ownership model).

Since the graph is acyclic, the dining philosophers problem will not
occur. And I see no other way for a deadlock.

Anyway, once these are all done, getting your make to be standards
compliant should be simple matter of adding a bit of fluff around
everything (for instance, the Makefile and all included files are
usually implicitly remade before everything else, if they are out of
date. And even if you have n+1 threads running, you need to limit the
number of subprocesses to whatever the argument to "-j" was, which you
can do with a semaphore. And then there's all the stuff GNU make added
to the expansion mechanism.)

Actually, now you got me started, gonna try to rig up at least a POC.


>
> I see in a slightly older 2012 release of the code entries for windows
> 32 and amiga. I’m questioning why!
>

Are you talking about GNU make? Because I can tell you from experience
that the GNU utilities are not a great learning ressource. You will
likely miss the forest for the trees. Or miss the interesting parts for
all the GNU fluff around it.

> Would it be worth while to strip make of these items and then attempt
> to clean the code section by section? Diff a legacy and perhaps gnu
> exclusive version against a newer release, or perhaps another
> approach?
>

Nah, that would be like trying to polish a turd at this point.

> In the past I have learned coding by jumping into an existing item and
> rewriting, not sure if this is a task I will take on but the thought
> has crossed my mind.
>

You should probably try to learn a bit about the computer science behind
these projects. Granted, there isn't a whole lot of CS that goes into
cp, but for some of the more interesting programs, like make or diff,
the coding can obscure the actual algorithm that makes it work. diff
isn't about opening and reading files, even though that is part of the
algorithm. :-) (The same way gingerbread isn't about the flour.)

> Thanks,
> Stephen

Ciao,
Markus
Received on Sun Dec 30 2018 - 09:53:50 CET