LCOV - code coverage report
Current view: top level - lib - btree.c (source / functions) Hit Total Coverage
Test: Real Lines: 3 253 1.2 %
Date: 2020-10-17 15:46:16 Functions: 0 31 0.0 %
Legend: Neither, QEMU, Real, Both Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : // SPDX-License-Identifier: GPL-2.0-only
       2                 :            : /*
       3                 :            :  * lib/btree.c  - Simple In-memory B+Tree
       4                 :            :  *
       5                 :            :  * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
       6                 :            :  * Bits and pieces stolen from Peter Zijlstra's code, which is
       7                 :            :  * Copyright 2007, Red Hat Inc. Peter Zijlstra
       8                 :            :  *
       9                 :            :  * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
      10                 :            :  *
      11                 :            :  * A relatively simple B+Tree implementation.  I have written it as a learning
      12                 :            :  * exercise to understand how B+Trees work.  Turned out to be useful as well.
      13                 :            :  *
      14                 :            :  * B+Trees can be used similar to Linux radix trees (which don't have anything
      15                 :            :  * in common with textbook radix trees, beware).  Prerequisite for them working
      16                 :            :  * well is that access to a random tree node is much faster than a large number
      17                 :            :  * of operations within each node.
      18                 :            :  *
      19                 :            :  * Disks have fulfilled the prerequisite for a long time.  More recently DRAM
      20                 :            :  * has gained similar properties, as memory access times, when measured in cpu
      21                 :            :  * cycles, have increased.  Cacheline sizes have increased as well, which also
      22                 :            :  * helps B+Trees.
      23                 :            :  *
      24                 :            :  * Compared to radix trees, B+Trees are more efficient when dealing with a
      25                 :            :  * sparsely populated address space.  Between 25% and 50% of the memory is
      26                 :            :  * occupied with valid pointers.  When densely populated, radix trees contain
      27                 :            :  * ~98% pointers - hard to beat.  Very sparse radix trees contain only ~2%
      28                 :            :  * pointers.
      29                 :            :  *
      30                 :            :  * This particular implementation stores pointers identified by a long value.
      31                 :            :  * Storing NULL pointers is illegal, lookup will return NULL when no entry
      32                 :            :  * was found.
      33                 :            :  *
      34                 :            :  * A tricks was used that is not commonly found in textbooks.  The lowest
      35                 :            :  * values are to the right, not to the left.  All used slots within a node
      36                 :            :  * are on the left, all unused slots contain NUL values.  Most operations
      37                 :            :  * simply loop once over all slots and terminate on the first NUL.
      38                 :            :  */
      39                 :            : 
      40                 :            : #include <linux/btree.h>
      41                 :            : #include <linux/cache.h>
      42                 :            : #include <linux/kernel.h>
      43                 :            : #include <linux/slab.h>
      44                 :            : #include <linux/module.h>
      45                 :            : 
      46                 :            : #define MAX(a, b) ((a) > (b) ? (a) : (b))
      47                 :            : #define NODESIZE MAX(L1_CACHE_BYTES, 128)
      48                 :            : 
      49                 :            : struct btree_geo {
      50                 :            :         int keylen;
      51                 :            :         int no_pairs;
      52                 :            :         int no_longs;
      53                 :            : };
      54                 :            : 
      55                 :            : struct btree_geo btree_geo32 = {
      56                 :            :         .keylen = 1,
      57                 :            :         .no_pairs = NODESIZE / sizeof(long) / 2,
      58                 :            :         .no_longs = NODESIZE / sizeof(long) / 2,
      59                 :            : };
      60                 :            : EXPORT_SYMBOL_GPL(btree_geo32);
      61                 :            : 
      62                 :            : #define LONG_PER_U64 (64 / BITS_PER_LONG)
      63                 :            : struct btree_geo btree_geo64 = {
      64                 :            :         .keylen = LONG_PER_U64,
      65                 :            :         .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
      66                 :            :         .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
      67                 :            : };
      68                 :            : EXPORT_SYMBOL_GPL(btree_geo64);
      69                 :            : 
      70                 :            : struct btree_geo btree_geo128 = {
      71                 :            :         .keylen = 2 * LONG_PER_U64,
      72                 :            :         .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
      73                 :            :         .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
      74                 :            : };
      75                 :            : EXPORT_SYMBOL_GPL(btree_geo128);
      76                 :            : 
      77                 :            : #define MAX_KEYLEN      (2 * LONG_PER_U64)
      78                 :            : 
      79                 :            : static struct kmem_cache *btree_cachep;
      80                 :            : 
      81                 :          0 : void *btree_alloc(gfp_t gfp_mask, void *pool_data)
      82                 :            : {
      83                 :          0 :         return kmem_cache_alloc(btree_cachep, gfp_mask);
      84                 :            : }
      85                 :            : EXPORT_SYMBOL_GPL(btree_alloc);
      86                 :            : 
      87                 :          0 : void btree_free(void *element, void *pool_data)
      88                 :            : {
      89                 :          0 :         kmem_cache_free(btree_cachep, element);
      90                 :          0 : }
      91                 :            : EXPORT_SYMBOL_GPL(btree_free);
      92                 :            : 
      93                 :          0 : static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
      94                 :            : {
      95                 :            :         unsigned long *node;
      96                 :            : 
      97                 :          0 :         node = mempool_alloc(head->mempool, gfp);
      98                 :          0 :         if (likely(node))
      99                 :          0 :                 memset(node, 0, NODESIZE);
     100                 :          0 :         return node;
     101                 :            : }
     102                 :            : 
     103                 :            : static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
     104                 :            : {
     105                 :            :         size_t i;
     106                 :            : 
     107                 :          0 :         for (i = 0; i < n; i++) {
     108                 :          0 :                 if (l1[i] < l2[i])
     109                 :            :                         return -1;
     110                 :          0 :                 if (l1[i] > l2[i])
     111                 :            :                         return 1;
     112                 :            :         }
     113                 :            :         return 0;
     114                 :            : }
     115                 :            : 
     116                 :            : static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
     117                 :            :                 size_t n)
     118                 :            : {
     119                 :            :         size_t i;
     120                 :            : 
     121                 :          0 :         for (i = 0; i < n; i++)
     122                 :          0 :                 dest[i] = src[i];
     123                 :            :         return dest;
     124                 :            : }
     125                 :            : 
     126                 :            : static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
     127                 :            : {
     128                 :            :         size_t i;
     129                 :            : 
     130                 :          0 :         for (i = 0; i < n; i++)
     131                 :          0 :                 s[i] = c;
     132                 :            :         return s;
     133                 :            : }
     134                 :            : 
     135                 :            : static void dec_key(struct btree_geo *geo, unsigned long *key)
     136                 :            : {
     137                 :            :         unsigned long val;
     138                 :            :         int i;
     139                 :            : 
     140                 :          0 :         for (i = geo->keylen - 1; i >= 0; i--) {
     141                 :          0 :                 val = key[i];
     142                 :          0 :                 key[i] = val - 1;
     143                 :          0 :                 if (val)
     144                 :            :                         break;
     145                 :            :         }
     146                 :            : }
     147                 :            : 
     148                 :            : static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
     149                 :            : {
     150                 :          0 :         return &node[n * geo->keylen];
     151                 :            : }
     152                 :            : 
     153                 :            : static void *bval(struct btree_geo *geo, unsigned long *node, int n)
     154                 :            : {
     155                 :          0 :         return (void *)node[geo->no_longs + n];
     156                 :            : }
     157                 :            : 
     158                 :            : static void setkey(struct btree_geo *geo, unsigned long *node, int n,
     159                 :            :                    unsigned long *key)
     160                 :            : {
     161                 :          0 :         longcpy(bkey(geo, node, n), key, geo->keylen);
     162                 :            : }
     163                 :            : 
     164                 :            : static void setval(struct btree_geo *geo, unsigned long *node, int n,
     165                 :            :                    void *val)
     166                 :            : {
     167                 :          0 :         node[geo->no_longs + n] = (unsigned long) val;
     168                 :            : }
     169                 :            : 
     170                 :            : static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
     171                 :            : {
     172                 :          0 :         longset(bkey(geo, node, n), 0, geo->keylen);
     173                 :          0 :         node[geo->no_longs + n] = 0;
     174                 :            : }
     175                 :            : 
     176                 :            : static inline void __btree_init(struct btree_head *head)
     177                 :            : {
     178                 :          0 :         head->node = NULL;
     179                 :          0 :         head->height = 0;
     180                 :            : }
     181                 :            : 
     182                 :          0 : void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
     183                 :            : {
     184                 :            :         __btree_init(head);
     185                 :          0 :         head->mempool = mempool;
     186                 :          0 : }
     187                 :            : EXPORT_SYMBOL_GPL(btree_init_mempool);
     188                 :            : 
     189                 :          0 : int btree_init(struct btree_head *head)
     190                 :            : {
     191                 :            :         __btree_init(head);
     192                 :          0 :         head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
     193                 :          0 :         if (!head->mempool)
     194                 :            :                 return -ENOMEM;
     195                 :          0 :         return 0;
     196                 :            : }
     197                 :            : EXPORT_SYMBOL_GPL(btree_init);
     198                 :            : 
     199                 :          0 : void btree_destroy(struct btree_head *head)
     200                 :            : {
     201                 :          0 :         mempool_free(head->node, head->mempool);
     202                 :          0 :         mempool_destroy(head->mempool);
     203                 :          0 :         head->mempool = NULL;
     204                 :          0 : }
     205                 :            : EXPORT_SYMBOL_GPL(btree_destroy);
     206                 :            : 
     207                 :          0 : void *btree_last(struct btree_head *head, struct btree_geo *geo,
     208                 :            :                  unsigned long *key)
     209                 :            : {
     210                 :          0 :         int height = head->height;
     211                 :          0 :         unsigned long *node = head->node;
     212                 :            : 
     213                 :          0 :         if (height == 0)
     214                 :            :                 return NULL;
     215                 :            : 
     216                 :          0 :         for ( ; height > 1; height--)
     217                 :            :                 node = bval(geo, node, 0);
     218                 :            : 
     219                 :          0 :         longcpy(key, bkey(geo, node, 0), geo->keylen);
     220                 :          0 :         return bval(geo, node, 0);
     221                 :            : }
     222                 :            : EXPORT_SYMBOL_GPL(btree_last);
     223                 :            : 
     224                 :            : static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
     225                 :            :                   unsigned long *key)
     226                 :            : {
     227                 :          0 :         return longcmp(bkey(geo, node, pos), key, geo->keylen);
     228                 :            : }
     229                 :            : 
     230                 :            : static int keyzero(struct btree_geo *geo, unsigned long *key)
     231                 :            : {
     232                 :            :         int i;
     233                 :            : 
     234                 :          0 :         for (i = 0; i < geo->keylen; i++)
     235                 :          0 :                 if (key[i])
     236                 :            :                         return 0;
     237                 :            : 
     238                 :            :         return 1;
     239                 :            : }
     240                 :            : 
     241                 :          0 : void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
     242                 :            :                 unsigned long *key)
     243                 :            : {
     244                 :          0 :         int i, height = head->height;
     245                 :          0 :         unsigned long *node = head->node;
     246                 :            : 
     247                 :          0 :         if (height == 0)
     248                 :            :                 return NULL;
     249                 :            : 
     250                 :          0 :         for ( ; height > 1; height--) {
     251                 :          0 :                 for (i = 0; i < geo->no_pairs; i++)
     252                 :          0 :                         if (keycmp(geo, node, i, key) <= 0)
     253                 :            :                                 break;
     254                 :          0 :                 if (i == geo->no_pairs)
     255                 :            :                         return NULL;
     256                 :            :                 node = bval(geo, node, i);
     257                 :          0 :                 if (!node)
     258                 :            :                         return NULL;
     259                 :            :         }
     260                 :            : 
     261                 :          0 :         if (!node)
     262                 :            :                 return NULL;
     263                 :            : 
     264                 :          0 :         for (i = 0; i < geo->no_pairs; i++)
     265                 :          0 :                 if (keycmp(geo, node, i, key) == 0)
     266                 :          0 :                         return bval(geo, node, i);
     267                 :            :         return NULL;
     268                 :            : }
     269                 :            : EXPORT_SYMBOL_GPL(btree_lookup);
     270                 :            : 
     271                 :          0 : int btree_update(struct btree_head *head, struct btree_geo *geo,
     272                 :            :                  unsigned long *key, void *val)
     273                 :            : {
     274                 :          0 :         int i, height = head->height;
     275                 :          0 :         unsigned long *node = head->node;
     276                 :            : 
     277                 :          0 :         if (height == 0)
     278                 :            :                 return -ENOENT;
     279                 :            : 
     280                 :          0 :         for ( ; height > 1; height--) {
     281                 :          0 :                 for (i = 0; i < geo->no_pairs; i++)
     282                 :          0 :                         if (keycmp(geo, node, i, key) <= 0)
     283                 :            :                                 break;
     284                 :          0 :                 if (i == geo->no_pairs)
     285                 :            :                         return -ENOENT;
     286                 :            :                 node = bval(geo, node, i);
     287                 :          0 :                 if (!node)
     288                 :            :                         return -ENOENT;
     289                 :            :         }
     290                 :            : 
     291                 :          0 :         if (!node)
     292                 :            :                 return -ENOENT;
     293                 :            : 
     294                 :          0 :         for (i = 0; i < geo->no_pairs; i++)
     295                 :          0 :                 if (keycmp(geo, node, i, key) == 0) {
     296                 :            :                         setval(geo, node, i, val);
     297                 :          0 :                         return 0;
     298                 :            :                 }
     299                 :            :         return -ENOENT;
     300                 :            : }
     301                 :            : EXPORT_SYMBOL_GPL(btree_update);
     302                 :            : 
     303                 :            : /*
     304                 :            :  * Usually this function is quite similar to normal lookup.  But the key of
     305                 :            :  * a parent node may be smaller than the smallest key of all its siblings.
     306                 :            :  * In such a case we cannot just return NULL, as we have only proven that no
     307                 :            :  * key smaller than __key, but larger than this parent key exists.
     308                 :            :  * So we set __key to the parent key and retry.  We have to use the smallest
     309                 :            :  * such parent key, which is the last parent key we encountered.
     310                 :            :  */
     311                 :          0 : void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
     312                 :            :                      unsigned long *__key)
     313                 :            : {
     314                 :            :         int i, height;
     315                 :            :         unsigned long *node, *oldnode;
     316                 :            :         unsigned long *retry_key = NULL, key[MAX_KEYLEN];
     317                 :            : 
     318                 :          0 :         if (keyzero(geo, __key))
     319                 :            :                 return NULL;
     320                 :            : 
     321                 :          0 :         if (head->height == 0)
     322                 :            :                 return NULL;
     323                 :          0 :         longcpy(key, __key, geo->keylen);
     324                 :            : retry:
     325                 :            :         dec_key(geo, key);
     326                 :            : 
     327                 :          0 :         node = head->node;
     328                 :          0 :         for (height = head->height ; height > 1; height--) {
     329                 :          0 :                 for (i = 0; i < geo->no_pairs; i++)
     330                 :          0 :                         if (keycmp(geo, node, i, key) <= 0)
     331                 :            :                                 break;
     332                 :          0 :                 if (i == geo->no_pairs)
     333                 :            :                         goto miss;
     334                 :            :                 oldnode = node;
     335                 :            :                 node = bval(geo, node, i);
     336                 :          0 :                 if (!node)
     337                 :            :                         goto miss;
     338                 :            :                 retry_key = bkey(geo, oldnode, i);
     339                 :            :         }
     340                 :            : 
     341                 :          0 :         if (!node)
     342                 :            :                 goto miss;
     343                 :            : 
     344                 :          0 :         for (i = 0; i < geo->no_pairs; i++) {
     345                 :          0 :                 if (keycmp(geo, node, i, key) <= 0) {
     346                 :          0 :                         if (bval(geo, node, i)) {
     347                 :            :                                 longcpy(__key, bkey(geo, node, i), geo->keylen);
     348                 :          0 :                                 return bval(geo, node, i);
     349                 :            :                         } else
     350                 :            :                                 goto miss;
     351                 :            :                 }
     352                 :            :         }
     353                 :            : miss:
     354                 :          0 :         if (retry_key) {
     355                 :            :                 longcpy(key, retry_key, geo->keylen);
     356                 :            :                 retry_key = NULL;
     357                 :            :                 goto retry;
     358                 :            :         }
     359                 :            :         return NULL;
     360                 :            : }
     361                 :            : EXPORT_SYMBOL_GPL(btree_get_prev);
     362                 :            : 
     363                 :          0 : static int getpos(struct btree_geo *geo, unsigned long *node,
     364                 :            :                 unsigned long *key)
     365                 :            : {
     366                 :            :         int i;
     367                 :            : 
     368                 :          0 :         for (i = 0; i < geo->no_pairs; i++) {
     369                 :          0 :                 if (keycmp(geo, node, i, key) <= 0)
     370                 :            :                         break;
     371                 :            :         }
     372                 :          0 :         return i;
     373                 :            : }
     374                 :            : 
     375                 :            : static int getfill(struct btree_geo *geo, unsigned long *node, int start)
     376                 :            : {
     377                 :            :         int i;
     378                 :            : 
     379                 :          0 :         for (i = start; i < geo->no_pairs; i++)
     380                 :          0 :                 if (!bval(geo, node, i))
     381                 :            :                         break;
     382                 :          0 :         return i;
     383                 :            : }
     384                 :            : 
     385                 :            : /*
     386                 :            :  * locate the correct leaf node in the btree
     387                 :            :  */
     388                 :          0 : static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
     389                 :            :                 unsigned long *key, int level)
     390                 :            : {
     391                 :          0 :         unsigned long *node = head->node;
     392                 :            :         int i, height;
     393                 :            : 
     394                 :          0 :         for (height = head->height; height > level; height--) {
     395                 :          0 :                 for (i = 0; i < geo->no_pairs; i++)
     396                 :          0 :                         if (keycmp(geo, node, i, key) <= 0)
     397                 :            :                                 break;
     398                 :            : 
     399                 :          0 :                 if ((i == geo->no_pairs) || !bval(geo, node, i)) {
     400                 :            :                         /* right-most key is too large, update it */
     401                 :            :                         /* FIXME: If the right-most key on higher levels is
     402                 :            :                          * always zero, this wouldn't be necessary. */
     403                 :          0 :                         i--;
     404                 :            :                         setkey(geo, node, i, key);
     405                 :            :                 }
     406                 :          0 :                 BUG_ON(i < 0);
     407                 :            :                 node = bval(geo, node, i);
     408                 :            :         }
     409                 :          0 :         BUG_ON(!node);
     410                 :          0 :         return node;
     411                 :            : }
     412                 :            : 
     413                 :          0 : static int btree_grow(struct btree_head *head, struct btree_geo *geo,
     414                 :            :                       gfp_t gfp)
     415                 :            : {
     416                 :            :         unsigned long *node;
     417                 :            :         int fill;
     418                 :            : 
     419                 :          0 :         node = btree_node_alloc(head, gfp);
     420                 :          0 :         if (!node)
     421                 :            :                 return -ENOMEM;
     422                 :          0 :         if (head->node) {
     423                 :            :                 fill = getfill(geo, head->node, 0);
     424                 :          0 :                 setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
     425                 :          0 :                 setval(geo, node, 0, head->node);
     426                 :            :         }
     427                 :          0 :         head->node = node;
     428                 :          0 :         head->height++;
     429                 :          0 :         return 0;
     430                 :            : }
     431                 :            : 
     432                 :          0 : static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
     433                 :            : {
     434                 :            :         unsigned long *node;
     435                 :            :         int fill;
     436                 :            : 
     437                 :          0 :         if (head->height <= 1)
     438                 :          0 :                 return;
     439                 :            : 
     440                 :          0 :         node = head->node;
     441                 :            :         fill = getfill(geo, node, 0);
     442                 :          0 :         BUG_ON(fill > 1);
     443                 :          0 :         head->node = bval(geo, node, 0);
     444                 :          0 :         head->height--;
     445                 :          0 :         mempool_free(node, head->mempool);
     446                 :            : }
     447                 :            : 
     448                 :          0 : static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
     449                 :            :                               unsigned long *key, void *val, int level,
     450                 :            :                               gfp_t gfp)
     451                 :            : {
     452                 :            :         unsigned long *node;
     453                 :            :         int i, pos, fill, err;
     454                 :            : 
     455                 :          0 :         BUG_ON(!val);
     456                 :          0 :         if (head->height < level) {
     457                 :          0 :                 err = btree_grow(head, geo, gfp);
     458                 :          0 :                 if (err)
     459                 :            :                         return err;
     460                 :            :         }
     461                 :            : 
     462                 :            : retry:
     463                 :          0 :         node = find_level(head, geo, key, level);
     464                 :          0 :         pos = getpos(geo, node, key);
     465                 :            :         fill = getfill(geo, node, pos);
     466                 :            :         /* two identical keys are not allowed */
     467                 :          0 :         BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
     468                 :            : 
     469                 :          0 :         if (fill == geo->no_pairs) {
     470                 :            :                 /* need to split node */
     471                 :            :                 unsigned long *new;
     472                 :            : 
     473                 :          0 :                 new = btree_node_alloc(head, gfp);
     474                 :          0 :                 if (!new)
     475                 :            :                         return -ENOMEM;
     476                 :          0 :                 err = btree_insert_level(head, geo,
     477                 :          0 :                                 bkey(geo, node, fill / 2 - 1),
     478                 :            :                                 new, level + 1, gfp);
     479                 :          0 :                 if (err) {
     480                 :          0 :                         mempool_free(new, head->mempool);
     481                 :          0 :                         return err;
     482                 :            :                 }
     483                 :          0 :                 for (i = 0; i < fill / 2; i++) {
     484                 :            :                         setkey(geo, new, i, bkey(geo, node, i));
     485                 :            :                         setval(geo, new, i, bval(geo, node, i));
     486                 :          0 :                         setkey(geo, node, i, bkey(geo, node, i + fill / 2));
     487                 :            :                         setval(geo, node, i, bval(geo, node, i + fill / 2));
     488                 :            :                         clearpair(geo, node, i + fill / 2);
     489                 :            :                 }
     490                 :          0 :                 if (fill & 1) {
     491                 :          0 :                         setkey(geo, node, i, bkey(geo, node, fill - 1));
     492                 :            :                         setval(geo, node, i, bval(geo, node, fill - 1));
     493                 :            :                         clearpair(geo, node, fill - 1);
     494                 :            :                 }
     495                 :            :                 goto retry;
     496                 :            :         }
     497                 :          0 :         BUG_ON(fill >= geo->no_pairs);
     498                 :            : 
     499                 :            :         /* shift and insert */
     500                 :          0 :         for (i = fill; i > pos; i--) {
     501                 :          0 :                 setkey(geo, node, i, bkey(geo, node, i - 1));
     502                 :            :                 setval(geo, node, i, bval(geo, node, i - 1));
     503                 :            :         }
     504                 :            :         setkey(geo, node, pos, key);
     505                 :            :         setval(geo, node, pos, val);
     506                 :            : 
     507                 :          0 :         return 0;
     508                 :            : }
     509                 :            : 
     510                 :          0 : int btree_insert(struct btree_head *head, struct btree_geo *geo,
     511                 :            :                 unsigned long *key, void *val, gfp_t gfp)
     512                 :            : {
     513                 :          0 :         BUG_ON(!val);
     514                 :          0 :         return btree_insert_level(head, geo, key, val, 1, gfp);
     515                 :            : }
     516                 :            : EXPORT_SYMBOL_GPL(btree_insert);
     517                 :            : 
     518                 :            : static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
     519                 :            :                 unsigned long *key, int level);
     520                 :          0 : static void merge(struct btree_head *head, struct btree_geo *geo, int level,
     521                 :            :                 unsigned long *left, int lfill,
     522                 :            :                 unsigned long *right, int rfill,
     523                 :            :                 unsigned long *parent, int lpos)
     524                 :            : {
     525                 :            :         int i;
     526                 :            : 
     527                 :          0 :         for (i = 0; i < rfill; i++) {
     528                 :            :                 /* Move all keys to the left */
     529                 :          0 :                 setkey(geo, left, lfill + i, bkey(geo, right, i));
     530                 :            :                 setval(geo, left, lfill + i, bval(geo, right, i));
     531                 :            :         }
     532                 :            :         /* Exchange left and right child in parent */
     533                 :            :         setval(geo, parent, lpos, right);
     534                 :          0 :         setval(geo, parent, lpos + 1, left);
     535                 :            :         /* Remove left (formerly right) child from parent */
     536                 :          0 :         btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
     537                 :          0 :         mempool_free(right, head->mempool);
     538                 :          0 : }
     539                 :            : 
     540                 :          0 : static void rebalance(struct btree_head *head, struct btree_geo *geo,
     541                 :            :                 unsigned long *key, int level, unsigned long *child, int fill)
     542                 :            : {
     543                 :            :         unsigned long *parent, *left = NULL, *right = NULL;
     544                 :            :         int i, no_left, no_right;
     545                 :            : 
     546                 :          0 :         if (fill == 0) {
     547                 :            :                 /* Because we don't steal entries from a neighbour, this case
     548                 :            :                  * can happen.  Parent node contains a single child, this
     549                 :            :                  * node, so merging with a sibling never happens.
     550                 :            :                  */
     551                 :          0 :                 btree_remove_level(head, geo, key, level + 1);
     552                 :          0 :                 mempool_free(child, head->mempool);
     553                 :          0 :                 return;
     554                 :            :         }
     555                 :            : 
     556                 :          0 :         parent = find_level(head, geo, key, level + 1);
     557                 :          0 :         i = getpos(geo, parent, key);
     558                 :          0 :         BUG_ON(bval(geo, parent, i) != child);
     559                 :            : 
     560                 :          0 :         if (i > 0) {
     561                 :          0 :                 left = bval(geo, parent, i - 1);
     562                 :            :                 no_left = getfill(geo, left, 0);
     563                 :          0 :                 if (fill + no_left <= geo->no_pairs) {
     564                 :          0 :                         merge(head, geo, level,
     565                 :            :                                         left, no_left,
     566                 :            :                                         child, fill,
     567                 :            :                                         parent, i - 1);
     568                 :          0 :                         return;
     569                 :            :                 }
     570                 :            :         }
     571                 :          0 :         if (i + 1 < getfill(geo, parent, i)) {
     572                 :            :                 right = bval(geo, parent, i + 1);
     573                 :            :                 no_right = getfill(geo, right, 0);
     574                 :          0 :                 if (fill + no_right <= geo->no_pairs) {
     575                 :          0 :                         merge(head, geo, level,
     576                 :            :                                         child, fill,
     577                 :            :                                         right, no_right,
     578                 :            :                                         parent, i);
     579                 :          0 :                         return;
     580                 :            :                 }
     581                 :            :         }
     582                 :            :         /*
     583                 :            :          * We could also try to steal one entry from the left or right
     584                 :            :          * neighbor.  By not doing so we changed the invariant from
     585                 :            :          * "all nodes are at least half full" to "no two neighboring
     586                 :            :          * nodes can be merged".  Which means that the average fill of
     587                 :            :          * all nodes is still half or better.
     588                 :            :          */
     589                 :            : }
     590                 :            : 
     591                 :          0 : static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
     592                 :            :                 unsigned long *key, int level)
     593                 :            : {
     594                 :            :         unsigned long *node;
     595                 :            :         int i, pos, fill;
     596                 :            :         void *ret;
     597                 :            : 
     598                 :          0 :         if (level > head->height) {
     599                 :            :                 /* we recursed all the way up */
     600                 :          0 :                 head->height = 0;
     601                 :          0 :                 head->node = NULL;
     602                 :          0 :                 return NULL;
     603                 :            :         }
     604                 :            : 
     605                 :          0 :         node = find_level(head, geo, key, level);
     606                 :          0 :         pos = getpos(geo, node, key);
     607                 :            :         fill = getfill(geo, node, pos);
     608                 :          0 :         if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
     609                 :            :                 return NULL;
     610                 :            :         ret = bval(geo, node, pos);
     611                 :            : 
     612                 :            :         /* remove and shift */
     613                 :          0 :         for (i = pos; i < fill - 1; i++) {
     614                 :          0 :                 setkey(geo, node, i, bkey(geo, node, i + 1));
     615                 :            :                 setval(geo, node, i, bval(geo, node, i + 1));
     616                 :            :         }
     617                 :          0 :         clearpair(geo, node, fill - 1);
     618                 :            : 
     619                 :          0 :         if (fill - 1 < geo->no_pairs / 2) {
     620                 :          0 :                 if (level < head->height)
     621                 :          0 :                         rebalance(head, geo, key, level, node, fill - 1);
     622                 :          0 :                 else if (fill - 1 == 1)
     623                 :          0 :                         btree_shrink(head, geo);
     624                 :            :         }
     625                 :            : 
     626                 :          0 :         return ret;
     627                 :            : }
     628                 :            : 
     629                 :          0 : void *btree_remove(struct btree_head *head, struct btree_geo *geo,
     630                 :            :                 unsigned long *key)
     631                 :            : {
     632                 :          0 :         if (head->height == 0)
     633                 :            :                 return NULL;
     634                 :            : 
     635                 :          0 :         return btree_remove_level(head, geo, key, 1);
     636                 :            : }
     637                 :            : EXPORT_SYMBOL_GPL(btree_remove);
     638                 :            : 
     639                 :          0 : int btree_merge(struct btree_head *target, struct btree_head *victim,
     640                 :            :                 struct btree_geo *geo, gfp_t gfp)
     641                 :            : {
     642                 :            :         unsigned long key[MAX_KEYLEN];
     643                 :            :         unsigned long dup[MAX_KEYLEN];
     644                 :            :         void *val;
     645                 :            :         int err;
     646                 :            : 
     647                 :          0 :         BUG_ON(target == victim);
     648                 :            : 
     649                 :          0 :         if (!(target->node)) {
     650                 :            :                 /* target is empty, just copy fields over */
     651                 :          0 :                 target->node = victim->node;
     652                 :          0 :                 target->height = victim->height;
     653                 :            :                 __btree_init(victim);
     654                 :          0 :                 return 0;
     655                 :            :         }
     656                 :            : 
     657                 :            :         /* TODO: This needs some optimizations.  Currently we do three tree
     658                 :            :          * walks to remove a single object from the victim.
     659                 :            :          */
     660                 :            :         for (;;) {
     661                 :          0 :                 if (!btree_last(victim, geo, key))
     662                 :            :                         break;
     663                 :          0 :                 val = btree_lookup(victim, geo, key);
     664                 :          0 :                 err = btree_insert(target, geo, key, val, gfp);
     665                 :          0 :                 if (err)
     666                 :          0 :                         return err;
     667                 :            :                 /* We must make a copy of the key, as the original will get
     668                 :            :                  * mangled inside btree_remove. */
     669                 :          0 :                 longcpy(dup, key, geo->keylen);
     670                 :            :                 btree_remove(victim, geo, dup);
     671                 :            :         }
     672                 :            :         return 0;
     673                 :            : }
     674                 :            : EXPORT_SYMBOL_GPL(btree_merge);
     675                 :            : 
     676                 :          0 : static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
     677                 :            :                                unsigned long *node, unsigned long opaque,
     678                 :            :                                void (*func)(void *elem, unsigned long opaque,
     679                 :            :                                             unsigned long *key, size_t index,
     680                 :            :                                             void *func2),
     681                 :            :                                void *func2, int reap, int height, size_t count)
     682                 :            : {
     683                 :            :         int i;
     684                 :            :         unsigned long *child;
     685                 :            : 
     686                 :          0 :         for (i = 0; i < geo->no_pairs; i++) {
     687                 :            :                 child = bval(geo, node, i);
     688                 :          0 :                 if (!child)
     689                 :            :                         break;
     690                 :          0 :                 if (height > 1)
     691                 :          0 :                         count = __btree_for_each(head, geo, child, opaque,
     692                 :            :                                         func, func2, reap, height - 1, count);
     693                 :            :                 else
     694                 :          0 :                         func(child, opaque, bkey(geo, node, i), count++,
     695                 :            :                                         func2);
     696                 :            :         }
     697                 :          0 :         if (reap)
     698                 :          0 :                 mempool_free(node, head->mempool);
     699                 :          0 :         return count;
     700                 :            : }
     701                 :            : 
     702                 :          0 : static void empty(void *elem, unsigned long opaque, unsigned long *key,
     703                 :            :                   size_t index, void *func2)
     704                 :            : {
     705                 :          0 : }
     706                 :            : 
     707                 :          0 : void visitorl(void *elem, unsigned long opaque, unsigned long *key,
     708                 :            :               size_t index, void *__func)
     709                 :            : {
     710                 :          0 :         visitorl_t func = __func;
     711                 :            : 
     712                 :          0 :         func(elem, opaque, *key, index);
     713                 :          0 : }
     714                 :            : EXPORT_SYMBOL_GPL(visitorl);
     715                 :            : 
     716                 :          0 : void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
     717                 :            :                size_t index, void *__func)
     718                 :            : {
     719                 :          0 :         visitor32_t func = __func;
     720                 :            :         u32 *key = (void *)__key;
     721                 :            : 
     722                 :          0 :         func(elem, opaque, *key, index);
     723                 :          0 : }
     724                 :            : EXPORT_SYMBOL_GPL(visitor32);
     725                 :            : 
     726                 :          0 : void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
     727                 :            :                size_t index, void *__func)
     728                 :            : {
     729                 :          0 :         visitor64_t func = __func;
     730                 :            :         u64 *key = (void *)__key;
     731                 :            : 
     732                 :          0 :         func(elem, opaque, *key, index);
     733                 :          0 : }
     734                 :            : EXPORT_SYMBOL_GPL(visitor64);
     735                 :            : 
     736                 :          0 : void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
     737                 :            :                 size_t index, void *__func)
     738                 :            : {
     739                 :          0 :         visitor128_t func = __func;
     740                 :            :         u64 *key = (void *)__key;
     741                 :            : 
     742                 :          0 :         func(elem, opaque, key[0], key[1], index);
     743                 :          0 : }
     744                 :            : EXPORT_SYMBOL_GPL(visitor128);
     745                 :            : 
     746                 :          0 : size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
     747                 :            :                      unsigned long opaque,
     748                 :            :                      void (*func)(void *elem, unsigned long opaque,
     749                 :            :                                   unsigned long *key,
     750                 :            :                                   size_t index, void *func2),
     751                 :            :                      void *func2)
     752                 :            : {
     753                 :            :         size_t count = 0;
     754                 :            : 
     755                 :          0 :         if (!func2)
     756                 :            :                 func = empty;
     757                 :          0 :         if (head->node)
     758                 :          0 :                 count = __btree_for_each(head, geo, head->node, opaque, func,
     759                 :            :                                 func2, 0, head->height, 0);
     760                 :          0 :         return count;
     761                 :            : }
     762                 :            : EXPORT_SYMBOL_GPL(btree_visitor);
     763                 :            : 
     764                 :          0 : size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
     765                 :            :                           unsigned long opaque,
     766                 :            :                           void (*func)(void *elem, unsigned long opaque,
     767                 :            :                                        unsigned long *key,
     768                 :            :                                        size_t index, void *func2),
     769                 :            :                           void *func2)
     770                 :            : {
     771                 :            :         size_t count = 0;
     772                 :            : 
     773                 :          0 :         if (!func2)
     774                 :            :                 func = empty;
     775                 :          0 :         if (head->node)
     776                 :          0 :                 count = __btree_for_each(head, geo, head->node, opaque, func,
     777                 :            :                                 func2, 1, head->height, 0);
     778                 :            :         __btree_init(head);
     779                 :          0 :         return count;
     780                 :            : }
     781                 :            : EXPORT_SYMBOL_GPL(btree_grim_visitor);
     782                 :            : 
     783                 :          3 : static int __init btree_module_init(void)
     784                 :            : {
     785                 :          3 :         btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
     786                 :            :                         SLAB_HWCACHE_ALIGN, NULL);
     787                 :          3 :         return 0;
     788                 :            : }
     789                 :            : 
     790                 :          0 : static void __exit btree_module_exit(void)
     791                 :            : {
     792                 :          0 :         kmem_cache_destroy(btree_cachep);
     793                 :          0 : }
     794                 :            : 
     795                 :            : /* If core code starts using btree, initialization should happen even earlier */
     796                 :            : module_init(btree_module_init);
     797                 :            : module_exit(btree_module_exit);
     798                 :            : 
     799                 :            : MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
     800                 :            : MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
     801                 :            : MODULE_LICENSE("GPL");
    

Generated by: LCOV version 1.14