Merge branches 'release', 'acpi_pm_device_sleep_state' and 'battery' into release
[linux-2.6] / fs / ocfs2 / suballoc.c
1 /* -*- mode: c; c-basic-offset: 8; -*-
2  * vim: noexpandtab sw=8 ts=8 sts=0:
3  *
4  * suballoc.c
5  *
6  * metadata alloc and free
7  * Inspired by ext3 block groups.
8  *
9  * Copyright (C) 2002, 2004 Oracle.  All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19  * General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public
22  * License along with this program; if not, write to the
23  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24  * Boston, MA 021110-1307, USA.
25  */
26
27 #include <linux/fs.h>
28 #include <linux/types.h>
29 #include <linux/slab.h>
30 #include <linux/highmem.h>
31
32 #define MLOG_MASK_PREFIX ML_DISK_ALLOC
33 #include <cluster/masklog.h>
34
35 #include "ocfs2.h"
36
37 #include "alloc.h"
38 #include "dlmglue.h"
39 #include "inode.h"
40 #include "journal.h"
41 #include "localalloc.h"
42 #include "suballoc.h"
43 #include "super.h"
44 #include "sysfile.h"
45 #include "uptodate.h"
46
47 #include "buffer_head_io.h"
48
49 static inline void ocfs2_debug_bg(struct ocfs2_group_desc *bg);
50 static inline void ocfs2_debug_suballoc_inode(struct ocfs2_dinode *fe);
51 static inline u16 ocfs2_find_victim_chain(struct ocfs2_chain_list *cl);
52 static int ocfs2_block_group_fill(handle_t *handle,
53                                   struct inode *alloc_inode,
54                                   struct buffer_head *bg_bh,
55                                   u64 group_blkno,
56                                   u16 my_chain,
57                                   struct ocfs2_chain_list *cl);
58 static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
59                                    struct inode *alloc_inode,
60                                    struct buffer_head *bh);
61
62 static int ocfs2_cluster_group_search(struct inode *inode,
63                                       struct buffer_head *group_bh,
64                                       u32 bits_wanted, u32 min_bits,
65                                       u16 *bit_off, u16 *bits_found);
66 static int ocfs2_block_group_search(struct inode *inode,
67                                     struct buffer_head *group_bh,
68                                     u32 bits_wanted, u32 min_bits,
69                                     u16 *bit_off, u16 *bits_found);
70 static int ocfs2_claim_suballoc_bits(struct ocfs2_super *osb,
71                                      struct ocfs2_alloc_context *ac,
72                                      handle_t *handle,
73                                      u32 bits_wanted,
74                                      u32 min_bits,
75                                      u16 *bit_off,
76                                      unsigned int *num_bits,
77                                      u64 *bg_blkno);
78 static int ocfs2_test_bg_bit_allocatable(struct buffer_head *bg_bh,
79                                          int nr);
80 static inline int ocfs2_block_group_set_bits(handle_t *handle,
81                                              struct inode *alloc_inode,
82                                              struct ocfs2_group_desc *bg,
83                                              struct buffer_head *group_bh,
84                                              unsigned int bit_off,
85                                              unsigned int num_bits);
86 static inline int ocfs2_block_group_clear_bits(handle_t *handle,
87                                                struct inode *alloc_inode,
88                                                struct ocfs2_group_desc *bg,
89                                                struct buffer_head *group_bh,
90                                                unsigned int bit_off,
91                                                unsigned int num_bits);
92
93 static int ocfs2_relink_block_group(handle_t *handle,
94                                     struct inode *alloc_inode,
95                                     struct buffer_head *fe_bh,
96                                     struct buffer_head *bg_bh,
97                                     struct buffer_head *prev_bg_bh,
98                                     u16 chain);
99 static inline int ocfs2_block_group_reasonably_empty(struct ocfs2_group_desc *bg,
100                                                      u32 wanted);
101 static inline u32 ocfs2_desc_bitmap_to_cluster_off(struct inode *inode,
102                                                    u64 bg_blkno,
103                                                    u16 bg_bit_off);
104 static inline void ocfs2_block_to_cluster_group(struct inode *inode,
105                                                 u64 data_blkno,
106                                                 u64 *bg_blkno,
107                                                 u16 *bg_bit_off);
108
109 void ocfs2_free_alloc_context(struct ocfs2_alloc_context *ac)
110 {
111         struct inode *inode = ac->ac_inode;
112
113         if (inode) {
114                 if (ac->ac_which != OCFS2_AC_USE_LOCAL)
115                         ocfs2_inode_unlock(inode, 1);
116
117                 mutex_unlock(&inode->i_mutex);
118
119                 iput(inode);
120         }
121         if (ac->ac_bh)
122                 brelse(ac->ac_bh);
123         kfree(ac);
124 }
125
126 static u32 ocfs2_bits_per_group(struct ocfs2_chain_list *cl)
127 {
128         return (u32)le16_to_cpu(cl->cl_cpg) * (u32)le16_to_cpu(cl->cl_bpc);
129 }
130
131 /* somewhat more expensive than our other checks, so use sparingly. */
132 int ocfs2_check_group_descriptor(struct super_block *sb,
133                                  struct ocfs2_dinode *di,
134                                  struct ocfs2_group_desc *gd)
135 {
136         unsigned int max_bits;
137
138         if (!OCFS2_IS_VALID_GROUP_DESC(gd)) {
139                 OCFS2_RO_ON_INVALID_GROUP_DESC(sb, gd);
140                 return -EIO;
141         }
142
143         if (di->i_blkno != gd->bg_parent_dinode) {
144                 ocfs2_error(sb, "Group descriptor # %llu has bad parent "
145                             "pointer (%llu, expected %llu)",
146                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
147                             (unsigned long long)le64_to_cpu(gd->bg_parent_dinode),
148                             (unsigned long long)le64_to_cpu(di->i_blkno));
149                 return -EIO;
150         }
151
152         max_bits = le16_to_cpu(di->id2.i_chain.cl_cpg) * le16_to_cpu(di->id2.i_chain.cl_bpc);
153         if (le16_to_cpu(gd->bg_bits) > max_bits) {
154                 ocfs2_error(sb, "Group descriptor # %llu has bit count of %u",
155                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
156                             le16_to_cpu(gd->bg_bits));
157                 return -EIO;
158         }
159
160         if (le16_to_cpu(gd->bg_chain) >=
161             le16_to_cpu(di->id2.i_chain.cl_next_free_rec)) {
162                 ocfs2_error(sb, "Group descriptor # %llu has bad chain %u",
163                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
164                             le16_to_cpu(gd->bg_chain));
165                 return -EIO;
166         }
167
168         if (le16_to_cpu(gd->bg_free_bits_count) > le16_to_cpu(gd->bg_bits)) {
169                 ocfs2_error(sb, "Group descriptor # %llu has bit count %u but "
170                             "claims that %u are free",
171                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
172                             le16_to_cpu(gd->bg_bits),
173                             le16_to_cpu(gd->bg_free_bits_count));
174                 return -EIO;
175         }
176
177         if (le16_to_cpu(gd->bg_bits) > (8 * le16_to_cpu(gd->bg_size))) {
178                 ocfs2_error(sb, "Group descriptor # %llu has bit count %u but "
179                             "max bitmap bits of %u",
180                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
181                             le16_to_cpu(gd->bg_bits),
182                             8 * le16_to_cpu(gd->bg_size));
183                 return -EIO;
184         }
185
186         return 0;
187 }
188
189 static int ocfs2_block_group_fill(handle_t *handle,
190                                   struct inode *alloc_inode,
191                                   struct buffer_head *bg_bh,
192                                   u64 group_blkno,
193                                   u16 my_chain,
194                                   struct ocfs2_chain_list *cl)
195 {
196         int status = 0;
197         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
198         struct super_block * sb = alloc_inode->i_sb;
199
200         mlog_entry_void();
201
202         if (((unsigned long long) bg_bh->b_blocknr) != group_blkno) {
203                 ocfs2_error(alloc_inode->i_sb, "group block (%llu) != "
204                             "b_blocknr (%llu)",
205                             (unsigned long long)group_blkno,
206                             (unsigned long long) bg_bh->b_blocknr);
207                 status = -EIO;
208                 goto bail;
209         }
210
211         status = ocfs2_journal_access(handle,
212                                       alloc_inode,
213                                       bg_bh,
214                                       OCFS2_JOURNAL_ACCESS_CREATE);
215         if (status < 0) {
216                 mlog_errno(status);
217                 goto bail;
218         }
219
220         memset(bg, 0, sb->s_blocksize);
221         strcpy(bg->bg_signature, OCFS2_GROUP_DESC_SIGNATURE);
222         bg->bg_generation = cpu_to_le32(OCFS2_SB(sb)->fs_generation);
223         bg->bg_size = cpu_to_le16(ocfs2_group_bitmap_size(sb));
224         bg->bg_bits = cpu_to_le16(ocfs2_bits_per_group(cl));
225         bg->bg_chain = cpu_to_le16(my_chain);
226         bg->bg_next_group = cl->cl_recs[my_chain].c_blkno;
227         bg->bg_parent_dinode = cpu_to_le64(OCFS2_I(alloc_inode)->ip_blkno);
228         bg->bg_blkno = cpu_to_le64(group_blkno);
229         /* set the 1st bit in the bitmap to account for the descriptor block */
230         ocfs2_set_bit(0, (unsigned long *)bg->bg_bitmap);
231         bg->bg_free_bits_count = cpu_to_le16(le16_to_cpu(bg->bg_bits) - 1);
232
233         status = ocfs2_journal_dirty(handle, bg_bh);
234         if (status < 0)
235                 mlog_errno(status);
236
237         /* There is no need to zero out or otherwise initialize the
238          * other blocks in a group - All valid FS metadata in a block
239          * group stores the superblock fs_generation value at
240          * allocation time. */
241
242 bail:
243         mlog_exit(status);
244         return status;
245 }
246
247 static inline u16 ocfs2_find_smallest_chain(struct ocfs2_chain_list *cl)
248 {
249         u16 curr, best;
250
251         best = curr = 0;
252         while (curr < le16_to_cpu(cl->cl_count)) {
253                 if (le32_to_cpu(cl->cl_recs[best].c_total) >
254                     le32_to_cpu(cl->cl_recs[curr].c_total))
255                         best = curr;
256                 curr++;
257         }
258         return best;
259 }
260
261 /*
262  * We expect the block group allocator to already be locked.
263  */
264 static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
265                                    struct inode *alloc_inode,
266                                    struct buffer_head *bh)
267 {
268         int status, credits;
269         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) bh->b_data;
270         struct ocfs2_chain_list *cl;
271         struct ocfs2_alloc_context *ac = NULL;
272         handle_t *handle = NULL;
273         u32 bit_off, num_bits;
274         u16 alloc_rec;
275         u64 bg_blkno;
276         struct buffer_head *bg_bh = NULL;
277         struct ocfs2_group_desc *bg;
278
279         BUG_ON(ocfs2_is_cluster_bitmap(alloc_inode));
280
281         mlog_entry_void();
282
283         cl = &fe->id2.i_chain;
284         status = ocfs2_reserve_clusters(osb,
285                                         le16_to_cpu(cl->cl_cpg),
286                                         &ac);
287         if (status < 0) {
288                 if (status != -ENOSPC)
289                         mlog_errno(status);
290                 goto bail;
291         }
292
293         credits = ocfs2_calc_group_alloc_credits(osb->sb,
294                                                  le16_to_cpu(cl->cl_cpg));
295         handle = ocfs2_start_trans(osb, credits);
296         if (IS_ERR(handle)) {
297                 status = PTR_ERR(handle);
298                 handle = NULL;
299                 mlog_errno(status);
300                 goto bail;
301         }
302
303         status = ocfs2_claim_clusters(osb,
304                                       handle,
305                                       ac,
306                                       le16_to_cpu(cl->cl_cpg),
307                                       &bit_off,
308                                       &num_bits);
309         if (status < 0) {
310                 if (status != -ENOSPC)
311                         mlog_errno(status);
312                 goto bail;
313         }
314
315         alloc_rec = ocfs2_find_smallest_chain(cl);
316
317         /* setup the group */
318         bg_blkno = ocfs2_clusters_to_blocks(osb->sb, bit_off);
319         mlog(0, "new descriptor, record %u, at block %llu\n",
320              alloc_rec, (unsigned long long)bg_blkno);
321
322         bg_bh = sb_getblk(osb->sb, bg_blkno);
323         if (!bg_bh) {
324                 status = -EIO;
325                 mlog_errno(status);
326                 goto bail;
327         }
328         ocfs2_set_new_buffer_uptodate(alloc_inode, bg_bh);
329
330         status = ocfs2_block_group_fill(handle,
331                                         alloc_inode,
332                                         bg_bh,
333                                         bg_blkno,
334                                         alloc_rec,
335                                         cl);
336         if (status < 0) {
337                 mlog_errno(status);
338                 goto bail;
339         }
340
341         bg = (struct ocfs2_group_desc *) bg_bh->b_data;
342
343         status = ocfs2_journal_access(handle, alloc_inode,
344                                       bh, OCFS2_JOURNAL_ACCESS_WRITE);
345         if (status < 0) {
346                 mlog_errno(status);
347                 goto bail;
348         }
349
350         le32_add_cpu(&cl->cl_recs[alloc_rec].c_free,
351                      le16_to_cpu(bg->bg_free_bits_count));
352         le32_add_cpu(&cl->cl_recs[alloc_rec].c_total, le16_to_cpu(bg->bg_bits));
353         cl->cl_recs[alloc_rec].c_blkno  = cpu_to_le64(bg_blkno);
354         if (le16_to_cpu(cl->cl_next_free_rec) < le16_to_cpu(cl->cl_count))
355                 le16_add_cpu(&cl->cl_next_free_rec, 1);
356
357         le32_add_cpu(&fe->id1.bitmap1.i_used, le16_to_cpu(bg->bg_bits) -
358                                         le16_to_cpu(bg->bg_free_bits_count));
359         le32_add_cpu(&fe->id1.bitmap1.i_total, le16_to_cpu(bg->bg_bits));
360         le32_add_cpu(&fe->i_clusters, le16_to_cpu(cl->cl_cpg));
361
362         status = ocfs2_journal_dirty(handle, bh);
363         if (status < 0) {
364                 mlog_errno(status);
365                 goto bail;
366         }
367
368         spin_lock(&OCFS2_I(alloc_inode)->ip_lock);
369         OCFS2_I(alloc_inode)->ip_clusters = le32_to_cpu(fe->i_clusters);
370         fe->i_size = cpu_to_le64(ocfs2_clusters_to_bytes(alloc_inode->i_sb,
371                                              le32_to_cpu(fe->i_clusters)));
372         spin_unlock(&OCFS2_I(alloc_inode)->ip_lock);
373         i_size_write(alloc_inode, le64_to_cpu(fe->i_size));
374         alloc_inode->i_blocks = ocfs2_inode_sector_count(alloc_inode);
375
376         status = 0;
377 bail:
378         if (handle)
379                 ocfs2_commit_trans(osb, handle);
380
381         if (ac)
382                 ocfs2_free_alloc_context(ac);
383
384         if (bg_bh)
385                 brelse(bg_bh);
386
387         mlog_exit(status);
388         return status;
389 }
390
391 static int ocfs2_reserve_suballoc_bits(struct ocfs2_super *osb,
392                                        struct ocfs2_alloc_context *ac,
393                                        int type,
394                                        u32 slot)
395 {
396         int status;
397         u32 bits_wanted = ac->ac_bits_wanted;
398         struct inode *alloc_inode;
399         struct buffer_head *bh = NULL;
400         struct ocfs2_dinode *fe;
401         u32 free_bits;
402
403         mlog_entry_void();
404
405         alloc_inode = ocfs2_get_system_file_inode(osb, type, slot);
406         if (!alloc_inode) {
407                 mlog_errno(-EINVAL);
408                 return -EINVAL;
409         }
410
411         mutex_lock(&alloc_inode->i_mutex);
412
413         status = ocfs2_inode_lock(alloc_inode, &bh, 1);
414         if (status < 0) {
415                 mutex_unlock(&alloc_inode->i_mutex);
416                 iput(alloc_inode);
417
418                 mlog_errno(status);
419                 return status;
420         }
421
422         ac->ac_inode = alloc_inode;
423
424         fe = (struct ocfs2_dinode *) bh->b_data;
425         if (!OCFS2_IS_VALID_DINODE(fe)) {
426                 OCFS2_RO_ON_INVALID_DINODE(alloc_inode->i_sb, fe);
427                 status = -EIO;
428                 goto bail;
429         }
430         if (!(fe->i_flags & cpu_to_le32(OCFS2_CHAIN_FL))) {
431                 ocfs2_error(alloc_inode->i_sb, "Invalid chain allocator %llu",
432                             (unsigned long long)le64_to_cpu(fe->i_blkno));
433                 status = -EIO;
434                 goto bail;
435         }
436
437         free_bits = le32_to_cpu(fe->id1.bitmap1.i_total) -
438                 le32_to_cpu(fe->id1.bitmap1.i_used);
439
440         if (bits_wanted > free_bits) {
441                 /* cluster bitmap never grows */
442                 if (ocfs2_is_cluster_bitmap(alloc_inode)) {
443                         mlog(0, "Disk Full: wanted=%u, free_bits=%u\n",
444                              bits_wanted, free_bits);
445                         status = -ENOSPC;
446                         goto bail;
447                 }
448
449                 status = ocfs2_block_group_alloc(osb, alloc_inode, bh);
450                 if (status < 0) {
451                         if (status != -ENOSPC)
452                                 mlog_errno(status);
453                         goto bail;
454                 }
455                 atomic_inc(&osb->alloc_stats.bg_extends);
456
457                 /* You should never ask for this much metadata */
458                 BUG_ON(bits_wanted >
459                        (le32_to_cpu(fe->id1.bitmap1.i_total)
460                         - le32_to_cpu(fe->id1.bitmap1.i_used)));
461         }
462
463         get_bh(bh);
464         ac->ac_bh = bh;
465 bail:
466         if (bh)
467                 brelse(bh);
468
469         mlog_exit(status);
470         return status;
471 }
472
473 int ocfs2_reserve_new_metadata(struct ocfs2_super *osb,
474                                struct ocfs2_dinode *fe,
475                                struct ocfs2_alloc_context **ac)
476 {
477         int status;
478         u32 slot;
479
480         *ac = kzalloc(sizeof(struct ocfs2_alloc_context), GFP_KERNEL);
481         if (!(*ac)) {
482                 status = -ENOMEM;
483                 mlog_errno(status);
484                 goto bail;
485         }
486
487         (*ac)->ac_bits_wanted = ocfs2_extend_meta_needed(fe);
488         (*ac)->ac_which = OCFS2_AC_USE_META;
489         slot = osb->slot_num;
490         (*ac)->ac_group_search = ocfs2_block_group_search;
491
492         status = ocfs2_reserve_suballoc_bits(osb, (*ac),
493                                              EXTENT_ALLOC_SYSTEM_INODE, slot);
494         if (status < 0) {
495                 if (status != -ENOSPC)
496                         mlog_errno(status);
497                 goto bail;
498         }
499
500         status = 0;
501 bail:
502         if ((status < 0) && *ac) {
503                 ocfs2_free_alloc_context(*ac);
504                 *ac = NULL;
505         }
506
507         mlog_exit(status);
508         return status;
509 }
510
511 int ocfs2_reserve_new_inode(struct ocfs2_super *osb,
512                             struct ocfs2_alloc_context **ac)
513 {
514         int status;
515
516         *ac = kzalloc(sizeof(struct ocfs2_alloc_context), GFP_KERNEL);
517         if (!(*ac)) {
518                 status = -ENOMEM;
519                 mlog_errno(status);
520                 goto bail;
521         }
522
523         (*ac)->ac_bits_wanted = 1;
524         (*ac)->ac_which = OCFS2_AC_USE_INODE;
525
526         (*ac)->ac_group_search = ocfs2_block_group_search;
527
528         status = ocfs2_reserve_suballoc_bits(osb, *ac,
529                                              INODE_ALLOC_SYSTEM_INODE,
530                                              osb->slot_num);
531         if (status < 0) {
532                 if (status != -ENOSPC)
533                         mlog_errno(status);
534                 goto bail;
535         }
536
537         status = 0;
538 bail:
539         if ((status < 0) && *ac) {
540                 ocfs2_free_alloc_context(*ac);
541                 *ac = NULL;
542         }
543
544         mlog_exit(status);
545         return status;
546 }
547
548 /* local alloc code has to do the same thing, so rather than do this
549  * twice.. */
550 int ocfs2_reserve_cluster_bitmap_bits(struct ocfs2_super *osb,
551                                       struct ocfs2_alloc_context *ac)
552 {
553         int status;
554
555         ac->ac_which = OCFS2_AC_USE_MAIN;
556         ac->ac_group_search = ocfs2_cluster_group_search;
557
558         status = ocfs2_reserve_suballoc_bits(osb, ac,
559                                              GLOBAL_BITMAP_SYSTEM_INODE,
560                                              OCFS2_INVALID_SLOT);
561         if (status < 0 && status != -ENOSPC) {
562                 mlog_errno(status);
563                 goto bail;
564         }
565
566 bail:
567         return status;
568 }
569
570 /* Callers don't need to care which bitmap (local alloc or main) to
571  * use so we figure it out for them, but unfortunately this clutters
572  * things a bit. */
573 int ocfs2_reserve_clusters(struct ocfs2_super *osb,
574                            u32 bits_wanted,
575                            struct ocfs2_alloc_context **ac)
576 {
577         int status;
578
579         mlog_entry_void();
580
581         *ac = kzalloc(sizeof(struct ocfs2_alloc_context), GFP_KERNEL);
582         if (!(*ac)) {
583                 status = -ENOMEM;
584                 mlog_errno(status);
585                 goto bail;
586         }
587
588         (*ac)->ac_bits_wanted = bits_wanted;
589
590         status = -ENOSPC;
591         if (ocfs2_alloc_should_use_local(osb, bits_wanted)) {
592                 status = ocfs2_reserve_local_alloc_bits(osb,
593                                                         bits_wanted,
594                                                         *ac);
595                 if ((status < 0) && (status != -ENOSPC)) {
596                         mlog_errno(status);
597                         goto bail;
598                 } else if (status == -ENOSPC) {
599                         /* reserve_local_bits will return enospc with
600                          * the local alloc inode still locked, so we
601                          * can change this safely here. */
602                         mlog(0, "Disabling local alloc\n");
603                         /* We set to OCFS2_LA_DISABLED so that umount
604                          * can clean up what's left of the local
605                          * allocation */
606                         osb->local_alloc_state = OCFS2_LA_DISABLED;
607                 }
608         }
609
610         if (status == -ENOSPC) {
611                 status = ocfs2_reserve_cluster_bitmap_bits(osb, *ac);
612                 if (status < 0) {
613                         if (status != -ENOSPC)
614                                 mlog_errno(status);
615                         goto bail;
616                 }
617         }
618
619         status = 0;
620 bail:
621         if ((status < 0) && *ac) {
622                 ocfs2_free_alloc_context(*ac);
623                 *ac = NULL;
624         }
625
626         mlog_exit(status);
627         return status;
628 }
629
630 /*
631  * More or less lifted from ext3. I'll leave their description below:
632  *
633  * "For ext3 allocations, we must not reuse any blocks which are
634  * allocated in the bitmap buffer's "last committed data" copy.  This
635  * prevents deletes from freeing up the page for reuse until we have
636  * committed the delete transaction.
637  *
638  * If we didn't do this, then deleting something and reallocating it as
639  * data would allow the old block to be overwritten before the
640  * transaction committed (because we force data to disk before commit).
641  * This would lead to corruption if we crashed between overwriting the
642  * data and committing the delete.
643  *
644  * @@@ We may want to make this allocation behaviour conditional on
645  * data-writes at some point, and disable it for metadata allocations or
646  * sync-data inodes."
647  *
648  * Note: OCFS2 already does this differently for metadata vs data
649  * allocations, as those bitmaps are separate and undo access is never
650  * called on a metadata group descriptor.
651  */
652 static int ocfs2_test_bg_bit_allocatable(struct buffer_head *bg_bh,
653                                          int nr)
654 {
655         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
656
657         if (ocfs2_test_bit(nr, (unsigned long *)bg->bg_bitmap))
658                 return 0;
659         if (!buffer_jbd(bg_bh) || !bh2jh(bg_bh)->b_committed_data)
660                 return 1;
661
662         bg = (struct ocfs2_group_desc *) bh2jh(bg_bh)->b_committed_data;
663         return !ocfs2_test_bit(nr, (unsigned long *)bg->bg_bitmap);
664 }
665
666 static int ocfs2_block_group_find_clear_bits(struct ocfs2_super *osb,
667                                              struct buffer_head *bg_bh,
668                                              unsigned int bits_wanted,
669                                              unsigned int total_bits,
670                                              u16 *bit_off,
671                                              u16 *bits_found)
672 {
673         void *bitmap;
674         u16 best_offset, best_size;
675         int offset, start, found, status = 0;
676         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
677
678         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
679                 OCFS2_RO_ON_INVALID_GROUP_DESC(osb->sb, bg);
680                 return -EIO;
681         }
682
683         found = start = best_offset = best_size = 0;
684         bitmap = bg->bg_bitmap;
685
686         while((offset = ocfs2_find_next_zero_bit(bitmap, total_bits, start)) != -1) {
687                 if (offset == total_bits)
688                         break;
689
690                 if (!ocfs2_test_bg_bit_allocatable(bg_bh, offset)) {
691                         /* We found a zero, but we can't use it as it
692                          * hasn't been put to disk yet! */
693                         found = 0;
694                         start = offset + 1;
695                 } else if (offset == start) {
696                         /* we found a zero */
697                         found++;
698                         /* move start to the next bit to test */
699                         start++;
700                 } else {
701                         /* got a zero after some ones */
702                         found = 1;
703                         start = offset + 1;
704                 }
705                 if (found > best_size) {
706                         best_size = found;
707                         best_offset = start - found;
708                 }
709                 /* we got everything we needed */
710                 if (found == bits_wanted) {
711                         /* mlog(0, "Found it all!\n"); */
712                         break;
713                 }
714         }
715
716         /* XXX: I think the first clause is equivalent to the second
717          *      - jlbec */
718         if (found == bits_wanted) {
719                 *bit_off = start - found;
720                 *bits_found = found;
721         } else if (best_size) {
722                 *bit_off = best_offset;
723                 *bits_found = best_size;
724         } else {
725                 status = -ENOSPC;
726                 /* No error log here -- see the comment above
727                  * ocfs2_test_bg_bit_allocatable */
728         }
729
730         return status;
731 }
732
733 static inline int ocfs2_block_group_set_bits(handle_t *handle,
734                                              struct inode *alloc_inode,
735                                              struct ocfs2_group_desc *bg,
736                                              struct buffer_head *group_bh,
737                                              unsigned int bit_off,
738                                              unsigned int num_bits)
739 {
740         int status;
741         void *bitmap = bg->bg_bitmap;
742         int journal_type = OCFS2_JOURNAL_ACCESS_WRITE;
743
744         mlog_entry_void();
745
746         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
747                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, bg);
748                 status = -EIO;
749                 goto bail;
750         }
751         BUG_ON(le16_to_cpu(bg->bg_free_bits_count) < num_bits);
752
753         mlog(0, "block_group_set_bits: off = %u, num = %u\n", bit_off,
754              num_bits);
755
756         if (ocfs2_is_cluster_bitmap(alloc_inode))
757                 journal_type = OCFS2_JOURNAL_ACCESS_UNDO;
758
759         status = ocfs2_journal_access(handle,
760                                       alloc_inode,
761                                       group_bh,
762                                       journal_type);
763         if (status < 0) {
764                 mlog_errno(status);
765                 goto bail;
766         }
767
768         le16_add_cpu(&bg->bg_free_bits_count, -num_bits);
769
770         while(num_bits--)
771                 ocfs2_set_bit(bit_off++, bitmap);
772
773         status = ocfs2_journal_dirty(handle,
774                                      group_bh);
775         if (status < 0) {
776                 mlog_errno(status);
777                 goto bail;
778         }
779
780 bail:
781         mlog_exit(status);
782         return status;
783 }
784
785 /* find the one with the most empty bits */
786 static inline u16 ocfs2_find_victim_chain(struct ocfs2_chain_list *cl)
787 {
788         u16 curr, best;
789
790         BUG_ON(!cl->cl_next_free_rec);
791
792         best = curr = 0;
793         while (curr < le16_to_cpu(cl->cl_next_free_rec)) {
794                 if (le32_to_cpu(cl->cl_recs[curr].c_free) >
795                     le32_to_cpu(cl->cl_recs[best].c_free))
796                         best = curr;
797                 curr++;
798         }
799
800         BUG_ON(best >= le16_to_cpu(cl->cl_next_free_rec));
801         return best;
802 }
803
804 static int ocfs2_relink_block_group(handle_t *handle,
805                                     struct inode *alloc_inode,
806                                     struct buffer_head *fe_bh,
807                                     struct buffer_head *bg_bh,
808                                     struct buffer_head *prev_bg_bh,
809                                     u16 chain)
810 {
811         int status;
812         /* there is a really tiny chance the journal calls could fail,
813          * but we wouldn't want inconsistent blocks in *any* case. */
814         u64 fe_ptr, bg_ptr, prev_bg_ptr;
815         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) fe_bh->b_data;
816         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
817         struct ocfs2_group_desc *prev_bg = (struct ocfs2_group_desc *) prev_bg_bh->b_data;
818
819         if (!OCFS2_IS_VALID_DINODE(fe)) {
820                 OCFS2_RO_ON_INVALID_DINODE(alloc_inode->i_sb, fe);
821                 status = -EIO;
822                 goto out;
823         }
824         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
825                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, bg);
826                 status = -EIO;
827                 goto out;
828         }
829         if (!OCFS2_IS_VALID_GROUP_DESC(prev_bg)) {
830                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, prev_bg);
831                 status = -EIO;
832                 goto out;
833         }
834
835         mlog(0, "Suballoc %llu, chain %u, move group %llu to top, prev = %llu\n",
836              (unsigned long long)le64_to_cpu(fe->i_blkno), chain,
837              (unsigned long long)le64_to_cpu(bg->bg_blkno),
838              (unsigned long long)le64_to_cpu(prev_bg->bg_blkno));
839
840         fe_ptr = le64_to_cpu(fe->id2.i_chain.cl_recs[chain].c_blkno);
841         bg_ptr = le64_to_cpu(bg->bg_next_group);
842         prev_bg_ptr = le64_to_cpu(prev_bg->bg_next_group);
843
844         status = ocfs2_journal_access(handle, alloc_inode, prev_bg_bh,
845                                       OCFS2_JOURNAL_ACCESS_WRITE);
846         if (status < 0) {
847                 mlog_errno(status);
848                 goto out_rollback;
849         }
850
851         prev_bg->bg_next_group = bg->bg_next_group;
852
853         status = ocfs2_journal_dirty(handle, prev_bg_bh);
854         if (status < 0) {
855                 mlog_errno(status);
856                 goto out_rollback;
857         }
858
859         status = ocfs2_journal_access(handle, alloc_inode, bg_bh,
860                                       OCFS2_JOURNAL_ACCESS_WRITE);
861         if (status < 0) {
862                 mlog_errno(status);
863                 goto out_rollback;
864         }
865
866         bg->bg_next_group = fe->id2.i_chain.cl_recs[chain].c_blkno;
867
868         status = ocfs2_journal_dirty(handle, bg_bh);
869         if (status < 0) {
870                 mlog_errno(status);
871                 goto out_rollback;
872         }
873
874         status = ocfs2_journal_access(handle, alloc_inode, fe_bh,
875                                       OCFS2_JOURNAL_ACCESS_WRITE);
876         if (status < 0) {
877                 mlog_errno(status);
878                 goto out_rollback;
879         }
880
881         fe->id2.i_chain.cl_recs[chain].c_blkno = bg->bg_blkno;
882
883         status = ocfs2_journal_dirty(handle, fe_bh);
884         if (status < 0) {
885                 mlog_errno(status);
886                 goto out_rollback;
887         }
888
889         status = 0;
890 out_rollback:
891         if (status < 0) {
892                 fe->id2.i_chain.cl_recs[chain].c_blkno = cpu_to_le64(fe_ptr);
893                 bg->bg_next_group = cpu_to_le64(bg_ptr);
894                 prev_bg->bg_next_group = cpu_to_le64(prev_bg_ptr);
895         }
896 out:
897         mlog_exit(status);
898         return status;
899 }
900
901 static inline int ocfs2_block_group_reasonably_empty(struct ocfs2_group_desc *bg,
902                                                      u32 wanted)
903 {
904         return le16_to_cpu(bg->bg_free_bits_count) > wanted;
905 }
906
907 /* return 0 on success, -ENOSPC to keep searching and any other < 0
908  * value on error. */
909 static int ocfs2_cluster_group_search(struct inode *inode,
910                                       struct buffer_head *group_bh,
911                                       u32 bits_wanted, u32 min_bits,
912                                       u16 *bit_off, u16 *bits_found)
913 {
914         int search = -ENOSPC;
915         int ret;
916         struct ocfs2_group_desc *gd = (struct ocfs2_group_desc *) group_bh->b_data;
917         u16 tmp_off, tmp_found;
918         unsigned int max_bits, gd_cluster_off;
919
920         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
921
922         if (gd->bg_free_bits_count) {
923                 max_bits = le16_to_cpu(gd->bg_bits);
924
925                 /* Tail groups in cluster bitmaps which aren't cpg
926                  * aligned are prone to partial extention by a failed
927                  * fs resize. If the file system resize never got to
928                  * update the dinode cluster count, then we don't want
929                  * to trust any clusters past it, regardless of what
930                  * the group descriptor says. */
931                 gd_cluster_off = ocfs2_blocks_to_clusters(inode->i_sb,
932                                                           le64_to_cpu(gd->bg_blkno));
933                 if ((gd_cluster_off + max_bits) >
934                     OCFS2_I(inode)->ip_clusters) {
935                         max_bits = OCFS2_I(inode)->ip_clusters - gd_cluster_off;
936                         mlog(0, "Desc %llu, bg_bits %u, clusters %u, use %u\n",
937                              (unsigned long long)le64_to_cpu(gd->bg_blkno),
938                              le16_to_cpu(gd->bg_bits),
939                              OCFS2_I(inode)->ip_clusters, max_bits);
940                 }
941
942                 ret = ocfs2_block_group_find_clear_bits(OCFS2_SB(inode->i_sb),
943                                                         group_bh, bits_wanted,
944                                                         max_bits,
945                                                         &tmp_off, &tmp_found);
946                 if (ret)
947                         return ret;
948
949                 /* ocfs2_block_group_find_clear_bits() might
950                  * return success, but we still want to return
951                  * -ENOSPC unless it found the minimum number
952                  * of bits. */
953                 if (min_bits <= tmp_found) {
954                         *bit_off = tmp_off;
955                         *bits_found = tmp_found;
956                         search = 0; /* success */
957                 }
958         }
959
960         return search;
961 }
962
963 static int ocfs2_block_group_search(struct inode *inode,
964                                     struct buffer_head *group_bh,
965                                     u32 bits_wanted, u32 min_bits,
966                                     u16 *bit_off, u16 *bits_found)
967 {
968         int ret = -ENOSPC;
969         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) group_bh->b_data;
970
971         BUG_ON(min_bits != 1);
972         BUG_ON(ocfs2_is_cluster_bitmap(inode));
973
974         if (bg->bg_free_bits_count)
975                 ret = ocfs2_block_group_find_clear_bits(OCFS2_SB(inode->i_sb),
976                                                         group_bh, bits_wanted,
977                                                         le16_to_cpu(bg->bg_bits),
978                                                         bit_off, bits_found);
979
980         return ret;
981 }
982
983 static int ocfs2_alloc_dinode_update_counts(struct inode *inode,
984                                        handle_t *handle,
985                                        struct buffer_head *di_bh,
986                                        u32 num_bits,
987                                        u16 chain)
988 {
989         int ret;
990         u32 tmp_used;
991         struct ocfs2_dinode *di = (struct ocfs2_dinode *) di_bh->b_data;
992         struct ocfs2_chain_list *cl = (struct ocfs2_chain_list *) &di->id2.i_chain;
993
994         ret = ocfs2_journal_access(handle, inode, di_bh,
995                                    OCFS2_JOURNAL_ACCESS_WRITE);
996         if (ret < 0) {
997                 mlog_errno(ret);
998                 goto out;
999         }
1000
1001         tmp_used = le32_to_cpu(di->id1.bitmap1.i_used);
1002         di->id1.bitmap1.i_used = cpu_to_le32(num_bits + tmp_used);
1003         le32_add_cpu(&cl->cl_recs[chain].c_free, -num_bits);
1004
1005         ret = ocfs2_journal_dirty(handle, di_bh);
1006         if (ret < 0)
1007                 mlog_errno(ret);
1008
1009 out:
1010         return ret;
1011 }
1012
1013 static int ocfs2_search_one_group(struct ocfs2_alloc_context *ac,
1014                                   handle_t *handle,
1015                                   u32 bits_wanted,
1016                                   u32 min_bits,
1017                                   u16 *bit_off,
1018                                   unsigned int *num_bits,
1019                                   u64 gd_blkno,
1020                                   u16 *bits_left)
1021 {
1022         int ret;
1023         u16 found;
1024         struct buffer_head *group_bh = NULL;
1025         struct ocfs2_group_desc *gd;
1026         struct inode *alloc_inode = ac->ac_inode;
1027
1028         ret = ocfs2_read_block(OCFS2_SB(alloc_inode->i_sb), gd_blkno,
1029                                &group_bh, OCFS2_BH_CACHED, alloc_inode);
1030         if (ret < 0) {
1031                 mlog_errno(ret);
1032                 return ret;
1033         }
1034
1035         gd = (struct ocfs2_group_desc *) group_bh->b_data;
1036         if (!OCFS2_IS_VALID_GROUP_DESC(gd)) {
1037                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, gd);
1038                 ret = -EIO;
1039                 goto out;
1040         }
1041
1042         ret = ac->ac_group_search(alloc_inode, group_bh, bits_wanted, min_bits,
1043                                   bit_off, &found);
1044         if (ret < 0) {
1045                 if (ret != -ENOSPC)
1046                         mlog_errno(ret);
1047                 goto out;
1048         }
1049
1050         *num_bits = found;
1051
1052         ret = ocfs2_alloc_dinode_update_counts(alloc_inode, handle, ac->ac_bh,
1053                                                *num_bits,
1054                                                le16_to_cpu(gd->bg_chain));
1055         if (ret < 0) {
1056                 mlog_errno(ret);
1057                 goto out;
1058         }
1059
1060         ret = ocfs2_block_group_set_bits(handle, alloc_inode, gd, group_bh,
1061                                          *bit_off, *num_bits);
1062         if (ret < 0)
1063                 mlog_errno(ret);
1064
1065         *bits_left = le16_to_cpu(gd->bg_free_bits_count);
1066
1067 out:
1068         brelse(group_bh);
1069
1070         return ret;
1071 }
1072
1073 static int ocfs2_search_chain(struct ocfs2_alloc_context *ac,
1074                               handle_t *handle,
1075                               u32 bits_wanted,
1076                               u32 min_bits,
1077                               u16 *bit_off,
1078                               unsigned int *num_bits,
1079                               u64 *bg_blkno,
1080                               u16 *bits_left)
1081 {
1082         int status;
1083         u16 chain, tmp_bits;
1084         u32 tmp_used;
1085         u64 next_group;
1086         struct inode *alloc_inode = ac->ac_inode;
1087         struct buffer_head *group_bh = NULL;
1088         struct buffer_head *prev_group_bh = NULL;
1089         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) ac->ac_bh->b_data;
1090         struct ocfs2_chain_list *cl = (struct ocfs2_chain_list *) &fe->id2.i_chain;
1091         struct ocfs2_group_desc *bg;
1092
1093         chain = ac->ac_chain;
1094         mlog(0, "trying to alloc %u bits from chain %u, inode %llu\n",
1095              bits_wanted, chain,
1096              (unsigned long long)OCFS2_I(alloc_inode)->ip_blkno);
1097
1098         status = ocfs2_read_block(OCFS2_SB(alloc_inode->i_sb),
1099                                   le64_to_cpu(cl->cl_recs[chain].c_blkno),
1100                                   &group_bh, OCFS2_BH_CACHED, alloc_inode);
1101         if (status < 0) {
1102                 mlog_errno(status);
1103                 goto bail;
1104         }
1105         bg = (struct ocfs2_group_desc *) group_bh->b_data;
1106         status = ocfs2_check_group_descriptor(alloc_inode->i_sb, fe, bg);
1107         if (status) {
1108                 mlog_errno(status);
1109                 goto bail;
1110         }
1111
1112         status = -ENOSPC;
1113         /* for now, the chain search is a bit simplistic. We just use
1114          * the 1st group with any empty bits. */
1115         while ((status = ac->ac_group_search(alloc_inode, group_bh,
1116                                              bits_wanted, min_bits, bit_off,
1117                                              &tmp_bits)) == -ENOSPC) {
1118                 if (!bg->bg_next_group)
1119                         break;
1120
1121                 if (prev_group_bh) {
1122                         brelse(prev_group_bh);
1123                         prev_group_bh = NULL;
1124                 }
1125                 next_group = le64_to_cpu(bg->bg_next_group);
1126                 prev_group_bh = group_bh;
1127                 group_bh = NULL;
1128                 status = ocfs2_read_block(OCFS2_SB(alloc_inode->i_sb),
1129                                           next_group, &group_bh,
1130                                           OCFS2_BH_CACHED, alloc_inode);
1131                 if (status < 0) {
1132                         mlog_errno(status);
1133                         goto bail;
1134                 }
1135                 bg = (struct ocfs2_group_desc *) group_bh->b_data;
1136                 status = ocfs2_check_group_descriptor(alloc_inode->i_sb, fe, bg);
1137                 if (status) {
1138                         mlog_errno(status);
1139                         goto bail;
1140                 }
1141         }
1142         if (status < 0) {
1143                 if (status != -ENOSPC)
1144                         mlog_errno(status);
1145                 goto bail;
1146         }
1147
1148         mlog(0, "alloc succeeds: we give %u bits from block group %llu\n",
1149              tmp_bits, (unsigned long long)le64_to_cpu(bg->bg_blkno));
1150
1151         *num_bits = tmp_bits;
1152
1153         BUG_ON(*num_bits == 0);
1154
1155         /*
1156          * Keep track of previous block descriptor read. When
1157          * we find a target, if we have read more than X
1158          * number of descriptors, and the target is reasonably
1159          * empty, relink him to top of his chain.
1160          *
1161          * We've read 0 extra blocks and only send one more to
1162          * the transaction, yet the next guy to search has a
1163          * much easier time.
1164          *
1165          * Do this *after* figuring out how many bits we're taking out
1166          * of our target group.
1167          */
1168         if (ac->ac_allow_chain_relink &&
1169             (prev_group_bh) &&
1170             (ocfs2_block_group_reasonably_empty(bg, *num_bits))) {
1171                 status = ocfs2_relink_block_group(handle, alloc_inode,
1172                                                   ac->ac_bh, group_bh,
1173                                                   prev_group_bh, chain);
1174                 if (status < 0) {
1175                         mlog_errno(status);
1176                         goto bail;
1177                 }
1178         }
1179
1180         /* Ok, claim our bits now: set the info on dinode, chainlist
1181          * and then the group */
1182         status = ocfs2_journal_access(handle,
1183                                       alloc_inode,
1184                                       ac->ac_bh,
1185                                       OCFS2_JOURNAL_ACCESS_WRITE);
1186         if (status < 0) {
1187                 mlog_errno(status);
1188                 goto bail;
1189         }
1190
1191         tmp_used = le32_to_cpu(fe->id1.bitmap1.i_used);
1192         fe->id1.bitmap1.i_used = cpu_to_le32(*num_bits + tmp_used);
1193         le32_add_cpu(&cl->cl_recs[chain].c_free, -(*num_bits));
1194
1195         status = ocfs2_journal_dirty(handle,
1196                                      ac->ac_bh);
1197         if (status < 0) {
1198                 mlog_errno(status);
1199                 goto bail;
1200         }
1201
1202         status = ocfs2_block_group_set_bits(handle,
1203                                             alloc_inode,
1204                                             bg,
1205                                             group_bh,
1206                                             *bit_off,
1207                                             *num_bits);
1208         if (status < 0) {
1209                 mlog_errno(status);
1210                 goto bail;
1211         }
1212
1213         mlog(0, "Allocated %u bits from suballocator %llu\n", *num_bits,
1214              (unsigned long long)le64_to_cpu(fe->i_blkno));
1215
1216         *bg_blkno = le64_to_cpu(bg->bg_blkno);
1217         *bits_left = le16_to_cpu(bg->bg_free_bits_count);
1218 bail:
1219         if (group_bh)
1220                 brelse(group_bh);
1221         if (prev_group_bh)
1222                 brelse(prev_group_bh);
1223
1224         mlog_exit(status);
1225         return status;
1226 }
1227
1228 /* will give out up to bits_wanted contiguous bits. */
1229 static int ocfs2_claim_suballoc_bits(struct ocfs2_super *osb,
1230                                      struct ocfs2_alloc_context *ac,
1231                                      handle_t *handle,
1232                                      u32 bits_wanted,
1233                                      u32 min_bits,
1234                                      u16 *bit_off,
1235                                      unsigned int *num_bits,
1236                                      u64 *bg_blkno)
1237 {
1238         int status;
1239         u16 victim, i;
1240         u16 bits_left = 0;
1241         u64 hint_blkno = ac->ac_last_group;
1242         struct ocfs2_chain_list *cl;
1243         struct ocfs2_dinode *fe;
1244
1245         mlog_entry_void();
1246
1247         BUG_ON(ac->ac_bits_given >= ac->ac_bits_wanted);
1248         BUG_ON(bits_wanted > (ac->ac_bits_wanted - ac->ac_bits_given));
1249         BUG_ON(!ac->ac_bh);
1250
1251         fe = (struct ocfs2_dinode *) ac->ac_bh->b_data;
1252         if (!OCFS2_IS_VALID_DINODE(fe)) {
1253                 OCFS2_RO_ON_INVALID_DINODE(osb->sb, fe);
1254                 status = -EIO;
1255                 goto bail;
1256         }
1257         if (le32_to_cpu(fe->id1.bitmap1.i_used) >=
1258             le32_to_cpu(fe->id1.bitmap1.i_total)) {
1259                 ocfs2_error(osb->sb, "Chain allocator dinode %llu has %u used "
1260                             "bits but only %u total.",
1261                             (unsigned long long)le64_to_cpu(fe->i_blkno),
1262                             le32_to_cpu(fe->id1.bitmap1.i_used),
1263                             le32_to_cpu(fe->id1.bitmap1.i_total));
1264                 status = -EIO;
1265                 goto bail;
1266         }
1267
1268         if (hint_blkno) {
1269                 /* Attempt to short-circuit the usual search mechanism
1270                  * by jumping straight to the most recently used
1271                  * allocation group. This helps us mantain some
1272                  * contiguousness across allocations. */
1273                 status = ocfs2_search_one_group(ac, handle, bits_wanted,
1274                                                 min_bits, bit_off, num_bits,
1275                                                 hint_blkno, &bits_left);
1276                 if (!status) {
1277                         /* Be careful to update *bg_blkno here as the
1278                          * caller is expecting it to be filled in, and
1279                          * ocfs2_search_one_group() won't do that for
1280                          * us. */
1281                         *bg_blkno = hint_blkno;
1282                         goto set_hint;
1283                 }
1284                 if (status < 0 && status != -ENOSPC) {
1285                         mlog_errno(status);
1286                         goto bail;
1287                 }
1288         }
1289
1290         cl = (struct ocfs2_chain_list *) &fe->id2.i_chain;
1291
1292         victim = ocfs2_find_victim_chain(cl);
1293         ac->ac_chain = victim;
1294         ac->ac_allow_chain_relink = 1;
1295
1296         status = ocfs2_search_chain(ac, handle, bits_wanted, min_bits, bit_off,
1297                                     num_bits, bg_blkno, &bits_left);
1298         if (!status)
1299                 goto set_hint;
1300         if (status < 0 && status != -ENOSPC) {
1301                 mlog_errno(status);
1302                 goto bail;
1303         }
1304
1305         mlog(0, "Search of victim chain %u came up with nothing, "
1306              "trying all chains now.\n", victim);
1307
1308         /* If we didn't pick a good victim, then just default to
1309          * searching each chain in order. Don't allow chain relinking
1310          * because we only calculate enough journal credits for one
1311          * relink per alloc. */
1312         ac->ac_allow_chain_relink = 0;
1313         for (i = 0; i < le16_to_cpu(cl->cl_next_free_rec); i ++) {
1314                 if (i == victim)
1315                         continue;
1316                 if (!cl->cl_recs[i].c_free)
1317                         continue;
1318
1319                 ac->ac_chain = i;
1320                 status = ocfs2_search_chain(ac, handle, bits_wanted, min_bits,
1321                                             bit_off, num_bits, bg_blkno,
1322                                             &bits_left);
1323                 if (!status)
1324                         break;
1325                 if (status < 0 && status != -ENOSPC) {
1326                         mlog_errno(status);
1327                         goto bail;
1328                 }
1329         }
1330
1331 set_hint:
1332         if (status != -ENOSPC) {
1333                 /* If the next search of this group is not likely to
1334                  * yield a suitable extent, then we reset the last
1335                  * group hint so as to not waste a disk read */
1336                 if (bits_left < min_bits)
1337                         ac->ac_last_group = 0;
1338                 else
1339                         ac->ac_last_group = *bg_blkno;
1340         }
1341
1342 bail:
1343         mlog_exit(status);
1344         return status;
1345 }
1346
1347 int ocfs2_claim_metadata(struct ocfs2_super *osb,
1348                          handle_t *handle,
1349                          struct ocfs2_alloc_context *ac,
1350                          u32 bits_wanted,
1351                          u16 *suballoc_bit_start,
1352                          unsigned int *num_bits,
1353                          u64 *blkno_start)
1354 {
1355         int status;
1356         u64 bg_blkno;
1357
1358         BUG_ON(!ac);
1359         BUG_ON(ac->ac_bits_wanted < (ac->ac_bits_given + bits_wanted));
1360         BUG_ON(ac->ac_which != OCFS2_AC_USE_META);
1361
1362         status = ocfs2_claim_suballoc_bits(osb,
1363                                            ac,
1364                                            handle,
1365                                            bits_wanted,
1366                                            1,
1367                                            suballoc_bit_start,
1368                                            num_bits,
1369                                            &bg_blkno);
1370         if (status < 0) {
1371                 mlog_errno(status);
1372                 goto bail;
1373         }
1374         atomic_inc(&osb->alloc_stats.bg_allocs);
1375
1376         *blkno_start = bg_blkno + (u64) *suballoc_bit_start;
1377         ac->ac_bits_given += (*num_bits);
1378         status = 0;
1379 bail:
1380         mlog_exit(status);
1381         return status;
1382 }
1383
1384 int ocfs2_claim_new_inode(struct ocfs2_super *osb,
1385                           handle_t *handle,
1386                           struct ocfs2_alloc_context *ac,
1387                           u16 *suballoc_bit,
1388                           u64 *fe_blkno)
1389 {
1390         int status;
1391         unsigned int num_bits;
1392         u64 bg_blkno;
1393
1394         mlog_entry_void();
1395
1396         BUG_ON(!ac);
1397         BUG_ON(ac->ac_bits_given != 0);
1398         BUG_ON(ac->ac_bits_wanted != 1);
1399         BUG_ON(ac->ac_which != OCFS2_AC_USE_INODE);
1400
1401         status = ocfs2_claim_suballoc_bits(osb,
1402                                            ac,
1403                                            handle,
1404                                            1,
1405                                            1,
1406                                            suballoc_bit,
1407                                            &num_bits,
1408                                            &bg_blkno);
1409         if (status < 0) {
1410                 mlog_errno(status);
1411                 goto bail;
1412         }
1413         atomic_inc(&osb->alloc_stats.bg_allocs);
1414
1415         BUG_ON(num_bits != 1);
1416
1417         *fe_blkno = bg_blkno + (u64) (*suballoc_bit);
1418         ac->ac_bits_given++;
1419         status = 0;
1420 bail:
1421         mlog_exit(status);
1422         return status;
1423 }
1424
1425 /* translate a group desc. blkno and it's bitmap offset into
1426  * disk cluster offset. */
1427 static inline u32 ocfs2_desc_bitmap_to_cluster_off(struct inode *inode,
1428                                                    u64 bg_blkno,
1429                                                    u16 bg_bit_off)
1430 {
1431         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
1432         u32 cluster = 0;
1433
1434         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
1435
1436         if (bg_blkno != osb->first_cluster_group_blkno)
1437                 cluster = ocfs2_blocks_to_clusters(inode->i_sb, bg_blkno);
1438         cluster += (u32) bg_bit_off;
1439         return cluster;
1440 }
1441
1442 /* given a cluster offset, calculate which block group it belongs to
1443  * and return that block offset. */
1444 u64 ocfs2_which_cluster_group(struct inode *inode, u32 cluster)
1445 {
1446         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
1447         u32 group_no;
1448
1449         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
1450
1451         group_no = cluster / osb->bitmap_cpg;
1452         if (!group_no)
1453                 return osb->first_cluster_group_blkno;
1454         return ocfs2_clusters_to_blocks(inode->i_sb,
1455                                         group_no * osb->bitmap_cpg);
1456 }
1457
1458 /* given the block number of a cluster start, calculate which cluster
1459  * group and descriptor bitmap offset that corresponds to. */
1460 static inline void ocfs2_block_to_cluster_group(struct inode *inode,
1461                                                 u64 data_blkno,
1462                                                 u64 *bg_blkno,
1463                                                 u16 *bg_bit_off)
1464 {
1465         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
1466         u32 data_cluster = ocfs2_blocks_to_clusters(osb->sb, data_blkno);
1467
1468         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
1469
1470         *bg_blkno = ocfs2_which_cluster_group(inode,
1471                                               data_cluster);
1472
1473         if (*bg_blkno == osb->first_cluster_group_blkno)
1474                 *bg_bit_off = (u16) data_cluster;
1475         else
1476                 *bg_bit_off = (u16) ocfs2_blocks_to_clusters(osb->sb,
1477                                                              data_blkno - *bg_blkno);
1478 }
1479
1480 /*
1481  * min_bits - minimum contiguous chunk from this total allocation we
1482  * can handle. set to what we asked for originally for a full
1483  * contig. allocation, set to '1' to indicate we can deal with extents
1484  * of any size.
1485  */
1486 int __ocfs2_claim_clusters(struct ocfs2_super *osb,
1487                            handle_t *handle,
1488                            struct ocfs2_alloc_context *ac,
1489                            u32 min_clusters,
1490                            u32 max_clusters,
1491                            u32 *cluster_start,
1492                            u32 *num_clusters)
1493 {
1494         int status;
1495         unsigned int bits_wanted = max_clusters;
1496         u64 bg_blkno = 0;
1497         u16 bg_bit_off;
1498
1499         mlog_entry_void();
1500
1501         BUG_ON(ac->ac_bits_given >= ac->ac_bits_wanted);
1502
1503         BUG_ON(ac->ac_which != OCFS2_AC_USE_LOCAL
1504                && ac->ac_which != OCFS2_AC_USE_MAIN);
1505
1506         if (ac->ac_which == OCFS2_AC_USE_LOCAL) {
1507                 status = ocfs2_claim_local_alloc_bits(osb,
1508                                                       handle,
1509                                                       ac,
1510                                                       bits_wanted,
1511                                                       cluster_start,
1512                                                       num_clusters);
1513                 if (!status)
1514                         atomic_inc(&osb->alloc_stats.local_data);
1515         } else {
1516                 if (min_clusters > (osb->bitmap_cpg - 1)) {
1517                         /* The only paths asking for contiguousness
1518                          * should know about this already. */
1519                         mlog(ML_ERROR, "minimum allocation requested %u exceeds "
1520                              "group bitmap size %u!\n", min_clusters,
1521                              osb->bitmap_cpg);
1522                         status = -ENOSPC;
1523                         goto bail;
1524                 }
1525                 /* clamp the current request down to a realistic size. */
1526                 if (bits_wanted > (osb->bitmap_cpg - 1))
1527                         bits_wanted = osb->bitmap_cpg - 1;
1528
1529                 status = ocfs2_claim_suballoc_bits(osb,
1530                                                    ac,
1531                                                    handle,
1532                                                    bits_wanted,
1533                                                    min_clusters,
1534                                                    &bg_bit_off,
1535                                                    num_clusters,
1536                                                    &bg_blkno);
1537                 if (!status) {
1538                         *cluster_start =
1539                                 ocfs2_desc_bitmap_to_cluster_off(ac->ac_inode,
1540                                                                  bg_blkno,
1541                                                                  bg_bit_off);
1542                         atomic_inc(&osb->alloc_stats.bitmap_data);
1543                 }
1544         }
1545         if (status < 0) {
1546                 if (status != -ENOSPC)
1547                         mlog_errno(status);
1548                 goto bail;
1549         }
1550
1551         ac->ac_bits_given += *num_clusters;
1552
1553 bail:
1554         mlog_exit(status);
1555         return status;
1556 }
1557
1558 int ocfs2_claim_clusters(struct ocfs2_super *osb,
1559                          handle_t *handle,
1560                          struct ocfs2_alloc_context *ac,
1561                          u32 min_clusters,
1562                          u32 *cluster_start,
1563                          u32 *num_clusters)
1564 {
1565         unsigned int bits_wanted = ac->ac_bits_wanted - ac->ac_bits_given;
1566
1567         return __ocfs2_claim_clusters(osb, handle, ac, min_clusters,
1568                                       bits_wanted, cluster_start, num_clusters);
1569 }
1570
1571 static inline int ocfs2_block_group_clear_bits(handle_t *handle,
1572                                                struct inode *alloc_inode,
1573                                                struct ocfs2_group_desc *bg,
1574                                                struct buffer_head *group_bh,
1575                                                unsigned int bit_off,
1576                                                unsigned int num_bits)
1577 {
1578         int status;
1579         unsigned int tmp;
1580         int journal_type = OCFS2_JOURNAL_ACCESS_WRITE;
1581         struct ocfs2_group_desc *undo_bg = NULL;
1582
1583         mlog_entry_void();
1584
1585         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
1586                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, bg);
1587                 status = -EIO;
1588                 goto bail;
1589         }
1590
1591         mlog(0, "off = %u, num = %u\n", bit_off, num_bits);
1592
1593         if (ocfs2_is_cluster_bitmap(alloc_inode))
1594                 journal_type = OCFS2_JOURNAL_ACCESS_UNDO;
1595
1596         status = ocfs2_journal_access(handle, alloc_inode, group_bh,
1597                                       journal_type);
1598         if (status < 0) {
1599                 mlog_errno(status);
1600                 goto bail;
1601         }
1602
1603         if (ocfs2_is_cluster_bitmap(alloc_inode))
1604                 undo_bg = (struct ocfs2_group_desc *) bh2jh(group_bh)->b_committed_data;
1605
1606         tmp = num_bits;
1607         while(tmp--) {
1608                 ocfs2_clear_bit((bit_off + tmp),
1609                                 (unsigned long *) bg->bg_bitmap);
1610                 if (ocfs2_is_cluster_bitmap(alloc_inode))
1611                         ocfs2_set_bit(bit_off + tmp,
1612                                       (unsigned long *) undo_bg->bg_bitmap);
1613         }
1614         le16_add_cpu(&bg->bg_free_bits_count, num_bits);
1615
1616         status = ocfs2_journal_dirty(handle, group_bh);
1617         if (status < 0)
1618                 mlog_errno(status);
1619 bail:
1620         return status;
1621 }
1622
1623 /*
1624  * expects the suballoc inode to already be locked.
1625  */
1626 int ocfs2_free_suballoc_bits(handle_t *handle,
1627                              struct inode *alloc_inode,
1628                              struct buffer_head *alloc_bh,
1629                              unsigned int start_bit,
1630                              u64 bg_blkno,
1631                              unsigned int count)
1632 {
1633         int status = 0;
1634         u32 tmp_used;
1635         struct ocfs2_super *osb = OCFS2_SB(alloc_inode->i_sb);
1636         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) alloc_bh->b_data;
1637         struct ocfs2_chain_list *cl = &fe->id2.i_chain;
1638         struct buffer_head *group_bh = NULL;
1639         struct ocfs2_group_desc *group;
1640
1641         mlog_entry_void();
1642
1643         if (!OCFS2_IS_VALID_DINODE(fe)) {
1644                 OCFS2_RO_ON_INVALID_DINODE(alloc_inode->i_sb, fe);
1645                 status = -EIO;
1646                 goto bail;
1647         }
1648         BUG_ON((count + start_bit) > ocfs2_bits_per_group(cl));
1649
1650         mlog(0, "%llu: freeing %u bits from group %llu, starting at %u\n",
1651              (unsigned long long)OCFS2_I(alloc_inode)->ip_blkno, count,
1652              (unsigned long long)bg_blkno, start_bit);
1653
1654         status = ocfs2_read_block(osb, bg_blkno, &group_bh, OCFS2_BH_CACHED,
1655                                   alloc_inode);
1656         if (status < 0) {
1657                 mlog_errno(status);
1658                 goto bail;
1659         }
1660
1661         group = (struct ocfs2_group_desc *) group_bh->b_data;
1662         status = ocfs2_check_group_descriptor(alloc_inode->i_sb, fe, group);
1663         if (status) {
1664                 mlog_errno(status);
1665                 goto bail;
1666         }
1667         BUG_ON((count + start_bit) > le16_to_cpu(group->bg_bits));
1668
1669         status = ocfs2_block_group_clear_bits(handle, alloc_inode,
1670                                               group, group_bh,
1671                                               start_bit, count);
1672         if (status < 0) {
1673                 mlog_errno(status);
1674                 goto bail;
1675         }
1676
1677         status = ocfs2_journal_access(handle, alloc_inode, alloc_bh,
1678                                       OCFS2_JOURNAL_ACCESS_WRITE);
1679         if (status < 0) {
1680                 mlog_errno(status);
1681                 goto bail;
1682         }
1683
1684         le32_add_cpu(&cl->cl_recs[le16_to_cpu(group->bg_chain)].c_free,
1685                      count);
1686         tmp_used = le32_to_cpu(fe->id1.bitmap1.i_used);
1687         fe->id1.bitmap1.i_used = cpu_to_le32(tmp_used - count);
1688
1689         status = ocfs2_journal_dirty(handle, alloc_bh);
1690         if (status < 0) {
1691                 mlog_errno(status);
1692                 goto bail;
1693         }
1694
1695 bail:
1696         if (group_bh)
1697                 brelse(group_bh);
1698
1699         mlog_exit(status);
1700         return status;
1701 }
1702
1703 int ocfs2_free_dinode(handle_t *handle,
1704                       struct inode *inode_alloc_inode,
1705                       struct buffer_head *inode_alloc_bh,
1706                       struct ocfs2_dinode *di)
1707 {
1708         u64 blk = le64_to_cpu(di->i_blkno);
1709         u16 bit = le16_to_cpu(di->i_suballoc_bit);
1710         u64 bg_blkno = ocfs2_which_suballoc_group(blk, bit);
1711
1712         return ocfs2_free_suballoc_bits(handle, inode_alloc_inode,
1713                                         inode_alloc_bh, bit, bg_blkno, 1);
1714 }
1715
1716 int ocfs2_free_clusters(handle_t *handle,
1717                        struct inode *bitmap_inode,
1718                        struct buffer_head *bitmap_bh,
1719                        u64 start_blk,
1720                        unsigned int num_clusters)
1721 {
1722         int status;
1723         u16 bg_start_bit;
1724         u64 bg_blkno;
1725         struct ocfs2_dinode *fe;
1726
1727         /* You can't ever have a contiguous set of clusters
1728          * bigger than a block group bitmap so we never have to worry
1729          * about looping on them. */
1730
1731         mlog_entry_void();
1732
1733         /* This is expensive. We can safely remove once this stuff has
1734          * gotten tested really well. */
1735         BUG_ON(start_blk != ocfs2_clusters_to_blocks(bitmap_inode->i_sb, ocfs2_blocks_to_clusters(bitmap_inode->i_sb, start_blk)));
1736
1737         fe = (struct ocfs2_dinode *) bitmap_bh->b_data;
1738
1739         ocfs2_block_to_cluster_group(bitmap_inode, start_blk, &bg_blkno,
1740                                      &bg_start_bit);
1741
1742         mlog(0, "want to free %u clusters starting at block %llu\n",
1743              num_clusters, (unsigned long long)start_blk);
1744         mlog(0, "bg_blkno = %llu, bg_start_bit = %u\n",
1745              (unsigned long long)bg_blkno, bg_start_bit);
1746
1747         status = ocfs2_free_suballoc_bits(handle, bitmap_inode, bitmap_bh,
1748                                           bg_start_bit, bg_blkno,
1749                                           num_clusters);
1750         if (status < 0)
1751                 mlog_errno(status);
1752
1753         mlog_exit(status);
1754         return status;
1755 }
1756
1757 static inline void ocfs2_debug_bg(struct ocfs2_group_desc *bg)
1758 {
1759         printk("Block Group:\n");
1760         printk("bg_signature:       %s\n", bg->bg_signature);
1761         printk("bg_size:            %u\n", bg->bg_size);
1762         printk("bg_bits:            %u\n", bg->bg_bits);
1763         printk("bg_free_bits_count: %u\n", bg->bg_free_bits_count);
1764         printk("bg_chain:           %u\n", bg->bg_chain);
1765         printk("bg_generation:      %u\n", le32_to_cpu(bg->bg_generation));
1766         printk("bg_next_group:      %llu\n",
1767                (unsigned long long)bg->bg_next_group);
1768         printk("bg_parent_dinode:   %llu\n",
1769                (unsigned long long)bg->bg_parent_dinode);
1770         printk("bg_blkno:           %llu\n",
1771                (unsigned long long)bg->bg_blkno);
1772 }
1773
1774 static inline void ocfs2_debug_suballoc_inode(struct ocfs2_dinode *fe)
1775 {
1776         int i;
1777
1778         printk("Suballoc Inode %llu:\n", (unsigned long long)fe->i_blkno);
1779         printk("i_signature:                  %s\n", fe->i_signature);
1780         printk("i_size:                       %llu\n",
1781                (unsigned long long)fe->i_size);
1782         printk("i_clusters:                   %u\n", fe->i_clusters);
1783         printk("i_generation:                 %u\n",
1784                le32_to_cpu(fe->i_generation));
1785         printk("id1.bitmap1.i_used:           %u\n",
1786                le32_to_cpu(fe->id1.bitmap1.i_used));
1787         printk("id1.bitmap1.i_total:          %u\n",
1788                le32_to_cpu(fe->id1.bitmap1.i_total));
1789         printk("id2.i_chain.cl_cpg:           %u\n", fe->id2.i_chain.cl_cpg);
1790         printk("id2.i_chain.cl_bpc:           %u\n", fe->id2.i_chain.cl_bpc);
1791         printk("id2.i_chain.cl_count:         %u\n", fe->id2.i_chain.cl_count);
1792         printk("id2.i_chain.cl_next_free_rec: %u\n",
1793                fe->id2.i_chain.cl_next_free_rec);
1794         for(i = 0; i < fe->id2.i_chain.cl_next_free_rec; i++) {
1795                 printk("fe->id2.i_chain.cl_recs[%d].c_free:  %u\n", i,
1796                        fe->id2.i_chain.cl_recs[i].c_free);
1797                 printk("fe->id2.i_chain.cl_recs[%d].c_total: %u\n", i,
1798                        fe->id2.i_chain.cl_recs[i].c_total);
1799                 printk("fe->id2.i_chain.cl_recs[%d].c_blkno: %llu\n", i,
1800                        (unsigned long long)fe->id2.i_chain.cl_recs[i].c_blkno);
1801         }
1802 }