From 11cb620266035ffbe17b21c4a174380cb8b6a521 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 26 Oct 2008 22:36:08 +0100
Subject: Implementation of 4B ASN support for BGP

---
 proto/bgp/packets.c | 151 ++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 116 insertions(+), 35 deletions(-)

(limited to 'proto/bgp/packets.c')

diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 2e6f0b60..0dd920e4 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -12,6 +12,7 @@
 #include "nest/iface.h"
 #include "nest/protocol.h"
 #include "nest/route.h"
+#include "nest/attrs.h"
 #include "conf/conf.h"
 #include "lib/unaligned.h"
 #include "lib/socket.h"
@@ -30,33 +31,64 @@ bgp_create_notification(struct bgp_conn *conn, byte *buf)
   return buf + 2 + conn->notify_size;
 }
 
+#ifdef IPV6
+static byte *
+bgp_put_cap_ipv6(struct bgp_conn *conn UNUSED, byte *buf)
+{
+  *buf++ = 1;		/* Capability 1: Multiprotocol extensions */
+  *buf++ = 4;		/* Capability data length */
+  *buf++ = 0;		/* We support AF IPv6 */
+  *buf++ = BGP_AF_IPV6;
+  *buf++ = 0;		/* RFU */
+  *buf++ = 1;		/* and SAFI 1 */
+  return buf;
+}
+#endif
+
+static byte *
+bgp_put_cap_as4(struct bgp_conn *conn, byte *buf)
+{
+  *buf++ = 65;		/* Capability 65: Support for 4-octet AS number */
+  *buf++ = 4;		/* Capability data length */
+  put_u32(buf, conn->bgp->local_as);
+  return buf + 4;
+}
+
 static byte *
 bgp_create_open(struct bgp_conn *conn, byte *buf)
 {
   struct bgp_proto *p = conn->bgp;
+  byte *cap;
+  int cap_len;
 
   BGP_TRACE(D_PACKETS, "Sending OPEN(ver=%d,as=%d,hold=%d,id=%08x)",
 	    BGP_VERSION, p->local_as, p->cf->hold_time, p->local_id);
   buf[0] = BGP_VERSION;
-  put_u16(buf+1, p->local_as);
+  put_u16(buf+1, (p->local_as < 0xFFFF) ? p->local_as : AS_TRANS);
   put_u16(buf+3, p->cf->hold_time);
   put_u32(buf+5, p->local_id);
-#ifndef IPV6
-  buf[9] = 0;				/* No optional parameters */
-  return buf+10;
-#else
-  buf += 9;
-  *buf++ = 8;		/* Optional params len */
-  *buf++ = 2;		/* Option: Capability list */
-  *buf++ = 6;		/* Option length */
-  *buf++ = 1;		/* Capability 1: Multiprotocol extensions */
-  *buf++ = 4;		/* Capability data length */
-  *buf++ = 0;		/* We support AF IPv6 */
-  *buf++ = BGP_AF_IPV6;
-  *buf++ = 0;		/* RFU */
-  *buf++ = 1;		/* and SAFI 1 */
-  return buf;
+  /* Skipped 3 B for length field and Capabilities parameter header */
+  cap = buf + 12;
+
+#ifdef IPV6
+  cap = bgp_put_cap_ipv6(conn, cap);
 #endif
+  if (bgp_as4_support)
+    cap = bgp_put_cap_as4(conn, cap);
+
+  cap_len = cap - buf - 12;
+  if (cap_len > 0)
+    {
+      buf[9]  = cap_len + 2;	/* Optional params len */
+      buf[10] = 2;		/* Option: Capability list */
+      buf[11] = cap_len;	/* Option length */
+      return cap;
+    }
+  else
+    {
+      buf[9] = 0;		/* No optional parameters */
+      return buf + 10;
+    }
 }
 
 static unsigned int
@@ -118,7 +150,7 @@ bgp_create_update(struct bgp_conn *conn, byte *buf)
 	      continue;
 	    }
 	  DBG("Processing bucket %p\n", buck);
-	  a_size = bgp_encode_attrs(w+2, buck->eattrs, 1024);
+	  a_size = bgp_encode_attrs(p, w+2, buck->eattrs, 1024);
 	  put_u16(w, a_size);
 	  w += a_size + 2;
 	  r_size = bgp_encode_prefixes(p, w, buck, remains - a_size);
@@ -166,7 +198,7 @@ bgp_create_update(struct bgp_conn *conn, byte *buf)
       *tmp++ = BGP_AF_IPV6;
       *tmp++ = 1;
       ea->attrs[0].u.ptr->length = bgp_encode_prefixes(p, tmp, buck, remains-11);
-      size = bgp_encode_attrs(w, ea, remains);
+      size = bgp_encode_attrs(p, w, ea, remains);
       w += size;
       remains -= size;
     }
@@ -183,7 +215,7 @@ bgp_create_update(struct bgp_conn *conn, byte *buf)
 	      continue;
 	    }
 	  DBG("Processing bucket %p\n", buck);
-	  size = bgp_encode_attrs(w, buck->eattrs, 1024);
+	  size = bgp_encode_attrs(p, w, buck->eattrs, 1024);
 	  w += size;
 	  remains -= size;
 	  tstart = tmp = bgp_attach_attr(&ea, bgp_linpool, BA_MP_REACH_NLRI, remains-8);
@@ -230,7 +262,7 @@ bgp_create_update(struct bgp_conn *conn, byte *buf)
 	  *tmp++ = 0;			/* No SNPA information */
 	  tmp += bgp_encode_prefixes(p, tmp, buck, remains - (8+3+32+1));
 	  ea->attrs[0].u.ptr->length = tmp - tstart;
