Updated to support IB core on RHEL7.6
authorVladimir Sokolovsky <vlad@mellanox.com>
Tue, 27 Aug 2019 20:04:48 +0000 (15:04 -0500)
committerVladimir Sokolovsky <vlad@mellanox.com>
Tue, 27 Aug 2019 20:04:48 +0000 (15:04 -0500)
Signed-off-by: Vladimir Sokolovsky <vlad@mellanox.com>
14 files changed:
compat/compat-5.2.c [new file with mode: 0644]
config/rdma.m4
include/linux/compat-2.6.h
include/linux/compat-5.3.h [new file with mode: 0644]
include/linux/dim.h [new file with mode: 0644]
include/linux/idr.h [new file with mode: 0644]
include/linux/inetdevice.h [new file with mode: 0644]
include/linux/mm.h
include/linux/netdevice.h
include/linux/overflow.h [new file with mode: 0644]
include/linux/sched/mm.h
include/linux/slab.h
include/linux/vmalloc.h [new file with mode: 0644]
include/linux/xarray.h [new file with mode: 0644]

diff --git a/compat/compat-5.2.c b/compat/compat-5.2.c
new file mode 100644 (file)
index 0000000..3eaec7a
--- /dev/null
@@ -0,0 +1,131 @@
+// SPDX-License-Identifier: GPL-2.0-only
+#ifndef HAVE_PUT_USER_PAGE
+#include <linux/kernel.h>
+#include <linux/errno.h>
+#include <linux/err.h>
+#include <linux/spinlock.h>
+
+#include <linux/mm.h>
+#include <linux/memremap.h>
+#include <linux/pagemap.h>
+#include <linux/rmap.h>
+#include <linux/swap.h>
+#include <linux/swapops.h>
+
+#include <linux/sched/signal.h>
+#include <linux/rwsem.h>
+#include <linux/hugetlb.h>
+#include <linux/migrate.h>
+#include <linux/mm_inline.h>
+#include <linux/sched/mm.h>
+
+#include <asm/mmu_context.h>
+#include <asm/pgtable.h>
+#include <asm/tlbflush.h>
+
+
+typedef int (*set_dirty_func_t)(struct page *page);
+
+static void __put_user_pages_dirty(struct page **pages,
+                                  unsigned long npages,
+                                  set_dirty_func_t sdf)
+{
+       unsigned long index;
+
+       for (index = 0; index < npages; index++) {
+               struct page *page = compound_head(pages[index]);
+
+               /*
+                * Checking PageDirty at this point may race with
+                * clear_page_dirty_for_io(), but that's OK. Two key cases:
+                *
+                * 1) This code sees the page as already dirty, so it skips
+                * the call to sdf(). That could happen because
+                * clear_page_dirty_for_io() called page_mkclean(),
+                * followed by set_page_dirty(). However, now the page is
+                * going to get written back, which meets the original
+                * intention of setting it dirty, so all is well:
+                * clear_page_dirty_for_io() goes on to call
+                * TestClearPageDirty(), and write the page back.
+                *
+                * 2) This code sees the page as clean, so it calls sdf().
+                * The page stays dirty, despite being written back, so it
+                * gets written back again in the next writeback cycle.
+                * This is harmless.
+                */
+               if (!PageDirty(page))
+                       sdf(page);
+
+               put_user_page(page);
+       }
+}
+
+/**
+ * put_user_pages_dirty() - release and dirty an array of gup-pinned pages
+ * @pages:  array of pages to be marked dirty and released.
+ * @npages: number of pages in the @pages array.
+ *
+ * "gup-pinned page" refers to a page that has had one of the get_user_pages()
+ * variants called on that page.
+ *
+ * For each page in the @pages array, make that page (or its head page, if a
+ * compound page) dirty, if it was previously listed as clean. Then, release
+ * the page using put_user_page().
+ *
+ * Please see the put_user_page() documentation for details.
+ *
+ * set_page_dirty(), which does not lock the page, is used here.
+ * Therefore, it is the caller's responsibility to ensure that this is
+ * safe. If not, then put_user_pages_dirty_lock() should be called instead.
+ *
+ */
+void put_user_pages_dirty(struct page **pages, unsigned long npages)
+{
+       __put_user_pages_dirty(pages, npages, set_page_dirty);
+}
+EXPORT_SYMBOL(put_user_pages_dirty);
+
+/**
+ * put_user_pages_dirty_lock() - release and dirty an array of gup-pinned pages
+ * @pages:  array of pages to be marked dirty and released.
+ * @npages: number of pages in the @pages array.
+ *
+ * For each page in the @pages array, make that page (or its head page, if a
+ * compound page) dirty, if it was previously listed as clean. Then, release
+ * the page using put_user_page().
+ *
+ * Please see the put_user_page() documentation for details.
+ *
+ * This is just like put_user_pages_dirty(), except that it invokes
+ * set_page_dirty_lock(), instead of set_page_dirty().
+ *
+ */
+void put_user_pages_dirty_lock(struct page **pages, unsigned long npages)
+{
+       __put_user_pages_dirty(pages, npages, set_page_dirty_lock);
+}
+EXPORT_SYMBOL(put_user_pages_dirty_lock);
+
+/**
+ * put_user_pages() - release an array of gup-pinned pages.
+ * @pages:  array of pages to be marked dirty and released.
+ * @npages: number of pages in the @pages array.
+ *
+ * For each page in the @pages array, release the page using put_user_page().
+ *
+ * Please see the put_user_page() documentation for details.
+ */
+void put_user_pages(struct page **pages, unsigned long npages)
+{
+       unsigned long index;
+
+       /*
+        * TODO: this can be optimized for huge pages: if a series of pages is
+        * physically contiguous and part of the same compound page, then a
+        * single operation to the head page should suffice.
+        */
+       for (index = 0; index < npages; index++)
+               put_user_page(pages[index]);
+}
+EXPORT_SYMBOL(put_user_pages);
+#endif /* HAVE_PUT_USER_PAGE */
index 480d455..d4eb4a4 100644 (file)
@@ -6387,6 +6387,21 @@ AC_DEFUN([LINUX_CONFIG_COMPAT],
                AC_MSG_RESULT(no)
        ])
 
