From owner-dev-commits-src-all@freebsd.org Sat Dec 26 18:39:54 2020 Return-Path: Delivered-To: dev-commits-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id AA2144BFEFD; Sat, 26 Dec 2020 18:39:54 +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 "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4D3CKQ4SbHz4Z5H; Sat, 26 Dec 2020 18:39:54 +0000 (UTC) (envelope-from git@FreeBSD.org) 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 8C06F197D9; Sat, 26 Dec 2020 18:39:54 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 0BQIdsdb055027; Sat, 26 Dec 2020 18:39:54 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 0BQIdsJb055026; Sat, 26 Dec 2020 18:39:54 GMT (envelope-from git) Date: Sat, 26 Dec 2020 18:39:54 GMT Message-Id: <202012261839.0BQIdsJb055026@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Jamie Gritton Subject: git: 7de883c82f50 - jail: Fix an O(n^2) loop when adding jails MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: jamie X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 7de883c82f50cd6945154915166fb0df97c70952 Auto-Submitted: auto-generated X-BeenThere: dev-commits-src-all@freebsd.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: "Commit messages for all branches of the src repository." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 26 Dec 2020 18:39:54 -0000 The branch main has been updated by jamie: URL: https://cgit.FreeBSD.org/src/commit/?id=7de883c82f50cd6945154915166fb0df97c70952 commit 7de883c82f50cd6945154915166fb0df97c70952 Author: Jamie Gritton AuthorDate: 2020-12-26 18:39:34 +0000 Commit: Jamie Gritton CommitDate: 2020-12-26 18:39:34 +0000 jail: Fix an O(n^2) loop when adding jails When a jail is added using the default (system-chosen) JID, and non-default-JID jails already exist, a loop through the allprison list could restart and result in unnecessary O(n^2) behaviour. There should never be more than two list passes required. Also clean up inefficient (though still O(n)) allprison list traversal when finding jails by ID, or when adding jails in the common case of all default JIDs. --- sys/kern/kern_jail.c | 163 +++++++++++++++++++++++++++++++++++---------------- 1 file changed, 114 insertions(+), 49 deletions(-) diff --git a/sys/kern/kern_jail.c b/sys/kern/kern_jail.c index 1bad2d7488c1..c29d966283f8 100644 --- a/sys/kern/kern_jail.c +++ b/sys/kern/kern_jail.c @@ -136,6 +136,7 @@ struct prisonlist allprison = TAILQ_HEAD_INITIALIZER(allprison); LIST_HEAD(, prison_racct) allprison_racct; int lastprid = 0; +static int get_next_prid(struct prison **insprp); static int do_jail_attach(struct thread *td, struct prison *pr); static void prison_complete(void *context, int pending); static void prison_deref(struct prison *pr, int flags); @@ -506,7 +507,7 @@ kern_jail_set(struct thread *td, struct uio *optuio, int flags) #endif struct vfsopt *opt; struct vfsoptlist *opts; - struct prison *pr, *deadpr, *mypr, *ppr, *tpr; + struct prison *pr, *deadpr, *inspr, *mypr, *ppr, *tpr; struct vnode *root; char *domain, *errmsg, *host, *name, *namelc, *p, *path, *uuid; char *g_path, *osrelstr; @@ -977,6 +978,7 @@ kern_jail_set(struct thread *td, struct uio *optuio, int flags) */ pr = NULL; ppr = mypr; + inspr = NULL; if (cuflags == JAIL_CREATE && jid == 0 && name != NULL) { namelc = strrchr(name, '.'); jid = strtoul(namelc != NULL ? namelc + 1 : name, &p, 10); @@ -985,23 +987,36 @@ kern_jail_set(struct thread *td, struct uio *optuio, int flags) } sx_xlock(&allprison_lock); if (jid != 0) { - /* - * See if a requested jid already exists. There is an - * information leak here if the jid exists but is not within - * the caller's jail hierarchy. Jail creators will get EEXIST - * even though they cannot see the jail, and CREATE | UPDATE - * will return ENOENT which is not normally a valid error. - */ if (jid < 0) { error = EINVAL; vfs_opterror(opts, "negative jid"); goto done_unlock_list; } - pr = prison_find(jid); + /* + * See if a requested jid already exists. Keep track of + * where it can be inserted later. + */ + TAILQ_FOREACH(inspr, &allprison, pr_list) { + if (inspr->pr_id == jid) { + mtx_lock(&inspr->pr_mtx); + if (inspr->pr_ref > 0) { + pr = inspr; + inspr = NULL; + } else + mtx_unlock(&inspr->pr_mtx); + break; + } + if (inspr->pr_id > jid) + break; + } if (pr != NULL) { ppr = pr->pr_parent; /* Create: jid must not exist. */ if (cuflags == JAIL_CREATE) { + /* + * Even creators that cannot see the jail will + * get EEXIST. + */ mtx_unlock(&pr->pr_mtx); error = EEXIST; vfs_opterror(opts, "jail %d already exists", @@ -1009,6 +1024,11 @@ kern_jail_set(struct thread *td, struct uio *optuio, int flags) goto done_unlock_list; } if (!prison_ischild(mypr, pr)) { + /* + * Updaters get ENOENT if they cannot see the + * jail. This is true even for CREATE | UPDATE, + * which normally cannot give this error. + */ mtx_unlock(&pr->pr_mtx); pr = NULL; } else if (pr->pr_uref == 0) { @@ -1175,52 +1195,26 @@ kern_jail_set(struct thread *td, struct uio *optuio, int flags) ppr->pr_uref++; mtx_unlock(&ppr->pr_mtx); pr = malloc(sizeof(*pr), M_PRISON, M_WAITOK | M_ZERO); - if (jid == 0) { - /* Find the next free jid. */ - jid = lastprid + 1; - findnext: - if (jid == JAIL_MAX) - jid = 1; - TAILQ_FOREACH(tpr, &allprison, pr_list) { - if (tpr->pr_id < jid) - continue; - if (tpr->pr_id > jid || tpr->pr_ref == 0) { - TAILQ_INSERT_BEFORE(tpr, pr, pr_list); - break; - } - if (jid == lastprid) { - error = EAGAIN; - vfs_opterror(opts, - "no available jail IDs"); - free(pr, M_PRISON); - prison_deref(ppr, PD_DEREF | - PD_DEUREF | PD_LIST_XLOCKED); - goto done_releroot; - } - jid++; - goto findnext; - } - lastprid = jid; - } else { - /* - * The jail already has a jid (that did not yet exist), - * so just find where to insert it. - */ - TAILQ_FOREACH(tpr, &allprison, pr_list) - if (tpr->pr_id >= jid) { - TAILQ_INSERT_BEFORE(tpr, pr, pr_list); - break; - } + + if (jid == 0 && (jid = get_next_prid(&inspr)) == 0) { + error = EAGAIN; + vfs_opterror(opts, "no available jail IDs"); + free(pr, M_PRISON); + prison_deref(ppr, + PD_DEREF | PD_DEUREF | PD_LIST_XLOCKED); + goto done_releroot; } - if (tpr == NULL) + pr->pr_id = jid; + if (inspr != NULL) + TAILQ_INSERT_BEFORE(inspr, pr, pr_list); + else TAILQ_INSERT_TAIL(&allprison, pr, pr_list); + + pr->pr_parent = ppr; LIST_INSERT_HEAD(&ppr->pr_children, pr, pr_sibling); for (tpr = ppr; tpr != NULL; tpr = tpr->pr_parent) tpr->pr_childcount++; - pr->pr_parent = ppr; - pr->pr_id = jid; - /* Set some default values, and inherit some from the parent. */ if (namelc == NULL) namelc = ""; @@ -1913,6 +1907,70 @@ kern_jail_set(struct thread *td, struct uio *optuio, int flags) return (error); } +/* + * Find the next available prison ID. Return the ID on success, or zero + * on failure. Also set a pointer to the allprison list entry the prison + * should be inserted before. + */ +static int +get_next_prid(struct prison **insprp) +{ + struct prison *inspr; + int jid, maxid; + + jid = lastprid % JAIL_MAX + 1; + if (TAILQ_EMPTY(&allprison) || + TAILQ_LAST(&allprison, prisonlist)->pr_id < jid) { + /* + * A common case is for all jails to be implicitly numbered, + * which means they'll go on the end of the list, at least + * for the first JAIL_MAX times. + */ + inspr = NULL; + } else { + /* + * Take two passes through the allprison list: first starting + * with the proposed jid, then ending with it. + */ + for (maxid = JAIL_MAX; maxid != 0; ) { + TAILQ_FOREACH(inspr, &allprison, pr_list) { + if (inspr->pr_id < jid) + continue; + if (inspr->pr_id > jid || inspr->pr_ref == 0) { + /* + * Found an opening. This may be a gap + * in the list, or a dead jail with the + * same ID. + */ + maxid = 0; + break; + } + if (++jid > maxid) { + if (lastprid == maxid || lastprid == 0) + { + /* + * The entire legal range + * has been traversed + */ + return 0; + } + /* Try again from the start. */ + jid = 1; + maxid = lastprid; + break; + } + } + if (inspr == NULL) { + /* Found room at the end of the list. */ + break; + } + } + } + *insprp = inspr; + lastprid = jid; + return (jid); +} + /* * struct jail_get_args { * struct iovec *iovp; @@ -2453,8 +2511,15 @@ prison_find(int prid) mtx_lock(&pr->pr_mtx); if (pr->pr_ref > 0) return (pr); + /* + * Any active prison with the same ID would have + * been inserted before a dead one. + */ mtx_unlock(&pr->pr_mtx); + break; } + if (pr->pr_id > prid) + break; } return (NULL); }