[PATCH] media: v4l2-dev: optimize device node number allocation logic

[PATCH] media: v4l2-dev: optimize device node number allocation logic

[Haipeng Jiang]

Refactor the device node number selection to:
1. Avoid redundant search in auto-allocation case (nr < 0)
2. Simplify error handling with unified boundary check
3. Maintain identical behavior for both auto and specific allocation

For automatic allocation (start = 0):
- Only search [0, minor_cnt) once
- Return -ENFILE if no free node found

For specific node request (start > 0):
- First search [start, minor_cnt)
- Then search [0, start) if first fails
- Return -ENFILE if both ranges have no free node

Signed-off-by: Haipeng Jiang <haipengjiang@foxmail.com>
---
 drivers/media/v4l2-core/v4l2-dev.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/drivers/media/v4l2-core/v4l2-dev.c b/drivers/media/v4l2-core/v4l2-dev.c
index c369235113d9..23d04c890e6b 100644
--- a/drivers/media/v4l2-core/v4l2-dev.c
+++ b/drivers/media/v4l2-core/v4l2-dev.c
@@ -907,6 +907,7 @@ int __video_register_device(struct video_device *vdev,
 	int ret;
 	int minor_offset = 0;
 	int minor_cnt = VIDEO_NUM_DEVICES;
+	int start;
 	const char *name_base;
 
 	/* A minor value of -1 marks this video device as never
@@ -994,10 +995,11 @@ int __video_register_device(struct video_device *vdev,
 
 	/* Pick a device node number */
 	mutex_lock(&videodev_lock);
-	nr = devnode_find(vdev, nr == -1 ? 0 : nr, minor_cnt);
-	if (nr == minor_cnt)
-		nr = devnode_find(vdev, 0, minor_cnt);
-	if (nr == minor_cnt) {
+	start = (nr < 0) ? 0 : nr;
+	nr = devnode_find(vdev, start, minor_cnt);
+	if (nr == minor_cnt && start != 0)
+		nr = devnode_find(vdev, 0, start);
+	if (nr == (start != 0 ? start : minor_cnt)) {
 		pr_err("could not get a free device node number\n");
 		mutex_unlock(&videodev_lock);
 		return -ENFILE;
-- 
2.46.2.windows.1

Re: [PATCH] media: v4l2-dev: optimize device node number allocation logic

[Ricardo Ribalda]

Hi Haipeng

Thanks for the patch.

Please note that devnode_find should be a very efficient bit
operation, it is most of the time done in O(1) and not in O(N) despide
it would sound otherwise.

If you want to refactor the code, I would suggest modifying
devnode_find() instead. Something like this (untested)

diff --git a/drivers/media/v4l2-core/v4l2-dev.c
b/drivers/media/v4l2-core/v4l2-dev.c
index c369235113d9..400240afb85d 100644
--- a/drivers/media/v4l2-core/v4l2-dev.c
+++ b/drivers/media/v4l2-core/v4l2-dev.c
@@ -138,10 +138,20 @@ static inline void devnode_clear(struct
video_device *vdev)
        clear_bit(vdev->num, devnode_bits(vdev->vfl_type));
 }

-/* Try to find a free device node number in the range [from, to> */
+/* Try to find a free device node number in the range [from, to> , wrapping */
 static inline int devnode_find(struct video_device *vdev, int from, int to)
 {
-       return find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
+       int ret;
+
+       ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
+       if (ret == to && from == 0)
+               return -ENOSPC;
+
+       ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), from, 0);
+       if (ret == from)
+               return -ENOSPC;
+
+       return ret;
 }

 struct video_device *video_device_alloc(void)
