1. 03 Aug, 2011 2 commits
    • Huang Ying's avatar
      lib, Add lock-less NULL terminated single list · f49f23ab
      Huang Ying authored
      Cmpxchg is used to implement adding new entry to the list, deleting
      all entries from the list, deleting first entry of the list and some
      other operations.
      
      Because this is a single list, so the tail can not be accessed in O(1).
      
      If there are multiple producers and multiple consumers, llist_add can
      be used in producers and llist_del_all can be used in consumers.  They
      can work simultaneously without lock.  But llist_del_first can not be
      used here.  Because llist_del_first depends on list->first->next does
      not changed if list->first is not changed during its operation, but
      llist_del_first, llist_add, llist_add (or llist_del_all, llist_add,
      llist_add) sequence in another consumer may violate that.
      
      If there are multiple producers and one consumer, llist_add can be
      used in producers and llist_del_all or llist_del_first can be used in
      the consumer.
      
      This can be summarized as follow:
      
                 |   add    | del_first |  del_all
       add       |    -     |     -     |     -
       del_first |          |     L     |     L
       del_all   |          |           |     -
      
      Where "-" stands for no lock is needed, while "L" stands for lock is
      needed.
      
      The list entries deleted via llist_del_all can be traversed with
      traversing function such as llist_for_each etc.  But the list entries
      can not be traversed safely before deleted from the list.  The order
      of deleted entries is from the newest to the oldest added one.  If you
      want to traverse from the oldest to the newest, you must reverse the
      order by yourself before traversing.
      
      The basic atomic operation of this list is cmpxchg on long.  On
      architectures that don't have NMI-safe cmpxchg implementation, the
      list can NOT be used in NMI handler.  So code uses the list in NMI
      handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
      Signed-off-by: default avatarHuang Ying <ying.huang@intel.com>
      Reviewed-by: default avatarAndi Kleen <ak@linux.intel.com>
      Reviewed-by: default avatarMathieu Desnoyers <mathieu.desnoyers@efficios.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLen Brown <len.brown@intel.com>
      f49f23ab
    • Huang Ying's avatar
      Add Kconfig option ARCH_HAVE_NMI_SAFE_CMPXCHG · df013ffb
      Huang Ying authored
      cmpxchg() is widely used by lockless code, including NMI-safe lockless
      code.  But on some architectures, the cmpxchg() implementation is not
      NMI-safe, on these architectures the lockless code may need a
      spin_trylock_irqsave() based implementation.
      
      This patch adds a Kconfig option: ARCH_HAVE_NMI_SAFE_CMPXCHG, so that
      NMI-safe lockless code can depend on it or provide different
      implementation according to it.
      
      On many architectures, cmpxchg is only NMI-safe for several specific
      operand sizes. So, ARCH_HAVE_NMI_SAFE_CMPXCHG define in this patch
      only guarantees cmpxchg is NMI-safe for sizeof(unsigned long).
      Signed-off-by: default avatarHuang Ying <ying.huang@intel.com>
      Acked-by: default avatarMike Frysinger <vapier@gentoo.org>
      Acked-by: default avatarPaul Mundt <lethal@linux-sh.org>
      Acked-by: default avatarHans-Christian Egtvedt <hans-christian.egtvedt@atmel.com>
      Acked-by: default avatarBenjamin Herrenschmidt <benh@kernel.crashing.org>
      Acked-by: default avatarChris Metcalf <cmetcalf@tilera.com>
      Acked-by: default avatarRichard Henderson <rth@twiddle.net>
      CC: Mikael Starvik <starvik@axis.com>
      Acked-by: default avatarDavid Howells <dhowells@redhat.com>
      CC: Yoshinori Sato <ysato@users.sourceforge.jp>
      CC: Tony Luck <tony.luck@intel.com>
      CC: Hirokazu Takata <takata@linux-m32r.org>
      CC: Geert Uytterhoeven <geert@linux-m68k.org>
      CC: Michal Simek <monstr@monstr.eu>
      Acked-by: default avatarRalf Baechle <ralf@linux-mips.org>
      CC: Kyle McMartin <kyle@mcmartin.ca>
      CC: Martin Schwidefsky <schwidefsky@de.ibm.com>
      CC: Chen Liqin <liqin.chen@sunplusct.com>
      CC: "David S. Miller" <davem@davemloft.net>
      CC: Ingo Molnar <mingo@redhat.com>
      CC: Chris Zankel <chris@zankel.net>
      Signed-off-by: default avatarLen Brown <len.brown@intel.com>
      df013ffb
  2. 14 Jul, 2011 10 commits
  3. 12 Jul, 2011 8 commits
  4. 11 Jul, 2011 20 commits