Properly handle references for nexthops and labels in filterset_copy()

Up until recently filterset_copy() was only used in the parent process
where none of those references exist but by using filterset_copy() in
the RDE to populate per-peer output filters the code needs to handle
such references. Without this rules like 'match to any set nexthop X'
will cause internal corruption on config reloads and session resets.
Bug report from Marko Cupac (marko.cupac (at) mimar.rs)
OK tb@

Implement a way to announce flowspec rules without hitting Adj-RIB-In
and Loc-RIB. Flowspec objects are collected in a single flowrib RIB
and then directly distributed into the various Adj-RIB-Outs.
For this to work add a bypass in the filter logic (flowspec AFI/SAFI
are currently accepted without any rule). The filter language lacks
a way to allow prefixes based on AFI/SAFI which is the minimum needed.
OK tb@

branches: 1.134.4;
Compile the output filter rules into per peer filter rules.

especially on route-servers the output filters are in the hot path so
reducing the number of rules to check has a big impact. I have seen a
25% to 30% speedup in my big IXP testbench.
The output ruleset is applied and copied for each peer during config reload
and when a peer is initially added.
OK tb@

Implement filter and control message matching for ASAP.

This adds avs (ASPA validation state) which can be 'unknown', 'valid'
or 'invalid'. It behaves similar to ovs but the ASPA validation state
of paths from iBGP sessions is 'unknown' and the role of the ebgp session
is important to get the right validation state.

OK tb@

Implement ASPA validation and reload logic on ASPA set changes.

For this use the validation state (vstate) in struct prefix and
struct filterstate to store both the ASPA and ROA validity.
Introduce helper functions to set and get the various states for
struct prefix and make sure struct filterstate is also setup properly.
Change the ASPA state in rde_aspath to be AFI/AID and role independent
by storing all 4 possible outcomes. Also add a ASPA generation count
which is used to update the rde_aspath ASPA state cache on reloads.
Rework the rde_aspa.c code to be AFI/AID and role independent. Doing
this for roles is trivial but AFI switch goes deep and is so unnecessary.
The reload is combined with the ROA reload logic and renamed to RPKI
softreload.

OK tb@

Split rde_filterstate_prep() into three functions.
- rde_filterstate_init(): initialize a filterstate to default values
- rde_filterstate_copy(): copy from a filterstate into a new state object
- rde_filterstate_prep(): set filtersate based on prefix passed as argument.

This makes the code a bit easier to read.
OK tb@

Add the validation state to the filterstate struct.
Removes vstate argument from rde_filter().
Rename prefix_vstate() to prefix_roa_vstate().
OK tb@

whitespace found during a read-thru; ok claudio

Implement a max communities filter match

When max-communities X is set on a filterrule the filter will match when
more than X communities are present in the path. In other words
max-communities 0 means no communities are allowed and max-communities 3
limits it up to 3 communities.
There is max-communities, max-ext-communities and max-large-communities
for each of the 3 community attributes. These three max checks can be used
together.
OK tb@ job@

Switch from u_intX_t types to stdint.h uintX_t. Mostly mechanical with
a few reindents.
OK florian@ tb@

Implement IMSG_CTL_SHOW_SET to get information about roa-set, as-sets and
prefix-sets loaded into the RDE. For now only the number of prefixes or
asnumbers are shown plus the time since the last change was done to the table.
OK benno@

rework the overflow checks for the various relative metric adjustments.
This test no longer depends on specific overflow behaviour.
OK millert@

Refactor the filterset handling of nexthops. Instead of depending on
bgpd_process and changing the behaviour that way add a new filterset
type ACTION_SET_NEXTHOP_REF which is used when the nexthop reference
of the union is used. Adjust the RDE to convert ACTION_SET_NEXTHOP to
ACTION_SET_NEXTHOP_REF when receiving the filtersets.
OK benno@

Rename copy_filterset() to filterset_copy() and move it to rde_filter.c
where functions like filterset_move() live. Also initialize the dest
TAILQ in filterset_copy() as it is done in filterset_move().
OK benno@ phessler@

Instead of passing a struct prefix pointer to rde_filter() pass the 4 values
prefix_peer, prefix_vstate and prefix/prefixlen to the function. This removes
some ugly hacks in cases where the prefix was not available.
Also adjust the order of arguments of rde_attr_set() to match rde_filter().
OK benno@

Unify the way object in the RDE are reference counted. The affected
structures are pt_entry, rde_aspath, rde_communities, and nexthop.
The functions are always called *_ref and *_unref also the behaviour
when the last reference is removed is unified and now the object is
removed inside of the unref function. The actual bean-counting is not
modified by this diff.
OK benno@

Add a direct pointer from struct prefix to struct pt_entry.
This changes makes it possible to not use the struct rib_entry pointer
which will be used to optimize the Adj-RIB-Out.
Also adjust pt_ref() and pt_unref() so that the code can be written
a bit more compact. Also prefix_cmp() no longer needs to go via
rib_compare() and calls pt_prefix_cmp() directly.
OK phessler@

Completley rewrite the community matching and handling code. All community
attributes are put into a new data structure when parsing the UPDATE.
The filter code can quickly lookup and modify this data structure.
When creating an UPDATE the data is put back into wire format.
Setups using a lot of communities benefit a lot from this.
Input and OK benno@

Neither rde_apply_set() nor rde_filter() are called with a NULL state so
remove some unneeded == NULL checks.
OK benno@

Implement as-override, a feature where the neighbor AS is replaced by the
local AS in AS paths. This is sometimes needed in bigger transport networks
where private AS numbers are used in multiple locations.
The implementation is done using a filterset which modifies the AS path -
somewhat inspired by the set attribute code. Setting as-override yes will add
match from <neighbor> set { as-override }
to the start of the filter rules. Since this is filters the Adj-RIB-In still
holds the original path and so reloads changing the setting just work.
With and OK markus@

Fold ext-communities into filter_community so that bgpd can match
multiple ext-communities at the same time as well. Additionally this fixes
parsing some of the ext-community types. Now all communities are handled
by one common struct.
OK benno@ plus some input from denis@

Refactor aspath code a bit. Move cached source_as (for origin validation)
into struct aspath and pass that struct to aspath_match().
OK denis@

Start reworking community handling. Merge standard communities and large
communities into one filter_community struct and allow it that more then
one community can be used in filter rules (currently up to 3).
Also rework the code handling bgpctl show rib commands. The special IMSG
types for the various filters are gone and the code is in general simpler.
OK job@, phessler@

Remove an unneeded union wrapping the skipsteps pointer.
OK phessler@

Implement origin validation in bgpd. This introduces two new tables, the
roa-set for RPKI based origin validation and a origin-set which allows to
lookup a source-as / prefix pair.
For RPKI a config can be built like this:
roa-set {
165.254.255.0/24 source-as 15562
193.0.0.0/21 maxlen 24 source-as 3333
}
deny from any ovs invalid
match from any ovs valid set community local-as:42
match from any ovs not-found set community local-as:43
Origin sets are similar but only match when the source-as / prefix pair is
valid.
match from any origin-set ARINDB set community local-as:44
Committing this now so that further work can be done in tree.
OK benno@, job@

Rename AS_NONE to AS_UNDEF, AS_NONE will be reused for a different purpose
soon. OK compiler and grep

Switching bgpd to a default deny policy had one bad side-effect. Some
withdraw were suddenly filtered out because the filter ran into the
default deny. So for this case (state == NULL) change action to default
allow. This bug was haunting bgpd for a while now causing prefixes to be
stuck for no obvious reason.
OK benno@, sthen@

Indent issue. No functional change

Split up as_set into a set_table and an as_set. The first is what does
the lookup and will now also be used in roa-set tries. The as_set is glue
to add the name and dirty flag. Add an accessor to get the set data so
that the imsg sending and printing can be moved into the right places.
This is done mainly because roa-sets need similar but slightly different
versions and making the code more generic is the best way fixing this.
OK benno@

whitespace cleanup, ok claudio@

use TAILQ_CONCAT in filterset_move(). ok claudio@

implement or-longer filter op for prefix-sets. Allows one two write rules like
deny from any prefix-set mynetworks or-longer
ok claudio, feature discussed with job and deraadt

fix badly broken reload of filter rules that use prefix-sets. debugged
and fixed with/by claudio@

Implement a fast presix-set lookup. This magic trie is able to match a
prefix addr/plen to a prefix-set spec addr/plen prefixlen min - max (a
prefix including prefixlen range). Every addr/plen pair is a node in the
trie and the prefixlen is added as a bitmask to those nodes.
For the lookup the any match is OK, there is no need to do longest or
best prefix matching.
Inspiration for this solution comes from the way bird implements this
which was done by Ondrej Zajicek santiago (at) crfreenet.org
OK benno@

Implement as-set a fast lookup table to be used instead of long list of
AS numbers in source-as, AS and transit-as filterstatements. These table
use bsearch to quickly verify if an AS is in the set or not.
The filter syntax is not fully set in stone yet.
OK denis@ benno@ and previously OK deraadt@

Implement most prefixlen operations as OP_RANGE (prefixlen A - B).
Simplify the RDE logic this way and make it possible to load such ranges
into a much faster lookup trie for prefix-sets.
When printing the config bgpd tries to use the nices way to express the rule:
e.g. match from any prefix 18.0.0.0/8 prefixlen 8 - 32
becomes match from any prefix 18.0.0.0/8 or-longer
Apart from that there is no user visible change because of this.
OK sthen@

Change the way as_compare() and aspath_match() handle 'neighbor-as'. Instead
of doing the condition before calling aspath_match() just pass the neighbor-as
down to as_compare() which then has all needed data for the lookup. While
doing this also remove one of the as fields in struct filter_as since the
min/max fields can be reused for unary operations.
OK denis@ phessler@

Move nexthop and nexthop flags from the rde_aspath to struct prefix.
struct prefix will be slowly becomming the hub of the rib.
OK phessler@ job@

Split out the rule skipping logic into own function and by doing so ensure
that both filter lists are treated the same way. This fixes an inconsistency
with ibgp and ebgp filters as used in the example config.
OK benno@ sthen@

Move nexthop into struct filterstate (including nexthop flags) and use
them whereever possible. In some places (path_update, softreconfig_out
handler) the nexthop state is temporarily folded back into the rde_aspath.
Tested and OK benno@

Use struct filterstate in rde_update_dispatch() and pass it down to
functions like rde_update_update and path_update. This will allow to
move more pointers from rde_aspath to the prefix.
Looks good benno@

