/* SPDX-License-Identifier: GPL-2.0-only */ /* * Copyright (c) 2024-2025, NVIDIA CORPORATION & AFFILIATES * * Iterators for Generic Page Table */ #ifndef __GENERIC_PT_PT_ITER_H #define __GENERIC_PT_PT_ITER_H #include "pt_common.h" #include /* * Use to mangle symbols so that backtraces and the symbol table are * understandable. Any non-inlined function should get mangled like this. */ #define NS(fn) CONCATENATE(PTPFX, fn) /** * pt_check_range() - Validate the range can be iterated * @range: Range to validate * * Check that VA and last_va fall within the permitted range of VAs. If the * format is using PT_FEAT_SIGN_EXTEND then this also checks the sign extension * is correct. */ static inline int pt_check_range(struct pt_range *range) { pt_vaddr_t prefix; PT_WARN_ON(!range->max_vasz_lg2); if (pt_feature(range->common, PT_FEAT_SIGN_EXTEND)) { PT_WARN_ON(range->common->max_vasz_lg2 != range->max_vasz_lg2); prefix = fvalog2_div(range->va, range->max_vasz_lg2 - 1) ? PT_VADDR_MAX : 0; } else { prefix = pt_full_va_prefix(range->common); } if (!fvalog2_div_eq(range->va, prefix, range->max_vasz_lg2) || !fvalog2_div_eq(range->last_va, prefix, range->max_vasz_lg2)) return -ERANGE; return 0; } /** * pt_index_to_va() - Update range->va to the current pts->index * @pts: Iteration State * * Adjust range->va to match the current index. This is done in a lazy manner * since computing the VA takes several instructions and is rarely required. */ static inline void pt_index_to_va(struct pt_state *pts) { pt_vaddr_t lower_va; lower_va = log2_mul(pts->index, pt_table_item_lg2sz(pts)); pts->range->va = fvalog2_set_mod(pts->range->va, lower_va, pt_table_oa_lg2sz(pts)); } /* * Add index_count_lg2 number of entries to pts's VA and index. The VA will be * adjusted to the end of the contiguous block if it is currently in the middle. */ static inline void _pt_advance(struct pt_state *pts, unsigned int index_count_lg2) { pts->index = log2_set_mod(pts->index + log2_to_int(index_count_lg2), 0, index_count_lg2); } /** * pt_entry_fully_covered() - Check if the item or entry is entirely contained * within pts->range * @pts: Iteration State * @oasz_lg2: The size of the item to check, pt_table_item_lg2sz() or * pt_entry_oa_lg2sz() * * Returns: true if the item is fully enclosed by the pts->range. */ static inline bool pt_entry_fully_covered(const struct pt_state *pts, unsigned int oasz_lg2) { struct pt_range *range = pts->range; /* Range begins at the start of the entry */ if (log2_mod(pts->range->va, oasz_lg2)) return false; /* Range ends past the end of the entry */ if (!log2_div_eq(range->va, range->last_va, oasz_lg2)) return true; /* Range ends at the end of the entry */ return log2_mod_eq_max(range->last_va, oasz_lg2); } /** * pt_range_to_index() - Starting index for an iteration * @pts: Iteration State * * Return: the starting index for the iteration in pts. */ static inline unsigned int pt_range_to_index(const struct pt_state *pts) { unsigned int isz_lg2 = pt_table_item_lg2sz(pts); PT_WARN_ON(pts->level > pts->range->top_level); if (pts->range->top_level == pts->level) return log2_div(fvalog2_mod(pts->range->va, pts->range->max_vasz_lg2), isz_lg2); return log2_mod(log2_div(pts->range->va, isz_lg2), pt_num_items_lg2(pts)); } /** * pt_range_to_end_index() - Ending index iteration * @pts: Iteration State * * Return: the last index for the iteration in pts. */ static inline unsigned int pt_range_to_end_index(const struct pt_state *pts) { unsigned int isz_lg2 = pt_table_item_lg2sz(pts); struct pt_range *range = pts->range; unsigned int num_entries_lg2; if (range->va == range->last_va) return pts->index + 1; if (pts->range->top_level == pts->level) return log2_div(fvalog2_mod(pts->range->last_va, pts->range->max_vasz_lg2), isz_lg2) + 1; num_entries_lg2 = pt_num_items_lg2(pts); /* last_va falls within this table */ if (log2_div_eq(range->va, range->last_va, num_entries_lg2 + isz_lg2)) return log2_mod(log2_div(pts->range->last_va, isz_lg2), num_entries_lg2) + 1; return log2_to_int(num_entries_lg2); } static inline void _pt_iter_first(struct pt_state *pts) { pts->index = pt_range_to_index(pts); pts->end_index = pt_range_to_end_index(pts); PT_WARN_ON(pts->index > pts->end_index); } static inline bool _pt_iter_load(struct pt_state *pts) { if (pts->index >= pts->end_index) return false; pt_load_entry(pts); return true; } /** * pt_next_entry() - Advance pts to the next entry * @pts: Iteration State * * Update pts to go to the next index at this level. If pts is pointing at a * contiguous entry then the index may advance my more than one. */ static inline void pt_next_entry(struct pt_state *pts) { if (pts->type == PT_ENTRY_OA && !__builtin_constant_p(pt_entry_num_contig_lg2(pts) == 0)) _pt_advance(pts, pt_entry_num_contig_lg2(pts)); else pts->index++; pt_index_to_va(pts); } /** * for_each_pt_level_entry() - For loop wrapper over entries in the range * @pts: Iteration State * * This is the basic iteration primitive. It iterates over all the entries in * pts->range that fall within the pts's current table level. Each step does * pt_load_entry(pts). */ #define for_each_pt_level_entry(pts) \ for (_pt_iter_first(pts); _pt_iter_load(pts); pt_next_entry(pts)) /** * pt_load_single_entry() - Version of pt_load_entry() usable within a walker * @pts: Iteration State * * Alternative to for_each_pt_level_entry() if the walker function uses only a * single entry. */ static inline enum pt_entry_type pt_load_single_entry(struct pt_state *pts) { pts->index = pt_range_to_index(pts); pt_load_entry(pts); return pts->type; } static __always_inline struct pt_range _pt_top_range(struct pt_common *common, uintptr_t top_of_table) { struct pt_range range = { .common = common, .top_table = (struct pt_table_p *)(top_of_table & ~(uintptr_t)PT_TOP_LEVEL_MASK), .top_level = top_of_table % (1 << PT_TOP_LEVEL_BITS), }; struct pt_state pts = { .range = &range, .level = range.top_level }; unsigned int max_vasz_lg2; max_vasz_lg2 = common->max_vasz_lg2; if (pt_feature(common, PT_FEAT_DYNAMIC_TOP) && pts.level != PT_MAX_TOP_LEVEL) max_vasz_lg2 = min_t(unsigned int, common->max_vasz_lg2, pt_num_items_lg2(&pts) + pt_table_item_lg2sz(&pts)); /* * The top range will default to the lower region only with sign extend. */ range.max_vasz_lg2 = max_vasz_lg2; if (pt_feature(common, PT_FEAT_SIGN_EXTEND)) max_vasz_lg2--; range.va = fvalog2_set_mod(pt_full_va_prefix(common), 0, max_vasz_lg2); range.last_va = fvalog2_set_mod_max(pt_full_va_prefix(common), max_vasz_lg2); return range; } /** * pt_top_range() - Return a range that spans part of the top level * @common: Table * * For PT_FEAT_SIGN_EXTEND this will return the lower range, and cover half the * total page table. Otherwise it returns the entire page table. */ static __always_inline struct pt_range pt_top_range(struct pt_common *common) { /* * The top pointer can change without locking. We capture the value and * it's level here and are safe to walk it so long as both values are * captured without tearing. */ return _pt_top_range(common, READ_ONCE(common->top_of_table)); } /** * pt_all_range() - Return a range that spans the entire page table * @common: Table * * The returned range spans the whole page table. Due to how PT_FEAT_SIGN_EXTEND * is supported range->va and range->last_va will be incorrect during the * iteration and must not be accessed. */ static inline struct pt_range pt_all_range(struct pt_common *common) { struct pt_range range = pt_top_range(common); if (!pt_feature(common, PT_FEAT_SIGN_EXTEND)) return range; /* * Pretend the table is linear from 0 without a sign extension. This * generates the correct indexes for iteration. */ range.last_va = fvalog2_set_mod_max(0, range.max_vasz_lg2); return range; } /** * pt_upper_range() - Return a range that spans part of the top level * @common: Table * * For PT_FEAT_SIGN_EXTEND this will return the upper range, and cover half the * total page table. Otherwise it returns the entire page table. */ static inline struct pt_range pt_upper_range(struct pt_common *common) { struct pt_range range = pt_top_range(common); if (!pt_feature(common, PT_FEAT_SIGN_EXTEND)) return range; range.va = fvalog2_set_mod(PT_VADDR_MAX, 0, range.max_vasz_lg2 - 1); range.last_va = PT_VADDR_MAX; return range; } /** * pt_make_range() - Return a range that spans part of the table * @common: Table * @va: Start address * @last_va: Last address * * The caller must validate the range with pt_check_range() before using it. */ static __always_inline struct pt_range pt_make_range(struct pt_common *common, pt_vaddr_t va, pt_vaddr_t last_va) { struct pt_range range = _pt_top_range(common, READ_ONCE(common->top_of_table)); range.va = va; range.last_va = last_va; return range; } /* * Span a slice of the table starting at a lower table level from an active * walk. */ static __always_inline struct pt_range pt_make_child_range(const struct pt_range *parent, pt_vaddr_t va, pt_vaddr_t last_va) { struct pt_range range = *parent; range.va = va; range.last_va = last_va; PT_WARN_ON(last_va < va); PT_WARN_ON(pt_check_range(&range)); return range; } /** * pt_init() - Initialize a pt_state on the stack * @range: Range pointer to embed in the state * @level: Table level for the state * @table: Pointer to the table memory at level * * Helper to initialize the on-stack pt_state from walker arguments. */ static __always_inline struct pt_state pt_init(struct pt_range *range, unsigned int level, struct pt_table_p *table) { struct pt_state pts = { .range = range, .table = table, .level = level, }; return pts; } /** * pt_init_top() - Initialize a pt_state on the stack * @range: Range pointer to embed in the state * * The pt_state points to the top most level. */ static __always_inline struct pt_state pt_init_top(struct pt_range *range) { return pt_init(range, range->top_level, range->top_table); } typedef int (*pt_level_fn_t)(struct pt_range *range, void *arg, unsigned int level, struct pt_table_p *table); /** * pt_descend() - Recursively invoke the walker for the lower level * @pts: Iteration State * @arg: Value to pass to the function * @fn: Walker function to call * * pts must point to a table item. Invoke fn as a walker on the table * pts points to. */ static __always_inline int pt_descend(struct pt_state *pts, void *arg, pt_level_fn_t fn) { int ret; if (PT_WARN_ON(!pts->table_lower)) return -EINVAL; ret = (*fn)(pts->range, arg, pts->level - 1, pts->table_lower); return ret; } /** * pt_walk_range() - Walk over a VA range * @range: Range pointer * @fn: Walker function to call * @arg: Value to pass to the function * * Walk over a VA range. The caller should have done a validity check, at * least calling pt_check_range(), when building range. The walk will * start at the top most table. */ static __always_inline int pt_walk_range(struct pt_range *range, pt_level_fn_t fn, void *arg) { return fn(range, arg, range->top_level, range->top_table); } /* * pt_walk_descend() - Recursively invoke the walker for a slice of a lower * level * @pts: Iteration State * @va: Start address * @last_va: Last address * @fn: Walker function to call * @arg: Value to pass to the function * * With pts pointing at a table item this will descend and over a slice of the * lower table. The caller must ensure that va/last_va are within the table * item. This creates a new walk and does not alter pts or pts->range. */ static __always_inline int pt_walk_descend(const struct pt_state *pts, pt_vaddr_t va, pt_vaddr_t last_va, pt_level_fn_t fn, void *arg) { struct pt_range range = pt_make_child_range(pts->range, va, last_va); if (PT_WARN_ON(!pt_can_have_table(pts)) || PT_WARN_ON(!pts->table_lower)) return -EINVAL; return fn(&range, arg, pts->level - 1, pts->table_lower); } /* * pt_walk_descend_all() - Recursively invoke the walker for a table item * @parent_pts: Iteration State * @fn: Walker function to call * @arg: Value to pass to the function * * With pts pointing at a table item this will descend and over the entire lower * table. This creates a new walk and does not alter pts or pts->range. */ static __always_inline int pt_walk_descend_all(const struct pt_state *parent_pts, pt_level_fn_t fn, void *arg) { unsigned int isz_lg2 = pt_table_item_lg2sz(parent_pts); return pt_walk_descend(parent_pts, log2_set_mod(parent_pts->range->va, 0, isz_lg2), log2_set_mod_max(parent_pts->range->va, isz_lg2), fn, arg); } /** * pt_range_slice() - Return a range that spans indexes * @pts: Iteration State * @start_index: Starting index within pts * @end_index: Ending index within pts * * Create a range than spans an index range of the current table level * pt_state points at. */ static inline struct pt_range pt_range_slice(const struct pt_state *pts, unsigned int start_index, unsigned int end_index) { unsigned int table_lg2sz = pt_table_oa_lg2sz(pts); pt_vaddr_t last_va; pt_vaddr_t va; va = fvalog2_set_mod(pts->range->va, log2_mul(start_index, pt_table_item_lg2sz(pts)), table_lg2sz); last_va = fvalog2_set_mod( pts->range->va, log2_mul(end_index, pt_table_item_lg2sz(pts)) - 1, table_lg2sz); return pt_make_child_range(pts->range, va, last_va); } /** * pt_top_memsize_lg2() * @common: Table * @top_of_table: Top of table value from _pt_top_set() * * Compute the allocation size of the top table. For PT_FEAT_DYNAMIC_TOP this * will compute the top size assuming the table will grow. */ static inline unsigned int pt_top_memsize_lg2(struct pt_common *common, uintptr_t top_of_table) { struct pt_range range = _pt_top_range(common, top_of_table); struct pt_state pts = pt_init_top(&range); unsigned int num_items_lg2; num_items_lg2 = common->max_vasz_lg2 - pt_table_item_lg2sz(&pts); if (range.top_level != PT_MAX_TOP_LEVEL && pt_feature(common, PT_FEAT_DYNAMIC_TOP)) num_items_lg2 = min(num_items_lg2, pt_num_items_lg2(&pts)); /* Round up the allocation size to the minimum alignment */ return max(ffs_t(u64, PT_TOP_PHYS_MASK), num_items_lg2 + ilog2(PT_ITEM_WORD_SIZE)); } /** * pt_compute_best_pgsize() - Determine the best page size for leaf entries * @pgsz_bitmap: Permitted page sizes * @va: Starting virtual address for the leaf entry * @last_va: Last virtual address for the leaf entry, sets the max page size * @oa: Starting output address for the leaf entry * * Compute the largest page size for va, last_va, and oa together and return it * in lg2. The largest page size depends on the format's supported page sizes at * this level, and the relative alignment of the VA and OA addresses. 0 means * the OA cannot be stored with the provided pgsz_bitmap. */ static inline unsigned int pt_compute_best_pgsize(pt_vaddr_t pgsz_bitmap, pt_vaddr_t va, pt_vaddr_t last_va, pt_oaddr_t oa) { unsigned int best_pgsz_lg2; unsigned int pgsz_lg2; pt_vaddr_t len = last_va - va + 1; pt_vaddr_t mask; if (PT_WARN_ON(va >= last_va)) return 0; /* * Given a VA/OA pair the best page size is the largest page size * where: * * 1) VA and OA start at the page. Bitwise this is the count of least * significant 0 bits. * This also implies that last_va/oa has the same prefix as va/oa. */ mask = va | oa; /* * 2) The page size is not larger than the last_va (length). Since page * sizes are always power of two this can't be larger than the * largest power of two factor of the length. */ mask |= log2_to_int(vafls(len) - 1); best_pgsz_lg2 = vaffs(mask); /* Choose the highest bit <= best_pgsz_lg2 */ if (best_pgsz_lg2 < PT_VADDR_MAX_LG2 - 1) pgsz_bitmap = log2_mod(pgsz_bitmap, best_pgsz_lg2 + 1); pgsz_lg2 = vafls(pgsz_bitmap); if (!pgsz_lg2) return 0; pgsz_lg2--; PT_WARN_ON(log2_mod(va, pgsz_lg2) != 0); PT_WARN_ON(oalog2_mod(oa, pgsz_lg2) != 0); PT_WARN_ON(va + log2_to_int(pgsz_lg2) - 1 > last_va); PT_WARN_ON(!log2_div_eq(va, va + log2_to_int(pgsz_lg2) - 1, pgsz_lg2)); PT_WARN_ON( !oalog2_div_eq(oa, oa + log2_to_int(pgsz_lg2) - 1, pgsz_lg2)); return pgsz_lg2; } #define _PT_MAKE_CALL_LEVEL(fn) \ static __always_inline int fn(struct pt_range *range, void *arg, \ unsigned int level, \ struct pt_table_p *table) \ { \ static_assert(PT_MAX_TOP_LEVEL <= 5); \ if (level == 0) \ return CONCATENATE(fn, 0)(range, arg, 0, table); \ if (level == 1 || PT_MAX_TOP_LEVEL == 1) \ return CONCATENATE(fn, 1)(range, arg, 1, table); \ if (level == 2 || PT_MAX_TOP_LEVEL == 2) \ return CONCATENATE(fn, 2)(range, arg, 2, table); \ if (level == 3 || PT_MAX_TOP_LEVEL == 3) \ return CONCATENATE(fn, 3)(range, arg, 3, table); \ if (level == 4 || PT_MAX_TOP_LEVEL == 4) \ return CONCATENATE(fn, 4)(range, arg, 4, table); \ return CONCATENATE(fn, 5)(range, arg, 5, table); \ } static inline int __pt_make_level_fn_err(struct pt_range *range, void *arg, unsigned int unused_level, struct pt_table_p *table) { static_assert(PT_MAX_TOP_LEVEL <= 5); return -EPROTOTYPE; } #define __PT_MAKE_LEVEL_FN(fn, level, descend_fn, do_fn) \ static inline int fn(struct pt_range *range, void *arg, \ unsigned int unused_level, \ struct pt_table_p *table) \ { \ return do_fn(range, arg, level, table, descend_fn); \ } /** * PT_MAKE_LEVELS() - Build an unwound walker * @fn: Name of the walker function * @do_fn: Function to call at each level * * This builds a function call tree that can be fully inlined. * The caller must provide a function body in an __always_inline function:: * * static __always_inline int do_fn(struct pt_range *range, void *arg, * unsigned int level, struct pt_table_p *table, * pt_level_fn_t descend_fn) * * An inline function will be created for each table level that calls do_fn with * a compile time constant for level and a pointer to the next lower function. * This generates an optimally inlined walk where each of the functions sees a * constant level and can codegen the exact constants/etc for that level. * * Note this can produce a lot of code! */ #define PT_MAKE_LEVELS(fn, do_fn) \ __PT_MAKE_LEVEL_FN(CONCATENATE(fn, 0), 0, __pt_make_level_fn_err, \ do_fn); \ __PT_MAKE_LEVEL_FN(CONCATENATE(fn, 1), 1, CONCATENATE(fn, 0), do_fn); \ __PT_MAKE_LEVEL_FN(CONCATENATE(fn, 2), 2, CONCATENATE(fn, 1), do_fn); \ __PT_MAKE_LEVEL_FN(CONCATENATE(fn, 3), 3, CONCATENATE(fn, 2), do_fn); \ __PT_MAKE_LEVEL_FN(CONCATENATE(fn, 4), 4, CONCATENATE(fn, 3), do_fn); \ __PT_MAKE_LEVEL_FN(CONCATENATE(fn, 5), 5, CONCATENATE(fn, 4), do_fn); \ _PT_MAKE_CALL_LEVEL(fn) #endif