From: Anthony Yznaga <anthony.yznaga@oracle.com>
To: linux-mm@kvack.org, linux-kernel@vger.kernel.org
Cc: willy@infradead.org, corbet@lwn.net, tglx@linutronix.de,
mingo@redhat.com, bp@alien8.de, x86@kernel.org, hpa@zytor.com,
dave.hansen@linux.intel.com, luto@kernel.org,
peterz@infradead.org, rppt@linux.ibm.com,
akpm@linux-foundation.org, hughd@google.com,
ebiederm@xmission.com, masahiroy@kernel.org, ardb@kernel.org,
ndesaulniers@google.com, dima@golovin.in,
daniel.kiper@oracle.com, nivedita@alum.mit.edu,
rafael.j.wysocki@intel.com, dan.j.williams@intel.com,
zhenzhong.duan@oracle.com, jroedel@suse.de, bhe@redhat.com,
guro@fb.com, Thomas.Lendacky@amd.com,
andriy.shevchenko@linux.intel.com, keescook@chromium.org,
hannes@cmpxchg.org, minchan@kernel.org, mhocko@kernel.org,
ying.huang@intel.com, yang.shi@linux.alibaba.com,
gustavo@embeddedor.com, ziqian.lzq@antfin.com,
vdavydov.dev@gmail.com, jason.zeng@intel.com,
kevin.tian@intel.com, zhiyuan.lv@intel.com, lei.l.li@intel.com,
paul.c.lai@intel.com, ashok.raj@intel.com,
linux-fsdevel@vger.kernel.org, linux-doc@vger.kernel.org,
kexec@lists.infradead.org
Subject: [RFC 41/43] XArray: add xas_export_node() and xas_import_node()
Date: Wed, 6 May 2020 17:42:07 -0700 [thread overview]
Message-ID: <1588812129-8596-42-git-send-email-anthony.yznaga@oracle.com> (raw)
In-Reply-To: <1588812129-8596-1-git-send-email-anthony.yznaga@oracle.com>
Contention on the xarray lock when multiple threads are adding to the
same xarray can be mitigated by providing a way to add entries in
bulk.
Allow a caller to allocate and populate an xarray node outside of
the target xarray and then only take the xarray lock long enough to
import the node into it.
Signed-off-by: Anthony Yznaga <anthony.yznaga@oracle.com>
---
Documentation/core-api/xarray.rst | 8 +++
include/linux/xarray.h | 2 +
lib/test_xarray.c | 45 +++++++++++++++++
lib/xarray.c | 100 ++++++++++++++++++++++++++++++++++++++
4 files changed, 155 insertions(+)
diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
index 640934b6f7b4..659e10df8901 100644
--- a/Documentation/core-api/xarray.rst
+++ b/Documentation/core-api/xarray.rst
@@ -444,6 +444,14 @@ called each time the XArray updates a node. This is used by the page
cache workingset code to maintain its list of nodes which contain only
shadow entries.
+xas_export_node() is used to remove and return a node from an XArray
+while xas_import_node() is used to add a node to an XArray. Together
+these can be used, for example, to reduce lock contention when multiple
+threads are updating an XArray by allowing a caller to allocate and
+populate a node outside of the target XArray in a local XArray, export
+the node, and then take the target XArray lock just long enough to import
+the node.
+
Multi-Index Entries
-------------------
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index 14c893433139..73bd8ccc4424 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -1504,6 +1504,8 @@ bool xas_nomem(struct xa_state *, gfp_t);
void xas_pause(struct xa_state *);
void xas_create_range(struct xa_state *);
+struct xa_node *xas_export_node(struct xa_state *xas);
+void xas_import_node(struct xa_state *xas, struct xa_node *node);
/**
* xas_reload() - Refetch an entry from the xarray.
diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index d4f97925dbd8..5cfaa1720cc1 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -1682,6 +1682,50 @@ static noinline void check_destroy(struct xarray *xa)
#endif
}
+static noinline void check_export_import_1(struct xarray *xa,
+ unsigned long index, unsigned int order)
+{
+ int xa_shift = order + XA_CHUNK_SHIFT - (order % XA_CHUNK_SHIFT);
+ XA_STATE(xas, xa, index);
+ struct xa_node *node;
+ unsigned long i;
+
+ xa_store_many_order(xa, index, xa_shift);
+
+ xas_lock(&xas);
+ xas_set_order(&xas, index, xa_shift);
+ node = xas_export_node(&xas);
+ xas_unlock(&xas);
+
+ XA_BUG_ON(xa, !xa_empty(xa));
+
+ do {
+ xas_lock(&xas);
+ xas_set_order(&xas, index, xa_shift);
+ xas_import_node(&xas, node);
+ xas_unlock(&xas);
+ } while (xas_nomem(&xas, GFP_KERNEL));
+
+ for (i = index; i < index + (1UL << xa_shift); i++)
+ xa_erase_index(xa, i);
+
+ XA_BUG_ON(xa, !xa_empty(xa));
+}
+
+static noinline void check_export_import(struct xarray *xa)
+{
+ unsigned int order;
+ unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
+
+ for (order = 0; order < max_order; order += XA_CHUNK_SHIFT) {
+ int xa_shift = order + XA_CHUNK_SHIFT;
+ unsigned long j;
+
+ for (j = 0; j < XA_CHUNK_SIZE; j++)
+ check_export_import_1(xa, j << xa_shift, order);
+ }
+}
+
static DEFINE_XARRAY(array);
static int xarray_checks(void)
@@ -1712,6 +1756,7 @@ static int xarray_checks(void)
check_workingset(&array, 0);
check_workingset(&array, 64);
check_workingset(&array, 4096);
+ check_export_import(&array);
printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
return (tests_run == tests_passed) ? 0 : -EINVAL;
diff --git a/lib/xarray.c b/lib/xarray.c
index e9e641d3c0c3..478925780e87 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -507,6 +507,30 @@ static void xas_delete_node(struct xa_state *xas)
xas_shrink(xas);
}
+static void xas_unlink_node(struct xa_state *xas)
+{
+ struct xa_node *node = xas->xa_node;
+ struct xa_node *parent;
+
+ parent = xa_parent_locked(xas->xa, node);
+ xas->xa_node = parent;
+ xas->xa_offset = node->offset;
+
+ if (!parent) {
+ xas->xa->xa_head = NULL;
+ xas->xa_node = XAS_BOUNDS;
+ return;
+ }
+
+ parent->slots[xas->xa_offset] = NULL;
+ parent->count--;
+ XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE);
+
+ xas_update(xas, parent);
+
+ xas_delete_node(xas);
+}
+
/**
* xas_free_nodes() - Free this node and all nodes that it references
* @xas: Array operation state.
@@ -1540,6 +1564,82 @@ static void xas_set_range(struct xa_state *xas, unsigned long first,
}
/**
+ * xas_export_node() - remove and return a node from an XArray
+ * @xas: XArray operation state
+ *
+ * The range covered by @xas must be aligned to and cover a single node
+ * at any level of the tree.
+ *
+ * Return: On success, returns the removed node. If the range is invalid,
+ * returns %NULL and sets -EINVAL in @xas. Otherwise returns %NULL if the
+ * node does not exist.
+ */
+struct xa_node *xas_export_node(struct xa_state *xas)
+{
+ struct xa_node *node;
+
+ if (!xas->xa_shift || xas->xa_sibs) {
+ xas_set_err(xas, -EINVAL);
+ return NULL;
+ }
+
+ xas->xa_shift -= XA_CHUNK_SHIFT;
+
+ if (!xas_find(xas, xas->xa_index))
+ return NULL;
+ node = xas->xa_node;
+ xas_unlink_node(xas);
+ node->parent = NULL;
+
+ return node;
+}
+
+/**
+ * xas_import_node() - add a node to an XArray
+ * @xas: XArray operation state
+ * @node: The node to add
+ *
+ * The range covered by @xas must be aligned to and cover a single node
+ * at any level of the tree. No nodes should already exist within the
+ * range.
+ * Sets an error in @xas if the range is invalid or xas_create() fails
+ */
+void xas_import_node(struct xa_state *xas, struct xa_node *node)
+{
+ struct xa_node *parent = NULL;
+ void __rcu **slot = &xas->xa->xa_head;
+ int count = 0;
+
+ if (!xas->xa_shift || xas->xa_sibs) {
+ xas_set_err(xas, -EINVAL);
+ return;
+ }
+
+ if (xas->xa_index || xa_head_locked(xas->xa)) {
+ xas_set_order(xas, xas->xa_index, node->shift + XA_CHUNK_SHIFT);
+ xas_create(xas, true);
+
+ if (xas_invalid(xas))
+ return;
+
+ parent = xas->xa_node;
+ }
+
+ if (parent) {
+ slot = &parent->slots[xas->xa_offset];
+ node->offset = xas->xa_offset;
+ count++;
+ }
+
+ RCU_INIT_POINTER(node->parent, parent);
+ node->array = xas->xa;
+
+ rcu_assign_pointer(*slot, xa_mk_node(node));
+
+ update_node(xas, parent, count, 0);
+}
+
+/**
* xa_store_range() - Store this entry at a range of indices in the XArray.
* @xa: XArray.
* @first: First index to affect.
--
2.13.3
next prev parent reply other threads:[~2020-05-07 0:48 UTC|newest]
Thread overview: 50+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-07 0:41 [RFC 00/43] PKRAM: Preserved-over-Kexec RAM Anthony Yznaga
2020-05-07 0:41 ` [RFC 01/43] mm: add PKRAM API stubs and Kconfig Anthony Yznaga
2020-05-07 0:41 ` [RFC 02/43] mm: PKRAM: implement node load and save functions Anthony Yznaga
2020-05-07 0:41 ` [RFC 03/43] mm: PKRAM: implement object " Anthony Yznaga
2020-05-07 0:41 ` [RFC 04/43] mm: PKRAM: implement page stream operations Anthony Yznaga
2020-05-07 0:41 ` [RFC 05/43] mm: PKRAM: support preserving transparent hugepages Anthony Yznaga
2020-05-07 0:41 ` [RFC 06/43] mm: PKRAM: implement byte stream operations Anthony Yznaga
2020-05-07 0:41 ` [RFC 07/43] mm: PKRAM: link nodes by pfn before reboot Anthony Yznaga
2020-05-07 0:41 ` [RFC 08/43] mm: PKRAM: introduce super block Anthony Yznaga
2020-05-07 0:41 ` [RFC 09/43] PKRAM: build a physical mapping pagetable of pages to be preserved Anthony Yznaga
2020-05-07 0:41 ` [RFC 10/43] PKRAM: add code for walking the preserved pages pagetable Anthony Yznaga
2020-05-07 0:41 ` [RFC 11/43] PKRAM: pass the preserved pages pagetable to the next kernel Anthony Yznaga
2020-05-07 0:41 ` [RFC 12/43] mm: PKRAM: reserve preserved memory at boot Anthony Yznaga
2020-05-07 0:41 ` [RFC 13/43] mm: PKRAM: free preserved pages pagetable Anthony Yznaga
2020-05-07 0:41 ` [RFC 14/43] mm: memblock: PKRAM: prevent memblock resize from clobbering preserved pages Anthony Yznaga
2020-05-11 13:57 ` Mike Rapoport
2020-05-11 23:29 ` Anthony Yznaga
2020-05-07 0:41 ` [RFC 15/43] PKRAM: provide a way to ban pages from use by PKRAM Anthony Yznaga
2020-05-07 0:41 ` [RFC 16/43] kexec: PKRAM: prevent kexec clobbering preserved pages in some cases Anthony Yznaga
2020-05-07 0:41 ` [RFC 17/43] PKRAM: provide a way to check if a memory range has preserved pages Anthony Yznaga
2020-05-07 0:41 ` [RFC 18/43] kexec: PKRAM: avoid clobbering already " Anthony Yznaga
2020-05-07 0:41 ` [RFC 19/43] mm: PKRAM: allow preserved memory to be freed from userspace Anthony Yznaga
2020-05-07 0:41 ` [RFC 20/43] PKRAM: disable feature when running the kdump kernel Anthony Yznaga
2020-05-07 0:41 ` [RFC 21/43] x86/KASLR: PKRAM: support physical kaslr Anthony Yznaga
2020-05-07 17:51 ` Kees Cook
2020-05-07 18:41 ` Anthony Yznaga
2020-05-07 0:41 ` [RFC 22/43] mm: shmem: introduce shmem_insert_page Anthony Yznaga
2020-05-07 0:41 ` [RFC 23/43] mm: shmem: enable saving to PKRAM Anthony Yznaga
2020-05-07 0:41 ` [RFC 24/43] mm: shmem: prevent swapping of PKRAM-enabled tmpfs pages Anthony Yznaga
2020-05-07 0:41 ` [RFC 25/43] mm: shmem: specify the mm to use when inserting pages Anthony Yznaga
2020-05-07 0:41 ` [RFC 26/43] mm: shmem: when inserting, handle pages already charged to a memcg Anthony Yznaga
2020-05-07 0:41 ` [RFC 27/43] x86/mm/numa: add numa_isolate_memblocks() Anthony Yznaga
2020-05-07 0:41 ` [RFC 28/43] PKRAM: ensure memblocks with preserved pages init'd for numa Anthony Yznaga
2020-05-07 0:41 ` [RFC 29/43] memblock: PKRAM: mark memblocks that contain preserved pages Anthony Yznaga
2020-05-07 0:41 ` [RFC 30/43] memblock: add for_each_reserved_mem_range() Anthony Yznaga
2020-05-07 0:41 ` [RFC 31/43] memblock, mm: defer initialization of preserved pages Anthony Yznaga
2020-05-07 0:41 ` [RFC 32/43] shmem: PKRAM: preserve shmem files a chunk at a time Anthony Yznaga
2020-05-07 0:41 ` [RFC 33/43] PKRAM: atomically add and remove link pages Anthony Yznaga
2020-05-07 0:42 ` [RFC 34/43] shmem: PKRAM: multithread preserving and restoring shmem pages Anthony Yznaga
2020-05-07 16:30 ` Randy Dunlap
2020-05-07 17:59 ` Anthony Yznaga
2020-05-07 0:42 ` [RFC 35/43] shmem: introduce shmem_insert_pages() Anthony Yznaga
2020-05-07 0:42 ` [RFC 36/43] PKRAM: add support for loading pages in bulk Anthony Yznaga
2020-05-07 0:42 ` [RFC 37/43] shmem: PKRAM: enable bulk loading of preserved pages into shmem Anthony Yznaga
2020-05-07 0:42 ` [RFC 38/43] mm: implement splicing a list of pages to the LRU Anthony Yznaga
2020-05-07 0:42 ` [RFC 39/43] shmem: optimize adding pages to the LRU in shmem_insert_pages() Anthony Yznaga
2020-05-07 0:42 ` [RFC 40/43] shmem: initial support for adding multiple pages to pagecache Anthony Yznaga
2020-05-07 0:42 ` Anthony Yznaga [this message]
2020-05-07 0:42 ` [RFC 42/43] shmem: reduce time holding xa_lock when inserting pages Anthony Yznaga
2020-05-07 0:42 ` [RFC 43/43] PKRAM: improve index alignment of pkram_link entries Anthony Yznaga
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1588812129-8596-42-git-send-email-anthony.yznaga@oracle.com \
--to=anthony.yznaga@oracle.com \
--cc=Thomas.Lendacky@amd.com \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=ardb@kernel.org \
--cc=ashok.raj@intel.com \
--cc=bhe@redhat.com \
--cc=bp@alien8.de \
--cc=corbet@lwn.net \
--cc=dan.j.williams@intel.com \
--cc=daniel.kiper@oracle.com \
--cc=dave.hansen@linux.intel.com \
--cc=dima@golovin.in \
--cc=ebiederm@xmission.com \
--cc=guro@fb.com \
--cc=gustavo@embeddedor.com \
--cc=hannes@cmpxchg.org \
--cc=hpa@zytor.com \
--cc=hughd@google.com \
--cc=jason.zeng@intel.com \
--cc=jroedel@suse.de \
--cc=keescook@chromium.org \
--cc=kevin.tian@intel.com \
--cc=kexec@lists.infradead.org \
--cc=lei.l.li@intel.com \
--cc=linux-doc@vger.kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=luto@kernel.org \
--cc=masahiroy@kernel.org \
--cc=mhocko@kernel.org \
--cc=minchan@kernel.org \
--cc=mingo@redhat.com \
--cc=ndesaulniers@google.com \
--cc=nivedita@alum.mit.edu \
--cc=paul.c.lai@intel.com \
--cc=peterz@infradead.org \
--cc=rafael.j.wysocki@intel.com \
--cc=rppt@linux.ibm.com \
--cc=tglx@linutronix.de \
--cc=vdavydov.dev@gmail.com \
--cc=willy@infradead.org \
--cc=x86@kernel.org \
--cc=yang.shi@linux.alibaba.com \
--cc=ying.huang@intel.com \
--cc=zhenzhong.duan@oracle.com \
--cc=zhiyuan.lv@intel.com \
--cc=ziqian.lzq@antfin.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).