1 #ifndef __ASM_X86_PT_CONTIG_MARKERS_H
2 #define __ASM_X86_PT_CONTIG_MARKERS_H
3
4 /*
5 * Short of having function templates in C, the function defined below is
6 * intended to be used by multiple parties interested in recording the
7 * degree of contiguity in mappings by a single page table.
8 *
9 * Scheme: Every entry records the order of contiguous successive entries,
10 * up to the maximum order covered by that entry (which is the number of
11 * clear low bits in its index, with entry 0 being the exception using
12 * the base-2 logarithm of the number of entries in a single page table).
13 * While a few entries need touching upon update, knowing whether the
14 * table is fully contiguous (and can hence be replaced by a higher level
15 * leaf entry) is then possible by simply looking at entry 0's marker.
16 *
17 * Prereqs:
18 * - CONTIG_MASK needs to be #define-d, to a value having at least 4
19 * contiguous bits (ignored by hardware), before including this file (or
20 * else only CONTIG_LEVEL_SHIFT and CONTIG_NR will become available),
21 * - page tables to be passed to the helper need to be initialized with
22 * correct markers,
23 * - not-present entries need to be entirely clear except for the marker.
24 */
25
26 /* This is the same for all anticipated users, so doesn't need passing in. */
27 #define CONTIG_LEVEL_SHIFT 9
28 #define CONTIG_NR (1 << CONTIG_LEVEL_SHIFT)
29
30 #ifdef CONTIG_MASK
31
32 #include <xen/bitops.h>
33 #include <xen/lib.h>
34 #include <xen/page-size.h>
35
36 #define GET_MARKER(e) MASK_EXTR(e, CONTIG_MASK)
37 #define SET_MARKER(e, m) \
38 ((void)((e) = ((e) & ~CONTIG_MASK) | MASK_INSR(m, CONTIG_MASK)))
39
40 #define IS_CONTIG(kind, pt, i, idx, shift, b) \
41 ((kind) == PTE_kind_leaf \
42 ? (((pt)[i] ^ (pt)[idx]) & ~CONTIG_MASK) == (1ULL << ((b) + (shift))) \
43 : !((pt)[i] & ~CONTIG_MASK))
44
45 enum PTE_kind {
46 PTE_kind_null,
47 PTE_kind_leaf,
48 PTE_kind_table,
49 };
50
pt_update_contig_markers(uint64_t * pt,unsigned int idx,unsigned int level,enum PTE_kind kind)51 static bool pt_update_contig_markers(uint64_t *pt, unsigned int idx,
52 unsigned int level, enum PTE_kind kind)
53 {
54 unsigned int b, i = idx;
55 unsigned int shift = (level - 1) * CONTIG_LEVEL_SHIFT + PAGE_SHIFT;
56
57 ASSERT(idx < CONTIG_NR);
58 ASSERT(!(pt[idx] & CONTIG_MASK));
59
60 /* Step 1: Reduce markers in lower numbered entries. */
61 while ( i )
62 {
63 b = ffs(i) - 1;
64 i &= ~(1U << b);
65 if ( GET_MARKER(pt[i]) <= b )
66 break;
67 SET_MARKER(pt[i], b);
68 }
69
70 /* An intermediate table is never contiguous with anything. */
71 if ( kind == PTE_kind_table )
72 return false;
73
74 /*
75 * Present entries need in-sync index and address to be a candidate
76 * for being contiguous: What we're after is whether ultimately the
77 * intermediate table can be replaced by a superpage.
78 */
79 if ( kind != PTE_kind_null &&
80 idx != ((pt[idx] >> shift) & (CONTIG_NR - 1)) )
81 return false;
82
83 /* Step 2: Check higher numbered entries for contiguity. */
84 for ( b = 0; b < CONTIG_LEVEL_SHIFT && !(idx & (1U << b)); ++b )
85 {
86 i = idx | (1U << b);
87 if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) != b )
88 break;
89 }
90
91 /* Step 3: Update markers in this and lower numbered entries. */
92 for ( ; SET_MARKER(pt[idx], b), b < CONTIG_LEVEL_SHIFT; ++b )
93 {
94 i = idx ^ (1U << b);
95 if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) != b )
96 break;
97 idx &= ~(1U << b);
98 }
99
100 return b == CONTIG_LEVEL_SHIFT;
101 }
102
103 #undef IS_CONTIG
104 #undef SET_MARKER
105 #undef GET_MARKER
106 #undef CONTIG_MASK
107
108 #endif /* CONTIG_MASK */
109
110 #endif /* __ASM_X86_PT_CONTIG_MARKERS_H */
111