Page MenuHomeFreeBSD

Clear the last bit from all the dereferenced rb_lefts and rb_rights
AbandonedPublic

Authored by dougm on Jun 12 2020, 7:05 PM.

Details

Reviewers
markj
alc
Summary

Everywhere rb_left or rb_right is used, clear the last bit with rb_ptr before dereferecing.

In rb_replace_node, preserve the color bit in the pointer to the replaced node.

Test Plan

Wait for somebody to tell me that something is fixed.

Diff Detail

Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

dougm requested review of this revision.Jun 12 2020, 7:06 PM

Don't modify 'new' in rb_replace_node.

I don't think this approach is really tenable. The point of the LinuxKPI is to make it as easy as possible to run unmodified Linux code, and this change violates that.

Since the Linux interface seems to really want to allow direct accesses to child pointers, I can see two possible solutions:

  • Rewrite the LinuxKPI implementation to not rely on RB_*, i.e., provide a separate rbtree implementation.
  • Somehow rework r361984 to integrate properly with the LinuxKPI implementation. Maybe the same goal can be achieved by storing a node's colour bit in the parent pointer, rather than in the parent's child pointer? I'm not sure.

In any case, I would suggest reverting the original revisions for now because of the regression, unless there is another quick solution. If @hselasky (the maintainer of this code) is ok with this patch as an interim measure, then that is fine too.

I agree with Mark that this apprach is a bit dangerous when porting code and patches. The API provided by LinuxKPI's rbtree.h must work w/o the use of rb_ptr() :-(

BTW: In https://svnweb.freebsd.org/changeset/base/361984 you remove some definitions which are API functions in Linux:

-#define rb_color(r) RB_COLOR(r, __entry)
-#define rb_is_red(r) (rb_color(r) == RB_RED)
-#define rb_is_black(r) (rb_color(r) == RB_BLACK)

BTW: In https://svnweb.freebsd.org/changeset/base/361984 you remove some definitions which are API functions in Linux:

-#define rb_color(r) RB_COLOR(r, __entry)
-#define rb_is_red(r) (rb_color(r) == RB_RED)
-#define rb_is_black(r) (rb_color(r) == RB_BLACK)

When I reviewed that I noticed that they are not used outside the rbtree implementation itself. I presume they are not really for external use. Also they are part of rbtree_augmented.h, not rbtree.h. The former is not implemented in the LinuxKPI (I know it is provided with the DRM drivers).

sys/ofed/drivers/infiniband/core/ib_cm.c
607

Did you miss converting this line?

709

What about use of "link" ?

@markj : If the macros are not used, then I guess removing them is fine.

It is at times like this C++ would be very handy.

-#define RB_RED		1
 #define RB_ENTRY(type)							\
 struct {								\
 	struct type *rbe_left;		/* left element */		\
 	struct type *rbe_right;		/* right element */		\
 	struct type *rbe_parent;	/* parent element */		\
-	int rbe_color;			/* node color */		\
 }

Missing:

__aligned(sizeof(void *)) for i386 for this to work reliably

Address some omissions in this patch before I abandon it.

Abandoning this.

I could do-over the elimination of the color field by using the low-order two bits of the parent pointer. Is that going to break something unexpectedly, or be otherwise unwelcome?

@dougm :

I think using a bit from the parent pointer is less likely to break.

Just rename rb_parent and see where the code breaks during compilation. Should be a quick way to get an overview.

Abandoning this.

I could do-over the elimination of the color field by using the low-order two bits of the parent pointer. Is that going to break something unexpectedly, or be otherwise unwelcome?

I don't see any reason it would break anything. Of course I didn't foresee the LinuxKPI breakage either, but the goal of the change, to shrink the tree node size, seems most welcome.