1 files changed, 100 insertions, 0 deletions
diff --git a/net/bird3/files/patch-13-allocate-normalization-buckets b/net/bird3/files/patch-13-allocate-normalization-buckets
new file mode 100644
index 000000000000..60ff582d71c5
--- /dev/null
+++ b/net/bird3/files/patch-13-allocate-normalization-buckets
@@ -0,0 +1,100 @@
+From c3c12e1b4ff908211b156a182a5027f2b11b0709 Mon Sep 17 00:00:00 2001
+From: Maria Matejka <mq@ucw.cz>
+Date: Tue, 24 Dec 2024 16:16:55 +0100
+Subject: [PATCH] Allocate the normalization buckets on stack
+
+Even though allocating from tmp_linpool is quite cheap,
+it isn't cheap when the block is larger than a page, which is the case here.
+Instead, we now allocate just the result which typically fits in a page,
+avoiding a necessity of a malloc().
+---
+ nest/rt-attr.c | 37 ++++++++++++++++++++++++-------------
+ 1 file changed, 24 insertions(+), 13 deletions(-)
+
+diff --git a/nest/rt-attr.c b/nest/rt-attr.c
+index 8d651efb2..9d5e10980 100644
+--- nest/rt-attr.c
++++ nest/rt-attr.c
+@@ -967,8 +967,8 @@ ea_list_size(ea_list *o)
+  * and creates the final structure useful for storage or fast searching.
+  * The method is a bucket sort.
+  *
+- * Returns the final ea_list with some excess memory at the end,
+- * allocated from the tmp_linpool. The adata is linked from the original places.
++ * Returns the final ea_list allocated from the tmp_linpool.
++ * The adata is linked from the original places.
+  */
+ ea_list *
+ ea_normalize(ea_list *e, u32 upto)
+@@ -976,21 +976,17 @@ ea_normalize(ea_list *e, u32 upto)
+   /* We expect some work to be actually needed. */
+   ASSERT_DIE(!BIT32_TEST(&upto, e->stored));
+ 
+-  /* Allocate the output */
+-  ea_list *out = tmp_allocz(ea_class_max * sizeof(eattr) + sizeof(ea_list));
+-  *out = (ea_list) {
+-    .flags = EALF_SORTED,
+-  };
+-
++  /* Allocate the buckets locally */
++  eattr *buckets = allocz(ea_class_max * sizeof(eattr));
+   uint min_id = ~0, max_id = 0;
+ 
+-  eattr *buckets = out->attrs;
++  ea_list *next = NULL;
+ 
+   /* Walk the attribute lists, one after another. */
+   for (; e; e = e->next)
+   {
+-    if (!out->next && BIT32_TEST(&upto, e->stored))
+-      out->next = e;
++    if (!next && BIT32_TEST(&upto, e->stored))
++      next = e;
+ 
+     for (int i = 0; i < e->count; i++)
+     {
+@@ -1000,7 +996,7 @@ ea_normalize(ea_list *e, u32 upto)
+       if (id < min_id)
+ 	min_id = id;
+ 
+-      if (out->next)
++      if (next)
+       {
+ 	/* Underlay: check whether the value is duplicate */
+ 	if (buckets[id].id && buckets[id].fresh)
+@@ -1026,6 +1022,18 @@ ea_normalize(ea_list *e, u32 upto)
+     }
+   }
+ 
++  /* Find out how big the output actually is. */
++  uint len = 0;
++  for (uint id = min_id; id <= max_id; id++)
++    if (buckets[id].id && !(buckets[id].undef && buckets[id].fresh))
++      len++;
++
++  ea_list *out = tmp_alloc(sizeof(ea_list) + len * sizeof(eattr));
++  *out = (ea_list) {
++    .flags = EALF_SORTED,
++    .next = next,
++  };
++
+   /* And now we just walk the list from beginning to end and collect
+    * everything to the beginning of the list.
+    * Walking just that part which is inhabited for sure. */
+@@ -1044,9 +1052,12 @@ ea_normalize(ea_list *e, u32 upto)
+ 
+     /* Move the attribute to the beginning */
+     ASSERT_DIE(out->count < id);
+-    buckets[out->count++] = buckets[id];
++    ASSERT_DIE(out->count < len);
++    out->attrs[out->count++] = buckets[id];
+   }
+ 
++  ASSERT_DIE(out->count == len);
++
+   /* We want to bisect only if the list is long enough */
+   if (out->count > 5)
+     out->flags |= EALF_BISECT;
+-- 
+GitLab
+