[quagga-dev 6582] bgp_aspatch.c: aspath_make_str_count()

Chris Caputo ccaputo at alt.net
Mon May 11 08:19:49 BST 2009


For the aspath_make_str_count function, do you all like the static 
buffer/exact strdup() method of below?  Or should we use this earlier 
patch I sent against my own patch which is now in the tree:

  http://lists.quagga.net/pipermail/quagga-dev/2009-April/006541.html

  - (Fix egregious realloc() while in while loop inefficiency.  This code 
    has been running on my two production routers since 4/30.)

Or?

I like the below but the downside is that it is not thread-safe.  Is that 
a concern long term?

If the below is preferred, I am happy to test & produce a diff against 
current git based on the below concept.

Thoughts?

Chris

---------- Forwarded message ----------
Date: Mon, 4 May 2009 23:14:22 +0100
From: Charles Briscoe-Smith <charles-quagga at briscoe-smith.org.uk>
To: paul at jakma.org
Cc: Quagga Users <quagga-users at lists.quagga.net>
Subject: [quagga-users 10627] Re: Quagga segfaulting

On Mon, May 04, 2009 at 06:20:31PM +0100, paul at jakma.org wrote:
> Sure, but it's a known quantity, and it doesn't change - which is 
> kind on the memory allocator. Realloc is a bit slower, and the 
> differing allocations can lead to fragmentation (though, demand-sized 
> realloc of the original is of course much worse for this than the 
> multiplier realloc).
> 
> That said, I don't know which way is better, and code simplicity 
> possibly is a more important factor. So we'll see.

I would like to suggest an approach something like the below patch.

The idea is to keep a single buffer around permanently and reuse it
each time.  It will rarely need realloc()ing and most of the time
strings will just be built in the existing buffer and then strdup()ed.
So it should be pretty space-efficient while doing just the one malloc()
on the vast majority of calls as the buffer will normally be big enough
already.  An alternative might be, instead of the final XSTRDUP() call,
to round up the string length to the next multiple of (say) 32, malloc()
that size and strcpy() into it, in order to have fewer different chunk
sizes floating around.

(It's against 0.99.11 because I'm not familiar with modern SCC systems;
sorry.  I've briefly tried compiling it, but not testing; sorry - my aim
was mainly just to suggest an approach I thought might help.  It's not
thread-safe because as far as I can see from a quick skim through the
code, quagga uses its own threading code which looks like it's based
on the usual select()-and-call-stuff-from-a-queue pattern, so there
would be no chance of pre-empting a thread in the middle of a function.
Plus I don't know how to make it thread-safe, not having ever done much
with threads!  It's also been many years since I did any useful amount
of C, so forgive me if my code's particularly naive.  Oh, and I didn't
do that conditionalising on sizeof() thing that you suggested either.)

Caveats aside, I hope this helps.

-- 
Charles Briscoe-Smith
Servology
150 Westway, LONDON, SW20 9LS
Phone: 020 8542 0505  Mobile: 07749 859527


--- bgp_aspath.c.orig	2008-09-05 15:27:26.000000000 +0100
+++ bgp_aspath.c	2009-05-04 23:09:21.000000000 +0100
@@ -522,38 +522,38 @@
 }
 
 /* Convert aspath structure to string expression. */
+/* Not thread-safe due to cached buffer. */
 static char *
 aspath_make_str_count (struct aspath *as)
 {
+  static int str_size = 0;
+  static char *str_buf = NULL;
+
   struct assegment *seg;
-  int str_size;
   int len = 0;
-  char *str_buf;
+
+  if (str_buf == NULL)
+    {
+      /* We keep this buffer for the life of bgpd, realloc()ing it
+       * longer when needed.  We construct ASPATH strings in the buffer,
+       * then strdup() them for the client.  We're unlikely to need to
+       * expand this buffer more than 3-4 times per bgpd, given typical
+       * ASPATH lengths, so this should save a lot of realloc()s and/or
+       * oversized malloc()s.
+       */
+      str_size = ASPATH_STR_DEFAULT_LEN;
+      str_buf = XMALLOC (MTYPE_AS_STR, len);
+    }
 
   /* Empty aspath. */
   if (!as->segments)
     {
-      str_buf = XMALLOC (MTYPE_AS_STR, 1);
       str_buf[0] = '\0';
-      return str_buf;
+      return XSTRDUP(MTYPE_AS_STR, str_buf);
     }
   
   seg = as->segments;
   
-  /* ASN takes 5 chars at least, plus seperator, see below.
-   * If there is one differing segment type, we need an additional
-   * 2 chars for segment delimiters, and the final '\0'.
-   * Hopefully this is large enough to avoid hitting the realloc
-   * code below for most common sequences.
-   *
-   * With 32bit ASNs, this range will increase, but only worth changing
-   * once there are significant numbers of ASN >= 100000
-   */
-#define ASN_STR_LEN (5 + 1)
-  str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1,
-                  ASPATH_STR_DEFAULT_LEN);
-  str_buf = XMALLOC (MTYPE_AS_STR, str_size);
-
   while (seg)
     {
       int i;
@@ -571,23 +571,21 @@
             seperator = ' ';
             break;
           default:
-            XFREE (MTYPE_AS_STR, str_buf);
             return NULL;
         }
       
-      /* We might need to increase str_buf, particularly if path has
-       * differing segments types, our initial guesstimate above will
-       * have been wrong.  need 5 chars for ASN, a seperator each and
-       * potentially two segment delimiters, plus a space between each
-       * segment and trailing zero.
+      /* We might need to increase str_buf.  need up to 10 chars and
+       * a separator per ASN and potentially two segment delimiters,
+       * plus a space between each segment and trailing zero.
        *
-       * This may need to revised if/when significant numbers of
-       * ASNs >= 100000 are assigned and in-use on the internet...
+       * ASN_STR_LEN will need to be revised if/when AS numbers of 10^10
+       * or more (11 or more decimal digits) are made possible.
        */
+#define ASN_STR_LEN (10 + 1)
 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
       if ( (len + SEGMENT_STR_LEN(seg)) > str_size)
         {
-          str_size = len + SEGMENT_STR_LEN(seg);
+          str_size = MAX (len + SEGMENT_STR_LEN(seg), str_size*2);
           str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
         }
 #undef ASN_STR_LEN
@@ -620,7 +618,7 @@
   
   str_buf[len] = '\0';
 
-  return str_buf;
+  return XSTRDUP (MTYPE_AS_STR, str_buf);
 }
 
 static void
--- END OF PATCH ---



More information about the Quagga-dev mailing list