From nobody Sun Aug 20 05:05:43 2023 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4RT3Th1lKgz4qk07; Sun, 20 Aug 2023 05:05:44 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4RT3Th0rF9z4VxT; Sun, 20 Aug 2023 05:05:44 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1692507944; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=XmM0brXUQLf58KdbMuRNFAWH9dSgHIL4INI1NaJqcw8=; b=g7wcolE20zEQQBkMNGJzlisk67kTFM9+cTU6WHpS/w/MH//c3o1xAcxCcMyWyWd5zFpbqb RlC04QDr7SSu1QEDFs8R6yOy0FTun2HINXbrJiw48rpGhfHk/3wTRZBH9xxmTNtXb2TZrV jjuQa7nFOQvzyZiKrqQn3EbH5iRLt9iIRYmuNOuWZ+OpSbmHpB8NbBDhpArg/BvD0j0YIx h/yaPFpDtYIqrwzoV7Jmua39RzPDBtq4qZ94Qe8vUkLNPOpoKLY9tHK927wBZOwPD9F1iz z1HVcp22NqeSuZ9UGRY2sUYHC5bG+Ps7Vf4FFDj9wkeGjb5oeRB2wRZTJpP8XA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1692507944; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=XmM0brXUQLf58KdbMuRNFAWH9dSgHIL4INI1NaJqcw8=; b=jY4+Vzd6fGh1vC/HsZQCFrbvNZNmvrN5PphrKmK9KLdmzxhz4BhD7byw2RcytGzo0lgBrd E9KtXLu8lpSJC3hBMuEyhcnDM21PQZGP19SX8DPIZL8BKOJvoIg73WdLYM5z2LbgcZjmSf T40Nz5PjYnSsGc87sBGQE23ZS0zL2a0Ljcs48bWQj0sdDGCf6S6kv5XWmKXX9pgrCSNWZb se1JNs25X1UXhLmmAcYPi7GnHLBeQVw3nCW8jM+4hmCMgeh9GPfPQUmGrOX5skkTJPNau+ T1hGcYV4o7trcnGaZROJZnEz1MS6hyFJbMarGXBsNNlN0UU/6d1qXV07zCKbuw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1692507944; a=rsa-sha256; cv=none; b=QgeZH5Uj7KIs2uTbMBW8/T3TDYN9flyEyTDUItd6nwlf8H8DPctVHl9qCLeor6209OOf5s UHuvV+QEmwZHZwBoBIa48iemZeW98FQ8fBnWQOmQ/K7ihiVM4Qou+LoU3FlulnSSl60Htb QGoQgRJcHSzEW3kEMGlhE6+Cy0EDVMXBA/ugdHUY+IjIuOibj6q7kCRJPoWHgJfXZSX4Zt bZZM1OP/N01UzyzIozYQv373gT+TOF7pspsRZqf16JIEQZeYtPKYNvDXUdAFqklLQLSWZm wyAVmYSomcBYo7rjm+FW/6FjFEnE/nvKOcq0zDWkJXQyWp0YgjhlsTx7AlP3xw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4RT3Tg71WWzBSM; Sun, 20 Aug 2023 05:05:43 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 37K55h4i000396; Sun, 20 Aug 2023 05:05:43 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 37K55hMo000393; Sun, 20 Aug 2023 05:05:43 GMT (envelope-from git) Date: Sun, 20 Aug 2023 05:05:43 GMT Message-Id: <202308200505.37K55hMo000393@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Colin Percival Subject: git: 9a7add6d01f3 - main - init_main: Switch from sysinit array to SLIST List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: cperciva X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 9a7add6d01f3c5f7eba811e794cf860d2bce131d Auto-Submitted: auto-generated The branch main has been updated by cperciva: URL: https://cgit.FreeBSD.org/src/commit/?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d commit 9a7add6d01f3c5f7eba811e794cf860d2bce131d Author: Colin Percival AuthorDate: 2023-07-18 02:29:20 +0000 Commit: Colin Percival CommitDate: 2023-08-20 05:04:56 +0000 init_main: Switch from sysinit array to SLIST This has two effects: 1. We can mergesort the sysinits instead of bubblesorting them, which shaves about 2 ms off the boot time in Firecracker. 2. Adding more sysinits (e.g. from a KLD) can be performed by sorting them and then merging the sorted lists, which is both faster than the previous "append and sort" approach and avoids needing malloc. Reviewed by: jhb (previous version) Sponsored by: https://www.patreon.com/cperciva Differential Revision: https://reviews.freebsd.org/D41075 --- sys/kern/init_main.c | 177 +++++++++++++++++++++++++-------------------------- 1 file changed, 86 insertions(+), 91 deletions(-) diff --git a/sys/kern/init_main.c b/sys/kern/init_main.c index d675e3538f67..aa82eafff9b0 100644 --- a/sys/kern/init_main.c +++ b/sys/kern/init_main.c @@ -73,6 +73,8 @@ #include #include #include +#include +#include #include #include #include @@ -154,46 +156,73 @@ FEATURE(invariants, "Kernel compiled with INVARIANTS, may affect performance"); SYSINIT(placeholder, SI_SUB_DUMMY, SI_ORDER_ANY, NULL, NULL); /* - * The sysinit table itself. Items are checked off as the are run. - * If we want to register new sysinit types, add them to newsysinit. + * The sysinit linker set compiled into the kernel. These are placed onto the + * sysinit list by mi_startup; sysinit_add can add (e.g., from klds) additional + * sysinits to the linked list but the linker set here does not change. */ SET_DECLARE(sysinit_set, struct sysinit); -struct sysinit **sysinit, **sysinit_end; -struct sysinit **newsysinit, **newsysinit_end; /* - * Merge a new sysinit set into the current set, reallocating it if - * necessary. This can only be called after malloc is running. + * The sysinit list itself. Items are removed as they are run. */ -void -sysinit_add(struct sysinit **set, struct sysinit **set_end) +static SLIST_HEAD(sysinitlist, sysinit) sysinit_list; + +/* + * Compare two sysinits; return -1, 0, or 1 if a comes before, at the same time + * as, or after b. + */ +static int +sysinit_compar(struct sysinit *a, struct sysinit *b, void *thunk __unused) +{ + + if (a->subsystem < b->subsystem) + return (-1); + if (a->subsystem > b->subsystem) + return (1); + if (a->order < b->order) + return (-1); + if (a->order > b->order) + return (1); + return (0); +} + +static void +sysinit_mklist(struct sysinitlist *list, struct sysinit **set, + struct sysinit **set_end) { - struct sysinit **newset; struct sysinit **sipp; - struct sysinit **xipp; - int count; - - count = set_end - set; - if (newsysinit) - count += newsysinit_end - newsysinit; - else - count += sysinit_end - sysinit; - newset = malloc(count * sizeof(*sipp), M_TEMP, M_NOWAIT); - if (newset == NULL) - panic("cannot malloc for sysinit"); - xipp = newset; - if (newsysinit) - for (sipp = newsysinit; sipp < newsysinit_end; sipp++) - *xipp++ = *sipp; - else - for (sipp = sysinit; sipp < sysinit_end; sipp++) - *xipp++ = *sipp; + + TSENTER(); + TSENTER2("listify"); + SLIST_INIT(list); for (sipp = set; sipp < set_end; sipp++) - *xipp++ = *sipp; - if (newsysinit) - free(newsysinit, M_TEMP); - newsysinit = newset; - newsysinit_end = newset + count; + SLIST_INSERT_HEAD(list, *sipp, next); + TSEXIT2("listify"); + TSENTER2("mergesort"); + SLIST_MERGESORT(list, NULL, sysinit_compar, sysinit, next); + TSEXIT2("mergesort"); + TSEXIT(); +} + +/* + * Merge a new sysinit set into the sysinit list. + */ +void +sysinit_add(struct sysinit **set, struct sysinit **set_end) +{ + struct sysinitlist new_list; + + TSENTER(); + + /* Construct a sorted list from the new sysinits. */ + sysinit_mklist(&new_list, set, set_end); + + /* Merge the new list into the existing one. */ + TSENTER2("SLIST_MERGE"); + SLIST_MERGE(&sysinit_list, &new_list, NULL, sysinit_compar, sysinit, next); + TSEXIT2("SLIST_MERGE"); + + TSEXIT(); } #if defined (DDB) && defined(VERBOSE_SYSINIT) @@ -229,10 +258,7 @@ void mi_startup(void) { - struct sysinit **sipp; /* system initialization*/ - struct sysinit **xipp; /* interior loop of sort*/ - struct sysinit *save; /* bubble*/ - + struct sysinit *sip; int last; #if defined(VERBOSE_SYSINIT) int verbose; @@ -243,29 +269,8 @@ mi_startup(void) if (boothowto & RB_VERBOSE) bootverbose++; - if (sysinit == NULL) { - sysinit = SET_BEGIN(sysinit_set); - sysinit_end = SET_LIMIT(sysinit_set); - } - -restart: - /* - * Perform a bubble sort of the system initialization objects by - * their subsystem (primary key) and order (secondary key). - */ - TSENTER2("bubblesort"); - for (sipp = sysinit; sipp < sysinit_end; sipp++) { - for (xipp = sipp + 1; xipp < sysinit_end; xipp++) { - if ((*sipp)->subsystem < (*xipp)->subsystem || - ((*sipp)->subsystem == (*xipp)->subsystem && - (*sipp)->order <= (*xipp)->order)) - continue; /* skip*/ - save = *sipp; - *sipp = *xipp; - *xipp = save; - } - } - TSEXIT2("bubblesort"); + /* Construct and sort sysinit list. */ + sysinit_mklist(&sysinit_list, SET_BEGIN(sysinit_set), SET_LIMIT(sysinit_set)); last = SI_SUB_COPYRIGHT; #if defined(VERBOSE_SYSINIT) @@ -276,21 +281,23 @@ restart: #endif /* - * Traverse the (now) ordered list of system initialization tasks. - * Perform each task, and continue on to the next task. + * Perform each system initialization task from the ordered list. Note + * that if sysinit_list is modified (e.g. by a KLD) we will nonetheless + * always perform the earlist-sorted sysinit at each step; using the + * SLIST_FOREACH macro would result in items being skipped if inserted + * earlier than the "current item". */ - for (sipp = sysinit; sipp < sysinit_end; sipp++) { - if ((*sipp)->subsystem == SI_SUB_DUMMY) - continue; /* skip dummy task(s)*/ + while ((sip = SLIST_FIRST(&sysinit_list)) != NULL) { + SLIST_REMOVE_HEAD(&sysinit_list, next); - if ((*sipp)->subsystem == SI_SUB_DONE) - continue; + if (sip->subsystem == SI_SUB_DUMMY) + continue; /* skip dummy task(s)*/ - if ((*sipp)->subsystem > last) - BOOTTRACE_INIT("sysinit 0x%7x", (*sipp)->subsystem); + if (sip->subsystem > last) + BOOTTRACE_INIT("sysinit 0x%7x", sip->subsystem); #if defined(VERBOSE_SYSINIT) - if ((*sipp)->subsystem > last && verbose_sysinit != 0) { + if (sip->subsystem > last && verbose_sysinit != 0) { verbose = 1; printf("subsystem %x\n", last); } @@ -298,23 +305,23 @@ restart: #if defined(DDB) const char *func, *data; - func = symbol_name((vm_offset_t)(*sipp)->func, + func = symbol_name((vm_offset_t)sip->func, DB_STGY_PROC); - data = symbol_name((vm_offset_t)(*sipp)->udata, + data = symbol_name((vm_offset_t)sip->udata, DB_STGY_ANY); if (func != NULL && data != NULL) printf(" %s(&%s)... ", func, data); else if (func != NULL) - printf(" %s(%p)... ", func, (*sipp)->udata); + printf(" %s(%p)... ", func, sip->udata); else #endif - printf(" %p(%p)... ", (*sipp)->func, - (*sipp)->udata); + printf(" %p(%p)... ", sip->func, + sip->udata); } #endif /* Call function */ - (*((*sipp)->func))((*sipp)->udata); + (*(sip->func))(sip->udata); #if defined(VERBOSE_SYSINIT) if (verbose) @@ -322,19 +329,7 @@ restart: #endif /* Check off the one we're just done */ - last = (*sipp)->subsystem; - (*sipp)->subsystem = SI_SUB_DONE; - - /* Check if we've installed more sysinit items via KLD */ - if (newsysinit != NULL) { - if (sysinit != SET_BEGIN(sysinit_set)) - free(sysinit, M_TEMP); - sysinit = newsysinit; - sysinit_end = newsysinit_end; - newsysinit = NULL; - newsysinit_end = NULL; - goto restart; - } + last = sip->subsystem; } TSEXIT(); /* Here so we don't overlap with start_init. */ @@ -904,13 +899,13 @@ db_show_print_syinit(struct sysinit *sip, bool ddb) DB_SHOW_COMMAND_FLAGS(sysinit, db_show_sysinit, DB_CMD_MEMSAFE) { - struct sysinit **sipp; + struct sysinit *sip; db_printf("SYSINIT vs Name(Ptr)\n"); db_printf(" Subsystem Order\n"); db_printf(" Function(Name)(Arg)\n"); - for (sipp = sysinit; sipp < sysinit_end; sipp++) { - db_show_print_syinit(*sipp, true); + SLIST_FOREACH(sip, &sysinit_list, next) { + db_show_print_syinit(sip, true); if (db_pager_quit) break; }