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.
Differential D25246
Clear the last bit from all the dereferenced rb_lefts and rb_rights dougm on Jun 12 2020, 7:05 PM. Authored by Tags None Referenced Files
Subscribers
Details
Diff Detail
Event TimelineComment Actions 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:
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. Comment Actions 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() :-( Comment Actions 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) Comment Actions 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). Comment Actions -#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 Comment Actions 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? Comment Actions Just rename rb_parent and see where the code breaks during compilation. Should be a quick way to get an overview. Comment Actions 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. |