Functions for matching paths added, tested lightly.

Functions for working with community lists added, they compile.

This should not be definitive place for this stuff.

2 files changed, 229 insertions, 23 deletions

diff --git a/filter/config.Y b/filter/config.Y
index 4003460..e17245d 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -11,6 +11,8 @@
 	FIXME: IP addresses in ipv6
 
 
+        FIXME: check messages for \n at the end
+
 (1) Cesty
 
    AS paths budtez interne reprezentovany stejne jako v BGP (viz RFC 1771),
@@ -22,17 +24,22 @@ mnozina cisel ASu. Na cestach nadefinuji nasledujici operace:
 
 Filtry by mely podporovat:
 
-        - operator pridani AS k ceste
+        - operator pridani AS k ceste [bgp_path_prepend]
         - matchovani na pritomnost podposloupnosti v ceste (pricemz vyskytne-li
           se tam mnozina, tak si ji lze predstavit prerovnanou v libovolnem
           poradi)
+
         - operator zjisteni delky cesty (pro vypocet metrik)
 
 Byl bych rad, kdyby se samotne matchovaci funkce objevily v proto/bgp/attrs.c.
 
+Jsou v sitove endianite. [lib/unaligned.h]
+
 
 (2) Community-listy
 
+posloupnost 32bitovych cisel s delkou.
+
 Community list budiz interne reprezentovan jako posloupnost 32-bitovych cisel.
 
 Filtry by se mely na communities divat jako na usporadane dvojice 16-bitovych
@@ -40,33 +47,14 @@ cisel (prvni je cislo AS, ktery community definoval, druhe pak community ID
 v ramci AS) a melo by byt mozne definovat si konstanty typu community.
 K dispozici by mely byt nasledujici operace:
 
