[PATCH 00/38] Convert networking to use the XArray

[PATCH 00/38] Convert networking to use the XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Hello good networking folks,

I am attempting to convert all IDR and radix tree users over to the
XArray API so we can remove the radix tree code from the kernel.  This
process is already underway, and you can see all the conversions in a
git tree [1].  

The set of conversions I am submitting to you today are only compile
tested.  I would appreciate it if those who are responsible for each
module could take on the job of making sure I didn't break anything.
Review is, of course, also welcome.

The primary difference between the IDR/radix tree and XArray APIs is that
the XArray embeds a spinlock.  This enables the ability to defragment
the slabs which contain XArray nodes, and for most users results in an
easier-to-use API.

There are a lot of smaller tweaks in the XArray API compared to the radix
tree or IDR APIs.  For example, there is no more preallocation of memory;
instead the XArray will drop the lock if needed to allocate memory.

Ideally, you'd include the patch for your module into your next pull
request to Dave and they'd land upstream in 5.4.  These patches are
against current net-next.  If you'd like to change whitespace or comments
or so on, please just do that; this is your code and I've got a lot of
other patches I need to whip into shape.

[1] http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv
Some of these conversions are known to be buggy, so I would not recommend
actually running this tree.

Matthew Wilcox (Oracle) (38):
  mlx4: Convert cq_table->tree to XArray
  mlx4: Convert srq_table->tree to XArray
  mlx4: Convert qp_table_tree to XArray
  mlx5: Convert cq_table to XArray
  mlx5: Convert mlx5_qp_table to XArray
  mlx5: Convert counters_idr to XArray
  mlx5: Convert fpga IDRs to XArray
  nfp: Convert to XArray
  ath10k: Convert pending_tx to XArray
  ath10k: Convert mgmt_pending_tx IDR to XArray
  mt76: Convert token IDR to XArray
  mwifiex: Convert ack_status_frames to XArray
  ppp: Convert units_idr to XArray
  tap: Convert minor_idr to XArray
  nfp: Convert internal ports to XArray
  qrtr: Convert qrtr_nodes to XArray
  qrtr: Convert qrtr_ports to XArray
  rxrpc: Convert to XArray
  9p: Convert reqs IDR to XArray
  9p: Convert fids IDR to XArray
  9p: Move lock from client to trans_fd
  sctp: Convert sctp_assocs_id to XArray
  cls_api: Convert tcf_net to XArray
  cls_u32: Convert tc_u_common->handle_idr to XArray
  cls_u32: Convert tc_u_hnode->handle_idr to XArray
  cls_bpf: Convert handle_idr to XArray
  cls_bpf: Remove list of programs
  cls_bpf: Use XArray marks to accelerate re-offload
  cls_flower: Convert handle_idr to XArray
  cls_flower: Use XArray list of filters in fl_walk
  cls_flower: Use XArray marks instead of separate list
  cls_basic: Convert handle_idr to XArray
  act_api: Convert action_idr to XArray
  net_namespace: Convert netns_ids to XArray
  tipc: Convert conn_idr to XArray
  netlink: Convert genl_fam_idr to XArray
  mac80211: Convert ack_status_frames to XArray
  mac80211: Convert function_inst_ids to XArray

 drivers/infiniband/hw/mlx4/cq.c               |   2 +-
 drivers/net/ethernet/mellanox/mlx4/cq.c       |  30 ++---
 drivers/net/ethernet/mellanox/mlx4/mlx4.h     |   9 +-
 drivers/net/ethernet/mellanox/mlx4/qp.c       |  37 ++---
 drivers/net/ethernet/mellanox/mlx4/srq.c      |  33 ++---
 drivers/net/ethernet/mellanox/mlx5/core/eq.c  |  27 +---
 .../ethernet/mellanox/mlx5/core/fpga/tls.c    |  54 +++-----
 .../ethernet/mellanox/mlx5/core/fpga/tls.h    |   6 +-
 .../ethernet/mellanox/mlx5/core/fs_counters.c |  31 ++---
 .../net/ethernet/mellanox/mlx5/core/lib/eq.h  |   7 +-
 drivers/net/ethernet/mellanox/mlx5/core/qp.c  |  38 ++----
 drivers/net/ethernet/netronome/nfp/abm/main.c |   4 +-
 drivers/net/ethernet/netronome/nfp/abm/main.h |   4 +-
 .../net/ethernet/netronome/nfp/abm/qdisc.c    |  33 ++---
 .../net/ethernet/netronome/nfp/flower/main.c  |  44 +++---
 .../net/ethernet/netronome/nfp/flower/main.h  |  12 +-
 drivers/net/ppp/ppp_generic.c                 |  73 +++-------
 drivers/net/tap.c                             |  32 ++---
 drivers/net/wireless/ath/ath10k/core.h        |   2 +-
 drivers/net/wireless/ath/ath10k/htt.h         |   2 +-
 drivers/net/wireless/ath/ath10k/htt_tx.c      |  31 ++---
 drivers/net/wireless/ath/ath10k/mac.c         |   4 +-
 drivers/net/wireless/ath/ath10k/txrx.c        |   2 +-
 drivers/net/wireless/ath/ath10k/wmi-tlv.c     |   8 +-
 drivers/net/wireless/ath/ath10k/wmi.c         |  43 +++---
 drivers/net/wireless/marvell/mwifiex/init.c   |   4 +-
 drivers/net/wireless/marvell/mwifiex/main.c   |  10 +-
 drivers/net/wireless/marvell/mwifiex/main.h   |   4 +-
 drivers/net/wireless/marvell/mwifiex/txrx.c   |   4 +-
 drivers/net/wireless/marvell/mwifiex/wmm.c    |  15 +--
 .../net/wireless/mediatek/mt76/mt7615/init.c  |  11 +-
 .../net/wireless/mediatek/mt76/mt7615/mac.c   |  24 ++--
 .../wireless/mediatek/mt76/mt7615/mt7615.h    |   4 +-
 include/linux/mlx4/device.h                   |   4 +-
 include/linux/mlx4/qp.h                       |   2 +-
 include/linux/mlx5/driver.h                   |  11 +-
 include/linux/mlx5/qp.h                       |   2 +-
 include/net/9p/client.h                       |  11 +-
 include/net/act_api.h                         |   6 +-
 include/net/net_namespace.h                   |   2 +-
 include/net/sctp/sctp.h                       |   5 +-
 net/9p/client.c                               |  65 ++++-----
 net/9p/trans_fd.c                             |  37 ++---
 net/9p/trans_rdma.c                           |   1 -
 net/9p/trans_virtio.c                         |   1 -
 net/core/net_namespace.c                      |  65 ++++-----
 net/mac80211/cfg.c                            |  70 ++++------
 net/mac80211/ieee80211_i.h                    |  12 +-
 net/mac80211/iface.c                          |  16 +--
 net/mac80211/main.c                           |  20 ++-
 net/mac80211/status.c                         |   6 +-
 net/mac80211/tx.c                             |  16 +--
 net/mac80211/util.c                           |  30 +----
 net/netlink/genetlink.c                       |  46 +++----
 net/qrtr/qrtr.c                               |  66 ++++-----
 net/rxrpc/af_rxrpc.c                          |   2 +-
 net/rxrpc/ar-internal.h                       |   3 +-
 net/rxrpc/conn_client.c                       |  49 +++----
 net/rxrpc/conn_object.c                       |   2 +-
 net/sched/act_api.c                           | 127 +++++++-----------
 net/sched/cls_api.c                           |  27 +---
 net/sched/cls_basic.c                         |  56 +++-----
 net/sched/cls_bpf.c                           |  74 +++++-----
 net/sched/cls_flower.c                        | 114 ++++++----------
 net/sched/cls_u32.c                           |  63 ++++-----
 net/sctp/associola.c                          |  34 ++---
 net/sctp/protocol.c                           |   6 -
 net/sctp/sm_make_chunk.c                      |   2 +-
 net/sctp/socket.c                             |   6 +-
 net/tipc/topsrv.c                             |  49 ++-----
 70 files changed, 650 insertions(+), 1102 deletions(-)

-- 
2.23.0.rc1

[PATCH 01/38] mlx4: Convert cq_table->tree to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Remove the custom spinlock as the XArray handles its own locking.
It might also be possible to remove the bitmap and use the XArray
in allocating mode.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/ethernet/mellanox/mlx4/cq.c   | 30 +++++++----------------
 drivers/net/ethernet/mellanox/mlx4/mlx4.h |  3 +--
 2 files changed, 10 insertions(+), 23 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx4/cq.c b/drivers/net/ethernet/mellanox/mlx4/cq.c
