Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Fri, May 27, 2016 at 07:27:57PM +0200, Sebastian Andrzej Siewior wrote:
> On 2016-05-19 14:25:58 [+0200], Peter Zijlstra wrote:
> > On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > > +static int futex_preallocate_hash(unsigned int slots)
> > > +{
> > > +#ifdef CONFIG_FUTEX_PRIVATE_HASH
> > > + struct mm_struct *mm = current->mm;
> > > + struct futex_hash_bucket *hb;
> > > + unsigned int bits;
> > > +
> > > + /* Try to allocate the requested nr of slots */
> > > + bits = order_base_2(slots);
> > > +
> > > + if (bits < FUTEX_MIN_HASH_BITS)
> > > + bits = FUTEX_MIN_HASH_BITS;
> > > +
> > > + if (bits > futex_max_hash_bits)
> > > + bits = futex_max_hash_bits;
> > > +
> > > + futex_populate_hash(bits);
> > 
> > Should we not simply fail if the provided number of slots is not a power
> > of 2 ?
> 
> We could if it is worth doing so. The procfs interface which limits the
> upper / lower limit is bits based. This is slot based which then gets
> converted to the number if bits.
> If we align this interface with proc's limits then we would expect the
> number of bits instead slots - now check for power of two anymore.
> Anyone?

I'm all for consistent and strict when it comes to things like this.

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Fri, May 27, 2016 at 07:27:57PM +0200, Sebastian Andrzej Siewior wrote:
> On 2016-05-19 14:25:58 [+0200], Peter Zijlstra wrote:
> > On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > > +static int futex_preallocate_hash(unsigned int slots)
> > > +{
> > > +#ifdef CONFIG_FUTEX_PRIVATE_HASH
> > > + struct mm_struct *mm = current->mm;
> > > + struct futex_hash_bucket *hb;
> > > + unsigned int bits;
> > > +
> > > + /* Try to allocate the requested nr of slots */
> > > + bits = order_base_2(slots);
> > > +
> > > + if (bits < FUTEX_MIN_HASH_BITS)
> > > + bits = FUTEX_MIN_HASH_BITS;
> > > +
> > > + if (bits > futex_max_hash_bits)
> > > + bits = futex_max_hash_bits;
> > > +
> > > + futex_populate_hash(bits);
> > 
> > Should we not simply fail if the provided number of slots is not a power
> > of 2 ?
> 
> We could if it is worth doing so. The procfs interface which limits the
> upper / lower limit is bits based. This is slot based which then gets
> converted to the number if bits.
> If we align this interface with proc's limits then we would expect the
> number of bits instead slots - now check for power of two anymore.
> Anyone?

I'm all for consistent and strict when it comes to things like this.

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Sebastian Andrzej Siewior]

On 2016-05-19 14:25:58 [+0200], Peter Zijlstra wrote:
> On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > +static int futex_preallocate_hash(unsigned int slots)
> > +{
> > +#ifdef CONFIG_FUTEX_PRIVATE_HASH
> > +   struct mm_struct *mm = current->mm;
> > +   struct futex_hash_bucket *hb;
> > +   unsigned int bits;
> > +
> > +   /* Try to allocate the requested nr of slots */
> > +   bits = order_base_2(slots);
> > +
> > +   if (bits < FUTEX_MIN_HASH_BITS)
> > +   bits = FUTEX_MIN_HASH_BITS;
> > +
> > +   if (bits > futex_max_hash_bits)
> > +   bits = futex_max_hash_bits;
> > +
> > +   futex_populate_hash(bits);
> 
> Should we not simply fail if the provided number of slots is not a power
> of 2 ?

We could if it is worth doing so. The procfs interface which limits the
upper / lower limit is bits based. This is slot based which then gets
converted to the number if bits.
If we align this interface with proc's limits then we would expect the
number of bits instead slots - now check for power of two anymore.
Anyone?

Sebastian

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Sebastian Andrzej Siewior]

On 2016-05-19 14:25:58 [+0200], Peter Zijlstra wrote:
> On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > +static int futex_preallocate_hash(unsigned int slots)
> > +{
> > +#ifdef CONFIG_FUTEX_PRIVATE_HASH
> > +   struct mm_struct *mm = current->mm;
> > +   struct futex_hash_bucket *hb;
> > +   unsigned int bits;
> > +
> > +   /* Try to allocate the requested nr of slots */
> > +   bits = order_base_2(slots);
> > +
> > +   if (bits < FUTEX_MIN_HASH_BITS)
> > +   bits = FUTEX_MIN_HASH_BITS;
> > +
> > +   if (bits > futex_max_hash_bits)
> > +   bits = futex_max_hash_bits;
> > +
> > +   futex_populate_hash(bits);
> 
> Should we not simply fail if the provided number of slots is not a power
> of 2 ?

We could if it is worth doing so. The procfs interface which limits the
upper / lower limit is bits based. This is slot based which then gets
converted to the number if bits.
If we align this interface with proc's limits then we would expect the
number of bits instead slots - now check for power of two anymore.
Anyone?

Sebastian

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Thu, May 19, 2016 at 12:38:19PM -0700, Darren Hart wrote:
> On Thu, May 19, 2016 at 02:24:57PM +0200, Peter Zijlstra wrote:
> > OK, so no on-line rehashing possible?
> 
> It doesn't do it currently... did you see something that makes it impossible 
> to
> add?

No, just tons of tricky.

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Thu, May 19, 2016 at 12:38:19PM -0700, Darren Hart wrote:
> On Thu, May 19, 2016 at 02:24:57PM +0200, Peter Zijlstra wrote:
> > OK, so no on-line rehashing possible?
> 
> It doesn't do it currently... did you see something that makes it impossible 
> to
> add?

No, just tons of tricky.

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Darren Hart]

On Thu, May 19, 2016 at 02:24:57PM +0200, Peter Zijlstra wrote:
> On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > From: Sebastian Siewior 
> > 
> > The per process hash is allocated on the fly at the first futex operation 
> > of a
> > process. The size of the hash is determined by a system wide default setting
> > controlled by the sys admin, This is suboptimal for RT applications and
> > applications with pathological futex abuse,
> > 
> >  - For RT applications its important to allocate the per process hash 
> > before the
> >first futex operation to avoid the allocation on the first futex 
> > operation.
> > 
> >  - For pathological applications which use gazillions of futexes its useful 
> > to
> >allocate a hash greater than the default hash size.
> > 
> > Add a futex op which allows to preallocate the hash with the requested
> > size. The size is limited by the systemwide maximum hash size, which can be
> > set by the admin. The requested size is rounded up to the next order of 2.
> > 
> > The function can be called several times, but ony the first call results in 
> > a
> > hash allocation of the requested size as there is no non-intrusive way to
> > reallocate/rehash in a multithreaded application.
> > 
> > Note, that this call must be issued before the first futex operation in the
> > process because that would automatically allocate the default sized hash.
> > 
> > The function returns the actual hash size or 0 if the global hash is used. 
> > The
> > latter is the case on UP and in the rare case that the allocation failed and
> > the global hash is used as a fallback.
> 
> OK, so no on-line rehashing possible?

It doesn't do it currently... did you see something that makes it impossible to
add?


-- 
Darren Hart
Intel Open Source Technology Center

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Darren Hart]

On Thu, May 19, 2016 at 02:24:57PM +0200, Peter Zijlstra wrote:
> On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > From: Sebastian Siewior 
> > 
> > The per process hash is allocated on the fly at the first futex operation 
> > of a
> > process. The size of the hash is determined by a system wide default setting
> > controlled by the sys admin, This is suboptimal for RT applications and
> > applications with pathological futex abuse,
> > 
> >  - For RT applications its important to allocate the per process hash 
> > before the
> >first futex operation to avoid the allocation on the first futex 
> > operation.
> > 
> >  - For pathological applications which use gazillions of futexes its useful 
> > to
> >allocate a hash greater than the default hash size.
> > 
> > Add a futex op which allows to preallocate the hash with the requested
> > size. The size is limited by the systemwide maximum hash size, which can be
> > set by the admin. The requested size is rounded up to the next order of 2.
> > 
> > The function can be called several times, but ony the first call results in 
> > a
> > hash allocation of the requested size as there is no non-intrusive way to
> > reallocate/rehash in a multithreaded application.
> > 
> > Note, that this call must be issued before the first futex operation in the
> > process because that would automatically allocate the default sized hash.
> > 
> > The function returns the actual hash size or 0 if the global hash is used. 
> > The
> > latter is the case on UP and in the rare case that the allocation failed and
> > the global hash is used as a fallback.
> 
> OK, so no on-line rehashing possible?

It doesn't do it currently... did you see something that makes it impossible to
add?


-- 
Darren Hart
Intel Open Source Technology Center

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Darren Hart]

On Thu, May 19, 2016 at 02:28:49PM +0200, Peter Zijlstra wrote:
> On Sat, May 07, 2016 at 10:47:38AM +0200, Thomas Gleixner wrote:
> > On Fri, 6 May 2016, Darren Hart wrote:
> 
> > > So this seems like it could be tricky for the user as system libraries, 
> > > like
> > > glibc, make use of futexes. Can we guarantee that "sys_futex" is not 
> > > called by
> > > the time main() is called?
> > 
> > To the extent of my testing I never observed that the hash was automatically
> > created when I called futex(PREALLOC) right away in main. But yes, that 
> > might
> > need some thought.
> 
> I suspect that even if glibc uses futexes before main(), they will not
> be contended, because, last time I checked, the C runtime environment is
> very much single threaded unless explicitly made not so by the program.
> 
> In any case (re)hashing if the hash is empty is 'easy', if there's already 
> state,
> not so much.

It certainly would be nice to be able to resize the hash if it's empty.