+       AC_MSG_CHECKING([if linux/security.h has register_blocking_lsm_notifier])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/security.h>
+       ],[
+               register_blocking_lsm_notifier(NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_REGISTER_BLOCKING_LSM_NOTIFIER, 1,
+                         [linux/security.h has register_blocking_lsm_notifier])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
        AC_MSG_CHECKING([if refcount.h exists])
        LB_LINUX_TRY_COMPILE([
                #include <linux/refcount.h>
@@ -8807,6 +8822,746 @@ AC_DEFUN([LINUX_CONFIG_COMPAT],
                AC_MSG_RESULT(no)
        ])
 
+       AC_MSG_CHECKING([if netdevice.h alloc_netdev_mq has 4 params])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/netdevice.h>
+       ],[
+               alloc_netdev_mq(0, NULL, NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_ALLOC_NETDEV_MQ_4_PARAMS, 1,
+                         [alloc_netdev_mq has 4 params])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if netdevice.h alloc_netdev_mqs has 5 params])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/netdevice.h>
+       ],[
+               alloc_netdev_mqs(0, NULL, NULL, 0, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_ALLOC_NETDEV_MQS_5_PARAMS, 1,
+                         [alloc_netdev_mqs has 5 params])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if linux/pci-p2pdma.h exists])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/pci-p2pdma.h>
+       ],[
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_PCI_P2PDMA_H, 1,
+                         [linux/pci-p2pdma.h exists])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if idr.h has ida_alloc])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/idr.h>
+       ],[
+               ida_alloc(NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_IDA_ALLOC, 1,
+                         [ida_alloc is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if linux/overflow.h exists])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/overflow.h>
+       ],[
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_LINUX_OVERFLOW_H, 1,
+                         [linux/overflow.h is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if route.h struct rtable has member rt_gw_family])
+       LB_LINUX_TRY_COMPILE([
+               #include <net/route.h>
+       ],[
+               struct rtable x = {
+                       .rt_gw_family = 0,
+               };
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_RT_GW_FAMILY, 1,
+                         [rt_gw_family is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if route.h struct rtable has member rt_uses_gateway])
+       LB_LINUX_TRY_COMPILE([
+               #include <net/route.h>
+       ],[
+               struct rtable x = {
+                       .rt_uses_gateway = 0,
+               };
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_RT_USES_GATEWAY, 1,
+                         [rt_uses_gateway is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       LB_CHECK_SYMBOL_EXPORT([devlink_params_publish],
+               [net/core/devlink.c],
+               [AC_DEFINE(HAVE_DEVLINK_PARAMS_PUBLISHED, 1,
+                       [devlink_params_publish is exported by the kernel])],
+       [])
+       LB_CHECK_SYMBOL_EXPORT([split_page],
+               [mm/page_alloc.c],
+               [AC_DEFINE(HAVE_SPLIT_PAGE_EXPORTED, 1,
+                       [split_page is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([ip6_dst_hoplimit],
+                [net/ipv6/output_core.c],
+                [AC_DEFINE(HAVE_IP6_DST_HOPLIMIT, 1,
+                        [ip6_dst_hoplimit is exported by the kernel])],
+        [])
+
+       LB_CHECK_SYMBOL_EXPORT([udp4_hwcsum],
+               [net/ipv4/udp.c],
+               [AC_DEFINE(HAVE_UDP4_HWCSUM, 1,
+                       [udp4_hwcsum is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([__ip_dev_find],
+               [net/ipv4/devinet.c],
+               [AC_DEFINE(HAVE___IP_DEV_FIND, 1,
+                       [HAVE___IP_DEV_FIND is exported by the kernel])],
+       [])
+       LB_CHECK_SYMBOL_EXPORT([inet_confirm_addr],
+               [net/ipv4/devinet.c],
+               [AC_DEFINE(HAVE_INET_CONFIRM_ADDR_EXPORTED, 1,
+                       [inet_confirm_addr is exported by the kernel])],
+       [])
+
+       AC_MSG_CHECKING([if tracepoint.h supports trace_event_raw_ib_mad_send_template])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/dma-mapping.h>
+               #include <linux/slab.h>
+               #include <linux/module.h>
+               #include <linux/security.h>
+               #include <linux/xarray.h>
+               #include <rdma/ib_cache.h>
+
+               #include "mad_priv.h"
+               #include "core_priv.h"
+               #include "mad_rmpp.h"
+               #include "smi.h"
+               #include "opa_smi.h"
+               #include "agent.h"
+
+               #include <trace/events/ib_mad.h>
+       ],[
+               #ifdef CONFIG_TRACEPOINTS
+               static void create_mad_addr_info(struct ib_mad_send_wr_private *mad_send_wr,
+                                        struct ib_mad_qp_info *qp_info,
+                                        struct trace_event_raw_ib_mad_send_template *entry)
+               {
+                      u16 pkey;
+                      struct ib_device *dev = qp_info->port_priv->device;
+                      u8 pnum = qp_info->port_priv->port_num;
+                      struct ib_ud_wr *wr = &mad_send_wr->send_wr;
+                      struct rdma_ah_attr attr = {};
+
+                      rdma_query_ah(wr->ah, &attr);
+
+                      /* These are common */
+                      entry->sl = attr.sl;
+                      ib_query_pkey(dev, pnum, wr->pkey_index, &pkey);
+                      entry->pkey = pkey;
+                      entry->rqpn = wr->remote_qpn;
+                      entry->rqkey = wr->remote_qkey;
+                      entry->dlid = rdma_ah_get_dlid(&attr);
+               }
+               #endif
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_TRACE_EVENT_RAW_IB_MAD_SEND_TEMPLATE, 1,
+                         [trace_event_raw_ib_mad_send_template is supported])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if netlink.h struct netlink_skb_parms has portid])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/netlink.h>
+       ],[
+               struct netlink_skb_parms xx = {
+                       .portid = 0,
+               };
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_NETLINK_SKB_PARMS_PORTID, 1,
+                         [struct netlink_skb_parms has portid])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if netlink.h has nla_nest_start_noflag])
+       LB_LINUX_TRY_COMPILE([
+               #include <net/netlink.h>
+       ],[
+               nla_nest_start_noflag(NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_NLA_NEST_START_NOFLAG, 1,
+                         [nla_nest_start_noflag exist])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if netlink.h has nlmsg_parse_deprecated ])
+       LB_LINUX_TRY_COMPILE([
+               #include <net/netlink.h>
+       ],[
+               nlmsg_parse_deprecated(NULL, 0, NULL, 0, NULL, NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_NLMSG_PARSE_DEPRECATED, 1,
+                         [nlmsg_parse_deprecated exist])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if idr.h has ida_alloc_max])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/idr.h>
+       ],[
+               ida_alloc_max(NULL, 0, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_IDA_ALLOC_MAX, 1,
+                         [ida_alloc_max is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if netlink.h has nlmsg_validate_deprecated ])
+       LB_LINUX_TRY_COMPILE([
+               #include <net/netlink.h>
+       ],[
+               nlmsg_validate_deprecated(NULL, 0, 0, NULL, NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_NLMSG_VALIDATE_DEPRECATED, 1,
+                         [nlmsg_validate_deprecated exist])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if fs.h has stream_open])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/fs.h>
+       ],[
+               stream_open(NULL, NULL);
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_STREAM_OPEN, 1,
+                       [fs.h has stream_open])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+
+       AC_MSG_CHECKING([if mm.h has mmget])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/sched/mm.h>
+       ],[
+               mmget(NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_MMGET, 1,
+                       [mmget is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if mm.h has mmget_not_zero])
+       LB_LINUX_TRY_COMPILE([
+                #include <linux/sched/mm.h>
+       ],[
+               mmget_not_zero(NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_MMGET_NOT_ZERO, 1,
+                       [mmget_not_zero is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if mm.h has mmget_still_valid])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/sched/mm.h>
+       ],[
+               mmget_still_valid(NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_MMGET_STILL_VALID, 1,
+                       [mmget_still_valid is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if mm.h has mmgrab])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/sched/mm.h>
+       ],[
+               mmgrab(NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_MMGRAB, 1,
+                       [mmgrab is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if linux/sched.h exists])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/sched.h>
+       ],[
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_SCHED_H, 1,
+                         [linux/sched.h exists])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if sched/mm.h has mmget_not_zero])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/sched/mm.h>
+       ],[
+               mmget_not_zero(NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_SCHED_MMGET_NOT_ZERO, 1,
+                       [mmget_not_zero is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if vm_fault_t exist in mm_types.h])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/mm_types.h>
+       ],[
+               vm_fault_t a;
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_VM_FAULT_T, 1,
+                         [vm_fault_t is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if uaccess.h access_ok has 3 parameters])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/uaccess.h>
+       ],[
+               access_ok(0, NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_ACCESS_OK_HAS_3_PARAMS, 1,
+                         [access_okhas 3 parameters])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if linux/atomic.h has __atomic_add_unless])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/highmem.h>
+       ],[
+               atomic_t x;
+               __atomic_add_unless(&x, 1, 1);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE___ATOMIC_ADD_UNLESS, 1,
+                         [__atomic_add_unless is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if linux/atomic.h has atomic_fetch_add_unless])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/highmem.h>
+       ],[
+               atomic_t x;
+               atomic_fetch_add_unless(&x, 1, 1);
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_ATOMIC_FETCH_ADD_UNLESS, 1,
+                         [atomic_fetch_add_unless is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if linux/cgroup_rdma.h exists])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/cgroup_rdma.h>
+       ],[
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_CGROUP_RDMA_H, 1,
+                         [linux/cgroup_rdma exists])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if idr.h has ida_simple_get])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/idr.h>
+       ],[
+               ida_simple_get(NULL, 0, 0, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_IDA_SIMPLE_GET, 1,
+                         [ida_simple_get is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if idr.h has idr_for_each_entry])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/idr.h>
+       ],[
+                int id;
+               void * entry;
+               struct idr * tmp_idr;
+               idr_for_each_entry(tmp_idr, entry, id);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_IDR_FOR_EACH_ENTRY, 1,
+                         [idr_for_each_entry is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if pci.h has pci_irq_get_affinity])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/pci.h>
+       ],[
+               pci_irq_get_affinity(NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_PCI_IRQ_GET_AFFINITY, 1,
+                         [pci_irq_get_affinity is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       LB_CHECK_SYMBOL_EXPORT([elfcorehdr_addr],
+               [kernel/crash_dump.c],
+               [AC_DEFINE(HAVE_ELFCOREHDR_ADDR_EXPORTED, 1,
+                       [elfcorehdr_addr is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([fib_lookup],
+               [net/ipv4/fib_rules.c],
+               [AC_DEFINE(HAVE_FIB_LOOKUP_EXPORTED, 1,
+                       [fib_lookup is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([idr_get_next_ul],
+               [lib/idr.c],
+               [AC_DEFINE(HAVE_IDR_GET_NEXT_UL_EXPORTED, 1,
+                       [idr_get_next_ul is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([idr_get_next],
+               [lib/idr.c],
+               [AC_DEFINE(HAVE_IDR_GET_NEXT_EXPORTED, 1,
+                       [idr_get_next is exported by the kernel])],
+       [])
+
+       AC_MSG_CHECKING([if pci.h has pci_irq_get_affinity])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/pci.h>
+       ],[
+               pci_irq_get_affinity(NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_PCI_IRQ_GET_AFFINITY, 1,
+                         [pci_irq_get_affinity is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       LB_CHECK_SYMBOL_EXPORT([elfcorehdr_addr],
+               [kernel/crash_dump.c],
+               [AC_DEFINE(HAVE_ELFCOREHDR_ADDR_EXPORTED, 1,
+                       [elfcorehdr_addr is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([fib_lookup],
+               [net/ipv4/fib_rules.c],
+               [AC_DEFINE(HAVE_FIB_LOOKUP_EXPORTED, 1,
+                       [fib_lookup is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([idr_get_next_ul],
+               [lib/idr.c],
+               [AC_DEFINE(HAVE_IDR_GET_NEXT_UL_EXPORTED, 1,
+                       [idr_get_next_ul is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([idr_get_next],
+               [lib/idr.c],
+               [AC_DEFINE(HAVE_IDR_GET_NEXT_EXPORTED, 1,
+                       [idr_get_next is exported by the kernel])],
+       [])
+
+       AC_MSG_CHECKING([if idr.h has idr_preload_end])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/idr.h>
+       ],[
+               idr_preload_end();
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_IDR_PRELOAD_END, 1,
+                         [idr_preload_end is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if smp_load_acquire is defined])
+       LB_LINUX_TRY_COMPILE([
+               #include <asm-generic/barrier.h>
+       ],[
+               u32 x;
+               smp_load_acquire(&x);
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_SMP_LOAD_ACQUIRE, 1,
+                         [smp_load_acquire is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       LB_CHECK_SYMBOL_EXPORT([idr_preload],
+               [lib/radix-tree.c],
+               [AC_DEFINE(HAVE_IDR_PRELOAD_EXPORTED, 1,
+                       [idr_preload is exported by the kernel])],
+       [])
+
+       LB_CHECK_SYMBOL_EXPORT([radix_tree_iter_delete],
+               [lib/radix-tree.c],
+               [AC_DEFINE(HAVE_RADIX_TREE_ITER_DELETE_EXPORTED, 1,
+                       [radix_tree_iter_delete is exported by the kernel])],
+       [])
+       LB_CHECK_SYMBOL_EXPORT([kobj_ns_grab_current],
+               [lib/kobject.c],
+               [AC_DEFINE(HAVE_KOBJ_NS_GRAB_CURRENT_EXPORTED, 1,
+                       [kobj_ns_grab_current is exported by the kernel])],
+       [])
+
+       AC_MSG_CHECKING([if mm.h struct vm_operations_struct has .fault])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/mm.h>
+               static vm_fault_t rdma_umap_fault(struct vm_fault *vmf) {
+                       return NULL;
+               }
+
+       ],[
+               struct vm_operations_struct rdma_umap_ops = {
+                       .fault = rdma_umap_fault,
+               };
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_VM_OPERATIONS_STRUCT_HAS_FAULT, 1,
+                         [vm_operations_struct has .fault])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if radix-tree.h has radix_tree_iter_lookup])
+       LB_LINUX_TRY_COMPILE([
+       #include <linux/radix-tree.h>
+       ],[
+               radix_tree_iter_lookup(NULL, NULL, 0);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_RADIX_TREE_ITER_LOOKUP, 1,
+               [radix_tree_iter_lookup is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if device.h struct class has member class_groups])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/device.h>
+               #include <linux/sysfs.h>
+       ],[
+               static struct attribute *umad_class_attrs[] = {
+                       NULL,
+               };
+               ATTRIBUTE_GROUPS(umad_class);
+
+               struct class x = {
+                       .class_groups = umad_class_groups,
+               };
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_CLASS_GROUPS, 1,
+                         [class_groups is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if mm.h has want_init_on_alloc])
+       LB_LINUX_TRY_COMPILE([
+       #include <linux/mm.h>
+       ],[
+               gfp_t flags = __GFP_ZERO;
+               want_init_on_alloc(flags);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_WANT_INIT_ON_ALLOC, 1,
+               [want_init_on_alloc is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if mm.h has FOLL_LONGTERM])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/mm.h>
+       ],[
+               int x = FOLL_LONGTERM;
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_FOLL_LONGTERM, 1,
+                       [FOLL_LONGTERM is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if get_user_pages has 7 params])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/mm.h>
+       ],[
+               unsigned long start;
+               unsigned long nr_pages;
+               unsigned int gup_flags;
+               struct page **page_list;
+               struct vm_area_struct **vmas;
+               int ret;
+
+               ret = get_user_pages(NULL, NULL, start, nr_pages, gup_flags,
+                                       page_list, vmas);
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_GET_USER_PAGES_7_PARAMS, 1,
+                       [get_user_pages has 7 params])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if radix-tree.h has radix_tree_iter_delete])
+       LB_LINUX_TRY_COMPILE([
+       #include <linux/radix-tree.h>
+       ],[
+               radix_tree_iter_delete(NULL, NULL, NULL);
+
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_RADIX_TREE_ITER_DELETE, 1,
+               [radix_tree_iter_delete is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
+       AC_MSG_CHECKING([if mm.h has put_user_page])
+       LB_LINUX_TRY_COMPILE([
+               #include <linux/mm.h>
+       ],[
+               struct page *page;
+
+               put_user_page(page);
+               return 0;
+       ],[
+               AC_MSG_RESULT(yes)
+               AC_DEFINE(HAVE_PUT_USER_PAGE, 1,
+                       [put_user_page is defined])
+       ],[
+               AC_MSG_RESULT(no)
+       ])
+
 ])
 #
 # COMPAT_CONFIG_HEADERS
index b24c478..bc4a1b1 100644 (file)
@@ -60,6 +60,7 @@ void backport_dependency_symbol(void);
 #include <linux/compat-4.11.h>
 #include <linux/compat-4.16.h>
 #include <linux/compat-4.17.h>
+#include <linux/compat-5.3.h>
 
 #endif /* CONFIG_COMPAT_RDMA */
 #endif /* LINUX_26_COMPAT_H */
diff --git a/include/linux/compat-5.3.h b/include/linux/compat-5.3.h
new file mode 100644 (file)
index 0000000..e07fc82
--- /dev/null
@@ -0,0 +1,22 @@
+#ifndef LINUX_5_3_COMPAT_H
+#define LINUX_5_3_COMPAT_H
+
+#include <linux/version.h>
+
+#if (LINUX_VERSION_CODE < KERNEL_VERSION(5,3,0))
+
+#include <linux/lockdep.h>
+
+#ifndef lockdep_is_held_type
+#define lockdep_is_held_type(l, r)      (1)
+#endif
+
+#ifndef lockdep_assert_held_write
+#define lockdep_assert_held_write(l)    do {            \
+        WARN_ON(debug_locks && !lockdep_is_held_type(l, 0));    \
+    } while (0)
+#endif
+
+#endif /* (LINUX_VERSION_CODE < KERNEL_VERSION(5,3,0)) */
+
+#endif /* LINUX_5_3_COMPAT_H */
diff --git a/include/linux/dim.h b/include/linux/dim.h
new file mode 100644 (file)
index 0000000..9fa4b3f
--- /dev/null
@@ -0,0 +1,333 @@
+/* SPDX-License-Identifier: GPL-2.0 OR Linux-OpenIB */
+/* Copyright (c) 2019 Mellanox Technologies. */
+
+#ifndef DIM_H
+#define DIM_H
+
+#include <linux/module.h>
+
+/**
+ * Number of events between DIM iterations.
+ * Causes a moderation of the algorithm run.
+ */
+#define DIM_NEVENTS 64
+
+/**
+ * Is a difference between values justifies taking an action.
+ * We consider 10% difference as significant.
+ */
+#define IS_SIGNIFICANT_DIFF(val, ref) \
+       (((100UL * abs((val) - (ref))) / (ref)) > 10)
+
+/**
+ * Calculate the gap between two values.
+ * Take wrap-around and variable size into consideration.
+ */
+#define BIT_GAP(bits, end, start) ((((end) - (start)) + BIT_ULL(bits)) \
+               & (BIT_ULL(bits) - 1))
+
+/**
+ * Structure for CQ moderation values.
+ * Used for communications between DIM and its consumer.
+ *
+ * @usec: CQ timer suggestion (by DIM)
+ * @pkts: CQ packet counter suggestion (by DIM)
+ * @cq_period_mode: CQ priod count mode (from CQE/EQE)
+ */
+struct dim_cq_moder {
+       u16 usec;
+       u16 pkts;
+       u16 comps;
+       u8 cq_period_mode;
+};
+
+/**
+ * Structure for DIM sample data.
+ * Used for communications between DIM and its consumer.
+ *
+ * @time: Sample timestamp
+ * @pkt_ctr: Number of packets
+ * @byte_ctr: Number of bytes
+ * @event_ctr: Number of events
+ */
+struct dim_sample {
+       ktime_t time;
+       u32 pkt_ctr;
+       u32 byte_ctr;
+       u16 event_ctr;
+       u32 comp_ctr;
+};
+
+/**
+ * Structure for DIM stats.
+ * Used for holding current measured rates.
+ *
+ * @ppms: Packets per msec
+ * @bpms: Bytes per msec
+ * @epms: Events per msec
+ */
+struct dim_stats {
+       int ppms; /* packets per msec */
+       int bpms; /* bytes per msec */
+       int epms; /* events per msec */
+       int cpms; /* completions per msec */
+       int cpe_ratio; /* ratio of completions to events */
+};
+
+/**
+ * Main structure for dynamic interrupt moderation (DIM).
+ * Used for holding all information about a specific DIM instance.
+ *
+ * @state: Algorithm state (see below)
+ * @prev_stats: Measured rates from previous iteration (for comparison)
+ * @start_sample: Sampled data at start of current iteration
+ * @work: Work to perform on action required
+ * @priv: A pointer to the struct that points to dim
+ * @profile_ix: Current moderation profile
+ * @mode: CQ period count mode
+ * @tune_state: Algorithm tuning state (see below)
+ * @steps_right: Number of steps taken towards higher moderation
+ * @steps_left: Number of steps taken towards lower moderation
+ * @tired: Parking depth counter
+ */
+struct dim {
+       u8 state;
+       struct dim_stats prev_stats;
+       struct dim_sample start_sample;
+       struct dim_sample measuring_sample;
+       struct work_struct work;
+       void *priv;
+       u8 profile_ix;
+       u8 mode;
+       u8 tune_state;
+       u8 steps_right;
+       u8 steps_left;
+       u8 tired;
+};
+
+/**
+ * enum dim_cq_period_mode
+ *
+ * These are the modes for CQ period count.
+ *
+ * @DIM_CQ_PERIOD_MODE_START_FROM_EQE: Start counting from EQE
+ * @DIM_CQ_PERIOD_MODE_START_FROM_CQE: Start counting from CQE (implies timer reset)
+ * @DIM_CQ_PERIOD_NUM_MODES: Number of modes
+ */
+enum {
+       DIM_CQ_PERIOD_MODE_START_FROM_EQE = 0x0,
+       DIM_CQ_PERIOD_MODE_START_FROM_CQE = 0x1,
+       DIM_CQ_PERIOD_NUM_MODES
+};
+
+/**
+ * enum dim_state
+ *
+ * These are the DIM algorithm states.
+ * These will determine if the algorithm is in a valid state to start an iteration.
+ *
+ * @DIM_START_MEASURE: This is the first iteration (also after applying a new profile)
+ * @DIM_MEASURE_IN_PROGRESS: Algorithm is already in progress - check if
+ * need to perform an action
+ * @DIM_APPLY_NEW_PROFILE: DIM consumer is currently applying a profile - no need to measure
+ */
+enum {
+       DIM_START_MEASURE,
+       DIM_MEASURE_IN_PROGRESS,
+       DIM_APPLY_NEW_PROFILE,
+};
+
+/**
+ * enum dim_tune_state
+ *
+ * These are the DIM algorithm tune states.
+ * These will determine which action the algorithm should perform.
+ *
+ * @DIM_PARKING_ON_TOP: Algorithm found a local top point - exit on significant difference
+ * @DIM_PARKING_TIRED: Algorithm found a deep top point - don't exit if tired > 0
+ * @DIM_GOING_RIGHT: Algorithm is currently trying higher moderation levels
+ * @DIM_GOING_LEFT: Algorithm is currently trying lower moderation levels
+ */
+enum {
+       DIM_PARKING_ON_TOP,
+       DIM_PARKING_TIRED,
+       DIM_GOING_RIGHT,
+       DIM_GOING_LEFT,
+};
+
+/**
+ * enum dim_stats_state
+ *
+ * These are the DIM algorithm statistics states.
+ * These will determine the verdict of current iteration.
+ *
+ * @DIM_STATS_WORSE: Current iteration shows worse performance than before
+ * @DIM_STATS_WORSE: Current iteration shows same performance than before
+ * @DIM_STATS_WORSE: Current iteration shows better performance than before
+ */
+enum {
+       DIM_STATS_WORSE,
+       DIM_STATS_SAME,
+       DIM_STATS_BETTER,
+};
+
+/**
+ * enum dim_step_result
+ *
+ * These are the DIM algorithm step results.
+ * These describe the result of a step.
+ *
+ * @DIM_STEPPED: Performed a regular step
+ * @DIM_TOO_TIRED: Same kind of step was done multiple times - should go to
+ * tired parking
+ * @DIM_ON_EDGE: Stepped to the most left/right profile
+ */
+enum {
+       DIM_STEPPED,
+       DIM_TOO_TIRED,
+       DIM_ON_EDGE,
+};
+
+/**
+ *     dim_on_top - check if current state is a good place to stop (top location)
+ *     @dim: DIM context
+ *
+ * Check if current profile is a good place to park at.
+ * This will result in reducing the DIM checks frequency as we assume we
+ * shouldn't probably change profiles, unless traffic pattern wasn't changed.
+ */
+bool dim_on_top(struct dim *dim);
+
+/**
+ *     dim_turn - change profile alterning direction
+ *     @dim: DIM context
+ *
+ * Go left if we were going right and vice-versa.
+ * Do nothing if currently parking.
+ */
+void dim_turn(struct dim *dim);
+
+/**
+ *     dim_park_on_top - enter a parking state on a top location
+ *     @dim: DIM context
+ *
+ * Enter parking state.
+ * Clear all movement history.
+ */
+void dim_park_on_top(struct dim *dim);
+
+/**
+ *     dim_park_tired - enter a tired parking state
+ *     @dim: DIM context
+ *
+ * Enter parking state.
+ * Clear all movement history and cause DIM checks frequency to reduce.
+ */
+void dim_park_tired(struct dim *dim);
+
+/**
+ *     dim_calc_stats - calculate the difference between two samples
+ *     @start: start sample
+ *     @end: end sample
+ *     @curr_stats: delta between samples
+ *
+ * Calculate the delta between two samples (in data rates).
+ * Takes into consideration counter wrap-around.
+ */
+void dim_calc_stats(struct dim_sample *start, struct dim_sample *end,
+                   struct dim_stats *curr_stats);
+
+/**
+ *     dim_update_sample - set a sample's fields with give values
+ *     @event_ctr: number of events to set
+ *     @packets: number of packets to set
+ *     @bytes: number of bytes to set
+ *     @s: DIM sample
+ */
+static inline void
+dim_update_sample(u16 event_ctr, u64 packets, u64 bytes, struct dim_sample *s)
+{
+       s->time      = ktime_get();
+       s->pkt_ctr   = packets;
+       s->byte_ctr  = bytes;
+       s->event_ctr = event_ctr;
+}
+
+/**
+ *     dim_update_sample_with_comps - set a sample's fields with given
+ *     values including the completion parameter
+ *     @event_ctr: number of events to set
+ *     @packets: number of packets to set
+ *     @bytes: number of bytes to set
+ *     @comps: number of completions to set
+ *     @s: DIM sample
+ */
+static inline void
+dim_update_sample_with_comps(u16 event_ctr, u64 packets, u64 bytes, u64 comps,
+                            struct dim_sample *s)
+{
+       dim_update_sample(event_ctr, packets, bytes, s);
+       s->comp_ctr = comps;
+}
+
+/* Net DIM */
+
+/**
+ *     net_dim_get_rx_moderation - provide a CQ moderation object for the given RX profile
+ *     @cq_period_mode: CQ period mode
+ *     @ix: Profile index
+ */
+struct dim_cq_moder net_dim_get_rx_moderation(u8 cq_period_mode, int ix);
+
+/**
+ *     net_dim_get_def_rx_moderation - provide the default RX moderation
+ *     @cq_period_mode: CQ period mode
+ */
+struct dim_cq_moder net_dim_get_def_rx_moderation(u8 cq_period_mode);
+
+/**
+ *     net_dim_get_tx_moderation - provide a CQ moderation object for the given TX profile
+ *     @cq_period_mode: CQ period mode
+ *     @ix: Profile index
+ */
+struct dim_cq_moder net_dim_get_tx_moderation(u8 cq_period_mode, int ix);
+
+/**
+ *     net_dim_get_def_tx_moderation - provide the default TX moderation
+ *     @cq_period_mode: CQ period mode
+ */
+struct dim_cq_moder net_dim_get_def_tx_moderation(u8 cq_period_mode);
+
+/**
+ *     net_dim - main DIM algorithm entry point
+ *     @dim: DIM instance information
+ *     @end_sample: Current data measurement
+ *
+ * Called by the consumer.
+ * This is the main logic of the algorithm, where data is processed in order to decide on next
+ * required action.
+ */
+void net_dim(struct dim *dim, struct dim_sample end_sample);
+
+/* RDMA DIM */
+
+/*
+ * RDMA DIM profile:
+ * profile size must be of RDMA_DIM_PARAMS_NUM_PROFILES.
+ */
+#define RDMA_DIM_PARAMS_NUM_PROFILES 9
+#define RDMA_DIM_START_PROFILE 0
+
+/**
+ * rdma_dim - Runs the adaptive moderation.
+ * @dim: The moderation struct.
+ * @completions: The number of completions collected in this round.
+ *
+ * Each call to rdma_dim takes the latest amount of completions that
+ * have been collected and counts them as a new event.
+ * Once enough events have been collected the algorithm decides a new
+ * moderation level.
+ */
+void rdma_dim(struct dim *dim, u64 completions);
+
+#endif /* DIM_H */
diff --git a/include/linux/idr.h b/include/linux/idr.h
new file mode 100644 (file)
index 0000000..5b5f0bf
--- /dev/null
@@ -0,0 +1,45 @@
+#ifndef _COMPAT_LINUX_IDR_H
+#define _COMPAT_LINUX_IDR_H
+
+#include "../../compat/config.h"
+
+#include_next <linux/idr.h>
+
+#ifndef HAVE_IDR_GET_NEXT_EXPORTED
+#define idr_get_next LINUX_BACKPORT(idr_get_next)
+void *idr_get_next(struct idr *idr, int *nextid);
+#endif
+
+#ifndef HAVE_IDR_PRELOAD_END
+static inline void idr_preload_end(void)
+{
+               preempt_enable();
+}
+#endif
+#ifndef HAVE_IDR_FOR_EACH_ENTRY
+#define compat_idr_for_each_entry(idr, entry, id)                      \
+               for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id)
+#else
+#define compat_idr_for_each_entry(idr, entry, id)          \
+               idr_for_each_entry(idr, entry, id)
+#endif
+
+#ifndef HAVE_IDA_SIMPLE_GET
+#define ida_simple_remove LINUX_BACKPORT(ida_simple_remove)
+void ida_simple_remove(struct ida *ida, unsigned int id);
+
+#define ida_simple_get LINUX_BACKPORT(ida_simple_get)
+int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
+                  gfp_t gfp_mask);
+
+#endif /* HAVE_IDA_SIMPLE_GET */
+#ifndef HAVE_IDR_GET_NEXT_UL_EXPORTED
+#define idr_get_next_ul LINUX_BACKPORT(idr_get_next_ul)
+void *idr_get_next_ul(struct idr *idr, unsigned long *nextid);
+
+
+#define idr_alloc_u32 LINUX_BACKPORT(idr_alloc_u32)
+int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
+               unsigned long max, gfp_t gfp);
+#endif
+#endif /* _COMPAT_LINUX_IDR_H */
diff --git a/include/linux/inetdevice.h b/include/linux/inetdevice.h
new file mode 100644 (file)
index 0000000..f3f4c41
--- /dev/null
@@ -0,0 +1,13 @@
+#ifndef _COMPAT_LINUX_INETDEVICE_H
+#define _COMPAT_LINUX_INETDEVICE_H 1
+
+#include "../../compat/config.h"
+#include_next <linux/inetdevice.h>
+
+#ifndef in_dev_for_each_ifa_rcu
+#define in_dev_for_each_ifa_rcu(ifa, in_dev)                   \
+       for (ifa = (in_dev)->ifa_list; ifa;                     \
+            ifa = ifa->ifa_next)
+#endif
+
+#endif /* __COMPAT_LINUX_INETDEVICE_H */
index 282ef67..6793737 100644 (file)
@@ -60,4 +60,38 @@ static inline void *kvzalloc_node(size_t size, gfp_t flags, int node)
 }
 #endif
 
+#ifndef HAVE_WANT_INIT_ON_ALLOC
+static inline bool want_init_on_alloc(gfp_t flags)
+{
+       return flags & __GFP_ZERO;
+}
+#endif
+
+#ifndef HAVE_PUT_USER_PAGE
+/**
+ * put_user_page() - release a gup-pinned page
+ * @page:            pointer to page to be released
+ *
+ * Pages that were pinned via get_user_pages*() must be released via
+ * either put_user_page(), or one of the put_user_pages*() routines
+ * below. This is so that eventually, pages that are pinned via
+ * get_user_pages*() can be separately tracked and uniquely handled. In
+ * particular, interactions with RDMA and filesystems need special
+ * handling.
+ *
+ * put_user_page() and put_page() are not interchangeable, despite this early
+ * implementation that makes them look the same. put_user_page() calls must
+ * be perfectly matched up with get_user_page() calls.
+ */
+static inline void put_user_page(struct page *page)
+{
+       put_page(page);
+}
+
+void put_user_pages_dirty(struct page **pages, unsigned long npages);
+void put_user_pages_dirty_lock(struct page **pages, unsigned long npages);
+void put_user_pages(struct page **pages, unsigned long npages);
+#endif /* HAVE_PUT_USER_PAGE */
+
 #endif /* _COMPAT_LINUX_MM_H */
+
index c747ef6..255f3b7 100644 (file)
@@ -6,6 +6,57 @@
 
 #include_next <linux/netdevice.h>
 
+#ifndef SET_ETHTOOL_OPS
+#define SET_ETHTOOL_OPS(netdev,ops) \
+    ( (netdev)->ethtool_ops = (ops) )
+#endif
+
+#if !defined(HAVE_NETDEV_EXTENDED_HW_FEATURES)     && \
+    !defined(HAVE_NETDEV_OPS_EXT_NDO_FIX_FEATURES) && \
+    !defined(HAVE_NETDEV_OPS_EXT_NDO_SET_FEATURES) && \
+    !defined(HAVE_NDO_SET_FEATURES)
+#define LEGACY_ETHTOOL_OPS
+#endif
+
+#ifndef NETDEV_BONDING_INFO
+#define NETDEV_BONDING_INFO     0x0019
+#endif
+
+
+#ifndef HAVE_NETDEV_MASTER_UPPER_DEV_GET_RCU
+#define netdev_master_upper_dev_get_rcu(x) (x)->master
+#define netdev_master_upper_dev_get(x) \
+       netdev_master_upper_dev_get_rcu(x)
+#else
+static inline int netdev_set_master(struct net_device *dev,
+                                   struct net_device *master)
+{
+       int rc = 0;
+
+       if (master) {
+#if defined(NETDEV_MASTER_UPPER_DEV_LINK_4_PARAMS)
+               rc = netdev_master_upper_dev_link(dev, master, NULL, NULL);
+#elif defined(NETDEV_MASTER_UPPER_DEV_LINK_5_PARAMS)
+               rc = netdev_master_upper_dev_link(dev, master,
+                                                 NULL, NULL, NULL);
+#else
+               rc = netdev_master_upper_dev_link(dev, master);
+#endif
+       } else {
+               master = netdev_master_upper_dev_get_rcu(dev);
+               netdev_upper_dev_unlink(dev, master);
+       }
+       return rc;
+}
+#endif
+
+#ifdef HAVE_ALLOC_NETDEV_MQS_5_PARAMS
+#define alloc_netdev_mqs(p1, p2, p3, p4, p5, p6) alloc_netdev_mqs(p1, p2, p4, p5, p6)
+#elif defined(HAVE_ALLOC_NETDEV_MQ_4_PARAMS)
+#define alloc_netdev_mqs(sizeof_priv, name, name_assign_type, setup, txqs, rxqs)       \
+       alloc_netdev_mq(sizeof_priv, name, setup,                                       \
+                       max_t(unsigned int, txqs, rxqs))
+#endif
 #ifdef HAVE_REGISTER_NETDEVICE_NOTIFIER_RH
 #define register_netdevice_notifier register_netdevice_notifier_rh
 #define unregister_netdevice_notifier unregister_netdevice_notifier_rh
diff --git a/include/linux/overflow.h b/include/linux/overflow.h
new file mode 100644 (file)
index 0000000..f533a2a
--- /dev/null
@@ -0,0 +1,307 @@
+#ifndef _COMPAT_LINUX_OVERFLOW_H
+#define _COMPAT_LINUX_OVERFLOW_H
+
+#include "../../compat/config.h"
+
+#ifdef HAVE_LINUX_OVERFLOW_H
+#include_next <linux/overflow.h>
+#else
+
+/* SPDX-License-Identifier: GPL-2.0 OR MIT */
+#ifndef __LINUX_OVERFLOW_H
+#define __LINUX_OVERFLOW_H
+
+#include <linux/compiler.h>
+
+/*
+ * In the fallback code below, we need to compute the minimum and
+ * maximum values representable in a given type. These macros may also
+ * be useful elsewhere, so we provide them outside the
+ * COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW block.
+ *
+ * It would seem more obvious to do something like
+ *
+ * #define type_min(T) (T)(is_signed_type(T) ? (T)1 << (8*sizeof(T)-1) : 0)
+ * #define type_max(T) (T)(is_signed_type(T) ? ((T)1 << (8*sizeof(T)-1)) - 1 : ~(T)0)
+ *
+ * Unfortunately, the middle expressions, strictly speaking, have
+ * undefined behaviour, and at least some versions of gcc warn about
+ * the type_max expression (but not if -fsanitize=undefined is in
+ * effect; in that case, the warning is deferred to runtime...).
+ *
+ * The slightly excessive casting in type_min is to make sure the
+ * macros also produce sensible values for the exotic type _Bool. [The
+ * overflow checkers only almost work for _Bool, but that's
+ * a-feature-not-a-bug, since people shouldn't be doing arithmetic on
+ * _Bools. Besides, the gcc builtins don't allow _Bool* as third
+ * argument.]
+ *
+ * Idea stolen from
+ * https://mail-index.netbsd.org/tech-misc/2007/02/05/0000.html -
+ * credit to Christian Biere.
+ */
+#define is_signed_type(type)       (((type)(-1)) < (type)1)
+#define __type_half_max(type) ((type)1 << (8*sizeof(type) - 1 - is_signed_type(type)))
+#define type_max(T) ((T)((__type_half_max(T) - 1) + __type_half_max(T)))
+#define type_min(T) ((T)((T)-type_max(T)-(T)1))
+
+
+#ifdef COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW
+/*
+ * For simplicity and code hygiene, the fallback code below insists on
+ * a, b and *d having the same type (similar to the min() and max()
+ * macros), whereas gcc's type-generic overflow checkers accept
+ * different types. Hence we don't just make check_add_overflow an
+ * alias for __builtin_add_overflow, but add type checks similar to
+ * below.
+ */
+#define check_add_overflow(a, b, d) ({         \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       __builtin_add_overflow(__a, __b, __d);  \
+})
+
+#define check_sub_overflow(a, b, d) ({         \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       __builtin_sub_overflow(__a, __b, __d);  \
+})
+
+#define check_mul_overflow(a, b, d) ({         \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       __builtin_mul_overflow(__a, __b, __d);  \
+})
+
+#else
+
+
+/* Checking for unsigned overflow is relatively easy without causing UB. */
+#define __unsigned_add_overflow(a, b, d) ({    \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       *__d = __a + __b;                       \
+       *__d < __a;                             \
+})
+#define __unsigned_sub_overflow(a, b, d) ({    \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       *__d = __a - __b;                       \
+       __a < __b;                              \
+})
+/*
+ * If one of a or b is a compile-time constant, this avoids a division.
+ */
+#define __unsigned_mul_overflow(a, b, d) ({            \
+       typeof(a) __a = (a);                            \
+       typeof(b) __b = (b);                            \
+       typeof(d) __d = (d);                            \
+       (void) (&__a == &__b);                          \
+       (void) (&__a == __d);                           \
+       *__d = __a * __b;                               \
+       __builtin_constant_p(__b) ?                     \
+         __b > 0 && __a > type_max(typeof(__a)) / __b : \
+         __a > 0 && __b > type_max(typeof(__b)) / __a;  \
+})
+
+/*
+ * For signed types, detecting overflow is much harder, especially if
+ * we want to avoid UB. But the interface of these macros is such that
+ * we must provide a result in *d, and in fact we must produce the
+ * result promised by gcc's builtins, which is simply the possibly
+ * wrapped-around value. Fortunately, we can just formally do the
+ * operations in the widest relevant unsigned type (u64) and then
+ * truncate the result - gcc is smart enough to generate the same code
+ * with and without the (u64) casts.
+ */
+
+/*
+ * Adding two signed integers can overflow only if they have the same
+ * sign, and overflow has happened iff the result has the opposite
+ * sign.
+ */
+#define __signed_add_overflow(a, b, d) ({      \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       *__d = (u64)__a + (u64)__b;             \
+       (((~(__a ^ __b)) & (*__d ^ __a))        \
+               & type_min(typeof(__a))) != 0;  \
+})
+
+/*
+ * Subtraction is similar, except that overflow can now happen only
+ * when the signs are opposite. In this case, overflow has happened if
+ * the result has the opposite sign of a.
+ */
+#define __signed_sub_overflow(a, b, d) ({      \
+       typeof(a) __a = (a);                    \
+       typeof(b) __b = (b);                    \
+       typeof(d) __d = (d);                    \
+       (void) (&__a == &__b);                  \
+       (void) (&__a == __d);                   \
+       *__d = (u64)__a - (u64)__b;             \
+       ((((__a ^ __b)) & (*__d ^ __a))         \
+               & type_min(typeof(__a))) != 0;  \
+})
+
+/*
+ * Signed multiplication is rather hard. gcc always follows C99, so
+ * division is truncated towards 0. This means that we can write the
+ * overflow check like this:
+ *
+ * (a > 0 && (b > MAX/a || b < MIN/a)) ||
+ * (a < -1 && (b > MIN/a || b < MAX/a) ||
+ * (a == -1 && b == MIN)
+ *
+ * The redundant casts of -1 are to silence an annoying -Wtype-limits
+ * (included in -Wextra) warning: When the type is u8 or u16, the
+ * __b_c_e in check_mul_overflow obviously selects
+ * __unsigned_mul_overflow, but unfortunately gcc still parses this
+ * code and warns about the limited range of __b.
+ */
+
+#define __signed_mul_overflow(a, b, d) ({                              \
+       typeof(a) __a = (a);                                            \
+       typeof(b) __b = (b);                                            \
+       typeof(d) __d = (d);                                            \
+       typeof(a) __tmax = type_max(typeof(a));                         \
+       typeof(a) __tmin = type_min(typeof(a));                         \
+       (void) (&__a == &__b);                                          \
+       (void) (&__a == __d);                                           \
+       *__d = (u64)__a * (u64)__b;                                     \
+       (__b > 0   && (__a > __tmax/__b || __a < __tmin/__b)) ||        \
+       (__b < (typeof(__b))-1  && (__a > __tmin/__b || __a < __tmax/__b)) || \
+       (__b == (typeof(__b))-1 && __a == __tmin);                      \
+})
+
+
+#define check_add_overflow(a, b, d)                                    \
+       __builtin_choose_expr(is_signed_type(typeof(a)),                \
+                       __signed_add_overflow(a, b, d),                 \
+                       __unsigned_add_overflow(a, b, d))
+
+#define check_sub_overflow(a, b, d)                                    \
+       __builtin_choose_expr(is_signed_type(typeof(a)),                \
+                       __signed_sub_overflow(a, b, d),                 \
+                       __unsigned_sub_overflow(a, b, d))
+
+#define check_mul_overflow(a, b, d)                                    \
+       __builtin_choose_expr(is_signed_type(typeof(a)),                \
+                       __signed_mul_overflow(a, b, d),                 \
+                       __unsigned_mul_overflow(a, b, d))
+
+
+#endif /* COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW */
+
+#endif /* __LINUX_OVERFLOW_H */
+
+#endif /* HAVE_LINUX_OVERFLOW_H */
+
+#ifndef struct_size
+/**
+ * array_size() - Calculate size of 2-dimensional array.
+ *
+ * @a: dimension one
+ * @b: dimension two
+ *
+ * Calculates size of 2-dimensional array: @a * @b.
+ *
+ * Returns: number of bytes needed to represent the array or SIZE_MAX on
+ * overflow.
+ */
+static inline __must_check size_t array_size(size_t a, size_t b)
+{
+       size_t bytes;
+
+       if (check_mul_overflow(a, b, &bytes))
+               return SIZE_MAX;
+
+       return bytes;
+}
+
+/**
+ * array3_size() - Calculate size of 3-dimensional array.
+ *
+ * @a: dimension one
+ * @b: dimension two
+ * @c: dimension three
+ *
+ * Calculates size of 3-dimensional array: @a * @b * @c.
+ *
+ * Returns: number of bytes needed to represent the array or SIZE_MAX on
+ * overflow.
+ */
+static inline __must_check size_t array3_size(size_t a, size_t b, size_t c)
+{
+       size_t bytes;
+
+       if (check_mul_overflow(a, b, &bytes))
+               return SIZE_MAX;
+       if (check_mul_overflow(bytes, c, &bytes))
+               return SIZE_MAX;
+
+       return bytes;
+}
+
+static inline __must_check size_t __ab_c_size(size_t n, size_t size, size_t c)
+{
+       size_t bytes;
+
+       if (check_mul_overflow(n, size, &bytes))
+               return SIZE_MAX;
+       if (check_add_overflow(bytes, c, &bytes))
+               return SIZE_MAX;
+
+       return bytes;
+}
+
+/**
+ * struct_size() - Calculate size of structure with trailing array.
+ * @p: Pointer to the structure.
+ * @member: Name of the array member.
+ * @n: Number of elements in the array.
+ *
+ * Calculates size of memory needed for structure @p followed by an
+ * array of @n @member elements.
+ *
+ * Return: number of bytes needed or SIZE_MAX on overflow.
+ */
+#define struct_size(p, member, n)                                      \
+       __ab_c_size(n,                                                  \
+                   sizeof(*(p)->member) + __must_be_array((p)->member),\
+                   sizeof(*(p)))
+#endif /* struct_size */
+
+#ifndef check_shl_overflow
+#define check_shl_overflow(a, s, d) ({                                 \
+       typeof(a) _a = a;                                               \
+       typeof(s) _s = s;                                               \
+       typeof(d) _d = d;                                               \
+       u64 _a_full = _a;                                               \
+       unsigned int _to_shift =                                        \
+               _s >= 0 && _s < 8 * sizeof(*d) ? _s : 0;                \
+       *_d = (_a_full << _to_shift);                                   \
+       (_to_shift != _s || *_d < 0 || _a < 0 ||                        \
+               (*_d >> _to_shift) != _a);                              \
+})
+#endif /* check_shl_overflow */
+
+#endif /* _COMPAT_LINUX_OVERFLOW_H */
index d4616ba..1427557 100644 (file)
@@ -7,4 +7,53 @@
 #include_next <linux/sched/mm.h>
 #endif
 
