[Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Fabio M. De Francesco]

Converted visorhba from IDR to XArray. The abstract data type XArray is
more memory-efficient, parallelisable and cache friendly. It takes 
advantage of RCU to perform lookups without locking.

Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
---
 .../staging/unisys/visorhba/visorhba_main.c   | 107 +++++++-----------
 1 file changed, 44 insertions(+), 63 deletions(-)

diff --git a/drivers/staging/unisys/visorhba/visorhba_main.c b/drivers/staging/unisys/visorhba/visorhba_main.c
index 4455d26f7c96..851e60ab0c46 100644
--- a/drivers/staging/unisys/visorhba/visorhba_main.c
+++ b/drivers/staging/unisys/visorhba/visorhba_main.c
@@ -6,10 +6,10 @@
 
 #include <linux/debugfs.h>
 #include <linux/kthread.h>
-#include <linux/idr.h>
 #include <linux/module.h>
 #include <linux/seq_file.h>
 #include <linux/visorbus.h>
+#include <linux/xarray.h>
 #include <scsi/scsi.h>
 #include <scsi/scsi_host.h>
 #include <scsi/scsi_cmnd.h>
@@ -23,6 +23,8 @@
 #define MAX_PENDING_REQUESTS (MIN_NUMSIGNALS * 2)
 #define VISORHBA_ERROR_COUNT 30
 
+static DEFINE_XARRAY_ALLOC(xa_dtstr);
+
 static struct dentry *visorhba_debugfs_dir;
 
 /* GUIDS for HBA channel type supported by this driver */
@@ -78,12 +80,6 @@ struct visorhba_devdata {
 	unsigned int max_buff_len;
 	int devnum;
 	struct uiscmdrsp *cmdrsp;
-	/*
-	 * allows us to pass int handles back-and-forth between us and
-	 * iovm, instead of raw pointers
-	 */
-	struct idr idr;
-
 	struct dentry *debugfs_dir;
 	struct dentry *debugfs_info;
 };
@@ -183,32 +179,16 @@ static struct uiscmdrsp *get_scsipending_cmdrsp(struct visorhba_devdata *ddata,
 }
 
 /*
- * simple_idr_get - Associate a provided pointer with an int value
- *		    1 <= value <= INT_MAX, and return this int value;
- *		    the pointer value can be obtained later by passing
- *		    this int value to idr_find()
- * @idrtable: The data object maintaining the pointer<-->int mappings
- * @p:	      The pointer value to be remembered
- * @lock:     A spinlock used when exclusive access to idrtable is needed
- *
- * Return: The id number mapped to pointer 'p', 0 on failure
+ * simple_xa_dtstr_get - Store a pointer to xa_dtstr xarray
+ * @id: Pointer to ID
+ * @entry: New entry
  */
-static unsigned int simple_idr_get(struct idr *idrtable, void *p,
-				   spinlock_t *lock)
+static int simple_xa_dtstr_get(u32 *id, void *entry)
 {
-	int id;
-	unsigned long flags;
+	int ret = xa_alloc_irq(&xa_dtstr, id, entry, xa_limit_32b, GFP_NOWAIT);
+	/* TODO: check for and manage errors */
 
-	idr_preload(GFP_KERNEL);
-	spin_lock_irqsave(lock, flags);
-	id = idr_alloc(idrtable, p, 1, INT_MAX, GFP_NOWAIT);
-	spin_unlock_irqrestore(lock, flags);
-	idr_preload_end();
-	/* failure */
-	if (id < 0)
-		return 0;
-	/* idr_alloc() guarantees > 0 */
-	return (unsigned int)(id);
+	return ret;
 }
 
 /*
@@ -216,22 +196,25 @@ static unsigned int simple_idr_get(struct idr *idrtable, void *p,
  *				completion processing logic for a taskmgmt
  *				cmd will be able to find who to wake up
  *				and where to stash the result
- * @idrtable: The data object maintaining the pointer<-->int mappings
- * @lock:     A spinlock used when exclusive access to idrtable is needed
+ * @xa_dtstr: The data object maintaining the pointer<-->int mappings
  * @cmdrsp:   Response from the IOVM
  * @event:    The event handle to associate with an id
  * @result:   The location to place the result of the event handle into
  */
-static void setup_scsitaskmgmt_handles(struct idr *idrtable, spinlock_t *lock,
-				       struct uiscmdrsp *cmdrsp,
-				       wait_queue_head_t *event, int *result)
+static void setup_scsitaskmgmt_handles(struct uiscmdrsp *cmdrsp,
+				       wait_queue_head_t *event, u32 *result)
 {
-	/* specify the event that has to be triggered when this */
-	/* cmd is complete */
-	cmdrsp->scsitaskmgmt.notify_handle =
-		simple_idr_get(idrtable, event, lock);
-	cmdrsp->scsitaskmgmt.notifyresult_handle =
-		simple_idr_get(idrtable, result, lock);
+	void *entry;
+	int ret;
+
+	/* specify the event that has to be triggered when this cmd is complete */
+	entry = &cmdrsp->scsitaskmgmt.notify_handle;
+	ret = simple_xa_dtstr_get(result, entry);
+	/* TODO: Check for and manage errors */
+
+	entry = &cmdrsp->scsitaskmgmt.notifyresult_handle;
+	ret = simple_xa_dtstr_get(result, entry);
+	/* TODO: Check for and manage errors */
 }
 
 /*
@@ -240,13 +223,17 @@ static void setup_scsitaskmgmt_handles(struct idr *idrtable, spinlock_t *lock,
  * @idrtable: The data object maintaining the pointer<-->int mappings
  * @cmdrsp:   Response from the IOVM
  */
