[PATCHSET] idr: deprecate idr_remove_all()

[PATCHSET] idr: deprecate idr_remove_all()

[Tejun Heo]

Hello,

(Andrew, I think this one is best routed through -mm.  Please read on)

idr is one of the areas with much higher concentration of bad
interface and implementation decisions.  This patchset removes one of
those oddities - idr_remove_all().  idr needs two steps for
destruction - idr_remove_all() followed by idr_destroy().
idr_remove_all() releases all IDs in use but doesn't release buffered
idr_layers.  idr_destroy() frees buffered idr_layers() but doesn't
bother with in-use idr_layers.

For added fun, calling idr_remove() on all allocated IDs doesn't
necessarily free all in-use idr_layers, so idr_for_each_entry()
idr_remove(); followed by idr_destroy() may still leak memory.

This confuses people.  Some correctly use both.  Many forget to call
idr_remove_all() and others forget idr_destroy() and they all leak
memory.  Even ida - something tightly coupled w/ idr - forgets to do
idr_remove_all() (although it's my fault).

This is just a bad interface.  While remove_all in itself might not be
that bad, there is only one legitimate user of idr_remove_all() which
can be converted to idr_remove() relatively easily, so I think it'd be
better to deprecate and later unexport it than keeping it around.

This patchset contains the following 14 patches.

 0001-idr-make-idr_destroy-imply-idr_remove_all.patch
 0002-atm-nicstar-don-t-use-idr_remove_all.patch
 0003-block-loop-don-t-use-idr_remove_all.patch
 0004-firewire-don-t-use-idr_remove_all.patch
 0005-drm-don-t-use-idr_remove_all.patch
 0006-dm-don-t-use-idr_remove_all.patch
 0007-remoteproc-don-t-use-idr_remove_all.patch
 0008-rpmsg-don-t-use-idr_remove_all.patch
 0009-dlm-use-idr_for_each_entry-in-recover_idr_clear-erro.patch
 0010-dlm-don-t-use-idr_remove_all.patch
 0011-nfs-idr_destroy-no-longer-needs-idr_remove_all.patch
 0012-inotify-don-t-use-idr_remove_all.patch
 0013-cgroup-don-t-use-idr_remove_all.patch
 0014-idr-deprecate-idr_remove_all.patch

0001 makes idr_destroy() imply idr_remove_all().  0002-0013 remove
uses of idr_remove_all().  0014 marks idr_remove_all() deprecated.
The patches are on top of the current linus#master 66e2d3e8c2 and also
applies on top of the current -mm.  It's available in the following
git branch.

 git://git.kernel.org/pub/scm/linux/kernel/git/tj/misc.git deprecate-idr_remove_all

As changes to most are trivial and have dependency on the first patch,
I think it would be best to route these together.  The only
non-trivial change is 0009 and 0010 which converts idr_for_each() to
idr_for_each_entry() and then replaces idr_remove_all() with
idr_remove() inside the for_each_entry loop.  Defintely wanna get acks
from dlm people.

Andrew, once people agree with the series, can you please route these
through -mm?

diffstat follows.  Thanks.

 drivers/atm/nicstar.c                   |    1 -
 drivers/block/loop.c                    |    1 -
 drivers/firewire/core-cdev.c            |    1 -
 drivers/gpu/drm/drm_context.c           |    2 +-
 drivers/gpu/drm/drm_crtc.c              |    1 -
 drivers/gpu/drm/drm_drv.c               |    1 -
 drivers/gpu/drm/drm_gem.c               |    2 --
 drivers/gpu/drm/exynos/exynos_drm_ipp.c |    4 ----
 drivers/gpu/drm/sis/sis_drv.c           |    1 -
 drivers/gpu/drm/via/via_map.c           |    1 -
 drivers/md/dm.c                         |    1 -
 drivers/remoteproc/remoteproc_core.c    |    1 -
 drivers/rpmsg/virtio_rpmsg_bus.c        |    1 -
 fs/dlm/lockspace.c                      |    1 -
 fs/dlm/recover.c                        |   25 +++++++++++--------------
 fs/nfs/client.c                         |    1 -
 fs/notify/inotify/inotify_fsnotify.c    |    1 -
 include/linux/idr.h                     |   14 +++++++++++++-
 kernel/cgroup.c                         |    4 +---
 lib/idr.c                               |   28 +++++++++++++---------------
 20 files changed, 39 insertions(+), 53 deletions(-)

--
tejun

[PATCH 01/14] idr: make idr_destroy() imply idr_remove_all()

[Tejun Heo]

idr is silly in quite a few ways, one of which is how it's supposed to
be destroyed - idr_destroy() doesn't release IDs and doesn't even
whine if the idr isn't empty.  If the caller forgets idr_remove_all(),
it simply leaks memory.

Even ida gets this wrong and leaks memory on destruction.  There is
absoltely no reason not to call idr_remove_all() from idr_destroy().
Nobody is abusing idr_destroy() for shrinking free layer buffer and
continues to use idr after idr_destroy(), so it's safe to do
remove_all from destroy.

In the whole kernel, there is only one place where idr_remove_all() is
legitimiately used without following idr_destroy() while there are
quite a few places where the caller forgets either idr_remove_all() or
idr_destroy() leaking memory.

This patch makes idr_destroy() call idr_destroy_all() and updates the
function description accordingly.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 6482390..1e47832 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -436,15 +436,6 @@ EXPORT_SYMBOL(idr_remove);
 /**
  * idr_remove_all - remove all ids from the given idr tree
  * @idp: idr handle
- *
- * idr_destroy() only frees up unused, cached idp_layers, but this
- * function will remove all id mappings and leave all idp_layers
- * unused.
- *
- * A typical clean-up sequence for objects stored in an idr tree will
- * use idr_for_each() to free all objects, if necessay, then
- * idr_remove_all() to remove all ids, and idr_destroy() to free
- * up the cached idr_layers.
  */
 void idr_remove_all(struct idr *idp)
 {
@@ -484,9 +475,20 @@ EXPORT_SYMBOL(idr_remove_all);
 /**
  * idr_destroy - release all cached layers within an idr tree
  * @idp: idr handle
+ *
+ * Free all id mappings and all idp_layers.  After this function, @idp is
+ * completely unused and can be freed / recycled.  The caller is
+ * responsible for ensuring that no one else accesses @idp during or after
+ * idr_destroy().
+ *
+ * A typical clean-up sequence for objects stored in an idr tree will use
+ * idr_for_each() to free all objects, if necessay, then idr_destroy() to
+ * free up the id mappings and cached idr_layers.
  */
 void idr_destroy(struct idr *idp)
 {
+	idr_remove_all(idp);
+
 	while (idp->id_free_cnt) {
 		struct idr_layer *p = get_from_free_list(idp);
 		kmem_cache_free(idr_layer_cache, p);
-- 
1.8.1

[PATCH 02/14] atm/nicstar: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Chas Williams <chas@cmf.nrl.navy.mil>
Cc: netdev@vger.kernel.org
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/atm/nicstar.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/atm/nicstar.c b/drivers/atm/nicstar.c
index ed1d2b7..628787e 100644
--- a/drivers/atm/nicstar.c
+++ b/drivers/atm/nicstar.c
@@ -251,7 +251,6 @@ static void nicstar_remove_one(struct pci_dev *pcidev)
 		if (card->scd2vc[j] != NULL)
 			free_scq(card, card->scd2vc[j]->scq, card->scd2vc[j]->tx_vcc);
 	}
-	idr_remove_all(&card->idr);
 	idr_destroy(&card->idr);
 	pci_free_consistent(card->pcidev, NS_RSQSIZE + NS_RSQ_ALIGNMENT,
 			    card->rsq.org, card->rsq.dma);
-- 
1.8.1

[PATCH 03/14] block/loop: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Jens Axboe <axboe@kernel.dk>
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/block/loop.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/block/loop.c b/drivers/block/loop.c
index ae12512..3b9c32b 100644
--- a/drivers/block/loop.c
+++ b/drivers/block/loop.c
@@ -1911,7 +1911,6 @@ static void __exit loop_exit(void)
 	range = max_loop ? max_loop << part_shift : 1UL << MINORBITS;
 
 	idr_for_each(&loop_index_idr, &loop_exit_cb, NULL);
-	idr_remove_all(&loop_index_idr);
 	idr_destroy(&loop_index_idr);
 
 	blk_unregister_region(MKDEV(LOOP_MAJOR, 0), range);
-- 
1.8.1

[PATCH 04/14] firewire: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Stefan Richter <stefanr@s5r6.in-berlin.de>
Cc: linux1394-devel@lists.sourceforge.net
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/firewire/core-cdev.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/firewire/core-cdev.c b/drivers/firewire/core-cdev.c
index f8d2287..68c3138 100644
--- a/drivers/firewire/core-cdev.c
+++ b/drivers/firewire/core-cdev.c
@@ -1779,7 +1779,6 @@ static int fw_device_op_release(struct inode *inode, struct file *file)
 	wait_event(client->tx_flush_wait, !has_outbound_transactions(client));
 
 	idr_for_each(&client->resource_idr, shutdown_resource, client);
-	idr_remove_all(&client->resource_idr);
 	idr_destroy(&client->resource_idr);
 
 	list_for_each_entry_safe(event, next_event, &client->event_list, link)
-- 
1.8.1

[PATCH 05/14] drm: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

* drm_ctxbitmap_cleanup() was calling idr_remove_all() but forgetting
  idr_destroy() thus leaking all buffered free idr_layers.  Replace it
  with idr_destroy().

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: David Airlie <airlied@linux.ie>
Cc: dri-devel@lists.freedesktop.org
Cc: Inki Dae <inki.dae@samsung.com>
Cc: Joonyoung Shim <jy0922.shim@samsung.com>
Cc: Seung-Woo Kim <sw0312.kim@samsung.com>
Cc: Kyungmin Park <kyungmin.park@samsung.com>
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/gpu/drm/drm_context.c           | 2 +-
 drivers/gpu/drm/drm_crtc.c              | 1 -
 drivers/gpu/drm/drm_drv.c               | 1 -
 drivers/gpu/drm/drm_gem.c               | 2 --
 drivers/gpu/drm/exynos/exynos_drm_ipp.c | 4 ----
 drivers/gpu/drm/sis/sis_drv.c           | 1 -
 drivers/gpu/drm/via/via_map.c           | 1 -
 7 files changed, 1 insertion(+), 11 deletions(-)

diff --git a/drivers/gpu/drm/drm_context.c b/drivers/gpu/drm/drm_context.c
index 45adf97..75f62c5 100644
--- a/drivers/gpu/drm/drm_context.c
+++ b/drivers/gpu/drm/drm_context.c
@@ -118,7 +118,7 @@ int drm_ctxbitmap_init(struct drm_device * dev)
 void drm_ctxbitmap_cleanup(struct drm_device * dev)
 {
 	mutex_lock(&dev->struct_mutex);
-	idr_remove_all(&dev->ctx_idr);
+	idr_destroy(&dev->ctx_idr);
 	mutex_unlock(&dev->struct_mutex);
 }
 
diff --git a/drivers/gpu/drm/drm_crtc.c b/drivers/gpu/drm/drm_crtc.c
index f2d667b..9b39d1f 100644
--- a/drivers/gpu/drm/drm_crtc.c
+++ b/drivers/gpu/drm/drm_crtc.c
@@ -1102,7 +1102,6 @@ void drm_mode_config_cleanup(struct drm_device *dev)
 		crtc->funcs->destroy(crtc);
 	}
 
-	idr_remove_all(&dev->mode_config.crtc_idr);
 	idr_destroy(&dev->mode_config.crtc_idr);
 }
 EXPORT_SYMBOL(drm_mode_config_cleanup);
diff --git a/drivers/gpu/drm/drm_drv.c b/drivers/gpu/drm/drm_drv.c
index be174ca..25f91cd 100644
--- a/drivers/gpu/drm/drm_drv.c
+++ b/drivers/gpu/drm/drm_drv.c
@@ -297,7 +297,6 @@ static void __exit drm_core_exit(void)
 
 	unregister_chrdev(DRM_MAJOR, "drm");
 
-	idr_remove_all(&drm_minors_idr);
 	idr_destroy(&drm_minors_idr);
 }
 
