Linux-mm Archive on lore.kernel.org
 help / color / mirror / Atom feed
From: Pratyush Yadav <pratyush@kernel.org>
To: Mike Rapoport <rppt@kernel.org>,
	Pasha Tatashin <pasha.tatashin@soleen.com>,
	Pratyush Yadav <pratyush@kernel.org>,
	Alexander Graf <graf@amazon.com>,
	Jonathan Corbet <corbet@lwn.net>,
	Shuah Khan <skhan@linuxfoundation.org>,
	Randy Dunlap <rdunlap@infradead.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	Tarun Sahu <tarunsahu@google.com>,
	David Matlack <dmatlack@google.com>,
	Samiullah Khawaja <skhawaja@google.com>
Cc: kexec@lists.infradead.org, linux-mm@kvack.org,
	linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
	linux-kselftest@vger.kernel.org
Subject: [RFC PATCH 0/5] KHO map
Date: Mon, 16 Nov 2026 14:40:05 +0100	[thread overview]
Message-ID: <20261116134013.1636689-1-pratyush@kernel.org> (raw)

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

Hi,

This series introduces the KHO map. It is a sparse map from integer keys
to u64 values. It is implemented as a radix tree of fixed depth.
Currently the tree depth is 6, so it can support keys up to 54 bits
wide.

The main user of the map is memfd. Currently memfd uses a vmalloc buffer
that has a pair of {index,pfn} to track the folios in the file. That
uses 16 bytes per page. The KHO map uses only 8 bytes per page with some
overhead. So for a 1 GiB memfd, it uses roughly half the memory.

In addition, it is a more versatile data structure. For example, it
allows for adding or removing pages from a memfd after preserve more
efficiently than the vmalloc array.

Post-LPC 2026, the plan is for KHO to maintain backwards compatibility
as much as possible. So this data structure allows the serialization
format to be more flexible to future changes. It can also be used by the
upcoming HugeTLB and guest_memfd preservation.

I have talked about this as "KHO xarray" before, but I think using
"xarray" is just going to confuse everyone since it isn't really a
xarray, and the API works a fair bit differently. So I renamed it to
"KHO map".

This series isn't complete yet, but it is in fairly good shape so I want
to share it to get some early feedback.

Things that are missing and planned in the future:

- Multi-index entry support: currently, while the map is very efficient
  with 4k folios, it is horribly inefficient with 2M folios. Each folio
  in the memfd takes up a full page to track. Multi-index entry support
  can fix this by tracking entries that cover a whole page in the
  previous level, similar to page tables.

- LUO versioning support: LUO versioning headers are still in
  discussion. This data structure should use them for future
  extensibility. I am mainly waiting for things to settle down there.

- Dynamic depth support: Currently the depth is static, so it can only
  support keys up to 54 bits wide. Adding support for multiple depth
  levels based on what the caller needs can improve efficiency and
  flexibility. I likely will only add support for this in the ABI and
  leave the actual implementation for later when we have a real use
  case.

This series is based on a couple of memfd patches I sent earlier [0][1].

[0] https://lore.kernel.org/kexec/20261103172251.2348370-1-pratyush@kernel.org/
[1] https://lore.kernel.org/kexec/20261110175855.2437084-1-pratyush@kernel.org/

Regards,
Pratyush Yadav

Pratyush Yadav (Google) (5):
  kho: add KHOSER_CLEAR_PTR()
  kho: build KHO objects into a single kho.o
  kho: add KHO map
  kho: test: add KHO map test
  mm/memfd_luo: use KHO map for tracking folios

 Documentation/core-api/kho/abi.rst     |   5 +
 Documentation/core-api/kho/index.rst   |  12 +
 include/linux/kho/abi/kexec_handover.h |   5 +
 include/linux/kho/abi/map.h            |  94 ++++
 include/linux/kho/abi/memfd.h          |  39 +-
 include/linux/kho_map.h                |  77 ++++
 kernel/liveupdate/Makefile             |  13 +-
 kernel/liveupdate/kho_map.c            | 514 ++++++++++++++++++++++
 lib/Kconfig.debug                      |   4 +
 lib/Makefile                           |   2 +-
 lib/test_kho_map.c                     | 575 +++++++++++++++++++++++++
 mm/memfd_luo.c                         | 292 ++++++-------
 tools/testing/selftests/kho/vmtest.sh  |   2 +
 13 files changed, 1449 insertions(+), 185 deletions(-)
 create mode 100644 include/linux/kho/abi/map.h
 create mode 100644 include/linux/kho_map.h
 create mode 100644 kernel/liveupdate/kho_map.c
 create mode 100644 lib/test_kho_map.c


base-commit: a0dc8eddbfdb6dd9c5c2b70eb66ab49cb1978425
prerequisite-patch-id: dc555295a2263ea9482ab393c50296636ab1e84f
prerequisite-patch-id: b0c8f9caeb6fd99a352692083e4d2e9255f13d02
prerequisite-patch-id: af8beaebdb1687c349732dc4a7773f7baa4a2c17
-- 
2.56.0.611.g1030f0b940-goog



             reply	other threads:[~2026-11-16 13:40 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16 13:40 Pratyush Yadav [this message]
2026-11-16 13:40 ` [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR() Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 2/5] kho: build KHO objects into a single kho.o Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 3/5] kho: add KHO map Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 4/5] kho: test: add KHO map test Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 5/5] mm/memfd_luo: use KHO map for tracking folios Pratyush Yadav

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=20261116134013.1636689-1-pratyush@kernel.org \
    --to=pratyush@kernel.org \
    --cc=akpm@linux-foundation.org \
    --cc=corbet@lwn.net \
    --cc=dmatlack@google.com \
    --cc=graf@amazon.com \
    --cc=kexec@lists.infradead.org \
    --cc=linux-doc@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-kselftest@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=pasha.tatashin@soleen.com \
    --cc=rdunlap@infradead.org \
    --cc=rppt@kernel.org \
    --cc=skhan@linuxfoundation.org \
    --cc=skhawaja@google.com \
    --cc=tarunsahu@google.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