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