[openib-general] SA multicast patches

[Sean Hefty]

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