1 .HTML "Maintaining Files on Plan 9 with Mk
3 Maintaining Files on Plan 9 with Mk
6 andrew@research.att.com
8 bobf@plan9.bell-labs.com
13 for describing and maintaining dependencies between
18 but provides several extensions.
20 flexible rule specifications, implied
21 dependency derivation, and parallel
22 execution of maintenance actions are
23 well-suited to the Plan 9 environment.
24 Almost all Plan 9 maintenance procedures
31 This document describes how
33 a program functionally similar to
36 is used to maintain dependencies between
39 provides several extensions to the
40 capabilities of its predecessor that work
41 well in Plan 9's distributed, multi-architecture
43 exploits the power of multiprocessors by executing
44 maintenance actions in parallel and interacts with
45 the Plan 9 command interpreter
47 to provide a powerful set of maintenance tools.
48 It accepts pattern-based dependency specifications
49 that are not limited to describing
50 rules for program construction.
51 The result is a tool that is flexible enough to
52 perform many maintenance tasks including
54 hardware design, and document production.
56 This document begins by discussing
57 the syntax of the control file,
58 the pattern matching capabilities, and
59 the special rules for maintaining archives.
60 A brief description of
62 algorithm for deriving dependencies
63 is followed by a discussion
64 of the conventions used to resolve ambiguous
65 specifications. The final sections
66 describe parallel execution
69 An earlier paper [Hume87]
70 provides a detailed discussion of
72 design and an appendix summarizes
73 the differences between
81 reads a file describing relationships among files
82 and executes commands to bring the files up to date.
83 The specification file, called a
85 contains three types of statements:
86 assignments, includes, and rules.
87 Assignment and include statements are similar
89 Rules specify dependencies between a
93 When the target and prerequisites are files, their
94 modification times determine if they
95 are out of date. Rules often contain a
99 script that produces the target from
104 produces an executable
105 from a C source file:
111 The first line assigns the name of the portable ANSI/POSIX compiler
116 subsequent references of the form
118 select this compiler.
119 The only rule specifies a dependence between the target file
121 and the prerequisite file
123 If the target does not exist or if the
124 prerequisite has been modified more recently than
131 is compiled and loaded to produce
134 The native Plan 9 environment
135 requires executables for
136 all architectures, not only the current one.
137 The Plan 9 version of the same
144 $LD $LDFLAGS -o f1 f1.$O
148 The first line is an include statement
149 that replaces itself with the contents of the file
150 .CW /$objtype/mkfile .
153 is inherited from the environment and
154 contains the name of the target architecture.
157 for that architecture defines architecture-specific variables:
161 are the names of the compiler and loader,
163 is the code character of the architecture.
164 The rules compile the source file into an object
165 file and invoke the loader to produce
169 from the command line as follows
173 vl $LDFLAGS -o f1 f1.k
178 executable of program
180 regardless of the current architecture type.
184 to build two programs:
192 $LD $LDFLAGS -o f1 f1.$O
196 $LD $LDFLAGS -o f2 f2.$O
205 builds both programs.
206 The attribute identifies
208 as a dummy target that is
209 not related to a file of the same name;
210 its precise effect is explained later.
211 This example describes cascading dependencies:
212 the first target depends on another which depends on a third and
214 Here, individual rules build each
215 program; later we'll see how to do this with a
218 Variables and the environment
221 does not distinguish between its
222 internal variables and
224 variables in the environment.
227 starts, it imports each environment variable into a
229 variable of the same name. Before executing a recipe,
231 exports all variables, including those
232 inherited from the environment,
233 to the environment in which
237 There are several ways for a
238 variable to take a value.
239 It can be set with an assignment statement,
240 inherited from the environment, or specified
243 also maintains several special internal variables
244 that are described in
246 Assignments have the following decreasing order of precedence:
249 1) Command line assignment
251 2) Assignment statement
253 3) Imported from the environment
255 4) Implicitly set by \f(CWmk\fP
258 For example, a command line assignment overrides
259 a value imported from the environment.
261 All variable values are strings. They can be
262 used for pattern matching and
263 comparison but not for arithmetic.
266 is a string containing several values separated by
267 white space. Each member is
268 handled individually during pattern matching,
269 target selection, and prerequisite evaluation.
273 is a list produced by
274 transforming the members of an existing list.
275 The transform applies a pattern to each member,
276 replacing each matched string with a new string,
277 much as in the substitute command in
290 matches a member beginning with the string
292 and ending with the string
294 with any string in between;
295 it behaves like the regular expression
300 matches this pattern,
308 and the matched string replaces itself.
315 may be the empty string. In effect, a namelist is
316 generated by applying the
320 s/\fIA\fP(.*)\fIB\fP/\fIC\fP\e1\fID\fP/
322 to each member of a variable list.
324 Namelists are useful for generating
325 a list based on a predictable transformation.
331 assigns the list \f(CW(a.v b.v c.v)\fP to
333 A namelist may be used anywhere a variable is allowed
336 Command output is assigned to a variable
343 The command executes in an environment populated
344 with previously assigned variables, including those
347 execution environment.
349 be arbitrarily complex; for example,
351 TARG=`{ls -d *.[cy] | sed 's/..$//'}
353 assigns a list of the C and yacc source files in the current
354 directory, stripped of their suffix, to the variable
357 The include statement
359 The include statement
360 replaces itself with the contents of a file.
361 It is functionally similar to the C
363 statement but uses a different syntax:
367 The contents of the file are evaluated
369 An include statement may be used anywhere except
375 has no built-in rules. Instead,
376 the include statement allows generic rules
377 to be imported from a prototype
381 use this approach [Flan95].
385 A rule has four elements: targets,
386 prerequisites, attributes, and a recipe.
389 \fItargets\fP:\fIattributes\fP:\fIprerequisites\fP
392 The first line, containing the
393 targets, attributes, and prerequisites is
397 must begin at the left margin.
398 The recipe contains zero or more lines,
399 each of which begins with white space.
400 One or more targets must be specified but the
401 attributes, prerequisites, and recipe are optional.
403 a dependency between the target(s) and its prerequisite(s),
404 the recipe brings the target(s)
405 up to date with the prerequisite(s) and
408 evaluation of the dependency.
410 Normally the target is a file that depends
411 on one or more prerequisite files.
413 compares the modification times of each target
414 and each prerequisite; a target is considered out of date
415 when it does not exist or when a prerequisite has been modified
417 When a target is out of date,
420 recipe to bring it up to date.
421 When the recipe completes,
422 the modification time of the target is checked and
423 used in later dependency evaluations.
424 If the recipe does not update the target,
425 evaluation continues with the out of date target.
427 A prerequisite of one rule
428 may be the target of another. When
429 this happens, the rules cascade
430 to define a multi-step procedure.
432 an executable target depends on prerequisite
433 object files, each of which is a target
434 in a rule with a C source file as the prerequisite.
436 follows a chain of dependencies until it encounters
437 a prerequisite that is not a target of another rule
438 or it finds a target that
439 is up to date. It then
440 executes the recipes in reverse order to produce
443 The rule header is evaluated when the rule is read.
444 Variables are replaced by their values, namelists are
446 commands are replaced by their
449 Most attributes modify
451 evaluation of a rule.
452 An attribute is usually a single letter but some
453 are more complicated.
454 This paper only discusses commonly used attributes;
461 attribute identifies a
464 that is, a target that is not a file.
470 removes executables and compiler intermediate files.
471 The target is virtual because it does not refer to a file named
473 Without the attribute, the recipe would not be
474 executed if a file named
480 silences the printing of a recipe before
482 It is useful when the output of a recipe is
483 similar to the recipe:
486 echo 'No default target; use mk all or mk install'
491 script. It is optional but when it is
492 missing, the rule is handled specially, as described later.
496 executes recipes without interpretation.
498 stripping the first white space character from each line
499 it passes the entire recipe to
504 does not interpret a recipe,
505 escape conventions are exactly those of
511 commands can be embedded exactly as they would
512 be entered from the command line.
520 to stop if any command
521 in the recipe exits with a non-zero status; the
523 attribute overrides this behavior and allows
525 to continue executing in the face of errors.
526 Before a recipe is executed, variables are exported
527 to the environment where they are available to
529 Commands in the recipe may not read from
530 standard input because
534 References to a variable can yield different
535 values depending on the location of the
539 resolves variable references
540 in assignment statements and rule headers
541 when the statement is read. Variable references
542 in recipes are evaluated by
544 when the recipe is executed; this
545 happens after the entire
547 has been read. The value of a variable in a recipe
548 is the last value assigned in the file. For example,
558 A variable assignment in a recipe
559 does not affect the value of the variable in the
564 does not import values from
565 the environment when a recipe completes;
566 one recipe cannot pass a value through
567 the environment to another recipe.
568 Second, no recipe is executed until
570 has completed its evaluation, so even if a variable
572 it would not affect the dependency evaluation.
578 is a rule based on a pattern.
579 The pattern selects a class of target(s) and
580 identifies related prerequisites.
582 metarules may select targets and prerequisites
583 based on any criterion that can be described by a pattern, not just
584 the suffix transformations associated with program
587 Metarule patterns are either
589 or regular expressions conforming to the
592 The intrinsic patterns are shorthand
593 for common regular expressions.
594 The intrinsic pattern
596 matches one or more of anything; it is equivalent to
597 the regular expression
599 The other intrinsic pattern,
601 matches one or more of any characters except \f(CW`/'\fP
603 It matches a portion of a path and is
604 equivalent to the regular expression
606 An intrinsic pattern in a prerequisite references
607 the string matched by the same intrinsic pattern in the target.
608 For example, the rule
612 says that a file ending in
614 depends on a file of the same name with a
624 The string matched by an intrinsic pattern in the target
625 is supplied to the recipe in the variable
632 creates an object file for the target architecture from
633 a similarly named C source file. If several object
634 files are out of date, the rule is applied repeatedly and
636 refers to each file in turn.
637 Since there is only one
639 variable, there can only be one
648 Metarules simplify the
650 for building programs
662 $LD -o $target $prereq
670 is a list of code characters for all architectures.)
671 Here, metarules specify
672 compile and load steps for all C source files.
673 The loader rule relies on two internal variables
676 during evaluation of the rule:
678 is the name of the target(s) and
680 the name of all prerequisite(s).
683 to be easily extended; a new program
684 is supported by adding its name to the third line.
686 A regular expression metarule must have an
689 Prerequisites may reference matching substrings in
690 the target using the form
694 is a digit from 1 to 9 specifying the
696 parenthesized sub-expression. In a recipe,
698 is the equivalent reference.
699 For example, a compile rule could be
700 specified using regular expressions:
709 refer to the name of the target object file without the
712 associated with an intrinsic pattern is undefined
713 in a regular expression metarule.
718 provides a special mechanism for maintaining an archive.
719 An archive member is referenced using the form
720 .CW \fIlib\fP(\fIfile\fP)
723 is the name of the archive and
725 is the name of the member. Two rules define the
726 dependency between an object file and its membership
733 The first rule establishes a dependency between the
734 archive member and the object file.
737 detects an error when a target does not exist and the rule
738 contains no recipe; the
740 attribute overrides this behavior because the subsequent rule
743 rule establishes the dependency between the member and
744 the archive; its recipe inserts the member
746 This two-step specification allows the modification time
748 to represent the state of its members. Other rules
749 can then specify the archive as a prerequisite instead of
752 A metarule generalizes library maintenance:
755 OBJS=etoa.$O atoe.$O ebcdic.$O
758 $LIB: ${OBJS:%=$LIB(%)}
761 The namelist prerequisite of the
763 target generates archive member names for each object file name;
768 This formulation always updates all members.
769 This is acceptable for a small archive, but may
770 be slow for a big one.
773 $LIB: ${OBJS:%=$LIB(%)}
774 ar rv $LIB `{membername $newprereq}
776 only updates out of date object files.
777 The internal variable
779 contains the names of the out of
780 date prerequisites. The
784 transforms an archive member specification into a file name:
795 OBJS=etoa.$O atoe.$O ebcdic.$O
798 $LD -o $target $prereq
801 $LIB: ${OBJS:%=$LIB(%)}
804 builds a program by loading it with a library.
808 For each target of interest,
813 structure called a dependency graph. The nodes of
814 the graph represent targets and prerequisites;
816 from one node to another indicates that
817 the file associated with the first node depends
818 on the file associated with the second.
821 has been completely read, the graph is analyzed.
822 In the first step, implied dependencies are resolved by
824 .I "transitive closure"
826 This calculation extends the graph to include all
827 targets that are potentially
828 derivable from the rules in the
830 Next the graph is checked for cycles;
832 accepts cyclic dependencies, but
836 prune subgraphs that are irrelevant for producing the
837 desired target and verify that there is only one way
839 The recipes associated with the
840 nodes on the longest path between the
841 target and an out of date prerequisite
842 are then executed in reverse order.
844 The transitive closure calculation is sensitive to
845 metarules; the patterns often select many potential targets
846 and cause the graph to grow rapidly.
848 dependencies associated with the desired target
849 usually form a small part of the graph, so, after
850 pruning, analysis is tractable.
851 For example, the rules
860 produce a graph with four nodes for each file in the
862 If the desired target is
865 detects the dependency between it
866 and the original file
868 through intermediate dependencies on
872 Nodes associated with other files are deleted during pruning because
873 they are irrelevant to the production of
877 avoids infinite cycles by evaluating
884 copies the prerequisite file once.
886 Conventions for evaluating rules
888 There must be only one
889 way to build each target. However, during evaluation
890 metarule patterns often select potential targets that
892 targets of other rules.
894 uses several conventions to resolve ambiguities
895 and to select the proper dependencies.
897 When a target selects more than one rule,
899 chooses a regular rule
906 FILES=f1.$O f2.$O f3.$O
909 $LD -o $target $prereq
917 contains two rules that could build
920 selects the last rule because its target,
922 is explicitly specified, while the
924 rule is a metarule. In effect,
925 the explicit rule for
927 overrides the general rule for building object files from
930 When a rule has a target and prerequisites but no recipe,
931 those prerequisites are added to all other rules with
932 recipes that have the same target.
933 All prerequisites, regardless of where they were specified, are
934 exported to the recipe in variable
940 FILES=f1.$O f2.$O f3.$O
943 $LD -o $target $prereq
952 as a prerequisite of the compile metarule;
953 an object file produced from a C source file
956 as well as the source file. Notice that the recipe of
957 the compile rule uses
961 because the latter specification would attempt to compile
964 When a target is virtual and there is no other rule with
967 evaluates each prerequisite.
968 For example, adding the rule
972 to the preceding example builds the executable
977 is the specified target. In effect, the
979 target is an alias for
982 When two rules have identical rule headers and both have
983 recipes, the later rule replaces the former one.
997 OFILES=f1.$O f2.$O f3.$O
1002 $LD $LFLAGS -l $OFILES -lbio -lc
1004 overrides the general loader rule with a special
1005 rule using a non-standard library search sequence.
1006 A rule is neutralized by overriding it with a rule
1016 attribute suppresses the printing of the semicolon.
1018 When a rule has no prerequisites, the recipe is executed
1019 only when the target does not exist. For example,
1024 defines a rule to manage a marker file.
1025 If the file exists, it is considered up to date
1026 regardless of its modification time.
1027 When a virtual target has no prerequisites the
1028 recipe is always executed.
1031 rule is of this type:
1034 rm -f [$OS].out *.[$OS]
1036 When a rule without prerequisites has multiple targets, the
1037 extra targets are aliases for the rule.
1041 rm -f [$OS].out *.[$OS]
1044 rule can be invoked by any of three names.
1047 is handled specially:
1050 is invoked without a command line target
1051 all targets of the first non-metarule are built.
1052 If that rule has multiple targets, the recipe
1053 is executed once for each target; normally, the recipe
1054 of a rule with multiple targets is only executed once.
1056 A rule applies to a target only when its prerequisites
1057 exist or can be derived. More than one rule may have the
1058 same target as long as only one rule with a recipe
1059 remains applicable after the dependency evaluation completes.
1060 For example, consider a program built from C
1061 and assembler source files. Two rules produce
1069 As long as there are not two source files with names like
1074 can unambiguously select the proper rule.
1075 If both files exist,
1076 the rules are ambiguous
1079 exits with an error message.
1081 In Plan 9, many programs consist of portable code stored
1082 in one directory and architecture-specific source stored in
1089 FILES=f1.$O f2.$O f3.$O f3.$O
1092 $LD -o $target $prereq
1098 $CC $CFLAGS ../port/$stem.c
1100 builds the program named
1102 using portable code in directory
1104 and architecture-specific code in the current directory.
1106 names of the C source files in
1108 do not conflict with the names of files in the current directory,
1110 selects the appropriate rule to build the object file.
1111 If like-named files exist in both directories, the
1112 specification is ambiguous and an explicit target
1113 must be specified to resolve the ambiguity.
1122 uses the architecture-specific version of
1124 instead of the portable one.
1125 Here, the explicit rule unambiguously
1126 documents which of the
1127 like-named source files is used to build the program.
1130 heuristics can produce unintended results
1131 when rules are not carefully specified.
1132 For example, the rules that build
1133 object files from C or assembler source files
1140 illustrate a subtle pratfall.
1141 Adding a header file dependency to the compile rule
1146 produces the error message
1148 .CW "don't know how to make '\fIfile\fP.c'"
1150 when \fIfile\fP.s is an assembler
1154 satisfies the assemble rule and
1156 satisfies the compile rule, so
1157 either rule can potentially produce the target.
1158 When a prerequisite exists or can be
1160 all other prerequisites in that
1161 rule header must exist or be derivable; here,
1164 forces the evaluation of a C source file.
1165 Specifying the dependencies in different
1166 rules avoids this interpretation:
1174 is an additional prerequisite of the compile rule,
1175 the two rules are evaluated independently and
1176 the existence of the C source file is not linked
1177 to the existence of the header file.
1178 However, this specification describes a different
1179 dependency. Originally, only object
1180 files derived from C files depended on
1182 now all object files, including those built
1183 from assembler source, depend on the header file.
1185 Metarule patterns should be as restrictive as possible to
1186 prevent conflicts with other rules.
1194 install:V: $BIN/$PROG
1198 $LD -o $target $stem.$O
1203 The first target builds an executable
1204 in the local directory; the second
1205 installs it in the directory
1206 of executables for the architecture.
1213 mk: ambiguous recipes for /mips/bin/foo:
1214 /mips/bin/foo <-(mkfile:8)- /mips/bin/foo.c <-(mkfile:12)- foo.c
1215 /mips/bin/foo <-(mkfile:12)- foo <-(mkfile:8)- foo.c
1217 The prerequisite of the
1221 matches both metarules because the
1223 pattern matches everything.
1226 pattern restricts the compile rule to files in the
1227 current directory and avoids the conflict:
1231 $LD -o $target $stem.$O
1234 Missing intermediates
1237 does not build a missing intermediate file if a target
1238 is up to date with the prerequisites of the intermediate.
1240 when an executable is up to date with its source file,
1242 does not compile the source to create a missing object file.
1243 The evaluation only applies
1244 when a target is considered up to date by pretending that the
1245 intermediate exists. Thus, it does not apply
1246 when the intermediate is a command line target
1247 or when it has no prerequisites.
1249 This capability is useful for
1250 maintaining archives. We can modify the archive
1251 update recipe to remove object files after
1255 $LIB: ${OBJS:%=$LIB(%)}
1256 names=`{membername $newprereq}
1262 does not remake the object files as long as the members
1263 of the archive remain up to date with the source files.
1266 command line option overrides this behavior
1267 and causes all intermediates to be built.
1269 Alternative out-of-date determination
1271 Sometimes the modification time is not useful
1272 for deciding when a target and prerequisite are out of date.
1275 attribute replaces the default mechanism with the result of
1276 a command. The command immediately follows the attribute
1277 and is repeatedly executed with each
1278 target and each prerequisite as its arguments;
1279 if its exit status is non-zero, they are considered out of date
1280 and the recipe is executed. Consider the
1283 foo.ref:Pcmp -s: foo
1294 the latter file is copied to the former.
1300 executes recipes in parallel.
1303 specifies the maximum number of simultaneously executing
1305 Normally it is imported from the environment,
1306 where the system has set it to the number of available processors.
1307 It can be decreased by assigning a new
1308 value and can be set to 1 to force single-threaded recipe execution.
1309 This is necessary when several targets access
1310 a common resource such as
1311 a status file or data base.
1312 When there is no dependency between targets,
1316 executed concurrently.
1317 Normally, this allows
1318 multiple prerequisites to be built simultaneously;
1319 for example, the object file prerequisites of
1320 a load rule can be produced by compiling the source files in parallel.
1322 does not define the order of execution of independent recipes.
1323 When the prerequisites of a rule are not independent,
1324 the dependencies between them should be specified in a rule or the
1326 should be single-threaded.
1327 For example, the archive update rules
1330 $LIB: ${OBJS:%=$LIB(%)}
1331 ar rv $LIB `{membername $newprereq}
1333 compile source files in parallel but update
1334 all members of the archive at once.
1335 It is a mistake to merge the two rules
1342 command is executed for every
1343 member of the library. Not only is this
1344 inefficient, but the archive is updated
1345 in parallel, making interference likely.
1349 environment variable contains a number associated
1350 with the processor executing a recipe.
1351 It can be used to create unique
1353 recipe may be executing simultaneously on several processors.
1354 Other maintenance tools provide mechanisms to control recipe
1355 scheduling explicitly [Cmel86], but
1357 general rules are sufficient for all but the most unusual cases.
1359 Deleting target files on errors
1366 to remove the target file when a
1367 recipe terminates prematurely.
1368 The error message describing the
1369 termination condition warns
1371 A partially built file is doubly dangerous:
1372 it is not only wrong, but is also
1373 considered to be up to date so
1376 will not rebuild it. For example,
1379 pic $prereq | tbl | troff -ms > $target
1381 produces the message
1383 .CW "mk: pic mk.ms | ... : exit status=rc 685: deleting 'pic.out'"
1385 if any program in the recipe exits with an error status.
1387 Unspecified dependencies
1391 command line flag forces the
1392 files following the flag to be treated
1393 as if they were just modified.
1394 We can use this flag with a command that selects files
1395 to force a build based on the selection criterion.
1396 For example, if the declaration of
1397 a global variable named
1399 is changed in a header file,
1400 all source files that reference
1401 it can be rebuilt with the command
1403 $ mk -w`{grep -l \fIvar\fP *.[cyl]}
1408 There are many programs related to
1410 each choosing a different balance between
1411 specialization and generality.
1413 emphasizes generality but allows
1414 customization through its pattern specifications and
1417 Plan 9 presents a difficult maintenance environment
1418 with its heterogeneous
1419 architectures and languages.
1421 flexible specification language and simple
1424 work well in this environment.
1428 to automate almost all maintenance.
1429 Tasks as diverse as updating the
1430 network data base, producing the manual,
1431 or building a release are expressed as
1437 [Cmel86] R. F. Cmelik,
1438 ``Concurrent Make: A Distributed Program in Concurrent C'',
1439 AT&T Bell Laboratories Technical Report, 1986.
1441 [Feld79] S. I. Feldman,
1442 ``Make \(em a program for maintaining computer programs'',
1444 Software Practice & Experience ,
1450 [Flan95] Bob Flandrena,
1454 [Hume87] A. G. Hume,
1455 ``Mk: A Successor to Make'',
1457 USENIX Summer Conf. Proc.,
1461 Appendix: Differences between
1466 The differences between
1473 builds targets when it needs them, allowing systematic use of side effects.
1475 constructs the entire dependency graph before building any target.
1478 supports suffix rules and
1484 and regular expression metarules.
1487 support only suffix rules.)
1490 performs transitive closure on metarules,
1495 supports cyclic dependencies,
1500 evaluates recipes one line at a time, replacing variables by their values and
1501 executing some commands internally.
1503 passes the entire recipe to the shell without
1504 interpretation or internal execution.
1507 supports parallel execution of single-line recipes when building
1508 the prerequisites for specified targets.
1510 supports parallel execution of all recipes.
1513 did not support parallel execution.)
1516 uses special targets (beginning with a period)
1517 to indicate special processing.
1519 uses attributes to modify rule evaluation.
1523 targets that are independent of the file system.
1526 allows non-standard out-of-date determination,
1530 It is usually easy to convert a
1532 to or from an equivalent