summaryrefslogtreecommitdiff
path: root/lib/a-path.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/a-path.c')
-rw-r--r--lib/a-path.c936
1 files changed, 936 insertions, 0 deletions
diff --git a/lib/a-path.c b/lib/a-path.c
new file mode 100644
index 00000000..a7a22e40
--- /dev/null
+++ b/lib/a-path.c
@@ -0,0 +1,936 @@
+/*
+ * BIRD -- Path Operations
+ *
+ * (c) 2000 Martin Mares <mj@ucw.cz>
+ * (c) 2000 Pavel Machek <pavel@ucw.cz>
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "nest/bird.h"
+#include "nest/rt.h"
+#include "lib/attrs.h"
+#include "lib/resource.h"
+#include "lib/unaligned.h"
+#include "lib/string.h"
+#include "filter/data.h"
+
+// static inline void put_as(byte *data, u32 as) { put_u32(data, as); }
+// static inline u32 get_as(byte *data) { return get_u32(data); }
+
+#define put_as put_u32
+#define get_as get_u32
+#define BS 4 /* Default block size of ASN (autonomous system number) */
+
+#define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; })
+
+int
+as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen)
+{
+ byte *pos = data;
+ char *err_dsc = NULL;
+ uint err_val = 0;
+
+ while (len)
+ {
+ if (len < 2)
+ BAD("segment framing error", 0);
+
+ /* Process one AS path segment */
+ uint type = pos[0];
+ uint slen = 2 + bs * pos[1];
+
+ if (len < slen)
+ BAD("segment framing error", len);
+
+ switch (type)
+ {
+ case AS_PATH_SET:
+ if (!sets)
+ BAD("AS_SET segment", type);
+ break;
+
+ case AS_PATH_SEQUENCE:
+ break;
+
+ case AS_PATH_CONFED_SEQUENCE:
+ if (!confed)
+ BAD("AS_CONFED_SEQUENCE segment", type);
+ break;
+
+ case AS_PATH_CONFED_SET:
+ if (!sets || !confed)
+ BAD("AS_CONFED_SET segment", type);
+ break;
+
+ default:
+ BAD("unknown segment", type);
+ }
+
+ if (pos[1] == 0)
+ BAD("zero-length segment", type);
+
+ pos += slen;
+ len -= slen;
+ }
+
+ return 1;
+
+bad:
+ if (err)
+ if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0)
+ err[0] = 0;
+
+ return 0;
+}
+
+int
+as_path_16to32(byte *dst, const byte *src, uint len)
+{
+ byte *dst0 = dst;
+ const byte *end = src + len;
+ uint i, n;
+
+ while (src < end)
+ {
+ n = src[1];
+ *dst++ = *src++;
+ *dst++ = *src++;
+
+ for (i = 0; i < n; i++)
+ {
+ put_u32(dst, get_u16(src));
+ src += 2;
+ dst += 4;
+ }
+ }
+
+ return dst - dst0;
+}
+
+int
+as_path_32to16(byte *dst, const byte *src, uint len)
+{
+ byte *dst0 = dst;
+ const byte *end = src + len;
+ uint i, n;
+
+ while (src < end)
+ {
+ n = src[1];
+ *dst++ = *src++;
+ *dst++ = *src++;
+
+ for (i = 0; i < n; i++)
+ {
+ put_u16(dst, get_u32(src));
+ src += 4;
+ dst += 2;
+ }
+ }
+
+ return dst - dst0;
+}
+
+int
+as_path_contains_as4(const struct adata *path)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+ uint i, n;
+
+ while (pos < end)
+ {
+ n = pos[1];
+ pos += 2;
+
+ for (i = 0; i < n; i++)
+ {
+ if (get_as(pos) > 0xFFFF)
+ return 1;
+
+ pos += BS;
+ }
+ }
+
+ return 0;
+}
+
+int
+as_path_contains_confed(const struct adata *path)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+
+ while (pos < end)
+ {
+ uint type = pos[0];
+ uint slen = 2 + BS * pos[1];
+
+ if ((type == AS_PATH_CONFED_SEQUENCE) ||
+ (type == AS_PATH_CONFED_SET))
+ return 1;
+
+ pos += slen;
+ }
+
+ return 0;
+}
+
+struct adata *
+as_path_strip_confed(struct linpool *pool, const struct adata *path)
+{
+ struct adata *res = lp_alloc_adata(pool, path->length);
+ const byte *src = path->data;
+ const byte *end = src + path->length;
+ byte *dst = res->data;
+
+ while (src < end)
+ {
+ uint type = src[0];
+ uint slen = 2 + BS * src[1];
+
+ /* Copy regular segments */
+ if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE))
+ {
+ memcpy(dst, src, slen);
+ dst += slen;
+ }
+
+ src += slen;
+ }
+
+ /* Fix the result length */
+ res->length = dst - res->data;
+
+ return res;
+}
+
+struct adata *
+as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as)
+{
+ struct adata *np;
+ const byte *pos = op->data;
+ uint len = op->length;
+
+ if (len && (pos[0] == seq) && (pos[1] < 255))
+ {
+ /* Starting with matching segment => just prepend the AS number */
+ np = lp_alloc_adata(pool, len + BS);
+ np->data[0] = seq;
+ np->data[1] = pos[1] + 1;
+ put_as(np->data + 2, as);
+
+ uint dlen = BS * pos[1];
+ memcpy(np->data + 2 + BS, pos + 2, dlen);
+ ADVANCE(pos, len, 2 + dlen);
+ }
+ else
+ {
+ /* Create a new path segment */
+ np = lp_alloc_adata(pool, len + 2 + BS);
+ np->data[0] = seq;
+ np->data[1] = 1;
+ put_as(np->data + 2, as);
+ }
+
+ if (len)
+ {
+ byte *dst = np->data + 2 + BS * np->data[1];
+
+ memcpy(dst, pos, len);
+ }
+
+ return np;
+}
+
+
+struct adata *
+as_path_to_old(struct linpool *pool, const struct adata *path)
+{
+ struct adata *res = lp_alloc_adata(pool, path->length);
+ byte *pos = res->data;
+ byte *end = pos + res->length;
+ uint i, n;
+ u32 as;
+
+ /* Copy the whole path */
+ memcpy(res->data, path->data, path->length);
+
+ /* Replace 32-bit AS numbers with AS_TRANS */
+ while (pos < end)
+ {
+ n = pos[1];
+ pos += 2;
+
+ for (i = 0; i < n; i++)
+ {
+ as = get_as(pos);
+ if (as > 0xFFFF)
+ put_as(pos, AS_TRANS);
+
+ pos += BS;
+ }
+ }
+
+ return res;
+}
+
+/*
+ * Cut the path to the length @num, measured to the usual path metric. Note that
+ * AS_CONFED_* segments have zero length and must be added if they are on edge.
+ */
+struct adata *
+as_path_cut(struct linpool *pool, const struct adata *path, uint num)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+
+ while (pos < end)
+ {
+ uint t = pos[0];
+ uint l = pos[1];
+ uint n = 0;
+
+ switch (t)
+ {
+ case AS_PATH_SET: n = 1; break;
+ case AS_PATH_SEQUENCE: n = l; break;
+ case AS_PATH_CONFED_SEQUENCE: n = 0; break;
+ case AS_PATH_CONFED_SET: n = 0; break;
+ default: bug("as_path_cut: Invalid path segment");
+ }
+
+ /* Cannot add whole segment, so try partial one and finish */
+ if (num < n)
+ {
+ const byte *nend = pos;
+ if (num)
+ nend += 2 + BS * num;
+
+ struct adata *res = lp_alloc_adata(pool, path->length);
+ res->length = nend - (const byte *) path->data;
+ memcpy(res->data, path->data, res->length);
+
+ if (num)
+ {
+ byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data);
+ dpos[1] = num;
+ }
+
+ return res;
+ }
+
+ num -= n;
+ pos += 2 + BS * l;
+ }
+
+ struct adata *res = lp_alloc_adata(pool, path->length);
+ res->length = path->length;
+ memcpy(res->data, path->data, res->length);
+ return res;
+}
+
+/*
+ * Merge (concatenate) paths @p1 and @p2 and return the result.
+ * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
+ */
+const struct adata *
+as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2)
+{
+ if (p1->length == 0)
+ return p2;
+
+ if (p2->length == 0)
+ return p1;
+
+ struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
+ memcpy(res->data, p1->data, p1->length);
+ memcpy(res->data + p1->length, p2->data, p2->length);
+
+ return res;
+}
+
+void
+as_path_format(const struct adata *path, byte *bb, uint size)
+{
+ buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf;
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+ const char *ops, *cls;
+
+ b->pos[0] = 0;
+
+ while (pos < end)
+ {
+ uint type = pos[0];
+ uint len = pos[1];
+ pos += 2;
+
+ switch (type)
+ {
+ case AS_PATH_SET: ops = "{"; cls = "}"; break;
+ case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break;
+ case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break;
+ case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break;
+ default: bug("Invalid path segment");
+ }
+
+ if (ops)
+ buffer_puts(b, ops);
+
+ while (len--)
+ {
+ buffer_print(b, len ? "%u " : "%u", get_as(pos));
+ pos += BS;
+ }
+
+ if (cls)
+ buffer_puts(b, cls);
+
+ if (pos < end)
+ buffer_puts(b, " ");
+ }
+
+ /* Handle overflow */
+ if (b->pos == b->end)
+ strcpy(b->end - 12, "...");
+}
+
+int
+as_path_getlen(const struct adata *path)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+ uint res = 0;
+
+ while (pos < end)
+ {
+ uint t = pos[0];
+ uint l = pos[1];
+ uint n = 0;
+
+ switch (t)
+ {
+ case AS_PATH_SET: n = 1; break;
+ case AS_PATH_SEQUENCE: n = l; break;
+ case AS_PATH_CONFED_SEQUENCE: n = 0; break;
+ case AS_PATH_CONFED_SET: n = 0; break;
+ default: bug("as_path_getlen: Invalid path segment");
+ }
+
+ res += n;
+ pos += 2 + BS * l;
+ }
+
+ return res;
+}
+
+int
+as_path_get_last(const struct adata *path, u32 *orig_as)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+ int found = 0;
+ u32 val = 0;
+
+ while (pos < end)
+ {
+ uint type = pos[0];
+ uint len = pos[1];
+ pos += 2;
+
+ if (!len)
+ continue;
+
+ switch (type)
+ {
+ case AS_PATH_SET:
+ case AS_PATH_CONFED_SET:
+ found = 0;
+ break;
+
+ case AS_PATH_SEQUENCE:
+ case AS_PATH_CONFED_SEQUENCE:
+ val = get_as(pos + BS * (len - 1));
+ found = 1;
+ break;
+
+ default:
+ bug("Invalid path segment");
+ }
+
+ pos += BS * len;
+ }
+
+ if (found)
+ *orig_as = val;
+ return found;
+}
+
+u32
+as_path_get_last_nonaggregated(const struct adata *path)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+ u32 val = 0;
+
+ while (pos < end)
+ {
+ uint type = pos[0];
+ uint len = pos[1];
+ pos += 2;
+
+ if (!len)
+ continue;
+
+ switch (type)
+ {
+ case AS_PATH_SET:
+ case AS_PATH_CONFED_SET:
+ return val;
+
+ case AS_PATH_SEQUENCE:
+ case AS_PATH_CONFED_SEQUENCE:
+ val = get_as(pos + BS * (len - 1));
+ break;
+
+ default:
+ bug("Invalid path segment");
+ }
+
+ pos += BS * len;
+ }
+
+ return val;
+}
+
+int
+as_path_get_first(const struct adata *path, u32 *last_as)
+{
+ const u8 *p = path->data;
+
+ if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
+ return 0;
+
+ *last_as = get_as(p+2);
+ return 1;
+}
+
+int
+as_path_get_first_regular(const struct adata *path, u32 *last_as)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+
+ while (pos < end)
+ {
+ uint type = pos[0];
+ uint len = pos[1];
+ pos += 2;
+
+ switch (type)
+ {
+ case AS_PATH_SET:
+ return 0;
+
+ case AS_PATH_SEQUENCE:
+ if (len == 0)
+ return 0;
+
+ *last_as = get_as(pos);
+ return 1;
+
+ case AS_PATH_CONFED_SEQUENCE:
+ case AS_PATH_CONFED_SET:
+ break;
+
+ default:
+ bug("Invalid path segment");
+ }
+
+ pos += BS * len;
+ }
+
+ return 0;
+}
+
+int
+as_path_contains(const struct adata *path, u32 as, int min)
+{
+ const u8 *p = path->data;
+ const u8 *q = p+path->length;
+ int num = 0;
+ int i, n;
+
+ while (p<q)
+ {
+ n = p[1];
+ p += 2;
+ for(i=0; i<n; i++)
+ {
+ if (get_as(p) == as)
+ if (++num == min)
+ return 1;
+ p += BS;
+ }
+ }
+ return 0;
+}
+
+int
+as_path_match_set(const struct adata *path, const struct f_tree *set)
+{
+ const u8 *p = path->data;
+ const u8 *q = p+path->length;
+ int i, n;
+
+ while (p<q)
+ {
+ n = p[1];
+ p += 2;
+ for (i=0; i<n; i++)
+ {
+ struct f_val v = { .type = T_INT, .val.i = get_as(p)};
+ if (find_tree(set, &v))
+ return 1;
+ p += BS;
+ }
+ }
+
+ return 0;
+}
+
+const struct adata *
+as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos)
+{
+ ASSERT((set->type == T_SET) || (set->type == T_INT));
+
+ if (!path)
+ return NULL;
+
+ int len = path->length;
+ const u8 *p = path->data;
+ const u8 *q = path->data + len;
+ u8 *d, *d2;
+ int i, bt, sn, dn;
+ u8 buf[len];
+
+ d = buf;
+ while (p<q)
+ {
+ /* Read block header (type and length) */
+ bt = p[0];
+ sn = p[1];
+ dn = 0;
+ p += 2;
+ d2 = d + 2;
+
+ for (i = 0; i < sn; i++)
+ {
+ u32 as = get_as(p);
+ int match;
+
+ if (set->type == T_SET)
+ {
+ struct f_val v = { .type = T_INT, .val.i = as};
+ match = !!find_tree(set->val.t, &v);
+ }
+ else /* T_INT */
+ match = (as == set->val.i);
+
+ if (match == pos)
+ {
+ put_as(d2, as);
+ d2 += BS;
+ dn++;
+ }
+
+ p += BS;
+ }
+
+ if (dn > 0)
+ {
+ /* Nonempty block, set block header and advance */
+ d[0] = bt;
+ d[1] = dn;
+ d = d2;
+ }
+ }
+
+ uint nl = d - buf;
+ if (nl == path->length)
+ return path;
+
+ struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
+ res->length = nl;
+ memcpy(res->data, buf, nl);
+
+ return res;
+}
+
+int
+as_path_walk(const struct adata *path, uint *pos, uint *val)
+{
+ if (!path)
+ return 0;
+
+ const u8 *p = path->data;
+ const u8 *q = p + path->length;
+ uint n, x = *pos;
+
+ while (p < q)
+ {
+ n = p[1];
+ p += 2;
+
+ if (x < n)
+ {
+ *val = get_as(p + x * BS);
+ *pos += 1;
+ return 1;
+ }
+
+ p += n * BS;
+ x -= n;
+ }
+
+ return 0;
+}
+
+
+struct pm_pos
+{
+ u8 set;
+ u8 mark;
+ union
+ {
+ const char *sp;
+ u32 asn;
+ } val;
+};
+
+static int
+parse_path(const struct adata *path, struct pm_pos *pp)
+{
+ const byte *pos = path->data;
+ const byte *end = pos + path->length;
+ struct pm_pos *op = pp;
+ uint i;
+
+ while (pos < end)
+ {
+ uint type = pos[0];
+ uint len = pos[1];
+ pos += 2;
+
+ switch (type)
+ {
+ case AS_PATH_SET:
+ case AS_PATH_CONFED_SET:
+ pp->set = 1;
+ pp->mark = 0;
+ pp->val.sp = pos - 1;
+ pp++;
+
+ pos += BS * len;
+ break;
+
+ case AS_PATH_SEQUENCE:
+ case AS_PATH_CONFED_SEQUENCE:
+ for (i = 0; i < len; i++)
+ {
+ pp->set = 0;
+ pp->mark = 0;
+ pp->val.asn = get_as(pos);
+ pp++;
+
+ pos += BS;
+ }
+ break;
+
+ default:
+ bug("Invalid path segment");
+ }
+ }
+
+ return pp - op;
+}
+
+static int
+pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2)
+{
+ u32 gas;
+ if (! pos->set)
+ return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
+
+ const u8 *p = pos->val.sp;
+ int len = *p++;
+ int i;
+
+ for (i = 0; i < len; i++)
+ {
+ gas = get_as(p + i * BS);
+
+ if ((gas >= asn) && (gas <= asn2))
+ return 1;
+ }
+
+ return 0;
+}
+
+static int
+pm_match_set(const struct pm_pos *pos, const struct f_tree *set)
+{
+ struct f_val asn = { .type = T_INT };
+
+ if (! pos->set)
+ {
+ asn.val.i = pos->val.asn;
+ return !!find_tree(set, &asn);
+ }
+
+ const u8 *p = pos->val.sp;
+ int len = *p++;
+ int i;
+
+ for (i = 0; i < len; i++)
+ {
+ asn.val.i = get_as(p + i * BS);
+ if (find_tree(set, &asn))
+ return 1;
+ }
+
+ return 0;
+}
+
+static inline int
+pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2)
+{
+ return ((mask->kind == PM_QUESTION) ||
+ ((mask->kind != PM_ASN_SET) ?
+ pm_match_val(pos, asn, asn2) :
+ pm_match_set(pos, mask->set)));
+}
+
+static void
+pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh)
+{
+ int j = *i;
+
+ if (pos[j].set)
+ do { pos[j].mark = 1; j++; }
+ while ((j < plen) && pos[j].set);
+ else
+ j++;
+
+ pos[j].mark = 1;
+
+ /* Update low, high based on first and last marked pos */
+ int l = pos[*i].set ? *i : j;
+
+ *nl = (*nl < 0) ? l : MIN(*nl, l);
+ *nh = MAX(*nh, j);
+ *i = j;
+}
+
+/* AS path matching is nontrivial. Because AS path can
+ * contain sets, it is not a plain wildcard matching. A set
+ * in an AS path is interpreted as it might represent any
+ * sequence of AS numbers from that set (possibly with
+ * repetitions). So it is also a kind of a pattern,
+ * more complicated than a path mask.
+ *
+ * The algorithm for AS path matching is a variant
+ * of nondeterministic finite state machine, where
+ * positions in AS path are states, and items in
+ * path mask are input for that finite state machine.
+ * During execution of the algorithm we maintain a set
+ * of marked states - a state is marked if it can be
+ * reached by any walk through NFSM with regard to
+ * currently processed part of input. When we process
+ * next part of mask, we advance each marked state.
+ * We start with marked first position, when we
+ * run out of marked positions, we reject. When
+ * we process the whole mask, we accept if final position
+ * (auxiliary position after last real position in AS path)
+ * is marked.
+ */
+int
+as_path_match(const struct adata *path, const struct f_path_mask *mask)
+{
+ struct pm_pos pos[2048 + 1];
+ int plen = parse_path(path, pos);
+ int l, h, i, nh, nl, last, loop;
+ u32 val = 0;
+ u32 val2 = 0;
+
+ /* l and h are bound of interval of positions where
+ are marked states */
+
+ pos[plen].set = 0;
+ pos[plen].mark = 0;
+
+ l = h = loop = 0;
+ pos[0].mark = 1;
+
+ for (uint m=0; m < mask->len; m++)
+ {
+ /* We remove this mark to not step after pos[plen] */
+ pos[plen].mark = 0;
+
+ switch (mask->item[m].kind)
+ {
+ case PM_ASTERISK:
+ for (i = l; i <= plen; i++)
+ pos[i].mark = 1;
+ h = plen;
+ break;
+
+ case PM_LOOP:
+ loop = 1;
+ break;
+
+ case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */
+ val2 = val = mask->item[m].asn;
+ goto step;
+ case PM_ASN_EXPR:
+ bug("Expressions should be evaluated on AS path mask construction.");
+ case PM_ASN_RANGE:
+ val = mask->item[m].from;
+ val2 = mask->item[m].to;
+ goto step;
+ case PM_QUESTION:
+ case PM_ASN_SET:
+ step:
+ nh = nl = -1;
+ last = plen;
+ for (i = h; i >= l; i--)
+ if (pos[i].mark)
+ {
+ pos[i].mark = 0;
+ int j = i;
+
+ match:
+ if (pm_match(pos + j, &mask->item[m], val, val2))
+ {
+ pm_mark(pos, &j, plen, &nl, &nh);
+ if (loop && (j < last))
+ goto match;
+ }
+
+ last = i;
+ }
+
+ if (nh < 0)
+ return 0;
+
+ h = nh;
+ l = nl;
+ loop = 0;
+ break;
+ }
+ }
+
+ return pos[plen].mark;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-30 17:21:45 +0000