)]}' { "log": [ { "commit": "391e43da797a96aeb65410281891f6d0b0e9611c", "tree": "0ce6784525a5a8f75b377170cf1a7d60abccea29", "parents": [ "029632fbb7b7c9d85063cc9eb470de6c54873df3" ], "author": { "name": "Peter Zijlstra", "email": "a.p.zijlstra@chello.nl", "time": "Tue Nov 15 17:14:39 2011 +0100" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Thu Nov 17 12:20:22 2011 +0100" }, "message": "sched: Move all scheduler bits into kernel/sched/\n\nThere\u0027s too many sched*.[ch] files in kernel/, give them their own\ndirectory.\n\n(No code changed, other than Makefile glue added.)\n\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "5710f15b52664ae0bfa60a66d75464769d297b2b", "tree": "3e5ab59e1dafbefe4f4ef6e809866be8ffd2d2e0", "parents": [ "d473750b4073f16f23f46f30dc1bd3de45c35754" ], "author": { "name": "Yong Zhang", "email": "yong.zhang0@gmail.com", "time": "Sat Aug 06 08:10:04 2011 +0800" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Sun Aug 14 12:01:11 2011 +0200" }, "message": "sched/cpupri: Remove cpupri-\u003epri_active\n\nSince [sched/cpupri: Remove the vec-\u003elock], member pri_active\nof struct cpupri is not needed any more, just remove it. Also\nclean stuff related to it.\n\nSigned-off-by: Yong Zhang \u003cyong.zhang0@gmail.com\u003e\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nLink: http://lkml.kernel.org/r/20110806001004.GA2207@zhy\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "c92211d9b772792a9dea530c042efb4ab5562f50", "tree": "d4ef2f4aa2e2c0d991a4dbc74a14e305caf46cee", "parents": [ "5181f4a46afd99e5e85c639b189e43e0a42b53df" ], "author": { "name": "Steven Rostedt", "email": "rostedt@goodmis.org", "time": "Tue Aug 02 16:36:12 2011 -0400" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Sun Aug 14 12:01:03 2011 +0200" }, "message": "sched/cpupri: Remove the vec-\u003elock\n\nsched/cpupri: Remove the vec-\u003elock\n\nThe cpupri vec-\u003elock has been showing up as a top contention\nlately. This is because of the RT push/pull logic takes an\nagressive approach for migrating RT tasks. The cpupri logic is\nin place to improve the performance of the push/pull when dealing\nwith large number CPU machines.\n\nThe problem though is a vec-\u003elock is required, where a vec is a\nglobal per RT priority structure. That is, if there are lots of\nRT tasks at the same priority, every time they are added or removed\nfrom the RT queue, this global vec-\u003elock is taken. Now that more\nkernel threads are becoming RT (RCU boost and threaded interrupts)\nthis is becoming much more of an issue.\n\nThere are two variables that are being synced by the vec-\u003elock.\nThe cpupri bitmask, and the vec-\u003ecounter. The cpupri bitmask\nis one bit per priority. If a RT priority vec has a process queued,\nthen the vec-\u003ecount is \u003e 0 and the cpupri bitmask is set for that\nRT priority.\n\nIf the cpupri bitmask gets out of sync with the vec-\u003ecounter, we could\nend up pushing a low proirity RT task to a high priority queue.\nThat RT task that could have run immediately could be queued on a\nrun queue with a higher priority task indefinitely.\n\nThe solution is not to use the cpupri bitmask and just look at the\nvec-\u003ecount directly when doing a pull. The cpupri bitmask is just\na fast way to scan the RT priorities when a pull is made. Instead\nof using the bitmask, and just examine all RT priorities, and\nlook at the vec-\u003ecounts, we could eliminate the vec-\u003elock. The\nscan of RT tasks is to find a run queue that we can push an RT task\nto, and we do not push to a high priority queue, thus the scan only\nneeds to go from 1 to RT task-\u003eprio, and not all 100 RT priorities.\n\nThe push algorithm, which does the scan of RT priorities (and\nscan of the bitmask) only happens when we have an overloaded RT run\nqueue (more than one RT task queued). The grabbing of the vec-\u003elock\nhappens every time any RT task is queued or dequeued on the run\nqueue for that priority. The slowing down of the scan by not using\na bitmask is negligible by the speed up of removing the vec-\u003elock\ncontention, and replacing it with an atomic counter and memory barrier.\n\nTo prove this, I wrote a patch that times both the loop and the code\nthat grabs the vec-\u003elocks. I passed the patches to various people\n(and companies) to test and show the results. I let everyone choose\ntheir own load to test, giving different loads on the system,\nfor various different setups.\n\nHere\u0027s some of the results: (snipping to a few CPUs to not make\nthis change log huge, but the results were consistent across\nthe entire system).\n\nSystem 1 (24 CPUs)\n\nBefore patch:\nCPU: Name Count Max Min Average Total\n---- ---- ----- --- --- ------- -----\n[...]\ncpu 20: loop 3057 1.766 0.061 0.642 1963.170\n vec 6782949 90.469 0.089 0.414 2811760.503\ncpu 21: loop 2617 1.723 0.062 0.641 1679.074\n vec 6782810 90.499 0.089 0.291 1978499.900\ncpu 22: loop 2212 1.863 0.063 0.699 1547.160\n vec 6767244 85.685 0.089 0.435 2949676.898\ncpu 23: loop 2320 2.013 0.062 0.594 1380.265\n vec 6781694 87.923 0.088 0.431 2928538.224\n\nAfter patch:\ncpu 20: loop 2078 1.579 0.061 0.533 1108.006\n vec 6164555 5.704 0.060 0.143 885185.809\ncpu 21: loop 2268 1.712 0.065 0.575 1305.248\n vec 6153376 5.558 0.060 0.187 1154960.469\ncpu 22: loop 1542 1.639 0.095 0.533 823.249\n vec 6156510 5.720 0.060 0.190 1172727.232\ncpu 23: loop 1650 1.733 0.068 0.545 900.781\n vec 6170784 5.533 0.060 0.167 1034287.953\n\nAll times are in microseconds. The \u0027loop\u0027 is the amount of time spent\ndoing the loop across the priorities (before patch uses bitmask).\nthe \u0027vec\u0027 is the amount of time in the code that requires grabbing\nthe vec-\u003elock. The second patch just does not have the vec lock, but\nencompasses the same code.\n\nAmazingly the loop code even went down on average. The vec code went\nfrom .5 down to .18, that\u0027s more than half the time spent!\n\nNote, more than one test was run, but they all had the same results.\n\nSystem 2 (64 CPUs)\n\nBefore patch:\nCPU: Name Count Max Min Average Total\n---- ---- ----- --- --- ------- -----\ncpu 60: loop 0 0 0 0 0\n vec 5410840 277.954 0.084 0.782 4232895.727\ncpu 61: loop 0 0 0 0 0\n vec 4915648 188.399 0.084 0.570 2803220.301\ncpu 62: loop 0 0 0 0 0\n vec 5356076 276.417 0.085 0.786 4214544.548\ncpu 63: loop 0 0 0 0 0\n vec 4891837 170.531 0.085 0.799 3910948.833\n\nAfter patch:\ncpu 60: loop 0 0 0 0 0\n vec 5365118 5.080 0.021 0.063 340490.267\ncpu 61: loop 0 0 0 0 0\n vec 4898590 1.757 0.019 0.071 347903.615\ncpu 62: loop 0 0 0 0 0\n vec 5737130 3.067 0.021 0.119 687108.734\ncpu 63: loop 0 0 0 0 0\n vec 4903228 1.822 0.021 0.071 348506.477\n\nThe test run during the measurement did not have any (very few,\nfrom other CPUs) RT tasks pushing. But this shows that it helped\nout tremendously with the contention, as the contention happens\nbecause the vec-\u003elock is taken only on queuing at an RT priority,\nand different CPUs that queue tasks at the same priority will\nhave contention.\n\nI tested on my own 4 CPU machine with the following results:\n\nBefore patch:\nCPU: Name Count Max Min Average Total\n---- ---- ----- --- --- ------- -----\ncpu 0: loop 2377 1.489 0.158 0.588 1398.395\n vec 4484 770.146 2.301 4.396 19711.755\ncpu 1: loop 2169 1.962 0.160 0.576 1250.110\n vec 4425 152.769 2.297 4.030 17834.228\ncpu 2: loop 2324 1.749 0.155 0.559 1299.799\n vec 4368 779.632 2.325 4.665 20379.268\ncpu 3: loop 2325 1.629 0.157 0.561 1306.113\n vec 4650 408.782 2.394 4.348 20222.577\n\nAfter patch:\nCPU: Name Count Max Min Average Total\n---- ---- ----- --- --- ------- -----\ncpu 0: loop 2121 1.616 0.113 0.636 1349.189\n vec 4303 1.151 0.225 0.421 1811.966\ncpu 1: loop 2130 1.638 0.178 0.644 1372.927\n vec 4627 1.379 0.235 0.428 1983.648\ncpu 2: loop 2056 1.464 0.165 0.637 1310.141\n vec 4471 1.311 0.217 0.433 1937.927\ncpu 3: loop 2154 1.481 0.162 0.601 1295.083\n vec 4236 1.253 0.230 0.425 1803.008\n\nThis was running my migrate.c code that can be found at:\nhttp://lwn.net/Articles/425763/\n\nThe migrate code does stress the RT tasks a bit. This shows that\nthe loop did increase a little after the patch, but not by much.\nThe vec code dropped dramatically. From 4.3us down to .42us.\nThat\u0027s a 10x improvement!\n\nTested-by: Mike Galbraith \u003cmgalbraith@suse.de\u003e\nTested-by: Luis Claudio R. Gonçalves \u003clgoncalv@redhat.com\u003e\nTested-by: Matthew Hank Sabins\u003cmsabins@linux.vnet.ibm.com\u003e\nSigned-off-by: Steven Rostedt \u003crostedt@goodmis.org\u003e\nReviewed-by: Gregory Haskins \u003cgregory.haskins@gmail.com\u003e\nAcked-by: Hillf Danton \u003cdhillf@gmail.com\u003e\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Chris Mason \u003cchris.mason@oracle.com\u003e\nLink: http://lkml.kernel.org/r/1312317372.18583.101.camel@gandalf.stny.rr.com\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "68c38fc3cb4e5a60f502ee9c45f3dfe70e5165ad", "tree": "32293b2fd969c57032407294863c1f2ee6bf5996", "parents": [ "bbc8cb5baead9607309583b20873ab0cc8d89eaf" ], "author": { "name": "Pekka Enberg", "email": "penberg@cs.helsinki.fi", "time": "Thu Jul 15 23:18:22 2010 +0300" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Sat Jul 17 12:06:22 2010 +0200" }, "message": "sched: No need for bootmem special cases\n\nAs of commit dcce284 (\"mm: Extend gfp masking to the page\nallocator\") and commit 7e85ee0 (\"slab,slub: don\u0027t enable\ninterrupts during early boot\"), the slab allocator makes\nsure we don\u0027t attempt to sleep during boot.\n\nTherefore, remove bootmem special cases from the scheduler\nand use plain GFP_KERNEL instead.\n\nSigned-off-by: Pekka Enberg \u003cpenberg@cs.helsinki.fi\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nLKML-Reference: \u003c1279225102-2572-1-git-send-email-penberg@cs.helsinki.fi\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "fe841226bd954fba4fd79f037a876053fe9c3217", "tree": "0819ff8a78b9eeed61a1dc26b5aa900f48d0c2e3", "parents": [ "0986b11b12ad2baed338385f79fd0dec58a23fc6" ], "author": { "name": "Thomas Gleixner", "email": "tglx@linutronix.de", "time": "Tue Nov 17 17:59:15 2009 +0100" }, "committer": { "name": "Thomas Gleixner", "email": "tglx@linutronix.de", "time": "Mon Dec 14 23:55:33 2009 +0100" }, "message": "sched: Convert cpupri lock to raw_spinlock\n\nConvert locks which cannot be sleeping locks in preempt-rt to\nraw_spinlocks.\n\nSigned-off-by: Thomas Gleixner \u003ctglx@linutronix.de\u003e\nAcked-by: Peter Zijlstra \u003cpeterz@infradead.org\u003e\nAcked-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "612a726faf8486fa48b34fa37115ce1e7421d383", "tree": "3448dd7e8129218401eac69b24a6116b06437b4f", "parents": [ "73d0a4b107d58908305f272bfae9bd17f74a2c81" ], "author": { "name": "Rusty Russell", "email": "rusty@rustcorp.com.au", "time": "Mon Mar 30 22:05:16 2009 -0600" }, "committer": { "name": "Rusty Russell", "email": "rusty@rustcorp.com.au", "time": "Mon Mar 30 22:05:17 2009 +1030" }, "message": "cpumask: remove cpumask_t from core\n\nImpact: cleanup\n\nstruct cpumask is nicer, and we use it to make where we\u0027ve made code\nsafe for CONFIG_CPUMASK_OFFSTACK\u003dy.\n\nSigned-off-by: Rusty Russell \u003crusty@rustcorp.com.au\u003e\n" }, { "commit": "68e74568fbe5854952355e942acca51f138096d9", "tree": "6263627b3b3c7e249f685ba0fe4d76002e882cd0", "parents": [ "4212823fb459eacc8098dd420bb68ebb9917989d" ], "author": { "name": "Rusty Russell", "email": "rusty@rustcorp.com.au", "time": "Tue Nov 25 02:35:13 2008 +1030" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Mon Nov 24 17:52:22 2008 +0100" }, "message": "sched: convert struct cpupri_vec cpumask_var_t.\n\nImpact: stack usage reduction, (future) size reduction for large NR_CPUS.\n\nDynamically allocating cpumasks (when CONFIG_CPUMASK_OFFSTACK) saves\nspace for small nr_cpu_ids but big CONFIG_NR_CPUS.\n\nThe fact cpupro_init is called both before and after the slab is\navailable makes for an ugly parameter unfortunately.\n\nWe also use cpumask_any_and to get rid of a temporary in cpupri_find.\n\nSigned-off-by: Rusty Russell \u003crusty@rustcorp.com.au\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "e539d8fcd11af811db70707d47ea436d5621d0da", "tree": "9bf41406ee7b635abf5a6769acd6a93cbd4df104", "parents": [ "709d4b0c60f990bccf3e10ba7c6da407ad65c97f" ], "author": { "name": "Thomas Gleixner", "email": "tglx@linutronix.de", "time": "Thu Jun 05 10:28:00 2008 +0200" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Fri Jun 06 15:19:44 2008 +0200" }, "message": "sched: fix the cpuprio count really\n\nPeter pointed out that the last version of the \"fix\" was still one off\nunder certain circumstances. Use BITS_TO_LONG instead to get an\naccurate result.\n\nSigned-off-by: Thomas Gleixner \u003ctglx@linutronix.de\u003e\n" }, { "commit": "709d4b0c60f990bccf3e10ba7c6da407ad65c97f", "tree": "1d8c931a068f0957d52dc5cae75c7013138caa50", "parents": [ "1f11eb6a8bc92536d9e93ead48fa3ffbd1478571" ], "author": { "name": "Gregory Haskins", "email": "ghaskins@novell.com", "time": "Wed Jun 04 15:04:10 2008 -0400" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Fri Jun 06 15:19:43 2008 +0200" }, "message": "sched: fix cpupri priocount\n\nA rounding error was pointed out by Peter Zijlstra which would result\nin the structure holding priorities to be off by one.\n\nSigned-off-by: Gregory Haskins \u003cghaskins@novell.com\u003e\nCc: Peter Zijlstra \u003cpeterz@infradead.org\u003e\nCc: Steven Rostedt \u003crostedt@goodmis.org\u003e\nCc: Arnaldo Carvalho de Melo \u003cacme@redhat.com\u003e\nSigned-off-by: Thomas Gleixner \u003ctglx@linutronix.de\u003e\n" }, { "commit": "6e0534f278199f1e3dd1049b9bc19a7a5b87ada1", "tree": "25f4da14ec32927742db9f599ac779b4e83d1763", "parents": [ "f333fdc9098b71e2687e4e9b6349fcb352960d66" ], "author": { "name": "Gregory Haskins", "email": "ghaskins@novell.com", "time": "Mon May 12 21:21:01 2008 +0200" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Fri Jun 06 15:19:28 2008 +0200" }, "message": "sched: use a 2-d bitmap for searching lowest-pri CPU\n\nThe current code use a linear algorithm which causes scaling issues\non larger SMP machines. This patch replaces that algorithm with a\n2-dimensional bitmap to reduce latencies in the wake-up path.\n\nSigned-off-by: Gregory Haskins \u003cghaskins@novell.com\u003e\nAcked-by: Steven Rostedt \u003csrostedt@redhat.com\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\nSigned-off-by: Thomas Gleixner \u003ctglx@linutronix.de\u003e\n" } ] }