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