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