Fragmentation Avoidance V19

Hi Andrew,

This is the latest release of the fragmentation avoidance patches with no code changes since v18. If it is possible, I would like to get this into -mm, so this patch is generated against the latest -mm tree 2.6.14-rc5-mm1 and is known to apply cleanly. If there is another tree that should be diffed against instead, just say so and I'll send another version.

Here are a few brief reasons why this set of patches is useful;

o Reduced fragmentation improves the chance a large order allocation succeeds
o General-purpose memory hotplug needs the page/memory groupings provided
o Reduces the number of badly-placed pages that page migration mechanism must deal with. This also applies to any active page defragmentation mechanism.
o This patch is a pre-requisite for a linear scanning mechanism that could be used to guarantee large-page allocations

Built and tested successfully on a single processor AMD machine, quad processor Xeon machine and PPC64. Benchmarks are generated on the Xeon machine.

Changelog since v18
o Resync against 2.6.14-rc5-mm1
o 004_markfree dropped
o Documentation note added on the behavior of free_area.nr_free

Changelog since v17
o Update to 2.6.14-rc4-mm1
o Remove explicit casts where implicit casts were in place
o Change __GFP_USER to __GFP_EASYRCLM, RCLM_USER to RCLM_EASY and PCPU_USER to PCPU_EASY
o Print a warning and return NULL if both RCLM flags are set in the GFP flags
o Reduce size of fallback_allocs
o Change magic number 64 to FREE_AREA_USEMAP_SIZE
o CodingStyle regressions cleanup
o Move sparsemen setup_usemap() out of header
o Changed fallback_balance to a mechanism that depended on zone->present_pages to avoid hotplug problems later
o Many superflous parenthesis removed

Changlog since v16
o Variables using bit operations now are unsigned long. Note that when used as indices, they are integers and cast to unsigned long when necessary. This is because aim9 shows regressions when used as unsigned longs throughout (~10% slowdown)
o 004_showfree added to provide more debugging information
o 008_stats dropped. Even with CONFIG_ALLOCSTATS disabled, it is causing severe performance regressions. No explanation as to why
o for_each_rclmtype_order moved to header
o More coding style cleanups

Changelog since V14 (V15 not released)
o Update against 2.6.14-rc3
o Resync with Joel's work. All suggestions made on fix-ups to his last set of patches should also be in here. e.g. __GFP_USER is still __GFP_USER but is better commented.
o Large amount of CodingStyle, readability cleanups and corrections pointed out by Dave Hansen.
o Fix CONFIG_NUMA error that corrupted per-cpu lists
o Patches broken out to have one-feature-per-patch rather than more-code-per-patch
o Fix fallback bug where pages for RCLM_NORCLM end up on random other free lists.

Changelog since V13
o Patches are now broken out
o Added per-cpu draining of userrclm pages
o Brought the patch more in line with memory hotplug work
o Fine-grained use of the __GFP_USER and __GFP_KERNRCLM flags
o Many coding-style corrections
o Many whitespace-damage corrections

Changelog since V12
o Minor whitespace damage fixed as pointed by Joel Schopp

Changelog since V11
o Mainly a redefiff against 2.6.12-rc5
o Use #defines for indexing into pcpu lists
o Fix rounding error in the size of usemap

Changelog since V10
o All allocation types now use per-cpu caches like the standard allocator
o Removed all the additional buddy allocator statistic code
o Elimated three zone fields that can be lived without
o Simplified some loops
o Removed many unnecessary calculations

Changelog since V9
o Tightened what pools are used for fallbacks, less likely to fragment
o Many micro-optimisations to have the same performance as the standard allocator. Modified allocator now faster than standard allocator using gcc 3.3.5
o Add counter for splits/coalescing

Changelog since V8
o rmqueue_bulk() allocates pages in large blocks and breaks it up into the requested size. Reduces the number of calls to __rmqueue()
o Beancounters are now a configurable option under "Kernel Hacking"
o Broke out some code into inline functions to be more Hotplug-friendly
o Increased the size of reserve for fallbacks from 10% to 12.5%.

Changelog since V7
o Updated to 2.6.11-rc4
o Lots of cleanups, mainly related to beancounters
o Fixed up a miscalculation in the bitmap size as pointed out by Mike Kravetz (thanks Mike)
o Introduced a 10% reserve for fallbacks. Drastically reduces the number of kernnorclm allocations that go to the wrong places
o Don't trigger OOM when large allocations are involved

Changelog since V6
o Updated to 2.6.11-rc2
o Minor change to allow prezeroing to be a cleaner looking patch

Changelog since V5
o Fixed up gcc-2.95 errors
o Fixed up whitespace damage

Changelog since V4
o No changes. Applies cleanly against 2.6.11-rc1 and 2.6.11-rc1-bk6. Applies with offsets to 2.6.11-rc1-mm1

Changelog since V3
o inlined get_pageblock_type() and set_pageblock_type()
o set_pageblock_type() now takes a zone parameter to avoid a call to page_zone()
o When taking from the global pool, do not scan all the low-order lists

Changelog since V2
o Do not to interfere with the "min" decay
o Update the __GFP_BITS_SHIFT properly. Old value broke fsync and probably anything to do with asynchronous IO

Changelog since V1
o Update patch to 2.6.11-rc1
o Cleaned up bug where memory was wasted on a large bitmap
o Remove code that needed the binary buddy bitmaps
o Update flags to avoid colliding with __GFP_ZERO changes
o Extended fallback_count bean counters to show the fallback count for each allocation type
o In-code documentation

Version 1
o Initial release against 2.6.9

This patch is designed to reduce fragmentation in the standard buddy allocator without impairing the performance of the allocator. High fragmentation in the standard binary buddy allocator means that high-order allocations can rarely be serviced. This patch works by dividing allocations into three different types of allocations;

EasyReclaimable - These are userspace pages that are easily reclaimable. This
flag is set when it is known that the pages will be trivially reclaimed by writing the page out to swap or syncing with backing storage

KernelReclaimable - These are pages allocated by the kernel that are easily
reclaimed. This is stuff like inode caches, dcache, buffer_heads etc. These type of pages potentially could be reclaimed by dumping the caches and reaping the slabs

KernelNonReclaimable - These are pages that are allocated by the kernel that
are not trivially reclaimed. For example, the memory allocated for a loaded module would be in this category. By default, allocations are considered to be of this type

Instead of having one global MAX_ORDER-sized array of free lists, there are four, one for each type of allocation and another reserve for fallbacks.

Once a 2^MAX_ORDER block of pages it split for a type of allocation, it is added to the free-lists for that type, in effect reserving it. Hence, over time, pages of the different types can be clustered together. This means that if 2^MAX_ORDER number of pages were required, the system could linearly scan a block of pages allocated for EasyReclaimable and page each of them out.

Fallback is used when there are no 2^MAX_ORDER pages available and there are no free pages of the desired type. The fallback lists were chosen in a way that keeps the most easily reclaimable pages together.

Three benchmark results are included all based on a 2.6.14-rc3 kernel compiled with gcc 3.4 (it is known that gcc 2.95 produces different results). The first is the output of portions of AIM9 for the vanilla allocator and the modified one;

(Tests run with bench-aim9.sh from VMRegress 0.17) 2.6.14-rc5-mm1-clean
------------------------------------------------------------------------------------------------------------
Test Test Elapsed Iteration Iteration Operation
Number Name Time (sec) Count Rate (loops/sec) Rate (ops/sec)
------------------------------------------------------------------------------------------------------------

     1 creat-clo           60.04        961   16.00600        16006.00 File Creations and Closes/second
     2 page_test           60.02       4149   69.12696       117515.83 System Allocations & Pages/second
     3 brk_test            60.04       1555   25.89940       440289.81 System Memory Allocations/second
     4 jmp_test            60.00     250768 4179.46667      4179466.67 Non-local gotos/second
     5 signal_test         60.01       4849   80.80320        80803.20 Signal Traps/second
     6 exec_test           60.00        741   12.35000           61.75 Program Loads/second
     7 fork_test           60.06        797   13.27006         1327.01 Task Creations/second
     8 link_test           60.01       5269   87.80203         5531.53 Link/Unlink Pairs/second

2.6.14-rc3-mbuddy-v19
------------------------------------------------------------------------------------------------------------
Test Test Elapsed Iteration Iteration Operation
Number Name Time (sec) Count Rate (loops/sec) Rate (ops/sec)
------------------------------------------------------------------------------------------------------------

     1 creat-clo           60.04        954   15.88941        15889.41 File Creations and Closes/second
     2 page_test           60.01       4133   68.87185       117082.15 System Allocations & Pages/second
     3 brk_test            60.02       1546   25.75808       437887.37 System Memory Allocations/second
     4 jmp_test            60.00     250797 4179.95000      4179950.00 Non-local gotos/second
     5 signal_test         60.01       5121   85.33578        85335.78 Signal Traps/second
     6 exec_test           60.00        743   12.38333           61.92 Program Loads/second
     7 fork_test           60.05        806   13.42215         1342.21 Task Creations/second
     8 link_test           60.00       5291   88.18333         5555.55 Link/Unlink Pairs/second

Difference in performance operations report generated by diff-aim9.sh

                   Clean   mbuddy-v19
                ---------- ----------
 1 creat-clo      16006.00   15889.41    -116.59 -0.73% File Creations and Closes/second
 2 page_test     117515.83  117082.15    -433.68 -0.37% System Allocations & Pages/second
 3 brk_test      440289.81  437887.37   -2402.44 -0.55% System Memory Allocations/second
 4 jmp_test     4179466.67 4179950.00     483.33  0.01% Non-local gotos/second
 5 signal_test    80803.20   85335.78    4532.58  5.61% Signal Traps/second
 6 exec_test         61.75      61.92       0.17  0.28% Program Loads/second
 7 fork_test       1327.01    1342.21      15.20  1.15% Task Creations/second
 8 link_test       5531.53    5555.55      24.02  0.43% Link/Unlink Pairs/second

In this test, there were small regressions in the page_test. However, it is known that different kernel configurations, compilers and even different runs show similar varianes of +/- 3% .

The second benchmark tested the CPU cache usage to make sure it was not getting clobbered. The test was to repeatedly render a large postscript file 10 times and get the average. The result is;

2.6.14-rc5-mm1-clean: Average: 43.254 real, 38.89 user, 0.042 sys
2.6.14-rc5-mm1-mbuddy-v19: Average: 43.212 real, 40.494 user, 0.044 sys

So there are no adverse cache effects. The last test is to show that the allocator can satisfy more high-order allocations, especially under load, than the standard allocator. The test performs the following;

1. Start updatedb running in the background
2. Load kernel modules that tries to allocate high-order blocks on demand
3. Clean a kernel tree
4. Make 6 copies of the tree. As each copy finishes, a compile starts at -j2
5. Start compiling the primary tree
6. Sleep 1 minute while the 7 trees are being compiled
7. Use the kernel module to attempt 160 times to allocate a 2^10 block of pages
- note, it only attempts 160 times, no matter how often it succeeds
- An allocation is attempted every 1/10th of a second
- Performance will get badly shot as it forces considerable amounts of pageout

The result of the allocations under load (load averaging 18) were;

2.6.14-rc5-mm1 Clean

Order:                 10
Allocation type:       HighMem
Attempted allocations: 160
Success allocs:        30
Failed allocs:         130
DMA zone allocs:       0
Normal zone allocs:    7
HighMem zone allocs:   23

% Success: 18

2.6.14-rc5-mm1 MBuddy V19

Order:                 10
Allocation type:       HighMem
Attempted allocations: 160
Success allocs:        76
Failed allocs:         84
DMA zone allocs:       1
Normal zone allocs:    30
HighMem zone allocs:   45

% Success: 47

One thing that had to be changed in the 2.6.14-rc5-mm1 clean test was to disable the OOM killer. During one test, the OOM killer had better results but invoked the OOM killer a very large number of times to achieve it. The patch with the placement policy never invoked the OOM killer.

The above results are not very dramatic but the affect is very noticeable when the system is at rest after the test completes. After the test, the standard allocator was able to allocate 45 order-10 pages and the modified allocator allocated 159. The ability to allocate large pages under load depend heavily on the decisions of kswapd so there can be large variances in results but that is a separate problem. It is also known that the success of large allocations is also dependant on the location of per-cpu pages but fixing that problem is a separate issue.

The results show that the modified allocator has comparable speed, has no adverse cache effects but is far less fragmented and in a better position to satisfy high-order allocations.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

