projects/linux·blob master · refs

416 lines · 10.5 KiB

1// SPDX-License-Identifier: GPL-2.0
2
3/*
4 * Copyright (c) 2026, Google LLC.
5 * Pasha Tatashin <[email protected]>
6 */
7
8/**
9 * DOC: KHO Serialization Blocks
10 *
11 * KHO provides a mechanism to preserve stateful data across a kexec handover
12 * by serializing it into memory blocks, and provides the common
13 * infrastructure for managing these blocks.
14 *
15 * Each block consists of a header (struct kho_block_header_ser) followed by an
16 * array of serialized entries. Multiple blocks are linked together via a
17 * physical pointer in the header, forming a linked list that can be easily
18 * traversed in both the current and the next kernel.
19 */
20
21#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
22
23#include <linux/io.h>
24#include <linux/kexec_handover.h>
25#include <linux/kho/abi/block.h>
26#include <linux/kho_block.h>
27#include <linux/slab.h>
28
29/*
30 * Safeguard limit for the number of serialization blocks. This is used to
31 * prevent infinite loops and excessive memory allocation in case of memory
32 * corruption in the preserved state.
33 *
34 * With a 4KB page size, 10k blocks is about 40MB. For 32-byte entries
35 * (e.g. 4 u64s), each block holds up to 127 entries (accounting for the
36 * 16-byte header), allowing the block set to hold up to 1.27M entries.
37 */
38#define KHO_MAX_BLOCKS 10000
39
40/**
41 * kho_block_set_init - Initialize a block set.
42 * @bs: The block set to initialize.
43 * @entry_size: The size of each entry in the blocks.
44 */
45void kho_block_set_init(struct kho_block_set *bs, size_t entry_size)
46{
47 *bs = (struct kho_block_set)KHO_BLOCK_SET_INIT(*bs, entry_size);
48 WARN_ON_ONCE(!bs->count_per_block);
49}
50
51/* Serialized entries start immediately after the block header */
52static void *kho_block_entries(struct kho_block *block)
53{
54 return (void *)(block->ser + 1);
55}
56
57/* Get the address of the serialized entry at the specified index */
58static void *kho_block_entry(struct kho_block_set_it *it, u64 index)
59{
60 return kho_block_entries(it->block) + (index * it->bs->entry_size);
61}
62
63/* Free serialized data */
64static void kho_block_free_ser(struct kho_block_set *bs,
65 struct kho_block_header_ser *ser)
66{
67 if (bs->incoming)
68 kho_restore_free(ser);
69 else
70 kho_unpreserve_free(ser);
71}
72
73static struct kho_block_header_ser *kho_block_alloc_ser(struct kho_block_set *bs)
74{
75 WARN_ON_ONCE(bs->incoming);
76 return kho_alloc_preserve(KHO_BLOCK_SIZE);
77}
78
79static int kho_block_add(struct kho_block_set *bs,
80 struct kho_block_header_ser *ser)
81{
82 struct kho_block *block, *last;
83
84 if (bs->nblocks >= KHO_MAX_BLOCKS)
85 return -ENOSPC;
86
87 block = kzalloc_obj(*block);
88 if (!block)
89 return -ENOMEM;
90
91 block->ser = ser;
92 last = list_last_entry_or_null(&bs->blocks, struct kho_block, list);
93 list_add_tail(&block->list, &bs->blocks);
94 bs->nblocks++;
95
96 if (last)
97 last->ser->next = virt_to_phys(ser);
98 else
99 bs->head_pa = virt_to_phys(ser);
100
101 return 0;
102}
103
104static int kho_block_set_grow_one(struct kho_block_set *bs)
105{
106 struct kho_block_header_ser *ser;
107 int err;
108
109 ser = kho_block_alloc_ser(bs);
110 if (IS_ERR(ser))
111 return PTR_ERR(ser);
112
113 err = kho_block_add(bs, ser);
114 if (err) {
115 kho_block_free_ser(bs, ser);
116 return err;
117 }
118
119 return 0;
120}
121
122static void kho_block_set_shrink_one(struct kho_block_set *bs)
123{
124 struct kho_block *last, *new_last;
125
126 if (list_empty(&bs->blocks))
127 return;
128
129 last = list_last_entry(&bs->blocks, struct kho_block, list);
130 list_del(&last->list);
131 bs->nblocks--;
132 kho_block_free_ser(bs, last->ser);
133 kfree(last);
134
135 new_last = list_last_entry_or_null(&bs->blocks, struct kho_block, list);
136 if (new_last)
137 new_last->ser->next = 0;
138 else
139 bs->head_pa = 0;
140}
141
142/**
143 * kho_block_set_grow - Expand the block set to accommodate the target count.
144 * @bs: The block set.
145 * @count: The target number of valid entries to accommodate.
146 *
147 * Dynamically preallocates and links preserved memory blocks if the target
148 * entry count exceeds the current total capacity of the set, ensuring they
149 * are available during serialization/deserialization.
150 *
151 * Context: Caller must hold a lock protecting the block set.
152 * Return: 0 on success, or a negative errno on failure.
153 */
154int kho_block_set_grow(struct kho_block_set *bs, u64 count)
155{
156 long orig_nblocks = bs->nblocks;
157 int err;
158
159 if (WARN_ON_ONCE(bs->incoming))
160 return -EINVAL;
161
162 while (count > bs->nblocks * bs->count_per_block) {
163 err = kho_block_set_grow_one(bs);
164 if (err)
165 goto err_shrink;
166 }
167
168 return 0;
169
170err_shrink:
171 while (bs->nblocks > orig_nblocks)
172 kho_block_set_shrink_one(bs);
173 return err;
174}
175
176/**
177 * kho_block_set_shrink - Shrink the block set to accommodate the target count.
178 * @bs: The block set.
179 * @count: The target number of valid entries to accommodate.
180 *
181 * Releases and unallocates redundant preserved memory blocks. Checks if the
182 * last block in the set can be removed because the remaining entry count is
183 * fully accommodated by the preceding blocks.
184 *
185 * Note: It is the caller's responsibility to ensure that entries are removed
186 * in the reverse order of their insertion. Because shrinking destroys the last
187 * block in the set, removing entries in any other order would corrupt active
188 * data.
189 *
190 * Context: Caller must hold a lock protecting the block set.
191 */
192void kho_block_set_shrink(struct kho_block_set *bs, u64 count)
193{
194 while (bs->nblocks > 0 && count <= (bs->nblocks - 1) * bs->count_per_block)
195 kho_block_set_shrink_one(bs);
196}
197
198/*
199 * kho_block_set_is_cyclic - Check for cycles in a linked list of blocks.
200 * Uses Floyd's cycle-finding algorithm to ensure sanity of the incoming list.
201 *
202 * Return: true if a cycle or corruption is detected, false otherwise.
203 */
204static bool kho_block_set_is_cyclic(struct kho_block_set *bs)
205{
206 struct kho_block_header_ser *fast;
207 struct kho_block_header_ser *slow;
208 int count = 0;
209
210 fast = phys_to_virt(bs->head_pa);
211 slow = fast;
212
213 while (fast) {
214 if (count++ >= KHO_MAX_BLOCKS) {
215 pr_err("Block set is corrupted\n");
216 return true;
217 }
218
219 if (!fast->next)
220 break;
221
222 fast = phys_to_virt(fast->next);
223 if (!fast->next)
224 break;
225
226 fast = phys_to_virt(fast->next);
227 slow = phys_to_virt(slow->next);
228
229 if (slow == fast) {
230 pr_err("Block set is corrupted\n");
231 return true;
232 }
233 }
234
235 return false;
236}
237
238/**
239 * kho_block_set_restore - Restore a block set from a physical address.
240 * @bs: The block set to restore.
241 * @head_pa: Physical address of the first block header.
242 *
243 * Restores a serialized block set from a given physical address. The caller is
244 * responsible for ensuring that the block set @bs has been allocated and
245 * initialized prior to calling this function.
246 *
247 * Return: 0 on success, or a negative errno on failure.
248 */
249int kho_block_set_restore(struct kho_block_set *bs, u64 head_pa)
250{
251 struct kho_block_header_ser *ser;
252 u64 next_pa = head_pa;
253 int err;
254
255 /* Restored block sets use size from the previous kernel */
256 bs->incoming = true;
257 if (!head_pa)
258 return 0;
259
260 bs->head_pa = head_pa;
261 if (kho_block_set_is_cyclic(bs)) {
262 bs->head_pa = 0;
263 return -EINVAL;
264 }
265
266 while (next_pa) {
267 ser = phys_to_virt(next_pa);
268 if (!ser->count || ser->count > bs->count_per_block) {
269 pr_warn("Block contains invalid entry count: %llu\n",
270 ser->count);
271 err = -EINVAL;
272 goto err_destroy;
273 }
274 err = kho_block_add(bs, ser);
275 if (err)
276 goto err_destroy;
277 next_pa = ser->next;
278 }
279
280 return 0;
281
282err_destroy:
283 kho_block_set_destroy(bs);
284
285 /* Free the remaining un-restored blocks in the physical chain */
286 while (next_pa) {
287 struct kho_block_header_ser *next_ser = phys_to_virt(next_pa);
288
289 next_pa = next_ser->next;
290 kho_block_free_ser(bs, next_ser);
291 }
292 return err;
293}
294
295/**
296 * kho_block_set_destroy - Destroy all blocks in a block set.
297 * @bs: The block set.
298 */
299void kho_block_set_destroy(struct kho_block_set *bs)
300{
301 struct kho_block *block, *tmp;
302
303 list_for_each_entry_safe(block, tmp, &bs->blocks, list) {
304 list_del(&block->list);
305 kho_block_free_ser(bs, block->ser);
306 kfree(block);
307 }
308 bs->nblocks = 0;
309 bs->head_pa = 0;
310}
311
312/**
313 * kho_block_set_clear - Clear all serialized data in a block set.
314 * @bs: The block set to clear.
315 */
316void kho_block_set_clear(struct kho_block_set *bs)
317{
318 struct kho_block *block;
319
320 list_for_each_entry(block, &bs->blocks, list) {
321 block->ser->count = 0;
322 memset(block->ser + 1, 0, KHO_BLOCK_SIZE - sizeof(*block->ser));
323 }
324}
325
326/**
327 * kho_block_set_it_init - Initialize a block set iterator.
328 * @it: The iterator to initialize.
329 * @bs: The block set to iterate over.
330 */
331void kho_block_set_it_init(struct kho_block_set_it *it, struct kho_block_set *bs)
332{
333 it->bs = bs;
334 it->block = list_first_entry_or_null(&bs->blocks, struct kho_block, list);
335 it->i = 0;
336}
337
338/**
339 * kho_block_set_it_reserve_entry - Reserve and return the next available slot for writing.
340 * @it: The block iterator.
341 *
342 * Reserves a slot in the current block during state serialization to add a new
343 * entry, advancing the internal index. If the current block is full, it
344 * automatically moves to the next block in the set.
345 *
346 * Return: A pointer to the reserved entry slot, or NULL if the block set's
347 * capacity is fully exhausted.
348 */
349void *kho_block_set_it_reserve_entry(struct kho_block_set_it *it)
350{
351 void *entry;
352
353 if (!it->block)
354 return NULL;
355
356 if (it->i == it->bs->count_per_block) {
357 if (list_is_last(&it->block->list, &it->bs->blocks))
358 return NULL;
359 it->block = list_next_entry(it->block, list);
360 it->i = 0;
361 }
362
363 entry = kho_block_entry(it, it->i++);
364 it->block->ser->count = it->i;
365 return entry;
366}
367
368/**
369 * kho_block_set_it_read_entry - Read the next serialized entry from the block set.
370 * @it: The block iterator.
371 *
372 * Iterates through previously written entries during state deserialization,
373 * respecting the actual count stored in each block's header.
374 *
375 * Return: A pointer to the next serialized entry, or NULL if all serialized
376 * entries have been read.
377 */
378void *kho_block_set_it_read_entry(struct kho_block_set_it *it)
379{
380 if (!it->block)
381 return NULL;
382
383 if (it->i == it->block->ser->count) {
384 if (list_is_last(&it->block->list, &it->bs->blocks))
385 return NULL;
386 it->block = list_next_entry(it->block, list);
387 it->i = 0;
388 }
389
390 return kho_block_entry(it, it->i++);
391}
392
393/**
394 * kho_block_set_it_prev - Return the previous entry slot in the block set.
395 * @it: The block iterator.
396 *
397 * If the current index is at the start of a block, it automatically moves to
398 * the end of the previous block.
399 *
400 * Return: A pointer to the previous entry slot, or NULL if at the very
401 * beginning of the block set.
402 */
403void *kho_block_set_it_prev(struct kho_block_set_it *it)
404{
405 if (!it->block)
406 return NULL;
407
408 if (it->i == 0) {
409 if (list_is_first(&it->block->list, &it->bs->blocks))
410 return NULL;
411 it->block = list_prev_entry(it->block, list);
412 it->i = it->bs->count_per_block;
413 }
414
415 return kho_block_entry(it, --it->i);
416}