mm/kmemleak: Simplify kmemleak_cond_resched() & fix UAF
Subsystems (2)
cover mm/kmemleak: Simplify kmemleak_cond_resched() & fix UAF
It was found that a KASAN use-after-free error was reported in the kmemleak_scan() function. After further examination, it is believe that even though a reference is taken from the current object, it does not prevent the object pointed to by the next pointer from going away after a cond_resched(). So the heuristics is now changed to restart scanning from the beginning of object_list in case the current object is no longer in the object_list, i.e. OBJECT_ALLOCATED flag not set.
While making the change, I also simplify the current usage of kmemleak_cond_resched() to make it easier to understand.
Waiman Long (2):
mm/kmemleak: Simplify kmemleak_cond_resched() usage mm/kmemleak: Fix UAF bug in kmemleak_scan()
mm/kmemleak.c | 59 ++++++++++++++++++++------------------------------- 1 file changed, 23 insertions(+), 36 deletions(-)
Signature · 1 line
2.31.1
PATCH 1/2 mm/kmemleak: Simplify kmemleak_cond_resched() usage
The presence of a pinned argument and the 64k loop count make kmemleak_cond_resched() a bit more complex to read. The pinned argument is used only by first kmemleak_scan() loop.
Simplify the usage of kmemleak_cond_resched() by removing the pinned argument and always do a get_object()/put_object() sequence. In addition, the 64k loop is removed by using need_resched() to decide if kmemleak_cond_resched() should be called.
--- mm/kmemleak.c | 48 ++++++++++++------------------------------------ 1 file changed, 12 insertions(+), 36 deletions(-)
mm/kmemleak.c +12 -36
@@ -1463,22 +1463,17 @@ static void scan_gray_list(void)/* * Conditionally call resched() in a object iteration loop while making sure * that the given object won't go away without RCU read lock by performing a -* get_object() if !pinned. -* -* Return: false if can't do a cond_resched() due to get_object() failure -* true otherwise +* get_object() if necessaary. */ -static bool kmemleak_cond_resched (struct kmemleak_object *object,bool pinned) +static void kmemleak_cond_resched (struct kmemleak_object *object) { -if (!pinned && !get_object (object)) -return false; +if (!get_object (object)) +return ;/* Try next object */ rcu_read_unlock ();cond_resched ();rcu_read_lock (); -if (!pinned) -put_object (object); -return true; +put_object (object); }/*
@@ -1492,15 +1487,12 @@ static void kmemleak_scan(void)struct zone *zone;int __maybe_unused i;int new_leaks =0 ; -int loop_cnt =0 ; jiffies_last_scan = jiffies;/* prepare the kmemleak_object's */ rcu_read_lock ();list_for_each_entry_rcu (object, &object_list, object_list) { -bool obj_pinned = false; -raw_spin_lock_irq (&object->lock);#ifdef DEBUG /*
@@ -1526,19 +1518,13 @@ static void kmemleak_scan(void)/* reset the reference count (whiten the object) */ object->count =0 ; -if (color_gray (object) &&get_object (object)) { +if (color_gray (object) &&get_object (object))list_add_tail (&object->gray_list, &gray_list); - obj_pinned = true; - }raw_spin_unlock_irq (&object->lock); -/* -* Do a cond_resched() every 64k objects to avoid soft lockup. -*/ -if (!(++loop_cnt &0xffff ) && - !kmemleak_cond_resched (object, obj_pinned)) - loop_cnt--;/* Try again on next object */ +if (need_resched ()) +kmemleak_cond_resched (object); }rcu_read_unlock ();
@@ -1605,14 +1591,9 @@ static void kmemleak_scan(void)* scan and color them gray until the next scan. */ rcu_read_lock (); - loop_cnt =0 ;list_for_each_entry_rcu (object, &object_list, object_list) { -/* -* Do a cond_resched() every 64k objects to avoid soft lockup. -*/ -if (!(++loop_cnt &0xffff ) && - !kmemleak_cond_resched (object, false)) - loop_cnt--;/* Try again on next object */ +if (need_resched ()) +kmemleak_cond_resched (object);/* * This is racy but we can save the overhead of lock/unlock
@@ -1647,14 +1628,9 @@ static void kmemleak_scan(void)* Scanning result reporting. */ rcu_read_lock (); - loop_cnt =0 ;list_for_each_entry_rcu (object, &object_list, object_list) { -/* -* Do a cond_resched() every 64k objects to avoid soft lockup. -*/ -if (!(++loop_cnt &0xffff ) && - !kmemleak_cond_resched (object, false)) - loop_cnt--;/* Try again on next object */ +if (need_resched ()) +kmemleak_cond_resched (object);/* * This is racy but we can save the overhead of lock/unlock
Signature · 1 line
2.31.1
Re: [PATCH 1/2] mm/kmemleak: Simplify kmemleak_cond_resched() usage
Quoted 8 lines · Waiman Long
The presence of a pinned argument and the 64k loop count make
kmemleak_cond_resched()a bit more complex to read. The pinned argument is used only by firstkmemleak_scan()loop.Simplify the usage of
kmemleak_cond_resched()by removing the pinned argument and always do a get_object()/put_object() sequence. In addition, the 64k loop is removed by usingneed_resched()to decide ifkmemleak_cond_resched()should be called.
Not sure why we ended up with the 'pinned' argument, get/put_object() can be nested.
PATCH 2/2 mm/kmemleak: Fix UAF bug in kmemleak_scan()
In reply to Waiman LongCommit 6edda04ccc7c ("mm/kmemleak: prevent soft lockup in first object iteration loop of kmemleak_scan()") fixes soft lockup problem in kmemleak_scan() by periodically doing a cond_resched(). It does take a reference of the current object before doing it. Unfortunately, if the object has been deleted from the object_list, the next object pointed to by its next pointer may no longer be valid after coming back from cond_resched(). This can result in use-after-free and other nasty problem.
Fix this problem by restarting the object scan from the beginning of the object_list in case the object has been de-allocated after returning from cond_resched().
--- mm/kmemleak.c | 23 +++++++++++++++++------ 1 file changed, 17 insertions(+), 6 deletions(-)
mm/kmemleak.c +17 -6
@@ -1465,15 +1465,26 @@ static void scan_gray_list(void)* that the given object won't go away without RCU read lock by performing a * get_object() if necessaary. */ -static void kmemleak_cond_resched (struct kmemleak_object *object) +static void kmemleak_cond_resched (struct kmemleak_object **pobject) { -if (!get_object (object)) +struct kmemleak_object *obj = *pobject; + +if (!(obj->flags &OBJECT_ALLOCATED ) || !get_object (obj))return ;/* Try next object */ rcu_read_unlock ();cond_resched ();rcu_read_lock (); -put_object (object); +put_object (obj); + +/* +* In the unlikely event that the object had been de-allocated, we +* have to restart the scanning from the beginning of the object_list +* as the object pointed to by the next pointer may have been freed. +*/ +if (unlikely (!(obj->flags &OBJECT_ALLOCATED ))) + *pobject =list_entry_rcu (object_list.next, +typeof (*obj), object_list); }/*
@@ -1524,7 +1535,7 @@ static void kmemleak_scan(void)raw_spin_unlock_irq (&object->lock);if (need_resched ()) -kmemleak_cond_resched (object); +kmemleak_cond_resched (&object); }rcu_read_unlock ();
@@ -1593,7 +1604,7 @@ static void kmemleak_scan(void)rcu_read_lock ();list_for_each_entry_rcu (object, &object_list, object_list) {if (need_resched ()) -kmemleak_cond_resched (object); +kmemleak_cond_resched (&object);/* * This is racy but we can save the overhead of lock/unlock
@@ -1630,7 +1641,7 @@ static void kmemleak_scan(void)rcu_read_lock ();list_for_each_entry_rcu (object, &object_list, object_list) {if (need_resched ()) -kmemleak_cond_resched (object); +kmemleak_cond_resched (&object);/* * This is racy but we can save the overhead of lock/unlock
Signature · 1 line
2.31.1
Catalin Marinas
maintainerRe: [PATCH 2/2] mm/kmemleak: Fix UAF bug in kmemleak_scan()
Quoted 8 lines · Waiman Long
Commit
6edda04ccc7c("mm/kmemleak: prevent soft lockup in first object iteration loop ofkmemleak_scan()") fixes soft lockup problem inkmemleak_scan()by periodically doing acond_resched(). It does take a reference of the current object before doing it. Unfortunately, if the object has been deleted from theobject_list, the next object pointed to by its next pointer may no longer be valid after coming back fromcond_resched(). This can result in use-after-free and other nasty problem.
Ah, kmemleak_cond_resched() releases the rcu lock, so using list_for_each_entry_rcu() doesn't help.
Quoted 6 lines
mm/kmemleak.c +0
-0@@ -1465,15 +1465,26 @@ static void scan_gray_list(void)* that the given object won't go away without RCU read lock by performing a
mm/kmemleak.c static void scan_gray_list(void) · line 1473
Quoted 10 lines
mm/kmemleak.c +4
-2* get_object() if necessaary. */ -static void kmemleak_cond_resched (struct kmemleak_object *object) +static void kmemleak_cond_resched (struct kmemleak_object **pobject) { -if (!get_object (object)) +struct kmemleak_object *obj = *pobject; + +if (!(obj->flags &OBJECT_ALLOCATED ) || !get_object (obj))return ;/* Try next object */
I don't think we can rely on obj->flags without holding obj->lock. We do have a few WARN_ON() checks without the lock but in all other places the lock should be held.
Another potential issue with re-scanning is that the loop may never complete if it always goes from the beginning. Yet another problem with restarting is that we may count references to an object multiple times and get more false negatives.
I'd keep the OBJECT_ALLOCATED logic in the main kmemleak_scan() loop and retake the object->lock if cond_resched() was called (kmemleak_need_resched() returning true), check if it was freed and restart the loop. We could add a new OBJECT_SCANNED flag so that we skip such objects if we restarted the loop. The flag is reset during list preparation.
I wonder whether we actually need the cond_resched() in the first loop. It does take a lot of locks but it doesn't scan the objects. I had a patch around to remove the fine-grained locking in favour of the big kmemleak_lock, it would make this loop faster (not sure what happened to that patch, I need to dig it out).
Signature · 1 line
Catalin
Re: [PATCH 2/2] mm/kmemleak: Fix UAF bug in kmemleak_scan()
Quoted 23 lines · Catalin Marinas
Quoted 8 lines · Waiman Long
Commit
6edda04ccc7c("mm/kmemleak: prevent soft lockup in first object iteration loop ofkmemleak_scan()") fixes soft lockup problem inkmemleak_scan()by periodically doing acond_resched(). It does take a reference of the current object before doing it. Unfortunately, if the object has been deleted from theobject_list, the next object pointed to by its next pointer may no longer be valid after coming back fromcond_resched(). This can result in use-after-free and other nasty problem.Ah,
kmemleak_cond_resched()releases the rcu lock, so usinglist_for_each_entry_rcu()doesn't help.Quoted 11 lines
mm/kmemleak.c +1
-1@@ -1465,15 +1465,26 @@ static void scan_gray_list(void)* that the given object won't go away without RCU read lock by performing a * get_object() if necessaary. */ -static void kmemleak_cond_resched (struct kmemleak_object *object) +static void kmemleak_cond_resched (struct kmemleak_object **pobject) {
Quoted 8 lines
mm/kmemleak.c static void scan_gray_list(void) · line 1473
Quoted 5 lines
mm/kmemleak.c +3
-1-if (!get_object (object)) +struct kmemleak_object *obj = *pobject; + +if (!(obj->flags &OBJECT_ALLOCATED ) || !get_object (obj))return ;/* Try next object */ I don't think we can rely on
obj->flagswithout holdingobj->lock. We do have a fewWARN_ON()checks without the lock but in all other places the lock should be held.
Good point. It is just an optimistic check and it is OK to be wrong. I think I may need to use data_race() macro to signify that racing can happen and it is fine.
Quoted 13 lines
Another potential issue with re-scanning is that the loop may never complete if it always goes from the beginning. Yet another problem with restarting is that we may count references to an object multiple times and get more false negatives.
I'd keep the
OBJECT_ALLOCATEDlogic in the mainkmemleak_scan()loop and retake theobject->lockifcond_resched()was called (kmemleak_need_resched()returning true), check if it was freed and restart the loop. We could add a newOBJECT_SCANNEDflag so that we skip such objects if we restarted the loop. The flag is reset during list preparation.
Quoted 6 lines
I wonder whether we actually need the
cond_resched()in the first loop. It does take a lot of locks but it doesn't scan the objects. I had a patch around to remove the fine-grained locking in favour of the bigkmemleak_lock, it would make this loop faster (not sure what happened to that patch, I need to dig it out).
Thanks for the review. Another alternative way to handle that is to add an OBJECT_ANCHORED flag to indicate that this object shouldn't be deleted from the object list yet. Maybe also an OBJECT_DELETE_PENDING flag so that kmemleak_cond_resched() will delete it after returning from cond_resched() when set by another function that want to delete this object. All these checks and flag setting will be done with object lock held. How do you think?
Cheers,
Longman
Catalin Marinas
maintainerRe: [PATCH 2/2] mm/kmemleak: Fix UAF bug in kmemleak_scan()
Quoted 13 lines · Waiman Long
Quoted 12 lines · Catalin Marinas
Quoted 8 lines · Waiman Long
Commit
6edda04ccc7c("mm/kmemleak: prevent soft lockup in first object iteration loop ofkmemleak_scan()") fixes soft lockup problem inkmemleak_scan()by periodically doing acond_resched(). It does take a reference of the current object before doing it. Unfortunately, if the object has been deleted from theobject_list, the next object pointed to by its next pointer may no longer be valid after coming back fromcond_resched(). This can result in use-after-free and other nasty problem.Ah,
kmemleak_cond_resched()releases the rcu lock, so usinglist_for_each_entry_rcu()doesn't help.
[...]
Quoted 11 lines
Quoted 11 lines
Another potential issue with re-scanning is that the loop may never complete if it always goes from the beginning. Yet another problem with restarting is that we may count references to an object multiple times and get more false negatives.
I'd keep the
OBJECT_ALLOCATEDlogic in the mainkmemleak_scan()loop and retake theobject->lockifcond_resched()was called (kmemleak_need_resched()returning true), check if it was freed and restart the loop. We could add a newOBJECT_SCANNEDflag so that we skip such objects if we restarted the loop. The flag is reset during list preparation.
[...]
Quoted 7 lines
Thanks for the review. Another alternative way to handle that is to add an
OBJECT_ANCHOREDflag to indicate that this object shouldn't be deleted from the object list yet. Maybe also anOBJECT_DELETE_PENDINGflag so thatkmemleak_cond_resched()will delete it after returning fromcond_resched()when set by another function that want to delete this object. All these checks and flag setting will be done with object lock held. How do you think?
I think we are over-complicating this. The problems I see with deleting an object are that (1) only the object being deleted is locked (so that the corresponding memory block is not freed while scanning) and (2) kmemleak_cond_resched() releases the RCU lock briefly. A list_del_rcu() on the object next to the one being scanned (and locked) will leave the current object->next pointer dangling.
If we get rid of object->lock and just use kmemleak_lock instead, we can have a big lock around the scanning, released briefly in kmemleak_cond_resched(). A standard list_del() (not _rcu) could be run during the resched but it also updates the current object->next. Once the lock is re-acquired, the list traversal can continue safely. The current object cannot be freed due to get_object(). No need for restarting the loop.
I don't think we'd miss much in terms of scalability for a debug feature. Object freeing already takes the kmemleak_lock, it's just that during scanning it will have to wait for the scanning loop to release it. We might as well release it within the loop on each iteration.
So my proposal is to replace the rcu list traversal with the classic one and kmemleak_lock held (some functions like __find_and_get_object() will have to skip the lock). With this in place, we can subsequently remove all object->lock instances, just rely on the big lock (we do need to run lockdep if we do the latter separately, some nesting is a bit weird; my preference would be to remove the object->lock at the same time). We still need the rcu freeing in put_object() but for a completely different reason: the sl*b allocators don't like being called recursively, so we just use the RCU mechanism to free the kmemleak structures in a separate thread.
Signature · 1 line
Catalin
Re: [PATCH 2/2] mm/kmemleak: Fix UAF bug in kmemleak_scan()
Quoted 33 lines · Catalin Marinas
Quoted 12 lines · Waiman Long
Quoted 11 lines · Catalin Marinas
Quoted 8 lines · Waiman Long
Commit
6edda04ccc7c("mm/kmemleak: prevent soft lockup in first object iteration loop ofkmemleak_scan()") fixes soft lockup problem inkmemleak_scan()by periodically doing acond_resched(). It does take a reference of the current object before doing it. Unfortunately, if the object has been deleted from theobject_list, the next object pointed to by its next pointer may no longer be valid after coming back fromcond_resched(). This can result in use-after-free and other nasty problem.Ah,
kmemleak_cond_resched()releases the rcu lock, so usinglist_for_each_entry_rcu()doesn't help.[...]
Quoted 11 lines
Quoted 11 lines
Another potential issue with re-scanning is that the loop may never complete if it always goes from the beginning. Yet another problem with restarting is that we may count references to an object multiple times and get more false negatives.
I'd keep the
OBJECT_ALLOCATEDlogic in the mainkmemleak_scan()loop and retake theobject->lockifcond_resched()was called (kmemleak_need_resched()returning true), check if it was freed and restart the loop. We could add a newOBJECT_SCANNEDflag so that we skip such objects if we restarted the loop. The flag is reset during list preparation.[...]
Quoted 7 lines
Thanks for the review. Another alternative way to handle that is to add an
OBJECT_ANCHOREDflag to indicate that this object shouldn't be deleted from the object list yet. Maybe also anOBJECT_DELETE_PENDINGflag so thatkmemleak_cond_resched()will delete it after returning fromcond_resched()when set by another function that want to delete this object. All these checks and flag setting will be done with object lock held. How do you think?
Quoted 6 lines
I think we are over-complicating this. The problems I see with deleting an object are that (1) only the object being deleted is locked (so that the corresponding memory block is not freed while scanning) and (2)
kmemleak_cond_resched()releases the RCU lock briefly. Alist_del_rcu()on the object next to the one being scanned (and locked) will leave the currentobject->nextpointer dangling.
Yes, I believe that is the cause of the UAF error that I saw from KASAN.
Quoted 7 lines
If we get rid of
object->lockand just usekmemleak_lockinstead, we can have a big lock around the scanning, released briefly inkmemleak_cond_resched(). A standardlist_del()(not_rcu) could be run during the resched but it also updates the currentobject->next. Once the lock is re-acquired, the list traversal can continue safely. The current object cannot be freed due toget_object(). No need for restarting the loop.
The problem with a big lock (kmemleak_lock) is that we will be disabing interrupt for an extended period of time which is not ideal.
I have posted a v2 patch that drop the idea of restarting the loop. Instead, I just block the current object from being removed from the object_list to make sure its next pointer will point to a valid object.
Quoted 6 lines
I don't think we'd miss much in terms of scalability for a debug feature. Object freeing already takes the
kmemleak_lock, it's just that during scanning it will have to wait for the scanning loop to release it. We might as well release it within the loop on each iteration.
Quoted 10 lines
So my proposal is to replace the rcu list traversal with the classic one and
kmemleak_lockheld (some functions like__find_and_get_object()will have to skip the lock). With this in place, we can subsequently remove allobject->lockinstances, just rely on the big lock (we do need to run lockdep if we do the latter separately, some nesting is a bit weird; my preference would be to remove theobject->lockat the same time). We still need the rcu freeing input_object()but for a completely different reason: the sl*b allocators don't like being called recursively, so we just use the RCU mechanism to free the kmemleak structures in a separate thread.
That was what I thought about when you said you wanted to use a big lock instead of object->lock in the last email. As I said above, we can't hold the kmemleak_lock with interrupt disabled for an extended period of time especially if RT tasks are running. So we may need to release the lock frequently like per dozen objects or so. I believe we still need rcu_read_lock() just to be safe.
Cheers,
Longman
Quoted 1 line
Catalin Marinas
maintainerRe: [PATCH 2/2] mm/kmemleak: Fix UAF bug in kmemleak_scan()
Quoted 12 lines · Waiman Long
Quoted 11 lines · Catalin Marinas
Quoted 10 lines · Waiman Long
Quoted 9 lines · Catalin Marinas
Quoted 8 lines · Waiman Long
Commit
6edda04ccc7c("mm/kmemleak: prevent soft lockup in first object iteration loop ofkmemleak_scan()") fixes soft lockup problem inkmemleak_scan()by periodically doing acond_resched(). It does take a reference of the current object before doing it. Unfortunately, if the object has been deleted from theobject_list, the next object pointed to by its next pointer may no longer be valid after coming back fromcond_resched(). This can result in use-after-free and other nasty problem.
[...]
Quoted 10 lines
Quoted 7 lines
If we get rid of
object->lockand just usekmemleak_lockinstead, we can have a big lock around the scanning, released briefly inkmemleak_cond_resched(). A standardlist_del()(not_rcu) could be run during the resched but it also updates the currentobject->next. Once the lock is re-acquired, the list traversal can continue safely. The current object cannot be freed due toget_object(). No need for restarting the loop.The problem with a big lock (
kmemleak_lock) is that we will be disabing interrupt for an extended period of time which is not ideal.
We do this already during scanning - scan_block() takes the kmemleak_lock as this protects the rb tree. We just need to take this lock at a higher level in scan_gray_list() but we can still release it in the loop as before, at least each iteration (even multiple times in an iteration if scan_block() takes longer).
Quoted 3 lines
I have posted a v2 patch that drop the idea of restarting the loop. Instead, I just block the current object from being removed from the
object_listto make sure its next pointer will point to a valid object.
I haven't got around to look at that yet. Still trying to see if we can simplify the locking here without a significant effect on latency.
Quoted 16 lines
Quoted 5 lines
I don't think we'd miss much in terms of scalability for a debug feature. Object freeing already takes the
kmemleak_lock, it's just that during scanning it will have to wait for the scanning loop to release it. We might as well release it within the loop on each iteration.Quoted 10 lines
So my proposal is to replace the rcu list traversal with the classic one and
kmemleak_lockheld (some functions like__find_and_get_object()will have to skip the lock). With this in place, we can subsequently remove allobject->lockinstances, just rely on the big lock (we do need to run lockdep if we do the latter separately, some nesting is a bit weird; my preference would be to remove theobject->lockat the same time). We still need the rcu freeing input_object()but for a completely different reason: the sl*b allocators don't like being called recursively, so we just use the RCU mechanism to free the kmemleak structures in a separate thread.
Quoted 6 lines
That was what I thought about when you said you wanted to use a big lock instead of
object->lockin the last email. As I said above, we can't hold thekmemleak_lockwith interrupt disabled for an extended period of time especially if RT tasks are running. So we may need to release the lock frequently like per dozen objects or so. I believe we still needrcu_read_lock()just to be safe.
Yes, that's what I had in mind, release the lock very often but use a non-RCU traversal mechanism that updates list_head.next.
Yet another option would be to do a quick traversal at the beginning of kmemleak_scan() to only do a get_object(). Once the use_count is increased, they won't be freed. Of course, it needs another walk at the end of the scanning to do the put_object().
I'll have a look at your v2 as well, though most likely early in January.
Signature · 1 line
Catalin