1 /* -*- mode: c; c-basic-offset: 8; -*-
2 * vim: noexpandtab sw=8 ts=8 sts=0:
6 * Allocation reservations implementation
8 * Some code borrowed from fs/ext3/balloc.c and is:
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)
15 * The rest is copyright (C) 2010 Novell. All rights reserved.
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.
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.
28 #include <linux/types.h>
29 #include <linux/highmem.h>
30 #include <linux/bitops.h>
31 #include <linux/list.h>
33 #include <cluster/masklog.h>
36 #include "ocfs2_trace.h"
38 #ifdef CONFIG_OCFS2_DEBUG_FS
39 #define OCFS2_CHECK_RESERVATIONS
42 static DEFINE_SPINLOCK(resv_lock
);
44 #define OCFS2_MIN_RESV_WINDOW_BITS 8
45 #define OCFS2_MAX_RESV_WINDOW_BITS 1024
47 int ocfs2_dir_resv_allowed(struct ocfs2_super
*osb
)
49 return (osb
->osb_resv_level
&& osb
->osb_dir_resv_level
);
52 static unsigned int ocfs2_resv_window_bits(struct ocfs2_reservation_map
*resmap
,
53 struct ocfs2_alloc_reservation
*resv
)
55 struct ocfs2_super
*osb
= resmap
->m_osb
;
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
;
62 bits
= 4 << osb
->osb_dir_resv_level
;
67 static inline unsigned int ocfs2_resv_end(struct ocfs2_alloc_reservation
*resv
)
70 return resv
->r_start
+ resv
->r_len
- 1;
74 static inline int ocfs2_resv_empty(struct ocfs2_alloc_reservation
*resv
)
76 return !!(resv
->r_len
== 0);
79 static inline int ocfs2_resmap_disabled(struct ocfs2_reservation_map
*resmap
)
81 if (resmap
->m_osb
->osb_resv_level
== 0)
86 static void ocfs2_dump_resv(struct ocfs2_reservation_map
*resmap
)
88 struct ocfs2_super
*osb
= resmap
->m_osb
;
90 struct ocfs2_alloc_reservation
*resv
;
93 mlog(ML_NOTICE
, "Dumping resmap for device %s. Bitmap length: %u\n",
94 osb
->dev_str
, resmap
->m_bitmap_len
);
96 node
= rb_first(&resmap
->m_reservations
);
98 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
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
,
105 node
= rb_next(node
);
109 mlog(ML_NOTICE
, "%d reservations found. LRU follows\n", i
);
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
,
122 #ifdef OCFS2_CHECK_RESERVATIONS
123 static int ocfs2_validate_resmap_bits(struct ocfs2_reservation_map
*resmap
,
125 struct ocfs2_alloc_reservation
*resv
)
127 char *disk_bitmap
= resmap
->m_disk_bitmap
;
128 unsigned int start
= resv
->r_start
;
129 unsigned int end
= ocfs2_resv_end(resv
);
131 while (start
<= end
) {
132 if (ocfs2_test_bit(start
, disk_bitmap
)) {
134 "reservation %d covers an allocated area "
135 "starting at bit %u!\n", i
, start
);
144 static void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
146 unsigned int off
= 0;
148 struct rb_node
*node
;
149 struct ocfs2_alloc_reservation
*resv
;
151 node
= rb_first(&resmap
->m_reservations
);
153 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
155 if (i
> 0 && resv
->r_start
<= off
) {
156 mlog(ML_ERROR
, "reservation %d has bad start off!\n",
161 if (resv
->r_len
== 0) {
162 mlog(ML_ERROR
, "reservation %d has no length!\n",
167 if (resv
->r_start
> ocfs2_resv_end(resv
)) {
168 mlog(ML_ERROR
, "reservation %d has invalid range!\n",
173 if (ocfs2_resv_end(resv
) >= resmap
->m_bitmap_len
) {
174 mlog(ML_ERROR
, "reservation %d extends past bitmap!\n",
179 if (ocfs2_validate_resmap_bits(resmap
, i
, resv
))
182 off
= ocfs2_resv_end(resv
);
183 node
= rb_next(node
);
190 ocfs2_dump_resv(resmap
);
194 static inline void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
200 void ocfs2_resv_init_once(struct ocfs2_alloc_reservation
*resv
)
202 memset(resv
, 0, sizeof(*resv
));
203 INIT_LIST_HEAD(&resv
->r_lru
);
206 void ocfs2_resv_set_type(struct ocfs2_alloc_reservation
*resv
,
209 BUG_ON(flags
& ~OCFS2_RESV_TYPES
);
211 resv
->r_flags
|= flags
;
214 int ocfs2_resmap_init(struct ocfs2_super
*osb
,
215 struct ocfs2_reservation_map
*resmap
)
217 memset(resmap
, 0, sizeof(*resmap
));
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
);
227 static void ocfs2_resv_mark_lru(struct ocfs2_reservation_map
*resmap
,
228 struct ocfs2_alloc_reservation
*resv
)
230 assert_spin_locked(&resv_lock
);
232 if (!list_empty(&resv
->r_lru
))
233 list_del_init(&resv
->r_lru
);
235 list_add_tail(&resv
->r_lru
, &resmap
->m_lru
);
238 static void __ocfs2_resv_trunc(struct ocfs2_alloc_reservation
*resv
)
244 static void ocfs2_resv_remove(struct ocfs2_reservation_map
*resmap
,
245 struct ocfs2_alloc_reservation
*resv
)
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
;
254 static void __ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
255 struct ocfs2_alloc_reservation
*resv
)
257 assert_spin_locked(&resv_lock
);
259 __ocfs2_resv_trunc(resv
);
261 * last_len and last_start no longer make sense if
262 * we're changing the range of our allocations.
264 resv
->r_last_len
= resv
->r_last_start
= 0;
266 ocfs2_resv_remove(resmap
, resv
);
269 /* does nothing if 'resv' is null */
270 void ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
271 struct ocfs2_alloc_reservation
*resv
)
274 spin_lock(&resv_lock
);
275 __ocfs2_resv_discard(resmap
, resv
);
276 spin_unlock(&resv_lock
);
280 static void ocfs2_resmap_clear_all_resv(struct ocfs2_reservation_map
*resmap
)
282 struct rb_node
*node
;
283 struct ocfs2_alloc_reservation
*resv
;
285 assert_spin_locked(&resv_lock
);
287 while ((node
= rb_last(&resmap
->m_reservations
)) != NULL
) {
288 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
290 __ocfs2_resv_discard(resmap
, resv
);
294 void ocfs2_resmap_restart(struct ocfs2_reservation_map
*resmap
,
295 unsigned int clen
, char *disk_bitmap
)
297 if (ocfs2_resmap_disabled(resmap
))
300 spin_lock(&resv_lock
);
302 ocfs2_resmap_clear_all_resv(resmap
);
303 resmap
->m_bitmap_len
= clen
;
304 resmap
->m_disk_bitmap
= disk_bitmap
;
306 spin_unlock(&resv_lock
);
309 void ocfs2_resmap_uninit(struct ocfs2_reservation_map
*resmap
)
311 /* Does nothing for now. Keep this around for API symmetry */
314 static void ocfs2_resv_insert(struct ocfs2_reservation_map
*resmap
,
315 struct ocfs2_alloc_reservation
*new)
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
;
322 assert_spin_locked(&resv_lock
);
324 trace_ocfs2_resv_insert(new->r_start
, new->r_len
);
329 tmp
= rb_entry(parent
, struct ocfs2_alloc_reservation
, r_node
);
331 if (new->r_start
< tmp
->r_start
) {
335 * This is a good place to check for
336 * overlapping reservations.
338 BUG_ON(ocfs2_resv_end(new) >= tmp
->r_start
);
339 } else if (new->r_start
> ocfs2_resv_end(tmp
)) {
342 /* This should never happen! */
343 mlog(ML_ERROR
, "Duplicate reservation window!\n");
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
;
352 ocfs2_resv_mark_lru(resmap
, new);
354 ocfs2_check_resmap(resmap
);
358 * ocfs2_find_resv_lhs() - find the window which contains goal
359 * @resmap: reservation map to search
360 * @goal: which bit to search for
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
366 static struct ocfs2_alloc_reservation
*
367 ocfs2_find_resv_lhs(struct ocfs2_reservation_map
*resmap
, unsigned int goal
)
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
;
373 assert_spin_locked(&resv_lock
);
378 node
= rb_first(&resmap
->m_reservations
);
380 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
382 if (resv
->r_start
<= goal
&& ocfs2_resv_end(resv
) >= goal
)
385 /* Check if we overshot the reservation just before goal? */
386 if (resv
->r_start
> goal
) {
392 node
= rb_next(node
);
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
404 * The start value of *rstart is insignificant.
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.
410 * Returns the length of allocation, 0 if no free bits are found.
412 * *cstart and *clen will also be populated with the result.
414 static int ocfs2_resmap_find_free_bits(struct ocfs2_reservation_map
*resmap
,
416 unsigned int search_start
,
417 unsigned int search_len
,
418 unsigned int *rstart
,
421 void *bitmap
= resmap
->m_disk_bitmap
;
422 unsigned int best_start
, best_len
= 0;
423 int offset
, start
, found
;
425 trace_ocfs2_resmap_find_free_bits_begin(search_start
, search_len
,
426 wanted
, resmap
->m_bitmap_len
);
428 found
= best_start
= best_len
= 0;
430 start
= search_start
;
431 while ((offset
= ocfs2_find_next_zero_bit(bitmap
, resmap
->m_bitmap_len
,
433 /* Search reached end of the region */
434 if (offset
>= (search_start
+ search_len
))
437 if (offset
== start
) {
438 /* we found a zero */
440 /* move start to the next bit to test */
443 /* got a zero after some ones */
447 if (found
> best_len
) {
449 best_start
= start
- found
;
459 if (best_len
>= wanted
)
463 *rstart
= best_start
;
465 trace_ocfs2_resmap_find_free_bits_end(best_start
, best_len
);
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
)
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;
482 * Nasty cases to consider:
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
489 trace_ocfs2_resv_find_window_begin(resv
->r_start
, ocfs2_resv_end(resv
),
490 goal
, wanted
, RB_EMPTY_ROOT(root
));
492 assert_spin_locked(&resv_lock
);
494 if (RB_EMPTY_ROOT(root
)) {
496 * Easiest case - empty tree. We can just take
497 * whatever window of free bits we want.
499 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
500 resmap
->m_bitmap_len
- goal
,
504 * This should never happen - the local alloc window
505 * will always have free bits when we're called.
507 BUG_ON(goal
== 0 && clen
== 0);
512 resv
->r_start
= cstart
;
515 ocfs2_resv_insert(resmap
, resv
);
519 prev_resv
= ocfs2_find_resv_lhs(resmap
, goal
);
521 if (prev_resv
== NULL
) {
523 * A NULL here means that the search code couldn't
524 * find a window that starts before goal.
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.
532 * Otherwise we fall back to a linear search, checking
533 * the gaps in between windows for a place to
537 next
= rb_first(root
);
538 next_resv
= rb_entry(next
, struct ocfs2_alloc_reservation
,
542 * The search should never return such a window. (see
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
);
552 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
553 next_resv
->r_start
- goal
,
558 if (best_len
== wanted
)
562 prev_resv
= next_resv
;
566 trace_ocfs2_resv_find_window_prev(prev_resv
->r_start
,
567 ocfs2_resv_end(prev_resv
));
569 prev
= &prev_resv
->r_node
;
571 /* Now we do a linear search for a window, starting at 'prev_rsv' */
573 next
= rb_next(prev
);
575 next_resv
= rb_entry(next
,
576 struct ocfs2_alloc_reservation
,
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;
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.
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;
593 trace_ocfs2_resv_find_window_next(next
? next_resv
->r_start
: -1,
594 next
? ocfs2_resv_end(next_resv
) : -1);
596 * No need to check this gap if we have already found
597 * a larger region of free bits.
599 if (gap_len
<= best_len
)
602 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, gap_start
,
603 gap_len
, &cstart
, &clen
);
604 if (clen
== wanted
) {
608 } else if (clen
> best_len
) {
618 prev_resv
= rb_entry(prev
, struct ocfs2_alloc_reservation
,
624 resv
->r_start
= best_start
;
625 resv
->r_len
= best_len
;
626 ocfs2_resv_insert(resmap
, resv
);
630 static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map
*resmap
,
631 struct ocfs2_alloc_reservation
*resv
,
634 struct ocfs2_alloc_reservation
*lru_resv
;
635 int tmpwindow
= !!(resv
->r_flags
& OCFS2_RESV_FLAG_TMP
);
636 unsigned int min_bits
;
639 min_bits
= ocfs2_resv_window_bits(resmap
, resv
) >> 1;
641 min_bits
= wanted
; /* We at know the temp window will use all
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)
650 lru_resv
= list_first_entry(&resmap
->m_lru
,
651 struct ocfs2_alloc_reservation
, r_lru
);
653 trace_ocfs2_cannibalize_resv_begin(lru_resv
->r_start
,
655 ocfs2_resv_end(lru_resv
));
658 * Cannibalize (some or all) of the target reservation and
659 * feed it to the current window.
661 if (lru_resv
->r_len
<= min_bits
) {
663 * Discard completely if size is less than or equal to a
664 * reasonable threshold - 50% of window bits for non temporary
667 resv
->r_start
= lru_resv
->r_start
;
668 resv
->r_len
= lru_resv
->r_len
;
670 __ocfs2_resv_discard(resmap
, lru_resv
);
676 shrink
= lru_resv
->r_len
/ 2;
678 lru_resv
->r_len
-= shrink
;
680 resv
->r_start
= ocfs2_resv_end(lru_resv
) + 1;
681 resv
->r_len
= shrink
;
684 trace_ocfs2_cannibalize_resv_end(resv
->r_start
, ocfs2_resv_end(resv
),
685 resv
->r_len
, resv
->r_last_start
,
688 ocfs2_resv_insert(resmap
, resv
);
691 static void ocfs2_resv_find_window(struct ocfs2_reservation_map
*resmap
,
692 struct ocfs2_alloc_reservation
*resv
,
695 unsigned int goal
= 0;
697 BUG_ON(!ocfs2_resv_empty(resv
));
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.
704 if (resv
->r_last_len
) {
705 goal
= resv
->r_last_start
+ resv
->r_last_len
;
706 if (goal
>= resmap
->m_bitmap_len
)
710 __ocfs2_resv_find_window(resmap
, resv
, goal
, wanted
);
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
);
716 if (ocfs2_resv_empty(resv
)) {
718 * Still empty? Pull oldest one off the LRU, remove it from
719 * tree, put this one in it's place.
721 ocfs2_cannibalize_resv(resmap
, resv
, wanted
);
724 BUG_ON(ocfs2_resv_empty(resv
));
727 int ocfs2_resmap_resv_bits(struct ocfs2_reservation_map
*resmap
,
728 struct ocfs2_alloc_reservation
*resv
,
729 int *cstart
, int *clen
)
731 if (resv
== NULL
|| ocfs2_resmap_disabled(resmap
))
734 spin_lock(&resv_lock
);
736 if (ocfs2_resv_empty(resv
)) {
738 * We don't want to over-allocate for temporary
739 * windows. Otherwise, we run the risk of fragmenting the
742 unsigned int wanted
= ocfs2_resv_window_bits(resmap
, resv
);
744 if ((resv
->r_flags
& OCFS2_RESV_FLAG_TMP
) || wanted
< *clen
)
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
754 ocfs2_resv_find_window(resmap
, resv
, wanted
);
755 trace_ocfs2_resmap_resv_bits(resv
->r_start
, resv
->r_len
);
758 BUG_ON(ocfs2_resv_empty(resv
));
760 *cstart
= resv
->r_start
;
763 spin_unlock(&resv_lock
);
768 ocfs2_adjust_resv_from_alloc(struct ocfs2_reservation_map
*resmap
,
769 struct ocfs2_alloc_reservation
*resv
,
770 unsigned int start
, unsigned int end
)
772 unsigned int rhs
= 0;
773 unsigned int old_end
= ocfs2_resv_end(resv
);
775 BUG_ON(start
!= resv
->r_start
|| old_end
< end
);
778 * Completely used? We can remove it then.
780 if (old_end
== end
) {
781 __ocfs2_resv_discard(resmap
, resv
);
788 * This should have been trapped above.
792 resv
->r_start
= end
+ 1;
793 resv
->r_len
= old_end
- resv
->r_start
+ 1;
796 void ocfs2_resmap_claimed_bits(struct ocfs2_reservation_map
*resmap
,
797 struct ocfs2_alloc_reservation
*resv
,
798 u32 cstart
, u32 clen
)
800 unsigned int cend
= cstart
+ clen
- 1;
802 if (resmap
== NULL
|| ocfs2_resmap_disabled(resmap
))
808 BUG_ON(cstart
!= resv
->r_start
);
810 spin_lock(&resv_lock
);
812 trace_ocfs2_resmap_claimed_bits_begin(cstart
, cend
, clen
, resv
->r_start
,
813 ocfs2_resv_end(resv
), resv
->r_len
,
817 BUG_ON(cstart
< resv
->r_start
);
818 BUG_ON(cstart
> ocfs2_resv_end(resv
));
819 BUG_ON(cend
> ocfs2_resv_end(resv
));
821 ocfs2_adjust_resv_from_alloc(resmap
, resv
, cstart
, cend
);
822 resv
->r_last_start
= cstart
;
823 resv
->r_last_len
= clen
;
826 * May have been discarded above from
827 * ocfs2_adjust_resv_from_alloc().
829 if (!ocfs2_resv_empty(resv
))
830 ocfs2_resv_mark_lru(resmap
, resv
);
832 trace_ocfs2_resmap_claimed_bits_end(resv
->r_start
, ocfs2_resv_end(resv
),
833 resv
->r_len
, resv
->r_last_start
,
836 ocfs2_check_resmap(resmap
);
838 spin_unlock(&resv_lock
);
This page took 0.046378 seconds and 5 git commands to generate.