Merge commit '9efaf6ba' into tmp-bad-learn

Also fixed forgotten best route selection among alien routes.

4 files changed, 99 insertions, 21 deletions

diff --git a/lib/attrs.h b/lib/attrs.h
index 79b7b14a..a75abcd3 100644
--- a/lib/attrs.h
+++ b/lib/attrs.h
@@ -42,7 +42,7 @@ lp_store_adata(struct linpool *pool, const void *buf, uint len)
 #define tmp_copy_adata(ad)	  tmp_store_adata((ad)->data, (ad)->length)
 
 static inline int adata_same(const struct adata *a, const struct adata *b)
-{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); }
+{ return (!a && !b) || (a->length == b->length && !memcmp(a->data, b->data, a->length)); }
 
 
 
diff --git a/lib/hash.h b/lib/hash.h
index 8febb33f..ebb2857a 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -10,7 +10,7 @@
 #ifndef _BIRD_HASH_H_
 #define _BIRD_HASH_H_
 
-#define HASH(type)		struct { type **data; uint count, order; }
+#define HASH(type)		struct { type **data; uint count; u16 iterators; u8 order; u8 down_requested:1; }
 #define HASH_TYPE(v)		typeof(** (v).data)
 #define HASH_SIZE(v)		(1U << (v).order)
 
@@ -125,20 +125,26 @@
 
 #define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args)			\
   ({                                                                    \
-    if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&		\
-	((v).order > (REHASH_LO_BOUND(args))))				\
+    if ((v).iterators)							\
+      (v).down_requested = 1;						\
+    else if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&	\
+	     ((v).order > (REHASH_LO_BOUND(args))))			\
       rehash_fn(&(v), pool, -(REHASH_LO_STEP(args)));			\
   })
 
 #define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args)			\
   ({                                                                    \
-    uint _o = (v).order;							\
-    while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&		\
-	   (_o > (REHASH_LO_BOUND(args))))				\
-      _o -= (REHASH_LO_STEP(args));					\
-    if (_o < (v).order)							\
-      rehash_fn(&(v), pool, _o - (v).order);				\
-  })
+    if ((v).iterators)							\
+      (v).down_requested = 1;						\
+    else {								\
+      uint _o = (v).order;						\
+      while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&		\
+	     (_o > (REHASH_LO_BOUND(args))))				\
+	_o -= (REHASH_LO_STEP(args));					\
+      if (_o < (v).order)						\
+	rehash_fn(&(v), pool, _o - (v).order);				\
+    }									\
+   })
 
 
 #define HASH_INSERT2(v,id,pool,node)					\
@@ -195,6 +201,20 @@
 #define HASH_WALK_FILTER_END } while (0)
 
 