-	  w += bgp_encode_attrs(w, ea, remains);
+	  w += bgp_encode_attrs(p, w, ea, remains);
 	  break;
 	}
     }
@@ -353,9 +385,49 @@ bgp_tx(sock *sk)
     ;
 }
 
+/* Capatibility negotiation as per RFC 2842 */
+
+void
+bgp_parse_capabilities(struct bgp_conn *conn, byte *opt, int len)
+{
+  struct bgp_proto *p = conn->bgp;
+  int cl;
+  u32 as;
+
+  while (len > 0)
+    {
+      if (len < 2 || len < 2 + opt[1])
+	goto err;
+      
+      cl = opt[1];
+
+      switch (opt[0])
+	{
+	case 65:
+	  if (cl != 4)
+	    goto err;
+	  p->as4_support = 1;
+	  if (bgp_as4_support)
+	    conn->advertised_as = get_u32(opt + 2);
+	  break;
+
+	  /* We can safely ignore all other capabilities */
+	}
+      len -= 2 + cl;
+      opt += 2 + cl;
+    }
+  return;
+
+    err:
+  bgp_error(conn, 2, 0, NULL, 0);
+  return;
+}
+
 static int
 bgp_parse_options(struct bgp_conn *conn, byte *opt, int len)
 {
+  int ol;
+
   while (len > 0)
     {
       if (len < 2 || len < 2 + opt[1])
@@ -369,12 +441,14 @@ bgp_parse_options(struct bgp_conn *conn, byte *opt, int len)
 	DBG("\n");
       }
 #endif
+
+      ol = opt[1];
       switch (opt[0])
 	{
 	case 2:
-	  /* Capatibility negotiation as per RFC 2842 */
-	  /* We can safely ignore all capabilities announced */
+	  bgp_parse_capabilities(conn, opt + 2, ol);
 	  break;
+
 	default:
 	  /*
 	   *  BGP specs don't tell us to send which option
@@ -382,11 +456,11 @@ bgp_parse_options(struct bgp_conn *conn, byte *opt, int len)
 	   *  to do so. Also, capability negotiation with
 	   *  Cisco routers doesn't work without that.
 	   */
-	  bgp_error(conn, 2, 4, opt, opt[1]);
+	  bgp_error(conn, 2, 4, opt, ol);
 	  return 0;
 	}
-      len -= 2 + opt[1];
-      opt += 2 + opt[1];
+      len -= 2 + ol;
+      opt += 2 + ol;
     }
   return 0;
 }
@@ -397,7 +471,7 @@ bgp_rx_open(struct bgp_conn *conn, byte *pkt, int len)
   struct bgp_conn *other;
   struct bgp_proto *p = conn->bgp;
   struct bgp_config *cf = p->cf;
-  unsigned as, hold;
+  unsigned hold;
   u32 id;
 
   /* Check state */
@@ -409,20 +483,27 @@ bgp_rx_open(struct bgp_conn *conn, byte *pkt, int len)
     { bgp_error(conn, 1, 2, pkt+16, 2); return; }
   if (pkt[19] != BGP_VERSION)
     { bgp_error(conn, 2, 1, pkt+19, 1); return; } /* RFC 1771 says 16 bits, draft-09 tells to use 8 */
-  as = get_u16(pkt+20);
+  conn->advertised_as = get_u16(pkt+20);
   hold = get_u16(pkt+22);
   id = get_u32(pkt+24);
-  BGP_TRACE(D_PACKETS, "Got OPEN(as=%d,hold=%d,id=%08x)", as, hold, id);
-  if (cf->remote_as && as != p->remote_as)
-    { bgp_error(conn, 2, 2, pkt+20, -2); return; }
-  if (hold > 0 && hold < 3)
-    { bgp_error(conn, 2, 6, pkt+22, 2); return; }
-  p->remote_id = id;
+  BGP_TRACE(D_PACKETS, "Got OPEN(as=%d,hold=%d,id=%08x)", conn->advertised_as, hold, id);
+
+  p->remote_id = id; // ???
   if (bgp_parse_options(conn, pkt+29, pkt[28]))
     return;
+
+  if (hold > 0 && hold < 3)
+    { bgp_error(conn, 2, 6, pkt+22, 2); return; }
+
   if (!id || id == 0xffffffff || id == p->local_id)
     { bgp_error(conn, 2, 3, pkt+24, -4); return; }
 
+
+  if (conn->advertised_as != p->remote_as)
+    {
+      bgp_error(conn, 2, 2, (byte *) &(conn->advertised_as), -4); return;
+    }
+
   /* Check the other connection */
   other = (conn == &p->outgoing_conn) ? &p->incoming_conn : &p->outgoing_conn;
   switch (other->state)
@@ -463,7 +544,7 @@ bgp_rx_open(struct bgp_conn *conn, byte *pkt, int len)
   else
     conn->hold_time = p->cf->hold_time;
   conn->keepalive_time = p->cf->keepalive_time ? : conn->hold_time / 3;
-  p->remote_as = as;
+  // p->remote_as = conn->advertised_as;
   p->remote_id = id;
   DBG("BGP: Hold timer set to %d, keepalive to %d, AS to %d, ID to %x\n", conn->hold_time, conn->keepalive_time, p->remote_as, p->remote_id);
 