+#ifdef HAVE_SCHED_H
+#include_next <linux/sched.h>
+#endif
+
+#ifndef HAVE_MMGET_NOT_ZERO
+#ifndef HAVE_SCHED_MMGET_NOT_ZERO
+static inline bool mmget_not_zero(struct mm_struct *mm)
+{
+       return atomic_inc_not_zero(&mm->mm_users);
+}
+#endif
+#endif
+
+#ifndef HAVE_MMGRAB
+static inline void mmgrab(struct mm_struct *mm)
+{
+       atomic_inc(&mm->mm_count);
+}
+#endif
+
+#ifndef HAVE_MMGET
+static inline void mmget(struct mm_struct *mm)
+{
+       atomic_inc(&mm->mm_users);
+}
+
+#endif
+#ifndef HAVE_MMGET_STILL_VALID
+/*
+ * This has to be called after a get_task_mm()/mmget_not_zero()
+ * followed by taking the mmap_sem for writing before modifying the
+ * vmas or anything the coredump pretends not to change from under it.
+ *
+ * NOTE: find_extend_vma() called from GUP context is the only place
+ * that can modify the "mm" (notably the vm_start/end) under mmap_sem
+ * for reading and outside the context of the process, so it is also
+ * the only case that holds the mmap_sem for reading that must call
+ * this function. Generally if the mmap_sem is hold for reading
+ * there's no need of this check after get_task_mm()/mmget_not_zero().
+ *
+ * This function can be obsoleted and the check can be removed, after
+ * the coredump code will hold the mmap_sem for writing before
+ * invoking the ->core_dump methods.
+ */
+static inline bool mmget_still_valid(struct mm_struct *mm)
+{
+       return likely(!mm->core_state);
+}
+#endif
 #endif /* COMPAT_LINUX_SCHED_MM_H */
