1
2
3
4
5
6
7
8
9
10
11
12
13
14#include <linux/quotaops.h>
15#include <linux/blkdev.h>
16#include "ext3.h"
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
35
36
37
38
39static void ext3_get_group_no_and_offset(struct super_block *sb,
40 ext3_fsblk_t blocknr, unsigned long *blockgrpp, ext3_grpblk_t *offsetp)
41{
42 struct ext3_super_block *es = EXT3_SB(sb)->s_es;
43
44 blocknr = blocknr - le32_to_cpu(es->s_first_data_block);
45 if (offsetp)
46 *offsetp = blocknr % EXT3_BLOCKS_PER_GROUP(sb);
47 if (blockgrpp)
48 *blockgrpp = blocknr / EXT3_BLOCKS_PER_GROUP(sb);
49}
50
51
52
53
54
55
56
57
58struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
59 unsigned int block_group,
60 struct buffer_head ** bh)
61{
62 unsigned long group_desc;
63 unsigned long offset;
64 struct ext3_group_desc * desc;
65 struct ext3_sb_info *sbi = EXT3_SB(sb);
66
67 if (block_group >= sbi->s_groups_count) {
68 ext3_error (sb, "ext3_get_group_desc",
69 "block_group >= groups_count - "
70 "block_group = %d, groups_count = %lu",
71 block_group, sbi->s_groups_count);
72
73 return NULL;
74 }
75 smp_rmb();
76
77 group_desc = block_group >> EXT3_DESC_PER_BLOCK_BITS(sb);
78 offset = block_group & (EXT3_DESC_PER_BLOCK(sb) - 1);
79 if (!sbi->s_group_desc[group_desc]) {
80 ext3_error (sb, "ext3_get_group_desc",
81 "Group descriptor not loaded - "
82 "block_group = %d, group_desc = %lu, desc = %lu",
83 block_group, group_desc, offset);
84 return NULL;
85 }
86
87 desc = (struct ext3_group_desc *) sbi->s_group_desc[group_desc]->b_data;
88 if (bh)
89 *bh = sbi->s_group_desc[group_desc];
90 return desc + offset;
91}
92
93static int ext3_valid_block_bitmap(struct super_block *sb,
94 struct ext3_group_desc *desc,
95 unsigned int block_group,
96 struct buffer_head *bh)
97{
98 ext3_grpblk_t offset;
99 ext3_grpblk_t next_zero_bit;
100 ext3_fsblk_t bitmap_blk;
101 ext3_fsblk_t group_first_block;
102
103 group_first_block = ext3_group_first_block_no(sb, block_group);
104
105
106 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
107 offset = bitmap_blk - group_first_block;
108 if (!ext3_test_bit(offset, bh->b_data))
109
110 goto err_out;
111
112
113 bitmap_blk = le32_to_cpu(desc->bg_inode_bitmap);
114 offset = bitmap_blk - group_first_block;
115 if (!ext3_test_bit(offset, bh->b_data))
116
117 goto err_out;
118
119
120 bitmap_blk = le32_to_cpu(desc->bg_inode_table);
121 offset = bitmap_blk - group_first_block;
122 next_zero_bit = ext3_find_next_zero_bit(bh->b_data,
123 offset + EXT3_SB(sb)->s_itb_per_group,
124 offset);
125 if (next_zero_bit >= offset + EXT3_SB(sb)->s_itb_per_group)
126
127 return 1;
128
129err_out:
130 ext3_error(sb, __func__,
131 "Invalid block bitmap - "
132 "block_group = %d, block = %lu",
133 block_group, bitmap_blk);
134 return 0;
135}
136
137
138
139
140
141
142
143
144
145
146
147static struct buffer_head *
148read_block_bitmap(struct super_block *sb, unsigned int block_group)
149{
150 struct ext3_group_desc * desc;
151 struct buffer_head * bh = NULL;
152 ext3_fsblk_t bitmap_blk;
153
154 desc = ext3_get_group_desc(sb, block_group, NULL);
155 if (!desc)
156 return NULL;
157 trace_ext3_read_block_bitmap(sb, block_group);
158 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
159 bh = sb_getblk(sb, bitmap_blk);
160 if (unlikely(!bh)) {
161 ext3_error(sb, __func__,
162 "Cannot read block bitmap - "
163 "block_group = %d, block_bitmap = %u",
164 block_group, le32_to_cpu(desc->bg_block_bitmap));
165 return NULL;
166 }
167 if (likely(bh_uptodate_or_lock(bh)))
168 return bh;
169
170 if (bh_submit_read(bh) < 0) {
171 brelse(bh);
172 ext3_error(sb, __func__,
173 "Cannot read block bitmap - "
174 "block_group = %d, block_bitmap = %u",
175 block_group, le32_to_cpu(desc->bg_block_bitmap));
176 return NULL;
177 }
178 ext3_valid_block_bitmap(sb, desc, block_group, bh);
179
180
181
182
183 return bh;
184}
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206#if 1
207static void __rsv_window_dump(struct rb_root *root, int verbose,
208 const char *fn)
209{
210 struct rb_node *n;
211 struct ext3_reserve_window_node *rsv, *prev;
212 int bad;
213
214restart:
215 n = rb_first(root);
216 bad = 0;
217 prev = NULL;
218
219 printk("Block Allocation Reservation Windows Map (%s):\n", fn);
220 while (n) {
221 rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
222 if (verbose)
223 printk("reservation window 0x%p "
224 "start: %lu, end: %lu\n",
225 rsv, rsv->rsv_start, rsv->rsv_end);
226 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
227 printk("Bad reservation %p (start >= end)\n",
228 rsv);
229 bad = 1;
230 }
231 if (prev && prev->rsv_end >= rsv->rsv_start) {
232 printk("Bad reservation %p (prev->end >= start)\n",
233 rsv);
234 bad = 1;
235 }
236 if (bad) {
237 if (!verbose) {
238 printk("Restarting reservation walk in verbose mode\n");
239 verbose = 1;
240 goto restart;
241 }
242 }
243 n = rb_next(n);
244 prev = rsv;
245 }
246 printk("Window map complete.\n");
247 BUG_ON(bad);
248}
249#define rsv_window_dump(root, verbose) \
250 __rsv_window_dump((root), (verbose), __func__)
251#else
252#define rsv_window_dump(root, verbose) do {} while (0)
253#endif
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271static int
272goal_in_my_reservation(struct ext3_reserve_window *rsv, ext3_grpblk_t grp_goal,
273 unsigned int group, struct super_block * sb)
274{
275 ext3_fsblk_t group_first_block, group_last_block;
276
277 group_first_block = ext3_group_first_block_no(sb, group);
278 group_last_block = group_first_block + (EXT3_BLOCKS_PER_GROUP(sb) - 1);
279
280 if ((rsv->_rsv_start > group_last_block) ||
281 (rsv->_rsv_end < group_first_block))
282 return 0;
283 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
284 || (grp_goal + group_first_block > rsv->_rsv_end)))
285 return 0;
286 return 1;
287}
288
289
290
291
292
293
294
295
296
297
298static struct ext3_reserve_window_node *
299search_reserve_window(struct rb_root *root, ext3_fsblk_t goal)
300{
301 struct rb_node *n = root->rb_node;
302 struct ext3_reserve_window_node *rsv;
303
304 if (!n)
305 return NULL;
306
307 do {
308 rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
309
310 if (goal < rsv->rsv_start)
311 n = n->rb_left;
312 else if (goal > rsv->rsv_end)
313 n = n->rb_right;
314 else
315 return rsv;
316 } while (n);
317
318
319
320
321
322
323 if (rsv->rsv_start > goal) {
324 n = rb_prev(&rsv->rsv_node);
325 rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
326 }
327 return rsv;
328}
329
330
331
332
333
334
335
336
337void ext3_rsv_window_add(struct super_block *sb,
338 struct ext3_reserve_window_node *rsv)
339{
340 struct rb_root *root = &EXT3_SB(sb)->s_rsv_window_root;
341 struct rb_node *node = &rsv->rsv_node;
342 ext3_fsblk_t start = rsv->rsv_start;
343
344 struct rb_node ** p = &root->rb_node;
345 struct rb_node * parent = NULL;
346 struct ext3_reserve_window_node *this;
347
348 trace_ext3_rsv_window_add(sb, rsv);
349 while (*p)
350 {
351 parent = *p;
352 this = rb_entry(parent, struct ext3_reserve_window_node, rsv_node);
353
354 if (start < this->rsv_start)
355 p = &(*p)->rb_left;
356 else if (start > this->rsv_end)
357 p = &(*p)->rb_right;
358 else {
359 rsv_window_dump(root, 1);
360 BUG();
361 }
362 }
363
364 rb_link_node(node, parent, p);
365 rb_insert_color(node, root);
366}
367
368
369
370
371
372
373
374
375
376
377static void rsv_window_remove(struct super_block *sb,
378 struct ext3_reserve_window_node *rsv)
379{
380 rsv->rsv_start = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
381 rsv->rsv_end = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
382 rsv->rsv_alloc_hit = 0;
383 rb_erase(&rsv->rsv_node, &EXT3_SB(sb)->s_rsv_window_root);
384}
385
386
387
388
389
390
391
392static inline int rsv_is_empty(struct ext3_reserve_window *rsv)
393{
394
395 return rsv->_rsv_end == EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
396}
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419void ext3_init_block_alloc_info(struct inode *inode)
420{
421 struct ext3_inode_info *ei = EXT3_I(inode);
422 struct ext3_block_alloc_info *block_i;
423 struct super_block *sb = inode->i_sb;
424
425 block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
426 if (block_i) {
427 struct ext3_reserve_window_node *rsv = &block_i->rsv_window_node;
428
429 rsv->rsv_start = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
430 rsv->rsv_end = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
431
432
433
434
435
436
437 if (!test_opt(sb, RESERVATION))
438 rsv->rsv_goal_size = 0;
439 else
440 rsv->rsv_goal_size = EXT3_DEFAULT_RESERVE_BLOCKS;
441 rsv->rsv_alloc_hit = 0;
442 block_i->last_alloc_logical_block = 0;
443 block_i->last_alloc_physical_block = 0;
444 }
445 ei->i_block_alloc_info = block_i;
446}
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461void ext3_discard_reservation(struct inode *inode)
462{
463 struct ext3_inode_info *ei = EXT3_I(inode);
464 struct ext3_block_alloc_info *block_i = ei->i_block_alloc_info;
465 struct ext3_reserve_window_node *rsv;
466 spinlock_t *rsv_lock = &EXT3_SB(inode->i_sb)->s_rsv_window_lock;
467
468 if (!block_i)
469 return;
470
471 rsv = &block_i->rsv_window_node;
472 if (!rsv_is_empty(&rsv->rsv_window)) {
473 spin_lock(rsv_lock);
474 if (!rsv_is_empty(&rsv->rsv_window)) {
475 trace_ext3_discard_reservation(inode, rsv);
476 rsv_window_remove(inode->i_sb, rsv);
477 }
478 spin_unlock(rsv_lock);
479 }
480}
481
482
483
484
485
486
487
488
489
490void ext3_free_blocks_sb(handle_t *handle, struct super_block *sb,
491 ext3_fsblk_t block, unsigned long count,
492 unsigned long *pdquot_freed_blocks)
493{
494 struct buffer_head *bitmap_bh = NULL;
495 struct buffer_head *gd_bh;
496 unsigned long block_group;
497 ext3_grpblk_t bit;
498 unsigned long i;
499 unsigned long overflow;
500 struct ext3_group_desc * desc;
501 struct ext3_super_block * es;
502 struct ext3_sb_info *sbi;
503 int err = 0, ret;
504 ext3_grpblk_t group_freed;
505
506 *pdquot_freed_blocks = 0;
507 sbi = EXT3_SB(sb);
508 es = sbi->s_es;
509 if (block < le32_to_cpu(es->s_first_data_block) ||
510 block + count < block ||
511 block + count > le32_to_cpu(es->s_blocks_count)) {
512 ext3_error (sb, "ext3_free_blocks",
513 "Freeing blocks not in datazone - "
514 "block = "E3FSBLK", count = %lu", block, count);
515 goto error_return;
516 }
517
518 ext3_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
519
520do_more:
521 overflow = 0;
522 block_group = (block - le32_to_cpu(es->s_first_data_block)) /
523 EXT3_BLOCKS_PER_GROUP(sb);
524 bit = (block - le32_to_cpu(es->s_first_data_block)) %
525 EXT3_BLOCKS_PER_GROUP(sb);
526
527
528
529
530 if (bit + count > EXT3_BLOCKS_PER_GROUP(sb)) {
531 overflow = bit + count - EXT3_BLOCKS_PER_GROUP(sb);
532 count -= overflow;
533 }
534 brelse(bitmap_bh);
535 bitmap_bh = read_block_bitmap(sb, block_group);
536 if (!bitmap_bh)
537 goto error_return;
538 desc = ext3_get_group_desc (sb, block_group, &gd_bh);
539 if (!desc)
540 goto error_return;
541
542 if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
543 in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
544 in_range (block, le32_to_cpu(desc->bg_inode_table),
545 sbi->s_itb_per_group) ||
546 in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
547 sbi->s_itb_per_group)) {
548 ext3_error (sb, "ext3_free_blocks",
549 "Freeing blocks in system zones - "
550 "Block = "E3FSBLK", count = %lu",
551 block, count);
552 goto error_return;
553 }
554
555
556
557
558
559
560 BUFFER_TRACE(bitmap_bh, "getting undo access");
561 err = ext3_journal_get_undo_access(handle, bitmap_bh);
562 if (err)
563 goto error_return;
564
565
566
567
568
569
570 BUFFER_TRACE(gd_bh, "get_write_access");
571 err = ext3_journal_get_write_access(handle, gd_bh);
572 if (err)
573 goto error_return;
574
575 jbd_lock_bh_state(bitmap_bh);
576
577 for (i = 0, group_freed = 0; i < count; i++) {
578
579
580
581#ifdef CONFIG_JBD_DEBUG
582 jbd_unlock_bh_state(bitmap_bh);
583 {
584 struct buffer_head *debug_bh;
585 debug_bh = sb_find_get_block(sb, block + i);
586 if (debug_bh) {
587 BUFFER_TRACE(debug_bh, "Deleted!");
588 if (!bh2jh(bitmap_bh)->b_committed_data)
589 BUFFER_TRACE(debug_bh,
590 "No committed data in bitmap");
591 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
592 __brelse(debug_bh);
593 }
594 }
595 jbd_lock_bh_state(bitmap_bh);
596#endif
597 if (need_resched()) {
598 jbd_unlock_bh_state(bitmap_bh);
599 cond_resched();
600 jbd_lock_bh_state(bitmap_bh);
601 }
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620 BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
621 J_ASSERT_BH(bitmap_bh,
622 bh2jh(bitmap_bh)->b_committed_data != NULL);
623 ext3_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
624 bh2jh(bitmap_bh)->b_committed_data);
625
626
627
628
629
630
631 BUFFER_TRACE(bitmap_bh, "clear bit");
632 if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
633 bit + i, bitmap_bh->b_data)) {
634 jbd_unlock_bh_state(bitmap_bh);
635 ext3_error(sb, __func__,
636 "bit already cleared for block "E3FSBLK,
637 block + i);
638 jbd_lock_bh_state(bitmap_bh);
639 BUFFER_TRACE(bitmap_bh, "bit already cleared");
640 } else {
641 group_freed++;
642 }
643 }
644 jbd_unlock_bh_state(bitmap_bh);
645
646 spin_lock(sb_bgl_lock(sbi, block_group));
647 le16_add_cpu(&desc->bg_free_blocks_count, group_freed);
648 spin_unlock(sb_bgl_lock(sbi, block_group));
649 percpu_counter_add(&sbi->s_freeblocks_counter, count);
650
651
652 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
653 err = ext3_journal_dirty_metadata(handle, bitmap_bh);
654
655
656 BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
657 ret = ext3_journal_dirty_metadata(handle, gd_bh);
658 if (!err) err = ret;
659 *pdquot_freed_blocks += group_freed;
660
661 if (overflow && !err) {
662 block += count;
663 count = overflow;
664 goto do_more;
665 }
666
667error_return:
668 brelse(bitmap_bh);
669 ext3_std_error(sb, err);
670 return;
671}
672
673
674
675
676
677
678
679
680void ext3_free_blocks(handle_t *handle, struct inode *inode,
681 ext3_fsblk_t block, unsigned long count)
682{
683 struct super_block *sb = inode->i_sb;
684 unsigned long dquot_freed_blocks;
685
686 trace_ext3_free_blocks(inode, block, count);
687 ext3_free_blocks_sb(handle, sb, block, count, &dquot_freed_blocks);
688 if (dquot_freed_blocks)
689 dquot_free_block(inode, dquot_freed_blocks);
690 return;
691}
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713static int ext3_test_allocatable(ext3_grpblk_t nr, struct buffer_head *bh)
714{
715 int ret;
716 struct journal_head *jh = bh2jh(bh);
717
718 if (ext3_test_bit(nr, bh->b_data))
719 return 0;
720
721 jbd_lock_bh_state(bh);
722 if (!jh->b_committed_data)
723 ret = 1;
724 else
725 ret = !ext3_test_bit(nr, jh->b_committed_data);
726 jbd_unlock_bh_state(bh);
727 return ret;
728}
729
730
731
732
733
734
735
736
737
738
739
740static ext3_grpblk_t
741bitmap_search_next_usable_block(ext3_grpblk_t start, struct buffer_head *bh,
742 ext3_grpblk_t maxblocks)
743{
744 ext3_grpblk_t next;
745 struct journal_head *jh = bh2jh(bh);
746
747 while (start < maxblocks) {
748 next = ext3_find_next_zero_bit(bh->b_data, maxblocks, start);
749 if (next >= maxblocks)
750 return -1;
751 if (ext3_test_allocatable(next, bh))
752 return next;
753 jbd_lock_bh_state(bh);
754 if (jh->b_committed_data)
755 start = ext3_find_next_zero_bit(jh->b_committed_data,
756 maxblocks, next);
757 jbd_unlock_bh_state(bh);
758 }
759 return -1;
760}
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775static ext3_grpblk_t
776find_next_usable_block(ext3_grpblk_t start, struct buffer_head *bh,
777 ext3_grpblk_t maxblocks)
778{
779 ext3_grpblk_t here, next;
780 char *p, *r;
781
782 if (start > 0) {
783
784
785
786
787
788
789
790
791 ext3_grpblk_t end_goal = (start + 63) & ~63;
792 if (end_goal > maxblocks)
793 end_goal = maxblocks;
794 here = ext3_find_next_zero_bit(bh->b_data, end_goal, start);
795 if (here < end_goal && ext3_test_allocatable(here, bh))
796 return here;
797 ext3_debug("Bit not found near goal\n");
798 }
799
800 here = start;
801 if (here < 0)
802 here = 0;
803
804 p = bh->b_data + (here >> 3);
805 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
806 next = (r - bh->b_data) << 3;
807
808 if (next < maxblocks && next >= start && ext3_test_allocatable(next, bh))
809 return next;
810
811
812
813
814
815
816 here = bitmap_search_next_usable_block(here, bh, maxblocks);
817 return here;
818}
819
820
821
822
823
824
825
826
827
828
829
830
831
832static inline int
833claim_block(spinlock_t *lock, ext3_grpblk_t block, struct buffer_head *bh)
834{
835 struct journal_head *jh = bh2jh(bh);
836 int ret;
837
838 if (ext3_set_bit_atomic(lock, block, bh->b_data))
839 return 0;
840 jbd_lock_bh_state(bh);
841 if (jh->b_committed_data && ext3_test_bit(block,jh->b_committed_data)) {
842 ext3_clear_bit_atomic(lock, block, bh->b_data);
843 ret = 0;
844 } else {
845 ret = 1;
846 }
847 jbd_unlock_bh_state(bh);
848 return ret;
849}
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875static ext3_grpblk_t
876ext3_try_to_allocate(struct super_block *sb, handle_t *handle, int group,
877 struct buffer_head *bitmap_bh, ext3_grpblk_t grp_goal,
878 unsigned long *count, struct ext3_reserve_window *my_rsv)
879{
880 ext3_fsblk_t group_first_block;
881 ext3_grpblk_t start, end;
882 unsigned long num = 0;
883
884
885 if (my_rsv) {
886 group_first_block = ext3_group_first_block_no(sb, group);
887 if (my_rsv->_rsv_start >= group_first_block)
888 start = my_rsv->_rsv_start - group_first_block;
889 else
890
891 start = 0;
892 end = my_rsv->_rsv_end - group_first_block + 1;
893 if (end > EXT3_BLOCKS_PER_GROUP(sb))
894
895 end = EXT3_BLOCKS_PER_GROUP(sb);
896 if ((start <= grp_goal) && (grp_goal < end))
897 start = grp_goal;
898 else
899 grp_goal = -1;
900 } else {
901 if (grp_goal > 0)
902 start = grp_goal;
903 else
904 start = 0;
905 end = EXT3_BLOCKS_PER_GROUP(sb);
906 }
907
908 BUG_ON(start > EXT3_BLOCKS_PER_GROUP(sb));
909
910repeat:
911 if (grp_goal < 0 || !ext3_test_allocatable(grp_goal, bitmap_bh)) {
912 grp_goal = find_next_usable_block(start, bitmap_bh, end);
913 if (grp_goal < 0)
914 goto fail_access;
915 if (!my_rsv) {
916 int i;
917
918 for (i = 0; i < 7 && grp_goal > start &&
919 ext3_test_allocatable(grp_goal - 1,
920 bitmap_bh);
921 i++, grp_goal--)
922 ;
923 }
924 }
925 start = grp_goal;
926
927 if (!claim_block(sb_bgl_lock(EXT3_SB(sb), group),
928 grp_goal, bitmap_bh)) {
929
930
931
932
933 start++;
934 grp_goal++;
935 if (start >= end)
936 goto fail_access;
937 goto repeat;
938 }
939 num++;
940 grp_goal++;
941 while (num < *count && grp_goal < end
942 && ext3_test_allocatable(grp_goal, bitmap_bh)
943 && claim_block(sb_bgl_lock(EXT3_SB(sb), group),
944 grp_goal, bitmap_bh)) {
945 num++;
946 grp_goal++;
947 }
948 *count = num;
949 return grp_goal - num;
950fail_access:
951 *count = num;
952 return -1;
953}
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990static int find_next_reservable_window(
991 struct ext3_reserve_window_node *search_head,
992 struct ext3_reserve_window_node *my_rsv,
993 struct super_block * sb,
994 ext3_fsblk_t start_block,
995 ext3_fsblk_t last_block)
996{
997 struct rb_node *next;
998 struct ext3_reserve_window_node *rsv, *prev;
999 ext3_fsblk_t cur;
1000 int size = my_rsv->rsv_goal_size;
1001
1002
1003
1004 cur = start_block;
1005 rsv = search_head;
1006 if (!rsv)
1007 return -1;
1008
1009 while (1) {
1010 if (cur <= rsv->rsv_end)
1011 cur = rsv->rsv_end + 1;
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022 if (cur > last_block)
1023 return -1;
1024
1025 prev = rsv;
1026 next = rb_next(&rsv->rsv_node);
1027 rsv = rb_entry(next,struct ext3_reserve_window_node,rsv_node);
1028
1029
1030
1031
1032
1033 if (!next)
1034 break;
1035
1036 if (cur + size <= rsv->rsv_start) {
1037
1038
1039
1040
1041 break;
1042 }
1043 }
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055 if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
1056 rsv_window_remove(sb, my_rsv);
1057
1058
1059
1060
1061
1062
1063
1064
1065 my_rsv->rsv_start = cur;
1066 my_rsv->rsv_end = cur + size - 1;
1067 my_rsv->rsv_alloc_hit = 0;
1068
1069 if (prev != my_rsv)
1070 ext3_rsv_window_add(sb, my_rsv);
1071
1072 return 0;
1073}
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112static int alloc_new_reservation(struct ext3_reserve_window_node *my_rsv,
1113 ext3_grpblk_t grp_goal, struct super_block *sb,
1114 unsigned int group, struct buffer_head *bitmap_bh)
1115{
1116 struct ext3_reserve_window_node *search_head;
1117 ext3_fsblk_t group_first_block, group_end_block, start_block;
1118 ext3_grpblk_t first_free_block;
1119 struct rb_root *fs_rsv_root = &EXT3_SB(sb)->s_rsv_window_root;
1120 unsigned long size;
1121 int ret;
1122 spinlock_t *rsv_lock = &EXT3_SB(sb)->s_rsv_window_lock;
1123
1124 group_first_block = ext3_group_first_block_no(sb, group);
1125 group_end_block = group_first_block + (EXT3_BLOCKS_PER_GROUP(sb) - 1);
1126
1127 if (grp_goal < 0)
1128 start_block = group_first_block;
1129 else
1130 start_block = grp_goal + group_first_block;
1131
1132 trace_ext3_alloc_new_reservation(sb, start_block);
1133 size = my_rsv->rsv_goal_size;
1134
1135 if (!rsv_is_empty(&my_rsv->rsv_window)) {
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150 if ((my_rsv->rsv_start <= group_end_block) &&
1151 (my_rsv->rsv_end > group_end_block) &&
1152 (start_block >= my_rsv->rsv_start))
1153 return -1;
1154
1155 if ((my_rsv->rsv_alloc_hit >
1156 (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
1157
1158
1159
1160
1161
1162
1163 size = size * 2;
1164 if (size > EXT3_MAX_RESERVE_BLOCKS)
1165 size = EXT3_MAX_RESERVE_BLOCKS;
1166 my_rsv->rsv_goal_size= size;
1167 }
1168 }
1169
1170 spin_lock(rsv_lock);
1171
1172
1173
1174 search_head = search_reserve_window(fs_rsv_root, start_block);
1175
1176
1177
1178
1179
1180
1181
1182
1183retry:
1184 ret = find_next_reservable_window(search_head, my_rsv, sb,
1185 start_block, group_end_block);
1186
1187 if (ret == -1) {
1188 if (!rsv_is_empty(&my_rsv->rsv_window))
1189 rsv_window_remove(sb, my_rsv);
1190 spin_unlock(rsv_lock);
1191 return -1;
1192 }
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205 spin_unlock(rsv_lock);
1206 first_free_block = bitmap_search_next_usable_block(
1207 my_rsv->rsv_start - group_first_block,
1208 bitmap_bh, group_end_block - group_first_block + 1);
1209
1210 if (first_free_block < 0) {
1211
1212
1213
1214
1215 spin_lock(rsv_lock);
1216 if (!rsv_is_empty(&my_rsv->rsv_window))
1217 rsv_window_remove(sb, my_rsv);
1218 spin_unlock(rsv_lock);
1219 return -1;
1220 }
1221
1222 start_block = first_free_block + group_first_block;
1223
1224
1225
1226
1227 if (start_block >= my_rsv->rsv_start &&
1228 start_block <= my_rsv->rsv_end) {
1229 trace_ext3_reserved(sb, start_block, my_rsv);
1230 return 0;
1231 }
1232
1233
1234
1235
1236
1237
1238 search_head = my_rsv;
1239 spin_lock(rsv_lock);
1240 goto retry;
1241}
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260static void try_to_extend_reservation(struct ext3_reserve_window_node *my_rsv,
1261 struct super_block *sb, int size)
1262{
1263 struct ext3_reserve_window_node *next_rsv;
1264 struct rb_node *next;
1265 spinlock_t *rsv_lock = &EXT3_SB(sb)->s_rsv_window_lock;
1266
1267 if (!spin_trylock(rsv_lock))
1268 return;
1269
1270 next = rb_next(&my_rsv->rsv_node);
1271
1272 if (!next)
1273 my_rsv->rsv_end += size;
1274 else {
1275 next_rsv = rb_entry(next, struct ext3_reserve_window_node, rsv_node);
1276
1277 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
1278 my_rsv->rsv_end += size;
1279 else
1280 my_rsv->rsv_end = next_rsv->rsv_start - 1;
1281 }
1282 spin_unlock(rsv_lock);
1283}
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314static ext3_grpblk_t
1315ext3_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
1316 unsigned int group, struct buffer_head *bitmap_bh,
1317 ext3_grpblk_t grp_goal,
1318 struct ext3_reserve_window_node * my_rsv,
1319 unsigned long *count, int *errp)
1320{
1321 ext3_fsblk_t group_first_block, group_last_block;
1322 ext3_grpblk_t ret = 0;
1323 int fatal;
1324 unsigned long num = *count;
1325
1326 *errp = 0;
1327
1328
1329
1330
1331
1332
1333 BUFFER_TRACE(bitmap_bh, "get undo access for new block");
1334 fatal = ext3_journal_get_undo_access(handle, bitmap_bh);
1335 if (fatal) {
1336 *errp = fatal;
1337 return -1;
1338 }
1339
1340
1341
1342
1343
1344
1345
1346 if (my_rsv == NULL ) {
1347 ret = ext3_try_to_allocate(sb, handle, group, bitmap_bh,
1348 grp_goal, count, NULL);
1349 goto out;
1350 }
1351
1352
1353
1354
1355
1356
1357 group_first_block = ext3_group_first_block_no(sb, group);
1358 group_last_block = group_first_block + (EXT3_BLOCKS_PER_GROUP(sb) - 1);
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375 while (1) {
1376 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
1377 !goal_in_my_reservation(&my_rsv->rsv_window,
1378 grp_goal, group, sb)) {
1379 if (my_rsv->rsv_goal_size < *count)
1380 my_rsv->rsv_goal_size = *count;
1381 ret = alloc_new_reservation(my_rsv, grp_goal, sb,
1382 group, bitmap_bh);
1383 if (ret < 0)
1384 break;
1385
1386 if (!goal_in_my_reservation(&my_rsv->rsv_window,
1387 grp_goal, group, sb))
1388 grp_goal = -1;
1389 } else if (grp_goal >= 0) {
1390 int curr = my_rsv->rsv_end -
1391 (grp_goal + group_first_block) + 1;
1392
1393 if (curr < *count)
1394 try_to_extend_reservation(my_rsv, sb,
1395 *count - curr);
1396 }
1397
1398 if ((my_rsv->rsv_start > group_last_block) ||
1399 (my_rsv->rsv_end < group_first_block)) {
1400 rsv_window_dump(&EXT3_SB(sb)->s_rsv_window_root, 1);
1401 BUG();
1402 }
1403 ret = ext3_try_to_allocate(sb, handle, group, bitmap_bh,
1404 grp_goal, &num, &my_rsv->rsv_window);
1405 if (ret >= 0) {
1406 my_rsv->rsv_alloc_hit += num;
1407 *count = num;
1408 break;
1409 }
1410 num = *count;
1411 }
1412out:
1413 if (ret >= 0) {
1414 BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for "
1415 "bitmap block");
1416 fatal = ext3_journal_dirty_metadata(handle, bitmap_bh);
1417 if (fatal) {
1418 *errp = fatal;
1419 return -1;
1420 }
1421 return ret;
1422 }
1423
1424 BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
1425 ext3_journal_release_buffer(handle, bitmap_bh);
1426 return ret;
1427}
1428
1429
1430
1431
1432
1433
1434
1435static int ext3_has_free_blocks(struct ext3_sb_info *sbi, int use_reservation)
1436{
1437 ext3_fsblk_t free_blocks, root_blocks;
1438
1439 free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
1440 root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count);
1441 if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
1442 !use_reservation && !uid_eq(sbi->s_resuid, current_fsuid()) &&
1443 (gid_eq(sbi->s_resgid, GLOBAL_ROOT_GID) ||
1444 !in_group_p (sbi->s_resgid))) {
1445 return 0;
1446 }
1447 return 1;
1448}
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462int ext3_should_retry_alloc(struct super_block *sb, int *retries)
1463{
1464 if (!ext3_has_free_blocks(EXT3_SB(sb), 0) || (*retries)++ > 3)
1465 return 0;
1466
1467 jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
1468
1469 return journal_force_commit_nested(EXT3_SB(sb)->s_journal);
1470}
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
1487 ext3_fsblk_t goal, unsigned long *count, int *errp)
1488{
1489 struct buffer_head *bitmap_bh = NULL;
1490 struct buffer_head *gdp_bh;
1491 int group_no;
1492 int goal_group;
1493 ext3_grpblk_t grp_target_blk;
1494 ext3_grpblk_t grp_alloc_blk;
1495 ext3_fsblk_t ret_block;
1496 int bgi;
1497 int fatal = 0, err;
1498 int performed_allocation = 0;
1499 ext3_grpblk_t free_blocks;
1500 struct super_block *sb;
1501 struct ext3_group_desc *gdp;
1502 struct ext3_super_block *es;
1503 struct ext3_sb_info *sbi;
1504 struct ext3_reserve_window_node *my_rsv = NULL;
1505 struct ext3_block_alloc_info *block_i;
1506 unsigned short windowsz = 0;
1507#ifdef EXT3FS_DEBUG
1508 static int goal_hits, goal_attempts;
1509#endif
1510 unsigned long ngroups;
1511 unsigned long num = *count;
1512
1513 *errp = -ENOSPC;
1514 sb = inode->i_sb;
1515
1516
1517
1518
1519 err = dquot_alloc_block(inode, num);
1520 if (err) {
1521 *errp = err;
1522 return 0;
1523 }
1524
1525 trace_ext3_request_blocks(inode, goal, num);
1526
1527 sbi = EXT3_SB(sb);
1528 es = sbi->s_es;
1529 ext3_debug("goal=%lu.\n", goal);
1530
1531
1532
1533
1534
1535
1536
1537
1538 block_i = EXT3_I(inode)->i_block_alloc_info;
1539 if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
1540 my_rsv = &block_i->rsv_window_node;
1541
1542 if (!ext3_has_free_blocks(sbi, IS_NOQUOTA(inode))) {
1543 *errp = -ENOSPC;
1544 goto out;
1545 }
1546
1547
1548
1549
1550 if (goal < le32_to_cpu(es->s_first_data_block) ||
1551 goal >= le32_to_cpu(es->s_blocks_count))
1552 goal = le32_to_cpu(es->s_first_data_block);
1553 group_no = (goal - le32_to_cpu(es->s_first_data_block)) /
1554 EXT3_BLOCKS_PER_GROUP(sb);
1555 goal_group = group_no;
1556retry_alloc:
1557 gdp = ext3_get_group_desc(sb, group_no, &gdp_bh);
1558 if (!gdp)
1559 goto io_error;
1560
1561 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1562
1563
1564
1565
1566 if (my_rsv && (free_blocks < windowsz)
1567 && (free_blocks > 0)
1568 && (rsv_is_empty(&my_rsv->rsv_window)))
1569 my_rsv = NULL;
1570
1571 if (free_blocks > 0) {
1572 grp_target_blk = ((goal - le32_to_cpu(es->s_first_data_block)) %
1573 EXT3_BLOCKS_PER_GROUP(sb));
1574 bitmap_bh = read_block_bitmap(sb, group_no);
1575 if (!bitmap_bh)
1576 goto io_error;
1577 grp_alloc_blk = ext3_try_to_allocate_with_rsv(sb, handle,
1578 group_no, bitmap_bh, grp_target_blk,
1579 my_rsv, &num, &fatal);
1580 if (fatal)
1581 goto out;
1582 if (grp_alloc_blk >= 0)
1583 goto allocated;
1584 }
1585
1586 ngroups = EXT3_SB(sb)->s_groups_count;
1587 smp_rmb();
1588
1589
1590
1591
1592
1593 for (bgi = 0; bgi < ngroups; bgi++) {
1594 group_no++;
1595 if (group_no >= ngroups)
1596 group_no = 0;
1597 gdp = ext3_get_group_desc(sb, group_no, &gdp_bh);
1598 if (!gdp)
1599 goto io_error;
1600 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1601
1602
1603
1604
1605 if (!free_blocks)
1606 continue;
1607
1608
1609
1610
1611
1612 if (my_rsv && (free_blocks <= (windowsz/2)))
1613 continue;
1614
1615 brelse(bitmap_bh);
1616 bitmap_bh = read_block_bitmap(sb, group_no);
1617 if (!bitmap_bh)
1618 goto io_error;
1619
1620
1621
1622 grp_alloc_blk = ext3_try_to_allocate_with_rsv(sb, handle,
1623 group_no, bitmap_bh, -1, my_rsv,
1624 &num, &fatal);
1625 if (fatal)
1626 goto out;
1627 if (grp_alloc_blk >= 0)
1628 goto allocated;
1629 }
1630
1631
1632
1633
1634
1635
1636
1637 if (my_rsv) {
1638 my_rsv = NULL;
1639 windowsz = 0;
1640 group_no = goal_group;
1641 goto retry_alloc;
1642 }
1643
1644 *errp = -ENOSPC;
1645 goto out;
1646
1647allocated:
1648
1649 ext3_debug("using block group %d(%d)\n",
1650 group_no, gdp->bg_free_blocks_count);
1651
1652 BUFFER_TRACE(gdp_bh, "get_write_access");
1653 fatal = ext3_journal_get_write_access(handle, gdp_bh);
1654 if (fatal)
1655 goto out;
1656
1657 ret_block = grp_alloc_blk + ext3_group_first_block_no(sb, group_no);
1658
1659 if (in_range(le32_to_cpu(gdp->bg_block_bitmap), ret_block, num) ||
1660 in_range(le32_to_cpu(gdp->bg_inode_bitmap), ret_block, num) ||
1661 in_range(ret_block, le32_to_cpu(gdp->bg_inode_table),
1662 EXT3_SB(sb)->s_itb_per_group) ||
1663 in_range(ret_block + num - 1, le32_to_cpu(gdp->bg_inode_table),
1664 EXT3_SB(sb)->s_itb_per_group)) {
1665 ext3_error(sb, "ext3_new_block",
1666 "Allocating block in system zone - "
1667 "blocks from "E3FSBLK", length %lu",
1668 ret_block, num);
1669
1670
1671
1672
1673 goto retry_alloc;
1674 }
1675
1676 performed_allocation = 1;
1677
1678#ifdef CONFIG_JBD_DEBUG
1679 {
1680 struct buffer_head *debug_bh;
1681
1682
1683 debug_bh = sb_find_get_block(sb, ret_block);
1684 if (debug_bh) {
1685 BUFFER_TRACE(debug_bh, "state when allocated");
1686 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap state");
1687 brelse(debug_bh);
1688 }
1689 }
1690 jbd_lock_bh_state(bitmap_bh);
1691 spin_lock(sb_bgl_lock(sbi, group_no));
1692 if (buffer_jbd(bitmap_bh) && bh2jh(bitmap_bh)->b_committed_data) {
1693 int i;
1694
1695 for (i = 0; i < num; i++) {
1696 if (ext3_test_bit(grp_alloc_blk+i,
1697 bh2jh(bitmap_bh)->b_committed_data)) {
1698 printk("%s: block was unexpectedly set in "
1699 "b_committed_data\n", __func__);
1700 }
1701 }
1702 }
1703 ext3_debug("found bit %d\n", grp_alloc_blk);
1704 spin_unlock(sb_bgl_lock(sbi, group_no));
1705 jbd_unlock_bh_state(bitmap_bh);
1706#endif
1707
1708 if (ret_block + num - 1 >= le32_to_cpu(es->s_blocks_count)) {
1709 ext3_error(sb, "ext3_new_block",
1710 "block("E3FSBLK") >= blocks count(%d) - "
1711 "block_group = %d, es == %p ", ret_block,
1712 le32_to_cpu(es->s_blocks_count), group_no, es);
1713 goto out;
1714 }
1715
1716
1717
1718
1719
1720
1721 ext3_debug("allocating block %lu. Goal hits %d of %d.\n",
1722 ret_block, goal_hits, goal_attempts);
1723
1724 spin_lock(sb_bgl_lock(sbi, group_no));
1725 le16_add_cpu(&gdp->bg_free_blocks_count, -num);
1726 spin_unlock(sb_bgl_lock(sbi, group_no));
1727 percpu_counter_sub(&sbi->s_freeblocks_counter, num);
1728
1729 BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
1730 fatal = ext3_journal_dirty_metadata(handle, gdp_bh);
1731 if (fatal)
1732 goto out;
1733
1734 *errp = 0;
1735 brelse(bitmap_bh);
1736
1737 if (num < *count) {
1738 dquot_free_block(inode, *count-num);
1739 *count = num;
1740 }
1741
1742 trace_ext3_allocate_blocks(inode, goal, num,
1743 (unsigned long long)ret_block);
1744
1745 return ret_block;
1746
1747io_error:
1748 *errp = -EIO;
1749out:
1750 if (fatal) {
1751 *errp = fatal;
1752 ext3_std_error(sb, fatal);
1753 }
1754
1755
1756
1757 if (!performed_allocation)
1758 dquot_free_block(inode, *count);
1759 brelse(bitmap_bh);
1760 return 0;
1761}
1762
1763ext3_fsblk_t ext3_new_block(handle_t *handle, struct inode *inode,
1764 ext3_fsblk_t goal, int *errp)
1765{
1766 unsigned long count = 1;
1767
1768 return ext3_new_blocks(handle, inode, goal, &count, errp);
1769}
1770
1771
1772
1773
1774
1775
1776
1777ext3_fsblk_t ext3_count_free_blocks(struct super_block *sb)
1778{
1779 ext3_fsblk_t desc_count;
1780 struct ext3_group_desc *gdp;
1781 int i;
1782 unsigned long ngroups = EXT3_SB(sb)->s_groups_count;
1783#ifdef EXT3FS_DEBUG
1784 struct ext3_super_block *es;
1785 ext3_fsblk_t bitmap_count;
1786 unsigned long x;
1787 struct buffer_head *bitmap_bh = NULL;
1788
1789 es = EXT3_SB(sb)->s_es;
1790 desc_count = 0;
1791 bitmap_count = 0;
1792 gdp = NULL;
1793
1794 smp_rmb();
1795 for (i = 0; i < ngroups; i++) {
1796 gdp = ext3_get_group_desc(sb, i, NULL);
1797 if (!gdp)
1798 continue;
1799 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1800 brelse(bitmap_bh);
1801 bitmap_bh = read_block_bitmap(sb, i);
1802 if (bitmap_bh == NULL)
1803 continue;
1804
1805 x = ext3_count_free(bitmap_bh, sb->s_blocksize);
1806 printk("group %d: stored = %d, counted = %lu\n",
1807 i, le16_to_cpu(gdp->bg_free_blocks_count), x);
1808 bitmap_count += x;
1809 }
1810 brelse(bitmap_bh);
1811 printk("ext3_count_free_blocks: stored = "E3FSBLK
1812 ", computed = "E3FSBLK", "E3FSBLK"\n",
1813 (ext3_fsblk_t)le32_to_cpu(es->s_free_blocks_count),
1814 desc_count, bitmap_count);
1815 return bitmap_count;
1816#else
1817 desc_count = 0;
1818 smp_rmb();
1819 for (i = 0; i < ngroups; i++) {
1820 gdp = ext3_get_group_desc(sb, i, NULL);
1821 if (!gdp)
1822 continue;
1823 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1824 }
1825
1826 return desc_count;
1827#endif
1828}
1829
1830static inline int test_root(int a, int b)
1831{
1832 int num = b;
1833
1834 while (a > num)
1835 num *= b;
1836 return num == a;
1837}
1838
1839static int ext3_group_sparse(int group)
1840{
1841 if (group <= 1)
1842 return 1;
1843 if (!(group & 1))
1844 return 0;
1845 return (test_root(group, 7) || test_root(group, 5) ||
1846 test_root(group, 3));
1847}
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857int ext3_bg_has_super(struct super_block *sb, int group)
1858{
1859 if (EXT3_HAS_RO_COMPAT_FEATURE(sb,
1860 EXT3_FEATURE_RO_COMPAT_SPARSE_SUPER) &&
1861 !ext3_group_sparse(group))
1862 return 0;
1863 return 1;
1864}
1865
1866static unsigned long ext3_bg_num_gdb_meta(struct super_block *sb, int group)
1867{
1868 unsigned long metagroup = group / EXT3_DESC_PER_BLOCK(sb);
1869 unsigned long first = metagroup * EXT3_DESC_PER_BLOCK(sb);
1870 unsigned long last = first + EXT3_DESC_PER_BLOCK(sb) - 1;
1871
1872 if (group == first || group == first + 1 || group == last)
1873 return 1;
1874 return 0;
1875}
1876
1877static unsigned long ext3_bg_num_gdb_nometa(struct super_block *sb, int group)
1878{
1879 return ext3_bg_has_super(sb, group) ? EXT3_SB(sb)->s_gdb_count : 0;
1880}
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
1892{
1893 unsigned long first_meta_bg =
1894 le32_to_cpu(EXT3_SB(sb)->s_es->s_first_meta_bg);
1895 unsigned long metagroup = group / EXT3_DESC_PER_BLOCK(sb);
1896
1897 if (!EXT3_HAS_INCOMPAT_FEATURE(sb,EXT3_FEATURE_INCOMPAT_META_BG) ||
1898 metagroup < first_meta_bg)
1899 return ext3_bg_num_gdb_nometa(sb,group);
1900
1901 return ext3_bg_num_gdb_meta(sb,group);
1902
1903}
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920static ext3_grpblk_t ext3_trim_all_free(struct super_block *sb,
1921 unsigned int group,
1922 ext3_grpblk_t start, ext3_grpblk_t max,
1923 ext3_grpblk_t minblocks)
1924{
1925 handle_t *handle;
1926 ext3_grpblk_t next, free_blocks, bit, freed, count = 0;
1927 ext3_fsblk_t discard_block;
1928 struct ext3_sb_info *sbi;
1929 struct buffer_head *gdp_bh, *bitmap_bh = NULL;
1930 struct ext3_group_desc *gdp;
1931 int err = 0, ret = 0;
1932
1933
1934
1935
1936 handle = ext3_journal_start_sb(sb, 2);
1937 if (IS_ERR(handle))
1938 return PTR_ERR(handle);
1939
1940 bitmap_bh = read_block_bitmap(sb, group);
1941 if (!bitmap_bh) {
1942 err = -EIO;
1943 goto err_out;
1944 }
1945
1946 BUFFER_TRACE(bitmap_bh, "getting undo access");
1947 err = ext3_journal_get_undo_access(handle, bitmap_bh);
1948 if (err)
1949 goto err_out;
1950
1951 gdp = ext3_get_group_desc(sb, group, &gdp_bh);
1952 if (!gdp) {
1953 err = -EIO;
1954 goto err_out;
1955 }
1956
1957 BUFFER_TRACE(gdp_bh, "get_write_access");
1958 err = ext3_journal_get_write_access(handle, gdp_bh);
1959 if (err)
1960 goto err_out;
1961
1962 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1963 sbi = EXT3_SB(sb);
1964
1965
1966 while (start <= max) {
1967 start = bitmap_search_next_usable_block(start, bitmap_bh, max);
1968 if (start < 0)
1969 break;
1970 next = start;
1971
1972
1973
1974
1975
1976 while (next <= max
1977 && claim_block(sb_bgl_lock(sbi, group),
1978 next, bitmap_bh)) {
1979 next++;
1980 }
1981
1982
1983 if (next == start)
1984 continue;
1985
1986 discard_block = (ext3_fsblk_t)start +
1987 ext3_group_first_block_no(sb, group);
1988
1989
1990 spin_lock(sb_bgl_lock(sbi, group));
1991 le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
1992 spin_unlock(sb_bgl_lock(sbi, group));
1993 percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
1994
1995 free_blocks -= next - start;
1996
1997 if ((next - start) < minblocks)
1998 goto free_extent;
1999
2000 trace_ext3_discard_blocks(sb, discard_block, next - start);
2001
2002 err = sb_issue_discard(sb, discard_block, next - start,
2003 GFP_NOFS, 0);
2004 count += (next - start);
2005free_extent:
2006 freed = 0;
2007
2008
2009
2010
2011 for (bit = start; bit < next; bit++) {
2012 BUFFER_TRACE(bitmap_bh, "clear bit");
2013 if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
2014 bit, bitmap_bh->b_data)) {
2015 ext3_error(sb, __func__,
2016 "bit already cleared for block "E3FSBLK,
2017 (unsigned long)bit);
2018 BUFFER_TRACE(bitmap_bh, "bit already cleared");
2019 } else {
2020 freed++;
2021 }
2022 }
2023
2024
2025 spin_lock(sb_bgl_lock(sbi, group));
2026 le16_add_cpu(&gdp->bg_free_blocks_count, freed);
2027 spin_unlock(sb_bgl_lock(sbi, group));
2028 percpu_counter_add(&sbi->s_freeblocks_counter, freed);
2029
2030 start = next;
2031 if (err < 0) {
2032 if (err != -EOPNOTSUPP)
2033 ext3_warning(sb, __func__, "Discard command "
2034 "returned error %d\n", err);
2035 break;
2036 }
2037
2038 if (fatal_signal_pending(current)) {
2039 err = -ERESTARTSYS;
2040 break;
2041 }
2042
2043 cond_resched();
2044
2045
2046 if (free_blocks < minblocks)
2047 break;
2048 }
2049
2050
2051 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
2052 ret = ext3_journal_dirty_metadata(handle, bitmap_bh);
2053 if (!err)
2054 err = ret;
2055
2056
2057 BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
2058 ret = ext3_journal_dirty_metadata(handle, gdp_bh);
2059 if (!err)
2060 err = ret;
2061
2062 ext3_debug("trimmed %d blocks in the group %d\n",
2063 count, group);
2064
2065err_out:
2066 if (err)
2067 count = err;
2068 ext3_journal_stop(handle);
2069 brelse(bitmap_bh);
2070
2071 return count;
2072}
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085int ext3_trim_fs(struct super_block *sb, struct fstrim_range *range)
2086{
2087 ext3_grpblk_t last_block, first_block;
2088 unsigned long group, first_group, last_group;
2089 struct ext3_group_desc *gdp;
2090 struct ext3_super_block *es = EXT3_SB(sb)->s_es;
2091 uint64_t start, minlen, end, trimmed = 0;
2092 ext3_fsblk_t first_data_blk =
2093 le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block);
2094 ext3_fsblk_t max_blks = le32_to_cpu(es->s_blocks_count);
2095 int ret = 0;
2096
2097 start = range->start >> sb->s_blocksize_bits;
2098 end = start + (range->len >> sb->s_blocksize_bits) - 1;
2099 minlen = range->minlen >> sb->s_blocksize_bits;
2100
2101 if (minlen > EXT3_BLOCKS_PER_GROUP(sb) ||
2102 start >= max_blks ||
2103 range->len < sb->s_blocksize)
2104 return -EINVAL;
2105 if (end >= max_blks)
2106 end = max_blks - 1;
2107 if (end <= first_data_blk)
2108 goto out;
2109 if (start < first_data_blk)
2110 start = first_data_blk;
2111
2112 smp_rmb();
2113
2114
2115 ext3_get_group_no_and_offset(sb, (ext3_fsblk_t) start,
2116 &first_group, &first_block);
2117 ext3_get_group_no_and_offset(sb, (ext3_fsblk_t) end,
2118 &last_group, &last_block);
2119
2120
2121 end = EXT3_BLOCKS_PER_GROUP(sb) - 1;
2122
2123 for (group = first_group; group <= last_group; group++) {
2124 gdp = ext3_get_group_desc(sb, group, NULL);
2125 if (!gdp)
2126 break;
2127
2128
2129
2130
2131
2132
2133
2134 if (group == last_group)
2135 end = last_block;
2136
2137 if (le16_to_cpu(gdp->bg_free_blocks_count) >= minlen) {
2138 ret = ext3_trim_all_free(sb, group, first_block,
2139 end, minlen);
2140 if (ret < 0)
2141 break;
2142 trimmed += ret;
2143 }
2144
2145
2146
2147
2148
2149 first_block = 0;
2150 }
2151
2152 if (ret > 0)
2153 ret = 0;
2154
2155out:
2156 range->len = trimmed * sb->s_blocksize;
2157 return ret;
2158}
2159