This patch adds two flags __GFP_EASYRCLM and __GFP_KERNRCLM that are used to trap the type of allocation the caller is made. Allocations using the __GFP_EASYRCLM flag are expected to be easily reclaimed by syncing with backing storage (be it a file or swap) or cleaning the buffers and discarding. Allocations using the __GFP_KERNRCLM flag belong to slab caches that can be shrunk by the kernel.

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/buffer.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/buffer.c
@@ -1119,7 +1119,8 @@ grow_dev_page(struct block_device *bdev,
 	struct page *page;
 	struct buffer_head *bh;
 
-	page = find_or_create_page(inode->i_mapping, index, GFP_NOFS);
+	page = find_or_create_page(inode->i_mapping, index,
+				   GFP_NOFS|__GFP_EASYRCLM);
 	if (!page)
 		return NULL;
 

@@ -3058,7 +3059,8 @@ static void recalc_bh_state(void)
 	
 struct buffer_head *alloc_buffer_head(gfp_t gfp_flags)
 {
-	struct buffer_head *ret = kmem_cache_alloc(bh_cachep, gfp_flags);
+	struct buffer_head *ret = kmem_cache_alloc(bh_cachep,
+						   gfp_flags|__GFP_KERNRCLM);
 	if (ret) {
 		get_cpu_var(bh_accounting).nr++;
 		recalc_bh_state();

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/compat.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/compat.c
@@ -1363,7 +1363,7 @@ static int compat_copy_strings(int argc,
 			page = bprm->page[i];
 			new = 0;
 			if (!page) {
-				page = alloc_page(GFP_HIGHUSER);
+				page = alloc_page(GFP_HIGHUSER|__GFP_EASYRCLM);
 				bprm->page[i] = page;
 				if (!page) {
 					ret = -ENOMEM;

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/dcache.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/dcache.c
@@ -878,7 +878,7 @@ struct dentry *d_alloc(struct dentry * p
 	struct dentry *dentry;
 	char *dname;
 
-	dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL); 
+	dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL|__GFP_KERNRCLM);
 	if (!dentry)
 		return NULL;
 

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/exec.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/exec.c
@@ -237,7 +237,7 @@ static int copy_strings(int argc, char _
 			page = bprm->page[i];
 			new = 0;
 			if (!page) {
-				page = alloc_page(GFP_HIGHUSER);
+				page = alloc_page(GFP_HIGHUSER|__GFP_EASYRCLM);
 				bprm->page[i] = page;
 				if (!page) {
 					ret = -ENOMEM;

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/ext2/super.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/ext2/super.c
@@ -141,7 +141,8 @@ static kmem_cache_t * ext2_inode_cachep;
 static struct inode *ext2_alloc_inode(struct super_block *sb)
 {
 	struct ext2_inode_info *ei;
-	ei = (struct ext2_inode_info *)kmem_cache_alloc(ext2_inode_cachep, SLAB_KERNEL);
+	ei = (struct ext2_inode_info *)kmem_cache_alloc(ext2_inode_cachep,
+						SLAB_KERNEL|__GFP_KERNRCLM);
 	if (!ei)
 		return NULL;
 #ifdef CONFIG_EXT2_FS_POSIX_ACL

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/ext3/super.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/ext3/super.c
@@ -444,7 +444,7 @@ static struct inode *ext3_alloc_inode(st
 {
 	struct ext3_inode_info *ei;
 
-	ei = kmem_cache_alloc(ext3_inode_cachep, SLAB_NOFS);
+	ei = kmem_cache_alloc(ext3_inode_cachep, SLAB_NOFS|__GFP_KERNRCLM);
 	if (!ei)
 		return NULL;
 #ifdef CONFIG_EXT3_FS_POSIX_ACL

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/inode.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/inode.c
@@ -146,7 +146,7 @@ static struct inode *alloc_inode(struct 
 		mapping->a_ops = &empty_aops;
  		mapping->host = inode;
 		mapping->flags = 0;
-		mapping_set_gfp_mask(mapping, GFP_HIGHUSER);
+		mapping_set_gfp_mask(mapping, GFP_HIGHUSER|__GFP_EASYRCLM);
 		mapping->assoc_mapping = NULL;
 		mapping->backing_dev_info = &default_backing_dev_info;
 

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/fs/ntfs/inode.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/fs/ntfs/inode.c
@@ -318,7 +318,7 @@ struct inode *ntfs_alloc_big_inode(struc
 	ntfs_inode *ni;
 
 	ntfs_debug("Entering.");
-	ni = kmem_cache_alloc(ntfs_big_inode_cache, SLAB_NOFS);
+	ni = kmem_cache_alloc(ntfs_big_inode_cache, SLAB_NOFS|__GFP_KERNRCLM);
 	if (likely(ni != NULL)) {
 		ni->state = 0;
 		return VFS_I(ni);

@@ -343,7 +343,7 @@ static inline ntfs_inode *ntfs_alloc_ext
 	ntfs_inode *ni;
 
 	ntfs_debug("Entering.");
-	ni = kmem_cache_alloc(ntfs_inode_cache, SLAB_NOFS);
+	ni = kmem_cache_alloc(ntfs_inode_cache, SLAB_NOFS|__GFP_KERNRCLM);
 	if (likely(ni != NULL)) {
 		ni->state = 0;
 		return ni;

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/include/asm-i386/page.h linux-2.6.14-rc5-mm1-001_antidefrag_flags/include/asm-i386/page.h
@@ -36,7 +36,8 @@
 #define clear_user_page(page, vaddr, pg)	clear_page(page)
 #define copy_user_page(to, from, vaddr, pg)	copy_page(to, from)
 
-#define alloc_zeroed_user_highpage(vma, vaddr) alloc_page_vma(GFP_HIGHUSER | __GFP_ZERO, vma, vaddr)
+#define alloc_zeroed_user_highpage(vma, vaddr) \
+	alloc_page_vma(GFP_HIGHUSER | __GFP_ZERO | __GFP_EASYRCLM, vma, vaddr)
 #define __HAVE_ARCH_ALLOC_ZEROED_USER_HIGHPAGE
 
 /*

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/include/linux/gfp.h linux-2.6.14-rc5-mm1-001_antidefrag_flags/include/linux/gfp.h
@@ -50,14 +50,27 @@ struct vm_area_struct;
 #define __GFP_HARDWALL   0x40000u /* Enforce hardwall cpuset memory allocs */
 #define __GFP_VALID	0x80000000u /* valid GFP flags */
 
-#define __GFP_BITS_SHIFT 20	/* Room for 20 __GFP_FOO bits */
+/*
+ * Allocation type modifiers, these are required to be adjacent
+ * __GFP_EASYRCLM: Easily reclaimed pages like userspace or buffer pages
+ * __GFP_KERNRCLM: Short-lived or reclaimable kernel allocation
+ * Both bits off: Kernel non-reclaimable or very hard to reclaim
+ * __GFP_EASYRCLM and __GFP_KERNRCLM should not be specified at the same time
+ * RCLM_SHIFT (defined elsewhere) depends on the location of these bits
+ */
+#define __GFP_EASYRCLM   0x80000u  /* User and other easily reclaimed pages */
+#define __GFP_KERNRCLM   0x100000u /* Kernel page that is reclaimable */
+#define __GFP_RCLM_BITS  (__GFP_EASYRCLM|__GFP_KERNRCLM)
+
+#define __GFP_BITS_SHIFT 21	/* Room for 21 __GFP_FOO bits */
 #define __GFP_BITS_MASK ((1 << __GFP_BITS_SHIFT) - 1)
 
 /* if you forget to add the bitmask here kernel will crash, period */
 #define GFP_LEVEL_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS| \
 			__GFP_COLD|__GFP_NOWARN|__GFP_REPEAT| \
 			__GFP_NOFAIL|__GFP_NORETRY|__GFP_NO_GROW|__GFP_COMP| \
-			__GFP_NOMEMALLOC|__GFP_NORECLAIM|__GFP_HARDWALL)
+			__GFP_NOMEMALLOC|__GFP_NORECLAIM|__GFP_HARDWALL| \
+			__GFP_EASYRCLM|__GFP_KERNRCLM)
 
 #define GFP_ATOMIC	(__GFP_VALID | __GFP_HIGH)
 #define GFP_NOIO	(__GFP_VALID | __GFP_WAIT)

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/include/linux/highmem.h linux-2.6.14-rc5-mm1-001_antidefrag_flags/include/linux/highmem.h
@@ -47,7 +47,8 @@ static inline void clear_user_highpage(s
 static inline struct page *
 alloc_zeroed_user_highpage(struct vm_area_struct *vma, unsigned long vaddr)
 {
-	struct page *page = alloc_page_vma(GFP_HIGHUSER, vma, vaddr);
+	struct page *page = alloc_page_vma(GFP_HIGHUSER|__GFP_EASYRCLM,
+							vma, vaddr);
 
 	if (page)
 		clear_user_highpage(page, vaddr);

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/mm/memory.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/mm/memory.c
@@ -1295,7 +1295,8 @@ static int do_wp_page(struct mm_struct *
 		if (!new_page)
 			goto oom;
 	} else {
-		new_page = alloc_page_vma(GFP_HIGHUSER, vma, address);
+		new_page = alloc_page_vma(GFP_HIGHUSER|__GFP_EASYRCLM,
+							vma, address);
 		if (!new_page)
 			goto oom;
 		copy_user_highpage(new_page, old_page, address);

@@ -1858,7 +1859,8 @@ retry:
 
 		if (unlikely(anon_vma_prepare(vma)))
 			goto oom;
-		page = alloc_page_vma(GFP_HIGHUSER, vma, address);
+		page = alloc_page_vma(GFP_HIGHUSER|__GFP_EASYRCLM,
+							vma, address);
 		if (!page)
 			goto oom;
 		copy_user_highpage(page, new_page, address);

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/mm/shmem.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/mm/shmem.c
@@ -906,7 +906,7 @@ shmem_alloc_page(unsigned long gfp, stru
 	pvma.vm_policy = mpol_shared_policy_lookup(&info->policy, idx);
 	pvma.vm_pgoff = idx;
 	pvma.vm_end = PAGE_SIZE;
-	page = alloc_page_vma(gfp | __GFP_ZERO, &pvma, 0);
+	page = alloc_page_vma(gfp | __GFP_ZERO | __GFP_EASYRCLM, &pvma, 0);
 	mpol_free(pvma.vm_policy);
 	return page;
 }

@@ -921,7 +921,7 @@ shmem_swapin(struct shmem_inode_info *in
 static inline struct page *
 shmem_alloc_page(gfp_t gfp,struct shmem_inode_info *info, unsigned long idx)
 {
-	return alloc_page(gfp | __GFP_ZERO);
+	return alloc_page(gfp | __GFP_ZERO | __GFP_EASYRCLM);
 }
 #endif
 

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-clean/mm/swap_state.c linux-2.6.14-rc5-mm1-001_antidefrag_flags/mm/swap_state.c
@@ -341,7 +341,8 @@ struct page *read_swap_cache_async(swp_e
 		 * Get a new page to read into from swap.
 		 */
 		if (!new_page) {
-			new_page = alloc_page_vma(GFP_HIGHUSER, vma, addr);
+			new_page = alloc_page_vma(GFP_HIGHUSER|__GFP_EASYRCLM,
+							vma, addr);
 			if (!new_page)
 				break;		/* Out of memory */
 		}

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

This patch adds a "usemap" to the allocator. When a PAGE_PER_MAXORDER block of pages (i.e. 2^(MAX_ORDER-1)) is split, the usemap is updated with the type of allocation when splitting. This information is used in an anti-fragmentation patch to group related allocation types together.

The __GFP_EASYRCLM and __GFP_KERNRCLM bits are used to enumerate three allocation types;

RCLM_NORLM: These are kernel allocations that cannot be reclaimed
on demand.
RCLM_EASY: These are pages allocated with __GFP_EASYRCLM flag set. They are
considered to be user and other easily reclaimed pages such as buffers
RCLM_KERN: Allocated for the kernel but for caches that can be reclaimed
on demand.

gfpflags_to_rclmtype() converts gfp_flags to their corresponding RCLM_TYPE by masking out irrelevant bits and shifting the result right by RCLM_SHIFT. Compile-time checks are made on RCLM_SHIFT to ensure gfpflags_to_rclmtype() keeps working. ffz() could be used to avoid static checks, but it would be runtime overhead for a compile-time constant.

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-001_antidefrag_flags/include/linux/mm.h linux-2.6.14-rc5-mm1-002_usemap/include/linux/mm.h
@@ -529,6 +529,12 @@ static inline void set_page_links(struct
 extern struct page *mem_map;
 #endif
 
+/*
+ * Return what type of page this 2^(MAX_ORDER-1) block of pages is being
+ * used for. Return value is one of the RCLM_X types
+ */
+extern int get_pageblock_type(struct zone *zone, struct page *page);
+
 static inline void *lowmem_page_address(struct page *page)
 {
 	return __va(page_to_pfn(page) << PAGE_SHIFT);

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

This patch adds the core of the anti-fragmentation strategy. It works by grouping related allocation types together. The idea is that large groups of pages that may be reclaimed are placed near each other. The zone->free_area list is broken into three free lists for each RCLM_TYPE.

This section of the patch looks superflous but it is to surpress a compiler warning. Suggestions to make this better looking are welcome.

- struct free_area * area;
+ struct free_area * area = NULL;

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-002_usemap/include/linux/mmzone.h linux-2.6.14-rc5-mm1-003_fragcore/include/linux/mmzone.h
@@ -33,6 +33,10 @@
 #define RCLM_TYPES    3
 #define BITS_PER_RCLM_TYPE 2
 
+#define for_each_rclmtype_order(type, order) \
+	for (order = 0; order < MAX_ORDER; order++) \
+		for (type = 0; type < RCLM_TYPES; type++)
+
 struct free_area {
 	struct list_head	free_list;
 	unsigned long		nr_free;

@@ -155,7 +159,6 @@ struct zone {
 	/* see spanned/present_pages for more description */
 	seqlock_t		span_seqlock;
 #endif
-	struct free_area	free_area[MAX_ORDER];
 
 #ifndef CONFIG_SPARSEMEM
 	/*

@@ -165,6 +168,8 @@ struct zone {
 	unsigned long		*free_area_usemap;
 #endif
 
+	struct free_area	free_area_lists[RCLM_TYPES][MAX_ORDER];
+
 	ZONE_PADDING(_pad1_)
 
 	/* Fields commonly accessed by the page reclaim scanner */

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

This patch implements fallback logic. In the event there is no 2^(MAX_ORDER-1) blocks of pages left, this will help the system decide what list to use. The highlights of the patch are;

o Define a RCLM_FALLBACK type for fallbacks
o Use a percentage of each zone for fallbacks. When a reserved pool of pages is depleted, it will try and use RCLM_FALLBACK before using anything else. This greatly reduces the amount of fallbacks causing fragmentation without needing complex balancing algorithms
o Add a fallback_reserve that records how much of the zone is currently used for allocations falling back to RCLM_FALLBACK
o Adds a fallback_allocs[] array that determines the order of freelists are used for each allocation type

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-003_fragcore/include/linux/mmzone.h linux-2.6.14-rc5-mm1-004_fallback/include/linux/mmzone.h
@@ -30,7 +30,8 @@
 #define RCLM_NORCLM   0
 #define RCLM_EASY     1
 #define RCLM_KERN     2
-#define RCLM_TYPES    3
+#define RCLM_FALLBACK 3
+#define RCLM_TYPES    4
 #define BITS_PER_RCLM_TYPE 2
 
 #define for_each_rclmtype_order(type, order) \

@@ -168,8 +169,17 @@ struct zone {
 	unsigned long		*free_area_usemap;
 #endif
 
+	/*
+	 * With allocation fallbacks, the nr_free count for each RCLM_TYPE must
+	 * be added together to get the correct count of free pages for a given
+	 * order. Individually, the nr_free count in a free_area may not match
+	 * the number of pages in the free_list.
+	 */
 	struct free_area	free_area_lists[RCLM_TYPES][MAX_ORDER];
 
+	/* Number of pages currently used for RCLM_FALLBACK */
+	unsigned long		fallback_reserve;
+
 	ZONE_PADDING(_pad1_)
 
 	/* Fields commonly accessed by the page reclaim scanner */

@@ -292,6 +302,17 @@ struct zonelist {
 	struct zone *zones[MAX_NUMNODES * MAX_NR_ZONES + 1]; // NULL delimited
 };
 
+static inline void inc_reserve_count(struct zone *zone, int type)
+{
+	if (type == RCLM_FALLBACK)
+		zone->fallback_reserve += PAGES_PER_MAXORDER;
+}
+
+static inline void dec_reserve_count(struct zone *zone, int type)
+{
+	if (type == RCLM_FALLBACK && zone->fallback_reserve)
+		zone->fallback_reserve -= PAGES_PER_MAXORDER;
+}
 
 /*
  * The pg_data_t structure is used in machines with CONFIG_DISCONTIGMEM

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Fragmentation avoidance patches increase our chances of satisfying high order allocations. So this patch takes more than one iteration at trying to fulfill those allocations because, unlike before, the extra iterations are often useful.

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-004_fallback/mm/page_alloc.c linux-2.6.14-rc5-mm1-005_largealloc_tryharder/mm/page_alloc.c
@@ -1127,6 +1127,7 @@ __alloc_pages(gfp_t gfp_mask, unsigned i
 	int do_retry;
 	int can_try_harder;
 	int did_some_progress;
+	int highorder_retry = 3;
 
 	might_sleep_if(wait);
 

@@ -1275,7 +1276,17 @@ rebalance:
 				goto got_pg;
 		}
 
-		out_of_memory(gfp_mask, order);
+		if (order < MAX_ORDER / 2)
+			out_of_memory(gfp_mask, order);
+
+		/*
+		 * Due to low fragmentation efforts, we try a little
+		 * harder to satisfy high order allocations and only
+		 * go OOM for low-order allocations
+		 */
+		if (order >= MAX_ORDER/2 && --highorder_retry > 0)
+				goto rebalance;
+
 		goto restart;
 	}
 

@@ -1292,6 +1303,8 @@ rebalance:
 			do_retry = 1;
 		if (gfp_mask & __GFP_NOFAIL)
 			do_retry = 1;
+		if (order >= MAX_ORDER/2 && --highorder_retry > 0)
+			do_retry = 1;
 	}
 	if (do_retry) {
 		blk_congestion_wait(WRITE, HZ/50);

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The freelists for each allocation type can slowly become corrupted due to the per-cpu list. Consider what happens when the following happens

1. A 2^(MAX_ORDER-1) list is reserved for __GFP_EASYRCLM pages
2. An order-0 page is allocated from the newly reserved block
3. The page is freed and placed on the per-cpu list
4. alloc_page() is called with GFP_KERNEL as the gfp_mask
5. The per-cpu list is used to satisfy the allocation

Now, a kernel page is in the middle of a __GFP_EASYRCLM page. This means that over long periods of the time, the anti-fragmentation scheme slowly degrades to the standard allocator.

This patch divides the per-cpu lists into Kernel and User lists. RCLM_NORCLM and RCLM_KERN use the Kernel list and RCLM_EASY uses the user list. Strictly speaking, there should be three lists but as little effort is made to reclaim RCLM_KERN pages, it is not worth the overhead *yet*.

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-005_largealloc_tryharder/include/linux/mmzone.h linux-2.6.14-rc5-mm1-006_percpu/include/linux/mmzone.h
@@ -60,12 +60,21 @@ struct zone_padding {
 #define ZONE_PADDING(name)
 #endif
 
+/*
+ * Indices into pcpu_list
+ * PCPU_KERNEL: For RCLM_NORCLM and RCLM_KERN allocations
+ * PCPU_EASY:   For RCLM_EASY allocations
+ */
+#define PCPU_KERNEL 0
+#define PCPU_EASY   1
+#define PCPU_TYPES  2
+
 struct per_cpu_pages {
-	int count;		/* number of pages in the list */
+	int count[PCPU_TYPES];  /* Number of pages on each list */
 	int low;		/* low watermark, refill needed */
 	int high;		/* high watermark, emptying needed */
 	int batch;		/* chunk size for buddy add/remove */
-	struct list_head list;	/* the list of pages */
+	struct list_head list[PCPU_TYPES]; /* the lists of pages */
 };
 
 struct per_cpu_pageset {

@@ -80,6 +89,10 @@ struct per_cpu_pageset {
 #endif
 } ____cacheline_aligned_in_smp;
 
+/* Helpers for per_cpu_pages */
+#define pset_count(pset) (pset.count[PCPU_KERNEL] + pset.count[PCPU_EASY])
+#define for_each_pcputype(pindex) \
+	for (pindex = 0; pindex < PCPU_TYPES; pindex++)
 #ifdef CONFIG_NUMA
 #define zone_pcp(__z, __cpu) ((__z)->pageset[(__cpu)])
 #else

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

It is not necessary to apply this patch to get all the anti-fragmentation code. This patch adds a new config option called CONFIG_ALLOCSTATS. If set, a number of new bean counters are added that are related to the anti-fragmentation code. The information is exported via /proc/buddyinfo. This is very useful when debugging why high-order pages are not available for allocation.

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-006_percpu/include/linux/mmzone.h linux-2.6.14-rc5-mm1-007_stats/include/linux/mmzone.h
@@ -193,6 +193,17 @@ struct zone {
 	/* Number of pages currently used for RCLM_FALLBACK */
 	unsigned long		fallback_reserve;
 
+#ifdef CONFIG_ALLOCSTATS
+	/*
+	 * These are beancounters that track how the placement policy
+	 * of the buddy allocator is performing
+	 */
+	unsigned long fallback_count[RCLM_TYPES];
+	unsigned long alloc_count[RCLM_TYPES];
+	unsigned long reserve_count[RCLM_TYPES];
+	unsigned long kernnorclm_full_steal;
+	unsigned long kernnorclm_partial_steal;
+#endif
 	ZONE_PADDING(_pad1_)
 
 	/* Fields commonly accessed by the page reclaim scanner */

@@ -292,6 +303,17 @@ struct zone {
 	char			*name;
 } ____cacheline_maxaligned_in_smp;
 
+#ifdef CONFIG_ALLOCSTATS
+#define inc_fallback_count(zone, type) zone->fallback_count[type]++
+#define inc_alloc_count(zone, type) zone->alloc_count[type]++
+#define inc_kernnorclm_partial_steal(zone) zone->kernnorclm_partial_steal++
+#define inc_kernnorclm_full_steal(zone) zone->kernnorclm_full_steal++
+#else
+#define inc_fallback_count(zone, type) do {} while (0)
+#define inc_alloc_count(zone, type) do {} while (0)
+#define inc_kernnorclm_partial_steal(zone) do {} while (0)
+#define inc_kernnorclm_full_steal(zone) do {} while (0)
+#endif
 
 /*
  * The "priority" of VM scanning is how much of the queues we will scan in one

@@ -319,12 +341,19 @@ static inline void inc_reserve_count(str
 {
 	if (type == RCLM_FALLBACK)
 		zone->fallback_reserve += PAGES_PER_MAXORDER;
+#ifdef CONFIG_ALLOCSTATS
+	zone->reserve_count[type]++;
+#endif
 }
 
 static inline void dec_reserve_count(struct zone *zone, int type)
 {
 	if (type == RCLM_FALLBACK && zone->fallback_reserve)
 		zone->fallback_reserve -= PAGES_PER_MAXORDER;
+#ifdef CONFIG_ALLOCSTATS
+	if (zone->reserve_count[type] > 0)
+		zone->reserve_count[type]--;
+#endif
 }
 
 /*

diff -rup -X /usr/src/patchset-0.5/bin//dontdiff linux-2.6.14-rc5-mm1-006_percpu/lib/Kconfig.debug linux-2.6.14-rc5-mm1-007_stats/lib/Kconfig.debug
@@ -77,6 +77,17 @@ config SCHEDSTATS
 	  application, you can say N to avoid the very slight overhead
 	  this adds.
 
+config ALLOCSTATS
+	bool "Collection buddy allocator statistics"
+	depends on DEBUG_KERNEL && PROC_FS
+	help
+	  If you say Y here, additional code will be inserted into the
+	  page allocator routines to collect statistics on the allocator
+	  behavior and provide them in /proc/buddyinfo. These stats are
+	  useful for measuring fragmentation in the buddy allocator. If
+	  you are not debugging or measuring the allocator, you can say N
+	  to avoid the slight overhead this adds.
+
 config DEBUG_SLAB
 	bool "Debug memory allocations"
 	depends on DEBUG_KERNEL

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I can say that this patch set makes hotplug memory remove be of value on ppc64. My system has 6GB of memory and I would 'load it up' to the point where it would just start to swap and let it run for an hour. Without these patches, it was almost impossible to find a section that could be offlined. With the patches, I can consistently reduce memory to somewhere between 512MB and 1GB. Of course, results will vary based on workload. Also, this is most advantageous for memory hotlug on ppc64 due to relatively small section size (16MB) as compared to the page grouping size (8MB). A more general purpose solution is needed for memory hotplug support on architectures with larger section sizes.

Just another data point,

Mike

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Despite what people were trying to tell me at Ottawa, this patch set really does add quite a lot of complexity to the page allocator, and it seems to be increasingly only of benefit to dynamically allocating hugepages and memory hot unplug.

If that is the case, do we really want to make such sacrifices for the huge machines that want these things? What about just making an extra zone for easy-to-reclaim things to live in?

This could possibly even be resized at runtime according to demand with the memory hotplug stuff (though I haven't been following that).

Don't take this as criticism of the actual implementation or its effectiveness.

Nick

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Remember that Rohit is seeing ~10% variation between runs of scientific software, and that his patch to use higher-order pages to preload the percpu-pages magazines fixed that up. I assume this means that it provided up to 10% speedup, which is a lot.

But the patch caused page allocator fragmentation and several reports of gigE Tx buffer allocation failures, so I dropped it.

We think that Mel's patches will allow us to reintroduce Rohit's optimisation.

But yes, adding additional complexity is a black mark, and these patches add quite a bit. (Ditto the fine-looking adaptive readahead patches, btw).

OK, I wasn't aware of this. I wonder what other approaches we could try to add a bit of colour to our pages? I bet something simple like trying to hand out alternate odd/even pages per task might help.

They do look quite fine. They seem to get their claws pretty deep into page reclaim, but I guess that is to be expected if we want to increase readahead smarts much more.

However, I'm hoping bits of that can be merged at a time, and interfaces and page reclaim stuff can be discussed and the best option taken. No such luck with these patches AFAIKS - simply adding another level of page groups, and another level of heuristics to the page allocator is going to hurt. By definition. I do wonder why zones can't be used... though I'm sure there are good reasons.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Reading through the kernel archives, it appears that any page colouring scheme was getting rejected because it slowed up workloads like kernel compilers that were not very cache sensitive. Where an approach didn't suffer from that problem, there was disagreement over whether there was a general performance improvement or not.

I recall Rohit's patch from an earlier -mm. Without knowing anything about his test, I am guessing he is getting cheap page colouring by preloading the per-cpu cache with contiguous pages and his workload is faulting in the batch of pages immediately by doing something like linearly reading a large array. Hence, the mappings of his workload are getting the right colour pages. This makes his workload a "lucky" workload. The general benefit of preloading the percpu magazines is that there is a chance the allocator only has to be called once, not pcp->batch times.

An odd/even allocation scheme could be provided by having two free_lists in a free_area. One list for the "left buddy" and the other list for the "right buddy". However, at best, that would provide two colours. I'm not sure how much benefit it would give for the cost of more linked lists.

Granted, the patch set does add complexity even though I tried to keep it as simple as possible. Benchmarks were posted with each patchset to show that it was not suffering in real performance even if the code is a bit less approachable.

Doing something similar with zones is an old idea and brought up specifically for memory hotplug. In implementations, the zone was called ZONE_HOTREMOVABLE or something similar. In my opinion, replicating the effect of this set of patches with zones introduces it's own set of headaches and ends up being far more complicated. Hopefully, someone will point out if I am missing historical context here, am rehashing old arguments or am just plain wrong :)

To replicate the functionality of these patches with zones would require two additional zones for NormalEasy and HighmemEasy (I suck at naming things). The plus side is that once the zone fallback lists are updated, the page allocator remains more or less the same as it is today. Then the headaches start.

Problem 1: Zone fallback lists are "one-way" and per-node. Lets assume a fallback list of HighMemEasy, HighMem, NormalEasy, Normal, DMA. Assuming we are allocating PTEs from high memory, we could fallback to the Normal zone even if highmem pages are available because the HighMem zone was out of pages. It will require very different fallback logic to say that HighMem allocations can also use HighMemEasy rather than falling back to Normal.

Problem 2: Setting the zone size will be a very difficult tunable to get right. Right off, we are are introducing a tunable which will make foreheads furrow. If the tunable is set wrong, system performance will suffer and we could see situations where kernel allocations fail because it's zone got depleted.

Problem 3: To get rid of the tunable, we could try resizing the zones dynamically but that will be hard. Obviously, the zones are going to be physically adjacent to each other. To resize the zone, the pages at one end of the zone will need to be free. Shrinking the NormalEasy zone would be easy enough, but shrinking the Normal zone with kernel pages in it would be considerably harder, if not outright impossible. One page in the wrong place will mean the zone cannot be resized

Problem 4: Page reclaim would have two new zones to deal with bringing with it a new set of zone balancing problems. That brings it's own special brand of fun.

There may be more problems but these 4 are fairly important. This patchset does not suffer from the same problems.

Problem 1: This patchset has a fallback list for each allocation type. So EasyRclm allocations can just as easily use an area reserved for kernel allocations and vice versa. Obviously we don't like when this happens, but when it does, things start fragmenting rather than breaking.

Problem 2: The number of pages that get reserved for each type grows and shrinks on demand. There is no tunable and no need for one.

Problem 3: Problem doesn't exist for this patchset

Problem 4: Problem doesn't exist for this patchset.

Bottom line, using zones will be more complex than this set of patches and bring a lot of tricky issues with it.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Or we could introduce a new allocation mechanism for anon pages that passes the vaddr to the allocator, and tries to get an odd/even page according to the vaddr.

2 colours should be a good first order improvement because you will no longer have adjacent pages of the same colour.

It would definitely be cheaper than fragmentation avoidance + higher order batch loading.

Just be a different set of GFP flags. Your patches obviously also have some ordering imposed.... pagecache would want HighMemEasy, HighMem, NormalEasy, Normal, DMA; ptes will want HighMem, Normal, DMA.

Note that if you do need to make some changes to the zone allocator, then IMO that is far preferable to add a new layer of things-that-are-blocks-of- -memory-but-not-zones, complete with their own balancing and other heuristics.

But even so, when you do automatic resizing, you seem to be adding a fundamental weak point in fragmentation avoidance.

OK, maybe it is hard ;) Do they really need to be resized, then?

Isn't the big memory hotunplug push aimed at virtual machines and hypervisors anyway? In which case one would presumably have some memory that "must" be reclaimable, in which case we can't expand non-Easy zones into that memory anyway.

If page reclaim can't deal with 5 zones then it is going to have problems somewhere at 3 and needs to be fixed. I don't see how your patches get around this fun by simply introducing their own balancing and fallback heuristics.

Maybe zones don't do exactly what you need, but I think they're better than you think ;)

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

We could, but it is a different problem than what this set of patches are trying to address. I'll add page colouring to the end of the todo list in case I get stuck for something to do.

Ok, but the page colours would also need to be in the per-cpu lists this new api that supplies vaddrs always takes the spinlock for the free lists. I don't believe it would be cheaper and any benefit would only show up on benchmarks that are cache sensitive. Judging by previous discussions on page colouring in the mail archives, Linus will happily kick the approach full of holes.

As for current performance, the Aim9 benchmarks show that the fragmentation avoidance does not have a major performance penalty. A run of the patches in the -mm tree should find out if there are performance regressions on other machine types.

As well as a different set of GFP flags, we would also need new zone fallback logic which will hit the __alloc_pages() path. It will be adding more complexity to the allocator and we're replacing one type of complexity with another.

Thing is, with my approach, the very worst that happens is that it fragments just as bad as the normal allocator. With a zone-based approach, the worst that happens is that the kernel zone is too small, kernel caches do not grow to a suitable size and overall system performance degrades.

The sizing I do is when a large block is split. Then the region is just marked for a particular allocation type. This is very simple. The second resizing that occurs is when a kernel allocation "steal" easyrclm pages. I do not like the fact that we steal in this fashion but the alternative is to teach kswapd how to reclaim easyrclm pages from other areas. I view this as "future work" but if it was done, the "steal" mechanism would go away.

I think we would need to, yes. If the size of the region is wrong, bad things are likely to happen. If the kernel page zone is too small, it'll be under pressure even though there is memory available elsewhere. If it's too large, then it will get fragmented and high order allocations will fail.

I believe that is the case for hotplug all right, but not the case where we just want to satisfy high order allocations in a reasonably reliable fashion. In that case, it would be nice to reclaim an easyrclm region.

It has already been reported by Mike Kravetz that memory remove works a whole lot better on PPC64 with this patch than without it. Memory hotplug remove was not the problem I was trying to solve, but I consider the fact that it is helped to be a big plus. So, even though it is possible that this approach still gets fragmented under some workloads, we know that, in general, it does a pretty good job.

If my approach gets the sizes of areas all wrong, it will fragment. If the zone-based approach gets the sizes of areas wrong, system performance degrades. I prefer the failure scenario of my approach :).

You may be right, but I still think that my approach is simpler and less likely to introduce horrible balancing problems.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

OK, but I'm just pointing out that improving page colouring doesn't require contiguous pages.

But I can see that there will be penalties. Cache misses, branches, etc. Obviously any new feature or more sophisticated behaviour is going to require that but they obviously need good justification.

It is complexity that is mostly already handled for us with the zones logic. Picking out a couple of small points that zones don't get exactly right isn't a good basis to come up with a completely new zoneing layer.

If you don't need to guarantee higher order allocations, then there is no problem with our current approach. If you do then you simply need to make a sacrifice.

Weak point, as in: gets fragmented.

But people will just have to get it right then. If they want to be able to hot unplug 10G of memory, or allocate 4G of hugepages on demand, then they simply need to specify their requirements. Not too difficult? It is really nice to be able to place some burden on huge servers and mainframes, because they have people administering and tuning them full-time. It allows us to not penalise small servers and desktops.

As I've said before, I think this is a false hope and we need to move away from higher order allocations.

Sure, but using zones would work too, and on the plus side you would be able to specify exactly how much removable memory to be.

Simpler? We already have zones though. They are a complexity we need to deal with already. I really can't see how you can use the simpler argument in favour of your patches ;)

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

I, for one, would like to see some harder numbers on that, together with which architectures they actually affect.

Yes, it made that condition worse but ...

... frankly, it happens without Rohit's patch as well (under more stress). If we want a OS that is robust, and supports higher order allocations, we need to start caring about fragmentations. Not just for large pages, and hotplug, but also for more common things like jumbo GigE frames, CIFS, various device drivers, kernel stacks > 4K etc.

To me, the question is "do we support higher order allocations, or not?". Pretending we do, making a half-assed job of it, and then it not working well under pressure is not helping anyone. I'm told, for instance, that AMD64 requires > 4K stacks - that's pretty fundamental, as just one instance. I'd rather make Linux pretty bulletproof - the added feature stuff is just a bonus that comes for free with that.

We don't make a good job of doing long-term stress testing, which is where fragmentation occurs. Unfortunately, customers do ;-(. I've become fairly convinced we need something like this.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Well... stacks are allocated with GFP_KERNEL, so we're reliable there.

It's the GFP_ATOMIC higher-order allocations which fail, and networking copes with that.

I suspect this would all be a non-issue if the net drivers were using __GFP_NOWARN ;)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

We still need to allocate them, even if it's GFP_KERNEL. As memory gets larger and larger, and we have no targetted reclaim, we'll have to blow away more and more stuff at random before we happen to get contiguous free areas. Just statistics aren't in your favour ... Getting 4 contig pages on a 1GB desktop is much harder than on a 128MB machine.

Is not going to get better as time goes on ;-) Yeah, yeah, I know, you want recreates, numbers, etc. Not the easiest thing to reproduce in a short-term consistent manner though.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

However, these allocations are not of the "easy to reclaim" type, in which case they just use the regular fragmented-to-shit areas. If no contiguous pages are available from there, then an easy-reclaim area needs to be stolen, right?

In which case I don't see why these patches don't have similar long term failure cases if there is strong demand for higher order allocations. Prolong things a bit, perhaps, but...

Regardless, I think we need to continue our steady move away from higher order allocation requirements.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Right.

It hinges all on how long the high order kernel allocation is. If it's short-lived, it will get freed back to the easyrclm free lists and we don't fragment. If it turns out to be long lived, then we are in trouble. If this turns out to be the case, a possibility would be to use the __GFP_KERNRCLM flag for high order, short lived allocations. This would tend to group large free areas in the same place. It would only be worth investigating if we found that memory still got fragmented over very long periods of time.

No arguement with you there. My actual aim is to guarantee HugeTLB allocations for userspace which we currently have to reserve at boot time. Stuff like memory hotplug remove and high order kernel allocations are benefits that would be nice to pick up on the way.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

But it doesn't seem to be a great problem right now, apart from hotplug and hugepages. Some jumbo GigE drivers use higher order allocations, but I think there are moves to get away from that (e1000, for example).

And i386 had required 8K stacks for a long long time too.

But this doesn't exactly make Linux bulletproof, AFAIKS it doesn't work well on small memory systems, and it can still get fragmented and not work. IMO in order to make Linux bulletproof, just have fallbacks for anything greater than about order 2 allocations.

From what I have seen, by far our biggest problems in the mm are due to page reclaim, and these patches will make our reclaim behaviour more complex I think.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

GigE drivers and any other subsystem will not use higher order allocations if they know the underlying allocator is not going to satisfy the request. These patches are the starting point for properly supporting large allocations. I will admit that this set of patches is not going to solve the whole problem, but it is a start that can be built upon.

Small memory systems are unlikely to care about satisfying large allocations. These patches should not be adversely affecting small memory systems but it is likely that a smaller value of MAX_ORDER would have to be used to help with fragmentation.

You are right that we can still get fragmented. To prevent all fragmentation would require more work but these patches would still be the starting point. It makes sense to start with this patchset now and move on the the more complex stuff later. If these patches are in, we could later do stuff like;

o Configurable option that controls how strict fallback is. In a situation where we absolutely do not want to fragment, do not allow kernel allocations to fallback to EasyRclm zones. Instead, teach kswapd to reclaim pages from the Fallback and KernNoRclm areas.

o Configurable option that gets kswapd to keep the KernNoRclm, KernRclm and Fallback areas free of EasyRclm pages. This would prevent awkward kernel pages ending up in the wrong areas at the cost of more work for kswapd

o Linear scan memory to remove contiguous groups of large pages to satisfy larger allocations. The usemap gives hints to what regions are worth trying to reclaim. I have a set of patches that do something like this and it was able to satisfy large allocations reliably, but they are slow right now and need a lot of work.

All these ideas need a mechanism like this set of patches to group related pages together. This set of patches still help fragmentation now, although not in a 100% reliable fashion. My desktop which is running a kernel patched with these patches has been running for 33 hours and managed to allocate 80 order-10 blocks from ZONE_NORMAL which is about 42% of the zone while xmms, X, konqueror and a pile of terminals were running. That is pretty decent, even if it's not perfect.

With this approach, an easyrclm region can be reclaimed to help satisfy a large allocation. This would be harder to do with a zone-based approach. Obviously, stealing easyrclm pages to satisfy a high order allocation could end up fragmenting the system given enough time. This worst-case scenario would occur if high order allocations were in heavy demand, they were kernel allocations *and* they were long lived.

If we find in the future that this worst-case scenario occurs frequently, the easiest solution would be to use __GFP_KERNRCLM for high order short lived allocations rather than it's current usage for caches like icaches. This would set up areas that tend to have high order free blocks in them.

What sort of fallbacks? Private pools of pages of the larger order for subsystems that need large pages is hardly desirable.

This patchset does not touch reclaim at all. The lists that this patch really affects is the zone freelists, not the LRU lists that page reclaim are dealing with. It is only later when we want to try and guarantee large-order allocations that we will have to change page reclaim.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I really don't think we *want* to say we support higher order allocations absolutely robustly, nor do we want people using them if possible. Because we don't. Even with your patches.

Ingo also brought up this point at Ottawa.

But complexity. More bugs, code harder to understand and maintain, more cache and memory footprint, more branches and instructions.

In which case someone like GigE is not going to be able to access unfragmented memory anyway. This is my point. The patch still has the same long term failure cases that we appear to only be able to sanely solve by avoiding higher order allocations.

The easy-to-reclaim stuff doesn't need higher order allocations anyway, so there is no point in being happy about large contiguous regions for these guys.

The only thing that seems to need it is memory hot unplug, which should rather use another zone.

But nobody does that. Why should we care? And in the case you *really* need to do that, your system likely to fail at some point anyway.

OK, for hot unplug you may want that, or for hugepages. However, in those cases it should be done with zones AFAIKS.

Mechanisms to continue to run without contiguous memory would be best. Small private pools aren't particularly undesirable - we do that everywhere anyway. Your fragmentation patches essentially do that.

But it affects things in the allocation path which in turn affects the reclaim path. You're doing various balancing and fallbacks and it is simply complicated behaviour in terms of trying to analyse a working system.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I accept that. We should not be encouraging subsystems to use high order allocations but keeping the system in a fragmented state to force the issue is hardly the correct thing to do either.

The patches have gone through a large number of revisions, have been heavily tested and reviewed by a few people. The memory footprint of this approach is smaller than introducing new zones. If the cache footprint, increased branches and instructions were a problem, I would expect them to show up in the aim9 benchmark or the benchmark that ran ghostscript multiple times on a large file.

The will need high order allocations if we want to provide HugeTLB pages to userspace on-demand rather than reserving at boot-time. This is a future problem, but it's one that is not worth tackling until the fragmentation problem is fixed first.

Work from 2004 in memory hotplug was trying to use additional zones. I am hoping that someone more involved with memory hotplug will tell us what problems they ran into. If they ran into no problems, they might explain why it was never included in the mainline.

And then we are back to what size to make the zones. This set of patches will largely manage themselves without requiring a sysadmin to intervene.

The main difference been that when a subsystem has small private pools, it is possible for anyone else to use them and shrinking mechanisms are required. My fragmentation patches has subpools, but they are always available.

Maybe it's because it's late, but I don't see how these patches currently hit the reclaim path. The reclaim path deals with LRU lists, this set of patches deals with the freelists.

Someone performing such an analysis of the system will only hit problems with these patches if they are performing a deep analysis of the page allocator. Other analysis such as the page reclaim should not even notice that the page allocator has changed.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

OK I'm starting to repeat myself a bit so after this I'll be quiet for a bit and let others speak :)

But you don't seem to actually "fix" anything. It is slightly improved, but for cases where higher order GFP_ATOMIC and GFP_KERNEL allocations fail (ie. anything other than memory hotplug or hugepages) you still seem to have all the same failure cases.

Transient higher order allocations mean we don't fragment much, you say? Well that is true, but it is true for how the system currently works. My desktop has been up for a day or two, and it has 4444K free, and it has 295 order-3 pages available - it can run a GigE and all its trasient allocations no problem.

In the cases were we *do* actually get those failures from eg. networking, I'd say your patch probably will end up having problems too. The way to fix it is to not use higher order allocations.

I appreciate that a lot of work has gone into them. You must appreciate that they add a reasonable amount of complexity and a non-zero perormance cost to the page allocator.

However I think something must be broken if the footprint of adding a new zone is higher?

Sure. In what form, we haven't agreed. I vote zones! :)

That would be good.

Either you need to guarantee some hugepage allocation / hot unplug capability or you don't. Placing a bit of burden on admins of these huge servers or mainframes sounds like a fine idea to me.

Seriously nobody else will want this, no embedded, no desktops, no small servers.

True, but we're talking about the need to guarantee an allocation. In that case, mempools are required anyway and neither the current nor your modified page allocator will help.

In the case were there is no need for a guarantee, there is presumably some other fallback.

You don't "hit" the reclaim path, but by making the allocation path more complex makes reclaim behaviour harder to analyse.

Let me think what a nasty one we had was? Oh yeah, the reclaim priority would "wind up" because concurrent allocations were keeping free pages below watermarks.

I don't know, that's just an example but there are others. The two are fundamentally tied together.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The set of patches do fix a lot and make a strong start at addressing the fragmentation problem, just not 100% of the way. The stress tests I've been running with kernel compiles show that relatively few kernel pages fallback to undesirable areas. The failure cases I hit are dependant on workload rather than almost guaranteed to happen as we have with the current approach.

For example, this is the fallback statistics for the Normal zone after a kernel compile stress-test (5 simultaneous -j2 kernel compiles);

KernNoRclm Allocs: 35461 Reserve: 24 Fallbacks: 2
EasyRclm Allocs: 971798 Reserve: 152 Fallbacks: 1223
KernRclm Allocs: 34816 Reserve: 16 Fallbacks: 0
Fallback Allocs: 0 Reserve: 28 Fallbacks: 0

2 really awkward kernel pages out of 35,461 allocations ended up in the wrong place. Reducing the fallbacks to 0 for all workloads would require page reclaim that knew what the areas in the usemap meant. If a mechanism like linear page reclaiming was built upon these patches, we would find that at least 152 2^MAX_ORDER-1 pages could be allocated on demand if we wanted to. We don't do anything like this today because it simply isn't possible.

GFP_ATOMIC allocations still suffer. If the order size they need is not available, they can't fix up the situation. Fixing that up would require something like active defragmentation, kswapd to work on keeping high order free pages or the reliable and reasonable "don't do high order GFP_ATOMIC allocations".

So, with this set of patches, how fragmented you get is dependant on the workload and it may still break down and high order allocations will fail. But the current situation is that it will defiantly break down. The fact is that it has been reported that memory hotplug remove works with these patches and doesn't without them. Granted, this is just one feature on a high-end machine, but it is one solid operation we can perform with the patches and cannot without them. The second possibility is that this patch may allow the preloading of per-cpu magazines which will improve some workloads and make no different to others. Preloading in one allocation is less work than loading with pcp->batch allocations.

I do appreciate that there is a reasonable amount of complexity. Hence the patches are fairly well commented and the introduction mail and changelog is detailed to help explain the mechanism. If that is not good enough, people googling may find the lwn.net article
(http://lwn.net/Articles/120960/) that explains the guts of the mechanism complete with comment at the end on how hard it is to get high-order allocation patches merged :). The complexity of this scheme was the main reason why an early version was released long before it was ready so people would have a chance to look through it.

The performance cost is something that has to be determined by benchmarks. With each version of this patch, I released aim9 benchmarks of the clean kernel and with my benchmarks. If there were performance regressions on my test machine, it didn't get released until I had figured out what I was doing wrong. Here is the difference between 2.6.14-rc5-mm1 and 2.6.14-rc5-mm1-mbuddy-v19

1 creat-clo 16006.00 15889.41 -116.59 -0.73% File Creations and Closes/second

 2 page_test     117515.83  117082.15    -433.68 -0.37% System Allocations & Pages/second
 3 brk_test      440289.81  437887.37   -2402.44 -0.55% System Memory Allocations/second
 4 jmp_test     4179466.67 4179950.00     483.33  0.01% Non-local gotos/second
 5 signal_test    80803.20   85335.78    4532.58  5.61% Signal Traps/second
 6 exec_test         61.75      61.92       0.17  0.28% Program Loads/second
 7 fork_test       1327.01    1342.21      15.20  1.15% Task Creations/second
 8 link_test       5531.53    5555.55      24.02  0.43% Link/Unlink Pairs/second

I'll admit right now there is a 0.37% drop in raw page allocation performance on this test run but these figures always vary by a few percent. I could run this aim9 test a few more times until I got a figure that showed the set of patches giving a performance gain. fork_test and signal_test show a nice performance improvement.

A trip through the -mm tree would discover if the performance figures are real, or are they just on my test machine.

Here are the sizeof() of struct zone in three kernels

2.6.14-rc5-mm1: 768
2.6.14-rc5-mm1-mbuddy-nostats: 1408
2.6.14-rc5-mm1-mbuddy-withallocstats: 1536

The main increases in the size is one additional list for per-cpu for every CPU in the system and the addition of the new free lists. The usemap is 2 bits per 2^(MAX_ORDER-1) pages in the system. On my system with 1.5GiB of RAM, that's 94 bytes. So the memory overhead is about 734 bytes in all.

If a very small memory system was worried about this, they could get rid of this whole scheme by defining __GFP_KERNRCLM and __GFP_EASYRCLM to 0 and change RCLM_TYPES from 4 to 1. Actually... Now that I think it, this whole anti fragmentation scheme could be made configurable by doing something like;

#ifdef CONFIG_ANTIDEFRAG

#define RCLM_NORCLM   0
#define RCLM_EASY     1
#define RCLM_KERN     2

#define RCLM_FALLBACK 3
#define RCLM_TYPES 4
#define __GFP_EASYRCLM 0x80000u /* User and other easily reclaimed pages */
#define __GFP_KERNRCLM 0x100000u /* Kernel page that is reclaimable */
#else

#define RCLM_NORCLM   0
#define RCLM_EASY     0
#define RCLM_KERN     0

#define RCLM_FALLBACK 0
#define RCLM_TYPES 1
#define __GFP_EASYRCLM 0u
#define __GFP_KERNRCLM 0u
#endif

This would need more work obviously, but essentially, the above would make anti-defragmentation a configurable option for small memory systems. However, I would be wary of changing the behavior of the allocator as a configurable option for anything other than debugging. Such an option should only be provided if we really want those 734 bytes back.

We can't measure the difference in code complexity as we don't have a zone-based approach to compare against. Ideally if it did exist, any loop that depends on MAX_NR_ZONES would be increased by 1, maybe 2 depending on how many of these easyrclm zones that would be created. This would impact both the allocator and kswapd. It would at least add 768 or 1536 for two zones in comparison to the 734 bytes my approach adds.

We'll agree to disagree for the moment ;) . I would expect others to choke on the idea of more zones been introduced. Some architectures like power and sparc64 (I think) only use one zone ZONE_DMA. Hopefully some of the architecture maintainers will express some opinion on the addition of new zones.

I'd rather avoid hitting people with tunables if at all possible. I'd rather my face didn't end up on the dart board of some NOC because their high-end server failed at 4 in the morning because they misconfigured the size of the kernel zone.

Not yet anyway. My long-term plan is to have HugeTLB pages supplied on demand for applications that wanted them. This would require fragmentation to be addressed first. Desktop applications like openoffice or anything using a sparse address space like Java applications should benefit if they could use HugeTLB pages. Small database servers should see a benefit as well. Of course, this would not happen today, because right now, we cannot give HugeTLB pages on demand to anyone, userspace or kernel space and there is no point even trying.

Solaris is able to supply large pages for applications on demand but it eventually falls back to using small pages because they get fragmented. I think Windows has an API for large pages as well, but it also hits fragmentation problems.

The modified allocator will help when refilling the mempools as long as the caller is not GFP_ATOMIC. If using GFP_KERNEL, kswapd will page out enough pages to get the contiguous blocks. Teaching kswapd to be smarter about freeing contiguous pages is future work.

I still don't see why. With the normal allocator, free pages are on a list that get allocated. With the modified allocator, free pages are on lists that get allocated.

That sounds like kswapd could not free pages fast enough for the storm of allocators coming in. In that case, they would all enter direct reclaim leading to a storm of kswapd-like processes.

I still cannot see any impact these patches would have on reclaim but maybe that is a lack of imagination. I'll accept that, potentially, these patches affect reclaim in some-currently-undefined-fashion. If that is the case, I would assert that any zone-based approach would also have an impact because kswapd has a new zone to manage the watermarks for.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

do you have an expectation to be able to solve the 'fragmentation problem', all the time, in a 100% way, now or in the future?

can you always, under any circumstance hot unplug RAM with these patches applied? If not, do you have any expectation to reach 100%?

Ingo

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

In a word, yes.

The current allocator has no design for measuring or reducing fragmentation. These patches provide the framework for at least measuring fragmentation.

The patches can not do anything magical and there will be a point where the system has to make a choice: fragment, or fail an allocation when there _is_ free memory.

These patches take us in a direction where we are capable of making such a decision.

With these patches, no. There are currently some very nice, pathological workloads which will still cause fragmentation. But, in the interest of incremental feature introduction, I think they're a fine first step. We can effectively reach toward a more comprehensive solution on top of these patches.

Reaching truly 100% will require some other changes such as being able to virtually remap things like kernel text.

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

then we need to see that 100% solution first - at least in terms of conceptual steps. Not being able to hot-unplug RAM in a 100% way wont satisfy customers. Whatever solution we choose, it must work 100%. Just to give a comparison: would you be content with your computer failing to start up apps 1 time out of 100, saying that 99% is good enough? Or would you call it what it is: buggy and unreliable?

to stress it: hot unplug is a _feature_ that must work 100%, _not_ some optimization where 99% is good enough. This is a feature that people will be depending on if we promise it, and 1% failure rate is not acceptable. Your 'pathological workload' might be customer X's daily workload. Unless there is a clear definition of what is possible and what is not (which definition can be relied upon by users), having a 99% solution is much worse than the current 0% solution!

worse than that, this is a known _hard_ problem to solve in a 100% way, and saying 'this patch is a good first step' just lures us (and customers) into believing that we are only 1% away from the desired 100% solution, while nothing could be further from the truth. They will demand the remaining 1%, but can we offer it? Unless you can provide a clear, accepted-upon path towards the 100% solution, we have nothing right now.

I have no problems with using higher-order pages for performance purposes [*], as long as 'failed' allocation (and freeing) actions are user-invisible. But the moment you make it user-visible, it _must_ work in a deterministic way!

Ingo

[*] in which case any slowdown in the page allocator must be offset by
the gains.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I don't think saying "truly 100%" really even makes sense. There will always be restrictions of some kind. For instance, with a 10MB kernel image, should you be able to shrink the memory in the system below 10MB? ;)

There is also no precedent in existing UNIXes for a 100% solution. From
http://publib.boulder.ibm.com/infocenter/pseries/index.jsp?topic=/com.ibm.aix.doc/aixbman/prftungd/dlpar.htm , a seemingly arbitrary restriction:

A memory region that contains a large page cannot be removed.

What the fragmentation patches _can_ give us is the ability to have 100% success in removing certain areas: the "user-reclaimable" areas referenced in the patch. This gives a customer at least the ability to plan for how dynamically reconfigurable a system should be.

After these patches, the next logical steps are to increase the knowledge that the slabs have about fragmentation, and to teach some of the shrinkers about fragmentation.

After that, we'll need some kind of virtual remapping, breaking the 1:1 kernel virtual mapping, so that the most problematic pages can be remapped. These pages would retain their virtual address, but getting a new physical. However, this is quite far down the road and will require some serious evaluation because it impacts how normal devices are able to to DMA. The ppc64 proprietary hypervisor has features to work around these issues, and any new hypervisors wishing to support partition memory hotplug would likely have to follow suit.

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

think of it in terms of filesystem shrinking: yes, obviously you cannot shrink to below the allocated size, but no user expects to be able to do it. But users would not accept filesystem shrinking failing for certain file layouts. In that case we are better off with no ability to shrink:
it makes it clear that we have not solved the problem, yet.

so it's all about expectations: _could_ you reasonably remove a piece of RAM? Customer will say: "I have stopped all nonessential services, and free RAM is at 90%, still I cannot remove that piece of faulty RAM, fix the kernel!". No reasonable customer will say: "True, I have all RAM used up in mlock()ed sections, but i want to remove some RAM nevertheless".

does this have any relevance to the point, other than to prove that it's a hard problem that we should not pretend to be able to solve, without seeing a clear path towards a solution?

Ingo

That's an excellent example. Until we have some kind of kernel remapping, breaking the 1:1 kernel virtual mapping, these pages will always exist. The easiest example of this kind of memory is kernel text.

Another example might be a somewhat errant device driver which has allocates some large buffers and is doing DMA to or from them. In this case, we need to have APIs to require devices to give up and reacquire any dynamically allocated structures. If the device driver does not implement these APIs it is not compatible with memory hotplug.

Agreed. It is a hard problem. One that some other UNIXes have not fully solved.

Here are the steps that I think we need to take. Do you see any holes in their coverage? Anything that seems infeasible?

1. Fragmentation avoidance
* by itself, increases likelyhood of having an area of memory which might be easily removed
* very small (if any) performance overhead
* other potential in-kernel users
* creates infrastructure to enforce the "hotplugablity" of any particular are of memory.
2. Driver APIs
* Require that drivers specifically request for areas which must retain constant physical addresses
* Driver must relinquish control of such areas upon request
* Can be worked around by hypervisors
3. Break 1:1 Kernel Virtual/Physial Mapping
* In any large area of physical memory we wish to remove, there will likely be very, very few straggler pages, which can not easily be freed.
* Kernel will transparently move the contents of these physical pages to new pages, keeping constant virtual addresses.
* Negative TLB overhead, as in-kernel large page mappings are broken down into smaller pages.
* __{p,v}a() become more expensive, likely a table lookup

I've already done (3) on a limited basis, in the early days of memory hotplug. Not the remapping, just breaking the 1:1 assumptions. It wasn't too horribly painful.

We'll also need to make some decisions along the way about what to do about thinks like large pages. Is it better to just punt like AIX and refuse to remove their areas? Break them down into small pages and degrade performance?

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

another example is open files, dentries, inodes, kernel stacks and various other kernel objects, which can become embedded in a generic kernel memory zone anywhere, and can become referenced to from other objects.

The C language we use for the kernel has no notion to automatically track these links between objects, which makes general purpose memory unmapping very hard: each and every pointer would have to be tracked explicitly.

Such an 'explicit pointer tracking' approach is not only error-prone [the C language offers us no way to _avoid_ direct dereferencing], it's also clearly a maintainance nightmare. Code like:

	obj->ptr = obj2;

would have to become something like:

	obj_set(obj_deref(obj, ptr), obj2);

this is only a theoretical thing, it is very clear that such an approach is unreadable, unmaintainable and unworkable.

fixing 1:1 mapping assumptions is a cakewalk in comparison ...

the only sane solution to make generic kernel RAM hot-removable, from a conceptual angle, is to use a language for the kernel that supports pointer-rewriting, garbage-collection and hence VM-shrinking. I.e. to rewrite the kernel in Java, C# or whatever other type-safe language that can track pointers. [But possibly not even current Java implementations can do this right now, because they currently use faulting methods for GC and do not track every pointer, which method is not suitable for hot-remove.]

[ C++ might work too, but that needs extensive other changes and a
kernel-pointer type that all other pointer types have to inherited from. No quick & easy void * pointers allowed. Such a restriction is possibly unenforcable and thus the solution is unmaintainable. ]

just to state the obvious: while using another programming language for the Linux kernel might make sense in the future, the likelhood for that to happen anytime soon seems quite low =B-)

so i strongly believe that it's plain impossible to do memory hot-unplug of generic kernel RAM in a reliable and guaranteed way.

there are other 'hot-' features though that might be doable though:
memory hot-add and memory hot-replace:

- hot-add is relatively easy (still nontrivial) and with discontigmem we have it supported in essence.

- hot-replace becomes possible with the breaking of 1:1 kernel mapping, because the totality of kernel RAM does not shrink, so it has no impact on the virtual side of kernel memory, it's "just" a replacement act on the physical side. It's still not trivial though: if the new memory area has a different physical offset (which is likely under most hw designs), all physical pointers needs tracking and fixups. I.e. DMA has to be tracked (iommu-alike approach) or silenced, and pagetables may need fixups. Also, if the swapped module involves the kernel image itself then "interesting" per-arch things have to be done. But in any case, this is a much more limited change than what hot-remove of generic kernel RAM necessiates. Hot-replace is what fault tolerant systems would need.

reliable hot-remove of generic kernel RAM is plain impossible even in a fully virtualized solution. It's impossible even with maximum hardware help. We simply dont have the means to fix up live kernel pointers still linked into the removed region, under the C programming model.

the hurdles towards a reliable solution are so incredibly high, that other solutions _have_ to be considered: restrict the type of RAM that can be removed, and put it into a separate zone. That solves things
easily: no kernel pointers will be allowed in those zones. It becomes similar to highmem: various kernel caches can opt-in to be included in that type of RAM, and the complexity (and maintainance impact) of the approach can thus be nicely scaled.

i dont see the most fundamental problem listed: live kernel pointers pointing into a generic kernel RAM zone. Removing the 1:1 mapping and making the kernel VM space fully virtual will not solve that problem!

lets face it: removal of generic kernel RAM is a hard, and essentially unsolvable problem under the current Linux kernel model. It's not just the VM itself and 1:1 mappings (which is a nontrivial problem but which we can and probably should solve), it boils down to the fundamental choice of using C as the language of the kernel!

really, once you accept that, the path out of this mess becomes 'easy':
we _have to_ compromise on the feature side! And the moment we give up the notion of 'generic kernel RAM' and focus on the hot-removability of a limited-functionality zone, the complexity of the solution becomes three orders of magnitude smaller. No fragmentation avoidance necessary. No 'have to handle dozens of very hard problems to become 99% functional' issues. Once you make that zone an opt-in thing, it becomes much better from a development dynamics point of view as well.

i believe that it's also easier from an emotional point of view: our choice to use the C language forces us to abandon the idea of hot-removable generic kernel RAM. This is not some borderline decision where different people have different judgement - this is a hard, almost-mathematical fact that is forced upon us by the laws of physics (and/or whatever deity you might believe in). The same laws that make faster than O(N)*O(log(N)) sorting impossible. No amount of hacking will get us past that wall.

Ingo

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I agree. Especially considering that all this memory hotplug usage for hypervisors etc. is a relatively new thing with few of our userbase actually using it. I think a simple zones solution is the right way to go for now.

In future, if we have a large proportion of users who want it, and their requirements are better understood, and there is still no hardware / hypervisor support for handling this for us, *then* it is time to re-evaluate our compromise.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

btw., virtualization is pretty much a red herring here. Xen already has a 'balooning driver', where a guest OS can give back unused RAM on a page-granular basis. This is an advantage of having a fully virtualized guest OS. That covers 99% of the 'remove RAM' needs. So i believe the real target audience of hot-unplug is mostly limited to hardware-level RAM unplug.

[ Xen also offers other features like migration of live images to
another piece of hardware, which further dampen the cost of virtualization (mapping overhead, etc.). With hot-remove you dont get such compound benefits of a conceptually more robust and thus more pervasive approach. ]

Ingo

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I agree enough on concept that I think we can go implement at least a demonstration of how easy it is to perform.

There are a couple of implementation details that will require some changes to the current zone model, however. Perhaps you have some suggestions on those.

In which zone do we place hot-added RAM? I don't think answer can simply be the HOTPLUGGABLE zone. If you start with sufficiently small of a machine, you'll degrade into the same horrible HIGHMEM behavior that a 64GB ia32 machine has today, despite your architecture. Think of a machine that starts out with a size of 256MB and grows to 1TB.

So, if you have to add to NORMAL/DMA on the fly, how do you handle a case where the new NORMAL/DMA ram is physically above HIGHMEM/HOTPLUGGABLE? Is there any other course than to make a zone required to be able to span other zones, and be noncontiguous? Would that represent too much of a change to the current model?

Getting reclaim rates of the HIGHMEM and NORMAL zones balanced has been hard, and I worry that we never got it quite. Introducing yet another zone makes this harder.

Should we allow allocations for NORMAL to fall back into HOTPLUGGABLE in any case?

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

What can we do reasonably sanely? I think we can drive about 16GB of highmem per 1GB of normal fairly well. So on your 1TB system, you should be able to unplug 960GB RAM.

Lower the ratio to taste if you happen to be doing something particularly zone normal intensive - remember in that case the frag patches won't buy you anything more because a zone normal intensive workload is going to cause unreclaimable regions by definition.

Perhaps. Perhaps it wouldn't be required to get a solution that is "good enough" though.

But if you can reclaim your ZONE_RECLAIMABLE, then you could reclaim it all and expand your normal zones into it, bottom up.

We didn't get it right, but there are fairly simple things we can do
(http://marc.theaimsgroup.com/?l=linux-kernel&m=113082256231168&w=2)
to improve things remarkably, and having yet more users should result in even more improvements.

We still have ZONE_DMA and ZONE_DMA32, so we can't just afford to abandon zones because they're crap ;)

I think this would defeat the purpose if we really want to set limits, but we could have a sysctl perhaps to turn it on or off, or say, only allow it if the alternative is going OOM.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

That's a good point. It would be slow, because you have to wait on page reclaim, but it would work. I do worry a bit that this might make adding memory to slow of an operation to be useful for short periods, but we'll see how it actually behaves.

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I think you need to talk to some more users trying to run 16GB ia32 systems. Feel the pain.

Can we quit coming up with specialist hacks for hotplug, and try to solve the generic problem please? hotplug is NOT the only issue here. Fragmentation in general is.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

OK, make it 8GB then.

And as a bonus we get all you IBM guys back on the case again to finish the job that was started on highmem :)

And as another bonus, you actually *have* the capability to unplug memory or use hugepages exactly the size you require, which is not the case with the frag patches.

Not really it isn't. There have been a few cases (e1000 being the main one, and is fixed upstream) where fragmentation in general is a problem. But mostly it is not.

Anyone who thinks they can start using higher order allocations willy nilly after Mel's patch, I'm fairly sure they're wrong because they are just going to be using up the contiguous regions.

Trust me, if the frag patches were a general solution that solved the generic fragmentation problem I would be a lot less concerned about the complexity they introduce. But even then it only seems to be a problem that a very small number of users care about.

Anyway I keep saying the same things (sorry) so I'll stop now.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Sigh. OK, tell me how you're going to fix kernel stacks > 4K please. And devices that don't support scatter-gather DMA.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

with CONFIG_4KSTACKS :)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

2-page allocations are _not_ a problem.

Especially not for fork()/clone(). If you don't even have 2-page contiguous areas, you are doing something _wrong_, or you're so low on memory that there's no point in forking any more.

Don't confuse "fragmentation" with "perfectly spread out page allocations".

Fragmentation means that it gets _exponentially_ more unlikely that you can allocate big contiguous areas. But contiguous areas of order 1 are very very likely indeed. It's only the _big_ areas that aren't going to happen.

This is why fragmentation avoidance has always been totally useless. It is
- only useful for big areas
- very hard for big areas

(Corollary: when it's easy and possible, it's not useful).

Don't do it. We've never done it, and we've been fine. Claiming that fork() is a reason to do fragmentation avoidance is invalid.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

64 bit platforms need kernel stacks > 8K, it seems.

With respect, we have not been fine. We see problems fairly regularly with no large page/hotplug issues with higher order allocations. Drivers, CIFS, kernel stacks, etc, etc etc.

The larger memory gets, the worse the problem is, just because the statistics make it less likely to free up multiple contiguous pages.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

agreed for the general case. There are some corner cases that you can trigger deliberate in an artifical setting with lots of java threads (esp on x86 on a 32Gb box; the lowmem zone works as a lever here leading to "hyperfragmentation"; otoh on x86 you can do 4k stacks and it's gone mostly)

yup. only possible exception is the leveraged scenario .. thank god for 64 bit x86-64.

(and in the leveraged scenario I don't think active defragmentation will buy you much over the long term at all)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

For me, it's the big areas that I am interested in, especially if we want to give HugeTLB pages to a user when they are asking for them. The obvious one here is database and HPC loads, particularly the HPC loads which may not have had a chance to reserve what they needed at boot time. These loads need 1024 contiguous pages on the x86 at least, not 2. We can free all we want on todays kernels and you're not going to get more than 1 or two blocks this large unless you are very lucky.

Hotplug is, for me, an additional benefit. For others, it is the main benefit. For others of course, they don't care, but others don't are about scalability to 64 processors either but we provide it anyway at a low cost to smaller machines.

Unless you are a user that wants a large area when it suddenly is useful.

We've never done it but, but we've only supported HugeTLB pages being reserved at boot time and nothing else as well.

I'm going to setup a kbuild environment, hopefully this evening, and see are these patches adversely impacting a load that kernel developers care about. If I am impacting it, oops I'm in some trouble. If I'm not, then why not try and help out the people who care about the big areas.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

No. It's _not_ suddenly useful.

It might be something you _want_, but that's a totally different issue.

My point is that regardless of what you _want_, defragmentation is _useless_. It's useless simply because for big areas it is so expensive as to be impractical.

Put another way: you may _want_ the moon to be made of cheese, but a moon made out of cheese is _useless_ because it is impractical.

The only way to support big areas is to have special zones for them.

(Then, we may be able to use the special zones for small things too, but under special rules, like "only used for anonymous mappings" where we can just always remove them by paging them out. But it would still be a special area meant for big pages, just temporarily "on loan").

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The problem is how these zones get resized. Can we hotplug memory between them, with some sparsemem like indirection layer?

Real customers have shown us that their workloads shift, and they have different needs at different parts of the day. We can't just pick one size and call it good. It's the same argument as the traditional VM balancing act between pagecache, user pages, and kernel pages (which incidentally, we don't use zones for). We want the system to be able to use memory wherever it's most needed.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I think you should be able to add them. You can remove them. But you can't resize them.

And I suspect that by default, there should be zero of them. Ie you'd have to set them up the same way you now set up a hugetlb area.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Any particular reasons you think we can't resize them? I know shrinking the non-reclaim (DMA,NORMAL) zones will be practically impossible, but it should be quite possible to shrink the reclaim zone, and grow DMA or NORMAL into it.

This will likely be necessary as memory is added to a system, and the ratio of reclaim to non-reclaim zones gets out of whack and away from the magic 16:1 or 8:1 highmem:normal ratio that seems popular.

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

--Linus Torvalds <[email protected]> wrote (on Thursday, November 03, 2005 09:19:35 -0800):

So ... if there are 0 by default, and I run for a while and dirty up memory, how do I free any pages up to put into them? Not sure how that works.

Going back to finding contig pages for a sec ... I don't disagree with your assertion that order 1 is doable (however, we do need to make one fix ...see below). It's > 1 that's a problem.

For amusement, let me put in some tritely oversimplified math. For the sake of arguement, assume the free watermarks are 8MB or so. Let's assume a clean 64-bit system with no zone issues, etc (ie all one zone). 4K pages. I'm going to assume random distribution of free pages, which is oversimplified, but I'm trying to demonstrate a general premise, not get accurate numbers.

8MB = 2048 pages.

On a 64MB system, we have 16384 pages, 2048 free. Very rougly speaking, for each free page, chance of it's buddy being free is 2048/16384. So in grossly-oversimplified stats-land, if I can remember anything at all, chance of finding one page with a free buddy is 1-(1-2048/16384)^2048, which is, for all intents and purposes ... 1.

1 GB. system, 262144 pages 1-(1-2048/16384)^2048 = 0.9999989

128GB system. 33554432 pages. 0.1175 probability

yes, yes, my math sucks and I'm a simpleton. The point is that as memory gets bigger, the odds suck for getting contiguous pages. And would also explain why you think there's no problem, and I do ;-) And bear in mind that's just for order 1 allocs. For bigger stuff, it REALLY sucks - I'll spare you more wild attempts at foully-approximated math.

Hmmm. If we keep 128MB free, that totally kills off the above calculation I think I'll just tweak it so the limit is not so hard on really big systems. Will send you a patch. However ... larger allocs will still suck ... I guess I'd better gross you out with more incorrect math after all ...

that is VERY over simplified though, given the anti-fragmentation property of buddy algorithm

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Indeed. I write a program at one time doing random allocation and de-allocation and looking at what the output was, and buddy is very good at avoiding fragmentation.

These days we have things like per-cpu lists in front of the buddy allocator that will make fragmentation somewhat higher, but it's still absolutely true that the page allocation layout is _not_ random.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

OK, well I'll quit torturing you with incorrect math if you'll concede that the situation gets much much worse as memory sizes get larger ;-)

For order > 1 allocs, I think it's fixable. For order > 1, I think we basically don't have a prayer on a largish system under pressure.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I don't remember the specifics (I did the stats several years ago), but if I recall correctly, the low-order allocations actually got _better_ with more memory, assuming you kept a fixed percentage of memory free. So you actually needed _less_ memory free (in percentages) to get low-order allocations reliably.

But the higher orders didn't much matter. Basically, it gets exponentially more difficult to keep higher-order allocations, and it doesn't help one whit if there's a linear improvement from having more memory available or something like that.

So it doesn't get _harder_ with lots of memory, but

- you need to keep the "minimum free" watermarks growing at the same rate the memory sizes grow (and on x86, I don't think we do: at least at some point, the HIGHMEM zone had a much lower low-water-mark because it made the balancing behaviour much nicer. But I didn't check that).

- with lots of memory, you tend to want to get higher-order pages, and that gets harder much much faster than your memory size grows. So _effectively_, the kinds of allocations you care about are much harder to get.

If you look at get_free_pages(), you will note that we actyally _guarantee_ memory allocations up to order-3:

	...
        if (!(gfp_mask & __GFP_NORETRY)) {
                if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
                        do_retry = 1;
	...

and nobody has ever even noticed. In other words, low-order allocations really _are_ dependable. It's just that the kinds of orders you want for memory hotplug or hugetlb (ie not orders <=3, but >=10) are not, and never will be.

(Btw, my statistics did depend on that fact that the _usage_ was an even higher exponential, ie you had many many more order-0 allocations than you had order-1). You can always run out of order-n (n != 0) pages if you just allocate enough of them. The buddy thing works well statistically, but it obviously can't do wonders).

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

--Linus Torvalds <[email protected]> wrote (on Thursday, November 03, 2005 10:44:14 -0800):

Possibly, I can redo the calculations easily enough (have to go for now, but I just sent the other ones). But we don't keep a fixed percentage of memory free - we cap it ... perhaps we should though?

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I suspect the capping may well be from some old HIGHMEM interaction on x86 (ie "don't keep half a gig free in the normal zone just because we have 16GB in the high-zone". We used to have serious balancing issues, and I wouldn't be surprised at all if there are remnants from that. Stuff that simply hasn't been visible, because not a lot of people had many many GB of memory even on machines that didn't need HIGHMEM.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

But pages_min is based on the zone size, not the system size. And we still cap it. Maybe that's just a mistake?

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The per-zone watermarking is actually the "modern" and "working" approach.

We didn't always do it that way. I would not be at all surprised if the capping was from the global watermarking days.

Of course, I would _also_ not be at all surprised if it wasn't just out of habit. Most of the things where we try to scale things up by memory size, we cap for various reasons. Ie we tend to try to scale things like hash sizes for core data structures by memory size, but then we tend to cap them to "sane" versions.

So quite frankly, it's entirely possible that the capping is there not because it _ever_ was a good idea, but just because it's what we almost always do ;)

Mental inertia is definitely alive and well.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ha ;-) Well thanks for the explanation. I would suggest the patch I sent you makes some semblence of sense then ...

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Let me add that as memory sized get larger, people are also looking for more tlb coverage and less per page overhead.

Looks like ppc64 is getting 64K page support, at which point higher order allocations (eg. for stacks) basically disappear don't they?

x86-64 I thought were also getting 64K page support but I can't find a reference to it right now - at the very least I know Andi wants to support larger soft pages for it.

ia64 is obviously already well covered.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Yes and no, HOWEVER, nobody sane will ever use 64kB pages on a general-purpose machine.

64kB pages are _only_ usable for databases, nothing else.

Why? Do the math. Try to cache the whole kernel source tree in 4kB pages vs 64kB pages. See how the memory usage goes up by a factor of _four_.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Actually people running HPC apps also like 64kB pages since their TLB misses go down significantly, and their data files tend to be large.

Fileserving for windows boxes should also benefit, since both the executables and the data files that typical office applications on windows use are largish. I got a distribution of file sizes for a government department office and concluded that 64k pages would only bloat the page cache by a few percent for that case.

Paul.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Yeah that's true. But Martin's worried about future machines with massive memories - so maybe it is safe to assume those will be using big pages, I don't know.

Maybe the solution is to bloat the kernel sources enough to make 64KB pages worthwhile?

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Todays massive machines are tomorrows desktop. Weak comment, I know, but it's happened before.

root@monocle:/boot# ls -l vmlinuz-2.6.14-rc5-mm1-clean
-rw-r--r--  1 root root 1718063 2005-11-01 16:17
vmlinuz-2.6.14-rc5-mm1-clean
root@monocle:/boot# ls -l vmlinuz-2.6.14-rc5-mm1-mbuddy-v19
-rw-r--r--  1 root root 1722102 2005-11-02 14:56
vmlinuz-2.6.14-rc5-mm1-mbuddy-v19
root@monocle:/boot# dc
1722102
1718063
- p
4039

root@monocle:/boot# ls -l vmlinux-2.6.14-rc5-mm1-clean
-rwxr-xr-x  1 root root 31518866 2005-11-01 16:17
vmlinux-2.6.14-rc5-mm1-clean
root@monocle:/boot# ls -l vmlinux-2.6.14-rc5-mm1-mbuddy-v19
-rwxr-xr-x  1 root root 31585714 2005-11-02 14:56
vmlinux-2.6.14-rc5-mm1-mbuddy-v19

mel@joshua:/usr/src/patchset-0.5/kernels/linux-2.6.14-rc5-mm1-nooom$ wc -l mm/page_alloc.c
2689 mm/page_alloc.c
mel@joshua:/usr/src/patchset-0.5/kernels/linux-2.6.14-rc5-mm1-mbuddy-v19-withdefrag$  wc -l mm/page_alloc.c
3188 mm/page_alloc.c

0.23% increase in size of bzImage, 0.21% increase in the size of vmlinux and the major increase in code size is in one file, *one* file, all of which does it's best to impact the flow of the well-understood code. We're seeing bigger differences in performance than we are in the size of the kernel. I'd understand if I was the first person to ever introduce complexity to the VM.

If the size of the image for really small systems is the issue, what if I say I'll add in another patch that optionally compiles away as much of anti-defrag as possible without making the code a mess of #defines . Are we still going to hear "no, I don't like looking at this". The current patch to compile it away deliberately choose the smallest part to take away to restore the allocator to todays behavior.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Oh I wouldn't bet against it. And if desktops of the future are using 100s of GB then they probably would be happy to use 64K pages as well.

Sorry this wasn't meant to be a dig at your patches - I guess it turned out that way though :\

But yes, if anybody is adding complexity or size to core code it obviously does need to be justified -- and by no means does this only apply to you.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

And would it not be nice to be ready when it happens, before it happens even?

Oh, I'll live. If I was going to take it personally and go into a big sulk, I wouldn't be here. This is linux-kernel, not the super-friends club.

I've tried to justify it with benchmarks that came with each release and code reviews, particularly by Dave Hansen, showed that earlier versions had significant problems that needed to be ironed out. I don't want to hurt the normal case, because the fact of the matter is, my desktop machine (which runs with these patches to see if there are any bugs) runs the normal case and it will until we get much further because I'm not configuring my machine for HugeTLB when it boots. If I'm hurting the normal case, that's more time switching windows to see if the next test kernel has built yet.

If we can do this and not regress in the standard case, then what is wrong? I'm still waiting for figures that say this approach is slow and I can only assume someone is trying considering the length of this thread. If and when those figures show up, I'll put on the thinking hat and see where I went wrong because regression performance is wrong. There is a win-win solution somewhere, how hard could it possibly be :) ?

I'm looking at the zone approach. I want to see if it can work in a nice fashion, not in a "if the sysadm can see the future and configure correctly, it'll work just fine" fashion. I'm not confident, but it might be bias.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Very well, but if the infrastructure required to help get 64kB pages still performs the same, or better, than the current infrastructure that gives 4kB pages, then why not? I am biased obviously and probably optimistic but I am hoping we have a case here where we get our cake and eat it twice.

I don't know, but I doubt they would use 64kB pages as the default size unless it is a specialised machine. I could be wrong, I don't have a ppc64 machine, I don't work on a ppc64 machine, I haven't read the architectures documentation and I didn't write this code for a ppc64 machine. If the machine here in question it's a specialised machine, they go into the 0.01% category of people, but it's a group that we can still help without introducing static zones they have to configure.

I'm still waiting on figures that say the approach proposed here is actually really slow, rather than makes people unhappy slow. If this is proved to be slow, then I'll admit there is a problem and put more effort into the plans to use zones instead. I just haven't found a problem on the machines I have available to me, be it aim9, bench-stresshighalloc or building kernels (which I think is important considering how often I build test kernels). If it's a documentation problem with these patches, I'll write up VM docs on the allocator and submit it as a patch, complete with downsides and caveats to be fair.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The statistical properties of the buddy system are a nightmare. There is a paper called "Statistical Properties of the Buddy System" which is a whole pile of no fun to read. It's because of the difficulty to analyse fragmentation offline that bench-stresshighalloc was written to see how well anti-defrag would do.

The worse cause of fragmentation I found were kernel caches that were long lived. How fragmenting the workload is depended heavily on whether things like updatedb happened which is why bench-stresshighalloc deliberately ran it. It's also why anti-defrag tries to group inodes and buffer_heads into the same areas in memory separate from other persumed-to-be-even-longer-lived kernel allocations. The assumption is if the buffer, inode and dcaches are all shrunk, contiguous blocks will appear.

You're also right on the size of the watermarks for zones and how it affects fragmentation. A serious problem I had with anti-defrag was when 87.5% of memory is in use. At this point, a "fallback" area is used by any allocation type that has no pages of it's own. When it is depleted, real fragmentation starts happening and it's also about here that the high watermark for reclaiming starts. I wanted to increase the watermarks up to start reclaiming pages when the "fallback" area started getting used but didn't think I would get away with adjusting those figures. I could have cheated and set it via /proc before benchmarks but didn't to avoid "magic test system" syndrome.

It's worse than somewhat higher for the per-cpu pages. Using another set of patches on top of an earlier version of anti-defrag, I was about to allocate about 75% of physical memory in pinned 4MiB chunks of memory under loads of 15-20 (kernel builds). To get there, per-cpu pages had to be drained using an IPI call because for some perverse reason, there were always 2 or 3 free per-cpu pages in the middle of a 1024 block of pages.

Basically, I don't we have to live with fragmentation in the page allocator. I think it can be pushed down a whole lot without taking a performance hit for the 99.99% of users that don't care about this sort of thing.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

You don't.

Just face it - people who want memory hotplug had better know that beforehand (and let's be honest - in practice it's only going to work in virtualized environments or in environments where you can insert the new bank of memory and copy it over and remove the old one with hw support).

Same as hugetlb.

Nobody sane _cares_. Nobody sane is asking for these things. Only people with special needs are asking for it, and they know their needs.

You have to realize that the first rule of engineering is to work out the balances. The undeniable fact is, that 99.99% of all users will never care one whit, and memory management is complex and fragile. End result: the 0.01% of users will have to do some manual configuration to keep things simpler for the cases that really matter.

Because the case that really matters is the sane case. The one where we
- don't change memory (normal)
- only add memory (easy)
- only switch out memory with hardware support (ie the _hardware_ supports parallel memory, and you can switch out a DIMM without software ever really even noticing)
- have system maintainers that do strange things, but _know_ that.

We simply DO NOT CARE about some theoretical "general case", because the general case is (a) insane and (b) impossible to cater to without excessive complexity.

Guys, a kernel developer needs to know when to say NO.

And we say NO, HELL NO!! to generic software-only memory hotplug.

If you are running a DB that needs to benchmark well, you damn well KNOW IT IN ADVANCE, AND YOU TUNE FOR IT.

Nobody takes a random machine and says "ok, we'll now put our most performance-critical database on this machine, and oh, btw, you can't reboot it and tune for it beforehand". And if you have such a person, you need to learn to IGNORE THE CRAZY PEOPLE.

When you hear voices in your head that tell you to shoot the pope, do you do what they say? Same thing goes for customers and managers. They are the crazy voices in your head, and you need to set them right, not just blindly do what they ask for.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The lawyers have a phrase for this:

Hard cases make bad law.

For us, that's bad code.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

For HugeTLB, there are cases were the sysadmin won't configure the server because it's a tunable that can badly affect the machine if they get it wrong. In those cases, the users just get small pages, the performance penalty and are told to like it.

Ok, so lets consider the 99.99% of users then. One two machines, aim9 benchmarks posted during this thread show some improvements on page_test, fork_test and brk_test, the paths you would expect to be hit by these patches. They are very minor improvements but 99.99% of users benefit from this. Aim9 might be considered artifical so somewhere in that 99.99% of users are kernel developers who care about kbuild so here are the timings of "kernel untar ; make defconfig ; make"

2.6.14-rc5-mm1: 1093 seconds
2.6.14-rc5-mm1-mbuddy-v19-withoutdefrag 1089 seconds 2.6.14-rc5-mm1-mbuddy-v19-withdefrag:: 1086 seconds

The withoutdefrag mark is with the core of anti-defrag disabled via a configure option. The option to disable was a separate patch produced during this thread. To be really honest, I don't think a configurable page allocator is a great idea.

Building kernels is faster with this set of patches which a few people on this list care about. aim9 shows very minor improvements which benefit a very large number of people and 0.01% of people who care about fragmentation get lower fragmentation.

Of course, maybe there is something magic with my test machines (or maybe I am willing it faster) so figures from other people wouldn't hurt whether they show gains or regressions. On my machine at least, 99.99% of people are still benefitting.

I am going to wait to see if people post figures that show regressions before asking "are you still saying no?" to this set of patches

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ha. Just because I don't think I made you puke hard enough already with foul approximations ... for order 2, I think it's

1-(1-(free_pool/total)^3)^free_pool

because all 3 of his buddies have to be free as well. (and generically ... 2^order - 1)

ORDER: 1

1024MB system, 8MB pool = 1.000000
131072MB system, 8MB pool = 0.117506
1024MB system, 128MB pool = 1.000000
131072MB system, 128MB pool = 1.000000

ORDER: 2

1024MB system, 8MB pool = 0.000976
131072MB system, 8MB pool = 0.000000
1024MB system, 128MB pool = 1.000000
131072MB system, 128MB pool = 0.000031

ORDER: 3

1024MB system, 8MB pool = 0.000000
131072MB system, 8MB pool = 0.000000
1024MB system, 128MB pool = 0.015504
131072MB system, 128MB pool = 0.000000

ORDER: 4

1024MB system, 8MB pool = 0.000000
131072MB system, 8MB pool = 0.000000
1024MB system, 128MB pool = 0.000000
131072MB system, 128MB pool = 0.000000

------------------------

I really should learn not to post my rusty math in such public places ... but I still think the point is correct. Anyway, I'm sure somewhere in the resultant flamewar, someone will come up with some better approx ;-)

And yes, I appreciate the random distribution thing is wrong. But it's still not going to work for bigger allocs. Fixing the free watermarks will help us a bit though.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Your basic fault is in believing that the free watermark would stay constant.

That's insane.

Would you keep 8MB free on a 64MB system?

Would you keep 8MB free on a 8GB system?

The point being, that if you start with insane assumptions, you'll get insane answers.

The _correct_ assumption is that you aim to keep some fixed percentage of memory free. With that assumption and your math, finding higher-order pages is equally hard regardless of amount of memory.

Now, your math then doesn't allow for the fact that buddy automatically coalesces for you, so in fact things get _easier_ with more memory, but hey, that needs more math than I can come up with (I never did it as math, only as simulations with allocation patterns - "smart people use math, plodding people just try to simulate an estimate" ;)

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ummm. I was basing it on what we actually do now in the code, unless I misread it, which is perfectly possible. Do you want this patch?

diff -purN -X /home/mbligh/.diff.exclude linux-2.6.14/mm/page_alloc.c 2.6.14-no_water_cap/mm/page_alloc.c
@@ -2387,8 +2387,6 @@ static void setup_per_zone_pages_min(voi
 			min_pages = zone->present_pages / 1024;
 			if (min_pages < SWAP_CLUSTER_MAX)
 				min_pages = SWAP_CLUSTER_MAX;
-			if (min_pages > 128)
-				min_pages = 128;
 			zone->pages_min = min_pages;
 		} else {
 			/* if it's a lowmem zone, reserve a number of pages

That would, indeed, make more sense.

Not sure what people who do math, but wrongly, are called, but I'm sure it's not polite, and I'm sure I'm one of those ;-)

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Hmm. it strikes me that there will be few (if any?) allocations out of highmem. PPC64 et al dump everything into ZONE_DMA though - so those should be uncapped already.

Well it's not 16MB on the other platforms, but ...

Yes. So we were only capping highmem before, now I squint at it closer. I was going off a simplification I'd written for a paper, which is not generally correct. I doubt frag is a problem in highmem, so maybe the code is correct as-is. We only want contig allocs for virtual when it's mapped 1-1 to physical (ie the kernel mapping) or real physical things.

I suppose I could write something to trawl the source tree to check that assumption, but it feels right ...

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I'd prefer not. The reason is that it increases the "min" watermark, which only gets used basically by GFP_ATOMIC and PF_MEMALLOC allocators - neither of which are likely to want highmem.

Also, I don't think anybody cares about higher order highmem allocations. At least the patches in this thread:
http://marc.theaimsgroup.com/?l=linux-kernel&m=113082256231168&w=2

Should be applied before this. However they also need more testing so I'll be sending them to Andrew first.

Patch 2 does basically the same thing as your patch, without increasing the min watermark.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

No, that was me and Matthew Dobson, circa 2.5.71. The thinking was that highmem is just for userspace pages and we don't need to keep the free memory pool around for things like atomic allocations. Especially as a proportionally-sized highmem emergency pool would be potentially hundreds of (wasted) megabytes.

iirc, things worked ok with a highmem min_pages threshold of zero pages. Back in 2.5.70, before everyone else broke it ;)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

My math is not that great either, so here is a simulation.

Setup: Reboot the machine which is a quad xeon xSeries 350 with 1.5GiB of RAM. Configure /proc/sys/vm/min_free_kbytes to try and keep 1/8th of physical memory free. This is to keep in line with your suggestion that fragmentation is low when there is a higher percentage of memory free.

Load: Run a load - 7 kernels compiling simultaneously at -j2 which gives loads between 10-14. Try and get 50% worth of physical memory in 4MiB pages (1024 contiguous pages) while compiling. When the test ends and the system is quiet, try again. 4MiB in this case is a single HugeTLB page.

Here are the results;

2.6.14-rc5-mm1-clean (OOM killer disabled) Allocating Under Load

Order:                 10
Allocation type:       HighMem
Attempted allocations: 160
Success allocs:        24
Failed allocs:         136
DMA zone allocs:       0
Normal zone allocs:    16
HighMem zone allocs:   8

% Success: 15

2.6.14-rc5-mm1-mbuddy-v19 Allocating Under Load

Order:                 10
Allocation type:       HighMem
Attempted allocations: 160
Success allocs:        24
Failed allocs:         136
DMA zone allocs:       0
Normal zone allocs:    11
HighMem zone allocs:   13

% Success: 15

Not a lot of difference there and the success rate is not great. mbuddy-v19 is a bit better at the normal zone and that's about it. These results are not surprising as kswapd is making no effort to get contiguous pages. Under a load of 7 kernel compiles, kswapd will not free pages fast enough.

When the test ends and the system is quiet, try and get 80% of physical memory in large pages. 4 attempts are made to satisfy the requests to give kswapd lots of time.

2.6.14-rc5-mm1-clean (OOM killer disabled) Allocating while rested

Order:                 10
Allocation type:       HighMem
Attempted allocations: 300
Success allocs:        159
Failed allocs:         141
DMA zone allocs:       0
Normal zone allocs:    46
HighMem zone allocs:   113

% Success: 53

Mainly highmem there.

2.6.14-rc5-mm1-mbuddy-v19 Allocating while rested

Order:                 10
Allocation type:       HighMem
Attempted allocations: 300
Success allocs:        212
Failed allocs:         88
DMA zone allocs:       0
Normal zone allocs:    102
HighMem zone allocs:   110

% Success: 70

Look at the big difference in the number of successful allocations in ZONE_NORMAL because the kernel allocations were kept together. Experience has shown me that failure to get higher success rates depended on per-cpu pages and the number of kernel pages that leaked to other areas (56 over the course of this test). Kernel pages leaking was helped a lot by setting min_free_kbytes higher than the default.

I then ported forward the linear scanner and ran the tests again. The linear scanner does two things - finds linear reclaimable pages using information provided by anti-defrag and drains the per-cpu caches. I'll post the linear scanner code if people want to look at it but it's really crap. It's slow, works too hard and doesn't try to hold on to the pages for the process reclaiming the pages are just some of it's problems. I need to rewrite it almost from scratch and avoid all the mistakes but it's a path that is hit *only* if you are allocating high orders.

2.6.14-rc5-mm1-mbuddy-v19-lnscan Allocating under load

Order:                 10
Allocation type:       HighMem
Attempted allocations: 160
Success allocs:        155
Failed allocs:         0
DMA zone allocs:       0
Normal zone allocs:    12
HighMem zone allocs:   143

% Success: 96

Mainly got it's pages back from highmem which is always easier as long as PTE pages are not in the way.

2.6.14-rc5-mm1-mbuddy-v19-lnscan Allocating while rested

Order:                 10
Allocation type:       HighMem
Attempted allocations: 300
Success allocs:        275
Failed allocs:         0
DMA zone allocs:       0
Normal zone allocs:    133
HighMem zone allocs:   142

% Success: 91

That is 71% of physical memory available in contiguous blocks with the linear scanner but that code is not ready. anti-defrag on it's own as it is today was able to get 55% of physical memory in 4MiB chunks.

This is provided without performance regressions in the normal case everyone cares about. In my tests, there are minor improvements on aim9 which is artificial, and gained a few seconds on kernel build tests which people do care about.

Does these patches still make no sense to you? Lower fragmentation that does not impact the cases everyone cares about? If so, why?

To get the best possibly results, a zone approach could still be built on top of this and it seems as if it's worth developing. At the cost of some configuration, the zone would give *hard* guarantees on the available number of large pages and anti-defrag would give best effort everywhere else. By default without configuration, you would get best-effort.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

--Arjan van de Ven <[email protected]> wrote (on Thursday, November 03, 2005 16:40:21 +0100):

I've been told previously that doesn't work for x86_64, and other 64 bit platforms. Is that incorrect?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Forget about freeing up arbitrary regions of RAM. I don't think anyone has strong enough drugs to seriously believe that works in the generic case. What we need is to free a small region of RAM, that's contiguous. Larger than one page, likely a few MB. Exactly WHICH region is pretty irrelevant, since mostly we just want one contiguous chunk to use.

Hypervisors do not remap at page-level granularity - that seems to be the source of some of the confusion here.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Hi, I'm one of men in -lhms

In my understanding...
- Memory Hotremove on IBM's LPAR? approach is
[remove some amount of memory from somewhere.]
For this approach, Mel's patch will work well.
But this will not guaranntee a user can remove specified range of memory at any time because how memory range is used is not defined by an admin but by the kernel automatically. But to extract some amount of memory, Mel's patch is very important and they need this.

My own target is NUMA node hotplug, what NUMA node hotplug want is
- [remove the range of memory] For this approach, admin should define *core* node and removable node. Memory on removable node is removable. Dividing area into removable and not-removable is needed, because
we cannot allocate any kernel's object on removable area.
Removable area should be 100% removable. Customer can know the limitation before using.

What I'm considering now is this:
- removable area is hot-added area
- not-removable area is memory which is visible to kernel at boot time. (I'd like to achieve this by the limitation : hot-added node goes into only ZONE_HIGHMEM) A customer can hot add their extra memory after boot. This is very easy to understand. Peformance problem is trade-off.(I'm afraid of this ;)

If a cutomer wants to guarantee some memory areas should be hot-removable, he will hot-add them.
I don't think adding memory for the kernel by hot-add is wanted by a customer.

-- Kame

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

One more consideration...
Some cpus which support virtialization will be shipped by some vendor in near future. If someone uses vitualized OS, only problem is *resizing*.
Hypervisor will be able to remap semi-physical pages anyware with hardware assistance but system resizing needs operating system assistance.
To this direction, [remove some amount of memory from somewhere.] is important approach.

-- Kame

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

In this case, we would want some mechanism that says "don't put awkward pages in this NUMA node" in a clear way. One way we could do this is;

1. Move fallback_allocs to be per-node. fallback_allocs is currently defined as
int fallback_allocs[RCLM_TYPES-1][RCLM_TYPES+1] = {

        {RCLM_NORCLM,   RCLM_FALLBACK, RCLM_KERN,   RCLM_EASY, RCLM_TYPES},
        {RCLM_EASY,     RCLM_FALLBACK, RCLM_NORCLM, RCLM_KERN, RCLM_TYPES},
        {RCLM_KERN,     RCLM_FALLBACK, RCLM_NORCLM, RCLM_EASY, RCLM_TYPES}

};

The effect is that a RCLM_NORCLM allocation, falls back to RCLM_FALLBACK, RCLM_KERN, RCLM_EASY and then gives up.

2. Architectures would need to provide a function that allocates and populates a fallback_allocs[][] array. If they do not provide one, a generic function uses array like the one above

3. When adding a node that must be removable, make the array look like this

int fallback_allocs[RCLM_TYPES-1][RCLM_TYPES+1] = {

        {RCLM_NORCLM,   RCLM_TYPES,    RCLM_TYPES,  RCLM_TYPES, RCLM_TYPES},
        {RCLM_EASY,     RCLM_FALLBACK, RCLM_NORCLM, RCLM_KERN, RCLM_TYPES},
        {RCLM_KERN,     RCLM_TYPES,    RCLM_TYPES,  RCLM_TYPES, RCLM_TYPES},

};

The effect of this is only allocations that are easily reclaimable will end up in this node. This would be a straight-forward addition to build upon this set of patches. The difference would only be visible to architectures that cared.

ZONE_HIGHMEM can still end up with PTE pages if allocating PTE pages from highmem is configured. This is bad. With the above approach, nodes that are not hot-added that have a ZONE_HIGHMEM will be able to use it for PTEs as well. But when a node is hot-added, it will have a ZONE_HIGHMEM that is not used for PTE allocations because they are not RCLM_EASY allocations.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Thank you for illustration.
maybe fallback_list per pgdat/zone is what I need with your patch. right ?

-- Kame

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

With my patch, yes. With zones, you need to change how zonelists are built for each node.

Mel Gorman
Part-time Phd Student                          Java Applications Developer
University of Limerick                         IBM Dublin Software Lab

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

With ix86 machines, the page directory pointed to by CR3 needs to always be present in physical memory. This means that there must always be some RAM that can't be hot-swapped (you can't put back the contents of the page-directory without using the CPU which needs the page directory).

This is explained on page 5-21 of the i486 reference manual. This happens because there is no "present" bit in CR3 as there are in the page tables themselves.

This problem means that "surprise" swaps are impossible. However, given a forewarning, it is possible to build a new table somewhere in existing RAM within the physical constraints required, call some code there (needs to be a 1:1 translation), disable paging, then proceed. The problem is that of writing of the contents of RAM to be replaced, to storage media so the new page-table needs to be loaded from the new location. This may not work if the LDT and the GDT are not accessible from their current locations. If they are in the RAM to be replaced, you are in a world of hurt taking the "world" apart and putting it back together again.

Cheers,
Dick Johnson
Penguin : Linux version 2.6.13.4 on an i686 machine (5589.55 BogoMips). Warning : 98.36% of all statistics are fiction.
.

****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

that's a perfectly fine method, and is quite similar to the 'separate zone' approach Nick mentioned too. It is also easily understandable for users/customers.

under such an approach, things become easier as well: if you have zones you can to restrict (no kernel pinned-down allocations, no mlock-ed pages, etc.), there's no need for any 'fragmentation avoidance' patches! Basically all of that RAM becomes instantly removable (with some small complications). That's the beauty of the separate-zones approach. It is also a limitation: no kernel allocations, so all the highmem-alike restrictions apply to it too.

but what is a dangerous fallacy is that we will be able to support hot memory unplug of generic kernel RAM in any reliable way!

you really have to look at this from the conceptual angle: 'can an approach ever lead to a satisfactory result'? If the answer is 'no', then we _must not_ add a 90% solution that we _know_ will never be a 100% solution.

for the separate-removable-zones approach we see the end of the tunnel. Separate zones are well-understood.

generic unpluggable kernel RAM _will not work_.

Ingo

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Actually, it will. Well, depending on terminology.

There are two usage models here - those which intend to remove physical elements and those where the kernel returnss management of its virtualized "physical" memory to a hypervisor. In the latter case, a hypervisor already maintains a virtual map of the memory and the OS needs to release virtualized "physical" memory. I think you are referring to RAM here as the physical component; however these same defrag patches help where a hypervisor is maintaining the real physical memory below the operating system and the OS is managing a virtualized "physical" memory.

On pSeries hardware or with Xen, a client OS can return chunks of memory to the hypervisor. That memory needs to be returned in chunks of the size that the hypervisor normally manages/maintains. But long ranges of physical contiguity are not required. Just shorter ranges, depending on what the hypervisor maintains, need to be returned from the OS to the hypervisor.

In other words, if we can return 1 MB chunks, the hypervisor can hand out those 1 MB chunks to other domains/partitions. So, if we can return 500 1 MB chunks from a 2 GB OS instance, we can add 500 MB dyanamically to another OS image.

This happens to be a *very* satisfactory answer for virtualized environments.

The other answer, which is harder, is to return (free) entire large physical chunks, e.g. the size of the full memory of a node, allowing a node to be dynamically removed (or a DIMM/SIMM/etc.).

So, people are working towards two distinct solutions, both of which require us to do a better job of defragmenting memory (or avoiding fragementation in the first place).

gerrit

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

This is just going around in circles. Even with your fragmentation avoidance and memory defragmentation, there are still going to be cases where memory does get fragmented and can't be defragmented. This is Ingo's point, I believe.

Isn't the solution for your hypervisor problem to dish out pages of the same size that are used by the virtual machines. Doesn't this provide you with a nice, 100% solution that doesn't add complexity where it isn't needed?

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

So do you see the problem with fragementation if the hypervisor is handing out, say, 1 MB pages? Or, more likely, something like 64 MB pages? What are the chances that an entire 64 MB page can be freed on a large system that has been up a while?

And, if you create zones, you run into all of the zone rebalancing problems of ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM. In that case, on any long running system, ZONE_HOTPLUGGABLE has been overwhelmed with random allocations, making almost none of it available.

However, with reasonable defragmentation or fragmentation avoidance, we have some potential to make large chunks available for return to the hypervisor. And, that same capability continues to help those who want to remove fixed ranges of physical memory.

gerrit

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I see the problem, but if you want to be able to shrink memory to a given size, then you must either introduce a hard limit somewhere, or have the hypervisor hand out guest sized pages. Use zones, or Xen?

If there are zone rebalancing problems[*], then it would be great to have more users of zones because then they will be more likely to get fixed.

[*] and there are, sadly enough - see the recent patches I posted to
lkml for example. But I'm fairly confident that once the particularly silly ones have been fixed, zone balancing will no longer be a derogatory term as has been thrown around (maybe rightly) in this thread!

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

So why do you believe there must be a hard limit?

Any reduction in memory usage is going to be workload related. If the workload is consuming less memory than is available, memory reclaim is easy (e.g. handle fragmentation, find nice sized chunks). The workload determines how much the administrator can free. If the workload is using all of the resources available (e.g. lots of associated kernel memory locked down, locked user pages, etc.) then the administrator will logically be able to reduce less memory from the machine.

The amount of memory to be freed up is not determined by some pre-defined machine constraints but based on the actual workload's use of the machine.

In other words, who really cares if there is some hard limit? The only limit should be the number of pages not currently needed by a given workload, not some arbitrary zone size.

You are more optimistic here than I. You might have improved the problem but I think that any zone rebalancing problem is intrinsicly hard given the way those zones are used and the fact that we sort of want them to be dynamic and yet physically contiguous. Those two core constraints seem to be relatively at odds with each other.

I'm not a huge fan of dividing memory up into different types which are all special purposed. Everything that becomes special purposed over time limits its use and brings up questions on what special purpose bucket each allocation should use (e.g. ZONE_NORMAL or ZONE_HIGHMEM or ZONE_DMA or ZONE_HOTPLUGGABLE). And then, when you run out of ZONE_HIGHMEM and have to reach into ZONE_HOTPLUGGABLE for some pinned memory allocation, it seems the whole concept leads to a messy train wreck.

gerrit

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

In the UML case, I want the system to automatically be able to hand back any sufficiently large chunks of memory it currently isn't using.

What does this have to do with specifying hard limits of anything? What's to specify? Workloads vary. Deal with it.

Ok, so you want to artificially turn this into a zone balancing issue in hopes of giving that area of the code more testing when, if zones weren't involved, there would be no need for balancing at all?

How does that make sense?

I was under the impression that zone balancing is, conceptually speaking, a difficult problem.

Great, you're advocating migrating the fragmentation patches to an area of code that has known problems you yourself describe as "particularly silly". A ringing endorsement, that.

The fact that the migrated version wouldn't even address fragmentation avoidance at all (the topic of this thread!) is apparently a side issue.

If I'm not mistaken, you introduced zones into this thread, you are the primary (possibly only) proponent of them. Yes, zones are a way of categorizing memory. They're not a way of defragmenting it.

Rob

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I'd just be happy with UML handing back page sized chunks of memory that it isn't currently using. How does contiguous memory (in either the host or the guest) help this?

Umm, if you hadn't bothered to read the thread then I won't go through it all again. The short of it is that if you want guaranteed unfragmented memory you have to specify a limit.

Have you looked at the frag patches? Do you realise that they have to balance between the different types of memory blocks? Duplicating the same or similar infrastructure (in this case, a memory zoning facility) is a bad thing in general.

I am under the impression that you think proper fragmentation avoidance is easier.

Err, the point is so we don't now have 2 layers doing very similar things, at least one of which has "particularly silly" bugs in it.

Zones can be used to guaranteee physically contiguous regions with exactly the same effectiveness as the frag patches.

So you didn't look at Yasunori Goto's patch from last year that implements exactly what I described, then?

Yes, have you read Mel's patches? Guess what they do?

Guess what they don't?

Send instant messages to your online friends http://au.messenger.yahoo.com

Smaller chunks of memory are likely to be reclaimed really soon, and adding in the syscall overhead working with individual pages of memory is almost guaranteed to slow us down. Plus with punch, we'd be fragmenting the heck out of the underlying file.

I read it. It just didn't contain an answer the the question. I want UML to be able to hand back however much memory it's not using, but handing back individual pages as we free them and inserting a syscall overhead for every page freed and allocated is just nuts. (Plus, at page size, the OS isn't likely to zero them much faster than we can ourselves even without the syscall overhead.) Defragmentation means we can batch this into a granularity that makes it worth it.

This has nothing to do with hard limits on anything.

I've read Mel's various descriptions, and tried to stay more or less up to date ever since LWN brought it to my attention. But I can't say I'm a linux VM system expert. (The last time I felt I had a really firm grasp on it was before Andrea and Rik started arguing circa 2.4 and Andrea spent six months just assuming everybody already knew what a classzone was. I've had other things to do since then...)

I realise they merge them back together into larger chunks as they free up space, and split larger chunks when they haven't got a smaller one.

Even when they keep track of very different things? The memory zoning thing is about where stuff is in physical memory, and it exists because various hardware that wants to access memory (24 bit DMA, 32 bit DMA, and PAE) is evil and crippled and we have to humor it by not asking it to do stuff it can't.

The fragmentation stuff is about what long contiguous runs of free memory we can arrange, and it's also nice to be able to categorize them as "zeroed" or "not zeroed" to make new allocations faster. Where they actually are in memory is not at issue here.

You can have prezeroed memory in 32 bit DMA space, and prezeroed memory in highmem, but there's memory in both that isn't prezeroed. I thought there was a hierarchy of zones. You want overlapping, interlaced, randomly laid out zones.

I was under the impression it was orthogonal to figuring out whether or not a given bank of physical memory is accessable to your sound blaster without an IOMMU.

Similar is not identical. You seem to be implying that the IO elevator and the network stack queueing should be merged because they do similar things.

If you'd like to write a counter-patch to Mel's to prove it...

I saw the patch he just posted, if that's what you mean. By his own admission, it doesn't address fragmentation at all.

The swap file is a way of storing data on disk. So is ext3. Obviously, one is a trivial extension of the other and there's no reason to have both.

I have no idea what you intended to mean by that. Mel posted a set of patches in a thread titled "fragmentation avoidance", and you've been arguing about hotplug, and pointing to a set of patches from Goto that do not address fragmentation at all. This confuses me.

Rob

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Because UML doesn't already make a syscall per individual page of memory freed? (If I read correctly)

Why? No you wouldn't.

Oh you have measured it and found out that "defragmentation" makes it worthwhile?

You said:

"What does this have to do with specifying hard limits of
anything? What's to specify? Workloads vary. Deal with it."

And I was answering your very polite questions.

Maybe you have better things to do now as well?

No, the buddy allocator is and always has been what tracks the "long contiguous runs of free memory". Both zones and Mels patches classify blocks of memory according to some criteria. They're not exactly the same obviously, but they're equivalent in terms of capability to guarantee contiguous freeable regions.

Huh?

No I don't.

It has already been written as you have been told numerous times.

Now if you'd like to actually learn about what you're commenting on, that would be really good too.

It seems to be that it provides exactly the same (actually stronger) guarantees than the current frag patches do. Or were you going to point out a bug in the implementation?

Don't try to bullshit your way around with stupid analogies please, it is an utter waste of time.

What I mean is that Mel's patches aren't a way of defragmenting memory either. They fit exactly the description you gave for zones (ie. a way of categorizing, not defragmenting).

Yeah it does seem like you are confused.

Now let's finish up this subthread and try to keep the SN ratio up, please? I'm sure Jeff or someone knowledgeable in the area can chime in if there are concerns about UML.

Send instant messages to your online friends http://au.messenger.yahoo.com

UML does a big mmap to get "physical" memory, and then manages itself using the normal Linux kernel mechanisms for doing so. We even have page tables, although I'm still somewhat unclear on quite how that works.

Creating holes in the file and freeing up the underlying blocks on disk? 4k at a time? Randomly scattered?

Lots of work has gone into batching up syscalls and making as few of them as possible because they are a performance bottleneck. You want to introduce a syscall for every single individual page of memory allocated or freed.

That's stupid.

You didn't answer. You keep saying you've already answered, but there continues to be no answer. Maybe you think you've answered, but I haven't seen it yet. You brought up hard limits, I asked what that had to do with anything, and in response you quote my question back at me.

Yeah, thanks for reminding me. I need to test Mel's newest round of fragmentation avoidance patches in my UML build system...

We are still discussing fragmentation avoidance, right? (I know _I'm_ trying to...)

Back up.

I don't care _where_ the freeable regions are. I just wan't them coalesced.

Zones are all about _where_ the memory is.

I'm pretty sure we're arguing past each other.

Fragmentation avoidance is what is orthogonal to...

They're similar though, aren't they? Why should we have different code in there to do both? (I know why, but that's what your argument sounds like to me.)

Quoting Yasunori Goto, Yesterday at 2:33 pm,
Message-Id: <[email protected]>

He's NOT ADDRESSING FRAGMENTATION.

So unless you're talking about some OTHER patch, we're talking past each other again.

The feeling is mutual.

No, I'm going to point out that the author of the patch contradicts you.

I agree that this conversation is a waste of time, and will stop trying to reason with you now.

Rob

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I think what I'm optimizing is TLB flushes, not system calls. With mmap et al, they are effectively the same thing though.

Jeff

I don't think that freeing pages back to the host in free_pages is the way to go. The normal behavior for a Linux system, virtual or physical, is to use all the memory it has. So, any memory that's freed is pretty likely to be reused for something else, wasting any effort that's made to free pages back to the host.

The one counter-example I can think of is when a large process with a lot of data exits. Then its data pages will be freed and they may stay free for a while until the system finds other data to fill them with.

Also, it's not the virtual machine's job to know how to make the host perform optimally. It doesn't have the information to do it. It's perfectly OK for a UML to hang on to memory if the host has plenty free. So, it's the host's job to make sure that its memory pressure is reflected to the UMLs.

My current thinking is that you'll have a daemon on the host keeping track of memory pressure on the host and the UMLs, plugging and unplugging memory in order to keep the busy machines, including the host, supplied with memory, and periodically pushing down the memory of idle UMLs in order to force them to GC their page caches.

With Badari's patch and UML memory hotplug, the infrastructure is there to make this work. The one thing I'm puzzling over right now is how to measure memory pressure.

Jeff

Yep. This is the exactly the issue other product groups normally raise on Linux. How do we measure memory pressure in linux ? Some of our software products want to grow or shrink their memory usage depending on the memory pressure in the system. Since most memory is used for cache, "free" really doesn't indicate anything -they are monitoring info in /proc/meminfo and swapping rates to "guess" on the memory pressure. They want a clear way of finding out "how badly" system is under memory pressure. (As a starting point, they want to find out out of "cached" memory - how much is really easily "reclaimable" under memory pressure - without swapping). I know this is kind of crazy, but interesting to think about :)

Thanks,
Badari

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I think this is wrong. Applications shouldn't be measuring host memory pressure and trying to react to it.

This gives you no way to implement a global memory use policy - you can't say "App X is the most important thing on the system and must have all the memory it needs in order run as quickly as possible".

You can't establish any sort of priority between apps when it comes to memory use, or change those priorities.

And how does this work when the system can change the amount of memory that it has, such as when the app is inside a UML?

I think the right way to go is for willing apps to have an interface through which they can be told "change your memory consumption by +-X" and have a single daemon on the host tracking memory use and memory pressure, and shuffling memory between the apps.

This allows the admin to set memory use priorities between the apps and to exempt important ones from having memory pulled.

Measuring at the bottom and pushing memory pressure upwards also works naturally for virtual machines and the apps running inside them. The host will push memory pressure at the virtual machines, which in turn will push that pressure at their apps.

With UML, I have an interface where a daemon on the host can add or remove memory from an instance. I think the apps that are willing to adjust should implement something similar.

Jeff

If we do ever get prezeroing, we'd want a tuneable to say how much memory should be spent on random page cache and how much should be prezeroed. And large chunks of prezeroed memory lying around are what you'd think about handing back to the host OS...

Rob

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Similarly, that SGI patch which was rejected 6-12 months ago to kill off processes once they started swapping. We thought that it could be done from userspace, but we need a way for userspace to detect when a task is being swapped on a per-task basis.

I'm thinking a few numbers in the mm_struct, incremented in the pageout code, reported via /proc/stat.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I just sent in a proposed patch for this - one more per-cpuset number, tracking the recent rate of calls into the synchronous (direct) page reclaim by tasks in the cpuset.

See the message sent a few minutes ago, with subject:

[PATCH 5/5] cpuset: memory reclaim rate meter

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

uh, OK. If that patch is merged, does that make Bron happy, so I don't have to reply to his plaintive email?

I was kind of thinking that the stats should be per-process (actually per-mm) rather than bound to cpusets. /proc/<pid>/pageout-stats or something.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

In theory yes, that should do it. I will ack again, by early next week, after I have verified this further.

And it should also handle some other folks who have plaintive emails in my inbox, that haven't gotten bold enough to pester you, yet.

It really is, for the users who know my email address (*), job based memory pressure, not task based, that matters. Sticking it in a cpuset, which is the natural job container, is easier, more natural, and more efficient for all concerned.

It's jobs that are being run in cpusets with dedicated (not shared) CPUs and Memory Nodes that care about this, so far as I know.

When running a system in a more typical sharing mode, with multiple jobs and applications competing for the same resources, then the kernel needs to be master of processor scheduling and memory allocation.

When running jobs in cpusets with dedicated CPUs and Memory Nodes, then less is being asked of the kernel, and some per-job controls from userspace make more sense. This is where a simple hook like this reclaim rate meter comes into play - passing up to user space another clue to help it do its job.

There may well be a market for these too. But such stats sound like more work, and the market isn't one that's paying my salary.

So I will leave that challenge on the table for someone else.

(*) Of course, there is some self selection going on here.
Folks not doing cpuset-based jobs are far less likely to know my email address ;).

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

But I have to care for all users.

And I won't merge your patch ;)

Seriously, it does appear that doing it per-task is adequate for your needs, and it is certainly more general.

I cannot understand why you decided to count only the number of direct-reclaim events, via a "digitally filtered, constant time based, event frequency meter".

a) It loses information. If we were to export the number of pages reclaimed from the mm, filtering can be done in userspace.

b) It omits reclaim performed by kswapd and by other tasks (ok, it's very cpuset-specific).

c) It only counts synchronous try_to_free_pages() attempts. What if an attempt only freed pagecache, or didbn't manage to free anything?

d) It doesn't notice if kswapd is swapping the heck out of your not-allocating-any-memory-now process.

I think all the above can be addressed by exporting per-task (actually per-mm) reclaim info. (I haven't put much though into what info that should be - page reclaim attempts, mmapped reclaims, swapcache reclaims, etc)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Be that way ;).

My motivations for the per-cpuset, digitally filtered rate, as opposed to the per-task raw counter mostly have to do with minimizing total cost (user + kernel) of collecting this information. I have this phobia, perhaps not well founded, that moving critical scheduling/allocation decisions like this into user space will fail in some cases because the cost of gathering the critical information will be too intrusive on system performance and scalability.

A per-task stat requires walking the tasklist, to build a list of the tasks to query.

A raw counter requires repeated polling to determine the recent rate of activity.

The filtered per-cpuset rate avoids any need to repeatedly access global resources such as the tasklist, and minimizes the total cpu cycles required to get the interesting stat.

Well you should, and well you do.

If you have good reason, or just good instincts, to think that there are uses for per-task raw counters, then your choice is clear.

As indeed it was clear.

I don't recall hearing of any desire for per-task memory pressure data, until tonight.

I will miss this patch. It had provided exactly what I thought was needed, with an extremely small impact on system (kern+user) performance.

Oh well.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Nope, just task->mm->whatever.

True.

Well no. Because the filtered-whatsit takes two spinlocks and does a bunch of arith for each and every task, each time it calls try_to_free_pages(). The frequency of that could be very high indeed, even when nobody is interested in the metric which is being maintained(!).

And I'd suggest that only a minority of workloads would be interested in this metric?

ergo, polling the thing once per five seconds in those situations where we actually want to poll the thing may well be cheaper, in global terms?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Nope.

Agreed - once you have the task, then sure, that's enough.

However - a batch scheduler will end up having to figure out what tasks there are to inquire, by either listing the tasks in a cpuset, or by listing /proc. Either way, that's a tasklist scan. And it will have to do that pretty much every iteration of polling, since it has no a priori knowledge of what tasks a job is firing up.

Neither spinlock is global - the task and a lock in its cpuset.

I see a fair number of existing locks and semaphores, some global and some in loops, that look to be in the code invoked by try_to_free_pages(). And far more arithmetic than in that little filter.

Granted, its cost seen by all, for the benefit of few. But other sorts of per-task or per-mm stats are not going to be free either. I would have figured that doing something per-page, even the most trivial "counter++" (better have that mm locked) will likely cost more than doing something per try_to_free_pages() call.

When I have a task start allocating memory as fast it can, it is only able to call try_to_free_pages() about 10 times a second on an idle ia64 SN2 system, with a single thread, or about 20 times a second running several threads at once allocating memory.

That's not "very high" in my book.

What sort of load would hit this much more often?

If more folks need these detailed stats, then that's how it should be.

But I am no fan of exposing more than the minimum kernel vm details for use by production software.

We agree that my per-cpuset memory_reclaim_rate meter certainly hides more detail than the sorts of stats you are suggesting. I thought that was good, so long as what was needed was still present.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

But it's horribly specific to cpusets. If you want something multi-task, would be better if it worked by more generic task groupings.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I've been looking at similar things. When we page out / free something from a shared library that 10 tasks have mapped, who does that count against for pressure?

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Count pte unmappings and minor faults and account them against the mm_struct, I guess.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The particular people that I deal with care about constraining things on a per-cpuset basis, so that is the information that I personally am looking for. But it is simple enough to map tasks to cpusets and vice-versa, so this is not really a serious consideration. I would generically be in favor of the per-process stats (even though the application at hand is actually interested in the cpuset aggregate stats), because we can always produce an aggregate from the detailed, but not vice-versa. And no doubt some future as-yet-unimagined application will want per-process info.

--
Bron Campbell Nelson [email protected]
These statements are my own, not those of Silicon Graphics.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

wouldnt the clean solution here be a "swap ulimit"?

I.e. something like the 2-minute quick-hack below (against Linus-curr).

Ingo

---
implement a swap ulimit: RLIMIT_SWAP.

setting the ulimit to 0 causes any swapin activity to kill the task. Setting the rlimit to 0 is allowed for unprivileged users too, since it is a decrease of the default RLIM_INFINITY value. I.e. users could run known-memory-intense jobs with such an ulimit set, and get a guarantee that they wont put the system into a swap-storm.

Note: it's just swapin that causes the SIGKILL, because at swapout time it's hard to identify the originating task. Pure swapouts and a buildup in the swap-cache is not punished, only actual hard swapins. I didnt try too hard to make the rlimit particularly finegrained - i.e. right now we only know 'zero' and 'infinity' ...

 include/asm-generic/resource.h |    4 +++-
 mm/memory.c                    |   13 +++++++++++++
 2 files changed, 16 insertions(+), 1 deletion(-)

Index: linux/include/asm-generic/resource.h
===================================================================
@@ -44,8 +44,9 @@
 #define RLIMIT_NICE		13	/* max nice prio allowed to raise to
 					   0-39 for nice level 19 .. -20 */
 #define RLIMIT_RTPRIO		14	/* maximum realtime priority */
+#define RLIMIT_SWAP		15	/* maximum swapspace for task */
 
-#define RLIM_NLIMITS		15
+#define RLIM_NLIMITS		16
 
 /*
  * SuS says limits have to be unsigned.

@@ -86,6 +87,7 @@
 	[RLIMIT_MSGQUEUE]	= {   MQ_BYTES_MAX,   MQ_BYTES_MAX },	\
 	[RLIMIT_NICE]		= { 0, 0 },				\
 	[RLIMIT_RTPRIO]		= { 0, 0 },				\
+	[RLIMIT_SWAP]		= {  RLIM_INFINITY,  RLIM_INFINITY },	\
 }
 
 #endif	/* __KERNEL__ */

Index: linux/mm/memory.c
===================================================================
@@ -1647,6 +1647,18 @@ void swapin_readahead(swp_entry_t entry,
 }
 
 /*
+ * Crude first-approximation swapin-avoidance: if there is a zero swap
+ * rlimit then kill the task.
+ */
+static inline void check_swap_rlimit(void)
+{
+	unsigned long limit = current->signal->rlim[RLIMIT_SWAP].rlim_cur;
+
+	if (limit != RLIM_INFINITY)
+		force_sig(SIGKILL, current);
+}
+
+/*
  * We enter with non-exclusive mmap_sem (to exclude vma changes,
  * but allow concurrent faults), and pte mapped but not yet locked.
  * We return with mmap_sem still held, but pte unmapped and unlocked.

@@ -1667,6 +1679,7 @@ static int do_swap_page(struct mm_struct
 	entry = pte_to_swp_entry(orig_pte);
 	page = lookup_swap_cache(entry);
 	if (!page) {
+		check_swap_rlimit();
  		swapin_readahead(entry, address, vma);
  		page = read_swap_cache_async(entry, vma, address);
 		if (!page) {

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Well it's _a_ solution, but it's terribly specific.

How hard is it to read /proc/<pid>/nr_swapped_in_pages and if that's non-zero, kill <pid>?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

on a system with possibly thousands of taks, over /proc, on a high-performance node where for a 0.5% improvement they are willing to sacrifice maidens? :)

Seriously, while nr_swapped_in_pages ought to be OK, i think there is a generic problem with /proc based stats.

System instrumentation people are already complaining about how costly /proc parsing is. If you have to get some nontrivial stat from all threads in the system, and if Linux doesnt offer that counter or summary by default, it gets pretty expensive.

One solution i can think of would be to make a binary representation of /proc/<pid>/stats readonly-mmap-able. This would add a 4K page to every task tracked that way, and stats updates would have to update this page too - but it would make instrumentation of running apps really unintrusive and scalable.

Another addition would be some mechanism for a monitoring app to capture events in the PID space: so that they can mmap() new tasks [if they are interested] on a non-polling basis, i.e. not like readdir on /proc. This capability probably has to be a system-call though, as /proc seems too quirky for it. The system does not wait on the monitoring app(s) to catch up - if it's too slow in reacting and the event buffer overflows then tough luck - monitoring apps will have no impact on the runtime characteristics of other tasks. In theory this is somewhat similar to auditing, but the purpose would be quite different, and it only cares about PID-space events like 'fork/clone', 'exec' and 'exit'.

Ingo

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Agreed.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

That would be awesome - the current methods we have are mostly crap. There are some atomicity issues though. Plus when I suggested this 2 years ago, everyone told me to piss off, but I'm not bitter ;-) Seriously, we do need a fast communication mechanism.

M.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

well or do it the other way around

write a counter to such a thing
and kill when it hits zero
(similar to the CPU perf counter stuff on x86)

doing this from userspace is tricky; what if the task dies of natural causes and the pid gets reused, between the time the userspace app reads the value and the time it decides the time is up and time for a kill.... (and on a busy server that can be quite a bit of time)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>