-static void cleanup_scsitaskmgmt_handles(struct idr *idrtable,
-					 struct uiscmdrsp *cmdrsp)
+static void cleanup_scsitaskmgmt_handles(struct uiscmdrsp_scsitaskmgmt *scsitaskmgmt)
 {
-	if (cmdrsp->scsitaskmgmt.notify_handle)
-		idr_remove(idrtable, cmdrsp->scsitaskmgmt.notify_handle);
-	if (cmdrsp->scsitaskmgmt.notifyresult_handle)
-		idr_remove(idrtable, cmdrsp->scsitaskmgmt.notifyresult_handle);
+	struct uiscmdrsp *cmdrsp;
+	unsigned long index;
+
+	xa_for_each(&xa_dtstr, index, cmdrsp) {
+		if (&cmdrsp->scsitaskmgmt != scsitaskmgmt)
+			continue;
+		xa_erase(&xa_dtstr, index);
+		kfree(cmdrsp);
+	}
 }
 
 /*
@@ -273,8 +260,7 @@ static int forward_taskmgmt_command(enum task_mgmt_types tasktype,
 	if (devdata->serverdown || devdata->serverchangingstate)
 		return FAILED;
 
-	scsicmd_id = add_scsipending_entry(devdata, CMD_SCSITASKMGMT_TYPE,
-					   NULL);
+	scsicmd_id = add_scsipending_entry(devdata, CMD_SCSITASKMGMT_TYPE, NULL);
 	if (scsicmd_id < 0)
 		return FAILED;
 
@@ -284,8 +270,7 @@ static int forward_taskmgmt_command(enum task_mgmt_types tasktype,
 
 	/* issue TASK_MGMT_ABORT_TASK */
 	cmdrsp->cmdtype = CMD_SCSITASKMGMT_TYPE;
-	setup_scsitaskmgmt_handles(&devdata->idr, &devdata->privlock, cmdrsp,
-				   &notifyevent, &notifyresult);
+	setup_scsitaskmgmt_handles(cmdrsp, &notifyevent, &notifyresult);
 
 	/* save destination */
 	cmdrsp->scsitaskmgmt.tasktype = tasktype;
@@ -311,14 +296,14 @@ static int forward_taskmgmt_command(enum task_mgmt_types tasktype,
 	dev_dbg(&scsidev->sdev_gendev,
 		"visorhba: taskmgmt type=%d success; result=0x%x\n",
 		 tasktype, notifyresult);
-	cleanup_scsitaskmgmt_handles(&devdata->idr, cmdrsp);
+	cleanup_scsitaskmgmt_handles(&cmdrsp->scsitaskmgmt);
 	return SUCCESS;
 
 err_del_scsipending_ent:
 	dev_dbg(&scsidev->sdev_gendev,
 		"visorhba: taskmgmt type=%d not executed\n", tasktype);
 	del_scsipending_ent(devdata, scsicmd_id);
-	cleanup_scsitaskmgmt_handles(&devdata->idr, cmdrsp);
+	cleanup_scsitaskmgmt_handles(&cmdrsp->scsitaskmgmt);
 	return FAILED;
 }
 
@@ -654,13 +639,12 @@ DEFINE_SHOW_ATTRIBUTE(info_debugfs);
  * Service Partition returned the result of the task management
  * command. Wake up anyone waiting for it.
  */