Introduce a struct filterstate and pass this to rde_filter instead of
passing the asp. This is no longer using asp_get() and should be therefor
be a bit lighter. Will also allow to put more stuff into the state.
OK denis@ sthen@

Prepare the ground for allowing temporary aspath object living on the stack.
To do this path_copy() gets a second argument (dst, src) and a new function
path_prep() is introduced to initialize an aspath object. The current
path_copy() usage is replaced with path_copy(path_get(), asp) which does
the same. Additionally some const where added to the *_copy functions to
make it more obvious which is the source and target. Also the pftable_ref()
and rtlabel_ref() functions return now the id instead of void.
OK sthen@

Remove rde_aspath pointer from rde_filter since that argument can be fetched
from the prefix instead. While there also switch to prefix_peer from asp->peer
in rde_dump_rib_as(). Makes the code easier overall.

Instead of passing the rde_aspath to nexthop_modify() pass pointers to
the nexthop and the flags.

Pass a struct prefix to rde_filter and remove some of the arguments which
are now fetched from struct prefix. Currently some trickery is needed
for export default-route but this will get better once Adj-RIB-Out comes.
OK benno@

Move rde_test_prefix() to a place where it makes more sense. No functional
change.

Properly start reference counting struct nexthop. This removes the need for
some ugly workaround to make sure nexthop objects don't disapear while
still being referenced. During initial lookup of a nexthop a extra reference
is pulled but even that is now a bit cleaner than before.
Tested by job@, dennis@, benno@ OK job@ dennis@

Use correct function name in fatalx()

Deprecate announce (all|self|none|default-route)
The announce keyword was overloaded and confused a lot of operators, time
to clean it up and while there incorporate RFC8212 guideline for propagation.
- `announce all` is the new default but the default deny filter will
make sure that by default nothing is leaked
- `announce self` is no more and results in syntax error
- `announce none` is now `export none`
- `announce default-route` becomes `export default-route`
- the filters are switched to a default deny rule both incoming and outgoing

You most certainly need to adjust your config!

Best is to change the config in advance by using `announce all` explicitly on
all neighbors and adding `deny from any` and `deny to any` at the start of
your filters and adjust the rest of the filters to still produce the same
result. `bgpd -nv -f bgpd.conf ` and `bgpctl show rib out nei foo` are good
tools to verify the changes.
Lots of discussions with job@, deraadt@, sthen@
OK job@

claudio noted that this is an else case because we have either a
prefix or a prefix-set.

Add prefix-sets, lists of prefixes which can be used in place of a
prefix in a filter rule. Initial idea hashed out with job@ in Toronto.
This is WIP, i'm commiting it now so we can work on it in the tree.
ok florian@ claudio@

prefix check must be last because the prefixlen check does an immediate return.
This will be rewritten soon so just do the quick fix now.
Found and OK benno@

allow filter rules to be written that affect ibgp or ebgp neighbors

discussed with henning@
OK claudio@, benno@, job@

Allow OpenBGPD to selectively choose which local ASN to use per-peer.
This is intended to be used for ASN migrations, not for permanent use.

You MUST use filters to protect yourself from receiving your own routes.
There be dragons and grues.

OK claudio@ benno@

allow us to use 'local-as' in the filter language

"match in from any set community local-as:neighbor-as"

OK claudio@

sync log.c from relayd et al to bgpd.

there is still a little difference regarding handling of the verbosity
value that will be handled later.

ok claudio@ florian@

properly check if large-community was set before

reported by Job Snijders

Add support for draft-ietf-idr-large-community

Joint work with Job Snijders, many thanks!
OK benno@ deraadt@

Add operators =, !=, - (range), >< (exclsive range) to the as-path
filters (AS, peer-as, source-as, transit-as).

Add a use case (block illegal AS numbers) to the bgpd.conf example.

feedback from claudio, sthen, florian,
ok florian@ phessler@

Radically improve the performance of bgpd filters. Based on PF's skip
steps (and uses much of the same code).

In a torture test of ~600k prefix filters and 65k prefixes, convergance
time goes from 35 minutes to 30 seconds.

Many thanks to LONAP for providing a base configuration for torture
testing.

many discussions with claudio@, benno@, sthen@ and the rest of the bgpd crowd

OK sthen@ benno@

In all other cases of rde_filter_match() we ensure that asp is valid so
do it here as well.

Next round of config cleanup. Move various lists into the bgpd_config struct.
This is the next step to better split parsing and merging the config.
OK benno@

allow us to write rules that match directly on the peer AS

...
allow from AS 1 prefix 192.0.2.0/24
...

Also adjust the IRR ruleset output to include the declared peer AS,
instead of hoping they listed their neighbor IP address!


OK benno@
older version OK: claudio@ henning@

rename rde_free_filter() to filterlist_free() and start using it outside
of the RDE to free the filterlists. Also refactor common code to merge
filterlists into its own function. Makes the code look nicer.

fix the matching for filter rules of 'prefixlen = XX'

OK claudio@

Merge the prefix and prefixlen filter bits into one filter. Change the
filter expansion so that rules are grouped by prefixes last. The RDE will
then be able to optimize the rules into table lookups but that is a later
step. As additional goodies it is now possible to use inet and inet6
on their own and or-longer can be used as a shorthand for prefixlen >= len.
OK henning@ sthen@ florian@

Rewrite the internals of the RDE reload logic.
This is the first step to make bgpd reload non blocking in the RDE.
It also speeds up the reload time a fair bit in some cases (mainly if
you run with multiple RIBs and have larger filtersets) and it should also
fix a few edge cases on reloads.
Testing done by benno@, florian@ and sthen@ OK henning@ and benno@

Allow filtering based on the NEXTHOP attribute. This allows to build rules
like: allow from any nexthop neighbor (to allow only prefixes that use the
routers IP address as nexthop). Lots of testing, input and OK florian@

Move a few functions into util.c because bgpctl will need them soon.

On reload the filtersets attached to a network need to be moved to the
existing network element. First free the old filterset and then move
the new on top of it. This solves the reload issue with changing network
statements. OK henning@

Deny prefixes that have F_ATTR_PARSE_ERR set by default. Now they
will not leak into the Loc-RIB or other RIBs but act as withdraws.
The invalid prefixes would not been selected anyway but it is better
to keep them out of all RIBs but the Adj-RIB-In.

Implement two new filters, max-as-len and max-as-seq. The first is limiting
the length of an AS path (matches if the path is longer then the specified
lenght) the second matches when a sequence of the same AS number is longer
then the specified length).
max-as-len is good to protect crappy comercial bgp boxes from other crappy
comercial bgp boxes. max-as-seq was a feature request from SwissIX and maybe
EuroIX to find and filter prepends.
Additinal testing and OK sthen@

Allow neighbor-as in AS filter statements like:
match from any source-as neighbor-as set localpref 1000
OK henning@

Allow to filter for ext-community attributes. Currently only perfect matches
work but that's already better then nothing. OK sthen@

Merge rde_filter_community() with community_match() and kill a useless
indirection.

Implement "set ext-community [delete] subtype key:value" to set and delete
extended communities as specified in RFC 4360. No matching implemented yet
and stuff like * and neighbor-as are neither supported but will be soon.
Looks good henning & sthen, manpage fixed by jmc

Use an artificial address family id in struct bgpd_addr and almost everywhere
else. Adds conversion functions to map AFI/SAFI and the Unix AF_ values
from and into AID used in bgpd. This is needed to support things like MPLS
VPN and other upcomming changes that need to play a lot with AFI/SAFI pairs.
Mostly mechanical change, henning@ has no particular issues with this.
Must go in so that I can continue working.

support for set origin; based on an initial diff from
Sebastian Benoit <benoit-lists at fb12 dot de> who also tested this version
claudio ok

Implement the error handling as proposed in draft-ietf-idr-optional-transitive
for optional transitive attributes. In short if the partial bit is set on
an optional transitive attribute but the attribute fails validation ignore
the attribute or mark the path as ineligible instead of killing the session
with a NOTIFICATION. Tested, input and OK sthen, OK henning

Some preliminary filter magic to support multiple RIBs on the filters.
It is ugly but does the trick for now. Filters will be rewritten anyway.
The rib specifier only makes sense on from rules. e.g. deny rib OMG from any

Correct the logic when matching prefixes. This solves issues where IPv6
prefixes where matched on a simple deny from any prefix 0.0.0.0/0 rule.
OK henning@

Allow bgpd to delete more then one community per filter rule. Fixes PR5807
tested by Raphael Ho long time ago.

allow matching on communities using 0 in the AS part, that is in use.
that unfortunately means we cannot use 0 for "unset".
ok claudio

Various spelling fixes from Stuart Henderson.

Make bgpd 4-byte AS compatible. All internal representations of AS numbers
are now 4-byte instead of the old 2-byte numbers. The only exception are
communities because they can not be switched. The RDE will inflate and deflate
the ASPATH and AGGREGATOR attributes on demand and create the NEW_ASPATH and
NEW_AGGREGATOR field whenever needed. Both old and new stile sessions are
supported and can be mixed. Currently new stile sessions with the 4-byte AS
number capability turned on are only enabled if one of the AS numbers involved
is a 4-byte one.
This is based on an initial diff by Geoff Huston gih (at) apnic (dot) net
Cleanup, testing and bug-fixes by myself (via AS 3.10).
Currently mrt table dumps are producing incompatible output this will be fixed
afterwards -- this diff is already big enough.

"get it in if you think it is ready" henning@

Even better nexthop delete behaviour. Do not delete nexthop if they are used
by filter sets or if the nexthop is currently looked up. With this the
"nexthop_update: non-existent nexthop" warning should be history. OK henning@

Preload and pin nexthop used in filtersets so the are validiated when used.
This will fix problems with set nexthop on outgoing filters. Found by
gluk@ OK henning@

Remove filterset_names from bgpd.h and replace it with a function because
the table was already out of sync now. OK henning@

add "set nexthop self", force nexthop to be set to own address even with IBGP
requested & tested Falk Brockerhoff <fb@smartterra.de>, and tony sarendal
tested this too. claudio ok

Implement "set community delete 65001:*" and friends. This will remove
communities from the path attributes. Useful to make sure that the ones you
set later are set by a (evil) peer. OK henning@

If the aspath gets copied because it is modified use the copy for filter
matching. With this it is possible to make later filters depend on previous
filter changes -- e.g. via community attributes.

Doh! Fix stupid copy paste error. Setting the community type to the AS instead
of the more obvious type produces really funny errors and gives you some happy
hours of debugging.

