Skip to contentSkip to conversation

Kernel memory leak detector 0.7

PATCH In review Catalin Marinas 7 participants 52 messages Jun 11, 2006 – Aug 3, 2006

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

cover Kernel memory leak detector 0.7

This is a new version (0.7) of the kernel memory leak detector. See the Documentation/kmemleak.txt file for a more detailed description. The patches are downloadable from (the bundled patch or the series):

http://homepage.ntlworld.com/cmarinas/kmemleak/patch-2.6.17-rc6-kmemleak-0.7.bz2
http://homepage.ntlworld.com/cmarinas/kmemleak/patches-kmemleak-0.7.tar.bz2

What's new in this version:

- different configuration options added for tweaking kmemleak
- reduced the length of time running with interrupts disabled (the interrupts are now only disabled for individual memory block scanning rather than for the whole memory)
- fixed bug in the memleak_seq_* functions (pointer structure accessed after freeing)
- more false positives ignored

To do:

- more testing
- more investigation into the task stacks scanning
- NUMA support
- (support for ioremap tracking)

Many thanks to Michal Piotrowski for stress-testing kmemleak and reporting various issues.

Signature · 1 line
Catalin
#1 lore raw

PATCH 1/9 Base support for kmemleak

From: Catalin Marinas <[email protected]>

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 orphan pointers are not freed but only shown in /proc/memleak. Enabling this feature would introduce an overhead to memory allocations.

---

 include/linux/kernel.h  |    7 
 include/linux/memleak.h |   83 +++
 init/main.c             |    3 
 lib/Kconfig.debug       |   65 +++
 mm/Makefile             |    2 
 mm/memleak.c            | 1166 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 1323 insertions(+), 3 deletions(-)
include/linux/kernel.h +6 -1
index f4fc576..9155457 100644
@@ -13,6 +13,7 @@ #include <linux/stddef.h>
 #include <linux/types.h>
 #include <linux/compiler.h>
 #include <linux/bitops.h>
+#include <linux/memleak.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
 
@@ -284,9 +285,13 @@ #define max_t(type,x,y) \
  * @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 +83 -0

83 lines not on this page · raw message

init/main.c +2 -1
index f715b9b..986487c 100644
@@ -513,6 +513,8 @@ #endif
 	cpuset_init_early();
 	mem_init();
 	kmem_cache_init();
+	radix_tree_init();
+	memleak_init();
 	setup_per_cpu_pageset();
 	numa_policy_init();
 	if (late_time_init)
@@ -533,7 +535,6 @@ #endif
 	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 +65 -0

71 lines not on this page · raw message

mm/Makefile +1 -1
index 0b8f73f..d487d96 100644
@@ -23,4 +23,4 @@ obj-$(CONFIG_SLAB) += slab.o
 obj-$(CONFIG_MEMORY_HOTPLUG) += memory_hotplug.o
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
 obj-$(CONFIG_MIGRATION) += migrate.o
-
+obj-$(CONFIG_DEBUG_MEMLEAK) += memleak.o
mm/memleak.c new file +1166 -0

1,166 lines not on this page · raw message

#4 lore raw

PATCH 2/9 Some documentation for kmemleak

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

---

 Documentation/kmemleak.txt |   92 ++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 92 insertions(+), 0 deletions(-)
Documentation/kmemleak.txt new file +92 -0
new file mode 100644
index 0000000..7072325
@@ -0,0 +1,92 @@
+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 pointers 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.
+
+
+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 radix tree. The
+corresponding freeing function calls are tracked and the pointers
+removed from the radix tree.
+
+An allocated block of memory is considered orphan if a pointer to its
+start address or to an alias (pointer aliases are explained later)
+cannot 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 pointers as white (remaining white pointers 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 radix
+     tree. If a white pointer is found, it is added to the grey list
+  3. scan the grey pointers for matching addresses (some white
+     pointers can become grey and added at the end of the grey list)
+     until the grey set is finished
+  4. the remaining white pointers 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 size information is stored in the
+.init.memleak_offsets section. The memleak_init() function creates a
+radix tree with corresponding offsets for every encountered block
+size. The memory allocations hook stores the pointer address together
+with its aliases based on the size of the allocated block.
+
+While one level of offsets should be enough for most cases, two levels
+are considered, i.e. container_of(container_of(...)) (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.
+
+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 (as a side node, it seems
+that gcc-4.0 doesn't compile these offsetof constructs either).
+
+Page allocations and ioremap are not tracked. NUMA architectures are
+not supported yet.
+
+Only the ARM and i386 architectures are currently supported.
#7 lore raw

PATCH 5/9 Add kmemleak support for i386

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

This patch modifies the vmlinux.lds.S script and adds the backtrace support for i386 to be used with kmemleak.

---

 arch/i386/kernel/vmlinux.lds.S |    4 ++++
 include/asm-i386/processor.h   |   12 ++++++++++++
 include/asm-i386/thread_info.h |   10 +++++++++-
 3 files changed, 25 insertions(+), 1 deletions(-)
arch/i386/kernel/vmlinux.lds.S +4 -0
index 8831303..370480e 100644
@@ -38,6 +38,7 @@ SECTIONS
   RODATA
 
   /* writeable */
+  _sdata = .;			/* Start of data section */
   .data : AT(ADDR(.data) - LOAD_OFFSET) {	/* Data */
 	*(.data)
 	CONSTRUCTORS
@@ -140,6 +141,9 @@ SECTIONS
   __per_cpu_start = .;
   .data.percpu  : AT(ADDR(.data.percpu) - LOAD_OFFSET) { *(.data.percpu) }
   __per_cpu_end = .;
+  __memleak_offsets_start = .;
+  .init.memleak_offsets : AT(ADDR(.init.memleak_offsets) - LOAD_OFFSET) { *(.init.memleak_offsets) }
+  __memleak_offsets_end = .;
   . = ALIGN(4096);
   __init_end = .;
   /* freed after init ends here */
include/asm-i386/processor.h +12 -0
index 805f0dc..9b6568a 100644
@@ -743,4 +743,16 @@ #else
 #define mcheck_init(c) do {} while(0)
 #endif
 
+#ifdef CONFIG_FRAME_POINTER
+static inline unsigned long arch_call_address(void *frame)
+{
+	return *(unsigned long *) (frame + 4);
+}
+
+static inline void *arch_prev_frame(void *frame)
+{
+	return *(void **) frame;
+}
+#endif
+
 #endif /* __ASM_I386_PROCESSOR_H */
include/asm-i386/thread_info.h +9 -1
index 1f7d48c..7e7c508 100644
@@ -102,12 +102,20 @@ #define alloc_thread_info(tsk)					\
 		struct thread_info *ret;			\
 								\
 		ret = kmalloc(THREAD_SIZE, GFP_KERNEL);		\
+		memleak_ignore(ret);				\
 		if (ret)					\
 			memset(ret, 0, THREAD_SIZE);		\
 		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 4/9 Modules support for kmemleak

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

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

---

 kernel/module.c |   32 ++++++++++++++++++++++++++++++++
 1 files changed, 32 insertions(+), 0 deletions(-)
kernel/module.c +32 -0
index bbe0486..2b66374 100644
@@ -1413,6 +1413,9 @@ static struct module *load_module(void _
 		exportindex, modindex, obsparmindex, infoindex, gplindex,
 		crcindex, gplcrcindex, versindex, pcpuindex, gplfutureindex,
 		gplfuturecrcindex;
+#ifdef CONFIG_DEBUG_MEMLEAK
+	unsigned int dataindex, bssindex, mloffindex;
+#endif
 	struct module *mod;
 	long err = 0;
 	void *percpu = NULL, *ptr = NULL; /* Stops spurious gcc warning */
@@ -1510,6 +1513,11 @@ #ifdef CONFIG_KALLSYMS
 	sechdrs[symindex].sh_flags |= SHF_ALLOC;
 	sechdrs[strindex].sh_flags |= SHF_ALLOC;
 #endif
+#ifdef CONFIG_DEBUG_MEMLEAK
+	dataindex = find_sec(hdr, sechdrs, secstrings, ".data");
+	bssindex = find_sec(hdr, sechdrs, secstrings, ".bss");
+	mloffindex = find_sec(hdr, sechdrs, secstrings, ".init.memleak_offsets");
+#endif
 
 	/* Check module struct version now, before we try to use module. */
 	if (!check_modstruct_version(sechdrs, versindex, mod)) {
@@ -1569,6 +1577,7 @@ #endif
 
 	/* Do the allocs. */
 	ptr = module_alloc(mod->core_size);
+	memleak_not_leak(ptr);
 	if (!ptr) {
 		err = -ENOMEM;
 		goto free_percpu;
@@ -1577,6 +1586,7 @@ #endif
 	mod->module_core = ptr;
 
 	ptr = module_alloc(mod->init_size);
+	memleak_ignore(ptr);
 	if (!ptr && mod->init_size) {
 		err = -ENOMEM;
 		goto free_core;
@@ -1608,6 +1618,28 @@ #endif
 	/* Module has been moved. */
 	mod = (void *)sechdrs[modindex].sh_addr;
 
+#ifdef CONFIG_DEBUG_MEMLEAK
+	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));
+	if (dataindex)
+		memleak_scan_area(mod->module_core,
+				  sechdrs[dataindex].sh_addr
+				    - (unsigned long)mod->module_core,
+				  sechdrs[dataindex].sh_size);
+	if (bssindex)
+		memleak_scan_area(mod->module_core,
+				  sechdrs[bssindex].sh_addr
+				    - (unsigned long)mod->module_core,
+				  sechdrs[bssindex].sh_size);
+#endif
+
 	/* Now we've moved module, initialize linked lists, etc. */
 	module_unload_init(mod);
 
#8 lore raw

PATCH 6/9 Add kmemleak support for ARM

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

This patch modifies the vmlinux.lds.S script and adds the backtrace support for ARM to be used with kmemleak.

---

 arch/arm/kernel/vmlinux.lds.S |    7 +++++++
 include/asm-arm/processor.h   |   12 ++++++++++++
 2 files changed, 19 insertions(+), 0 deletions(-)
arch/arm/kernel/vmlinux.lds.S +7 -0
index 2b254e8..c6f038c 100644
@@ -68,6 +68,11 @@ #endif
 		__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)
@@ -110,6 +115,7 @@ #endif
 
 	.data : AT(__data_loc) {
 		__data_start = .;	/* address in memory */
+		_sdata = .;
 
 		/*
 		 * first, the init task union, aligned
@@ -158,6 +164,7 @@ #endif
 		__bss_start = .;	/* BSS				*/
 		*(.bss)
 		*(COMMON)
+		__bss_stop = .;
 		_end = .;
 	}
 					/* Stabs debugging sections.	*/
include/asm-arm/processor.h +12 -0
index 04f4d34..feaf017 100644
@@ -121,6 +121,18 @@ #define spin_lock_prefetch(x) do { } whi
 
 #endif
 
+#ifdef CONFIG_FRAME_POINTER
+static inline unsigned long arch_call_address(void *frame)
+{
+	return *(unsigned long *) (frame - 4) - 4;
+}
+
+static inline void *arch_prev_frame(void *frame)
+{
+	return *(void **) (frame - 12);
+}
+#endif
+
 #endif
 
 #endif /* __ASM_ARM_PROCESSOR_H */
#5 lore raw

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

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

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

---

 include/linux/slab.h |    4 ++++
 mm/page_alloc.c      |    2 ++
 mm/slab.c            |   22 ++++++++++++++++++++--
 mm/vmalloc.c         |   24 ++++++++++++++++++++++--
 4 files changed, 48 insertions(+), 4 deletions(-)
include/linux/slab.h +4 -0
index 2d985d5..aa37216 100644
@@ -89,6 +89,7 @@ #endif
 
 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) \
@@ -107,6 +108,7 @@ found:
 			malloc_sizes[i].cs_dmacachep :
 			malloc_sizes[i].cs_cachep, flags);
 	}
+#endif
 	return __kmalloc(size, flags);
 }
 
@@ -114,6 +116,7 @@ extern void *__kzalloc(size_t, gfp_t);
 
 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) \
