1. 14 Feb, 2017 3 commits
    • Matthew Wilcox's avatar
      idr: Return the deleted entry from idr_remove · d3e709e6
      Matthew Wilcox authored
      It is a relatively common idiom (8 instances) to first look up an IDR
      entry, and then remove it from the tree if it is found, possibly doing
      further operations upon the entry afterwards.  If we change idr_remove()
      to return the removed object, all of these users can save themselves a
      walk of the IDR tree.
      Signed-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
    • Matthew Wilcox's avatar
      ida: Move ida_bitmap to a percpu variable · 7ad3d4d8
      Matthew Wilcox authored
      When we preload the IDA, we allocate an IDA bitmap.  Instead of storing
      that preallocated bitmap in the IDA, we store it in a percpu variable.
      Generally there are more IDAs in the system than CPUs, so this cuts down
      on the number of preallocated bitmaps that are unused, and about half
      of the IDA users did not call ida_destroy() so they were leaking IDA
      Signed-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
    • Matthew Wilcox's avatar
      Reimplement IDR and IDA using the radix tree · 0a835c4f
      Matthew Wilcox authored
      The IDR is very similar to the radix tree.  It has some functionality that
      the radix tree did not have (alloc next free, cyclic allocation, a
      callback-based for_each, destroy tree), which is readily implementable on
      top of the radix tree.  A few small changes were needed in order to use a
      tag to represent nodes with free space below them.  More extensive
      changes were needed to support storing NULL as a valid entry in an IDR.
      Plain radix trees still interpret NULL as a not-present entry.
      The IDA is reimplemented as a client of the newly enhanced radix tree.  As
      in the current implementation, it uses a bitmap at the last level of the
      Signed-off-by: default avatarMatthew Wilcox <willy@infradead.org>
      Signed-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
      Tested-by: default avatarKirill A. Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Cc: Tejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
  2. 15 Dec, 2016 3 commits
  3. 25 Nov, 2015 1 commit
  4. 06 Jun, 2014 1 commit
  5. 07 Apr, 2014 1 commit
  6. 17 Feb, 2014 1 commit
  7. 30 Jan, 2014 1 commit
  8. 30 Apr, 2013 1 commit
    • Jeff Layton's avatar
      idr: introduce idr_alloc_cyclic() · 3e6628c4
      Jeff Layton authored
      As Tejun points out, there are several users of the IDR facility that
      attempt to use it in a cyclic fashion.  These users are likely to see
      -ENOSPC errors after the counter wraps one or more times however.
      This patchset adds a new idr_alloc_cyclic routine and converts several
      of these users to it.  Many of these users are in obscure parts of the
      kernel, and I don't have a good way to test some of them.  The change is
      pretty straightforward though, so hopefully it won't be an issue.
      There is one other cyclic user of idr_alloc that I didn't touch in
      ipc/util.c.  That one is doing some strange stuff that I didn't quite
      understand, but it looks like it should probably be converted later
      This patch:
      Thus spake Tejun Heo:
          Ooh, BTW, the cyclic allocation is broken.  It's prone to -ENOSPC
          after the first wraparound.  There are several cyclic users in the
          kernel and I think it probably would be best to implement cyclic
          support in idr.
      This patch does that by adding new idr_alloc_cyclic function that such
      users in the kernel can use.  With this, there's no need for a caller to
      keep track of the last value used as that's now tracked internally.  This
      should prevent the ENOSPC problems that can hit when the "last allocated"
      counter exceeds INT_MAX.
      Later patches will convert existing cyclic users to the new interface.
      Signed-off-by: default avatarJeff Layton <jlayton@redhat.com>
      Reviewed-by: default avatarTejun Heo <tj@kernel.org>
      Cc: "David S. Miller" <davem@davemloft.net>
      Cc: "J. Bruce Fields" <bfields@fieldses.org>
      Cc: Eric Paris <eparis@parisplace.org>
      Cc: Jack Morgenstein <jackm@dev.mellanox.co.il>
      Cc: John McCutchan <john@johnmccutchan.com>
      Cc: Neil Horman <nhorman@tuxdriver.com>
      Cc: Or Gerlitz <ogerlitz@mellanox.com>
      Cc: Robert Love <rlove@rlove.org>
      Cc: Roland Dreier <roland@purestorage.com>
      Cc: Sridhar Samudrala <sri@us.ibm.com>
      Cc: Steve Wise <swise@opengridcomputing.com>
      Cc: Tom Tucker <tom@opengridcomputing.com>
      Cc: Vlad Yasevich <vyasevich@gmail.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
  9. 28 Mar, 2013 1 commit
  10. 13 Mar, 2013 2 commits
  11. 28 Feb, 2013 10 commits
    • Tejun Heo's avatar
      idr: implement lookup hint · 0ffc2a9c
      Tejun Heo authored
      While idr lookup isn't a particularly heavy operation, it still is too
      substantial to use in hot paths without worrying about the performance
      implications.  With recent changes, each idr_layer covers 256 slots
      which should be enough to cover most use cases with single idr_layer
      making lookup hint very attractive.
      This patch adds idr->hint which points to the idr_layer which
      allocated an ID most recently and the fast path lookup becomes
      	if (look up target's prefix matches that of the hinted layer)
      		return hint->ary[ID's offset in the leaf layer];
      which can be inlined.
      idr->hint is set to the leaf node on idr_fill_slot() and cleared from
      [andriy.shevchenko@linux.intel.com: always do slow path when hint is uninitialized]
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Cc: Kirill A. Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Sasha Levin <sasha.levin@oracle.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: add idr_layer->prefix · 54616283
      Tejun Heo authored
      Add a field which carries the prefix of ID the idr_layer covers.  This
      will be used to implement lookup hint.
      This patch doesn't make use of the new field and doesn't introduce any
      behavior difference.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: make idr_layer larger · 050a6b47
      Tejun Heo authored
      With recent preloading changes, idr no longer keeps full layer cache per
      each idr instance (used to be ~6.5k per idr on 64bit) and the previous
      patch removed restriction on the bitmap size.  Both now allow us to have
      larger layers.
      Increase IDR_BITS to 8 regardless of BITS_PER_LONG.  Each layer is
      slightly larger than 2k on 64bit and 1k on 32bit and carries 256 entries.
      The size isn't too large, especially compared to what we used to waste on
      per-idr caches, and 256 entries should be able to serve most use cases
      with single layer.  The max tree depth is 4 which is much better than the
      previous 6 on 64bit and 7 on 32bit.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: remove length restriction from idr_layer->bitmap · 1d9b2e1e
      Tejun Heo authored
      Currently, idr->bitmap is declared as an unsigned long which restricts
      the number of bits an idr_layer can contain.  All bitops can handle
      arbitrary positive integer bit number and there's no reason for this
      Declare idr_layer->bitmap using DECLARE_BITMAP() instead of a single
      unsigned long.
      * idr_layer->bitmap is now an array.  '&' dropped from params to
      * Replaced "== IDR_FULL" tests with bitmap_full() and removed
      * Replaced find_next_bit() on ~bitmap with find_next_zero_bit().
      * Replaced "bitmap = 0" with bitmap_clear().
      This patch doesn't (or at least shouldn't) introduce any behavior
      [akpm@linux-foundation.org: checkpatch fixes]
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: remove MAX_IDR_MASK and move left MAX_IDR_* into idr.c · e8c8d1bc
      Tejun Heo authored
      MAX_IDR_MASK is another weirdness in the idr interface.  As idr covers
      whole positive integer range, it's defined as 0x7fffffff or INT_MAX.
      Its usage in idr_find(), idr_replace() and idr_remove() is bizarre.
      They basically mask off the sign bit and operate on the rest, so if
      the caller, by accident, passes in a negative number, the sign bit
      will be masked off and the remaining part will be used as if that was
      the input, which is worse than crashing.
      The constant is visible in idr.h and there are several users in the
      * drivers/i2c/i2c-core.c:i2c_add_numbered_adapter()
        Basically used to test if adap->nr is a negative number which isn't
        -1 and returns -EINVAL if so.  idr_alloc() already has negative
        @start checking (w/ WARN_ON_ONCE), so this can go away.
      * drivers/infiniband/core/cm.c:cm_alloc_id()
        Used to wrap cyclic @start.  Can be replaced with max(next, 0).
        Note that this type of cyclic allocation using idr is buggy.  These
        are prone to spurious -ENOSPC failure after the first wraparound.
      * fs/super.c:get_anon_bdev()
        The ID allocated from ida is masked off before being tested whether
        it's inside valid range.  ida allocated ID can never be a negative
        number and the masking is unnecessary.
      Update idr_*() functions to fail with -EINVAL when negative @id is
      specified and update other MAX_IDR_MASK users as described above.
      This leaves MAX_IDR_MASK without any user, remove it and relocate
      other MAX_IDR_* constants to lib/idr.c.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Cc: Jean Delvare <khali@linux-fr.org>
      Cc: Roland Dreier <roland@kernel.org>
      Cc: Sean Hefty <sean.hefty@intel.com>
      Cc: Hal Rosenstock <hal.rosenstock@gmail.com>
      Cc: "Marciniszyn, Mike" <mike.marciniszyn@intel.com>
      Cc: Jack Morgenstein <jackm@dev.mellanox.co.il>
      Cc: Or Gerlitz <ogerlitz@mellanox.com>
      Cc: Al Viro <viro@zeniv.linux.org.uk>
      Acked-by: default avatarWolfram Sang <wolfram@the-dreams.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: implement idr_preload[_end]() and idr_alloc() · d5c7409f
      Tejun Heo authored
      The current idr interface is very cumbersome.
      * For all allocations, two function calls - idr_pre_get() and
        idr_get_new*() - should be made.
      * idr_pre_get() doesn't guarantee that the following idr_get_new*()
        will not fail from memory shortage.  If idr_get_new*() returns
        -EAGAIN, the caller is expected to retry pre_get and allocation.
      * idr_get_new*() can't enforce upper limit.  Upper limit can only be
        enforced by allocating and then freeing if above limit.
      * idr_layer buffer is unnecessarily per-idr.  Each idr ends up keeping
        around MAX_IDR_FREE idr_layers.  The memory consumed per idr is
        under two pages but it makes it difficult to make idr_layer larger.
      This patch implements the following new set of allocation functions.
      * idr_preload[_end]() - Similar to radix preload but doesn't fail.
        The first idr_alloc() inside preload section can be treated as if it
        were called with @gfp_mask used for idr_preload().
      * idr_alloc() - Allocate an ID w/ lower and upper limits.  Takes
        @gfp_flags and can be used w/o preloading.  When used inside
        preloaded section, the allocation mask of preloading can be assumed.
      If idr_alloc() can be called from a context which allows sufficiently
      relaxed @gfp_mask, it can be used by itself.  If, for example,
      idr_alloc() is called inside spinlock protected region, preloading can
      be used like the following.
      	id = idr_alloc(idr, ptr, start, end, GFP_NOWAIT);
      	if (id < 0)
      which is much simpler and less error-prone than idr_pre_get and
      idr_get_new*() loop.
      The new interface uses per-pcu idr_layer buffer and thus the number of
      idr's in the system doesn't affect the amount of memory used for
      idr_layer_alloc() is introduced to handle idr_layer allocations for
      both old and new ID allocation paths.  This is a bit hairy now but the
      new interface is expected to replace the old and the internal
      implementation eventually will become simpler.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Cc: Rusty Russell <rusty@rustcorp.com.au>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: remove _idr_rc_to_errno() hack · 12d1b439
      Tejun Heo authored
      idr uses -1, IDR_NEED_TO_GROW and IDR_NOMORE_SPACE to communicate
      exception conditions internally.  The return value is later translated
      to errno values using _idr_rc_to_errno().
      This is confusing.  Drop the custom ones and consistently use -EAGAIN
      for "tree needs to grow", -ENOMEM for "need more memory" and -ENOSPC for
      "ran out of ID space".
      Due to the weird memory preloading mechanism, [ra]_get_new*() return
      -EAGAIN on memory shortage, so we need to substitute -ENOMEM w/
      -EAGAIN on those interface functions.  They'll eventually be cleaned
      up and the translations will go away.
      This patch doesn't introduce any functional changes.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: relocate idr_for_each_entry() and reorganize id[r|a]_get_new() · 49038ef4
      Tejun Heo authored
      * Move idr_for_each_entry() definition next to other idr related
      * Make id[r|a]_get_new() inline wrappers of id[r|a]_get_new_above().
      This changes the implementation of idr_get_new() but the new
      implementation is trivial.  This patch doesn't introduce any
      functional change.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: cosmetic updates to struct / initializer definitions · 4106ecaf
      Tejun Heo authored
      * Tab align fields like a normal person.
      * Drop the unnecessary 0 inits from IDR_INIT().
      This patch is purely cosmetic.
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Tejun Heo's avatar
      idr: deprecate idr_remove_all() · fe6e24ec
      Tejun Heo authored
      There was only one legitimate use of idr_remove_all() and a lot more of
      incorrect uses (or lack of it).  Now that idr_destroy() implies
      idr_remove_all() and all the in-kernel users updated not to use it,
      there's no reason to keep it around.  Mark it deprecated so that we can
      later unexport it.
      idr_remove_all() is made an inline function calling __idr_remove_all()
      to avoid triggering deprecated warning on EXPORT_SYMBOL().
      Signed-off-by: default avatarTejun Heo <tj@kernel.org>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
  12. 19 Feb, 2013 1 commit
  13. 05 Oct, 2012 1 commit
  14. 29 Aug, 2011 1 commit
  15. 04 Aug, 2011 1 commit
  16. 27 Oct, 2010 1 commit
  17. 23 Sep, 2010 1 commit
  18. 20 Aug, 2010 1 commit
  19. 03 Apr, 2009 1 commit
    • KAMEZAWA Hiroyuki's avatar
      cgroup: CSS ID support · 38460b48
      KAMEZAWA Hiroyuki authored
      Patch for Per-CSS(Cgroup Subsys State) ID and private hierarchy code.
      This patch attaches unique ID to each css and provides following.
       - css_lookup(subsys, id)
         returns pointer to struct cgroup_subysys_state of id.
       - css_get_next(subsys, id, rootid, depth, foundid)
         returns the next css under "root" by scanning
      When cgroup_subsys->use_id is set, an id for css is maintained.
      The cgroup framework only parepares
      	- css_id of root css for subsys
      	- id is automatically attached at creation of css.
      	- id is *not* freed automatically. Because the cgroup framework
      	  don't know lifetime of cgroup_subsys_state.
      	  free_css_id() function is provided. This must be called by subsys.
      There are several reasons to develop this.
      	- Saving space .... For example, memcg's swap_cgroup is array of
      	  pointers to cgroup. But it is not necessary to be very fast.
      	  By replacing pointers(8bytes per ent) to ID (2byes per ent), we can
      	  reduce much amount of memory usage.
      	- Scanning without lock.
      	  CSS_ID provides "scan id under this ROOT" function. By this, scanning
      	  css under root can be written without locks.
      	  do {
      		next = cgroup_get_next(subsys, id, root, &found);
      		/* check sanity of next here */
      		id = found + 1
      	 } while(...)
      	- Each css has unique ID under subsys.
      	- Lifetime of ID is controlled by subsys.
      	- css ID contains "ID" and "Depth in hierarchy" and stack of hierarchy
      	- Allowed ID is 1-65535, ID 0 is UNUSED ID.
      Design Choices:
      	- scan-by-ID v.s. scan-by-tree-walk.
      	  As /proc's pid scan does, scan-by-ID is robust when scanning is done
      	  by following kind of routine.
      	  scan -> rest a while(release a lock) -> conitunue from interrupted
      	  memcg's hierarchical reclaim does this.
      	- When subsys->use_id is set, # of css in the system is limited to
      [bharata@linux.vnet.ibm.com: remove rcu_read_lock() from css_get_next()]
      Signed-off-by: default avatarKAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
      Acked-by: default avatarPaul Menage <menage@google.com>
      Cc: Li Zefan <lizf@cn.fujitsu.com>
      Cc: Balbir Singh <balbir@in.ibm.com>
      Cc: Daisuke Nishimura <nishimura@mxp.nes.nec.co.jp>
      Signed-off-by: default avatarBharata B Rao <bharata@linux.vnet.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
  20. 02 Dec, 2008 1 commit
  21. 25 Jul, 2008 3 commits
  22. 29 Apr, 2008 1 commit
  23. 16 Jul, 2007 2 commits
    • Kristian Hoegsberg's avatar
      lib: add idr_remove_all · 23936cc0
      Kristian Hoegsberg authored
      Remove all ids from the given idr tree.  idr_destroy() only frees up
      unused, cached idp_layers, but this function will remove all id mappings
      and leave all idp_layers unused.
      A typical clean-up sequence for objects stored in an idr tree, will use
      idr_for_each() to free all objects, if necessay, then idr_remove_all() to
      remove all ids, and idr_destroy() to free up the cached idr_layers.
      Signed-off-by: default avatarKristian Hoegsberg <krh@redhat.com>
      Cc: Tejun Heo <htejun@gmail.com>
      Cc: Dave Airlie <airlied@linux.ie>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    • Kristian Hoegsberg's avatar
      lib: add idr_for_each() · 96d7fa42
      Kristian Hoegsberg authored
      This patch adds an iterator function for the idr data structure.  Compared
      to just iterating through the idr with an integer and idr_find, this
      iterator is (almost, but not quite) linear in the number of elements, as
      opposed to the number of integers in the range covered by the idr.  This
      makes a difference for sparse idrs, but more importantly, it's a nicer way
      to iterate through the elements.
      The drm subsystem is moving to idr for tracking contexts and drawables, and
      with this change, we can use the idr exclusively for tracking these
      [akpm@linux-foundation.org: fix comment]
      Signed-off-by: default avatarKristian Hoegsberg <krh@redhat.com>
      Cc: Tejun Heo <htejun@gmail.com>
      Cc: Dave Airlie <airlied@linux.ie>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>