Implement new special community "neighbor-as". neighbor-as is expanded on
the fly to the remote AS of the current neighbor. This can be used to
simplify rulesets in a dramatic way -- going from a script based nightmare
down to a handfull rules. jajajaja henning@

Check if filter changed on a per peer basis. This should speed up the
table run done later as many filter evaluations can be skipped.
From the softreconfig in tree. Looks good henning@

Copy AS path in rde_filter() on demand instead of doing it before calling
rde_filter(). Adapt path_update() to this change too. path_update() does
a path_copy before linking the rde_aspath into the RIB. Looks good Henning.

The attributes cache broke the set community filterset because community_set()
modified the attribute data directly and corrupted the cache by doing it.
It is no longer allowed to modify attributes via attr_optget() -> change
attr->data. Instead remove the old attribute from the aspath and then add
a new modifed one again. Included in this change is the removal of a "feature"
that allowed only one community per AS. If you had problems to add multiple
communities via filters then this was the problem. Looks good Henning.

Missing #include <limits.h>

even more spaces and tabs.

Implement filterset_equal() and rde_filter_equal(). Both return 1 if
the two passed filter(set)s are equal or 0 otherwise. rde_filter_equal()
has an additional argument dir to specify which direction should be considered.

Softreconfig out support. On config reload filter changes of outgoing rules
will propagte directly to the neighbors. There is no need to restart bgpd
in that case. Currently not optimal but a good start. "get it in" henning@

Switch from the per peer filter set list to a filter-only solution.
The default filter_sets are converted into match filter rules that get
evaluated first. Simplifies code massively -- mainly the config reload
part -- and makes softreconfig out a piece of cake. "get it in" henning@

Pass the correct peer to rde_apply_set(). rde_apply_set() needs to know
the peer where the prefix came from so that prepend-neighbor works.
Extend rde_filter() and make sure that the correct peer is passed.
Until now most cases resulted in a NULL peer causing a nasty crash that
was found by David Ulevitch. OK henning@

New function filterset_cmp() used two compare two struct filter_set for
equality. This function is a bit more complicated than a memcmp() because there
are types that need to be considered equal e.g. ACTION_SET_MED and
ACTION_SET_RELATIVE_MED. Also ACTION_SET_COMMUNITY and ACTION_SET_NEXTHOP
need some special care. OK henning@

More spaces

Switch filter_sets form SIMPLEQ to TAILQ, needed for upcomming stuff.

The newly introduced function filterset_free() existed already as
rde_free_set(), I just missed it when I was looking for it.
Kill rde_free_set() and use the more correct filterset_free() from now on.

Make the pftable filter set use the name2id "cache" like the route labels.
This saves 14 bytes per aspath. OK henning@

rtlabel support via filter sets. Just use "set rtlabel foobar" in filters
network and neighbor statements and the routes are labeled accordingly.
While doing that fix some mem-leaks by introducing filterset_free() and
remove the free on send option of send_filterset().
This took a bit longer because we need to carefully track the rtlabel id
refcnts or bad things may happen on reloads.
henning@ looks fine

Introduce a per prefix weight. The weight is used to tip prefixes with equal
long AS pathes in one or the other direction. It weights a prefix at a very
late stage in the decision process. This is a nice bgpd feature to traffic
engineer networks where most AS pathes are equally long.
OK henning@

Allow to modify the metrics in a relative way by prepending the number with
a '+' or '-'. e.g. set localpref +20. This is another gem from the FOSDEM
lying around on my HD gathering dust. OK henning@

Finally commit the transparent-as and nexthop no-modify stuff I wrote on the
way to FOSDEM. With transparent-as set to ye bgpd will not prepend his own
AS for sent updates. NB the neighbor needs to set "enforce neighbor-as no"
or it will not like the received AS paths. With set nexthop no-modify bgpd
will change the nexthop as done normaly.
OK henning@ man page update with help of jmc@

Add two missing breaks and suddenly using filter has no strange side effects.
Sometimes it is good to look at the rib output of a test box.

KNF

Switch from a single filter_set to a linked list of sets. With this change
it is possible to specify multiple communities. This is also the first step
to better bgpd filters. OK henning@

Don't access pointers blindly. asp is NULL for withdraws. This fixes a rde
crash noticed by Stefan Wahl and later by henning@. OK henning@

one m is enough in incoming, really ;)

Add prepend-neighbor feature. Prepend the remote-as n times similar to
prepend-self. Only for incomming UPDATEs. OK henning@

switch nexthop in struct filter_set form struct in_addr to struct bgpd_addr
OK henning@

Correctly set the MED in outgoing UPDATEs. OK henning@

Monster diff to get one step closer to IPv6 support.
Cleanup path attribute handling. First of all kill struct attr_flags, all
those infos are now in struct rde_aspath. Second move attribute parser
functions into rde.c, rde_attr.c is shared between bgpd and bgpctl.
Third reimplementation of the nexthop handling. Make it IPv6 ready and
fix some major bug relating to "set nexthop".
henning@ OK if it breaks nothing

Cleanup aspath specific functions and api. Mainly switch to a refcnt based
allocation. This helps to save a bit of RAM. looks good henning@

rename and move prefix_equal() to prefix_compare() which returns -1, 0, 1
similar to memcmp() and all other compare functions in bgpd. OK henning@

Fix reverse logic bug in the prefix filter.

