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
| ||
|
Message-Id: <20171226112521.0e834803c78462e792284ed0@gmail.com> Date: Tue, 26 Dec 2017 11:25:21 +0100 From: Vitaly Wool <vitalywool@...il.com> To: linux-kernel@...r.kernel.org, Huang Ying <ying.huang@...el.com> Cc: Oleksiy.Avramchenko@...y.com Subject: [PATCH v2] llist: add llist_[add|del_first]_exclusive It sometimes is necessary to be able to be able to use llist in the following manner: > if (node_unlisted(node)) > llst_add(node, list); i. e. only add a node to the list if it's not already on a list. This is not possible without taking locks because otherwise there's an obvious race between the check and the addition. This patch adds the routine to add a node only if it is not on any list that is lockless and race free as long as there's only one consumer. That is, llist_add_exclusive would only add a node if it's not already on a list, and llist_del_first_exclusive will delete the first node off the list and mark it as not being on any list. Signed-off-by: Vitaly Vul <vitaly.vul@...y.com> --- include/linux/llist.h | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) diff --git a/include/linux/llist.h b/include/linux/llist.h index fd4ca0b..7aaab25 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -69,6 +69,15 @@ struct llist_node { #define LLIST_HEAD_INIT(name) { NULL } #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) +#define LLIST_NODE_UNLISTED ((void *)(-1L)) +#define LLIST_NODE_INIT(name) { LLIST_NODE_UNLISTED } +#define LLIST_NODE(name) struct llist_node name = LLIST_NODE_INIT(name) + +static inline void INIT_LLIST_NODE(struct llist_node *node) +{ + WRITE_ONCE(node->next, LLIST_NODE_UNLISTED); +} + /** * init_llist_head - initialize lock-less list head * @head: the head for your lock-less list @@ -197,4 +206,42 @@ extern struct llist_node *llist_del_first(struct llist_head *head); struct llist_node *llist_reverse_order(struct llist_node *head); +/** + * llist_del_first_exclusive - delete the first entry of lock-less list + * and make sure it's marked as UNLISTED + * @head: the head for your lock-less list + * + * If list is empty, return NULL, otherwise, return the first entry + * deleted, this is the newest added one. + * + */ +static inline struct llist_node *llist_del_first_exclusive( + struct llist_head *head) +{ + struct llist_node *node = llist_del_first(head); + + if (READ_ONCE(node)) + smp_store_release(&node->next, LLIST_NODE_UNLISTED); + return node; +} + + +/** + * llist_add_exclusive - add a node only if it's not on any list + (i. e. marked as UNLISTED) + * @node: the node to be added + * @head: the head for your lock-less list + * + * Return true if the node was added, or false otherwise. + */ +static inline bool llist_add_exclusive(struct llist_node *node, + struct llist_head *head) +{ + if (cmpxchg(&node->next, LLIST_NODE_UNLISTED, NULL) != + LLIST_NODE_UNLISTED) + return false; + + llist_add(node, head); + return true; +} #endif /* LLIST_H */ -- 2.7.4
Powered by blists - more mailing lists