GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/bgpd/rde_decide.c Lines: 0 97 0.0 %
Date: 2017-11-13 Branches: 0 102 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: rde_decide.c,v 1.66 2017/01/25 00:15:38 claudio Exp $ */
2
3
/*
4
 * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
5
 * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
6
 *
7
 * Permission to use, copy, modify, and distribute this software for any
8
 * purpose with or without fee is hereby granted, provided that the above
9
 * copyright notice and this permission notice appear in all copies.
10
 *
11
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18
 */
19
20
#include <sys/types.h>
21
#include <sys/queue.h>
22
23
#include <string.h>
24
25
#include "bgpd.h"
26
#include "rde.h"
27
#include "log.h"
28
29
int	prefix_cmp(struct prefix *, struct prefix *);
30
/*
31
 * Decision Engine RFC implementation:
32
 *  Phase 1:
33
 *   - calculate LOCAL_PREF if needed -- EBGP or IGP learnt routes
34
 *   - IBGP routes may either use LOCAL_PREF or the local system computes
35
 *     the degree of preference
36
 *   - If the route is ineligible, the route MAY NOT serve as an input to
37
 *     the next phase of route selection
38
 *   - if the route is eligible the computed value MUST be used as the
39
 *     LOCAL_PREF value in any IBGP readvertisement
40
 *
41
 *  Phase 2:
42
 *   - If the NEXT_HOP attribute of a BGP route depicts an address that is
43
 *     not resolvable the BGP route MUST be excluded from the Phase 2 decision
44
 *     function.
45
 *   - If the AS_PATH attribute of a BGP route contains an AS loop, the BGP
46
 *     route should be excluded from the Phase 2 decision function.
47
 *   - The local BGP speaker identifies the route that has:
48
 *     a) the highest degree of preference of any route to the same set
49
 *        of destinations
50
 *     b) is the only route to that destination
51
 *     c) is selected as a result of the Phase 2 tie breaking rules
52
 *   - The local speaker MUST determine the immediate next-hop address from
53
 *     the NEXT_HOP attribute of the selected route.
54
 *   - If either the immediate next hop or the IGP cost to the NEXT_HOP changes,
55
 *     Phase 2 Route Selection MUST be performed again.
56
 *
57
 *  Route Resolvability Condition
58
 *   - A route Rte1, referencing only the intermediate network address, is
59
 *     considered resolvable if the Routing Table contains at least one
60
 *     resolvable route Rte2 that matches Rte1's intermediate network address
61
 *     and is not recursively resolved through Rte1.
62
 *   - Routes referencing interfaces are considered resolvable if the state of
63
 *     the referenced interface is up and IP processing is enabled.
64
 *
65
 *  Breaking Ties (Phase 2)
66
 *   1. Remove from consideration all routes which are not tied for having the
67
 *      smallest number of AS numbers present in their AS_PATH attributes.
68
 *      Note, that when counting this number, an AS_SET counts as 1
69
 *   2. Remove from consideration all routes which are not tied for having the
70
 *      lowest Origin number in their Origin attribute.
71
 *   3. Remove from consideration routes with less-preferred MULTI_EXIT_DISC
72
 *      attributes. MULTI_EXIT_DISC is only comparable between routes learned
73
 *      from the same neighboring AS.
74
 *   4. If at least one of the candidate routes was received via EBGP,
75
 *      remove from consideration all routes which were received via IBGP.
76
 *   5. Remove from consideration any routes with less-preferred interior cost.
77
 *      If the NEXT_HOP hop for a route is reachable, but no cost can be
78
 *      determined, then this step should be skipped.
79
 *   6. Remove from consideration all routes other than the route that was
80
 *      advertised by the BGP speaker whose BGP Identifier has the lowest value.
81
 *   7. Prefer the route received from the lowest peer address.
82
 *
83
 * Phase 3: Route Dissemination
84
 *   - All routes in the Loc-RIB are processed into Adj-RIBs-Out according
85
 *     to configured policy. A route SHALL NOT be installed in the Adj-Rib-Out
86
 *     unless the destination and NEXT_HOP described by this route may be
87
 *     forwarded appropriately by the Routing Table.
88
 */
89
90
/*
91
 * Decision Engine OUR implementation:
92
 * Our implementation has only one RIB. The filtering is done first. The
93
 * filtering calculates the preference and stores it in LOCAL_PREF (Phase 1).
94
 * Ineligible routes are flagged as ineligible via nexthop_add().
95
 * Phase 3 is done together with Phase 2.
96
 * In following cases a prefix needs to be reevaluated:
97
 *  - update of a prefix (path_update)
98
 *  - withdraw of a prefix (prefix_remove)
99
 *  - state change of the nexthop (nexthop-{in}validate)
100
 *  - state change of session (session down)
101
 */
