Index: etc/defaults/rc.conf
===================================================================
--- etc/defaults/rc.conf
+++ etc/defaults/rc.conf
@@ -25,6 +25,7 @@
 # when the kenv variable rc.debug is set.
 #rc_debug="NO"		# Set to YES to enable debugging output from rc.d
 rc_info="NO"		# Enables display of informational messages at boot.
+rc_parallel="NO" 	# Run startup scripts in parallel
 rc_startmsgs="YES" 	# Show "Starting foo:" messages at boot
 rcshutdown_timeout="90" # Seconds to wait before terminating rc.shutdown
 early_late_divider="FILESYSTEMS"	# Script that separates early/late
Index: etc/rc
===================================================================
--- etc/rc
+++ etc/rc
@@ -120,13 +120,27 @@
 	skip_firstboot=""
 fi
 
-files=`rcorder ${skip} ${skip_firstboot} /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_parallel; then
+	_rc_parallel='-p'
+else
+	_rc_parallel=''
+fi
 
-	run_rc_script ${_rc_elem} ${_boot}
+files=`rcorder ${_rc_parallel} ${skip} ${skip_firstboot} /etc/rc.d/* ${local_rc} 2>/dev/null`
+echo "$files" | while read line
+do
+	for _rc_elem in ${line}; do
+		case "$_rc_elem_done" in
+		*" $_rc_elem "*)	continue ;;
+		esac
+
+		if [ -n ${_rc_parallel} ]; then
+			run_rc_script ${_rc_elem} ${_boot} &
+		else
+			run_rc_script ${_rc_elem} ${_boot}
+		fi
+	done
+	[ -n ${_rc_parallel} ] && wait
 done
 
 # Remove the firstboot sentinel, and reboot if it was requested.
Index: sbin/rcorder/rcorder.c
===================================================================
--- sbin/rcorder/rcorder.c
+++ sbin/rcorder/rcorder.c
@@ -77,6 +77,7 @@
 
 static int exit_code;
 static int file_count;
+static int generation;
 static char **file_list;
 
 typedef int bool;
@@ -124,6 +125,7 @@
 	f_reqnode	*req_list;
 	f_provnode	*prov_list;
 	strnodelist	*keyword_list;
+	int		generation;
 };
 
 static filenode fn_head_s, *fn_head;
@@ -152,13 +154,15 @@
 static void crunch_all_files(void);
 static void initialize(void);
 static void generate_ordering(void);
+static void generate_parallel(void);
+static int parallel = 0;
 
 int
 main(int argc, char *argv[])
 {
 	int ch;
 
-	while ((ch = getopt(argc, argv, "dk:s:")) != -1)
+	while ((ch = getopt(argc, argv, "dk:ps:")) != -1)
 		switch (ch) {
 		case 'd':
 #ifdef DEBUG
@@ -170,6 +174,9 @@
 		case 'k':
 			strnode_add(&keep_list, optarg, 0);
 			break;
+		case 'p':
+			parallel = 1;
+			break;
 		case 's':
 			strnode_add(&skip_list, optarg, 0);
 			break;
@@ -188,7 +195,11 @@
 	DPRINTF((stderr, "initialize\n"));
 	crunch_all_files();
 	DPRINTF((stderr, "crunch_all_files\n"));
-	generate_ordering();
+	if (parallel) {
+		generate_parallel();
+	} else {
+		generate_ordering();
+	}
 	DPRINTF((stderr, "generate_ordering\n"));
 
 	exit(exit_code);
@@ -721,46 +732,66 @@
 	} else
 		was_set = 0;
 
-	/* mark fnode */
-	fnode->in_progress = SET;
+	if (parallel) {
+		/*
+		 * Mark node as handled in the current iteration.
+		 * When running in parallel mode, we use this mechanism
+		 * instead of removing dependencies, because in case
+		 * where we have "A" node and its dependency "B", we must
+		 * make sure we don't emit "B A", but always "B\nA".
+		 */
+		DPRINTF((stderr, "node %s done in generation %d\n",
+		    fnode->filename, generation));
+		fnode->generation = generation;
+	} else {
+		/* mark fnode */
+		fnode->in_progress = SET;
 
-	/*
-	 * for each requirement of fnode -> r
-	 *	satisfy_req(r, filename)
-	 */
-	r = fnode->req_list;
-	while (r != NULL) {
-		satisfy_req(r, fnode->filename);
-		r = r->next;
-	}
-	fnode->req_list = NULL;
+		/*
+		 * for each requirement of fnode -> r
+		 *	satisfy_req(r, filename)
+		 */
+		r = fnode->req_list;
+		while (r != NULL) {
+#if 0
+			r_tmp = r;
+#endif
+			satisfy_req(r, fnode->filename);
+			r = r->next;
+#if 0
+			if (was_set == 0)
+				free(r_tmp);
+#endif
+		}
+		fnode->req_list = NULL;
 
-	/*
-	 * for each provision of fnode -> p
-	 *	remove fnode from provision list for p in hash table
-	 */
-	p = fnode->prov_list;
-	while (p != NULL) {
-		p_tmp = p;
-		pnode = p->pnode;
-		if (pnode->next != NULL) {
-			pnode->next->last = pnode->last;
+		/*
+		 * for each provision of fnode -> p
+		 *	remove fnode from provision list for p in hash table
+		 */
+		p = fnode->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);
 		}
-		if (pnode->last != NULL) {
-			pnode->last->next = pnode->next;
-		}
-		free(pnode);
-		p = p->next;
-		free(p_tmp);
+		fnode->prov_list = NULL;
 	}
