aboutsummaryrefslogtreecommitdiff
path: root/sys/netinet
diff options
context:
space:
mode:
authorMarko Zec <zec@FreeBSD.org>2021-09-20 04:30:45 +0000
committerMarko Zec <zec@FreeBSD.org>2021-09-20 04:30:45 +0000
commit2ac039f7be620f692a3a086f35a51f1a0b6b03d2 (patch)
tree17c2593a843e56f4ea26e503845e47df2309bc42 /sys/netinet
parent5a01dea7e8c9640605e5731a9fc7f600c07ace61 (diff)
downloadsrc-2ac039f7be620f692a3a086f35a51f1a0b6b03d2.tar.gz
src-2ac039f7be620f692a3a086f35a51f1a0b6b03d2.zip
[fib_algo][dxr] Merge adjacent empty range table chunks.
MFC after: 3 days
Diffstat (limited to 'sys/netinet')
-rw-r--r--sys/netinet/in_fib_dxr.c60
1 files 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