1 // SPDX-License-Identifier: GPL-2.0-only
5 * Allocation reservations implementation
7 * Some code borrowed from fs/ext3/balloc.c and is:
9 * Copyright (C) 1992, 1993, 1994, 1995
10 * Remy Card (card@masi.ibp.fr)
11 * Laboratoire MASI - Institut Blaise Pascal
12 * Universite Pierre et Marie Curie (Paris VI)
14 * The rest is copyright (C) 2010 Novell. All rights reserved.
18 #include <linux/types.h>
19 #include <linux/highmem.h>
20 #include <linux/bitops.h>
21 #include <linux/list.h>
23 #include <cluster/masklog.h>
26 #include "ocfs2_trace.h"
28 #ifdef CONFIG_OCFS2_DEBUG_FS
29 #define OCFS2_CHECK_RESERVATIONS
32 static DEFINE_SPINLOCK(resv_lock
);
34 int ocfs2_dir_resv_allowed(struct ocfs2_super
*osb
)
36 return (osb
->osb_resv_level
&& osb
->osb_dir_resv_level
);
39 static unsigned int ocfs2_resv_window_bits(struct ocfs2_reservation_map
*resmap
,
40 struct ocfs2_alloc_reservation
*resv
)
42 struct ocfs2_super
*osb
= resmap
->m_osb
;
45 if (!(resv
->r_flags
& OCFS2_RESV_FLAG_DIR
)) {
46 /* 8, 16, 32, 64, 128, 256, 512, 1024 */
47 bits
= 4 << osb
->osb_resv_level
;
49 bits
= 4 << osb
->osb_dir_resv_level
;
54 static inline unsigned int ocfs2_resv_end(struct ocfs2_alloc_reservation
*resv
)
57 return resv
->r_start
+ resv
->r_len
- 1;
61 static inline int ocfs2_resv_empty(struct ocfs2_alloc_reservation
*resv
)
63 return !!(resv
->r_len
== 0);
66 static inline int ocfs2_resmap_disabled(struct ocfs2_reservation_map
*resmap
)
68 if (resmap
->m_osb
->osb_resv_level
== 0)
73 static void ocfs2_dump_resv(struct ocfs2_reservation_map
*resmap
)
75 struct ocfs2_super
*osb
= resmap
->m_osb
;
77 struct ocfs2_alloc_reservation
*resv
;
80 mlog(ML_NOTICE
, "Dumping resmap for device %s. Bitmap length: %u\n",
81 osb
->dev_str
, resmap
->m_bitmap_len
);
83 node
= rb_first(&resmap
->m_reservations
);
85 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
87 mlog(ML_NOTICE
, "start: %u\tend: %u\tlen: %u\tlast_start: %u"
88 "\tlast_len: %u\n", resv
->r_start
,
89 ocfs2_resv_end(resv
), resv
->r_len
, resv
->r_last_start
,
96 mlog(ML_NOTICE
, "%d reservations found. LRU follows\n", i
);
99 list_for_each_entry(resv
, &resmap
->m_lru
, r_lru
) {
100 mlog(ML_NOTICE
, "LRU(%d) start: %u\tend: %u\tlen: %u\t"
101 "last_start: %u\tlast_len: %u\n", i
, resv
->r_start
,
102 ocfs2_resv_end(resv
), resv
->r_len
, resv
->r_last_start
,
109 #ifdef OCFS2_CHECK_RESERVATIONS
110 static int ocfs2_validate_resmap_bits(struct ocfs2_reservation_map
*resmap
,
112 struct ocfs2_alloc_reservation
*resv
)
114 char *disk_bitmap
= resmap
->m_disk_bitmap
;
115 unsigned int start
= resv
->r_start
;
116 unsigned int end
= ocfs2_resv_end(resv
);
118 while (start
<= end
) {
119 if (ocfs2_test_bit(start
, disk_bitmap
)) {
121 "reservation %d covers an allocated area "
122 "starting at bit %u!\n", i
, start
);
131 static void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
133 unsigned int off
= 0;
135 struct rb_node
*node
;
136 struct ocfs2_alloc_reservation
*resv
;
138 node
= rb_first(&resmap
->m_reservations
);
140 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
142 if (i
> 0 && resv
->r_start
<= off
) {
143 mlog(ML_ERROR
, "reservation %d has bad start off!\n",
148 if (resv
->r_len
== 0) {
149 mlog(ML_ERROR
, "reservation %d has no length!\n",
154 if (resv
->r_start
> ocfs2_resv_end(resv
)) {
155 mlog(ML_ERROR
, "reservation %d has invalid range!\n",
160 if (ocfs2_resv_end(resv
) >= resmap
->m_bitmap_len
) {
161 mlog(ML_ERROR
, "reservation %d extends past bitmap!\n",
166 if (ocfs2_validate_resmap_bits(resmap
, i
, resv
))
169 off
= ocfs2_resv_end(resv
);
170 node
= rb_next(node
);
177 ocfs2_dump_resv(resmap
);
181 static inline void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
187 void ocfs2_resv_init_once(struct ocfs2_alloc_reservation
*resv
)
189 memset(resv
, 0, sizeof(*resv
));
190 INIT_LIST_HEAD(&resv
->r_lru
);
193 void ocfs2_resv_set_type(struct ocfs2_alloc_reservation
*resv
,
196 BUG_ON(flags
& ~OCFS2_RESV_TYPES
);
198 resv
->r_flags
|= flags
;
201 void ocfs2_resmap_init(struct ocfs2_super
*osb
,
202 struct ocfs2_reservation_map
*resmap
)
204 memset(resmap
, 0, sizeof(*resmap
));
207 resmap
->m_reservations
= RB_ROOT
;
208 /* m_bitmap_len is initialized to zero by the above memset. */
209 INIT_LIST_HEAD(&resmap
->m_lru
);
212 static void ocfs2_resv_mark_lru(struct ocfs2_reservation_map
*resmap
,
213 struct ocfs2_alloc_reservation
*resv
)
215 assert_spin_locked(&resv_lock
);
217 if (!list_empty(&resv
->r_lru
))
218 list_del_init(&resv
->r_lru
);
220 list_add_tail(&resv
->r_lru
, &resmap
->m_lru
);
223 static void __ocfs2_resv_trunc(struct ocfs2_alloc_reservation
*resv
)
229 static void ocfs2_resv_remove(struct ocfs2_reservation_map
*resmap
,
230 struct ocfs2_alloc_reservation
*resv
)
232 if (resv
->r_flags
& OCFS2_RESV_FLAG_INUSE
) {
233 list_del_init(&resv
->r_lru
);
234 rb_erase(&resv
->r_node
, &resmap
->m_reservations
);
235 resv
->r_flags
&= ~OCFS2_RESV_FLAG_INUSE
;
239 static void __ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
240 struct ocfs2_alloc_reservation
*resv
)
242 assert_spin_locked(&resv_lock
);
244 __ocfs2_resv_trunc(resv
);
246 * last_len and last_start no longer make sense if
247 * we're changing the range of our allocations.
249 resv
->r_last_len
= resv
->r_last_start
= 0;
251 ocfs2_resv_remove(resmap
, resv
);
254 /* does nothing if 'resv' is null */
255 void ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
256 struct ocfs2_alloc_reservation
*resv
)
259 spin_lock(&resv_lock
);
260 __ocfs2_resv_discard(resmap
, resv
);
261 spin_unlock(&resv_lock
);
265 static void ocfs2_resmap_clear_all_resv(struct ocfs2_reservation_map
*resmap
)
267 struct rb_node
*node
;
268 struct ocfs2_alloc_reservation
*resv
;
270 assert_spin_locked(&resv_lock
);
272 while ((node
= rb_last(&resmap
->m_reservations
)) != NULL
) {
273 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
275 __ocfs2_resv_discard(resmap
, resv
);
279 void ocfs2_resmap_restart(struct ocfs2_reservation_map
*resmap
,
280 unsigned int clen
, char *disk_bitmap
)
282 if (ocfs2_resmap_disabled(resmap
))
285 spin_lock(&resv_lock
);
287 ocfs2_resmap_clear_all_resv(resmap
);
288 resmap
->m_bitmap_len
= clen
;
289 resmap
->m_disk_bitmap
= disk_bitmap
;
291 spin_unlock(&resv_lock
);
294 void ocfs2_resmap_uninit(struct ocfs2_reservation_map
*resmap
)
296 /* Does nothing for now. Keep this around for API symmetry */
299 static void ocfs2_resv_insert(struct ocfs2_reservation_map
*resmap
,
300 struct ocfs2_alloc_reservation
*new)
302 struct rb_root
*root
= &resmap
->m_reservations
;
303 struct rb_node
*parent
= NULL
;
304 struct rb_node
**p
= &root
->rb_node
;
305 struct ocfs2_alloc_reservation
*tmp
;
307 assert_spin_locked(&resv_lock
);
309 trace_ocfs2_resv_insert(new->r_start
, new->r_len
);
314 tmp
= rb_entry(parent
, struct ocfs2_alloc_reservation
, r_node
);
316 if (new->r_start
< tmp
->r_start
) {
320 * This is a good place to check for
321 * overlapping reservations.
323 BUG_ON(ocfs2_resv_end(new) >= tmp
->r_start
);
324 } else if (new->r_start
> ocfs2_resv_end(tmp
)) {
327 /* This should never happen! */
328 mlog(ML_ERROR
, "Duplicate reservation window!\n");
333 rb_link_node(&new->r_node
, parent
, p
);
334 rb_insert_color(&new->r_node
, root
);
335 new->r_flags
|= OCFS2_RESV_FLAG_INUSE
;
337 ocfs2_resv_mark_lru(resmap
, new);
339 ocfs2_check_resmap(resmap
);
343 * ocfs2_find_resv_lhs() - find the window which contains goal
344 * @resmap: reservation map to search
345 * @goal: which bit to search for
347 * If a window containing that goal is not found, we return the window
348 * which comes before goal. Returns NULL on empty rbtree or no window
351 static struct ocfs2_alloc_reservation
*
352 ocfs2_find_resv_lhs(struct ocfs2_reservation_map
*resmap
, unsigned int goal
)
354 struct ocfs2_alloc_reservation
*resv
= NULL
;
355 struct ocfs2_alloc_reservation
*prev_resv
= NULL
;
356 struct rb_node
*node
= resmap
->m_reservations
.rb_node
;
358 assert_spin_locked(&resv_lock
);
363 node
= rb_first(&resmap
->m_reservations
);
365 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
367 if (resv
->r_start
<= goal
&& ocfs2_resv_end(resv
) >= goal
)
370 /* Check if we overshot the reservation just before goal? */
371 if (resv
->r_start
> goal
) {
377 node
= rb_next(node
);
384 * We are given a range within the bitmap, which corresponds to a gap
385 * inside the reservations tree (search_start, search_len). The range
386 * can be anything from the whole bitmap, to a gap between
389 * The start value of *rstart is insignificant.
391 * This function searches the bitmap range starting at search_start
392 * with length search_len for a set of contiguous free bits. We try
393 * to find up to 'wanted' bits, but can sometimes return less.
395 * Returns the length of allocation, 0 if no free bits are found.
397 * *cstart and *clen will also be populated with the result.
399 static int ocfs2_resmap_find_free_bits(struct ocfs2_reservation_map
*resmap
,
401 unsigned int search_start
,
402 unsigned int search_len
,
403 unsigned int *rstart
,
406 void *bitmap
= resmap
->m_disk_bitmap
;
407 unsigned int best_start
, best_len
= 0;
408 int offset
, start
, found
;
410 trace_ocfs2_resmap_find_free_bits_begin(search_start
, search_len
,
411 wanted
, resmap
->m_bitmap_len
);
413 found
= best_start
= best_len
= 0;
415 start
= search_start
;
416 while ((offset
= ocfs2_find_next_zero_bit(bitmap
, resmap
->m_bitmap_len
,
417 start
)) < resmap
->m_bitmap_len
) {
418 /* Search reached end of the region */
419 if (offset
>= (search_start
+ search_len
))
422 if (offset
== start
) {
423 /* we found a zero */
425 /* move start to the next bit to test */
428 /* got a zero after some ones */
432 if (found
> best_len
) {
434 best_start
= start
- found
;
444 if (best_len
>= wanted
)
448 *rstart
= best_start
;
450 trace_ocfs2_resmap_find_free_bits_end(best_start
, best_len
);
455 static void __ocfs2_resv_find_window(struct ocfs2_reservation_map
*resmap
,
456 struct ocfs2_alloc_reservation
*resv
,
457 unsigned int goal
, unsigned int wanted
)
459 struct rb_root
*root
= &resmap
->m_reservations
;
460 unsigned int gap_start
, gap_end
, gap_len
;
461 struct ocfs2_alloc_reservation
*prev_resv
, *next_resv
;
462 struct rb_node
*prev
, *next
;
463 unsigned int cstart
, clen
;
464 unsigned int best_start
= 0, best_len
= 0;
467 * Nasty cases to consider:
470 * - our window should be first in all reservations
471 * - our window should be last in all reservations
472 * - need to make sure we don't go past end of bitmap
474 trace_ocfs2_resv_find_window_begin(resv
->r_start
, ocfs2_resv_end(resv
),
475 goal
, wanted
, RB_EMPTY_ROOT(root
));
477 assert_spin_locked(&resv_lock
);
479 if (RB_EMPTY_ROOT(root
)) {
481 * Easiest case - empty tree. We can just take
482 * whatever window of free bits we want.
484 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
485 resmap
->m_bitmap_len
- goal
,
489 * This should never happen - the local alloc window
490 * will always have free bits when we're called.
492 BUG_ON(goal
== 0 && clen
== 0);
497 resv
->r_start
= cstart
;
500 ocfs2_resv_insert(resmap
, resv
);
504 prev_resv
= ocfs2_find_resv_lhs(resmap
, goal
);
506 if (prev_resv
== NULL
) {
508 * A NULL here means that the search code couldn't
509 * find a window that starts before goal.
511 * However, we can take the first window after goal,
512 * which is also by definition, the leftmost window in
513 * the entire tree. If we can find free bits in the
514 * gap between goal and the LHS window, then the
515 * reservation can safely be placed there.
517 * Otherwise we fall back to a linear search, checking
518 * the gaps in between windows for a place to
522 next
= rb_first(root
);
523 next_resv
= rb_entry(next
, struct ocfs2_alloc_reservation
,
527 * The search should never return such a window. (see
530 if (next_resv
->r_start
<= goal
) {
531 mlog(ML_ERROR
, "goal: %u next_resv: start %u len %u\n",
532 goal
, next_resv
->r_start
, next_resv
->r_len
);
533 ocfs2_dump_resv(resmap
);
537 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
538 next_resv
->r_start
- goal
,
543 if (best_len
== wanted
)
547 prev_resv
= next_resv
;
551 trace_ocfs2_resv_find_window_prev(prev_resv
->r_start
,
552 ocfs2_resv_end(prev_resv
));
554 prev
= &prev_resv
->r_node
;
556 /* Now we do a linear search for a window, starting at 'prev_rsv' */
558 next
= rb_next(prev
);
560 next_resv
= rb_entry(next
,
561 struct ocfs2_alloc_reservation
,
564 gap_start
= ocfs2_resv_end(prev_resv
) + 1;
565 gap_end
= next_resv
->r_start
- 1;
566 gap_len
= gap_end
- gap_start
+ 1;
569 * We're at the rightmost edge of the
570 * tree. See if a reservation between this
571 * window and the end of the bitmap will work.
573 gap_start
= ocfs2_resv_end(prev_resv
) + 1;
574 gap_len
= resmap
->m_bitmap_len
- gap_start
;
575 gap_end
= resmap
->m_bitmap_len
- 1;
578 trace_ocfs2_resv_find_window_next(next
? next_resv
->r_start
: -1,
579 next
? ocfs2_resv_end(next_resv
) : -1);
581 * No need to check this gap if we have already found
582 * a larger region of free bits.
584 if (gap_len
<= best_len
)
587 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, gap_start
,
588 gap_len
, &cstart
, &clen
);
589 if (clen
== wanted
) {
593 } else if (clen
> best_len
) {
603 prev_resv
= rb_entry(prev
, struct ocfs2_alloc_reservation
,
609 resv
->r_start
= best_start
;
610 resv
->r_len
= best_len
;
611 ocfs2_resv_insert(resmap
, resv
);
615 static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map
*resmap
,
616 struct ocfs2_alloc_reservation
*resv
,
619 struct ocfs2_alloc_reservation
*lru_resv
;
620 int tmpwindow
= !!(resv
->r_flags
& OCFS2_RESV_FLAG_TMP
);
621 unsigned int min_bits
;
624 min_bits
= ocfs2_resv_window_bits(resmap
, resv
) >> 1;
626 min_bits
= wanted
; /* We at know the temp window will use all
630 * Take the first reservation off the LRU as our 'target'. We
631 * don't try to be smart about it. There might be a case for
632 * searching based on size but I don't have enough data to be
633 * sure. --Mark (3/16/2010)
635 lru_resv
= list_first_entry(&resmap
->m_lru
,
636 struct ocfs2_alloc_reservation
, r_lru
);
638 trace_ocfs2_cannibalize_resv_begin(lru_resv
->r_start
,
640 ocfs2_resv_end(lru_resv
));
643 * Cannibalize (some or all) of the target reservation and
644 * feed it to the current window.
646 if (lru_resv
->r_len
<= min_bits
) {
648 * Discard completely if size is less than or equal to a
649 * reasonable threshold - 50% of window bits for non temporary
652 resv
->r_start
= lru_resv
->r_start
;
653 resv
->r_len
= lru_resv
->r_len
;
655 __ocfs2_resv_discard(resmap
, lru_resv
);
661 shrink
= lru_resv
->r_len
/ 2;
663 lru_resv
->r_len
-= shrink
;
665 resv
->r_start
= ocfs2_resv_end(lru_resv
) + 1;
666 resv
->r_len
= shrink
;
669 trace_ocfs2_cannibalize_resv_end(resv
->r_start
, ocfs2_resv_end(resv
),
670 resv
->r_len
, resv
->r_last_start
,
673 ocfs2_resv_insert(resmap
, resv
);
676 static void ocfs2_resv_find_window(struct ocfs2_reservation_map
*resmap
,
677 struct ocfs2_alloc_reservation
*resv
,
680 unsigned int goal
= 0;
682 BUG_ON(!ocfs2_resv_empty(resv
));
685 * Begin by trying to get a window as close to the previous
686 * one as possible. Using the most recent allocation as a
687 * start goal makes sense.
689 if (resv
->r_last_len
) {
690 goal
= resv
->r_last_start
+ resv
->r_last_len
;
691 if (goal
>= resmap
->m_bitmap_len
)
695 __ocfs2_resv_find_window(resmap
, resv
, goal
, wanted
);
697 /* Search from last alloc didn't work, try once more from beginning. */
698 if (ocfs2_resv_empty(resv
) && goal
!= 0)
699 __ocfs2_resv_find_window(resmap
, resv
, 0, wanted
);
701 if (ocfs2_resv_empty(resv
)) {
703 * Still empty? Pull oldest one off the LRU, remove it from
704 * tree, put this one in it's place.
706 ocfs2_cannibalize_resv(resmap
, resv
, wanted
);
709 BUG_ON(ocfs2_resv_empty(resv
));
712 int ocfs2_resmap_resv_bits(struct ocfs2_reservation_map
*resmap
,
713 struct ocfs2_alloc_reservation
*resv
,
714 int *cstart
, int *clen
)
716 if (resv
== NULL
|| ocfs2_resmap_disabled(resmap
))
719 spin_lock(&resv_lock
);
721 if (ocfs2_resv_empty(resv
)) {
723 * We don't want to over-allocate for temporary
724 * windows. Otherwise, we run the risk of fragmenting the
727 unsigned int wanted
= ocfs2_resv_window_bits(resmap
, resv
);
729 if ((resv
->r_flags
& OCFS2_RESV_FLAG_TMP
) || wanted
< *clen
)
733 * Try to get a window here. If it works, we must fall
734 * through and test the bitmap . This avoids some
735 * ping-ponging of windows due to non-reserved space
736 * being allocation before we initialize a window for
739 ocfs2_resv_find_window(resmap
, resv
, wanted
);
740 trace_ocfs2_resmap_resv_bits(resv
->r_start
, resv
->r_len
);
743 BUG_ON(ocfs2_resv_empty(resv
));
745 *cstart
= resv
->r_start
;
748 spin_unlock(&resv_lock
);
753 ocfs2_adjust_resv_from_alloc(struct ocfs2_reservation_map
*resmap
,
754 struct ocfs2_alloc_reservation
*resv
,
755 unsigned int start
, unsigned int end
)
757 unsigned int rhs
= 0;
758 unsigned int old_end
= ocfs2_resv_end(resv
);
760 BUG_ON(start
!= resv
->r_start
|| old_end
< end
);
763 * Completely used? We can remove it then.
765 if (old_end
== end
) {
766 __ocfs2_resv_discard(resmap
, resv
);
773 * This should have been trapped above.
777 resv
->r_start
= end
+ 1;
778 resv
->r_len
= old_end
- resv
->r_start
+ 1;
781 void ocfs2_resmap_claimed_bits(struct ocfs2_reservation_map
*resmap
,
782 struct ocfs2_alloc_reservation
*resv
,
783 u32 cstart
, u32 clen
)
785 unsigned int cend
= cstart
+ clen
- 1;
787 if (resmap
== NULL
|| ocfs2_resmap_disabled(resmap
))
793 BUG_ON(cstart
!= resv
->r_start
);
795 spin_lock(&resv_lock
);
797 trace_ocfs2_resmap_claimed_bits_begin(cstart
, cend
, clen
, resv
->r_start
,
798 ocfs2_resv_end(resv
), resv
->r_len
,
802 BUG_ON(cstart
< resv
->r_start
);
803 BUG_ON(cstart
> ocfs2_resv_end(resv
));
804 BUG_ON(cend
> ocfs2_resv_end(resv
));
806 ocfs2_adjust_resv_from_alloc(resmap
, resv
, cstart
, cend
);
807 resv
->r_last_start
= cstart
;
808 resv
->r_last_len
= clen
;
811 * May have been discarded above from
812 * ocfs2_adjust_resv_from_alloc().
814 if (!ocfs2_resv_empty(resv
))
815 ocfs2_resv_mark_lru(resmap
, resv
);
817 trace_ocfs2_resmap_claimed_bits_end(resv
->r_start
, ocfs2_resv_end(resv
),
818 resv
->r_len
, resv
->r_last_start
,
821 ocfs2_check_resmap(resmap
);
823 spin_unlock(&resv_lock
);