From owner-freebsd-bugs@FreeBSD.ORG Fri Sep 2 18:50:07 2011 Return-Path: Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id F036A106564A for ; Fri, 2 Sep 2011 18:50:07 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:4f8:fff6::28]) by mx1.freebsd.org (Postfix) with ESMTP id C6AF08FC13 for ; Fri, 2 Sep 2011 18:50:07 +0000 (UTC) Received: from freefall.freebsd.org (localhost [127.0.0.1]) by freefall.freebsd.org (8.14.4/8.14.4) with ESMTP id p82Io7LZ093007 for ; Fri, 2 Sep 2011 18:50:07 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.4/8.14.4/Submit) id p82Io7Pb093006; Fri, 2 Sep 2011 18:50:07 GMT (envelope-from gnats) Resent-Date: Fri, 2 Sep 2011 18:50:07 GMT Resent-Message-Id: <201109021850.p82Io7Pb093006@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Kilian Klimek Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 7F6BD106567C for ; Fri, 2 Sep 2011 18:45:01 +0000 (UTC) (envelope-from nobody@FreeBSD.org) Received: from red.freebsd.org (red.freebsd.org [IPv6:2001:4f8:fff6::22]) by mx1.freebsd.org (Postfix) with ESMTP id 6A0FA8FC13 for ; Fri, 2 Sep 2011 18:45:01 +0000 (UTC) Received: from red.freebsd.org (localhost [127.0.0.1]) by red.freebsd.org (8.14.4/8.14.4) with ESMTP id p82Ij1pV070853 for ; Fri, 2 Sep 2011 18:45:01 GMT (envelope-from nobody@red.freebsd.org) Received: (from nobody@localhost) by red.freebsd.org (8.14.4/8.14.4/Submit) id p82Ij0jP070852; Fri, 2 Sep 2011 18:45:00 GMT (envelope-from nobody) Message-Id: <201109021845.p82Ij0jP070852@red.freebsd.org> Date: Fri, 2 Sep 2011 18:45:00 GMT From: Kilian Klimek To: freebsd-gnats-submit@FreeBSD.org X-Send-Pr-Version: www-3.1 Cc: Subject: bin/160403: concurrently running rc-scripts during boot X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 02 Sep 2011 18:50:08 -0000 >Number: 160403 >Category: bin >Synopsis: concurrently running rc-scripts during boot >Confidential: no >Severity: non-critical >Priority: low >Responsible: freebsd-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: change-request >Submitter-Id: current-users >Arrival-Date: Fri Sep 02 18:50:07 UTC 2011 >Closed-Date: >Last-Modified: >Originator: Kilian Klimek >Release: >Organization: >Environment: >Description: Attached in a patch against current that modifies rcorder to allow it to run rc-scripts concurrently during boot. The purpose is, of course, to speedup the boot process. The speedup can be quite substantial. I measured a speedup of up to 30% (some numbers to support this can be found at https://github.com/kil/rcorder in the README). A few notes about the patch: - The modifications in /etc/rc.d/ are required to make sure cleartmp doesn't run at the same time as the scripts modified (they create temporary files in /tmp). - To ensure compatibility, the modifications to rcorder don't affect the default invocation of it in /etc/rc. The ordering of the rc-scripts that is generated is identical to the ordering that is generated now. >How-To-Repeat: >Fix: Patch attached with submission follows: Index: etc/rc =================================================================== --- etc/rc (revision 225227) +++ etc/rc (working copy) @@ -82,17 +82,21 @@ # Do a first pass to get everything up to $early_late_divider so that # we can do a second pass that includes $local_startup directories # -files=`rcorder ${skip} /etc/rc.d/* 2>/dev/null` +if checkyesno rc_concurrent; then + rcorder -r ${skip} -a ${_boot} -l ${early_late_divider} /etc/rc.d/* +else + files=`rcorder ${skip} /etc/rc.d/* 2>/dev/null` -_rc_elem_done=' ' -for _rc_elem in ${files}; do - run_rc_script ${_rc_elem} ${_boot} - _rc_elem_done="${_rc_elem_done}${_rc_elem} " + _rc_elem_done=' ' + for _rc_elem in ${files}; do + run_rc_script ${_rc_elem} ${_boot} + _rc_elem_done="${_rc_elem_done}${_rc_elem} " - case "$_rc_elem" in - */${early_late_divider}) break ;; - esac -done + case "$_rc_elem" in + */${early_late_divider}) break ;; + esac + done +fi unset files local_rc @@ -104,15 +108,20 @@ *) find_local_scripts_new ;; esac -files=`rcorder ${skip} /etc/rc.d/* ${local_rc} 2>/dev/null` -for _rc_elem in ${files}; do - case "$_rc_elem_done" in - *" $_rc_elem "*) continue ;; - esac +if checkyesno rc_concurrent; then + rcorder -r ${skip} -a ${_boot} -f ${early_late_divider} /etc/rc.d/* \ + ${local_rc} + echo "rc_concurrent finished" +else + files=`rcorder ${skip} /etc/rc.d/* ${local_rc} 2>/dev/null` + for _rc_elem in ${files}; do + case "$_rc_elem_done" in + *" $_rc_elem "*) continue ;; + esac - run_rc_script ${_rc_elem} ${_boot} -done - + run_rc_script ${_rc_elem} ${_boot} + done +fi echo '' date exit 0 Index: etc/Makefile =================================================================== --- etc/Makefile (revision 225227) +++ etc/Makefile (working copy) @@ -102,7 +102,7 @@ .endif # -rwxr-xr-x root:wheel, for the new cron root:wheel -BIN2= netstart pccard_ether rc.suspend rc.resume +BIN2= netstart pccard_ether rc.suspend rc.resume rc.trampoline MTREE= BSD.include.dist BSD.root.dist BSD.usr.dist BSD.var.dist .if ${MK_SENDMAIL} != "no" Index: etc/rc.d/abi =================================================================== --- etc/rc.d/abi (revision 225227) +++ etc/rc.d/abi (working copy) @@ -6,6 +6,7 @@ # PROVIDE: abi # REQUIRE: archdep # KEYWORD: nojail +# BEFORE: cleartmp . /etc/rc.subr Index: etc/rc.d/jail =================================================================== --- etc/rc.d/jail (revision 225227) +++ etc/rc.d/jail (working copy) @@ -4,7 +4,7 @@ # # PROVIDE: jail -# REQUIRE: LOGIN cleanvar +# REQUIRE: LOGIN cleanvar cleartmp # BEFORE: securelevel # KEYWORD: nojail shutdown Index: etc/rc.d/motd =================================================================== --- etc/rc.d/motd (revision 225227) +++ etc/rc.d/motd (working copy) @@ -5,7 +5,7 @@ # PROVIDE: motd # REQUIRE: mountcritremote -# BEFORE: LOGIN +# BEFORE: LOGIN cleartmp . /etc/rc.subr Index: etc/defaults/rc.conf =================================================================== --- etc/defaults/rc.conf (revision 225227) +++ etc/defaults/rc.conf (working copy) @@ -25,6 +25,7 @@ rc_info="NO" # Enables display of informational messages at boot. rc_startmsgs="YES" # Show "Starting foo:" messages at boot rcshutdown_timeout="30" # Seconds to wait before terminating rc.shutdown +rc_concurrent="NO" # start rc scripts concurrently. early_late_divider="FILESYSTEMS" # Script that separates early/late # stages of the boot process. Make sure you know # the ramifications if you change this. Index: etc/rc.trampoline =================================================================== --- etc/rc.trampoline (revision 0) +++ etc/rc.trampoline (revision 0) @@ -0,0 +1,11 @@ +#!/bin/sh +. /etc/rc.subr +load_rc_config 'XXX' + +if test -n "$_RCORDER_RUN_DEBUG"; then + echo '_RCORDER_RUN_DEBUG' $1 $2 + sleep 0.02 + exit 0 +fi + +run_rc_script $1 $2 Property changes on: etc/rc.trampoline ___________________________________________________________________ Added: svn:executable + * Index: sbin/rcorder/rcorder.c =================================================================== --- sbin/rcorder/rcorder.c (revision 225227) +++ sbin/rcorder/rcorder.c (working copy) @@ -3,6 +3,7 @@ #endif /* + * Copyright (c) 2011 Kilian Klimek * Copyright (c) 1998, 1999 Matthew R. Green * All rights reserved. * Copyright (c) 1998 @@ -46,6 +47,12 @@ #include #include #include +#include +#include +#include +#include +#include +#include #include "ealloc.h" #include "sprite.h" @@ -76,6 +83,14 @@ int exit_code; int file_count; char **file_list; +int kq; +int childs = 0; +char d_script_arg[] = "faststart"; +char d_trampoline[] = "/etc/rc.trampoline"; +char *trampoline = d_trampoline; +char *script_arg = d_script_arg; +char *rc_first = NULL; +char *rc_last = NULL; typedef int bool; #define TRUE 1 @@ -83,6 +98,9 @@ typedef bool flag; #define SET TRUE #define RESET FALSE +#define RUNNING 2 +#define FIRST 3 +#define LAST 4 Hash_Table provide_hash_s, *provide_hash; @@ -90,6 +108,7 @@ typedef struct filenode filenode; typedef struct f_provnode f_provnode; typedef struct f_reqnode f_reqnode; +typedef struct f_neednode f_neednode; typedef struct strnodelist strnodelist; struct provnode { @@ -109,6 +128,11 @@ f_reqnode *next; }; +struct f_neednode { + filenode *entry; + f_neednode *next; +}; + struct strnodelist { filenode *node; strnodelist *next; @@ -122,6 +146,7 @@ f_reqnode *req_list; f_provnode *prov_list; strnodelist *keyword_list; + f_neednode *need_list; }; filenode fn_head_s, *fn_head; @@ -151,17 +176,31 @@ void initialize(void); void generate_ordering(void); int main(int, char *[]); +static pid_t spawn(filenode *); +static int wait_child(void); +static void run_scripts(void); +static void filenode_unlink(filenode *); +static int can_run(filenode *); +static void check_start(filenode *); +static void generate_needs(void); int main(int argc, char *argv[]) { int ch; + int run = 0; + struct stat st; - while ((ch = getopt(argc, argv, "dk:s:")) != -1) + while ((ch = getopt(argc, argv, "a:df:k:l:rs:T:")) != -1) switch (ch) { + case 'a': + script_arg = optarg; + break; case 'd': #ifdef DEBUG debug = 1; + /* inherited by the trampoline script */ + setenv("_RCORDER_RUN_DEBUG", "yes", 1); #else warnx("debugging not compiled in, -d ignored"); #endif @@ -169,9 +208,21 @@ case 'k': strnode_add(&keep_list, optarg, 0); break; + case 'r': + run = 1; + break; case 's': strnode_add(&skip_list, optarg, 0); break; + case 'T': + trampoline = optarg; + break; + case 'f': + rc_first = optarg; + break; + case 'l': + rc_last = optarg; + break; default: /* XXX should crunch it? */ break; @@ -187,9 +238,27 @@ DPRINTF((stderr, "initialize\n")); crunch_all_files(); DPRINTF((stderr, "crunch_all_files\n")); - generate_ordering(); - DPRINTF((stderr, "generate_ordering\n")); + if (run) { + /* do some sanity checking on the trampoline script */ + if (stat(trampoline, &st) == -1) + err(1, "failed to stat %s", trampoline); + if (!S_ISREG(st.st_mode)) + errx(1, "not a regular file: %s", trampoline); + + if ((st.st_mode & (S_IXUSR | S_IXGRP | S_IXOTH)) == 0) + errx(1, "not executable: %s", trampoline); + + if ((kq = kqueue()) == -1) + err(1, "kqueue failed"); + + run_scripts(); + DPRINTF((stderr, "run_scripts\n")); + } else { + generate_ordering(); + DPRINTF((stderr, "generate_ordering\n")); + } + exit(exit_code); } @@ -240,7 +309,16 @@ temp->req_list = NULL; temp->prov_list = NULL; temp->keyword_list = NULL; - temp->in_progress = RESET; + temp->need_list = NULL; + + if (rc_first != NULL && strncmp(rc_first, basename(filename), strlen(rc_first)) == 0) { + temp->in_progress = FIRST; + } else if (rc_last != NULL && strncmp(rc_last, basename(filename), strlen(rc_last)) == 0) { + temp->in_progress = LAST; + } else { + temp->in_progress = RESET; + } + /* * link the filenode into the list of filenodes. * note that the double linking means we can delete a @@ -720,9 +798,6 @@ } else was_set = 0; - /* mark fnode */ - fnode->in_progress = SET; - /* * for each requirement of fnode -> r * satisfy_req(r, filename) @@ -739,6 +814,10 @@ } fnode->req_list = NULL; + /* mark fnode */ + if (fnode->in_progress != FIRST && fnode->in_progress != LAST) + fnode->in_progress = SET; + /* * for each provision of fnode -> p * remove fnode from provision list for p in hash table @@ -763,8 +842,14 @@ DPRINTF((stderr, "next do: ")); /* if we were already in progress, don't print again */ - if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) - printf("%s\n", fnode->filename); + if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) { + if (rc_first == NULL) + printf("%s\n", fnode->filename); + if (fnode->in_progress == FIRST) + rc_first = NULL; + else if (fnode->in_progress == LAST) + exit(0); + } if (fnode->next != NULL) { fnode->next->last = fnode->last; @@ -805,3 +890,299 @@ do_file(fn_head->next); } } + +/* + * Check if fn_this can be started by checking its requirements and status. + */ +static int +can_run(filenode *fn_this) { + provnode *p; + Hash_Entry *entry; + f_reqnode *r; + int all_set; + + if (fn_this->in_progress == RUNNING + || fn_this->in_progress == LAST + || fn_this->in_progress == SET) + return (0); + + all_set = 1; + + if (fn_this->req_list != NULL) { + r = fn_this->req_list; + + /* check if all requirements are satisfied */ + while (r != NULL) { + entry = r->entry; + p = Hash_GetValue(entry); + + if (p != NULL && p->head == SET) + p = p->next; + + if (p != NULL) { + all_set = 0; + break; + } + + r = r->next; + } + } + return (all_set); +} + +/* + * Generate the need_list for all nodes. This has to happen after all + * dependencies have been resolved. + */ +static void +generate_needs(void) +{ + provnode *p; + Hash_Entry *entry; + f_reqnode *r; + filenode *fn_this; + f_neednode *n; + + for(fn_this = fn_head->next; fn_this != NULL; fn_this = fn_this->next) { + if (fn_this->req_list != NULL) { + r = fn_this->req_list; + + while (r != NULL) { + entry = r->entry; + p = Hash_GetValue(entry); + + if (p != NULL && p->head == SET) + p = p->next; + + while (p != NULL) { + if(p->fnode == NULL) { + p = p->next; + continue; + } + + n = emalloc(sizeof(f_neednode)); + n->next = NULL; + n->entry = fn_this; + n->next = p->fnode->need_list; + p->fnode->need_list = n; + p = p->next; + } + r = r->next; + } + } + } +} + +/* + * fill the need lists and start everything that has no requirements. + */ +static void +run_scripts(void) +{ + filenode *fn_this, + *t = NULL; + + generate_needs(); + + DPRINTF((stderr, "init...\n")); + fn_this = fn_head->next; + while (fn_this != NULL) { + if (fn_this->in_progress == FIRST) { + t = fn_this; + } else { + if (can_run(fn_this)) + spawn(fn_this); + } + fn_this = fn_this->next; + } + + /* + * If rc_first was set, we have to skip the dependecies before + * rc_first. We can't unset rc_first in the loop above because + * that would allow scripts, that should not started, to run. + */ + if (t) { + rc_first = NULL; + t->in_progress = RESET; + spawn(t); + fn_this = fn_head->next; + while (fn_this != NULL) { + if (can_run(fn_this)) + spawn(fn_this); + fn_this = fn_this->next; + } + } + + DPRINTF((stderr, "wait ...\n")); + while (childs > 0) + wait_child(); + exit(0); +} + + +/* + * Start a rc script for a filenode. + */ +static pid_t +spawn(filenode *fn) +{ + struct kevent event; + pid_t p; + char *args[] = {trampoline, fn->filename, script_arg, NULL}; + + if (fn->in_progress == SET || fn->in_progress == RUNNING) + return (0); + + if (fn->in_progress == FIRST) + return (0); + + if (fn->in_progress == LAST) + return (0); + + if (rc_first != NULL) { + filenode_unlink(fn); + check_start(fn); + return (1); + } + + if (!(skip_ok(fn) && keep_ok(fn))) { + filenode_unlink(fn); + check_start(fn); + return (1); + } + + DPRINTF((stderr, "spawn: %s\n", fn->filename)); + childs++; + p = fork(); + + if (p == -1) { + if (errno == EAGAIN) + return (0); + err(1, "fork"); + } + + /* parent */ + if (p > 0) { + EV_SET(&event, p, EVFILT_PROC, + EV_ADD | EV_ENABLE | EV_ONESHOT, + NOTE_EXIT, 0, fn); + + if (kevent(kq, &event, 1, NULL, 0, NULL) == -1) { + if (errno == EINTR) + return (0); + err(1, "kevent"); + } + + fn->in_progress = RUNNING; + return (p); + } + + /* child */ + execv(args[0], args); + exit(1); +} + +/* + * Wait for at least one child process to exit. We block for a maximum + * of 20 seconds. After that, collect what is available. + */ +static int +wait_child(void) +{ + struct kevent event; + filenode *f; + int ret; + struct timespec ts; + + ts.tv_sec = 20; + ts.tv_nsec = 0; + + while (1) { + ret = kevent(kq, NULL, 0, &event, 1, &ts); + + if (ret == 0) + break; + + ts.tv_sec = 0; + + if (ret == -1) { + if (errno == EINTR) + break; + err(1, "kevent"); + } + + /* + * ignore waitpid errors and exit status; nothing we can do. + * just collect childs. + */ + waitpid(event.ident, NULL, WNOHANG); + childs--; + + f = (filenode *) event.udata; + + if (event.fflags & NOTE_EXIT) { + DPRINTF((stderr, "exit: %s (%d)\n", f->filename, event.ident)); + filenode_unlink(f); + check_start(f); + } + } + + return (0); +} + +/* + * For f check which nodes that require it can be started. and start them. + */ +static void +check_start(filenode *f) +{ + filenode *fn; + f_neednode *n; + + if (f->need_list == NULL) + return; + + n = f->need_list; + while (n != NULL) { + fn = n->entry; + if(can_run(fn)) + spawn(fn); + n = n->next; + } +} + +/* + * Remove filenode from list. + */ +static void +filenode_unlink(filenode *f) +{ + f_provnode *p, + *p_tmp; + provnode *pnode; + + f->in_progress = SET; + if (f->next != NULL) + f->next->last = f->last; + if (f->last != NULL) + f->last->next = f->next; + f->req_list = NULL; + + /* + * for each provision of fnode -> p + * remove fnode from provision list for p in hash table + */ + p = f->prov_list; + while (p != NULL) { + p_tmp = p; + pnode = p->pnode; + if (pnode->next != NULL) + pnode->next->last = pnode->last; + if (pnode->last != NULL) + pnode->last->next = pnode->next; + free(pnode); + p = p->next; + free(p_tmp); + } + f->prov_list = NULL; +} Index: sbin/rcorder/rcorder.8 =================================================================== --- sbin/rcorder/rcorder.8 (revision 225227) +++ sbin/rcorder/rcorder.8 (working copy) @@ -39,8 +39,13 @@ .Nd print a dependency ordering of interdependent files .Sh SYNOPSIS .Nm +.Op Fl a Ar action +.Op Fl f Ar first .Op Fl k Ar keep +.Op Fl l Ar last +.Op Fl r .Op Fl s Ar skip +.Op Fl T Ar trampoline_script .Ar .Sh DESCRIPTION The @@ -95,18 +100,44 @@ .Pp The options are as follows: .Bl -tag -width indent +.It Fl a Ar action +Argument passed to rc scripts by the trampoline script. +.It Fl f Ar first +Act as if the requirement +.Ar first, +and requirements leading up to it, have already been satisfied (see +.Sx CAVEATS +sections). .It Fl k Add the specified keyword to the .Dq "keep list" . If any .Fl k option is given, only those files containing the matching keyword are listed. +.It Fl l Ar last +Stop when the requirement +.Ar last +has been satisfied (see +.Sx CAVEATS +sections). +.It Fl r +Instead of printing the ordered list of rc scripts, execute them concurrently +as +.Nm +sees fit. .It Fl s Add the specified keyword to the .Dq "skip list" . If any .Fl s option is given, files containing the matching keyword are not listed. +.It Fl T Ar trampoline_script +When running with the +.Fl r +flag, use the specified argument as the +.Ar trampoline_script. +It is called with the rc script to start as the first argument and the action +(e.g. faststart) to take as the second argument. .El .Pp An example block follows: @@ -155,6 +186,48 @@ A set of files has a circular dependency which was detected while processing the stated file. .El +.Sh CAVEATS +When running with the +.Fl r +flag, the arguments passed to +.Fl f +or +.Fl l +must be one of the check-points (or "placeholders") mentioned in +.Xr rc 8 . +.Pp +The ordering generated when running with or without the +.Fl r +flag is different. Without the +.Fl r +flag, and with the +.Fl l +flag, +.Nm +produces an ordering that only guarantees that the check-point will +be satisfied. With the +.Fl r +flag, +.Nm +will guarantee that all and only the requirements leading up to the +check-point will be satisfied. +.Pp +Likewise, with the +.Fl f +flag and the +.Fl r +flag set, +.Nm +will assume all and only the requirements before the check-point are +satisfied. Without the +.Fl r +flag, the ordering will complement the ordering generated of the same +.Nm +run with the +.Fl f +replaced with +.Fl l +flag. .Sh SEE ALSO .Xr rc 8 .Sh HISTORY Index: share/man/man5/rc.conf.5 =================================================================== --- share/man/man5/rc.conf.5 (revision 225227) +++ share/man/man5/rc.conf.5 (working copy) @@ -114,6 +114,11 @@ show .Dq Starting foo: when faststart is used (e.g., at boot time). +.It Va rc_concurrent +.Pq Vt bool +If set to +.Dq Li YES , +start rc scripts concurrently. .It Va early_late_divider .Pq Vt str The name of the script that should be used as the >Release-Note: >Audit-Trail: >Unformatted: