fs/ocfs2/reservations.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /* -*- mode: c; c-basic-offset: 8; -*-
   3  * vim: noexpandtab sw=8 ts=8 sts=0:
   4  *
   5  * reservations.c
   6  *
   7  * Allocation reservations implementation
   8  *
   9  * Some code borrowed from fs/ext3/balloc.c and is:
  10  *
  11  * Copyright (C) 1992, 1993, 1994, 1995
  12  * Remy Card (card@masi.ibp.fr)
  13  * Laboratoire MASI - Institut Blaise Pascal
  14  * Universite Pierre et Marie Curie (Paris VI)
  15  *
  16  * The rest is copyright (C) 2010 Novell.  All rights reserved.
  17  */
  18
  19 #include <linux/fs.h>
  20 #include <linux/types.h>
  21 #include <linux/highmem.h>
  22 #include <linux/bitops.h>
  23 #include <linux/list.h>
  24
  25 #include <cluster/masklog.h>
  26
  27 #include "ocfs2.h"
  28 #include "ocfs2_trace.h"
  29
  30 #ifdef CONFIG_OCFS2_DEBUG_FS
  31 #define OCFS2_CHECK_RESERVATIONS
  32 #endif
  33
  34 static DEFINE_SPINLOCK(resv_lock);
  35
  36 #define OCFS2_MIN_RESV_WINDOW_BITS      8
  37 #define OCFS2_MAX_RESV_WINDOW_BITS      1024
  38
  39 int ocfs2_dir_resv_allowed(struct ocfs2_super *osb)
  40 {
  41         return (osb->osb_resv_level && osb->osb_dir_resv_level);
  42 }
  43
  44 static unsigned int ocfs2_resv_window_bits(struct ocfs2_reservation_map *resmap,
  45                                            struct ocfs2_alloc_reservation *resv)
  46 {
  47         struct ocfs2_super *osb = resmap->m_osb;
  48         unsigned int bits;
  49
  50         if (!(resv->r_flags & OCFS2_RESV_FLAG_DIR)) {
  51                 /* 8, 16, 32, 64, 128, 256, 512, 1024 */
  52                 bits = 4 << osb->osb_resv_level;
  53         } else {
  54                 bits = 4 << osb->osb_dir_resv_level;
  55         }
  56         return bits;
  57 }
  58
  59 static inline unsigned int ocfs2_resv_end(struct ocfs2_alloc_reservation *resv)
  60 {
  61         if (resv->r_len)
  62                 return resv->r_start + resv->r_len - 1;
  63         return resv->r_start;
  64 }
  65
  66 static inline int ocfs2_resv_empty(struct ocfs2_alloc_reservation *resv)
  67 {
  68         return !!(resv->r_len == 0);
  69 }
  70
  71 static inline int ocfs2_resmap_disabled(struct ocfs2_reservation_map *resmap)
  72 {
  73         if (resmap->m_osb->osb_resv_level == 0)
  74                 return 1;
  75         return 0;
  76 }
  77
  78 static void ocfs2_dump_resv(struct ocfs2_reservation_map *resmap)
  79 {
  80         struct ocfs2_super *osb = resmap->m_osb;
  81         struct rb_node *node;
  82         struct ocfs2_alloc_reservation *resv;
  83         int i = 0;
  84
  85         mlog(ML_NOTICE, "Dumping resmap for device %s. Bitmap length: %u\n",
  86              osb->dev_str, resmap->m_bitmap_len);
  87
  88         node = rb_first(&resmap->m_reservations);
  89         while (node) {
  90                 resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node);
  91
  92                 mlog(ML_NOTICE, "start: %u\tend: %u\tlen: %u\tlast_start: %u"
  93                      "\tlast_len: %u\n", resv->r_start,
  94                      ocfs2_resv_end(resv), resv->r_len, resv->r_last_start,
  95                      resv->r_last_len);
  96
  97                 node = rb_next(node);
  98                 i++;
  99         }
 100
 101         mlog(ML_NOTICE, "%d reservations found. LRU follows\n", i);
 102
 103         i = 0;
 104         list_for_each_entry(resv, &resmap->m_lru, r_lru) {
 105                 mlog(ML_NOTICE, "LRU(%d) start: %u\tend: %u\tlen: %u\t"
 106                      "last_start: %u\tlast_len: %u\n", i, resv->r_start,
 107                      ocfs2_resv_end(resv), resv->r_len, resv->r_last_start,
 108                      resv->r_last_len);
 109
 110                 i++;
 111         }
 112 }
 113
 114 #ifdef OCFS2_CHECK_RESERVATIONS
 115 static int ocfs2_validate_resmap_bits(struct ocfs2_reservation_map *resmap,
 116                                       int i,
 117                                       struct ocfs2_alloc_reservation *resv)
 118 {
 119         char *disk_bitmap = resmap->m_disk_bitmap;
 120         unsigned int start = resv->r_start;
 121         unsigned int end = ocfs2_resv_end(resv);
 122
 123         while (start <= end) {
 124                 if (ocfs2_test_bit(start, disk_bitmap)) {
 125                         mlog(ML_ERROR,
 126                              "reservation %d covers an allocated area "
 127                              "starting at bit %u!\n", i, start);
 128                         return 1;
 129                 }
 130
 131                 start++;
 132         }
 133         return 0;
 134 }
 135
 136 static void ocfs2_check_resmap(struct ocfs2_reservation_map *resmap)
 137 {
 138         unsigned int off = 0;
 139         int i = 0;
 140         struct rb_node *node;
 141         struct ocfs2_alloc_reservation *resv;
 142
 143         node = rb_first(&resmap->m_reservations);
 144         while (node) {
 145                 resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node);
 146
 147                 if (i > 0 && resv->r_start <= off) {
 148                         mlog(ML_ERROR, "reservation %d has bad start off!\n",
 149                              i);
 150                         goto bad;
 151                 }
 152
 153                 if (resv->r_len == 0) {
 154                         mlog(ML_ERROR, "reservation %d has no length!\n",
 155                              i);
 156                         goto bad;
 157                 }
 158
 159                 if (resv->r_start > ocfs2_resv_end(resv)) {
 160                         mlog(ML_ERROR, "reservation %d has invalid range!\n",
 161                              i);
 162                         goto bad;
 163                 }
 164
 165                 if (ocfs2_resv_end(resv) >= resmap->m_bitmap_len) {
 166                         mlog(ML_ERROR, "reservation %d extends past bitmap!\n",
 167                              i);
 168                         goto bad;
 169                 }
 170
 171                 if (ocfs2_validate_resmap_bits(resmap, i, resv))
 172                         goto bad;
 173
 174                 off = ocfs2_resv_end(resv);
 175                 node = rb_next(node);
 176
 177                 i++;
 178         }
 179         return;
 180
 181 bad:
 182         ocfs2_dump_resv(resmap);
 183         BUG();
 184 }
 185 #else
 186 static inline void ocfs2_check_resmap(struct ocfs2_reservation_map *resmap)
 187 {
 188
 189 }
 190 #endif
 191
 192 void ocfs2_resv_init_once(struct ocfs2_alloc_reservation *resv)
 193 {
 194         memset(resv, 0, sizeof(*resv));
 195         INIT_LIST_HEAD(&resv->r_lru);
 196 }
 197
 198 void ocfs2_resv_set_type(struct ocfs2_alloc_reservation *resv,
 199                          unsigned int flags)
 200 {
 201         BUG_ON(flags & ~OCFS2_RESV_TYPES);
 202
 203         resv->r_flags |= flags;
 204 }
 205
 206 int ocfs2_resmap_init(struct ocfs2_super *osb,
 207                       struct ocfs2_reservation_map *resmap)
 208 {
 209         memset(resmap, 0, sizeof(*resmap));
 210
 211         resmap->m_osb = osb;
 212         resmap->m_reservations = RB_ROOT;
 213         /* m_bitmap_len is initialized to zero by the above memset. */
 214         INIT_LIST_HEAD(&resmap->m_lru);
 215
 216         return 0;
 217 }
 218
 219 static void ocfs2_resv_mark_lru(struct ocfs2_reservation_map *resmap,
 220                                 struct ocfs2_alloc_reservation *resv)
 221 {
 222         assert_spin_locked(&resv_lock);
 223
 224         if (!list_empty(&resv->r_lru))
 225                 list_del_init(&resv->r_lru);
 226
 227         list_add_tail(&resv->r_lru, &resmap->m_lru);
 228 }
 229
 230 static void __ocfs2_resv_trunc(struct ocfs2_alloc_reservation *resv)
 231 {
 232         resv->r_len = 0;
 233         resv->r_start = 0;
 234 }
 235
 236 static void ocfs2_resv_remove(struct ocfs2_reservation_map *resmap,
 237                               struct ocfs2_alloc_reservation *resv)
 238 {
 239         if (resv->r_flags & OCFS2_RESV_FLAG_INUSE) {
 240                 list_del_init(&resv->r_lru);
 241                 rb_erase(&resv->r_node, &resmap->m_reservations);
 242                 resv->r_flags &= ~OCFS2_RESV_FLAG_INUSE;
 243         }
 244 }
 245
 246 static void __ocfs2_resv_discard(struct ocfs2_reservation_map *resmap,
 247                                  struct ocfs2_alloc_reservation *resv)
 248 {
 249         assert_spin_locked(&resv_lock);
 250
 251         __ocfs2_resv_trunc(resv);
 252         /*
 253          * last_len and last_start no longer make sense if
 254          * we're changing the range of our allocations.
 255          */
 256         resv->r_last_len = resv->r_last_start = 0;
 257
 258         ocfs2_resv_remove(resmap, resv);
 259 }
 260
 261 /* does nothing if 'resv' is null */
 262 void ocfs2_resv_discard(struct ocfs2_reservation_map *resmap,
 263                         struct ocfs2_alloc_reservation *resv)
 264 {
 265         if (resv) {
 266                 spin_lock(&resv_lock);
 267                 __ocfs2_resv_discard(resmap, resv);
 268                 spin_unlock(&resv_lock);
 269         }
 270 }
 271
 272 static void ocfs2_resmap_clear_all_resv(struct ocfs2_reservation_map *resmap)
 273 {
 274         struct rb_node *node;
 275         struct ocfs2_alloc_reservation *resv;
 276
 277         assert_spin_locked(&resv_lock);
 278
 279         while ((node = rb_last(&resmap->m_reservations)) != NULL) {
 280                 resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node);
 281
 282                 __ocfs2_resv_discard(resmap, resv);
 283         }
 284 }
 285
 286 void ocfs2_resmap_restart(struct ocfs2_reservation_map *resmap,
 287                           unsigned int clen, char *disk_bitmap)
 288 {
 289         if (ocfs2_resmap_disabled(resmap))
 290                 return;
 291
 292         spin_lock(&resv_lock);
 293
 294         ocfs2_resmap_clear_all_resv(resmap);
 295         resmap->m_bitmap_len = clen;
 296         resmap->m_disk_bitmap = disk_bitmap;
 297
 298         spin_unlock(&resv_lock);
 299 }
 300
 301 void ocfs2_resmap_uninit(struct ocfs2_reservation_map *resmap)
 302 {
 303         /* Does nothing for now. Keep this around for API symmetry */
 304 }
 305
 306 static void ocfs2_resv_insert(struct ocfs2_reservation_map *resmap,
 307                               struct ocfs2_alloc_reservation *new)
 308 {
 309         struct rb_root *root = &resmap->m_reservations;
 310         struct rb_node *parent = NULL;
 311         struct rb_node **p = &root->rb_node;
 312         struct ocfs2_alloc_reservation *tmp;
 313
 314         assert_spin_locked(&resv_lock);
 315
 316         trace_ocfs2_resv_insert(new->r_start, new->r_len);
 317
 318         while (*p) {
 319                 parent = *p;
 320
 321                 tmp = rb_entry(parent, struct ocfs2_alloc_reservation, r_node);
 322
 323                 if (new->r_start < tmp->r_start) {
 324                         p = &(*p)->rb_left;
 325
 326                         /*
 327                          * This is a good place to check for
 328                          * overlapping reservations.
 329                          */
 330                         BUG_ON(ocfs2_resv_end(new) >= tmp->r_start);
 331                 } else if (new->r_start > ocfs2_resv_end(tmp)) {
 332                         p = &(*p)->rb_right;
 333                 } else {
 334                         /* This should never happen! */
 335                         mlog(ML_ERROR, "Duplicate reservation window!\n");
 336                         BUG();
 337                 }
 338         }
 339
 340         rb_link_node(&new->r_node, parent, p);
 341         rb_insert_color(&new->r_node, root);
 342         new->r_flags |= OCFS2_RESV_FLAG_INUSE;
 343
 344         ocfs2_resv_mark_lru(resmap, new);
 345
 346         ocfs2_check_resmap(resmap);
 347 }
 348
 349 /**
 350  * ocfs2_find_resv_lhs() - find the window which contains goal
 351  * @resmap: reservation map to search
 352  * @goal: which bit to search for
 353  *
 354  * If a window containing that goal is not found, we return the window
 355  * which comes before goal. Returns NULL on empty rbtree or no window
 356  * before goal.
 357  */
 358 static struct ocfs2_alloc_reservation *
 359 ocfs2_find_resv_lhs(struct ocfs2_reservation_map *resmap, unsigned int goal)
 360 {
 361         struct ocfs2_alloc_reservation *resv = NULL;
 362         struct ocfs2_alloc_reservation *prev_resv = NULL;
 363         struct rb_node *node = resmap->m_reservations.rb_node;
 364
 365         assert_spin_locked(&resv_lock);
 366
 367         if (!node)
 368                 return NULL;
 369
 370         node = rb_first(&resmap->m_reservations);
 371         while (node) {
 372                 resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node);
 373
 374                 if (resv->r_start <= goal && ocfs2_resv_end(resv) >= goal)
 375                         break;
 376
 377                 /* Check if we overshot the reservation just before goal? */
 378                 if (resv->r_start > goal) {
 379                         resv = prev_resv;
 380                         break;
 381                 }
 382
 383                 prev_resv = resv;
 384                 node = rb_next(node);
 385         }
 386
 387         return resv;
 388 }
 389
 390 /*
 391  * We are given a range within the bitmap, which corresponds to a gap
 392  * inside the reservations tree (search_start, search_len). The range
 393  * can be anything from the whole bitmap, to a gap between
 394  * reservations.
 395  *
 396  * The start value of *rstart is insignificant.
 397  *
 398  * This function searches the bitmap range starting at search_start
 399  * with length search_len for a set of contiguous free bits. We try
 400  * to find up to 'wanted' bits, but can sometimes return less.
 401  *
 402  * Returns the length of allocation, 0 if no free bits are found.
 403  *
 404  * *cstart and *clen will also be populated with the result.
 405  */
 406 static int ocfs2_resmap_find_free_bits(struct ocfs2_reservation_map *resmap,
 407                                        unsigned int wanted,
 408                                        unsigned int search_start,
 409                                        unsigned int search_len,
 410                                        unsigned int *rstart,
 411                                        unsigned int *rlen)
 412 {
 413         void *bitmap = resmap->m_disk_bitmap;
 414         unsigned int best_start, best_len = 0;
 415         int offset, start, found;
 416
 417         trace_ocfs2_resmap_find_free_bits_begin(search_start, search_len,
 418                                                 wanted, resmap->m_bitmap_len);
 419
 420         found = best_start = best_len = 0;
 421
 422         start = search_start;
 423         while ((offset = ocfs2_find_next_zero_bit(bitmap, resmap->m_bitmap_len,
 424                                                  start)) != -1) {
 425                 /* Search reached end of the region */
 426                 if (offset >= (search_start + search_len))
 427                         break;
 428
 429                 if (offset == start) {
 430                         /* we found a zero */
 431                         found++;
 432                         /* move start to the next bit to test */
 433                         start++;
 434                 } else {
 435                         /* got a zero after some ones */
 436                         found = 1;
 437                         start = offset + 1;
 438                 }
 439                 if (found > best_len) {
 440                         best_len = found;
 441                         best_start = start - found;
 442                 }
 443
 444                 if (found >= wanted)
 445                         break;
 446         }
 447
 448         if (best_len == 0)
 449                 return 0;
 450
 451         if (best_len >= wanted)
 452                 best_len = wanted;
 453
 454         *rlen = best_len;
 455         *rstart = best_start;
 456
 457         trace_ocfs2_resmap_find_free_bits_end(best_start, best_len);
 458
 459         return *rlen;
 460 }
 461
 462 static void __ocfs2_resv_find_window(struct ocfs2_reservation_map *resmap,
 463                                      struct ocfs2_alloc_reservation *resv,
 464                                      unsigned int goal, unsigned int wanted)
 465 {
 466         struct rb_root *root = &resmap->m_reservations;
 467         unsigned int gap_start, gap_end, gap_len;
 468         struct ocfs2_alloc_reservation *prev_resv, *next_resv;
 469         struct rb_node *prev, *next;
 470         unsigned int cstart, clen;
 471         unsigned int best_start = 0, best_len = 0;
 472
 473         /*
 474          * Nasty cases to consider:
 475          *
 476          * - rbtree is empty
 477          * - our window should be first in all reservations
 478          * - our window should be last in all reservations
 479          * - need to make sure we don't go past end of bitmap
 480          */
 481         trace_ocfs2_resv_find_window_begin(resv->r_start, ocfs2_resv_end(resv),
 482                                            goal, wanted, RB_EMPTY_ROOT(root));
 483
 484         assert_spin_locked(&resv_lock);
 485
 486         if (RB_EMPTY_ROOT(root)) {
 487                 /*
 488                  * Easiest case - empty tree. We can just take
 489                  * whatever window of free bits we want.
 490                  */
 491                 clen = ocfs2_resmap_find_free_bits(resmap, wanted, goal,
 492                                                    resmap->m_bitmap_len - goal,
 493                                                    &cstart, &clen);
 494
 495                 /*
 496                  * This should never happen - the local alloc window
 497                  * will always have free bits when we're called.
 498                  */
 499                 BUG_ON(goal == 0 && clen == 0);
 500
 501                 if (clen == 0)
 502                         return;
 503
 504                 resv->r_start = cstart;
 505                 resv->r_len = clen;
 506
 507                 ocfs2_resv_insert(resmap, resv);
 508                 return;
 509         }
 510
 511         prev_resv = ocfs2_find_resv_lhs(resmap, goal);
 512
 513         if (prev_resv == NULL) {
 514                 /*
 515                  * A NULL here means that the search code couldn't
 516                  * find a window that starts before goal.
 517                  *
 518                  * However, we can take the first window after goal,
 519                  * which is also by definition, the leftmost window in
 520                  * the entire tree. If we can find free bits in the
 521                  * gap between goal and the LHS window, then the
 522                  * reservation can safely be placed there.
 523                  *
 524                  * Otherwise we fall back to a linear search, checking
 525                  * the gaps in between windows for a place to
 526                  * allocate.
 527                  */
 528
 529                 next = rb_first(root);
 530                 next_resv = rb_entry(next, struct ocfs2_alloc_reservation,
 531                                      r_node);
 532
 533                 /*
 534                  * The search should never return such a window. (see
 535                  * comment above
 536                  */
 537                 if (next_resv->r_start <= goal) {
 538                         mlog(ML_ERROR, "goal: %u next_resv: start %u len %u\n",
 539                              goal, next_resv->r_start, next_resv->r_len);
 540                         ocfs2_dump_resv(resmap);
 541                         BUG();
 542                 }
 543
 544                 clen = ocfs2_resmap_find_free_bits(resmap, wanted, goal,
 545                                                    next_resv->r_start - goal,
 546                                                    &cstart, &clen);
 547                 if (clen) {
 548                         best_len = clen;
 549                         best_start = cstart;
 550                         if (best_len == wanted)
 551                                 goto out_insert;
 552                 }
 553
 554                 prev_resv = next_resv;
 555                 next_resv = NULL;
 556         }
 557
 558         trace_ocfs2_resv_find_window_prev(prev_resv->r_start,
 559                                           ocfs2_resv_end(prev_resv));
 560
 561         prev = &prev_resv->r_node;
 562
 563         /* Now we do a linear search for a window, starting at 'prev_rsv' */
 564         while (1) {
 565                 next = rb_next(prev);
 566                 if (next) {
 567                         next_resv = rb_entry(next,
 568                                              struct ocfs2_alloc_reservation,
 569                                              r_node);
 570
 571                         gap_start = ocfs2_resv_end(prev_resv) + 1;
 572                         gap_end = next_resv->r_start - 1;
 573                         gap_len = gap_end - gap_start + 1;
 574                 } else {
 575                         /*
 576                          * We're at the rightmost edge of the
 577                          * tree. See if a reservation between this
 578                          * window and the end of the bitmap will work.
 579                          */
 580                         gap_start = ocfs2_resv_end(prev_resv) + 1;
 581                         gap_len = resmap->m_bitmap_len - gap_start;
 582                         gap_end = resmap->m_bitmap_len - 1;
 583                 }
 584
 585                 trace_ocfs2_resv_find_window_next(next ? next_resv->r_start: -1,
 586                                         next ? ocfs2_resv_end(next_resv) : -1);
 587                 /*
 588                  * No need to check this gap if we have already found
 589                  * a larger region of free bits.
 590                  */
 591                 if (gap_len <= best_len)
 592                         goto next_resv;
 593
 594                 clen = ocfs2_resmap_find_free_bits(resmap, wanted, gap_start,
 595                                                    gap_len, &cstart, &clen);
 596                 if (clen == wanted) {
 597                         best_len = clen;
 598                         best_start = cstart;
 599                         goto out_insert;
 600                 } else if (clen > best_len) {
 601                         best_len = clen;
 602                         best_start = cstart;
 603                 }
 604
 605 next_resv:
 606                 if (!next)
 607                         break;
 608
 609                 prev = next;
 610                 prev_resv = rb_entry(prev, struct ocfs2_alloc_reservation,
 611                                      r_node);
 612         }
 613
 614 out_insert:
 615         if (best_len) {
 616                 resv->r_start = best_start;
 617                 resv->r_len = best_len;
 618                 ocfs2_resv_insert(resmap, resv);
 619         }
 620 }
 621
 622 static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map *resmap,
 623                                    struct ocfs2_alloc_reservation *resv,
 624                                    unsigned int wanted)
 625 {
 626         struct ocfs2_alloc_reservation *lru_resv;
 627         int tmpwindow = !!(resv->r_flags & OCFS2_RESV_FLAG_TMP);
 628         unsigned int min_bits;
 629
 630         if (!tmpwindow)
 631                 min_bits = ocfs2_resv_window_bits(resmap, resv) >> 1;
 632         else
 633                 min_bits = wanted; /* We at know the temp window will use all
 634                                     * of these bits */
 635
 636         /*
 637          * Take the first reservation off the LRU as our 'target'. We
 638          * don't try to be smart about it. There might be a case for
 639          * searching based on size but I don't have enough data to be
 640          * sure. --Mark (3/16/2010)
 641          */
 642         lru_resv = list_first_entry(&resmap->m_lru,
 643                                     struct ocfs2_alloc_reservation, r_lru);
 644
 645         trace_ocfs2_cannibalize_resv_begin(lru_resv->r_start,
 646                                            lru_resv->r_len,
 647                                            ocfs2_resv_end(lru_resv));
 648
 649         /*
 650          * Cannibalize (some or all) of the target reservation and
 651          * feed it to the current window.
 652          */
 653         if (lru_resv->r_len <= min_bits) {
 654                 /*
 655                  * Discard completely if size is less than or equal to a
 656                  * reasonable threshold - 50% of window bits for non temporary
 657                  * windows.
 658                  */
 659                 resv->r_start = lru_resv->r_start;
 660                 resv->r_len = lru_resv->r_len;
 661
 662                 __ocfs2_resv_discard(resmap, lru_resv);
 663         } else {
 664                 unsigned int shrink;
 665                 if (tmpwindow)
 666                         shrink = min_bits;
 667                 else
 668                         shrink = lru_resv->r_len / 2;
 669
 670                 lru_resv->r_len -= shrink;
 671
 672                 resv->r_start = ocfs2_resv_end(lru_resv) + 1;
 673                 resv->r_len = shrink;
 674         }
 675
 676         trace_ocfs2_cannibalize_resv_end(resv->r_start, ocfs2_resv_end(resv),
 677                                          resv->r_len, resv->r_last_start,
 678                                          resv->r_last_len);
 679
 680         ocfs2_resv_insert(resmap, resv);
 681 }
 682
 683 static void ocfs2_resv_find_window(struct ocfs2_reservation_map *resmap,
 684                                    struct ocfs2_alloc_reservation *resv,
 685                                    unsigned int wanted)
 686 {
 687         unsigned int goal = 0;
 688
 689         BUG_ON(!ocfs2_resv_empty(resv));
 690
 691         /*
 692          * Begin by trying to get a window as close to the previous
 693          * one as possible. Using the most recent allocation as a
 694          * start goal makes sense.
 695          */
 696         if (resv->r_last_len) {
 697                 goal = resv->r_last_start + resv->r_last_len;
 698                 if (goal >= resmap->m_bitmap_len)
 699                         goal = 0;
 700         }
 701
 702         __ocfs2_resv_find_window(resmap, resv, goal, wanted);
 703
 704         /* Search from last alloc didn't work, try once more from beginning. */
 705         if (ocfs2_resv_empty(resv) && goal != 0)
 706                 __ocfs2_resv_find_window(resmap, resv, 0, wanted);
 707
 708         if (ocfs2_resv_empty(resv)) {
 709                 /*
 710                  * Still empty? Pull oldest one off the LRU, remove it from
 711                  * tree, put this one in it's place.
 712                  */
 713                 ocfs2_cannibalize_resv(resmap, resv, wanted);
 714         }
 715
 716         BUG_ON(ocfs2_resv_empty(resv));
 717 }
 718
 719 int ocfs2_resmap_resv_bits(struct ocfs2_reservation_map *resmap,
 720                            struct ocfs2_alloc_reservation *resv,
 721                            int *cstart, int *clen)
 722 {
 723         if (resv == NULL || ocfs2_resmap_disabled(resmap))
 724                 return -ENOSPC;
 725
 726         spin_lock(&resv_lock);
 727
 728         if (ocfs2_resv_empty(resv)) {
 729                 /*
 730                  * We don't want to over-allocate for temporary
 731                  * windows. Otherwise, we run the risk of fragmenting the
 732                  * allocation space.
 733                  */
 734                 unsigned int wanted = ocfs2_resv_window_bits(resmap, resv);
 735
 736                 if ((resv->r_flags & OCFS2_RESV_FLAG_TMP) || wanted < *clen)
 737                         wanted = *clen;
 738
 739                 /*
 740                  * Try to get a window here. If it works, we must fall
 741                  * through and test the bitmap . This avoids some
 742                  * ping-ponging of windows due to non-reserved space
 743                  * being allocation before we initialize a window for
 744                  * that inode.
 745                  */
 746                 ocfs2_resv_find_window(resmap, resv, wanted);
 747                 trace_ocfs2_resmap_resv_bits(resv->r_start, resv->r_len);
 748         }
 749
 750         BUG_ON(ocfs2_resv_empty(resv));
 751
 752         *cstart = resv->r_start;
 753         *clen = resv->r_len;
 754
 755         spin_unlock(&resv_lock);
 756         return 0;
 757 }
 758
 759 static void
 760         ocfs2_adjust_resv_from_alloc(struct ocfs2_reservation_map *resmap,
 761                                      struct ocfs2_alloc_reservation *resv,
 762                                      unsigned int start, unsigned int end)
 763 {
 764         unsigned int rhs = 0;
 765         unsigned int old_end = ocfs2_resv_end(resv);
 766
 767         BUG_ON(start != resv->r_start || old_end < end);
 768
 769         /*
 770          * Completely used? We can remove it then.
 771          */
 772         if (old_end == end) {
 773                 __ocfs2_resv_discard(resmap, resv);
 774                 return;
 775         }
 776
 777         rhs = old_end - end;
 778
 779         /*
 780          * This should have been trapped above.
 781          */
 782         BUG_ON(rhs == 0);
 783
 784         resv->r_start = end + 1;
 785         resv->r_len = old_end - resv->r_start + 1;
 786 }
 787
 788 void ocfs2_resmap_claimed_bits(struct ocfs2_reservation_map *resmap,
 789                                struct ocfs2_alloc_reservation *resv,
 790                                u32 cstart, u32 clen)
 791 {
 792         unsigned int cend = cstart + clen - 1;
 793
 794         if (resmap == NULL || ocfs2_resmap_disabled(resmap))
 795                 return;
 796
 797         if (resv == NULL)
 798                 return;
 799
 800         BUG_ON(cstart != resv->r_start);
 801
 802         spin_lock(&resv_lock);
 803
 804         trace_ocfs2_resmap_claimed_bits_begin(cstart, cend, clen, resv->r_start,
 805                                               ocfs2_resv_end(resv), resv->r_len,
 806                                               resv->r_last_start,
 807                                               resv->r_last_len);
 808
 809         BUG_ON(cstart < resv->r_start);
 810         BUG_ON(cstart > ocfs2_resv_end(resv));
 811         BUG_ON(cend > ocfs2_resv_end(resv));
 812
 813         ocfs2_adjust_resv_from_alloc(resmap, resv, cstart, cend);
 814         resv->r_last_start = cstart;
 815         resv->r_last_len = clen;
 816
 817         /*
 818          * May have been discarded above from
 819          * ocfs2_adjust_resv_from_alloc().
 820          */
 821         if (!ocfs2_resv_empty(resv))
 822                 ocfs2_resv_mark_lru(resmap, resv);
 823
 824         trace_ocfs2_resmap_claimed_bits_end(resv->r_start, ocfs2_resv_end(resv),
 825                                             resv->r_len, resv->r_last_start,
 826                                             resv->r_last_len);
 827
 828         ocfs2_check_resmap(resmap);
 829
 830         spin_unlock(&resv_lock);
 831 }