Re: [RFC][PATCH 0/1] kmemleak: Fix false positive with alias
From: Paul E. McKenney
Date: Mon Aug 30 2010 - 16:30:46 EST
On Fri, Aug 27, 2010 at 09:12:24AM +0300, Hiroshi DOYU wrote:
> Hi Catalin,
>
> From: Hiroshi DOYU <Hiroshi.DOYU@xxxxxxxxx>
> Subject: Re: [RFC][PATCH 0/1] kmemleak: Fix false positive with alias
> Date: Tue, 10 Aug 2010 18:49:03 +0300 (EEST)
>
> <snip>
> >>> The performance impact is indeed pretty high, though some parts of the
> >>> code look over-engineered to me (the __scan_block function with a loop
> >>> going through an array of two function pointers - I think the compiler
> >>> cannot figure out what to inline). You could just extend the
> >>> find_and_get_object() to search both trees under a single spinlock
> >>> region (as locking also takes time).
> >>
> >> Ok, a good point.
> >
> > Now there's not much difference with the attached patch, a new version
> > of alias.
> >
> > / # modprobe kmemleak-special-test use_alias=0
> > / # time echo scan > /sys/kernel/debug/kmemleak
> > real 0m 2.30s
> > user 0m 0.00s
> > sys 0m 2.30s
> >
> > / # modprobe kmemleak-special-test use_alias=1
> > / # time echo scan > /sys/kernel/debug/kmemleak
> > real 0m 3.91s
> > user 0m 0.00s
> > sys 0m 3.91s
>
> It would be nice if you could have some time to take a look at this
> patch and give some comments.
>
> > From a5670d69b2cafe85f6f26f6951097210d3b9917f Mon Sep 17 00:00:00 2001
> > From: Hiroshi DOYU <Hiroshi.DOYU@xxxxxxxxx>
> > Date: Thu, 17 Jun 2010 13:36:45 +0300
> > Subject: [PATCH 1/1] kmemleak: Fix false positive with address alias
> >
> > There is a false positive case that a pointer is calculated by other
> > methods than the usual container_of macro. "kmemleak_ignore" can cover
> > such a false positive, but it would loose the advantage of memory leak
> > detection. This patch allows kmemleak to work with such false
> > positives by aliasing of address. A client module can register an
> > alias address to an original pointer.
> >
> > A typical use case could be the IOMMU pagetable allocation which
> > stores pointers to the second level of page tables with some
> > conversion, for example, a physical address with attribute bits. Right
> > now I don't have other use cases but I hope that there could be some
> > that this special scan works with.
A few questions below...
Thanx, Paul
> > Signed-off-by: Hiroshi DOYU <Hiroshi.DOYU@xxxxxxxxx>
> > Cc: Phil Carmody <ext-phil.2.carmody@xxxxxxxxx>
> > ---
> > include/linux/kmemleak.h | 8 ++
> > mm/kmemleak.c | 208 +++++++++++++++++++++++++++++++++++++++++++---
> > 2 files changed, 204 insertions(+), 12 deletions(-)
> >
> > diff --git a/include/linux/kmemleak.h b/include/linux/kmemleak.h
> > index 99d9a67..9e2af3a 100644
> > --- a/include/linux/kmemleak.h
> > +++ b/include/linux/kmemleak.h
> > @@ -34,6 +34,8 @@ extern void kmemleak_not_leak(const void *ptr) __ref;
> > extern void kmemleak_ignore(const void *ptr) __ref;
> > extern void kmemleak_scan_area(const void *ptr, size_t size, gfp_t gfp) __ref;
> > extern void kmemleak_no_scan(const void *ptr) __ref;
> > +extern void kmemleak_add_alias(const void *ptr, const void *new) __ref;
> > +extern void kmemleak_unalias(const void *alias) __ref;
> >
> > static inline void kmemleak_alloc_recursive(const void *ptr, size_t size,
> > int min_count, unsigned long flags,
> > @@ -92,6 +94,12 @@ static inline void kmemleak_erase(void **ptr)
> > static inline void kmemleak_no_scan(const void *ptr)
> > {
> > }
> > +static inline void kmemleak_add_alias(const void *ptr, const void *new)
> > +{
> > +}
> > +static inline void kmemleak_unalias(const void *alias)
> > +{
> > +}
> >
> > #endif /* CONFIG_DEBUG_KMEMLEAK */
> >
> > diff --git a/mm/kmemleak.c b/mm/kmemleak.c
> > index 2c0d032..3875cb7 100644
> > --- a/mm/kmemleak.c
> > +++ b/mm/kmemleak.c
> > @@ -157,6 +157,13 @@ struct kmemleak_object {
> > unsigned long jiffies; /* creation timestamp */
> > pid_t pid; /* pid of the current task */
> > char comm[TASK_COMM_LEN]; /* executable name */
> > + struct kmemleak_alias *alias; /* if a pointer is modified */
> > +};
> > +
> > +struct kmemleak_alias {
> > + struct list_head alias_list;
> > + struct prio_tree_node tree_node;
> > + struct kmemleak_object *object;
> > };
> >
> > /* flag representing the memory block allocation status */
> > @@ -179,13 +186,18 @@ struct kmemleak_object {
> > static LIST_HEAD(object_list);
> > /* the list of gray-colored objects (see color_gray comment below) */
> > static LIST_HEAD(gray_list);
> > +/* the list of objects with alias (see alias comment below) */
> > +static LIST_HEAD(alias_list);
> > /* prio search tree for object boundaries */
> > static struct prio_tree_root object_tree_root;
> > +/* prio search tree for alias object boundaries */
> > +static struct prio_tree_root alias_tree_root;
> > /* rw_lock protecting the access to object_list and prio_tree_root */
> > static DEFINE_RWLOCK(kmemleak_lock);
> >
> > /* allocation caches for kmemleak internal data */
> > static struct kmem_cache *object_cache;
> > +static struct kmem_cache *alias_cache;
> > static struct kmem_cache *scan_area_cache;
> >
> > /* set if tracing memory operations is enabled */
> > @@ -269,6 +281,8 @@ static void kmemleak_disable(void);
> > kmemleak_disable(); \
> > } while (0)
> >
> > +#define to_address(obj) ((obj)->tree_node.start)
> > +
> > /*
> > * Printing of the objects hex dump to the seq file. The number of lines to be
> > * printed is limited to HEX_MAX_LINES to prevent seq file spamming. The
> > @@ -369,7 +383,7 @@ static void dump_object_info(struct kmemleak_object *object)
> > trace.entries = object->trace;
> >
> > pr_notice("Object 0x%08lx (size %zu):\n",
> > - object->tree_node.start, object->size);
> > + to_address(object), object->size);
> > pr_notice(" comm \"%s\", pid %d, jiffies %lu\n",
> > object->comm, object->pid, object->jiffies);
> > pr_notice(" min_count = %d\n", object->min_count);
> > @@ -436,6 +450,8 @@ static void free_object_rcu(struct rcu_head *rcu)
> > hlist_del(elem);
> > kmem_cache_free(scan_area_cache, area);
> > }
> > + if (object->alias)
> > + kmem_cache_free(alias_cache, object->alias);
> > kmem_cache_free(object_cache, object);
> > }
> >
> > @@ -460,12 +476,11 @@ static void put_object(struct kmemleak_object *object)
> > /*
> > * Look up an object in the prio search tree and increase its use_count.
> > */
> > -static struct kmemleak_object *find_and_get_object(unsigned long ptr, int alias)
> > +static struct kmemleak_object *__find_and_get_object(unsigned long ptr, int alias)
> > {
> > unsigned long flags;
> > struct kmemleak_object *object = NULL;
> >
> > - rcu_read_lock();
> > read_lock_irqsave(&kmemleak_lock, flags);
> > if (ptr >= min_addr && ptr < max_addr)
> > object = lookup_object(ptr, alias);
> > @@ -474,6 +489,75 @@ static struct kmemleak_object *find_and_get_object(unsigned long ptr, int alias)
> > /* check whether the object is still available */
> > if (object && !get_object(object))
> > object = NULL;
> > +
> > + return object;
> > +}
> > +
> > +static struct kmemleak_object *find_and_get_object(unsigned long ptr, int alias)
> > +{
> > + struct kmemleak_object *object;
> > +
> > + rcu_read_lock();
> > + object = __find_and_get_object(ptr, alias);
> > + rcu_read_unlock();
> > +
> > + return object;
> > +}
> > +
> > +static struct kmemleak_object *__find_and_get_alias(unsigned long ptr, int alias)
> > +{
> > + struct kmemleak_object *object = NULL;
> > + struct kmemleak_alias *ao = NULL;
> > + struct prio_tree_node *node;
> > + struct prio_tree_iter iter;
> > + unsigned long flags;
> > +
> > + read_lock_irqsave(&kmemleak_lock, flags);
If we hold this readlock, how is RCU helping us? Or are there updates
that do not write-hold kmemleak_lock?
> > +
> > + prio_tree_iter_init(&iter, &alias_tree_root, ptr, ptr);
> > + node = prio_tree_next(&iter);
> > + if (node) {
> > + ao = prio_tree_entry(node, struct kmemleak_alias, tree_node);
> > + if (!alias && to_address(ao) != ptr) {
> > + kmemleak_warn("Found object by alias");
> > + ao = NULL;
> > + }
> > + }
> > +
> > + read_unlock_irqrestore(&kmemleak_lock, flags);
> > +
> > + if (ao && get_object(ao->object))
> > + object = ao->object;
> > +
> > + return object;
> > +}
> > +
> > +static struct kmemleak_object *find_and_get_alias(unsigned long ptr, int alias)
> > +{
> > + struct kmemleak_object *object = NULL;
> > +
> > + rcu_read_lock();
> > + object = __find_and_get_alias(ptr, alias);
> > + rcu_read_unlock();
> > +
> > + return object;
> > +}
> > +
> > +/*
> > + * Try to find object first, and then with alias address if not found.
> > + */
> > +static struct kmemleak_object *find_and_get_object_with_alias(unsigned long ptr,
> > + int alias)
> > +{
> > + struct kmemleak_object *object = NULL;
> > +
> > + rcu_read_lock();
> > +
> > + object = __find_and_get_object(ptr, alias);
> > + if (!object &&
> > + !prio_tree_empty(&alias_tree_root))
> > + object = __find_and_get_alias(ptr, alias);
> > +
> > rcu_read_unlock();
> >
> > return object;
> > @@ -524,6 +608,7 @@ static struct kmemleak_object *create_object(unsigned long ptr, size_t size,
> > object->count = 0; /* white color initially */
> > object->jiffies = jiffies;
> > object->checksum = 0;
> > + object->alias = NULL;
> >
> > /* task information */
> > if (in_irq()) {
> > @@ -547,7 +632,7 @@ static struct kmemleak_object *create_object(unsigned long ptr, size_t size,
> > object->trace_len = __save_stack_trace(object->trace);
> >
> > INIT_PRIO_TREE_NODE(&object->tree_node);
> > - object->tree_node.start = ptr;
> > + to_address(object) = ptr;
> > object->tree_node.last = ptr + size - 1;
> >
> > write_lock_irqsave(&kmemleak_lock, flags);
> > @@ -577,6 +662,57 @@ out:
> > return object;
> > }
> >
> > +static void create_alias_object(struct kmemleak_object *object,
> > + unsigned long ptr)
> > +{
> > + struct kmemleak_alias *alias;
> > + struct prio_tree_node *node;
> > + unsigned long flags;
> > +
> > + alias = kmem_cache_alloc(alias_cache, GFP_KERNEL);
> > + if (!alias) {
> > + kmemleak_stop("Cannot allocate a kmemleak_alias structure\n");
> > + return;
> > + }
> > + INIT_LIST_HEAD(&alias->alias_list);
> > + INIT_PRIO_TREE_NODE(&alias->tree_node);
> > + to_address(alias) = ptr;
> > +
> > + spin_lock_irqsave(&object->lock, flags);
> > + alias->tree_node.last = ptr + object->size - 1;
> > + alias->object = object;
> > + object->alias = alias;
> > + spin_unlock_irqrestore(&object->lock, flags);
> > +
> > + write_lock_irqsave(&kmemleak_lock, flags);
> > +
> > + node = prio_tree_insert(&alias_tree_root, &alias->tree_node);
> > + if (!node) {
> > + kmemleak_warn("Cannot allocate a kmemleak_alias structure\n");
> > + kmem_cache_free(alias_cache, alias);
> > + }
> > + list_add_tail_rcu(&alias->alias_list, &alias_list);
> > +
> > + write_unlock_irqrestore(&kmemleak_lock, flags);
> > +}
> > +
> > +static void __delete_alias_object(struct kmemleak_object *object)
> > +{
> > + prio_tree_remove(&alias_tree_root, &object->alias->tree_node);
> > + list_del_rcu(&object->alias->alias_list);
Don't we need an RCU grace period here, based on either synchronize_rcu()
or call_rcu()? Perhaps calling free_object_rcu(), though perhaps it frees
up more than you would like.
> > + kmem_cache_free(alias_cache, object->alias);
> > + object->alias = NULL;
> > +}
> > +
> > +static void delete_alias_object(struct kmemleak_object *object)
> > +{
> > + unsigned long flags;
> > +
> > + write_lock_irqsave(&kmemleak_lock, flags);
> > + __delete_alias_object(object);
> > + write_unlock_irqrestore(&kmemleak_lock, flags);
> > +}
> > +
> > /*
> > * Remove the metadata (struct kmemleak_object) for a memory block from the
> > * object_list and object_tree_root and decrement its use_count.
> > @@ -588,6 +724,8 @@ static void __delete_object(struct kmemleak_object *object)
> > write_lock_irqsave(&kmemleak_lock, flags);
> > prio_tree_remove(&object_tree_root, &object->tree_node);
> > list_del_rcu(&object->object_list);
> > + if (object->alias)
> > + __delete_alias_object(object);
> > write_unlock_irqrestore(&kmemleak_lock, flags);
> >
> > WARN_ON(!(object->flags & OBJECT_ALLOCATED));
> > @@ -630,7 +768,7 @@ static void delete_object_full(unsigned long ptr)
> > */
> > static void delete_object_part(unsigned long ptr, size_t size)
> > {
> > - struct kmemleak_object *object;
> > + struct kmemleak_object *object, *new;
> > unsigned long start, end;
> >
> > object = find_and_get_object(ptr, 1);
> > @@ -652,12 +790,24 @@ static void delete_object_part(unsigned long ptr, size_t size)
> > */
> > start = object->pointer;
> > end = object->pointer + object->size;
> > - if (ptr > start)
> > - create_object(start, ptr - start, object->min_count,
> > - GFP_KERNEL);
> > - if (ptr + size < end)
> > - create_object(ptr + size, end - ptr - size, object->min_count,
> > - GFP_KERNEL);
> > + if (ptr > start) {
> > + new = create_object(start, ptr - start, object->min_count,
> > + GFP_KERNEL);
> > + if (new && unlikely(object->alias))
> > + create_alias_object(new, to_address(object->alias));
> > + }
> > + if (ptr + size < end) {
> > + new = create_object(ptr + size, end - ptr - size,
> > + object->min_count, GFP_KERNEL);
> > + if (new && unlikely(object->alias)) {
> > + unsigned long alias_ptr;
> > +
> > + alias_ptr = to_address(object->alias);
> > + alias_ptr += ptr - start + size;
> > +
> > + create_alias_object(new, alias_ptr);
> > + }
> > + }
> >
> > put_object(object);
> > }
> > @@ -944,6 +1094,38 @@ void __ref kmemleak_no_scan(const void *ptr)
> > }
> > EXPORT_SYMBOL(kmemleak_no_scan);
> >
> > +void kmemleak_add_alias(const void *ptr, const void *alias)
> > +{
> > + struct kmemleak_object *object;
> > +
> > + pr_debug("%s(0x%p -> 0x%p)\n", __func__, ptr, alias);
> > +
> > + object = find_and_get_object((unsigned long)ptr, 0);
> > + if (!object) {
> > + kmemleak_warn("Aliasing unknown object at 0x%p\n", ptr);
> > + return;
> > + }
> > + create_alias_object(object, (unsigned long)alias);
> > + put_object(object);
> > +}
> > +EXPORT_SYMBOL(kmemleak_add_alias);
> > +
> > +void kmemleak_unalias(const void *alias)
> > +{
> > + struct kmemleak_object *object;
> > +
> > + pr_debug("%s(0x%p)\n", __func__, alias);
> > +
> > + object = find_and_get_alias((unsigned long)alias, 0);
> > + if (!object) {
> > + kmemleak_warn("Aliasing unknown object at 0x%p\n", alias);
> > + return;
> > + }
> > + delete_alias_object(object);
> > + put_object(object);
> > +}
> > +EXPORT_SYMBOL(kmemleak_unalias);
> > +
> > /*
> > * Update an object's checksum and return true if it was modified.
> > */
> > @@ -1007,7 +1189,7 @@ static void scan_block(void *_start, void *_end,
> >
> > pointer = *ptr;
> >
> > - object = find_and_get_object(pointer, 1);
> > + object = find_and_get_object_with_alias(pointer, 1);
> > if (!object)
> > continue;
> > if (object == scanned) {
> > @@ -1620,8 +1802,10 @@ void __init kmemleak_init(void)
> > jiffies_scan_wait = msecs_to_jiffies(SECS_SCAN_WAIT * 1000);
> >
> > object_cache = KMEM_CACHE(kmemleak_object, SLAB_NOLEAKTRACE);
> > + alias_cache = KMEM_CACHE(kmemleak_alias, SLAB_NOLEAKTRACE);
> > scan_area_cache = KMEM_CACHE(kmemleak_scan_area, SLAB_NOLEAKTRACE);
> > INIT_PRIO_TREE_ROOT(&object_tree_root);
> > + INIT_PRIO_TREE_ROOT(&alias_tree_root);
> >
> > /* the kernel is still in UP mode, so disabling the IRQs is enough */
> > local_irq_save(flags);
> > --
> > 1.7.1.rc2
> >
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/