kho: introduce the KHO array
Subsystems (5)
Pratyush Yadav
maintainercover kho: introduce the KHO array
Hi,
This series introduces the KHO array concept, and to demonstrate it in action it converts the perservation bitmaps to use it. It also takes Mike's vmalloc preservation patches v2 [0] and ports them to use the KHO array as well. The memfd preservation proposed in [1] can also be a user of this.
The main idea behind the KHO array is to build fundamental and flexible serialization data structures that other layers can use to make their logic easier. There was extensive discussion on this topic in [1]. This series provides actual code in action to give more substance to that discussion.
Patch 1 adds the KHO array. Read it for more details on the data structure. Patch 2 converts the memory preservation bitmaps to use KHO array. Patches 3 and 4 are from Mike's vmalloc series [0] and are modified to use KHO array instead of open-coding the linked lists. The full git tree can be found at [2].
When converting the two users to the KHO array, I think it did make the serialization logic simpler for both. The actual judgement of whether this is "worth it" is of course subjective, but I think this should at least give everyone a clear idea of how it looks like.
[0] https://lore.kernel.org/linux-mm/[email protected]/T/#u
[1] https://lore.kernel.org/linux-mm/[email protected]/T/#u
[2] https://git.kernel.org/pub/scm/linux/kernel/git/pratyush/linux.git/tag/?h=kho-array-rfc-v1
Mike Rapoport (Microsoft) (2):
kho: add support for preserving vmalloc allocations lib/test_kho: use kho_preserve_vmalloc instead of storing addresses in
fdt
Pratyush Yadav (2):
kho: introduce the KHO array
kho: use KHO array for preserved memory bitmap serialization
MAINTAINERS | 2 + include/linux/kexec_handover.h | 21 +++ include/linux/kho_array.h | 300 +++++++++++++++++++++++++++++++++ kernel/Makefile | 1 + kernel/kexec_handover.c | 291 +++++++++++++++++++++++--------- kernel/kho_array.c | 209 +++++++++++++++++++++++ lib/test_kho.c | 30 +++- 7 files changed, 768 insertions(+), 86 deletions(-) create mode 100644 include/linux/kho_array.h create mode 100644 kernel/kho_array.c
base-commit: b320789d6883cc00ac78ce83bccbfe7ed58afcf0
Signature · 1 line
2.47.3
Pratyush Yadav
maintainerRFC PATCH 1/4 kho: introduce the KHO array
The KHO Array is a data structure that behaves like a sparse array of pointers. It is designed to be preserved and restored over Kexec Handover (KHO), and targets only 64-bit platforms. It can store 8-byte aligned pointers. It can also store integers between 0 and LONG_MAX. It supports sparse indices, though it performs best with densely clustered indices.
The goal with KHO array is to provide a fundamental data type that can then be used to build serialization logic for higher layers. Moving the complexity of tracking these scattered list of pages to the KHO array layer makes higher layers simpler.
The data format consists of a descriptor of the array which contains a magic number, format version, and pointer to the first page. Each page contains the starting position of the entries in the page and a pointer to the next page, forming a linked list. This linked list allows for the array to be built with non-contiguous pages. Visually, the data format looks like below:
kho_array
+----------+
| Magic |
+----------+ kho_array_page
| Version | +----------+----------+-----------
+----------+ +--->| Next | Startpos | Entries...
| Reserved | | +----------+----------+-----------
+----------+ | | kho_array_page
| First |----+ | +----------+----------+-----------
+----------+ +--->| Next | Startpos | Entries...
+----------+----------+-----------
|
|
+--->...--- MAINTAINERS | 2 + include/linux/kho_array.h | 300 ++++++++++++++++++++++++++++++++++++++ kernel/Makefile | 1 + kernel/kho_array.c | 209 ++++++++++++++++++++++++++ 4 files changed, 512 insertions(+) create mode 100644 include/linux/kho_array.h create mode 100644 kernel/kho_array.c
MAINTAINERS +2 -0
@@ -13550,7 +13550,9 @@ S: Maintained F: Documentation/admin-guide/mm/kho.rst F: Documentation/core-api/kho/* F: include/linux/kexec_handover.h +F: include/linux/kho_array.h F: kernel/kexec_handover.c +F: kernel/kho_array.c F: tools/testing/selftests/kho/ KEYS-ENCRYPTED
include/linux/kho_array.h new file +300 -0
300 lines not on this page · raw message
kernel/Makefile +1 -0
@@ -82,6 +82,7 @@ obj-$(CONFIG_KEXEC) += kexec.o obj-$(CONFIG_KEXEC_FILE) += kexec_file.o obj-$(CONFIG_KEXEC_ELF) += kexec_elf.o obj-$(CONFIG_KEXEC_HANDOVER) += kexec_handover.o +obj-$(CONFIG_KEXEC_HANDOVER) += kho_array.o obj-$(CONFIG_BACKTRACE_SELF_TEST) += backtracetest.o obj-$(CONFIG_COMPAT) += compat.o obj-$(CONFIG_CGROUPS) += cgroup/
kernel/kho_array.c new file +209 -0
209 lines not on this page · raw message
Signature · 1 line
2.47.3
Quoted 6 lines · Pratyush Yadav
The KHO Array is a data structure that behaves like a sparse array of pointers. It is designed to be preserved and restored over Kexec Handover (KHO), and targets only 64-bit platforms. It can store 8-byte aligned pointers. It can also store integers between 0 and
LONG_MAX. It supports sparse indices, though it performs best with densely clustered indices.
That is a bit of an understatement, it looks like worst case cost is 4k per entry. I would expect better efficiency than this if we are serious about supporting sparsity..
I think you need to encode the start pos within the entries in some way so worst case cost is bounded to more like 16/24 byte per entry.
For instance if the page was broken up into an array of structs like
struct entries_block {
u64 flags:1;
u64 num_entries:13
u64 pos_increment:50;
u64 entries[]; // contiguous pos
};
And if a high 64 bit pos can't be represented with pos_increment then you'd have flags = X and entries[0] == pos instead.
Jason
Pratyush Yadav
maintainerHi Jason,
Quoted 15 lines · Jason Gunthorpe
Quoted 6 lines · Pratyush Yadav
The KHO Array is a data structure that behaves like a sparse array of pointers. It is designed to be preserved and restored over Kexec Handover (KHO), and targets only 64-bit platforms. It can store 8-byte aligned pointers. It can also store integers between 0 and
LONG_MAX. It supports sparse indices, though it performs best with densely clustered indices.That is a bit of an understatement, it looks like worst case cost is 4k per entry. I would expect better efficiency than this if we are serious about supporting sparsity..
I think you need to encode the start pos within the entries in some way so worst case cost is bounded to more like 16/24 byte per entry.
Quoted 8 lines
For instance if the page was broken up into an array of structs like
struct
entries_block{
u64 flags:1;
u64 num_entries:13
u64 pos_increment:50;
u64 entries[]; // contiguous pos
};
Right, good idea. I can look into this. But only if we get an agreement that this whole idea is worth pursuing. I don't want to waste time on something that will not make it in at a fundamental level :-)
I think another idea can be run-length encoding to make this even more efficient. But I have stayed away from that so far since I think that can get tricky and bug-prone to create and parse.
PS: do you know if bitfield layout is reliable for serialization? Can different compiler versions move them around? I always thought they can. If not, I can also use them in memfd code since they make the code neater.
Quoted 5 lines
And if a high 64 bit pos can't be represented with
pos_incrementthen you'd have flags = X and entries[0] == pos instead.Jason
Signature · 2 lines
Regards, Pratyush Yadav
Quoted 4 lines · Pratyush Yadav
PS: do you know if bitfield layout is reliable for serialization? Can different compiler versions move them around? I always thought they can. If not, I can also use them in memfd code since they make the code neater.
It is specified by the SYSV ABI, compilers are not free to change it.
I didn't check ARM64 but would be shocked to find it is not specified.
Jason
Pratyush Yadav
maintainerRFC PATCH 2/4 kho: use KHO array for preserved memory bitmap serialization
In reply to Pratyush YadavThe preserved memory bitmap preservation creates a linked list of pages to track the bitmaps for preserved memory. Essentially, it is a scattered list of pointers grouped by folio order. Use a KHO array to hold the pointers to the bitmaps instead. This moves the burden of tracking this metadata to the KHO array layer, and makes the KHO core simpler.
Currently, the bitmaps are held in chunks, which is a fixed-size array of pointers, plus some metadata including the order of the preserved folios. The KHO array holds only pointers and has no mechanism for grouping. To make the serialization format simpler, move the folio order from struct khoser_mem_chunk to struct khoser_mem_bitmap_ptr.
The chunks to hold the bitmaps are not KHO-preserved since they are only used during the scratch-only phase. The same holds true with the KHO array. The pages which track the KHO array metadata are not KHO-preserved and thus are only valid during the scratch phase of the next kernel. After that, they are discarded and freed to buddy.
---
The diff is a bit hard to read. The final result can be found at
https://git.kernel.org/pub/scm/linux/kernel/git/pratyush/linux.git/tree/kernel/kexec_handover.c?h=kho-array-rfc-v1#n227
kernel/kexec_handover.c | 148 +++++++++++++++++++--------------------- 1 file changed, 69 insertions(+), 79 deletions(-)
kernel/kexec_handover.c +69 -79
@@ -18,6 +18,7 @@#include <linux/memblock.h> #include <linux/notifier.h> #include <linux/page-isolation.h> +#include <linux/kho_array.h> #include <asm/early_ioremap.h>
@@ -80,15 +81,13 @@ struct kho_mem_track {struct xarray orders; }; -struct khoser_mem_chunk ; -struct kho_serialization {struct page *fdt;struct list_head fdt_list;struct dentry *sub_fdt_dir;struct kho_mem_track track; -/* First chunk of serialized preserved memory map */ -struct khoser_mem_chunk *preserved_mem_map; +/* Serialized preserved memory map */ +struct kho_array *preserved_mem_map; };static void *xa_load_or_alloc (struct xarray *xa,unsigned long index,size_t sz)
@@ -226,11 +225,11 @@ EXPORT_SYMBOL_GPL(kho_restore_folio);/* Serialize and deserialize struct kho_mem_phys across kexec * -* Record all the bitmaps in a linked list of pages for the next kernel to -* process. Each chunk holds bitmaps of the same order and each block of bitmaps -* starts at a given physical address. This allows the bitmaps to be sparse. The -* xarray is used to store them in a tree while building up the data structure, -* but the KHO successor kernel only needs to process them once in order. +* Record all the bitmaps in a KHO array for the next kernel to process. Each +* bitmap stores the order of the folios and starts at a given physical address. +* This allows the bitmaps to be sparse. The xarray is used to store them in a +* tree while building up the data structure, but the KHO successor kernel only +* needs to process them once in order. * * All of this memory is normal kmalloc() memory and is not marked for * preservation. The successor kernel will remain isolated to the scratch space
@@ -240,118 +239,107 @@ EXPORT_SYMBOL_GPL(kho_restore_folio);struct khoser_mem_bitmap_ptr {phys_addr_t phys_start; - DECLARE_KHOSER_PTR(bitmap, struct kho_mem_phys_bits *); -}; - -struct khoser_mem_chunk_hdr { - DECLARE_KHOSER_PTR(next, struct khoser_mem_chunk *);unsigned int order; -unsigned int num_elms; -}; - -#define KHOSER_BITMAP_SIZE \ - ((PAGE_SIZE - sizeof(struct khoser_mem_chunk_hdr)) / \ - sizeof(struct khoser_mem_bitmap_ptr)) - -struct khoser_mem_chunk { -struct khoser_mem_chunk_hdr hdr; -struct khoser_mem_bitmap_ptr bitmaps[KHOSER_BITMAP_SIZE ]; +unsigned int __reserved; + DECLARE_KHOSER_PTR(bitmap, struct kho_mem_phys_bits *); }; -static_assert (sizeof (struct khoser_mem_chunk ) ==PAGE_SIZE ); - -static struct khoser_mem_chunk *new_chunk (struct khoser_mem_chunk *cur_chunk, -unsigned long order) +static struct khoser_mem_bitmap_ptr *new_bitmap (phys_addr_t start, +struct kho_mem_phys_bits *bits, +unsigned int order) { -struct khoser_mem_chunk *chunk; +struct khoser_mem_bitmap_ptr *bitmap; - chunk =kzalloc (PAGE_SIZE ,GFP_KERNEL ); -if (!chunk) + bitmap =kzalloc (sizeof (*bitmap),GFP_KERNEL ); +if (!bitmap)return NULL ; - chunk->hdr.order = order; -if (cur_chunk) -KHOSER_STORE_PTR (cur_chunk->hdr.next, chunk); -return chunk; + + bitmap->phys_start = start; + bitmap->order = order; +KHOSER_STORE_PTR (bitmap->bitmap, bits); +return bitmap; } -static void kho_mem_ser_free (struct khoser_mem_chunk *first_chunk) +static void kho_mem_ser_free (struct kho_array *ka) { -struct khoser_mem_chunk *chunk = first_chunk; +struct khoser_mem_bitmap_ptr *elm; +struct ka_iter iter; -while (chunk) { -struct khoser_mem_chunk *tmp = chunk; +if (!ka) +return ; - chunk =KHOSER_LOAD_PTR (chunk->hdr.next); -kfree (tmp); - } +ka_iter_init_read (&iter, ka); +ka_iter_for_each (&iter, elm) +kfree (elm); + +kho_array_destroy (ka); +kfree (ka); }static int kho_mem_serialize (struct kho_serialization *ser) { -struct khoser_mem_chunk *first_chunk =NULL ; -struct khoser_mem_chunk *chunk =NULL ;struct kho_mem_phys *physxa; -unsigned long order; +unsigned long order, pos =0 ; +struct kho_array *ka =NULL ; +struct ka_iter iter; + + ka =kzalloc (sizeof (*ka),GFP_KERNEL ); +if (!ka) +return -ENOMEM ; +ka_iter_init_write (&iter, ka);xa_for_each (&ser->track.orders, order, physxa) {struct kho_mem_phys_bits *bits;unsigned long phys; - chunk =new_chunk (chunk, order); -if (!chunk) - goto err_free; - -if (!first_chunk) - first_chunk = chunk; -xa_for_each (&physxa->phys_bits, phys, bits) {struct khoser_mem_bitmap_ptr *elm; +phys_addr_t start; + + start = (phys *PRESERVE_BITS ) << (order +PAGE_SHIFT ); + elm =new_bitmap (start, bits, order); +if (!elm) + goto err_free; -if (chunk->hdr.num_elms ==ARRAY_SIZE (chunk->bitmaps)) { - chunk =new_chunk (chunk, order); -if (!chunk) - goto err_free; - } - - elm = &chunk->bitmaps[chunk->hdr.num_elms]; - chunk->hdr.num_elms++; - elm->phys_start = (phys *PRESERVE_BITS ) - << (order +PAGE_SHIFT ); -KHOSER_STORE_PTR (elm->bitmap, bits); +ka_iter_setpos (&iter, pos); +if (ka_iter_setentry (&iter, elm)) + goto err_free; + pos++; } } - ser->preserved_mem_map = first_chunk; + ser->preserved_mem_map = ka;return 0 ; err_free: -kho_mem_ser_free (first_chunk); +kho_mem_ser_free (ka);return -ENOMEM ; } -static void __init deserialize_bitmap (unsigned int order, -struct khoser_mem_bitmap_ptr *elm) +static void __init deserialize_bitmap (struct khoser_mem_bitmap_ptr *elm) {struct kho_mem_phys_bits *bitmap =KHOSER_LOAD_PTR (elm->bitmap);unsigned long bit;for_each_set_bit (bit, bitmap->preserve,PRESERVE_BITS ) { -int sz =1 << (order +PAGE_SHIFT ); +int sz =1 << (elm->order +PAGE_SHIFT );phys_addr_t phys = - elm->phys_start + (bit << (order +PAGE_SHIFT )); + elm->phys_start + (bit << (elm->order +PAGE_SHIFT ));struct page *page =phys_to_page (phys);memblock_reserve (phys, sz);memblock_reserved_mark_noinit (phys, sz); - page->private = order; + page->private = elm->order; } }static void __init kho_mem_deserialize (const void *fdt) { -struct khoser_mem_chunk *chunk; +struct khoser_mem_bitmap_ptr *elm;const phys_addr_t *mem; +struct kho_array *ka; +struct ka_iter iter;int len; mem =fdt_getprop (fdt,0 ,PROP_PRESERVED_MEMORY_MAP , &len);
@@ -361,15 +349,17 @@ static void __init kho_mem_deserialize(const void *fdt)return ; } - chunk = *mem ?phys_to_virt (*mem) :NULL ; -while (chunk) { -unsigned int i; - -for (i =0 ; i != chunk->hdr.num_elms; i++) -deserialize_bitmap (chunk->hdr.order, - &chunk->bitmaps[i]); - chunk =KHOSER_LOAD_PTR (chunk->hdr.next); + ka = *mem ?phys_to_virt (*mem) :NULL ; +if (!ka) +return ; +if (!kho_array_valid (ka)) { +pr_err ("invalid KHO array for preserved memory bitmaps\n" ); +return ; } + +ka_iter_init_read (&iter, ka); +ka_iter_for_each (&iter, elm) +deserialize_bitmap (elm); }/*
Signature · 1 line
2.47.3
Pratyush Yadav
maintainerRFC PATCH 3/4 kho: add support for preserving vmalloc allocations
In reply to Pratyush YadavFrom: "Mike Rapoport (Microsoft)" <[email protected]>
A vmalloc allocation is preserved using binary structure similar to global KHO memory tracker. It's a linked list of pages where each page is an array of physical address of pages in vmalloc area.
kho_preserve_vmalloc() hands out the physical address of the head page to the caller. This address is used as the argument to kho_vmalloc_restore() to restore the mapping in the vmalloc address space and populate it with the preserved pages.
[[email protected]: use KHO array instead of linked list of pages to track physical addresses]
--- include/linux/kexec_handover.h | 21 +++++ kernel/kexec_handover.c | 143 +++++++++++++++++++++++++++++++++ 2 files changed, 164 insertions(+)
include/linux/kexec_handover.h +21 -0
@@ -4,6 +4,7 @@#include <linux/types.h> #include <linux/errno.h> +#include <linux/kho_array.h> struct kho_scratch {phys_addr_t addr;
@@ -37,13 +38,23 @@ struct notifier_block; })struct kho_serialization ; +struct kho_vmalloc ;#ifdef CONFIG_KEXEC_HANDOVER +struct kho_vmalloc { +struct kho_array ka; +unsigned int total_pages; +unsigned int flags; +unsigned short order; +}; +bool kho_is_enabled (void );int kho_preserve_folio (struct folio *folio); +int kho_preserve_vmalloc (void *ptr,struct kho_vmalloc *preservation);int kho_preserve_phys (phys_addr_t phys,size_t size);struct folio *kho_restore_folio (phys_addr_t phys); +void *kho_restore_vmalloc (struct kho_vmalloc *preservation);int kho_add_subtree (struct kho_serialization *ser,const char *name,void *fdt);int kho_retrieve_subtree (const char *name,phys_addr_t *phys);
@@ -70,11 +81,21 @@ static inline int kho_preserve_phys(phys_addr_t phys, size_t size)return -EOPNOTSUPP ; } +static inline int kho_preserve_vmalloc (void *ptr,struct kho_vmalloc *preservation) +{ +return -EOPNOTSUPP ; +} +static inline struct folio *kho_restore_folio (phys_addr_t phys) {return NULL ; } +static inline void *kho_restore_vmalloc (struct kho_vmalloc *preservation) +{ +return NULL ; +} +static inline int kho_add_subtree (struct kho_serialization *ser,const char *name,void *fdt) {
kernel/kexec_handover.c +143 -0
155 lines not on this page · raw message
Signature · 1 line
2.47.3
Pratyush Yadav
maintainerRFC PATCH 4/4 lib/test_kho: use kho_preserve_vmalloc instead of storing addresses in fdt
In reply to Pratyush YadavFrom: "Mike Rapoport (Microsoft)" <[email protected]>
KHO test stores physical addresses of the preserved folios directly in fdt.
Use kho_preserve_vmalloc() instead of it and kho_restore_vmalloc() to retrieve the addresses after kexec.
This makes the test more scalable from one side and adds tests coverage for kho_preserve_vmalloc() from the other.
--- lib/test_kho.c | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-)
lib/test_kho.c +23 -7
@@ -32,6 +32,7 @@ module_param(max_mem, long, 0644);struct kho_test_state {unsigned int nr_folios;struct folio **folios; +phys_addr_t *folios_info;struct folio *fdt;__wsum csum; };
@@ -67,14 +68,18 @@ static struct notifier_block kho_test_nb = {static int kho_test_save_data (struct kho_test_state *state,void *fdt) { +struct kho_vmalloc folios_info_preservation = {}; phys_addr_t *folios_info __free(kvfree) = NULL;int err =0 ; - folios_info =kvmalloc_array (state->nr_folios,sizeof (*folios_info), -GFP_KERNEL ); + folios_info =vmalloc_array (state->nr_folios,sizeof (*folios_info));if (!folios_info)return -ENOMEM ; + err =kho_preserve_vmalloc (folios_info, &folios_info_preservation); +if (err) +return err; +for (int i =0 ; i < state->nr_folios; i++) {struct folio *folio = state->folios[i];unsigned int order =folio_order (folio);
@@ -89,11 +94,14 @@ static int kho_test_save_data(struct kho_test_state *state, void *fdt) err |=fdt_begin_node (fdt,"data" ); err |=fdt_property (fdt,"nr_folios" , &state->nr_folios,sizeof (state->nr_folios)); - err |=fdt_property (fdt,"folios_info" , folios_info, - state->nr_folios *sizeof (*folios_info)); + err |=fdt_property (fdt,"folios_info" , &folios_info_preservation, +sizeof (folios_info_preservation)); err |=fdt_property (fdt,"csum" , &state->csum,sizeof (state->csum)); err |=fdt_end_node (fdt); +if (!err) + state->folios_info =no_free_ptr (folios_info); +return err; }
@@ -197,7 +205,8 @@ static int kho_test_save(void)static int kho_test_restore_data (const void *fdt,int node) {const unsigned int *nr_folios; -const phys_addr_t *folios_info; +const struct kho_vmalloc *folios_info_preservation; +phys_addr_t *folios_info;const __wsum *old_csum;__wsum csum =0 ;int len;
@@ -212,8 +221,12 @@ static int kho_test_restore_data(const void *fdt, int node)if (!old_csum || len !=sizeof (*old_csum))return -EINVAL ; - folios_info =fdt_getprop (fdt, node,"folios_info" , &len); -if (!folios_info || len !=sizeof (*folios_info) * *nr_folios) + folios_info_preservation =fdt_getprop (fdt, node,"folios_info" , &len); +if (!folios_info_preservation || len !=sizeof (*folios_info_preservation)) +return -EINVAL ; + + folios_info =kho_restore_vmalloc ((struct kho_vmalloc *)folios_info_preservation); +if (!folios_info)return -EINVAL ;for (int i =0 ; i < *nr_folios; i++) {
@@ -233,6 +246,8 @@ static int kho_test_restore_data(const void *fdt, int node)folio_put (folio); } +vfree (folios_info); +if (csum != *old_csum)return -EINVAL ;
@@ -291,6 +306,7 @@ static void kho_test_cleanup(void)folio_put (kho_test_state.folios[i]);kvfree (kho_test_state.folios); +vfree (kho_test_state.folios_info); } static void __exit kho_test_exit(void)
Signature · 1 line
2.47.3