@@ -720,7 +801,7 @@ static struct {
   { 2, 4, "Unsupported optional parameter" },
   { 2, 5, "Authentication failure" },
   { 2, 6, "Unacceptable hold time" },
-  { 2, 7, "Required capability missing" }, /* capability negotiation draft */
+  { 2, 7, "Required capability missing" }, /* [RFC3392] */
   { 3, 0, "Invalid UPDATE message" },
   { 3, 1, "Malformed attribute list" },
   { 3, 2, "Unrecognized well-known attribute" },
-- 
cgit v1.2.3


From 4847a894bf7d4852325c3f1ea4bb4890054a1f66 Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 26 Oct 2008 22:45:09 +0100
Subject: Implementation of route reflection for BGP

---
 filter/filter.h     |   1 +
 nest/a-set.c        |   8 +-
 nest/attrs.h        |   3 +
 proto/bgp/attrs.c   | 223 +++++++++++++++++++++++++++++++++++++---------------
 proto/bgp/bgp.c     |   9 +++
 proto/bgp/bgp.h     |  10 ++-
 proto/bgp/config.Y  |   6 +-
 proto/bgp/packets.c |   6 +-
 8 files changed, 195 insertions(+), 71 deletions(-)

(limited to 'proto/bgp/packets.c')

diff --git a/filter/filter.h b/filter/filter.h
index 04a26236..f71e54d3 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -11,6 +11,7 @@
 
 #include "lib/resource.h"
 #include "lib/ip.h"
+#include "nest/route.h"
 #include "nest/attrs.h"
 
 struct f_inst {		/* Instruction */
diff --git a/nest/a-set.c b/nest/a-set.c
index 44407141..69c090b7 100644
--- a/nest/a-set.c
+++ b/nest/a-set.c
@@ -40,10 +40,12 @@ int_set_format(struct adata *set, byte *buf, unsigned int size)
 struct adata *
 int_set_add(struct linpool *pool, struct adata *list, u32 val)
 {
-  struct adata *res = lp_alloc(pool, list->length + sizeof(struct adata) + 4);
-  res->length = list->length+4;
+  int len = list ? list->length : 0;
+  struct adata *res = lp_alloc(pool, len + sizeof(struct adata) + 4);
+  res->length = len + 4;
   * (u32 *) res->data = val;
-  memcpy((char *) res->data + 4, list->data, list->length);
+  if (list)
+    memcpy((char *) res->data + 4, list->data, list->length);
   return res;
 }
 
diff --git a/nest/attrs.h b/nest/attrs.h
index f63f2e45..aaa5f4a2 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -47,4 +47,7 @@ struct adata *int_set_add(struct linpool *pool, struct adata *list, u32 val);
 int int_set_contains(struct adata *list, u32 val);
 struct adata *int_set_del(struct linpool *pool, struct adata *list, u32 val);
 
+static inline int int_set_get_size(struct adata *list)
+{ return list->length / 4; }
+
 #endif
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index 48cb9dd5..a42a4880 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -104,13 +104,19 @@ bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a, int len)
 }
 
 static int
-bgp_check_aggregator(struct bgp_proto *p UNUSED, UNUSED byte *a, int len)
+bgp_check_aggregator(struct bgp_proto *p, UNUSED byte *a, int len)
 {
   int exp_len = (bgp_as4_support && p->as4_support) ? 8 : 6;
   
   return (len == exp_len) ? 0 : 5;
 }
 
