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