From owner-dev-commits-src-all@freebsd.org Mon Sep 20 04:37:15 2021 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 AAD5F677820; Mon, 20 Sep 2021 04:37:15 +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 4HCWxR4Bsmz3Phl; Mon, 20 Sep 2021 04:37:15 +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 6C3AE1CB8; Mon, 20 Sep 2021 04:37:15 +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 18K4bFWg054950; Mon, 20 Sep 2021 04:37:15 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 18K4bFeH054949; Mon, 20 Sep 2021 04:37:15 GMT (envelope-from git) Date: Mon, 20 Sep 2021 04:37:15 GMT Message-Id: <202109200437.18K4bFeH054949@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Marko Zec Subject: git: 2ac039f7be62 - main - [fib_algo][dxr] Merge adjacent empty range table chunks. MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: zec X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 2ac039f7be620f692a3a086f35a51f1a0b6b03d2 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: Mon, 20 Sep 2021 04:37:15 -0000 The branch main has been updated by zec: URL: https://cgit.FreeBSD.org/src/commit/?id=2ac039f7be620f692a3a086f35a51f1a0b6b03d2 commit 2ac039f7be620f692a3a086f35a51f1a0b6b03d2 Author: Marko Zec AuthorDate: 2021-09-20 04:30:45 +0000 Commit: Marko Zec CommitDate: 2021-09-20 04:30:45 +0000 [fib_algo][dxr] Merge adjacent empty range table chunks. MFC after: 3 days --- sys/netinet/in_fib_dxr.c | 60 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 45 insertions(+), 15 deletions(-) diff --git a/sys/netinet/in_fib_dxr.c b/sys/netinet/in_fib_dxr.c index 3aa357cadedc..c4f42abdda27 100644 --- a/sys/netinet/in_fib_dxr.c +++ b/sys/netinet/in_fib_dxr.c @@ -418,14 +418,15 @@ chunk_ref(struct dxr_aux *da, uint32_t chunk) fdesc->base = cdp->cd_base; da->rtbl_top -= size; da->unused_chunks_cnt--; - if (cdp->cd_max_size > size + 1) { + if (cdp->cd_max_size > size) { /* Split the range in two, need a new descriptor */ empty_cdp = uma_zalloc(chunk_zone, M_NOWAIT); if (empty_cdp == NULL) return (1); + empty_cdp->cd_cur_size = 0; empty_cdp->cd_max_size = cdp->cd_max_size - size; empty_cdp->cd_base = cdp->cd_base + size; - LIST_INSERT_AFTER(cdp, empty_cdp, cd_all_le); + LIST_INSERT_BEFORE(cdp, empty_cdp, cd_all_le); LIST_INSERT_AFTER(cdp, empty_cdp, cd_hash_le); da->all_chunks_cnt++; da->unused_chunks_cnt++; @@ -433,7 +434,7 @@ chunk_ref(struct dxr_aux *da, uint32_t chunk) } LIST_REMOVE(cdp, cd_hash_le); } else { - /* Alloc a new descriptor */ + /* Alloc a new descriptor at the top of the heap*/ cdp = uma_zalloc(chunk_zone, M_NOWAIT); if (cdp == NULL) return (1); @@ -441,6 +442,8 @@ chunk_ref(struct dxr_aux *da, uint32_t chunk) cdp->cd_base = fdesc->base; LIST_INSERT_HEAD(&da->all_chunks, cdp, cd_all_le); da->all_chunks_cnt++; + KASSERT(cdp->cd_base + cdp->cd_max_size == da->rtbl_top, + ("dxr: %s %d", __FUNCTION__, __LINE__)); } cdp->cd_hash = hash; @@ -473,12 +476,12 @@ static void chunk_unref(struct dxr_aux *da, uint32_t chunk) { struct direct_entry *fdesc = &da->direct_tbl[chunk]; - struct chunk_desc *cdp; + struct chunk_desc *cdp, *cdp2; uint32_t base = fdesc->base; uint32_t size = chunk_size(da, fdesc); uint32_t hash = chunk_hash(da, fdesc); - /* Find an existing descriptor */ + /* Find the corresponding descriptor */ LIST_FOREACH(cdp, &da->chunk_hashtbl[hash & CHUNK_HASH_MASK], cd_hash_le) if (cdp->cd_hash == hash && cdp->cd_cur_size == size && @@ -492,23 +495,50 @@ chunk_unref(struct dxr_aux *da, uint32_t chunk) LIST_REMOVE(cdp, cd_hash_le); da->unused_chunks_cnt++; - if (cdp->cd_base + cdp->cd_max_size != da->rtbl_top) { - LIST_INSERT_HEAD(&da->unused_chunks, cdp, cd_hash_le); - return; + cdp->cd_cur_size = 0; + + /* Attempt to merge with the preceding chunk, if empty */ + cdp2 = LIST_NEXT(cdp, cd_all_le); + if (cdp2 != NULL && cdp2->cd_cur_size == 0) { + KASSERT(cdp2->cd_base + cdp2->cd_max_size == cdp->cd_base, + ("dxr: %s %d", __FUNCTION__, __LINE__)); + LIST_REMOVE(cdp, cd_all_le); + da->all_chunks_cnt--; + LIST_REMOVE(cdp2, cd_hash_le); + da->unused_chunks_cnt--; + cdp2->cd_max_size += cdp->cd_max_size; + uma_zfree(chunk_zone, cdp); + cdp = cdp2; } - do { + /* Attempt to merge with the subsequent chunk, if empty */ + cdp2 = LIST_PREV(cdp, &da->all_chunks, chunk_desc, cd_all_le); + if (cdp2 != NULL && cdp2->cd_cur_size == 0) { + KASSERT(cdp->cd_base + cdp->cd_max_size == cdp2->cd_base, + ("dxr: %s %d", __FUNCTION__, __LINE__)); + LIST_REMOVE(cdp, cd_all_le); + da->all_chunks_cnt--; + LIST_REMOVE(cdp2, cd_hash_le); + da->unused_chunks_cnt--; + cdp2->cd_max_size += cdp->cd_max_size; + cdp2->cd_base = cdp->cd_base; + uma_zfree(chunk_zone, cdp); + cdp = cdp2; + } + + if (cdp->cd_base + cdp->cd_max_size == da->rtbl_top) { + /* Free the chunk on the top of the range heap, trim the heap */ + KASSERT(cdp == LIST_FIRST(&da->all_chunks), + ("dxr: %s %d", __FUNCTION__, __LINE__)); da->all_chunks_cnt--; da->unused_chunks_cnt--; da->rtbl_top -= cdp->cd_max_size; LIST_REMOVE(cdp, cd_all_le); uma_zfree(chunk_zone, cdp); - LIST_FOREACH(cdp, &da->unused_chunks, cd_hash_le) - if (cdp->cd_base + cdp->cd_max_size == da->rtbl_top) { - LIST_REMOVE(cdp, cd_hash_le); - break; - } - } while (cdp != NULL); + return; + } + + LIST_INSERT_HEAD(&da->unused_chunks, cdp, cd_hash_le); } #ifdef DXR2