From mboxrd@z Thu Jan 1 00:00:00 1970 From: NeilBrown Subject: Re: [PATCH v3] rhashtable: detect when object movement between tables might have invalidated a lookup Date: Mon, 03 Dec 2018 09:20:23 +1100 Message-ID: <878t17o9js.fsf@notabene.neil.brown.name> References: <87muqbtev6.fsf@notabene.neil.brown.name> <20181116055551.zxfydbpoicslsfkg@gondor.apana.org.au> <878t1tece0.fsf@notabene.neil.brown.name> <87pnuno479.fsf@notabene.neil.brown.name> <20181201084727.6mfh46yshxdoba4h@gondor.apana.org.au> Mime-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" Cc: David Miller , tgraf@suug.ch, netdev@vger.kernel.org, linux-kernel@vger.kernel.org, eric.dumazet@gmail.com To: Herbert Xu Return-path: In-Reply-To: <20181201084727.6mfh46yshxdoba4h@gondor.apana.org.au> Sender: linux-kernel-owner@vger.kernel.org List-Id: netdev.vger.kernel.org --=-=-= Content-Type: text/plain Content-Transfer-Encoding: quoted-printable On Sat, Dec 01 2018, Herbert Xu wrote: > On Fri, Nov 30, 2018 at 10:26:50AM +1100, NeilBrown wrote: >> >> diff --git a/lib/rhashtable.c b/lib/rhashtable.c >> index 30526afa8343..852ffa5160f1 100644 >> --- a/lib/rhashtable.c >> +++ b/lib/rhashtable.c >> @@ -1179,8 +1179,7 @@ struct rhash_head __rcu **rht_bucket_nested(const = struct bucket_table *tbl, >> unsigned int hash) >> { >> const unsigned int shift =3D PAGE_SHIFT - ilog2(sizeof(void *)); >> - static struct rhash_head __rcu *rhnull =3D >> - (struct rhash_head __rcu *)NULLS_MARKER(0); >> + static struct rhash_head __rcu *rhnull; >> unsigned int index =3D hash & ((1 << tbl->nest) - 1); >> unsigned int size =3D tbl->size >> tbl->nest; >> unsigned int subhash =3D hash; >> @@ -1198,8 +1197,11 @@ struct rhash_head __rcu **rht_bucket_nested(const= struct bucket_table *tbl, >> subhash >>=3D shift; >> } >>=20=20 >> - if (!ntbl) >> + if (!ntbl) { >> + if (!rhnull) >> + INIT_RHT_NULLS_HEAD(rhnull); >> return &rhnull; >> + } > > I think you missed my earlier reply beause of bouncing emails. Yeah, sorry about that. I should have looked through an lkml archive once I realized that was happening - I have now. > > I think this is unnecessary because > > RHT_NULLS_MARKER(RHT_NULLS_MARKER(0)) =3D RHT_NULLS_MARKER(0) > I don't understand how this is relevant. I think you are saying that when rht_bucket_nested() finds that the target page hasn't been allocated, it should return a pointer to a static variable which contains RHT_NULLS_MARKER(0) static struct rhash_head *rhnull =3D RHT_NULLS_MARKER(0); Then in __rhashtable_lookup(), head =3D rht_bucket(tbl, hash); would result in 'head' having the value '&rhnull'. Then rht_for_each_rcu_continue(he, *head, tbl, hash) { would result in 'he' having the value RHT_NULLS_MARKER(0) Then } while (he !=3D RHT_NULLS_MARKER(head)); will compare RHT_NULLS_MARKER(0) with RHT_NULLS_MARKED(&rhnull) and they will be different, so it will loop indefinitely. With respect to the shifting, you wrote: > The top-bit is most likely to be fixed and offer no real value. While this might be likely, it is not certain, so not relevant. On a 32bit machine with more than 2GB of physical memory, some memory addresses will have 0 in the msb, some will have 1. It is possible (however unlikely) that two hash buckets in different tables will have the same address except for the msb. If we ignore the msb, we might incorrectly determine that we have reached the end of the chain from the first bucket, whereas we actually reached the end of the chain from the second bucket. Thanks, NeilBrown --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEG8Yp69OQ2HB7X0l6Oeye3VZigbkFAlwEWqsACgkQOeye3VZi gbm+hw//TTRkiV4JY0ksig2gHFTyDTIjqyZajks5Tg3ZHyt2Ry3TWrAoYMoDd2+/ iyHbknxYy3zXBLC/QEhNsUvh/fZtCBSPGh/9qpnTNJm6d8+E+btnBIh1poWRyxoH VCQu4+RyNwgLjtIAfw3v++ku1uj00OQ1R+whs1DXu9R+VVI3DRAJmRrHldgp5nDl QNrtUP4wYZOTj7RCPIIcaTjaYJYK1eqzquEIB0rYzhDqT3mEkFGHHJoRy6ifkRTL xMy6Z8PdsKAL0oWAOQ7xMXIdNPR9vuqmoSv0cLRExyYxqn9RhkYzVjWij2EdH0mB acH3VTMFkpAIee2Ppp82gwMdwqIrQUhaJvKshab7nxQlW+Nd2RmylJMZfdnGV7bM oF9WJuqEnWoAFAo1IlTz4DaamUYQHWYqvgQ4xq9gl204SHdwOfYrYNJGyV3+dgIX /+bidcSjJM5ugYHQJQzgd3WSjjDS+jQsZ5IXwD3+qoxEw+xs11Z+cOr1OK482LVp 6gGkQLTD1feQnqZQo1OpWp9mcTZWff7CANMBdSjDIegtvXfsSYr92o8L4myjSmFA 48eU3/tTq4Xb3LkhW4Zh7VRYl6zXPwUVJ/3iQDuqNAC6g4bGTjqiBjJU4jPW1L3B SOuQWEzSMckoi8BQSJAp+lABnhRdY9RrejSuWgfMHPrrJkZrP7s= =y12K -----END PGP SIGNATURE----- --=-=-=--