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/slab.h>
30 #include <linux/highmem.h>
31 #include <linux/bitops.h>
32 #include <linux/list.h>
34 #define MLOG_MASK_PREFIX ML_RESERVATIONS
35 #include <cluster/masklog.h>
39 #ifdef CONFIG_OCFS2_DEBUG_FS
40 #define OCFS2_CHECK_RESERVATIONS
43 DEFINE_SPINLOCK(resv_lock
);
45 #define OCFS2_MIN_RESV_WINDOW_BITS 8
46 #define OCFS2_MAX_RESV_WINDOW_BITS 1024
48 int ocfs2_dir_resv_allowed(struct ocfs2_super
*osb
)
50 return (osb
->osb_resv_level
&& osb
->osb_dir_resv_level
);
53 static unsigned int ocfs2_resv_window_bits(struct ocfs2_reservation_map
*resmap
,
54 struct ocfs2_alloc_reservation
*resv
)
56 struct ocfs2_super
*osb
= resmap
->m_osb
;
59 if (!(resv
->r_flags
& OCFS2_RESV_FLAG_DIR
)) {
60 /* 8, 16, 32, 64, 128, 256, 512, 1024 */
61 bits
= 4 << osb
->osb_resv_level
;
63 bits
= 4 << osb
->osb_dir_resv_level
;
68 static inline unsigned int ocfs2_resv_end(struct ocfs2_alloc_reservation
*resv
)
71 return resv
->r_start
+ resv
->r_len
- 1;
75 static inline int ocfs2_resv_empty(struct ocfs2_alloc_reservation
*resv
)
77 return !!(resv
->r_len
== 0);
80 static inline int ocfs2_resmap_disabled(struct ocfs2_reservation_map
*resmap
)
82 if (resmap
->m_osb
->osb_resv_level
== 0)
87 static void ocfs2_dump_resv(struct ocfs2_reservation_map
*resmap
)
89 struct ocfs2_super
*osb
= resmap
->m_osb
;
91 struct ocfs2_alloc_reservation
*resv
;
94 mlog(ML_NOTICE
, "Dumping resmap for device %s. Bitmap length: %u\n",
95 osb
->dev_str
, resmap
->m_bitmap_len
);
97 node
= rb_first(&resmap
->m_reservations
);
99 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
101 mlog(ML_NOTICE
, "start: %u\tend: %u\tlen: %u\tlast_start: %u"
102 "\tlast_len: %u\n", resv
->r_start
,
103 ocfs2_resv_end(resv
), resv
->r_len
, resv
->r_last_start
,
106 node
= rb_next(node
);
110 mlog(ML_NOTICE
, "%d reservations found. LRU follows\n", i
);
113 list_for_each_entry(resv
, &resmap
->m_lru
, r_lru
) {
114 mlog(ML_NOTICE
, "LRU(%d) start: %u\tend: %u\tlen: %u\t"
115 "last_start: %u\tlast_len: %u\n", i
, resv
->r_start
,
116 ocfs2_resv_end(resv
), resv
->r_len
, resv
->r_last_start
,
123 #ifdef OCFS2_CHECK_RESERVATIONS
124 static int ocfs2_validate_resmap_bits(struct ocfs2_reservation_map
*resmap
,
126 struct ocfs2_alloc_reservation
*resv
)
128 char *disk_bitmap
= resmap
->m_disk_bitmap
;
129 unsigned int start
= resv
->r_start
;
130 unsigned int end
= ocfs2_resv_end(resv
);
132 while (start
<= end
) {
133 if (ocfs2_test_bit(start
, disk_bitmap
)) {
135 "reservation %d covers an allocated area "
136 "starting at bit %u!\n", i
, start
);
145 static void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
147 unsigned int off
= 0;
149 struct rb_node
*node
;
150 struct ocfs2_alloc_reservation
*resv
;
152 node
= rb_first(&resmap
->m_reservations
);
154 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
156 if (i
> 0 && resv
->r_start
<= off
) {
157 mlog(ML_ERROR
, "reservation %d has bad start off!\n",
162 if (resv
->r_len
== 0) {
163 mlog(ML_ERROR
, "reservation %d has no length!\n",
168 if (resv
->r_start
> ocfs2_resv_end(resv
)) {
169 mlog(ML_ERROR
, "reservation %d has invalid range!\n",
174 if (ocfs2_resv_end(resv
) >= resmap
->m_bitmap_len
) {
175 mlog(ML_ERROR
, "reservation %d extends past bitmap!\n",
180 if (ocfs2_validate_resmap_bits(resmap
, i
, resv
))
183 off
= ocfs2_resv_end(resv
);
184 node
= rb_next(node
);
191 ocfs2_dump_resv(resmap
);
195 static inline void ocfs2_check_resmap(struct ocfs2_reservation_map
*resmap
)
201 void ocfs2_resv_init_once(struct ocfs2_alloc_reservation
*resv
)
203 memset(resv
, 0, sizeof(*resv
));
204 INIT_LIST_HEAD(&resv
->r_lru
);
207 void ocfs2_resv_set_type(struct ocfs2_alloc_reservation
*resv
,
210 BUG_ON(flags
& ~OCFS2_RESV_TYPES
);
212 resv
->r_flags
|= flags
;
215 int ocfs2_resmap_init(struct ocfs2_super
*osb
,
216 struct ocfs2_reservation_map
*resmap
)
218 memset(resmap
, 0, sizeof(*resmap
));
221 resmap
->m_reservations
= RB_ROOT
;
222 /* m_bitmap_len is initialized to zero by the above memset. */
223 INIT_LIST_HEAD(&resmap
->m_lru
);
228 static void ocfs2_resv_mark_lru(struct ocfs2_reservation_map
*resmap
,
229 struct ocfs2_alloc_reservation
*resv
)
231 assert_spin_locked(&resv_lock
);
233 if (!list_empty(&resv
->r_lru
))
234 list_del_init(&resv
->r_lru
);
236 list_add_tail(&resv
->r_lru
, &resmap
->m_lru
);
239 static void __ocfs2_resv_trunc(struct ocfs2_alloc_reservation
*resv
)
245 static void ocfs2_resv_remove(struct ocfs2_reservation_map
*resmap
,
246 struct ocfs2_alloc_reservation
*resv
)
248 if (resv
->r_flags
& OCFS2_RESV_FLAG_INUSE
) {
249 list_del_init(&resv
->r_lru
);
250 rb_erase(&resv
->r_node
, &resmap
->m_reservations
);
251 resv
->r_flags
&= ~OCFS2_RESV_FLAG_INUSE
;
255 static void __ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
256 struct ocfs2_alloc_reservation
*resv
)
258 assert_spin_locked(&resv_lock
);
260 __ocfs2_resv_trunc(resv
);
262 * last_len and last_start no longer make sense if
263 * we're changing the range of our allocations.
265 resv
->r_last_len
= resv
->r_last_start
= 0;
267 ocfs2_resv_remove(resmap
, resv
);
270 /* does nothing if 'resv' is null */
271 void ocfs2_resv_discard(struct ocfs2_reservation_map
*resmap
,
272 struct ocfs2_alloc_reservation
*resv
)
275 spin_lock(&resv_lock
);
276 __ocfs2_resv_discard(resmap
, resv
);
277 spin_unlock(&resv_lock
);
281 static void ocfs2_resmap_clear_all_resv(struct ocfs2_reservation_map
*resmap
)
283 struct rb_node
*node
;
284 struct ocfs2_alloc_reservation
*resv
;
286 assert_spin_locked(&resv_lock
);
288 while ((node
= rb_last(&resmap
->m_reservations
)) != NULL
) {
289 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
291 __ocfs2_resv_discard(resmap
, resv
);
295 void ocfs2_resmap_restart(struct ocfs2_reservation_map
*resmap
,
296 unsigned int clen
, char *disk_bitmap
)
298 if (ocfs2_resmap_disabled(resmap
))
301 spin_lock(&resv_lock
);
303 ocfs2_resmap_clear_all_resv(resmap
);
304 resmap
->m_bitmap_len
= clen
;
305 resmap
->m_disk_bitmap
= disk_bitmap
;
307 spin_unlock(&resv_lock
);
310 void ocfs2_resmap_uninit(struct ocfs2_reservation_map
*resmap
)
312 /* Does nothing for now. Keep this around for API symmetry */
315 static void ocfs2_resv_insert(struct ocfs2_reservation_map
*resmap
,
316 struct ocfs2_alloc_reservation
*new)
318 struct rb_root
*root
= &resmap
->m_reservations
;
319 struct rb_node
*parent
= NULL
;
320 struct rb_node
**p
= &root
->rb_node
;
321 struct ocfs2_alloc_reservation
*tmp
;
323 assert_spin_locked(&resv_lock
);
325 mlog(0, "Insert reservation start: %u len: %u\n", new->r_start
,
331 tmp
= rb_entry(parent
, struct ocfs2_alloc_reservation
, r_node
);
333 if (new->r_start
< tmp
->r_start
) {
337 * This is a good place to check for
338 * overlapping reservations.
340 BUG_ON(ocfs2_resv_end(new) >= tmp
->r_start
);
341 } else if (new->r_start
> ocfs2_resv_end(tmp
)) {
344 /* This should never happen! */
345 mlog(ML_ERROR
, "Duplicate reservation window!\n");
350 rb_link_node(&new->r_node
, parent
, p
);
351 rb_insert_color(&new->r_node
, root
);
352 new->r_flags
|= OCFS2_RESV_FLAG_INUSE
;
354 ocfs2_resv_mark_lru(resmap
, new);
356 ocfs2_check_resmap(resmap
);
360 * ocfs2_find_resv_lhs() - find the window which contains goal
361 * @resmap: reservation map to search
362 * @goal: which bit to search for
364 * If a window containing that goal is not found, we return the window
365 * which comes before goal. Returns NULL on empty rbtree or no window
368 static struct ocfs2_alloc_reservation
*
369 ocfs2_find_resv_lhs(struct ocfs2_reservation_map
*resmap
, unsigned int goal
)
371 struct ocfs2_alloc_reservation
*resv
= NULL
;
372 struct ocfs2_alloc_reservation
*prev_resv
= NULL
;
373 struct rb_node
*node
= resmap
->m_reservations
.rb_node
;
375 assert_spin_locked(&resv_lock
);
380 node
= rb_first(&resmap
->m_reservations
);
382 resv
= rb_entry(node
, struct ocfs2_alloc_reservation
, r_node
);
384 if (resv
->r_start
<= goal
&& ocfs2_resv_end(resv
) >= goal
)
387 /* Check if we overshot the reservation just before goal? */
388 if (resv
->r_start
> goal
) {
394 node
= rb_next(node
);
401 * We are given a range within the bitmap, which corresponds to a gap
402 * inside the reservations tree (search_start, search_len). The range
403 * can be anything from the whole bitmap, to a gap between
406 * The start value of *rstart is insignificant.
408 * This function searches the bitmap range starting at search_start
409 * with length search_len for a set of contiguous free bits. We try
410 * to find up to 'wanted' bits, but can sometimes return less.
412 * Returns the length of allocation, 0 if no free bits are found.
414 * *cstart and *clen will also be populated with the result.
416 static int ocfs2_resmap_find_free_bits(struct ocfs2_reservation_map
*resmap
,
418 unsigned int search_start
,
419 unsigned int search_len
,
420 unsigned int *rstart
,
423 void *bitmap
= resmap
->m_disk_bitmap
;
424 unsigned int best_start
, best_len
= 0;
425 int offset
, start
, found
;
427 mlog(0, "Find %u bits within range (%u, len %u) resmap len: %u\n",
428 wanted
, search_start
, search_len
, resmap
->m_bitmap_len
);
430 found
= best_start
= best_len
= 0;
432 start
= search_start
;
433 while ((offset
= ocfs2_find_next_zero_bit(bitmap
, resmap
->m_bitmap_len
,
435 /* Search reached end of the region */
436 if (offset
>= (search_start
+ search_len
))
439 if (offset
== start
) {
440 /* we found a zero */
442 /* move start to the next bit to test */
445 /* got a zero after some ones */
449 if (found
> best_len
) {
451 best_start
= start
- found
;
461 if (best_len
>= wanted
)
465 *rstart
= best_start
;
467 mlog(0, "Found start: %u len: %u\n", best_start
, best_len
);
472 static void __ocfs2_resv_find_window(struct ocfs2_reservation_map
*resmap
,
473 struct ocfs2_alloc_reservation
*resv
,
474 unsigned int goal
, unsigned int wanted
)
476 struct rb_root
*root
= &resmap
->m_reservations
;
477 unsigned int gap_start
, gap_end
, gap_len
;
478 struct ocfs2_alloc_reservation
*prev_resv
, *next_resv
;
479 struct rb_node
*prev
, *next
;
480 unsigned int cstart
, clen
;
481 unsigned int best_start
= 0, best_len
= 0;
484 * Nasty cases to consider:
487 * - our window should be first in all reservations
488 * - our window should be last in all reservations
489 * - need to make sure we don't go past end of bitmap
492 mlog(0, "resv start: %u resv end: %u goal: %u wanted: %u\n",
493 resv
->r_start
, ocfs2_resv_end(resv
), goal
, wanted
);
495 assert_spin_locked(&resv_lock
);
497 if (RB_EMPTY_ROOT(root
)) {
499 * Easiest case - empty tree. We can just take
500 * whatever window of free bits we want.
503 mlog(0, "Empty root\n");
505 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
506 resmap
->m_bitmap_len
- goal
,
510 * This should never happen - the local alloc window
511 * will always have free bits when we're called.
513 BUG_ON(goal
== 0 && clen
== 0);
518 resv
->r_start
= cstart
;
521 ocfs2_resv_insert(resmap
, resv
);
525 prev_resv
= ocfs2_find_resv_lhs(resmap
, goal
);
527 if (prev_resv
== NULL
) {
528 mlog(0, "Goal on LHS of leftmost window\n");
531 * A NULL here means that the search code couldn't
532 * find a window that starts before goal.
534 * However, we can take the first window after goal,
535 * which is also by definition, the leftmost window in
536 * the entire tree. If we can find free bits in the
537 * gap between goal and the LHS window, then the
538 * reservation can safely be placed there.
540 * Otherwise we fall back to a linear search, checking
541 * the gaps in between windows for a place to
545 next
= rb_first(root
);
546 next_resv
= rb_entry(next
, struct ocfs2_alloc_reservation
,
550 * The search should never return such a window. (see
553 if (next_resv
->r_start
<= goal
) {
554 mlog(ML_ERROR
, "goal: %u next_resv: start %u len %u\n",
555 goal
, next_resv
->r_start
, next_resv
->r_len
);
556 ocfs2_dump_resv(resmap
);
560 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, goal
,
561 next_resv
->r_start
- goal
,
566 if (best_len
== wanted
)
570 prev_resv
= next_resv
;
574 prev
= &prev_resv
->r_node
;
576 /* Now we do a linear search for a window, starting at 'prev_rsv' */
578 next
= rb_next(prev
);
580 mlog(0, "One more resv found in linear search\n");
581 next_resv
= rb_entry(next
,
582 struct ocfs2_alloc_reservation
,
585 gap_start
= ocfs2_resv_end(prev_resv
) + 1;
586 gap_end
= next_resv
->r_start
- 1;
587 gap_len
= gap_end
- gap_start
+ 1;
589 mlog(0, "No next node\n");
591 * We're at the rightmost edge of the
592 * tree. See if a reservation between this
593 * window and the end of the bitmap will work.
595 gap_start
= ocfs2_resv_end(prev_resv
) + 1;
596 gap_len
= resmap
->m_bitmap_len
- gap_start
;
597 gap_end
= resmap
->m_bitmap_len
- 1;
601 * No need to check this gap if we have already found
602 * a larger region of free bits.
604 if (gap_len
<= best_len
)
607 clen
= ocfs2_resmap_find_free_bits(resmap
, wanted
, gap_start
,
608 gap_len
, &cstart
, &clen
);
609 if (clen
== wanted
) {
613 } else if (clen
> best_len
) {
623 prev_resv
= rb_entry(prev
, struct ocfs2_alloc_reservation
,
629 resv
->r_start
= best_start
;
630 resv
->r_len
= best_len
;
631 ocfs2_resv_insert(resmap
, resv
);
635 static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map
*resmap
,
636 struct ocfs2_alloc_reservation
*resv
,
639 struct ocfs2_alloc_reservation
*lru_resv
;
640 int tmpwindow
= !!(resv
->r_flags
& OCFS2_RESV_FLAG_TMP
);
641 unsigned int min_bits
;
644 min_bits
= ocfs2_resv_window_bits(resmap
, resv
) >> 1;
646 min_bits
= wanted
; /* We at know the temp window will use all
650 * Take the first reservation off the LRU as our 'target'. We
651 * don't try to be smart about it. There might be a case for
652 * searching based on size but I don't have enough data to be
653 * sure. --Mark (3/16/2010)
655 lru_resv
= list_first_entry(&resmap
->m_lru
,
656 struct ocfs2_alloc_reservation
, r_lru
);
658 mlog(0, "lru resv: start: %u len: %u end: %u\n", lru_resv
->r_start
,
659 lru_resv
->r_len
, ocfs2_resv_end(lru_resv
));
662 * Cannibalize (some or all) of the target reservation and
663 * feed it to the current window.
665 if (lru_resv
->r_len
<= min_bits
) {
667 * Discard completely if size is less than or equal to a
668 * reasonable threshold - 50% of window bits for non temporary
671 resv
->r_start
= lru_resv
->r_start
;
672 resv
->r_len
= lru_resv
->r_len
;
674 __ocfs2_resv_discard(resmap
, lru_resv
);
680 shrink
= lru_resv
->r_len
/ 2;
682 lru_resv
->r_len
-= shrink
;
684 resv
->r_start
= ocfs2_resv_end(lru_resv
) + 1;
685 resv
->r_len
= shrink
;
688 mlog(0, "Reservation now looks like: r_start: %u r_end: %u "
689 "r_len: %u r_last_start: %u r_last_len: %u\n",
690 resv
->r_start
, ocfs2_resv_end(resv
), resv
->r_len
,
691 resv
->r_last_start
, resv
->r_last_len
);
693 ocfs2_resv_insert(resmap
, resv
);
696 static void ocfs2_resv_find_window(struct ocfs2_reservation_map
*resmap
,
697 struct ocfs2_alloc_reservation
*resv
,
700 unsigned int goal
= 0;
702 BUG_ON(!ocfs2_resv_empty(resv
));
705 * Begin by trying to get a window as close to the previous
706 * one as possible. Using the most recent allocation as a
707 * start goal makes sense.
709 if (resv
->r_last_len
) {
710 goal
= resv
->r_last_start
+ resv
->r_last_len
;
711 if (goal
>= resmap
->m_bitmap_len
)
715 __ocfs2_resv_find_window(resmap
, resv
, goal
, wanted
);
717 /* Search from last alloc didn't work, try once more from beginning. */
718 if (ocfs2_resv_empty(resv
) && goal
!= 0)
719 __ocfs2_resv_find_window(resmap
, resv
, 0, wanted
);
721 if (ocfs2_resv_empty(resv
)) {
723 * Still empty? Pull oldest one off the LRU, remove it from
724 * tree, put this one in it's place.
726 ocfs2_cannibalize_resv(resmap
, resv
, wanted
);
729 BUG_ON(ocfs2_resv_empty(resv
));
732 int ocfs2_resmap_resv_bits(struct ocfs2_reservation_map
*resmap
,
733 struct ocfs2_alloc_reservation
*resv
,
734 int *cstart
, int *clen
)
736 unsigned int wanted
= *clen
;
738 if (resv
== NULL
|| ocfs2_resmap_disabled(resmap
))
741 spin_lock(&resv_lock
);
744 * We don't want to over-allocate for temporary
745 * windows. Otherwise, we run the risk of fragmenting the
748 wanted
= ocfs2_resv_window_bits(resmap
, resv
);
749 if ((resv
->r_flags
& OCFS2_RESV_FLAG_TMP
) || wanted
< *clen
)
752 if (ocfs2_resv_empty(resv
)) {
753 mlog(0, "empty reservation, find new window\n");
756 * Try to get a window here. If it works, we must fall
757 * through and test the bitmap . This avoids some
758 * ping-ponging of windows due to non-reserved space
759 * being allocation before we initialize a window for
762 ocfs2_resv_find_window(resmap
, resv
, wanted
);
765 BUG_ON(ocfs2_resv_empty(resv
));
767 *cstart
= resv
->r_start
;
770 spin_unlock(&resv_lock
);
775 ocfs2_adjust_resv_from_alloc(struct ocfs2_reservation_map
*resmap
,
776 struct ocfs2_alloc_reservation
*resv
,
777 unsigned int start
, unsigned int end
)
779 unsigned int rhs
= 0;
780 unsigned int old_end
= ocfs2_resv_end(resv
);
782 BUG_ON(start
!= resv
->r_start
|| old_end
< end
);
785 * Completely used? We can remove it then.
787 if (old_end
== end
) {
788 __ocfs2_resv_discard(resmap
, resv
);
795 * This should have been trapped above.
799 resv
->r_start
= end
+ 1;
800 resv
->r_len
= old_end
- resv
->r_start
+ 1;
803 void ocfs2_resmap_claimed_bits(struct ocfs2_reservation_map
*resmap
,
804 struct ocfs2_alloc_reservation
*resv
,
805 u32 cstart
, u32 clen
)
807 unsigned int cend
= cstart
+ clen
- 1;
809 if (resmap
== NULL
|| ocfs2_resmap_disabled(resmap
))
815 BUG_ON(cstart
!= resv
->r_start
);
817 spin_lock(&resv_lock
);
819 mlog(0, "claim bits: cstart: %u cend: %u clen: %u r_start: %u "
820 "r_end: %u r_len: %u, r_last_start: %u r_last_len: %u\n",
821 cstart
, cend
, clen
, resv
->r_start
, ocfs2_resv_end(resv
),
822 resv
->r_len
, resv
->r_last_start
, resv
->r_last_len
);
824 BUG_ON(cstart
< resv
->r_start
);
825 BUG_ON(cstart
> ocfs2_resv_end(resv
));
826 BUG_ON(cend
> ocfs2_resv_end(resv
));
828 ocfs2_adjust_resv_from_alloc(resmap
, resv
, cstart
, cend
);
829 resv
->r_last_start
= cstart
;
830 resv
->r_last_len
= clen
;
833 * May have been discarded above from
834 * ocfs2_adjust_resv_from_alloc().
836 if (!ocfs2_resv_empty(resv
))
837 ocfs2_resv_mark_lru(resmap
, resv
);
839 mlog(0, "Reservation now looks like: r_start: %u r_end: %u "
840 "r_len: %u r_last_start: %u r_last_len: %u\n",
841 resv
->r_start
, ocfs2_resv_end(resv
), resv
->r_len
,
842 resv
->r_last_start
, resv
->r_last_len
);
844 ocfs2_check_resmap(resmap
);
846 spin_unlock(&resv_lock
);