Re: [PATCH] list: add more extensive double add check

["Christian König" <ckoenig.leichtzumerken@gmail.com>]

Am 01.02.21 um 23:16 schrieb NeilBrown:
> On Mon, Feb 01 2021, Andy Shevchenko wrote:
>
>> On Mon, Feb 01, 2021 at 02:52:51PM +0100, Christian König wrote:
>>> Adding the same element to a linked list multiple times
>>> seems to be a rather common programming mistake. To debug
>>> those I've more than once written some code to check a
>>> linked list for duplicates.
>>>
>>> Since re-inventing the wheel over and over again is a bad
>>> idea this patch tries to add some common code which allows
>>> to check linked lists for duplicates while adding new
>>> elements.
>>>
>>> When list debugging is enabled we currently already check
>>> the previous and next element if they are identical to the
>>> new one. This patch now adds a configuration option to
>>> check N elements before and after the desired position.
>>>
>>> By default we still only test one item since testing more
>>> means quite a large CPU overhead. This can be overwritten
>>> on a per C file bases by defining DEBUG_LIST_DOUBLE_ADD
>>> before including list.h.
>> I'm not sure it is a good idea. Currently the implementation is *generic*.
>> You are customizing it w/o letting caller know.
>>
>> Create a derivative implementation and name it exlist (exclusive list) and use
>> whenever it makes sense.
>>
>> And I think if you are still pushing to modify generic one the default must be
>> 0 in order not altering current behaviour.
> I don't understand your complaint.
> The extra checks are also completely *generic*.  It can never make sense
> to add sometime to a list if it is already on the list.  All lists are
> exclusive lists.
> The code ALREADY tests if the inserted object is already present either
> side of the insert side of the insertion point.  This patch just extends
> it somewhat.

Correct, we are just checking for obvious bugs. The bigger problem is 
the usability and potentially performance impact.

In other words when you set this value to high the list_add() function 
will use so much time that the kernel thinks that the CPU is stuck. I've 
was already able to trigger this.

Would it be more acceptable if I drop the config option and only allow 
to override the check on a per C file basis?

> I myself have never had, or heard of, a bug due to double insertion so
> I'm no strongly in favour of this patch for that reason.
> But I *am* in favour of making the platform more resilient in general,
> and if others have experienced this sort of bug, then I'm in favour of
> make that easier to detect in future.

I have seen plenty of those. Especially when you implement state 
machines when a certain object needs to move from state to state 
triggered by external events.

For example it seems to be a common mistake to do a list_del_init, drop 
a lock and then assume a list_add should do it when you re-aquired the 
lock. In reality you have a very small window where a device interrupt 
could have already added the item to the list again between the locks.

Thanks,
Christian.

>
> NeilBrown
>
>
>>> A new kunit test is also added to the existing list tests
>>> which intentionally triggers the debug functionality.
>> -- 
>> With Best Regards,
>> Andy Shevchenko