idr: deprecate idr_remove_all()

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

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.

---
 lib/idr.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

index 6482390..1e47832 100644
@@ -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

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

---
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(-)

index ed1d2b7..628787e 100644
@@ -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

From: Tejun Heo <[email protected]>
Date: Fri, 25 Jan 2013 17:31:00 -0800

Please do:

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.

---
 drivers/atm/nicstar.c |   29 +++++++++++++----------------
 1 file changed, 13 insertions(+), 16 deletions(-)

@@ -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)) ;

Hey,

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

Thanks.

tejun

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

---
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(-)

index ae12512..3b9c32b 100644
@@ -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

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

---
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(-)

index f8d2287..68c3138 100644
@@ -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

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().

---
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(-)

index 45adf97..75f62c5 100644
@@ -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);
 }
 

index f2d667b..9b39d1f 100644
@@ -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);

index be174ca..25f91cd 100644
@@ -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);
 }
 

index 24efae4..e775859 100644
@@ -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);
 }
 

index 0bda964..49278f0 100644
@@ -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);
 

index 841065b..5a5325e 100644
@@ -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);

index c0f1cc7..d0ab3fb 100644
@@ -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

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

---
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(-)

index c72e4d5..ea1a6ca 100644
@@ -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

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

---
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(-)

index dd3bfaf..634d367 100644
@@ -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

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

---
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(-)

index f1e3239..aa334b6 100644
@@ -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

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.

---
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(-)

index aedea28..b2856e7 100644
@@ -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

Ack

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.

---
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(-)

index 2e99fb0..3ca79d3 100644
@@ -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);
 
 	/*

index b2856e7..236d108 100644
@@ -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

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

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

Hello, David.

Sorry about the delay.

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

Hello, David.

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(+)

@@ -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);

Yes, that's correct.

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

Hello, David.

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

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.

---
 lib/idr.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

index 6482390..ca5aa00 100644
@@ -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@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;

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

Thanks!

tejun

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

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

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

Don't we need to cc stable?

Hey, Li.

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

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.

---
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(-)

index 9f3c664..84d8eae 100644
@@ -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

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

--b.

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

Trond Myklebust
Linux NFS client maintainer

NetApp
[email protected]
www.netapp.com

Hello, Trond.

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

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

---
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(-)

index 871569c..4216308 100644
@@ -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

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

---
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(-)

index 4855892..6b18c5c 100644
@@ -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

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().

---
 include/linux/idr.h | 14 +++++++++++++-
 lib/idr.c           | 10 +++-------
 2 files changed, 16 insertions(+), 8 deletions(-)

index de7e190..1b932e7 100644
@@ -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

index 1e47832..1408e93 100644
@@ -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

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

Arnd

Hello, Arnd.

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