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/slab.h>
17#include <linux/sched.h>
18#include <linux/buffer_head.h>
19#include <linux/capability.h>
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
38
39struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb,
40 unsigned int block_group,
41 struct buffer_head ** bh)
42{
43 unsigned long group_desc;
44 unsigned long offset;
45 struct ext2_group_desc * desc;
46 struct ext2_sb_info *sbi = EXT2_SB(sb);
47
48 if (block_group >= sbi->s_groups_count) {
49 ext2_error (sb, "ext2_get_group_desc",
50 "block_group >= groups_count - "
51 "block_group = %d, groups_count = %lu",
52 block_group, sbi->s_groups_count);
53
54 return NULL;
55 }
56
57 group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb);
58 offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1);
59 if (!sbi->s_group_desc[group_desc]) {
60 ext2_error (sb, "ext2_get_group_desc",
61 "Group descriptor not loaded - "
62 "block_group = %d, group_desc = %lu, desc = %lu",
63 block_group, group_desc, offset);
64 return NULL;
65 }
66
67 desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data;
68 if (bh)
69 *bh = sbi->s_group_desc[group_desc];
70 return desc + offset;
71}
72
73static int ext2_valid_block_bitmap(struct super_block *sb,
74 struct ext2_group_desc *desc,
75 unsigned int block_group,
76 struct buffer_head *bh)
77{
78 ext2_grpblk_t offset;
79 ext2_grpblk_t next_zero_bit;
80 ext2_fsblk_t bitmap_blk;
81 ext2_fsblk_t group_first_block;
82
83 group_first_block = ext2_group_first_block_no(sb, block_group);
84
85
86 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
87 offset = bitmap_blk - group_first_block;
88 if (!ext2_test_bit(offset, bh->b_data))
89
90 goto err_out;
91
92
93 bitmap_blk = le32_to_cpu(desc->bg_inode_bitmap);
94 offset = bitmap_blk - group_first_block;
95 if (!ext2_test_bit(offset, bh->b_data))
96
97 goto err_out;
98
99
100 bitmap_blk = le32_to_cpu(desc->bg_inode_table);
101 offset = bitmap_blk - group_first_block;
102 next_zero_bit = ext2_find_next_zero_bit(bh->b_data,
103 offset + EXT2_SB(sb)->s_itb_per_group,
104 offset);
105 if (next_zero_bit >= offset + EXT2_SB(sb)->s_itb_per_group)
106
107 return 1;
108
109err_out:
110 ext2_error(sb, __func__,
111 "Invalid block bitmap - "
112 "block_group = %d, block = %lu",
113 block_group, bitmap_blk);
114 return 0;
115}
116
117
118
119
120
121
122
123static struct buffer_head *
124read_block_bitmap(struct super_block *sb, unsigned int block_group)
125{
126 struct ext2_group_desc * desc;
127 struct buffer_head * bh = NULL;
128 ext2_fsblk_t bitmap_blk;
129
130 desc = ext2_get_group_desc(sb, block_group, NULL);
131 if (!desc)
132 return NULL;
133 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
134 bh = sb_getblk(sb, bitmap_blk);
135 if (unlikely(!bh)) {
136 ext2_error(sb, __func__,
137 "Cannot read block bitmap - "
138 "block_group = %d, block_bitmap = %u",
139 block_group, le32_to_cpu(desc->bg_block_bitmap));
140 return NULL;
141 }
142 if (likely(bh_uptodate_or_lock(bh)))
143 return bh;
144
145 if (bh_submit_read(bh) < 0) {
146 brelse(bh);
147 ext2_error(sb, __func__,
148 "Cannot read block bitmap - "
149 "block_group = %d, block_bitmap = %u",
150 block_group, le32_to_cpu(desc->bg_block_bitmap));
151 return NULL;
152 }
153
154 ext2_valid_block_bitmap(sb, desc, block_group, bh);
155
156
157
158
159 return bh;
160}
161
162static void release_blocks(struct super_block *sb, int count)
163{
164 if (count) {
165 struct ext2_sb_info *sbi = EXT2_SB(sb);
166
167 percpu_counter_add(&sbi->s_freeblocks_counter, count);
168 sb->s_dirt = 1;
169 }
170}
171
172static void group_adjust_blocks(struct super_block *sb, int group_no,
173 struct ext2_group_desc *desc, struct buffer_head *bh, int count)
174{
175 if (count) {
176 struct ext2_sb_info *sbi = EXT2_SB(sb);
177 unsigned free_blocks;
178
179 spin_lock(sb_bgl_lock(sbi, group_no));
180 free_blocks = le16_to_cpu(desc->bg_free_blocks_count);
181 desc->bg_free_blocks_count = cpu_to_le16(free_blocks + count);
182 spin_unlock(sb_bgl_lock(sbi, group_no));
183 sb->s_dirt = 1;
184 mark_buffer_dirty(bh);
185 }
186}
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209#if 1
210static void __rsv_window_dump(struct rb_root *root, int verbose,
211 const char *fn)
212{
213 struct rb_node *n;
214 struct ext2_reserve_window_node *rsv, *prev;
215 int bad;
216
217restart:
218 n = rb_first(root);
219 bad = 0;
220 prev = NULL;
221
222 printk("Block Allocation Reservation Windows Map (%s):\n", fn);
223 while (n) {
224 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
225 if (verbose)
226 printk("reservation window 0x%p "
227 "start: %lu, end: %lu\n",
228 rsv, rsv->rsv_start, rsv->rsv_end);
229 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
230 printk("Bad reservation %p (start >= end)\n",
231 rsv);
232 bad = 1;
233 }
234 if (prev && prev->rsv_end >= rsv->rsv_start) {
235 printk("Bad reservation %p (prev->end >= start)\n",
236 rsv);
237 bad = 1;
238 }
239 if (bad) {
240 if (!verbose) {
241 printk("Restarting reservation walk in verbose mode\n");
242 verbose = 1;
243 goto restart;
244 }
245 }
246 n = rb_next(n);
247 prev = rsv;
248 }
249 printk("Window map complete.\n");
250 BUG_ON(bad);
251}
252#define rsv_window_dump(root, verbose) \
253 __rsv_window_dump((root), (verbose), __func__)
254#else
255#define rsv_window_dump(root, verbose) do {} while (0)
256#endif
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274static int
275goal_in_my_reservation(struct ext2_reserve_window *rsv, ext2_grpblk_t grp_goal,
276 unsigned int group, struct super_block * sb)
277{
278 ext2_fsblk_t group_first_block, group_last_block;
279
280 group_first_block = ext2_group_first_block_no(sb, group);
281 group_last_block = group_first_block + EXT2_BLOCKS_PER_GROUP(sb) - 1;
282
283 if ((rsv->_rsv_start > group_last_block) ||
284 (rsv->_rsv_end < group_first_block))
285 return 0;
286 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
287 || (grp_goal + group_first_block > rsv->_rsv_end)))
288 return 0;
289 return 1;
290}
291
292
293
294
295
296
297
298
299
300
301static struct ext2_reserve_window_node *
302search_reserve_window(struct rb_root *root, ext2_fsblk_t goal)
303{
304 struct rb_node *n = root->rb_node;
305 struct ext2_reserve_window_node *rsv;
306
307 if (!n)
308 return NULL;
309
310 do {
311 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
312
313 if (goal < rsv->rsv_start)
314 n = n->rb_left;
315 else if (goal > rsv->rsv_end)
316 n = n->rb_right;
317 else
318 return rsv;
319 } while (n);
320
321
322
323
324
325
326 if (rsv->rsv_start > goal) {
327 n = rb_prev(&rsv->rsv_node);
328 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
329 }
330 return rsv;
331}
332
333
334
335
336
337
338
339
340void ext2_rsv_window_add(struct super_block *sb,
341 struct ext2_reserve_window_node *rsv)
342{
343 struct rb_root *root = &EXT2_SB(sb)->s_rsv_window_root;
344 struct rb_node *node = &rsv->rsv_node;
345 ext2_fsblk_t start = rsv->rsv_start;
346
347 struct rb_node ** p = &root->rb_node;
348 struct rb_node * parent = NULL;
349 struct ext2_reserve_window_node *this;
350
351 while (*p)
352 {
353 parent = *p;
354 this = rb_entry(parent, struct ext2_reserve_window_node, rsv_node);
355
356 if (start < this->rsv_start)
357 p = &(*p)->rb_left;
358 else if (start > this->rsv_end)
359 p = &(*p)->rb_right;
360 else {
361 rsv_window_dump(root, 1);
362 BUG();
363 }
364 }
365
366 rb_link_node(node, parent, p);
367 rb_insert_color(node, root);
368}
369
370
371
372
373
374
375
376
377
378
379static void rsv_window_remove(struct super_block *sb,
380 struct ext2_reserve_window_node *rsv)
381{
382 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
383 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
384 rsv->rsv_alloc_hit = 0;
385 rb_erase(&rsv->rsv_node, &EXT2_SB(sb)->s_rsv_window_root);
386}
387
388
389
390
391
392
393
394static inline int rsv_is_empty(struct ext2_reserve_window *rsv)
395{
396
397 return (rsv->_rsv_end == EXT2_RESERVE_WINDOW_NOT_ALLOCATED);
398}
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421void ext2_init_block_alloc_info(struct inode *inode)
422{
423 struct ext2_inode_info *ei = EXT2_I(inode);
424 struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info;
425 struct super_block *sb = inode->i_sb;
426
427 block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
428 if (block_i) {
429 struct ext2_reserve_window_node *rsv = &block_i->rsv_window_node;
430
431 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
432 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
433
434
435
436
437
438
439 if (!test_opt(sb, RESERVATION))
440 rsv->rsv_goal_size = 0;
441 else
442 rsv->rsv_goal_size = EXT2_DEFAULT_RESERVE_BLOCKS;
443 rsv->rsv_alloc_hit = 0;
444 block_i->last_alloc_logical_block = 0;
445 block_i->last_alloc_physical_block = 0;
446 }
447 ei->i_block_alloc_info = block_i;
448}
449
450
451
452
453
454
455
456
457
458
459
460
461
462void ext2_discard_reservation(struct inode *inode)
463{
464 struct ext2_inode_info *ei = EXT2_I(inode);
465 struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info;
466 struct ext2_reserve_window_node *rsv;
467 spinlock_t *rsv_lock = &EXT2_SB(inode->i_sb)->s_rsv_window_lock;
468
469 if (!block_i)
470 return;
471
472 rsv = &block_i->rsv_window_node;
473 if (!rsv_is_empty(&rsv->rsv_window)) {
474 spin_lock(rsv_lock);
475 if (!rsv_is_empty(&rsv->rsv_window))
476 rsv_window_remove(inode->i_sb, rsv);
477 spin_unlock(rsv_lock);
478 }
479}
480
481
482
483
484
485
486
487void ext2_free_blocks (struct inode * inode, unsigned long block,
488 unsigned long count)
489{
490 struct buffer_head *bitmap_bh = NULL;
491 struct buffer_head * bh2;
492 unsigned long block_group;
493 unsigned long bit;
494 unsigned long i;
495 unsigned long overflow;
496 struct super_block * sb = inode->i_sb;
497 struct ext2_sb_info * sbi = EXT2_SB(sb);
498 struct ext2_group_desc * desc;
499 struct ext2_super_block * es = sbi->s_es;
500 unsigned freed = 0, group_freed;
501
502 if (block < le32_to_cpu(es->s_first_data_block) ||
503 block + count < block ||
504 block + count > le32_to_cpu(es->s_blocks_count)) {
505 ext2_error (sb, "ext2_free_blocks",
506 "Freeing blocks not in datazone - "
507 "block = %lu, count = %lu", block, count);
508 goto error_return;
509 }
510
511 ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
512
513do_more:
514 overflow = 0;
515 block_group = (block - le32_to_cpu(es->s_first_data_block)) /
516 EXT2_BLOCKS_PER_GROUP(sb);
517 bit = (block - le32_to_cpu(es->s_first_data_block)) %
518 EXT2_BLOCKS_PER_GROUP(sb);
519
520
521
522
523 if (bit + count > EXT2_BLOCKS_PER_GROUP(sb)) {
524 overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb);
525 count -= overflow;
526 }
527 brelse(bitmap_bh);
528 bitmap_bh = read_block_bitmap(sb, block_group);
529 if (!bitmap_bh)
530 goto error_return;
531
532 desc = ext2_get_group_desc (sb, block_group, &bh2);
533 if (!desc)
534 goto error_return;
535
536 if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
537 in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
538 in_range (block, le32_to_cpu(desc->bg_inode_table),
539 sbi->s_itb_per_group) ||
540 in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
541 sbi->s_itb_per_group)) {
542 ext2_error (sb, "ext2_free_blocks",
543 "Freeing blocks in system zones - "
544 "Block = %lu, count = %lu",
545 block, count);
546 goto error_return;
547 }
548
549 for (i = 0, group_freed = 0; i < count; i++) {
550 if (!ext2_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
551 bit + i, bitmap_bh->b_data)) {
552 ext2_error(sb, __func__,
553 "bit already cleared for block %lu", block + i);
554 } else {
555 group_freed++;
556 }
557 }
558
559 mark_buffer_dirty(bitmap_bh);
560 if (sb->s_flags & MS_SYNCHRONOUS)
561 sync_dirty_buffer(bitmap_bh);
562
563 group_adjust_blocks(sb, block_group, desc, bh2, group_freed);
564 freed += group_freed;
565
566 if (overflow) {
567 block += count;
568 count = overflow;
569 goto do_more;
570 }
571error_return:
572 brelse(bitmap_bh);
573 release_blocks(sb, freed);
574 dquot_free_block_nodirty(inode, freed);
575}
576
577
578
579
580
581
582
583
584
585
586static ext2_grpblk_t
587bitmap_search_next_usable_block(ext2_grpblk_t start, struct buffer_head *bh,
588 ext2_grpblk_t maxblocks)
589{
590 ext2_grpblk_t next;
591
592 next = ext2_find_next_zero_bit(bh->b_data, maxblocks, start);
593 if (next >= maxblocks)
594 return -1;
595 return next;
596}
597
598
599
600
601
602
603
604
605
606
607
608
609
610static ext2_grpblk_t
611find_next_usable_block(int start, struct buffer_head *bh, int maxblocks)
612{
613 ext2_grpblk_t here, next;
614 char *p, *r;
615
616 if (start > 0) {
617
618
619
620
621
622
623
624
625 ext2_grpblk_t end_goal = (start + 63) & ~63;
626 if (end_goal > maxblocks)
627 end_goal = maxblocks;
628 here = ext2_find_next_zero_bit(bh->b_data, end_goal, start);
629 if (here < end_goal)
630 return here;
631 ext2_debug("Bit not found near goal\n");
632 }
633
634 here = start;
635 if (here < 0)
636 here = 0;
637
638 p = ((char *)bh->b_data) + (here >> 3);
639 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
640 next = (r - ((char *)bh->b_data)) << 3;
641
642 if (next < maxblocks && next >= here)
643 return next;
644
645 here = bitmap_search_next_usable_block(here, bh, maxblocks);
646 return here;
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 int ret;
1240
1241 *errp = -ENOSPC;
1242 sb = inode->i_sb;
1243 if (!sb) {
1244 printk("ext2_new_blocks: nonexistent device");
1245 return 0;
1246 }
1247
1248
1249
1250
1251 ret = dquot_alloc_block(inode, num);
1252 if (ret) {
1253 *errp = ret;
1254 return 0;
1255 }
1256
1257 sbi = EXT2_SB(sb);
1258 es = EXT2_SB(sb)->s_es;
1259 ext2_debug("goal=%lu.\n", goal);
1260
1261
1262
1263
1264
1265
1266
1267
1268 block_i = EXT2_I(inode)->i_block_alloc_info;
1269 if (block_i) {
1270 windowsz = block_i->rsv_window_node.rsv_goal_size;
1271 if (windowsz > 0)
1272 my_rsv = &block_i->rsv_window_node;
1273 }
1274
1275 if (!ext2_has_free_blocks(sbi)) {
1276 *errp = -ENOSPC;
1277 goto out;
1278 }
1279
1280
1281
1282
1283 if (goal < le32_to_cpu(es->s_first_data_block) ||
1284 goal >= le32_to_cpu(es->s_blocks_count))
1285 goal = le32_to_cpu(es->s_first_data_block);
1286 group_no = (goal - le32_to_cpu(es->s_first_data_block)) /
1287 EXT2_BLOCKS_PER_GROUP(sb);
1288 goal_group = group_no;
1289retry_alloc:
1290 gdp = ext2_get_group_desc(sb, group_no, &gdp_bh);
1291 if (!gdp)
1292 goto io_error;
1293
1294 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1295
1296
1297
1298
1299 if (my_rsv && (free_blocks < windowsz)
1300 && (free_blocks > 0)
1301 && (rsv_is_empty(&my_rsv->rsv_window)))
1302 my_rsv = NULL;
1303
1304 if (free_blocks > 0) {
1305 grp_target_blk = ((goal - le32_to_cpu(es->s_first_data_block)) %
1306 EXT2_BLOCKS_PER_GROUP(sb));
1307 bitmap_bh = read_block_bitmap(sb, group_no);
1308 if (!bitmap_bh)
1309 goto io_error;
1310 grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no,
1311 bitmap_bh, grp_target_blk,
1312 my_rsv, &num);
1313 if (grp_alloc_blk >= 0)
1314 goto allocated;
1315 }
1316
1317 ngroups = EXT2_SB(sb)->s_groups_count;
1318 smp_rmb();
1319
1320
1321
1322
1323
1324 for (bgi = 0; bgi < ngroups; bgi++) {
1325 group_no++;
1326 if (group_no >= ngroups)
1327 group_no = 0;
1328 gdp = ext2_get_group_desc(sb, group_no, &gdp_bh);
1329 if (!gdp)
1330 goto io_error;
1331
1332 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1333
1334
1335
1336
1337 if (!free_blocks)
1338 continue;
1339
1340
1341
1342
1343
1344 if (my_rsv && (free_blocks <= (windowsz/2)))
1345 continue;
1346
1347 brelse(bitmap_bh);
1348 bitmap_bh = read_block_bitmap(sb, group_no);
1349 if (!bitmap_bh)
1350 goto io_error;
1351
1352
1353
1354 grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no,
1355 bitmap_bh, -1, my_rsv, &num);
1356 if (grp_alloc_blk >= 0)
1357 goto allocated;
1358 }
1359
1360
1361
1362
1363
1364
1365
1366 if (my_rsv) {
1367 my_rsv = NULL;
1368 windowsz = 0;
1369 group_no = goal_group;
1370 goto retry_alloc;
1371 }
1372
1373 *errp = -ENOSPC;
1374 goto out;
1375
1376allocated:
1377
1378 ext2_debug("using block group %d(%d)\n",
1379 group_no, gdp->bg_free_blocks_count);
1380
1381 ret_block = grp_alloc_blk + ext2_group_first_block_no(sb, group_no);
1382
1383 if (in_range(le32_to_cpu(gdp->bg_block_bitmap), ret_block, num) ||
1384 in_range(le32_to_cpu(gdp->bg_inode_bitmap), ret_block, num) ||
1385 in_range(ret_block, le32_to_cpu(gdp->bg_inode_table),
1386 EXT2_SB(sb)->s_itb_per_group) ||
1387 in_range(ret_block + num - 1, le32_to_cpu(gdp->bg_inode_table),
1388 EXT2_SB(sb)->s_itb_per_group)) {
1389 ext2_error(sb, "ext2_new_blocks",
1390 "Allocating block in system zone - "
1391 "blocks from "E2FSBLK", length %lu",
1392 ret_block, num);
1393
1394
1395
1396
1397
1398 goto retry_alloc;
1399 }
1400
1401 performed_allocation = 1;
1402
1403 if (ret_block + num - 1 >= le32_to_cpu(es->s_blocks_count)) {
1404 ext2_error(sb, "ext2_new_blocks",
1405 "block("E2FSBLK") >= blocks count(%d) - "
1406 "block_group = %d, es == %p ", ret_block,
1407 le32_to_cpu(es->s_blocks_count), group_no, es);
1408 goto out;
1409 }
1410
1411 group_adjust_blocks(sb, group_no, gdp, gdp_bh, -num);
1412 percpu_counter_sub(&sbi->s_freeblocks_counter, num);
1413
1414 mark_buffer_dirty(bitmap_bh);
1415 if (sb->s_flags & MS_SYNCHRONOUS)
1416 sync_dirty_buffer(bitmap_bh);
1417
1418 *errp = 0;
1419 brelse(bitmap_bh);
1420 dquot_free_block_nodirty(inode, *count-num);
1421 mark_inode_dirty(inode);
1422 *count = num;
1423 return ret_block;
1424
1425io_error:
1426 *errp = -EIO;
1427out:
1428
1429
1430
1431 if (!performed_allocation) {
1432 dquot_free_block_nodirty(inode, *count);
1433 mark_inode_dirty(inode);
1434 }
1435 brelse(bitmap_bh);
1436 return 0;
1437}
1438
1439ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp)
1440{
1441 unsigned long count = 1;
1442
1443 return ext2_new_blocks(inode, goal, &count, errp);
1444}
1445
1446#ifdef EXT2FS_DEBUG
1447
1448static const int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
1449
1450unsigned long ext2_count_free (struct buffer_head * map, unsigned int numchars)
1451{
1452 unsigned int i;
1453 unsigned long sum = 0;
1454
1455 if (!map)
1456 return (0);
1457 for (i = 0; i < numchars; i++)
1458 sum += nibblemap[map->b_data[i] & 0xf] +
1459 nibblemap[(map->b_data[i] >> 4) & 0xf];
1460 return (sum);
1461}
1462
1463#endif
1464
1465unsigned long ext2_count_free_blocks (struct super_block * sb)
1466{
1467 struct ext2_group_desc * desc;
1468 unsigned long desc_count = 0;
1469 int i;
1470#ifdef EXT2FS_DEBUG
1471 unsigned long bitmap_count, x;
1472 struct ext2_super_block *es;
1473
1474 es = EXT2_SB(sb)->s_es;
1475 desc_count = 0;
1476 bitmap_count = 0;
1477 desc = NULL;
1478 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
1479 struct buffer_head *bitmap_bh;
1480 desc = ext2_get_group_desc (sb, i, NULL);
1481 if (!desc)
1482 continue;
1483 desc_count += le16_to_cpu(desc->bg_free_blocks_count);
1484 bitmap_bh = read_block_bitmap(sb, i);
1485 if (!bitmap_bh)
1486 continue;
1487
1488 x = ext2_count_free(bitmap_bh, sb->s_blocksize);
1489 printk ("group %d: stored = %d, counted = %lu\n",
1490 i, le16_to_cpu(desc->bg_free_blocks_count), x);
1491 bitmap_count += x;
1492 brelse(bitmap_bh);
1493 }
1494 printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n",
1495 (long)le32_to_cpu(es->s_free_blocks_count),
1496 desc_count, bitmap_count);
1497 return bitmap_count;
1498#else
1499 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
1500 desc = ext2_get_group_desc (sb, i, NULL);
1501 if (!desc)
1502 continue;
1503 desc_count += le16_to_cpu(desc->bg_free_blocks_count);
1504 }
1505 return desc_count;
1506#endif
1507}
1508
1509static inline int test_root(int a, int b)
1510{
1511 int num = b;
1512
1513 while (a > num)
1514 num *= b;
1515 return num == a;
1516}
1517
1518static int ext2_group_sparse(int group)
1519{
1520 if (group <= 1)
1521 return 1;
1522 return (test_root(group, 3) || test_root(group, 5) ||
1523 test_root(group, 7));
1524}
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534int ext2_bg_has_super(struct super_block *sb, int group)
1535{
1536 if (EXT2_HAS_RO_COMPAT_FEATURE(sb,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
1537 !ext2_group_sparse(group))
1538 return 0;
1539 return 1;
1540}
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551unsigned long ext2_bg_num_gdb(struct super_block *sb, int group)
1552{
1553 return ext2_bg_has_super(sb, group) ? EXT2_SB(sb)->s_gdb_count : 0;
1554}
1555
1556