Branch data     Line data    Source code

       1                 :            : 
       2                 :            : #include <linux/export.h>
       3                 :            : #include <linux/generic-radix-tree.h>
       4                 :            : #include <linux/gfp.h>
       5                 :            : #include <linux/kmemleak.h>
       6                 :            : 
       7                 :            : #define GENRADIX_ARY            (PAGE_SIZE / sizeof(struct genradix_node *))
       8                 :            : #define GENRADIX_ARY_SHIFT      ilog2(GENRADIX_ARY)
       9                 :            : 
      10                 :            : struct genradix_node {
      11                 :            :         union {
      12                 :            :                 /* Interior node: */
      13                 :            :                 struct genradix_node    *children[GENRADIX_ARY];
      14                 :            : 
      15                 :            :                 /* Leaf: */
      16                 :            :                 u8                      data[PAGE_SIZE];
      17                 :            :         };
      18                 :            : };
      19                 :            : 
      20                 :            : static inline int genradix_depth_shift(unsigned depth)
      21                 :            : {
      22                 :          0 :         return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
      23                 :            : }
      24                 :            : 
      25                 :            : /*
      26                 :            :  * Returns size (of data, in bytes) that a tree of a given depth holds:
      27                 :            :  */
      28                 :            : static inline size_t genradix_depth_size(unsigned depth)
      29                 :            : {
      30                 :          0 :         return 1UL << genradix_depth_shift(depth);
      31                 :            : }
      32                 :            : 
      33                 :            : /* depth that's needed for a genradix that can address up to ULONG_MAX: */
      34                 :            : #define GENRADIX_MAX_DEPTH      \
      35                 :            :         DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
      36                 :            : 
      37                 :            : #define GENRADIX_DEPTH_MASK                             \
      38                 :            :         ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
      39                 :            : 
      40                 :            : static inline unsigned genradix_root_to_depth(struct genradix_root *r)
      41                 :            : {
      42                 :          0 :         return (unsigned long) r & GENRADIX_DEPTH_MASK;
      43                 :            : }
      44                 :            : 
      45                 :            : static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r)
      46                 :            : {
      47                 :          0 :         return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
      48                 :            : }
      49                 :            : 
      50                 :            : /*
      51                 :            :  * Returns pointer to the specified byte @offset within @radix, or NULL if not
      52                 :            :  * allocated
      53                 :            :  */
      54                 :          0 : void *__genradix_ptr(struct __genradix *radix, size_t offset)
      55                 :            : {
      56                 :            :         struct genradix_root *r = READ_ONCE(radix->root);
      57                 :            :         struct genradix_node *n = genradix_root_to_node(r);
      58                 :            :         unsigned level          = genradix_root_to_depth(r);
      59                 :            : 
      60                 :          0 :         if (ilog2(offset) >= genradix_depth_shift(level))
      61                 :            :                 return NULL;
      62                 :            : 
      63                 :            :         while (1) {
      64                 :          0 :                 if (!n)
      65                 :            :                         return NULL;
      66                 :          0 :                 if (!level)
      67                 :            :                         break;
      68                 :            : 
      69                 :          0 :                 level--;
      70                 :            : 
      71                 :          0 :                 n = n->children[offset >> genradix_depth_shift(level)];
      72                 :          0 :                 offset &= genradix_depth_size(level) - 1;
      73                 :          0 :         }
      74                 :            : 
      75                 :          0 :         return &n->data[offset];
      76                 :            : }
      77                 :            : EXPORT_SYMBOL(__genradix_ptr);
      78                 :            : 
      79                 :            : static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask)
      80                 :            : {
      81                 :            :         struct genradix_node *node;
      82                 :            : 
      83                 :          0 :         node = (struct genradix_node *)__get_free_page(gfp_mask|__GFP_ZERO);
      84                 :            : 
      85                 :            :         /*
      86                 :            :          * We're using pages (not slab allocations) directly for kernel data
      87                 :            :          * structures, so we need to explicitly inform kmemleak of them in order
      88                 :            :          * to avoid false positive memory leak reports.
      89                 :            :          */
      90                 :            :         kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask);
      91                 :            :         return node;
      92                 :            : }
      93                 :            : 
      94                 :            : static inline void genradix_free_node(struct genradix_node *node)
      95                 :            : {
      96                 :            :         kmemleak_free(node);
      97                 :          0 :         free_page((unsigned long)node);
      98                 :            : }
      99                 :            : 
     100                 :            : /*
     101                 :            :  * Returns pointer to the specified byte @offset within @radix, allocating it if
     102                 :            :  * necessary - newly allocated slots are always zeroed out:
     103                 :            :  */
     104                 :          0 : void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
     105                 :            :                            gfp_t gfp_mask)
     106                 :            : {
     107                 :          0 :         struct genradix_root *v = READ_ONCE(radix->root);
     108                 :            :         struct genradix_node *n, *new_node = NULL;
     109                 :            :         unsigned level;
     110                 :            : 
     111                 :            :         /* Increase tree depth if necessary: */
     112                 :            :         while (1) {
     113                 :            :                 struct genradix_root *r = v, *new_root;
     114                 :            : 
     115                 :            :                 n       = genradix_root_to_node(r);
     116                 :            :                 level   = genradix_root_to_depth(r);
     117                 :            : 
     118                 :          0 :                 if (n && ilog2(offset) < genradix_depth_shift(level))
     119                 :            :                         break;
     120                 :            : 
     121                 :          0 :                 if (!new_node) {
     122                 :            :                         new_node = genradix_alloc_node(gfp_mask);
     123                 :          0 :                         if (!new_node)
     124                 :            :                                 return NULL;
     125                 :            :                 }
     126                 :            : 
     127                 :          0 :                 new_node->children[0] = n;
     128                 :          0 :                 new_root = ((struct genradix_root *)
     129                 :          0 :                             ((unsigned long) new_node | (n ? level + 1 : 0)));
     130                 :            : 
     131                 :          0 :                 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
     132                 :            :                         v = new_root;
     133                 :            :                         new_node = NULL;
     134                 :            :                 }
     135                 :            :         }
     136                 :            : 
     137                 :          0 :         while (level--) {
     138                 :          0 :                 struct genradix_node **p =
     139                 :          0 :                         &n->children[offset >> genradix_depth_shift(level)];
     140                 :          0 :                 offset &= genradix_depth_size(level) - 1;
     141                 :            : 
     142                 :          0 :                 n = READ_ONCE(*p);
     143                 :          0 :                 if (!n) {
     144                 :          0 :                         if (!new_node) {
     145                 :            :                                 new_node = genradix_alloc_node(gfp_mask);
     146                 :          0 :                                 if (!new_node)
     147                 :            :                                         return NULL;
     148                 :            :                         }
     149                 :            : 
     150                 :          0 :                         if (!(n = cmpxchg_release(p, NULL, new_node)))
     151                 :            :                                 swap(n, new_node);
     152                 :            :                 }
     153                 :            :         }
     154                 :            : 
     155                 :          0 :         if (new_node)
     156                 :            :                 genradix_free_node(new_node);
     157                 :            : 
     158                 :          0 :         return &n->data[offset];
     159                 :            : }
     160                 :            : EXPORT_SYMBOL(__genradix_ptr_alloc);
     161                 :            : 
     162                 :          0 : void *__genradix_iter_peek(struct genradix_iter *iter,
     163                 :            :                            struct __genradix *radix,
     164                 :            :                            size_t objs_per_page)
     165                 :            : {
     166                 :            :         struct genradix_root *r;
     167                 :            :         struct genradix_node *n;
     168                 :            :         unsigned level, i;
     169                 :            : restart:
     170                 :          0 :         r = READ_ONCE(radix->root);
     171                 :          0 :         if (!r)
     172                 :            :                 return NULL;
     173                 :            : 
     174                 :            :         n       = genradix_root_to_node(r);
     175                 :            :         level   = genradix_root_to_depth(r);
     176                 :            : 
     177                 :          0 :         if (ilog2(iter->offset) >= genradix_depth_shift(level))
     178                 :            :                 return NULL;
     179                 :            : 
     180                 :          0 :         while (level) {
     181                 :          0 :                 level--;
     182                 :            : 
     183                 :          0 :                 i = (iter->offset >> genradix_depth_shift(level)) &
     184                 :            :                         (GENRADIX_ARY - 1);
     185                 :            : 
     186                 :          0 :                 while (!n->children[i]) {
     187                 :          0 :                         i++;
     188                 :          0 :                         iter->offset = round_down(iter->offset +
     189                 :            :                                            genradix_depth_size(level),
     190                 :            :                                            genradix_depth_size(level));
     191                 :          0 :                         iter->pos = (iter->offset >> PAGE_SHIFT) *
     192                 :            :                                 objs_per_page;
     193                 :          0 :                         if (i == GENRADIX_ARY)
     194                 :            :                                 goto restart;
     195                 :            :                 }
     196                 :            : 
     197                 :          0 :                 n = n->children[i];
     198                 :            :         }
     199                 :            : 
     200                 :          0 :         return &n->data[iter->offset & (PAGE_SIZE - 1)];
     201                 :            : }
     202                 :            : EXPORT_SYMBOL(__genradix_iter_peek);
     203                 :            : 
     204                 :          0 : static void genradix_free_recurse(struct genradix_node *n, unsigned level)
     205                 :            : {
     206                 :          0 :         if (level) {
     207                 :            :                 unsigned i;
     208                 :            : 
     209                 :          0 :                 for (i = 0; i < GENRADIX_ARY; i++)
     210                 :          0 :                         if (n->children[i])
     211                 :          0 :                                 genradix_free_recurse(n->children[i], level - 1);
     212                 :            :         }
     213                 :            : 
     214                 :            :         genradix_free_node(n);
     215                 :          0 : }
     216                 :            : 
     217                 :          0 : int __genradix_prealloc(struct __genradix *radix, size_t size,
     218                 :            :                         gfp_t gfp_mask)
     219                 :            : {
     220                 :            :         size_t offset;
     221                 :            : 
     222                 :          0 :         for (offset = 0; offset < size; offset += PAGE_SIZE)
     223                 :          0 :                 if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
     224                 :            :                         return -ENOMEM;
     225                 :            : 
     226                 :            :         return 0;
     227                 :            : }
     228                 :            : EXPORT_SYMBOL(__genradix_prealloc);
     229                 :            : 
     230                 :          0 : void __genradix_free(struct __genradix *radix)
     231                 :            : {
     232                 :          0 :         struct genradix_root *r = xchg(&radix->root, NULL);
     233                 :            : 
     234                 :          0 :         genradix_free_recurse(genradix_root_to_node(r),
     235                 :            :                               genradix_root_to_depth(r));
     236                 :          0 : }
     237                 :            : EXPORT_SYMBOL(__genradix_free);