-- 
Darren Hart
Intel Open Source Technology Center

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Darren Hart]

On Thu, May 19, 2016 at 02:28:49PM +0200, Peter Zijlstra wrote:
> On Sat, May 07, 2016 at 10:47:38AM +0200, Thomas Gleixner wrote:
> > On Fri, 6 May 2016, Darren Hart wrote:
> 
> > > So this seems like it could be tricky for the user as system libraries, 
> > > like
> > > glibc, make use of futexes. Can we guarantee that "sys_futex" is not 
> > > called by
> > > the time main() is called?
> > 
> > To the extent of my testing I never observed that the hash was automatically
> > created when I called futex(PREALLOC) right away in main. But yes, that 
> > might
> > need some thought.
> 
> I suspect that even if glibc uses futexes before main(), they will not
> be contended, because, last time I checked, the C runtime environment is
> very much single threaded unless explicitly made not so by the program.
> 
> In any case (re)hashing if the hash is empty is 'easy', if there's already 
> state,
> not so much.

It certainly would be nice to be able to resize the hash if it's empty.

-- 
Darren Hart
Intel Open Source Technology Center

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Sat, May 07, 2016 at 10:47:38AM +0200, Thomas Gleixner wrote:
> On Fri, 6 May 2016, Darren Hart wrote:

> > So this seems like it could be tricky for the user as system libraries, like
> > glibc, make use of futexes. Can we guarantee that "sys_futex" is not called 
> > by
> > the time main() is called?
> 
> To the extent of my testing I never observed that the hash was automatically
> created when I called futex(PREALLOC) right away in main. But yes, that might
> need some thought.

I suspect that even if glibc uses futexes before main(), they will not
be contended, because, last time I checked, the C runtime environment is
very much single threaded unless explicitly made not so by the program.

In any case (re)hashing if the hash is empty is 'easy', if there's already 
state,
not so much.

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Sat, May 07, 2016 at 10:47:38AM +0200, Thomas Gleixner wrote:
> On Fri, 6 May 2016, Darren Hart wrote:

> > So this seems like it could be tricky for the user as system libraries, like
> > glibc, make use of futexes. Can we guarantee that "sys_futex" is not called 
> > by
> > the time main() is called?
> 
> To the extent of my testing I never observed that the hash was automatically
> created when I called futex(PREALLOC) right away in main. But yes, that might
> need some thought.

I suspect that even if glibc uses futexes before main(), they will not
be contended, because, last time I checked, the C runtime environment is
very much single threaded unless explicitly made not so by the program.

