Re: [PATCH] mm: batch-free pcp list if possible

[Minchan Kim]

On Thu, Feb 10, 2011 at 6:47 AM, Andrew Morton
<akpm@xxxxxxxxxxxxxxxxxxxx> wrote:
> On Wed, 9 Feb 2011 22:33:38 +0100
> Johannes Weiner <hannes@xxxxxxxxxxx> wrote:
>
>> On Wed, Feb 09, 2011 at 12:38:03PM -0800, Andrew Morton wrote:
>> > On Wed, Â9 Feb 2011 22:21:17 +0900
>> > Namhyung Kim <namhyung@xxxxxxxxx> wrote:
>> >
>> > > free_pcppages_bulk() frees pages from pcp lists in a round-robin
>> > > fashion by keeping batch_free counter. But it doesn't need to spin
>> > > if there is only one non-empty list. This can be checked by
>> > > batch_free == MIGRATE_PCPTYPES.
>> > >
>> > > Signed-off-by: Namhyung Kim <namhyung@xxxxxxxxx>
>> > > ---
>> > > Âmm/page_alloc.c | Â Â4 ++++
>> > > Â1 files changed, 4 insertions(+), 0 deletions(-)
>> > >
>> > > diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> > > index a873e61e312e..470fb42e303c 100644
>> > > --- a/mm/page_alloc.c
>> > > +++ b/mm/page_alloc.c
>> > > @@ -614,6 +614,10 @@ static void free_pcppages_bulk(struct zone *zone, int count,
>> > > Â Â Â Â Â Â Â Â Â list = &pcp->lists[migratetype];
>> > > Â Â Â Â Â } while (list_empty(list));
>> > >
>> > > + Â Â Â Â /* This is an only non-empty list. Free them all. */
>> > > + Â Â Â Â if (batch_free == MIGRATE_PCPTYPES)
>> > > + Â Â Â Â Â Â Â Â batch_free = to_free;
>> > > +
>> > > Â Â Â Â Â do {
>> > > Â Â Â Â Â Â Â Â Â page = list_entry(list->prev, struct page, lru);
>> > > Â Â Â Â Â Â Â Â Â /* must delete as __free_one_page list manipulates */
>> >
>> > free_pcppages_bulk() hurts my brain.
>>
>> Thanks for saying that ;-)
>
> My brain has a lot of scar tissue.
>
>> > What is it actually trying to do, and why? ÂIt counts up the number of
>> > contiguous empty lists and then frees that number of pages from the
>> > first-encountered non-empty list and then advances onto the next list?
>> >
>> > What's the point in that? ÂWhat relationship does the number of
>> > contiguous empty lists have with the number of pages to free from one
>> > list?
>>
>> It at least recovers some of the otherwise wasted effort of looking at
>> an empty list, by flushing more pages once it encounters a non-empty
>> list. ÂAfter all, freeing to_free pages is the goal.
>>
>> That breaks the round-robin fashion, though. ÂIf list-1 has pages,
>> list-2 is empty and list-3 has pages, it will repeatedly free one page
>> from list-1 and two pages from list-3.
>>
>> My initial response to Namhyung's patch was to write up a version that
>> used a bitmap for all lists. ÂIt starts with all lists set and clears
>> their respective bit once the list is empty, so it would never
>> consider them again. ÂBut it looked a bit over-engineered for 3 lists
>> and the resulting object code was bigger than what we have now.
>> Though, it would be more readable. ÂAttached for reference (untested
>> and all).
>>
>> Â Â Â Hannes
>>
>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> index 60e58b0..c77ab28 100644
>> --- a/mm/page_alloc.c
>> +++ b/mm/page_alloc.c
>> @@ -590,8 +590,7 @@ static inline int free_pages_check(struct page *page)
>> Âstatic void free_pcppages_bulk(struct zone *zone, int count,
>> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â struct per_cpu_pages *pcp)
>> Â{
>> - Â Â int migratetype = 0;
>> - Â Â int batch_free = 0;
>> + Â Â unsigned long listmap = (1 << MIGRATE_PCPTYPES) - 1;
>> Â Â Â int to_free = count;
>>
>> Â Â Â spin_lock(&zone->lock);
>> @@ -599,31 +598,29 @@ static void free_pcppages_bulk(struct zone *zone, int count,
>> Â Â Â zone->pages_scanned = 0;
>>
>> Â Â Â while (to_free) {
>> - Â Â Â Â Â Â struct page *page;
>> - Â Â Â Â Â Â struct list_head *list;
>> -
>> + Â Â Â Â Â Â int migratetype;
>> Â Â Â Â Â Â Â /*
>> - Â Â Â Â Â Â Â* Remove pages from lists in a round-robin fashion. A
>> - Â Â Â Â Â Â Â* batch_free count is maintained that is incremented when an
>> - Â Â Â Â Â Â Â* empty list is encountered. ÂThis is so more pages are freed
>> - Â Â Â Â Â Â Â* off fuller lists instead of spinning excessively around empty
>> - Â Â Â Â Â Â Â* lists
>> + Â Â Â Â Â Â Â* Remove pages from lists in a round-robin fashion.
>> + Â Â Â Â Â Â Â* Empty lists are excluded from subsequent rounds.
>> Â Â Â Â Â Â Â Â*/
>> - Â Â Â Â Â Â do {
>> - Â Â Â Â Â Â Â Â Â Â batch_free++;
>> - Â Â Â Â Â Â Â Â Â Â if (++migratetype == MIGRATE_PCPTYPES)
>> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â migratetype = 0;
>> - Â Â Â Â Â Â Â Â Â Â list = &pcp->lists[migratetype];
>> - Â Â Â Â Â Â } while (list_empty(list));
>> + Â Â Â Â Â Â for_each_set_bit (migratetype, &listmap, MIGRATE_PCPTYPES) {
>> + Â Â Â Â Â Â Â Â Â Â struct list_head *list;
>> + Â Â Â Â Â Â Â Â Â Â struct page *page;
>>
>> - Â Â Â Â Â Â do {
>> + Â Â Â Â Â Â Â Â Â Â list = &pcp->lists[migratetype];
>> + Â Â Â Â Â Â Â Â Â Â if (list_empty(list)) {
>> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â listmap &= ~(1 << migratetype);
>> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â continue;
>> + Â Â Â Â Â Â Â Â Â Â }
>> + Â Â Â Â Â Â Â Â Â Â if (!to_free--)
>> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â break;
>> Â Â Â Â Â Â Â Â Â Â Â page = list_entry(list->prev, struct page, lru);
>> Â Â Â Â Â Â Â Â Â Â Â /* must delete as __free_one_page list manipulates */
>> Â Â Â Â Â Â Â Â Â Â Â list_del(&page->lru);
>> Â Â Â Â Â Â Â Â Â Â Â /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
>> Â Â Â Â Â Â Â Â Â Â Â __free_one_page(page, zone, 0, page_private(page));
>> Â Â Â Â Â Â Â Â Â Â Â trace_mm_page_pcpu_drain(page, 0, page_private(page));
>> - Â Â Â Â Â Â } while (--to_free && --batch_free && !list_empty(list));
>> + Â Â Â Â Â Â }
>> Â Â Â }
>> Â Â Â __mod_zone_page_state(zone, NR_FREE_PAGES, count);
>> Â Â Â spin_unlock(&zone->lock);
>
> Well, it replaces one linear search with another one. ÂIf you really
> want to avoid repeated walking over empty lists then create a local
> array `list_head *lists[MIGRATE_PCPTYPES]' (or MIGRATE_PCPTYPES+1 for
> null-termination), populate it on entry and compact it as lists fall
> empty. ÂThen the code can simply walk around the lists until to_free is
> satisfied or list_empty(lists[0]). ÂIt's not obviously worth the effort
> though - the empty list_heads will be cache-hot and all the cost will
> be in hitting cache-cold pageframes.

Hannes's patch solves round-robin fairness as well as avoidance of
empty list although it makes rather bloated code.
I think it's enough to solve the fairness regardless of whether it's
Hannes's approach or your idea.

>
>
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at Âhttp://vger.kernel.org/majordomo-info.html
> Please read the FAQ at Âhttp://www.tux.org/lkml/
>



-- 
Kind regards,
Minchan Kim
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/