[openib-general] SA multicast patches

[Roland Dreier]

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:

 > +		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:

 > +		else if (allow_duplicates)
 > +			link = &(*link)->rb_left;

which seems to put duplicates to the left always.

Also I'd be really worried that the rebalancing code freaks out when
duplicate keys are inserted in the tree.

 - R.