implement "set nexthop blackhole" and "set nexthop reject"
blackhole/reject routes will be entered to the kernel for matching ones.
this is intended to be used with the Cymru Bogon Route Server Project
(http://www.cymru.com/BGP/bogon-rs.html) and similar services, claudio ok

First step at multiprotocol support, only partially done.
OK henning@

at least somewhat consistently name the TAILQ_ENTRYs... this confused me
more than once

extend filter language to allow basic setting of COMMUNITIES attribute.
ok claudio@

add a filter option to dump prefixes learned in UPDATEs into a PF table,
intended for building realtime BGP blacklists (e.g. with spamd);
ok claudio & henning

Add basic support for communities. Currently it is only possible to filter
on communities, e.g match from any community 24640:* set localpref 666
OK henning@

Framework for rib lookups by prefix. OK henning@

spelling

remove unneded peer pointer in struct prefix and change a in_addr_t to
struct in_addr. OK henning@

spaces

Enhance filters. prefixlen knows now 8-24 and 8><24. It is possible to use
prefix 10.0.0.0/8 prefixlen >= 8 and set localpref 100 can be set on a per
neighbor basis. OK henning@

Add support for basic filters. Nothing optimized and it has some issues but
this is a huge step forward. OK henning@

Implement a way to announce flowspec rules without hitting Adj-RIB-In
and Loc-RIB. Flowspec objects are collected in a single flowrib RIB
and then directly distributed into the various Adj-RIB-Outs.
For this to work add a bypass in the filter logic (flowspec AFI/SAFI
are currently accepted without any rule). The filter language lacks
a way to allow prefixes based on AFI/SAFI which is the minimum needed.
OK tb@

Compile the output filter rules into per peer filter rules.

especially on route-servers the output filters are in the hot path so
reducing the number of rules to check has a big impact. I have seen a
25% to 30% speedup in my big IXP testbench.
The output ruleset is applied and copied for each peer during config reload
and when a peer is initially added.
OK tb@

Implement filter and control message matching for ASAP.

This adds avs (ASPA validation state) which can be 'unknown', 'valid'
or 'invalid'. It behaves similar to ovs but the ASPA validation state
of paths from iBGP sessions is 'unknown' and the role of the ebgp session
is important to get the right validation state.

OK tb@

Implement ASPA validation and reload logic on ASPA set changes.

For this use the validation state (vstate) in struct prefix and
struct filterstate to store both the ASPA and ROA validity.
Introduce helper functions to set and get the various states for
struct prefix and make sure struct filterstate is also setup properly.
Change the ASPA state in rde_aspath to be AFI/AID and role independent
by storing all 4 possible outcomes. Also add a ASPA generation count
which is used to update the rde_aspath ASPA state cache on reloads.
Rework the rde_aspa.c code to be AFI/AID and role independent. Doing
this for roles is trivial but AFI switch goes deep and is so unnecessary.
The reload is combined with the ROA reload logic and renamed to RPKI
softreload.

OK tb@

Split rde_filterstate_prep() into three functions.
- rde_filterstate_init(): initialize a filterstate to default values
- rde_filterstate_copy(): copy from a filterstate into a new state object
- rde_filterstate_prep(): set filtersate based on prefix passed as argument.

This makes the code a bit easier to read.
OK tb@

Add the validation state to the filterstate struct.
Removes vstate argument from rde_filter().
Rename prefix_vstate() to prefix_roa_vstate().
OK tb@

whitespace found during a read-thru; ok claudio

Implement a max communities filter match

When max-communities X is set on a filterrule the filter will match when
more than X communities are present in the path. In other words
max-communities 0 means no communities are allowed and max-communities 3
limits it up to 3 communities.
There is max-communities, max-ext-communities and max-large-communities
for each of the 3 community attributes. These three max checks can be used
together.
OK tb@ job@

Switch from u_intX_t types to stdint.h uintX_t. Mostly mechanical with
a few reindents.
OK florian@ tb@

Implement IMSG_CTL_SHOW_SET to get information about roa-set, as-sets and
prefix-sets loaded into the RDE. For now only the number of prefixes or
asnumbers are shown plus the time since the last change was done to the table.
OK benno@

rework the overflow checks for the various relative metric adjustments.
This test no longer depends on specific overflow behaviour.
OK millert@

Refactor the filterset handling of nexthops. Instead of depending on
bgpd_process and changing the behaviour that way add a new filterset
type ACTION_SET_NEXTHOP_REF which is used when the nexthop reference
of the union is used. Adjust the RDE to convert ACTION_SET_NEXTHOP to
ACTION_SET_NEXTHOP_REF when receiving the filtersets.
OK benno@

Rename copy_filterset() to filterset_copy() and move it to rde_filter.c
where functions like filterset_move() live. Also initialize the dest
TAILQ in filterset_copy() as it is done in filterset_move().
OK benno@ phessler@

Instead of passing a struct prefix pointer to rde_filter() pass the 4 values
prefix_peer, prefix_vstate and prefix/prefixlen to the function. This removes
some ugly hacks in cases where the prefix was not available.
Also adjust the order of arguments of rde_attr_set() to match rde_filter().
OK benno@

Unify the way object in the RDE are reference counted. The affected
structures are pt_entry, rde_aspath, rde_communities, and nexthop.
The functions are always called *_ref and *_unref also the behaviour
when the last reference is removed is unified and now the object is
removed inside of the unref function. The actual bean-counting is not
modified by this diff.
OK benno@

Add a direct pointer from struct prefix to struct pt_entry.
This changes makes it possible to not use the struct rib_entry pointer
which will be used to optimize the Adj-RIB-Out.
Also adjust pt_ref() and pt_unref() so that the code can be written
a bit more compact. Also prefix_cmp() no longer needs to go via
rib_compare() and calls pt_prefix_cmp() directly.
OK phessler@

Completley rewrite the community matching and handling code. All community
attributes are put into a new data structure when parsing the UPDATE.
The filter code can quickly lookup and modify this data structure.
When creating an UPDATE the data is put back into wire format.
Setups using a lot of communities benefit a lot from this.
Input and OK benno@

Neither rde_apply_set() nor rde_filter() are called with a NULL state so
remove some unneeded == NULL checks.
OK benno@

Implement as-override, a feature where the neighbor AS is replaced by the
local AS in AS paths. This is sometimes needed in bigger transport networks
where private AS numbers are used in multiple locations.
The implementation is done using a filterset which modifies the AS path -
somewhat inspired by the set attribute code. Setting as-override yes will add
match from <neighbor> set { as-override }
to the start of the filter rules. Since this is filters the Adj-RIB-In still
holds the original path and so reloads changing the setting just work.
With and OK markus@

Fold ext-communities into filter_community so that bgpd can match
multiple ext-communities at the same time as well. Additionally this fixes
parsing some of the ext-community types. Now all communities are handled
by one common struct.
OK benno@ plus some input from denis@

Refactor aspath code a bit. Move cached source_as (for origin validation)
into struct aspath and pass that struct to aspath_match().
OK denis@

Start reworking community handling. Merge standard communities and large
communities into one filter_community struct and allow it that more then
one community can be used in filter rules (currently up to 3).
Also rework the code handling bgpctl show rib commands. The special IMSG
types for the various filters are gone and the code is in general simpler.
OK job@, phessler@

Remove an unneeded union wrapping the skipsteps pointer.
OK phessler@

Implement origin validation in bgpd. This introduces two new tables, the
roa-set for RPKI based origin validation and a origin-set which allows to
lookup a source-as / prefix pair.
For RPKI a config can be built like this:
roa-set {
165.254.255.0/24 source-as 15562
193.0.0.0/21 maxlen 24 source-as 3333
}
deny from any ovs invalid
match from any ovs valid set community local-as:42
match from any ovs not-found set community local-as:43
Origin sets are similar but only match when the source-as / prefix pair is
valid.
match from any origin-set ARINDB set community local-as:44
Committing this now so that further work can be done in tree.
OK benno@, job@

Rename AS_NONE to AS_UNDEF, AS_NONE will be reused for a different purpose
soon. OK compiler and grep

Switching bgpd to a default deny policy had one bad side-effect. Some
withdraw were suddenly filtered out because the filter ran into the
default deny. So for this case (state == NULL) change action to default
allow. This bug was haunting bgpd for a while now causing prefixes to be
stuck for no obvious reason.
OK benno@, sthen@

Indent issue. No functional change

Split up as_set into a set_table and an as_set. The first is what does
the lookup and will now also be used in roa-set tries. The as_set is glue
to add the name and dirty flag. Add an accessor to get the set data so
that the imsg sending and printing can be moved into the right places.
This is done mainly because roa-sets need similar but slightly different
versions and making the code more generic is the best way fixing this.
OK benno@

whitespace cleanup, ok claudio@

use TAILQ_CONCAT in filterset_move(). ok claudio@

implement or-longer filter op for prefix-sets. Allows one two write rules like
deny from any prefix-set mynetworks or-longer
ok claudio, feature discussed with job and deraadt

fix badly broken reload of filter rules that use prefix-sets. debugged
and fixed with/by claudio@

Implement a fast presix-set lookup. This magic trie is able to match a
prefix addr/plen to a prefix-set spec addr/plen prefixlen min - max (a
prefix including prefixlen range). Every addr/plen pair is a node in the
trie and the prefixlen is added as a bitmask to those nodes.
For the lookup the any match is OK, there is no need to do longest or
best prefix matching.
Inspiration for this solution comes from the way bird implements this
which was done by Ondrej Zajicek santiago (at) crfreenet.org
OK benno@

Implement as-set a fast lookup table to be used instead of long list of
AS numbers in source-as, AS and transit-as filterstatements. These table
use bsearch to quickly verify if an AS is in the set or not.
The filter syntax is not fully set in stone yet.
OK denis@ benno@ and previously OK deraadt@

Implement most prefixlen operations as OP_RANGE (prefixlen A - B).
Simplify the RDE logic this way and make it possible to load such ranges
into a much faster lookup trie for prefix-sets.
When printing the config bgpd tries to use the nices way to express the rule:
e.g. match from any prefix 18.0.0.0/8 prefixlen 8 - 32
becomes match from any prefix 18.0.0.0/8 or-longer
Apart from that there is no user visible change because of this.
OK sthen@

Change the way as_compare() and aspath_match() handle 'neighbor-as'. Instead
of doing the condition before calling aspath_match() just pass the neighbor-as
down to as_compare() which then has all needed data for the lookup. While
doing this also remove one of the as fields in struct filter_as since the
min/max fields can be reused for unary operations.
OK denis@ phessler@

Move nexthop and nexthop flags from the rde_aspath to struct prefix.
struct prefix will be slowly becomming the hub of the rib.
OK phessler@ job@

Split out the rule skipping logic into own function and by doing so ensure
that both filter lists are treated the same way. This fixes an inconsistency
with ibgp and ebgp filters as used in the example config.
OK benno@ sthen@

Move nexthop into struct filterstate (including nexthop flags) and use
them whereever possible. In some places (path_update, softreconfig_out
handler) the nexthop state is temporarily folded back into the rde_aspath.
Tested and OK benno@

Use struct filterstate in rde_update_dispatch() and pass it down to
functions like rde_update_update and path_update. This will allow to
move more pointers from rde_aspath to the prefix.
Looks good benno@

Introduce a struct filterstate and pass this to rde_filter instead of
passing the asp. This is no longer using asp_get() and should be therefor
be a bit lighter. Will also allow to put more stuff into the state.
OK denis@ sthen@

Prepare the ground for allowing temporary aspath object living on the stack.
To do this path_copy() gets a second argument (dst, src) and a new function
path_prep() is introduced to initialize an aspath object. The current
path_copy() usage is replaced with path_copy(path_get(), asp) which does
the same. Additionally some const where added to the *_copy functions to
make it more obvious which is the source and target. Also the pftable_ref()
and rtlabel_ref() functions return now the id instead of void.
OK sthen@

Remove rde_aspath pointer from rde_filter since that argument can be fetched
from the prefix instead. While there also switch to prefix_peer from asp->peer
in rde_dump_rib_as(). Makes the code easier overall.

Instead of passing the rde_aspath to nexthop_modify() pass pointers to
the nexthop and the flags.

Pass a struct prefix to rde_filter and remove some of the arguments which
are now fetched from struct prefix. Currently some trickery is needed
for export default-route but this will get better once Adj-RIB-Out comes.
OK benno@

Move rde_test_prefix() to a place where it makes more sense. No functional
change.

Properly start reference counting struct nexthop. This removes the need for
some ugly workaround to make sure nexthop objects don't disapear while
still being referenced. During initial lookup of a nexthop a extra reference
is pulled but even that is now a bit cleaner than before.
Tested by job@, dennis@, benno@ OK job@ dennis@

Use correct function name in fatalx()

Deprecate announce (all|self|none|default-route)
The announce keyword was overloaded and confused a lot of operators, time
to clean it up and while there incorporate RFC8212 guideline for propagation.
- `announce all` is the new default but the default deny filter will
make sure that by default nothing is leaked
- `announce self` is no more and results in syntax error
- `announce none` is now `export none`
- `announce default-route` becomes `export default-route`
- the filters are switched to a default deny rule both incoming and outgoing

You most certainly need to adjust your config!

Best is to change the config in advance by using `announce all` explicitly on
all neighbors and adding `deny from any` and `deny to any` at the start of
your filters and adjust the rest of the filters to still produce the same
result. `bgpd -nv -f bgpd.conf ` and `bgpctl show rib out nei foo` are good
tools to verify the changes.
Lots of discussions with job@, deraadt@, sthen@
OK job@

claudio noted that this is an else case because we have either a
prefix or a prefix-set.

Add prefix-sets, lists of prefixes which can be used in place of a
prefix in a filter rule. Initial idea hashed out with job@ in Toronto.
This is WIP, i'm commiting it now so we can work on it in the tree.
ok florian@ claudio@

prefix check must be last because the prefixlen check does an immediate return.
This will be rewritten soon so just do the quick fix now.
Found and OK benno@

allow filter rules to be written that affect ibgp or ebgp neighbors

discussed with henning@
OK claudio@, benno@, job@

Allow OpenBGPD to selectively choose which local ASN to use per-peer.
This is intended to be used for ASN migrations, not for permanent use.

You MUST use filters to protect yourself from receiving your own routes.
There be dragons and grues.

OK claudio@ benno@

allow us to use 'local-as' in the filter language

"match in from any set community local-as:neighbor-as"

OK claudio@

sync log.c from relayd et al to bgpd.

there is still a little difference regarding handling of the verbosity
value that will be handled later.

ok claudio@ florian@

properly check if large-community was set before

reported by Job Snijders

Add support for draft-ietf-idr-large-community

Joint work with Job Snijders, many thanks!
OK benno@ deraadt@

Add operators =, !=, - (range), >< (exclsive range) to the as-path
filters (AS, peer-as, source-as, transit-as).

Add a use case (block illegal AS numbers) to the bgpd.conf example.

feedback from claudio, sthen, florian,
ok florian@ phessler@

Radically improve the performance of bgpd filters. Based on PF's skip
steps (and uses much of the same code).

In a torture test of ~600k prefix filters and 65k prefixes, convergance
time goes from 35 minutes to 30 seconds.

Many thanks to LONAP for providing a base configuration for torture
testing.

many discussions with claudio@, benno@, sthen@ and the rest of the bgpd crowd

OK sthen@ benno@

In all other cases of rde_filter_match() we ensure that asp is valid so
do it here as well.

Next round of config cleanup. Move various lists into the bgpd_config struct.
This is the next step to better split parsing and merging the config.
OK benno@

allow us to write rules that match directly on the peer AS

...
allow from AS 1 prefix 192.0.2.0/24
...

Also adjust the IRR ruleset output to include the declared peer AS,
instead of hoping they listed their neighbor IP address!


OK benno@
older version OK: claudio@ henning@

rename rde_free_filter() to filterlist_free() and start using it outside
of the RDE to free the filterlists. Also refactor common code to merge
filterlists into its own function. Makes the code look nicer.

fix the matching for filter rules of 'prefixlen = XX'

OK claudio@

Merge the prefix and prefixlen filter bits into one filter. Change the
filter expansion so that rules are grouped by prefixes last. The RDE will
then be able to optimize the rules into table lookups but that is a later
step. As additional goodies it is now possible to use inet and inet6
on their own and or-longer can be used as a shorthand for prefixlen >= len.
OK henning@ sthen@ florian@

Rewrite the internals of the RDE reload logic.
This is the first step to make bgpd reload non blocking in the RDE.
It also speeds up the reload time a fair bit in some cases (mainly if
you run with multiple RIBs and have larger filtersets) and it should also
fix a few edge cases on reloads.
Testing done by benno@, florian@ and sthen@ OK henning@ and benno@

Allow filtering based on the NEXTHOP attribute. This allows to build rules
like: allow from any nexthop neighbor (to allow only prefixes that use the
routers IP address as nexthop). Lots of testing, input and OK florian@

Move a few functions into util.c because bgpctl will need them soon.

On reload the filtersets attached to a network need to be moved to the
existing network element. First free the old filterset and then move
the new on top of it. This solves the reload issue with changing network
statements. OK henning@

Deny prefixes that have F_ATTR_PARSE_ERR set by default. Now they
will not leak into the Loc-RIB or other RIBs but act as withdraws.
The invalid prefixes would not been selected anyway but it is better
to keep them out of all RIBs but the Adj-RIB-In.

Implement two new filters, max-as-len and max-as-seq. The first is limiting
the length of an AS path (matches if the path is longer then the specified
lenght) the second matches when a sequence of the same AS number is longer
then the specified length).
max-as-len is good to protect crappy comercial bgp boxes from other crappy
comercial bgp boxes. max-as-seq was a feature request from SwissIX and maybe
EuroIX to find and filter prepends.
Additinal testing and OK sthen@

