[PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[Bodo Stroesser]

This small series is based on Martin's for-next.

Future patches will need something like the - meanwhile removed -
radix_tree_for_each_contig macro.
Since general direction is to use xarray as replacement for
radix_tree and IDR, instead of re-introducing or open coding the
removed macro, with this series we switch over to xarray API.
Based on xarray a future patch easily can implement an analog
to radix_tree_for_each_contig.

Bodo Stroesser (2):
  scsi: target: tcmu: Replace IDR by XArray
  scsi: target: tcmu: Replace radix_tree with XArray

 drivers/target/target_core_user.c | 64 +++++++++++++++++++--------------------
 1 file changed, 31 insertions(+), 33 deletions(-)

-- 
2.12.3

[PATCH 1/2] scsi: target: tcmu: Replace IDR by XArray

[Bodo Stroesser]

An attempt from Matthew Wilcox to replace IDR usage by XArray
in tcmu more than 1 year ago unfortunately got lost.

I rebased that work on latest tcmu and tested it.

Signed-off-by: Bodo Stroesser <bostroesser@gmail.com>
---
 drivers/target/target_core_user.c | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

diff --git a/drivers/target/target_core_user.c b/drivers/target/target_core_user.c
index bf73cd5f4b04..1fbfb307d5e5 100644
--- a/drivers/target/target_core_user.c
+++ b/drivers/target/target_core_user.c
@@ -8,12 +8,12 @@
 
 #include <linux/spinlock.h>
 #include <linux/module.h>
-#include <linux/idr.h>
 #include <linux/kernel.h>
 #include <linux/timer.h>
 #include <linux/parser.h>
 #include <linux/vmalloc.h>
 #include <linux/uio_driver.h>
+#include <linux/xarray.h>
 #include <linux/radix-tree.h>
 #include <linux/stringify.h>
 #include <linux/bitops.h>
@@ -145,7 +145,7 @@ struct tcmu_dev {
 	unsigned long *data_bitmap;
 	struct radix_tree_root data_blocks;
 
-	struct idr commands;
+	struct xarray commands;
 
 	struct timer_list cmd_timer;
 	unsigned int cmd_time_out;
@@ -977,8 +977,8 @@ static int queue_cmd_ring(struct tcmu_cmd *tcmu_cmd, sense_reason_t *scsi_err)
 	struct tcmu_mailbox *mb = udev->mb_addr;
 	struct tcmu_cmd_entry *entry;
 	struct iovec *iov;
-	int iov_cnt, iov_bidi_cnt, cmd_id;
-	uint32_t cmd_head;
+	int iov_cnt, iov_bidi_cnt;
+	uint32_t cmd_id, cmd_head;
 	uint64_t cdb_off;
 	/* size of data buffer needed */
 	size_t data_length = (size_t)tcmu_cmd->dbi_cnt * DATA_BLOCK_SIZE;
@@ -1031,8 +1031,8 @@ static int queue_cmd_ring(struct tcmu_cmd *tcmu_cmd, sense_reason_t *scsi_err)
 		 */
 		goto free_and_queue;
 
-	cmd_id = idr_alloc(&udev->commands, tcmu_cmd, 1, USHRT_MAX, GFP_NOWAIT);
-	if (cmd_id < 0) {
+	if (xa_alloc(&udev->commands, &cmd_id, tcmu_cmd, XA_LIMIT(1, 0xffff),
+		     GFP_NOWAIT) < 0) {
 		pr_err("tcmu: Could not allocate cmd id.\n");
 
 		tcmu_cmd_free_data(tcmu_cmd, tcmu_cmd->dbi_cnt);
@@ -1415,7 +1415,7 @@ static unsigned int tcmu_handle_completions(struct tcmu_dev *udev)
 		}
 		WARN_ON(tcmu_hdr_get_op(entry->hdr.len_op) != TCMU_OP_CMD);
 
-		cmd = idr_remove(&udev->commands, entry->hdr.cmd_id);
+		cmd = xa_erase(&udev->commands, entry->hdr.cmd_id);
 		if (!cmd) {
 			pr_err("cmd_id %u not found, ring is broken\n",
 			       entry->hdr.cmd_id);
@@ -1433,7 +1433,7 @@ static unsigned int tcmu_handle_completions(struct tcmu_dev *udev)
 		free_space = tcmu_run_tmr_queue(udev);
 
 	if (atomic_read(&global_db_count) > tcmu_global_max_blocks &&
-	    idr_is_empty(&udev->commands) && list_empty(&udev->qfull_queue)) {
+	    xa_empty(&udev->commands) && list_empty(&udev->qfull_queue)) {
 		/*
 		 * Allocated blocks exceeded global block limit, currently no
 		 * more pending or waiting commands so try to reclaim blocks.
@@ -1556,7 +1556,7 @@ static struct se_device *tcmu_alloc_device(struct se_hba *hba, const char *name)
 	INIT_LIST_HEAD(&udev->qfull_queue);
 	INIT_LIST_HEAD(&udev->tmr_queue);
 	INIT_LIST_HEAD(&udev->inflight_queue);
-	idr_init(&udev->commands);
+	xa_init_flags(&udev->commands, XA_FLAGS_ALLOC1);
 
 	timer_setup(&udev->qfull_timer, tcmu_qfull_timedout, 0);
 	timer_setup(&udev->cmd_timer, tcmu_cmd_timedout, 0);
@@ -1616,7 +1616,7 @@ static void tcmu_dev_kref_release(struct kref *kref)
 	struct se_device *dev = &udev->se_dev;
 	struct tcmu_cmd *cmd;
 	bool all_expired = true;
-	int i;
+	unsigned long i;
 
 	vfree(udev->mb_addr);
 	udev->mb_addr = NULL;
@@ -1628,7 +1628,7 @@ static void tcmu_dev_kref_release(struct kref *kref)
 
 	/* Upper layer should drain all requests before calling this */
 	mutex_lock(&udev->cmdr_lock);
-	idr_for_each_entry(&udev->commands, cmd, i) {
+	xa_for_each(&udev->commands, i, cmd) {
 		if (tcmu_check_and_free_pending_cmd(cmd) != 0)
 			all_expired = false;
 	}
@@ -1636,7 +1636,7 @@ static void tcmu_dev_kref_release(struct kref *kref)
 	tcmu_remove_all_queued_tmr(udev);
 	if (!list_empty(&udev->qfull_queue))
 		all_expired = false;
-	idr_destroy(&udev->commands);
+	xa_destroy(&udev->commands);
 	WARN_ON(!all_expired);
 
 	tcmu_blocks_release(&udev->data_blocks, 0, udev->dbi_max + 1);
@@ -2226,16 +2226,16 @@ static void tcmu_reset_ring(struct tcmu_dev *udev, u8 err_level)
 {
 	struct tcmu_mailbox *mb;
 	struct tcmu_cmd *cmd;
-	int i;
+	unsigned long i;
 
 	mutex_lock(&udev->cmdr_lock);
 
-	idr_for_each_entry(&udev->commands, cmd, i) {
+	xa_for_each(&udev->commands, i, cmd) {
 		pr_debug("removing cmd %u on dev %s from ring (is expired %d)\n",
 			  cmd->cmd_id, udev->name,
 			  test_bit(TCMU_CMD_BIT_EXPIRED, &cmd->flags));
 
-		idr_remove(&udev->commands, i);
+		xa_erase(&udev->commands, i);
 		if (!test_bit(TCMU_CMD_BIT_EXPIRED, &cmd->flags)) {
 			WARN_ON(!cmd->se_cmd);
 			list_del_init(&cmd->queue_entry);
-- 
2.12.3

[PATCH 2/2] scsi: target: tcmu: Replace radix_tree with XArray

[Bodo Stroesser]

An attempt from Matthew Wilcox to replace radix-tree usage by
XArray in tcmu more than 1 year ago unfortunately got lost.

I rebased that work on latest tcmu and tested it.

Signed-off-by: Bodo Stroesser <bostroesser@gmail.com>
---
 drivers/target/target_core_user.c | 34 ++++++++++++++++------------------
 1 file changed, 16 insertions(+), 18 deletions(-)

diff --git a/drivers/target/target_core_user.c b/drivers/target/target_core_user.c
index 1fbfb307d5e5..067e00e37673 100644
--- a/drivers/target/target_core_user.c
+++ b/drivers/target/target_core_user.c
@@ -14,7 +14,6 @@
 #include <linux/vmalloc.h>
 #include <linux/uio_driver.h>
 #include <linux/xarray.h>
-#include <linux/radix-tree.h>
 #include <linux/stringify.h>
 #include <linux/bitops.h>
 #include <linux/highmem.h>
@@ -143,7 +142,7 @@ struct tcmu_dev {
 	uint32_t dbi_max;
 	uint32_t dbi_thresh;
 	unsigned long *data_bitmap;
-	struct radix_tree_root data_blocks;
+	struct xarray data_blocks;
 
 	struct xarray commands;
 
@@ -500,13 +499,13 @@ static inline int tcmu_get_empty_block(struct tcmu_dev *udev,
 				       int prev_dbi, int *iov_cnt)
 {
 	struct page *page;
-	int ret, dbi;
+	int dbi;
 
 	dbi = find_first_zero_bit(udev->data_bitmap, udev->dbi_thresh);
 	if (dbi == udev->dbi_thresh)
 		return -1;
 
-	page = radix_tree_lookup(&udev->data_blocks, dbi);
+	page = xa_load(&udev->data_blocks, dbi);
 	if (!page) {
 		if (atomic_add_return(1, &global_db_count) >
 				      tcmu_global_max_blocks)
@@ -517,8 +516,7 @@ static inline int tcmu_get_empty_block(struct tcmu_dev *udev,
 		if (!page)
 			goto err_alloc;
 
-		ret = radix_tree_insert(&udev->data_blocks, dbi, page);
-		if (ret)
+		if (xa_store(&udev->data_blocks, dbi, page, GFP_KERNEL))
 			goto err_insert;
 	}
 
@@ -557,7 +555,7 @@ static int tcmu_get_empty_blocks(struct tcmu_dev *udev,
 static inline struct page *
 tcmu_get_block_page(struct tcmu_dev *udev, uint32_t dbi)
 {
-	return radix_tree_lookup(&udev->data_blocks, dbi);
+	return xa_load(&udev->data_blocks, dbi);
 }
 
 static inline void tcmu_free_cmd(struct tcmu_cmd *tcmu_cmd)
@@ -1561,7 +1559,7 @@ static struct se_device *tcmu_alloc_device(struct se_hba *hba, const char *name)
 	timer_setup(&udev->qfull_timer, tcmu_qfull_timedout, 0);
 	timer_setup(&udev->cmd_timer, tcmu_cmd_timedout, 0);
 
-	INIT_RADIX_TREE(&udev->data_blocks, GFP_KERNEL);
+	xa_init(&udev->data_blocks);
 
 	return &udev->se_dev;
 }
@@ -1585,19 +1583,19 @@ static int tcmu_check_and_free_pending_cmd(struct tcmu_cmd *cmd)
 	return -EINVAL;
 }
 
-static void tcmu_blocks_release(struct radix_tree_root *blocks,
-				int start, int end)
+static void tcmu_blocks_release(struct xarray *blocks, unsigned long first,
+				unsigned long last)
 {
-	int i;
+	XA_STATE(xas, blocks, first);
 	struct page *page;
 
-	for (i = start; i < end; i++) {
-		page = radix_tree_delete(blocks, i);
-		if (page) {
-			__free_page(page);
-			atomic_dec(&global_db_count);
-		}
+	xas_lock(&xas);
+	xas_for_each(&xas, page, last) {
+		xas_store(&xas, NULL);
+		__free_page(page);
+		atomic_dec(&global_db_count);
 	}
+	xas_unlock(&xas);
 }
 
 static void tcmu_remove_all_queued_tmr(struct tcmu_dev *udev)
@@ -2923,7 +2921,7 @@ static void find_free_blocks(void)
 		unmap_mapping_range(udev->inode->i_mapping, off, 0, 1);
 
 		/* Release the block pages */
-		tcmu_blocks_release(&udev->data_blocks, start, end);
+		tcmu_blocks_release(&udev->data_blocks, start, end - 1);
 		mutex_unlock(&udev->cmdr_lock);
 
 		total_freed += end - start;
-- 
2.12.3

Re: [PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[michael.christie]

On 2/24/21 12:53 PM, Bodo Stroesser wrote:
> This small series is based on Martin's for-next.
> 
> Future patches will need something like the - meanwhile removed -
> radix_tree_for_each_contig macro.
> Since general direction is to use xarray as replacement for
> radix_tree and IDR, instead of re-introducing or open coding the
> removed macro, with this series we switch over to xarray API.
> Based on xarray a future patch easily can implement an analog
> to radix_tree_for_each_contig.
> 
> Bodo Stroesser (2):
>   scsi: target: tcmu: Replace IDR by XArray
>   scsi: target: tcmu: Replace radix_tree with XArray
> 
>  drivers/target/target_core_user.c | 64 +++++++++++++++++++--------------------
>  1 file changed, 31 insertions(+), 33 deletions(-)
> 

Looks ok to me.

Reviewed-by: Mike Christie <michael.christie@oracle.com>

I think in a separate patch we need to change:

+		if (xa_store(&udev->data_blocks, dbi, page, GFP_KERNEL))
 			goto err_insert;

to GFP_NOIO. There were some users doing tcm loop  + tcmu and
were hitting issues when GFP_KERNEL lead to write backs back on
to the same tcmu device. We tried to change all the gfp flags but
we missed that one, because it was hidden in the radix tree's
xa_flags.

Re: [PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[Bodo Stroesser]

On 26.02.21 04:59, michael.christie@oracle.com wrote:
> On 2/24/21 12:53 PM, Bodo Stroesser wrote:
>> This small series is based on Martin's for-next.
>>
>> Future patches will need something like the - meanwhile removed -
>> radix_tree_for_each_contig macro.
>> Since general direction is to use xarray as replacement for
>> radix_tree and IDR, instead of re-introducing or open coding the
>> removed macro, with this series we switch over to xarray API.
>> Based on xarray a future patch easily can implement an analog
>> to radix_tree_for_each_contig.
>>
>> Bodo Stroesser (2):
>>    scsi: target: tcmu: Replace IDR by XArray
>>    scsi: target: tcmu: Replace radix_tree with XArray
>>
>>   drivers/target/target_core_user.c | 64 +++++++++++++++++++--------------------
>>   1 file changed, 31 insertions(+), 33 deletions(-)
>>
> 
> Looks ok to me.
> 
> Reviewed-by: Mike Christie <michael.christie@oracle.com>
> 
> I think in a separate patch we need to change:
> 
> +		if (xa_store(&udev->data_blocks, dbi, page, GFP_KERNEL))
>   			goto err_insert;
> 
> to GFP_NOIO. There were some users doing tcm loop  + tcmu and
> were hitting issues when GFP_KERNEL lead to write backs back on
> to the same tcmu device. We tried to change all the gfp flags but
> we missed that one, because it was hidden in the radix tree's
> xa_flags.
> 

But then, for consistency reasons, shouldn't we change

+	if (xa_alloc(&udev->commands, &cmd_id, tcmu_cmd, XA_LIMIT(1, 0xffff),
+		     GFP_NOWAIT) < 0) {

to GFP_NOIO also?

Additionally I have to change memory allocation in tcmu_tmr_notify from
GFP_KERNEL to GFP_NOIO, since it happens while holding cmdr_lock mutex,
which could also cause the problems you desribed.

Shouldn't we better change to new API memalloc_noio_save and
memalloc_noio_restore in that new patch?

Re: [PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[Mike Christie]

On 2/26/21 2:41 AM, Bodo Stroesser wrote:
> On 26.02.21 04:59, michael.christie@oracle.com wrote:
>> On 2/24/21 12:53 PM, Bodo Stroesser wrote:
>>> This small series is based on Martin's for-next.
>>>
>>> Future patches will need something like the - meanwhile removed -
>>> radix_tree_for_each_contig macro.
>>> Since general direction is to use xarray as replacement for
>>> radix_tree and IDR, instead of re-introducing or open coding the
>>> removed macro, with this series we switch over to xarray API.
>>> Based on xarray a future patch easily can implement an analog
>>> to radix_tree_for_each_contig.
>>>
>>> Bodo Stroesser (2):
>>>    scsi: target: tcmu: Replace IDR by XArray
>>>    scsi: target: tcmu: Replace radix_tree with XArray
>>>
>>>   drivers/target/target_core_user.c | 64 +++++++++++++++++++--------------------
>>>   1 file changed, 31 insertions(+), 33 deletions(-)
>>>
>>
>> Looks ok to me.
>>
>> Reviewed-by: Mike Christie <michael.christie@oracle.com>
>>
>> I think in a separate patch we need to change:
>>
>> +        if (xa_store(&udev->data_blocks, dbi, page, GFP_KERNEL))
>>               goto err_insert;
>>
>> to GFP_NOIO. There were some users doing tcm loop  + tcmu and
>> were hitting issues when GFP_KERNEL lead to write backs back on
>> to the same tcmu device. We tried to change all the gfp flags but
>> we missed that one, because it was hidden in the radix tree's
>> xa_flags.
>>
> 
> But then, for consistency reasons, shouldn't we change
> 
> +    if (xa_alloc(&udev->commands, &cmd_id, tcmu_cmd, XA_LIMIT(1, 0xffff),
> +             GFP_NOWAIT) < 0) {
> 
> to GFP_NOIO also?

I think so, but am not sure. I've always wondered why we used
GFP_NOWAIT and meant to test with different gfp values but didn't
have time. It wouldn't hit the same issue I mentioned though.

> 
> Additionally I have to change memory allocation in tcmu_tmr_notify from
> GFP_KERNEL to GFP_NOIO, since it happens while holding cmdr_lock mutex,
> which could also cause the problems you desribed.
> 
> Shouldn't we better change to new API memalloc_noio_save and
> memalloc_noio_restore in that new patch?

I think it's your preference. I like to use the correct gfp
when I can, so you can just look at that chunk of code and
know it's right. If you put memalloc_noio_save in tcmu_queue_cmd
then a couple functions down you have a GFP_KERNEL it's
confusing when you are just searching the code.

I think memalloc_noio_save is handy in other places like the
iscsi/nbd code since when calling into the network stack you can't
control all the allocations sometimes.

Re: [PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[Bodo Stroesser]

On 26.02.21 17:04, Mike Christie wrote:
> On 2/26/21 2:41 AM, Bodo Stroesser wrote:
>> On 26.02.21 04:59, michael.christie@oracle.com wrote:
>>> On 2/24/21 12:53 PM, Bodo Stroesser wrote:
>>>> This small series is based on Martin's for-next.
>>>>
>>>> Future patches will need something like the - meanwhile removed -
>>>> radix_tree_for_each_contig macro.
>>>> Since general direction is to use xarray as replacement for
>>>> radix_tree and IDR, instead of re-introducing or open coding the
>>>> removed macro, with this series we switch over to xarray API.
>>>> Based on xarray a future patch easily can implement an analog
>>>> to radix_tree_for_each_contig.
>>>>
>>>> Bodo Stroesser (2):
>>>>     scsi: target: tcmu: Replace IDR by XArray
>>>>     scsi: target: tcmu: Replace radix_tree with XArray
>>>>
>>>>    drivers/target/target_core_user.c | 64 +++++++++++++++++++--------------------
>>>>    1 file changed, 31 insertions(+), 33 deletions(-)
>>>>
>>>
>>> Looks ok to me.
>>>
>>> Reviewed-by: Mike Christie <michael.christie@oracle.com>
>>>
>>> I think in a separate patch we need to change:
>>>
>>> +        if (xa_store(&udev->data_blocks, dbi, page, GFP_KERNEL))
>>>                goto err_insert;
>>>
>>> to GFP_NOIO. There were some users doing tcm loop  + tcmu and
>>> were hitting issues when GFP_KERNEL lead to write backs back on
>>> to the same tcmu device. We tried to change all the gfp flags but
>>> we missed that one, because it was hidden in the radix tree's
>>> xa_flags.
>>>
>>
>> But then, for consistency reasons, shouldn't we change
>>
>> +    if (xa_alloc(&udev->commands, &cmd_id, tcmu_cmd, XA_LIMIT(1, 0xffff),
>> +             GFP_NOWAIT) < 0) {
>>
>> to GFP_NOIO also?
> 
> I think so, but am not sure. I've always wondered why we used
> GFP_NOWAIT and meant to test with different gfp values but didn't
> have time. It wouldn't hit the same issue I mentioned though.
> 

I'll send a patch changing it to GFP_NOIO.
There is no reason to disallow sleeping. Just IO should be avoided
as you said.

>>
>> Additionally I have to change memory allocation in tcmu_tmr_notify from
>> GFP_KERNEL to GFP_NOIO, since it happens while holding cmdr_lock mutex,
>> which could also cause the problems you desribed.
>>
>> Shouldn't we better change to new API memalloc_noio_save and
>> memalloc_noio_restore in that new patch?
> 
> I think it's your preference. I like to use the correct gfp
> when I can, so you can just look at that chunk of code and
> know it's right. If you put memalloc_noio_save in tcmu_queue_cmd
> then a couple functions down you have a GFP_KERNEL it's
> confusing when you are just searching the code.
> 

Good point. I'll stay with GFP_NOIO.

> I think memalloc_noio_save is handy in other places like the
> iscsi/nbd code since when calling into the network stack you can't
> control all the allocations sometimes.
> 
> 
> 

Re: [PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[Martin K. Petersen]

Bodo,

> Future patches will need something like the - meanwhile removed -
> radix_tree_for_each_contig macro.  Since general direction is to use
> xarray as replacement for radix_tree and IDR, instead of
> re-introducing or open coding the removed macro, with this series we
> switch over to xarray API.  Based on xarray a future patch easily can
> implement an analog to radix_tree_for_each_contig.

Applied to 5.13/scsi-staging, thanks!

-- 
Martin K. Petersen	Oracle Linux Engineering

Re: [PATCH 0/2] scsi: target: tcmu: Replace IDR and radix_tree with XArray

[Martin K. Petersen]

On Wed, 24 Feb 2021 19:53:33 +0100, Bodo Stroesser wrote:

> This small series is based on Martin's for-next.
> 
> Future patches will need something like the - meanwhile removed -
> radix_tree_for_each_contig macro.
> Since general direction is to use xarray as replacement for
> radix_tree and IDR, instead of re-introducing or open coding the
> removed macro, with this series we switch over to xarray API.
> Based on xarray a future patch easily can implement an analog
> to radix_tree_for_each_contig.
> 
> [...]

Applied to 5.13/scsi-queue, thanks!

[1/2] scsi: target: tcmu: Replace IDR by XArray
      https://git.kernel.org/mkp/scsi/c/d3cbb743c362
[2/2] scsi: target: tcmu: Replace radix_tree with XArray
      https://git.kernel.org/mkp/scsi/c/f7c89771d07d

-- 
Martin K. Petersen	Oracle Linux Engineering