diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/attrs.h | 2 | ||||
| -rw-r--r-- | lib/hash.h | 40 | ||||
| -rw-r--r-- | lib/hash_test.c | 41 | ||||
| -rw-r--r-- | lib/route.h | 37 |
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)); } @@ -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); |