102
103
/*
104
 * Compare two prefixes with equal pt_entry. Returns an integer greater than or
105
 * less than 0, according to whether the prefix p1 is more or less preferred
106
 * than the prefix p2. p1 should be used for the new prefix and p2 for a
107
 * already added prefix.
108
 */
109
int
110
prefix_cmp(struct prefix *p1, struct prefix *p2)
111
{
112
	struct rde_aspath	*asp1, *asp2;
113
	struct attr		*a;
114
	u_int32_t		 p1id, p2id;
115
	int			 p1cnt, p2cnt;
116
117
	if (p1 == NULL)
118
		return (-1);
119
	if (p2 == NULL)
120
		return (1);
121
122
	asp1 = p1->aspath;
123
	asp2 = p2->aspath;
124
125
	/* pathes with errors are not eligible */
126
	if (asp1->flags & F_ATTR_PARSE_ERR)
127
		return (-1);
128
	if (asp2->flags & F_ATTR_PARSE_ERR)
129
		return (1);
130
131
	/* only loop free pathes are eligible */
132
	if (asp1->flags & F_ATTR_LOOP)
133
		return (-1);
134
	if (asp2->flags & F_ATTR_LOOP)
135
		return (1);
136
137
	/* 1. check if prefix is eligible a.k.a reachable */
138
	if (asp2->nexthop != NULL && asp2->nexthop->state != NEXTHOP_REACH)
139
		return (1);
140
	if (asp1->nexthop != NULL && asp1->nexthop->state != NEXTHOP_REACH)
141
		return (-1);
142
143
	/* 2. local preference of prefix, bigger is better */
144
	if ((asp1->lpref - asp2->lpref) != 0)
145
		return (asp1->lpref - asp2->lpref);
146
147
	/* 3. aspath count, the shorter the better */
148
	if ((asp2->aspath->ascnt - asp1->aspath->ascnt) != 0)
149
		return (asp2->aspath->ascnt - asp1->aspath->ascnt);
150
151
	/* 4. origin, the lower the better */
152
	if ((asp2->origin - asp1->origin) != 0)
153
		return (asp2->origin - asp1->origin);
154
155
	/* 5. MED decision, only comparable between the same neighboring AS */
156
	if (rde_decisionflags() & BGPD_FLAG_DECISION_MED_ALWAYS ||
157
	    aspath_neighbor(asp1->aspath) == aspath_neighbor(asp2->aspath))
158
		/* lowest value wins */
159
		if ((asp2->med - asp1->med) != 0)
160
			return (asp2->med - asp1->med);
161
162
	/*
163
	 * 6. EBGP is cooler than IBGP
164
	 * It is absolutely important that the ebgp value in peer_config.ebgp
165
	 * is bigger than all other ones (IBGP, confederations)
166
	 */
167
	if (asp1->peer->conf.ebgp != asp2->peer->conf.ebgp) {
168
		if (asp1->peer->conf.ebgp) /* p1 is EBGP other is lower */
169
			return 1;
170
		else if (asp2->peer->conf.ebgp) /* p2 is EBGP */
171
			return -1;
172
	}
173
174
	/*
175
	 * 7. local tie-breaker, this weight is here to tip equal long AS
176
	 * paths in one or the other direction. It happens more and more
177
	 * that AS paths are equally long and so traffic engineering needs
178
	 * a metric that weights a prefix at a very late stage in the
179
	 * decision process.
180
	 */
181
	if ((asp1->weight - asp2->weight) != 0)
182
		return (asp1->weight - asp2->weight);
183
184
	/* 8. nexthop costs. NOT YET -> IGNORE */
185
186
	/*
187
	 * 9. older route (more stable) wins but only if route-age
188
	 * evaluation is enabled.
189
	 */
190
	if (rde_decisionflags() & BGPD_FLAG_DECISION_ROUTEAGE)
191
		if ((p2->lastchange - p1->lastchange) != 0)
192
			return (p2->lastchange - p1->lastchange);
193
194
	/* 10. lowest BGP Id wins, use ORIGINATOR_ID if present */
195
	if ((a = attr_optget(asp1, ATTR_ORIGINATOR_ID)) != NULL) {
196
		memcpy(&p1id, a->data, sizeof(p1id));
197
		p1id = ntohl(p1id);
198
	} else
199
		p1id = asp1->peer->remote_bgpid;
200
	if ((a = attr_optget(asp2, ATTR_ORIGINATOR_ID)) != NULL) {
201
		memcpy(&p2id, a->data, sizeof(p2id));
202
		p2id = ntohl(p2id);
203
	} else
204
		p2id = asp2->peer->remote_bgpid;
205
	if ((p2id - p1id) != 0)
206
		return (p2id - p1id);
207
208
	/* 11. compare CLUSTER_LIST length, shorter is better */
209
	p1cnt = p2cnt = 0;
210
	if ((a = attr_optget(asp1, ATTR_CLUSTER_LIST)) != NULL)
211
		p1cnt = a->len / sizeof(u_int32_t);
212
	if ((a = attr_optget(asp2, ATTR_CLUSTER_LIST)) != NULL)
213
		p2cnt = a->len / sizeof(u_int32_t);
214
	if ((p2cnt - p1cnt) != 0)
215
		return (p2cnt - p1cnt);
216
217
	/* 12. lowest peer address wins (IPv4 is better than IPv6) */
218
	if (memcmp(&p1->aspath->peer->remote_addr,
219
	    &p2->aspath->peer->remote_addr,
220
	    sizeof(p1->aspath->peer->remote_addr)) != 0)
221
		return (-memcmp(&p1->aspath->peer->remote_addr,
222
		    &p2->aspath->peer->remote_addr,
223
		    sizeof(p1->aspath->peer->remote_addr)));
224
225
	/* 13. for announced prefixes prefer dynamic routes */
226
	if ((asp1->flags & F_ANN_DYNAMIC) != (asp2->flags & F_ANN_DYNAMIC)) {
227
		if (asp1->flags & F_ANN_DYNAMIC)
228
			return (1);
229
		else
230
			return (-1);
231
	}
232
233
	fatalx("Uh, oh a politician in the decision process");
234
	/* NOTREACHED */
235
}
236
237
/*
238
 * Find the correct place to insert the prefix in the prefix list.
239
 * If the active prefix has changed we need to send an update.
240
 * The to evaluate prefix must not be in the prefix list.
241
 */