+static int
+bgp_check_cluster_list(struct bgp_proto *p UNUSED, UNUSED byte *a, int len)
+{
+  return ((len % 4) == 0) ? 0 : 5;
+}
+
 static int
 bgp_check_reach_nlri(struct bgp_proto *p UNUSED, byte *a UNUSED, int len UNUSED)
 {
@@ -150,8 +156,10 @@ static struct attr_desc bgp_attr_table[] = {
     bgp_check_aggregator, NULL },
   { "community", -1, BAF_OPTIONAL | BAF_TRANSITIVE, EAF_TYPE_INT_SET, 1,	/* BA_COMMUNITY */
     NULL, NULL },
-  { NULL, },									/* BA_ORIGINATOR_ID */
-  { NULL, },									/* BA_CLUSTER_LIST */
+  { "originator_id", 4, BAF_OPTIONAL, EAF_TYPE_INT, 0,				/* BA_ORIGINATOR_ID */
+    NULL, NULL },
+  { "cluster_list", -1, BAF_OPTIONAL, EAF_TYPE_INT_SET, 0,			/* BA_CLUSTER_LIST */
+    bgp_check_cluster_list, NULL }, 
   { NULL, },									/* BA_DPA */
   { NULL, },									/* BA_ADVERTISER */
   { NULL, },									/* BA_RCID_PATH */
@@ -173,35 +181,52 @@ static struct attr_desc bgp_attr_table[] = {
 
 #define ATTR_KNOWN(code) ((code) < ARRAY_SIZE(bgp_attr_table) && bgp_attr_table[code].name)
 
-static byte *
-bgp_set_attr(eattr *e, struct linpool *pool, unsigned attr, unsigned val)
+static inline struct adata *
+bgp_alloc_adata(struct linpool *pool, unsigned len)
+{
+  struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len);
+  ad->length = len;
+  return ad;
+}
+
+static void
+bgp_set_attr(eattr *e, unsigned attr, uintptr_t val)
 {
   ASSERT(ATTR_KNOWN(attr));
   e->id = EA_CODE(EAP_BGP, attr);
   e->type = bgp_attr_table[attr].type;
   e->flags = bgp_attr_table[attr].expected_flags;
   if (e->type & EAF_EMBEDDED)
-    {
-      e->u.data = val;
-      return NULL;
-    }
+    e->u.data = val;
   else
-    {
-      e->u.ptr = lp_alloc(pool, sizeof(struct adata) + val);
-      e->u.ptr->length = val;
-      return e->u.ptr->data;
-    }
+    e->u.ptr = (struct adata *) val;
 }
 
-byte *
-bgp_attach_attr(ea_list **to, struct linpool *pool, unsigned attr, unsigned val)
+static byte *
+bgp_set_attr_wa(eattr *e, struct linpool *pool, unsigned attr, unsigned len)
+{
+  struct adata *ad = bgp_alloc_adata(pool, len);
+  bgp_set_attr(e, attr, (uintptr_t) ad);
+  return ad->data;
+}
+
+void
+bgp_attach_attr(ea_list **to, struct linpool *pool, unsigned attr, uintptr_t val)
 {
   ea_list *a = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
   a->next = *to;
   *to = a;
   a->flags = EALF_SORTED;
   a->count = 1;
-  return bgp_set_attr(a->attrs, pool, attr, val);
+  bgp_set_attr(a->attrs, attr, val);
+}
+
+byte *
+bgp_attach_attr_wa(ea_list **to, struct linpool *pool, unsigned attr, unsigned len)
+{
+  struct adata *ad = bgp_alloc_adata(pool, len);
+  bgp_attach_attr(to, pool, attr, (uintptr_t) ad);
+  return ad->data;
 }
 
 static int
@@ -713,6 +738,7 @@ bgp_rt_notify(struct proto *P, net *n, rte *new, rte *old UNUSED, ea_list *attrs
   bgp_schedule_packet(p->conn, PKT_UPDATE);
 }
 
+
 static int
 bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
 {
@@ -725,14 +751,14 @@ bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
   ea->flags = EALF_SORTED;
   ea->count = 4;
 
-  bgp_set_attr(ea->attrs, pool, BA_ORIGIN,
+  bgp_set_attr(ea->attrs, BA_ORIGIN,
        ((rta->source == RTS_OSPF_EXT1) || (rta->source == RTS_OSPF_EXT2)) ? ORIGIN_INCOMPLETE : ORIGIN_IGP);
 
   if (p->is_internal)
-    bgp_set_attr(ea->attrs+1, pool, BA_AS_PATH, 0);
+    bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, 0);
   else
     {
-      z = bgp_set_attr(ea->attrs+1, pool, BA_AS_PATH, bgp_as4_support ? 6 : 4);
+      z = bgp_set_attr_wa(ea->attrs+1, pool, BA_AS_PATH, bgp_as4_support ? 6 : 4);
       z[0] = AS_PATH_SEQUENCE;
       z[1] = 1;				/* 1 AS */
 
@@ -742,7 +768,7 @@ bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
 	put_u16(z+2, p->local_as);
     }
 
-  z = bgp_set_attr(ea->attrs+2, pool, BA_NEXT_HOP, sizeof(ip_addr));
+  z = bgp_set_attr_wa(ea->attrs+2, pool, BA_NEXT_HOP, sizeof(ip_addr));
   if (p->cf->next_hop_self ||
       !p->is_internal ||
       rta->dest != RTD_ROUTER)
@@ -755,34 +781,55 @@ bgp_create_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
   else
     *(ip_addr *)z = e->attrs->gw;
 
-  bgp_set_attr(ea->attrs+3, pool, BA_LOCAL_PREF, 0);
+  bgp_set_attr(ea->attrs+3, BA_LOCAL_PREF, 0);
 
   return 0;				/* Leave decision to the filters */
 }
 
-static ea_list *
-bgp_path_prepend(struct linpool *pool, eattr *a, ea_list *old, int as)
+
+static inline int
+bgp_as_path_loopy(struct bgp_proto *p, rta *a)
+{
+  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+  return (e && as_path_is_member(e->u.ptr, p->local_as));
+}
+
+static inline int
+bgp_originator_id_loopy(struct bgp_proto *p, rta *a)
 {
-  struct ea_list *e = lp_alloc(pool, sizeof(ea_list) + sizeof(eattr));
-  struct adata *olda = a->u.ptr;
-
-  e->next = old;
-  e->flags = EALF_SORTED;
-  e->count = 1;
-  e->attrs[0].id = EA_CODE(EAP_BGP, BA_AS_PATH);
-  e->attrs[0].flags = BAF_TRANSITIVE;
-  e->attrs[0].type = EAF_TYPE_AS_PATH;
-  e->attrs[0].u.ptr = as_path_prepend(pool, olda, as);
-  return e;
+  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
+  return (e && (e->u.data == p->local_id));
+}
+
+static inline int
+bgp_cluster_list_loopy(struct bgp_proto *p, rta *a)
+{
+  eattr *e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
+  return (e && p->rr_client && int_set_contains(e->u.ptr, p->rr_cluster_id));
+}
+
+
+static inline void
+bgp_path_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 as)
+{
+  eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+  bgp_attach_attr(attrs, pool, BA_AS_PATH, (uintptr_t) as_path_prepend(pool, a->u.ptr, as));
+}
+
+static inline void
+bgp_cluster_list_prepend(rte *e, ea_list **attrs, struct linpool *pool, u32 cid)
+{
+  eattr *a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
+  bgp_attach_attr(attrs, pool, BA_CLUSTER_LIST, (uintptr_t) int_set_add(pool, a ? a->u.ptr : NULL, cid));
 }
 
 static int
-bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool)
+bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *pool, int rr)
 {
   eattr *a;
 
-  if (!p->is_internal && (a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH))))
-    *attrs = bgp_path_prepend(pool, a, *attrs, p->local_as);
+  if (!p->is_internal)
+    bgp_path_prepend(e, attrs, pool, p->local_as);
 
   a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_NEXT_HOP));
   if (a && (p->is_internal || (!p->is_internal && e->attrs->iface == p->neigh->iface)))