+#define HASH_WALK_ITER(v, id, n, iter)					\
+  do {									\
+    uint _hash_walk_iter_put = 0;					\
+    uint _shift = 32 - (v).order;					\
+    for ( ; !_hash_walk_iter_put; (iter) += (1U << _shift)) {		\
+      _hash_walk_iter_put = ((iter) + (1U << _shift) == 0);		\
+      for (HASH_TYPE(v) *n = (v).data[(iter) >> _shift]; n; n = id##_NEXT((n)))\
+	if (HASH_FN(v, id, id##_KEY(n)) >= ((iter) >> _shift))		\
+
+#define HASH_WALK_ITER_PUT	(_hash_walk_iter_put = 1)
+
+#define HASH_WALK_ITER_END } } while (0)
+
+
 static inline void
 mem_hash_init(u64 *h)
 {
diff --git a/lib/hash_test.c b/lib/hash_test.c
index 4bce7017..ecfcdd66 100644
--- a/lib/hash_test.c
+++ b/lib/hash_test.c
@@ -285,6 +285,46 @@ t_walk_filter(void)
   return 1;
 }
 
+static int
+t_walk_iter(void)
+{
+  init_hash();
+  fill_hash();
+
+  u32 hit = 0;
+
+  u32 prev_hash = ~0;
+  for (uint cnt = 0; cnt < MAX_NUM; )
+  {
+    u32 last_hash = ~0;
+//    printf("PUT!\n");
+    HASH_WALK_ITER(hash, TEST, n, hit)
+    {
+      cnt++;
+      u32 cur_hash = HASH_FN(hash, TEST, n->key);
+      /*
+      printf("C%08x L%08x P%08x K%08x H%08x N%p S%d I%ld\n",
+	  cur_hash, last_hash, prev_hash, n->key, hit, n, _shift, n - &nodes[0]);
+	  */
+
+      if (last_hash == ~0U)
+      {
+	if (prev_hash != ~0U)
+	  bt_assert(prev_hash < cur_hash);
+	last_hash = prev_hash = cur_hash;
+      }
+      else
+	bt_assert(last_hash == cur_hash);
+
+      if (cnt < MAX_NUM)
+	HASH_WALK_ITER_PUT;
+    }
+    HASH_WALK_ITER_END;
+  }
+
+  return 1;
+}
+
 int
 main(int argc, char *argv[])
 {
@@ -299,6 +339,7 @@ main(int argc, char *argv[])
   bt_test_suite(t_walk_delsafe_remove, 	"HASH_WALK_DELSAFE and HASH_REMOVE");
   bt_test_suite(t_walk_delsafe_remove2,	"HASH_WALK_DELSAFE and HASH_REMOVE2. HASH_REMOVE2 is HASH_REMOVE and smart auto-resize function");
   bt_test_suite(t_walk_filter,		"HASH_WALK_FILTER");
+  bt_test_suite(t_walk_iter,		"HASH_WALK_ITER");
 
   return bt_exit_value();
 }
diff --git a/lib/route.h b/lib/route.h
index 1b2f4de6..68596316 100644
--- a/lib/route.h
+++ b/lib/route.h
@@ -35,6 +35,7 @@ typedef struct rte {
 #define REF_STALE	4		/* Route is stale in a refresh cycle */
 #define REF_DISCARD	8		/* Route is scheduled for discard */
 #define REF_MODIFY	16		/* Route is scheduled for modify */
+#define REF_PENDING	32		/* Route has not propagated completely yet */
 
 /* Route is valid for propagation (may depend on other flags in the future), accepts NULL */
 static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); }
@@ -53,6 +54,7 @@ struct rte_src {
 
 struct rte_src *rt_find_source(struct proto *p, u32 id);
 struct rte_src *rt_get_source(struct proto *p, u32 id);
+struct rte_src *rt_find_source_global(u32 id);
 static inline void rt_lock_source(struct rte_src *src) { src->uc++; }
 static inline void rt_unlock_source(struct rte_src *src) { src->uc--; }
 void rt_prune_sources(void);
@@ -147,10 +149,6 @@ typedef struct eattr {
 #define EA_BIT_GET(ea) ((ea) >> 24)
 
 typedef struct ea_list {
-  struct ea_list *next_hash;		/* Next in hash chain */
-  struct ea_list **pprev_hash;		/* Previous in hash chain */
-  u32 uc;				/* Use count */
-  u32 hash_key;				/* List hash */
   struct ea_list *next;			/* In case we have an override list */
   byte flags;				/* Flags: EALF_... */
   byte rfu;
@@ -158,6 +156,14 @@ typedef struct ea_list {
   eattr attrs[0];			/* Attribute definitions themselves */
 } ea_list;
 
+struct ea_storage {
+  struct ea_storage *next_hash;		/* Next in hash chain */
+  struct ea_storage **pprev_hash;	/* Previous in hash chain */
+  u32 uc;				/* Use count */
+  u32 hash_key;				/* List hash */
+  ea_list l[0];				/* The list itself */
+};
+
 #define EALF_SORTED 1			/* Attributes are sorted by code */
 #define EALF_BISECT 2			/* Use interval bisection for searching */
 #define EALF_CACHED 4			/* List is cached */
@@ -171,6 +177,7 @@ struct ea_class {
   btype type;				/* Data type ID */ \
   uint readonly:1;			/* This attribute can't be changed by filters */ \
   uint conf:1;				/* Requested by config */ \
+  uint hidden:1;			/* Technical attribute, do not show, do not expose to filters */ \
   void (*format)(const eattr *ea, byte *buf, uint size); \
   void (*stored)(const eattr *ea);	/* When stored into global hash */ \
   void (*freed)(const eattr *ea);	/* When released from global hash */ \
@@ -237,7 +244,7 @@ ea_list *ea_append(ea_list *to, ea_list *what);
 void ea_format_bitfield(const struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max);
 
 /* Normalize ea_list; allocates the result from tmp_linpool */
-ea_list *ea_normalize(const ea_list *e);
+ea_list *ea_normalize(ea_list *e, int overlay);
 
 uint ea_list_size(ea_list *);
 void ea_list_copy(ea_list *dest, ea_list *src, uint size);
@@ -413,11 +420,21 @@ static inline int rte_dest(const rte *r)
 }
 
 void rta_init(void);
-ea_list *ea_lookup(ea_list *);		/* Get a cached (and normalized) variant of this attribute list */
-static inline int ea_is_cached(ea_list *r) { return r->flags & EALF_CACHED; }
-static inline ea_list *ea_clone(ea_list *r) { r->uc++; return r; }
-void ea__free(ea_list *r);
-static inline void ea_free(ea_list *r) { if (r && !--r->uc) ea__free(r); }
+ea_list *ea_lookup(ea_list *, int overlay);		/* Get a cached (and normalized) variant of this attribute list */
+static inline int ea_is_cached(const ea_list *r) { return r->flags & EALF_CACHED; }
+static inline struct ea_storage *ea_get_storage(ea_list *r)
+{
+  ASSERT_DIE(ea_is_cached(r));
+  return SKIP_BACK(struct ea_storage, l, r);
+}
+
+static inline ea_list *ea_clone(ea_list *r) { ea_get_storage(r)->uc++; return r; }
+void ea__free(struct ea_storage *r);
+static inline void ea_free(ea_list *l) {
+  if (!l) return;
+  struct ea_storage *r = ea_get_storage(l);
+  if (!--r->uc) ea__free(r);
+}
 
 void ea_dump(ea_list *);
 void ea_dump_all(void);