git: c5981a8130e2 - stable/13 - [fib_algo][dxr] Merge adjacent empty range table chunks.

[Marko Zec]

The branch stable/13 has been updated by zec:

URL: https://cgit.FreeBSD.org/src/commit/?id=c5981a8130e259a21c29e8c0928aced0b0e17fec

commit c5981a8130e259a21c29e8c0928aced0b0e17fec
Author:     Marko Zec <zec at FreeBSD.org>
AuthorDate: 2021-09-20 04:30:45 +0000
Commit:     Marko Zec <zec at FreeBSD.org>
CommitDate: 2021-09-29 20:40:01 +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