Allow neighbor-as in AS filter statements like:
match from any source-as neighbor-as set localpref 1000
OK henning@

Allow to filter for ext-community attributes. Currently only perfect matches
work but that's already better then nothing. OK sthen@

Merge rde_filter_community() with community_match() and kill a useless
indirection.

Implement "set ext-community [delete] subtype key:value" to set and delete
extended communities as specified in RFC 4360. No matching implemented yet
and stuff like * and neighbor-as are neither supported but will be soon.
Looks good henning & sthen, manpage fixed by jmc

Use an artificial address family id in struct bgpd_addr and almost everywhere
else. Adds conversion functions to map AFI/SAFI and the Unix AF_ values
from and into AID used in bgpd. This is needed to support things like MPLS
VPN and other upcomming changes that need to play a lot with AFI/SAFI pairs.
Mostly mechanical change, henning@ has no particular issues with this.
Must go in so that I can continue working.

support for set origin; based on an initial diff from
Sebastian Benoit <benoit-lists at fb12 dot de> who also tested this version
claudio ok

Implement the error handling as proposed in draft-ietf-idr-optional-transitive
for optional transitive attributes. In short if the partial bit is set on
an optional transitive attribute but the attribute fails validation ignore
the attribute or mark the path as ineligible instead of killing the session
with a NOTIFICATION. Tested, input and OK sthen, OK henning

Some preliminary filter magic to support multiple RIBs on the filters.
It is ugly but does the trick for now. Filters will be rewritten anyway.
The rib specifier only makes sense on from rules. e.g. deny rib OMG from any

Correct the logic when matching prefixes. This solves issues where IPv6
prefixes where matched on a simple deny from any prefix 0.0.0.0/0 rule.
OK henning@

Allow bgpd to delete more then one community per filter rule. Fixes PR5807
tested by Raphael Ho long time ago.

allow matching on communities using 0 in the AS part, that is in use.
that unfortunately means we cannot use 0 for "unset".
ok claudio

Various spelling fixes from Stuart Henderson.

Make bgpd 4-byte AS compatible. All internal representations of AS numbers
are now 4-byte instead of the old 2-byte numbers. The only exception are
communities because they can not be switched. The RDE will inflate and deflate
the ASPATH and AGGREGATOR attributes on demand and create the NEW_ASPATH and
NEW_AGGREGATOR field whenever needed. Both old and new stile sessions are
supported and can be mixed. Currently new stile sessions with the 4-byte AS
number capability turned on are only enabled if one of the AS numbers involved
is a 4-byte one.
This is based on an initial diff by Geoff Huston gih (at) apnic (dot) net
Cleanup, testing and bug-fixes by myself (via AS 3.10).
Currently mrt table dumps are producing incompatible output this will be fixed
afterwards -- this diff is already big enough.

"get it in if you think it is ready" henning@

Even better nexthop delete behaviour. Do not delete nexthop if they are used
by filter sets or if the nexthop is currently looked up. With this the
"nexthop_update: non-existent nexthop" warning should be history. OK henning@

Preload and pin nexthop used in filtersets so the are validiated when used.
This will fix problems with set nexthop on outgoing filters. Found by
gluk@ OK henning@

Remove filterset_names from bgpd.h and replace it with a function because
the table was already out of sync now. OK henning@

add "set nexthop self", force nexthop to be set to own address even with IBGP
requested & tested Falk Brockerhoff <fb@smartterra.de>, and tony sarendal
tested this too. claudio ok

Implement "set community delete 65001:*" and friends. This will remove
communities from the path attributes. Useful to make sure that the ones you
set later are set by a (evil) peer. OK henning@

If the aspath gets copied because it is modified use the copy for filter
matching. With this it is possible to make later filters depend on previous
filter changes -- e.g. via community attributes.

Doh! Fix stupid copy paste error. Setting the community type to the AS instead
of the more obvious type produces really funny errors and gives you some happy
hours of debugging.

Implement new special community "neighbor-as". neighbor-as is expanded on
the fly to the remote AS of the current neighbor. This can be used to
simplify rulesets in a dramatic way -- going from a script based nightmare
down to a handfull rules. jajajaja henning@

Check if filter changed on a per peer basis. This should speed up the
table run done later as many filter evaluations can be skipped.
From the softreconfig in tree. Looks good henning@

Copy AS path in rde_filter() on demand instead of doing it before calling
rde_filter(). Adapt path_update() to this change too. path_update() does
a path_copy before linking the rde_aspath into the RIB. Looks good Henning.

The attributes cache broke the set community filterset because community_set()
modified the attribute data directly and corrupted the cache by doing it.
It is no longer allowed to modify attributes via attr_optget() -> change
attr->data. Instead remove the old attribute from the aspath and then add
a new modifed one again. Included in this change is the removal of a "feature"
that allowed only one community per AS. If you had problems to add multiple
communities via filters then this was the problem. Looks good Henning.

Missing #include <limits.h>

even more spaces and tabs.

Implement filterset_equal() and rde_filter_equal(). Both return 1 if
the two passed filter(set)s are equal or 0 otherwise. rde_filter_equal()
has an additional argument dir to specify which direction should be considered.

Softreconfig out support. On config reload filter changes of outgoing rules
will propagte directly to the neighbors. There is no need to restart bgpd
in that case. Currently not optimal but a good start. "get it in" henning@

Switch from the per peer filter set list to a filter-only solution.
The default filter_sets are converted into match filter rules that get
evaluated first. Simplifies code massively -- mainly the config reload
part -- and makes softreconfig out a piece of cake. "get it in" henning@

Pass the correct peer to rde_apply_set(). rde_apply_set() needs to know
the peer where the prefix came from so that prepend-neighbor works.
Extend rde_filter() and make sure that the correct peer is passed.
Until now most cases resulted in a NULL peer causing a nasty crash that
was found by David Ulevitch. OK henning@

New function filterset_cmp() used two compare two struct filter_set for
equality. This function is a bit more complicated than a memcmp() because there
are types that need to be considered equal e.g. ACTION_SET_MED and
ACTION_SET_RELATIVE_MED. Also ACTION_SET_COMMUNITY and ACTION_SET_NEXTHOP
need some special care. OK henning@

More spaces

Switch filter_sets form SIMPLEQ to TAILQ, needed for upcomming stuff.

The newly introduced function filterset_free() existed already as
rde_free_set(), I just missed it when I was looking for it.
Kill rde_free_set() and use the more correct filterset_free() from now on.

Make the pftable filter set use the name2id "cache" like the route labels.
This saves 14 bytes per aspath. OK henning@

rtlabel support via filter sets. Just use "set rtlabel foobar" in filters
network and neighbor statements and the routes are labeled accordingly.
While doing that fix some mem-leaks by introducing filterset_free() and
remove the free on send option of send_filterset().
This took a bit longer because we need to carefully track the rtlabel id
refcnts or bad things may happen on reloads.
henning@ looks fine

Introduce a per prefix weight. The weight is used to tip prefixes with equal
long AS pathes in one or the other direction. It weights a prefix at a very
late stage in the decision process. This is a nice bgpd feature to traffic
engineer networks where most AS pathes are equally long.
OK henning@

Allow to modify the metrics in a relative way by prepending the number with
a '+' or '-'. e.g. set localpref +20. This is another gem from the FOSDEM
lying around on my HD gathering dust. OK henning@

Finally commit the transparent-as and nexthop no-modify stuff I wrote on the
way to FOSDEM. With transparent-as set to ye bgpd will not prepend his own
AS for sent updates. NB the neighbor needs to set "enforce neighbor-as no"
or it will not like the received AS paths. With set nexthop no-modify bgpd
will change the nexthop as done normaly.
OK henning@ man page update with help of jmc@

Add two missing breaks and suddenly using filter has no strange side effects.
Sometimes it is good to look at the rib output of a test box.

KNF

Switch from a single filter_set to a linked list of sets. With this change
it is possible to specify multiple communities. This is also the first step
to better bgpd filters. OK henning@

Don't access pointers blindly. asp is NULL for withdraws. This fixes a rde
crash noticed by Stefan Wahl and later by henning@. OK henning@

one m is enough in incoming, really ;)

Add prepend-neighbor feature. Prepend the remote-as n times similar to
prepend-self. Only for incomming UPDATEs. OK henning@

