following rn_dupedkey chains in rtsock.c

[David Young]

I'm trying to hide the radix-trie implementation of the forwarding
table so that it is easier to replace the implementation. I've found
radix_nodes used strangely in the routing socket code. I don't think
that this code in route_output() that walks an rn_dupedkey chain is
necessary, but I would like a second opinion:

case RTM_GET:
case RTM_CHANGE:
case RTM_LOCK:
/* XXX This will mask info.rti_info[RTAX_DST] with
* info.rti_info[RTAX_NETMASK] before
* searching. It did not used to do that. --dyoung
*/
error = rtrequest1(RTM_GET, &info, &rt);
if (error != 0)
senderr(error);
if (rtm->rtm_type != RTM_GET) {/* XXX: too grotty */
struct radix_node *rn;

if (memcmp(info.rti_info[RTAX_DST], rt_getkey(rt),
info.rti_info[RTAX_DST]->sa_len) != 0)
senderr(ESRCH);
info.rti_info[RTAX_NETMASK] = intern_netmask(
info.rti_info[RTAX_NETMASK]);
for (rn = rt->rt_nodes; rn; rn = rn->rn_dupedkey)
if (info.rti_info[RTAX_NETMASK] ==
(const struct sockaddr *)rn->rn_mask)
break;
if (rn == NULL)
senderr(ETOOMANYREFS);
rt = (struct rtentry *)rn;
}

It follows from the implementation of rn_lookup(), which
rtrequest1(RTM_GET) calls via rnh->rnh_lookup(), that

1 if the query mask, info.rti_info[RTAX_NETMASK], is not NULL, then the
rtrequest1(RTM_GET) call returns either the one and only rtentry that
has a matching mask, or no rtentry at all. I.e., rtrequest1() returns
an exact match. It also follows that

2 if the query mask is NULL, then rtrequest1() returns either an rtentry
whose mask is also NULL (an exact match), or an rtentry that cannot
possibly be followed in the rn_dupedkey chain by an rtentry with NULL
mask, because NULL masks are most specific (they indicate a host
route), and rn_dupedkey chains are sorted from most to least specific.

In either case, there is no point following the rn_dupedkey chain. We
can compare the rtentry's mask with the query mask and be done with it.
This code,

for (rn = rt->rt_nodes; rn; rn = rn->rn_dupedkey)
if (info.rti_info[RTAX_NETMASK] ==
(const struct sockaddr *)rn->rn_mask)
break;
if (rn == NULL)
senderr(ETOOMANYREFS);
rt = (struct rtentry *)rn;

becomes this code,

if (info.rti_info[RTAX_NETMASK] != rt_mask(rt))
senderr(ETOOMANYREFS);

Please tell me what I have missed. :-)

Dave

[David Young]

Post by David Young
In either case, there is no point following the rn_dupedkey chain. We
can compare the rtentry's mask with the query mask and be done with it.
This code,
for (rn = rt->rt_nodes; rn; rn = rn->rn_dupedkey)
if (info.rti_info[RTAX_NETMASK] ==
(const struct sockaddr *)rn->rn_mask)
break;
if (rn == NULL)
senderr(ETOOMANYREFS);
rt = (struct rtentry *)rn;
becomes this code,
if (info.rti_info[RTAX_NETMASK] != rt_mask(rt))
senderr(ETOOMANYREFS);

I have attached a much better patch. It avoids the intern_netmask()
call, and then I can delete intern_netmask(). That's 19 lines of code
saved, and no more fiddling with radix_nodes in rtsock.c.

Dave