@@ -132,6 +135,7 @@ found:
 			malloc_sizes[i].cs_dmacachep :
 			malloc_sizes[i].cs_cachep, flags);
 	}
+#endif
 	return __kzalloc(size, flags);
 }
 
mm/page_alloc.c +2 -0
index 253a450..4a65aa9 100644
@@ -2800,6 +2800,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 +20 -2
index f1b644e..0d38f74 100644
@@ -2878,6 +2878,7 @@ #endif
 		STATS_INC_ALLOCMISS(cachep);
 		objp = cache_alloc_refill(cachep, flags);
 	}
+	memleak_erase(ac->entry[ac->avail]);
 	return objp;
 }
 
@@ -3143,7 +3144,11 @@ #endif
  */
 void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
 {
-	return __cache_alloc(cachep, flags, __builtin_return_address(0));
+	void *ptr = __cache_alloc(cachep, flags, __builtin_return_address(0));
+
+	memleak_alloc(ptr, cachep->obj_size, 1);
+
+	return ptr;
 }
 EXPORT_SYMBOL(kmem_cache_alloc);
 
@@ -3158,6 +3163,9 @@ EXPORT_SYMBOL(kmem_cache_alloc);
 void *kmem_cache_zalloc(struct kmem_cache *cache, gfp_t flags)
 {
 	void *ret = __cache_alloc(cache, flags, __builtin_return_address(0));
+
+	memleak_alloc(ret, cache->obj_size, 1);
+
 	if (ret)
 		memset(ret, 0, obj_size(cache));
 	return ret;
@@ -3279,6 +3287,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_.
@@ -3288,7 +3297,11 @@ 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_alloc(ptr, size, 1);
+
+	return ptr;
 }
 
 
@@ -3372,6 +3385,9 @@ void kmem_cache_free(struct kmem_cache *
 	unsigned long flags;
 
 	local_irq_save(flags);
+
+	memleak_free(objp);
+
 	__cache_free(cachep, objp);
 	local_irq_restore(flags);
 }
@@ -3395,6 +3411,8 @@ void kfree(const void *objp)
 		return;
 	local_irq_save(flags);
 	kfree_debugcheck(objp);
+	memleak_free(objp);
+
 	c = virt_to_cache(objp);
 	mutex_debug_check_no_locks_freed(objp, obj_size(c));
 	__cache_free(c, (void *)objp);