diff --git a/drivers/gpu/drm/drm_gem.c b/drivers/gpu/drm/drm_gem.c
index 24efae4..e775859 100644
--- a/drivers/gpu/drm/drm_gem.c
+++ b/drivers/gpu/drm/drm_gem.c
@@ -561,8 +561,6 @@ drm_gem_release(struct drm_device *dev, struct drm_file *file_private)
 {
 	idr_for_each(&file_private->object_idr,
 		     &drm_gem_object_release_handle, file_private);
-
-	idr_remove_all(&file_private->object_idr);
 	idr_destroy(&file_private->object_idr);
 }
 
diff --git a/drivers/gpu/drm/exynos/exynos_drm_ipp.c b/drivers/gpu/drm/exynos/exynos_drm_ipp.c
index 0bda964..49278f0 100644
--- a/drivers/gpu/drm/exynos/exynos_drm_ipp.c
+++ b/drivers/gpu/drm/exynos/exynos_drm_ipp.c
@@ -1786,8 +1786,6 @@ err_iommu:
 			drm_iommu_detach_device(drm_dev, ippdrv->dev);
 
 err_idr:
-	idr_remove_all(&ctx->ipp_idr);
-	idr_remove_all(&ctx->prop_idr);
 	idr_destroy(&ctx->ipp_idr);
 	idr_destroy(&ctx->prop_idr);
 	return ret;
@@ -1965,8 +1963,6 @@ static int ipp_remove(struct platform_device *pdev)
 	exynos_drm_subdrv_unregister(&ctx->subdrv);
 
 	/* remove,destroy ipp idr */
-	idr_remove_all(&ctx->ipp_idr);
-	idr_remove_all(&ctx->prop_idr);
 	idr_destroy(&ctx->ipp_idr);
 	idr_destroy(&ctx->prop_idr);
 