242
void
243
prefix_evaluate(struct prefix *p, struct rib_entry *re)
244
{
245
	struct prefix	*xp;
246
247
	if (re_rib(re)->flags & F_RIB_NOEVALUATE || rde_noevaluate()) {
248
		/* decision process is turned off */
249
		if (p != NULL)
250
			LIST_INSERT_HEAD(&re->prefix_h, p, rib_l);
251
		if (re->active != NULL) {
252
			re->active->aspath->active_cnt--;
253
			re->active = NULL;
254
		}
255
		return;
256
	}
257
258
	if (p != NULL) {
259
		if (LIST_EMPTY(&re->prefix_h))
260
			LIST_INSERT_HEAD(&re->prefix_h, p, rib_l);
261
		else {
262
			LIST_FOREACH(xp, &re->prefix_h, rib_l)
263
				if (prefix_cmp(p, xp) > 0) {
264
					LIST_INSERT_BEFORE(xp, p, rib_l);
265
					break;
266
				} else if (LIST_NEXT(xp, rib_l) == NULL) {
267
					/* if xp last element ... */
268
					LIST_INSERT_AFTER(xp, p, rib_l);
269
					break;
270
				}
271
		}
272
	}
273
274
	xp = LIST_FIRST(&re->prefix_h);
275
	if (xp == NULL || xp->aspath->flags & (F_ATTR_LOOP|F_ATTR_PARSE_ERR) ||
276
	    (xp->aspath->nexthop != NULL &&
277
	    xp->aspath->nexthop->state != NEXTHOP_REACH))
278
		/* xp is ineligible */
279
		xp = NULL;
280
281
	if (re->active != xp) {
282
		/* need to generate an update */
283
		if (re->active != NULL)
284
			re->active->aspath->active_cnt--;
285
286
		/*
287
		 * Send update with remove for re->active and add for xp
288
		 * but remember that xp may be NULL aka ineligible.
289
		 * Additional decision may be made by the called functions.
290
		 */
291
		rde_generate_updates(re_rib(re), xp, re->active);
292
		if ((re_rib(re)->flags & F_RIB_NOFIB) == 0)
293
			rde_send_kroute(re_rib(re), xp, re->active);
294
295
		re->active = xp;
296
		if (xp != NULL)
297
			xp->aspath->active_cnt++;
298
	}
299
}