diff mbox series

radix-tree: fix memory leak in radix_tree_insert

Message ID 20231211094840.642118-1-lizhi.xu@windriver.com
State New
Headers
Series radix-tree: fix memory leak in radix_tree_insert |

Commit Message

Lizhi Xu Dec. 11, 2023, 9:48 a.m. UTC 
  [Syz report]
BUG: memory leak
unreferenced object 0xffff88810bbf56d8 (size 576):
  comm "syz-executor250", pid 5051, jiffies 4294951219 (age 12.920s)
  hex dump (first 32 bytes):
    3c 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00  <...............
    f0 a9 2d 0c 81 88 ff ff f0 56 bf 0b 81 88 ff ff  ..-......V......
  backtrace:
    [<ffffffff81631398>] kmemleak_alloc_recursive include/linux/kmemleak.h:42 [inline]
    [<ffffffff81631398>] slab_post_alloc_hook mm/slab.h:766 [inline]
    [<ffffffff81631398>] slab_alloc_node mm/slub.c:3478 [inline]
    [<ffffffff81631398>] slab_alloc mm/slub.c:3486 [inline]
    [<ffffffff81631398>] __kmem_cache_alloc_lru mm/slub.c:3493 [inline]
    [<ffffffff81631398>] kmem_cache_alloc+0x298/0x430 mm/slub.c:3502
    [<ffffffff84b5094c>] radix_tree_node_alloc.constprop.0+0x7c/0x1a0 lib/radix-tree.c:276
    [<ffffffff84b524cf>] __radix_tree_create lib/radix-tree.c:624 [inline]
    [<ffffffff84b524cf>] radix_tree_insert+0x14f/0x360 lib/radix-tree.c:712
    [<ffffffff84ae105d>] qrtr_tx_wait net/qrtr/af_qrtr.c:277 [inline]
    [<ffffffff84ae105d>] qrtr_node_enqueue+0x57d/0x630 net/qrtr/af_qrtr.c:348
    [<ffffffff84ae26f6>] qrtr_bcast_enqueue+0x66/0xd0 net/qrtr/af_qrtr.c:891
    [<ffffffff84ae32d2>] qrtr_sendmsg+0x232/0x450 net/qrtr/af_qrtr.c:992
    [<ffffffff83ec3c32>] sock_sendmsg_nosec net/socket.c:730 [inline]
    [<ffffffff83ec3c32>] __sock_sendmsg+0x52/0xa0 net/socket.c:745
    [<ffffffff83ec3d7b>] sock_write_iter+0xfb/0x180 net/socket.c:1158
    [<ffffffff816961a7>] call_write_iter include/linux/fs.h:2020 [inline]
    [<ffffffff816961a7>] new_sync_write fs/read_write.c:491 [inline]
    [<ffffffff816961a7>] vfs_write+0x327/0x590 fs/read_write.c:584
    [<ffffffff816966fb>] ksys_write+0x13b/0x170 fs/read_write.c:637
    [<ffffffff84b6ddcf>] do_syscall_x64 arch/x86/entry/common.c:51 [inline]
    [<ffffffff84b6ddcf>] do_syscall_64+0x3f/0x110 arch/x86/entry/common.c:82
    [<ffffffff84c0008b>] entry_SYSCALL_64_after_hwframe+0x63/0x6b

[Analysis]
When creating child nodes, if not all child nodes used to store indexes are created,
so the child nodes created before the failure should be released.

Reported-and-tested-by: syzbot+006987d1be3586e13555@syzkaller.appspotmail.com
Signed-off-by: Lizhi Xu <lizhi.xu@windriver.com>
---
 lib/radix-tree.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)

Comments

