[PATCH] threads: Update PID limit comment according to futex UAPI change

[PATCH] threads: Update PID limit comment according to futex UAPI change

[Jann Horn]

The futex UAPI changed back in commit 76b81e2b0e22 ("[PATCH] lightweight
robust futexes updates 2"), which landed in v2.6.17: FUTEX_TID_MASK is now
0x3fffffff instead of 0x1fffffff. Update the corresponding comment in
include/linux/threads.h.

Signed-off-by: Jann Horn <jannh@google.com>
---
 include/linux/threads.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/threads.h b/include/linux/threads.h
index 3086dba525e20..18d5a74bcc3dd 100644
--- a/include/linux/threads.h
+++ b/include/linux/threads.h
@@ -29,7 +29,7 @@
 
 /*
  * A maximum of 4 million PIDs should be enough for a while.
- * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]
+ * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
  */
 #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
 	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))
-- 
2.25.0.265.gbab2e86ba0-goog

Re: [PATCH] threads: Update PID limit comment according to futex UAPI change

[Peter Zijlstra]

On Mon, Mar 02, 2020 at 12:29:39PM +0100, Jann Horn wrote:
> The futex UAPI changed back in commit 76b81e2b0e22 ("[PATCH] lightweight
> robust futexes updates 2"), which landed in v2.6.17: FUTEX_TID_MASK is now
> 0x3fffffff instead of 0x1fffffff. Update the corresponding comment in
> include/linux/threads.h.
> 
> Signed-off-by: Jann Horn <jannh@google.com>
> ---
>  include/linux/threads.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/include/linux/threads.h b/include/linux/threads.h
> index 3086dba525e20..18d5a74bcc3dd 100644
> --- a/include/linux/threads.h
> +++ b/include/linux/threads.h
> @@ -29,7 +29,7 @@
>  
>  /*
>   * A maximum of 4 million PIDs should be enough for a while.
> - * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]
> + * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
>   */
>  #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
>  	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))

I just noticed another mention of this in Documentation/robust-futex-ABI.txt
There it states that bit-29 is reserved for future use.

Thomas, do we want to release that bit and update all this?

Re: [PATCH] threads: Update PID limit comment according to futex UAPI change

[Thomas Gleixner]

Peter Zijlstra <peterz@infradead.org> writes:
> On Mon, Mar 02, 2020 at 12:29:39PM +0100, Jann Horn wrote:
>> The futex UAPI changed back in commit 76b81e2b0e22 ("[PATCH] lightweight
>> robust futexes updates 2"), which landed in v2.6.17: FUTEX_TID_MASK is now
>> 0x3fffffff instead of 0x1fffffff. Update the corresponding comment in
>> include/linux/threads.h.
>> 
>> Signed-off-by: Jann Horn <jannh@google.com>
>> ---
>>  include/linux/threads.h | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>> 
>> diff --git a/include/linux/threads.h b/include/linux/threads.h
>> index 3086dba525e20..18d5a74bcc3dd 100644
>> --- a/include/linux/threads.h
>> +++ b/include/linux/threads.h
>> @@ -29,7 +29,7 @@
>>  
>>  /*
>>   * A maximum of 4 million PIDs should be enough for a while.
>> - * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]
>> + * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
>>   */
>>  #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
>>  	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))
>
> I just noticed another mention of this in Documentation/robust-futex-ABI.txt
> There it states that bit-29 is reserved for future use.
>
> Thomas, do we want to release that bit and update all this?

In fact we've released it long ago:

include/uapi/linux/futex.h:

#define FUTEX_TID_MASK          0x3fffffff

Thanks,

        tglx

Re: [PATCH] threads: Update PID limit comment according to futex UAPI change

[Thomas Gleixner]

Reviving this old thread.

On Tue, Mar 03 2020 at 15:12, Thomas Gleixner wrote:
> Peter Zijlstra <peterz@infradead.org> writes:
>> On Mon, Mar 02, 2020 at 12:29:39PM +0100, Jann Horn wrote:
>>>  /*
>>>   * A maximum of 4 million PIDs should be enough for a while.
>>> - * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]
>>> + * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
>>>   */
>>>  #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
>>>  	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))
>>
>> I just noticed another mention of this in Documentation/robust-futex-ABI.txt
>> There it states that bit-29 is reserved for future use.
>>
>> Thomas, do we want to release that bit and update all this?
>
> In fact we've released it long ago:
>
> include/uapi/linux/futex.h:
>
> #define FUTEX_TID_MASK          0x3fffffff

That futex mask is irrelevant because there is another limitiation for
the PID space namely posix CPU timers:

static inline clockid_t make_process_cpuclock(const unsigned int pid,
		                              const clockid_t clock)
{
	return ((~pid) << 3) | clock;
}

That existed even before we fiddled with robust futexes and puts a hard
limit of 29 bits on the PID space.

So we want something like the below.

Thanks,

        tglx
---       
--- a/include/linux/threads.h
+++ b/include/linux/threads.h
@@ -29,7 +29,9 @@
 
 /*
  * A maximum of 4 million PIDs should be enough for a while.
- * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
+ *
+ * PID/TIDs are limited to 2^29 due to POSIX CPU timers. See
+ * make_process_cpuclock().
  */
 #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
 	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))

Re: [PATCH] threads: Update PID limit comment according to futex UAPI change

[Thomas Gleixner]