-	fnode->prov_list = NULL;
 
 	/* do_it(fnode) */
 	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);
+		printf("%s%s", fnode->filename, parallel ? " " : "\n");
 	
 	if (fnode->next != NULL) {
 		fnode->next->last = fnode->last;
@@ -776,6 +807,96 @@
    		free(fnode);
 	}
 #endif
+}
+
+static bool
+unsatisfied_req(const struct filenode *fnode)
+{
+	const Hash_Entry *entry;
+	const provnode *head;
+	const f_reqnode *r;
+	int ndeps = 0;
+
+	for (r = fnode->req_list; r != NULL; r = r->next) {
+		entry = r->entry;
+		head = Hash_GetValue(entry);
+		if (head == NULL) {
+			warnx("requirement `%s' in file `%s' has no providers.",
+			    Hash_GetKey(entry), fnode->filename);
+			continue;
+		}
+
+		for (head = head->next; head != NULL; head = head->next) {
+			/*
+			 * Ignore dependencies handled in previous runs,
+			 * but not those handled in the current one.  Increase
+			 * current generation counter, emit newline, and go
+			 * around.
+			 */
+			if (head->fnode->generation != 0 &&
+			    head->fnode->generation < generation) {
+				DPRINTF((stderr, "%s had dependency %s handled "
+				    "in generation %d\n",
+				    fnode->filename, head->fnode->filename,
+				    head->fnode->generation));
+			} else {
+				DPRINTF((stderr, "%s has dependency %s\n",
+				    fnode->filename, head->fnode->filename));
+				//return (TRUE);
+				ndeps++;
+			}
+		}
+	}
+
+	if (ndeps > 0)
+		return (TRUE);
+
+	return (FALSE);
+}
+
+static void
+generate_parallel(void)
+{
+	static filenode *fnode, *fnode_next;
+	int nodes_done;
+	bool ignore_deps;
+
+	/*
+	 * Iterate over nodes, printing out leaf ones.  After each pass
+	 * emit "\n" to mark dependency of the following nodes on the
+	 * preceding ones.  Continue until there are no nodes left.
+	 */
+	ignore_deps = FALSE;
+	generation = 1;
+	do {
+		nodes_done = 0;
+		for (fnode = fn_head->next; fnode != NULL; fnode = fnode_next) {
+			fnode_next = fnode->next;
+			if (ignore_deps) {
+				warnx("cycle detected; ignoring dependencies "
+				    "for %s", fnode->filename);
+				ignore_deps = FALSE;
+			} else if (unsatisfied_req(fnode)) {
+				DPRINTF((stderr, "%s has dependencies; "
+				    "skipping\n", fnode->filename));
+				continue;
+			}
+			nodes_done++;
+			do_file(fnode);
+		}
+		generation++;
+		if (nodes_done > 0) {
+			printf("\n");
+		} else {
+			/*
+			 * There were no leaf nodes, ie nodes with no
+			 * dependencies.  This means the graph is cyclic.
+			 * It's hard to handle this in a sensible way; just
+			 * ignore dependencies for the next node and try again.
+			 */
+			ignore_deps = TRUE;
+		}
+	} while (fn_head->next != NULL);
 }
 
 static void