lustre/ptlrpc/heap.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 only,
   8  * as published by the Free Software Foundation.
   9
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License version 2 for more details.  A copy is
  14  * included in the COPYING file that accompanied this code.
  15
  16  * GPL HEADER END
  17  */
  18 /*
  19  * Copyright (c) 2011 Intel Corporation
  20  */
  21 /*
  22  * libcfs/libcfs/heap.c
  23  *
  24  * Author: Eric Barton  <eeb@whamcloud.com>
  25  *         Liang Zhen   <liang@whamcloud.com>
  26  */
  27 /** \addtogroup heap
  28  *
  29  * @{
  30  */
  31
  32 #define DEBUG_SUBSYSTEM S_LNET
  33
  34 #include <libcfs/libcfs.h>
  35 #include <lustre_net.h>
  36 #include "heap.h"
  37
  38 #define CBH_ALLOC(ptr, h)                                               \
  39 do {                                                                    \
  40         if (h->cbh_cptab) {                                             \
  41                 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)              \
  42                         LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab,       \
  43                                              h->cbh_cptid, CBH_NOB,     \
  44                                              GFP_ATOMIC);               \
  45                 else                                                    \
  46                         LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab,           \
  47                                          h->cbh_cptid, CBH_NOB);        \
  48         } else {                                                        \
  49                 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)              \
  50                         LIBCFS_ALLOC_ATOMIC((ptr), CBH_NOB);            \
  51                 else                                                    \
  52                         LIBCFS_ALLOC((ptr), CBH_NOB);                   \
  53         }                                                               \
  54 } while (0)
  55
  56 #define CBH_FREE(ptr)   LIBCFS_FREE(ptr, CBH_NOB)
  57
  58 /**
  59  * Grows the capacity of a binary heap so that it can handle a larger number of
  60  * \e struct cfs_binheap_node objects.
  61  *
  62  * \param[in] h The binary heap
  63  *
  64  * \retval 0       Successfully grew the heap
  65  * \retval -ENOMEM OOM error
  66  */
  67 static int
  68 cfs_binheap_grow(struct cfs_binheap *h)
  69 {
  70         struct cfs_binheap_node ***frag1 = NULL;
  71         struct cfs_binheap_node  **frag2;
  72         int hwm = h->cbh_hwm;
  73
  74         /* need a whole new chunk of pointers */
  75         LASSERT((h->cbh_hwm & CBH_MASK) == 0);
  76
  77         if (hwm == 0) {
  78                 /* first use of single indirect */
  79                 CBH_ALLOC(h->cbh_elements1, h);
  80                 if (h->cbh_elements1 == NULL)
  81                         return -ENOMEM;
  82
  83                 goto out;
  84         }
  85
  86         hwm -= CBH_SIZE;
  87         if (hwm < CBH_SIZE * CBH_SIZE) {
  88                 /* not filled double indirect */
  89                 CBH_ALLOC(frag2, h);
  90                 if (frag2 == NULL)
  91                         return -ENOMEM;
  92
  93                 if (hwm == 0) {
  94                         /* first use of double indirect */
  95                         CBH_ALLOC(h->cbh_elements2, h);
  96                         if (h->cbh_elements2 == NULL) {
  97                                 CBH_FREE(frag2);
  98                                 return -ENOMEM;
  99                         }
 100                 }
 101
 102                 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
 103                 goto out;
 104         }
 105
 106         hwm -= CBH_SIZE * CBH_SIZE;
 107 #if (CBH_SHIFT * 3 < 32)
 108         if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
 109                 /* filled triple indirect */
 110                 return -ENOMEM;
 111         }
 112 #endif
 113         CBH_ALLOC(frag2, h);
 114         if (frag2 == NULL)
 115                 return -ENOMEM;
 116
 117         if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
 118                 /* first use of this 2nd level index */
 119                 CBH_ALLOC(frag1, h);
 120                 if (frag1 == NULL) {
 121                         CBH_FREE(frag2);
 122                         return -ENOMEM;
 123                 }
 124         }
 125
 126         if (hwm == 0) {
 127                 /* first use of triple indirect */
 128                 CBH_ALLOC(h->cbh_elements3, h);
 129                 if (h->cbh_elements3 == NULL) {
 130                         CBH_FREE(frag2);
 131                         CBH_FREE(frag1);
 132                         return -ENOMEM;
 133                 }
 134         }
 135
 136         if (frag1 != NULL) {
 137                 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
 138                 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
 139         } else {
 140                 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
 141                 LASSERT(frag1 != NULL);
 142         }
 143
 144         frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
 145
 146  out:
 147         h->cbh_hwm += CBH_SIZE;
 148         return 0;
 149 }
 150
 151 /**
 152  * Creates and initializes a binary heap instance.
 153  *
 154  * \param[in] ops   The operations to be used
 155  * \param[in] flags The heap flags
 156  * \parm[in]  count The initial heap capacity in # of elements
 157  * \param[in] arg   An optional private argument
 158  * \param[in] cptab The CPT table this heap instance will operate over
 159  * \param[in] cptid The CPT id of \a cptab this heap instance will operate over
 160  *
 161  * \retval valid-pointer A newly-created and initialized binary heap object
 162  * \retval NULL          error
 163  */
 164 struct cfs_binheap *
 165 cfs_binheap_create(struct cfs_binheap_ops *ops, unsigned int flags,
 166                    unsigned int count, void *arg, struct cfs_cpt_table *cptab,
 167                    int cptid)
 168 {
 169         struct cfs_binheap *h;
 170
 171         LASSERT(ops != NULL);
 172         LASSERT(ops->hop_compare != NULL);
 173         if (cptab) {
 174                 LASSERT(cptid == CFS_CPT_ANY ||
 175                        (cptid >= 0 && cptid < cfs_cpt_number(cptab)));
 176                 LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
 177         } else {
 178                 LIBCFS_ALLOC(h, sizeof(*h));
 179         }
 180         if (!h)
 181                 return NULL;
 182
 183         h->cbh_ops        = ops;
 184         h->cbh_nelements  = 0;
 185         h->cbh_hwm        = 0;
 186         h->cbh_private    = arg;
 187         h->cbh_flags      = flags & (~CBH_FLAG_ATOMIC_GROW);
 188         h->cbh_cptab      = cptab;
 189         h->cbh_cptid      = cptid;
 190
 191         while (h->cbh_hwm < count) { /* preallocate */
 192                 if (cfs_binheap_grow(h) != 0) {
 193                         cfs_binheap_destroy(h);
 194                         return NULL;
 195                 }
 196         }
 197
 198         h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
 199
 200         return h;
 201 }
 202 EXPORT_SYMBOL(cfs_binheap_create);
 203
 204 /**
 205  * Releases all resources associated with a binary heap instance.
 206  *
 207  * Deallocates memory for all indirection levels and the binary heap object
 208  * itself.
 209  *
 210  * \param[in] h The binary heap object
 211  */
 212 void
 213 cfs_binheap_destroy(struct cfs_binheap *h)
 214 {
 215         int idx0;
 216         int idx1;
 217         int n;
 218
 219         LASSERT(h != NULL);
 220
 221         n = h->cbh_hwm;
 222
 223         if (n > 0) {
 224                 CBH_FREE(h->cbh_elements1);
 225                 n -= CBH_SIZE;
 226         }
 227
 228         if (n > 0) {
 229                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 230                         CBH_FREE(h->cbh_elements2[idx0]);
 231                         n -= CBH_SIZE;
 232                 }
 233
 234                 CBH_FREE(h->cbh_elements2);
 235         }
 236
 237         if (n > 0) {
 238                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 239
 240                         for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
 241                                 CBH_FREE(h->cbh_elements3[idx0][idx1]);
 242                                 n -= CBH_SIZE;
 243                         }
 244
 245                         CBH_FREE(h->cbh_elements3[idx0]);
 246                 }
 247
 248                 CBH_FREE(h->cbh_elements3);
 249         }
 250
 251         LIBCFS_FREE(h, sizeof(*h));
 252 }
 253 EXPORT_SYMBOL(cfs_binheap_destroy);
 254
 255 /**
 256  * Obtains a double pointer to a heap element, given its index into the binary
 257  * tree.
 258  *
 259  * \param[in] h   The binary heap instance
 260  * \param[in] idx The requested node's index
 261  *
 262  * \retval valid-pointer A double pointer to a heap pointer entry
 263  */
 264 static struct cfs_binheap_node **
 265 cfs_binheap_pointer(struct cfs_binheap *h, unsigned int idx)
 266 {
 267         if (idx < CBH_SIZE)
 268                 return &(h->cbh_elements1[idx]);
 269
 270         idx -= CBH_SIZE;
 271         if (idx < CBH_SIZE * CBH_SIZE)
 272                 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
 273
 274         idx -= CBH_SIZE * CBH_SIZE;
 275         return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]
 276                                  [(idx >> CBH_SHIFT) & CBH_MASK]
 277                                  [idx & CBH_MASK]);
 278 }
 279
 280 /**
 281  * Obtains a pointer to a heap element, given its index into the binary tree.
 282  *
 283  * \param[in] h   The binary heap
 284  * \param[in] idx The requested node's index
 285  *
 286  * \retval valid-pointer The requested heap node
 287  * \retval NULL          Supplied index is out of bounds
 288  */
 289 struct cfs_binheap_node *
 290 cfs_binheap_find(struct cfs_binheap *h, unsigned int idx)
 291 {
 292         if (idx >= h->cbh_nelements)
 293                 return NULL;
 294
 295         return *cfs_binheap_pointer(h, idx);
 296 }
 297 EXPORT_SYMBOL(cfs_binheap_find);
 298
 299 /**
 300  * Moves a node upwards, towards the root of the binary tree.
 301  *
 302  * \param[in] h The heap
 303  * \param[in] e The node
 304  *
 305  * \retval 1 The position of \a e in the tree was changed at least once
 306  * \retval 0 The position of \a e in the tree was not changed
 307  */
 308 static int
 309 cfs_binheap_bubble(struct cfs_binheap *h, struct cfs_binheap_node *e)
 310 {
 311         unsigned int         cur_idx = e->chn_index;
 312         struct cfs_binheap_node **cur_ptr;
 313         unsigned int         parent_idx;
 314         struct cfs_binheap_node **parent_ptr;
 315         int                  did_sth = 0;
 316
 317         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 318         LASSERT(*cur_ptr == e);
 319
 320         while (cur_idx > 0) {
 321                 parent_idx = (cur_idx - 1) >> 1;
 322
 323                 parent_ptr = cfs_binheap_pointer(h, parent_idx);
 324                 LASSERT((*parent_ptr)->chn_index == parent_idx);
 325
 326                 if (h->cbh_ops->hop_compare(*parent_ptr, e))
 327                         break;
 328
 329                 (*parent_ptr)->chn_index = cur_idx;
 330                 *cur_ptr = *parent_ptr;
 331                 cur_ptr = parent_ptr;
 332                 cur_idx = parent_idx;
 333                 did_sth = 1;
 334         }
 335
 336         e->chn_index = cur_idx;
 337         *cur_ptr = e;
 338
 339         return did_sth;
 340 }
 341
 342 /**
 343  * Moves a node downwards, towards the last level of the binary tree.
 344  *
 345  * \param[in] h The heap
 346  * \param[in] e The node
 347  *
 348  * \retval 1 The position of \a e in the tree was changed at least once
 349  * \retval 0 The position of \a e in the tree was not changed
 350  */
 351 static int
 352 cfs_binheap_sink(struct cfs_binheap *h, struct cfs_binheap_node *e)
 353 {
 354         unsigned int         n = h->cbh_nelements;
 355         unsigned int         child_idx;
 356         struct cfs_binheap_node **child_ptr;
 357         struct cfs_binheap_node  *child;
 358         unsigned int         child2_idx;
 359         struct cfs_binheap_node **child2_ptr;
 360         struct cfs_binheap_node  *child2;
 361         unsigned int         cur_idx;
 362         struct cfs_binheap_node **cur_ptr;
 363         int                  did_sth = 0;
 364
 365         cur_idx = e->chn_index;
 366         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 367         LASSERT(*cur_ptr == e);
 368
 369         while (cur_idx < n) {
 370                 child_idx = (cur_idx << 1) + 1;
 371                 if (child_idx >= n)
 372                         break;
 373
 374                 child_ptr = cfs_binheap_pointer(h, child_idx);
 375                 child = *child_ptr;
 376
 377                 child2_idx = child_idx + 1;
 378                 if (child2_idx < n) {
 379                         child2_ptr = cfs_binheap_pointer(h, child2_idx);
 380                         child2 = *child2_ptr;
 381
 382                         if (h->cbh_ops->hop_compare(child2, child)) {
 383                                 child_idx = child2_idx;
 384                                 child_ptr = child2_ptr;
 385                                 child = child2;
 386                         }
 387                 }
 388
 389                 LASSERT(child->chn_index == child_idx);
 390
 391                 if (h->cbh_ops->hop_compare(e, child))
 392                         break;
 393
 394                 child->chn_index = cur_idx;
 395                 *cur_ptr = child;
 396                 cur_ptr = child_ptr;
 397                 cur_idx = child_idx;
 398                 did_sth = 1;
 399         }
 400
 401         e->chn_index = cur_idx;
 402         *cur_ptr = e;
 403
 404         return did_sth;
 405 }
 406
 407 /**
 408  * Sort-inserts a node into the binary heap.
 409  *
 410  * \param[in] h The heap
 411  * \param[in] e The node
 412  *
 413  * \retval 0    Element inserted successfully
 414  * \retval != 0 error
 415  */
 416 int
 417 cfs_binheap_insert(struct cfs_binheap *h, struct cfs_binheap_node *e)
 418 {
 419         struct cfs_binheap_node **new_ptr;
 420         unsigned int         new_idx = h->cbh_nelements;
 421         int                  rc;
 422
 423         if (new_idx == h->cbh_hwm) {
 424                 rc = cfs_binheap_grow(h);
 425                 if (rc != 0)
 426                         return rc;
 427         }
 428
 429         if (h->cbh_ops->hop_enter) {
 430                 rc = h->cbh_ops->hop_enter(h, e);
 431                 if (rc != 0)
 432                         return rc;
 433         }
 434
 435         e->chn_index = new_idx;
 436         new_ptr = cfs_binheap_pointer(h, new_idx);
 437         h->cbh_nelements++;
 438         *new_ptr = e;
 439
 440         cfs_binheap_bubble(h, e);
 441
 442         return 0;
 443 }
 444 EXPORT_SYMBOL(cfs_binheap_insert);
 445
 446 /**
 447  * Removes a node from the binary heap.
 448  *
 449  * \param[in] h The heap
 450  * \param[in] e The node
 451  */
 452 void
 453 cfs_binheap_remove(struct cfs_binheap *h, struct cfs_binheap_node *e)
 454 {
 455         unsigned int         n = h->cbh_nelements;
 456         unsigned int         cur_idx = e->chn_index;
 457         struct cfs_binheap_node **cur_ptr;
 458         struct cfs_binheap_node  *last;
 459
 460         LASSERT(cur_idx != CBH_POISON);
 461         LASSERT(cur_idx < n);
 462
 463         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 464         LASSERT(*cur_ptr == e);
 465
 466         n--;
 467         last = *cfs_binheap_pointer(h, n);
 468         h->cbh_nelements = n;
 469         if (last == e)
 470                 return;
 471
 472         last->chn_index = cur_idx;
 473         *cur_ptr = last;
 474         cfs_binheap_relocate(h, *cur_ptr);
 475
 476         e->chn_index = CBH_POISON;
 477         if (h->cbh_ops->hop_exit)
 478                 h->cbh_ops->hop_exit(h, e);
 479 }
 480 EXPORT_SYMBOL(cfs_binheap_remove);
 481
 482 /**
 483  * Relocate a node in the binary heap.
 484  * Should be called whenever a node's values
 485  * which affects its ranking are changed.
 486  *
 487  * \param[in] h The heap
 488  * \param[in] e The node
 489  */
 490 void
 491 cfs_binheap_relocate(struct cfs_binheap *h, struct cfs_binheap_node *e)
 492 {
 493         if (!cfs_binheap_bubble(h, e))
 494                 cfs_binheap_sink(h, e);
 495 }
 496 EXPORT_SYMBOL(cfs_binheap_relocate);
 497 /** @} heap */