1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#include "ext2.h"
16#include <linux/quotaops.h>
17#include <linux/slab.h>
18#include <linux/sched.h>
19#include <linux/cred.h>
20#include <linux/buffer_head.h>
21#include <linux/capability.h>
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
40
41struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb,
42 unsigned int block_group,
43 struct buffer_head ** bh)
44{
45 unsigned long group_desc;
46 unsigned long offset;
47 struct ext2_group_desc * desc;
48 struct ext2_sb_info *sbi = EXT2_SB(sb);
49
50 if (block_group >= sbi->s_groups_count) {
51 ext2_error (sb, "ext2_get_group_desc",
52 "block_group >= groups_count - "
53 "block_group = %d, groups_count = %lu",
54 block_group, sbi->s_groups_count);
55
56 return NULL;
57 }
58
59 group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb);
60 offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1);
61 if (!sbi->s_group_desc[group_desc]) {
62 ext2_error (sb, "ext2_get_group_desc",
63 "Group descriptor not loaded - "
64 "block_group = %d, group_desc = %lu, desc = %lu",
65 block_group, group_desc, offset);
66 return NULL;
67 }
68
69 desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data;
70 if (bh)
71 *bh = sbi->s_group_desc[group_desc];
72 return desc + offset;
73}
74
75static int ext2_valid_block_bitmap(struct super_block *sb,
76 struct ext2_group_desc *desc,
77 unsigned int block_group,
78 struct buffer_head *bh)
79{
80 ext2_grpblk_t offset;
81 ext2_grpblk_t next_zero_bit;
82 ext2_fsblk_t bitmap_blk;
83 ext2_fsblk_t group_first_block;
84
85 group_first_block = ext2_group_first_block_no(sb, block_group);
86
87
88 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
89 offset = bitmap_blk - group_first_block;
90 if (!ext2_test_bit(offset, bh->b_data))
91
92 goto err_out;
93
94
95 bitmap_blk = le32_to_cpu(desc->bg_inode_bitmap);
96 offset = bitmap_blk - group_first_block;
97 if (!ext2_test_bit(offset, bh->b_data))
98
99 goto err_out;
100
101
102 bitmap_blk = le32_to_cpu(desc->bg_inode_table);
103 offset = bitmap_blk - group_first_block;
104 next_zero_bit = ext2_find_next_zero_bit(bh->b_data,
105 offset + EXT2_SB(sb)->s_itb_per_group,
106 offset);
107 if (next_zero_bit >= offset + EXT2_SB(sb)->s_itb_per_group)
108
109 return 1;
110
111err_out:
112 ext2_error(sb, __func__,
113 "Invalid block bitmap - "
114 "block_group = %d, block = %lu",
115 block_group, bitmap_blk);
116 return 0;
117}
118
119
120
121
122
123
124
125static struct buffer_head *
126read_block_bitmap(struct super_block *sb, unsigned int block_group)
127{
128 struct ext2_group_desc * desc;
129 struct buffer_head * bh = NULL;
130 ext2_fsblk_t bitmap_blk;
131
132 desc = ext2_get_group_desc(sb, block_group, NULL);
133 if (!desc)
134 return NULL;
135 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
136 bh = sb_getblk(sb, bitmap_blk);
137 if (unlikely(!bh)) {
138 ext2_error(sb, __func__,
139 "Cannot read block bitmap - "
140 "block_group = %d, block_bitmap = %u",
141 block_group, le32_to_cpu(desc->bg_block_bitmap));
142 return NULL;
143 }
144 if (likely(bh_uptodate_or_lock(bh)))
145 return bh;
146
147 if (bh_submit_read(bh) < 0) {
148 brelse(bh);
149 ext2_error(sb, __func__,
150 "Cannot read block bitmap - "
151 "block_group = %d, block_bitmap = %u",
152 block_group, le32_to_cpu(desc->bg_block_bitmap));
153 return NULL;
154 }
155
156 ext2_valid_block_bitmap(sb, desc, block_group, bh);
157
158
159
160
161 return bh;
162}
163
164static void group_adjust_blocks(struct super_block *sb, int group_no,
165 struct ext2_group_desc *desc, struct buffer_head *bh, int count)
166{
167 if (count) {
168 struct ext2_sb_info *sbi = EXT2_SB(sb);
169 unsigned free_blocks;
170
171 spin_lock(sb_bgl_lock(sbi, group_no));
172 free_blocks = le16_to_cpu(desc->bg_free_blocks_count);
173 desc->bg_free_blocks_count = cpu_to_le16(free_blocks + count);
174 spin_unlock(sb_bgl_lock(sbi, group_no));
175 mark_buffer_dirty(bh);
176 }
177}
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200#if 1
201static void __rsv_window_dump(struct rb_root *root, int verbose,
202 const char *fn)
203{
204 struct rb_node *n;
205 struct ext2_reserve_window_node *rsv, *prev;
206 int bad;
207
208restart:
209 n = rb_first(root);
210 bad = 0;
211 prev = NULL;
212
213 printk("Block Allocation Reservation Windows Map (%s):\n", fn);
214 while (n) {
215 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
216 if (verbose)
217 printk("reservation window 0x%p "
218 "start: %lu, end: %lu\n",
219 rsv, rsv->rsv_start, rsv->rsv_end);
220 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
221 printk("Bad reservation %p (start >= end)\n",
222 rsv);
223 bad = 1;
224 }
225 if (prev && prev->rsv_end >= rsv->rsv_start) {
226 printk("Bad reservation %p (prev->end >= start)\n",
227 rsv);
228 bad = 1;
229 }
230 if (bad) {
231 if (!verbose) {
232 printk("Restarting reservation walk in verbose mode\n");
233 verbose = 1;
234 goto restart;
235 }
236 }
237 n = rb_next(n);
238 prev = rsv;
239 }
240 printk("Window map complete.\n");
241 BUG_ON(bad);
242}
243#define rsv_window_dump(root, verbose) \
244 __rsv_window_dump((root), (verbose), __func__)
245#else
246#define rsv_window_dump(root, verbose) do {} while (0)
247#endif
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265static int
266goal_in_my_reservation(struct ext2_reserve_window *rsv, ext2_grpblk_t grp_goal,
267 unsigned int group, struct super_block * sb)
268{
269 ext2_fsblk_t group_first_block, group_last_block;
270
271 group_first_block = ext2_group_first_block_no(sb, group);
272 group_last_block = group_first_block + EXT2_BLOCKS_PER_GROUP(sb) - 1;
273
274 if ((rsv->_rsv_start > group_last_block) ||
275 (rsv->_rsv_end < group_first_block))
276 return 0;
277 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
278 || (grp_goal + group_first_block > rsv->_rsv_end)))
279 return 0;
280 return 1;
281}
282
283
284
285
286
287
288
289
290
291
292static struct ext2_reserve_window_node *
293search_reserve_window(struct rb_root *root, ext2_fsblk_t goal)
294{
295 struct rb_node *n = root->rb_node;
296 struct ext2_reserve_window_node *rsv;
297
298 if (!n)
299 return NULL;
300
301 do {
302 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
303
304 if (goal < rsv->rsv_start)
305 n = n->rb_left;
306 else if (goal > rsv->rsv_end)
307 n = n->rb_right;
308 else
309 return rsv;
310 } while (n);
311
312
313
314
315
316
317 if (rsv->rsv_start > goal) {
318 n = rb_prev(&rsv->rsv_node);
319 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
320 }
321 return rsv;
322}
323
324
325
326
327
328
329
330
331void ext2_rsv_window_add(struct super_block *sb,
332 struct ext2_reserve_window_node *rsv)
333{
334 struct rb_root *root = &EXT2_SB(sb)->s_rsv_window_root;
335 struct rb_node *node = &rsv->rsv_node;
336 ext2_fsblk_t start = rsv->rsv_start;
337
338 struct rb_node ** p = &root->rb_node;
339 struct rb_node * parent = NULL;
340 struct ext2_reserve_window_node *this;
341
342 while (*p)
343 {
344 parent = *p;
345 this = rb_entry(parent, struct ext2_reserve_window_node, rsv_node);
346
347 if (start < this->rsv_start)
348 p = &(*p)->rb_left;
349 else if (start > this->rsv_end)
350 p = &(*p)->rb_right;
351 else {
352 rsv_window_dump(root, 1);
353 BUG();
354 }
355 }
356
357 rb_link_node(node, parent, p);
358 rb_insert_color(node, root);
359}
360
361
362
363
364
365
366
367
368
369
370static void rsv_window_remove(struct super_block *sb,
371 struct ext2_reserve_window_node *rsv)
372{
373 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
374 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
375 rsv->rsv_alloc_hit = 0;
376 rb_erase(&rsv->rsv_node, &EXT2_SB(sb)->s_rsv_window_root);
377}
378
379
380
381
382
383
384
385static inline int rsv_is_empty(struct ext2_reserve_window *rsv)
386{
387
388 return (rsv->_rsv_end == EXT2_RESERVE_WINDOW_NOT_ALLOCATED);
389}
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412void ext2_init_block_alloc_info(struct inode *inode)
413{
414 struct ext2_inode_info *ei = EXT2_I(inode);
415 struct ext2_block_alloc_info *block_i;
416 struct super_block *sb = inode->i_sb;
417
418 block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
419 if (block_i) {
420 struct ext2_reserve_window_node *rsv = &block_i->rsv_window_node;
421
422 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
423 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
424
425
426
427
428
429
430 if (!test_opt(sb, RESERVATION))
431 rsv->rsv_goal_size = 0;
432 else
433 rsv->rsv_goal_size = EXT2_DEFAULT_RESERVE_BLOCKS;
434 rsv->rsv_alloc_hit = 0;
435 block_i->last_alloc_logical_block = 0;
436 block_i->last_alloc_physical_block = 0;
437 }
438 ei->i_block_alloc_info = block_i;
439}
440
441
442
443
444
445
446
447
448
449
450
451
452
453void ext2_discard_reservation(struct inode *inode)
454{
455 struct ext2_inode_info *ei = EXT2_I(inode);
456 struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info;
457 struct ext2_reserve_window_node *rsv;
458 spinlock_t *rsv_lock = &EXT2_SB(inode->i_sb)->s_rsv_window_lock;
459
460 if (!block_i)
461 return;
462
463 rsv = &block_i->rsv_window_node;
464 if (!rsv_is_empty(&rsv->rsv_window)) {
465 spin_lock(rsv_lock);
466 if (!rsv_is_empty(&rsv->rsv_window))
467 rsv_window_remove(inode->i_sb, rsv);
468 spin_unlock(rsv_lock);
469 }
470}
471
472
473
474
475
476
477
478void ext2_free_blocks (struct inode * inode, unsigned long block,
479 unsigned long count)
480{
481 struct buffer_head *bitmap_bh = NULL;
482 struct buffer_head * bh2;
483 unsigned long block_group;
484 unsigned long bit;
485 unsigned long i;
486 unsigned long overflow;
487 struct super_block * sb = inode->i_sb;
488 struct ext2_sb_info * sbi = EXT2_SB(sb);
489 struct ext2_group_desc * desc;
490 struct ext2_super_block * es = sbi->s_es;
491 unsigned freed = 0, group_freed;
492
493 if (block < le32_to_cpu(es->s_first_data_block) ||
494 block + count < block ||
495 block + count > le32_to_cpu(es->s_blocks_count)) {
496 ext2_error (sb, "ext2_free_blocks",
497 "Freeing blocks not in datazone - "
498 "block = %lu, count = %lu", block, count);
499 goto error_return;
500 }
501
502 ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
503
504do_more:
505 overflow = 0;
506 block_group = (block - le32_to_cpu(es->s_first_data_block)) /
507 EXT2_BLOCKS_PER_GROUP(sb);
508 bit = (block - le32_to_cpu(es->s_first_data_block)) %
509 EXT2_BLOCKS_PER_GROUP(sb);
510
511
512
513
514 if (bit + count > EXT2_BLOCKS_PER_GROUP(sb)) {
515 overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb);
516 count -= overflow;
517 }
518 brelse(bitmap_bh);
519 bitmap_bh = read_block_bitmap(sb, block_group);
520 if (!bitmap_bh)
521 goto error_return;
522
523 desc = ext2_get_group_desc (sb, block_group, &bh2);
524 if (!desc)
525 goto error_return;
526
527 if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
528 in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
529 in_range (block, le32_to_cpu(desc->bg_inode_table),
530 sbi->s_itb_per_group) ||
531 in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
532 sbi->s_itb_per_group)) {
533 ext2_error (sb, "ext2_free_blocks",
534 "Freeing blocks in system zones - "
535 "Block = %lu, count = %lu",
536 block, count);
537 goto error_return;
538 }
539
540 for (i = 0, group_freed = 0; i < count; i++) {
541 if (!ext2_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
542 bit + i, bitmap_bh->b_data)) {
543 ext2_error(sb, __func__,
544 "bit already cleared for block %lu", block + i);
545 } else {
546 group_freed++;
547 }
548 }
549
550 mark_buffer_dirty(bitmap_bh);
551 if (sb->s_flags & SB_SYNCHRONOUS)
552 sync_dirty_buffer(bitmap_bh);
553
554 group_adjust_blocks(sb, block_group, desc, bh2, group_freed);
555 freed += group_freed;
556
557 if (overflow) {
558 block += count;
559 count = overflow;
560 goto do_more;
561 }
562error_return:
563 brelse(bitmap_bh);
564 if (freed) {
565 percpu_counter_add(&sbi->s_freeblocks_counter, freed);
566 dquot_free_block_nodirty(inode, freed);
567 mark_inode_dirty(inode);
568 }
569}
570
571
572
573
574
575
576
577
578
579
580static ext2_grpblk_t
581bitmap_search_next_usable_block(ext2_grpblk_t start, struct buffer_head *bh,
582 ext2_grpblk_t maxblocks)
583{
584 ext2_grpblk_t next;
585
586 next = ext2_find_next_zero_bit(bh->b_data, maxblocks, start);
587 if (next >= maxblocks)
588 return -1;
589 return next;
590}
591
592
593
594
595
596
597
598
599
600
601
602
603
604static ext2_grpblk_t
605find_next_usable_block(int start, struct buffer_head *bh, int maxblocks)
606{
607 ext2_grpblk_t here, next;
608 char *p, *r;
609
610 if (start > 0) {
611
612
613
614
615
616
617
618
619 ext2_grpblk_t end_goal = (start + 63) & ~63;
620 if (end_goal > maxblocks)
621 end_goal = maxblocks;
622 here = ext2_find_next_zero_bit(bh->b_data, end_goal, start);
623 if (here < end_goal)
624 return here;
625 ext2_debug("Bit not found near goal\n");
626 }
627
628 here = start;
629 if (here < 0)
630 here = 0;
631
632 p = ((char *)bh->b_data) + (here >> 3);
633 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
634 next = (r - ((char *)bh->b_data)) << 3;
635
636 if (next < maxblocks && next >= here)
637 return next;
638
639 here = bitmap_search_next_usable_block(here, bh, maxblocks);
640 return here;
641}
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665static int
666ext2_try_to_allocate(struct super_block *sb, int group,
667 struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal,
668 unsigned long *count,
669 struct ext2_reserve_window *my_rsv)
670{
671 ext2_fsblk_t group_first_block;
672 ext2_grpblk_t start, end;
673 unsigned long num = 0;
674
675
676 if (my_rsv) {
677 group_first_block = ext2_group_first_block_no(sb, group);
678 if (my_rsv->_rsv_start >= group_first_block)
679 start = my_rsv->_rsv_start - group_first_block;
680 else
681
682 start = 0;
683 end = my_rsv->_rsv_end - group_first_block + 1;
684 if (end > EXT2_BLOCKS_PER_GROUP(sb))
685
686 end = EXT2_BLOCKS_PER_GROUP(sb);
687 if ((start <= grp_goal) && (grp_goal < end))
688 start = grp_goal;
689 else
690 grp_goal = -1;
691 } else {
692 if (grp_goal > 0)
693 start = grp_goal;
694 else
695 start = 0;
696 end = EXT2_BLOCKS_PER_GROUP(sb);
697 }
698
699 BUG_ON(start > EXT2_BLOCKS_PER_GROUP(sb));
700
701repeat:
702 if (grp_goal < 0) {
703 grp_goal = find_next_usable_block(start, bitmap_bh, end);
704 if (grp_goal < 0)
705 goto fail_access;
706 if (!my_rsv) {
707 int i;
708
709 for (i = 0; i < 7 && grp_goal > start &&
710 !ext2_test_bit(grp_goal - 1,
711 bitmap_bh->b_data);
712 i++, grp_goal--)
713 ;
714 }
715 }
716 start = grp_goal;
717
718 if (ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group), grp_goal,
719 bitmap_bh->b_data)) {
720
721
722
723
724 start++;
725 grp_goal++;
726 if (start >= end)
727 goto fail_access;
728 goto repeat;
729 }
730 num++;
731 grp_goal++;
732 while (num < *count && grp_goal < end
733 && !ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group),
734 grp_goal, bitmap_bh->b_data)) {
735 num++;
736 grp_goal++;
737 }
738 *count = num;
739 return grp_goal - num;
740fail_access:
741 *count = num;
742 return -1;
743}
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778static int find_next_reservable_window(
779 struct ext2_reserve_window_node *search_head,
780 struct ext2_reserve_window_node *my_rsv,
781 struct super_block * sb,
782 ext2_fsblk_t start_block,
783 ext2_fsblk_t last_block)
784{
785 struct rb_node *next;
786 struct ext2_reserve_window_node *rsv, *prev;
787 ext2_fsblk_t cur;
788 int size = my_rsv->rsv_goal_size;
789
790
791
792 cur = start_block;
793 rsv = search_head;
794 if (!rsv)
795 return -1;
796
797 while (1) {
798 if (cur <= rsv->rsv_end)
799 cur = rsv->rsv_end + 1;
800
801
802
803
804
805
806
807
808
809
810 if (cur > last_block)
811 return -1;
812
813 prev = rsv;
814 next = rb_next(&rsv->rsv_node);
815 rsv = rb_entry(next,struct ext2_reserve_window_node,rsv_node);
816
817
818
819
820
821 if (!next)
822 break;
823
824 if (cur + size <= rsv->rsv_start) {
825
826
827
828
829 break;
830 }
831 }
832
833
834
835
836
837
838
839
840
841
842
843 if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
844 rsv_window_remove(sb, my_rsv);
845
846
847
848
849
850
851
852
853 my_rsv->rsv_start = cur;
854 my_rsv->rsv_end = cur + size - 1;
855 my_rsv->rsv_alloc_hit = 0;
856
857 if (prev != my_rsv)
858 ext2_rsv_window_add(sb, my_rsv);
859
860 return 0;
861}
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900static int alloc_new_reservation(struct ext2_reserve_window_node *my_rsv,
901 ext2_grpblk_t grp_goal, struct super_block *sb,
902 unsigned int group, struct buffer_head *bitmap_bh)
903{
904 struct ext2_reserve_window_node *search_head;
905 ext2_fsblk_t group_first_block, group_end_block, start_block;
906 ext2_grpblk_t first_free_block;
907 struct rb_root *fs_rsv_root = &EXT2_SB(sb)->s_rsv_window_root;
908 unsigned long size;
909 int ret;
910 spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock;
911
912 group_first_block = ext2_group_first_block_no(sb, group);
913 group_end_block = group_first_block + (EXT2_BLOCKS_PER_GROUP(sb) - 1);
914
915 if (grp_goal < 0)
916 start_block = group_first_block;
917 else
918 start_block = grp_goal + group_first_block;
919
920 size = my_rsv->rsv_goal_size;
921
922 if (!rsv_is_empty(&my_rsv->rsv_window)) {
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937 if ((my_rsv->rsv_start <= group_end_block) &&
938 (my_rsv->rsv_end > group_end_block) &&
939 (start_block >= my_rsv->rsv_start))
940 return -1;
941
942 if ((my_rsv->rsv_alloc_hit >
943 (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
944
945
946
947
948
949
950 size = size * 2;
951 if (size > EXT2_MAX_RESERVE_BLOCKS)
952 size = EXT2_MAX_RESERVE_BLOCKS;
953 my_rsv->rsv_goal_size= size;
954 }
955 }
956
957 spin_lock(rsv_lock);
958
959
960
961 search_head = search_reserve_window(fs_rsv_root, start_block);
962
963
964
965
966
967
968
969
970retry:
971 ret = find_next_reservable_window(search_head, my_rsv, sb,
972 start_block, group_end_block);
973
974 if (ret == -1) {
975 if (!rsv_is_empty(&my_rsv->rsv_window))
976 rsv_window_remove(sb, my_rsv);
977 spin_unlock(rsv_lock);
978 return -1;
979 }
980
981
982
983
984
985
986
987
988
989
990 spin_unlock(rsv_lock);
991 first_free_block = bitmap_search_next_usable_block(
992 my_rsv->rsv_start - group_first_block,
993 bitmap_bh, group_end_block - group_first_block + 1);
994
995 if (first_free_block < 0) {
996
997
998
999
1000 spin_lock(rsv_lock);
1001 if (!rsv_is_empty(&my_rsv->rsv_window))
1002 rsv_window_remove(sb, my_rsv);
1003 spin_unlock(rsv_lock);
1004 return -1;
1005 }
1006
1007 start_block = first_free_block + group_first_block;
1008
1009
1010
1011
1012 if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end)
1013 return 0;
1014
1015
1016
1017
1018
1019
1020 search_head = my_rsv;
1021 spin_lock(rsv_lock);
1022 goto retry;
1023}
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042static void try_to_extend_reservation(struct ext2_reserve_window_node *my_rsv,
1043 struct super_block *sb, int size)
1044{
1045 struct ext2_reserve_window_node *next_rsv;
1046 struct rb_node *next;
1047 spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock;
1048
1049 if (!spin_trylock(rsv_lock))
1050 return;
1051
1052 next = rb_next(&my_rsv->rsv_node);
1053
1054 if (!next)
1055 my_rsv->rsv_end += size;
1056 else {
1057 next_rsv = rb_entry(next, struct ext2_reserve_window_node, rsv_node);
1058
1059 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
1060 my_rsv->rsv_end += size;
1061 else
1062 my_rsv->rsv_end = next_rsv->rsv_start - 1;
1063 }
1064 spin_unlock(rsv_lock);
1065}
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093static ext2_grpblk_t
1094ext2_try_to_allocate_with_rsv(struct super_block *sb, unsigned int group,
1095 struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal,
1096 struct ext2_reserve_window_node * my_rsv,
1097 unsigned long *count)
1098{
1099 ext2_fsblk_t group_first_block, group_last_block;
1100 ext2_grpblk_t ret = 0;
1101 unsigned long num = *count;
1102
1103
1104
1105
1106
1107
1108
1109 if (my_rsv == NULL) {
1110 return ext2_try_to_allocate(sb, group, bitmap_bh,
1111 grp_goal, count, NULL);
1112 }
1113
1114
1115
1116
1117
1118
1119 group_first_block = ext2_group_first_block_no(sb, group);
1120 group_last_block = group_first_block + (EXT2_BLOCKS_PER_GROUP(sb) - 1);
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137 while (1) {
1138 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
1139 !goal_in_my_reservation(&my_rsv->rsv_window,
1140 grp_goal, group, sb)) {
1141 if (my_rsv->rsv_goal_size < *count)
1142 my_rsv->rsv_goal_size = *count;
1143 ret = alloc_new_reservation(my_rsv, grp_goal, sb,
1144 group, bitmap_bh);
1145 if (ret < 0)
1146 break;
1147
1148 if (!goal_in_my_reservation(&my_rsv->rsv_window,
1149 grp_goal, group, sb))
1150 grp_goal = -1;
1151 } else if (grp_goal >= 0) {
1152 int curr = my_rsv->rsv_end -
1153 (grp_goal + group_first_block) + 1;
1154
1155 if (curr < *count)
1156 try_to_extend_reservation(my_rsv, sb,
1157 *count - curr);
1158 }
1159
1160 if ((my_rsv->rsv_start > group_last_block) ||
1161 (my_rsv->rsv_end < group_first_block)) {
1162 rsv_window_dump(&EXT2_SB(sb)->s_rsv_window_root, 1);
1163 BUG();
1164 }
1165 ret = ext2_try_to_allocate(sb, group, bitmap_bh, grp_goal,
1166 &num, &my_rsv->rsv_window);
1167 if (ret >= 0) {
1168 my_rsv->rsv_alloc_hit += num;
1169 *count = num;
1170 break;
1171 }
1172 num = *count;
1173 }
1174 return ret;
1175}
1176
1177
1178
1179
1180
1181
1182
1183static int ext2_has_free_blocks(struct ext2_sb_info *sbi)
1184{
1185 ext2_fsblk_t free_blocks, root_blocks;
1186
1187 free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
1188 root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count);
1189 if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
1190 !uid_eq(sbi->s_resuid, current_fsuid()) &&
1191 (gid_eq(sbi->s_resgid, GLOBAL_ROOT_GID) ||
1192 !in_group_p (sbi->s_resgid))) {
1193 return 0;
1194 }
1195 return 1;
1196}
1197
1198
1199
1200
1201
1202int ext2_data_block_valid(struct ext2_sb_info *sbi, ext2_fsblk_t start_blk,
1203 unsigned int count)
1204{
1205 if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) ||
1206 (start_blk + count < start_blk) ||
1207 (start_blk > le32_to_cpu(sbi->s_es->s_blocks_count)))
1208 return 0;
1209
1210
1211 if ((start_blk <= sbi->s_sb_block) &&
1212 (start_blk + count >= sbi->s_sb_block))
1213 return 0;
1214
1215 return 1;
1216}
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232ext2_fsblk_t ext2_new_blocks(struct inode *inode, ext2_fsblk_t goal,
1233 unsigned long *count, int *errp)
1234{
1235 struct buffer_head *bitmap_bh = NULL;
1236 struct buffer_head *gdp_bh;
1237 int group_no;
1238 int goal_group;
1239 ext2_grpblk_t grp_target_blk;
1240 ext2_grpblk_t grp_alloc_blk;
1241 ext2_fsblk_t ret_block;
1242 int bgi;
1243 int performed_allocation = 0;
1244 ext2_grpblk_t free_blocks;
1245 struct super_block *sb;
1246 struct ext2_group_desc *gdp;
1247 struct ext2_super_block *es;
1248 struct ext2_sb_info *sbi;
1249 struct ext2_reserve_window_node *my_rsv = NULL;
1250 struct ext2_block_alloc_info *block_i;
1251 unsigned short windowsz = 0;
1252 unsigned long ngroups;
1253 unsigned long num = *count;
1254 int ret;
1255
1256 *errp = -ENOSPC;
1257 sb = inode->i_sb;
1258
1259
1260
1261
1262 ret = dquot_alloc_block(inode, num);
1263 if (ret) {
1264 *errp = ret;
1265 return 0;
1266 }
1267
1268 sbi = EXT2_SB(sb);
1269 es = EXT2_SB(sb)->s_es;
1270 ext2_debug("goal=%lu.\n", goal);
1271
1272
1273
1274
1275
1276
1277
1278
1279 block_i = EXT2_I(inode)->i_block_alloc_info;
1280 if (block_i) {
1281 windowsz = block_i->rsv_window_node.rsv_goal_size;
1282 if (windowsz > 0)
1283 my_rsv = &block_i->rsv_window_node;
1284 }
1285
1286 if (!ext2_has_free_blocks(sbi)) {
1287 *errp = -ENOSPC;
1288 goto out;
1289 }
1290
1291
1292
1293
1294 if (goal < le32_to_cpu(es->s_first_data_block) ||
1295 goal >= le32_to_cpu(es->s_blocks_count))
1296 goal = le32_to_cpu(es->s_first_data_block);
1297 group_no = (goal - le32_to_cpu(es->s_first_data_block)) /
1298 EXT2_BLOCKS_PER_GROUP(sb);
1299 goal_group = group_no;
1300retry_alloc:
1301 gdp = ext2_get_group_desc(sb, group_no, &gdp_bh);
1302 if (!gdp)
1303 goto io_error;
1304
1305 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1306
1307
1308
1309
1310 if (my_rsv && (free_blocks < windowsz)
1311 && (free_blocks > 0)
1312 && (rsv_is_empty(&my_rsv->rsv_window)))
1313 my_rsv = NULL;
1314
1315 if (free_blocks > 0) {
1316 grp_target_blk = ((goal - le32_to_cpu(es->s_first_data_block)) %
1317 EXT2_BLOCKS_PER_GROUP(sb));
1318 bitmap_bh = read_block_bitmap(sb, group_no);
1319 if (!bitmap_bh)
1320 goto io_error;
1321 grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no,
1322 bitmap_bh, grp_target_blk,
1323 my_rsv, &num);
1324 if (grp_alloc_blk >= 0)
1325 goto allocated;
1326 }
1327
1328 ngroups = EXT2_SB(sb)->s_groups_count;
1329 smp_rmb();
1330
1331
1332
1333
1334
1335 for (bgi = 0; bgi < ngroups; bgi++) {
1336 group_no++;
1337 if (group_no >= ngroups)
1338 group_no = 0;
1339 gdp = ext2_get_group_desc(sb, group_no, &gdp_bh);
1340 if (!gdp)
1341 goto io_error;
1342
1343 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1344
1345
1346
1347
1348 if (!free_blocks)
1349 continue;
1350
1351
1352
1353
1354
1355 if (my_rsv && (free_blocks <= (windowsz/2)))
1356 continue;
1357
1358 brelse(bitmap_bh);
1359 bitmap_bh = read_block_bitmap(sb, group_no);
1360 if (!bitmap_bh)
1361 goto io_error;
1362
1363
1364
1365 grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no,
1366 bitmap_bh, -1, my_rsv, &num);
1367 if (grp_alloc_blk >= 0)
1368 goto allocated;
1369 }
1370
1371
1372
1373
1374
1375
1376
1377 if (my_rsv) {
1378 my_rsv = NULL;
1379 windowsz = 0;
1380 group_no = goal_group;
1381 goto retry_alloc;
1382 }
1383
1384 *errp = -ENOSPC;
1385 goto out;
1386
1387allocated:
1388
1389 ext2_debug("using block group %d(%d)\n",
1390 group_no, gdp->bg_free_blocks_count);
1391
1392 ret_block = grp_alloc_blk + ext2_group_first_block_no(sb, group_no);
1393
1394 if (in_range(le32_to_cpu(gdp->bg_block_bitmap), ret_block, num) ||
1395 in_range(le32_to_cpu(gdp->bg_inode_bitmap), ret_block, num) ||
1396 in_range(ret_block, le32_to_cpu(gdp->bg_inode_table),
1397 EXT2_SB(sb)->s_itb_per_group) ||
1398 in_range(ret_block + num - 1, le32_to_cpu(gdp->bg_inode_table),
1399 EXT2_SB(sb)->s_itb_per_group)) {
1400 ext2_error(sb, "ext2_new_blocks",
1401 "Allocating block in system zone - "
1402 "blocks from "E2FSBLK", length %lu",
1403 ret_block, num);
1404
1405
1406
1407
1408
1409 goto retry_alloc;
1410 }
1411
1412 performed_allocation = 1;
1413
1414 if (ret_block + num - 1 >= le32_to_cpu(es->s_blocks_count)) {
1415 ext2_error(sb, "ext2_new_blocks",
1416 "block("E2FSBLK") >= blocks count(%d) - "
1417 "block_group = %d, es == %p ", ret_block,
1418 le32_to_cpu(es->s_blocks_count), group_no, es);
1419 goto out;
1420 }
1421
1422 group_adjust_blocks(sb, group_no, gdp, gdp_bh, -num);
1423 percpu_counter_sub(&sbi->s_freeblocks_counter, num);
1424
1425 mark_buffer_dirty(bitmap_bh);
1426 if (sb->s_flags & SB_SYNCHRONOUS)
1427 sync_dirty_buffer(bitmap_bh);
1428
1429 *errp = 0;
1430 brelse(bitmap_bh);
1431 if (num < *count) {
1432 dquot_free_block_nodirty(inode, *count-num);
1433 mark_inode_dirty(inode);
1434 *count = num;
1435 }
1436 return ret_block;
1437
1438io_error:
1439 *errp = -EIO;
1440out:
1441
1442
1443
1444 if (!performed_allocation) {
1445 dquot_free_block_nodirty(inode, *count);
1446 mark_inode_dirty(inode);
1447 }
1448 brelse(bitmap_bh);
1449 return 0;
1450}
1451
1452ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp)
1453{
1454 unsigned long count = 1;
1455
1456 return ext2_new_blocks(inode, goal, &count, errp);
1457}
1458
1459#ifdef EXT2FS_DEBUG
1460
1461unsigned long ext2_count_free(struct buffer_head *map, unsigned int numchars)
1462{
1463 return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars);
1464}
1465
1466#endif
1467
1468unsigned long ext2_count_free_blocks (struct super_block * sb)
1469{
1470 struct ext2_group_desc * desc;
1471 unsigned long desc_count = 0;
1472 int i;
1473#ifdef EXT2FS_DEBUG
1474 unsigned long bitmap_count, x;
1475 struct ext2_super_block *es;
1476
1477 es = EXT2_SB(sb)->s_es;
1478 desc_count = 0;
1479 bitmap_count = 0;
1480 desc = NULL;
1481 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
1482 struct buffer_head *bitmap_bh;
1483 desc = ext2_get_group_desc (sb, i, NULL);
1484 if (!desc)
1485 continue;
1486 desc_count += le16_to_cpu(desc->bg_free_blocks_count);
1487 bitmap_bh = read_block_bitmap(sb, i);
1488 if (!bitmap_bh)
1489 continue;
1490
1491 x = ext2_count_free(bitmap_bh, sb->s_blocksize);
1492 printk ("group %d: stored = %d, counted = %lu\n",
1493 i, le16_to_cpu(desc->bg_free_blocks_count), x);
1494 bitmap_count += x;
1495 brelse(bitmap_bh);
1496 }
1497 printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n",
1498 (long)le32_to_cpu(es->s_free_blocks_count),
1499 desc_count, bitmap_count);
1500 return bitmap_count;
1501#else
1502 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
1503 desc = ext2_get_group_desc (sb, i, NULL);
1504 if (!desc)
1505 continue;
1506 desc_count += le16_to_cpu(desc->bg_free_blocks_count);
1507 }
1508 return desc_count;
1509#endif
1510}
1511
1512static inline int test_root(int a, int b)
1513{
1514 int num = b;
1515
1516 while (a > num)
1517 num *= b;
1518 return num == a;
1519}
1520
1521static int ext2_group_sparse(int group)
1522{
1523 if (group <= 1)
1524 return 1;
1525 return (test_root(group, 3) || test_root(group, 5) ||
1526 test_root(group, 7));
1527}
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537int ext2_bg_has_super(struct super_block *sb, int group)
1538{
1539 if (EXT2_HAS_RO_COMPAT_FEATURE(sb,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
1540 !ext2_group_sparse(group))
1541 return 0;
1542 return 1;
1543}
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554unsigned long ext2_bg_num_gdb(struct super_block *sb, int group)
1555{
1556 return ext2_bg_has_super(sb, group) ? EXT2_SB(sb)->s_gdb_count : 0;
1557}
1558
1559