KVM Archive on lore.kernel.org
 help / color / Atom feed
From: Alexander Duyck <alexander.duyck@gmail.com>
To: David Hildenbrand <david@redhat.com>
Cc: Nitesh Narayan Lal <nitesh@redhat.com>,
	kvm list <kvm@vger.kernel.org>,
	"Michael S. Tsirkin" <mst@redhat.com>,
	Dave Hansen <dave.hansen@intel.com>,
	LKML <linux-kernel@vger.kernel.org>,
	linux-mm <linux-mm@kvack.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	Yang Zhang <yang.zhang.wz@gmail.com>,
	pagupta@redhat.com, Rik van Riel <riel@surriel.com>,
	Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>,
	lcapitulino@redhat.com, wei.w.wang@intel.com,
	Andrea Arcangeli <aarcange@redhat.com>,
	Paolo Bonzini <pbonzini@redhat.com>,
	dan.j.williams@intel.com,
	Alexander Duyck <alexander.h.duyck@linux.intel.com>
Subject: Re: [PATCH v1 1/6] mm: Adjust shuffle code to allow for future coalescing
Date: Fri, 28 Jun 2019 12:49:11 -0700
Message-ID: <CAKgT0UfNFbAs=1o_DMHRQScDKP8qLnmOGtgfUhjk3_Jupbwf6w@mail.gmail.com> (raw)
In-Reply-To: <7d959202-b2cd-fe24-5b3c-84e159eafe0a@redhat.com>