index 65f8a4b6ed0c..d0be77e70065 100644
--- a/drivers/net/ethernet/mellanox/mlx4/cq.c
+++ b/drivers/net/ethernet/mellanox/mlx4/cq.c
@@ -105,10 +105,8 @@ void mlx4_cq_completion(struct mlx4_dev *dev, u32 cqn)
 {
 	struct mlx4_cq *cq;
 
-	rcu_read_lock();
-	cq = radix_tree_lookup(&mlx4_priv(dev)->cq_table.tree,
+	cq = xa_load(&mlx4_priv(dev)->cq_table.array,
 			       cqn & (dev->caps.num_cqs - 1));
-	rcu_read_unlock();
 
 	if (!cq) {
 		mlx4_dbg(dev, "Completion event for bogus CQ %08x\n", cqn);
@@ -128,9 +126,7 @@ void mlx4_cq_event(struct mlx4_dev *dev, u32 cqn, int event_type)
 	struct mlx4_cq_table *cq_table = &mlx4_priv(dev)->cq_table;
 	struct mlx4_cq *cq;
 
-	rcu_read_lock();
-	cq = radix_tree_lookup(&cq_table->tree, cqn & (dev->caps.num_cqs - 1));
-	rcu_read_unlock();
+	cq = xa_load(&cq_table->array, cqn & (dev->caps.num_cqs - 1));
 
 	if (!cq) {
 		mlx4_dbg(dev, "Async event for bogus CQ %08x\n", cqn);
@@ -360,16 +356,14 @@ int mlx4_cq_alloc(struct mlx4_dev *dev, int nent,
 	if (err)
 		return err;
 
-	spin_lock(&cq_table->lock);
-	err = radix_tree_insert(&cq_table->tree, cq->cqn, cq);
-	spin_unlock(&cq_table->lock);
+	err = xa_err(xa_store(&cq_table->array, cq->cqn, cq, GFP_KERNEL));
 	if (err)
 		goto err_icm;
 
 	mailbox = mlx4_alloc_cmd_mailbox(dev);
 	if (IS_ERR(mailbox)) {
 		err = PTR_ERR(mailbox);
-		goto err_radix;
+		goto err_xa;
 	}
 
 	cq_context = mailbox->buf;
@@ -404,7 +398,7 @@ int mlx4_cq_alloc(struct mlx4_dev *dev, int nent,
 
 	mlx4_free_cmd_mailbox(dev, mailbox);
 	if (err)
-		goto err_radix;
+		goto err_xa;
 
 	cq->cons_index = 0;
 	cq->arm_sn     = 1;
@@ -420,10 +414,8 @@ int mlx4_cq_alloc(struct mlx4_dev *dev, int nent,
 	cq->irq = priv->eq_table.eq[MLX4_CQ_TO_EQ_VECTOR(vector)].irq;
 	return 0;
 
-err_radix:
-	spin_lock(&cq_table->lock);
-	radix_tree_delete(&cq_table->tree, cq->cqn);
-	spin_unlock(&cq_table->lock);
+err_xa:
+	xa_erase(&cq_table->array, cq->cqn);
 
 err_icm:
 	mlx4_cq_free_icm(dev, cq->cqn);
@@ -442,9 +434,7 @@ void mlx4_cq_free(struct mlx4_dev *dev, struct mlx4_cq *cq)
 	if (err)
 		mlx4_warn(dev, "HW2SW_CQ failed (%d) for CQN %06x\n", err, cq->cqn);
 
-	spin_lock(&cq_table->lock);
-	radix_tree_delete(&cq_table->tree, cq->cqn);
-	spin_unlock(&cq_table->lock);
+	xa_erase(&cq_table->array, cq->cqn);
 
 	synchronize_irq(priv->eq_table.eq[MLX4_CQ_TO_EQ_VECTOR(cq->vector)].irq);
 	if (priv->eq_table.eq[MLX4_CQ_TO_EQ_VECTOR(cq->vector)].irq !=
@@ -464,8 +454,7 @@ int mlx4_init_cq_table(struct mlx4_dev *dev)
 	struct mlx4_cq_table *cq_table = &mlx4_priv(dev)->cq_table;
 	int err;
 
-	spin_lock_init(&cq_table->lock);
-	INIT_RADIX_TREE(&cq_table->tree, GFP_ATOMIC);
+	xa_init(&cq_table->array);
 	if (mlx4_is_slave(dev))
 		return 0;
 
@@ -481,6 +470,5 @@ void mlx4_cleanup_cq_table(struct mlx4_dev *dev)
 {
 	if (mlx4_is_slave(dev))
 		return;
-	/* Nothing to do to clean up radix_tree */
 	mlx4_bitmap_cleanup(&mlx4_priv(dev)->cq_table.bitmap);
 }
diff --git a/drivers/net/ethernet/mellanox/mlx4/mlx4.h b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
index 23f1b5b512c2..a40a9a259adb 100644
--- a/drivers/net/ethernet/mellanox/mlx4/mlx4.h
+++ b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
@@ -678,8 +678,7 @@ struct mlx4_mr_table {
 
 struct mlx4_cq_table {
 	struct mlx4_bitmap	bitmap;
-	spinlock_t		lock;
-	struct radix_tree_root	tree;
+	struct xarray		array;
 	struct mlx4_icm_table	table;
 	struct mlx4_icm_table	cmpt_table;
 };
-- 
2.23.0.rc1

[PATCH 02/38] mlx4: Convert srq_table->tree to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Adjust the locking to not disable interrupts; this isn't needed as all
accesses are either writes from process context or reads protected
by the RCU lock.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/infiniband/hw/mlx4/cq.c           |  2 +-
 drivers/net/ethernet/mellanox/mlx4/mlx4.h |  3 +--
 drivers/net/ethernet/mellanox/mlx4/srq.c  | 33 +++++++----------------
 3 files changed, 11 insertions(+), 27 deletions(-)

diff --git a/drivers/infiniband/hw/mlx4/cq.c b/drivers/infiniband/hw/mlx4/cq.c
index a7d238d312f0..0d7709823b9f 100644
--- a/drivers/infiniband/hw/mlx4/cq.c
+++ b/drivers/infiniband/hw/mlx4/cq.c
@@ -728,7 +728,7 @@ static int mlx4_ib_poll_one(struct mlx4_ib_cq *cq,
 		u32 srq_num;
 		g_mlpath_rqpn = be32_to_cpu(cqe->g_mlpath_rqpn);
 		srq_num       = g_mlpath_rqpn & 0xffffff;
-		/* SRQ is also in the radix tree */
+		/* SRQ is also in the xarray */
 		msrq = mlx4_srq_lookup(to_mdev(cq->ibcq.device)->dev,
 				       srq_num);
 	}
diff --git a/drivers/net/ethernet/mellanox/mlx4/mlx4.h b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
index a40a9a259adb..b6fe22bee9f4 100644
--- a/drivers/net/ethernet/mellanox/mlx4/mlx4.h
+++ b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
@@ -698,8 +698,7 @@ struct mlx4_eq_table {
 
 struct mlx4_srq_table {
 	struct mlx4_bitmap	bitmap;
-	spinlock_t		lock;
-	struct radix_tree_root	tree;
+	struct xarray		array;
 	struct mlx4_icm_table	table;
 	struct mlx4_icm_table	cmpt_table;
 };
diff --git a/drivers/net/ethernet/mellanox/mlx4/srq.c b/drivers/net/ethernet/mellanox/mlx4/srq.c
index cbe4d9746ddf..b7c4007fbc85 100644
--- a/drivers/net/ethernet/mellanox/mlx4/srq.c
+++ b/drivers/net/ethernet/mellanox/mlx4/srq.c
@@ -45,9 +45,7 @@ void mlx4_srq_event(struct mlx4_dev *dev, u32 srqn, int event_type)
 	struct mlx4_srq_table *srq_table = &mlx4_priv(dev)->srq_table;
 	struct mlx4_srq *srq;
 
-	rcu_read_lock();
-	srq = radix_tree_lookup(&srq_table->tree, srqn & (dev->caps.num_srqs - 1));
-	rcu_read_unlock();
+	srq = xa_load(&srq_table->array, srqn & (dev->caps.num_srqs - 1));
 	if (srq)
 		refcount_inc(&srq->refcount);
 	else {
@@ -172,16 +170,14 @@ int mlx4_srq_alloc(struct mlx4_dev *dev, u32 pdn, u32 cqn, u16 xrcd,
 	if (err)
 		return err;
 
-	spin_lock_irq(&srq_table->lock);
-	err = radix_tree_insert(&srq_table->tree, srq->srqn, srq);
-	spin_unlock_irq(&srq_table->lock);
+	err = xa_err(xa_store(&srq_table->array, srq->srqn, srq, GFP_KERNEL));
 	if (err)
 		goto err_icm;
 
 	mailbox = mlx4_alloc_cmd_mailbox(dev);
 	if (IS_ERR(mailbox)) {
 		err = PTR_ERR(mailbox);
-		goto err_radix;
+		goto err_xa;
 	}
 
 	srq_context = mailbox->buf;
@@ -201,17 +197,15 @@ int mlx4_srq_alloc(struct mlx4_dev *dev, u32 pdn, u32 cqn, u16 xrcd,
 	err = mlx4_SW2HW_SRQ(dev, mailbox, srq->srqn);
 	mlx4_free_cmd_mailbox(dev, mailbox);
 	if (err)
-		goto err_radix;
+		goto err_xa;
 
 	refcount_set(&srq->refcount, 1);
 	init_completion(&srq->free);
 
 	return 0;
 
-err_radix:
-	spin_lock_irq(&srq_table->lock);
-	radix_tree_delete(&srq_table->tree, srq->srqn);
-	spin_unlock_irq(&srq_table->lock);
+err_xa:
+	xa_erase(&srq_table->array, srq->srqn);
 
 err_icm:
 	mlx4_srq_free_icm(dev, srq->srqn);
@@ -228,9 +222,7 @@ void mlx4_srq_free(struct mlx4_dev *dev, struct mlx4_srq *srq)
 	if (err)
 		mlx4_warn(dev, "HW2SW_SRQ failed (%d) for SRQN %06x\n", err, srq->srqn);
 
-	spin_lock_irq(&srq_table->lock);
-	radix_tree_delete(&srq_table->tree, srq->srqn);
-	spin_unlock_irq(&srq_table->lock);
+	xa_erase(&srq_table->array, srq->srqn);
 
 	if (refcount_dec_and_test(&srq->refcount))
 		complete(&srq->free);
@@ -274,8 +266,7 @@ int mlx4_init_srq_table(struct mlx4_dev *dev)
 	struct mlx4_srq_table *srq_table = &mlx4_priv(dev)->srq_table;
 	int err;
 
-	spin_lock_init(&srq_table->lock);
-	INIT_RADIX_TREE(&srq_table->tree, GFP_ATOMIC);
+	xa_init(&srq_table->array);
 	if (mlx4_is_slave(dev))
 		return 0;
 
@@ -297,13 +288,7 @@ void mlx4_cleanup_srq_table(struct mlx4_dev *dev)
 struct mlx4_srq *mlx4_srq_lookup(struct mlx4_dev *dev, u32 srqn)
 {
 	struct mlx4_srq_table *srq_table = &mlx4_priv(dev)->srq_table;
-	struct mlx4_srq *srq;
-
-	rcu_read_lock();
-	srq = radix_tree_lookup(&srq_table->tree,
-				srqn & (dev->caps.num_srqs - 1));
-	rcu_read_unlock();
 
-	return srq;
+	return xa_load(&srq_table->array, srqn & (dev->caps.num_srqs - 1));
 }
 EXPORT_SYMBOL_GPL(mlx4_srq_lookup);
-- 
2.23.0.rc1

[PATCH 03/38] mlx4: Convert qp_table_tree to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

This XArray appears to be modifiable from interrupt context, so we have
to be a little more careful with the locking.  However, the lookup can
be done without the spinlock held.  I cannot determine whether
mlx4_qp_alloc() is allowed to sleep, so I've retained the GFP_ATOMIC
there, but it could be turned into GFP_KERNEL if the callers can
tolerate it sleeping.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/ethernet/mellanox/mlx4/mlx4.h |  3 +-
 drivers/net/ethernet/mellanox/mlx4/qp.c   | 37 ++++++-----------------
 include/linux/mlx4/device.h               |  4 +--
 include/linux/mlx4/qp.h                   |  2 +-
 4 files changed, 14 insertions(+), 32 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx4/mlx4.h b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
index b6fe22bee9f4..aaece8480da7 100644
--- a/drivers/net/ethernet/mellanox/mlx4/mlx4.h
+++ b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
@@ -38,7 +38,7 @@
 #define MLX4_H
 
 #include <linux/mutex.h>
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
 #include <linux/rbtree.h>
 #include <linux/timer.h>
 #include <linux/semaphore.h>
@@ -716,7 +716,6 @@ struct mlx4_qp_table {
 	u32			zones_uids[MLX4_QP_TABLE_ZONE_NUM];
 	u32			rdmarc_base;
 	int			rdmarc_shift;
-	spinlock_t		lock;
 	struct mlx4_icm_table	qp_table;
 	struct mlx4_icm_table	auxc_table;
 	struct mlx4_icm_table	altc_table;
diff --git a/drivers/net/ethernet/mellanox/mlx4/qp.c b/drivers/net/ethernet/mellanox/mlx4/qp.c
index 427e7a31862c..4659ecec12c1 100644
--- a/drivers/net/ethernet/mellanox/mlx4/qp.c
+++ b/drivers/net/ethernet/mellanox/mlx4/qp.c
@@ -48,16 +48,13 @@
 
 void mlx4_qp_event(struct mlx4_dev *dev, u32 qpn, int event_type)
 {
-	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
 	struct mlx4_qp *qp;
 
-	spin_lock(&qp_table->lock);
-
+	xa_lock(&dev->qp_table);
 	qp = __mlx4_qp_lookup(dev, qpn);
 	if (qp)
 		refcount_inc(&qp->refcount);
-
-	spin_unlock(&qp_table->lock);
+	xa_unlock(&dev->qp_table);
 
 	if (!qp) {
 		mlx4_dbg(dev, "Async event for none existent QP %08x\n", qpn);
@@ -390,21 +387,11 @@ static void mlx4_qp_free_icm(struct mlx4_dev *dev, int qpn)
 
 struct mlx4_qp *mlx4_qp_lookup(struct mlx4_dev *dev, u32 qpn)
 {
-	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
-	struct mlx4_qp *qp;
-
-	spin_lock_irq(&qp_table->lock);
-
-	qp = __mlx4_qp_lookup(dev, qpn);
-
-	spin_unlock_irq(&qp_table->lock);
-	return qp;
+	return __mlx4_qp_lookup(dev, qpn);
 }
 
 int mlx4_qp_alloc(struct mlx4_dev *dev, int qpn, struct mlx4_qp *qp)
 {
-	struct mlx4_priv *priv = mlx4_priv(dev);
-	struct mlx4_qp_table *qp_table = &priv->qp_table;
 	int err;
 
 	if (!qpn)
@@ -416,10 +403,9 @@ int mlx4_qp_alloc(struct mlx4_dev *dev, int qpn, struct mlx4_qp *qp)
 	if (err)
 		return err;
 
-	spin_lock_irq(&qp_table->lock);
-	err = radix_tree_insert(&dev->qp_table_tree, qp->qpn &
-				(dev->caps.num_qps - 1), qp);
-	spin_unlock_irq(&qp_table->lock);
+	err = xa_err(xa_store_irq(&dev->qp_table,
+				qp->qpn & (dev->caps.num_qps - 1),
+				qp, GFP_ATOMIC));
 	if (err)
 		goto err_icm;
 
@@ -512,12 +498,11 @@ EXPORT_SYMBOL_GPL(mlx4_update_qp);
 
 void mlx4_qp_remove(struct mlx4_dev *dev, struct mlx4_qp *qp)
 {
-	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
 	unsigned long flags;
 
-	spin_lock_irqsave(&qp_table->lock, flags);
-	radix_tree_delete(&dev->qp_table_tree, qp->qpn & (dev->caps.num_qps - 1));
-	spin_unlock_irqrestore(&qp_table->lock, flags);
+	xa_lock_irqsave(&dev->qp_table, flags);
+	__xa_erase(&dev->qp_table, qp->qpn & (dev->caps.num_qps - 1));
+	xa_unlock_irqrestore(&dev->qp_table, flags);
 }
 EXPORT_SYMBOL_GPL(mlx4_qp_remove);
 
@@ -760,7 +745,6 @@ static void mlx4_cleanup_qp_zones(struct mlx4_dev *dev)
 
 int mlx4_init_qp_table(struct mlx4_dev *dev)
 {
-	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
 	int err;
 	int reserved_from_top = 0;
 	int reserved_from_bot;
@@ -770,8 +754,7 @@ int mlx4_init_qp_table(struct mlx4_dev *dev)
 	u32 max_table_offset = dev->caps.dmfs_high_rate_qpn_base +
 			dev->caps.dmfs_high_rate_qpn_range;
 
-	spin_lock_init(&qp_table->lock);
-	INIT_RADIX_TREE(&dev->qp_table_tree, GFP_ATOMIC);
+	xa_init_flags(&dev->qp_table, XA_FLAGS_LOCK_IRQ);
 	if (mlx4_is_slave(dev))
 		return 0;
 
diff --git a/include/linux/mlx4/device.h b/include/linux/mlx4/device.h
index 36e412c3d657..acffca7d9f00 100644
--- a/include/linux/mlx4/device.h
+++ b/include/linux/mlx4/device.h
@@ -36,7 +36,7 @@
 #include <linux/if_ether.h>
 #include <linux/pci.h>
 #include <linux/completion.h>
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
 #include <linux/cpu_rmap.h>
 #include <linux/crash_dump.h>
 
@@ -889,7 +889,7 @@ struct mlx4_dev {
 	struct mlx4_caps	caps;
 	struct mlx4_phys_caps	phys_caps;
 	struct mlx4_quotas	quotas;
-	struct radix_tree_root	qp_table_tree;
+	struct xarray		qp_table;
 	u8			rev_id;
 	u8			port_random_macs;
 	char			board_id[MLX4_BOARD_ID_LEN];
diff --git a/include/linux/mlx4/qp.h b/include/linux/mlx4/qp.h
index 8e2828d48d7f..6c3ec3197a10 100644
--- a/include/linux/mlx4/qp.h
+++ b/include/linux/mlx4/qp.h
@@ -488,7 +488,7 @@ int mlx4_qp_to_ready(struct mlx4_dev *dev, struct mlx4_mtt *mtt,
 
 static inline struct mlx4_qp *__mlx4_qp_lookup(struct mlx4_dev *dev, u32 qpn)
 {
-	return radix_tree_lookup(&dev->qp_table_tree, qpn & (dev->caps.num_qps - 1));
+	return xa_load(&dev->qp_table, qpn & (dev->caps.num_qps - 1));
 }
 
 void mlx4_qp_remove(struct mlx4_dev *dev, struct mlx4_qp *qp);
-- 
2.23.0.rc1

[PATCH 04/38] mlx5: Convert cq_table to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Since mlx5_cq_table would have shrunk down to just the xarray, eliminate
it and embed the xarray directly into mlx5_eq.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/ethernet/mellanox/mlx5/core/eq.c  | 27 ++++---------------
 .../net/ethernet/mellanox/mlx5/core/lib/eq.h  |  7 +----
 2 files changed, 6 insertions(+), 28 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx5/core/eq.c b/drivers/net/ethernet/mellanox/mlx5/core/eq.c
index 09d4c64b6e73..c5953f6e0a69 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/eq.c
+++ b/drivers/net/ethernet/mellanox/mlx5/core/eq.c
@@ -113,11 +113,10 @@ static int mlx5_cmd_destroy_eq(struct mlx5_core_dev *dev, u8 eqn)
 /* caller must eventually call mlx5_cq_put on the returned cq */
 static struct mlx5_core_cq *mlx5_eq_cq_get(struct mlx5_eq *eq, u32 cqn)
 {
-	struct mlx5_cq_table *table = &eq->cq_table;
-	struct mlx5_core_cq *cq = NULL;
+	struct mlx5_core_cq *cq;
 
 	rcu_read_lock();
-	cq = radix_tree_lookup(&table->tree, cqn);
+	cq = xa_load(&eq->cq_table, cqn);
 	if (likely(cq))
 		mlx5_cq_hold(cq);
 	rcu_read_unlock();
@@ -243,7 +242,6 @@ static int
 create_map_eq(struct mlx5_core_dev *dev, struct mlx5_eq *eq,
 	      struct mlx5_eq_param *param)
 {
-	struct mlx5_cq_table *cq_table = &eq->cq_table;
 	u32 out[MLX5_ST_SZ_DW(create_eq_out)] = {0};
 	struct mlx5_priv *priv = &dev->priv;
 	u8 vecidx = param->irq_index;
@@ -254,11 +252,7 @@ create_map_eq(struct mlx5_core_dev *dev, struct mlx5_eq *eq,
 	int err;
 	int i;
 
-	/* Init CQ table */
-	memset(cq_table, 0, sizeof(*cq_table));
-	spin_lock_init(&cq_table->lock);
-	INIT_RADIX_TREE(&cq_table->tree, GFP_ATOMIC);
-
+	xa_init_flags(&eq->cq_table, XA_FLAGS_LOCK_IRQ);
 	eq->nent = roundup_pow_of_two(param->nent + MLX5_NUM_SPARE_EQE);
 	eq->cons_index = 0;
 	err = mlx5_buf_alloc(dev, eq->nent * MLX5_EQE_SIZE, &eq->buf);
@@ -378,25 +372,14 @@ static int destroy_unmap_eq(struct mlx5_core_dev *dev, struct mlx5_eq *eq)
 
 int mlx5_eq_add_cq(struct mlx5_eq *eq, struct mlx5_core_cq *cq)
 {
-	struct mlx5_cq_table *table = &eq->cq_table;
-	int err;
-
-	spin_lock(&table->lock);
-	err = radix_tree_insert(&table->tree, cq->cqn, cq);
-	spin_unlock(&table->lock);
-
-	return err;
+	return xa_err(xa_store(&eq->cq_table, cq->cqn, cq, GFP_KERNEL));
 }
 
 void mlx5_eq_del_cq(struct mlx5_eq *eq, struct mlx5_core_cq *cq)
 {
-	struct mlx5_cq_table *table = &eq->cq_table;
 	struct mlx5_core_cq *tmp;
 
-	spin_lock(&table->lock);
-	tmp = radix_tree_delete(&table->tree, cq->cqn);
-	spin_unlock(&table->lock);
-
+	tmp = xa_erase(&eq->cq_table, cq->cqn);
 	if (!tmp) {
 		mlx5_core_dbg(eq->dev, "cq 0x%x not found in eq 0x%x tree\n",
 			      eq->eqn, cq->cqn);
diff --git a/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h b/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
index 4be4d2d36218..a342cf78120e 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
+++ b/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
@@ -16,14 +16,9 @@ struct mlx5_eq_tasklet {
 	spinlock_t            lock; /* lock completion tasklet list */
 };
 
-struct mlx5_cq_table {
-	spinlock_t              lock;	/* protect radix tree */
-	struct radix_tree_root  tree;
-};
-
 struct mlx5_eq {
 	struct mlx5_core_dev    *dev;
-	struct mlx5_cq_table    cq_table;
+	struct xarray		cq_table;
 	__be32 __iomem	        *doorbell;
 	u32                     cons_index;
 	struct mlx5_frag_buf    buf;
-- 
2.23.0.rc1

[PATCH 05/38] mlx5: Convert mlx5_qp_table to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Fix the locking in destroy_resource_common() to be irq-disable rather
than irq-save.  wait_for_completion() can sleep, so this function must
not be callable from interrupt context.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/ethernet/mellanox/mlx5/core/qp.c | 38 ++++++--------------
 include/linux/mlx5/driver.h                  |  8 ++---
 include/linux/mlx5/qp.h                      |  2 +-
 3 files changed, 13 insertions(+), 35 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx5/core/qp.c b/drivers/net/ethernet/mellanox/mlx5/core/qp.c
index b8ba74de9555..e3367290b5ce 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/qp.c
+++ b/drivers/net/ethernet/mellanox/mlx5/core/qp.c
@@ -49,13 +49,11 @@ mlx5_get_rsc(struct mlx5_qp_table *table, u32 rsn)
 	struct mlx5_core_rsc_common *common;
 	unsigned long flags;
 
-	spin_lock_irqsave(&table->lock, flags);
-
-	common = radix_tree_lookup(&table->tree, rsn);
+	xa_lock_irqsave(&table->array, flags);
+	common = xa_load(&table->array, rsn);
 	if (common)
 		atomic_inc(&common->refcount);
-
-	spin_unlock_irqrestore(&table->lock, flags);
+	xa_unlock_irqrestore(&table->array, flags);
 
 	return common;
 }
@@ -197,35 +195,22 @@ static int create_resource_common(struct mlx5_core_dev *dev,
 				  struct mlx5_core_qp *qp,
 				  int rsc_type)
 {
-	struct mlx5_qp_table *table = &dev->priv.qp_table;
-	int err;
-
-	qp->common.res = rsc_type;
-	spin_lock_irq(&table->lock);
-	err = radix_tree_insert(&table->tree,
-				qp->qpn | (rsc_type << MLX5_USER_INDEX_LEN),
-				qp);
-	spin_unlock_irq(&table->lock);
-	if (err)
-		return err;
-
 	atomic_set(&qp->common.refcount, 1);
 	init_completion(&qp->common.free);
 	qp->pid = current->pid;
 
-	return 0;
+	qp->common.res = rsc_type;
+	return xa_err(xa_store_irq(&dev->priv.qp_table.array,
+				qp->qpn | (rsc_type << MLX5_USER_INDEX_LEN),
+				qp, GFP_KERNEL));
 }
 
 static void destroy_resource_common(struct mlx5_core_dev *dev,
 				    struct mlx5_core_qp *qp)
 {
-	struct mlx5_qp_table *table = &dev->priv.qp_table;
-	unsigned long flags;
+	struct xarray *xa = &dev->priv.qp_table.array;
 
-	spin_lock_irqsave(&table->lock, flags);
-	radix_tree_delete(&table->tree,
-			  qp->qpn | (qp->common.res << MLX5_USER_INDEX_LEN));
-	spin_unlock_irqrestore(&table->lock, flags);
+	xa_erase_irq(xa, qp->qpn | (qp->common.res << MLX5_USER_INDEX_LEN));
 	mlx5_core_put_rsc((struct mlx5_core_rsc_common *)qp);
 	wait_for_completion(&qp->common.free);
 }
@@ -524,10 +509,7 @@ EXPORT_SYMBOL_GPL(mlx5_core_qp_modify);
 void mlx5_init_qp_table(struct mlx5_core_dev *dev)
 {
 	struct mlx5_qp_table *table = &dev->priv.qp_table;
-
-	memset(table, 0, sizeof(*table));
-	spin_lock_init(&table->lock);
-	INIT_RADIX_TREE(&table->tree, GFP_ATOMIC);
+	xa_init_flags(&table->array, XA_FLAGS_LOCK_IRQ);
 	mlx5_qp_debugfs_init(dev);
 
 	table->nb.notifier_call = rsc_event_notifier;
diff --git a/include/linux/mlx5/driver.h b/include/linux/mlx5/driver.h
index df23f17eed64..ba8f59b11920 100644
--- a/include/linux/mlx5/driver.h
+++ b/include/linux/mlx5/driver.h
@@ -448,12 +448,8 @@ struct mlx5_core_health {
 };
 
 struct mlx5_qp_table {
-	struct notifier_block   nb;
-
-	/* protect radix tree
-	 */
-	spinlock_t		lock;
-	struct radix_tree_root	tree;
+	struct notifier_block	nb;
+	struct xarray		array;
 };
 
 struct mlx5_vf_context {
diff --git a/include/linux/mlx5/qp.h b/include/linux/mlx5/qp.h
index ae63b1ae9004..6d1577a1ca41 100644
--- a/include/linux/mlx5/qp.h
+++ b/include/linux/mlx5/qp.h
@@ -555,7 +555,7 @@ struct mlx5_qp_context {
 
 static inline struct mlx5_core_qp *__mlx5_qp_lookup(struct mlx5_core_dev *dev, u32 qpn)
 {
-	return radix_tree_lookup(&dev->priv.qp_table.tree, qpn);
+	return xa_load(&dev->priv.qp_table.array, qpn);
 }
 
 int mlx5_core_create_dct(struct mlx5_core_dev *dev,
-- 
2.23.0.rc1

[PATCH 06/38] mlx5: Convert counters_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

This IDR wasn't using the allocation functionality, so convert it to a
plain XArray.  I also suspect it could be used to replace the list_head
'counters', but I'm not willing to do that work right now.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 .../ethernet/mellanox/mlx5/core/fs_counters.c | 31 +++++--------------
 include/linux/mlx5/driver.h                   |  3 +-
 2 files changed, 9 insertions(+), 25 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c b/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c
index 1804cf3c3814..5ee20d285c5e 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c
+++ b/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c
@@ -108,18 +108,14 @@ static struct list_head *mlx5_fc_counters_lookup_next(struct mlx5_core_dev *dev,
 						      u32 id)
 {
 	struct mlx5_fc_stats *fc_stats = &dev->priv.fc_stats;
-	unsigned long next_id = (unsigned long)id + 1;
 	struct mlx5_fc *counter;
-	unsigned long tmp;
+	unsigned long next_id;
 
-	rcu_read_lock();
-	/* skip counters that are in idr, but not yet in counters list */
-	idr_for_each_entry_continue_ul(&fc_stats->counters_idr,
-				       counter, tmp, next_id) {
+	/* skip counters that are not yet in counters list */
+	xa_for_each_start(&fc_stats->counters_xa, next_id, counter, id + 1) {
 		if (!list_empty(&counter->list))
 			break;
 	}
-	rcu_read_unlock();
 
 	return counter ? &counter->list : &fc_stats->counters;
 }
@@ -139,9 +135,7 @@ static void mlx5_fc_stats_remove(struct mlx5_core_dev *dev,
 
 	list_del(&counter->list);
 
-	spin_lock(&fc_stats->counters_idr_lock);
-	WARN_ON(!idr_remove(&fc_stats->counters_idr, counter->id));
-	spin_unlock(&fc_stats->counters_idr_lock);
+	WARN_ON(!xa_erase(&fc_stats->counters_xa, counter->id));
 }
 
 static int get_max_bulk_query_len(struct mlx5_core_dev *dev)
@@ -309,20 +303,12 @@ struct mlx5_fc *mlx5_fc_create(struct mlx5_core_dev *dev, bool aging)
 	counter->aging = aging;
 
 	if (aging) {
-		u32 id = counter->id;
-
 		counter->cache.lastuse = jiffies;
 		counter->lastbytes = counter->cache.bytes;
 		counter->lastpackets = counter->cache.packets;
 
-		idr_preload(GFP_KERNEL);
-		spin_lock(&fc_stats->counters_idr_lock);
-
-		err = idr_alloc_u32(&fc_stats->counters_idr, counter, &id, id,
-				    GFP_NOWAIT);
-
-		spin_unlock(&fc_stats->counters_idr_lock);
-		idr_preload_end();
+		err = xa_insert(&fc_stats->counters_xa, counter->id, counter,
+				GFP_KERNEL);
 		if (err)
 			goto err_out_alloc;
 
@@ -368,8 +354,7 @@ int mlx5_init_fc_stats(struct mlx5_core_dev *dev)
 	int max_bulk_len;
 	int max_out_len;
 
-	spin_lock_init(&fc_stats->counters_idr_lock);
-	idr_init(&fc_stats->counters_idr);
+	xa_init(&fc_stats->counters_xa);
 	INIT_LIST_HEAD(&fc_stats->counters);
 	init_llist_head(&fc_stats->addlist);
 	init_llist_head(&fc_stats->dellist);
@@ -409,7 +394,7 @@ void mlx5_cleanup_fc_stats(struct mlx5_core_dev *dev)
 
 	kfree(fc_stats->bulk_query_out);
 
-	idr_destroy(&fc_stats->counters_idr);
+	xa_destroy(&fc_stats->counters_xa);
 
 	tmplist = llist_del_all(&fc_stats->addlist);
 	llist_for_each_entry_safe(counter, tmp, tmplist, addlist)
diff --git a/include/linux/mlx5/driver.h b/include/linux/mlx5/driver.h
index ba8f59b11920..b8b66cdb8357 100644
--- a/include/linux/mlx5/driver.h
+++ b/include/linux/mlx5/driver.h
@@ -477,8 +477,7 @@ struct mlx5_fc_pool {
 };
 
 struct mlx5_fc_stats {
-	spinlock_t counters_idr_lock; /* protects counters_idr */
-	struct idr counters_idr;
+	struct xarray counters_xa;
 	struct list_head counters;
 	struct llist_head addlist;
 	struct llist_head dellist;
-- 
2.23.0.rc1

[PATCH 07/38] mlx5: Convert fpga IDRs to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Leave the locking as irq-disabling since it appears we can release
entries from interrupt context.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 .../ethernet/mellanox/mlx5/core/fpga/tls.c    | 54 +++++++------------
 .../ethernet/mellanox/mlx5/core/fpga/tls.h    |  6 +--
 2 files changed, 21 insertions(+), 39 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.c b/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.c
index 22a2ef111514..dbc09c8659a5 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.c
+++ b/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.c
@@ -121,16 +121,12 @@ static void mlx5_fpga_tls_cmd_send(struct mlx5_fpga_device *fdev,
 	spin_unlock_irqrestore(&tls->pending_cmds_lock, flags);
 }
 
-/* Start of context identifiers range (inclusive) */
-#define SWID_START	0
 /* End of context identifiers range (exclusive) */
 #define SWID_END	BIT(24)
 
-static int mlx5_fpga_tls_alloc_swid(struct idr *idr, spinlock_t *idr_spinlock,
-				    void *ptr)
+static int mlx5_fpga_tls_alloc_swid(struct xarray *xa, void *flow)
 {
-	unsigned long flags;
-	int ret;
+	int ret, id;
 
 	/* TLS metadata format is 1 byte for syndrome followed
 	 * by 3 bytes of swid (software ID)
@@ -139,24 +135,22 @@ static int mlx5_fpga_tls_alloc_swid(struct idr *idr, spinlock_t *idr_spinlock,
 	 */
 	BUILD_BUG_ON((SWID_END - 1) & 0xFF000000);
 
-	idr_preload(GFP_KERNEL);
-	spin_lock_irqsave(idr_spinlock, flags);
-	ret = idr_alloc(idr, ptr, SWID_START, SWID_END, GFP_ATOMIC);
-	spin_unlock_irqrestore(idr_spinlock, flags);
-	idr_preload_end();
+	ret = xa_alloc_irq(xa, &id, flow, XA_LIMIT(0, SWID_END - 1),
+			GFP_KERNEL);
+	if (!ret)
+		return id;
 
 	return ret;
 }
 
-static void *mlx5_fpga_tls_release_swid(struct idr *idr,
-					spinlock_t *idr_spinlock, u32 swid)
+static void *mlx5_fpga_tls_release_swid(struct xarray *xa, u32 swid)
 {
 	unsigned long flags;
 	void *ptr;
 
-	spin_lock_irqsave(idr_spinlock, flags);
-	ptr = idr_remove(idr, swid);
-	spin_unlock_irqrestore(idr_spinlock, flags);
+	xa_lock_irqsave(xa, flags);
+	ptr = __xa_erase(xa, swid);
+	xa_unlock_irqrestore(xa, flags);
 	return ptr;
 }
 
@@ -210,7 +204,7 @@ int mlx5_fpga_tls_resync_rx(struct mlx5_core_dev *mdev, u32 handle, u32 seq,
 	cmd = (buf + 1);
 
 	rcu_read_lock();
-	flow = idr_find(&mdev->fpga->tls->rx_idr, ntohl(handle));
+	flow = xa_load(&mdev->fpga->tls->rx_flows, ntohl(handle));
 	if (unlikely(!flow)) {
 		rcu_read_unlock();
 		WARN_ONCE(1, "Received NULL pointer for handle\n");
@@ -269,13 +263,9 @@ void mlx5_fpga_tls_del_flow(struct mlx5_core_dev *mdev, u32 swid,
 	void *flow;
 
 	if (direction_sx)
-		flow = mlx5_fpga_tls_release_swid(&tls->tx_idr,
-						  &tls->tx_idr_spinlock,
-						  swid);
+		flow = mlx5_fpga_tls_release_swid(&tls->tx_flows, swid);
 	else
-		flow = mlx5_fpga_tls_release_swid(&tls->rx_idr,
-						  &tls->rx_idr_spinlock,
-						  swid);
+		flow = mlx5_fpga_tls_release_swid(&tls->rx_flows, swid);
 
 	if (!flow) {
 		mlx5_fpga_err(mdev->fpga, "No flow information for swid %u\n",
@@ -483,10 +473,8 @@ int mlx5_fpga_tls_init(struct mlx5_core_dev *mdev)
 	spin_lock_init(&tls->pending_cmds_lock);
 	INIT_LIST_HEAD(&tls->pending_cmds);
 
-	idr_init(&tls->tx_idr);
-	idr_init(&tls->rx_idr);
-	spin_lock_init(&tls->tx_idr_spinlock);
-	spin_lock_init(&tls->rx_idr_spinlock);
+	xa_init_flags(&tls->tx_flows, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
+	xa_init_flags(&tls->rx_flows, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
 	fdev->tls = tls;
 	return 0;
 
@@ -591,11 +579,9 @@ int mlx5_fpga_tls_add_flow(struct mlx5_core_dev *mdev, void *flow,
 	u32 swid;
 
 	if (direction_sx)
-		ret = mlx5_fpga_tls_alloc_swid(&tls->tx_idr,
-					       &tls->tx_idr_spinlock, flow);
+		ret = mlx5_fpga_tls_alloc_swid(&tls->tx_flows, flow);
 	else
-		ret = mlx5_fpga_tls_alloc_swid(&tls->rx_idr,
-					       &tls->rx_idr_spinlock, flow);
+		ret = mlx5_fpga_tls_alloc_swid(&tls->rx_flows, flow);
 
 	if (ret < 0)
 		return ret;
@@ -612,11 +598,9 @@ int mlx5_fpga_tls_add_flow(struct mlx5_core_dev *mdev, void *flow,
 	return 0;
 free_swid:
 	if (direction_sx)
-		mlx5_fpga_tls_release_swid(&tls->tx_idr,
-					   &tls->tx_idr_spinlock, swid);
+		mlx5_fpga_tls_release_swid(&tls->tx_flows, swid);
 	else
-		mlx5_fpga_tls_release_swid(&tls->rx_idr,
-					   &tls->rx_idr_spinlock, swid);
+		mlx5_fpga_tls_release_swid(&tls->rx_flows, swid);
 
 	return ret;
 }
diff --git a/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.h b/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.h
index 3b2e37bf76fe..0b56332f453b 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.h
+++ b/drivers/net/ethernet/mellanox/mlx5/core/fpga/tls.h
@@ -45,10 +45,8 @@ struct mlx5_fpga_tls {
 	u32 caps;
 	struct mlx5_fpga_conn *conn;
 
-	struct idr tx_idr;
-	struct idr rx_idr;
-	spinlock_t tx_idr_spinlock; /* protects the IDR */
-	spinlock_t rx_idr_spinlock; /* protects the IDR */
+	struct xarray tx_flows;
+	struct xarray rx_flows;
 };
 
 int mlx5_fpga_tls_add_flow(struct mlx5_core_dev *mdev, void *flow,
-- 
2.23.0.rc1

[PATCH 08/38] nfp: Convert to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

A minor change in semantics where we simply store into the XArray rather
than insert; this only matters if there could already be something stored
at that index, and from my reading of the code that can't happen.

Use xa_for_each() rather than xas_for_each() as none of these loops
appear to be performance-critical.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/ethernet/netronome/nfp/abm/main.c |  4 +--
 drivers/net/ethernet/netronome/nfp/abm/main.h |  4 +--
 .../net/ethernet/netronome/nfp/abm/qdisc.c    | 33 +++++++------------
 3 files changed, 15 insertions(+), 26 deletions(-)

diff --git a/drivers/net/ethernet/netronome/nfp/abm/main.c b/drivers/net/ethernet/netronome/nfp/abm/main.c
index 9183b3e85d21..2a06a3012e39 100644
--- a/drivers/net/ethernet/netronome/nfp/abm/main.c
+++ b/drivers/net/ethernet/netronome/nfp/abm/main.c
@@ -345,7 +345,7 @@ nfp_abm_vnic_alloc(struct nfp_app *app, struct nfp_net *nn, unsigned int id)
 	netif_keep_dst(nn->dp.netdev);
 
 	nfp_abm_vnic_set_mac(app->pf, abm, nn, id);
-	INIT_RADIX_TREE(&alink->qdiscs, GFP_KERNEL);
+	xa_init(&alink->qdiscs);
 
 	return 0;
 
@@ -361,7 +361,7 @@ static void nfp_abm_vnic_free(struct nfp_app *app, struct nfp_net *nn)
 	struct nfp_abm_link *alink = nn->app_priv;
 
 	nfp_abm_kill_reprs(alink->abm, alink);
-	WARN(!radix_tree_empty(&alink->qdiscs), "left over qdiscs\n");
+	WARN(!xa_empty(&alink->qdiscs), "left over qdiscs\n");
 	kfree(alink->prio_map);
 	kfree(alink);
 }
diff --git a/drivers/net/ethernet/netronome/nfp/abm/main.h b/drivers/net/ethernet/netronome/nfp/abm/main.h
index 48746c9c6224..2b78abe606d9 100644
--- a/drivers/net/ethernet/netronome/nfp/abm/main.h
+++ b/drivers/net/ethernet/netronome/nfp/abm/main.h
@@ -6,7 +6,7 @@
 
 #include <linux/bits.h>
 #include <linux/list.h>
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
 #include <net/devlink.h>
 #include <net/pkt_cls.h>
 #include <net/pkt_sched.h>
@@ -219,7 +219,7 @@ struct nfp_abm_link {
 	struct list_head dscp_map;
 
 	struct nfp_qdisc *root_qdisc;
-	struct radix_tree_root qdiscs;
+	struct xarray qdiscs;
 };
 
 static inline bool nfp_abm_has_prio(struct nfp_abm *abm)
diff --git a/drivers/net/ethernet/netronome/nfp/abm/qdisc.c b/drivers/net/ethernet/netronome/nfp/abm/qdisc.c
index 2473fb5f75e5..b40ee2f5e1c1 100644
--- a/drivers/net/ethernet/netronome/nfp/abm/qdisc.c
+++ b/drivers/net/ethernet/netronome/nfp/abm/qdisc.c
@@ -24,11 +24,6 @@ static bool nfp_abm_qdisc_child_valid(struct nfp_qdisc *qdisc, unsigned int id)
 	       qdisc->children[id] != NFP_QDISC_UNTRACKED;
 }
 
-static void *nfp_abm_qdisc_tree_deref_slot(void __rcu **slot)
-{
-	return rtnl_dereference(*slot);
-}
-
 static void
 nfp_abm_stats_propagate(struct nfp_alink_stats *parent,
 			struct nfp_alink_stats *child)
@@ -245,10 +240,8 @@ nfp_abm_offload_compile_mq(struct nfp_abm_link *alink, struct nfp_qdisc *qdisc)
 void nfp_abm_qdisc_offload_update(struct nfp_abm_link *alink)
 {
 	struct nfp_abm *abm = alink->abm;
-	struct radix_tree_iter iter;
 	struct nfp_qdisc *qdisc;
-	void __rcu **slot;
-	size_t i;
+	unsigned long i;
 
 	/* Mark all thresholds as unconfigured */
 	for (i = 0; i < abm->num_bands; i++)
@@ -257,17 +250,14 @@ void nfp_abm_qdisc_offload_update(struct nfp_abm_link *alink)
 			     alink->total_queues);
 
 	/* Clear offload marks */
-	radix_tree_for_each_slot(slot, &alink->qdiscs, &iter, 0) {
-		qdisc = nfp_abm_qdisc_tree_deref_slot(slot);
+	xa_for_each(&alink->qdiscs, i, qdisc)
 		qdisc->offload_mark = false;
-	}
 
 	if (alink->root_qdisc)
 		nfp_abm_offload_compile_mq(alink, alink->root_qdisc);
 
 	/* Refresh offload status */
-	radix_tree_for_each_slot(slot, &alink->qdiscs, &iter, 0) {
-		qdisc = nfp_abm_qdisc_tree_deref_slot(slot);
+	xa_for_each(&alink->qdiscs, i, qdisc) {
 		if (!qdisc->offload_mark && qdisc->offloaded)
 			nfp_abm_qdisc_offload_stop(alink, qdisc);
 		qdisc->offloaded = qdisc->offload_mark;
@@ -285,9 +275,9 @@ static void
 nfp_abm_qdisc_clear_mq(struct net_device *netdev, struct nfp_abm_link *alink,
 		       struct nfp_qdisc *qdisc)
 {
-	struct radix_tree_iter iter;
 	unsigned int mq_refs = 0;
-	void __rcu **slot;
+	unsigned long index;
+	struct nfp_qdisc *mq;
 
 	if (!qdisc->use_cnt)
 		return;
@@ -300,8 +290,7 @@ nfp_abm_qdisc_clear_mq(struct net_device *netdev, struct nfp_abm_link *alink,
 		return;
 
 	/* Count refs held by MQ instances and clear pointers */
-	radix_tree_for_each_slot(slot, &alink->qdiscs, &iter, 0) {
-		struct nfp_qdisc *mq = nfp_abm_qdisc_tree_deref_slot(slot);
+	xa_for_each(&alink->qdiscs, index, mq) {
 		unsigned int i;
 
 		if (mq->type != NFP_QDISC_MQ || mq->netdev != netdev)
@@ -326,8 +315,7 @@ nfp_abm_qdisc_free(struct net_device *netdev, struct nfp_abm_link *alink,
 	if (!qdisc)
 		return;
 	nfp_abm_qdisc_clear_mq(netdev, alink, qdisc);
-	WARN_ON(radix_tree_delete(&alink->qdiscs,
-				  TC_H_MAJ(qdisc->handle)) != qdisc);
+	WARN_ON(xa_erase(&alink->qdiscs, TC_H_MAJ(qdisc->handle)) != qdisc);
 
 	kfree(qdisc->children);
 	kfree(qdisc);
@@ -360,10 +348,11 @@ nfp_abm_qdisc_alloc(struct net_device *netdev, struct nfp_abm_link *alink,
 	qdisc->handle = handle;
 	qdisc->num_children = children;
 
-	err = radix_tree_insert(&alink->qdiscs, TC_H_MAJ(qdisc->handle), qdisc);
+	err = xa_err(xa_store(&alink->qdiscs, TC_H_MAJ(qdisc->handle), qdisc,
+				GFP_KERNEL));
 	if (err) {
 		nfp_err(alink->abm->app->cpp,
-			"Qdisc insertion into radix tree failed: %d\n", err);
+			"Qdisc insertion failed: %d\n", err);
 		goto err_free_child_tbl;
 	}
 
@@ -380,7 +369,7 @@ nfp_abm_qdisc_alloc(struct net_device *netdev, struct nfp_abm_link *alink,
 static struct nfp_qdisc *
 nfp_abm_qdisc_find(struct nfp_abm_link *alink, u32 handle)
 {
-	return radix_tree_lookup(&alink->qdiscs, TC_H_MAJ(handle));
+	return xa_load(&alink->qdiscs, TC_H_MAJ(handle));
 }
 
 static int
-- 
2.23.0.rc1

[PATCH 09/38] ath10k: Convert pending_tx to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Leave the tx_lock in place; it might be removable around some of the
places that use the XArray, but err on the side of double locking for now.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/wireless/ath/ath10k/htt.h    |  2 +-
 drivers/net/wireless/ath/ath10k/htt_tx.c | 31 ++++++++++++------------
 drivers/net/wireless/ath/ath10k/mac.c    |  4 +--
 drivers/net/wireless/ath/ath10k/txrx.c   |  2 +-
 4 files changed, 20 insertions(+), 19 deletions(-)

diff --git a/drivers/net/wireless/ath/ath10k/htt.h b/drivers/net/wireless/ath/ath10k/htt.h
index 30c080094af1..971f0a8629bc 100644
--- a/drivers/net/wireless/ath/ath10k/htt.h
+++ b/drivers/net/wireless/ath/ath10k/htt.h
@@ -1965,7 +1965,7 @@ struct ath10k_htt {
 	int max_num_pending_tx;
 	int num_pending_tx;
 	int num_pending_mgmt_tx;
-	struct idr pending_tx;
+	struct xarray pending_tx;
 	wait_queue_head_t empty_tx_wq;
 
 	/* FIFO for storing tx done status {ack, no-ack, discard} and msdu id */
diff --git a/drivers/net/wireless/ath/ath10k/htt_tx.c b/drivers/net/wireless/ath/ath10k/htt_tx.c
index 2ef717f18795..c25b01fcfa53 100644
--- a/drivers/net/wireless/ath/ath10k/htt_tx.c
+++ b/drivers/net/wireless/ath/ath10k/htt_tx.c
@@ -195,13 +195,16 @@ void ath10k_htt_tx_mgmt_dec_pending(struct ath10k_htt *htt)
 int ath10k_htt_tx_alloc_msdu_id(struct ath10k_htt *htt, struct sk_buff *skb)
 {
 	struct ath10k *ar = htt->ar;
-	int ret;
+	int ret, id;
 
 	spin_lock_bh(&htt->tx_lock);
-	ret = idr_alloc(&htt->pending_tx, skb, 0,
-			htt->max_num_pending_tx, GFP_ATOMIC);
+	ret = xa_alloc(&htt->pending_tx, &id, skb,
+			XA_LIMIT(0, htt->max_num_pending_tx - 1), GFP_ATOMIC);
 	spin_unlock_bh(&htt->tx_lock);
 
+	if (ret == 0)
+		ret = id;
+
 	ath10k_dbg(ar, ATH10K_DBG_HTT, "htt tx alloc msdu_id %d\n", ret);
 
 	return ret;
@@ -215,7 +218,7 @@ void ath10k_htt_tx_free_msdu_id(struct ath10k_htt *htt, u16 msdu_id)
 
 	ath10k_dbg(ar, ATH10K_DBG_HTT, "htt tx free msdu_id %hu\n", msdu_id);
 
-	idr_remove(&htt->pending_tx, msdu_id);
+	xa_erase(&htt->pending_tx, msdu_id);
 }
 
 static void ath10k_htt_tx_free_cont_txbuf_32(struct ath10k_htt *htt)
@@ -479,7 +482,7 @@ int ath10k_htt_tx_start(struct ath10k_htt *htt)
 		   htt->max_num_pending_tx);
 
 	spin_lock_init(&htt->tx_lock);
-	idr_init(&htt->pending_tx);
+	xa_init_flags(&htt->pending_tx, XA_FLAGS_ALLOC);
 
 	if (htt->tx_mem_allocated)
 		return 0;
@@ -489,21 +492,15 @@ int ath10k_htt_tx_start(struct ath10k_htt *htt)
 
 	ret = ath10k_htt_tx_alloc_buf(htt);
 	if (ret)
-		goto free_idr_pending_tx;
+		return ret;
 
 	htt->tx_mem_allocated = true;
 
 	return 0;
-
-free_idr_pending_tx:
-	idr_destroy(&htt->pending_tx);
-
-	return ret;
 }
 
-static int ath10k_htt_tx_clean_up_pending(int msdu_id, void *skb, void *ctx)
+static int ath10k_htt_tx_clean_up_pending(int msdu_id, struct ath10k *ar)
 {
-	struct ath10k *ar = ctx;
 	struct ath10k_htt *htt = &ar->htt;
 	struct htt_tx_done tx_done = {0};
 
@@ -531,8 +528,12 @@ void ath10k_htt_tx_destroy(struct ath10k_htt *htt)
 
 void ath10k_htt_tx_stop(struct ath10k_htt *htt)
 {
-	idr_for_each(&htt->pending_tx, ath10k_htt_tx_clean_up_pending, htt->ar);
-	idr_destroy(&htt->pending_tx);
+	struct sk_buff *skb;
+	unsigned long index;
+
+	xa_for_each(&htt->pending_tx, index, skb)
+		ath10k_htt_tx_clean_up_pending(index, htt->ar);
+	xa_destroy(&htt->pending_tx);
 }
 
 void ath10k_htt_tx_free(struct ath10k_htt *htt)
diff --git a/drivers/net/wireless/ath/ath10k/mac.c b/drivers/net/wireless/ath/ath10k/mac.c
index 12dad659bf68..9c4cb2e31b76 100644
--- a/drivers/net/wireless/ath/ath10k/mac.c
+++ b/drivers/net/wireless/ath/ath10k/mac.c
@@ -3939,13 +3939,13 @@ static void ath10k_mac_txq_unref(struct ath10k *ar, struct ieee80211_txq *txq)
 {
 	struct ath10k_skb_cb *cb;
 	struct sk_buff *msdu;
-	int msdu_id;
+	unsigned long msdu_id;
 
 	if (!txq)
 		return;
 
 	spin_lock_bh(&ar->htt.tx_lock);
-	idr_for_each_entry(&ar->htt.pending_tx, msdu, msdu_id) {
+	xa_for_each(&ar->htt.pending_tx, msdu_id, msdu) {
 		cb = ATH10K_SKB_CB(msdu);
 		if (cb->txq == txq)
 			cb->txq = NULL;
diff --git a/drivers/net/wireless/ath/ath10k/txrx.c b/drivers/net/wireless/ath/ath10k/txrx.c
index 4102df016931..87bf6ab65347 100644
--- a/drivers/net/wireless/ath/ath10k/txrx.c
+++ b/drivers/net/wireless/ath/ath10k/txrx.c
@@ -62,7 +62,7 @@ int ath10k_txrx_tx_unref(struct ath10k_htt *htt,
 	}
 
 	spin_lock_bh(&htt->tx_lock);
-	msdu = idr_find(&htt->pending_tx, tx_done->msdu_id);
+	msdu = xa_load(&htt->pending_tx, tx_done->msdu_id);
 	if (!msdu) {
 		ath10k_warn(ar, "received tx completion for invalid msdu_id: %d\n",
 			    tx_done->msdu_id);
-- 
2.23.0.rc1

[PATCH 10/38] ath10k: Convert mgmt_pending_tx IDR to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Leave the ->data_lock locking in place; it may be possible to remove it,
but err on the side of double-locking for now.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/wireless/ath/ath10k/core.h    |  2 +-
 drivers/net/wireless/ath/ath10k/wmi-tlv.c |  8 +++--
 drivers/net/wireless/ath/ath10k/wmi.c     | 43 ++++++++++-------------
 3 files changed, 25 insertions(+), 28 deletions(-)

diff --git a/drivers/net/wireless/ath/ath10k/core.h b/drivers/net/wireless/ath/ath10k/core.h
index 4d7db07db6ba..89b94322aeb1 100644
--- a/drivers/net/wireless/ath/ath10k/core.h
+++ b/drivers/net/wireless/ath/ath10k/core.h
@@ -175,7 +175,7 @@ struct ath10k_wmi {
 	u32 mgmt_max_num_pending_tx;
 
 	/* Protected by data_lock */
-	struct idr mgmt_pending_tx;
+	struct xarray mgmt_pending_tx;
 
 	u32 num_mem_chunks;
 	u32 rx_decap_mode;
diff --git a/drivers/net/wireless/ath/ath10k/wmi-tlv.c b/drivers/net/wireless/ath/ath10k/wmi-tlv.c
index 2985bb17decd..6144d6d9c539 100644
--- a/drivers/net/wireless/ath/ath10k/wmi-tlv.c
+++ b/drivers/net/wireless/ath/ath10k/wmi-tlv.c
@@ -2843,7 +2843,7 @@ ath10k_wmi_mgmt_tx_alloc_msdu_id(struct ath10k *ar, struct sk_buff *skb,
 {
 	struct ath10k_wmi *wmi = &ar->wmi;
 	struct ath10k_mgmt_tx_pkt_addr *pkt_addr;
-	int ret;
+	int ret, id;
 
 	pkt_addr = kmalloc(sizeof(*pkt_addr), GFP_ATOMIC);
 	if (!pkt_addr)
@@ -2853,9 +2853,11 @@ ath10k_wmi_mgmt_tx_alloc_msdu_id(struct ath10k *ar, struct sk_buff *skb,
 	pkt_addr->paddr = paddr;
 
 	spin_lock_bh(&ar->data_lock);
-	ret = idr_alloc(&wmi->mgmt_pending_tx, pkt_addr, 0,
-			wmi->mgmt_max_num_pending_tx, GFP_ATOMIC);
+	ret = xa_alloc(&wmi->mgmt_pending_tx, &id, pkt_addr,
+			XA_LIMIT(0, wmi->mgmt_max_num_pending_tx), GFP_ATOMIC);
 	spin_unlock_bh(&ar->data_lock);
+	if (ret == 0)
+		ret = id;
 
 	ath10k_dbg(ar, ATH10K_DBG_WMI, "wmi mgmt tx alloc msdu_id ret %d\n", ret);
 	return ret;
diff --git a/drivers/net/wireless/ath/ath10k/wmi.c b/drivers/net/wireless/ath/ath10k/wmi.c
index 4f707c6394bb..280220c4fe3b 100644
--- a/drivers/net/wireless/ath/ath10k/wmi.c
+++ b/drivers/net/wireless/ath/ath10k/wmi.c
@@ -2353,7 +2353,7 @@ wmi_process_mgmt_tx_comp(struct ath10k *ar, struct mgmt_tx_compl_params *param)
 
 	spin_lock_bh(&ar->data_lock);
 
-	pkt_addr = idr_find(&wmi->mgmt_pending_tx, param->desc_id);
+	pkt_addr = xa_load(&wmi->mgmt_pending_tx, param->desc_id);
 	if (!pkt_addr) {
 		ath10k_warn(ar, "received mgmt tx completion for invalid msdu_id: %d\n",
 			    param->desc_id);
@@ -2380,7 +2380,7 @@ wmi_process_mgmt_tx_comp(struct ath10k *ar, struct mgmt_tx_compl_params *param)
 	ret = 0;
 
 out:
-	idr_remove(&wmi->mgmt_pending_tx, param->desc_id);
+	xa_erase(&wmi->mgmt_pending_tx, param->desc_id);
 	spin_unlock_bh(&ar->data_lock);
 	return ret;
 }
@@ -9389,7 +9389,7 @@ int ath10k_wmi_attach(struct ath10k *ar)
 
 	if (test_bit(ATH10K_FW_FEATURE_MGMT_TX_BY_REF,
 		     ar->running_fw->fw_file.fw_features)) {
-		idr_init(&ar->wmi.mgmt_pending_tx);
+		xa_init_flags(&ar->wmi.mgmt_pending_tx, XA_FLAGS_ALLOC);
 	}
 
 	return 0;
@@ -9410,32 +9410,27 @@ void ath10k_wmi_free_host_mem(struct ath10k *ar)
 	ar->wmi.num_mem_chunks = 0;
 }
 
-static int ath10k_wmi_mgmt_tx_clean_up_pending(int msdu_id, void *ptr,
-					       void *ctx)
-{
-	struct ath10k_mgmt_tx_pkt_addr *pkt_addr = ptr;
-	struct ath10k *ar = ctx;
-	struct sk_buff *msdu;
-
-	ath10k_dbg(ar, ATH10K_DBG_WMI,
-		   "force cleanup mgmt msdu_id %hu\n", msdu_id);
-
-	msdu = pkt_addr->vaddr;
-	dma_unmap_single(ar->dev, pkt_addr->paddr,
-			 msdu->len, DMA_FROM_DEVICE);
-	ieee80211_free_txskb(ar->hw, msdu);
-
-	return 0;
-}
-
 void ath10k_wmi_detach(struct ath10k *ar)
 {
 	if (test_bit(ATH10K_FW_FEATURE_MGMT_TX_BY_REF,
 		     ar->running_fw->fw_file.fw_features)) {
+		struct ath10k_mgmt_tx_pkt_addr *pkt_addr;
+		unsigned long index;
+
 		spin_lock_bh(&ar->data_lock);
-		idr_for_each(&ar->wmi.mgmt_pending_tx,
-			     ath10k_wmi_mgmt_tx_clean_up_pending, ar);
-		idr_destroy(&ar->wmi.mgmt_pending_tx);
+		xa_for_each(&ar->wmi.mgmt_pending_tx, index, pkt_addr) {
+			struct sk_buff *msdu;
+
+			ath10k_dbg(ar, ATH10K_DBG_WMI,
+					"force cleanup mgmt msdu_id %lu\n",
+					index);
+
+			msdu = pkt_addr->vaddr;
+			dma_unmap_single(ar->dev, pkt_addr->paddr, msdu->len,
+					DMA_FROM_DEVICE);
+			ieee80211_free_txskb(ar->hw, msdu);
+		}
+		xa_destroy(&ar->wmi.mgmt_pending_tx);
 		spin_unlock_bh(&ar->data_lock);
 	}
 
-- 
2.23.0.rc1

[PATCH 11/38] mt76: Convert token IDR to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Straightforward conversion; locking is similar.  It may be possible to
change the GFP_ATOMIC to GFP_KERNEL, but I can't tell whether this
context permits sleeping or not.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 .../net/wireless/mediatek/mt76/mt7615/init.c  | 11 ++++-----
 .../net/wireless/mediatek/mt76/mt7615/mac.c   | 24 +++++++++----------
 .../wireless/mediatek/mt76/mt7615/mt7615.h    |  4 ++--
 3 files changed, 17 insertions(+), 22 deletions(-)

diff --git a/drivers/net/wireless/mediatek/mt76/mt7615/init.c b/drivers/net/wireless/mediatek/mt76/mt7615/init.c
index 859de2454ec6..459ccb79c9cf 100644
--- a/drivers/net/wireless/mediatek/mt76/mt7615/init.c
+++ b/drivers/net/wireless/mediatek/mt76/mt7615/init.c
@@ -71,8 +71,7 @@ static int mt7615_init_hardware(struct mt7615_dev *dev)
 
 	mt76_wr(dev, MT_INT_SOURCE_CSR, ~0);
 
-	spin_lock_init(&dev->token_lock);
-	idr_init(&dev->token);
+	xa_init_flags(&dev->token, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_BH);
 
 	ret = mt7615_eeprom_init(dev);
 	if (ret < 0)
@@ -266,21 +265,19 @@ int mt7615_register_device(struct mt7615_dev *dev)
 void mt7615_unregister_device(struct mt7615_dev *dev)
 {
 	struct mt76_txwi_cache *txwi;
-	int id;
+	unsigned long id;
 
 	mt76_unregister_device(&dev->mt76);
 	mt7615_mcu_exit(dev);
 	mt7615_dma_cleanup(dev);
 
-	spin_lock_bh(&dev->token_lock);
-	idr_for_each_entry(&dev->token, txwi, id) {
+	xa_for_each(&dev->token, id, txwi) {
 		mt7615_txp_skb_unmap(&dev->mt76, txwi);
 		if (txwi->skb)
 			dev_kfree_skb_any(txwi->skb);
 		mt76_put_txwi(&dev->mt76, txwi);
 	}
-	spin_unlock_bh(&dev->token_lock);
-	idr_destroy(&dev->token);
+	xa_destroy(&dev->token);
 
 	mt76_free_device(&dev->mt76);
 }
diff --git a/drivers/net/wireless/mediatek/mt76/mt7615/mac.c b/drivers/net/wireless/mediatek/mt76/mt7615/mac.c
index 1eb0e9c9970c..335fc3cdcb86 100644
--- a/drivers/net/wireless/mediatek/mt76/mt7615/mac.c
+++ b/drivers/net/wireless/mediatek/mt76/mt7615/mac.c
@@ -238,9 +238,7 @@ void mt7615_tx_complete_skb(struct mt76_dev *mdev, enum mt76_txq_id qid,
 		txp = (struct mt7615_txp *)(txwi_ptr + MT_TXD_SIZE);
 		dev = container_of(mdev, struct mt7615_dev, mt76);
 
-		spin_lock_bh(&dev->token_lock);
-		t = idr_remove(&dev->token, le16_to_cpu(txp->token));
-		spin_unlock_bh(&dev->token_lock);
+		t = xa_erase_bh(&dev->token, le16_to_cpu(txp->token));
 		e->skb = t ? t->skb : NULL;
 	}
 
@@ -457,7 +455,7 @@ int mt7615_tx_prepare_skb(struct mt76_dev *mdev, void *txwi_ptr,
 	struct ieee80211_tx_info *info = IEEE80211_SKB_CB(tx_info->skb);
 	struct ieee80211_key_conf *key = info->control.hw_key;
 	struct ieee80211_vif *vif = info->control.vif;
-	int i, pid, id, nbuf = tx_info->nbuf - 1;
+	int err, i, pid, id, nbuf = tx_info->nbuf - 1;
 	u8 *txwi = (u8 *)txwi_ptr;
 	struct mt76_txwi_cache *t;
 	struct mt7615_txp *txp;
@@ -506,13 +504,15 @@ int mt7615_tx_prepare_skb(struct mt76_dev *mdev, void *txwi_ptr,
 	t = (struct mt76_txwi_cache *)(txwi + mdev->drv->txwi_size);
 	t->skb = tx_info->skb;
 
-	spin_lock_bh(&dev->token_lock);
-	id = idr_alloc(&dev->token, t, 0, MT7615_TOKEN_SIZE, GFP_ATOMIC);
-	spin_unlock_bh(&dev->token_lock);
-	if (id < 0)
-		return id;
+	xa_lock_bh(&dev->token);
+	err = __xa_alloc(&dev->token, &id, t,
+			XA_LIMIT(0, MT7615_TOKEN_SIZE - 1), GFP_ATOMIC);
+	if (!err)
+		txp->token = cpu_to_le16(id);
+	xa_unlock_bh(&dev->token);
+	if (err < 0)
+		return err;
 
-	txp->token = cpu_to_le16(id);
 	txp->rept_wds_wcid = 0xff;
 	tx_info->skb = DMA_DUMMY_DATA;
 
@@ -717,9 +717,7 @@ void mt7615_mac_tx_free(struct mt7615_dev *dev, struct sk_buff *skb)
 
 	count = FIELD_GET(MT_TX_FREE_MSDU_ID_CNT, le16_to_cpu(free->ctrl));
 	for (i = 0; i < count; i++) {
-		spin_lock_bh(&dev->token_lock);
-		txwi = idr_remove(&dev->token, le16_to_cpu(free->token[i]));
-		spin_unlock_bh(&dev->token_lock);
+		txwi = xa_erase_bh(&dev->token, le16_to_cpu(free->token[i]));
 
 		if (!txwi)
 			continue;
diff --git a/drivers/net/wireless/mediatek/mt76/mt7615/mt7615.h b/drivers/net/wireless/mediatek/mt76/mt7615/mt7615.h
index f02ffcffe637..5a3ecc6faede 100644
--- a/drivers/net/wireless/mediatek/mt76/mt7615/mt7615.h
+++ b/drivers/net/wireless/mediatek/mt76/mt7615/mt7615.h
@@ -6,6 +6,7 @@
 
 #include <linux/interrupt.h>
 #include <linux/ktime.h>
+#include <linux/xarray.h>
 #include "../mt76.h"
 #include "regs.h"
 
@@ -68,8 +69,7 @@ struct mt7615_dev {
 	u32 vif_mask;
 	u32 omac_mask;
 
-	spinlock_t token_lock;
-	struct idr token;
+	struct xarray token;
 };
 
 enum {
-- 
2.23.0.rc1

[PATCH 12/38] mwifiex: Convert ack_status_frames to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Straightforward locking conversion; the only two points of note is that we
can't pass the address of the tx_token_id to xa_alloc() because it's too
small (an unsigned char), and mwifiex_free_ack_frame() becomes inlined
into its caller.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/wireless/marvell/mwifiex/init.c |  4 ++--
 drivers/net/wireless/marvell/mwifiex/main.c | 10 ++++------
 drivers/net/wireless/marvell/mwifiex/main.h |  4 +---
 drivers/net/wireless/marvell/mwifiex/txrx.c |  4 +---
 drivers/net/wireless/marvell/mwifiex/wmm.c  | 15 ++++++---------
 5 files changed, 14 insertions(+), 23 deletions(-)

diff --git a/drivers/net/wireless/marvell/mwifiex/init.c b/drivers/net/wireless/marvell/mwifiex/init.c
index 6c0e52eb8794..03e43077ae45 100644
--- a/drivers/net/wireless/marvell/mwifiex/init.c
+++ b/drivers/net/wireless/marvell/mwifiex/init.c
@@ -477,8 +477,8 @@ int mwifiex_init_lock_list(struct mwifiex_adapter *adapter)
 		spin_lock_init(&priv->tx_ba_stream_tbl_lock);
 		spin_lock_init(&priv->rx_reorder_tbl_lock);
 
-		spin_lock_init(&priv->ack_status_lock);
-		idr_init(&priv->ack_status_frames);
+		xa_init_flags(&priv->ack_status_frames,
+				XA_FLAGS_ALLOC1 | XA_FLAGS_LOCK_BH);
 	}
 
 	return 0;
diff --git a/drivers/net/wireless/marvell/mwifiex/main.c b/drivers/net/wireless/marvell/mwifiex/main.c
index a9657ae6d782..0587bd7c8a13 100644
--- a/drivers/net/wireless/marvell/mwifiex/main.c
+++ b/drivers/net/wireless/marvell/mwifiex/main.c
@@ -822,14 +822,12 @@ mwifiex_clone_skb_for_tx_status(struct mwifiex_private *priv,
 
 	skb = skb_clone(skb, GFP_ATOMIC);
 	if (skb) {
-		int id;
+		int err, id;
 
-		spin_lock_bh(&priv->ack_status_lock);
-		id = idr_alloc(&priv->ack_status_frames, orig_skb,
-			       1, 0x10, GFP_ATOMIC);
-		spin_unlock_bh(&priv->ack_status_lock);
+		err = xa_alloc_bh(&priv->ack_status_frames, &id, orig_skb,
+			       XA_LIMIT(1, 0xf), GFP_ATOMIC);
 
-		if (id >= 0) {
+		if (err == 0) {
 			tx_info = MWIFIEX_SKB_TXCB(skb);
 			tx_info->ack_frame_id = id;
 			tx_info->flags |= flag;
diff --git a/drivers/net/wireless/marvell/mwifiex/main.h b/drivers/net/wireless/marvell/mwifiex/main.h
index 095837fba300..5e06bc9d9519 100644
--- a/drivers/net/wireless/marvell/mwifiex/main.h
+++ b/drivers/net/wireless/marvell/mwifiex/main.h
@@ -682,9 +682,7 @@ struct mwifiex_private {
 	u8 check_tdls_tx;
 	struct timer_list auto_tdls_timer;
 	bool auto_tdls_timer_active;
-	struct idr ack_status_frames;
-	/* spin lock for ack status */
-	spinlock_t ack_status_lock;
+	struct xarray ack_status_frames;
 	/** rx histogram data */
 	struct mwifiex_histogram_data *hist_data;
 	struct cfg80211_chan_def dfs_chandef;
diff --git a/drivers/net/wireless/marvell/mwifiex/txrx.c b/drivers/net/wireless/marvell/mwifiex/txrx.c
index e3c1446dd847..b2ef30d9f26d 100644
--- a/drivers/net/wireless/marvell/mwifiex/txrx.c
+++ b/drivers/net/wireless/marvell/mwifiex/txrx.c
@@ -339,9 +339,7 @@ void mwifiex_parse_tx_status_event(struct mwifiex_private *priv,
 	if (!tx_status->tx_token_id)
 		return;
 
-	spin_lock_bh(&priv->ack_status_lock);
-	ack_skb = idr_remove(&priv->ack_status_frames, tx_status->tx_token_id);
-	spin_unlock_bh(&priv->ack_status_lock);
+	ack_skb = xa_erase_bh(&priv->ack_status_frames, tx_status->tx_token_id);
 
 	if (ack_skb) {
 		tx_info = MWIFIEX_SKB_TXCB(ack_skb);
diff --git a/drivers/net/wireless/marvell/mwifiex/wmm.c b/drivers/net/wireless/marvell/mwifiex/wmm.c
index 41f0231376c0..64ff6ac3889b 100644
--- a/drivers/net/wireless/marvell/mwifiex/wmm.c
+++ b/drivers/net/wireless/marvell/mwifiex/wmm.c
@@ -562,13 +562,6 @@ static void mwifiex_wmm_delete_all_ralist(struct mwifiex_private *priv)
 	}
 }
 
-static int mwifiex_free_ack_frame(int id, void *p, void *data)
-{
-	pr_warn("Have pending ack frames!\n");
-	kfree_skb(p);
-	return 0;
-}
-
 /*
  * This function cleans up the Tx and Rx queues.
  *
@@ -582,6 +575,7 @@ static int mwifiex_free_ack_frame(int id, void *p, void *data)
 void
 mwifiex_clean_txrx(struct mwifiex_private *priv)
 {
+	unsigned long index;
 	struct sk_buff *skb, *tmp;
 
 	mwifiex_11n_cleanup_reorder_tbl(priv);
@@ -612,8 +606,11 @@ mwifiex_clean_txrx(struct mwifiex_private *priv)
 	}
 	atomic_set(&priv->adapter->bypass_tx_pending, 0);
 
-	idr_for_each(&priv->ack_status_frames, mwifiex_free_ack_frame, NULL);
-	idr_destroy(&priv->ack_status_frames);
+	xa_for_each(&priv->ack_status_frames, index, skb) {
+		WARN_ONCE(1, "Have pending ack frames!\n");
+		kfree_skb(skb);
+	}
+	xa_destroy(&priv->ack_status_frames);
 }
 
 /*
-- 
2.23.0.rc1

[PATCH 13/38] ppp: Convert units_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Remove the unit_* wrappers around the IDR code; using the XArray API
directly is more clear.  I suspect the all_ppp_mutex could probably be
removed, but it probably isn't a scalability bottleneck.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/ppp/ppp_generic.c | 73 ++++++++---------------------------
 1 file changed, 16 insertions(+), 57 deletions(-)

diff --git a/drivers/net/ppp/ppp_generic.c b/drivers/net/ppp/ppp_generic.c
index a30e41a56085..1a12f30de30f 100644
--- a/drivers/net/ppp/ppp_generic.c
+++ b/drivers/net/ppp/ppp_generic.c
@@ -24,7 +24,6 @@
 #include <linux/kmod.h>
 #include <linux/init.h>
 #include <linux/list.h>
-#include <linux/idr.h>
 #include <linux/netdevice.h>
 #include <linux/poll.h>
 #include <linux/ppp_defs.h>
@@ -48,6 +47,7 @@
 #include <net/slhc_vj.h>
 #include <linux/atomic.h>
 #include <linux/refcount.h>
+#include <linux/xarray.h>
 
 #include <linux/nsproxy.h>
 #include <net/net_namespace.h>
@@ -206,7 +206,7 @@ static atomic_t channel_count = ATOMIC_INIT(0);
 static unsigned int ppp_net_id __read_mostly;
 struct ppp_net {
 	/* units to ppp mapping */
-	struct idr units_idr;
+	struct xarray units;
 
 	/*
 	 * all_ppp_mutex protects the units_idr mapping.
@@ -283,10 +283,6 @@ static struct channel *ppp_find_channel(struct ppp_net *pn, int unit);
 static int ppp_connect_channel(struct channel *pch, int unit);
 static int ppp_disconnect_channel(struct channel *pch);
 static void ppp_destroy_channel(struct channel *pch);
-static int unit_get(struct idr *p, void *ptr);
-static int unit_set(struct idr *p, void *ptr, int n);
-static void unit_put(struct idr *p, int n);
-static void *unit_find(struct idr *p, int n);
 static void ppp_setup(struct net_device *dev);
 
 static const struct net_device_ops ppp_netdev_ops;
@@ -904,7 +900,7 @@ static __net_init int ppp_init_net(struct net *net)
 {
 	struct ppp_net *pn = net_generic(net, ppp_net_id);
 
-	idr_init(&pn->units_idr);
+	xa_init_flags(&pn->units, XA_FLAGS_ALLOC);
 	mutex_init(&pn->all_ppp_mutex);
 
 	INIT_LIST_HEAD(&pn->all_channels);
@@ -922,7 +918,7 @@ static __net_exit void ppp_exit_net(struct net *net)
 	struct net_device *aux;
 	struct ppp *ppp;
 	LIST_HEAD(list);
-	int id;
+	unsigned long id;
 
 	rtnl_lock();
 	for_each_netdev_safe(net, dev, aux) {
@@ -930,7 +926,7 @@ static __net_exit void ppp_exit_net(struct net *net)
 			unregister_netdevice_queue(dev, &list);
 	}
 
-	idr_for_each_entry(&pn->units_idr, ppp, id)
+	xa_for_each(&pn->units, id, ppp)
 		/* Skip devices already unregistered by previous loop */
 		if (!net_eq(dev_net(ppp->dev), net))
 			unregister_netdevice_queue(ppp->dev, &list);
@@ -939,7 +935,6 @@ static __net_exit void ppp_exit_net(struct net *net)
 	rtnl_unlock();
 
 	mutex_destroy(&pn->all_ppp_mutex);
-	idr_destroy(&pn->units_idr);
 	WARN_ON_ONCE(!list_empty(&pn->all_channels));
 	WARN_ON_ONCE(!list_empty(&pn->new_channels));
 }
@@ -959,27 +954,25 @@ static int ppp_unit_register(struct ppp *ppp, int unit, bool ifname_is_set)
 	mutex_lock(&pn->all_ppp_mutex);
 
 	if (unit < 0) {
-		ret = unit_get(&pn->units_idr, ppp);
+		ret = xa_alloc(&pn->units, &ppp->file.index, ppp,
+				xa_limit_31b, GFP_KERNEL);
 		if (ret < 0)
 			goto err;
 	} else {
-		/* Caller asked for a specific unit number. Fail with -EEXIST
+		/*
+		 * Caller asked for a specific unit number. Fail with -EEXIST
 		 * if unavailable. For backward compatibility, return -EEXIST
-		 * too if idr allocation fails; this makes pppd retry without
-		 * requesting a specific unit number.
+		 * too if memory allocation fails; this makes pppd retry
+		 * without requesting a specific unit number.
 		 */
-		if (unit_find(&pn->units_idr, unit)) {
-			ret = -EEXIST;
-			goto err;
-		}
-		ret = unit_set(&pn->units_idr, ppp, unit);
+		ret = xa_insert(&pn->units, unit, ppp, GFP_KERNEL);
 		if (ret < 0) {
 			/* Rewrite error for backward compatibility */
 			ret = -EEXIST;
 			goto err;
 		}
+		ppp->file.index = unit;
 	}
-	ppp->file.index = ret;
 
 	if (!ifname_is_set)
 		snprintf(ppp->dev->name, IFNAMSIZ, "ppp%i", ppp->file.index);
@@ -996,7 +989,7 @@ static int ppp_unit_register(struct ppp *ppp, int unit, bool ifname_is_set)
 
 err_unit:
 	mutex_lock(&pn->all_ppp_mutex);
-	unit_put(&pn->units_idr, ppp->file.index);
+	xa_erase(&pn->units, ppp->file.index);
 err:
 	mutex_unlock(&pn->all_ppp_mutex);
 
@@ -1346,7 +1339,7 @@ static void ppp_dev_uninit(struct net_device *dev)
 	ppp_unlock(ppp);
 
 	mutex_lock(&pn->all_ppp_mutex);
-	unit_put(&pn->units_idr, ppp->file.index);
+	xa_erase(&pn->units, ppp->file.index);
 	mutex_unlock(&pn->all_ppp_mutex);
 
 	ppp->owner = NULL;
@@ -3136,7 +3129,7 @@ static void ppp_destroy_interface(struct ppp *ppp)
 static struct ppp *
 ppp_find_unit(struct ppp_net *pn, int unit)
 {
-	return unit_find(&pn->units_idr, unit);
+	return xa_load(&pn->units, unit);
 }
 
 /*
@@ -3277,40 +3270,6 @@ static void __exit ppp_cleanup(void)
 	unregister_pernet_device(&ppp_net_ops);
 }
 
-/*
- * Units handling. Caller must protect concurrent access
- * by holding all_ppp_mutex
- */
-
-/* associate pointer with specified number */
-static int unit_set(struct idr *p, void *ptr, int n)
-{
-	int unit;
-
-	unit = idr_alloc(p, ptr, n, n + 1, GFP_KERNEL);
-	if (unit == -ENOSPC)
-		unit = -EINVAL;
-	return unit;
-}
-
-/* get new free unit number and associate pointer with it */
-static int unit_get(struct idr *p, void *ptr)
-{
-	return idr_alloc(p, ptr, 0, 0, GFP_KERNEL);
-}
-
-/* put unit number back to a pool */
-static void unit_put(struct idr *p, int n)
-{
-	idr_remove(p, n);
-}
-
-/* get pointer associated with the number */
-static void *unit_find(struct idr *p, int n)
-{
-	return idr_find(p, n);
-}
-
 /* Module/initialization stuff */
 
 module_init(ppp_init);
-- 
2.23.0.rc1

[PATCH 14/38] tap: Convert minor_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

The minor_lock can be removed as the XArray contains its own spinlock.
I suspect the GFP_ATOMIC allocation could be GFP_KERNEL, but I couldn't
prove it.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 drivers/net/tap.c | 32 +++++++++++++-------------------
 1 file changed, 13 insertions(+), 19 deletions(-)

diff --git a/drivers/net/tap.c b/drivers/net/tap.c
index dd614c2cd994..81b06a21d96c 100644
--- a/drivers/net/tap.c
+++ b/drivers/net/tap.c
@@ -14,9 +14,9 @@
 #include <linux/slab.h>
 #include <linux/wait.h>
 #include <linux/cdev.h>
-#include <linux/idr.h>
 #include <linux/fs.h>
 #include <linux/uio.h>
+#include <linux/xarray.h>
 
 #include <net/net_namespace.h>
 #include <net/rtnetlink.h>
@@ -106,8 +106,7 @@ static LIST_HEAD(major_list);
 struct major_info {
 	struct rcu_head rcu;
 	dev_t major;
-	struct idr minor_idr;
-	spinlock_t minor_lock;
+	struct xarray tap_devs;
 	const char *device_name;
 	struct list_head next;
 };
@@ -414,19 +413,16 @@ int tap_get_minor(dev_t major, struct tap_dev *tap)
 		goto unlock;
 	}
 
-	spin_lock(&tap_major->minor_lock);
-	retval = idr_alloc(&tap_major->minor_idr, tap, 1, TAP_NUM_DEVS, GFP_ATOMIC);
-	if (retval >= 0) {
-		tap->minor = retval;
-	} else if (retval == -ENOSPC) {
+	retval = xa_alloc(&tap_major->tap_devs, &tap->minor, tap,
+			XA_LIMIT(0, TAP_NUM_DEVS), GFP_ATOMIC);
+	if (retval == -EBUSY) {
 		netdev_err(tap->dev, "Too many tap devices\n");
 		retval = -EINVAL;
 	}
-	spin_unlock(&tap_major->minor_lock);
 
 unlock:
 	rcu_read_unlock();
-	return retval < 0 ? retval : 0;
+	return retval;
 }
 EXPORT_SYMBOL_GPL(tap_get_minor);
 
@@ -440,12 +436,12 @@ void tap_free_minor(dev_t major, struct tap_dev *tap)
 		goto unlock;
 	}
 
-	spin_lock(&tap_major->minor_lock);
+	xa_lock(&tap_major->tap_devs);
 	if (tap->minor) {
-		idr_remove(&tap_major->minor_idr, tap->minor);
+		__xa_erase(&tap_major->tap_devs, tap->minor);
 		tap->minor = 0;
 	}
-	spin_unlock(&tap_major->minor_lock);
+	xa_unlock(&tap_major->tap_devs);
 
 unlock:
 	rcu_read_unlock();
@@ -465,13 +461,13 @@ static struct tap_dev *dev_get_by_tap_file(int major, int minor)
 		goto unlock;
 	}
 
-	spin_lock(&tap_major->minor_lock);
-	tap = idr_find(&tap_major->minor_idr, minor);
+	xa_lock(&tap_major->tap_devs);
+	tap = xa_load(&tap_major->tap_devs, minor);
 	if (tap) {
 		dev = tap->dev;
 		dev_hold(dev);
 	}
-	spin_unlock(&tap_major->minor_lock);
+	xa_unlock(&tap_major->tap_devs);
 
 unlock:
 	rcu_read_unlock();
@@ -1322,8 +1318,7 @@ static int tap_list_add(dev_t major, const char *device_name)
 
 	tap_major->major = MAJOR(major);
 
-	idr_init(&tap_major->minor_idr);
-	spin_lock_init(&tap_major->minor_lock);
+	xa_init_flags(&tap_major->tap_devs, XA_FLAGS_ALLOC1);
 
 	tap_major->device_name = device_name;
 
@@ -1369,7 +1364,6 @@ void tap_destroy_cdev(dev_t major, struct cdev *tap_cdev)
 	unregister_chrdev_region(major, TAP_NUM_DEVS);
 	list_for_each_entry_safe(tap_major, tmp, &major_list, next) {
 		if (tap_major->major == MAJOR(major)) {
-			idr_destroy(&tap_major->minor_idr);
 			list_del_rcu(&tap_major->next);
 			kfree_rcu(tap_major, rcu);
 		}
-- 
2.23.0.rc1

[PATCH 15/38] nfp: Convert internal ports to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Since nfp_fl_internal_ports was only an IDR and the lock to protect it,
replace the entire data structure with an XArray (which has an embedded
lock).

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 .../net/ethernet/netronome/nfp/flower/main.c  | 44 +++++++------------
 .../net/ethernet/netronome/nfp/flower/main.h  | 12 +----
 2 files changed, 17 insertions(+), 39 deletions(-)

diff --git a/drivers/net/ethernet/netronome/nfp/flower/main.c b/drivers/net/ethernet/netronome/nfp/flower/main.c
index 7a20447cca19..706ae41645f5 100644
--- a/drivers/net/ethernet/netronome/nfp/flower/main.c
+++ b/drivers/net/ethernet/netronome/nfp/flower/main.c
@@ -40,35 +40,31 @@ nfp_flower_lookup_internal_port_id(struct nfp_flower_priv *priv,
 				   struct net_device *netdev)
 {
 	struct net_device *entry;
-	int i, id = 0;
+	unsigned long i;
 
-	rcu_read_lock();
-	idr_for_each_entry(&priv->internal_ports.port_ids, entry, i)
-		if (entry == netdev) {
-			id = i;
-			break;
-		}
-	rcu_read_unlock();
+	xa_for_each(&priv->internal_ports, i, entry) {
+		if (entry == netdev)
+			return i;
+	}
 
-	return id;
+	return 0;
 }
 
 static int
 nfp_flower_get_internal_port_id(struct nfp_app *app, struct net_device *netdev)
 {
 	struct nfp_flower_priv *priv = app->priv;
-	int id;
+	int err, id;
 
 	id = nfp_flower_lookup_internal_port_id(priv, netdev);
 	if (id > 0)
 		return id;
 
-	idr_preload(GFP_ATOMIC);
-	spin_lock_bh(&priv->internal_ports.lock);
-	id = idr_alloc(&priv->internal_ports.port_ids, netdev,
-		       NFP_MIN_INT_PORT_ID, NFP_MAX_INT_PORT_ID, GFP_ATOMIC);
-	spin_unlock_bh(&priv->internal_ports.lock);
-	idr_preload_end();
+	err = xa_alloc_bh(&priv->internal_ports, &id, netdev,
+		       XA_LIMIT(NFP_MIN_INT_PORT_ID, NFP_MAX_INT_PORT_ID),
+		       GFP_ATOMIC);
+	if (err < 0)
+		return err;
 
 	return id;
 }
@@ -95,13 +91,8 @@ static struct net_device *
 nfp_flower_get_netdev_from_internal_port_id(struct nfp_app *app, int port_id)
 {
 	struct nfp_flower_priv *priv = app->priv;
-	struct net_device *netdev;
-
-	rcu_read_lock();
-	netdev = idr_find(&priv->internal_ports.port_ids, port_id);
-	rcu_read_unlock();
 
-	return netdev;
+	return xa_load(&priv->internal_ports, port_id);
 }
 
 static void
@@ -114,9 +105,7 @@ nfp_flower_free_internal_port_id(struct nfp_app *app, struct net_device *netdev)
 	if (!id)
 		return;
 
-	spin_lock_bh(&priv->internal_ports.lock);
-	idr_remove(&priv->internal_ports.port_ids, id);
-	spin_unlock_bh(&priv->internal_ports.lock);
+	xa_erase_bh(&priv->internal_ports, id);
 }
 
 static int
@@ -133,13 +122,12 @@ nfp_flower_internal_port_event_handler(struct nfp_app *app,
 
 static void nfp_flower_internal_port_init(struct nfp_flower_priv *priv)
 {
-	spin_lock_init(&priv->internal_ports.lock);
-	idr_init(&priv->internal_ports.port_ids);
+	xa_init_flags(&priv->internal_ports, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_BH);
 }
 
 static void nfp_flower_internal_port_cleanup(struct nfp_flower_priv *priv)
 {
-	idr_destroy(&priv->internal_ports.port_ids);
+	xa_destroy(&priv->internal_ports);
 }
 
 static struct nfp_flower_non_repr_priv *
diff --git a/drivers/net/ethernet/netronome/nfp/flower/main.h b/drivers/net/ethernet/netronome/nfp/flower/main.h
index 31d94592a7c0..735e995ae740 100644
--- a/drivers/net/ethernet/netronome/nfp/flower/main.h
+++ b/drivers/net/ethernet/netronome/nfp/flower/main.h
@@ -119,16 +119,6 @@ struct nfp_fl_lag {
 	struct sk_buff_head retrans_skbs;
 };
 
-/**
- * struct nfp_fl_internal_ports - Flower APP priv data for additional ports
- * @port_ids:	Assignment of ids to any additional ports
- * @lock:	Lock for extra ports list
- */
-struct nfp_fl_internal_ports {
-	struct idr port_ids;
-	spinlock_t lock;
-};
-
 /**
  * struct nfp_flower_priv - Flower APP per-vNIC priv data
  * @app:		Back pointer to app
@@ -191,7 +181,7 @@ struct nfp_flower_priv {
 	struct list_head non_repr_priv;
 	unsigned int active_mem_unit;
 	unsigned int total_mem_units;
-	struct nfp_fl_internal_ports internal_ports;
+	struct xarray internal_ports;
 	struct delayed_work qos_stats_work;
 	unsigned int qos_rate_limiters;
 	spinlock_t qos_stats_lock; /* Protect the qos stats */
-- 
2.23.0.rc1

[PATCH 16/38] qrtr: Convert qrtr_nodes to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Moved the kref protection under the xa_lock too.  It's a little
disconcerting to not be checking the error code from xa_store(),
but the original code doesn't return an errno from qrtr_node_assign()
and that would be a larger change to the driver than I'm conmfortable
making.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/qrtr/qrtr.c | 23 ++++++++++++-----------
 1 file changed, 12 insertions(+), 11 deletions(-)

diff --git a/net/qrtr/qrtr.c b/net/qrtr/qrtr.c
index 6c8b0f6d28f9..e02fa6be76d2 100644
--- a/net/qrtr/qrtr.c
+++ b/net/qrtr/qrtr.c
@@ -97,10 +97,10 @@ static inline struct qrtr_sock *qrtr_sk(struct sock *sk)
 static unsigned int qrtr_local_nid = NUMA_NO_NODE;
 
 /* for node ids */
-static RADIX_TREE(qrtr_nodes, GFP_KERNEL);
+static DEFINE_XARRAY(qrtr_nodes);
 /* broadcast list */
 static LIST_HEAD(qrtr_all_nodes);
-/* lock for qrtr_nodes, qrtr_all_nodes and node reference */
+/* lock for qrtr_all_nodes */
 static DEFINE_MUTEX(qrtr_node_lock);
 
 /* local port allocation management */
@@ -138,15 +138,18 @@ static int qrtr_bcast_enqueue(struct qrtr_node *node, struct sk_buff *skb,
 /* Release node resources and free the node.
  *
  * Do not call directly, use qrtr_node_release.  To be used with
- * kref_put_mutex.  As such, the node mutex is expected to be locked on call.
+ * kref_put_lock.  As such, the xa_lock is expected to be held on call.
  */
 static void __qrtr_node_release(struct kref *kref)
+		__releases(qrtr_nodes.xa_lock)
 {
 	struct qrtr_node *node = container_of(kref, struct qrtr_node, ref);
 
 	if (node->nid != QRTR_EP_NID_AUTO)
-		radix_tree_delete(&qrtr_nodes, node->nid);
+		__xa_erase(&qrtr_nodes, node->nid);
+	xa_unlock(&qrtr_nodes);
 
+	mutex_lock(&qrtr_node_lock);
 	list_del(&node->item);
 	mutex_unlock(&qrtr_node_lock);
 
@@ -167,7 +170,7 @@ static void qrtr_node_release(struct qrtr_node *node)
 {
 	if (!node)
 		return;
-	kref_put_mutex(&node->ref, __qrtr_node_release, &qrtr_node_lock);
+	kref_put_lock(&node->ref, __qrtr_node_release, &qrtr_nodes.xa_lock);
 }
 
 /* Pass an outgoing packet socket buffer to the endpoint driver. */
@@ -215,10 +218,10 @@ static struct qrtr_node *qrtr_node_lookup(unsigned int nid)
 {
 	struct qrtr_node *node;
 
-	mutex_lock(&qrtr_node_lock);
-	node = radix_tree_lookup(&qrtr_nodes, nid);
+	xa_lock(&qrtr_nodes);
+	node = xa_load(&qrtr_nodes, nid);
 	node = qrtr_node_acquire(node);
-	mutex_unlock(&qrtr_node_lock);
+	xa_unlock(&qrtr_nodes);
 
 	return node;
 }
@@ -233,10 +236,8 @@ static void qrtr_node_assign(struct qrtr_node *node, unsigned int nid)
 	if (node->nid != QRTR_EP_NID_AUTO || nid == QRTR_EP_NID_AUTO)
 		return;
 
-	mutex_lock(&qrtr_node_lock);
-	radix_tree_insert(&qrtr_nodes, nid, node);
 	node->nid = nid;
-	mutex_unlock(&qrtr_node_lock);
+	xa_store(&qrtr_nodes, nid, node, GFP_KERNEL);
 }
 
 /**
-- 
2.23.0.rc1

[PATCH 17/38] qrtr: Convert qrtr_ports to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Replace the qrtr_port_lock mutex with the XArray internal spinlock.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/qrtr/qrtr.c | 43 +++++++++++++++----------------------------
 1 file changed, 15 insertions(+), 28 deletions(-)

diff --git a/net/qrtr/qrtr.c b/net/qrtr/qrtr.c
index e02fa6be76d2..fdbc20442a93 100644
--- a/net/qrtr/qrtr.c
+++ b/net/qrtr/qrtr.c
@@ -104,8 +104,7 @@ static LIST_HEAD(qrtr_all_nodes);
 static DEFINE_MUTEX(qrtr_node_lock);
 
 /* local port allocation management */
-static DEFINE_IDR(qrtr_ports);
-static DEFINE_MUTEX(qrtr_port_lock);
+static DEFINE_XARRAY_ALLOC(qrtr_ports);
 
 /**
  * struct qrtr_node - endpoint node
@@ -483,11 +482,11 @@ static struct qrtr_sock *qrtr_port_lookup(int port)
 	if (port == QRTR_PORT_CTRL)
 		port = 0;
 
-	mutex_lock(&qrtr_port_lock);
-	ipc = idr_find(&qrtr_ports, port);
+	xa_lock(&qrtr_ports);
+	ipc = xa_load(&qrtr_ports, port);
 	if (ipc)
 		sock_hold(&ipc->sk);
-	mutex_unlock(&qrtr_port_lock);
+	xa_unlock(&qrtr_ports);
 
 	return ipc;
 }
@@ -526,9 +525,7 @@ static void qrtr_port_remove(struct qrtr_sock *ipc)
 
 	__sock_put(&ipc->sk);
 
-	mutex_lock(&qrtr_port_lock);
-	idr_remove(&qrtr_ports, port);
-	mutex_unlock(&qrtr_port_lock);
+	xa_erase(&qrtr_ports, port);
 }
 
 /* Assign port number to socket.
@@ -545,25 +542,19 @@ static int qrtr_port_assign(struct qrtr_sock *ipc, int *port)
 {
 	int rc;
 
-	mutex_lock(&qrtr_port_lock);
 	if (!*port) {
-		rc = idr_alloc(&qrtr_ports, ipc,
-			       QRTR_MIN_EPH_SOCKET, QRTR_MAX_EPH_SOCKET + 1,
-			       GFP_ATOMIC);
-		if (rc >= 0)
-			*port = rc;
+		rc = xa_alloc(&qrtr_ports, port, ipc,
+				XA_LIMIT(QRTR_MIN_EPH_SOCKET,
+					QRTR_MAX_EPH_SOCKET), GFP_KERNEL);
 	} else if (*port < QRTR_MIN_EPH_SOCKET && !capable(CAP_NET_ADMIN)) {
 		rc = -EACCES;
 	} else if (*port == QRTR_PORT_CTRL) {
-		rc = idr_alloc(&qrtr_ports, ipc, 0, 1, GFP_ATOMIC);
+		rc = xa_insert(&qrtr_ports, 0, ipc, GFP_KERNEL);
 	} else {
-		rc = idr_alloc(&qrtr_ports, ipc, *port, *port + 1, GFP_ATOMIC);
-		if (rc >= 0)
-			*port = rc;
+		rc = xa_insert(&qrtr_ports, *port, ipc, GFP_KERNEL);
 	}
-	mutex_unlock(&qrtr_port_lock);
 
-	if (rc == -ENOSPC)
+	if (rc == -EBUSY)
 		return -EADDRINUSE;
 	else if (rc < 0)
 		return rc;
@@ -577,20 +568,16 @@ static int qrtr_port_assign(struct qrtr_sock *ipc, int *port)
 static void qrtr_reset_ports(void)
 {
 	struct qrtr_sock *ipc;
-	int id;
-
-	mutex_lock(&qrtr_port_lock);
-	idr_for_each_entry(&qrtr_ports, ipc, id) {
-		/* Don't reset control port */
-		if (id == 0)
-			continue;
+	unsigned long id;
 
+	xa_lock(&qrtr_ports);
+	xa_for_each_start(&qrtr_ports, id, ipc, 1) {
 		sock_hold(&ipc->sk);
 		ipc->sk.sk_err = ENETRESET;
 		ipc->sk.sk_error_report(&ipc->sk);
 		sock_put(&ipc->sk);
 	}
-	mutex_unlock(&qrtr_port_lock);
+	xa_unlock(&qrtr_ports);
 }
 
 /* Bind socket to address.
-- 
2.23.0.rc1

[PATCH 18/38] rxrpc: Convert to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

The XArray requires a separate cursor, but embeds the lock, so it's
a minor saving.  Also, there's no need to preload.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/rxrpc/af_rxrpc.c    |  2 +-
 net/rxrpc/ar-internal.h |  3 ++-
 net/rxrpc/conn_client.c | 49 +++++++++++++++--------------------------
 net/rxrpc/conn_object.c |  2 +-
 4 files changed, 22 insertions(+), 34 deletions(-)

diff --git a/net/rxrpc/af_rxrpc.c b/net/rxrpc/af_rxrpc.c
index d09eaf153544..16e289bbc825 100644
--- a/net/rxrpc/af_rxrpc.c
+++ b/net/rxrpc/af_rxrpc.c
@@ -981,7 +981,7 @@ static int __init af_rxrpc_init(void)
 	tmp &= 0x3fffffff;
 	if (tmp == 0)
 		tmp = 1;
-	idr_set_cursor(&rxrpc_client_conn_ids, tmp);
+	rxrpc_client_conn_next = tmp;
 
 	ret = -ENOMEM;
 	rxrpc_call_jar = kmem_cache_create(
diff --git a/net/rxrpc/ar-internal.h b/net/rxrpc/ar-internal.h
index 63b26baa108a..7721448aa7a4 100644
--- a/net/rxrpc/ar-internal.h
+++ b/net/rxrpc/ar-internal.h
@@ -898,7 +898,8 @@ extern unsigned int rxrpc_max_client_connections;
 extern unsigned int rxrpc_reap_client_connections;
 extern unsigned long rxrpc_conn_idle_client_expiry;
 extern unsigned long rxrpc_conn_idle_client_fast_expiry;
-extern struct idr rxrpc_client_conn_ids;
+extern struct xarray rxrpc_client_conn_ids;
+extern u32 rxrpc_client_conn_next;
 
 void rxrpc_destroy_client_conn_ids(void);
 int rxrpc_connect_call(struct rxrpc_sock *, struct rxrpc_call *,
diff --git a/net/rxrpc/conn_client.c b/net/rxrpc/conn_client.c
index aea82f909c60..d967de7a5eb9 100644
--- a/net/rxrpc/conn_client.c
+++ b/net/rxrpc/conn_client.c
@@ -72,7 +72,7 @@
 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
 
 #include <linux/slab.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 #include <linux/timer.h>
 #include <linux/sched/signal.h>
 
@@ -86,14 +86,14 @@ __read_mostly unsigned long rxrpc_conn_idle_client_fast_expiry = 2 * HZ;
 /*
  * We use machine-unique IDs for our client connections.
  */
-DEFINE_IDR(rxrpc_client_conn_ids);
-static DEFINE_SPINLOCK(rxrpc_conn_id_lock);
+DEFINE_XARRAY_ALLOC1(rxrpc_client_conn_ids);
+u32 rxrpc_client_conn_next;
 
 static void rxrpc_cull_active_client_conns(struct rxrpc_net *);
 
 /*
  * Get a connection ID and epoch for a client connection from the global pool.
- * The connection struct pointer is then recorded in the idr radix tree.  The
+ * The connection struct pointer is then recorded in the XArray.  The
  * epoch doesn't change until the client is rebooted (or, at least, unless the
  * module is unloaded).
  */
@@ -101,21 +101,15 @@ static int rxrpc_get_client_connection_id(struct rxrpc_connection *conn,
 					  gfp_t gfp)
 {
 	struct rxrpc_net *rxnet = conn->params.local->rxnet;
-	int id;
+	int err, id;
 
 	_enter("");
 
-	idr_preload(gfp);
-	spin_lock(&rxrpc_conn_id_lock);
-
-	id = idr_alloc_cyclic(&rxrpc_client_conn_ids, conn,
-			      1, 0x40000000, GFP_NOWAIT);
-	if (id < 0)
+	err = xa_alloc_cyclic(&rxrpc_client_conn_ids, &id, conn,
+			XA_LIMIT(1, 0x40000000), &rxrpc_client_conn_next, gfp);
+	if (err < 0)
 		goto error;
 
-	spin_unlock(&rxrpc_conn_id_lock);
-	idr_preload_end();
-
 	conn->proto.epoch = rxnet->epoch;
 	conn->proto.cid = id << RXRPC_CIDSHIFT;
 	set_bit(RXRPC_CONN_HAS_IDR, &conn->flags);
@@ -123,10 +117,8 @@ static int rxrpc_get_client_connection_id(struct rxrpc_connection *conn,
 	return 0;
 
 error:
-	spin_unlock(&rxrpc_conn_id_lock);
-	idr_preload_end();
-	_leave(" = %d", id);
-	return id;
+	_leave(" = %d", err);
+	return err;
 }
 
 /*
@@ -135,30 +127,26 @@ static int rxrpc_get_client_connection_id(struct rxrpc_connection *conn,
 static void rxrpc_put_client_connection_id(struct rxrpc_connection *conn)
 {
 	if (test_bit(RXRPC_CONN_HAS_IDR, &conn->flags)) {
-		spin_lock(&rxrpc_conn_id_lock);
-		idr_remove(&rxrpc_client_conn_ids,
+		xa_erase(&rxrpc_client_conn_ids,
 			   conn->proto.cid >> RXRPC_CIDSHIFT);
-		spin_unlock(&rxrpc_conn_id_lock);
 	}
 }
 
 /*
- * Destroy the client connection ID tree.
+ * There should be no outstanding client connections.
  */
 void rxrpc_destroy_client_conn_ids(void)
 {
-	struct rxrpc_connection *conn;
-	int id;
+	if (!xa_empty(&rxrpc_client_conn_ids)) {
+		struct rxrpc_connection *conn;
+		unsigned long id;
 
-	if (!idr_is_empty(&rxrpc_client_conn_ids)) {
-		idr_for_each_entry(&rxrpc_client_conn_ids, conn, id) {
+		xa_for_each(&rxrpc_client_conn_ids, id, conn) {
 			pr_err("AF_RXRPC: Leaked client conn %p {%d}\n",
 			       conn, atomic_read(&conn->usage));
 		}
 		BUG();
 	}
-
-	idr_destroy(&rxrpc_client_conn_ids);
 }
 
 /*
@@ -234,7 +222,7 @@ rxrpc_alloc_client_connection(struct rxrpc_conn_parameters *cp, gfp_t gfp)
 static bool rxrpc_may_reuse_conn(struct rxrpc_connection *conn)
 {
 	struct rxrpc_net *rxnet = conn->params.local->rxnet;
-	int id_cursor, id, distance, limit;
+	int id, distance, limit;
 
 	if (test_bit(RXRPC_CONN_DONT_REUSE, &conn->flags))
 		goto dont_reuse;
@@ -248,9 +236,8 @@ static bool rxrpc_may_reuse_conn(struct rxrpc_connection *conn)
 	 * times the maximum number of client conns away from the current
 	 * allocation point to try and keep the IDs concentrated.
 	 */
-	id_cursor = idr_get_cursor(&rxrpc_client_conn_ids);
 	id = conn->proto.cid >> RXRPC_CIDSHIFT;
-	distance = id - id_cursor;
+	distance = id - rxrpc_client_conn_next;
 	if (distance < 0)
 		distance = -distance;
 	limit = max(rxrpc_max_client_connections * 4, 1024U);
diff --git a/net/rxrpc/conn_object.c b/net/rxrpc/conn_object.c
index 434ef392212b..31eef9c2a9ac 100644
--- a/net/rxrpc/conn_object.c
+++ b/net/rxrpc/conn_object.c
@@ -115,7 +115,7 @@ struct rxrpc_connection *rxrpc_find_connection_rcu(struct rxrpc_local *local,
 		/* Look up client connections by connection ID alone as their
 		 * IDs are unique for this machine.
 		 */
-		conn = idr_find(&rxrpc_client_conn_ids,
+		conn = xa_load(&rxrpc_client_conn_ids,
 				sp->hdr.cid >> RXRPC_CIDSHIFT);
 		if (!conn || atomic_read(&conn->usage) == 0) {
 			_debug("no conn");
-- 
2.23.0.rc1

[PATCH 19/38] 9p: Convert reqs IDR to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Use the xarray spinlock instead of the client spinlock.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/net/9p/client.h |  2 +-
 net/9p/client.c         | 41 ++++++++++++++++++++---------------------
 2 files changed, 21 insertions(+), 22 deletions(-)

diff --git a/include/net/9p/client.h b/include/net/9p/client.h
index acc60d8a3b3b..6fe36ca0c32e 100644
--- a/include/net/9p/client.h
+++ b/include/net/9p/client.h
@@ -124,7 +124,7 @@ struct p9_client {
 	} trans_opts;
 
 	struct idr fids;
-	struct idr reqs;
+	struct xarray reqs;
 
 	char name[__NEW_UTS_LEN + 1];
 };
diff --git a/net/9p/client.c b/net/9p/client.c
index 9622f3e469f6..5c566e48f63e 100644
--- a/net/9p/client.c
+++ b/net/9p/client.c
@@ -269,7 +269,8 @@ p9_tag_alloc(struct p9_client *c, int8_t type, unsigned int max_size)
 {
 	struct p9_req_t *req = kmem_cache_alloc(p9_req_cache, GFP_NOFS);
 	int alloc_msize = min(c->msize, max_size);
-	int tag;
+	int err;
+	u32 tag;
 
 	if (!req)
 		return ERR_PTR(-ENOMEM);
@@ -285,17 +286,17 @@ p9_tag_alloc(struct p9_client *c, int8_t type, unsigned int max_size)
 	init_waitqueue_head(&req->wq);
 	INIT_LIST_HEAD(&req->req_list);
 
-	idr_preload(GFP_NOFS);
-	spin_lock_irq(&c->lock);
-	if (type == P9_TVERSION)
-		tag = idr_alloc(&c->reqs, req, P9_NOTAG, P9_NOTAG + 1,
-				GFP_NOWAIT);
-	else
-		tag = idr_alloc(&c->reqs, req, 0, P9_NOTAG, GFP_NOWAIT);
+	xa_lock_irq(&c->reqs);
+	if (type == P9_TVERSION) {
+		tag = P9_NOTAG;
+		err = __xa_insert(&c->reqs, P9_NOTAG, req, GFP_NOFS);
+	} else {
+		err = __xa_alloc(&c->reqs, &tag, req, XA_LIMIT(0, P9_NOTAG - 1),
+				GFP_NOFS);
+	}
 	req->tc.tag = tag;
-	spin_unlock_irq(&c->lock);
-	idr_preload_end();
-	if (tag < 0)
+	xa_unlock_irq(&c->reqs);
+	if (err < 0)
 		goto free;
 
 	/* Init ref to two because in the general case there is one ref
@@ -334,7 +335,7 @@ struct p9_req_t *p9_tag_lookup(struct p9_client *c, u16 tag)
 
 	rcu_read_lock();
 again:
-	req = idr_find(&c->reqs, tag);
+	req = xa_load(&c->reqs, tag);
 	if (req) {
 		/* We have to be careful with the req found under rcu_read_lock
 		 * Thanks to SLAB_TYPESAFE_BY_RCU we can safely try to get the
@@ -367,9 +368,9 @@ static int p9_tag_remove(struct p9_client *c, struct p9_req_t *r)
 	u16 tag = r->tc.tag;
 
 	p9_debug(P9_DEBUG_MUX, "clnt %p req %p tag: %d\n", c, r, tag);
-	spin_lock_irqsave(&c->lock, flags);
-	idr_remove(&c->reqs, tag);
-	spin_unlock_irqrestore(&c->lock, flags);
+	xa_lock_irqsave(&c->reqs, flags);
+	__xa_erase(&c->reqs, tag);
+	xa_unlock_irqrestore(&c->reqs, flags);
 	return p9_req_put(r);
 }
 
@@ -397,16 +398,14 @@ EXPORT_SYMBOL(p9_req_put);
 static void p9_tag_cleanup(struct p9_client *c)
 {
 	struct p9_req_t *req;
-	int id;
+	unsigned long id;
 
-	rcu_read_lock();
-	idr_for_each_entry(&c->reqs, req, id) {
-		pr_info("Tag %d still in use\n", id);
+	xa_for_each(&c->reqs, id, req) {
+		pr_info("Tag %ld still in use\n", id);
 		if (p9_tag_remove(c, req) == 0)
 			pr_warn("Packet with tag %d has still references",
 				req->tc.tag);
 	}
-	rcu_read_unlock();
 }
 
 /**
@@ -1016,7 +1015,7 @@ struct p9_client *p9_client_create(const char *dev_name, char *options)
 
 	spin_lock_init(&clnt->lock);
 	idr_init(&clnt->fids);
-	idr_init(&clnt->reqs);
+	xa_init_flags(&clnt->reqs, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
 
 	err = parse_opts(options, clnt);
 	if (err < 0)
-- 
2.23.0.rc1

[PATCH 20/38] 9p: Convert fids IDR to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Locking changes to use the internal XArray spinlock instead of the
client spinlock.  Also remove all references to the IDR header file
and a dangling define of P9_ROW_MAXTAG.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/net/9p/client.h |  7 ++-----
 net/9p/client.c         | 23 ++++++++---------------
 net/9p/trans_fd.c       |  1 -
 net/9p/trans_rdma.c     |  1 -
 net/9p/trans_virtio.c   |  1 -
 5 files changed, 10 insertions(+), 23 deletions(-)

diff --git a/include/net/9p/client.h b/include/net/9p/client.h
index 6fe36ca0c32e..a50f98cff203 100644
--- a/include/net/9p/client.h
+++ b/include/net/9p/client.h
@@ -12,10 +12,7 @@
 #define NET_9P_CLIENT_H
 
 #include <linux/utsname.h>
-#include <linux/idr.h>
-
-/* Number of requests per row */
-#define P9_ROW_MAXTAG 255
+#include <linux/xarray.h>
 
 /** enum p9_proto_versions - 9P protocol versions
  * @p9_proto_legacy: 9P Legacy mode, pre-9P2000.u
@@ -123,7 +120,7 @@ struct p9_client {
 		} tcp;
 	} trans_opts;
 
-	struct idr fids;
+	struct xarray fids;
 	struct xarray reqs;
 
 	char name[__NEW_UTS_LEN + 1];
diff --git a/net/9p/client.c b/net/9p/client.c
index 5c566e48f63e..ca7bd0949ebb 100644
--- a/net/9p/client.c
+++ b/net/9p/client.c
@@ -14,7 +14,6 @@
 #include <linux/errno.h>
 #include <linux/fs.h>
 #include <linux/poll.h>
-#include <linux/idr.h>
 #include <linux/mutex.h>
 #include <linux/slab.h>
 #include <linux/sched/signal.h>
@@ -898,15 +897,9 @@ static struct p9_fid *p9_fid_create(struct p9_client *clnt)
 	fid->uid = current_fsuid();
 	fid->clnt = clnt;
 	fid->rdir = NULL;
-	fid->fid = 0;
-
-	idr_preload(GFP_KERNEL);
-	spin_lock_irq(&clnt->lock);
-	ret = idr_alloc_u32(&clnt->fids, fid, &fid->fid, P9_NOFID - 1,
-			    GFP_NOWAIT);
-	spin_unlock_irq(&clnt->lock);
-	idr_preload_end();
 
+	ret = xa_alloc_irq(&clnt->fids, &fid->fid, fid,
+				XA_LIMIT(0, P9_NOFID - 1), GFP_KERNEL);
 	if (!ret)
 		return fid;
 
@@ -921,9 +914,9 @@ static void p9_fid_destroy(struct p9_fid *fid)
 
 	p9_debug(P9_DEBUG_FID, "fid %d\n", fid->fid);
 	clnt = fid->clnt;
-	spin_lock_irqsave(&clnt->lock, flags);
-	idr_remove(&clnt->fids, fid->fid);
-	spin_unlock_irqrestore(&clnt->lock, flags);
+	xa_lock_irqsave(&clnt->fids, flags);
+	__xa_erase(&clnt->fids, fid->fid);
+	xa_unlock_irqrestore(&clnt->fids, flags);
 	kfree(fid->rdir);
 	kfree(fid);
 }
@@ -1014,7 +1007,7 @@ struct p9_client *p9_client_create(const char *dev_name, char *options)
 	memcpy(clnt->name, client_id, strlen(client_id) + 1);
 
 	spin_lock_init(&clnt->lock);
-	idr_init(&clnt->fids);
+	xa_init_flags(&clnt->fids, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
 	xa_init_flags(&clnt->reqs, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
 
 	err = parse_opts(options, clnt);
@@ -1076,7 +1069,7 @@ EXPORT_SYMBOL(p9_client_create);
 void p9_client_destroy(struct p9_client *clnt)
 {
 	struct p9_fid *fid;
-	int id;
+	unsigned long id;
 
 	p9_debug(P9_DEBUG_MUX, "clnt %p\n", clnt);
 
@@ -1085,7 +1078,7 @@ void p9_client_destroy(struct p9_client *clnt)
 
 	v9fs_put_trans(clnt->trans_mod);
 
-	idr_for_each_entry(&clnt->fids, fid, id) {
+	xa_for_each(&clnt->fids, id, fid) {
 		pr_info("Found fid %d not clunked\n", fid->fid);
 		p9_fid_destroy(fid);
 	}
diff --git a/net/9p/trans_fd.c b/net/9p/trans_fd.c
index 13cd683a658a..05fa9cb2897e 100644
--- a/net/9p/trans_fd.c
+++ b/net/9p/trans_fd.c
@@ -22,7 +22,6 @@
 #include <linux/un.h>
 #include <linux/uaccess.h>
 #include <linux/inet.h>
-#include <linux/idr.h>
 #include <linux/file.h>
 #include <linux/parser.h>
 #include <linux/slab.h>
diff --git a/net/9p/trans_rdma.c b/net/9p/trans_rdma.c
index bac8dad5dd69..935f9464da6e 100644
--- a/net/9p/trans_rdma.c
+++ b/net/9p/trans_rdma.c
@@ -23,7 +23,6 @@
 #include <linux/un.h>
 #include <linux/uaccess.h>
 #include <linux/inet.h>
-#include <linux/idr.h>
 #include <linux/file.h>
 #include <linux/parser.h>
 #include <linux/semaphore.h>
diff --git a/net/9p/trans_virtio.c b/net/9p/trans_virtio.c
index a3cd90a74012..947a85f87f22 100644
--- a/net/9p/trans_virtio.c
+++ b/net/9p/trans_virtio.c
@@ -22,7 +22,6 @@
 #include <linux/un.h>
 #include <linux/uaccess.h>
 #include <linux/inet.h>
-#include <linux/idr.h>
 #include <linux/file.h>
 #include <linux/highmem.h>
 #include <linux/slab.h>
-- 
2.23.0.rc1

[PATCH 21/38] 9p: Move lock from client to trans_fd

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

The trans_fd back end is now the only transport using the client
spinlock so move it into the transport connection.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/net/9p/client.h |  2 --
 net/9p/client.c         |  1 -
 net/9p/trans_fd.c       | 36 +++++++++++++++++++++---------------
 3 files changed, 21 insertions(+), 18 deletions(-)

diff --git a/include/net/9p/client.h b/include/net/9p/client.h
index a50f98cff203..0ff697676d00 100644
--- a/include/net/9p/client.h
+++ b/include/net/9p/client.h
@@ -86,7 +86,6 @@ struct p9_req_t {
 
 /**
  * struct p9_client - per client instance state
- * @lock: protect @fids and @reqs
  * @msize: maximum data size negotiated by protocol
  * @proto_version: 9P protocol version to use
  * @trans_mod: module API instantiated with this client
@@ -100,7 +99,6 @@ struct p9_req_t {
  * state that has been instantiated.
  */
 struct p9_client {
-	spinlock_t lock;
 	unsigned int msize;
 	unsigned char proto_version;
 	struct p9_trans_module *trans_mod;
diff --git a/net/9p/client.c b/net/9p/client.c
index ca7bd0949ebb..1b419fcc5033 100644
--- a/net/9p/client.c
+++ b/net/9p/client.c
@@ -1006,7 +1006,6 @@ struct p9_client *p9_client_create(const char *dev_name, char *options)
 	client_id = utsname()->nodename;
 	memcpy(clnt->name, client_id, strlen(client_id) + 1);
 
-	spin_lock_init(&clnt->lock);
 	xa_init_flags(&clnt->fids, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
 	xa_init_flags(&clnt->reqs, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_IRQ);
 
diff --git a/net/9p/trans_fd.c b/net/9p/trans_fd.c
index 05fa9cb2897e..74d946e02cf9 100644
--- a/net/9p/trans_fd.c
+++ b/net/9p/trans_fd.c
@@ -112,6 +112,7 @@ struct p9_poll_wait {
 struct p9_conn {
 	struct list_head mux_list;
 	struct p9_client *client;
+	spinlock_t lock;
 	int err;
 	struct list_head req_list;
 	struct list_head unsent_req_list;
@@ -188,10 +189,10 @@ static void p9_conn_cancel(struct p9_conn *m, int err)
 
 	p9_debug(P9_DEBUG_ERROR, "mux %p err %d\n", m, err);
 
-	spin_lock(&m->client->lock);
+	spin_lock(&m->lock);
 
 	if (m->err) {
-		spin_unlock(&m->client->lock);
+		spin_unlock(&m->lock);
 		return;
 	}
 
@@ -211,7 +212,7 @@ static void p9_conn_cancel(struct p9_conn *m, int err)
 			req->t_err = err;
 		p9_client_cb(m->client, req, REQ_STATUS_ERROR);
 	}
-	spin_unlock(&m->client->lock);
+	spin_unlock(&m->lock);
 }
 
 static __poll_t
@@ -357,19 +358,19 @@ static void p9_read_work(struct work_struct *work)
 	if ((m->rreq) && (m->rc.offset == m->rc.capacity)) {
 		p9_debug(P9_DEBUG_TRANS, "got new packet\n");
 		m->rreq->rc.size = m->rc.offset;
-		spin_lock(&m->client->lock);
+		spin_lock(&m->lock);
 		if (m->rreq->status == REQ_STATUS_SENT) {
 			list_del(&m->rreq->req_list);
 			p9_client_cb(m->client, m->rreq, REQ_STATUS_RCVD);
 		} else {
-			spin_unlock(&m->client->lock);
+			spin_unlock(&m->lock);
 			p9_debug(P9_DEBUG_ERROR,
 				 "Request tag %d errored out while we were reading the reply\n",
 				 m->rc.tag);
 			err = -EIO;
 			goto error;
 		}
-		spin_unlock(&m->client->lock);
+		spin_unlock(&m->lock);
 		m->rc.sdata = NULL;
 		m->rc.offset = 0;
 		m->rc.capacity = 0;
@@ -447,10 +448,10 @@ static void p9_write_work(struct work_struct *work)
 	}
 
 	if (!m->wsize) {
-		spin_lock(&m->client->lock);
+		spin_lock(&m->lock);
 		if (list_empty(&m->unsent_req_list)) {
 			clear_bit(Wworksched, &m->wsched);
-			spin_unlock(&m->client->lock);
+			spin_unlock(&m->lock);
 			return;
 		}
 
@@ -465,7 +466,7 @@ static void p9_write_work(struct work_struct *work)
 		m->wpos = 0;
 		p9_req_get(req);
 		m->wreq = req;
-		spin_unlock(&m->client->lock);
+		spin_unlock(&m->lock);
 	}
 
 	p9_debug(P9_DEBUG_TRANS, "mux %p pos %d size %d\n",
@@ -663,10 +664,10 @@ static int p9_fd_request(struct p9_client *client, struct p9_req_t *req)
 	if (m->err < 0)
 		return m->err;
 
-	spin_lock(&client->lock);
+	spin_lock(&m->lock);
 	req->status = REQ_STATUS_UNSENT;
 	list_add_tail(&req->req_list, &m->unsent_req_list);
-	spin_unlock(&client->lock);
+	spin_unlock(&m->lock);
 
 	if (test_and_clear_bit(Wpending, &m->wsched))
 		n = EPOLLOUT;
@@ -681,11 +682,13 @@ static int p9_fd_request(struct p9_client *client, struct p9_req_t *req)
 
 static int p9_fd_cancel(struct p9_client *client, struct p9_req_t *req)
 {
+	struct p9_trans_fd *ts = client->trans;
+	struct p9_conn *m = &ts->conn;
 	int ret = 1;
 
 	p9_debug(P9_DEBUG_TRANS, "client %p req %p\n", client, req);
 
-	spin_lock(&client->lock);
+	spin_lock(&m->lock);
 
 	if (req->status == REQ_STATUS_UNSENT) {
 		list_del(&req->req_list);
@@ -693,21 +696,24 @@ static int p9_fd_cancel(struct p9_client *client, struct p9_req_t *req)
 		p9_req_put(req);
 		ret = 0;
 	}
-	spin_unlock(&client->lock);
+	spin_unlock(&m->lock);
 
 	return ret;
 }
 
 static int p9_fd_cancelled(struct p9_client *client, struct p9_req_t *req)
 {
+	struct p9_trans_fd *ts = client->trans;
+	struct p9_conn *m = &ts->conn;
+
 	p9_debug(P9_DEBUG_TRANS, "client %p req %p\n", client, req);
 
 	/* we haven't received a response for oldreq,
 	 * remove it from the list.
 	 */
-	spin_lock(&client->lock);
+	spin_lock(&m->lock);
 	list_del(&req->req_list);
-	spin_unlock(&client->lock);
+	spin_unlock(&m->lock);
 	p9_req_put(req);
 
 	return 0;
-- 
2.23.0.rc1

[PATCH 22/38] sctp: Convert sctp_assocs_id to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

This is a fairly straightforward conversion.  The load side could be
converted to RCU by appropriate handling of races between delete and
lookup (eg RCU-freeing the sctp_association).  One point to note is
that sctp_assoc_set_id() will now return 1 if the allocation wrapped;
I have converted the callers to check for an error using '< 0' instead
of '!= 0'.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/net/sctp/sctp.h  |  5 ++---
 net/sctp/associola.c     | 34 +++++++++-------------------------
 net/sctp/protocol.c      |  6 ------
 net/sctp/sm_make_chunk.c |  2 +-
 net/sctp/socket.c        |  6 +++---
 5 files changed, 15 insertions(+), 38 deletions(-)

diff --git a/include/net/sctp/sctp.h b/include/net/sctp/sctp.h
index 5d60f13d2347..4bcce5d052d1 100644
--- a/include/net/sctp/sctp.h
+++ b/include/net/sctp/sctp.h
@@ -47,7 +47,7 @@
 #include <linux/proc_fs.h>
 #include <linux/spinlock.h>
 #include <linux/jiffies.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 
 #if IS_ENABLED(CONFIG_IPV6)
 #include <net/ipv6.h>
@@ -462,8 +462,7 @@ extern struct proto sctp_prot;
 extern struct proto sctpv6_prot;
 void sctp_put_port(struct sock *sk);
 
-extern struct idr sctp_assocs_id;
-extern spinlock_t sctp_assocs_id_lock;
+extern struct xarray sctp_assocs_id;
 
 /* Static inline functions. */
 
diff --git a/net/sctp/associola.c b/net/sctp/associola.c
index 5010cce52c93..4d6baecbdb99 100644
--- a/net/sctp/associola.c
+++ b/net/sctp/associola.c
@@ -39,6 +39,9 @@
 #include <net/sctp/sctp.h>
 #include <net/sctp/sm.h>
 
+DEFINE_XARRAY_FLAGS(sctp_assocs_id, XA_FLAGS_ALLOC1 | XA_FLAGS_LOCK_BH);
+static u32 sctp_assocs_next_id;
+
 /* Forward declarations for internal functions. */
 static void sctp_select_active_and_retran_path(struct sctp_association *asoc);
 static void sctp_assoc_bh_rcv(struct work_struct *work);
@@ -412,11 +415,8 @@ static void sctp_association_destroy(struct sctp_association *asoc)
 	sctp_endpoint_put(asoc->ep);
 	sock_put(asoc->base.sk);
 
-	if (asoc->assoc_id != 0) {
-		spin_lock_bh(&sctp_assocs_id_lock);
-		idr_remove(&sctp_assocs_id, asoc->assoc_id);
-		spin_unlock_bh(&sctp_assocs_id_lock);
-	}
+	if (asoc->assoc_id != 0)
+		xa_erase_bh(&sctp_assocs_id, asoc->assoc_id);
 
 	WARN_ON(atomic_read(&asoc->rmem_alloc));
 
@@ -1177,7 +1177,7 @@ int sctp_assoc_update(struct sctp_association *asoc,
 			sctp_stream_update(&asoc->stream, &new->stream);
 
 		/* get a new assoc id if we don't have one yet. */
-		if (sctp_assoc_set_id(asoc, GFP_ATOMIC))
+		if (sctp_assoc_set_id(asoc, GFP_ATOMIC) < 0)
 			return -ENOMEM;
 	}
 
@@ -1624,29 +1624,13 @@ int sctp_assoc_lookup_laddr(struct sctp_association *asoc,
 /* Set an association id for a given association */
 int sctp_assoc_set_id(struct sctp_association *asoc, gfp_t gfp)
 {
-	bool preload = gfpflags_allow_blocking(gfp);
-	int ret;
-
 	/* If the id is already assigned, keep it. */
 	if (asoc->assoc_id)
 		return 0;
 
-	if (preload)
-		idr_preload(gfp);
-	spin_lock_bh(&sctp_assocs_id_lock);
-	/* 0, 1, 2 are used as SCTP_FUTURE_ASSOC, SCTP_CURRENT_ASSOC and
-	 * SCTP_ALL_ASSOC, so an available id must be > SCTP_ALL_ASSOC.
-	 */
-	ret = idr_alloc_cyclic(&sctp_assocs_id, asoc, SCTP_ALL_ASSOC + 1, 0,
-			       GFP_NOWAIT);
-	spin_unlock_bh(&sctp_assocs_id_lock);
-	if (preload)
-		idr_preload_end();
-	if (ret < 0)
-		return ret;
-
-	asoc->assoc_id = (sctp_assoc_t)ret;
-	return 0;
+	return xa_alloc_cyclic_bh(&sctp_assocs_id, &asoc->assoc_id, asoc,
+			XA_LIMIT(SCTP_ALL_ASSOC + 1, INT_MAX),
+			&sctp_assocs_next_id, gfp);
 }
 
 /* Free the ASCONF queue */
diff --git a/net/sctp/protocol.c b/net/sctp/protocol.c
index 2d47adcb4cbe..79ccc786e5c9 100644
--- a/net/sctp/protocol.c
+++ b/net/sctp/protocol.c
@@ -50,9 +50,6 @@
 /* Global data structures. */
 struct sctp_globals sctp_globals __read_mostly;
 
-struct idr sctp_assocs_id;
-DEFINE_SPINLOCK(sctp_assocs_id_lock);
-
 static struct sctp_pf *sctp_pf_inet6_specific;
 static struct sctp_pf *sctp_pf_inet_specific;
 static struct sctp_af *sctp_af_v4_specific;
@@ -1388,9 +1385,6 @@ static __init int sctp_init(void)
 	sctp_max_instreams    		= SCTP_DEFAULT_INSTREAMS;
 	sctp_max_outstreams   		= SCTP_DEFAULT_OUTSTREAMS;
 
-	/* Initialize handle used for association ids. */
-	idr_init(&sctp_assocs_id);
-
 	limit = nr_free_buffer_pages() / 8;
 	limit = max(limit, 128UL);
 	sysctl_sctp_mem[0] = limit / 4 * 3;
diff --git a/net/sctp/sm_make_chunk.c b/net/sctp/sm_make_chunk.c
index 36bd8a6e82df..f049cfad6cf8 100644
--- a/net/sctp/sm_make_chunk.c
+++ b/net/sctp/sm_make_chunk.c
@@ -2443,7 +2443,7 @@ int sctp_process_init(struct sctp_association *asoc, struct sctp_chunk *chunk,
 	/* Update frag_point when stream_interleave may get changed. */
 	sctp_assoc_update_frag_point(asoc);
 
-	if (!asoc->temp && sctp_assoc_set_id(asoc, gfp))
+	if (!asoc->temp && sctp_assoc_set_id(asoc, gfp) < 0)
 		goto clean_up;
 
 	/* ADDIP Section 4.1 ASCONF Chunk Procedures
diff --git a/net/sctp/socket.c b/net/sctp/socket.c
index 12503e16fa96..0df05adfd033 100644
--- a/net/sctp/socket.c
+++ b/net/sctp/socket.c
@@ -236,11 +236,11 @@ struct sctp_association *sctp_id2assoc(struct sock *sk, sctp_assoc_t id)
 	if (id <= SCTP_ALL_ASSOC)
 		return NULL;
 
-	spin_lock_bh(&sctp_assocs_id_lock);
-	asoc = (struct sctp_association *)idr_find(&sctp_assocs_id, (int)id);
+	xa_lock_bh(&sctp_assocs_id);
+	asoc = xa_load(&sctp_assocs_id, id);
 	if (asoc && (asoc->base.sk != sk || asoc->base.dead))
 		asoc = NULL;
-	spin_unlock_bh(&sctp_assocs_id_lock);
+	xa_unlock_bh(&sctp_assocs_id);
 
 	return asoc;
 }
-- 
2.23.0.rc1

[PATCH 23/38] cls_api: Convert tcf_net to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

This module doesn't use the allocating functionality; convert it to a
plain XArray instead of an allocating one.  I've left struct tcf_net
in place in case more objects are added to it in future, although
it now only contains an XArray.  We don't need to call xa_destroy()
if the array is empty, so I've removed the contents of tcf_net_exit()
-- if it can be called with entries still in place, then it shoud call
xa_destroy() instead.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_api.c | 27 ++++++---------------------
 1 file changed, 6 insertions(+), 21 deletions(-)

diff --git a/net/sched/cls_api.c b/net/sched/cls_api.c
index e0d8b456e9f5..8392a7ef0ed4 100644
--- a/net/sched/cls_api.c
+++ b/net/sched/cls_api.c
@@ -19,7 +19,7 @@
 #include <linux/init.h>
 #include <linux/kmod.h>
 #include <linux/slab.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 #include <linux/rhashtable.h>
 #include <net/net_namespace.h>
 #include <net/sock.h>
@@ -777,8 +777,7 @@ tcf_chain0_head_change_cb_del(struct tcf_block *block,
 }
 
 struct tcf_net {
-	spinlock_t idr_lock; /* Protects idr */
-	struct idr idr;
+	struct xarray blocks;
 };
 
 static unsigned int tcf_net_id;
@@ -787,25 +786,15 @@ static int tcf_block_insert(struct tcf_block *block, struct net *net,
 			    struct netlink_ext_ack *extack)
 {
 	struct tcf_net *tn = net_generic(net, tcf_net_id);
-	int err;
-
-	idr_preload(GFP_KERNEL);
-	spin_lock(&tn->idr_lock);
-	err = idr_alloc_u32(&tn->idr, block, &block->index, block->index,
-			    GFP_NOWAIT);
-	spin_unlock(&tn->idr_lock);
-	idr_preload_end();
 
-	return err;
+	return xa_insert(&tn->blocks, block->index, block, GFP_KERNEL);
 }
 
 static void tcf_block_remove(struct tcf_block *block, struct net *net)
 {
 	struct tcf_net *tn = net_generic(net, tcf_net_id);
 
-	spin_lock(&tn->idr_lock);
-	idr_remove(&tn->idr, block->index);
-	spin_unlock(&tn->idr_lock);
+	xa_erase(&tn->blocks, block->index);
 }
 
 static struct tcf_block *tcf_block_create(struct net *net, struct Qdisc *q,
@@ -839,7 +828,7 @@ static struct tcf_block *tcf_block_lookup(struct net *net, u32 block_index)
 {
 	struct tcf_net *tn = net_generic(net, tcf_net_id);
 
-	return idr_find(&tn->idr, block_index);
+	return xa_load(&tn->blocks, block_index);
 }
 
 static struct tcf_block *tcf_block_refcnt_get(struct net *net, u32 block_index)
@@ -3164,16 +3153,12 @@ static __net_init int tcf_net_init(struct net *net)
 {
 	struct tcf_net *tn = net_generic(net, tcf_net_id);
 
-	spin_lock_init(&tn->idr_lock);
-	idr_init(&tn->idr);
+	xa_init(&tn->blocks);
 	return 0;
 }
 
 static void __net_exit tcf_net_exit(struct net *net)
 {
-	struct tcf_net *tn = net_generic(net, tcf_net_id);
-
-	idr_destroy(&tn->idr);
 }
 
 static struct pernet_operations tcf_net_ops = {
-- 
2.23.0.rc1

[PATCH 24/38] cls_u32: Convert tc_u_common->handle_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

There are two structures called 'handle_idr' in this module, which is
most confusing.  Rename this one to ht_xa.  Leave the existing locking
alone, which means that we're covered by both the rtnl lock and the
XArray spinlock when accessing this XArray.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_u32.c | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 8614088edd1b..18ef5f375976 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -86,7 +86,8 @@ struct tc_u_common {
 	struct tc_u_hnode __rcu	*hlist;
 	void			*ptr;
 	int			refcnt;
-	struct idr		handle_idr;
+	u32			ht_next;
+	struct xarray		ht_xa;
 	struct hlist_node	hnode;
 	long			knodes;
 };
@@ -305,8 +306,12 @@ static void *u32_get(struct tcf_proto *tp, u32 handle)
 /* Protected by rtnl lock */
 static u32 gen_new_htid(struct tc_u_common *tp_c, struct tc_u_hnode *ptr)
 {
-	int id = idr_alloc_cyclic(&tp_c->handle_idr, ptr, 1, 0x7FF, GFP_KERNEL);
-	if (id < 0)
+	int err;
+	u32 id;
+
+	err = xa_alloc_cyclic(&tp_c->ht_xa, &id, ptr, XA_LIMIT(0, 0x7ff),
+			&tp_c->ht_next, GFP_KERNEL);
+	if (err < 0)
 		return 0;
 	return (id | 0x800U) << 20;
 }
@@ -371,8 +376,7 @@ static int u32_init(struct tcf_proto *tp)
 		}
 		tp_c->ptr = key;
 		INIT_HLIST_NODE(&tp_c->hnode);
-		idr_init(&tp_c->handle_idr);
-
+		xa_init_flags(&tp_c->ht_xa, XA_FLAGS_ALLOC1);
 		hlist_add_head(&tp_c->hnode, tc_u_hash(key));
 	}
 
@@ -608,7 +612,7 @@ static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht,
 		if (phn == ht) {
 			u32_clear_hw_hnode(tp, ht, extack);
 			idr_destroy(&ht->handle_idr);
-			idr_remove(&tp_c->handle_idr, ht->handle);
+			xa_erase(&tp_c->ht_xa, ht->handle);
 			RCU_INIT_POINTER(*hn, ht->next);
 			kfree_rcu(ht, rcu);
 			return 0;
@@ -645,7 +649,6 @@ static void u32_destroy(struct tcf_proto *tp, bool rtnl_held,
 				kfree_rcu(ht, rcu);
 		}
 
-		idr_destroy(&tp_c->handle_idr);
 		kfree(tp_c);
 	}
 
@@ -950,8 +953,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 				return -ENOMEM;
 			}
 		} else {
-			err = idr_alloc_u32(&tp_c->handle_idr, ht, &handle,
-					    handle, GFP_KERNEL);
+			err = xa_insert(&tp_c->ht_xa, handle, ht, GFP_KERNEL);
 			if (err) {
 				kfree(ht);
 				return err;
@@ -966,7 +968,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 
 		err = u32_replace_hw_hnode(tp, ht, flags, extack);
 		if (err) {
-			idr_remove(&tp_c->handle_idr, handle);
+			xa_erase(&tp_c->ht_xa, handle);
 			kfree(ht);
 			return err;
 		}
-- 
2.23.0.rc1

[PATCH 25/38] cls_u32: Convert tc_u_hnode->handle_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Rename this IDR to 'knodes' since that's what's being stored in it.
Use xa_alloc_cyclic() since that's what's being emulated in gen_new_kid().
Allow gen_new_kid() to return a "no space" indicator.  Access to this
XArray is now under both the rtnl lock and the XArray spinlock.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_u32.c | 41 ++++++++++++++++++++---------------------
 1 file changed, 20 insertions(+), 21 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 18ef5f375976..46ddfd312952 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -38,7 +38,7 @@
 #include <net/netlink.h>
 #include <net/act_api.h>
 #include <net/pkt_cls.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 
 struct tc_u_knode {
 	struct tc_u_knode __rcu	*next;
@@ -72,7 +72,7 @@ struct tc_u_hnode {
 	u32			prio;
 	int			refcnt;
 	unsigned int		divisor;
-	struct idr		handle_idr;
+	struct xarray		knodes;
 	bool			is_root;
 	struct rcu_head		rcu;
 	u32			flags;
@@ -366,7 +366,7 @@ static int u32_init(struct tcf_proto *tp)
 	root_ht->handle = tp_c ? gen_new_htid(tp_c, root_ht) : 0x80000000;
 	root_ht->prio = tp->prio;
 	root_ht->is_root = true;
-	idr_init(&root_ht->handle_idr);
+	xa_init_flags(&root_ht->knodes, XA_FLAGS_ALLOC);
 
 	if (tp_c == NULL) {
 		tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
@@ -461,7 +461,7 @@ static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode *key)
 				tp_c->knodes--;
 
 				tcf_unbind_filter(tp, &key->res);
-				idr_remove(&ht->handle_idr, key->handle);
+				xa_erase(&ht->knodes, key->handle);
 				tcf_exts_get_net(&key->exts);
 				tcf_queue_work(&key->rwork, u32_delete_key_freepf_work);
 				return 0;
@@ -585,7 +585,7 @@ static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht,
 			tp_c->knodes--;
 			tcf_unbind_filter(tp, &n->res);
 			u32_remove_hw_knode(tp, n, extack);
-			idr_remove(&ht->handle_idr, n->handle);
+			xa_erase(&ht->knodes, n->handle);
 			if (tcf_exts_get_net(&n->exts))
 				tcf_queue_work(&n->rwork, u32_delete_key_freepf_work);
 			else
@@ -611,7 +611,6 @@ static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht,
 	     hn = &phn->next, phn = rtnl_dereference(*hn)) {
 		if (phn == ht) {
 			u32_clear_hw_hnode(tp, ht, extack);
-			idr_destroy(&ht->handle_idr);
 			xa_erase(&tp_c->ht_xa, ht->handle);
 			RCU_INIT_POINTER(*hn, ht->next);
 			kfree_rcu(ht, rcu);
@@ -687,15 +686,13 @@ static int u32_delete(struct tcf_proto *tp, void *arg, bool *last,
 
 static u32 gen_new_kid(struct tc_u_hnode *ht, u32 htid)
 {
-	u32 index = htid | 0x800;
-	u32 max = htid | 0xFFF;
-
-	if (idr_alloc_u32(&ht->handle_idr, NULL, &index, max, GFP_KERNEL)) {
-		index = htid + 1;
-		if (idr_alloc_u32(&ht->handle_idr, NULL, &index, max,
-				 GFP_KERNEL))
-			index = max;
-	}
+	u32 start = htid | 0x800;
+	u32 index;
+
+	if (xa_alloc_cyclic(&ht->knodes, &index, NULL,
+				XA_LIMIT(htid + 1, htid | 0xfff), &start,
+				GFP_KERNEL) < 0)
+		index = htid;
 
 	return index;
 }
@@ -789,7 +786,7 @@ static void u32_replace_knode(struct tcf_proto *tp, struct tc_u_common *tp_c,
 		if (pins->handle == n->handle)
 			break;
 
-	idr_replace(&ht->handle_idr, n, n->handle);
+	xa_store(&ht->knodes, n->handle, n, 0);
 	RCU_INIT_POINTER(n->next, pins->next);
 	rcu_assign_pointer(*ins, n);
 }
@@ -963,7 +960,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 		ht->divisor = divisor;
 		ht->handle = handle;
 		ht->prio = tp->prio;
-		idr_init(&ht->handle_idr);
+		xa_init_flags(&ht->knodes, XA_FLAGS_ALLOC);
 		ht->flags = flags;
 
 		err = u32_replace_hw_hnode(tp, ht, flags, extack);
@@ -1008,12 +1005,14 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 			return -EINVAL;
 		}
 		handle = htid | TC_U32_NODE(handle);
-		err = idr_alloc_u32(&ht->handle_idr, NULL, &handle, handle,
-				    GFP_KERNEL);
+		err = xa_insert(&ht->knodes, handle, NULL, GFP_KERNEL);
 		if (err)
 			return err;
-	} else
+	} else {
 		handle = gen_new_kid(ht, htid);
+		if (handle == htid)
+			return -ENOBUFS;
+	}
 
 	if (tb[TCA_U32_SEL] == NULL) {
 		NL_SET_ERR_MSG_MOD(extack, "Selector not specified");
@@ -1108,7 +1107,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 #endif
 	kfree(n);
 erridr:
-	idr_remove(&ht->handle_idr, handle);
+	xa_erase(&ht->knodes, handle);
 	return err;
 }
 
-- 
2.23.0.rc1

[PATCH 26/38] cls_bpf: Convert handle_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Rename it to 'progs' as this is what's stored there.  The locking is
unchanged, so access to this XArray is protected by both the rtnl lock
and the XArray spinlock.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_bpf.c | 28 +++++++++++++---------------
 1 file changed, 13 insertions(+), 15 deletions(-)

diff --git a/net/sched/cls_bpf.c b/net/sched/cls_bpf.c
index 3f7a9c02b70c..9a794f557861 100644
--- a/net/sched/cls_bpf.c
+++ b/net/sched/cls_bpf.c
@@ -14,7 +14,7 @@
 #include <linux/skbuff.h>
 #include <linux/filter.h>
 #include <linux/bpf.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 
 #include <net/rtnetlink.h>
 #include <net/pkt_cls.h>
@@ -30,7 +30,7 @@ MODULE_DESCRIPTION("TC BPF based classifier");
 
 struct cls_bpf_head {
 	struct list_head plist;
-	struct idr handle_idr;
+	struct xarray progs;
 	struct rcu_head rcu;
 };
 
@@ -242,7 +242,7 @@ static int cls_bpf_init(struct tcf_proto *tp)
 		return -ENOBUFS;
 
 	INIT_LIST_HEAD_RCU(&head->plist);
-	idr_init(&head->handle_idr);
+	xa_init_flags(&head->progs, XA_FLAGS_ALLOC1);
 	rcu_assign_pointer(tp->root, head);
 
 	return 0;
@@ -283,7 +283,7 @@ static void __cls_bpf_delete(struct tcf_proto *tp, struct cls_bpf_prog *prog,
 {
 	struct cls_bpf_head *head = rtnl_dereference(tp->root);
 
-	idr_remove(&head->handle_idr, prog->handle);
+	xa_erase(&head->progs, prog->handle);
 	cls_bpf_stop_offload(tp, prog, extack);
 	list_del_rcu(&prog->link);
 	tcf_unbind_filter(tp, &prog->res);
@@ -312,7 +312,7 @@ static void cls_bpf_destroy(struct tcf_proto *tp, bool rtnl_held,
 	list_for_each_entry_safe(prog, tmp, &head->plist, link)
 		__cls_bpf_delete(tp, prog, extack);
 
-	idr_destroy(&head->handle_idr);
+	xa_destroy(&head->progs);
 	kfree_rcu(head, rcu);
 }
 
@@ -484,23 +484,21 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 		}
 	}
 
+	prog->handle = handle;
 	if (handle == 0) {
-		handle = 1;
-		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
-				    INT_MAX, GFP_KERNEL);
+		ret = xa_alloc(&head->progs, &prog->handle, prog, xa_limit_31b,
+				GFP_KERNEL);
 	} else if (!oldprog) {
-		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
-				    handle, GFP_KERNEL);
+		ret = xa_insert(&head->progs, handle, prog, GFP_KERNEL);
 	}
 
 	if (ret)
 		goto errout;
-	prog->handle = handle;
 
 	ret = cls_bpf_set_parms(net, tp, prog, base, tb, tca[TCA_RATE], ovr,
 				extack);
 	if (ret < 0)
-		goto errout_idr;
+		goto errout_prog;
 
 	ret = cls_bpf_offload(tp, prog, oldprog, extack);
 	if (ret)
@@ -510,7 +508,7 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 		prog->gen_flags |= TCA_CLS_FLAGS_NOT_IN_HW;
 
 	if (oldprog) {
-		idr_replace(&head->handle_idr, prog, handle);
+		xa_store(&head->progs, handle, prog, 0);
 		list_replace_rcu(&oldprog->link, &prog->link);
 		tcf_unbind_filter(tp, &oldprog->res);
 		tcf_exts_get_net(&oldprog->exts);
@@ -524,9 +522,9 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 
 errout_parms:
 	cls_bpf_free_parms(prog);
-errout_idr:
+errout_prog:
 	if (!oldprog)
-		idr_remove(&head->handle_idr, prog->handle);
+		xa_erase(&head->progs, prog->handle);
 errout:
 	tcf_exts_destroy(&prog->exts);
 	kfree(prog);
-- 
2.23.0.rc1

[PATCH 27/38] cls_bpf: Remove list of programs

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Use the XArray for all this functionality.  Saves two pointers per
program and it's faster to iterate over an XArray than a linked list.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_bpf.c | 38 ++++++++++++++------------------------
 1 file changed, 14 insertions(+), 24 deletions(-)

diff --git a/net/sched/cls_bpf.c b/net/sched/cls_bpf.c
index 9a794f557861..295baabdc683 100644
--- a/net/sched/cls_bpf.c
+++ b/net/sched/cls_bpf.c
@@ -29,14 +29,12 @@ MODULE_DESCRIPTION("TC BPF based classifier");
 	(TCA_CLS_FLAGS_SKIP_HW | TCA_CLS_FLAGS_SKIP_SW)
 
 struct cls_bpf_head {
-	struct list_head plist;
 	struct xarray progs;
 	struct rcu_head rcu;
 };
 
 struct cls_bpf_prog {
 	struct bpf_prog *filter;
-	struct list_head link;
 	struct tcf_result res;
 	bool exts_integrated;
 	u32 gen_flags;
@@ -81,13 +79,14 @@ static int cls_bpf_classify(struct sk_buff *skb, const struct tcf_proto *tp,
 			    struct tcf_result *res)
 {
 	struct cls_bpf_head *head = rcu_dereference_bh(tp->root);
+	XA_STATE(xas, &head->progs, 0);
 	bool at_ingress = skb_at_tc_ingress(skb);
 	struct cls_bpf_prog *prog;
 	int ret = -1;
 
 	/* Needed here for accessing maps. */
 	rcu_read_lock();
-	list_for_each_entry_rcu(prog, &head->plist, link) {
+	xas_for_each(&xas, prog, ULONG_MAX) {
 		int filter_res;
 
 		qdisc_skb_cb(skb)->tc_classid = prog->res.classid;
@@ -241,7 +240,6 @@ static int cls_bpf_init(struct tcf_proto *tp)
 	if (head == NULL)
 		return -ENOBUFS;
 
-	INIT_LIST_HEAD_RCU(&head->plist);
 	xa_init_flags(&head->progs, XA_FLAGS_ALLOC1);
 	rcu_assign_pointer(tp->root, head);
 
@@ -285,7 +283,6 @@ static void __cls_bpf_delete(struct tcf_proto *tp, struct cls_bpf_prog *prog,
 
 	xa_erase(&head->progs, prog->handle);
 	cls_bpf_stop_offload(tp, prog, extack);
-	list_del_rcu(&prog->link);
 	tcf_unbind_filter(tp, &prog->res);
 	if (tcf_exts_get_net(&prog->exts))
 		tcf_queue_work(&prog->rwork, cls_bpf_delete_prog_work);
@@ -299,7 +296,7 @@ static int cls_bpf_delete(struct tcf_proto *tp, void *arg, bool *last,
 	struct cls_bpf_head *head = rtnl_dereference(tp->root);
 
 	__cls_bpf_delete(tp, arg, extack);
-	*last = list_empty(&head->plist);
+	*last = xa_empty(&head->progs);
 	return 0;
 }
 
@@ -307,26 +304,20 @@ static void cls_bpf_destroy(struct tcf_proto *tp, bool rtnl_held,
 			    struct netlink_ext_ack *extack)
 {
 	struct cls_bpf_head *head = rtnl_dereference(tp->root);
-	struct cls_bpf_prog *prog, *tmp;
+	struct cls_bpf_prog *prog;
+	unsigned long handle;
 
-	list_for_each_entry_safe(prog, tmp, &head->plist, link)
+	xa_for_each(&head->progs, handle, prog)
 		__cls_bpf_delete(tp, prog, extack);
 
-	xa_destroy(&head->progs);
 	kfree_rcu(head, rcu);
 }
 
 static void *cls_bpf_get(struct tcf_proto *tp, u32 handle)
 {
 	struct cls_bpf_head *head = rtnl_dereference(tp->root);
-	struct cls_bpf_prog *prog;
 
-	list_for_each_entry(prog, &head->plist, link) {
-		if (prog->handle == handle)
-			return prog;
-	}
-
-	return NULL;
+	return xa_load(&head->progs, handle);
 }
 
 static int cls_bpf_prog_from_ops(struct nlattr **tb, struct cls_bpf_prog *prog)
@@ -509,12 +500,9 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 
 	if (oldprog) {
 		xa_store(&head->progs, handle, prog, 0);
-		list_replace_rcu(&oldprog->link, &prog->link);
 		tcf_unbind_filter(tp, &oldprog->res);
 		tcf_exts_get_net(&oldprog->exts);
 		tcf_queue_work(&oldprog->rwork, cls_bpf_delete_prog_work);
-	} else {
-		list_add_rcu(&prog->link, &head->plist);
 	}
 
 	*arg = prog;
@@ -636,15 +624,16 @@ static void cls_bpf_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 {
 	struct cls_bpf_head *head = rtnl_dereference(tp->root);
 	struct cls_bpf_prog *prog;
+	unsigned long handle;
+
+	arg->count = arg->skip;
 
-	list_for_each_entry(prog, &head->plist, link) {
-		if (arg->count < arg->skip)
-			goto skip;
+	xa_for_each_start(&head->progs, handle, prog, arg->cookie) {
 		if (arg->fn(tp, prog, arg) < 0) {
 			arg->stop = 1;
 			break;
 		}
-skip:
+		arg->cookie = handle + 1;
 		arg->count++;
 	}
 }
@@ -656,9 +645,10 @@ static int cls_bpf_reoffload(struct tcf_proto *tp, bool add, flow_setup_cb_t *cb
 	struct tcf_block *block = tp->chain->block;
 	struct tc_cls_bpf_offload cls_bpf = {};
 	struct cls_bpf_prog *prog;
+	unsigned long handle;
 	int err;
 
-	list_for_each_entry(prog, &head->plist, link) {
+	xa_for_each(&head->progs, handle, prog) {
 		if (tc_skip_hw(prog->gen_flags))
 			continue;
 
-- 
2.23.0.rc1

[PATCH 28/38] cls_bpf: Use XArray marks to accelerate re-offload

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Propagate the skip_hw flag from the cls_bpf_prog structure into one of
the XArray mark bits which lets us skip examining the unwanted programs.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_bpf.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/net/sched/cls_bpf.c b/net/sched/cls_bpf.c
index 295baabdc683..4dcab41b25b5 100644
--- a/net/sched/cls_bpf.c
+++ b/net/sched/cls_bpf.c
@@ -33,6 +33,8 @@ struct cls_bpf_head {
 	struct rcu_head rcu;
 };
 
+#define HW_FILTER	XA_MARK_1
+
 struct cls_bpf_prog {
 	struct bpf_prog *filter;
 	struct tcf_result res;
@@ -505,6 +507,11 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 		tcf_queue_work(&oldprog->rwork, cls_bpf_delete_prog_work);
 	}
 
+	if (!tc_skip_hw(prog->gen_flags))
+		xa_set_mark(&head->progs, prog->handle, HW_FILTER);
+	else if (oldprog)
+		xa_clear_mark(&head->progs, prog->handle, HW_FILTER);
+
 	*arg = prog;
 	return 0;
 
@@ -648,10 +655,7 @@ static int cls_bpf_reoffload(struct tcf_proto *tp, bool add, flow_setup_cb_t *cb
 	unsigned long handle;
 	int err;
 
-	xa_for_each(&head->progs, handle, prog) {
-		if (tc_skip_hw(prog->gen_flags))
-			continue;
-
+	xa_for_each_marked(&head->progs, handle, prog, HW_FILTER) {
 		tc_cls_common_offload_init(&cls_bpf.common, tp, prog->gen_flags,
 					   extack);
 		cls_bpf.command = TC_CLSBPF_OFFLOAD;
-- 
2.23.0.rc1

[PATCH 29/38] cls_flower: Convert handle_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Inline __fl_get() into fl_get().  Use the RCU lock explicitly for
lookups and walks instead of relying on RTNL.  The xa_lock protects us,
but remains nested under the RTNL for now.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_flower.c | 54 ++++++++++++++++++++----------------------
 1 file changed, 26 insertions(+), 28 deletions(-)

diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index 054123742e32..54026c9e9b05 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -91,7 +91,7 @@ struct cls_fl_head {
 	struct list_head masks;
 	struct list_head hw_filters;
 	struct rcu_work rwork;
-	struct idr handle_idr;
+	struct xarray filters;
 };
 
 struct cls_fl_filter {
@@ -334,7 +334,7 @@ static int fl_init(struct tcf_proto *tp)
 	INIT_LIST_HEAD_RCU(&head->masks);
 	INIT_LIST_HEAD(&head->hw_filters);
 	rcu_assign_pointer(tp->root, head);
-	idr_init(&head->handle_idr);
+	xa_init_flags(&head->filters, XA_FLAGS_ALLOC1);
 
 	return rhashtable_init(&head->ht, &mask_ht_params);
 }
@@ -530,19 +530,6 @@ static void __fl_put(struct cls_fl_filter *f)
 		__fl_destroy_filter(f);
 }
 
-static struct cls_fl_filter *__fl_get(struct cls_fl_head *head, u32 handle)
-{
-	struct cls_fl_filter *f;
-
-	rcu_read_lock();
-	f = idr_find(&head->handle_idr, handle);
-	if (f && !refcount_inc_not_zero(&f->refcnt))
-		f = NULL;
-	rcu_read_unlock();
-
-	return f;
-}
-
 static int __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f,
 		       bool *last, bool rtnl_held,
 		       struct netlink_ext_ack *extack)
@@ -560,7 +547,7 @@ static int __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f,
 	f->deleted = true;
 	rhashtable_remove_fast(&f->mask->ht, &f->ht_node,
 			       f->mask->filter_ht_params);
-	idr_remove(&head->handle_idr, f->handle);
+	xa_erase(&head->filters, f->handle);
 	list_del_rcu(&f->list);
 	spin_unlock(&tp->lock);
 
@@ -599,7 +586,7 @@ static void fl_destroy(struct tcf_proto *tp, bool rtnl_held,
 				break;
 		}
 	}
-	idr_destroy(&head->handle_idr);
+	xa_destroy(&head->filters);
 
 	__module_get(THIS_MODULE);
 	tcf_queue_work(&head->rwork, fl_destroy_sleepable);
@@ -615,8 +602,15 @@ static void fl_put(struct tcf_proto *tp, void *arg)
 static void *fl_get(struct tcf_proto *tp, u32 handle)
 {
 	struct cls_fl_head *head = fl_head_dereference(tp);
+	struct cls_fl_filter *f;
+
+	rcu_read_lock();
+	f = xa_load(&head->filters, handle);
+	if (f && !refcount_inc_not_zero(&f->refcnt))
+		f = NULL;
+	rcu_read_unlock();
 
-	return __fl_get(head, handle);
+	return f;
 }
 
 static const struct nla_policy fl_policy[TCA_FLOWER_MAX + 1] = {
@@ -1663,7 +1657,7 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 		rhashtable_remove_fast(&fold->mask->ht,
 				       &fold->ht_node,
 				       fold->mask->filter_ht_params);
-		idr_replace(&head->handle_idr, fnew, fnew->handle);
+		xa_store(&head->filters, fnew->handle, fnew, 0);
 		list_replace_rcu(&fold->list, &fnew->list);
 		fold->deleted = true;
 
@@ -1681,8 +1675,9 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 	} else {
 		if (handle) {
 			/* user specifies a handle and it doesn't exist */
-			err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
-					    handle, GFP_ATOMIC);
+			fnew->handle = handle;
+			err = xa_insert(&head->filters, handle, fnew,
+					GFP_ATOMIC);
 
 			/* Filter with specified handle was concurrently
 			 * inserted after initial check in cls_api. This is not
@@ -1690,18 +1685,16 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 			 * message flags. Returning EAGAIN will cause cls_api to
 			 * try to update concurrently inserted rule.
 			 */
-			if (err == -ENOSPC)
+			if (err == -EBUSY)
 				err = -EAGAIN;
 		} else {
-			handle = 1;
-			err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
-					    INT_MAX, GFP_ATOMIC);
+			err = xa_alloc(&head->filters, &fnew->handle, fnew,
+					xa_limit_31b, GFP_ATOMIC);
 		}
 		if (err)
 			goto errout_hw;
 
 		refcount_inc(&fnew->refcnt);
-		fnew->handle = handle;
 		list_add_tail_rcu(&fnew->list, &fnew->mask->filters);
 		spin_unlock(&tp->lock);
 	}
@@ -1755,23 +1748,28 @@ static void fl_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 		    bool rtnl_held)
 {
 	struct cls_fl_head *head = fl_head_dereference(tp);
-	unsigned long id = arg->cookie, tmp;
+	unsigned long id;
 	struct cls_fl_filter *f;
 
 	arg->count = arg->skip;
 
-	idr_for_each_entry_continue_ul(&head->handle_idr, f, tmp, id) {
+	rcu_read_lock();
+	xa_for_each_start(&head->filters, id, f, arg->cookie) {
 		/* don't return filters that are being deleted */
 		if (!refcount_inc_not_zero(&f->refcnt))
 			continue;
+		rcu_read_unlock();
 		if (arg->fn(tp, f, arg) < 0) {
 			__fl_put(f);
 			arg->stop = 1;
+			rcu_read_lock();
 			break;
 		}
 		__fl_put(f);
 		arg->count++;
+		rcu_read_lock();
 	}
+	rcu_read_unlock();
 	arg->cookie = id;
 }
 
-- 
2.23.0.rc1

[PATCH 30/38] cls_flower: Use XArray list of filters in fl_walk

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Instead of iterating over every filter attached to every mark, just
iterate over each filter.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_flower.c | 15 ++++++---------
 1 file changed, 6 insertions(+), 9 deletions(-)

diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index 54026c9e9b05..2a1999d2b507 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -575,18 +575,15 @@ static void fl_destroy(struct tcf_proto *tp, bool rtnl_held,
 		       struct netlink_ext_ack *extack)
 {
 	struct cls_fl_head *head = fl_head_dereference(tp);
-	struct fl_flow_mask *mask, *next_mask;
-	struct cls_fl_filter *f, *next;
+	struct cls_fl_filter *f;
+	unsigned long handle;
 	bool last;
 
-	list_for_each_entry_safe(mask, next_mask, &head->masks, list) {
-		list_for_each_entry_safe(f, next, &mask->filters, list) {
-			__fl_delete(tp, f, &last, rtnl_held, extack);
-			if (last)
-				break;
-		}
+	xa_for_each(&head->filters, handle, f) {
+		__fl_delete(tp, f, &last, rtnl_held, extack);
+		if (last)
+			break;
 	}
-	xa_destroy(&head->filters);
 
 	__module_get(THIS_MODULE);
 	tcf_queue_work(&head->rwork, fl_destroy_sleepable);
-- 
2.23.0.rc1

[PATCH 31/38] cls_flower: Use XArray marks instead of separate list

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Remove the hw_filter list in favour of using one of the XArray mark
bits which lets us iterate more efficiently than walking a linked list.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_flower.c | 47 ++++++++++--------------------------------
 1 file changed, 11 insertions(+), 36 deletions(-)

diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index 2a1999d2b507..4625de5e29a7 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -85,11 +85,12 @@ struct fl_flow_tmplt {
 	struct tcf_chain *chain;
 };
 
+#define HW_FILTER	XA_MARK_1
+
 struct cls_fl_head {
 	struct rhashtable ht;
 	spinlock_t masks_lock; /* Protect masks list */
 	struct list_head masks;
-	struct list_head hw_filters;
 	struct rcu_work rwork;
 	struct xarray filters;
 };
@@ -102,7 +103,6 @@ struct cls_fl_filter {
 	struct tcf_result res;
 	struct fl_flow_key key;
 	struct list_head list;
-	struct list_head hw_list;
 	u32 handle;
 	u32 flags;
 	u32 in_hw_count;
@@ -332,7 +332,6 @@ static int fl_init(struct tcf_proto *tp)
 
 	spin_lock_init(&head->masks_lock);
 	INIT_LIST_HEAD_RCU(&head->masks);
-	INIT_LIST_HEAD(&head->hw_filters);
 	rcu_assign_pointer(tp->root, head);
 	xa_init_flags(&head->filters, XA_FLAGS_ALLOC1);
 
@@ -421,7 +420,6 @@ static void fl_hw_destroy_filter(struct tcf_proto *tp, struct cls_fl_filter *f,
 
 	tc_setup_cb_call(block, TC_SETUP_CLSFLOWER, &cls_flower, false);
 	spin_lock(&tp->lock);
-	list_del_init(&f->hw_list);
 	tcf_block_offload_dec(block, &f->flags);
 	spin_unlock(&tp->lock);
 
@@ -433,7 +431,6 @@ static int fl_hw_replace_filter(struct tcf_proto *tp,
 				struct cls_fl_filter *f, bool rtnl_held,
 				struct netlink_ext_ack *extack)
 {
-	struct cls_fl_head *head = fl_head_dereference(tp);
 	struct tcf_block *block = tp->chain->block;
 	struct flow_cls_offload cls_flower = {};
 	bool skip_sw = tc_skip_sw(f->flags);
@@ -485,9 +482,6 @@ static int fl_hw_replace_filter(struct tcf_proto *tp,
 		goto errout;
 	}
 
-	spin_lock(&tp->lock);
-	list_add(&f->hw_list, &head->hw_filters);
-	spin_unlock(&tp->lock);
 errout:
 	if (!rtnl_held)
 		rtnl_unlock();
@@ -1581,7 +1575,6 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 		err = -ENOBUFS;
 		goto errout_tb;
 	}
-	INIT_LIST_HEAD(&fnew->hw_list);
 	refcount_set(&fnew->refcnt, 1);
 
 	err = tcf_exts_init(&fnew->exts, net, TCA_FLOWER_ACT, 0);
@@ -1698,6 +1691,11 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 
 	*arg = fnew;
 
+	if (!tc_skip_hw(fnew->flags))
+		xa_set_mark(&head->filters, fnew->handle, HW_FILTER);
+	else if (fold)
+		xa_clear_mark(&head->filters, fnew->handle, HW_FILTER);
+
 	kfree(tb);
 	tcf_queue_work(&mask->rwork, fl_uninit_mask_free_work);
 	return 0;
@@ -1770,37 +1768,14 @@ static void fl_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 	arg->cookie = id;
 }
 
-static struct cls_fl_filter *
-fl_get_next_hw_filter(struct tcf_proto *tp, struct cls_fl_filter *f, bool add)
-{
-	struct cls_fl_head *head = fl_head_dereference(tp);
-
-	spin_lock(&tp->lock);
-	if (list_empty(&head->hw_filters)) {
-		spin_unlock(&tp->lock);
-		return NULL;
-	}
-
-	if (!f)
-		f = list_entry(&head->hw_filters, struct cls_fl_filter,
-			       hw_list);
-	list_for_each_entry_continue(f, &head->hw_filters, hw_list) {
-		if (!(add && f->deleted) && refcount_inc_not_zero(&f->refcnt)) {
-			spin_unlock(&tp->lock);
-			return f;
-		}
-	}
-
-	spin_unlock(&tp->lock);
-	return NULL;
-}
-
 static int fl_reoffload(struct tcf_proto *tp, bool add, flow_setup_cb_t *cb,
 			void *cb_priv, struct netlink_ext_ack *extack)
 {
+	struct cls_fl_head *head = fl_head_dereference(tp);
 	struct tcf_block *block = tp->chain->block;
 	struct flow_cls_offload cls_flower = {};
-	struct cls_fl_filter *f = NULL;
+	struct cls_fl_filter *f;
+	unsigned long handle;
 	int err;
 
 	/* hw_filters list can only be changed by hw offload functions after
@@ -1809,7 +1784,7 @@ static int fl_reoffload(struct tcf_proto *tp, bool add, flow_setup_cb_t *cb,
 	 */
 	ASSERT_RTNL();
 
-	while ((f = fl_get_next_hw_filter(tp, f, add))) {
+	xa_for_each_marked(&head->filters, handle, f, HW_FILTER) {
 		cls_flower.rule =
 			flow_rule_alloc(tcf_exts_num_actions(&f->exts));
 		if (!cls_flower.rule) {
-- 
2.23.0.rc1

[PATCH 32/38] cls_basic: Convert handle_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

The flist is redundant with the XArray, so remove it and use XArray
operations to iterate & look up filters by ID.  Locking is unadjusted,
so most XArray operations continue to be protected by both the rtnl
lock and the XArray spinlock.  Lookups remain under the rtnl lock,
but could be switched to pure RCU protection.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/sched/cls_basic.c | 56 ++++++++++++++++---------------------------
 1 file changed, 21 insertions(+), 35 deletions(-)

diff --git a/net/sched/cls_basic.c b/net/sched/cls_basic.c
index 4aafbe3d435c..66efad664a92 100644
--- a/net/sched/cls_basic.c
+++ b/net/sched/cls_basic.c
@@ -13,15 +13,14 @@
 #include <linux/errno.h>
 #include <linux/rtnetlink.h>
 #include <linux/skbuff.h>
-#include <linux/idr.h>
 #include <linux/percpu.h>
+#include <linux/xarray.h>
 #include <net/netlink.h>
 #include <net/act_api.h>
 #include <net/pkt_cls.h>
 
 struct basic_head {
-	struct list_head	flist;
-	struct idr		handle_idr;
+	struct xarray		filters;
 	struct rcu_head		rcu;
 };
 
@@ -31,7 +30,6 @@ struct basic_filter {
 	struct tcf_ematch_tree	ematches;
 	struct tcf_result	res;
 	struct tcf_proto	*tp;
-	struct list_head	link;
 	struct tc_basic_pcnt __percpu *pf;
 	struct rcu_work		rwork;
 };
@@ -42,8 +40,9 @@ static int basic_classify(struct sk_buff *skb, const struct tcf_proto *tp,
 	int r;
 	struct basic_head *head = rcu_dereference_bh(tp->root);
 	struct basic_filter *f;
+	unsigned long index;
 
-	list_for_each_entry_rcu(f, &head->flist, link) {
+	xa_for_each(&head->filters, index, f) {
 		__this_cpu_inc(f->pf->rcnt);
 		if (!tcf_em_tree_match(skb, &f->ematches, NULL))
 			continue;
@@ -60,15 +59,8 @@ static int basic_classify(struct sk_buff *skb, const struct tcf_proto *tp,
 static void *basic_get(struct tcf_proto *tp, u32 handle)
 {
 	struct basic_head *head = rtnl_dereference(tp->root);
-	struct basic_filter *f;
-
-	list_for_each_entry(f, &head->flist, link) {
-		if (f->handle == handle) {
-			return f;
-		}
-	}
 
-	return NULL;
+	return xa_load(&head->filters, handle);
 }
 
 static int basic_init(struct tcf_proto *tp)
@@ -78,8 +70,7 @@ static int basic_init(struct tcf_proto *tp)
 	head = kzalloc(sizeof(*head), GFP_KERNEL);
 	if (head == NULL)
 		return -ENOBUFS;
-	INIT_LIST_HEAD(&head->flist);
-	idr_init(&head->handle_idr);
+	xa_init_flags(&head->filters, XA_FLAGS_ALLOC1);
 	rcu_assign_pointer(tp->root, head);
 	return 0;
 }
@@ -107,18 +98,17 @@ static void basic_destroy(struct tcf_proto *tp, bool rtnl_held,
 			  struct netlink_ext_ack *extack)
 {
 	struct basic_head *head = rtnl_dereference(tp->root);
-	struct basic_filter *f, *n;
+	struct basic_filter *f;
+	unsigned long index;
 
-	list_for_each_entry_safe(f, n, &head->flist, link) {
-		list_del_rcu(&f->link);
+	xa_for_each(&head->filters, index, f) {
 		tcf_unbind_filter(tp, &f->res);
-		idr_remove(&head->handle_idr, f->handle);
+		xa_erase(&head->filters, index);
 		if (tcf_exts_get_net(&f->exts))
 			tcf_queue_work(&f->rwork, basic_delete_filter_work);
 		else
 			__basic_delete_filter(f);
 	}
-	idr_destroy(&head->handle_idr);
 	kfree_rcu(head, rcu);
 }
 
@@ -128,12 +118,11 @@ static int basic_delete(struct tcf_proto *tp, void *arg, bool *last,
 	struct basic_head *head = rtnl_dereference(tp->root);
 	struct basic_filter *f = arg;
 
-	list_del_rcu(&f->link);
 	tcf_unbind_filter(tp, &f->res);
-	idr_remove(&head->handle_idr, f->handle);
+	xa_erase(&head->filters, f->handle);
 	tcf_exts_get_net(&f->exts);
 	tcf_queue_work(&f->rwork, basic_delete_filter_work);
-	*last = list_empty(&head->flist);
+	*last = xa_empty(&head->filters);
 	return 0;
 }
 
@@ -199,17 +188,16 @@ static int basic_change(struct net *net, struct sk_buff *in_skb,
 	if (err < 0)
 		goto errout;
 
+	fnew->handle = handle;
 	if (!handle) {
-		handle = 1;
-		err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
-				    INT_MAX, GFP_KERNEL);
+		err = xa_alloc(&head->filters, &fnew->handle, fnew,
+				xa_limit_32b, GFP_KERNEL);
 	} else if (!fold) {
-		err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
-				    handle, GFP_KERNEL);
+		err = xa_insert(&head->filters, handle, fnew, GFP_KERNEL);
 	}
 	if (err)
 		goto errout;
-	fnew->handle = handle;
+
 	fnew->pf = alloc_percpu(struct tc_basic_pcnt);
 	if (!fnew->pf) {
 		err = -ENOMEM;
@@ -220,20 +208,17 @@ static int basic_change(struct net *net, struct sk_buff *in_skb,
 			      extack);
 	if (err < 0) {
 		if (!fold)
-			idr_remove(&head->handle_idr, fnew->handle);
+			xa_erase(&head->filters, fnew->handle);
 		goto errout;
 	}
 
 	*arg = fnew;
 
 	if (fold) {
-		idr_replace(&head->handle_idr, fnew, fnew->handle);
-		list_replace_rcu(&fold->link, &fnew->link);
+		xa_store(&head->filters, fnew->handle, fnew, GFP_KERNEL);
 		tcf_unbind_filter(tp, &fold->res);
 		tcf_exts_get_net(&fold->exts);
 		tcf_queue_work(&fold->rwork, basic_delete_filter_work);
-	} else {
-		list_add_rcu(&fnew->link, &head->flist);
 	}
 
 	return 0;
@@ -249,8 +234,9 @@ static void basic_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 {
 	struct basic_head *head = rtnl_dereference(tp->root);
 	struct basic_filter *f;
+	unsigned long index;
 
-	list_for_each_entry(f, &head->flist, link) {
+	xa_for_each(&head->filters, index, f) {
 		if (arg->count < arg->skip)
 			goto skip;
 
-- 
2.23.0.rc1

[PATCH 33/38] act_api: Convert action_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Replace the mutex protecting the IDR with the XArray spinlock.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/net/act_api.h |   6 +-
 net/sched/act_api.c   | 127 +++++++++++++++++-------------------------
 2 files changed, 53 insertions(+), 80 deletions(-)

diff --git a/include/net/act_api.h b/include/net/act_api.h
index c61a1bf4e3de..da1a515fd94d 100644
--- a/include/net/act_api.h
+++ b/include/net/act_api.h
@@ -13,8 +13,7 @@
 #include <net/netns/generic.h>
 
 struct tcf_idrinfo {
-	struct mutex	lock;
-	struct idr	action_idr;
+	struct xarray	actions;
 };
 
 struct tc_action_ops;
@@ -117,8 +116,7 @@ int tc_action_net_init(struct tc_action_net *tn,
 	if (!tn->idrinfo)
 		return -ENOMEM;
 	tn->ops = ops;
-	mutex_init(&tn->idrinfo->lock);
-	idr_init(&tn->idrinfo->action_idr);
+	xa_init_flags(&tn->idrinfo->actions, XA_FLAGS_ALLOC1);
 	return err;
 }
 
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 339712296164..4039ad8c686c 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -126,11 +126,12 @@ static int __tcf_action_put(struct tc_action *p, bool bind)
 {
 	struct tcf_idrinfo *idrinfo = p->idrinfo;
 
-	if (refcount_dec_and_mutex_lock(&p->tcfa_refcnt, &idrinfo->lock)) {
+	if (refcount_dec_and_lock(&p->tcfa_refcnt,
+				&idrinfo->actions.xa_lock)) {
 		if (bind)
 			atomic_dec(&p->tcfa_bindcnt);
-		idr_remove(&idrinfo->action_idr, p->tcfa_index);
-		mutex_unlock(&idrinfo->lock);
+		__xa_erase(&idrinfo->actions, p->tcfa_index);
+		xa_unlock(&idrinfo->actions);
 
 		tcf_action_cleanup(p);
 		return 1;
@@ -214,24 +215,17 @@ static size_t tcf_action_fill_size(const struct tc_action *act)
 static int tcf_dump_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 			   struct netlink_callback *cb)
 {
-	int err = 0, index = -1, s_i = 0, n_i = 0;
+	int err = 0, n_i = 0;
 	u32 act_flags = cb->args[2];
 	unsigned long jiffy_since = cb->args[3];
 	struct nlattr *nest;
-	struct idr *idr = &idrinfo->action_idr;
+	struct xarray *xa = &idrinfo->actions;
 	struct tc_action *p;
-	unsigned long id = 1;
-	unsigned long tmp;
+	unsigned long index;
 
-	mutex_lock(&idrinfo->lock);
-
-	s_i = cb->args[0];
-
-	idr_for_each_entry_ul(idr, p, tmp, id) {
-		index++;
-		if (index < s_i)
-			continue;
+	xa_lock(xa);
 
+	xa_for_each_start(&idrinfo->actions, index, p, cb->args[0]) {
 		if (jiffy_since &&
 		    time_after(jiffy_since,
 			       (unsigned long)p->tcfa_tm.lastuse))
@@ -255,10 +249,9 @@ static int tcf_dump_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 			goto done;
 	}
 done:
-	if (index >= 0)
-		cb->args[0] = index + 1;
+	cb->args[0] = index + 1;
+	xa_unlock(xa);
 
-	mutex_unlock(&idrinfo->lock);
 	if (n_i) {
 		if (act_flags & TCA_FLAG_LARGE_DUMP_ON)
 			cb->args[1] = n_i;
@@ -276,7 +269,7 @@ static int tcf_idr_release_unsafe(struct tc_action *p)
 		return -EPERM;
 
 	if (refcount_dec_and_test(&p->tcfa_refcnt)) {
-		idr_remove(&p->idrinfo->action_idr, p->tcfa_index);
+		xa_erase(&p->idrinfo->actions, p->tcfa_index);
 		tcf_action_cleanup(p);
 		return ACT_P_DELETED;
 	}
@@ -290,10 +283,8 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 	struct nlattr *nest;
 	int n_i = 0;
 	int ret = -EINVAL;
-	struct idr *idr = &idrinfo->action_idr;
 	struct tc_action *p;
-	unsigned long id = 1;
-	unsigned long tmp;
+	unsigned long index;
 
 	nest = nla_nest_start_noflag(skb, 0);
 	if (nest == NULL)
@@ -301,18 +292,18 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 	if (nla_put_string(skb, TCA_KIND, ops->kind))
 		goto nla_put_failure;
 
-	mutex_lock(&idrinfo->lock);
-	idr_for_each_entry_ul(idr, p, tmp, id) {
+	xa_lock(&idrinfo->actions);
+	xa_for_each(&idrinfo->actions, index, p) {
 		ret = tcf_idr_release_unsafe(p);
 		if (ret == ACT_P_DELETED) {
 			module_put(ops->owner);
 			n_i++;
 		} else if (ret < 0) {
-			mutex_unlock(&idrinfo->lock);
+			xa_unlock(&idrinfo->actions);
 			goto nla_put_failure;
 		}
 	}
-	mutex_unlock(&idrinfo->lock);
+	xa_unlock(&idrinfo->actions);
 
 	if (nla_put_u32(skb, TCA_FCNT, n_i))
 		goto nla_put_failure;
@@ -348,13 +339,11 @@ int tcf_idr_search(struct tc_action_net *tn, struct tc_action **a, u32 index)
 	struct tcf_idrinfo *idrinfo = tn->idrinfo;
 	struct tc_action *p;
 
-	mutex_lock(&idrinfo->lock);
-	p = idr_find(&idrinfo->action_idr, index);
-	if (IS_ERR(p))
-		p = NULL;
-	else if (p)
+	xa_lock(&idrinfo->actions);
+	p = xa_load(&idrinfo->actions, index);
+	if (p)
 		refcount_inc(&p->tcfa_refcnt);
-	mutex_unlock(&idrinfo->lock);
+	xa_unlock(&idrinfo->actions);
 
 	if (p) {
 		*a = p;
@@ -369,10 +358,10 @@ static int tcf_idr_delete_index(struct tcf_idrinfo *idrinfo, u32 index)
 	struct tc_action *p;
 	int ret = 0;
 
-	mutex_lock(&idrinfo->lock);
-	p = idr_find(&idrinfo->action_idr, index);
+	xa_lock(&idrinfo->actions);
+	p = xa_load(&idrinfo->actions, index);
 	if (!p) {
-		mutex_unlock(&idrinfo->lock);
+		xa_unlock(&idrinfo->actions);
 		return -ENOENT;
 	}
 
@@ -380,9 +369,8 @@ static int tcf_idr_delete_index(struct tcf_idrinfo *idrinfo, u32 index)
 		if (refcount_dec_and_test(&p->tcfa_refcnt)) {
 			struct module *owner = p->ops->owner;
 
-			WARN_ON(p != idr_remove(&idrinfo->action_idr,
-						p->tcfa_index));
-			mutex_unlock(&idrinfo->lock);
+			__xa_erase(&idrinfo->actions, p->tcfa_index);
+			xa_unlock(&idrinfo->actions);
 
 			tcf_action_cleanup(p);
 			module_put(owner);
@@ -393,7 +381,7 @@ static int tcf_idr_delete_index(struct tcf_idrinfo *idrinfo, u32 index)
 		ret = -EPERM;
 	}
 
-	mutex_unlock(&idrinfo->lock);
+	xa_unlock(&idrinfo->actions);
 	return ret;
 }
 
@@ -455,10 +443,7 @@ void tcf_idr_insert(struct tc_action_net *tn, struct tc_action *a)
 {
 	struct tcf_idrinfo *idrinfo = tn->idrinfo;
 
-	mutex_lock(&idrinfo->lock);
-	/* Replace ERR_PTR(-EBUSY) allocated by tcf_idr_check_alloc */
-	WARN_ON(!IS_ERR(idr_replace(&idrinfo->action_idr, a, a->tcfa_index)));
-	mutex_unlock(&idrinfo->lock);
+	xa_store(&idrinfo->actions, a->tcfa_index, a, GFP_KERNEL);
 }
 EXPORT_SYMBOL(tcf_idr_insert);
 
@@ -468,10 +453,7 @@ void tcf_idr_cleanup(struct tc_action_net *tn, u32 index)
 {
 	struct tcf_idrinfo *idrinfo = tn->idrinfo;
 
-	mutex_lock(&idrinfo->lock);
-	/* Remove ERR_PTR(-EBUSY) allocated by tcf_idr_check_alloc */
-	WARN_ON(!IS_ERR(idr_remove(&idrinfo->action_idr, index)));
-	mutex_unlock(&idrinfo->lock);
+	xa_erase(&idrinfo->actions, index);
 }
 EXPORT_SYMBOL(tcf_idr_cleanup);
 
@@ -489,41 +471,36 @@ int tcf_idr_check_alloc(struct tc_action_net *tn, u32 *index,
 	int ret;
 
 again:
-	mutex_lock(&idrinfo->lock);
+	xa_lock(&idrinfo->actions);
 	if (*index) {
-		p = idr_find(&idrinfo->action_idr, *index);
-		if (IS_ERR(p)) {
-			/* This means that another process allocated
-			 * index but did not assign the pointer yet.
-			 */
-			mutex_unlock(&idrinfo->lock);
-			goto again;
-		}
-
+		p = xa_load(&idrinfo->actions, *index);
 		if (p) {
 			refcount_inc(&p->tcfa_refcnt);
 			if (bind)
 				atomic_inc(&p->tcfa_bindcnt);
-			*a = p;
 			ret = 1;
 		} else {
 			*a = NULL;
-			ret = idr_alloc_u32(&idrinfo->action_idr, NULL, index,
-					    *index, GFP_KERNEL);
-			if (!ret)
-				idr_replace(&idrinfo->action_idr,
-					    ERR_PTR(-EBUSY), *index);
+			ret = __xa_insert(&idrinfo->actions, *index, NULL,
+					    GFP_KERNEL);
+			if (ret == -EBUSY) {
+				/*
+				 * Another process has allocated this index,
+				 * but has not yet assigned a pointer.
+				 */
+				xa_unlock(&idrinfo->actions);
+				cpu_relax();
+				goto again;
+			}
 		}
 	} else {
-		*index = 1;
-		*a = NULL;
-		ret = idr_alloc_u32(&idrinfo->action_idr, NULL, index,
-				    UINT_MAX, GFP_KERNEL);
-		if (!ret)
-			idr_replace(&idrinfo->action_idr, ERR_PTR(-EBUSY),
-				    *index);
+		ret = __xa_alloc(&idrinfo->actions, index, NULL, xa_limit_32b,
+				GFP_KERNEL);
+		p = NULL;
 	}
-	mutex_unlock(&idrinfo->lock);
+
+	*a = p;
+	xa_unlock(&idrinfo->actions);
 	return ret;
 }
 EXPORT_SYMBOL(tcf_idr_check_alloc);
@@ -531,20 +508,18 @@ EXPORT_SYMBOL(tcf_idr_check_alloc);
 void tcf_idrinfo_destroy(const struct tc_action_ops *ops,
 			 struct tcf_idrinfo *idrinfo)
 {
-	struct idr *idr = &idrinfo->action_idr;
 	struct tc_action *p;
 	int ret;
-	unsigned long id = 1;
-	unsigned long tmp;
+	unsigned long index;
 
-	idr_for_each_entry_ul(idr, p, tmp, id) {
+	xa_for_each(&idrinfo->actions, index, p) {
 		ret = __tcf_idr_release(p, false, true);
 		if (ret == ACT_P_DELETED)
 			module_put(ops->owner);
 		else if (ret < 0)
 			return;
 	}
-	idr_destroy(&idrinfo->action_idr);
+	xa_destroy(&idrinfo->actions);
 }
 EXPORT_SYMBOL(tcf_idrinfo_destroy);
 
-- 
2.23.0.rc1

[PATCH 34/38] net_namespace: Convert netns_ids to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

This is a straightforward conversion; it should be possible to eliminate
nsid_lock as it seems to only be used to protect netns_ids.  The tricky
part is that dropping the lock (eg to allocate memory) could end up
allowing two networks which are equal to each other being allocated.
So stick with the GFP_ATOMIC allocations and double locking until
someone who's more savvy wants to try their hand at eliminating it.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 include/net/net_namespace.h |  2 +-
 net/core/net_namespace.c    | 65 +++++++++++++++++--------------------
 2 files changed, 30 insertions(+), 37 deletions(-)

diff --git a/include/net/net_namespace.h b/include/net/net_namespace.h
index 4a9da951a794..6c80cadc6396 100644
--- a/include/net/net_namespace.h
+++ b/include/net/net_namespace.h
@@ -78,7 +78,7 @@ struct net {
 	struct user_namespace   *user_ns;	/* Owning user namespace */
 	struct ucounts		*ucounts;
 	spinlock_t		nsid_lock;
-	struct idr		netns_ids;
+	struct xarray		netns_ids;
 
 	struct ns_common	ns;
 
diff --git a/net/core/net_namespace.c b/net/core/net_namespace.c
index a0e0d298c991..c9b16e1b4a7e 100644
--- a/net/core/net_namespace.c
+++ b/net/core/net_namespace.c
@@ -188,27 +188,18 @@ static void ops_free_list(const struct pernet_operations *ops,
 /* should be called with nsid_lock held */
 static int alloc_netid(struct net *net, struct net *peer, int reqid)
 {
-	int min = 0, max = 0;
+	int ret;
 
 	if (reqid >= 0) {
-		min = reqid;
-		max = reqid + 1;
+		ret = xa_insert(&net->netns_ids, reqid, peer, GFP_ATOMIC);
+	} else {
+		ret = xa_alloc(&net->netns_ids, &reqid, peer, xa_limit_31b,
+				GFP_ATOMIC);
 	}
 
-	return idr_alloc(&net->netns_ids, peer, min, max, GFP_ATOMIC);
-}
-
-/* This function is used by idr_for_each(). If net is equal to peer, the
- * function returns the id so that idr_for_each() stops. Because we cannot
- * returns the id 0 (idr_for_each() will not stop), we return the magic value
- * NET_ID_ZERO (-1) for it.
- */
-#define NET_ID_ZERO -1
-static int net_eq_idr(int id, void *net, void *peer)
-{
-	if (net_eq(net, peer))
-		return id ? : NET_ID_ZERO;
-	return 0;
+	if (ret)
+		return ret;
+	return reqid;
 }
 
 /* Should be called with nsid_lock held. If a new id is assigned, the bool alloc
@@ -217,16 +208,17 @@ static int net_eq_idr(int id, void *net, void *peer)
  */
 static int __peernet2id_alloc(struct net *net, struct net *peer, bool *alloc)
 {
-	int id = idr_for_each(&net->netns_ids, net_eq_idr, peer);
+	int id;
+	struct net *tmp;
+	unsigned long index;
 	bool alloc_it = *alloc;
 
-	*alloc = false;
-
-	/* Magic value for id 0. */
-	if (id == NET_ID_ZERO)
-		return 0;
-	if (id > 0)
-		return id;
+	xa_for_each(&net->netns_ids, index, tmp) {
+		if (net_eq(tmp, peer)) {
+			*alloc = false;
+			return index;
+		}
+	}
 
 	if (alloc_it) {
 		id = alloc_netid(net, peer, -1);
@@ -261,7 +253,7 @@ int peernet2id_alloc(struct net *net, struct net *peer)
 	 * When peer is obtained from RCU lists, we may race with
 	 * its cleanup. Check whether it's alive, and this guarantees
 	 * we never hash a peer back to net->netns_ids, after it has
-	 * just been idr_remove()'d from there in cleanup_net().
+	 * just been removed from there in cleanup_net().
 	 */
 	if (maybe_get_net(peer))
 		alive = alloc = true;
@@ -303,7 +295,7 @@ struct net *get_net_ns_by_id(struct net *net, int id)
 		return NULL;
 
 	rcu_read_lock();
-	peer = idr_find(&net->netns_ids, id);
+	peer = xa_load(&net->netns_ids, id);
 	if (peer)
 		peer = maybe_get_net(peer);
 	rcu_read_unlock();
@@ -326,7 +318,7 @@ static __net_init int setup_net(struct net *net, struct user_namespace *user_ns)
 	get_random_bytes(&net->hash_mix, sizeof(u32));
 	net->dev_base_seq = 1;
 	net->user_ns = user_ns;
-	idr_init(&net->netns_ids);
+	xa_init_flags(&net->netns_ids, XA_FLAGS_ALLOC);
 	spin_lock_init(&net->nsid_lock);
 	mutex_init(&net->ipv4.ra_mutex);
 
@@ -529,16 +521,14 @@ static void unhash_nsid(struct net *net, struct net *last)
 		spin_lock_bh(&tmp->nsid_lock);
 		id = __peernet2id(tmp, net);
 		if (id >= 0)
-			idr_remove(&tmp->netns_ids, id);
+			xa_erase(&tmp->netns_ids, id);
 		spin_unlock_bh(&tmp->nsid_lock);
 		if (id >= 0)
 			rtnl_net_notifyid(tmp, RTM_DELNSID, id);
 		if (tmp == last)
 			break;
 	}
-	spin_lock_bh(&net->nsid_lock);
-	idr_destroy(&net->netns_ids);
-	spin_unlock_bh(&net->nsid_lock);
+	BUG_ON(!xa_empty(&net->netns_ids));
 }
 
 static LLIST_HEAD(cleanup_list);
@@ -766,7 +756,7 @@ static int rtnl_net_newid(struct sk_buff *skb, struct nlmsghdr *nlh,
 	if (err >= 0) {
 		rtnl_net_notifyid(net, RTM_NEWNSID, err);
 		err = 0;
-	} else if (err == -ENOSPC && nsid >= 0) {
+	} else if (err == -EBUSY && nsid >= 0) {
 		err = -EEXIST;
 		NL_SET_BAD_ATTR(extack, tb[NETNSA_NSID]);
 		NL_SET_ERR_MSG(extack, "The specified nsid is already used");
@@ -946,9 +936,9 @@ struct rtnl_net_dump_cb {
 	int s_idx;
 };
 
-static int rtnl_net_dumpid_one(int id, void *peer, void *data)
+static int rtnl_net_dumpid_one(int id, struct net *peer,
+		struct rtnl_net_dump_cb *net_cb)
 {
-	struct rtnl_net_dump_cb *net_cb = (struct rtnl_net_dump_cb *)data;
 	int ret;
 
 	if (net_cb->idx < net_cb->s_idx)
@@ -1022,6 +1012,8 @@ static int rtnl_net_dumpid(struct sk_buff *skb, struct netlink_callback *cb)
 		.idx = 0,
 		.s_idx = cb->args[0],
 	};
+	struct net *peer;
+	unsigned long index;
 	int err = 0;
 
 	if (cb->strict_check) {
@@ -1038,7 +1030,8 @@ static int rtnl_net_dumpid(struct sk_buff *skb, struct netlink_callback *cb)
 		err = -EAGAIN;
 		goto end;
 	}
-	idr_for_each(&net_cb.tgt_net->netns_ids, rtnl_net_dumpid_one, &net_cb);
+	xa_for_each(&net_cb.tgt_net->netns_ids, index, peer)
+		rtnl_net_dumpid_one(index, peer, &net_cb);
 	if (net_cb.fillargs.add_ref &&
 	    !net_eq(net_cb.ref_net, net_cb.tgt_net))
 		spin_unlock_bh(&net_cb.ref_net->nsid_lock);
-- 
2.23.0.rc1

[PATCH 35/38] tipc: Convert conn_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Replace idr_lock with the internal XArray lock.  The idr_in_use
counter isn't needed as we can free all the elements in the array
without it.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/tipc/topsrv.c | 49 ++++++++++++++---------------------------------
 1 file changed, 14 insertions(+), 35 deletions(-)

diff --git a/net/tipc/topsrv.c b/net/tipc/topsrv.c
index 3a12fc18239b..72b3180e0ea5 100644
--- a/net/tipc/topsrv.c
+++ b/net/tipc/topsrv.c
@@ -54,9 +54,7 @@
 
 /**
  * struct tipc_topsrv - TIPC server structure
- * @conn_idr: identifier set of connection
- * @idr_lock: protect the connection identifier set
- * @idr_in_use: amount of allocated identifier entry
+ * @conns: identifier set of connection
  * @net: network namspace instance
  * @awork: accept work item
  * @rcv_wq: receive workqueue
@@ -65,9 +63,7 @@
  * @name: server name
  */
 struct tipc_topsrv {
-	struct idr conn_idr;
-	spinlock_t idr_lock; /* for idr list */
-	int idr_in_use;
+	struct xarray conns;
 	struct net *net;
 	struct work_struct awork;
 	struct workqueue_struct *rcv_wq;
@@ -127,10 +123,7 @@ static void tipc_conn_kref_release(struct kref *kref)
 	struct tipc_topsrv *s = con->server;
 	struct outqueue_entry *e, *safe;
 
-	spin_lock_bh(&s->idr_lock);
-	idr_remove(&s->conn_idr, con->conid);
-	s->idr_in_use--;
-	spin_unlock_bh(&s->idr_lock);
+	xa_erase_bh(&s->conns, con->conid);
 	if (con->sock)
 		sock_release(con->sock);
 
@@ -194,16 +187,12 @@ static struct tipc_conn *tipc_conn_alloc(struct tipc_topsrv *s)
 	INIT_WORK(&con->swork, tipc_conn_send_work);
 	INIT_WORK(&con->rwork, tipc_conn_recv_work);
 
-	spin_lock_bh(&s->idr_lock);
-	ret = idr_alloc(&s->conn_idr, con, 0, 0, GFP_ATOMIC);
+	ret = xa_alloc_bh(&s->conns, &con->conid, con, xa_limit_32b,
+			GFP_ATOMIC);
 	if (ret < 0) {
 		kfree(con);
-		spin_unlock_bh(&s->idr_lock);
 		return ERR_PTR(-ENOMEM);
 	}
-	con->conid = ret;
-	s->idr_in_use++;
-	spin_unlock_bh(&s->idr_lock);
 
 	set_bit(CF_CONNECTED, &con->flags);
 	con->server = s;
@@ -215,11 +204,11 @@ static struct tipc_conn *tipc_conn_lookup(struct tipc_topsrv *s, int conid)
 {
 	struct tipc_conn *con;
 
-	spin_lock_bh(&s->idr_lock);
-	con = idr_find(&s->conn_idr, conid);
+	xa_lock_bh(&s->conns);
+	con = xa_load(&s->conns, conid);
 	if (!connected(con) || !kref_get_unless_zero(&con->kref))
 		con = NULL;
-	spin_unlock_bh(&s->idr_lock);
+	xa_unlock_bh(&s->conns);
 	return con;
 }
 
@@ -655,9 +644,7 @@ static int tipc_topsrv_start(struct net *net)
 	tn->topsrv = srv;
 	atomic_set(&tn->subscription_count, 0);
 
-	spin_lock_init(&srv->idr_lock);
-	idr_init(&srv->conn_idr);
-	srv->idr_in_use = 0;
+	xa_init_flags(&srv->conns, XA_FLAGS_ALLOC | XA_FLAGS_LOCK_BH);
 
 	ret = tipc_topsrv_work_start(srv);
 	if (ret < 0)
@@ -675,24 +662,16 @@ static void tipc_topsrv_stop(struct net *net)
 	struct tipc_topsrv *srv = tipc_topsrv(net);
 	struct socket *lsock = srv->listener;
 	struct tipc_conn *con;
-	int id;
-
-	spin_lock_bh(&srv->idr_lock);
-	for (id = 0; srv->idr_in_use; id++) {
-		con = idr_find(&srv->conn_idr, id);
-		if (con) {
-			spin_unlock_bh(&srv->idr_lock);
-			tipc_conn_close(con);
-			spin_lock_bh(&srv->idr_lock);
-		}
-	}
+	unsigned long id;
+
+	xa_for_each(&srv->conns, id, con)
+		tipc_conn_close(con);
+
 	__module_get(lsock->ops->owner);
 	__module_get(lsock->sk->sk_prot_creator->owner);
 	srv->listener = NULL;
-	spin_unlock_bh(&srv->idr_lock);
 	sock_release(lsock);
 	tipc_topsrv_work_stop(srv);
-	idr_destroy(&srv->conn_idr);
 	kfree(srv);
 }
 
-- 
2.23.0.rc1

[PATCH 36/38] netlink: Convert genl_fam_idr to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Straightforward conversion without touching the locking.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/netlink/genetlink.c | 46 +++++++++++++++++------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)

diff --git a/net/netlink/genetlink.c b/net/netlink/genetlink.c
index efccd1ac9a66..02f5c7453f84 100644
--- a/net/netlink/genetlink.c
+++ b/net/netlink/genetlink.c
@@ -18,7 +18,7 @@
 #include <linux/mutex.h>
 #include <linux/bitmap.h>
 #include <linux/rwsem.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 #include <net/sock.h>
 #include <net/genetlink.h>
 
@@ -60,7 +60,8 @@ static void genl_unlock_all(void)
 	up_write(&cb_lock);
 }
 
-static DEFINE_IDR(genl_fam_idr);
+static unsigned int genl_families_next;
+static DEFINE_XARRAY_ALLOC(genl_families);
 
 /*
  * Bitmap of multicast groups that are currently in use.
@@ -92,15 +93,15 @@ static int genl_ctrl_event(int event, const struct genl_family *family,
 
 static const struct genl_family *genl_family_find_byid(unsigned int id)
 {
-	return idr_find(&genl_fam_idr, id);
+	return xa_load(&genl_families, id);
 }
 
 static const struct genl_family *genl_family_find_byname(char *name)
 {
 	const struct genl_family *family;
-	unsigned int id;
+	unsigned long id;
 
-	idr_for_each_entry(&genl_fam_idr, family, id)
+	xa_for_each(&genl_families, id, family)
 		if (strcmp(family->name, name) == 0)
 			return family;
 
@@ -362,12 +363,10 @@ int genl_register_family(struct genl_family *family)
 	} else
 		family->attrbuf = NULL;
 
-	family->id = idr_alloc_cyclic(&genl_fam_idr, family,
-				      start, end + 1, GFP_KERNEL);
-	if (family->id < 0) {
-		err = family->id;
+	err = xa_alloc_cyclic(&genl_families, &family->id, family,
+			XA_LIMIT(start, end), &genl_families_next, GFP_KERNEL);
+	if (err < 0)
 		goto errout_free;
-	}
 
 	err = genl_validate_assign_mc_groups(family);
 	if (err)
@@ -384,7 +383,7 @@ int genl_register_family(struct genl_family *family)
 	return 0;
 
 errout_remove:
-	idr_remove(&genl_fam_idr, family->id);
+	xa_erase(&genl_families, family->id);
 errout_free:
 	kfree(family->attrbuf);
 errout_locked:
@@ -412,7 +411,7 @@ int genl_unregister_family(const struct genl_family *family)
 
 	genl_unregister_mc_groups(family);
 
-	idr_remove(&genl_fam_idr, family->id);
+	xa_erase(&genl_families, family->id);
 
 	up_write(&cb_lock);
 	wait_event(genl_sk_destructing_waitq,
@@ -802,28 +801,21 @@ static int ctrl_fill_mcgrp_info(const struct genl_family *family,
 
 static int ctrl_dumpfamily(struct sk_buff *skb, struct netlink_callback *cb)
 {
-	int n = 0;
 	struct genl_family *rt;
 	struct net *net = sock_net(skb->sk);
-	int fams_to_skip = cb->args[0];
-	unsigned int id;
+	unsigned long id;
 
-	idr_for_each_entry(&genl_fam_idr, rt, id) {
+	xa_for_each_start(&genl_families, id, rt, cb->args[0]) {
 		if (!rt->netnsok && !net_eq(net, &init_net))
 			continue;
 
-		if (n++ < fams_to_skip)
-			continue;
-
 		if (ctrl_fill_info(rt, NETLINK_CB(cb->skb).portid,
 				   cb->nlh->nlmsg_seq, NLM_F_MULTI,
-				   skb, CTRL_CMD_NEWFAMILY) < 0) {
-			n--;
+				   skb, CTRL_CMD_NEWFAMILY) < 0)
 			break;
-		}
 	}
 
-	cb->args[0] = n;
+	cb->args[0] = id;
 	return skb->len;
 }
 
@@ -993,11 +985,11 @@ static int genl_bind(struct net *net, int group)
 {
 	struct genl_family *f;
 	int err = -ENOENT;
-	unsigned int id;
+	unsigned long id;
 
 	down_read(&cb_lock);
 
-	idr_for_each_entry(&genl_fam_idr, f, id) {
+	xa_for_each(&genl_families, id, f) {
 		if (group >= f->mcgrp_offset &&
 		    group < f->mcgrp_offset + f->n_mcgrps) {
 			int fam_grp = group - f->mcgrp_offset;
@@ -1019,11 +1011,11 @@ static int genl_bind(struct net *net, int group)
 static void genl_unbind(struct net *net, int group)
 {
 	struct genl_family *f;
-	unsigned int id;
+	unsigned long id;
 
 	down_read(&cb_lock);
 
-	idr_for_each_entry(&genl_fam_idr, f, id) {
+	xa_for_each(&genl_families, id, f) {
 		if (group >= f->mcgrp_offset &&
 		    group < f->mcgrp_offset + f->n_mcgrps) {
 			int fam_grp = group - f->mcgrp_offset;
-- 
2.23.0.rc1

[PATCH 37/38] mac80211: Convert ack_status_frames to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Replace the ack_status_lock with the XArray internal lock.  Using the
xa_for_each() iterator lets us inline ieee80211_free_ack_frame().

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/mac80211/cfg.c         | 13 ++++++-------
 net/mac80211/ieee80211_i.h |  3 +--
 net/mac80211/main.c        | 20 ++++++++------------
 net/mac80211/status.c      |  6 +++---
 net/mac80211/tx.c          | 16 ++++++++--------
 5 files changed, 26 insertions(+), 32 deletions(-)

diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c
index ed56b0c6fe19..47d7670094a9 100644
--- a/net/mac80211/cfg.c
+++ b/net/mac80211/cfg.c
@@ -3425,24 +3425,23 @@ int ieee80211_attach_ack_skb(struct ieee80211_local *local, struct sk_buff *skb,
 {
 	unsigned long spin_flags;
 	struct sk_buff *ack_skb;
-	int id;
+	int err, id;
 
 	ack_skb = skb_copy(skb, gfp);
 	if (!ack_skb)
 		return -ENOMEM;
 
-	spin_lock_irqsave(&local->ack_status_lock, spin_flags);
-	id = idr_alloc(&local->ack_status_frames, ack_skb,
-		       1, 0x10000, GFP_ATOMIC);
-	spin_unlock_irqrestore(&local->ack_status_lock, spin_flags);
+	xa_lock_irqsave(&local->ack_status_frames, spin_flags);
+	err = __xa_alloc(&local->ack_status_frames, &id, ack_skb,
+			XA_LIMIT(0, 0xffff), GFP_ATOMIC);
+	xa_unlock_irqrestore(&local->ack_status_frames, spin_flags);
 
-	if (id < 0) {
+	if (err < 0) {
 		kfree_skb(ack_skb);
 		return -ENOMEM;
 	}
 
 	IEEE80211_SKB_CB(skb)->ack_frame_id = id;
-
 	*cookie = ieee80211_mgmt_tx_cookie(local);
 	IEEE80211_SKB_CB(ack_skb)->ack.cookie = *cookie;
 
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index 791ce58d0f09..ade005892099 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -1393,8 +1393,7 @@ struct ieee80211_local {
 	unsigned long hw_roc_start_time;
 	u64 roc_cookie_counter;
 
-	struct idr ack_status_frames;
-	spinlock_t ack_status_lock;
+	struct xarray ack_status_frames;
 
 	struct ieee80211_sub_if_data __rcu *p2p_sdata;
 
diff --git a/net/mac80211/main.c b/net/mac80211/main.c
index 29b9d57df1a3..0d46aa52368a 100644
--- a/net/mac80211/main.c
+++ b/net/mac80211/main.c
@@ -693,8 +693,7 @@ struct ieee80211_hw *ieee80211_alloc_hw_nm(size_t priv_data_len,
 
 	INIT_WORK(&local->tdls_chsw_work, ieee80211_tdls_chsw_work);
 
-	spin_lock_init(&local->ack_status_lock);
-	idr_init(&local->ack_status_frames);
+	xa_init_flags(&local->ack_status_frames, XA_FLAGS_ALLOC1);
 
 	for (i = 0; i < IEEE80211_MAX_QUEUES; i++) {
 		skb_queue_head_init(&local->pending[i]);
@@ -1353,16 +1352,11 @@ void ieee80211_unregister_hw(struct ieee80211_hw *hw)
 }
 EXPORT_SYMBOL(ieee80211_unregister_hw);
 
-static int ieee80211_free_ack_frame(int id, void *p, void *data)
-{
-	WARN_ONCE(1, "Have pending ack frames!\n");
-	kfree_skb(p);
-	return 0;
-}
-
 void ieee80211_free_hw(struct ieee80211_hw *hw)
 {
 	struct ieee80211_local *local = hw_to_local(hw);
+	struct sk_buff *skb;
+	unsigned long index;
 	enum nl80211_band band;
 
 	mutex_destroy(&local->iflist_mtx);
@@ -1371,9 +1365,11 @@ void ieee80211_free_hw(struct ieee80211_hw *hw)
 	if (local->wiphy_ciphers_allocated)
 		kfree(local->hw.wiphy->cipher_suites);
 
-	idr_for_each(&local->ack_status_frames,
-		     ieee80211_free_ack_frame, NULL);
-	idr_destroy(&local->ack_status_frames);
+	xa_for_each(&local->ack_status_frames, index, skb) {
+		WARN_ONCE(1, "Have pending ack frames!\n");
+		kfree_skb(skb);
+	}
+	xa_destroy(&local->ack_status_frames);
 
 	sta_info_stop(local);
 
diff --git a/net/mac80211/status.c b/net/mac80211/status.c
index f03aa8924d23..8f38af968941 100644
--- a/net/mac80211/status.c
+++ b/net/mac80211/status.c
@@ -619,9 +619,9 @@ static void ieee80211_report_ack_skb(struct ieee80211_local *local,
 	struct sk_buff *skb;
 	unsigned long flags;
 
-	spin_lock_irqsave(&local->ack_status_lock, flags);
-	skb = idr_remove(&local->ack_status_frames, info->ack_frame_id);
-	spin_unlock_irqrestore(&local->ack_status_lock, flags);
+	xa_lock_irqsave(&local->ack_status_frames, flags);
+	skb = __xa_erase(&local->ack_status_frames, info->ack_frame_id);
+	xa_unlock_irqrestore(&local->ack_status_frames, flags);
 
 	if (!skb)
 		return;
diff --git a/net/mac80211/tx.c b/net/mac80211/tx.c
index 235c6377a203..a7c0e3a0dbfb 100644
--- a/net/mac80211/tx.c
+++ b/net/mac80211/tx.c
@@ -2459,7 +2459,7 @@ static struct sk_buff *ieee80211_build_hdr(struct ieee80211_sub_if_data *sdata,
 	bool wme_sta = false, authorized = false;
 	bool tdls_peer;
 	bool multicast;
-	u16 info_id = 0;
+	u32 info_id = 0;
 	struct ieee80211_chanctx_conf *chanctx_conf;
 	struct ieee80211_sub_if_data *ap_sdata;
 	enum nl80211_band band;
@@ -2721,15 +2721,15 @@ static struct sk_buff *ieee80211_build_hdr(struct ieee80211_sub_if_data *sdata,
 
 		if (ack_skb) {
 			unsigned long flags;
-			int id;
+			int err;
 
-			spin_lock_irqsave(&local->ack_status_lock, flags);
-			id = idr_alloc(&local->ack_status_frames, ack_skb,
-				       1, 0x10000, GFP_ATOMIC);
-			spin_unlock_irqrestore(&local->ack_status_lock, flags);
+			xa_lock_irqsave(&local->ack_status_frames, flags);
+			err = __xa_alloc(&local->ack_status_frames, &info_id,
+					ack_skb, XA_LIMIT(0, 0xffff),
+					GFP_ATOMIC);
+			xa_unlock_irqrestore(&local->ack_status_frames, flags);
 
-			if (id >= 0) {
-				info_id = id;
+			if (!err) {
 				info_flags |= IEEE80211_TX_CTL_REQ_TX_STATUS;
 			} else {
 				kfree_skb(ack_skb);
-- 
2.23.0.rc1

[PATCH 38/38] mac80211: Convert function_inst_ids to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

Replae the func_lock with the internal XArray spinlock.  Ensuring that
nan_func is fully initialised before dropping the lock allows us to
iterate the array while not holding the lock, avoiding the awkward dance
in ieee80211_reconfig_nan().

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 net/mac80211/cfg.c         | 57 ++++++++++++++------------------------
 net/mac80211/ieee80211_i.h |  9 ++----
 net/mac80211/iface.c       | 16 +++++------
 net/mac80211/util.c        | 30 ++++----------------
 4 files changed, 37 insertions(+), 75 deletions(-)

diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c
index 47d7670094a9..2ea45b7007db 100644
--- a/net/mac80211/cfg.c
+++ b/net/mac80211/cfg.c
@@ -266,7 +266,7 @@ static int ieee80211_add_nan_func(struct wiphy *wiphy,
 				  struct cfg80211_nan_func *nan_func)
 {
 	struct ieee80211_sub_if_data *sdata = IEEE80211_WDEV_TO_SUB_IF(wdev);
-	int ret;
+	int ret, id;
 
 	if (sdata->vif.type != NL80211_IFTYPE_NAN)
 		return -EOPNOTSUPP;
@@ -274,27 +274,22 @@ static int ieee80211_add_nan_func(struct wiphy *wiphy,
 	if (!ieee80211_sdata_running(sdata))
 		return -ENETDOWN;
 
-	spin_lock_bh(&sdata->u.nan.func_lock);
-
-	ret = idr_alloc(&sdata->u.nan.function_inst_ids,
-			nan_func, 1, sdata->local->hw.max_nan_de_entries + 1,
-			GFP_ATOMIC);
-	spin_unlock_bh(&sdata->u.nan.func_lock);
+	xa_lock_bh(&sdata->u.nan.functions);
+	ret = __xa_alloc(&sdata->u.nan.functions, &id, nan_func,
+			XA_LIMIT(0, sdata->local->hw.max_nan_de_entries),
+			GFP_KERNEL);
+	if (ret == 0)
+		nan_func->instance_id = id;
+	xa_unlock_bh(&sdata->u.nan.functions);
 
 	if (ret < 0)
 		return ret;
 
-	nan_func->instance_id = ret;
-
 	WARN_ON(nan_func->instance_id == 0);
 
 	ret = drv_add_nan_func(sdata->local, sdata, nan_func);
-	if (ret) {
-		spin_lock_bh(&sdata->u.nan.func_lock);
-		idr_remove(&sdata->u.nan.function_inst_ids,
-			   nan_func->instance_id);
-		spin_unlock_bh(&sdata->u.nan.func_lock);
-	}
+	if (ret)
+		xa_erase_bh(&sdata->u.nan.functions, nan_func->instance_id);
 
 	return ret;
 }
@@ -304,11 +299,11 @@ ieee80211_find_nan_func_by_cookie(struct ieee80211_sub_if_data *sdata,
 				  u64 cookie)
 {
 	struct cfg80211_nan_func *func;
-	int id;
+	unsigned long id;
 
-	lockdep_assert_held(&sdata->u.nan.func_lock);
+	lockdep_assert_held(&sdata->u.nan.functions.xa_lock);
 
-	idr_for_each_entry(&sdata->u.nan.function_inst_ids, func, id) {
+	xa_for_each(&sdata->u.nan.functions, id, func) {
 		if (func->cookie == cookie)
 			return func;
 	}
@@ -327,13 +322,13 @@ static void ieee80211_del_nan_func(struct wiphy *wiphy,
 	    !ieee80211_sdata_running(sdata))
 		return;
 
-	spin_lock_bh(&sdata->u.nan.func_lock);
+	xa_lock_bh(&sdata->u.nan.functions);
 
 	func = ieee80211_find_nan_func_by_cookie(sdata, cookie);
 	if (func)
 		instance_id = func->instance_id;
 
-	spin_unlock_bh(&sdata->u.nan.func_lock);
+	xa_unlock_bh(&sdata->u.nan.functions);
 
 	if (instance_id)
 		drv_del_nan_func(sdata->local, sdata, instance_id);
@@ -3766,19 +3761,11 @@ void ieee80211_nan_func_terminated(struct ieee80211_vif *vif,
 	if (WARN_ON(vif->type != NL80211_IFTYPE_NAN))
 		return;
 
-	spin_lock_bh(&sdata->u.nan.func_lock);
-
-	func = idr_find(&sdata->u.nan.function_inst_ids, inst_id);
-	if (WARN_ON(!func)) {
-		spin_unlock_bh(&sdata->u.nan.func_lock);
+	func = xa_erase_bh(&sdata->u.nan.functions, inst_id);
+	if (WARN_ON(!func))
 		return;
-	}
 
 	cookie = func->cookie;
-	idr_remove(&sdata->u.nan.function_inst_ids, inst_id);
-
-	spin_unlock_bh(&sdata->u.nan.func_lock);
-
 	cfg80211_free_nan_func(func);
 
 	cfg80211_nan_func_terminated(ieee80211_vif_to_wdev(vif), inst_id,
@@ -3796,16 +3783,14 @@ void ieee80211_nan_func_match(struct ieee80211_vif *vif,
 	if (WARN_ON(vif->type != NL80211_IFTYPE_NAN))
 		return;
 
-	spin_lock_bh(&sdata->u.nan.func_lock);
-
-	func = idr_find(&sdata->u.nan.function_inst_ids,  match->inst_id);
+	xa_lock_bh(&sdata->u.nan.functions);
+	func = xa_load(&sdata->u.nan.functions,  match->inst_id);
 	if (WARN_ON(!func)) {
-		spin_unlock_bh(&sdata->u.nan.func_lock);
+		xa_unlock_bh(&sdata->u.nan.functions);
 		return;
 	}
 	match->cookie = func->cookie;
-
-	spin_unlock_bh(&sdata->u.nan.func_lock);
+	xa_unlock_bh(&sdata->u.nan.functions);
 
 	cfg80211_nan_match(ieee80211_vif_to_wdev(vif), match, gfp);
 }
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index ade005892099..7be25939a6bf 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -23,7 +23,7 @@
 #include <linux/spinlock.h>
 #include <linux/etherdevice.h>
 #include <linux/leds.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 #include <linux/rhashtable.h>
 #include <net/ieee80211_radiotap.h>
 #include <net/cfg80211.h>
@@ -862,14 +862,11 @@ struct ieee80211_if_mntr {
  * struct ieee80211_if_nan - NAN state
  *
  * @conf: current NAN configuration
- * @func_ids: a bitmap of available instance_id's
+ * @functions: NAN function pointers
  */
 struct ieee80211_if_nan {
 	struct cfg80211_nan_conf conf;
-
-	/* protects function_inst_ids */
-	spinlock_t func_lock;
-	struct idr function_inst_ids;
+	struct xarray functions;
 };
 
 struct ieee80211_sub_if_data {
diff --git a/net/mac80211/iface.c b/net/mac80211/iface.c
index 8dc6580e1787..022e2eb6a46c 100644
--- a/net/mac80211/iface.c
+++ b/net/mac80211/iface.c
@@ -802,6 +802,7 @@ static void ieee80211_do_stop(struct ieee80211_sub_if_data *sdata,
 	struct cfg80211_chan_def chandef;
 	bool cancel_scan;
 	struct cfg80211_nan_func *func;
+	unsigned long index;
 
 	clear_bit(SDATA_STATE_RUNNING, &sdata->state);
 
@@ -961,15 +962,12 @@ static void ieee80211_do_stop(struct ieee80211_sub_if_data *sdata,
 		break;
 	case NL80211_IFTYPE_NAN:
 		/* clean all the functions */
-		spin_lock_bh(&sdata->u.nan.func_lock);
-
-		idr_for_each_entry(&sdata->u.nan.function_inst_ids, func, i) {
-			idr_remove(&sdata->u.nan.function_inst_ids, i);
+		xa_lock_bh(&sdata->u.nan.functions);
+		xa_for_each(&sdata->u.nan.functions, index, func) {
+			__xa_erase(&sdata->u.nan.functions, index);
 			cfg80211_free_nan_func(func);
 		}
-		idr_destroy(&sdata->u.nan.function_inst_ids);
-
-		spin_unlock_bh(&sdata->u.nan.func_lock);
+		xa_unlock_bh(&sdata->u.nan.functions);
 		break;
 	case NL80211_IFTYPE_P2P_DEVICE:
 		/* relies on synchronize_rcu() below */
@@ -1463,8 +1461,8 @@ static void ieee80211_setup_sdata(struct ieee80211_sub_if_data *sdata,
 		sdata->vif.bss_conf.bssid = NULL;
 		break;
 	case NL80211_IFTYPE_NAN:
-		idr_init(&sdata->u.nan.function_inst_ids);
-		spin_lock_init(&sdata->u.nan.func_lock);
+		xa_init_flags(&sdata->u.nan.functions,
+				XA_FLAGS_ALLOC1 | XA_FLAGS_LOCK_BH);
 		sdata->vif.bss_conf.bssid = sdata->vif.addr;
 		break;
 	case NL80211_IFTYPE_AP_VLAN:
diff --git a/net/mac80211/util.c b/net/mac80211/util.c
index 286c7ee35e63..4996a3c01205 100644
--- a/net/mac80211/util.c
+++ b/net/mac80211/util.c
@@ -2082,42 +2082,24 @@ static void ieee80211_reconfig_stations(struct ieee80211_sub_if_data *sdata)
 
 static int ieee80211_reconfig_nan(struct ieee80211_sub_if_data *sdata)
 {
-	struct cfg80211_nan_func *func, **funcs;
-	int res, id, i = 0;
+	struct cfg80211_nan_func *func;
+	unsigned long id;
+	int res;
 
 	res = drv_start_nan(sdata->local, sdata,
 			    &sdata->u.nan.conf);
 	if (WARN_ON(res))
 		return res;
 
-	funcs = kcalloc(sdata->local->hw.max_nan_de_entries + 1,
-			sizeof(*funcs),
-			GFP_KERNEL);
-	if (!funcs)
-		return -ENOMEM;
-
-	/* Add all the functions:
-	 * This is a little bit ugly. We need to call a potentially sleeping
-	 * callback for each NAN function, so we can't hold the spinlock.
-	 */
-	spin_lock_bh(&sdata->u.nan.func_lock);
-
-	idr_for_each_entry(&sdata->u.nan.function_inst_ids, func, id)
-		funcs[i++] = func;
-
-	spin_unlock_bh(&sdata->u.nan.func_lock);
-
-	for (i = 0; funcs[i]; i++) {
-		res = drv_add_nan_func(sdata->local, sdata, funcs[i]);
+	xa_for_each(&sdata->u.nan.functions, id, func) {
+		res = drv_add_nan_func(sdata->local, sdata, func);
 		if (WARN_ON(res))
 			ieee80211_nan_func_terminated(&sdata->vif,
-						      funcs[i]->instance_id,
+						      func->instance_id,
 						      NL80211_NAN_FUNC_TERM_REASON_ERROR,
 						      GFP_KERNEL);
 	}
 
-	kfree(funcs);
-
 	return 0;
 }
 
-- 
2.23.0.rc1

Re: [PATCH 23/38] cls_api: Convert tcf_net to XArray

[David Miller]

From: Matthew Wilcox <willy@infradead.org>
Date: Tue, 20 Aug 2019 15:32:44 -0700

> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
> 
> This module doesn't use the allocating functionality; convert it to a
> plain XArray instead of an allocating one.  I've left struct tcf_net
> in place in case more objects are added to it in future, although
> it now only contains an XArray.  We don't need to call xa_destroy()
> if the array is empty, so I've removed the contents of tcf_net_exit()
> -- if it can be called with entries still in place, then it shoud call
> xa_destroy() instead.
> 
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

I don't know if the net exit can be invoked with entires still in place,
however if the tcf_net_exit() function is made empty it should be removed
along with the assignment to the per-netns ops.

Re: [PATCH 29/38] cls_flower: Convert handle_idr to XArray

[David Miller]

From: Matthew Wilcox <willy@infradead.org>
Date: Tue, 20 Aug 2019 15:32:50 -0700

> -		idr_replace(&head->handle_idr, fnew, fnew->handle);
> +		xa_store(&head->filters, fnew->handle, fnew, 0);

Passing a gfp_t of zero? :-)

Re: [PATCH 29/38] cls_flower: Convert handle_idr to XArray

[Matthew Wilcox]

On Tue, Aug 20, 2019 at 04:58:34PM -0700, David Miller wrote:
> From: Matthew Wilcox <willy@infradead.org>
> Date: Tue, 20 Aug 2019 15:32:50 -0700
> 
> > -		idr_replace(&head->handle_idr, fnew, fnew->handle);
> > +		xa_store(&head->filters, fnew->handle, fnew, 0);
> 
> Passing a gfp_t of zero? :-)

Yes!  We know we'll never do an allocation here because we're replacing
an entry that already exists.  It wouldn't harm us to pass a real
GFP flag, so I'll probably just change that.  It might help a future
implementation, and it will definitely save confusion.

Re: [PATCH 23/38] cls_api: Convert tcf_net to XArray

[Matthew Wilcox]

On Tue, Aug 20, 2019 at 04:57:28PM -0700, David Miller wrote:
> > From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
> > 
> > This module doesn't use the allocating functionality; convert it to a
> > plain XArray instead of an allocating one.  I've left struct tcf_net
> > in place in case more objects are added to it in future, although
> > it now only contains an XArray.  We don't need to call xa_destroy()
> > if the array is empty, so I've removed the contents of tcf_net_exit()
> > -- if it can be called with entries still in place, then it shoud call
> > xa_destroy() instead.
> > 
> > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> 
> I don't know if the net exit can be invoked with entires still in place,
> however if the tcf_net_exit() function is made empty it should be removed
> along with the assignment to the per-netns ops.

Thanks!  I wasn't sure what the rule was for these ops.  I'll fix that up.

Re: [PATCH 08/38] nfp: Convert to XArray

[Jakub Kicinski]

On Tue, 20 Aug 2019 15:32:29 -0700, Matthew Wilcox wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
> 
> A minor change in semantics where we simply store into the XArray rather
> than insert; this only matters if there could already be something stored
> at that index, and from my reading of the code that can't happen.
> 
> Use xa_for_each() rather than xas_for_each() as none of these loops
> appear to be performance-critical.
> 
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

Looks reasonable (indeed IIRC there should not be anything at the
index we try to store to). I'll try to test tomorrow (CCing maintainers
could speed things up a little.. 🤭)

> @@ -285,9 +275,9 @@ static void
>  nfp_abm_qdisc_clear_mq(struct net_device *netdev, struct nfp_abm_link *alink,
>  		       struct nfp_qdisc *qdisc)
>  {
> -	struct radix_tree_iter iter;
>  	unsigned int mq_refs = 0;
> -	void __rcu **slot;
> +	unsigned long index;
> +	struct nfp_qdisc *mq;

Could you keep the variables sorted longest to shortest as is customary
in networking code if you respin?

Re: [PATCH 29/38] cls_flower: Convert handle_idr to XArray

[Vlad Buslov]

On Wed 21 Aug 2019 at 01:32, Matthew Wilcox <willy@infradead.org> wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
>
> Inline __fl_get() into fl_get().  Use the RCU lock explicitly for
> lookups and walks instead of relying on RTNL.  The xa_lock protects us,
> but remains nested under the RTNL for now.
>
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> ---
>  net/sched/cls_flower.c | 54 ++++++++++++++++++++----------------------
>  1 file changed, 26 insertions(+), 28 deletions(-)
>
> diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
> index 054123742e32..54026c9e9b05 100644
> --- a/net/sched/cls_flower.c
> +++ b/net/sched/cls_flower.c
> @@ -91,7 +91,7 @@ struct cls_fl_head {
>  	struct list_head masks;
>  	struct list_head hw_filters;
>  	struct rcu_work rwork;
> -	struct idr handle_idr;
> +	struct xarray filters;
>  };
>
>  struct cls_fl_filter {
> @@ -334,7 +334,7 @@ static int fl_init(struct tcf_proto *tp)
>  	INIT_LIST_HEAD_RCU(&head->masks);
>  	INIT_LIST_HEAD(&head->hw_filters);
>  	rcu_assign_pointer(tp->root, head);
> -	idr_init(&head->handle_idr);
> +	xa_init_flags(&head->filters, XA_FLAGS_ALLOC1);
>
>  	return rhashtable_init(&head->ht, &mask_ht_params);
>  }
> @@ -530,19 +530,6 @@ static void __fl_put(struct cls_fl_filter *f)
>  		__fl_destroy_filter(f);
>  }
>
> -static struct cls_fl_filter *__fl_get(struct cls_fl_head *head, u32 handle)
> -{
> -	struct cls_fl_filter *f;
> -
> -	rcu_read_lock();
> -	f = idr_find(&head->handle_idr, handle);
> -	if (f && !refcount_inc_not_zero(&f->refcnt))
> -		f = NULL;
> -	rcu_read_unlock();
> -
> -	return f;
> -}
> -
>  static int __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f,
>  		       bool *last, bool rtnl_held,
>  		       struct netlink_ext_ack *extack)
> @@ -560,7 +547,7 @@ static int __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f,
>  	f->deleted = true;
>  	rhashtable_remove_fast(&f->mask->ht, &f->ht_node,
>  			       f->mask->filter_ht_params);
> -	idr_remove(&head->handle_idr, f->handle);
> +	xa_erase(&head->filters, f->handle);
>  	list_del_rcu(&f->list);
>  	spin_unlock(&tp->lock);
>
> @@ -599,7 +586,7 @@ static void fl_destroy(struct tcf_proto *tp, bool rtnl_held,
>  				break;
>  		}
>  	}
> -	idr_destroy(&head->handle_idr);
> +	xa_destroy(&head->filters);
>
>  	__module_get(THIS_MODULE);
>  	tcf_queue_work(&head->rwork, fl_destroy_sleepable);
> @@ -615,8 +602,15 @@ static void fl_put(struct tcf_proto *tp, void *arg)
>  static void *fl_get(struct tcf_proto *tp, u32 handle)
>  {
>  	struct cls_fl_head *head = fl_head_dereference(tp);
> +	struct cls_fl_filter *f;
> +
> +	rcu_read_lock();
> +	f = xa_load(&head->filters, handle);
> +	if (f && !refcount_inc_not_zero(&f->refcnt))
> +		f = NULL;
> +	rcu_read_unlock();
>
> -	return __fl_get(head, handle);
> +	return f;
>  }
>
>  static const struct nla_policy fl_policy[TCA_FLOWER_MAX + 1] = {
> @@ -1663,7 +1657,7 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
>  		rhashtable_remove_fast(&fold->mask->ht,
>  				       &fold->ht_node,
>  				       fold->mask->filter_ht_params);
> -		idr_replace(&head->handle_idr, fnew, fnew->handle);
> +		xa_store(&head->filters, fnew->handle, fnew, 0);
>  		list_replace_rcu(&fold->list, &fnew->list);
>  		fold->deleted = true;
>
> @@ -1681,8 +1675,9 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
>  	} else {
>  		if (handle) {
>  			/* user specifies a handle and it doesn't exist */
> -			err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
> -					    handle, GFP_ATOMIC);
> +			fnew->handle = handle;
> +			err = xa_insert(&head->filters, handle, fnew,
> +					GFP_ATOMIC);
>
>  			/* Filter with specified handle was concurrently
>  			 * inserted after initial check in cls_api. This is not
> @@ -1690,18 +1685,16 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
>  			 * message flags. Returning EAGAIN will cause cls_api to
>  			 * try to update concurrently inserted rule.
>  			 */
> -			if (err == -ENOSPC)
> +			if (err == -EBUSY)
>  				err = -EAGAIN;
>  		} else {
> -			handle = 1;
> -			err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
> -					    INT_MAX, GFP_ATOMIC);
> +			err = xa_alloc(&head->filters, &fnew->handle, fnew,
> +					xa_limit_31b, GFP_ATOMIC);
>  		}
>  		if (err)
>  			goto errout_hw;
>
>  		refcount_inc(&fnew->refcnt);
> -		fnew->handle = handle;
>  		list_add_tail_rcu(&fnew->list, &fnew->mask->filters);
>  		spin_unlock(&tp->lock);
>  	}
> @@ -1755,23 +1748,28 @@ static void fl_walk(struct tcf_proto *tp, struct tcf_walker *arg,
>  		    bool rtnl_held)
>  {
>  	struct cls_fl_head *head = fl_head_dereference(tp);
> -	unsigned long id = arg->cookie, tmp;
> +	unsigned long id;
>  	struct cls_fl_filter *f;

Could you sort these by line length if you respin?

>
>  	arg->count = arg->skip;
>
> -	idr_for_each_entry_continue_ul(&head->handle_idr, f, tmp, id) {
> +	rcu_read_lock();
> +	xa_for_each_start(&head->filters, id, f, arg->cookie) {
>  		/* don't return filters that are being deleted */
>  		if (!refcount_inc_not_zero(&f->refcnt))
>  			continue;
> +		rcu_read_unlock();
>  		if (arg->fn(tp, f, arg) < 0) {
>  			__fl_put(f);
>  			arg->stop = 1;
> +			rcu_read_lock();
>  			break;
>  		}
>  		__fl_put(f);
>  		arg->count++;
> +		rcu_read_lock();
>  	}
> +	rcu_read_unlock();
>  	arg->cookie = id;
>  }

At first I was confused why you bring up rtnl lock in commit message
(flower classifier has 'unlocked' flag set and can't rely on it anymore)
but looking at the code I see that we lost rcu read lock here in commit
d39d714969cd ("idr: introduce idr_for_each_entry_continue_ul()") and you
are correctly bringing it back. Adding Cong to advise if it is okay to
wait for this patch to be accepted or we need to proceed with fixing the
missing RCU lock as a standalone patch.

Re: [PATCH 30/38] cls_flower: Use XArray list of filters in fl_walk

[Vlad Buslov]

On Wed 21 Aug 2019 at 01:32, Matthew Wilcox <willy@infradead.org> wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
>
> Instead of iterating over every filter attached to every mark, just
> iterate over each filter.
>
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> ---
>  net/sched/cls_flower.c | 15 ++++++---------
>  1 file changed, 6 insertions(+), 9 deletions(-)
>
> diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
> index 54026c9e9b05..2a1999d2b507 100644
> --- a/net/sched/cls_flower.c
> +++ b/net/sched/cls_flower.c
> @@ -575,18 +575,15 @@ static void fl_destroy(struct tcf_proto *tp, bool rtnl_held,
>  		       struct netlink_ext_ack *extack)
>  {
>  	struct cls_fl_head *head = fl_head_dereference(tp);
> -	struct fl_flow_mask *mask, *next_mask;
> -	struct cls_fl_filter *f, *next;
> +	struct cls_fl_filter *f;
> +	unsigned long handle;
>  	bool last;
>
> -	list_for_each_entry_safe(mask, next_mask, &head->masks, list) {
> -		list_for_each_entry_safe(f, next, &mask->filters, list) {
> -			__fl_delete(tp, f, &last, rtnl_held, extack);
> -			if (last)
> -				break;
> -		}
> +	xa_for_each(&head->filters, handle, f) {
> +		__fl_delete(tp, f, &last, rtnl_held, extack);
> +		if (last)
> +			break;
>  	}
> -	xa_destroy(&head->filters);
>
>  	__module_get(THIS_MODULE);
>  	tcf_queue_work(&head->rwork, fl_destroy_sleepable);

What is the motivation for this change? You substitute O(n) iteration
over linked list with O(nlogn) iteration over xarray without any
apparent benefit.

Re: [PATCH 31/38] cls_flower: Use XArray marks instead of separate list

[Vlad Buslov]

On Wed 21 Aug 2019 at 01:32, Matthew Wilcox <willy@infradead.org> wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
>
> Remove the hw_filter list in favour of using one of the XArray mark
> bits which lets us iterate more efficiently than walking a linked list.
>
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> ---
>  net/sched/cls_flower.c | 47 ++++++++++--------------------------------
>  1 file changed, 11 insertions(+), 36 deletions(-)
>
> diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
> index 2a1999d2b507..4625de5e29a7 100644
> --- a/net/sched/cls_flower.c
> +++ b/net/sched/cls_flower.c
> @@ -85,11 +85,12 @@ struct fl_flow_tmplt {
>  	struct tcf_chain *chain;
>  };
>
> +#define HW_FILTER	XA_MARK_1
> +
>  struct cls_fl_head {
>  	struct rhashtable ht;
>  	spinlock_t masks_lock; /* Protect masks list */
>  	struct list_head masks;
> -	struct list_head hw_filters;
>  	struct rcu_work rwork;
>  	struct xarray filters;
>  };
> @@ -102,7 +103,6 @@ struct cls_fl_filter {
>  	struct tcf_result res;
>  	struct fl_flow_key key;
>  	struct list_head list;
> -	struct list_head hw_list;
>  	u32 handle;
>  	u32 flags;
>  	u32 in_hw_count;
> @@ -332,7 +332,6 @@ static int fl_init(struct tcf_proto *tp)
>
>  	spin_lock_init(&head->masks_lock);
>  	INIT_LIST_HEAD_RCU(&head->masks);
> -	INIT_LIST_HEAD(&head->hw_filters);
>  	rcu_assign_pointer(tp->root, head);
>  	xa_init_flags(&head->filters, XA_FLAGS_ALLOC1);
>
> @@ -421,7 +420,6 @@ static void fl_hw_destroy_filter(struct tcf_proto *tp, struct cls_fl_filter *f,
>
>  	tc_setup_cb_call(block, TC_SETUP_CLSFLOWER, &cls_flower, false);
>  	spin_lock(&tp->lock);
> -	list_del_init(&f->hw_list);
>  	tcf_block_offload_dec(block, &f->flags);
>  	spin_unlock(&tp->lock);
>
> @@ -433,7 +431,6 @@ static int fl_hw_replace_filter(struct tcf_proto *tp,
>  				struct cls_fl_filter *f, bool rtnl_held,
>  				struct netlink_ext_ack *extack)
>  {
> -	struct cls_fl_head *head = fl_head_dereference(tp);
>  	struct tcf_block *block = tp->chain->block;
>  	struct flow_cls_offload cls_flower = {};
>  	bool skip_sw = tc_skip_sw(f->flags);
> @@ -485,9 +482,6 @@ static int fl_hw_replace_filter(struct tcf_proto *tp,
>  		goto errout;
>  	}
>
> -	spin_lock(&tp->lock);
> -	list_add(&f->hw_list, &head->hw_filters);
> -	spin_unlock(&tp->lock);
>  errout:
>  	if (!rtnl_held)
>  		rtnl_unlock();
> @@ -1581,7 +1575,6 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
>  		err = -ENOBUFS;
>  		goto errout_tb;
>  	}
> -	INIT_LIST_HEAD(&fnew->hw_list);
>  	refcount_set(&fnew->refcnt, 1);
>
>  	err = tcf_exts_init(&fnew->exts, net, TCA_FLOWER_ACT, 0);
> @@ -1698,6 +1691,11 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
>
>  	*arg = fnew;
>
> +	if (!tc_skip_hw(fnew->flags))
> +		xa_set_mark(&head->filters, fnew->handle, HW_FILTER);
> +	else if (fold)
> +		xa_clear_mark(&head->filters, fnew->handle, HW_FILTER);
> +

I like how xa mark simplifies reoffload handling, but this wouldn't
work anymore because without rtnl protection fl_change()/fl_delete() can
be called concurrently with fl_reoffload(). My original implementation
of unlocked flower classifier relied on idr in fl_reoffload() and we had
to introduce hw_list due to following race conditions:

- fl_reoffload() can miss fnew if it runs after fnew was provisioned to
  hardware with fl_hw_replace_filter() but before it is marked with
  HW_FILTER.

- Another race condition would be in __fl_delete() when filter is
  removed from xarray, then shared block is detached concurrently which
  causes fl_reoffload() that misses the filter, then the block callback
  is no longer present when fl_hw_destroy_filter() calls
  tc_setup_cb_call() and we have a dangling filter that can't be removed
  from hardware anymore.

That is why filter must be added to hw_list where it is done now - in
fl_hw*() functions while holding rtnl lock to prevent concurrent
reoffload (block bind/unbind always take rtnl). I guess
marking/unmarking filters as HW_FILTER in exactly the same places where
it is inserted/removed from hw_list would also work.

>  	kfree(tb);
>  	tcf_queue_work(&mask->rwork, fl_uninit_mask_free_work);
>  	return 0;
> @@ -1770,37 +1768,14 @@ static void fl_walk(struct tcf_proto *tp, struct tcf_walker *arg,
>  	arg->cookie = id;
>  }
>
> -static struct cls_fl_filter *
> -fl_get_next_hw_filter(struct tcf_proto *tp, struct cls_fl_filter *f, bool add)
> -{
> -	struct cls_fl_head *head = fl_head_dereference(tp);
> -
> -	spin_lock(&tp->lock);
> -	if (list_empty(&head->hw_filters)) {
> -		spin_unlock(&tp->lock);
> -		return NULL;
> -	}
> -
> -	if (!f)
> -		f = list_entry(&head->hw_filters, struct cls_fl_filter,
> -			       hw_list);
> -	list_for_each_entry_continue(f, &head->hw_filters, hw_list) {
> -		if (!(add && f->deleted) && refcount_inc_not_zero(&f->refcnt)) {
> -			spin_unlock(&tp->lock);
> -			return f;
> -		}
> -	}
> -
> -	spin_unlock(&tp->lock);
> -	return NULL;
> -}
> -
>  static int fl_reoffload(struct tcf_proto *tp, bool add, flow_setup_cb_t *cb,
>  			void *cb_priv, struct netlink_ext_ack *extack)
>  {
> +	struct cls_fl_head *head = fl_head_dereference(tp);
>  	struct tcf_block *block = tp->chain->block;
>  	struct flow_cls_offload cls_flower = {};
> -	struct cls_fl_filter *f = NULL;
> +	struct cls_fl_filter *f;
> +	unsigned long handle;
>  	int err;
>
>  	/* hw_filters list can only be changed by hw offload functions after
> @@ -1809,7 +1784,7 @@ static int fl_reoffload(struct tcf_proto *tp, bool add, flow_setup_cb_t *cb,
>  	 */
>  	ASSERT_RTNL();
>
> -	while ((f = fl_get_next_hw_filter(tp, f, add))) {
> +	xa_for_each_marked(&head->filters, handle, f, HW_FILTER) {
>  		cls_flower.rule =
>  			flow_rule_alloc(tcf_exts_num_actions(&f->exts));
>  		if (!cls_flower.rule) {

Re: [PATCH 33/38] act_api: Convert action_idr to XArray

[Vlad Buslov]

On Wed 21 Aug 2019 at 01:32, Matthew Wilcox <willy@infradead.org> wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
>
> Replace the mutex protecting the IDR with the XArray spinlock.
>
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> ---
>  include/net/act_api.h |   6 +-
>  net/sched/act_api.c   | 127 +++++++++++++++++-------------------------
>  2 files changed, 53 insertions(+), 80 deletions(-)
>
> diff --git a/include/net/act_api.h b/include/net/act_api.h

[...]

> @@ -290,10 +283,8 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
>  	struct nlattr *nest;
>  	int n_i = 0;
>  	int ret = -EINVAL;
> -	struct idr *idr = &idrinfo->action_idr;
>  	struct tc_action *p;
> -	unsigned long id = 1;
> -	unsigned long tmp;
> +	unsigned long index;
>  
>  	nest = nla_nest_start_noflag(skb, 0);
>  	if (nest == NULL)
> @@ -301,18 +292,18 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
>  	if (nla_put_string(skb, TCA_KIND, ops->kind))
>  		goto nla_put_failure;
>  
> -	mutex_lock(&idrinfo->lock);
> -	idr_for_each_entry_ul(idr, p, tmp, id) {
> +	xa_lock(&idrinfo->actions);
> +	xa_for_each(&idrinfo->actions, index, p) {
>  		ret = tcf_idr_release_unsafe(p);

I like the simplification of reusing builtin xarray spinlock for this,
but the reason we are using mutex here is because the following call
chain: tcf_idr_release_unsafe() -> tcf_action_cleanup() -> free_tcf() ->
tcf_chain_put_by_act() -> __tcf_chain_put() -> mutex_lock(&block->lock);

Re: [PATCH 33/38] act_api: Convert action_idr to XArray

[Matthew Wilcox]

On Wed, Aug 21, 2019 at 07:41:19PM +0000, Vlad Buslov wrote:
> > @@ -301,18 +292,18 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
> >  	if (nla_put_string(skb, TCA_KIND, ops->kind))
> >  		goto nla_put_failure;
> >  
> > -	mutex_lock(&idrinfo->lock);
> > -	idr_for_each_entry_ul(idr, p, tmp, id) {
> > +	xa_lock(&idrinfo->actions);
> > +	xa_for_each(&idrinfo->actions, index, p) {
> >  		ret = tcf_idr_release_unsafe(p);
> 
> I like the simplification of reusing builtin xarray spinlock for this,
> but the reason we are using mutex here is because the following call
> chain: tcf_idr_release_unsafe() -> tcf_action_cleanup() -> free_tcf() ->
> tcf_chain_put_by_act() -> __tcf_chain_put() -> mutex_lock(&block->lock);

Ah, this one is buggy anyway because we call xa_erase() inside the
loop, so it'll deadlock.

We could just drop the xa_lock() / xa_unlock() around the loop.  There's
no need to hold the lock unless we're trying to prevent other simultaneous
additions/deletions, which shouldn't be happening?  ie this:

@@ -268,8 +268,10 @@ static int tcf_idr_release_unsafe(struct tc_action *p)
        if (atomic_read(&p->tcfa_bindcnt) > 0)
                return -EPERM;
 
-       if (refcount_dec_and_test(&p->tcfa_refcnt)) {
-               xa_erase(&p->idrinfo->actions, p->tcfa_index);
+       if (refcount_dec_and_lock(&p->tcfa_refcnt,
+                                       &p->idrinfo->actions.xa_lock)) {
+               __xa_erase(&p->idrinfo->actions, p->tcfa_index);
+               xa_unlock(&p->idrinfo->actions);
                tcf_action_cleanup(p);
                return ACT_P_DELETED;
        }
@@ -292,18 +294,15 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
        if (nla_put_string(skb, TCA_KIND, ops->kind))
                goto nla_put_failure;
 
-       xa_lock(&idrinfo->actions);
        xa_for_each(&idrinfo->actions, index, p) {
                ret = tcf_idr_release_unsafe(p);
                if (ret == ACT_P_DELETED) {
                        module_put(ops->owner);
                        n_i++;
                } else if (ret < 0) {
-                       xa_unlock(&idrinfo->actions);
                        goto nla_put_failure;
                }
        }
-       xa_unlock(&idrinfo->actions);
 
        if (nla_put_u32(skb, TCA_FCNT, n_i))
                goto nla_put_failure;

Re: [PATCH 24/38] cls_u32: Convert tc_u_common->handle_idr to XArray

[Jakub Kicinski]

On Tue, 20 Aug 2019 15:32:45 -0700, Matthew Wilcox wrote:
> @@ -305,8 +306,12 @@ static void *u32_get(struct tcf_proto *tp, u32 handle)
>  /* Protected by rtnl lock */
>  static u32 gen_new_htid(struct tc_u_common *tp_c, struct tc_u_hnode *ptr)
>  {
> -	int id = idr_alloc_cyclic(&tp_c->handle_idr, ptr, 1, 0x7FF, GFP_KERNEL);
> -	if (id < 0)
> +	int err;
> +	u32 id;
> +
> +	err = xa_alloc_cyclic(&tp_c->ht_xa, &id, ptr, XA_LIMIT(0, 0x7ff),
> +			&tp_c->ht_next, GFP_KERNEL);

nit: indentation seems off here and a couple of other places.

Re: [PATCH 24/38] cls_u32: Convert tc_u_common->handle_idr to XArray

[Matthew Wilcox]

On Wed, Aug 21, 2019 at 02:13:08PM -0700, Jakub Kicinski wrote:
> On Tue, 20 Aug 2019 15:32:45 -0700, Matthew Wilcox wrote:
> > @@ -305,8 +306,12 @@ static void *u32_get(struct tcf_proto *tp, u32 handle)
> >  /* Protected by rtnl lock */
> >  static u32 gen_new_htid(struct tc_u_common *tp_c, struct tc_u_hnode *ptr)
> >  {
> > -	int id = idr_alloc_cyclic(&tp_c->handle_idr, ptr, 1, 0x7FF, GFP_KERNEL);
> > -	if (id < 0)
> > +	int err;
> > +	u32 id;
> > +
> > +	err = xa_alloc_cyclic(&tp_c->ht_xa, &id, ptr, XA_LIMIT(0, 0x7ff),
> > +			&tp_c->ht_next, GFP_KERNEL);
> 
> nit: indentation seems off here and a couple of other places.

what indentation rule does the networking stack use?  i just leave the
cursor where my editor puts it, which seems to be two tabs.

Re: [PATCH 24/38] cls_u32: Convert tc_u_common->handle_idr to XArray

[Jakub Kicinski]

On Wed, 21 Aug 2019 14:25:42 -0700, Matthew Wilcox wrote:
> On Wed, Aug 21, 2019 at 02:13:08PM -0700, Jakub Kicinski wrote:
> > On Tue, 20 Aug 2019 15:32:45 -0700, Matthew Wilcox wrote:  
> > > @@ -305,8 +306,12 @@ static void *u32_get(struct tcf_proto *tp, u32 handle)
> > >  /* Protected by rtnl lock */
> > >  static u32 gen_new_htid(struct tc_u_common *tp_c, struct tc_u_hnode *ptr)
> > >  {
> > > -	int id = idr_alloc_cyclic(&tp_c->handle_idr, ptr, 1, 0x7FF, GFP_KERNEL);
> > > -	if (id < 0)
> > > +	int err;
> > > +	u32 id;
> > > +
> > > +	err = xa_alloc_cyclic(&tp_c->ht_xa, &id, ptr, XA_LIMIT(0, 0x7ff),
> > > +			&tp_c->ht_next, GFP_KERNEL);  
> > 
> > nit: indentation seems off here and a couple of other places.  
> 
> what indentation rule does the networking stack use?  i just leave the
> cursor where my editor puts it, which seems to be two tabs.

Oh, match opening bracket..

	err = xa_alloc_cyclic(&tp_c->ht_xa, &id, ptr, XA_LIMIT(0, 0x7ff),
			      &tp_c->ht_next, GFP_KERNEL);

Re: [PATCH 29/38] cls_flower: Convert handle_idr to XArray

[Cong Wang]

On Wed, Aug 21, 2019 at 11:27 AM Vlad Buslov <vladbu@mellanox.com> wrote:
> At first I was confused why you bring up rtnl lock in commit message
> (flower classifier has 'unlocked' flag set and can't rely on it anymore)
> but looking at the code I see that we lost rcu read lock here in commit
> d39d714969cd ("idr: introduce idr_for_each_entry_continue_ul()") and you
> are correctly bringing it back. Adding Cong to advise if it is okay to
> wait for this patch to be accepted or we need to proceed with fixing the
> missing RCU lock as a standalone patch.

Hmm? Isn't ->walk() still called with RTNL lock? tcf_chain_dump()
calls __tcf_get_next_proto() which asserts RTNL.

So why does it still need RCU read lock when having RTNL?

Re: [PATCH 29/38] cls_flower: Convert handle_idr to XArray

[Vlad Buslov]

On Sun 25 Aug 2019 at 21:32, Cong Wang <xiyou.wangcong@gmail.com> wrote:
> On Wed, Aug 21, 2019 at 11:27 AM Vlad Buslov <vladbu@mellanox.com> wrote:
>> At first I was confused why you bring up rtnl lock in commit message
>> (flower classifier has 'unlocked' flag set and can't rely on it anymore)
>> but looking at the code I see that we lost rcu read lock here in commit
>> d39d714969cd ("idr: introduce idr_for_each_entry_continue_ul()") and you
>> are correctly bringing it back. Adding Cong to advise if it is okay to
>> wait for this patch to be accepted or we need to proceed with fixing the
>> missing RCU lock as a standalone patch.
>
> Hmm? Isn't ->walk() still called with RTNL lock? tcf_chain_dump()
> calls __tcf_get_next_proto() which asserts RTNL.
>
> So why does it still need RCU read lock when having RTNL?

Individual filters can be deleted without obtaining rtnl lock. And
without rcu read lock, f can be deallocated in fl_walk() main loop
before refcount_inc_not_zero() obtains reference to it.

Re: [PATCH 03/38] mlx4: Convert qp_table_tree to XArray

[Saeed Mahameed]

On Tue, 2019-08-20 at 15:32 -0700, Matthew Wilcox wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
> 
> This XArray appears to be modifiable from interrupt context, so we
> have
> to be a little more careful with the locking.  However, the lookup
> can
> be done without the spinlock held.  I cannot determine whether
> mlx4_qp_alloc() is allowed to sleep, so I've retained the GFP_ATOMIC
> there, but it could be turned into GFP_KERNEL if the callers can
> tolerate it sleeping.
> 
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> ---
>  drivers/net/ethernet/mellanox/mlx4/mlx4.h |  3 +-
>  drivers/net/ethernet/mellanox/mlx4/qp.c   | 37 ++++++---------------
> --
>  include/linux/mlx4/device.h               |  4 +--
>  include/linux/mlx4/qp.h                   |  2 +-
>  4 files changed, 14 insertions(+), 32 deletions(-)
> 
> diff --git a/drivers/net/ethernet/mellanox/mlx4/mlx4.h
> b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
> index b6fe22bee9f4..aaece8480da7 100644
> --- a/drivers/net/ethernet/mellanox/mlx4/mlx4.h
> +++ b/drivers/net/ethernet/mellanox/mlx4/mlx4.h
> @@ -38,7 +38,7 @@
>  #define MLX4_H
>  
>  #include <linux/mutex.h>
> -#include <linux/radix-tree.h>
> +#include <linux/xarray.h>
>  #include <linux/rbtree.h>
>  #include <linux/timer.h>
>  #include <linux/semaphore.h>
> @@ -716,7 +716,6 @@ struct mlx4_qp_table {
>  	u32			zones_uids[MLX4_QP_TABLE_ZONE_NUM];
>  	u32			rdmarc_base;
>  	int			rdmarc_shift;
> -	spinlock_t		lock;
>  	struct mlx4_icm_table	qp_table;
>  	struct mlx4_icm_table	auxc_table;
>  	struct mlx4_icm_table	altc_table;
> diff --git a/drivers/net/ethernet/mellanox/mlx4/qp.c
> b/drivers/net/ethernet/mellanox/mlx4/qp.c
> index 427e7a31862c..4659ecec12c1 100644
> --- a/drivers/net/ethernet/mellanox/mlx4/qp.c
> +++ b/drivers/net/ethernet/mellanox/mlx4/qp.c
> @@ -48,16 +48,13 @@
>  
>  void mlx4_qp_event(struct mlx4_dev *dev, u32 qpn, int event_type)
>  {
> -	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
>  	struct mlx4_qp *qp;
>  
> -	spin_lock(&qp_table->lock);
> -
> +	xa_lock(&dev->qp_table);
>  	qp = __mlx4_qp_lookup(dev, qpn);
>  	if (qp)
>  		refcount_inc(&qp->refcount);
> -
> -	spin_unlock(&qp_table->lock);
> +	xa_unlock(&dev->qp_table);
>  
>  	if (!qp) {
>  		mlx4_dbg(dev, "Async event for none existent QP
> %08x\n", qpn);
> @@ -390,21 +387,11 @@ static void mlx4_qp_free_icm(struct mlx4_dev
> *dev, int qpn)
>  
>  struct mlx4_qp *mlx4_qp_lookup(struct mlx4_dev *dev, u32 qpn)
>  {
> -	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
> -	struct mlx4_qp *qp;
> -
> -	spin_lock_irq(&qp_table->lock);
> -
> -	qp = __mlx4_qp_lookup(dev, qpn);
> -
> -	spin_unlock_irq(&qp_table->lock);
> -	return qp;
> +	return __mlx4_qp_lookup(dev, qpn);
>  }
>  
>  int mlx4_qp_alloc(struct mlx4_dev *dev, int qpn, struct mlx4_qp *qp)
>  {
> -	struct mlx4_priv *priv = mlx4_priv(dev);
> -	struct mlx4_qp_table *qp_table = &priv->qp_table;
>  	int err;
>  
>  	if (!qpn)
> @@ -416,10 +403,9 @@ int mlx4_qp_alloc(struct mlx4_dev *dev, int qpn,
> struct mlx4_qp *qp)
>  	if (err)
>  		return err;
>  
> -	spin_lock_irq(&qp_table->lock);
> -	err = radix_tree_insert(&dev->qp_table_tree, qp->qpn &
> -				(dev->caps.num_qps - 1), qp);
> -	spin_unlock_irq(&qp_table->lock);
> +	err = xa_err(xa_store_irq(&dev->qp_table,
> +				qp->qpn & (dev->caps.num_qps - 1),
> +				qp, GFP_ATOMIC));

mlx4_qp_alloc might sleep, so GFP_KERNEL here.

>  	if (err)
>  		goto err_icm;
>  
> @@ -512,12 +498,11 @@ EXPORT_SYMBOL_GPL(mlx4_update_qp);
>  
>  void mlx4_qp_remove(struct mlx4_dev *dev, struct mlx4_qp *qp)
>  {
> -	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
>  	unsigned long flags;
>  
> -	spin_lock_irqsave(&qp_table->lock, flags);
> -	radix_tree_delete(&dev->qp_table_tree, qp->qpn & (dev-
> >caps.num_qps - 1));
> -	spin_unlock_irqrestore(&qp_table->lock, flags);
> +	xa_lock_irqsave(&dev->qp_table, flags);
> +	__xa_erase(&dev->qp_table, qp->qpn & (dev->caps.num_qps - 1));
> +	xa_unlock_irqrestore(&dev->qp_table, flags);
>  }
>  EXPORT_SYMBOL_GPL(mlx4_qp_remove);
>  
> @@ -760,7 +745,6 @@ static void mlx4_cleanup_qp_zones(struct mlx4_dev
> *dev)
>  
>  int mlx4_init_qp_table(struct mlx4_dev *dev)
>  {
> -	struct mlx4_qp_table *qp_table = &mlx4_priv(dev)->qp_table;
>  	int err;
>  	int reserved_from_top = 0;
>  	int reserved_from_bot;
> @@ -770,8 +754,7 @@ int mlx4_init_qp_table(struct mlx4_dev *dev)
>  	u32 max_table_offset = dev->caps.dmfs_high_rate_qpn_base +
>  			dev->caps.dmfs_high_rate_qpn_range;
>  
> -	spin_lock_init(&qp_table->lock);
> -	INIT_RADIX_TREE(&dev->qp_table_tree, GFP_ATOMIC);
> +	xa_init_flags(&dev->qp_table, XA_FLAGS_LOCK_IRQ);
>  	if (mlx4_is_slave(dev))
>  		return 0;
>  
> diff --git a/include/linux/mlx4/device.h
> b/include/linux/mlx4/device.h
> index 36e412c3d657..acffca7d9f00 100644
> --- a/include/linux/mlx4/device.h
> +++ b/include/linux/mlx4/device.h
> @@ -36,7 +36,7 @@
>  #include <linux/if_ether.h>
>  #include <linux/pci.h>
>  #include <linux/completion.h>
> -#include <linux/radix-tree.h>
> +#include <linux/xarray.h>
>  #include <linux/cpu_rmap.h>
>  #include <linux/crash_dump.h>
>  
> @@ -889,7 +889,7 @@ struct mlx4_dev {
>  	struct mlx4_caps	caps;
>  	struct mlx4_phys_caps	phys_caps;
>  	struct mlx4_quotas	quotas;
> -	struct radix_tree_root	qp_table_tree;
> +	struct xarray		qp_table;
>  	u8			rev_id;
>  	u8			port_random_macs;
>  	char			board_id[MLX4_BOARD_ID_LEN];
> diff --git a/include/linux/mlx4/qp.h b/include/linux/mlx4/qp.h
> index 8e2828d48d7f..6c3ec3197a10 100644
> --- a/include/linux/mlx4/qp.h
> +++ b/include/linux/mlx4/qp.h
> @@ -488,7 +488,7 @@ int mlx4_qp_to_ready(struct mlx4_dev *dev, struct
> mlx4_mtt *mtt,
>  
>  static inline struct mlx4_qp *__mlx4_qp_lookup(struct mlx4_dev *dev,
> u32 qpn)
>  {
> -	return radix_tree_lookup(&dev->qp_table_tree, qpn & (dev-
> >caps.num_qps - 1));
> +	return xa_load(&dev->qp_table, qpn & (dev->caps.num_qps - 1));
>  }
>  
>  void mlx4_qp_remove(struct mlx4_dev *dev, struct mlx4_qp *qp);

Re: [PATCH 04/38] mlx5: Convert cq_table to XArray

[Saeed Mahameed]

On Tue, 2019-08-20 at 15:32 -0700, Matthew Wilcox wrote:
> From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
> 
> Since mlx5_cq_table would have shrunk down to just the xarray,
> eliminate
> it and embed the xarray directly into mlx5_eq.
> 
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> ---
>  drivers/net/ethernet/mellanox/mlx5/core/eq.c  | 27 ++++-------------
> --
>  .../net/ethernet/mellanox/mlx5/core/lib/eq.h  |  7 +----
>  2 files changed, 6 insertions(+), 28 deletions(-)
> 
> diff --git a/drivers/net/ethernet/mellanox/mlx5/core/eq.c
> b/drivers/net/ethernet/mellanox/mlx5/core/eq.c
> index 09d4c64b6e73..c5953f6e0a69 100644
> --- a/drivers/net/ethernet/mellanox/mlx5/core/eq.c
> +++ b/drivers/net/ethernet/mellanox/mlx5/core/eq.c
> @@ -113,11 +113,10 @@ static int mlx5_cmd_destroy_eq(struct
> mlx5_core_dev *dev, u8 eqn)
>  /* caller must eventually call mlx5_cq_put on the returned cq */
>  static struct mlx5_core_cq *mlx5_eq_cq_get(struct mlx5_eq *eq, u32
> cqn)
>  {
> -	struct mlx5_cq_table *table = &eq->cq_table;
> -	struct mlx5_core_cq *cq = NULL;
> +	struct mlx5_core_cq *cq;
>  
>  	rcu_read_lock();
> -	cq = radix_tree_lookup(&table->tree, cqn);
> +	cq = xa_load(&eq->cq_table, cqn);
>  	if (likely(cq))
>  		mlx5_cq_hold(cq);
>  	rcu_read_unlock();
> @@ -243,7 +242,6 @@ static int
>  create_map_eq(struct mlx5_core_dev *dev, struct mlx5_eq *eq,
>  	      struct mlx5_eq_param *param)
>  {
> -	struct mlx5_cq_table *cq_table = &eq->cq_table;
>  	u32 out[MLX5_ST_SZ_DW(create_eq_out)] = {0};
>  	struct mlx5_priv *priv = &dev->priv;
>  	u8 vecidx = param->irq_index;
> @@ -254,11 +252,7 @@ create_map_eq(struct mlx5_core_dev *dev, struct
> mlx5_eq *eq,
>  	int err;
>  	int i;
>  
> -	/* Init CQ table */
> -	memset(cq_table, 0, sizeof(*cq_table));
> -	spin_lock_init(&cq_table->lock);
> -	INIT_RADIX_TREE(&cq_table->tree, GFP_ATOMIC);
> -
> +	xa_init_flags(&eq->cq_table, XA_FLAGS_LOCK_IRQ);

Why the IRQ flag ? we are not going to modify the xarray in irq context
all we do is hold a ref count on the entry we looked up
mlx5_cq_hold(cq); and this is protected by rcu_lock. 

>  	eq->nent = roundup_pow_of_two(param->nent +
> MLX5_NUM_SPARE_EQE);
>  	eq->cons_index = 0;
>  	err = mlx5_buf_alloc(dev, eq->nent * MLX5_EQE_SIZE, &eq->buf);
> @@ -378,25 +372,14 @@ static int destroy_unmap_eq(struct
> mlx5_core_dev *dev, struct mlx5_eq *eq)
>  
>  int mlx5_eq_add_cq(struct mlx5_eq *eq, struct mlx5_core_cq *cq)
>  {
> -	struct mlx5_cq_table *table = &eq->cq_table;
> -	int err;
> -
> -	spin_lock(&table->lock);
> -	err = radix_tree_insert(&table->tree, cq->cqn, cq);
> -	spin_unlock(&table->lock);
> -
> -	return err;
> +	return xa_err(xa_store(&eq->cq_table, cq->cqn, cq,
> GFP_KERNEL));
>  }
>  
>  void mlx5_eq_del_cq(struct mlx5_eq *eq, struct mlx5_core_cq *cq)
>  {
> -	struct mlx5_cq_table *table = &eq->cq_table;
>  	struct mlx5_core_cq *tmp;
>  
> -	spin_lock(&table->lock);
> -	tmp = radix_tree_delete(&table->tree, cq->cqn);
> -	spin_unlock(&table->lock);
> -
> +	tmp = xa_erase(&eq->cq_table, cq->cqn);
>  	if (!tmp) {
>  		mlx5_core_dbg(eq->dev, "cq 0x%x not found in eq 0x%x
> tree\n",
>  			      eq->eqn, cq->cqn);
> diff --git a/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
> b/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
> index 4be4d2d36218..a342cf78120e 100644
> --- a/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
> +++ b/drivers/net/ethernet/mellanox/mlx5/core/lib/eq.h
> @@ -16,14 +16,9 @@ struct mlx5_eq_tasklet {
>  	spinlock_t            lock; /* lock completion tasklet list */
>  };
>  
> -struct mlx5_cq_table {
> -	spinlock_t              lock;	/* protect radix tree */
> -	struct radix_tree_root  tree;
> -};
> -
>  struct mlx5_eq {
>  	struct mlx5_core_dev    *dev;
> -	struct mlx5_cq_table    cq_table;
> +	struct xarray		cq_table;
>  	__be32 __iomem	        *doorbell;
>  	u32                     cons_index;
>  	struct mlx5_frag_buf    buf;