)]}'
{
  "commit": "55c888d6d09a0df236adfaf8ccf06ff5d0646775",
  "tree": "deb9434abe3cf7c9b714ccb267ef5d943a847dfe",
  "parents": [
    "bdd646a44672115c986593956aa4ef105485a184"
  ],
  "author": {
    "name": "Oleg Nesterov",
    "email": "oleg@tv-sign.ru",
    "time": "Thu Jun 23 00:08:56 2005 -0700"
  },
  "committer": {
    "name": "Linus Torvalds",
    "email": "torvalds@ppc970.osdl.org",
    "time": "Thu Jun 23 09:45:16 2005 -0700"
  },
  "message": "[PATCH] timers fixes/improvements\n\nThis patch tries to solve following problems:\n\n1. del_timer_sync() is racy. The timer can be fired again after\n   del_timer_sync have checked all cpus and before it will recheck\n   timer_pending().\n\n2. It has scalability problems. All cpus are scanned to determine\n   if the timer is running on that cpu.\n\n   With this patch del_timer_sync is O(1) and no slower than plain\n   del_timer(pending_timer), unless it has to actually wait for\n   completion of the currently running timer.\n\n   The only restriction is that the recurring timer should not use\n   add_timer_on().\n\n3. The timers are not serialized wrt to itself.\n\n   If CPU_0 does mod_timer(jiffies+1) while the timer is currently\n   running on CPU 1, it is quite possible that local interrupt on\n   CPU_0 will start that timer before it finished on CPU_1.\n\n4. The timers locking is suboptimal. __mod_timer() takes 3 locks\n   at once and still requires wmb() in del_timer/run_timers.\n\n   The new implementation takes 2 locks sequentially and does not\n   need memory barriers.\n\nCurrently -\u003ebase !\u003d NULL means that the timer is pending. In that case\n-\u003ebase.lock is used to lock the timer. __mod_timer also takes timer-\u003elock\nbecause -\u003ebase can be \u003d\u003d NULL.\n\nThis patch uses timer-\u003eentry.next !\u003d NULL as indication that the timer is\npending. So it does __list_del(), entry-\u003enext \u003d NULL instead of list_del()\nwhen the timer is deleted.\n\nThe -\u003ebase field is used for hashed locking only, it is initialized\nin init_timer() which sets -\u003ebase \u003d per_cpu(tvec_bases). When the\ntvec_bases.lock is locked, it means that all timers which are tied\nto this base via timer-\u003ebase are locked, and the base itself is locked\ntoo.\n\nSo __run_timers/migrate_timers can safely modify all timers which could\nbe found on -\u003etvX lists (pending timers).\n\nWhen the timer\u0027s base is locked, and the timer removed from -\u003eentry list\n(which means that _run_timers/migrate_timers can\u0027t see this timer), it is\npossible to set timer-\u003ebase \u003d NULL and drop the lock: the timer remains\nlocked.\n\nThis patch adds lock_timer_base() helper, which waits for -\u003ebase !\u003d NULL,\nlocks the -\u003ebase, and checks it is still the same.\n\n__mod_timer() schedules the timer on the local CPU and changes it\u0027s base.\nHowever, it does not lock both old and new bases at once. It locks the\ntimer via lock_timer_base(), deletes the timer, sets -\u003ebase \u003d NULL, and\nunlocks old base. Then __mod_timer() locks new_base, sets -\u003ebase \u003d new_base,\nand adds this timer. This simplifies the code, because AB-BA deadlock is not\npossible. __mod_timer() also ensures that the timer\u0027s base is not changed\nwhile the timer\u0027s handler is running on the old base.\n\n__run_timers(), del_timer() do not change -\u003ebase anymore, they only clear\npending flag.\n\nSo del_timer_sync() can test timer-\u003ebase-\u003erunning_timer \u003d\u003d timer to detect\nwhether it is running or not.\n\nWe don\u0027t need timer_list-\u003elock anymore, this patch kills it.\n\nWe also don\u0027t need barriers. del_timer() and __run_timers() used smp_wmb()\nbefore clearing timer\u0027s pending flag. It was needed because __mod_timer()\ndid not lock old_base if the timer is not pending, so __mod_timer()-\u003elist_add()\ncould race with del_timer()-\u003elist_del(). With this patch these functions are\nserialized through base-\u003elock.\n\nOne problem. TIMER_INITIALIZER can\u0027t use per_cpu(tvec_bases). So this patch\nadds global\n\n        struct timer_base_s {\n                spinlock_t lock;\n                struct timer_list *running_timer;\n        } __init_timer_base;\n\nwhich is used by TIMER_INITIALIZER. The corresponding fields in tvec_t_base_s\nstruct are replaced by struct timer_base_s t_base.\n\nIt is indeed ugly. But this can\u0027t have scalability problems. The global\n__init_timer_base.lock is used only when __mod_timer() is called for the first\ntime AND the timer was compile time initialized. After that the timer migrates\nto the local CPU.\n\nSigned-off-by: Oleg Nesterov \u003coleg@tv-sign.ru\u003e\nAcked-by: Ingo Molnar \u003cmingo@elte.hu\u003e\nSigned-off-by: Renaud Lienhart \u003crenaud.lienhart@free.fr\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "90db1cc62ddd02875918840b129945aff45df56e",
      "old_mode": 33188,
      "old_path": "include/linux/timer.h",
      "new_id": "2e78fedfc06929bfeb7ed70c380e60f31dcf3cba",
      "new_mode": 33188,
      "new_path": "include/linux/timer.h"
    },
    {
      "type": "modify",
      "old_id": "207aa4f0aa10b741373b5863d48bd2c183564270",
      "old_mode": 33188,
      "old_path": "kernel/timer.c",
      "new_id": "8aadc62efd65379dff44fcc08cc57e3c0fd90bbf",
      "new_mode": 33188,
      "new_path": "kernel/timer.c"
    }
  ]
}