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