Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Message-ID: <1d7de9f9f4074f67c567dbb4cc1497503d739e30.camel@linux.intel.com>
Subject: Re: [PATCH v9 0/8] stg mail -e --version=v9 \
From:   Alexander Duyck <alexander.h.duyck@linux.intel.com>
To:     Michal Hocko <mhocko@kernel.org>,
        Alexander Duyck <alexander.duyck@gmail.com>
Cc:     virtio-dev@lists.oasis-open.org, kvm list <kvm@vger.kernel.org>,
        "Michael S. Tsirkin" <mst@redhat.com>,
        Catalin Marinas <catalin.marinas@arm.com>,
        David Hildenbrand <david@redhat.com>,
        Dave Hansen <dave.hansen@intel.com>,
        LKML <linux-kernel@vger.kernel.org>,
        Matthew Wilcox <willy@infradead.org>,
        linux-mm <linux-mm@kvack.org>,
        Andrew Morton <akpm@linux-foundation.org>, will@kernel.org,
        linux-arm-kernel@lists.infradead.org,
        Oscar Salvador <osalvador@suse.de>,
        Yang Zhang <yang.zhang.wz@gmail.com>,
        Pankaj Gupta <pagupta@redhat.com>,
        Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>,
        Nitesh Narayan Lal <nitesh@redhat.com>,
        Rik van Riel <riel@surriel.com>, lcapitulino@redhat.com,
        "Wang, Wei W" <wei.w.wang@intel.com>,
        Andrea Arcangeli <aarcange@redhat.com>, ying.huang@intel.com,
        Paolo Bonzini <pbonzini@redhat.com>,
        Dan Williams <dan.j.williams@intel.com>,
        Fengguang Wu <fengguang.wu@intel.com>,
        "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Date:   Tue, 10 Sep 2019 14:23:40 -0700
In-Reply-To: <20190910175213.GD4023@dhcp22.suse.cz>
References: <20190907172225.10910.34302.stgit@localhost.localdomain>
         <20190910124209.GY2063@dhcp22.suse.cz>
         <CAKgT0Udr6nYQFTRzxLbXk41SiJ-pcT_bmN1j1YR4deCwdTOaUQ@mail.gmail.com>
         <20190910144713.GF2063@dhcp22.suse.cz>
         <CAKgT0UdB4qp3vFGrYEs=FwSXKpBEQ7zo7DV55nJRO2C-KCEOrw@mail.gmail.com>
         <20190910175213.GD4023@dhcp22.suse.cz>
Content-Type: text/plain; charset="UTF-8"
User-Agent: Evolution 3.30.5 (3.30.5-1.fc29) 
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Tue, 2019-09-10 at 19:52 +0200, Michal Hocko wrote:
> On Tue 10-09-19 09:05:43, Alexander Duyck wrote:
> > On Tue, Sep 10, 2019 at 7:47 AM Michal Hocko <mhocko@kernel.org> wrote:
> > > On Tue 10-09-19 07:42:43, Alexander Duyck wrote:
> > > > On Tue, Sep 10, 2019 at 5:42 AM Michal Hocko <mhocko@kernel.org> wrote:
> > > > > I wanted to review "mm: Introduce Reported pages" just realize that I
> > > > > have no clue on what is going on so returned to the cover and it didn't
> > > > > really help much. I am completely unfamiliar with virtio so please bear
> > > > > with me.
> > > > > 
> > > > > On Sat 07-09-19 10:25:03, Alexander Duyck wrote:
> > > > > [...]
> > > > > > This series provides an asynchronous means of reporting to a hypervisor
> > > > > > that a guest page is no longer in use and can have the data associated
> > > > > > with it dropped. To do this I have implemented functionality that allows
> > > > > > for what I am referring to as unused page reporting
> > > > > > 
> > > > > > The functionality for this is fairly simple. When enabled it will allocate
> > > > > > statistics to track the number of reported pages in a given free area.
> > > > > > When the number of free pages exceeds this value plus a high water value,
> > > > > > currently 32, it will begin performing page reporting which consists of
> > > > > > pulling pages off of free list and placing them into a scatter list. The
> > > > > > scatterlist is then given to the page reporting device and it will perform
> > > > > > the required action to make the pages "reported", in the case of
> > > > > > virtio-balloon this results in the pages being madvised as MADV_DONTNEED
> > > > > > and as such they are forced out of the guest. After this they are placed
> > > > > > back on the free list,
> > > > > 
> > > > > And here I am reallly lost because "forced out of the guest" makes me
> > > > > feel that those pages are no longer usable by the guest. So how come you
> > > > > can add them back to the free list. I suspect understanding this part
> > > > > will allow me to understand why we have to mark those pages and prevent
> > > > > merging.
> > > > 
> > > > Basically as the paragraph above mentions "forced out of the guest"
> > > > really is just the hypervisor calling MADV_DONTNEED on the page in
> > > > question. So the behavior is the same as any userspace application
> > > > that calls MADV_DONTNEED where the contents are no longer accessible
> > > > from userspace and attempting to access them will result in a fault
> > > > and the page being populated with a zero fill on-demand page, or a
> > > > copy of the file contents if the memory is file backed.
> > > 
> > > As I've said I have no idea about virt so this doesn't really tell me
> > > much. Does that mean that if somebody allocates such a page and tries to
> > > access it then virt will handle a fault and bring it back?
> > 
> > Actually I am probably describing too much as the MADV_DONTNEED is the
> > hypervisor behavior in response to the virtio-balloon notification. A
> > more thorough explanation of it can be found by just running "man
> > madvise", probably best just to leave it at that since I am probably
> > confusing things by describing hypervisor behavior in a kernel patch
> > set.
> 
> This analogy is indeed confusing and doesn't help to build a picture.

