Date: Mon, 20 Sep 2021 04:37:15 GMT From: Marko Zec <zec@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 2ac039f7be62 - main - [fib_algo][dxr] Merge adjacent empty range table chunks. Message-ID: <202109200437.18K4bFeH054949@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by zec: URL: https://cgit.FreeBSD.org/src/commit/?id=2ac039f7be620f692a3a086f35a51f1a0b6b03d2 commit 2ac039f7be620f692a3a086f35a51f1a0b6b03d2 Author: Marko Zec <zec@FreeBSD.org> AuthorDate: 2021-09-20 04:30:45 +0000 Commit: Marko Zec <zec@FreeBSD.org> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202109200437.18K4bFeH054949>