diff --git a/drivers/gpu/drm/sis/sis_drv.c b/drivers/gpu/drm/sis/sis_drv.c
index 841065b..5a5325e 100644
--- a/drivers/gpu/drm/sis/sis_drv.c
+++ b/drivers/gpu/drm/sis/sis_drv.c
@@ -58,7 +58,6 @@ static int sis_driver_unload(struct drm_device *dev)
 {
 	drm_sis_private_t *dev_priv = dev->dev_private;
 
-	idr_remove_all(&dev_priv->object_idr);
 	idr_destroy(&dev_priv->object_idr);
 
 	kfree(dev_priv);
diff --git a/drivers/gpu/drm/via/via_map.c b/drivers/gpu/drm/via/via_map.c
index c0f1cc7..d0ab3fb 100644
--- a/drivers/gpu/drm/via/via_map.c
+++ b/drivers/gpu/drm/via/via_map.c
@@ -120,7 +120,6 @@ int via_driver_unload(struct drm_device *dev)
 {
 	drm_via_private_t *dev_priv = dev->dev_private;
 
-	idr_remove_all(&dev_priv->object_idr);
 	idr_destroy(&dev_priv->object_idr);
 
 	kfree(dev_priv);
-- 
1.8.1

[PATCH 06/14] dm: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Alasdair Kergon <agk@redhat.com>
Cc: dm-devel@redhat.com
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/md/dm.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/md/dm.c b/drivers/md/dm.c
index c72e4d5..ea1a6ca 100644
--- a/drivers/md/dm.c
+++ b/drivers/md/dm.c
@@ -318,7 +318,6 @@ static void __exit dm_exit(void)
 	/*
 	 * Should be empty by this point.
 	 */
-	idr_remove_all(&_minor_idr);
 	idr_destroy(&_minor_idr);
 }
 
-- 
1.8.1

[PATCH 07/14] remoteproc: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Ohad Ben-Cohen <ohad@wizery.com>
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/remoteproc/remoteproc_core.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/remoteproc/remoteproc_core.c b/drivers/remoteproc/remoteproc_core.c
index dd3bfaf..634d367 100644
--- a/drivers/remoteproc/remoteproc_core.c
+++ b/drivers/remoteproc/remoteproc_core.c
@@ -1180,7 +1180,6 @@ static void rproc_type_release(struct device *dev)
 
 	rproc_delete_debug_dir(rproc);
 
-	idr_remove_all(&rproc->notifyids);
 	idr_destroy(&rproc->notifyids);
 
 	if (rproc->index >= 0)
-- 
1.8.1

[PATCH 08/14] rpmsg: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Ohad Ben-Cohen <ohad@wizery.com>
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 drivers/rpmsg/virtio_rpmsg_bus.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/rpmsg/virtio_rpmsg_bus.c b/drivers/rpmsg/virtio_rpmsg_bus.c
index f1e3239..aa334b6 100644
--- a/drivers/rpmsg/virtio_rpmsg_bus.c
+++ b/drivers/rpmsg/virtio_rpmsg_bus.c
@@ -1036,7 +1036,6 @@ static void rpmsg_remove(struct virtio_device *vdev)
 	if (vrp->ns_ept)
 		__rpmsg_destroy_ept(vrp, vrp->ns_ept);
 
-	idr_remove_all(&vrp->endpoints);
 	idr_destroy(&vrp->endpoints);
 
 	vdev->config->del_vqs(vrp->vdev);
-- 
1.8.1

[PATCH 09/14] dlm: use idr_for_each_entry() in recover_idr_clear() error path

[Tejun Heo]

Convert recover_idr_clear() to use idr_for_each_entry() instead of
idr_for_each().  It's somewhat less efficient this way but it
shouldn't matter in an error path.  This is to help with deprecation
of idr_remove_all().

Only compile tested.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Christine Caulfield <ccaulfie@redhat.com>
Cc: David Teigland <teigland@redhat.com>
Cc: cluster-devel@redhat.com
---
This patch depends on an earlier idr patch and I think it would be
best to route these together through -mm.  Christine, David, can you
please ack this?

Thanks.

 fs/dlm/recover.c | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

diff --git a/fs/dlm/recover.c b/fs/dlm/recover.c
index aedea28..b2856e7 100644
--- a/fs/dlm/recover.c
+++ b/fs/dlm/recover.c
@@ -351,23 +351,20 @@ static struct dlm_rsb *recover_idr_find(struct dlm_ls *ls, uint64_t id)
 	return r;
 }
 
-static int recover_idr_clear_rsb(int id, void *p, void *data)
+static void recover_idr_clear(struct dlm_ls *ls)
 {
-	struct dlm_ls *ls = data;
-	struct dlm_rsb *r = p;
+	struct dlm_rsb *r;
+	int id;
 
-	r->res_id = 0;
-	r->res_recover_locks_count = 0;
-	ls->ls_recover_list_count--;
+	spin_lock(&ls->ls_recover_idr_lock);
 
-	dlm_put_rsb(r);
-	return 0;
-}
+	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
+		r->res_id = 0;
+		r->res_recover_locks_count = 0;
+		ls->ls_recover_list_count--;
 