All I am really doing is using a pointer per free_list, the page->index, 
and a page flag to provide a way to iterate over the list in such a way
that I will not repeat the operation on a page I have already reported. It
is taking advantage of the fact that we add pages to either the head or
the tail of the list, and can pull the pages from anywhere in the list, so
we have to work around those edges to avoid processing the already
reported pages in between.

Admittedly this is pretty complex. I've been at this for several months,
and have gone through several iterations.

If it helps I can try to draw it out as a bit of ASCII art. Basically what
I am trying to do is find a way to skip over the blob of reported pages
that would exist after we have not been reporting for a little while. Most
of this logic is in the get_reported_pages/free_reported_pages that should
be in patch 6.

So on our first iteration through the pages it is pretty straightforward.
We basically just keep pushing the boundary pointer up, we fetch the pages
immediately in front of it, and then when we return the now-reported pages
we push the boundary pointer up to those pages.

While we are actively reporting a given zone we prevent any pages from
being inserted behind the boundary. They are always inserted before the
boundary pointer. This is achieved by replacing the free_list tail pointer
value with the boundary pointer value in the case of add_to_tail calls.

Legend:
U Unused Page
R Reported Page
< Boundary Reported Page

     Head ....................................................... Tail
Start     UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU <
..        UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU<RRRRRRRRRRRRRRRRRRRRRRR
End       UU<RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

After we completed the boundary pointer is discarded and we don't have to
update it when the zone->flag indicating reporting is active is no longer
set. What we then have happening is that pages are pulled out of the
free_list at random locations or from the head. This causes the list of
reported pages to slowly shrink, however the block of pages should remain
contiguous since new pages are only added to the head or the tail.

     Head ....................................................... Tail
Idle      UUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRUUUU

Once we have a large enough difference between the nr_free and
reported_pages we will then restart the reporting by resetting the
boundary to the tail and proceeding to pull the non-reported pages that
are in front of the boundary(fig1). Once those are exhasusted we will
start pulling the pages from the head of the list, reporting those, and
then placing them back at the boundary(fig2). When we finally hit the
point where there are no more pages to pull from the head that are not
reported we will update the boundary to the first reported page in the
list, return the reported pages there, and we should be done reporting
pages from this free list.

     Head ....................................................... Tail
Start     UUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRUUUU <
fig1      UUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRU<RRRR
fig2      UUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR<RRRRRRRRRRRRRRRRRRRR
End       UU<RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

The goal with all this is to allow the boundary pointer to move, but to
guarantee forward progress as we work our way through the free_list(s).
Essentially the only requirements we are posing on the page allocator is
that if it pulls the page at the boundary it has to push it back, and if
it wants to add to the tail it has to use the boundary page as the tail
instead.

> > For the most part all the page reporting really does is provide a way
> > to incrementally identify unused regions of memory in the buddy
> > allocator. That in turn is used by virtio-balloon in a polling thread
> > to report to the hypervisor what pages are not in use so that it can
> > make a decision on what to do with the pages now that it knows they
> > are unused.
> 
> So essentially you want to store metadata into free pages and control
> what the allocator can do with them? Namely buddy merging if the type
> doesn't match?

We don't put any limitations on the allocator other then that it needs to
clean up the metadata on allocation, and that it cannot allocate a page
that is in the process of being reported since we pulled it from the
free_list. If the page is a "Reported" page then it decrements the
reported_pages count for the free_area and makes sure the page doesn't
exist in the "Boundary" array pointer value, if it does it moves the
"Boundary" since it is pulling the page.

> > All this is providing is just a report and it is optional if the
> > hypervisor will act on it or not. If the hypervisor takes some sort of
> > action on the page, then the expectation is that the hypervisor will
> > use some sort of mechanism such as a page fault to discover when the
> > page is used again.
> 
> OK so the baloon driver is in charge of this metadata and the allocator
> has to live with that. Isn't that a layer violation?

Really the metadata belongs to the page reporting. The virtio balloon
driver doesn't get to see any of it. It basically registers as a Reporting
interface and then we start sending it scatterlists to report. It doesn't
do anything with the actual pages themselves other then DMA map the
physical addresses for them.