1. 13 Jul, 2013 2 commits
    • Oleg Nesterov's avatar
      llist: llist_add() can use llist_add_batch() · e9a17bd7
      Oleg Nesterov authored
      
      
      llist_add(new, head) can simply use llist_add_batch(new, new, head),
      no need to duplicate the code.
      
      This obviously uninlines llist_add() and to me this is a win. But we
      can make llist_add_batch() inline if this is desirable, in this case
      gcc can notice that new_first == new_last if the caller is llist_add().
      Signed-off-by: default avatarOleg Nesterov <oleg@redhat.com>
      Cc: Al Viro <viro@zeniv.linux.org.uk>
      Cc: Andrey Vagin <avagin@openvz.org>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Cc: David Howells <dhowells@redhat.com>
      Cc: Huang Ying <ying.huang@intel.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
      e9a17bd7
    • Oleg Nesterov's avatar
      llist: fix/simplify llist_add() and llist_add_batch() · fb4214db
      Oleg Nesterov authored
      
      
      1. This is mostly theoretical, but llist_add*() need ACCESS_ONCE().
      
         Otherwise it is not guaranteed that the first cmpxchg() uses the
         same value for old_entry and new_last->next.
      
      2. These helpers cache the result of cmpxchg() and read the initial
         value of head->first before the main loop. I do not think this
         makes sense. In the likely case cmpxchg() succeeds, otherwise
         it doesn't hurt to reload head->first.
      
         I think it would be better to simplify the code and simply read
         ->first before cmpxchg().
      Signed-off-by: default avatarOleg Nesterov <oleg@redhat.com>
      Cc: Al Viro <viro@zeniv.linux.org.uk>
      Cc: Andrey Vagin <avagin@openvz.org>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Cc: David Howells <dhowells@redhat.com>
      Cc: Huang Ying <ying.huang@intel.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
      fb4214db
  2. 19 Feb, 2013 1 commit
    • Konrad Rzeszutek Wilk's avatar
      xen-blkfront: drop the use of llist_for_each_entry_safe · f84adf49
      Konrad Rzeszutek Wilk authored
      
      
      Replace llist_for_each_entry_safe with a while loop.
      
      llist_for_each_entry_safe can trigger a bug in GCC 4.1, so it's best
      to remove it and use a while loop and do the deletion manually.
      
      Specifically this bug can be triggered by hot-unplugging a disk, either
      by doing xm block-detach or by save/restore cycle.
      
      BUG: unable to handle kernel paging request at fffffffffffffff0
      IP: [<ffffffffa0047223>] blkif_free+0x63/0x130 [xen_blkfront]
      The crash call trace is:
      	...
      bad_area_nosemaphore+0x13/0x20
      do_page_fault+0x25e/0x4b0
      page_fault+0x25/0x30
      ? blkif_free+0x63/0x130 [xen_blkfront]
      blkfront_resume+0x46/0xa0 [xen_blkfront]
      xenbus_dev_resume+0x6c/0x140
      pm_op+0x192/0x1b0
      device_resume+0x82/0x1e0
      dpm_resume+0xc9/0x1a0
      dpm_resume_end+0x15/0x30
      do_suspend+0x117/0x1e0
      
      When drilling down to the assembler code, on newer GCC it does
      .L29:
              cmpq    $-16, %r12      #, persistent_gnt check
              je      .L30    	#, out of the loop
      .L25:
      	... code in the loop
              testq   %r13, %r13      # n
              je      .L29    	#, back to the top of the loop
              cmpq    $-16, %r12      #, persistent_gnt check
              movq    16(%r12), %r13  # <variable>.node.next, n
              jne     .L25    	#,	back to the top of the loop
      .L30:
      
      While on GCC 4.1, it is:
      L78:
      	... code in the loop
      	testq   %r13, %r13      # n
              je      .L78    #,	back to the top of the loop
              movq    16(%rbx), %r13  # <variable>.node.next, n
              jmp     .L78    #,	back to the top of the loop
      
      Which basically means that the exit loop condition instead of
      being:
      
      	&(pos)->member != NULL;
      
      is:
      	;
      
      which makes the loop unbound.
      
      Since xen-blkfront is the only user of the llist_for_each_entry_safe
      macro remove it from llist.h.
      
      Orabug: 16263164
      CC: stable@vger.kernel.org
      Signed-off-by: default avatarKonrad Rzeszutek Wilk <konrad.wilk@oracle.com>
      f84adf49
  3. 17 Dec, 2012 1 commit
  4. 28 Mar, 2012 1 commit
    • David Howells's avatar
      Add #includes needed to permit the removal of asm/system.h · 96f951ed
      David Howells authored
      
      
      asm/system.h is a cause of circular dependency problems because it contains
      commonly used primitive stuff like barrier definitions and uncommonly used
      stuff like switch_to() that might require MMU definitions.
      
      asm/system.h has been disintegrated by this point on all arches into the
      following common segments:
      
       (1) asm/barrier.h
      
           Moved memory barrier definitions here.
      
       (2) asm/cmpxchg.h
      
           Moved xchg() and cmpxchg() here.  #included in asm/atomic.h.
      
       (3) asm/bug.h
      
           Moved die() and similar here.
      
       (4) asm/exec.h
      
           Moved arch_align_stack() here.
      
       (5) asm/elf.h
      
           Moved AT_VECTOR_SIZE_ARCH here.
      
       (6) asm/switch_to.h
      
           Moved switch_to() here.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      96f951ed
  5. 31 Oct, 2011 1 commit
  6. 11 Oct, 2011 1 commit
  7. 04 Oct, 2011 6 commits
  8. 03 Aug, 2011 1 commit
    • 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