@@ -792,7 +839,24 @@ bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
   else
     {
       /* Need to create new one */
-      *(ip_addr *) bgp_attach_attr(attrs, pool, BA_NEXT_HOP, sizeof(ip_addr)) = p->local_addr;
+      bgp_attach_attr_ip(attrs, pool, BA_NEXT_HOP, p->local_addr);
+    }
+
+  if (rr)
+    {
+      /* Handling route reflection, RFC 4456 */
+      struct bgp_proto *src = (struct bgp_proto *) e->attrs->proto;
+
+      a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
+      if (!a)
+	bgp_attach_attr(attrs, pool, BA_ORIGINATOR_ID, src->remote_id);
+
+      /* We attach proper cluster ID according to whether the route is entering or leaving the cluster */
+      bgp_cluster_list_prepend(e, attrs, pool, src->rr_client ? src->rr_cluster_id : p->rr_cluster_id);
+
+      /* Two RR clients with different cluster ID, hmmm */
+      if (src->rr_client && p->rr_client && (src->rr_cluster_id != p->rr_cluster_id))
+	bgp_cluster_list_prepend(e, attrs, pool, p->rr_cluster_id);
     }
 
   return 0;				/* Leave decision to the filters */
@@ -809,9 +873,22 @@ bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *
     return -1;
   if (new_bgp)
     {
+      /* We should check here for cluster list loop, because the receiving BGP instance
+	 might have different cluster ID  */
+      if (bgp_cluster_list_loopy(p, e->attrs))
+	return -1;
+
       if (p->local_as == new_bgp->local_as && p->is_internal && new_bgp->is_internal)
-	return -1;			/* Don't redistribute internal routes with IBGP */
-      return bgp_update_attrs(p, e, attrs, pool);
+	{
+	  /* Redistribution of internal routes with IBGP */
+	  if (p->rr_client || new_bgp->rr_client)
+	    /* Route reflection, RFC 4456 */
+	    return bgp_update_attrs(p, e, attrs, pool, 1);
+	  else
+	    return -1;
+	}
+      else
+	return bgp_update_attrs(p, e, attrs, pool, 0);
     }
   else
     return bgp_create_attrs(p, e, attrs, pool);
@@ -835,7 +912,7 @@ bgp_rte_better(rte *new, rte *old)
   if (n < o)
     return 0;
 
-  /* Use AS path lengths */
+  /* RFC 4271 9.1.2.2. a)  Use AS path lengths */
   if (new_bgp->cf->compare_path_lengths || old_bgp->cf->compare_path_lengths)
     {
       x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
@@ -848,7 +925,7 @@ bgp_rte_better(rte *new, rte *old)
 	return 0;
     }
 
-  /* Use origins */
+  /* RFC 4271 9.1.2.2. b) Use origins */
   x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
   y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN));
   n = x ? x->u.data : ORIGIN_INCOMPLETE;
@@ -858,7 +935,7 @@ bgp_rte_better(rte *new, rte *old)
   if (n > o)
     return 0;
 
-  /* Compare MED's */
+  /* RFC 4271 9.1.2.2. c) Compare MED's */
   x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
   y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_MULTI_EXIT_DISC));
   n = x ? x->u.data : new_bgp->cf->default_med;
@@ -868,24 +945,41 @@ bgp_rte_better(rte *new, rte *old)
   if (n > o)
     return 0;
 
-  /* A tie breaking procedure according to RFC 1771, section 9.1.2.1 */
-  /* We don't have interior distances */
-  /* We prefer external peers */
+  /* RFC 4271 9.1.2.2. d) Prefer external peers */
   if (new_bgp->is_internal > old_bgp->is_internal)
     return 0;
   if (new_bgp->is_internal < old_bgp->is_internal)
     return 1;
-  /* Finally we compare BGP identifiers */
-  return (new_bgp->remote_id < old_bgp->remote_id);
-}
 
