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

From: Waiman Long
Date: Wed Jul 20 2016 - 15:54:18 EST

On 07/19/2016 03:23 PM, Tejun Heo wrote:

On Tue, Jul 19, 2016 at 02:42:31PM -0400, Waiman Long wrote:
On 07/18/2016 07:38 PM, Tejun Heo wrote:
+struct dlock_list_node {
+ struct list_head list;
+ spinlock_t *lockptr;
Wouldn't it be better to point to dlock_list_percpu?
I could. However, the only thing that matter is the spinlock that protects
the list entry.
Yeah, we can get back to this when it's actually necessary. It just
looked a bit weird to me.

+ * The dlock list iteration functions which return true if iteration has
+ * to be continued.
+ */
+extern bool dlock_list_next(struct dlock_list_head *dlist,
+ struct dlock_list_iter *iter);
+extern bool dlock_list_next_safe(struct dlock_list_head *dlist,
+ struct dlock_list_iter *iter);
Why not return dlock_list_node * for the current node? That'd more
conventional and allows dlock_list_iter to be opaque.
Yes, I can make it return dlock_list_node *.

However, to make dlock_list_iter opaque, I will have to dynamically allocate
the structure. That will add an extra memory allocation and free calls as
well as handling the error case of running out of memory. I don't think that
is worth doing at this point.
Sure, keep it defined in the header file. Just don't require users to
reach into it and add a comment saying that the struct is opaque to
its users.

Will do so.

+int alloc_dlock_list_head(struct dlock_list_head *dlist)
+ struct dlock_list_head dlist_tmp;
+ int cpu;
+ dlist_tmp.head = alloc_percpu(struct dlock_list_head_percpu);
+ if (!dlist_tmp.head)
+ return -ENOMEM;
+ for_each_possible_cpu(cpu) {
+ struct dlock_list_head_percpu *head;
+ head = per_cpu_ptr(dlist_tmp.head, cpu);
+ INIT_LIST_HEAD(&head->list);
+ head->lock = __SPIN_LOCK_UNLOCKED(&head->lock);
+ lockdep_set_class(&head->lock,&dlock_list_key);
+ }
+ dlist->head = dlist_tmp.head;
Just use dlist->head directly or use local __perpcu head pointer?
I just don't want to expose the structure to world until it is fully
initialized. If you think I am over-cautious, I can use dlist->head as
I don't think it makes any actual difference. No strong opinion
either way. Just use local __percpu head pointer then?

+ return 0;
Does this actually need to be exported? If so, it might be a better
idea to start with EXPORT_SYMBOL_GPL().
For the current use case, we probably don't need to export the symbols.
Other use cases may require that. I will change it to use the version
If it's not immediately necessary, it's best to not export at all.

I will remove the EXPORT statements.

+void dlock_list_del(struct dlock_list_node *node)
+ spinlock_t *lock = READ_ONCE(node->lockptr);
+ if (unlikely(!lock)) {
+ "dlock_list_del: node 0x%lx has no associated lock\n",
+ (unsigned long)node);
Maybe "if (WARN_ONCE(!lock...)"? WARN_ONCE implies unlikely.
OK, will do that.

+ return;
+ }
+ spin_lock(lock);
+ if (likely(lock == node->lockptr)) {
+ list_del_init(&node->list);
+ node->lockptr = NULL;
+ } else {
+ /*
+ * This path should never be executed.
+ */
+ }
This still kinda bothers me because this pretty much requires the
users to have strong synchronization around the operations and makes
it unusable in situations where opportunistic behaviors are
acceptable. It negates the usefulness quite a bit.
I understand your concern. I will make it retry again with the new lock.
It doesn't necessarily have to retry but shouldn't break down when
used in an opportunistic racy way - e.g. if adds and removes race, the
order of operations isn't clearly defined as such any outcome is fine
as long as the list maintains its integrity.

I am going to retry it if the lock changes to different one and ignore it if it becomes NULL.

+ * dlock_list_next_safe - Removal-safe iterator of dlock list
+ * @dlist: Pointer to the dlock_list_head structure
+ * @iter : Pointer to the dlock list iterator structure
+ * Return: true if the next entry is found, false if all the entries iterated
+ *
+ * The iterator has to be properly initialized before calling this function.
+ * This iteration function is safe with respect to list entry removal.
+ * However, it cannot correctly iterate newly added entries right after the
+ * current one.
+ */
This still looks wrong to me. If you want to provide the two variants
of iterations, can't you just implement one next function and build
the two types of iterations on top of it?
I have been thinking about making dlock_list_next_cpu() the real external
function and have 2 inline functions that implement dlock_list_next() and
dlock_list_next_safe(). That may strike a better balance between performance
and code abstraction. I will do so if you have no objection to that.
Yeah, please give it a try. As mentioned in another reply, it'd
probably be best to provide an iteration macro which encapsulates the
whole thing.


Yes, I am go to make the dlist_for_each_entry macro as suggested by Al.