Skip to contentSkip to conversation

Kernel memory leak detector 0.13

PATCH In review Catalin Marinas 4 participants 41 messages Dec 16, 2006 – Dec 28, 2006

Subsystems (18)
lore
Share & tools
lore
#0 lore raw

cover Kernel memory leak detector 0.13

This series of patches represent version 0.13 of the kernel memory leak detector. See the Documentation/kmemleak.txt file for a more detailed description. The patches are downloadable from (the whole patch or the broken-out series) http://www.procode.org/kmemleak/

What's new in this version:

- updated to Linux 2.6.20-rc1
- fixed a bug noticeable with a big number of reported memory leaks

Signature · 1 line
Catalin
#1 lore raw

PATCH 1/10 Base support for kmemleak

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.

---

 include/linux/kernel.h  |    7 
 include/linux/memleak.h |  111 ++++
 init/main.c             |    3 
 lib/Kconfig.debug       |  114 ++++
 mm/Makefile             |    1 
 mm/memleak.c            | 1478 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 1712 insertions(+), 2 deletions(-)
include/linux/kernel.h +6 -1
index b0c4a05..2fca6bf 100644
@@ -14,6 +14,7 @@
 #include <linux/compiler.h>
 #include <linux/bitops.h>
 #include <linux/log2.h>
+#include <linux/memleak.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
 
@@ -285,9 +286,13 @@ static inline int __attribute__ ((format
  * @member:	the name of the member within the struct.
  *
  */
-#define container_of(ptr, type, member) ({			\
+#define __container_of(ptr, type, member) ({			\
         const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
         (type *)( (char *)__mptr - offsetof(type,member) );})
+#define container_of(ptr, type, member) ({			\
+	DECLARE_MEMLEAK_OFFSET(container_of, type, member);	\
+	__container_of(ptr, type, member);			\
+})
 
 /*
  * Check at compile time that something is of a particular type.
include/linux/memleak.h new file +111 -0

111 lines not on this page · raw message

init/main.c +2 -1
index e3f0bb2..c5cdc87 100644
@@ -584,6 +584,8 @@ asmlinkage void __init start_kernel(void
 	cpuset_init_early();
 	mem_init();
 	kmem_cache_init();
+	radix_tree_init();
+	memleak_init();
 	setup_per_cpu_pageset();
 	numa_policy_init();
 	if (late_time_init)
@@ -604,7 +606,6 @@ asmlinkage void __init start_kernel(void
 	key_init();
 	security_init();
 	vfs_caches_init(num_physpages);
-	radix_tree_init();
 	signals_init();
 	/* rootfs populating might need page-writeback */
 	page_writeback_init();
lib/Kconfig.debug +114 -0

120 lines not on this page · raw message

mm/Makefile +1 -0
index f3c077e..aafe03f 100644
@@ -29,3 +29,4 @@ obj-$(CONFIG_MEMORY_HOTPLUG) += memory_h
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
 obj-$(CONFIG_MIGRATION) += migrate.o
 obj-$(CONFIG_SMP) += allocpercpu.o
+obj-$(CONFIG_DEBUG_MEMLEAK) += memleak.o
mm/memleak.c new file +1478 -0

1,478 lines not on this page · raw message

#2 lore raw

PATCH 2/10 Kmemleak documentation

In reply to Catalin Marinas

---

 Documentation/kmemleak.txt |  161 ++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 161 insertions(+), 0 deletions(-)
Documentation/kmemleak.txt new file +161 -0
new file mode 100644
index 0000000..4689f85
@@ -0,0 +1,161 @@
+Kernel Memory Leak Detector
+===========================
+
+
+Introduction
+------------
+
+Kmemleak provides a way of detecting possible kernel memory leaks in a
+way similar to a tracing garbage collector
+(http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Tracing_garbage_collectors),
+with the difference that the orphan objects are not freed but only
+reported via /sys/kernel/debug/memleak. A similar method is used by
+the Valgrind tool (memcheck --leak-check) to detect the memory leaks
+in user-space applications.
+
+
+Usage
+-----
+
+CONFIG_DEBUG_MEMLEAK has to be enabled. For additional config options,
+look in:
+
+  -> Kernel hacking
+    -> Kernel debugging
+      -> Debug slab memory allocations
+        -> Kernel memory leak detector
+
+To display the possible memory leaks:
+
+  # mount -t debugfs nodev /sys/kernel/debug/
+  # cat /sys/kernel/debug/memleak
+
+In order to reduce the run-time overhead, memory scanning is only
+performed when reading the /sys/kernel/debug/memleak file. Note that
+the orphan objects are listed in the order they were allocated and one
+object at the beginning of the list may cause other subsequent objects
+to be reported as orphan.
+
+
+Basic Algorithm
+---------------
+
+The memory allocations via kmalloc, vmalloc, kmem_cache_alloc and
+friends are tracked and the pointers, together with additional
+information like size and stack trace, are stored in a hash table. The
+corresponding freeing function calls are tracked and the pointers
+removed from the hash table.
+
+An allocated block of memory is considered orphan if no pointer to its
+start address or to an alias (pointer aliases are explained later) can
+be found by scanning the memory (including saved registers). This
+means that there might be no way for the kernel to pass the address of
+the allocated block to a freeing function and therefore the block is
+considered a leak.
+
+The scanning algorithm steps:
+
+  1. mark all objects as white (remaining white objects will later be
+     considered orphan)
+  2. scan the memory starting with the data section and stacks,
+     checking the values against the addresses stored in the hash
+     table. If a pointer to a white object is found, the object is
+     added to the grey list
+  3. scan the grey objects for matching addresses (some white objects
+     can become grey and added at the end of the grey list) until the
+     grey set is finished
+  4. the remaining white objects are considered orphan and reported
+     via /sys/kernel/debug/memleak
+
+
+Improvements
+------------
+
+Because the Linux kernel calculates many pointers at run-time via the
+container_of macro (see the lists implementation), a lot of false
+positives would be reported. This tool re-writes the container_of
+macro so that the offset and type information is stored in the
+.init.memleak_offsets section. The memleak_init() function creates a
+radix tree with corresponding offsets for every encountered block
+type. The memory allocations hook stores the pointer address together
+with its aliases based on the type of the allocated block.
+
+While one level of offsets should be enough for most cases, a second
+level, i.e. container_of(container_of(...)), can be enabled via the
+configuration options (one false positive is the "struct socket_alloc"
+allocation in the sock_alloc_inode() function).
+
+Some allocated memory blocks have pointers stored in the kernel's
+internal data structures and they cannot be detected as orphans. To
+avoid this, kmemleak can also store the number of values equal to the
+pointer (or aliases) that need to be found so that the block is not
+considered a leak. One example is __vmalloc().
+
+
+Limitations and Drawbacks
+-------------------------
+
+The biggest drawback is the reduced performance of memory allocation
+and freeing. To avoid other penalties, the memory scanning is only
+performed when the /sys/kernel/debug/memleak file is read. Anyway,
+this tool is intended for debugging purposes where the performance
+might not be the most important requirement.
+
+Kmemleak currently approximates the type id using the sizeof()
+compiler built-in function. This is not accurate and can lead to false
+negatives. The aim is to gradually change the kernel and kmemleak to
+do more precise type identification.
+
+Another source of false negatives is the data stored in non-pointer
+values. Together with the more precise type identification, kmemleak
+could only scan the pointer members in the allocated structures.
+
+The tool can report false positives. These are cases where an
+allocated block doesn't need to be freed (some cases in the init_call
+functions), the pointer is calculated by other methods than the
+container_of macro or the pointer is stored in a location not scanned
+by kmemleak. If the "member" argument in the offsetof(type, member)
+call is not constant, kmemleak considers the offset as zero since it
+cannot be determined at compilation time.
+
+Page allocations and ioremap are not tracked. Only the ARM and i386
+architectures are currently supported.
+
+
+Kmemleak API
+------------
+
+See the include/linux/memleak.h header for the functions prototype.
+
+memleak_init		- initialize kmemleak
+memleak_alloc		- notify of a memory block allocation
+memleak_free		- notify of a memory block freeing
+memleak_padding		- mark the boundaries of the data inside the block
+memleak_not_leak	- mark an object as not a leak
+memleak_ignore		- do not scan or report an object as leak
+memleak_scan_area	- add scan areas inside a memory block
+memleak_insert_aliases	- add aliases for a given type
+memleak_erase		- erase an old value in a pointer variable
+memleak_typeid_raw	- set the typeid for an allocated block
+memleak_container	- statically declare a pointer alias
+memleak_typeid		- set the typeid for an allocated block (takes
+			  a type rather than typeid as argument)
+
+
+Dealing with false positives/negatives
+--------------------------------------
+
+To reduce the false negatives, kmemleak provides the memleak_ignore,
+memleak_scan_area and memleak_erase functions. The task stacks also
+increase the amount of false negatives and their scanning is not
+enabled by default.
+
+To eliminate the false positives caused by code allocating a different
+size from the object one (either for alignment or for extra memory
+after the end of the structure), kmemleak provides the memleak_padding
+and memleak_typeid functions.
+
+For objects known not to be leaks, kmemleak provides the
+memleak_not_leak function. The memleak_ignore could also be used if
+the memory block is known not to contain other pointers and it will no
+longer be scanned.
#3 lore raw

PATCH 3/10 Add the memory allocation/freeing hooks for kmemleak

In reply to Catalin Marinas

This patch adds the callbacks to memleak_(alloc|free) functions from kmalloc/kfree, kmem_cache_(alloc|free), vmalloc/vfree etc.

---

 include/linux/slab_def.h |    6 ++++++
 mm/page_alloc.c          |    2 ++
 mm/slab.c                |   19 +++++++++++++++++--
 mm/vmalloc.c             |   22 ++++++++++++++++++++--
 4 files changed, 45 insertions(+), 4 deletions(-)
include/linux/slab_def.h +6 -0
index 4b463e6..30d4bd9 100644
@@ -25,6 +25,7 @@ extern struct cache_sizes malloc_sizes[]
 
 static inline void *kmalloc(size_t size, gfp_t flags)
 {
+#ifndef CONFIG_DEBUG_MEMLEAK
 	if (__builtin_constant_p(size)) {
 		int i = 0;
 #define CACHE(x) \
@@ -43,11 +44,13 @@ found:
 			malloc_sizes[i].cs_dmacachep :
 			malloc_sizes[i].cs_cachep, flags);
 	}
+#endif
 	return __kmalloc(size, flags);
 }
 
 static inline void *kzalloc(size_t size, gfp_t flags)
 {
+#ifndef CONFIG_DEBUG_MEMLEAK
 	if (__builtin_constant_p(size)) {
 		int i = 0;
 #define CACHE(x) \
@@ -66,6 +69,7 @@ found:
 			malloc_sizes[i].cs_dmacachep :
 			malloc_sizes[i].cs_cachep, flags);
 	}
+#endif
 	return __kzalloc(size, flags);
 }
 
@@ -74,6 +78,7 @@ extern void *__kmalloc_node(size_t size,
 
 static inline void *kmalloc_node(size_t size, gfp_t flags, int node)
 {
+#ifndef CONFIG_DEBUG_MEMLEAK
 	if (__builtin_constant_p(size)) {
 		int i = 0;
 #define CACHE(x) \
@@ -92,6 +97,7 @@ found:
 			malloc_sizes[i].cs_dmacachep :
 			malloc_sizes[i].cs_cachep, flags, node);
 	}
+#endif
 	return __kmalloc_node(size, flags, node);
 }
 
mm/page_alloc.c +2 -0
index 8c1a116..816e909 100644
@@ -3363,6 +3363,8 @@ void *__init alloc_large_system_hash(con
 	if (_hash_mask)
 		*_hash_mask = (1 << log2qty) - 1;
 
+	memleak_alloc(table, size, 1);
+
 	return table;
 }
 
