linux-kernel - [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <1532998716-5037-1-git-send-email-byungchul.park@lge.com>
Date:   Tue, 31 Jul 2018 09:58:36 +0900
From:   Byungchul Park <byungchul.park@....com>
To:     linux-kernel@...r.kernel.org
Cc:     kernel-team@....com, ying.huang@...el.com, peterz@...radead.org,
        mingo@...nel.org, jiangshanlai@...il.com,
        paulmck@...ux.vnet.ibm.com, josh@...htriplett.org,
        rostedt@...dmis.org, mathieu.desnoyers@...icios.com,
        joel@...lfernandes.org, len.brown@...el.com, glider@...gle.com,
        peter@...leysoftware.com, aik@...abs.ru
Subject: [QUESTION] llist: Comment releasing 'must delete' restriction before traversing

Hello folks,

I'm careful in saying.. and curious about..

In restrictive cases like only addtions happen but never deletion, can't
we safely traverse a llist? I believe llist can be more useful if we can
release the restriction. Can't we?

If yes, we may add another function traversing starting from a head. Or
just use existing funtion with head->first.

Thank a lot for your answers in advance :)

----->8-----
>From 1e73882799b269cd86e7a7c955021e3a18d1e6cf Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park@....com>
Date: Tue, 31 Jul 2018 09:31:57 +0900
Subject: [QUESTION] llist: Comment releasing 'must delete' restriction before
 traversing

llist traversing can run without deletion in restrictive cases all
items are added but never deleted like a rculist traversing such as
list_for_each_entry_lockless. So add the comment.

Signed-off-by: Byungchul Park <byungchul.park@....com>
---
 include/linux/llist.h | 24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index 85abc29..d012d3e 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -32,8 +32,12 @@
  * operation, with "-" being no lock needed, while "L" being lock is needed.
  *
  * The list entries deleted via llist_del_all can be traversed with
- * traversing function such as llist_for_each etc.  But the list
- * entries can not be traversed safely before deleted from the list.
+ * traversing function such as llist_for_each etc.  Normally the list
+ * entries cannot be traversed safely before deleted from the list
+ * except the cases items are added to the list but never deleted.  In
+ * that restrictive cases the list may be safely traversed concurrently
+ * with llist_add.
+ *
  * The order of deleted entries is from the newest to the oldest added
  * one.  If you want to traverse from the oldest to the newest, you
  * must reverse the order by yourself before traversing.
@@ -116,7 +120,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being deleted from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
@@ -135,7 +141,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being deleted from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
@@ -153,7 +161,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being removed from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
@@ -175,7 +185,9 @@ static inline void init_llist_head(struct llist_head *list)
  *
  * In general, some entries of the lock-less list can be traversed
  * safely only after being removed from list, so start with an entry
- * instead of list head.
+ * instead of list head.  But in restrictive cases items are added to
+ * the list but never deleted, the list may be safely traversed
+ * concurrently with llist_add.
  *
  * If being used on entries deleted from lock-less list directly, the
  * traverse order is from the newest to the oldest added entry.  If
-- 
1.9.1