As requested by Peter at [1], this patchset drops the ROBUST_LIST_LIMIT. This is
achieve by simply rewriting the processed list element ->next to point to the
head->list address, destroying the linked list to avoid any circular list.

Patches 2-4 create selftest for robust lists. Patch 2/4 creates helpful
macros for futex selftests and 3/4 creates a bunch of tests for the interface (as I
had submitted before at [2]).

Patch 4/4 is used to validate the changes made at 1/4:
 - That the kernel can now handle a lock that is allocated in an index bigger than
  ROBUST_LIST_LIMIT
 - That the kernel can still handle circular linked lists.

[1] https://lore.kernel.org/lkml/20241219171344.GA26279@noisy.programming.kicks-ass.net/
[2] https://lore.kernel.org/lkml/20241212210436.112076-1-andrealmeid@igalia.com/

Changelog:

- Rebased on top of tip/locking/urgent (for 6.14-rc1)
v1: https://lore.kernel.org/lkml/20250110200508.353290-1-andrealmeid@igalia.com/#t

André Almeida (4):
  futex: Drop ROBUST_LIST_LIMIT
  selftests/futex: Add ASSERT_ macros
  selftests/futex: Create test for robust list
  selftests/futex: Create tests for long and circular robust lists

 include/uapi/linux/futex.h                    |   3 +-
 kernel/futex/core.c                           |  13 +-
 .../selftests/futex/functional/.gitignore     |   1 +
 .../selftests/futex/functional/Makefile       |   3 +-
 .../selftests/futex/functional/robust_list.c  | 641 ++++++++++++++++++
 .../testing/selftests/futex/include/logging.h |  38 ++
 6 files changed, 690 insertions(+), 9 deletions(-)
 create mode 100644 tools/testing/selftests/futex/functional/robust_list.c

-- 
2.48.0

* André Almeida:

> As requested by Peter at [1], this patchset drops the
> ROBUST_LIST_LIMIT. This is achieve by simply rewriting the processed
> list element ->next to point to the head->list address, destroying the
> linked list to avoid any circular list.

Doesn't this turn a robust mutex overwrite or a TCB overwrite into a
write-anything-anywhere primitive?  Furthermore, I'm not entirely sure
if this is entirely backwards-compatible.

Could you use the tortoise/hare approach instead?

Thanks,
Florian

On Tue, Jan 28, 2025 at 08:50:41AM +0100, Florian Weimer wrote:
> * André Almeida:
> 
> > As requested by Peter at [1], this patchset drops the
> > ROBUST_LIST_LIMIT. This is achieve by simply rewriting the processed
> > list element ->next to point to the head->list address, destroying the
> > linked list to avoid any circular list.

Well, I suggested we do this for a new robust list.

> Furthermore, I'm not entirely sure
> if this is entirely backwards-compatible.

I share Florian's concern about backward compat here. It might work, it
might not.

I was just saying that if we're going to be doing new robust lists, we
should try and fix all the known wrongs, and this one lets us get rid of the limit.

> Could you use the tortoise/hare approach instead?

That seems overly complicated for what we need.

Em 03/02/2025 10:29, Peter Zijlstra escreveu:
> On Tue, Jan 28, 2025 at 08:50:41AM +0100, Florian Weimer wrote:
>> * André Almeida:
>>
>>> As requested by Peter at [1], this patchset drops the
>>> ROBUST_LIST_LIMIT. This is achieve by simply rewriting the processed
>>> list element ->next to point to the head->list address, destroying the
>>> linked list to avoid any circular list.
> 
> Well, I suggested we do this for a new robust list.
> 
>> Furthermore, I'm not entirely sure
>> if this is entirely backwards-compatible.
> 
> I share Florian's concern about backward compat here. It might work, it
> might not.
> 
> I was just saying that if we're going to be doing new robust lists, we
> should try and fix all the known wrongs, and this one lets us get rid of the limit.
> 

Oh, now I see, thanks for the clarification. I will add this for the new 
interface then.

In the meanwhile, if you can a look at  patch 3/4 "selftests/futex: 
Create test for robust list" that would help to make sure the new 
interface don't mess with the old one.

Hi Florian,

Em 28/01/2025 04:50, Florian Weimer escreveu:
> * André Almeida:
> 
>> As requested by Peter at [1], this patchset drops the
>> ROBUST_LIST_LIMIT. This is achieve by simply rewriting the processed
>> list element ->next to point to the head->list address, destroying the
>> linked list to avoid any circular list.
> 
> Doesn't this turn a robust mutex overwrite or a TCB overwrite into a
> write-anything-anywhere primitive?  Furthermore, I'm not entirely sure
> if this is entirely backwards-compatible.
> 

The robust list is meant to be a private resource, per-process, and this 
patch only rewrites it after the process exits, so I believe that any 
changes done in this memory should be safe given that the process will 
soon disappear anyway, right?

Do you think you can point out a scenario that wouldn't be 
backwards-compatible? I would like to try to test it.

> Could you use the tortoise/hare approach instead?
> 

I believe that you want the approach to be "slow and steady" but I'm not 
sure what you have in mind, if you could you please elaborate :)

> Thanks,
> Florian
> 

* André Almeida:

> Hi Florian,
>
> Em 28/01/2025 04:50, Florian Weimer escreveu:
>> * André Almeida:
>> 
>>> As requested by Peter at [1], this patchset drops the
>>> ROBUST_LIST_LIMIT. This is achieve by simply rewriting the processed
>>> list element ->next to point to the head->list address, destroying the
>>> linked list to avoid any circular list.
>> Doesn't this turn a robust mutex overwrite or a TCB overwrite into a
>> write-anything-anywhere primitive?  Furthermore, I'm not entirely sure
>> if this is entirely backwards-compatible.
>> 
>
> The robust list is meant to be a private resource, per-process, and
> this patch only rewrites it after the process exits, so I believe that
> any changes done in this memory should be safe given that the process
> will soon disappear anyway, right?

At least in the glibc implementation, we let the kernel handle robust
mutex notification on thread exit, and that's observable.

Beyond that, process-shared robust mutexes exist, too, and those updates
will be observable, too.

> Do you think you can point out a scenario that wouldn't be
> backwards-compatible? I would like to try to test it.

I think it should be okay for the glibc implementation.  The robust list
is libc-owned (at least in glibc implementation), so it should not
matter, but the are other libs out there.

>> Could you use the tortoise/hare approach instead?

> I believe that you want the approach to be "slow and steady" but I'm
> not sure what you have in mind, if you could you please elaborate :)

I meant cycle detection using Floyd's algorithm.

Thanks,
Florian

On Tue, Jan 28, 2025 at 09:35:26PM +0100, Florian Weimer wrote:

> >> Doesn't this turn a robust mutex overwrite or a TCB overwrite into a
> >> write-anything-anywhere primitive?
> >
> > The robust list is meant to be a private resource, per-process, and
> > this patch only rewrites it after the process exits, so I believe that
> > any changes done in this memory should be safe given that the process
> > will soon disappear anyway, right?
> 
> At least in the glibc implementation, we let the kernel handle robust
> mutex notification on thread exit, and that's observable.
> 
> Beyond that, process-shared robust mutexes exist, too, and those updates
> will be observable, too.

AFAICT we don't allow writing anywhere we couldn't already. The process
shared things should be in shared memory, something we can already write
to.

Notably, the kernel doesn't change address space while walking the
robust list (the robust list doesn't even contain enough information to
do this, even if we wanted to), it can only write to things the dying
task could already write to.

So I don't think there is a security angle here. Yes userspace can shoot
itself in the foot with this, but what else is new.