mm/slab.c +17 -2
index 909975f..4db2029 100644
@@ -2574,6 +2574,9 @@ static struct slab *alloc_slabmgmt(struc
 		/* Slab management obj is off-slab. */
 		slabp = kmem_cache_alloc_node(cachep->slabp_cache,
 					      local_flags & ~GFP_THISNODE, nodeid);
+		/* only scan the list member to avoid false negatives */
+		memleak_scan_area(slabp, offsetof(struct slab, list),
+				  sizeof(struct list_head));
 		if (!slabp)
 			return NULL;
 	} else {
@@ -3194,6 +3197,8 @@ static inline void *____cache_alloc(stru
 		STATS_INC_ALLOCMISS(cachep);
 		objp = cache_alloc_refill(cachep, flags);
 	}
+	/* avoid false negatives */
+	memleak_erase(&ac->entry[ac->avail]);
 	return objp;
 }
 
@@ -3222,6 +3227,7 @@ static __always_inline void *__cache_all
 	local_irq_restore(save_flags);
 	objp = cache_alloc_debugcheck_after(cachep, flags, objp,
 					    caller);
+	memleak_alloc(objp, obj_size(cachep), 1);
 	prefetchw(objp);
 	return objp;
 }
@@ -3492,6 +3498,7 @@ static inline void __cache_free(struct k
 	struct array_cache *ac = cpu_cache_get(cachep);
 
 	check_irq_off();
+	memleak_free(objp);
 	objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
 
 	if (cache_free_alien(cachep, objp))
@@ -3628,6 +3635,7 @@ __cache_alloc_node(struct kmem_cache *ca
 
 	local_irq_restore(save_flags);
 	ptr = cache_alloc_debugcheck_after(cachep, flags, ptr, caller);
+	memleak_alloc(ptr, obj_size(cachep), 1);
 
 	return ptr;
 }
@@ -3643,11 +3651,14 @@ static __always_inline void *
 __do_kmalloc_node(size_t size, gfp_t flags, int node, void *caller)
 {
 	struct kmem_cache *cachep;
+	void *ptr;
 
 	cachep = kmem_find_general_cachep(size, flags);
 	if (unlikely(cachep == NULL))
 		return NULL;
-	return kmem_cache_alloc_node(cachep, flags, node);
+	ptr = kmem_cache_alloc_node(cachep, flags, node);
+	memleak_padding(ptr, 0, size);
+	return ptr;
 }
 
 #ifdef CONFIG_DEBUG_SLAB
@@ -3683,6 +3694,7 @@ static __always_inline void *__do_kmallo
 					  void *caller)
 {
 	struct kmem_cache *cachep;
+	void *ptr;
 
 	/* If you want to save a few bytes .text space: replace
 	 * __ with kmem_.
@@ -3692,7 +3704,10 @@ static __always_inline void *__do_kmallo
 	cachep = __find_general_cachep(size, flags);
 	if (unlikely(cachep == NULL))
 		return NULL;
-	return __cache_alloc(cachep, flags, caller);
+	ptr = __cache_alloc(cachep, flags, caller);
+	memleak_padding(ptr, 0, size);
+
+	return ptr;
 }
 
 
mm/vmalloc.c +20 -2
index 86897ee..603aee9 100644
@@ -365,6 +365,9 @@ void __vunmap(void *addr, int deallocate
 void vfree(void *addr)
 {
 	BUG_ON(in_interrupt());
+
+	memleak_free(addr);
+
 	__vunmap(addr, 1);
 }
 EXPORT_SYMBOL(vfree);
@@ -465,7 +468,14 @@ fail:
 
 void *__vmalloc_area(struct vm_struct *area, gfp_t gfp_mask, pgprot_t prot)
 {
-	return __vmalloc_area_node(area, gfp_mask, prot, -1);
+	void *addr = __vmalloc_area_node(area, gfp_mask, prot, -1);
+
+	/* this needs ref_count = 2 since vm_struct also contains a
+	 * pointer to this address. The guard page is also subtracted
+	 * from the size */
+	memleak_alloc(addr, area->size - PAGE_SIZE, 2);
+
+	return addr;
 }
 
 /**
@@ -483,6 +493,8 @@ static void *__vmalloc_node(unsigned lon
 			    int node)
 {
 	struct vm_struct *area;
+	void *addr;
+	unsigned long real_size = size;
 
 	size = PAGE_ALIGN(size);
 	if (!size || (size >> PAGE_SHIFT) > num_physpages)
@@ -492,7 +504,13 @@ static void *__vmalloc_node(unsigned lon
 	if (!area)
 		return NULL;
 
-	return __vmalloc_area_node(area, gfp_mask, prot, node);
+	addr = __vmalloc_area_node(area, gfp_mask, prot, node);
+
+	/* this needs ref_count = 2 since the vm_struct also contains
+	   a pointer to this address */
+	memleak_alloc(addr, real_size, 2);
+
+	return addr;
 }
 
 void *__vmalloc(unsigned long size, gfp_t gfp_mask, pgprot_t prot)
#4 lore raw

PATCH 4/10 Modules support for kmemleak

In reply to Catalin Marinas

This patch handles the kmemleak operations needed for modules loading so that memory allocations from inside a module are properly tracked.

---

 kernel/module.c |   56 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 56 insertions(+), 0 deletions(-)