mm/vmalloc.c +22 -2
index c0504f1..b7a9db3 100644
@@ -349,6 +349,9 @@ void __vunmap(void *addr, int deallocate
 void vfree(void *addr)
 {
 	BUG_ON(in_interrupt());
+
+	memleak_free(addr);
+
 	__vunmap(addr, 1);
 }
 EXPORT_SYMBOL(vfree);
@@ -447,7 +450,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;
 }
 
 /**
@@ -466,6 +476,10 @@ void *__vmalloc_node(unsigned long size,
 			int node)
 {
 	struct vm_struct *area;
+	void *addr;
+#ifdef CONFIG_DEBUG_MEMLEAK
+	unsigned long real_size = size;
+#endif
 
 	size = PAGE_ALIGN(size);
 	if (!size || (size >> PAGE_SHIFT) > num_physpages)
@@ -475,7 +489,13 @@ void *__vmalloc_node(unsigned long size,
 	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;
 }
 EXPORT_SYMBOL(__vmalloc_node);
 
#9 lore raw

PATCH 7/9 Remove some of the kmemleak false positives

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

There are allocations for which the main pointer cannot be found but they are not memory leaks. This patch fixes some of them.

---

 arch/i386/kernel/setup.c |    1 +
 drivers/base/platform.c  |    1 +
 drivers/hwmon/w83627hf.c |    1 +
 drivers/scsi/hosts.c     |    1 +
 fs/ext3/dir.c            |    1 +
 ipc/util.c               |    2 ++
 kernel/params.c          |    7 +++++--
 mm/slab.c                |    1 +
 net/core/dev.c           |    1 +
 net/sched/sch_generic.c  |    1 +
 10 files changed, 15 insertions(+), 2 deletions(-)
arch/i386/kernel/setup.c +1 -0
index dd6b0e3..0866fcf 100644
@@ -1323,6 +1323,7 @@ legacy_init_iomem_resources(struct resou
 		if (e820.map[i].addr + e820.map[i].size > 0x100000000ULL)
 			continue;
 		res = kzalloc(sizeof(struct resource), GFP_ATOMIC);
+		memleak_not_leak(res);
 		switch (e820.map[i].type) {
 		case E820_RAM:	res->name = "System RAM"; break;
 		case E820_ACPI:	res->name = "ACPI Tables"; break;
drivers/base/platform.c +1 -0
index 83f5c59..f818909 100644
@@ -166,6 +166,7 @@ struct platform_device *platform_device_
 	struct platform_object *pa;
 
 	pa = kzalloc(sizeof(struct platform_object) + strlen(name), GFP_KERNEL);
+	memleak_padding(pa, 0, sizeof(struct platform_object));
 	if (pa) {
 		strcpy(pa->name, name);
 		pa->pdev.name = pa->name;
drivers/hwmon/w83627hf.c +1 -0
index 71fb7f1..4208d37 100644
@@ -1065,6 +1065,7 @@ static int w83627hf_detect(struct i2c_ad
 		err = -ENOMEM;
 		goto ERROR1;
 	}
+	memleak_container(struct w83627hf_data, client);
 
 	new_client = &data->client;
 	i2c_set_clientdata(new_client, data);
drivers/scsi/hosts.c +1 -0
index dfcb96f..0a05151 100644
@@ -297,6 +297,7 @@ struct Scsi_Host *scsi_host_alloc(struct
 	shost = kzalloc(sizeof(struct Scsi_Host) + privsize, gfp_mask);
 	if (!shost)
 		return NULL;
+	memleak_padding(shost, 0, sizeof(struct Scsi_Host));
 
 	spin_lock_init(&shost->default_lock);
 	scsi_assign_lock(shost, &shost->default_lock);
fs/ext3/dir.c +1 -0
index f37528e..f66fbed 100644
@@ -346,6 +346,7 @@ int ext3_htree_store_dirent(struct file 
 	new_fn = kmalloc(len, GFP_KERNEL);
 	if (!new_fn)
 		return -ENOMEM;
+	memleak_padding(new_fn, 0, sizeof(struct fname));
 	memset(new_fn, 0, len);
 	new_fn->hash = hash;
 	new_fn->minor_hash = minor_hash;
ipc/util.c +2 -0
index 8193299..dcf3e2d 100644
@@ -389,6 +389,7 @@ void* ipc_rcu_alloc(int size)
 	 */
 	if (rcu_use_vmalloc(size)) {
 		out = vmalloc(HDRLEN_VMALLOC + size);
+		memleak_not_leak(out);
 		if (out) {
 			out += HDRLEN_VMALLOC;
 			container_of(out, struct ipc_rcu_hdr, data)->is_vmalloc = 1;
@@ -396,6 +397,7 @@ void* ipc_rcu_alloc(int size)
 		}
 	} else {
 		out = kmalloc(HDRLEN_KMALLOC + size, GFP_KERNEL);
+		memleak_not_leak(out);
 		if (out) {
 			out += HDRLEN_KMALLOC;
 			container_of(out, struct ipc_rcu_hdr, data)->is_vmalloc = 0;
kernel/params.c +5 -2
index af43ecd..a30beaf 100644
@@ -548,6 +548,7 @@ static void __init kernel_param_sysfs_se
 					    unsigned int name_skip)
 {
 	struct module_kobject *mk;
+	struct module_param_attrs *mp;
 
 	mk = kzalloc(sizeof(struct module_kobject), GFP_KERNEL);
 	BUG_ON(!mk);
@@ -557,11 +558,13 @@ static void __init kernel_param_sysfs_se
 	kobject_set_name(&mk->kobj, name);
 	kobject_register(&mk->kobj);
 
+	mp = param_sysfs_setup(mk, kparam, num_params, name_skip);
 	/* 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);
-	}
+	} else
+		memleak_not_leak(mp);
 }
 
 /*
mm/slab.c +1 -0
index 0d38f74..395e7bb 100644
@@ -3357,6 +3357,7 @@ void *__alloc_percpu(size_t size)
 		memset(pdata->ptrs[i], 0, size);
 	}
 
+	memleak_not_leak(pdata);
 	/* Catch derefs w/o wrappers */
 	return (void *)(~(unsigned long)pdata);
 
net/core/dev.c +1 -0
index 4fba549..2ab745f 100644
@@ -3103,6 +3103,7 @@ 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;
+	memleak_padding(p, dev->padded, sizeof(struct net_device));
 
 	if (sizeof_priv)
 		dev->priv = netdev_priv(dev);
net/sched/sch_generic.c +1 -0
index 138ea92..5422889 100644
@@ -427,6 +427,7 @@ struct Qdisc *qdisc_alloc(struct net_dev
 	memset(p, 0, size);
 	sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 	sch->padded = (char *) sch - (char *) p;
+	memleak_padding(p, sch->padded, sizeof(struct Qdisc));
 
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
#50 lore raw

PATCH 8/9 Simple testing for kmemleak

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

This patch only contains some very simple testing at the moment. Proper testing will be needed.

---

 lib/Kconfig.debug |    9 ++++++
 mm/Makefile       |    1 +
 mm/memleak-test.c |   83 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 93 insertions(+), 0 deletions(-)
lib/Kconfig.debug +9 -0
index 8bfc665..36e001b 100644
@@ -154,6 +154,15 @@ config DEBUG_MEMLEAK_ORPHAN_FREEING
 	  information displayed allow an easier identification of
 	  false positives.
 
+config DEBUG_MEMLEAK_TEST
+	tristate "Test the kernel memory leak detector"
+	default n
+	depends on DEBUG_MEMLEAK
+	help
+	  Say Y here to build the test harness for the kernel memory
+	  leak detector. At the moment, this option enables a module
+	  that explicitly leaks memory.
+
 config DEBUG_PREEMPT
 	bool "Debug preemptible kernel"
 	depends on DEBUG_KERNEL && PREEMPT
mm/Makefile +1 -0
index d487d96..aef1bd8 100644
@@ -24,3 +24,4 @@ obj-$(CONFIG_MEMORY_HOTPLUG) += memory_h
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
 obj-$(CONFIG_MIGRATION) += migrate.o
 obj-$(CONFIG_DEBUG_MEMLEAK) += memleak.o
+obj-$(CONFIG_DEBUG_MEMLEAK_TEST) += memleak-test.o
mm/memleak-test.c new file +83 -0

83 lines not on this page · raw message

#51 lore raw

PATCH 9/9 Keep the __init functions after initialization

In reply to Catalin Marinas

From: Catalin Marinas <[email protected]>

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 |    4 ++++
 lib/Kconfig.debug    |   10 ++++++++++
 2 files changed, 14 insertions(+), 0 deletions(-)
include/linux/init.h +4 -0
index 93dcbe1..198edb5 100644
@@ -41,7 +41,11 @@ #include <linux/compiler.h>
 
 /* These are for everybody (although not all archs will actually
    discard it in modules) */
+#ifdef CONFIG_DEBUG_KEEP_INIT
+#define __init
+#else
 #define __init		__attribute__ ((__section__ (".init.text")))
+#endif
 #define __initdata	__attribute__ ((__section__ (".init.data")))
 #define __exitdata	__attribute__ ((__section__(".exit.data")))
 #define __exit_call	__attribute_used__ __attribute__ ((__section__ (".exitcall.exit")))
lib/Kconfig.debug +10 -0
index 36e001b..54b3d0d 100644
@@ -154,6 +154,16 @@ config DEBUG_MEMLEAK_ORPHAN_FREEING
 	  information displayed allow an easier identification of
 	  false positives.
 
+config DEBUG_KEEP_INIT
+	bool "Do not free the __init functions"
+	default n
+	depends on DEBUG_MEMLEAK
+	help
+	  This option moves the __init functions out of the .init.text
+	  section and therefore they are no longer freed after the
+	  kernel initialization. It is useful for identifying memory
+	  leaks happening during the kernel or modules initialization.
+
 config DEBUG_MEMLEAK_TEST
 	tristate "Test the kernel memory leak detector"
 	default n
#10 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Catalin Marinas

Hi Catalin,

Quoted 2 lines · 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.

Can we fix this by looking for pointers to anywhere in the allocated memory block instead of just looking for the start?

Pekka

#11 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 8 lines · Pekka Enberg

Hi Catalin,

Quoted 2 lines · 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.

Can we fix this by looking for pointers to anywhere in the allocated memory block instead of just looking for the start?

I thought about this as well (I think that's how Valgrind works) but it would increase the chances of missing real leaks. It currently looks for the start of the block and a few locations inside the block (those from which the main pointer is computed using the container_of() macro).

I need to do some tests to see how it works but I won't be able to use the radix_tree (as storing each location in the block would lead to a huge tree).

Signature · 1 line
Catalin
#12 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Hi,

Quoted 2 lines · Pekka Enberg
Quoted 2 lines

Can we fix this by looking for pointers to anywhere in the allocated memory block instead of just looking for the start?

Quoted 2 lines · Catalin Marinas

I thought about this as well (I think that's how Valgrind works) but it would increase the chances of missing real leaks.

Yeah but that's far better than adding bunch of 'not a leak' annotations around the kernel which is very impractical to maintain. I would like to see your leak detector in the kernel so we can finally get rid of all those per-subsystem magic allocators. This patch, however, is unacceptable for inclusion IMHO.

Pekka

#13 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 5 lines · Pekka J Enberg
Quoted 2 lines · Pekka Enberg
Quoted 2 lines

Can we fix this by looking for pointers to anywhere in the allocated memory block instead of just looking for the start?

On Mon, 12 Jun 2006, Catalin Marinas wrote:

Quoted 8 lines
Quoted 2 lines

I thought about this as well (I think that's how Valgrind works) but it would increase the chances of missing real leaks.

Yeah but that's far better than adding bunch of 'not a leak' annotations around the kernel which is very impractical to maintain. I would like to see your leak detector in the kernel so we can finally get rid of all those per-subsystem magic allocators. This patch, however, is unacceptable for inclusion IMHO.

My initial hope was that simply tweaking the container_of macro would be enough to get the inside-block pointers (or, at least, modify some key places like net/core/dev.c) but it looks like it wasn't and I introduced the memleak_not_leak() function which had to be added to some individual drivers as well.

As I said, I'll do some tests first because looking at all the locations inside a block might make the tool less useful.

Signature · 1 line
Catalin
#41 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Catalin Marinas
Quoted 16 lines · Catalin Marinas
Quoted 8 lines · Pekka Enberg

Hi Catalin,

Quoted 2 lines · 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.

Can we fix this by looking for pointers to anywhere in the allocated memory block instead of just looking for the start?

I thought about this as well (I think that's how Valgrind works) but it would increase the chances of missing real leaks. It currently looks for the start of the block and a few locations inside the block (those from which the main pointer is computed using the container_of() macro).

Quoted 3 lines

I need to do some tests to see how it works but I won't be able to use the radix_tree (as storing each location in the block would lead to a huge tree).

A radix-priority-search-tree would allow to store intervals and query addresses.

Peter

#42 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 6 lines · Peter Zijlstra
Quoted 3 lines

I need to do some tests to see how it works but I won't be able to use the radix_tree (as storing each location in the block would lead to a huge tree).

A radix-priority-search-tree would allow to store intervals and query addresses.

Great, this would simplify things. I'll post a new version using this in the next days.

Thanks.

Signature · 1 line
Catalin
#14 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Pekka J Enberg
Quoted 9 lines · Pekka J Enberg
Quoted 2 lines · Catalin Marinas

I thought about this as well (I think that's how Valgrind works) but it would increase the chances of missing real leaks.

Yeah but that's far better than adding bunch of 'not a leak' annotations around the kernel which is very impractical to maintain. I would like to see your leak detector in the kernel so we can finally get rid of all those per-subsystem magic allocators. This patch, however, is unacceptable for inclusion IMHO.

While it's always good to reduce the amount of false positives, i dont think it's unacceptable for inclusion right now. A few dozen annotations out of 7000+ allocation call sites isnt a big maintainance problem - and the benefits of automatic leak-checking are really huge. The impact only appears to be large because the patch is trying to cover an initial 7+ million lines of codebase. The followup per-kernel-release overhead will be minimal, and will be offset by the quality increase of the kernel and by the productivity increase that comes due to developers not having to do long searches for kernel memory leaks. The debugging cost of a single leak found can far outweigh the cost of 10 annotations (or more).

What i'd like to see though are clear explanations about why an allocation is not considered a leak, in terms of comments added to the code. That will also help us reduce the number of annotations later on.

Ingo

#15 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Hi Ingo,

Quoted 4 lines · Ingo Molnar

While it's always good to reduce the amount of false positives, i dont think it's unacceptable for inclusion right now. A few dozen annotations out of 7000+ allocation call sites isnt a big maintainance problem - and the benefits of automatic leak-checking are really huge.

Did you look at the call sites? It seems clear that kmemleak doesn't support existing kernel coding style yet (see below) which means we're not covering all false positives.

Quoted 3 lines · Ingo Molnar

What i'd like to see though are clear explanations about why an allocation is not considered a leak, in terms of comments added to the code. That will also help us reduce the number of annotations later on.

I found at least two unacceptable false positive classes:

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

- drivers/base/platform.c and fs/ext3/dir.c:
False positive because we allocate memory for struct + some extra stuff.

At least the latter can be fixed as outlined by Catalin in another mail.

Pekka

#16 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 9 lines · Pekka J Enberg
Quoted 4 lines · Ingo Molnar

While it's always good to reduce the amount of false positives, i dont think it's unacceptable for inclusion right now. A few dozen annotations out of 7000+ allocation call sites isnt a big maintainance problem - and the benefits of automatic leak-checking are really huge.

Did you look at the call sites? It seems clear that kmemleak doesn't support existing kernel coding style yet (see below) which means we're not covering all false positives.

but "supporting existing kernel coding style as-is" is not a must-have criterium for inclusion. While preserving semantics is strongly encouraged of course, a patch can change semantics (or can introduce restrictions) as long as it's common-sense or there is no other way out. The question is benefit vs. disadvantage, not a rigid "does it change semantics" rule.

Just look at Sparse annotations: they add maintainance overhead, but the overhead is well worth the trouble: they avoid bugs and they also serve as documentation/specification. And Sparse annotations are alot more numerous than kmemleak annotations will ever be!

Quoted 10 lines · Ingo Molnar
Quoted 3 lines

What i'd like to see though are clear explanations about why an allocation is not considered a leak, in terms of comments added to the code. That will also help us reduce the number of annotations later on.

I found at least two unacceptable false positive classes:

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

there's no good way around this one but to annotate it in one way or another.

We could express the non-leak nature of this allocation in a cleaner way by introducing the following API:

	memleak_boot_time_alloc(res);

Here kmemleak should build a global list of such allocations, with the following rules: these allocations must not be freed after that point, but these allocations will be searched for further pointers.

Via this method we will both document the special nature of these allocations and we'll enforce that it's not freed. (not that there is a high likelyhood of freeing a buffer whose pointer nobody knows - the purpose is rather to make sure that the annotation is correct)

Quoted 6 lines

- drivers/base/platform.c and fs/ext3/dir.c:
False positive because we allocate memory for struct + some extra stuff.

At least the latter can be fixed as outlined by Catalin in another mail.

yes.

my "document the exceptions" request was to make sure that such special rules are not forgotten. As long as they are documented clearly, if there's some common pattern between a number of them then they can be moved into the kmemleak infrastructure, to further reduce the annotation overhead.

Ingo

#17 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 6 lines · Ingo Molnar

but "supporting existing kernel coding style as-is" is not a must-have criterium for inclusion. While preserving semantics is strongly encouraged of course, a patch can change semantics (or can introduce restrictions) as long as it's common-sense or there is no other way out. The question is benefit vs. disadvantage, not a rigid "does it change semantics" rule.

Agreed. I wasn't talking about general principles though but about the current kmemleak annotations, which I still find lacking as-is.

Quoted 8 lines · Ingo Molnar
Quoted 5 lines

I found at least two unacceptable false positive classes:

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

there's no good way around this one but to annotate it in one way or another.

Scanning bss and data sections is too expensive, I guess. I would prefer we create a separate section for gc roots but what you're suggesting is ok as well.

Quoted 8 lines · Ingo Molnar
Quoted 6 lines

- drivers/base/platform.c and fs/ext3/dir.c:
False positive because we allocate memory for struct + some extra stuff.

At least the latter can be fixed as outlined by Catalin in another mail.

yes.

Indeed and should be fixed before inclusion.

Pekka

#18 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 7 lines · Pekka J Enberg
Quoted 6 lines · Ingo Molnar
Quoted 5 lines

I found at least two unacceptable false positive classes:

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

Quoted 6 lines
Quoted 2 lines

there's no good way around this one but to annotate it in one way or another.

Scanning bss and data sections is too expensive, I guess. I would prefer we create a separate section for gc roots but what you're suggesting is ok as well.

Data and BSS sections are scanned, otherwise it would report a lot of false positives.

Looking again at this false positive, I might have been wrong in the first place. Since the iomem_resource is scanned (being in the data section), there should be a way to get to the "res" pointer, unless the request_resource() doesn't return NULL (or some other sibling is freed without calling release_resource).

Quoted 11 lines · Ingo Molnar
Quoted 8 lines
Quoted 6 lines

- drivers/base/platform.c and fs/ext3/dir.c:
False positive because we allocate memory for struct + some extra stuff.

At least the latter can be fixed as outlined by Catalin in another mail.

yes.

Indeed and should be fixed before inclusion.

... with a slight risk of increasing the false negatives (but reducing the memleak_padding calls).

The reason for the current implementation - because the type information is lost in alloc calls, there is no way to know what type of structure it is and what container_of() macros are used on its members. The sizeof() value provides an approximation to this but this assumption is broken once the allocated memory is different from the size of the allocated structure. The above idea would eliminate these issues

Signature · 1 line
Catalin
#22 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 3 lines · Ingo Molnar

What i'd like to see though are clear explanations about why an allocation is not considered a leak, in terms of comments added to the code. That will also help us reduce the number of annotations later on.

I'll document them in both Documentation/kmemleak.txt and inside the code. If I implement the "any pointer inside the block" method, all the memleak_padding() false positives will disappear.

Signature · 1 line
Catalin
#19 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Pekka J Enberg
Quoted 10 lines · Pekka J Enberg
Quoted 6 lines
Quoted 3 lines

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

there's no good way around this one but to annotate it in one way or another.

Scanning bss and data sections is too expensive, I guess. I would prefer we create a separate section for gc roots but what you're suggesting is ok as well.

kmemleak does scan global data sections. I dont know why we dont discover this particular pointer though: the resource pointer ought to be accessible via the iomem_resource.parent/sibling/child sorted list. Hm.

Ingo

#20 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 9 lines · Ingo Molnar
Quoted 7 lines · Pekka J Enberg
Quoted 6 lines
Quoted 3 lines

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

there's no good way around this one but to annotate it in one way or another.

Quoted 8 lines
Quoted 3 lines

Scanning bss and data sections is too expensive, I guess. I would prefer we create a separate section for gc roots but what you're suggesting is ok as well.

kmemleak does scan global data sections. I dont know why we dont discover this particular pointer though: the resource pointer ought to be accessible via the iomem_resource.parent/sibling/child sorted list. Hm.

Maybe it only appeared in the initial versions of kmemleak due to bugs in the tool and I never removed it. I'll check it again this evening on my home machine (that's where I got it). However, if request_resource() returns -EBUSY, that's a real leak.

Signature · 1 line
Catalin
#23 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Catalin Marinas
Quoted 8 lines · Catalin Marinas
Quoted 3 lines · Ingo Molnar

What i'd like to see though are clear explanations about why an allocation is not considered a leak, in terms of comments added to the code. That will also help us reduce the number of annotations later on.

I'll document them in both Documentation/kmemleak.txt and inside the code. If I implement the "any pointer inside the block" method, all the memleak_padding() false positives will disappear.

i dont know - i feel uneasy about the 'any pointer' method - it has a high potential for false negatives, especially for structures that contain strings (or other random data), etc.

did you consider the tracking of the types of allocated blocks explicitly? I'd expect that most blocks dont have pointers embedded in them that point to allocated blocks. For the ones that do, the allocation could be extended with the type information. For each affected type, we could annotate the structures themselves with offset information. How intrusive would such a method be?

Ingo

#24 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 8 lines · Ingo Molnar
Quoted 5 lines · Catalin Marinas
Quoted 3 lines · Ingo Molnar

What i'd like to see though are clear explanations about why an allocation is not considered a leak, in terms of comments added to the code. That will also help us reduce the number of annotations later on.

Quoted 7 lines
Quoted 3 lines

I'll document them in both Documentation/kmemleak.txt and inside the code. If I implement the "any pointer inside the block" method, all the memleak_padding() false positives will disappear.

i dont know - i feel uneasy about the 'any pointer' method - it has a high potential for false negatives, especially for structures that contain strings (or other random data), etc.

That's my concern as well. The advantage is that it simplifies kmemleak but I can't tell how good the detection would be. I can add some code to the current implementation to show how many values (32 bit aligned) found during scanning look like valid pointers (i.e. PAGE_OFFSET < x < PAGE_OFFSET + ram_size) but cannot be found in the radix_tree. It might not be that bad (I'll post tomorrow some statistics).

Quoted 6 lines

did you consider the tracking of the types of allocated blocks explicitly? I'd expect that most blocks dont have pointers embedded in them that point to allocated blocks. For the ones that do, the allocation could be extended with the type information. For each affected type, we could annotate the structures themselves with offset information. How intrusive would such a method be?

Do you mean that when scanning it should only consider at the pointer members in a structure? I don't think this can be easily achieved because of the amount of structures in the kernel. There are places where a pointer is stored as a long. There is also no way in C to quantify the type of an object (similar to "typeid" in C++). The closest approximation I could get was the size.

Signature · 1 line
Catalin
#21 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 10 lines · Ingo Molnar
Quoted 7 lines · Pekka J Enberg
Quoted 6 lines
Quoted 3 lines

- arch/i386/kernel/setup.c:
False positive because res pointer is stored in a global instance of struct resource.

there's no good way around this one but to annotate it in one way or another.

Quoted 8 lines
Quoted 3 lines

Scanning bss and data sections is too expensive, I guess. I would prefer we create a separate section for gc roots but what you're suggesting is ok as well.

kmemleak does scan global data sections. I dont know why we dont discover this particular pointer though: the resource pointer ought to be accessible via the iomem_resource.parent/sibling/child sorted list. Hm.

I tested it on my x86 machine and kmemleak is right, this is a leak because request_resource() returns -EBUSY. Something like the attached patch fixes it (I'm not sure that's the correct fix, maybe we should check why the resource overlaps with something else).

Signature · 1 line
Catalin
arch/i386/kernel/setup.c +4 -1
index dd6b0e3..60f5d99 100644
@@ -1332,7 +1332,10 @@ legacy_init_iomem_resources(struct resou
 		res->start = e820.map[i].addr;
 		res->end = res->start + e820.map[i].size - 1;
 		res->flags = IORESOURCE_MEM | IORESOURCE_BUSY;
-		request_resource(&iomem_resource, res);
+		if (request_resource(&iomem_resource, res)) {
+			kfree(res);
+			continue;
+		}
 		if (e820.map[i].type == E820_RAM) {
 			/*
 			 *  We don't know which RAM region contains kernel data,
#25 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar

Hi Ingo,

Quoted 3 lines · Ingo Molnar

i dont know - i feel uneasy about the 'any pointer' method - it has a high potential for false negatives, especially for structures that contain strings (or other random data), etc.

Is that a problem in practice? Structures that contain data are usually allocated from the slab. There needs to be a link to that struct from the gc roots to get a false negative. Or am I missing something here?

Pekka

#26 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 10 lines · Pekka J Enberg

Hi Ingo,

Quoted 3 lines · Ingo Molnar

i dont know - i feel uneasy about the 'any pointer' method - it has a high potential for false negatives, especially for structures that contain strings (or other random data), etc.

Is that a problem in practice? Structures that contain data are usually allocated from the slab. There needs to be a link to that struct from the gc roots to get a false negative. Or am I missing something here?

The gc roots are the data and bss sections (and maybe task kernel stacks) and all the slab-allocated blocks are scanned if a link to them is found from the roots (and all of them are usually scanned). If no link is found, they would be reported as memory leaks (and not scanned). You can't really avoid the scanning of allocated blocks since they may contain pointers to other blocks.

Signature · 1 line
Catalin
#31 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Pekka J Enberg
Quoted 11 lines · Pekka J Enberg

Hi Ingo,

Quoted 3 lines · Ingo Molnar

i dont know - i feel uneasy about the 'any pointer' method - it has a high potential for false negatives, especially for structures that contain strings (or other random data), etc.

Is that a problem in practice? Structures that contain data are usually allocated from the slab. There needs to be a link to that struct from the gc roots to get a false negative. Or am I missing something here?

you should think of this in terms of a 'graph of data', where each node is a block of memory. The edges between nodes are represented by pointers. The graph roots from .data/bss, but it may go indefinitely into dynamically allocated blocks as well - just think of a hash-list where the hash list table is in .data, but all the chain entries are in allocated blocks and the chaining can be arbitrarily deep.

Furtermore, each block of data has a couple of fields within it that contain 'outgoing pointers', and each block of data has a couple of addresses associated with it that are valid targets for 'incoming pointers'.

The task of kmemleak is to find orphan blocks of memory - the ones that are not connected to the graph via any edge. For that it starts scanning in .data/bss and recursively searches through the blocks of memory (marking all scanned blocks, to avoid circular walking of the graph) until it has walked the whole graph. Blocks that were registered but were not touched during this recursive walking are the leaks.

Currently kmemleak does not track the per-block position of 'outgoing pointers': it assumes that all fields within a block may be an outgoing pointer. This is a source of false negatives. (fields that do not contain a real pointer might accidentally contain a value that is interpreted as a false edge - falsely connecting a leaked block to the graph.)

Kmemleak does recognize 'incoming pointers' via the offsetof tracking method, but it's limited in that it is not a type-accurate method
either: it tracks per-size offsets, so two types accidentally having the same size merges their 'possible incoming pointer offset' lists, which introduces false negatives. (a pointer may be considered an incoming edge while in reality the pointer is not validly pointing into this structure)

The full matching that was suggested before would further weaken the 'incoming pointers' logic and would introduce yet another source of false negatives: we'd match every block pointer against every possible target address that points to within another block.

My suggestion would be to attempt to achieve perfect matches: annotate structures to figure out the offset of pointers, and thus to figure out the precise source addresses and a precise list of valid target addresses. This is a quite elaborate task to pull off though, and i'm not sure it's possible without intolerable maintainance overhead, but we should consider it nevertheless. It will also be _much_ faster, because per block we'd only have to scan a handful of outgoing pointers.

Perhaps a hybrid method could be used: by default we assume the most lenient structure: if the block type is 'unknown' (which is the default for not-yet-annotated structures) then we'd assume that all fields are pointers, and that they could all be targets too.

Once a structure is annotated, the scope of scanning is drastically
reduced: only the annotated fields are scanned for pointers (and at that point we'd also _enforce_ that those pointers do indeed point to valid blocks of memory - i.e. this would also serve as a pointer-correctness checker), and annotated blocks will also restrict the scope of 'incoming pointers'.

Naturally, there would be two types of annotations: one that finetunes the scanning of outgoing pointers to happen only for fields that are true pointers, and one that finetunes incoming pointer matching to only those addresses within the block that program logic allows. All in a strictly per-type manner.

This also means that by default we'd have no false positives at all, but that there is a capable annotation method to reduce the amount of false negatives, in a gradual and managable way - down to zero if everything is annotated.

Ingo

#27 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Catalin Marinas

Hi Catalin,

Quoted 6 lines · Catalin Marinas

The gc roots are the data and bss sections (and maybe task kernel stacks) and all the slab-allocated blocks are scanned if a link to them is found from the roots (and all of them are usually scanned). If no link is found, they would be reported as memory leaks (and not scanned). You can't really avoid the scanning of allocated blocks since they may contain pointers to other blocks.

I am not sure you're agreeing or disagreeing :-). As far as I understood, Ingo is worried about:

	struct s { /* some fields */; char *buf; };

	struct s *p = kmalloc(sizeof(struct s) + BUF_SIZE);
	p->buf = p + sizeof(struct s);

Which could lead to false negative due to p->buf pointing to p. However, for us to even _find_ p->buf, we would need an incoming pointer _to_ p which makes me think this is not a problem in practice. Hmm?

Pekka

#32 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 4 lines · Ingo Molnar

This also means that by default we'd have no false positives at all, but that there is a capable annotation method to reduce the amount of false negatives, in a gradual and managable way - down to zero if everything is annotated.

Yeah, sounds much better to me. However, I am unable to figure out any real examples where we'd actually need the annotations for reasonably sane code. Do you have some in mind?

Pekka

#28 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Pekka J Enberg
Quoted 11 lines · Pekka J Enberg

Hi Catalin,

Quoted 6 lines · Catalin Marinas

The gc roots are the data and bss sections (and maybe task kernel stacks) and all the slab-allocated blocks are scanned if a link to them is found from the roots (and all of them are usually scanned). If no link is found, they would be reported as memory leaks (and not scanned). You can't really avoid the scanning of allocated blocks since they may contain pointers to other blocks.

I am not sure you're agreeing or disagreeing :-).

I'm not sure either :-). Doing some quick statistics on an ARM platform shows that there are plenty of values (almost 15%) in the scanned memory that look like pointers (i.e. between 3GB and 3GB+128MB) but do not point to any allocated block:

total scanned values = 932102
total detected pointers = 6270
detected by alias (i.e. in-block address) = 2096
looking like pointer = 135675

I'll add a test to see how many of the look-like pointers actually point to a valid in-block address. If this is considerable larger than the detected by alias above, it shouldn't be implemented.

Quoted 10 lines

As far as I understood, Ingo is worried about:

        struct s { /* some fields */; char *buf; };

        struct s *p = kmalloc(sizeof(struct s) + BUF_SIZE);
        p->buf = p + sizeof(struct s);

Which could lead to false negative due to p->buf pointing to p. However, for us to even _find_ p->buf, we would need an incoming pointer _to_ p which makes me think this is not a problem in practice. Hmm?

Not exactly. In the above case, Ingo (and me) is worried about having a incoming pointer (from other block) equal to p->buf and therefore inside the block allocated with kmalloc. It doesn't matter whether any value in a block point to locations inside the block since the actual block first needs to be accessible on the directed graph starting from the root.

Signature · 1 line
Catalin
#29 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 10 lines · Pekka J Enberg
Quoted 10 lines

As far as I understood, Ingo is worried about:

        struct s { /* some fields */; char *buf; };

        struct s *p = kmalloc(sizeof(struct s) + BUF_SIZE);
        p->buf = p + sizeof(struct s);

Which could lead to false negative due to p->buf pointing to p. However, for us to even _find_ p->buf, we would need an incoming pointer _to_ p which makes me think this is not a problem in practice. Hmm?

Quoted 3 lines · Catalin Marinas

Not exactly. In the above case, Ingo (and me) is worried about having a incoming pointer (from other block) equal to p->buf and therefore inside the block allocated with kmalloc.

Ah, right, I overlooked that case. But, is it really a leak? That is, even though we currently don't have a pointer to the beginning fo the block, we don't know for sure it was a leak. You're now allowed to do:

   p = kmalloc(...);
   p = p + HDR_SIZE;

/* ... */

   kfree(p - HDR_SIZE);

Do you think we should ban the above?

Pekka

#30 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 21 lines · Pekka Enberg
Quoted 10 lines · Pekka J Enberg
Quoted 10 lines

As far as I understood, Ingo is worried about:

        struct s { /* some fields */; char *buf; };

        struct s *p = kmalloc(sizeof(struct s) + BUF_SIZE);
        p->buf = p + sizeof(struct s);

Which could lead to false negative due to p->buf pointing to p. However, for us to even _find_ p->buf, we would need an incoming pointer _to_ p which makes me think this is not a problem in practice. Hmm?

Quoted 3 lines · Catalin Marinas

Not exactly. In the above case, Ingo (and me) is worried about having a incoming pointer (from other block) equal to p->buf and therefore inside the block allocated with kmalloc.

Ah, right, I overlooked that case. But, is it really a leak? That is, even though we currently don't have a pointer to the beginning fo the block, we don't know for sure it was a leak. You're now allowed to do:

Quoted 8 lines
    p = kmalloc(...);
    p = p + HDR_SIZE;

    /* ... */

    kfree(p - HDR_SIZE);

Do you think we should ban the above?

I don't think you can ban this because of places where the structure needs to be aligned to a certain value. Look in the false positives patch for the memleak_padding() calls with the 2nd argument not zero.

Signature · 1 line
Catalin
#33 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 15 lines · Ingo Molnar
Quoted 11 lines · Pekka J Enberg

Hi Ingo,

Quoted 3 lines · Ingo Molnar

i dont know - i feel uneasy about the 'any pointer' method - it has a high potential for false negatives, especially for structures that contain strings (or other random data), etc.

Is that a problem in practice? Structures that contain data are usually allocated from the slab. There needs to be a link to that struct from the gc roots to get a false negative. Or am I missing something here?

Quoted 6 lines

you should think of this in terms of a 'graph of data', where each node is a block of memory. The edges between nodes are represented by pointers. The graph roots from .data/bss, but it may go indefinitely into dynamically allocated blocks as well - just think of a hash-list where the hash list table is in .data, but all the chain entries are in allocated blocks and the chaining can be arbitrarily deep.

[...]

Nice description, I should add it to the kmemleak doc :-)

Quoted 6 lines

Currently kmemleak does not track the per-block position of 'outgoing pointers': it assumes that all fields within a block may be an outgoing pointer. This is a source of false negatives. (fields that do not contain a real pointer might accidentally contain a value that is interpreted as a false edge - falsely connecting a leaked block to the graph.)

That's correct but it might not be a real issue in practice. Many people use the Boehm's GC and haven't complained about the amount of false negatives (AFAIK, there is even a proposal to include it in the next C++ standard).

Quoted 7 lines

Kmemleak does recognize 'incoming pointers' via the offsetof tracking method, but it's limited in that it is not a type-accurate method
either: it tracks per-size offsets, so two types accidentally having the same size merges their 'possible incoming pointer offset' lists, which introduces false negatives. (a pointer may be considered an incoming edge while in reality the pointer is not validly pointing into this structure)

The number of collisions would need to be investigated. On my system, there are 158 distinct sizeof values generated by container_of. Of this, 90 have at least two aliases (incoming pointer offsets). I'm not sure how many different structures are in the kernel but I can't find an easy (gcc magic) way to get a unique id for a type (apart from modifying all the container_of calls and add a 4th argument - maybe a string with the name of the type).

Quoted 4 lines

The full matching that was suggested before would further weaken the 'incoming pointers' logic and would introduce yet another source of false negatives: we'd match every block pointer against every possible target address that points to within another block.

That's correct.

Quoted 7 lines

My suggestion would be to attempt to achieve perfect matches: annotate structures to figure out the offset of pointers, and thus to figure out the precise source addresses and a precise list of valid target addresses. This is a quite elaborate task to pull off though, and i'm not sure it's possible without intolerable maintainance overhead, but we should consider it nevertheless. It will also be _much_ faster, because per block we'd only have to scan a handful of outgoing pointers.

The problem would be simpler if you get a reliable typeid. If we consider the sizeof method, a script could scan the kernel and generate a list of sizeof-pointer_offset pairs which is added to a radix tree (similar to the aliases tree we have) at boot time. But this would assume adding the memleak_padding() call not only for incoming pointers but also for outgoing ones. The method, however, would eliminate the need for annotating each structure in the kernel.

Quoted 1 line

This also means that by default we'd have no false positives at all,

You can still have a scenario like this - a pointer is freed but the value remains in a valid member; it is afterwards re-allocated and leaks but the value is found in a previous allocation. I think it's a very low risk for this to happen and not worth the hassle.

Quoted 4 lines

but
that there is a capable annotation method to reduce the amount of false negatives, in a gradual and managable way - down to zero if everything is annotated.

I'm not sure this could be achieved in a maintainable way, at least not without support from the compiler.

Signature · 1 line
Catalin
#2 lore raw

Re: [PATCH 2.6.17-rc6 1/9] Base support for kmemleak

In reply to Catalin Marinas

Hi Catalin,

Quoted 5 lines · Catalin Marinas

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 orphan pointers are not freed but only shown in /proc/memleak. Enabling this feature would introduce an overhead to memory allocations.

Some coding style comments below.

include/linux/memleak.h line 5

Quoted 8 lines
include/linux/memleak.h new file +5 -0
@@ -0,0 +1,83 @@
+extern void memleak_scan_area(const void *ptr, unsigned long offset, size_t length);
+extern void memleak_insert_aliases(struct memleak_offset *ml_off_start,
+                                  struct memleak_offset *ml_off_end);
+
+#define memleak_erase(ptr)     do { (ptr) = NULL; } while (0)

Use static inline functions instead of macros, please.

include/linux/memleak.h line 79

Quoted 10 lines
include/linux/memleak.h new file +10 -0
+#define memleak_init()
+#define memleak_alloc(ptr, size, ref_count)
+#define memleak_free(ptr)
+#define memleak_padding(ptr, offset, size)
+#define memleak_not_leak(ptr)
+#define memleak_ignore(ptr)
+#define memleak_scan_area(ptr, offset, length)
+#define memleak_insert_aliases(ml_off_start, ml_off_end)
+#define memleak_erase(ptr)
+#define memleak_container(type, member)

Ditto.

mm/memleak.c line 8

Quoted 11 lines
mm/memleak.c new file +8 -0
@@ -0,0 +1,1166 @@
+typedef enum {
+       MEMLEAK_ALLOC,
+       MEMLEAK_FREE,
+       MEMLEAK_PADDING,
+       MEMLEAK_NOT_LEAK,
+       MEMLEAK_IGNORE,
+       MEMLEAK_SCAN_AREA
+} memleak_action_t;

Please drop the typedef.

mm/memleak.c line 112

Quoted 8 lines
mm/memleak.c new file +8 -0
+/* Pointer colors, encoded with count and ref_count:
+ *   - white - orphan block, i.e. not enough references to it (ref_count >= 1)
+ *   - gray  - referred at least once and therefore non-orphan (ref_count == 0)
+ *   - black - ignore; it doesn't contain references (text section) (ref_count == -1)
+ */
+#define COLOR_WHITE(pointer)   ((pointer)->count != -1 && (pointer)->count < (pointer)->ref_count)
+#define COLOR_GRAY(pointer)    ((pointer)->ref_count != -1 && (pointer)->count >= (pointer)->ref_count)
+#define COLOR_BLACK(pointer)   ((pointer)->ref_count == -1)

Use static inline functions instead of macros, please.

mm/memleak.c line 18

Quoted 2 lines
mm/memleak.c new file +2 -0
+
+static kmem_cache_t *pointer_cache;

Please use struct kmem_cache instead of the typedef.

mm/memleak.c line 129

Quoted 1 line
mm/memleak.c new file +1 -0
+static int __initdata preinit_pos = 0;

Unnecessary initialization to zero.

mm/memleak.c line 132

Quoted 1 line
mm/memleak.c new file +1 -0
+static struct memleak_pointer *last_pointer = NULL;

Same here for NULL.

Quoted 27 lines
mm/memleak.c new file +27 -0
+
+static void dump_pointer_info(struct memleak_pointer *pointer)
+{
+#ifdef CONFIG_KALLSYMS
+       char namebuf[KSYM_NAME_LEN + 1] = "";
+       char *modname;
+       unsigned long symsize;
+       unsigned long offset = 0;
+#endif
+#ifdef DEBUG
+       struct memleak_alias *alias;
+       struct hlist_node *elem;
+#endif
+       int i;
+
+       printk(KERN_NOTICE "kmemleak: pointer 0x%08lx:\n", pointer->pointer);
+#ifdef DEBUG
+       printk(KERN_NOTICE "  size = %d\n", pointer->size);
+       printk(KERN_NOTICE "  ref_count = %d\n", pointer->ref_count);
+       printk(KERN_NOTICE "  count = %d\n", pointer->count);
+       printk(KERN_NOTICE "  aliases:\n");
+       if (pointer->alias_list)
+               hlist_for_each_entry(alias, elem, pointer->alias_list, node)
+                       printk(KERN_NOTICE "    0x%lx\n", alias->offset);
+       printk(KERN_NOTICE "  trace:\n");
+#endif
+       for (i = 0; i < MAX_TRACE; i++) {

mm/memleak.c line 169

Quoted 10 lines
mm/memleak.c new file +10 -0
+               unsigned long trace = pointer->trace[i];
+
+               if (!trace)
+                       break;
+#ifdef CONFIG_KALLSYMS
+               kallsyms_lookup(trace, &symsize, &offset, &modname, namebuf);
+               printk(KERN_NOTICE "    %lx: <%s>\n", trace, namebuf);
+#else
+               printk(KERN_NOTICE "    %lx\n", trace);
+#endif

Please move both #ifdef cases into separate functions and provide a stub for the case where they're not enabled for readability.

mm/memleak.c line 178

Quoted 3 lines
mm/memleak.c new file +3 -0
+static int insert_alias(unsigned long size, unsigned long offset)
+{
+       int ret = 0;

Unnecessary initialization to zero.

mm/memleak.c line 1098

Quoted 4 lines
mm/memleak.c new file +4 -0
+/* KMemLeak initialization. Set up the radix tree for the pointer aliases */
+void __init memleak_init(void)
+{
+       int i = 0;

Unnecessary initialization to zero.

#3 lore raw

Re: [PATCH 2.6.17-rc6 1/9] Base support for kmemleak

Quoted 11 lines · Pekka Enberg

include/linux/memleak.h line 5

Quoted 8 lines · Catalin Marinas
include/linux/memleak.h new file +5 -0
@@ -0,0 +1,83 @@
+extern void memleak_scan_area(const void *ptr, unsigned long offset, size_t length);
+extern void memleak_insert_aliases(struct memleak_offset *ml_off_start,
+                                  struct memleak_offset *ml_off_end);
+
+#define memleak_erase(ptr)     do { (ptr) = NULL; } while (0)

Use static inline functions instead of macros, please.

That was the simplest way in some cases when kmemleak was not dependent on DEBUG_SLAB obj_size() in mm/slab.c was not always defined. It works correctly with inlining now so I'll change them.

Quoted 1 line

include/linux/memleak.h line 79

Quoted 1 line
include/linux/memleak.h new file +1 -0
+#define memleak_container(type, member)

This cannot be an inline function as it takes a type as argument.

Quoted 7 lines

include/linux/memleak.h line 7

Quoted 1 line
include/linux/memleak.h new file +1 -0
+static int __initdata preinit_pos = 0;

Unnecessary initialization to zero.

include/linux/memleak.h line 8

Quoted 1 line
include/linux/memleak.h new file +1 -0
+static struct memleak_pointer *last_pointer = NULL;

Same here for NULL.

True, it is unnecessary. That's just my style of marking them as initialised.

Quoted 5 lines

include/linux/memleak.h line 11

Quoted 3 lines
include/linux/memleak.h new file +3 -0
+static int insert_alias(unsigned long size, unsigned long offset)
+{
+       int ret = 0;

Unnecessary initialization to zero.

That's needed because there is an exit path which doesn't set this variable.

I am OK with the other comments. Thanks.

Signature · 1 line
Catalin
#34 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Catalin Marinas
Quoted 11 lines · Catalin Marinas
Quoted 7 lines · Ingo Molnar

you should think of this in terms of a 'graph of data', where each node is a block of memory. The edges between nodes are represented by pointers. The graph roots from .data/bss, but it may go indefinitely into dynamically allocated blocks as well - just think of a hash-list where the hash list table is in .data, but all the chain entries are in allocated blocks and the chaining can be arbitrarily deep.

[...]

Nice description, I should add it to the kmemleak doc :-)

feel free :-)

Quoted 11 lines
Quoted 6 lines

Currently kmemleak does not track the per-block position of 'outgoing pointers': it assumes that all fields within a block may be an outgoing pointer. This is a source of false negatives. (fields that do not contain a real pointer might accidentally contain a value that is interpreted as a false edge - falsely connecting a leaked block to the graph.)

That's correct but it might not be a real issue in practice. Many people use the Boehm's GC and haven't complained about the amount of false negatives (AFAIK, there is even a proposal to include it in the next C++ standard).

For a GC a false negative is no big problem - it will reduce the efficiency of the GC a bit, but that's all. For leak detection, if we happen to have a persistent false pointer in .data (or any other persistently allocated memory), it may prevent the detection of a leak permanently - at least for that bootup. Statistically it could still be found on other systems, but it would be better to have a design that will eventually lead to having no false negatives.

But it's not just about the amount of false negatives, but also about the overhead of scanning. You are concentrated on embedded systems with small RAM - but most of the testers will be running this with at last 1GB of RAM - which is _alot_ of memory to scan.

(But, if it's not possible to implement it in a sane manner then that's not an issue either - it's rather the false positives that must be avoided.)

Quoted 8 lines
Quoted 7 lines

Kmemleak does recognize 'incoming pointers' via the offsetof tracking method, but it's limited in that it is not a type-accurate method
either: it tracks per-size offsets, so two types accidentally having the same size merges their 'possible incoming pointer offset' lists, which introduces false negatives. (a pointer may be considered an incoming edge while in reality the pointer is not validly pointing into this structure)

Quoted 7 lines

The number of collisions would need to be investigated. On my system, there are 158 distinct sizeof values generated by container_of. Of this, 90 have at least two aliases (incoming pointer offsets). I'm not sure how many different structures are in the kernel but I can't find an easy (gcc magic) way to get a unique id for a type (apart from modifying all the container_of calls and add a 4th argument - maybe a string with the name of the type).

there are a couple of possibilities.

If the ID is string based then you dont even have to touch containr_of() calls - just generate the typename string via the "#y" stringification preprocessor directive, where 'y' is the second parameter of container_of().

there's another, much faster solution as well that assigns IDs build-time for globally visible types: the __builtin_types_compatible_p gcc extension to match the type against a global registry of types. I.e. here's what i use in PREEMPT_RT:

#undef TYPE_EQUAL
#define TYPE_EQUAL(lock, type) \
__builtin_types_compatible_p(typeof(lock), type *)

#define PICK_OP(type, optype, op, lock)                         \
do {                                                            \
        if (TYPE_EQUAL((lock), type))                           \
                _raw_##optype##op((type *)(lock));              \
        else if (TYPE_EQUAL(lock, spinlock_t))                  \
                _spin##op((spinlock_t *)(lock));                \
        else __bad_spinlock_type();                             \

} while (0)

so you can generate a (really) long branch that checks every known type that assigns an ID to a type build-time:

	if (TYPE_EQUAL(type, struct skb_head))
		type_id = 1;
	else if (TYPE_EQUAL(type, struct ))
		type_id = 2;
	...
	else
		type_id = UNKNOWN_TYPE;

despite this branch having hundreds of checks, the compiler will eliminate it at build time and only a single static type ID assignment remains.

this long branch could be auto-generated build-time (just like asm-offsets.c) in a maintainable way by putting a single "register type" line after every structure definition in global .h files:

REGISTER_TYPE(struct skb_head)

where REGISTER_TYPE(x) maps to nothing during normal kernel builds, but if a special flag is set it generates the type string into a special section:

#ifdef GENERATE_TYPE_REGISTRY

# define REGISTER_TYPE(x) \
	static char x __attribute__((section(".type.registry")) = #x;
#endif

so you can build and execute a special utility early during kernel build that prints out the generated code. (again, like asm-offsets.c)

it needs some thought, but this way it's quite possible to build-time map types to IDs.

Quoted 6 lines
Quoted 3 lines

but that there is a capable annotation method to reduce the amount of false negatives, in a gradual and managable way - down to zero if everything is annotated.

I'm not sure this could be achieved in a maintainable way, at least not without support from the compiler.

it's possible with gcc (for global types), just hidden a bit :-)

Ingo

#35 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 4 lines · Ingo Molnar

But it's not just about the amount of false negatives, but also about the overhead of scanning. You are concentrated on embedded systems with small RAM - but most of the testers will be running this with at last 1GB of RAM - which is _alot_ of memory to scan.

Most of this should be normally in page cache which doesn't need to be scanned?

There might be some extreme loads with a lot more kernel data, but they are probably rare.

-Andi
7

#36 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 4 lines · Ingo Molnar

For a GC a false negative is no big problem - it will reduce the efficiency of the GC a bit, but that's all. For leak detection, if we happen to have a persistent false pointer in .data (or any other persistently allocated memory), it may prevent the detection of a leak permanently - at least for that bootup. Statistically it could still be found on other systems, but it would be better to have a design that will eventually lead to having no false negatives.

But it's not just about the amount of false negatives, but also about the overhead of scanning. You are concentrated on embedded systems with small RAM - but most of the testers will be running this with at last 1GB of RAM - which is _alot_ of memory to scan.

It seems to me that most types with any pointers are fairly pointer-dense. There's not much point in trying to skip a couple of non-pointers nested among a dozen others; once you've worn the cost of pulling in the cache line there's not much else to worry about. The most useful thing is to distinguish between completely pointerless allocations and allocations which have pointers. Pointerless allocations are generally just data (strings, numbers, user data), and so are a waste of effort to scan, and possibly full of false pointers. In the kernel, you could probably do it by making it a property of slabs, assume all kmalloc allocations are pointerful (perhaps add GFP_POINTERLESS), and make sure all user-data pages are considered pointerless.

False pointers in kernel allocations can be avoided in a few ways. The first, obviously, is the make sure all memory is initialized to a known non-pointer value. The second is to ignore pointers which don't point near the start of an allocated region (possibly unsafe in the kernel, depending on the definition of "near"). You can get more sophisticated from there; the Boehm GC keeps tracks of things which look like pointers but turn out not to be (they don't point to allocated memory); it marks that memory as being unusable, so that the false pointer won't get mistaken for one later on, with the obvious risk that lots of false pointers can render large parts of your heap address space unusable.

In general, false pointers aren't a huge problem. They'll generally lead to a bounded number of allocations being unreported as leaks; its highly unlikely that a large heap graph will remain hidden from a leak checker forever; espectially since kernel pointers are fairly unlike other kinds of data (large enough to not be aliased to most normal integer values, don't look like strings, and there are no FP numbers in the kernel).

Quoted 2 lines

(But, if it's not possible to implement it in a sane manner then that's not an issue either - it's rather the false positives that must be avoided.)

There's some risk of false positives. You can imagine cases where the last reference to a block is transformed into a bus address, and in effect a piece of hardware holds it. You don't get to know about the pointer until the hardware gives it back. You might want a GFP_ROOT flag (or whatever), to mark a block as being always referenced in order to suppress these cases.

Quoted 6 lines

there are a couple of possibilities.

If the ID is string based then you dont even have to touch containr_of() calls - just generate the typename string via the "#y" stringification preprocessor directive, where 'y' is the second parameter of container_of(). [...]
it needs some thought, but this way it's quite possible to build-time map types to IDs.

This seems pretty over-engineered. I wouldn't go this far unless you're actually seeing performance/correctness problems, and a simple with/without pointers flag isn't enough. It also doesn't address the most troublesome source of false pointers: stacks. There is all sorts of junk lying around on stacks, and you can have an old dead pointer sitting there pinning old dead memory for a long time.

J

#37 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 6 lines · Jeremy Fitzhardinge

This seems pretty over-engineered. I wouldn't go this far unless you're actually seeing performance/correctness problems, and a simple with/without pointers flag isn't enough. It also doesn't address the most troublesome source of false pointers: stacks. There is all sorts of junk lying around on stacks, and you can have an old dead pointer sitting there pinning old dead memory for a long time.

in an earlier thread i suggested to not scan kernel stacks at all, but to delay the registration of new blocks to return-from-syscall time (via having a per-task list of newly allocated but not yet registered blocks). That way we dont get false positives for stuff that is on the kernel stack temporarily and then freed, and we correctly register newly allocated blocks as well.

Ingo

#40 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 6 lines · Ingo Molnar

* Catalin Marinas <[email protected]> wrote:

But it's not just about the amount of false negatives, but also about the overhead of scanning. You are concentrated on embedded systems with small RAM - but most of the testers will be running this with at last 1GB of RAM - which is _alot_ of memory to scan.

As Andi mentioned, it might not be a big issue since the page cache is not scanned.

Quoted 7 lines
Quoted 7 lines

The number of collisions would need to be investigated. On my system, there are 158 distinct sizeof values generated by container_of. Of this, 90 have at least two aliases (incoming pointer offsets). I'm not sure how many different structures are in the kernel but I can't find an easy (gcc magic) way to get a unique id for a type (apart from modifying all the container_of calls and add a 4th argument - maybe a string with the name of the type).

Looking at these collisions in more detail, from the above 90 only about 40 are real collisions that introduce new aliases. The others are container_of() usages on other members (task_struct has about 4 different aliases).

Quoted 4 lines

If the ID is string based then you dont even have to touch containr_of() calls - just generate the typename string via the "#y" stringification preprocessor directive, where 'y' is the second parameter of container_of().

Since the linker seems to be smart enough to eliminate string duplicates, a "const char *" can be used as a unique id (assuming that the container_of is always called with the type name and not "typeof").

Quoted 4 lines

there's another, much faster solution as well that assigns IDs build-time for globally visible types: the __builtin_types_compatible_p gcc extension to match the type against a global registry of types. I.e. here's what i use in PREEMPT_RT:

[...]

Quoted 2 lines

it needs some thought, but this way it's quite possible to build-time map types to IDs.

That's an interesting approach and it would work even with "typeof()" constructs.

Anyway, in both the incoming and outgoing pointers case, the type information needs to be associated with the allocated memory block. This would mean that all the kmalloc/kmem_cache_alloc etc. calls in the kernel have to be modified to pass the type information. Would such a (big) patch be acceptable for the kernel? The sizeof is the only information that could get close to type identification and is passed to these functions, though it has its risks.

Is it also worth the effort? With the large number of platforms Linux runs on, a leak would be spotted sooner or later.

Signature · 1 line
Catalin
#39 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Jeremy Fitzhardinge

Hi Jeremy,

It's good to hear some experience from the Valgrind world :-)

Quoted 8 lines · Jeremy Fitzhardinge
Quoted 5 lines · Ingo Molnar

But it's not just about the amount of false negatives, but also about the overhead of scanning. You are concentrated on embedded systems with small RAM - but most of the testers will be running this with at last 1GB of RAM - which is _alot_ of memory to scan.

It seems to me that most types with any pointers are fairly pointer-dense.

There seem to be many structures containing mostly data and only one or two list_head structures with pointers. Here only the list_head member would need to be scanned.

Quoted 3 lines

False pointers in kernel allocations can be avoided in a few ways. The first, obviously, is the make sure all memory is initialized to a known non-pointer value.

This is done already by the DEBUG_SLAB configuration.

Quoted 3 lines

The second is to ignore pointers which don't point
near the start of an allocated region (possibly unsafe in the kernel, depending on the definition of "near").

Kmemleak only accepts values that point to either the beginning of the allocated block or to one of its aliases (a offset from the beginning which is determined from the container_of() usages on that structure/member - most of the list usages). There is a discussion one whether to allow a value to point anywhere inside a block but I would need to investigate the risks.

Quoted 6 lines

You can get more sophisticated
from there; the Boehm GC keeps tracks of things which look like pointers but turn out not to be (they don't point to allocated memory); it marks that memory as being unusable, so that the false pointer won't get mistaken for one later on, with the obvious risk that lots of false pointers can render large parts of your heap address space unusable.

This would increase the overhead as in my tests around 15% of all the values scanned look like pointers (i.e. between PAGE_OFFSET and PAGE_OFFSET + ram_size).

Quoted 4 lines

There's some risk of false positives. You can imagine cases where the last reference to a block is transformed into a bus address, and in effect a piece of hardware holds it. You don't get to know about the pointer until the hardware gives it back.

This is pretty rare and you can easily tell kmemleak to ignore it.

Signature · 1 line
Catalin
#38 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 10 lines · Ingo Molnar
Quoted 6 lines · Jeremy Fitzhardinge

This seems pretty over-engineered. I wouldn't go this far unless you're actually seeing performance/correctness problems, and a simple with/without pointers flag isn't enough. It also doesn't address the most troublesome source of false pointers: stacks. There is all sorts of junk lying around on stacks, and you can have an old dead pointer sitting there pinning old dead memory for a long time.

Quoted 6 lines

in an earlier thread i suggested to not scan kernel stacks at all, but to delay the registration of new blocks to return-from-syscall time (via having a per-task list of newly allocated but not yet registered blocks). That way we dont get false positives for stuff that is on the kernel stack temporarily and then freed, and we correctly register newly allocated blocks as well.

I didn't have time to try this idea. However, the number of false positives doesn't seem to be increased (or they are only reported temporarily) if you don't scan the stacks at all (especially if you scan the memory at a relatively quiet time). That's why I added a config option for this.

The problem looks a bit more complicated for kernel threads as they always use the kernel stack.

Another idea would be to only scan the stacks of the sleeping tasks (and you could also get the frame pointer from the call to the schedule function).

Signature · 1 line
Catalin
#43 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Pekka Enberg

Hi Pekka,

Quoted 6 lines · Pekka Enberg
Quoted 2 lines · 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.

Can we fix this by looking for pointers to anywhere in the allocated memory block instead of just looking for the start?

I eventually got some spare time to continue the investigation on this.

I did some statistics with using a priority radix tree for pointer detection. This would eliminate the container_of hack and the memleak_padding calls. The statistics on qemu x86 (with just a prompt, no X or other applications started and unaligned values ignored) look like this:

allocated/detected pointers = 30433
detected via aliases = 6355

locations scanned = 1654781
pointer like values = 476145
values found in the radix tree = 157011
values found in the prio tree = 283283

Quoted 1 line

From the scanned values, 9.5% were found in the radix tree (current

implementation). There is a total of 28.8% values that look like pointers. This means that 67% of the values that look like pointers aren't pointing to any block (the other 33% are pointing to a block start or to certain offsets inside the block).

However, using a priority radix tree, 17% from the scanned values would match allocated blocks (almost double compared to the current method). 41% of the values that look like pointers would not be found pointing to a block or somewhere inside one. This means that an additional 26% of the values that look like pointers (compared to the radix tree method) have the potential of creating false negatives.

My opinion is not to implement the "anywhere inside a block" method as it would increase the risk of false negatives with a little benefit (removing some false positive notifications, probably less than 30).

To the other extreme is Ingo's suggestion of using exact type identification but I don't think this would be acceptable for the kernel as it would to modify all the memory alloc calls in the kernel to either pass an additional parameter (the type id) or another post-allocation call to kmemleak to update the id.

A compromise would be to use the "sizeof" type approximation for both incoming and outgoing pointers (kmemleak currently does this for incoming pointers). This would require an external tool for scanning all the structure definitions in the kernel and generate sizeof-pointer_offset pairs. It could also compare whether the size of the dereferenced outgoing pointer is the same as that of the detected memory block. I think this method would add the need of additional false-positives covering in the kernel.

Anyway, the current implementation (I'll update it for 2.6.17) detects real memory leaks. I suspect that a wide range of leaks would be covered if it is used on different platforms and different conditions.

Signature · 1 line
Catalin
#44 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 3 lines · Catalin Marinas

My opinion is not to implement the "anywhere inside a block" method as it would increase the risk of false negatives with a little benefit (removing some false positive notifications, probably less than 30).

agreed.

Quoted 5 lines

To the other extreme is Ingo's suggestion of using exact type identification but I don't think this would be acceptable for the kernel as it would to modify all the memory alloc calls in the kernel to either pass an additional parameter (the type id) or another post-allocation call to kmemleak to update the id.

passing in the type ID wouldnt be that bad and it would have other advantages as well: for example we could do strict type-checking of allocation size versus type-we-use-it-for.

As long as the conversion is gradual i think we could try this. I.e. we'd default to 'no ID passed', and in that case we would fall back to the size-based method and generate an ID out of the structure size.

Quoted 3 lines

Anyway, the current implementation (I'll update it for 2.6.17) detects real memory leaks. I suspect that a wide range of leaks would be covered if it is used on different platforms and different conditions.

btw., what leaks were found so far? I know about the ACPI one - any other ones?

Ingo

#45 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 11 lines · Ingo Molnar
Quoted 5 lines · Catalin Marinas

To the other extreme is Ingo's suggestion of using exact type identification but I don't think this would be acceptable for the kernel as it would to modify all the memory alloc calls in the kernel to either pass an additional parameter (the type id) or another post-allocation call to kmemleak to update the id.

passing in the type ID wouldnt be that bad and it would have other advantages as well: for example we could do strict type-checking of allocation size versus type-we-use-it-for.

There are valid places in the kernel where the allocated size is different from the type's one. That's why I added the memleak_padding().

Quoted 3 lines

As long as the conversion is gradual i think we could try this. I.e. we'd default to 'no ID passed', and in that case we would fall back to the size-based method and generate an ID out of the structure size.

OK, I'll try to add the infrastructure for type ids but default to sizeof initially.

Quoted 6 lines
Quoted 3 lines

Anyway, the current implementation (I'll update it for 2.6.17) detects real memory leaks. I suspect that a wide range of leaks would be covered if it is used on different platforms and different conditions.

btw., what leaks were found so far? I know about the ACPI one - any other ones?

There are two leaks reported in ACPI but I only posted a patch for one as I didn't have time to track the other (a reference count doesn't get to zero and the structure not freed).

There is another leak in legacy_init_iomem_resources() in arch/i386/setup.c (request_resource() fails but the memory is not freed - see the attached patch). I initially marked this as a false positive but it wasn't (I have to revisit the false positives).

Signature · 1 line
Catalin

Fix a memory leak in the i386 setup code

From: Catalin Marinas <[email protected]>

---

 arch/i386/kernel/setup.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)
arch/i386/kernel/setup.c +4 -1
index dd6b0e3..60f5d99 100644
@@ -1332,7 +1332,10 @@ legacy_init_iomem_resources(struct resou
 		res->start = e820.map[i].addr;
 		res->end = res->start + e820.map[i].size - 1;
 		res->flags = IORESOURCE_MEM | IORESOURCE_BUSY;
-		request_resource(&iomem_resource, res);
+		if (request_resource(&iomem_resource, res)) {
+			kfree(res);
+			continue;
+		}
 		if (e820.map[i].type == E820_RAM) {
 			/*
 			 *  We don't know which RAM region contains kernel data,
#46 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

In reply to Ingo Molnar
Quoted 6 lines · Ingo Molnar
Quoted 5 lines

To the other extreme is Ingo's suggestion of using exact type identification but I don't think this would be acceptable for the kernel as it would to modify all the memory alloc calls in the kernel to either pass an additional parameter (the type id) or another post-allocation call to kmemleak to update the id.

Quoted 7 lines

passing in the type ID wouldnt be that bad and it would have other advantages as well: for example we could do strict type-checking of allocation size versus type-we-use-it-for.

As long as the conversion is gradual i think we could try this. I.e. we'd default to 'no ID passed', and in that case we would fall back to the size-based method and generate an ID out of the structure size.

update: there's also a neat gcc extension trick suggested by Arjan:
__builtin_classify_type(). This converts types into integers!

Ingo

#47 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 2 lines · Ingo Molnar

update: there's also a neat gcc extension trick suggested by Arjan:
__builtin_classify_type(). This converts types into integers!

It's not really reliable as it doesn't distinguish well between types. All the structures, no matter what they contain, have the same id (which I think only refers to the fact that it is built-in type, pointer or structure, without differentiation).

The attached code gives the following results:

typeof(a) = 12, sizeof(a) = 136
typeof(b) = 12, sizeof(b) = 8
typeof(c) = 1, sizeof(c) = 4
typeof(d) = 1, sizeof(d) = 4
typeof(e) = 1, sizeof(e) = 4
typeof(f) = 1, sizeof(f) = 1
typeof(g) = 5, sizeof(g) = 4
typeof(h) = 5, sizeof(h) = 4

Signature · 1 line
Catalin

#include <stdio.h>

struct A {
	void *a;
	long b;
	char c[128];
};
struct B {
	long a;
	void *b;
};
enum C {
	a,
	b
};
#define PRINT_TYPE(val)							\
	printf("typeof(" #val ") = %d, sizeof(" #val ") = %d\n",	\
			__builtin_classify_type(val),			\
			sizeof(val))

int main()

{
	struct A a;
	struct B b;
	enum C c;
	int d;
	long e;
	char f;
	int *g;
	char *h;

	PRINT_TYPE(a);
	PRINT_TYPE(b);
	PRINT_TYPE(c);
	PRINT_TYPE(d);
	PRINT_TYPE(e);
	PRINT_TYPE(f);
	PRINT_TYPE(g);
	PRINT_TYPE(h);

	return 0;
}
#48 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 8 lines · Catalin Marinas
Quoted 2 lines · Ingo Molnar

update: there's also a neat gcc extension trick suggested by Arjan:
__builtin_classify_type(). This converts types into integers!

It's not really reliable as it doesn't distinguish well between types. All the structures, no matter what they contain, have the same id (which I think only refers to the fact that it is built-in type, pointer or structure, without differentiation).

__builtin_classify_type () doesn't give types unique ID, it only classifies them:

/* Values returned by __builtin_classify_type. */

enum type_class
{
no_type_class = -1,
void_type_class, integer_type_class, char_type_class, enumeral_type_class, boolean_type_class, pointer_type_class, reference_type_class, offset_type_class, real_type_class, complex_type_class, function_type_class, method_type_class, record_type_class, union_type_class, array_type_class, string_type_class, lang_type_class
};

All structures are given record_type_class, all unions union_type_class, all pointers pointer_type_class, etc.
That doesn't mean you can't use it in the kernel as additional source of type checking (in addition to e.g. sizeof and __alignof__).

Jakub

#49 lore raw

Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives

Quoted 12 lines · Jakub Jelinek
Quoted 8 lines · Catalin Marinas
Quoted 2 lines · Ingo Molnar

update: there's also a neat gcc extension trick suggested by Arjan:
__builtin_classify_type(). This converts types into integers!

It's not really reliable as it doesn't distinguish well between types. All the structures, no matter what they contain, have the same id (which I think only refers to the fact that it is built-in type, pointer or structure, without differentiation).

__builtin_classify_type () doesn't give types unique ID, it only classifies them:

[...]

Quoted 2 lines

All structures are given record_type_class, all unions union_type_class, all pointers pointer_type_class, etc.

Yes, I noticed this.

Quoted 2 lines

That doesn't mean you can't use it in the kernel as additional source of type checking (in addition to e.g. sizeof and __alignof__).

It is useful indeed, especially for identifying which types could actually be or contain pointers. However, with the current Linux API, the only information that can be passed to kmemleak via the alloc functions is the size information.

My plan is to post a kmemleak update (some bug-fixes) this weekend and get some wider testing (maybe in the -mm tree). Once people are happy with the current implementation, I'll try to add more precise type checking and introduce new functions (macros) like kmalloc_typed and kmem_cache_create_typed together with Ingo's algorithm for unique type ids.

There is another improvement that could be made to reduce the false negatives - allocate slab objects larger than the required size and change the offset every time the object is re-allocated. I think this would be useful not only for kmemleak but also for catching possible object alterations after it was re-allocated.

Signature · 1 line
Catalin