-static void recover_idr_clear(struct dlm_ls *ls)
-{
-	spin_lock(&ls->ls_recover_idr_lock);
-	idr_for_each(&ls->ls_recover_idr, recover_idr_clear_rsb, ls);
+		dlm_put_rsb(r);
+	}
 	idr_remove_all(&ls->ls_recover_idr);
 
 	if (ls->ls_recover_list_count != 0) {
-- 
1.8.1

[PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.

The conversion isn't completely trivial for recover_idr_clear() as
it's the only place in kernel which makes legitimate use of
idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
inside idr_for_each_entry() loop.  It goes on top so that it matches
the operation order in recover_idr_del().

Only compile tested.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Christine Caulfield <ccaulfie@redhat.com>
Cc: David Teigland <teigland@redhat.com>
Cc: cluster-devel@redhat.com
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 fs/dlm/lockspace.c | 1 -
 fs/dlm/recover.c   | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/fs/dlm/lockspace.c b/fs/dlm/lockspace.c
index 2e99fb0..3ca79d3 100644
--- a/fs/dlm/lockspace.c
+++ b/fs/dlm/lockspace.c
@@ -796,7 +796,6 @@ static int release_lockspace(struct dlm_ls *ls, int force)
 	 */
 
 	idr_for_each(&ls->ls_lkbidr, lkb_idr_free, ls);
-	idr_remove_all(&ls->ls_lkbidr);
 	idr_destroy(&ls->ls_lkbidr);
 
 	/*
diff --git a/fs/dlm/recover.c b/fs/dlm/recover.c
index b2856e7..236d108 100644
--- a/fs/dlm/recover.c
+++ b/fs/dlm/recover.c
@@ -359,13 +359,13 @@ static void recover_idr_clear(struct dlm_ls *ls)
 	spin_lock(&ls->ls_recover_idr_lock);
 
 	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
+		idr_remove(&ls->ls_recover_idr, id);
 		r->res_id = 0;
 		r->res_recover_locks_count = 0;
 		ls->ls_recover_list_count--;
 
 		dlm_put_rsb(r);
 	}
-	idr_remove_all(&ls->ls_recover_idr);
 
 	if (ls->ls_recover_list_count != 0) {
 		log_error(ls, "warning: recover_list_count %d",
-- 
1.8.1

[PATCH 11/14] nfs: idr_destroy() no longer needs idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop reference to idr_remove_all().  Note that the code
wasn't completely correct before because idr_remove() on all entries
doesn't necessarily release all idr_layers which could lead to memory
leak.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: "J. Bruce Fields" <bfields@fieldses.org>
Cc: linux-nfs@vger.kernel.org
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 fs/nfs/client.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/fs/nfs/client.c b/fs/nfs/client.c
index 9f3c664..84d8eae 100644
--- a/fs/nfs/client.c
+++ b/fs/nfs/client.c
@@ -197,7 +197,6 @@ error_0:
 EXPORT_SYMBOL_GPL(nfs_alloc_client);
 
 #if IS_ENABLED(CONFIG_NFS_V4)
-/* idr_remove_all is not needed as all id's are removed by nfs_put_client */
 void nfs_cleanup_cb_ident_idr(struct net *net)
 {
 	struct nfs_net *nn = net_generic(net, nfs_net_id);
-- 
1.8.1

[PATCH 12/14] inotify: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: John McCutchan <john@johnmccutchan.com>
Cc: Robert Love <rlove@rlove.org>
Cc: Eric Paris <eparis@parisplace.org>
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 fs/notify/inotify/inotify_fsnotify.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/fs/notify/inotify/inotify_fsnotify.c b/fs/notify/inotify/inotify_fsnotify.c
index 871569c..4216308 100644
--- a/fs/notify/inotify/inotify_fsnotify.c
+++ b/fs/notify/inotify/inotify_fsnotify.c
@@ -197,7 +197,6 @@ static void inotify_free_group_priv(struct fsnotify_group *group)
 {
 	/* ideally the idr is empty and we won't hit the BUG in the callback */
 	idr_for_each(&group->inotify_data.idr, idr_callback, group);
-	idr_remove_all(&group->inotify_data.idr);
 	idr_destroy(&group->inotify_data.idr);
 	atomic_dec(&group->inotify_data.user->inotify_devs);
 	free_uid(group->inotify_data.user);
-- 
1.8.1

[PATCH 13/14] cgroup: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.  Drop its usage.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Li Zefan <lizefan@huawei.com>
Cc: containers@lists.linux-foundation.org
Cc: cgroups@vger.kernel.org
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 kernel/cgroup.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/kernel/cgroup.c b/kernel/cgroup.c
index 4855892..6b18c5c 100644
--- a/kernel/cgroup.c
+++ b/kernel/cgroup.c
@@ -4567,10 +4567,8 @@ void cgroup_unload_subsys(struct cgroup_subsys *ss)
 	offline_css(ss, dummytop);
 	ss->active = 0;
 
-	if (ss->use_id) {
-		idr_remove_all(&ss->idr);
+	if (ss->use_id)
 		idr_destroy(&ss->idr);
-	}
 
 	/* deassign the subsys_id */
 	subsys[ss->subsys_id] = NULL;
-- 
1.8.1

[PATCH 14/14] idr: deprecate idr_remove_all()

[Tejun Heo]

There was only one legitimate use of idr_remove_all() and a lot more
of incorrect uses (or lack of it).  Now that idr_destroy() implies
idr_remove_all() and all the in-kernel users updated not to use it,
there's no reason to keep it around.  Mark it deprecated so that we
can later unexport it.

idr_remove_all() is made an inline function calling __idr_remove_all()
to avoid triggering deprecated warning on EXPORT_SYMBOL().

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 include/linux/idr.h | 14 +++++++++++++-
 lib/idr.c           | 10 +++-------
 2 files changed, 16 insertions(+), 8 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index de7e190..1b932e7 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -110,10 +110,22 @@ int idr_for_each(struct idr *idp,
 void *idr_get_next(struct idr *idp, int *nextid);
 void *idr_replace(struct idr *idp, void *ptr, int id);
 void idr_remove(struct idr *idp, int id);
-void idr_remove_all(struct idr *idp);
 void idr_destroy(struct idr *idp);
 void idr_init(struct idr *idp);
 
+void __idr_remove_all(struct idr *idp);	/* don't use */
+
+/**
+ * idr_remove_all - remove all ids from the given idr tree
+ * @idp: idr handle
+ *
+ * If you're trying to destroy @idp, calling idr_destroy() is enough.
+ * This is going away.  Don't use.
+ */
+static inline void __deprecated idr_remove_all(struct idr *idp)
+{
+	__idr_remove_all(idp);
+}
 
 /*
  * IDA - IDR based id allocator, use when translation from id to
diff --git a/lib/idr.c b/lib/idr.c
index 1e47832..1408e93 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -433,11 +433,7 @@ void idr_remove(struct idr *idp, int id)
 }
 EXPORT_SYMBOL(idr_remove);
 
-/**
- * idr_remove_all - remove all ids from the given idr tree
- * @idp: idr handle
- */
-void idr_remove_all(struct idr *idp)
+void __idr_remove_all(struct idr *idp)
 {
 	int n, id, max;
 	int bt_mask;
@@ -470,7 +466,7 @@ void idr_remove_all(struct idr *idp)
 	}
 	idp->layers = 0;
 }
-EXPORT_SYMBOL(idr_remove_all);
+EXPORT_SYMBOL(__idr_remove_all);
 
 /**
  * idr_destroy - release all cached layers within an idr tree
@@ -487,7 +483,7 @@ EXPORT_SYMBOL(idr_remove_all);
  */
 void idr_destroy(struct idr *idp)
 {
-	idr_remove_all(idp);
+	__idr_remove_all(idp);
 
 	while (idp->id_free_cnt) {
 		struct idr_layer *p = get_from_free_list(idp);
-- 
1.8.1

Re: [PATCH 04/14] firewire: don't use idr_remove_all()

[Stefan Richter]

On Jan 25 Tejun Heo wrote:
> idr_destroy() can destroy idr by itself and idr_remove_all() is being
> deprecated.  Drop its usage.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Stefan Richter <stefanr@s5r6.in-berlin.de>
> Cc: linux1394-devel@lists.sourceforge.net
> ---
> This patch depends on an earlier idr patch and given the trivial
> nature of the patch, I think it would be best to route these together
> through -mm.  Please holler if there's any objection.

Acked-by: Stefan Richter <stefanr@s5r6.in-berlin.de>

> Thanks.
> 
>  drivers/firewire/core-cdev.c | 1 -
>  1 file changed, 1 deletion(-)
> 
> diff --git a/drivers/firewire/core-cdev.c b/drivers/firewire/core-cdev.c
> index f8d2287..68c3138 100644
> --- a/drivers/firewire/core-cdev.c
> +++ b/drivers/firewire/core-cdev.c
> @@ -1779,7 +1779,6 @@ static int fw_device_op_release(struct inode *inode, struct file *file)
>  	wait_event(client->tx_flush_wait, !has_outbound_transactions(client));
>  
>  	idr_for_each(&client->resource_idr, shutdown_resource, client);
> -	idr_remove_all(&client->resource_idr);
>  	idr_destroy(&client->resource_idr);
>  
>  	list_for_each_entry_safe(event, next_event, &client->event_list, link)



-- 
Stefan Richter
-=====-===-= ---= ==-=-
http://arcgraph.de/sr/

Re: [PATCH 14/14] idr: deprecate idr_remove_all()

[Arnd Bergmann]

On Saturday 26 January 2013, Tejun Heo wrote:
> 
> There was only one legitimate use of idr_remove_all() and a lot more
> of incorrect uses (or lack of it).  Now that idr_destroy() implies
> idr_remove_all() and all the in-kernel users updated not to use it,
> there's no reason to keep it around.  Mark it deprecated so that we
> can later unexport it.
> 
> idr_remove_all() is made an inline function calling __idr_remove_all()
> to avoid triggering deprecated warning on EXPORT_SYMBOL().
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>

If all in-kernel users are gone, why not just remove the function
completely?

	Arnd

Re: [PATCH 14/14] idr: deprecate idr_remove_all()

[Tejun Heo]

Hello, Arnd.

On Sat, Jan 26, 2013 at 5:48 AM, Arnd Bergmann <arnd@arndb.de> wrote:
> If all in-kernel users are gone, why not just remove the function
> completely?

Out of pure kindness of my heart for the sad folks without the grace
of mainline. I was thinking to kill it in a release cycle or two.

Thanks.

-- 
tejun

Re: [PATCH 02/14] atm/nicstar: don't use idr_remove_all()

[David Miller]

From: Tejun Heo <tj@kernel.org>
Date: Fri, 25 Jan 2013 17:31:00 -0800

> idr_destroy() can destroy idr by itself and idr_remove_all() is being
> deprecated.  Drop its usage.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Chas Williams <chas@cmf.nrl.navy.mil>
> Cc: netdev@vger.kernel.org
> ---
> This patch depends on an earlier idr patch and given the trivial
> nature of the patch, I think it would be best to route these together
> through -mm.  Please holler if there's any objection.

Please do:

Acked-by: David S. Miller <davem@davemloft.net>

Re: [PATCH 09/14] dlm: use idr_for_each_entry() in recover_idr_clear() error path

[David Teigland]

On Fri, Jan 25, 2013 at 05:31:07PM -0800, Tejun Heo wrote:
> Convert recover_idr_clear() to use idr_for_each_entry() instead of
> idr_for_each().  It's somewhat less efficient this way but it
> shouldn't matter in an error path.  This is to help with deprecation
> of idr_remove_all().
> 
> Only compile tested.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Christine Caulfield <ccaulfie@redhat.com>
> Cc: David Teigland <teigland@redhat.com>
> Cc: cluster-devel@redhat.com
> ---
> This patch depends on an earlier idr patch and I think it would be
> best to route these together through -mm.  Christine, David, can you
> please ack this?

Ack

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Fri, Jan 25, 2013 at 05:31:08PM -0800, Tejun Heo wrote:
> idr_destroy() can destroy idr by itself and idr_remove_all() is being
> deprecated.
> 
> The conversion isn't completely trivial for recover_idr_clear() as
> it's the only place in kernel which makes legitimate use of
> idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
> inside idr_for_each_entry() loop.  It goes on top so that it matches
> the operation order in recover_idr_del().
> 
> Only compile tested.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Christine Caulfield <ccaulfie@redhat.com>
> Cc: David Teigland <teigland@redhat.com>
> Cc: cluster-devel@redhat.com
> ---
> This patch depends on an earlier idr patch and given the trivial
> nature of the patch, I think it would be best to route these together
> through -mm.  Please holler if there's any objection.

Yes, that's good for me.  I'll grab the set and test the dlm bits.

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Mon, Jan 28, 2013 at 10:57:23AM -0500, David Teigland wrote:
> On Fri, Jan 25, 2013 at 05:31:08PM -0800, Tejun Heo wrote:
> > idr_destroy() can destroy idr by itself and idr_remove_all() is being
> > deprecated.
> > 
> > The conversion isn't completely trivial for recover_idr_clear() as
> > it's the only place in kernel which makes legitimate use of
> > idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
> > inside idr_for_each_entry() loop.  It goes on top so that it matches
> > the operation order in recover_idr_del().
> > 
> > Only compile tested.
> > 
> > Signed-off-by: Tejun Heo <tj@kernel.org>
> > Cc: Christine Caulfield <ccaulfie@redhat.com>
> > Cc: David Teigland <teigland@redhat.com>
> > Cc: cluster-devel@redhat.com
> > ---
> > This patch depends on an earlier idr patch and given the trivial
> > nature of the patch, I think it would be best to route these together
> > through -mm.  Please holler if there's any objection.
> 
> Yes, that's good for me.  I'll grab the set and test the dlm bits.

Hi Tejun,
Unfortunately, the list_for_each_entry doesn't seem to be clearing
everything.  I've seen "warning: recover_list_count 39" at the end of that
function.
Dave

Re: [PATCH 11/14] nfs: idr_destroy() no longer needs idr_remove_all()

[J. Bruce Fields]

On Fri, Jan 25, 2013 at 05:31:09PM -0800, Tejun Heo wrote:
> idr_destroy() can destroy idr by itself and idr_remove_all() is being
> deprecated.  Drop reference to idr_remove_all().  Note that the code
> wasn't completely correct before because idr_remove() on all entries
> doesn't necessarily release all idr_layers which could lead to memory
> leak.

Seems fine, but actually this is client-side so I think you meant the cc
to be to Trond.

--b.

> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: "J. Bruce Fields" <bfields@fieldses.org>
> Cc: linux-nfs@vger.kernel.org
> ---
> This patch depends on an earlier idr patch and given the trivial
> nature of the patch, I think it would be best to route these together
> through -mm.  Please holler if there's any objection.
> 
> Thanks.
> 
>  fs/nfs/client.c | 1 -
>  1 file changed, 1 deletion(-)
> 
> diff --git a/fs/nfs/client.c b/fs/nfs/client.c
> index 9f3c664..84d8eae 100644
> --- a/fs/nfs/client.c
> +++ b/fs/nfs/client.c
> @@ -197,7 +197,6 @@ error_0:
>  EXPORT_SYMBOL_GPL(nfs_alloc_client);
>  
>  #if IS_ENABLED(CONFIG_NFS_V4)
> -/* idr_remove_all is not needed as all id's are removed by nfs_put_client */
>  void nfs_cleanup_cb_ident_idr(struct net *net)
>  {
>  	struct nfs_net *nn = net_generic(net, nfs_net_id);
> -- 
> 1.8.1
> 

Re: [PATCH 11/14] nfs: idr_destroy() no longer needs idr_remove_all()

[Myklebust, Trond]

On Tue, 2013-01-29 at 17:58 -0500, J. Bruce Fields wrote:
> On Fri, Jan 25, 2013 at 05:31:09PM -0800, Tejun Heo wrote:
> > idr_destroy() can destroy idr by itself and idr_remove_all() is being
> > deprecated.  Drop reference to idr_remove_all().  Note that the code
> > wasn't completely correct before because idr_remove() on all entries
> > doesn't necessarily release all idr_layers which could lead to memory
> > leak.
> 
> Seems fine, but actually this is client-side so I think you meant the cc
> to be to Trond.

Acked-by: Trond Myklebust <Trond.Myklebust@netapp.com>

No problems whatsoever with removing a comment. :-)

My worry is more about Tejun's comment that we did actually need a call
to idr_remove_all() in the original code. Do we need to queue up a fix
for the 3.8 and existing stable kernels?

Cheers
  Trond

> > Signed-off-by: Tejun Heo <tj@kernel.org>
> > Cc: "J. Bruce Fields" <bfields@fieldses.org>
> > Cc: linux-nfs@vger.kernel.org
> > ---
> > This patch depends on an earlier idr patch and given the trivial
> > nature of the patch, I think it would be best to route these together
> > through -mm.  Please holler if there's any objection.
> > 
> > Thanks.
> > 
> >  fs/nfs/client.c | 1 -
> >  1 file changed, 1 deletion(-)
> > 
> > diff --git a/fs/nfs/client.c b/fs/nfs/client.c
> > index 9f3c664..84d8eae 100644
> > --- a/fs/nfs/client.c
> > +++ b/fs/nfs/client.c
> > @@ -197,7 +197,6 @@ error_0:
> >  EXPORT_SYMBOL_GPL(nfs_alloc_client);
> >  
> >  #if IS_ENABLED(CONFIG_NFS_V4)
> > -/* idr_remove_all is not needed as all id's are removed by nfs_put_client */
> >  void nfs_cleanup_cb_ident_idr(struct net *net)
> >  {
> >  	struct nfs_net *nn = net_generic(net, nfs_net_id);
> > -- 
> > 1.8.1
> > 

-- 
Trond Myklebust
Linux NFS client maintainer

NetApp
Trond.Myklebust@netapp.com
www.netapp.com

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Tue, Jan 29, 2013 at 10:13:17AM -0500, David Teigland wrote:
> On Mon, Jan 28, 2013 at 10:57:23AM -0500, David Teigland wrote:
> > On Fri, Jan 25, 2013 at 05:31:08PM -0800, Tejun Heo wrote:
> > > idr_destroy() can destroy idr by itself and idr_remove_all() is being
> > > deprecated.
> > > 
> > > The conversion isn't completely trivial for recover_idr_clear() as
> > > it's the only place in kernel which makes legitimate use of
> > > idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
> > > inside idr_for_each_entry() loop.  It goes on top so that it matches
> > > the operation order in recover_idr_del().
> > > 
> > > Only compile tested.
> > > 
> > > Signed-off-by: Tejun Heo <tj@kernel.org>
> > > Cc: Christine Caulfield <ccaulfie@redhat.com>
> > > Cc: David Teigland <teigland@redhat.com>
> > > Cc: cluster-devel@redhat.com
> > > ---
> > > This patch depends on an earlier idr patch and given the trivial
> > > nature of the patch, I think it would be best to route these together
> > > through -mm.  Please holler if there's any objection.
> > 
> > Yes, that's good for me.  I'll grab the set and test the dlm bits.
> 
> Hi Tejun,
> Unfortunately, the list_for_each_entry doesn't seem to be clearing
> everything.  I've seen "warning: recover_list_count 39" at the end of that
> function.

I don't want to pretend to understand the internals of this idr code, but
it's not clear that idr_for_each is equivalent to idr_for_each_entry when
iterating through all id values.  The "++id" in idr_for_each_entry looks
like it could lead to some missed entries?  The comment about idr_get_next
returning the "next number to given id" sounds like an entry with an id of
"++id" would be missed.

Dave

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

Hello, David.

Sorry about the delay.

On Wed, Jan 30, 2013 at 04:24:18PM -0500, David Teigland wrote:
> > Unfortunately, the list_for_each_entry doesn't seem to be clearing
> > everything.  I've seen "warning: recover_list_count 39" at the end of that
> > function.
> 
> I don't want to pretend to understand the internals of this idr code, but
> it's not clear that idr_for_each is equivalent to idr_for_each_entry when
> iterating through all id values.  The "++id" in idr_for_each_entry looks
> like it could lead to some missed entries?  The comment about idr_get_next
> returning the "next number to given id" sounds like an entry with an id of
> "++id" would be missed.

The function description is misleading.  The function does search
inclusive range and needs explicit cursor increment to make progress.
Weird that it doesn't work.  Looking into it.  I'll write when I know
more.

Thanks!

-- 
tejun

Re: [PATCH 11/14] nfs: idr_destroy() no longer needs idr_remove_all()

[Tejun Heo]

Hello, Trond.

On Wed, Jan 30, 2013 at 02:18:06AM +0000, Myklebust, Trond wrote:
> My worry is more about Tejun's comment that we did actually need a call
> to idr_remove_all() in the original code. Do we need to queue up a fix
> for the 3.8 and existing stable kernels?

IIUC, the only case where idr_layer is left around after idr_remove()
on all elems is when the deletions lead to multi-level left-most
collapse.  Not sure whether the current code can actually hit that.
No harm in adding idr_remove_all(), I guess.

Thanks.

-- 
tejun

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

Hello, David.

On Thu, Jan 31, 2013 at 03:53:20PM -0800, Tejun Heo wrote:
> The function description is misleading.  The function does search
> inclusive range and needs explicit cursor increment to make progress.
> Weird that it doesn't work.  Looking into it.  I'll write when I know
> more.

It looks a bit weird to me that ls->ls_recover_list_count is also
incremented by recover_list_add().  The two code paths don't seem to
be interlocke at least upon my very shallow glance.  Is it that only
either the list or idr is in use?

Anyways, can you please apply the following patch and see which IDs
are leaking from the iteration?  The patch too is only compile tested
so I might have done something stupid but it hopefully shouldn't be
too difficult to make it work.

Thanks!
---
 fs/dlm/recover.c |   12 ++++++++++++
 1 file changed, 12 insertions(+)

--- a/fs/dlm/recover.c
+++ b/fs/dlm/recover.c
@@ -351,6 +351,12 @@ static struct dlm_rsb *recover_idr_find(
 	return r;
 }
 
+static int dlm_dump_idr(int id, void *p, void *data)
+{
+	pr_cont(" %d", id);
+	return 0;
+}
+
 static void recover_idr_clear(struct dlm_ls *ls)
 {
 	struct dlm_rsb *r;
@@ -358,7 +364,9 @@ static void recover_idr_clear(struct dlm
 
 	spin_lock(&ls->ls_recover_idr_lock);
 
+	pr_info("XXX clearing:");
 	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
+		pr_cont(" %d", id);
 		idr_remove(&ls->ls_recover_idr, id);
 		r->res_id = 0;
 		r->res_recover_locks_count = 0;
@@ -366,10 +374,14 @@ static void recover_idr_clear(struct dlm
 
 		dlm_put_rsb(r);
 	}
+	pr_cont("\n");
 
 	if (ls->ls_recover_list_count != 0) {
 		log_error(ls, "warning: recover_list_count %d",
 			  ls->ls_recover_list_count);
+		pr_info("XXX leftovers: ");
+		idr_for_each(&ls->ls_recover_idr, dlm_dump_idr, NULL);
+		pr_cont("\n");
 		ls->ls_recover_list_count = 0;
 	}
 	spin_unlock(&ls->ls_recover_idr_lock);

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Thu, Jan 31, 2013 at 04:18:41PM -0800, Tejun Heo wrote:
> It looks a bit weird to me that ls->ls_recover_list_count is also
> incremented by recover_list_add().  The two code paths don't seem to
> be interlocke at least upon my very shallow glance.  Is it that only
> either the list or idr is in use?

Yes, that's correct.

> Anyways, can you please apply the following patch and see which IDs
> are leaking from the iteration?  The patch too is only compile tested
> so I might have done something stupid but it hopefully shouldn't be
> too difficult to make it work.

I'm trying your patch now, I don't have a test optimized to hit this code
so it may take a while.

>  static void recover_idr_clear(struct dlm_ls *ls)
>  {
>  	struct dlm_rsb *r;
> @@ -358,7 +364,9 @@ static void recover_idr_clear(struct dlm
>  
>  	spin_lock(&ls->ls_recover_idr_lock);
>  
> +	pr_info("XXX clearing:");
>  	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
> +		pr_cont(" %d", id);

It will often be clearing hundreds of thousands of entries, so this will
probably be excessive.

>  	if (ls->ls_recover_list_count != 0) {
>  		log_error(ls, "warning: recover_list_count %d",
>  			  ls->ls_recover_list_count);
> +		pr_info("XXX leftovers: ");
> +		idr_for_each(&ls->ls_recover_idr, dlm_dump_idr, NULL);
> +		pr_cont("\n");

I already tried my own version of this, but used idr_for_each_entry a
second time.  Unfortunately, the number it found and printed did not match
recover_list_count.

warning: recover_list_count 566

It printed 304 ids:

41218 41222 41223 41224 41226 41228 41229 41230 41231 41232 41234 41235
41236 41237 41239 41241 41242 41243 41244 41245 41246 41249 41252 41253
41254 41255 41256 41257 41259 41260 41261 41263 41264 41266 41271 41272
41273 41274 41277 41278 41475 41480 41483 41524 41525 41526 41655 41731
41741 41745 41749 41767 41768 41769 41772 41773 41782 42113 42114 42115
42121 42122 42124 42128 42132 42136 42138 42139 42141 42165 42375 42381
42385 42388 42390 42392 42399 42401 42404 42407 42409 42411 42416 42422
42694 42699 42712 42717 42727 42866 43009 43042 43044 43046 43049 43051
43058 43059 43064 43065 43066 43067 43330 43332 43337 43338 43339 43343
43348 43349 43351 43354 43355 43356 43361 43362 43368 43369 43370 43375
43376 43377 43378 43379 43381 43575 43576 43577 43677 43678 43680 43683
43684 43685 43689 43690 43819 43820 43823 43824 43825 43826 43827 43828
43829 43831 43905 43907 43908 43912 43929 43930 43955 43956 43960 43962
43965 44288 44289 44291 44296 44298 44300 44310 44311 44313 44314 44316
44318 44321 44323 44325 44454 44456 44457 44458 44544 44547 44548 44550
44555 44557 44560 44562 44564 44567 44573 44575 44576 44578 44579 44581
44582 44583 44584 44585 44589 44592 44595 44596 44726 44728 44729 44732
44734 44866 44867 44873 44876 44878 44879 44912 44914 44916 44920 44923
44924 45053 45186 45189 45190 45195 45197 45199 45200 45201 45203 45204
45208 45209 45212 45213 45216 45220 45223 45224 45225 45227 45228 45231
45234 45440 45441 45444 45448 45450 45452 45454 45456 45457 45458 45459
45460 45461 45464 45466 45467 45472 45475 45477 45484 45485 45488 45492
45494 45495 45496 45497 45498 45499 45628 45630 45698 45699 45700 45703
45707 45708 45710 45713 45715 45717 45720 45722 45723 45724 45725 45727
45729 45730 45731 45733 45734 45737 45739 45741 45742 45746 45748 45750
45755 47292 47293 47294

Re: [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

Hello, David.

On Fri, Feb 01, 2013 at 12:44:43PM -0500, David Teigland wrote:
> I already tried my own version of this, but used idr_for_each_entry a
> second time.  Unfortunately, the number it found and printed did not match
> recover_list_count.
> 
> warning: recover_list_count 566
> 
> It printed 304 ids:

Heh, that's really weird.  Maybe idr_get_next() is buggy above certain
number or at certain boundaries?  If you find something, please let me
know.  I'll see if I can reproduce it in some minimal way.

Thanks!

-- 
tejun

[PATCH] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

The iteration logic of idr_get_next() is borrowed mostly verbatim from
idr_for_each().  It walks down the tree looking for the slot matching
the current ID.  If the matching slot is not found, the ID is
incremented by the distance of single slot at the given level and
repeats.

The implementation assumes that during the whole iteration id is
aligned to the layer boundaries of the level closest to the leaf,
which is true for all iterations starting from zero or an existing
element and thus is fine for idr_for_each().

However, idr_get_next() may be given any point and if the starting id
hits in the middle of a non-existent layer, increment to the next
layer will end up skipping the same offset into it.  For example, an
IDR with IDs filled between [64, 127] would look like the following.

          [  0  64 ... ]
       /----/   |
       |        |
      NULL    [ 64 ... 127 ]

If idr_get_next() is called with 63 as the starting point, it will try
to follow down the pointer from 0.  As it is NULL, it will then try to
proceed to the next slot in the same level by adding the slot distance
at that level which is 64 - making the next try 127.  It goes around
the loop and finds and returns 127 skipping [64, 126].

Note that this bug also triggers in idr_for_each_entry() loop which
deletes during iteration as deletions can make layers go away leaving
the iteration with unaligned ID into missing layers.

Fix it by ensuring proceeding to the next slot doesn't carry over the
unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
id += slot_distance.

Signed-off-by: Tejun Heo <tj@kernel.org>
Reported-by: David Teigland <teigland@redhat.com>
Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
---
 lib/idr.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/lib/idr.c b/lib/idr.c
index 6482390..ca5aa00 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -625,7 +625,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
 			return p;
 		}
 
-		id += 1 << n;
+		/*
+		 * Proceed to the next layer at the current level.  Unlike
+		 * idr_for_each(), @id isn't guaranteed to be aligned to
+		 * layer boundary at this point and adding 1 << n may
+		 * incorrectly skip IDs.  Make sure we jump to the
+		 * beginning of the next layer using round_up().
+		 */
+		id = round_up(id + 1, 1 << n);
 		while (n < fls(id)) {
 			n += IDR_BITS;
 			p = *--paa;

Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
> Fix it by ensuring proceeding to the next slot doesn't carry over the
> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> id += slot_distance.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Reported-by: David Teigland <teigland@redhat.com>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>

David, can you please test whether the patch makes the skipped
deletion bug go away?

Thanks!

-- 
tejun

Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[Randy Dunlap]

On 02/02/13 15:11, Tejun Heo wrote:
> On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
>> Fix it by ensuring proceeding to the next slot doesn't carry over the
>> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
>> id += slot_distance.
>>
>> Signed-off-by: Tejun Heo <tj@kernel.org>
>> Reported-by: David Teigland <teigland@redhat.com>
>> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> 
> David, can you please test whether the patch makes the skipped
> deletion bug go away?
> 
> Thanks!

Hugh, did you update the idr test suite or the radix-tree test suite?

Is there an idr test suite or module?  I have a kernel module source file
named idr_test.c by Eric Paris.

thanks,

-- 
~Randy

Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[Hugh Dickins]

On Sat, 2 Feb 2013, Randy Dunlap wrote:
> On 02/02/13 15:11, Tejun Heo wrote:
> > On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
> >> Fix it by ensuring proceeding to the next slot doesn't carry over the
> >> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> >> id += slot_distance.
> >>
> >> Signed-off-by: Tejun Heo <tj@kernel.org>
> >> Reported-by: David Teigland <teigland@redhat.com>
> >> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> > 
> > David, can you please test whether the patch makes the skipped
> > deletion bug go away?
> > 
> > Thanks!
> 
> Hugh, did you update the idr test suite or the radix-tree test suite?

Sorry, not the answer you want: it was the radix-tree test harness, rtth,
that I updated a year ago (but then lib/radix-tree.c changed again).

Hugh

> 
> Is there an idr test suite or module?  I have a kernel module source file
> named idr_test.c by Eric Paris.
> 
> thanks,
> 
> -- 
> ~Randy

Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[Li Zefan]

On 2013/2/3 7:10, Tejun Heo wrote:
> The iteration logic of idr_get_next() is borrowed mostly verbatim from
> idr_for_each().  It walks down the tree looking for the slot matching
> the current ID.  If the matching slot is not found, the ID is
> incremented by the distance of single slot at the given level and
> repeats.
> 
> The implementation assumes that during the whole iteration id is
> aligned to the layer boundaries of the level closest to the leaf,
> which is true for all iterations starting from zero or an existing
> element and thus is fine for idr_for_each().
> 
> However, idr_get_next() may be given any point and if the starting id
> hits in the middle of a non-existent layer, increment to the next
> layer will end up skipping the same offset into it.  For example, an
> IDR with IDs filled between [64, 127] would look like the following.
> 
>           [  0  64 ... ]
>        /----/   |
>        |        |
>       NULL    [ 64 ... 127 ]
> 
> If idr_get_next() is called with 63 as the starting point, it will try
> to follow down the pointer from 0.  As it is NULL, it will then try to
> proceed to the next slot in the same level by adding the slot distance
> at that level which is 64 - making the next try 127.  It goes around
> the loop and finds and returns 127 skipping [64, 126].
> 
> Note that this bug also triggers in idr_for_each_entry() loop which
> deletes during iteration as deletions can make layers go away leaving
> the iteration with unaligned ID into missing layers.
> 
> Fix it by ensuring proceeding to the next slot doesn't carry over the
> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> id += slot_distance.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>

Don't we need to cc stable?

> Reported-by: David Teigland <teigland@redhat.com>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> ---
>  lib/idr.c |    9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/idr.c b/lib/idr.c
> index 6482390..ca5aa00 100644
> --- a/lib/idr.c
> +++ b/lib/idr.c
> @@ -625,7 +625,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
>  			return p;
>  		}
>  
> -		id += 1 << n;
> +		/*
> +		 * Proceed to the next layer at the current level.  Unlike
> +		 * idr_for_each(), @id isn't guaranteed to be aligned to
> +		 * layer boundary at this point and adding 1 << n may
> +		 * incorrectly skip IDs.  Make sure we jump to the
> +		 * beginning of the next layer using round_up().
> +		 */
> +		id = round_up(id + 1, 1 << n);
>  		while (n < fls(id)) {
>  			n += IDR_BITS;
>  			p = *--paa;
> --

Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

Hey, Li.

On Mon, Feb 04, 2013 at 11:39:50AM +0800, Li Zefan wrote:
> > Fix it by ensuring proceeding to the next slot doesn't carry over the
> > unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> > id += slot_distance.
> > 
> > Signed-off-by: Tejun Heo <tj@kernel.org>
> 
> Don't we need to cc stable?

I thought we didn't have idr_remove() inside idr_for_each_entry() in
kernel, which isn't true.  drbd already does that, so yeah, we need to
cc stable.

Thanks.

-- 
tejun

[PATCH v2 02/14] atm/nicstar: don't use idr_remove_all()

[Tejun Heo]

Subject: atm/nicstar: convert to idr_alloc()

Convert to the much saner new idr interface.  The existing code looks
buggy to me - ID 0 is treated as no-ID but allocation specifies 0 as
lower limit and there's no error handling after partial success.  This
conversion keeps the bugs unchanged.

Only compile tested.

v2: id1 and id2 are now directly used for -errno return and thus
    should be signed.  Make them int instead of u32.  This was spotted
    by kbuild test robot.

Signed-off-by: Tejun Heo <tj@kernel.org>
Acked-by: Chas Williams <chas@cmf.nrl.navy.mil>
Reported-by: kbuild test robot <fengguang.wu@intel.com>
Cc: netdev@vger.kernel.org
---
 drivers/atm/nicstar.c |   29 +++++++++++++----------------
 1 file changed, 13 insertions(+), 16 deletions(-)

--- a/drivers/atm/nicstar.c
+++ b/drivers/atm/nicstar.c
@@ -949,7 +949,7 @@ static void free_scq(ns_dev *card, scq_i
 static void push_rxbufs(ns_dev * card, struct sk_buff *skb)
 {
 	struct sk_buff *handle1, *handle2;
-	u32 id1 = 0, id2 = 0;
+	int id1 = 0, id2 = 0;
 	u32 addr1, addr2;
 	u32 stat;
 	unsigned long flags;
@@ -1026,24 +1026,21 @@ static void push_rxbufs(ns_dev * card, s
 				card->lbfqc += 2;
 		}
 
-		do {
-			if (!idr_pre_get(&card->idr, GFP_ATOMIC)) {
-				printk(KERN_ERR
-				       "nicstar%d: no free memory for idr\n",
-				       card->index);
+		if (id1 < 0) {
+			id1 = idr_alloc(&card->idr, handle1, 0, 0, GFP_ATOMIC);
+			if (id1 < 0) {
+				err = id1;
 				goto out;
 			}
+		}
 
-			if (!id1)
-				err = idr_get_new_above(&card->idr, handle1, 0, &id1);
-
-			if (!id2 && err == 0)
-				err = idr_get_new_above(&card->idr, handle2, 0, &id2);
-
-		} while (err == -EAGAIN);
-
-		if (err)
-			goto out;
+		if (id2 < 0) {
+			id2 = idr_alloc(&card->idr, handle2, 0, 0, GFP_ATOMIC);
+			if (id2 < 0) {
+				err = id2;
+				goto out;
+			}
+		}
 
 		spin_lock_irqsave(&card->res_lock, flags);
 		while (CMD_BUSY(card)) ;

Re: [PATCH v2 02/14] atm/nicstar: don't use idr_remove_all()

[chas williams - CONTRACTOR]

On Mon, 4 Feb 2013 09:52:10 -0800
Tejun Heo <tj@kernel.org> wrote:

> Subject: atm/nicstar: convert to idr_alloc()
> 
> Convert to the much saner new idr interface.  The existing code looks
> buggy to me - ID 0 is treated as no-ID but allocation specifies 0 as
> lower limit and there's no error handling after partial success.  This
> conversion keeps the bugs unchanged.
> 
> Only compile tested.
> 
> v2: id1 and id2 are now directly used for -errno return and thus
>     should be signed.  Make them int instead of u32.  This was spotted
>     by kbuild test robot.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Acked-by: Chas Williams <chas@cmf.nrl.navy.mil>
> Reported-by: kbuild test robot <fengguang.wu@intel.com>
> Cc: netdev@vger.kernel.org
> ---
>  drivers/atm/nicstar.c |   29 +++++++++++++----------------
>  1 file changed, 13 insertions(+), 16 deletions(-)
> 
> --- a/drivers/atm/nicstar.c
> +++ b/drivers/atm/nicstar.c
> @@ -949,7 +949,7 @@ static void free_scq(ns_dev *card, scq_i
>  static void push_rxbufs(ns_dev * card, struct sk_buff *skb)
>  {
>  	struct sk_buff *handle1, *handle2;
> -	u32 id1 = 0, id2 = 0;
> +	int id1 = 0, id2 = 0;
>  	u32 addr1, addr2;
>  	u32 stat;
>  	unsigned long flags;
> @@ -1026,24 +1026,21 @@ static void push_rxbufs(ns_dev * card, s
>  				card->lbfqc += 2;
>  		}
>  
> -		do {
> -			if (!idr_pre_get(&card->idr, GFP_ATOMIC)) {
> -				printk(KERN_ERR
> -				       "nicstar%d: no free memory for idr\n",
> -				       card->index);
> +		if (id1 < 0) {

you assign id1 to 0, so this never happens i think.  i don't think the
reason to preassign id1/id2 exists anymore once the do loop is removed.

> +			id1 = idr_alloc(&card->idr, handle1, 0, 0, GFP_ATOMIC);
> +			if (id1 < 0) {
> +				err = id1;

you dont need to assign err since it isn't returned.

>  				goto out;
>  			}
> +		}
>  
> -			if (!id1)
> -				err = idr_get_new_above(&card->idr, handle1, 0, &id1);
> -
> -			if (!id2 && err == 0)
> -				err = idr_get_new_above(&card->idr, handle2, 0, &id2);
> -
> -		} while (err == -EAGAIN);
> -
> -		if (err)
> -			goto out;
> +		if (id2 < 0) {

same as above.

> +			id2 = idr_alloc(&card->idr, handle2, 0, 0, GFP_ATOMIC);
> +			if (id2 < 0) {
> +				err = id2;
> +				goto out;
> +			}
> +		}
>  
>  		spin_lock_irqsave(&card->res_lock, flags);
>  		while (CMD_BUSY(card)) ;

Re: [PATCH v2 02/14] atm/nicstar: don't use idr_remove_all()

[Tejun Heo]

Hey,

On Mon, Feb 04, 2013 at 01:10:34PM -0500, chas williams - CONTRACTOR wrote:
> you assign id1 to 0, so this never happens i think.  i don't think the
> reason to preassign id1/id2 exists anymore once the do loop is removed.
> 
> > +			id1 = idr_alloc(&card->idr, handle1, 0, 0, GFP_ATOMIC);
> > +			if (id1 < 0) {
> > +				err = id1;
> 
> you dont need to assign err since it isn't returned.

Heh, I put v2 under the wrong thread.  I'll do v3 and post it under
v1.

Thanks.

-- 
tejun

Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[David Teigland]

On Sat, Feb 02, 2013 at 03:11:35PM -0800, Tejun Heo wrote:
> On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
> > Fix it by ensuring proceeding to the next slot doesn't carry over the
> > unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> > id += slot_distance.
> > 
> > Signed-off-by: Tejun Heo <tj@kernel.org>
> > Reported-by: David Teigland <teigland@redhat.com>
> > Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> 
> David, can you please test whether the patch makes the skipped
> deletion bug go away?

Yes, I've tested, and it works fine now.
Thanks,
Dave