-        - zjisteni pritomnosti community v listu
-        - pridani community do listu
-        - odebrani community z listu
+        - zjisteni pritomnosti community v listu [linearni pruchod]
+        - pridani community do listu [s kopii]
+        - odebrani community z listu [s kopii]
         - zresetovani listu
 
 Pro operace na cestach i na community listech by se mela pouzivat `teckova'
 notace pouzita v mem puvodnim navrhu syntaxe.
 
-
-(3) Zmeny v semantice dynamickych atributu
-
-Aby se nemusely neustale kopirovat seznamy atributu, rad bych provedl jeste
-jednu zmenu v tom, jak filtry nakladaji s atributy (pevne doufam, ze posledni,
-ale uznavam, ze u te predchozi jsem to take tvrdil): Funkci f_run budiz
-pridan jeste jeden parametr, ktery prepina mezi dvema mody:
-
-        (a)  [incoming filter mode]  Jako nyni.
-
-        (b)  [outgoing filter mode]  Pokud se hleda atribut, hleda se nejdrive
-             v tmp_attrs a pokud to selze, tak v rta->attrs. Pokud se nastavuje,
-             dava se _vzdy_ do tmp_attrs.
-
-Diky tomu filtry pri exportu routes nebudou vubec muset modifikovat rta a
-protokoly, ktere v import_control potrebuji nastavovat i non-temporary
-atributy, je budou moci pridat do tmp_attrs, aniz by sahly na rta.
-
-
  */
 
 CF_HDR
@@ -83,6 +71,8 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
 	FROM, GW, NET, MASK, SOURCE,
 	LEN,
 	DEFINED,
+	ADD, DELETE, CONTAINS, RESET,
+	APPEND, MATCH,
 	FILTER, WHERE)
 
 %nonassoc THEN
@@ -400,6 +390,19 @@ term:
  | term '.' IP { $$ = f_new_inst(); $$->code = P('c','p'); $$->a1.p = $1; $$->aux = T_IP; }
  | term '.' LEN { $$ = f_new_inst(); $$->code = P('c','p'); $$->a1.p = $1; $$->aux = T_INT; }
  | term '.' MASK '(' term ')' { $$ = f_new_inst(); $$->code = P('i','M'); $$->a1.p = $1; $$->a2.p = $5; }
+
+/* Communities */
+
+ | term '.' ADD '(' term ')' { }
+ | term '.' DELETE '(' term ')' { }
+ | term '.' CONTAINS '(' term ')' { }
+ | term '.' RESET { }
+
+/* Paths */
+ | term '.' APPEND '(' term ')' { }
+/* | term '.' LEN { }  Hmm, this would colide with ip.len. What to do with that? */
+ | term '.' MATCH '(' term ')' { }
+
 /* function_call is inlined here */
  | SYM '(' var_list ')' {
      struct symbol *sym;
diff --git a/filter/filter.c b/filter/filter.c
index af7ee53..7549d6b 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -16,6 +16,7 @@
 #include "lib/resource.h"
 #include "lib/socket.h"
 #include "lib/string.h"
+#include "lib/unaligned.h"
 #include "nest/route.h"
 #include "nest/protocol.h"
 #include "nest/iface.h"
@@ -133,6 +134,7 @@ val_print(struct f_val v)
   case T_SET: tree_print( v.val.t ); PRINTF( "\n" ); break;
   case T_ENUM: PRINTF( "(enum %x)%d", v.type, v.val.i ); break;
   default: PRINTF( "[unknown type %x]", v.type );
+#undef PRINTF
   }
   debug( buf );
 }
@@ -554,6 +556,7 @@ filters_postconfig(void)
       die( "Startup function resulted in error." );
     debug( "done\n" );
   }
+  self_test();
 } 
 
 int
@@ -566,3 +569,203 @@ filter_same(struct filter *new, struct filter *old)
     return 0;
   return i_same(new->root, old->root);
 }
+
+/* This should end up far away from here! */
+
+int
+path_getlen(u8 *p, int len)
+{
+  int res = 0;
+  u8 *q = p+len;
+  while (p<q) {
+    switch (*p++) {
+    case 1: len = *p++; res++;    p += 2*len; break;
+    case 2: len = *p++; res+=len; p += 2*len; break;
+    default: bug("This should not be in path");
+    }
+  }
+  return res;
+}
+
+
+#define PRINTF(a...) { int l; bsnprintf( buf, 8000, a ); s -= (l = strlen(buf)); if (s<bigbuf) return "Path was much too long"; memcpy(s, buf, l); }
+#define COMMA if (first) first = 0; else PRINTF( ", " );
+char *
+path_format(u8 *p, int len)
+{
+  char bigbuf[4096];	/* Keep it smaller than buf */
+  char *s = bigbuf+4095;
+  char buf[8000];
+  int first = 1;
+  int i;
+  u8 *q = p+len;
+  *s-- = 0;
+  while (p<q) {
+    switch (*p++) {
+    case 1:	/* This is a set */
+      len = *p++;
+      COMMA;
+      PRINTF( "}" );
+      {
+	int first = 1;
+	for (i=0; i<len; i++) {
+	  COMMA;
+	  PRINTF( "%d", get_u16(p));
+	  p+=2;
+	}
+      }
+      PRINTF( "{" );
+      break;
+
+    case 2:	/* This is a sequence */
+      len = *p++;
+      for (i=0; i<len; i++) {
+	int l;
+	COMMA;
+	PRINTF( "%d", get_u16(p));
+	p+=2;
+      }
+      break;
+
+    default:
+      bug("This should not be in path");
+    }
+  }
+  return strdup(s);
+}
+#undef PRINTF
+#undef COMMA
+
+#define PM_END -1
+#define PM_ASTERIX -2
+
+#define MASK_PLUS do { if (*++mask == PM_END) return next == q; \
+		       asterix = (*mask == PM_ASTERIX); \
+		       printf( "Asterix now %d\n", asterix ); \
+                       if (asterix) { if (*++mask == PM_END) { printf( "Quick exit\n" ); return 1; } } \
+		       } while(0)
+
+
+int
+path_match(u8 *p, int len, s32 *mask)
+{
+  int i;
+  int asterix = 0;
+  u8 *q = p+len;
+  u8 *next;
+
+  while (p<q) {
+    switch (*p++) {
+    case 1:	/* This is a set */
+      len = *p++;
+      {
+	u8 *p_save = p;
+	next = p_save + 2*len;
+      retry:
+	p = p_save;
+	for (i=0; i<len; i++) {
+	  if (asterix && (get_u16(p) == *mask)) {
+	    MASK_PLUS;
+	    goto retry;
+	  }
+	  if (!asterix && (get_u16(p) == *mask)) {
+	    p = next;
+	    MASK_PLUS;
+	    goto okay;
+	  }
+	  p+=2;
+	}
+	if (!asterix)
+	  return 0;
+      okay:
+      }
+      break;
+
+    case 2:	/* This is a sequence */
+      len = *p++;
+      for (i=0; i<len; i++) {
+	next = p+2;
+	if (asterix && (get_u16(p) == *mask))
+	  MASK_PLUS;
+	else if (!asterix) {
+	  if (get_u16(p) != *mask)
+	    return 0;
+	  MASK_PLUS;
+	}
+	p+=2;
+      }
+      break;
+
+    default:
+      bug("This should not be in path");
+    }
+  }
+  return 0;
+}
+
+struct adata *
+comlist_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;
+  * (u32 *) res->data = val;
+  memcpy((char *) res->data + 4, list->data, list->length);
+  return res;
+}
+
+struct adata *
+comlist_contains(struct adata *list, u32 val)
+{
+  u32 *l = &(list->data);
+  int i;
+  for (i=0; i<list->length/4; i++)
+    if (*l++ == val)
+      return 1;
+  return 0;
+}
+
+struct adata *
+comlist_del(struct linpool *pool, struct adata *list, u32 val)
+{
+  struct adata *res;
+  u32 *l, *k;
+  int i;
+
+  if (!comlist_contains(list, val))
+    return list;
+
+  res = lp_alloc(pool, list->length + sizeof(struct adata) - 4);
+  res->length = list->length-4;
+
+  l = &(list->data);
+  k = &(res->data);
+  for (i=0; i<list->length/4; i++)
+    if (l[i] != val)
+      *k++ = l[i];
+
+  return res;
+}
+
+struct adata *
+comlist_empty(struct linpool *pool)
+{
+  struct adata *res = lp_alloc(pool, sizeof(struct adata));
+  res->length = 0;
+  return res;
+}
+
+void
+self_test(void)
+{
+  char path1[] = { 2, 5, 0, 5, 0, 4, 0, 3, 0, 2, 0, 1 };
+  char path2[] = { 2, 5, 0, 5, 0, 4, 0, 3, 0, 2, 0, 1, 1, 5, 0, 5, 0, 4, 0, 3, 0, 2, 0, 1 };
+  s32 match[] = { 5, PM_ASTERIX, 2, PM_ASTERIX, 1, 3, PM_END };
+
+  DBG( "Filters self-testing:\n" );
+  DBG( "%s\n", path_format(path1, sizeof(path1)) );
+  DBG( "%s\n", path_format(path2, sizeof(path2)) );
+  DBG( "5, 6 = %d, %d\n", path_getlen(path1, sizeof(path1)), path_getlen(path2, sizeof(path2)) );
+  DBG( "%d\n", path_match(path1, sizeof(path1), match));
+  DBG( "%d\n", path_match(path2, sizeof(path2), match));
+//  die( "okay" );
+}