/* * BIRD Internet Routing Daemon -- Network prefix storage * * (c) 1998--2000 Martin Mares <mj@ucw.cz> * (c) 2022 Maria Matejka <mq@jmq.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ #ifndef _BIRD_LIB_FIB_H_ #define _BIRD_LIB_FIB_H_ /* * BIRD FIBs are generic data structure for storing network prefixes. * Also used for the master routing table. Currently implemented as * a hash table. * * Available operations: * - insertion of new entry * - deletion of entry * - searching for entry by network prefix * - asynchronous retrieval of fib contents */ struct fib; struct fib_node { struct fib_node *next; /* Next in hash chain */ struct fib_iterator *readers; /* List of readers of this node */ net_addr addr[0]; }; struct fib_iterator { /* See lib/slists.h for an explanation */ struct fib_iterator *prev, *next; /* Must be synced with struct fib_node! */ byte efef; /* 0xff to distinguish between iterator and node */ byte pad[3]; struct fib_node *node; /* Or NULL if freshly merged */ uint hash; }; typedef void (*fib_init_fn)(struct fib *, void *); struct fib { pool *fib_pool; /* Pool holding all our data */ slab *fib_slab; /* Slab holding all fib nodes */ struct fib_node **hash_table; /* Node hash table */ uint hash_size; /* Number of hash table entries (a power of two) */ uint hash_order; /* Binary logarithm of hash_size */ uint hash_shift; /* 32 - hash_order */ uint addr_type; /* Type of address data stored in fib (NET_*) */ uint node_size; /* FIB node size, 0 for nonuniform */ uint node_offset; /* Offset of fib_node struct inside of user data */ uint entries; /* Number of entries */ uint entries_min, entries_max; /* Entry count limits (else start rehashing) */ fib_init_fn init; /* Constructor */ }; static inline void * fib_node_to_user(struct fib *f, struct fib_node *e) { return e ? (void *) ((char *) e - f->node_offset) : NULL; } static inline struct fib_node * fib_user_to_node(struct fib *f, void *e) { return e ? (void *) ((char *) e + f->node_offset) : NULL; } void fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init); void *fib_find(struct fib *, const net_addr *); /* Find or return NULL if doesn't exist */ void *fib_get_chain(struct fib *f, const net_addr *a); /* Find first node in linked list from hash table */ void *fib_get(struct fib *, const net_addr *); /* Find or create new if nonexistent */ void *fib_route(struct fib *, const net_addr *); /* Longest-match routing lookup */ void fib_delete(struct fib *, void *); /* Remove fib entry */ void fib_free(struct fib *); /* Destroy the fib */ void fib_check(struct fib *); /* Consistency check for debugging */ void fit_init(struct fib_iterator *, struct fib *); /* Internal functions, don't call */ struct fib_node *fit_get(struct fib *, struct fib_iterator *); void fit_put(struct fib_iterator *, struct fib_node *); void fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos); void fit_put_end(struct fib_iterator *i); void fit_copy(struct fib *f, struct fib_iterator *dst, struct fib_iterator *src); #define FIB_WALK(fib, type, z) do { \ struct fib_node *fn_, **ff_ = (fib)->hash_table; \ uint count_ = (fib)->hash_size; \ type *z; \ while (count_--) \ for (fn_ = *ff_++; z = fib_node_to_user(fib, fn_); fn_=fn_->next) #define FIB_WALK_END } while (0) #define FIB_ITERATE_INIT(it, fib) fit_init(it, fib) #define FIB_ITERATE_START(fib, it, type, z) do { \ struct fib_node *fn_ = fit_get(fib, it); \ uint count_ = (fib)->hash_size; \ uint hpos_ = (it)->hash; \ type *z; \ for(;;) { \ if (!fn_) \ { \ if (++hpos_ >= count_) \ break; \ fn_ = (fib)->hash_table[hpos_]; \ continue; \ } \ z = fib_node_to_user(fib, fn_); #define FIB_ITERATE_END fn_ = fn_->next; } } while(0) #define FIB_ITERATE_PUT(it) fit_put(it, fn_) #define FIB_ITERATE_PUT_NEXT(it, fib) fit_put_next(fib, it, fn_, hpos_) #define FIB_ITERATE_PUT_END(it) fit_put_end(it) #define FIB_ITERATE_UNLINK(it, fib) fit_get(fib, it) #define FIB_ITERATE_COPY(dst, src, fib) fit_copy(fib, dst, src) #endif