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