Date: Tue, 26 Feb 2013 11:56:41 -0500 From: Dheeraj Kandula <dkandula@gmail.com> To: freebsd-net@freebsd.org Subject: Clarifications required in rn_delete Message-ID: <CA%2BqNgxSQdA4_M9LQT-kyiqE1sU3XKOEZuyuZLboZ3mRLZQFa2A@mail.gmail.com>
next in thread | raw e-mail | index | archive | help
Hey All,
I have been reading through the routing path code in FreeBSD 9.1 and
have a few questions while adding and deleting a route using rn_addroute()
and rn_delete(). My questions are highlighted in bold.
In the code fragment below - part of rn_delete() function:
b = -1 - tt->rn_bit;
t = saved_tt->rn_parent;
if (b > t->rn_bit)
goto on1; /* Wasn't lifted at all */
do {
x = t;
t = t->rn_parent;
} while (b <= t->rn_bit && x != top);
for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
if (m == saved_m) {
*mp = m->rm_mklist;
MKFree(m);
break;
}
if (m == 0) {
log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
if (tt->rn_flags & RNF_NORMAL)
return (0); /* Dangling ref to us */
}
the node "m" inside the for loop is removed from x's rn_mklist and inserted
into rn_mkfreelist.
*Shouldn't a test for the rm_refs similar to code below - part of
rn_delete() too - be performed.??*
/*
* Demote routes attached to us.
*/
if (t->rn_mklist) {
if (x->rn_bit >= 0) {
for (mp = &x->rn_mklist; (m = *mp);)
mp = &m->rm_mklist;
*mp = t->rn_mklist;
} else {
/* If there are any key,mask pairs in a sibling
duped-key chain, some subset will appear sorted
in the same order attached to our mklist */
for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
if (m == x->rn_mklist) {
struct radix_mask *mm = m->rm_mklist;
x->rn_mklist = 0;
* if (--(m->rm_refs) < 0)
MKFree(m);*
m = mm;
}
if (m)
log(LOG_ERR,
"rn_delete: Orphaned Mask %p at %p\n",
m, x);
}
}
My understanding is that for leaf nodes that represent a network route,
there will be only one radix_mask node in the linked list.
When a new route is being added i.e. rn_addroute(), the other child of the
new route's parent i.e. the sibling of the new route's node, can be either
a leaf or an internal node.
The scenarios are described below:
1. Leaf Node.
a. If it is a leaf that is a network route and no duplicate routes at x
i.e. x->rn_dupedkey is NULL, a new radix_mask node is created when the
rn_bit is >= the new route's rn_bit i.e. x->rn_bit >= b_leaf and
x->rn_mklist == 0.
/* Promote general routes from below */
if (x->rn_bit < 0) {
for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
*mp = m = rn_new_radix_mask(x, 0);
if (m)
mp = &m->rm_mklist;
}
}
b. If it is a leaf that is a network node and there are duplicate
routes at x i.e. x->rn_dupedkey is NON-NULL, a new radix_mask node is
added for every node in the duplicate linked list if. x->rn_bit >= b_leaf.
as per the code above in case a.
2. Internal Node:
If it is an internal node and the x->rn_mklist is NON-NULL, the linked list
headed by x->rn_mklist is traversed and the traversal is discontinued only
if m->rm_bit >= b_leaf.
else if (x->rn_mklist) {
/*
* Skip over masks whose index is > that of new node
*/
for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
if (m->rm_bit >= b_leaf)
break;
t->rn_mklist = m; *mp = 0;
}
Here x will always be an internal node and hence if (m->rm_bit >= b_leaf)
will always fail as b_leaf is a signed short and rm_bit is a signed short
too and b_leaf is negative as b_leaf is -1 -t->rn_bit. *Isn't it? Is this a
bug in the code.*
Dheeraj
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CA%2BqNgxSQdA4_M9LQT-kyiqE1sU3XKOEZuyuZLboZ3mRLZQFa2A>