On Tue, Jun 25, 2019 at 12:56 AM David Hildenbrand <david@redhat.com> wrote:
>
> On 20.06.19 00:33, Alexander Duyck wrote:
> > From: Alexander Duyck <alexander.h.duyck@linux.intel.com>
> >
> > This patch is meant to move the head/tail adding logic out of the shuffle
> > code and into the __free_one_page function since ultimately that is where
> > it is really needed anyway. By doing this we should be able to reduce the
> > overhead and can consolidate all of the list addition bits in one spot.
> >
> > Signed-off-by: Alexander Duyck <alexander.h.duyck@linux.intel.com>
> > ---
> >  include/linux/mmzone.h |   12 --------
> >  mm/page_alloc.c        |   70 +++++++++++++++++++++++++++---------------------
> >  mm/shuffle.c           |   24 ----------------
> >  mm/shuffle.h           |   35 ++++++++++++++++++++++++
> >  4 files changed, 74 insertions(+), 67 deletions(-)
> >
> > diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
> > index 427b79c39b3c..4c07af2cfc2f 100644
> > --- a/include/linux/mmzone.h
> > +++ b/include/linux/mmzone.h
> > @@ -116,18 +116,6 @@ static inline void add_to_free_area_tail(struct page *page, struct free_area *ar
> >       area->nr_free++;
> >  }
> >
> > -#ifdef CONFIG_SHUFFLE_PAGE_ALLOCATOR
> > -/* Used to preserve page allocation order entropy */
> > -void add_to_free_area_random(struct page *page, struct free_area *area,
> > -             int migratetype);
> > -#else
> > -static inline void add_to_free_area_random(struct page *page,
> > -             struct free_area *area, int migratetype)
> > -{
> > -     add_to_free_area(page, area, migratetype);
> > -}
> > -#endif
> > -
> >  /* Used for pages which are on another list */
> >  static inline void move_to_free_area(struct page *page, struct free_area *area,
> >                            int migratetype)
> > diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> > index f4651a09948c..ec344ce46587 100644
> > --- a/mm/page_alloc.c
> > +++ b/mm/page_alloc.c
> > @@ -830,6 +830,36 @@ static inline struct capture_control *task_capc(struct zone *zone)
> >  #endif /* CONFIG_COMPACTION */
> >
> >  /*
> > + * If this is not the largest possible page, check if the buddy
> > + * of the next-highest order is free. If it is, it's possible
> > + * that pages are being freed that will coalesce soon. In case,
> > + * that is happening, add the free page to the tail of the list
> > + * so it's less likely to be used soon and more likely to be merged
> > + * as a higher order page
> > + */
> > +static inline bool
> > +buddy_merge_likely(unsigned long pfn, unsigned long buddy_pfn,
> > +                struct page *page, unsigned int order)
> > +{
> > +     struct page *higher_page, *higher_buddy;
> > +     unsigned long combined_pfn;
> > +
> > +     if (is_shuffle_order(order) || order >= (MAX_ORDER - 2))
>
> My intuition tells me you can drop the () around "MAX_ORDER - 2"

I dunno, I always kind of prefer to use the parenthesis in these cases
for readability. I suppose I can drop it though.

> > +             return false;
>
> Guess the "is_shuffle_order(order)" check should rather be performed by
> the caller, before calling this function.

I could do that, however I am not sure it adds much. I am pretty sure
the resultant code would be the same. Where things would be a bit more
complicated is that I would then have to probably look at adding a
variable to trap the output of is_shuffle_tail_page or
buddy_merge_likely.

> > +
> > +     if (!pfn_valid_within(buddy_pfn))
> > +             return false;
> > +
> > +     combined_pfn = buddy_pfn & pfn;
> > +     higher_page = page + (combined_pfn - pfn);
> > +     buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
> > +     higher_buddy = higher_page + (buddy_pfn - combined_pfn);
> > +
> > +     return pfn_valid_within(buddy_pfn) &&
> > +            page_is_buddy(higher_page, higher_buddy, order + 1);
> > +}
> > +
> > +/*
> >   * Freeing function for a buddy system allocator.
> >   *
> >   * The concept of a buddy system is to maintain direct-mapped table
> > @@ -858,11 +888,12 @@ static inline void __free_one_page(struct page *page,
> >               struct zone *zone, unsigned int order,
> >               int migratetype)
> >  {
> > -     unsigned long combined_pfn;
> > +     struct capture_control *capc = task_capc(zone);
> >       unsigned long uninitialized_var(buddy_pfn);
> > -     struct page *buddy;
> > +     unsigned long combined_pfn;
> > +     struct free_area *area;
> >       unsigned int max_order;
> > -     struct capture_control *capc = task_capc(zone);
> > +     struct page *buddy;
> >
> >       max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
> >
> > @@ -931,35 +962,12 @@ static inline void __free_one_page(struct page *page,
> >  done_merging:
> >       set_page_order(page, order);
> >
> > -     /*
> > -      * If this is not the largest possible page, check if the buddy
> > -      * of the next-highest order is free. If it is, it's possible
> > -      * that pages are being freed that will coalesce soon. In case,
> > -      * that is happening, add the free page to the tail of the list
> > -      * so it's less likely to be used soon and more likely to be merged
> > -      * as a higher order page
> > -      */
> > -     if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)
> > -                     && !is_shuffle_order(order)) {
> > -             struct page *higher_page, *higher_buddy;
> > -             combined_pfn = buddy_pfn & pfn;
> > -             higher_page = page + (combined_pfn - pfn);
> > -             buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
> > -             higher_buddy = higher_page + (buddy_pfn - combined_pfn);
> > -             if (pfn_valid_within(buddy_pfn) &&
> > -                 page_is_buddy(higher_page, higher_buddy, order + 1)) {
> > -                     add_to_free_area_tail(page, &zone->free_area[order],
> > -                                           migratetype);
> > -                     return;
> > -             }
> > -     }
> > -
> > -     if (is_shuffle_order(order))
> > -             add_to_free_area_random(page, &zone->free_area[order],
> > -                             migratetype);
> > +     area = &zone->free_area[order];
> > +     if (buddy_merge_likely(pfn, buddy_pfn, page, order) ||
> > +         is_shuffle_tail_page(order))
> > +             add_to_free_area_tail(page, area, migratetype);
>
> I would prefer here something like
>
> if (is_shuffle_order(order)) {
>         if (add_shuffle_order_to_tail(order))
>                 add_to_free_area_tail(page, area, migratetype);
>         else
>                 add_to_free_area(page, area, migratetype);
> } else if (buddy_merge_likely(pfn, buddy_pfn, page, order)) {
>         add_to_free_area_tail(page, area, migratetype);
> } else {
>         add_to_free_area(page, area, migratetype);
> }
>
> dropping "is_shuffle_order()" from buddy_merge_likely()
>
> Especially, the name "is_shuffle_tail_page(order)" suggests that you are
> passing a page.

Okay, I can look at renaming that. I will probably look at just using
a variable instead of nesting the if statements like that. Otherwise
that is going to get pretty messy fairly quickly.