switch nexthop in struct filter_set form struct in_addr to struct bgpd_addr
OK henning@

Correctly set the MED in outgoing UPDATEs. OK henning@

Monster diff to get one step closer to IPv6 support.
Cleanup path attribute handling. First of all kill struct attr_flags, all
those infos are now in struct rde_aspath. Second move attribute parser
functions into rde.c, rde_attr.c is shared between bgpd and bgpctl.
Third reimplementation of the nexthop handling. Make it IPv6 ready and
fix some major bug relating to "set nexthop".
henning@ OK if it breaks nothing

Cleanup aspath specific functions and api. Mainly switch to a refcnt based
allocation. This helps to save a bit of RAM. looks good henning@

rename and move prefix_equal() to prefix_compare() which returns -1, 0, 1
similar to memcmp() and all other compare functions in bgpd. OK henning@

Fix reverse logic bug in the prefix filter.

implement "set nexthop blackhole" and "set nexthop reject"
blackhole/reject routes will be entered to the kernel for matching ones.
this is intended to be used with the Cymru Bogon Route Server Project
(http://www.cymru.com/BGP/bogon-rs.html) and similar services, claudio ok

First step at multiprotocol support, only partially done.
OK henning@

at least somewhat consistently name the TAILQ_ENTRYs... this confused me
more than once

extend filter language to allow basic setting of COMMUNITIES attribute.
ok claudio@

add a filter option to dump prefixes learned in UPDATEs into a PF table,
intended for building realtime BGP blacklists (e.g. with spamd);
ok claudio & henning

Add basic support for communities. Currently it is only possible to filter
on communities, e.g match from any community 24640:* set localpref 666
OK henning@

Framework for rib lookups by prefix. OK henning@

spelling

remove unneded peer pointer in struct prefix and change a in_addr_t to
struct in_addr. OK henning@

spaces

Enhance filters. prefixlen knows now 8-24 and 8><24. It is possible to use
prefix 10.0.0.0/8 prefixlen >= 8 and set localpref 100 can be set on a per
neighbor basis. OK henning@

Add support for basic filters. Nothing optimized and it has some issues but
this is a huge step forward. OK henning@

Compile the output filter rules into per peer filter rules.

especially on route-servers the output filters are in the hot path so
reducing the number of rules to check has a big impact. I have seen a
25% to 30% speedup in my big IXP testbench.
The output ruleset is applied and copied for each peer during config reload
and when a peer is initially added.
OK tb@

Implement filter and control message matching for ASAP.

This adds avs (ASPA validation state) which can be 'unknown', 'valid'
or 'invalid'. It behaves similar to ovs but the ASPA validation state
of paths from iBGP sessions is 'unknown' and the role of the ebgp session
is important to get the right validation state.

OK tb@

Implement ASPA validation and reload logic on ASPA set changes.

For this use the validation state (vstate) in struct prefix and
struct filterstate to store both the ASPA and ROA validity.
Introduce helper functions to set and get the various states for
struct prefix and make sure struct filterstate is also setup properly.
Change the ASPA state in rde_aspath to be AFI/AID and role independent
by storing all 4 possible outcomes. Also add a ASPA generation count
which is used to update the rde_aspath ASPA state cache on reloads.
Rework the rde_aspa.c code to be AFI/AID and role independent. Doing
this for roles is trivial but AFI switch goes deep and is so unnecessary.
The reload is combined with the ROA reload logic and renamed to RPKI
softreload.

OK tb@

Split rde_filterstate_prep() into three functions.
- rde_filterstate_init(): initialize a filterstate to default values
- rde_filterstate_copy(): copy from a filterstate into a new state object
- rde_filterstate_prep(): set filtersate based on prefix passed as argument.

This makes the code a bit easier to read.
OK tb@

Add the validation state to the filterstate struct.
Removes vstate argument from rde_filter().
Rename prefix_vstate() to prefix_roa_vstate().
OK tb@

whitespace found during a read-thru; ok claudio

Implement a max communities filter match

When max-communities X is set on a filterrule the filter will match when
more than X communities are present in the path. In other words
max-communities 0 means no communities are allowed and max-communities 3
limits it up to 3 communities.
There is max-communities, max-ext-communities and max-large-communities
for each of the 3 community attributes. These three max checks can be used
together.
OK tb@ job@

Switch from u_intX_t types to stdint.h uintX_t. Mostly mechanical with
a few reindents.
OK florian@ tb@

Implement IMSG_CTL_SHOW_SET to get information about roa-set, as-sets and
prefix-sets loaded into the RDE. For now only the number of prefixes or
asnumbers are shown plus the time since the last change was done to the table.
OK benno@

rework the overflow checks for the various relative metric adjustments.
This test no longer depends on specific overflow behaviour.
OK millert@

Refactor the filterset handling of nexthops. Instead of depending on
bgpd_process and changing the behaviour that way add a new filterset
type ACTION_SET_NEXTHOP_REF which is used when the nexthop reference
of the union is used. Adjust the RDE to convert ACTION_SET_NEXTHOP to
ACTION_SET_NEXTHOP_REF when receiving the filtersets.
OK benno@

Rename copy_filterset() to filterset_copy() and move it to rde_filter.c
where functions like filterset_move() live. Also initialize the dest
TAILQ in filterset_copy() as it is done in filterset_move().
OK benno@ phessler@

Instead of passing a struct prefix pointer to rde_filter() pass the 4 values
prefix_peer, prefix_vstate and prefix/prefixlen to the function. This removes
some ugly hacks in cases where the prefix was not available.
Also adjust the order of arguments of rde_attr_set() to match rde_filter().
OK benno@

Unify the way object in the RDE are reference counted. The affected
structures are pt_entry, rde_aspath, rde_communities, and nexthop.
The functions are always called *_ref and *_unref also the behaviour
when the last reference is removed is unified and now the object is
removed inside of the unref function. The actual bean-counting is not
modified by this diff.
OK benno@

Add a direct pointer from struct prefix to struct pt_entry.
This changes makes it possible to not use the struct rib_entry pointer
which will be used to optimize the Adj-RIB-Out.
Also adjust pt_ref() and pt_unref() so that the code can be written
a bit more compact. Also prefix_cmp() no longer needs to go via
rib_compare() and calls pt_prefix_cmp() directly.
OK phessler@

Completley rewrite the community matching and handling code. All community
attributes are put into a new data structure when parsing the UPDATE.
The filter code can quickly lookup and modify this data structure.
When creating an UPDATE the data is put back into wire format.
Setups using a lot of communities benefit a lot from this.
Input and OK benno@

Neither rde_apply_set() nor rde_filter() are called with a NULL state so
remove some unneeded == NULL checks.
OK benno@

Implement as-override, a feature where the neighbor AS is replaced by the
local AS in AS paths. This is sometimes needed in bigger transport networks
where private AS numbers are used in multiple locations.
The implementation is done using a filterset which modifies the AS path -
somewhat inspired by the set attribute code. Setting as-override yes will add
match from <neighbor> set { as-override }
to the start of the filter rules. Since this is filters the Adj-RIB-In still
holds the original path and so reloads changing the setting just work.
With and OK markus@

Fold ext-communities into filter_community so that bgpd can match
multiple ext-communities at the same time as well. Additionally this fixes
parsing some of the ext-community types. Now all communities are handled
by one common struct.
OK benno@ plus some input from denis@

Refactor aspath code a bit. Move cached source_as (for origin validation)
into struct aspath and pass that struct to aspath_match().
OK denis@

Start reworking community handling. Merge standard communities and large
communities into one filter_community struct and allow it that more then
one community can be used in filter rules (currently up to 3).
Also rework the code handling bgpctl show rib commands. The special IMSG
types for the various filters are gone and the code is in general simpler.
OK job@, phessler@

Remove an unneeded union wrapping the skipsteps pointer.
OK phessler@

Implement origin validation in bgpd. This introduces two new tables, the
roa-set for RPKI based origin validation and a origin-set which allows to
lookup a source-as / prefix pair.
For RPKI a config can be built like this:
roa-set {
165.254.255.0/24 source-as 15562
193.0.0.0/21 maxlen 24 source-as 3333
}
deny from any ovs invalid
match from any ovs valid set community local-as:42
match from any ovs not-found set community local-as:43
Origin sets are similar but only match when the source-as / prefix pair is
valid.
match from any origin-set ARINDB set community local-as:44
Committing this now so that further work can be done in tree.
OK benno@, job@

Rename AS_NONE to AS_UNDEF, AS_NONE will be reused for a different purpose
soon. OK compiler and grep

Switching bgpd to a default deny policy had one bad side-effect. Some
withdraw were suddenly filtered out because the filter ran into the
default deny. So for this case (state == NULL) change action to default
allow. This bug was haunting bgpd for a while now causing prefixes to be
stuck for no obvious reason.
OK benno@, sthen@

Indent issue. No functional change

Split up as_set into a set_table and an as_set. The first is what does
the lookup and will now also be used in roa-set tries. The as_set is glue
to add the name and dirty flag. Add an accessor to get the set data so
that the imsg sending and printing can be moved into the right places.
This is done mainly because roa-sets need similar but slightly different
versions and making the code more generic is the best way fixing this.
OK benno@

whitespace cleanup, ok claudio@

use TAILQ_CONCAT in filterset_move(). ok claudio@

implement or-longer filter op for prefix-sets. Allows one two write rules like
deny from any prefix-set mynetworks or-longer
ok claudio, feature discussed with job and deraadt

fix badly broken reload of filter rules that use prefix-sets. debugged
and fixed with/by claudio@

Implement a fast presix-set lookup. This magic trie is able to match a
prefix addr/plen to a prefix-set spec addr/plen prefixlen min - max (a
prefix including prefixlen range). Every addr/plen pair is a node in the
trie and the prefixlen is added as a bitmask to those nodes.
For the lookup the any match is OK, there is no need to do longest or
best prefix matching.
Inspiration for this solution comes from the way bird implements this
which was done by Ondrej Zajicek santiago (at) crfreenet.org
OK benno@

Implement as-set a fast lookup table to be used instead of long list of
AS numbers in source-as, AS and transit-as filterstatements. These table
use bsearch to quickly verify if an AS is in the set or not.
The filter syntax is not fully set in stone yet.
OK denis@ benno@ and previously OK deraadt@

Implement most prefixlen operations as OP_RANGE (prefixlen A - B).
Simplify the RDE logic this way and make it possible to load such ranges
into a much faster lookup trie for prefix-sets.
When printing the config bgpd tries to use the nices way to express the rule:
e.g. match from any prefix 18.0.0.0/8 prefixlen 8 - 32
becomes match from any prefix 18.0.0.0/8 or-longer
Apart from that there is no user visible change because of this.
OK sthen@

Change the way as_compare() and aspath_match() handle 'neighbor-as'. Instead
of doing the condition before calling aspath_match() just pass the neighbor-as
down to as_compare() which then has all needed data for the lookup. While
doing this also remove one of the as fields in struct filter_as since the
min/max fields can be reused for unary operations.
OK denis@ phessler@

Move nexthop and nexthop flags from the rde_aspath to struct prefix.
struct prefix will be slowly becomming the hub of the rib.
OK phessler@ job@

Split out the rule skipping logic into own function and by doing so ensure
that both filter lists are treated the same way. This fixes an inconsistency
with ibgp and ebgp filters as used in the example config.
OK benno@ sthen@

Move nexthop into struct filterstate (including nexthop flags) and use
them whereever possible. In some places (path_update, softreconfig_out
handler) the nexthop state is temporarily folded back into the rde_aspath.
Tested and OK benno@

Use struct filterstate in rde_update_dispatch() and pass it down to
functions like rde_update_update and path_update. This will allow to
move more pointers from rde_aspath to the prefix.
Looks good benno@

Introduce a struct filterstate and pass this to rde_filter instead of
passing the asp. This is no longer using asp_get() and should be therefor
be a bit lighter. Will also allow to put more stuff into the state.
OK denis@ sthen@

Prepare the ground for allowing temporary aspath object living on the stack.
To do this path_copy() gets a second argument (dst, src) and a new function
path_prep() is introduced to initialize an aspath object. The current
path_copy() usage is replaced with path_copy(path_get(), asp) which does
the same. Additionally some const where added to the *_copy functions to
make it more obvious which is the source and target. Also the pftable_ref()
and rtlabel_ref() functions return now the id instead of void.
OK sthen@

Remove rde_aspath pointer from rde_filter since that argument can be fetched
from the prefix instead. While there also switch to prefix_peer from asp->peer
in rde_dump_rib_as(). Makes the code easier overall.

Instead of passing the rde_aspath to nexthop_modify() pass pointers to
the nexthop and the flags.

Pass a struct prefix to rde_filter and remove some of the arguments which
are now fetched from struct prefix. Currently some trickery is needed
for export default-route but this will get better once Adj-RIB-Out comes.
OK benno@

Move rde_test_prefix() to a place where it makes more sense. No functional
change.

Properly start reference counting struct nexthop. This removes the need for
some ugly workaround to make sure nexthop objects don't disapear while
still being referenced. During initial lookup of a nexthop a extra reference
is pulled but even that is now a bit cleaner than before.
Tested by job@, dennis@, benno@ OK job@ dennis@

Use correct function name in fatalx()

Deprecate announce (all|self|none|default-route)
The announce keyword was overloaded and confused a lot of operators, time
to clean it up and while there incorporate RFC8212 guideline for propagation.
- `announce all` is the new default but the default deny filter will
make sure that by default nothing is leaked
- `announce self` is no more and results in syntax error
- `announce none` is now `export none`
- `announce default-route` becomes `export default-route`
- the filters are switched to a default deny rule both incoming and outgoing

You most certainly need to adjust your config!

Best is to change the config in advance by using `announce all` explicitly on
all neighbors and adding `deny from any` and `deny to any` at the start of
your filters and adjust the rest of the filters to still produce the same
result. `bgpd -nv -f bgpd.conf ` and `bgpctl show rib out nei foo` are good
tools to verify the changes.
Lots of discussions with job@, deraadt@, sthen@
OK job@

claudio noted that this is an else case because we have either a
prefix or a prefix-set.

Add prefix-sets, lists of prefixes which can be used in place of a
prefix in a filter rule. Initial idea hashed out with job@ in Toronto.
This is WIP, i'm commiting it now so we can work on it in the tree.
ok florian@ claudio@

prefix check must be last because the prefixlen check does an immediate return.
This will be rewritten soon so just do the quick fix now.
Found and OK benno@

allow filter rules to be written that affect ibgp or ebgp neighbors

discussed with henning@
OK claudio@, benno@, job@

Allow OpenBGPD to selectively choose which local ASN to use per-peer.
This is intended to be used for ASN migrations, not for permanent use.

You MUST use filters to protect yourself from receiving your own routes.
There be dragons and grues.

OK claudio@ benno@

allow us to use 'local-as' in the filter language

"match in from any set community local-as:neighbor-as"

OK claudio@

sync log.c from relayd et al to bgpd.

there is still a little difference regarding handling of the verbosity
value that will be handled later.

ok claudio@ florian@

properly check if large-community was set before

reported by Job Snijders

Add support for draft-ietf-idr-large-community

Joint work with Job Snijders, many thanks!
OK benno@ deraadt@

Add operators =, !=, - (range), >< (exclsive range) to the as-path
filters (AS, peer-as, source-as, transit-as).

Add a use case (block illegal AS numbers) to the bgpd.conf example.

feedback from claudio, sthen, florian,
ok florian@ phessler@

Radically improve the performance of bgpd filters. Based on PF's skip
steps (and uses much of the same code).

In a torture test of ~600k prefix filters and 65k prefixes, convergance
time goes from 35 minutes to 30 seconds.

Many thanks to LONAP for providing a base configuration for torture
testing.

many discussions with claudio@, benno@, sthen@ and the rest of the bgpd crowd

OK sthen@ benno@

In all other cases of rde_filter_match() we ensure that asp is valid so
do it here as well.

Next round of config cleanup. Move various lists into the bgpd_config struct.
This is the next step to better split parsing and merging the config.
OK benno@

allow us to write rules that match directly on the peer AS

...
allow from AS 1 prefix 192.0.2.0/24
...

Also adjust the IRR ruleset output to include the declared peer AS,
instead of hoping they listed their neighbor IP address!


OK benno@
older version OK: claudio@ henning@

rename rde_free_filter() to filterlist_free() and start using it outside
of the RDE to free the filterlists. Also refactor common code to merge
filterlists into its own function. Makes the code look nicer.

fix the matching for filter rules of 'prefixlen = XX'

OK claudio@

Merge the prefix and prefixlen filter bits into one filter. Change the
filter expansion so that rules are grouped by prefixes last. The RDE will
then be able to optimize the rules into table lookups but that is a later
step. As additional goodies it is now possible to use inet and inet6
on their own and or-longer can be used as a shorthand for prefixlen >= len.
OK henning@ sthen@ florian@

Rewrite the internals of the RDE reload logic.
This is the first step to make bgpd reload non blocking in the RDE.
It also speeds up the reload time a fair bit in some cases (mainly if
you run with multiple RIBs and have larger filtersets) and it should also
fix a few edge cases on reloads.
Testing done by benno@, florian@ and sthen@ OK henning@ and benno@

Allow filtering based on the NEXTHOP attribute. This allows to build rules
like: allow from any nexthop neighbor (to allow only prefixes that use the
routers IP address as nexthop). Lots of testing, input and OK florian@

Move a few functions into util.c because bgpctl will need them soon.

On reload the filtersets attached to a network need to be moved to the
existing network element. First free the old filterset and then move
the new on top of it. This solves the reload issue with changing network
statements. OK henning@

Deny prefixes that have F_ATTR_PARSE_ERR set by default. Now they
will not leak into the Loc-RIB or other RIBs but act as withdraws.
The invalid prefixes would not been selected anyway but it is better
to keep them out of all RIBs but the Adj-RIB-In.

Implement two new filters, max-as-len and max-as-seq. The first is limiting
the length of an AS path (matches if the path is longer then the specified
lenght) the second matches when a sequence of the same AS number is longer
then the specified length).
max-as-len is good to protect crappy comercial bgp boxes from other crappy
comercial bgp boxes. max-as-seq was a feature request from SwissIX and maybe
EuroIX to find and filter prepends.
Additinal testing and OK sthen@