On Thu, May 11 2023 at 14:47, Thomas Gleixner wrote:
>> #define FUTEX_TID_MASK          0x3fffffff
>
> That futex mask is irrelevant because there is another limitiation for
> the PID space namely posix CPU timers:
>
> static inline clockid_t make_process_cpuclock(const unsigned int pid,
> 		                              const clockid_t clock)
> {
> 	return ((~pid) << 3) | clock;
> }
>
> That existed even before we fiddled with robust futexes and puts a hard
> limit of 29 bits on the PID space.

Actually it's worse than this. The limit is 28 bits because posix CPU
timers rely on this:

static const struct k_clock *clockid_to_kclock(const clockid_t id)
{
	clockid_t idx = id;

	if (id < 0) {
		return (id & CLOCKFD_MASK) == CLOCKFD ?
			&clock_posix_dynamic : &clock_posix_cpu;
	}
        ....

So TID must be smaller than 2^28 because if bit 28 would be set, then
the resulting clock would be positive after shift.

Sigh...

[tip: sched/core] threads: Update PID limit comment according to futex UAPI change

[tip-bot2 for Jann Horn]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     9c40365a65d62d7c06a95fb331b3442cb02d2fd9
Gitweb:        https://git.kernel.org/tip/9c40365a65d62d7c06a95fb331b3442cb02d2fd9
Author:        Jann Horn <jannh@google.com>
AuthorDate:    Mon, 02 Mar 2020 12:29:39 +01:00
Committer:     Thomas Gleixner <tglx@linutronix.de>
CommitterDate: Sat, 21 Mar 2020 17:48:13 +01:00

threads: Update PID limit comment according to futex UAPI change

The futex UAPI changed back in commit 76b81e2b0e22 ("[PATCH] lightweight
robust futexes updates 2"), which landed in v2.6.17: FUTEX_TID_MASK is now
0x3fffffff instead of 0x1fffffff. Update the corresponding comment in
include/linux/threads.h.

Documentation mentions that only the lower 29 bits are available for TID
storage, but as the UAPI header released the bit already via
FUTEX_TID_MASK, this is moot as well. Fix it up.

[ tglx: Fixed up documentation ]

Signed-off-by: Jann Horn <jannh@google.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Link: https://lkml.kernel.org/r/20200302112939.8068-1-jannh@google.com

---
 Documentation/robust-futex-ABI.txt | 14 ++++++--------
 include/linux/threads.h            |  2 +-
 2 files changed, 7 insertions(+), 9 deletions(-)

diff --git a/Documentation/robust-futex-ABI.txt b/Documentation/robust-futex-ABI.txt
index 8a5d34a..f24904f 100644
--- a/Documentation/robust-futex-ABI.txt
+++ b/Documentation/robust-futex-ABI.txt
@@ -61,8 +61,8 @@ setup that list.
   address of the associated 'lock entry', plus or minus, of what will
   be called the 'lock word', from that 'lock entry'.  The 'lock word'
   is always a 32 bit word, unlike the other words above.  The 'lock
-  word' holds 3 flag bits in the upper 3 bits, and the thread id (TID)
-  of the thread holding the lock in the bottom 29 bits.  See further
+  word' holds 2 flag bits in the upper 2 bits, and the thread id (TID)
+  of the thread holding the lock in the bottom 30 bits.  See further
   below for a description of the flag bits.
 
   The third word, called 'list_op_pending', contains transient copy of
@@ -128,7 +128,7 @@ that thread's robust_futex linked lock list a given time.
 A given futex lock structure in a user shared memory region may be held
 at different times by any of the threads with access to that region. The
 thread currently holding such a lock, if any, is marked with the threads
-TID in the lower 29 bits of the 'lock word'.
+TID in the lower 30 bits of the 'lock word'.
 
 When adding or removing a lock from its list of held locks, in order for
 the kernel to correctly handle lock cleanup regardless of when the task
@@ -141,7 +141,7 @@ On insertion:
  1) set the 'list_op_pending' word to the address of the 'lock entry'
     to be inserted,
  2) acquire the futex lock,
- 3) add the lock entry, with its thread id (TID) in the bottom 29 bits
+ 3) add the lock entry, with its thread id (TID) in the bottom 30 bits
     of the 'lock word', to the linked list starting at 'head', and
  4) clear the 'list_op_pending' word.
 
@@ -155,7 +155,7 @@ On removal:
 
 On exit, the kernel will consider the address stored in
 'list_op_pending' and the address of each 'lock word' found by walking
-the list starting at 'head'.  For each such address, if the bottom 29
+the list starting at 'head'.  For each such address, if the bottom 30
 bits of the 'lock word' at offset 'offset' from that address equals the
 exiting threads TID, then the kernel will do two things:
 
@@ -180,7 +180,5 @@ any point:
     future kernel configuration changes) elements.
 
 When the kernel sees a list entry whose 'lock word' doesn't have the
-current threads TID in the lower 29 bits, it does nothing with that
+current threads TID in the lower 30 bits, it does nothing with that
 entry, and goes on to the next entry.
-
-Bit 29 (0x20000000) of the 'lock word' is reserved for future use.
diff --git a/include/linux/threads.h b/include/linux/threads.h
index 3086dba..18d5a74 100644
--- a/include/linux/threads.h
+++ b/include/linux/threads.h
@@ -29,7 +29,7 @@
 
 /*
  * A maximum of 4 million PIDs should be enough for a while.
- * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]
+ * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
  */
 #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
 	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))