Improve zone lock scalability using Daniel Jordan's list work
Subsystems (6)
cover Improve zone lock scalability using Daniel Jordan's list work
Daniel Jordan and others proposed an innovative technique to make multiple threads concurrently use list_del() at any position of the list and list_add() at head position of the list without taking a lock in this year's MM summit[0].
People think this technique may be useful to improve zone lock scalability so here is my try. This series is based on Daniel Jordan's most recent patchset[1]. To make this series self contained, 2 of his patches are extracted here.
Scalability comes best when multiple threads are operating at different positions of the list. Since free path will access (buddy) pages randomly on free list during merging, it is a good fit to make use of this technique. This patchset makes free path run concurrently.
Patch 1 is for testing purpose only, it removes LRU lock from the picture so we can get a better understanding of how much improvement this patchset has on zone lock.
Patch 2-3 are Daniel's work to realize concurrent list_del() and list_add(), these new APIs are called smp_list_del() and smp_list_splice().
Patch 4-7 makes free path run concurrently by converting the zone lock from spinlock to rwlock and has free path taking the zone lock in read mode. To avoid complexity and problems, all other code paths take zone lock in write mode.
Patch 8 is an optimization that reduces free list head access to avoid severe cache bouncing. It also comes with a side effect: with this patch, there will be mergable pages unmerged in Buddy.
Patch 9 improves fragmentation issues introduced in patch 8 by doing pre-merges before pages are sent to merge under zone lock.
This patchset is based on v4.19-rc2.
Performance wise on 56 cores/112 threads Intel Skylake 2 sockets server using will-it-scale/page_fault1 process mode(higher is better):
kernel performance zone lock contention patch1 9219349 76.99% patch7 2461133 -73.3% 54.46%(another 34.66% on smp_list_add()) patch8 11712766 +27.0% 68.14% patch9 11386980 +23.5% 67.18%
Though lock contention reduced a lot for patch7, the performance dropped considerably due to severe cache bouncing on free list head among multiple threads doing page free at the same time, because every page free will need to add the page to the free list head.
Patch8 is meant to solve this cache bouncing problem and has good result, except the above mentioned side effect of having mergable pages unmerged in Buddy. Patch9 reduced the fragmentation problem to some extent while caused slightly performance drop.
As a comparison to the no_merge+cluster_alloc approach I posted before[2]:
kernel performance zone lock contention patch1 9219349 76.99% no_merge 11733153 +27.3% 69.18%
no_merge+cluster_alloc 12094893 +31.2% 0.73%
no_merge(skip merging for order0 page on free path) has similar performance and zone lock contention as patch8/9, while with cluster_alloc that also improves allocation side, zone lock contention for this workload is almost gone.
To get an idea of how fragmentation are affected by patch8 and how much improvement patch9 has, this is the result of /proc/buddyinfo after running will-it-scale/page_fault1 for 3 minutes:
With patch7:
Node 0, zone DMA 0 2 1 1 3 2 2 1 0 1 3 Node 0, zone DMA32 7 3 6 5 5 10 6 7 6 10 410 Node 0, zone Normal 17820 16819 14645 12969 11367 9229 6365 3062 756 69 5646 Node 1, zone Normal 44789 60354 52331 37532 22071 9604 2750 241 32 11 6378
With patch8:
Node 0, zone DMA 0 2 1 1 3 2 2 1 0 1 3 Node 0, zone DMA32 7 9 5 4 5 10 6 7 6 10 410 Node 0, zone Normal 404917 119614 79446 58303 20679 3106 222 89 28 9 5615 Node 1, zone Normal 507659 127355 64470 53549 14104 1288 30 4 1 1 6078
With patch9:
Node 0, zone DMA 0 3 0 1 3 0 1 0 1 1 3 Node 0, zone DMA32 11 423 621 705 726 702 60 14 5 6 296 Node 0, zone Normal 20407 21016 18731 16195 13697 10483 6873 3148 735 39 5637 Node 1, zone Normal 79738 76963 59313 35996 18626 9743 3947 750 21 2 6080
A lot more pages stayed in order0 in patch8 than patch7, consequently, for order5 and above pages, there are fewer with patch8 than patch7, suggesting that some pages are not properly merged into high order pages with patch8 applied. Patch9 has far fewer pages stayed in order0 than patch8, which is a good sign but still not as good as patch7.
As a comparison, this is the result of no_merge(think of it as a worst case result regarding fragmentation):
With no_merge:
Node 0, zone DMA 0 2 1 1 3 2 2 1 0 1 3 Node 0, zone DMA32 7 3 6 5 5 10 6 7 6 10 410 Node 0, zone Normal 1895199 5 1 1 4 2 2 1 1 1 5614 Node 1, zone Normal 1718733 4 1 13 10 3 2 0 1 1 6008
Conclusion: The approach I proposed here caused performance drop due to free list head cache bouncing. If we can bear the result of some mergable pages becoming unmerged in Buddy, zone lock scalability can be
improved: performance increase 20%+, lock contention drop 8%. no_merge+cluster_alloc on the other hand, can eiminate zone lock contention entirely, but has worse fragmentation issue.
[0] https://lwn.net/Articles/753058/
[1] https://lkml.kernel.org/r/[email protected]
[2] https://lkml.kernel.org/r/[email protected]
Aaron Lu (7):
mm: do not add anon pages to LRU
mm: convert zone lock from spinlock to rwlock mm/page_alloc: use helper functions to add/remove a page to/from buddy use atomic for free_area[order].nr_free
mm: use read_lock for free path
mm: use smp_list_splice() on free path
mm: page_alloc: merge before sending pages to global pool
Daniel Jordan (2):
mm: introduce smp_list_del for concurrent list entry removals
mm: introduce smp_list_splice to prepare for concurrent LRU adds
include/linux/list.h | 4 + include/linux/mm.h | 1 + include/linux/mmzone.h | 4 +- init/main.c | 1 + lib/Makefile | 2 +- lib/list.c | 227 ++++++++++++++++++++++++++++ mm/compaction.c | 90 +++++------ mm/hugetlb.c | 8 +- mm/memory.c | 2 +- mm/page_alloc.c | 332 ++++++++++++++++++++++++++++------------- mm/page_isolation.c | 12 +- mm/vmstat.c | 8 +- 12 files changed, 526 insertions(+), 165 deletions(-) create mode 100644 lib/list.c
Signature · 1 line
2.17.1
RFC PATCH 1/9 mm: do not add anon pages to LRU
For the sake of testing purpose, do not add anon pages to LRU to avoid LRU lock so we can test zone lock exclusively.
--- mm/memory.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
mm/memory.c +1 -1
@@ -3208,7 +3208,7 @@ static vm_fault_t do_anonymous_page(struct vm_fault *vmf)inc_mm_counter_fast (vma->vm_mm,MM_ANONPAGES );page_add_new_anon_rmap (page, vma, vmf->address, false);mem_cgroup_commit_charge (page, memcg, false, false); -lru_cache_add_active_or_unevictable (page, vma); +//lru_cache_add_active_or_unevictable(page, vma); setpte:set_pte_at (vma->vm_mm, vmf->address, vmf->pte, entry);
Signature · 1 line
2.17.1
RFC PATCH 2/9 mm: introduce smp_list_del for concurrent list entry removals
In reply to Aaron LuFrom: Daniel Jordan <[email protected]>
Now that the LRU lock is a RW lock, lay the groundwork for fine-grained synchronization so that multiple threads holding the lock as reader can safely remove pages from an LRU at the same time.
Add a thread-safe variant of list_del called smp_list_del that allows multiple threads to delete nodes from a list, and wrap this new list API in smp_del_page_from_lru to get the LRU statistics updates right.
For bisectability's sake, call the new function only when holding lru_lock as writer. In the next patch, switch to taking it as reader.
The algorithm is explained in detail in the comments. Yosef Lev conceived of the algorithm, and this patch is heavily based on an earlier version from him. Thanks to Dave Dice for suggesting the prefetch.
--- include/linux/list.h | 2 + lib/Makefile | 2 +- lib/list.c | 158 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 161 insertions(+), 1 deletion(-) create mode 100644 lib/list.c
include/linux/list.h +2 -0
@@ -47,6 +47,8 @@ static inline bool __list_del_entry_valid(struct list_head *entry) }#endif +extern void smp_list_del (struct list_head *entry); +/* * Insert a new entry between two known consecutive entries. *
lib/Makefile +1 -1
@@ -38,7 +38,7 @@ obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \ gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ percpu-refcount.o rhashtable.o reciprocal_div.o \ - once.o refcount.o usercopy.o errseq.o bucket_locks.o + once.o refcount.o usercopy.o errseq.o bucket_locks.o list.o obj-$(CONFIG_STRING_SELFTEST) += test_string.o obj-y += string_helpers.o obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
lib/list.c new file +158 -0
158 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH 3/9 mm: introduce smp_list_splice to prepare for concurrent LRU adds
In reply to Aaron LuFrom: Daniel Jordan <[email protected]>
Now that we splice a local list onto the LRU, prepare for multiple tasks doing this concurrently by adding a variant of the kernel's list splicing API, list_splice, that's designed to work with multiple tasks.
Although there is naturally less parallelism to be gained from locking the LRU head this way, the main benefit of doing this is to allow removals to happen concurrently. The way lru_lock is today, an add needlessly blocks removal of any page but the first in the LRU.
For now, hold lru_lock as writer to serialize the adds to ensure the function is correct for a single thread at a time.
Yosef Lev came up with this algorithm.
--- include/linux/list.h | 1 + lib/list.c | 60 ++++++++++++++++++++++++++++++++++++++------ 2 files changed, 54 insertions(+), 7 deletions(-)
include/linux/list.h +1 -0
@@ -48,6 +48,7 @@ static inline bool __list_del_entry_valid(struct list_head *entry)#endif extern void smp_list_del (struct list_head *entry); +extern void smp_list_splice (struct list_head *list,struct list_head *head);/* * Insert a new entry between two known consecutive entries.
lib/list.c +53 -7
73 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH 4/9 mm: convert zone lock from spinlock to rwlock
In reply to Aaron LuThis patch converts zone lock from spinlock to rwlock and always take the lock in write mode so there is no functionality change.
This is a preparation for free path to take the lock in read mode to make free path work concurrently.
compact_trylock and compact_unlock_should_abort are taken from Daniel Jordan's patch.
--- include/linux/mmzone.h | 2 +- mm/compaction.c | 90 +++++++++++++++++++++--------------------- mm/hugetlb.c | 8 ++-- mm/page_alloc.c | 52 ++++++++++++------------ mm/page_isolation.c | 12 +++--- mm/vmstat.c | 4 +- 6 files changed, 85 insertions(+), 83 deletions(-)
include/linux/mmzone.h +1 -1
@@ -465,7 +465,7 @@ struct zone {unsigned long flags;/* Primarily protects free_area */ -spinlock_t lock; +rwlock_t lock;/* Write-intensive fields used by compaction and vmstats. */ ZONE_PADDING (_pad2_)
mm/compaction.c +46 -44
132 lines not on this page · raw message
mm/hugetlb.c +4 -4
@@ -1113,7 +1113,7 @@ static struct page *alloc_gigantic_page(struct hstate *h, gfp_t gfp_mask, zonelist =node_zonelist (nid, gfp_mask);for_each_zone_zonelist_nodemask (zone, z, zonelist,gfp_zone (gfp_mask), nodemask) { -spin_lock_irqsave (&zone->lock, flags); +write_lock_irqsave (&zone->lock, flags); pfn =ALIGN (zone->zone_start_pfn, nr_pages);while (zone_spans_last_pfn (zone, pfn, nr_pages)) {
@@ -1125,16 +1125,16 @@ static struct page *alloc_gigantic_page(struct hstate *h, gfp_t gfp_mask,* spinning on this lock, it may win the race * and cause alloc_contig_range() to fail... */ -spin_unlock_irqrestore (&zone->lock, flags); +write_unlock_irqrestore (&zone->lock, flags); ret =__alloc_gigantic_page (pfn, nr_pages, gfp_mask);if (!ret)return pfn_to_page (pfn); -spin_lock_irqsave (&zone->lock, flags); +write_lock_irqsave (&zone->lock, flags); } pfn += nr_pages; } -spin_unlock_irqrestore (&zone->lock, flags); +write_unlock_irqrestore (&zone->lock, flags); }return NULL ;
mm/page_alloc.c +26 -26
204 lines not on this page · raw message
mm/page_isolation.c +6 -6
@@ -26,7 +26,7 @@ static int set_migratetype_isolate(struct page *page, int migratetype, zone =page_zone (page); -spin_lock_irqsave (&zone->lock, flags); +write_lock_irqsave (&zone->lock, flags);/* * We assume the caller intended to SET migrate type to isolate.
@@ -82,7 +82,7 @@ static int set_migratetype_isolate(struct page *page, int migratetype,__mod_zone_freepage_state (zone, -nr_pages, mt); } -spin_unlock_irqrestore (&zone->lock, flags); +write_unlock_irqrestore (&zone->lock, flags);if (!ret)drain_all_pages (zone);return ret;
@@ -98,7 +98,7 @@ static void unset_migratetype_isolate(struct page *page, unsigned migratetype)struct page *buddy; zone =page_zone (page); -spin_lock_irqsave (&zone->lock, flags); +write_lock_irqsave (&zone->lock, flags);if (!is_migrate_isolate_page (page)) goto out;
@@ -137,7 +137,7 @@ static void unset_migratetype_isolate(struct page *page, unsigned migratetype)set_pageblock_migratetype (page, migratetype); zone->nr_isolate_pageblock--; out: -spin_unlock_irqrestore (&zone->lock, flags); +write_unlock_irqrestore (&zone->lock, flags);if (isolated_page) {post_alloc_hook (page, order, __GFP_MOVABLE);__free_pages (page, order);
@@ -299,10 +299,10 @@ int test_pages_isolated(unsigned long start_pfn, unsigned long end_pfn,return -EBUSY ;/* Check all pages are free or marked as ISOLATED */ zone =page_zone (page); -spin_lock_irqsave (&zone->lock, flags); +write_lock_irqsave (&zone->lock, flags); pfn =__test_page_isolated_in_pageblock (start_pfn, end_pfn, skip_hwpoisoned_pages); -spin_unlock_irqrestore (&zone->lock, flags); +write_unlock_irqrestore (&zone->lock, flags);trace_test_pages_isolated (start_pfn, end_pfn, pfn);
mm/vmstat.c +2 -2
@@ -1337,10 +1337,10 @@ static void walk_zones_in_node(struct seq_file *m, pg_data_t *pgdat,continue ;if (!nolock) -spin_lock_irqsave (&zone->lock, flags); +write_lock_irqsave (&zone->lock, flags);if (!nolock) - spin_unlock_irqrestore(&zone->lock, flags); + write_unlock_irqrestore(&zone->lock, flags); } }#endif
Signature · 1 line
2.17.1
RFC PATCH 5/9 mm/page_alloc: use helper functions to add/remove a page to/from buddy
In reply to Aaron LuThere are multiple places that add/remove a page into/from buddy, introduce helper functions for them.
This also makes it easier to add code when a page is added/removed to/from buddy.
No functionality change.
--- mm/page_alloc.c | 65 +++++++++++++++++++++++++++++-------------------- 1 file changed, 39 insertions(+), 26 deletions(-)
mm/page_alloc.c +39 -26
@@ -697,12 +697,41 @@ static inline void set_page_order(struct page *page, unsigned int order)__SetPageBuddy (page); } +static inline void add_to_buddy_common (struct page *page,struct zone *zone, +unsigned int order) +{ +set_page_order (page, order); + zone->free_area[order].nr_free++; +} + +static inline void add_to_buddy_head (struct page *page,struct zone *zone, +unsigned int order,int mt) +{ +add_to_buddy_common (page, zone, order); +list_add (&page->lru, &zone->free_area[order].free_list[mt]); +} + +static inline void add_to_buddy_tail (struct page *page,struct zone *zone, +unsigned int order,int mt) +{ +add_to_buddy_common (page, zone, order); +list_add_tail (&page->lru, &zone->free_area[order].free_list[mt]); +} +static inline void rmv_page_order (struct page *page) {__ClearPageBuddy (page);set_page_private (page,0 ); } +static inline void remove_from_buddy (struct page *page,struct zone *zone, +unsigned int order) +{ +list_del (&page->lru); + zone->free_area[order].nr_free--; +rmv_page_order (page); +} +/* * This function checks whether a page is free && is the buddy * we can coalesce a page and its buddy if
@@ -803,13 +832,10 @@ static inline void __free_one_page(struct page *page,* Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page, * merge with it and move up one order. */ -if (page_is_guard (buddy)) { +if (page_is_guard (buddy))clear_page_guard (zone, buddy, order, migratetype); - }else { -list_del (&buddy->lru); - zone->free_area[order].nr_free--; -rmv_page_order (buddy); - } +else +remove_from_buddy (buddy, zone, order); combined_pfn = buddy_pfn & pfn; page = page + (combined_pfn - pfn); pfn = combined_pfn;
@@ -841,8 +867,6 @@ 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
@@ -859,15 +883,12 @@ static inline void __free_one_page(struct page *page, higher_buddy = higher_page + (buddy_pfn - combined_pfn);if (pfn_valid_within (buddy_pfn) &&page_is_buddy (higher_page, higher_buddy, order +1 )) { -list_add_tail (&page->lru, - &zone->free_area[order].free_list[migratetype]); - goto out; +add_to_buddy_tail (page, zone, order, migratetype); +return ; } } -list_add (&page->lru, &zone->free_area[order].free_list[migratetype]); -out: - zone->free_area[order].nr_free++; +add_to_buddy_head (page, zone, order, migratetype); }/*
@@ -1805,9 +1826,7 @@ static inline void expand(struct zone *zone, struct page *page,if (set_page_guard (zone, &page[size], high, migratetype))continue ; -list_add (&page[size].lru, &area->free_list[migratetype]); - area->nr_free++; -set_page_order (&page[size], high); +add_to_buddy_head (&page[size], zone, high, migratetype); } }
@@ -1951,9 +1970,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order, struct page, lru);if (!page)continue ; -list_del (&page->lru); -rmv_page_order (page); - area->nr_free--; +remove_from_buddy (page, zone, current_order);expand (zone, page, order, current_order, area, migratetype);set_pcppage_migratetype (page, migratetype);return page;
@@ -2871,9 +2888,7 @@ int __isolate_free_page(struct page *page, unsigned int order) }/* Remove page from free list */ -list_del (&page->lru); - zone->free_area[order].nr_free--; -rmv_page_order (page); +remove_from_buddy (page, zone, order);/* * Set the pageblock if the isolated page is at least half of a
@@ -8066,9 +8081,7 @@ __offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)pr_info ("remove from free list %lx %d %lx\n" , pfn,1 << order, end_pfn);#endif -list_del (&page->lru); -rmv_page_order (page); - zone->free_area[order].nr_free--; +remove_from_buddy (page, zone, order);for (i =0 ; i < (1 << order); i++)SetPageReserved ((page+i)); pfn += (1 << order);
Signature · 1 line
2.17.1
RFC PATCH 6/9 use atomic for free_area[order].nr_free
In reply to Aaron LuSince we will make free path run concurrently, free_area[].nr_free has to be atomic.
--- include/linux/mmzone.h | 2 +- mm/page_alloc.c | 12 ++++++------ mm/vmstat.c | 4 ++-- 3 files changed, 9 insertions(+), 9 deletions(-)
include/linux/mmzone.h +1 -1
@@ -95,7 +95,7 @@ extern int page_group_by_mobility_disabled;struct free_area {struct list_head free_list[MIGRATE_TYPES ]; -unsigned long nr_free; +atomic_long_t nr_free; };struct pglist_data ;
mm/page_alloc.c +6 -6
@@ -701,7 +701,7 @@ static inline void add_to_buddy_common(struct page *page, struct zone *zone, unsigned int order) {set_page_order (page, order); - zone->free_area[order].nr_free++; +atomic_long_inc (&zone->free_area[order].nr_free); } static inline void add_to_buddy_head(struct page *page, struct zone *zone,
@@ -728,7 +728,7 @@ static inline void remove_from_buddy(struct page *page, struct zone *zone, unsigned int order) {list_del (&page->lru); - zone->free_area[order].nr_free--; +atomic_long_dec (&zone->free_area[order].nr_free);rmv_page_order (page); }
@@ -2225,7 +2225,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,int i;int fallback_mt; -if (area->nr_free ==0 ) +if (atomic_long_read (&area->nr_free) ==0 )return -1 ; *can_steal = false;
@@ -3178,7 +3178,7 @@ bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,struct free_area *area = &z->free_area[o];int mt; -if (!area->nr_free) +if (atomic_long_read (&area->nr_free) ==0 )continue ;for (mt =0 ; mt <MIGRATE_PCPTYPES ; mt++) {
@@ -5029,7 +5029,7 @@ void show_free_areas(unsigned int filter, nodemask_t *nodemask)struct free_area *area = &zone->free_area[order];int type; - nr[order] = area->nr_free; + nr[order] =atomic_long_read (&area->nr_free); total += nr[order] << order; types[order] =0 ;
@@ -5562,7 +5562,7 @@ static void __meminit zone_init_free_lists(struct zone *zone)unsigned int order, t;for_each_migratetype_order (order, t) {INIT_LIST_HEAD (&zone->free_area[order].free_list[t]); - zone->free_area[order].nr_free =0 ; +atomic_long_set (&zone->free_area[order].nr_free,0 ); } }
mm/vmstat.c +2 -2
@@ -1030,7 +1030,7 @@ static void fill_contig_page_info(struct zone *zone,unsigned long blocks;/* Count number of free blocks */ - blocks = zone->free_area[order].nr_free; + blocks =atomic_long_read (&zone->free_area[order].nr_free); info->free_blocks_total += blocks;/* Count free base pages */
@@ -1353,7 +1353,7 @@ static void frag_show_print(struct seq_file *m, pg_data_t *pgdat,seq_printf (m,"Node %d, zone %8s " , pgdat->node_id, zone->name);for (order =0 ; order <MAX_ORDER ; ++order) -seq_printf (m,"%6lu " , zone->free_area[order].nr_free); +seq_printf (m,"%6lu " ,atomic_long_read (&zone->free_area[order].nr_free));seq_putc (m,'\n' ); }
Signature · 1 line
2.17.1
RFC PATCH 7/9 mm: use read_lock for free path
In reply to Aaron LuDaniel Jordan's patch has made it possible for multiple threads to operate on a global list with smp_list_del() at any position and smp_list_add/splice() at head position concurrently without taking any lock.
This patch makes use of this technique on free list. To make this happen, add_to_buddy_tail() is removed since only adding to list head is safe with smp_list_del() so only add_to_buddy() is used.
Once free path can run concurrently, it is possible for multiple threads to free pages at the same time. If 2 pages being freed are buddy, they can miss the oppotunity to be merged.
For this reason, introduce range locks to protect merge operation that makes sure inside one range, only one merge can happen and a page's Buddy status is properly set inside the lock. The range is selected as an order of (MAX_ORDER-1) pages since merge can't exceed that order.
--- include/linux/list.h | 1 + include/linux/mmzone.h | 3 ++ lib/list.c | 23 ++++++++++ mm/page_alloc.c | 95 +++++++++++++++++++++++------------------- 4 files changed, 78 insertions(+), 44 deletions(-)
include/linux/list.h +1 -0
@@ -49,6 +49,7 @@ static inline bool __list_del_entry_valid(struct list_head *entry)extern void smp_list_del (struct list_head *entry);extern void smp_list_splice (struct list_head *list,struct list_head *head); +extern void smp_list_add (struct list_head *entry,struct list_head *head);/* * Insert a new entry between two known consecutive entries.
include/linux/mmzone.h +3 -0
@@ -467,6 +467,9 @@ struct zone {/* Primarily protects free_area */ rwlock_t lock; +/* Protects merge operation for a range of order=(MAX_ORDER-1) pages */ +spinlock_t *range_locks; +/* Write-intensive fields used by compaction and vmstats. */ ZONE_PADDING (_pad2_)
lib/list.c +23 -0
@@ -202,3 +202,26 @@ void smp_list_splice(struct list_head *list, struct list_head *head)/* Simultaneously complete the splice and unlock the head node. */ WRITE_ONCE (head->next, first); } + +void smp_list_add (struct list_head *entry,struct list_head *head) +{ +struct list_head *succ; + +/* +* Lock the front of @head by replacing its next pointer with NULL. +* Should another thread be adding to the front, wait until it's done. +*/ + succ =READ_ONCE (head->next); +while (succ ==NULL ||cmpxchg (&head->next, succ,NULL ) != succ) { +cpu_relax (); + succ =READ_ONCE (head->next); + } + + entry->next = succ; + entry->prev = head; + succ->prev = entry; + +smp_wmb (); + +WRITE_ONCE (head->next, entry); +}
mm/page_alloc.c +51 -44
174 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH 8/9 mm: use smp_list_splice() on free path
In reply to Aaron LuWith free path running concurrently, the cache bouncing on free list head is severe since multiple threads can be freeing pages and each free will need to add the page to free list head.
To improve performance on free path for order-0 pages, we can choose to not add the merged pages to Buddy immediately after merge but keep them on a local percpu list first and then after all pages are finished merging, add these merged pages to Buddy with smp_list_splice() in one go.
This optimization caused a problem though: the page we hold on the local percpu list can be a buddy of other being freed page and we lose the merge oppotunity for them. With this patch, we will have mergable pages unmerged in Buddy.
Due to this, I don't see much value of keeping the range lock which is used to avoid such thing from happening, so the range lock is removed in this patch.
--- include/linux/mm.h | 1 + include/linux/mmzone.h | 3 - init/main.c | 1 + mm/page_alloc.c | 151 +++++++++++++++++++++++++---------------- 4 files changed, 95 insertions(+), 61 deletions(-)
include/linux/mm.h +1 -0
@@ -2155,6 +2155,7 @@ extern void memmap_init_zone(unsigned long, int, unsigned long, unsigned long,extern void setup_per_zone_wmarks (void );extern int __meminit init_per_zone_wmark_min (void );extern void mem_init (void ); +extern void percpu_mergelist_init (void );extern void __init mmap_init (void );extern void show_mem (unsigned int flags,nodemask_t *nodemask);extern long si_mem_available (void );
include/linux/mmzone.h +0 -3
@@ -467,9 +467,6 @@ struct zone {/* Primarily protects free_area */ rwlock_t lock; -/* Protects merge operation for a range of order=(MAX_ORDER-1) pages */ -spinlock_t *range_locks; -/* Write-intensive fields used by compaction and vmstats. */ ZONE_PADDING (_pad2_)
init/main.c +1 -0
@@ -517,6 +517,7 @@ static void __init mm_init(void)* bigger than MAX_ORDER unless SPARSEMEM. */ page_ext_init_flatmem (); +percpu_mergelist_init ();mem_init ();kmem_cache_init ();pgtable_init ();
mm/page_alloc.c +93 -58
231 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH 9/9 mm: page_alloc: merge before sending pages to global pool
In reply to Aaron LuNow that we have mergable pages in Buddy unmerged, this is a step to reduce such things from happening to some extent.
Suppose two buddy pages are on the list to be freed in free_pcppages_bulk(), the first page goes to merge but its buddy is not in Buddy yet so we hold it locally as an order0 page; then its buddy page goes to merge and couldn't merge either because we hold the first page locally instead of having it in Buddy. The end result is, we have two mergable buddy pages but failed to merge it.
So this patch will attempt merge for these to-be-freed pages before acquiring any lock, it could, to some extent, reduce fragmentation caused by last patch.
With this change, the pcp_drain trace isn't easy to use so I removed it.
--- mm/page_alloc.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 73 insertions(+), 2 deletions(-)
mm/page_alloc.c +73 -2
@@ -1098,6 +1098,72 @@ void __init percpu_mergelist_init(void) } } +static inline bool buddy_in_list (struct page *page,struct page *buddy, +struct list_head *list) +{ +list_for_each_entry_continue (page, list, lru) +if (page == buddy) +return true; + +return false; +} + +static inline void merge_in_pcp (struct list_head *list) +{ +int order; +struct page *page; + +/* Set order information to 0 initially since they are PCP pages */ +list_for_each_entry (page, list, lru) +set_page_private (page,0 ); + +/* +* Check for mergable pages for each order. +* +* For each order, check if their buddy is also in the list and +* if so, do merge, then remove the merged buddy from the list. +*/ +for (order =0 ; order <MAX_ORDER -1 ; order++) { +bool has_merge = false; + + page = list_first_entry(list, struct page, lru); +while (&page->lru != list) { +unsigned long pfn, buddy_pfn, combined_pfn; +struct page *buddy, *n; + +if (page_order (page) != order) { + page =list_next_entry (page, lru); +continue ; + } + + pfn =page_to_pfn (page); + buddy_pfn =__find_buddy_pfn (pfn, order); + buddy = page + (buddy_pfn - pfn); +if (!buddy_in_list (page, buddy, list) || +page_order (buddy) != order) { + page =list_next_entry (page, lru); +continue ; + } + + combined_pfn = pfn & buddy_pfn; +if (combined_pfn == pfn) { +set_page_private (page, order +1 ); +list_del (&buddy->lru); + page =list_next_entry (page, lru); + }else { +set_page_private (buddy, order +1 ); + n =list_next_entry (page, lru); +list_del (&page->lru); + page = n; + } + has_merge = true; + } + +if (!has_merge) +break ; + } +} +/* * Frees a number of pages from the PCP lists * Assumes all pages on list are in same zone, and of same order.
@@ -1165,6 +1231,12 @@ static void free_pcppages_bulk(struct zone *zone, int count, }while (--count && --batch_free && !list_empty (list)); } +/* +* Before acquiring the possibly heavily contended zone lock, do merge +* among these to-be-freed PCP pages before sending them to Buddy. +*/ +merge_in_pcp (&head); +read_lock (&zone->lock); isolated_pageblocks =has_isolate_pageblock (zone);
@@ -1182,10 +1254,9 @@ static void free_pcppages_bulk(struct zone *zone, int count,if (unlikely (isolated_pageblocks)) mt =get_pageblock_migratetype (page); - order =0 ; + order =page_order (page); merged_page =do_merge (page,page_to_pfn (page), zone, &order, mt);list_add (&merged_page->lru,this_cpu_ptr (&merge_lists[order][mt])); -trace_mm_page_pcpu_drain (page,0 , mt); }for_each_migratetype_order (order, migratetype) {
Signature · 1 line
2.17.1
Quoted 7 lines · Aaron Lu
Daniel Jordan and others proposed an innovative technique to make multiple threads concurrently use
list_del()at any position of the list andlist_add()at head position of the list without taking a lock in this year's MM summit[0].People think this technique may be useful to improve zone lock scalability so here is my try.
Nice, this uses the smp_list_* functions well in spite of the limitations you encountered with them here.
Quoted 8 lines
Performance wise on 56 cores/112 threads Intel Skylake 2 sockets server using will-it-scale/page_fault1 process mode(higher is better):
kernel performance zone lock contention patch1 9219349 76.99% patch7 2461133 -73.3% 54.46%(another 34.66% on smp_list_add()) patch8 11712766 +27.0% 68.14% patch9 11386980 +23.5% 67.18%
Is "zone lock contention" the percentage that readers and writers combined spent waiting? I'm curious to see read and write wait time broken out, since it seems there are writers (very likely on the allocation side) spoiling the parallelism we get with the read lock.
If the contention is from allocation, I wonder whether it's feasible to make that path use SMP list functions. Something like smp_list_cut_position combined with using page clusters from [*] to cut off a chunk of list. Many details to keep in mind there, though, like having to unset PageBuddy in that list chunk when other tasks can be concurrently merging pages that are part of it.
Or maybe what's needed is a more scalable data structure than an array of lists, since contention on the heads seems to be the limiting factor. A simple list that keeps the pages in most-recently-used order (except when adding to the list tail) is good for cache warmth, but I wonder how helpful that is when all CPUs can allocate from the front. Having multiple places to put pages of a given order/mt would ease the contention.
Quoted 4 lines
Though lock contention reduced a lot for patch7, the performance dropped considerably due to severe cache bouncing on free list head among multiple threads doing page free at the same time, because every page free will need to add the page to the free list head.
Could be beneficial to take an MCS-style approach in smp_list_splice/add so that multiple waiters aren't bouncing the same cacheline around. This is something I'm planning to try on lru_lock.
Daniel
Quoted 21 lines · Daniel Jordan
Quoted 7 lines · Aaron Lu
Daniel Jordan and others proposed an innovative technique to make multiple threads concurrently use
list_del()at any position of the list andlist_add()at head position of the list without taking a lock in this year's MM summit[0].People think this technique may be useful to improve zone lock scalability so here is my try.
Nice, this uses the smp_list_* functions well in spite of the limitations you encountered with them here.
Quoted 8 lines
Performance wise on 56 cores/112 threads Intel Skylake 2 sockets server using will-it-scale/page_fault1 process mode(higher is better):
kernel performance zone lock contention patch1 9219349 76.99% patch7 2461133 -73.3% 54.46%(another 34.66% on smp_list_add()) patch8 11712766 +27.0% 68.14% patch9 11386980 +23.5% 67.18%
Quoted 4 lines
Is "zone lock contention" the percentage that readers and writers combined spent waiting? I'm curious to see read and write wait time broken out, since it seems there are writers (very likely on the allocation side) spoiling the parallelism we get with the read lock.
lock contention is combined, read side consumes about 31% while write side consumes 35%. Write side definitely is blocking read side.
I also tried not taking lock in read mode on free path to avoid free path blocking on allocation path, but that caused other unplesant consequences for allocation path, namely the free_list head->next can be NULL when allocating pages due to free path can be adding pages to the list using smp_list_add/splice so I had to use free_list head->prev instead to fetch pages on allocation path. Also, the fetched page can be merged in the mean time on free path so need to confirm if it is really usable, etc. This complicated allocation path and didn't deliver good results so I gave up this idea.
Quoted 6 lines
If the contention is from allocation, I wonder whether it's feasible to make that path use SMP list functions. Something like
smp_list_cut_positioncombined with using page clusters from [*] to cut off a chunk of list. Many details to keep in mind there, though, like having to unset PageBuddy in that list chunk when other tasks can be concurrently merging pages that are part of it.
As you put here, the PageBuddy flag is a problem. If I cut off a batch of pages from free_list and then dropping the lock, these pages will have PageBuddy flag set and free path can attempt a merge with any of these pages and cause problems.
PageBuddy flag can not be cleared with lock held since that would require accessing 'struct page's for these pages and it is the most time consuming part among all operations that happened on allocation path under zone lock.
This is doable in your referenced no_merge+cluster_alloc approach because we skipped merge most of the time. And when merge really needs to happen like in compaction, cluser_alloc will be disabled.
Quoted 6 lines
Or maybe what's needed is a more scalable data structure than an array of lists, since contention on the heads seems to be the limiting factor. A simple list that keeps the pages in most-recently-used order (except when adding to the list tail) is good for cache warmth, but I wonder how helpful that is when all CPUs can allocate from the front. Having multiple places to put pages of a given order/mt would ease the contention.
Agree.
Quoted 8 lines
Quoted 4 lines
Though lock contention reduced a lot for patch7, the performance dropped considerably due to severe cache bouncing on free list head among multiple threads doing page free at the same time, because every page free will need to add the page to the free list head.
Could be beneficial to take an MCS-style approach in smp_list_splice/add so that multiple waiters aren't bouncing the same cacheline around. This is something I'm planning to try on
lru_lock.
That's a good idea.
If that is done, we can at least parallelise free path and gain something by not paying the penalty of cache bouncing on list head.
Quoted 4 lines
Daniel
And thanks a lot for the comments!