On Mon, Jan 07, 2019 at 03:31:18PM +0800, He Zhe wrote:
>
>
> On 1/5/19 2:37 AM, Catalin Marinas wrote:
> > On Fri, Jan 04, 2019 at 10:29:13PM +0800, zhe.he@xxxxxxxxxxxxx wrote:
> >> It's not necessary to keep consistency between readers and writers of
> >> kmemleak_lock. RCU is more proper for this case. And in order to gain better
> >> performance, we turn the reader locks to RCU read locks and writer locks to
> >> normal spin locks.
> > This won't work.
> >
> >> @@ -515,9 +515,7 @@ static struct kmemleak_object *find_and_get_object(unsigned long ptr, int alias)
> >> struct kmemleak_object *object;
> >>
> >> rcu_read_lock();
> >> - read_lock_irqsave(&kmemleak_lock, flags);
> >> object = lookup_object(ptr, alias);
> >> - read_unlock_irqrestore(&kmemleak_lock, flags);
> > The comment on lookup_object() states that the kmemleak_lock must be
> > held. That's because we don't have an RCU-like mechanism for removing
> > removing objects from the object_tree_root:
> >
> >>
> >> /* check whether the object is still available */
> >> if (object && !get_object(object))
> >> @@ -537,13 +535,13 @@ static struct kmemleak_object *find_and_remove_object(unsigned long ptr, int ali
> >> unsigned long flags;
> >> struct kmemleak_object *object;
> >>
> >> - write_lock_irqsave(&kmemleak_lock, flags);
> >> + spin_lock_irqsave(&kmemleak_lock, flags);
> >> object = lookup_object(ptr, alias);
> >> if (object) {
> >> rb_erase(&object->rb_node, &object_tree_root);
> >> list_del_rcu(&object->object_list);
> >> }
> >> - write_unlock_irqrestore(&kmemleak_lock, flags);
> >> + spin_unlock_irqrestore(&kmemleak_lock, flags);
> > So here, while list removal is RCU-safe, rb_erase() is not.
> >
> > If you have time to implement an rb_erase_rcu(), than we could reduce
> > the locking in kmemleak.
>
> Thanks, I really neglected that rb_erase is not RCU-safe here.
>
> I'm not sure if it is practically possible to implement rb_erase_rcu. Here
> is my concern:
> In the code paths starting from rb_erase, the tree is tweaked at many
> places, in both __rb_erase_augmented and ____rb_erase_color. To my
> understanding, there are many intermediate versions of the tree
> during the erasion. In some of the versions, the tree is incomplete, i.e.
> some nodes(not the one to be deleted) are invisible to readers. I'm not
> sure if this is acceptable as an RCU implementation. Does it mean we
> need to form a rb_erase_rcu from scratch?
>
> And are there any other concerns about this attempt?
>
> Let me add RCU supporters Paul and Josh here. Your advice would be
> highly appreciated.
If updates and rebalancing are handled carefully, it can be made to work.
The classic paper by Kung and Lehman covers the rebalancing issues:
http://www.eecs.harvard.edu/~htk/publication/1980-tods-kung-lehman.pdf
Thanx, Paul