index 4e36ebd..d327380 100644 (file)
@@ -4,6 +4,7 @@
 #include "../../compat/config.h"
 
 #include_next <linux/slab.h>
+#include <linux/overflow.h>
 
 #ifndef HAVE_KMALLOC_ARRAY
 /**
diff --git a/include/linux/vmalloc.h b/include/linux/vmalloc.h
new file mode 100644 (file)
index 0000000..9b30849
--- /dev/null
@@ -0,0 +1,18 @@
+#ifndef _COMPAT_LINUX_VMALLOC_H
+#define _COMPAT_LINUX_VMALLOC_H
+
+#include "../../compat/config.h"
+
+#include <linux/version.h>
+#include_next <linux/vmalloc.h>
+#include <linux/overflow.h>
+
+#if (LINUX_VERSION_CODE < KERNEL_VERSION(2,6,37))
+#define vzalloc LINUX_BACKPORT(vzalloc)
+#define vzalloc_node LINUX_BACKPORT(vzalloc_node)
+
+extern void *vzalloc(unsigned long size);
+extern void *vzalloc_node(unsigned long size, int node);
+#endif /* (LINUX_VERSION_CODE < KERNEL_VERSION(2,6,37)) */
+
+#endif /* _COMPAT_LINUX_VMALLOC_H */
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
new file mode 100644 (file)
index 0000000..5921599
--- /dev/null
@@ -0,0 +1,1750 @@
+/* SPDX-License-Identifier: GPL-2.0+ */
+#ifndef _LINUX_XARRAY_H
+#define _LINUX_XARRAY_H
+/*
+ * eXtensible Arrays
+ * Copyright (c) 2017 Microsoft Corporation
+ * Author: Matthew Wilcox <willy@infradead.org>
+ *
+ * See Documentation/core-api/xarray.rst for how to use the XArray.
+ */
+
+#include <linux/bug.h>
+#include <linux/compiler.h>
+#include <linux/gfp.h>
+#include <linux/kconfig.h>
+#include <linux/kernel.h>
+#include <linux/rcupdate.h>
+#include <linux/spinlock.h>
+#include <linux/types.h>
+
+/*
+ * The bottom two bits of the entry determine how the XArray interprets
+ * the contents:
+ *
+ * 00: Pointer entry
+ * 10: Internal entry
+ * x1: Value entry or tagged pointer
+ *
+ * Attempting to store internal entries in the XArray is a bug.
+ *
+ * Most internal entries are pointers to the next node in the tree.
+ * The following internal entries have a special meaning:
+ *
+ * 0-62: Sibling entries
+ * 256: Zero entry
+ * 257: Retry entry
+ *
+ * Errors are also represented as internal entries, but use the negative
+ * space (-4094 to -2).  They're never stored in the slots array; only
+ * returned by the normal API.
+ */
+
+#define BITS_PER_XA_VALUE      (BITS_PER_LONG - 1)
+
+/**
+ * xa_mk_value() - Create an XArray entry from an integer.
+ * @v: Value to store in XArray.
+ *
+ * Context: Any context.
+ * Return: An entry suitable for storing in the XArray.
+ */
+static inline void *xa_mk_value(unsigned long v)
+{
+       WARN_ON((long)v < 0);
+       return (void *)((v << 1) | 1);
+}
+
+/**
+ * xa_to_value() - Get value stored in an XArray entry.
+ * @entry: XArray entry.
+ *
+ * Context: Any context.
+ * Return: The value stored in the XArray entry.
+ */
+static inline unsigned long xa_to_value(const void *entry)
+{
+       return (unsigned long)entry >> 1;
+}
+
+/**
+ * xa_is_value() - Determine if an entry is a value.
+ * @entry: XArray entry.
+ *
+ * Context: Any context.
+ * Return: True if the entry is a value, false if it is a pointer.
+ */
+static inline bool xa_is_value(const void *entry)
+{
+       return (unsigned long)entry & 1;
+}
+
+/**
+ * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
+ * @p: Plain pointer.
+ * @tag: Tag value (0, 1 or 3).
+ *
+ * If the user of the XArray prefers, they can tag their pointers instead
+ * of storing value entries.  Three tags are available (0, 1 and 3).
+ * These are distinct from the xa_mark_t as they are not replicated up
+ * through the array and cannot be searched for.
+ *
+ * Context: Any context.
+ * Return: An XArray entry.
+ */
+static inline void *xa_tag_pointer(void *p, unsigned long tag)
+{
+       return (void *)((unsigned long)p | tag);
+}
+
+/**
+ * xa_untag_pointer() - Turn an XArray entry into a plain pointer.
+ * @entry: XArray entry.
+ *
+ * If you have stored a tagged pointer in the XArray, call this function
+ * to get the untagged version of the pointer.
+ *
+ * Context: Any context.
+ * Return: A pointer.
+ */
+static inline void *xa_untag_pointer(void *entry)
+{
+       return (void *)((unsigned long)entry & ~3UL);
+}
+
+/**
+ * xa_pointer_tag() - Get the tag stored in an XArray entry.
+ * @entry: XArray entry.
+ *
+ * If you have stored a tagged pointer in the XArray, call this function
+ * to get the tag of that pointer.
+ *
+ * Context: Any context.
+ * Return: A tag.
+ */
+static inline unsigned int xa_pointer_tag(void *entry)
+{
+       return (unsigned long)entry & 3UL;
+}
+
+/*
+ * xa_mk_internal() - Create an internal entry.
+ * @v: Value to turn into an internal entry.
+ *
+ * Internal entries are used for a number of purposes.  Entries 0-255 are
+ * used for sibling entries (only 0-62 are used by the current code).  256
+ * is used for the retry entry.  257 is used for the reserved / zero entry.
+ * Negative internal entries are used to represent errnos.  Node pointers
+ * are also tagged as internal entries in some situations.
+ *
+ * Context: Any context.
+ * Return: An XArray internal entry corresponding to this value.
+ */
+static inline void *xa_mk_internal(unsigned long v)
+{
+       return (void *)((v << 2) | 2);
+}
+
+/*
+ * xa_to_internal() - Extract the value from an internal entry.
+ * @entry: XArray entry.
+ *
+ * Context: Any context.
+ * Return: The value which was stored in the internal entry.
+ */
+static inline unsigned long xa_to_internal(const void *entry)
+{
+       return (unsigned long)entry >> 2;
+}
+
+/*
+ * xa_is_internal() - Is the entry an internal entry?
+ * @entry: XArray entry.
+ *
+ * Context: Any context.
+ * Return: %true if the entry is an internal entry.
+ */
+static inline bool xa_is_internal(const void *entry)
+{
+       return ((unsigned long)entry & 3) == 2;
+}
+
+#define XA_ZERO_ENTRY          xa_mk_internal(257)
+
+/**
+ * xa_is_zero() - Is the entry a zero entry?
+ * @entry: Entry retrieved from the XArray
+ *
+ * The normal API will return NULL as the contents of a slot containing
+ * a zero entry.  You can only see zero entries by using the advanced API.
+ *
+ * Return: %true if the entry is a zero entry.
+ */
+static inline bool xa_is_zero(const void *entry)
+{
+       return unlikely(entry == XA_ZERO_ENTRY);
+}
+
+/**
+ * xa_is_err() - Report whether an XArray operation returned an error
+ * @entry: Result from calling an XArray function
+ *
+ * If an XArray operation cannot complete an operation, it will return
+ * a special value indicating an error.  This function tells you
+ * whether an error occurred; xa_err() tells you which error occurred.
+ *
+ * Context: Any context.
+ * Return: %true if the entry indicates an error.
+ */
+static inline bool xa_is_err(const void *entry)
+{
+       return unlikely(xa_is_internal(entry) &&
+                       entry >= xa_mk_internal(-MAX_ERRNO));
+}
+
+/**
+ * xa_err() - Turn an XArray result into an errno.
+ * @entry: Result from calling an XArray function.
+ *
+ * If an XArray operation cannot complete an operation, it will return
+ * a special pointer value which encodes an errno.  This function extracts
+ * the errno from the pointer value, or returns 0 if the pointer does not
+ * represent an errno.
+ *
+ * Context: Any context.
+ * Return: A negative errno or 0.
+ */
+static inline int xa_err(void *entry)
+{
+       /* xa_to_internal() would not do sign extension. */
+       if (xa_is_err(entry))
+               return (long)entry >> 2;
+       return 0;
+}
+
+/**
+ * struct xa_limit - Represents a range of IDs.
+ * @min: The lowest ID to allocate (inclusive).
+ * @max: The maximum ID to allocate (inclusive).
+ *
+ * This structure is used either directly or via the XA_LIMIT() macro
+ * to communicate the range of IDs that are valid for allocation.
+ * Two common ranges are predefined for you:
+ *  * xa_limit_32b     - [0 - UINT_MAX]
+ *  * xa_limit_31b     - [0 - INT_MAX]
+ */
+struct xa_limit {
+       u32 max;
+       u32 min;
+};
+
+#define XA_LIMIT(_min, _max) (struct xa_limit) { .min = _min, .max = _max }
+
+#define xa_limit_32b   XA_LIMIT(0, UINT_MAX)
+#define xa_limit_31b   XA_LIMIT(0, INT_MAX)
+
+typedef unsigned __bitwise xa_mark_t;
+#define XA_MARK_0              ((__force xa_mark_t)0U)
+#define XA_MARK_1              ((__force xa_mark_t)1U)
+#define XA_MARK_2              ((__force xa_mark_t)2U)
+#define XA_PRESENT             ((__force xa_mark_t)8U)
+#define XA_MARK_MAX            XA_MARK_2
+#define XA_FREE_MARK           XA_MARK_0
+
+enum xa_lock_type {
+       XA_LOCK_IRQ = 1,
+       XA_LOCK_BH = 2,
+};
+
+/*
+ * Values for xa_flags.  The radix tree stores its GFP flags in the xa_flags,
+ * and we remain compatible with that.
+ */
+#define XA_FLAGS_LOCK_IRQ      ((__force gfp_t)XA_LOCK_IRQ)
+#define XA_FLAGS_LOCK_BH       ((__force gfp_t)XA_LOCK_BH)
+#define XA_FLAGS_TRACK_FREE    ((__force gfp_t)4U)
+#define XA_FLAGS_ZERO_BUSY     ((__force gfp_t)8U)
+#define XA_FLAGS_ALLOC_WRAPPED ((__force gfp_t)16U)
+#define XA_FLAGS_ACCOUNT       ((__force gfp_t)32U)
+#define XA_FLAGS_MARK(mark)    ((__force gfp_t)((1U << __GFP_BITS_SHIFT) << \
+                                               (__force unsigned)(mark)))
+
+/* ALLOC is for a normal 0-based alloc.  ALLOC1 is for an 1-based alloc */
+#define XA_FLAGS_ALLOC (XA_FLAGS_TRACK_FREE | XA_FLAGS_MARK(XA_FREE_MARK))
+#define XA_FLAGS_ALLOC1        (XA_FLAGS_TRACK_FREE | XA_FLAGS_ZERO_BUSY)
+
+/**
+ * struct xarray - The anchor of the XArray.
+ * @xa_lock: Lock that protects the contents of the XArray.
+ *
+ * To use the xarray, define it statically or embed it in your data structure.
+ * It is a very small data structure, so it does not usually make sense to
+ * allocate it separately and keep a pointer to it in your data structure.
+ *
+ * You may use the xa_lock to protect your own data structures as well.
+ */
+/*
+ * If all of the entries in the array are NULL, @xa_head is a NULL pointer.
+ * If the only non-NULL entry in the array is at index 0, @xa_head is that
+ * entry.  If any other entry in the array is non-NULL, @xa_head points
+ * to an @xa_node.
+ */
+struct xarray {
+       spinlock_t      xa_lock;
+/* private: The rest of the data structure is not to be used directly. */
+       gfp_t           xa_flags;
+       void __rcu *    xa_head;
+};
+
+#define XARRAY_INIT(name, flags) {                             \
+       .xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock),          \
+       .xa_flags = flags,                                      \
+       .xa_head = NULL,                                        \
+}
+
+/**
+ * DEFINE_XARRAY_FLAGS() - Define an XArray with custom flags.
+ * @name: A string that names your XArray.
+ * @flags: XA_FLAG values.
+ *
+ * This is intended for file scope definitions of XArrays.  It declares
+ * and initialises an empty XArray with the chosen name and flags.  It is
+ * equivalent to calling xa_init_flags() on the array, but it does the
+ * initialisation at compiletime instead of runtime.
+ */
+#define DEFINE_XARRAY_FLAGS(name, flags)                               \
+       struct xarray name = XARRAY_INIT(name, flags)
+
+/**
+ * DEFINE_XARRAY() - Define an XArray.
+ * @name: A string that names your XArray.
+ *
+ * This is intended for file scope definitions of XArrays.  It declares
+ * and initialises an empty XArray with the chosen name.  It is equivalent
+ * to calling xa_init() on the array, but it does the initialisation at
+ * compiletime instead of runtime.
+ */
+#define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0)
+
+/**
+ * DEFINE_XARRAY_ALLOC() - Define an XArray which allocates IDs starting at 0.
+ * @name: A string that names your XArray.
+ *
+ * This is intended for file scope definitions of allocating XArrays.
+ * See also DEFINE_XARRAY().
+ */
+#define DEFINE_XARRAY_ALLOC(name) DEFINE_XARRAY_FLAGS(name, XA_FLAGS_ALLOC)
+
+/**
+ * DEFINE_XARRAY_ALLOC1() - Define an XArray which allocates IDs starting at 1.
+ * @name: A string that names your XArray.
+ *
+ * This is intended for file scope definitions of allocating XArrays.
+ * See also DEFINE_XARRAY().
+ */
+#define DEFINE_XARRAY_ALLOC1(name) DEFINE_XARRAY_FLAGS(name, XA_FLAGS_ALLOC1)
+
+void *xa_load(struct xarray *, unsigned long index);
+void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
+void *xa_erase(struct xarray *, unsigned long index);
+void *xa_store_range(struct xarray *, unsigned long first, unsigned long last,
+                       void *entry, gfp_t);
+bool xa_get_mark(struct xarray *, unsigned long index, xa_mark_t);
+void xa_set_mark(struct xarray *, unsigned long index, xa_mark_t);
+void xa_clear_mark(struct xarray *, unsigned long index, xa_mark_t);
+void *xa_find(struct xarray *xa, unsigned long *index,
+               unsigned long max, xa_mark_t) __attribute__((nonnull(2)));
+void *xa_find_after(struct xarray *xa, unsigned long *index,
+               unsigned long max, xa_mark_t) __attribute__((nonnull(2)));
+unsigned int xa_extract(struct xarray *, void **dst, unsigned long start,
+               unsigned long max, unsigned int n, xa_mark_t);
+void xa_destroy(struct xarray *);
+
+/**
+ * xa_init_flags() - Initialise an empty XArray with flags.
+ * @xa: XArray.
+ * @flags: XA_FLAG values.
+ *
+ * If you need to initialise an XArray with special flags (eg you need
+ * to take the lock from interrupt context), use this function instead
+ * of xa_init().
+ *
+ * Context: Any context.
+ */
+static inline void xa_init_flags(struct xarray *xa, gfp_t flags)
+{
+       spin_lock_init(&xa->xa_lock);
+       xa->xa_flags = flags;
+       xa->xa_head = NULL;
+}
+
+/**
+ * xa_init() - Initialise an empty XArray.
+ * @xa: XArray.
+ *
+ * An empty XArray is full of NULL entries.
+ *
+ * Context: Any context.
+ */
+static inline void xa_init(struct xarray *xa)
+{
+       xa_init_flags(xa, 0);
+}
+
+/**
+ * xa_empty() - Determine if an array has any present entries.
+ * @xa: XArray.
+ *
+ * Context: Any context.
+ * Return: %true if the array contains only NULL pointers.
+ */
+static inline bool xa_empty(const struct xarray *xa)
+{
+       return xa->xa_head == NULL;
+}
+
+/**
+ * xa_marked() - Inquire whether any entry in this array has a mark set
+ * @xa: Array
+ * @mark: Mark value
+ *
+ * Context: Any context.
+ * Return: %true if any entry has this mark set.
+ */
+static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)
+{
+       return xa->xa_flags & XA_FLAGS_MARK(mark);
+}
+
+/**
+ * xa_for_each_start() - Iterate over a portion of an XArray.
+ * @xa: XArray.
+ * @index: Index of @entry.
+ * @entry: Entry retrieved from array.
+ * @start: First index to retrieve from array.
+ *
+ * During the iteration, @entry will have the value of the entry stored
+ * in @xa at @index.  You may modify @index during the iteration if you
+ * want to skip or reprocess indices.  It is safe to modify the array
+ * during the iteration.  At the end of the iteration, @entry will be set
+ * to NULL and @index will have a value less than or equal to max.
+ *
+ * xa_for_each_start() is O(n.log(n)) while xas_for_each() is O(n).  You have
+ * to handle your own locking with xas_for_each(), and if you have to unlock
+ * after each iteration, it will also end up being O(n.log(n)).
+ * xa_for_each_start() will spin if it hits a retry entry; if you intend to
+ * see retry entries, you should use the xas_for_each() iterator instead.
+ * The xas_for_each() iterator will expand into more inline code than
+ * xa_for_each_start().
+ *
+ * Context: Any context.  Takes and releases the RCU lock.
+ */
+#define xa_for_each_start(xa, index, entry, start)                     \
+       for (index = start,                                             \
+            entry = xa_find(xa, &index, ULONG_MAX, XA_PRESENT);        \
+            entry;                                                     \
+            entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT))
+
+/**
+ * xa_for_each() - Iterate over present entries in an XArray.
+ * @xa: XArray.
+ * @index: Index of @entry.
+ * @entry: Entry retrieved from array.
+ *
+ * During the iteration, @entry will have the value of the entry stored
+ * in @xa at @index.  You may modify @index during the iteration if you want
+ * to skip or reprocess indices.  It is safe to modify the array during the
+ * iteration.  At the end of the iteration, @entry will be set to NULL and
+ * @index will have a value less than or equal to max.
+ *
+ * xa_for_each() is O(n.log(n)) while xas_for_each() is O(n).  You have
+ * to handle your own locking with xas_for_each(), and if you have to unlock
+ * after each iteration, it will also end up being O(n.log(n)).  xa_for_each()
+ * will spin if it hits a retry entry; if you intend to see retry entries,
+ * you should use the xas_for_each() iterator instead.  The xas_for_each()
+ * iterator will expand into more inline code than xa_for_each().
+ *
+ * Context: Any context.  Takes and releases the RCU lock.
+ */
+#define xa_for_each(xa, index, entry) \
+       xa_for_each_start(xa, index, entry, 0)
+
+/**
+ * xa_for_each_marked() - Iterate over marked entries in an XArray.
+ * @xa: XArray.
+ * @index: Index of @entry.
+ * @entry: Entry retrieved from array.
+ * @filter: Selection criterion.
+ *
+ * During the iteration, @entry will have the value of the entry stored
+ * in @xa at @index.  The iteration will skip all entries in the array
+ * which do not match @filter.  You may modify @index during the iteration
+ * if you want to skip or reprocess indices.  It is safe to modify the array
+ * during the iteration.  At the end of the iteration, @entry will be set to
+ * NULL and @index will have a value less than or equal to max.
+ *
+ * xa_for_each_marked() is O(n.log(n)) while xas_for_each_marked() is O(n).
+ * You have to handle your own locking with xas_for_each(), and if you have
+ * to unlock after each iteration, it will also end up being O(n.log(n)).
+ * xa_for_each_marked() will spin if it hits a retry entry; if you intend to
+ * see retry entries, you should use the xas_for_each_marked() iterator
+ * instead.  The xas_for_each_marked() iterator will expand into more inline
+ * code than xa_for_each_marked().
+ *
+ * Context: Any context.  Takes and releases the RCU lock.
+ */
+#define xa_for_each_marked(xa, index, entry, filter) \
+       for (index = 0, entry = xa_find(xa, &index, ULONG_MAX, filter); \
+            entry; entry = xa_find_after(xa, &index, ULONG_MAX, filter))
+
+#define xa_trylock(xa)         spin_trylock(&(xa)->xa_lock)
+#define xa_lock(xa)            spin_lock(&(xa)->xa_lock)
+#define xa_unlock(xa)          spin_unlock(&(xa)->xa_lock)
+#define xa_lock_bh(xa)         spin_lock_bh(&(xa)->xa_lock)
+#define xa_unlock_bh(xa)       spin_unlock_bh(&(xa)->xa_lock)
+#define xa_lock_irq(xa)                spin_lock_irq(&(xa)->xa_lock)
+#define xa_unlock_irq(xa)      spin_unlock_irq(&(xa)->xa_lock)
+#define xa_lock_irqsave(xa, flags) \
+                               spin_lock_irqsave(&(xa)->xa_lock, flags)
+#define xa_unlock_irqrestore(xa, flags) \
+                               spin_unlock_irqrestore(&(xa)->xa_lock, flags)
+
+/*
+ * Versions of the normal API which require the caller to hold the
+ * xa_lock.  If the GFP flags allow it, they will drop the lock to
+ * allocate memory, then reacquire it afterwards.  These functions
+ * may also re-enable interrupts if the XArray flags indicate the
+ * locking should be interrupt safe.
+ */
+void *__xa_erase(struct xarray *, unsigned long index);
+void *__xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
+void *__xa_cmpxchg(struct xarray *, unsigned long index, void *old,
+               void *entry, gfp_t);
+int __must_check __xa_insert(struct xarray *, unsigned long index,
+               void *entry, gfp_t);
+int __must_check __xa_alloc(struct xarray *, u32 *id, void *entry,
+               struct xa_limit, gfp_t);
+int __must_check __xa_alloc_cyclic(struct xarray *, u32 *id, void *entry,
+               struct xa_limit, u32 *next, gfp_t);
+void __xa_set_mark(struct xarray *, unsigned long index, xa_mark_t);
+void __xa_clear_mark(struct xarray *, unsigned long index, xa_mark_t);
+
+/**
+ * xa_store_bh() - Store this entry in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @entry: New entry.
+ * @gfp: Memory allocation flags.
+ *
+ * This function is like calling xa_store() except it disables softirqs
+ * while holding the array lock.
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.
+ * Return: The entry which used to be at this index.
+ */
+static inline void *xa_store_bh(struct xarray *xa, unsigned long index,
+               void *entry, gfp_t gfp)
+{
+       void *curr;
+
+       xa_lock_bh(xa);
+       curr = __xa_store(xa, index, entry, gfp);
+       xa_unlock_bh(xa);
+
+       return curr;
+}
+
+/**
+ * xa_store_irq() - Store this entry in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @entry: New entry.
+ * @gfp: Memory allocation flags.
+ *
+ * This function is like calling xa_store() except it disables interrupts
+ * while holding the array lock.
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.
+ * Return: The entry which used to be at this index.
+ */
+static inline void *xa_store_irq(struct xarray *xa, unsigned long index,
+               void *entry, gfp_t gfp)
+{
+       void *curr;
+
+       xa_lock_irq(xa);
+       curr = __xa_store(xa, index, entry, gfp);
+       xa_unlock_irq(xa);
+
+       return curr;
+}
+
+/**
+ * xa_erase_bh() - Erase this entry from the XArray.
+ * @xa: XArray.
+ * @index: Index of entry.
+ *
+ * After this function returns, loading from @index will return %NULL.
+ * If the index is part of a multi-index entry, all indices will be erased
+ * and none of the entries will be part of a multi-index entry.
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.
+ * Return: The entry which used to be at this index.
+ */
+static inline void *xa_erase_bh(struct xarray *xa, unsigned long index)
+{
+       void *entry;
+
+       xa_lock_bh(xa);
+       entry = __xa_erase(xa, index);
+       xa_unlock_bh(xa);
+
+       return entry;
+}
+
+/**
+ * xa_erase_irq() - Erase this entry from the XArray.
+ * @xa: XArray.
+ * @index: Index of entry.
+ *
+ * After this function returns, loading from @index will return %NULL.
+ * If the index is part of a multi-index entry, all indices will be erased
+ * and none of the entries will be part of a multi-index entry.
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.
+ * Return: The entry which used to be at this index.
+ */
+static inline void *xa_erase_irq(struct xarray *xa, unsigned long index)
+{
+       void *entry;
+
+       xa_lock_irq(xa);
+       entry = __xa_erase(xa, index);
+       xa_unlock_irq(xa);
+
+       return entry;
+}
+
+/**
+ * xa_cmpxchg() - Conditionally replace an entry in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @old: Old value to test against.
+ * @entry: New value to place in array.
+ * @gfp: Memory allocation flags.
+ *
+ * If the entry at @index is the same as @old, replace it with @entry.
+ * If the return value is equal to @old, then the exchange was successful.
+ *
+ * Context: Any context.  Takes and releases the xa_lock.  May sleep
+ * if the @gfp flags permit.
+ * Return: The old value at this index or xa_err() if an error happened.
+ */
+static inline void *xa_cmpxchg(struct xarray *xa, unsigned long index,
+                       void *old, void *entry, gfp_t gfp)
+{
+       void *curr;
+
+       xa_lock(xa);
+       curr = __xa_cmpxchg(xa, index, old, entry, gfp);
+       xa_unlock(xa);
+
+       return curr;
+}
+
+/**
+ * xa_cmpxchg_bh() - Conditionally replace an entry in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @old: Old value to test against.
+ * @entry: New value to place in array.
+ * @gfp: Memory allocation flags.
+ *
+ * This function is like calling xa_cmpxchg() except it disables softirqs
+ * while holding the array lock.
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.  May sleep if the @gfp flags permit.
+ * Return: The old value at this index or xa_err() if an error happened.
+ */
+static inline void *xa_cmpxchg_bh(struct xarray *xa, unsigned long index,
+                       void *old, void *entry, gfp_t gfp)
+{
+       void *curr;
+
+       xa_lock_bh(xa);
+       curr = __xa_cmpxchg(xa, index, old, entry, gfp);
+       xa_unlock_bh(xa);
+
+       return curr;
+}
+
+/**
+ * xa_cmpxchg_irq() - Conditionally replace an entry in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @old: Old value to test against.
+ * @entry: New value to place in array.
+ * @gfp: Memory allocation flags.
+ *
+ * This function is like calling xa_cmpxchg() except it disables interrupts
+ * while holding the array lock.
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.  May sleep if the @gfp flags permit.
+ * Return: The old value at this index or xa_err() if an error happened.
+ */
+static inline void *xa_cmpxchg_irq(struct xarray *xa, unsigned long index,
+                       void *old, void *entry, gfp_t gfp)
+{
+       void *curr;
+
+       xa_lock_irq(xa);
+       curr = __xa_cmpxchg(xa, index, old, entry, gfp);
+       xa_unlock_irq(xa);
+
+       return curr;
+}
+
+/**
+ * xa_insert() - Store this entry in the XArray unless another entry is
+ *                     already present.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @entry: New entry.
+ * @gfp: Memory allocation flags.
+ *
+ * Inserting a NULL entry will store a reserved entry (like xa_reserve())
+ * if no entry is present.  Inserting will fail if a reserved entry is
+ * present, even though loading from this index will return NULL.
+ *
+ * Context: Any context.  Takes and releases the xa_lock.  May sleep if
+ * the @gfp flags permit.
+ * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
+ * -ENOMEM if memory could not be allocated.
+ */
+static inline int __must_check xa_insert(struct xarray *xa,
+               unsigned long index, void *entry, gfp_t gfp)
+{
+       int err;
+
+       xa_lock(xa);
+       err = __xa_insert(xa, index, entry, gfp);
+       xa_unlock(xa);
+
+       return err;
+}
+
+/**
+ * xa_insert_bh() - Store this entry in the XArray unless another entry is
+ *                     already present.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @entry: New entry.
+ * @gfp: Memory allocation flags.
+ *
+ * Inserting a NULL entry will store a reserved entry (like xa_reserve())
+ * if no entry is present.  Inserting will fail if a reserved entry is
+ * present, even though loading from this index will return NULL.
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.  May sleep if the @gfp flags permit.
+ * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
+ * -ENOMEM if memory could not be allocated.
+ */
+static inline int __must_check xa_insert_bh(struct xarray *xa,
+               unsigned long index, void *entry, gfp_t gfp)
+{
+       int err;
+
+       xa_lock_bh(xa);
+       err = __xa_insert(xa, index, entry, gfp);
+       xa_unlock_bh(xa);
+
+       return err;
+}
+
+/**
+ * xa_insert_irq() - Store this entry in the XArray unless another entry is
+ *                     already present.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @entry: New entry.
+ * @gfp: Memory allocation flags.
+ *
+ * Inserting a NULL entry will store a reserved entry (like xa_reserve())
+ * if no entry is present.  Inserting will fail if a reserved entry is
+ * present, even though loading from this index will return NULL.
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.  May sleep if the @gfp flags permit.
+ * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
+ * -ENOMEM if memory could not be allocated.
+ */
+static inline int __must_check xa_insert_irq(struct xarray *xa,
+               unsigned long index, void *entry, gfp_t gfp)
+{
+       int err;
+
+       xa_lock_irq(xa);
+       err = __xa_insert(xa, index, entry, gfp);
+       xa_unlock_irq(xa);
+
+       return err;
+}
+
+/**
+ * xa_alloc() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @id: Pointer to ID.
+ * @entry: New entry.
+ * @limit: Range of ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Finds an empty entry in @xa between @limit.min and @limit.max,
+ * stores the index into the @id pointer, then stores the entry at
+ * that index.  A concurrent lookup will not see an uninitialised @id.
+ *
+ * Context: Any context.  Takes and releases the xa_lock.  May sleep if
+ * the @gfp flags permit.
+ * Return: 0 on success, -ENOMEM if memory could not be allocated or
+ * -EBUSY if there are no free entries in @limit.
+ */
+static inline __must_check int xa_alloc(struct xarray *xa, u32 *id,
+               void *entry, struct xa_limit limit, gfp_t gfp)
+{
+       int err;
+
+       xa_lock(xa);
+       err = __xa_alloc(xa, id, entry, limit, gfp);
+       xa_unlock(xa);
+
+       return err;
+}
+
+/**
+ * xa_alloc_bh() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @id: Pointer to ID.
+ * @entry: New entry.
+ * @limit: Range of ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Finds an empty entry in @xa between @limit.min and @limit.max,
+ * stores the index into the @id pointer, then stores the entry at
+ * that index.  A concurrent lookup will not see an uninitialised @id.
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.  May sleep if the @gfp flags permit.
+ * Return: 0 on success, -ENOMEM if memory could not be allocated or
+ * -EBUSY if there are no free entries in @limit.
+ */
+static inline int __must_check xa_alloc_bh(struct xarray *xa, u32 *id,
+               void *entry, struct xa_limit limit, gfp_t gfp)
+{
+       int err;
+
+       xa_lock_bh(xa);
+       err = __xa_alloc(xa, id, entry, limit, gfp);
+       xa_unlock_bh(xa);
+
+       return err;
+}
+
+/**
+ * xa_alloc_irq() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @id: Pointer to ID.
+ * @entry: New entry.
+ * @limit: Range of ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Finds an empty entry in @xa between @limit.min and @limit.max,
+ * stores the index into the @id pointer, then stores the entry at
+ * that index.  A concurrent lookup will not see an uninitialised @id.
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.  May sleep if the @gfp flags permit.
+ * Return: 0 on success, -ENOMEM if memory could not be allocated or
+ * -EBUSY if there are no free entries in @limit.
+ */
+static inline int __must_check xa_alloc_irq(struct xarray *xa, u32 *id,
+               void *entry, struct xa_limit limit, gfp_t gfp)
+{
+       int err;
+
+       xa_lock_irq(xa);
+       err = __xa_alloc(xa, id, entry, limit, gfp);
+       xa_unlock_irq(xa);
+
+       return err;
+}
+
+/**
+ * xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @id: Pointer to ID.
+ * @entry: New entry.
+ * @limit: Range of allocated ID.
+ * @next: Pointer to next ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Finds an empty entry in @xa between @limit.min and @limit.max,
+ * stores the index into the @id pointer, then stores the entry at
+ * that index.  A concurrent lookup will not see an uninitialised @id.
+ * The search for an empty entry will start at @next and will wrap
+ * around if necessary.
+ *
+ * Context: Any context.  Takes and releases the xa_lock.  May sleep if
+ * the @gfp flags permit.
+ * Return: 0 if the allocation succeeded without wrapping.  1 if the
+ * allocation succeeded after wrapping, -ENOMEM if memory could not be
+ * allocated or -EBUSY if there are no free entries in @limit.
+ */
+static inline int xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,
+               struct xa_limit limit, u32 *next, gfp_t gfp)
+{
+       int err;
+
+       xa_lock(xa);
+       err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);
+       xa_unlock(xa);
+
+       return err;
+}
+
+/**
+ * xa_alloc_cyclic_bh() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @id: Pointer to ID.
+ * @entry: New entry.
+ * @limit: Range of allocated ID.
+ * @next: Pointer to next ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Finds an empty entry in @xa between @limit.min and @limit.max,
+ * stores the index into the @id pointer, then stores the entry at
+ * that index.  A concurrent lookup will not see an uninitialised @id.
+ * The search for an empty entry will start at @next and will wrap
+ * around if necessary.
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.  May sleep if the @gfp flags permit.
+ * Return: 0 if the allocation succeeded without wrapping.  1 if the
+ * allocation succeeded after wrapping, -ENOMEM if memory could not be
+ * allocated or -EBUSY if there are no free entries in @limit.
+ */
+static inline int xa_alloc_cyclic_bh(struct xarray *xa, u32 *id, void *entry,
+               struct xa_limit limit, u32 *next, gfp_t gfp)
+{
+       int err;
+
+       xa_lock_bh(xa);
+       err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);
+       xa_unlock_bh(xa);
+
+       return err;
+}
+
+/**
+ * xa_alloc_cyclic_irq() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @id: Pointer to ID.
+ * @entry: New entry.
+ * @limit: Range of allocated ID.
+ * @next: Pointer to next ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Finds an empty entry in @xa between @limit.min and @limit.max,
+ * stores the index into the @id pointer, then stores the entry at
+ * that index.  A concurrent lookup will not see an uninitialised @id.
+ * The search for an empty entry will start at @next and will wrap
+ * around if necessary.
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.  May sleep if the @gfp flags permit.
+ * Return: 0 if the allocation succeeded without wrapping.  1 if the
+ * allocation succeeded after wrapping, -ENOMEM if memory could not be
+ * allocated or -EBUSY if there are no free entries in @limit.
+ */
+static inline int xa_alloc_cyclic_irq(struct xarray *xa, u32 *id, void *entry,
+               struct xa_limit limit, u32 *next, gfp_t gfp)
+{
+       int err;
+
+       xa_lock_irq(xa);
+       err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);
+       xa_unlock_irq(xa);
+
+       return err;
+}
+
+/**
+ * xa_reserve() - Reserve this index in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @gfp: Memory allocation flags.
+ *
+ * Ensures there is somewhere to store an entry at @index in the array.
+ * If there is already something stored at @index, this function does
+ * nothing.  If there was nothing there, the entry is marked as reserved.
+ * Loading from a reserved entry returns a %NULL pointer.
+ *
+ * If you do not use the entry that you have reserved, call xa_release()
+ * or xa_erase() to free any unnecessary memory.
+ *
+ * Context: Any context.  Takes and releases the xa_lock.
+ * May sleep if the @gfp flags permit.
+ * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
+ */
+static inline __must_check
+int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp)
+{
+       return xa_err(xa_cmpxchg(xa, index, NULL, XA_ZERO_ENTRY, gfp));
+}
+
+/**
+ * xa_reserve_bh() - Reserve this index in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @gfp: Memory allocation flags.
+ *
+ * A softirq-disabling version of xa_reserve().
+ *
+ * Context: Any context.  Takes and releases the xa_lock while
+ * disabling softirqs.
+ * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
+ */
+static inline __must_check
+int xa_reserve_bh(struct xarray *xa, unsigned long index, gfp_t gfp)
+{
+       return xa_err(xa_cmpxchg_bh(xa, index, NULL, XA_ZERO_ENTRY, gfp));
+}
+
+/**
+ * xa_reserve_irq() - Reserve this index in the XArray.
+ * @xa: XArray.
+ * @index: Index into array.
+ * @gfp: Memory allocation flags.
+ *
+ * An interrupt-disabling version of xa_reserve().
+ *
+ * Context: Process context.  Takes and releases the xa_lock while
+ * disabling interrupts.
+ * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
+ */
+static inline __must_check
+int xa_reserve_irq(struct xarray *xa, unsigned long index, gfp_t gfp)
+{
+       return xa_err(xa_cmpxchg_irq(xa, index, NULL, XA_ZERO_ENTRY, gfp));
+}
+
+/**
+ * xa_release() - Release a reserved entry.
+ * @xa: XArray.
+ * @index: Index of entry.
+ *
+ * After calling xa_reserve(), you can call this function to release the
+ * reservation.  If the entry at @index has been stored to, this function
+ * will do nothing.
+ */
+static inline void xa_release(struct xarray *xa, unsigned long index)
+{
+       xa_cmpxchg(xa, index, XA_ZERO_ENTRY, NULL, 0);
+}
+
+/* Everything below here is the Advanced API.  Proceed with caution. */
+
+/*
+ * The xarray is constructed out of a set of 'chunks' of pointers.  Choosing
+ * the best chunk size requires some tradeoffs.  A power of two recommends
+ * itself so that we can walk the tree based purely on shifts and masks.
+ * Generally, the larger the better; as the number of slots per level of the
+ * tree increases, the less tall the tree needs to be.  But that needs to be
+ * balanced against the memory consumption of each node.  On a 64-bit system,
+ * xa_node is currently 576 bytes, and we get 7 of them per 4kB page.  If we
+ * doubled the number of slots per node, we'd get only 3 nodes per 4kB page.
+ */
+#ifndef XA_CHUNK_SHIFT
+#define XA_CHUNK_SHIFT         (CONFIG_BASE_SMALL ? 4 : 6)
+#endif
+#define XA_CHUNK_SIZE          (1UL << XA_CHUNK_SHIFT)
+#define XA_CHUNK_MASK          (XA_CHUNK_SIZE - 1)
+#define XA_MAX_MARKS           3
+#define XA_MARK_LONGS          DIV_ROUND_UP(XA_CHUNK_SIZE, BITS_PER_LONG)
+
+/*
+ * @count is the count of every non-NULL element in the ->slots array
+ * whether that is a value entry, a retry entry, a user pointer,
+ * a sibling entry or a pointer to the next level of the tree.
+ * @nr_values is the count of every element in ->slots which is
+ * either a value entry or a sibling of a value entry.
+ */
+struct xa_node {
+       unsigned char   shift;          /* Bits remaining in each slot */
+       unsigned char   offset;         /* Slot offset in parent */
+       unsigned char   count;          /* Total entry count */
+       unsigned char   nr_values;      /* Value entry count */
+       struct xa_node __rcu *parent;   /* NULL at top of tree */
+       struct xarray   *array;         /* The array we belong to */
+       union {
+               struct list_head private_list;  /* For tree user */
+               struct rcu_head rcu_head;       /* Used when freeing node */
+       };
+       void __rcu      *slots[XA_CHUNK_SIZE];
+       union {
+               unsigned long   tags[XA_MAX_MARKS][XA_MARK_LONGS];
+               unsigned long   marks[XA_MAX_MARKS][XA_MARK_LONGS];
+       };
+};
+
+void xa_dump(const struct xarray *);
+void xa_dump_node(const struct xa_node *);
+
+#ifdef XA_DEBUG
+#define XA_BUG_ON(xa, x) do {                                  \
+               if (x) {                                        \
+                       xa_dump(xa);                            \
+                       BUG();                                  \
+               }                                               \
+       } while (0)
+#define XA_NODE_BUG_ON(node, x) do {                           \
+               if (x) {                                        \
+                       if (node) xa_dump_node(node);           \
+                       BUG();                                  \
+               }                                               \
+       } while (0)
+#else
+#define XA_BUG_ON(xa, x)       do { } while (0)
+#define XA_NODE_BUG_ON(node, x)        do { } while (0)
+#endif
+
+/* Private */
+static inline void *xa_head(const struct xarray *xa)
+{
+       return rcu_dereference_check(xa->xa_head,
+                                               lockdep_is_held(&xa->xa_lock));
+}
+
+/* Private */
+static inline void *xa_head_locked(const struct xarray *xa)
+{
+       return rcu_dereference_protected(xa->xa_head,
+                                               lockdep_is_held(&xa->xa_lock));
+}
+
+/* Private */
+static inline void *xa_entry(const struct xarray *xa,
+                               const struct xa_node *node, unsigned int offset)
+{
+       XA_NODE_BUG_ON(node, offset >= XA_CHUNK_SIZE);
+       return rcu_dereference_check(node->slots[offset],
+                                               lockdep_is_held(&xa->xa_lock));
+}
+
+/* Private */
+static inline void *xa_entry_locked(const struct xarray *xa,
+                               const struct xa_node *node, unsigned int offset)
+{
+       XA_NODE_BUG_ON(node, offset >= XA_CHUNK_SIZE);
+       return rcu_dereference_protected(node->slots[offset],
+                                               lockdep_is_held(&xa->xa_lock));
+}
+
+/* Private */
+static inline struct xa_node *xa_parent(const struct xarray *xa,
+                                       const struct xa_node *node)
+{
+       return rcu_dereference_check(node->parent,
+                                               lockdep_is_held(&xa->xa_lock));
+}
+
+/* Private */
+static inline struct xa_node *xa_parent_locked(const struct xarray *xa,
+                                       const struct xa_node *node)
+{
+       return rcu_dereference_protected(node->parent,
+                                               lockdep_is_held(&xa->xa_lock));
+}
+
+/* Private */
+static inline void *xa_mk_node(const struct xa_node *node)
+{
+       return (void *)((unsigned long)node | 2);
+}
+
+/* Private */
+static inline struct xa_node *xa_to_node(const void *entry)
+{
+       return (struct xa_node *)((unsigned long)entry - 2);
+}
+
+/* Private */
+static inline bool xa_is_node(const void *entry)
+{
+       return xa_is_internal(entry) && (unsigned long)entry > 4096;
+}
+
+/* Private */
+static inline void *xa_mk_sibling(unsigned int offset)
+{
+       return xa_mk_internal(offset);
+}
+
+/* Private */
+static inline unsigned long xa_to_sibling(const void *entry)
+{
+       return xa_to_internal(entry);
+}
+
+/**
+ * xa_is_sibling() - Is the entry a sibling entry?
+ * @entry: Entry retrieved from the XArray
+ *
+ * Return: %true if the entry is a sibling entry.
+ */
+static inline bool xa_is_sibling(const void *entry)
+{
+       return IS_ENABLED(CONFIG_XARRAY_MULTI) && xa_is_internal(entry) &&
+               (entry < xa_mk_sibling(XA_CHUNK_SIZE - 1));
+}
+
+#define XA_RETRY_ENTRY         xa_mk_internal(256)
+
+/**
+ * xa_is_retry() - Is the entry a retry entry?
+ * @entry: Entry retrieved from the XArray
+ *
+ * Return: %true if the entry is a retry entry.
+ */
+static inline bool xa_is_retry(const void *entry)
+{
+       return unlikely(entry == XA_RETRY_ENTRY);
+}
+
+/**
+ * xa_is_advanced() - Is the entry only permitted for the advanced API?
+ * @entry: Entry to be stored in the XArray.
+ *
+ * Return: %true if the entry cannot be stored by the normal API.
+ */
+static inline bool xa_is_advanced(const void *entry)
+{
+       return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY);
+}
+
+/**
+ * typedef xa_update_node_t - A callback function from the XArray.
+ * @node: The node which is being processed
+ *
+ * This function is called every time the XArray updates the count of
+ * present and value entries in a node.  It allows advanced users to
+ * maintain the private_list in the node.
+ *
+ * Context: The xa_lock is held and interrupts may be disabled.
+ *         Implementations should not drop the xa_lock, nor re-enable
+ *         interrupts.
+ */
+typedef void (*xa_update_node_t)(struct xa_node *node);
+
+/*
+ * The xa_state is opaque to its users.  It contains various different pieces
+ * of state involved in the current operation on the XArray.  It should be
+ * declared on the stack and passed between the various internal routines.
+ * The various elements in it should not be accessed directly, but only
+ * through the provided accessor functions.  The below documentation is for
+ * the benefit of those working on the code, not for users of the XArray.
+ *
+ * @xa_node usually points to the xa_node containing the slot we're operating
+ * on (and @xa_offset is the offset in the slots array).  If there is a
+ * single entry in the array at index 0, there are no allocated xa_nodes to
+ * point to, and so we store %NULL in @xa_node.  @xa_node is set to
+ * the value %XAS_RESTART if the xa_state is not walked to the correct
+ * position in the tree of nodes for this operation.  If an error occurs
+ * during an operation, it is set to an %XAS_ERROR value.  If we run off the
+ * end of the allocated nodes, it is set to %XAS_BOUNDS.
+ */
+struct xa_state {
+       struct xarray *xa;
+       unsigned long xa_index;
+       unsigned char xa_shift;
+       unsigned char xa_sibs;
+       unsigned char xa_offset;
+       unsigned char xa_pad;           /* Helps gcc generate better code */
+       struct xa_node *xa_node;
+       struct xa_node *xa_alloc;
+       xa_update_node_t xa_update;
+};
+
+/*
+ * We encode errnos in the xas->xa_node.  If an error has happened, we need to
+ * drop the lock to fix it, and once we've done so the xa_state is invalid.
+ */
+#define XA_ERROR(errno) ((struct xa_node *)(((unsigned long)errno << 2) | 2UL))
+#define XAS_BOUNDS     ((struct xa_node *)1UL)
+#define XAS_RESTART    ((struct xa_node *)3UL)
+
+#define __XA_STATE(array, index, shift, sibs)  {       \
+       .xa = array,                                    \
+       .xa_index = index,                              \
+       .xa_shift = shift,                              \
+       .xa_sibs = sibs,                                \
+       .xa_offset = 0,                                 \
+       .xa_pad = 0,                                    \
+       .xa_node = XAS_RESTART,                         \
+       .xa_alloc = NULL,                               \
+       .xa_update = NULL                               \
+}
+
+/**
+ * XA_STATE() - Declare an XArray operation state.
+ * @name: Name of this operation state (usually xas).
+ * @array: Array to operate on.
+ * @index: Initial index of interest.
+ *
+ * Declare and initialise an xa_state on the stack.
+ */
+#define XA_STATE(name, array, index)                           \
+       struct xa_state name = __XA_STATE(array, index, 0, 0)
+
+/**
+ * XA_STATE_ORDER() - Declare an XArray operation state.
+ * @name: Name of this operation state (usually xas).
+ * @array: Array to operate on.
+ * @index: Initial index of interest.
+ * @order: Order of entry.
+ *
+ * Declare and initialise an xa_state on the stack.  This variant of
+ * XA_STATE() allows you to specify the 'order' of the element you
+ * want to operate on.`
+ */
+#define XA_STATE_ORDER(name, array, index, order)              \
+       struct xa_state name = __XA_STATE(array,                \
+                       (index >> order) << order,              \
+                       order - (order % XA_CHUNK_SHIFT),       \
+                       (1U << (order % XA_CHUNK_SHIFT)) - 1)
+
+#define xas_marked(xas, mark)  xa_marked((xas)->xa, (mark))
+#define xas_trylock(xas)       xa_trylock((xas)->xa)
+#define xas_lock(xas)          xa_lock((xas)->xa)
+#define xas_unlock(xas)                xa_unlock((xas)->xa)
+#define xas_lock_bh(xas)       xa_lock_bh((xas)->xa)
+#define xas_unlock_bh(xas)     xa_unlock_bh((xas)->xa)
+#define xas_lock_irq(xas)      xa_lock_irq((xas)->xa)
+#define xas_unlock_irq(xas)    xa_unlock_irq((xas)->xa)
+#define xas_lock_irqsave(xas, flags) \
+                               xa_lock_irqsave((xas)->xa, flags)
+#define xas_unlock_irqrestore(xas, flags) \
+                               xa_unlock_irqrestore((xas)->xa, flags)
+
+/**
+ * xas_error() - Return an errno stored in the xa_state.
+ * @xas: XArray operation state.
+ *
+ * Return: 0 if no error has been noted.  A negative errno if one has.
+ */
+static inline int xas_error(const struct xa_state *xas)
+{
+       return xa_err(xas->xa_node);
+}
+
+/**
+ * xas_set_err() - Note an error in the xa_state.
+ * @xas: XArray operation state.
+ * @err: Negative error number.
+ *
+ * Only call this function with a negative @err; zero or positive errors
+ * will probably not behave the way you think they should.  If you want
+ * to clear the error from an xa_state, use xas_reset().
+ */
+static inline void xas_set_err(struct xa_state *xas, long err)
+{
+       xas->xa_node = XA_ERROR(err);
+}
+
+/**
+ * xas_invalid() - Is the xas in a retry or error state?
+ * @xas: XArray operation state.
+ *
+ * Return: %true if the xas cannot be used for operations.
+ */
+static inline bool xas_invalid(const struct xa_state *xas)
+{
+       return (unsigned long)xas->xa_node & 3;
+}
+
+/**
+ * xas_valid() - Is the xas a valid cursor into the array?
+ * @xas: XArray operation state.
+ *
+ * Return: %true if the xas can be used for operations.
+ */
+static inline bool xas_valid(const struct xa_state *xas)
+{
+       return !xas_invalid(xas);
+}
+
+/**
+ * xas_is_node() - Does the xas point to a node?
+ * @xas: XArray operation state.
+ *
+ * Return: %true if the xas currently references a node.
+ */
+static inline bool xas_is_node(const struct xa_state *xas)
+{
+       return xas_valid(xas) && xas->xa_node;
+}
+
+/* True if the pointer is something other than a node */
+static inline bool xas_not_node(struct xa_node *node)
+{
+       return ((unsigned long)node & 3) || !node;
+}
+
+/* True if the node represents RESTART or an error */
+static inline bool xas_frozen(struct xa_node *node)
+{
+       return (unsigned long)node & 2;
+}
+
+/* True if the node represents head-of-tree, RESTART or BOUNDS */
+static inline bool xas_top(struct xa_node *node)
+{
+       return node <= XAS_RESTART;
+}
+
+/**
+ * xas_reset() - Reset an XArray operation state.
+ * @xas: XArray operation state.
+ *
+ * Resets the error or walk state of the @xas so future walks of the
+ * array will start from the root.  Use this if you have dropped the
+ * xarray lock and want to reuse the xa_state.
+ *
+ * Context: Any context.
+ */
+static inline void xas_reset(struct xa_state *xas)
+{
+       xas->xa_node = XAS_RESTART;
+}
+
+/**
+ * xas_retry() - Retry the operation if appropriate.
+ * @xas: XArray operation state.
+ * @entry: Entry from xarray.
+ *
+ * The advanced functions may sometimes return an internal entry, such as
+ * a retry entry or a zero entry.  This function sets up the @xas to restart
+ * the walk from the head of the array if needed.
+ *
+ * Context: Any context.
+ * Return: true if the operation needs to be retried.
+ */
+static inline bool xas_retry(struct xa_state *xas, const void *entry)
+{
+       if (xa_is_zero(entry))
+               return true;
+       if (!xa_is_retry(entry))
+               return false;
+       xas_reset(xas);
+       return true;
+}
+
+void *xas_load(struct xa_state *);
+void *xas_store(struct xa_state *, void *entry);
+void *xas_find(struct xa_state *, unsigned long max);
+void *xas_find_conflict(struct xa_state *);
+
+bool xas_get_mark(const struct xa_state *, xa_mark_t);
+void xas_set_mark(const struct xa_state *, xa_mark_t);
+void xas_clear_mark(const struct xa_state *, xa_mark_t);
+void *xas_find_marked(struct xa_state *, unsigned long max, xa_mark_t);
+void xas_init_marks(const struct xa_state *);
+
+bool xas_nomem(struct xa_state *, gfp_t);
+void xas_pause(struct xa_state *);
+
+void xas_create_range(struct xa_state *);
+
+/**
+ * xas_reload() - Refetch an entry from the xarray.
+ * @xas: XArray operation state.
+ *
+ * Use this function to check that a previously loaded entry still has
+ * the same value.  This is useful for the lockless pagecache lookup where
+ * we walk the array with only the RCU lock to protect us, lock the page,
+ * then check that the page hasn't moved since we looked it up.
+ *
+ * The caller guarantees that @xas is still valid.  If it may be in an
+ * error or restart state, call xas_load() instead.
+ *
+ * Return: The entry at this location in the xarray.
+ */
+static inline void *xas_reload(struct xa_state *xas)
+{
+       struct xa_node *node = xas->xa_node;
+
+       if (node)
+               return xa_entry(xas->xa, node, xas->xa_offset);
+       return xa_head(xas->xa);
+}
+
+/**
+ * xas_set() - Set up XArray operation state for a different index.
+ * @xas: XArray operation state.
+ * @index: New index into the XArray.
+ *
+ * Move the operation state to refer to a different index.  This will
+ * have the effect of starting a walk from the top; see xas_next()
+ * to move to an adjacent index.
+ */
+static inline void xas_set(struct xa_state *xas, unsigned long index)
+{
+       xas->xa_index = index;
+       xas->xa_node = XAS_RESTART;
+}
+
+/**
+ * xas_set_order() - Set up XArray operation state for a multislot entry.
+ * @xas: XArray operation state.
+ * @index: Target of the operation.
+ * @order: Entry occupies 2^@order indices.
+ */
+static inline void xas_set_order(struct xa_state *xas, unsigned long index,
+                                       unsigned int order)
+{
+#ifdef CONFIG_XARRAY_MULTI
+       xas->xa_index = order < BITS_PER_LONG ? (index >> order) << order : 0;
+       xas->xa_shift = order - (order % XA_CHUNK_SHIFT);
+       xas->xa_sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;
+       xas->xa_node = XAS_RESTART;
+#else
+       BUG_ON(order > 0);
+       xas_set(xas, index);
+#endif
+}
+
+/**
+ * xas_set_update() - Set up XArray operation state for a callback.
+ * @xas: XArray operation state.
+ * @update: Function to call when updating a node.
+ *
+ * The XArray can notify a caller after it has updated an xa_node.
+ * This is advanced functionality and is only needed by the page cache.
+ */
+static inline void xas_set_update(struct xa_state *xas, xa_update_node_t update)
+{
+       xas->xa_update = update;
+}
+
+/**
+ * xas_next_entry() - Advance iterator to next present entry.
+ * @xas: XArray operation state.
+ * @max: Highest index to return.
+ *
+ * xas_next_entry() is an inline function to optimise xarray traversal for
+ * speed.  It is equivalent to calling xas_find(), and will call xas_find()
+ * for all the hard cases.
+ *
+ * Return: The next present entry after the one currently referred to by @xas.
+ */
+static inline void *xas_next_entry(struct xa_state *xas, unsigned long max)
+{
+       struct xa_node *node = xas->xa_node;
+       void *entry;
+
+       if (unlikely(xas_not_node(node) || node->shift ||
+                       xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)))
+               return xas_find(xas, max);
+
+       do {
+               if (unlikely(xas->xa_index >= max))
+                       return xas_find(xas, max);
+               if (unlikely(xas->xa_offset == XA_CHUNK_MASK))
+                       return xas_find(xas, max);
+               entry = xa_entry(xas->xa, node, xas->xa_offset + 1);
+               if (unlikely(xa_is_internal(entry)))
+                       return xas_find(xas, max);
+               xas->xa_offset++;
+               xas->xa_index++;
+       } while (!entry);
+
+       return entry;
+}
+
+/* Private */
+static inline unsigned int xas_find_chunk(struct xa_state *xas, bool advance,
+               xa_mark_t mark)
+{
+       unsigned long *addr = xas->xa_node->marks[(__force unsigned)mark];
+       unsigned int offset = xas->xa_offset;
+
+       if (advance)
+               offset++;
+       if (XA_CHUNK_SIZE == BITS_PER_LONG) {
+               if (offset < XA_CHUNK_SIZE) {
+                       unsigned long data = *addr & (~0UL << offset);
+                       if (data)
+                               return __ffs(data);
+               }
+               return XA_CHUNK_SIZE;
+       }
+
+       return find_next_bit(addr, XA_CHUNK_SIZE, offset);
+}
+
+/**
+ * xas_next_marked() - Advance iterator to next marked entry.
+ * @xas: XArray operation state.
+ * @max: Highest index to return.
+ * @mark: Mark to search for.
+ *
+ * xas_next_marked() is an inline function to optimise xarray traversal for
+ * speed.  It is equivalent to calling xas_find_marked(), and will call
+ * xas_find_marked() for all the hard cases.
+ *
+ * Return: The next marked entry after the one currently referred to by @xas.
+ */
+static inline void *xas_next_marked(struct xa_state *xas, unsigned long max,
+                                                               xa_mark_t mark)
+{
+       struct xa_node *node = xas->xa_node;
+       unsigned int offset;
+
+       if (unlikely(xas_not_node(node) || node->shift))
+               return xas_find_marked(xas, max, mark);
+       offset = xas_find_chunk(xas, true, mark);
+       xas->xa_offset = offset;
+       xas->xa_index = (xas->xa_index & ~XA_CHUNK_MASK) + offset;
+       if (xas->xa_index > max)
+               return NULL;
+       if (offset == XA_CHUNK_SIZE)
+               return xas_find_marked(xas, max, mark);
+       return xa_entry(xas->xa, node, offset);
+}
+
+/*
+ * If iterating while holding a lock, drop the lock and reschedule
+ * every %XA_CHECK_SCHED loops.
+ */
+enum {
+       XA_CHECK_SCHED = 4096,
+};
+
+/**
+ * xas_for_each() - Iterate over a range of an XArray.
+ * @xas: XArray operation state.
+ * @entry: Entry retrieved from the array.
+ * @max: Maximum index to retrieve from array.
+ *
+ * The loop body will be executed for each entry present in the xarray
+ * between the current xas position and @max.  @entry will be set to
+ * the entry retrieved from the xarray.  It is safe to delete entries
+ * from the array in the loop body.  You should hold either the RCU lock
+ * or the xa_lock while iterating.  If you need to drop the lock, call
+ * xas_pause() first.
+ */
+#define xas_for_each(xas, entry, max) \
+       for (entry = xas_find(xas, max); entry; \
+            entry = xas_next_entry(xas, max))
+
+/**
+ * xas_for_each_marked() - Iterate over a range of an XArray.
+ * @xas: XArray operation state.
+ * @entry: Entry retrieved from the array.
+ * @max: Maximum index to retrieve from array.
+ * @mark: Mark to search for.
+ *
+ * The loop body will be executed for each marked entry in the xarray
+ * between the current xas position and @max.  @entry will be set to
+ * the entry retrieved from the xarray.  It is safe to delete entries
+ * from the array in the loop body.  You should hold either the RCU lock
+ * or the xa_lock while iterating.  If you need to drop the lock, call
+ * xas_pause() first.
+ */
+#define xas_for_each_marked(xas, entry, max, mark) \
+       for (entry = xas_find_marked(xas, max, mark); entry; \
+            entry = xas_next_marked(xas, max, mark))
+
+/**
+ * xas_for_each_conflict() - Iterate over a range of an XArray.
+ * @xas: XArray operation state.
+ * @entry: Entry retrieved from the array.
+ *
+ * The loop body will be executed for each entry in the XArray that lies
+ * within the range specified by @xas.  If the loop completes successfully,
+ * any entries that lie in this range will be replaced by @entry.  The caller
+ * may break out of the loop; if they do so, the contents of the XArray will
+ * be unchanged.  The operation may fail due to an out of memory condition.
+ * The caller may also call xa_set_err() to exit the loop while setting an
+ * error to record the reason.
+ */
+#define xas_for_each_conflict(xas, entry) \
+       while ((entry = xas_find_conflict(xas)))
+
+void *__xas_next(struct xa_state *);
+void *__xas_prev(struct xa_state *);
+
+/**
+ * xas_prev() - Move iterator to previous index.
+ * @xas: XArray operation state.
+ *
+ * If the @xas was in an error state, it will remain in an error state
+ * and this function will return %NULL.  If the @xas has never been walked,
+ * it will have the effect of calling xas_load().  Otherwise one will be
+ * subtracted from the index and the state will be walked to the correct
+ * location in the array for the next operation.
+ *
+ * If the iterator was referencing index 0, this function wraps
+ * around to %ULONG_MAX.
+ *
+ * Return: The entry at the new index.  This may be %NULL or an internal
+ * entry.
+ */
+static inline void *xas_prev(struct xa_state *xas)
+{
+       struct xa_node *node = xas->xa_node;
+
+       if (unlikely(xas_not_node(node) || node->shift ||
+                               xas->xa_offset == 0))
+               return __xas_prev(xas);
+
+       xas->xa_index--;
+       xas->xa_offset--;
+       return xa_entry(xas->xa, node, xas->xa_offset);
+}
+
+/**
+ * xas_next() - Move state to next index.
+ * @xas: XArray operation state.
+ *
+ * If the @xas was in an error state, it will remain in an error state
+ * and this function will return %NULL.  If the @xas has never been walked,
+ * it will have the effect of calling xas_load().  Otherwise one will be
+ * added to the index and the state will be walked to the correct
+ * location in the array for the next operation.
+ *
+ * If the iterator was referencing index %ULONG_MAX, this function wraps
+ * around to 0.
+ *
+ * Return: The entry at the new index.  This may be %NULL or an internal
+ * entry.
+ */
+static inline void *xas_next(struct xa_state *xas)
+{
+       struct xa_node *node = xas->xa_node;
+
+       if (unlikely(xas_not_node(node) || node->shift ||
+                               xas->xa_offset == XA_CHUNK_MASK))
+               return __xas_next(xas);
+
+       xas->xa_index++;
+       xas->xa_offset++;
+       return xa_entry(xas->xa, node, xas->xa_offset);
+}
+
+#endif /* _LINUX_XARRAY_H */