Allow neighbor-as in AS filter statements like:
match from any source-as neighbor-as set localpref 1000
OK henning@

Allow to filter for ext-community attributes. Currently only perfect matches
work but that's already better then nothing. OK sthen@

Merge rde_filter_community() with community_match() and kill a useless
indirection.

Implement "set ext-community [delete] subtype key:value" to set and delete
extended communities as specified in RFC 4360. No matching implemented yet
and stuff like * and neighbor-as are neither supported but will be soon.
Looks good henning & sthen, manpage fixed by jmc

Use an artificial address family id in struct bgpd_addr and almost everywhere
else. Adds conversion functions to map AFI/SAFI and the Unix AF_ values
from and into AID used in bgpd. This is needed to support things like MPLS
VPN and other upcomming changes that need to play a lot with AFI/SAFI pairs.
Mostly mechanical change, henning@ has no particular issues with this.
Must go in so that I can continue working.

support for set origin; based on an initial diff from
Sebastian Benoit <benoit-lists at fb12 dot de> who also tested this version
claudio ok

Implement the error handling as proposed in draft-ietf-idr-optional-transitive
for optional transitive attributes. In short if the partial bit is set on
an optional transitive attribute but the attribute fails validation ignore
the attribute or mark the path as ineligible instead of killing the session
with a NOTIFICATION. Tested, input and OK sthen, OK henning

Some preliminary filter magic to support multiple RIBs on the filters.
It is ugly but does the trick for now. Filters will be rewritten anyway.
The rib specifier only makes sense on from rules. e.g. deny rib OMG from any

Correct the logic when matching prefixes. This solves issues where IPv6
prefixes where matched on a simple deny from any prefix 0.0.0.0/0 rule.
OK henning@

Allow bgpd to delete more then one community per filter rule. Fixes PR5807
tested by Raphael Ho long time ago.

allow matching on communities using 0 in the AS part, that is in use.
that unfortunately means we cannot use 0 for "unset".
ok claudio

Various spelling fixes from Stuart Henderson.

Make bgpd 4-byte AS compatible. All internal representations of AS numbers
are now 4-byte instead of the old 2-byte numbers. The only exception are
communities because they can not be switched. The RDE will inflate and deflate
the ASPATH and AGGREGATOR attributes on demand and create the NEW_ASPATH and
NEW_AGGREGATOR field whenever needed. Both old and new stile sessions are
supported and can be mixed. Currently new stile sessions with the 4-byte AS
number capability turned on are only enabled if one of the AS numbers involved
is a 4-byte one.
This is based on an initial diff by Geoff Huston gih (at) apnic (dot) net
Cleanup, testing and bug-fixes by myself (via AS 3.10).
Currently mrt table dumps are producing incompatible output this will be fixed
afterwards -- this diff is already big enough.

