{"id":807445,"url":"http://patchwork.ozlabs.org/api/1.0/patches/807445/?format=json","project":{"id":7,"url":"http://patchwork.ozlabs.org/api/1.0/projects/7/?format=json","name":"Linux network development","link_name":"netdev","list_id":"netdev.vger.kernel.org","list_email":"netdev@vger.kernel.org","web_url":null,"scm_url":null,"webscm_url":null},"msgid":"<1504074719-15147-2-git-send-email-chrism@mellanox.com>","date":"2017-08-30T06:31:57","name":"[net-next,v2,1/3] idr: Add new APIs to support unsigned long","commit_ref":null,"pull_url":null,"state":"accepted","archived":true,"hash":"c36c15c7c26ae726af426344cca76e5ff7411705","submitter":{"id":72170,"url":"http://patchwork.ozlabs.org/api/1.0/people/72170/?format=json","name":"Chris Mi","email":"chrism@mellanox.com"},"delegate":{"id":34,"url":"http://patchwork.ozlabs.org/api/1.0/users/34/?format=json","username":"davem","first_name":"David","last_name":"Miller","email":"davem@davemloft.net"},"mbox":"http://patchwork.ozlabs.org/project/netdev/patch/1504074719-15147-2-git-send-email-chrism@mellanox.com/mbox/","series":[{"id":534,"url":"http://patchwork.ozlabs.org/api/1.0/series/534/?format=json","date":"2017-08-30T06:31:56","name":"net/sched: Improve getting objects by indexes","version":2,"mbox":"http://patchwork.ozlabs.org/series/534/mbox/"}],"check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/807445/checks/","tags":{},"headers":{"Return-Path":"","X-Original-To":"patchwork-incoming@ozlabs.org","Delivered-To":"patchwork-incoming@ozlabs.org","Authentication-Results":"ozlabs.org;\n\tspf=none (mailfrom) smtp.mailfrom=vger.kernel.org\n\t(client-ip=209.132.180.67; helo=vger.kernel.org;\n\tenvelope-from=netdev-owner@vger.kernel.org;\n\treceiver=)","Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xhwfT5321z9sN7\n\tfor ;\n\tWed, 30 Aug 2017 16:32:33 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1750941AbdH3Gc0 (ORCPT );\n\tWed, 30 Aug 2017 02:32:26 -0400","from mail-il-dmz.mellanox.com ([193.47.165.129]:37966 \"EHLO\n\tmellanox.co.il\" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org\n\twith ESMTP id S1750746AbdH3GcZ (ORCPT\n\t); Wed, 30 Aug 2017 02:32:25 -0400","from Internal Mail-Server by MTLPINE1 (envelope-from\n\tchrism@mellanox.com)\n\twith ESMTPS (AES256-SHA encrypted); 30 Aug 2017 09:32:19 +0300","from dev-r630-04.mtbc.labs.mlnx (dev-r630-04.mtbc.labs.mlnx\n\t[10.12.205.14])\n\tby labmailer.mlnx (8.13.8/8.13.8) with ESMTP id v7U6WBVS010171;\n\tWed, 30 Aug 2017 09:32:18 +0300"],"From":"Chris Mi ","To":"netdev@vger.kernel.org","Cc":"jhs@mojatatu.com, xiyou.wangcong@gmail.com, jiri@resnulli.us,\n\tdavem@davemloft.net, mawilcox@microsoft.com","Subject":"[patch net-next v2 1/3] idr: Add new APIs to support unsigned long","Date":"Wed, 30 Aug 2017 02:31:57 -0400","Message-Id":"<1504074719-15147-2-git-send-email-chrism@mellanox.com>","X-Mailer":"git-send-email 1.8.3.1","In-Reply-To":"<1504074719-15147-1-git-send-email-chrism@mellanox.com>","References":"<1504074719-15147-1-git-send-email-chrism@mellanox.com>","Sender":"netdev-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"netdev@vger.kernel.org"},"content":"The following new APIs are added:\n\nint idr_alloc_ext(struct idr *idr, void *ptr, unsigned long *index,\n unsigned long start, unsigned long end, gfp_t gfp);\nvoid *idr_remove_ext(struct idr *idr, unsigned long id);\nvoid *idr_find_ext(const struct idr *idr, unsigned long id);\nvoid *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id);\nvoid *idr_get_next_ext(struct idr *idr, unsigned long *nextid);\n\nSigned-off-by: Chris Mi \nSigned-off-by: Jiri Pirko \n---\n include/linux/idr.h | 69 ++++++++++++++++++++++++++++++++++++++++++++--\n include/linux/radix-tree.h | 21 ++++++++++++--\n lib/idr.c | 66 +++++++++++++++++++++++++-------------------\n lib/radix-tree.c | 6 ++--\n 4 files changed, 125 insertions(+), 37 deletions(-)","diff":"diff --git a/include/linux/idr.h b/include/linux/idr.h\nindex bf70b3e..7c3a365 100644\n--- a/include/linux/idr.h\n+++ b/include/linux/idr.h\n@@ -80,19 +80,75 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val)\n */\n \n void idr_preload(gfp_t gfp_mask);\n-int idr_alloc(struct idr *, void *entry, int start, int end, gfp_t);\n+\n+int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index,\n+\t\t unsigned long start, unsigned long end, gfp_t gfp,\n+\t\t bool ext);\n+\n+/**\n+ * idr_alloc - allocate an id\n+ * @idr: idr handle\n+ * @ptr: pointer to be associated with the new id\n+ * @start: the minimum id (inclusive)\n+ * @end: the maximum id (exclusive)\n+ * @gfp: memory allocation flags\n+ *\n+ * Allocates an unused ID in the range [start, end). Returns -ENOSPC\n+ * if there are no unused IDs in that range.\n+ *\n+ * Note that @end is treated as max when <= 0. This is to always allow\n+ * using @start + N as @end as long as N is inside integer range.\n+ *\n+ * Simultaneous modifications to the @idr are not allowed and should be\n+ * prevented by the user, usually with a lock. idr_alloc() may be called\n+ * concurrently with read-only accesses to the @idr, such as idr_find() and\n+ * idr_for_each_entry().\n+ */\n+static inline int idr_alloc(struct idr *idr, void *ptr,\n+\t\t\t int start, int end, gfp_t gfp)\n+{\n+\tunsigned long id;\n+\tint ret;\n+\n+\tif (WARN_ON_ONCE(start < 0))\n+\t\treturn -EINVAL;\n+\n+\tret = idr_alloc_cmn(idr, ptr, &id, start, end, gfp, false);\n+\n+\tif (ret)\n+\t\treturn ret;\n+\n+\treturn id;\n+}\n+\n+static inline int idr_alloc_ext(struct idr *idr, void *ptr,\n+\t\t\t\tunsigned long *index,\n+\t\t\t\tunsigned long start,\n+\t\t\t\tunsigned long end,\n+\t\t\t\tgfp_t gfp)\n+{\n+\treturn idr_alloc_cmn(idr, ptr, index, start, end, gfp, true);\n+}\n+\n int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t);\n int idr_for_each(const struct idr *,\n \t\t int (*fn)(int id, void *p, void *data), void *data);\n void *idr_get_next(struct idr *, int *nextid);\n+void *idr_get_next_ext(struct idr *idr, unsigned long *nextid);\n void *idr_replace(struct idr *, void *, int id);\n+void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id);\n void idr_destroy(struct idr *);\n \n-static inline void *idr_remove(struct idr *idr, int id)\n+static inline void *idr_remove_ext(struct idr *idr, unsigned long id)\n {\n \treturn radix_tree_delete_item(&idr->idr_rt, id, NULL);\n }\n \n+static inline void *idr_remove(struct idr *idr, int id)\n+{\n+\treturn idr_remove_ext(idr, id);\n+}\n+\n static inline void idr_init(struct idr *idr)\n {\n \tINIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);\n@@ -128,11 +184,16 @@ static inline void idr_preload_end(void)\n * This function can be called under rcu_read_lock(), given that the leaf\n * pointers lifetimes are correctly managed.\n */\n-static inline void *idr_find(const struct idr *idr, int id)\n+static inline void *idr_find_ext(const struct idr *idr, unsigned long id)\n {\n \treturn radix_tree_lookup(&idr->idr_rt, id);\n }\n \n+static inline void *idr_find(const struct idr *idr, int id)\n+{\n+\treturn idr_find_ext(idr, id);\n+}\n+\n /**\n * idr_for_each_entry - iterate over an idr's elements of a given type\n * @idr: idr handle\n@@ -145,6 +206,8 @@ static inline void *idr_find(const struct idr *idr, int id)\n */\n #define idr_for_each_entry(idr, entry, id)\t\t\t\\\n \tfor (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id)\n+#define idr_for_each_entry_ext(idr, entry, id)\t\t\t\\\n+\tfor (id = 0; ((entry) = idr_get_next_ext(idr, &(id))) != NULL; ++id)\n \n /**\n * idr_for_each_entry_continue - continue iteration over an idr's elements of a given type\ndiff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h\nindex 3e57350..567ebb5 100644\n--- a/include/linux/radix-tree.h\n+++ b/include/linux/radix-tree.h\n@@ -357,8 +357,25 @@ int radix_tree_split(struct radix_tree_root *, unsigned long index,\n \t\t\tunsigned new_order);\n int radix_tree_join(struct radix_tree_root *, unsigned long index,\n \t\t\tunsigned new_order, void *);\n-void __rcu **idr_get_free(struct radix_tree_root *, struct radix_tree_iter *,\n-\t\t\tgfp_t, int end);\n+\n+void __rcu **idr_get_free_cmn(struct radix_tree_root *root,\n+\t\t\t struct radix_tree_iter *iter, gfp_t gfp,\n+\t\t\t unsigned long max);\n+static inline void __rcu **idr_get_free(struct radix_tree_root *root,\n+\t\t\t\t\tstruct radix_tree_iter *iter,\n+\t\t\t\t\tgfp_t gfp,\n+\t\t\t\t\tint end)\n+{\n+\treturn idr_get_free_cmn(root, iter, gfp, end > 0 ? end - 1 : INT_MAX);\n+}\n+\n+static inline void __rcu **idr_get_free_ext(struct radix_tree_root *root,\n+\t\t\t\t\t struct radix_tree_iter *iter,\n+\t\t\t\t\t gfp_t gfp,\n+\t\t\t\t\t unsigned long end)\n+{\n+\treturn idr_get_free_cmn(root, iter, gfp, end - 1);\n+}\n \n enum {\n \tRADIX_TREE_ITER_TAG_MASK = 0x0f,\t/* tag index in lower nybble */\ndiff --git a/lib/idr.c b/lib/idr.c\nindex b13682b..082778c 100644\n--- a/lib/idr.c\n+++ b/lib/idr.c\n@@ -7,45 +7,32 @@\n DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap);\n static DEFINE_SPINLOCK(simple_ida_lock);\n \n-/**\n- * idr_alloc - allocate an id\n- * @idr: idr handle\n- * @ptr: pointer to be associated with the new id\n- * @start: the minimum id (inclusive)\n- * @end: the maximum id (exclusive)\n- * @gfp: memory allocation flags\n- *\n- * Allocates an unused ID in the range [start, end). Returns -ENOSPC\n- * if there are no unused IDs in that range.\n- *\n- * Note that @end is treated as max when <= 0. This is to always allow\n- * using @start + N as @end as long as N is inside integer range.\n- *\n- * Simultaneous modifications to the @idr are not allowed and should be\n- * prevented by the user, usually with a lock. idr_alloc() may be called\n- * concurrently with read-only accesses to the @idr, such as idr_find() and\n- * idr_for_each_entry().\n- */\n-int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)\n+int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index,\n+\t\t unsigned long start, unsigned long end, gfp_t gfp,\n+\t\t bool ext)\n {\n-\tvoid __rcu **slot;\n \tstruct radix_tree_iter iter;\n+\tvoid __rcu **slot;\n \n-\tif (WARN_ON_ONCE(start < 0))\n-\t\treturn -EINVAL;\n \tif (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))\n \t\treturn -EINVAL;\n \n \tradix_tree_iter_init(&iter, start);\n-\tslot = idr_get_free(&idr->idr_rt, &iter, gfp, end);\n+\tif (ext)\n+\t\tslot = idr_get_free_ext(&idr->idr_rt, &iter, gfp, end);\n+\telse\n+\t\tslot = idr_get_free(&idr->idr_rt, &iter, gfp, end);\n \tif (IS_ERR(slot))\n \t\treturn PTR_ERR(slot);\n \n \tradix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);\n \tradix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);\n-\treturn iter.index;\n+\n+\tif (index)\n+\t\t*index = iter.index;\n+\treturn 0;\n }\n-EXPORT_SYMBOL_GPL(idr_alloc);\n+EXPORT_SYMBOL_GPL(idr_alloc_cmn);\n \n /**\n * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion\n@@ -134,6 +121,20 @@ void *idr_get_next(struct idr *idr, int *nextid)\n }\n EXPORT_SYMBOL(idr_get_next);\n \n+void *idr_get_next_ext(struct idr *idr, unsigned long *nextid)\n+{\n+\tstruct radix_tree_iter iter;\n+\tvoid __rcu **slot;\n+\n+\tslot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);\n+\tif (!slot)\n+\t\treturn NULL;\n+\n+\t*nextid = iter.index;\n+\treturn rcu_dereference_raw(*slot);\n+}\n+EXPORT_SYMBOL(idr_get_next_ext);\n+\n /**\n * idr_replace - replace pointer for given id\n * @idr: idr handle\n@@ -150,12 +151,19 @@ void *idr_get_next(struct idr *idr, int *nextid)\n */\n void *idr_replace(struct idr *idr, void *ptr, int id)\n {\n+\tif (WARN_ON_ONCE(id < 0))\n+\t\treturn ERR_PTR(-EINVAL);\n+\n+\treturn idr_replace_ext(idr, ptr, id);\n+}\n+EXPORT_SYMBOL(idr_replace);\n+\n+void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id)\n+{\n \tstruct radix_tree_node *node;\n \tvoid __rcu **slot = NULL;\n \tvoid *entry;\n \n-\tif (WARN_ON_ONCE(id < 0))\n-\t\treturn ERR_PTR(-EINVAL);\n \tif (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))\n \t\treturn ERR_PTR(-EINVAL);\n \n@@ -167,7 +175,7 @@ void *idr_replace(struct idr *idr, void *ptr, int id)\n \n \treturn entry;\n }\n-EXPORT_SYMBOL(idr_replace);\n+EXPORT_SYMBOL(idr_replace_ext);\n \n /**\n * DOC: IDA description\ndiff --git a/lib/radix-tree.c b/lib/radix-tree.c\nindex 898e879..c191b42 100644\n--- a/lib/radix-tree.c\n+++ b/lib/radix-tree.c\n@@ -2137,13 +2137,13 @@ int ida_pre_get(struct ida *ida, gfp_t gfp)\n }\n EXPORT_SYMBOL(ida_pre_get);\n \n-void __rcu **idr_get_free(struct radix_tree_root *root,\n-\t\t\tstruct radix_tree_iter *iter, gfp_t gfp, int end)\n+void __rcu **idr_get_free_cmn(struct radix_tree_root *root,\n+\t\t\t struct radix_tree_iter *iter, gfp_t gfp,\n+\t\t\t unsigned long max)\n {\n \tstruct radix_tree_node *node = NULL, *child;\n \tvoid __rcu **slot = (void __rcu **)&root->rnode;\n \tunsigned long maxindex, start = iter->next_index;\n-\tunsigned long max = end > 0 ? end - 1 : INT_MAX;\n \tunsigned int shift, offset = 0;\n \n grow:\n","prefixes":["net-next","v2","1/3"]}