Roland Dreier wrote:
> OK, another question about the multicast.c code:
>
> > +static struct mcast_group *mcast_find(struct mcast_port *port,
> > + union ib_gid *mgid)
> > +{
> > + struct rb_node *node = port->table.rb_node;
> > + struct mcast_group *group;
> > + int ret;
> > +
> > + while (node) {
> > + group = rb_entry(node, struct mcast_group, node);
> > + ret = memcmp(mgid->raw, group->rec.mgid.raw, sizeof *mgid);
> > + if (!ret)
> > + return group;
> > +
> > + if (ret < 0)
> > + node = node->rb_left;
> > + else
> > + node = node->rb_right;
> > + }
> > + return NULL;
> > +}
> > +
> > +static struct mcast_group *mcast_insert(struct mcast_port *port,
> > + struct mcast_group *group,
> > + int allow_duplicates)
> > +{
> > + struct rb_node **link = &port->table.rb_node;
> > + struct rb_node *parent = NULL;
> > + struct mcast_group *cur_group;
> > + int ret;
> > +
> > + while (*link) {
> > + parent = *link;
> > + cur_group = rb_entry(parent, struct mcast_group, node);
> > +
> > + ret = memcmp(group->rec.mgid.raw, cur_group->rec.mgid.raw,
> > + sizeof group->rec.mgid);
> > + if (ret < 0)
> > + link = &(*link)->rb_left;
> > + else if (ret > 0)
> > + link = &(*link)->rb_right;
> > + else if (allow_duplicates)
> > + link = &(*link)->rb_left;
> > + else
> > + return cur_group;
> > + }
> > + rb_link_node(&group->node, parent, link);
> > + rb_insert_color(&group->node, &port->table);
> > + return NULL;
> > +}
>
> How does it work to put duplicates into the RB tree? It seems
> especially strange that the lookup code does:
The only duplicates that should appear in the tree are for MGID 0. After a
join
for MGID 0 completes, the group is removed from the tree and re-inserted based
on the MGID that was assigned by the SA.
All multicast groups need to be tracked, which is why even groups with MGID 0
are inserted into the tree.
> > + if (ret < 0)
> > + node = node->rb_left;
> > + else
> > + node = node->rb_right;
>
> so if ret == 0 (ie the two GIDs being tested are the same) then it
> continues to traverse to the right, while the insert code does:
Immediately above this code, the group is returned if ret == 0. Calling
mcast_find() for MGID 0 isn't useful, so the code avoids doing this, but I
think
that it would work. The caller would just get an arbitrary group.
> Also I'd be really worried that the rebalancing code freaks out when
> duplicate keys are inserted in the tree.
I would guess that the rebalancing code is based on left/right branching, and
isn't aware of the actual key values. Having duplicate keys would work fine
then, with the restriction that code searching for a duplicated key would get
an
unpredictable match that is based on the current tree layout.
- Sean
_______________________________________________
openib-general mailing list
[email protected]
http://openib.org/mailman/listinfo/openib-general
To unsubscribe, please visit http://openib.org/mailman/listinfo/openib-general
