File: [local] / src / usr.sbin / bgpd / rde_prefix.c (download)
Revision 1.50, Wed Jul 12 14:45:43 2023 UTC (10 months, 3 weeks ago) by claudio
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE, OPENBSD_7_5, OPENBSD_7_4_BASE, OPENBSD_7_4, HEAD Changes since 1.49: +58 -90 lines
Update OpenBGPD to use new ibuf API.
This replaces the old way of using a static buffer and a len to build
UPDATEs with a pure ibuf solution. The result is much cleaner and a lot
of almost duplicate code can be removed because often a version for ibufs
and one for this static buffer was implemented (e.g. for mrt or bgpctl).
With and OK tb@
|
/* $OpenBSD: rde_prefix.c,v 1.50 2023/07/12 14:45:43 claudio Exp $ */
/*
* Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
#include <sys/types.h>
#include <sys/queue.h>
#include <endian.h>
#include <errno.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "bgpd.h"
#include "rde.h"
#include "log.h"
/*
* Prefix Table functions:
* pt_add: create new prefix and link it into the prefix table
* pt_remove: Checks if there is no bgp prefix linked to the prefix,
* unlinks from the prefix table and frees the pt_entry.
* pt_get: get a prefix/prefixlen entry. While pt_lookup searches for the
* best matching prefix pt_get only finds the prefix/prefixlen
* entry. The speed of pt_get is important for the bgp updates.
* pt_getaddr: convert the address into a struct bgpd_addr.
* pt_lookup: lookup a IP in the prefix table. Mainly for "show ip bgp".
* pt_empty: returns true if there is no bgp prefix linked to the pt_entry.
* pt_init: initialize prefix table.
* pt_alloc: allocate a AF specific pt_entry. Internal function.
* pt_free: free a pt_entry. Internal function.
*/
/* internal prototypes */
static struct pt_entry *pt_alloc(struct pt_entry *, int len);
static void pt_free(struct pt_entry *);
struct pt_entry4 {
RB_ENTRY(pt_entry) pt_e;
uint8_t aid;
uint8_t prefixlen;
uint16_t len;
uint32_t refcnt;
struct in_addr prefix4;
};
struct pt_entry6 {
RB_ENTRY(pt_entry) pt_e;
uint8_t aid;
uint8_t prefixlen;
uint16_t len;
uint32_t refcnt;
struct in6_addr prefix6;
};
struct pt_entry_vpn4 {
RB_ENTRY(pt_entry) pt_e;
uint8_t aid;
uint8_t prefixlen;
uint16_t len;
uint32_t refcnt;
uint64_t rd;
struct in_addr prefix4;
uint8_t labelstack[21];
uint8_t labellen;
uint8_t pad1;
uint8_t pad2;
};
struct pt_entry_vpn6 {
RB_ENTRY(pt_entry) pt_e;
uint8_t aid;
uint8_t prefixlen;
uint16_t len;
uint32_t refcnt;
uint64_t rd;
struct in6_addr prefix6;
uint8_t labelstack[21];
uint8_t labellen;
uint8_t pad1;
uint8_t pad2;
};
struct pt_entry_flow {
RB_ENTRY(pt_entry) pt_e;
uint8_t aid;
uint8_t prefixlen; /* unused ??? */
uint16_t len;
uint32_t refcnt;
uint64_t rd;
uint8_t flow[1]; /* NLRI */
};
#define PT_FLOW_SIZE (offsetof(struct pt_entry_flow, flow))
RB_HEAD(pt_tree, pt_entry);
RB_PROTOTYPE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
RB_GENERATE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
struct pt_tree pttable;
void
pt_init(void)
{
RB_INIT(&pttable);
}
void
pt_shutdown(void)
{
if (!RB_EMPTY(&pttable))
log_debug("pt_shutdown: tree is not empty.");
}
void
pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
{
struct pt_entry_flow *pflow;
memset(addr, 0, sizeof(struct bgpd_addr));
addr->aid = pte->aid;
switch (addr->aid) {
case AID_INET:
addr->v4 = ((struct pt_entry4 *)pte)->prefix4;
break;
case AID_INET6:
addr->v6 = ((struct pt_entry6 *)pte)->prefix6;
/* XXX scope_id ??? */
break;
case AID_VPN_IPv4:
addr->v4 = ((struct pt_entry_vpn4 *)pte)->prefix4;
addr->rd = ((struct pt_entry_vpn4 *)pte)->rd;
addr->labellen = ((struct pt_entry_vpn4 *)pte)->labellen;
memcpy(addr->labelstack,
((struct pt_entry_vpn4 *)pte)->labelstack,
addr->labellen);
break;
case AID_VPN_IPv6:
addr->v6 = ((struct pt_entry_vpn6 *)pte)->prefix6;
addr->rd = ((struct pt_entry_vpn6 *)pte)->rd;
addr->labellen = ((struct pt_entry_vpn6 *)pte)->labellen;
memcpy(addr->labelstack,
((struct pt_entry_vpn6 *)pte)->labelstack,
addr->labellen);
break;
case AID_FLOWSPECv4:
case AID_FLOWSPECv6:
pflow = (struct pt_entry_flow *)pte;
flowspec_get_addr(pflow->flow, pflow->len - PT_FLOW_SIZE,
FLOWSPEC_TYPE_DEST, addr->aid == AID_FLOWSPECv6,
addr, &pflow->prefixlen, NULL);
break;
default:
fatalx("pt_getaddr: unknown af");
}
}
int
pt_getflowspec(struct pt_entry *pte, uint8_t **flow)
{
struct pt_entry_flow *pflow;
switch (pte->aid) {
case AID_FLOWSPECv4:
case AID_FLOWSPECv6:
pflow = (struct pt_entry_flow *)pte;
*flow = pflow->flow;
return pflow->len - PT_FLOW_SIZE;
default:
fatalx("pt_getflowspec: unknown af");
}
}
struct pt_entry *
pt_fill(struct bgpd_addr *prefix, int prefixlen)
{
static struct pt_entry4 pte4;
static struct pt_entry6 pte6;
static struct pt_entry_vpn4 pte_vpn4;
static struct pt_entry_vpn6 pte_vpn6;
switch (prefix->aid) {
case AID_INET:
memset(&pte4, 0, sizeof(pte4));
pte4.len = sizeof(pte4);
pte4.refcnt = UINT32_MAX;
pte4.aid = prefix->aid;
if (prefixlen > 32)
fatalx("pt_fill: bad IPv4 prefixlen");
inet4applymask(&pte4.prefix4, &prefix->v4, prefixlen);
pte4.prefixlen = prefixlen;
return ((struct pt_entry *)&pte4);
case AID_INET6:
memset(&pte6, 0, sizeof(pte6));
pte6.len = sizeof(pte6);
pte6.refcnt = UINT32_MAX;
pte6.aid = prefix->aid;
if (prefixlen > 128)
fatalx("pt_fill: bad IPv6 prefixlen");
inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
pte6.prefixlen = prefixlen;
return ((struct pt_entry *)&pte6);
case AID_VPN_IPv4:
memset(&pte_vpn4, 0, sizeof(pte_vpn4));
pte_vpn4.len = sizeof(pte_vpn4);
pte_vpn4.refcnt = UINT32_MAX;
pte_vpn4.aid = prefix->aid;
if (prefixlen > 32)
fatalx("pt_fill: bad IPv4 prefixlen");
inet4applymask(&pte_vpn4.prefix4, &prefix->v4, prefixlen);
pte_vpn4.prefixlen = prefixlen;
pte_vpn4.rd = prefix->rd;
pte_vpn4.labellen = prefix->labellen;
memcpy(pte_vpn4.labelstack, prefix->labelstack,
prefix->labellen);
return ((struct pt_entry *)&pte_vpn4);
case AID_VPN_IPv6:
memset(&pte_vpn6, 0, sizeof(pte_vpn6));
pte_vpn6.len = sizeof(pte_vpn6);
pte_vpn6.refcnt = UINT32_MAX;
pte_vpn6.aid = prefix->aid;
if (prefixlen > 128)
fatalx("pt_get: bad IPv6 prefixlen");
inet6applymask(&pte_vpn6.prefix6, &prefix->v6, prefixlen);
pte_vpn6.prefixlen = prefixlen;
pte_vpn6.rd = prefix->rd;
pte_vpn6.labellen = prefix->labellen;
memcpy(pte_vpn6.labelstack, prefix->labelstack,
prefix->labellen);
return ((struct pt_entry *)&pte_vpn6);
default:
fatalx("pt_fill: unknown af");
}
}
struct pt_entry *
pt_get(struct bgpd_addr *prefix, int prefixlen)
{
struct pt_entry *pte;
pte = pt_fill(prefix, prefixlen);
return RB_FIND(pt_tree, &pttable, pte);
}
struct pt_entry *
pt_add(struct bgpd_addr *prefix, int prefixlen)
{
struct pt_entry *p = NULL;
p = pt_fill(prefix, prefixlen);
p = pt_alloc(p, p->len);
if (RB_INSERT(pt_tree, &pttable, p) != NULL)
fatalx("pt_add: insert failed");
return (p);
}
struct pt_entry *
pt_get_flow(struct flowspec *f)
{
struct pt_entry *needle;
union {
struct pt_entry_flow flow;
uint8_t buf[4096];
} x;
needle = (struct pt_entry *)&x.flow;
memset(needle, 0, PT_FLOW_SIZE);
needle->aid = f->aid;
needle->len = f->len + PT_FLOW_SIZE;
memcpy(((struct pt_entry_flow *)needle)->flow, f->data, f->len);
return RB_FIND(pt_tree, &pttable, (struct pt_entry *)needle);
}
struct pt_entry *
pt_add_flow(struct flowspec *f)
{
struct pt_entry *p;
int len = f->len + PT_FLOW_SIZE;
p = malloc(len);
if (p == NULL)
fatal(__func__);
rdemem.pt_cnt[f->aid]++;
rdemem.pt_size[f->aid] += len;
memset(p, 0, PT_FLOW_SIZE);
p->len = len;
p->aid = f->aid;
memcpy(((struct pt_entry_flow *)p)->flow, f->data, f->len);
if (RB_INSERT(pt_tree, &pttable, p) != NULL)
fatalx("pt_add: insert failed");
return (p);
}
void
pt_remove(struct pt_entry *pte)
{
if (pte->refcnt != 0)
fatalx("pt_remove: entry still holds references");
if (RB_REMOVE(pt_tree, &pttable, pte) == NULL)
log_warnx("pt_remove: remove failed.");
pt_free(pte);
}
struct pt_entry *
pt_lookup(struct bgpd_addr *addr)
{
struct pt_entry *p;
int i;
switch (addr->aid) {
case AID_INET:
case AID_VPN_IPv4:
i = 32;
break;
case AID_INET6:
case AID_VPN_IPv6:
i = 128;
break;
default:
fatalx("pt_lookup: unknown af");
}
for (; i >= 0; i--) {
p = pt_get(addr, i);
if (p != NULL)
return (p);
}
return (NULL);
}
int
pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b)
{
const struct pt_entry4 *a4, *b4;
const struct pt_entry6 *a6, *b6;
const struct pt_entry_vpn4 *va4, *vb4;
const struct pt_entry_vpn6 *va6, *vb6;
const struct pt_entry_flow *af, *bf;
int i;
if (a->aid > b->aid)
return (1);
if (a->aid < b->aid)
return (-1);
switch (a->aid) {
case AID_INET:
a4 = (const struct pt_entry4 *)a;
b4 = (const struct pt_entry4 *)b;
if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr))
return (1);
if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr))
return (-1);
if (a4->prefixlen > b4->prefixlen)
return (1);
if (a4->prefixlen < b4->prefixlen)
return (-1);
return (0);
case AID_INET6:
a6 = (const struct pt_entry6 *)a;
b6 = (const struct pt_entry6 *)b;
i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr));
if (i > 0)
return (1);
if (i < 0)
return (-1);
if (a6->prefixlen < b6->prefixlen)
return (-1);
if (a6->prefixlen > b6->prefixlen)
return (1);
return (0);
case AID_VPN_IPv4:
va4 = (const struct pt_entry_vpn4 *)a;
vb4 = (const struct pt_entry_vpn4 *)b;
if (be64toh(va4->rd) > be64toh(vb4->rd))
return (1);
if (be64toh(va4->rd) < be64toh(vb4->rd))
return (-1);
if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr))
return (1);
if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr))
return (-1);
if (va4->prefixlen > vb4->prefixlen)
return (1);
if (va4->prefixlen < vb4->prefixlen)
return (-1);
return (0);
case AID_VPN_IPv6:
va6 = (const struct pt_entry_vpn6 *)a;
vb6 = (const struct pt_entry_vpn6 *)b;
if (be64toh(va6->rd) > be64toh(vb6->rd))
return (1);
if (be64toh(va6->rd) < be64toh(vb6->rd))
return (-1);
i = memcmp(&va6->prefix6, &vb6->prefix6,
sizeof(struct in6_addr));
if (i > 0)
return (1);
if (i < 0)
return (-1);
if (va6->prefixlen > vb6->prefixlen)
return (1);
if (va6->prefixlen < vb6->prefixlen)
return (-1);
return (0);
case AID_FLOWSPECv4:
case AID_FLOWSPECv6:
af = (const struct pt_entry_flow *)a;
bf = (const struct pt_entry_flow *)b;
return flowspec_cmp(af->flow, af->len - PT_FLOW_SIZE,
bf->flow, bf->len - PT_FLOW_SIZE,
a->aid == AID_FLOWSPECv6);
default:
fatalx("pt_prefix_cmp: unknown af");
}
return (-1);
}
/*
* Returns a pt_entry cloned from the one passed in.
* Function may not return on failure.
*/
static struct pt_entry *
pt_alloc(struct pt_entry *op, int len)
{
struct pt_entry *p;
p = malloc(len);
if (p == NULL)
fatal("pt_alloc");
rdemem.pt_cnt[op->aid]++;
rdemem.pt_size[op->aid] += len;
memcpy(p, op, len);
p->refcnt = 0;
return (p);
}
static void
pt_free(struct pt_entry *pte)
{
rdemem.pt_cnt[pte->aid]--;
rdemem.pt_size[pte->aid] -= pte->len;
free(pte);
}
/* dump a prefix into specified buffer */
int
pt_writebuf(struct ibuf *buf, struct pt_entry *pte, int withdraw,
int add_path, uint32_t pathid)
{
struct pt_entry_vpn4 *pvpn4 = (struct pt_entry_vpn4 *)pte;
struct pt_entry_vpn6 *pvpn6 = (struct pt_entry_vpn6 *)pte;
struct pt_entry_flow *pflow = (struct pt_entry_flow *)pte;
struct ibuf *tmp;
int flowlen, psize;
uint8_t plen;
if ((tmp = ibuf_dynamic(32, UINT16_MAX)) == NULL)
goto fail;
if (add_path) {
if (ibuf_add_n32(tmp, pathid) == -1)
goto fail;
}
switch (pte->aid) {
case AID_INET:
case AID_INET6:
plen = pte->prefixlen;
if (ibuf_add_n8(tmp, plen) == -1)
goto fail;
if (ibuf_add(tmp, pte->data, PREFIX_SIZE(plen) - 1) == -1)
goto fail;
break;
case AID_VPN_IPv4:
plen = pvpn4->prefixlen;
psize = PREFIX_SIZE(plen) - 1;
plen += sizeof(pvpn4->rd) * 8;
if (withdraw) {
/* withdraw have one compat label as placeholder */
plen += 3 * 8;
} else {
plen += pvpn4->labellen * 8;
}
if (ibuf_add_n8(tmp, plen) == -1)
goto fail;
if (withdraw) {
/* magic compatibility label as per rfc8277 */
if (ibuf_add_n8(tmp, 0x80) == -1 ||
ibuf_add_zero(tmp, 2) == -1)
goto fail;
} else {
if (ibuf_add(tmp, &pvpn4->labelstack,
pvpn4->labellen) == -1)
goto fail;
}
if (ibuf_add(tmp, &pvpn4->rd, sizeof(pvpn4->rd)) == -1 ||
ibuf_add(tmp, &pvpn4->prefix4, psize) == -1)
goto fail;
break;
case AID_VPN_IPv6:
plen = pvpn6->prefixlen;
psize = PREFIX_SIZE(plen) - 1;
plen += sizeof(pvpn6->rd) * 8;
if (withdraw) {
/* withdraw have one compat label as placeholder */
plen += 3 * 8;
} else {
plen += pvpn6->labellen * 8;
}
if (ibuf_add_n8(tmp, plen) == -1)
goto fail;
if (withdraw) {
/* magic compatibility label as per rfc8277 */
if (ibuf_add_n8(tmp, 0x80) == -1 ||
ibuf_add_zero(tmp, 2) == -1)
goto fail;
} else {
if (ibuf_add(tmp, &pvpn6->labelstack,
pvpn6->labellen) == -1)
goto fail;
}
if (ibuf_add(tmp, &pvpn6->rd, sizeof(pvpn6->rd)) == -1 ||
ibuf_add(tmp, &pvpn6->prefix6, psize) == -1)
goto fail;
break;
case AID_FLOWSPECv4:
case AID_FLOWSPECv6:
flowlen = pflow->len - PT_FLOW_SIZE;
if (flowlen < FLOWSPEC_LEN_LIMIT) {
if (ibuf_add_n8(tmp, flowlen) == -1)
goto fail;
} else {
if (ibuf_add_n8(tmp, 0xf0 | (flowlen >> 8)) == -1 ||
ibuf_add_n8(tmp, flowlen) == -1)
goto fail;
}
if (ibuf_add(tmp, &pflow->flow, flowlen) == -1)
goto fail;
break;
default:
goto fail;
}
if (ibuf_add_buf(buf, tmp) == -1)
goto fail;
ibuf_free(tmp);
return 0;
fail:
ibuf_free(tmp);
return -1;
}