In any case (re)hashing if the hash is empty is 'easy', if there's already 
state,
not so much.

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> +static int futex_preallocate_hash(unsigned int slots)
> +{
> +#ifdef CONFIG_FUTEX_PRIVATE_HASH
> + struct mm_struct *mm = current->mm;
> + struct futex_hash_bucket *hb;
> + unsigned int bits;
> +
> + /* Try to allocate the requested nr of slots */
> + bits = order_base_2(slots);
> +
> + if (bits < FUTEX_MIN_HASH_BITS)
> + bits = FUTEX_MIN_HASH_BITS;
> +
> + if (bits > futex_max_hash_bits)
> + bits = futex_max_hash_bits;
> +
> + futex_populate_hash(bits);

Should we not simply fail if the provided number of slots is not a power
of 2 ?

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> +static int futex_preallocate_hash(unsigned int slots)
> +{
> +#ifdef CONFIG_FUTEX_PRIVATE_HASH
> + struct mm_struct *mm = current->mm;
> + struct futex_hash_bucket *hb;
> + unsigned int bits;
> +
> + /* Try to allocate the requested nr of slots */
> + bits = order_base_2(slots);
> +
> + if (bits < FUTEX_MIN_HASH_BITS)
> + bits = FUTEX_MIN_HASH_BITS;
> +
> + if (bits > futex_max_hash_bits)
> + bits = futex_max_hash_bits;
> +
> + futex_populate_hash(bits);

Should we not simply fail if the provided number of slots is not a power
of 2 ?

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> From: Sebastian Siewior 
> 
> The per process hash is allocated on the fly at the first futex operation of a
> process. The size of the hash is determined by a system wide default setting
> controlled by the sys admin, This is suboptimal for RT applications and
> applications with pathological futex abuse,
> 
>  - For RT applications its important to allocate the per process hash before 
> the
>first futex operation to avoid the allocation on the first futex operation.
> 
>  - For pathological applications which use gazillions of futexes its useful to
>allocate a hash greater than the default hash size.
> 
> Add a futex op which allows to preallocate the hash with the requested
> size. The size is limited by the systemwide maximum hash size, which can be
> set by the admin. The requested size is rounded up to the next order of 2.
> 
> The function can be called several times, but ony the first call results in a
> hash allocation of the requested size as there is no non-intrusive way to
> reallocate/rehash in a multithreaded application.
> 
> Note, that this call must be issued before the first futex operation in the
> process because that would automatically allocate the default sized hash.
> 
> The function returns the actual hash size or 0 if the global hash is used. The
> latter is the case on UP and in the rare case that the allocation failed and
> the global hash is used as a fallback.

OK, so no on-line rehashing possible?

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Peter Zijlstra]

On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> From: Sebastian Siewior 
> 
> The per process hash is allocated on the fly at the first futex operation of a
> process. The size of the hash is determined by a system wide default setting
> controlled by the sys admin, This is suboptimal for RT applications and
> applications with pathological futex abuse,
> 
>  - For RT applications its important to allocate the per process hash before 
> the
>first futex operation to avoid the allocation on the first futex operation.
> 
>  - For pathological applications which use gazillions of futexes its useful to
>allocate a hash greater than the default hash size.
> 
> Add a futex op which allows to preallocate the hash with the requested
> size. The size is limited by the systemwide maximum hash size, which can be
> set by the admin. The requested size is rounded up to the next order of 2.
> 
> The function can be called several times, but ony the first call results in a
> hash allocation of the requested size as there is no non-intrusive way to
> reallocate/rehash in a multithreaded application.
> 
> Note, that this call must be issued before the first futex operation in the
> process because that would automatically allocate the default sized hash.
> 
> The function returns the actual hash size or 0 if the global hash is used. The
> latter is the case on UP and in the rare case that the allocation failed and
> the global hash is used as a fallback.

OK, so no on-line rehashing possible?

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

On Sat, 7 May 2016, Thomas Gleixner wrote:
> On Fri, 6 May 2016, Darren Hart wrote:
> > > Note, that this call must be issued before the first futex operation in 
> > > the
> > > process because that would automatically allocate the default sized hash.
> > 
> > So this seems like it could be tricky for the user as system libraries, like
> > glibc, make use of futexes. Can we guarantee that "sys_futex" is not called 
> > by
> > the time main() is called?
> 
> To the extent of my testing I never observed that the hash was automatically
> created when I called futex(PREALLOC) right away in main. But yes, that might
> need some thought.

Thinking more about it. If a process is single threaded and it definitely is
up to the point where it reaches main(), there is nothing which might cause a
sys_futex() call except something which would use shared futexes in the depth
of init code. I doubt that this happens, and if it does, then it's some non
standard feature^Whackery which I do not care about at all.

Thanks,

tglx

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

On Sat, 7 May 2016, Thomas Gleixner wrote:
> On Fri, 6 May 2016, Darren Hart wrote:
> > > Note, that this call must be issued before the first futex operation in 
> > > the
> > > process because that would automatically allocate the default sized hash.
> > 
> > So this seems like it could be tricky for the user as system libraries, like
> > glibc, make use of futexes. Can we guarantee that "sys_futex" is not called 
> > by
> > the time main() is called?
> 
> To the extent of my testing I never observed that the hash was automatically
> created when I called futex(PREALLOC) right away in main. But yes, that might
> need some thought.

Thinking more about it. If a process is single threaded and it definitely is
up to the point where it reaches main(), there is nothing which might cause a
sys_futex() call except something which would use shared futexes in the depth
of init code. I doubt that this happens, and if it does, then it's some non
standard feature^Whackery which I do not care about at all.

Thanks,

tglx

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

On Fri, 6 May 2016, Darren Hart wrote:
> On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > From: Sebastian Siewior 
> > 
> > The per process hash is allocated on the fly at the first futex operation 
> > of a
> > process. The size of the hash is determined by a system wide default setting
> > controlled by the sys admin, This is suboptimal for RT applications and
> > applications with pathological futex abuse,
> > 
> >  - For RT applications its important to allocate the per process hash 
> > before the
> >first futex operation to avoid the allocation on the first futex 
> > operation.
> > 
> >  - For pathological applications which use gazillions of futexes its useful 
> > to
> >allocate a hash greater than the default hash size.
> 
> "it's" or preferably "it is"
> 
> > 
> > Add a futex op which allows to preallocate the hash with the requested
> 
> "allows for preallocating"
> 
> > size. The size is limited by the systemwide maximum hash size, which can be
> 
> system-wide
> 
> > set by the admin. The requested size is rounded up to the next order of 2.
> > 
> > The function can be called several times, but ony the first call results in 
> > a
> > hash allocation of the requested size as there is no non-intrusive way to
> > reallocate/rehash in a multithreaded application.
> > 
> > Note, that this call must be issued before the first futex operation in the
> > process because that would automatically allocate the default sized hash.
> 
> So this seems like it could be tricky for the user as system libraries, like
> glibc, make use of futexes. Can we guarantee that "sys_futex" is not called by
> the time main() is called?

To the extent of my testing I never observed that the hash was automatically
created when I called futex(PREALLOC) right away in main. But yes, that might
need some thought.

Thanks,

tglx

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

On Fri, 6 May 2016, Darren Hart wrote:
> On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> > From: Sebastian Siewior 
> > 
> > The per process hash is allocated on the fly at the first futex operation 
> > of a
> > process. The size of the hash is determined by a system wide default setting
> > controlled by the sys admin, This is suboptimal for RT applications and
> > applications with pathological futex abuse,
> > 
> >  - For RT applications its important to allocate the per process hash 
> > before the
> >first futex operation to avoid the allocation on the first futex 
> > operation.
> > 
> >  - For pathological applications which use gazillions of futexes its useful 
> > to
> >allocate a hash greater than the default hash size.
> 
> "it's" or preferably "it is"
> 
> > 
> > Add a futex op which allows to preallocate the hash with the requested
> 
> "allows for preallocating"
> 
> > size. The size is limited by the systemwide maximum hash size, which can be
> 
> system-wide
> 
> > set by the admin. The requested size is rounded up to the next order of 2.
> > 
> > The function can be called several times, but ony the first call results in 
> > a
> > hash allocation of the requested size as there is no non-intrusive way to
> > reallocate/rehash in a multithreaded application.
> > 
> > Note, that this call must be issued before the first futex operation in the
> > process because that would automatically allocate the default sized hash.
> 
> So this seems like it could be tricky for the user as system libraries, like
> glibc, make use of futexes. Can we guarantee that "sys_futex" is not called by
> the time main() is called?

To the extent of my testing I never observed that the hash was automatically
created when I called futex(PREALLOC) right away in main. But yes, that might
need some thought.

Thanks,

tglx

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Darren Hart]

