@@ -0,0 +1,110 @@
+#ifndef __ASM_X86_PT_CONTIG_MARKERS_H
+#define __ASM_X86_PT_CONTIG_MARKERS_H
+
+/*
+ * Short of having function templates in C, the function defined below is
+ * intended to be used by multiple parties interested in recording the
+ * degree of contiguity in mappings by a single page table.
+ *
+ * Scheme: Every entry records the order of contiguous successive entries,
+ * up to the maximum order covered by that entry (which is the number of
+ * clear low bits in its index, with entry 0 being the exception using
+ * the base-2 logarithm of the number of entries in a single page table).
+ * While a few entries need touching upon update, knowing whether the
+ * table is fully contiguous (and can hence be replaced by a higher level
+ * leaf entry) is then possible by simply looking at entry 0's marker.
+ *
+ * Prereqs:
+ * - CONTIG_MASK needs to be #define-d, to a value having at least 4
+ * contiguous bits (ignored by hardware), before including this file (or
+ * else only CONTIG_LEVEL_SHIFT and CONTIG_NR will become available),
+ * - page tables to be passed to the helper need to be initialized with
+ * correct markers,
+ * - not-present entries need to be entirely clear except for the marker.
+ */
+
+/* This is the same for all anticipated users, so doesn't need passing in. */
+#define CONTIG_LEVEL_SHIFT 9
+#define CONTIG_NR (1 << CONTIG_LEVEL_SHIFT)
+
+#ifdef CONTIG_MASK
+
+#include <xen/bitops.h>
+#include <xen/lib.h>
+#include <xen/page-size.h>
+
+#define GET_MARKER(e) MASK_EXTR(e, CONTIG_MASK)
+#define SET_MARKER(e, m) \
+ ((void)((e) = ((e) & ~CONTIG_MASK) | MASK_INSR(m, CONTIG_MASK)))
+
+#define IS_CONTIG(kind, pt, i, idx, shift, b) \
+ ((kind) == PTE_kind_leaf \
+ ? (((pt)[i] ^ (pt)[idx]) & ~CONTIG_MASK) == (1ULL << ((b) + (shift))) \
+ : !((pt)[i] & ~CONTIG_MASK))
+
+enum PTE_kind {
+ PTE_kind_null,
+ PTE_kind_leaf,
+ PTE_kind_table,
+};
+
+static bool pt_update_contig_markers(uint64_t *pt, unsigned int idx,
+ unsigned int level, enum PTE_kind kind)
+{
+ unsigned int b, i = idx;
+ unsigned int shift = (level - 1) * CONTIG_LEVEL_SHIFT + PAGE_SHIFT;
+
+ ASSERT(idx < CONTIG_NR);
+ ASSERT(!(pt[idx] & CONTIG_MASK));
+
+ /* Step 1: Reduce markers in lower numbered entries. */
+ while ( i )
+ {
+ b = find_first_set_bit(i);
+ i &= ~(1U << b);
+ if ( GET_MARKER(pt[i]) <= b )
+ break;
+ SET_MARKER(pt[i], b);
+ }
+
+ /* An intermediate table is never contiguous with anything. */
+ if ( kind == PTE_kind_table )
+ return false;
+
+ /*
+ * Present entries need in-sync index and address to be a candidate
+ * for being contiguous: What we're after is whether ultimately the
+ * intermediate table can be replaced by a superpage.
+ */
+ if ( kind != PTE_kind_null &&
+ idx != ((pt[idx] >> shift) & (CONTIG_NR - 1)) )
+ return false;
+
+ /* Step 2: Check higher numbered entries for contiguity. */
+ for ( b = 0; b < CONTIG_LEVEL_SHIFT && !(idx & (1U << b)); ++b )
+ {
+ i = idx | (1U << b);
+ if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) != b )
+ break;
+ }
+
+ /* Step 3: Update markers in this and lower numbered entries. */
+ for ( ; SET_MARKER(pt[idx], b), b < CONTIG_LEVEL_SHIFT; ++b )
+ {
+ i = idx ^ (1U << b);
+ if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) != b )
+ break;
+ idx &= ~(1U << b);
+ }
+
+ return b == CONTIG_LEVEL_SHIFT;
+}
+
+#undef IS_CONTIG
+#undef SET_MARKER
+#undef GET_MARKER
+#undef CONTIG_MASK
+
+#endif /* CONTIG_MASK */
+
+#endif /* __ASM_X86_PT_CONTIG_MARKERS_H */