kernel test robot Dec. 11, 2023, 11:16 p.m. UTC | #1 
Hi Lizhi,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-nonmm-unstable]
[also build test WARNING on linus/master v6.7-rc5 next-20231211]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Lizhi-Xu/radix-tree-fix-memory-leak-in-radix_tree_insert/20231211-174951
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20231211094840.642118-1-lizhi.xu%40windriver.com
patch subject: [PATCH] radix-tree: fix memory leak in radix_tree_insert
config: i386-randconfig-061-20231212 (https://download.01.org/0day-ci/archive/20231212/202312120651.92GGXeX4-lkp@intel.com/config)
compiler: gcc-7 (Ubuntu 7.5.0-6ubuntu2) 7.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20231212/202312120651.92GGXeX4-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202312120651.92GGXeX4-lkp@intel.com/

sparse warnings: (new ones prefixed by >>)
   lib/radix-tree.c:266:36: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *nodes @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:266:36: sparse:     expected struct xa_node *nodes
   lib/radix-tree.c:266:36: sparse:     got struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:284:29: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node [noderef] __rcu *parent @@     got struct xa_node *parent @@
   lib/radix-tree.c:284:29: sparse:     expected struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:284:29: sparse:     got struct xa_node *parent
   lib/radix-tree.c:344:38: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node [noderef] __rcu *parent @@     got struct xa_node *nodes @@
   lib/radix-tree.c:344:38: sparse:     expected struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:344:38: sparse:     got struct xa_node *nodes
   lib/radix-tree.c:446:54: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node [noderef] __rcu *parent @@     got struct xa_node *node @@
   lib/radix-tree.c:446:54: sparse:     expected struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:446:54: sparse:     got struct xa_node *node
   lib/radix-tree.c:558:24: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *parent @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:558:24: sparse:     expected struct xa_node *parent
   lib/radix-tree.c:558:24: sparse:     got struct xa_node [noderef] __rcu *parent
>> lib/radix-tree.c:653:28: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *pn @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:653:28: sparse:     expected struct xa_node *pn
   lib/radix-tree.c:653:28: sparse:     got struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:687:31: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *[assigned] child @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:687:31: sparse:     expected struct xa_node *[assigned] child
   lib/radix-tree.c:687:31: sparse:     got struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:962:22: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *node @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:962:22: sparse:     expected struct xa_node *node
   lib/radix-tree.c:962:22: sparse:     got struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:1022:22: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *node @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:1022:22: sparse:     expected struct xa_node *node
   lib/radix-tree.c:1022:22: sparse:     got struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:1542:38: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *[assigned] node @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:1542:38: sparse:     expected struct xa_node *[assigned] node
   lib/radix-tree.c:1542:38: sparse:     got struct xa_node [noderef] __rcu *parent
   lib/radix-tree.c:1602:28: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *nodes @@     got struct xa_node [noderef] __rcu *parent @@
   lib/radix-tree.c:1602:28: sparse:     expected struct xa_node *nodes
   lib/radix-tree.c:1602:28: sparse:     got struct xa_node [noderef] __rcu *parent

vim +653 lib/radix-tree.c

   581	
   582	/**
   583	 *	__radix_tree_create	-	create a slot in a radix tree
   584	 *	@root:		radix tree root
   585	 *	@index:		index key
   586	 *	@nodep:		returns node
   587	 *	@slotp:		returns slot
   588	 *
   589	 *	Create, if necessary, and return the node and slot for an item
   590	 *	at position @index in the radix tree @root.
   591	 *
   592	 *	Until there is more than one item in the tree, no nodes are
   593	 *	allocated and @root->xa_head is used as a direct slot instead of
   594	 *	pointing to a node, in which case *@nodep will be NULL.
   595	 *
   596	 *	Returns -ENOMEM, or 0 for success.
   597	 */
   598	static int __radix_tree_create(struct radix_tree_root *root,
   599			unsigned long index, struct radix_tree_node **nodep,
   600			void __rcu ***slotp)
   601	{
   602		struct radix_tree_node *node = NULL, *child;
   603		void __rcu **slot = (void __rcu **)&root->xa_head;
   604		unsigned long maxindex;
   605		unsigned int shift, offset = 0, mmshift = 0;
   606		unsigned long max = index;
   607		gfp_t gfp = root_gfp_mask(root);
   608		int ret;
   609	
   610		shift = radix_tree_load_root(root, &child, &maxindex);
   611	
   612		/* Make sure the tree is high enough.  */
   613		if (max > maxindex) {
   614			int error = radix_tree_extend(root, gfp, max, shift);
   615			if (error < 0)
   616				return error;
   617			shift = error;
   618			mmshift = error;
   619			child = rcu_dereference_raw(root->xa_head);
   620		}
   621	
   622		while (shift > 0) {
   623			shift -= RADIX_TREE_MAP_SHIFT;
   624			if (child == NULL) {
   625				/* Have to add a child node.  */
   626				child = radix_tree_node_alloc(gfp, node, root, shift,
   627								offset, 0, 0);
   628				if (!child) {
   629					 ret = -ENOMEM;
   630					 goto freec;
   631				}
   632				rcu_assign_pointer(*slot, node_to_entry(child));
   633				if (node)
   634					node->count++;
   635			} else if (!radix_tree_is_internal_node(child))
   636				break;
   637	
   638			/* Go a level down */
   639			node = entry_to_node(child);
   640			offset = radix_tree_descend(node, &child, index);
   641			slot = &node->slots[offset];
   642		}
   643	
   644		if (nodep)
   645			*nodep = node;
   646		if (slotp)
   647			*slotp = slot;
   648		return 0;
   649	freec:
   650		if (mmshift > 0) {
   651			struct radix_tree_node *pn;
   652			while (shift < mmshift && node) {
 > 653				pn = node->parent;
   654				radix_tree_node_rcu_free(&node->rcu_head);
   655				shift += RADIX_TREE_MAP_SHIFT;
   656				node = pn;
   657			}
   658		}
   659		return ret;
   660	}
   661
Lizhi Xu Dec. 13, 2023, 3:25 a.m. UTC | #2 
On Tue, 12 Dec 2023 07:16:50 +0800, kernel test robot <lkp@intel.com> wrote:
> kernel test robot noticed the following build warnings:
>    lib/radix-tree.c:558:24: sparse:     got struct xa_node [noderef] __rcu *parent
> >> lib/radix-tree.c:653:28: sparse: sparse: incorrect type in assignment (different address spaces) @@     expected struct xa_node *pn @@     got struct xa_node [noderef] __rcu *parent @@
>    lib/radix-tree.c:653:28: sparse:     expected struct xa_node *pn
>   651			struct radix_tree_node *pn;
>   652			while (shift < mmshift && node) {
> > 653				pn = node->parent;
It can be clarified here that node->parent is the type just alloced as 
"struct radix_tree node *", so there is no need to use cast type conversion,  
Please ignore this warning.

BR,
Lizhi
diff mbox series

Patch

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index a89df8afa510..c5caf5b7523a 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -616,9 +616,10 @@  static int __radix_tree_create(struct radix_tree_root *root,
 	struct radix_tree_node *node = NULL, *child;
 	void __rcu **slot = (void __rcu **)&root->xa_head;
 	unsigned long maxindex;
-	unsigned int shift, offset = 0;
+	unsigned int shift, offset = 0, mmshift = 0;
 	unsigned long max = index;
 	gfp_t gfp = root_gfp_mask(root);
+	int ret;
 
 	shift = radix_tree_load_root(root, &child, &maxindex);
 
@@ -628,6 +629,7 @@  static int __radix_tree_create(struct radix_tree_root *root,
 		if (error < 0)
 			return error;
 		shift = error;
+		mmshift = error;
 		child = rcu_dereference_raw(root->xa_head);
 	}
 
@@ -637,8 +639,10 @@  static int __radix_tree_create(struct radix_tree_root *root,
 			/* Have to add a child node.  */
 			child = radix_tree_node_alloc(gfp, node, root, shift,
 							offset, 0, 0);
-			if (!child)
-				return -ENOMEM;
+			if (!child) {
+				 ret = -ENOMEM;
+				 goto freec;
+			}
 			rcu_assign_pointer(*slot, node_to_entry(child));
 			if (node)
 				node->count++;
@@ -656,6 +660,17 @@  static int __radix_tree_create(struct radix_tree_root *root,
 	if (slotp)
 		*slotp = slot;
 	return 0;
+freec:
+	if (mmshift > 0) {
+		struct radix_tree_node *pn;
+		while (shift < mmshift && node) {
+			pn = node->parent;
+			radix_tree_node_rcu_free(&node->rcu_head);
+			shift += RADIX_TREE_MAP_SHIFT;
+			node = pn;
+		}
+	}
+	return ret;
 }
 
 /*