kernel/module.c +56 -0
index b565eae..f1ff3f5 100644
@@ -345,6 +345,7 @@ static void *percpu_modalloc(unsigned lo
 	unsigned long extra;
 	unsigned int i;
 	void *ptr;
+	int cpu;
 
 	if (align > SMP_CACHE_BYTES) {
 		printk(KERN_WARNING "%s: per-cpu alignment %li > %i\n",
@@ -374,6 +375,10 @@ static void *percpu_modalloc(unsigned lo
 			if (!split_block(i, size))
 				return NULL;
 
+		/* add the per-cpu scanning areas */
+		for_each_possible_cpu(cpu)
+			memleak_alloc(ptr + per_cpu_offset(cpu), size, 0);
+
 		/* Mark allocated */
 		pcpu_size[i] = -pcpu_size[i];
 		return ptr;
@@ -388,6 +393,7 @@ static void percpu_modfree(void *freeme)
 {
 	unsigned int i;
 	void *ptr = __per_cpu_start + block_size(pcpu_size[0]);
+	int cpu;
 
 	/* First entry is core kernel percpu data. */
 	for (i = 1; i < pcpu_num_used; ptr += block_size(pcpu_size[i]), i++) {
@@ -399,6 +405,10 @@ static void percpu_modfree(void *freeme)
 	BUG();
 
  free:
+	/* remove the per-cpu scanning areas */
+	for_each_possible_cpu(cpu)
+		memleak_free(freeme + per_cpu_offset(cpu));
+
 	/* Merge with previous? */
 	if (pcpu_size[i-1] >= 0) {
 		pcpu_size[i-1] += pcpu_size[i];
@@ -1529,6 +1539,42 @@ static inline void add_kallsyms(struct m
 }
 #endif /* CONFIG_KALLSYMS */
 
+#ifdef CONFIG_DEBUG_MEMLEAK
+static void memleak_load_module(struct module *mod, Elf_Ehdr *hdr,
+				Elf_Shdr *sechdrs, char *secstrings)
+{
+	unsigned int mloffindex, i;
+
+	/* insert any new pointer aliases */
+	mloffindex = find_sec(hdr, sechdrs, secstrings, ".init.memleak_offsets");
+	if (mloffindex)
+		memleak_insert_aliases((void *)sechdrs[mloffindex].sh_addr,
+				       (void *)sechdrs[mloffindex].sh_addr
+				       + sechdrs[mloffindex].sh_size);
+
+	/* only scan the sections containing data */
+	memleak_scan_area(mod->module_core,
+			  (unsigned long)mod - (unsigned long)mod->module_core,
+			  sizeof(struct module));
+
+	for (i = 1; i < hdr->e_shnum; i++) {
+		if (!(sechdrs[i].sh_flags & SHF_ALLOC))
+			continue;
+		if (strncmp(secstrings + sechdrs[i].sh_name, ".data", 5) != 0
+		    && strncmp(secstrings + sechdrs[i].sh_name, ".bss", 4) != 0)
+			continue;
+
+		memleak_scan_area(mod->module_core,
+				  sechdrs[i].sh_addr - (unsigned long)mod->module_core,
+				  sechdrs[i].sh_size);
+	}
+}
+#else
+static inline void memleak_load_module(struct module *mod, Elf_Ehdr *hdr,
+				       Elf_Shdr *sechdrs, char *secstrings)
+{ }
+#endif
+
 /* Allocate and load the module: note that size of section 0 is always
    zero, and we rely on this for optional sections. */
 static struct module *load_module(void __user *umod,
@@ -1724,6 +1770,10 @@ static struct module *load_module(void _
 
 	/* Do the allocs. */
 	ptr = module_alloc(mod->core_size);
+	/* the pointer to this block is stored in the module structure
+	 * which is inside the block. Just mark it as not being a
+	 * leak */
+	memleak_not_leak(ptr);
 	if (!ptr) {
 		err = -ENOMEM;
 		goto free_percpu;
@@ -1732,6 +1782,11 @@ static struct module *load_module(void _
 	mod->module_core = ptr;
 
 	ptr = module_alloc(mod->init_size);
+	/* the pointer to this block is stored in the module structure
+	 * which is inside the block. This block doesn't need to be
+	 * scanned as it contains data and code that will be freed
+	 * after the module is initialized */
+	memleak_ignore(ptr);
 	if (!ptr && mod->init_size) {
 		err = -ENOMEM;
 		goto free_core;
@@ -1762,6 +1817,7 @@ static struct module *load_module(void _
 	}
 	/* Module has been moved. */
 	mod = (void *)sechdrs[modindex].sh_addr;
+	memleak_load_module(mod, hdr, sechdrs, secstrings);
 
 	/* Now we've moved module, initialize linked lists, etc. */
 	module_unload_init(mod);
#5 lore raw

PATCH 5/10 Add kmemleak support for i386

In reply to Catalin Marinas

This patch adds the kmemleak-related entries to the vmlinux.lds.S linker script.

---

 arch/i386/kernel/vmlinux.lds.S |    6 ++++++
 include/asm-i386/thread_info.h |   18 ++++++++++++++++--
 2 files changed, 22 insertions(+), 2 deletions(-)
arch/i386/kernel/vmlinux.lds.S +6 -0
index a53c8b1..2850bed 100644
@@ -69,6 +69,7 @@ SECTIONS
 
   /* writeable */
   . = ALIGN(4096);
+  _sdata = .;			/* Start of data section */
   .data : AT(ADDR(.data) - LOAD_OFFSET) {	/* Data */
 	*(.data)
 	CONSTRUCTORS
@@ -193,6 +194,11 @@ SECTIONS
 	*(.data.percpu)
 	__per_cpu_end = .;
   }
+  .init.memleak_offsets : AT(ADDR(.init.memleak_offsets) - LOAD_OFFSET) {
+	__memleak_offsets_start = .;
+	*(.init.memleak_offsets)
+	__memleak_offsets_end = .;
+  }
   . = ALIGN(4096);
   /* freed after init ends here */
 	
include/asm-i386/thread_info.h +16 -2
index 4b187bb..02f3457 100644
@@ -95,9 +95,23 @@ static inline struct thread_info *curren
 
 /* thread information allocation */
 #ifdef CONFIG_DEBUG_STACK_USAGE
-#define alloc_thread_info(tsk) kzalloc(THREAD_SIZE, GFP_KERNEL)
+#define alloc_thread_info(tsk)					\
+	({							\
+		struct thread_info *ret;			\
+								\
+		ret = kzalloc(THREAD_SIZE, GFP_KERNEL);		\
+		memleak_ignore(ret);				\
+		ret;						\
+	})
 #else
-#define alloc_thread_info(tsk) kmalloc(THREAD_SIZE, GFP_KERNEL)
+#define alloc_thread_info(tsk)					\
+	({							\
+		struct thread_info *ret;			\
+								\
+		ret = kmalloc(THREAD_SIZE, GFP_KERNEL);		\
+		memleak_ignore(ret);				\
+		ret;						\
+	})
 #endif
 
 #define free_thread_info(info)	kfree(info)
#6 lore raw

PATCH 6/10 Add kmemleak support for ARM

In reply to Catalin Marinas

This patch adds the kmemleak-related entries to the vmlinux.lds.S linker script.

---

 arch/arm/kernel/vmlinux.lds.S |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)
arch/arm/kernel/vmlinux.lds.S +7 -0
index a8fa75e..7ec22ad 100644
@@ -61,6 +61,11 @@ SECTIONS
 		__per_cpu_start = .;
 			*(.data.percpu)
 		__per_cpu_end = .;
+#ifdef CONFIG_DEBUG_MEMLEAK
+		__memleak_offsets_start = .;
+			*(.init.memleak_offsets)
+		__memleak_offsets_end = .;
+#endif
 #ifndef CONFIG_XIP_KERNEL
 		__init_begin = _stext;
 		*(.init.data)
@@ -109,6 +114,7 @@ SECTIONS
 
 	.data : AT(__data_loc) {
 		__data_start = .;	/* address in memory */
+		_sdata = .;
 
 		/*
 		 * first, the init task union, aligned
@@ -159,6 +165,7 @@ SECTIONS
 		__bss_start = .;	/* BSS				*/
 		*(.bss)
 		*(COMMON)
+		__bss_stop = .;
 		_end = .;
 	}
 					/* Stabs debugging sections.	*/
#7 lore raw

PATCH 7/10 Remove some of the kmemleak false positives

In reply to Catalin Marinas

There are allocations for which the main pointer cannot be found but they are not memory leaks. This patch fixes some of them. For more information on false positives, see Documentation/kmemleak.txt.

---

 arch/i386/kernel/setup.c               |    2 ++
 drivers/base/platform.c                |    3 +++
 drivers/char/vt.c                      |    4 ++++
 drivers/hwmon/w83627hf.c               |    4 ++++
 drivers/scsi/hosts.c                   |    3 +++
 drivers/video/console/fbcon.c          |    3 +++
 fs/ext3/dir.c                          |    3 +++
 include/linux/percpu.h                 |    5 +++++
 ipc/util.c                             |    6 ++++++
 kernel/params.c                        |    8 +++++++-
 net/core/dev.c                         |    6 ++++++
 net/core/skbuff.c                      |    3 +++
 net/ipv4/netfilter/ip_conntrack_core.c |    5 +++++
 net/sched/sch_generic.c                |    5 +++++
 14 files changed, 59 insertions(+), 1 deletions(-)
arch/i386/kernel/setup.c +2 -0
index 79df6e6..9f159d9 100644
@@ -658,6 +658,8 @@ static __init int add_pcspkr(void)
 	int ret;
 
 	pd = platform_device_alloc("pcspkr", -1);
+	/* mark it as not a leak since this device doesn't need to be freed */
+	memleak_not_leak(pd);
 	if (!pd)
 		return -ENOMEM;
 
drivers/base/platform.c +3 -0
index f9c903b..0e03452 100644
@@ -166,6 +166,9 @@ struct platform_device *platform_device_
 	struct platform_object *pa;
 
 	pa = kzalloc(sizeof(struct platform_object) + strlen(name), GFP_KERNEL);
+	/* kmemleak cannot guess the object type because the block
+	 * size is different from the object size */
+	memleak_typeid(pa, struct platform_object);
 	if (pa) {
 		strcpy(pa->name, name);
 		pa->pdev.name = pa->name;
drivers/char/vt.c +4 -0
index 06c32a3..1d74ffe 100644
@@ -2640,6 +2640,10 @@ static int __init con_init(void)
 	 */
 	for (currcons = 0; currcons < MIN_NR_CONSOLES; currcons++) {
 		vc_cons[currcons].d = vc = alloc_bootmem(sizeof(struct vc_data));
+		/* kmemleak does not track the memory allocated via
+		 * alloc_bootmem() but this block contains pointers to
+		 * other blocks allocated via kmalloc */
+		memleak_alloc(vc, sizeof(struct vc_data), 1);
 		visual_init(vc, currcons, 1);
 		vc->vc_screenbuf = (unsigned short *)alloc_bootmem(vc->vc_screenbuf_size);
 		vc->vc_kmalloced = 0;
drivers/hwmon/w83627hf.c +4 -0
index dfdc29c..6f5c70f 100644
@@ -1097,6 +1097,10 @@ static int w83627hf_detect(struct i2c_ad
 		err = -ENOMEM;
 		goto ERROR1;
 	}
+	/* the pointer to member is stored but the code doesn't use
+	 * container_of for access and the alias need to be
+	 * explicitely declared here */
+	memleak_container(struct w83627hf_data, client);
 
 	new_client = &data->client;
 	i2c_set_clientdata(new_client, data);
drivers/scsi/hosts.c +3 -0
index 38c3a29..965dd14 100644
@@ -304,6 +304,9 @@ struct Scsi_Host *scsi_host_alloc(struct
 	shost = kzalloc(sizeof(struct Scsi_Host) + privsize, gfp_mask);
 	if (!shost)
 		return NULL;
+	/* kmemleak cannot guess the object type because the block
+	 * size is different from the object size */
+	memleak_typeid(shost, struct Scsi_Host);
 
 	shost->host_lock = &shost->default_lock;
 	spin_lock_init(shost->host_lock);
drivers/video/console/fbcon.c +3 -0
index 31f476a..1949f2c 100644
@@ -2485,6 +2485,9 @@ static int fbcon_set_font(struct vc_data
 	size = h * pitch * charcount;
 
 	new_data = kmalloc(FONT_EXTRA_WORDS * sizeof(int) + size, GFP_USER);
+	/* the stored pointer is different from the address of the
+	 * allocated block because of padding */
+	memleak_padding(new_data, FONT_EXTRA_WORDS * sizeof(int), size);
 
 	if (!new_data)
 		return -ENOMEM;
fs/ext3/dir.c +3 -0
index 665adee..13d2888 100644
@@ -352,6 +352,9 @@ int ext3_htree_store_dirent(struct file
 	new_fn = kzalloc(len, GFP_KERNEL);
 	if (!new_fn)
 		return -ENOMEM;
+	/* kmemleak cannot guess the object type because the block
+	 * size is different from the object size */
+	memleak_typeid(new_fn, struct fname);
 	new_fn->hash = hash;
 	new_fn->minor_hash = minor_hash;
 	new_fn->inode = le32_to_cpu(dirent->inode);
include/linux/percpu.h +5 -0
index 600e3d3..899776c 100644
@@ -30,7 +30,12 @@ struct percpu_data {
 	void *ptrs[NR_CPUS];
 };
 
+/* pointer disguising messes up the kmemleak objects tracking */
+#ifndef CONFIG_DEBUG_MEMLEAK
 #define __percpu_disguise(pdata) (struct percpu_data *)~(unsigned long)(pdata)
+#else
+#define __percpu_disguise(pdata) (struct percpu_data *)(pdata)
+#endif
 /* 
  * Use this to get to a cpu's version of the per-cpu object dynamically
  * allocated. Non-atomic access to the current CPU's version should
ipc/util.c +6 -0
index a9b7a22..7088618 100644
@@ -492,6 +492,9 @@ void* ipc_rcu_alloc(int size)
 	 */
 	if (rcu_use_vmalloc(size)) {
 		out = vmalloc(HDRLEN_VMALLOC + size);
+		/* the stored pointer is different from the address of
+		 * the allocated block because of padding */
+		memleak_padding(out, HDRLEN_VMALLOC, size);
 		if (out) {
 			out += HDRLEN_VMALLOC;
 			container_of(out, struct ipc_rcu_hdr, data)->is_vmalloc = 1;
@@ -499,6 +502,9 @@ void* ipc_rcu_alloc(int size)
 		}
 	} else {
 		out = kmalloc(HDRLEN_KMALLOC + size, GFP_KERNEL);
+		/* the stored pointer is different from the address of
+		 * the allocated block because of padding */
+		memleak_padding(out, HDRLEN_KMALLOC, size);
 		if (out) {
 			out += HDRLEN_KMALLOC;
 			container_of(out, struct ipc_rcu_hdr, data)->is_vmalloc = 0;
kernel/params.c +7 -1
index f406655..1510d89 100644
@@ -548,6 +548,7 @@ static void __init kernel_param_sysfs_se
 {
 	struct module_kobject *mk;
 	int ret;
+	struct module_param_attrs *mp;
 
 	mk = kzalloc(sizeof(struct module_kobject), GFP_KERNEL);
 	BUG_ON(!mk);
@@ -558,8 +559,13 @@ static void __init kernel_param_sysfs_se
 	ret = kobject_register(&mk->kobj);
 	BUG_ON(ret < 0);
 
+	mp = param_sysfs_setup(mk, kparam, num_params, name_skip);
+	/* this structure is not freed but the pointer is
+	 * lost. However, there are other pointers to its members and
+	 * the object has to be kept */
+	memleak_not_leak(mp);
 	/* no need to keep the kobject if no parameter is exported */
-	if (!param_sysfs_setup(mk, kparam, num_params, name_skip)) {
+	if (!mp) {
 		kobject_unregister(&mk->kobj);
 		kfree(mk);
 	}
net/core/dev.c +6 -0
index e660cb5..96fbe2c 100644
@@ -3191,6 +3191,12 @@ struct net_device *alloc_netdev(int size
 	dev = (struct net_device *)
 		(((long)p + NETDEV_ALIGN_CONST) & ~NETDEV_ALIGN_CONST);
 	dev->padded = (char *)dev - (char *)p;
+	/* kmemleak cannot guess the object type because the block
+	 * size is different from the object size. The stored pointer
+	 * is also different from the address of the allocated block
+	 * because of padding */
+	memleak_padding(p, dev->padded, alloc_size - dev->padded);
+	memleak_typeid(p, struct net_device);
 
 	if (sizeof_priv)
 		dev->priv = netdev_priv(dev);
net/core/skbuff.c +3 -0
index de7801d..14de9cb 100644
@@ -153,6 +153,9 @@ struct sk_buff *__alloc_skb(unsigned int
 
 	/* Get the HEAD */
 	skb = kmem_cache_alloc_node(cache, gfp_mask & ~__GFP_DMA, node);
+	/* the skbuff_fclone_cache contains objects larger than
+	 * "struct sk_buff" and kmemleak cannot guess the type */
+	memleak_typeid(skb, struct sk_buff);
 	if (!skb)
 		goto out;
 
net/ipv4/netfilter/ip_conntrack_core.c +5 -0
index 8556a4f..0bcd3a5 100644
@@ -639,6 +639,11 @@ struct ip_conntrack *ip_conntrack_alloc(
 	}
 
 	conntrack = kmem_cache_alloc(ip_conntrack_cachep, GFP_ATOMIC);
+	/* tuplehash_to_ctrack doesn't pass a constant argument to
+	 * container_of and therefore the conntrack->tuplehash[].list
+	 * aliases are ignored */
+	memleak_container(struct ip_conntrack, tuplehash[IP_CT_DIR_ORIGINAL]);
+	memleak_container(struct ip_conntrack, tuplehash[IP_CT_DIR_REPLY]);
 	if (!conntrack) {
 		DEBUGP("Can't allocate conntrack.\n");
 		atomic_dec(&ip_conntrack_count);
net/sched/sch_generic.c +5 -0
index bc116bd..eef15c4 100644
@@ -434,6 +434,11 @@ struct Qdisc *qdisc_alloc(struct net_dev
 		goto errout;
 	sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 	sch->padded = (char *) sch - (char *) p;
+	/* kmemleak cannot guess the object type because the block
+	 * size is different from the object size. The stored pointer
+	 * is also different from the address of the allocated block
+	 * because of padding */
+	memleak_padding(p, sch->padded, sizeof(struct Qdisc));
 
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
#8 lore raw

PATCH 8/10 Keep the __init functions after initialization

In reply to Catalin Marinas

This patch adds the CONFIG_DEBUG_KEEP_INIT option which preserves the .init.text section after initialization. Memory leaks happening during this phase can be more easily tracked.

---

 include/linux/init.h |    5 +++++
 lib/Kconfig.debug    |   12 ++++++++++++
 2 files changed, 17 insertions(+), 0 deletions(-)
include/linux/init.h +5 -0
index 5a593a1..eecdb17 100644
@@ -40,8 +40,13 @@
 
 /* These are for everybody (although not all archs will actually
    discard it in modules) */
+#ifdef CONFIG_DEBUG_KEEP_INIT
+#define __init
+#define __initdata
+#else
 #define __init		__attribute__ ((__section__ (".init.text")))
 #define __initdata	__attribute__ ((__section__ (".init.data")))
+#endif
 #define __exitdata	__attribute__ ((__section__(".exit.data")))
 #define __exit_call	__attribute_used__ __attribute__ ((__section__ (".exitcall.exit")))
 
lib/Kconfig.debug +12 -0
index 42f60fb..9695af1 100644
@@ -251,6 +251,18 @@ config DEBUG_MEMLEAK_REPORTS_NR
 	  reading the /sys/kernel/debug/memleak file could lead to
 	  some soft-locks.
 
+config DEBUG_KEEP_INIT
+	bool "Do not free the __init code/data"
+	default n
+	depends on DEBUG_MEMLEAK
+	help
+	  This option moves the __init code/data out of the
+	  .init.text/.init.data sections. It is useful for identifying
+	  memory leaks happening during the kernel or modules
+	  initialization.
+
+	  If unsure, say N.
+
 config DEBUG_PREEMPT
 	bool "Debug preemptible kernel"
 	depends on DEBUG_KERNEL && PREEMPT && TRACE_IRQFLAGS_SUPPORT
#9 lore raw

PATCH 9/10 Testing module for kmemleak

In reply to Catalin Marinas

This patch adds a loadable module that deliberately leaks memory. It is used for testing various memory leaking scenarios.

---

 lib/Kconfig.debug |   11 ++++++
 mm/Makefile       |    1 +
 mm/memleak-test.c |   94 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 106 insertions(+), 0 deletions(-)
lib/Kconfig.debug +11 -0
index 9695af1..b430479 100644
@@ -263,6 +263,17 @@ config DEBUG_KEEP_INIT
 
 	  If unsure, say N.
 
+config DEBUG_MEMLEAK_TEST
+	tristate "Test the kernel memory leak detector"
+	default n
+	depends on DEBUG_MEMLEAK
+	help
+	  Say Y or M here to build the test harness for the kernel
+	  memory leak detector. At the moment, this option enables a
+	  module that explicitly leaks memory.
+
+	  If unsure, say N.
+
 config DEBUG_PREEMPT
 	bool "Debug preemptible kernel"
 	depends on DEBUG_KERNEL && PREEMPT && TRACE_IRQFLAGS_SUPPORT
mm/Makefile +1 -0
index aafe03f..9f5d450 100644
@@ -30,3 +30,4 @@ obj-$(CONFIG_FS_XIP) += filemap_xip.o
 obj-$(CONFIG_MIGRATION) += migrate.o
 obj-$(CONFIG_SMP) += allocpercpu.o
 obj-$(CONFIG_DEBUG_MEMLEAK) += memleak.o
+obj-$(CONFIG_DEBUG_MEMLEAK_TEST) += memleak-test.o
mm/memleak-test.c new file +94 -0

94 lines not on this page · raw message

#10 lore raw

PATCH 10/10 Update the MAINTAINERS file for kmemleak

In reply to Catalin Marinas

---

 MAINTAINERS |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)
MAINTAINERS +6 -0
index dea5b2a..fe186b4 100644
@@ -1746,6 +1746,12 @@ L:	[email protected]
 W:	http://www.kerneljanitors.org/
 S:	Maintained
 
+KERNEL MEMORY LEAK DETECTOR
+P:	Catalin Marinas
+M:	[email protected]
+W:	http://www.procode.org/kmemleak/
+S:	Maintained
+
 KERNEL NFSD
 P:	Neil Brown
 M:	[email protected]
#11 lore raw
In reply to Catalin Marinas
Quoted 4 lines · Catalin Marinas

This series of patches represent version 0.13 of the kernel memory leak detector. See the Documentation/kmemleak.txt file for a more detailed description. The patches are downloadable from (the whole patch or the broken-out series) http://www.procode.org/kmemleak/

nice stuff!

FYI, i'm working on integrating kmemleak into -rt. Firstly, i needed the fixes below when applying it ontop of 2.6.19-rt15.

Secondly, i'm wondering about the following recursion:

 [<c045a7e1>] rt_spin_lock_slowlock+0x98/0x1dc
 [<c045b16b>] rt_spin_lock+0x13/0x4b
 [<c018f155>] kfree+0x3a/0xce
 [<c0192e79>] hash_delete+0x58/0x5f
 [<c019309b>] memleak_free+0xe9/0x1e6
 [<c018ed2e>] __cache_free+0x27/0x414
 [<c018f1d0>] kfree+0xb5/0xce
 [<c02788dd>] acpi_ns_get_node+0xb1/0xbb
 [<c02772fa>] acpi_ns_root_initialize+0x30f/0x31d
 [<c0280194>] acpi_initialize_subsystem+0x58/0x87
 [<c06a4641>] acpi_early_init+0x4f/0x12e
 [<c06888bc>] start_kernel+0x41b/0x44b

kfree() within kfree() ... this probably works on the upstream SLAB allocator but makes it pretty nasty to sort out SLAB locking in -rt.

Wouldnt it be better to just preallocate the hash nodes, like lockdep does, to avoid conceptual nesting? Basically debugging infrastructure should rely on other infrastructure as little as possible.

also, the number of knobs in the Kconfig is quite large:

CONFIG_DEBUG_MEMLEAK=y
CONFIG_DEBUG_MEMLEAK_HASH_BITS=16
CONFIG_DEBUG_MEMLEAK_TRACE_LENGTH=4
CONFIG_DEBUG_MEMLEAK_PREINIT_OBJECTS=512
CONFIG_DEBUG_MEMLEAK_SECONDARY_ALIASES=y
CONFIG_DEBUG_MEMLEAK_TASK_STACKS=y

i'd suggest to simplify the Kconfig choices to a binary thing: either have kmemleak or not have it.

plus the Kconfig dependency on SLAB_DEBUG makes it less likely for people to spontaneously try kmemleak. I'd suggest to offer KMEMLEAK unconditionally (when KERNEL_DEBUG is specified) and simply select SLAB_DEBUG.

Ingo

---
 fs/fcntl.c           |    4 ++--
 fs/mbcache.c         |    2 +-
 include/linux/list.h |    9 +++++++++
 include/linux/pid.h  |    7 +++++++
 kernel/pid.c         |    2 +-
 5 files changed, 20 insertions(+), 4 deletions(-)
fs/fcntl.c +2 -2
Index: linux/fs/fcntl.c
===================================================================
@@ -512,7 +512,7 @@ void send_sigio(struct fown_struct *fown
 		goto out_unlock_fown;
 	
 	read_lock(&tasklist_lock);
-	do_each_pid_task(pid, type, p) {
+	__do_each_pid_task(pid, type, p) {
 		send_sigio_to_task(p, fown, fd, band);
 	} while_each_pid_task(pid, type, p);
 	read_unlock(&tasklist_lock);
@@ -543,7 +543,7 @@ int send_sigurg(struct fown_struct *fown
 	ret = 1;
 	
 	read_lock(&tasklist_lock);
-	do_each_pid_task(pid, type, p) {
+	__do_each_pid_task(pid, type, p) {
 		send_sigurg_to_task(p, fown);
 	} while_each_pid_task(pid, type, p);
 	read_unlock(&tasklist_lock);
fs/mbcache.c +1 -1
Index: linux/fs/mbcache.c
===================================================================
@@ -555,7 +555,7 @@ __mb_cache_entry_find(struct list_head *
 {
 	while (l != head) {
 		struct mb_cache_entry *ce =
-			list_entry(l, struct mb_cache_entry,
+			__list_entry(l, struct mb_cache_entry,
 			           e_indexes[index].o_list);
 		if (ce->e_bdev == bdev && ce->e_indexes[index].o_key == key) {
 			DEFINE_WAIT(wait);
include/linux/list.h +9 -0
Index: linux/include/linux/list.h
===================================================================
@@ -367,6 +367,8 @@ static inline void list_splice_init(stru
  */
 #define list_entry(ptr, type, member) \
 	container_of(ptr, type, member)
+#define __list_entry(ptr, type, member) \
+	__container_of(ptr, type, member)
 
 /**
  * list_for_each	-	iterate over a list
@@ -822,6 +824,7 @@ static inline void hlist_add_after_rcu(s
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
+#define __hlist_entry(ptr, type, member) __container_of(ptr,type,member)
 
 #define hlist_for_each(pos, head) \
 	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
@@ -897,6 +900,12 @@ static inline void hlist_add_after_rcu(s
 	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	 \
 		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 	     pos = pos->next)
+#define __hlist_for_each_entry_rcu(tpos, pos, head, member)		 \
+	for (pos = (head)->first;					 \
+	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	 \
+		({ tpos = __hlist_entry(pos, typeof(*tpos), member); 1;}); \
+	     pos = pos->next)
+
 
 #else
 #warning "don't include kernel headers in userspace"
include/linux/pid.h +7 -0
Index: linux/include/linux/pid.h
===================================================================
@@ -125,6 +125,13 @@ static inline pid_t pid_nr(struct pid *p
 			hlist_for_each_entry_rcu((task), pos___,	\
 				&pid->tasks[type], pids[type].node) {
 
+#define __do_each_pid_task(pid, type, task)				\
+	do {								\
+		struct hlist_node *pos___;				\
+		if (pid != NULL)					\
+			__hlist_for_each_entry_rcu((task), pos___,	\
+				&pid->tasks[type], pids[type].node) {
+
 #define while_each_pid_task(pid, type, task)				\
 			}						\
 	} while (0)
kernel/pid.c +1 -1
Index: linux/kernel/pid.c
===================================================================
@@ -289,7 +289,7 @@ struct task_struct * fastcall pid_task(s
 		struct hlist_node *first;
 		first = rcu_dereference(pid->tasks[type].first);
 		if (first)
-			result = hlist_entry(first, struct task_struct, pids[(type)].node);
+			result = __container_of(first, struct task_struct, pids[(type)].node);
 	}
 	return result;
 }
#12 lore raw

Hi Ingo,

Quoted 2 lines · Ingo Molnar

FYI, i'm working on integrating kmemleak into -rt. Firstly, i needed the fixes below when applying it ontop of 2.6.19-rt15.

Do you need these fixes to avoid a compiler error? If yes, this is caused by a bug in gcc-4.x. The kmemleak container_of macro has protection for non-constant offsets passed to container_of but the faulty gcc always returns true for builtin_contant_p, even when this is not the case. Previous versions (3.4) or one of the latest 4.x gcc don't have this bug.

I wouldn't extend kmemleak to work around a gcc bug which was already fixed.

Quoted 15 lines

Secondly, i'm wondering about the following recursion:

 [<c045a7e1>] rt_spin_lock_slowlock+0x98/0x1dc
 [<c045b16b>] rt_spin_lock+0x13/0x4b
 [<c018f155>] kfree+0x3a/0xce
 [<c0192e79>] hash_delete+0x58/0x5f
 [<c019309b>] memleak_free+0xe9/0x1e6
 [<c018ed2e>] __cache_free+0x27/0x414
 [<c018f1d0>] kfree+0xb5/0xce
 [<c02788dd>] acpi_ns_get_node+0xb1/0xbb
 [<c02772fa>] acpi_ns_root_initialize+0x30f/0x31d
 [<c0280194>] acpi_initialize_subsystem+0x58/0x87
 [<c06a4641>] acpi_early_init+0x4f/0x12e
 [<c06888bc>] start_kernel+0x41b/0x44b
Quoted 2 lines

kfree() within kfree() ... this probably works on the upstream SLAB allocator but makes it pretty nasty to sort out SLAB locking in -rt.

I test kmemleak with lockdep enabled but I eliminated all the dependencies on the vanilla kernel. When kfree(hnode) is called (in hash_delete), no kmemleak locks are held and hence no dependency on the kmemleak locks (since kmemleak is protected against re-entrance). My understanding is that slab __cache_free is re-entrant anyway (noticed this when using radix-tree instead of hash in kmemleak and got some lockdep reports on l3->list_lock and memleak_lock) and calling it again from kmemleak doesn't seem to have any problem on the vanilla kernel.

In the -rt kernel, is there any protection against a re-entrant __cache_free (via cache_flusharray -> free_block -> slab_destroy) or this is not needed?

Quoted 3 lines

Wouldnt it be better to just preallocate the hash nodes, like lockdep does, to avoid conceptual nesting? Basically debugging infrastructure should rely on other infrastructure as little as possible.

It would indeed be better to avoid using the slab infrastructure (and not worry about kmemleak re-entrance and lock dependecies). I'll have a look on how this is done in lockdep since the preallocation size isn't known. There are also the memleak_object structures that need to be allocated/freed. To avoid any locking dependencies, I ended up delaying the memleak_object structures freeing in an RCU manner. It might work if I do the same with the hash nodes.

Quoted 1 line

also, the number of knobs in the Kconfig is quite large:

I had some reasons and couldn't find a unified solution, but probably only for one or two if them:

Quoted 2 lines

CONFIG_DEBUG_MEMLEAK=y
CONFIG_DEBUG_MEMLEAK_HASH_BITS=16

For my limited configurations (an x86 laptop and several ARM embedded platforms), 16 bits were enough. I'm not sure this is enough on a server machine for example.

Quoted 1 line

CONFIG_DEBUG_MEMLEAK_TRACE_LENGTH=4

I thought this is a user preference. I could hard-code it to 16. What's the trace length used by lockdep?

Quoted 1 line

CONFIG_DEBUG_MEMLEAK_PREINIT_OBJECTS=512

I can probably hard-code this as well. This is a buffer to temporary store memory allocations before kmemleak is fully initialised. Kmemleak gets initialised quite early in the start_kernel function and shouldn't be that different in other kernel configurations.

Quoted 2 lines

CONFIG_DEBUG_MEMLEAK_SECONDARY_ALIASES=y
CONFIG_DEBUG_MEMLEAK_TASK_STACKS=y

These could be eliminated as well.

There are also:

CONFIG_DEBUG_MEMLEAK_REPORT_THLD - can be removed CONFIG_DEBUG_MEMLEAK_REPORTS_NR - can be removed CONFIG_DEBUG_KEEP_INIT - this might be useful for other tools that store the backtrace and display it at a later time. Could be made more generic.

Quoted 4 lines

plus the Kconfig dependency on SLAB_DEBUG makes it less likely for people to spontaneously try kmemleak. I'd suggest to offer KMEMLEAK unconditionally (when KERNEL_DEBUG is specified) and simply select SLAB_DEBUG.

I just followed the DEBUG_SLAB_LEAK configuration but I don't have any problem with making it more visible.

Thanks for your comments.

Signature · 1 line
Catalin
#13 lore raw
Quoted 13 lines · Catalin Marinas

Hi Ingo,

Quoted 2 lines · Ingo Molnar

FYI, i'm working on integrating kmemleak into -rt. Firstly, i needed the fixes below when applying it ontop of 2.6.19-rt15.

Do you need these fixes to avoid a compiler error? If yes, this is caused by a bug in gcc-4.x. The kmemleak container_of macro has protection for non-constant offsets passed to container_of but the faulty gcc always returns true for builtin_contant_p, even when this is not the case. Previous versions (3.4) or one of the latest 4.x gcc don't have this bug.

Quoted 2 lines

I wouldn't extend kmemleak to work around a gcc bug which was already fixed.

correct, i needed it for gcc 4.0.2. If you want this feature upstream, this has to be solved - no way are we going to phase out portions of gcc4. It's not hard as you can see it from my patch, non-static container_of is very rare. We do alot of other hackery to keep older compilers alive, and we only drop compiler support if some important feature really, really needs new gcc and a sane workaround is not possible.

Quoted 28 lines
Quoted 15 lines

Secondly, i'm wondering about the following recursion:

[<c045a7e1>] rt_spin_lock_slowlock+0x98/0x1dc
[<c045b16b>] rt_spin_lock+0x13/0x4b
[<c018f155>] kfree+0x3a/0xce
[<c0192e79>] hash_delete+0x58/0x5f
[<c019309b>] memleak_free+0xe9/0x1e6
[<c018ed2e>] __cache_free+0x27/0x414
[<c018f1d0>] kfree+0xb5/0xce
[<c02788dd>] acpi_ns_get_node+0xb1/0xbb
[<c02772fa>] acpi_ns_root_initialize+0x30f/0x31d
[<c0280194>] acpi_initialize_subsystem+0x58/0x87
[<c06a4641>] acpi_early_init+0x4f/0x12e
[<c06888bc>] start_kernel+0x41b/0x44b
Quoted 2 lines

kfree() within kfree() ... this probably works on the upstream SLAB allocator but makes it pretty nasty to sort out SLAB locking in -rt.

I test kmemleak with lockdep enabled but I eliminated all the dependencies on the vanilla kernel. When kfree(hnode) is called (in hash_delete), no kmemleak locks are held and hence no dependency on the kmemleak locks (since kmemleak is protected against re-entrance). My understanding is that slab __cache_free is re-entrant anyway (noticed this when using radix-tree instead of hash in kmemleak and got some lockdep reports on l3->list_lock and memleak_lock) and calling it again from kmemleak doesn't seem to have any problem on the vanilla kernel.

Quoted 3 lines

In the -rt kernel, is there any protection against a re-entrant __cache_free (via cache_flusharray -> free_block -> slab_destroy) or this is not needed?

the problem on -rt is the per-CPU slab buffer handling. In vanilla they are handled with irqs off/on - but inside is an unbound algorithm so for -rt i converted the local_irq_disable() logic to per-CPU locks. So this is an -rt only problem.

hm, even on vanilla you might run into problems in slab_destroy(), there we hold the l3 lock.

Quoted 8 lines
Quoted 3 lines

Wouldnt it be better to just preallocate the hash nodes, like lockdep does, to avoid conceptual nesting? Basically debugging infrastructure should rely on other infrastructure as little as possible.

It would indeed be better to avoid using the slab infrastructure (and not worry about kmemleak re-entrance and lock dependecies). I'll have a look on how this is done in lockdep since the preallocation size isn't known. [...]

lockdep just uses a large compile-time array to allocate from and never grows that array.

Quoted 4 lines

There are also the memleak_object structures that need to be allocated/freed. To avoid any locking dependencies, I ended up delaying the memleak_object structures freeing in an RCU manner. It might work if I do the same with the hash nodes.

yeah, delayed RCU freeing might work better.

Quoted 3 lines
Quoted 1 line

also, the number of knobs in the Kconfig is quite large:

I had some reasons and couldn't find a unified solution, [...]

i'm just saying that for upstream you have to make up your mind about them and have to provide a simplified configuration API. Sometimes it's hard, but it has to be done. Experience is that both users and distributors /will/ misconfigure it.

Quoted 8 lines

[...] but probably only for one or two if them:

Quoted 2 lines

CONFIG_DEBUG_MEMLEAK=y
CONFIG_DEBUG_MEMLEAK_HASH_BITS=16

For my limited configurations (an x86 laptop and several ARM embedded platforms), 16 bits were enough. I'm not sure this is enough on a server machine for example.

we try to never expose something like this via the config infrastructure. One solution here would be to use CONFIG_BASE_SMALL, that's the standard way of expressing that the kernel is for a small machine.

Quoted 4 lines
Quoted 1 line

CONFIG_DEBUG_MEMLEAK_TRACE_LENGTH=4

I thought this is a user preference. I could hard-code it to 16. What's the trace length used by lockdep?

lockdep saves all of them because stack traces are very useful in their entirety. But lockdep really allocates everything internally and puts out a warning and turns itself off if that pool is depleted. Also, the amount of memory needed for lockdep is bound by the number of unique lock acquire sites in the kernel, while kmemleak might need /alot/ of memory if there's lots of small allocations around - so the comparison to lockdep in this area is not valid.

Ingo

#14 lore raw

the other thing that is pretty ugly is the recursive_enter/clear/exit code. I'd suggest the lockdep model here: use a single flag in task_struct to detect recursion. Also, never use BUG() when hitting a bug in a debugging helper - that will crash the box. Use a flag to turn off the whole thing if you encounter an internal bug and print a warning. That way bugs can actually be reported, instead of users wondering why the box locked up under X.

Ingo

#15 lore raw

one more thing: after bootup i need to access the /debug/memleak file twice to get any output from it - is that normal? The first 'cat /debug/memleak' gives no output (but there's the usual scanning delay, so memleak does do its work).

Ingo

#16 lore raw

it would also be nice to have more information than this:

unreferenced object 0xf76f5af8 (size 512):
[<c0191f23>] memleak_alloc
[<c018eeaa>] kmem_cache_zalloc
[<c03277a7>] probe_hwif
[<c032870c>] probe_hwif_init_with_fixup
[<c032aea1>] ide_setup_pci_device
[<c0312564>] amd74xx_probe
[<c069c4b4>] ide_scan_pcidev
[<c069c505>] ide_scan_pcibus
[<c069bdca>] ide_init
[<c0100532>] init
[<c0105da3>] kernel_thread_helper
[<ffffffff>]

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

plus it would be nice to have a kernel thread (running at nice 19) that scans everything every 10 minutes or so, which would output some overview 'delta' information into the syslog, along the lines of:

kmemleak: 2 new object leaks detected, see /debug/memleak for details

that way users could see (and report) new leaks in the dmesg, without having to do anything. I'd like to enable kmemleak in the -rt yum kernels, so it all has to be as automatic and as informative as possible.

Ingo

#17 lore raw

plus a boot-time and a runtime switch to turn kmemleak off would be nice as well. (turning it back on is probably not needed and is harder as well)

Ingo

#18 lore raw
In reply to Ingo Molnar
Quoted 16 lines · Ingo Molnar

it would also be nice to have more information than this:

unreferenced object 0xf76f5af8 (size 512):
[<c0191f23>] memleak_alloc
[<c018eeaa>] kmem_cache_zalloc
[<c03277a7>] probe_hwif
[<c032870c>] probe_hwif_init_with_fixup
[<c032aea1>] ide_setup_pci_device
[<c0312564>] amd74xx_probe
[<c069c4b4>] ide_scan_pcidev
[<c069c505>] ide_scan_pcibus
[<c069bdca>] ide_init
[<c0100532>] init
[<c0105da3>] kernel_thread_helper
[<ffffffff>]

BTW, I think there is a call to kzalloc in probe_hwif and it is optimised to do a kmem_cache_zalloc in include/linux/slab_def.h. The latest kmemleak-0.13 ifdef's out this optimisation because the size information gets lost otherwise. The slab.h file was already patched for this in 2.6.19 but its content was moved to slab_def.h in 2.6.20-rc1.

Quoted 4 lines

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

I'll add them. Thanks.

Signature · 1 line
Catalin
#19 lore raw
In reply to Ingo Molnar
Quoted 4 lines · Ingo Molnar

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

Trying to copy the comm with get_task_comm, I get the lockdep report below, caused by acquiring the task's alloc_lock. Any idea how to go around this?

=================================
[ INFO: inconsistent lock state ]
2.6.20-rc2 #211
---------------------------------
inconsistent {hardirq-on-W} -> {in-hardirq-W} usage. swapper/0 [HC1[1]:SC0[0]:HE0:SE1] takes:
(init_task.alloc_lock){+-..}, at: [<c007d950>] get_task_comm+0x24/0x40 {hardirq-on-W} state was registered at:

 [<c00493d0>] lock_acquire+0x80/0x94
 [<c020cf1c>] _spin_lock+0x30/0x40
 [<c0027c80>] copy_process+0x8b8/0x1208
 [<c0028874>] do_fork+0xc0/0x1e0
 [<c001497c>] kernel_thread+0x70/0x80
 [<c000f864>] rest_init+0x1c/0x30
 [<c000fa9c>] start_kernel+0x224/0x27c
 [<00008078>] 0x8078
irq event stamp: 33758
hardirqs last  enabled at (33757): [<c0014ef8>] default_idle+0x44/0x50
hardirqs last disabled at (33758): [<c00131d4>] __irq_svc+0x34/0xc0
softirqs last  enabled at (33750): [<c002f97c>] __do_softirq+0x10c/0x124
softirqs last disabled at (33745): [<c002fde0>] irq_exit+0x58/0x60

other info that might help us debug this:
1 lock held by swapper/0:
#0: (&lp->lock){+...}, at: [<c0146b9c>] smc_interrupt+0x28/0x784

stack backtrace:
[<c0018cf4>] (dump_stack+0x0/0x14) from [<c00471b4>]
(print_usage_bug+0x11c/0x154)
[<c0047098>] (print_usage_bug+0x0/0x154) from [<c0047b60>]
(mark_lock+0xe0/0x4c8)

r8 = 00000001 r7 = C02A4348 r6 = 00000000 r5 = 00000002
r4 = C02A4638
[<c0047a80>] (mark_lock+0x0/0x4c8) from [<c0048b34>] (__lock_acquire+0x424/0xc40)
[<c0048710>] (__lock_acquire+0x0/0xc40) from [<c00493d0>] (lock_acquire+0x80/0x94)
[<c0049350>] (lock_acquire+0x0/0x94) from [<c020cf1c>] (_spin_lock+0x30/0x40) [<c020ceec>] (_spin_lock+0x0/0x40) from [<c007d950>] (get_task_comm+0x24/0x40) r4 = C02A4348
[<c007d92c>] (get_task_comm+0x0/0x40) from [<c0075570>] (memleak_alloc+0x168/0x2b4)
r6 = C7596E60 r5 = A0000193 r4 = C7596E64
[<c0075408>] (memleak_alloc+0x0/0x2b4) from [<c0072800>] (kmem_cache_alloc+0x110/0x124)
[<c00726f0>] (kmem_cache_alloc+0x0/0x124) from [<c0199228>] (__alloc_skb+0x34/0x130)
[<c01991f4>] (__alloc_skb+0x0/0x130) from [<c0146f04>] (smc_interrupt+0x390/0x784)
[<c0146b74>] (smc_interrupt+0x0/0x784) from [<c005322c>] (handle_IRQ_event+0x2c/0x68)
[<c0053200>] (handle_IRQ_event+0x0/0x68) from [<c0054d94>] (handle_level_irq+0xe4/0x150)
r7 = C02A1128 r6 = C7805C20 r5 = 00000029 r4 = C02A1100 [<c0054cb0>] (handle_level_irq+0x0/0x150) from [<c001469c>] (asm_do_IRQ+0x70/0x9c)
r7 = 00008000 r6 = 00000029 r5 = 00000000 r4 = C029E000 [<c001462c>] (asm_do_IRQ+0x0/0x9c) from [<c00131d4>] (__irq_svc+0x34/0xc0) r5 = FF000100 r4 = FFFFFFFF
[<c0014eb4>] (default_idle+0x0/0x50) from [<c0014cb0>] (cpu_idle+0x30/0x4c) [<c0014c80>] (cpu_idle+0x0/0x4c) from [<c000f870>] (rest_init+0x28/0x30) r5 = C02C3D30 r4 = C04DB2A4
[<c000f848>] (rest_init+0x0/0x30) from [<c000fa9c>] (start_kernel+0x224/0x27c) [<c000f878>] (start_kernel+0x0/0x27c) from [<00008078>] (0x8078)

Signature · 1 line
Catalin
#20 lore raw
Quoted 9 lines · Catalin Marinas
Quoted 4 lines · Ingo Molnar

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

Trying to copy the comm with get_task_comm, I get the lockdep report below, caused by acquiring the task's alloc_lock. Any idea how to go around this?

well you take the lock from irq context, which means it needs to use _irqsave/restore everywhere. (and all locks taken inside it must be irq safe as well)

maybe.. not use comm in irq context? it doesn't actually mean anything there anyway...

Signature · 2 lines
if you want to mail me at work (you don't), use arjan (at) linux.intel.com
Test the interaction between Linux and your BIOS via http://www.linuxfirmwarekit.org
#21 lore raw
Quoted 11 lines · Arjan van de Ven
Quoted 9 lines · Catalin Marinas
Quoted 4 lines · Ingo Molnar

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

Trying to copy the comm with get_task_comm, I get the lockdep report below, caused by acquiring the task's alloc_lock. Any idea how to go around this?

Quoted 6 lines

well you take the lock from irq context, which means it needs to use _irqsave/restore everywhere. (and all locks taken inside it must be irq safe as well)

maybe.. not use comm in irq context? it doesn't actually mean anything there anyway...

Thanks. Done this and it is ok now.

Signature · 1 line
Catalin
#22 lore raw
In reply to Catalin Marinas
Quoted 9 lines · Catalin Marinas
Quoted 4 lines · Ingo Molnar

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

Trying to copy the comm with get_task_comm, I get the lockdep report below, caused by acquiring the task's alloc_lock. Any idea how to go around this?

just memcpy p->comm without any locking. It's for the current task, right? That does not need any locking.

Ingo

#23 lore raw
Quoted 6 lines · Ingo Molnar
Quoted 3 lines

Trying to copy the comm with get_task_comm, I get the lockdep report below, caused by acquiring the task's alloc_lock. Any idea how to go around this?

just memcpy p->comm without any locking. It's for the current task, right? That does not need any locking.

furthermore, i'd put "hardirq" into the comm copy if in_hardirq() is true, and i'd put "softirq" into the comm copy if !in_hardirq && in_softirq(). That way the allocation is not attributed to a process that has no real connection to it.

Ingo

#24 lore raw
In reply to Ingo Molnar
Quoted 9 lines · Ingo Molnar
Quoted 6 lines · Catalin Marinas
Quoted 4 lines · Ingo Molnar

it would be nice to record 1) the jiffies value at the time of allocation, 2) the PID and the comm of the task that did the allocation. The jiffies timestamp would be useful to see the age of the allocation, and the PID/comm is useful for context.

Quoted 6 lines
Quoted 3 lines

Trying to copy the comm with get_task_comm, I get the lockdep report below, caused by acquiring the task's alloc_lock. Any idea how to go around this?

just memcpy p->comm without any locking. It's for the current task, right? That does not need any locking.

Yes, it is for the current task. I also added an in_interrupt() test since the current->comm is not relevant in this case as Arjan pointed out.

Signature · 1 line
Catalin
#25 lore raw
In reply to Ingo Molnar
Quoted 4 lines · Ingo Molnar

one more thing: after bootup i need to access the /debug/memleak file twice to get any output from it - is that normal? The first 'cat /debug/memleak' gives no output (but there's the usual scanning delay, so memleak does do its work).

Yes, this is normal. Especially on SMP, I get some transient reports, probably caused by pointers hold in registers (even more visible on ARM due to the bigger number of registers per CPU). Reporting a leak only if it was seen at least once before greatly reduces the false positives (this is configurable as well but I'll drop the configuration option). Without this, you could see that, at every scan, the reported pointers are different.

Some people testing kmemleak used to read the /debug/memleak file periodically from a script and this wasn't noticeable. It would be even better if, as you suggested, I schedule a periodic memory scanning.

Signature · 1 line
Catalin
#26 lore raw
Quoted 14 lines · Catalin Marinas
Quoted 4 lines · Ingo Molnar

one more thing: after bootup i need to access the /debug/memleak file twice to get any output from it - is that normal? The first 'cat /debug/memleak' gives no output (but there's the usual scanning delay, so memleak does do its work).

Yes, this is normal. Especially on SMP, I get some transient reports, probably caused by pointers hold in registers (even more visible on ARM due to the bigger number of registers per CPU). Reporting a leak only if it was seen at least once before greatly reduces the false positives (this is configurable as well but I'll drop the configuration option). Without this, you could see that, at every scan, the reported pointers are different.

Quoted 4 lines

Some people testing kmemleak used to read the /debug/memleak file periodically from a script and this wasn't noticeable. It would be even better if, as you suggested, I schedule a periodic memory scanning.

yeah. You could also use the allocation timestamp to exclude too young entries. (if something really leaked then it will be a leak in 10 minutes too)

Ingo

#27 lore raw
In reply to Ingo Molnar
Quoted 18 lines · Ingo Molnar
Quoted 13 lines · Catalin Marinas

Hi Ingo,

Quoted 2 lines · Ingo Molnar

FYI, i'm working on integrating kmemleak into -rt. Firstly, i needed the fixes below when applying it ontop of 2.6.19-rt15.

Do you need these fixes to avoid a compiler error? If yes, this is caused by a bug in gcc-4.x. The kmemleak container_of macro has protection for non-constant offsets passed to container_of but the faulty gcc always returns true for builtin_contant_p, even when this is not the case. Previous versions (3.4) or one of the latest 4.x gcc don't have this bug.

Quoted 2 lines

I wouldn't extend kmemleak to work around a gcc bug which was already fixed.

Quoted 7 lines

correct, i needed it for gcc 4.0.2. If you want this feature upstream, this has to be solved - no way are we going to phase out portions of gcc4. It's not hard as you can see it from my patch, non-static container_of is very rare. We do alot of other hackery to keep older compilers alive, and we only drop compiler support if some important feature really, really needs new gcc and a sane workaround is not possible.

If that's because of things like the dinky testcase below,

   int main (int argc, char *argv[])
   {
     static int a[] = { __builtin_constant_p (argc) ? 1 : 0 };
     return a[0];
   }

AFAIK, no SuSE compiler can handle it. I just build/tested their latest version,

gcc version 4.1.2 20061129 (prerelease) (SUSE Linux)

and it still can't deal with that without gcc41-rh198849.patch being applied.

-Mike

#28 lore raw
In reply to Ingo Molnar
Quoted 8 lines · Ingo Molnar
Quoted 6 lines · Catalin Marinas

Do you need these fixes to avoid a compiler error? If yes, this is caused by a bug in gcc-4.x. The kmemleak container_of macro has protection for non-constant offsets passed to container_of but the faulty gcc always returns true for builtin_contant_p, even when this is not the case. Previous versions (3.4) or one of the latest 4.x gcc don't have this bug.

Quoted 7 lines

correct, i needed it for gcc 4.0.2. If you want this feature upstream, this has to be solved - no way are we going to phase out portions of gcc4. It's not hard as you can see it from my patch, non-static container_of is very rare. We do alot of other hackery to keep older compilers alive, and we only drop compiler support if some important feature really, really needs new gcc and a sane workaround is not possible.

There might be a simpler solution (haven't tried it), just before your compilation error line:

#undef container_of
#define container_of(...) __container_of(...)

I could add some meaningful macros that eliminate the use of the non-constant offset to make this more obvious.

Quoted 11 lines
Quoted 3 lines

In the -rt kernel, is there any protection against a re-entrant __cache_free (via cache_flusharray -> free_block -> slab_destroy) or this is not needed?

the problem on -rt is the per-CPU slab buffer handling. In vanilla they are handled with irqs off/on - but inside is an unbound algorithm so for -rt i converted the local_irq_disable() logic to per-CPU locks. So this is an -rt only problem.

hm, even on vanilla you might run into problems in slab_destroy(), there we hold the l3 lock.

It seems that slab_destroy doesn't take the l3 lock again if it is already held, otherwise it would fail without kmemleak. However, I can't guarantee that even a minor change wouldn't break kmemleak.

Quoted 6 lines
Quoted 4 lines

There are also the memleak_object structures that need to be allocated/freed. To avoid any locking dependencies, I ended up delaying the memleak_object structures freeing in an RCU manner. It might work if I do the same with the hash nodes.

yeah, delayed RCU freeing might work better.

I could also use a simple allocator based on alloc_pages since kmemleak doesn't track pages. It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

This would simplify the recursiveness and also work on any other slab allocator (looking back at the amount of time I spend to sort out the recursiveness and locking dependencies, I could've implemented a full allocator).

I'll try to implement your other suggestions as well. Thanks.

Signature · 1 line
Catalin
#29 lore raw
Quoted 6 lines · Catalin Marinas
Quoted 2 lines

hm, even on vanilla you might run into problems in slab_destroy(), there we hold the l3 lock.

It seems that slab_destroy doesn't take the l3 lock again if it is already held, otherwise it would fail without kmemleak. However, I can't guarantee that even a minor change wouldn't break kmemleak.

slab_destroy() is careful to not take the /same/ lock. But kmemleak does an unconditional kfree() and i dont see what saves us from a rare but possible deadlock here.

Quoted 4 lines
Quoted 1 line

yeah, delayed RCU freeing might work better.

I could also use a simple allocator based on alloc_pages since kmemleak doesn't track pages. [...]

actually, i'm quite sure we want to track pages later on too, any reason why kmemleak shouldnt cover them?

But i agree that using a separate allocator would be the right choice here. Once the page allocator will be added to the tracking mechanism we can exclude those allocations by doing wrappers. I.e. you shouldnt just add the memleak_*() functions to the page allocator directly - wrap the existing calls cleanly, and thus preserve a non-tracked API variant. For the SLAB this is hard because the SLAB has so many internal dependencies
- but the buddy is a 'core' allocator.

and those non-wrapped APIs would also be useful for the SLAB to call into - that way we could exclude the tracking of SLAB allocations. (unless someone wants to track/debug the SLAB implementation itself.)

Quoted 3 lines

[...] It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

sounds good to me. Please make it a per-CPU pool. We'll have to fix the locking too, to be per-CPU - memleak_lock is quite a scalability problem right now. (Add a memleak_object->cpu pointer so that freeing can be done on any other CPU as well.)

Quoted 4 lines

This would simplify the recursiveness and also work on any other slab allocator (looking back at the amount of time I spend to sort out the recursiveness and locking dependencies, I could've implemented a full allocator).

yes.

Ingo

#30 lore raw
Quoted 7 lines · Ingo Molnar
Quoted 2 lines · Catalin Marinas

I could also use a simple allocator based on alloc_pages since kmemleak doesn't track pages. [...]

actually, i'm quite sure we want to track pages later on too, any reason why kmemleak shouldnt cover them?

It could track them but I'm not sure how efficient it would be since you have different ways to get the page addresses like pfn, struct page. The pfn would actually introduce a lot of false negatives.

This needs some investigation and it can probably be done but I'll first focus on the slab allocator.

Quoted 5 lines
Quoted 3 lines

[...] It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

sounds good to me. Please make it a per-CPU pool.

Isn't there a risk for the pools to become imbalanced? A lot of allocations would initially happen on the first CPU.

Quoted 2 lines

[...] (Add a memleak_object->cpu pointer so that freeing can be done on any other CPU as well.)

We could add the freed objects to the CPU pool where they were freed and not use a memleak_object->cpu pointer.

Quoted 3 lines

We'll have to fix the
locking too, to be per-CPU - memleak_lock is quite a scalability problem right now.

The memleak_lock is indeed too coarse (but it was easier to track the locking dependencies). With a new allocator, however, I could do a finer grain locking. It probably still needs a (rw)lock for the hash table. Having per-CPU hash tables is inefficient as we would have to look up all the tables at every freeing or scanning for the corresponding memleak_object.

There is a global object_list as well covered by memleak_lock (only for insertions/deletions as traversing is RCU). Since modifications to this list happen at the same time with the hash table modifications, the memleak_lock is held anyway so we probably don't need to do per-CPU object lists (they would also need some locking if freeing would happen on a different CPU). List insertion/deletion is very small compared to the hash-table look-up and it wouldn't introduce a scalability problem.

Signature · 1 line
Catalin
#31 lore raw
Quoted 8 lines · Catalin Marinas
Quoted 5 lines
Quoted 3 lines

[...] It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

sounds good to me. Please make it a per-CPU pool.

Isn't there a risk for the pools to become imbalanced? A lot of allocations would initially happen on the first CPU.

hm, what's the problem with imbalance? These are trees and imbalance isnt a big issue.

Quoted 5 lines
Quoted 2 lines

[...] (Add a memleak_object->cpu pointer so that freeing can be done on any other CPU as well.)

We could add the freed objects to the CPU pool where they were freed and not use a memleak_object->cpu pointer.

i mean totally per-CPU locking and per-CPU radix trees, etc.

Quoted 9 lines
Quoted 2 lines

We'll have to fix the locking too, to be per-CPU - memleak_lock is quite a scalability problem right now.

The memleak_lock is indeed too coarse (but it was easier to track the locking dependencies). With a new allocator, however, I could do a finer grain locking. It probably still needs a (rw)lock for the hash table. Having per-CPU hash tables is inefficient as we would have to look up all the tables at every freeing or scanning for the corresponding memleak_object.

at freeing we only have to look up the tree belonging to object->cpu. Scanning overhead does not matter in comparison to runtime tracking overhead. (but i doubt it would be much different - scanning overhead scales with size of tree)

Quoted 2 lines

There is a global object_list as well covered by memleak_lock (only for insertions/deletions as traversing is RCU). [...]

yeah, that would have to become per-CPU too.

Quoted 2 lines

[...] List insertion/deletion is very small compared to the hash-table look-up and it wouldn't introduce a scalability problem.

it's a common misconception to think that 'small' critical sections are fine. That's not the issue. The pure fact of having globally modified resource is the problem, the lock cacheline would ping-pong, etc.

Ingo

#32 lore raw
Quoted 7 lines · Ingo Molnar
Quoted 4 lines · Catalin Marinas
Quoted 4 lines
Quoted 3 lines

[...] It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

sounds good to me. Please make it a per-CPU pool.

Isn't there a risk for the pools to become imbalanced? A lot of allocations would initially happen on the first CPU.

hm, what's the problem with imbalance? These are trees and imbalance isnt a big issue.

It could just be more available (freed) memleak_objects on one CPU than on the others and use more memory. Not a big problem though.

Quoted 11 lines
Quoted 9 lines
Quoted 2 lines

We'll have to fix the locking too, to be per-CPU - memleak_lock is quite a scalability problem right now.

The memleak_lock is indeed too coarse (but it was easier to track the locking dependencies). With a new allocator, however, I could do a finer grain locking. It probably still needs a (rw)lock for the hash table. Having per-CPU hash tables is inefficient as we would have to look up all the tables at every freeing or scanning for the corresponding memleak_object.

at freeing we only have to look up the tree belonging to object->cpu.

At freeing, kmemleak only gets a pointer value which has to be looked up in the hash table for the corresponding memleak_object. Only after that, we can know memleak_object->cpu. That's why I think we only need to have a global hash table. The hash table look-up can be RCU.

It would work with per-CPU hash tables but we still need to look-up the other hash tables in case the freeing happened on a different CPU (i.e. look-up the current hash table and, if it fails, look-up the other per-CPU hashes). Freeing would need to remove the entry from the hash table and acquire a lock but this would be per-CPU. I'm not sure how often you get this scenario (allocation and freeing on different CPUs) but it might introduce an overhead to the memory freeing.

Do you have a better solution here?

Quoted 4 lines
Quoted 2 lines

There is a global object_list as well covered by memleak_lock (only for insertions/deletions as traversing is RCU). [...]

yeah, that would have to become per-CPU too.

That's not that difficult but, as above, we need the hash table look-up before we find which list it is on.

Quoted 6 lines
Quoted 2 lines

[...] List insertion/deletion is very small compared to the hash-table look-up and it wouldn't introduce a scalability problem.

it's a common misconception to think that 'small' critical sections are fine. That's not the issue. The pure fact of having globally modified resource is the problem, the lock cacheline would ping-pong, etc.

You are right but I didn't mean that small critical sections are better, just that in case we need a critical section for the global hash table look-up, extending this critical region with list addition/deletion wouldn't make things any worse (than they are, regarding scalability).

Signature · 1 line
Catalin
#33 lore raw
Quoted 15 lines · Catalin Marinas
Quoted 1 line

at freeing we only have to look up the tree belonging to object->cpu.

At freeing, kmemleak only gets a pointer value which has to be looked up in the hash table for the corresponding memleak_object. Only after that, we can know memleak_object->cpu. That's why I think we only need to have a global hash table. The hash table look-up can be RCU.

It would work with per-CPU hash tables but we still need to look-up the other hash tables in case the freeing happened on a different CPU (i.e. look-up the current hash table and, if it fails, look-up the other per-CPU hashes). Freeing would need to remove the entry from the hash table and acquire a lock but this would be per-CPU. I'm not sure how often you get this scenario (allocation and freeing on different CPUs) but it might introduce an overhead to the memory freeing.

Quoted 1 line

Do you have a better solution here?

hmm ... nasty. Would it be feasible to embedd the memleak info into the allocated object itself? That would remove quite some runtime overhead, besides eliminating the global hash.

Ingo

#34 lore raw
Quoted 11 lines · Ingo Molnar
Quoted 7 lines · Catalin Marinas
Quoted 1 line

at freeing we only have to look up the tree belonging to object->cpu.

At freeing, kmemleak only gets a pointer value which has to be looked up in the hash table for the corresponding memleak_object. Only after that, we can know memleak_object->cpu. That's why I think we only need to have a global hash table. The hash table look-up can be RCU. [...]

Quoted 3 lines

hmm ... nasty. Would it be feasible to embedd the memleak info into the allocated object itself? That would remove quite some runtime overhead, besides eliminating the global hash.

I thought about this but would be more difficult for page allocations and even impossible if we later want to track ioremap'ed regions (or any other resource that has a unique id). The vmalloc'ed regions are page aligned, though not sure there is any code that makes use of this assumption. It also makes it too dependent on the allocator itself (maybe not a big problem). Being less intrusive makes this easier to maintain, especially if you want to use a different allocator.

Another option would be to store kmemleak info in the slab management structures, vm_area (for vmalloc) or page structures but this breaks the kmemleak functions for marking the false positives (which is done outside the allocator).

Is there any scalability/performance impact of just acquiring/releasing a lock or this is only affected by the contention situations? If it's the latter, there can be a lock per hash-table entry and drastically reduce the contention. The drawback is the doubling of the hash table size, maybe with some impact on caches and TLBs.

Signature · 1 line
Catalin
#35 lore raw
In reply to Ingo Molnar
Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Catalin Marinas

I could also use a simple allocator based on alloc_pages [...] [...] It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

sounds good to me. Please make it a per-CPU pool. We'll have to fix the locking too, to be per-CPU - memleak_lock is quite a scalability problem right now. (Add a memleak_object->cpu pointer so that freeing can be done on any other CPU as well.)

I did some simple statistics about allocations happening on one CPU and freeing on a different one. On a 4-CPU ARM system (and without IRQ balancing and without CONFIG_PREEMPT), these seem to happen in about 8-10% of the cases. Do you expect higher figures on other systems/configurations?

As I mentioned in a different e-mail, a way to remove the global hash table is to create per-cpu hashes. The only problem is that in these 8-10% of the cases, freeing would need to look up the other hashes. This would become a problem with a high number of CPUs but I'm not sure whether it would overtake the performance issues introduced by cacheline ping-ponging in the single-hash case.

Any thoughts?

Thanks.

Signature · 1 line
Catalin
#36 lore raw
Quoted 18 lines · Catalin Marinas
Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Catalin Marinas

I could also use a simple allocator based on alloc_pages [...] [...] It could be so simple that it would never need to free any pages, just grow the size as required and reuse the freed memleak objects from a list.

sounds good to me. Please make it a per-CPU pool. We'll have to fix the locking too, to be per-CPU - memleak_lock is quite a scalability problem right now. (Add a memleak_object->cpu pointer so that freeing can be done on any other CPU as well.)

I did some simple statistics about allocations happening on one CPU and freeing on a different one. On a 4-CPU ARM system (and without IRQ balancing and without CONFIG_PREEMPT), these seem to happen in about 8-10% of the cases. Do you expect higher figures on other systems/configurations?

Quoted 6 lines

As I mentioned in a different e-mail, a way to remove the global hash table is to create per-cpu hashes. The only problem is that in these 8-10% of the cases, freeing would need to look up the other hashes. This would become a problem with a high number of CPUs but I'm not sure whether it would overtake the performance issues introduced by cacheline ping-ponging in the single-hash case.

i dont think it's worth doing that. So we should either do the current global lock & hash (bad for scalability), or a pure per-CPU design. The pure per-CPU design would have to embedd the CPU ID the object is attached to into the allocated object. If that is not feasible then only the global hash remains i think.

Ingo

#37 lore raw
Quoted 7 lines · Ingo Molnar
Quoted 6 lines

As I mentioned in a different e-mail, a way to remove the global hash table is to create per-cpu hashes. The only problem is that in these 8-10% of the cases, freeing would need to look up the other hashes. This would become a problem with a high number of CPUs but I'm not sure whether it would overtake the performance issues introduced by cacheline ping-ponging in the single-hash case.

Quoted 5 lines

i dont think it's worth doing that. So we should either do the current global lock & hash (bad for scalability), or a pure per-CPU design. The pure per-CPU design would have to embedd the CPU ID the object is attached to into the allocated object. If that is not feasible then only the global hash remains i think.

embedding the info shouldnt be /that/ hard in case of the SLAB: if the memleak info is at a negative offset from the allocated pointer. I.e. that if kmalloc() returns 'ptr', the memleak info could be at ptr-sizeof(memleak_info). That way you dont have to know the size of the object beforehand and there's absolutely no need for a global hash of any sort.

(it gets a bit more complex for page aligned allocations for the buddy and for vmalloc - but that could be solved by adding one extra pointer into struct page. That is a far more preferable cost than the locking/cache overhead of a global hash.)

Ingo

#38 lore raw
Quoted 11 lines · Ingo Molnar
Quoted 3 lines · Ingo Molnar

The pure per-CPU design would have to embedd the CPU ID the object is attached to into the allocated object. If that is not feasible then only the global hash remains i think.

embedding the info shouldnt be /that/ hard in case of the SLAB: if the memleak info is at a negative offset from the allocated pointer. I.e. that if kmalloc() returns 'ptr', the memleak info could be at ptr-sizeof(memleak_info). That way you dont have to know the size of the object beforehand and there's absolutely no need for a global hash of any sort.

It would probably need to be just a pointer embedded in the allocated block. With the current design, the memleak objects have a lifetime longer than the tracked block. This is mainly to avoid long locking during memory scanning and reporting.

Quoted 3 lines

(it gets a bit more complex for page aligned allocations for the buddy and for vmalloc - but that could be solved by adding one extra pointer into struct page. [...]

This still leaves the issue of marking objects as not being leaks or being of a different type. This is done by calling memleak_* functions at the allocation point (outside allocator) where only the pointer is known. In the vmalloc case, it would need to call find_vm_area. This might not be a big problem, only that memory resources are no longer treated in a unified way by kmemleak (and might not be trivial to add support for new allocators).

Quoted 2 lines

[...] That is a far more preferable cost than the
locking/cache overhead of a global hash.)

A global hash would need to be re-built for every scan (and destroyed afterwards), making this operation longer since the pointer values together with their aliases (resulted from using container_of) are added to the hash.

I understand the benefits but I personally favor simplicity over performance, especially for code used as a debugging tool. DEBUG_SLAB already introduces an overhead by poisoning the allocated blocks. Generating the backtrace and filling in the memleak objects for every allocation is another overhead. Global structures are indeed a scalability problem but for a reasonable number of CPUs their overhead might not be that big. Anyway, I can't be sure without some benchmarking and this is probably highly dependent on the system (caches, snoop control unit etc.).

Signature · 1 line
Catalin
#39 lore raw
Quoted 10 lines · Catalin Marinas
Quoted 5 lines

memleak info is at a negative offset from the allocated pointer. I.e. that if kmalloc() returns 'ptr', the memleak info could be at ptr-sizeof(memleak_info). That way you dont have to know the size of the object beforehand and there's absolutely no need for a global hash of any sort.

It would probably need to be just a pointer embedded in the allocated block. With the current design, the memleak objects have a lifetime longer than the tracked block. This is mainly to avoid long locking during memory scanning and reporting.

this thing has to be /fast/ in the common path. I dont really see the point in spreading out allocations like that for small objects. Access to the object has to be refcounted /anyway/ due to scanning. Just move that refcounting to the object freeing stage. Keep freed-but-used buffers in some sort of per-CPU list that the scanning code flushes after it's done. (Also maybe hold the cache_chain_mutex to prevent slab caches from being destroyed during scanning.)

Quoted 8 lines
Quoted 3 lines

(it gets a bit more complex for page aligned allocations for the buddy and for vmalloc - but that could be solved by adding one extra pointer into struct page. [...]

This still leaves the issue of marking objects as not being leaks or being of a different type. This is done by calling memleak_* functions at the allocation point (outside allocator) where only the pointer is known. [...]

i dont see the problem. By having the pointer we have access to the memleak descriptor too.

Quoted 4 lines

[...] In the vmalloc case, it would need to call find_vm_area. This might not be a big problem, only that memory resources are no longer treated in a unified way by kmemleak (and might not be trivial to add support for new allocators).

the pretty horrible locking dependencies in the current one are just as bad. (which could be softened by a simplified allocator - but that brings in other problems, which problems can only be solved via allocator complexity ...)

If 'unification' means global locking and bad overhead and leak descriptor maintainance complexity then yes, we very much dont want to treat them in a unified way. Unless there's some killer counter-argument against embedding the memleak descriptor in the object that we allocate it is pretty much a must.

btw., you made the argument before that what matters most is the SLAB allocator. (when i argued that we might want to extend this to other allocators as well) You cant have it both ways :)

Quoted 7 lines
Quoted 2 lines

[...] That is a far more preferable cost than the locking/cache overhead of a global hash.)

A global hash would need to be re-built for every scan (and destroyed afterwards), making this operation longer since the pointer values together with their aliases (resulted from using container_of) are added to the hash.

by 'global hash' i mean the current code.

Quoted 2 lines

I understand the benefits but I personally favor simplicity over performance, [...]

i think you are trying to clinge to a bad design detail. You spent time on it, and that time was still worthwile, believe me. I often change design details dozens of times before a patch hits lkml. It doesnt matter, really - it's the path you walk that matters. This thing /has/ to be fast/scalable to be used in distributions.

Quoted 2 lines

[...] Global structures are indeed a scalability problem but for a reasonable number of CPUs their overhead might not be that big.

lets forget you ever said this, ok? ;-)

Ingo

#40 lore raw
Quoted 9 lines · Ingo Molnar
Quoted 6 lines · Catalin Marinas
Quoted 5 lines

memleak info is at a negative offset from the allocated pointer. I.e. that if kmalloc() returns 'ptr', the memleak info could be at ptr-sizeof(memleak_info). That way you dont have to know the size of the object beforehand and there's absolutely no need for a global hash of any sort.

Quoted 7 lines
Quoted 4 lines

It would probably need to be just a pointer embedded in the allocated block. With the current design, the memleak objects have a lifetime longer than the tracked block. This is mainly to avoid long locking during memory scanning and reporting.

this thing has to be /fast/ in the common path. I dont really see the point in spreading out allocations like that for small objects.

This might have to be done for the vmalloc case, unless we embed the memleak object in the vm_struct. A different way would be to vmalloc an extra page but we waste a bit of memory (at least on ARM, the vmalloc space is pretty small). The current size of the memleak_object struct is 160 bytes.

Yet another implementation would be to embed the memleak object in the slab object (since this is the most common case) and use some kind of global hash for vmalloc or other allocators (see below for what other objects kmemleak tracks).

Quoted 6 lines

Access
to the object has to be refcounted /anyway/ due to scanning. Just move that refcounting to the object freeing stage. Keep freed-but-used buffers in some sort of per-CPU list that the scanning code flushes after it's done. (Also maybe hold the cache_chain_mutex to prevent slab caches from being destroyed during scanning.)

I'm a bit worried about locking dependencies between l3->list_lock and some lock for the freed-but-used lists. I have to investigate this as I'm not familiar with the internals of the slab allocator.

Also, do you see any issues with using RCU freeing instead of a freed-but-used list (rcu_data is already per-cpu)?

Quoted 11 lines
Quoted 8 lines
Quoted 3 lines

(it gets a bit more complex for page aligned allocations for the buddy and for vmalloc - but that could be solved by adding one extra pointer into struct page. [...]

This still leaves the issue of marking objects as not being leaks or being of a different type. This is done by calling memleak_* functions at the allocation point (outside allocator) where only the pointer is known. [...]

i dont see the problem. By having the pointer we have access to the memleak descriptor too.

Maybe not directly (i.e. without find_vm_area) in the vmalloc case but it depends on where we store the memleak_object in this case.

Quoted 7 lines
Quoted 4 lines

[...] In the vmalloc case, it would need to call find_vm_area. This might not be a big problem, only that memory resources are no longer treated in a unified way by kmemleak (and might not be trivial to add support for new allocators).

the pretty horrible locking dependencies in the current one are just as bad.

Yes, I agree, and I'll implement a simplified allocator.

Quoted 5 lines

If 'unification' means global locking and bad overhead and leak descriptor maintainance complexity then yes, we very much dont want to treat them in a unified way. Unless there's some killer counter-argument against embedding the memleak descriptor in the object that we allocate it is pretty much a must.

I don't have a strong counter-argument, I just try to find solutions to the difficulties I encountered during the initial implementation.

Quoted 3 lines

btw., you made the argument before that what matters most is the SLAB allocator. (when i argued that we might want to extend this to other allocators as well) You cant have it both ways :)

I forgot to mention but it needs to track the vmalloc allocations as well since vmalloc'ed objects can have pointers to slab objects (one clear example is the loadable modules).

There are also some memory areas that need to be scanned or tracked (so that we don't get false positives) but are not allocated via slab or vmalloc (like alloc_large_system_hash or percpu_modalloc). I currently treat them in a /unified/ way, just by calling memleak_alloc() on those pointers (as with slab and vmalloc). I can change the API and add a memleak_add_area or similar and store them in some internal memleak structure, global or per-CPU (it might not matter much since these are called quite seldom but I should stop expressing opinions on scalability :-)).

Quoted 8 lines
Quoted 2 lines

I understand the benefits but I personally favor simplicity over performance, [...]

i think you are trying to clinge to a bad design detail. You spent time on it, and that time was still worthwile, believe me. I often change design details dozens of times before a patch hits lkml. It doesnt matter, really - it's the path you walk that matters. This thing /has/ to be fast/scalable to be used in distributions.

I don't have an issue with dumping the current design but, as I said, I need to think about solutions to the problems I encountered in the past (maybe I should just start re-coding kmemleak and see whether it works but I try to make the transition as easy as possible since I do this mainly in my spare time and want to finish it in a reasonable time).

Quoted 4 lines
Quoted 2 lines

[...] Global structures are indeed a scalability problem but for a reasonable number of CPUs their overhead might not be that big.

lets forget you ever said this, ok? ;-)

Well, most of my Linux experience is on limited resources embedded systems (ARM only recently joined the multi-CPU world). Enlightening is welcomed :-)

Thanks for your comments.

Signature · 1 line
Catalin