* Re: Re: [PATCH 4/3] random: use siphash24 instead of md5 for get_random_int/long
From: Jason A. Donenfeld @ 2016-12-15 1:19 UTC (permalink / raw)
To: kernel-hardening, Theodore Ts'o, Jason A. Donenfeld, Netdev,
David Miller, Linus Torvalds, LKML, George Spelvin, Scott Bauer,
Andi Kleen, Andy Lutomirski, Greg KH, Eric Biggers,
Linux Crypto Mailing List, Jean-Philippe Aumasson
In-Reply-To: <CAHmME9o3uQoi5h=YTKB=5yN1yzz=d3=GFjGiXv_Sf12kAsjx3A@mail.gmail.com>
Hey Ted,
On Wed, Dec 14, 2016 at 8:12 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> I think this opens up a big window for optimizing it even
> further.
I optimized it a bit further and siphash is now the clear winner over chacha:
[ 1.784801] random benchmark!!
[ 1.785161] get_random_long # cycles: 415983
[ 1.785595] get_random_long_chacha # cycles: 242047
[ 1.785997] get_random_long_siphash # cycles: 137130
[ 1.787450] get_random_bytes # cycles: 1452985
[ 1.787947] get_random_int # cycles: 343323
[ 1.788282] get_random_int_chacha # cycles: 170767
[ 1.788656] get_random_int_siphash # cycles: 86384
[ 1.789764] get_random_bytes # cycles: 2279519
And even still, there is more that could be optimized. Therefore, I'll
continue to keep this patch in the series and will CC you on the next
patch set that goes out.
Jason
^ permalink raw reply
* RE: [Qemu-devel] [PATCH v7 1/1] crypto: add virtio-crypto driver
From: Gonglei (Arei) @ 2016-12-15 1:08 UTC (permalink / raw)
To: Zeng, Xin, Halil Pasic, linux-kernel@vger.kernel.org,
qemu-devel@nongnu.org, virtio-dev@lists.oasis-open.org,
virtualization@lists.linux-foundation.org,
linux-crypto@vger.kernel.org
Cc: Huangweidong (C), Claudio Fontana, mst@redhat.com, Luonengjun,
Hanweidong (Randy), Xuquan (Quan Xu), Wanzongshun (Vincent),
stefanha@redhat.com, Zhoujian (jay, Euler),
cornelia.huck@de.ibm.com, longpeng, arei.gonglei@hotmail.com,
davem@davemloft.net, Wubin (H), herbert@gondor.apana.org.au
In-Reply-To: <82063967A54EF84C8AFCD6BD7F6AD93310C14374@SHSMSX103.ccr.corp.intel.com>
Regards,
-Gonglei
> -----Original Message-----
> From: Zeng, Xin [mailto:xin.zeng@intel.com]
> Sent: Thursday, December 15, 2016 8:59 AM
> To: Gonglei (Arei); Halil Pasic; linux-kernel@vger.kernel.org;
> qemu-devel@nongnu.org; virtio-dev@lists.oasis-open.org;
> virtualization@lists.linux-foundation.org; linux-crypto@vger.kernel.org
> Cc: Huangweidong (C); Claudio Fontana; mst@redhat.com; Luonengjun;
> Hanweidong (Randy); Xuquan (Quan Xu); Wanzongshun (Vincent);
> stefanha@redhat.com; Zhoujian (jay, Euler); cornelia.huck@de.ibm.com;
> longpeng; arei.gonglei@hotmail.com; davem@davemloft.net; Wubin (H);
> herbert@gondor.apana.org.au
> Subject: RE: [Qemu-devel] [PATCH v7 1/1] crypto: add virtio-crypto driver
>
> On Thursday, December 15, 2016 8:45 AM, Gonglei (Arei) Wrote:
> < > > diff --git a/drivers/crypto/virtio/virtio_crypto_core.c
> < > b/drivers/crypto/virtio/virtio_crypto_core.c
> < > > new file mode 100644
> < > > index 0000000..c0854a1
> < > > --- /dev/null
> < > > +++ b/drivers/crypto/virtio/virtio_crypto_core.c
> < > > @@ -0,0 +1,474 @@
> < > [..]
> < > > +
> < > > +static void virtcrypto_dataq_callback(struct virtqueue *vq)
> < > > +{
> < > > + struct virtio_crypto *vcrypto = vq->vdev->priv;
> < > > + struct virtio_crypto_request *vc_req;
> < > > + unsigned long flags;
> < > > + unsigned int len;
> < > > + struct ablkcipher_request *ablk_req;
> < > > + int error;
> < > > +
> < > > + spin_lock_irqsave(&vcrypto->lock, flags);
> < >
> < > Would it make sense to use a per virtqueue lock
> < > like in virtio_blk for example instead of locking on the whole
> < > device? OK, it seems you use only one dataqueue, so it
> < > may not be that relevant.
> < >
> < Currently yes, both the backend device (cryptodev-backend-builtin)
> < and the frontend driver use one dataqueue.
> <
>
> I think it makes sense to use per virtqueue lock here though it only uses one
> queue so far,
> but in the spec we already have multi queues support.
>
Yes, I agree. Will do that in V8 soon.
Hope to catch up with Michael's pull request for 4.10.
Regards,
-Gonglei
^ permalink raw reply
* RE: [Qemu-devel] [PATCH v7 1/1] crypto: add virtio-crypto driver
From: Zeng, Xin @ 2016-12-15 0:59 UTC (permalink / raw)
To: Gonglei (Arei), Halil Pasic, linux-kernel@vger.kernel.org,
qemu-devel@nongnu.org, virtio-dev@lists.oasis-open.org,
virtualization@lists.linux-foundation.org,
linux-crypto@vger.kernel.org
Cc: Xuquan (Quan Xu), Huangweidong (C), herbert@gondor.apana.org.au,
Hanweidong (Randy), Claudio Fontana, mst@redhat.com, Luonengjun,
Wanzongshun (Vincent), stefanha@redhat.com, Zhoujian (jay, Euler),
longpeng, davem@davemloft.net, Wubin (H),
arei.gonglei@hotmail.com
In-Reply-To: <33183CC9F5247A488A2544077AF19020DA163033@DGGEMA505-MBX.china.huawei.com>
On Thursday, December 15, 2016 8:45 AM, Gonglei (Arei) Wrote:
< > > diff --git a/drivers/crypto/virtio/virtio_crypto_core.c
< > b/drivers/crypto/virtio/virtio_crypto_core.c
< > > new file mode 100644
< > > index 0000000..c0854a1
< > > --- /dev/null
< > > +++ b/drivers/crypto/virtio/virtio_crypto_core.c
< > > @@ -0,0 +1,474 @@
< > [..]
< > > +
< > > +static void virtcrypto_dataq_callback(struct virtqueue *vq)
< > > +{
< > > + struct virtio_crypto *vcrypto = vq->vdev->priv;
< > > + struct virtio_crypto_request *vc_req;
< > > + unsigned long flags;
< > > + unsigned int len;
< > > + struct ablkcipher_request *ablk_req;
< > > + int error;
< > > +
< > > + spin_lock_irqsave(&vcrypto->lock, flags);
< >
< > Would it make sense to use a per virtqueue lock
< > like in virtio_blk for example instead of locking on the whole
< > device? OK, it seems you use only one dataqueue, so it
< > may not be that relevant.
< >
< Currently yes, both the backend device (cryptodev-backend-builtin)
< and the frontend driver use one dataqueue.
<
I think it makes sense to use per virtqueue lock here though it only uses one queue so far,
but in the spec we already have multi queues support.
< Regards,
< -Gonglei
^ permalink raw reply
* RE: [Qemu-devel] [PATCH v7 1/1] crypto: add virtio-crypto driver
From: Gonglei (Arei) @ 2016-12-15 0:45 UTC (permalink / raw)
To: Halil Pasic, linux-kernel@vger.kernel.org, qemu-devel@nongnu.org,
virtio-dev@lists.oasis-open.org,
virtualization@lists.linux-foundation.org,
linux-crypto@vger.kernel.org
Cc: Xuquan (Quan Xu), Huangweidong (C), herbert@gondor.apana.org.au,
Hanweidong (Randy), Claudio Fontana, mst@redhat.com, Luonengjun,
Wanzongshun (Vincent), stefanha@redhat.com, Zhoujian (jay, Euler),
longpeng, davem@davemloft.net, Wubin (H),
arei.gonglei@hotmail.com
In-Reply-To: <bcf62fa0-8fc9-daaf-ea7b-e09eb83b593a@linux.vnet.ibm.com>
>
>
> On 12/14/2016 12:50 PM, Gonglei wrote:
> > diff --git a/drivers/crypto/virtio/virtio_crypto_core.c
> b/drivers/crypto/virtio/virtio_crypto_core.c
> > new file mode 100644
> > index 0000000..c0854a1
> > --- /dev/null
> > +++ b/drivers/crypto/virtio/virtio_crypto_core.c
> > @@ -0,0 +1,474 @@
> [..]
> > +
> > +static void virtcrypto_dataq_callback(struct virtqueue *vq)
> > +{
> > + struct virtio_crypto *vcrypto = vq->vdev->priv;
> > + struct virtio_crypto_request *vc_req;
> > + unsigned long flags;
> > + unsigned int len;
> > + struct ablkcipher_request *ablk_req;
> > + int error;
> > +
> > + spin_lock_irqsave(&vcrypto->lock, flags);
>
> Would it make sense to use a per virtqueue lock
> like in virtio_blk for example instead of locking on the whole
> device? OK, it seems you use only one dataqueue, so it
> may not be that relevant.
>
Currently yes, both the backend device (cryptodev-backend-builtin)
and the frontend driver use one dataqueue.
Regards,
-Gonglei
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Linus Torvalds @ 2016-12-15 0:10 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Tom Herbert, Netdev, kernel-hardening@lists.openwall.com, LKML,
Linux Crypto Mailing List, Jean-Philippe Aumasson,
Daniel J . Bernstein, Eric Biggers, David Laight
In-Reply-To: <CAHmME9pu6No0wqPzPpaBwQR_b+5CXvh0kke7J8ouN=rx4pxMGg@mail.gmail.com>
On Wed, Dec 14, 2016 at 3:34 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Or does your reasonable dislike of "word" still allow for the use of
> dword and qword, so that the current function names of:
dword really is confusing to people.
If you have a MIPS background, it means 64 bits. While to people with
Windows programming backgrounds it means 32 bits.
Please try to avoid using it.
As mentioned, I think almost everybody agrees on the "q" part being 64
bits, but that may just be me not having seen it in any other context.
And before anybody points it out - yes, we already have lots of uses
of "dword" in various places. But they tend to be mostly
hardware-specific - either architectures or drivers.
So I'd _prefer_ to try to keep "word" and "dword" away from generic
helper routines. But it's not like anything is really black and white.
Linus
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 23:34 UTC (permalink / raw)
To: Linus Torvalds
Cc: Tom Herbert, Netdev, kernel-hardening@lists.openwall.com, LKML,
Linux Crypto Mailing List, Jean-Philippe Aumasson,
Daniel J . Bernstein, Eric Biggers, David Laight
In-Reply-To: <CA+55aFyBGQpEKiAcs0w58ZEie+L8OrWvf_2hvGx4E=L56p5hMg@mail.gmail.com>
Hey Linus,
On Thu, Dec 15, 2016 at 12:30 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> No. The bug is talking about "words" in the first place.
>
> Depending on your background, a "word" can be generally be either 16
> bits or 32 bits (or, in some cases, 18 bits).
>
> In theory, a 64-bit entity can be a "word" too, but pretty much nobody
> uses that. Even architectures that started out with a 64-bit register
> size and never had any smaller historical baggage (eg alpha) tend to
> call 32-bit entities "words".
>
> So 16 bits can be a word, but some people/architectures will call it a
> "half-word".
>
> To make matters even more confusing, a "quadword" is generally always
> 64 bits, regardless of the size of "word".
>
> So please try to avoid the use of "word" entirely. It's too ambiguous,
> and it's not even helpful as a "size of the native register". It's
> almost purely random.
>
> For the kernel, we tend use
>
> - uX for types that have specific sizes (X being the number of bits)
>
> - "[unsigned] long" for native register size
>
> But never "word".
The voice of reason. Have a desired name for this function family?
siphash_3u64s
siphash_3u64
siphash_three_u64
siphash_3sixityfourbitintegers
Or does your reasonable dislike of "word" still allow for the use of
dword and qword, so that the current function names of:
siphash_3qwords
siphash_6dwords
are okay?
Jason
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Linus Torvalds @ 2016-12-14 23:30 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Tom Herbert, Netdev, kernel-hardening@lists.openwall.com, LKML,
Linux Crypto Mailing List, Jean-Philippe Aumasson,
Daniel J . Bernstein, Eric Biggers, David Laight
In-Reply-To: <CAHmME9rpvf4tyDjZcJAJxMAW1LcqNm7DiquiYX0uQhRzDLbwqw@mail.gmail.com>
On Wed, Dec 14, 2016 at 2:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> So actually jhash_Nwords makes no sense, since it takes dwords
> (32-bits) not words (16-bits). The siphash analog should be called
> siphash24_Nqwords.
No. The bug is talking about "words" in the first place.
Depending on your background, a "word" can be generally be either 16
bits or 32 bits (or, in some cases, 18 bits).
In theory, a 64-bit entity can be a "word" too, but pretty much nobody
uses that. Even architectures that started out with a 64-bit register
size and never had any smaller historical baggage (eg alpha) tend to
call 32-bit entities "words".
So 16 bits can be a word, but some people/architectures will call it a
"half-word".
To make matters even more confusing, a "quadword" is generally always
64 bits, regardless of the size of "word".
So please try to avoid the use of "word" entirely. It's too ambiguous,
and it's not even helpful as a "size of the native register". It's
almost purely random.
For the kernel, we tend use
- uX for types that have specific sizes (X being the number of bits)
- "[unsigned] long" for native register size
But never "word".
Linus
^ permalink raw reply
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 23:29 UTC (permalink / raw)
To: Hannes Frederic Sowa
Cc: David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson,
LKML, Linux Crypto Mailing List, Daniel J . Bernstein,
Linus Torvalds, Eric Biggers
In-Reply-To: <8ea3fdff-23c4-b81d-2588-44549bd2d8c1@stressinduktion.org>
Hi Hannes,
On Wed, Dec 14, 2016 at 11:03 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> I fear that the alignment requirement will be a source of bugs on 32 bit
> machines, where you cannot even simply take a well aligned struct on a
> stack and put it into the normal siphash(aligned) function without
> adding alignment annotations everywhere. Even blocks returned from
> kmalloc on 32 bit are not aligned to 64 bit.
That's what the "__aligned(SIPHASH24_ALIGNMENT)" attribute is for. The
aligned siphash function will be for structs explicitly made for
siphash consumption. For everything else there's siphash_unaligned.
> Can we do this a runtime check and just have one function (siphash)
> dealing with that?
Seems like the runtime branching on the aligned function would be bad
for performance, when we likely know at compile time if it's going to
be aligned or not. I suppose we could add that check just to the
unaligned version, and rename it to "maybe_unaligned"? Is this what
you have in mind?
Jason
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 23:17 UTC (permalink / raw)
To: Tom Herbert
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers, David Laight
In-Reply-To: <CALx6S349hOFhnMgM_TgKXC1O7bmOvR87Nm=5B7_sNLEWiZU8Zg@mail.gmail.com>
Hey Tom,
On Thu, Dec 15, 2016 at 12:14 AM, Tom Herbert <tom@herbertland.com> wrote:
> I'm confused, doesn't 2dword == 1qword? Anyway, I think the qword
> functions are good enough. If someone needs to hash over some odd
> length they can either put them in a structure padded to 64 bits or
> call the hash function that takes a byte length.
Yes. Here's an example:
static inline u64 siphash24_2dwords(const u32 a, const u32 b, const u8
key[SIPHASH24_KEY_LEN])
{
return siphash24_1qword(((u64)b << 32) | a, key);
}
This winds up being extremely useful and syntactically convenient in a
few places. Check out my git branch in about 10 minutes or wait for v4
to be posted tomorrow; these are nice helpers.
> I'd still drop the "24" unless you really think we're going to have
> multiple variants coming into the kernel.
Okay. I don't have a problem with this, unless anybody has some reason
to the contrary.
Jason
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Tom Herbert @ 2016-12-14 23:14 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers, David Laight
In-Reply-To: <CAHmME9rpvf4tyDjZcJAJxMAW1LcqNm7DiquiYX0uQhRzDLbwqw@mail.gmail.com>
On Wed, Dec 14, 2016 at 2:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Hey Tom,
>
> On Wed, Dec 14, 2016 at 10:35 PM, Tom Herbert <tom@herbertland.com> wrote:
>> Those look good, although I would probably just do 1,2,3 words and
>> then have a function that takes n words like jhash. Might want to call
>> these dword to distinguish from 32 bit words in jhash.
>
> So actually jhash_Nwords makes no sense, since it takes dwords
> (32-bits) not words (16-bits). The siphash analog should be called
> siphash24_Nqwords.
>
Yeah, that's a "bug" with jhash function names.
> I think what I'll do is change what I already have to:
> siphash24_1qword
> siphash24_2qword
> siphash24_3qword
> siphash24_4qword
>
> And then add some static inline helpers to assist with smaller u32s
> like ipv4 addresses called:
>
> siphash24_2dword
> siphash24_4dword
> siphash24_6dword
> siphash24_8dword
>
> While we're having something new, might as well call it the right thing.
>
I'm confused, doesn't 2dword == 1qword? Anyway, I think the qword
functions are good enough. If someone needs to hash over some odd
length they can either put them in a structure padded to 64 bits or
call the hash function that takes a byte length.
>
>> Also, what is the significance of "24" in the function and constant
>> names? Can we just drop that and call this siphash?
>
> SipHash is actually a family of PRFs, differentiated by the number of
> SIPROUNDs after each 64-bit input is processed and the number of
> SIPROUNDs at the very end of the function. The best trade-off of speed
> and security for kernel usage is 2 rounds after each 64-bit input and
> 4 rounds at the end of the function. This doesn't fall to any known
> cryptanalysis and it's very fast.
I'd still drop the "24" unless you really think we're going to have
multiple variants coming into the kernel.
Tom
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 22:56 UTC (permalink / raw)
To: Tom Herbert
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers, David Laight
In-Reply-To: <CALx6S35VBjw42G6rHPrNfVaBfLMz3YZVjs3D3hBG=4gp5+g5tA@mail.gmail.com>
Hey Tom,
On Wed, Dec 14, 2016 at 10:35 PM, Tom Herbert <tom@herbertland.com> wrote:
> Those look good, although I would probably just do 1,2,3 words and
> then have a function that takes n words like jhash. Might want to call
> these dword to distinguish from 32 bit words in jhash.
So actually jhash_Nwords makes no sense, since it takes dwords
(32-bits) not words (16-bits). The siphash analog should be called
siphash24_Nqwords.
I think what I'll do is change what I already have to:
siphash24_1qword
siphash24_2qword
siphash24_3qword
siphash24_4qword
And then add some static inline helpers to assist with smaller u32s
like ipv4 addresses called:
siphash24_2dword
siphash24_4dword
siphash24_6dword
siphash24_8dword
While we're having something new, might as well call it the right thing.
> Also, what is the significance of "24" in the function and constant
> names? Can we just drop that and call this siphash?
SipHash is actually a family of PRFs, differentiated by the number of
SIPROUNDs after each 64-bit input is processed and the number of
SIPROUNDs at the very end of the function. The best trade-off of speed
and security for kernel usage is 2 rounds after each 64-bit input and
4 rounds at the end of the function. This doesn't fall to any known
cryptanalysis and it's very fast.
^ permalink raw reply
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function
From: Hannes Frederic Sowa @ 2016-12-14 22:03 UTC (permalink / raw)
To: Jason A. Donenfeld, David Laight
Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML,
Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers
In-Reply-To: <CAHmME9q9ffdtWRbzyMO1ktTdtEFdfumTfojTTNLXFhoa+R+MWQ@mail.gmail.com>
On 14.12.2016 13:46, Jason A. Donenfeld wrote:
> Hi David,
>
> On Wed, Dec 14, 2016 at 10:56 AM, David Laight <David.Laight@aculab.com> wrote:
>> ...
>>> +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN])
>> ...
>>> + u64 k0 = get_unaligned_le64(key);
>>> + u64 k1 = get_unaligned_le64(key + sizeof(u64));
>> ...
>>> + m = get_unaligned_le64(data);
>>
>> All these unaligned accesses are going to get expensive on architectures
>> like sparc64.
>
> Yes, the unaligned accesses aren't pretty. Since in pretty much all
> use cases thus far, the data can easily be made aligned, perhaps it
> makes sense to create siphash24() and siphash24_unaligned(). Any
> thoughts on doing something like that?
I fear that the alignment requirement will be a source of bugs on 32 bit
machines, where you cannot even simply take a well aligned struct on a
stack and put it into the normal siphash(aligned) function without
adding alignment annotations everywhere. Even blocks returned from
kmalloc on 32 bit are not aligned to 64 bit.
Can we do this a runtime check and just have one function (siphash)
dealing with that?
Bye,
Hannes
^ permalink raw reply
* Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long
From: kbuild test robot @ 2016-12-14 21:57 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto,
Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso
In-Reply-To: <20161214184605.24006-3-Jason@zx2c4.com>
[-- Attachment #1: Type: text/plain, Size: 1528 bytes --]
Hi Jason,
[auto build test ERROR on linus/master]
[also build test ERROR on next-20161214]
[cannot apply to v4.9]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458
config: openrisc-or1ksim_defconfig (attached as .config)
compiler: or32-linux-gcc (GCC) 4.5.1-or32-1.0rc1
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=openrisc
All errors (new ones prefixed by >>):
>> drivers/char/random.c:2046:1: error: requested alignment is not a constant
drivers/char/random.c: In function 'get_random_int':
drivers/char/random.c:2071:2: error: requested alignment is not a constant
drivers/char/random.c: In function 'get_random_long':
drivers/char/random.c:2100:2: error: requested alignment is not a constant
vim +2046 drivers/char/random.c
2040 },
2041 #endif
2042 { }
2043 };
2044 #endif /* CONFIG_SYSCTL */
2045
> 2046 static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT);
2047
2048 int random_int_secret_init(void)
2049 {
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 7325 bytes --]
^ permalink raw reply
* Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long
From: kbuild test robot @ 2016-12-14 21:56 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto,
Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso
In-Reply-To: <20161214184605.24006-3-Jason@zx2c4.com>
[-- Attachment #1: Type: text/plain, Size: 1583 bytes --]
Hi Jason,
[auto build test ERROR on linus/master]
[also build test ERROR on next-20161214]
[cannot apply to v4.9]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458
config: i386-randconfig-i1-201650 (attached as .config)
compiler: gcc-4.8 (Debian 4.8.4-1) 4.8.4
reproduce:
# save the attached .config to linux build tree
make ARCH=i386
All errors (new ones prefixed by >>):
>> drivers/char/random.c:2046:1: error: requested alignment is not an integer constant
static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT);
^
drivers/char/random.c: In function 'get_random_int':
drivers/char/random.c:2071:2: error: requested alignment is not an integer constant
} __aligned(SIPHASH24_ALIGNMENT) combined;
^
drivers/char/random.c: In function 'get_random_long':
drivers/char/random.c:2100:2: error: requested alignment is not an integer constant
} __aligned(SIPHASH24_ALIGNMENT) combined;
^
vim +2046 drivers/char/random.c
2040 },
2041 #endif
2042 { }
2043 };
2044 #endif /* CONFIG_SYSCTL */
2045
> 2046 static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT);
2047
2048 int random_int_secret_init(void)
2049 {
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 26712 bytes --]
^ permalink raw reply
* Re: [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform
From: kbuild test robot @ 2016-12-14 21:44 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto,
Jason A. Donenfeld, Andi Kleen, David Miller, David Laight
In-Reply-To: <20161214184605.24006-2-Jason@zx2c4.com>
[-- Attachment #1: Type: text/plain, Size: 1635 bytes --]
Hi Jason,
[auto build test ERROR on linus/master]
[also build test ERROR on next-20161214]
[cannot apply to v4.9]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458
config: openrisc-or1ksim_defconfig (attached as .config)
compiler: or32-linux-gcc (GCC) 4.5.1-or32-1.0rc1
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=openrisc
All errors (new ones prefixed by >>):
>> net/core/secure_seq.c:20:1: error: requested alignment is not a constant
net/core/secure_seq.c: In function 'secure_tcp_sequence_number':
net/core/secure_seq.c:99:2: error: requested alignment is not a constant
net/core/secure_seq.c: In function 'secure_ipv4_port_ephemeral':
net/core/secure_seq.c:119:2: error: requested alignment is not a constant
vim +20 net/core/secure_seq.c
14 #include <net/secure_seq.h>
15
16 #if IS_ENABLED(CONFIG_IPV6) || IS_ENABLED(CONFIG_INET)
17 #include <linux/in6.h>
18 #include <net/tcp.h>
19
> 20 static u8 net_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT);
21
22 static __always_inline void net_secret_init(void)
23 {
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 7325 bytes --]
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Tom Herbert @ 2016-12-14 21:35 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers, David Laight
In-Reply-To: <CAHmME9pR3tD2zknKsYaFaTJm_3aBBOA6c174hypm6S-q9wp5nw@mail.gmail.com>
On Wed, Dec 14, 2016 at 12:55 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Hey Tom,
>
> Just following up on what I mentioned in my last email...
>
> On Wed, Dec 14, 2016 at 8:35 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>> I think your suggestion for (2) will contribute to further
>> optimizations for (1). In v2, I had another patch in there adding
>> siphash_1word, siphash_2words, etc, like jhash, but I implemented it
>> by taking u32 variables and then just concatenating these into a
>> buffer and passing them to the main siphash function. I removed it
>> from v3 because I thought that these kind of missed the whole point.
>> In particular:
>>
>> a) siphash24_1word, siphash24_2words, siphash24_3words, etc should
>> take u64, not u32, since that's what siphash operates on natively
>
> I implemented these here:
> https://git.zx2c4.com/linux-dev/commit/?h=siphash&id=4652b6f3643bdba217e2194d89661348bbac48a0
>
Those look good, although I would probably just do 1,2,3 words and
then have a function that takes n words like jhash. Might want to call
these dword to distinguish from 32 bit words in jhash.
Also, what is the significance of "24" in the function and constant
names? Can we just drop that and call this siphash?
Tom
> This will be part of the next version of the series I submit. It's not
> immediately clear that using it is strictly faster than the struct
> trick though. However, I'm not yet sure why this would be.
>
> Jason
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 21:21 UTC (permalink / raw)
To: kbuild test robot
Cc: kbuild-all, Netdev, kernel-hardening, LKML,
Linux Crypto Mailing List, Jean-Philippe Aumasson,
Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight
In-Reply-To: <201612150515.xggXiOp3%fengguang.wu@intel.com>
Interesting. Evidently gcc 4.8 doesn't like my use of:
enum siphash_lengths {
SIPHASH24_KEY_LEN = 16,
SIPHASH24_ALIGNMENT = 8
};
I'll convert this to the more boring:
#define SIPHASH24_KEY_LEN 16
#define SIPHASH24_ALIGNMENT 8
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: kbuild test robot @ 2016-12-14 21:15 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto,
Jason A. Donenfeld, Jean-Philippe Aumasson, Daniel J . Bernstein,
Linus Torvalds, Eric Biggers, David Laight
In-Reply-To: <20161214184605.24006-1-Jason@zx2c4.com>
[-- Attachment #1: Type: text/plain, Size: 1420 bytes --]
Hi Jason,
[auto build test ERROR on linus/master]
[also build test ERROR on v4.9 next-20161214]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458
config: i386-randconfig-i1-201650 (attached as .config)
compiler: gcc-4.8 (Debian 4.8.4-1) 4.8.4
reproduce:
# save the attached .config to linux build tree
make ARCH=i386
All errors (new ones prefixed by >>):
lib/test_siphash.c: In function 'siphash_test_init':
>> lib/test_siphash.c:49:2: error: requested alignment is not an integer constant
u8 in[64] __aligned(SIPHASH24_ALIGNMENT);
^
lib/test_siphash.c:50:2: error: requested alignment is not an integer constant
u8 k[16] __aligned(SIPHASH24_ALIGNMENT);
^
vim +49 lib/test_siphash.c
43 0x6ca4ecb15c5f91e1ULL, 0x9f626da15c9625f3ULL, 0xe51b38608ef25f57ULL,
44 0x958a324ceb064572ULL
45 };
46
47 static int __init siphash_test_init(void)
48 {
> 49 u8 in[64] __aligned(SIPHASH24_ALIGNMENT);
50 u8 k[16] __aligned(SIPHASH24_ALIGNMENT);
51 u8 in_unaligned[65];
52 u8 k_unaligned[65];
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 26712 bytes --]
^ permalink raw reply
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform
From: Jason A. Donenfeld @ 2016-12-14 21:01 UTC (permalink / raw)
To: Tom Herbert
Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML,
Linux Crypto Mailing List
In-Reply-To: <CALx6S37mGaLJoacxyu3_ZQANSNz9UU38-b-V6g1nma=Gye3pjw@mail.gmail.com>
On Wed, Dec 14, 2016 at 9:12 PM, Tom Herbert <tom@herbertland.com> wrote:
> If you pad the data structure to 64 bits then we can call the version
> of siphash that only deals in 64 bit words. Writing a zero in the
> padding will be cheaper than dealing with odd lengths in siphash24.
On Wed, Dec 14, 2016 at 9:27 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> What I don't really understand is that the addition of this complexity
> actually reduces the performance, as you have to take the "if (left)"
> branch during hashing and causes you to make a load_unaligned_zeropad.
Oh, duh, you guys are right. Fixed in my repo [1]. I'll submit the
next version in a day or so to let some other comments come in.
Thanks again for your reviews.
Jason
[1] https://git.zx2c4.com/linux-dev/log/?h=siphash
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 20:55 UTC (permalink / raw)
To: Tom Herbert
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers, David Laight
In-Reply-To: <CAHmME9oMaQOhzJbNKh8GN759iJngeRdXt3naOnFhY9mD6t5Kxg@mail.gmail.com>
Hey Tom,
Just following up on what I mentioned in my last email...
On Wed, Dec 14, 2016 at 8:35 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> I think your suggestion for (2) will contribute to further
> optimizations for (1). In v2, I had another patch in there adding
> siphash_1word, siphash_2words, etc, like jhash, but I implemented it
> by taking u32 variables and then just concatenating these into a
> buffer and passing them to the main siphash function. I removed it
> from v3 because I thought that these kind of missed the whole point.
> In particular:
>
> a) siphash24_1word, siphash24_2words, siphash24_3words, etc should
> take u64, not u32, since that's what siphash operates on natively
I implemented these here:
https://git.zx2c4.com/linux-dev/commit/?h=siphash&id=4652b6f3643bdba217e2194d89661348bbac48a0
This will be part of the next version of the series I submit. It's not
immediately clear that using it is strictly faster than the struct
trick though. However, I'm not yet sure why this would be.
Jason
^ permalink raw reply
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform
From: Hannes Frederic Sowa @ 2016-12-14 20:27 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: David Miller, David Laight, Netdev, kernel-hardening, Andi Kleen,
LKML, Linux Crypto Mailing List
In-Reply-To: <CAHmME9rp2oSCo0eu92jKm00S0eJHz65bJKXRpeS7=_EV6zZNYw@mail.gmail.com>
Hey Jason,
On 14.12.2016 20:38, Jason A. Donenfeld wrote:
> On Wed, Dec 14, 2016 at 8:22 PM, Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
>> I don't think this helps. Did you test it? I don't see reason why
>> padding could be left out between `d' and `end' because of the flexible
>> array member?
>
> Because the type u8 doesn't require any alignment requirements, it can
> nestle right up there cozy with the u16:
>
> zx2c4@thinkpad ~ $ cat a.c
> #include <stdint.h>
> #include <stdio.h>
> #include <stddef.h>
> int main()
> {
> struct {
> uint64_t a;
> uint32_t b;
> uint32_t c;
> uint16_t d;
> char x[];
> } a;
> printf("%zu\n", sizeof(a));
> printf("%zu\n", offsetof(typeof(a), x));
> return 0;
> }
> zx2c4@thinkpad ~ $ gcc a.c
> zx2c4@thinkpad ~ $ ./a.out
> 24
> 18
Sorry, I misread the patch. You are using offsetof. In this case remove
the char x[] and just use offsetofend because it is misleading
otherwise. Should work like that though.
What I don't really understand is that the addition of this complexity
actually reduces the performance, as you have to take the "if (left)"
branch during hashing and causes you to make a load_unaligned_zeropad.
Bye,
Hannes
^ permalink raw reply
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform
From: Tom Herbert @ 2016-12-14 20:12 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML,
Linux Crypto Mailing List
In-Reply-To: <CAHmME9pEM=cDC5S=j1BU2oCF8-WdnbRfiVojcet4rXcRLcpJRw@mail.gmail.com>
On Wed, Dec 14, 2016 at 4:53 AM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Hi David,
>
> On Wed, Dec 14, 2016 at 10:51 AM, David Laight <David.Laight@aculab.com> wrote:
>> From: Jason A. Donenfeld
>>> Sent: 14 December 2016 00:17
>>> This gives a clear speed and security improvement. Rather than manually
>>> filling MD5 buffers, we simply create a layout by a simple anonymous
>>> struct, for which gcc generates rather efficient code.
>> ...
>>> + const struct {
>>> + struct in6_addr saddr;
>>> + struct in6_addr daddr;
>>> + __be16 sport;
>>> + __be16 dport;
>>> + } __packed combined = {
>>> + .saddr = *(struct in6_addr *)saddr,
>>> + .daddr = *(struct in6_addr *)daddr,
>>> + .sport = sport,
>>> + .dport = dport
>>> + };
>>
>> You need to look at the effect of marking this (and the other)
>> structures 'packed' on architectures like sparc64.
>
> In all current uses of __packed in the code, I think the impact is
> precisely zero, because all structures have members in descending
> order of size, with each member being a perfect multiple of the one
> below it. The __packed is therefore just there for safety, in case
> somebody comes in and screws everything up by sticking a u8 in
> between. In that case, it wouldn't be desirable to hash the structure
> padding bits. In the worst case, I don't believe the impact would be
> worse than a byte-by-byte memcpy, which is what the old code did. But
> anyway, these structures are already naturally packed anyway, so the
> present impact is nil.
>
If you pad the data structure to 64 bits then we can call the version
of siphash that only deals in 64 bit words. Writing a zero in the
padding will be cheaper than dealing with odd lengths in siphash24.
Tom
> Jason
^ permalink raw reply
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 19:47 UTC (permalink / raw)
To: Hannes Frederic Sowa
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers
In-Reply-To: <9fea41e0-fd55-7328-e2f4-73eb2e7f7a98@stressinduktion.org>
Hi Hannes,
On Wed, Dec 14, 2016 at 4:09 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> Yes, numbers would be very usable here. I am mostly concerned about
> small plastic router cases. E.g. assume you double packet processing
> time with a change of the hashing function at what point is the actual
> packet processing more of an attack vector than the hashtable?
I agree. Looks like Tom did some very quick benchmarks. I'll do some
more precise benchmarks myself when we graduate from looking at md5
replacement (the easy case) to looking at jhash replacement (the
harder case).
>> With that said, siphash is here to replace uses of jhash where
>> hashtable poisoning vulnerabilities make it necessary. Where there's
>> no significant security improvement, if there's no speed improvement
>> either, then of course nothing's going to change.
>
> It still changes currently well working source. ;-)
I mean if siphash doesn't make things better in someway, we'll just
continue using jhash, so no source change or anything. In other words:
evolutionary conservative approach rather than hasty "replace 'em
all!" tomfoolery.
> MD5 is considered broken because its collision resistance is broken?
> SipHash doesn't even claim to have collision resistance (which we don't
> need here)?
Not just that, but it's not immediately clear to me that using MD5 as
a PRF the way it is now with md5_transform is even a straightforwardly
good idea.
> But I agree, certainly it could be a nice speed-up!
The benchmarks for the secure sequence number generation and the rng
are indeed really promising.
> I think you mean non-linearity.
Yea of course, editing typo, sorry.
> In general I am in favor to switch to siphash, but it would be nice to
> see some benchmarks with the specific kernel implementation also on some
> smaller 32 bit CPUs and especially without using any SIMD instructions
> (which might have been used in paper comparison).
Sure, agreed. Each proposed jhash replacement will need to be
benchmarked on little MIPS machines and x86 monsters alike, with
patches indicating PPS before and after.
Jason
^ permalink raw reply
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform
From: Jason A. Donenfeld @ 2016-12-14 19:38 UTC (permalink / raw)
To: Hannes Frederic Sowa
Cc: David Miller, David Laight, Netdev, kernel-hardening, Andi Kleen,
LKML, Linux Crypto Mailing List
In-Reply-To: <0e708ba2-6a4e-013e-597a-62ab32cc240b@stressinduktion.org>
Hi Hannes,
On Wed, Dec 14, 2016 at 8:22 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> I don't think this helps. Did you test it? I don't see reason why
> padding could be left out between `d' and `end' because of the flexible
> array member?
Because the type u8 doesn't require any alignment requirements, it can
nestle right up there cozy with the u16:
zx2c4@thinkpad ~ $ cat a.c
#include <stdint.h>
#include <stdio.h>
#include <stddef.h>
int main()
{
struct {
uint64_t a;
uint32_t b;
uint32_t c;
uint16_t d;
char x[];
} a;
printf("%zu\n", sizeof(a));
printf("%zu\n", offsetof(typeof(a), x));
return 0;
}
zx2c4@thinkpad ~ $ gcc a.c
zx2c4@thinkpad ~ $ ./a.out
24
18
Jason
^ permalink raw reply
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
From: Jason A. Donenfeld @ 2016-12-14 19:35 UTC (permalink / raw)
To: Tom Herbert
Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List,
Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds,
Eric Biggers, David Laight
In-Reply-To: <CALx6S35UgTyqkYUjS5gYFH4HnjW974WQ_JiDXxgb9rZ7gnY52Q@mail.gmail.com>
Hi Tom,
On Wed, Dec 14, 2016 at 8:18 PM, Tom Herbert <tom@herbertland.com> wrote:
> "super fast" is relative. My quick test shows that this faster than
> Toeplitz (good, but not exactly hard to achieve), but is about 4x
> slower than jhash.
Fast relative to other cryptographically secure PRFs.
>> SipHash isn't just some new trendy hash function. It's been around for a
>> while, and there really isn't anything that comes remotely close to
>> being useful in the way SipHash is. With that said, why do we need this?
> I don't think we need advertising nor a lesson on hashing. It would be
> much more useful if you just point us to the paper on siphash (which I
> assume I http://cr.yp.to/siphash/siphash-20120918.pdf ?).
Ugh. Sorry. It definitely wasn't my intention to give an uninvited
lesson or an annoying advert. For the former, I didn't want to make
any expectations about fields of knowledge, because I honest have no
idea. For the latter, I wrote that sentence to indicate that siphash
isn't just some newfangled hipster function, but something useful and
well established. I didn't mean it as a form of advertising. My
apologies if I've offended your sensibilities.
That cr.yp.to link is fine, or https://131002.net/siphash/siphash.pdf I believe.
> Key rotation is important anyway, without any key rotation even if the
> key is compromised in siphash by some external means we would have an
> insecure hash until the system reboots.
I'm a bit surprised to read this. I've never designed a system to be
secure even in the event of remote arbitrary kernel memory disclosure,
and I wasn't aware this was generally considered an architectural
requirement or Linux.
In any case, if you want this, I suppose you can have it with siphash too.
> Maybe so, but we need to do due diligence before considering adopting
> siphash as the primary hashing in the network stack. Consider that we
> may very well perform a hash over L4 tuples on _every_ packet. We've
> done a good job at limiting this to be at most one hash per packet,
> but nevertheless the performance of the hash function must be take
> into account.
I agree with you. It seems like each case is going to needed to be
measured on a case by case basis. In this series I make the first use
of siphash in the secure sequence generation and get_random_int/long,
where siphash replaces md5, so there's a pretty clear performance in.
But for the jhash replacements indeed things are going to need to be
individually evaluated.
> 1) My quick test shows siphash is about four times more expensive than
> jhash. On my test system, computing a hash over IPv4 tuple (two 32 bit
> addresses and 2 16 bit source ports) is 6.9 nsecs in Jenkins hash, 33
> nsecs with siphash. Given that we have eliminated most of the packet
> header hashes this might be tolerable, but still should be looking at
> ways to optimize.
> 2) I like moving to use u64 (quad words) in the hash, this is an
> improvement over Jenkins which is based on 32 bit words. If we put
> this in the kernel we probably want to have several variants of
> siphash for specific sizes (e.g. siphash1, siphash2, siphash2,
> siphashn for hash over one, two, three, or n sixty four bit words).
I think your suggestion for (2) will contribute to further
optimizations for (1). In v2, I had another patch in there adding
siphash_1word, siphash_2words, etc, like jhash, but I implemented it
by taking u32 variables and then just concatenating these into a
buffer and passing them to the main siphash function. I removed it
from v3 because I thought that these kind of missed the whole point.
In particular:
a) siphash24_1word, siphash24_2words, siphash24_3words, etc should
take u64, not u32, since that's what siphash operates on natively
b) Rather than concatenating them in a buffer, I should write
specializations of the siphash24 function _especially_ for these size
inputs to avoid the copy and to reduce the book keeping.
I'll add these functions to v4 implemented like that.
Thanks for the useful feedback and benchmarks!
Jason
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox