1 // SPDX-License-Identifier: GPL-2.0-only
2 /* -*- mode: c; c-basic-offset: 8; -*-
3 * vim: noexpandtab sw=8 ts=8 sts=0:
7 * Allocation reservations implementation
9 * Some code borrowed from fs/ext3/balloc.c and is:
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)
16 * The rest is copyright (C) 2010 Novell. All rights reserved.
20 #include <linux/types.h>
21 #include <linux/highmem.h>
22 #include <linux/bitops.h>
23 #include <linux/list.h>
25 #include <cluster/masklog.h>
28 #include "ocfs2_trace.h"
30 #ifdef CONFIG_OCFS2_DEBUG_FS
31 #define OCFS2_CHECK_RESERVATIONS
34 static DEFINE_SPINLOCK(resv_lock
);
36 #define OCFS2_MIN_RESV_WINDOW_BITS 8
37 #define OCFS2_MAX_RESV_WINDOW_BITS 1024
39 int ocfs2_dir_resv_allowed(struct ocfs2_super
*osb
)
41 return (osb
->osb_resv_level
&& osb
->osb_dir_resv_level
);
44 static unsigned int ocfs2_resv_window_bits(struct ocfs2_reservation_map
*resmap
,
45 struct ocfs2_alloc_reservation
*resv
)
47 struct ocfs2_super
*osb
= resmap
->m_osb
;
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
;
54 bits
= 4 << osb
->osb_dir_resv_level
;
59 static inline unsigned int ocfs2_resv_end(struct ocfs2_alloc_reservation
*resv
)
62 return resv
->r_start
+ resv
->r_len
- 1;
66 static inline int ocfs2_resv_empty(struct ocfs2_alloc_reservation
*resv
)
68 return !!(resv
->r_len
== 0);
71 static inline int ocfs2_resmap_disabled(struct ocfs2_reservation_map
*resmap
)
73 if (resmap
->m_osb
->osb_resv_level
== 0)
78 static void ocfs2_dump_resv(struct ocfs2_reservation_map
*resmap
)
80 struct ocfs2_super
*osb
= resmap
->m_osb
;
82 struct ocfs2_alloc_reservation
*resv
;
85 mlog(ML_NOTICE
, "Dumping resmap for device %s. Bitmap length: %u\n",
86 osb
->dev_str
, resmap
->m_bitmap_len
);
88 node
= rb_first(&resmap
->m_reservations
);
90 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
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
,
101 mlog(ML_NOTICE
, "%d reservations found. LRU follows\n", i
);
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
,
114 #ifdef OCFS2_CHECK_RESERVATIONS
115 static int ocfs2_validate_resmap_bits(struct ocfs2_reservation_map
*resmap
,
117 struct ocfs2_alloc_reservation
*resv
)
119 char *disk_bitmap
= resmap
->m_disk_bitmap
;
120 unsigned int start
= resv
->r_start
;
121 unsigned int end
= ocfs2_resv_end(resv
);
123 while (start
<= end
) {
124 if (ocfs2_test_bit(start
, disk_bitmap
)) {
126 "reservation %d covers an allocated area "
127 "starting at bit %u!\n", i
, start
);
136 static void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
138 unsigned int off
= 0;
140 struct rb_node
*node
;
141 struct ocfs2_alloc_reservation
*resv
;
143 node
= rb_first(&resmap
->m_reservations
);
145 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
147 if (i
> 0 && resv
->r_start
<= off
) {
148 mlog(ML_ERROR
, "reservation %d has bad start off!\n",
153 if (resv
->r_len
== 0) {
154 mlog(ML_ERROR
, "reservation %d has no length!\n",
159 if (resv
->r_start
> ocfs2_resv_end(resv
)) {
160 mlog(ML_ERROR
, "reservation %d has invalid range!\n",
165 if (ocfs2_resv_end(resv
) >= resmap
->m_bitmap_len
) {
166 mlog(ML_ERROR
, "reservation %d extends past bitmap!\n",
171 if (ocfs2_validate_resmap_bits(resmap
, i
, resv
))
174 off
= ocfs2_resv_end(resv
);
175 node
= rb_next(node
);
182 ocfs2_dump_resv(resmap
);
186 static inline void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
192 void ocfs2_resv_init_once(struct ocfs2_alloc_reservation
*resv
)
194 memset(resv
, 0, sizeof(*resv
));
195 INIT_LIST_HEAD(&resv
->r_lru
);
198 void ocfs2_resv_set_type(struct ocfs2_alloc_reservation
*resv
,
201 BUG_ON(flags
& ~OCFS2_RESV_TYPES
);
203 resv
->r_flags
|= flags
;
206 int ocfs2_resmap_init(struct ocfs2_super
*osb
,
207 struct ocfs2_reservation_map
*resmap
)
209 memset(resmap
, 0, sizeof(*resmap
));
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
);
219 static void ocfs2_resv_mark_lru(struct ocfs2_reservation_map
*resmap
,
220 struct ocfs2_alloc_reservation
*resv
)
222 assert_spin_locked(&resv_lock
);
224 if (!list_empty(&resv
->r_lru
))
225 list_del_init(&resv
->r_lru
);
227 list_add_tail(&resv
->r_lru
, &resmap
->m_lru
);
230 static void __ocfs2_resv_trunc(struct ocfs2_alloc_reservation
*resv
)
236 static void ocfs2_resv_remove(struct ocfs2_reservation_map
*resmap
,
237 struct ocfs2_alloc_reservation
*resv
)
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
;
246 static void __ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
247 struct ocfs2_alloc_reservation
*resv
)
249 assert_spin_locked(&resv_lock
);
251 __ocfs2_resv_trunc(resv
);
253 * last_len and last_start no longer make sense if
254 * we're changing the range of our allocations.
256 resv
->r_last_len
= resv
->r_last_start
= 0;
258 ocfs2_resv_remove(resmap
, resv
);
261 /* does nothing if 'resv' is null */
262 void ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
263 struct ocfs2_alloc_reservation
*resv
)
266 spin_lock(&resv_lock
);
267 __ocfs2_resv_discard(resmap
, resv
);
268 spin_unlock(&resv_lock
);
272 static void ocfs2_resmap_clear_all_resv(struct ocfs2_reservation_map
*resmap
)
274 struct rb_node
*node
;
275 struct ocfs2_alloc_reservation
*resv
;
277 assert_spin_locked(&resv_lock
);
279 while ((node
= rb_last(&resmap
->m_reservations
)) != NULL
) {
280 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
282 __ocfs2_resv_discard(resmap
, resv
);
286 void ocfs2_resmap_restart(struct ocfs2_reservation_map
*resmap
,
287 unsigned int clen
, char *disk_bitmap
)
289 if (ocfs2_resmap_disabled(resmap
))
292 spin_lock(&resv_lock
);
294 ocfs2_resmap_clear_all_resv(resmap
);
295 resmap
->m_bitmap_len
= clen
;
296 resmap
->m_disk_bitmap
= disk_bitmap
;
298 spin_unlock(&resv_lock
);
301 void ocfs2_resmap_uninit(struct ocfs2_reservation_map
*resmap
)
303 /* Does nothing for now. Keep this around for API symmetry */
306 static void ocfs2_resv_insert(struct ocfs2_reservation_map
*resmap
,
307 struct ocfs2_alloc_reservation
*new)
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
;
314 assert_spin_locked(&resv_lock
);
316 trace_ocfs2_resv_insert(new->r_start
, new->r_len
);
321 tmp
= rb_entry(parent
, struct ocfs2_alloc_reservation
, r_node
);
323 if (new->r_start
< tmp
->r_start
) {
327 * This is a good place to check for
328 * overlapping reservations.
330 BUG_ON(ocfs2_resv_end(new) >= tmp
->r_start
);
331 } else if (new->r_start
> ocfs2_resv_end(tmp
)) {
334 /* This should never happen! */
335 mlog(ML_ERROR
, "Duplicate reservation window!\n");
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
;
344 ocfs2_resv_mark_lru(resmap
, new);
346 ocfs2_check_resmap(resmap
);
350 * ocfs2_find_resv_lhs() - find the window which contains goal
351 * @resmap: reservation map to search
352 * @goal: which bit to search for
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
358 static struct ocfs2_alloc_reservation
*
359 ocfs2_find_resv_lhs(struct ocfs2_reservation_map
*resmap
, unsigned int goal
)
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
;
365 assert_spin_locked(&resv_lock
);
370 node
= rb_first(&resmap
->m_reservations
);
372 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
374 if (resv
->r_start
<= goal
&& ocfs2_resv_end(resv
) >= goal
)
377 /* Check if we overshot the reservation just before goal? */
378 if (resv
->r_start
> goal
) {
384 node
= rb_next(node
);
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
396 * The start value of *rstart is insignificant.
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.
402 * Returns the length of allocation, 0 if no free bits are found.
404 * *cstart and *clen will also be populated with the result.
406 static int ocfs2_resmap_find_free_bits(struct ocfs2_reservation_map
*resmap
,
408 unsigned int search_start
,
409 unsigned int search_len
,
410 unsigned int *rstart
,
413 void *bitmap
= resmap
->m_disk_bitmap
;
414 unsigned int best_start
, best_len
= 0;
415 int offset
, start
, found
;
417 trace_ocfs2_resmap_find_free_bits_begin(search_start
, search_len
,
418 wanted
, resmap
->m_bitmap_len
);
420 found
= best_start
= best_len
= 0;
422 start
= search_start
;
423 while ((offset
= ocfs2_find_next_zero_bit(bitmap
, resmap
->m_bitmap_len
,
425 /* Search reached end of the region */
426 if (offset
>= (search_start
+ search_len
))
429 if (offset
== start
) {
430 /* we found a zero */
432 /* move start to the next bit to test */
435 /* got a zero after some ones */
439 if (found
> best_len
) {
441 best_start
= start
- found
;
451 if (best_len
>= wanted
)
455 *rstart
= best_start
;
457 trace_ocfs2_resmap_find_free_bits_end(best_start
, best_len
);
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
)
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;
474 * Nasty cases to consider:
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
481 trace_ocfs2_resv_find_window_begin(resv
->r_start
, ocfs2_resv_end(resv
),
482 goal
, wanted
, RB_EMPTY_ROOT(root
));
484 assert_spin_locked(&resv_lock
);
486 if (RB_EMPTY_ROOT(root
)) {
488 * Easiest case - empty tree. We can just take
489 * whatever window of free bits we want.
491 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
492 resmap
->m_bitmap_len
- goal
,
496 * This should never happen - the local alloc window
497 * will always have free bits when we're called.
499 BUG_ON(goal
== 0 && clen
== 0);
504 resv
->r_start
= cstart
;
507 ocfs2_resv_insert(resmap
, resv
);
511 prev_resv
= ocfs2_find_resv_lhs(resmap
, goal
);
513 if (prev_resv
== NULL
) {
515 * A NULL here means that the search code couldn't
516 * find a window that starts before goal.
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.
524 * Otherwise we fall back to a linear search, checking
525 * the gaps in between windows for a place to
529 next
= rb_first(root
);
530 next_resv
= rb_entry(next
, struct ocfs2_alloc_reservation
,
534 * The search should never return such a window. (see
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
);
544 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
545 next_resv
->r_start
- goal
,
550 if (best_len
== wanted
)
554 prev_resv
= next_resv
;
558 trace_ocfs2_resv_find_window_prev(prev_resv
->r_start
,
559 ocfs2_resv_end(prev_resv
));
561 prev
= &prev_resv
->r_node
;
563 /* Now we do a linear search for a window, starting at 'prev_rsv' */
565 next
= rb_next(prev
);
567 next_resv
= rb_entry(next
,
568 struct ocfs2_alloc_reservation
,
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;
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.
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;
585 trace_ocfs2_resv_find_window_next(next
? next_resv
->r_start
: -1,
586 next
? ocfs2_resv_end(next_resv
) : -1);
588 * No need to check this gap if we have already found
589 * a larger region of free bits.
591 if (gap_len
<= best_len
)
594 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, gap_start
,
595 gap_len
, &cstart
, &clen
);
596 if (clen
== wanted
) {
600 } else if (clen
> best_len
) {
610 prev_resv
= rb_entry(prev
, struct ocfs2_alloc_reservation
,
616 resv
->r_start
= best_start
;
617 resv
->r_len
= best_len
;
618 ocfs2_resv_insert(resmap
, resv
);
622 static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map
*resmap
,
623 struct ocfs2_alloc_reservation
*resv
,
626 struct ocfs2_alloc_reservation
*lru_resv
;
627 int tmpwindow
= !!(resv
->r_flags
& OCFS2_RESV_FLAG_TMP
);
628 unsigned int min_bits
;
631 min_bits
= ocfs2_resv_window_bits(resmap
, resv
) >> 1;
633 min_bits
= wanted
; /* We at know the temp window will use all
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)
642 lru_resv
= list_first_entry(&resmap
->m_lru
,
643 struct ocfs2_alloc_reservation
, r_lru
);
645 trace_ocfs2_cannibalize_resv_begin(lru_resv
->r_start
,
647 ocfs2_resv_end(lru_resv
));
650 * Cannibalize (some or all) of the target reservation and
651 * feed it to the current window.
653 if (lru_resv
->r_len
<= min_bits
) {
655 * Discard completely if size is less than or equal to a
656 * reasonable threshold - 50% of window bits for non temporary
659 resv
->r_start
= lru_resv
->r_start
;
660 resv
->r_len
= lru_resv
->r_len
;
662 __ocfs2_resv_discard(resmap
, lru_resv
);
668 shrink
= lru_resv
->r_len
/ 2;
670 lru_resv
->r_len
-= shrink
;
672 resv
->r_start
= ocfs2_resv_end(lru_resv
) + 1;
673 resv
->r_len
= shrink
;
676 trace_ocfs2_cannibalize_resv_end(resv
->r_start
, ocfs2_resv_end(resv
),
677 resv
->r_len
, resv
->r_last_start
,
680 ocfs2_resv_insert(resmap
, resv
);
683 static void ocfs2_resv_find_window(struct ocfs2_reservation_map
*resmap
,
684 struct ocfs2_alloc_reservation
*resv
,
687 unsigned int goal
= 0;
689 BUG_ON(!ocfs2_resv_empty(resv
));
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.
696 if (resv
->r_last_len
) {
697 goal
= resv
->r_last_start
+ resv
->r_last_len
;
698 if (goal
>= resmap
->m_bitmap_len
)
702 __ocfs2_resv_find_window(resmap
, resv
, goal
, wanted
);
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
);
708 if (ocfs2_resv_empty(resv
)) {
710 * Still empty? Pull oldest one off the LRU, remove it from
711 * tree, put this one in it's place.
713 ocfs2_cannibalize_resv(resmap
, resv
, wanted
);
716 BUG_ON(ocfs2_resv_empty(resv
));
719 int ocfs2_resmap_resv_bits(struct ocfs2_reservation_map
*resmap
,
720 struct ocfs2_alloc_reservation
*resv
,
721 int *cstart
, int *clen
)
723 if (resv
== NULL
|| ocfs2_resmap_disabled(resmap
))
726 spin_lock(&resv_lock
);
728 if (ocfs2_resv_empty(resv
)) {
730 * We don't want to over-allocate for temporary
731 * windows. Otherwise, we run the risk of fragmenting the
734 unsigned int wanted
= ocfs2_resv_window_bits(resmap
, resv
);
736 if ((resv
->r_flags
& OCFS2_RESV_FLAG_TMP
) || wanted
< *clen
)
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
746 ocfs2_resv_find_window(resmap
, resv
, wanted
);
747 trace_ocfs2_resmap_resv_bits(resv
->r_start
, resv
->r_len
);
750 BUG_ON(ocfs2_resv_empty(resv
));
752 *cstart
= resv
->r_start
;
755 spin_unlock(&resv_lock
);
760 ocfs2_adjust_resv_from_alloc(struct ocfs2_reservation_map
*resmap
,
761 struct ocfs2_alloc_reservation
*resv
,
762 unsigned int start
, unsigned int end
)
764 unsigned int rhs
= 0;
765 unsigned int old_end
= ocfs2_resv_end(resv
);
767 BUG_ON(start
!= resv
->r_start
|| old_end
< end
);
770 * Completely used? We can remove it then.
772 if (old_end
== end
) {
773 __ocfs2_resv_discard(resmap
, resv
);
780 * This should have been trapped above.
784 resv
->r_start
= end
+ 1;
785 resv
->r_len
= old_end
- resv
->r_start
+ 1;
788 void ocfs2_resmap_claimed_bits(struct ocfs2_reservation_map
*resmap
,
789 struct ocfs2_alloc_reservation
*resv
,
790 u32 cstart
, u32 clen
)
792 unsigned int cend
= cstart
+ clen
- 1;
794 if (resmap
== NULL
|| ocfs2_resmap_disabled(resmap
))
800 BUG_ON(cstart
!= resv
->r_start
);
802 spin_lock(&resv_lock
);
804 trace_ocfs2_resmap_claimed_bits_begin(cstart
, cend
, clen
, resv
->r_start
,
805 ocfs2_resv_end(resv
), resv
->r_len
,
809 BUG_ON(cstart
< resv
->r_start
);
810 BUG_ON(cstart
> ocfs2_resv_end(resv
));
811 BUG_ON(cend
> ocfs2_resv_end(resv
));
813 ocfs2_adjust_resv_from_alloc(resmap
, resv
, cstart
, cend
);
814 resv
->r_last_start
= cstart
;
815 resv
->r_last_len
= clen
;
818 * May have been discarded above from
819 * ocfs2_adjust_resv_from_alloc().
821 if (!ocfs2_resv_empty(resv
))
822 ocfs2_resv_mark_lru(resmap
, resv
);
824 trace_ocfs2_resmap_claimed_bits_end(resv
->r_start
, ocfs2_resv_end(resv
),
825 resv
->r_len
, resv
->r_last_start
,
828 ocfs2_check_resmap(resmap
);
830 spin_unlock(&resv_lock
);