LCOV - code coverage report
Current view: top level - lib - idr.c (source / functions) Hit Total Coverage
Test: gcov_data_raspi2_real_modules_combined.info Lines: 121 153 79.1 %
Date: 2020-09-30 20:25:40 Functions: 11 12 91.7 %
Branches: 74 130 56.9 %

           Branch data     Line data    Source code
       1                 :            : // SPDX-License-Identifier: GPL-2.0-only
       2                 :            : #include <linux/bitmap.h>
       3                 :            : #include <linux/bug.h>
       4                 :            : #include <linux/export.h>
       5                 :            : #include <linux/idr.h>
       6                 :            : #include <linux/slab.h>
       7                 :            : #include <linux/spinlock.h>
       8                 :            : #include <linux/xarray.h>
       9                 :            : 
      10                 :            : /**
      11                 :            :  * idr_alloc_u32() - Allocate an ID.
      12                 :            :  * @idr: IDR handle.
      13                 :            :  * @ptr: Pointer to be associated with the new ID.
      14                 :            :  * @nextid: Pointer to an ID.
      15                 :            :  * @max: The maximum ID to allocate (inclusive).
      16                 :            :  * @gfp: Memory allocation flags.
      17                 :            :  *
      18                 :            :  * Allocates an unused ID in the range specified by @nextid and @max.
      19                 :            :  * Note that @max is inclusive whereas the @end parameter to idr_alloc()
      20                 :            :  * is exclusive.  The new ID is assigned to @nextid before the pointer
      21                 :            :  * is inserted into the IDR, so if @nextid points into the object pointed
      22                 :            :  * to by @ptr, a concurrent lookup will not find an uninitialised ID.
      23                 :            :  *
      24                 :            :  * The caller should provide their own locking to ensure that two
      25                 :            :  * concurrent modifications to the IDR are not possible.  Read-only
      26                 :            :  * accesses to the IDR may be done under the RCU read lock or may
      27                 :            :  * exclude simultaneous writers.
      28                 :            :  *
      29                 :            :  * Return: 0 if an ID was allocated, -ENOMEM if memory allocation failed,
      30                 :            :  * or -ENOSPC if no free IDs could be found.  If an error occurred,
      31                 :            :  * @nextid is unchanged.
      32                 :            :  */
      33                 :    5498266 : int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
      34                 :            :                         unsigned long max, gfp_t gfp)
      35                 :            : {
      36                 :            :         struct radix_tree_iter iter;
      37                 :            :         void __rcu **slot;
      38                 :    5498266 :         unsigned int base = idr->idr_base;
      39                 :    5498266 :         unsigned int id = *nextid;
      40                 :            : 
      41   [ -  +  #  #  :    5498266 :         if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
                   -  + ]
      42                 :          0 :                 idr->idr_rt.xa_flags |= IDR_RT_MARKER;
      43                 :            : 
      44         [ +  + ]:    5498267 :         id = (id < base) ? 0 : id - base;
      45                 :            :         radix_tree_iter_init(&iter, id);
      46                 :    5498267 :         slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
      47         [ -  + ]:    5498274 :         if (IS_ERR(slot))
      48                 :          0 :                 return PTR_ERR(slot);
      49                 :            : 
      50                 :    5498274 :         *nextid = iter.index + base;
      51                 :            :         /* there is a memory barrier inside radix_tree_iter_replace() */
      52                 :    5498274 :         radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
      53                 :    5498276 :         radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
      54                 :            : 
      55                 :    5498272 :         return 0;
      56                 :            : }
      57                 :            : EXPORT_SYMBOL_GPL(idr_alloc_u32);
      58                 :            : 
      59                 :            : /**
      60                 :            :  * idr_alloc() - Allocate an ID.
      61                 :            :  * @idr: IDR handle.
      62                 :            :  * @ptr: Pointer to be associated with the new ID.
      63                 :            :  * @start: The minimum ID (inclusive).
      64                 :            :  * @end: The maximum ID (exclusive).
      65                 :            :  * @gfp: Memory allocation flags.
      66                 :            :  *
      67                 :            :  * Allocates an unused ID in the range specified by @start and @end.  If
      68                 :            :  * @end is <= 0, it is treated as one larger than %INT_MAX.  This allows
      69                 :            :  * callers to use @start + N as @end as long as N is within integer range.
      70                 :            :  *
      71                 :            :  * The caller should provide their own locking to ensure that two
      72                 :            :  * concurrent modifications to the IDR are not possible.  Read-only
      73                 :            :  * accesses to the IDR may be done under the RCU read lock or may
      74                 :            :  * exclude simultaneous writers.
      75                 :            :  *
      76                 :            :  * Return: The newly allocated ID, -ENOMEM if memory allocation failed,
      77                 :            :  * or -ENOSPC if no free IDs could be found.
      78                 :            :  */
      79                 :     110974 : int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
      80                 :            : {
      81                 :     110974 :         u32 id = start;
      82                 :            :         int ret;
      83                 :            : 
      84   [ -  +  #  #  :     110974 :         if (WARN_ON_ONCE(start < 0))
                   +  - ]
      85                 :            :                 return -EINVAL;
      86                 :            : 
      87         [ +  + ]:     110982 :         ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp);
      88         [ +  - ]:     110981 :         if (ret)
      89                 :            :                 return ret;
      90                 :            : 
      91                 :     110983 :         return id;
      92                 :            : }
      93                 :            : EXPORT_SYMBOL_GPL(idr_alloc);
      94                 :            : 
      95                 :            : /**
      96                 :            :  * idr_alloc_cyclic() - Allocate an ID cyclically.
      97                 :            :  * @idr: IDR handle.
      98                 :            :  * @ptr: Pointer to be associated with the new ID.
      99                 :            :  * @start: The minimum ID (inclusive).
     100                 :            :  * @end: The maximum ID (exclusive).
     101                 :            :  * @gfp: Memory allocation flags.
     102                 :            :  *
     103                 :            :  * Allocates an unused ID in the range specified by @nextid and @end.  If
     104                 :            :  * @end is <= 0, it is treated as one larger than %INT_MAX.  This allows
     105                 :            :  * callers to use @start + N as @end as long as N is within integer range.
     106                 :            :  * The search for an unused ID will start at the last ID allocated and will
     107                 :            :  * wrap around to @start if no free IDs are found before reaching @end.
     108                 :            :  *
     109                 :            :  * The caller should provide their own locking to ensure that two
     110                 :            :  * concurrent modifications to the IDR are not possible.  Read-only
     111                 :            :  * accesses to the IDR may be done under the RCU read lock or may
     112                 :            :  * exclude simultaneous writers.
     113                 :            :  *
     114                 :            :  * Return: The newly allocated ID, -ENOMEM if memory allocation failed,
     115                 :            :  * or -ENOSPC if no free IDs could be found.
     116                 :            :  */
     117                 :    5387284 : int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
     118                 :            : {
     119                 :    5387284 :         u32 id = idr->idr_next;
     120         [ +  + ]:    5387284 :         int err, max = end > 0 ? end - 1 : INT_MAX;
     121                 :            : 
     122         [ +  + ]:    5387284 :         if ((int)id < start)
     123                 :      10350 :                 id = start;
     124                 :            : 
     125                 :    5387284 :         err = idr_alloc_u32(idr, ptr, &id, max, gfp);
     126   [ -  +  #  # ]:    5387279 :         if ((err == -ENOSPC) && (id > start)) {
     127                 :          0 :                 id = start;
     128                 :          0 :                 err = idr_alloc_u32(idr, ptr, &id, max, gfp);
     129                 :            :         }
     130         [ +  - ]:    5387291 :         if (err)
     131                 :            :                 return err;
     132                 :            : 
     133                 :    5387291 :         idr->idr_next = id + 1;
     134                 :    5387291 :         return id;
     135                 :            : }
     136                 :            : EXPORT_SYMBOL(idr_alloc_cyclic);
     137                 :            : 
     138                 :            : /**
     139                 :            :  * idr_remove() - Remove an ID from the IDR.
     140                 :            :  * @idr: IDR handle.
     141                 :            :  * @id: Pointer ID.
     142                 :            :  *
     143                 :            :  * Removes this ID from the IDR.  If the ID was not previously in the IDR,
     144                 :            :  * this function returns %NULL.
     145                 :            :  *
     146                 :            :  * Since this function modifies the IDR, the caller should provide their
     147                 :            :  * own locking to ensure that concurrent modification of the same IDR is
     148                 :            :  * not possible.
     149                 :            :  *
     150                 :            :  * Return: The pointer formerly associated with this ID.
     151                 :            :  */
     152                 :    2010417 : void *idr_remove(struct idr *idr, unsigned long id)
     153                 :            : {
     154                 :    2010417 :         return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
     155                 :            : }
     156                 :            : EXPORT_SYMBOL_GPL(idr_remove);
     157                 :            : 
     158                 :            : /**
     159                 :            :  * idr_find() - Return pointer for given ID.
     160                 :            :  * @idr: IDR handle.
     161                 :            :  * @id: Pointer ID.
     162                 :            :  *
     163                 :            :  * Looks up the pointer associated with this ID.  A %NULL pointer may
     164                 :            :  * indicate that @id is not allocated or that the %NULL pointer was
     165                 :            :  * associated with this ID.
     166                 :            :  *
     167                 :            :  * This function can be called under rcu_read_lock(), given that the leaf
     168                 :            :  * pointers lifetimes are correctly managed.
     169                 :            :  *
     170                 :            :  * Return: The pointer associated with this ID.
     171                 :            :  */
     172                 :    3986965 : void *idr_find(const struct idr *idr, unsigned long id)
     173                 :            : {
     174                 :    3986965 :         return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
     175                 :            : }
     176                 :            : EXPORT_SYMBOL_GPL(idr_find);
     177                 :            : 
     178                 :            : /**
     179                 :            :  * idr_for_each() - Iterate through all stored pointers.
     180                 :            :  * @idr: IDR handle.
     181                 :            :  * @fn: Function to be called for each pointer.
     182                 :            :  * @data: Data passed to callback function.
     183                 :            :  *
     184                 :            :  * The callback function will be called for each entry in @idr, passing
     185                 :            :  * the ID, the entry and @data.
     186                 :            :  *
     187                 :            :  * If @fn returns anything other than %0, the iteration stops and that
     188                 :            :  * value is returned from this function.
     189                 :            :  *
     190                 :            :  * idr_for_each() can be called concurrently with idr_alloc() and
     191                 :            :  * idr_remove() if protected by RCU.  Newly added entries may not be
     192                 :            :  * seen and deleted entries may be seen, but adding and removing entries
     193                 :            :  * will not cause other entries to be skipped, nor spurious ones to be seen.
     194                 :            :  */
     195                 :     126712 : int idr_for_each(const struct idr *idr,
     196                 :            :                 int (*fn)(int id, void *p, void *data), void *data)
     197                 :            : {
     198                 :            :         struct radix_tree_iter iter;
     199                 :            :         void __rcu **slot;
     200                 :     126712 :         int base = idr->idr_base;
     201                 :            : 
     202   [ -  +  -  + ]:     253424 :         radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
     203                 :            :                 int ret;
     204                 :          0 :                 unsigned long id = iter.index + base;
     205                 :            : 
     206   [ #  #  #  #  :          0 :                 if (WARN_ON_ONCE(id > INT_MAX))
                   #  # ]
     207                 :            :                         break;
     208                 :          0 :                 ret = fn(id, rcu_dereference_raw(*slot), data);
     209         [ #  # ]:          0 :                 if (ret)
     210                 :          0 :                         return ret;
     211                 :            :         }
     212                 :            : 
     213                 :            :         return 0;
     214                 :            : }
     215                 :            : EXPORT_SYMBOL(idr_for_each);
     216                 :            : 
     217                 :            : /**
     218                 :            :  * idr_get_next_ul() - Find next populated entry.
     219                 :            :  * @idr: IDR handle.
     220                 :            :  * @nextid: Pointer to an ID.
     221                 :            :  *
     222                 :            :  * Returns the next populated entry in the tree with an ID greater than
     223                 :            :  * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
     224                 :            :  * to the ID of the found value.  To use in a loop, the value pointed to by
     225                 :            :  * nextid must be incremented by the user.
     226                 :            :  */
     227                 :      14283 : void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
     228                 :            : {
     229                 :            :         struct radix_tree_iter iter;
     230                 :            :         void __rcu **slot;
     231                 :            :         void *entry = NULL;
     232                 :      14283 :         unsigned long base = idr->idr_base;
     233                 :      14283 :         unsigned long id = *nextid;
     234                 :            : 
     235         [ +  - ]:      14283 :         id = (id < base) ? 0 : id - base;
     236   [ -  +  +  + ]:      28566 :         radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, id) {
     237                 :            :                 entry = rcu_dereference_raw(*slot);
     238         [ -  + ]:      12213 :                 if (!entry)
     239                 :          0 :                         continue;
     240         [ -  + ]:      12213 :                 if (!xa_is_internal(entry))
     241                 :            :                         break;
     242   [ #  #  #  # ]:          0 :                 if (slot != &idr->idr_rt.xa_head && !xa_is_retry(entry))
     243                 :            :                         break;
     244                 :            :                 slot = radix_tree_iter_retry(&iter);
     245                 :            :         }
     246         [ +  + ]:      14283 :         if (!slot)
     247                 :            :                 return NULL;
     248                 :            : 
     249                 :      12213 :         *nextid = iter.index + base;
     250                 :      12213 :         return entry;
     251                 :            : }
     252                 :            : EXPORT_SYMBOL(idr_get_next_ul);
     253                 :            : 
     254                 :            : /**
     255                 :            :  * idr_get_next() - Find next populated entry.
     256                 :            :  * @idr: IDR handle.
     257                 :            :  * @nextid: Pointer to an ID.
     258                 :            :  *
     259                 :            :  * Returns the next populated entry in the tree with an ID greater than
     260                 :            :  * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
     261                 :            :  * to the ID of the found value.  To use in a loop, the value pointed to by
     262                 :            :  * nextid must be incremented by the user.
     263                 :            :  */
     264                 :      14283 : void *idr_get_next(struct idr *idr, int *nextid)
     265                 :            : {
     266                 :      14283 :         unsigned long id = *nextid;
     267                 :      14283 :         void *entry = idr_get_next_ul(idr, &id);
     268                 :            : 
     269   [ -  +  #  #  :      14283 :         if (WARN_ON_ONCE(id > INT_MAX))
                   +  - ]
     270                 :            :                 return NULL;
     271                 :      14283 :         *nextid = id;
     272                 :      14283 :         return entry;
     273                 :            : }
     274                 :            : EXPORT_SYMBOL(idr_get_next);
     275                 :            : 
     276                 :            : /**
     277                 :            :  * idr_replace() - replace pointer for given ID.
     278                 :            :  * @idr: IDR handle.
     279                 :            :  * @ptr: New pointer to associate with the ID.
     280                 :            :  * @id: ID to change.
     281                 :            :  *
     282                 :            :  * Replace the pointer registered with an ID and return the old value.
     283                 :            :  * This function can be called under the RCU read lock concurrently with
     284                 :            :  * idr_alloc() and idr_remove() (as long as the ID being removed is not
     285                 :            :  * the one being replaced!).
     286                 :            :  *
     287                 :            :  * Returns: the old value on success.  %-ENOENT indicates that @id was not
     288                 :            :  * found.  %-EINVAL indicates that @ptr was not valid.
     289                 :            :  */
     290                 :    1045736 : void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
     291                 :            : {
     292                 :            :         struct radix_tree_node *node;
     293                 :    1045736 :         void __rcu **slot = NULL;
     294                 :            :         void *entry;
     295                 :            : 
     296                 :    1045736 :         id -= idr->idr_base;
     297                 :            : 
     298                 :    1045736 :         entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
     299   [ +  +  +  + ]:    1045736 :         if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
     300                 :            :                 return ERR_PTR(-ENOENT);
     301                 :            : 
     302                 :    1045731 :         __radix_tree_replace(&idr->idr_rt, node, slot, ptr);
     303                 :            : 
     304                 :    1045736 :         return entry;
     305                 :            : }
     306                 :            : EXPORT_SYMBOL(idr_replace);
     307                 :            : 
     308                 :            : /**
     309                 :            :  * DOC: IDA description
     310                 :            :  *
     311                 :            :  * The IDA is an ID allocator which does not provide the ability to
     312                 :            :  * associate an ID with a pointer.  As such, it only needs to store one
     313                 :            :  * bit per ID, and so is more space efficient than an IDR.  To use an IDA,
     314                 :            :  * define it using DEFINE_IDA() (or embed a &struct ida in a data structure,
     315                 :            :  * then initialise it using ida_init()).  To allocate a new ID, call
     316                 :            :  * ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range().
     317                 :            :  * To free an ID, call ida_free().
     318                 :            :  *
     319                 :            :  * ida_destroy() can be used to dispose of an IDA without needing to
     320                 :            :  * free the individual IDs in it.  You can use ida_is_empty() to find
     321                 :            :  * out whether the IDA has any IDs currently allocated.
     322                 :            :  *
     323                 :            :  * The IDA handles its own locking.  It is safe to call any of the IDA
     324                 :            :  * functions without synchronisation in your code.
     325                 :            :  *
     326                 :            :  * IDs are currently limited to the range [0-INT_MAX].  If this is an awkward
     327                 :            :  * limitation, it should be quite straightforward to raise the maximum.
     328                 :            :  */
     329                 :            : 
     330                 :            : /*
     331                 :            :  * Developer's notes:
     332                 :            :  *
     333                 :            :  * The IDA uses the functionality provided by the XArray to store bitmaps in
     334                 :            :  * each entry.  The XA_FREE_MARK is only cleared when all bits in the bitmap
     335                 :            :  * have been set.
     336                 :            :  *
     337                 :            :  * I considered telling the XArray that each slot is an order-10 node
     338                 :            :  * and indexing by bit number, but the XArray can't allow a single multi-index
     339                 :            :  * entry in the head, which would significantly increase memory consumption
     340                 :            :  * for the IDA.  So instead we divide the index by the number of bits in the
     341                 :            :  * leaf bitmap before doing a radix tree lookup.
     342                 :            :  *
     343                 :            :  * As an optimisation, if there are only a few low bits set in any given
     344                 :            :  * leaf, instead of allocating a 128-byte bitmap, we store the bits
     345                 :            :  * as a value entry.  Value entries never have the XA_FREE_MARK cleared
     346                 :            :  * because we can always convert them into a bitmap entry.
     347                 :            :  *
     348                 :            :  * It would be possible to optimise further; once we've run out of a
     349                 :            :  * single 128-byte bitmap, we currently switch to a 576-byte node, put
     350                 :            :  * the 128-byte bitmap in the first entry and then start allocating extra
     351                 :            :  * 128-byte entries.  We could instead use the 512 bytes of the node's
     352                 :            :  * data as a bitmap before moving to that scheme.  I do not believe this
     353                 :            :  * is a worthwhile optimisation; Rasmus Villemoes surveyed the current
     354                 :            :  * users of the IDA and almost none of them use more than 1024 entries.
     355                 :            :  * Those that do use more than the 8192 IDs that the 512 bytes would
     356                 :            :  * provide.
     357                 :            :  *
     358                 :            :  * The IDA always uses a lock to alloc/free.  If we add a 'test_bit'
     359                 :            :  * equivalent, it will still need locking.  Going to RCU lookup would require
     360                 :            :  * using RCU to free bitmaps, and that's not trivial without embedding an
     361                 :            :  * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte
     362                 :            :  * bitmap, which is excessive.
     363                 :            :  */
     364                 :            : 
     365                 :            : /**
     366                 :            :  * ida_alloc_range() - Allocate an unused ID.
     367                 :            :  * @ida: IDA handle.
     368                 :            :  * @min: Lowest ID to allocate.
     369                 :            :  * @max: Highest ID to allocate.
     370                 :            :  * @gfp: Memory allocation flags.
     371                 :            :  *
     372                 :            :  * Allocate an ID between @min and @max, inclusive.  The allocated ID will
     373                 :            :  * not exceed %INT_MAX, even if @max is larger.
     374                 :            :  *
     375                 :            :  * Context: Any context.
     376                 :            :  * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
     377                 :            :  * or %-ENOSPC if there are no free IDs.
     378                 :            :  */
     379                 :     441409 : int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
     380                 :            :                         gfp_t gfp)
     381                 :            : {
     382                 :     441409 :         XA_STATE(xas, &ida->xa, min / IDA_BITMAP_BITS);
     383                 :     441409 :         unsigned bit = min % IDA_BITMAP_BITS;
     384                 :            :         unsigned long flags;
     385                 :            :         struct ida_bitmap *bitmap, *alloc = NULL;
     386                 :            : 
     387         [ +  + ]:     441409 :         if ((int)min < 0)
     388                 :            :                 return -ENOSPC;
     389                 :            : 
     390         [ +  + ]:     441408 :         if ((int)max < 0)
     391                 :            :                 max = INT_MAX;
     392                 :            : 
     393                 :            : retry:
     394                 :     882816 :         xas_lock_irqsave(&xas, flags);
     395                 :            : next:
     396                 :     441411 :         bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK);
     397         [ +  + ]:     441411 :         if (xas.xa_index > min / IDA_BITMAP_BITS)
     398                 :            :                 bit = 0;
     399         [ +  - ]:     441411 :         if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
     400                 :            :                 goto nospc;
     401                 :            : 
     402         [ +  + ]:     441411 :         if (xa_is_value(bitmap)) {
     403                 :      58467 :                 unsigned long tmp = xa_to_value(bitmap);
     404                 :            : 
     405         [ +  + ]:      58467 :                 if (bit < BITS_PER_XA_VALUE) {
     406                 :      58466 :                         bit = find_next_zero_bit(&tmp, BITS_PER_XA_VALUE, bit);
     407         [ +  - ]:      58467 :                         if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
     408                 :            :                                 goto nospc;
     409         [ +  + ]:      58467 :                         if (bit < BITS_PER_XA_VALUE) {
     410                 :      57223 :                                 tmp |= 1UL << bit;
     411                 :      57223 :                                 xas_store(&xas, xa_mk_value(tmp));
     412                 :      57215 :                                 goto out;
     413                 :            :                         }
     414                 :            :                 }
     415                 :            :                 bitmap = alloc;
     416         [ +  + ]:       1245 :                 if (!bitmap)
     417                 :       1242 :                         bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);
     418         [ +  - ]:       1242 :                 if (!bitmap)
     419                 :            :                         goto alloc;
     420                 :       1242 :                 bitmap->bitmap[0] = tmp;
     421                 :       1242 :                 xas_store(&xas, bitmap);
     422         [ +  + ]:       1112 :                 if (xas_error(&xas)) {
     423                 :          3 :                         bitmap->bitmap[0] = 0;
     424                 :          3 :                         goto out;
     425                 :            :                 }
     426                 :            :         }
     427                 :            : 
     428         [ +  + ]:     384186 :         if (bitmap) {
     429                 :     377769 :                 bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);
     430         [ +  - ]:     377769 :                 if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
     431                 :            :                         goto nospc;
     432         [ -  + ]:     377769 :                 if (bit == IDA_BITMAP_BITS)
     433                 :            :                         goto next;
     434                 :            : 
     435                 :     377769 :                 __set_bit(bit, bitmap->bitmap);
     436         [ +  + ]:     377769 :                 if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
     437                 :        207 :                         xas_clear_mark(&xas, XA_FREE_MARK);
     438                 :            :         } else {
     439         [ +  + ]:       6417 :                 if (bit < BITS_PER_XA_VALUE) {
     440                 :       6210 :                         bitmap = xa_mk_value(1UL << bit);
     441                 :            :                 } else {
     442                 :            :                         bitmap = alloc;
     443         [ +  - ]:        207 :                         if (!bitmap)
     444                 :        207 :                                 bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);
     445         [ +  - ]:        207 :                         if (!bitmap)
     446                 :            :                                 goto alloc;
     447                 :        207 :                         __set_bit(bit, bitmap->bitmap);
     448                 :            :                 }
     449                 :       6417 :                 xas_store(&xas, bitmap);
     450                 :            :         }
     451                 :            : out:
     452                 :     441271 :         xas_unlock_irqrestore(&xas, flags);
     453         [ -  + ]:     441410 :         if (xas_nomem(&xas, gfp)) {
     454                 :          0 :                 xas.xa_index = min / IDA_BITMAP_BITS;
     455                 :            :                 bit = min % IDA_BITMAP_BITS;
     456                 :          0 :                 goto retry;
     457                 :            :         }
     458         [ +  + ]:     441346 :         if (bitmap != alloc)
     459                 :     441382 :                 kfree(alloc);
     460         [ -  + ]:     441404 :         if (xas_error(&xas))
     461                 :          0 :                 return xas_error(&xas);
     462                 :     441404 :         return xas.xa_index * IDA_BITMAP_BITS + bit;
     463                 :            : alloc:
     464                 :          0 :         xas_unlock_irqrestore(&xas, flags);
     465                 :          0 :         alloc = kzalloc(sizeof(*bitmap), gfp);
     466         [ #  # ]:          0 :         if (!alloc)
     467                 :            :                 return -ENOMEM;
     468                 :            :         xas_set(&xas, min / IDA_BITMAP_BITS);
     469                 :            :         bit = min % IDA_BITMAP_BITS;
     470                 :          0 :         goto retry;
     471                 :            : nospc:
     472                 :          0 :         xas_unlock_irqrestore(&xas, flags);
     473                 :          0 :         return -ENOSPC;
     474                 :            : }
     475                 :            : EXPORT_SYMBOL(ida_alloc_range);
     476                 :            : 
     477                 :            : /**
     478                 :            :  * ida_free() - Release an allocated ID.
     479                 :            :  * @ida: IDA handle.
     480                 :            :  * @id: Previously allocated ID.
     481                 :            :  *
     482                 :            :  * Context: Any context.
     483                 :            :  */
     484                 :      39683 : void ida_free(struct ida *ida, unsigned int id)
     485                 :            : {
     486                 :      39683 :         XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS);
     487                 :      39683 :         unsigned bit = id % IDA_BITMAP_BITS;
     488                 :            :         struct ida_bitmap *bitmap;
     489                 :            :         unsigned long flags;
     490                 :            : 
     491         [ -  + ]:      39683 :         BUG_ON((int)id < 0);
     492                 :            : 
     493                 :      39683 :         xas_lock_irqsave(&xas, flags);
     494                 :      39685 :         bitmap = xas_load(&xas);
     495                 :            : 
     496         [ +  + ]:      39685 :         if (xa_is_value(bitmap)) {
     497                 :            :                 unsigned long v = xa_to_value(bitmap);
     498         [ +  - ]:       7390 :                 if (bit >= BITS_PER_XA_VALUE)
     499                 :            :                         goto err;
     500         [ +  - ]:       7390 :                 if (!(v & (1UL << bit)))
     501                 :            :                         goto err;
     502                 :       7390 :                 v &= ~(1UL << bit);
     503         [ +  + ]:       7390 :                 if (!v)
     504                 :            :                         goto delete;
     505                 :       6769 :                 xas_store(&xas, xa_mk_value(v));
     506                 :            :         } else {
     507         [ +  - ]:      64590 :                 if (!test_bit(bit, bitmap->bitmap))
     508                 :            :                         goto err;
     509                 :            :                 __clear_bit(bit, bitmap->bitmap);
     510                 :      32295 :                 xas_set_mark(&xas, XA_FREE_MARK);
     511         [ -  + ]:      32295 :                 if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
     512                 :          0 :                         kfree(bitmap);
     513                 :            : delete:
     514                 :        621 :                         xas_store(&xas, NULL);
     515                 :            :                 }
     516                 :            :         }
     517                 :      39685 :         xas_unlock_irqrestore(&xas, flags);
     518                 :      79370 :         return;
     519                 :            :  err:
     520                 :          0 :         xas_unlock_irqrestore(&xas, flags);
     521                 :          0 :         WARN(1, "ida_free called for id=%d which is not allocated.\n", id);
     522                 :            : }
     523                 :            : EXPORT_SYMBOL(ida_free);
     524                 :            : 
     525                 :            : /**
     526                 :            :  * ida_destroy() - Free all IDs.
     527                 :            :  * @ida: IDA handle.
     528                 :            :  *
     529                 :            :  * Calling this function frees all IDs and releases all resources used
     530                 :            :  * by an IDA.  When this call returns, the IDA is empty and can be reused
     531                 :            :  * or freed.  If the IDA is already empty, there is no need to call this
     532                 :            :  * function.
     533                 :            :  *
     534                 :            :  * Context: Any context.
     535                 :            :  */
     536                 :          0 : void ida_destroy(struct ida *ida)
     537                 :            : {
     538                 :          0 :         XA_STATE(xas, &ida->xa, 0);
     539                 :            :         struct ida_bitmap *bitmap;
     540                 :            :         unsigned long flags;
     541                 :            : 
     542                 :          0 :         xas_lock_irqsave(&xas, flags);
     543         [ #  # ]:          0 :         xas_for_each(&xas, bitmap, ULONG_MAX) {
     544         [ #  # ]:          0 :                 if (!xa_is_value(bitmap))
     545                 :          0 :                         kfree(bitmap);
     546                 :          0 :                 xas_store(&xas, NULL);
     547                 :            :         }
     548                 :          0 :         xas_unlock_irqrestore(&xas, flags);
     549                 :          0 : }
     550                 :            : EXPORT_SYMBOL(ida_destroy);
     551                 :            : 
     552                 :            : #ifndef __KERNEL__
     553                 :            : extern void xa_dump_index(unsigned long index, unsigned int shift);
     554                 :            : #define IDA_CHUNK_SHIFT         ilog2(IDA_BITMAP_BITS)
     555                 :            : 
     556                 :            : static void ida_dump_entry(void *entry, unsigned long index)
     557                 :            : {
     558                 :            :         unsigned long i;
     559                 :            : 
     560                 :            :         if (!entry)
     561                 :            :                 return;
     562                 :            : 
     563                 :            :         if (xa_is_node(entry)) {
     564                 :            :                 struct xa_node *node = xa_to_node(entry);
     565                 :            :                 unsigned int shift = node->shift + IDA_CHUNK_SHIFT +
     566                 :            :                         XA_CHUNK_SHIFT;
     567                 :            : 
     568                 :            :                 xa_dump_index(index * IDA_BITMAP_BITS, shift);
     569                 :            :                 xa_dump_node(node);
     570                 :            :                 for (i = 0; i < XA_CHUNK_SIZE; i++)
     571                 :            :                         ida_dump_entry(node->slots[i],
     572                 :            :                                         index | (i << node->shift));
     573                 :            :         } else if (xa_is_value(entry)) {
     574                 :            :                 xa_dump_index(index * IDA_BITMAP_BITS, ilog2(BITS_PER_LONG));
     575                 :            :                 pr_cont("value: data %lx [%px]\n", xa_to_value(entry), entry);
     576                 :            :         } else {
     577                 :            :                 struct ida_bitmap *bitmap = entry;
     578                 :            : 
     579                 :            :                 xa_dump_index(index * IDA_BITMAP_BITS, IDA_CHUNK_SHIFT);
     580                 :            :                 pr_cont("bitmap: %p data", bitmap);
     581                 :            :                 for (i = 0; i < IDA_BITMAP_LONGS; i++)
     582                 :            :                         pr_cont(" %lx", bitmap->bitmap[i]);
     583                 :            :                 pr_cont("\n");
     584                 :            :         }
     585                 :            : }
     586                 :            : 
     587                 :            : static void ida_dump(struct ida *ida)
     588                 :            : {
     589                 :            :         struct xarray *xa = &ida->xa;
     590                 :            :         pr_debug("ida: %p node %p free %d\n", ida, xa->xa_head,
     591                 :            :                                 xa->xa_flags >> ROOT_TAG_SHIFT);
     592                 :            :         ida_dump_entry(xa->xa_head, 0);
     593                 :            : }
     594                 :            : #endif

Generated by: LCOV version 1.14