)]}' { "commit": "db64fe02258f1507e13fe5212a989922323685ce", "tree": "ed24c8d4e3b0bcadfce3a8c3916a6b35d6c891cb", "parents": [ "cb8f488c33539f096580e202f5438a809195008f" ], "author": { "name": "Nick Piggin", "email": "npiggin@suse.de", "time": "Sat Oct 18 20:27:03 2008 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Mon Oct 20 08:52:32 2008 -0700" }, "message": "mm: rewrite vmap layer\n\nRewrite the vmap allocator to use rbtrees and lazy tlb flushing, and\nprovide a fast, scalable percpu frontend for small vmaps (requires a\nslightly different API, though).\n\nThe biggest problem with vmap is actually vunmap. Presently this requires\na global kernel TLB flush, which on most architectures is a broadcast IPI\nto all CPUs to flush the cache. This is all done under a global lock. As\nthe number of CPUs increases, so will the number of vunmaps a scaled\nworkload will want to perform, and so will the cost of a global TLB flush.\n This gives terrible quadratic scalability characteristics.\n\nAnother problem is that the entire vmap subsystem works under a single\nlock. It is a rwlock, but it is actually taken for write in all the fast\npaths, and the read locking would likely never be run concurrently anyway,\nso it\u0027s just pointless.\n\nThis is a rewrite of vmap subsystem to solve those problems. The existing\nvmalloc API is implemented on top of the rewritten subsystem.\n\nThe TLB flushing problem is solved by using lazy TLB unmapping. vmap\naddresses do not have to be flushed immediately when they are vunmapped,\nbecause the kernel will not reuse them again (would be a use-after-free)\nuntil they are reallocated. So the addresses aren\u0027t allocated again until\na subsequent TLB flush. A single TLB flush then can flush multiple\nvunmaps from each CPU.\n\nXEN and PAT and such do not like deferred TLB flushing because they can\u0027t\nalways handle multiple aliasing virtual addresses to a physical address.\nThey now call vm_unmap_aliases() in order to flush any deferred mappings.\nThat call is very expensive (well, actually not a lot more expensive than\na single vunmap under the old scheme), however it should be OK if not\ncalled too often.\n\nThe virtual memory extent information is stored in an rbtree rather than a\nlinked list to improve the algorithmic scalability.\n\nThere is a per-CPU allocator for small vmaps, which amortizes or avoids\nglobal locking.\n\nTo use the per-CPU interface, the vm_map_ram / vm_unmap_ram interfaces\nmust be used in place of vmap and vunmap. Vmalloc does not use these\ninterfaces at the moment, so it will not be quite so scalable (although it\nwill use lazy TLB flushing).\n\nAs a quick test of performance, I ran a test that loops in the kernel,\nlinearly mapping then touching then unmapping 4 pages. Different numbers\nof tests were run in parallel on an 4 core, 2 socket opteron. Results are\nin nanoseconds per map+touch+unmap.\n\nthreads vanilla vmap rewrite\n1 14700 2900\n2 33600 3000\n4 49500 2800\n8 70631 2900\n\nSo with a 8 cores, the rewritten version is already 25x faster.\n\nIn a slightly more realistic test (although with an older and less\nscalable version of the patch), I ripped the not-very-good vunmap batching\ncode out of XFS, and implemented the large buffer mapping with vm_map_ram\nand vm_unmap_ram... along with a couple of other tricks, I was able to\nspeed up a large directory workload by 20x on a 64 CPU system. I believe\nvmap/vunmap is actually sped up a lot more than 20x on such a system, but\nI\u0027m running into other locks now. vmap is pretty well blown off the\nprofiles.\n\nBefore:\n1352059 total 0.1401\n798784 _write_lock 8320.6667 \u003c- vmlist_lock\n529313 default_idle 1181.5022\n 15242 smp_call_function 15.8771 \u003c- vmap tlb flushing\n 2472 __get_vm_area_node 1.9312 \u003c- vmap\n 1762 remove_vm_area 4.5885 \u003c- vunmap\n 316 map_vm_area 0.2297 \u003c- vmap\n 312 kfree 0.1950\n 300 _spin_lock 3.1250\n 252 sn_send_IPI_phys 0.4375 \u003c- tlb flushing\n 238 vmap 0.8264 \u003c- vmap\n 216 find_lock_page 0.5192\n 196 find_next_bit 0.3603\n 136 sn2_send_IPI 0.2024\n 130 pio_phys_write_mmr 2.0312\n 118 unmap_kernel_range 0.1229\n\nAfter:\n 78406 total 0.0081\n 40053 default_idle 89.4040\n 33576 ia64_spinlock_contention 349.7500\n 1650 _spin_lock 17.1875\n 319 __reg_op 0.5538\n 281 _atomic_dec_and_lock 1.0977\n 153 mutex_unlock 1.5938\n 123 iget_locked 0.1671\n 117 xfs_dir_lookup 0.1662\n 117 dput 0.1406\n 114 xfs_iget_core 0.0268\n 92 xfs_da_hashname 0.1917\n 75 d_alloc 0.0670\n 68 vmap_page_range 0.0462 \u003c- vmap\n 58 kmem_cache_alloc 0.0604\n 57 memset 0.0540\n 52 rb_next 0.1625\n 50 __copy_user 0.0208\n 49 bitmap_find_free_region 0.2188 \u003c- vmap\n 46 ia64_sn_udelay 0.1106\n 45 find_inode_fast 0.1406\n 42 memcmp 0.2188\n 42 finish_task_switch 0.1094\n 42 __d_lookup 0.0410\n 40 radix_tree_lookup_slot 0.1250\n 37 _spin_unlock_irqrestore 0.3854\n 36 xfs_bmapi 0.0050\n 36 kmem_cache_free 0.0256\n 35 xfs_vn_getattr 0.0322\n 34 radix_tree_lookup 0.1062\n 33 __link_path_walk 0.0035\n 31 xfs_da_do_buf 0.0091\n 30 _xfs_buf_find 0.0204\n 28 find_get_page 0.0875\n 27 xfs_iread 0.0241\n 27 __strncpy_from_user 0.2812\n 26 _xfs_buf_initialize 0.0406\n 24 _xfs_buf_lookup_pages 0.0179\n 24 vunmap_page_range 0.0250 \u003c- vunmap\n 23 find_lock_page 0.0799\n 22 vm_map_ram 0.0087 \u003c- vmap\n 20 kfree 0.0125\n 19 put_page 0.0330\n 18 __kmalloc 0.0176\n 17 xfs_da_node_lookup_int 0.0086\n 17 _read_lock 0.0885\n 17 page_waitqueue 0.0664\n\nvmap has gone from being the top 5 on the profiles and flushing the crap\nout of all TLBs, to using less than 1% of kernel time.\n\n[akpm@linux-foundation.org: cleanups, section fix]\n[akpm@linux-foundation.org: fix build on alpha]\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nCc: Jeremy Fitzhardinge \u003cjeremy@goop.org\u003e\nCc: Krzysztof Helt \u003ckrzysztof.h1@poczta.fm\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "a9ec89c3fbca32c3fda0e65d8da8846c8f96ed2a", "old_mode": 33188, "old_path": "arch/x86/mm/pageattr.c", "new_id": "407d8784f669603fd48667c8d2ee22bb8e870f35", "new_mode": 33188, "new_path": "arch/x86/mm/pageattr.c" }, { "type": "modify", "old_id": "0013a729b41ddc93045510068da9bcbbadf76433", "old_mode": 33188, "old_path": "arch/x86/xen/enlighten.c", "new_id": "b61534c7a4c4d5894812c5bb97a89f29a0f72338", "new_mode": 33188, "new_path": "arch/x86/xen/enlighten.c" }, { "type": "modify", "old_id": "ae173f6edd8ba044f5cc5372193ea7ce0af2e299", "old_mode": 33188, "old_path": "arch/x86/xen/mmu.c", "new_id": "d4d52f5a1cf7bae392801e19367030ebe58ccf79", "new_mode": 33188, "new_path": "arch/x86/xen/mmu.c" }, { "type": "modify", "old_id": "328eb40227277967c8a6179efb56ad14e03fc233", "old_mode": 33188, "old_path": "include/linux/vmalloc.h", "new_id": "4c28c4d564e2da1e5e6112e0e5081d4f08ebd942", "new_mode": 33188, "new_path": "include/linux/vmalloc.h" }, { "type": "modify", "old_id": "27f6bf6108e96908b10df5b20e0011aaebb3266c", "old_mode": 33188, "old_path": "init/main.c", "new_id": "4371d11721f618f45ccfc65b799fbbdfebbf8140", "new_mode": 33188, "new_path": "init/main.c" }, { "type": "modify", "old_id": "bba06c41fc59ed10be118f7af24ecfa71d023c33", "old_mode": 33188, "old_path": "mm/vmalloc.c", "new_id": "712ae47af0bf5f23a4b32ea0497dd2f6e8272085", "new_mode": 33188, "new_path": "mm/vmalloc.c" } ] }