LXR linux/mm/shuffle.c

   1// SPDX-License-Identifier: GPL-2.0
   2// Copyright(c) 2018 Intel Corporation. All rights reserved.
   3
   4#include <linux/mm.h>
   5#include <linux/init.h>
   6#include <linux/mmzone.h>
   7#include <linux/random.h>
   8#include <linux/moduleparam.h>
   9#include "internal.h"
  10#include "shuffle.h"
  11
  12DEFINE_STATIC_KEY_FALSE(page_alloc_shuffle_key);
  13static unsigned long shuffle_state __ro_after_init;
  14
  15/*
  16 * Depending on the architecture, module parameter parsing may run
  17 * before, or after the cache detection. SHUFFLE_FORCE_DISABLE prevents,
  18 * or reverts the enabling of the shuffle implementation. SHUFFLE_ENABLE
  19 * attempts to turn on the implementation, but aborts if it finds
  20 * SHUFFLE_FORCE_DISABLE already set.
  21 */
  22__meminit void page_alloc_shuffle(enum mm_shuffle_ctl ctl)
  23{
  24        if (ctl == SHUFFLE_FORCE_DISABLE)
  25                set_bit(SHUFFLE_FORCE_DISABLE, &shuffle_state);
  26
  27        if (test_bit(SHUFFLE_FORCE_DISABLE, &shuffle_state)) {
  28                if (test_and_clear_bit(SHUFFLE_ENABLE, &shuffle_state))
  29                        static_branch_disable(&page_alloc_shuffle_key);
  30        } else if (ctl == SHUFFLE_ENABLE
  31                        && !test_and_set_bit(SHUFFLE_ENABLE, &shuffle_state))
  32                static_branch_enable(&page_alloc_shuffle_key);
  33}
  34
  35static bool shuffle_param;
  36extern int shuffle_show(char *buffer, const struct kernel_param *kp)
  37{
  38        return sprintf(buffer, "%c\n", test_bit(SHUFFLE_ENABLE, &shuffle_state)
  39                        ? 'Y' : 'N');
  40}
  41
  42static __meminit int shuffle_store(const char *val,
  43                const struct kernel_param *kp)
  44{
  45        int rc = param_set_bool(val, kp);
  46
  47        if (rc < 0)
  48                return rc;
  49        if (shuffle_param)
  50                page_alloc_shuffle(SHUFFLE_ENABLE);
  51        else
  52                page_alloc_shuffle(SHUFFLE_FORCE_DISABLE);
  53        return 0;
  54}
  55module_param_call(shuffle, shuffle_store, shuffle_show, &shuffle_param, 0400);
  56
  57/*
  58 * For two pages to be swapped in the shuffle, they must be free (on a
  59 * 'free_area' lru), have the same order, and have the same migratetype.
  60 */
  61static struct page * __meminit shuffle_valid_page(unsigned long pfn, int order)
  62{
  63        struct page *page;
  64
  65        /*
  66         * Given we're dealing with randomly selected pfns in a zone we
  67         * need to ask questions like...
  68         */
  69
  70        /* ...is the pfn even in the memmap? */
  71        if (!pfn_valid_within(pfn))
  72                return NULL;
  73
  74        /* ...is the pfn in a present section or a hole? */
  75        if (!pfn_present(pfn))
  76                return NULL;
  77
  78        /* ...is the page free and currently on a free_area list? */
  79        page = pfn_to_page(pfn);
  80        if (!PageBuddy(page))
  81                return NULL;
  82
  83        /*
  84         * ...is the page on the same list as the page we will
  85         * shuffle it with?
  86         */
  87        if (page_order(page) != order)
  88                return NULL;
  89
  90        return page;
  91}
  92
  93/*
  94 * Fisher-Yates shuffle the freelist which prescribes iterating through an
  95 * array, pfns in this case, and randomly swapping each entry with another in
  96 * the span, end_pfn - start_pfn.
  97 *
  98 * To keep the implementation simple it does not attempt to correct for sources
  99 * of bias in the distribution, like modulo bias or pseudo-random number
 100 * generator bias. I.e. the expectation is that this shuffling raises the bar
 101 * for attacks that exploit the predictability of page allocations, but need not
 102 * be a perfect shuffle.
 103 */
 104#define SHUFFLE_RETRY 10
 105void __meminit __shuffle_zone(struct zone *z)
 106{
 107        unsigned long i, flags;
 108        unsigned long start_pfn = z->zone_start_pfn;
 109        unsigned long end_pfn = zone_end_pfn(z);
 110        const int order = SHUFFLE_ORDER;
 111        const int order_pages = 1 << order;
 112
 113        spin_lock_irqsave(&z->lock, flags);
 114        start_pfn = ALIGN(start_pfn, order_pages);
 115        for (i = start_pfn; i < end_pfn; i += order_pages) {
 116                unsigned long j;
 117                int migratetype, retry;
 118                struct page *page_i, *page_j;
 119
 120                /*
 121                 * We expect page_i, in the sub-range of a zone being added
 122                 * (@start_pfn to @end_pfn), to more likely be valid compared to
 123                 * page_j randomly selected in the span @zone_start_pfn to
 124                 * @spanned_pages.
 125                 */
 126                page_i = shuffle_valid_page(i, order);
 127                if (!page_i)
 128                        continue;
 129
 130                for (retry = 0; retry < SHUFFLE_RETRY; retry++) {
 131                        /*
 132                         * Pick a random order aligned page in the zone span as
 133                         * a swap target. If the selected pfn is a hole, retry
 134                         * up to SHUFFLE_RETRY attempts find a random valid pfn
 135                         * in the zone.
 136                         */
 137                        j = z->zone_start_pfn +
 138                                ALIGN_DOWN(get_random_long() % z->spanned_pages,
 139                                                order_pages);
 140                        page_j = shuffle_valid_page(j, order);
 141                        if (page_j && page_j != page_i)
 142                                break;
 143                }
 144                if (retry >= SHUFFLE_RETRY) {
 145                        pr_debug("%s: failed to swap %#lx\n", __func__, i);
 146                        continue;
 147                }
 148
 149                /*
 150                 * Each migratetype corresponds to its own list, make sure the
 151                 * types match otherwise we're moving pages to lists where they
 152                 * do not belong.
 153                 */
 154                migratetype = get_pageblock_migratetype(page_i);
 155                if (get_pageblock_migratetype(page_j) != migratetype) {
 156                        pr_debug("%s: migratetype mismatch %#lx\n", __func__, i);
 157                        continue;
 158                }
 159
 160                list_swap(&page_i->lru, &page_j->lru);
 161
 162                pr_debug("%s: swap: %#lx -> %#lx\n", __func__, i, j);
 163
 164                /* take it easy on the zone lock */
 165                if ((i % (100 * order_pages)) == 0) {
 166                        spin_unlock_irqrestore(&z->lock, flags);
 167                        cond_resched();
 168                        spin_lock_irqsave(&z->lock, flags);
 169                }
 170        }
 171        spin_unlock_irqrestore(&z->lock, flags);
 172}
 173
 174/**
 175 * shuffle_free_memory - reduce the predictability of the page allocator
 176 * @pgdat: node page data
 177 */
 178void __meminit __shuffle_free_memory(pg_data_t *pgdat)
 179{
 180        struct zone *z;
 181
 182        for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
 183                shuffle_zone(z);
 184}
 185
 186void add_to_free_area_random(struct page *page, struct free_area *area,
 187                int migratetype)
 188{
 189        static u64 rand;
 190        static u8 rand_bits;
 191
 192        /*
 193         * The lack of locking is deliberate. If 2 threads race to
 194         * update the rand state it just adds to the entropy.
 195         */
 196        if (rand_bits == 0) {
 197                rand_bits = 64;
 198                rand = get_random_u64();
 199        }
 200
 201        if (rand & 1)
 202                add_to_free_area(page, area, migratetype);
 203        else
 204                add_to_free_area_tail(page, area, migratetype);
 205        rand_bits--;
 206        rand >>= 1;
 207}
 208