Messages in this thread | | | Date | Sun, 7 Dec 2008 15:19:59 -0800 | From | "Paul E. McKenney" <> | Subject | Re: [PATCH 2.6.28-rc5 01/11] kmemleak: Add the base support |
| |
On Sat, Dec 06, 2008 at 11:07:30PM +0000, Catalin Marinas wrote: > On Thu, 2008-12-04 at 08:55 -0800, Paul E. McKenney wrote: > > On Thu, Dec 04, 2008 at 12:14:26PM +0000, Catalin Marinas wrote: > > > On Wed, 2008-12-03 at 10:12 -0800, Paul E. McKenney wrote: > > > > On Thu, Nov 20, 2008 at 11:30:34AM +0000, Catalin Marinas wrote: > > > > > This patch adds the base support for the kernel memory leak > > > > > detector. It traces the memory allocation/freeing in a way similar to > > > > > the Boehm's conservative garbage collector, the difference being that > > > > > the unreferenced objects are not freed but only shown in > > > > > /sys/kernel/debug/memleak. Enabling this feature introduces an > > > > > overhead to memory allocations. > > > > > > > > I have some concerns about your locking/RCU design, please see > > > > interspersed questions and comments. > [...] > > > I'll comment below as well but I'll first show my logic which I added as > > > comment at the top of the memleak.c file: > > > > This is very helpful, thank you! (And please accept my apologies if I > > missed seeing it in my earlier review.) > > You haven't missed it, that's the first time I posted this text.
Whew! ;-)
> > > * The following locks are used by kmemleak: > > > * > > > * - object_list_lock (spinlock): protects the object_list. This is the main > > > * list holding the metadata (struct memleak_object) for the allocated > > > * objects. The memleak_object structures are added to the list in the > > > * create_object() function called from the memleak_alloc() callback. They > > > * are removed from the list in put_object() if the object->use_count is 0 > > > > This part sounds good. I would also add that once object->use_count is > > zero, no one is allowed to increment it. Also, attempts to increment > > object->use_count must be under the protection of rcu_read_lock(), > > correct? > > So, to make sure I understand it correctly, the rcu_read_lock() is > needed to protect between the point where the object pointer was > obtained to the get_object() point.
More generally, it ensures that an RCU-protected object stays around until the matching rcu_read_unlock() is reached. The guarantee call_rcu() provides is to invoke the specified function only after all pre-existing RCU read-side critical sections have completed, in other words, only after any task that previously executed rcu_read_lock() has executed the matching rcu_read_unlock().
> Would it also work if > spin_lock_irqsave(object_list_lock) is used instead of rcu_read_lock()? > The call_rcu() in put_object is bracketed with object_list_lock.
For some RCU implementations, but only by accident.
Just please don't do this!
Instead, consider wrapping rcu_read_lock() and rcu_read_unlock() around the region of interest, if need be. The RCU read-side primitives are quite cheap, so you are losing almost nothing (and in some cases exactly nothing) by using them.
> BTW, I'll have a look if I could remove an object from the object_list > in delete_object() rather than waiting until put_object().
If by doing this, you exclude all readers while removing, you are set.
> > > * - object_tree_lock (rwlock): protects the object_tree_root. When the > > > * metadata is created in create_object(), it is added to the object prio > > > * search tree and removed in delete_object() with this lock held > > > * (write_lock). This lock is also acquired (read_lock) in > > > * find_and_get_object() when an object needs to be looked up by a pointer > > > * value (either during scanning or when changing its properties like > > > * marking as false positive) > > > > Looks OK. I must confess that I am a bit fuzzy on the purpose of > > object_tree_root vs. object_list. > > object_list holds all the memleak_objects in the system and it is > traversed when preparing the scanning and also when reporting the leaks. > > object_tree_root is used to look-up memleak_objects by the allocated > memory block. In the past, this used to be a radix tree (with some > lockdep problems) and later a hash. I now use a prio tree because it > allows pointer ranges. > > Kmemleak could probably iterate over the object_tree_root when reporting > but it is more convenient to report the leaks in the order they were > allocated (preserved by object_list) since one leak may trigger many > subsequent reports but they disappear once the first one is solved.
Very helpful, thank you!
> > > * - memleak_object.lock (spinlock): protects a memleak_object. Modifications > > > * of the metadata (e.g. count) are protected by this lock. Note that some > > > * members of this structure may be protected by other means (atomic or > > > * object_list lock). This lock is also held when scanning the corresponding > > > * object to avoid the kernel freeing it via the memleak_free() callback. > > > * This is less heavyweight than holding a global lock like object_list_lock > > > * during scanning > > > > OK, holding an object's lock can protect that object from deletion, > > but only after you actually acquire the lock. There must be some other > > mechanism preventing the object from being freed during the actual > > acquisition of the lock. > > > > Now this might be the object_list_lock, object_tree_lock, RCU, or some > > combination of the three, for example it might depend on how that object > > is looked up. > > Correct. I'll have to review this again.
Fair enough!
> > > * Freeing a memleak_object is done via an RCU callback invoked from > > > * put_object() when its use_count is 0 and after removing it from the > > > * object_list. One of the reasons for the RCU is to delay the freeing and > > > * avoid a recursive call into the allocator via kmem_cache_free(). Another > > > * reason is to allow lock-less object_list traversal during memleak_scan(). > > > > I did figure out the lock-less object_list traversal, but totally missed > > the fact that you were using RCU to prevent infinite recursion. Cute! > > It wasn't documented, so pretty hard to guess.
I guess I don't feel quite so bad, then. ;-)
> > Also, the memleak_object must have been removed from object_tree before > > its use_count can possibly go to 0, correct? > > Yes.
Good!
> > > > > +static void free_object_rcu(struct rcu_head *rcu) > > > > > +{ > > > > > + struct hlist_node *elem, *tmp; > > > > > + struct memleak_scan_area *area; > > > > > + struct memleak_object *object = > > > > > + container_of(rcu, struct memleak_object, rcu); > > > > > + > > > > > + /* once use_count is 0, there is no code accessing the object */ > > > > > > > > OK, so we won't pass free_object_rcu() to call_rcu() until use_count > > > > is equal to zero. And once use_count is zero, it is never incremented. > > > > So the point of the RCU grace period is to ensure that all tasks > > > > who didn't quite call get_object() soon enough get done failing > > > > before we free up the object, correct? > > > > > > > > Which means that get_object() needs to be under rcu_read_lock()... > > > > > > My view here is that if use_count is 0, no other thread would be able to > > > use this object. It will also be removed from the object_list and hence > > > no other way to get this this object. > > > > What if some other CPU picked up a pointer to the object just before it > > was removed from the list? If that CPU was not under the protection of > > rcu_read_lock(), and if that CPU was delayed, then the object could be > > freed (and possibly re-allocated as something else) before the CPU got > > around to doing the atomic_inc_not_zero(). > > OK, I got it now.
It can indeed be a bit subtle, to be sure.
> > It looks to me that the code currently does the right thing here, just > > want to make sure I understand the locking and that we don't end up > > tempting someone later to break it. ;-) > > I'll document it better and make sure it's clear for me as well.
Sounds good, look forward to seeing the next version!
> > > > > +static void put_object(struct memleak_object *object) > > > > > +{ > > > > > + unsigned long flags; > > > > > + > > > > > + if (!atomic_dec_and_test(&object->use_count)) > > > > > + return; > > > > > + > > > > > + /* should only get here after delete_object was called */ > > > > > + BUG_ON(object->flags & OBJECT_ALLOCATED); > > > > > + > > > > > + spin_lock_irqsave(&object_list_lock, flags); > > > > > > > > We also need to write-hold the object_tree_lock, not? > > > > > > Not here, the memleak_object is removed from the object_tree in the > > > delete_object() function (via from the memleak_free callback). If it is > > > in the object_tree, it should have a use_count >= 1. > > > > So the code never calls the last put_object() without first having > > called delete_object() to remove it from the object_tree? The "last" > > put_object() being the one that decrements object->use_count to zero. > > Yes.
Good!
> > > > > +static void *memleak_seq_next(struct seq_file *seq, void *v, loff_t *pos) > > > > > +{ > > > > > + struct list_head *n; > > > > > + struct memleak_object *next = NULL; > > > > > + unsigned long flags; > > > > > + > > > > > + ++(*pos); > > > > > + if (reported_leaks >= REPORTS_NR) > > > > > + goto out; > > > > > + > > > > > + spin_lock_irqsave(&object_list_lock, flags); > > > > > > > > Using a spinlock instead of rcu_read_lock() is OK, but only if all > > > > updates are also protected by this same spinlock. Which means that, > > > > given that find_and_get_object read-acquires object_tree_lock, deletions > > > > must be projected both by object_list_lock and by write-acquiring > > > > object_tree_lock. Or all calls to memleak_seq_next need to be covered > > > > by rcu_read_lock(). > > > > > > The spin_lock here is only to retrieve the next object in the list but I > > > agree that even if the object_list modifications are protected by > > > object_list_lock, put_object could actually set the use_count to 0 and > > > get_object return in this function isn't checked. If get_object returns > > > successfully, I don't think an rcu_read_lock() is needed since > > > put_object() can no longer invoke free_object_rcu(). > > > > OK, so let me see if I understand: > > > > The memleak_object passed in via the "v" argument to > > memleak_seq_next() was get_object()-ed by some prior > > call, either an earlier memleak_seq_next() or presumably > > by memleak_seq_start(). > > Yes.
OK, good! I might be (slowly) catching on here.
> > memleak_seq_start() -does- do its scan under RCU protection, > > so looks OK. > > > > I believe you also need RCU protection in memleak_seq_next() > > to prevent the next memleak_object from disappearing > > during the traversal. Yes, you do greatly decrease the > > odds of this happening by having irqs disabled, but the > > fact is that RCU is within its rights to end a grace > > period during this time. > > I'll try to make the memleak_seq_next() function use rcu_dereference() > and rcu_read_lock(). ATM, the "v" object has use_count >= 1 (from a > previous get_object) and the next pointer is accessed under > object_list_lock, so no modifications to the list (even put_object > acquires this lock when invoking call_rcu). There is still the bug with > not checking the get_object() return.
Fair enough!
> > Assuming that I do understand, as you say, if the get_object() in > > memleak_seq_next() fails, we could end up accessing freed-up memory on > > the next call to memleak_seq_next(), or even during the current one, > > assuming an aggressive RCU or an extended NMI, SMI, burst of ECC errors > > or some other delay. So I agree that it is necessary to check the return > > value of get_object(). > > Yes
Whew!
> > Also, I do see the put_object() call in memleak_seq_stop(), but it looks > > to me that this only does a put_object() on the last memleak_object. > > What does the put_object() on the earlier memleak_object structures that > > were scanned by memleak_seq_next? Or is there never more than one > > such object in a given list? > > The previous objects' use_count are decremented in memleak_seq_next() > just before returning "next", so between seq_start-seq_next and > seq_next-seq_stop, there is only one object with an incremented > use_count. The memleak_seq_next() function may have two such objects for > a small period of time. > > I actually added a test for this in memleak_scan() (if DEBUG is defined) > and I've never got any reports. There may be some situations when for > very short periods of time the use_count is > 1 at the beginning of a > scan, usually when one of the memleak_scan_area or memleak_ignore > callbacks are invoked. > > I'll revise the locking a bit and re-post the patches this week.
I look forward to seeing them!
Thanx, Paul
| |