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