From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm0-f67.google.com ([74.125.82.67]:50682 "EHLO mail-wm0-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S934240AbdJRIyw (ORCPT ); Wed, 18 Oct 2017 04:54:52 -0400 Date: Wed, 18 Oct 2017 16:55:59 +0800 From: Boqun Feng To: Waiman Long Cc: Alexander Viro , Jan Kara , Jeff Layton , "J. Bruce Fields" , Tejun Heo , Christoph Lameter , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, Ingo Molnar , Peter Zijlstra , Andi Kleen , Dave Chinner , Davidlohr Bueso Subject: Re: [PATCH v7 1/6] lib/dlock-list: Distributed and lock-protected lists Message-ID: <20171018085559.wwtqvofjguhveozg@tardis> References: <1507229008-20569-1-git-send-email-longman@redhat.com> <1507229008-20569-2-git-send-email-longman@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="6gd5lxgi67ix5uiy" Content-Disposition: inline In-Reply-To: <1507229008-20569-2-git-send-email-longman@redhat.com> Sender: linux-fsdevel-owner@vger.kernel.org List-ID: --6gd5lxgi67ix5uiy Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, Oct 05, 2017 at 06:43:23PM +0000, Waiman Long wrote: [...] > +/* > + * Find the first entry of the next available list. > + */ > +extern struct dlock_list_node * > +__dlock_list_next_list(struct dlock_list_iter *iter); > + > +/** > + * __dlock_list_next_entry - Iterate to the next entry of the dlock list > + * @curr : Pointer to the current dlock_list_node structure > + * @iter : Pointer to the dlock list iterator structure > + * Return: Pointer to the next entry or NULL if all the entries are iter= ated > + * > + * The iterator has to be properly initialized before calling this funct= ion. > + */ > +static inline struct dlock_list_node * > +__dlock_list_next_entry(struct dlock_list_node *curr, > + struct dlock_list_iter *iter) > +{ > + /* > + * Find next entry > + */ > + if (curr) > + curr =3D list_next_entry(curr, list); > + > + if (!curr || (&curr->list =3D=3D &iter->entry->list)) { > + /* > + * The current list has been exhausted, try the next available > + * list. > + */ > + curr =3D __dlock_list_next_list(iter); > + } > + > + return curr; /* Continue the iteration */ > +} > + > +/** > + * dlock_list_first_entry - get the first element from a list > + * @iter : The dlock list iterator. > + * @type : The type of the struct this is embedded in. > + * @member: The name of the dlock_list_node within the struct. > + * Return : Pointer to the next entry or NULL if all the entries are ite= rated. > + */ > +#define dlock_list_first_entry(iter, type, member) \ > + ({ \ > + struct dlock_list_node *_n; \ > + _n =3D __dlock_list_next_entry(NULL, iter); \ > + _n ? list_entry(_n, type, member) : NULL; \ > + }) > + > +/** > + * dlock_list_next_entry - iterate to the next entry of the list > + * @pos : The type * to cursor > + * @iter : The dlock list iterator. > + * @member: The name of the dlock_list_node within the struct. > + * Return : Pointer to the next entry or NULL if all the entries are ite= rated. > + * > + * Note that pos can't be NULL. > + */ > +#define dlock_list_next_entry(pos, iter, member) \ > + ({ \ > + struct dlock_list_node *_n; \ > + _n =3D __dlock_list_next_entry(&(pos)->member, iter); \ > + _n ? list_entry(_n, typeof(*(pos)), member) : NULL; \ > + }) > + [...] > +/** > + * dlist_for_each_entry_safe - iterate over the dlock list & safe over r= emoval > + * @pos : Type * to use as a loop cursor > + * @n : Another type * to use as temporary storage > + * @iter : The dlock list iterator > + * @member: The name of the dlock_list_node within the struct > + * > + * This iteration macro is safe with respect to list entry removal. > + * However, it cannot correctly iterate newly added entries right after = the > + * current one. > + */ > +#define dlist_for_each_entry_safe(pos, n, iter, member) \ So I missed something interesting here ;-) > + for (pos =3D dlock_list_first_entry(iter, typeof(*(pos)), member);\ > + ({ \ > + bool _b =3D (pos !=3D NULL); \ > + if (_b) \ > + n =3D dlock_list_next_entry(pos, iter, member); \ If @pos is the last item of the list of the index/cpu, and dlock_list_next_entry() will eventually call __dlock_list_next_list(), which will drop the lock for the current list and grab the lock for the next list, leaving @pos unprotected. But in the meanwhile, there could be another thread deleting @pos via dlock_lists_del() and freeing it. This is a use-after-free. I think we can have something like: (by adding a ->prev_entry in dlock_list_iter and severl helper functions.) bool dlist_is_last_perlist(struct dlock_list_node *n) { return list_is_last(&n->list, &n->head->list); =09 } void dlock_list_release_prev(struct dlock_list_iter *iter) { spin_unlock(iter->prev_entry->lock); iter->prev_entry =3D NULL; } #define dlist_for_each_entry_safe(pos, n, iter, member) \ for (pos =3D dlock_list_first_entry(iter, typeof(*(pos)), member); \ ({ \ bool _b =3D (pos !=3D NULL); \ if (_b) { \ if (dlist_is_last_perlist(&(pos)->member)) { \ iter->prev_entry =3D iter->entry; \ iter->entry =3D NULL; \ n =3D dlock_list_first_entry(NULL, iter, member); \ } \ else \ n =3D dlock_list_next_entry(pos, iter, member); \ } \ _b; \ }); \ pos =3D n, iter->prev_entry && dlock_list_release_prev(iter)) Of course, the dlock_list_first_entry() here may need a better name ;-) Thoughts? Regards, Boqun > + _b; \ > + }); \ > + pos =3D n) > + > +#endif /* __LINUX_DLOCK_LIST_H */ [...] > +/** > + * __dlock_list_next_list: Find the first entry of the next available li= st > + * @dlist: Pointer to the dlock_list_heads structure > + * @iter : Pointer to the dlock list iterator structure > + * Return: true if the entry is found, false if all the lists exhausted > + * > + * The information about the next available list will be put into the it= erator. > + */ > +struct dlock_list_node *__dlock_list_next_list(struct dlock_list_iter *i= ter) > +{ > + struct dlock_list_node *next; > + struct dlock_list_head *head; > + > +restart: > + if (iter->entry) { > + spin_unlock(&iter->entry->lock); > + iter->entry =3D NULL; > + } > + > +next_list: > + /* > + * Try next list > + */ > + if (++iter->index >=3D nr_cpu_ids) > + return NULL; /* All the entries iterated */ > + > + if (list_empty(&iter->head[iter->index].list)) > + goto next_list; > + > + head =3D iter->entry =3D &iter->head[iter->index]; > + spin_lock(&head->lock); > + /* > + * There is a slight chance that the list may become empty just > + * before the lock is acquired. So an additional check is > + * needed to make sure that a valid node will be returned. > + */ > + if (list_empty(&head->list)) > + goto restart; > + > + next =3D list_entry(head->list.next, struct dlock_list_node, > + list); > + WARN_ON_ONCE(next->head !=3D head); > + > + return next; > +} > --=20 > 1.8.3.1 >=20 --6gd5lxgi67ix5uiy Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAABCAAdFiEEj5IosQTPz8XU1wRHSXnow7UH+rgFAlnnFxwACgkQSXnow7UH +rhHOgf+Li1cKevUiFkrdmnywbtMK0CVOs9ZnzXFXtMgp0maQQLmJ27y1s3aOm6k Q8ItKMt+sy4uxaxKxCmCurVaPZ8ZfkkGAWrJ+6mYaMABD3DhmXGvzkL4DKNOKrC2 B27wk7NeTrA5O2G5UyqKgqP4e4YjKYR0LBPxpIQDtAiGbRpWqIjujO3M8TiyrEWi qsPo+C4jDo/4CpzAa+ZBlGSeu5DcFaavqFeudABBpM+dOnlwOsjQlP50wcNTkiZd Nx9YUby61IahRkTfMMY/vCZ9cdBA1kx2/95xK3NkAy3jrpZ/RVZU0laY0+oMQHoP 2ljNEB1K17lwTnvvJz1wmo8DxGzuUQ== =3zUE -----END PGP SIGNATURE----- --6gd5lxgi67ix5uiy--