From 2710221a4c088d920700a47d771a8bafb408db59 Mon Sep 17 00:00:00 2001 From: Vojtech Vilimek Date: Tue, 21 May 2024 15:43:41 +0200 Subject: [PATCH] SNMP: MIB improvement Tests look to pass. --- proto/snmp/mib_tree.c | 560 ++++++++++++------------------------ proto/snmp/mib_tree.h | 84 +----- proto/snmp/snmp_test.c | 613 +++++++++++++++++++++++++++++++++++----- proto/snmp/snmp_utils.c | 22 +- 4 files changed, 744 insertions(+), 535 deletions(-) diff --git a/proto/snmp/mib_tree.c b/proto/snmp/mib_tree.c index 78a3e9cbe..a74c7cf95 100644 --- a/proto/snmp/mib_tree.c +++ b/proto/snmp/mib_tree.c @@ -1,8 +1,6 @@ #include "mib_tree.h" #include "snmp_utils.h" -/* TODO does the code handle leafs correctly ?! */ - #ifdef allocz #undef allocz #endif @@ -29,6 +27,14 @@ mib_mb_realloc(pool *p, void *ptr, unsigned size) return mb_realloc(ptr, size); } +/* + *mib_tree_init - Initialize a MIB tree + * @p: allocation source pool + * @t: pointer to a tree being initialized + * + * By default the standard SNMP internet prefix (.1.3.6.1) is inserted into the + * tree. + */ void mib_tree_init(pool *p, struct mib_tree *t) { @@ -49,21 +55,29 @@ mib_tree_init(pool *p, struct mib_tree *t) STORE_U32(oid->ids[i], snmp_internet[i]); (void) mib_tree_add(p, t, oid, 0); - - /* WTF ?? - struct mib_walk_state walk = { }; - (void) mib_tree_find(t, &walk, oid); -*/ } -// This function does not work with leaf nodes inside the snmp_internet prefix +// TODO: This function does not work with leaf nodes inside the snmp_internet prefix // area // Return NULL of failure, valid mib_node_u pointer otherwise + +/* + * mib_tree_add - Insert a new node to the tree + * @p: allocation source pool + * @t: MIB tree to insert to + * @oid: identification of inserted node. + * @is_leaf: flag signaling that inserted OID should be leaf node. + * + * Reinsertion only return already valid node pointer, no allocations are done + * in this case. Return pointer to node in the MIB tree @t or NULL if the + * requested insertion is invalid. Insertion is invalid if we want to insert + * node below a leaf or insert a leaf in place taken by normal node. + * + */ mib_node_u * mib_tree_add(pool *p, struct mib_tree *t, const struct oid *oid, int is_leaf) { - //ASSERT(snmp_oid_is_prefixed(oid) || !snmp_oid_is_prefixable(oid)); struct mib_walk_state walk; mib_node_u *node; @@ -73,7 +87,7 @@ mib_tree_add(pool *p, struct mib_tree *t, const struct oid *oid, int is_leaf) else if (snmp_is_oid_empty(oid)) return NULL; - mib_tree_walk_init(&walk); + mib_tree_walk_init(&walk, t); node = mib_tree_find(t, &walk, oid); ASSERT(walk.id_pos <= LOAD_U8(oid->n_subid) + 1); @@ -186,11 +200,6 @@ mib_tree_add(pool *p, struct mib_tree *t, const struct oid *oid, int is_leaf) node_inner->child_len = child_id + 1; node_inner->children = allocz(node_inner->child_len * sizeof(mib_node_u *)); - /* - node_inner->child_len = (child_id == 0) ? 0 : child_id; - node_inner->children = (child_id == 0) ? NULL - : allocz(node_inner->child_len * sizeof(mib_node_u *)); - */ } parent = node_inner; @@ -203,7 +212,6 @@ mib_tree_add(pool *p, struct mib_tree *t, const struct oid *oid, int is_leaf) parent->children[child_id] = (mib_node_u *) leaf; leaf->c.id = child_id; - //leaf->c.id = LOAD_U32(oid->ids[subids - 1]); leaf->c.flags = MIB_TREE_LEAF; } else @@ -213,245 +221,48 @@ mib_tree_add(pool *p, struct mib_tree *t, const struct oid *oid, int is_leaf) parent->children[child_id] = (mib_node_u *) node_inner; node_inner->c.id = child_id; - //node_inner->c.id = LOAD_U32(oid->ids[subids - 1]); /* fields c.flags, child_len and children are set by zeroed allocz() */ } return last; } -#if 0 -// TODO merge functions mib_tree_add and mib_tree_insert into one with public iface - -mib_node_u * -mib_tree_add(struct snmp_proto *p, struct mib_tree *t, const struct oid *oid, uint size, int is_leaf) -{ - struct mib_walk_state walk = { }; - mib_node_u *known = mib_tree_find(t, &walk, oid); - - if (known) - return known; - - known = walk.stack[walk.stack_pos]; - - // redundant ??, if not, would be returned from find - if (walk.id_pos_abs == oid->n_subid) - return known; - - if (walk.id_pos_rel < 0) - - if (walk.id_pos_abs < oid->n_subid && (u32) walk.id_pos_rel == known->id_len) - { - if (known->child_len >= oid->ids[walk.id_pos_abs]) // abs +1? - { - u32 old_len = known->child_len; - known->child_len = oid->ids[walk.id_pos_abs] + 1; - known->children = mb_realloc(known->children, - known->child_len * sizeof(struct mib_node *)); - - for (uint i = old_len; i < known->child_len; i++) - known->children[i] = NULL; - } - - /* find would return it - if (known->children[oid->ids[]]) - return known->children[oid->ids[]]; - */ - - struct mib_node *node = mb_alloc(p->p.pool, sizeof(struct mib_node)); - node->id_len = oid->n_subid - walk.id_pos_abs; - node->ids = mb_alloc(p->p.pool, node->id_len * sizeof(u32)); - node->flags = 0; - node->children = NULL; - node->child_len = 0; - node->child_count = 0; - - known->child_count++; - known->children[oid->ids[0]] = node; - return node; - } - else if (walk.id_pos_abs < oid->n_subid) - { - /* We known that walk.id_pos_rel < known->id_len */ - struct mib_node *parent = mb_alloc(p->p.pool, sizeof(struct mib_node)); - parent->id_len = known->id_len - walk.id_pos_rel; - parent->ids = mb_alloc(p->p.pool, - parent->id_len * sizeof(struct mib_node *)); - memcpy(&parent->ids, &known->ids, parent->id_len * sizeof(struct mib_node *)); - u32 *ids = mb_alloc(p->p.pool, - (known->id_len - walk.id_pos_rel) * sizeof(u32)); - memcpy(ids, &known->ids[parent->id_len], - (known->id_len - parent->id_len) * sizeof(struct mib_node *)); - mb_free(known->ids); - known->id_len = known->id_len - walk.id_pos_rel; - known->ids = ids; - parent->child_len = MAX(known->ids[0], oid->ids[walk.id_pos_abs]) + 1; - parent->children = mb_allocz(p->p.pool, - parent->child_len * sizeof(struct mib_node *)); - parent->children[known->ids[0]] = known; - - struct mib_node *child = mb_alloc(p->p.pool, sizeof(struct mib_node)); - child->id_len = oid->n_subid - walk.id_pos_abs - parent->id_len; - child->ids = mb_alloc(p->p.pool, - child->id_len * sizeof(struct mib_node *)); - memcpy(&child->ids, &oid->ids[oid->n_subid - child->id_len], - child->id_len * sizeof(u32)); - // TODO test that we do not override the known - parent->children[child->ids[0]] = child; - - return child; - } - else if (walk.id_pos_abs > oid->n_subid) - die("unreachable"); - - return NULL; -} -#endif - /* + * mib_tree_delete - delete a MIB subtree + * @t: MIB tree + * @walk: MIB tree walk state that specify the subtree + * + * Return number of nodes deleted in the subtree. It is possible to delete an empty + * prefix which leads to deletion of all nodes inside the MIB tree. Note that + * the empty prefix (tree root) node itself could be deleted therefore 0 may be + * returned in case of empty prefix deletion. + */ int -mib_tree_insert(struct snmp_proto *p, struct mib_tree *t, struct oid *oid) +mib_tree_delete(struct mib_tree *t, struct mib_walk_state *walk) { - ASSUME(oid); + int deleted = 0; + ASSUME(t); - struct mib_walk_state walk = { }; - struct mib_node *node = mib_tree_find(t, &walk, oid); - struct mib_leaf *leaf = NULL; + /* (walk->stack_pos < 2) It is impossible to delete root node */ + if (!walk || walk->stack_pos == 0) + return 0; - if (!node) + if (walk->stack_pos == 1) { - node = walk.stack[walk.stack_pos]; - - if (walk.id_pos_abs > oid->n_subid) + for (u32 child = 0; child < t->root.child_len; child++) { - } - else / * walk.id_pos_abs <= oid->n_subid * / - { - leaf = mb_alloc(p->p.pool, sizeof(struct mib_leaf)); - leaf->id_len = oid->n_subid - walk.id_pos_abs; - leaf->ids = mb_alloc(p->p.pool, leaf->id_len * sizeof(struct mib_node *)); - memcpy(&leaf->ids, &oid->ids[oid->n_subid - leaf->id_len], - leaf->id_len * sizeof(u32)); - leaf->flags = 0; - leaf->children = NULL; - leaf->child_len = 0; - leaf->child_count = 0; - } - } -} -*/ - -#if 0 -int -mib_tree_insert(struct snmp_proto *p, struct mib_tree *t, struct oid *oid, struct mib_leaf *leaf) -{ - ASSUME(oid); - - struct mib_walk_state walk = { }; - struct mib_node *node = mib_tree_find(t, &walk, oid); - struct mib_node *leaf_node = &leaf->n; + if (!t->root.children[child]) + continue; - if (!node) - { - node = walk.stack[walk.stack_pos]; + walk->stack_pos = 2; + walk->stack[0] = (mib_node_u*) &t->root; + walk->stack[1] = t->root.children[child]; - // can this really happen ?? - if (walk.id_pos_abs > oid->n_subid) - { - struct mib_node *parent = mb_alloc(p->p.pool, sizeof(struct mib_node)); - parent->id_len = walk.id_pos_abs - oid->n_subid; // -1? - parent->ids = mb_alloc(p->p.pool, parent->id_len * sizeof(u32)); - memcpy(&parent->ids, &node->ids, parent->id_len * sizeof(u32)); - u32 *ids = mb_alloc(p->p.pool, - (node->id_len - parent->id_len) * sizeof(u32)); - node->id_len = node->id_len - parent->id_len; - memcpy(ids, &node->ids[parent->id_len], node->id_len * sizeof(u32)); - mb_free(node->ids); - node->ids = ids; - - parent->child_count = 2; - parent->child_len = MAX(node->ids[0], oid->ids[walk.id_pos_abs]) + 1; - parent->children = mb_allocz(p->p.pool, - parent->child_len * sizeof(struct mib_node *)); - parent->children[node->ids[0]] = node; - parent->children[leaf_node->ids[0]] = leaf_node; - return 1; - } - else - { - mb_free(leaf_node->ids); - leaf_node->id_len = oid->n_subid - walk.id_pos_abs; - leaf_node->ids = mb_alloc(p->p.pool, leaf_node->id_len * sizeof(u32)); - return 1; + deleted += mib_tree_delete(t, walk); } - } - - if (mib_node_is_leaf(node)) - { - struct mib_leaf *l = SKIP_BACK(struct mib_leaf, n, node); - insert_node(&leaf->leafs, &l->leafs); - return 1; - } - - if (node->child_len > 0) - return 0; - - // problem when node->id_len + (walk.id_pos_abs - walk.id_pos_rel) > oid->n_subid - if (walk.id_pos_abs < oid->n_subid) // +-1?? - { - leaf_node->id_len = node->id_len - walk.id_pos_abs; - leaf_node->ids = mb_alloc(p->p.pool, leaf_node->id_len * sizeof(u32)); - memcpy(&leaf_node->ids, &oid->ids[walk.id_pos_abs], leaf_node->id_len * sizeof(u32)); - leaf_node->child_len = leaf_node->child_count = 0; - leaf_node->children = NULL; - return 1; - } - else - return 0; - return 1; -} -#endif - -/* -int -mib_tree_remove(struct mib_tree *tree, struct oid *oid) -{ - struct mib_walk_state walk = { }; - struct mib_node *node = mib_tree_find(tree, &walk, oid); - if (!node) - return 0; - - mib_tree_delete(&walk); - //mib_tree_delete(tree, &walk); - return 1; -} -*/ - -int -mib_tree_remove(struct mib_tree *t, const struct oid *oid) -{ - struct mib_walk_state walk = { }; - mib_node_u *node = mib_tree_find(t, &walk, oid); - - if (!node) - return 0; - else - { - (void) mib_tree_delete(t, &walk); - return 1; + return deleted; } -} - -int -mib_tree_delete(struct mib_tree *t, struct mib_walk_state *walk) -{ - int deleted = 0; - ASSUME(t); - - /* (walk->stack_pos < 2) It is impossible to delete root node */ - if (!walk || !walk->id_pos || walk->stack_pos < 2) - return 0; struct mib_node *parent = &walk->stack[walk->stack_pos - 2]->inner; mib_node_u *node = walk->stack[walk->stack_pos - 1]; @@ -537,10 +348,39 @@ continue_while: /* like outer continue, but skip always true condition */ return deleted; } -/* currently support only search with blank new walk state */ -/* requires non-NULL walk */ -/* TODO doc string, user should check if the node is not root (or at least be - * aware of that */ +/* + * mib_tree_remove - delete a MIB subtree + * @t: MIB tree + * @oid: object identifier specifying the subtree + * + * This is a convenience wrapper around mib_tree_delete(). The mib_tree_remove() + * finds the corresponding node and deletes it. Return 0 if the OID was not + * found. Otherwise return number of deleted nodes (see mib_tree_delete() for + * more details). + */ +int +mib_tree_remove(struct mib_tree *t, const struct oid *oid) +{ + struct mib_walk_state walk = { }; + mib_node_u *node = mib_tree_find(t, &walk, oid); + + if (!node) + return 0; + + return mib_tree_delete(t, &walk); +} + +/* + * mib_tree_find - Find a OID node in MIB tree + * @t: searched tree + * @walk: output search state + * @oid: searched node identification + * + * Return valid pointer to node in MIB tree or NULL. The search state @walk is + * always updated and contains the longest possible prefix of @oid present + * inside the tree @t. The @walk must not be NULL and must be blank (only + * initialized). + */ mib_node_u * mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struct oid *oid) { @@ -556,39 +396,41 @@ mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struc mib_node_u *node; struct mib_node *node_inner; - u8 oid_pos = walk->id_pos = 0; - node = walk->stack[walk->stack_pos++] = (mib_node_u *) &t->root; - -#if 0 + /* the OID id index to use */ u8 oid_pos = walk->id_pos; if (walk->stack_pos > 0) - node = walk->stack[walk->stack_pos]; + node = walk->stack[walk->stack_pos - 1]; else node = walk->stack[walk->stack_pos++] = (mib_node_u *) &t->root; if (mib_node_is_leaf(node)) { - if (snmp_oid_is_prefixed(oid) && LOAD_U8(oid->n_subid) + ARRAY_SIZE(snmp_internet) + 1 == walk->id_pos) + /* In any of cases below we did not move in the tree therefore the + * walk->id_pos is left untouched. */ + if (snmp_oid_is_prefixed(oid) && + LOAD_U8(oid->n_subid) + ARRAY_SIZE(snmp_internet) + 1 == walk->id_pos) return node; + else if (snmp_oid_is_prefixed(oid) && + LOAD_U8(oid->n_subid) + ARRAY_SIZE(snmp_internet) + 1 > walk->id_pos) + return NULL; + else if (!snmp_oid_is_prefixed(oid) && LOAD_U8(oid->n_subid) + 1 == walk->id_pos) return node; - - /* it could hold that LOAD_U8(oid->n_subid) >= walk->id_pos */ - return NULL; } -#endif node_inner = &node->inner; - ASSERT(node && !mib_node_is_leaf(node)); + ASSERT(node); /* node may be leaf if OID is not in tree t */ /* Handling of prefixed OID */ - if (snmp_oid_is_prefixed(oid)) + if (snmp_oid_is_prefixed(oid) && walk->stack_pos < 6) { - uint i; + /* The movement inside implicit SNMP internet and following prefix is not + * projected to walk->id_pos. */ + uint i = (uint) walk->stack_pos - 1; /* walking the snmp_internet prefix itself */ - for (i = 0; i < ARRAY_SIZE(snmp_internet); i++) + for (; i < ARRAY_SIZE(snmp_internet); i++) { if (node_inner->child_len <= snmp_internet[i]) return NULL; @@ -629,11 +471,13 @@ mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struc return (node == (mib_node_u *) &t->root) ? NULL : node; /* loop for all OID's ids except the last one */ - for (oid_pos = 0; oid_pos < subids - 1; oid_pos++) // remove oid_pos assignment + for (; oid_pos < subids - 1 && walk->stack_pos < MIB_WALK_STACK_SIZE + 1; oid_pos++) { u32 id = LOAD_U32(oid->ids[oid_pos]); if (node_inner->child_len <= id) { + /* The walk->id_pos points after the last accepted OID id. + * This is correct because we did not find the last OID in the tree. */ walk->id_pos = oid_pos; return NULL; } @@ -643,6 +487,8 @@ mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struc if (!node) { + /* Same as above, the last node is not valid therefore the walk->is_pos + * points after the last accepted OID id. */ walk->id_pos = oid_pos; return NULL; } @@ -652,6 +498,8 @@ mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struc if (mib_node_is_leaf(node)) { + /* We need to increment the oid_pos because the walk->is_pos suppose the + * pointer after the last valid OID id. */ walk->id_pos = ++oid_pos; return NULL; } @@ -659,7 +507,8 @@ mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struc walk->id_pos = oid_pos; u32 last_id = LOAD_U32(oid->ids[oid_pos]); - if (node_inner->child_len <= last_id) + if (node_inner->child_len <= last_id || + walk->stack_pos >= MIB_WALK_STACK_SIZE + 1) return NULL; node = node_inner->children[last_id]; @@ -671,36 +520,90 @@ mib_tree_find(const struct mib_tree *t, struct mib_walk_state *walk, const struc /* here, the check of node being a leaf is intentionally omitted * because we may need to search for a inner node */ ASSERT(node->empty.id == last_id); + + /* We need to increment the oid_pos because the walk->is_pos suppose the + * pointer after the last valid OID id. */ walk->id_pos = ++oid_pos; return walk->stack[walk->stack_pos++] = node; } void -mib_tree_walk_init(struct mib_walk_state *walk) +mib_tree_walk_init(struct mib_walk_state *walk, const struct mib_tree *t) { walk->id_pos = 0; - walk->stack_pos = 0; + walk->stack_pos = (t != NULL) ? 1 : 0; memset(&walk->stack, 0, sizeof(walk->stack)); + + if (t != NULL) + walk->stack[0] = (mib_node_u *) &t->root; } -/* -void -mib_node_free(mib_node_u *node) +static inline int +walk_is_prefixable(const struct mib_walk_state *walk) { - if (!mib_node_is_leaf(node)) + /* empty prefix and oid->prefix (+2) */ + if (walk->stack_pos < ARRAY_SIZE(snmp_internet) + 2) + return 0; + + for (uint i = 0; i < ARRAY_SIZE(snmp_internet); i++) { - struct mib_node *node_inner = &node->inner; - node_inner->child_len = 0; - free(node_inner->children); - node_inner->children = NULL; + if (walk->stack[i + 1]->empty.id != snmp_internet[i]) + return 0; } - free(node); + u32 id = walk->stack[ARRAY_SIZE(snmp_internet) + 1]->empty.id; + return id > 0 && id <= UINT8_MAX; +} + +int +mib_tree_walk_to_oid(const struct mib_walk_state *walk, struct oid *result, u32 subids) +{ + ASSERT(walk && result); + + /* the stack_pos point after last valid index, and the first is always empty + * prefix */ + if (walk->stack_pos <= 1) + { + /* create a null valued OID; sets all n_subid, prefix, include and reserved */ + memset(result, 0, sizeof(struct oid)); + return 0; + } + + u32 index; + if (walk_is_prefixable(walk)) + { + if (walk->stack_pos - 2 > subids - (ARRAY_SIZE(snmp_internet) + 1)) + return 1; + + /* skip empty prefix, whole snmp_internet .1.3.6.1 and oid->prefix */ + index = 2 + ARRAY_SIZE(snmp_internet); + STORE_U8(result->n_subid, walk->stack_pos - (ARRAY_SIZE(snmp_internet) + 2)); + STORE_U8(result->prefix, + walk->stack[ARRAY_SIZE(snmp_internet) + 1]->empty.id); + } + else + { + if (walk->stack_pos - 2 > subids) + return 1; + + index = 1; /* skip empty prefix */ + STORE_U8(result->n_subid, walk->stack_pos - 1); + STORE_U8(result->prefix, 0); + } + + STORE_U8(result->include, 0); + STORE_U8(result->reserved, 0); + + u32 i = 0; + /* the index could point after last stack array element */ + for (; index < walk->stack_pos && index < MIB_WALK_STACK_SIZE; index++) + STORE_U32(result->ids[i++], walk->stack[index]->empty.id); + + return 0; } -*/ mib_node_u * -mib_tree_walk_next(struct mib_tree *t, struct mib_walk_state *walk) +mib_tree_walk_next(const struct mib_tree *t, struct mib_walk_state *walk) { ASSERT(t && walk); @@ -747,63 +650,10 @@ mib_tree_walk_next(struct mib_tree *t, struct mib_walk_state *walk) return NULL; } -#if 0 -struct mib_node * -mib_tree_walk_next(struct mib_walk_state *walk) -{ - ASSUME(walk->stack[walk->stack_pos]); - - if (walk->stack_pos == 0 && walk->stack[0] && - walk->stack[0]->flags & (MIB_TREE_REG_ACK || MIB_TREE_REG_WAIT)) - return walk->stack[0]; - - struct mib_node *node = walk->stack[walk->stack_pos]; - u32 id; - -find_leaf: - while (!mib_node_is_leaf(node)) - { - for (id = 0; id < node->child_len; id++) - { - if (node->children[id]) - { - node = node->children[id]; - walk->stack[++walk->stack_pos] = node; - break; - } - } - - if (node->flags & (MIB_TREE_REG_ACK || MIB_TREE_REG_WAIT)) - return node; - } - - id = node->ids[0]; - - while (walk->stack_pos) - { - walk->stack[walk->stack_pos] = NULL; - --walk->stack_pos; - node = walk->stack[walk->stack_pos]; - - if (id + 1 != node->child_len) - break; - } - - if (id + 1 == node->child_len) - return walk->stack[0] = NULL; - - node = node->children[id + 1]; - walk->stack_pos++; - walk->stack[walk->stack_pos] = node; - goto find_leaf; -} -#endif - - struct mib_leaf * -mib_tree_walk_next_leaf(struct mib_tree *t, struct mib_walk_state *walk) +mib_tree_walk_next_leaf(const struct mib_tree *t, struct mib_walk_state *walk) { - (void) t; + (void)t; if (walk->stack_pos == 0) return NULL; @@ -815,7 +665,7 @@ mib_tree_walk_next_leaf(struct mib_tree *t, struct mib_walk_state *walk) { next_id = node->leaf.c.id + 1; walk->stack[--walk->stack_pos] = NULL; - node = walk->stack[walk->stack_pos - 1]; // does it underflow ?? + node = walk->stack[walk->stack_pos - 1]; } else if (mib_node_is_leaf(node)) { @@ -824,19 +674,13 @@ mib_tree_walk_next_leaf(struct mib_tree *t, struct mib_walk_state *walk) return NULL; } - mib_node_u *parent = (walk->stack_pos <= 1) ? NULL : - walk->stack[walk->stack_pos - 2]; - while (walk->stack_pos > 0) { continue_while: node = walk->stack[walk->stack_pos - 1]; if (mib_node_is_leaf(node)) - { - walk->stack[walk->stack_pos++] = node; return (struct mib_leaf *) node; - } struct mib_node *node_inner = &node->inner; for (u32 id = next_id; id < node_inner->child_len; id++) @@ -852,58 +696,10 @@ continue_while: goto continue_while; } - while (walk->stack_pos > 1) // endless loop here possible ?? - { - parent = walk->stack[walk->stack_pos - 2]; - node = walk->stack[walk->stack_pos - 1]; - - ASSUME(mib_node_is_leaf(node)); - if (node->leaf.c.id + 1 == parent->inner.child_len) - walk->stack[--walk->stack_pos] = NULL; - - next_id = node->inner.c.id + 1; - } + next_id = node->empty.id + 1; + walk->stack[--walk->stack_pos] = NULL; } return NULL; } -#if 0 -struct mib_leaf * -mib_tree_next_leaf(struct mib_walk_state *walk) -{ - ASSUME(walk->stack[walk->stack_pos] && - mib_node_is_leaf(walk->stack[walk->stack_pos])); - - struct mib_node *node = walk->stack[walk->stack_pos]; - u32 id; - - while (walk->stack_pos) - { - id = node->ids[0]; - walk->stack[walk->stack_pos] = NULL; - --walk->stack_pos; - node = walk->stack[walk->stack_pos]; - - if (id + 1 != node->child_len) - break; - } - - if (id + 1 == node->child_len) - return (struct mib_leaf *) (walk->stack[0] = NULL); - - id++; - while (!mib_node_is_leaf(node)) - { - for (; id < node->child_len && !node->children[id]; id++) - ; - - node = node->children[id]; - walk->stack[++walk->stack_pos] = node; - id = 0; - } - - return (struct mib_leaf *) node; -} -#endif - diff --git a/proto/snmp/mib_tree.h b/proto/snmp/mib_tree.h index bec13b259..feae332d0 100644 --- a/proto/snmp/mib_tree.h +++ b/proto/snmp/mib_tree.h @@ -26,7 +26,8 @@ struct mib_node { struct mib_leaf { struct mib_node_core c; - enum snmp_search_res (*filler)(struct snmp_proto_pdu *pc, struct agentx_varbind **vb); + enum snmp_search_res (*filler)(struct snmp_proto *p, struct snmp_pdu *c); + //enum snmp_search_res (*filler)(struct snmp_proto_pdu *pc, struct agentx_varbind **vb); enum agentx_type type; int size; }; @@ -37,22 +38,13 @@ union mib_node_union { struct mib_leaf leaf; }; -/* -cannonical names - find - walk_init - walk_next - init - insert - delete / remove - */ - /* * The stack size include empty prefix (mib tree root). */ #define MIB_WALK_STACK_SIZE 33 STATIC_ASSERT(OID_MAX_LEN < MIB_WALK_STACK_SIZE); +/* walk state for MIB tree */ struct mib_walk_state { u8 id_pos; /* points after last matching subid in OID */ u32 stack_pos; /* points after last valid stack node */ @@ -64,81 +56,23 @@ struct mib_tree { }; void mib_tree_init(pool *p, struct mib_tree *t); -void mib_tree_walk_init(struct mib_walk_state *state); -//void mib_node_free(mib_node_u *node); -//void mib_tree_free(struct mib_tree *tree); +// TODO: remove need for argument include_root +void mib_tree_walk_init(struct mib_walk_state *state, const struct mib_tree *t); +int mib_tree_walk_to_oid(const struct mib_walk_state *state, struct oid *result, u32 subids); mib_node_u *mib_tree_add(pool *p, struct mib_tree *tree, const struct oid *oid, int is_leaf); int mib_tree_remove(struct mib_tree *t, const struct oid *oid); int mib_tree_delete(struct mib_tree *t, struct mib_walk_state *state); mib_node_u *mib_tree_find(const struct mib_tree *tree, struct mib_walk_state *walk, const struct oid *oid); -mib_node_u *mib_tree_next(struct mib_tree *tree, mib_node_u *end); +mib_node_u *mib_tree_walk_next(const struct mib_tree *t, struct mib_walk_state *walk); +struct mib_leaf *mib_tree_walk_next_leaf(const struct mib_tree *t, struct mib_walk_state *walk); static inline int mib_node_is_leaf(const mib_node_u *node) { + ASSUME(node); return node->empty.flags & MIB_TREE_LEAF; } -/* -WALK OID ID POS !!! -assert on STACK SIZE overflow resp fix entering the too long OIDs - -Enumerace divnych pripadu - -OID { n_subid 0, prefix 0 } ids NULL -OID { n_subid 0, prefix 2 } ids NULL <- todle je divny -OID { n_subid 1, prefix 0 } ids { 1 } -OID { n_subid 2, prefix 0 } ids { 1, 31 } -OID { n_subid 3, prefix 0 } ids { 1, 30, 32 } -OID { n_subid 7, prefix 0 } ids { 1, 2, 3, 4, 5, 6, 7 } -OID { n_subid 1, prefix 4 } ids { 8 } -OID { n_subid 2, prefix 19 } ids { 3, 2 } -OID { n_subid 3, prefix 5 } ids { 3, 9, 1 } -OID { n_subid 4, prefix 2 } ids { 1, 15, 1, 2 } <- obecny priklad - -hledani -odstraneni -odstraneni stromu/podstromu -nasledovnik -nasledovnik list -pridani do vrcholu do stromu - -TODO -add -next -next leaf -find with non-empty walk state - -je opravdu potreba mit v vsech funkcich argument stromu (struct mib_tree *t) ? - >> walk, walk_init, next, next_leaf << - -otestovat neprefixovane OID v prefixovanem strome -a prefixove OID v neprefixovanem strome - -TESTING TREES - -s internet prefixem - - jinak prazdny - - jeden vrchol - - dva vrcholy - - 3, 4, - - rand() vrcholu - - cesta, vidlicka, hrabe - -bez internet prefixu - - uplne prazdny - - jediny vrchol (0, 1, 300, rand()) - - dva vrcholy - - tri vrcholy - - ctyri vrcholy - - pet vrcholu jako v internet ale s prefixem = 300 - - rand() vrcholu rand() hodnot - - cesta vidlicka hrabe - - */ - #endif diff --git a/proto/snmp/snmp_test.c b/proto/snmp/snmp_test.c index e66812782..aecef3375 100644 --- a/proto/snmp/snmp_test.c +++ b/proto/snmp/snmp_test.c @@ -12,18 +12,28 @@ #include "test/birdtest.h" #include "test/bt-utils.h" -#include "bgp_mib.h" +#include "bgp4_mib.h" #include "subagent.h" #include "snmp.h" #include "snmp_utils.h" #include "mib_tree.h" +/************************************************************************* + * + * TODO: reject OIDs longer than OID_MAX_LEN in subagent.c/snmp_utils.c + * + *************************************************************************/ + +// TODO: limit for prefixed OID used for walking is 27 ids (32 - 4inet -1prefix +// resp. 33 - 4inet-1prefix-1empty) + // TODO test walk state stack overflow // TODO hint for child len alloc size static int t_oid_empty(void); static int t_oid_compare(void); static int t_oid_prefixize(void); +static int t_walk_to_oid(void); static int t_tree_find(void); static int t_tree_traversal(void); static int t_tree_leafs(void); @@ -31,7 +41,7 @@ static int t_tree_add(void); static int t_tree_delete(void); #define SNMP_BUFFER_SIZE 1024 -#define TESTS_NUM 20 +#define TESTS_NUM 32 #define SMALL_TESTS_NUM 10 static int tree_sizes[] = { 0, 1, 10, 100, 1000 }; @@ -99,7 +109,7 @@ oid_random_id(void) static struct oid * random_prefixed_oid(void) { - u32 len = xrandom(OID_MAX_LEN + 1 - ARRAY_SIZE(snmp_internet)); + u32 len = xrandom(OID_MAX_LEN + 1 - (ARRAY_SIZE(snmp_internet) + 1)); u8 prefix = (u8) xrandom(UINT8_MAX + 1); @@ -356,6 +366,34 @@ t_oid_compare(void) bt_assert(snmp_oid_compare(super, weird) != 0); + struct oid *pref = oid_create(0, 7, 0); // no ids, only prefix + struct oid *no_pref = oid_create(5, 0, 0, /* ids */ 1, 3, 6, 1, 7); + + bt_assert(snmp_oid_compare(pref, no_pref) == 0); + + struct oid *inet = oid_create(4, 0, 0, /* ids */ 1, 3, 6, 1); + + bt_assert(snmp_oid_compare(inet, pref) < 0); + bt_assert(snmp_oid_compare(pref, inet) > 0); + bt_assert(snmp_oid_compare(inet, no_pref) < 0); + bt_assert(snmp_oid_compare(no_pref, inet) > 0); + + struct oid *pref2 = oid_create(0, 16, 0); // no ids, only prefix + struct oid *no_pref2 = oid_create(5, 0, 0, /* ids */ 1, 3, 6, 1, 16); + + bt_assert(snmp_oid_compare(pref2, no_pref2) == 0); + bt_assert(snmp_oid_compare(no_pref2, pref2) == 0); + + bt_assert(snmp_oid_compare(pref, pref2) < 0); + bt_assert(snmp_oid_compare(pref2, pref) > 0); + bt_assert(snmp_oid_compare(pref, no_pref2) < 0); + bt_assert(snmp_oid_compare(no_pref2, pref) > 0); + bt_assert(snmp_oid_compare(no_pref, pref2) < 0); + bt_assert(snmp_oid_compare(pref2, no_pref) > 0); + bt_assert(snmp_oid_compare(no_pref, no_pref2) < 0); + bt_assert(snmp_oid_compare(no_pref2, no_pref) > 0); + + tmp_flush(); return 1; } @@ -508,6 +546,63 @@ continue_testing: return 1; } +static inline void +walk_to_oid_one(pool *pool, const struct oid *oid) +{ + struct mib_tree storage, *tree = &storage; + mib_tree_init(pool, tree); + + struct mib_walk_state walk; + mib_tree_walk_init(&walk, tree); + + const struct oid *inet_pref = oid_create(1, 0, 0, /* ids */ 1); + mib_tree_remove(tree, inet_pref); + + (void) mib_tree_add(pool, tree, oid, xrandom(2)); + mib_tree_find(tree, &walk, oid); + + char buf[1024]; + struct oid *from_walk = (void *) buf; + + int r = mib_tree_walk_to_oid(&walk, from_walk, + (1024 - sizeof(struct oid)) / sizeof(u32)); + + /* the memory limit should not be breached */ + bt_assert(r == 0); + + bt_assert(snmp_oid_compare(from_walk, oid) == 0); + + /* cleanup */ + mib_tree_remove(tree, inet_pref); +} + +/* test MIB tree walk to OID */ +static int +t_walk_to_oid(void) +{ + lp_state tmps; + lp_save(tmp_linpool, &tmps); + + + pool *pool = &root_pool; + + for (int test = 0; test < TESTS_NUM; test++) + { + + walk_to_oid_one(pool, random_prefixed_oid()); + walk_to_oid_one(pool, random_no_prefix_oid()); + walk_to_oid_one(pool, random_prefixable_oid()); + /* only a one of above */ + //walk_to_oid_one(random_oid); + + lp_restore(tmp_linpool, &tmps); + } + + tmp_flush(); + + return 1; +} + static void test_both(void *buffer, uint size, const struct oid *left, const struct oid *right, const struct oid *expected) @@ -640,31 +735,6 @@ generate_oids(struct oid *oids[], struct oid *sorted[], int size, struct oid *(* return (size > 1) ? last_used + 1 : size; } -/* checks if the last two oids are same, but one is leaf and the other is not */ -static inline int UNUSED -corner_case(struct oid **oids, int oid_idx, struct oid **leafs, int leaf_idx, int is_leaf) -{ - const struct oid **oids_c = (const struct oid **) oids; - const struct oid **leafs_c = (const struct oid **) leafs; - if (oid_idx == 0) - return 0; - - /* if the current (last) OID from oids is not leaf */ - if (!is_leaf && leaf_idx > 0 && - /* and is same as the last leaf */ - snmp_oid_compare(oids_c[oid_idx], leafs_c[leaf_idx - 1]) == 0) - return 1; /* then return true */ - - - /* if the current (last) OID from oids is a leaf */ - if (is_leaf && oid_idx > 0 && - /* and is same as previous OID */ - snmp_oid_compare(oids_c[oid_idx], oids_c[oid_idx - 1]) == 0) - return 1; /* then return true */ - - return 0; /* false */ -} - static void UNUSED print_dups(const struct oid *oids[], uint size) { @@ -754,7 +824,7 @@ gen_test_add(struct oid *(*generator)(void)) struct oid **oids = mb_alloc(pool, size * sizeof(struct oid *)); byte *types = mb_alloc(pool, size * sizeof(byte)); - byte *invalid_hist = mb_alloc(pool, size & sizeof(byte)); + byte *invalid_hist = mb_alloc(pool, size * sizeof(byte)); struct oid **sorted = mb_alloc(pool, size * sizeof(struct oid *)); struct oid **leafs = (with_leafs) ? mb_alloc(pool, size * sizeof(struct oid *)) : NULL; @@ -787,6 +857,20 @@ gen_test_add(struct oid *(*generator)(void)) if (oid_nulled && is_leaf) invalid = 1; + if (!no_inet_prefix) + { + char buffer[1024]; + struct oid *o = (void *) buffer; + + struct oid *inet = oid_create(4, 0, 0, /* ids */ 1, 3, 6, 1); + snmp_oid_common_ancestor(oids[i], inet, o); + + /* If the standard internet prefix is present, + * then the prefix leafs are invalid. */ + if (snmp_oid_compare(oids[i], o) == 0) + invalid = is_leaf; + } + /* check existence of ancestor node of a new leaf */ for (int oi = 0; !invalid && !oid_nulled && oi < i; oi++) { @@ -959,6 +1043,7 @@ gen_test_find(struct oid *(*generator)(void)) } } + mib_node_u *last = NULL; for (int i = 0; i < size; i++) { /* @@ -970,15 +1055,35 @@ gen_test_find(struct oid *(*generator)(void)) */ int expected_precise = 1; mib_node_u *expected = nodes[i]; - for (int j = 0; j < size; j++) + + if (!no_inet_prefix) + { + char buf[1024]; + struct oid *o = (void *) buf; + snmp_oid_common_ancestor(oids[i], longest_inet_pref, o); + if (snmp_oid_compare(oids[i], o) == 0) + expected_precise = 0; + } + + if (snmp_is_oid_empty(oids[i])) + { + expected_precise = 0; + } + + for (int j = 0; expected_precise && j < size; j++) { if (i == j) continue; if (snmp_oid_compare(oids[i], oids[j]) == 0 && types[i] != types[j] && nodes[i] == NULL) { - expected = nodes[j]; - break; + if (nodes[j] != NULL) + { + expected = nodes[j]; + break; + } + + /* else expected = NULL; */ } char buf[1024]; @@ -996,15 +1101,50 @@ gen_test_find(struct oid *(*generator)(void)) } } + struct mib_walk_state walk; - mib_tree_walk_init(&walk); + //mib_tree_walk_init(&walk, tree, 0); + mib_tree_walk_init(&walk, NULL); mib_node_u *found = mib_tree_find(tree, &walk, oids[i]); + bt_assert(walk.stack_pos <= MIB_WALK_STACK_SIZE + 1); + bt_assert(walk.id_pos <= OID_MAX_LEN); + if (expected_precise) bt_assert(found == expected); else /* found is an auto-inserted node on path to some dest OID */ bt_assert(found != NULL); + + last = found; + + /* test finding with walk state not pointing at the root of the tree */ + u8 subids = LOAD_U8(oids[i]->n_subid); + if (subids > 0) + { + found = NULL; + u32 new_ids = xrandom(subids); + mib_tree_walk_init(&walk, (xrandom(2)) ? tree : NULL); + + STORE_U8(oids[i]->n_subid, new_ids); + + mib_node_u *ignored UNUSED; + ignored = mib_tree_find(tree, &walk, oids[i]); + + STORE_U8(oids[i]->n_subid, subids); + + found = mib_tree_find(tree, &walk, oids[i]); + + /* see above */ + if (expected_precise) + bt_assert(found == expected); + else + { + /* test that the result is same as direct searched from tree root */ + bt_assert(found == last); + bt_assert(found != NULL); + } + } } for (int search = 0; search < size; search++) @@ -1016,6 +1156,8 @@ gen_test_find(struct oid *(*generator)(void)) struct oid *o = (void *) buf; snmp_oid_common_ancestor(oids[stored], searched[search], o); + /* test if OID oids[stored] is valid and if it forms a path from root + * with OID searched[search] */ if (nodes[stored] != NULL && snmp_oid_compare(searched[search], o) == 0) { has_node = 1; @@ -1044,9 +1186,40 @@ gen_test_find(struct oid *(*generator)(void)) } struct mib_walk_state walk; - mib_tree_walk_init(&walk); + mib_tree_walk_init(&walk, NULL); + //mib_tree_walk_init(&walk, tree); /* TODO should work also like this */ mib_node_u *found = mib_tree_find(tree, &walk, searched[search]); bt_assert(has_node == (found != NULL)); + + bt_assert(walk.stack_pos <= MIB_WALK_STACK_SIZE + 1); + bt_assert(walk.id_pos <= OID_MAX_LEN); + + last = found; + + u8 subids = LOAD_U8(searched[search]->n_subid); + if (subids > 0) + { + found = NULL; + u32 new_ids = xrandom(subids); + mib_tree_walk_init(&walk, (xrandom(2)) ? tree : NULL); + + STORE_U8(searched[search]->n_subid, new_ids); + + mib_node_u *ignored UNUSED; + ignored = mib_tree_find(tree, &walk, searched[search]); + + STORE_U8(searched[search]->n_subid, subids); + + found = mib_tree_find(tree, &walk, searched[search]); + + bt_assert(has_node == (found != NULL)); + + bt_assert(walk.stack_pos <= MIB_WALK_STACK_SIZE + 1); + bt_assert(walk.id_pos <= OID_MAX_LEN); + + /* test that the result is same as direct search from tree root */ + bt_assert(last == found); + } } lp_restore(tmp_linpool, &tmps); @@ -1072,6 +1245,7 @@ t_tree_find(void) return 1; } +#if 0 static int delete_cleanup(const struct oid *oid, struct oid *oids[], mib_node_u *valid[], int size) { @@ -1098,9 +1272,10 @@ delete_cleanup(const struct oid *oid, struct oid *oids[], mib_node_u *valid[], i return counter; } +#endif static int -gen_test_delete(struct oid *(*generator)(void)) +gen_test_delete_remove(struct oid *(*generator)(void), int remove) { lp_state tmps; lp_save(tmp_linpool, &tmps); @@ -1113,62 +1288,119 @@ gen_test_delete(struct oid *(*generator)(void)) int size = tree_sizes[test % tsz]; int with_leafs = (test % (2 * tsz)) < tsz; - int no_iet_prefix = (test % (4 * tsz)) < (2 * tsz); + int no_inet_prefix = (test % (4 * tsz)) < (2 * tsz); struct oid **oids = mb_alloc(pool, size * sizeof(struct oid *)); - mib_node_u **nodes = mb_alloc(pool, size * sizeof(struct mib_node_u *)); + struct oid **sorted = mb_alloc(pool, size * sizeof(struct oid *)); + mib_node_u **nodes = mb_alloc(pool, size * sizeof(mib_node_u *)); byte *types = mb_alloc(pool, size * sizeof(byte)); struct mib_tree storage, *tree = &storage; - mib_tree_init(tree); + mib_tree_init(pool, tree); - generate_raw_oids(oids, size, generator); + if (no_inet_prefix) + { + /* remove the node .1 and all children */ + const struct oid *inet_pref = oid_create(1, 0, 0, /* ids */ 1); + mib_tree_remove(tree, inet_pref); + } + + int distinct = generate_oids(oids, sorted, size, generator); for (int i = 0; i < size; i++) { int is_leaf; is_leaf = types[i] = (byte) (with_leafs) ? xrandom(2) : 0; - nodes[i] = mib_tree_add(pool, tree, oids[i], is_leaf); + (void) mib_tree_add(pool, tree, oids[i], is_leaf); } - for (int round = 0; round < size / 4; round++) + for (int d = 0; d < distinct; d++) { - int i = xrandom(size); - - mib_tree_walk_state walk; - mib_tree_walk_walk_init(&walk); - mib_node_u *node = mib_tree_find(tree, walk, oids[i]); + struct mib_walk_state walk; + mib_tree_walk_init(&walk, NULL); + //mib_tree_walk_init(&walk, tree); TODO + nodes[d] = mib_tree_find(tree, &walk, sorted[d]); + } - int deleted = mib_tree_delete(tree, walk); + /* we need to populate the nodes array after all insertions because + * some insertion may fail (== NULL) because we try to insert a leaf */ +#if 0 + for (int i = 0; i < size; i++) + { + struct mib_walk_state walk; + mib_tree_walk_init(&walk, tree, 0); + nodes[i] = mib_tree_find(tree, &walk, oids[i]); + } +#endif - int invalid_counter = 0; - for (int j = 0; j < size; j++) + int deleted, invalid_counter; + /* test deletion one of the inserted OIDs */ + for (int round = 0; round < (size + 3) / 4 + remove; round++) + { + /* note: we do not run any rounds for size zero because xrandom(0) + * does not exist */ + int i; + struct oid *oid; + if (!remove) { - if (oids[i] == oids[j]) - { - mib_node_u *node = mib_tree_find(oids[j]); - bt_assert(node == NULL); - invalid_counter++; - continue; - } + /* this way we are also testing remove non-existent tree nodes */ + i = xrandom(size); /* not xrandom(distinct) */ + oid = oids[i]; + } + else + { + i = -1; /* break fast */ + oid = generator(); + } - char buf[1024]; - struct oid *o = (void *) buf; + struct mib_walk_state walk; + mib_tree_walk_init(&walk, NULL); + // mib_tree_walk_init(&walk, tree); TODO + mib_node_u *node = mib_tree_find(tree, &walk, oid); + + if (node == NULL) + continue; + + if (!remove) + deleted = mib_tree_delete(tree, &walk); + else + deleted = mib_tree_remove(tree, oid); - // TODO check that new invalid oids is == or below the deleted one */ + bt_assert(deleted > 0 || snmp_is_oid_empty(oid)); - mib_node_u *node = mib_tree_find(oids[j]); - if (node != nodes[j]) + invalid_counter = 0; + int counted_removed = 0; + for (int j = 0; j < distinct; j++) + { + //mib_tree_walk_init(&walk, tree, 0); + mib_tree_walk_init(&walk, NULL); + mib_node_u *node = mib_tree_find(tree, &walk, sorted[j]); + + if (snmp_is_oid_empty(oid)) + ; + /* the oid could have multiple instances in the oids dataset */ + else if (snmp_oid_compare(oid, sorted[j]) == 0 && !counted_removed) { + invalid_counter++; + counted_removed = 1; + bt_assert(node == NULL); nodes[j] = NULL; + } + else if (node != nodes[j]) + { invalid_counter++; + bt_assert(node == NULL); + nodes[j] = NULL; } } + /* we do not count the internal node that are included in the deleted */ + bt_assert(deleted >= invalid_counter); } lp_restore(tmp_linpool, &tmps); mb_free(oids); + mb_free(sorted); mb_free(nodes); } @@ -1181,10 +1413,10 @@ static int t_tree_delete(void) { - gen_test_delete(random_prefixed_oid); - gen_test_delete(random_no_prefix_oid); - gen_test_delete(random_prefixable_oid); - gen_test_delete(random_oid); + gen_test_delete_remove(random_prefixed_oid, 0); + gen_test_delete_remove(random_no_prefix_oid, 0); + gen_test_delete_remove(random_prefixable_oid, 0); + gen_test_delete_remove(random_oid, 0); return 1; } @@ -1192,28 +1424,261 @@ t_tree_delete(void) static int t_tree_remove(void) { - return 0; /* failed */ + + gen_test_delete_remove(random_prefixed_oid, 1); + gen_test_delete_remove(random_no_prefix_oid, 1); + gen_test_delete_remove(random_prefixable_oid, 1); + gen_test_delete_remove(random_oid, 1); + + return 1; } +static void +gen_test_traverse(struct oid *(*generator)(void)) +{ + lp_state tmps; + lp_save(tmp_linpool, &tmps); + + pool *pool = &root_pool; + + for (int test = 0; test < TESTS_NUM; test++) + { + size_t tsz = ARRAY_SIZE(tree_sizes); + + int size = tree_sizes[test % tsz]; + int with_leafs = (test % (2 * tsz)) < tsz; + int no_inet_prefix = (test % (4 * tsz)) < (2 * tsz); + + struct oid **oids = mb_alloc(pool, size * sizeof(struct oid *)); + struct oid **sorted = mb_alloc(pool, size * sizeof(struct oid *)); + mib_node_u **nodes = mb_allocz(pool, size * sizeof(mib_node_u *)); + + const int distinct = generate_oids(oids, sorted, size, generator); + + struct mib_tree storage, *tree = &storage; + mib_tree_init(pool, tree); + + if (no_inet_prefix) + { + /* remove the node .1 and all children */ + const struct oid *inet_pref = oid_create(1, 0, 0, /* ids */ 1); + mib_tree_remove(tree, inet_pref); + } + + for (int o = 0; o < size; o++) + { + int is_leaf = (with_leafs) ? (int) xrandom(2) : 0; + (void) mib_tree_add(pool, tree, oids[o], is_leaf); + } + + for (int d = 0; d < distinct; d++) + { + struct mib_walk_state walk; + mib_tree_walk_init(&walk, NULL); + nodes[d] = mib_tree_find(tree, &walk, sorted[d]); + } + + int bound = 0; + + for (int d = 0; d < distinct; d++) + { + if (snmp_oid_is_prefixed(sorted[d])) + bound += 5; + bound += (int)LOAD_U8(sorted[d]->n_subid); + } + + if (!no_inet_prefix) + bound += (ARRAY_SIZE(snmp_internet) + 1); + + struct mib_walk_state walk; + mib_tree_walk_init(&walk, tree); + + char buf[1024], buf2[1024]; + struct oid *oid = (void *) buf; + struct oid *last = (void *) buf2; + memset(oid, 0, sizeof(struct oid)); /* create a null OID */ + memset(last, 0, sizeof(struct oid)); + + int oid_index = 0; + if (size > 0 && snmp_is_oid_empty(sorted[oid_index])) + oid_index++; + + mib_node_u *current; + int i = 0; + while ((current = mib_tree_walk_next(tree, &walk)) != NULL && i++ < bound) + { + memcpy(last, oid, snmp_oid_size(oid)); + mib_tree_walk_to_oid(&walk, oid, + (1024 - sizeof(struct oid) / sizeof(u32))); + + bt_assert(snmp_oid_compare(last, oid) < 0); + + while (oid_index < distinct && nodes[oid_index] == NULL) + oid_index++; + + if (oid_index < distinct && snmp_oid_compare(sorted[oid_index], oid) == 0) + oid_index++; + } + + bt_assert(current == NULL); + while (oid_index < distinct && nodes[oid_index] == NULL) + oid_index++; + + /* the bound check is only for that the loop is finite */ + bt_assert(i <= bound + 2); + + current = mib_tree_walk_next(tree, &walk); + bt_assert(current == NULL); + bt_assert(oid_index == distinct); + + mb_free(oids); + mb_free(sorted); + mb_free(nodes); + + lp_restore(tmp_linpool, &tmps); + } + + tmp_flush(); +} static int t_tree_traversal(void) { - return 0; /* failed */ + gen_test_traverse(random_prefixed_oid); + gen_test_traverse(random_no_prefix_oid); + gen_test_traverse(random_prefixable_oid); + gen_test_traverse(random_oid); + + return 1; +} + +static void +gen_test_leafs(struct oid *(*generator)(void)) +{ + lp_state tmps; + lp_save(tmp_linpool, &tmps); + + pool *pool = &root_pool; + + for (int test = 0; test < TESTS_NUM; test++) + { + size_t tsz = ARRAY_SIZE(tree_sizes); + + int size = tree_sizes[test % tsz]; + int with_leafs = (test % (2 * tsz)) < tsz; + int no_inet_prefix = (test % (4 * tsz)) < (2 * tsz); + + struct oid **oids = mb_alloc(pool, size * sizeof(struct oid *)); + struct oid **sorted = mb_alloc(pool, size * sizeof(struct oid *)); + mib_node_u **nodes = mb_allocz(pool, size * sizeof(mib_node_u *)); + + const int distinct = generate_oids(oids, sorted, size, generator); + + struct mib_tree storage, *tree = &storage; + mib_tree_init(pool, tree); + + if (no_inet_prefix) + { + /* remove the node .1 and all children */ + const struct oid *inet_pref = oid_create(1, 0, 0, /* ids */ 1); + mib_tree_remove(tree, inet_pref); + } + + for (int o = 0; o < size; o++) + { + int is_leaf = (with_leafs) ? (int) xrandom(2) : 0; + (void) mib_tree_add(pool, tree, oids[o], is_leaf); + } + + int leafs = 0; + for (int d = 0; d < distinct; d++) + { + struct mib_walk_state walk; + mib_tree_walk_init(&walk, NULL); + nodes[d] = mib_tree_find(tree, &walk, sorted[d]); + + /* count only leafs that was successfully inserted without duplicits */ + if (nodes[d] != NULL && mib_node_is_leaf(nodes[d])) + leafs++; + } + + struct mib_walk_state walk; + mib_tree_walk_init(&walk, tree); + if (!with_leafs) + { + struct mib_leaf *leaf = mib_tree_walk_next_leaf(tree, &walk); + bt_assert(leaf == NULL); + + continue; + } + + char buf[1024], buf2[1024]; + struct oid *oid = (void *) buf; + struct oid *last = (void *) buf2; + memset(oid, 0, sizeof(struct oid)); /* create a null OID */ + memset(last, 0, sizeof(struct oid)); + + int oid_index = 0; + + struct mib_leaf *current; + int i = 0; /* iteration counter ~ leafs found */ + while ((current = mib_tree_walk_next_leaf(tree, &walk)) != NULL && i++ < leafs) + { + memcpy(last, oid, snmp_oid_size(oid)); + mib_tree_walk_to_oid(&walk, oid, + (1024 - sizeof(struct oid) / sizeof(u32))); + + bt_assert(snmp_oid_compare(last, oid) < 0); + bt_assert(mib_node_is_leaf(((mib_node_u *)current))); + + while (oid_index < distinct && + (nodes[oid_index] == NULL || !mib_node_is_leaf(nodes[oid_index]))) + oid_index++; + + if (oid_index < distinct && snmp_oid_compare(sorted[oid_index], oid) == 0) + oid_index++; + } + + bt_assert(current == NULL); + while (oid_index < distinct && + (nodes[oid_index] == NULL || !mib_node_is_leaf(nodes[oid_index]))) + oid_index++; + + current = mib_tree_walk_next_leaf(tree, &walk); + bt_assert(current == NULL); + bt_assert(oid_index == distinct); + bt_assert(i == leafs); + + mb_free(oids); + mb_free(sorted); + mb_free(nodes); + + lp_restore(tmp_linpool, &tmps); + } + + tmp_flush(); } static int t_tree_leafs(void) { - return 0; /* failed */ + + gen_test_leafs(random_prefixed_oid); + gen_test_leafs(random_no_prefix_oid); + gen_test_leafs(random_prefixable_oid); + gen_test_leafs(random_oid); + + return 1; } +#if 0 static int t_tree_all(void) { - /* random sequences of insertion/deletion */ + /* random sequences of insertion/deletion/searches and walks */ return 0; /* failed */ } +#endif int main(int argc, char **argv) @@ -1221,18 +1686,24 @@ int main(int argc, char **argv) bt_init(argc, argv); bt_bird_init(); - srandom(0x0000fa00); + unsigned seed = rand(); + //unsigned seed = 1000789714; + log("random seed is %d", seed); + srandom(seed); bt_test_suite(t_oid_empty, "Function that determines if the OID is empty"); bt_test_suite(t_oid_compare, "Function defining lexicographical order on OIDs"); bt_test_suite(t_oid_prefixize, "Function transforming OID to prefixed form"); bt_test_suite(t_oid_ancestor, "Function finding common ancestor of two OIDs"); + bt_test_suite(t_walk_to_oid, "Function transforming MIB tree walk state to OID"); bt_test_suite(t_tree_find, "MIB tree search"); bt_test_suite(t_tree_traversal, "MIB tree traversal"); bt_test_suite(t_tree_leafs, "MIB tree leafs traversal"); bt_test_suite(t_tree_add, "MIB tree insertion"); - bt_test_suite(t_tree_delete, "MIB tree removal"); + bt_test_suite(t_tree_delete, "MIB tree deletion"); + bt_test_suite(t_tree_remove, "MIB tree removal"); + //bt_test_suite(t_tree_all, "MIB tree random find, add, delete mix"); return bt_exit_value(); } diff --git a/proto/snmp/snmp_utils.c b/proto/snmp/snmp_utils.c index dc0823de0..bb7c6efd7 100644 --- a/proto/snmp/snmp_utils.c +++ b/proto/snmp/snmp_utils.c @@ -18,6 +18,8 @@ snmp_pdu_context(struct snmp_pdu *pdu, sock *sk) pdu->buffer = sk->tpos; pdu->size = sk->tbuf + sk->tbsize - sk->tpos; pdu->index = 0; + pdu->sr_vb_start = NULL; + pdu->sr_o_end = NULL; } /** @@ -629,7 +631,7 @@ int snmp_oid_compare(const struct oid *left, const struct oid *right) { const u8 left_subids = LOAD_U8(left->n_subid); - const u8 right_subids = LOAD_U8(right->n_subid); + u8 right_subids = LOAD_U8(right->n_subid); // see hack for more info const u8 left_prefix = LOAD_U8(left->prefix); const u8 right_prefix = LOAD_U8(right->prefix); @@ -655,16 +657,18 @@ snmp_oid_compare(const struct oid *left, const struct oid *right) if (left_subids <= ARRAY_SIZE(snmp_internet)) return -1; + /* check prefix */ if (LOAD_U32(left->ids[4]) < (u32) right_prefix) return -1; else if (LOAD_U32(left->ids[4]) > (u32) right_prefix) return 1; - int limit = MIN(left_subids - (int) ARRAY_SIZE(snmp_internet), + /* the right prefix is already checked (+1) */ + int limit = MIN(left_subids - (int) (ARRAY_SIZE(snmp_internet) + 1), (int) right_subids); for (int i = 0; i < limit; i++) { - u32 left_id = LOAD_U32(left->ids[i + ARRAY_SIZE(snmp_internet)]); + u32 left_id = LOAD_U32(left->ids[i + ARRAY_SIZE(snmp_internet) + 1]); u32 right_id = LOAD_U32(right->ids[i]); if (left_id < right_id) return -1; @@ -672,6 +676,10 @@ snmp_oid_compare(const struct oid *left, const struct oid *right) return 1; } + /* hack: we known at this point that right has >= 5 subids + * (implicit in snmp_internet and oid->prefix), so + * we simplify to common case by altering left_subids */ + right_subids += 5; goto all_same; } @@ -939,7 +947,8 @@ snmp_oid_log(const struct oid *oid) * The @out must be large enough to always fit the resulting OID, a safe value * is minimum between number of left subids and right subids. The result might * be NULL OID in cases where there is no common subid. The result could be also - * viewed as longest common prefix. + * viewed as longest common prefix. Note that if both @left and @right are + * prefixable but not prefixed the result in @out will also not be prefixed. */ void snmp_oid_common_ancestor(const struct oid *left, const struct oid *right, struct oid *out) @@ -948,6 +957,7 @@ snmp_oid_common_ancestor(const struct oid *left, const struct oid *right, struct STORE_U8(out->include, 0); STORE_U8(out->reserved, 0); + STORE_U8(out->prefix, 0); u32 offset = 0; u8 left_ids = LOAD_U8(left->n_subid), right_ids = LOAD_U8(right->n_subid); @@ -958,7 +968,6 @@ snmp_oid_common_ancestor(const struct oid *left, const struct oid *right, struct if (LOAD_U8(left->prefix) != LOAD_U8(right->prefix)) { STORE_U8(out->n_subid, 4); - STORE_U8(out->prefix, 0); for (uint id = 0; id < ARRAY_SIZE(snmp_internet); id++) STORE_U32(out->ids[id], snmp_internet[id]); @@ -974,7 +983,6 @@ snmp_oid_common_ancestor(const struct oid *left, const struct oid *right, struct { /* finish creating NULL OID */ STORE_U8(out->n_subid, 0); - STORE_U8(out->prefix, 0); return; } @@ -983,7 +991,6 @@ snmp_oid_common_ancestor(const struct oid *left, const struct oid *right, struct if (LOAD_U32(left->ids[id]) != snmp_internet[id]) { STORE_U8(out->n_subid, id); - STORE_U8(out->prefix, 0); return; } @@ -1029,3 +1036,4 @@ snmp_oid_common_ancestor(const struct oid *left, const struct oid *right, struct } STORE_U8(out->n_subid, subids); } + -- 2.47.2