[PATCH] Input: serio - fix O(n^2) complexity in serio_unregister_driver()

[PATCH] Input: serio - fix O(n^2) complexity in serio_unregister_driver()

[Mohamad Raizudeen]

The current implementation restarts the scan from the beginning after
each disconnection(goto start_over) because serio_disconnect_port() may
delete the current list entry. This results in O(n^2) worst case
behaviour.

Replace with a two-phase approach:

	1.Collect only top-level ports bound to the driver(skip those whose parent is also bound to the same driver) into a
	  temporary list.

	2.Process each collected port once, moving it back to serio_list first to maintain invariants expected by serio_destroy_port().

This eliminates the restart loop, reduces complexity from O(n^2) to O(n)
and avoids use-after-free by never collecting child ports separately.

Signed-off-by: Mohamad Raizudeen <raizudeen.kerneldev@gmail.com>
---
 drivers/input/serio/serio.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/drivers/input/serio/serio.c b/drivers/input/serio/serio.c
index 54dd26249b02..46b8faf1a46c 100644
--- a/drivers/input/serio/serio.c
+++ b/drivers/input/serio/serio.c
@@ -821,22 +821,27 @@ EXPORT_SYMBOL(__serio_register_driver);
 
 void serio_unregister_driver(struct serio_driver *drv)
 {
-	struct serio *serio;
+	struct serio *serio, *next;
+	LIST_HEAD(disconnect_list);
+
 
 	guard(mutex)(&serio_mutex);
 
 	drv->manual_bind = true;	/* so serio_find_driver ignores it */
 	serio_remove_pending_events(drv);
 
-start_over:
-	list_for_each_entry(serio, &serio_list, node) {
-		if (serio->drv == drv) {
-			serio_disconnect_port(serio);
-			serio_find_driver(serio);
-			/* we could've deleted some ports, restart */
-			goto start_over;
+	/*Collect all ports bound to this driver first*/
+	list_for_each_entry_safe(serio, next, &serio_list, node) {
+		if (serio->drv == drv && !(serio->parent && serio->parent->drv == drv)) {
+			list_move_tail(&serio->node, &disconnect_list);
 		}
 	}
+	
+	list_for_each_entry_safe(serio, next, &disconnect_list, node) {
+		list_move_tail(&serio->node, &serio_list);
+		serio_disconnect_port(serio);
+		serio_find_driver(serio);
+	}
 
 	driver_unregister(&drv->driver);
 }
-- 
2.43.0

Re: [PATCH] Input: serio - fix O(n^2) complexity in serio_unregister_driver()

[Dmitry Torokhov]

Hi Mohamad,

On Wed, Apr 08, 2026 at 09:58:47PM +0530, Mohamad Raizudeen wrote:
> The current implementation restarts the scan from the beginning after
> each disconnection(goto start_over) because serio_disconnect_port() may
> delete the current list entry. This results in O(n^2) worst case
> behaviour.

The "big O" notation only makes sense when numbers are big. Here we are
dealing with 6 serio ports max (1 KBC, 4xMUX, 1 Synaptics pass-through)
unless you have a serial port expander and hooked up a few ports there.
But still, the number if very limited.

> 
> Replace with a two-phase approach:
> 
> 	1.Collect only top-level ports bound to the driver(skip those whose parent is also bound to the same driver) into a
> 	  temporary list.

We do not have such setups at the moment, but what about parent's
parent's parent?

> 
> 	2.Process each collected port once, moving it back to serio_list first to maintain invariants expected by serio_destroy_port().
> 
> This eliminates the restart loop, reduces complexity from O(n^2) to O(n)
> and avoids use-after-free by never collecting child ports separately.

Could you explain more about the use-after-free scenario?

Thanks.

-- 
Dmitry

Re: [PATCH] Input: serio - fix O(n^2) complexity in serio_unregister_driver()

[Dmitry Torokhov]

On Wed, Apr 08, 2026 at 11:21:30PM +0530, Mohamad Raizudeen wrote:
> Hi Dmitry,

Please do not top-post.

> 
> *We do not have such setups at the moment, but what about parent's parent's
> parent?*
> You are right. Even though we don't have such setups today, let me explain
> why the patch works for arbitrary depth.
> 
> If we have three ports linked like A->B->C (A is top, B is child of A, C is
> child of B) and all use the same driver.

What happens if B uses different driver from A?

> 
> C sees its parent B is using the same driver, skip C
> B sees its parent A is using the same driver, skip B
> A has no parent using the same driver, collect A
> 
> When we disconnect A, it automatically destroys B and C. So all ports are
> cleaned up. The logic works for any number of levels.
> 
> * Could you explain more about the use-after-free scenario?*
> If we collected both A and B, disconnecting A would free B. Then when we
> try to process B from the list, we would use memory that is already freed
> that leads to crash. My patch avoids this by never collecting a port whose
> parent is also using the same driver.

But currently we restart scanning the list, so there won't be any stale
entries. How would we end up with touching freed memory?

Thanks.

-- 
Dmitry

Re: [PATCH] Input: serio - fix O(n^2) complexity in serio_unregister_driver()

[Mohamad Raizudeen]

On Wed, Apr 08, 2026 at 10:56:26AM -0700, Dmitry Torokhov wrote:
> On Wed, Apr 08, 2026 at 11:21:30PM +0530, Mohamad Raizudeen wrote:
> > Hi Dmitry,
> 
> Please do not top-post.
> 
> > 
> > *We do not have such setups at the moment, but what about parent's parent's
> > parent?*
> > You are right. Even though we don't have such setups today, let me explain
> > why the patch works for arbitrary depth.
> > 
> > If we have three ports linked like A->B->C (A is top, B is child of A, C is
> > child of B) and all use the same driver.
> 
> What happens if B uses different driver from A?
> 
> > 
> > C sees its parent B is using the same driver, skip C
> > B sees its parent A is using the same driver, skip B
> > A has no parent using the same driver, collect A
> > 
> > When we disconnect A, it automatically destroys B and C. So all ports are
> > cleaned up. The logic works for any number of levels.
> > 
> > * Could you explain more about the use-after-free scenario?*
> > If we collected both A and B, disconnecting A would free B. Then when we
> > try to process B from the list, we would use memory that is already freed
> > that leads to crash. My patch avoids this by never collecting a port whose
> > parent is also using the same driver.
> 
> But currently we restart scanning the list, so there won't be any stale
> entries. How would we end up with touching freed memory?
> 
> Thanks.
> 
> -- 
> Dmitry
Thank you for your careful review and for pointing out the mixed driver nestingscenario (A bound to driver X, B bound to driver Y, C bound to driver X). I completely missed that case.
You are right my 
My patch would collect both A and C, then disconnecting A would detroy B and C, leading to a use-after-free when C is later processed from the temporary list. The original goto approach handles this correctly by restarting the scan. 

I am sorry for sending a flawed patch. I will withdraw it.

I will try to deisign a better solution that works for all cases, includes mixed driver nesting, before submitting again.

Thank you again for your guidance.

Regards,
Mohamad Raizudeen.

Re: [PATCH] Input: serio - fix O(n^2) complexity in serio_unregister_driver()

[Dmitry Torokhov]

On Wed, Apr 08, 2026 at 11:49:48PM +0530, Mohamad Raizudeen wrote:
> On Wed, Apr 08, 2026 at 10:56:26AM -0700, Dmitry Torokhov wrote:
> > On Wed, Apr 08, 2026 at 11:21:30PM +0530, Mohamad Raizudeen wrote:
> > > Hi Dmitry,
> > 
> > Please do not top-post.
> > 
> > > 
> > > *We do not have such setups at the moment, but what about parent's parent's
> > > parent?*
> > > You are right. Even though we don't have such setups today, let me explain
> > > why the patch works for arbitrary depth.
> > > 
> > > If we have three ports linked like A->B->C (A is top, B is child of A, C is
> > > child of B) and all use the same driver.
> > 
> > What happens if B uses different driver from A?
> > 
> > > 
> > > C sees its parent B is using the same driver, skip C
> > > B sees its parent A is using the same driver, skip B
> > > A has no parent using the same driver, collect A
> > > 
> > > When we disconnect A, it automatically destroys B and C. So all ports are
> > > cleaned up. The logic works for any number of levels.
> > > 
> > > * Could you explain more about the use-after-free scenario?*
> > > If we collected both A and B, disconnecting A would free B. Then when we
> > > try to process B from the list, we would use memory that is already freed
> > > that leads to crash. My patch avoids this by never collecting a port whose
> > > parent is also using the same driver.
> > 
> > But currently we restart scanning the list, so there won't be any stale
> > entries. How would we end up with touching freed memory?
> > 
> > Thanks.
> > 
> > -- 
> > Dmitry
>

> Thank you for your careful review and for pointing out the mixed
> driver nestingscenario (A bound to driver X, B bound to driver Y, C
> bound to driver X). I completely missed that case. You are right my My
> patch would collect both A and C, then disconnecting A would detroy B
> and C, leading to a use-after-free when C is later processed from the
> temporary list. The original goto approach handles this correctly by
> restarting the scan. 
> 
> I am sorry for sending a flawed patch. I will withdraw it.
> 
> I will try to deisign a better solution that works for all cases,
> includes mixed driver nesting, before submitting again.

Appreciate you looking at the code but I do not think that particular
area needs addressing.

If you would like to improve the subsystem I would recommend you look
into making serio rely on the asynchronous driver probing, removing
custom handling of async port registration. This would allow
serio_register_port() to return errors and clean up bunch of things.

This will complicate attempt to synchronously switch serio protocols,
but I am willing to let go of that feature as I do not think anyone is
actually using this.

Thanks.

-- 
Dmitry