@@ -994,10 +1004,8 @@ int __video_register_device(struct video_device *vdev,

        /* Pick a device node number */
        mutex_lock(&videodev_lock);
-       nr = devnode_find(vdev, nr == -1 ? 0 : nr, minor_cnt);
-       if (nr == minor_cnt)
-               nr = devnode_find(vdev, 0, minor_cnt);
-       if (nr == minor_cnt) {
+       nr = devnode_find(vdev, (nr == -1) ? 0 : nr, minor_cnt);
+       if (nr == -ENOSPC) {
                pr_err("could not get a free device node number\n");
                mutex_unlock(&videodev_lock);
                return -ENFILE;


Regards

On Wed, 11 Jun 2025 at 16:06, Haipeng Jiang <haipengjiang@foxmail.com> wrote:
>
> Refactor the device node number selection to:
> 1. Avoid redundant search in auto-allocation case (nr < 0)
> 2. Simplify error handling with unified boundary check
> 3. Maintain identical behavior for both auto and specific allocation
>
> For automatic allocation (start = 0):
> - Only search [0, minor_cnt) once
> - Return -ENFILE if no free node found
>
> For specific node request (start > 0):
> - First search [start, minor_cnt)
> - Then search [0, start) if first fails
> - Return -ENFILE if both ranges have no free node
>
> Signed-off-by: Haipeng Jiang <haipengjiang@foxmail.com>
> ---
>  drivers/media/v4l2-core/v4l2-dev.c | 10 ++++++----
>  1 file changed, 6 insertions(+), 4 deletions(-)
>
> diff --git a/drivers/media/v4l2-core/v4l2-dev.c b/drivers/media/v4l2-core/v4l2-dev.c
> index c369235113d9..23d04c890e6b 100644
> --- a/drivers/media/v4l2-core/v4l2-dev.c
> +++ b/drivers/media/v4l2-core/v4l2-dev.c
> @@ -907,6 +907,7 @@ int __video_register_device(struct video_device *vdev,
>         int ret;
>         int minor_offset = 0;
>         int minor_cnt = VIDEO_NUM_DEVICES;
> +       int start;
>         const char *name_base;
>
>         /* A minor value of -1 marks this video device as never
> @@ -994,10 +995,11 @@ int __video_register_device(struct video_device *vdev,
>
>         /* Pick a device node number */
>         mutex_lock(&videodev_lock);
> -       nr = devnode_find(vdev, nr == -1 ? 0 : nr, minor_cnt);
> -       if (nr == minor_cnt)
> -               nr = devnode_find(vdev, 0, minor_cnt);
> -       if (nr == minor_cnt) {
> +       start = (nr < 0) ? 0 : nr;
> +       nr = devnode_find(vdev, start, minor_cnt);
> +       if (nr == minor_cnt && start != 0)
> +               nr = devnode_find(vdev, 0, start);
> +       if (nr == (start != 0 ? start : minor_cnt)) {
>                 pr_err("could not get a free device node number\n");
>                 mutex_unlock(&videodev_lock);
>                 return -ENFILE;
> --
> 2.46.2.windows.1
>


-- 
Ricardo Ribalda

[PATCH v2] media: v4l2-dev: implement wrap-around search in devnode_find

[Haipeng Jiang]

Moved wrap-around search logic into devnode_find() to avoid redundant
lookups when nr=0. Returns -ENOSPC when device node numbers are
exhausted.

Signed-off-by: Haipeng Jiang <haipengjiang@foxmail.com>
---
Changes in v2:
- Implemented wrap-around search logic directly in devnode_find()

 drivers/media/v4l2-core/v4l2-dev.c | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

diff --git a/drivers/media/v4l2-core/v4l2-dev.c b/drivers/media/v4l2-core/v4l2-dev.c
index c369235113d9..39e175d529a4 100644
--- a/drivers/media/v4l2-core/v4l2-dev.c
+++ b/drivers/media/v4l2-core/v4l2-dev.c
@@ -138,10 +138,22 @@ static inline void devnode_clear(struct video_device *vdev)
 	clear_bit(vdev->num, devnode_bits(vdev->vfl_type));
 }
 
-/* Try to find a free device node number in the range [from, to> */
+/* Try to find a free device node number in the range [from, to>, wrapping */
 static inline int devnode_find(struct video_device *vdev, int from, int to)
 {
-	return find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
+	int ret;
+
+	ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
+
+	if (ret == to) {
+		if (from == 0)
+			return -ENOSPC;
+		ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), from, 0);
+		if (ret == from)
+			return -ENOSPC;
+	}
+
+	return ret;
 }
 
 struct video_device *video_device_alloc(void)
@@ -995,9 +1007,7 @@ int __video_register_device(struct video_device *vdev,
 	/* Pick a device node number */
 	mutex_lock(&videodev_lock);
 	nr = devnode_find(vdev, nr == -1 ? 0 : nr, minor_cnt);
-	if (nr == minor_cnt)
-		nr = devnode_find(vdev, 0, minor_cnt);
-	if (nr == minor_cnt) {
+	if (nr == -ENOSPC) {
 		pr_err("could not get a free device node number\n");
 		mutex_unlock(&videodev_lock);
 		return -ENFILE;
-- 
2.46.2.windows.1

Re: [PATCH v2] media: v4l2-dev: implement wrap-around search in devnode_find

[Ricardo Ribalda]

On Sat, 14 Jun 2025 at 08:35, Haipeng Jiang <haipengjiang@foxmail.com> wrote:
>
> Moved wrap-around search logic into devnode_find() to avoid redundant
> lookups when nr=0. Returns -ENOSPC when device node numbers are
> exhausted.
>
Reviewed-by: Ricardo Ribalda <ribalda@chromium.org>
> Signed-off-by: Haipeng Jiang <haipengjiang@foxmail.com>
> ---
> Changes in v2:
> - Implemented wrap-around search logic directly in devnode_find()
>
>  drivers/media/v4l2-core/v4l2-dev.c | 20 +++++++++++++++-----
>  1 file changed, 15 insertions(+), 5 deletions(-)
>
> diff --git a/drivers/media/v4l2-core/v4l2-dev.c b/drivers/media/v4l2-core/v4l2-dev.c
> index c369235113d9..39e175d529a4 100644
> --- a/drivers/media/v4l2-core/v4l2-dev.c
> +++ b/drivers/media/v4l2-core/v4l2-dev.c
> @@ -138,10 +138,22 @@ static inline void devnode_clear(struct video_device *vdev)
>         clear_bit(vdev->num, devnode_bits(vdev->vfl_type));
>  }
>
> -/* Try to find a free device node number in the range [from, to> */
> +/* Try to find a free device node number in the range [from, to>, wrapping */
>  static inline int devnode_find(struct video_device *vdev, int from, int to)
>  {
> -       return find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
> +       int ret;
> +
> +       ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
> +
> +       if (ret == to) {
> +               if (from == 0)
> +                       return -ENOSPC;
> +               ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), from, 0);
> +               if (ret == from)
> +                       return -ENOSPC;
> +       }
> +
> +       return ret;
>  }
>

The code is correct, but I would have implemented it a bit differently
to avoid indentation level.
Probably nitpicking.

ret = find_next_zero()
if (ret != to)
  return ret;
if (from == 0)
   return -ENOSPC;
ret = find_next_zero()
if (ret == from)
  return -ENOSPC
return ret;

As I previously said, find_next_zero_bit is really fast, so there is
no big harm to run it twice even if it is not needed. Up to the
maintainer to decide if they need the patch or not :)

Thanks



>  struct video_device *video_device_alloc(void)
> @@ -995,9 +1007,7 @@ int __video_register_device(struct video_device *vdev,
>         /* Pick a device node number */
>         mutex_lock(&videodev_lock);
>         nr = devnode_find(vdev, nr == -1 ? 0 : nr, minor_cnt);
> -       if (nr == minor_cnt)
> -               nr = devnode_find(vdev, 0, minor_cnt);
> -       if (nr == minor_cnt) {
> +       if (nr == -ENOSPC) {
>                 pr_err("could not get a free device node number\n");
>                 mutex_unlock(&videodev_lock);
>                 return -ENFILE;
> --
> 2.46.2.windows.1
>


-- 
Ricardo Ribalda

Re: [PATCH v2] media: v4l2-dev: implement wrap-around search in devnode_find

[Hans Verkuil]

On 16/06/2025 08:40, Ricardo Ribalda wrote:
> On Sat, 14 Jun 2025 at 08:35, Haipeng Jiang <haipengjiang@foxmail.com> wrote:
>>
>> Moved wrap-around search logic into devnode_find() to avoid redundant
>> lookups when nr=0. Returns -ENOSPC when device node numbers are
>> exhausted.
>>
> Reviewed-by: Ricardo Ribalda <ribalda@chromium.org>
>> Signed-off-by: Haipeng Jiang <haipengjiang@foxmail.com>
>> ---
>> Changes in v2:
>> - Implemented wrap-around search logic directly in devnode_find()
>>
>>  drivers/media/v4l2-core/v4l2-dev.c | 20 +++++++++++++++-----
>>  1 file changed, 15 insertions(+), 5 deletions(-)
>>
>> diff --git a/drivers/media/v4l2-core/v4l2-dev.c b/drivers/media/v4l2-core/v4l2-dev.c
>> index c369235113d9..39e175d529a4 100644
>> --- a/drivers/media/v4l2-core/v4l2-dev.c
>> +++ b/drivers/media/v4l2-core/v4l2-dev.c
>> @@ -138,10 +138,22 @@ static inline void devnode_clear(struct video_device *vdev)
>>         clear_bit(vdev->num, devnode_bits(vdev->vfl_type));
>>  }
>>
>> -/* Try to find a free device node number in the range [from, to> */
>> +/* Try to find a free device node number in the range [from, to>, wrapping */
>>  static inline int devnode_find(struct video_device *vdev, int from, int to)
>>  {
>> -       return find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
>> +       int ret;
>> +
>> +       ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), to, from);
>> +
>> +       if (ret == to) {
>> +               if (from == 0)
>> +                       return -ENOSPC;
>> +               ret = find_next_zero_bit(devnode_bits(vdev->vfl_type), from, 0);
>> +               if (ret == from)
>> +                       return -ENOSPC;
>> +       }
>> +
>> +       return ret;
>>  }
>>
> 
> The code is correct, but I would have implemented it a bit differently
> to avoid indentation level.
> Probably nitpicking.
> 
> ret = find_next_zero()
> if (ret != to)
>   return ret;
> if (from == 0)
>    return -ENOSPC;
> ret = find_next_zero()
> if (ret == from)
>   return -ENOSPC
> return ret;
> 
> As I previously said, find_next_zero_bit is really fast, so there is
> no big harm to run it twice even if it is not needed. Up to the
> maintainer to decide if they need the patch or not :)

I don't see a compelling reason to take this patch. It is a very slight improvement
if you run out of available minor numbers, which is exceedingly rare. And you have
bigger problems if you hit that.

So I'm dropping this patch, it just makes the code longer without any real benefits.

Sorry,

	Hans

> 
> Thanks
> 
> 
> 
>>  struct video_device *video_device_alloc(void)
>> @@ -995,9 +1007,7 @@ int __video_register_device(struct video_device *vdev,
>>         /* Pick a device node number */
>>         mutex_lock(&videodev_lock);
>>         nr = devnode_find(vdev, nr == -1 ? 0 : nr, minor_cnt);
>> -       if (nr == minor_cnt)
>> -               nr = devnode_find(vdev, 0, minor_cnt);
>> -       if (nr == minor_cnt) {
>> +       if (nr == -ENOSPC) {
>>                 pr_err("could not get a free device node number\n");
>>                 mutex_unlock(&videodev_lock);
>>                 return -ENFILE;
>> --
>> 2.46.2.windows.1
>>
> 
>