-static void complete_taskmgmt_command(struct idr *idrtable,
-				      struct uiscmdrsp *cmdrsp, int result)
+static void complete_taskmgmt_command(struct uiscmdrsp *cmdrsp, int result)
 {
 	wait_queue_head_t *wq =
-		idr_find(idrtable, cmdrsp->scsitaskmgmt.notify_handle);
+		xa_load(&xa_dtstr, cmdrsp->scsitaskmgmt.notify_handle);
 	int *scsi_result_ptr =
-		idr_find(idrtable, cmdrsp->scsitaskmgmt.notifyresult_handle);
+		xa_load(&xa_dtstr, cmdrsp->scsitaskmgmt.notifyresult_handle);
 	if (unlikely(!(wq && scsi_result_ptr))) {
 		pr_err("visorhba: no completion context; cmd will time out\n");
 		return;
@@ -708,8 +692,7 @@ static void visorhba_serverdown_complete(struct visorhba_devdata *devdata)
 			break;
 		case CMD_SCSITASKMGMT_TYPE:
 			cmdrsp = pendingdel->sent;
-			complete_taskmgmt_command(&devdata->idr, cmdrsp,
-						  TASK_MGMT_FAILED);
+			complete_taskmgmt_command(cmdrsp, TASK_MGMT_FAILED);
 			break;
 		default:
 			break;
@@ -905,7 +888,7 @@ static void drain_queue(struct uiscmdrsp *cmdrsp,
 			if (!del_scsipending_ent(devdata,
 						 cmdrsp->scsitaskmgmt.handle))
 				break;
-			complete_taskmgmt_command(&devdata->idr, cmdrsp,
+			complete_taskmgmt_command(cmdrsp,
 						  cmdrsp->scsitaskmgmt.result);
 		} else if (cmdrsp->cmdtype == CMD_NOTIFYGUEST_TYPE)
 			dev_err_once(&devdata->dev->device,
@@ -1053,8 +1036,6 @@ static int visorhba_probe(struct visor_device *dev)
 	if (err)
 		goto err_debugfs_info;
 
-	idr_init(&devdata->idr);
-
 	devdata->cmdrsp = kmalloc(sizeof(*devdata->cmdrsp), GFP_ATOMIC);
 	visorbus_enable_channel_interrupts(dev);
 
@@ -1096,7 +1077,7 @@ static void visorhba_remove(struct visor_device *dev)
 	scsi_remove_host(scsihost);
 	scsi_host_put(scsihost);
 
-	idr_destroy(&devdata->idr);
+	xa_destroy(&xa_dtstr);
 
 	dev_set_drvdata(&dev->device, NULL);
 	debugfs_remove(devdata->debugfs_info);
-- 
2.31.1

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Greg Kroah-Hartman]

On Mon, Apr 26, 2021 at 11:50:15AM +0200, Fabio M. De Francesco wrote:
> Converted visorhba from IDR to XArray. The abstract data type XArray is
> more memory-efficient, parallelisable and cache friendly. It takes 
> advantage of RCU to perform lookups without locking.
> 
> Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
> ---
>  .../staging/unisys/visorhba/visorhba_main.c   | 107 +++++++-----------
>  1 file changed, 44 insertions(+), 63 deletions(-)
> 
> diff --git a/drivers/staging/unisys/visorhba/visorhba_main.c b/drivers/staging/unisys/visorhba/visorhba_main.c
> index 4455d26f7c96..851e60ab0c46 100644
> --- a/drivers/staging/unisys/visorhba/visorhba_main.c
> +++ b/drivers/staging/unisys/visorhba/visorhba_main.c
> @@ -6,10 +6,10 @@
>  
>  #include <linux/debugfs.h>
>  #include <linux/kthread.h>
> -#include <linux/idr.h>
>  #include <linux/module.h>
>  #include <linux/seq_file.h>
>  #include <linux/visorbus.h>
> +#include <linux/xarray.h>
>  #include <scsi/scsi.h>
>  #include <scsi/scsi_host.h>
>  #include <scsi/scsi_cmnd.h>
> @@ -23,6 +23,8 @@
>  #define MAX_PENDING_REQUESTS (MIN_NUMSIGNALS * 2)
>  #define VISORHBA_ERROR_COUNT 30
>  
> +static DEFINE_XARRAY_ALLOC(xa_dtstr);
> +
>  static struct dentry *visorhba_debugfs_dir;
>  
>  /* GUIDS for HBA channel type supported by this driver */
> @@ -78,12 +80,6 @@ struct visorhba_devdata {
>  	unsigned int max_buff_len;
>  	int devnum;
>  	struct uiscmdrsp *cmdrsp;
> -	/*
> -	 * allows us to pass int handles back-and-forth between us and
> -	 * iovm, instead of raw pointers
> -	 */
> -	struct idr idr;
> -
>  	struct dentry *debugfs_dir;
>  	struct dentry *debugfs_info;
>  };
> @@ -183,32 +179,16 @@ static struct uiscmdrsp *get_scsipending_cmdrsp(struct visorhba_devdata *ddata,
>  }
>  
>  /*
> - * simple_idr_get - Associate a provided pointer with an int value
> - *		    1 <= value <= INT_MAX, and return this int value;
> - *		    the pointer value can be obtained later by passing
> - *		    this int value to idr_find()
> - * @idrtable: The data object maintaining the pointer<-->int mappings
> - * @p:	      The pointer value to be remembered
> - * @lock:     A spinlock used when exclusive access to idrtable is needed
> - *
> - * Return: The id number mapped to pointer 'p', 0 on failure
> + * simple_xa_dtstr_get - Store a pointer to xa_dtstr xarray
> + * @id: Pointer to ID
> + * @entry: New entry
>   */
> -static unsigned int simple_idr_get(struct idr *idrtable, void *p,
> -				   spinlock_t *lock)
> +static int simple_xa_dtstr_get(u32 *id, void *entry)

What are you trying to really "get" here?  We shouldn't name the
function based on the data type being used.  All we want is some sort of
"token" or hash or something else?  It's hard to tell...

>  {
> -	int id;
> -	unsigned long flags;
> +	int ret = xa_alloc_irq(&xa_dtstr, id, entry, xa_limit_32b, GFP_NOWAIT);
> +	/* TODO: check for and manage errors */

That's a nice TODO, which means we really should not be considering this
patch to be merged, right?

thanks,

greg k-h

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Julia Lawall]

> @@ -273,8 +260,7 @@ static int forward_taskmgmt_command(enum task_mgmt_types tasktype,
>  	if (devdata->serverdown || devdata->serverchangingstate)
>  		return FAILED;
>
> -	scsicmd_id = add_scsipending_entry(devdata, CMD_SCSITASKMGMT_TYPE,
> -					   NULL);
> +	scsicmd_id = add_scsipending_entry(devdata, CMD_SCSITASKMGMT_TYPE, NULL);
>  	if (scsicmd_id < 0)
>  		return FAILED;
>

As far as I can see, this is just a whitespace change, so it shouldn't be
in with the rest.  If you make whitspace changes, they should be in with
the other code that you are changing.

julia

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Fabio M. De Francesco]

On Monday, April 26, 2021 11:56:21 AM CEST Greg Kroah-Hartman wrote:
> On Mon, Apr 26, 2021 at 11:50:15AM +0200, Fabio M. De Francesco wrote:
> > Converted visorhba from IDR to XArray. The abstract data type XArray is
> > more memory-efficient, parallelisable and cache friendly. It takes
> > advantage of RCU to perform lookups without locking.
> > 
> > Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
> > ---
> > 
> >  .../staging/unisys/visorhba/visorhba_main.c   | 107 +++++++-----------
> >  1 file changed, 44 insertions(+), 63 deletions(-)
> > 
> > diff --git a/drivers/staging/unisys/visorhba/visorhba_main.c
> > b/drivers/staging/unisys/visorhba/visorhba_main.c index 
4455d26f7c96..851e60ab0c46
> > 100644
> > --- a/drivers/staging/unisys/visorhba/visorhba_main.c
> > +++ b/drivers/staging/unisys/visorhba/visorhba_main.c
> > @@ -6,10 +6,10 @@
> > 
> >  #include <linux/debugfs.h>
> >  #include <linux/kthread.h>
> > 
> > -#include <linux/idr.h>
> > 
> >  #include <linux/module.h>
> >  #include <linux/seq_file.h>
> >  #include <linux/visorbus.h>
> > 
> > +#include <linux/xarray.h>
> > 
> >  #include <scsi/scsi.h>
> >  #include <scsi/scsi_host.h>
> >  #include <scsi/scsi_cmnd.h>
> > 
> > @@ -23,6 +23,8 @@
> > 
> >  #define MAX_PENDING_REQUESTS (MIN_NUMSIGNALS * 2)
> >  #define VISORHBA_ERROR_COUNT 30
> > 
> > +static DEFINE_XARRAY_ALLOC(xa_dtstr);
> > +
> > 
> >  static struct dentry *visorhba_debugfs_dir;
> >  
> >  /* GUIDS for HBA channel type supported by this driver */
> > 
> > @@ -78,12 +80,6 @@ struct visorhba_devdata {
> > 
> >  	unsigned int max_buff_len;
> >  	int devnum;
> >  	struct uiscmdrsp *cmdrsp;
> > 
> > -	/*
> > -	 * allows us to pass int handles back-and-forth between us and
> > -	 * iovm, instead of raw pointers
> > -	 */
> > -	struct idr idr;
> > -
> > 
> >  	struct dentry *debugfs_dir;
> >  	struct dentry *debugfs_info;
> >  
> >  };
> > 
> > @@ -183,32 +179,16 @@ static struct uiscmdrsp 
*get_scsipending_cmdrsp(struct
> > visorhba_devdata *ddata,> 
> >  }
> >  
> >  /*
> > 
> > - * simple_idr_get - Associate a provided pointer with an int value
> > - *		    1 <= value <= INT_MAX, and return this int value;
> > - *		    the pointer value can be obtained later by passing
> > - *		    this int value to idr_find()
> > - * @idrtable: The data object maintaining the pointer<-->int mappings
> > - * @p:	      The pointer value to be remembered
> > - * @lock:     A spinlock used when exclusive access to idrtable is needed
> > - *
> > - * Return: The id number mapped to pointer 'p', 0 on failure
> > + * simple_xa_dtstr_get - Store a pointer to xa_dtstr xarray
> > + * @id: Pointer to ID
> > + * @entry: New entry
> > 
> >   */
> > 
> > -static unsigned int simple_idr_get(struct idr *idrtable, void *p,
> > -				   spinlock_t *lock)
> > +static int simple_xa_dtstr_get(u32 *id, void *entry)
> 
> What are you trying to really "get" here?  We shouldn't name the
> function based on the data type being used.  All we want is some sort of
> "token" or hash or something else?  It's hard to tell...
> 
Sorry, I am so lazy that I just substituted the _idr_ in the old name with 
_xa_dtstr_. Perhaps simple_entry_get() would be better. it deserves a v2.
>
> >  {
> > 
> > -	int id;
> > -	unsigned long flags;
> > +	int ret = xa_alloc_irq(&xa_dtstr, id, entry, xa_limit_32b, 
GFP_NOWAIT);
> > +	/* TODO: check for and manage errors */
> 
> That's a nice TODO, which means we really should not be considering this
> patch to be merged, right?
>
Right, lazy again :)

The fact is that I was just interested in conversion from IDR to XArray 
because this would be the main subject of the project I applied for the DRM 
subsystem. Therefore, where I didn't find proper error checking and management 
in the old code, I simply wrote some TODO. 

I suppose that some more knowledge of both Linux device drivers programming 
and of that specific driver is needed to do proper management of errors in 
order to unwind what is already done by the code and leave everything in a 
consistent state. I'd left that work to Unisys developers, if you don't mind. 
I'd prefer to simply remove those TODO from where I placed them. I hope that 
you agree with me.

Thanks for your review,

Fabio 
> 
> thanks,
> 
> greg k-h

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Julia Lawall]

On Mon, 26 Apr 2021, Fabio M. De Francesco wrote:

> On Monday, April 26, 2021 11:56:21 AM CEST Greg Kroah-Hartman wrote:
> > On Mon, Apr 26, 2021 at 11:50:15AM +0200, Fabio M. De Francesco wrote:
> > > Converted visorhba from IDR to XArray. The abstract data type XArray is
> > > more memory-efficient, parallelisable and cache friendly. It takes
> > > advantage of RCU to perform lookups without locking.
> > >
> > > Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
> > > ---
> > >
> > >  .../staging/unisys/visorhba/visorhba_main.c   | 107 +++++++-----------
> > >  1 file changed, 44 insertions(+), 63 deletions(-)
> > >
> > > diff --git a/drivers/staging/unisys/visorhba/visorhba_main.c
> > > b/drivers/staging/unisys/visorhba/visorhba_main.c index
> 4455d26f7c96..851e60ab0c46
> > > 100644
> > > --- a/drivers/staging/unisys/visorhba/visorhba_main.c
> > > +++ b/drivers/staging/unisys/visorhba/visorhba_main.c
> > > @@ -6,10 +6,10 @@
> > >
> > >  #include <linux/debugfs.h>
> > >  #include <linux/kthread.h>
> > >
> > > -#include <linux/idr.h>
> > >
> > >  #include <linux/module.h>
> > >  #include <linux/seq_file.h>
> > >  #include <linux/visorbus.h>
> > >
> > > +#include <linux/xarray.h>
> > >
> > >  #include <scsi/scsi.h>
> > >  #include <scsi/scsi_host.h>
> > >  #include <scsi/scsi_cmnd.h>
> > >
> > > @@ -23,6 +23,8 @@
> > >
> > >  #define MAX_PENDING_REQUESTS (MIN_NUMSIGNALS * 2)
> > >  #define VISORHBA_ERROR_COUNT 30
> > >
> > > +static DEFINE_XARRAY_ALLOC(xa_dtstr);
> > > +
> > >
> > >  static struct dentry *visorhba_debugfs_dir;
> > >
> > >  /* GUIDS for HBA channel type supported by this driver */
> > >
> > > @@ -78,12 +80,6 @@ struct visorhba_devdata {
> > >
> > >  	unsigned int max_buff_len;
> > >  	int devnum;
> > >  	struct uiscmdrsp *cmdrsp;
> > >
> > > -	/*
> > > -	 * allows us to pass int handles back-and-forth between us and
> > > -	 * iovm, instead of raw pointers
> > > -	 */
> > > -	struct idr idr;
> > > -
> > >
> > >  	struct dentry *debugfs_dir;
> > >  	struct dentry *debugfs_info;
> > >
> > >  };
> > >
> > > @@ -183,32 +179,16 @@ static struct uiscmdrsp
> *get_scsipending_cmdrsp(struct
> > > visorhba_devdata *ddata,>
> > >  }
> > >
> > >  /*
> > >
> > > - * simple_idr_get - Associate a provided pointer with an int value
> > > - *		    1 <= value <= INT_MAX, and return this int value;
> > > - *		    the pointer value can be obtained later by passing
> > > - *		    this int value to idr_find()
> > > - * @idrtable: The data object maintaining the pointer<-->int mappings
> > > - * @p:	      The pointer value to be remembered
> > > - * @lock:     A spinlock used when exclusive access to idrtable is needed
> > > - *
> > > - * Return: The id number mapped to pointer 'p', 0 on failure
> > > + * simple_xa_dtstr_get - Store a pointer to xa_dtstr xarray
> > > + * @id: Pointer to ID
> > > + * @entry: New entry
> > >
> > >   */
> > >
> > > -static unsigned int simple_idr_get(struct idr *idrtable, void *p,
> > > -				   spinlock_t *lock)
> > > +static int simple_xa_dtstr_get(u32 *id, void *entry)
> >
> > What are you trying to really "get" here?  We shouldn't name the
> > function based on the data type being used.  All we want is some sort of
> > "token" or hash or something else?  It's hard to tell...
> >
> Sorry, I am so lazy that I just substituted the _idr_ in the old name with
> _xa_dtstr_. Perhaps simple_entry_get() would be better. it deserves a v2.
> >
> > >  {
> > >
> > > -	int id;
> > > -	unsigned long flags;
> > > +	int ret = xa_alloc_irq(&xa_dtstr, id, entry, xa_limit_32b,
> GFP_NOWAIT);
> > > +	/* TODO: check for and manage errors */
> >
> > That's a nice TODO, which means we really should not be considering this
> > patch to be merged, right?
> >
> Right, lazy again :)
>
> The fact is that I was just interested in conversion from IDR to XArray
> because this would be the main subject of the project I applied for the DRM
> subsystem. Therefore, where I didn't find proper error checking and management
> in the old code, I simply wrote some TODO.
>
> I suppose that some more knowledge of both Linux device drivers programming
> and of that specific driver is needed to do proper management of errors in
> order to unwind what is already done by the code and leave everything in a
> consistent state. I'd left that work to Unisys developers, if you don't mind.
> I'd prefer to simply remove those TODO from where I placed them. I hope that
> you agree with me.

I don't know the details of this code, but normally the code is written so
that it is only what is done in the current function that has to be
unwound.  Perhaps it is possible to find what to do by looking at similar
code in other drivers.  It is better to do the whole thing than to leave
the code partly done.

julia

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Matthew Wilcox]

On Mon, Apr 26, 2021 at 11:50:15AM +0200, Fabio M. De Francesco wrote:
>  #define VISORHBA_ERROR_COUNT 30
>  
> +static DEFINE_XARRAY_ALLOC(xa_dtstr);
> +
>  static struct dentry *visorhba_debugfs_dir;
>  
>  /* GUIDS for HBA channel type supported by this driver */
> @@ -78,12 +80,6 @@ struct visorhba_devdata {
>  	unsigned int max_buff_len;
>  	int devnum;
>  	struct uiscmdrsp *cmdrsp;
> -	/*
> -	 * allows us to pass int handles back-and-forth between us and
> -	 * iovm, instead of raw pointers
> -	 */
> -	struct idr idr;
> -

Why did you change the driver from having one namespace per HBA to having
a global namespace?

>  /*
> - * simple_idr_get - Associate a provided pointer with an int value
> - *		    1 <= value <= INT_MAX, and return this int value;
> - *		    the pointer value can be obtained later by passing
> - *		    this int value to idr_find()
> - * @idrtable: The data object maintaining the pointer<-->int mappings
> - * @p:	      The pointer value to be remembered
> - * @lock:     A spinlock used when exclusive access to idrtable is needed
> - *
> - * Return: The id number mapped to pointer 'p', 0 on failure
> + * simple_xa_dtstr_get - Store a pointer to xa_dtstr xarray
> + * @id: Pointer to ID
> + * @entry: New entry
>   */
> -static unsigned int simple_idr_get(struct idr *idrtable, void *p,
> -				   spinlock_t *lock)
> +static int simple_xa_dtstr_get(u32 *id, void *entry)
>  {
> -	int id;
> -	unsigned long flags;
> +	int ret = xa_alloc_irq(&xa_dtstr, id, entry, xa_limit_32b, GFP_NOWAIT);
> +	/* TODO: check for and manage errors */
>  
> -	idr_preload(GFP_KERNEL);
> -	spin_lock_irqsave(lock, flags);
> -	id = idr_alloc(idrtable, p, 1, INT_MAX, GFP_NOWAIT);
> -	spin_unlock_irqrestore(lock, flags);
> -	idr_preload_end();
> -	/* failure */
> -	if (id < 0)
> -		return 0;
> -	/* idr_alloc() guarantees > 0 */
> -	return (unsigned int)(id);
> +	return ret;
>  }

I would think that this wrapper should probably be removed.  It'll almost
certainly be better to inline the call to xa_alloc_irq() at the call
sites.

You've also changed the behaviour; it used to allocate an id between 1
and INT_MAX; now it allocates an ID between 0 and UINT_MAX.  Maybe that's
safe, but you need to argue for it in the changelog.

And it shouldn't be using GFP_NOWAIT, but GFP_KERNEL, like the IDR code
used to do.

>  /*
> @@ -216,22 +196,25 @@ static unsigned int simple_idr_get(struct idr *idrtable, void *p,
>   *				completion processing logic for a taskmgmt
>   *				cmd will be able to find who to wake up
>   *				and where to stash the result
> - * @idrtable: The data object maintaining the pointer<-->int mappings
> - * @lock:     A spinlock used when exclusive access to idrtable is needed
> + * @xa_dtstr: The data object maintaining the pointer<-->int mappings

You added this in the documentation, but not in the function ...

>   * @cmdrsp:   Response from the IOVM
>   * @event:    The event handle to associate with an id
>   * @result:   The location to place the result of the event handle into
>   */
> -static void setup_scsitaskmgmt_handles(struct idr *idrtable, spinlock_t *lock,
> -				       struct uiscmdrsp *cmdrsp,
> -				       wait_queue_head_t *event, int *result)
> +static void setup_scsitaskmgmt_handles(struct uiscmdrsp *cmdrsp,
> +				       wait_queue_head_t *event, u32 *result)
>  {
> -	/* specify the event that has to be triggered when this */
> -	/* cmd is complete */
> -	cmdrsp->scsitaskmgmt.notify_handle =
> -		simple_idr_get(idrtable, event, lock);
> -	cmdrsp->scsitaskmgmt.notifyresult_handle =
> -		simple_idr_get(idrtable, result, lock);
> +	void *entry;
> +	int ret;
> +
> +	/* specify the event that has to be triggered when this cmd is complete */
> +	entry = &cmdrsp->scsitaskmgmt.notify_handle;
> +	ret = simple_xa_dtstr_get(result, entry);
> +	/* TODO: Check for and manage errors */

The prior code assigned the ID for 'event' to scsitaskmgmt.notify_handle.
Now, you're allocating an ID for the address of scsitaskmgmt.notify_handle
to 'result'.  That's clearly not right.

> +	entry = &cmdrsp->scsitaskmgmt.notifyresult_handle;
> +	ret = simple_xa_dtstr_get(result, entry);
> +	/* TODO: Check for and manage errors */
>  }
>  
>  /*
> @@ -240,13 +223,17 @@ static void setup_scsitaskmgmt_handles(struct idr *idrtable, spinlock_t *lock,
>   * @idrtable: The data object maintaining the pointer<-->int mappings
>   * @cmdrsp:   Response from the IOVM
>   */
> -static void cleanup_scsitaskmgmt_handles(struct idr *idrtable,
> -					 struct uiscmdrsp *cmdrsp)
> +static void cleanup_scsitaskmgmt_handles(struct uiscmdrsp_scsitaskmgmt *scsitaskmgmt)
>  {
> -	if (cmdrsp->scsitaskmgmt.notify_handle)
> -		idr_remove(idrtable, cmdrsp->scsitaskmgmt.notify_handle);
> -	if (cmdrsp->scsitaskmgmt.notifyresult_handle)
> -		idr_remove(idrtable, cmdrsp->scsitaskmgmt.notifyresult_handle);
> +	struct uiscmdrsp *cmdrsp;
> +	unsigned long index;
> +
> +	xa_for_each(&xa_dtstr, index, cmdrsp) {
> +		if (&cmdrsp->scsitaskmgmt != scsitaskmgmt)
> +			continue;
> +		xa_erase(&xa_dtstr, index);
> +		kfree(cmdrsp);
> +	}

I suspect this is part of the same confusion, but the old code passed in an
ID that we just looked up & removed.  You've changed that to iterate over
all the entries and remove the ones that match ...

> @@ -1096,7 +1077,7 @@ static void visorhba_remove(struct visor_device *dev)
>  	scsi_remove_host(scsihost);
>  	scsi_host_put(scsihost);
>  
> -	idr_destroy(&devdata->idr);
> +	xa_destroy(&xa_dtstr);
>  
>  	dev_set_drvdata(&dev->device, NULL);
>  	debugfs_remove(devdata->debugfs_info);

What happens if you have two HBAs in the system, one is active and you
remove the other one?

More generally, the IDR required you call idr_destroy() to avoid leaking
preallocated memory.  I changed that, but there are still many drivers
that have unnecessary calls to idr_destroy().  It's good form to just
delete them and not turn them into calls to xa_destroy().

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Fabio M. De Francesco]

On Monday, April 26, 2021 1:49:02 PM CEST Matthew Wilcox wrote:
> On Mon, Apr 26, 2021 at 11:50:15AM +0200, Fabio M. De Francesco wrote:
> >  #define VISORHBA_ERROR_COUNT 30
> > 
> > +static DEFINE_XARRAY_ALLOC(xa_dtstr);
> > +
> > 
> >  static struct dentry *visorhba_debugfs_dir;
> >  
> >  /* GUIDS for HBA channel type supported by this driver */
> > 
> > @@ -78,12 +80,6 @@ struct visorhba_devdata {
> > 
> >  	unsigned int max_buff_len;
> >  	int devnum;
> >  	struct uiscmdrsp *cmdrsp;
> > 
> > -	/*
> > -	 * allows us to pass int handles back-and-forth between us and
> > -	 * iovm, instead of raw pointers
> > -	 */
> > -	struct idr idr;
> > -
> 
> Why did you change the driver from having one namespace per HBA to having
> a global namespace?
> 
I made that change simply because I didn't catch that there could be more than 
just one HBA. 
> >  /*
> > 
> > - * simple_idr_get - Associate a provided pointer with an int value
> > - *		    1 <= value <= INT_MAX, and return this int value;
> > - *		    the pointer value can be obtained later by passing
> > - *		    this int value to idr_find()
> > - * @idrtable: The data object maintaining the pointer<-->int mappings
> > - * @p:	      The pointer value to be remembered
> > - * @lock:     A spinlock used when exclusive access to idrtable is needed
> > - *
> > - * Return: The id number mapped to pointer 'p', 0 on failure
> > + * simple_xa_dtstr_get - Store a pointer to xa_dtstr xarray
> > + * @id: Pointer to ID
> > + * @entry: New entry
> > 
> >   */
> > 
> > -static unsigned int simple_idr_get(struct idr *idrtable, void *p,
> > -				   spinlock_t *lock)
> > +static int simple_xa_dtstr_get(u32 *id, void *entry)
> > 
> >  {
> > 
> > -	int id;
> > -	unsigned long flags;
> > +	int ret = xa_alloc_irq(&xa_dtstr, id, entry, xa_limit_32b, 
GFP_NOWAIT);
> > +	/* TODO: check for and manage errors */
> > 
> > -	idr_preload(GFP_KERNEL);
> > -	spin_lock_irqsave(lock, flags);
> > -	id = idr_alloc(idrtable, p, 1, INT_MAX, GFP_NOWAIT);
> > -	spin_unlock_irqrestore(lock, flags);
> > -	idr_preload_end();
> > -	/* failure */
> > -	if (id < 0)
> > -		return 0;
> > -	/* idr_alloc() guarantees > 0 */
> > -	return (unsigned int)(id);
> > +	return ret;
> > 
> >  }
> 
> I would think that this wrapper should probably be removed.  It'll almost
> certainly be better to inline the call to xa_alloc_irq() at the call
> sites.
>
I think I got it now.
> 
> You've also changed the behaviour; it used to allocate an id between 1
> and INT_MAX; now it allocates an ID between 0 and UINT_MAX.  Maybe that's
> safe, but you need to argue for it in the changelog.
>
Same as above..
>
> And it shouldn't be using GFP_NOWAIT, but GFP_KERNEL, like the IDR code
> used to do.
>
I'm not sure to understand why idr_preload() uses GFP_KERNEL and instead  
idr_alloc() uses GFP_NOWAIT. I'd better read anew the documentation of the 
above-mentioned functions  
> 
> >  /*
> > 
> > @@ -216,22 +196,25 @@ static unsigned int simple_idr_get(struct idr 
*idrtable, void
> > *p,
> > 
> >   *				completion processing logic for 
a taskmgmt
> >   *				cmd will be able to find who to 
wake up
> >   *				and where to stash the result
> > 
> > - * @idrtable: The data object maintaining the pointer<-->int mappings
> > - * @lock:     A spinlock used when exclusive access to idrtable is needed
> > + * @xa_dtstr: The data object maintaining the pointer<-->int mappings
> 
> You added this in the documentation, but not in the function ...
>
It happened when I wrongly decided to have a global namespace (as I explained 
above).
> 
> >   * @cmdrsp:   Response from the IOVM
> >   * @event:    The event handle to associate with an id
> >   * @result:   The location to place the result of the event handle into
> >   */
> > 
> > -static void setup_scsitaskmgmt_handles(struct idr *idrtable, spinlock_t 
*lock,
> > -				       struct uiscmdrsp *cmdrsp,
> > -				       wait_queue_head_t *event, 
int *result)
> > +static void setup_scsitaskmgmt_handles(struct uiscmdrsp *cmdrsp,
> > +				       wait_queue_head_t *event, 
u32 *result)
> > 
> >  {
> > 
> > -	/* specify the event that has to be triggered when this */
> > -	/* cmd is complete */
> > -	cmdrsp->scsitaskmgmt.notify_handle =
> > -		simple_idr_get(idrtable, event, lock);
> > -	cmdrsp->scsitaskmgmt.notifyresult_handle =
> > -		simple_idr_get(idrtable, result, lock);
> > +	void *entry;
> > +	int ret;
> > +
> > +	/* specify the event that has to be triggered when this cmd is 
complete */
> > +	entry = &cmdrsp->scsitaskmgmt.notify_handle;
> > +	ret = simple_xa_dtstr_get(result, entry);
> > +	/* TODO: Check for and manage errors */
> 
> The prior code assigned the ID for 'event' to scsitaskmgmt.notify_handle.
> Now, you're allocating an ID for the address of scsitaskmgmt.notify_handle
> to 'result'.  That's clearly not right.
> 
That's due to my fault in understanding the semantics of those functions.
>
> > +	entry = &cmdrsp->scsitaskmgmt.notifyresult_handle;
> > +	ret = simple_xa_dtstr_get(result, entry);
> > +	/* TODO: Check for and manage errors */
> > 
> >  }
> >  
> >  /*
> > 
> > @@ -240,13 +223,17 @@ static void setup_scsitaskmgmt_handles(struct idr 
*idrtable,
> > spinlock_t *lock,> 
> >   * @idrtable: The data object maintaining the pointer<-->int mappings
> >   * @cmdrsp:   Response from the IOVM
> >   */
> > 
> > -static void cleanup_scsitaskmgmt_handles(struct idr *idrtable,
> > -					 struct uiscmdrsp 
*cmdrsp)
> > +static void cleanup_scsitaskmgmt_handles(struct uiscmdrsp_scsitaskmgmt 
*scsitaskmgmt)
> > 
> >  {
> > 
> > -	if (cmdrsp->scsitaskmgmt.notify_handle)
> > -		idr_remove(idrtable, cmdrsp-
>scsitaskmgmt.notify_handle);
> > -	if (cmdrsp->scsitaskmgmt.notifyresult_handle)
> > -		idr_remove(idrtable, cmdrsp-
>scsitaskmgmt.notifyresult_handle);
> > +	struct uiscmdrsp *cmdrsp;
> > +	unsigned long index;
> > +
> > +	xa_for_each(&xa_dtstr, index, cmdrsp) {
> > +		if (&cmdrsp->scsitaskmgmt != scsitaskmgmt)
> > +			continue;
> > +		xa_erase(&xa_dtstr, index);
> > +		kfree(cmdrsp);
> > +	}
> 
> I suspect this is part of the same confusion, but the old code passed in an
> ID that we just looked up & removed.  You've changed that to iterate over
> all the entries and remove the ones that match ...
>
I'm not sure if I understand it, however I suppose that you mean that there is 
no need to iterate over all the entries to find the one that matches for the 
purpose of erasing it. I'll look at this issue anew and find out the right way 
for the removals.
> 
> > @@ -1096,7 +1077,7 @@ static void visorhba_remove(struct visor_device 
*dev)
> > 
> >  	scsi_remove_host(scsihost);
> >  	scsi_host_put(scsihost);
> > 
> > -	idr_destroy(&devdata->idr);
> > +	xa_destroy(&xa_dtstr);
> > 
> >  	dev_set_drvdata(&dev->device, NULL);
> >  	debugfs_remove(devdata->debugfs_info);
> 
> What happens if you have two HBAs in the system, one is active and you
> remove the other one?
>
This will not be anymore a problem when I'll restore the use of one namespace 
per HBA. It's correct?
>
> More generally, the IDR required you call idr_destroy() to avoid leaking
> preallocated memory.  I changed that, but there are still many drivers
> that have unnecessary calls to idr_destroy().  It's good form to just
> delete them and not turn them into calls to xa_destroy().
>
This one is a bit obscure to me. I have to look into it more carefully. Maybe 
I'll ask for some further help.

Thanks for your review,

Fabio 

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Matthew Wilcox]

On Mon, Apr 26, 2021 at 03:14:42PM +0200, Fabio M. De Francesco wrote:
> > > -	int id;
> > > -	unsigned long flags;
> > > 
> > > -	idr_preload(GFP_KERNEL);
> > > -	spin_lock_irqsave(lock, flags);
> > > -	id = idr_alloc(idrtable, p, 1, INT_MAX, GFP_NOWAIT);
> > > -	spin_unlock_irqrestore(lock, flags);
> > > -	idr_preload_end();
> > > -	/* failure */
> > > -	if (id < 0)
> > > -		return 0;
> > > -	/* idr_alloc() guarantees > 0 */
> > > -	return (unsigned int)(id);
> >
> > And it shouldn't be using GFP_NOWAIT, but GFP_KERNEL, like the IDR code
> > used to do.
> I'm not sure to understand why idr_preload() uses GFP_KERNEL and instead  
> idr_alloc() uses GFP_NOWAIT. I'd better read anew the documentation of the 
> above-mentioned functions  

If you're holding a spinlock, you can't do a GFP_KERNEL allocation,
because it can sleep, and sleeping while holding a spinlock isn't allowed.

The IDR and radix tree have an approach where you first preallocate
memory using GFP_KERNEL and then use GFP_NOWAIT or GFP_ATOMIC after
you've taken the spinlock.  XArray doesn't do that; it takes the spinlock
and does a GFP_NOWAIT allocation.  If it fails, it drops the spinlock,
allocates the memory using GFP_KERNEL, and retries.

> This will not be anymore a problem when I'll restore the use of one namespace 
> per HBA. It's correct?

true ...

> > More generally, the IDR required you call idr_destroy() to avoid leaking
> > preallocated memory.  I changed that, but there are still many drivers
> > that have unnecessary calls to idr_destroy().  It's good form to just
> > delete them and not turn them into calls to xa_destroy().
> >
> This one is a bit obscure to me. I have to look into it more carefully. Maybe 
> I'll ask for some further help.

The IDR used to have a per-idr preallocation, so you had to destroy it
in order to make sure they were freed.  I got rid of that about five
years ago because most IDR users weren't calling idr_destroy().

Re: [Outreachy kernel] [RFC PATCH] staging: unisys: visorhba: Convert module from IDR to XArray

[Fabio M. De Francesco]

On Monday, April 26, 2021 3:29:28 PM CEST Matthew Wilcox wrote:
> On Mon, Apr 26, 2021 at 03:14:42PM +0200, Fabio M. De Francesco wrote:
> > > > -	int id;
> > > > -	unsigned long flags;
> > > > 
> > > > -	idr_preload(GFP_KERNEL);
> > > > -	spin_lock_irqsave(lock, flags);
> > > > -	id = idr_alloc(idrtable, p, 1, INT_MAX, GFP_NOWAIT);
> > > > -	spin_unlock_irqrestore(lock, flags);
> > > > -	idr_preload_end();
> > > > -	/* failure */
> > > > -	if (id < 0)
> > > > -		return 0;
> > > > -	/* idr_alloc() guarantees > 0 */
> > > > -	return (unsigned int)(id);
> > > 
> > > And it shouldn't be using GFP_NOWAIT, but GFP_KERNEL, like the IDR code
> > > used to do.
> > 
> > I'm not sure to understand why idr_preload() uses GFP_KERNEL and instead
> > idr_alloc() uses GFP_NOWAIT. I'd better read anew the documentation of the
> > above-mentioned functions
> 
> If you're holding a spinlock, you can't do a GFP_KERNEL allocation,
> because it can sleep, and sleeping while holding a spinlock isn't allowed.
>
I know that since a long time... that is last week, day more day less  :) 

I've just started to read R.Love's LKD 3rd ed. I don't have enough time to 
read it at the moment, however I skipped a few chapters and read "Kernel 
synchronization methods" and "Memory management".
> 
> The IDR and radix tree have an approach where you first preallocate
> memory using GFP_KERNEL and then use GFP_NOWAIT or GFP_ATOMIC after
> you've taken the spinlock.  XArray doesn't do that; it takes the spinlock
> and does a GFP_NOWAIT allocation.  If it fails, it drops the spinlock,
> allocates the memory using GFP_KERNEL, and retries.
>
This is something one cannot find in Love's book, unless I overlooked that.
> 
> > This will not be anymore a problem when I'll restore the use of one 
namespace
> > per HBA. It's correct?
> 
> true ...
> 
> > > More generally, the IDR required you call idr_destroy() to avoid leaking
> > > preallocated memory.  I changed that, but there are still many drivers
> > > that have unnecessary calls to idr_destroy().  It's good form to just
> > > delete them and not turn them into calls to xa_destroy().
> > 
> > This one is a bit obscure to me. I have to look into it more carefully. 
Maybe
> > I'll ask for some further help.
> 
> The IDR used to have a per-idr preallocation, so you had to destroy it
> in order to make sure they were freed.  I got rid of that about five
> years ago because most IDR users weren't calling idr_destroy().
>
OK, I think I got it.
>
Thanks again,

Fabio