-static int
-bgp_path_loopy(struct bgp_proto *p, eattr *a)
-{
-  return as_path_is_member(a->u.ptr, p->local_as);
-}
+  /* Skipping RFC 4271 9.1.2.2. e) */
+  /* We don't have interior distances */
+
+  /* RFC 4456 9. b) Compare cluster list lengths */
+  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
+  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_CLUSTER_LIST));
+  n = x ? int_set_get_size(x->u.ptr) : 0;
+  o = y ? int_set_get_size(y->u.ptr) : 0;
+  if (n < o)
+    return 1;
+  if (n > o)
+    return 0;
+
+  /* RFC 4271 9.1.2.2. f) Compare BGP identifiers */
+  /* RFC 4456 9. a) Use ORIGINATOR_ID instead of local neighor ID */
+  x = ea_find(new->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
+  y = ea_find(old->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
+  n = x ? x->u.data : new_bgp->remote_id;
+  o = y ? y->u.data : old_bgp->remote_id;
+  if (n < o)
+    return 1;
+  if (n > o)
+    return 0;
 
 
+  /* RFC 4271 9.1.2.2. g) Compare peer IP adresses */
+  return (ipa_compare(new_bgp->cf->remote_ip, old_bgp->cf->remote_ip) < 0);
+}
+
 static struct adata *
 bgp_aggregator_convert_to_new(struct adata *old, struct linpool *pool)
 {
@@ -916,7 +1010,7 @@ bgp_merge_as_paths(struct adata *old2, struct adata *old4, int req_as, struct li
 }
 
 
-/* Reconstruct 4B AS_PATH and AGGREGATOR according to RFC4893 4.2.3 */
+/* Reconstruct 4B AS_PATH and AGGREGATOR according to RFC 4893 4.2.3 */
 static void
 bgp_reconstruct_4b_atts(struct bgp_proto *p, rta *a, struct linpool *pool)
 {
@@ -1159,18 +1253,23 @@ bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct lin
     bgp_remove_as4_attrs(bgp, a);
 
   /* If the AS path attribute contains our AS, reject the routes */
-  e = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
-  if (e && bgp_path_loopy(bgp, e))
-    {
-      DBG("BGP: Path loop!\n");
-      return NULL;
-    }
+  if (bgp_as_path_loopy(bgp, a))
+    goto loop;
+
+  /* Two checks for IBGP loops caused by route reflection, RFC 4456 */ 
+  if (bgp_originator_id_loopy(bgp, a) ||
+      bgp_cluster_list_loopy(bgp, a))
+    goto loop;
 
   /* If there's no local preference, define one */
   if (!(seen[0] && (1 << BA_LOCAL_PREF)))
     bgp_attach_attr(&a->eattrs, pool, BA_LOCAL_PREF, 0);
   return a;
 
+loop:
+  DBG("BGP: Path loop!\n");
+  return NULL;
+
 malformed:
   bgp_error(conn, 3, 1, NULL, 0);
   return NULL;
diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c
index e1f5ec02..5fa12492 100644
--- a/proto/bgp/bgp.c
+++ b/proto/bgp/bgp.c
@@ -485,6 +485,13 @@ bgp_start_locked(struct object_lock *lock)
   p->local_id = cf->c.global->router_id;
   p->next_hop = cf->multihop ? cf->multihop_via : cf->remote_ip;
   p->neigh = neigh_find(&p->p, &p->next_hop, NEF_STICKY);
+
+  if (cf->rr_client)
+    {
+      p->rr_cluster_id = cf->rr_cluster_id ? cf->rr_cluster_id : p->local_id;
+      p->rr_client = cf->rr_client;
+    }
+
   if (!p->neigh)
     {
       log(L_ERR "%s: Invalid next hop %I", p->p.name, p->next_hop);
@@ -633,6 +640,8 @@ bgp_check(struct bgp_config *c)
     cf_error("Local AS number out of range");
   if (!bgp_as4_support && (c->remote_as > 0xFFFF))
     cf_error("Neighbor AS number out of range");
+  if ((c->local_as != c->remote_as) && (c->rr_client))
+    cf_error("Only internal neighbor can be RR client");
 }
 
 static void
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index 93383244..af3c5c5a 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -25,6 +25,8 @@ struct bgp_config {
   int compare_path_lengths;		/* Use path lengths when selecting best route */
   u32 default_local_pref;		/* Default value for LOCAL_PREF attribute */
   u32 default_med;			/* Default value for MULTI_EXIT_DISC attribute */
+  u32 rr_cluster_id;			/* Route reflector cluster ID, if different from local ID */
+  int rr_client;			/* Whether neighbor is RR client of me */
   unsigned connect_retry_time;
   unsigned hold_time, initial_hold_time;
   unsigned keepalive_time;
@@ -60,6 +62,8 @@ struct bgp_proto {
   int as4_support;			/* Peer supports 4B AS numbers [RFC4893] */
   u32 local_id;				/* BGP identifier of this router */
   u32 remote_id;			/* BGP identifier of the neighbor */
+  u32 rr_cluster_id;			/* Route reflector cluster ID */
+  int rr_client;			/* Whether neighbor is RR client of me */
   struct bgp_conn *conn;		/* Connection we have established */
   struct bgp_conn outgoing_conn;	/* Outgoing connection we're working with */
   struct bgp_conn incoming_conn;	/* Incoming connection we have neither accepted nor rejected yet */
@@ -121,7 +125,8 @@ void bgp_close_conn(struct bgp_conn *c);
 
 /* attrs.c */
 
-byte *bgp_attach_attr(struct ea_list **to, struct linpool *, unsigned attr, unsigned val);
+void bgp_attach_attr(struct ea_list **to, struct linpool *pool, unsigned attr, uintptr_t val);
+byte *bgp_attach_attr_wa(struct ea_list **to, struct linpool *pool, unsigned attr, unsigned len);
 struct rta *bgp_decode_attrs(struct bgp_conn *conn, byte *a, unsigned int len, struct linpool *pool, int mandatory);
 int bgp_get_attr(struct eattr *e, byte *buf);
 int bgp_rte_better(struct rte *, struct rte *);
@@ -132,6 +137,9 @@ unsigned int bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int
 void bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck);
 void bgp_get_route_info(struct rte *, byte *buf, struct ea_list *attrs);
 
+inline static void bgp_attach_attr_ip(struct ea_list **to, struct linpool *pool, unsigned attr, ip_addr a)
+{ *(ip_addr *) bgp_attach_attr_wa(to, pool, attr, sizeof(ip_addr)) = a; }
+
 /* packets.c */
 
 void bgp_schedule_packet(struct bgp_conn *conn, int type);
diff --git a/proto/bgp/config.Y b/proto/bgp/config.Y
index 580c008f..b23b66cf 100644
--- a/proto/bgp/config.Y
+++ b/proto/bgp/config.Y
@@ -20,7 +20,8 @@ CF_KEYWORDS(BGP, LOCAL, NEIGHBOR, AS, HOLD, TIME, CONNECT, RETRY, KEEPALIVE,
 	MULTIHOP, STARTUP, VIA, NEXT, HOP, SELF, DEFAULT, PATH, METRIC,
 	ERROR, START, DELAY, FORGET, WAIT, DISABLE, AFTER,
 	BGP_PATH, BGP_LOCAL_PREF, BGP_MED, BGP_ORIGIN, BGP_NEXT_HOP,
-	BGP_ATOMIC_AGGR, BGP_AGGREGATOR, BGP_COMMUNITY, SOURCE, ADDRESS, PASSWORD)
+	BGP_ATOMIC_AGGR, BGP_AGGREGATOR, BGP_COMMUNITY, SOURCE, ADDRESS,
+	PASSWORD, RR, CLIENT, CLUSTER, ID)
 
 CF_GRAMMAR
 
@@ -38,7 +39,6 @@ bgp_proto_start: proto_start BGP {
      BGP_CFG->error_amnesia_time = 300;
      BGP_CFG->error_delay_time_min = 60;
      BGP_CFG->error_delay_time_max = 300;
-     BGP_CFG->password = NULL;
  }
  ;
 
@@ -52,6 +52,8 @@ bgp_proto:
      BGP_CFG->remote_ip = $3;
      BGP_CFG->remote_as = $5;
    }
+ | bgp_proto RR CLUSTER ID expr ';' { BGP_CFG->rr_cluster_id = $5; }
+ | bgp_proto RR CLIENT ';' { BGP_CFG->rr_client = 1; }
  | bgp_proto HOLD TIME expr ';' { BGP_CFG->hold_time = $4; }
  | bgp_proto STARTUP HOLD TIME expr ';' { BGP_CFG->initial_hold_time = $5; }
  | bgp_proto CONNECT RETRY TIME expr ';' { BGP_CFG->connect_retry_time = $5; }
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 0dd920e4..8a352c68 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -193,7 +193,7 @@ bgp_create_update(struct bgp_conn *conn, byte *buf)
   if ((buck = p->withdraw_bucket) && !EMPTY_LIST(buck->prefixes))
     {
       DBG("Withdrawn routes:\n");
-      tmp = bgp_attach_attr(&ea, bgp_linpool, BA_MP_UNREACH_NLRI, remains-8);
+      tmp = bgp_attach_attr_wa(&ea, bgp_linpool, BA_MP_UNREACH_NLRI, remains-8);
       *tmp++ = 0;
       *tmp++ = BGP_AF_IPV6;
       *tmp++ = 1;
@@ -218,7 +218,7 @@ bgp_create_update(struct bgp_conn *conn, byte *buf)
 	  size = bgp_encode_attrs(p, w, buck->eattrs, 1024);
 	  w += size;
 	  remains -= size;
-	  tstart = tmp = bgp_attach_attr(&ea, bgp_linpool, BA_MP_REACH_NLRI, remains-8);
+	  tstart = tmp = bgp_attach_attr_wa(&ea, bgp_linpool, BA_MP_REACH_NLRI, remains-8);
 	  *tmp++ = 0;
 	  *tmp++ = BGP_AF_IPV6;
 	  *tmp++ = 1;
@@ -702,7 +702,7 @@ bgp_do_rx_update(struct bgp_conn *conn,
       /* Create fake NEXT_HOP attribute */
       if (len < 1 || (*x != 16 && *x != 32) || len < *x + 2)
 	goto bad;
-      memcpy(bgp_attach_attr(&a0->eattrs, bgp_linpool, BA_NEXT_HOP, 16), x+1, 16);
+      bgp_attach_attr_ip(&a0->eattrs, bgp_linpool, BA_NEXT_HOP, x[1]);
       len -= *x + 2;
       x += *x + 1;
 
-- 
cgit v1.2.3


From ba5ed6f3e4eb4b2899cdad08e2edb99063bfbcee Mon Sep 17 00:00:00 2001
From: Ondrej Zajicek <santiago@crfreenet.org>
Date: Sun, 26 Oct 2008 22:48:02 +0100
Subject: Implementation of an option for disabling AS4 support per BGP
 instance.

---
 proto/bgp/attrs.c   | 14 +++++++-------
 proto/bgp/bgp.c     |  6 ++++--
 proto/bgp/bgp.h     |  2 ++
 proto/bgp/config.Y  |  6 ++++--
 proto/bgp/packets.c |  5 +++--
 5 files changed, 20 insertions(+), 13 deletions(-)

(limited to 'proto/bgp/packets.c')

diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index a42a4880..0fcd1ce1 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -73,13 +73,13 @@ bgp_check_path(byte *a, int len, int bs, int errcode)
 static int
 bgp_check_as_path(struct bgp_proto *p, byte *a, int len)
 {
-  return bgp_check_path(a, len, (bgp_as4_support && p->as4_support) ? 4 : 2, 11);
+  return bgp_check_path(a, len, p->as4_session ? 4 : 2, 11);
 }
 
 static int
 bgp_check_as4_path(struct bgp_proto *p, byte *a, int len)
 {
-  if (bgp_as4_support && (! p->as4_support))
+  if (bgp_as4_support && (! p->as4_session))
     return bgp_check_path(a, len, 4, 9);
   else 
     return 0;
@@ -106,7 +106,7 @@ bgp_check_next_hop(struct bgp_proto *p UNUSED, byte *a, int len)
 static int
 bgp_check_aggregator(struct bgp_proto *p, UNUSED byte *a, int len)
 {
-  int exp_len = (bgp_as4_support && p->as4_support) ? 8 : 6;
+  int exp_len = p->as4_session ? 8 : 6;
   
   return (len == exp_len) ? 0 : 5;
 }
@@ -344,7 +344,7 @@ bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
        * we have to convert our 4B AS_PATH to 2B AS_PATH and send our AS_PATH 
        * as optional AS4_PATH attribute.
        */
-      if ((code == BA_AS_PATH) && bgp_as4_support && (! p->as4_support))
+      if ((code == BA_AS_PATH) && bgp_as4_support && (! p->as4_session))
 	{
 	  len = a->u.ptr->length;
 
@@ -384,7 +384,7 @@ bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
 	}
 
       /* The same issue with AGGREGATOR attribute */
-      if ((code == BA_AGGREGATOR) && bgp_as4_support && (! p->as4_support))
+      if ((code == BA_AGGREGATOR) && bgp_as4_support && (! p->as4_session))
 	{
 	  int new_used;
 
@@ -1082,7 +1082,7 @@ bgp_remove_as4_attrs(struct bgp_proto *p, rta *a)
       if ((fid == id1) || (fid == id2))
 	{
 	  *el = (*el)->next;
-	  if (p->as4_support)
+	  if (p->as4_session)
 	    log(L_WARN "BGP: Unexpected AS4_* attributes received");
 	}
       else
@@ -1246,7 +1246,7 @@ bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct lin
   /* When receiving attributes from non-AS4-aware BGP speaker,
    * we have to reconstruct 4B AS_PATH and AGGREGATOR attributes
    */
-  if (bgp_as4_support && (! bgp->as4_support))
+  if (bgp_as4_support && (! bgp->as4_session))
     bgp_reconstruct_4b_atts(bgp, a, pool);
 
   if (bgp_as4_support)
diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c
index 5fa12492..0d580be1 100644
--- a/proto/bgp/bgp.c
+++ b/proto/bgp/bgp.c
@@ -636,9 +636,11 @@ bgp_check(struct bgp_config *c)
     cf_error("Local AS number must be set");
   if (!c->remote_as)
     cf_error("Neighbor must be configured");
-  if (!bgp_as4_support && (c->local_as > 0xFFFF))
+  if (!bgp_as4_support && c->enable_as4)
+    cf_error("AS4 support disabled globbaly");
+  if (!c->enable_as4 && (c->local_as > 0xFFFF))
     cf_error("Local AS number out of range");
-  if (!bgp_as4_support && (c->remote_as > 0xFFFF))
+  if (!c->enable_as4 && (c->remote_as > 0xFFFF))
     cf_error("Neighbor AS number out of range");
   if ((c->local_as != c->remote_as) && (c->rr_client))
     cf_error("Only internal neighbor can be RR client");
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index af3c5c5a..1d67e336 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -25,6 +25,7 @@ struct bgp_config {
   int compare_path_lengths;		/* Use path lengths when selecting best route */
   u32 default_local_pref;		/* Default value for LOCAL_PREF attribute */
   u32 default_med;			/* Default value for MULTI_EXIT_DISC attribute */
+  int enable_as4;			/* Enable local support for 4B AS numbers [RFC4893] */
   u32 rr_cluster_id;			/* Route reflector cluster ID, if different from local ID */
   int rr_client;			/* Whether neighbor is RR client of me */
   unsigned connect_retry_time;
@@ -60,6 +61,7 @@ struct bgp_proto {
   u32 local_as, remote_as;
   int is_internal;			/* Internal BGP connection (local_as == remote_as) */
   int as4_support;			/* Peer supports 4B AS numbers [RFC4893] */
+  int as4_session;			/* Session uses 4B AS numbers in AS_PATH (both sides support it) */
   u32 local_id;				/* BGP identifier of this router */
   u32 remote_id;			/* BGP identifier of the neighbor */
   u32 rr_cluster_id;			/* Route reflector cluster ID */
diff --git a/proto/bgp/config.Y b/proto/bgp/config.Y
index b23b66cf..d7bba575 100644
--- a/proto/bgp/config.Y
+++ b/proto/bgp/config.Y
@@ -18,10 +18,10 @@ CF_DECLS
 
 CF_KEYWORDS(BGP, LOCAL, NEIGHBOR, AS, HOLD, TIME, CONNECT, RETRY, KEEPALIVE,
 	MULTIHOP, STARTUP, VIA, NEXT, HOP, SELF, DEFAULT, PATH, METRIC,
-	ERROR, START, DELAY, FORGET, WAIT, DISABLE, AFTER,
+	ERROR, START, DELAY, FORGET, WAIT, ENABLE, DISABLE, AFTER,
 	BGP_PATH, BGP_LOCAL_PREF, BGP_MED, BGP_ORIGIN, BGP_NEXT_HOP,
 	BGP_ATOMIC_AGGR, BGP_AGGREGATOR, BGP_COMMUNITY, SOURCE, ADDRESS,
-	PASSWORD, RR, CLIENT, CLUSTER, ID)
+	PASSWORD, RR, CLIENT, CLUSTER, ID, AS4)
 
 CF_GRAMMAR
 
@@ -39,6 +39,7 @@ bgp_proto_start: proto_start BGP {
      BGP_CFG->error_amnesia_time = 300;
      BGP_CFG->error_delay_time_min = 60;
      BGP_CFG->error_delay_time_max = 300;
+     BGP_CFG->enable_as4 = bgp_as4_support;
  }
  ;
 
@@ -68,6 +69,7 @@ bgp_proto:
  | bgp_proto ERROR FORGET TIME expr ';' { BGP_CFG->error_amnesia_time = $5; } 
  | bgp_proto ERROR WAIT TIME expr ',' expr ';' { BGP_CFG->error_delay_time_min = $5; BGP_CFG->error_delay_time_max = $7; }
  | bgp_proto DISABLE AFTER ERROR bool ';' { BGP_CFG->disable_after_error = $5; }
+ | bgp_proto ENABLE AS4 bool ';' { BGP_CFG->enable_as4 = $4; }
  | bgp_proto PASSWORD TEXT ';' { BGP_CFG->password = $3; }
  ;
 
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 8a352c68..c18c6e42 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -73,7 +73,7 @@ bgp_create_open(struct bgp_conn *conn, byte *buf)
 #ifdef IPV6
   cap = bgp_put_cap_ipv6(conn, cap);
 #endif
-  if (bgp_as4_support)
+  if (p->cf->enable_as4)
     cap = bgp_put_cap_as4(conn, cap);
 
   cap_len = cap - buf - 12;
@@ -407,7 +407,8 @@ bgp_parse_capabilities(struct bgp_conn *conn, byte *opt, int len)
 	  if (cl != 4)
 	    goto err;
 	  p->as4_support = 1;
-	  if (bgp_as4_support)
+	  p->as4_session = p->cf->enable_as4;
+	  if (p->as4_session)
 	    conn->advertised_as = get_u32(opt + 2);
 	  break;
 
-- 
cgit v1.2.3