1. 02 Mar, 2016 1 commit
    • Frederic Weisbecker's avatar
      posix-cpu-timers: Migrate to use new tick dependency mask model · b7878300
      Frederic Weisbecker authored
      Instead of providing asynchronous checks for the nohz subsystem to verify
      posix cpu timers tick dependency, migrate the latter to the new mask.
      
      In order to keep track of the running timers and expose the tick
      dependency accordingly, we must probe the timers queuing and dequeuing
      on threads and process lists.
      
      Unfortunately it implies both task and signal level dependencies. We
      should be able to further optimize this and merge all that on the task
      level dependency, at the cost of a bit of complexity and may be overhead.
      Reviewed-by: default avatarChris Metcalf <cmetcalf@ezchip.com>
      Cc: Christoph Lameter <cl@linux.com>
      Cc: Chris Metcalf <cmetcalf@ezchip.com>
      Cc: Ingo Molnar <mingo@kernel.org>
      Cc: Luiz Capitulino <lcapitulino@redhat.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Viresh Kumar <viresh.kumar@linaro.org>
      Signed-off-by: default avatarFrederic Weisbecker <fweisbec@gmail.com>
      b7878300
  2. 03 Jul, 2013 1 commit
    • Frederic Weisbecker's avatar
      posix_cpu_timer: consolidate expiry time type · 55ccb616
      Frederic Weisbecker authored
      The posix cpu timer expiry time is stored in a union of two types: a 64
      bits field if we rely on scheduler precise accounting, or a cputime_t if
      we rely on jiffies.
      
      This results in quite some duplicate code and special cases to handle the
      two types.
      
      Just unify this into a single 64 bits field.  cputime_t can always fit
      into it.
      Signed-off-by: default avatarFrederic Weisbecker <fweisbec@gmail.com>
      Cc: Stanislaw Gruszka <sgruszka@redhat.com>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Ingo Molnar <mingo@elte.hu>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: KOSAKI Motohiro <kosaki.motohiro@gmail.com>
      Cc: Olivier Langlois <olivier@trillion01.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      55ccb616
  3. 19 Apr, 2013 1 commit
    • Frederic Weisbecker's avatar
      posix_timers: New API to prevent from stopping the tick when timers are running · 555347f6
      Frederic Weisbecker authored
      Bring a new helper that the full dynticks infrastructure can
      call in order to know if it can safely stop the tick from
      the posix cpu timers subsystem point of view.
      Signed-off-by: default avatarFrederic Weisbecker <fweisbec@gmail.com>
      Cc: Chris Metcalf <cmetcalf@tilera.com>
      Cc: Christoph Lameter <cl@linux.com>
      Cc: Geoff Levand <geoff@infradead.org>
      Cc: Gilad Ben Yossef <gilad@benyossef.com>
      Cc: Hakan Akkan <hakanakkan@gmail.com>
      Cc: Ingo Molnar <mingo@kernel.org>
      Cc: Kevin Hilman <khilman@linaro.org>
      Cc: Li Zhong <zhong@linux.vnet.ibm.com>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
      Cc: Paul Gortmaker <paul.gortmaker@windriver.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Steven Rostedt <rostedt@goodmis.org>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      555347f6
  4. 17 Apr, 2013 1 commit
    • Pavel Emelyanov's avatar
      posix timers: Allocate timer id per process (v2) · 5ed67f05
      Pavel Emelyanov authored
      Currently kernel generates IDs for posix timers in a global manner --
      there's a kernel-wide IDR tree from which IDs are created. This makes
      it impossible to recreate a timer with a desired ID (in particular
      this is done by the CRIU checkpoint-restore project) -- since these
      IDs are global it may happen, that at the time we recreate a timer, the
      ID we want for it is already busy by some other timer.
      
      In order to address this, replace the IDR tree with a global hash
      table for timers and makes timer IDs unique per signal_struct (to
      which timers are linked anyway). With this, two timers belonging to
      different processes may have equal IDs and we can recreate either of
      them with the ID we want.
      Signed-off-by: default avatarPavel Emelyanov <xemul@parallels.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Michael Kerrisk <mtk.manpages@gmail.com>
      Cc: Matthew Helsley <matt.helsley@gmail.com>
      Link: http://lkml.kernel.org/r/513D9FF5.9010004@parallels.comSigned-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
      5ed67f05
  5. 10 Aug, 2011 1 commit
  6. 24 May, 2011 1 commit
    • Eric Dumazet's avatar
      posix-timers: RCU conversion · 8af08871
      Eric Dumazet authored
      Ben Nagy reported a scalability problem with KVM/QEMU that hit very hard
      a single spinlock (idr_lock) in posix-timers code, on its 48 core
      machine.
      
      Even on a 16 cpu machine (2x4x2), a single test can show 98% of cpu time
      used in ticket_spin_lock, from lock_timer
      
      Ref: http://www.spinics.net/lists/kvm/msg51526.html
      
      Switching to RCU is quite easy, IDR being already RCU ready. idr_lock
      should be locked only for an insert/delete, not a lookup.
      
      Benchmark on a 2x4x2 machine, 16 processes calling timer_gettime().
      
      Before :
      
      real    1m18.669s
      user    0m1.346s
      sys     1m17.180s
      
      After :
      
      real    0m3.296s
      user    0m1.366s
      sys     0m1.926s
      Reported-by: default avatarBen Nagy <ben@iagu.net>
      Signed-off-by: default avatarEric Dumazet <eric.dumazet@gmail.com>
      Tested-by: default avatarBen Nagy <ben@iagu.net>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: Avi Kivity <avi@redhat.com>
      Cc: John Stultz <johnstul@us.ibm.com>
      Cc: Richard Cochran <richard.cochran@omicron.at>
      Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
      8af08871
  7. 26 Apr, 2011 1 commit
    • John Stultz's avatar
      timers: Posix interface for alarm-timers · 9a7adcf5
      John Stultz authored
      This patch exposes alarm-timers to userland via the posix clock
      and timers interface, using two new clockids: CLOCK_REALTIME_ALARM
      and CLOCK_BOOTTIME_ALARM. Both clockids behave identically to
      CLOCK_REALTIME and CLOCK_BOOTTIME, respectively, but timers
      set against the _ALARM suffixed clockids will wake the system if
      it is suspended.
      
      Some background can be found here:
      	https://lwn.net/Articles/429925/
      
      The concept for Alarm-timers was inspired by the Android Alarm
      driver (by Arve Hjønnevåg) found in the Android kernel tree.
      
      See: http://android.git.kernel.org/?p=kernel/common.git;a=blob;f=drivers/rtc/alarm.c;h=1250edfbdf3302f5e4ea6194847c6ef4bb7beb1c;hb=android-2.6.36
      
      While the in-kernel interface is pretty similar between
      alarm-timers and Android alarm driver, the user-space interface
      for the Android alarm driver is via ioctls to a new char device.
      As mentioned above, I've instead chosen to export this functionality
      via the posix interface, as it seemed a little simpler and avoids
      creating duplicate interfaces to things like CLOCK_REALTIME and
      CLOCK_MONOTONIC under alternate names (ie:ANDROID_ALARM_RTC and
      ANDROID_ALARM_SYSTEMTIME).
      
      The semantics of the Android alarm driver are different from what
      this posix interface provides. For instance, threads other then
      the thread waiting on the Android alarm driver are able to modify
      the alarm being waited on. Also this interface does not allow
      the same wakelock semantics that the Android driver provides
      (ie: kernel takes a wakelock on RTC alarm-interupt, and holds it
      through process wakeup, and while the process runs, until the
      process either closes the char device or calls back in to wait
      on a new alarm).
      
      One potential way to implement similar semantics may be via
      the timerfd infrastructure, but this needs more research.
      
      There may also need to be some sort of sysfs system level policy
      hooks that allow alarm timers to be disabled to keep them
      from firing at inappropriate times (ie: laptop in a well insulated
      bag, mid-flight).
      
      CC: Arve Hjønnevåg <arve@android.com>
      CC: Thomas Gleixner <tglx@linutronix.de>
      CC: Alessandro Zummo <a.zummo@towertech.it>
      Acked-by: default avatarArnd Bergmann <arnd@arndb.de>
      Signed-off-by: default avatarJohn Stultz <john.stultz@linaro.org>
      9a7adcf5
  8. 02 Feb, 2011 10 commits
  9. 16 Jul, 2010 1 commit
  10. 12 Dec, 2008 1 commit
    • Oleg Nesterov's avatar
      posix-timers: use "struct pid*" instead of "struct task_struct*" · 27af4245
      Oleg Nesterov authored
      Impact: restructure, clean up code
      
      k_itimer holds the ref to the ->it_process until sys_timer_delete(). This
      allows to pin up to RLIMIT_SIGPENDING dead task_struct's. Change the code
      to use "struct pid *" instead.
      
      The patch doesn't kill ->it_process, it places ->it_pid into the union.
      ->it_process is still used by do_cpu_nanosleep() as before. It would be
      trivial to change the nanosleep code as well, but since it uses it_process
      in a special way I think it is better to keep this field for grep.
      
      The patch bloats the kernel by 104 bytes and it also adds the new pointer,
      ->it_signal, to k_itimer. It is used by lock_timer() to verify that the
      found timer was not created by another process. It is not clear why do we
      use the global database (and thus the global idr_lock) for posix timers.
      We still need the signal_struct->posix_timers which contains all useable
      timers, perhaps it is better to use some form of per-process array
      instead.
      Signed-off-by: default avatarOleg Nesterov <oleg@tv-sign.ru>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
      27af4245
  11. 24 Sep, 2008 1 commit
  12. 14 Sep, 2008 1 commit
    • Frank Mayhar's avatar
      timers: fix itimer/many thread hang · f06febc9
      Frank Mayhar authored
      Overview
      
      This patch reworks the handling of POSIX CPU timers, including the
      ITIMER_PROF, ITIMER_VIRT timers and rlimit handling.  It was put together
      with the help of Roland McGrath, the owner and original writer of this code.
      
      The problem we ran into, and the reason for this rework, has to do with using
      a profiling timer in a process with a large number of threads.  It appears
      that the performance of the old implementation of run_posix_cpu_timers() was
      at least O(n*3) (where "n" is the number of threads in a process) or worse.
      Everything is fine with an increasing number of threads until the time taken
      for that routine to run becomes the same as or greater than the tick time, at
      which point things degrade rather quickly.
      
      This patch fixes bug 9906, "Weird hang with NPTL and SIGPROF."
      
      Code Changes
      
      This rework corrects the implementation of run_posix_cpu_timers() to make it
      run in constant time for a particular machine.  (Performance may vary between
      one machine and another depending upon whether the kernel is built as single-
      or multiprocessor and, in the latter case, depending upon the number of
      running processors.)  To do this, at each tick we now update fields in
      signal_struct as well as task_struct.  The run_posix_cpu_timers() function
      uses those fields to make its decisions.
      
      We define a new structure, "task_cputime," to contain user, system and
      scheduler times and use these in appropriate places:
      
      struct task_cputime {
      	cputime_t utime;
      	cputime_t stime;
      	unsigned long long sum_exec_runtime;
      };
      
      This is included in the structure "thread_group_cputime," which is a new
      substructure of signal_struct and which varies for uniprocessor versus
      multiprocessor kernels.  For uniprocessor kernels, it uses "task_cputime" as
      a simple substructure, while for multiprocessor kernels it is a pointer:
      
      struct thread_group_cputime {
      	struct task_cputime totals;
      };
      
      struct thread_group_cputime {
      	struct task_cputime *totals;
      };
      
      We also add a new task_cputime substructure directly to signal_struct, to
      cache the earliest expiration of process-wide timers, and task_cputime also
      replaces the it_*_expires fields of task_struct (used for earliest expiration
      of thread timers).  The "thread_group_cputime" structure contains process-wide
      timers that are updated via account_user_time() and friends.  In the non-SMP
      case the structure is a simple aggregator; unfortunately in the SMP case that
      simplicity was not achievable due to cache-line contention between CPUs (in
      one measured case performance was actually _worse_ on a 16-cpu system than
      the same test on a 4-cpu system, due to this contention).  For SMP, the
      thread_group_cputime counters are maintained as a per-cpu structure allocated
      using alloc_percpu().  The timer functions update only the timer field in
      the structure corresponding to the running CPU, obtained using per_cpu_ptr().
      
      We define a set of inline functions in sched.h that we use to maintain the
      thread_group_cputime structure and hide the differences between UP and SMP
      implementations from the rest of the kernel.  The thread_group_cputime_init()
      function initializes the thread_group_cputime structure for the given task.
      The thread_group_cputime_alloc() is a no-op for UP; for SMP it calls the
      out-of-line function thread_group_cputime_alloc_smp() to allocate and fill
      in the per-cpu structures and fields.  The thread_group_cputime_free()
      function, also a no-op for UP, in SMP frees the per-cpu structures.  The
      thread_group_cputime_clone_thread() function (also a UP no-op) for SMP calls
      thread_group_cputime_alloc() if the per-cpu structures haven't yet been
      allocated.  The thread_group_cputime() function fills the task_cputime
      structure it is passed with the contents of the thread_group_cputime fields;
      in UP it's that simple but in SMP it must also safely check that tsk->signal
      is non-NULL (if it is it just uses the appropriate fields of task_struct) and,
      if so, sums the per-cpu values for each online CPU.  Finally, the three
      functions account_group_user_time(), account_group_system_time() and
      account_group_exec_runtime() are used by timer functions to update the
      respective fields of the thread_group_cputime structure.
      
      Non-SMP operation is trivial and will not be mentioned further.
      
      The per-cpu structure is always allocated when a task creates its first new
      thread, via a call to thread_group_cputime_clone_thread() from copy_signal().
      It is freed at process exit via a call to thread_group_cputime_free() from
      cleanup_signal().
      
      All functions that formerly summed utime/stime/sum_sched_runtime values from
      from all threads in the thread group now use thread_group_cputime() to
      snapshot the values in the thread_group_cputime structure or the values in
      the task structure itself if the per-cpu structure hasn't been allocated.
      
      Finally, the code in kernel/posix-cpu-timers.c has changed quite a bit.
      The run_posix_cpu_timers() function has been split into a fast path and a
      slow path; the former safely checks whether there are any expired thread
      timers and, if not, just returns, while the slow path does the heavy lifting.
      With the dedicated thread group fields, timers are no longer "rebalanced" and
      the process_timer_rebalance() function and related code has gone away.  All
      summing loops are gone and all code that used them now uses the
      thread_group_cputime() inline.  When process-wide timers are set, the new
      task_cputime structure in signal_struct is used to cache the earliest
      expiration; this is checked in the fast path.
      
      Performance
      
      The fix appears not to add significant overhead to existing operations.  It
      generally performs the same as the current code except in two cases, one in
      which it performs slightly worse (Case 5 below) and one in which it performs
      very significantly better (Case 2 below).  Overall it's a wash except in those
      two cases.
      
      I've since done somewhat more involved testing on a dual-core Opteron system.
      
      Case 1: With no itimer running, for a test with 100,000 threads, the fixed
      	kernel took 1428.5 seconds, 513 seconds more than the unfixed system,
      	all of which was spent in the system.  There were twice as many
      	voluntary context switches with the fix as without it.
      
      Case 2: With an itimer running at .01 second ticks and 4000 threads (the most
      	an unmodified kernel can handle), the fixed kernel ran the test in
      	eight percent of the time (5.8 seconds as opposed to 70 seconds) and
      	had better tick accuracy (.012 seconds per tick as opposed to .023
      	seconds per tick).
      
      Case 3: A 4000-thread test with an initial timer tick of .01 second and an
      	interval of 10,000 seconds (i.e. a timer that ticks only once) had
      	very nearly the same performance in both cases:  6.3 seconds elapsed
      	for the fixed kernel versus 5.5 seconds for the unfixed kernel.
      
      With fewer threads (eight in these tests), the Case 1 test ran in essentially
      the same time on both the modified and unmodified kernels (5.2 seconds versus
      5.8 seconds).  The Case 2 test ran in about the same time as well, 5.9 seconds
      versus 5.4 seconds but again with much better tick accuracy, .013 seconds per
      tick versus .025 seconds per tick for the unmodified kernel.
      
      Since the fix affected the rlimit code, I also tested soft and hard CPU limits.
      
      Case 4: With a hard CPU limit of 20 seconds and eight threads (and an itimer
      	running), the modified kernel was very slightly favored in that while
      	it killed the process in 19.997 seconds of CPU time (5.002 seconds of
      	wall time), only .003 seconds of that was system time, the rest was
      	user time.  The unmodified kernel killed the process in 20.001 seconds
      	of CPU (5.014 seconds of wall time) of which .016 seconds was system
      	time.  Really, though, the results were too close to call.  The results
      	were essentially the same with no itimer running.
      
      Case 5: With a soft limit of 20 seconds and a hard limit of 2000 seconds
      	(where the hard limit would never be reached) and an itimer running,
      	the modified kernel exhibited worse tick accuracy than the unmodified
      	kernel: .050 seconds/tick versus .028 seconds/tick.  Otherwise,
      	performance was almost indistinguishable.  With no itimer running this
      	test exhibited virtually identical behavior and times in both cases.
      
      In times past I did some limited performance testing.  those results are below.
      
      On a four-cpu Opteron system without this fix, a sixteen-thread test executed
      in 3569.991 seconds, of which user was 3568.435s and system was 1.556s.  On
      the same system with the fix, user and elapsed time were about the same, but
      system time dropped to 0.007 seconds.  Performance with eight, four and one
      thread were comparable.  Interestingly, the timer ticks with the fix seemed
      more accurate:  The sixteen-thread test with the fix received 149543 ticks
      for 0.024 seconds per tick, while the same test without the fix received 58720
      for 0.061 seconds per tick.  Both cases were configured for an interval of
      0.01 seconds.  Again, the other tests were comparable.  Each thread in this
      test computed the primes up to 25,000,000.
      
      I also did a test with a large number of threads, 100,000 threads, which is
      impossible without the fix.  In this case each thread computed the primes only
      up to 10,000 (to make the runtime manageable).  System time dominated, at
      1546.968 seconds out of a total 2176.906 seconds (giving a user time of
      629.938s).  It received 147651 ticks for 0.015 seconds per tick, still quite
      accurate.  There is obviously no comparable test without the fix.
      Signed-off-by: default avatarFrank Mayhar <fmayhar@google.com>
      Cc: Roland McGrath <roland@redhat.com>
      Cc: Alexey Dobriyan <adobriyan@gmail.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      f06febc9
  13. 29 Sep, 2006 1 commit
  14. 01 Feb, 2006 1 commit
  15. 10 Jan, 2006 4 commits
  16. 16 Apr, 2005 1 commit
    • Linus Torvalds's avatar
      Linux-2.6.12-rc2 · 1da177e4
      Linus Torvalds authored
      Initial git repository build. I'm not bothering with the full history,
      even though we have it. We can create a separate "historical" git
      archive of that later if we want to, and in the meantime it's about
      3.2GB when imported into git - space that would just make the early
      git days unnecessarily complicated, when we don't have a lot of good
      infrastructure for it.
      
      Let it rip!
      1da177e4