On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> From: Sebastian Siewior 
> 
> The per process hash is allocated on the fly at the first futex operation of a
> process. The size of the hash is determined by a system wide default setting
> controlled by the sys admin, This is suboptimal for RT applications and
> applications with pathological futex abuse,
> 
>  - For RT applications its important to allocate the per process hash before 
> the
>first futex operation to avoid the allocation on the first futex operation.
> 
>  - For pathological applications which use gazillions of futexes its useful to
>allocate a hash greater than the default hash size.

"it's" or preferably "it is"

> 
> Add a futex op which allows to preallocate the hash with the requested

"allows for preallocating"

> size. The size is limited by the systemwide maximum hash size, which can be

system-wide

> set by the admin. The requested size is rounded up to the next order of 2.
> 
> The function can be called several times, but ony the first call results in a
> hash allocation of the requested size as there is no non-intrusive way to
> reallocate/rehash in a multithreaded application.
> 
> Note, that this call must be issued before the first futex operation in the
> process because that would automatically allocate the default sized hash.

So this seems like it could be tricky for the user as system libraries, like
glibc, make use of futexes. Can we guarantee that "sys_futex" is not called by
the time main() is called?

> The function returns the actual hash size or 0 if the global hash is used. The
> latter is the case on UP and in the rare case that the allocation failed and
> the global hash is used as a fallback.
> 
> Signed-off-by: Sebastian Siewior 
> Signed-off-by: Thomas Gleixner 

...

-- 
Darren Hart
Intel Open Source Technology Center

Re: [patch V2 3/7] futex: Add op for hash preallocation

[Darren Hart]

On Thu, May 05, 2016 at 08:44:05PM -, Thomas Gleixner wrote:
> From: Sebastian Siewior 
> 
> The per process hash is allocated on the fly at the first futex operation of a
> process. The size of the hash is determined by a system wide default setting
> controlled by the sys admin, This is suboptimal for RT applications and
> applications with pathological futex abuse,
> 
>  - For RT applications its important to allocate the per process hash before 
> the
>first futex operation to avoid the allocation on the first futex operation.
> 
>  - For pathological applications which use gazillions of futexes its useful to
>allocate a hash greater than the default hash size.

"it's" or preferably "it is"

> 
> Add a futex op which allows to preallocate the hash with the requested

"allows for preallocating"

> size. The size is limited by the systemwide maximum hash size, which can be

system-wide

> set by the admin. The requested size is rounded up to the next order of 2.
> 
> The function can be called several times, but ony the first call results in a
> hash allocation of the requested size as there is no non-intrusive way to
> reallocate/rehash in a multithreaded application.
> 
> Note, that this call must be issued before the first futex operation in the
> process because that would automatically allocate the default sized hash.

So this seems like it could be tricky for the user as system libraries, like
glibc, make use of futexes. Can we guarantee that "sys_futex" is not called by
the time main() is called?

> The function returns the actual hash size or 0 if the global hash is used. The
> latter is the case on UP and in the rare case that the allocation failed and
> the global hash is used as a fallback.
> 
> Signed-off-by: Sebastian Siewior 
> Signed-off-by: Thomas Gleixner 

...

-- 
Darren Hart
Intel Open Source Technology Center

[patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

From: Sebastian Siewior 

The per process hash is allocated on the fly at the first futex operation of a
process. The size of the hash is determined by a system wide default setting
controlled by the sys admin, This is suboptimal for RT applications and
applications with pathological futex abuse,

 - For RT applications its important to allocate the per process hash before the
   first futex operation to avoid the allocation on the first futex operation.

 - For pathological applications which use gazillions of futexes its useful to
   allocate a hash greater than the default hash size.

Add a futex op which allows to preallocate the hash with the requested
size. The size is limited by the systemwide maximum hash size, which can be
set by the admin. The requested size is rounded up to the next order of 2.

The function can be called several times, but ony the first call results in a
hash allocation of the requested size as there is no non-intrusive way to
reallocate/rehash in a multithreaded application.

Note, that this call must be issued before the first futex operation in the
process because that would automatically allocate the default sized hash.

The function returns the actual hash size or 0 if the global hash is used. The
latter is the case on UP and in the rare case that the allocation failed and
the global hash is used as a fallback.

Signed-off-by: Sebastian Siewior 
Signed-off-by: Thomas Gleixner 
---
 include/uapi/linux/futex.h |1 +
 kernel/futex.c |   41 +
 2 files changed, 42 insertions(+)

--- a/include/uapi/linux/futex.h
+++ b/include/uapi/linux/futex.h
@@ -20,6 +20,7 @@
 #define FUTEX_WAKE_BITSET  10
 #define FUTEX_WAIT_REQUEUE_PI  11
 #define FUTEX_CMP_REQUEUE_PI   12
+#define FUTEX_PREALLOC_HASH13
 
 #define FUTEX_PRIVATE_FLAG 128
 #define FUTEX_CLOCK_REALTIME   256
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -3307,6 +3307,45 @@ static void futex_populate_hash(unsigned
 static inline void futex_populate_hash(unsigned int hash_bits) { }
 #endif
 
+/**
+ * futex_preallocate_hash - Preallocate the process private hash
+ * @slots: Number of slots to allocate
+ *
+ * The function will allocate the process private hash with the number of
+ * requested slots. The number is rounded to the next power of two and may not
+ * exceed the current system limit.
+ *
+ * If the hash was already allocated by either an earlier call to
+ * futex_preallocate_hash() or an earlier futex op which allocated the cache
+ * on the fly, we return the size of the active hash.
+ *
+ * Returns::   Size of the hash, if 0 then the global hash is used.
+ */
+static int futex_preallocate_hash(unsigned int slots)
+{
+#ifdef CONFIG_FUTEX_PRIVATE_HASH
+   struct mm_struct *mm = current->mm;
+   struct futex_hash_bucket *hb;
+   unsigned int bits;
+
+   /* Try to allocate the requested nr of slots */
+   bits = order_base_2(slots);
+
+   if (bits < FUTEX_MIN_HASH_BITS)
+   bits = FUTEX_MIN_HASH_BITS;
+
+   if (bits > futex_max_hash_bits)
+   bits = futex_max_hash_bits;
+
+   futex_populate_hash(bits);
+
+   hb = mm->futex_hash.hash;
+   return hb == FUTEX_USE_GLOBAL_HASH ? 0 : 1 << mm->futex_hash.hash_bits;
+#else
+   return 0;
+#endif
+}
+
 long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
u32 __user *uaddr2, u32 val2, u32 val3)
 {
@@ -3362,6 +3401,8 @@ long do_futex(u32 __user *uaddr, int op,
 uaddr2);
case FUTEX_CMP_REQUEUE_PI:
return futex_requeue(uaddr, flags, uaddr2, val, val2, , 1);
+   case FUTEX_PREALLOC_HASH:
+   return futex_preallocate_hash(val);
}
return -ENOSYS;
 }

[patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

From: Sebastian Siewior 

The per process hash is allocated on the fly at the first futex operation of a
process. The size of the hash is determined by a system wide default setting
controlled by the sys admin, This is suboptimal for RT applications and
applications with pathological futex abuse,

 - For RT applications its important to allocate the per process hash before the
   first futex operation to avoid the allocation on the first futex operation.

 - For pathological applications which use gazillions of futexes its useful to
   allocate a hash greater than the default hash size.

Add a futex op which allows to preallocate the hash with the requested
size. The size is limited by the systemwide maximum hash size, which can be
set by the admin. The requested size is rounded up to the next order of 2.

The function can be called several times, but ony the first call results in a
hash allocation of the requested size as there is no non-intrusive way to
reallocate/rehash in a multithreaded application.

Note, that this call must be issued before the first futex operation in the
process because that would automatically allocate the default sized hash.

The function returns the actual hash size or 0 if the global hash is used. The
latter is the case on UP and in the rare case that the allocation failed and
the global hash is used as a fallback.

Signed-off-by: Sebastian Siewior 
Signed-off-by: Thomas Gleixner 
---
 include/uapi/linux/futex.h |1 +
 kernel/futex.c |   41 +
 2 files changed, 42 insertions(+)

--- a/include/uapi/linux/futex.h
+++ b/include/uapi/linux/futex.h
@@ -20,6 +20,7 @@
 #define FUTEX_WAKE_BITSET  10
 #define FUTEX_WAIT_REQUEUE_PI  11
 #define FUTEX_CMP_REQUEUE_PI   12
+#define FUTEX_PREALLOC_HASH13
 
 #define FUTEX_PRIVATE_FLAG 128
 #define FUTEX_CLOCK_REALTIME   256
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -3307,6 +3307,45 @@ static void futex_populate_hash(unsigned
 static inline void futex_populate_hash(unsigned int hash_bits) { }
 #endif
 
+/**
+ * futex_preallocate_hash - Preallocate the process private hash
+ * @slots: Number of slots to allocate
+ *
+ * The function will allocate the process private hash with the number of
+ * requested slots. The number is rounded to the next power of two and may not
+ * exceed the current system limit.
+ *
+ * If the hash was already allocated by either an earlier call to
+ * futex_preallocate_hash() or an earlier futex op which allocated the cache
+ * on the fly, we return the size of the active hash.
+ *
+ * Returns::   Size of the hash, if 0 then the global hash is used.
+ */
+static int futex_preallocate_hash(unsigned int slots)
+{
+#ifdef CONFIG_FUTEX_PRIVATE_HASH
+   struct mm_struct *mm = current->mm;
+   struct futex_hash_bucket *hb;
+   unsigned int bits;
+
+   /* Try to allocate the requested nr of slots */
+   bits = order_base_2(slots);
+
+   if (bits < FUTEX_MIN_HASH_BITS)
+   bits = FUTEX_MIN_HASH_BITS;
+
+   if (bits > futex_max_hash_bits)
+   bits = futex_max_hash_bits;
+
+   futex_populate_hash(bits);
+
+   hb = mm->futex_hash.hash;
+   return hb == FUTEX_USE_GLOBAL_HASH ? 0 : 1 << mm->futex_hash.hash_bits;
+#else
+   return 0;
+#endif
+}
+
 long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
u32 __user *uaddr2, u32 val2, u32 val3)
 {
@@ -3362,6 +3401,8 @@ long do_futex(u32 __user *uaddr, int op,
 uaddr2);
case FUTEX_CMP_REQUEUE_PI:
return futex_requeue(uaddr, flags, uaddr2, val, val2, , 1);
+   case FUTEX_PREALLOC_HASH:
+   return futex_preallocate_hash(val);
}
return -ENOSYS;
 }

[patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

From: Sebastian Siewior 

The per process hash is allocated on the fly at the first futex operation of a
process. The size of the hash is determined by a system wide default setting
controlled by the sys admin, This is suboptimal for RT applications and
applications with pathological futex abuse,

 - For RT applications its important to allocate the per process hash before the
   first futex operation to avoid the allocation on the first futex operation.

 - For pathological applications which use gazillions of futexes its useful to
   allocate a hash greater than the default hash size.

Add a futex op which allows to preallocate the hash with the requested
size. The size is limited by the systemwide maximum hash size, which can be
set by the admin. The requested size is rounded up to the next order of 2.

The function can be called several times, but ony the first call results in a
hash allocation of the requested size as there is no non-intrusive way to
reallocate/rehash in a multithreaded application.

Note, that this call must be issued before the first futex operation in the
process because that would automatically allocate the default sized hash.

The function returns the actual hash size or 0 if the global hash is used. The
latter is the case on UP and in the rare case that the allocation failed and
the global hash is used as a fallback.

Signed-off-by: Sebastian Siewior 
Signed-off-by: Thomas Gleixner 
---
 include/uapi/linux/futex.h |1 +
 kernel/futex.c |   41 +
 2 files changed, 42 insertions(+)

--- a/include/uapi/linux/futex.h
+++ b/include/uapi/linux/futex.h
@@ -20,6 +20,7 @@
 #define FUTEX_WAKE_BITSET  10
 #define FUTEX_WAIT_REQUEUE_PI  11
 #define FUTEX_CMP_REQUEUE_PI   12
+#define FUTEX_PREALLOC_HASH13
 
 #define FUTEX_PRIVATE_FLAG 128
 #define FUTEX_CLOCK_REALTIME   256
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -3307,6 +3307,45 @@ static void futex_populate_hash(unsigned
 static inline void futex_populate_hash(unsigned int hash_bits) { }
 #endif
 
+/**
+ * futex_preallocate_hash - Preallocate the process private hash
+ * @slots: Number of slots to allocate
+ *
+ * The function will allocate the process private hash with the number of
+ * requested slots. The number is rounded to the next power of two and may not
+ * exceed the current system limit.
+ *
+ * If the hash was already allocated by either an earlier call to
+ * futex_preallocate_hash() or an earlier futex op which allocated the cache
+ * on the fly, we return the size of the active hash.
+ *
+ * Returns::   Size of the hash, if 0 then the global hash is used.
+ */
+static int futex_preallocate_hash(unsigned int slots)
+{
+#ifdef CONFIG_FUTEX_PRIVATE_HASH
+   struct mm_struct *mm = current->mm;
+   struct futex_hash_bucket *hb;
+   unsigned int bits;
+
+   /* Try to allocate the requested nr of slots */
+   bits = order_base_2(slots);
+
+   if (bits < FUTEX_MIN_HASH_BITS)
+   bits = FUTEX_MIN_HASH_BITS;
+
+   if (bits > futex_max_hash_bits)
+   bits = futex_max_hash_bits;
+
+   futex_populate_hash(bits);
+
+   hb = mm->futex_hash.hash;
+   return hb == FUTEX_USE_GLOBAL_HASH ? 0 : 1 << mm->futex_hash.hash_bits;
+#else
+   return 0;
+#endif
+}
+
 long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
u32 __user *uaddr2, u32 val2, u32 val3)
 {
@@ -3362,6 +3401,8 @@ long do_futex(u32 __user *uaddr, int op,
 uaddr2);
case FUTEX_CMP_REQUEUE_PI:
return futex_requeue(uaddr, flags, uaddr2, val, val2, , 1);
+   case FUTEX_PREALLOC_HASH:
+   return futex_preallocate_hash(val);
}
return -ENOSYS;
 }