"get it in if you think it is ready" henning@

Even better nexthop delete behaviour. Do not delete nexthop if they are used
by filter sets or if the nexthop is currently looked up. With this the
"nexthop_update: non-existent nexthop" warning should be history. OK henning@

Preload and pin nexthop used in filtersets so the are validiated when used.
This will fix problems with set nexthop on outgoing filters. Found by
gluk@ OK henning@

Remove filterset_names from bgpd.h and replace it with a function because
the table was already out of sync now. OK henning@

add "set nexthop self", force nexthop to be set to own address even with IBGP
requested & tested Falk Brockerhoff <fb@smartterra.de>, and tony sarendal
tested this too. claudio ok

Implement "set community delete 65001:*" and friends. This will remove
communities from the path attributes. Useful to make sure that the ones you
set later are set by a (evil) peer. OK henning@

If the aspath gets copied because it is modified use the copy for filter
matching. With this it is possible to make later filters depend on previous
filter changes -- e.g. via community attributes.

Doh! Fix stupid copy paste error. Setting the community type to the AS instead
of the more obvious type produces really funny errors and gives you some happy
hours of debugging.

Implement new special community "neighbor-as". neighbor-as is expanded on
the fly to the remote AS of the current neighbor. This can be used to
simplify rulesets in a dramatic way -- going from a script based nightmare
down to a handfull rules. jajajaja henning@

Check if filter changed on a per peer basis. This should speed up the
table run done later as many filter evaluations can be skipped.
From the softreconfig in tree. Looks good henning@

Copy AS path in rde_filter() on demand instead of doing it before calling
rde_filter(). Adapt path_update() to this change too. path_update() does
a path_copy before linking the rde_aspath into the RIB. Looks good Henning.

The attributes cache broke the set community filterset because community_set()
modified the attribute data directly and corrupted the cache by doing it.
It is no longer allowed to modify attributes via attr_optget() -> change
attr->data. Instead remove the old attribute from the aspath and then add
a new modifed one again. Included in this change is the removal of a "feature"
that allowed only one community per AS. If you had problems to add multiple
communities via filters then this was the problem. Looks good Henning.

Missing #include <limits.h>

even more spaces and tabs.

Implement filterset_equal() and rde_filter_equal(). Both return 1 if
the two passed filter(set)s are equal or 0 otherwise. rde_filter_equal()
has an additional argument dir to specify which direction should be considered.

Softreconfig out support. On config reload filter changes of outgoing rules
will propagte directly to the neighbors. There is no need to restart bgpd
in that case. Currently not optimal but a good start. "get it in" henning@

Switch from the per peer filter set list to a filter-only solution.
The default filter_sets are converted into match filter rules that get
evaluated first. Simplifies code massively -- mainly the config reload
part -- and makes softreconfig out a piece of cake. "get it in" henning@

Pass the correct peer to rde_apply_set(). rde_apply_set() needs to know
the peer where the prefix came from so that prepend-neighbor works.
Extend rde_filter() and make sure that the correct peer is passed.
Until now most cases resulted in a NULL peer causing a nasty crash that
was found by David Ulevitch. OK henning@

New function filterset_cmp() used two compare two struct filter_set for
equality. This function is a bit more complicated than a memcmp() because there
are types that need to be considered equal e.g. ACTION_SET_MED and
ACTION_SET_RELATIVE_MED. Also ACTION_SET_COMMUNITY and ACTION_SET_NEXTHOP
need some special care. OK henning@

More spaces

Switch filter_sets form SIMPLEQ to TAILQ, needed for upcomming stuff.

The newly introduced function filterset_free() existed already as
rde_free_set(), I just missed it when I was looking for it.
Kill rde_free_set() and use the more correct filterset_free() from now on.

Make the pftable filter set use the name2id "cache" like the route labels.
This saves 14 bytes per aspath. OK henning@

rtlabel support via filter sets. Just use "set rtlabel foobar" in filters
network and neighbor statements and the routes are labeled accordingly.
While doing that fix some mem-leaks by introducing filterset_free() and
remove the free on send option of send_filterset().
This took a bit longer because we need to carefully track the rtlabel id
refcnts or bad things may happen on reloads.
henning@ looks fine

Introduce a per prefix weight. The weight is used to tip prefixes with equal
long AS pathes in one or the other direction. It weights a prefix at a very
late stage in the decision process. This is a nice bgpd feature to traffic
engineer networks where most AS pathes are equally long.
OK henning@

Allow to modify the metrics in a relative way by prepending the number with
a '+' or '-'. e.g. set localpref +20. This is another gem from the FOSDEM
lying around on my HD gathering dust. OK henning@

Finally commit the transparent-as and nexthop no-modify stuff I wrote on the
way to FOSDEM. With transparent-as set to ye bgpd will not prepend his own
AS for sent updates. NB the neighbor needs to set "enforce neighbor-as no"
or it will not like the received AS paths. With set nexthop no-modify bgpd
will change the nexthop as done normaly.
OK henning@ man page update with help of jmc@

Add two missing breaks and suddenly using filter has no strange side effects.
Sometimes it is good to look at the rib output of a test box.

KNF

Switch from a single filter_set to a linked list of sets. With this change
it is possible to specify multiple communities. This is also the first step
to better bgpd filters. OK henning@

Don't access pointers blindly. asp is NULL for withdraws. This fixes a rde
crash noticed by Stefan Wahl and later by henning@. OK henning@

one m is enough in incoming, really ;)

Add prepend-neighbor feature. Prepend the remote-as n times similar to
prepend-self. Only for incomming UPDATEs. OK henning@

switch nexthop in struct filter_set form struct in_addr to struct bgpd_addr
OK henning@

Correctly set the MED in outgoing UPDATEs. OK henning@

Monster diff to get one step closer to IPv6 support.
Cleanup path attribute handling. First of all kill struct attr_flags, all
those infos are now in struct rde_aspath. Second move attribute parser
functions into rde.c, rde_attr.c is shared between bgpd and bgpctl.
Third reimplementation of the nexthop handling. Make it IPv6 ready and
fix some major bug relating to "set nexthop".
henning@ OK if it breaks nothing

Cleanup aspath specific functions and api. Mainly switch to a refcnt based
allocation. This helps to save a bit of RAM. looks good henning@

rename and move prefix_equal() to prefix_compare() which returns -1, 0, 1
similar to memcmp() and all other compare functions in bgpd. OK henning@

Fix reverse logic bug in the prefix filter.

implement "set nexthop blackhole" and "set nexthop reject"
blackhole/reject routes will be entered to the kernel for matching ones.
this is intended to be used with the Cymru Bogon Route Server Project
(http://www.cymru.com/BGP/bogon-rs.html) and similar services, claudio ok

First step at multiprotocol support, only partially done.
OK henning@

at least somewhat consistently name the TAILQ_ENTRYs... this confused me
more than once

extend filter language to allow basic setting of COMMUNITIES attribute.
ok claudio@

add a filter option to dump prefixes learned in UPDATEs into a PF table,
intended for building realtime BGP blacklists (e.g. with spamd);
ok claudio & henning

Add basic support for communities. Currently it is only possible to filter
on communities, e.g match from any community 24640:* set localpref 666
OK henning@

Framework for rib lookups by prefix. OK henning@

spelling

remove unneded peer pointer in struct prefix and change a in_addr_t to
struct in_addr. OK henning@

spaces

Enhance filters. prefixlen knows now 8-24 and 8><24. It is possible to use
prefix 10.0.0.0/8 prefixlen >= 8 and set localpref 100 can be set on a per
neighbor basis. OK henning@

Add support for basic filters. Nothing optimized and it has some issues but
this is a huge step forward. OK henning@

Implement filter and control message matching for ASAP.

This adds avs (ASPA validation state) which can be 'unknown', 'valid'
or 'invalid'. It behaves similar to ovs but the ASPA validation state
of paths from iBGP sessions is 'unknown' and the role of the ebgp session
is important to get the right validation state.

OK tb@

Implement ASPA validation and reload logic on ASPA set changes.

For this use the validation state (vstate) in struct prefix and
struct filterstate to store both the ASPA and ROA validity.
Introduce helper functions to set and get the various states for
struct prefix and make sure struct filterstate is also setup properly.
Change the ASPA state in rde_aspath to be AFI/AID and role independent
by storing all 4 possible outcomes. Also add a ASPA generation count
which is used to update the rde_aspath ASPA state cache on reloads.
Rework the rde_aspa.c code to be AFI/AID and role independent. Doing
this for roles is trivial but AFI switch goes deep and is so unnecessary.
The reload is combined with the ROA reload logic and renamed to RPKI
softreload.

OK tb@

Split rde_filterstate_prep() into three functions.
- rde_filterstate_init(): initialize a filterstate to default values
- rde_filterstate_copy(): copy from a filterstate into a new state object
- rde_filterstate_prep(): set filtersate based on prefix passed as argument.

This makes the code a bit easier to read.
OK tb@

Add the validation state to the filterstate struct.
Removes vstate argument from rde_filter().
Rename prefix_vstate() to prefix_roa_vstate().
OK tb@

whitespace found during a read-thru; ok claudio

Implement a max communities filter match

When max-communities X is set on a filterrule the filter will match when
more than X communities are present in the path. In other words
max-communities 0 means no communities are allowed and max-communities 3
limits it up to 3 communities.
There is max-communities, max-ext-communities and max-large-communities
for each of the 3 community attributes. These three max checks can be used
together.
OK tb@ job@

Switch from u_intX_t types to stdint.h uintX_t. Mostly mechanical with
a few reindents.
OK florian@ tb@

Implement IMSG_CTL_SHOW_SET to get information about roa-set, as-sets and
prefix-sets loaded into the RDE. For now only the number of prefixes or
asnumbers are shown plus the time since the last change was done to the table.
OK benno@

rework the overflow checks for the various relative metric adjustments.
This test no longer depends on specific overflow behaviour.
OK millert@

Refactor the filterset handling of nexthops. Instead of depending on
bgpd_process and changing the behaviour that way add a new filterset
type ACTION_SET_NEXTHOP_REF which is used when the nexthop reference
of the union is used. Adjust the RDE to convert ACTION_SET_NEXTHOP to
ACTION_SET_NEXTHOP_REF when receiving the filtersets.
OK benno@