Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/benh/powerpc
[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 /*
4800  * Mark part or all of the extent record at split_index in the leaf
4801  * pointed to by path as written. This removes the unwritten
4802  * extent flag.
4803  *
4804  * Care is taken to handle contiguousness so as to not grow the tree.
4805  *
4806  * meta_ac is not strictly necessary - we only truly need it if growth
4807  * of the tree is required. All other cases will degrade into a less
4808  * optimal tree layout.
4809  *
4810  * last_eb_bh should be the rightmost leaf block for any extent
4811  * btree. Since a split may grow the tree or a merge might shrink it,
4812  * the caller cannot trust the contents of that buffer after this call.
4813  *
4814  * This code is optimized for readability - several passes might be
4815  * made over certain portions of the tree. All of those blocks will
4816  * have been brought into cache (and pinned via the journal), so the
4817  * extra overhead is not expressed in terms of disk reads.
4818  */
4819 static int __ocfs2_mark_extent_written(struct inode *inode,
4820                                        struct ocfs2_extent_tree *et,
4821                                        handle_t *handle,
4822                                        struct ocfs2_path *path,
4823                                        int split_index,
4824                                        struct ocfs2_extent_rec *split_rec,
4825                                        struct ocfs2_alloc_context *meta_ac,
4826                                        struct ocfs2_cached_dealloc_ctxt *dealloc)
4827 {
4828         int ret = 0;
4829         struct ocfs2_extent_list *el = path_leaf_el(path);
4830         struct buffer_head *last_eb_bh = NULL;
4831         struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
4832         struct ocfs2_merge_ctxt ctxt;
4833         struct ocfs2_extent_list *rightmost_el;
4834
4835         if (!(rec->e_flags & OCFS2_EXT_UNWRITTEN)) {
4836                 ret = -EIO;
4837                 mlog_errno(ret);
4838                 goto out;
4839         }
4840
4841         if (le32_to_cpu(rec->e_cpos) > le32_to_cpu(split_rec->e_cpos) ||
4842             ((le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)) <
4843              (le32_to_cpu(split_rec->e_cpos) + le16_to_cpu(split_rec->e_leaf_clusters)))) {
4844                 ret = -EIO;
4845                 mlog_errno(ret);
4846                 goto out;
4847         }
4848
4849         ctxt.c_contig_type = ocfs2_figure_merge_contig_type(inode, path, el,
4850                                                             split_index,
4851                                                             split_rec);
4852
4853         /*
4854          * The core merge / split code wants to know how much room is
4855          * left in this inodes allocation tree, so we pass the
4856          * rightmost extent list.
4857          */
4858         if (path->p_tree_depth) {
4859                 struct ocfs2_extent_block *eb;
4860
4861                 ret = ocfs2_read_extent_block(inode,
4862                                               ocfs2_et_get_last_eb_blk(et),
4863                                               &last_eb_bh);
4864                 if (ret) {
4865                         mlog_exit(ret);
4866                         goto out;
4867                 }
4868
4869                 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
4870                 rightmost_el = &eb->h_list;
4871         } else
4872                 rightmost_el = path_root_el(path);
4873
4874         if (rec->e_cpos == split_rec->e_cpos &&
4875             rec->e_leaf_clusters == split_rec->e_leaf_clusters)
4876                 ctxt.c_split_covers_rec = 1;
4877         else
4878                 ctxt.c_split_covers_rec = 0;
4879
4880         ctxt.c_has_empty_extent = ocfs2_is_empty_extent(&el->l_recs[0]);
4881
4882         mlog(0, "index: %d, contig: %u, has_empty: %u, split_covers: %u\n",
4883              split_index, ctxt.c_contig_type, ctxt.c_has_empty_extent,
4884              ctxt.c_split_covers_rec);
4885
4886         if (ctxt.c_contig_type == CONTIG_NONE) {
4887                 if (ctxt.c_split_covers_rec)
4888                         el->l_recs[split_index] = *split_rec;
4889                 else
4890                         ret = ocfs2_split_and_insert(inode, handle, path, et,
4891                                                      &last_eb_bh, split_index,
4892                                                      split_rec, meta_ac);
4893                 if (ret)
4894                         mlog_errno(ret);
4895         } else {
4896                 ret = ocfs2_try_to_merge_extent(inode, handle, path,
4897                                                 split_index, split_rec,
4898                                                 dealloc, &ctxt, et);
4899                 if (ret)
4900                         mlog_errno(ret);
4901         }
4902
4903 out:
4904         brelse(last_eb_bh);
4905         return ret;
4906 }
4907
4908 /*
4909  * Mark the already-existing extent at cpos as written for len clusters.
4910  *
4911  * If the existing extent is larger than the request, initiate a
4912  * split. An attempt will be made at merging with adjacent extents.
4913  *
4914  * The caller is responsible for passing down meta_ac if we'll need it.
4915  */
4916 int ocfs2_mark_extent_written(struct inode *inode,
4917                               struct ocfs2_extent_tree *et,
4918                               handle_t *handle, u32 cpos, u32 len, u32 phys,
4919                               struct ocfs2_alloc_context *meta_ac,
4920                               struct ocfs2_cached_dealloc_ctxt *dealloc)
4921 {
4922         int ret, index;
4923         u64 start_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys);
4924         struct ocfs2_extent_rec split_rec;
4925         struct ocfs2_path *left_path = NULL;
4926         struct ocfs2_extent_list *el;
4927
4928         mlog(0, "Inode %lu cpos %u, len %u, phys %u (%llu)\n",
4929              inode->i_ino, cpos, len, phys, (unsigned long long)start_blkno);
4930
4931         if (!ocfs2_writes_unwritten_extents(OCFS2_SB(inode->i_sb))) {
4932                 ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents "
4933                             "that are being written to, but the feature bit "
4934                             "is not set in the super block.",
4935                             (unsigned long long)OCFS2_I(inode)->ip_blkno);
4936                 ret = -EROFS;
4937                 goto out;
4938         }
4939
4940         /*
4941          * XXX: This should be fixed up so that we just re-insert the
4942          * next extent records.
4943          *
4944          * XXX: This is a hack on the extent tree, maybe it should be
4945          * an op?
4946          */
4947         if (et->et_ops == &ocfs2_dinode_et_ops)
4948                 ocfs2_extent_map_trunc(inode, 0);
4949
4950         left_path = ocfs2_new_path_from_et(et);
4951         if (!left_path) {
4952                 ret = -ENOMEM;
4953                 mlog_errno(ret);
4954                 goto out;
4955         }
4956
4957         ret = ocfs2_find_path(inode, left_path, cpos);
4958         if (ret) {
4959                 mlog_errno(ret);
4960                 goto out;
4961         }
4962         el = path_leaf_el(left_path);
4963
4964         index = ocfs2_search_extent_list(el, cpos);
4965         if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4966                 ocfs2_error(inode->i_sb,
4967                             "Inode %llu has an extent at cpos %u which can no "
4968                             "longer be found.\n",
4969                             (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos);
4970                 ret = -EROFS;
4971                 goto out;
4972         }
4973
4974         memset(&split_rec, 0, sizeof(struct ocfs2_extent_rec));
4975         split_rec.e_cpos = cpu_to_le32(cpos);
4976         split_rec.e_leaf_clusters = cpu_to_le16(len);
4977         split_rec.e_blkno = cpu_to_le64(start_blkno);
4978         split_rec.e_flags = path_leaf_el(left_path)->l_recs[index].e_flags;
4979         split_rec.e_flags &= ~OCFS2_EXT_UNWRITTEN;
4980
4981         ret = __ocfs2_mark_extent_written(inode, et, handle, left_path,
4982                                           index, &split_rec, meta_ac,
4983                                           dealloc);
4984         if (ret)
4985                 mlog_errno(ret);
4986
4987 out:
4988         ocfs2_free_path(left_path);
4989         return ret;
4990 }
4991
4992 static int ocfs2_split_tree(struct inode *inode, struct ocfs2_extent_tree *et,
4993                             handle_t *handle, struct ocfs2_path *path,
4994                             int index, u32 new_range,
4995                             struct ocfs2_alloc_context *meta_ac)
4996 {
4997         int ret, depth, credits = handle->h_buffer_credits;
4998         struct buffer_head *last_eb_bh = NULL;
4999         struct ocfs2_extent_block *eb;
5000         struct ocfs2_extent_list *rightmost_el, *el;
5001         struct ocfs2_extent_rec split_rec;
5002         struct ocfs2_extent_rec *rec;
5003         struct ocfs2_insert_type insert;
5004
5005         /*
5006          * Setup the record to split before we grow the tree.
5007          */
5008         el = path_leaf_el(path);
5009         rec = &el->l_recs[index];
5010         ocfs2_make_right_split_rec(inode->i_sb, &split_rec, new_range, rec);
5011
5012         depth = path->p_tree_depth;
5013         if (depth > 0) {
5014                 ret = ocfs2_read_extent_block(inode,
5015                                               ocfs2_et_get_last_eb_blk(et),
5016                                               &last_eb_bh);
5017                 if (ret < 0) {
5018                         mlog_errno(ret);
5019                         goto out;
5020                 }
5021
5022                 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
5023                 rightmost_el = &eb->h_list;
5024         } else
5025                 rightmost_el = path_leaf_el(path);
5026
5027         credits += path->p_tree_depth +
5028                    ocfs2_extend_meta_needed(et->et_root_el);
5029         ret = ocfs2_extend_trans(handle, credits);
5030         if (ret) {
5031                 mlog_errno(ret);
5032                 goto out;
5033         }
5034
5035         if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
5036             le16_to_cpu(rightmost_el->l_count)) {
5037                 ret = ocfs2_grow_tree(inode, handle, et, &depth, &last_eb_bh,
5038                                       meta_ac);
5039                 if (ret) {
5040                         mlog_errno(ret);
5041                         goto out;
5042                 }
5043         }
5044
5045         memset(&insert, 0, sizeof(struct ocfs2_insert_type));
5046         insert.ins_appending = APPEND_NONE;
5047         insert.ins_contig = CONTIG_NONE;
5048         insert.ins_split = SPLIT_RIGHT;
5049         insert.ins_tree_depth = depth;
5050
5051         ret = ocfs2_do_insert_extent(inode, handle, et, &split_rec, &insert);
5052         if (ret)
5053                 mlog_errno(ret);
5054
5055 out:
5056         brelse(last_eb_bh);
5057         return ret;
5058 }
5059
5060 static int ocfs2_truncate_rec(struct inode *inode, handle_t *handle,
5061                               struct ocfs2_path *path, int index,
5062                               struct ocfs2_cached_dealloc_ctxt *dealloc,
5063                               u32 cpos, u32 len,
5064                               struct ocfs2_extent_tree *et)
5065 {
5066         int ret;
5067         u32 left_cpos, rec_range, trunc_range;
5068         int wants_rotate = 0, is_rightmost_tree_rec = 0;
5069         struct super_block *sb = inode->i_sb;
5070         struct ocfs2_path *left_path = NULL;
5071         struct ocfs2_extent_list *el = path_leaf_el(path);
5072         struct ocfs2_extent_rec *rec;
5073         struct ocfs2_extent_block *eb;
5074
5075         if (ocfs2_is_empty_extent(&el->l_recs[0]) && index > 0) {
5076                 ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc, et);
5077                 if (ret) {
5078                         mlog_errno(ret);
5079                         goto out;
5080                 }
5081
5082                 index--;
5083         }
5084
5085         if (index == (le16_to_cpu(el->l_next_free_rec) - 1) &&
5086             path->p_tree_depth) {
5087                 /*
5088                  * Check whether this is the rightmost tree record. If
5089                  * we remove all of this record or part of its right
5090                  * edge then an update of the record lengths above it
5091                  * will be required.
5092                  */
5093                 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
5094                 if (eb->h_next_leaf_blk == 0)
5095                         is_rightmost_tree_rec = 1;
5096         }
5097
5098         rec = &el->l_recs[index];
5099         if (index == 0 && path->p_tree_depth &&
5100             le32_to_cpu(rec->e_cpos) == cpos) {
5101                 /*
5102                  * Changing the leftmost offset (via partial or whole
5103                  * record truncate) of an interior (or rightmost) path
5104                  * means we have to update the subtree that is formed
5105                  * by this leaf and the one to it's left.
5106                  *
5107                  * There are two cases we can skip:
5108                  *   1) Path is the leftmost one in our inode tree.
5109                  *   2) The leaf is rightmost and will be empty after
5110                  *      we remove the extent record - the rotate code
5111                  *      knows how to update the newly formed edge.
5112                  */
5113
5114                 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path,
5115                                                     &left_cpos);
5116                 if (ret) {
5117                         mlog_errno(ret);
5118                         goto out;
5119                 }
5120
5121                 if (left_cpos && le16_to_cpu(el->l_next_free_rec) > 1) {
5122                         left_path = ocfs2_new_path_from_path(path);
5123                         if (!left_path) {
5124                                 ret = -ENOMEM;
5125                                 mlog_errno(ret);
5126                                 goto out;
5127                         }
5128
5129                         ret = ocfs2_find_path(inode, left_path, left_cpos);
5130                         if (ret) {
5131                                 mlog_errno(ret);
5132                                 goto out;
5133                         }
5134                 }
5135         }
5136
5137         ret = ocfs2_extend_rotate_transaction(handle, 0,
5138                                               handle->h_buffer_credits,
5139                                               path);
5140         if (ret) {
5141                 mlog_errno(ret);
5142                 goto out;
5143         }
5144
5145         ret = ocfs2_journal_access_path(inode, handle, path);
5146         if (ret) {
5147                 mlog_errno(ret);
5148                 goto out;
5149         }
5150
5151         ret = ocfs2_journal_access_path(inode, handle, left_path);
5152         if (ret) {
5153                 mlog_errno(ret);
5154                 goto out;
5155         }
5156
5157         rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
5158         trunc_range = cpos + len;
5159
5160         if (le32_to_cpu(rec->e_cpos) == cpos && rec_range == trunc_range) {
5161                 int next_free;
5162
5163                 memset(rec, 0, sizeof(*rec));
5164                 ocfs2_cleanup_merge(el, index);
5165                 wants_rotate = 1;
5166
5167                 next_free = le16_to_cpu(el->l_next_free_rec);
5168                 if (is_rightmost_tree_rec && next_free > 1) {
5169                         /*
5170                          * We skip the edge update if this path will
5171                          * be deleted by the rotate code.
5172                          */
5173                         rec = &el->l_recs[next_free - 1];
5174                         ocfs2_adjust_rightmost_records(inode, handle, path,
5175                                                        rec);
5176                 }
5177         } else if (le32_to_cpu(rec->e_cpos) == cpos) {
5178                 /* Remove leftmost portion of the record. */
5179                 le32_add_cpu(&rec->e_cpos, len);
5180                 le64_add_cpu(&rec->e_blkno, ocfs2_clusters_to_blocks(sb, len));
5181                 le16_add_cpu(&rec->e_leaf_clusters, -len);
5182         } else if (rec_range == trunc_range) {
5183                 /* Remove rightmost portion of the record */
5184                 le16_add_cpu(&rec->e_leaf_clusters, -len);
5185                 if (is_rightmost_tree_rec)
5186                         ocfs2_adjust_rightmost_records(inode, handle, path, rec);
5187         } else {
5188                 /* Caller should have trapped this. */
5189                 mlog(ML_ERROR, "Inode %llu: Invalid record truncate: (%u, %u) "
5190                      "(%u, %u)\n", (unsigned long long)OCFS2_I(inode)->ip_blkno,
5191                      le32_to_cpu(rec->e_cpos),
5192                      le16_to_cpu(rec->e_leaf_clusters), cpos, len);
5193                 BUG();
5194         }
5195
5196         if (left_path) {
5197                 int subtree_index;
5198
5199                 subtree_index = ocfs2_find_subtree_root(inode, left_path, path);
5200                 ocfs2_complete_edge_insert(inode, handle, left_path, path,
5201                                            subtree_index);
5202         }
5203
5204         ocfs2_journal_dirty(handle, path_leaf_bh(path));
5205
5206         ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc, et);
5207         if (ret) {
5208                 mlog_errno(ret);
5209                 goto out;
5210         }
5211
5212 out:
5213         ocfs2_free_path(left_path);
5214         return ret;
5215 }
5216
5217 int ocfs2_remove_extent(struct inode *inode,
5218                         struct ocfs2_extent_tree *et,
5219                         u32 cpos, u32 len, handle_t *handle,
5220                         struct ocfs2_alloc_context *meta_ac,
5221                         struct ocfs2_cached_dealloc_ctxt *dealloc)
5222 {
5223         int ret, index;
5224         u32 rec_range, trunc_range;
5225         struct ocfs2_extent_rec *rec;
5226         struct ocfs2_extent_list *el;
5227         struct ocfs2_path *path = NULL;
5228
5229         ocfs2_extent_map_trunc(inode, 0);
5230
5231         path = ocfs2_new_path_from_et(et);
5232         if (!path) {
5233                 ret = -ENOMEM;
5234                 mlog_errno(ret);
5235                 goto out;
5236         }
5237
5238         ret = ocfs2_find_path(inode, path, cpos);
5239         if (ret) {
5240                 mlog_errno(ret);
5241                 goto out;
5242         }
5243
5244         el = path_leaf_el(path);
5245         index = ocfs2_search_extent_list(el, cpos);
5246         if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
5247                 ocfs2_error(inode->i_sb,
5248                             "Inode %llu has an extent at cpos %u which can no "
5249                             "longer be found.\n",
5250                             (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos);
5251                 ret = -EROFS;
5252                 goto out;
5253         }
5254
5255         /*
5256          * We have 3 cases of extent removal:
5257          *   1) Range covers the entire extent rec
5258          *   2) Range begins or ends on one edge of the extent rec
5259          *   3) Range is in the middle of the extent rec (no shared edges)
5260          *
5261          * For case 1 we remove the extent rec and left rotate to
5262          * fill the hole.
5263          *
5264          * For case 2 we just shrink the existing extent rec, with a
5265          * tree update if the shrinking edge is also the edge of an
5266          * extent block.
5267          *
5268          * For case 3 we do a right split to turn the extent rec into
5269          * something case 2 can handle.
5270          */
5271         rec = &el->l_recs[index];
5272         rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
5273         trunc_range = cpos + len;
5274
5275         BUG_ON(cpos < le32_to_cpu(rec->e_cpos) || trunc_range > rec_range);
5276
5277         mlog(0, "Inode %llu, remove (cpos %u, len %u). Existing index %d "
5278              "(cpos %u, len %u)\n",
5279              (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos, len, index,
5280              le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec));
5281
5282         if (le32_to_cpu(rec->e_cpos) == cpos || rec_range == trunc_range) {
5283                 ret = ocfs2_truncate_rec(inode, handle, path, index, dealloc,
5284                                          cpos, len, et);
5285                 if (ret) {
5286                         mlog_errno(ret);
5287                         goto out;
5288                 }
5289         } else {
5290                 ret = ocfs2_split_tree(inode, et, handle, path, index,
5291                                        trunc_range, meta_ac);
5292                 if (ret) {
5293                         mlog_errno(ret);
5294                         goto out;
5295                 }
5296
5297                 /*
5298                  * The split could have manipulated the tree enough to
5299                  * move the record location, so we have to look for it again.
5300                  */
5301                 ocfs2_reinit_path(path, 1);
5302
5303                 ret = ocfs2_find_path(inode, path, cpos);
5304                 if (ret) {
5305                         mlog_errno(ret);
5306                         goto out;
5307                 }
5308
5309                 el = path_leaf_el(path);
5310                 index = ocfs2_search_extent_list(el, cpos);
5311                 if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
5312                         ocfs2_error(inode->i_sb,
5313                                     "Inode %llu: split at cpos %u lost record.",
5314                                     (unsigned long long)OCFS2_I(inode)->ip_blkno,
5315                                     cpos);
5316                         ret = -EROFS;
5317                         goto out;
5318                 }
5319
5320                 /*
5321                  * Double check our values here. If anything is fishy,
5322                  * it's easier to catch it at the top level.
5323                  */
5324                 rec = &el->l_recs[index];
5325                 rec_range = le32_to_cpu(rec->e_cpos) +
5326                         ocfs2_rec_clusters(el, rec);
5327                 if (rec_range != trunc_range) {
5328                         ocfs2_error(inode->i_sb,
5329                                     "Inode %llu: error after split at cpos %u"
5330                                     "trunc len %u, existing record is (%u,%u)",
5331                                     (unsigned long long)OCFS2_I(inode)->ip_blkno,
5332                                     cpos, len, le32_to_cpu(rec->e_cpos),
5333                                     ocfs2_rec_clusters(el, rec));
5334                         ret = -EROFS;
5335                         goto out;
5336                 }
5337
5338                 ret = ocfs2_truncate_rec(inode, handle, path, index, dealloc,
5339                                          cpos, len, et);
5340                 if (ret) {
5341                         mlog_errno(ret);
5342                         goto out;
5343                 }
5344         }
5345
5346 out:
5347         ocfs2_free_path(path);
5348         return ret;
5349 }
5350
5351 int ocfs2_remove_btree_range(struct inode *inode,
5352                              struct ocfs2_extent_tree *et,
5353                              u32 cpos, u32 phys_cpos, u32 len,
5354                              struct ocfs2_cached_dealloc_ctxt *dealloc)
5355 {
5356         int ret;
5357         u64 phys_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys_cpos);
5358         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
5359         struct inode *tl_inode = osb->osb_tl_inode;
5360         handle_t *handle;
5361         struct ocfs2_alloc_context *meta_ac = NULL;
5362
5363         ret = ocfs2_lock_allocators(inode, et, 0, 1, NULL, &meta_ac);
5364         if (ret) {
5365                 mlog_errno(ret);
5366                 return ret;
5367         }
5368
5369         mutex_lock(&tl_inode->i_mutex);
5370
5371         if (ocfs2_truncate_log_needs_flush(osb)) {
5372                 ret = __ocfs2_flush_truncate_log(osb);
5373                 if (ret < 0) {
5374                         mlog_errno(ret);
5375                         goto out;
5376                 }
5377         }
5378
5379         handle = ocfs2_start_trans(osb, ocfs2_remove_extent_credits(osb->sb));
5380         if (IS_ERR(handle)) {
5381                 ret = PTR_ERR(handle);
5382                 mlog_errno(ret);
5383                 goto out;
5384         }
5385
5386         ret = ocfs2_et_root_journal_access(handle, inode, et,
5387                                            OCFS2_JOURNAL_ACCESS_WRITE);
5388         if (ret) {
5389                 mlog_errno(ret);
5390                 goto out;
5391         }
5392
5393         ret = ocfs2_remove_extent(inode, et, cpos, len, handle, meta_ac,
5394                                   dealloc);
5395         if (ret) {
5396                 mlog_errno(ret);
5397                 goto out_commit;
5398         }
5399
5400         ocfs2_et_update_clusters(inode, et, -len);
5401
5402         ret = ocfs2_journal_dirty(handle, et->et_root_bh);
5403         if (ret) {
5404                 mlog_errno(ret);
5405                 goto out_commit;
5406         }
5407
5408         ret = ocfs2_truncate_log_append(osb, handle, phys_blkno, len);
5409         if (ret)
5410                 mlog_errno(ret);
5411
5412 out_commit:
5413         ocfs2_commit_trans(osb, handle);
5414 out:
5415         mutex_unlock(&tl_inode->i_mutex);
5416
5417         if (meta_ac)
5418                 ocfs2_free_alloc_context(meta_ac);
5419
5420         return ret;
5421 }
5422
5423 int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb)
5424 {
5425         struct buffer_head *tl_bh = osb->osb_tl_bh;
5426         struct ocfs2_dinode *di;
5427         struct ocfs2_truncate_log *tl;
5428
5429         di = (struct ocfs2_dinode *) tl_bh->b_data;
5430         tl = &di->id2.i_dealloc;
5431
5432         mlog_bug_on_msg(le16_to_cpu(tl->tl_used) > le16_to_cpu(tl->tl_count),
5433                         "slot %d, invalid truncate log parameters: used = "
5434                         "%u, count = %u\n", osb->slot_num,
5435                         le16_to_cpu(tl->tl_used), le16_to_cpu(tl->tl_count));
5436         return le16_to_cpu(tl->tl_used) == le16_to_cpu(tl->tl_count);
5437 }
5438
5439 static int ocfs2_truncate_log_can_coalesce(struct ocfs2_truncate_log *tl,
5440                                            unsigned int new_start)
5441 {
5442         unsigned int tail_index;
5443         unsigned int current_tail;
5444
5445         /* No records, nothing to coalesce */
5446         if (!le16_to_cpu(tl->tl_used))
5447                 return 0;
5448
5449         tail_index = le16_to_cpu(tl->tl_used) - 1;
5450         current_tail = le32_to_cpu(tl->tl_recs[tail_index].t_start);
5451         current_tail += le32_to_cpu(tl->tl_recs[tail_index].t_clusters);
5452
5453         return current_tail == new_start;
5454 }
5455
5456 int ocfs2_truncate_log_append(struct ocfs2_super *osb,
5457                               handle_t *handle,
5458                               u64 start_blk,
5459                               unsigned int num_clusters)
5460 {
5461         int status, index;
5462         unsigned int start_cluster, tl_count;
5463         struct inode *tl_inode = osb->osb_tl_inode;
5464         struct buffer_head *tl_bh = osb->osb_tl_bh;
5465         struct ocfs2_dinode *di;
5466         struct ocfs2_truncate_log *tl;
5467
5468         mlog_entry("start_blk = %llu, num_clusters = %u\n",
5469                    (unsigned long long)start_blk, num_clusters);
5470
5471         BUG_ON(mutex_trylock(&tl_inode->i_mutex));
5472
5473         start_cluster = ocfs2_blocks_to_clusters(osb->sb, start_blk);
5474
5475         di = (struct ocfs2_dinode *) tl_bh->b_data;
5476
5477         /* tl_bh is loaded from ocfs2_truncate_log_init().  It's validated
5478          * by the underlying call to ocfs2_read_inode_block(), so any
5479          * corruption is a code bug */
5480         BUG_ON(!OCFS2_IS_VALID_DINODE(di));
5481
5482         tl = &di->id2.i_dealloc;
5483         tl_count = le16_to_cpu(tl->tl_count);
5484         mlog_bug_on_msg(tl_count > ocfs2_truncate_recs_per_inode(osb->sb) ||
5485                         tl_count == 0,
5486                         "Truncate record count on #%llu invalid "
5487                         "wanted %u, actual %u\n",
5488                         (unsigned long long)OCFS2_I(tl_inode)->ip_blkno,
5489                         ocfs2_truncate_recs_per_inode(osb->sb),
5490                         le16_to_cpu(tl->tl_count));
5491
5492         /* Caller should have known to flush before calling us. */
5493         index = le16_to_cpu(tl->tl_used);
5494         if (index >= tl_count) {
5495                 status = -ENOSPC;
5496                 mlog_errno(status);
5497                 goto bail;
5498         }
5499
5500         status = ocfs2_journal_access_di(handle, tl_inode, tl_bh,
5501                                          OCFS2_JOURNAL_ACCESS_WRITE);
5502         if (status < 0) {
5503                 mlog_errno(status);
5504                 goto bail;
5505         }
5506
5507         mlog(0, "Log truncate of %u clusters starting at cluster %u to "
5508              "%llu (index = %d)\n", num_clusters, start_cluster,
5509              (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, index);
5510
5511         if (ocfs2_truncate_log_can_coalesce(tl, start_cluster)) {
5512                 /*
5513                  * Move index back to the record we are coalescing with.
5514                  * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5515                  */
5516                 index--;
5517
5518                 num_clusters += le32_to_cpu(tl->tl_recs[index].t_clusters);
5519                 mlog(0, "Coalesce with index %u (start = %u, clusters = %u)\n",
5520                      index, le32_to_cpu(tl->tl_recs[index].t_start),
5521                      num_clusters);
5522         } else {
5523                 tl->tl_recs[index].t_start = cpu_to_le32(start_cluster);
5524                 tl->tl_used = cpu_to_le16(index + 1);
5525         }
5526         tl->tl_recs[index].t_clusters = cpu_to_le32(num_clusters);
5527
5528         status = ocfs2_journal_dirty(handle, tl_bh);
5529         if (status < 0) {
5530                 mlog_errno(status);
5531                 goto bail;
5532         }
5533
5534 bail:
5535         mlog_exit(status);
5536         return status;
5537 }
5538
5539 static int ocfs2_replay_truncate_records(struct ocfs2_super *osb,
5540                                          handle_t *handle,
5541                                          struct inode *data_alloc_inode,
5542                                          struct buffer_head *data_alloc_bh)
5543 {
5544         int status = 0;
5545         int i;
5546         unsigned int num_clusters;
5547         u64 start_blk;
5548         struct ocfs2_truncate_rec rec;
5549         struct ocfs2_dinode *di;
5550         struct ocfs2_truncate_log *tl;
5551         struct inode *tl_inode = osb->osb_tl_inode;
5552         struct buffer_head *tl_bh = osb->osb_tl_bh;
5553
5554         mlog_entry_void();
5555
5556         di = (struct ocfs2_dinode *) tl_bh->b_data;
5557         tl = &di->id2.i_dealloc;
5558         i = le16_to_cpu(tl->tl_used) - 1;
5559         while (i >= 0) {
5560                 /* Caller has given us at least enough credits to
5561                  * update the truncate log dinode */
5562                 status = ocfs2_journal_access_di(handle, tl_inode, tl_bh,
5563                                                  OCFS2_JOURNAL_ACCESS_WRITE);
5564                 if (status < 0) {
5565                         mlog_errno(status);
5566                         goto bail;
5567                 }
5568
5569                 tl->tl_used = cpu_to_le16(i);
5570
5571                 status = ocfs2_journal_dirty(handle, tl_bh);
5572                 if (status < 0) {
5573                         mlog_errno(status);
5574                         goto bail;
5575                 }
5576
5577                 /* TODO: Perhaps we can calculate the bulk of the
5578                  * credits up front rather than extending like
5579                  * this. */
5580                 status = ocfs2_extend_trans(handle,
5581                                             OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5582                 if (status < 0) {
5583                         mlog_errno(status);
5584                         goto bail;
5585                 }
5586
5587                 rec = tl->tl_recs[i];
5588                 start_blk = ocfs2_clusters_to_blocks(data_alloc_inode->i_sb,
5589                                                     le32_to_cpu(rec.t_start));
5590                 num_clusters = le32_to_cpu(rec.t_clusters);
5591
5592                 /* if start_blk is not set, we ignore the record as
5593                  * invalid. */
5594                 if (start_blk) {
5595                         mlog(0, "free record %d, start = %u, clusters = %u\n",
5596                              i, le32_to_cpu(rec.t_start), num_clusters);
5597
5598                         status = ocfs2_free_clusters(handle, data_alloc_inode,
5599                                                      data_alloc_bh, start_blk,
5600                                                      num_clusters);
5601                         if (status < 0) {
5602                                 mlog_errno(status);
5603                                 goto bail;
5604                         }
5605                 }
5606                 i--;
5607         }
5608
5609 bail:
5610         mlog_exit(status);
5611         return status;
5612 }
5613
5614 /* Expects you to already be holding tl_inode->i_mutex */
5615 int __ocfs2_flush_truncate_log(struct ocfs2_super *osb)
5616 {
5617         int status;
5618         unsigned int num_to_flush;
5619         handle_t *handle;
5620         struct inode *tl_inode = osb->osb_tl_inode;
5621         struct inode *data_alloc_inode = NULL;
5622         struct buffer_head *tl_bh = osb->osb_tl_bh;
5623         struct buffer_head *data_alloc_bh = NULL;
5624         struct ocfs2_dinode *di;
5625         struct ocfs2_truncate_log *tl;
5626
5627         mlog_entry_void();
5628
5629         BUG_ON(mutex_trylock(&tl_inode->i_mutex));
5630
5631         di = (struct ocfs2_dinode *) tl_bh->b_data;
5632
5633         /* tl_bh is loaded from ocfs2_truncate_log_init().  It's validated
5634          * by the underlying call to ocfs2_read_inode_block(), so any
5635          * corruption is a code bug */
5636         BUG_ON(!OCFS2_IS_VALID_DINODE(di));
5637
5638         tl = &di->id2.i_dealloc;
5639         num_to_flush = le16_to_cpu(tl->tl_used);
5640         mlog(0, "Flush %u records from truncate log #%llu\n",
5641              num_to_flush, (unsigned long long)OCFS2_I(tl_inode)->ip_blkno);
5642         if (!num_to_flush) {
5643                 status = 0;
5644                 goto out;
5645         }
5646
5647         data_alloc_inode = ocfs2_get_system_file_inode(osb,
5648                                                        GLOBAL_BITMAP_SYSTEM_INODE,
5649                                                        OCFS2_INVALID_SLOT);
5650         if (!data_alloc_inode) {
5651                 status = -EINVAL;
5652                 mlog(ML_ERROR, "Could not get bitmap inode!\n");
5653                 goto out;
5654         }
5655
5656         mutex_lock(&data_alloc_inode->i_mutex);
5657
5658         status = ocfs2_inode_lock(data_alloc_inode, &data_alloc_bh, 1);
5659         if (status < 0) {
5660                 mlog_errno(status);
5661                 goto out_mutex;
5662         }
5663
5664         handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
5665         if (IS_ERR(handle)) {
5666                 status = PTR_ERR(handle);
5667                 mlog_errno(status);
5668                 goto out_unlock;
5669         }
5670
5671         status = ocfs2_replay_truncate_records(osb, handle, data_alloc_inode,
5672                                                data_alloc_bh);
5673         if (status < 0)
5674                 mlog_errno(status);
5675
5676         ocfs2_commit_trans(osb, handle);
5677
5678 out_unlock:
5679         brelse(data_alloc_bh);
5680         ocfs2_inode_unlock(data_alloc_inode, 1);
5681
5682 out_mutex:
5683         mutex_unlock(&data_alloc_inode->i_mutex);
5684         iput(data_alloc_inode);
5685
5686 out:
5687         mlog_exit(status);
5688         return status;
5689 }
5690
5691 int ocfs2_flush_truncate_log(struct ocfs2_super *osb)
5692 {
5693         int status;
5694         struct inode *tl_inode = osb->osb_tl_inode;
5695
5696         mutex_lock(&tl_inode->i_mutex);
5697         status = __ocfs2_flush_truncate_log(osb);
5698         mutex_unlock(&tl_inode->i_mutex);
5699
5700         return status;
5701 }
5702
5703 static void ocfs2_truncate_log_worker(struct work_struct *work)
5704 {
5705         int status;
5706         struct ocfs2_super *osb =
5707                 container_of(work, struct ocfs2_super,
5708                              osb_truncate_log_wq.work);
5709
5710         mlog_entry_void();
5711
5712         status = ocfs2_flush_truncate_log(osb);
5713         if (status < 0)
5714                 mlog_errno(status);
5715         else
5716                 ocfs2_init_inode_steal_slot(osb);
5717
5718         mlog_exit(status);
5719 }
5720
5721 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
5722 void ocfs2_schedule_truncate_log_flush(struct ocfs2_super *osb,
5723                                        int cancel)
5724 {
5725         if (osb->osb_tl_inode) {
5726                 /* We want to push off log flushes while truncates are
5727                  * still running. */
5728                 if (cancel)
5729                         cancel_delayed_work(&osb->osb_truncate_log_wq);
5730
5731                 queue_delayed_work(ocfs2_wq, &osb->osb_truncate_log_wq,
5732                                    OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
5733         }
5734 }
5735
5736 static int ocfs2_get_truncate_log_info(struct ocfs2_super *osb,
5737                                        int slot_num,
5738                                        struct inode **tl_inode,
5739                                        struct buffer_head **tl_bh)
5740 {
5741         int status;
5742         struct inode *inode = NULL;
5743         struct buffer_head *bh = NULL;
5744
5745         inode = ocfs2_get_system_file_inode(osb,
5746                                            TRUNCATE_LOG_SYSTEM_INODE,
5747                                            slot_num);
5748         if (!inode) {
5749                 status = -EINVAL;
5750                 mlog(ML_ERROR, "Could not get load truncate log inode!\n");
5751                 goto bail;
5752         }
5753
5754         status = ocfs2_read_inode_block(inode, &bh);
5755         if (status < 0) {
5756                 iput(inode);
5757                 mlog_errno(status);
5758                 goto bail;
5759         }
5760
5761         *tl_inode = inode;
5762         *tl_bh    = bh;
5763 bail:
5764         mlog_exit(status);
5765         return status;
5766 }
5767
5768 /* called during the 1st stage of node recovery. we stamp a clean
5769  * truncate log and pass back a copy for processing later. if the
5770  * truncate log does not require processing, a *tl_copy is set to
5771  * NULL. */
5772 int ocfs2_begin_truncate_log_recovery(struct ocfs2_super *osb,
5773                                       int slot_num,
5774                                       struct ocfs2_dinode **tl_copy)
5775 {
5776         int status;
5777         struct inode *tl_inode = NULL;
5778         struct buffer_head *tl_bh = NULL;
5779         struct ocfs2_dinode *di;
5780         struct ocfs2_truncate_log *tl;
5781
5782         *tl_copy = NULL;
5783
5784         mlog(0, "recover truncate log from slot %d\n", slot_num);
5785
5786         status = ocfs2_get_truncate_log_info(osb, slot_num, &tl_inode, &tl_bh);
5787         if (status < 0) {
5788                 mlog_errno(status);
5789                 goto bail;
5790         }
5791
5792         di = (struct ocfs2_dinode *) tl_bh->b_data;
5793
5794         /* tl_bh is loaded from ocfs2_get_truncate_log_info().  It's
5795          * validated by the underlying call to ocfs2_read_inode_block(),
5796          * so any corruption is a code bug */
5797         BUG_ON(!OCFS2_IS_VALID_DINODE(di));
5798
5799         tl = &di->id2.i_dealloc;
5800         if (le16_to_cpu(tl->tl_used)) {
5801                 mlog(0, "We'll have %u logs to recover\n",
5802                      le16_to_cpu(tl->tl_used));
5803
5804                 *tl_copy = kmalloc(tl_bh->b_size, GFP_KERNEL);
5805                 if (!(*tl_copy)) {
5806                         status = -ENOMEM;
5807                         mlog_errno(status);
5808                         goto bail;
5809                 }
5810
5811                 /* Assuming the write-out below goes well, this copy
5812                  * will be passed back to recovery for processing. */
5813                 memcpy(*tl_copy, tl_bh->b_data, tl_bh->b_size);
5814
5815                 /* All we need to do to clear the truncate log is set
5816                  * tl_used. */
5817                 tl->tl_used = 0;
5818
5819                 ocfs2_compute_meta_ecc(osb->sb, tl_bh->b_data, &di->i_check);
5820                 status = ocfs2_write_block(osb, tl_bh, tl_inode);
5821                 if (status < 0) {
5822                         mlog_errno(status);
5823                         goto bail;
5824                 }
5825         }
5826
5827 bail:
5828         if (tl_inode)
5829                 iput(tl_inode);
5830         brelse(tl_bh);
5831
5832         if (status < 0 && (*tl_copy)) {
5833                 kfree(*tl_copy);
5834                 *tl_copy = NULL;
5835         }
5836
5837         mlog_exit(status);
5838         return status;
5839 }
5840
5841 int ocfs2_complete_truncate_log_recovery(struct ocfs2_super *osb,
5842                                          struct ocfs2_dinode *tl_copy)
5843 {
5844         int status = 0;
5845         int i;
5846         unsigned int clusters, num_recs, start_cluster;
5847         u64 start_blk;
5848         handle_t *handle;
5849         struct inode *tl_inode = osb->osb_tl_inode;
5850         struct ocfs2_truncate_log *tl;
5851
5852         mlog_entry_void();
5853
5854         if (OCFS2_I(tl_inode)->ip_blkno == le64_to_cpu(tl_copy->i_blkno)) {
5855                 mlog(ML_ERROR, "Asked to recover my own truncate log!\n");
5856                 return -EINVAL;
5857         }
5858
5859         tl = &tl_copy->id2.i_dealloc;
5860         num_recs = le16_to_cpu(tl->tl_used);
5861         mlog(0, "cleanup %u records from %llu\n", num_recs,
5862              (unsigned long long)le64_to_cpu(tl_copy->i_blkno));
5863
5864         mutex_lock(&tl_inode->i_mutex);
5865         for(i = 0; i < num_recs; i++) {
5866                 if (ocfs2_truncate_log_needs_flush(osb)) {
5867                         status = __ocfs2_flush_truncate_log(osb);
5868                         if (status < 0) {
5869                                 mlog_errno(status);
5870                                 goto bail_up;
5871                         }
5872                 }
5873
5874                 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
5875                 if (IS_ERR(handle)) {
5876                         status = PTR_ERR(handle);
5877                         mlog_errno(status);
5878                         goto bail_up;
5879                 }
5880
5881                 clusters = le32_to_cpu(tl->tl_recs[i].t_clusters);
5882                 start_cluster = le32_to_cpu(tl->tl_recs[i].t_start);
5883                 start_blk = ocfs2_clusters_to_blocks(osb->sb, start_cluster);
5884
5885                 status = ocfs2_truncate_log_append(osb, handle,
5886                                                    start_blk, clusters);
5887                 ocfs2_commit_trans(osb, handle);
5888                 if (status < 0) {
5889                         mlog_errno(status);
5890                         goto bail_up;
5891                 }
5892         }
5893
5894 bail_up:
5895         mutex_unlock(&tl_inode->i_mutex);
5896
5897         mlog_exit(status);
5898         return status;
5899 }
5900
5901 void ocfs2_truncate_log_shutdown(struct ocfs2_super *osb)
5902 {
5903         int status;
5904         struct inode *tl_inode = osb->osb_tl_inode;
5905
5906         mlog_entry_void();
5907
5908         if (tl_inode) {
5909                 cancel_delayed_work(&osb->osb_truncate_log_wq);
5910                 flush_workqueue(ocfs2_wq);
5911
5912                 status = ocfs2_flush_truncate_log(osb);
5913                 if (status < 0)
5914                         mlog_errno(status);
5915
5916                 brelse(osb->osb_tl_bh);
5917                 iput(osb->osb_tl_inode);
5918         }
5919
5920         mlog_exit_void();
5921 }
5922
5923 int ocfs2_truncate_log_init(struct ocfs2_super *osb)
5924 {
5925         int status;
5926         struct inode *tl_inode = NULL;
5927         struct buffer_head *tl_bh = NULL;
5928
5929         mlog_entry_void();
5930
5931         status = ocfs2_get_truncate_log_info(osb,
5932                                              osb->slot_num,
5933                                              &tl_inode,
5934                                              &tl_bh);
5935         if (status < 0)
5936                 mlog_errno(status);
5937
5938         /* ocfs2_truncate_log_shutdown keys on the existence of
5939          * osb->osb_tl_inode so we don't set any of the osb variables
5940          * until we're sure all is well. */
5941         INIT_DELAYED_WORK(&osb->osb_truncate_log_wq,
5942                           ocfs2_truncate_log_worker);
5943         osb->osb_tl_bh    = tl_bh;
5944         osb->osb_tl_inode = tl_inode;
5945
5946         mlog_exit(status);
5947         return status;
5948 }
5949
5950 /*
5951  * Delayed de-allocation of suballocator blocks.
5952  *
5953  * Some sets of block de-allocations might involve multiple suballocator inodes.
5954  *
5955  * The locking for this can get extremely complicated, especially when
5956  * the suballocator inodes to delete from aren't known until deep
5957  * within an unrelated codepath.
5958  *
5959  * ocfs2_extent_block structures are a good example of this - an inode
5960  * btree could have been grown by any number of nodes each allocating
5961  * out of their own suballoc inode.
5962  *
5963  * These structures allow the delay of block de-allocation until a
5964  * later time, when locking of multiple cluster inodes won't cause
5965  * deadlock.
5966  */
5967
5968 /*
5969  * Describe a single bit freed from a suballocator.  For the block
5970  * suballocators, it represents one block.  For the global cluster
5971  * allocator, it represents some clusters and free_bit indicates
5972  * clusters number.
5973  */
5974 struct ocfs2_cached_block_free {
5975         struct ocfs2_cached_block_free          *free_next;
5976         u64                                     free_blk;
5977         unsigned int                            free_bit;
5978 };
5979
5980 struct ocfs2_per_slot_free_list {
5981         struct ocfs2_per_slot_free_list         *f_next_suballocator;
5982         int                                     f_inode_type;
5983         int                                     f_slot;
5984         struct ocfs2_cached_block_free          *f_first;
5985 };
5986
5987 static int ocfs2_free_cached_blocks(struct ocfs2_super *osb,
5988                                     int sysfile_type,
5989                                     int slot,
5990                                     struct ocfs2_cached_block_free *head)
5991 {
5992         int ret;
5993         u64 bg_blkno;
5994         handle_t *handle;
5995         struct inode *inode;
5996         struct buffer_head *di_bh = NULL;
5997         struct ocfs2_cached_block_free *tmp;
5998
5999         inode = ocfs2_get_system_file_inode(osb, sysfile_type, slot);
6000         if (!inode) {
6001                 ret = -EINVAL;
6002                 mlog_errno(ret);
6003                 goto out;
6004         }
6005
6006         mutex_lock(&inode->i_mutex);
6007
6008         ret = ocfs2_inode_lock(inode, &di_bh, 1);
6009         if (ret) {
6010                 mlog_errno(ret);
6011                 goto out_mutex;
6012         }
6013
6014         handle = ocfs2_start_trans(osb, OCFS2_SUBALLOC_FREE);
6015         if (IS_ERR(handle)) {
6016                 ret = PTR_ERR(handle);
6017                 mlog_errno(ret);
6018                 goto out_unlock;
6019         }
6020
6021         while (head) {
6022                 bg_blkno = ocfs2_which_suballoc_group(head->free_blk,
6023                                                       head->free_bit);
6024                 mlog(0, "Free bit: (bit %u, blkno %llu)\n",
6025                      head->free_bit, (unsigned long long)head->free_blk);
6026
6027                 ret = ocfs2_free_suballoc_bits(handle, inode, di_bh,
6028                                                head->free_bit, bg_blkno, 1);
6029                 if (ret) {
6030                         mlog_errno(ret);
6031                         goto out_journal;
6032                 }
6033
6034                 ret = ocfs2_extend_trans(handle, OCFS2_SUBALLOC_FREE);
6035                 if (ret) {
6036                         mlog_errno(ret);
6037                         goto out_journal;
6038                 }
6039
6040                 tmp = head;
6041                 head = head->free_next;
6042                 kfree(tmp);
6043         }
6044
6045 out_journal:
6046         ocfs2_commit_trans(osb, handle);
6047
6048 out_unlock:
6049         ocfs2_inode_unlock(inode, 1);
6050         brelse(di_bh);
6051 out_mutex:
6052         mutex_unlock(&inode->i_mutex);
6053         iput(inode);
6054 out:
6055         while(head) {
6056                 /* Premature exit may have left some dangling items. */
6057                 tmp = head;
6058                 head = head->free_next;
6059                 kfree(tmp);
6060         }
6061
6062         return ret;
6063 }
6064
6065 int ocfs2_cache_cluster_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt,
6066                                 u64 blkno, unsigned int bit)
6067 {
6068         int ret = 0;
6069         struct ocfs2_cached_block_free *item;
6070
6071         item = kmalloc(sizeof(*item), GFP_NOFS);
6072         if (item == NULL) {
6073                 ret = -ENOMEM;
6074                 mlog_errno(ret);
6075                 return ret;
6076         }
6077
6078         mlog(0, "Insert clusters: (bit %u, blk %llu)\n",
6079              bit, (unsigned long long)blkno);
6080
6081         item->free_blk = blkno;
6082         item->free_bit = bit;
6083         item->free_next = ctxt->c_global_allocator;
6084
6085         ctxt->c_global_allocator = item;
6086         return ret;
6087 }
6088
6089 static int ocfs2_free_cached_clusters(struct ocfs2_super *osb,
6090                                       struct ocfs2_cached_block_free *head)
6091 {
6092         struct ocfs2_cached_block_free *tmp;
6093         struct inode *tl_inode = osb->osb_tl_inode;
6094         handle_t *handle;
6095         int ret = 0;
6096
6097         mutex_lock(&tl_inode->i_mutex);
6098
6099         while (head) {
6100                 if (ocfs2_truncate_log_needs_flush(osb)) {
6101                         ret = __ocfs2_flush_truncate_log(osb);
6102                         if (ret < 0) {
6103                                 mlog_errno(ret);
6104                                 break;
6105                         }
6106                 }
6107
6108                 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
6109                 if (IS_ERR(handle)) {
6110                         ret = PTR_ERR(handle);
6111                         mlog_errno(ret);
6112                         break;
6113                 }
6114
6115                 ret = ocfs2_truncate_log_append(osb, handle, head->free_blk,
6116                                                 head->free_bit);
6117
6118                 ocfs2_commit_trans(osb, handle);
6119                 tmp = head;
6120                 head = head->free_next;
6121                 kfree(tmp);
6122
6123                 if (ret < 0) {
6124                         mlog_errno(ret);
6125                         break;
6126                 }
6127         }
6128
6129         mutex_unlock(&tl_inode->i_mutex);
6130
6131         while (head) {
6132                 /* Premature exit may have left some dangling items. */
6133                 tmp = head;
6134                 head = head->free_next;
6135                 kfree(tmp);
6136         }
6137
6138         return ret;
6139 }
6140
6141 int ocfs2_run_deallocs(struct ocfs2_super *osb,
6142                        struct ocfs2_cached_dealloc_ctxt *ctxt)
6143 {
6144         int ret = 0, ret2;
6145         struct ocfs2_per_slot_free_list *fl;
6146
6147         if (!ctxt)
6148                 return 0;
6149
6150         while (ctxt->c_first_suballocator) {
6151                 fl = ctxt->c_first_suballocator;
6152
6153                 if (fl->f_first) {
6154                         mlog(0, "Free items: (type %u, slot %d)\n",
6155                              fl->f_inode_type, fl->f_slot);
6156                         ret2 = ocfs2_free_cached_blocks(osb,
6157                                                         fl->f_inode_type,
6158                                                         fl->f_slot,
6159                                                         fl->f_first);
6160                         if (ret2)
6161                                 mlog_errno(ret2);
6162                         if (!ret)
6163                                 ret = ret2;
6164                 }
6165
6166                 ctxt->c_first_suballocator = fl->f_next_suballocator;
6167                 kfree(fl);
6168         }
6169
6170         if (ctxt->c_global_allocator) {
6171                 ret2 = ocfs2_free_cached_clusters(osb,
6172                                                   ctxt->c_global_allocator);
6173                 if (ret2)
6174                         mlog_errno(ret2);
6175                 if (!ret)
6176                         ret = ret2;
6177
6178                 ctxt->c_global_allocator = NULL;
6179         }
6180
6181         return ret;
6182 }
6183
6184 static struct ocfs2_per_slot_free_list *
6185 ocfs2_find_per_slot_free_list(int type,
6186                               int slot,
6187                               struct ocfs2_cached_dealloc_ctxt *ctxt)
6188 {
6189         struct ocfs2_per_slot_free_list *fl = ctxt->c_first_suballocator;
6190
6191         while (fl) {
6192                 if (fl->f_inode_type == type && fl->f_slot == slot)
6193                         return fl;
6194
6195                 fl = fl->f_next_suballocator;
6196         }
6197
6198         fl = kmalloc(sizeof(*fl), GFP_NOFS);
6199         if (fl) {
6200                 fl->f_inode_type = type;
6201                 fl->f_slot = slot;
6202                 fl->f_first = NULL;
6203                 fl->f_next_suballocator = ctxt->c_first_suballocator;
6204
6205                 ctxt->c_first_suballocator = fl;
6206         }
6207         return fl;
6208 }
6209
6210 static int ocfs2_cache_block_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt,
6211                                      int type, int slot, u64 blkno,
6212                                      unsigned int bit)
6213 {
6214         int ret;
6215         struct ocfs2_per_slot_free_list *fl;
6216         struct ocfs2_cached_block_free *item;
6217
6218         fl = ocfs2_find_per_slot_free_list(type, slot, ctxt);
6219         if (fl == NULL) {
6220                 ret = -ENOMEM;
6221                 mlog_errno(ret);
6222                 goto out;
6223         }
6224
6225         item = kmalloc(sizeof(*item), GFP_NOFS);
6226         if (item == NULL) {
6227                 ret = -ENOMEM;
6228                 mlog_errno(ret);
6229                 goto out;
6230         }
6231
6232         mlog(0, "Insert: (type %d, slot %u, bit %u, blk %llu)\n",
6233              type, slot, bit, (unsigned long long)blkno);
6234
6235         item->free_blk = blkno;
6236         item->free_bit = bit;
6237         item->free_next = fl->f_first;
6238
6239         fl->f_first = item;
6240
6241         ret = 0;
6242 out:
6243         return ret;
6244 }
6245
6246 static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt,
6247                                          struct ocfs2_extent_block *eb)
6248 {
6249         return ocfs2_cache_block_dealloc(ctxt, EXTENT_ALLOC_SYSTEM_INODE,
6250                                          le16_to_cpu(eb->h_suballoc_slot),
6251                                          le64_to_cpu(eb->h_blkno),
6252                                          le16_to_cpu(eb->h_suballoc_bit));
6253 }
6254
6255 /* This function will figure out whether the currently last extent
6256  * block will be deleted, and if it will, what the new last extent
6257  * block will be so we can update his h_next_leaf_blk field, as well
6258  * as the dinodes i_last_eb_blk */
6259 static int ocfs2_find_new_last_ext_blk(struct inode *inode,
6260                                        unsigned int clusters_to_del,
6261                                        struct ocfs2_path *path,
6262                                        struct buffer_head **new_last_eb)
6263 {
6264         int next_free, ret = 0;
6265         u32 cpos;
6266         struct ocfs2_extent_rec *rec;
6267         struct ocfs2_extent_block *eb;
6268         struct ocfs2_extent_list *el;
6269         struct buffer_head *bh = NULL;
6270
6271         *new_last_eb = NULL;
6272
6273         /* we have no tree, so of course, no last_eb. */
6274         if (!path->p_tree_depth)
6275                 goto out;
6276
6277         /* trunc to zero special case - this makes tree_depth = 0
6278          * regardless of what it is.  */
6279         if (OCFS2_I(inode)->ip_clusters == clusters_to_del)
6280                 goto out;
6281
6282         el = path_leaf_el(path);
6283         BUG_ON(!el->l_next_free_rec);
6284
6285         /*
6286          * Make sure that this extent list will actually be empty
6287          * after we clear away the data. We can shortcut out if
6288          * there's more than one non-empty extent in the
6289          * list. Otherwise, a check of the remaining extent is
6290          * necessary.
6291          */
6292         next_free = le16_to_cpu(el->l_next_free_rec);
6293         rec = NULL;
6294         if (ocfs2_is_empty_extent(&el->l_recs[0])) {
6295                 if (next_free > 2)
6296                         goto out;
6297
6298                 /* We may have a valid extent in index 1, check it. */
6299                 if (next_free == 2)
6300                         rec = &el->l_recs[1];
6301
6302                 /*
6303                  * Fall through - no more nonempty extents, so we want
6304                  * to delete this leaf.
6305                  */
6306         } else {
6307                 if (next_free > 1)
6308                         goto out;
6309
6310                 rec = &el->l_recs[0];
6311         }
6312
6313         if (rec) {
6314                 /*
6315                  * Check it we'll only be trimming off the end of this
6316                  * cluster.
6317                  */
6318                 if (le16_to_cpu(rec->e_leaf_clusters) > clusters_to_del)
6319                         goto out;
6320         }
6321
6322         ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos);
6323         if (ret) {
6324                 mlog_errno(ret);
6325                 goto out;
6326         }
6327
6328         ret = ocfs2_find_leaf(inode, path_root_el(path), cpos, &bh);
6329         if (ret) {
6330                 mlog_errno(ret);
6331                 goto out;
6332         }
6333
6334         eb = (struct ocfs2_extent_block *) bh->b_data;
6335         el = &eb->h_list;
6336
6337         /* ocfs2_find_leaf() gets the eb from ocfs2_read_extent_block().
6338          * Any corruption is a code bug. */
6339         BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb));
6340
6341         *new_last_eb = bh;
6342         get_bh(*new_last_eb);
6343         mlog(0, "returning block %llu, (cpos: %u)\n",
6344              (unsigned long long)le64_to_cpu(eb->h_blkno), cpos);
6345 out:
6346         brelse(bh);
6347
6348         return ret;
6349 }
6350
6351 /*
6352  * Trim some clusters off the rightmost edge of a tree. Only called
6353  * during truncate.
6354  *
6355  * The caller needs to:
6356  *   - start journaling of each path component.
6357  *   - compute and fully set up any new last ext block
6358  */
6359 static int ocfs2_trim_tree(struct inode *inode, struct ocfs2_path *path,
6360                            handle_t *handle, struct ocfs2_truncate_context *tc,
6361                            u32 clusters_to_del, u64 *delete_start)
6362 {
6363         int ret, i, index = path->p_tree_depth;
6364         u32 new_edge = 0;
6365         u64 deleted_eb = 0;
6366         struct buffer_head *bh;
6367         struct ocfs2_extent_list *el;
6368         struct ocfs2_extent_rec *rec;
6369
6370         *delete_start = 0;
6371
6372         while (index >= 0) {
6373                 bh = path->p_node[index].bh;
6374                 el = path->p_node[index].el;
6375
6376                 mlog(0, "traveling tree (index = %d, block = %llu)\n",
6377                      index,  (unsigned long long)bh->b_blocknr);
6378
6379                 BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0);
6380
6381                 if (index !=
6382                     (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) {
6383                         ocfs2_error(inode->i_sb,
6384                                     "Inode %lu has invalid ext. block %llu",
6385                                     inode->i_ino,
6386                                     (unsigned long long)bh->b_blocknr);
6387                         ret = -EROFS;
6388                         goto out;
6389                 }
6390
6391 find_tail_record:
6392                 i = le16_to_cpu(el->l_next_free_rec) - 1;
6393                 rec = &el->l_recs[i];
6394
6395                 mlog(0, "Extent list before: record %d: (%u, %u, %llu), "
6396                      "next = %u\n", i, le32_to_cpu(rec->e_cpos),
6397                      ocfs2_rec_clusters(el, rec),
6398                      (unsigned long long)le64_to_cpu(rec->e_blkno),
6399                      le16_to_cpu(el->l_next_free_rec));
6400
6401                 BUG_ON(ocfs2_rec_clusters(el, rec) < clusters_to_del);
6402
6403                 if (le16_to_cpu(el->l_tree_depth) == 0) {
6404                         /*
6405                          * If the leaf block contains a single empty
6406                          * extent and no records, we can just remove
6407                          * the block.
6408                          */
6409                         if (i == 0 && ocfs2_is_empty_extent(rec)) {
6410                                 memset(rec, 0,
6411                                        sizeof(struct ocfs2_extent_rec));
6412                                 el->l_next_free_rec = cpu_to_le16(0);
6413
6414                                 goto delete;
6415                         }
6416
6417                         /*
6418                          * Remove any empty extents by shifting things
6419                          * left. That should make life much easier on
6420                          * the code below. This condition is rare
6421                          * enough that we shouldn't see a performance
6422                          * hit.
6423                          */
6424                         if (ocfs2_is_empty_extent(&el->l_recs[0])) {
6425                                 le16_add_cpu(&el->l_next_free_rec, -1);
6426
6427                                 for(i = 0;
6428                                     i < le16_to_cpu(el->l_next_free_rec); i++)
6429                                         el->l_recs[i] = el->l_recs[i + 1];
6430
6431                                 memset(&el->l_recs[i], 0,
6432                                        sizeof(struct ocfs2_extent_rec));
6433
6434                                 /*
6435                                  * We've modified our extent list. The
6436                                  * simplest way to handle this change
6437                                  * is to being the search from the
6438                                  * start again.
6439                                  */
6440                                 goto find_tail_record;
6441                         }
6442
6443                         le16_add_cpu(&rec->e_leaf_clusters, -clusters_to_del);
6444
6445                         /*
6446                          * We'll use "new_edge" on our way back up the
6447                          * tree to know what our rightmost cpos is.
6448                          */
6449                         new_edge = le16_to_cpu(rec->e_leaf_clusters);
6450                         new_edge += le32_to_cpu(rec->e_cpos);
6451
6452                         /*
6453                          * The caller will use this to delete data blocks.
6454                          */
6455                         *delete_start = le64_to_cpu(rec->e_blkno)
6456                                 + ocfs2_clusters_to_blocks(inode->i_sb,
6457                                         le16_to_cpu(rec->e_leaf_clusters));
6458
6459                         /*
6460                          * If it's now empty, remove this record.
6461                          */
6462                         if (le16_to_cpu(rec->e_leaf_clusters) == 0) {
6463                                 memset(rec, 0,
6464                                        sizeof(struct ocfs2_extent_rec));
6465                                 le16_add_cpu(&el->l_next_free_rec, -1);
6466                         }
6467                 } else {
6468                         if (le64_to_cpu(rec->e_blkno) == deleted_eb) {
6469                                 memset(rec, 0,
6470                                        sizeof(struct ocfs2_extent_rec));
6471                                 le16_add_cpu(&el->l_next_free_rec, -1);
6472
6473                                 goto delete;
6474                         }
6475
6476                         /* Can this actually happen? */
6477                         if (le16_to_cpu(el->l_next_free_rec) == 0)
6478                                 goto delete;
6479
6480                         /*
6481                          * We never actually deleted any clusters
6482                          * because our leaf was empty. There's no
6483                          * reason to adjust the rightmost edge then.
6484                          */
6485                         if (new_edge == 0)
6486                                 goto delete;
6487
6488                         rec->e_int_clusters = cpu_to_le32(new_edge);
6489                         le32_add_cpu(&rec->e_int_clusters,
6490                                      -le32_to_cpu(rec->e_cpos));
6491
6492                          /*
6493                           * A deleted child record should have been
6494                           * caught above.
6495                           */
6496                          BUG_ON(le32_to_cpu(rec->e_int_clusters) == 0);
6497                 }
6498
6499 delete:
6500                 ret = ocfs2_journal_dirty(handle, bh);
6501                 if (ret) {
6502                         mlog_errno(ret);
6503                         goto out;
6504                 }
6505
6506                 mlog(0, "extent list container %llu, after: record %d: "
6507                      "(%u, %u, %llu), next = %u.\n",
6508                      (unsigned long long)bh->b_blocknr, i,
6509                      le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec),
6510                      (unsigned long long)le64_to_cpu(rec->e_blkno),
6511                      le16_to_cpu(el->l_next_free_rec));
6512
6513                 /*
6514                  * We must be careful to only attempt delete of an
6515                  * extent block (and not the root inode block).
6516                  */
6517                 if (index > 0 && le16_to_cpu(el->l_next_free_rec) == 0) {
6518                         struct ocfs2_extent_block *eb =
6519                                 (struct ocfs2_extent_block *)bh->b_data;
6520
6521                         /*
6522                          * Save this for use when processing the
6523                          * parent block.
6524                          */
6525                         deleted_eb = le64_to_cpu(eb->h_blkno);
6526
6527                         mlog(0, "deleting this extent block.\n");
6528
6529                         ocfs2_remove_from_cache(inode, bh);
6530
6531                         BUG_ON(ocfs2_rec_clusters(el, &el->l_recs[0]));
6532                         BUG_ON(le32_to_cpu(el->l_recs[0].e_cpos));
6533                         BUG_ON(le64_to_cpu(el->l_recs[0].e_blkno));
6534
6535                         ret = ocfs2_cache_extent_block_free(&tc->tc_dealloc, eb);
6536                         /* An error here is not fatal. */
6537                         if (ret < 0)
6538                                 mlog_errno(ret);
6539                 } else {
6540                         deleted_eb = 0;
6541                 }
6542
6543                 index--;
6544         }
6545
6546         ret = 0;
6547 out:
6548         return ret;
6549 }
6550
6551 static int ocfs2_do_truncate(struct ocfs2_super *osb,
6552                              unsigned int clusters_to_del,
6553                              struct inode *inode,
6554                              struct buffer_head *fe_bh,
6555                              handle_t *handle,
6556                              struct ocfs2_truncate_context *tc,
6557                              struct ocfs2_path *path)
6558 {
6559         int status;
6560         struct ocfs2_dinode *fe;
6561         struct ocfs2_extent_block *last_eb = NULL;
6562         struct ocfs2_extent_list *el;
6563         struct buffer_head *last_eb_bh = NULL;
6564         u64 delete_blk = 0;
6565
6566         fe = (struct ocfs2_dinode *) fe_bh->b_data;
6567
6568         status = ocfs2_find_new_last_ext_blk(inode, clusters_to_del,
6569                                              path, &last_eb_bh);
6570         if (status < 0) {
6571                 mlog_errno(status);
6572                 goto bail;
6573         }
6574
6575         /*
6576          * Each component will be touched, so we might as well journal
6577          * here to avoid having to handle errors later.
6578          */
6579         status = ocfs2_journal_access_path(inode, handle, path);
6580         if (status < 0) {
6581                 mlog_errno(status);
6582                 goto bail;
6583         }
6584
6585         if (last_eb_bh) {
6586                 status = ocfs2_journal_access_eb(handle, inode, last_eb_bh,
6587                                                  OCFS2_JOURNAL_ACCESS_WRITE);
6588                 if (status < 0) {
6589                         mlog_errno(status);
6590                         goto bail;
6591                 }
6592
6593                 last_eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
6594         }
6595
6596         el = &(fe->id2.i_list);
6597
6598         /*
6599          * Lower levels depend on this never happening, but it's best
6600          * to check it up here before changing the tree.
6601          */
6602         if (el->l_tree_depth && el->l_recs[0].e_int_clusters == 0) {
6603                 ocfs2_error(inode->i_sb,
6604                             "Inode %lu has an empty extent record, depth %u\n",
6605                             inode->i_ino, le16_to_cpu(el->l_tree_depth));
6606                 status = -EROFS;
6607                 goto bail;
6608         }
6609
6610         vfs_dq_free_space_nodirty(inode,
6611                         ocfs2_clusters_to_bytes(osb->sb, clusters_to_del));
6612         spin_lock(&OCFS2_I(inode)->ip_lock);
6613         OCFS2_I(inode)->ip_clusters = le32_to_cpu(fe->i_clusters) -
6614                                       clusters_to_del;
6615         spin_unlock(&OCFS2_I(inode)->ip_lock);
6616         le32_add_cpu(&fe->i_clusters, -clusters_to_del);
6617         inode->i_blocks = ocfs2_inode_sector_count(inode);
6618
6619         status = ocfs2_trim_tree(inode, path, handle, tc,
6620                                  clusters_to_del, &delete_blk);
6621         if (status) {
6622                 mlog_errno(status);
6623                 goto bail;
6624         }
6625
6626         if (le32_to_cpu(fe->i_clusters) == 0) {
6627                 /* trunc to zero is a special case. */
6628                 el->l_tree_depth = 0;
6629                 fe->i_last_eb_blk = 0;
6630         } else if (last_eb)
6631                 fe->i_last_eb_blk = last_eb->h_blkno;
6632
6633         status = ocfs2_journal_dirty(handle, fe_bh);
6634         if (status < 0) {
6635                 mlog_errno(status);
6636                 goto bail;
6637         }
6638
6639         if (last_eb) {
6640                 /* If there will be a new last extent block, then by
6641                  * definition, there cannot be any leaves to the right of
6642                  * him. */
6643                 last_eb->h_next_leaf_blk = 0;
6644                 status = ocfs2_journal_dirty(handle, last_eb_bh);
6645                 if (status < 0) {
6646                         mlog_errno(status);
6647                         goto bail;
6648                 }
6649         }
6650
6651         if (delete_blk) {
6652                 status = ocfs2_truncate_log_append(osb, handle, delete_blk,
6653                                                    clusters_to_del);
6654                 if (status < 0) {
6655                         mlog_errno(status);
6656                         goto bail;
6657                 }
6658         }
6659         status = 0;
6660 bail:
6661
6662         mlog_exit(status);
6663         return status;
6664 }
6665
6666 static int ocfs2_zero_func(handle_t *handle, struct buffer_head *bh)
6667 {
6668         set_buffer_uptodate(bh);
6669         mark_buffer_dirty(bh);
6670         return 0;
6671 }
6672
6673 static void ocfs2_map_and_dirty_page(struct inode *inode, handle_t *handle,
6674                                      unsigned int from, unsigned int to,
6675                                      struct page *page, int zero, u64 *phys)
6676 {
6677         int ret, partial = 0;
6678
6679         ret = ocfs2_map_page_blocks(page, phys, inode, from, to, 0);
6680         if (ret)
6681                 mlog_errno(ret);
6682
6683         if (zero)
6684                 zero_user_segment(page, from, to);
6685
6686         /*
6687          * Need to set the buffers we zero'd into uptodate
6688          * here if they aren't - ocfs2_map_page_blocks()
6689          * might've skipped some
6690          */
6691         ret = walk_page_buffers(handle, page_buffers(page),
6692                                 from, to, &partial,
6693                                 ocfs2_zero_func);
6694         if (ret < 0)
6695                 mlog_errno(ret);
6696         else if (ocfs2_should_order_data(inode)) {
6697                 ret = ocfs2_jbd2_file_inode(handle, inode);
6698                 if (ret < 0)
6699                         mlog_errno(ret);
6700         }
6701
6702         if (!partial)
6703                 SetPageUptodate(page);
6704
6705         flush_dcache_page(page);
6706 }
6707
6708 static void ocfs2_zero_cluster_pages(struct inode *inode, loff_t start,
6709                                      loff_t end, struct page **pages,
6710                                      int numpages, u64 phys, handle_t *handle)
6711 {
6712         int i;
6713         struct page *page;
6714         unsigned int from, to = PAGE_CACHE_SIZE;
6715         struct super_block *sb = inode->i_sb;
6716
6717         BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb)));
6718
6719         if (numpages == 0)
6720                 goto out;
6721
6722         to = PAGE_CACHE_SIZE;
6723         for(i = 0; i < numpages; i++) {
6724                 page = pages[i];
6725
6726                 from = start & (PAGE_CACHE_SIZE - 1);
6727                 if ((end >> PAGE_CACHE_SHIFT) == page->index)
6728                         to = end & (PAGE_CACHE_SIZE - 1);
6729
6730                 BUG_ON(from > PAGE_CACHE_SIZE);
6731                 BUG_ON(to > PAGE_CACHE_SIZE);
6732
6733                 ocfs2_map_and_dirty_page(inode, handle, from, to, page, 1,
6734                                          &phys);
6735
6736                 start = (page->index + 1) << PAGE_CACHE_SHIFT;
6737         }
6738 out:
6739         if (pages)
6740                 ocfs2_unlock_and_free_pages(pages, numpages);
6741 }
6742
6743 static int ocfs2_grab_eof_pages(struct inode *inode, loff_t start, loff_t end,
6744                                 struct page **pages, int *num)
6745 {
6746         int numpages, ret = 0;
6747         struct super_block *sb = inode->i_sb;
6748         struct address_space *mapping = inode->i_mapping;
6749         unsigned long index;
6750         loff_t last_page_bytes;
6751
6752         BUG_ON(start > end);
6753
6754         BUG_ON(start >> OCFS2_SB(sb)->s_clustersize_bits !=
6755                (end - 1) >> OCFS2_SB(sb)->s_clustersize_bits);
6756
6757         numpages = 0;
6758         last_page_bytes = PAGE_ALIGN(end);
6759         index = start >> PAGE_CACHE_SHIFT;
6760         do {
6761                 pages[numpages] = grab_cache_page(mapping, index);
6762                 if (!pages[numpages]) {
6763                         ret = -ENOMEM;
6764                         mlog_errno(ret);
6765                         goto out;
6766                 }
6767
6768                 numpages++;
6769                 index++;
6770         } while (index < (last_page_bytes >> PAGE_CACHE_SHIFT));
6771
6772 out:
6773         if (ret != 0) {
6774                 if (pages)
6775                         ocfs2_unlock_and_free_pages(pages, numpages);
6776                 numpages = 0;
6777         }
6778
6779         *num = numpages;
6780
6781         return ret;
6782 }
6783
6784 /*
6785  * Zero the area past i_size but still within an allocated
6786  * cluster. This avoids exposing nonzero data on subsequent file
6787  * extends.
6788  *
6789  * We need to call this before i_size is updated on the inode because
6790  * otherwise block_write_full_page() will skip writeout of pages past
6791  * i_size. The new_i_size parameter is passed for this reason.
6792  */
6793 int ocfs2_zero_range_for_truncate(struct inode *inode, handle_t *handle,
6794                                   u64 range_start, u64 range_end)
6795 {
6796         int ret = 0, numpages;
6797         struct page **pages = NULL;
6798         u64 phys;
6799         unsigned int ext_flags;
6800         struct super_block *sb = inode->i_sb;
6801
6802         /*
6803          * File systems which don't support sparse files zero on every
6804          * extend.
6805          */
6806         if (!ocfs2_sparse_alloc(OCFS2_SB(sb)))
6807                 return 0;
6808
6809         pages = kcalloc(ocfs2_pages_per_cluster(sb),
6810                         sizeof(struct page *), GFP_NOFS);
6811         if (pages == NULL) {
6812                 ret = -ENOMEM;
6813                 mlog_errno(ret);
6814                 goto out;
6815         }
6816
6817         if (range_start == range_end)
6818                 goto out;
6819
6820         ret = ocfs2_extent_map_get_blocks(inode,
6821                                           range_start >> sb->s_blocksize_bits,
6822                                           &phys, NULL, &ext_flags);
6823         if (ret) {
6824                 mlog_errno(ret);
6825                 goto out;
6826         }
6827
6828         /*
6829          * Tail is a hole, or is marked unwritten. In either case, we
6830          * can count on read and write to return/push zero's.
6831          */
6832         if (phys == 0 || ext_flags & OCFS2_EXT_UNWRITTEN)
6833                 goto out;
6834
6835         ret = ocfs2_grab_eof_pages(inode, range_start, range_end, pages,
6836                                    &numpages);
6837         if (ret) {
6838                 mlog_errno(ret);
6839                 goto out;
6840         }
6841
6842         ocfs2_zero_cluster_pages(inode, range_start, range_end, pages,
6843                                  numpages, phys, handle);
6844
6845         /*
6846          * Initiate writeout of the pages we zero'd here. We don't
6847          * wait on them - the truncate_inode_pages() call later will
6848          * do that for us.
6849          */
6850         ret = do_sync_mapping_range(inode->i_mapping, range_start,
6851                                     range_end - 1, SYNC_FILE_RANGE_WRITE);
6852         if (ret)
6853                 mlog_errno(ret);
6854
6855 out:
6856         if (pages)
6857                 kfree(pages);
6858
6859         return ret;
6860 }
6861
6862 static void ocfs2_zero_dinode_id2_with_xattr(struct inode *inode,
6863                                              struct ocfs2_dinode *di)
6864 {
6865         unsigned int blocksize = 1 << inode->i_sb->s_blocksize_bits;
6866         unsigned int xattrsize = le16_to_cpu(di->i_xattr_inline_size);
6867
6868         if (le16_to_cpu(di->i_dyn_features) & OCFS2_INLINE_XATTR_FL)
6869                 memset(&di->id2, 0, blocksize -
6870                                     offsetof(struct ocfs2_dinode, id2) -
6871                                     xattrsize);
6872         else
6873                 memset(&di->id2, 0, blocksize -
6874                                     offsetof(struct ocfs2_dinode, id2));
6875 }
6876
6877 void ocfs2_dinode_new_extent_list(struct inode *inode,
6878                                   struct ocfs2_dinode *di)
6879 {
6880         ocfs2_zero_dinode_id2_with_xattr(inode, di);
6881         di->id2.i_list.l_tree_depth = 0;
6882         di->id2.i_list.l_next_free_rec = 0;
6883         di->id2.i_list.l_count = cpu_to_le16(
6884                 ocfs2_extent_recs_per_inode_with_xattr(inode->i_sb, di));
6885 }
6886
6887 void ocfs2_set_inode_data_inline(struct inode *inode, struct ocfs2_dinode *di)
6888 {
6889         struct ocfs2_inode_info *oi = OCFS2_I(inode);
6890         struct ocfs2_inline_data *idata = &di->id2.i_data;
6891
6892         spin_lock(&oi->ip_lock);
6893         oi->ip_dyn_features |= OCFS2_INLINE_DATA_FL;
6894         di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features);
6895         spin_unlock(&oi->ip_lock);
6896
6897         /*
6898          * We clear the entire i_data structure here so that all
6899          * fields can be properly initialized.
6900          */
6901         ocfs2_zero_dinode_id2_with_xattr(inode, di);
6902
6903         idata->id_count = cpu_to_le16(
6904                         ocfs2_max_inline_data_with_xattr(inode->i_sb, di));
6905 }
6906
6907 int ocfs2_convert_inline_data_to_extents(struct inode *inode,
6908                                          struct buffer_head *di_bh)
6909 {
6910         int ret, i, has_data, num_pages = 0;
6911         handle_t *handle;
6912         u64 uninitialized_var(block);
6913         struct ocfs2_inode_info *oi = OCFS2_I(inode);
6914         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
6915         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
6916         struct ocfs2_alloc_context *data_ac = NULL;
6917         struct page **pages = NULL;
6918         loff_t end = osb->s_clustersize;
6919         struct ocfs2_extent_tree et;
6920         int did_quota = 0;
6921
6922         has_data = i_size_read(inode) ? 1 : 0;
6923
6924         if (has_data) {
6925                 pages = kcalloc(ocfs2_pages_per_cluster(osb->sb),
6926                                 sizeof(struct page *), GFP_NOFS);
6927                 if (pages == NULL) {
6928                         ret = -ENOMEM;
6929                         mlog_errno(ret);
6930                         goto out;
6931                 }
6932
6933                 ret = ocfs2_reserve_clusters(osb, 1, &data_ac);
6934                 if (ret) {
6935                         mlog_errno(ret);
6936                         goto out;
6937                 }
6938         }
6939
6940         handle = ocfs2_start_trans(osb,
6941                                    ocfs2_inline_to_extents_credits(osb->sb));
6942         if (IS_ERR(handle)) {
6943                 ret = PTR_ERR(handle);
6944                 mlog_errno(ret);
6945                 goto out_unlock;
6946         }
6947
6948         ret = ocfs2_journal_access_di(handle, inode, di_bh,
6949                                       OCFS2_JOURNAL_ACCESS_WRITE);
6950         if (ret) {
6951                 mlog_errno(ret);
6952                 goto out_commit;
6953         }
6954
6955         if (has_data) {
6956                 u32 bit_off, num;
6957                 unsigned int page_end;
6958                 u64 phys;
6959
6960                 if (vfs_dq_alloc_space_nodirty(inode,
6961                                        ocfs2_clusters_to_bytes(osb->sb, 1))) {
6962                         ret = -EDQUOT;
6963                         goto out_commit;
6964                 }
6965                 did_quota = 1;
6966
6967                 ret = ocfs2_claim_clusters(osb, handle, data_ac, 1, &bit_off,
6968                                            &num);
6969                 if (ret) {
6970                         mlog_errno(ret);
6971                         goto out_commit;
6972                 }
6973
6974                 /*
6975                  * Save two copies, one for insert, and one that can
6976                  * be changed by ocfs2_map_and_dirty_page() below.
6977                  */
6978                 block = phys = ocfs2_clusters_to_blocks(inode->i_sb, bit_off);
6979
6980                 /*
6981                  * Non sparse file systems zero on extend, so no need
6982                  * to do that now.
6983                  */
6984                 if (!ocfs2_sparse_alloc(osb) &&
6985                     PAGE_CACHE_SIZE < osb->s_clustersize)
6986                         end = PAGE_CACHE_SIZE;
6987
6988                 ret = ocfs2_grab_eof_pages(inode, 0, end, pages, &num_pages);
6989                 if (ret) {
6990                         mlog_errno(ret);
6991                         goto out_commit;
6992                 }
6993
6994                 /*
6995                  * This should populate the 1st page for us and mark
6996                  * it up to date.
6997                  */
6998                 ret = ocfs2_read_inline_data(inode, pages[0], di_bh);
6999                 if (ret) {
7000                         mlog_errno(ret);
7001                         goto out_commit;
7002                 }
7003
7004                 page_end = PAGE_CACHE_SIZE;
7005                 if (PAGE_CACHE_SIZE > osb->s_clustersize)
7006                         page_end = osb->s_clustersize;
7007
7008                 for (i = 0; i < num_pages; i++)
7009                         ocfs2_map_and_dirty_page(inode, handle, 0, page_end,
7010                                                  pages[i], i > 0, &phys);
7011         }
7012
7013         spin_lock(&oi->ip_lock);
7014         oi->ip_dyn_features &= ~OCFS2_INLINE_DATA_FL;
7015         di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features);
7016         spin_unlock(&oi->ip_lock);
7017
7018         ocfs2_dinode_new_extent_list(inode, di);
7019
7020         ocfs2_journal_dirty(handle, di_bh);
7021
7022         if (has_data) {
7023                 /*
7024                  * An error at this point should be extremely rare. If
7025                  * this proves to be false, we could always re-build
7026                  * the in-inode data from our pages.
7027                  */
7028                 ocfs2_init_dinode_extent_tree(&et, inode, di_bh);
7029                 ret = ocfs2_insert_extent(osb, handle, inode, &et,
7030                                           0, block, 1, 0, NULL);
7031                 if (ret) {
7032                         mlog_errno(ret);
7033                         goto out_commit;
7034                 }
7035
7036                 inode->i_blocks = ocfs2_inode_sector_count(inode);
7037         }
7038
7039 out_commit:
7040         if (ret < 0 && did_quota)
7041                 vfs_dq_free_space_nodirty(inode,
7042                                           ocfs2_clusters_to_bytes(osb->sb, 1));
7043
7044         ocfs2_commit_trans(osb, handle);
7045
7046 out_unlock:
7047         if (data_ac)
7048                 ocfs2_free_alloc_context(data_ac);
7049
7050 out:
7051         if (pages) {
7052                 ocfs2_unlock_and_free_pages(pages, num_pages);
7053                 kfree(pages);
7054         }
7055
7056         return ret;
7057 }
7058
7059 /*
7060  * It is expected, that by the time you call this function,
7061  * inode->i_size and fe->i_size have been adjusted.
7062  *
7063  * WARNING: This will kfree the truncate context
7064  */
7065 int ocfs2_commit_truncate(struct ocfs2_super *osb,
7066                           struct inode *inode,
7067                           struct buffer_head *fe_bh,
7068                           struct ocfs2_truncate_context *tc)
7069 {
7070         int status, i, credits, tl_sem = 0;
7071         u32 clusters_to_del, new_highest_cpos, range;
7072         struct ocfs2_extent_list *el;
7073         handle_t *handle = NULL;
7074         struct inode *tl_inode = osb->osb_tl_inode;
7075         struct ocfs2_path *path = NULL;
7076         struct ocfs2_dinode *di = (struct ocfs2_dinode *)fe_bh->b_data;
7077
7078         mlog_entry_void();
7079
7080         new_highest_cpos = ocfs2_clusters_for_bytes(osb->sb,
7081                                                      i_size_read(inode));
7082
7083         path = ocfs2_new_path(fe_bh, &di->id2.i_list,
7084                               ocfs2_journal_access_di);
7085         if (!path) {
7086                 status = -ENOMEM;
7087                 mlog_errno(status);
7088                 goto bail;
7089         }
7090
7091         ocfs2_extent_map_trunc(inode, new_highest_cpos);
7092
7093 start:
7094         /*
7095          * Check that we still have allocation to delete.
7096          */
7097         if (OCFS2_I(inode)->ip_clusters == 0) {
7098                 status = 0;
7099                 goto bail;
7100         }
7101
7102         /*
7103          * Truncate always works against the rightmost tree branch.
7104          */
7105         status = ocfs2_find_path(inode, path, UINT_MAX);
7106         if (status) {
7107                 mlog_errno(status);
7108                 goto bail;
7109         }
7110
7111         mlog(0, "inode->ip_clusters = %u, tree_depth = %u\n",
7112              OCFS2_I(inode)->ip_clusters, path->p_tree_depth);
7113
7114         /*
7115          * By now, el will point to the extent list on the bottom most
7116          * portion of this tree. Only the tail record is considered in
7117          * each pass.
7118          *
7119          * We handle the following cases, in order:
7120          * - empty extent: delete the remaining branch
7121          * - remove the entire record
7122          * - remove a partial record
7123          * - no record needs to be removed (truncate has completed)
7124          */
7125         el = path_leaf_el(path);
7126         if (le16_to_cpu(el->l_next_free_rec) == 0) {
7127                 ocfs2_error(inode->i_sb,
7128                             "Inode %llu has empty extent block at %llu\n",
7129                             (unsigned long long)OCFS2_I(inode)->ip_blkno,
7130                             (unsigned long long)path_leaf_bh(path)->b_blocknr);
7131                 status = -EROFS;
7132                 goto bail;
7133         }
7134
7135         i = le16_to_cpu(el->l_next_free_rec) - 1;
7136         range = le32_to_cpu(el->l_recs[i].e_cpos) +
7137                 ocfs2_rec_clusters(el, &el->l_recs[i]);
7138         if (i == 0 && ocfs2_is_empty_extent(&el->l_recs[i])) {
7139                 clusters_to_del = 0;
7140         } else if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_highest_cpos) {
7141                 clusters_to_del = ocfs2_rec_clusters(el, &el->l_recs[i]);
7142         } else if (range > new_highest_cpos) {
7143                 clusters_to_del = (ocfs2_rec_clusters(el, &el->l_recs[i]) +
7144                                    le32_to_cpu(el->l_recs[i].e_cpos)) -
7145                                   new_highest_cpos;
7146         } else {
7147                 status = 0;
7148                 goto bail;
7149         }
7150
7151         mlog(0, "clusters_to_del = %u in this pass, tail blk=%llu\n",
7152              clusters_to_del, (unsigned long long)path_leaf_bh(path)->b_blocknr);
7153
7154         mutex_lock(&tl_inode->i_mutex);
7155         tl_sem = 1;
7156         /* ocfs2_truncate_log_needs_flush guarantees us at least one
7157          * record is free for use. If there isn't any, we flush to get
7158          * an empty truncate log.  */
7159         if (ocfs2_truncate_log_needs_flush(osb)) {
7160                 status = __ocfs2_flush_truncate_log(osb);
7161                 if (status < 0) {
7162                         mlog_errno(status);
7163                         goto bail;
7164                 }
7165         }
7166
7167         credits = ocfs2_calc_tree_trunc_credits(osb->sb, clusters_to_del,
7168                                                 (struct ocfs2_dinode *)fe_bh->b_data,
7169                                                 el);
7170         handle = ocfs2_start_trans(osb, credits);
7171         if (IS_ERR(handle)) {
7172                 status = PTR_ERR(handle);
7173                 handle = NULL;
7174                 mlog_errno(status);
7175                 goto bail;
7176         }
7177
7178         status = ocfs2_do_truncate(osb, clusters_to_del, inode, fe_bh, handle,
7179                                    tc, path);
7180         if (status < 0) {
7181                 mlog_errno(status);
7182                 goto bail;
7183         }
7184
7185         mutex_unlock(&tl_inode->i_mutex);
7186         tl_sem = 0;
7187
7188         ocfs2_commit_trans(osb, handle);
7189         handle = NULL;
7190
7191         ocfs2_reinit_path(path, 1);
7192
7193         /*
7194          * The check above will catch the case where we've truncated
7195          * away all allocation.
7196          */
7197         goto start;
7198
7199 bail:
7200
7201         ocfs2_schedule_truncate_log_flush(osb, 1);
7202
7203         if (tl_sem)
7204                 mutex_unlock(&tl_inode->i_mutex);
7205
7206         if (handle)
7207                 ocfs2_commit_trans(osb, handle);
7208
7209         ocfs2_run_deallocs(osb, &tc->tc_dealloc);
7210
7211         ocfs2_free_path(path);
7212
7213         /* This will drop the ext_alloc cluster lock for us */
7214         ocfs2_free_truncate_context(tc);
7215
7216         mlog_exit(status);
7217         return status;
7218 }
7219
7220 /*
7221  * Expects the inode to already be locked.
7222  */
7223 int ocfs2_prepare_truncate(struct ocfs2_super *osb,
7224                            struct inode *inode,
7225                            struct buffer_head *fe_bh,
7226                            struct ocfs2_truncate_context **tc)
7227 {
7228         int status;
7229         unsigned int new_i_clusters;
7230         struct ocfs2_dinode *fe;
7231         struct ocfs2_extent_block *eb;
7232         struct buffer_head *last_eb_bh = NULL;
7233
7234         mlog_entry_void();
7235
7236         *tc = NULL;
7237
7238         new_i_clusters = ocfs2_clusters_for_bytes(osb->sb,
7239                                                   i_size_read(inode));
7240         fe = (struct ocfs2_dinode *) fe_bh->b_data;
7241
7242         mlog(0, "fe->i_clusters = %u, new_i_clusters = %u, fe->i_size ="
7243              "%llu\n", le32_to_cpu(fe->i_clusters), new_i_clusters,
7244              (unsigned long long)le64_to_cpu(fe->i_size));
7245
7246         *tc = kzalloc(sizeof(struct ocfs2_truncate_context), GFP_KERNEL);
7247         if (!(*tc)) {
7248                 status = -ENOMEM;
7249                 mlog_errno(status);
7250                 goto bail;
7251         }
7252         ocfs2_init_dealloc_ctxt(&(*tc)->tc_dealloc);
7253
7254         if (fe->id2.i_list.l_tree_depth) {
7255                 status = ocfs2_read_extent_block(inode,
7256                                                  le64_to_cpu(fe->i_last_eb_blk),
7257                                                  &last_eb_bh);
7258                 if (status < 0) {
7259                         mlog_errno(status);
7260                         goto bail;
7261                 }
7262                 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
7263         }
7264
7265         (*tc)->tc_last_eb_bh = last_eb_bh;
7266
7267         status = 0;
7268 bail:
7269         if (status < 0) {
7270                 if (*tc)
7271                         ocfs2_free_truncate_context(*tc);
7272                 *tc = NULL;
7273         }
7274         mlog_exit_void();
7275         return status;
7276 }
7277
7278 /*
7279  * 'start' is inclusive, 'end' is not.
7280  */
7281 int ocfs2_truncate_inline(struct inode *inode, struct buffer_head *di_bh,
7282                           unsigned int start, unsigned int end, int trunc)
7283 {
7284         int ret;
7285         unsigned int numbytes;
7286         handle_t *handle;
7287         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
7288         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
7289         struct ocfs2_inline_data *idata = &di->id2.i_data;
7290
7291         if (end > i_size_read(inode))
7292                 end = i_size_read(inode);
7293
7294         BUG_ON(start >= end);
7295
7296         if (!(OCFS2_I(inode)->ip_dyn_features & OCFS2_INLINE_DATA_FL) ||
7297             !(le16_to_cpu(di->i_dyn_features) & OCFS2_INLINE_DATA_FL) ||
7298             !ocfs2_supports_inline_data(osb)) {
7299                 ocfs2_error(inode->i_sb,
7300                             "Inline data flags for inode %llu don't agree! "
7301                             "Disk: 0x%x, Memory: 0x%x, Superblock: 0x%x\n",
7302                             (unsigned long long)OCFS2_I(inode)->ip_blkno,
7303                             le16_to_cpu(di->i_dyn_features),
7304                             OCFS2_I(inode)->ip_dyn_features,
7305                             osb->s_feature_incompat);
7306                 ret = -EROFS;
7307                 goto out;
7308         }
7309
7310         handle = ocfs2_start_trans(osb, OCFS2_INODE_UPDATE_CREDITS);
7311         if (IS_ERR(handle)) {
7312                 ret = PTR_ERR(handle);
7313                 mlog_errno(ret);
7314                 goto out;
7315         }
7316
7317         ret = ocfs2_journal_access_di(handle, inode, di_bh,
7318                                       OCFS2_JOURNAL_ACCESS_WRITE);
7319         if (ret) {
7320                 mlog_errno(ret);
7321                 goto out_commit;
7322         }
7323
7324         numbytes = end - start;
7325         memset(idata->id_data + start, 0, numbytes);
7326
7327         /*
7328          * No need to worry about the data page here - it's been
7329          * truncated already and inline data doesn't need it for
7330          * pushing zero's to disk, so we'll let readpage pick it up
7331          * later.
7332          */
7333         if (trunc) {
7334                 i_size_write(inode, start);
7335                 di->i_size = cpu_to_le64(start);
7336         }
7337
7338         inode->i_blocks = ocfs2_inode_sector_count(inode);
7339         inode->i_ctime = inode->i_mtime = CURRENT_TIME;
7340
7341         di->i_ctime = di->i_mtime = cpu_to_le64(inode->i_ctime.tv_sec);
7342         di->i_ctime_nsec = di->i_mtime_nsec = cpu_to_le32(inode->i_ctime.tv_nsec);
7343
7344         ocfs2_journal_dirty(handle, di_bh);
7345
7346 out_commit:
7347         ocfs2_commit_trans(osb, handle);
7348
7349 out:
7350         return ret;
7351 }
7352
7353 static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc)
7354 {
7355         /*
7356          * The caller is responsible for completing deallocation
7357          * before freeing the context.
7358          */
7359         if (tc->tc_dealloc.c_first_suballocator != NULL)
7360                 mlog(ML_NOTICE,
7361                      "Truncate completion has non-empty dealloc context\n");
7362
7363         brelse(tc->tc_last_eb_bh);
7364
7365         kfree(tc);
7366 }