[patch V2 3/7] futex: Add op for hash preallocation

[Thomas Gleixner]

From: Sebastian Siewior 

The per process hash is allocated on the fly at the first futex operation of a
process. The size of the hash is determined by a system wide default setting
controlled by the sys admin, This is suboptimal for RT applications and
applications with pathological futex abuse,

 - For RT applications its important to allocate the per process hash before the
   first futex operation to avoid the allocation on the first futex operation.

 - For pathological applications which use gazillions of futexes its useful to
   allocate a hash greater than the default hash size.

Add a futex op which allows to preallocate the hash with the requested
size. The size is limited by the systemwide maximum hash size, which can be
set by the admin. The requested size is rounded up to the next order of 2.

The function can be called several times, but ony the first call results in a
hash allocation of the requested size as there is no non-intrusive way to
reallocate/rehash in a multithreaded application.

Note, that this call must be issued before the first futex operation in the
process because that would automatically allocate the default sized hash.

The function returns the actual hash size or 0 if the global hash is used. The
latter is the case on UP and in the rare case that the allocation failed and
the global hash is used as a fallback.

Signed-off-by: Sebastian Siewior 
Signed-off-by: Thomas Gleixner 
---
 include/uapi/linux/futex.h |1 +
 kernel/futex.c |   41 +
 2 files changed, 42 insertions(+)

--- a/include/uapi/linux/futex.h
+++ b/include/uapi/linux/futex.h
@@ -20,6 +20,7 @@
 #define FUTEX_WAKE_BITSET  10
 #define FUTEX_WAIT_REQUEUE_PI  11
 #define FUTEX_CMP_REQUEUE_PI   12
+#define FUTEX_PREALLOC_HASH13
 
 #define FUTEX_PRIVATE_FLAG 128
 #define FUTEX_CLOCK_REALTIME   256
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -3307,6 +3307,45 @@ static void futex_populate_hash(unsigned
 static inline void futex_populate_hash(unsigned int hash_bits) { }
 #endif
 
+/**
+ * futex_preallocate_hash - Preallocate the process private hash
+ * @slots: Number of slots to allocate
+ *
+ * The function will allocate the process private hash with the number of
+ * requested slots. The number is rounded to the next power of two and may not
+ * exceed the current system limit.
+ *
+ * If the hash was already allocated by either an earlier call to
+ * futex_preallocate_hash() or an earlier futex op which allocated the cache
+ * on the fly, we return the size of the active hash.
+ *
+ * Returns::   Size of the hash, if 0 then the global hash is used.
+ */
+static int futex_preallocate_hash(unsigned int slots)
+{
+#ifdef CONFIG_FUTEX_PRIVATE_HASH
+   struct mm_struct *mm = current->mm;
+   struct futex_hash_bucket *hb;
+   unsigned int bits;
+
+   /* Try to allocate the requested nr of slots */
+   bits = order_base_2(slots);
+
+   if (bits < FUTEX_MIN_HASH_BITS)
+   bits = FUTEX_MIN_HASH_BITS;
+
+   if (bits > futex_max_hash_bits)
+   bits = futex_max_hash_bits;
+
+   futex_populate_hash(bits);
+
+   hb = mm->futex_hash.hash;
+   return hb == FUTEX_USE_GLOBAL_HASH ? 0 : 1 << mm->futex_hash.hash_bits;
+#else
+   return 0;
+#endif
+}
+
 long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
u32 __user *uaddr2, u32 val2, u32 val3)
 {
@@ -3362,6 +3401,8 @@ long do_futex(u32 __user *uaddr, int op,
 uaddr2);
case FUTEX_CMP_REQUEUE_PI:
return futex_requeue(uaddr, flags, uaddr2, val, val2, , 1);
+   case FUTEX_PREALLOC_HASH:
+   return futex_preallocate_hash(val);
}
return -ENOSYS;
 }