> >       else
> > -             add_to_free_area(page, &zone->free_area[order], migratetype);
> > -
> > +             add_to_free_area(page, area, migratetype);
> >  }
> >
> >  /*
> > diff --git a/mm/shuffle.c b/mm/shuffle.c
> > index 3ce12481b1dc..55d592e62526 100644
> > --- a/mm/shuffle.c
> > +++ b/mm/shuffle.c
> > @@ -4,7 +4,6 @@
> >  #include <linux/mm.h>
> >  #include <linux/init.h>
> >  #include <linux/mmzone.h>
> > -#include <linux/random.h>
> >  #include <linux/moduleparam.h>
> >  #include "internal.h"
> >  #include "shuffle.h"
> > @@ -182,26 +181,3 @@ void __meminit __shuffle_free_memory(pg_data_t *pgdat)
> >       for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
> >               shuffle_zone(z);
> >  }
> > -
> > -void add_to_free_area_random(struct page *page, struct free_area *area,
> > -             int migratetype)
> > -{
> > -     static u64 rand;
> > -     static u8 rand_bits;
> > -
> > -     /*
> > -      * The lack of locking is deliberate. If 2 threads race to
> > -      * update the rand state it just adds to the entropy.
> > -      */
> > -     if (rand_bits == 0) {
> > -             rand_bits = 64;
> > -             rand = get_random_u64();
> > -     }
> > -
> > -     if (rand & 1)
> > -             add_to_free_area(page, area, migratetype);
> > -     else
> > -             add_to_free_area_tail(page, area, migratetype);
> > -     rand_bits--;
> > -     rand >>= 1;
> > -}
> > diff --git a/mm/shuffle.h b/mm/shuffle.h
> > index 777a257a0d2f..3f4edb60a453 100644
> > --- a/mm/shuffle.h
> > +++ b/mm/shuffle.h
> > @@ -3,6 +3,7 @@
> >  #ifndef _MM_SHUFFLE_H
> >  #define _MM_SHUFFLE_H
> >  #include <linux/jump_label.h>
> > +#include <linux/random.h>
> >
> >  /*
> >   * SHUFFLE_ENABLE is called from the command line enabling path, or by
> > @@ -43,6 +44,35 @@ static inline bool is_shuffle_order(int order)
> >               return false;
> >       return order >= SHUFFLE_ORDER;
> >  }
> > +
> > +static inline bool is_shuffle_tail_page(int order)
> > +{
> > +     static u64 rand;
> > +     static u8 rand_bits;
> > +     u64 rand_old;
> > +
> > +     if (!is_shuffle_order(order))
> > +             return false;
> > +
> > +     /*
> > +      * The lack of locking is deliberate. If 2 threads race to
> > +      * update the rand state it just adds to the entropy.
> > +      */
> > +     if (rand_bits-- == 0) {
> > +             rand_bits = 64;
> > +             rand = get_random_u64();
> > +     }
> > +
> > +     /*
> > +      * Test highest order bit while shifting our random value. This
> > +      * should result in us testing for the carry flag following the
> > +      * shift.
> > +      */
> > +     rand_old = rand;
> > +     rand <<= 1;
> > +
> > +     return rand < rand_old;
> > +}
> >  #else
> >  static inline void shuffle_free_memory(pg_data_t *pgdat)
> >  {
> > @@ -60,5 +90,10 @@ static inline bool is_shuffle_order(int order)
> >  {
> >       return false;
> >  }
> > +
> > +static inline bool is_shuffle_tail_page(int order)
> > +{
> > +     return false;
> > +}
> >  #endif
> >  #endif /* _MM_SHUFFLE_H */
> >
>
>
> --
>
> Thanks,
>
> David / dhildenb

  reply index

Thread overview: 59+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-06-19 22:32 [PATCH v1 0/6] mm / virtio: Provide support for paravirtual waste page treatment Alexander Duyck
2019-06-19 22:33 ` [PATCH v1 1/6] mm: Adjust shuffle code to allow for future coalescing Alexander Duyck
2019-06-25  7:55   ` David Hildenbrand
2019-06-28 19:49     ` Alexander Duyck [this message]
2019-06-25 18:25   ` Dave Hansen
2019-06-25 18:26   ` Dave Hansen
2019-06-19 22:33 ` [PATCH v1 2/6] mm: Move set/get_pcppage_migratetype to mmzone.h Alexander Duyck
2019-06-25 18:28   ` Dave Hansen
2019-06-28 19:55     ` Alexander Duyck
2019-06-19 22:33 ` [PATCH v1 3/6] mm: Use zone and order instead of free area in free_list manipulators Alexander Duyck
2019-06-25 18:36   ` Dave Hansen
2019-06-19 22:33 ` [PATCH v1 4/6] mm: Introduce "aerated" pages Alexander Duyck
2019-06-25 19:45   ` Dave Hansen
2019-07-08 17:32     ` Alexander Duyck
2019-06-19 22:33 ` [PATCH v1 5/6] mm: Add logic for separating "aerated" pages from "raw" pages Alexander Duyck
2019-06-25 20:24   ` Dave Hansen
2019-07-08 19:02     ` Alexander Duyck
2019-07-08 19:36       ` Dave Hansen
2019-07-08 22:02         ` Alexander Duyck
2019-06-19 22:33 ` [PATCH v1 6/6] virtio-balloon: Add support for aerating memory via hinting Alexander Duyck
2019-07-16  9:55   ` Michael S. Tsirkin
2019-07-16 14:00     ` Dave Hansen
2019-07-16 14:12       ` David Hildenbrand
2019-07-16 14:17         ` David Hildenbrand
2019-07-16 15:04           ` Michael S. Tsirkin
2019-07-16 14:41         ` Dave Hansen
2019-07-16 15:01           ` Wang, Wei W
2019-07-16 16:12             ` Michael S. Tsirkin
2019-07-16 15:02           ` David Hildenbrand
2019-07-16 15:37     ` Alexander Duyck
2019-07-16 16:07       ` Michael S. Tsirkin
2019-07-16 16:54         ` Alexander Duyck
2019-07-16 17:41           ` Michael S. Tsirkin
2019-07-16 21:06             ` Alexander Duyck
2019-07-17 10:28               ` Michael S. Tsirkin
2019-07-17 16:43                 ` Alexander Duyck
2019-07-18  5:13                   ` Michael S. Tsirkin
2019-07-18 15:34                     ` Alexander Duyck
2019-07-18 16:03                       ` Nitesh Narayan Lal
2019-07-18 20:27                         ` Michael S. Tsirkin
2019-07-18 16:07                       ` Michael S. Tsirkin
2019-07-18 20:29                         ` Alexander Duyck
2019-07-18 20:37                           ` Michael S. Tsirkin
2019-07-18 20:54                             ` Alexander Duyck
2019-07-18 20:24                       ` Michael S. Tsirkin
2019-07-18 20:34                         ` Alexander Duyck
2019-07-18 20:48                           ` Michael S. Tsirkin
2019-07-18 21:09                             ` Alexander Duyck
2019-06-19 22:37 ` [PATCH v1 QEMU] QEMU: Provide a interface for hinting based off of the balloon infrastructure Alexander Duyck
2019-06-25  7:42 ` [PATCH v1 0/6] mm / virtio: Provide support for paravirtual waste page treatment David Hildenbrand
2019-06-25 14:10   ` Dave Hansen
2019-06-25 17:00     ` Alexander Duyck
2019-06-25 18:12       ` David Hildenbrand
2019-06-25 18:22       ` Dave Hansen
2019-07-15  9:41         ` David Hildenbrand
2019-07-15 14:57           ` Alexander Duyck
2019-06-25 16:09   ` Alexander Duyck
2019-06-26  9:01   ` Christophe de Dinechin
2019-06-26  9:12     ` David Hildenbrand

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAKgT0UfNFbAs=1o_DMHRQScDKP8qLnmOGtgfUhjk3_Jupbwf6w@mail.gmail.com' \
    --to=alexander.duyck@gmail.com \
    --cc=aarcange@redhat.com \
    --cc=akpm@linux-foundation.org \
    --cc=alexander.h.duyck@linux.intel.com \
    --cc=dan.j.williams@intel.com \
    --cc=dave.hansen@intel.com \
    --cc=david@redhat.com \
    --cc=konrad.wilk@oracle.com \
    --cc=kvm@vger.kernel.org \
    --cc=lcapitulino@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=mst@redhat.com \
    --cc=nitesh@redhat.com \
    --cc=pagupta@redhat.com \
    --cc=pbonzini@redhat.com \
    --cc=riel@surriel.com \
    --cc=wei.w.wang@intel.com \
    --cc=yang.zhang.wz@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

KVM Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/kvm/0 kvm/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 kvm kvm/ https://lore.kernel.org/kvm \
		kvm@vger.kernel.org
	public-inbox-index kvm

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.kvm


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git