Merge branch 'linus' into oprofile-v2
[linux-2.6] / fs / ocfs2 / alloc.c
1 /* -*- mode: c; c-basic-offset: 8; -*-
2  * vim: noexpandtab sw=8 ts=8 sts=0:
3  *
4  * alloc.c
5  *
6  * Extent allocs and frees
7  *
8  * Copyright (C) 2002, 2004 Oracle.  All rights reserved.
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public
21  * License along with this program; if not, write to the
22  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
23  * Boston, MA 021110-1307, USA.
24  */
25
26 #include <linux/fs.h>
27 #include <linux/types.h>
28 #include <linux/slab.h>
29 #include <linux/highmem.h>
30 #include <linux/swap.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 "aops.h"
39 #include "dlmglue.h"
40 #include "extent_map.h"
41 #include "inode.h"
42 #include "journal.h"
43 #include "localalloc.h"
44 #include "suballoc.h"
45 #include "sysfile.h"
46 #include "file.h"
47 #include "super.h"
48 #include "uptodate.h"
49
50 #include "buffer_head_io.h"
51
52 static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc);
53 static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt,
54                                          struct ocfs2_extent_block *eb);
55
56 /*
57  * Structures which describe a path through a btree, and functions to
58  * manipulate them.
59  *
60  * The idea here is to be as generic as possible with the tree
61  * manipulation code.
62  */
63 struct ocfs2_path_item {
64         struct buffer_head              *bh;
65         struct ocfs2_extent_list        *el;
66 };
67
68 #define OCFS2_MAX_PATH_DEPTH    5
69
70 struct ocfs2_path {
71         int                     p_tree_depth;
72         struct ocfs2_path_item  p_node[OCFS2_MAX_PATH_DEPTH];
73 };
74
75 #define path_root_bh(_path) ((_path)->p_node[0].bh)
76 #define path_root_el(_path) ((_path)->p_node[0].el)
77 #define path_leaf_bh(_path) ((_path)->p_node[(_path)->p_tree_depth].bh)
78 #define path_leaf_el(_path) ((_path)->p_node[(_path)->p_tree_depth].el)
79 #define path_num_items(_path) ((_path)->p_tree_depth + 1)
80
81 /*
82  * Reset the actual path elements so that we can re-use the structure
83  * to build another path. Generally, this involves freeing the buffer
84  * heads.
85  */
86 static void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root)
87 {
88         int i, start = 0, depth = 0;
89         struct ocfs2_path_item *node;
90
91         if (keep_root)
92                 start = 1;
93
94         for(i = start; i < path_num_items(path); i++) {
95                 node = &path->p_node[i];
96
97                 brelse(node->bh);
98                 node->bh = NULL;
99                 node->el = NULL;
100         }
101
102         /*
103          * Tree depth may change during truncate, or insert. If we're
104          * keeping the root extent list, then make sure that our path
105          * structure reflects the proper depth.
106          */
107         if (keep_root)
108                 depth = le16_to_cpu(path_root_el(path)->l_tree_depth);
109
110         path->p_tree_depth = depth;
111 }
112
113 static void ocfs2_free_path(struct ocfs2_path *path)
114 {
115         if (path) {
116                 ocfs2_reinit_path(path, 0);
117                 kfree(path);
118         }
119 }
120
121 /*
122  * All the elements of src into dest. After this call, src could be freed
123  * without affecting dest.
124  *
125  * Both paths should have the same root. Any non-root elements of dest
126  * will be freed.
127  */
128 static void ocfs2_cp_path(struct ocfs2_path *dest, struct ocfs2_path *src)
129 {
130         int i;
131
132         BUG_ON(path_root_bh(dest) != path_root_bh(src));
133         BUG_ON(path_root_el(dest) != path_root_el(src));
134
135         ocfs2_reinit_path(dest, 1);
136
137         for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
138                 dest->p_node[i].bh = src->p_node[i].bh;
139                 dest->p_node[i].el = src->p_node[i].el;
140
141                 if (dest->p_node[i].bh)
142                         get_bh(dest->p_node[i].bh);
143         }
144 }
145
146 /*
147  * Make the *dest path the same as src and re-initialize src path to
148  * have a root only.
149  */
150 static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src)
151 {
152         int i;
153
154         BUG_ON(path_root_bh(dest) != path_root_bh(src));
155
156         for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
157                 brelse(dest->p_node[i].bh);
158
159                 dest->p_node[i].bh = src->p_node[i].bh;
160                 dest->p_node[i].el = src->p_node[i].el;
161
162                 src->p_node[i].bh = NULL;
163                 src->p_node[i].el = NULL;
164         }
165 }
166
167 /*
168  * Insert an extent block at given index.
169  *
170  * This will not take an additional reference on eb_bh.
171  */
172 static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index,
173                                         struct buffer_head *eb_bh)
174 {
175         struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)eb_bh->b_data;
176
177         /*
178          * Right now, no root bh is an extent block, so this helps
179          * catch code errors with dinode trees. The assertion can be
180          * safely removed if we ever need to insert extent block
181          * structures at the root.
182          */
183         BUG_ON(index == 0);
184
185         path->p_node[index].bh = eb_bh;
186         path->p_node[index].el = &eb->h_list;
187 }
188
189 static struct ocfs2_path *ocfs2_new_path(struct buffer_head *root_bh,
190                                          struct ocfs2_extent_list *root_el)
191 {
192         struct ocfs2_path *path;
193
194         BUG_ON(le16_to_cpu(root_el->l_tree_depth) >= OCFS2_MAX_PATH_DEPTH);
195
196         path = kzalloc(sizeof(*path), GFP_NOFS);
197         if (path) {
198                 path->p_tree_depth = le16_to_cpu(root_el->l_tree_depth);
199                 get_bh(root_bh);
200                 path_root_bh(path) = root_bh;
201                 path_root_el(path) = root_el;
202         }
203
204         return path;
205 }
206
207 /*
208  * Allocate and initialize a new path based on a disk inode tree.
209  */
210 static struct ocfs2_path *ocfs2_new_inode_path(struct buffer_head *di_bh)
211 {
212         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
213         struct ocfs2_extent_list *el = &di->id2.i_list;
214
215         return ocfs2_new_path(di_bh, el);
216 }
217
218 /*
219  * Convenience function to journal all components in a path.
220  */
221 static int ocfs2_journal_access_path(struct inode *inode, handle_t *handle,
222                                      struct ocfs2_path *path)
223 {
224         int i, ret = 0;
225
226         if (!path)
227                 goto out;
228
229         for(i = 0; i < path_num_items(path); i++) {
230                 ret = ocfs2_journal_access(handle, inode, path->p_node[i].bh,
231                                            OCFS2_JOURNAL_ACCESS_WRITE);
232                 if (ret < 0) {
233                         mlog_errno(ret);
234                         goto out;
235                 }
236         }
237
238 out:
239         return ret;
240 }
241
242 /*
243  * Return the index of the extent record which contains cluster #v_cluster.
244  * -1 is returned if it was not found.
245  *
246  * Should work fine on interior and exterior nodes.
247  */
248 int ocfs2_search_extent_list(struct ocfs2_extent_list *el, u32 v_cluster)
249 {
250         int ret = -1;
251         int i;
252         struct ocfs2_extent_rec *rec;
253         u32 rec_end, rec_start, clusters;
254
255         for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) {
256                 rec = &el->l_recs[i];
257
258                 rec_start = le32_to_cpu(rec->e_cpos);
259                 clusters = ocfs2_rec_clusters(el, rec);
260
261                 rec_end = rec_start + clusters;
262
263                 if (v_cluster >= rec_start && v_cluster < rec_end) {
264                         ret = i;
265                         break;
266                 }
267         }
268
269         return ret;
270 }
271
272 enum ocfs2_contig_type {
273         CONTIG_NONE = 0,
274         CONTIG_LEFT,
275         CONTIG_RIGHT,
276         CONTIG_LEFTRIGHT,
277 };
278
279
280 /*
281  * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
282  * ocfs2_extent_contig only work properly against leaf nodes!
283  */
284 static int ocfs2_block_extent_contig(struct super_block *sb,
285                                      struct ocfs2_extent_rec *ext,
286                                      u64 blkno)
287 {
288         u64 blk_end = le64_to_cpu(ext->e_blkno);
289
290         blk_end += ocfs2_clusters_to_blocks(sb,
291                                     le16_to_cpu(ext->e_leaf_clusters));
292
293         return blkno == blk_end;
294 }
295
296 static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left,
297                                   struct ocfs2_extent_rec *right)
298 {
299         u32 left_range;
300
301         left_range = le32_to_cpu(left->e_cpos) +
302                 le16_to_cpu(left->e_leaf_clusters);
303
304         return (left_range == le32_to_cpu(right->e_cpos));
305 }
306
307 static enum ocfs2_contig_type
308         ocfs2_extent_contig(struct inode *inode,
309                             struct ocfs2_extent_rec *ext,
310                             struct ocfs2_extent_rec *insert_rec)
311 {
312         u64 blkno = le64_to_cpu(insert_rec->e_blkno);
313
314         /*
315          * Refuse to coalesce extent records with different flag
316          * fields - we don't want to mix unwritten extents with user
317          * data.
318          */
319         if (ext->e_flags != insert_rec->e_flags)
320                 return CONTIG_NONE;
321
322         if (ocfs2_extents_adjacent(ext, insert_rec) &&
323             ocfs2_block_extent_contig(inode->i_sb, ext, blkno))
324                         return CONTIG_RIGHT;
325
326         blkno = le64_to_cpu(ext->e_blkno);
327         if (ocfs2_extents_adjacent(insert_rec, ext) &&
328             ocfs2_block_extent_contig(inode->i_sb, insert_rec, blkno))
329                 return CONTIG_LEFT;
330
331         return CONTIG_NONE;
332 }
333
334 /*
335  * NOTE: We can have pretty much any combination of contiguousness and
336  * appending.
337  *
338  * The usefulness of APPEND_TAIL is more in that it lets us know that
339  * we'll have to update the path to that leaf.
340  */
341 enum ocfs2_append_type {
342         APPEND_NONE = 0,
343         APPEND_TAIL,
344 };
345
346 enum ocfs2_split_type {
347         SPLIT_NONE = 0,
348         SPLIT_LEFT,
349         SPLIT_RIGHT,
350 };
351
352 struct ocfs2_insert_type {
353         enum ocfs2_split_type   ins_split;
354         enum ocfs2_append_type  ins_appending;
355         enum ocfs2_contig_type  ins_contig;
356         int                     ins_contig_index;
357         int                     ins_tree_depth;
358 };
359
360 struct ocfs2_merge_ctxt {
361         enum ocfs2_contig_type  c_contig_type;
362         int                     c_has_empty_extent;
363         int                     c_split_covers_rec;
364 };
365
366 /*
367  * How many free extents have we got before we need more meta data?
368  */
369 int ocfs2_num_free_extents(struct ocfs2_super *osb,
370                            struct inode *inode,
371                            struct ocfs2_dinode *fe)
372 {
373         int retval;
374         struct ocfs2_extent_list *el;
375         struct ocfs2_extent_block *eb;
376         struct buffer_head *eb_bh = NULL;
377
378         mlog_entry_void();
379
380         if (!OCFS2_IS_VALID_DINODE(fe)) {
381                 OCFS2_RO_ON_INVALID_DINODE(inode->i_sb, fe);
382                 retval = -EIO;
383                 goto bail;
384         }
385
386         if (fe->i_last_eb_blk) {
387                 retval = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk),
388                                           &eb_bh, OCFS2_BH_CACHED, inode);
389                 if (retval < 0) {
390                         mlog_errno(retval);
391                         goto bail;
392                 }
393                 eb = (struct ocfs2_extent_block *) eb_bh->b_data;
394                 el = &eb->h_list;
395         } else
396                 el = &fe->id2.i_list;
397
398         BUG_ON(el->l_tree_depth != 0);
399
400         retval = le16_to_cpu(el->l_count) - le16_to_cpu(el->l_next_free_rec);
401 bail:
402         if (eb_bh)
403                 brelse(eb_bh);
404
405         mlog_exit(retval);
406         return retval;
407 }
408
409 /* expects array to already be allocated
410  *
411  * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
412  * l_count for you
413  */
414 static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb,
415                                      handle_t *handle,
416                                      struct inode *inode,
417                                      int wanted,
418                                      struct ocfs2_alloc_context *meta_ac,
419                                      struct buffer_head *bhs[])
420 {
421         int count, status, i;
422         u16 suballoc_bit_start;
423         u32 num_got;
424         u64 first_blkno;
425         struct ocfs2_extent_block *eb;
426
427         mlog_entry_void();
428
429         count = 0;
430         while (count < wanted) {
431                 status = ocfs2_claim_metadata(osb,
432                                               handle,
433                                               meta_ac,
434                                               wanted - count,
435                                               &suballoc_bit_start,
436                                               &num_got,
437                                               &first_blkno);
438                 if (status < 0) {
439                         mlog_errno(status);
440                         goto bail;
441                 }
442
443                 for(i = count;  i < (num_got + count); i++) {
444                         bhs[i] = sb_getblk(osb->sb, first_blkno);
445                         if (bhs[i] == NULL) {
446                                 status = -EIO;
447                                 mlog_errno(status);
448                                 goto bail;
449                         }
450                         ocfs2_set_new_buffer_uptodate(inode, bhs[i]);
451
452                         status = ocfs2_journal_access(handle, inode, bhs[i],
453                                                       OCFS2_JOURNAL_ACCESS_CREATE);
454                         if (status < 0) {
455                                 mlog_errno(status);
456                                 goto bail;
457                         }
458
459                         memset(bhs[i]->b_data, 0, osb->sb->s_blocksize);
460                         eb = (struct ocfs2_extent_block *) bhs[i]->b_data;
461                         /* Ok, setup the minimal stuff here. */
462                         strcpy(eb->h_signature, OCFS2_EXTENT_BLOCK_SIGNATURE);
463                         eb->h_blkno = cpu_to_le64(first_blkno);
464                         eb->h_fs_generation = cpu_to_le32(osb->fs_generation);
465                         eb->h_suballoc_slot = cpu_to_le16(osb->slot_num);
466                         eb->h_suballoc_bit = cpu_to_le16(suballoc_bit_start);
467                         eb->h_list.l_count =
468                                 cpu_to_le16(ocfs2_extent_recs_per_eb(osb->sb));
469
470                         suballoc_bit_start++;
471                         first_blkno++;
472
473                         /* We'll also be dirtied by the caller, so
474                          * this isn't absolutely necessary. */
475                         status = ocfs2_journal_dirty(handle, bhs[i]);
476                         if (status < 0) {
477                                 mlog_errno(status);
478                                 goto bail;
479                         }
480                 }
481
482                 count += num_got;
483         }
484
485         status = 0;
486 bail:
487         if (status < 0) {
488                 for(i = 0; i < wanted; i++) {
489                         if (bhs[i])
490                                 brelse(bhs[i]);
491                         bhs[i] = NULL;
492                 }
493         }
494         mlog_exit(status);
495         return status;
496 }
497
498 /*
499  * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
500  *
501  * Returns the sum of the rightmost extent rec logical offset and
502  * cluster count.
503  *
504  * ocfs2_add_branch() uses this to determine what logical cluster
505  * value should be populated into the leftmost new branch records.
506  *
507  * ocfs2_shift_tree_depth() uses this to determine the # clusters
508  * value for the new topmost tree record.
509  */
510 static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list  *el)
511 {
512         int i;
513
514         i = le16_to_cpu(el->l_next_free_rec) - 1;
515
516         return le32_to_cpu(el->l_recs[i].e_cpos) +
517                 ocfs2_rec_clusters(el, &el->l_recs[i]);
518 }
519
520 /*
521  * Add an entire tree branch to our inode. eb_bh is the extent block
522  * to start at, if we don't want to start the branch at the dinode
523  * structure.
524  *
525  * last_eb_bh is required as we have to update it's next_leaf pointer
526  * for the new last extent block.
527  *
528  * the new branch will be 'empty' in the sense that every block will
529  * contain a single record with cluster count == 0.
530  */
531 static int ocfs2_add_branch(struct ocfs2_super *osb,
532                             handle_t *handle,
533                             struct inode *inode,
534                             struct buffer_head *fe_bh,
535                             struct buffer_head *eb_bh,
536                             struct buffer_head **last_eb_bh,
537                             struct ocfs2_alloc_context *meta_ac)
538 {
539         int status, new_blocks, i;
540         u64 next_blkno, new_last_eb_blk;
541         struct buffer_head *bh;
542         struct buffer_head **new_eb_bhs = NULL;
543         struct ocfs2_dinode *fe;
544         struct ocfs2_extent_block *eb;
545         struct ocfs2_extent_list  *eb_el;
546         struct ocfs2_extent_list  *el;
547         u32 new_cpos;
548
549         mlog_entry_void();
550
551         BUG_ON(!last_eb_bh || !*last_eb_bh);
552
553         fe = (struct ocfs2_dinode *) fe_bh->b_data;
554
555         if (eb_bh) {
556                 eb = (struct ocfs2_extent_block *) eb_bh->b_data;
557                 el = &eb->h_list;
558         } else
559                 el = &fe->id2.i_list;
560
561         /* we never add a branch to a leaf. */
562         BUG_ON(!el->l_tree_depth);
563
564         new_blocks = le16_to_cpu(el->l_tree_depth);
565
566         /* allocate the number of new eb blocks we need */
567         new_eb_bhs = kcalloc(new_blocks, sizeof(struct buffer_head *),
568                              GFP_KERNEL);
569         if (!new_eb_bhs) {
570                 status = -ENOMEM;
571                 mlog_errno(status);
572                 goto bail;
573         }
574
575         status = ocfs2_create_new_meta_bhs(osb, handle, inode, new_blocks,
576                                            meta_ac, new_eb_bhs);
577         if (status < 0) {
578                 mlog_errno(status);
579                 goto bail;
580         }
581
582         eb = (struct ocfs2_extent_block *)(*last_eb_bh)->b_data;
583         new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list);
584
585         /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
586          * linked with the rest of the tree.
587          * conversly, new_eb_bhs[0] is the new bottommost leaf.
588          *
589          * when we leave the loop, new_last_eb_blk will point to the
590          * newest leaf, and next_blkno will point to the topmost extent
591          * block. */
592         next_blkno = new_last_eb_blk = 0;
593         for(i = 0; i < new_blocks; i++) {
594                 bh = new_eb_bhs[i];
595                 eb = (struct ocfs2_extent_block *) bh->b_data;
596                 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
597                         OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
598                         status = -EIO;
599                         goto bail;
600                 }
601                 eb_el = &eb->h_list;
602
603                 status = ocfs2_journal_access(handle, inode, bh,
604                                               OCFS2_JOURNAL_ACCESS_CREATE);
605                 if (status < 0) {
606                         mlog_errno(status);
607                         goto bail;
608                 }
609
610                 eb->h_next_leaf_blk = 0;
611                 eb_el->l_tree_depth = cpu_to_le16(i);
612                 eb_el->l_next_free_rec = cpu_to_le16(1);
613                 /*
614                  * This actually counts as an empty extent as
615                  * c_clusters == 0
616                  */
617                 eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos);
618                 eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno);
619                 /*
620                  * eb_el isn't always an interior node, but even leaf
621                  * nodes want a zero'd flags and reserved field so
622                  * this gets the whole 32 bits regardless of use.
623                  */
624                 eb_el->l_recs[0].e_int_clusters = cpu_to_le32(0);
625                 if (!eb_el->l_tree_depth)
626                         new_last_eb_blk = le64_to_cpu(eb->h_blkno);
627
628                 status = ocfs2_journal_dirty(handle, bh);
629                 if (status < 0) {
630                         mlog_errno(status);
631                         goto bail;
632                 }
633
634                 next_blkno = le64_to_cpu(eb->h_blkno);
635         }
636
637         /* This is a bit hairy. We want to update up to three blocks
638          * here without leaving any of them in an inconsistent state
639          * in case of error. We don't have to worry about
640          * journal_dirty erroring as it won't unless we've aborted the
641          * handle (in which case we would never be here) so reserving
642          * the write with journal_access is all we need to do. */
643         status = ocfs2_journal_access(handle, inode, *last_eb_bh,
644                                       OCFS2_JOURNAL_ACCESS_WRITE);
645         if (status < 0) {
646                 mlog_errno(status);
647                 goto bail;
648         }
649         status = ocfs2_journal_access(handle, inode, fe_bh,
650                                       OCFS2_JOURNAL_ACCESS_WRITE);
651         if (status < 0) {
652                 mlog_errno(status);
653                 goto bail;
654         }
655         if (eb_bh) {
656                 status = ocfs2_journal_access(handle, inode, eb_bh,
657                                               OCFS2_JOURNAL_ACCESS_WRITE);
658                 if (status < 0) {
659                         mlog_errno(status);
660                         goto bail;
661                 }
662         }
663
664         /* Link the new branch into the rest of the tree (el will
665          * either be on the fe, or the extent block passed in. */
666         i = le16_to_cpu(el->l_next_free_rec);
667         el->l_recs[i].e_blkno = cpu_to_le64(next_blkno);
668         el->l_recs[i].e_cpos = cpu_to_le32(new_cpos);
669         el->l_recs[i].e_int_clusters = 0;
670         le16_add_cpu(&el->l_next_free_rec, 1);
671
672         /* fe needs a new last extent block pointer, as does the
673          * next_leaf on the previously last-extent-block. */
674         fe->i_last_eb_blk = cpu_to_le64(new_last_eb_blk);
675
676         eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data;
677         eb->h_next_leaf_blk = cpu_to_le64(new_last_eb_blk);
678
679         status = ocfs2_journal_dirty(handle, *last_eb_bh);
680         if (status < 0)
681                 mlog_errno(status);
682         status = ocfs2_journal_dirty(handle, fe_bh);
683         if (status < 0)
684                 mlog_errno(status);
685         if (eb_bh) {
686                 status = ocfs2_journal_dirty(handle, eb_bh);
687                 if (status < 0)
688                         mlog_errno(status);
689         }
690
691         /*
692          * Some callers want to track the rightmost leaf so pass it
693          * back here.
694          */
695         brelse(*last_eb_bh);
696         get_bh(new_eb_bhs[0]);
697         *last_eb_bh = new_eb_bhs[0];
698
699         status = 0;
700 bail:
701         if (new_eb_bhs) {
702                 for (i = 0; i < new_blocks; i++)
703                         if (new_eb_bhs[i])
704                                 brelse(new_eb_bhs[i]);
705                 kfree(new_eb_bhs);
706         }
707
708         mlog_exit(status);
709         return status;
710 }
711
712 /*
713  * adds another level to the allocation tree.
714  * returns back the new extent block so you can add a branch to it
715  * after this call.
716  */
717 static int ocfs2_shift_tree_depth(struct ocfs2_super *osb,
718                                   handle_t *handle,
719                                   struct inode *inode,
720                                   struct buffer_head *fe_bh,
721                                   struct ocfs2_alloc_context *meta_ac,
722                                   struct buffer_head **ret_new_eb_bh)
723 {
724         int status, i;
725         u32 new_clusters;
726         struct buffer_head *new_eb_bh = NULL;
727         struct ocfs2_dinode *fe;
728         struct ocfs2_extent_block *eb;
729         struct ocfs2_extent_list  *fe_el;
730         struct ocfs2_extent_list  *eb_el;
731
732         mlog_entry_void();
733
734         status = ocfs2_create_new_meta_bhs(osb, handle, inode, 1, meta_ac,
735                                            &new_eb_bh);
736         if (status < 0) {
737                 mlog_errno(status);
738                 goto bail;
739         }
740
741         eb = (struct ocfs2_extent_block *) new_eb_bh->b_data;
742         if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
743                 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
744                 status = -EIO;
745                 goto bail;
746         }
747
748         eb_el = &eb->h_list;
749         fe = (struct ocfs2_dinode *) fe_bh->b_data;
750         fe_el = &fe->id2.i_list;
751
752         status = ocfs2_journal_access(handle, inode, new_eb_bh,
753                                       OCFS2_JOURNAL_ACCESS_CREATE);
754         if (status < 0) {
755                 mlog_errno(status);
756                 goto bail;
757         }
758
759         /* copy the fe data into the new extent block */
760         eb_el->l_tree_depth = fe_el->l_tree_depth;
761         eb_el->l_next_free_rec = fe_el->l_next_free_rec;
762         for(i = 0; i < le16_to_cpu(fe_el->l_next_free_rec); i++)
763                 eb_el->l_recs[i] = fe_el->l_recs[i];
764
765         status = ocfs2_journal_dirty(handle, new_eb_bh);
766         if (status < 0) {
767                 mlog_errno(status);
768                 goto bail;
769         }
770
771         status = ocfs2_journal_access(handle, inode, fe_bh,
772                                       OCFS2_JOURNAL_ACCESS_WRITE);
773         if (status < 0) {
774                 mlog_errno(status);
775                 goto bail;
776         }
777
778         new_clusters = ocfs2_sum_rightmost_rec(eb_el);
779
780         /* update fe now */
781         le16_add_cpu(&fe_el->l_tree_depth, 1);
782         fe_el->l_recs[0].e_cpos = 0;
783         fe_el->l_recs[0].e_blkno = eb->h_blkno;
784         fe_el->l_recs[0].e_int_clusters = cpu_to_le32(new_clusters);
785         for(i = 1; i < le16_to_cpu(fe_el->l_next_free_rec); i++)
786                 memset(&fe_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
787         fe_el->l_next_free_rec = cpu_to_le16(1);
788
789         /* If this is our 1st tree depth shift, then last_eb_blk
790          * becomes the allocated extent block */
791         if (fe_el->l_tree_depth == cpu_to_le16(1))
792                 fe->i_last_eb_blk = eb->h_blkno;
793
794         status = ocfs2_journal_dirty(handle, fe_bh);
795         if (status < 0) {
796                 mlog_errno(status);
797                 goto bail;
798         }
799
800         *ret_new_eb_bh = new_eb_bh;
801         new_eb_bh = NULL;
802         status = 0;
803 bail:
804         if (new_eb_bh)
805                 brelse(new_eb_bh);
806
807         mlog_exit(status);
808         return status;
809 }
810
811 /*
812  * Should only be called when there is no space left in any of the
813  * leaf nodes. What we want to do is find the lowest tree depth
814  * non-leaf extent block with room for new records. There are three
815  * valid results of this search:
816  *
817  * 1) a lowest extent block is found, then we pass it back in
818  *    *lowest_eb_bh and return '0'
819  *
820  * 2) the search fails to find anything, but the dinode has room. We
821  *    pass NULL back in *lowest_eb_bh, but still return '0'
822  *
823  * 3) the search fails to find anything AND the dinode is full, in
824  *    which case we return > 0
825  *
826  * return status < 0 indicates an error.
827  */
828 static int ocfs2_find_branch_target(struct ocfs2_super *osb,
829                                     struct inode *inode,
830                                     struct buffer_head *fe_bh,
831                                     struct buffer_head **target_bh)
832 {
833         int status = 0, i;
834         u64 blkno;
835         struct ocfs2_dinode *fe;
836         struct ocfs2_extent_block *eb;
837         struct ocfs2_extent_list  *el;
838         struct buffer_head *bh = NULL;
839         struct buffer_head *lowest_bh = NULL;
840
841         mlog_entry_void();
842
843         *target_bh = NULL;
844
845         fe = (struct ocfs2_dinode *) fe_bh->b_data;
846         el = &fe->id2.i_list;
847
848         while(le16_to_cpu(el->l_tree_depth) > 1) {
849                 if (le16_to_cpu(el->l_next_free_rec) == 0) {
850                         ocfs2_error(inode->i_sb, "Dinode %llu has empty "
851                                     "extent list (next_free_rec == 0)",
852                                     (unsigned long long)OCFS2_I(inode)->ip_blkno);
853                         status = -EIO;
854                         goto bail;
855                 }
856                 i = le16_to_cpu(el->l_next_free_rec) - 1;
857                 blkno = le64_to_cpu(el->l_recs[i].e_blkno);
858                 if (!blkno) {
859                         ocfs2_error(inode->i_sb, "Dinode %llu has extent "
860                                     "list where extent # %d has no physical "
861                                     "block start",
862                                     (unsigned long long)OCFS2_I(inode)->ip_blkno, i);
863                         status = -EIO;
864                         goto bail;
865                 }
866
867                 if (bh) {
868                         brelse(bh);
869                         bh = NULL;
870                 }
871
872                 status = ocfs2_read_block(osb, blkno, &bh, OCFS2_BH_CACHED,
873                                           inode);
874                 if (status < 0) {
875                         mlog_errno(status);
876                         goto bail;
877                 }
878
879                 eb = (struct ocfs2_extent_block *) bh->b_data;
880                 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
881                         OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
882                         status = -EIO;
883                         goto bail;
884                 }
885                 el = &eb->h_list;
886
887                 if (le16_to_cpu(el->l_next_free_rec) <
888                     le16_to_cpu(el->l_count)) {
889                         if (lowest_bh)
890                                 brelse(lowest_bh);
891                         lowest_bh = bh;
892                         get_bh(lowest_bh);
893                 }
894         }
895
896         /* If we didn't find one and the fe doesn't have any room,
897          * then return '1' */
898         if (!lowest_bh
899             && (fe->id2.i_list.l_next_free_rec == fe->id2.i_list.l_count))
900                 status = 1;
901
902         *target_bh = lowest_bh;
903 bail:
904         if (bh)
905                 brelse(bh);
906
907         mlog_exit(status);
908         return status;
909 }
910
911 /*
912  * Grow a b-tree so that it has more records.
913  *
914  * We might shift the tree depth in which case existing paths should
915  * be considered invalid.
916  *
917  * Tree depth after the grow is returned via *final_depth.
918  *
919  * *last_eb_bh will be updated by ocfs2_add_branch().
920  */
921 static int ocfs2_grow_tree(struct inode *inode, handle_t *handle,
922                            struct buffer_head *di_bh, int *final_depth,
923                            struct buffer_head **last_eb_bh,
924                            struct ocfs2_alloc_context *meta_ac)
925 {
926         int ret, shift;
927         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
928         int depth = le16_to_cpu(di->id2.i_list.l_tree_depth);
929         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
930         struct buffer_head *bh = NULL;
931
932         BUG_ON(meta_ac == NULL);
933
934         shift = ocfs2_find_branch_target(osb, inode, di_bh, &bh);
935         if (shift < 0) {
936                 ret = shift;
937                 mlog_errno(ret);
938                 goto out;
939         }
940
941         /* We traveled all the way to the bottom of the allocation tree
942          * and didn't find room for any more extents - we need to add
943          * another tree level */
944         if (shift) {
945                 BUG_ON(bh);
946                 mlog(0, "need to shift tree depth (current = %d)\n", depth);
947
948                 /* ocfs2_shift_tree_depth will return us a buffer with
949                  * the new extent block (so we can pass that to
950                  * ocfs2_add_branch). */
951                 ret = ocfs2_shift_tree_depth(osb, handle, inode, di_bh,
952                                              meta_ac, &bh);
953                 if (ret < 0) {
954                         mlog_errno(ret);
955                         goto out;
956                 }
957                 depth++;
958                 if (depth == 1) {
959                         /*
960                          * Special case: we have room now if we shifted from
961                          * tree_depth 0, so no more work needs to be done.
962                          *
963                          * We won't be calling add_branch, so pass
964                          * back *last_eb_bh as the new leaf. At depth
965                          * zero, it should always be null so there's
966                          * no reason to brelse.
967                          */
968                         BUG_ON(*last_eb_bh);
969                         get_bh(bh);
970                         *last_eb_bh = bh;
971                         goto out;
972                 }
973         }
974
975         /* call ocfs2_add_branch to add the final part of the tree with
976          * the new data. */
977         mlog(0, "add branch. bh = %p\n", bh);
978         ret = ocfs2_add_branch(osb, handle, inode, di_bh, bh, last_eb_bh,
979                                meta_ac);
980         if (ret < 0) {
981                 mlog_errno(ret);
982                 goto out;
983         }
984
985 out:
986         if (final_depth)
987                 *final_depth = depth;
988         brelse(bh);
989         return ret;
990 }
991
992 /*
993  * This function will discard the rightmost extent record.
994  */
995 static void ocfs2_shift_records_right(struct ocfs2_extent_list *el)
996 {
997         int next_free = le16_to_cpu(el->l_next_free_rec);
998         int count = le16_to_cpu(el->l_count);
999         unsigned int num_bytes;
1000
1001         BUG_ON(!next_free);
1002         /* This will cause us to go off the end of our extent list. */
1003         BUG_ON(next_free >= count);
1004
1005         num_bytes = sizeof(struct ocfs2_extent_rec) * next_free;
1006
1007         memmove(&el->l_recs[1], &el->l_recs[0], num_bytes);
1008 }
1009
1010 static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el,
1011                               struct ocfs2_extent_rec *insert_rec)
1012 {
1013         int i, insert_index, next_free, has_empty, num_bytes;
1014         u32 insert_cpos = le32_to_cpu(insert_rec->e_cpos);
1015         struct ocfs2_extent_rec *rec;
1016
1017         next_free = le16_to_cpu(el->l_next_free_rec);
1018         has_empty = ocfs2_is_empty_extent(&el->l_recs[0]);
1019
1020         BUG_ON(!next_free);
1021
1022         /* The tree code before us didn't allow enough room in the leaf. */
1023         BUG_ON(el->l_next_free_rec == el->l_count && !has_empty);
1024
1025         /*
1026          * The easiest way to approach this is to just remove the
1027          * empty extent and temporarily decrement next_free.
1028          */
1029         if (has_empty) {
1030                 /*
1031                  * If next_free was 1 (only an empty extent), this
1032                  * loop won't execute, which is fine. We still want
1033                  * the decrement above to happen.
1034                  */
1035                 for(i = 0; i < (next_free - 1); i++)
1036                         el->l_recs[i] = el->l_recs[i+1];
1037
1038                 next_free--;
1039         }
1040
1041         /*
1042          * Figure out what the new record index should be.
1043          */
1044         for(i = 0; i < next_free; i++) {
1045                 rec = &el->l_recs[i];
1046
1047                 if (insert_cpos < le32_to_cpu(rec->e_cpos))
1048                         break;
1049         }
1050         insert_index = i;
1051
1052         mlog(0, "ins %u: index %d, has_empty %d, next_free %d, count %d\n",
1053              insert_cpos, insert_index, has_empty, next_free, le16_to_cpu(el->l_count));
1054
1055         BUG_ON(insert_index < 0);
1056         BUG_ON(insert_index >= le16_to_cpu(el->l_count));
1057         BUG_ON(insert_index > next_free);
1058
1059         /*
1060          * No need to memmove if we're just adding to the tail.
1061          */
1062         if (insert_index != next_free) {
1063                 BUG_ON(next_free >= le16_to_cpu(el->l_count));
1064
1065                 num_bytes = next_free - insert_index;
1066                 num_bytes *= sizeof(struct ocfs2_extent_rec);
1067                 memmove(&el->l_recs[insert_index + 1],
1068                         &el->l_recs[insert_index],
1069                         num_bytes);
1070         }
1071
1072         /*
1073          * Either we had an empty extent, and need to re-increment or
1074          * there was no empty extent on a non full rightmost leaf node,
1075          * in which case we still need to increment.
1076          */
1077         next_free++;
1078         el->l_next_free_rec = cpu_to_le16(next_free);
1079         /*
1080          * Make sure none of the math above just messed up our tree.
1081          */
1082         BUG_ON(le16_to_cpu(el->l_next_free_rec) > le16_to_cpu(el->l_count));
1083
1084         el->l_recs[insert_index] = *insert_rec;
1085
1086 }
1087
1088 static void ocfs2_remove_empty_extent(struct ocfs2_extent_list *el)
1089 {
1090         int size, num_recs = le16_to_cpu(el->l_next_free_rec);
1091
1092         BUG_ON(num_recs == 0);
1093
1094         if (ocfs2_is_empty_extent(&el->l_recs[0])) {
1095                 num_recs--;
1096                 size = num_recs * sizeof(struct ocfs2_extent_rec);
1097                 memmove(&el->l_recs[0], &el->l_recs[1], size);
1098                 memset(&el->l_recs[num_recs], 0,
1099                        sizeof(struct ocfs2_extent_rec));
1100                 el->l_next_free_rec = cpu_to_le16(num_recs);
1101         }
1102 }
1103
1104 /*
1105  * Create an empty extent record .
1106  *
1107  * l_next_free_rec may be updated.
1108  *
1109  * If an empty extent already exists do nothing.
1110  */
1111 static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el)
1112 {
1113         int next_free = le16_to_cpu(el->l_next_free_rec);
1114
1115         BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
1116
1117         if (next_free == 0)
1118                 goto set_and_inc;
1119
1120         if (ocfs2_is_empty_extent(&el->l_recs[0]))
1121                 return;
1122
1123         mlog_bug_on_msg(el->l_count == el->l_next_free_rec,
1124                         "Asked to create an empty extent in a full list:\n"
1125                         "count = %u, tree depth = %u",
1126                         le16_to_cpu(el->l_count),
1127                         le16_to_cpu(el->l_tree_depth));
1128
1129         ocfs2_shift_records_right(el);
1130
1131 set_and_inc:
1132         le16_add_cpu(&el->l_next_free_rec, 1);
1133         memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1134 }
1135
1136 /*
1137  * For a rotation which involves two leaf nodes, the "root node" is
1138  * the lowest level tree node which contains a path to both leafs. This
1139  * resulting set of information can be used to form a complete "subtree"
1140  *
1141  * This function is passed two full paths from the dinode down to a
1142  * pair of adjacent leaves. It's task is to figure out which path
1143  * index contains the subtree root - this can be the root index itself
1144  * in a worst-case rotation.
1145  *
1146  * The array index of the subtree root is passed back.
1147  */
1148 static int ocfs2_find_subtree_root(struct inode *inode,
1149                                    struct ocfs2_path *left,
1150                                    struct ocfs2_path *right)
1151 {
1152         int i = 0;
1153
1154         /*
1155          * Check that the caller passed in two paths from the same tree.
1156          */
1157         BUG_ON(path_root_bh(left) != path_root_bh(right));
1158
1159         do {
1160                 i++;
1161
1162                 /*
1163                  * The caller didn't pass two adjacent paths.
1164                  */
1165                 mlog_bug_on_msg(i > left->p_tree_depth,
1166                                 "Inode %lu, left depth %u, right depth %u\n"
1167                                 "left leaf blk %llu, right leaf blk %llu\n",
1168                                 inode->i_ino, left->p_tree_depth,
1169                                 right->p_tree_depth,
1170                                 (unsigned long long)path_leaf_bh(left)->b_blocknr,
1171                                 (unsigned long long)path_leaf_bh(right)->b_blocknr);
1172         } while (left->p_node[i].bh->b_blocknr ==
1173                  right->p_node[i].bh->b_blocknr);
1174
1175         return i - 1;
1176 }
1177
1178 typedef void (path_insert_t)(void *, struct buffer_head *);
1179
1180 /*
1181  * Traverse a btree path in search of cpos, starting at root_el.
1182  *
1183  * This code can be called with a cpos larger than the tree, in which
1184  * case it will return the rightmost path.
1185  */
1186 static int __ocfs2_find_path(struct inode *inode,
1187                              struct ocfs2_extent_list *root_el, u32 cpos,
1188                              path_insert_t *func, void *data)
1189 {
1190         int i, ret = 0;
1191         u32 range;
1192         u64 blkno;
1193         struct buffer_head *bh = NULL;
1194         struct ocfs2_extent_block *eb;
1195         struct ocfs2_extent_list *el;
1196         struct ocfs2_extent_rec *rec;
1197         struct ocfs2_inode_info *oi = OCFS2_I(inode);
1198
1199         el = root_el;
1200         while (el->l_tree_depth) {
1201                 if (le16_to_cpu(el->l_next_free_rec) == 0) {
1202                         ocfs2_error(inode->i_sb,
1203                                     "Inode %llu has empty extent list at "
1204                                     "depth %u\n",
1205                                     (unsigned long long)oi->ip_blkno,
1206                                     le16_to_cpu(el->l_tree_depth));
1207                         ret = -EROFS;
1208                         goto out;
1209
1210                 }
1211
1212                 for(i = 0; i < le16_to_cpu(el->l_next_free_rec) - 1; i++) {
1213                         rec = &el->l_recs[i];
1214
1215                         /*
1216                          * In the case that cpos is off the allocation
1217                          * tree, this should just wind up returning the
1218                          * rightmost record.
1219                          */
1220                         range = le32_to_cpu(rec->e_cpos) +
1221                                 ocfs2_rec_clusters(el, rec);
1222                         if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range)
1223                             break;
1224                 }
1225
1226                 blkno = le64_to_cpu(el->l_recs[i].e_blkno);
1227                 if (blkno == 0) {
1228                         ocfs2_error(inode->i_sb,
1229                                     "Inode %llu has bad blkno in extent list "
1230                                     "at depth %u (index %d)\n",
1231                                     (unsigned long long)oi->ip_blkno,
1232                                     le16_to_cpu(el->l_tree_depth), i);
1233                         ret = -EROFS;
1234                         goto out;
1235                 }
1236
1237                 brelse(bh);
1238                 bh = NULL;
1239                 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), blkno,
1240                                        &bh, OCFS2_BH_CACHED, inode);
1241                 if (ret) {
1242                         mlog_errno(ret);
1243                         goto out;
1244                 }
1245
1246                 eb = (struct ocfs2_extent_block *) bh->b_data;
1247                 el = &eb->h_list;
1248                 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
1249                         OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
1250                         ret = -EIO;
1251                         goto out;
1252                 }
1253
1254                 if (le16_to_cpu(el->l_next_free_rec) >
1255                     le16_to_cpu(el->l_count)) {
1256                         ocfs2_error(inode->i_sb,
1257                                     "Inode %llu has bad count in extent list "
1258                                     "at block %llu (next free=%u, count=%u)\n",
1259                                     (unsigned long long)oi->ip_blkno,
1260                                     (unsigned long long)bh->b_blocknr,
1261                                     le16_to_cpu(el->l_next_free_rec),
1262                                     le16_to_cpu(el->l_count));
1263                         ret = -EROFS;
1264                         goto out;
1265                 }
1266
1267                 if (func)
1268                         func(data, bh);
1269         }
1270
1271 out:
1272         /*
1273          * Catch any trailing bh that the loop didn't handle.
1274          */
1275         brelse(bh);
1276
1277         return ret;
1278 }
1279
1280 /*
1281  * Given an initialized path (that is, it has a valid root extent
1282  * list), this function will traverse the btree in search of the path
1283  * which would contain cpos.
1284  *
1285  * The path traveled is recorded in the path structure.
1286  *
1287  * Note that this will not do any comparisons on leaf node extent
1288  * records, so it will work fine in the case that we just added a tree
1289  * branch.
1290  */
1291 struct find_path_data {
1292         int index;
1293         struct ocfs2_path *path;
1294 };
1295 static void find_path_ins(void *data, struct buffer_head *bh)
1296 {
1297         struct find_path_data *fp = data;
1298
1299         get_bh(bh);
1300         ocfs2_path_insert_eb(fp->path, fp->index, bh);
1301         fp->index++;
1302 }
1303 static int ocfs2_find_path(struct inode *inode, struct ocfs2_path *path,
1304                            u32 cpos)
1305 {
1306         struct find_path_data data;
1307
1308         data.index = 1;
1309         data.path = path;
1310         return __ocfs2_find_path(inode, path_root_el(path), cpos,
1311                                  find_path_ins, &data);
1312 }
1313
1314 static void find_leaf_ins(void *data, struct buffer_head *bh)
1315 {
1316         struct ocfs2_extent_block *eb =(struct ocfs2_extent_block *)bh->b_data;
1317         struct ocfs2_extent_list *el = &eb->h_list;
1318         struct buffer_head **ret = data;
1319
1320         /* We want to retain only the leaf block. */
1321         if (le16_to_cpu(el->l_tree_depth) == 0) {
1322                 get_bh(bh);
1323                 *ret = bh;
1324         }
1325 }
1326 /*
1327  * Find the leaf block in the tree which would contain cpos. No
1328  * checking of the actual leaf is done.
1329  *
1330  * Some paths want to call this instead of allocating a path structure
1331  * and calling ocfs2_find_path().
1332  *
1333  * This function doesn't handle non btree extent lists.
1334  */
1335 int ocfs2_find_leaf(struct inode *inode, struct ocfs2_extent_list *root_el,
1336                     u32 cpos, struct buffer_head **leaf_bh)
1337 {
1338         int ret;
1339         struct buffer_head *bh = NULL;
1340
1341         ret = __ocfs2_find_path(inode, root_el, cpos, find_leaf_ins, &bh);
1342         if (ret) {
1343                 mlog_errno(ret);
1344                 goto out;
1345         }
1346
1347         *leaf_bh = bh;
1348 out:
1349         return ret;
1350 }
1351
1352 /*
1353  * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1354  *
1355  * Basically, we've moved stuff around at the bottom of the tree and
1356  * we need to fix up the extent records above the changes to reflect
1357  * the new changes.
1358  *
1359  * left_rec: the record on the left.
1360  * left_child_el: is the child list pointed to by left_rec
1361  * right_rec: the record to the right of left_rec
1362  * right_child_el: is the child list pointed to by right_rec
1363  *
1364  * By definition, this only works on interior nodes.
1365  */
1366 static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec,
1367                                   struct ocfs2_extent_list *left_child_el,
1368                                   struct ocfs2_extent_rec *right_rec,
1369                                   struct ocfs2_extent_list *right_child_el)
1370 {
1371         u32 left_clusters, right_end;
1372
1373         /*
1374          * Interior nodes never have holes. Their cpos is the cpos of
1375          * the leftmost record in their child list. Their cluster
1376          * count covers the full theoretical range of their child list
1377          * - the range between their cpos and the cpos of the record
1378          * immediately to their right.
1379          */
1380         left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos);
1381         if (ocfs2_is_empty_extent(&right_child_el->l_recs[0])) {
1382                 BUG_ON(le16_to_cpu(right_child_el->l_next_free_rec) <= 1);
1383                 left_clusters = le32_to_cpu(right_child_el->l_recs[1].e_cpos);
1384         }
1385         left_clusters -= le32_to_cpu(left_rec->e_cpos);
1386         left_rec->e_int_clusters = cpu_to_le32(left_clusters);
1387
1388         /*
1389          * Calculate the rightmost cluster count boundary before
1390          * moving cpos - we will need to adjust clusters after
1391          * updating e_cpos to keep the same highest cluster count.
1392          */
1393         right_end = le32_to_cpu(right_rec->e_cpos);
1394         right_end += le32_to_cpu(right_rec->e_int_clusters);
1395
1396         right_rec->e_cpos = left_rec->e_cpos;
1397         le32_add_cpu(&right_rec->e_cpos, left_clusters);
1398
1399         right_end -= le32_to_cpu(right_rec->e_cpos);
1400         right_rec->e_int_clusters = cpu_to_le32(right_end);
1401 }
1402
1403 /*
1404  * Adjust the adjacent root node records involved in a
1405  * rotation. left_el_blkno is passed in as a key so that we can easily
1406  * find it's index in the root list.
1407  */
1408 static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el,
1409                                       struct ocfs2_extent_list *left_el,
1410                                       struct ocfs2_extent_list *right_el,
1411                                       u64 left_el_blkno)
1412 {
1413         int i;
1414
1415         BUG_ON(le16_to_cpu(root_el->l_tree_depth) <=
1416                le16_to_cpu(left_el->l_tree_depth));
1417
1418         for(i = 0; i < le16_to_cpu(root_el->l_next_free_rec) - 1; i++) {
1419                 if (le64_to_cpu(root_el->l_recs[i].e_blkno) == left_el_blkno)
1420                         break;
1421         }
1422
1423         /*
1424          * The path walking code should have never returned a root and
1425          * two paths which are not adjacent.
1426          */
1427         BUG_ON(i >= (le16_to_cpu(root_el->l_next_free_rec) - 1));
1428
1429         ocfs2_adjust_adjacent_records(&root_el->l_recs[i], left_el,
1430                                       &root_el->l_recs[i + 1], right_el);
1431 }
1432
1433 /*
1434  * We've changed a leaf block (in right_path) and need to reflect that
1435  * change back up the subtree.
1436  *
1437  * This happens in multiple places:
1438  *   - When we've moved an extent record from the left path leaf to the right
1439  *     path leaf to make room for an empty extent in the left path leaf.
1440  *   - When our insert into the right path leaf is at the leftmost edge
1441  *     and requires an update of the path immediately to it's left. This
1442  *     can occur at the end of some types of rotation and appending inserts.
1443  *   - When we've adjusted the last extent record in the left path leaf and the
1444  *     1st extent record in the right path leaf during cross extent block merge.
1445  */
1446 static void ocfs2_complete_edge_insert(struct inode *inode, handle_t *handle,
1447                                        struct ocfs2_path *left_path,
1448                                        struct ocfs2_path *right_path,
1449                                        int subtree_index)
1450 {
1451         int ret, i, idx;
1452         struct ocfs2_extent_list *el, *left_el, *right_el;
1453         struct ocfs2_extent_rec *left_rec, *right_rec;
1454         struct buffer_head *root_bh = left_path->p_node[subtree_index].bh;
1455
1456         /*
1457          * Update the counts and position values within all the
1458          * interior nodes to reflect the leaf rotation we just did.
1459          *
1460          * The root node is handled below the loop.
1461          *
1462          * We begin the loop with right_el and left_el pointing to the
1463          * leaf lists and work our way up.
1464          *
1465          * NOTE: within this loop, left_el and right_el always refer
1466          * to the *child* lists.
1467          */
1468         left_el = path_leaf_el(left_path);
1469         right_el = path_leaf_el(right_path);
1470         for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) {
1471                 mlog(0, "Adjust records at index %u\n", i);
1472
1473                 /*
1474                  * One nice property of knowing that all of these
1475                  * nodes are below the root is that we only deal with
1476                  * the leftmost right node record and the rightmost
1477                  * left node record.
1478                  */
1479                 el = left_path->p_node[i].el;
1480                 idx = le16_to_cpu(left_el->l_next_free_rec) - 1;
1481                 left_rec = &el->l_recs[idx];
1482
1483                 el = right_path->p_node[i].el;
1484                 right_rec = &el->l_recs[0];
1485
1486                 ocfs2_adjust_adjacent_records(left_rec, left_el, right_rec,
1487                                               right_el);
1488
1489                 ret = ocfs2_journal_dirty(handle, left_path->p_node[i].bh);
1490                 if (ret)
1491                         mlog_errno(ret);
1492
1493                 ret = ocfs2_journal_dirty(handle, right_path->p_node[i].bh);
1494                 if (ret)
1495                         mlog_errno(ret);
1496
1497                 /*
1498                  * Setup our list pointers now so that the current
1499                  * parents become children in the next iteration.
1500                  */
1501                 left_el = left_path->p_node[i].el;
1502                 right_el = right_path->p_node[i].el;
1503         }
1504
1505         /*
1506          * At the root node, adjust the two adjacent records which
1507          * begin our path to the leaves.
1508          */
1509
1510         el = left_path->p_node[subtree_index].el;
1511         left_el = left_path->p_node[subtree_index + 1].el;
1512         right_el = right_path->p_node[subtree_index + 1].el;
1513
1514         ocfs2_adjust_root_records(el, left_el, right_el,
1515                                   left_path->p_node[subtree_index + 1].bh->b_blocknr);
1516
1517         root_bh = left_path->p_node[subtree_index].bh;
1518
1519         ret = ocfs2_journal_dirty(handle, root_bh);
1520         if (ret)
1521                 mlog_errno(ret);
1522 }
1523
1524 static int ocfs2_rotate_subtree_right(struct inode *inode,
1525                                       handle_t *handle,
1526                                       struct ocfs2_path *left_path,
1527                                       struct ocfs2_path *right_path,
1528                                       int subtree_index)
1529 {
1530         int ret, i;
1531         struct buffer_head *right_leaf_bh;
1532         struct buffer_head *left_leaf_bh = NULL;
1533         struct buffer_head *root_bh;
1534         struct ocfs2_extent_list *right_el, *left_el;
1535         struct ocfs2_extent_rec move_rec;
1536
1537         left_leaf_bh = path_leaf_bh(left_path);
1538         left_el = path_leaf_el(left_path);
1539
1540         if (left_el->l_next_free_rec != left_el->l_count) {
1541                 ocfs2_error(inode->i_sb,
1542                             "Inode %llu has non-full interior leaf node %llu"
1543                             "(next free = %u)",
1544                             (unsigned long long)OCFS2_I(inode)->ip_blkno,
1545                             (unsigned long long)left_leaf_bh->b_blocknr,
1546                             le16_to_cpu(left_el->l_next_free_rec));
1547                 return -EROFS;
1548         }
1549
1550         /*
1551          * This extent block may already have an empty record, so we
1552          * return early if so.
1553          */
1554         if (ocfs2_is_empty_extent(&left_el->l_recs[0]))
1555                 return 0;
1556
1557         root_bh = left_path->p_node[subtree_index].bh;
1558         BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
1559
1560         ret = ocfs2_journal_access(handle, inode, root_bh,
1561                                    OCFS2_JOURNAL_ACCESS_WRITE);
1562         if (ret) {
1563                 mlog_errno(ret);
1564                 goto out;
1565         }
1566
1567         for(i = subtree_index + 1; i < path_num_items(right_path); i++) {
1568                 ret = ocfs2_journal_access(handle, inode,
1569                                            right_path->p_node[i].bh,
1570                                            OCFS2_JOURNAL_ACCESS_WRITE);
1571                 if (ret) {
1572                         mlog_errno(ret);
1573                         goto out;
1574                 }
1575
1576                 ret = ocfs2_journal_access(handle, inode,
1577                                            left_path->p_node[i].bh,
1578                                            OCFS2_JOURNAL_ACCESS_WRITE);
1579                 if (ret) {
1580                         mlog_errno(ret);
1581                         goto out;
1582                 }
1583         }
1584
1585         right_leaf_bh = path_leaf_bh(right_path);
1586         right_el = path_leaf_el(right_path);
1587
1588         /* This is a code error, not a disk corruption. */
1589         mlog_bug_on_msg(!right_el->l_next_free_rec, "Inode %llu: Rotate fails "
1590                         "because rightmost leaf block %llu is empty\n",
1591                         (unsigned long long)OCFS2_I(inode)->ip_blkno,
1592                         (unsigned long long)right_leaf_bh->b_blocknr);
1593
1594         ocfs2_create_empty_extent(right_el);
1595
1596         ret = ocfs2_journal_dirty(handle, right_leaf_bh);
1597         if (ret) {
1598                 mlog_errno(ret);
1599                 goto out;
1600         }
1601
1602         /* Do the copy now. */
1603         i = le16_to_cpu(left_el->l_next_free_rec) - 1;
1604         move_rec = left_el->l_recs[i];
1605         right_el->l_recs[0] = move_rec;
1606
1607         /*
1608          * Clear out the record we just copied and shift everything
1609          * over, leaving an empty extent in the left leaf.
1610          *
1611          * We temporarily subtract from next_free_rec so that the
1612          * shift will lose the tail record (which is now defunct).
1613          */
1614         le16_add_cpu(&left_el->l_next_free_rec, -1);
1615         ocfs2_shift_records_right(left_el);
1616         memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1617         le16_add_cpu(&left_el->l_next_free_rec, 1);
1618
1619         ret = ocfs2_journal_dirty(handle, left_leaf_bh);
1620         if (ret) {
1621                 mlog_errno(ret);
1622                 goto out;
1623         }
1624
1625         ocfs2_complete_edge_insert(inode, handle, left_path, right_path,
1626                                 subtree_index);
1627
1628 out:
1629         return ret;
1630 }
1631
1632 /*
1633  * Given a full path, determine what cpos value would return us a path
1634  * containing the leaf immediately to the left of the current one.
1635  *
1636  * Will return zero if the path passed in is already the leftmost path.
1637  */
1638 static int ocfs2_find_cpos_for_left_leaf(struct super_block *sb,
1639                                          struct ocfs2_path *path, u32 *cpos)
1640 {
1641         int i, j, ret = 0;
1642         u64 blkno;
1643         struct ocfs2_extent_list *el;
1644
1645         BUG_ON(path->p_tree_depth == 0);
1646
1647         *cpos = 0;
1648
1649         blkno = path_leaf_bh(path)->b_blocknr;
1650
1651         /* Start at the tree node just above the leaf and work our way up. */
1652         i = path->p_tree_depth - 1;
1653         while (i >= 0) {
1654                 el = path->p_node[i].el;
1655
1656                 /*
1657                  * Find the extent record just before the one in our
1658                  * path.
1659                  */
1660                 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) {
1661                         if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) {
1662                                 if (j == 0) {
1663                                         if (i == 0) {
1664                                                 /*
1665                                                  * We've determined that the
1666                                                  * path specified is already
1667                                                  * the leftmost one - return a
1668                                                  * cpos of zero.
1669                                                  */
1670                                                 goto out;
1671                                         }
1672                                         /*
1673                                          * The leftmost record points to our
1674                                          * leaf - we need to travel up the
1675                                          * tree one level.
1676                                          */
1677                                         goto next_node;
1678                                 }
1679
1680                                 *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos);
1681                                 *cpos = *cpos + ocfs2_rec_clusters(el,
1682                                                            &el->l_recs[j - 1]);
1683                                 *cpos = *cpos - 1;
1684                                 goto out;
1685                         }
1686                 }
1687
1688                 /*
1689                  * If we got here, we never found a valid node where
1690                  * the tree indicated one should be.
1691                  */
1692                 ocfs2_error(sb,
1693                             "Invalid extent tree at extent block %llu\n",
1694                             (unsigned long long)blkno);
1695                 ret = -EROFS;
1696                 goto out;
1697
1698 next_node:
1699                 blkno = path->p_node[i].bh->b_blocknr;
1700                 i--;
1701         }
1702
1703 out:
1704         return ret;
1705 }
1706
1707 /*
1708  * Extend the transaction by enough credits to complete the rotation,
1709  * and still leave at least the original number of credits allocated
1710  * to this transaction.
1711  */
1712 static int ocfs2_extend_rotate_transaction(handle_t *handle, int subtree_depth,
1713                                            int op_credits,
1714                                            struct ocfs2_path *path)
1715 {
1716         int credits = (path->p_tree_depth - subtree_depth) * 2 + 1 + op_credits;
1717
1718         if (handle->h_buffer_credits < credits)
1719                 return ocfs2_extend_trans(handle, credits);
1720
1721         return 0;
1722 }
1723
1724 /*
1725  * Trap the case where we're inserting into the theoretical range past
1726  * the _actual_ left leaf range. Otherwise, we'll rotate a record
1727  * whose cpos is less than ours into the right leaf.
1728  *
1729  * It's only necessary to look at the rightmost record of the left
1730  * leaf because the logic that calls us should ensure that the
1731  * theoretical ranges in the path components above the leaves are
1732  * correct.
1733  */
1734 static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path,
1735                                                  u32 insert_cpos)
1736 {
1737         struct ocfs2_extent_list *left_el;
1738         struct ocfs2_extent_rec *rec;
1739         int next_free;
1740
1741         left_el = path_leaf_el(left_path);
1742         next_free = le16_to_cpu(left_el->l_next_free_rec);
1743         rec = &left_el->l_recs[next_free - 1];
1744
1745         if (insert_cpos > le32_to_cpu(rec->e_cpos))
1746                 return 1;
1747         return 0;
1748 }
1749
1750 static int ocfs2_leftmost_rec_contains(struct ocfs2_extent_list *el, u32 cpos)
1751 {
1752         int next_free = le16_to_cpu(el->l_next_free_rec);
1753         unsigned int range;
1754         struct ocfs2_extent_rec *rec;
1755
1756         if (next_free == 0)
1757                 return 0;
1758
1759         rec = &el->l_recs[0];
1760         if (ocfs2_is_empty_extent(rec)) {
1761                 /* Empty list. */
1762                 if (next_free == 1)
1763                         return 0;
1764                 rec = &el->l_recs[1];
1765         }
1766
1767         range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
1768         if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range)
1769                 return 1;
1770         return 0;
1771 }
1772
1773 /*
1774  * Rotate all the records in a btree right one record, starting at insert_cpos.
1775  *
1776  * The path to the rightmost leaf should be passed in.
1777  *
1778  * The array is assumed to be large enough to hold an entire path (tree depth).
1779  *
1780  * Upon succesful return from this function:
1781  *
1782  * - The 'right_path' array will contain a path to the leaf block
1783  *   whose range contains e_cpos.
1784  * - That leaf block will have a single empty extent in list index 0.
1785  * - In the case that the rotation requires a post-insert update,
1786  *   *ret_left_path will contain a valid path which can be passed to
1787  *   ocfs2_insert_path().
1788  */
1789 static int ocfs2_rotate_tree_right(struct inode *inode,
1790                                    handle_t *handle,
1791                                    enum ocfs2_split_type split,
1792                                    u32 insert_cpos,
1793                                    struct ocfs2_path *right_path,
1794                                    struct ocfs2_path **ret_left_path)
1795 {
1796         int ret, start, orig_credits = handle->h_buffer_credits;
1797         u32 cpos;
1798         struct ocfs2_path *left_path = NULL;
1799
1800         *ret_left_path = NULL;
1801
1802         left_path = ocfs2_new_path(path_root_bh(right_path),
1803                                    path_root_el(right_path));
1804         if (!left_path) {
1805                 ret = -ENOMEM;
1806                 mlog_errno(ret);
1807                 goto out;
1808         }
1809
1810         ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, &cpos);
1811         if (ret) {
1812                 mlog_errno(ret);
1813                 goto out;
1814         }
1815
1816         mlog(0, "Insert: %u, first left path cpos: %u\n", insert_cpos, cpos);
1817
1818         /*
1819          * What we want to do here is:
1820          *
1821          * 1) Start with the rightmost path.
1822          *
1823          * 2) Determine a path to the leaf block directly to the left
1824          *    of that leaf.
1825          *
1826          * 3) Determine the 'subtree root' - the lowest level tree node
1827          *    which contains a path to both leaves.
1828          *
1829          * 4) Rotate the subtree.
1830          *
1831          * 5) Find the next subtree by considering the left path to be
1832          *    the new right path.
1833          *
1834          * The check at the top of this while loop also accepts
1835          * insert_cpos == cpos because cpos is only a _theoretical_
1836          * value to get us the left path - insert_cpos might very well
1837          * be filling that hole.
1838          *
1839          * Stop at a cpos of '0' because we either started at the
1840          * leftmost branch (i.e., a tree with one branch and a
1841          * rotation inside of it), or we've gone as far as we can in
1842          * rotating subtrees.
1843          */
1844         while (cpos && insert_cpos <= cpos) {
1845                 mlog(0, "Rotating a tree: ins. cpos: %u, left path cpos: %u\n",
1846                      insert_cpos, cpos);
1847
1848                 ret = ocfs2_find_path(inode, left_path, cpos);
1849                 if (ret) {
1850                         mlog_errno(ret);
1851                         goto out;
1852                 }
1853
1854                 mlog_bug_on_msg(path_leaf_bh(left_path) ==
1855                                 path_leaf_bh(right_path),
1856                                 "Inode %lu: error during insert of %u "
1857                                 "(left path cpos %u) results in two identical "
1858                                 "paths ending at %llu\n",
1859                                 inode->i_ino, insert_cpos, cpos,
1860                                 (unsigned long long)
1861                                 path_leaf_bh(left_path)->b_blocknr);
1862
1863                 if (split == SPLIT_NONE &&
1864                     ocfs2_rotate_requires_path_adjustment(left_path,
1865                                                           insert_cpos)) {
1866
1867                         /*
1868                          * We've rotated the tree as much as we
1869                          * should. The rest is up to
1870                          * ocfs2_insert_path() to complete, after the
1871                          * record insertion. We indicate this
1872                          * situation by returning the left path.
1873                          *
1874                          * The reason we don't adjust the records here
1875                          * before the record insert is that an error
1876                          * later might break the rule where a parent
1877                          * record e_cpos will reflect the actual
1878                          * e_cpos of the 1st nonempty record of the
1879                          * child list.
1880                          */
1881                         *ret_left_path = left_path;
1882                         goto out_ret_path;
1883                 }
1884
1885                 start = ocfs2_find_subtree_root(inode, left_path, right_path);
1886
1887                 mlog(0, "Subtree root at index %d (blk %llu, depth %d)\n",
1888                      start,
1889                      (unsigned long long) right_path->p_node[start].bh->b_blocknr,
1890                      right_path->p_tree_depth);
1891
1892                 ret = ocfs2_extend_rotate_transaction(handle, start,
1893                                                       orig_credits, right_path);
1894                 if (ret) {
1895                         mlog_errno(ret);
1896                         goto out;
1897                 }
1898
1899                 ret = ocfs2_rotate_subtree_right(inode, handle, left_path,
1900                                                  right_path, start);
1901                 if (ret) {
1902                         mlog_errno(ret);
1903                         goto out;
1904                 }
1905
1906                 if (split != SPLIT_NONE &&
1907                     ocfs2_leftmost_rec_contains(path_leaf_el(right_path),
1908                                                 insert_cpos)) {
1909                         /*
1910                          * A rotate moves the rightmost left leaf
1911                          * record over to the leftmost right leaf
1912                          * slot. If we're doing an extent split
1913                          * instead of a real insert, then we have to
1914                          * check that the extent to be split wasn't
1915                          * just moved over. If it was, then we can
1916                          * exit here, passing left_path back -
1917                          * ocfs2_split_extent() is smart enough to
1918                          * search both leaves.
1919                          */
1920                         *ret_left_path = left_path;
1921                         goto out_ret_path;
1922                 }
1923
1924                 /*
1925                  * There is no need to re-read the next right path
1926                  * as we know that it'll be our current left
1927                  * path. Optimize by copying values instead.
1928                  */
1929                 ocfs2_mv_path(right_path, left_path);
1930
1931                 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path,
1932                                                     &cpos);
1933                 if (ret) {
1934                         mlog_errno(ret);
1935                         goto out;
1936                 }
1937         }
1938
1939 out:
1940         ocfs2_free_path(left_path);
1941
1942 out_ret_path:
1943         return ret;
1944 }
1945
1946 static void ocfs2_update_edge_lengths(struct inode *inode, handle_t *handle,
1947                                       struct ocfs2_path *path)
1948 {
1949         int i, idx;
1950         struct ocfs2_extent_rec *rec;
1951         struct ocfs2_extent_list *el;
1952         struct ocfs2_extent_block *eb;
1953         u32 range;
1954
1955         /* Path should always be rightmost. */
1956         eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
1957         BUG_ON(eb->h_next_leaf_blk != 0ULL);
1958
1959         el = &eb->h_list;
1960         BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0);
1961         idx = le16_to_cpu(el->l_next_free_rec) - 1;
1962         rec = &el->l_recs[idx];
1963         range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
1964
1965         for (i = 0; i < path->p_tree_depth; i++) {
1966                 el = path->p_node[i].el;
1967                 idx = le16_to_cpu(el->l_next_free_rec) - 1;
1968                 rec = &el->l_recs[idx];
1969
1970                 rec->e_int_clusters = cpu_to_le32(range);
1971                 le32_add_cpu(&rec->e_int_clusters, -le32_to_cpu(rec->e_cpos));
1972
1973                 ocfs2_journal_dirty(handle, path->p_node[i].bh);
1974         }
1975 }
1976
1977 static void ocfs2_unlink_path(struct inode *inode, handle_t *handle,
1978                               struct ocfs2_cached_dealloc_ctxt *dealloc,
1979                               struct ocfs2_path *path, int unlink_start)
1980 {
1981         int ret, i;
1982         struct ocfs2_extent_block *eb;
1983         struct ocfs2_extent_list *el;
1984         struct buffer_head *bh;
1985
1986         for(i = unlink_start; i < path_num_items(path); i++) {
1987                 bh = path->p_node[i].bh;
1988
1989                 eb = (struct ocfs2_extent_block *)bh->b_data;
1990                 /*
1991                  * Not all nodes might have had their final count
1992                  * decremented by the caller - handle this here.
1993                  */
1994                 el = &eb->h_list;
1995                 if (le16_to_cpu(el->l_next_free_rec) > 1) {
1996                         mlog(ML_ERROR,
1997                              "Inode %llu, attempted to remove extent block "
1998                              "%llu with %u records\n",
1999                              (unsigned long long)OCFS2_I(inode)->ip_blkno,
2000                              (unsigned long long)le64_to_cpu(eb->h_blkno),
2001                              le16_to_cpu(el->l_next_free_rec));
2002
2003                         ocfs2_journal_dirty(handle, bh);
2004                         ocfs2_remove_from_cache(inode, bh);
2005                         continue;
2006                 }
2007
2008                 el->l_next_free_rec = 0;
2009                 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2010
2011                 ocfs2_journal_dirty(handle, bh);
2012
2013                 ret = ocfs2_cache_extent_block_free(dealloc, eb);
2014                 if (ret)
2015                         mlog_errno(ret);
2016
2017                 ocfs2_remove_from_cache(inode, bh);
2018         }
2019 }
2020
2021 static void ocfs2_unlink_subtree(struct inode *inode, handle_t *handle,
2022                                  struct ocfs2_path *left_path,
2023                                  struct ocfs2_path *right_path,
2024                                  int subtree_index,
2025                                  struct ocfs2_cached_dealloc_ctxt *dealloc)
2026 {
2027         int i;
2028         struct buffer_head *root_bh = left_path->p_node[subtree_index].bh;
2029         struct ocfs2_extent_list *root_el = left_path->p_node[subtree_index].el;
2030         struct ocfs2_extent_list *el;
2031         struct ocfs2_extent_block *eb;
2032
2033         el = path_leaf_el(left_path);
2034
2035         eb = (struct ocfs2_extent_block *)right_path->p_node[subtree_index + 1].bh->b_data;
2036
2037         for(i = 1; i < le16_to_cpu(root_el->l_next_free_rec); i++)
2038                 if (root_el->l_recs[i].e_blkno == eb->h_blkno)
2039                         break;
2040
2041         BUG_ON(i >= le16_to_cpu(root_el->l_next_free_rec));
2042
2043         memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
2044         le16_add_cpu(&root_el->l_next_free_rec, -1);
2045
2046         eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2047         eb->h_next_leaf_blk = 0;
2048
2049         ocfs2_journal_dirty(handle, root_bh);
2050         ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
2051
2052         ocfs2_unlink_path(inode, handle, dealloc, right_path,
2053                           subtree_index + 1);
2054 }
2055
2056 static int ocfs2_rotate_subtree_left(struct inode *inode, handle_t *handle,
2057                                      struct ocfs2_path *left_path,
2058                                      struct ocfs2_path *right_path,
2059                                      int subtree_index,
2060                                      struct ocfs2_cached_dealloc_ctxt *dealloc,
2061                                      int *deleted)
2062 {
2063         int ret, i, del_right_subtree = 0, right_has_empty = 0;
2064         struct buffer_head *root_bh, *di_bh = path_root_bh(right_path);
2065         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
2066         struct ocfs2_extent_list *right_leaf_el, *left_leaf_el;
2067         struct ocfs2_extent_block *eb;
2068
2069         *deleted = 0;
2070
2071         right_leaf_el = path_leaf_el(right_path);
2072         left_leaf_el = path_leaf_el(left_path);
2073         root_bh = left_path->p_node[subtree_index].bh;
2074         BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
2075
2076         if (!ocfs2_is_empty_extent(&left_leaf_el->l_recs[0]))
2077                 return 0;
2078
2079         eb = (struct ocfs2_extent_block *)path_leaf_bh(right_path)->b_data;
2080         if (ocfs2_is_empty_extent(&right_leaf_el->l_recs[0])) {
2081                 /*
2082                  * It's legal for us to proceed if the right leaf is
2083                  * the rightmost one and it has an empty extent. There
2084                  * are two cases to handle - whether the leaf will be
2085                  * empty after removal or not. If the leaf isn't empty
2086                  * then just remove the empty extent up front. The
2087                  * next block will handle empty leaves by flagging
2088                  * them for unlink.
2089                  *
2090                  * Non rightmost leaves will throw -EAGAIN and the
2091                  * caller can manually move the subtree and retry.
2092                  */
2093
2094                 if (eb->h_next_leaf_blk != 0ULL)
2095                         return -EAGAIN;
2096
2097                 if (le16_to_cpu(right_leaf_el->l_next_free_rec) > 1) {
2098                         ret = ocfs2_journal_access(handle, inode,
2099                                                    path_leaf_bh(right_path),
2100                                                    OCFS2_JOURNAL_ACCESS_WRITE);
2101                         if (ret) {
2102                                 mlog_errno(ret);
2103                                 goto out;
2104                         }
2105
2106                         ocfs2_remove_empty_extent(right_leaf_el);
2107                 } else
2108                         right_has_empty = 1;
2109         }
2110
2111         if (eb->h_next_leaf_blk == 0ULL &&
2112             le16_to_cpu(right_leaf_el->l_next_free_rec) == 1) {
2113                 /*
2114                  * We have to update i_last_eb_blk during the meta
2115                  * data delete.
2116                  */
2117                 ret = ocfs2_journal_access(handle, inode, di_bh,
2118                                            OCFS2_JOURNAL_ACCESS_WRITE);
2119                 if (ret) {
2120                         mlog_errno(ret);
2121                         goto out;
2122                 }
2123
2124                 del_right_subtree = 1;
2125         }
2126
2127         /*
2128          * Getting here with an empty extent in the right path implies
2129          * that it's the rightmost path and will be deleted.
2130          */
2131         BUG_ON(right_has_empty && !del_right_subtree);
2132
2133         ret = ocfs2_journal_access(handle, inode, root_bh,
2134                                    OCFS2_JOURNAL_ACCESS_WRITE);
2135         if (ret) {
2136                 mlog_errno(ret);
2137                 goto out;
2138         }
2139
2140         for(i = subtree_index + 1; i < path_num_items(right_path); i++) {
2141                 ret = ocfs2_journal_access(handle, inode,
2142                                            right_path->p_node[i].bh,
2143                                            OCFS2_JOURNAL_ACCESS_WRITE);
2144                 if (ret) {
2145                         mlog_errno(ret);
2146                         goto out;
2147                 }
2148
2149                 ret = ocfs2_journal_access(handle, inode,
2150                                            left_path->p_node[i].bh,
2151                                            OCFS2_JOURNAL_ACCESS_WRITE);
2152                 if (ret) {
2153                         mlog_errno(ret);
2154                         goto out;
2155                 }
2156         }
2157
2158         if (!right_has_empty) {
2159                 /*
2160                  * Only do this if we're moving a real
2161                  * record. Otherwise, the action is delayed until
2162                  * after removal of the right path in which case we
2163                  * can do a simple shift to remove the empty extent.
2164                  */
2165                 ocfs2_rotate_leaf(left_leaf_el, &right_leaf_el->l_recs[0]);
2166                 memset(&right_leaf_el->l_recs[0], 0,
2167                        sizeof(struct ocfs2_extent_rec));
2168         }
2169         if (eb->h_next_leaf_blk == 0ULL) {
2170                 /*
2171                  * Move recs over to get rid of empty extent, decrease
2172                  * next_free. This is allowed to remove the last
2173                  * extent in our leaf (setting l_next_free_rec to
2174                  * zero) - the delete code below won't care.
2175                  */
2176                 ocfs2_remove_empty_extent(right_leaf_el);
2177         }
2178
2179         ret = ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
2180         if (ret)
2181                 mlog_errno(ret);
2182         ret = ocfs2_journal_dirty(handle, path_leaf_bh(right_path));
2183         if (ret)
2184                 mlog_errno(ret);
2185
2186         if (del_right_subtree) {
2187                 ocfs2_unlink_subtree(inode, handle, left_path, right_path,
2188                                      subtree_index, dealloc);
2189                 ocfs2_update_edge_lengths(inode, handle, left_path);
2190
2191                 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2192                 di->i_last_eb_blk = eb->h_blkno;
2193
2194                 /*
2195                  * Removal of the extent in the left leaf was skipped
2196                  * above so we could delete the right path
2197                  * 1st.
2198                  */
2199                 if (right_has_empty)
2200                         ocfs2_remove_empty_extent(left_leaf_el);
2201
2202                 ret = ocfs2_journal_dirty(handle, di_bh);
2203                 if (ret)
2204                         mlog_errno(ret);
2205
2206                 *deleted = 1;
2207         } else
2208                 ocfs2_complete_edge_insert(inode, handle, left_path, right_path,
2209                                            subtree_index);
2210
2211 out:
2212         return ret;
2213 }
2214
2215 /*
2216  * Given a full path, determine what cpos value would return us a path
2217  * containing the leaf immediately to the right of the current one.
2218  *
2219  * Will return zero if the path passed in is already the rightmost path.
2220  *
2221  * This looks similar, but is subtly different to
2222  * ocfs2_find_cpos_for_left_leaf().
2223  */
2224 static int ocfs2_find_cpos_for_right_leaf(struct super_block *sb,
2225                                           struct ocfs2_path *path, u32 *cpos)
2226 {
2227         int i, j, ret = 0;
2228         u64 blkno;
2229         struct ocfs2_extent_list *el;
2230
2231         *cpos = 0;
2232
2233         if (path->p_tree_depth == 0)
2234                 return 0;
2235
2236         blkno = path_leaf_bh(path)->b_blocknr;
2237
2238         /* Start at the tree node just above the leaf and work our way up. */
2239         i = path->p_tree_depth - 1;
2240         while (i >= 0) {
2241                 int next_free;
2242
2243                 el = path->p_node[i].el;
2244
2245                 /*
2246                  * Find the extent record just after the one in our
2247                  * path.
2248                  */
2249                 next_free = le16_to_cpu(el->l_next_free_rec);
2250                 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) {
2251                         if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) {
2252                                 if (j == (next_free - 1)) {
2253                                         if (i == 0) {
2254                                                 /*
2255                                                  * We've determined that the
2256                                                  * path specified is already
2257                                                  * the rightmost one - return a
2258                                                  * cpos of zero.
2259                                                  */
2260                                                 goto out;
2261                                         }
2262                                         /*
2263                                          * The rightmost record points to our
2264                                          * leaf - we need to travel up the
2265                                          * tree one level.
2266                                          */
2267                                         goto next_node;
2268                                 }
2269
2270                                 *cpos = le32_to_cpu(el->l_recs[j + 1].e_cpos);
2271                                 goto out;
2272                         }
2273                 }
2274
2275                 /*
2276                  * If we got here, we never found a valid node where
2277                  * the tree indicated one should be.
2278                  */
2279                 ocfs2_error(sb,
2280                             "Invalid extent tree at extent block %llu\n",
2281                             (unsigned long long)blkno);
2282                 ret = -EROFS;
2283                 goto out;
2284
2285 next_node:
2286                 blkno = path->p_node[i].bh->b_blocknr;
2287                 i--;
2288         }
2289
2290 out:
2291         return ret;
2292 }
2293
2294 static int ocfs2_rotate_rightmost_leaf_left(struct inode *inode,
2295                                             handle_t *handle,
2296                                             struct buffer_head *bh,
2297                                             struct ocfs2_extent_list *el)
2298 {
2299         int ret;
2300
2301         if (!ocfs2_is_empty_extent(&el->l_recs[0]))
2302                 return 0;
2303
2304         ret = ocfs2_journal_access(handle, inode, bh,
2305                                    OCFS2_JOURNAL_ACCESS_WRITE);
2306         if (ret) {
2307                 mlog_errno(ret);
2308                 goto out;
2309         }
2310
2311         ocfs2_remove_empty_extent(el);
2312
2313         ret = ocfs2_journal_dirty(handle, bh);
2314         if (ret)
2315                 mlog_errno(ret);
2316
2317 out:
2318         return ret;
2319 }
2320
2321 static int __ocfs2_rotate_tree_left(struct inode *inode,
2322                                     handle_t *handle, int orig_credits,
2323                                     struct ocfs2_path *path,
2324                                     struct ocfs2_cached_dealloc_ctxt *dealloc,
2325                                     struct ocfs2_path **empty_extent_path)
2326 {
2327         int ret, subtree_root, deleted;
2328         u32 right_cpos;
2329         struct ocfs2_path *left_path = NULL;
2330         struct ocfs2_path *right_path = NULL;
2331
2332         BUG_ON(!ocfs2_is_empty_extent(&(path_leaf_el(path)->l_recs[0])));
2333
2334         *empty_extent_path = NULL;
2335
2336         ret = ocfs2_find_cpos_for_right_leaf(inode->i_sb, path,
2337                                              &right_cpos);
2338         if (ret) {
2339                 mlog_errno(ret);
2340                 goto out;
2341         }
2342
2343         left_path = ocfs2_new_path(path_root_bh(path),
2344                                    path_root_el(path));
2345         if (!left_path) {
2346                 ret = -ENOMEM;
2347                 mlog_errno(ret);
2348                 goto out;
2349         }
2350
2351         ocfs2_cp_path(left_path, path);
2352
2353         right_path = ocfs2_new_path(path_root_bh(path),
2354                                     path_root_el(path));
2355         if (!right_path) {
2356                 ret = -ENOMEM;
2357                 mlog_errno(ret);
2358                 goto out;
2359         }
2360
2361         while (right_cpos) {
2362                 ret = ocfs2_find_path(inode, right_path, right_cpos);
2363                 if (ret) {
2364                         mlog_errno(ret);
2365                         goto out;
2366                 }
2367
2368                 subtree_root = ocfs2_find_subtree_root(inode, left_path,
2369                                                        right_path);
2370
2371                 mlog(0, "Subtree root at index %d (blk %llu, depth %d)\n",
2372                      subtree_root,
2373                      (unsigned long long)
2374                      right_path->p_node[subtree_root].bh->b_blocknr,
2375                      right_path->p_tree_depth);
2376
2377                 ret = ocfs2_extend_rotate_transaction(handle, subtree_root,
2378                                                       orig_credits, left_path);
2379                 if (ret) {
2380                         mlog_errno(ret);
2381                         goto out;
2382                 }
2383
2384                 /*
2385                  * Caller might still want to make changes to the
2386                  * tree root, so re-add it to the journal here.
2387                  */
2388                 ret = ocfs2_journal_access(handle, inode,
2389                                            path_root_bh(left_path),
2390                                            OCFS2_JOURNAL_ACCESS_WRITE);
2391                 if (ret) {
2392                         mlog_errno(ret);
2393                         goto out;
2394                 }
2395
2396                 ret = ocfs2_rotate_subtree_left(inode, handle, left_path,
2397                                                 right_path, subtree_root,
2398                                                 dealloc, &deleted);
2399                 if (ret == -EAGAIN) {
2400                         /*
2401                          * The rotation has to temporarily stop due to
2402                          * the right subtree having an empty
2403                          * extent. Pass it back to the caller for a
2404                          * fixup.
2405                          */
2406                         *empty_extent_path = right_path;
2407                         right_path = NULL;
2408                         goto out;
2409                 }
2410                 if (ret) {
2411                         mlog_errno(ret);
2412                         goto out;
2413                 }
2414
2415                 /*
2416                  * The subtree rotate might have removed records on
2417                  * the rightmost edge. If so, then rotation is
2418                  * complete.
2419                  */
2420                 if (deleted)
2421                         break;
2422
2423                 ocfs2_mv_path(left_path, right_path);
2424
2425                 ret = ocfs2_find_cpos_for_right_leaf(inode->i_sb, left_path,
2426                                                      &right_cpos);
2427                 if (ret) {
2428                         mlog_errno(ret);
2429                         goto out;
2430                 }
2431         }
2432
2433 out:
2434         ocfs2_free_path(right_path);
2435         ocfs2_free_path(left_path);
2436
2437         return ret;
2438 }
2439
2440 static int ocfs2_remove_rightmost_path(struct inode *inode, handle_t *handle,
2441                                        struct ocfs2_path *path,
2442                                        struct ocfs2_cached_dealloc_ctxt *dealloc)
2443 {
2444         int ret, subtree_index;
2445         u32 cpos;
2446         struct ocfs2_path *left_path = NULL;
2447         struct ocfs2_dinode *di;
2448         struct ocfs2_extent_block *eb;
2449         struct ocfs2_extent_list *el;
2450
2451         /*
2452          * XXX: This code assumes that the root is an inode, which is
2453          * true for now but may change as tree code gets generic.
2454          */
2455         di = (struct ocfs2_dinode *)path_root_bh(path)->b_data;
2456         if (!OCFS2_IS_VALID_DINODE(di)) {
2457                 ret = -EIO;
2458                 ocfs2_error(inode->i_sb,
2459                             "Inode %llu has invalid path root",
2460                             (unsigned long long)OCFS2_I(inode)->ip_blkno);
2461                 goto out;
2462         }
2463
2464         /*
2465          * There's two ways we handle this depending on
2466          * whether path is the only existing one.
2467          */
2468         ret = ocfs2_extend_rotate_transaction(handle, 0,
2469                                               handle->h_buffer_credits,
2470                                               path);
2471         if (ret) {
2472                 mlog_errno(ret);
2473                 goto out;
2474         }
2475
2476         ret = ocfs2_journal_access_path(inode, handle, path);
2477         if (ret) {
2478                 mlog_errno(ret);
2479                 goto out;
2480         }
2481
2482         ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos);
2483         if (ret) {
2484                 mlog_errno(ret);
2485                 goto out;
2486         }
2487
2488         if (cpos) {
2489                 /*
2490                  * We have a path to the left of this one - it needs
2491                  * an update too.
2492                  */
2493                 left_path = ocfs2_new_path(path_root_bh(path),
2494                                            path_root_el(path));
2495                 if (!left_path) {
2496                         ret = -ENOMEM;
2497                         mlog_errno(ret);
2498                         goto out;
2499                 }
2500
2501                 ret = ocfs2_find_path(inode, left_path, cpos);
2502                 if (ret) {
2503                         mlog_errno(ret);
2504                         goto out;
2505                 }
2506
2507                 ret = ocfs2_journal_access_path(inode, handle, left_path);
2508                 if (ret) {
2509                         mlog_errno(ret);
2510                         goto out;
2511                 }
2512
2513                 subtree_index = ocfs2_find_subtree_root(inode, left_path, path);
2514
2515                 ocfs2_unlink_subtree(inode, handle, left_path, path,
2516                                      subtree_index, dealloc);
2517                 ocfs2_update_edge_lengths(inode, handle, left_path);
2518
2519                 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2520                 di->i_last_eb_blk = eb->h_blkno;
2521         } else {
2522                 /*
2523                  * 'path' is also the leftmost path which
2524                  * means it must be the only one. This gets
2525                  * handled differently because we want to
2526                  * revert the inode back to having extents
2527                  * in-line.
2528                  */
2529                 ocfs2_unlink_path(inode, handle, dealloc, path, 1);
2530
2531                 el = &di->id2.i_list;
2532                 el->l_tree_depth = 0;
2533                 el->l_next_free_rec = 0;
2534                 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2535
2536                 di->i_last_eb_blk = 0;
2537         }
2538
2539         ocfs2_journal_dirty(handle, path_root_bh(path));
2540
2541 out:
2542         ocfs2_free_path(left_path);
2543         return ret;
2544 }
2545
2546 /*
2547  * Left rotation of btree records.
2548  *
2549  * In many ways, this is (unsurprisingly) the opposite of right
2550  * rotation. We start at some non-rightmost path containing an empty
2551  * extent in the leaf block. The code works its way to the rightmost
2552  * path by rotating records to the left in every subtree.
2553  *
2554  * This is used by any code which reduces the number of extent records
2555  * in a leaf. After removal, an empty record should be placed in the
2556  * leftmost list position.
2557  *
2558  * This won't handle a length update of the rightmost path records if
2559  * the rightmost tree leaf record is removed so the caller is
2560  * responsible for detecting and correcting that.
2561  */
2562 static int ocfs2_rotate_tree_left(struct inode *inode, handle_t *handle,
2563                                   struct ocfs2_path *path,
2564                                   struct ocfs2_cached_dealloc_ctxt *dealloc)
2565 {
2566         int ret, orig_credits = handle->h_buffer_credits;
2567         struct ocfs2_path *tmp_path = NULL, *restart_path = NULL;
2568         struct ocfs2_extent_block *eb;
2569         struct ocfs2_extent_list *el;
2570
2571         el = path_leaf_el(path);
2572         if (!ocfs2_is_empty_extent(&el->l_recs[0]))
2573                 return 0;
2574
2575         if (path->p_tree_depth == 0) {
2576 rightmost_no_delete:
2577                 /*
2578                  * In-inode extents. This is trivially handled, so do
2579                  * it up front.
2580                  */
2581                 ret = ocfs2_rotate_rightmost_leaf_left(inode, handle,
2582                                                        path_leaf_bh(path),
2583                                                        path_leaf_el(path));
2584                 if (ret)
2585                         mlog_errno(ret);
2586                 goto out;
2587         }
2588
2589         /*
2590          * Handle rightmost branch now. There's several cases:
2591          *  1) simple rotation leaving records in there. That's trivial.
2592          *  2) rotation requiring a branch delete - there's no more
2593          *     records left. Two cases of this:
2594          *     a) There are branches to the left.
2595          *     b) This is also the leftmost (the only) branch.
2596          *
2597          *  1) is handled via ocfs2_rotate_rightmost_leaf_left()
2598          *  2a) we need the left branch so that we can update it with the unlink
2599          *  2b) we need to bring the inode back to inline extents.
2600          */
2601
2602         eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
2603         el = &eb->h_list;
2604         if (eb->h_next_leaf_blk == 0) {
2605                 /*
2606                  * This gets a bit tricky if we're going to delete the
2607                  * rightmost path. Get the other cases out of the way
2608                  * 1st.
2609                  */
2610                 if (le16_to_cpu(el->l_next_free_rec) > 1)
2611                         goto rightmost_no_delete;
2612
2613                 if (le16_to_cpu(el->l_next_free_rec) == 0) {
2614                         ret = -EIO;
2615                         ocfs2_error(inode->i_sb,
2616                                     "Inode %llu has empty extent block at %llu",
2617                                     (unsigned long long)OCFS2_I(inode)->ip_blkno,
2618                                     (unsigned long long)le64_to_cpu(eb->h_blkno));
2619                         goto out;
2620                 }
2621
2622                 /*
2623                  * XXX: The caller can not trust "path" any more after
2624                  * this as it will have been deleted. What do we do?
2625                  *
2626                  * In theory the rotate-for-merge code will never get
2627                  * here because it'll always ask for a rotate in a
2628                  * nonempty list.
2629                  */
2630
2631                 ret = ocfs2_remove_rightmost_path(inode, handle, path,
2632                                                   dealloc);
2633                 if (ret)
2634                         mlog_errno(ret);
2635                 goto out;
2636         }
2637
2638         /*
2639          * Now we can loop, remembering the path we get from -EAGAIN
2640          * and restarting from there.
2641          */
2642 try_rotate:
2643         ret = __ocfs2_rotate_tree_left(inode, handle, orig_credits, path,
2644                                        dealloc, &restart_path);
2645         if (ret && ret != -EAGAIN) {
2646                 mlog_errno(ret);
2647                 goto out;
2648         }
2649
2650         while (ret == -EAGAIN) {
2651                 tmp_path = restart_path;
2652                 restart_path = NULL;
2653
2654                 ret = __ocfs2_rotate_tree_left(inode, handle, orig_credits,
2655                                                tmp_path, dealloc,
2656                                                &restart_path);
2657                 if (ret && ret != -EAGAIN) {
2658                         mlog_errno(ret);
2659                         goto out;
2660                 }
2661
2662                 ocfs2_free_path(tmp_path);
2663                 tmp_path = NULL;
2664
2665                 if (ret == 0)
2666                         goto try_rotate;
2667         }
2668
2669 out:
2670         ocfs2_free_path(tmp_path);
2671         ocfs2_free_path(restart_path);
2672         return ret;
2673 }
2674
2675 static void ocfs2_cleanup_merge(struct ocfs2_extent_list *el,
2676                                 int index)
2677 {
2678         struct ocfs2_extent_rec *rec = &el->l_recs[index];
2679         unsigned int size;
2680
2681         if (rec->e_leaf_clusters == 0) {
2682                 /*
2683                  * We consumed all of the merged-from record. An empty
2684                  * extent cannot exist anywhere but the 1st array
2685                  * position, so move things over if the merged-from
2686                  * record doesn't occupy that position.
2687                  *
2688                  * This creates a new empty extent so the caller
2689                  * should be smart enough to have removed any existing
2690                  * ones.
2691                  */
2692                 if (index > 0) {
2693                         BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0]));
2694                         size = index * sizeof(struct ocfs2_extent_rec);
2695                         memmove(&el->l_recs[1], &el->l_recs[0], size);
2696                 }
2697
2698                 /*
2699                  * Always memset - the caller doesn't check whether it
2700                  * created an empty extent, so there could be junk in
2701                  * the other fields.
2702                  */
2703                 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2704         }
2705 }
2706
2707 static int ocfs2_get_right_path(struct inode *inode,
2708                                 struct ocfs2_path *left_path,
2709                                 struct ocfs2_path **ret_right_path)
2710 {
2711         int ret;
2712         u32 right_cpos;
2713         struct ocfs2_path *right_path = NULL;
2714         struct ocfs2_extent_list *left_el;
2715
2716         *ret_right_path = NULL;
2717
2718         /* This function shouldn't be called for non-trees. */
2719         BUG_ON(left_path->p_tree_depth == 0);
2720
2721         left_el = path_leaf_el(left_path);
2722         BUG_ON(left_el->l_next_free_rec != left_el->l_count);
2723
2724         ret = ocfs2_find_cpos_for_right_leaf(inode->i_sb, left_path,
2725                                              &right_cpos);
2726         if (ret) {
2727                 mlog_errno(ret);
2728                 goto out;
2729         }
2730
2731         /* This function shouldn't be called for the rightmost leaf. */
2732         BUG_ON(right_cpos == 0);
2733
2734         right_path = ocfs2_new_path(path_root_bh(left_path),
2735                                     path_root_el(left_path));
2736         if (!right_path) {
2737                 ret = -ENOMEM;
2738                 mlog_errno(ret);
2739                 goto out;
2740         }
2741
2742         ret = ocfs2_find_path(inode, right_path, right_cpos);
2743         if (ret) {
2744                 mlog_errno(ret);
2745                 goto out;
2746         }
2747
2748         *ret_right_path = right_path;
2749 out:
2750         if (ret)
2751                 ocfs2_free_path(right_path);
2752         return ret;
2753 }
2754
2755 /*
2756  * Remove split_rec clusters from the record at index and merge them
2757  * onto the beginning of the record "next" to it.
2758  * For index < l_count - 1, the next means the extent rec at index + 1.
2759  * For index == l_count - 1, the "next" means the 1st extent rec of the
2760  * next extent block.
2761  */
2762 static int ocfs2_merge_rec_right(struct inode *inode,
2763                                  struct ocfs2_path *left_path,
2764                                  handle_t *handle,
2765                                  struct ocfs2_extent_rec *split_rec,
2766                                  int index)
2767 {
2768         int ret, next_free, i;
2769         unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters);
2770         struct ocfs2_extent_rec *left_rec;
2771         struct ocfs2_extent_rec *right_rec;
2772         struct ocfs2_extent_list *right_el;
2773         struct ocfs2_path *right_path = NULL;
2774         int subtree_index = 0;
2775         struct ocfs2_extent_list *el = path_leaf_el(left_path);
2776         struct buffer_head *bh = path_leaf_bh(left_path);
2777         struct buffer_head *root_bh = NULL;
2778
2779         BUG_ON(index >= le16_to_cpu(el->l_next_free_rec));
2780         left_rec = &el->l_recs[index];
2781
2782         if (index == le16_to_cpu(el->l_next_free_rec) - 1 &&
2783             le16_to_cpu(el->l_next_free_rec) == le16_to_cpu(el->l_count)) {
2784                 /* we meet with a cross extent block merge. */
2785                 ret = ocfs2_get_right_path(inode, left_path, &right_path);
2786                 if (ret) {
2787                         mlog_errno(ret);
2788                         goto out;
2789                 }
2790
2791                 right_el = path_leaf_el(right_path);
2792                 next_free = le16_to_cpu(right_el->l_next_free_rec);
2793                 BUG_ON(next_free <= 0);
2794                 right_rec = &right_el->l_recs[0];
2795                 if (ocfs2_is_empty_extent(right_rec)) {
2796                         BUG_ON(next_free <= 1);
2797                         right_rec = &right_el->l_recs[1];
2798                 }
2799
2800                 BUG_ON(le32_to_cpu(left_rec->e_cpos) +
2801                        le16_to_cpu(left_rec->e_leaf_clusters) !=
2802                        le32_to_cpu(right_rec->e_cpos));
2803
2804                 subtree_index = ocfs2_find_subtree_root(inode,
2805                                                         left_path, right_path);
2806
2807                 ret = ocfs2_extend_rotate_transaction(handle, subtree_index,
2808                                                       handle->h_buffer_credits,
2809                                                       right_path);
2810                 if (ret) {
2811                         mlog_errno(ret);
2812                         goto out;
2813                 }
2814
2815                 root_bh = left_path->p_node[subtree_index].bh;
2816                 BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
2817
2818                 ret = ocfs2_journal_access(handle, inode, root_bh,
2819                                            OCFS2_JOURNAL_ACCESS_WRITE);
2820                 if (ret) {
2821                         mlog_errno(ret);
2822                         goto out;
2823                 }
2824
2825                 for (i = subtree_index + 1;
2826                      i < path_num_items(right_path); i++) {
2827                         ret = ocfs2_journal_access(handle, inode,
2828                                                    right_path->p_node[i].bh,
2829                                                    OCFS2_JOURNAL_ACCESS_WRITE);
2830                         if (ret) {
2831                                 mlog_errno(ret);
2832                                 goto out;
2833                         }
2834
2835                         ret = ocfs2_journal_access(handle, inode,
2836                                                    left_path->p_node[i].bh,
2837                                                    OCFS2_JOURNAL_ACCESS_WRITE);
2838                         if (ret) {
2839                                 mlog_errno(ret);
2840                                 goto out;
2841                         }
2842                 }
2843
2844         } else {
2845                 BUG_ON(index == le16_to_cpu(el->l_next_free_rec) - 1);
2846                 right_rec = &el->l_recs[index + 1];
2847         }
2848
2849         ret = ocfs2_journal_access(handle, inode, bh,
2850                                    OCFS2_JOURNAL_ACCESS_WRITE);
2851         if (ret) {
2852                 mlog_errno(ret);
2853                 goto out;
2854         }
2855
2856         le16_add_cpu(&left_rec->e_leaf_clusters, -split_clusters);
2857
2858         le32_add_cpu(&right_rec->e_cpos, -split_clusters);
2859         le64_add_cpu(&right_rec->e_blkno,
2860                      -ocfs2_clusters_to_blocks(inode->i_sb, split_clusters));
2861         le16_add_cpu(&right_rec->e_leaf_clusters, split_clusters);
2862
2863         ocfs2_cleanup_merge(el, index);
2864
2865         ret = ocfs2_journal_dirty(handle, bh);
2866         if (ret)
2867                 mlog_errno(ret);
2868
2869         if (right_path) {
2870                 ret = ocfs2_journal_dirty(handle, path_leaf_bh(right_path));
2871                 if (ret)
2872                         mlog_errno(ret);
2873
2874                 ocfs2_complete_edge_insert(inode, handle, left_path,
2875                                            right_path, subtree_index);
2876         }
2877 out:
2878         if (right_path)
2879                 ocfs2_free_path(right_path);
2880         return ret;
2881 }
2882
2883 static int ocfs2_get_left_path(struct inode *inode,
2884                                struct ocfs2_path *right_path,
2885                                struct ocfs2_path **ret_left_path)
2886 {
2887         int ret;
2888         u32 left_cpos;
2889         struct ocfs2_path *left_path = NULL;
2890
2891         *ret_left_path = NULL;
2892
2893         /* This function shouldn't be called for non-trees. */
2894         BUG_ON(right_path->p_tree_depth == 0);
2895
2896         ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb,
2897                                             right_path, &left_cpos);
2898         if (ret) {
2899                 mlog_errno(ret);
2900                 goto out;
2901         }
2902
2903         /* This function shouldn't be called for the leftmost leaf. */
2904         BUG_ON(left_cpos == 0);
2905
2906         left_path = ocfs2_new_path(path_root_bh(right_path),
2907                                    path_root_el(right_path));
2908         if (!left_path) {
2909                 ret = -ENOMEM;
2910                 mlog_errno(ret);
2911                 goto out;
2912         }
2913
2914         ret = ocfs2_find_path(inode, left_path, left_cpos);
2915         if (ret) {
2916                 mlog_errno(ret);
2917                 goto out;
2918         }
2919
2920         *ret_left_path = left_path;
2921 out:
2922         if (ret)
2923                 ocfs2_free_path(left_path);
2924         return ret;
2925 }
2926
2927 /*
2928  * Remove split_rec clusters from the record at index and merge them
2929  * onto the tail of the record "before" it.
2930  * For index > 0, the "before" means the extent rec at index - 1.
2931  *
2932  * For index == 0, the "before" means the last record of the previous
2933  * extent block. And there is also a situation that we may need to
2934  * remove the rightmost leaf extent block in the right_path and change
2935  * the right path to indicate the new rightmost path.
2936  */
2937 static int ocfs2_merge_rec_left(struct inode *inode,
2938                                 struct ocfs2_path *right_path,
2939                                 handle_t *handle,
2940                                 struct ocfs2_extent_rec *split_rec,
2941                                 struct ocfs2_cached_dealloc_ctxt *dealloc,
2942                                 int index)
2943 {
2944         int ret, i, subtree_index = 0, has_empty_extent = 0;
2945         unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters);
2946         struct ocfs2_extent_rec *left_rec;
2947         struct ocfs2_extent_rec *right_rec;
2948         struct ocfs2_extent_list *el = path_leaf_el(right_path);
2949         struct buffer_head *bh = path_leaf_bh(right_path);
2950         struct buffer_head *root_bh = NULL;
2951         struct ocfs2_path *left_path = NULL;
2952         struct ocfs2_extent_list *left_el;
2953
2954         BUG_ON(index < 0);
2955
2956         right_rec = &el->l_recs[index];
2957         if (index == 0) {
2958                 /* we meet with a cross extent block merge. */
2959                 ret = ocfs2_get_left_path(inode, right_path, &left_path);
2960                 if (ret) {
2961                         mlog_errno(ret);
2962                         goto out;
2963                 }
2964
2965                 left_el = path_leaf_el(left_path);
2966                 BUG_ON(le16_to_cpu(left_el->l_next_free_rec) !=
2967                        le16_to_cpu(left_el->l_count));
2968
2969                 left_rec = &left_el->l_recs[
2970                                 le16_to_cpu(left_el->l_next_free_rec) - 1];
2971                 BUG_ON(le32_to_cpu(left_rec->e_cpos) +
2972                        le16_to_cpu(left_rec->e_leaf_clusters) !=
2973                        le32_to_cpu(split_rec->e_cpos));
2974
2975                 subtree_index = ocfs2_find_subtree_root(inode,
2976                                                         left_path, right_path);
2977
2978                 ret = ocfs2_extend_rotate_transaction(handle, subtree_index,
2979                                                       handle->h_buffer_credits,
2980                                                       left_path);
2981                 if (ret) {
2982                         mlog_errno(ret);
2983                         goto out;
2984                 }
2985
2986                 root_bh = left_path->p_node[subtree_index].bh;
2987                 BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
2988
2989                 ret = ocfs2_journal_access(handle, inode, root_bh,
2990                                            OCFS2_JOURNAL_ACCESS_WRITE);
2991                 if (ret) {
2992                         mlog_errno(ret);
2993                         goto out;
2994                 }
2995
2996                 for (i = subtree_index + 1;
2997                      i < path_num_items(right_path); i++) {
2998                         ret = ocfs2_journal_access(handle, inode,
2999                                                    right_path->p_node[i].bh,
3000                                                    OCFS2_JOURNAL_ACCESS_WRITE);
3001                         if (ret) {
3002                                 mlog_errno(ret);
3003                                 goto out;
3004                         }
3005
3006                         ret = ocfs2_journal_access(handle, inode,
3007                                                    left_path->p_node[i].bh,
3008                                                    OCFS2_JOURNAL_ACCESS_WRITE);
3009                         if (ret) {
3010                                 mlog_errno(ret);
3011                                 goto out;
3012                         }
3013                 }
3014         } else {
3015                 left_rec = &el->l_recs[index - 1];
3016                 if (ocfs2_is_empty_extent(&el->l_recs[0]))
3017                         has_empty_extent = 1;
3018         }
3019
3020         ret = ocfs2_journal_access(handle, inode, bh,
3021                                    OCFS2_JOURNAL_ACCESS_WRITE);
3022         if (ret) {
3023                 mlog_errno(ret);
3024                 goto out;
3025         }
3026
3027         if (has_empty_extent && index == 1) {
3028                 /*
3029                  * The easy case - we can just plop the record right in.
3030                  */
3031                 *left_rec = *split_rec;
3032
3033                 has_empty_extent = 0;
3034         } else
3035                 le16_add_cpu(&left_rec->e_leaf_clusters, split_clusters);
3036
3037         le32_add_cpu(&right_rec->e_cpos, split_clusters);
3038         le64_add_cpu(&right_rec->e_blkno,
3039                      ocfs2_clusters_to_blocks(inode->i_sb, split_clusters));
3040         le16_add_cpu(&right_rec->e_leaf_clusters, -split_clusters);
3041
3042         ocfs2_cleanup_merge(el, index);
3043
3044         ret = ocfs2_journal_dirty(handle, bh);
3045         if (ret)
3046                 mlog_errno(ret);
3047
3048         if (left_path) {
3049                 ret = ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
3050                 if (ret)
3051                         mlog_errno(ret);
3052
3053                 /*
3054                  * In the situation that the right_rec is empty and the extent
3055                  * block is empty also,  ocfs2_complete_edge_insert can't handle
3056                  * it and we need to delete the right extent block.
3057                  */
3058                 if (le16_to_cpu(right_rec->e_leaf_clusters) == 0 &&
3059                     le16_to_cpu(el->l_next_free_rec) == 1) {
3060
3061                         ret = ocfs2_remove_rightmost_path(inode, handle,
3062                                                           right_path, dealloc);
3063                         if (ret) {
3064                                 mlog_errno(ret);
3065                                 goto out;
3066                         }
3067
3068                         /* Now the rightmost extent block has been deleted.
3069                          * So we use the new rightmost path.
3070                          */
3071                         ocfs2_mv_path(right_path, left_path);
3072                         left_path = NULL;
3073                 } else
3074                         ocfs2_complete_edge_insert(inode, handle, left_path,
3075                                                    right_path, subtree_index);
3076         }
3077 out:
3078         if (left_path)
3079                 ocfs2_free_path(left_path);
3080         return ret;
3081 }
3082
3083 static int ocfs2_try_to_merge_extent(struct inode *inode,
3084                                      handle_t *handle,
3085                                      struct ocfs2_path *path,
3086                                      int split_index,
3087                                      struct ocfs2_extent_rec *split_rec,
3088                                      struct ocfs2_cached_dealloc_ctxt *dealloc,
3089                                      struct ocfs2_merge_ctxt *ctxt)
3090
3091 {
3092         int ret = 0;
3093         struct ocfs2_extent_list *el = path_leaf_el(path);
3094         struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
3095
3096         BUG_ON(ctxt->c_contig_type == CONTIG_NONE);
3097
3098         if (ctxt->c_split_covers_rec && ctxt->c_has_empty_extent) {
3099                 /*
3100                  * The merge code will need to create an empty
3101                  * extent to take the place of the newly
3102                  * emptied slot. Remove any pre-existing empty
3103                  * extents - having more than one in a leaf is
3104                  * illegal.
3105                  */
3106                 ret = ocfs2_rotate_tree_left(inode, handle, path,
3107                                              dealloc);
3108                 if (ret) {
3109                         mlog_errno(ret);
3110                         goto out;
3111                 }
3112                 split_index--;
3113                 rec = &el->l_recs[split_index];
3114         }
3115
3116         if (ctxt->c_contig_type == CONTIG_LEFTRIGHT) {
3117                 /*
3118                  * Left-right contig implies this.
3119                  */
3120                 BUG_ON(!ctxt->c_split_covers_rec);
3121
3122                 /*
3123                  * Since the leftright insert always covers the entire
3124                  * extent, this call will delete the insert record
3125                  * entirely, resulting in an empty extent record added to
3126                  * the extent block.
3127                  *
3128                  * Since the adding of an empty extent shifts
3129                  * everything back to the right, there's no need to
3130                  * update split_index here.
3131                  *
3132                  * When the split_index is zero, we need to merge it to the
3133                  * prevoius extent block. It is more efficient and easier
3134                  * if we do merge_right first and merge_left later.
3135                  */
3136                 ret = ocfs2_merge_rec_right(inode, path,
3137                                             handle, split_rec,
3138                                             split_index);
3139                 if (ret) {
3140                         mlog_errno(ret);
3141                         goto out;
3142                 }
3143
3144                 /*
3145                  * We can only get this from logic error above.
3146                  */
3147                 BUG_ON(!ocfs2_is_empty_extent(&el->l_recs[0]));
3148
3149                 /* The merge left us with an empty extent, remove it. */
3150                 ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc);
3151                 if (ret) {
3152                         mlog_errno(ret);
3153                         goto out;
3154                 }
3155
3156                 rec = &el->l_recs[split_index];
3157
3158                 /*
3159                  * Note that we don't pass split_rec here on purpose -
3160                  * we've merged it into the rec already.
3161                  */
3162                 ret = ocfs2_merge_rec_left(inode, path,
3163                                            handle, rec,
3164                                            dealloc,
3165                                            split_index);
3166
3167                 if (ret) {
3168                         mlog_errno(ret);
3169                         goto out;
3170                 }
3171
3172                 ret = ocfs2_rotate_tree_left(inode, handle, path,
3173                                              dealloc);
3174                 /*
3175                  * Error from this last rotate is not critical, so
3176                  * print but don't bubble it up.
3177                  */
3178                 if (ret)
3179                         mlog_errno(ret);
3180                 ret = 0;
3181         } else {
3182                 /*
3183                  * Merge a record to the left or right.
3184                  *
3185                  * 'contig_type' is relative to the existing record,
3186                  * so for example, if we're "right contig", it's to
3187                  * the record on the left (hence the left merge).
3188                  */
3189                 if (ctxt->c_contig_type == CONTIG_RIGHT) {
3190                         ret = ocfs2_merge_rec_left(inode,
3191                                                    path,
3192                                                    handle, split_rec,
3193                                                    dealloc,
3194                                                    split_index);
3195                         if (ret) {
3196                                 mlog_errno(ret);
3197                                 goto out;
3198                         }
3199                 } else {
3200                         ret = ocfs2_merge_rec_right(inode,
3201                                                     path,
3202                                                     handle, split_rec,
3203                                                     split_index);
3204                         if (ret) {
3205                                 mlog_errno(ret);
3206                                 goto out;
3207                         }
3208                 }
3209
3210                 if (ctxt->c_split_covers_rec) {
3211                         /*
3212                          * The merge may have left an empty extent in
3213                          * our leaf. Try to rotate it away.
3214                          */
3215                         ret = ocfs2_rotate_tree_left(inode, handle, path,
3216                                                      dealloc);
3217                         if (ret)
3218                                 mlog_errno(ret);
3219                         ret = 0;
3220                 }
3221         }
3222
3223 out:
3224         return ret;
3225 }
3226
3227 static void ocfs2_subtract_from_rec(struct super_block *sb,
3228                                     enum ocfs2_split_type split,
3229                                     struct ocfs2_extent_rec *rec,
3230                                     struct ocfs2_extent_rec *split_rec)
3231 {
3232         u64 len_blocks;
3233
3234         len_blocks = ocfs2_clusters_to_blocks(sb,
3235                                 le16_to_cpu(split_rec->e_leaf_clusters));
3236
3237         if (split == SPLIT_LEFT) {
3238                 /*
3239                  * Region is on the left edge of the existing
3240                  * record.
3241                  */
3242                 le32_add_cpu(&rec->e_cpos,
3243                              le16_to_cpu(split_rec->e_leaf_clusters));
3244                 le64_add_cpu(&rec->e_blkno, len_blocks);
3245                 le16_add_cpu(&rec->e_leaf_clusters,
3246                              -le16_to_cpu(split_rec->e_leaf_clusters));
3247         } else {
3248                 /*
3249                  * Region is on the right edge of the existing
3250                  * record.
3251                  */
3252                 le16_add_cpu(&rec->e_leaf_clusters,
3253                              -le16_to_cpu(split_rec->e_leaf_clusters));
3254         }
3255 }
3256
3257 /*
3258  * Do the final bits of extent record insertion at the target leaf
3259  * list. If this leaf is part of an allocation tree, it is assumed
3260  * that the tree above has been prepared.
3261  */
3262 static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec,
3263                                  struct ocfs2_extent_list *el,
3264                                  struct ocfs2_insert_type *insert,
3265                                  struct inode *inode)
3266 {
3267         int i = insert->ins_contig_index;
3268         unsigned int range;
3269         struct ocfs2_extent_rec *rec;
3270
3271         BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
3272
3273         if (insert->ins_split != SPLIT_NONE) {
3274                 i = ocfs2_search_extent_list(el, le32_to_cpu(insert_rec->e_cpos));
3275                 BUG_ON(i == -1);
3276                 rec = &el->l_recs[i];
3277                 ocfs2_subtract_from_rec(inode->i_sb, insert->ins_split, rec,
3278                                         insert_rec);
3279                 goto rotate;
3280         }
3281
3282         /*
3283          * Contiguous insert - either left or right.
3284          */
3285         if (insert->ins_contig != CONTIG_NONE) {
3286                 rec = &el->l_recs[i];
3287                 if (insert->ins_contig == CONTIG_LEFT) {
3288                         rec->e_blkno = insert_rec->e_blkno;
3289                         rec->e_cpos = insert_rec->e_cpos;
3290                 }
3291                 le16_add_cpu(&rec->e_leaf_clusters,
3292                              le16_to_cpu(insert_rec->e_leaf_clusters));
3293                 return;
3294         }
3295
3296         /*
3297          * Handle insert into an empty leaf.
3298          */
3299         if (le16_to_cpu(el->l_next_free_rec) == 0 ||
3300             ((le16_to_cpu(el->l_next_free_rec) == 1) &&
3301              ocfs2_is_empty_extent(&el->l_recs[0]))) {
3302                 el->l_recs[0] = *insert_rec;
3303                 el->l_next_free_rec = cpu_to_le16(1);
3304                 return;
3305         }
3306
3307         /*
3308          * Appending insert.
3309          */
3310         if (insert->ins_appending == APPEND_TAIL) {
3311                 i = le16_to_cpu(el->l_next_free_rec) - 1;
3312                 rec = &el->l_recs[i];
3313                 range = le32_to_cpu(rec->e_cpos)
3314                         + le16_to_cpu(rec->e_leaf_clusters);
3315                 BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range);
3316
3317                 mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >=
3318                                 le16_to_cpu(el->l_count),
3319                                 "inode %lu, depth %u, count %u, next free %u, "
3320                                 "rec.cpos %u, rec.clusters %u, "
3321                                 "insert.cpos %u, insert.clusters %u\n",
3322                                 inode->i_ino,
3323                                 le16_to_cpu(el->l_tree_depth),
3324                                 le16_to_cpu(el->l_count),
3325                                 le16_to_cpu(el->l_next_free_rec),
3326                                 le32_to_cpu(el->l_recs[i].e_cpos),
3327                                 le16_to_cpu(el->l_recs[i].e_leaf_clusters),
3328                                 le32_to_cpu(insert_rec->e_cpos),
3329                                 le16_to_cpu(insert_rec->e_leaf_clusters));
3330                 i++;
3331                 el->l_recs[i] = *insert_rec;
3332                 le16_add_cpu(&el->l_next_free_rec, 1);
3333                 return;
3334         }
3335
3336 rotate:
3337         /*
3338          * Ok, we have to rotate.
3339          *
3340          * At this point, it is safe to assume that inserting into an
3341          * empty leaf and appending to a leaf have both been handled
3342          * above.
3343          *
3344          * This leaf needs to have space, either by the empty 1st
3345          * extent record, or by virtue of an l_next_rec < l_count.
3346          */
3347         ocfs2_rotate_leaf(el, insert_rec);
3348 }
3349
3350 static inline void ocfs2_update_dinode_clusters(struct inode *inode,
3351                                                 struct ocfs2_dinode *di,
3352                                                 u32 clusters)
3353 {
3354         le32_add_cpu(&di->i_clusters, clusters);
3355         spin_lock(&OCFS2_I(inode)->ip_lock);
3356         OCFS2_I(inode)->ip_clusters = le32_to_cpu(di->i_clusters);
3357         spin_unlock(&OCFS2_I(inode)->ip_lock);
3358 }
3359
3360 static void ocfs2_adjust_rightmost_records(struct inode *inode,
3361                                            handle_t *handle,
3362                                            struct ocfs2_path *path,
3363                                            struct ocfs2_extent_rec *insert_rec)
3364 {
3365         int ret, i, next_free;
3366         struct buffer_head *bh;
3367         struct ocfs2_extent_list *el;
3368         struct ocfs2_extent_rec *rec;
3369
3370         /*
3371          * Update everything except the leaf block.
3372          */
3373         for (i = 0; i < path->p_tree_depth; i++) {
3374                 bh = path->p_node[i].bh;
3375                 el = path->p_node[i].el;
3376
3377                 next_free = le16_to_cpu(el->l_next_free_rec);
3378                 if (next_free == 0) {
3379                         ocfs2_error(inode->i_sb,
3380                                     "Dinode %llu has a bad extent list",
3381                                     (unsigned long long)OCFS2_I(inode)->ip_blkno);
3382                         ret = -EIO;
3383                         return;
3384                 }
3385
3386                 rec = &el->l_recs[next_free - 1];
3387
3388                 rec->e_int_clusters = insert_rec->e_cpos;
3389                 le32_add_cpu(&rec->e_int_clusters,
3390                              le16_to_cpu(insert_rec->e_leaf_clusters));
3391                 le32_add_cpu(&rec->e_int_clusters,
3392                              -le32_to_cpu(rec->e_cpos));
3393
3394                 ret = ocfs2_journal_dirty(handle, bh);
3395                 if (ret)
3396                         mlog_errno(ret);
3397
3398         }
3399 }
3400
3401 static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle,
3402                                     struct ocfs2_extent_rec *insert_rec,
3403                                     struct ocfs2_path *right_path,
3404                                     struct ocfs2_path **ret_left_path)
3405 {
3406         int ret, next_free;
3407         struct ocfs2_extent_list *el;
3408         struct ocfs2_path *left_path = NULL;
3409
3410         *ret_left_path = NULL;
3411
3412         /*
3413          * This shouldn't happen for non-trees. The extent rec cluster
3414          * count manipulation below only works for interior nodes.
3415          */
3416         BUG_ON(right_path->p_tree_depth == 0);
3417
3418         /*
3419          * If our appending insert is at the leftmost edge of a leaf,
3420          * then we might need to update the rightmost records of the
3421          * neighboring path.
3422          */
3423         el = path_leaf_el(right_path);
3424         next_free = le16_to_cpu(el->l_next_free_rec);
3425         if (next_free == 0 ||
3426             (next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) {
3427                 u32 left_cpos;
3428
3429                 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path,
3430                                                     &left_cpos);
3431                 if (ret) {
3432                         mlog_errno(ret);
3433                         goto out;
3434                 }
3435
3436                 mlog(0, "Append may need a left path update. cpos: %u, "
3437                      "left_cpos: %u\n", le32_to_cpu(insert_rec->e_cpos),
3438                      left_cpos);
3439
3440                 /*
3441                  * No need to worry if the append is already in the
3442                  * leftmost leaf.
3443                  */
3444                 if (left_cpos) {
3445                         left_path = ocfs2_new_path(path_root_bh(right_path),
3446                                                    path_root_el(right_path));
3447                         if (!left_path) {
3448                                 ret = -ENOMEM;
3449                                 mlog_errno(ret);
3450                                 goto out;
3451                         }
3452
3453                         ret = ocfs2_find_path(inode, left_path, left_cpos);
3454                         if (ret) {
3455                                 mlog_errno(ret);
3456                                 goto out;
3457                         }
3458
3459                         /*
3460                          * ocfs2_insert_path() will pass the left_path to the
3461                          * journal for us.
3462                          */
3463                 }
3464         }
3465
3466         ret = ocfs2_journal_access_path(inode, handle, right_path);
3467         if (ret) {
3468                 mlog_errno(ret);
3469                 goto out;
3470         }
3471
3472         ocfs2_adjust_rightmost_records(inode, handle, right_path, insert_rec);
3473
3474         *ret_left_path = left_path;
3475         ret = 0;
3476 out:
3477         if (ret != 0)
3478                 ocfs2_free_path(left_path);
3479
3480         return ret;
3481 }
3482
3483 static void ocfs2_split_record(struct inode *inode,
3484                                struct ocfs2_path *left_path,
3485                                struct ocfs2_path *right_path,
3486                                struct ocfs2_extent_rec *split_rec,
3487                                enum ocfs2_split_type split)
3488 {
3489         int index;
3490         u32 cpos = le32_to_cpu(split_rec->e_cpos);
3491         struct ocfs2_extent_list *left_el = NULL, *right_el, *insert_el, *el;
3492         struct ocfs2_extent_rec *rec, *tmprec;
3493
3494         right_el = path_leaf_el(right_path);;
3495         if (left_path)
3496                 left_el = path_leaf_el(left_path);
3497
3498         el = right_el;
3499         insert_el = right_el;
3500         index = ocfs2_search_extent_list(el, cpos);
3501         if (index != -1) {
3502                 if (index == 0 && left_path) {
3503                         BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0]));
3504
3505                         /*
3506                          * This typically means that the record
3507                          * started in the left path but moved to the
3508                          * right as a result of rotation. We either
3509                          * move the existing record to the left, or we
3510                          * do the later insert there.
3511                          *
3512                          * In this case, the left path should always
3513                          * exist as the rotate code will have passed
3514                          * it back for a post-insert update.
3515                          */
3516
3517                         if (split == SPLIT_LEFT) {
3518                                 /*
3519                                  * It's a left split. Since we know
3520                                  * that the rotate code gave us an
3521                                  * empty extent in the left path, we
3522                                  * can just do the insert there.
3523                                  */
3524                                 insert_el = left_el;
3525                         } else {
3526                                 /*
3527                                  * Right split - we have to move the
3528                                  * existing record over to the left
3529                                  * leaf. The insert will be into the
3530                                  * newly created empty extent in the
3531                                  * right leaf.
3532                                  */
3533                                 tmprec = &right_el->l_recs[index];
3534                                 ocfs2_rotate_leaf(left_el, tmprec);
3535                                 el = left_el;
3536
3537                                 memset(tmprec, 0, sizeof(*tmprec));
3538                                 index = ocfs2_search_extent_list(left_el, cpos);
3539                                 BUG_ON(index == -1);
3540                         }
3541                 }
3542         } else {
3543                 BUG_ON(!left_path);
3544                 BUG_ON(!ocfs2_is_empty_extent(&left_el->l_recs[0]));
3545                 /*
3546                  * Left path is easy - we can just allow the insert to
3547                  * happen.
3548                  */
3549                 el = left_el;
3550                 insert_el = left_el;
3551                 index = ocfs2_search_extent_list(el, cpos);
3552                 BUG_ON(index == -1);
3553         }
3554
3555         rec = &el->l_recs[index];
3556         ocfs2_subtract_from_rec(inode->i_sb, split, rec, split_rec);
3557         ocfs2_rotate_leaf(insert_el, split_rec);
3558 }
3559
3560 /*
3561  * This function only does inserts on an allocation b-tree. For dinode
3562  * lists, ocfs2_insert_at_leaf() is called directly.
3563  *
3564  * right_path is the path we want to do the actual insert
3565  * in. left_path should only be passed in if we need to update that
3566  * portion of the tree after an edge insert.
3567  */
3568 static int ocfs2_insert_path(struct inode *inode,
3569                              handle_t *handle,
3570                              struct ocfs2_path *left_path,
3571                              struct ocfs2_path *right_path,
3572                              struct ocfs2_extent_rec *insert_rec,
3573                              struct ocfs2_insert_type *insert)
3574 {
3575         int ret, subtree_index;
3576         struct buffer_head *leaf_bh = path_leaf_bh(right_path);
3577
3578         if (left_path) {
3579                 int credits = handle->h_buffer_credits;
3580
3581                 /*
3582                  * There's a chance that left_path got passed back to
3583                  * us without being accounted for in the
3584                  * journal. Extend our transaction here to be sure we
3585                  * can change those blocks.
3586                  */
3587                 credits += left_path->p_tree_depth;
3588
3589                 ret = ocfs2_extend_trans(handle, credits);
3590                 if (ret < 0) {
3591                         mlog_errno(ret);
3592                         goto out;
3593                 }
3594
3595                 ret = ocfs2_journal_access_path(inode, handle, left_path);
3596                 if (ret < 0) {
3597                         mlog_errno(ret);
3598                         goto out;
3599                 }
3600         }
3601
3602         /*
3603          * Pass both paths to the journal. The majority of inserts
3604          * will be touching all components anyway.
3605          */
3606         ret = ocfs2_journal_access_path(inode, handle, right_path);
3607         if (ret < 0) {
3608                 mlog_errno(ret);
3609                 goto out;
3610         }
3611
3612         if (insert->ins_split != SPLIT_NONE) {
3613                 /*
3614                  * We could call ocfs2_insert_at_leaf() for some types
3615                  * of splits, but it's easier to just let one separate
3616                  * function sort it all out.
3617                  */
3618                 ocfs2_split_record(inode, left_path, right_path,
3619                                    insert_rec, insert->ins_split);
3620
3621                 /*
3622                  * Split might have modified either leaf and we don't
3623                  * have a guarantee that the later edge insert will
3624                  * dirty this for us.
3625                  */
3626                 if (left_path)
3627                         ret = ocfs2_journal_dirty(handle,
3628                                                   path_leaf_bh(left_path));
3629                         if (ret)
3630                                 mlog_errno(ret);
3631         } else
3632                 ocfs2_insert_at_leaf(insert_rec, path_leaf_el(right_path),
3633                                      insert, inode);
3634
3635         ret = ocfs2_journal_dirty(handle, leaf_bh);
3636         if (ret)
3637                 mlog_errno(ret);
3638
3639         if (left_path) {
3640                 /*
3641                  * The rotate code has indicated that we need to fix
3642                  * up portions of the tree after the insert.
3643                  *
3644                  * XXX: Should we extend the transaction here?
3645                  */
3646                 subtree_index = ocfs2_find_subtree_root(inode, left_path,
3647                                                         right_path);
3648                 ocfs2_complete_edge_insert(inode, handle, left_path,
3649                                            right_path, subtree_index);
3650         }
3651
3652         ret = 0;
3653 out:
3654         return ret;
3655 }
3656
3657 static int ocfs2_do_insert_extent(struct inode *inode,
3658                                   handle_t *handle,
3659                                   struct buffer_head *di_bh,
3660                                   struct ocfs2_extent_rec *insert_rec,
3661                                   struct ocfs2_insert_type *type)
3662 {
3663         int ret, rotate = 0;
3664         u32 cpos;
3665         struct ocfs2_path *right_path = NULL;
3666         struct ocfs2_path *left_path = NULL;
3667         struct ocfs2_dinode *di;
3668         struct ocfs2_extent_list *el;
3669
3670         di = (struct ocfs2_dinode *) di_bh->b_data;
3671         el = &di->id2.i_list;
3672
3673         ret = ocfs2_journal_access(handle, inode, di_bh,
3674                                    OCFS2_JOURNAL_ACCESS_WRITE);
3675         if (ret) {
3676                 mlog_errno(ret);
3677                 goto out;
3678         }
3679
3680         if (le16_to_cpu(el->l_tree_depth) == 0) {
3681                 ocfs2_insert_at_leaf(insert_rec, el, type, inode);
3682                 goto out_update_clusters;
3683         }
3684
3685         right_path = ocfs2_new_inode_path(di_bh);
3686         if (!right_path) {
3687                 ret = -ENOMEM;
3688                 mlog_errno(ret);
3689                 goto out;
3690         }
3691
3692         /*
3693          * Determine the path to start with. Rotations need the
3694          * rightmost path, everything else can go directly to the
3695          * target leaf.
3696          */
3697         cpos = le32_to_cpu(insert_rec->e_cpos);
3698         if (type->ins_appending == APPEND_NONE &&
3699             type->ins_contig == CONTIG_NONE) {
3700                 rotate = 1;
3701                 cpos = UINT_MAX;
3702         }
3703
3704         ret = ocfs2_find_path(inode, right_path, cpos);
3705         if (ret) {
3706                 mlog_errno(ret);
3707                 goto out;
3708         }
3709
3710         /*
3711          * Rotations and appends need special treatment - they modify
3712          * parts of the tree's above them.
3713          *
3714          * Both might pass back a path immediate to the left of the
3715          * one being inserted to. This will be cause
3716          * ocfs2_insert_path() to modify the rightmost records of
3717          * left_path to account for an edge insert.
3718          *
3719          * XXX: When modifying this code, keep in mind that an insert
3720          * can wind up skipping both of these two special cases...
3721          */
3722         if (rotate) {
3723                 ret = ocfs2_rotate_tree_right(inode, handle, type->ins_split,
3724                                               le32_to_cpu(insert_rec->e_cpos),
3725                                               right_path, &left_path);
3726                 if (ret) {
3727                         mlog_errno(ret);
3728                         goto out;
3729                 }
3730
3731                 /*
3732                  * ocfs2_rotate_tree_right() might have extended the
3733                  * transaction without re-journaling our tree root.
3734                  */
3735                 ret = ocfs2_journal_access(handle, inode, di_bh,
3736                                            OCFS2_JOURNAL_ACCESS_WRITE);
3737                 if (ret) {
3738                         mlog_errno(ret);
3739                         goto out;
3740                 }
3741         } else if (type->ins_appending == APPEND_TAIL
3742                    && type->ins_contig != CONTIG_LEFT) {
3743                 ret = ocfs2_append_rec_to_path(inode, handle, insert_rec,
3744                                                right_path, &left_path);
3745                 if (ret) {
3746                         mlog_errno(ret);
3747                         goto out;
3748                 }
3749         }
3750
3751         ret = ocfs2_insert_path(inode, handle, left_path, right_path,
3752                                 insert_rec, type);
3753         if (ret) {
3754                 mlog_errno(ret);
3755                 goto out;
3756         }
3757
3758 out_update_clusters:
3759         if (type->ins_split == SPLIT_NONE)
3760                 ocfs2_update_dinode_clusters(inode, di,
3761                                              le16_to_cpu(insert_rec->e_leaf_clusters));
3762
3763         ret = ocfs2_journal_dirty(handle, di_bh);
3764         if (ret)
3765                 mlog_errno(ret);
3766
3767 out:
3768         ocfs2_free_path(left_path);
3769         ocfs2_free_path(right_path);
3770
3771         return ret;
3772 }
3773
3774 static enum ocfs2_contig_type
3775 ocfs2_figure_merge_contig_type(struct inode *inode, struct ocfs2_path *path,
3776                                struct ocfs2_extent_list *el, int index,
3777                                struct ocfs2_extent_rec *split_rec)
3778 {
3779         int status;
3780         enum ocfs2_contig_type ret = CONTIG_NONE;
3781         u32 left_cpos, right_cpos;
3782         struct ocfs2_extent_rec *rec = NULL;
3783         struct ocfs2_extent_list *new_el;
3784         struct ocfs2_path *left_path = NULL, *right_path = NULL;
3785         struct buffer_head *bh;
3786         struct ocfs2_extent_block *eb;
3787
3788         if (index > 0) {
3789                 rec = &el->l_recs[index - 1];
3790         } else if (path->p_tree_depth > 0) {
3791                 status = ocfs2_find_cpos_for_left_leaf(inode->i_sb,
3792                                                        path, &left_cpos);
3793                 if (status)
3794                         goto out;
3795
3796                 if (left_cpos != 0) {
3797                         left_path = ocfs2_new_path(path_root_bh(path),
3798                                                    path_root_el(path));
3799                         if (!left_path)
3800                                 goto out;
3801
3802                         status = ocfs2_find_path(inode, left_path, left_cpos);
3803                         if (status)
3804                                 goto out;
3805
3806                         new_el = path_leaf_el(left_path);
3807
3808                         if (le16_to_cpu(new_el->l_next_free_rec) !=
3809                             le16_to_cpu(new_el->l_count)) {
3810                                 bh = path_leaf_bh(left_path);
3811                                 eb = (struct ocfs2_extent_block *)bh->b_data;
3812                                 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb,
3813                                                                  eb);
3814                                 goto out;
3815                         }
3816                         rec = &new_el->l_recs[
3817                                 le16_to_cpu(new_el->l_next_free_rec) - 1];
3818                 }
3819         }
3820
3821         /*
3822          * We're careful to check for an empty extent record here -
3823          * the merge code will know what to do if it sees one.
3824          */
3825         if (rec) {
3826                 if (index == 1 && ocfs2_is_empty_extent(rec)) {
3827                         if (split_rec->e_cpos == el->l_recs[index].e_cpos)
3828                                 ret = CONTIG_RIGHT;
3829                 } else {
3830                         ret = ocfs2_extent_contig(inode, rec, split_rec);
3831                 }
3832         }
3833
3834         rec = NULL;
3835         if (index < (le16_to_cpu(el->l_next_free_rec) - 1))
3836                 rec = &el->l_recs[index + 1];
3837         else if (le16_to_cpu(el->l_next_free_rec) == le16_to_cpu(el->l_count) &&
3838                  path->p_tree_depth > 0) {
3839                 status = ocfs2_find_cpos_for_right_leaf(inode->i_sb,
3840                                                         path, &right_cpos);
3841                 if (status)
3842                         goto out;
3843
3844                 if (right_cpos == 0)
3845                         goto out;
3846
3847                 right_path = ocfs2_new_path(path_root_bh(path),
3848                                             path_root_el(path));
3849                 if (!right_path)
3850                         goto out;
3851
3852                 status = ocfs2_find_path(inode, right_path, right_cpos);
3853                 if (status)
3854                         goto out;
3855
3856                 new_el = path_leaf_el(right_path);
3857                 rec = &new_el->l_recs[0];
3858                 if (ocfs2_is_empty_extent(rec)) {
3859                         if (le16_to_cpu(new_el->l_next_free_rec) <= 1) {
3860                                 bh = path_leaf_bh(right_path);
3861                                 eb = (struct ocfs2_extent_block *)bh->b_data;
3862                                 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb,
3863                                                                  eb);
3864                                 goto out;
3865                         }
3866                         rec = &new_el->l_recs[1];
3867                 }
3868         }
3869
3870         if (rec) {
3871                 enum ocfs2_contig_type contig_type;
3872
3873                 contig_type = ocfs2_extent_contig(inode, rec, split_rec);
3874
3875                 if (contig_type == CONTIG_LEFT && ret == CONTIG_RIGHT)
3876                         ret = CONTIG_LEFTRIGHT;
3877                 else if (ret == CONTIG_NONE)
3878                         ret = contig_type;
3879         }
3880
3881 out:
3882         if (left_path)
3883                 ocfs2_free_path(left_path);
3884         if (right_path)
3885                 ocfs2_free_path(right_path);
3886
3887         return ret;
3888 }
3889
3890 static void ocfs2_figure_contig_type(struct inode *inode,
3891                                      struct ocfs2_insert_type *insert,
3892                                      struct ocfs2_extent_list *el,
3893                                      struct ocfs2_extent_rec *insert_rec)
3894 {
3895         int i;
3896         enum ocfs2_contig_type contig_type = CONTIG_NONE;
3897
3898         BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
3899
3900         for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) {
3901                 contig_type = ocfs2_extent_contig(inode, &el->l_recs[i],
3902                                                   insert_rec);
3903                 if (contig_type != CONTIG_NONE) {
3904                         insert->ins_contig_index = i;
3905                         break;
3906                 }
3907         }
3908         insert->ins_contig = contig_type;
3909 }
3910
3911 /*
3912  * This should only be called against the righmost leaf extent list.
3913  *
3914  * ocfs2_figure_appending_type() will figure out whether we'll have to
3915  * insert at the tail of the rightmost leaf.
3916  *
3917  * This should also work against the dinode list for tree's with 0
3918  * depth. If we consider the dinode list to be the rightmost leaf node
3919  * then the logic here makes sense.
3920  */
3921 static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert,
3922                                         struct ocfs2_extent_list *el,
3923                                         struct ocfs2_extent_rec *insert_rec)
3924 {
3925         int i;
3926         u32 cpos = le32_to_cpu(insert_rec->e_cpos);
3927         struct ocfs2_extent_rec *rec;
3928
3929         insert->ins_appending = APPEND_NONE;
3930
3931         BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
3932
3933         if (!el->l_next_free_rec)
3934                 goto set_tail_append;
3935
3936         if (ocfs2_is_empty_extent(&el->l_recs[0])) {
3937                 /* Were all records empty? */
3938                 if (le16_to_cpu(el->l_next_free_rec) == 1)
3939                         goto set_tail_append;
3940         }
3941
3942         i = le16_to_cpu(el->l_next_free_rec) - 1;
3943         rec = &el->l_recs[i];
3944
3945         if (cpos >=
3946             (le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)))
3947                 goto set_tail_append;
3948
3949         return;
3950
3951 set_tail_append:
3952         insert->ins_appending = APPEND_TAIL;
3953 }
3954
3955 /*
3956  * Helper function called at the begining of an insert.
3957  *
3958  * This computes a few things that are commonly used in the process of
3959  * inserting into the btree:
3960  *   - Whether the new extent is contiguous with an existing one.
3961  *   - The current tree depth.
3962  *   - Whether the insert is an appending one.
3963  *   - The total # of free records in the tree.
3964  *
3965  * All of the information is stored on the ocfs2_insert_type
3966  * structure.
3967  */
3968 static int ocfs2_figure_insert_type(struct inode *inode,
3969                                     struct buffer_head *di_bh,
3970                                     struct buffer_head **last_eb_bh,
3971                                     struct ocfs2_extent_rec *insert_rec,
3972                                     int *free_records,
3973                                     struct ocfs2_insert_type *insert)
3974 {
3975         int ret;
3976         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
3977         struct ocfs2_extent_block *eb;
3978         struct ocfs2_extent_list *el;
3979         struct ocfs2_path *path = NULL;
3980         struct buffer_head *bh = NULL;
3981
3982         insert->ins_split = SPLIT_NONE;
3983
3984         el = &di->id2.i_list;
3985         insert->ins_tree_depth = le16_to_cpu(el->l_tree_depth);
3986
3987         if (el->l_tree_depth) {
3988                 /*
3989                  * If we have tree depth, we read in the
3990                  * rightmost extent block ahead of time as
3991                  * ocfs2_figure_insert_type() and ocfs2_add_branch()
3992                  * may want it later.
3993                  */
3994                 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
3995                                        le64_to_cpu(di->i_last_eb_blk), &bh,
3996                                        OCFS2_BH_CACHED, inode);
3997                 if (ret) {
3998                         mlog_exit(ret);
3999                         goto out;
4000                 }
4001                 eb = (struct ocfs2_extent_block *) bh->b_data;
4002                 el = &eb->h_list;
4003         }
4004
4005         /*
4006          * Unless we have a contiguous insert, we'll need to know if
4007          * there is room left in our allocation tree for another
4008          * extent record.
4009          *
4010          * XXX: This test is simplistic, we can search for empty
4011          * extent records too.
4012          */
4013         *free_records = le16_to_cpu(el->l_count) -
4014                 le16_to_cpu(el->l_next_free_rec);
4015
4016         if (!insert->ins_tree_depth) {
4017                 ocfs2_figure_contig_type(inode, insert, el, insert_rec);
4018                 ocfs2_figure_appending_type(insert, el, insert_rec);
4019                 return 0;
4020         }
4021
4022         path = ocfs2_new_inode_path(di_bh);
4023         if (!path) {
4024                 ret = -ENOMEM;
4025                 mlog_errno(ret);
4026                 goto out;
4027         }
4028
4029         /*
4030          * In the case that we're inserting past what the tree
4031          * currently accounts for, ocfs2_find_path() will return for
4032          * us the rightmost tree path. This is accounted for below in
4033          * the appending code.
4034          */
4035         ret = ocfs2_find_path(inode, path, le32_to_cpu(insert_rec->e_cpos));
4036         if (ret) {
4037                 mlog_errno(ret);
4038                 goto out;
4039         }
4040
4041         el = path_leaf_el(path);
4042
4043         /*
4044          * Now that we have the path, there's two things we want to determine:
4045          * 1) Contiguousness (also set contig_index if this is so)
4046          *
4047          * 2) Are we doing an append? We can trivially break this up
4048          *     into two types of appends: simple record append, or a
4049          *     rotate inside the tail leaf.
4050          */
4051         ocfs2_figure_contig_type(inode, insert, el, insert_rec);
4052
4053         /*
4054          * The insert code isn't quite ready to deal with all cases of
4055          * left contiguousness. Specifically, if it's an insert into
4056          * the 1st record in a leaf, it will require the adjustment of
4057          * cluster count on the last record of the path directly to it's
4058          * left. For now, just catch that case and fool the layers
4059          * above us. This works just fine for tree_depth == 0, which
4060          * is why we allow that above.
4061          */
4062         if (insert->ins_contig == CONTIG_LEFT &&
4063             insert->ins_contig_index == 0)
4064                 insert->ins_contig = CONTIG_NONE;
4065
4066         /*
4067          * Ok, so we can simply compare against last_eb to figure out
4068          * whether the path doesn't exist. This will only happen in
4069          * the case that we're doing a tail append, so maybe we can
4070          * take advantage of that information somehow.
4071          */
4072         if (le64_to_cpu(di->i_last_eb_blk) == path_leaf_bh(path)->b_blocknr) {
4073                 /*
4074                  * Ok, ocfs2_find_path() returned us the rightmost
4075                  * tree path. This might be an appending insert. There are
4076                  * two cases:
4077                  *    1) We're doing a true append at the tail:
4078                  *      -This might even be off the end of the leaf
4079                  *    2) We're "appending" by rotating in the tail
4080                  */
4081                 ocfs2_figure_appending_type(insert, el, insert_rec);
4082         }
4083
4084 out:
4085         ocfs2_free_path(path);
4086
4087         if (ret == 0)
4088                 *last_eb_bh = bh;
4089         else
4090                 brelse(bh);
4091         return ret;
4092 }
4093
4094 /*
4095  * Insert an extent into an inode btree.
4096  *
4097  * The caller needs to update fe->i_clusters
4098  */
4099 int ocfs2_insert_extent(struct ocfs2_super *osb,
4100                         handle_t *handle,
4101                         struct inode *inode,
4102                         struct buffer_head *fe_bh,
4103                         u32 cpos,
4104                         u64 start_blk,
4105                         u32 new_clusters,
4106                         u8 flags,
4107                         struct ocfs2_alloc_context *meta_ac)
4108 {
4109         int status;
4110         int uninitialized_var(free_records);
4111         struct buffer_head *last_eb_bh = NULL;
4112         struct ocfs2_insert_type insert = {0, };
4113         struct ocfs2_extent_rec rec;
4114
4115         BUG_ON(OCFS2_I(inode)->ip_dyn_features & OCFS2_INLINE_DATA_FL);
4116
4117         mlog(0, "add %u clusters at position %u to inode %llu\n",
4118              new_clusters, cpos, (unsigned long long)OCFS2_I(inode)->ip_blkno);
4119
4120         mlog_bug_on_msg(!ocfs2_sparse_alloc(osb) &&
4121                         (OCFS2_I(inode)->ip_clusters != cpos),
4122                         "Device %s, asking for sparse allocation: inode %llu, "
4123                         "cpos %u, clusters %u\n",
4124                         osb->dev_str,
4125                         (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos,
4126                         OCFS2_I(inode)->ip_clusters);
4127
4128         memset(&rec, 0, sizeof(rec));
4129         rec.e_cpos = cpu_to_le32(cpos);
4130         rec.e_blkno = cpu_to_le64(start_blk);
4131         rec.e_leaf_clusters = cpu_to_le16(new_clusters);
4132         rec.e_flags = flags;
4133
4134         status = ocfs2_figure_insert_type(inode, fe_bh, &last_eb_bh, &rec,
4135                                           &free_records, &insert);
4136         if (status < 0) {
4137                 mlog_errno(status);
4138                 goto bail;
4139         }
4140
4141         mlog(0, "Insert.appending: %u, Insert.Contig: %u, "
4142              "Insert.contig_index: %d, Insert.free_records: %d, "
4143              "Insert.tree_depth: %d\n",
4144              insert.ins_appending, insert.ins_contig, insert.ins_contig_index,
4145              free_records, insert.ins_tree_depth);
4146
4147         if (insert.ins_contig == CONTIG_NONE && free_records == 0) {
4148                 status = ocfs2_grow_tree(inode, handle, fe_bh,
4149                                          &insert.ins_tree_depth, &last_eb_bh,
4150                                          meta_ac);
4151                 if (status) {
4152                         mlog_errno(status);
4153                         goto bail;
4154                 }
4155         }
4156
4157         /* Finally, we can add clusters. This might rotate the tree for us. */
4158         status = ocfs2_do_insert_extent(inode, handle, fe_bh, &rec, &insert);
4159         if (status < 0)
4160                 mlog_errno(status);
4161         else
4162                 ocfs2_extent_map_insert_rec(inode, &rec);
4163
4164 bail:
4165         if (last_eb_bh)
4166                 brelse(last_eb_bh);
4167
4168         mlog_exit(status);
4169         return status;
4170 }
4171
4172 static void ocfs2_make_right_split_rec(struct super_block *sb,
4173                                        struct ocfs2_extent_rec *split_rec,
4174                                        u32 cpos,
4175                                        struct ocfs2_extent_rec *rec)
4176 {
4177         u32 rec_cpos = le32_to_cpu(rec->e_cpos);
4178         u32 rec_range = rec_cpos + le16_to_cpu(rec->e_leaf_clusters);
4179
4180         memset(split_rec, 0, sizeof(struct ocfs2_extent_rec));
4181
4182         split_rec->e_cpos = cpu_to_le32(cpos);
4183         split_rec->e_leaf_clusters = cpu_to_le16(rec_range - cpos);
4184
4185         split_rec->e_blkno = rec->e_blkno;
4186         le64_add_cpu(&split_rec->e_blkno,
4187                      ocfs2_clusters_to_blocks(sb, cpos - rec_cpos));
4188
4189         split_rec->e_flags = rec->e_flags;
4190 }
4191
4192 static int ocfs2_split_and_insert(struct inode *inode,
4193                                   handle_t *handle,
4194                                   struct ocfs2_path *path,
4195                                   struct buffer_head *di_bh,
4196                                   struct buffer_head **last_eb_bh,
4197                                   int split_index,
4198                                   struct ocfs2_extent_rec *orig_split_rec,
4199                                   struct ocfs2_alloc_context *meta_ac)
4200 {
4201         int ret = 0, depth;
4202         unsigned int insert_range, rec_range, do_leftright = 0;
4203         struct ocfs2_extent_rec tmprec;
4204         struct ocfs2_extent_list *rightmost_el;
4205         struct ocfs2_extent_rec rec;
4206         struct ocfs2_extent_rec split_rec = *orig_split_rec;
4207         struct ocfs2_insert_type insert;
4208         struct ocfs2_extent_block *eb;
4209         struct ocfs2_dinode *di;
4210
4211 leftright:
4212         /*
4213          * Store a copy of the record on the stack - it might move
4214          * around as the tree is manipulated below.
4215          */
4216         rec = path_leaf_el(path)->l_recs[split_index];
4217
4218         di = (struct ocfs2_dinode *)di_bh->b_data;
4219         rightmost_el = &di->id2.i_list;
4220
4221         depth = le16_to_cpu(rightmost_el->l_tree_depth);
4222         if (depth) {
4223                 BUG_ON(!(*last_eb_bh));
4224                 eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data;
4225                 rightmost_el = &eb->h_list;
4226         }
4227
4228         if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
4229             le16_to_cpu(rightmost_el->l_count)) {
4230                 ret = ocfs2_grow_tree(inode, handle, di_bh, &depth, last_eb_bh,
4231                                       meta_ac);
4232                 if (ret) {
4233                         mlog_errno(ret);
4234                         goto out;
4235                 }
4236         }
4237
4238         memset(&insert, 0, sizeof(struct ocfs2_insert_type));
4239         insert.ins_appending = APPEND_NONE;
4240         insert.ins_contig = CONTIG_NONE;
4241         insert.ins_tree_depth = depth;
4242
4243         insert_range = le32_to_cpu(split_rec.e_cpos) +
4244                 le16_to_cpu(split_rec.e_leaf_clusters);
4245         rec_range = le32_to_cpu(rec.e_cpos) +
4246                 le16_to_cpu(rec.e_leaf_clusters);
4247
4248         if (split_rec.e_cpos == rec.e_cpos) {
4249                 insert.ins_split = SPLIT_LEFT;
4250         } else if (insert_range == rec_range) {
4251                 insert.ins_split = SPLIT_RIGHT;
4252         } else {
4253                 /*
4254                  * Left/right split. We fake this as a right split
4255                  * first and then make a second pass as a left split.
4256                  */
4257                 insert.ins_split = SPLIT_RIGHT;
4258
4259                 ocfs2_make_right_split_rec(inode->i_sb, &tmprec, insert_range,
4260                                            &rec);
4261
4262                 split_rec = tmprec;
4263
4264                 BUG_ON(do_leftright);
4265                 do_leftright = 1;
4266         }
4267
4268         ret = ocfs2_do_insert_extent(inode, handle, di_bh, &split_rec,
4269                                      &insert);
4270         if (ret) {
4271                 mlog_errno(ret);
4272                 goto out;
4273         }
4274
4275         if (do_leftright == 1) {
4276                 u32 cpos;
4277                 struct ocfs2_extent_list *el;
4278
4279                 do_leftright++;
4280                 split_rec = *orig_split_rec;
4281
4282                 ocfs2_reinit_path(path, 1);
4283
4284                 cpos = le32_to_cpu(split_rec.e_cpos);
4285                 ret = ocfs2_find_path(inode, path, cpos);
4286                 if (ret) {
4287                         mlog_errno(ret);
4288                         goto out;
4289                 }
4290
4291                 el = path_leaf_el(path);
4292                 split_index = ocfs2_search_extent_list(el, cpos);
4293                 goto leftright;
4294         }
4295 out:
4296
4297         return ret;
4298 }
4299
4300 /*
4301  * Mark part or all of the extent record at split_index in the leaf
4302  * pointed to by path as written. This removes the unwritten
4303  * extent flag.
4304  *
4305  * Care is taken to handle contiguousness so as to not grow the tree.
4306  *
4307  * meta_ac is not strictly necessary - we only truly need it if growth
4308  * of the tree is required. All other cases will degrade into a less
4309  * optimal tree layout.
4310  *
4311  * last_eb_bh should be the rightmost leaf block for any inode with a
4312  * btree. Since a split may grow the tree or a merge might shrink it, the caller cannot trust the contents of that buffer after this call.
4313  *
4314  * This code is optimized for readability - several passes might be
4315  * made over certain portions of the tree. All of those blocks will
4316  * have been brought into cache (and pinned via the journal), so the
4317  * extra overhead is not expressed in terms of disk reads.
4318  */
4319 static int __ocfs2_mark_extent_written(struct inode *inode,
4320                                        struct buffer_head *di_bh,
4321                                        handle_t *handle,
4322                                        struct ocfs2_path *path,
4323                                        int split_index,
4324                                        struct ocfs2_extent_rec *split_rec,
4325                                        struct ocfs2_alloc_context *meta_ac,
4326                                        struct ocfs2_cached_dealloc_ctxt *dealloc)
4327 {
4328         int ret = 0;
4329         struct ocfs2_extent_list *el = path_leaf_el(path);
4330         struct buffer_head *last_eb_bh = NULL;
4331         struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
4332         struct ocfs2_merge_ctxt ctxt;
4333         struct ocfs2_extent_list *rightmost_el;
4334
4335         if (!(rec->e_flags & OCFS2_EXT_UNWRITTEN)) {
4336                 ret = -EIO;
4337                 mlog_errno(ret);
4338                 goto out;
4339         }
4340
4341         if (le32_to_cpu(rec->e_cpos) > le32_to_cpu(split_rec->e_cpos) ||
4342             ((le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)) <
4343              (le32_to_cpu(split_rec->e_cpos) + le16_to_cpu(split_rec->e_leaf_clusters)))) {
4344                 ret = -EIO;
4345                 mlog_errno(ret);
4346                 goto out;
4347         }
4348
4349         ctxt.c_contig_type = ocfs2_figure_merge_contig_type(inode, path, el,
4350                                                             split_index,
4351                                                             split_rec);
4352
4353         /*
4354          * The core merge / split code wants to know how much room is
4355          * left in this inodes allocation tree, so we pass the
4356          * rightmost extent list.
4357          */
4358         if (path->p_tree_depth) {
4359                 struct ocfs2_extent_block *eb;
4360                 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4361
4362                 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
4363                                        le64_to_cpu(di->i_last_eb_blk),
4364                                        &last_eb_bh, OCFS2_BH_CACHED, inode);
4365                 if (ret) {
4366                         mlog_exit(ret);
4367                         goto out;
4368                 }
4369
4370                 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
4371                 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
4372                         OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
4373                         ret = -EROFS;
4374                         goto out;
4375                 }
4376
4377                 rightmost_el = &eb->h_list;
4378         } else
4379                 rightmost_el = path_root_el(path);
4380
4381         if (rec->e_cpos == split_rec->e_cpos &&
4382             rec->e_leaf_clusters == split_rec->e_leaf_clusters)
4383                 ctxt.c_split_covers_rec = 1;
4384         else
4385                 ctxt.c_split_covers_rec = 0;
4386
4387         ctxt.c_has_empty_extent = ocfs2_is_empty_extent(&el->l_recs[0]);
4388
4389         mlog(0, "index: %d, contig: %u, has_empty: %u, split_covers: %u\n",
4390              split_index, ctxt.c_contig_type, ctxt.c_has_empty_extent,
4391              ctxt.c_split_covers_rec);
4392
4393         if (ctxt.c_contig_type == CONTIG_NONE) {
4394                 if (ctxt.c_split_covers_rec)
4395                         el->l_recs[split_index] = *split_rec;
4396                 else
4397                         ret = ocfs2_split_and_insert(inode, handle, path, di_bh,
4398                                                      &last_eb_bh, split_index,
4399                                                      split_rec, meta_ac);
4400                 if (ret)
4401                         mlog_errno(ret);
4402         } else {
4403                 ret = ocfs2_try_to_merge_extent(inode, handle, path,
4404                                                 split_index, split_rec,
4405                                                 dealloc, &ctxt);
4406                 if (ret)
4407                         mlog_errno(ret);
4408         }
4409
4410 out:
4411         brelse(last_eb_bh);
4412         return ret;
4413 }
4414
4415 /*
4416  * Mark the already-existing extent at cpos as written for len clusters.
4417  *
4418  * If the existing extent is larger than the request, initiate a
4419  * split. An attempt will be made at merging with adjacent extents.
4420  *
4421  * The caller is responsible for passing down meta_ac if we'll need it.
4422  */
4423 int ocfs2_mark_extent_written(struct inode *inode, struct buffer_head *di_bh,
4424                               handle_t *handle, u32 cpos, u32 len, u32 phys,
4425                               struct ocfs2_alloc_context *meta_ac,
4426                               struct ocfs2_cached_dealloc_ctxt *dealloc)
4427 {
4428         int ret, index;
4429         u64 start_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys);
4430         struct ocfs2_extent_rec split_rec;
4431         struct ocfs2_path *left_path = NULL;
4432         struct ocfs2_extent_list *el;
4433
4434         mlog(0, "Inode %lu cpos %u, len %u, phys %u (%llu)\n",
4435              inode->i_ino, cpos, len, phys, (unsigned long long)start_blkno);
4436
4437         if (!ocfs2_writes_unwritten_extents(OCFS2_SB(inode->i_sb))) {
4438                 ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents "
4439                             "that are being written to, but the feature bit "
4440                             "is not set in the super block.",
4441                             (unsigned long long)OCFS2_I(inode)->ip_blkno);
4442                 ret = -EROFS;
4443                 goto out;
4444         }
4445
4446         /*
4447          * XXX: This should be fixed up so that we just re-insert the
4448          * next extent records.
4449          */
4450         ocfs2_extent_map_trunc(inode, 0);
4451
4452         left_path = ocfs2_new_inode_path(di_bh);
4453         if (!left_path) {
4454                 ret = -ENOMEM;
4455                 mlog_errno(ret);
4456                 goto out;
4457         }
4458
4459         ret = ocfs2_find_path(inode, left_path, cpos);
4460         if (ret) {
4461                 mlog_errno(ret);
4462                 goto out;
4463         }
4464         el = path_leaf_el(left_path);
4465
4466         index = ocfs2_search_extent_list(el, cpos);
4467         if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4468                 ocfs2_error(inode->i_sb,
4469                             "Inode %llu has an extent at cpos %u which can no "
4470                             "longer be found.\n",
4471                             (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos);
4472                 ret = -EROFS;
4473                 goto out;
4474         }
4475
4476         memset(&split_rec, 0, sizeof(struct ocfs2_extent_rec));
4477         split_rec.e_cpos = cpu_to_le32(cpos);
4478         split_rec.e_leaf_clusters = cpu_to_le16(len);
4479         split_rec.e_blkno = cpu_to_le64(start_blkno);
4480         split_rec.e_flags = path_leaf_el(left_path)->l_recs[index].e_flags;
4481         split_rec.e_flags &= ~OCFS2_EXT_UNWRITTEN;
4482
4483         ret = __ocfs2_mark_extent_written(inode, di_bh, handle, left_path,
4484                                           index, &split_rec, meta_ac, dealloc);
4485         if (ret)
4486                 mlog_errno(ret);
4487
4488 out:
4489         ocfs2_free_path(left_path);
4490         return ret;
4491 }
4492
4493 static int ocfs2_split_tree(struct inode *inode, struct buffer_head *di_bh,
4494                             handle_t *handle, struct ocfs2_path *path,
4495                             int index, u32 new_range,
4496                             struct ocfs2_alloc_context *meta_ac)
4497 {
4498         int ret, depth, credits = handle->h_buffer_credits;
4499         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4500         struct buffer_head *last_eb_bh = NULL;
4501         struct ocfs2_extent_block *eb;
4502         struct ocfs2_extent_list *rightmost_el, *el;
4503         struct ocfs2_extent_rec split_rec;
4504         struct ocfs2_extent_rec *rec;
4505         struct ocfs2_insert_type insert;
4506
4507         /*
4508          * Setup the record to split before we grow the tree.
4509          */
4510         el = path_leaf_el(path);
4511         rec = &el->l_recs[index];
4512         ocfs2_make_right_split_rec(inode->i_sb, &split_rec, new_range, rec);
4513
4514         depth = path->p_tree_depth;
4515         if (depth > 0) {
4516                 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
4517                                        le64_to_cpu(di->i_last_eb_blk),
4518                                        &last_eb_bh, OCFS2_BH_CACHED, inode);
4519                 if (ret < 0) {
4520                         mlog_errno(ret);
4521                         goto out;
4522                 }
4523
4524                 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
4525                 rightmost_el = &eb->h_list;
4526         } else
4527                 rightmost_el = path_leaf_el(path);
4528
4529         credits += path->p_tree_depth + ocfs2_extend_meta_needed(di);
4530         ret = ocfs2_extend_trans(handle, credits);
4531         if (ret) {
4532                 mlog_errno(ret);
4533                 goto out;
4534         }
4535
4536         if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
4537             le16_to_cpu(rightmost_el->l_count)) {
4538                 ret = ocfs2_grow_tree(inode, handle, di_bh, &depth, &last_eb_bh,
4539                                       meta_ac);
4540                 if (ret) {
4541                         mlog_errno(ret);
4542                         goto out;
4543                 }
4544         }
4545
4546         memset(&insert, 0, sizeof(struct ocfs2_insert_type));
4547         insert.ins_appending = APPEND_NONE;
4548         insert.ins_contig = CONTIG_NONE;
4549         insert.ins_split = SPLIT_RIGHT;
4550         insert.ins_tree_depth = depth;
4551
4552         ret = ocfs2_do_insert_extent(inode, handle, di_bh, &split_rec, &insert);
4553         if (ret)
4554                 mlog_errno(ret);
4555
4556 out:
4557         brelse(last_eb_bh);
4558         return ret;
4559 }
4560
4561 static int ocfs2_truncate_rec(struct inode *inode, handle_t *handle,
4562                               struct ocfs2_path *path, int index,
4563                               struct ocfs2_cached_dealloc_ctxt *dealloc,
4564                               u32 cpos, u32 len)
4565 {
4566         int ret;
4567         u32 left_cpos, rec_range, trunc_range;
4568         int wants_rotate = 0, is_rightmost_tree_rec = 0;
4569         struct super_block *sb = inode->i_sb;
4570         struct ocfs2_path *left_path = NULL;
4571         struct ocfs2_extent_list *el = path_leaf_el(path);
4572         struct ocfs2_extent_rec *rec;
4573         struct ocfs2_extent_block *eb;
4574
4575         if (ocfs2_is_empty_extent(&el->l_recs[0]) && index > 0) {
4576                 ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc);
4577                 if (ret) {
4578                         mlog_errno(ret);
4579                         goto out;
4580                 }
4581
4582                 index--;
4583         }
4584
4585         if (index == (le16_to_cpu(el->l_next_free_rec) - 1) &&
4586             path->p_tree_depth) {
4587                 /*
4588                  * Check whether this is the rightmost tree record. If
4589                  * we remove all of this record or part of its right
4590                  * edge then an update of the record lengths above it
4591                  * will be required.
4592                  */
4593                 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
4594                 if (eb->h_next_leaf_blk == 0)
4595                         is_rightmost_tree_rec = 1;
4596         }
4597
4598         rec = &el->l_recs[index];
4599         if (index == 0 && path->p_tree_depth &&
4600             le32_to_cpu(rec->e_cpos) == cpos) {
4601                 /*
4602                  * Changing the leftmost offset (via partial or whole
4603                  * record truncate) of an interior (or rightmost) path
4604                  * means we have to update the subtree that is formed
4605                  * by this leaf and the one to it's left.
4606                  *
4607                  * There are two cases we can skip:
4608                  *   1) Path is the leftmost one in our inode tree.
4609                  *   2) The leaf is rightmost and will be empty after
4610                  *      we remove the extent record - the rotate code
4611                  *      knows how to update the newly formed edge.
4612                  */
4613
4614                 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path,
4615                                                     &left_cpos);
4616                 if (ret) {
4617                         mlog_errno(ret);
4618                         goto out;
4619                 }
4620
4621                 if (left_cpos && le16_to_cpu(el->l_next_free_rec) > 1) {
4622                         left_path = ocfs2_new_path(path_root_bh(path),
4623                                                    path_root_el(path));
4624                         if (!left_path) {
4625                                 ret = -ENOMEM;
4626                                 mlog_errno(ret);
4627                                 goto out;
4628                         }
4629
4630                         ret = ocfs2_find_path(inode, left_path, left_cpos);
4631                         if (ret) {
4632                                 mlog_errno(ret);
4633                                 goto out;
4634                         }
4635                 }
4636         }
4637
4638         ret = ocfs2_extend_rotate_transaction(handle, 0,
4639                                               handle->h_buffer_credits,
4640                                               path);
4641         if (ret) {
4642                 mlog_errno(ret);
4643                 goto out;
4644         }
4645
4646         ret = ocfs2_journal_access_path(inode, handle, path);
4647         if (ret) {
4648                 mlog_errno(ret);
4649                 goto out;
4650         }
4651
4652         ret = ocfs2_journal_access_path(inode, handle, left_path);
4653         if (ret) {
4654                 mlog_errno(ret);
4655                 goto out;
4656         }
4657
4658         rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
4659         trunc_range = cpos + len;
4660
4661         if (le32_to_cpu(rec->e_cpos) == cpos && rec_range == trunc_range) {
4662                 int next_free;
4663
4664                 memset(rec, 0, sizeof(*rec));
4665                 ocfs2_cleanup_merge(el, index);
4666                 wants_rotate = 1;
4667
4668                 next_free = le16_to_cpu(el->l_next_free_rec);
4669                 if (is_rightmost_tree_rec && next_free > 1) {
4670                         /*
4671                          * We skip the edge update if this path will
4672                          * be deleted by the rotate code.
4673                          */
4674                         rec = &el->l_recs[next_free - 1];
4675                         ocfs2_adjust_rightmost_records(inode, handle, path,
4676                                                        rec);
4677                 }
4678         } else if (le32_to_cpu(rec->e_cpos) == cpos) {
4679                 /* Remove leftmost portion of the record. */
4680                 le32_add_cpu(&rec->e_cpos, len);
4681                 le64_add_cpu(&rec->e_blkno, ocfs2_clusters_to_blocks(sb, len));
4682                 le16_add_cpu(&rec->e_leaf_clusters, -len);
4683         } else if (rec_range == trunc_range) {
4684                 /* Remove rightmost portion of the record */
4685                 le16_add_cpu(&rec->e_leaf_clusters, -len);
4686                 if (is_rightmost_tree_rec)
4687                         ocfs2_adjust_rightmost_records(inode, handle, path, rec);
4688         } else {
4689                 /* Caller should have trapped this. */
4690                 mlog(ML_ERROR, "Inode %llu: Invalid record truncate: (%u, %u) "
4691                      "(%u, %u)\n", (unsigned long long)OCFS2_I(inode)->ip_blkno,
4692                      le32_to_cpu(rec->e_cpos),
4693                      le16_to_cpu(rec->e_leaf_clusters), cpos, len);
4694                 BUG();
4695         }
4696
4697         if (left_path) {
4698                 int subtree_index;
4699
4700                 subtree_index = ocfs2_find_subtree_root(inode, left_path, path);
4701                 ocfs2_complete_edge_insert(inode, handle, left_path, path,
4702                                            subtree_index);
4703         }
4704
4705         ocfs2_journal_dirty(handle, path_leaf_bh(path));
4706
4707         ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc);
4708         if (ret) {
4709                 mlog_errno(ret);
4710                 goto out;
4711         }
4712
4713 out:
4714         ocfs2_free_path(left_path);
4715         return ret;
4716 }
4717
4718 int ocfs2_remove_extent(struct inode *inode, struct buffer_head *di_bh,
4719                         u32 cpos, u32 len, handle_t *handle,
4720                         struct ocfs2_alloc_context *meta_ac,
4721                         struct ocfs2_cached_dealloc_ctxt *dealloc)
4722 {
4723         int ret, index;
4724         u32 rec_range, trunc_range;
4725         struct ocfs2_extent_rec *rec;
4726         struct ocfs2_extent_list *el;
4727         struct ocfs2_path *path;
4728
4729         ocfs2_extent_map_trunc(inode, 0);
4730
4731         path = ocfs2_new_inode_path(di_bh);
4732         if (!path) {
4733                 ret = -ENOMEM;
4734                 mlog_errno(ret);
4735                 goto out;
4736         }
4737
4738         ret = ocfs2_find_path(inode, path, cpos);
4739         if (ret) {
4740                 mlog_errno(ret);
4741                 goto out;
4742         }
4743
4744         el = path_leaf_el(path);
4745         index = ocfs2_search_extent_list(el, cpos);
4746         if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4747                 ocfs2_error(inode->i_sb,
4748                             "Inode %llu has an extent at cpos %u which can no "
4749                             "longer be found.\n",
4750                             (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos);
4751                 ret = -EROFS;
4752                 goto out;
4753         }
4754
4755         /*
4756          * We have 3 cases of extent removal:
4757          *   1) Range covers the entire extent rec
4758          *   2) Range begins or ends on one edge of the extent rec
4759          *   3) Range is in the middle of the extent rec (no shared edges)
4760          *
4761          * For case 1 we remove the extent rec and left rotate to
4762          * fill the hole.
4763          *
4764          * For case 2 we just shrink the existing extent rec, with a
4765          * tree update if the shrinking edge is also the edge of an
4766          * extent block.
4767          *
4768          * For case 3 we do a right split to turn the extent rec into
4769          * something case 2 can handle.
4770          */
4771         rec = &el->l_recs[index];
4772         rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
4773         trunc_range = cpos + len;
4774
4775         BUG_ON(cpos < le32_to_cpu(rec->e_cpos) || trunc_range > rec_range);
4776
4777         mlog(0, "Inode %llu, remove (cpos %u, len %u). Existing index %d "
4778              "(cpos %u, len %u)\n",
4779              (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos, len, index,
4780              le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec));
4781
4782         if (le32_to_cpu(rec->e_cpos) == cpos || rec_range == trunc_range) {
4783                 ret = ocfs2_truncate_rec(inode, handle, path, index, dealloc,
4784                                          cpos, len);
4785                 if (ret) {
4786                         mlog_errno(ret);
4787                         goto out;
4788                 }
4789         } else {
4790                 ret = ocfs2_split_tree(inode, di_bh, handle, path, index,
4791                                        trunc_range, meta_ac);
4792                 if (ret) {
4793                         mlog_errno(ret);
4794                         goto out;
4795                 }
4796
4797                 /*
4798                  * The split could have manipulated the tree enough to
4799                  * move the record location, so we have to look for it again.
4800                  */
4801                 ocfs2_reinit_path(path, 1);
4802
4803                 ret = ocfs2_find_path(inode, path, cpos);
4804                 if (ret) {
4805                         mlog_errno(ret);
4806                         goto out;
4807                 }
4808
4809                 el = path_leaf_el(path);
4810                 index = ocfs2_search_extent_list(el, cpos);
4811                 if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4812                         ocfs2_error(inode->i_sb,
4813                                     "Inode %llu: split at cpos %u lost record.",
4814                                     (unsigned long long)OCFS2_I(inode)->ip_blkno,
4815                                     cpos);
4816                         ret = -EROFS;
4817                         goto out;
4818                 }
4819
4820                 /*
4821                  * Double check our values here. If anything is fishy,
4822                  * it's easier to catch it at the top level.
4823                  */
4824                 rec = &el->l_recs[index];
4825                 rec_range = le32_to_cpu(rec->e_cpos) +
4826                         ocfs2_rec_clusters(el, rec);
4827                 if (rec_range != trunc_range) {
4828                         ocfs2_error(inode->i_sb,
4829                                     "Inode %llu: error after split at cpos %u"
4830                                     "trunc len %u, existing record is (%u,%u)",
4831                                     (unsigned long long)OCFS2_I(inode)->ip_blkno,
4832                                     cpos, len, le32_to_cpu(rec->e_cpos),
4833                                     ocfs2_rec_clusters(el, rec));
4834                         ret = -EROFS;
4835                         goto out;
4836                 }
4837
4838                 ret = ocfs2_truncate_rec(inode, handle, path, index, dealloc,
4839                                          cpos, len);
4840                 if (ret) {
4841                         mlog_errno(ret);
4842                         goto out;
4843                 }
4844         }
4845
4846 out:
4847         ocfs2_free_path(path);
4848         return ret;
4849 }
4850
4851 int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb)
4852 {
4853         struct buffer_head *tl_bh = osb->osb_tl_bh;
4854         struct ocfs2_dinode *di;
4855         struct ocfs2_truncate_log *tl;
4856
4857         di = (struct ocfs2_dinode *) tl_bh->b_data;
4858         tl = &di->id2.i_dealloc;
4859
4860         mlog_bug_on_msg(le16_to_cpu(tl->tl_used) > le16_to_cpu(tl->tl_count),
4861                         "slot %d, invalid truncate log parameters: used = "
4862                         "%u, count = %u\n", osb->slot_num,
4863                         le16_to_cpu(tl->tl_used), le16_to_cpu(tl->tl_count));
4864         return le16_to_cpu(tl->tl_used) == le16_to_cpu(tl->tl_count);
4865 }
4866
4867 static int ocfs2_truncate_log_can_coalesce(struct ocfs2_truncate_log *tl,
4868                                            unsigned int new_start)
4869 {
4870         unsigned int tail_index;
4871         unsigned int current_tail;
4872
4873         /* No records, nothing to coalesce */
4874         if (!le16_to_cpu(tl->tl_used))
4875                 return 0;
4876
4877         tail_index = le16_to_cpu(tl->tl_used) - 1;
4878         current_tail = le32_to_cpu(tl->tl_recs[tail_index].t_start);
4879         current_tail += le32_to_cpu(tl->tl_recs[tail_index].t_clusters);
4880
4881         return current_tail == new_start;
4882 }
4883
4884 int ocfs2_truncate_log_append(struct ocfs2_super *osb,
4885                               handle_t *handle,
4886                               u64 start_blk,
4887                               unsigned int num_clusters)
4888 {
4889         int status, index;
4890         unsigned int start_cluster, tl_count;
4891         struct inode *tl_inode = osb->osb_tl_inode;
4892         struct buffer_head *tl_bh = osb->osb_tl_bh;
4893         struct ocfs2_dinode *di;
4894         struct ocfs2_truncate_log *tl;
4895
4896         mlog_entry("start_blk = %llu, num_clusters = %u\n",
4897                    (unsigned long long)start_blk, num_clusters);
4898
4899         BUG_ON(mutex_trylock(&tl_inode->i_mutex));
4900
4901         start_cluster = ocfs2_blocks_to_clusters(osb->sb, start_blk);
4902
4903         di = (struct ocfs2_dinode *) tl_bh->b_data;
4904         tl = &di->id2.i_dealloc;
4905         if (!OCFS2_IS_VALID_DINODE(di)) {
4906                 OCFS2_RO_ON_INVALID_DINODE(osb->sb, di);
4907                 status = -EIO;
4908                 goto bail;
4909         }
4910
4911         tl_count = le16_to_cpu(tl->tl_count);
4912         mlog_bug_on_msg(tl_count > ocfs2_truncate_recs_per_inode(osb->sb) ||
4913                         tl_count == 0,
4914                         "Truncate record count on #%llu invalid "
4915                         "wanted %u, actual %u\n",
4916                         (unsigned long long)OCFS2_I(tl_inode)->ip_blkno,
4917                         ocfs2_truncate_recs_per_inode(osb->sb),
4918                         le16_to_cpu(tl->tl_count));
4919
4920         /* Caller should have known to flush before calling us. */
4921         index = le16_to_cpu(tl->tl_used);
4922         if (index >= tl_count) {
4923                 status = -ENOSPC;
4924                 mlog_errno(status);
4925                 goto bail;
4926         }
4927
4928         status = ocfs2_journal_access(handle, tl_inode, tl_bh,
4929                                       OCFS2_JOURNAL_ACCESS_WRITE);
4930         if (status < 0) {
4931                 mlog_errno(status);
4932                 goto bail;
4933         }
4934
4935         mlog(0, "Log truncate of %u clusters starting at cluster %u to "
4936              "%llu (index = %d)\n", num_clusters, start_cluster,
4937              (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, index);
4938
4939         if (ocfs2_truncate_log_can_coalesce(tl, start_cluster)) {
4940                 /*
4941                  * Move index back to the record we are coalescing with.
4942                  * ocfs2_truncate_log_can_coalesce() guarantees nonzero
4943                  */
4944                 index--;
4945
4946                 num_clusters += le32_to_cpu(tl->tl_recs[index].t_clusters);
4947                 mlog(0, "Coalesce with index %u (start = %u, clusters = %u)\n",
4948                      index, le32_to_cpu(tl->tl_recs[index].t_start),
4949                      num_clusters);
4950         } else {
4951                 tl->tl_recs[index].t_start = cpu_to_le32(start_cluster);
4952                 tl->tl_used = cpu_to_le16(index + 1);
4953         }
4954         tl->tl_recs[index].t_clusters = cpu_to_le32(num_clusters);
4955
4956         status = ocfs2_journal_dirty(handle, tl_bh);
4957         if (status < 0) {
4958                 mlog_errno(status);
4959                 goto bail;
4960         }
4961
4962 bail:
4963         mlog_exit(status);
4964         return status;
4965 }
4966
4967 static int ocfs2_replay_truncate_records(struct ocfs2_super *osb,
4968                                          handle_t *handle,
4969                                          struct inode *data_alloc_inode,
4970                                          struct buffer_head *data_alloc_bh)
4971 {
4972         int status = 0;
4973         int i;
4974         unsigned int num_clusters;
4975         u64 start_blk;
4976         struct ocfs2_truncate_rec rec;
4977         struct ocfs2_dinode *di;
4978         struct ocfs2_truncate_log *tl;
4979         struct inode *tl_inode = osb->osb_tl_inode;
4980         struct buffer_head *tl_bh = osb->osb_tl_bh;
4981
4982         mlog_entry_void();
4983
4984         di = (struct ocfs2_dinode *) tl_bh->b_data;
4985         tl = &di->id2.i_dealloc;
4986         i = le16_to_cpu(tl->tl_used) - 1;
4987         while (i >= 0) {
4988                 /* Caller has given us at least enough credits to
4989                  * update the truncate log dinode */
4990                 status = ocfs2_journal_access(handle, tl_inode, tl_bh,
4991                                               OCFS2_JOURNAL_ACCESS_WRITE);
4992                 if (status < 0) {
4993                         mlog_errno(status);
4994                         goto bail;
4995                 }
4996
4997                 tl->tl_used = cpu_to_le16(i);
4998
4999                 status = ocfs2_journal_dirty(handle, tl_bh);
5000                 if (status < 0) {
5001                         mlog_errno(status);
5002                         goto bail;
5003                 }
5004
5005                 /* TODO: Perhaps we can calculate the bulk of the
5006                  * credits up front rather than extending like
5007                  * this. */
5008                 status = ocfs2_extend_trans(handle,
5009                                             OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5010                 if (status < 0) {
5011                         mlog_errno(status);
5012                         goto bail;
5013                 }
5014
5015                 rec = tl->tl_recs[i];
5016                 start_blk = ocfs2_clusters_to_blocks(data_alloc_inode->i_sb,
5017                                                     le32_to_cpu(rec.t_start));
5018                 num_clusters = le32_to_cpu(rec.t_clusters);
5019
5020                 /* if start_blk is not set, we ignore the record as
5021                  * invalid. */
5022                 if (start_blk) {
5023                         mlog(0, "free record %d, start = %u, clusters = %u\n",
5024                              i, le32_to_cpu(rec.t_start), num_clusters);
5025
5026                         status = ocfs2_free_clusters(handle, data_alloc_inode,
5027                                                      data_alloc_bh, start_blk,
5028                                                      num_clusters);
5029                         if (status < 0) {
5030                                 mlog_errno(status);
5031                                 goto bail;
5032                         }
5033                 }
5034                 i--;
5035         }
5036
5037 bail:
5038         mlog_exit(status);
5039         return status;
5040 }
5041
5042 /* Expects you to already be holding tl_inode->i_mutex */
5043 int __ocfs2_flush_truncate_log(struct ocfs2_super *osb)
5044 {
5045         int status;
5046         unsigned int num_to_flush;
5047         handle_t *handle;
5048         struct inode *tl_inode = osb->osb_tl_inode;
5049         struct inode *data_alloc_inode = NULL;
5050         struct buffer_head *tl_bh = osb->osb_tl_bh;
5051         struct buffer_head *data_alloc_bh = NULL;
5052         struct ocfs2_dinode *di;
5053         struct ocfs2_truncate_log *tl;
5054
5055         mlog_entry_void();
5056
5057         BUG_ON(mutex_trylock(&tl_inode->i_mutex));
5058
5059         di = (struct ocfs2_dinode *) tl_bh->b_data;
5060         tl = &di->id2.i_dealloc;
5061         if (!OCFS2_IS_VALID_DINODE(di)) {
5062                 OCFS2_RO_ON_INVALID_DINODE(osb->sb, di);
5063                 status = -EIO;
5064                 goto out;
5065         }
5066
5067         num_to_flush = le16_to_cpu(tl->tl_used);
5068         mlog(0, "Flush %u records from truncate log #%llu\n",
5069              num_to_flush, (unsigned long long)OCFS2_I(tl_inode)->ip_blkno);
5070         if (!num_to_flush) {
5071                 status = 0;
5072                 goto out;
5073         }
5074
5075         data_alloc_inode = ocfs2_get_system_file_inode(osb,
5076                                                        GLOBAL_BITMAP_SYSTEM_INODE,
5077                                                        OCFS2_INVALID_SLOT);
5078         if (!data_alloc_inode) {
5079                 status = -EINVAL;
5080                 mlog(ML_ERROR, "Could not get bitmap inode!\n");
5081                 goto out;
5082         }
5083
5084         mutex_lock(&data_alloc_inode->i_mutex);
5085
5086         status = ocfs2_inode_lock(data_alloc_inode, &data_alloc_bh, 1);
5087         if (status < 0) {
5088                 mlog_errno(status);
5089                 goto out_mutex;
5090         }
5091
5092         handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
5093         if (IS_ERR(handle)) {
5094                 status = PTR_ERR(handle);
5095                 mlog_errno(status);
5096                 goto out_unlock;
5097         }
5098
5099         status = ocfs2_replay_truncate_records(osb, handle, data_alloc_inode,
5100                                                data_alloc_bh);
5101         if (status < 0)
5102                 mlog_errno(status);
5103
5104         ocfs2_commit_trans(osb, handle);
5105
5106 out_unlock:
5107         brelse(data_alloc_bh);
5108         ocfs2_inode_unlock(data_alloc_inode, 1);
5109
5110 out_mutex:
5111         mutex_unlock(&data_alloc_inode->i_mutex);
5112         iput(data_alloc_inode);
5113
5114 out:
5115         mlog_exit(status);
5116         return status;
5117 }
5118
5119 int ocfs2_flush_truncate_log(struct ocfs2_super *osb)
5120 {
5121         int status;
5122         struct inode *tl_inode = osb->osb_tl_inode;
5123
5124         mutex_lock(&tl_inode->i_mutex);
5125         status = __ocfs2_flush_truncate_log(osb);
5126         mutex_unlock(&tl_inode->i_mutex);
5127
5128         return status;
5129 }
5130
5131 static void ocfs2_truncate_log_worker(struct work_struct *work)
5132 {
5133         int status;
5134         struct ocfs2_super *osb =
5135                 container_of(work, struct ocfs2_super,
5136                              osb_truncate_log_wq.work);
5137
5138         mlog_entry_void();
5139
5140         status = ocfs2_flush_truncate_log(osb);
5141         if (status < 0)
5142                 mlog_errno(status);
5143         else
5144                 ocfs2_init_inode_steal_slot(osb);
5145
5146         mlog_exit(status);
5147 }
5148
5149 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
5150 void ocfs2_schedule_truncate_log_flush(struct ocfs2_super *osb,
5151                                        int cancel)
5152 {
5153         if (osb->osb_tl_inode) {
5154                 /* We want to push off log flushes while truncates are
5155                  * still running. */
5156                 if (cancel)
5157                         cancel_delayed_work(&osb->osb_truncate_log_wq);
5158
5159                 queue_delayed_work(ocfs2_wq, &osb->osb_truncate_log_wq,
5160                                    OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
5161         }
5162 }
5163
5164 static int ocfs2_get_truncate_log_info(struct ocfs2_super *osb,
5165                                        int slot_num,
5166                                        struct inode **tl_inode,
5167                                        struct buffer_head **tl_bh)
5168 {
5169         int status;
5170         struct inode *inode = NULL;
5171         struct buffer_head *bh = NULL;
5172
5173         inode = ocfs2_get_system_file_inode(osb,
5174                                            TRUNCATE_LOG_SYSTEM_INODE,
5175                                            slot_num);
5176         if (!inode) {
5177                 status = -EINVAL;
5178                 mlog(ML_ERROR, "Could not get load truncate log inode!\n");
5179                 goto bail;
5180         }
5181
5182         status = ocfs2_read_block(osb, OCFS2_I(inode)->ip_blkno, &bh,
5183                                   OCFS2_BH_CACHED, inode);
5184         if (status < 0) {
5185                 iput(inode);
5186                 mlog_errno(status);
5187                 goto bail;
5188         }
5189
5190         *tl_inode = inode;
5191         *tl_bh    = bh;
5192 bail:
5193         mlog_exit(status);
5194         return status;
5195 }
5196
5197 /* called during the 1st stage of node recovery. we stamp a clean
5198  * truncate log and pass back a copy for processing later. if the
5199  * truncate log does not require processing, a *tl_copy is set to
5200  * NULL. */
5201 int ocfs2_begin_truncate_log_recovery(struct ocfs2_super *osb,
5202                                       int slot_num,
5203                                       struct ocfs2_dinode **tl_copy)
5204 {
5205         int status;
5206         struct inode *tl_inode = NULL;
5207         struct buffer_head *tl_bh = NULL;
5208         struct ocfs2_dinode *di;
5209         struct ocfs2_truncate_log *tl;
5210
5211         *tl_copy = NULL;
5212
5213         mlog(0, "recover truncate log from slot %d\n", slot_num);
5214
5215         status = ocfs2_get_truncate_log_info(osb, slot_num, &tl_inode, &tl_bh);
5216         if (status < 0) {
5217                 mlog_errno(status);
5218                 goto bail;
5219         }
5220
5221         di = (struct ocfs2_dinode *) tl_bh->b_data;
5222         tl = &di->id2.i_dealloc;
5223         if (!OCFS2_IS_VALID_DINODE(di)) {
5224                 OCFS2_RO_ON_INVALID_DINODE(tl_inode->i_sb, di);
5225                 status = -EIO;
5226                 goto bail;
5227         }
5228
5229         if (le16_to_cpu(tl->tl_used)) {
5230                 mlog(0, "We'll have %u logs to recover\n",
5231                      le16_to_cpu(tl->tl_used));
5232
5233                 *tl_copy = kmalloc(tl_bh->b_size, GFP_KERNEL);
5234                 if (!(*tl_copy)) {
5235                         status = -ENOMEM;
5236                         mlog_errno(status);
5237                         goto bail;
5238                 }
5239
5240                 /* Assuming the write-out below goes well, this copy
5241                  * will be passed back to recovery for processing. */
5242                 memcpy(*tl_copy, tl_bh->b_data, tl_bh->b_size);
5243
5244                 /* All we need to do to clear the truncate log is set
5245                  * tl_used. */
5246                 tl->tl_used = 0;
5247
5248                 status = ocfs2_write_block(osb, tl_bh, tl_inode);
5249                 if (status < 0) {
5250                         mlog_errno(status);
5251                         goto bail;
5252                 }
5253         }
5254
5255 bail:
5256         if (tl_inode)
5257                 iput(tl_inode);
5258         if (tl_bh)
5259                 brelse(tl_bh);
5260
5261         if (status < 0 && (*tl_copy)) {
5262                 kfree(*tl_copy);
5263                 *tl_copy = NULL;
5264         }
5265
5266         mlog_exit(status);
5267         return status;
5268 }
5269
5270 int ocfs2_complete_truncate_log_recovery(struct ocfs2_super *osb,
5271                                          struct ocfs2_dinode *tl_copy)
5272 {
5273         int status = 0;
5274         int i;
5275         unsigned int clusters, num_recs, start_cluster;
5276         u64 start_blk;
5277         handle_t *handle;
5278         struct inode *tl_inode = osb->osb_tl_inode;
5279         struct ocfs2_truncate_log *tl;
5280
5281         mlog_entry_void();
5282
5283         if (OCFS2_I(tl_inode)->ip_blkno == le64_to_cpu(tl_copy->i_blkno)) {
5284                 mlog(ML_ERROR, "Asked to recover my own truncate log!\n");
5285                 return -EINVAL;
5286         }
5287
5288         tl = &tl_copy->id2.i_dealloc;
5289         num_recs = le16_to_cpu(tl->tl_used);
5290         mlog(0, "cleanup %u records from %llu\n", num_recs,
5291              (unsigned long long)le64_to_cpu(tl_copy->i_blkno));
5292
5293         mutex_lock(&tl_inode->i_mutex);
5294         for(i = 0; i < num_recs; i++) {
5295                 if (ocfs2_truncate_log_needs_flush(osb)) {
5296                         status = __ocfs2_flush_truncate_log(osb);
5297                         if (status < 0) {
5298                                 mlog_errno(status);
5299                                 goto bail_up;
5300                         }
5301                 }
5302
5303                 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
5304                 if (IS_ERR(handle)) {
5305                         status = PTR_ERR(handle);
5306                         mlog_errno(status);
5307                         goto bail_up;
5308                 }
5309
5310                 clusters = le32_to_cpu(tl->tl_recs[i].t_clusters);
5311                 start_cluster = le32_to_cpu(tl->tl_recs[i].t_start);
5312                 start_blk = ocfs2_clusters_to_blocks(osb->sb, start_cluster);
5313
5314                 status = ocfs2_truncate_log_append(osb, handle,
5315                                                    start_blk, clusters);
5316                 ocfs2_commit_trans(osb, handle);
5317                 if (status < 0) {
5318                         mlog_errno(status);
5319                         goto bail_up;
5320                 }
5321         }
5322
5323 bail_up:
5324         mutex_unlock(&tl_inode->i_mutex);
5325
5326         mlog_exit(status);
5327         return status;
5328 }
5329
5330 void ocfs2_truncate_log_shutdown(struct ocfs2_super *osb)
5331 {
5332         int status;
5333         struct inode *tl_inode = osb->osb_tl_inode;
5334
5335         mlog_entry_void();
5336
5337         if (tl_inode) {
5338                 cancel_delayed_work(&osb->osb_truncate_log_wq);
5339                 flush_workqueue(ocfs2_wq);
5340
5341                 status = ocfs2_flush_truncate_log(osb);
5342                 if (status < 0)
5343                         mlog_errno(status);
5344
5345                 brelse(osb->osb_tl_bh);
5346                 iput(osb->osb_tl_inode);
5347         }
5348
5349         mlog_exit_void();
5350 }
5351
5352 int ocfs2_truncate_log_init(struct ocfs2_super *osb)
5353 {
5354         int status;
5355         struct inode *tl_inode = NULL;
5356         struct buffer_head *tl_bh = NULL;
5357
5358         mlog_entry_void();
5359
5360         status = ocfs2_get_truncate_log_info(osb,
5361                                              osb->slot_num,
5362                                              &tl_inode,
5363                                              &tl_bh);
5364         if (status < 0)
5365                 mlog_errno(status);
5366
5367         /* ocfs2_truncate_log_shutdown keys on the existence of
5368          * osb->osb_tl_inode so we don't set any of the osb variables
5369          * until we're sure all is well. */
5370         INIT_DELAYED_WORK(&osb->osb_truncate_log_wq,
5371                           ocfs2_truncate_log_worker);
5372         osb->osb_tl_bh    = tl_bh;
5373         osb->osb_tl_inode = tl_inode;
5374
5375         mlog_exit(status);
5376         return status;
5377 }
5378
5379 /*
5380  * Delayed de-allocation of suballocator blocks.
5381  *
5382  * Some sets of block de-allocations might involve multiple suballocator inodes.
5383  *
5384  * The locking for this can get extremely complicated, especially when
5385  * the suballocator inodes to delete from aren't known until deep
5386  * within an unrelated codepath.
5387  *
5388  * ocfs2_extent_block structures are a good example of this - an inode
5389  * btree could have been grown by any number of nodes each allocating
5390  * out of their own suballoc inode.
5391  *
5392  * These structures allow the delay of block de-allocation until a
5393  * later time, when locking of multiple cluster inodes won't cause
5394  * deadlock.
5395  */
5396
5397 /*
5398  * Describes a single block free from a suballocator
5399  */
5400 struct ocfs2_cached_block_free {
5401         struct ocfs2_cached_block_free          *free_next;
5402         u64                                     free_blk;
5403         unsigned int                            free_bit;
5404 };
5405
5406 struct ocfs2_per_slot_free_list {
5407         struct ocfs2_per_slot_free_list         *f_next_suballocator;
5408         int                                     f_inode_type;
5409         int                                     f_slot;
5410         struct ocfs2_cached_block_free          *f_first;
5411 };
5412
5413 static int ocfs2_free_cached_items(struct ocfs2_super *osb,
5414                                    int sysfile_type,
5415                                    int slot,
5416                                    struct ocfs2_cached_block_free *head)
5417 {
5418         int ret;
5419         u64 bg_blkno;
5420         handle_t *handle;
5421         struct inode *inode;
5422         struct buffer_head *di_bh = NULL;
5423         struct ocfs2_cached_block_free *tmp;
5424
5425         inode = ocfs2_get_system_file_inode(osb, sysfile_type, slot);
5426         if (!inode) {
5427                 ret = -EINVAL;
5428                 mlog_errno(ret);
5429                 goto out;
5430         }
5431
5432         mutex_lock(&inode->i_mutex);
5433
5434         ret = ocfs2_inode_lock(inode, &di_bh, 1);
5435         if (ret) {
5436                 mlog_errno(ret);
5437                 goto out_mutex;
5438         }
5439
5440         handle = ocfs2_start_trans(osb, OCFS2_SUBALLOC_FREE);
5441         if (IS_ERR(handle)) {
5442                 ret = PTR_ERR(handle);
5443                 mlog_errno(ret);
5444                 goto out_unlock;
5445         }
5446
5447         while (head) {
5448                 bg_blkno = ocfs2_which_suballoc_group(head->free_blk,
5449                                                       head->free_bit);
5450                 mlog(0, "Free bit: (bit %u, blkno %llu)\n",
5451                      head->free_bit, (unsigned long long)head->free_blk);
5452
5453                 ret = ocfs2_free_suballoc_bits(handle, inode, di_bh,
5454                                                head->free_bit, bg_blkno, 1);
5455                 if (ret) {
5456                         mlog_errno(ret);
5457                         goto out_journal;
5458                 }
5459
5460                 ret = ocfs2_extend_trans(handle, OCFS2_SUBALLOC_FREE);
5461                 if (ret) {
5462                         mlog_errno(ret);
5463                         goto out_journal;
5464                 }
5465
5466                 tmp = head;
5467                 head = head->free_next;
5468                 kfree(tmp);
5469         }
5470
5471 out_journal:
5472         ocfs2_commit_trans(osb, handle);
5473
5474 out_unlock:
5475         ocfs2_inode_unlock(inode, 1);
5476         brelse(di_bh);
5477 out_mutex:
5478         mutex_unlock(&inode->i_mutex);
5479         iput(inode);
5480 out:
5481         while(head) {
5482                 /* Premature exit may have left some dangling items. */
5483                 tmp = head;
5484                 head = head->free_next;
5485                 kfree(tmp);
5486         }
5487
5488         return ret;
5489 }
5490
5491 int ocfs2_run_deallocs(struct ocfs2_super *osb,
5492                        struct ocfs2_cached_dealloc_ctxt *ctxt)
5493 {
5494         int ret = 0, ret2;
5495         struct ocfs2_per_slot_free_list *fl;
5496
5497         if (!ctxt)
5498                 return 0;
5499
5500         while (ctxt->c_first_suballocator) {
5501                 fl = ctxt->c_first_suballocator;
5502
5503                 if (fl->f_first) {
5504                         mlog(0, "Free items: (type %u, slot %d)\n",
5505                              fl->f_inode_type, fl->f_slot);
5506                         ret2 = ocfs2_free_cached_items(osb, fl->f_inode_type,
5507                                                        fl->f_slot, fl->f_first);
5508                         if (ret2)
5509                                 mlog_errno(ret2);
5510                         if (!ret)
5511                                 ret = ret2;
5512                 }
5513
5514                 ctxt->c_first_suballocator = fl->f_next_suballocator;
5515                 kfree(fl);
5516         }
5517
5518         return ret;
5519 }
5520
5521 static struct ocfs2_per_slot_free_list *
5522 ocfs2_find_per_slot_free_list(int type,
5523                               int slot,
5524                               struct ocfs2_cached_dealloc_ctxt *ctxt)
5525 {
5526         struct ocfs2_per_slot_free_list *fl = ctxt->c_first_suballocator;
5527
5528         while (fl) {
5529                 if (fl->f_inode_type == type && fl->f_slot == slot)
5530                         return fl;
5531
5532                 fl = fl->f_next_suballocator;
5533         }
5534
5535         fl = kmalloc(sizeof(*fl), GFP_NOFS);
5536         if (fl) {
5537                 fl->f_inode_type = type;
5538                 fl->f_slot = slot;
5539                 fl->f_first = NULL;
5540                 fl->f_next_suballocator = ctxt->c_first_suballocator;
5541
5542                 ctxt->c_first_suballocator = fl;
5543         }
5544         return fl;
5545 }
5546
5547 static int ocfs2_cache_block_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt,
5548                                      int type, int slot, u64 blkno,
5549                                      unsigned int bit)
5550 {
5551         int ret;
5552         struct ocfs2_per_slot_free_list *fl;
5553         struct ocfs2_cached_block_free *item;
5554
5555         fl = ocfs2_find_per_slot_free_list(type, slot, ctxt);
5556         if (fl == NULL) {
5557                 ret = -ENOMEM;
5558                 mlog_errno(ret);
5559                 goto out;
5560         }
5561
5562         item = kmalloc(sizeof(*item), GFP_NOFS);
5563         if (item == NULL) {
5564                 ret = -ENOMEM;
5565                 mlog_errno(ret);
5566                 goto out;
5567         }
5568
5569         mlog(0, "Insert: (type %d, slot %u, bit %u, blk %llu)\n",
5570              type, slot, bit, (unsigned long long)blkno);
5571
5572         item->free_blk = blkno;
5573         item->free_bit = bit;
5574         item->free_next = fl->f_first;
5575
5576         fl->f_first = item;
5577
5578         ret = 0;
5579 out:
5580         return ret;
5581 }
5582
5583 static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt,
5584                                          struct ocfs2_extent_block *eb)
5585 {
5586         return ocfs2_cache_block_dealloc(ctxt, EXTENT_ALLOC_SYSTEM_INODE,
5587                                          le16_to_cpu(eb->h_suballoc_slot),
5588                                          le64_to_cpu(eb->h_blkno),
5589                                          le16_to_cpu(eb->h_suballoc_bit));
5590 }
5591
5592 /* This function will figure out whether the currently last extent
5593  * block will be deleted, and if it will, what the new last extent
5594  * block will be so we can update his h_next_leaf_blk field, as well
5595  * as the dinodes i_last_eb_blk */
5596 static int ocfs2_find_new_last_ext_blk(struct inode *inode,
5597                                        unsigned int clusters_to_del,
5598                                        struct ocfs2_path *path,
5599                                        struct buffer_head **new_last_eb)
5600 {
5601         int next_free, ret = 0;
5602         u32 cpos;
5603         struct ocfs2_extent_rec *rec;
5604         struct ocfs2_extent_block *eb;
5605         struct ocfs2_extent_list *el;
5606         struct buffer_head *bh = NULL;
5607
5608         *new_last_eb = NULL;
5609
5610         /* we have no tree, so of course, no last_eb. */
5611         if (!path->p_tree_depth)
5612                 goto out;
5613
5614         /* trunc to zero special case - this makes tree_depth = 0
5615          * regardless of what it is.  */
5616         if (OCFS2_I(inode)->ip_clusters == clusters_to_del)
5617                 goto out;
5618
5619         el = path_leaf_el(path);
5620         BUG_ON(!el->l_next_free_rec);
5621
5622         /*
5623          * Make sure that this extent list will actually be empty
5624          * after we clear away the data. We can shortcut out if
5625          * there's more than one non-empty extent in the
5626          * list. Otherwise, a check of the remaining extent is
5627          * necessary.
5628          */
5629         next_free = le16_to_cpu(el->l_next_free_rec);
5630         rec = NULL;
5631         if (ocfs2_is_empty_extent(&el->l_recs[0])) {
5632                 if (next_free > 2)
5633                         goto out;
5634
5635                 /* We may have a valid extent in index 1, check it. */
5636                 if (next_free == 2)
5637                         rec = &el->l_recs[1];
5638
5639                 /*
5640                  * Fall through - no more nonempty extents, so we want
5641                  * to delete this leaf.
5642                  */
5643         } else {
5644                 if (next_free > 1)
5645                         goto out;
5646
5647                 rec = &el->l_recs[0];
5648         }
5649
5650         if (rec) {
5651                 /*
5652                  * Check it we'll only be trimming off the end of this
5653                  * cluster.
5654                  */
5655                 if (le16_to_cpu(rec->e_leaf_clusters) > clusters_to_del)
5656                         goto out;
5657         }
5658
5659         ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos);
5660         if (ret) {
5661                 mlog_errno(ret);
5662                 goto out;
5663         }
5664
5665         ret = ocfs2_find_leaf(inode, path_root_el(path), cpos, &bh);
5666         if (ret) {
5667                 mlog_errno(ret);
5668                 goto out;
5669         }
5670
5671         eb = (struct ocfs2_extent_block *) bh->b_data;
5672         el = &eb->h_list;
5673         if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
5674                 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
5675                 ret = -EROFS;
5676                 goto out;
5677         }
5678
5679         *new_last_eb = bh;
5680         get_bh(*new_last_eb);
5681         mlog(0, "returning block %llu, (cpos: %u)\n",
5682              (unsigned long long)le64_to_cpu(eb->h_blkno), cpos);
5683 out:
5684         brelse(bh);
5685
5686         return ret;
5687 }
5688
5689 /*
5690  * Trim some clusters off the rightmost edge of a tree. Only called
5691  * during truncate.
5692  *
5693  * The caller needs to:
5694  *   - start journaling of each path component.
5695  *   - compute and fully set up any new last ext block
5696  */
5697 static int ocfs2_trim_tree(struct inode *inode, struct ocfs2_path *path,
5698                            handle_t *handle, struct ocfs2_truncate_context *tc,
5699                            u32 clusters_to_del, u64 *delete_start)
5700 {
5701         int ret, i, index = path->p_tree_depth;
5702         u32 new_edge = 0;
5703         u64 deleted_eb = 0;
5704         struct buffer_head *bh;
5705         struct ocfs2_extent_list *el;
5706         struct ocfs2_extent_rec *rec;
5707
5708         *delete_start = 0;
5709
5710         while (index >= 0) {
5711                 bh = path->p_node[index].bh;
5712                 el = path->p_node[index].el;
5713
5714                 mlog(0, "traveling tree (index = %d, block = %llu)\n",
5715                      index,  (unsigned long long)bh->b_blocknr);
5716
5717                 BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0);
5718
5719                 if (index !=
5720                     (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) {
5721                         ocfs2_error(inode->i_sb,
5722                                     "Inode %lu has invalid ext. block %llu",
5723                                     inode->i_ino,
5724                                     (unsigned long long)bh->b_blocknr);
5725                         ret = -EROFS;
5726                         goto out;
5727                 }
5728
5729 find_tail_record:
5730                 i = le16_to_cpu(el->l_next_free_rec) - 1;
5731                 rec = &el->l_recs[i];
5732
5733                 mlog(0, "Extent list before: record %d: (%u, %u, %llu), "
5734                      "next = %u\n", i, le32_to_cpu(rec->e_cpos),
5735                      ocfs2_rec_clusters(el, rec),
5736                      (unsigned long long)le64_to_cpu(rec->e_blkno),
5737                      le16_to_cpu(el->l_next_free_rec));
5738
5739                 BUG_ON(ocfs2_rec_clusters(el, rec) < clusters_to_del);
5740
5741                 if (le16_to_cpu(el->l_tree_depth) == 0) {
5742                         /*
5743                          * If the leaf block contains a single empty
5744                          * extent and no records, we can just remove
5745                          * the block.
5746                          */
5747                         if (i == 0 && ocfs2_is_empty_extent(rec)) {
5748                                 memset(rec, 0,
5749                                        sizeof(struct ocfs2_extent_rec));
5750                                 el->l_next_free_rec = cpu_to_le16(0);
5751
5752                                 goto delete;
5753                         }
5754
5755                         /*
5756                          * Remove any empty extents by shifting things
5757                          * left. That should make life much easier on
5758                          * the code below. This condition is rare
5759                          * enough that we shouldn't see a performance
5760                          * hit.
5761                          */
5762                         if (ocfs2_is_empty_extent(&el->l_recs[0])) {
5763                                 le16_add_cpu(&el->l_next_free_rec, -1);
5764
5765                                 for(i = 0;
5766                                     i < le16_to_cpu(el->l_next_free_rec); i++)
5767                                         el->l_recs[i] = el->l_recs[i + 1];
5768
5769                                 memset(&el->l_recs[i], 0,
5770                                        sizeof(struct ocfs2_extent_rec));
5771
5772                                 /*
5773                                  * We've modified our extent list. The
5774                                  * simplest way to handle this change
5775                                  * is to being the search from the
5776                                  * start again.
5777                                  */
5778                                 goto find_tail_record;
5779                         }
5780
5781                         le16_add_cpu(&rec->e_leaf_clusters, -clusters_to_del);
5782
5783                         /*
5784                          * We'll use "new_edge" on our way back up the
5785                          * tree to know what our rightmost cpos is.
5786                          */
5787                         new_edge = le16_to_cpu(rec->e_leaf_clusters);
5788                         new_edge += le32_to_cpu(rec->e_cpos);
5789
5790                         /*
5791                          * The caller will use this to delete data blocks.
5792                          */
5793                         *delete_start = le64_to_cpu(rec->e_blkno)
5794                                 + ocfs2_clusters_to_blocks(inode->i_sb,
5795                                         le16_to_cpu(rec->e_leaf_clusters));
5796
5797                         /*
5798                          * If it's now empty, remove this record.
5799                          */
5800                         if (le16_to_cpu(rec->e_leaf_clusters) == 0) {
5801                                 memset(rec, 0,
5802                                        sizeof(struct ocfs2_extent_rec));
5803                                 le16_add_cpu(&el->l_next_free_rec, -1);
5804                         }
5805                 } else {
5806                         if (le64_to_cpu(rec->e_blkno) == deleted_eb) {
5807                                 memset(rec, 0,
5808                                        sizeof(struct ocfs2_extent_rec));
5809                                 le16_add_cpu(&el->l_next_free_rec, -1);
5810
5811                                 goto delete;
5812                         }
5813
5814                         /* Can this actually happen? */
5815                         if (le16_to_cpu(el->l_next_free_rec) == 0)
5816                                 goto delete;
5817
5818                         /*
5819                          * We never actually deleted any clusters
5820                          * because our leaf was empty. There's no
5821                          * reason to adjust the rightmost edge then.
5822                          */
5823                         if (new_edge == 0)
5824                                 goto delete;
5825
5826                         rec->e_int_clusters = cpu_to_le32(new_edge);
5827                         le32_add_cpu(&rec->e_int_clusters,
5828                                      -le32_to_cpu(rec->e_cpos));
5829
5830                          /*
5831                           * A deleted child record should have been
5832                           * caught above.
5833                           */
5834                          BUG_ON(le32_to_cpu(rec->e_int_clusters) == 0);
5835                 }
5836
5837 delete:
5838                 ret = ocfs2_journal_dirty(handle, bh);
5839                 if (ret) {
5840                         mlog_errno(ret);
5841                         goto out;
5842                 }
5843
5844                 mlog(0, "extent list container %llu, after: record %d: "
5845                      "(%u, %u, %llu), next = %u.\n",
5846                      (unsigned long long)bh->b_blocknr, i,
5847                      le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec),
5848                      (unsigned long long)le64_to_cpu(rec->e_blkno),
5849                      le16_to_cpu(el->l_next_free_rec));
5850
5851                 /*
5852                  * We must be careful to only attempt delete of an
5853                  * extent block (and not the root inode block).
5854                  */
5855                 if (index > 0 && le16_to_cpu(el->l_next_free_rec) == 0) {
5856                         struct ocfs2_extent_block *eb =
5857                                 (struct ocfs2_extent_block *)bh->b_data;
5858
5859                         /*
5860                          * Save this for use when processing the
5861                          * parent block.
5862                          */
5863                         deleted_eb = le64_to_cpu(eb->h_blkno);
5864
5865                         mlog(0, "deleting this extent block.\n");
5866
5867                         ocfs2_remove_from_cache(inode, bh);
5868
5869                         BUG_ON(ocfs2_rec_clusters(el, &el->l_recs[0]));
5870                         BUG_ON(le32_to_cpu(el->l_recs[0].e_cpos));
5871                         BUG_ON(le64_to_cpu(el->l_recs[0].e_blkno));
5872
5873                         ret = ocfs2_cache_extent_block_free(&tc->tc_dealloc, eb);
5874                         /* An error here is not fatal. */
5875                         if (ret < 0)
5876                                 mlog_errno(ret);
5877                 } else {
5878                         deleted_eb = 0;
5879                 }
5880
5881                 index--;
5882         }
5883
5884         ret = 0;
5885 out:
5886         return ret;
5887 }
5888
5889 static int ocfs2_do_truncate(struct ocfs2_super *osb,
5890                              unsigned int clusters_to_del,
5891                              struct inode *inode,
5892                              struct buffer_head *fe_bh,
5893                              handle_t *handle,
5894                              struct ocfs2_truncate_context *tc,
5895                              struct ocfs2_path *path)
5896 {
5897         int status;
5898         struct ocfs2_dinode *fe;
5899         struct ocfs2_extent_block *last_eb = NULL;
5900         struct ocfs2_extent_list *el;
5901         struct buffer_head *last_eb_bh = NULL;
5902         u64 delete_blk = 0;
5903
5904         fe = (struct ocfs2_dinode *) fe_bh->b_data;
5905
5906         status = ocfs2_find_new_last_ext_blk(inode, clusters_to_del,
5907                                              path, &last_eb_bh);
5908         if (status < 0) {
5909                 mlog_errno(status);
5910                 goto bail;
5911         }
5912
5913         /*
5914          * Each component will be touched, so we might as well journal
5915          * here to avoid having to handle errors later.
5916          */
5917         status = ocfs2_journal_access_path(inode, handle, path);
5918         if (status < 0) {
5919                 mlog_errno(status);
5920                 goto bail;
5921         }
5922
5923         if (last_eb_bh) {
5924                 status = ocfs2_journal_access(handle, inode, last_eb_bh,
5925                                               OCFS2_JOURNAL_ACCESS_WRITE);
5926                 if (status < 0) {
5927                         mlog_errno(status);
5928                         goto bail;
5929                 }
5930
5931                 last_eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
5932         }
5933
5934         el = &(fe->id2.i_list);
5935
5936         /*
5937          * Lower levels depend on this never happening, but it's best
5938          * to check it up here before changing the tree.
5939          */
5940         if (el->l_tree_depth && el->l_recs[0].e_int_clusters == 0) {
5941                 ocfs2_error(inode->i_sb,
5942                             "Inode %lu has an empty extent record, depth %u\n",
5943                             inode->i_ino, le16_to_cpu(el->l_tree_depth));
5944                 status = -EROFS;
5945                 goto bail;
5946         }
5947
5948         spin_lock(&OCFS2_I(inode)->ip_lock);
5949         OCFS2_I(inode)->ip_clusters = le32_to_cpu(fe->i_clusters) -
5950                                       clusters_to_del;
5951         spin_unlock(&OCFS2_I(inode)->ip_lock);
5952         le32_add_cpu(&fe->i_clusters, -clusters_to_del);
5953         inode->i_blocks = ocfs2_inode_sector_count(inode);
5954
5955         status = ocfs2_trim_tree(inode, path, handle, tc,
5956                                  clusters_to_del, &delete_blk);
5957         if (status) {
5958                 mlog_errno(status);
5959                 goto bail;
5960         }
5961
5962         if (le32_to_cpu(fe->i_clusters) == 0) {
5963                 /* trunc to zero is a special case. */
5964                 el->l_tree_depth = 0;
5965                 fe->i_last_eb_blk = 0;
5966         } else if (last_eb)
5967                 fe->i_last_eb_blk = last_eb->h_blkno;
5968
5969         status = ocfs2_journal_dirty(handle, fe_bh);
5970         if (status < 0) {
5971                 mlog_errno(status);
5972                 goto bail;
5973         }
5974
5975         if (last_eb) {
5976                 /* If there will be a new last extent block, then by
5977                  * definition, there cannot be any leaves to the right of
5978                  * him. */
5979                 last_eb->h_next_leaf_blk = 0;
5980                 status = ocfs2_journal_dirty(handle, last_eb_bh);
5981                 if (status < 0) {
5982                         mlog_errno(status);
5983                         goto bail;
5984                 }
5985         }
5986
5987         if (delete_blk) {
5988                 status = ocfs2_truncate_log_append(osb, handle, delete_blk,
5989                                                    clusters_to_del);
5990                 if (status < 0) {
5991                         mlog_errno(status);
5992                         goto bail;
5993                 }
5994         }
5995         status = 0;
5996 bail:
5997
5998         mlog_exit(status);
5999         return status;
6000 }
6001
6002 static int ocfs2_writeback_zero_func(handle_t *handle, struct buffer_head *bh)
6003 {
6004         set_buffer_uptodate(bh);
6005         mark_buffer_dirty(bh);
6006         return 0;
6007 }
6008
6009 static int ocfs2_ordered_zero_func(handle_t *handle, struct buffer_head *bh)
6010 {
6011         set_buffer_uptodate(bh);
6012         mark_buffer_dirty(bh);
6013         return ocfs2_journal_dirty_data(handle, bh);
6014 }
6015
6016 static void ocfs2_map_and_dirty_page(struct inode *inode, handle_t *handle,
6017                                      unsigned int from, unsigned int to,
6018                                      struct page *page, int zero, u64 *phys)
6019 {
6020         int ret, partial = 0;
6021
6022         ret = ocfs2_map_page_blocks(page, phys, inode, from, to, 0);
6023         if (ret)
6024                 mlog_errno(ret);
6025
6026         if (zero)
6027                 zero_user_segment(page, from, to);
6028
6029         /*
6030          * Need to set the buffers we zero'd into uptodate
6031          * here if they aren't - ocfs2_map_page_blocks()
6032          * might've skipped some
6033          */
6034         if (ocfs2_should_order_data(inode)) {
6035                 ret = walk_page_buffers(handle,
6036                                         page_buffers(page),
6037                                         from, to, &partial,
6038                                         ocfs2_ordered_zero_func);
6039                 if (ret < 0)
6040                         mlog_errno(ret);
6041         } else {
6042                 ret = walk_page_buffers(handle, page_buffers(page),
6043                                         from, to, &partial,
6044                                         ocfs2_writeback_zero_func);
6045                 if (ret < 0)
6046                         mlog_errno(ret);
6047         }
6048
6049         if (!partial)
6050                 SetPageUptodate(page);
6051
6052         flush_dcache_page(page);
6053 }
6054
6055 static void ocfs2_zero_cluster_pages(struct inode *inode, loff_t start,
6056                                      loff_t end, struct page **pages,
6057                                      int numpages, u64 phys, handle_t *handle)
6058 {
6059         int i;
6060         struct page *page;
6061         unsigned int from, to = PAGE_CACHE_SIZE;
6062         struct super_block *sb = inode->i_sb;
6063
6064         BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb)));
6065
6066         if (numpages == 0)
6067                 goto out;
6068
6069         to = PAGE_CACHE_SIZE;
6070         for(i = 0; i < numpages; i++) {
6071                 page = pages[i];
6072
6073                 from = start & (PAGE_CACHE_SIZE - 1);
6074                 if ((end >> PAGE_CACHE_SHIFT) == page->index)
6075                         to = end & (PAGE_CACHE_SIZE - 1);
6076
6077                 BUG_ON(from > PAGE_CACHE_SIZE);
6078                 BUG_ON(to > PAGE_CACHE_SIZE);
6079
6080                 ocfs2_map_and_dirty_page(inode, handle, from, to, page, 1,
6081                                          &phys);
6082
6083                 start = (page->index + 1) << PAGE_CACHE_SHIFT;
6084         }
6085 out:
6086         if (pages)
6087                 ocfs2_unlock_and_free_pages(pages, numpages);
6088 }
6089
6090 static int ocfs2_grab_eof_pages(struct inode *inode, loff_t start, loff_t end,
6091                                 struct page **pages, int *num)
6092 {
6093         int numpages, ret = 0;
6094         struct super_block *sb = inode->i_sb;
6095         struct address_space *mapping = inode->i_mapping;
6096         unsigned long index;
6097         loff_t last_page_bytes;
6098
6099         BUG_ON(start > end);
6100
6101         BUG_ON(start >> OCFS2_SB(sb)->s_clustersize_bits !=
6102                (end - 1) >> OCFS2_SB(sb)->s_clustersize_bits);
6103
6104         numpages = 0;
6105         last_page_bytes = PAGE_ALIGN(end);
6106         index = start >> PAGE_CACHE_SHIFT;
6107         do {
6108                 pages[numpages] = grab_cache_page(mapping, index);
6109                 if (!pages[numpages]) {
6110                         ret = -ENOMEM;
6111                         mlog_errno(ret);
6112                         goto out;
6113                 }
6114
6115                 numpages++;
6116                 index++;
6117         } while (index < (last_page_bytes >> PAGE_CACHE_SHIFT));
6118
6119 out:
6120         if (ret != 0) {
6121                 if (pages)
6122                         ocfs2_unlock_and_free_pages(pages, numpages);
6123                 numpages = 0;
6124         }
6125
6126         *num = numpages;
6127
6128         return ret;
6129 }
6130
6131 /*
6132  * Zero the area past i_size but still within an allocated
6133  * cluster. This avoids exposing nonzero data on subsequent file
6134  * extends.
6135  *
6136  * We need to call this before i_size is updated on the inode because
6137  * otherwise block_write_full_page() will skip writeout of pages past
6138  * i_size. The new_i_size parameter is passed for this reason.
6139  */
6140 int ocfs2_zero_range_for_truncate(struct inode *inode, handle_t *handle,
6141                                   u64 range_start, u64 range_end)
6142 {
6143         int ret = 0, numpages;
6144         struct page **pages = NULL;
6145         u64 phys;
6146         unsigned int ext_flags;
6147         struct super_block *sb = inode->i_sb;
6148
6149         /*
6150          * File systems which don't support sparse files zero on every
6151          * extend.
6152          */
6153         if (!ocfs2_sparse_alloc(OCFS2_SB(sb)))
6154                 return 0;
6155
6156         pages = kcalloc(ocfs2_pages_per_cluster(sb),
6157                         sizeof(struct page *), GFP_NOFS);
6158         if (pages == NULL) {
6159                 ret = -ENOMEM;
6160                 mlog_errno(ret);
6161                 goto out;
6162         }
6163
6164         if (range_start == range_end)
6165                 goto out;
6166
6167         ret = ocfs2_extent_map_get_blocks(inode,
6168                                           range_start >> sb->s_blocksize_bits,
6169                                           &phys, NULL, &ext_flags);
6170         if (ret) {
6171                 mlog_errno(ret);
6172                 goto out;
6173         }
6174
6175         /*
6176          * Tail is a hole, or is marked unwritten. In either case, we
6177          * can count on read and write to return/push zero's.
6178          */
6179         if (phys == 0 || ext_flags & OCFS2_EXT_UNWRITTEN)
6180                 goto out;
6181
6182         ret = ocfs2_grab_eof_pages(inode, range_start, range_end, pages,
6183                                    &numpages);
6184         if (ret) {
6185                 mlog_errno(ret);
6186                 goto out;
6187         }
6188
6189         ocfs2_zero_cluster_pages(inode, range_start, range_end, pages,
6190                                  numpages, phys, handle);
6191
6192         /*
6193          * Initiate writeout of the pages we zero'd here. We don't
6194          * wait on them - the truncate_inode_pages() call later will
6195          * do that for us.
6196          */
6197         ret = do_sync_mapping_range(inode->i_mapping, range_start,
6198                                     range_end - 1, SYNC_FILE_RANGE_WRITE);
6199         if (ret)
6200                 mlog_errno(ret);
6201
6202 out:
6203         if (pages)
6204                 kfree(pages);
6205
6206         return ret;
6207 }
6208
6209 static void ocfs2_zero_dinode_id2(struct inode *inode, struct ocfs2_dinode *di)
6210 {
6211         unsigned int blocksize = 1 << inode->i_sb->s_blocksize_bits;
6212
6213         memset(&di->id2, 0, blocksize - offsetof(struct ocfs2_dinode, id2));
6214 }
6215
6216 void ocfs2_dinode_new_extent_list(struct inode *inode,
6217                                   struct ocfs2_dinode *di)
6218 {
6219         ocfs2_zero_dinode_id2(inode, di);
6220         di->id2.i_list.l_tree_depth = 0;
6221         di->id2.i_list.l_next_free_rec = 0;
6222         di->id2.i_list.l_count = cpu_to_le16(ocfs2_extent_recs_per_inode(inode->i_sb));
6223 }
6224
6225 void ocfs2_set_inode_data_inline(struct inode *inode, struct ocfs2_dinode *di)
6226 {
6227         struct ocfs2_inode_info *oi = OCFS2_I(inode);
6228         struct ocfs2_inline_data *idata = &di->id2.i_data;
6229
6230         spin_lock(&oi->ip_lock);
6231         oi->ip_dyn_features |= OCFS2_INLINE_DATA_FL;
6232         di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features);
6233         spin_unlock(&oi->ip_lock);
6234
6235         /*
6236          * We clear the entire i_data structure here so that all
6237          * fields can be properly initialized.
6238          */
6239         ocfs2_zero_dinode_id2(inode, di);
6240
6241         idata->id_count = cpu_to_le16(ocfs2_max_inline_data(inode->i_sb));
6242 }
6243
6244 int ocfs2_convert_inline_data_to_extents(struct inode *inode,
6245                                          struct buffer_head *di_bh)
6246 {
6247         int ret, i, has_data, num_pages = 0;
6248         handle_t *handle;
6249         u64 uninitialized_var(block);
6250         struct ocfs2_inode_info *oi = OCFS2_I(inode);
6251         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
6252         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
6253         struct ocfs2_alloc_context *data_ac = NULL;
6254         struct page **pages = NULL;
6255         loff_t end = osb->s_clustersize;
6256
6257         has_data = i_size_read(inode) ? 1 : 0;
6258
6259         if (has_data) {
6260                 pages = kcalloc(ocfs2_pages_per_cluster(osb->sb),
6261                                 sizeof(struct page *), GFP_NOFS);
6262                 if (pages == NULL) {
6263                         ret = -ENOMEM;
6264                         mlog_errno(ret);
6265                         goto out;
6266                 }
6267
6268                 ret = ocfs2_reserve_clusters(osb, 1, &data_ac);
6269                 if (ret) {
6270                         mlog_errno(ret);
6271                         goto out;
6272                 }
6273         }
6274
6275         handle = ocfs2_start_trans(osb, OCFS2_INLINE_TO_EXTENTS_CREDITS);
6276         if (IS_ERR(handle)) {
6277                 ret = PTR_ERR(handle);
6278                 mlog_errno(ret);
6279                 goto out_unlock;
6280         }
6281
6282         ret = ocfs2_journal_access(handle, inode, di_bh,
6283                                    OCFS2_JOURNAL_ACCESS_WRITE);
6284         if (ret) {
6285                 mlog_errno(ret);
6286                 goto out_commit;
6287         }
6288
6289         if (has_data) {
6290                 u32 bit_off, num;
6291                 unsigned int page_end;
6292                 u64 phys;
6293
6294                 ret = ocfs2_claim_clusters(osb, handle, data_ac, 1, &bit_off,
6295                                            &num);
6296                 if (ret) {
6297                         mlog_errno(ret);
6298                         goto out_commit;
6299                 }
6300
6301                 /*
6302                  * Save two copies, one for insert, and one that can
6303                  * be changed by ocfs2_map_and_dirty_page() below.
6304                  */
6305                 block = phys = ocfs2_clusters_to_blocks(inode->i_sb, bit_off);
6306
6307                 /*
6308                  * Non sparse file systems zero on extend, so no need
6309                  * to do that now.
6310                  */
6311                 if (!ocfs2_sparse_alloc(osb) &&
6312                     PAGE_CACHE_SIZE < osb->s_clustersize)
6313                         end = PAGE_CACHE_SIZE;
6314
6315                 ret = ocfs2_grab_eof_pages(inode, 0, end, pages, &num_pages);
6316                 if (ret) {
6317                         mlog_errno(ret);
6318                         goto out_commit;
6319                 }
6320
6321                 /*
6322                  * This should populate the 1st page for us and mark
6323                  * it up to date.
6324                  */
6325                 ret = ocfs2_read_inline_data(inode, pages[0], di_bh);
6326                 if (ret) {
6327                         mlog_errno(ret);
6328                         goto out_commit;
6329                 }
6330
6331                 page_end = PAGE_CACHE_SIZE;
6332                 if (PAGE_CACHE_SIZE > osb->s_clustersize)
6333                         page_end = osb->s_clustersize;
6334
6335                 for (i = 0; i < num_pages; i++)
6336                         ocfs2_map_and_dirty_page(inode, handle, 0, page_end,
6337                                                  pages[i], i > 0, &phys);
6338         }
6339
6340         spin_lock(&oi->ip_lock);
6341         oi->ip_dyn_features &= ~OCFS2_INLINE_DATA_FL;
6342         di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features);
6343         spin_unlock(&oi->ip_lock);
6344
6345         ocfs2_dinode_new_extent_list(inode, di);
6346
6347         ocfs2_journal_dirty(handle, di_bh);
6348
6349         if (has_data) {
6350                 /*
6351                  * An error at this point should be extremely rare. If
6352                  * this proves to be false, we could always re-build
6353                  * the in-inode data from our pages.
6354                  */
6355                 ret = ocfs2_insert_extent(osb, handle, inode, di_bh,
6356                                           0, block, 1, 0, NULL);
6357                 if (ret) {
6358                         mlog_errno(ret);
6359                         goto out_commit;
6360                 }
6361
6362                 inode->i_blocks = ocfs2_inode_sector_count(inode);
6363         }
6364
6365 out_commit:
6366         ocfs2_commit_trans(osb, handle);
6367
6368 out_unlock:
6369         if (data_ac)
6370                 ocfs2_free_alloc_context(data_ac);
6371
6372 out:
6373         if (pages) {
6374                 ocfs2_unlock_and_free_pages(pages, num_pages);
6375                 kfree(pages);
6376         }
6377
6378         return ret;
6379 }
6380
6381 /*
6382  * It is expected, that by the time you call this function,
6383  * inode->i_size and fe->i_size have been adjusted.
6384  *
6385  * WARNING: This will kfree the truncate context
6386  */
6387 int ocfs2_commit_truncate(struct ocfs2_super *osb,
6388                           struct inode *inode,
6389                           struct buffer_head *fe_bh,
6390                           struct ocfs2_truncate_context *tc)
6391 {
6392         int status, i, credits, tl_sem = 0;
6393         u32 clusters_to_del, new_highest_cpos, range;
6394         struct ocfs2_extent_list *el;
6395         handle_t *handle = NULL;
6396         struct inode *tl_inode = osb->osb_tl_inode;
6397         struct ocfs2_path *path = NULL;
6398
6399         mlog_entry_void();
6400
6401         new_highest_cpos = ocfs2_clusters_for_bytes(osb->sb,
6402                                                      i_size_read(inode));
6403
6404         path = ocfs2_new_inode_path(fe_bh);
6405         if (!path) {
6406                 status = -ENOMEM;
6407                 mlog_errno(status);
6408                 goto bail;
6409         }
6410
6411         ocfs2_extent_map_trunc(inode, new_highest_cpos);
6412
6413 start:
6414         /*
6415          * Check that we still have allocation to delete.
6416          */
6417         if (OCFS2_I(inode)->ip_clusters == 0) {
6418                 status = 0;
6419                 goto bail;
6420         }
6421
6422         /*
6423          * Truncate always works against the rightmost tree branch.
6424          */
6425         status = ocfs2_find_path(inode, path, UINT_MAX);
6426         if (status) {
6427                 mlog_errno(status);
6428                 goto bail;
6429         }
6430
6431         mlog(0, "inode->ip_clusters = %u, tree_depth = %u\n",
6432              OCFS2_I(inode)->ip_clusters, path->p_tree_depth);
6433
6434         /*
6435          * By now, el will point to the extent list on the bottom most
6436          * portion of this tree. Only the tail record is considered in
6437          * each pass.
6438          *
6439          * We handle the following cases, in order:
6440          * - empty extent: delete the remaining branch
6441          * - remove the entire record
6442          * - remove a partial record
6443          * - no record needs to be removed (truncate has completed)
6444          */
6445         el = path_leaf_el(path);
6446         if (le16_to_cpu(el->l_next_free_rec) == 0) {
6447                 ocfs2_error(inode->i_sb,
6448                             "Inode %llu has empty extent block at %llu\n",
6449                             (unsigned long long)OCFS2_I(inode)->ip_blkno,
6450                             (unsigned long long)path_leaf_bh(path)->b_blocknr);
6451                 status = -EROFS;
6452                 goto bail;
6453         }
6454
6455         i = le16_to_cpu(el->l_next_free_rec) - 1;
6456         range = le32_to_cpu(el->l_recs[i].e_cpos) +
6457                 ocfs2_rec_clusters(el, &el->l_recs[i]);
6458         if (i == 0 && ocfs2_is_empty_extent(&el->l_recs[i])) {
6459                 clusters_to_del = 0;
6460         } else if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_highest_cpos) {
6461                 clusters_to_del = ocfs2_rec_clusters(el, &el->l_recs[i]);
6462         } else if (range > new_highest_cpos) {
6463                 clusters_to_del = (ocfs2_rec_clusters(el, &el->l_recs[i]) +
6464                                    le32_to_cpu(el->l_recs[i].e_cpos)) -
6465                                   new_highest_cpos;
6466         } else {
6467                 status = 0;
6468                 goto bail;
6469         }
6470
6471         mlog(0, "clusters_to_del = %u in this pass, tail blk=%llu\n",
6472              clusters_to_del, (unsigned long long)path_leaf_bh(path)->b_blocknr);
6473
6474         mutex_lock(&tl_inode->i_mutex);
6475         tl_sem = 1;
6476         /* ocfs2_truncate_log_needs_flush guarantees us at least one
6477          * record is free for use. If there isn't any, we flush to get
6478          * an empty truncate log.  */
6479         if (ocfs2_truncate_log_needs_flush(osb)) {
6480                 status = __ocfs2_flush_truncate_log(osb);
6481                 if (status < 0) {
6482                         mlog_errno(status);
6483                         goto bail;
6484                 }
6485         }
6486
6487         credits = ocfs2_calc_tree_trunc_credits(osb->sb, clusters_to_del,
6488                                                 (struct ocfs2_dinode *)fe_bh->b_data,
6489                                                 el);
6490         handle = ocfs2_start_trans(osb, credits);
6491         if (IS_ERR(handle)) {
6492                 status = PTR_ERR(handle);
6493                 handle = NULL;
6494                 mlog_errno(status);
6495                 goto bail;
6496         }
6497
6498         status = ocfs2_do_truncate(osb, clusters_to_del, inode, fe_bh, handle,
6499                                    tc, path);
6500         if (status < 0) {
6501                 mlog_errno(status);
6502                 goto bail;
6503         }
6504
6505         mutex_unlock(&tl_inode->i_mutex);
6506         tl_sem = 0;
6507
6508         ocfs2_commit_trans(osb, handle);
6509         handle = NULL;
6510
6511         ocfs2_reinit_path(path, 1);
6512
6513         /*
6514          * The check above will catch the case where we've truncated
6515          * away all allocation.
6516          */
6517         goto start;
6518
6519 bail:
6520
6521         ocfs2_schedule_truncate_log_flush(osb, 1);
6522
6523         if (tl_sem)
6524                 mutex_unlock(&tl_inode->i_mutex);
6525
6526         if (handle)
6527                 ocfs2_commit_trans(osb, handle);
6528
6529         ocfs2_run_deallocs(osb, &tc->tc_dealloc);
6530
6531         ocfs2_free_path(path);
6532
6533         /* This will drop the ext_alloc cluster lock for us */
6534         ocfs2_free_truncate_context(tc);
6535
6536         mlog_exit(status);
6537         return status;
6538 }
6539
6540 /*
6541  * Expects the inode to already be locked.
6542  */
6543 int ocfs2_prepare_truncate(struct ocfs2_super *osb,
6544                            struct inode *inode,
6545                            struct buffer_head *fe_bh,
6546                            struct ocfs2_truncate_context **tc)
6547 {
6548         int status;
6549         unsigned int new_i_clusters;
6550         struct ocfs2_dinode *fe;
6551         struct ocfs2_extent_block *eb;
6552         struct buffer_head *last_eb_bh = NULL;
6553
6554         mlog_entry_void();
6555
6556         *tc = NULL;
6557
6558         new_i_clusters = ocfs2_clusters_for_bytes(osb->sb,
6559                                                   i_size_read(inode));
6560         fe = (struct ocfs2_dinode *) fe_bh->b_data;
6561
6562         mlog(0, "fe->i_clusters = %u, new_i_clusters = %u, fe->i_size ="
6563              "%llu\n", le32_to_cpu(fe->i_clusters), new_i_clusters,
6564              (unsigned long long)le64_to_cpu(fe->i_size));
6565
6566         *tc = kzalloc(sizeof(struct ocfs2_truncate_context), GFP_KERNEL);
6567         if (!(*tc)) {
6568                 status = -ENOMEM;
6569                 mlog_errno(status);
6570                 goto bail;
6571         }
6572         ocfs2_init_dealloc_ctxt(&(*tc)->tc_dealloc);
6573
6574         if (fe->id2.i_list.l_tree_depth) {
6575                 status = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk),
6576                                           &last_eb_bh, OCFS2_BH_CACHED, inode);
6577                 if (status < 0) {
6578                         mlog_errno(status);
6579                         goto bail;
6580                 }
6581                 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
6582                 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
6583                         OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
6584
6585                         brelse(last_eb_bh);
6586                         status = -EIO;
6587                         goto bail;
6588                 }
6589         }
6590
6591         (*tc)->tc_last_eb_bh = last_eb_bh;
6592
6593         status = 0;
6594 bail:
6595         if (status < 0) {
6596                 if (*tc)
6597                         ocfs2_free_truncate_context(*tc);
6598                 *tc = NULL;
6599         }
6600         mlog_exit_void();
6601         return status;
6602 }
6603
6604 /*
6605  * 'start' is inclusive, 'end' is not.
6606  */
6607 int ocfs2_truncate_inline(struct inode *inode, struct buffer_head *di_bh,
6608                           unsigned int start, unsigned int end, int trunc)
6609 {
6610         int ret;
6611         unsigned int numbytes;
6612         handle_t *handle;
6613         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
6614         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
6615         struct ocfs2_inline_data *idata = &di->id2.i_data;
6616
6617         if (end > i_size_read(inode))
6618                 end = i_size_read(inode);
6619
6620         BUG_ON(start >= end);
6621
6622         if (!(OCFS2_I(inode)->ip_dyn_features & OCFS2_INLINE_DATA_FL) ||
6623             !(le16_to_cpu(di->i_dyn_features) & OCFS2_INLINE_DATA_FL) ||
6624             !ocfs2_supports_inline_data(osb)) {
6625                 ocfs2_error(inode->i_sb,
6626                             "Inline data flags for inode %llu don't agree! "
6627                             "Disk: 0x%x, Memory: 0x%x, Superblock: 0x%x\n",
6628                             (unsigned long long)OCFS2_I(inode)->ip_blkno,
6629                             le16_to_cpu(di->i_dyn_features),
6630                             OCFS2_I(inode)->ip_dyn_features,
6631                             osb->s_feature_incompat);
6632                 ret = -EROFS;
6633                 goto out;
6634         }
6635
6636         handle = ocfs2_start_trans(osb, OCFS2_INODE_UPDATE_CREDITS);
6637         if (IS_ERR(handle)) {
6638                 ret = PTR_ERR(handle);
6639                 mlog_errno(ret);
6640                 goto out;
6641         }
6642
6643         ret = ocfs2_journal_access(handle, inode, di_bh,
6644                                    OCFS2_JOURNAL_ACCESS_WRITE);
6645         if (ret) {
6646                 mlog_errno(ret);
6647                 goto out_commit;
6648         }
6649
6650         numbytes = end - start;
6651         memset(idata->id_data + start, 0, numbytes);
6652
6653         /*
6654          * No need to worry about the data page here - it's been
6655          * truncated already and inline data doesn't need it for
6656          * pushing zero's to disk, so we'll let readpage pick it up
6657          * later.
6658          */
6659         if (trunc) {
6660                 i_size_write(inode, start);
6661                 di->i_size = cpu_to_le64(start);
6662         }
6663
6664         inode->i_blocks = ocfs2_inode_sector_count(inode);
6665         inode->i_ctime = inode->i_mtime = CURRENT_TIME;
6666
6667         di->i_ctime = di->i_mtime = cpu_to_le64(inode->i_ctime.tv_sec);
6668         di->i_ctime_nsec = di->i_mtime_nsec = cpu_to_le32(inode->i_ctime.tv_nsec);
6669
6670         ocfs2_journal_dirty(handle, di_bh);
6671
6672 out_commit:
6673         ocfs2_commit_trans(osb, handle);
6674
6675 out:
6676         return ret;
6677 }
6678
6679 static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc)
6680 {
6681         /*
6682          * The caller is responsible for completing deallocation
6683          * before freeing the context.
6684          */
6685         if (tc->tc_dealloc.c_first_suballocator != NULL)
6686                 mlog(ML_NOTICE,
6687                      "Truncate completion has non-empty dealloc context\n");
6688
6689         if (tc->tc_last_eb_bh)
6690                 brelse(tc->tc_last_eb_bh);
6691
6692         kfree(tc);
6693 }