From: Rasmus Villemoes <linux@rasmusvillemoes.dk>
To: Ilya Dryomov <idryomov@gmail.com>
Cc: David Howells <dhowells@redhat.com>,
Linus Torvalds <torvalds@linux-foundation.org>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
Peter Zijlstra <peterz@infradead.org>,
nicolas.dichtel@6wind.com, raven@themaw.net,
Christian Brauner <christian@brauner.io>,
keyrings@vger.kernel.org, linux-usb@vger.kernel.org,
linux-block <linux-block@vger.kernel.org>,
linux-security-module@vger.kernel.org,
linux-fsdevel <linux-fsdevel@vger.kernel.org>,
linux-api@vger.kernel.org, LKML <linux-kernel@vger.kernel.org>
Subject: Re: [RFC PATCH 04/10] pipe: Use head and tail pointers for the ring, not cursor and length [ver #2]
Date: Wed, 30 Oct 2019 23:38:38 +0100 [thread overview]
Message-ID: <d08d13d9-8eee-9c1e-2f8d-e846063882d7@rasmusvillemoes.dk> (raw)
In-Reply-To: <CAOi1vP9paV2-2_S0NgfbZDE6+5kqHXVc9xabHVC-2Ss1MmXkCg@mail.gmail.com>
On 30/10/2019 23.16, Ilya Dryomov wrote:
> On Wed, Oct 30, 2019 at 9:35 PM Rasmus Villemoes
> <linux@rasmusvillemoes.dk> wrote:
>>
>> On 30/10/2019 17.19, Ilya Dryomov wrote:
>>> On Thu, Oct 24, 2019 at 11:49 AM David Howells <dhowells@redhat.com> wrote:
>>>> /*
>>>> - * We use a start+len construction, which provides full use of the
>>>> - * allocated memory.
>>>> - * -- Florian Coosmann (FGC)
>>>> - *
>>>> + * We use head and tail indices that aren't masked off, except at the point of
>>>> + * dereference, but rather they're allowed to wrap naturally. This means there
>>>> + * isn't a dead spot in the buffer, provided the ring size < INT_MAX.
>>>> + * -- David Howells 2019-09-23.
>>>
>>> Hi David,
>>>
>>> Is "ring size < INT_MAX" constraint correct?
>>
>> No. As long as one always uses a[idx % size] to access the array, the
>> only requirement is that size is representable in an unsigned int. Then
>> because one also wants to do the % using simple bitmasking, that further
>> restricts one to sizes that are a power of 2, so the end result is that
>> the max size is 2^31 (aka INT_MAX+1).
>
> I think the fact that indices are free running and wrap at a power of
> two already restricts you to sizes the are a power of two,
Ah, yes, of course. When reducing indices mod n that may already have
been implicitly reduced mod N, N must be a multiple of n for the result
to be well-defined.
Rasmus
next prev parent reply other threads:[~2019-10-30 22:38 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-23 20:17 [RFC PATCH 00/10] pipe: Notification queue preparation [ver #2] David Howells
2019-10-23 20:17 ` [RFC PATCH 01/10] pipe: Reduce #inclusion of pipe_fs_i.h " David Howells
2019-10-23 20:17 ` [RFC PATCH 02/10] Remove the nr_exclusive argument from __wake_up_sync_key() " David Howells
2019-10-23 20:17 ` [RFC PATCH 03/10] Add wake_up_interruptible_sync_poll_locked() " David Howells
2019-10-23 20:17 ` [RFC PATCH 04/10] pipe: Use head and tail pointers for the ring, not cursor and length " David Howells
2019-10-26 14:58 ` [pipe] 6567a02d20: BUG:kernel_NULL_pointer_dereference,address kernel test robot
2019-10-27 14:03 ` [RFC PATCH 04/10] pipe: Use head and tail pointers for the ring, not cursor and length [ver #2] Linus Torvalds
2019-10-30 16:19 ` Ilya Dryomov
2019-10-30 20:35 ` Rasmus Villemoes
2019-10-30 22:16 ` Ilya Dryomov
2019-10-30 22:38 ` Rasmus Villemoes [this message]
2019-10-31 15:11 ` David Howells
2019-10-31 15:57 ` Ilya Dryomov
2019-11-01 14:53 ` David Howells
2019-10-31 14:57 ` David Howells
2019-11-03 11:17 ` Matthew Wilcox
2019-12-06 21:47 ` Johannes Hirte
2019-12-06 22:14 ` Linus Torvalds
2019-12-07 0:00 ` Johannes Hirte
2019-12-07 1:03 ` Linus Torvalds
2019-12-08 17:56 ` Johannes Hirte
2019-12-08 18:10 ` Linus Torvalds
2019-12-07 6:47 ` Linus Torvalds
2019-12-06 22:15 ` David Howells
2019-10-23 20:17 ` [RFC PATCH 05/10] pipe: Allow pipes to have kernel-reserved slots " David Howells
2019-10-23 20:18 ` [RFC PATCH 06/10] pipe: Advance tail pointer inside of wait spinlock in pipe_read() " David Howells
2019-10-23 20:18 ` [RFC PATCH 07/10] pipe: Conditionalise wakeup " David Howells
2019-10-27 15:57 ` Konstantin Khlebnikov
2019-10-31 15:21 ` David Howells
2019-10-31 16:38 ` David Howells
2019-11-03 11:04 ` Konstantin Khlebnikov
2019-10-23 20:18 ` [RFC PATCH 08/10] pipe: Rearrange sequence in pipe_write() to preallocate slot " David Howells
2019-10-23 20:18 ` [RFC PATCH 09/10] pipe: Remove redundant wakeup from pipe_write() " David Howells
2019-10-23 20:18 ` [RFC PATCH 10/10] pipe: Check for ring full inside of the spinlock in " David Howells
2019-10-24 10:32 ` [RFC PATCH 04/10] pipe: Use head and tail pointers for the ring, not cursor and length " David Howells
2019-10-24 13:14 ` [RFC PATCH 00/10] pipe: Notification queue preparation " Peter Zijlstra
2019-10-24 16:57 ` [RFC PATCH 11/10] pipe: Add fsync() support " David Howells
2019-10-24 21:29 ` Linus Torvalds
2019-10-25 8:34 ` David Howells
2019-10-27 15:22 ` Christoph Hellwig
2019-10-27 16:04 ` Konstantin Khlebnikov
2019-10-31 15:13 ` David Howells
2019-10-31 15:15 ` David Howells
2019-11-02 18:53 ` Linus Torvalds
2019-11-02 19:34 ` David Howells
2019-11-02 20:31 ` Andy Lutomirski
2019-11-02 22:03 ` Linus Torvalds
2019-11-02 22:09 ` Linus Torvalds
2019-11-02 22:30 ` Andy Lutomirski
2019-11-02 23:02 ` Linus Torvalds
2019-11-02 23:09 ` Linus Torvalds
2019-11-02 23:14 ` Andy Lutomirski
2019-11-03 12:02 ` Konstantin Khlebnikov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d08d13d9-8eee-9c1e-2f8d-e846063882d7@rasmusvillemoes.dk \
--to=linux@rasmusvillemoes.dk \
--cc=christian@brauner.io \
--cc=dhowells@redhat.com \
--cc=gregkh@linuxfoundation.org \
--cc=idryomov@gmail.com \
--cc=keyrings@vger.kernel.org \
--cc=linux-api@vger.kernel.org \
--cc=linux-block@vger.kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-security-module@vger.kernel.org \
--cc=linux-usb@vger.kernel.org \
--cc=nicolas.dichtel@6wind.com \
--cc=peterz@infradead.org \
--cc=raven@themaw.net \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).