[Babel-users] 64k routes, bird, babel rfc, rtod, etc

[Dave Taht]

for the record - I am testing on openwrt: mips (wndr3800), mipsel
(edgerouterx), arm (dual core A15), APU2 (low end amd x86), , and
periodically a couple nanostation or picostations that are lying
around. Got cross compilation for any given version kind of automated
now. It's all openwrt 18.6 + builds of babel

on ubuntu 16, is a intel quad core atom, core i3, 1 12 core olde xeons
on ubuntu 18 1 12 core xeon, 1 apu2

Anyway...

The last major place where babeld goes asymptotic is when you have a
lot of announcements, retractions and other shifts of metrics going
on. There's a linked list over in resend.c that gets scanned, and
rescanned, a lot, and that shows up in a gprof when you have that
level of churn going on and having that cpu get bloated causes carnage
elsewhere.

It didn't seem like the route_stream idea or periodic sorting would
help here, but a semi-permanent structure. I first tried rbtrees
(which worked well, but deletion was a PITA, I can put that version up
if someone wants it), then I reached for an old standby, the uthash
file which supports O(1) hash lookups, O(1) deletion (from a doubly
linked list), and other stuff (aside from the hash cost) that makes it
really fast....

The result in resend.c looks kind of pretty, IMHO

https://github.com/dtaht/babeld-hacking/blob/5856c729e3f883e043889a1b8a3caa407de54674/resend.c

And even the uthash.h is not too hard on the eyes. (bird has a *nice*
hash lib, too)

The nlogn performance improvement for xroute imports was really
helpful (aside from the redistribute bug), but when you're churning,
the uthashed resend.c kept things much more sane on top of that.

with the nlogn + uthash, well, I got to ~64k routes... or 16k with
lots of intentional churn.

So: If anyone wants to try it: This is a merge of what I just tested
over the past week on top of the nlogn branch:

https://github.com/dtaht/babeld-hacking/commits/nlogn-uthash-merge

which just has the uthash of resend.c in it.

this is my ongoing branch effort (on top of rfc6126bis) to make all of
the babel structures hashable.

https://github.com/dtaht/babeld-hacking/commits/uthash

which I think might have potential in a post "dev" "datum" structure
world in particular. I started on it with the idea that if everything
ended up hashed, and quickly sortable, and immediately deletable...
life might be better. I have to admire the route_stream idea and how
parsimonious babel currently is with memory, but with each malloc
pointer eating? 24 bytes on 64 bit arches? (I don't remember) + the
typical size of a babel structure + uthash (54 bytes), it didn't seem
like it would hurt all that much... and if you only hash once
(post-datum branch)... and join on that hash value.... oooooh..... :)

Still...

A) I don't like scanning for garbage whilst otherwise really busy (me
and GC have a lot of frustrated history together in the realtime
world). timerwheels...
B) still want to get the hellos in and out no matter what else is going on...

I have had the most time to fiddle with babeld the past month in
years, and I have to say, I really admire it. So much functionality in
so little code.