Re: [PATCH v7 1/6] lib/dlock-list: Distributed and lock-protected lists

[Boqun Feng]

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 iterated
> + *
> + * The iterator has to be properly initialized before calling this function.
> + */
> +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 = list_next_entry(curr, list);
> +
> +	if (!curr || (&curr->list == &iter->entry->list)) {
> +		/*
> +		 * The current list has been exhausted, try the next available
> +		 * list.
> +		 */
> +		curr = __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 iterated.
> + */
> +#define dlock_list_first_entry(iter, type, member)			\
> +	({								\
> +		struct dlock_list_node *_n;				\
> +		_n = __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 iterated.
> + *
> + * Note that pos can't be NULL.
> + */
> +#define dlock_list_next_entry(pos, iter, member)			\
> +	({								\
> +		struct dlock_list_node *_n;				\
> +		_n = __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 removal
> + * @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 = dlock_list_first_entry(iter, typeof(*(pos)), member);\
> +	    ({								\
> +		bool _b = (pos != NULL);				\
> +		if (_b)							\
> +			n = 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);
	
	}

	void dlock_list_release_prev(struct dlock_list_iter *iter)
	{
		spin_unlock(iter->prev_entry->lock);
		iter->prev_entry = NULL;
	}

	#define dlist_for_each_entry_safe(pos, n, iter, member)		\
		for (pos = dlock_list_first_entry(iter, typeof(*(pos)), member);	\
		    ({									\
			bool _b = (pos != NULL);					\
			if (_b) {							\
				if (dlist_is_last_perlist(&(pos)->member)) {		\
					iter->prev_entry = iter->entry;			\
					iter->entry = NULL;				\
					n = dlock_list_first_entry(NULL, iter, member);	\
				}							\
				else							\
					n = dlock_list_next_entry(pos, iter, member);	\
			}								\
			_b;								\
		    });									\
		    pos = 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 = n)
> +
> +#endif /* __LINUX_DLOCK_LIST_H */

[...]

> +/**
> + * __dlock_list_next_list: Find the first entry of the next available list
> + * @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 iterator.
> + */
> +struct dlock_list_node *__dlock_list_next_list(struct dlock_list_iter *iter)
> +{
> +	struct dlock_list_node *next;
> +	struct dlock_list_head *head;
> +
> +restart:
> +	if (iter->entry) {
> +		spin_unlock(&iter->entry->lock);
> +		iter->entry = NULL;
> +	}
> +
> +next_list:
> +	/*
> +	 * Try next list
> +	 */
> +	if (++iter->index >= nr_cpu_ids)
> +		return NULL;	/* All the entries iterated */
> +
> +	if (list_empty(&iter->head[iter->index].list))
> +		goto next_list;
> +
> +	head = iter->entry = &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 = list_entry(head->list.next, struct dlock_list_node,
> +			  list);
> +	WARN_ON_ONCE(next->head != head);
> +
> +	return next;
> +}
> -- 
> 1.8.3.1
>

Attachment: signature.asc
Description: PGP signature