Merge branch 'master' of /usr/src/ntfs-2.6/
[linux-2.6] / fs / ext3 / balloc.c
1 /*
2  *  linux/fs/ext3/balloc.c
3  *
4  * Copyright (C) 1992, 1993, 1994, 1995
5  * Remy Card (card@masi.ibp.fr)
6  * Laboratoire MASI - Institut Blaise Pascal
7  * Universite Pierre et Marie Curie (Paris VI)
8  *
9  *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
10  *  Big-endian to little-endian byte-swapping/bitmaps by
11  *        David S. Miller (davem@caip.rutgers.edu), 1995
12  */
13
14 #include <linux/config.h>
15 #include <linux/time.h>
16 #include <linux/fs.h>
17 #include <linux/jbd.h>
18 #include <linux/ext3_fs.h>
19 #include <linux/ext3_jbd.h>
20 #include <linux/quotaops.h>
21 #include <linux/buffer_head.h>
22
23 #include "bitmap.h"
24
25 /*
26  * balloc.c contains the blocks allocation and deallocation routines
27  */
28
29 /*
30  * The free blocks are managed by bitmaps.  A file system contains several
31  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
32  * block for inodes, N blocks for the inode table and data blocks.
33  *
34  * The file system contains group descriptors which are located after the
35  * super block.  Each descriptor contains the number of the bitmap block and
36  * the free blocks count in the block.  The descriptors are loaded in memory
37  * when a file system is mounted (see ext3_read_super).
38  */
39
40
41 #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
42
43 struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
44                                              unsigned int block_group,
45                                              struct buffer_head ** bh)
46 {
47         unsigned long group_desc;
48         unsigned long offset;
49         struct ext3_group_desc * desc;
50         struct ext3_sb_info *sbi = EXT3_SB(sb);
51
52         if (block_group >= sbi->s_groups_count) {
53                 ext3_error (sb, "ext3_get_group_desc",
54                             "block_group >= groups_count - "
55                             "block_group = %d, groups_count = %lu",
56                             block_group, sbi->s_groups_count);
57
58                 return NULL;
59         }
60         smp_rmb();
61
62         group_desc = block_group >> EXT3_DESC_PER_BLOCK_BITS(sb);
63         offset = block_group & (EXT3_DESC_PER_BLOCK(sb) - 1);
64         if (!sbi->s_group_desc[group_desc]) {
65                 ext3_error (sb, "ext3_get_group_desc",
66                             "Group descriptor not loaded - "
67                             "block_group = %d, group_desc = %lu, desc = %lu",
68                              block_group, group_desc, offset);
69                 return NULL;
70         }
71
72         desc = (struct ext3_group_desc *) sbi->s_group_desc[group_desc]->b_data;
73         if (bh)
74                 *bh = sbi->s_group_desc[group_desc];
75         return desc + offset;
76 }
77
78 /*
79  * Read the bitmap for a given block_group, reading into the specified 
80  * slot in the superblock's bitmap cache.
81  *
82  * Return buffer_head on success or NULL in case of failure.
83  */
84 static struct buffer_head *
85 read_block_bitmap(struct super_block *sb, unsigned int block_group)
86 {
87         struct ext3_group_desc * desc;
88         struct buffer_head * bh = NULL;
89
90         desc = ext3_get_group_desc (sb, block_group, NULL);
91         if (!desc)
92                 goto error_out;
93         bh = sb_bread(sb, le32_to_cpu(desc->bg_block_bitmap));
94         if (!bh)
95                 ext3_error (sb, "read_block_bitmap",
96                             "Cannot read block bitmap - "
97                             "block_group = %d, block_bitmap = %u",
98                             block_group, le32_to_cpu(desc->bg_block_bitmap));
99 error_out:
100         return bh;
101 }
102 /*
103  * The reservation window structure operations
104  * --------------------------------------------
105  * Operations include:
106  * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
107  *
108  * We use sorted double linked list for the per-filesystem reservation
109  * window list. (like in vm_region).
110  *
111  * Initially, we keep those small operations in the abstract functions,
112  * so later if we need a better searching tree than double linked-list,
113  * we could easily switch to that without changing too much
114  * code.
115  */
116 #if 0
117 static void __rsv_window_dump(struct rb_root *root, int verbose,
118                               const char *fn)
119 {
120         struct rb_node *n;
121         struct ext3_reserve_window_node *rsv, *prev;
122         int bad;
123
124 restart:
125         n = rb_first(root);
126         bad = 0;
127         prev = NULL;
128
129         printk("Block Allocation Reservation Windows Map (%s):\n", fn);
130         while (n) {
131                 rsv = list_entry(n, struct ext3_reserve_window_node, rsv_node);
132                 if (verbose)
133                         printk("reservation window 0x%p "
134                                "start:  %d, end:  %d\n",
135                                rsv, rsv->rsv_start, rsv->rsv_end);
136                 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
137                         printk("Bad reservation %p (start >= end)\n",
138                                rsv);
139                         bad = 1;
140                 }
141                 if (prev && prev->rsv_end >= rsv->rsv_start) {
142                         printk("Bad reservation %p (prev->end >= start)\n",
143                                rsv);
144                         bad = 1;
145                 }
146                 if (bad) {
147                         if (!verbose) {
148                                 printk("Restarting reservation walk in verbose mode\n");
149                                 verbose = 1;
150                                 goto restart;
151                         }
152                 }
153                 n = rb_next(n);
154                 prev = rsv;
155         }
156         printk("Window map complete.\n");
157         if (bad)
158                 BUG();
159 }
160 #define rsv_window_dump(root, verbose) \
161         __rsv_window_dump((root), (verbose), __FUNCTION__)
162 #else
163 #define rsv_window_dump(root, verbose) do {} while (0)
164 #endif
165
166 static int
167 goal_in_my_reservation(struct ext3_reserve_window *rsv, int goal,
168                         unsigned int group, struct super_block * sb)
169 {
170         unsigned long group_first_block, group_last_block;
171
172         group_first_block = le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block) +
173                                 group * EXT3_BLOCKS_PER_GROUP(sb);
174         group_last_block = group_first_block + EXT3_BLOCKS_PER_GROUP(sb) - 1;
175
176         if ((rsv->_rsv_start > group_last_block) ||
177             (rsv->_rsv_end < group_first_block))
178                 return 0;
179         if ((goal >= 0) && ((goal + group_first_block < rsv->_rsv_start)
180                 || (goal + group_first_block > rsv->_rsv_end)))
181                 return 0;
182         return 1;
183 }
184
185 /*
186  * Find the reserved window which includes the goal, or the previous one
187  * if the goal is not in any window.
188  * Returns NULL if there are no windows or if all windows start after the goal.
189  */
190 static struct ext3_reserve_window_node *
191 search_reserve_window(struct rb_root *root, unsigned long goal)
192 {
193         struct rb_node *n = root->rb_node;
194         struct ext3_reserve_window_node *rsv;
195
196         if (!n)
197                 return NULL;
198
199         do {
200                 rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
201
202                 if (goal < rsv->rsv_start)
203                         n = n->rb_left;
204                 else if (goal > rsv->rsv_end)
205                         n = n->rb_right;
206                 else
207                         return rsv;
208         } while (n);
209         /*
210          * We've fallen off the end of the tree: the goal wasn't inside
211          * any particular node.  OK, the previous node must be to one
212          * side of the interval containing the goal.  If it's the RHS,
213          * we need to back up one.
214          */
215         if (rsv->rsv_start > goal) {
216                 n = rb_prev(&rsv->rsv_node);
217                 rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
218         }
219         return rsv;
220 }
221
222 void ext3_rsv_window_add(struct super_block *sb,
223                     struct ext3_reserve_window_node *rsv)
224 {
225         struct rb_root *root = &EXT3_SB(sb)->s_rsv_window_root;
226         struct rb_node *node = &rsv->rsv_node;
227         unsigned int start = rsv->rsv_start;
228
229         struct rb_node ** p = &root->rb_node;
230         struct rb_node * parent = NULL;
231         struct ext3_reserve_window_node *this;
232
233         while (*p)
234         {
235                 parent = *p;
236                 this = rb_entry(parent, struct ext3_reserve_window_node, rsv_node);
237
238                 if (start < this->rsv_start)
239                         p = &(*p)->rb_left;
240                 else if (start > this->rsv_end)
241                         p = &(*p)->rb_right;
242                 else
243                         BUG();
244         }
245
246         rb_link_node(node, parent, p);
247         rb_insert_color(node, root);
248 }
249
250 static void rsv_window_remove(struct super_block *sb,
251                               struct ext3_reserve_window_node *rsv)
252 {
253         rsv->rsv_start = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
254         rsv->rsv_end = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
255         rsv->rsv_alloc_hit = 0;
256         rb_erase(&rsv->rsv_node, &EXT3_SB(sb)->s_rsv_window_root);
257 }
258
259 static inline int rsv_is_empty(struct ext3_reserve_window *rsv)
260 {
261         /* a valid reservation end block could not be 0 */
262         return (rsv->_rsv_end == EXT3_RESERVE_WINDOW_NOT_ALLOCATED);
263 }
264 void ext3_init_block_alloc_info(struct inode *inode)
265 {
266         struct ext3_inode_info *ei = EXT3_I(inode);
267         struct ext3_block_alloc_info *block_i = ei->i_block_alloc_info;
268         struct super_block *sb = inode->i_sb;
269
270         block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
271         if (block_i) {
272                 struct ext3_reserve_window_node *rsv = &block_i->rsv_window_node;
273
274                 rsv->rsv_start = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
275                 rsv->rsv_end = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
276
277                 /*
278                  * if filesystem is mounted with NORESERVATION, the goal
279                  * reservation window size is set to zero to indicate
280                  * block reservation is off
281                  */
282                 if (!test_opt(sb, RESERVATION))
283                         rsv->rsv_goal_size = 0;
284                 else
285                         rsv->rsv_goal_size = EXT3_DEFAULT_RESERVE_BLOCKS;
286                 rsv->rsv_alloc_hit = 0;
287                 block_i->last_alloc_logical_block = 0;
288                 block_i->last_alloc_physical_block = 0;
289         }
290         ei->i_block_alloc_info = block_i;
291 }
292
293 void ext3_discard_reservation(struct inode *inode)
294 {
295         struct ext3_inode_info *ei = EXT3_I(inode);
296         struct ext3_block_alloc_info *block_i = ei->i_block_alloc_info;
297         struct ext3_reserve_window_node *rsv;
298         spinlock_t *rsv_lock = &EXT3_SB(inode->i_sb)->s_rsv_window_lock;
299
300         if (!block_i)
301                 return;
302
303         rsv = &block_i->rsv_window_node;
304         if (!rsv_is_empty(&rsv->rsv_window)) {
305                 spin_lock(rsv_lock);
306                 if (!rsv_is_empty(&rsv->rsv_window))
307                         rsv_window_remove(inode->i_sb, rsv);
308                 spin_unlock(rsv_lock);
309         }
310 }
311
312 /* Free given blocks, update quota and i_blocks field */
313 void ext3_free_blocks_sb(handle_t *handle, struct super_block *sb,
314                          unsigned long block, unsigned long count,
315                          int *pdquot_freed_blocks)
316 {
317         struct buffer_head *bitmap_bh = NULL;
318         struct buffer_head *gd_bh;
319         unsigned long block_group;
320         unsigned long bit;
321         unsigned long i;
322         unsigned long overflow;
323         struct ext3_group_desc * desc;
324         struct ext3_super_block * es;
325         struct ext3_sb_info *sbi;
326         int err = 0, ret;
327         unsigned group_freed;
328
329         *pdquot_freed_blocks = 0;
330         sbi = EXT3_SB(sb);
331         es = sbi->s_es;
332         if (block < le32_to_cpu(es->s_first_data_block) ||
333             block + count < block ||
334             block + count > le32_to_cpu(es->s_blocks_count)) {
335                 ext3_error (sb, "ext3_free_blocks",
336                             "Freeing blocks not in datazone - "
337                             "block = %lu, count = %lu", block, count);
338                 goto error_return;
339         }
340
341         ext3_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
342
343 do_more:
344         overflow = 0;
345         block_group = (block - le32_to_cpu(es->s_first_data_block)) /
346                       EXT3_BLOCKS_PER_GROUP(sb);
347         bit = (block - le32_to_cpu(es->s_first_data_block)) %
348                       EXT3_BLOCKS_PER_GROUP(sb);
349         /*
350          * Check to see if we are freeing blocks across a group
351          * boundary.
352          */
353         if (bit + count > EXT3_BLOCKS_PER_GROUP(sb)) {
354                 overflow = bit + count - EXT3_BLOCKS_PER_GROUP(sb);
355                 count -= overflow;
356         }
357         brelse(bitmap_bh);
358         bitmap_bh = read_block_bitmap(sb, block_group);
359         if (!bitmap_bh)
360                 goto error_return;
361         desc = ext3_get_group_desc (sb, block_group, &gd_bh);
362         if (!desc)
363                 goto error_return;
364
365         if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
366             in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
367             in_range (block, le32_to_cpu(desc->bg_inode_table),
368                       sbi->s_itb_per_group) ||
369             in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
370                       sbi->s_itb_per_group))
371                 ext3_error (sb, "ext3_free_blocks",
372                             "Freeing blocks in system zones - "
373                             "Block = %lu, count = %lu",
374                             block, count);
375
376         /*
377          * We are about to start releasing blocks in the bitmap,
378          * so we need undo access.
379          */
380         /* @@@ check errors */
381         BUFFER_TRACE(bitmap_bh, "getting undo access");
382         err = ext3_journal_get_undo_access(handle, bitmap_bh);
383         if (err)
384                 goto error_return;
385
386         /*
387          * We are about to modify some metadata.  Call the journal APIs
388          * to unshare ->b_data if a currently-committing transaction is
389          * using it
390          */
391         BUFFER_TRACE(gd_bh, "get_write_access");
392         err = ext3_journal_get_write_access(handle, gd_bh);
393         if (err)
394                 goto error_return;
395
396         jbd_lock_bh_state(bitmap_bh);
397
398         for (i = 0, group_freed = 0; i < count; i++) {
399                 /*
400                  * An HJ special.  This is expensive...
401                  */
402 #ifdef CONFIG_JBD_DEBUG
403                 jbd_unlock_bh_state(bitmap_bh);
404                 {
405                         struct buffer_head *debug_bh;
406                         debug_bh = sb_find_get_block(sb, block + i);
407                         if (debug_bh) {
408                                 BUFFER_TRACE(debug_bh, "Deleted!");
409                                 if (!bh2jh(bitmap_bh)->b_committed_data)
410                                         BUFFER_TRACE(debug_bh,
411                                                 "No commited data in bitmap");
412                                 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
413                                 __brelse(debug_bh);
414                         }
415                 }
416                 jbd_lock_bh_state(bitmap_bh);
417 #endif
418                 if (need_resched()) {
419                         jbd_unlock_bh_state(bitmap_bh);
420                         cond_resched();
421                         jbd_lock_bh_state(bitmap_bh);
422                 }
423                 /* @@@ This prevents newly-allocated data from being
424                  * freed and then reallocated within the same
425                  * transaction. 
426                  * 
427                  * Ideally we would want to allow that to happen, but to
428                  * do so requires making journal_forget() capable of
429                  * revoking the queued write of a data block, which
430                  * implies blocking on the journal lock.  *forget()
431                  * cannot block due to truncate races.
432                  *
433                  * Eventually we can fix this by making journal_forget()
434                  * return a status indicating whether or not it was able
435                  * to revoke the buffer.  On successful revoke, it is
436                  * safe not to set the allocation bit in the committed
437                  * bitmap, because we know that there is no outstanding
438                  * activity on the buffer any more and so it is safe to
439                  * reallocate it.  
440                  */
441                 BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
442                 J_ASSERT_BH(bitmap_bh,
443                                 bh2jh(bitmap_bh)->b_committed_data != NULL);
444                 ext3_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
445                                 bh2jh(bitmap_bh)->b_committed_data);
446
447                 /*
448                  * We clear the bit in the bitmap after setting the committed
449                  * data bit, because this is the reverse order to that which
450                  * the allocator uses.
451                  */
452                 BUFFER_TRACE(bitmap_bh, "clear bit");
453                 if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
454                                                 bit + i, bitmap_bh->b_data)) {
455                         jbd_unlock_bh_state(bitmap_bh);
456                         ext3_error(sb, __FUNCTION__,
457                                 "bit already cleared for block %lu", block + i);
458                         jbd_lock_bh_state(bitmap_bh);
459                         BUFFER_TRACE(bitmap_bh, "bit already cleared");
460                 } else {
461                         group_freed++;
462                 }
463         }
464         jbd_unlock_bh_state(bitmap_bh);
465
466         spin_lock(sb_bgl_lock(sbi, block_group));
467         desc->bg_free_blocks_count =
468                 cpu_to_le16(le16_to_cpu(desc->bg_free_blocks_count) +
469                         group_freed);
470         spin_unlock(sb_bgl_lock(sbi, block_group));
471         percpu_counter_mod(&sbi->s_freeblocks_counter, count);
472
473         /* We dirtied the bitmap block */
474         BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
475         err = ext3_journal_dirty_metadata(handle, bitmap_bh);
476
477         /* And the group descriptor block */
478         BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
479         ret = ext3_journal_dirty_metadata(handle, gd_bh);
480         if (!err) err = ret;
481         *pdquot_freed_blocks += group_freed;
482
483         if (overflow && !err) {
484                 block += count;
485                 count = overflow;
486                 goto do_more;
487         }
488         sb->s_dirt = 1;
489 error_return:
490         brelse(bitmap_bh);
491         ext3_std_error(sb, err);
492         return;
493 }
494
495 /* Free given blocks, update quota and i_blocks field */
496 void ext3_free_blocks(handle_t *handle, struct inode *inode,
497                         unsigned long block, unsigned long count)
498 {
499         struct super_block * sb;
500         int dquot_freed_blocks;
501
502         sb = inode->i_sb;
503         if (!sb) {
504                 printk ("ext3_free_blocks: nonexistent device");
505                 return;
506         }
507         ext3_free_blocks_sb(handle, sb, block, count, &dquot_freed_blocks);
508         if (dquot_freed_blocks)
509                 DQUOT_FREE_BLOCK(inode, dquot_freed_blocks);
510         return;
511 }
512
513 /*
514  * For ext3 allocations, we must not reuse any blocks which are
515  * allocated in the bitmap buffer's "last committed data" copy.  This
516  * prevents deletes from freeing up the page for reuse until we have
517  * committed the delete transaction.
518  *
519  * If we didn't do this, then deleting something and reallocating it as
520  * data would allow the old block to be overwritten before the
521  * transaction committed (because we force data to disk before commit).
522  * This would lead to corruption if we crashed between overwriting the
523  * data and committing the delete. 
524  *
525  * @@@ We may want to make this allocation behaviour conditional on
526  * data-writes at some point, and disable it for metadata allocations or
527  * sync-data inodes.
528  */
529 static int ext3_test_allocatable(int nr, struct buffer_head *bh)
530 {
531         int ret;
532         struct journal_head *jh = bh2jh(bh);
533
534         if (ext3_test_bit(nr, bh->b_data))
535                 return 0;
536
537         jbd_lock_bh_state(bh);
538         if (!jh->b_committed_data)
539                 ret = 1;
540         else
541                 ret = !ext3_test_bit(nr, jh->b_committed_data);
542         jbd_unlock_bh_state(bh);
543         return ret;
544 }
545
546 static int
547 bitmap_search_next_usable_block(int start, struct buffer_head *bh,
548                                         int maxblocks)
549 {
550         int next;
551         struct journal_head *jh = bh2jh(bh);
552
553         /*
554          * The bitmap search --- search forward alternately through the actual
555          * bitmap and the last-committed copy until we find a bit free in
556          * both
557          */
558         while (start < maxblocks) {
559                 next = ext3_find_next_zero_bit(bh->b_data, maxblocks, start);
560                 if (next >= maxblocks)
561                         return -1;
562                 if (ext3_test_allocatable(next, bh))
563                         return next;
564                 jbd_lock_bh_state(bh);
565                 if (jh->b_committed_data)
566                         start = ext3_find_next_zero_bit(jh->b_committed_data,
567                                                         maxblocks, next);
568                 jbd_unlock_bh_state(bh);
569         }
570         return -1;
571 }
572
573 /*
574  * Find an allocatable block in a bitmap.  We honour both the bitmap and
575  * its last-committed copy (if that exists), and perform the "most
576  * appropriate allocation" algorithm of looking for a free block near
577  * the initial goal; then for a free byte somewhere in the bitmap; then
578  * for any free bit in the bitmap.
579  */
580 static int
581 find_next_usable_block(int start, struct buffer_head *bh, int maxblocks)
582 {
583         int here, next;
584         char *p, *r;
585
586         if (start > 0) {
587                 /*
588                  * The goal was occupied; search forward for a free 
589                  * block within the next XX blocks.
590                  *
591                  * end_goal is more or less random, but it has to be
592                  * less than EXT3_BLOCKS_PER_GROUP. Aligning up to the
593                  * next 64-bit boundary is simple..
594                  */
595                 int end_goal = (start + 63) & ~63;
596                 if (end_goal > maxblocks)
597                         end_goal = maxblocks;
598                 here = ext3_find_next_zero_bit(bh->b_data, end_goal, start);
599                 if (here < end_goal && ext3_test_allocatable(here, bh))
600                         return here;
601                 ext3_debug("Bit not found near goal\n");
602         }
603
604         here = start;
605         if (here < 0)
606                 here = 0;
607
608         p = ((char *)bh->b_data) + (here >> 3);
609         r = memscan(p, 0, (maxblocks - here + 7) >> 3);
610         next = (r - ((char *)bh->b_data)) << 3;
611
612         if (next < maxblocks && next >= start && ext3_test_allocatable(next, bh))
613                 return next;
614
615         /*
616          * The bitmap search --- search forward alternately through the actual
617          * bitmap and the last-committed copy until we find a bit free in
618          * both
619          */
620         here = bitmap_search_next_usable_block(here, bh, maxblocks);
621         return here;
622 }
623
624 /*
625  * We think we can allocate this block in this bitmap.  Try to set the bit.
626  * If that succeeds then check that nobody has allocated and then freed the
627  * block since we saw that is was not marked in b_committed_data.  If it _was_
628  * allocated and freed then clear the bit in the bitmap again and return
629  * zero (failure).
630  */
631 static inline int
632 claim_block(spinlock_t *lock, int block, struct buffer_head *bh)
633 {
634         struct journal_head *jh = bh2jh(bh);
635         int ret;
636
637         if (ext3_set_bit_atomic(lock, block, bh->b_data))
638                 return 0;
639         jbd_lock_bh_state(bh);
640         if (jh->b_committed_data && ext3_test_bit(block,jh->b_committed_data)) {
641                 ext3_clear_bit_atomic(lock, block, bh->b_data);
642                 ret = 0;
643         } else {
644                 ret = 1;
645         }
646         jbd_unlock_bh_state(bh);
647         return ret;
648 }
649
650 /*
651  * If we failed to allocate the desired block then we may end up crossing to a
652  * new bitmap.  In that case we must release write access to the old one via
653  * ext3_journal_release_buffer(), else we'll run out of credits.
654  */
655 static int
656 ext3_try_to_allocate(struct super_block *sb, handle_t *handle, int group,
657         struct buffer_head *bitmap_bh, int goal, struct ext3_reserve_window *my_rsv)
658 {
659         int group_first_block, start, end;
660
661         /* we do allocation within the reservation window if we have a window */
662         if (my_rsv) {
663                 group_first_block =
664                         le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block) +
665                         group * EXT3_BLOCKS_PER_GROUP(sb);
666                 if (my_rsv->_rsv_start >= group_first_block)
667                         start = my_rsv->_rsv_start - group_first_block;
668                 else
669                         /* reservation window cross group boundary */
670                         start = 0;
671                 end = my_rsv->_rsv_end - group_first_block + 1;
672                 if (end > EXT3_BLOCKS_PER_GROUP(sb))
673                         /* reservation window crosses group boundary */
674                         end = EXT3_BLOCKS_PER_GROUP(sb);
675                 if ((start <= goal) && (goal < end))
676                         start = goal;
677                 else
678                         goal = -1;
679         } else {
680                 if (goal > 0)
681                         start = goal;
682                 else
683                         start = 0;
684                 end = EXT3_BLOCKS_PER_GROUP(sb);
685         }
686
687         BUG_ON(start > EXT3_BLOCKS_PER_GROUP(sb));
688
689 repeat:
690         if (goal < 0 || !ext3_test_allocatable(goal, bitmap_bh)) {
691                 goal = find_next_usable_block(start, bitmap_bh, end);
692                 if (goal < 0)
693                         goto fail_access;
694                 if (!my_rsv) {
695                         int i;
696
697                         for (i = 0; i < 7 && goal > start &&
698                                         ext3_test_allocatable(goal - 1,
699                                                                 bitmap_bh);
700                                         i++, goal--)
701                                 ;
702                 }
703         }
704         start = goal;
705
706         if (!claim_block(sb_bgl_lock(EXT3_SB(sb), group), goal, bitmap_bh)) {
707                 /*
708                  * The block was allocated by another thread, or it was
709                  * allocated and then freed by another thread
710                  */
711                 start++;
712                 goal++;
713                 if (start >= end)
714                         goto fail_access;
715                 goto repeat;
716         }
717         return goal;
718 fail_access:
719         return -1;
720 }
721
722 /**
723  *      find_next_reservable_window():
724  *              find a reservable space within the given range.
725  *              It does not allocate the reservation window for now:
726  *              alloc_new_reservation() will do the work later.
727  *
728  *      @search_head: the head of the searching list;
729  *              This is not necessarily the list head of the whole filesystem
730  *
731  *              We have both head and start_block to assist the search
732  *              for the reservable space. The list starts from head,
733  *              but we will shift to the place where start_block is,
734  *              then start from there, when looking for a reservable space.
735  *
736  *      @size: the target new reservation window size
737  *
738  *      @group_first_block: the first block we consider to start
739  *                      the real search from
740  *
741  *      @last_block:
742  *              the maximum block number that our goal reservable space
743  *              could start from. This is normally the last block in this
744  *              group. The search will end when we found the start of next
745  *              possible reservable space is out of this boundary.
746  *              This could handle the cross boundary reservation window
747  *              request.
748  *
749  *      basically we search from the given range, rather than the whole
750  *      reservation double linked list, (start_block, last_block)
751  *      to find a free region that is of my size and has not
752  *      been reserved.
753  *
754  */
755 static int find_next_reservable_window(
756                                 struct ext3_reserve_window_node *search_head,
757                                 struct ext3_reserve_window_node *my_rsv,
758                                 struct super_block * sb, int start_block,
759                                 int last_block)
760 {
761         struct rb_node *next;
762         struct ext3_reserve_window_node *rsv, *prev;
763         int cur;
764         int size = my_rsv->rsv_goal_size;
765
766         /* TODO: make the start of the reservation window byte-aligned */
767         /* cur = *start_block & ~7;*/
768         cur = start_block;
769         rsv = search_head;
770         if (!rsv)
771                 return -1;
772
773         while (1) {
774                 if (cur <= rsv->rsv_end)
775                         cur = rsv->rsv_end + 1;
776
777                 /* TODO?
778                  * in the case we could not find a reservable space
779                  * that is what is expected, during the re-search, we could
780                  * remember what's the largest reservable space we could have
781                  * and return that one.
782                  *
783                  * For now it will fail if we could not find the reservable
784                  * space with expected-size (or more)...
785                  */
786                 if (cur > last_block)
787                         return -1;              /* fail */
788
789                 prev = rsv;
790                 next = rb_next(&rsv->rsv_node);
791                 rsv = list_entry(next,struct ext3_reserve_window_node,rsv_node);
792
793                 /*
794                  * Reached the last reservation, we can just append to the
795                  * previous one.
796                  */
797                 if (!next)
798                         break;
799
800                 if (cur + size <= rsv->rsv_start) {
801                         /*
802                          * Found a reserveable space big enough.  We could
803                          * have a reservation across the group boundary here
804                          */
805                         break;
806                 }
807         }
808         /*
809          * we come here either :
810          * when we reach the end of the whole list,
811          * and there is empty reservable space after last entry in the list.
812          * append it to the end of the list.
813          *
814          * or we found one reservable space in the middle of the list,
815          * return the reservation window that we could append to.
816          * succeed.
817          */
818
819         if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
820                 rsv_window_remove(sb, my_rsv);
821
822         /*
823          * Let's book the whole avaliable window for now.  We will check the
824          * disk bitmap later and then, if there are free blocks then we adjust
825          * the window size if it's larger than requested.
826          * Otherwise, we will remove this node from the tree next time
827          * call find_next_reservable_window.
828          */
829         my_rsv->rsv_start = cur;
830         my_rsv->rsv_end = cur + size - 1;
831         my_rsv->rsv_alloc_hit = 0;
832
833         if (prev != my_rsv)
834                 ext3_rsv_window_add(sb, my_rsv);
835
836         return 0;
837 }
838
839 /**
840  *      alloc_new_reservation()--allocate a new reservation window
841  *
842  *              To make a new reservation, we search part of the filesystem
843  *              reservation list (the list that inside the group). We try to
844  *              allocate a new reservation window near the allocation goal,
845  *              or the beginning of the group, if there is no goal.
846  *
847  *              We first find a reservable space after the goal, then from
848  *              there, we check the bitmap for the first free block after
849  *              it. If there is no free block until the end of group, then the
850  *              whole group is full, we failed. Otherwise, check if the free
851  *              block is inside the expected reservable space, if so, we
852  *              succeed.
853  *              If the first free block is outside the reservable space, then
854  *              start from the first free block, we search for next available
855  *              space, and go on.
856  *
857  *      on succeed, a new reservation will be found and inserted into the list
858  *      It contains at least one free block, and it does not overlap with other
859  *      reservation windows.
860  *
861  *      failed: we failed to find a reservation window in this group
862  *
863  *      @rsv: the reservation
864  *
865  *      @goal: The goal (group-relative).  It is where the search for a
866  *              free reservable space should start from.
867  *              if we have a goal(goal >0 ), then start from there,
868  *              no goal(goal = -1), we start from the first block
869  *              of the group.
870  *
871  *      @sb: the super block
872  *      @group: the group we are trying to allocate in
873  *      @bitmap_bh: the block group block bitmap
874  *
875  */
876 static int alloc_new_reservation(struct ext3_reserve_window_node *my_rsv,
877                 int goal, struct super_block *sb,
878                 unsigned int group, struct buffer_head *bitmap_bh)
879 {
880         struct ext3_reserve_window_node *search_head;
881         int group_first_block, group_end_block, start_block;
882         int first_free_block;
883         struct rb_root *fs_rsv_root = &EXT3_SB(sb)->s_rsv_window_root;
884         unsigned long size;
885         int ret;
886         spinlock_t *rsv_lock = &EXT3_SB(sb)->s_rsv_window_lock;
887
888         group_first_block = le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block) +
889                                 group * EXT3_BLOCKS_PER_GROUP(sb);
890         group_end_block = group_first_block + EXT3_BLOCKS_PER_GROUP(sb) - 1;
891
892         if (goal < 0)
893                 start_block = group_first_block;
894         else
895                 start_block = goal + group_first_block;
896
897         size = my_rsv->rsv_goal_size;
898
899         if (!rsv_is_empty(&my_rsv->rsv_window)) {
900                 /*
901                  * if the old reservation is cross group boundary
902                  * and if the goal is inside the old reservation window,
903                  * we will come here when we just failed to allocate from
904                  * the first part of the window. We still have another part
905                  * that belongs to the next group. In this case, there is no
906                  * point to discard our window and try to allocate a new one
907                  * in this group(which will fail). we should
908                  * keep the reservation window, just simply move on.
909                  *
910                  * Maybe we could shift the start block of the reservation
911                  * window to the first block of next group.
912                  */
913
914                 if ((my_rsv->rsv_start <= group_end_block) &&
915                                 (my_rsv->rsv_end > group_end_block) &&
916                                 (start_block >= my_rsv->rsv_start))
917                         return -1;
918
919                 if ((my_rsv->rsv_alloc_hit >
920                      (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
921                         /*
922                          * if we previously allocation hit ration is greater than half
923                          * we double the size of reservation window next time
924                          * otherwise keep the same
925                          */
926                         size = size * 2;
927                         if (size > EXT3_MAX_RESERVE_BLOCKS)
928                                 size = EXT3_MAX_RESERVE_BLOCKS;
929                         my_rsv->rsv_goal_size= size;
930                 }
931         }
932
933         spin_lock(rsv_lock);
934         /*
935          * shift the search start to the window near the goal block
936          */
937         search_head = search_reserve_window(fs_rsv_root, start_block);
938
939         /*
940          * find_next_reservable_window() simply finds a reservable window
941          * inside the given range(start_block, group_end_block).
942          *
943          * To make sure the reservation window has a free bit inside it, we
944          * need to check the bitmap after we found a reservable window.
945          */
946 retry:
947         ret = find_next_reservable_window(search_head, my_rsv, sb,
948                                                 start_block, group_end_block);
949
950         if (ret == -1) {
951                 if (!rsv_is_empty(&my_rsv->rsv_window))
952                         rsv_window_remove(sb, my_rsv);
953                 spin_unlock(rsv_lock);
954                 return -1;
955         }
956
957         /*
958          * On success, find_next_reservable_window() returns the
959          * reservation window where there is a reservable space after it.
960          * Before we reserve this reservable space, we need
961          * to make sure there is at least a free block inside this region.
962          *
963          * searching the first free bit on the block bitmap and copy of
964          * last committed bitmap alternatively, until we found a allocatable
965          * block. Search start from the start block of the reservable space
966          * we just found.
967          */
968         spin_unlock(rsv_lock);
969         first_free_block = bitmap_search_next_usable_block(
970                         my_rsv->rsv_start - group_first_block,
971                         bitmap_bh, group_end_block - group_first_block + 1);
972
973         if (first_free_block < 0) {
974                 /*
975                  * no free block left on the bitmap, no point
976                  * to reserve the space. return failed.
977                  */
978                 spin_lock(rsv_lock);
979                 if (!rsv_is_empty(&my_rsv->rsv_window))
980                         rsv_window_remove(sb, my_rsv);
981                 spin_unlock(rsv_lock);
982                 return -1;              /* failed */
983         }
984
985         start_block = first_free_block + group_first_block;
986         /*
987          * check if the first free block is within the
988          * free space we just reserved
989          */
990         if (start_block >= my_rsv->rsv_start && start_block < my_rsv->rsv_end)
991                 return 0;               /* success */
992         /*
993          * if the first free bit we found is out of the reservable space
994          * continue search for next reservable space,
995          * start from where the free block is,
996          * we also shift the list head to where we stopped last time
997          */
998         search_head = my_rsv;
999         spin_lock(rsv_lock);
1000         goto retry;
1001 }
1002
1003 /*
1004  * This is the main function used to allocate a new block and its reservation
1005  * window.
1006  *
1007  * Each time when a new block allocation is need, first try to allocate from
1008  * its own reservation.  If it does not have a reservation window, instead of
1009  * looking for a free bit on bitmap first, then look up the reservation list to
1010  * see if it is inside somebody else's reservation window, we try to allocate a
1011  * reservation window for it starting from the goal first. Then do the block
1012  * allocation within the reservation window.
1013  *
1014  * This will avoid keeping on searching the reservation list again and
1015  * again when somebody is looking for a free block (without
1016  * reservation), and there are lots of free blocks, but they are all
1017  * being reserved.
1018  *
1019  * We use a sorted double linked list for the per-filesystem reservation list.
1020  * The insert, remove and find a free space(non-reserved) operations for the
1021  * sorted double linked list should be fast.
1022  *
1023  */
1024 static int
1025 ext3_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
1026                         unsigned int group, struct buffer_head *bitmap_bh,
1027                         int goal, struct ext3_reserve_window_node * my_rsv,
1028                         int *errp)
1029 {
1030         unsigned long group_first_block;
1031         int ret = 0;
1032         int fatal;
1033
1034         *errp = 0;
1035
1036         /*
1037          * Make sure we use undo access for the bitmap, because it is critical
1038          * that we do the frozen_data COW on bitmap buffers in all cases even
1039          * if the buffer is in BJ_Forget state in the committing transaction.
1040          */
1041         BUFFER_TRACE(bitmap_bh, "get undo access for new block");
1042         fatal = ext3_journal_get_undo_access(handle, bitmap_bh);
1043         if (fatal) {
1044                 *errp = fatal;
1045                 return -1;
1046         }
1047
1048         /*
1049          * we don't deal with reservation when
1050          * filesystem is mounted without reservation
1051          * or the file is not a regular file
1052          * or last attempt to allocate a block with reservation turned on failed
1053          */
1054         if (my_rsv == NULL ) {
1055                 ret = ext3_try_to_allocate(sb, handle, group, bitmap_bh, goal, NULL);
1056                 goto out;
1057         }
1058         /*
1059          * goal is a group relative block number (if there is a goal)
1060          * 0 < goal < EXT3_BLOCKS_PER_GROUP(sb)
1061          * first block is a filesystem wide block number
1062          * first block is the block number of the first block in this group
1063          */
1064         group_first_block = le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block) +
1065                         group * EXT3_BLOCKS_PER_GROUP(sb);
1066
1067         /*
1068          * Basically we will allocate a new block from inode's reservation
1069          * window.
1070          *
1071          * We need to allocate a new reservation window, if:
1072          * a) inode does not have a reservation window; or
1073          * b) last attempt to allocate a block from existing reservation
1074          *    failed; or
1075          * c) we come here with a goal and with a reservation window
1076          *
1077          * We do not need to allocate a new reservation window if we come here
1078          * at the beginning with a goal and the goal is inside the window, or
1079          * we don't have a goal but already have a reservation window.
1080          * then we could go to allocate from the reservation window directly.
1081          */
1082         while (1) {
1083                 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
1084                         !goal_in_my_reservation(&my_rsv->rsv_window, goal, group, sb)) {
1085                         ret = alloc_new_reservation(my_rsv, goal, sb,
1086                                                         group, bitmap_bh);
1087                         if (ret < 0)
1088                                 break;                  /* failed */
1089
1090                         if (!goal_in_my_reservation(&my_rsv->rsv_window, goal, group, sb))
1091                                 goal = -1;
1092                 }
1093                 if ((my_rsv->rsv_start >= group_first_block + EXT3_BLOCKS_PER_GROUP(sb))
1094                     || (my_rsv->rsv_end < group_first_block))
1095                         BUG();
1096                 ret = ext3_try_to_allocate(sb, handle, group, bitmap_bh, goal,
1097                                            &my_rsv->rsv_window);
1098                 if (ret >= 0) {
1099                         my_rsv->rsv_alloc_hit++;
1100                         break;                          /* succeed */
1101                 }
1102         }
1103 out:
1104         if (ret >= 0) {
1105                 BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for "
1106                                         "bitmap block");
1107                 fatal = ext3_journal_dirty_metadata(handle, bitmap_bh);
1108                 if (fatal) {
1109                         *errp = fatal;
1110                         return -1;
1111                 }
1112                 return ret;
1113         }
1114
1115         BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
1116         ext3_journal_release_buffer(handle, bitmap_bh);
1117         return ret;
1118 }
1119
1120 static int ext3_has_free_blocks(struct ext3_sb_info *sbi)
1121 {
1122         int free_blocks, root_blocks;
1123
1124         free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
1125         root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count);
1126         if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
1127                 sbi->s_resuid != current->fsuid &&
1128                 (sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
1129                 return 0;
1130         }
1131         return 1;
1132 }
1133
1134 /*
1135  * ext3_should_retry_alloc() is called when ENOSPC is returned, and if
1136  * it is profitable to retry the operation, this function will wait
1137  * for the current or commiting transaction to complete, and then
1138  * return TRUE.
1139  */
1140 int ext3_should_retry_alloc(struct super_block *sb, int *retries)
1141 {
1142         if (!ext3_has_free_blocks(EXT3_SB(sb)) || (*retries)++ > 3)
1143                 return 0;
1144
1145         jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
1146
1147         return journal_force_commit_nested(EXT3_SB(sb)->s_journal);
1148 }
1149
1150 /*
1151  * ext3_new_block uses a goal block to assist allocation.  If the goal is
1152  * free, or there is a free block within 32 blocks of the goal, that block
1153  * is allocated.  Otherwise a forward search is made for a free block; within 
1154  * each block group the search first looks for an entire free byte in the block
1155  * bitmap, and then for any free bit if that fails.
1156  * This function also updates quota and i_blocks field.
1157  */
1158 int ext3_new_block(handle_t *handle, struct inode *inode,
1159                         unsigned long goal, int *errp)
1160 {
1161         struct buffer_head *bitmap_bh = NULL;
1162         struct buffer_head *gdp_bh;
1163         int group_no;
1164         int goal_group;
1165         int ret_block;
1166         int bgi;                        /* blockgroup iteration index */
1167         int target_block;
1168         int fatal = 0, err;
1169         int performed_allocation = 0;
1170         int free_blocks;
1171         struct super_block *sb;
1172         struct ext3_group_desc *gdp;
1173         struct ext3_super_block *es;
1174         struct ext3_sb_info *sbi;
1175         struct ext3_reserve_window_node *my_rsv = NULL;
1176         struct ext3_block_alloc_info *block_i;
1177         unsigned short windowsz = 0;
1178 #ifdef EXT3FS_DEBUG
1179         static int goal_hits, goal_attempts;
1180 #endif
1181         unsigned long ngroups;
1182
1183         *errp = -ENOSPC;
1184         sb = inode->i_sb;
1185         if (!sb) {
1186                 printk("ext3_new_block: nonexistent device");
1187                 return 0;
1188         }
1189
1190         /*
1191          * Check quota for allocation of this block.
1192          */
1193         if (DQUOT_ALLOC_BLOCK(inode, 1)) {
1194                 *errp = -EDQUOT;
1195                 return 0;
1196         }
1197
1198         sbi = EXT3_SB(sb);
1199         es = EXT3_SB(sb)->s_es;
1200         ext3_debug("goal=%lu.\n", goal);
1201         /*
1202          * Allocate a block from reservation only when
1203          * filesystem is mounted with reservation(default,-o reservation), and
1204          * it's a regular file, and
1205          * the desired window size is greater than 0 (One could use ioctl
1206          * command EXT3_IOC_SETRSVSZ to set the window size to 0 to turn off
1207          * reservation on that particular file)
1208          */
1209         block_i = EXT3_I(inode)->i_block_alloc_info;
1210         if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
1211                 my_rsv = &block_i->rsv_window_node;
1212
1213         if (!ext3_has_free_blocks(sbi)) {
1214                 *errp = -ENOSPC;
1215                 goto out;
1216         }
1217
1218         /*
1219          * First, test whether the goal block is free.
1220          */
1221         if (goal < le32_to_cpu(es->s_first_data_block) ||
1222             goal >= le32_to_cpu(es->s_blocks_count))
1223                 goal = le32_to_cpu(es->s_first_data_block);
1224         group_no = (goal - le32_to_cpu(es->s_first_data_block)) /
1225                         EXT3_BLOCKS_PER_GROUP(sb);
1226         gdp = ext3_get_group_desc(sb, group_no, &gdp_bh);
1227         if (!gdp)
1228                 goto io_error;
1229
1230         goal_group = group_no;
1231 retry:
1232         free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1233         /*
1234          * if there is not enough free blocks to make a new resevation
1235          * turn off reservation for this allocation
1236          */
1237         if (my_rsv && (free_blocks < windowsz)
1238                 && (rsv_is_empty(&my_rsv->rsv_window)))
1239                 my_rsv = NULL;
1240
1241         if (free_blocks > 0) {
1242                 ret_block = ((goal - le32_to_cpu(es->s_first_data_block)) %
1243                                 EXT3_BLOCKS_PER_GROUP(sb));
1244                 bitmap_bh = read_block_bitmap(sb, group_no);
1245                 if (!bitmap_bh)
1246                         goto io_error;
1247                 ret_block = ext3_try_to_allocate_with_rsv(sb, handle, group_no,
1248                                         bitmap_bh, ret_block, my_rsv, &fatal);
1249                 if (fatal)
1250                         goto out;
1251                 if (ret_block >= 0)
1252                         goto allocated;
1253         }
1254
1255         ngroups = EXT3_SB(sb)->s_groups_count;
1256         smp_rmb();
1257
1258         /*
1259          * Now search the rest of the groups.  We assume that 
1260          * i and gdp correctly point to the last group visited.
1261          */
1262         for (bgi = 0; bgi < ngroups; bgi++) {
1263                 group_no++;
1264                 if (group_no >= ngroups)
1265                         group_no = 0;
1266                 gdp = ext3_get_group_desc(sb, group_no, &gdp_bh);
1267                 if (!gdp) {
1268                         *errp = -EIO;
1269                         goto out;
1270                 }
1271                 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1272                 /*
1273                  * skip this group if the number of
1274                  * free blocks is less than half of the reservation
1275                  * window size.
1276                  */
1277                 if (free_blocks <= (windowsz/2))
1278                         continue;
1279
1280                 brelse(bitmap_bh);
1281                 bitmap_bh = read_block_bitmap(sb, group_no);
1282                 if (!bitmap_bh)
1283                         goto io_error;
1284                 ret_block = ext3_try_to_allocate_with_rsv(sb, handle, group_no,
1285                                         bitmap_bh, -1, my_rsv, &fatal);
1286                 if (fatal)
1287                         goto out;
1288                 if (ret_block >= 0) 
1289                         goto allocated;
1290         }
1291         /*
1292          * We may end up a bogus ealier ENOSPC error due to
1293          * filesystem is "full" of reservations, but
1294          * there maybe indeed free blocks avaliable on disk
1295          * In this case, we just forget about the reservations
1296          * just do block allocation as without reservations.
1297          */
1298         if (my_rsv) {
1299                 my_rsv = NULL;
1300                 group_no = goal_group;
1301                 goto retry;
1302         }
1303         /* No space left on the device */
1304         *errp = -ENOSPC;
1305         goto out;
1306
1307 allocated:
1308
1309         ext3_debug("using block group %d(%d)\n",
1310                         group_no, gdp->bg_free_blocks_count);
1311
1312         BUFFER_TRACE(gdp_bh, "get_write_access");
1313         fatal = ext3_journal_get_write_access(handle, gdp_bh);
1314         if (fatal)
1315                 goto out;
1316
1317         target_block = ret_block + group_no * EXT3_BLOCKS_PER_GROUP(sb)
1318                                 + le32_to_cpu(es->s_first_data_block);
1319
1320         if (target_block == le32_to_cpu(gdp->bg_block_bitmap) ||
1321             target_block == le32_to_cpu(gdp->bg_inode_bitmap) ||
1322             in_range(target_block, le32_to_cpu(gdp->bg_inode_table),
1323                       EXT3_SB(sb)->s_itb_per_group))
1324                 ext3_error(sb, "ext3_new_block",
1325                             "Allocating block in system zone - "
1326                             "block = %u", target_block);
1327
1328         performed_allocation = 1;
1329
1330 #ifdef CONFIG_JBD_DEBUG
1331         {
1332                 struct buffer_head *debug_bh;
1333
1334                 /* Record bitmap buffer state in the newly allocated block */
1335                 debug_bh = sb_find_get_block(sb, target_block);
1336                 if (debug_bh) {
1337                         BUFFER_TRACE(debug_bh, "state when allocated");
1338                         BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap state");
1339                         brelse(debug_bh);
1340                 }
1341         }
1342         jbd_lock_bh_state(bitmap_bh);
1343         spin_lock(sb_bgl_lock(sbi, group_no));
1344         if (buffer_jbd(bitmap_bh) && bh2jh(bitmap_bh)->b_committed_data) {
1345                 if (ext3_test_bit(ret_block,
1346                                 bh2jh(bitmap_bh)->b_committed_data)) {
1347                         printk("%s: block was unexpectedly set in "
1348                                 "b_committed_data\n", __FUNCTION__);
1349                 }
1350         }
1351         ext3_debug("found bit %d\n", ret_block);
1352         spin_unlock(sb_bgl_lock(sbi, group_no));
1353         jbd_unlock_bh_state(bitmap_bh);
1354 #endif
1355
1356         /* ret_block was blockgroup-relative.  Now it becomes fs-relative */
1357         ret_block = target_block;
1358
1359         if (ret_block >= le32_to_cpu(es->s_blocks_count)) {
1360                 ext3_error(sb, "ext3_new_block",
1361                             "block(%d) >= blocks count(%d) - "
1362                             "block_group = %d, es == %p ", ret_block,
1363                         le32_to_cpu(es->s_blocks_count), group_no, es);
1364                 goto out;
1365         }
1366
1367         /*
1368          * It is up to the caller to add the new buffer to a journal
1369          * list of some description.  We don't know in advance whether
1370          * the caller wants to use it as metadata or data.
1371          */
1372         ext3_debug("allocating block %d. Goal hits %d of %d.\n",
1373                         ret_block, goal_hits, goal_attempts);
1374
1375         spin_lock(sb_bgl_lock(sbi, group_no));
1376         gdp->bg_free_blocks_count =
1377                         cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count) - 1);
1378         spin_unlock(sb_bgl_lock(sbi, group_no));
1379         percpu_counter_mod(&sbi->s_freeblocks_counter, -1);
1380
1381         BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
1382         err = ext3_journal_dirty_metadata(handle, gdp_bh);
1383         if (!fatal)
1384                 fatal = err;
1385
1386         sb->s_dirt = 1;
1387         if (fatal)
1388                 goto out;
1389
1390         *errp = 0;
1391         brelse(bitmap_bh);
1392         return ret_block;
1393
1394 io_error:
1395         *errp = -EIO;
1396 out:
1397         if (fatal) {
1398                 *errp = fatal;
1399                 ext3_std_error(sb, fatal);
1400         }
1401         /*
1402          * Undo the block allocation
1403          */
1404         if (!performed_allocation)
1405                 DQUOT_FREE_BLOCK(inode, 1);
1406         brelse(bitmap_bh);
1407         return 0;
1408 }
1409
1410 unsigned long ext3_count_free_blocks(struct super_block *sb)
1411 {
1412         unsigned long desc_count;
1413         struct ext3_group_desc *gdp;
1414         int i;
1415         unsigned long ngroups = EXT3_SB(sb)->s_groups_count;
1416 #ifdef EXT3FS_DEBUG
1417         struct ext3_super_block *es;
1418         unsigned long bitmap_count, x;
1419         struct buffer_head *bitmap_bh = NULL;
1420
1421         es = EXT3_SB(sb)->s_es;
1422         desc_count = 0;
1423         bitmap_count = 0;
1424         gdp = NULL;
1425
1426         smp_rmb();
1427         for (i = 0; i < ngroups; i++) {
1428                 gdp = ext3_get_group_desc(sb, i, NULL);
1429                 if (!gdp)
1430                         continue;
1431                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1432                 brelse(bitmap_bh);
1433                 bitmap_bh = read_block_bitmap(sb, i);
1434                 if (bitmap_bh == NULL)
1435                         continue;
1436
1437                 x = ext3_count_free(bitmap_bh, sb->s_blocksize);
1438                 printk("group %d: stored = %d, counted = %lu\n",
1439                         i, le16_to_cpu(gdp->bg_free_blocks_count), x);
1440                 bitmap_count += x;
1441         }
1442         brelse(bitmap_bh);
1443         printk("ext3_count_free_blocks: stored = %u, computed = %lu, %lu\n",
1444                le32_to_cpu(es->s_free_blocks_count), desc_count, bitmap_count);
1445         return bitmap_count;
1446 #else
1447         desc_count = 0;
1448         smp_rmb();
1449         for (i = 0; i < ngroups; i++) {
1450                 gdp = ext3_get_group_desc(sb, i, NULL);
1451                 if (!gdp)
1452                         continue;
1453                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1454         }
1455
1456         return desc_count;
1457 #endif
1458 }
1459
1460 static inline int
1461 block_in_use(unsigned long block, struct super_block *sb, unsigned char *map)
1462 {
1463         return ext3_test_bit ((block -
1464                 le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block)) %
1465                          EXT3_BLOCKS_PER_GROUP(sb), map);
1466 }
1467
1468 static inline int test_root(int a, int b)
1469 {
1470         int num = b;
1471
1472         while (a > num)
1473                 num *= b;
1474         return num == a;
1475 }
1476
1477 static int ext3_group_sparse(int group)
1478 {
1479         if (group <= 1)
1480                 return 1;
1481         if (!(group & 1))
1482                 return 0;
1483         return (test_root(group, 7) || test_root(group, 5) ||
1484                 test_root(group, 3));
1485 }
1486
1487 /**
1488  *      ext3_bg_has_super - number of blocks used by the superblock in group
1489  *      @sb: superblock for filesystem
1490  *      @group: group number to check
1491  *
1492  *      Return the number of blocks used by the superblock (primary or backup)
1493  *      in this group.  Currently this will be only 0 or 1.
1494  */
1495 int ext3_bg_has_super(struct super_block *sb, int group)
1496 {
1497         if (EXT3_HAS_RO_COMPAT_FEATURE(sb,EXT3_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
1498             !ext3_group_sparse(group))
1499                 return 0;
1500         return 1;
1501 }
1502
1503 /**
1504  *      ext3_bg_num_gdb - number of blocks used by the group table in group
1505  *      @sb: superblock for filesystem
1506  *      @group: group number to check
1507  *
1508  *      Return the number of blocks used by the group descriptor table
1509  *      (primary or backup) in this group.  In the future there may be a
1510  *      different number of descriptor blocks in each group.
1511  */
1512 unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
1513 {
1514         if (EXT3_HAS_RO_COMPAT_FEATURE(sb,EXT3_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
1515             !ext3_group_sparse(group))
1516                 return 0;
1517         return EXT3_SB(sb)->s_gdb_count;
1518 }
1519
1520 #ifdef CONFIG_EXT3_CHECK
1521 /* Called at mount-time, super-block is locked */
1522 void ext3_check_blocks_bitmap (struct super_block * sb)
1523 {
1524         struct ext3_super_block *es;
1525         unsigned long desc_count, bitmap_count, x, j;
1526         unsigned long desc_blocks;
1527         struct buffer_head *bitmap_bh = NULL;
1528         struct ext3_group_desc *gdp;
1529         int i;
1530
1531         es = EXT3_SB(sb)->s_es;
1532         desc_count = 0;
1533         bitmap_count = 0;
1534         gdp = NULL;
1535         for (i = 0; i < EXT3_SB(sb)->s_groups_count; i++) {
1536                 gdp = ext3_get_group_desc (sb, i, NULL);
1537                 if (!gdp)
1538                         continue;
1539                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1540                 brelse(bitmap_bh);
1541                 bitmap_bh = read_block_bitmap(sb, i);
1542                 if (bitmap_bh == NULL)
1543                         continue;
1544
1545                 if (ext3_bg_has_super(sb, i) &&
1546                                 !ext3_test_bit(0, bitmap_bh->b_data))
1547                         ext3_error(sb, __FUNCTION__,
1548                                    "Superblock in group %d is marked free", i);
1549
1550                 desc_blocks = ext3_bg_num_gdb(sb, i);
1551                 for (j = 0; j < desc_blocks; j++)
1552                         if (!ext3_test_bit(j + 1, bitmap_bh->b_data))
1553                                 ext3_error(sb, __FUNCTION__,
1554                                            "Descriptor block #%ld in group "
1555                                            "%d is marked free", j, i);
1556
1557                 if (!block_in_use (le32_to_cpu(gdp->bg_block_bitmap),
1558                                                 sb, bitmap_bh->b_data))
1559                         ext3_error (sb, "ext3_check_blocks_bitmap",
1560                                     "Block bitmap for group %d is marked free",
1561                                     i);
1562
1563                 if (!block_in_use (le32_to_cpu(gdp->bg_inode_bitmap),
1564                                                 sb, bitmap_bh->b_data))
1565                         ext3_error (sb, "ext3_check_blocks_bitmap",
1566                                     "Inode bitmap for group %d is marked free",
1567                                     i);
1568
1569                 for (j = 0; j < EXT3_SB(sb)->s_itb_per_group; j++)
1570                         if (!block_in_use (le32_to_cpu(gdp->bg_inode_table) + j,
1571                                                         sb, bitmap_bh->b_data))
1572                                 ext3_error (sb, "ext3_check_blocks_bitmap",
1573                                             "Block #%d of the inode table in "
1574                                             "group %d is marked free", j, i);
1575
1576                 x = ext3_count_free(bitmap_bh, sb->s_blocksize);
1577                 if (le16_to_cpu(gdp->bg_free_blocks_count) != x)
1578                         ext3_error (sb, "ext3_check_blocks_bitmap",
1579                                     "Wrong free blocks count for group %d, "
1580                                     "stored = %d, counted = %lu", i,
1581                                     le16_to_cpu(gdp->bg_free_blocks_count), x);
1582                 bitmap_count += x;
1583         }
1584         brelse(bitmap_bh);
1585         if (le32_to_cpu(es->s_free_blocks_count) != bitmap_count)
1586                 ext3_error (sb, "ext3_check_blocks_bitmap",
1587                         "Wrong free blocks count in super block, "
1588                         "stored = %lu, counted = %lu",
1589                         (unsigned long)le32_to_cpu(es->s_free_blocks_count),
1590                         bitmap_count);
1591 }
1592 #endif