1 /* -*- mode: c; c-basic-offset: 8; -*-
2 * vim: noexpandtab sw=8 ts=8 sts=0:
6 * Extent allocs and frees
8 * Copyright (C) 2002, 2004 Oracle. All rights reserved.
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.
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.
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.
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 #include <linux/blkdev.h>
34 #include <cluster/masklog.h>
40 #include "blockcheck.h"
42 #include "extent_map.h"
45 #include "localalloc.h"
52 #include "refcounttree.h"
53 #include "ocfs2_trace.h"
55 #include "buffer_head_io.h"
57 enum ocfs2_contig_type
{
64 static enum ocfs2_contig_type
65 ocfs2_extent_rec_contig(struct super_block
*sb
,
66 struct ocfs2_extent_rec
*ext
,
67 struct ocfs2_extent_rec
*insert_rec
);
69 * Operations for a specific extent tree type.
71 * To implement an on-disk btree (extent tree) type in ocfs2, add
72 * an ocfs2_extent_tree_operations structure and the matching
73 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it
74 * for the allocation portion of the extent tree.
76 struct ocfs2_extent_tree_operations
{
78 * last_eb_blk is the block number of the right most leaf extent
79 * block. Most on-disk structures containing an extent tree store
80 * this value for fast access. The ->eo_set_last_eb_blk() and
81 * ->eo_get_last_eb_blk() operations access this value. They are
84 void (*eo_set_last_eb_blk
)(struct ocfs2_extent_tree
*et
,
86 u64 (*eo_get_last_eb_blk
)(struct ocfs2_extent_tree
*et
);
89 * The on-disk structure usually keeps track of how many total
90 * clusters are stored in this extent tree. This function updates
91 * that value. new_clusters is the delta, and must be
92 * added to the total. Required.
94 void (*eo_update_clusters
)(struct ocfs2_extent_tree
*et
,
98 * If this extent tree is supported by an extent map, insert
99 * a record into the map.
101 void (*eo_extent_map_insert
)(struct ocfs2_extent_tree
*et
,
102 struct ocfs2_extent_rec
*rec
);
105 * If this extent tree is supported by an extent map, truncate the
108 void (*eo_extent_map_truncate
)(struct ocfs2_extent_tree
*et
,
112 * If ->eo_insert_check() exists, it is called before rec is
113 * inserted into the extent tree. It is optional.
115 int (*eo_insert_check
)(struct ocfs2_extent_tree
*et
,
116 struct ocfs2_extent_rec
*rec
);
117 int (*eo_sanity_check
)(struct ocfs2_extent_tree
*et
);
120 * --------------------------------------------------------------
121 * The remaining are internal to ocfs2_extent_tree and don't have
126 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
129 void (*eo_fill_root_el
)(struct ocfs2_extent_tree
*et
);
132 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
133 * it exists. If it does not, et->et_max_leaf_clusters is set
134 * to 0 (unlimited). Optional.
136 void (*eo_fill_max_leaf_clusters
)(struct ocfs2_extent_tree
*et
);
139 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
140 * are contiguous or not. Optional. Don't need to set it if use
141 * ocfs2_extent_rec as the tree leaf.
143 enum ocfs2_contig_type
144 (*eo_extent_contig
)(struct ocfs2_extent_tree
*et
,
145 struct ocfs2_extent_rec
*ext
,
146 struct ocfs2_extent_rec
*insert_rec
);
151 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
154 static u64
ocfs2_dinode_get_last_eb_blk(struct ocfs2_extent_tree
*et
);
155 static void ocfs2_dinode_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
157 static void ocfs2_dinode_update_clusters(struct ocfs2_extent_tree
*et
,
159 static void ocfs2_dinode_extent_map_insert(struct ocfs2_extent_tree
*et
,
160 struct ocfs2_extent_rec
*rec
);
161 static void ocfs2_dinode_extent_map_truncate(struct ocfs2_extent_tree
*et
,
163 static int ocfs2_dinode_insert_check(struct ocfs2_extent_tree
*et
,
164 struct ocfs2_extent_rec
*rec
);
165 static int ocfs2_dinode_sanity_check(struct ocfs2_extent_tree
*et
);
166 static void ocfs2_dinode_fill_root_el(struct ocfs2_extent_tree
*et
);
167 static struct ocfs2_extent_tree_operations ocfs2_dinode_et_ops
= {
168 .eo_set_last_eb_blk
= ocfs2_dinode_set_last_eb_blk
,
169 .eo_get_last_eb_blk
= ocfs2_dinode_get_last_eb_blk
,
170 .eo_update_clusters
= ocfs2_dinode_update_clusters
,
171 .eo_extent_map_insert
= ocfs2_dinode_extent_map_insert
,
172 .eo_extent_map_truncate
= ocfs2_dinode_extent_map_truncate
,
173 .eo_insert_check
= ocfs2_dinode_insert_check
,
174 .eo_sanity_check
= ocfs2_dinode_sanity_check
,
175 .eo_fill_root_el
= ocfs2_dinode_fill_root_el
,
178 static void ocfs2_dinode_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
181 struct ocfs2_dinode
*di
= et
->et_object
;
183 BUG_ON(et
->et_ops
!= &ocfs2_dinode_et_ops
);
184 di
->i_last_eb_blk
= cpu_to_le64(blkno
);
187 static u64
ocfs2_dinode_get_last_eb_blk(struct ocfs2_extent_tree
*et
)
189 struct ocfs2_dinode
*di
= et
->et_object
;
191 BUG_ON(et
->et_ops
!= &ocfs2_dinode_et_ops
);
192 return le64_to_cpu(di
->i_last_eb_blk
);
195 static void ocfs2_dinode_update_clusters(struct ocfs2_extent_tree
*et
,
198 struct ocfs2_inode_info
*oi
= cache_info_to_inode(et
->et_ci
);
199 struct ocfs2_dinode
*di
= et
->et_object
;
201 le32_add_cpu(&di
->i_clusters
, clusters
);
202 spin_lock(&oi
->ip_lock
);
203 oi
->ip_clusters
= le32_to_cpu(di
->i_clusters
);
204 spin_unlock(&oi
->ip_lock
);
207 static void ocfs2_dinode_extent_map_insert(struct ocfs2_extent_tree
*et
,
208 struct ocfs2_extent_rec
*rec
)
210 struct inode
*inode
= &cache_info_to_inode(et
->et_ci
)->vfs_inode
;
212 ocfs2_extent_map_insert_rec(inode
, rec
);
215 static void ocfs2_dinode_extent_map_truncate(struct ocfs2_extent_tree
*et
,
218 struct inode
*inode
= &cache_info_to_inode(et
->et_ci
)->vfs_inode
;
220 ocfs2_extent_map_trunc(inode
, clusters
);
223 static int ocfs2_dinode_insert_check(struct ocfs2_extent_tree
*et
,
224 struct ocfs2_extent_rec
*rec
)
226 struct ocfs2_inode_info
*oi
= cache_info_to_inode(et
->et_ci
);
227 struct ocfs2_super
*osb
= OCFS2_SB(oi
->vfs_inode
.i_sb
);
229 BUG_ON(oi
->ip_dyn_features
& OCFS2_INLINE_DATA_FL
);
230 mlog_bug_on_msg(!ocfs2_sparse_alloc(osb
) &&
231 (oi
->ip_clusters
!= le32_to_cpu(rec
->e_cpos
)),
232 "Device %s, asking for sparse allocation: inode %llu, "
233 "cpos %u, clusters %u\n",
235 (unsigned long long)oi
->ip_blkno
,
236 rec
->e_cpos
, oi
->ip_clusters
);
241 static int ocfs2_dinode_sanity_check(struct ocfs2_extent_tree
*et
)
243 struct ocfs2_dinode
*di
= et
->et_object
;
245 BUG_ON(et
->et_ops
!= &ocfs2_dinode_et_ops
);
246 BUG_ON(!OCFS2_IS_VALID_DINODE(di
));
251 static void ocfs2_dinode_fill_root_el(struct ocfs2_extent_tree
*et
)
253 struct ocfs2_dinode
*di
= et
->et_object
;
255 et
->et_root_el
= &di
->id2
.i_list
;
259 static void ocfs2_xattr_value_fill_root_el(struct ocfs2_extent_tree
*et
)
261 struct ocfs2_xattr_value_buf
*vb
= et
->et_object
;
263 et
->et_root_el
= &vb
->vb_xv
->xr_list
;
266 static void ocfs2_xattr_value_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
269 struct ocfs2_xattr_value_buf
*vb
= et
->et_object
;
271 vb
->vb_xv
->xr_last_eb_blk
= cpu_to_le64(blkno
);
274 static u64
ocfs2_xattr_value_get_last_eb_blk(struct ocfs2_extent_tree
*et
)
276 struct ocfs2_xattr_value_buf
*vb
= et
->et_object
;
278 return le64_to_cpu(vb
->vb_xv
->xr_last_eb_blk
);
281 static void ocfs2_xattr_value_update_clusters(struct ocfs2_extent_tree
*et
,
284 struct ocfs2_xattr_value_buf
*vb
= et
->et_object
;
286 le32_add_cpu(&vb
->vb_xv
->xr_clusters
, clusters
);
289 static struct ocfs2_extent_tree_operations ocfs2_xattr_value_et_ops
= {
290 .eo_set_last_eb_blk
= ocfs2_xattr_value_set_last_eb_blk
,
291 .eo_get_last_eb_blk
= ocfs2_xattr_value_get_last_eb_blk
,
292 .eo_update_clusters
= ocfs2_xattr_value_update_clusters
,
293 .eo_fill_root_el
= ocfs2_xattr_value_fill_root_el
,
296 static void ocfs2_xattr_tree_fill_root_el(struct ocfs2_extent_tree
*et
)
298 struct ocfs2_xattr_block
*xb
= et
->et_object
;
300 et
->et_root_el
= &xb
->xb_attrs
.xb_root
.xt_list
;
303 static void ocfs2_xattr_tree_fill_max_leaf_clusters(struct ocfs2_extent_tree
*et
)
305 struct super_block
*sb
= ocfs2_metadata_cache_get_super(et
->et_ci
);
306 et
->et_max_leaf_clusters
=
307 ocfs2_clusters_for_bytes(sb
, OCFS2_MAX_XATTR_TREE_LEAF_SIZE
);
310 static void ocfs2_xattr_tree_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
313 struct ocfs2_xattr_block
*xb
= et
->et_object
;
314 struct ocfs2_xattr_tree_root
*xt
= &xb
->xb_attrs
.xb_root
;
316 xt
->xt_last_eb_blk
= cpu_to_le64(blkno
);
319 static u64
ocfs2_xattr_tree_get_last_eb_blk(struct ocfs2_extent_tree
*et
)
321 struct ocfs2_xattr_block
*xb
= et
->et_object
;
322 struct ocfs2_xattr_tree_root
*xt
= &xb
->xb_attrs
.xb_root
;
324 return le64_to_cpu(xt
->xt_last_eb_blk
);
327 static void ocfs2_xattr_tree_update_clusters(struct ocfs2_extent_tree
*et
,
330 struct ocfs2_xattr_block
*xb
= et
->et_object
;
332 le32_add_cpu(&xb
->xb_attrs
.xb_root
.xt_clusters
, clusters
);
335 static struct ocfs2_extent_tree_operations ocfs2_xattr_tree_et_ops
= {
336 .eo_set_last_eb_blk
= ocfs2_xattr_tree_set_last_eb_blk
,
337 .eo_get_last_eb_blk
= ocfs2_xattr_tree_get_last_eb_blk
,
338 .eo_update_clusters
= ocfs2_xattr_tree_update_clusters
,
339 .eo_fill_root_el
= ocfs2_xattr_tree_fill_root_el
,
340 .eo_fill_max_leaf_clusters
= ocfs2_xattr_tree_fill_max_leaf_clusters
,
343 static void ocfs2_dx_root_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
346 struct ocfs2_dx_root_block
*dx_root
= et
->et_object
;
348 dx_root
->dr_last_eb_blk
= cpu_to_le64(blkno
);
351 static u64
ocfs2_dx_root_get_last_eb_blk(struct ocfs2_extent_tree
*et
)
353 struct ocfs2_dx_root_block
*dx_root
= et
->et_object
;
355 return le64_to_cpu(dx_root
->dr_last_eb_blk
);
358 static void ocfs2_dx_root_update_clusters(struct ocfs2_extent_tree
*et
,
361 struct ocfs2_dx_root_block
*dx_root
= et
->et_object
;
363 le32_add_cpu(&dx_root
->dr_clusters
, clusters
);
366 static int ocfs2_dx_root_sanity_check(struct ocfs2_extent_tree
*et
)
368 struct ocfs2_dx_root_block
*dx_root
= et
->et_object
;
370 BUG_ON(!OCFS2_IS_VALID_DX_ROOT(dx_root
));
375 static void ocfs2_dx_root_fill_root_el(struct ocfs2_extent_tree
*et
)
377 struct ocfs2_dx_root_block
*dx_root
= et
->et_object
;
379 et
->et_root_el
= &dx_root
->dr_list
;
382 static struct ocfs2_extent_tree_operations ocfs2_dx_root_et_ops
= {
383 .eo_set_last_eb_blk
= ocfs2_dx_root_set_last_eb_blk
,
384 .eo_get_last_eb_blk
= ocfs2_dx_root_get_last_eb_blk
,
385 .eo_update_clusters
= ocfs2_dx_root_update_clusters
,
386 .eo_sanity_check
= ocfs2_dx_root_sanity_check
,
387 .eo_fill_root_el
= ocfs2_dx_root_fill_root_el
,
390 static void ocfs2_refcount_tree_fill_root_el(struct ocfs2_extent_tree
*et
)
392 struct ocfs2_refcount_block
*rb
= et
->et_object
;
394 et
->et_root_el
= &rb
->rf_list
;
397 static void ocfs2_refcount_tree_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
400 struct ocfs2_refcount_block
*rb
= et
->et_object
;
402 rb
->rf_last_eb_blk
= cpu_to_le64(blkno
);
405 static u64
ocfs2_refcount_tree_get_last_eb_blk(struct ocfs2_extent_tree
*et
)
407 struct ocfs2_refcount_block
*rb
= et
->et_object
;
409 return le64_to_cpu(rb
->rf_last_eb_blk
);
412 static void ocfs2_refcount_tree_update_clusters(struct ocfs2_extent_tree
*et
,
415 struct ocfs2_refcount_block
*rb
= et
->et_object
;
417 le32_add_cpu(&rb
->rf_clusters
, clusters
);
420 static enum ocfs2_contig_type
421 ocfs2_refcount_tree_extent_contig(struct ocfs2_extent_tree
*et
,
422 struct ocfs2_extent_rec
*ext
,
423 struct ocfs2_extent_rec
*insert_rec
)
428 static struct ocfs2_extent_tree_operations ocfs2_refcount_tree_et_ops
= {
429 .eo_set_last_eb_blk
= ocfs2_refcount_tree_set_last_eb_blk
,
430 .eo_get_last_eb_blk
= ocfs2_refcount_tree_get_last_eb_blk
,
431 .eo_update_clusters
= ocfs2_refcount_tree_update_clusters
,
432 .eo_fill_root_el
= ocfs2_refcount_tree_fill_root_el
,
433 .eo_extent_contig
= ocfs2_refcount_tree_extent_contig
,
436 static void __ocfs2_init_extent_tree(struct ocfs2_extent_tree
*et
,
437 struct ocfs2_caching_info
*ci
,
438 struct buffer_head
*bh
,
439 ocfs2_journal_access_func access
,
441 struct ocfs2_extent_tree_operations
*ops
)
446 et
->et_root_journal_access
= access
;
448 obj
= (void *)bh
->b_data
;
451 et
->et_ops
->eo_fill_root_el(et
);
452 if (!et
->et_ops
->eo_fill_max_leaf_clusters
)
453 et
->et_max_leaf_clusters
= 0;
455 et
->et_ops
->eo_fill_max_leaf_clusters(et
);
458 void ocfs2_init_dinode_extent_tree(struct ocfs2_extent_tree
*et
,
459 struct ocfs2_caching_info
*ci
,
460 struct buffer_head
*bh
)
462 __ocfs2_init_extent_tree(et
, ci
, bh
, ocfs2_journal_access_di
,
463 NULL
, &ocfs2_dinode_et_ops
);
466 void ocfs2_init_xattr_tree_extent_tree(struct ocfs2_extent_tree
*et
,
467 struct ocfs2_caching_info
*ci
,
468 struct buffer_head
*bh
)
470 __ocfs2_init_extent_tree(et
, ci
, bh
, ocfs2_journal_access_xb
,
471 NULL
, &ocfs2_xattr_tree_et_ops
);
474 void ocfs2_init_xattr_value_extent_tree(struct ocfs2_extent_tree
*et
,
475 struct ocfs2_caching_info
*ci
,
476 struct ocfs2_xattr_value_buf
*vb
)
478 __ocfs2_init_extent_tree(et
, ci
, vb
->vb_bh
, vb
->vb_access
, vb
,
479 &ocfs2_xattr_value_et_ops
);
482 void ocfs2_init_dx_root_extent_tree(struct ocfs2_extent_tree
*et
,
483 struct ocfs2_caching_info
*ci
,
484 struct buffer_head
*bh
)
486 __ocfs2_init_extent_tree(et
, ci
, bh
, ocfs2_journal_access_dr
,
487 NULL
, &ocfs2_dx_root_et_ops
);
490 void ocfs2_init_refcount_extent_tree(struct ocfs2_extent_tree
*et
,
491 struct ocfs2_caching_info
*ci
,
492 struct buffer_head
*bh
)
494 __ocfs2_init_extent_tree(et
, ci
, bh
, ocfs2_journal_access_rb
,
495 NULL
, &ocfs2_refcount_tree_et_ops
);
498 static inline void ocfs2_et_set_last_eb_blk(struct ocfs2_extent_tree
*et
,
501 et
->et_ops
->eo_set_last_eb_blk(et
, new_last_eb_blk
);
504 static inline u64
ocfs2_et_get_last_eb_blk(struct ocfs2_extent_tree
*et
)
506 return et
->et_ops
->eo_get_last_eb_blk(et
);
509 static inline void ocfs2_et_update_clusters(struct ocfs2_extent_tree
*et
,
512 et
->et_ops
->eo_update_clusters(et
, clusters
);
515 static inline void ocfs2_et_extent_map_insert(struct ocfs2_extent_tree
*et
,
516 struct ocfs2_extent_rec
*rec
)
518 if (et
->et_ops
->eo_extent_map_insert
)
519 et
->et_ops
->eo_extent_map_insert(et
, rec
);
522 static inline void ocfs2_et_extent_map_truncate(struct ocfs2_extent_tree
*et
,
525 if (et
->et_ops
->eo_extent_map_truncate
)
526 et
->et_ops
->eo_extent_map_truncate(et
, clusters
);
529 static inline int ocfs2_et_root_journal_access(handle_t
*handle
,
530 struct ocfs2_extent_tree
*et
,
533 return et
->et_root_journal_access(handle
, et
->et_ci
, et
->et_root_bh
,
537 static inline enum ocfs2_contig_type
538 ocfs2_et_extent_contig(struct ocfs2_extent_tree
*et
,
539 struct ocfs2_extent_rec
*rec
,
540 struct ocfs2_extent_rec
*insert_rec
)
542 if (et
->et_ops
->eo_extent_contig
)
543 return et
->et_ops
->eo_extent_contig(et
, rec
, insert_rec
);
545 return ocfs2_extent_rec_contig(
546 ocfs2_metadata_cache_get_super(et
->et_ci
),
550 static inline int ocfs2_et_insert_check(struct ocfs2_extent_tree
*et
,
551 struct ocfs2_extent_rec
*rec
)
555 if (et
->et_ops
->eo_insert_check
)
556 ret
= et
->et_ops
->eo_insert_check(et
, rec
);
560 static inline int ocfs2_et_sanity_check(struct ocfs2_extent_tree
*et
)
564 if (et
->et_ops
->eo_sanity_check
)
565 ret
= et
->et_ops
->eo_sanity_check(et
);
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
);
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
580 void ocfs2_reinit_path(struct ocfs2_path
*path
, int keep_root
)
582 int i
, start
= 0, depth
= 0;
583 struct ocfs2_path_item
*node
;
588 for(i
= start
; i
< path_num_items(path
); i
++) {
589 node
= &path
->p_node
[i
];
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.
602 depth
= le16_to_cpu(path_root_el(path
)->l_tree_depth
);
604 path_root_access(path
) = NULL
;
606 path
->p_tree_depth
= depth
;
609 void ocfs2_free_path(struct ocfs2_path
*path
)
612 ocfs2_reinit_path(path
, 0);
618 * All the elements of src into dest. After this call, src could be freed
619 * without affecting dest.
621 * Both paths should have the same root. Any non-root elements of dest
624 static void ocfs2_cp_path(struct ocfs2_path
*dest
, struct ocfs2_path
*src
)
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
));
632 ocfs2_reinit_path(dest
, 1);
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
;
638 if (dest
->p_node
[i
].bh
)
639 get_bh(dest
->p_node
[i
].bh
);
644 * Make the *dest path the same as src and re-initialize src path to
647 static void ocfs2_mv_path(struct ocfs2_path
*dest
, struct ocfs2_path
*src
)
651 BUG_ON(path_root_bh(dest
) != path_root_bh(src
));
652 BUG_ON(path_root_access(dest
) != path_root_access(src
));
654 for(i
= 1; i
< OCFS2_MAX_PATH_DEPTH
; i
++) {
655 brelse(dest
->p_node
[i
].bh
);
657 dest
->p_node
[i
].bh
= src
->p_node
[i
].bh
;
658 dest
->p_node
[i
].el
= src
->p_node
[i
].el
;
660 src
->p_node
[i
].bh
= NULL
;
661 src
->p_node
[i
].el
= NULL
;
666 * Insert an extent block at given index.
668 * This will not take an additional reference on eb_bh.
670 static inline void ocfs2_path_insert_eb(struct ocfs2_path
*path
, int index
,
671 struct buffer_head
*eb_bh
)
673 struct ocfs2_extent_block
*eb
= (struct ocfs2_extent_block
*)eb_bh
->b_data
;
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.
683 path
->p_node
[index
].bh
= eb_bh
;
684 path
->p_node
[index
].el
= &eb
->h_list
;
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
)
691 struct ocfs2_path
*path
;
693 BUG_ON(le16_to_cpu(root_el
->l_tree_depth
) >= OCFS2_MAX_PATH_DEPTH
);
695 path
= kzalloc(sizeof(*path
), GFP_NOFS
);
697 path
->p_tree_depth
= le16_to_cpu(root_el
->l_tree_depth
);
699 path_root_bh(path
) = root_bh
;
700 path_root_el(path
) = root_el
;
701 path_root_access(path
) = access
;
707 struct ocfs2_path
*ocfs2_new_path_from_path(struct ocfs2_path
*path
)
709 return ocfs2_new_path(path_root_bh(path
), path_root_el(path
),
710 path_root_access(path
));
713 struct ocfs2_path
*ocfs2_new_path_from_et(struct ocfs2_extent_tree
*et
)
715 return ocfs2_new_path(et
->et_root_bh
, et
->et_root_el
,
716 et
->et_root_journal_access
);
720 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
721 * otherwise it's the root_access function.
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.
726 int ocfs2_path_bh_journal_access(handle_t
*handle
,
727 struct ocfs2_caching_info
*ci
,
728 struct ocfs2_path
*path
,
731 ocfs2_journal_access_func access
= path_root_access(path
);
734 access
= ocfs2_journal_access
;
737 access
= ocfs2_journal_access_eb
;
739 return access(handle
, ci
, path
->p_node
[idx
].bh
,
740 OCFS2_JOURNAL_ACCESS_WRITE
);
744 * Convenience function to journal all components in a path.
746 int ocfs2_journal_access_path(struct ocfs2_caching_info
*ci
,
748 struct ocfs2_path
*path
)
755 for(i
= 0; i
< path_num_items(path
); i
++) {
756 ret
= ocfs2_path_bh_journal_access(handle
, ci
, path
, i
);
768 * Return the index of the extent record which contains cluster #v_cluster.
769 * -1 is returned if it was not found.
771 * Should work fine on interior and exterior nodes.
773 int ocfs2_search_extent_list(struct ocfs2_extent_list
*el
, u32 v_cluster
)
777 struct ocfs2_extent_rec
*rec
;
778 u32 rec_end
, rec_start
, clusters
;
780 for(i
= 0; i
< le16_to_cpu(el
->l_next_free_rec
); i
++) {
781 rec
= &el
->l_recs
[i
];
783 rec_start
= le32_to_cpu(rec
->e_cpos
);
784 clusters
= ocfs2_rec_clusters(el
, rec
);
786 rec_end
= rec_start
+ clusters
;
788 if (v_cluster
>= rec_start
&& v_cluster
< rec_end
) {
798 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
799 * ocfs2_extent_rec_contig only work properly against leaf nodes!
801 static int ocfs2_block_extent_contig(struct super_block
*sb
,
802 struct ocfs2_extent_rec
*ext
,
805 u64 blk_end
= le64_to_cpu(ext
->e_blkno
);
807 blk_end
+= ocfs2_clusters_to_blocks(sb
,
808 le16_to_cpu(ext
->e_leaf_clusters
));
810 return blkno
== blk_end
;
813 static int ocfs2_extents_adjacent(struct ocfs2_extent_rec
*left
,
814 struct ocfs2_extent_rec
*right
)
818 left_range
= le32_to_cpu(left
->e_cpos
) +
819 le16_to_cpu(left
->e_leaf_clusters
);
821 return (left_range
== le32_to_cpu(right
->e_cpos
));
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
)
829 u64 blkno
= le64_to_cpu(insert_rec
->e_blkno
);
832 * Refuse to coalesce extent records with different flag
833 * fields - we don't want to mix unwritten extents with user
836 if (ext
->e_flags
!= insert_rec
->e_flags
)
839 if (ocfs2_extents_adjacent(ext
, insert_rec
) &&
840 ocfs2_block_extent_contig(sb
, ext
, blkno
))
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
))
852 * NOTE: We can have pretty much any combination of contiguousness and
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.
858 enum ocfs2_append_type
{
863 enum ocfs2_split_type
{
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
;
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
;
883 static int ocfs2_validate_extent_block(struct super_block
*sb
,
884 struct buffer_head
*bh
)
887 struct ocfs2_extent_block
*eb
=
888 (struct ocfs2_extent_block
*)bh
->b_data
;
890 trace_ocfs2_validate_extent_block((unsigned long long)bh
->b_blocknr
);
892 BUG_ON(!buffer_uptodate(bh
));
895 * If the ecc fails, we return the error but otherwise
896 * leave the filesystem running. We know any error is
897 * local to this block.
899 rc
= ocfs2_validate_meta_ecc(sb
, bh
->b_data
, &eb
->h_check
);
901 mlog(ML_ERROR
, "Checksum failed for extent block %llu\n",
902 (unsigned long long)bh
->b_blocknr
);
907 * Errors after here are fatal.
910 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb
)) {
912 "Extent block #%llu has bad signature %.*s",
913 (unsigned long long)bh
->b_blocknr
, 7,
918 if (le64_to_cpu(eb
->h_blkno
) != bh
->b_blocknr
) {
920 "Extent block #%llu has an invalid h_blkno "
922 (unsigned long long)bh
->b_blocknr
,
923 (unsigned long long)le64_to_cpu(eb
->h_blkno
));
927 if (le32_to_cpu(eb
->h_fs_generation
) != OCFS2_SB(sb
)->fs_generation
) {
929 "Extent block #%llu has an invalid "
930 "h_fs_generation of #%u",
931 (unsigned long long)bh
->b_blocknr
,
932 le32_to_cpu(eb
->h_fs_generation
));
939 int ocfs2_read_extent_block(struct ocfs2_caching_info
*ci
, u64 eb_blkno
,
940 struct buffer_head
**bh
)
943 struct buffer_head
*tmp
= *bh
;
945 rc
= ocfs2_read_block(ci
, eb_blkno
, &tmp
,
946 ocfs2_validate_extent_block
);
948 /* If ocfs2_read_block() got us a new bh, pass it up. */
957 * How many free extents have we got before we need more meta data?
959 int ocfs2_num_free_extents(struct ocfs2_super
*osb
,
960 struct ocfs2_extent_tree
*et
)
963 struct ocfs2_extent_list
*el
= NULL
;
964 struct ocfs2_extent_block
*eb
;
965 struct buffer_head
*eb_bh
= NULL
;
969 last_eb_blk
= ocfs2_et_get_last_eb_blk(et
);
972 retval
= ocfs2_read_extent_block(et
->et_ci
, last_eb_blk
,
978 eb
= (struct ocfs2_extent_block
*) eb_bh
->b_data
;
982 BUG_ON(el
->l_tree_depth
!= 0);
984 retval
= le16_to_cpu(el
->l_count
) - le16_to_cpu(el
->l_next_free_rec
);
988 trace_ocfs2_num_free_extents(retval
);
992 /* expects array to already be allocated
994 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
997 static int ocfs2_create_new_meta_bhs(handle_t
*handle
,
998 struct ocfs2_extent_tree
*et
,
1000 struct ocfs2_alloc_context
*meta_ac
,
1001 struct buffer_head
*bhs
[])
1003 int count
, status
, i
;
1004 u16 suballoc_bit_start
;
1006 u64 suballoc_loc
, first_blkno
;
1007 struct ocfs2_super
*osb
=
1008 OCFS2_SB(ocfs2_metadata_cache_get_super(et
->et_ci
));
1009 struct ocfs2_extent_block
*eb
;
1012 while (count
< wanted
) {
1013 status
= ocfs2_claim_metadata(handle
,
1017 &suballoc_bit_start
,
1025 for(i
= count
; i
< (num_got
+ count
); i
++) {
1026 bhs
[i
] = sb_getblk(osb
->sb
, first_blkno
);
1027 if (bhs
[i
] == NULL
) {
1032 ocfs2_set_new_buffer_uptodate(et
->et_ci
, bhs
[i
]);
1034 status
= ocfs2_journal_access_eb(handle
, et
->et_ci
,
1036 OCFS2_JOURNAL_ACCESS_CREATE
);
1042 memset(bhs
[i
]->b_data
, 0, osb
->sb
->s_blocksize
);
1043 eb
= (struct ocfs2_extent_block
*) bhs
[i
]->b_data
;
1044 /* Ok, setup the minimal stuff here. */
1045 strcpy(eb
->h_signature
, OCFS2_EXTENT_BLOCK_SIGNATURE
);
1046 eb
->h_blkno
= cpu_to_le64(first_blkno
);
1047 eb
->h_fs_generation
= cpu_to_le32(osb
->fs_generation
);
1048 eb
->h_suballoc_slot
=
1049 cpu_to_le16(meta_ac
->ac_alloc_slot
);
1050 eb
->h_suballoc_loc
= cpu_to_le64(suballoc_loc
);
1051 eb
->h_suballoc_bit
= cpu_to_le16(suballoc_bit_start
);
1052 eb
->h_list
.l_count
=
1053 cpu_to_le16(ocfs2_extent_recs_per_eb(osb
->sb
));
1055 suballoc_bit_start
++;
1058 /* We'll also be dirtied by the caller, so
1059 * this isn't absolutely necessary. */
1060 ocfs2_journal_dirty(handle
, bhs
[i
]);
1069 for(i
= 0; i
< wanted
; i
++) {
1079 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1081 * Returns the sum of the rightmost extent rec logical offset and
1084 * ocfs2_add_branch() uses this to determine what logical cluster
1085 * value should be populated into the leftmost new branch records.
1087 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1088 * value for the new topmost tree record.
1090 static inline u32
ocfs2_sum_rightmost_rec(struct ocfs2_extent_list
*el
)
1094 i
= le16_to_cpu(el
->l_next_free_rec
) - 1;
1096 return le32_to_cpu(el
->l_recs
[i
].e_cpos
) +
1097 ocfs2_rec_clusters(el
, &el
->l_recs
[i
]);
1101 * Change range of the branches in the right most path according to the leaf
1102 * extent block's rightmost record.
1104 static int ocfs2_adjust_rightmost_branch(handle_t
*handle
,
1105 struct ocfs2_extent_tree
*et
)
1108 struct ocfs2_path
*path
= NULL
;
1109 struct ocfs2_extent_list
*el
;
1110 struct ocfs2_extent_rec
*rec
;
1112 path
= ocfs2_new_path_from_et(et
);
1118 status
= ocfs2_find_path(et
->et_ci
, path
, UINT_MAX
);
1124 status
= ocfs2_extend_trans(handle
, path_num_items(path
));
1130 status
= ocfs2_journal_access_path(et
->et_ci
, handle
, path
);
1136 el
= path_leaf_el(path
);
1137 rec
= &el
->l_recs
[le16_to_cpu(el
->l_next_free_rec
) - 1];
1139 ocfs2_adjust_rightmost_records(handle
, et
, path
, rec
);
1142 ocfs2_free_path(path
);
1147 * Add an entire tree branch to our inode. eb_bh is the extent block
1148 * to start at, if we don't want to start the branch at the root
1151 * last_eb_bh is required as we have to update it's next_leaf pointer
1152 * for the new last extent block.
1154 * the new branch will be 'empty' in the sense that every block will
1155 * contain a single record with cluster count == 0.
1157 static int ocfs2_add_branch(handle_t
*handle
,
1158 struct ocfs2_extent_tree
*et
,
1159 struct buffer_head
*eb_bh
,
1160 struct buffer_head
**last_eb_bh
,
1161 struct ocfs2_alloc_context
*meta_ac
)
1163 int status
, new_blocks
, i
;
1164 u64 next_blkno
, new_last_eb_blk
;
1165 struct buffer_head
*bh
;
1166 struct buffer_head
**new_eb_bhs
= NULL
;
1167 struct ocfs2_extent_block
*eb
;
1168 struct ocfs2_extent_list
*eb_el
;
1169 struct ocfs2_extent_list
*el
;
1170 u32 new_cpos
, root_end
;
1172 BUG_ON(!last_eb_bh
|| !*last_eb_bh
);
1175 eb
= (struct ocfs2_extent_block
*) eb_bh
->b_data
;
1178 el
= et
->et_root_el
;
1180 /* we never add a branch to a leaf. */
1181 BUG_ON(!el
->l_tree_depth
);
1183 new_blocks
= le16_to_cpu(el
->l_tree_depth
);
1185 eb
= (struct ocfs2_extent_block
*)(*last_eb_bh
)->b_data
;
1186 new_cpos
= ocfs2_sum_rightmost_rec(&eb
->h_list
);
1187 root_end
= ocfs2_sum_rightmost_rec(et
->et_root_el
);
1190 * If there is a gap before the root end and the real end
1191 * of the righmost leaf block, we need to remove the gap
1192 * between new_cpos and root_end first so that the tree
1193 * is consistent after we add a new branch(it will start
1196 if (root_end
> new_cpos
) {
1197 trace_ocfs2_adjust_rightmost_branch(
1198 (unsigned long long)
1199 ocfs2_metadata_cache_owner(et
->et_ci
),
1200 root_end
, new_cpos
);
1202 status
= ocfs2_adjust_rightmost_branch(handle
, et
);
1209 /* allocate the number of new eb blocks we need */
1210 new_eb_bhs
= kcalloc(new_blocks
, sizeof(struct buffer_head
*),
1218 status
= ocfs2_create_new_meta_bhs(handle
, et
, new_blocks
,
1219 meta_ac
, new_eb_bhs
);
1225 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1226 * linked with the rest of the tree.
1227 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1229 * when we leave the loop, new_last_eb_blk will point to the
1230 * newest leaf, and next_blkno will point to the topmost extent
1232 next_blkno
= new_last_eb_blk
= 0;
1233 for(i
= 0; i
< new_blocks
; i
++) {
1235 eb
= (struct ocfs2_extent_block
*) bh
->b_data
;
1236 /* ocfs2_create_new_meta_bhs() should create it right! */
1237 BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb
));
1238 eb_el
= &eb
->h_list
;
1240 status
= ocfs2_journal_access_eb(handle
, et
->et_ci
, bh
,
1241 OCFS2_JOURNAL_ACCESS_CREATE
);
1247 eb
->h_next_leaf_blk
= 0;
1248 eb_el
->l_tree_depth
= cpu_to_le16(i
);
1249 eb_el
->l_next_free_rec
= cpu_to_le16(1);
1251 * This actually counts as an empty extent as
1254 eb_el
->l_recs
[0].e_cpos
= cpu_to_le32(new_cpos
);
1255 eb_el
->l_recs
[0].e_blkno
= cpu_to_le64(next_blkno
);
1257 * eb_el isn't always an interior node, but even leaf
1258 * nodes want a zero'd flags and reserved field so
1259 * this gets the whole 32 bits regardless of use.
1261 eb_el
->l_recs
[0].e_int_clusters
= cpu_to_le32(0);
1262 if (!eb_el
->l_tree_depth
)
1263 new_last_eb_blk
= le64_to_cpu(eb
->h_blkno
);
1265 ocfs2_journal_dirty(handle
, bh
);
1266 next_blkno
= le64_to_cpu(eb
->h_blkno
);
1269 /* This is a bit hairy. We want to update up to three blocks
1270 * here without leaving any of them in an inconsistent state
1271 * in case of error. We don't have to worry about
1272 * journal_dirty erroring as it won't unless we've aborted the
1273 * handle (in which case we would never be here) so reserving
1274 * the write with journal_access is all we need to do. */
1275 status
= ocfs2_journal_access_eb(handle
, et
->et_ci
, *last_eb_bh
,
1276 OCFS2_JOURNAL_ACCESS_WRITE
);
1281 status
= ocfs2_et_root_journal_access(handle
, et
,
1282 OCFS2_JOURNAL_ACCESS_WRITE
);
1288 status
= ocfs2_journal_access_eb(handle
, et
->et_ci
, eb_bh
,
1289 OCFS2_JOURNAL_ACCESS_WRITE
);
1296 /* Link the new branch into the rest of the tree (el will
1297 * either be on the root_bh, or the extent block passed in. */
1298 i
= le16_to_cpu(el
->l_next_free_rec
);
1299 el
->l_recs
[i
].e_blkno
= cpu_to_le64(next_blkno
);
1300 el
->l_recs
[i
].e_cpos
= cpu_to_le32(new_cpos
);
1301 el
->l_recs
[i
].e_int_clusters
= 0;
1302 le16_add_cpu(&el
->l_next_free_rec
, 1);
1304 /* fe needs a new last extent block pointer, as does the
1305 * next_leaf on the previously last-extent-block. */
1306 ocfs2_et_set_last_eb_blk(et
, new_last_eb_blk
);
1308 eb
= (struct ocfs2_extent_block
*) (*last_eb_bh
)->b_data
;
1309 eb
->h_next_leaf_blk
= cpu_to_le64(new_last_eb_blk
);
1311 ocfs2_journal_dirty(handle
, *last_eb_bh
);
1312 ocfs2_journal_dirty(handle
, et
->et_root_bh
);
1314 ocfs2_journal_dirty(handle
, eb_bh
);
1317 * Some callers want to track the rightmost leaf so pass it
1320 brelse(*last_eb_bh
);
1321 get_bh(new_eb_bhs
[0]);
1322 *last_eb_bh
= new_eb_bhs
[0];
1327 for (i
= 0; i
< new_blocks
; i
++)
1328 brelse(new_eb_bhs
[i
]);
1336 * adds another level to the allocation tree.
1337 * returns back the new extent block so you can add a branch to it
1340 static int ocfs2_shift_tree_depth(handle_t
*handle
,
1341 struct ocfs2_extent_tree
*et
,
1342 struct ocfs2_alloc_context
*meta_ac
,
1343 struct buffer_head
**ret_new_eb_bh
)
1347 struct buffer_head
*new_eb_bh
= NULL
;
1348 struct ocfs2_extent_block
*eb
;
1349 struct ocfs2_extent_list
*root_el
;
1350 struct ocfs2_extent_list
*eb_el
;
1352 status
= ocfs2_create_new_meta_bhs(handle
, et
, 1, meta_ac
,
1359 eb
= (struct ocfs2_extent_block
*) new_eb_bh
->b_data
;
1360 /* ocfs2_create_new_meta_bhs() should create it right! */
1361 BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb
));
1363 eb_el
= &eb
->h_list
;
1364 root_el
= et
->et_root_el
;
1366 status
= ocfs2_journal_access_eb(handle
, et
->et_ci
, new_eb_bh
,
1367 OCFS2_JOURNAL_ACCESS_CREATE
);
1373 /* copy the root extent list data into the new extent block */
1374 eb_el
->l_tree_depth
= root_el
->l_tree_depth
;
1375 eb_el
->l_next_free_rec
= root_el
->l_next_free_rec
;
1376 for (i
= 0; i
< le16_to_cpu(root_el
->l_next_free_rec
); i
++)
1377 eb_el
->l_recs
[i
] = root_el
->l_recs
[i
];
1379 ocfs2_journal_dirty(handle
, new_eb_bh
);
1381 status
= ocfs2_et_root_journal_access(handle
, et
,
1382 OCFS2_JOURNAL_ACCESS_WRITE
);
1388 new_clusters
= ocfs2_sum_rightmost_rec(eb_el
);
1390 /* update root_bh now */
1391 le16_add_cpu(&root_el
->l_tree_depth
, 1);
1392 root_el
->l_recs
[0].e_cpos
= 0;
1393 root_el
->l_recs
[0].e_blkno
= eb
->h_blkno
;
1394 root_el
->l_recs
[0].e_int_clusters
= cpu_to_le32(new_clusters
);
1395 for (i
= 1; i
< le16_to_cpu(root_el
->l_next_free_rec
); i
++)
1396 memset(&root_el
->l_recs
[i
], 0, sizeof(struct ocfs2_extent_rec
));
1397 root_el
->l_next_free_rec
= cpu_to_le16(1);
1399 /* If this is our 1st tree depth shift, then last_eb_blk
1400 * becomes the allocated extent block */
1401 if (root_el
->l_tree_depth
== cpu_to_le16(1))
1402 ocfs2_et_set_last_eb_blk(et
, le64_to_cpu(eb
->h_blkno
));
1404 ocfs2_journal_dirty(handle
, et
->et_root_bh
);
1406 *ret_new_eb_bh
= new_eb_bh
;
1416 * Should only be called when there is no space left in any of the
1417 * leaf nodes. What we want to do is find the lowest tree depth
1418 * non-leaf extent block with room for new records. There are three
1419 * valid results of this search:
1421 * 1) a lowest extent block is found, then we pass it back in
1422 * *lowest_eb_bh and return '0'
1424 * 2) the search fails to find anything, but the root_el has room. We
1425 * pass NULL back in *lowest_eb_bh, but still return '0'
1427 * 3) the search fails to find anything AND the root_el is full, in
1428 * which case we return > 0
1430 * return status < 0 indicates an error.
1432 static int ocfs2_find_branch_target(struct ocfs2_extent_tree
*et
,
1433 struct buffer_head
**target_bh
)
1437 struct ocfs2_extent_block
*eb
;
1438 struct ocfs2_extent_list
*el
;
1439 struct buffer_head
*bh
= NULL
;
1440 struct buffer_head
*lowest_bh
= NULL
;
1444 el
= et
->et_root_el
;
1446 while(le16_to_cpu(el
->l_tree_depth
) > 1) {
1447 if (le16_to_cpu(el
->l_next_free_rec
) == 0) {
1448 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
1449 "Owner %llu has empty "
1450 "extent list (next_free_rec == 0)",
1451 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
));
1455 i
= le16_to_cpu(el
->l_next_free_rec
) - 1;
1456 blkno
= le64_to_cpu(el
->l_recs
[i
].e_blkno
);
1458 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
1459 "Owner %llu has extent "
1460 "list where extent # %d has no physical "
1462 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
), i
);
1470 status
= ocfs2_read_extent_block(et
->et_ci
, blkno
, &bh
);
1476 eb
= (struct ocfs2_extent_block
*) bh
->b_data
;
1479 if (le16_to_cpu(el
->l_next_free_rec
) <
1480 le16_to_cpu(el
->l_count
)) {
1487 /* If we didn't find one and the fe doesn't have any room,
1488 * then return '1' */
1489 el
= et
->et_root_el
;
1490 if (!lowest_bh
&& (el
->l_next_free_rec
== el
->l_count
))
1493 *target_bh
= lowest_bh
;
1501 * Grow a b-tree so that it has more records.
1503 * We might shift the tree depth in which case existing paths should
1504 * be considered invalid.
1506 * Tree depth after the grow is returned via *final_depth.
1508 * *last_eb_bh will be updated by ocfs2_add_branch().
1510 static int ocfs2_grow_tree(handle_t
*handle
, struct ocfs2_extent_tree
*et
,
1511 int *final_depth
, struct buffer_head
**last_eb_bh
,
1512 struct ocfs2_alloc_context
*meta_ac
)
1515 struct ocfs2_extent_list
*el
= et
->et_root_el
;
1516 int depth
= le16_to_cpu(el
->l_tree_depth
);
1517 struct buffer_head
*bh
= NULL
;
1519 BUG_ON(meta_ac
== NULL
);
1521 shift
= ocfs2_find_branch_target(et
, &bh
);
1528 /* We traveled all the way to the bottom of the allocation tree
1529 * and didn't find room for any more extents - we need to add
1530 * another tree level */
1533 trace_ocfs2_grow_tree(
1534 (unsigned long long)
1535 ocfs2_metadata_cache_owner(et
->et_ci
),
1538 /* ocfs2_shift_tree_depth will return us a buffer with
1539 * the new extent block (so we can pass that to
1540 * ocfs2_add_branch). */
1541 ret
= ocfs2_shift_tree_depth(handle
, et
, meta_ac
, &bh
);
1549 * Special case: we have room now if we shifted from
1550 * tree_depth 0, so no more work needs to be done.
1552 * We won't be calling add_branch, so pass
1553 * back *last_eb_bh as the new leaf. At depth
1554 * zero, it should always be null so there's
1555 * no reason to brelse.
1557 BUG_ON(*last_eb_bh
);
1564 /* call ocfs2_add_branch to add the final part of the tree with
1566 ret
= ocfs2_add_branch(handle
, et
, bh
, last_eb_bh
,
1575 *final_depth
= depth
;
1581 * This function will discard the rightmost extent record.
1583 static void ocfs2_shift_records_right(struct ocfs2_extent_list
*el
)
1585 int next_free
= le16_to_cpu(el
->l_next_free_rec
);
1586 int count
= le16_to_cpu(el
->l_count
);
1587 unsigned int num_bytes
;
1590 /* This will cause us to go off the end of our extent list. */
1591 BUG_ON(next_free
>= count
);
1593 num_bytes
= sizeof(struct ocfs2_extent_rec
) * next_free
;
1595 memmove(&el
->l_recs
[1], &el
->l_recs
[0], num_bytes
);
1598 static void ocfs2_rotate_leaf(struct ocfs2_extent_list
*el
,
1599 struct ocfs2_extent_rec
*insert_rec
)
1601 int i
, insert_index
, next_free
, has_empty
, num_bytes
;
1602 u32 insert_cpos
= le32_to_cpu(insert_rec
->e_cpos
);
1603 struct ocfs2_extent_rec
*rec
;
1605 next_free
= le16_to_cpu(el
->l_next_free_rec
);
1606 has_empty
= ocfs2_is_empty_extent(&el
->l_recs
[0]);
1610 /* The tree code before us didn't allow enough room in the leaf. */
1611 BUG_ON(el
->l_next_free_rec
== el
->l_count
&& !has_empty
);
1614 * The easiest way to approach this is to just remove the
1615 * empty extent and temporarily decrement next_free.
1619 * If next_free was 1 (only an empty extent), this
1620 * loop won't execute, which is fine. We still want
1621 * the decrement above to happen.
1623 for(i
= 0; i
< (next_free
- 1); i
++)
1624 el
->l_recs
[i
] = el
->l_recs
[i
+1];
1630 * Figure out what the new record index should be.
1632 for(i
= 0; i
< next_free
; i
++) {
1633 rec
= &el
->l_recs
[i
];
1635 if (insert_cpos
< le32_to_cpu(rec
->e_cpos
))
1640 trace_ocfs2_rotate_leaf(insert_cpos
, insert_index
,
1641 has_empty
, next_free
,
1642 le16_to_cpu(el
->l_count
));
1644 BUG_ON(insert_index
< 0);
1645 BUG_ON(insert_index
>= le16_to_cpu(el
->l_count
));
1646 BUG_ON(insert_index
> next_free
);
1649 * No need to memmove if we're just adding to the tail.
1651 if (insert_index
!= next_free
) {
1652 BUG_ON(next_free
>= le16_to_cpu(el
->l_count
));
1654 num_bytes
= next_free
- insert_index
;
1655 num_bytes
*= sizeof(struct ocfs2_extent_rec
);
1656 memmove(&el
->l_recs
[insert_index
+ 1],
1657 &el
->l_recs
[insert_index
],
1662 * Either we had an empty extent, and need to re-increment or
1663 * there was no empty extent on a non full rightmost leaf node,
1664 * in which case we still need to increment.
1667 el
->l_next_free_rec
= cpu_to_le16(next_free
);
1669 * Make sure none of the math above just messed up our tree.
1671 BUG_ON(le16_to_cpu(el
->l_next_free_rec
) > le16_to_cpu(el
->l_count
));
1673 el
->l_recs
[insert_index
] = *insert_rec
;
1677 static void ocfs2_remove_empty_extent(struct ocfs2_extent_list
*el
)
1679 int size
, num_recs
= le16_to_cpu(el
->l_next_free_rec
);
1681 BUG_ON(num_recs
== 0);
1683 if (ocfs2_is_empty_extent(&el
->l_recs
[0])) {
1685 size
= num_recs
* sizeof(struct ocfs2_extent_rec
);
1686 memmove(&el
->l_recs
[0], &el
->l_recs
[1], size
);
1687 memset(&el
->l_recs
[num_recs
], 0,
1688 sizeof(struct ocfs2_extent_rec
));
1689 el
->l_next_free_rec
= cpu_to_le16(num_recs
);
1694 * Create an empty extent record .
1696 * l_next_free_rec may be updated.
1698 * If an empty extent already exists do nothing.
1700 static void ocfs2_create_empty_extent(struct ocfs2_extent_list
*el
)
1702 int next_free
= le16_to_cpu(el
->l_next_free_rec
);
1704 BUG_ON(le16_to_cpu(el
->l_tree_depth
) != 0);
1709 if (ocfs2_is_empty_extent(&el
->l_recs
[0]))
1712 mlog_bug_on_msg(el
->l_count
== el
->l_next_free_rec
,
1713 "Asked to create an empty extent in a full list:\n"
1714 "count = %u, tree depth = %u",
1715 le16_to_cpu(el
->l_count
),
1716 le16_to_cpu(el
->l_tree_depth
));
1718 ocfs2_shift_records_right(el
);
1721 le16_add_cpu(&el
->l_next_free_rec
, 1);
1722 memset(&el
->l_recs
[0], 0, sizeof(struct ocfs2_extent_rec
));
1726 * For a rotation which involves two leaf nodes, the "root node" is
1727 * the lowest level tree node which contains a path to both leafs. This
1728 * resulting set of information can be used to form a complete "subtree"
1730 * This function is passed two full paths from the dinode down to a
1731 * pair of adjacent leaves. It's task is to figure out which path
1732 * index contains the subtree root - this can be the root index itself
1733 * in a worst-case rotation.
1735 * The array index of the subtree root is passed back.
1737 int ocfs2_find_subtree_root(struct ocfs2_extent_tree
*et
,
1738 struct ocfs2_path
*left
,
1739 struct ocfs2_path
*right
)
1744 * Check that the caller passed in two paths from the same tree.
1746 BUG_ON(path_root_bh(left
) != path_root_bh(right
));
1752 * The caller didn't pass two adjacent paths.
1754 mlog_bug_on_msg(i
> left
->p_tree_depth
,
1755 "Owner %llu, left depth %u, right depth %u\n"
1756 "left leaf blk %llu, right leaf blk %llu\n",
1757 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
1758 left
->p_tree_depth
, right
->p_tree_depth
,
1759 (unsigned long long)path_leaf_bh(left
)->b_blocknr
,
1760 (unsigned long long)path_leaf_bh(right
)->b_blocknr
);
1761 } while (left
->p_node
[i
].bh
->b_blocknr
==
1762 right
->p_node
[i
].bh
->b_blocknr
);
1767 typedef void (path_insert_t
)(void *, struct buffer_head
*);
1770 * Traverse a btree path in search of cpos, starting at root_el.
1772 * This code can be called with a cpos larger than the tree, in which
1773 * case it will return the rightmost path.
1775 static int __ocfs2_find_path(struct ocfs2_caching_info
*ci
,
1776 struct ocfs2_extent_list
*root_el
, u32 cpos
,
1777 path_insert_t
*func
, void *data
)
1782 struct buffer_head
*bh
= NULL
;
1783 struct ocfs2_extent_block
*eb
;
1784 struct ocfs2_extent_list
*el
;
1785 struct ocfs2_extent_rec
*rec
;
1788 while (el
->l_tree_depth
) {
1789 if (le16_to_cpu(el
->l_next_free_rec
) == 0) {
1790 ocfs2_error(ocfs2_metadata_cache_get_super(ci
),
1791 "Owner %llu has empty extent list at "
1793 (unsigned long long)ocfs2_metadata_cache_owner(ci
),
1794 le16_to_cpu(el
->l_tree_depth
));
1800 for(i
= 0; i
< le16_to_cpu(el
->l_next_free_rec
) - 1; i
++) {
1801 rec
= &el
->l_recs
[i
];
1804 * In the case that cpos is off the allocation
1805 * tree, this should just wind up returning the
1808 range
= le32_to_cpu(rec
->e_cpos
) +
1809 ocfs2_rec_clusters(el
, rec
);
1810 if (cpos
>= le32_to_cpu(rec
->e_cpos
) && cpos
< range
)
1814 blkno
= le64_to_cpu(el
->l_recs
[i
].e_blkno
);
1816 ocfs2_error(ocfs2_metadata_cache_get_super(ci
),
1817 "Owner %llu has bad blkno in extent list "
1818 "at depth %u (index %d)\n",
1819 (unsigned long long)ocfs2_metadata_cache_owner(ci
),
1820 le16_to_cpu(el
->l_tree_depth
), i
);
1827 ret
= ocfs2_read_extent_block(ci
, blkno
, &bh
);
1833 eb
= (struct ocfs2_extent_block
*) bh
->b_data
;
1836 if (le16_to_cpu(el
->l_next_free_rec
) >
1837 le16_to_cpu(el
->l_count
)) {
1838 ocfs2_error(ocfs2_metadata_cache_get_super(ci
),
1839 "Owner %llu has bad count in extent list "
1840 "at block %llu (next free=%u, count=%u)\n",
1841 (unsigned long long)ocfs2_metadata_cache_owner(ci
),
1842 (unsigned long long)bh
->b_blocknr
,
1843 le16_to_cpu(el
->l_next_free_rec
),
1844 le16_to_cpu(el
->l_count
));
1855 * Catch any trailing bh that the loop didn't handle.
1863 * Given an initialized path (that is, it has a valid root extent
1864 * list), this function will traverse the btree in search of the path
1865 * which would contain cpos.
1867 * The path traveled is recorded in the path structure.
1869 * Note that this will not do any comparisons on leaf node extent
1870 * records, so it will work fine in the case that we just added a tree
1873 struct find_path_data
{
1875 struct ocfs2_path
*path
;
1877 static void find_path_ins(void *data
, struct buffer_head
*bh
)
1879 struct find_path_data
*fp
= data
;
1882 ocfs2_path_insert_eb(fp
->path
, fp
->index
, bh
);
1885 int ocfs2_find_path(struct ocfs2_caching_info
*ci
,
1886 struct ocfs2_path
*path
, u32 cpos
)
1888 struct find_path_data data
;
1892 return __ocfs2_find_path(ci
, path_root_el(path
), cpos
,
1893 find_path_ins
, &data
);
1896 static void find_leaf_ins(void *data
, struct buffer_head
*bh
)
1898 struct ocfs2_extent_block
*eb
=(struct ocfs2_extent_block
*)bh
->b_data
;
1899 struct ocfs2_extent_list
*el
= &eb
->h_list
;
1900 struct buffer_head
**ret
= data
;
1902 /* We want to retain only the leaf block. */
1903 if (le16_to_cpu(el
->l_tree_depth
) == 0) {
1909 * Find the leaf block in the tree which would contain cpos. No
1910 * checking of the actual leaf is done.
1912 * Some paths want to call this instead of allocating a path structure
1913 * and calling ocfs2_find_path().
1915 * This function doesn't handle non btree extent lists.
1917 int ocfs2_find_leaf(struct ocfs2_caching_info
*ci
,
1918 struct ocfs2_extent_list
*root_el
, u32 cpos
,
1919 struct buffer_head
**leaf_bh
)
1922 struct buffer_head
*bh
= NULL
;
1924 ret
= __ocfs2_find_path(ci
, root_el
, cpos
, find_leaf_ins
, &bh
);
1936 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1938 * Basically, we've moved stuff around at the bottom of the tree and
1939 * we need to fix up the extent records above the changes to reflect
1942 * left_rec: the record on the left.
1943 * left_child_el: is the child list pointed to by left_rec
1944 * right_rec: the record to the right of left_rec
1945 * right_child_el: is the child list pointed to by right_rec
1947 * By definition, this only works on interior nodes.
1949 static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec
*left_rec
,
1950 struct ocfs2_extent_list
*left_child_el
,
1951 struct ocfs2_extent_rec
*right_rec
,
1952 struct ocfs2_extent_list
*right_child_el
)
1954 u32 left_clusters
, right_end
;
1957 * Interior nodes never have holes. Their cpos is the cpos of
1958 * the leftmost record in their child list. Their cluster
1959 * count covers the full theoretical range of their child list
1960 * - the range between their cpos and the cpos of the record
1961 * immediately to their right.
1963 left_clusters
= le32_to_cpu(right_child_el
->l_recs
[0].e_cpos
);
1964 if (!ocfs2_rec_clusters(right_child_el
, &right_child_el
->l_recs
[0])) {
1965 BUG_ON(right_child_el
->l_tree_depth
);
1966 BUG_ON(le16_to_cpu(right_child_el
->l_next_free_rec
) <= 1);
1967 left_clusters
= le32_to_cpu(right_child_el
->l_recs
[1].e_cpos
);
1969 left_clusters
-= le32_to_cpu(left_rec
->e_cpos
);
1970 left_rec
->e_int_clusters
= cpu_to_le32(left_clusters
);
1973 * Calculate the rightmost cluster count boundary before
1974 * moving cpos - we will need to adjust clusters after
1975 * updating e_cpos to keep the same highest cluster count.
1977 right_end
= le32_to_cpu(right_rec
->e_cpos
);
1978 right_end
+= le32_to_cpu(right_rec
->e_int_clusters
);
1980 right_rec
->e_cpos
= left_rec
->e_cpos
;
1981 le32_add_cpu(&right_rec
->e_cpos
, left_clusters
);
1983 right_end
-= le32_to_cpu(right_rec
->e_cpos
);
1984 right_rec
->e_int_clusters
= cpu_to_le32(right_end
);
1988 * Adjust the adjacent root node records involved in a
1989 * rotation. left_el_blkno is passed in as a key so that we can easily
1990 * find it's index in the root list.
1992 static void ocfs2_adjust_root_records(struct ocfs2_extent_list
*root_el
,
1993 struct ocfs2_extent_list
*left_el
,
1994 struct ocfs2_extent_list
*right_el
,
1999 BUG_ON(le16_to_cpu(root_el
->l_tree_depth
) <=
2000 le16_to_cpu(left_el
->l_tree_depth
));
2002 for(i
= 0; i
< le16_to_cpu(root_el
->l_next_free_rec
) - 1; i
++) {
2003 if (le64_to_cpu(root_el
->l_recs
[i
].e_blkno
) == left_el_blkno
)
2008 * The path walking code should have never returned a root and
2009 * two paths which are not adjacent.
2011 BUG_ON(i
>= (le16_to_cpu(root_el
->l_next_free_rec
) - 1));
2013 ocfs2_adjust_adjacent_records(&root_el
->l_recs
[i
], left_el
,
2014 &root_el
->l_recs
[i
+ 1], right_el
);
2018 * We've changed a leaf block (in right_path) and need to reflect that
2019 * change back up the subtree.
2021 * This happens in multiple places:
2022 * - When we've moved an extent record from the left path leaf to the right
2023 * path leaf to make room for an empty extent in the left path leaf.
2024 * - When our insert into the right path leaf is at the leftmost edge
2025 * and requires an update of the path immediately to it's left. This
2026 * can occur at the end of some types of rotation and appending inserts.
2027 * - When we've adjusted the last extent record in the left path leaf and the
2028 * 1st extent record in the right path leaf during cross extent block merge.
2030 static void ocfs2_complete_edge_insert(handle_t
*handle
,
2031 struct ocfs2_path
*left_path
,
2032 struct ocfs2_path
*right_path
,
2036 struct ocfs2_extent_list
*el
, *left_el
, *right_el
;
2037 struct ocfs2_extent_rec
*left_rec
, *right_rec
;
2038 struct buffer_head
*root_bh
= left_path
->p_node
[subtree_index
].bh
;
2041 * Update the counts and position values within all the
2042 * interior nodes to reflect the leaf rotation we just did.
2044 * The root node is handled below the loop.
2046 * We begin the loop with right_el and left_el pointing to the
2047 * leaf lists and work our way up.
2049 * NOTE: within this loop, left_el and right_el always refer
2050 * to the *child* lists.
2052 left_el
= path_leaf_el(left_path
);
2053 right_el
= path_leaf_el(right_path
);
2054 for(i
= left_path
->p_tree_depth
- 1; i
> subtree_index
; i
--) {
2055 trace_ocfs2_complete_edge_insert(i
);
2058 * One nice property of knowing that all of these
2059 * nodes are below the root is that we only deal with
2060 * the leftmost right node record and the rightmost
2063 el
= left_path
->p_node
[i
].el
;
2064 idx
= le16_to_cpu(left_el
->l_next_free_rec
) - 1;
2065 left_rec
= &el
->l_recs
[idx
];
2067 el
= right_path
->p_node
[i
].el
;
2068 right_rec
= &el
->l_recs
[0];
2070 ocfs2_adjust_adjacent_records(left_rec
, left_el
, right_rec
,
2073 ocfs2_journal_dirty(handle
, left_path
->p_node
[i
].bh
);
2074 ocfs2_journal_dirty(handle
, right_path
->p_node
[i
].bh
);
2077 * Setup our list pointers now so that the current
2078 * parents become children in the next iteration.
2080 left_el
= left_path
->p_node
[i
].el
;
2081 right_el
= right_path
->p_node
[i
].el
;
2085 * At the root node, adjust the two adjacent records which
2086 * begin our path to the leaves.
2089 el
= left_path
->p_node
[subtree_index
].el
;
2090 left_el
= left_path
->p_node
[subtree_index
+ 1].el
;
2091 right_el
= right_path
->p_node
[subtree_index
+ 1].el
;
2093 ocfs2_adjust_root_records(el
, left_el
, right_el
,
2094 left_path
->p_node
[subtree_index
+ 1].bh
->b_blocknr
);
2096 root_bh
= left_path
->p_node
[subtree_index
].bh
;
2098 ocfs2_journal_dirty(handle
, root_bh
);
2101 static int ocfs2_rotate_subtree_right(handle_t
*handle
,
2102 struct ocfs2_extent_tree
*et
,
2103 struct ocfs2_path
*left_path
,
2104 struct ocfs2_path
*right_path
,
2108 struct buffer_head
*right_leaf_bh
;
2109 struct buffer_head
*left_leaf_bh
= NULL
;
2110 struct buffer_head
*root_bh
;
2111 struct ocfs2_extent_list
*right_el
, *left_el
;
2112 struct ocfs2_extent_rec move_rec
;
2114 left_leaf_bh
= path_leaf_bh(left_path
);
2115 left_el
= path_leaf_el(left_path
);
2117 if (left_el
->l_next_free_rec
!= left_el
->l_count
) {
2118 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
2119 "Inode %llu has non-full interior leaf node %llu"
2121 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
2122 (unsigned long long)left_leaf_bh
->b_blocknr
,
2123 le16_to_cpu(left_el
->l_next_free_rec
));
2128 * This extent block may already have an empty record, so we
2129 * return early if so.
2131 if (ocfs2_is_empty_extent(&left_el
->l_recs
[0]))
2134 root_bh
= left_path
->p_node
[subtree_index
].bh
;
2135 BUG_ON(root_bh
!= right_path
->p_node
[subtree_index
].bh
);
2137 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, right_path
,
2144 for(i
= subtree_index
+ 1; i
< path_num_items(right_path
); i
++) {
2145 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
2152 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
2160 right_leaf_bh
= path_leaf_bh(right_path
);
2161 right_el
= path_leaf_el(right_path
);
2163 /* This is a code error, not a disk corruption. */
2164 mlog_bug_on_msg(!right_el
->l_next_free_rec
, "Inode %llu: Rotate fails "
2165 "because rightmost leaf block %llu is empty\n",
2166 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
2167 (unsigned long long)right_leaf_bh
->b_blocknr
);
2169 ocfs2_create_empty_extent(right_el
);
2171 ocfs2_journal_dirty(handle
, right_leaf_bh
);
2173 /* Do the copy now. */
2174 i
= le16_to_cpu(left_el
->l_next_free_rec
) - 1;
2175 move_rec
= left_el
->l_recs
[i
];
2176 right_el
->l_recs
[0] = move_rec
;
2179 * Clear out the record we just copied and shift everything
2180 * over, leaving an empty extent in the left leaf.
2182 * We temporarily subtract from next_free_rec so that the
2183 * shift will lose the tail record (which is now defunct).
2185 le16_add_cpu(&left_el
->l_next_free_rec
, -1);
2186 ocfs2_shift_records_right(left_el
);
2187 memset(&left_el
->l_recs
[0], 0, sizeof(struct ocfs2_extent_rec
));
2188 le16_add_cpu(&left_el
->l_next_free_rec
, 1);
2190 ocfs2_journal_dirty(handle
, left_leaf_bh
);
2192 ocfs2_complete_edge_insert(handle
, left_path
, right_path
,
2200 * Given a full path, determine what cpos value would return us a path
2201 * containing the leaf immediately to the left of the current one.
2203 * Will return zero if the path passed in is already the leftmost path.
2205 int ocfs2_find_cpos_for_left_leaf(struct super_block
*sb
,
2206 struct ocfs2_path
*path
, u32
*cpos
)
2210 struct ocfs2_extent_list
*el
;
2212 BUG_ON(path
->p_tree_depth
== 0);
2216 blkno
= path_leaf_bh(path
)->b_blocknr
;
2218 /* Start at the tree node just above the leaf and work our way up. */
2219 i
= path
->p_tree_depth
- 1;
2221 el
= path
->p_node
[i
].el
;
2224 * Find the extent record just before the one in our
2227 for(j
= 0; j
< le16_to_cpu(el
->l_next_free_rec
); j
++) {
2228 if (le64_to_cpu(el
->l_recs
[j
].e_blkno
) == blkno
) {
2232 * We've determined that the
2233 * path specified is already
2234 * the leftmost one - return a
2240 * The leftmost record points to our
2241 * leaf - we need to travel up the
2247 *cpos
= le32_to_cpu(el
->l_recs
[j
- 1].e_cpos
);
2248 *cpos
= *cpos
+ ocfs2_rec_clusters(el
,
2249 &el
->l_recs
[j
- 1]);
2256 * If we got here, we never found a valid node where
2257 * the tree indicated one should be.
2260 "Invalid extent tree at extent block %llu\n",
2261 (unsigned long long)blkno
);
2266 blkno
= path
->p_node
[i
].bh
->b_blocknr
;
2275 * Extend the transaction by enough credits to complete the rotation,
2276 * and still leave at least the original number of credits allocated
2277 * to this transaction.
2279 static int ocfs2_extend_rotate_transaction(handle_t
*handle
, int subtree_depth
,
2281 struct ocfs2_path
*path
)
2284 int credits
= (path
->p_tree_depth
- subtree_depth
) * 2 + 1 + op_credits
;
2286 if (handle
->h_buffer_credits
< credits
)
2287 ret
= ocfs2_extend_trans(handle
,
2288 credits
- handle
->h_buffer_credits
);
2294 * Trap the case where we're inserting into the theoretical range past
2295 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2296 * whose cpos is less than ours into the right leaf.
2298 * It's only necessary to look at the rightmost record of the left
2299 * leaf because the logic that calls us should ensure that the
2300 * theoretical ranges in the path components above the leaves are
2303 static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path
*left_path
,
2306 struct ocfs2_extent_list
*left_el
;
2307 struct ocfs2_extent_rec
*rec
;
2310 left_el
= path_leaf_el(left_path
);
2311 next_free
= le16_to_cpu(left_el
->l_next_free_rec
);
2312 rec
= &left_el
->l_recs
[next_free
- 1];
2314 if (insert_cpos
> le32_to_cpu(rec
->e_cpos
))
2319 static int ocfs2_leftmost_rec_contains(struct ocfs2_extent_list
*el
, u32 cpos
)
2321 int next_free
= le16_to_cpu(el
->l_next_free_rec
);
2323 struct ocfs2_extent_rec
*rec
;
2328 rec
= &el
->l_recs
[0];
2329 if (ocfs2_is_empty_extent(rec
)) {
2333 rec
= &el
->l_recs
[1];
2336 range
= le32_to_cpu(rec
->e_cpos
) + ocfs2_rec_clusters(el
, rec
);
2337 if (cpos
>= le32_to_cpu(rec
->e_cpos
) && cpos
< range
)
2343 * Rotate all the records in a btree right one record, starting at insert_cpos.
2345 * The path to the rightmost leaf should be passed in.
2347 * The array is assumed to be large enough to hold an entire path (tree depth).
2349 * Upon successful return from this function:
2351 * - The 'right_path' array will contain a path to the leaf block
2352 * whose range contains e_cpos.
2353 * - That leaf block will have a single empty extent in list index 0.
2354 * - In the case that the rotation requires a post-insert update,
2355 * *ret_left_path will contain a valid path which can be passed to
2356 * ocfs2_insert_path().
2358 static int ocfs2_rotate_tree_right(handle_t
*handle
,
2359 struct ocfs2_extent_tree
*et
,
2360 enum ocfs2_split_type split
,
2362 struct ocfs2_path
*right_path
,
2363 struct ocfs2_path
**ret_left_path
)
2365 int ret
, start
, orig_credits
= handle
->h_buffer_credits
;
2367 struct ocfs2_path
*left_path
= NULL
;
2368 struct super_block
*sb
= ocfs2_metadata_cache_get_super(et
->et_ci
);
2370 *ret_left_path
= NULL
;
2372 left_path
= ocfs2_new_path_from_path(right_path
);
2379 ret
= ocfs2_find_cpos_for_left_leaf(sb
, right_path
, &cpos
);
2385 trace_ocfs2_rotate_tree_right(
2386 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
2390 * What we want to do here is:
2392 * 1) Start with the rightmost path.
2394 * 2) Determine a path to the leaf block directly to the left
2397 * 3) Determine the 'subtree root' - the lowest level tree node
2398 * which contains a path to both leaves.
2400 * 4) Rotate the subtree.
2402 * 5) Find the next subtree by considering the left path to be
2403 * the new right path.
2405 * The check at the top of this while loop also accepts
2406 * insert_cpos == cpos because cpos is only a _theoretical_
2407 * value to get us the left path - insert_cpos might very well
2408 * be filling that hole.
2410 * Stop at a cpos of '0' because we either started at the
2411 * leftmost branch (i.e., a tree with one branch and a
2412 * rotation inside of it), or we've gone as far as we can in
2413 * rotating subtrees.
2415 while (cpos
&& insert_cpos
<= cpos
) {
2416 trace_ocfs2_rotate_tree_right(
2417 (unsigned long long)
2418 ocfs2_metadata_cache_owner(et
->et_ci
),
2421 ret
= ocfs2_find_path(et
->et_ci
, left_path
, cpos
);
2427 mlog_bug_on_msg(path_leaf_bh(left_path
) ==
2428 path_leaf_bh(right_path
),
2429 "Owner %llu: error during insert of %u "
2430 "(left path cpos %u) results in two identical "
2431 "paths ending at %llu\n",
2432 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
2434 (unsigned long long)
2435 path_leaf_bh(left_path
)->b_blocknr
);
2437 if (split
== SPLIT_NONE
&&
2438 ocfs2_rotate_requires_path_adjustment(left_path
,
2442 * We've rotated the tree as much as we
2443 * should. The rest is up to
2444 * ocfs2_insert_path() to complete, after the
2445 * record insertion. We indicate this
2446 * situation by returning the left path.
2448 * The reason we don't adjust the records here
2449 * before the record insert is that an error
2450 * later might break the rule where a parent
2451 * record e_cpos will reflect the actual
2452 * e_cpos of the 1st nonempty record of the
2455 *ret_left_path
= left_path
;
2459 start
= ocfs2_find_subtree_root(et
, left_path
, right_path
);
2461 trace_ocfs2_rotate_subtree(start
,
2462 (unsigned long long)
2463 right_path
->p_node
[start
].bh
->b_blocknr
,
2464 right_path
->p_tree_depth
);
2466 ret
= ocfs2_extend_rotate_transaction(handle
, start
,
2467 orig_credits
, right_path
);
2473 ret
= ocfs2_rotate_subtree_right(handle
, et
, left_path
,
2480 if (split
!= SPLIT_NONE
&&
2481 ocfs2_leftmost_rec_contains(path_leaf_el(right_path
),
2484 * A rotate moves the rightmost left leaf
2485 * record over to the leftmost right leaf
2486 * slot. If we're doing an extent split
2487 * instead of a real insert, then we have to
2488 * check that the extent to be split wasn't
2489 * just moved over. If it was, then we can
2490 * exit here, passing left_path back -
2491 * ocfs2_split_extent() is smart enough to
2492 * search both leaves.
2494 *ret_left_path
= left_path
;
2499 * There is no need to re-read the next right path
2500 * as we know that it'll be our current left
2501 * path. Optimize by copying values instead.
2503 ocfs2_mv_path(right_path
, left_path
);
2505 ret
= ocfs2_find_cpos_for_left_leaf(sb
, right_path
, &cpos
);
2513 ocfs2_free_path(left_path
);
2519 static int ocfs2_update_edge_lengths(handle_t
*handle
,
2520 struct ocfs2_extent_tree
*et
,
2521 int subtree_index
, struct ocfs2_path
*path
)
2524 struct ocfs2_extent_rec
*rec
;
2525 struct ocfs2_extent_list
*el
;
2526 struct ocfs2_extent_block
*eb
;
2530 * In normal tree rotation process, we will never touch the
2531 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2532 * doesn't reserve the credits for them either.
2534 * But we do have a special case here which will update the rightmost
2535 * records for all the bh in the path.
2536 * So we have to allocate extra credits and access them.
2538 ret
= ocfs2_extend_trans(handle
, subtree_index
);
2544 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, path
);
2550 /* Path should always be rightmost. */
2551 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(path
)->b_data
;
2552 BUG_ON(eb
->h_next_leaf_blk
!= 0ULL);
2555 BUG_ON(le16_to_cpu(el
->l_next_free_rec
) == 0);
2556 idx
= le16_to_cpu(el
->l_next_free_rec
) - 1;
2557 rec
= &el
->l_recs
[idx
];
2558 range
= le32_to_cpu(rec
->e_cpos
) + ocfs2_rec_clusters(el
, rec
);
2560 for (i
= 0; i
< path
->p_tree_depth
; i
++) {
2561 el
= path
->p_node
[i
].el
;
2562 idx
= le16_to_cpu(el
->l_next_free_rec
) - 1;
2563 rec
= &el
->l_recs
[idx
];
2565 rec
->e_int_clusters
= cpu_to_le32(range
);
2566 le32_add_cpu(&rec
->e_int_clusters
, -le32_to_cpu(rec
->e_cpos
));
2568 ocfs2_journal_dirty(handle
, path
->p_node
[i
].bh
);
2574 static void ocfs2_unlink_path(handle_t
*handle
,
2575 struct ocfs2_extent_tree
*et
,
2576 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
2577 struct ocfs2_path
*path
, int unlink_start
)
2580 struct ocfs2_extent_block
*eb
;
2581 struct ocfs2_extent_list
*el
;
2582 struct buffer_head
*bh
;
2584 for(i
= unlink_start
; i
< path_num_items(path
); i
++) {
2585 bh
= path
->p_node
[i
].bh
;
2587 eb
= (struct ocfs2_extent_block
*)bh
->b_data
;
2589 * Not all nodes might have had their final count
2590 * decremented by the caller - handle this here.
2593 if (le16_to_cpu(el
->l_next_free_rec
) > 1) {
2595 "Inode %llu, attempted to remove extent block "
2596 "%llu with %u records\n",
2597 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
2598 (unsigned long long)le64_to_cpu(eb
->h_blkno
),
2599 le16_to_cpu(el
->l_next_free_rec
));
2601 ocfs2_journal_dirty(handle
, bh
);
2602 ocfs2_remove_from_cache(et
->et_ci
, bh
);
2606 el
->l_next_free_rec
= 0;
2607 memset(&el
->l_recs
[0], 0, sizeof(struct ocfs2_extent_rec
));
2609 ocfs2_journal_dirty(handle
, bh
);
2611 ret
= ocfs2_cache_extent_block_free(dealloc
, eb
);
2615 ocfs2_remove_from_cache(et
->et_ci
, bh
);
2619 static void ocfs2_unlink_subtree(handle_t
*handle
,
2620 struct ocfs2_extent_tree
*et
,
2621 struct ocfs2_path
*left_path
,
2622 struct ocfs2_path
*right_path
,
2624 struct ocfs2_cached_dealloc_ctxt
*dealloc
)
2627 struct buffer_head
*root_bh
= left_path
->p_node
[subtree_index
].bh
;
2628 struct ocfs2_extent_list
*root_el
= left_path
->p_node
[subtree_index
].el
;
2629 struct ocfs2_extent_list
*el
;
2630 struct ocfs2_extent_block
*eb
;
2632 el
= path_leaf_el(left_path
);
2634 eb
= (struct ocfs2_extent_block
*)right_path
->p_node
[subtree_index
+ 1].bh
->b_data
;
2636 for(i
= 1; i
< le16_to_cpu(root_el
->l_next_free_rec
); i
++)
2637 if (root_el
->l_recs
[i
].e_blkno
== eb
->h_blkno
)
2640 BUG_ON(i
>= le16_to_cpu(root_el
->l_next_free_rec
));
2642 memset(&root_el
->l_recs
[i
], 0, sizeof(struct ocfs2_extent_rec
));
2643 le16_add_cpu(&root_el
->l_next_free_rec
, -1);
2645 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(left_path
)->b_data
;
2646 eb
->h_next_leaf_blk
= 0;
2648 ocfs2_journal_dirty(handle
, root_bh
);
2649 ocfs2_journal_dirty(handle
, path_leaf_bh(left_path
));
2651 ocfs2_unlink_path(handle
, et
, dealloc
, right_path
,
2655 static int ocfs2_rotate_subtree_left(handle_t
*handle
,
2656 struct ocfs2_extent_tree
*et
,
2657 struct ocfs2_path
*left_path
,
2658 struct ocfs2_path
*right_path
,
2660 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
2663 int ret
, i
, del_right_subtree
= 0, right_has_empty
= 0;
2664 struct buffer_head
*root_bh
, *et_root_bh
= path_root_bh(right_path
);
2665 struct ocfs2_extent_list
*right_leaf_el
, *left_leaf_el
;
2666 struct ocfs2_extent_block
*eb
;
2670 right_leaf_el
= path_leaf_el(right_path
);
2671 left_leaf_el
= path_leaf_el(left_path
);
2672 root_bh
= left_path
->p_node
[subtree_index
].bh
;
2673 BUG_ON(root_bh
!= right_path
->p_node
[subtree_index
].bh
);
2675 if (!ocfs2_is_empty_extent(&left_leaf_el
->l_recs
[0]))
2678 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(right_path
)->b_data
;
2679 if (ocfs2_is_empty_extent(&right_leaf_el
->l_recs
[0])) {
2681 * It's legal for us to proceed if the right leaf is
2682 * the rightmost one and it has an empty extent. There
2683 * are two cases to handle - whether the leaf will be
2684 * empty after removal or not. If the leaf isn't empty
2685 * then just remove the empty extent up front. The
2686 * next block will handle empty leaves by flagging
2689 * Non rightmost leaves will throw -EAGAIN and the
2690 * caller can manually move the subtree and retry.
2693 if (eb
->h_next_leaf_blk
!= 0ULL)
2696 if (le16_to_cpu(right_leaf_el
->l_next_free_rec
) > 1) {
2697 ret
= ocfs2_journal_access_eb(handle
, et
->et_ci
,
2698 path_leaf_bh(right_path
),
2699 OCFS2_JOURNAL_ACCESS_WRITE
);
2705 ocfs2_remove_empty_extent(right_leaf_el
);
2707 right_has_empty
= 1;
2710 if (eb
->h_next_leaf_blk
== 0ULL &&
2711 le16_to_cpu(right_leaf_el
->l_next_free_rec
) == 1) {
2713 * We have to update i_last_eb_blk during the meta
2716 ret
= ocfs2_et_root_journal_access(handle
, et
,
2717 OCFS2_JOURNAL_ACCESS_WRITE
);
2723 del_right_subtree
= 1;
2727 * Getting here with an empty extent in the right path implies
2728 * that it's the rightmost path and will be deleted.
2730 BUG_ON(right_has_empty
&& !del_right_subtree
);
2732 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, right_path
,
2739 for(i
= subtree_index
+ 1; i
< path_num_items(right_path
); i
++) {
2740 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
2747 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
2755 if (!right_has_empty
) {
2757 * Only do this if we're moving a real
2758 * record. Otherwise, the action is delayed until
2759 * after removal of the right path in which case we
2760 * can do a simple shift to remove the empty extent.
2762 ocfs2_rotate_leaf(left_leaf_el
, &right_leaf_el
->l_recs
[0]);
2763 memset(&right_leaf_el
->l_recs
[0], 0,
2764 sizeof(struct ocfs2_extent_rec
));
2766 if (eb
->h_next_leaf_blk
== 0ULL) {
2768 * Move recs over to get rid of empty extent, decrease
2769 * next_free. This is allowed to remove the last
2770 * extent in our leaf (setting l_next_free_rec to
2771 * zero) - the delete code below won't care.
2773 ocfs2_remove_empty_extent(right_leaf_el
);
2776 ocfs2_journal_dirty(handle
, path_leaf_bh(left_path
));
2777 ocfs2_journal_dirty(handle
, path_leaf_bh(right_path
));
2779 if (del_right_subtree
) {
2780 ocfs2_unlink_subtree(handle
, et
, left_path
, right_path
,
2781 subtree_index
, dealloc
);
2782 ret
= ocfs2_update_edge_lengths(handle
, et
, subtree_index
,
2789 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(left_path
)->b_data
;
2790 ocfs2_et_set_last_eb_blk(et
, le64_to_cpu(eb
->h_blkno
));
2793 * Removal of the extent in the left leaf was skipped
2794 * above so we could delete the right path
2797 if (right_has_empty
)
2798 ocfs2_remove_empty_extent(left_leaf_el
);
2800 ocfs2_journal_dirty(handle
, et_root_bh
);
2804 ocfs2_complete_edge_insert(handle
, left_path
, right_path
,
2812 * Given a full path, determine what cpos value would return us a path
2813 * containing the leaf immediately to the right of the current one.
2815 * Will return zero if the path passed in is already the rightmost path.
2817 * This looks similar, but is subtly different to
2818 * ocfs2_find_cpos_for_left_leaf().
2820 int ocfs2_find_cpos_for_right_leaf(struct super_block
*sb
,
2821 struct ocfs2_path
*path
, u32
*cpos
)
2825 struct ocfs2_extent_list
*el
;
2829 if (path
->p_tree_depth
== 0)
2832 blkno
= path_leaf_bh(path
)->b_blocknr
;
2834 /* Start at the tree node just above the leaf and work our way up. */
2835 i
= path
->p_tree_depth
- 1;
2839 el
= path
->p_node
[i
].el
;
2842 * Find the extent record just after the one in our
2845 next_free
= le16_to_cpu(el
->l_next_free_rec
);
2846 for(j
= 0; j
< le16_to_cpu(el
->l_next_free_rec
); j
++) {
2847 if (le64_to_cpu(el
->l_recs
[j
].e_blkno
) == blkno
) {
2848 if (j
== (next_free
- 1)) {
2851 * We've determined that the
2852 * path specified is already
2853 * the rightmost one - return a
2859 * The rightmost record points to our
2860 * leaf - we need to travel up the
2866 *cpos
= le32_to_cpu(el
->l_recs
[j
+ 1].e_cpos
);
2872 * If we got here, we never found a valid node where
2873 * the tree indicated one should be.
2876 "Invalid extent tree at extent block %llu\n",
2877 (unsigned long long)blkno
);
2882 blkno
= path
->p_node
[i
].bh
->b_blocknr
;
2890 static int ocfs2_rotate_rightmost_leaf_left(handle_t
*handle
,
2891 struct ocfs2_extent_tree
*et
,
2892 struct ocfs2_path
*path
)
2895 struct buffer_head
*bh
= path_leaf_bh(path
);
2896 struct ocfs2_extent_list
*el
= path_leaf_el(path
);
2898 if (!ocfs2_is_empty_extent(&el
->l_recs
[0]))
2901 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, path
,
2902 path_num_items(path
) - 1);
2908 ocfs2_remove_empty_extent(el
);
2909 ocfs2_journal_dirty(handle
, bh
);
2915 static int __ocfs2_rotate_tree_left(handle_t
*handle
,
2916 struct ocfs2_extent_tree
*et
,
2918 struct ocfs2_path
*path
,
2919 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
2920 struct ocfs2_path
**empty_extent_path
)
2922 int ret
, subtree_root
, deleted
;
2924 struct ocfs2_path
*left_path
= NULL
;
2925 struct ocfs2_path
*right_path
= NULL
;
2926 struct super_block
*sb
= ocfs2_metadata_cache_get_super(et
->et_ci
);
2928 BUG_ON(!ocfs2_is_empty_extent(&(path_leaf_el(path
)->l_recs
[0])));
2930 *empty_extent_path
= NULL
;
2932 ret
= ocfs2_find_cpos_for_right_leaf(sb
, path
, &right_cpos
);
2938 left_path
= ocfs2_new_path_from_path(path
);
2945 ocfs2_cp_path(left_path
, path
);
2947 right_path
= ocfs2_new_path_from_path(path
);
2954 while (right_cpos
) {
2955 ret
= ocfs2_find_path(et
->et_ci
, right_path
, right_cpos
);
2961 subtree_root
= ocfs2_find_subtree_root(et
, left_path
,
2964 trace_ocfs2_rotate_subtree(subtree_root
,
2965 (unsigned long long)
2966 right_path
->p_node
[subtree_root
].bh
->b_blocknr
,
2967 right_path
->p_tree_depth
);
2969 ret
= ocfs2_extend_rotate_transaction(handle
, subtree_root
,
2970 orig_credits
, left_path
);
2977 * Caller might still want to make changes to the
2978 * tree root, so re-add it to the journal here.
2980 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
2987 ret
= ocfs2_rotate_subtree_left(handle
, et
, left_path
,
2988 right_path
, subtree_root
,
2990 if (ret
== -EAGAIN
) {
2992 * The rotation has to temporarily stop due to
2993 * the right subtree having an empty
2994 * extent. Pass it back to the caller for a
2997 *empty_extent_path
= right_path
;
3007 * The subtree rotate might have removed records on
3008 * the rightmost edge. If so, then rotation is
3014 ocfs2_mv_path(left_path
, right_path
);
3016 ret
= ocfs2_find_cpos_for_right_leaf(sb
, left_path
,
3025 ocfs2_free_path(right_path
);
3026 ocfs2_free_path(left_path
);
3031 static int ocfs2_remove_rightmost_path(handle_t
*handle
,
3032 struct ocfs2_extent_tree
*et
,
3033 struct ocfs2_path
*path
,
3034 struct ocfs2_cached_dealloc_ctxt
*dealloc
)
3036 int ret
, subtree_index
;
3038 struct ocfs2_path
*left_path
= NULL
;
3039 struct ocfs2_extent_block
*eb
;
3040 struct ocfs2_extent_list
*el
;
3043 ret
= ocfs2_et_sanity_check(et
);
3047 * There's two ways we handle this depending on
3048 * whether path is the only existing one.
3050 ret
= ocfs2_extend_rotate_transaction(handle
, 0,
3051 handle
->h_buffer_credits
,
3058 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, path
);
3064 ret
= ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et
->et_ci
),
3073 * We have a path to the left of this one - it needs
3076 left_path
= ocfs2_new_path_from_path(path
);
3083 ret
= ocfs2_find_path(et
->et_ci
, left_path
, cpos
);
3089 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, left_path
);
3095 subtree_index
= ocfs2_find_subtree_root(et
, left_path
, path
);
3097 ocfs2_unlink_subtree(handle
, et
, left_path
, path
,
3098 subtree_index
, dealloc
);
3099 ret
= ocfs2_update_edge_lengths(handle
, et
, subtree_index
,
3106 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(left_path
)->b_data
;
3107 ocfs2_et_set_last_eb_blk(et
, le64_to_cpu(eb
->h_blkno
));
3110 * 'path' is also the leftmost path which
3111 * means it must be the only one. This gets
3112 * handled differently because we want to
3113 * revert the root back to having extents
3116 ocfs2_unlink_path(handle
, et
, dealloc
, path
, 1);
3118 el
= et
->et_root_el
;
3119 el
->l_tree_depth
= 0;
3120 el
->l_next_free_rec
= 0;
3121 memset(&el
->l_recs
[0], 0, sizeof(struct ocfs2_extent_rec
));
3123 ocfs2_et_set_last_eb_blk(et
, 0);
3126 ocfs2_journal_dirty(handle
, path_root_bh(path
));
3129 ocfs2_free_path(left_path
);
3134 * Left rotation of btree records.
3136 * In many ways, this is (unsurprisingly) the opposite of right
3137 * rotation. We start at some non-rightmost path containing an empty
3138 * extent in the leaf block. The code works its way to the rightmost
3139 * path by rotating records to the left in every subtree.
3141 * This is used by any code which reduces the number of extent records
3142 * in a leaf. After removal, an empty record should be placed in the
3143 * leftmost list position.
3145 * This won't handle a length update of the rightmost path records if
3146 * the rightmost tree leaf record is removed so the caller is
3147 * responsible for detecting and correcting that.
3149 static int ocfs2_rotate_tree_left(handle_t
*handle
,
3150 struct ocfs2_extent_tree
*et
,
3151 struct ocfs2_path
*path
,
3152 struct ocfs2_cached_dealloc_ctxt
*dealloc
)
3154 int ret
, orig_credits
= handle
->h_buffer_credits
;
3155 struct ocfs2_path
*tmp_path
= NULL
, *restart_path
= NULL
;
3156 struct ocfs2_extent_block
*eb
;
3157 struct ocfs2_extent_list
*el
;
3159 el
= path_leaf_el(path
);
3160 if (!ocfs2_is_empty_extent(&el
->l_recs
[0]))
3163 if (path
->p_tree_depth
== 0) {
3164 rightmost_no_delete
:
3166 * Inline extents. This is trivially handled, so do
3169 ret
= ocfs2_rotate_rightmost_leaf_left(handle
, et
, path
);
3176 * Handle rightmost branch now. There's several cases:
3177 * 1) simple rotation leaving records in there. That's trivial.
3178 * 2) rotation requiring a branch delete - there's no more
3179 * records left. Two cases of this:
3180 * a) There are branches to the left.
3181 * b) This is also the leftmost (the only) branch.
3183 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3184 * 2a) we need the left branch so that we can update it with the unlink
3185 * 2b) we need to bring the root back to inline extents.
3188 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(path
)->b_data
;
3190 if (eb
->h_next_leaf_blk
== 0) {
3192 * This gets a bit tricky if we're going to delete the
3193 * rightmost path. Get the other cases out of the way
3196 if (le16_to_cpu(el
->l_next_free_rec
) > 1)
3197 goto rightmost_no_delete
;
3199 if (le16_to_cpu(el
->l_next_free_rec
) == 0) {
3201 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
3202 "Owner %llu has empty extent block at %llu",
3203 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
3204 (unsigned long long)le64_to_cpu(eb
->h_blkno
));
3209 * XXX: The caller can not trust "path" any more after
3210 * this as it will have been deleted. What do we do?
3212 * In theory the rotate-for-merge code will never get
3213 * here because it'll always ask for a rotate in a
3217 ret
= ocfs2_remove_rightmost_path(handle
, et
, path
,
3225 * Now we can loop, remembering the path we get from -EAGAIN
3226 * and restarting from there.
3229 ret
= __ocfs2_rotate_tree_left(handle
, et
, orig_credits
, path
,
3230 dealloc
, &restart_path
);
3231 if (ret
&& ret
!= -EAGAIN
) {
3236 while (ret
== -EAGAIN
) {
3237 tmp_path
= restart_path
;
3238 restart_path
= NULL
;
3240 ret
= __ocfs2_rotate_tree_left(handle
, et
, orig_credits
,
3243 if (ret
&& ret
!= -EAGAIN
) {
3248 ocfs2_free_path(tmp_path
);
3256 ocfs2_free_path(tmp_path
);
3257 ocfs2_free_path(restart_path
);
3261 static void ocfs2_cleanup_merge(struct ocfs2_extent_list
*el
,
3264 struct ocfs2_extent_rec
*rec
= &el
->l_recs
[index
];
3267 if (rec
->e_leaf_clusters
== 0) {
3269 * We consumed all of the merged-from record. An empty
3270 * extent cannot exist anywhere but the 1st array
3271 * position, so move things over if the merged-from
3272 * record doesn't occupy that position.
3274 * This creates a new empty extent so the caller
3275 * should be smart enough to have removed any existing
3279 BUG_ON(ocfs2_is_empty_extent(&el
->l_recs
[0]));
3280 size
= index
* sizeof(struct ocfs2_extent_rec
);
3281 memmove(&el
->l_recs
[1], &el
->l_recs
[0], size
);
3285 * Always memset - the caller doesn't check whether it
3286 * created an empty extent, so there could be junk in
3289 memset(&el
->l_recs
[0], 0, sizeof(struct ocfs2_extent_rec
));
3293 static int ocfs2_get_right_path(struct ocfs2_extent_tree
*et
,
3294 struct ocfs2_path
*left_path
,
3295 struct ocfs2_path
**ret_right_path
)
3299 struct ocfs2_path
*right_path
= NULL
;
3300 struct ocfs2_extent_list
*left_el
;
3302 *ret_right_path
= NULL
;
3304 /* This function shouldn't be called for non-trees. */
3305 BUG_ON(left_path
->p_tree_depth
== 0);
3307 left_el
= path_leaf_el(left_path
);
3308 BUG_ON(left_el
->l_next_free_rec
!= left_el
->l_count
);
3310 ret
= ocfs2_find_cpos_for_right_leaf(ocfs2_metadata_cache_get_super(et
->et_ci
),
3311 left_path
, &right_cpos
);
3317 /* This function shouldn't be called for the rightmost leaf. */
3318 BUG_ON(right_cpos
== 0);
3320 right_path
= ocfs2_new_path_from_path(left_path
);
3327 ret
= ocfs2_find_path(et
->et_ci
, right_path
, right_cpos
);
3333 *ret_right_path
= right_path
;
3336 ocfs2_free_path(right_path
);
3341 * Remove split_rec clusters from the record at index and merge them
3342 * onto the beginning of the record "next" to it.
3343 * For index < l_count - 1, the next means the extent rec at index + 1.
3344 * For index == l_count - 1, the "next" means the 1st extent rec of the
3345 * next extent block.
3347 static int ocfs2_merge_rec_right(struct ocfs2_path
*left_path
,
3349 struct ocfs2_extent_tree
*et
,
3350 struct ocfs2_extent_rec
*split_rec
,
3353 int ret
, next_free
, i
;
3354 unsigned int split_clusters
= le16_to_cpu(split_rec
->e_leaf_clusters
);
3355 struct ocfs2_extent_rec
*left_rec
;
3356 struct ocfs2_extent_rec
*right_rec
;
3357 struct ocfs2_extent_list
*right_el
;
3358 struct ocfs2_path
*right_path
= NULL
;
3359 int subtree_index
= 0;
3360 struct ocfs2_extent_list
*el
= path_leaf_el(left_path
);
3361 struct buffer_head
*bh
= path_leaf_bh(left_path
);
3362 struct buffer_head
*root_bh
= NULL
;
3364 BUG_ON(index
>= le16_to_cpu(el
->l_next_free_rec
));
3365 left_rec
= &el
->l_recs
[index
];
3367 if (index
== le16_to_cpu(el
->l_next_free_rec
) - 1 &&
3368 le16_to_cpu(el
->l_next_free_rec
) == le16_to_cpu(el
->l_count
)) {
3369 /* we meet with a cross extent block merge. */
3370 ret
= ocfs2_get_right_path(et
, left_path
, &right_path
);
3376 right_el
= path_leaf_el(right_path
);
3377 next_free
= le16_to_cpu(right_el
->l_next_free_rec
);
3378 BUG_ON(next_free
<= 0);
3379 right_rec
= &right_el
->l_recs
[0];
3380 if (ocfs2_is_empty_extent(right_rec
)) {
3381 BUG_ON(next_free
<= 1);
3382 right_rec
= &right_el
->l_recs
[1];
3385 BUG_ON(le32_to_cpu(left_rec
->e_cpos
) +
3386 le16_to_cpu(left_rec
->e_leaf_clusters
) !=
3387 le32_to_cpu(right_rec
->e_cpos
));
3389 subtree_index
= ocfs2_find_subtree_root(et
, left_path
,
3392 ret
= ocfs2_extend_rotate_transaction(handle
, subtree_index
,
3393 handle
->h_buffer_credits
,
3400 root_bh
= left_path
->p_node
[subtree_index
].bh
;
3401 BUG_ON(root_bh
!= right_path
->p_node
[subtree_index
].bh
);
3403 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, right_path
,
3410 for (i
= subtree_index
+ 1;
3411 i
< path_num_items(right_path
); i
++) {
3412 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
3419 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
3428 BUG_ON(index
== le16_to_cpu(el
->l_next_free_rec
) - 1);
3429 right_rec
= &el
->l_recs
[index
+ 1];
3432 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, left_path
,
3433 path_num_items(left_path
) - 1);
3439 le16_add_cpu(&left_rec
->e_leaf_clusters
, -split_clusters
);
3441 le32_add_cpu(&right_rec
->e_cpos
, -split_clusters
);
3442 le64_add_cpu(&right_rec
->e_blkno
,
3443 -ocfs2_clusters_to_blocks(ocfs2_metadata_cache_get_super(et
->et_ci
),
3445 le16_add_cpu(&right_rec
->e_leaf_clusters
, split_clusters
);
3447 ocfs2_cleanup_merge(el
, index
);
3449 ocfs2_journal_dirty(handle
, bh
);
3451 ocfs2_journal_dirty(handle
, path_leaf_bh(right_path
));
3452 ocfs2_complete_edge_insert(handle
, left_path
, right_path
,
3456 ocfs2_free_path(right_path
);
3460 static int ocfs2_get_left_path(struct ocfs2_extent_tree
*et
,
3461 struct ocfs2_path
*right_path
,
3462 struct ocfs2_path
**ret_left_path
)
3466 struct ocfs2_path
*left_path
= NULL
;
3468 *ret_left_path
= NULL
;
3470 /* This function shouldn't be called for non-trees. */
3471 BUG_ON(right_path
->p_tree_depth
== 0);
3473 ret
= ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et
->et_ci
),
3474 right_path
, &left_cpos
);
3480 /* This function shouldn't be called for the leftmost leaf. */
3481 BUG_ON(left_cpos
== 0);
3483 left_path
= ocfs2_new_path_from_path(right_path
);
3490 ret
= ocfs2_find_path(et
->et_ci
, left_path
, left_cpos
);
3496 *ret_left_path
= left_path
;
3499 ocfs2_free_path(left_path
);
3504 * Remove split_rec clusters from the record at index and merge them
3505 * onto the tail of the record "before" it.
3506 * For index > 0, the "before" means the extent rec at index - 1.
3508 * For index == 0, the "before" means the last record of the previous
3509 * extent block. And there is also a situation that we may need to
3510 * remove the rightmost leaf extent block in the right_path and change
3511 * the right path to indicate the new rightmost path.
3513 static int ocfs2_merge_rec_left(struct ocfs2_path
*right_path
,
3515 struct ocfs2_extent_tree
*et
,
3516 struct ocfs2_extent_rec
*split_rec
,
3517 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
3520 int ret
, i
, subtree_index
= 0, has_empty_extent
= 0;
3521 unsigned int split_clusters
= le16_to_cpu(split_rec
->e_leaf_clusters
);
3522 struct ocfs2_extent_rec
*left_rec
;
3523 struct ocfs2_extent_rec
*right_rec
;
3524 struct ocfs2_extent_list
*el
= path_leaf_el(right_path
);
3525 struct buffer_head
*bh
= path_leaf_bh(right_path
);
3526 struct buffer_head
*root_bh
= NULL
;
3527 struct ocfs2_path
*left_path
= NULL
;
3528 struct ocfs2_extent_list
*left_el
;
3532 right_rec
= &el
->l_recs
[index
];
3534 /* we meet with a cross extent block merge. */
3535 ret
= ocfs2_get_left_path(et
, right_path
, &left_path
);
3541 left_el
= path_leaf_el(left_path
);
3542 BUG_ON(le16_to_cpu(left_el
->l_next_free_rec
) !=
3543 le16_to_cpu(left_el
->l_count
));
3545 left_rec
= &left_el
->l_recs
[
3546 le16_to_cpu(left_el
->l_next_free_rec
) - 1];
3547 BUG_ON(le32_to_cpu(left_rec
->e_cpos
) +
3548 le16_to_cpu(left_rec
->e_leaf_clusters
) !=
3549 le32_to_cpu(split_rec
->e_cpos
));
3551 subtree_index
= ocfs2_find_subtree_root(et
, left_path
,
3554 ret
= ocfs2_extend_rotate_transaction(handle
, subtree_index
,
3555 handle
->h_buffer_credits
,
3562 root_bh
= left_path
->p_node
[subtree_index
].bh
;
3563 BUG_ON(root_bh
!= right_path
->p_node
[subtree_index
].bh
);
3565 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, right_path
,
3572 for (i
= subtree_index
+ 1;
3573 i
< path_num_items(right_path
); i
++) {
3574 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
3581 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
,
3589 left_rec
= &el
->l_recs
[index
- 1];
3590 if (ocfs2_is_empty_extent(&el
->l_recs
[0]))
3591 has_empty_extent
= 1;
3594 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, right_path
,
3595 path_num_items(right_path
) - 1);
3601 if (has_empty_extent
&& index
== 1) {
3603 * The easy case - we can just plop the record right in.
3605 *left_rec
= *split_rec
;
3607 has_empty_extent
= 0;
3609 le16_add_cpu(&left_rec
->e_leaf_clusters
, split_clusters
);
3611 le32_add_cpu(&right_rec
->e_cpos
, split_clusters
);
3612 le64_add_cpu(&right_rec
->e_blkno
,
3613 ocfs2_clusters_to_blocks(ocfs2_metadata_cache_get_super(et
->et_ci
),
3615 le16_add_cpu(&right_rec
->e_leaf_clusters
, -split_clusters
);
3617 ocfs2_cleanup_merge(el
, index
);
3619 ocfs2_journal_dirty(handle
, bh
);
3621 ocfs2_journal_dirty(handle
, path_leaf_bh(left_path
));
3624 * In the situation that the right_rec is empty and the extent
3625 * block is empty also, ocfs2_complete_edge_insert can't handle
3626 * it and we need to delete the right extent block.
3628 if (le16_to_cpu(right_rec
->e_leaf_clusters
) == 0 &&
3629 le16_to_cpu(el
->l_next_free_rec
) == 1) {
3631 ret
= ocfs2_remove_rightmost_path(handle
, et
,
3639 /* Now the rightmost extent block has been deleted.
3640 * So we use the new rightmost path.
3642 ocfs2_mv_path(right_path
, left_path
);
3645 ocfs2_complete_edge_insert(handle
, left_path
,
3646 right_path
, subtree_index
);
3649 ocfs2_free_path(left_path
);
3653 static int ocfs2_try_to_merge_extent(handle_t
*handle
,
3654 struct ocfs2_extent_tree
*et
,
3655 struct ocfs2_path
*path
,
3657 struct ocfs2_extent_rec
*split_rec
,
3658 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
3659 struct ocfs2_merge_ctxt
*ctxt
)
3662 struct ocfs2_extent_list
*el
= path_leaf_el(path
);
3663 struct ocfs2_extent_rec
*rec
= &el
->l_recs
[split_index
];
3665 BUG_ON(ctxt
->c_contig_type
== CONTIG_NONE
);
3667 if (ctxt
->c_split_covers_rec
&& ctxt
->c_has_empty_extent
) {
3669 * The merge code will need to create an empty
3670 * extent to take the place of the newly
3671 * emptied slot. Remove any pre-existing empty
3672 * extents - having more than one in a leaf is
3675 ret
= ocfs2_rotate_tree_left(handle
, et
, path
, dealloc
);
3681 rec
= &el
->l_recs
[split_index
];
3684 if (ctxt
->c_contig_type
== CONTIG_LEFTRIGHT
) {
3686 * Left-right contig implies this.
3688 BUG_ON(!ctxt
->c_split_covers_rec
);
3691 * Since the leftright insert always covers the entire
3692 * extent, this call will delete the insert record
3693 * entirely, resulting in an empty extent record added to
3696 * Since the adding of an empty extent shifts
3697 * everything back to the right, there's no need to
3698 * update split_index here.
3700 * When the split_index is zero, we need to merge it to the
3701 * prevoius extent block. It is more efficient and easier
3702 * if we do merge_right first and merge_left later.
3704 ret
= ocfs2_merge_rec_right(path
, handle
, et
, split_rec
,
3712 * We can only get this from logic error above.
3714 BUG_ON(!ocfs2_is_empty_extent(&el
->l_recs
[0]));
3716 /* The merge left us with an empty extent, remove it. */
3717 ret
= ocfs2_rotate_tree_left(handle
, et
, path
, dealloc
);
3723 rec
= &el
->l_recs
[split_index
];
3726 * Note that we don't pass split_rec here on purpose -
3727 * we've merged it into the rec already.
3729 ret
= ocfs2_merge_rec_left(path
, handle
, et
, rec
,
3730 dealloc
, split_index
);
3737 ret
= ocfs2_rotate_tree_left(handle
, et
, path
, dealloc
);
3739 * Error from this last rotate is not critical, so
3740 * print but don't bubble it up.
3747 * Merge a record to the left or right.
3749 * 'contig_type' is relative to the existing record,
3750 * so for example, if we're "right contig", it's to
3751 * the record on the left (hence the left merge).
3753 if (ctxt
->c_contig_type
== CONTIG_RIGHT
) {
3754 ret
= ocfs2_merge_rec_left(path
, handle
, et
,
3762 ret
= ocfs2_merge_rec_right(path
, handle
,
3771 if (ctxt
->c_split_covers_rec
) {
3773 * The merge may have left an empty extent in
3774 * our leaf. Try to rotate it away.
3776 ret
= ocfs2_rotate_tree_left(handle
, et
, path
,
3788 static void ocfs2_subtract_from_rec(struct super_block
*sb
,
3789 enum ocfs2_split_type split
,
3790 struct ocfs2_extent_rec
*rec
,
3791 struct ocfs2_extent_rec
*split_rec
)
3795 len_blocks
= ocfs2_clusters_to_blocks(sb
,
3796 le16_to_cpu(split_rec
->e_leaf_clusters
));
3798 if (split
== SPLIT_LEFT
) {
3800 * Region is on the left edge of the existing
3803 le32_add_cpu(&rec
->e_cpos
,
3804 le16_to_cpu(split_rec
->e_leaf_clusters
));
3805 le64_add_cpu(&rec
->e_blkno
, len_blocks
);
3806 le16_add_cpu(&rec
->e_leaf_clusters
,
3807 -le16_to_cpu(split_rec
->e_leaf_clusters
));
3810 * Region is on the right edge of the existing
3813 le16_add_cpu(&rec
->e_leaf_clusters
,
3814 -le16_to_cpu(split_rec
->e_leaf_clusters
));
3819 * Do the final bits of extent record insertion at the target leaf
3820 * list. If this leaf is part of an allocation tree, it is assumed
3821 * that the tree above has been prepared.
3823 static void ocfs2_insert_at_leaf(struct ocfs2_extent_tree
*et
,
3824 struct ocfs2_extent_rec
*insert_rec
,
3825 struct ocfs2_extent_list
*el
,
3826 struct ocfs2_insert_type
*insert
)
3828 int i
= insert
->ins_contig_index
;
3830 struct ocfs2_extent_rec
*rec
;
3832 BUG_ON(le16_to_cpu(el
->l_tree_depth
) != 0);
3834 if (insert
->ins_split
!= SPLIT_NONE
) {
3835 i
= ocfs2_search_extent_list(el
, le32_to_cpu(insert_rec
->e_cpos
));
3837 rec
= &el
->l_recs
[i
];
3838 ocfs2_subtract_from_rec(ocfs2_metadata_cache_get_super(et
->et_ci
),
3839 insert
->ins_split
, rec
,
3845 * Contiguous insert - either left or right.
3847 if (insert
->ins_contig
!= CONTIG_NONE
) {
3848 rec
= &el
->l_recs
[i
];
3849 if (insert
->ins_contig
== CONTIG_LEFT
) {
3850 rec
->e_blkno
= insert_rec
->e_blkno
;
3851 rec
->e_cpos
= insert_rec
->e_cpos
;
3853 le16_add_cpu(&rec
->e_leaf_clusters
,
3854 le16_to_cpu(insert_rec
->e_leaf_clusters
));
3859 * Handle insert into an empty leaf.
3861 if (le16_to_cpu(el
->l_next_free_rec
) == 0 ||
3862 ((le16_to_cpu(el
->l_next_free_rec
) == 1) &&
3863 ocfs2_is_empty_extent(&el
->l_recs
[0]))) {
3864 el
->l_recs
[0] = *insert_rec
;
3865 el
->l_next_free_rec
= cpu_to_le16(1);
3872 if (insert
->ins_appending
== APPEND_TAIL
) {
3873 i
= le16_to_cpu(el
->l_next_free_rec
) - 1;
3874 rec
= &el
->l_recs
[i
];
3875 range
= le32_to_cpu(rec
->e_cpos
)
3876 + le16_to_cpu(rec
->e_leaf_clusters
);
3877 BUG_ON(le32_to_cpu(insert_rec
->e_cpos
) < range
);
3879 mlog_bug_on_msg(le16_to_cpu(el
->l_next_free_rec
) >=
3880 le16_to_cpu(el
->l_count
),
3881 "owner %llu, depth %u, count %u, next free %u, "
3882 "rec.cpos %u, rec.clusters %u, "
3883 "insert.cpos %u, insert.clusters %u\n",
3884 ocfs2_metadata_cache_owner(et
->et_ci
),
3885 le16_to_cpu(el
->l_tree_depth
),
3886 le16_to_cpu(el
->l_count
),
3887 le16_to_cpu(el
->l_next_free_rec
),
3888 le32_to_cpu(el
->l_recs
[i
].e_cpos
),
3889 le16_to_cpu(el
->l_recs
[i
].e_leaf_clusters
),
3890 le32_to_cpu(insert_rec
->e_cpos
),
3891 le16_to_cpu(insert_rec
->e_leaf_clusters
));
3893 el
->l_recs
[i
] = *insert_rec
;
3894 le16_add_cpu(&el
->l_next_free_rec
, 1);
3900 * Ok, we have to rotate.
3902 * At this point, it is safe to assume that inserting into an
3903 * empty leaf and appending to a leaf have both been handled
3906 * This leaf needs to have space, either by the empty 1st
3907 * extent record, or by virtue of an l_next_rec < l_count.
3909 ocfs2_rotate_leaf(el
, insert_rec
);
3912 static void ocfs2_adjust_rightmost_records(handle_t
*handle
,
3913 struct ocfs2_extent_tree
*et
,
3914 struct ocfs2_path
*path
,
3915 struct ocfs2_extent_rec
*insert_rec
)
3917 int ret
, i
, next_free
;
3918 struct buffer_head
*bh
;
3919 struct ocfs2_extent_list
*el
;
3920 struct ocfs2_extent_rec
*rec
;
3923 * Update everything except the leaf block.
3925 for (i
= 0; i
< path
->p_tree_depth
; i
++) {
3926 bh
= path
->p_node
[i
].bh
;
3927 el
= path
->p_node
[i
].el
;
3929 next_free
= le16_to_cpu(el
->l_next_free_rec
);
3930 if (next_free
== 0) {
3931 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
3932 "Owner %llu has a bad extent list",
3933 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
));
3938 rec
= &el
->l_recs
[next_free
- 1];
3940 rec
->e_int_clusters
= insert_rec
->e_cpos
;
3941 le32_add_cpu(&rec
->e_int_clusters
,
3942 le16_to_cpu(insert_rec
->e_leaf_clusters
));
3943 le32_add_cpu(&rec
->e_int_clusters
,
3944 -le32_to_cpu(rec
->e_cpos
));
3946 ocfs2_journal_dirty(handle
, bh
);
3950 static int ocfs2_append_rec_to_path(handle_t
*handle
,
3951 struct ocfs2_extent_tree
*et
,
3952 struct ocfs2_extent_rec
*insert_rec
,
3953 struct ocfs2_path
*right_path
,
3954 struct ocfs2_path
**ret_left_path
)
3957 struct ocfs2_extent_list
*el
;
3958 struct ocfs2_path
*left_path
= NULL
;
3960 *ret_left_path
= NULL
;
3963 * This shouldn't happen for non-trees. The extent rec cluster
3964 * count manipulation below only works for interior nodes.
3966 BUG_ON(right_path
->p_tree_depth
== 0);
3969 * If our appending insert is at the leftmost edge of a leaf,
3970 * then we might need to update the rightmost records of the
3973 el
= path_leaf_el(right_path
);
3974 next_free
= le16_to_cpu(el
->l_next_free_rec
);
3975 if (next_free
== 0 ||
3976 (next_free
== 1 && ocfs2_is_empty_extent(&el
->l_recs
[0]))) {
3979 ret
= ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et
->et_ci
),
3980 right_path
, &left_cpos
);
3986 trace_ocfs2_append_rec_to_path(
3987 (unsigned long long)
3988 ocfs2_metadata_cache_owner(et
->et_ci
),
3989 le32_to_cpu(insert_rec
->e_cpos
),
3993 * No need to worry if the append is already in the
3997 left_path
= ocfs2_new_path_from_path(right_path
);
4004 ret
= ocfs2_find_path(et
->et_ci
, left_path
,
4012 * ocfs2_insert_path() will pass the left_path to the
4018 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, right_path
);
4024 ocfs2_adjust_rightmost_records(handle
, et
, right_path
, insert_rec
);
4026 *ret_left_path
= left_path
;
4030 ocfs2_free_path(left_path
);
4035 static void ocfs2_split_record(struct ocfs2_extent_tree
*et
,
4036 struct ocfs2_path
*left_path
,
4037 struct ocfs2_path
*right_path
,
4038 struct ocfs2_extent_rec
*split_rec
,
4039 enum ocfs2_split_type split
)
4042 u32 cpos
= le32_to_cpu(split_rec
->e_cpos
);
4043 struct ocfs2_extent_list
*left_el
= NULL
, *right_el
, *insert_el
, *el
;
4044 struct ocfs2_extent_rec
*rec
, *tmprec
;
4046 right_el
= path_leaf_el(right_path
);
4048 left_el
= path_leaf_el(left_path
);
4051 insert_el
= right_el
;
4052 index
= ocfs2_search_extent_list(el
, cpos
);
4054 if (index
== 0 && left_path
) {
4055 BUG_ON(ocfs2_is_empty_extent(&el
->l_recs
[0]));
4058 * This typically means that the record
4059 * started in the left path but moved to the
4060 * right as a result of rotation. We either
4061 * move the existing record to the left, or we
4062 * do the later insert there.
4064 * In this case, the left path should always
4065 * exist as the rotate code will have passed
4066 * it back for a post-insert update.
4069 if (split
== SPLIT_LEFT
) {
4071 * It's a left split. Since we know
4072 * that the rotate code gave us an
4073 * empty extent in the left path, we
4074 * can just do the insert there.
4076 insert_el
= left_el
;
4079 * Right split - we have to move the
4080 * existing record over to the left
4081 * leaf. The insert will be into the
4082 * newly created empty extent in the
4085 tmprec
= &right_el
->l_recs
[index
];
4086 ocfs2_rotate_leaf(left_el
, tmprec
);
4089 memset(tmprec
, 0, sizeof(*tmprec
));
4090 index
= ocfs2_search_extent_list(left_el
, cpos
);
4091 BUG_ON(index
== -1);
4096 BUG_ON(!ocfs2_is_empty_extent(&left_el
->l_recs
[0]));
4098 * Left path is easy - we can just allow the insert to
4102 insert_el
= left_el
;
4103 index
= ocfs2_search_extent_list(el
, cpos
);
4104 BUG_ON(index
== -1);
4107 rec
= &el
->l_recs
[index
];
4108 ocfs2_subtract_from_rec(ocfs2_metadata_cache_get_super(et
->et_ci
),
4109 split
, rec
, split_rec
);
4110 ocfs2_rotate_leaf(insert_el
, split_rec
);
4114 * This function only does inserts on an allocation b-tree. For tree
4115 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4117 * right_path is the path we want to do the actual insert
4118 * in. left_path should only be passed in if we need to update that
4119 * portion of the tree after an edge insert.
4121 static int ocfs2_insert_path(handle_t
*handle
,
4122 struct ocfs2_extent_tree
*et
,
4123 struct ocfs2_path
*left_path
,
4124 struct ocfs2_path
*right_path
,
4125 struct ocfs2_extent_rec
*insert_rec
,
4126 struct ocfs2_insert_type
*insert
)
4128 int ret
, subtree_index
;
4129 struct buffer_head
*leaf_bh
= path_leaf_bh(right_path
);
4133 * There's a chance that left_path got passed back to
4134 * us without being accounted for in the
4135 * journal. Extend our transaction here to be sure we
4136 * can change those blocks.
4138 ret
= ocfs2_extend_trans(handle
, left_path
->p_tree_depth
);
4144 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, left_path
);
4152 * Pass both paths to the journal. The majority of inserts
4153 * will be touching all components anyway.
4155 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, right_path
);
4161 if (insert
->ins_split
!= SPLIT_NONE
) {
4163 * We could call ocfs2_insert_at_leaf() for some types
4164 * of splits, but it's easier to just let one separate
4165 * function sort it all out.
4167 ocfs2_split_record(et
, left_path
, right_path
,
4168 insert_rec
, insert
->ins_split
);
4171 * Split might have modified either leaf and we don't
4172 * have a guarantee that the later edge insert will
4173 * dirty this for us.
4176 ocfs2_journal_dirty(handle
,
4177 path_leaf_bh(left_path
));
4179 ocfs2_insert_at_leaf(et
, insert_rec
, path_leaf_el(right_path
),
4182 ocfs2_journal_dirty(handle
, leaf_bh
);
4186 * The rotate code has indicated that we need to fix
4187 * up portions of the tree after the insert.
4189 * XXX: Should we extend the transaction here?
4191 subtree_index
= ocfs2_find_subtree_root(et
, left_path
,
4193 ocfs2_complete_edge_insert(handle
, left_path
, right_path
,
4202 static int ocfs2_do_insert_extent(handle_t
*handle
,
4203 struct ocfs2_extent_tree
*et
,
4204 struct ocfs2_extent_rec
*insert_rec
,
4205 struct ocfs2_insert_type
*type
)
4207 int ret
, rotate
= 0;
4209 struct ocfs2_path
*right_path
= NULL
;
4210 struct ocfs2_path
*left_path
= NULL
;
4211 struct ocfs2_extent_list
*el
;
4213 el
= et
->et_root_el
;
4215 ret
= ocfs2_et_root_journal_access(handle
, et
,
4216 OCFS2_JOURNAL_ACCESS_WRITE
);
4222 if (le16_to_cpu(el
->l_tree_depth
) == 0) {
4223 ocfs2_insert_at_leaf(et
, insert_rec
, el
, type
);
4224 goto out_update_clusters
;
4227 right_path
= ocfs2_new_path_from_et(et
);
4235 * Determine the path to start with. Rotations need the
4236 * rightmost path, everything else can go directly to the
4239 cpos
= le32_to_cpu(insert_rec
->e_cpos
);
4240 if (type
->ins_appending
== APPEND_NONE
&&
4241 type
->ins_contig
== CONTIG_NONE
) {
4246 ret
= ocfs2_find_path(et
->et_ci
, right_path
, cpos
);
4253 * Rotations and appends need special treatment - they modify
4254 * parts of the tree's above them.
4256 * Both might pass back a path immediate to the left of the
4257 * one being inserted to. This will be cause
4258 * ocfs2_insert_path() to modify the rightmost records of
4259 * left_path to account for an edge insert.
4261 * XXX: When modifying this code, keep in mind that an insert
4262 * can wind up skipping both of these two special cases...
4265 ret
= ocfs2_rotate_tree_right(handle
, et
, type
->ins_split
,
4266 le32_to_cpu(insert_rec
->e_cpos
),
4267 right_path
, &left_path
);
4274 * ocfs2_rotate_tree_right() might have extended the
4275 * transaction without re-journaling our tree root.
4277 ret
= ocfs2_et_root_journal_access(handle
, et
,
4278 OCFS2_JOURNAL_ACCESS_WRITE
);
4283 } else if (type
->ins_appending
== APPEND_TAIL
4284 && type
->ins_contig
!= CONTIG_LEFT
) {
4285 ret
= ocfs2_append_rec_to_path(handle
, et
, insert_rec
,
4286 right_path
, &left_path
);
4293 ret
= ocfs2_insert_path(handle
, et
, left_path
, right_path
,
4300 out_update_clusters
:
4301 if (type
->ins_split
== SPLIT_NONE
)
4302 ocfs2_et_update_clusters(et
,
4303 le16_to_cpu(insert_rec
->e_leaf_clusters
));
4305 ocfs2_journal_dirty(handle
, et
->et_root_bh
);
4308 ocfs2_free_path(left_path
);
4309 ocfs2_free_path(right_path
);
4314 static int ocfs2_figure_merge_contig_type(struct ocfs2_extent_tree
*et
,
4315 struct ocfs2_path
*path
,
4316 struct ocfs2_extent_list
*el
, int index
,
4317 struct ocfs2_extent_rec
*split_rec
,
4318 struct ocfs2_merge_ctxt
*ctxt
)
4321 enum ocfs2_contig_type ret
= CONTIG_NONE
;
4322 u32 left_cpos
, right_cpos
;
4323 struct ocfs2_extent_rec
*rec
= NULL
;
4324 struct ocfs2_extent_list
*new_el
;
4325 struct ocfs2_path
*left_path
= NULL
, *right_path
= NULL
;
4326 struct buffer_head
*bh
;
4327 struct ocfs2_extent_block
*eb
;
4328 struct super_block
*sb
= ocfs2_metadata_cache_get_super(et
->et_ci
);
4331 rec
= &el
->l_recs
[index
- 1];
4332 } else if (path
->p_tree_depth
> 0) {
4333 status
= ocfs2_find_cpos_for_left_leaf(sb
, path
, &left_cpos
);
4337 if (left_cpos
!= 0) {
4338 left_path
= ocfs2_new_path_from_path(path
);
4345 status
= ocfs2_find_path(et
->et_ci
, left_path
,
4348 goto free_left_path
;
4350 new_el
= path_leaf_el(left_path
);
4352 if (le16_to_cpu(new_el
->l_next_free_rec
) !=
4353 le16_to_cpu(new_el
->l_count
)) {
4354 bh
= path_leaf_bh(left_path
);
4355 eb
= (struct ocfs2_extent_block
*)bh
->b_data
;
4357 "Extent block #%llu has an "
4358 "invalid l_next_free_rec of "
4359 "%d. It should have "
4360 "matched the l_count of %d",
4361 (unsigned long long)le64_to_cpu(eb
->h_blkno
),
4362 le16_to_cpu(new_el
->l_next_free_rec
),
4363 le16_to_cpu(new_el
->l_count
));
4365 goto free_left_path
;
4367 rec
= &new_el
->l_recs
[
4368 le16_to_cpu(new_el
->l_next_free_rec
) - 1];
4373 * We're careful to check for an empty extent record here -
4374 * the merge code will know what to do if it sees one.
4377 if (index
== 1 && ocfs2_is_empty_extent(rec
)) {
4378 if (split_rec
->e_cpos
== el
->l_recs
[index
].e_cpos
)
4381 ret
= ocfs2_et_extent_contig(et
, rec
, split_rec
);
4386 if (index
< (le16_to_cpu(el
->l_next_free_rec
) - 1))
4387 rec
= &el
->l_recs
[index
+ 1];
4388 else if (le16_to_cpu(el
->l_next_free_rec
) == le16_to_cpu(el
->l_count
) &&
4389 path
->p_tree_depth
> 0) {
4390 status
= ocfs2_find_cpos_for_right_leaf(sb
, path
, &right_cpos
);
4392 goto free_left_path
;
4394 if (right_cpos
== 0)
4395 goto free_left_path
;
4397 right_path
= ocfs2_new_path_from_path(path
);
4401 goto free_left_path
;
4404 status
= ocfs2_find_path(et
->et_ci
, right_path
, right_cpos
);
4406 goto free_right_path
;
4408 new_el
= path_leaf_el(right_path
);
4409 rec
= &new_el
->l_recs
[0];
4410 if (ocfs2_is_empty_extent(rec
)) {
4411 if (le16_to_cpu(new_el
->l_next_free_rec
) <= 1) {
4412 bh
= path_leaf_bh(right_path
);
4413 eb
= (struct ocfs2_extent_block
*)bh
->b_data
;
4415 "Extent block #%llu has an "
4416 "invalid l_next_free_rec of %d",
4417 (unsigned long long)le64_to_cpu(eb
->h_blkno
),
4418 le16_to_cpu(new_el
->l_next_free_rec
));
4420 goto free_right_path
;
4422 rec
= &new_el
->l_recs
[1];
4427 enum ocfs2_contig_type contig_type
;
4429 contig_type
= ocfs2_et_extent_contig(et
, rec
, split_rec
);
4431 if (contig_type
== CONTIG_LEFT
&& ret
== CONTIG_RIGHT
)
4432 ret
= CONTIG_LEFTRIGHT
;
4433 else if (ret
== CONTIG_NONE
)
4438 ocfs2_free_path(right_path
);
4440 ocfs2_free_path(left_path
);
4443 ctxt
->c_contig_type
= ret
;
4448 static void ocfs2_figure_contig_type(struct ocfs2_extent_tree
*et
,
4449 struct ocfs2_insert_type
*insert
,
4450 struct ocfs2_extent_list
*el
,
4451 struct ocfs2_extent_rec
*insert_rec
)
4454 enum ocfs2_contig_type contig_type
= CONTIG_NONE
;
4456 BUG_ON(le16_to_cpu(el
->l_tree_depth
) != 0);
4458 for(i
= 0; i
< le16_to_cpu(el
->l_next_free_rec
); i
++) {
4459 contig_type
= ocfs2_et_extent_contig(et
, &el
->l_recs
[i
],
4461 if (contig_type
!= CONTIG_NONE
) {
4462 insert
->ins_contig_index
= i
;
4466 insert
->ins_contig
= contig_type
;
4468 if (insert
->ins_contig
!= CONTIG_NONE
) {
4469 struct ocfs2_extent_rec
*rec
=
4470 &el
->l_recs
[insert
->ins_contig_index
];
4471 unsigned int len
= le16_to_cpu(rec
->e_leaf_clusters
) +
4472 le16_to_cpu(insert_rec
->e_leaf_clusters
);
4475 * Caller might want us to limit the size of extents, don't
4476 * calculate contiguousness if we might exceed that limit.
4478 if (et
->et_max_leaf_clusters
&&
4479 (len
> et
->et_max_leaf_clusters
))
4480 insert
->ins_contig
= CONTIG_NONE
;
4485 * This should only be called against the righmost leaf extent list.
4487 * ocfs2_figure_appending_type() will figure out whether we'll have to
4488 * insert at the tail of the rightmost leaf.
4490 * This should also work against the root extent list for tree's with 0
4491 * depth. If we consider the root extent list to be the rightmost leaf node
4492 * then the logic here makes sense.
4494 static void ocfs2_figure_appending_type(struct ocfs2_insert_type
*insert
,
4495 struct ocfs2_extent_list
*el
,
4496 struct ocfs2_extent_rec
*insert_rec
)
4499 u32 cpos
= le32_to_cpu(insert_rec
->e_cpos
);
4500 struct ocfs2_extent_rec
*rec
;
4502 insert
->ins_appending
= APPEND_NONE
;
4504 BUG_ON(le16_to_cpu(el
->l_tree_depth
) != 0);
4506 if (!el
->l_next_free_rec
)
4507 goto set_tail_append
;
4509 if (ocfs2_is_empty_extent(&el
->l_recs
[0])) {
4510 /* Were all records empty? */
4511 if (le16_to_cpu(el
->l_next_free_rec
) == 1)
4512 goto set_tail_append
;
4515 i
= le16_to_cpu(el
->l_next_free_rec
) - 1;
4516 rec
= &el
->l_recs
[i
];
4519 (le32_to_cpu(rec
->e_cpos
) + le16_to_cpu(rec
->e_leaf_clusters
)))
4520 goto set_tail_append
;
4525 insert
->ins_appending
= APPEND_TAIL
;
4529 * Helper function called at the beginning of an insert.
4531 * This computes a few things that are commonly used in the process of
4532 * inserting into the btree:
4533 * - Whether the new extent is contiguous with an existing one.
4534 * - The current tree depth.
4535 * - Whether the insert is an appending one.
4536 * - The total # of free records in the tree.
4538 * All of the information is stored on the ocfs2_insert_type
4541 static int ocfs2_figure_insert_type(struct ocfs2_extent_tree
*et
,
4542 struct buffer_head
**last_eb_bh
,
4543 struct ocfs2_extent_rec
*insert_rec
,
4545 struct ocfs2_insert_type
*insert
)
4548 struct ocfs2_extent_block
*eb
;
4549 struct ocfs2_extent_list
*el
;
4550 struct ocfs2_path
*path
= NULL
;
4551 struct buffer_head
*bh
= NULL
;
4553 insert
->ins_split
= SPLIT_NONE
;
4555 el
= et
->et_root_el
;
4556 insert
->ins_tree_depth
= le16_to_cpu(el
->l_tree_depth
);
4558 if (el
->l_tree_depth
) {
4560 * If we have tree depth, we read in the
4561 * rightmost extent block ahead of time as
4562 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4563 * may want it later.
4565 ret
= ocfs2_read_extent_block(et
->et_ci
,
4566 ocfs2_et_get_last_eb_blk(et
),
4572 eb
= (struct ocfs2_extent_block
*) bh
->b_data
;
4577 * Unless we have a contiguous insert, we'll need to know if
4578 * there is room left in our allocation tree for another
4581 * XXX: This test is simplistic, we can search for empty
4582 * extent records too.
4584 *free_records
= le16_to_cpu(el
->l_count
) -
4585 le16_to_cpu(el
->l_next_free_rec
);
4587 if (!insert
->ins_tree_depth
) {
4588 ocfs2_figure_contig_type(et
, insert
, el
, insert_rec
);
4589 ocfs2_figure_appending_type(insert
, el
, insert_rec
);
4593 path
= ocfs2_new_path_from_et(et
);
4601 * In the case that we're inserting past what the tree
4602 * currently accounts for, ocfs2_find_path() will return for
4603 * us the rightmost tree path. This is accounted for below in
4604 * the appending code.
4606 ret
= ocfs2_find_path(et
->et_ci
, path
, le32_to_cpu(insert_rec
->e_cpos
));
4612 el
= path_leaf_el(path
);
4615 * Now that we have the path, there's two things we want to determine:
4616 * 1) Contiguousness (also set contig_index if this is so)
4618 * 2) Are we doing an append? We can trivially break this up
4619 * into two types of appends: simple record append, or a
4620 * rotate inside the tail leaf.
4622 ocfs2_figure_contig_type(et
, insert
, el
, insert_rec
);
4625 * The insert code isn't quite ready to deal with all cases of
4626 * left contiguousness. Specifically, if it's an insert into
4627 * the 1st record in a leaf, it will require the adjustment of
4628 * cluster count on the last record of the path directly to it's
4629 * left. For now, just catch that case and fool the layers
4630 * above us. This works just fine for tree_depth == 0, which
4631 * is why we allow that above.
4633 if (insert
->ins_contig
== CONTIG_LEFT
&&
4634 insert
->ins_contig_index
== 0)
4635 insert
->ins_contig
= CONTIG_NONE
;
4638 * Ok, so we can simply compare against last_eb to figure out
4639 * whether the path doesn't exist. This will only happen in
4640 * the case that we're doing a tail append, so maybe we can
4641 * take advantage of that information somehow.
4643 if (ocfs2_et_get_last_eb_blk(et
) ==
4644 path_leaf_bh(path
)->b_blocknr
) {
4646 * Ok, ocfs2_find_path() returned us the rightmost
4647 * tree path. This might be an appending insert. There are
4649 * 1) We're doing a true append at the tail:
4650 * -This might even be off the end of the leaf
4651 * 2) We're "appending" by rotating in the tail
4653 ocfs2_figure_appending_type(insert
, el
, insert_rec
);
4657 ocfs2_free_path(path
);
4667 * Insert an extent into a btree.
4669 * The caller needs to update the owning btree's cluster count.
4671 int ocfs2_insert_extent(handle_t
*handle
,
4672 struct ocfs2_extent_tree
*et
,
4677 struct ocfs2_alloc_context
*meta_ac
)
4680 int uninitialized_var(free_records
);
4681 struct buffer_head
*last_eb_bh
= NULL
;
4682 struct ocfs2_insert_type insert
= {0, };
4683 struct ocfs2_extent_rec rec
;
4685 trace_ocfs2_insert_extent_start(
4686 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
4687 cpos
, new_clusters
);
4689 memset(&rec
, 0, sizeof(rec
));
4690 rec
.e_cpos
= cpu_to_le32(cpos
);
4691 rec
.e_blkno
= cpu_to_le64(start_blk
);
4692 rec
.e_leaf_clusters
= cpu_to_le16(new_clusters
);
4693 rec
.e_flags
= flags
;
4694 status
= ocfs2_et_insert_check(et
, &rec
);
4700 status
= ocfs2_figure_insert_type(et
, &last_eb_bh
, &rec
,
4701 &free_records
, &insert
);
4707 trace_ocfs2_insert_extent(insert
.ins_appending
, insert
.ins_contig
,
4708 insert
.ins_contig_index
, free_records
,
4709 insert
.ins_tree_depth
);
4711 if (insert
.ins_contig
== CONTIG_NONE
&& free_records
== 0) {
4712 status
= ocfs2_grow_tree(handle
, et
,
4713 &insert
.ins_tree_depth
, &last_eb_bh
,
4721 /* Finally, we can add clusters. This might rotate the tree for us. */
4722 status
= ocfs2_do_insert_extent(handle
, et
, &rec
, &insert
);
4726 ocfs2_et_extent_map_insert(et
, &rec
);
4735 * Allcate and add clusters into the extent b-tree.
4736 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4737 * The extent b-tree's root is specified by et, and
4738 * it is not limited to the file storage. Any extent tree can use this
4739 * function if it implements the proper ocfs2_extent_tree.
4741 int ocfs2_add_clusters_in_btree(handle_t
*handle
,
4742 struct ocfs2_extent_tree
*et
,
4743 u32
*logical_offset
,
4744 u32 clusters_to_add
,
4746 struct ocfs2_alloc_context
*data_ac
,
4747 struct ocfs2_alloc_context
*meta_ac
,
4748 enum ocfs2_alloc_restarted
*reason_ret
)
4750 int status
= 0, err
= 0;
4753 enum ocfs2_alloc_restarted reason
= RESTART_NONE
;
4754 u32 bit_off
, num_bits
;
4757 struct ocfs2_super
*osb
=
4758 OCFS2_SB(ocfs2_metadata_cache_get_super(et
->et_ci
));
4760 BUG_ON(!clusters_to_add
);
4763 flags
= OCFS2_EXT_UNWRITTEN
;
4765 free_extents
= ocfs2_num_free_extents(osb
, et
);
4766 if (free_extents
< 0) {
4767 status
= free_extents
;
4772 /* there are two cases which could cause us to EAGAIN in the
4773 * we-need-more-metadata case:
4774 * 1) we haven't reserved *any*
4775 * 2) we are so fragmented, we've needed to add metadata too
4777 if (!free_extents
&& !meta_ac
) {
4780 reason
= RESTART_META
;
4782 } else if ((!free_extents
)
4783 && (ocfs2_alloc_context_bits_left(meta_ac
)
4784 < ocfs2_extend_meta_needed(et
->et_root_el
))) {
4787 reason
= RESTART_META
;
4791 status
= __ocfs2_claim_clusters(handle
, data_ac
, 1,
4792 clusters_to_add
, &bit_off
, &num_bits
);
4794 if (status
!= -ENOSPC
)
4799 BUG_ON(num_bits
> clusters_to_add
);
4801 /* reserve our write early -- insert_extent may update the tree root */
4802 status
= ocfs2_et_root_journal_access(handle
, et
,
4803 OCFS2_JOURNAL_ACCESS_WRITE
);
4810 block
= ocfs2_clusters_to_blocks(osb
->sb
, bit_off
);
4811 trace_ocfs2_add_clusters_in_btree(
4812 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
4814 status
= ocfs2_insert_extent(handle
, et
, *logical_offset
, block
,
4815 num_bits
, flags
, meta_ac
);
4822 ocfs2_journal_dirty(handle
, et
->et_root_bh
);
4824 clusters_to_add
-= num_bits
;
4825 *logical_offset
+= num_bits
;
4827 if (clusters_to_add
) {
4828 err
= clusters_to_add
;
4830 reason
= RESTART_TRANS
;
4835 if (data_ac
->ac_which
== OCFS2_AC_USE_LOCAL
)
4836 ocfs2_free_local_alloc_bits(osb
, handle
, data_ac
,
4839 ocfs2_free_clusters(handle
,
4842 ocfs2_clusters_to_blocks(osb
->sb
, bit_off
),
4848 *reason_ret
= reason
;
4849 trace_ocfs2_add_clusters_in_btree_ret(status
, reason
, err
);
4853 static void ocfs2_make_right_split_rec(struct super_block
*sb
,
4854 struct ocfs2_extent_rec
*split_rec
,
4856 struct ocfs2_extent_rec
*rec
)
4858 u32 rec_cpos
= le32_to_cpu(rec
->e_cpos
);
4859 u32 rec_range
= rec_cpos
+ le16_to_cpu(rec
->e_leaf_clusters
);
4861 memset(split_rec
, 0, sizeof(struct ocfs2_extent_rec
));
4863 split_rec
->e_cpos
= cpu_to_le32(cpos
);
4864 split_rec
->e_leaf_clusters
= cpu_to_le16(rec_range
- cpos
);
4866 split_rec
->e_blkno
= rec
->e_blkno
;
4867 le64_add_cpu(&split_rec
->e_blkno
,
4868 ocfs2_clusters_to_blocks(sb
, cpos
- rec_cpos
));
4870 split_rec
->e_flags
= rec
->e_flags
;
4873 static int ocfs2_split_and_insert(handle_t
*handle
,
4874 struct ocfs2_extent_tree
*et
,
4875 struct ocfs2_path
*path
,
4876 struct buffer_head
**last_eb_bh
,
4878 struct ocfs2_extent_rec
*orig_split_rec
,
4879 struct ocfs2_alloc_context
*meta_ac
)
4882 unsigned int insert_range
, rec_range
, do_leftright
= 0;
4883 struct ocfs2_extent_rec tmprec
;
4884 struct ocfs2_extent_list
*rightmost_el
;
4885 struct ocfs2_extent_rec rec
;
4886 struct ocfs2_extent_rec split_rec
= *orig_split_rec
;
4887 struct ocfs2_insert_type insert
;
4888 struct ocfs2_extent_block
*eb
;
4892 * Store a copy of the record on the stack - it might move
4893 * around as the tree is manipulated below.
4895 rec
= path_leaf_el(path
)->l_recs
[split_index
];
4897 rightmost_el
= et
->et_root_el
;
4899 depth
= le16_to_cpu(rightmost_el
->l_tree_depth
);
4901 BUG_ON(!(*last_eb_bh
));
4902 eb
= (struct ocfs2_extent_block
*) (*last_eb_bh
)->b_data
;
4903 rightmost_el
= &eb
->h_list
;
4906 if (le16_to_cpu(rightmost_el
->l_next_free_rec
) ==
4907 le16_to_cpu(rightmost_el
->l_count
)) {
4908 ret
= ocfs2_grow_tree(handle
, et
,
4909 &depth
, last_eb_bh
, meta_ac
);
4916 memset(&insert
, 0, sizeof(struct ocfs2_insert_type
));
4917 insert
.ins_appending
= APPEND_NONE
;
4918 insert
.ins_contig
= CONTIG_NONE
;
4919 insert
.ins_tree_depth
= depth
;
4921 insert_range
= le32_to_cpu(split_rec
.e_cpos
) +
4922 le16_to_cpu(split_rec
.e_leaf_clusters
);
4923 rec_range
= le32_to_cpu(rec
.e_cpos
) +
4924 le16_to_cpu(rec
.e_leaf_clusters
);
4926 if (split_rec
.e_cpos
== rec
.e_cpos
) {
4927 insert
.ins_split
= SPLIT_LEFT
;
4928 } else if (insert_range
== rec_range
) {
4929 insert
.ins_split
= SPLIT_RIGHT
;
4932 * Left/right split. We fake this as a right split
4933 * first and then make a second pass as a left split.
4935 insert
.ins_split
= SPLIT_RIGHT
;
4937 ocfs2_make_right_split_rec(ocfs2_metadata_cache_get_super(et
->et_ci
),
4938 &tmprec
, insert_range
, &rec
);
4942 BUG_ON(do_leftright
);
4946 ret
= ocfs2_do_insert_extent(handle
, et
, &split_rec
, &insert
);
4952 if (do_leftright
== 1) {
4954 struct ocfs2_extent_list
*el
;
4957 split_rec
= *orig_split_rec
;
4959 ocfs2_reinit_path(path
, 1);
4961 cpos
= le32_to_cpu(split_rec
.e_cpos
);
4962 ret
= ocfs2_find_path(et
->et_ci
, path
, cpos
);
4968 el
= path_leaf_el(path
);
4969 split_index
= ocfs2_search_extent_list(el
, cpos
);
4970 if (split_index
== -1) {
4971 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
4972 "Owner %llu has an extent at cpos %u "
4973 "which can no longer be found.\n",
4974 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
4986 static int ocfs2_replace_extent_rec(handle_t
*handle
,
4987 struct ocfs2_extent_tree
*et
,
4988 struct ocfs2_path
*path
,
4989 struct ocfs2_extent_list
*el
,
4991 struct ocfs2_extent_rec
*split_rec
)
4995 ret
= ocfs2_path_bh_journal_access(handle
, et
->et_ci
, path
,
4996 path_num_items(path
) - 1);
5002 el
->l_recs
[split_index
] = *split_rec
;
5004 ocfs2_journal_dirty(handle
, path_leaf_bh(path
));
5010 * Split part or all of the extent record at split_index in the leaf
5011 * pointed to by path. Merge with the contiguous extent record if needed.
5013 * Care is taken to handle contiguousness so as to not grow the tree.
5015 * meta_ac is not strictly necessary - we only truly need it if growth
5016 * of the tree is required. All other cases will degrade into a less
5017 * optimal tree layout.
5019 * last_eb_bh should be the rightmost leaf block for any extent
5020 * btree. Since a split may grow the tree or a merge might shrink it,
5021 * the caller cannot trust the contents of that buffer after this call.
5023 * This code is optimized for readability - several passes might be
5024 * made over certain portions of the tree. All of those blocks will
5025 * have been brought into cache (and pinned via the journal), so the
5026 * extra overhead is not expressed in terms of disk reads.
5028 int ocfs2_split_extent(handle_t
*handle
,
5029 struct ocfs2_extent_tree
*et
,
5030 struct ocfs2_path
*path
,
5032 struct ocfs2_extent_rec
*split_rec
,
5033 struct ocfs2_alloc_context
*meta_ac
,
5034 struct ocfs2_cached_dealloc_ctxt
*dealloc
)
5037 struct ocfs2_extent_list
*el
= path_leaf_el(path
);
5038 struct buffer_head
*last_eb_bh
= NULL
;
5039 struct ocfs2_extent_rec
*rec
= &el
->l_recs
[split_index
];
5040 struct ocfs2_merge_ctxt ctxt
;
5041 struct ocfs2_extent_list
*rightmost_el
;
5043 if (le32_to_cpu(rec
->e_cpos
) > le32_to_cpu(split_rec
->e_cpos
) ||
5044 ((le32_to_cpu(rec
->e_cpos
) + le16_to_cpu(rec
->e_leaf_clusters
)) <
5045 (le32_to_cpu(split_rec
->e_cpos
) + le16_to_cpu(split_rec
->e_leaf_clusters
)))) {
5051 ret
= ocfs2_figure_merge_contig_type(et
, path
, el
,
5061 * The core merge / split code wants to know how much room is
5062 * left in this allocation tree, so we pass the
5063 * rightmost extent list.
5065 if (path
->p_tree_depth
) {
5066 struct ocfs2_extent_block
*eb
;
5068 ret
= ocfs2_read_extent_block(et
->et_ci
,
5069 ocfs2_et_get_last_eb_blk(et
),
5076 eb
= (struct ocfs2_extent_block
*) last_eb_bh
->b_data
;
5077 rightmost_el
= &eb
->h_list
;
5079 rightmost_el
= path_root_el(path
);
5081 if (rec
->e_cpos
== split_rec
->e_cpos
&&
5082 rec
->e_leaf_clusters
== split_rec
->e_leaf_clusters
)
5083 ctxt
.c_split_covers_rec
= 1;
5085 ctxt
.c_split_covers_rec
= 0;
5087 ctxt
.c_has_empty_extent
= ocfs2_is_empty_extent(&el
->l_recs
[0]);
5089 trace_ocfs2_split_extent(split_index
, ctxt
.c_contig_type
,
5090 ctxt
.c_has_empty_extent
,
5091 ctxt
.c_split_covers_rec
);
5093 if (ctxt
.c_contig_type
== CONTIG_NONE
) {
5094 if (ctxt
.c_split_covers_rec
)
5095 ret
= ocfs2_replace_extent_rec(handle
, et
, path
, el
,
5096 split_index
, split_rec
);
5098 ret
= ocfs2_split_and_insert(handle
, et
, path
,
5099 &last_eb_bh
, split_index
,
5100 split_rec
, meta_ac
);
5104 ret
= ocfs2_try_to_merge_extent(handle
, et
, path
,
5105 split_index
, split_rec
,
5117 * Change the flags of the already-existing extent at cpos for len clusters.
5119 * new_flags: the flags we want to set.
5120 * clear_flags: the flags we want to clear.
5121 * phys: the new physical offset we want this new extent starts from.
5123 * If the existing extent is larger than the request, initiate a
5124 * split. An attempt will be made at merging with adjacent extents.
5126 * The caller is responsible for passing down meta_ac if we'll need it.
5128 int ocfs2_change_extent_flag(handle_t
*handle
,
5129 struct ocfs2_extent_tree
*et
,
5130 u32 cpos
, u32 len
, u32 phys
,
5131 struct ocfs2_alloc_context
*meta_ac
,
5132 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
5133 int new_flags
, int clear_flags
)
5136 struct super_block
*sb
= ocfs2_metadata_cache_get_super(et
->et_ci
);
5137 u64 start_blkno
= ocfs2_clusters_to_blocks(sb
, phys
);
5138 struct ocfs2_extent_rec split_rec
;
5139 struct ocfs2_path
*left_path
= NULL
;
5140 struct ocfs2_extent_list
*el
;
5141 struct ocfs2_extent_rec
*rec
;
5143 left_path
= ocfs2_new_path_from_et(et
);
5150 ret
= ocfs2_find_path(et
->et_ci
, left_path
, cpos
);
5155 el
= path_leaf_el(left_path
);
5157 index
= ocfs2_search_extent_list(el
, cpos
);
5160 "Owner %llu has an extent at cpos %u which can no "
5161 "longer be found.\n",
5162 (unsigned long long)
5163 ocfs2_metadata_cache_owner(et
->et_ci
), cpos
);
5169 rec
= &el
->l_recs
[index
];
5170 if (new_flags
&& (rec
->e_flags
& new_flags
)) {
5171 mlog(ML_ERROR
, "Owner %llu tried to set %d flags on an "
5172 "extent that already had them",
5173 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5178 if (clear_flags
&& !(rec
->e_flags
& clear_flags
)) {
5179 mlog(ML_ERROR
, "Owner %llu tried to clear %d flags on an "
5180 "extent that didn't have them",
5181 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5186 memset(&split_rec
, 0, sizeof(struct ocfs2_extent_rec
));
5187 split_rec
.e_cpos
= cpu_to_le32(cpos
);
5188 split_rec
.e_leaf_clusters
= cpu_to_le16(len
);
5189 split_rec
.e_blkno
= cpu_to_le64(start_blkno
);
5190 split_rec
.e_flags
= rec
->e_flags
;
5192 split_rec
.e_flags
|= new_flags
;
5194 split_rec
.e_flags
&= ~clear_flags
;
5196 ret
= ocfs2_split_extent(handle
, et
, left_path
,
5197 index
, &split_rec
, meta_ac
,
5203 ocfs2_free_path(left_path
);
5209 * Mark the already-existing extent at cpos as written for len clusters.
5210 * This removes the unwritten extent flag.
5212 * If the existing extent is larger than the request, initiate a
5213 * split. An attempt will be made at merging with adjacent extents.
5215 * The caller is responsible for passing down meta_ac if we'll need it.
5217 int ocfs2_mark_extent_written(struct inode
*inode
,
5218 struct ocfs2_extent_tree
*et
,
5219 handle_t
*handle
, u32 cpos
, u32 len
, u32 phys
,
5220 struct ocfs2_alloc_context
*meta_ac
,
5221 struct ocfs2_cached_dealloc_ctxt
*dealloc
)
5225 trace_ocfs2_mark_extent_written(
5226 (unsigned long long)OCFS2_I(inode
)->ip_blkno
,
5229 if (!ocfs2_writes_unwritten_extents(OCFS2_SB(inode
->i_sb
))) {
5230 ocfs2_error(inode
->i_sb
, "Inode %llu has unwritten extents "
5231 "that are being written to, but the feature bit "
5232 "is not set in the super block.",
5233 (unsigned long long)OCFS2_I(inode
)->ip_blkno
);
5239 * XXX: This should be fixed up so that we just re-insert the
5240 * next extent records.
5242 ocfs2_et_extent_map_truncate(et
, 0);
5244 ret
= ocfs2_change_extent_flag(handle
, et
, cpos
,
5245 len
, phys
, meta_ac
, dealloc
,
5246 0, OCFS2_EXT_UNWRITTEN
);
5254 static int ocfs2_split_tree(handle_t
*handle
, struct ocfs2_extent_tree
*et
,
5255 struct ocfs2_path
*path
,
5256 int index
, u32 new_range
,
5257 struct ocfs2_alloc_context
*meta_ac
)
5259 int ret
, depth
, credits
;
5260 struct buffer_head
*last_eb_bh
= NULL
;
5261 struct ocfs2_extent_block
*eb
;
5262 struct ocfs2_extent_list
*rightmost_el
, *el
;
5263 struct ocfs2_extent_rec split_rec
;
5264 struct ocfs2_extent_rec
*rec
;
5265 struct ocfs2_insert_type insert
;
5268 * Setup the record to split before we grow the tree.
5270 el
= path_leaf_el(path
);
5271 rec
= &el
->l_recs
[index
];
5272 ocfs2_make_right_split_rec(ocfs2_metadata_cache_get_super(et
->et_ci
),
5273 &split_rec
, new_range
, rec
);
5275 depth
= path
->p_tree_depth
;
5277 ret
= ocfs2_read_extent_block(et
->et_ci
,
5278 ocfs2_et_get_last_eb_blk(et
),
5285 eb
= (struct ocfs2_extent_block
*) last_eb_bh
->b_data
;
5286 rightmost_el
= &eb
->h_list
;
5288 rightmost_el
= path_leaf_el(path
);
5290 credits
= path
->p_tree_depth
+
5291 ocfs2_extend_meta_needed(et
->et_root_el
);
5292 ret
= ocfs2_extend_trans(handle
, credits
);
5298 if (le16_to_cpu(rightmost_el
->l_next_free_rec
) ==
5299 le16_to_cpu(rightmost_el
->l_count
)) {
5300 ret
= ocfs2_grow_tree(handle
, et
, &depth
, &last_eb_bh
,
5308 memset(&insert
, 0, sizeof(struct ocfs2_insert_type
));
5309 insert
.ins_appending
= APPEND_NONE
;
5310 insert
.ins_contig
= CONTIG_NONE
;
5311 insert
.ins_split
= SPLIT_RIGHT
;
5312 insert
.ins_tree_depth
= depth
;
5314 ret
= ocfs2_do_insert_extent(handle
, et
, &split_rec
, &insert
);
5323 static int ocfs2_truncate_rec(handle_t
*handle
,
5324 struct ocfs2_extent_tree
*et
,
5325 struct ocfs2_path
*path
, int index
,
5326 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
5330 u32 left_cpos
, rec_range
, trunc_range
;
5331 int wants_rotate
= 0, is_rightmost_tree_rec
= 0;
5332 struct super_block
*sb
= ocfs2_metadata_cache_get_super(et
->et_ci
);
5333 struct ocfs2_path
*left_path
= NULL
;
5334 struct ocfs2_extent_list
*el
= path_leaf_el(path
);
5335 struct ocfs2_extent_rec
*rec
;
5336 struct ocfs2_extent_block
*eb
;
5338 if (ocfs2_is_empty_extent(&el
->l_recs
[0]) && index
> 0) {
5339 ret
= ocfs2_rotate_tree_left(handle
, et
, path
, dealloc
);
5348 if (index
== (le16_to_cpu(el
->l_next_free_rec
) - 1) &&
5349 path
->p_tree_depth
) {
5351 * Check whether this is the rightmost tree record. If
5352 * we remove all of this record or part of its right
5353 * edge then an update of the record lengths above it
5356 eb
= (struct ocfs2_extent_block
*)path_leaf_bh(path
)->b_data
;
5357 if (eb
->h_next_leaf_blk
== 0)
5358 is_rightmost_tree_rec
= 1;
5361 rec
= &el
->l_recs
[index
];
5362 if (index
== 0 && path
->p_tree_depth
&&
5363 le32_to_cpu(rec
->e_cpos
) == cpos
) {
5365 * Changing the leftmost offset (via partial or whole
5366 * record truncate) of an interior (or rightmost) path
5367 * means we have to update the subtree that is formed
5368 * by this leaf and the one to it's left.
5370 * There are two cases we can skip:
5371 * 1) Path is the leftmost one in our btree.
5372 * 2) The leaf is rightmost and will be empty after
5373 * we remove the extent record - the rotate code
5374 * knows how to update the newly formed edge.
5377 ret
= ocfs2_find_cpos_for_left_leaf(sb
, path
, &left_cpos
);
5383 if (left_cpos
&& le16_to_cpu(el
->l_next_free_rec
) > 1) {
5384 left_path
= ocfs2_new_path_from_path(path
);
5391 ret
= ocfs2_find_path(et
->et_ci
, left_path
,
5400 ret
= ocfs2_extend_rotate_transaction(handle
, 0,
5401 handle
->h_buffer_credits
,
5408 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, path
);
5414 ret
= ocfs2_journal_access_path(et
->et_ci
, handle
, left_path
);
5420 rec_range
= le32_to_cpu(rec
->e_cpos
) + ocfs2_rec_clusters(el
, rec
);
5421 trunc_range
= cpos
+ len
;
5423 if (le32_to_cpu(rec
->e_cpos
) == cpos
&& rec_range
== trunc_range
) {
5426 memset(rec
, 0, sizeof(*rec
));
5427 ocfs2_cleanup_merge(el
, index
);
5430 next_free
= le16_to_cpu(el
->l_next_free_rec
);
5431 if (is_rightmost_tree_rec
&& next_free
> 1) {
5433 * We skip the edge update if this path will
5434 * be deleted by the rotate code.
5436 rec
= &el
->l_recs
[next_free
- 1];
5437 ocfs2_adjust_rightmost_records(handle
, et
, path
,
5440 } else if (le32_to_cpu(rec
->e_cpos
) == cpos
) {
5441 /* Remove leftmost portion of the record. */
5442 le32_add_cpu(&rec
->e_cpos
, len
);
5443 le64_add_cpu(&rec
->e_blkno
, ocfs2_clusters_to_blocks(sb
, len
));
5444 le16_add_cpu(&rec
->e_leaf_clusters
, -len
);
5445 } else if (rec_range
== trunc_range
) {
5446 /* Remove rightmost portion of the record */
5447 le16_add_cpu(&rec
->e_leaf_clusters
, -len
);
5448 if (is_rightmost_tree_rec
)
5449 ocfs2_adjust_rightmost_records(handle
, et
, path
, rec
);
5451 /* Caller should have trapped this. */
5452 mlog(ML_ERROR
, "Owner %llu: Invalid record truncate: (%u, %u) "
5454 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5455 le32_to_cpu(rec
->e_cpos
),
5456 le16_to_cpu(rec
->e_leaf_clusters
), cpos
, len
);
5463 subtree_index
= ocfs2_find_subtree_root(et
, left_path
, path
);
5464 ocfs2_complete_edge_insert(handle
, left_path
, path
,
5468 ocfs2_journal_dirty(handle
, path_leaf_bh(path
));
5470 ret
= ocfs2_rotate_tree_left(handle
, et
, path
, dealloc
);
5477 ocfs2_free_path(left_path
);
5481 int ocfs2_remove_extent(handle_t
*handle
,
5482 struct ocfs2_extent_tree
*et
,
5484 struct ocfs2_alloc_context
*meta_ac
,
5485 struct ocfs2_cached_dealloc_ctxt
*dealloc
)
5488 u32 rec_range
, trunc_range
;
5489 struct ocfs2_extent_rec
*rec
;
5490 struct ocfs2_extent_list
*el
;
5491 struct ocfs2_path
*path
= NULL
;
5494 * XXX: Why are we truncating to 0 instead of wherever this
5497 ocfs2_et_extent_map_truncate(et
, 0);
5499 path
= ocfs2_new_path_from_et(et
);
5506 ret
= ocfs2_find_path(et
->et_ci
, path
, cpos
);
5512 el
= path_leaf_el(path
);
5513 index
= ocfs2_search_extent_list(el
, cpos
);
5515 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
5516 "Owner %llu has an extent at cpos %u which can no "
5517 "longer be found.\n",
5518 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5525 * We have 3 cases of extent removal:
5526 * 1) Range covers the entire extent rec
5527 * 2) Range begins or ends on one edge of the extent rec
5528 * 3) Range is in the middle of the extent rec (no shared edges)
5530 * For case 1 we remove the extent rec and left rotate to
5533 * For case 2 we just shrink the existing extent rec, with a
5534 * tree update if the shrinking edge is also the edge of an
5537 * For case 3 we do a right split to turn the extent rec into
5538 * something case 2 can handle.
5540 rec
= &el
->l_recs
[index
];
5541 rec_range
= le32_to_cpu(rec
->e_cpos
) + ocfs2_rec_clusters(el
, rec
);
5542 trunc_range
= cpos
+ len
;
5544 BUG_ON(cpos
< le32_to_cpu(rec
->e_cpos
) || trunc_range
> rec_range
);
5546 trace_ocfs2_remove_extent(
5547 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5548 cpos
, len
, index
, le32_to_cpu(rec
->e_cpos
),
5549 ocfs2_rec_clusters(el
, rec
));
5551 if (le32_to_cpu(rec
->e_cpos
) == cpos
|| rec_range
== trunc_range
) {
5552 ret
= ocfs2_truncate_rec(handle
, et
, path
, index
, dealloc
,
5559 ret
= ocfs2_split_tree(handle
, et
, path
, index
,
5560 trunc_range
, meta_ac
);
5567 * The split could have manipulated the tree enough to
5568 * move the record location, so we have to look for it again.
5570 ocfs2_reinit_path(path
, 1);
5572 ret
= ocfs2_find_path(et
->et_ci
, path
, cpos
);
5578 el
= path_leaf_el(path
);
5579 index
= ocfs2_search_extent_list(el
, cpos
);
5581 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
5582 "Owner %llu: split at cpos %u lost record.",
5583 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5590 * Double check our values here. If anything is fishy,
5591 * it's easier to catch it at the top level.
5593 rec
= &el
->l_recs
[index
];
5594 rec_range
= le32_to_cpu(rec
->e_cpos
) +
5595 ocfs2_rec_clusters(el
, rec
);
5596 if (rec_range
!= trunc_range
) {
5597 ocfs2_error(ocfs2_metadata_cache_get_super(et
->et_ci
),
5598 "Owner %llu: error after split at cpos %u"
5599 "trunc len %u, existing record is (%u,%u)",
5600 (unsigned long long)ocfs2_metadata_cache_owner(et
->et_ci
),
5601 cpos
, len
, le32_to_cpu(rec
->e_cpos
),
5602 ocfs2_rec_clusters(el
, rec
));
5607 ret
= ocfs2_truncate_rec(handle
, et
, path
, index
, dealloc
,
5616 ocfs2_free_path(path
);
5621 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5622 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5623 * number to reserve some extra blocks, and it only handles meta
5626 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5627 * and punching holes.
5629 static int ocfs2_reserve_blocks_for_rec_trunc(struct inode
*inode
,
5630 struct ocfs2_extent_tree
*et
,
5631 u32 extents_to_split
,
5632 struct ocfs2_alloc_context
**ac
,
5635 int ret
= 0, num_free_extents
;
5636 unsigned int max_recs_needed
= 2 * extents_to_split
;
5637 struct ocfs2_super
*osb
= OCFS2_SB(inode
->i_sb
);
5641 num_free_extents
= ocfs2_num_free_extents(osb
, et
);
5642 if (num_free_extents
< 0) {
5643 ret
= num_free_extents
;
5648 if (!num_free_extents
||
5649 (ocfs2_sparse_alloc(osb
) && num_free_extents
< max_recs_needed
))
5650 extra_blocks
+= ocfs2_extend_meta_needed(et
->et_root_el
);
5653 ret
= ocfs2_reserve_new_metadata_blocks(osb
, extra_blocks
, ac
);
5664 ocfs2_free_alloc_context(*ac
);
5672 int ocfs2_remove_btree_range(struct inode
*inode
,
5673 struct ocfs2_extent_tree
*et
,
5674 u32 cpos
, u32 phys_cpos
, u32 len
, int flags
,
5675 struct ocfs2_cached_dealloc_ctxt
*dealloc
,
5676 u64 refcount_loc
, bool refcount_tree_locked
)
5678 int ret
, credits
= 0, extra_blocks
= 0;
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
;
5683 struct ocfs2_alloc_context
*meta_ac
= NULL
;
5684 struct ocfs2_refcount_tree
*ref_tree
= NULL
;
5686 if ((flags
& OCFS2_EXT_REFCOUNTED
) && len
) {
5687 BUG_ON(!(OCFS2_I(inode
)->ip_dyn_features
&
5688 OCFS2_HAS_REFCOUNT_FL
));
5690 if (!refcount_tree_locked
) {
5691 ret
= ocfs2_lock_refcount_tree(osb
, refcount_loc
, 1,
5699 ret
= ocfs2_prepare_refcount_change_for_del(inode
,
5711 ret
= ocfs2_reserve_blocks_for_rec_trunc(inode
, et
, 1, &meta_ac
,
5718 mutex_lock(&tl_inode
->i_mutex
);
5720 if (ocfs2_truncate_log_needs_flush(osb
)) {
5721 ret
= __ocfs2_flush_truncate_log(osb
);
5728 handle
= ocfs2_start_trans(osb
,
5729 ocfs2_remove_extent_credits(osb
->sb
) + credits
);
5730 if (IS_ERR(handle
)) {
5731 ret
= PTR_ERR(handle
);
5736 ret
= ocfs2_et_root_journal_access(handle
, et
,
5737 OCFS2_JOURNAL_ACCESS_WRITE
);
5743 dquot_free_space_nodirty(inode
,
5744 ocfs2_clusters_to_bytes(inode
->i_sb
, len
));
5746 ret
= ocfs2_remove_extent(handle
, et
, cpos
, len
, meta_ac
, dealloc
);
5752 ocfs2_et_update_clusters(et
, -len
);
5753 ocfs2_update_inode_fsync_trans(handle
, inode
, 1);
5755 ocfs2_journal_dirty(handle
, et
->et_root_bh
);
5758 if (flags
& OCFS2_EXT_REFCOUNTED
)
5759 ret
= ocfs2_decrease_refcount(inode
, handle
,
5760 ocfs2_blocks_to_clusters(osb
->sb
,
5765 ret
= ocfs2_truncate_log_append(osb
, handle
,
5773 ocfs2_commit_trans(osb
, handle
);
5775 mutex_unlock(&tl_inode
->i_mutex
);
5778 ocfs2_free_alloc_context(meta_ac
);
5781 ocfs2_unlock_refcount_tree(osb
, ref_tree
, 1);
5786 int ocfs2_truncate_log_needs_flush(struct ocfs2_super
*osb
)
5788 struct buffer_head
*tl_bh
= osb
->osb_tl_bh
;
5789 struct ocfs2_dinode
*di
;
5790 struct ocfs2_truncate_log
*tl
;
5792 di
= (struct ocfs2_dinode
*) tl_bh
->b_data
;
5793 tl
= &di
->id2
.i_dealloc
;
5795 mlog_bug_on_msg(le16_to_cpu(tl
->tl_used
) > le16_to_cpu(tl
->tl_count
),
5796 "slot %d, invalid truncate log parameters: used = "
5797 "%u, count = %u\n", osb
->slot_num
,
5798 le16_to_cpu(tl
->tl_used
), le16_to_cpu(tl
->tl_count
));
5799 return le16_to_cpu(tl
->tl_used
) == le16_to_cpu(tl
->tl_count
);
5802 static int ocfs2_truncate_log_can_coalesce(struct ocfs2_truncate_log
*tl
,
5803 unsigned int new_start
)
5805 unsigned int tail_index
;
5806 unsigned int current_tail
;
5808 /* No records, nothing to coalesce */
5809 if (!le16_to_cpu(tl
->tl_used
))
5812 tail_index
= le16_to_cpu(tl
->tl_used
) - 1;
5813 current_tail
= le32_to_cpu(tl
->tl_recs
[tail_index
].t_start
);
5814 current_tail
+= le32_to_cpu(tl
->tl_recs
[tail_index
].t_clusters
);
5816 return current_tail
== new_start
;
5819 int ocfs2_truncate_log_append(struct ocfs2_super
*osb
,
5822 unsigned int num_clusters
)
5825 unsigned int start_cluster
, tl_count
;
5826 struct inode
*tl_inode
= osb
->osb_tl_inode
;
5827 struct buffer_head
*tl_bh
= osb
->osb_tl_bh
;
5828 struct ocfs2_dinode
*di
;
5829 struct ocfs2_truncate_log
*tl
;
5831 BUG_ON(mutex_trylock(&tl_inode
->i_mutex
));
5833 start_cluster
= ocfs2_blocks_to_clusters(osb
->sb
, start_blk
);
5835 di
= (struct ocfs2_dinode
*) tl_bh
->b_data
;
5837 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5838 * by the underlying call to ocfs2_read_inode_block(), so any
5839 * corruption is a code bug */
5840 BUG_ON(!OCFS2_IS_VALID_DINODE(di
));
5842 tl
= &di
->id2
.i_dealloc
;
5843 tl_count
= le16_to_cpu(tl
->tl_count
);
5844 mlog_bug_on_msg(tl_count
> ocfs2_truncate_recs_per_inode(osb
->sb
) ||
5846 "Truncate record count on #%llu invalid "
5847 "wanted %u, actual %u\n",
5848 (unsigned long long)OCFS2_I(tl_inode
)->ip_blkno
,
5849 ocfs2_truncate_recs_per_inode(osb
->sb
),
5850 le16_to_cpu(tl
->tl_count
));
5852 /* Caller should have known to flush before calling us. */
5853 index
= le16_to_cpu(tl
->tl_used
);
5854 if (index
>= tl_count
) {
5860 status
= ocfs2_journal_access_di(handle
, INODE_CACHE(tl_inode
), tl_bh
,
5861 OCFS2_JOURNAL_ACCESS_WRITE
);
5867 trace_ocfs2_truncate_log_append(
5868 (unsigned long long)OCFS2_I(tl_inode
)->ip_blkno
, index
,
5869 start_cluster
, num_clusters
);
5870 if (ocfs2_truncate_log_can_coalesce(tl
, start_cluster
)) {
5872 * Move index back to the record we are coalescing with.
5873 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5877 num_clusters
+= le32_to_cpu(tl
->tl_recs
[index
].t_clusters
);
5878 trace_ocfs2_truncate_log_append(
5879 (unsigned long long)OCFS2_I(tl_inode
)->ip_blkno
,
5880 index
, le32_to_cpu(tl
->tl_recs
[index
].t_start
),
5883 tl
->tl_recs
[index
].t_start
= cpu_to_le32(start_cluster
);
5884 tl
->tl_used
= cpu_to_le16(index
+ 1);
5886 tl
->tl_recs
[index
].t_clusters
= cpu_to_le32(num_clusters
);
5888 ocfs2_journal_dirty(handle
, tl_bh
);
5890 osb
->truncated_clusters
+= num_clusters
;
5895 static int ocfs2_replay_truncate_records(struct ocfs2_super
*osb
,
5897 struct inode
*data_alloc_inode
,
5898 struct buffer_head
*data_alloc_bh
)
5902 unsigned int num_clusters
;
5904 struct ocfs2_truncate_rec rec
;
5905 struct ocfs2_dinode
*di
;
5906 struct ocfs2_truncate_log
*tl
;
5907 struct inode
*tl_inode
= osb
->osb_tl_inode
;
5908 struct buffer_head
*tl_bh
= osb
->osb_tl_bh
;
5910 di
= (struct ocfs2_dinode
*) tl_bh
->b_data
;
5911 tl
= &di
->id2
.i_dealloc
;
5912 i
= le16_to_cpu(tl
->tl_used
) - 1;
5914 /* Caller has given us at least enough credits to
5915 * update the truncate log dinode */
5916 status
= ocfs2_journal_access_di(handle
, INODE_CACHE(tl_inode
), tl_bh
,
5917 OCFS2_JOURNAL_ACCESS_WRITE
);
5923 tl
->tl_used
= cpu_to_le16(i
);
5925 ocfs2_journal_dirty(handle
, tl_bh
);
5927 /* TODO: Perhaps we can calculate the bulk of the
5928 * credits up front rather than extending like
5930 status
= ocfs2_extend_trans(handle
,
5931 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC
);
5937 rec
= tl
->tl_recs
[i
];
5938 start_blk
= ocfs2_clusters_to_blocks(data_alloc_inode
->i_sb
,
5939 le32_to_cpu(rec
.t_start
));
5940 num_clusters
= le32_to_cpu(rec
.t_clusters
);
5942 /* if start_blk is not set, we ignore the record as
5945 trace_ocfs2_replay_truncate_records(
5946 (unsigned long long)OCFS2_I(tl_inode
)->ip_blkno
,
5947 i
, le32_to_cpu(rec
.t_start
), num_clusters
);
5949 status
= ocfs2_free_clusters(handle
, data_alloc_inode
,
5950 data_alloc_bh
, start_blk
,
5960 osb
->truncated_clusters
= 0;
5966 /* Expects you to already be holding tl_inode->i_mutex */
5967 int __ocfs2_flush_truncate_log(struct ocfs2_super
*osb
)
5970 unsigned int num_to_flush
;
5972 struct inode
*tl_inode
= osb
->osb_tl_inode
;
5973 struct inode
*data_alloc_inode
= NULL
;
5974 struct buffer_head
*tl_bh
= osb
->osb_tl_bh
;
5975 struct buffer_head
*data_alloc_bh
= NULL
;
5976 struct ocfs2_dinode
*di
;
5977 struct ocfs2_truncate_log
*tl
;
5979 BUG_ON(mutex_trylock(&tl_inode
->i_mutex
));
5981 di
= (struct ocfs2_dinode
*) tl_bh
->b_data
;
5983 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5984 * by the underlying call to ocfs2_read_inode_block(), so any
5985 * corruption is a code bug */
5986 BUG_ON(!OCFS2_IS_VALID_DINODE(di
));
5988 tl
= &di
->id2
.i_dealloc
;
5989 num_to_flush
= le16_to_cpu(tl
->tl_used
);
5990 trace_ocfs2_flush_truncate_log(
5991 (unsigned long long)OCFS2_I(tl_inode
)->ip_blkno
,
5993 if (!num_to_flush
) {
5998 data_alloc_inode
= ocfs2_get_system_file_inode(osb
,
5999 GLOBAL_BITMAP_SYSTEM_INODE
,
6000 OCFS2_INVALID_SLOT
);
6001 if (!data_alloc_inode
) {
6003 mlog(ML_ERROR
, "Could not get bitmap inode!\n");
6007 mutex_lock(&data_alloc_inode
->i_mutex
);
6009 status
= ocfs2_inode_lock(data_alloc_inode
, &data_alloc_bh
, 1);
6015 handle
= ocfs2_start_trans(osb
, OCFS2_TRUNCATE_LOG_UPDATE
);
6016 if (IS_ERR(handle
)) {
6017 status
= PTR_ERR(handle
);
6022 status
= ocfs2_replay_truncate_records(osb
, handle
, data_alloc_inode
,
6027 ocfs2_commit_trans(osb
, handle
);
6030 brelse(data_alloc_bh
);
6031 ocfs2_inode_unlock(data_alloc_inode
, 1);
6034 mutex_unlock(&data_alloc_inode
->i_mutex
);
6035 iput(data_alloc_inode
);
6041 int ocfs2_flush_truncate_log(struct ocfs2_super
*osb
)
6044 struct inode
*tl_inode
= osb
->osb_tl_inode
;
6046 mutex_lock(&tl_inode
->i_mutex
);
6047 status
= __ocfs2_flush_truncate_log(osb
);
6048 mutex_unlock(&tl_inode
->i_mutex
);
6053 static void ocfs2_truncate_log_worker(struct work_struct
*work
)
6056 struct ocfs2_super
*osb
=
6057 container_of(work
, struct ocfs2_super
,
6058 osb_truncate_log_wq
.work
);
6060 status
= ocfs2_flush_truncate_log(osb
);
6064 ocfs2_init_steal_slots(osb
);
6067 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6068 void ocfs2_schedule_truncate_log_flush(struct ocfs2_super
*osb
,
6071 if (osb
->osb_tl_inode
&&
6072 atomic_read(&osb
->osb_tl_disable
) == 0) {
6073 /* We want to push off log flushes while truncates are
6076 cancel_delayed_work(&osb
->osb_truncate_log_wq
);
6078 queue_delayed_work(ocfs2_wq
, &osb
->osb_truncate_log_wq
,
6079 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL
);
6083 static int ocfs2_get_truncate_log_info(struct ocfs2_super
*osb
,
6085 struct inode
**tl_inode
,
6086 struct buffer_head
**tl_bh
)
6089 struct inode
*inode
= NULL
;
6090 struct buffer_head
*bh
= NULL
;
6092 inode
= ocfs2_get_system_file_inode(osb
,
6093 TRUNCATE_LOG_SYSTEM_INODE
,
6097 mlog(ML_ERROR
, "Could not get load truncate log inode!\n");
6101 status
= ocfs2_read_inode_block(inode
, &bh
);
6114 /* called during the 1st stage of node recovery. we stamp a clean
6115 * truncate log and pass back a copy for processing later. if the
6116 * truncate log does not require processing, a *tl_copy is set to
6118 int ocfs2_begin_truncate_log_recovery(struct ocfs2_super
*osb
,
6120 struct ocfs2_dinode
**tl_copy
)
6123 struct inode
*tl_inode
= NULL
;
6124 struct buffer_head
*tl_bh
= NULL
;
6125 struct ocfs2_dinode
*di
;
6126 struct ocfs2_truncate_log
*tl
;
6130 trace_ocfs2_begin_truncate_log_recovery(slot_num
);
6132 status
= ocfs2_get_truncate_log_info(osb
, slot_num
, &tl_inode
, &tl_bh
);
6138 di
= (struct ocfs2_dinode
*) tl_bh
->b_data
;
6140 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6141 * validated by the underlying call to ocfs2_read_inode_block(),
6142 * so any corruption is a code bug */
6143 BUG_ON(!OCFS2_IS_VALID_DINODE(di
));
6145 tl
= &di
->id2
.i_dealloc
;
6146 if (le16_to_cpu(tl
->tl_used
)) {
6147 trace_ocfs2_truncate_log_recovery_num(le16_to_cpu(tl
->tl_used
));
6149 *tl_copy
= kmalloc(tl_bh
->b_size
, GFP_KERNEL
);
6156 /* Assuming the write-out below goes well, this copy
6157 * will be passed back to recovery for processing. */
6158 memcpy(*tl_copy
, tl_bh
->b_data
, tl_bh
->b_size
);
6160 /* All we need to do to clear the truncate log is set
6164 ocfs2_compute_meta_ecc(osb
->sb
, tl_bh
->b_data
, &di
->i_check
);
6165 status
= ocfs2_write_block(osb
, tl_bh
, INODE_CACHE(tl_inode
));
6177 if (status
< 0 && (*tl_copy
)) {
6186 int ocfs2_complete_truncate_log_recovery(struct ocfs2_super
*osb
,
6187 struct ocfs2_dinode
*tl_copy
)
6191 unsigned int clusters
, num_recs
, start_cluster
;
6194 struct inode
*tl_inode
= osb
->osb_tl_inode
;
6195 struct ocfs2_truncate_log
*tl
;
6197 if (OCFS2_I(tl_inode
)->ip_blkno
== le64_to_cpu(tl_copy
->i_blkno
)) {
6198 mlog(ML_ERROR
, "Asked to recover my own truncate log!\n");
6202 tl
= &tl_copy
->id2
.i_dealloc
;
6203 num_recs
= le16_to_cpu(tl
->tl_used
);
6204 trace_ocfs2_complete_truncate_log_recovery(
6205 (unsigned long long)le64_to_cpu(tl_copy
->i_blkno
),
6208 mutex_lock(&tl_inode
->i_mutex
);
6209 for(i
= 0; i
< num_recs
; i
++) {
6210 if (ocfs2_truncate_log_needs_flush(osb
)) {
6211 status
= __ocfs2_flush_truncate_log(osb
);
6218 handle
= ocfs2_start_trans(osb
, OCFS2_TRUNCATE_LOG_UPDATE
);
6219 if (IS_ERR(handle
)) {
6220 status
= PTR_ERR(handle
);
6225 clusters
= le32_to_cpu(tl
->tl_recs
[i
].t_clusters
);
6226 start_cluster
= le32_to_cpu(tl
->tl_recs
[i
].t_start
);
6227 start_blk
= ocfs2_clusters_to_blocks(osb
->sb
, start_cluster
);
6229 status
= ocfs2_truncate_log_append(osb
, handle
,
6230 start_blk
, clusters
);
6231 ocfs2_commit_trans(osb
, handle
);
6239 mutex_unlock(&tl_inode
->i_mutex
);
6244 void ocfs2_truncate_log_shutdown(struct ocfs2_super
*osb
)
6247 struct inode
*tl_inode
= osb
->osb_tl_inode
;
6249 atomic_set(&osb
->osb_tl_disable
, 1);
6252 cancel_delayed_work(&osb
->osb_truncate_log_wq
);
6253 flush_workqueue(ocfs2_wq
);
6255 status
= ocfs2_flush_truncate_log(osb
);
6259 brelse(osb
->osb_tl_bh
);
6260 iput(osb
->osb_tl_inode
);
6264 int ocfs2_truncate_log_init(struct ocfs2_super
*osb
)
6267 struct inode
*tl_inode
= NULL
;
6268 struct buffer_head
*tl_bh
= NULL
;
6270 status
= ocfs2_get_truncate_log_info(osb
,
6277 /* ocfs2_truncate_log_shutdown keys on the existence of
6278 * osb->osb_tl_inode so we don't set any of the osb variables
6279 * until we're sure all is well. */
6280 INIT_DELAYED_WORK(&osb
->osb_truncate_log_wq
,
6281 ocfs2_truncate_log_worker
);
6282 atomic_set(&osb
->osb_tl_disable
, 0);
6283 osb
->osb_tl_bh
= tl_bh
;
6284 osb
->osb_tl_inode
= tl_inode
;
6290 * Delayed de-allocation of suballocator blocks.
6292 * Some sets of block de-allocations might involve multiple suballocator inodes.
6294 * The locking for this can get extremely complicated, especially when
6295 * the suballocator inodes to delete from aren't known until deep
6296 * within an unrelated codepath.
6298 * ocfs2_extent_block structures are a good example of this - an inode
6299 * btree could have been grown by any number of nodes each allocating
6300 * out of their own suballoc inode.
6302 * These structures allow the delay of block de-allocation until a
6303 * later time, when locking of multiple cluster inodes won't cause
6308 * Describe a single bit freed from a suballocator. For the block
6309 * suballocators, it represents one block. For the global cluster
6310 * allocator, it represents some clusters and free_bit indicates
6313 struct ocfs2_cached_block_free
{
6314 struct ocfs2_cached_block_free
*free_next
;
6317 unsigned int free_bit
;
6320 struct ocfs2_per_slot_free_list
{
6321 struct ocfs2_per_slot_free_list
*f_next_suballocator
;
6324 struct ocfs2_cached_block_free
*f_first
;
6327 static int ocfs2_free_cached_blocks(struct ocfs2_super
*osb
,
6330 struct ocfs2_cached_block_free
*head
)
6335 struct inode
*inode
;
6336 struct buffer_head
*di_bh
= NULL
;
6337 struct ocfs2_cached_block_free
*tmp
;
6339 inode
= ocfs2_get_system_file_inode(osb
, sysfile_type
, slot
);
6346 mutex_lock(&inode
->i_mutex
);
6348 ret
= ocfs2_inode_lock(inode
, &di_bh
, 1);
6354 handle
= ocfs2_start_trans(osb
, OCFS2_SUBALLOC_FREE
);
6355 if (IS_ERR(handle
)) {
6356 ret
= PTR_ERR(handle
);
6363 bg_blkno
= head
->free_bg
;
6365 bg_blkno
= ocfs2_which_suballoc_group(head
->free_blk
,
6367 trace_ocfs2_free_cached_blocks(
6368 (unsigned long long)head
->free_blk
, head
->free_bit
);
6370 ret
= ocfs2_free_suballoc_bits(handle
, inode
, di_bh
,
6371 head
->free_bit
, bg_blkno
, 1);
6377 ret
= ocfs2_extend_trans(handle
, OCFS2_SUBALLOC_FREE
);
6384 head
= head
->free_next
;
6389 ocfs2_commit_trans(osb
, handle
);
6392 ocfs2_inode_unlock(inode
, 1);
6395 mutex_unlock(&inode
->i_mutex
);
6399 /* Premature exit may have left some dangling items. */
6401 head
= head
->free_next
;
6408 int ocfs2_cache_cluster_dealloc(struct ocfs2_cached_dealloc_ctxt
*ctxt
,
6409 u64 blkno
, unsigned int bit
)
6412 struct ocfs2_cached_block_free
*item
;
6414 item
= kzalloc(sizeof(*item
), GFP_NOFS
);
6421 trace_ocfs2_cache_cluster_dealloc((unsigned long long)blkno
, bit
);
6423 item
->free_blk
= blkno
;
6424 item
->free_bit
= bit
;
6425 item
->free_next
= ctxt
->c_global_allocator
;
6427 ctxt
->c_global_allocator
= item
;
6431 static int ocfs2_free_cached_clusters(struct ocfs2_super
*osb
,
6432 struct ocfs2_cached_block_free
*head
)
6434 struct ocfs2_cached_block_free
*tmp
;
6435 struct inode
*tl_inode
= osb
->osb_tl_inode
;
6439 mutex_lock(&tl_inode
->i_mutex
);
6442 if (ocfs2_truncate_log_needs_flush(osb
)) {
6443 ret
= __ocfs2_flush_truncate_log(osb
);
6450 handle
= ocfs2_start_trans(osb
, OCFS2_TRUNCATE_LOG_UPDATE
);
6451 if (IS_ERR(handle
)) {
6452 ret
= PTR_ERR(handle
);
6457 ret
= ocfs2_truncate_log_append(osb
, handle
, head
->free_blk
,
6460 ocfs2_commit_trans(osb
, handle
);
6462 head
= head
->free_next
;
6471 mutex_unlock(&tl_inode
->i_mutex
);
6474 /* Premature exit may have left some dangling items. */
6476 head
= head
->free_next
;
6483 int ocfs2_run_deallocs(struct ocfs2_super
*osb
,
6484 struct ocfs2_cached_dealloc_ctxt
*ctxt
)
6487 struct ocfs2_per_slot_free_list
*fl
;
6492 while (ctxt
->c_first_suballocator
) {
6493 fl
= ctxt
->c_first_suballocator
;
6496 trace_ocfs2_run_deallocs(fl
->f_inode_type
,
6498 ret2
= ocfs2_free_cached_blocks(osb
,
6508 ctxt
->c_first_suballocator
= fl
->f_next_suballocator
;
6512 if (ctxt
->c_global_allocator
) {
6513 ret2
= ocfs2_free_cached_clusters(osb
,
6514 ctxt
->c_global_allocator
);
6520 ctxt
->c_global_allocator
= NULL
;
6526 static struct ocfs2_per_slot_free_list
*
6527 ocfs2_find_per_slot_free_list(int type
,
6529 struct ocfs2_cached_dealloc_ctxt
*ctxt
)
6531 struct ocfs2_per_slot_free_list
*fl
= ctxt
->c_first_suballocator
;
6534 if (fl
->f_inode_type
== type
&& fl
->f_slot
== slot
)
6537 fl
= fl
->f_next_suballocator
;
6540 fl
= kmalloc(sizeof(*fl
), GFP_NOFS
);
6542 fl
->f_inode_type
= type
;
6545 fl
->f_next_suballocator
= ctxt
->c_first_suballocator
;
6547 ctxt
->c_first_suballocator
= fl
;
6552 int ocfs2_cache_block_dealloc(struct ocfs2_cached_dealloc_ctxt
*ctxt
,
6553 int type
, int slot
, u64 suballoc
,
6554 u64 blkno
, unsigned int bit
)
6557 struct ocfs2_per_slot_free_list
*fl
;
6558 struct ocfs2_cached_block_free
*item
;
6560 fl
= ocfs2_find_per_slot_free_list(type
, slot
, ctxt
);
6567 item
= kzalloc(sizeof(*item
), GFP_NOFS
);
6574 trace_ocfs2_cache_block_dealloc(type
, slot
,
6575 (unsigned long long)suballoc
,
6576 (unsigned long long)blkno
, bit
);
6578 item
->free_bg
= suballoc
;
6579 item
->free_blk
= blkno
;
6580 item
->free_bit
= bit
;
6581 item
->free_next
= fl
->f_first
;
6590 static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt
*ctxt
,
6591 struct ocfs2_extent_block
*eb
)
6593 return ocfs2_cache_block_dealloc(ctxt
, EXTENT_ALLOC_SYSTEM_INODE
,
6594 le16_to_cpu(eb
->h_suballoc_slot
),
6595 le64_to_cpu(eb
->h_suballoc_loc
),
6596 le64_to_cpu(eb
->h_blkno
),
6597 le16_to_cpu(eb
->h_suballoc_bit
));
6600 static int ocfs2_zero_func(handle_t
*handle
, struct buffer_head
*bh
)
6602 set_buffer_uptodate(bh
);
6603 mark_buffer_dirty(bh
);
6607 void ocfs2_map_and_dirty_page(struct inode
*inode
, handle_t
*handle
,
6608 unsigned int from
, unsigned int to
,
6609 struct page
*page
, int zero
, u64
*phys
)
6611 int ret
, partial
= 0;
6613 ret
= ocfs2_map_page_blocks(page
, phys
, inode
, from
, to
, 0);
6618 zero_user_segment(page
, from
, to
);
6621 * Need to set the buffers we zero'd into uptodate
6622 * here if they aren't - ocfs2_map_page_blocks()
6623 * might've skipped some
6625 ret
= walk_page_buffers(handle
, page_buffers(page
),
6630 else if (ocfs2_should_order_data(inode
)) {
6631 ret
= ocfs2_jbd2_file_inode(handle
, inode
);
6637 SetPageUptodate(page
);
6639 flush_dcache_page(page
);
6642 static void ocfs2_zero_cluster_pages(struct inode
*inode
, loff_t start
,
6643 loff_t end
, struct page
**pages
,
6644 int numpages
, u64 phys
, handle_t
*handle
)
6648 unsigned int from
, to
= PAGE_CACHE_SIZE
;
6649 struct super_block
*sb
= inode
->i_sb
;
6651 BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb
)));
6656 to
= PAGE_CACHE_SIZE
;
6657 for(i
= 0; i
< numpages
; i
++) {
6660 from
= start
& (PAGE_CACHE_SIZE
- 1);
6661 if ((end
>> PAGE_CACHE_SHIFT
) == page
->index
)
6662 to
= end
& (PAGE_CACHE_SIZE
- 1);
6664 BUG_ON(from
> PAGE_CACHE_SIZE
);
6665 BUG_ON(to
> PAGE_CACHE_SIZE
);
6667 ocfs2_map_and_dirty_page(inode
, handle
, from
, to
, page
, 1,
6670 start
= (page
->index
+ 1) << PAGE_CACHE_SHIFT
;
6674 ocfs2_unlock_and_free_pages(pages
, numpages
);
6677 int ocfs2_grab_pages(struct inode
*inode
, loff_t start
, loff_t end
,
6678 struct page
**pages
, int *num
)
6680 int numpages
, ret
= 0;
6681 struct address_space
*mapping
= inode
->i_mapping
;
6682 unsigned long index
;
6683 loff_t last_page_bytes
;
6685 BUG_ON(start
> end
);
6688 last_page_bytes
= PAGE_ALIGN(end
);
6689 index
= start
>> PAGE_CACHE_SHIFT
;
6691 pages
[numpages
] = find_or_create_page(mapping
, index
, GFP_NOFS
);
6692 if (!pages
[numpages
]) {
6700 } while (index
< (last_page_bytes
>> PAGE_CACHE_SHIFT
));
6705 ocfs2_unlock_and_free_pages(pages
, numpages
);
6714 static int ocfs2_grab_eof_pages(struct inode
*inode
, loff_t start
, loff_t end
,
6715 struct page
**pages
, int *num
)
6717 struct super_block
*sb
= inode
->i_sb
;
6719 BUG_ON(start
>> OCFS2_SB(sb
)->s_clustersize_bits
!=
6720 (end
- 1) >> OCFS2_SB(sb
)->s_clustersize_bits
);
6722 return ocfs2_grab_pages(inode
, start
, end
, pages
, num
);
6726 * Zero the area past i_size but still within an allocated
6727 * cluster. This avoids exposing nonzero data on subsequent file
6730 * We need to call this before i_size is updated on the inode because
6731 * otherwise block_write_full_page() will skip writeout of pages past
6732 * i_size. The new_i_size parameter is passed for this reason.
6734 int ocfs2_zero_range_for_truncate(struct inode
*inode
, handle_t
*handle
,
6735 u64 range_start
, u64 range_end
)
6737 int ret
= 0, numpages
;
6738 struct page
**pages
= NULL
;
6740 unsigned int ext_flags
;
6741 struct super_block
*sb
= inode
->i_sb
;
6744 * File systems which don't support sparse files zero on every
6747 if (!ocfs2_sparse_alloc(OCFS2_SB(sb
)))
6750 pages
= kcalloc(ocfs2_pages_per_cluster(sb
),
6751 sizeof(struct page
*), GFP_NOFS
);
6752 if (pages
== NULL
) {
6758 if (range_start
== range_end
)
6761 ret
= ocfs2_extent_map_get_blocks(inode
,
6762 range_start
>> sb
->s_blocksize_bits
,
6763 &phys
, NULL
, &ext_flags
);
6770 * Tail is a hole, or is marked unwritten. In either case, we
6771 * can count on read and write to return/push zero's.
6773 if (phys
== 0 || ext_flags
& OCFS2_EXT_UNWRITTEN
)
6776 ret
= ocfs2_grab_eof_pages(inode
, range_start
, range_end
, pages
,
6783 ocfs2_zero_cluster_pages(inode
, range_start
, range_end
, pages
,
6784 numpages
, phys
, handle
);
6787 * Initiate writeout of the pages we zero'd here. We don't
6788 * wait on them - the truncate_inode_pages() call later will
6791 ret
= filemap_fdatawrite_range(inode
->i_mapping
, range_start
,
6802 static void ocfs2_zero_dinode_id2_with_xattr(struct inode
*inode
,
6803 struct ocfs2_dinode
*di
)
6805 unsigned int blocksize
= 1 << inode
->i_sb
->s_blocksize_bits
;
6806 unsigned int xattrsize
= le16_to_cpu(di
->i_xattr_inline_size
);
6808 if (le16_to_cpu(di
->i_dyn_features
) & OCFS2_INLINE_XATTR_FL
)
6809 memset(&di
->id2
, 0, blocksize
-
6810 offsetof(struct ocfs2_dinode
, id2
) -
6813 memset(&di
->id2
, 0, blocksize
-
6814 offsetof(struct ocfs2_dinode
, id2
));
6817 void ocfs2_dinode_new_extent_list(struct inode
*inode
,
6818 struct ocfs2_dinode
*di
)
6820 ocfs2_zero_dinode_id2_with_xattr(inode
, di
);
6821 di
->id2
.i_list
.l_tree_depth
= 0;
6822 di
->id2
.i_list
.l_next_free_rec
= 0;
6823 di
->id2
.i_list
.l_count
= cpu_to_le16(
6824 ocfs2_extent_recs_per_inode_with_xattr(inode
->i_sb
, di
));
6827 void ocfs2_set_inode_data_inline(struct inode
*inode
, struct ocfs2_dinode
*di
)
6829 struct ocfs2_inode_info
*oi
= OCFS2_I(inode
);
6830 struct ocfs2_inline_data
*idata
= &di
->id2
.i_data
;
6832 spin_lock(&oi
->ip_lock
);
6833 oi
->ip_dyn_features
|= OCFS2_INLINE_DATA_FL
;
6834 di
->i_dyn_features
= cpu_to_le16(oi
->ip_dyn_features
);
6835 spin_unlock(&oi
->ip_lock
);
6838 * We clear the entire i_data structure here so that all
6839 * fields can be properly initialized.
6841 ocfs2_zero_dinode_id2_with_xattr(inode
, di
);
6843 idata
->id_count
= cpu_to_le16(
6844 ocfs2_max_inline_data_with_xattr(inode
->i_sb
, di
));
6847 int ocfs2_convert_inline_data_to_extents(struct inode
*inode
,
6848 struct buffer_head
*di_bh
)
6850 int ret
, i
, has_data
, num_pages
= 0;
6854 u64
uninitialized_var(block
);
6855 struct ocfs2_inode_info
*oi
= OCFS2_I(inode
);
6856 struct ocfs2_super
*osb
= OCFS2_SB(inode
->i_sb
);
6857 struct ocfs2_dinode
*di
= (struct ocfs2_dinode
*)di_bh
->b_data
;
6858 struct ocfs2_alloc_context
*data_ac
= NULL
;
6859 struct page
**pages
= NULL
;
6860 loff_t end
= osb
->s_clustersize
;
6861 struct ocfs2_extent_tree et
;
6864 has_data
= i_size_read(inode
) ? 1 : 0;
6867 pages
= kcalloc(ocfs2_pages_per_cluster(osb
->sb
),
6868 sizeof(struct page
*), GFP_NOFS
);
6869 if (pages
== NULL
) {
6875 ret
= ocfs2_reserve_clusters(osb
, 1, &data_ac
);
6882 handle
= ocfs2_start_trans(osb
,
6883 ocfs2_inline_to_extents_credits(osb
->sb
));
6884 if (IS_ERR(handle
)) {
6885 ret
= PTR_ERR(handle
);
6890 ret
= ocfs2_journal_access_di(handle
, INODE_CACHE(inode
), di_bh
,
6891 OCFS2_JOURNAL_ACCESS_WRITE
);
6898 unsigned int page_end
;
6901 ret
= dquot_alloc_space_nodirty(inode
,
6902 ocfs2_clusters_to_bytes(osb
->sb
, 1));
6907 data_ac
->ac_resv
= &OCFS2_I(inode
)->ip_la_data_resv
;
6909 ret
= ocfs2_claim_clusters(handle
, data_ac
, 1, &bit_off
,
6917 * Save two copies, one for insert, and one that can
6918 * be changed by ocfs2_map_and_dirty_page() below.
6920 block
= phys
= ocfs2_clusters_to_blocks(inode
->i_sb
, bit_off
);
6923 * Non sparse file systems zero on extend, so no need
6926 if (!ocfs2_sparse_alloc(osb
) &&
6927 PAGE_CACHE_SIZE
< osb
->s_clustersize
)
6928 end
= PAGE_CACHE_SIZE
;
6930 ret
= ocfs2_grab_eof_pages(inode
, 0, end
, pages
, &num_pages
);
6938 * This should populate the 1st page for us and mark
6941 ret
= ocfs2_read_inline_data(inode
, pages
[0], di_bh
);
6948 page_end
= PAGE_CACHE_SIZE
;
6949 if (PAGE_CACHE_SIZE
> osb
->s_clustersize
)
6950 page_end
= osb
->s_clustersize
;
6952 for (i
= 0; i
< num_pages
; i
++)
6953 ocfs2_map_and_dirty_page(inode
, handle
, 0, page_end
,
6954 pages
[i
], i
> 0, &phys
);
6957 spin_lock(&oi
->ip_lock
);
6958 oi
->ip_dyn_features
&= ~OCFS2_INLINE_DATA_FL
;
6959 di
->i_dyn_features
= cpu_to_le16(oi
->ip_dyn_features
);
6960 spin_unlock(&oi
->ip_lock
);
6962 ocfs2_update_inode_fsync_trans(handle
, inode
, 1);
6963 ocfs2_dinode_new_extent_list(inode
, di
);
6965 ocfs2_journal_dirty(handle
, di_bh
);
6969 * An error at this point should be extremely rare. If
6970 * this proves to be false, we could always re-build
6971 * the in-inode data from our pages.
6973 ocfs2_init_dinode_extent_tree(&et
, INODE_CACHE(inode
), di_bh
);
6974 ret
= ocfs2_insert_extent(handle
, &et
, 0, block
, 1, 0, NULL
);
6981 inode
->i_blocks
= ocfs2_inode_sector_count(inode
);
6986 ocfs2_unlock_and_free_pages(pages
, num_pages
);
6989 if (ret
< 0 && did_quota
)
6990 dquot_free_space_nodirty(inode
,
6991 ocfs2_clusters_to_bytes(osb
->sb
, 1));
6994 if (data_ac
->ac_which
== OCFS2_AC_USE_LOCAL
)
6995 ocfs2_free_local_alloc_bits(osb
, handle
, data_ac
,
6998 ocfs2_free_clusters(handle
,
7001 ocfs2_clusters_to_blocks(osb
->sb
, bit_off
),
7005 ocfs2_commit_trans(osb
, handle
);
7009 ocfs2_free_alloc_context(data_ac
);
7016 * It is expected, that by the time you call this function,
7017 * inode->i_size and fe->i_size have been adjusted.
7019 * WARNING: This will kfree the truncate context
7021 int ocfs2_commit_truncate(struct ocfs2_super
*osb
,
7022 struct inode
*inode
,
7023 struct buffer_head
*di_bh
)
7025 int status
= 0, i
, flags
= 0;
7026 u32 new_highest_cpos
, range
, trunc_cpos
, trunc_len
, phys_cpos
, coff
;
7028 struct ocfs2_extent_list
*el
;
7029 struct ocfs2_extent_rec
*rec
;
7030 struct ocfs2_path
*path
= NULL
;
7031 struct ocfs2_dinode
*di
= (struct ocfs2_dinode
*)di_bh
->b_data
;
7032 struct ocfs2_extent_list
*root_el
= &(di
->id2
.i_list
);
7033 u64 refcount_loc
= le64_to_cpu(di
->i_refcount_loc
);
7034 struct ocfs2_extent_tree et
;
7035 struct ocfs2_cached_dealloc_ctxt dealloc
;
7036 struct ocfs2_refcount_tree
*ref_tree
= NULL
;
7038 ocfs2_init_dinode_extent_tree(&et
, INODE_CACHE(inode
), di_bh
);
7039 ocfs2_init_dealloc_ctxt(&dealloc
);
7041 new_highest_cpos
= ocfs2_clusters_for_bytes(osb
->sb
,
7042 i_size_read(inode
));
7044 path
= ocfs2_new_path(di_bh
, &di
->id2
.i_list
,
7045 ocfs2_journal_access_di
);
7052 ocfs2_extent_map_trunc(inode
, new_highest_cpos
);
7056 * Check that we still have allocation to delete.
7058 if (OCFS2_I(inode
)->ip_clusters
== 0) {
7064 * Truncate always works against the rightmost tree branch.
7066 status
= ocfs2_find_path(INODE_CACHE(inode
), path
, UINT_MAX
);
7072 trace_ocfs2_commit_truncate(
7073 (unsigned long long)OCFS2_I(inode
)->ip_blkno
,
7075 OCFS2_I(inode
)->ip_clusters
,
7076 path
->p_tree_depth
);
7079 * By now, el will point to the extent list on the bottom most
7080 * portion of this tree. Only the tail record is considered in
7083 * We handle the following cases, in order:
7084 * - empty extent: delete the remaining branch
7085 * - remove the entire record
7086 * - remove a partial record
7087 * - no record needs to be removed (truncate has completed)
7089 el
= path_leaf_el(path
);
7090 if (le16_to_cpu(el
->l_next_free_rec
) == 0) {
7091 ocfs2_error(inode
->i_sb
,
7092 "Inode %llu has empty extent block at %llu\n",
7093 (unsigned long long)OCFS2_I(inode
)->ip_blkno
,
7094 (unsigned long long)path_leaf_bh(path
)->b_blocknr
);
7099 i
= le16_to_cpu(el
->l_next_free_rec
) - 1;
7100 rec
= &el
->l_recs
[i
];
7101 flags
= rec
->e_flags
;
7102 range
= le32_to_cpu(rec
->e_cpos
) + ocfs2_rec_clusters(el
, rec
);
7104 if (i
== 0 && ocfs2_is_empty_extent(rec
)) {
7106 * Lower levels depend on this never happening, but it's best
7107 * to check it up here before changing the tree.
7109 if (root_el
->l_tree_depth
&& rec
->e_int_clusters
== 0) {
7110 ocfs2_error(inode
->i_sb
, "Inode %lu has an empty "
7111 "extent record, depth %u\n", inode
->i_ino
,
7112 le16_to_cpu(root_el
->l_tree_depth
));
7116 trunc_cpos
= le32_to_cpu(rec
->e_cpos
);
7119 } else if (le32_to_cpu(rec
->e_cpos
) >= new_highest_cpos
) {
7121 * Truncate entire record.
7123 trunc_cpos
= le32_to_cpu(rec
->e_cpos
);
7124 trunc_len
= ocfs2_rec_clusters(el
, rec
);
7125 blkno
= le64_to_cpu(rec
->e_blkno
);
7126 } else if (range
> new_highest_cpos
) {
7128 * Partial truncate. it also should be
7129 * the last truncate we're doing.
7131 trunc_cpos
= new_highest_cpos
;
7132 trunc_len
= range
- new_highest_cpos
;
7133 coff
= new_highest_cpos
- le32_to_cpu(rec
->e_cpos
);
7134 blkno
= le64_to_cpu(rec
->e_blkno
) +
7135 ocfs2_clusters_to_blocks(inode
->i_sb
, coff
);
7138 * Truncate completed, leave happily.
7144 phys_cpos
= ocfs2_blocks_to_clusters(inode
->i_sb
, blkno
);
7146 if ((flags
& OCFS2_EXT_REFCOUNTED
) && trunc_len
&& !ref_tree
) {
7147 status
= ocfs2_lock_refcount_tree(osb
, refcount_loc
, 1,
7155 status
= ocfs2_remove_btree_range(inode
, &et
, trunc_cpos
,
7156 phys_cpos
, trunc_len
, flags
, &dealloc
,
7157 refcount_loc
, true);
7163 ocfs2_reinit_path(path
, 1);
7166 * The check above will catch the case where we've truncated
7167 * away all allocation.
7173 ocfs2_unlock_refcount_tree(osb
, ref_tree
, 1);
7175 ocfs2_schedule_truncate_log_flush(osb
, 1);
7177 ocfs2_run_deallocs(osb
, &dealloc
);
7179 ocfs2_free_path(path
);
7185 * 'start' is inclusive, 'end' is not.
7187 int ocfs2_truncate_inline(struct inode
*inode
, struct buffer_head
*di_bh
,
7188 unsigned int start
, unsigned int end
, int trunc
)
7191 unsigned int numbytes
;
7193 struct ocfs2_super
*osb
= OCFS2_SB(inode
->i_sb
);
7194 struct ocfs2_dinode
*di
= (struct ocfs2_dinode
*)di_bh
->b_data
;
7195 struct ocfs2_inline_data
*idata
= &di
->id2
.i_data
;
7197 if (end
> i_size_read(inode
))
7198 end
= i_size_read(inode
);
7200 BUG_ON(start
> end
);
7202 if (!(OCFS2_I(inode
)->ip_dyn_features
& OCFS2_INLINE_DATA_FL
) ||
7203 !(le16_to_cpu(di
->i_dyn_features
) & OCFS2_INLINE_DATA_FL
) ||
7204 !ocfs2_supports_inline_data(osb
)) {
7205 ocfs2_error(inode
->i_sb
,
7206 "Inline data flags for inode %llu don't agree! "
7207 "Disk: 0x%x, Memory: 0x%x, Superblock: 0x%x\n",
7208 (unsigned long long)OCFS2_I(inode
)->ip_blkno
,
7209 le16_to_cpu(di
->i_dyn_features
),
7210 OCFS2_I(inode
)->ip_dyn_features
,
7211 osb
->s_feature_incompat
);
7216 handle
= ocfs2_start_trans(osb
, OCFS2_INODE_UPDATE_CREDITS
);
7217 if (IS_ERR(handle
)) {
7218 ret
= PTR_ERR(handle
);
7223 ret
= ocfs2_journal_access_di(handle
, INODE_CACHE(inode
), di_bh
,
7224 OCFS2_JOURNAL_ACCESS_WRITE
);
7230 numbytes
= end
- start
;
7231 memset(idata
->id_data
+ start
, 0, numbytes
);
7234 * No need to worry about the data page here - it's been
7235 * truncated already and inline data doesn't need it for
7236 * pushing zero's to disk, so we'll let readpage pick it up
7240 i_size_write(inode
, start
);
7241 di
->i_size
= cpu_to_le64(start
);
7244 inode
->i_blocks
= ocfs2_inode_sector_count(inode
);
7245 inode
->i_ctime
= inode
->i_mtime
= CURRENT_TIME
;
7247 di
->i_ctime
= di
->i_mtime
= cpu_to_le64(inode
->i_ctime
.tv_sec
);
7248 di
->i_ctime_nsec
= di
->i_mtime_nsec
= cpu_to_le32(inode
->i_ctime
.tv_nsec
);
7250 ocfs2_update_inode_fsync_trans(handle
, inode
, 1);
7251 ocfs2_journal_dirty(handle
, di_bh
);
7254 ocfs2_commit_trans(osb
, handle
);
7260 static int ocfs2_trim_extent(struct super_block
*sb
,
7261 struct ocfs2_group_desc
*gd
,
7262 u32 start
, u32 count
)
7264 u64 discard
, bcount
;
7266 bcount
= ocfs2_clusters_to_blocks(sb
, count
);
7267 discard
= le64_to_cpu(gd
->bg_blkno
) +
7268 ocfs2_clusters_to_blocks(sb
, start
);
7270 trace_ocfs2_trim_extent(sb
, (unsigned long long)discard
, bcount
);
7272 return sb_issue_discard(sb
, discard
, bcount
, GFP_NOFS
, 0);
7275 static int ocfs2_trim_group(struct super_block
*sb
,
7276 struct ocfs2_group_desc
*gd
,
7277 u32 start
, u32 max
, u32 minbits
)
7279 int ret
= 0, count
= 0, next
;
7280 void *bitmap
= gd
->bg_bitmap
;
7282 if (le16_to_cpu(gd
->bg_free_bits_count
) < minbits
)
7285 trace_ocfs2_trim_group((unsigned long long)le64_to_cpu(gd
->bg_blkno
),
7286 start
, max
, minbits
);
7288 while (start
< max
) {
7289 start
= ocfs2_find_next_zero_bit(bitmap
, max
, start
);
7292 next
= ocfs2_find_next_bit(bitmap
, max
, start
);
7294 if ((next
- start
) >= minbits
) {
7295 ret
= ocfs2_trim_extent(sb
, gd
,
7296 start
, next
- start
);
7301 count
+= next
- start
;
7305 if (fatal_signal_pending(current
)) {
7306 count
= -ERESTARTSYS
;
7310 if ((le16_to_cpu(gd
->bg_free_bits_count
) - count
) < minbits
)
7320 int ocfs2_trim_fs(struct super_block
*sb
, struct fstrim_range
*range
)
7322 struct ocfs2_super
*osb
= OCFS2_SB(sb
);
7323 u64 start
, len
, trimmed
, first_group
, last_group
, group
;
7325 u32 first_bit
, last_bit
, minlen
;
7326 struct buffer_head
*main_bm_bh
= NULL
;
7327 struct inode
*main_bm_inode
= NULL
;
7328 struct buffer_head
*gd_bh
= NULL
;
7329 struct ocfs2_dinode
*main_bm
;
7330 struct ocfs2_group_desc
*gd
= NULL
;
7332 start
= range
->start
>> osb
->s_clustersize_bits
;
7333 len
= range
->len
>> osb
->s_clustersize_bits
;
7334 minlen
= range
->minlen
>> osb
->s_clustersize_bits
;
7336 if (minlen
>= osb
->bitmap_cpg
|| range
->len
< sb
->s_blocksize
)
7339 main_bm_inode
= ocfs2_get_system_file_inode(osb
,
7340 GLOBAL_BITMAP_SYSTEM_INODE
,
7341 OCFS2_INVALID_SLOT
);
7342 if (!main_bm_inode
) {
7348 mutex_lock(&main_bm_inode
->i_mutex
);
7350 ret
= ocfs2_inode_lock(main_bm_inode
, &main_bm_bh
, 0);
7355 main_bm
= (struct ocfs2_dinode
*)main_bm_bh
->b_data
;
7357 if (start
>= le32_to_cpu(main_bm
->i_clusters
)) {
7362 len
= range
->len
>> osb
->s_clustersize_bits
;
7363 if (start
+ len
> le32_to_cpu(main_bm
->i_clusters
))
7364 len
= le32_to_cpu(main_bm
->i_clusters
) - start
;
7366 trace_ocfs2_trim_fs(start
, len
, minlen
);
7368 /* Determine first and last group to examine based on start and len */
7369 first_group
= ocfs2_which_cluster_group(main_bm_inode
, start
);
7370 if (first_group
== osb
->first_cluster_group_blkno
)
7373 first_bit
= start
- ocfs2_blocks_to_clusters(sb
, first_group
);
7374 last_group
= ocfs2_which_cluster_group(main_bm_inode
, start
+ len
- 1);
7375 last_bit
= osb
->bitmap_cpg
;
7378 for (group
= first_group
; group
<= last_group
;) {
7379 if (first_bit
+ len
>= osb
->bitmap_cpg
)
7380 last_bit
= osb
->bitmap_cpg
;
7382 last_bit
= first_bit
+ len
;
7384 ret
= ocfs2_read_group_descriptor(main_bm_inode
,
7392 gd
= (struct ocfs2_group_desc
*)gd_bh
->b_data
;
7393 cnt
= ocfs2_trim_group(sb
, gd
, first_bit
, last_bit
, minlen
);
7403 len
-= osb
->bitmap_cpg
- first_bit
;
7405 if (group
== osb
->first_cluster_group_blkno
)
7406 group
= ocfs2_clusters_to_blocks(sb
, osb
->bitmap_cpg
);
7408 group
+= ocfs2_clusters_to_blocks(sb
, osb
->bitmap_cpg
);
7410 range
->len
= trimmed
* sb
->s_blocksize
;
7412 ocfs2_inode_unlock(main_bm_inode
, 0);
7415 mutex_unlock(&main_bm_inode
->i_mutex
);
7416 iput(main_bm_inode
);