the-tree/mm/shuffle.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 // Copyright(c) 2018 Intel Corporation. All rights reserved.
0003
0004 #include <linux/mm.h>
0005 #include <linux/init.h>
0006 #include <linux/mmzone.h>
0007 #include <linux/random.h>
0008 #include <linux/moduleparam.h>
0009 #include "internal.h"
0010 #include "shuffle.h"
0011
0012 DEFINE_STATIC_KEY_FALSE(page_alloc_shuffle_key);
0013
0014 static bool shuffle_param;
0015 static int shuffle_show(char *buffer, const struct kernel_param *kp)
0016 {
0017     return sprintf(buffer, "%c\n", shuffle_param ? 'Y' : 'N');
0018 }
0019
0020 static __meminit int shuffle_store(const char *val,
0021         const struct kernel_param *kp)
0022 {
0023     int rc = param_set_bool(val, kp);
0024
0025     if (rc < 0)
0026         return rc;
0027     if (shuffle_param)
0028         static_branch_enable(&page_alloc_shuffle_key);
0029     return 0;
0030 }
0031 module_param_call(shuffle, shuffle_store, shuffle_show, &shuffle_param, 0400);
0032
0033 /*
0034  * For two pages to be swapped in the shuffle, they must be free (on a
0035  * 'free_area' lru), have the same order, and have the same migratetype.
0036  */
0037 static struct page * __meminit shuffle_valid_page(struct zone *zone,
0038                           unsigned long pfn, int order)
0039 {
0040     struct page *page = pfn_to_online_page(pfn);
0041
0042     /*
0043      * Given we're dealing with randomly selected pfns in a zone we
0044      * need to ask questions like...
0045      */
0046
0047     /* ... is the page managed by the buddy? */
0048     if (!page)
0049         return NULL;
0050
0051     /* ... is the page assigned to the same zone? */
0052     if (page_zone(page) != zone)
0053         return NULL;
0054
0055     /* ...is the page free and currently on a free_area list? */
0056     if (!PageBuddy(page))
0057         return NULL;
0058
0059     /*
0060      * ...is the page on the same list as the page we will
0061      * shuffle it with?
0062      */
0063     if (buddy_order(page) != order)
0064         return NULL;
0065
0066     return page;
0067 }
0068
0069 /*
0070  * Fisher-Yates shuffle the freelist which prescribes iterating through an
0071  * array, pfns in this case, and randomly swapping each entry with another in
0072  * the span, end_pfn - start_pfn.
0073  *
0074  * To keep the implementation simple it does not attempt to correct for sources
0075  * of bias in the distribution, like modulo bias or pseudo-random number
0076  * generator bias. I.e. the expectation is that this shuffling raises the bar
0077  * for attacks that exploit the predictability of page allocations, but need not
0078  * be a perfect shuffle.
0079  */
0080 #define SHUFFLE_RETRY 10
0081 void __meminit __shuffle_zone(struct zone *z)
0082 {
0083     unsigned long i, flags;
0084     unsigned long start_pfn = z->zone_start_pfn;
0085     unsigned long end_pfn = zone_end_pfn(z);
0086     const int order = SHUFFLE_ORDER;
0087     const int order_pages = 1 << order;
0088
0089     spin_lock_irqsave(&z->lock, flags);
0090     start_pfn = ALIGN(start_pfn, order_pages);
0091     for (i = start_pfn; i < end_pfn; i += order_pages) {
0092         unsigned long j;
0093         int migratetype, retry;
0094         struct page *page_i, *page_j;
0095
0096         /*
0097          * We expect page_i, in the sub-range of a zone being added
0098          * (@start_pfn to @end_pfn), to more likely be valid compared to
0099          * page_j randomly selected in the span @zone_start_pfn to
0100          * @spanned_pages.
0101          */
0102         page_i = shuffle_valid_page(z, i, order);
0103         if (!page_i)
0104             continue;
0105
0106         for (retry = 0; retry < SHUFFLE_RETRY; retry++) {
0107             /*
0108              * Pick a random order aligned page in the zone span as
0109              * a swap target. If the selected pfn is a hole, retry
0110              * up to SHUFFLE_RETRY attempts find a random valid pfn
0111              * in the zone.
0112              */
0113             j = z->zone_start_pfn +
0114                 ALIGN_DOWN(get_random_long() % z->spanned_pages,
0115                         order_pages);
0116             page_j = shuffle_valid_page(z, j, order);
0117             if (page_j && page_j != page_i)
0118                 break;
0119         }
0120         if (retry >= SHUFFLE_RETRY) {
0121             pr_debug("%s: failed to swap %#lx\n", __func__, i);
0122             continue;
0123         }
0124
0125         /*
0126          * Each migratetype corresponds to its own list, make sure the
0127          * types match otherwise we're moving pages to lists where they
0128          * do not belong.
0129          */
0130         migratetype = get_pageblock_migratetype(page_i);
0131         if (get_pageblock_migratetype(page_j) != migratetype) {
0132             pr_debug("%s: migratetype mismatch %#lx\n", __func__, i);
0133             continue;
0134         }
0135
0136         list_swap(&page_i->lru, &page_j->lru);
0137
0138         pr_debug("%s: swap: %#lx -> %#lx\n", __func__, i, j);
0139
0140         /* take it easy on the zone lock */
0141         if ((i % (100 * order_pages)) == 0) {
0142             spin_unlock_irqrestore(&z->lock, flags);
0143             cond_resched();
0144             spin_lock_irqsave(&z->lock, flags);
0145         }
0146     }
0147     spin_unlock_irqrestore(&z->lock, flags);
0148 }
0149
0150 /*
0151  * __shuffle_free_memory - reduce the predictability of the page allocator
0152  * @pgdat: node page data
0153  */
0154 void __meminit __shuffle_free_memory(pg_data_t *pgdat)
0155 {
0156     struct zone *z;
0157
0158     for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
0159         shuffle_zone(z);
0160 }
0161
0162 bool shuffle_pick_tail(void)
0163 {
0164     static u64 rand;
0165     static u8 rand_bits;
0166     bool ret;
0167
0168     /*
0169      * The lack of locking is deliberate. If 2 threads race to
0170      * update the rand state it just adds to the entropy.
0171      */
0172     if (rand_bits == 0) {
0173         rand_bits = 64;
0174         rand = get_random_u64();
0175     }
0176
0177     ret = rand & 1;
0178
0179     rand_bits--;
0180     rand >>= 1;
0181
0182     return ret;
0183 }