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