Received-SPF: pass (google.com: domain of linux-nfs-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Chuck Lever III <chuck.lever@oracle.com>
To:     Neil Brown <neilb@suse.de>
CC:     Linux NFS Mailing List <linux-nfs@vger.kernel.org>
Subject: Re: [PATCH v2 7/9] NFSD: Use rhashtable for managing nfs4_file
 objects
Thread-Topic: [PATCH v2 7/9] NFSD: Use rhashtable for managing nfs4_file
 objects
Thread-Index: AQHY2Z+f4KLIvxFyZE+pJJ7lJKAPUq4IWjWAgADUNACAALMrAIABAksA
Date:   Wed, 12 Oct 2022 15:01:53 +0000
Message-ID: <4004BFE1-C887-4A53-9512-8A264E0361FF@oracle.com>
References: <166507275951.1802.13184584115155050247.stgit@manet.1015granger.net>
 <166507324882.1802.884870684212914640.stgit@manet.1015granger.net>
 <166544739751.14457.9018300177489236723@noble.neil.brown.name>
 <EB08B095-BF02-4B5E-8CD2-12B0201328D2@oracle.com>
 <166553144435.32740.14940127200777208215@noble.neil.brown.name>
In-Reply-To: <166553144435.32740.14940127200777208215@noble.neil.brown.name>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?85EGY5ilJZ6fjfbvqYHSyAYCgYud7EGaSUNtyNVYLu8mEPKZnyfnUJQrID55?=
 =?us-ascii?Q?mXBh/crXJnQckb9eo0Pthfg7k35CuiTI/fErnhY1YzYVfvGG3O7++1MHL/Ka?=
 =?us-ascii?Q?1oKQDi5HHAiAO/6h0dc1fvod8VMi8gdHjwhjmxxGUe/3BNJJC2gDOxK+/BrW?=
 =?us-ascii?Q?8ibQ1RulVHLLLC9my/nHcNloRmnklnUTCRyUwyNBbycw5fpjbsMe4TULcD1Y?=
 =?us-ascii?Q?Q37X5u+4IXC1Y9gSxNsoBKO4STxuh7/UYzgBdnXB2MFnd6FtJXKUkfRaKNLE?=
 =?us-ascii?Q?UHo8YnvcydLu/Ioe72w0UlCELAlWwvKhx2UaGnMgnmdP/RiA2J9ZFYxKnFD5?=
 =?us-ascii?Q?T9rmogG2smMnbO/Ulkz02yxgFsTiGyhxNF5oRzcdTFa4SOcYCkMtDA7ms9G9?=
 =?us-ascii?Q?wMEuf0bJVCZ3udFbqVeinDfYfL6gXnnakS5B8kDTmLABGmqZnkj1OqMNkEka?=
 =?us-ascii?Q?/3UPYnAP/zuZJ3yr3EeFy4naBnuRrqcCar3QV5bLDMgPLxLlen8dp3W9zOxg?=
 =?us-ascii?Q?uvKdMn6z+u+qzdloKBaZc+P90+//AZSNQS7bHea+fRYrZRnvcLXMgS2e5gfE?=
 =?us-ascii?Q?k9acGGQkKF/mzTI+CZ9hv7iQghM6teGRu7FSKi3xRSZuaCF1YUf5aSgR1Djp?=
 =?us-ascii?Q?5OHqrdwi2hPt7KLal79H1rdDrp8o+Gipyt4CROOeubdMxDxIkH20x9qk84e2?=
 =?us-ascii?Q?QWYKnhLrXiQ6vMkv2fVTNJY7cqjpoORK0imkUTbWGuvtJ9gg3YG1OQ9Zk4af?=
 =?us-ascii?Q?WlvX82iva7CNbMWQ6o5LlUemFdgtcUqSMkIqkn2QBDMl50xPvOPyfbydVTJy?=
 =?us-ascii?Q?8913eySWPEsv9TwCqv8KbZ3Shl9b6RYNOaL8Qmk0pL1xfr97Zzt6gLBzCYYu?=
 =?us-ascii?Q?CcZkBdltYFtpVu7ut/m/NUc6DUJbrJtOdveuo9znlybBFE1+Hhg4vD/oa67d?=
 =?us-ascii?Q?5PI8/1fB2vTsN9NA2+dmT75saqkmss9+ktAT+8AywoUSvKJwFaOORSD9W4YP?=
 =?us-ascii?Q?Q+qhitqXikCNdWZ/KWcnM6y+auo4bwWZAs5quEeP1CuOSYND7voBHaG8EVWv?=
 =?us-ascii?Q?pgFU6yrP4Z34OZnyMubOsNtPCPAt3mL/tBTfaZhh88gc6KykngFY7YVxF3yi?=
 =?us-ascii?Q?dzvFMHfX18VFYdvwJ8mdnkPpm0fuBjwcniS0nfgdfuVYrMBJ7dtJxtTnQp4S?=
 =?us-ascii?Q?hs9iPypjThp2zHZkdRoFTBXRqLKLrAS7G/x5R4vLqONHy4GRj2msPuMTTE6K?=
 =?us-ascii?Q?40pHWdSCMhwdMjxySNj7E3KZGRHUtZxhlmVsjqOXqF4oP26ghBWogX15NhoC?=
 =?us-ascii?Q?7TnSg6RCEcqWUntf9UKeOVAIygtQgoVtcibyvjehMgPafR7PSf4sFN1ctfE0?=
 =?us-ascii?Q?M7zIPxG0MSKxywo15CUPdVtxcCXXh4FTGXQhR/oU/XiVOFmkH0dL56zK/s+0?=
 =?us-ascii?Q?jJoKLuIn2DG6OX4ic4joVoFy8UgXE0PxWMVRckv7txZadTdkerjUGkFTdEWI?=
 =?us-ascii?Q?ptfq87ivIoQxV5+n7BEgBI1C00qHKSF3d8KsjPkY4L11Lwcpx9j4HpvSSJyU?=
 =?us-ascii?Q?ty0BQ2nclLs31XTZ01tMrdaj++IXmcDdThV02ZP0kPISaQCy861pakARZfHP?=
 =?us-ascii?Q?eQ=3D=3D?=
Content-Type: text/plain; charset="us-ascii"
Content-ID: <9BC23CE408D49B4E9513AC610FB77A17@namprd10.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BN0PR10MB5128.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: c64a270a-3e69-4a1e-1758-08daac62b31a
X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Oct 2022 15:01:53.7638
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: v7EEOYmJRgvyi+N93m0hZTsQUIgZ7GXSiJJV4qKkFLjjZbX2ubjvxkNVyFCNxVCXBuHQQwFjQ84zJ6XxFXsVmA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BLAPR10MB5041
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.205,Aquarius:18.0.895,Hydra:6.0.545,FMLib:17.11.122.1
 definitions=2022-10-12_07,2022-10-12_01,2022-06-22_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 phishscore=0
 malwarescore=0 mlxscore=0 spamscore=0 bulkscore=0 mlxlogscore=999
 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2209130000 definitions=main-2210120099
X-Proofpoint-GUID: cYekvWnVjMUiAw4AKy2AFkYBt3jYugUA
X-Proofpoint-ORIG-GUID: cYekvWnVjMUiAw4AKy2AFkYBt3jYugUA
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE autolearn=ham
        autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-nfs.vger.kernel.org>
X-Mailing-List: linux-nfs@vger.kernel.org


> On Oct 11, 2022, at 7:37 PM, NeilBrown <neilb@suse.de> wrote:
>=20
> On Tue, 11 Oct 2022, Chuck Lever III wrote:
>>> On Oct 10, 2022, at 8:16 PM, NeilBrown <neilb@suse.de> wrote:
>>>=20
>>> On Fri, 07 Oct 2022, Chuck Lever wrote:
>>>>=20
>>>> -static unsigned int file_hashval(struct svc_fh *fh)
>>>> +/*
>>>> + * The returned hash value is based solely on the address of an in-co=
de
>>>> + * inode, a pointer to a slab-allocated object. The entropy in such a
>>>> + * pointer is concentrated in its middle bits.
>>>=20
>>> I think you need more justification than that for throwing away some of
>>> the entropy, even if you don't think it is much.
>>=20
>> We might have that justification:
>>=20
>> https://lore.kernel.org/linux-nfs/YrUFbLJ5uVbWtZbf@ZenIV/
>>=20
>> Actually I believe we are not discarding /any/ entropy in
>> this function. The bits we discard are invariant.
>>=20
>=20
> Ok, I can accept that this:
>=20
> +	k =3D ptr >> L1_CACHE_SHIFT;

> I searched for ">> *L1_CACHE_SHIFT".  Apart from the nfsd
> filecache you mentioned I find two.  One in quota and one in reiserfs.
> Both work with traditional hash tables which are more forgiving of
> longer chains.
> Do you have other evidence of this being a common trope?


This approach is based on the hash function in fs/inode.c,
which uses integer division instead of a shift.

 509 static unsigned long hash(struct super_block *sb, unsigned long hashva=
l)
 510 {
 511         unsigned long tmp;
 512=20
 513         tmp =3D (hashval * (unsigned long)sb) ^ (GOLDEN_RATIO_PRIME + =
hashval) /
 514                         L1_CACHE_BYTES;
 515         tmp =3D tmp ^ ((tmp ^ GOLDEN_RATIO_PRIME) >> i_hash_shift);
 516         return tmp & i_hash_mask;
 517 }


> only discards invariant bits, but how can you justify this:
>=20
> +	k &=3D 0x00ffffff;
>=20
> ??

After shifting an address, the top byte generally contains
invariant bits as well.


> And given that you pass it all to jhash anyway, why not just pass all of
> it?

I don't think this is a big deal, but these functions are
basically the same as what was recently merged without
complaint. It's not a high priority to revisit those.

It might be worth a clean-up to share this hash function
between the two hash tables... at that point we might
consider removing the extra mask.


>> And, note that this is exactly the same situation we just merged
>> in the filecache overhaul, and is a common trope amongst other
>> hash tables that base their function on the inode's address.
>>=20
>>=20
>>> Presumably you think hashing 32 bits is faster than hashing 64 bits.
>>> Maybe it is, but is it worth it?
>>>=20
>>> rhashtable depends heavily on having a strong hash function.  In
>>> particular if any bucket ends up with more than 16 elements it will
>>> choose a new seed and rehash.  If you deliberately remove some bits tha=
t
>>> it might have been used to spread those 16 out, then you are asking for
>>> trouble.
>>>=20
>>> We know that two different file handles can refer to the same inode
>>> ("rarely"), and you deliberately place them in the same hash bucket.
>>> So if an attacker arranges to access 17 files with the same inode but
>>> different file handles, then the hashtable will be continuously
>>> rehashed.
>>>=20
>>> The preferred approach when you require things to share a hash chain is
>>> to use an rhl table.
>>=20
>> Again, this is the same situation for the filecache. Do you
>> believe it is worth reworking that? I'm guessing "yes".
>=20
> As a matter of principle: yes.
> rhashtable is designed to assume that hash collisions are bad and can be
> changed by choosing a different seed.
> rhl_tables was explicitly added for cases when people wanted multiple
> elements to hash to the same value.
>=20
> The chance of it causing a problem without an attack are admittedly
> tiny.  Attacks are only possible with subtree_check enabled, or if the
> underlying filesystem does something "clever" with file handles, so
> there wouldn't be many situations where an attack would even be
> possible.  But if it were possible, it would likely be easy.
> The cost of the attack would be a minor-to-modest performance impact.
>=20
> So it is hard to argue "this code is dangerous and must be changed", but
> we have different tools for a reason, and I believe that rhl-tables is
> the right tool for this job.

Agreed. I wasn't suggesting it's an emergency situation, but it's
something that should get fixed at some point if there's a problem
with it, even a minor one.

I think I stopped at the non-list variant of rhashtable because
using rhl was more complex, and the non-list variant seemed to
work fine. There's no architectural reason either file_hashtbl
or the filecache must use the non-list variant.

In any event, it's worth taking the trouble now to change the
nfs4_file implementation proposed here as you suggest.


--
Chuck Lever