blob: df186d2e82485b407697de04b4982b2507a03c08 [file] [log] [blame]
Mark Fashehccd979b2005-12-15 14:31:24 -08001/* -*- mode: c; c-basic-offset: 8; -*-
2 * vim: noexpandtab sw=8 ts=8 sts=0:
3 *
4 * alloc.c
5 *
6 * Extent allocs and frees
7 *
8 * Copyright (C) 2002, 2004 Oracle. All rights reserved.
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public
12 * License as published by the Free Software Foundation; either
13 * version 2 of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public
21 * License along with this program; if not, write to the
22 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
23 * Boston, MA 021110-1307, USA.
24 */
25
26#include <linux/fs.h>
27#include <linux/types.h>
28#include <linux/slab.h>
29#include <linux/highmem.h>
Mark Fasheh60b11392007-02-16 11:46:50 -080030#include <linux/swap.h>
Mark Fashehccd979b2005-12-15 14:31:24 -080031
32#define MLOG_MASK_PREFIX ML_DISK_ALLOC
33#include <cluster/masklog.h>
34
35#include "ocfs2.h"
36
37#include "alloc.h"
Mark Fasheh60b11392007-02-16 11:46:50 -080038#include "aops.h"
Mark Fashehccd979b2005-12-15 14:31:24 -080039#include "dlmglue.h"
40#include "extent_map.h"
41#include "inode.h"
42#include "journal.h"
43#include "localalloc.h"
44#include "suballoc.h"
45#include "sysfile.h"
46#include "file.h"
47#include "super.h"
48#include "uptodate.h"
49
50#include "buffer_head_io.h"
51
Mark Fashehccd979b2005-12-15 14:31:24 -080052static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc);
Mark Fasheh59a5e412007-06-22 15:52:36 -070053static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt,
54 struct ocfs2_extent_block *eb);
Mark Fashehccd979b2005-12-15 14:31:24 -080055
Mark Fashehdcd05382007-01-16 11:32:23 -080056/*
57 * Structures which describe a path through a btree, and functions to
58 * manipulate them.
59 *
60 * The idea here is to be as generic as possible with the tree
61 * manipulation code.
62 */
63struct ocfs2_path_item {
64 struct buffer_head *bh;
65 struct ocfs2_extent_list *el;
66};
67
68#define OCFS2_MAX_PATH_DEPTH 5
69
70struct ocfs2_path {
71 int p_tree_depth;
72 struct ocfs2_path_item p_node[OCFS2_MAX_PATH_DEPTH];
73};
74
75#define path_root_bh(_path) ((_path)->p_node[0].bh)
76#define path_root_el(_path) ((_path)->p_node[0].el)
77#define path_leaf_bh(_path) ((_path)->p_node[(_path)->p_tree_depth].bh)
78#define path_leaf_el(_path) ((_path)->p_node[(_path)->p_tree_depth].el)
79#define path_num_items(_path) ((_path)->p_tree_depth + 1)
80
81/*
82 * Reset the actual path elements so that we can re-use the structure
83 * to build another path. Generally, this involves freeing the buffer
84 * heads.
85 */
86static void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root)
87{
88 int i, start = 0, depth = 0;
89 struct ocfs2_path_item *node;
90
91 if (keep_root)
92 start = 1;
93
94 for(i = start; i < path_num_items(path); i++) {
95 node = &path->p_node[i];
96
97 brelse(node->bh);
98 node->bh = NULL;
99 node->el = NULL;
100 }
101
102 /*
103 * Tree depth may change during truncate, or insert. If we're
104 * keeping the root extent list, then make sure that our path
105 * structure reflects the proper depth.
106 */
107 if (keep_root)
108 depth = le16_to_cpu(path_root_el(path)->l_tree_depth);
109
110 path->p_tree_depth = depth;
111}
112
113static void ocfs2_free_path(struct ocfs2_path *path)
114{
115 if (path) {
116 ocfs2_reinit_path(path, 0);
117 kfree(path);
118 }
119}
120
121/*
Mark Fasheh328d5752007-06-18 10:48:04 -0700122 * All the elements of src into dest. After this call, src could be freed
123 * without affecting dest.
124 *
125 * Both paths should have the same root. Any non-root elements of dest
126 * will be freed.
127 */
128static void ocfs2_cp_path(struct ocfs2_path *dest, struct ocfs2_path *src)
129{
130 int i;
131
132 BUG_ON(path_root_bh(dest) != path_root_bh(src));
133 BUG_ON(path_root_el(dest) != path_root_el(src));
134
135 ocfs2_reinit_path(dest, 1);
136
137 for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
138 dest->p_node[i].bh = src->p_node[i].bh;
139 dest->p_node[i].el = src->p_node[i].el;
140
141 if (dest->p_node[i].bh)
142 get_bh(dest->p_node[i].bh);
143 }
144}
145
146/*
Mark Fashehdcd05382007-01-16 11:32:23 -0800147 * Make the *dest path the same as src and re-initialize src path to
148 * have a root only.
149 */
150static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src)
151{
152 int i;
153
154 BUG_ON(path_root_bh(dest) != path_root_bh(src));
155
156 for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
157 brelse(dest->p_node[i].bh);
158
159 dest->p_node[i].bh = src->p_node[i].bh;
160 dest->p_node[i].el = src->p_node[i].el;
161
162 src->p_node[i].bh = NULL;
163 src->p_node[i].el = NULL;
164 }
165}
166
167/*
168 * Insert an extent block at given index.
169 *
170 * This will not take an additional reference on eb_bh.
171 */
172static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index,
173 struct buffer_head *eb_bh)
174{
175 struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)eb_bh->b_data;
176
177 /*
178 * Right now, no root bh is an extent block, so this helps
179 * catch code errors with dinode trees. The assertion can be
180 * safely removed if we ever need to insert extent block
181 * structures at the root.
182 */
183 BUG_ON(index == 0);
184
185 path->p_node[index].bh = eb_bh;
186 path->p_node[index].el = &eb->h_list;
187}
188
189static struct ocfs2_path *ocfs2_new_path(struct buffer_head *root_bh,
190 struct ocfs2_extent_list *root_el)
191{
192 struct ocfs2_path *path;
193
194 BUG_ON(le16_to_cpu(root_el->l_tree_depth) >= OCFS2_MAX_PATH_DEPTH);
195
196 path = kzalloc(sizeof(*path), GFP_NOFS);
197 if (path) {
198 path->p_tree_depth = le16_to_cpu(root_el->l_tree_depth);
199 get_bh(root_bh);
200 path_root_bh(path) = root_bh;
201 path_root_el(path) = root_el;
202 }
203
204 return path;
205}
206
207/*
208 * Allocate and initialize a new path based on a disk inode tree.
209 */
210static struct ocfs2_path *ocfs2_new_inode_path(struct buffer_head *di_bh)
211{
212 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
213 struct ocfs2_extent_list *el = &di->id2.i_list;
214
215 return ocfs2_new_path(di_bh, el);
216}
217
218/*
219 * Convenience function to journal all components in a path.
220 */
221static int ocfs2_journal_access_path(struct inode *inode, handle_t *handle,
222 struct ocfs2_path *path)
223{
224 int i, ret = 0;
225
226 if (!path)
227 goto out;
228
229 for(i = 0; i < path_num_items(path); i++) {
230 ret = ocfs2_journal_access(handle, inode, path->p_node[i].bh,
231 OCFS2_JOURNAL_ACCESS_WRITE);
232 if (ret < 0) {
233 mlog_errno(ret);
234 goto out;
235 }
236 }
237
238out:
239 return ret;
240}
241
Mark Fasheh328d5752007-06-18 10:48:04 -0700242/*
243 * Return the index of the extent record which contains cluster #v_cluster.
244 * -1 is returned if it was not found.
245 *
246 * Should work fine on interior and exterior nodes.
247 */
248int ocfs2_search_extent_list(struct ocfs2_extent_list *el, u32 v_cluster)
249{
250 int ret = -1;
251 int i;
252 struct ocfs2_extent_rec *rec;
253 u32 rec_end, rec_start, clusters;
254
255 for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) {
256 rec = &el->l_recs[i];
257
258 rec_start = le32_to_cpu(rec->e_cpos);
259 clusters = ocfs2_rec_clusters(el, rec);
260
261 rec_end = rec_start + clusters;
262
263 if (v_cluster >= rec_start && v_cluster < rec_end) {
264 ret = i;
265 break;
266 }
267 }
268
269 return ret;
270}
271
Mark Fashehdcd05382007-01-16 11:32:23 -0800272enum ocfs2_contig_type {
273 CONTIG_NONE = 0,
274 CONTIG_LEFT,
Mark Fasheh328d5752007-06-18 10:48:04 -0700275 CONTIG_RIGHT,
276 CONTIG_LEFTRIGHT,
Mark Fashehdcd05382007-01-16 11:32:23 -0800277};
278
Mark Fashehe48edee2007-03-07 16:46:57 -0800279
280/*
281 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
282 * ocfs2_extent_contig only work properly against leaf nodes!
283 */
Mark Fashehdcd05382007-01-16 11:32:23 -0800284static int ocfs2_block_extent_contig(struct super_block *sb,
285 struct ocfs2_extent_rec *ext,
286 u64 blkno)
Mark Fashehccd979b2005-12-15 14:31:24 -0800287{
Mark Fashehe48edee2007-03-07 16:46:57 -0800288 u64 blk_end = le64_to_cpu(ext->e_blkno);
289
290 blk_end += ocfs2_clusters_to_blocks(sb,
291 le16_to_cpu(ext->e_leaf_clusters));
292
293 return blkno == blk_end;
Mark Fashehccd979b2005-12-15 14:31:24 -0800294}
295
Mark Fashehdcd05382007-01-16 11:32:23 -0800296static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left,
297 struct ocfs2_extent_rec *right)
298{
Mark Fashehe48edee2007-03-07 16:46:57 -0800299 u32 left_range;
300
301 left_range = le32_to_cpu(left->e_cpos) +
302 le16_to_cpu(left->e_leaf_clusters);
303
304 return (left_range == le32_to_cpu(right->e_cpos));
Mark Fashehdcd05382007-01-16 11:32:23 -0800305}
306
307static enum ocfs2_contig_type
308 ocfs2_extent_contig(struct inode *inode,
309 struct ocfs2_extent_rec *ext,
310 struct ocfs2_extent_rec *insert_rec)
311{
312 u64 blkno = le64_to_cpu(insert_rec->e_blkno);
313
Mark Fasheh328d5752007-06-18 10:48:04 -0700314 /*
315 * Refuse to coalesce extent records with different flag
316 * fields - we don't want to mix unwritten extents with user
317 * data.
318 */
319 if (ext->e_flags != insert_rec->e_flags)
320 return CONTIG_NONE;
321
Mark Fashehdcd05382007-01-16 11:32:23 -0800322 if (ocfs2_extents_adjacent(ext, insert_rec) &&
323 ocfs2_block_extent_contig(inode->i_sb, ext, blkno))
324 return CONTIG_RIGHT;
325
326 blkno = le64_to_cpu(ext->e_blkno);
327 if (ocfs2_extents_adjacent(insert_rec, ext) &&
328 ocfs2_block_extent_contig(inode->i_sb, insert_rec, blkno))
329 return CONTIG_LEFT;
330
331 return CONTIG_NONE;
332}
333
334/*
335 * NOTE: We can have pretty much any combination of contiguousness and
336 * appending.
337 *
338 * The usefulness of APPEND_TAIL is more in that it lets us know that
339 * we'll have to update the path to that leaf.
340 */
341enum ocfs2_append_type {
342 APPEND_NONE = 0,
343 APPEND_TAIL,
344};
345
Mark Fasheh328d5752007-06-18 10:48:04 -0700346enum ocfs2_split_type {
347 SPLIT_NONE = 0,
348 SPLIT_LEFT,
349 SPLIT_RIGHT,
350};
351
Mark Fashehdcd05382007-01-16 11:32:23 -0800352struct ocfs2_insert_type {
Mark Fasheh328d5752007-06-18 10:48:04 -0700353 enum ocfs2_split_type ins_split;
Mark Fashehdcd05382007-01-16 11:32:23 -0800354 enum ocfs2_append_type ins_appending;
355 enum ocfs2_contig_type ins_contig;
356 int ins_contig_index;
357 int ins_free_records;
358 int ins_tree_depth;
359};
360
Mark Fasheh328d5752007-06-18 10:48:04 -0700361struct ocfs2_merge_ctxt {
362 enum ocfs2_contig_type c_contig_type;
363 int c_has_empty_extent;
364 int c_split_covers_rec;
365 int c_used_tail_recs;
366};
367
Mark Fashehccd979b2005-12-15 14:31:24 -0800368/*
369 * How many free extents have we got before we need more meta data?
370 */
371int ocfs2_num_free_extents(struct ocfs2_super *osb,
372 struct inode *inode,
373 struct ocfs2_dinode *fe)
374{
375 int retval;
376 struct ocfs2_extent_list *el;
377 struct ocfs2_extent_block *eb;
378 struct buffer_head *eb_bh = NULL;
379
380 mlog_entry_void();
381
382 if (!OCFS2_IS_VALID_DINODE(fe)) {
383 OCFS2_RO_ON_INVALID_DINODE(inode->i_sb, fe);
384 retval = -EIO;
385 goto bail;
386 }
387
388 if (fe->i_last_eb_blk) {
389 retval = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk),
390 &eb_bh, OCFS2_BH_CACHED, inode);
391 if (retval < 0) {
392 mlog_errno(retval);
393 goto bail;
394 }
395 eb = (struct ocfs2_extent_block *) eb_bh->b_data;
396 el = &eb->h_list;
397 } else
398 el = &fe->id2.i_list;
399
400 BUG_ON(el->l_tree_depth != 0);
401
402 retval = le16_to_cpu(el->l_count) - le16_to_cpu(el->l_next_free_rec);
403bail:
404 if (eb_bh)
405 brelse(eb_bh);
406
407 mlog_exit(retval);
408 return retval;
409}
410
411/* expects array to already be allocated
412 *
413 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
414 * l_count for you
415 */
416static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb,
Mark Fasheh1fabe142006-10-09 18:11:45 -0700417 handle_t *handle,
Mark Fashehccd979b2005-12-15 14:31:24 -0800418 struct inode *inode,
419 int wanted,
420 struct ocfs2_alloc_context *meta_ac,
421 struct buffer_head *bhs[])
422{
423 int count, status, i;
424 u16 suballoc_bit_start;
425 u32 num_got;
426 u64 first_blkno;
427 struct ocfs2_extent_block *eb;
428
429 mlog_entry_void();
430
431 count = 0;
432 while (count < wanted) {
433 status = ocfs2_claim_metadata(osb,
434 handle,
435 meta_ac,
436 wanted - count,
437 &suballoc_bit_start,
438 &num_got,
439 &first_blkno);
440 if (status < 0) {
441 mlog_errno(status);
442 goto bail;
443 }
444
445 for(i = count; i < (num_got + count); i++) {
446 bhs[i] = sb_getblk(osb->sb, first_blkno);
447 if (bhs[i] == NULL) {
448 status = -EIO;
449 mlog_errno(status);
450 goto bail;
451 }
452 ocfs2_set_new_buffer_uptodate(inode, bhs[i]);
453
454 status = ocfs2_journal_access(handle, inode, bhs[i],
455 OCFS2_JOURNAL_ACCESS_CREATE);
456 if (status < 0) {
457 mlog_errno(status);
458 goto bail;
459 }
460
461 memset(bhs[i]->b_data, 0, osb->sb->s_blocksize);
462 eb = (struct ocfs2_extent_block *) bhs[i]->b_data;
463 /* Ok, setup the minimal stuff here. */
464 strcpy(eb->h_signature, OCFS2_EXTENT_BLOCK_SIGNATURE);
465 eb->h_blkno = cpu_to_le64(first_blkno);
466 eb->h_fs_generation = cpu_to_le32(osb->fs_generation);
Mark Fashehccd979b2005-12-15 14:31:24 -0800467 eb->h_suballoc_slot = cpu_to_le16(osb->slot_num);
Mark Fashehccd979b2005-12-15 14:31:24 -0800468 eb->h_suballoc_bit = cpu_to_le16(suballoc_bit_start);
469 eb->h_list.l_count =
470 cpu_to_le16(ocfs2_extent_recs_per_eb(osb->sb));
471
472 suballoc_bit_start++;
473 first_blkno++;
474
475 /* We'll also be dirtied by the caller, so
476 * this isn't absolutely necessary. */
477 status = ocfs2_journal_dirty(handle, bhs[i]);
478 if (status < 0) {
479 mlog_errno(status);
480 goto bail;
481 }
482 }
483
484 count += num_got;
485 }
486
487 status = 0;
488bail:
489 if (status < 0) {
490 for(i = 0; i < wanted; i++) {
491 if (bhs[i])
492 brelse(bhs[i]);
493 bhs[i] = NULL;
494 }
495 }
496 mlog_exit(status);
497 return status;
498}
499
500/*
Mark Fashehdcd05382007-01-16 11:32:23 -0800501 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
502 *
503 * Returns the sum of the rightmost extent rec logical offset and
504 * cluster count.
505 *
506 * ocfs2_add_branch() uses this to determine what logical cluster
507 * value should be populated into the leftmost new branch records.
508 *
509 * ocfs2_shift_tree_depth() uses this to determine the # clusters
510 * value for the new topmost tree record.
511 */
512static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el)
513{
514 int i;
515
516 i = le16_to_cpu(el->l_next_free_rec) - 1;
517
518 return le32_to_cpu(el->l_recs[i].e_cpos) +
Mark Fashehe48edee2007-03-07 16:46:57 -0800519 ocfs2_rec_clusters(el, &el->l_recs[i]);
Mark Fashehdcd05382007-01-16 11:32:23 -0800520}
521
522/*
Mark Fashehccd979b2005-12-15 14:31:24 -0800523 * Add an entire tree branch to our inode. eb_bh is the extent block
524 * to start at, if we don't want to start the branch at the dinode
525 * structure.
526 *
527 * last_eb_bh is required as we have to update it's next_leaf pointer
528 * for the new last extent block.
529 *
530 * the new branch will be 'empty' in the sense that every block will
Mark Fashehe48edee2007-03-07 16:46:57 -0800531 * contain a single record with cluster count == 0.
Mark Fashehccd979b2005-12-15 14:31:24 -0800532 */
533static int ocfs2_add_branch(struct ocfs2_super *osb,
Mark Fasheh1fabe142006-10-09 18:11:45 -0700534 handle_t *handle,
Mark Fashehccd979b2005-12-15 14:31:24 -0800535 struct inode *inode,
536 struct buffer_head *fe_bh,
537 struct buffer_head *eb_bh,
Mark Fasheh328d5752007-06-18 10:48:04 -0700538 struct buffer_head **last_eb_bh,
Mark Fashehccd979b2005-12-15 14:31:24 -0800539 struct ocfs2_alloc_context *meta_ac)
540{
541 int status, new_blocks, i;
542 u64 next_blkno, new_last_eb_blk;
543 struct buffer_head *bh;
544 struct buffer_head **new_eb_bhs = NULL;
545 struct ocfs2_dinode *fe;
546 struct ocfs2_extent_block *eb;
547 struct ocfs2_extent_list *eb_el;
548 struct ocfs2_extent_list *el;
Mark Fashehdcd05382007-01-16 11:32:23 -0800549 u32 new_cpos;
Mark Fashehccd979b2005-12-15 14:31:24 -0800550
551 mlog_entry_void();
552
Mark Fasheh328d5752007-06-18 10:48:04 -0700553 BUG_ON(!last_eb_bh || !*last_eb_bh);
Mark Fashehccd979b2005-12-15 14:31:24 -0800554
555 fe = (struct ocfs2_dinode *) fe_bh->b_data;
556
557 if (eb_bh) {
558 eb = (struct ocfs2_extent_block *) eb_bh->b_data;
559 el = &eb->h_list;
560 } else
561 el = &fe->id2.i_list;
562
563 /* we never add a branch to a leaf. */
564 BUG_ON(!el->l_tree_depth);
565
566 new_blocks = le16_to_cpu(el->l_tree_depth);
567
568 /* allocate the number of new eb blocks we need */
569 new_eb_bhs = kcalloc(new_blocks, sizeof(struct buffer_head *),
570 GFP_KERNEL);
571 if (!new_eb_bhs) {
572 status = -ENOMEM;
573 mlog_errno(status);
574 goto bail;
575 }
576
577 status = ocfs2_create_new_meta_bhs(osb, handle, inode, new_blocks,
578 meta_ac, new_eb_bhs);
579 if (status < 0) {
580 mlog_errno(status);
581 goto bail;
582 }
583
Mark Fasheh328d5752007-06-18 10:48:04 -0700584 eb = (struct ocfs2_extent_block *)(*last_eb_bh)->b_data;
Mark Fashehdcd05382007-01-16 11:32:23 -0800585 new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list);
586
Mark Fashehccd979b2005-12-15 14:31:24 -0800587 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
588 * linked with the rest of the tree.
589 * conversly, new_eb_bhs[0] is the new bottommost leaf.
590 *
591 * when we leave the loop, new_last_eb_blk will point to the
592 * newest leaf, and next_blkno will point to the topmost extent
593 * block. */
594 next_blkno = new_last_eb_blk = 0;
595 for(i = 0; i < new_blocks; i++) {
596 bh = new_eb_bhs[i];
597 eb = (struct ocfs2_extent_block *) bh->b_data;
598 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
599 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
600 status = -EIO;
601 goto bail;
602 }
603 eb_el = &eb->h_list;
604
605 status = ocfs2_journal_access(handle, inode, bh,
606 OCFS2_JOURNAL_ACCESS_CREATE);
607 if (status < 0) {
608 mlog_errno(status);
609 goto bail;
610 }
611
612 eb->h_next_leaf_blk = 0;
613 eb_el->l_tree_depth = cpu_to_le16(i);
614 eb_el->l_next_free_rec = cpu_to_le16(1);
Mark Fashehdcd05382007-01-16 11:32:23 -0800615 /*
616 * This actually counts as an empty extent as
617 * c_clusters == 0
618 */
619 eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos);
Mark Fashehccd979b2005-12-15 14:31:24 -0800620 eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno);
Mark Fashehe48edee2007-03-07 16:46:57 -0800621 /*
622 * eb_el isn't always an interior node, but even leaf
623 * nodes want a zero'd flags and reserved field so
624 * this gets the whole 32 bits regardless of use.
625 */
626 eb_el->l_recs[0].e_int_clusters = cpu_to_le32(0);
Mark Fashehccd979b2005-12-15 14:31:24 -0800627 if (!eb_el->l_tree_depth)
628 new_last_eb_blk = le64_to_cpu(eb->h_blkno);
629
630 status = ocfs2_journal_dirty(handle, bh);
631 if (status < 0) {
632 mlog_errno(status);
633 goto bail;
634 }
635
636 next_blkno = le64_to_cpu(eb->h_blkno);
637 }
638
639 /* This is a bit hairy. We want to update up to three blocks
640 * here without leaving any of them in an inconsistent state
641 * in case of error. We don't have to worry about
642 * journal_dirty erroring as it won't unless we've aborted the
643 * handle (in which case we would never be here) so reserving
644 * the write with journal_access is all we need to do. */
Mark Fasheh328d5752007-06-18 10:48:04 -0700645 status = ocfs2_journal_access(handle, inode, *last_eb_bh,
Mark Fashehccd979b2005-12-15 14:31:24 -0800646 OCFS2_JOURNAL_ACCESS_WRITE);
647 if (status < 0) {
648 mlog_errno(status);
649 goto bail;
650 }
651 status = ocfs2_journal_access(handle, inode, fe_bh,
652 OCFS2_JOURNAL_ACCESS_WRITE);
653 if (status < 0) {
654 mlog_errno(status);
655 goto bail;
656 }
657 if (eb_bh) {
658 status = ocfs2_journal_access(handle, inode, eb_bh,
659 OCFS2_JOURNAL_ACCESS_WRITE);
660 if (status < 0) {
661 mlog_errno(status);
662 goto bail;
663 }
664 }
665
666 /* Link the new branch into the rest of the tree (el will
667 * either be on the fe, or the extent block passed in. */
668 i = le16_to_cpu(el->l_next_free_rec);
669 el->l_recs[i].e_blkno = cpu_to_le64(next_blkno);
Mark Fashehdcd05382007-01-16 11:32:23 -0800670 el->l_recs[i].e_cpos = cpu_to_le32(new_cpos);
Mark Fashehe48edee2007-03-07 16:46:57 -0800671 el->l_recs[i].e_int_clusters = 0;
Mark Fashehccd979b2005-12-15 14:31:24 -0800672 le16_add_cpu(&el->l_next_free_rec, 1);
673
674 /* fe needs a new last extent block pointer, as does the
675 * next_leaf on the previously last-extent-block. */
676 fe->i_last_eb_blk = cpu_to_le64(new_last_eb_blk);
677
Mark Fasheh328d5752007-06-18 10:48:04 -0700678 eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data;
Mark Fashehccd979b2005-12-15 14:31:24 -0800679 eb->h_next_leaf_blk = cpu_to_le64(new_last_eb_blk);
680
Mark Fasheh328d5752007-06-18 10:48:04 -0700681 status = ocfs2_journal_dirty(handle, *last_eb_bh);
Mark Fashehccd979b2005-12-15 14:31:24 -0800682 if (status < 0)
683 mlog_errno(status);
684 status = ocfs2_journal_dirty(handle, fe_bh);
685 if (status < 0)
686 mlog_errno(status);
687 if (eb_bh) {
688 status = ocfs2_journal_dirty(handle, eb_bh);
689 if (status < 0)
690 mlog_errno(status);
691 }
692
Mark Fasheh328d5752007-06-18 10:48:04 -0700693 /*
694 * Some callers want to track the rightmost leaf so pass it
695 * back here.
696 */
697 brelse(*last_eb_bh);
698 get_bh(new_eb_bhs[0]);
699 *last_eb_bh = new_eb_bhs[0];
700
Mark Fashehccd979b2005-12-15 14:31:24 -0800701 status = 0;
702bail:
703 if (new_eb_bhs) {
704 for (i = 0; i < new_blocks; i++)
705 if (new_eb_bhs[i])
706 brelse(new_eb_bhs[i]);
707 kfree(new_eb_bhs);
708 }
709
710 mlog_exit(status);
711 return status;
712}
713
714/*
715 * adds another level to the allocation tree.
716 * returns back the new extent block so you can add a branch to it
717 * after this call.
718 */
719static int ocfs2_shift_tree_depth(struct ocfs2_super *osb,
Mark Fasheh1fabe142006-10-09 18:11:45 -0700720 handle_t *handle,
Mark Fashehccd979b2005-12-15 14:31:24 -0800721 struct inode *inode,
722 struct buffer_head *fe_bh,
723 struct ocfs2_alloc_context *meta_ac,
724 struct buffer_head **ret_new_eb_bh)
725{
726 int status, i;
Mark Fashehdcd05382007-01-16 11:32:23 -0800727 u32 new_clusters;
Mark Fashehccd979b2005-12-15 14:31:24 -0800728 struct buffer_head *new_eb_bh = NULL;
729 struct ocfs2_dinode *fe;
730 struct ocfs2_extent_block *eb;
731 struct ocfs2_extent_list *fe_el;
732 struct ocfs2_extent_list *eb_el;
733
734 mlog_entry_void();
735
736 status = ocfs2_create_new_meta_bhs(osb, handle, inode, 1, meta_ac,
737 &new_eb_bh);
738 if (status < 0) {
739 mlog_errno(status);
740 goto bail;
741 }
742
743 eb = (struct ocfs2_extent_block *) new_eb_bh->b_data;
744 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
745 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
746 status = -EIO;
747 goto bail;
748 }
749
750 eb_el = &eb->h_list;
751 fe = (struct ocfs2_dinode *) fe_bh->b_data;
752 fe_el = &fe->id2.i_list;
753
754 status = ocfs2_journal_access(handle, inode, new_eb_bh,
755 OCFS2_JOURNAL_ACCESS_CREATE);
756 if (status < 0) {
757 mlog_errno(status);
758 goto bail;
759 }
760
761 /* copy the fe data into the new extent block */
762 eb_el->l_tree_depth = fe_el->l_tree_depth;
763 eb_el->l_next_free_rec = fe_el->l_next_free_rec;
Mark Fashehe48edee2007-03-07 16:46:57 -0800764 for(i = 0; i < le16_to_cpu(fe_el->l_next_free_rec); i++)
765 eb_el->l_recs[i] = fe_el->l_recs[i];
Mark Fashehccd979b2005-12-15 14:31:24 -0800766
767 status = ocfs2_journal_dirty(handle, new_eb_bh);
768 if (status < 0) {
769 mlog_errno(status);
770 goto bail;
771 }
772
773 status = ocfs2_journal_access(handle, inode, fe_bh,
774 OCFS2_JOURNAL_ACCESS_WRITE);
775 if (status < 0) {
776 mlog_errno(status);
777 goto bail;
778 }
779
Mark Fashehdcd05382007-01-16 11:32:23 -0800780 new_clusters = ocfs2_sum_rightmost_rec(eb_el);
781
Mark Fashehccd979b2005-12-15 14:31:24 -0800782 /* update fe now */
783 le16_add_cpu(&fe_el->l_tree_depth, 1);
784 fe_el->l_recs[0].e_cpos = 0;
785 fe_el->l_recs[0].e_blkno = eb->h_blkno;
Mark Fashehe48edee2007-03-07 16:46:57 -0800786 fe_el->l_recs[0].e_int_clusters = cpu_to_le32(new_clusters);
787 for(i = 1; i < le16_to_cpu(fe_el->l_next_free_rec); i++)
788 memset(&fe_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
Mark Fashehccd979b2005-12-15 14:31:24 -0800789 fe_el->l_next_free_rec = cpu_to_le16(1);
790
791 /* If this is our 1st tree depth shift, then last_eb_blk
792 * becomes the allocated extent block */
793 if (fe_el->l_tree_depth == cpu_to_le16(1))
794 fe->i_last_eb_blk = eb->h_blkno;
795
796 status = ocfs2_journal_dirty(handle, fe_bh);
797 if (status < 0) {
798 mlog_errno(status);
799 goto bail;
800 }
801
802 *ret_new_eb_bh = new_eb_bh;
803 new_eb_bh = NULL;
804 status = 0;
805bail:
806 if (new_eb_bh)
807 brelse(new_eb_bh);
808
809 mlog_exit(status);
810 return status;
811}
812
813/*
Mark Fashehccd979b2005-12-15 14:31:24 -0800814 * Should only be called when there is no space left in any of the
815 * leaf nodes. What we want to do is find the lowest tree depth
816 * non-leaf extent block with room for new records. There are three
817 * valid results of this search:
818 *
819 * 1) a lowest extent block is found, then we pass it back in
820 * *lowest_eb_bh and return '0'
821 *
822 * 2) the search fails to find anything, but the dinode has room. We
823 * pass NULL back in *lowest_eb_bh, but still return '0'
824 *
825 * 3) the search fails to find anything AND the dinode is full, in
826 * which case we return > 0
827 *
828 * return status < 0 indicates an error.
829 */
830static int ocfs2_find_branch_target(struct ocfs2_super *osb,
831 struct inode *inode,
832 struct buffer_head *fe_bh,
833 struct buffer_head **target_bh)
834{
835 int status = 0, i;
836 u64 blkno;
837 struct ocfs2_dinode *fe;
838 struct ocfs2_extent_block *eb;
839 struct ocfs2_extent_list *el;
840 struct buffer_head *bh = NULL;
841 struct buffer_head *lowest_bh = NULL;
842
843 mlog_entry_void();
844
845 *target_bh = NULL;
846
847 fe = (struct ocfs2_dinode *) fe_bh->b_data;
848 el = &fe->id2.i_list;
849
850 while(le16_to_cpu(el->l_tree_depth) > 1) {
851 if (le16_to_cpu(el->l_next_free_rec) == 0) {
Mark Fashehb06970532006-03-03 10:24:33 -0800852 ocfs2_error(inode->i_sb, "Dinode %llu has empty "
Mark Fashehccd979b2005-12-15 14:31:24 -0800853 "extent list (next_free_rec == 0)",
Mark Fashehb06970532006-03-03 10:24:33 -0800854 (unsigned long long)OCFS2_I(inode)->ip_blkno);
Mark Fashehccd979b2005-12-15 14:31:24 -0800855 status = -EIO;
856 goto bail;
857 }
858 i = le16_to_cpu(el->l_next_free_rec) - 1;
859 blkno = le64_to_cpu(el->l_recs[i].e_blkno);
860 if (!blkno) {
Mark Fashehb06970532006-03-03 10:24:33 -0800861 ocfs2_error(inode->i_sb, "Dinode %llu has extent "
Mark Fashehccd979b2005-12-15 14:31:24 -0800862 "list where extent # %d has no physical "
863 "block start",
Mark Fashehb06970532006-03-03 10:24:33 -0800864 (unsigned long long)OCFS2_I(inode)->ip_blkno, i);
Mark Fashehccd979b2005-12-15 14:31:24 -0800865 status = -EIO;
866 goto bail;
867 }
868
869 if (bh) {
870 brelse(bh);
871 bh = NULL;
872 }
873
874 status = ocfs2_read_block(osb, blkno, &bh, OCFS2_BH_CACHED,
875 inode);
876 if (status < 0) {
877 mlog_errno(status);
878 goto bail;
879 }
880
881 eb = (struct ocfs2_extent_block *) bh->b_data;
882 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
883 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
884 status = -EIO;
885 goto bail;
886 }
887 el = &eb->h_list;
888
889 if (le16_to_cpu(el->l_next_free_rec) <
890 le16_to_cpu(el->l_count)) {
891 if (lowest_bh)
892 brelse(lowest_bh);
893 lowest_bh = bh;
894 get_bh(lowest_bh);
895 }
896 }
897
898 /* If we didn't find one and the fe doesn't have any room,
899 * then return '1' */
900 if (!lowest_bh
901 && (fe->id2.i_list.l_next_free_rec == fe->id2.i_list.l_count))
902 status = 1;
903
904 *target_bh = lowest_bh;
905bail:
906 if (bh)
907 brelse(bh);
908
909 mlog_exit(status);
910 return status;
911}
912
Mark Fashehe48edee2007-03-07 16:46:57 -0800913/*
Mark Fashehc3afcbb2007-05-29 14:28:51 -0700914 * Grow a b-tree so that it has more records.
915 *
916 * We might shift the tree depth in which case existing paths should
917 * be considered invalid.
918 *
919 * Tree depth after the grow is returned via *final_depth.
Mark Fasheh328d5752007-06-18 10:48:04 -0700920 *
921 * *last_eb_bh will be updated by ocfs2_add_branch().
Mark Fashehc3afcbb2007-05-29 14:28:51 -0700922 */
923static int ocfs2_grow_tree(struct inode *inode, handle_t *handle,
924 struct buffer_head *di_bh, int *final_depth,
Mark Fasheh328d5752007-06-18 10:48:04 -0700925 struct buffer_head **last_eb_bh,
Mark Fashehc3afcbb2007-05-29 14:28:51 -0700926 struct ocfs2_alloc_context *meta_ac)
927{
928 int ret, shift;
929 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
930 int depth = le16_to_cpu(di->id2.i_list.l_tree_depth);
931 struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
932 struct buffer_head *bh = NULL;
933
934 BUG_ON(meta_ac == NULL);
935
936 shift = ocfs2_find_branch_target(osb, inode, di_bh, &bh);
937 if (shift < 0) {
938 ret = shift;
939 mlog_errno(ret);
940 goto out;
941 }
942
943 /* We traveled all the way to the bottom of the allocation tree
944 * and didn't find room for any more extents - we need to add
945 * another tree level */
946 if (shift) {
947 BUG_ON(bh);
948 mlog(0, "need to shift tree depth (current = %d)\n", depth);
949
950 /* ocfs2_shift_tree_depth will return us a buffer with
951 * the new extent block (so we can pass that to
952 * ocfs2_add_branch). */
953 ret = ocfs2_shift_tree_depth(osb, handle, inode, di_bh,
954 meta_ac, &bh);
955 if (ret < 0) {
956 mlog_errno(ret);
957 goto out;
958 }
959 depth++;
Mark Fasheh328d5752007-06-18 10:48:04 -0700960 if (depth == 1) {
961 /*
962 * Special case: we have room now if we shifted from
963 * tree_depth 0, so no more work needs to be done.
964 *
965 * We won't be calling add_branch, so pass
966 * back *last_eb_bh as the new leaf. At depth
967 * zero, it should always be null so there's
968 * no reason to brelse.
969 */
970 BUG_ON(*last_eb_bh);
971 get_bh(bh);
972 *last_eb_bh = bh;
Mark Fashehc3afcbb2007-05-29 14:28:51 -0700973 goto out;
Mark Fasheh328d5752007-06-18 10:48:04 -0700974 }
Mark Fashehc3afcbb2007-05-29 14:28:51 -0700975 }
976
977 /* call ocfs2_add_branch to add the final part of the tree with
978 * the new data. */
979 mlog(0, "add branch. bh = %p\n", bh);
980 ret = ocfs2_add_branch(osb, handle, inode, di_bh, bh, last_eb_bh,
981 meta_ac);
982 if (ret < 0) {
983 mlog_errno(ret);
984 goto out;
985 }
986
987out:
988 if (final_depth)
989 *final_depth = depth;
990 brelse(bh);
991 return ret;
992}
993
994/*
Mark Fashehe48edee2007-03-07 16:46:57 -0800995 * This is only valid for leaf nodes, which are the only ones that can
996 * have empty extents anyway.
997 */
Mark Fashehdcd05382007-01-16 11:32:23 -0800998static inline int ocfs2_is_empty_extent(struct ocfs2_extent_rec *rec)
999{
Mark Fashehe48edee2007-03-07 16:46:57 -08001000 return !rec->e_leaf_clusters;
Mark Fashehdcd05382007-01-16 11:32:23 -08001001}
1002
1003/*
1004 * This function will discard the rightmost extent record.
1005 */
1006static void ocfs2_shift_records_right(struct ocfs2_extent_list *el)
1007{
1008 int next_free = le16_to_cpu(el->l_next_free_rec);
1009 int count = le16_to_cpu(el->l_count);
1010 unsigned int num_bytes;
1011
1012 BUG_ON(!next_free);
1013 /* This will cause us to go off the end of our extent list. */
1014 BUG_ON(next_free >= count);
1015
1016 num_bytes = sizeof(struct ocfs2_extent_rec) * next_free;
1017
1018 memmove(&el->l_recs[1], &el->l_recs[0], num_bytes);
1019}
1020
1021static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el,
1022 struct ocfs2_extent_rec *insert_rec)
1023{
1024 int i, insert_index, next_free, has_empty, num_bytes;
1025 u32 insert_cpos = le32_to_cpu(insert_rec->e_cpos);
1026 struct ocfs2_extent_rec *rec;
1027
1028 next_free = le16_to_cpu(el->l_next_free_rec);
1029 has_empty = ocfs2_is_empty_extent(&el->l_recs[0]);
1030
1031 BUG_ON(!next_free);
1032
1033 /* The tree code before us didn't allow enough room in the leaf. */
1034 if (el->l_next_free_rec == el->l_count && !has_empty)
1035 BUG();
1036
1037 /*
1038 * The easiest way to approach this is to just remove the
1039 * empty extent and temporarily decrement next_free.
1040 */
1041 if (has_empty) {
1042 /*
1043 * If next_free was 1 (only an empty extent), this
1044 * loop won't execute, which is fine. We still want
1045 * the decrement above to happen.
1046 */
1047 for(i = 0; i < (next_free - 1); i++)
1048 el->l_recs[i] = el->l_recs[i+1];
1049
1050 next_free--;
1051 }
1052
1053 /*
1054 * Figure out what the new record index should be.
1055 */
1056 for(i = 0; i < next_free; i++) {
1057 rec = &el->l_recs[i];
1058
1059 if (insert_cpos < le32_to_cpu(rec->e_cpos))
1060 break;
1061 }
1062 insert_index = i;
1063
1064 mlog(0, "ins %u: index %d, has_empty %d, next_free %d, count %d\n",
1065 insert_cpos, insert_index, has_empty, next_free, le16_to_cpu(el->l_count));
1066
1067 BUG_ON(insert_index < 0);
1068 BUG_ON(insert_index >= le16_to_cpu(el->l_count));
1069 BUG_ON(insert_index > next_free);
1070
1071 /*
1072 * No need to memmove if we're just adding to the tail.
1073 */
1074 if (insert_index != next_free) {
1075 BUG_ON(next_free >= le16_to_cpu(el->l_count));
1076
1077 num_bytes = next_free - insert_index;
1078 num_bytes *= sizeof(struct ocfs2_extent_rec);
1079 memmove(&el->l_recs[insert_index + 1],
1080 &el->l_recs[insert_index],
1081 num_bytes);
1082 }
1083
1084 /*
1085 * Either we had an empty extent, and need to re-increment or
1086 * there was no empty extent on a non full rightmost leaf node,
1087 * in which case we still need to increment.
1088 */
1089 next_free++;
1090 el->l_next_free_rec = cpu_to_le16(next_free);
1091 /*
1092 * Make sure none of the math above just messed up our tree.
1093 */
1094 BUG_ON(le16_to_cpu(el->l_next_free_rec) > le16_to_cpu(el->l_count));
1095
1096 el->l_recs[insert_index] = *insert_rec;
1097
1098}
1099
Mark Fasheh328d5752007-06-18 10:48:04 -07001100static void ocfs2_remove_empty_extent(struct ocfs2_extent_list *el)
1101{
1102 int size, num_recs = le16_to_cpu(el->l_next_free_rec);
1103
1104 BUG_ON(num_recs == 0);
1105
1106 if (ocfs2_is_empty_extent(&el->l_recs[0])) {
1107 num_recs--;
1108 size = num_recs * sizeof(struct ocfs2_extent_rec);
1109 memmove(&el->l_recs[0], &el->l_recs[1], size);
1110 memset(&el->l_recs[num_recs], 0,
1111 sizeof(struct ocfs2_extent_rec));
1112 el->l_next_free_rec = cpu_to_le16(num_recs);
1113 }
1114}
1115
Mark Fashehdcd05382007-01-16 11:32:23 -08001116/*
1117 * Create an empty extent record .
1118 *
1119 * l_next_free_rec may be updated.
1120 *
1121 * If an empty extent already exists do nothing.
1122 */
1123static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el)
1124{
1125 int next_free = le16_to_cpu(el->l_next_free_rec);
1126
Mark Fashehe48edee2007-03-07 16:46:57 -08001127 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
1128
Mark Fashehdcd05382007-01-16 11:32:23 -08001129 if (next_free == 0)
1130 goto set_and_inc;
1131
1132 if (ocfs2_is_empty_extent(&el->l_recs[0]))
1133 return;
1134
1135 mlog_bug_on_msg(el->l_count == el->l_next_free_rec,
1136 "Asked to create an empty extent in a full list:\n"
1137 "count = %u, tree depth = %u",
1138 le16_to_cpu(el->l_count),
1139 le16_to_cpu(el->l_tree_depth));
1140
1141 ocfs2_shift_records_right(el);
1142
1143set_and_inc:
1144 le16_add_cpu(&el->l_next_free_rec, 1);
1145 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1146}
1147
1148/*
1149 * For a rotation which involves two leaf nodes, the "root node" is
1150 * the lowest level tree node which contains a path to both leafs. This
1151 * resulting set of information can be used to form a complete "subtree"
1152 *
1153 * This function is passed two full paths from the dinode down to a
1154 * pair of adjacent leaves. It's task is to figure out which path
1155 * index contains the subtree root - this can be the root index itself
1156 * in a worst-case rotation.
1157 *
1158 * The array index of the subtree root is passed back.
1159 */
1160static int ocfs2_find_subtree_root(struct inode *inode,
1161 struct ocfs2_path *left,
1162 struct ocfs2_path *right)
1163{
1164 int i = 0;
1165
1166 /*
1167 * Check that the caller passed in two paths from the same tree.
1168 */
1169 BUG_ON(path_root_bh(left) != path_root_bh(right));
1170
1171 do {
1172 i++;
1173
1174 /*
1175 * The caller didn't pass two adjacent paths.
1176 */
1177 mlog_bug_on_msg(i > left->p_tree_depth,
1178 "Inode %lu, left depth %u, right depth %u\n"
1179 "left leaf blk %llu, right leaf blk %llu\n",
1180 inode->i_ino, left->p_tree_depth,
1181 right->p_tree_depth,
1182 (unsigned long long)path_leaf_bh(left)->b_blocknr,
1183 (unsigned long long)path_leaf_bh(right)->b_blocknr);
1184 } while (left->p_node[i].bh->b_blocknr ==
1185 right->p_node[i].bh->b_blocknr);
1186
1187 return i - 1;
1188}
1189
1190typedef void (path_insert_t)(void *, struct buffer_head *);
1191
1192/*
1193 * Traverse a btree path in search of cpos, starting at root_el.
1194 *
1195 * This code can be called with a cpos larger than the tree, in which
1196 * case it will return the rightmost path.
1197 */
1198static int __ocfs2_find_path(struct inode *inode,
1199 struct ocfs2_extent_list *root_el, u32 cpos,
1200 path_insert_t *func, void *data)
1201{
1202 int i, ret = 0;
1203 u32 range;
1204 u64 blkno;
1205 struct buffer_head *bh = NULL;
1206 struct ocfs2_extent_block *eb;
1207 struct ocfs2_extent_list *el;
1208 struct ocfs2_extent_rec *rec;
1209 struct ocfs2_inode_info *oi = OCFS2_I(inode);
1210
1211 el = root_el;
1212 while (el->l_tree_depth) {
1213 if (le16_to_cpu(el->l_next_free_rec) == 0) {
1214 ocfs2_error(inode->i_sb,
1215 "Inode %llu has empty extent list at "
1216 "depth %u\n",
1217 (unsigned long long)oi->ip_blkno,
1218 le16_to_cpu(el->l_tree_depth));
1219 ret = -EROFS;
1220 goto out;
1221
1222 }
1223
1224 for(i = 0; i < le16_to_cpu(el->l_next_free_rec) - 1; i++) {
1225 rec = &el->l_recs[i];
1226
1227 /*
1228 * In the case that cpos is off the allocation
1229 * tree, this should just wind up returning the
1230 * rightmost record.
1231 */
1232 range = le32_to_cpu(rec->e_cpos) +
Mark Fashehe48edee2007-03-07 16:46:57 -08001233 ocfs2_rec_clusters(el, rec);
Mark Fashehdcd05382007-01-16 11:32:23 -08001234 if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range)
1235 break;
1236 }
1237
1238 blkno = le64_to_cpu(el->l_recs[i].e_blkno);
1239 if (blkno == 0) {
1240 ocfs2_error(inode->i_sb,
1241 "Inode %llu has bad blkno in extent list "
1242 "at depth %u (index %d)\n",
1243 (unsigned long long)oi->ip_blkno,
1244 le16_to_cpu(el->l_tree_depth), i);
1245 ret = -EROFS;
1246 goto out;
1247 }
1248
1249 brelse(bh);
1250 bh = NULL;
1251 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), blkno,
1252 &bh, OCFS2_BH_CACHED, inode);
1253 if (ret) {
1254 mlog_errno(ret);
1255 goto out;
1256 }
1257
1258 eb = (struct ocfs2_extent_block *) bh->b_data;
1259 el = &eb->h_list;
1260 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
1261 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
1262 ret = -EIO;
1263 goto out;
1264 }
1265
1266 if (le16_to_cpu(el->l_next_free_rec) >
1267 le16_to_cpu(el->l_count)) {
1268 ocfs2_error(inode->i_sb,
1269 "Inode %llu has bad count in extent list "
1270 "at block %llu (next free=%u, count=%u)\n",
1271 (unsigned long long)oi->ip_blkno,
1272 (unsigned long long)bh->b_blocknr,
1273 le16_to_cpu(el->l_next_free_rec),
1274 le16_to_cpu(el->l_count));
1275 ret = -EROFS;
1276 goto out;
1277 }
1278
1279 if (func)
1280 func(data, bh);
1281 }
1282
1283out:
1284 /*
1285 * Catch any trailing bh that the loop didn't handle.
1286 */
1287 brelse(bh);
1288
1289 return ret;
1290}
1291
1292/*
1293 * Given an initialized path (that is, it has a valid root extent
1294 * list), this function will traverse the btree in search of the path
1295 * which would contain cpos.
1296 *
1297 * The path traveled is recorded in the path structure.
1298 *
1299 * Note that this will not do any comparisons on leaf node extent
1300 * records, so it will work fine in the case that we just added a tree
1301 * branch.
1302 */
1303struct find_path_data {
1304 int index;
1305 struct ocfs2_path *path;
1306};
1307static void find_path_ins(void *data, struct buffer_head *bh)
1308{
1309 struct find_path_data *fp = data;
1310
1311 get_bh(bh);
1312 ocfs2_path_insert_eb(fp->path, fp->index, bh);
1313 fp->index++;
1314}
1315static int ocfs2_find_path(struct inode *inode, struct ocfs2_path *path,
1316 u32 cpos)
1317{
1318 struct find_path_data data;
1319
1320 data.index = 1;
1321 data.path = path;
1322 return __ocfs2_find_path(inode, path_root_el(path), cpos,
1323 find_path_ins, &data);
1324}
1325
1326static void find_leaf_ins(void *data, struct buffer_head *bh)
1327{
1328 struct ocfs2_extent_block *eb =(struct ocfs2_extent_block *)bh->b_data;
1329 struct ocfs2_extent_list *el = &eb->h_list;
1330 struct buffer_head **ret = data;
1331
1332 /* We want to retain only the leaf block. */
1333 if (le16_to_cpu(el->l_tree_depth) == 0) {
1334 get_bh(bh);
1335 *ret = bh;
1336 }
1337}
1338/*
1339 * Find the leaf block in the tree which would contain cpos. No
1340 * checking of the actual leaf is done.
1341 *
1342 * Some paths want to call this instead of allocating a path structure
1343 * and calling ocfs2_find_path().
1344 *
1345 * This function doesn't handle non btree extent lists.
1346 */
Mark Fasheh363041a2007-01-17 12:31:35 -08001347int ocfs2_find_leaf(struct inode *inode, struct ocfs2_extent_list *root_el,
1348 u32 cpos, struct buffer_head **leaf_bh)
Mark Fashehdcd05382007-01-16 11:32:23 -08001349{
1350 int ret;
1351 struct buffer_head *bh = NULL;
1352
1353 ret = __ocfs2_find_path(inode, root_el, cpos, find_leaf_ins, &bh);
1354 if (ret) {
1355 mlog_errno(ret);
1356 goto out;
1357 }
1358
1359 *leaf_bh = bh;
1360out:
1361 return ret;
1362}
1363
1364/*
1365 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1366 *
1367 * Basically, we've moved stuff around at the bottom of the tree and
1368 * we need to fix up the extent records above the changes to reflect
1369 * the new changes.
1370 *
1371 * left_rec: the record on the left.
1372 * left_child_el: is the child list pointed to by left_rec
1373 * right_rec: the record to the right of left_rec
1374 * right_child_el: is the child list pointed to by right_rec
1375 *
1376 * By definition, this only works on interior nodes.
1377 */
1378static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec,
1379 struct ocfs2_extent_list *left_child_el,
1380 struct ocfs2_extent_rec *right_rec,
1381 struct ocfs2_extent_list *right_child_el)
1382{
1383 u32 left_clusters, right_end;
1384
1385 /*
1386 * Interior nodes never have holes. Their cpos is the cpos of
1387 * the leftmost record in their child list. Their cluster
1388 * count covers the full theoretical range of their child list
1389 * - the range between their cpos and the cpos of the record
1390 * immediately to their right.
1391 */
1392 left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos);
Mark Fasheh328d5752007-06-18 10:48:04 -07001393 if (ocfs2_is_empty_extent(&right_child_el->l_recs[0])) {
1394 BUG_ON(le16_to_cpu(right_child_el->l_next_free_rec) <= 1);
1395 left_clusters = le32_to_cpu(right_child_el->l_recs[1].e_cpos);
1396 }
Mark Fashehdcd05382007-01-16 11:32:23 -08001397 left_clusters -= le32_to_cpu(left_rec->e_cpos);
Mark Fashehe48edee2007-03-07 16:46:57 -08001398 left_rec->e_int_clusters = cpu_to_le32(left_clusters);
Mark Fashehdcd05382007-01-16 11:32:23 -08001399
1400 /*
1401 * Calculate the rightmost cluster count boundary before
Mark Fashehe48edee2007-03-07 16:46:57 -08001402 * moving cpos - we will need to adjust clusters after
Mark Fashehdcd05382007-01-16 11:32:23 -08001403 * updating e_cpos to keep the same highest cluster count.
1404 */
1405 right_end = le32_to_cpu(right_rec->e_cpos);
Mark Fashehe48edee2007-03-07 16:46:57 -08001406 right_end += le32_to_cpu(right_rec->e_int_clusters);
Mark Fashehdcd05382007-01-16 11:32:23 -08001407
1408 right_rec->e_cpos = left_rec->e_cpos;
1409 le32_add_cpu(&right_rec->e_cpos, left_clusters);
1410
1411 right_end -= le32_to_cpu(right_rec->e_cpos);
Mark Fashehe48edee2007-03-07 16:46:57 -08001412 right_rec->e_int_clusters = cpu_to_le32(right_end);
Mark Fashehdcd05382007-01-16 11:32:23 -08001413}
1414
1415/*
1416 * Adjust the adjacent root node records involved in a
1417 * rotation. left_el_blkno is passed in as a key so that we can easily
1418 * find it's index in the root list.
1419 */
1420static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el,
1421 struct ocfs2_extent_list *left_el,
1422 struct ocfs2_extent_list *right_el,
1423 u64 left_el_blkno)
1424{
1425 int i;
1426
1427 BUG_ON(le16_to_cpu(root_el->l_tree_depth) <=
1428 le16_to_cpu(left_el->l_tree_depth));
1429
1430 for(i = 0; i < le16_to_cpu(root_el->l_next_free_rec) - 1; i++) {
1431 if (le64_to_cpu(root_el->l_recs[i].e_blkno) == left_el_blkno)
1432 break;
1433 }
1434
1435 /*
1436 * The path walking code should have never returned a root and
1437 * two paths which are not adjacent.
1438 */
1439 BUG_ON(i >= (le16_to_cpu(root_el->l_next_free_rec) - 1));
1440
1441 ocfs2_adjust_adjacent_records(&root_el->l_recs[i], left_el,
1442 &root_el->l_recs[i + 1], right_el);
1443}
1444
1445/*
1446 * We've changed a leaf block (in right_path) and need to reflect that
1447 * change back up the subtree.
1448 *
1449 * This happens in multiple places:
1450 * - When we've moved an extent record from the left path leaf to the right
1451 * path leaf to make room for an empty extent in the left path leaf.
1452 * - When our insert into the right path leaf is at the leftmost edge
1453 * and requires an update of the path immediately to it's left. This
1454 * can occur at the end of some types of rotation and appending inserts.
1455 */
1456static void ocfs2_complete_edge_insert(struct inode *inode, handle_t *handle,
1457 struct ocfs2_path *left_path,
1458 struct ocfs2_path *right_path,
1459 int subtree_index)
1460{
1461 int ret, i, idx;
1462 struct ocfs2_extent_list *el, *left_el, *right_el;
1463 struct ocfs2_extent_rec *left_rec, *right_rec;
1464 struct buffer_head *root_bh = left_path->p_node[subtree_index].bh;
1465
1466 /*
1467 * Update the counts and position values within all the
1468 * interior nodes to reflect the leaf rotation we just did.
1469 *
1470 * The root node is handled below the loop.
1471 *
1472 * We begin the loop with right_el and left_el pointing to the
1473 * leaf lists and work our way up.
1474 *
1475 * NOTE: within this loop, left_el and right_el always refer
1476 * to the *child* lists.
1477 */
1478 left_el = path_leaf_el(left_path);
1479 right_el = path_leaf_el(right_path);
1480 for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) {
1481 mlog(0, "Adjust records at index %u\n", i);
1482
1483 /*
1484 * One nice property of knowing that all of these
1485 * nodes are below the root is that we only deal with
1486 * the leftmost right node record and the rightmost
1487 * left node record.
1488 */
1489 el = left_path->p_node[i].el;
1490 idx = le16_to_cpu(left_el->l_next_free_rec) - 1;
1491 left_rec = &el->l_recs[idx];
1492
1493 el = right_path->p_node[i].el;
1494 right_rec = &el->l_recs[0];
1495
1496 ocfs2_adjust_adjacent_records(left_rec, left_el, right_rec,
1497 right_el);
1498
1499 ret = ocfs2_journal_dirty(handle, left_path->p_node[i].bh);
1500 if (ret)
1501 mlog_errno(ret);
1502
1503 ret = ocfs2_journal_dirty(handle, right_path->p_node[i].bh);
1504 if (ret)
1505 mlog_errno(ret);
1506
1507 /*
1508 * Setup our list pointers now so that the current
1509 * parents become children in the next iteration.
1510 */
1511 left_el = left_path->p_node[i].el;
1512 right_el = right_path->p_node[i].el;
1513 }
1514
1515 /*
1516 * At the root node, adjust the two adjacent records which
1517 * begin our path to the leaves.
1518 */
1519
1520 el = left_path->p_node[subtree_index].el;
1521 left_el = left_path->p_node[subtree_index + 1].el;
1522 right_el = right_path->p_node[subtree_index + 1].el;
1523
1524 ocfs2_adjust_root_records(el, left_el, right_el,
1525 left_path->p_node[subtree_index + 1].bh->b_blocknr);
1526
1527 root_bh = left_path->p_node[subtree_index].bh;
1528
1529 ret = ocfs2_journal_dirty(handle, root_bh);
1530 if (ret)
1531 mlog_errno(ret);
1532}
1533
1534static int ocfs2_rotate_subtree_right(struct inode *inode,
1535 handle_t *handle,
1536 struct ocfs2_path *left_path,
1537 struct ocfs2_path *right_path,
1538 int subtree_index)
1539{
1540 int ret, i;
1541 struct buffer_head *right_leaf_bh;
1542 struct buffer_head *left_leaf_bh = NULL;
1543 struct buffer_head *root_bh;
1544 struct ocfs2_extent_list *right_el, *left_el;
1545 struct ocfs2_extent_rec move_rec;
1546
1547 left_leaf_bh = path_leaf_bh(left_path);
1548 left_el = path_leaf_el(left_path);
1549
1550 if (left_el->l_next_free_rec != left_el->l_count) {
1551 ocfs2_error(inode->i_sb,
1552 "Inode %llu has non-full interior leaf node %llu"
1553 "(next free = %u)",
1554 (unsigned long long)OCFS2_I(inode)->ip_blkno,
1555 (unsigned long long)left_leaf_bh->b_blocknr,
1556 le16_to_cpu(left_el->l_next_free_rec));
1557 return -EROFS;
1558 }
1559
1560 /*
1561 * This extent block may already have an empty record, so we
1562 * return early if so.
1563 */
1564 if (ocfs2_is_empty_extent(&left_el->l_recs[0]))
1565 return 0;
1566
1567 root_bh = left_path->p_node[subtree_index].bh;
1568 BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
1569
1570 ret = ocfs2_journal_access(handle, inode, root_bh,
1571 OCFS2_JOURNAL_ACCESS_WRITE);
1572 if (ret) {
1573 mlog_errno(ret);
1574 goto out;
1575 }
1576
1577 for(i = subtree_index + 1; i < path_num_items(right_path); i++) {
1578 ret = ocfs2_journal_access(handle, inode,
1579 right_path->p_node[i].bh,
1580 OCFS2_JOURNAL_ACCESS_WRITE);
1581 if (ret) {
1582 mlog_errno(ret);
1583 goto out;
1584 }
1585
1586 ret = ocfs2_journal_access(handle, inode,
1587 left_path->p_node[i].bh,
1588 OCFS2_JOURNAL_ACCESS_WRITE);
1589 if (ret) {
1590 mlog_errno(ret);
1591 goto out;
1592 }
1593 }
1594
1595 right_leaf_bh = path_leaf_bh(right_path);
1596 right_el = path_leaf_el(right_path);
1597
1598 /* This is a code error, not a disk corruption. */
1599 mlog_bug_on_msg(!right_el->l_next_free_rec, "Inode %llu: Rotate fails "
1600 "because rightmost leaf block %llu is empty\n",
1601 (unsigned long long)OCFS2_I(inode)->ip_blkno,
1602 (unsigned long long)right_leaf_bh->b_blocknr);
1603
1604 ocfs2_create_empty_extent(right_el);
1605
1606 ret = ocfs2_journal_dirty(handle, right_leaf_bh);
1607 if (ret) {
1608 mlog_errno(ret);
1609 goto out;
1610 }
1611
1612 /* Do the copy now. */
1613 i = le16_to_cpu(left_el->l_next_free_rec) - 1;
1614 move_rec = left_el->l_recs[i];
1615 right_el->l_recs[0] = move_rec;
1616
1617 /*
1618 * Clear out the record we just copied and shift everything
1619 * over, leaving an empty extent in the left leaf.
1620 *
1621 * We temporarily subtract from next_free_rec so that the
1622 * shift will lose the tail record (which is now defunct).
1623 */
1624 le16_add_cpu(&left_el->l_next_free_rec, -1);
1625 ocfs2_shift_records_right(left_el);
1626 memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1627 le16_add_cpu(&left_el->l_next_free_rec, 1);
1628
1629 ret = ocfs2_journal_dirty(handle, left_leaf_bh);
1630 if (ret) {
1631 mlog_errno(ret);
1632 goto out;
1633 }
1634
1635 ocfs2_complete_edge_insert(inode, handle, left_path, right_path,
1636 subtree_index);
1637
1638out:
1639 return ret;
1640}
1641
1642/*
1643 * Given a full path, determine what cpos value would return us a path
1644 * containing the leaf immediately to the left of the current one.
1645 *
1646 * Will return zero if the path passed in is already the leftmost path.
1647 */
1648static int ocfs2_find_cpos_for_left_leaf(struct super_block *sb,
1649 struct ocfs2_path *path, u32 *cpos)
1650{
1651 int i, j, ret = 0;
1652 u64 blkno;
1653 struct ocfs2_extent_list *el;
1654
Mark Fashehe48edee2007-03-07 16:46:57 -08001655 BUG_ON(path->p_tree_depth == 0);
1656
Mark Fashehdcd05382007-01-16 11:32:23 -08001657 *cpos = 0;
1658
1659 blkno = path_leaf_bh(path)->b_blocknr;
1660
1661 /* Start at the tree node just above the leaf and work our way up. */
1662 i = path->p_tree_depth - 1;
1663 while (i >= 0) {
1664 el = path->p_node[i].el;
1665
1666 /*
1667 * Find the extent record just before the one in our
1668 * path.
1669 */
1670 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) {
1671 if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) {
1672 if (j == 0) {
1673 if (i == 0) {
1674 /*
1675 * We've determined that the
1676 * path specified is already
1677 * the leftmost one - return a
1678 * cpos of zero.
1679 */
1680 goto out;
1681 }
1682 /*
1683 * The leftmost record points to our
1684 * leaf - we need to travel up the
1685 * tree one level.
1686 */
1687 goto next_node;
1688 }
1689
1690 *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos);
Mark Fashehe48edee2007-03-07 16:46:57 -08001691 *cpos = *cpos + ocfs2_rec_clusters(el,
1692 &el->l_recs[j - 1]);
1693 *cpos = *cpos - 1;
Mark Fashehdcd05382007-01-16 11:32:23 -08001694 goto out;
1695 }
1696 }
1697
1698 /*
1699 * If we got here, we never found a valid node where
1700 * the tree indicated one should be.
1701 */
1702 ocfs2_error(sb,
1703 "Invalid extent tree at extent block %llu\n",
1704 (unsigned long long)blkno);
1705 ret = -EROFS;
1706 goto out;
1707
1708next_node:
1709 blkno = path->p_node[i].bh->b_blocknr;
1710 i--;
1711 }
1712
1713out:
1714 return ret;
1715}
1716
Mark Fasheh328d5752007-06-18 10:48:04 -07001717/*
1718 * Extend the transaction by enough credits to complete the rotation,
1719 * and still leave at least the original number of credits allocated
1720 * to this transaction.
1721 */
Mark Fashehdcd05382007-01-16 11:32:23 -08001722static int ocfs2_extend_rotate_transaction(handle_t *handle, int subtree_depth,
Mark Fasheh328d5752007-06-18 10:48:04 -07001723 int op_credits,
Mark Fashehdcd05382007-01-16 11:32:23 -08001724 struct ocfs2_path *path)
1725{
Mark Fasheh328d5752007-06-18 10:48:04 -07001726 int credits = (path->p_tree_depth - subtree_depth) * 2 + 1 + op_credits;
Mark Fashehdcd05382007-01-16 11:32:23 -08001727
1728 if (handle->h_buffer_credits < credits)
1729 return ocfs2_extend_trans(handle, credits);
1730
1731 return 0;
1732}
1733
1734/*
1735 * Trap the case where we're inserting into the theoretical range past
1736 * the _actual_ left leaf range. Otherwise, we'll rotate a record
1737 * whose cpos is less than ours into the right leaf.
1738 *
1739 * It's only necessary to look at the rightmost record of the left
1740 * leaf because the logic that calls us should ensure that the
1741 * theoretical ranges in the path components above the leaves are
1742 * correct.
1743 */
1744static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path,
1745 u32 insert_cpos)
1746{
1747 struct ocfs2_extent_list *left_el;
1748 struct ocfs2_extent_rec *rec;
1749 int next_free;
1750
1751 left_el = path_leaf_el(left_path);
1752 next_free = le16_to_cpu(left_el->l_next_free_rec);
1753 rec = &left_el->l_recs[next_free - 1];
1754
1755 if (insert_cpos > le32_to_cpu(rec->e_cpos))
1756 return 1;
1757 return 0;
1758}
1759
Mark Fasheh328d5752007-06-18 10:48:04 -07001760static int ocfs2_leftmost_rec_contains(struct ocfs2_extent_list *el, u32 cpos)
1761{
1762 int next_free = le16_to_cpu(el->l_next_free_rec);
1763 unsigned int range;
1764 struct ocfs2_extent_rec *rec;
1765
1766 if (next_free == 0)
1767 return 0;
1768
1769 rec = &el->l_recs[0];
1770 if (ocfs2_is_empty_extent(rec)) {
1771 /* Empty list. */
1772 if (next_free == 1)
1773 return 0;
1774 rec = &el->l_recs[1];
1775 }
1776
1777 range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
1778 if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range)
1779 return 1;
1780 return 0;
1781}
1782
Mark Fashehdcd05382007-01-16 11:32:23 -08001783/*
1784 * Rotate all the records in a btree right one record, starting at insert_cpos.
1785 *
1786 * The path to the rightmost leaf should be passed in.
1787 *
1788 * The array is assumed to be large enough to hold an entire path (tree depth).
1789 *
1790 * Upon succesful return from this function:
1791 *
1792 * - The 'right_path' array will contain a path to the leaf block
1793 * whose range contains e_cpos.
1794 * - That leaf block will have a single empty extent in list index 0.
1795 * - In the case that the rotation requires a post-insert update,
1796 * *ret_left_path will contain a valid path which can be passed to
1797 * ocfs2_insert_path().
1798 */
1799static int ocfs2_rotate_tree_right(struct inode *inode,
1800 handle_t *handle,
Mark Fasheh328d5752007-06-18 10:48:04 -07001801 enum ocfs2_split_type split,
Mark Fashehdcd05382007-01-16 11:32:23 -08001802 u32 insert_cpos,
1803 struct ocfs2_path *right_path,
1804 struct ocfs2_path **ret_left_path)
1805{
Mark Fasheh328d5752007-06-18 10:48:04 -07001806 int ret, start, orig_credits = handle->h_buffer_credits;
Mark Fashehdcd05382007-01-16 11:32:23 -08001807 u32 cpos;
1808 struct ocfs2_path *left_path = NULL;
1809
1810 *ret_left_path = NULL;
1811
1812 left_path = ocfs2_new_path(path_root_bh(right_path),
1813 path_root_el(right_path));
1814 if (!left_path) {
1815 ret = -ENOMEM;
1816 mlog_errno(ret);
1817 goto out;
1818 }
1819
1820 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, &cpos);
1821 if (ret) {
1822 mlog_errno(ret);
1823 goto out;
1824 }
1825
1826 mlog(0, "Insert: %u, first left path cpos: %u\n", insert_cpos, cpos);
1827
1828 /*
1829 * What we want to do here is:
1830 *
1831 * 1) Start with the rightmost path.
1832 *
1833 * 2) Determine a path to the leaf block directly to the left
1834 * of that leaf.
1835 *
1836 * 3) Determine the 'subtree root' - the lowest level tree node
1837 * which contains a path to both leaves.
1838 *
1839 * 4) Rotate the subtree.
1840 *
1841 * 5) Find the next subtree by considering the left path to be
1842 * the new right path.
1843 *
1844 * The check at the top of this while loop also accepts
1845 * insert_cpos == cpos because cpos is only a _theoretical_
1846 * value to get us the left path - insert_cpos might very well
1847 * be filling that hole.
1848 *
1849 * Stop at a cpos of '0' because we either started at the
1850 * leftmost branch (i.e., a tree with one branch and a
1851 * rotation inside of it), or we've gone as far as we can in
1852 * rotating subtrees.
1853 */
1854 while (cpos && insert_cpos <= cpos) {
1855 mlog(0, "Rotating a tree: ins. cpos: %u, left path cpos: %u\n",
1856 insert_cpos, cpos);
1857
1858 ret = ocfs2_find_path(inode, left_path, cpos);
1859 if (ret) {
1860 mlog_errno(ret);
1861 goto out;
1862 }
1863
1864 mlog_bug_on_msg(path_leaf_bh(left_path) ==
1865 path_leaf_bh(right_path),
1866 "Inode %lu: error during insert of %u "
1867 "(left path cpos %u) results in two identical "
1868 "paths ending at %llu\n",
1869 inode->i_ino, insert_cpos, cpos,
1870 (unsigned long long)
1871 path_leaf_bh(left_path)->b_blocknr);
1872
Mark Fasheh328d5752007-06-18 10:48:04 -07001873 if (split == SPLIT_NONE &&
1874 ocfs2_rotate_requires_path_adjustment(left_path,
Mark Fashehdcd05382007-01-16 11:32:23 -08001875 insert_cpos)) {
Mark Fashehdcd05382007-01-16 11:32:23 -08001876
1877 /*
1878 * We've rotated the tree as much as we
1879 * should. The rest is up to
1880 * ocfs2_insert_path() to complete, after the
1881 * record insertion. We indicate this
1882 * situation by returning the left path.
1883 *
1884 * The reason we don't adjust the records here
1885 * before the record insert is that an error
1886 * later might break the rule where a parent
1887 * record e_cpos will reflect the actual
1888 * e_cpos of the 1st nonempty record of the
1889 * child list.
1890 */
1891 *ret_left_path = left_path;
1892 goto out_ret_path;
1893 }
1894
1895 start = ocfs2_find_subtree_root(inode, left_path, right_path);
1896
1897 mlog(0, "Subtree root at index %d (blk %llu, depth %d)\n",
1898 start,
1899 (unsigned long long) right_path->p_node[start].bh->b_blocknr,
1900 right_path->p_tree_depth);
1901
1902 ret = ocfs2_extend_rotate_transaction(handle, start,
Mark Fasheh328d5752007-06-18 10:48:04 -07001903 orig_credits, right_path);
Mark Fashehdcd05382007-01-16 11:32:23 -08001904 if (ret) {
1905 mlog_errno(ret);
1906 goto out;
1907 }
1908
1909 ret = ocfs2_rotate_subtree_right(inode, handle, left_path,
1910 right_path, start);
1911 if (ret) {
1912 mlog_errno(ret);
1913 goto out;
1914 }
1915
Mark Fasheh328d5752007-06-18 10:48:04 -07001916 if (split != SPLIT_NONE &&
1917 ocfs2_leftmost_rec_contains(path_leaf_el(right_path),
1918 insert_cpos)) {
1919 /*
1920 * A rotate moves the rightmost left leaf
1921 * record over to the leftmost right leaf
1922 * slot. If we're doing an extent split
1923 * instead of a real insert, then we have to
1924 * check that the extent to be split wasn't
1925 * just moved over. If it was, then we can
1926 * exit here, passing left_path back -
1927 * ocfs2_split_extent() is smart enough to
1928 * search both leaves.
1929 */
1930 *ret_left_path = left_path;
1931 goto out_ret_path;
1932 }
1933
Mark Fashehdcd05382007-01-16 11:32:23 -08001934 /*
1935 * There is no need to re-read the next right path
1936 * as we know that it'll be our current left
1937 * path. Optimize by copying values instead.
1938 */
1939 ocfs2_mv_path(right_path, left_path);
1940
1941 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path,
1942 &cpos);
1943 if (ret) {
1944 mlog_errno(ret);
1945 goto out;
1946 }
1947 }
1948
1949out:
1950 ocfs2_free_path(left_path);
1951
1952out_ret_path:
1953 return ret;
1954}
1955
Mark Fasheh328d5752007-06-18 10:48:04 -07001956static void ocfs2_update_edge_lengths(struct inode *inode, handle_t *handle,
1957 struct ocfs2_path *path)
1958{
1959 int i, idx;
1960 struct ocfs2_extent_rec *rec;
1961 struct ocfs2_extent_list *el;
1962 struct ocfs2_extent_block *eb;
1963 u32 range;
1964
1965 /* Path should always be rightmost. */
1966 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
1967 BUG_ON(eb->h_next_leaf_blk != 0ULL);
1968
1969 el = &eb->h_list;
1970 BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0);
1971 idx = le16_to_cpu(el->l_next_free_rec) - 1;
1972 rec = &el->l_recs[idx];
1973 range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
1974
1975 for (i = 0; i < path->p_tree_depth; i++) {
1976 el = path->p_node[i].el;
1977 idx = le16_to_cpu(el->l_next_free_rec) - 1;
1978 rec = &el->l_recs[idx];
1979
1980 rec->e_int_clusters = cpu_to_le32(range);
1981 le32_add_cpu(&rec->e_int_clusters, -le32_to_cpu(rec->e_cpos));
1982
1983 ocfs2_journal_dirty(handle, path->p_node[i].bh);
1984 }
1985}
1986
1987static void ocfs2_unlink_path(struct inode *inode, handle_t *handle,
1988 struct ocfs2_cached_dealloc_ctxt *dealloc,
1989 struct ocfs2_path *path, int unlink_start)
1990{
1991 int ret, i;
1992 struct ocfs2_extent_block *eb;
1993 struct ocfs2_extent_list *el;
1994 struct buffer_head *bh;
1995
1996 for(i = unlink_start; i < path_num_items(path); i++) {
1997 bh = path->p_node[i].bh;
1998
1999 eb = (struct ocfs2_extent_block *)bh->b_data;
2000 /*
2001 * Not all nodes might have had their final count
2002 * decremented by the caller - handle this here.
2003 */
2004 el = &eb->h_list;
2005 if (le16_to_cpu(el->l_next_free_rec) > 1) {
2006 mlog(ML_ERROR,
2007 "Inode %llu, attempted to remove extent block "
2008 "%llu with %u records\n",
2009 (unsigned long long)OCFS2_I(inode)->ip_blkno,
2010 (unsigned long long)le64_to_cpu(eb->h_blkno),
2011 le16_to_cpu(el->l_next_free_rec));
2012
2013 ocfs2_journal_dirty(handle, bh);
2014 ocfs2_remove_from_cache(inode, bh);
2015 continue;
2016 }
2017
2018 el->l_next_free_rec = 0;
2019 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2020
2021 ocfs2_journal_dirty(handle, bh);
2022
2023 ret = ocfs2_cache_extent_block_free(dealloc, eb);
2024 if (ret)
2025 mlog_errno(ret);
2026
2027 ocfs2_remove_from_cache(inode, bh);
2028 }
2029}
2030
2031static void ocfs2_unlink_subtree(struct inode *inode, handle_t *handle,
2032 struct ocfs2_path *left_path,
2033 struct ocfs2_path *right_path,
2034 int subtree_index,
2035 struct ocfs2_cached_dealloc_ctxt *dealloc)
2036{
2037 int i;
2038 struct buffer_head *root_bh = left_path->p_node[subtree_index].bh;
2039 struct ocfs2_extent_list *root_el = left_path->p_node[subtree_index].el;
2040 struct ocfs2_extent_list *el;
2041 struct ocfs2_extent_block *eb;
2042
2043 el = path_leaf_el(left_path);
2044
2045 eb = (struct ocfs2_extent_block *)right_path->p_node[subtree_index + 1].bh->b_data;
2046
2047 for(i = 1; i < le16_to_cpu(root_el->l_next_free_rec); i++)
2048 if (root_el->l_recs[i].e_blkno == eb->h_blkno)
2049 break;
2050
2051 BUG_ON(i >= le16_to_cpu(root_el->l_next_free_rec));
2052
2053 memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
2054 le16_add_cpu(&root_el->l_next_free_rec, -1);
2055
2056 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2057 eb->h_next_leaf_blk = 0;
2058
2059 ocfs2_journal_dirty(handle, root_bh);
2060 ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
2061
2062 ocfs2_unlink_path(inode, handle, dealloc, right_path,
2063 subtree_index + 1);
2064}
2065
2066static int ocfs2_rotate_subtree_left(struct inode *inode, handle_t *handle,
2067 struct ocfs2_path *left_path,
2068 struct ocfs2_path *right_path,
2069 int subtree_index,
2070 struct ocfs2_cached_dealloc_ctxt *dealloc,
2071 int *deleted)
2072{
2073 int ret, i, del_right_subtree = 0, right_has_empty = 0;
2074 struct buffer_head *root_bh, *di_bh = path_root_bh(right_path);
2075 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
2076 struct ocfs2_extent_list *right_leaf_el, *left_leaf_el;
2077 struct ocfs2_extent_block *eb;
2078
2079 *deleted = 0;
2080
2081 right_leaf_el = path_leaf_el(right_path);
2082 left_leaf_el = path_leaf_el(left_path);
2083 root_bh = left_path->p_node[subtree_index].bh;
2084 BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
2085
2086 if (!ocfs2_is_empty_extent(&left_leaf_el->l_recs[0]))
2087 return 0;
2088
2089 eb = (struct ocfs2_extent_block *)path_leaf_bh(right_path)->b_data;
2090 if (ocfs2_is_empty_extent(&right_leaf_el->l_recs[0])) {
2091 /*
2092 * It's legal for us to proceed if the right leaf is
2093 * the rightmost one and it has an empty extent. There
2094 * are two cases to handle - whether the leaf will be
2095 * empty after removal or not. If the leaf isn't empty
2096 * then just remove the empty extent up front. The
2097 * next block will handle empty leaves by flagging
2098 * them for unlink.
2099 *
2100 * Non rightmost leaves will throw -EAGAIN and the
2101 * caller can manually move the subtree and retry.
2102 */
2103
2104 if (eb->h_next_leaf_blk != 0ULL)
2105 return -EAGAIN;
2106
2107 if (le16_to_cpu(right_leaf_el->l_next_free_rec) > 1) {
2108 ret = ocfs2_journal_access(handle, inode,
2109 path_leaf_bh(right_path),
2110 OCFS2_JOURNAL_ACCESS_WRITE);
2111 if (ret) {
2112 mlog_errno(ret);
2113 goto out;
2114 }
2115
2116 ocfs2_remove_empty_extent(right_leaf_el);
2117 } else
2118 right_has_empty = 1;
2119 }
2120
2121 if (eb->h_next_leaf_blk == 0ULL &&
2122 le16_to_cpu(right_leaf_el->l_next_free_rec) == 1) {
2123 /*
2124 * We have to update i_last_eb_blk during the meta
2125 * data delete.
2126 */
2127 ret = ocfs2_journal_access(handle, inode, di_bh,
2128 OCFS2_JOURNAL_ACCESS_WRITE);
2129 if (ret) {
2130 mlog_errno(ret);
2131 goto out;
2132 }
2133
2134 del_right_subtree = 1;
2135 }
2136
2137 /*
2138 * Getting here with an empty extent in the right path implies
2139 * that it's the rightmost path and will be deleted.
2140 */
2141 BUG_ON(right_has_empty && !del_right_subtree);
2142
2143 ret = ocfs2_journal_access(handle, inode, root_bh,
2144 OCFS2_JOURNAL_ACCESS_WRITE);
2145 if (ret) {
2146 mlog_errno(ret);
2147 goto out;
2148 }
2149
2150 for(i = subtree_index + 1; i < path_num_items(right_path); i++) {
2151 ret = ocfs2_journal_access(handle, inode,
2152 right_path->p_node[i].bh,
2153 OCFS2_JOURNAL_ACCESS_WRITE);
2154 if (ret) {
2155 mlog_errno(ret);
2156 goto out;
2157 }
2158
2159 ret = ocfs2_journal_access(handle, inode,
2160 left_path->p_node[i].bh,
2161 OCFS2_JOURNAL_ACCESS_WRITE);
2162 if (ret) {
2163 mlog_errno(ret);
2164 goto out;
2165 }
2166 }
2167
2168 if (!right_has_empty) {
2169 /*
2170 * Only do this if we're moving a real
2171 * record. Otherwise, the action is delayed until
2172 * after removal of the right path in which case we
2173 * can do a simple shift to remove the empty extent.
2174 */
2175 ocfs2_rotate_leaf(left_leaf_el, &right_leaf_el->l_recs[0]);
2176 memset(&right_leaf_el->l_recs[0], 0,
2177 sizeof(struct ocfs2_extent_rec));
2178 }
2179 if (eb->h_next_leaf_blk == 0ULL) {
2180 /*
2181 * Move recs over to get rid of empty extent, decrease
2182 * next_free. This is allowed to remove the last
2183 * extent in our leaf (setting l_next_free_rec to
2184 * zero) - the delete code below won't care.
2185 */
2186 ocfs2_remove_empty_extent(right_leaf_el);
2187 }
2188
2189 ret = ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
2190 if (ret)
2191 mlog_errno(ret);
2192 ret = ocfs2_journal_dirty(handle, path_leaf_bh(right_path));
2193 if (ret)
2194 mlog_errno(ret);
2195
2196 if (del_right_subtree) {
2197 ocfs2_unlink_subtree(inode, handle, left_path, right_path,
2198 subtree_index, dealloc);
2199 ocfs2_update_edge_lengths(inode, handle, left_path);
2200
2201 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2202 di->i_last_eb_blk = eb->h_blkno;
2203
2204 /*
2205 * Removal of the extent in the left leaf was skipped
2206 * above so we could delete the right path
2207 * 1st.
2208 */
2209 if (right_has_empty)
2210 ocfs2_remove_empty_extent(left_leaf_el);
2211
2212 ret = ocfs2_journal_dirty(handle, di_bh);
2213 if (ret)
2214 mlog_errno(ret);
2215
2216 *deleted = 1;
2217 } else
2218 ocfs2_complete_edge_insert(inode, handle, left_path, right_path,
2219 subtree_index);
2220
2221out:
2222 return ret;
2223}
2224
2225/*
2226 * Given a full path, determine what cpos value would return us a path
2227 * containing the leaf immediately to the right of the current one.
2228 *
2229 * Will return zero if the path passed in is already the rightmost path.
2230 *
2231 * This looks similar, but is subtly different to
2232 * ocfs2_find_cpos_for_left_leaf().
2233 */
2234static int ocfs2_find_cpos_for_right_leaf(struct super_block *sb,
2235 struct ocfs2_path *path, u32 *cpos)
2236{
2237 int i, j, ret = 0;
2238 u64 blkno;
2239 struct ocfs2_extent_list *el;
2240
2241 *cpos = 0;
2242
2243 if (path->p_tree_depth == 0)
2244 return 0;
2245
2246 blkno = path_leaf_bh(path)->b_blocknr;
2247
2248 /* Start at the tree node just above the leaf and work our way up. */
2249 i = path->p_tree_depth - 1;
2250 while (i >= 0) {
2251 int next_free;
2252
2253 el = path->p_node[i].el;
2254
2255 /*
2256 * Find the extent record just after the one in our
2257 * path.
2258 */
2259 next_free = le16_to_cpu(el->l_next_free_rec);
2260 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) {
2261 if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) {
2262 if (j == (next_free - 1)) {
2263 if (i == 0) {
2264 /*
2265 * We've determined that the
2266 * path specified is already
2267 * the rightmost one - return a
2268 * cpos of zero.
2269 */
2270 goto out;
2271 }
2272 /*
2273 * The rightmost record points to our
2274 * leaf - we need to travel up the
2275 * tree one level.
2276 */
2277 goto next_node;
2278 }
2279
2280 *cpos = le32_to_cpu(el->l_recs[j + 1].e_cpos);
2281 goto out;
2282 }
2283 }
2284
2285 /*
2286 * If we got here, we never found a valid node where
2287 * the tree indicated one should be.
2288 */
2289 ocfs2_error(sb,
2290 "Invalid extent tree at extent block %llu\n",
2291 (unsigned long long)blkno);
2292 ret = -EROFS;
2293 goto out;
2294
2295next_node:
2296 blkno = path->p_node[i].bh->b_blocknr;
2297 i--;
2298 }
2299
2300out:
2301 return ret;
2302}
2303
2304static int ocfs2_rotate_rightmost_leaf_left(struct inode *inode,
2305 handle_t *handle,
2306 struct buffer_head *bh,
2307 struct ocfs2_extent_list *el)
2308{
2309 int ret;
2310
2311 if (!ocfs2_is_empty_extent(&el->l_recs[0]))
2312 return 0;
2313
2314 ret = ocfs2_journal_access(handle, inode, bh,
2315 OCFS2_JOURNAL_ACCESS_WRITE);
2316 if (ret) {
2317 mlog_errno(ret);
2318 goto out;
2319 }
2320
2321 ocfs2_remove_empty_extent(el);
2322
2323 ret = ocfs2_journal_dirty(handle, bh);
2324 if (ret)
2325 mlog_errno(ret);
2326
2327out:
2328 return ret;
2329}
2330
2331static int __ocfs2_rotate_tree_left(struct inode *inode,
2332 handle_t *handle, int orig_credits,
2333 struct ocfs2_path *path,
2334 struct ocfs2_cached_dealloc_ctxt *dealloc,
2335 struct ocfs2_path **empty_extent_path)
2336{
2337 int ret, subtree_root, deleted;
2338 u32 right_cpos;
2339 struct ocfs2_path *left_path = NULL;
2340 struct ocfs2_path *right_path = NULL;
2341
2342 BUG_ON(!ocfs2_is_empty_extent(&(path_leaf_el(path)->l_recs[0])));
2343
2344 *empty_extent_path = NULL;
2345
2346 ret = ocfs2_find_cpos_for_right_leaf(inode->i_sb, path,
2347 &right_cpos);
2348 if (ret) {
2349 mlog_errno(ret);
2350 goto out;
2351 }
2352
2353 left_path = ocfs2_new_path(path_root_bh(path),
2354 path_root_el(path));
2355 if (!left_path) {
2356 ret = -ENOMEM;
2357 mlog_errno(ret);
2358 goto out;
2359 }
2360
2361 ocfs2_cp_path(left_path, path);
2362
2363 right_path = ocfs2_new_path(path_root_bh(path),
2364 path_root_el(path));
2365 if (!right_path) {
2366 ret = -ENOMEM;
2367 mlog_errno(ret);
2368 goto out;
2369 }
2370
2371 while (right_cpos) {
2372 ret = ocfs2_find_path(inode, right_path, right_cpos);
2373 if (ret) {
2374 mlog_errno(ret);
2375 goto out;
2376 }
2377
2378 subtree_root = ocfs2_find_subtree_root(inode, left_path,
2379 right_path);
2380
2381 mlog(0, "Subtree root at index %d (blk %llu, depth %d)\n",
2382 subtree_root,
2383 (unsigned long long)
2384 right_path->p_node[subtree_root].bh->b_blocknr,
2385 right_path->p_tree_depth);
2386
2387 ret = ocfs2_extend_rotate_transaction(handle, subtree_root,
2388 orig_credits, left_path);
2389 if (ret) {
2390 mlog_errno(ret);
2391 goto out;
2392 }
2393
2394 ret = ocfs2_rotate_subtree_left(inode, handle, left_path,
2395 right_path, subtree_root,
2396 dealloc, &deleted);
2397 if (ret == -EAGAIN) {
2398 /*
2399 * The rotation has to temporarily stop due to
2400 * the right subtree having an empty
2401 * extent. Pass it back to the caller for a
2402 * fixup.
2403 */
2404 *empty_extent_path = right_path;
2405 right_path = NULL;
2406 goto out;
2407 }
2408 if (ret) {
2409 mlog_errno(ret);
2410 goto out;
2411 }
2412
2413 /*
2414 * The subtree rotate might have removed records on
2415 * the rightmost edge. If so, then rotation is
2416 * complete.
2417 */
2418 if (deleted)
2419 break;
2420
2421 ocfs2_mv_path(left_path, right_path);
2422
2423 ret = ocfs2_find_cpos_for_right_leaf(inode->i_sb, left_path,
2424 &right_cpos);
2425 if (ret) {
2426 mlog_errno(ret);
2427 goto out;
2428 }
2429 }
2430
2431out:
2432 ocfs2_free_path(right_path);
2433 ocfs2_free_path(left_path);
2434
2435 return ret;
2436}
2437
2438static int ocfs2_remove_rightmost_path(struct inode *inode, handle_t *handle,
2439 struct ocfs2_path *path,
2440 struct ocfs2_cached_dealloc_ctxt *dealloc)
2441{
2442 int ret, subtree_index;
2443 u32 cpos;
2444 struct ocfs2_path *left_path = NULL;
2445 struct ocfs2_dinode *di;
2446 struct ocfs2_extent_block *eb;
2447 struct ocfs2_extent_list *el;
2448
2449 /*
2450 * XXX: This code assumes that the root is an inode, which is
2451 * true for now but may change as tree code gets generic.
2452 */
2453 di = (struct ocfs2_dinode *)path_root_bh(path)->b_data;
2454 if (!OCFS2_IS_VALID_DINODE(di)) {
2455 ret = -EIO;
2456 ocfs2_error(inode->i_sb,
2457 "Inode %llu has invalid path root",
2458 (unsigned long long)OCFS2_I(inode)->ip_blkno);
2459 goto out;
2460 }
2461
2462 /*
2463 * There's two ways we handle this depending on
2464 * whether path is the only existing one.
2465 */
2466 ret = ocfs2_extend_rotate_transaction(handle, 0,
2467 handle->h_buffer_credits,
2468 path);
2469 if (ret) {
2470 mlog_errno(ret);
2471 goto out;
2472 }
2473
2474 ret = ocfs2_journal_access_path(inode, handle, path);
2475 if (ret) {
2476 mlog_errno(ret);
2477 goto out;
2478 }
2479
2480 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos);
2481 if (ret) {
2482 mlog_errno(ret);
2483 goto out;
2484 }
2485
2486 if (cpos) {
2487 /*
2488 * We have a path to the left of this one - it needs
2489 * an update too.
2490 */
2491 left_path = ocfs2_new_path(path_root_bh(path),
2492 path_root_el(path));
2493 if (!left_path) {
2494 ret = -ENOMEM;
2495 mlog_errno(ret);
2496 goto out;
2497 }
2498
2499 ret = ocfs2_find_path(inode, left_path, cpos);
2500 if (ret) {
2501 mlog_errno(ret);
2502 goto out;
2503 }
2504
2505 ret = ocfs2_journal_access_path(inode, handle, left_path);
2506 if (ret) {
2507 mlog_errno(ret);
2508 goto out;
2509 }
2510
2511 subtree_index = ocfs2_find_subtree_root(inode, left_path, path);
2512
2513 ocfs2_unlink_subtree(inode, handle, left_path, path,
2514 subtree_index, dealloc);
2515 ocfs2_update_edge_lengths(inode, handle, left_path);
2516
2517 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2518 di->i_last_eb_blk = eb->h_blkno;
2519 } else {
2520 /*
2521 * 'path' is also the leftmost path which
2522 * means it must be the only one. This gets
2523 * handled differently because we want to
2524 * revert the inode back to having extents
2525 * in-line.
2526 */
2527 ocfs2_unlink_path(inode, handle, dealloc, path, 1);
2528
2529 el = &di->id2.i_list;
2530 el->l_tree_depth = 0;
2531 el->l_next_free_rec = 0;
2532 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2533
2534 di->i_last_eb_blk = 0;
2535 }
2536
2537 ocfs2_journal_dirty(handle, path_root_bh(path));
2538
2539out:
2540 ocfs2_free_path(left_path);
2541 return ret;
2542}
2543
2544/*
2545 * Left rotation of btree records.
2546 *
2547 * In many ways, this is (unsurprisingly) the opposite of right
2548 * rotation. We start at some non-rightmost path containing an empty
2549 * extent in the leaf block. The code works its way to the rightmost
2550 * path by rotating records to the left in every subtree.
2551 *
2552 * This is used by any code which reduces the number of extent records
2553 * in a leaf. After removal, an empty record should be placed in the
2554 * leftmost list position.
2555 *
2556 * This won't handle a length update of the rightmost path records if
2557 * the rightmost tree leaf record is removed so the caller is
2558 * responsible for detecting and correcting that.
2559 */
2560static int ocfs2_rotate_tree_left(struct inode *inode, handle_t *handle,
2561 struct ocfs2_path *path,
2562 struct ocfs2_cached_dealloc_ctxt *dealloc)
2563{
2564 int ret, orig_credits = handle->h_buffer_credits;
2565 struct ocfs2_path *tmp_path = NULL, *restart_path = NULL;
2566 struct ocfs2_extent_block *eb;
2567 struct ocfs2_extent_list *el;
2568
2569 el = path_leaf_el(path);
2570 if (!ocfs2_is_empty_extent(&el->l_recs[0]))
2571 return 0;
2572
2573 if (path->p_tree_depth == 0) {
2574rightmost_no_delete:
2575 /*
2576 * In-inode extents. This is trivially handled, so do
2577 * it up front.
2578 */
2579 ret = ocfs2_rotate_rightmost_leaf_left(inode, handle,
2580 path_leaf_bh(path),
2581 path_leaf_el(path));
2582 if (ret)
2583 mlog_errno(ret);
2584 goto out;
2585 }
2586
2587 /*
2588 * Handle rightmost branch now. There's several cases:
2589 * 1) simple rotation leaving records in there. That's trivial.
2590 * 2) rotation requiring a branch delete - there's no more
2591 * records left. Two cases of this:
2592 * a) There are branches to the left.
2593 * b) This is also the leftmost (the only) branch.
2594 *
2595 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
2596 * 2a) we need the left branch so that we can update it with the unlink
2597 * 2b) we need to bring the inode back to inline extents.
2598 */
2599
2600 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
2601 el = &eb->h_list;
2602 if (eb->h_next_leaf_blk == 0) {
2603 /*
2604 * This gets a bit tricky if we're going to delete the
2605 * rightmost path. Get the other cases out of the way
2606 * 1st.
2607 */
2608 if (le16_to_cpu(el->l_next_free_rec) > 1)
2609 goto rightmost_no_delete;
2610
2611 if (le16_to_cpu(el->l_next_free_rec) == 0) {
2612 ret = -EIO;
2613 ocfs2_error(inode->i_sb,
2614 "Inode %llu has empty extent block at %llu",
2615 (unsigned long long)OCFS2_I(inode)->ip_blkno,
2616 (unsigned long long)le64_to_cpu(eb->h_blkno));
2617 goto out;
2618 }
2619
2620 /*
2621 * XXX: The caller can not trust "path" any more after
2622 * this as it will have been deleted. What do we do?
2623 *
2624 * In theory the rotate-for-merge code will never get
2625 * here because it'll always ask for a rotate in a
2626 * nonempty list.
2627 */
2628
2629 ret = ocfs2_remove_rightmost_path(inode, handle, path,
2630 dealloc);
2631 if (ret)
2632 mlog_errno(ret);
2633 goto out;
2634 }
2635
2636 /*
2637 * Now we can loop, remembering the path we get from -EAGAIN
2638 * and restarting from there.
2639 */
2640try_rotate:
2641 ret = __ocfs2_rotate_tree_left(inode, handle, orig_credits, path,
2642 dealloc, &restart_path);
2643 if (ret && ret != -EAGAIN) {
2644 mlog_errno(ret);
2645 goto out;
2646 }
2647
2648 while (ret == -EAGAIN) {
2649 tmp_path = restart_path;
2650 restart_path = NULL;
2651
2652 ret = __ocfs2_rotate_tree_left(inode, handle, orig_credits,
2653 tmp_path, dealloc,
2654 &restart_path);
2655 if (ret && ret != -EAGAIN) {
2656 mlog_errno(ret);
2657 goto out;
2658 }
2659
2660 ocfs2_free_path(tmp_path);
2661 tmp_path = NULL;
2662
2663 if (ret == 0)
2664 goto try_rotate;
2665 }
2666
2667out:
2668 ocfs2_free_path(tmp_path);
2669 ocfs2_free_path(restart_path);
2670 return ret;
2671}
2672
2673static void ocfs2_cleanup_merge(struct ocfs2_extent_list *el,
2674 int index)
2675{
2676 struct ocfs2_extent_rec *rec = &el->l_recs[index];
2677 unsigned int size;
2678
2679 if (rec->e_leaf_clusters == 0) {
2680 /*
2681 * We consumed all of the merged-from record. An empty
2682 * extent cannot exist anywhere but the 1st array
2683 * position, so move things over if the merged-from
2684 * record doesn't occupy that position.
2685 *
2686 * This creates a new empty extent so the caller
2687 * should be smart enough to have removed any existing
2688 * ones.
2689 */
2690 if (index > 0) {
2691 BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0]));
2692 size = index * sizeof(struct ocfs2_extent_rec);
2693 memmove(&el->l_recs[1], &el->l_recs[0], size);
2694 }
2695
2696 /*
2697 * Always memset - the caller doesn't check whether it
2698 * created an empty extent, so there could be junk in
2699 * the other fields.
2700 */
2701 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2702 }
2703}
2704
2705/*
2706 * Remove split_rec clusters from the record at index and merge them
2707 * onto the beginning of the record at index + 1.
2708 */
2709static int ocfs2_merge_rec_right(struct inode *inode, struct buffer_head *bh,
2710 handle_t *handle,
2711 struct ocfs2_extent_rec *split_rec,
2712 struct ocfs2_extent_list *el, int index)
2713{
2714 int ret;
2715 unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters);
2716 struct ocfs2_extent_rec *left_rec;
2717 struct ocfs2_extent_rec *right_rec;
2718
2719 BUG_ON(index >= le16_to_cpu(el->l_next_free_rec));
2720
2721 left_rec = &el->l_recs[index];
2722 right_rec = &el->l_recs[index + 1];
2723
2724 ret = ocfs2_journal_access(handle, inode, bh,
2725 OCFS2_JOURNAL_ACCESS_WRITE);
2726 if (ret) {
2727 mlog_errno(ret);
2728 goto out;
2729 }
2730
2731 le16_add_cpu(&left_rec->e_leaf_clusters, -split_clusters);
2732
2733 le32_add_cpu(&right_rec->e_cpos, -split_clusters);
2734 le64_add_cpu(&right_rec->e_blkno,
2735 -ocfs2_clusters_to_blocks(inode->i_sb, split_clusters));
2736 le16_add_cpu(&right_rec->e_leaf_clusters, split_clusters);
2737
2738 ocfs2_cleanup_merge(el, index);
2739
2740 ret = ocfs2_journal_dirty(handle, bh);
2741 if (ret)
2742 mlog_errno(ret);
2743
2744out:
2745 return ret;
2746}
2747
2748/*
2749 * Remove split_rec clusters from the record at index and merge them
2750 * onto the tail of the record at index - 1.
2751 */
2752static int ocfs2_merge_rec_left(struct inode *inode, struct buffer_head *bh,
2753 handle_t *handle,
2754 struct ocfs2_extent_rec *split_rec,
2755 struct ocfs2_extent_list *el, int index)
2756{
2757 int ret, has_empty_extent = 0;
2758 unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters);
2759 struct ocfs2_extent_rec *left_rec;
2760 struct ocfs2_extent_rec *right_rec;
2761
2762 BUG_ON(index <= 0);
2763
2764 left_rec = &el->l_recs[index - 1];
2765 right_rec = &el->l_recs[index];
2766 if (ocfs2_is_empty_extent(&el->l_recs[0]))
2767 has_empty_extent = 1;
2768
2769 ret = ocfs2_journal_access(handle, inode, bh,
2770 OCFS2_JOURNAL_ACCESS_WRITE);
2771 if (ret) {
2772 mlog_errno(ret);
2773 goto out;
2774 }
2775
2776 if (has_empty_extent && index == 1) {
2777 /*
2778 * The easy case - we can just plop the record right in.
2779 */
2780 *left_rec = *split_rec;
2781
2782 has_empty_extent = 0;
2783 } else {
2784 le16_add_cpu(&left_rec->e_leaf_clusters, split_clusters);
2785 }
2786
2787 le32_add_cpu(&right_rec->e_cpos, split_clusters);
2788 le64_add_cpu(&right_rec->e_blkno,
2789 ocfs2_clusters_to_blocks(inode->i_sb, split_clusters));
2790 le16_add_cpu(&right_rec->e_leaf_clusters, -split_clusters);
2791
2792 ocfs2_cleanup_merge(el, index);
2793
2794 ret = ocfs2_journal_dirty(handle, bh);
2795 if (ret)
2796 mlog_errno(ret);
2797
2798out:
2799 return ret;
2800}
2801
2802static int ocfs2_try_to_merge_extent(struct inode *inode,
2803 handle_t *handle,
2804 struct ocfs2_path *left_path,
2805 int split_index,
2806 struct ocfs2_extent_rec *split_rec,
2807 struct ocfs2_cached_dealloc_ctxt *dealloc,
2808 struct ocfs2_merge_ctxt *ctxt)
2809
2810{
2811 int ret = 0, delete_tail_recs = 0;
2812 struct ocfs2_extent_list *el = path_leaf_el(left_path);
2813 struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
2814
2815 BUG_ON(ctxt->c_contig_type == CONTIG_NONE);
2816
2817 if (ctxt->c_split_covers_rec) {
2818 delete_tail_recs++;
2819
2820 if (ctxt->c_contig_type == CONTIG_LEFTRIGHT ||
2821 ctxt->c_has_empty_extent)
2822 delete_tail_recs++;
2823
2824 if (ctxt->c_has_empty_extent) {
2825 /*
2826 * The merge code will need to create an empty
2827 * extent to take the place of the newly
2828 * emptied slot. Remove any pre-existing empty
2829 * extents - having more than one in a leaf is
2830 * illegal.
2831 */
2832 ret = ocfs2_rotate_tree_left(inode, handle, left_path,
2833 dealloc);
2834 if (ret) {
2835 mlog_errno(ret);
2836 goto out;
2837 }
2838 split_index--;
2839 rec = &el->l_recs[split_index];
2840 }
2841 }
2842
2843 if (ctxt->c_contig_type == CONTIG_LEFTRIGHT) {
2844 /*
2845 * Left-right contig implies this.
2846 */
2847 BUG_ON(!ctxt->c_split_covers_rec);
2848 BUG_ON(split_index == 0);
2849
2850 /*
2851 * Since the leftright insert always covers the entire
2852 * extent, this call will delete the insert record
2853 * entirely, resulting in an empty extent record added to
2854 * the extent block.
2855 *
2856 * Since the adding of an empty extent shifts
2857 * everything back to the right, there's no need to
2858 * update split_index here.
2859 */
2860 ret = ocfs2_merge_rec_left(inode, path_leaf_bh(left_path),
2861 handle, split_rec, el, split_index);
2862 if (ret) {
2863 mlog_errno(ret);
2864 goto out;
2865 }
2866
2867 /*
2868 * We can only get this from logic error above.
2869 */
2870 BUG_ON(!ocfs2_is_empty_extent(&el->l_recs[0]));
2871
2872 /*
2873 * The left merge left us with an empty extent, remove
2874 * it.
2875 */
2876 ret = ocfs2_rotate_tree_left(inode, handle, left_path, dealloc);
2877 if (ret) {
2878 mlog_errno(ret);
2879 goto out;
2880 }
2881 split_index--;
2882 rec = &el->l_recs[split_index];
2883
2884 /*
2885 * Note that we don't pass split_rec here on purpose -
2886 * we've merged it into the left side.
2887 */
2888 ret = ocfs2_merge_rec_right(inode, path_leaf_bh(left_path),
2889 handle, rec, el, split_index);
2890 if (ret) {
2891 mlog_errno(ret);
2892 goto out;
2893 }
2894
2895 BUG_ON(!ocfs2_is_empty_extent(&el->l_recs[0]));
2896
2897 ret = ocfs2_rotate_tree_left(inode, handle, left_path,
2898 dealloc);
2899 /*
2900 * Error from this last rotate is not critical, so
2901 * print but don't bubble it up.
2902 */
2903 if (ret)
2904 mlog_errno(ret);
2905 ret = 0;
2906 } else {
2907 /*
2908 * Merge a record to the left or right.
2909 *
2910 * 'contig_type' is relative to the existing record,
2911 * so for example, if we're "right contig", it's to
2912 * the record on the left (hence the left merge).
2913 */
2914 if (ctxt->c_contig_type == CONTIG_RIGHT) {
2915 ret = ocfs2_merge_rec_left(inode,
2916 path_leaf_bh(left_path),
2917 handle, split_rec, el,
2918 split_index);
2919 if (ret) {
2920 mlog_errno(ret);
2921 goto out;
2922 }
2923 } else {
2924 ret = ocfs2_merge_rec_right(inode,
2925 path_leaf_bh(left_path),
2926 handle, split_rec, el,
2927 split_index);
2928 if (ret) {
2929 mlog_errno(ret);
2930 goto out;
2931 }
2932 }
2933
2934 if (ctxt->c_split_covers_rec) {
2935 /*
2936 * The merge may have left an empty extent in
2937 * our leaf. Try to rotate it away.
2938 */
2939 ret = ocfs2_rotate_tree_left(inode, handle, left_path,
2940 dealloc);
2941 if (ret)
2942 mlog_errno(ret);
2943 ret = 0;
2944 }
2945 }
2946
2947out:
2948 return ret;
2949}
2950
2951static void ocfs2_subtract_from_rec(struct super_block *sb,
2952 enum ocfs2_split_type split,
2953 struct ocfs2_extent_rec *rec,
2954 struct ocfs2_extent_rec *split_rec)
2955{
2956 u64 len_blocks;
2957
2958 len_blocks = ocfs2_clusters_to_blocks(sb,
2959 le16_to_cpu(split_rec->e_leaf_clusters));
2960
2961 if (split == SPLIT_LEFT) {
2962 /*
2963 * Region is on the left edge of the existing
2964 * record.
2965 */
2966 le32_add_cpu(&rec->e_cpos,
2967 le16_to_cpu(split_rec->e_leaf_clusters));
2968 le64_add_cpu(&rec->e_blkno, len_blocks);
2969 le16_add_cpu(&rec->e_leaf_clusters,
2970 -le16_to_cpu(split_rec->e_leaf_clusters));
2971 } else {
2972 /*
2973 * Region is on the right edge of the existing
2974 * record.
2975 */
2976 le16_add_cpu(&rec->e_leaf_clusters,
2977 -le16_to_cpu(split_rec->e_leaf_clusters));
2978 }
2979}
2980
Mark Fashehdcd05382007-01-16 11:32:23 -08002981/*
2982 * Do the final bits of extent record insertion at the target leaf
2983 * list. If this leaf is part of an allocation tree, it is assumed
2984 * that the tree above has been prepared.
2985 */
2986static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec,
2987 struct ocfs2_extent_list *el,
2988 struct ocfs2_insert_type *insert,
2989 struct inode *inode)
2990{
2991 int i = insert->ins_contig_index;
2992 unsigned int range;
2993 struct ocfs2_extent_rec *rec;
2994
Mark Fashehe48edee2007-03-07 16:46:57 -08002995 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
Mark Fashehdcd05382007-01-16 11:32:23 -08002996
Mark Fasheh328d5752007-06-18 10:48:04 -07002997 if (insert->ins_split != SPLIT_NONE) {
2998 i = ocfs2_search_extent_list(el, le32_to_cpu(insert_rec->e_cpos));
2999 BUG_ON(i == -1);
3000 rec = &el->l_recs[i];
3001 ocfs2_subtract_from_rec(inode->i_sb, insert->ins_split, rec,
3002 insert_rec);
3003 goto rotate;
3004 }
3005
Mark Fashehdcd05382007-01-16 11:32:23 -08003006 /*
3007 * Contiguous insert - either left or right.
3008 */
3009 if (insert->ins_contig != CONTIG_NONE) {
3010 rec = &el->l_recs[i];
3011 if (insert->ins_contig == CONTIG_LEFT) {
3012 rec->e_blkno = insert_rec->e_blkno;
3013 rec->e_cpos = insert_rec->e_cpos;
3014 }
Mark Fashehe48edee2007-03-07 16:46:57 -08003015 le16_add_cpu(&rec->e_leaf_clusters,
3016 le16_to_cpu(insert_rec->e_leaf_clusters));
Mark Fashehdcd05382007-01-16 11:32:23 -08003017 return;
3018 }
3019
3020 /*
3021 * Handle insert into an empty leaf.
3022 */
3023 if (le16_to_cpu(el->l_next_free_rec) == 0 ||
3024 ((le16_to_cpu(el->l_next_free_rec) == 1) &&
3025 ocfs2_is_empty_extent(&el->l_recs[0]))) {
3026 el->l_recs[0] = *insert_rec;
3027 el->l_next_free_rec = cpu_to_le16(1);
3028 return;
3029 }
3030
3031 /*
3032 * Appending insert.
3033 */
3034 if (insert->ins_appending == APPEND_TAIL) {
3035 i = le16_to_cpu(el->l_next_free_rec) - 1;
3036 rec = &el->l_recs[i];
Mark Fashehe48edee2007-03-07 16:46:57 -08003037 range = le32_to_cpu(rec->e_cpos)
3038 + le16_to_cpu(rec->e_leaf_clusters);
Mark Fashehdcd05382007-01-16 11:32:23 -08003039 BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range);
3040
3041 mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >=
3042 le16_to_cpu(el->l_count),
3043 "inode %lu, depth %u, count %u, next free %u, "
3044 "rec.cpos %u, rec.clusters %u, "
3045 "insert.cpos %u, insert.clusters %u\n",
3046 inode->i_ino,
3047 le16_to_cpu(el->l_tree_depth),
3048 le16_to_cpu(el->l_count),
3049 le16_to_cpu(el->l_next_free_rec),
3050 le32_to_cpu(el->l_recs[i].e_cpos),
Mark Fashehe48edee2007-03-07 16:46:57 -08003051 le16_to_cpu(el->l_recs[i].e_leaf_clusters),
Mark Fashehdcd05382007-01-16 11:32:23 -08003052 le32_to_cpu(insert_rec->e_cpos),
Mark Fashehe48edee2007-03-07 16:46:57 -08003053 le16_to_cpu(insert_rec->e_leaf_clusters));
Mark Fashehdcd05382007-01-16 11:32:23 -08003054 i++;
3055 el->l_recs[i] = *insert_rec;
3056 le16_add_cpu(&el->l_next_free_rec, 1);
3057 return;
3058 }
3059
Mark Fasheh328d5752007-06-18 10:48:04 -07003060rotate:
Mark Fashehdcd05382007-01-16 11:32:23 -08003061 /*
3062 * Ok, we have to rotate.
3063 *
3064 * At this point, it is safe to assume that inserting into an
3065 * empty leaf and appending to a leaf have both been handled
3066 * above.
3067 *
3068 * This leaf needs to have space, either by the empty 1st
3069 * extent record, or by virtue of an l_next_rec < l_count.
3070 */
3071 ocfs2_rotate_leaf(el, insert_rec);
3072}
3073
3074static inline void ocfs2_update_dinode_clusters(struct inode *inode,
3075 struct ocfs2_dinode *di,
3076 u32 clusters)
3077{
3078 le32_add_cpu(&di->i_clusters, clusters);
3079 spin_lock(&OCFS2_I(inode)->ip_lock);
3080 OCFS2_I(inode)->ip_clusters = le32_to_cpu(di->i_clusters);
3081 spin_unlock(&OCFS2_I(inode)->ip_lock);
3082}
3083
Mark Fasheh328d5752007-06-18 10:48:04 -07003084static void ocfs2_adjust_rightmost_records(struct inode *inode,
3085 handle_t *handle,
3086 struct ocfs2_path *path,
3087 struct ocfs2_extent_rec *insert_rec)
3088{
3089 int ret, i, next_free;
3090 struct buffer_head *bh;
3091 struct ocfs2_extent_list *el;
3092 struct ocfs2_extent_rec *rec;
3093
3094 /*
3095 * Update everything except the leaf block.
3096 */
3097 for (i = 0; i < path->p_tree_depth; i++) {
3098 bh = path->p_node[i].bh;
3099 el = path->p_node[i].el;
3100
3101 next_free = le16_to_cpu(el->l_next_free_rec);
3102 if (next_free == 0) {
3103 ocfs2_error(inode->i_sb,
3104 "Dinode %llu has a bad extent list",
3105 (unsigned long long)OCFS2_I(inode)->ip_blkno);
3106 ret = -EIO;
3107 return;
3108 }
3109
3110 rec = &el->l_recs[next_free - 1];
3111
3112 rec->e_int_clusters = insert_rec->e_cpos;
3113 le32_add_cpu(&rec->e_int_clusters,
3114 le16_to_cpu(insert_rec->e_leaf_clusters));
3115 le32_add_cpu(&rec->e_int_clusters,
3116 -le32_to_cpu(rec->e_cpos));
3117
3118 ret = ocfs2_journal_dirty(handle, bh);
3119 if (ret)
3120 mlog_errno(ret);
3121
3122 }
3123}
3124
Mark Fashehdcd05382007-01-16 11:32:23 -08003125static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle,
3126 struct ocfs2_extent_rec *insert_rec,
3127 struct ocfs2_path *right_path,
3128 struct ocfs2_path **ret_left_path)
3129{
Mark Fasheh328d5752007-06-18 10:48:04 -07003130 int ret, next_free;
Mark Fashehdcd05382007-01-16 11:32:23 -08003131 struct ocfs2_extent_list *el;
3132 struct ocfs2_path *left_path = NULL;
3133
3134 *ret_left_path = NULL;
3135
3136 /*
Mark Fashehe48edee2007-03-07 16:46:57 -08003137 * This shouldn't happen for non-trees. The extent rec cluster
3138 * count manipulation below only works for interior nodes.
3139 */
3140 BUG_ON(right_path->p_tree_depth == 0);
3141
3142 /*
Mark Fashehdcd05382007-01-16 11:32:23 -08003143 * If our appending insert is at the leftmost edge of a leaf,
3144 * then we might need to update the rightmost records of the
3145 * neighboring path.
3146 */
3147 el = path_leaf_el(right_path);
3148 next_free = le16_to_cpu(el->l_next_free_rec);
3149 if (next_free == 0 ||
3150 (next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) {
3151 u32 left_cpos;
3152
3153 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path,
3154 &left_cpos);
3155 if (ret) {
3156 mlog_errno(ret);
3157 goto out;
3158 }
3159
3160 mlog(0, "Append may need a left path update. cpos: %u, "
3161 "left_cpos: %u\n", le32_to_cpu(insert_rec->e_cpos),
3162 left_cpos);
3163
3164 /*
3165 * No need to worry if the append is already in the
3166 * leftmost leaf.
3167 */
3168 if (left_cpos) {
3169 left_path = ocfs2_new_path(path_root_bh(right_path),
3170 path_root_el(right_path));
3171 if (!left_path) {
3172 ret = -ENOMEM;
3173 mlog_errno(ret);
3174 goto out;
3175 }
3176
3177 ret = ocfs2_find_path(inode, left_path, left_cpos);
3178 if (ret) {
3179 mlog_errno(ret);
3180 goto out;
3181 }
3182
3183 /*
3184 * ocfs2_insert_path() will pass the left_path to the
3185 * journal for us.
3186 */
3187 }
3188 }
3189
3190 ret = ocfs2_journal_access_path(inode, handle, right_path);
3191 if (ret) {
3192 mlog_errno(ret);
3193 goto out;
3194 }
3195
Mark Fasheh328d5752007-06-18 10:48:04 -07003196 ocfs2_adjust_rightmost_records(inode, handle, right_path, insert_rec);
Mark Fashehdcd05382007-01-16 11:32:23 -08003197
3198 *ret_left_path = left_path;
3199 ret = 0;
3200out:
3201 if (ret != 0)
3202 ocfs2_free_path(left_path);
3203
3204 return ret;
3205}
3206
Mark Fasheh328d5752007-06-18 10:48:04 -07003207static void ocfs2_split_record(struct inode *inode,
3208 struct ocfs2_path *left_path,
3209 struct ocfs2_path *right_path,
3210 struct ocfs2_extent_rec *split_rec,
3211 enum ocfs2_split_type split)
3212{
3213 int index;
3214 u32 cpos = le32_to_cpu(split_rec->e_cpos);
3215 struct ocfs2_extent_list *left_el = NULL, *right_el, *insert_el, *el;
3216 struct ocfs2_extent_rec *rec, *tmprec;
3217
3218 right_el = path_leaf_el(right_path);;
3219 if (left_path)
3220 left_el = path_leaf_el(left_path);
3221
3222 el = right_el;
3223 insert_el = right_el;
3224 index = ocfs2_search_extent_list(el, cpos);
3225 if (index != -1) {
3226 if (index == 0 && left_path) {
3227 BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0]));
3228
3229 /*
3230 * This typically means that the record
3231 * started in the left path but moved to the
3232 * right as a result of rotation. We either
3233 * move the existing record to the left, or we
3234 * do the later insert there.
3235 *
3236 * In this case, the left path should always
3237 * exist as the rotate code will have passed
3238 * it back for a post-insert update.
3239 */
3240
3241 if (split == SPLIT_LEFT) {
3242 /*
3243 * It's a left split. Since we know
3244 * that the rotate code gave us an
3245 * empty extent in the left path, we
3246 * can just do the insert there.
3247 */
3248 insert_el = left_el;
3249 } else {
3250 /*
3251 * Right split - we have to move the
3252 * existing record over to the left
3253 * leaf. The insert will be into the
3254 * newly created empty extent in the
3255 * right leaf.
3256 */
3257 tmprec = &right_el->l_recs[index];
3258 ocfs2_rotate_leaf(left_el, tmprec);
3259 el = left_el;
3260
3261 memset(tmprec, 0, sizeof(*tmprec));
3262 index = ocfs2_search_extent_list(left_el, cpos);
3263 BUG_ON(index == -1);
3264 }
3265 }
3266 } else {
3267 BUG_ON(!left_path);
3268 BUG_ON(!ocfs2_is_empty_extent(&left_el->l_recs[0]));
3269 /*
3270 * Left path is easy - we can just allow the insert to
3271 * happen.
3272 */
3273 el = left_el;
3274 insert_el = left_el;
3275 index = ocfs2_search_extent_list(el, cpos);
3276 BUG_ON(index == -1);
3277 }
3278
3279 rec = &el->l_recs[index];
3280 ocfs2_subtract_from_rec(inode->i_sb, split, rec, split_rec);
3281 ocfs2_rotate_leaf(insert_el, split_rec);
3282}
3283
Mark Fashehdcd05382007-01-16 11:32:23 -08003284/*
3285 * This function only does inserts on an allocation b-tree. For dinode
3286 * lists, ocfs2_insert_at_leaf() is called directly.
3287 *
3288 * right_path is the path we want to do the actual insert
3289 * in. left_path should only be passed in if we need to update that
3290 * portion of the tree after an edge insert.
3291 */
3292static int ocfs2_insert_path(struct inode *inode,
3293 handle_t *handle,
3294 struct ocfs2_path *left_path,
3295 struct ocfs2_path *right_path,
3296 struct ocfs2_extent_rec *insert_rec,
3297 struct ocfs2_insert_type *insert)
3298{
3299 int ret, subtree_index;
3300 struct buffer_head *leaf_bh = path_leaf_bh(right_path);
Mark Fashehdcd05382007-01-16 11:32:23 -08003301
3302 /*
3303 * Pass both paths to the journal. The majority of inserts
3304 * will be touching all components anyway.
3305 */
3306 ret = ocfs2_journal_access_path(inode, handle, right_path);
3307 if (ret < 0) {
3308 mlog_errno(ret);
3309 goto out;
3310 }
3311
3312 if (left_path) {
3313 int credits = handle->h_buffer_credits;
3314
3315 /*
3316 * There's a chance that left_path got passed back to
3317 * us without being accounted for in the
3318 * journal. Extend our transaction here to be sure we
3319 * can change those blocks.
3320 */
3321 credits += left_path->p_tree_depth;
3322
3323 ret = ocfs2_extend_trans(handle, credits);
3324 if (ret < 0) {
3325 mlog_errno(ret);
3326 goto out;
3327 }
3328
3329 ret = ocfs2_journal_access_path(inode, handle, left_path);
3330 if (ret < 0) {
3331 mlog_errno(ret);
3332 goto out;
3333 }
3334 }
3335
Mark Fasheh328d5752007-06-18 10:48:04 -07003336 if (insert->ins_split != SPLIT_NONE) {
3337 /*
3338 * We could call ocfs2_insert_at_leaf() for some types
3339 * of splits, but it's easier to just let one seperate
3340 * function sort it all out.
3341 */
3342 ocfs2_split_record(inode, left_path, right_path,
3343 insert_rec, insert->ins_split);
3344 } else
3345 ocfs2_insert_at_leaf(insert_rec, path_leaf_el(right_path),
3346 insert, inode);
Mark Fashehdcd05382007-01-16 11:32:23 -08003347
Mark Fashehdcd05382007-01-16 11:32:23 -08003348 ret = ocfs2_journal_dirty(handle, leaf_bh);
3349 if (ret)
3350 mlog_errno(ret);
3351
3352 if (left_path) {
3353 /*
3354 * The rotate code has indicated that we need to fix
3355 * up portions of the tree after the insert.
3356 *
3357 * XXX: Should we extend the transaction here?
3358 */
3359 subtree_index = ocfs2_find_subtree_root(inode, left_path,
3360 right_path);
3361 ocfs2_complete_edge_insert(inode, handle, left_path,
3362 right_path, subtree_index);
3363 }
3364
3365 ret = 0;
3366out:
3367 return ret;
3368}
3369
3370static int ocfs2_do_insert_extent(struct inode *inode,
3371 handle_t *handle,
3372 struct buffer_head *di_bh,
3373 struct ocfs2_extent_rec *insert_rec,
3374 struct ocfs2_insert_type *type)
3375{
3376 int ret, rotate = 0;
3377 u32 cpos;
3378 struct ocfs2_path *right_path = NULL;
3379 struct ocfs2_path *left_path = NULL;
3380 struct ocfs2_dinode *di;
3381 struct ocfs2_extent_list *el;
3382
3383 di = (struct ocfs2_dinode *) di_bh->b_data;
3384 el = &di->id2.i_list;
3385
3386 ret = ocfs2_journal_access(handle, inode, di_bh,
3387 OCFS2_JOURNAL_ACCESS_WRITE);
3388 if (ret) {
3389 mlog_errno(ret);
3390 goto out;
3391 }
3392
3393 if (le16_to_cpu(el->l_tree_depth) == 0) {
3394 ocfs2_insert_at_leaf(insert_rec, el, type, inode);
3395 goto out_update_clusters;
3396 }
3397
3398 right_path = ocfs2_new_inode_path(di_bh);
3399 if (!right_path) {
3400 ret = -ENOMEM;
3401 mlog_errno(ret);
3402 goto out;
3403 }
3404
3405 /*
3406 * Determine the path to start with. Rotations need the
3407 * rightmost path, everything else can go directly to the
3408 * target leaf.
3409 */
3410 cpos = le32_to_cpu(insert_rec->e_cpos);
3411 if (type->ins_appending == APPEND_NONE &&
3412 type->ins_contig == CONTIG_NONE) {
3413 rotate = 1;
3414 cpos = UINT_MAX;
3415 }
3416
3417 ret = ocfs2_find_path(inode, right_path, cpos);
3418 if (ret) {
3419 mlog_errno(ret);
3420 goto out;
3421 }
3422
3423 /*
3424 * Rotations and appends need special treatment - they modify
3425 * parts of the tree's above them.
3426 *
3427 * Both might pass back a path immediate to the left of the
3428 * one being inserted to. This will be cause
3429 * ocfs2_insert_path() to modify the rightmost records of
3430 * left_path to account for an edge insert.
3431 *
3432 * XXX: When modifying this code, keep in mind that an insert
3433 * can wind up skipping both of these two special cases...
3434 */
3435 if (rotate) {
Mark Fasheh328d5752007-06-18 10:48:04 -07003436 ret = ocfs2_rotate_tree_right(inode, handle, type->ins_split,
Mark Fashehdcd05382007-01-16 11:32:23 -08003437 le32_to_cpu(insert_rec->e_cpos),
3438 right_path, &left_path);
3439 if (ret) {
3440 mlog_errno(ret);
3441 goto out;
3442 }
3443 } else if (type->ins_appending == APPEND_TAIL
3444 && type->ins_contig != CONTIG_LEFT) {
3445 ret = ocfs2_append_rec_to_path(inode, handle, insert_rec,
3446 right_path, &left_path);
3447 if (ret) {
3448 mlog_errno(ret);
3449 goto out;
3450 }
3451 }
3452
3453 ret = ocfs2_insert_path(inode, handle, left_path, right_path,
3454 insert_rec, type);
3455 if (ret) {
3456 mlog_errno(ret);
3457 goto out;
3458 }
3459
3460out_update_clusters:
Mark Fasheh328d5752007-06-18 10:48:04 -07003461 if (type->ins_split == SPLIT_NONE)
3462 ocfs2_update_dinode_clusters(inode, di,
3463 le16_to_cpu(insert_rec->e_leaf_clusters));
Mark Fashehdcd05382007-01-16 11:32:23 -08003464
3465 ret = ocfs2_journal_dirty(handle, di_bh);
3466 if (ret)
3467 mlog_errno(ret);
3468
3469out:
3470 ocfs2_free_path(left_path);
3471 ocfs2_free_path(right_path);
3472
3473 return ret;
3474}
3475
Mark Fasheh328d5752007-06-18 10:48:04 -07003476static enum ocfs2_contig_type
3477ocfs2_figure_merge_contig_type(struct inode *inode,
3478 struct ocfs2_extent_list *el, int index,
3479 struct ocfs2_extent_rec *split_rec)
3480{
3481 struct ocfs2_extent_rec *rec;
3482 enum ocfs2_contig_type ret = CONTIG_NONE;
3483
3484 /*
3485 * We're careful to check for an empty extent record here -
3486 * the merge code will know what to do if it sees one.
3487 */
3488
3489 if (index > 0) {
3490 rec = &el->l_recs[index - 1];
3491 if (index == 1 && ocfs2_is_empty_extent(rec)) {
3492 if (split_rec->e_cpos == el->l_recs[index].e_cpos)
3493 ret = CONTIG_RIGHT;
3494 } else {
3495 ret = ocfs2_extent_contig(inode, rec, split_rec);
3496 }
3497 }
3498
3499 if (index < (le16_to_cpu(el->l_next_free_rec) - 1)) {
3500 enum ocfs2_contig_type contig_type;
3501
3502 rec = &el->l_recs[index + 1];
3503 contig_type = ocfs2_extent_contig(inode, rec, split_rec);
3504
3505 if (contig_type == CONTIG_LEFT && ret == CONTIG_RIGHT)
3506 ret = CONTIG_LEFTRIGHT;
3507 else if (ret == CONTIG_NONE)
3508 ret = contig_type;
3509 }
3510
3511 return ret;
3512}
3513
Mark Fashehdcd05382007-01-16 11:32:23 -08003514static void ocfs2_figure_contig_type(struct inode *inode,
3515 struct ocfs2_insert_type *insert,
3516 struct ocfs2_extent_list *el,
3517 struct ocfs2_extent_rec *insert_rec)
3518{
3519 int i;
3520 enum ocfs2_contig_type contig_type = CONTIG_NONE;
3521
Mark Fashehe48edee2007-03-07 16:46:57 -08003522 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
3523
Mark Fashehdcd05382007-01-16 11:32:23 -08003524 for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) {
3525 contig_type = ocfs2_extent_contig(inode, &el->l_recs[i],
3526 insert_rec);
3527 if (contig_type != CONTIG_NONE) {
3528 insert->ins_contig_index = i;
3529 break;
3530 }
3531 }
3532 insert->ins_contig = contig_type;
3533}
3534
3535/*
3536 * This should only be called against the righmost leaf extent list.
3537 *
3538 * ocfs2_figure_appending_type() will figure out whether we'll have to
3539 * insert at the tail of the rightmost leaf.
3540 *
3541 * This should also work against the dinode list for tree's with 0
3542 * depth. If we consider the dinode list to be the rightmost leaf node
3543 * then the logic here makes sense.
3544 */
3545static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert,
3546 struct ocfs2_extent_list *el,
3547 struct ocfs2_extent_rec *insert_rec)
3548{
3549 int i;
3550 u32 cpos = le32_to_cpu(insert_rec->e_cpos);
3551 struct ocfs2_extent_rec *rec;
3552
3553 insert->ins_appending = APPEND_NONE;
3554
Mark Fashehe48edee2007-03-07 16:46:57 -08003555 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
Mark Fashehdcd05382007-01-16 11:32:23 -08003556
3557 if (!el->l_next_free_rec)
3558 goto set_tail_append;
3559
3560 if (ocfs2_is_empty_extent(&el->l_recs[0])) {
3561 /* Were all records empty? */
3562 if (le16_to_cpu(el->l_next_free_rec) == 1)
3563 goto set_tail_append;
3564 }
3565
3566 i = le16_to_cpu(el->l_next_free_rec) - 1;
3567 rec = &el->l_recs[i];
3568
Mark Fashehe48edee2007-03-07 16:46:57 -08003569 if (cpos >=
3570 (le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)))
Mark Fashehdcd05382007-01-16 11:32:23 -08003571 goto set_tail_append;
3572
3573 return;
3574
3575set_tail_append:
3576 insert->ins_appending = APPEND_TAIL;
3577}
3578
3579/*
3580 * Helper function called at the begining of an insert.
3581 *
3582 * This computes a few things that are commonly used in the process of
3583 * inserting into the btree:
3584 * - Whether the new extent is contiguous with an existing one.
3585 * - The current tree depth.
3586 * - Whether the insert is an appending one.
3587 * - The total # of free records in the tree.
3588 *
3589 * All of the information is stored on the ocfs2_insert_type
3590 * structure.
3591 */
3592static int ocfs2_figure_insert_type(struct inode *inode,
3593 struct buffer_head *di_bh,
3594 struct buffer_head **last_eb_bh,
3595 struct ocfs2_extent_rec *insert_rec,
3596 struct ocfs2_insert_type *insert)
3597{
3598 int ret;
3599 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
3600 struct ocfs2_extent_block *eb;
3601 struct ocfs2_extent_list *el;
3602 struct ocfs2_path *path = NULL;
3603 struct buffer_head *bh = NULL;
3604
Mark Fasheh328d5752007-06-18 10:48:04 -07003605 insert->ins_split = SPLIT_NONE;
3606
Mark Fashehdcd05382007-01-16 11:32:23 -08003607 el = &di->id2.i_list;
3608 insert->ins_tree_depth = le16_to_cpu(el->l_tree_depth);
3609
3610 if (el->l_tree_depth) {
3611 /*
3612 * If we have tree depth, we read in the
3613 * rightmost extent block ahead of time as
3614 * ocfs2_figure_insert_type() and ocfs2_add_branch()
3615 * may want it later.
3616 */
3617 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
3618 le64_to_cpu(di->i_last_eb_blk), &bh,
3619 OCFS2_BH_CACHED, inode);
3620 if (ret) {
3621 mlog_exit(ret);
3622 goto out;
3623 }
3624 eb = (struct ocfs2_extent_block *) bh->b_data;
3625 el = &eb->h_list;
3626 }
3627
3628 /*
3629 * Unless we have a contiguous insert, we'll need to know if
3630 * there is room left in our allocation tree for another
3631 * extent record.
3632 *
3633 * XXX: This test is simplistic, we can search for empty
3634 * extent records too.
3635 */
3636 insert->ins_free_records = le16_to_cpu(el->l_count) -
3637 le16_to_cpu(el->l_next_free_rec);
3638
3639 if (!insert->ins_tree_depth) {
3640 ocfs2_figure_contig_type(inode, insert, el, insert_rec);
3641 ocfs2_figure_appending_type(insert, el, insert_rec);
3642 return 0;
3643 }
3644
3645 path = ocfs2_new_inode_path(di_bh);
3646 if (!path) {
3647 ret = -ENOMEM;
3648 mlog_errno(ret);
3649 goto out;
3650 }
3651
3652 /*
3653 * In the case that we're inserting past what the tree
3654 * currently accounts for, ocfs2_find_path() will return for
3655 * us the rightmost tree path. This is accounted for below in
3656 * the appending code.
3657 */
3658 ret = ocfs2_find_path(inode, path, le32_to_cpu(insert_rec->e_cpos));
3659 if (ret) {
3660 mlog_errno(ret);
3661 goto out;
3662 }
3663
3664 el = path_leaf_el(path);
3665
3666 /*
3667 * Now that we have the path, there's two things we want to determine:
3668 * 1) Contiguousness (also set contig_index if this is so)
3669 *
3670 * 2) Are we doing an append? We can trivially break this up
3671 * into two types of appends: simple record append, or a
3672 * rotate inside the tail leaf.
3673 */
3674 ocfs2_figure_contig_type(inode, insert, el, insert_rec);
3675
3676 /*
3677 * The insert code isn't quite ready to deal with all cases of
3678 * left contiguousness. Specifically, if it's an insert into
3679 * the 1st record in a leaf, it will require the adjustment of
Mark Fashehe48edee2007-03-07 16:46:57 -08003680 * cluster count on the last record of the path directly to it's
Mark Fashehdcd05382007-01-16 11:32:23 -08003681 * left. For now, just catch that case and fool the layers
3682 * above us. This works just fine for tree_depth == 0, which
3683 * is why we allow that above.
3684 */
3685 if (insert->ins_contig == CONTIG_LEFT &&
3686 insert->ins_contig_index == 0)
3687 insert->ins_contig = CONTIG_NONE;
3688
3689 /*
3690 * Ok, so we can simply compare against last_eb to figure out
3691 * whether the path doesn't exist. This will only happen in
3692 * the case that we're doing a tail append, so maybe we can
3693 * take advantage of that information somehow.
3694 */
3695 if (le64_to_cpu(di->i_last_eb_blk) == path_leaf_bh(path)->b_blocknr) {
3696 /*
3697 * Ok, ocfs2_find_path() returned us the rightmost
3698 * tree path. This might be an appending insert. There are
3699 * two cases:
3700 * 1) We're doing a true append at the tail:
3701 * -This might even be off the end of the leaf
3702 * 2) We're "appending" by rotating in the tail
3703 */
3704 ocfs2_figure_appending_type(insert, el, insert_rec);
3705 }
3706
3707out:
3708 ocfs2_free_path(path);
3709
3710 if (ret == 0)
3711 *last_eb_bh = bh;
3712 else
3713 brelse(bh);
3714 return ret;
3715}
3716
3717/*
3718 * Insert an extent into an inode btree.
3719 *
3720 * The caller needs to update fe->i_clusters
3721 */
Mark Fashehccd979b2005-12-15 14:31:24 -08003722int ocfs2_insert_extent(struct ocfs2_super *osb,
Mark Fasheh1fabe142006-10-09 18:11:45 -07003723 handle_t *handle,
Mark Fashehccd979b2005-12-15 14:31:24 -08003724 struct inode *inode,
3725 struct buffer_head *fe_bh,
Mark Fashehdcd05382007-01-16 11:32:23 -08003726 u32 cpos,
Mark Fashehccd979b2005-12-15 14:31:24 -08003727 u64 start_blk,
3728 u32 new_clusters,
Mark Fasheh2ae99a62007-03-09 16:43:28 -08003729 u8 flags,
Mark Fashehccd979b2005-12-15 14:31:24 -08003730 struct ocfs2_alloc_context *meta_ac)
3731{
Mark Fashehc3afcbb2007-05-29 14:28:51 -07003732 int status;
Mark Fashehccd979b2005-12-15 14:31:24 -08003733 struct buffer_head *last_eb_bh = NULL;
3734 struct buffer_head *bh = NULL;
Mark Fashehdcd05382007-01-16 11:32:23 -08003735 struct ocfs2_insert_type insert = {0, };
3736 struct ocfs2_extent_rec rec;
Mark Fashehccd979b2005-12-15 14:31:24 -08003737
Mark Fashehdcd05382007-01-16 11:32:23 -08003738 mlog(0, "add %u clusters at position %u to inode %llu\n",
3739 new_clusters, cpos, (unsigned long long)OCFS2_I(inode)->ip_blkno);
Mark Fashehccd979b2005-12-15 14:31:24 -08003740
Mark Fashehdcd05382007-01-16 11:32:23 -08003741 mlog_bug_on_msg(!ocfs2_sparse_alloc(osb) &&
3742 (OCFS2_I(inode)->ip_clusters != cpos),
3743 "Device %s, asking for sparse allocation: inode %llu, "
3744 "cpos %u, clusters %u\n",
3745 osb->dev_str,
3746 (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos,
3747 OCFS2_I(inode)->ip_clusters);
Mark Fashehccd979b2005-12-15 14:31:24 -08003748
Mark Fashehe48edee2007-03-07 16:46:57 -08003749 memset(&rec, 0, sizeof(rec));
Mark Fashehdcd05382007-01-16 11:32:23 -08003750 rec.e_cpos = cpu_to_le32(cpos);
3751 rec.e_blkno = cpu_to_le64(start_blk);
Mark Fashehe48edee2007-03-07 16:46:57 -08003752 rec.e_leaf_clusters = cpu_to_le16(new_clusters);
Mark Fasheh2ae99a62007-03-09 16:43:28 -08003753 rec.e_flags = flags;
Mark Fashehccd979b2005-12-15 14:31:24 -08003754
Mark Fashehdcd05382007-01-16 11:32:23 -08003755 status = ocfs2_figure_insert_type(inode, fe_bh, &last_eb_bh, &rec,
3756 &insert);
3757 if (status < 0) {
3758 mlog_errno(status);
3759 goto bail;
Mark Fashehccd979b2005-12-15 14:31:24 -08003760 }
3761
Mark Fashehdcd05382007-01-16 11:32:23 -08003762 mlog(0, "Insert.appending: %u, Insert.Contig: %u, "
3763 "Insert.contig_index: %d, Insert.free_records: %d, "
3764 "Insert.tree_depth: %d\n",
3765 insert.ins_appending, insert.ins_contig, insert.ins_contig_index,
3766 insert.ins_free_records, insert.ins_tree_depth);
Mark Fashehccd979b2005-12-15 14:31:24 -08003767
Mark Fashehc3afcbb2007-05-29 14:28:51 -07003768 if (insert.ins_contig == CONTIG_NONE && insert.ins_free_records == 0) {
3769 status = ocfs2_grow_tree(inode, handle, fe_bh,
Mark Fasheh328d5752007-06-18 10:48:04 -07003770 &insert.ins_tree_depth, &last_eb_bh,
Mark Fashehc3afcbb2007-05-29 14:28:51 -07003771 meta_ac);
3772 if (status) {
Mark Fashehccd979b2005-12-15 14:31:24 -08003773 mlog_errno(status);
3774 goto bail;
3775 }
Mark Fashehccd979b2005-12-15 14:31:24 -08003776 }
3777
Mark Fashehdcd05382007-01-16 11:32:23 -08003778 /* Finally, we can add clusters. This might rotate the tree for us. */
3779 status = ocfs2_do_insert_extent(inode, handle, fe_bh, &rec, &insert);
Mark Fashehccd979b2005-12-15 14:31:24 -08003780 if (status < 0)
3781 mlog_errno(status);
Mark Fasheh83418972007-04-23 18:53:12 -07003782 else
3783 ocfs2_extent_map_insert_rec(inode, &rec);
Mark Fashehccd979b2005-12-15 14:31:24 -08003784
3785bail:
3786 if (bh)
3787 brelse(bh);
3788
3789 if (last_eb_bh)
3790 brelse(last_eb_bh);
3791
3792 mlog_exit(status);
3793 return status;
3794}
3795
Mark Fasheh328d5752007-06-18 10:48:04 -07003796static void ocfs2_make_right_split_rec(struct super_block *sb,
3797 struct ocfs2_extent_rec *split_rec,
3798 u32 cpos,
3799 struct ocfs2_extent_rec *rec)
3800{
3801 u32 rec_cpos = le32_to_cpu(rec->e_cpos);
3802 u32 rec_range = rec_cpos + le16_to_cpu(rec->e_leaf_clusters);
3803
3804 memset(split_rec, 0, sizeof(struct ocfs2_extent_rec));
3805
3806 split_rec->e_cpos = cpu_to_le32(cpos);
3807 split_rec->e_leaf_clusters = cpu_to_le16(rec_range - cpos);
3808
3809 split_rec->e_blkno = rec->e_blkno;
3810 le64_add_cpu(&split_rec->e_blkno,
3811 ocfs2_clusters_to_blocks(sb, cpos - rec_cpos));
3812
3813 split_rec->e_flags = rec->e_flags;
3814}
3815
3816static int ocfs2_split_and_insert(struct inode *inode,
3817 handle_t *handle,
3818 struct ocfs2_path *path,
3819 struct buffer_head *di_bh,
3820 struct buffer_head **last_eb_bh,
3821 int split_index,
3822 struct ocfs2_extent_rec *orig_split_rec,
3823 struct ocfs2_alloc_context *meta_ac)
3824{
3825 int ret = 0, depth;
3826 unsigned int insert_range, rec_range, do_leftright = 0;
3827 struct ocfs2_extent_rec tmprec;
3828 struct ocfs2_extent_list *rightmost_el;
3829 struct ocfs2_extent_rec rec;
3830 struct ocfs2_extent_rec split_rec = *orig_split_rec;
3831 struct ocfs2_insert_type insert;
3832 struct ocfs2_extent_block *eb;
3833 struct ocfs2_dinode *di;
3834
3835leftright:
3836 /*
3837 * Store a copy of the record on the stack - it might move
3838 * around as the tree is manipulated below.
3839 */
3840 rec = path_leaf_el(path)->l_recs[split_index];
3841
3842 di = (struct ocfs2_dinode *)di_bh->b_data;
3843 rightmost_el = &di->id2.i_list;
3844
3845 depth = le16_to_cpu(rightmost_el->l_tree_depth);
3846 if (depth) {
3847 BUG_ON(!(*last_eb_bh));
3848 eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data;
3849 rightmost_el = &eb->h_list;
3850 }
3851
3852 if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
3853 le16_to_cpu(rightmost_el->l_count)) {
3854 int old_depth = depth;
3855
3856 ret = ocfs2_grow_tree(inode, handle, di_bh, &depth, last_eb_bh,
3857 meta_ac);
3858 if (ret) {
3859 mlog_errno(ret);
3860 goto out;
3861 }
3862
3863 if (old_depth != depth) {
3864 eb = (struct ocfs2_extent_block *)(*last_eb_bh)->b_data;
3865 rightmost_el = &eb->h_list;
3866 }
3867 }
3868
3869 memset(&insert, 0, sizeof(struct ocfs2_insert_type));
3870 insert.ins_appending = APPEND_NONE;
3871 insert.ins_contig = CONTIG_NONE;
3872 insert.ins_free_records = le16_to_cpu(rightmost_el->l_count)
3873 - le16_to_cpu(rightmost_el->l_next_free_rec);
3874 insert.ins_tree_depth = depth;
3875
3876 insert_range = le32_to_cpu(split_rec.e_cpos) +
3877 le16_to_cpu(split_rec.e_leaf_clusters);
3878 rec_range = le32_to_cpu(rec.e_cpos) +
3879 le16_to_cpu(rec.e_leaf_clusters);
3880
3881 if (split_rec.e_cpos == rec.e_cpos) {
3882 insert.ins_split = SPLIT_LEFT;
3883 } else if (insert_range == rec_range) {
3884 insert.ins_split = SPLIT_RIGHT;
3885 } else {
3886 /*
3887 * Left/right split. We fake this as a right split
3888 * first and then make a second pass as a left split.
3889 */
3890 insert.ins_split = SPLIT_RIGHT;
3891
3892 ocfs2_make_right_split_rec(inode->i_sb, &tmprec, insert_range,
3893 &rec);
3894
3895 split_rec = tmprec;
3896
3897 BUG_ON(do_leftright);
3898 do_leftright = 1;
3899 }
3900
3901 ret = ocfs2_do_insert_extent(inode, handle, di_bh, &split_rec,
3902 &insert);
3903 if (ret) {
3904 mlog_errno(ret);
3905 goto out;
3906 }
3907
3908 if (do_leftright == 1) {
3909 u32 cpos;
3910 struct ocfs2_extent_list *el;
3911
3912 do_leftright++;
3913 split_rec = *orig_split_rec;
3914
3915 ocfs2_reinit_path(path, 1);
3916
3917 cpos = le32_to_cpu(split_rec.e_cpos);
3918 ret = ocfs2_find_path(inode, path, cpos);
3919 if (ret) {
3920 mlog_errno(ret);
3921 goto out;
3922 }
3923
3924 el = path_leaf_el(path);
3925 split_index = ocfs2_search_extent_list(el, cpos);
3926 goto leftright;
3927 }
3928out:
3929
3930 return ret;
3931}
3932
3933/*
3934 * Mark part or all of the extent record at split_index in the leaf
3935 * pointed to by path as written. This removes the unwritten
3936 * extent flag.
3937 *
3938 * Care is taken to handle contiguousness so as to not grow the tree.
3939 *
3940 * meta_ac is not strictly necessary - we only truly need it if growth
3941 * of the tree is required. All other cases will degrade into a less
3942 * optimal tree layout.
3943 *
3944 * last_eb_bh should be the rightmost leaf block for any inode with a
3945 * btree. Since a split may grow the tree or a merge might shrink it, the caller cannot trust the contents of that buffer after this call.
3946 *
3947 * This code is optimized for readability - several passes might be
3948 * made over certain portions of the tree. All of those blocks will
3949 * have been brought into cache (and pinned via the journal), so the
3950 * extra overhead is not expressed in terms of disk reads.
3951 */
3952static int __ocfs2_mark_extent_written(struct inode *inode,
3953 struct buffer_head *di_bh,
3954 handle_t *handle,
3955 struct ocfs2_path *path,
3956 int split_index,
3957 struct ocfs2_extent_rec *split_rec,
3958 struct ocfs2_alloc_context *meta_ac,
3959 struct ocfs2_cached_dealloc_ctxt *dealloc)
3960{
3961 int ret = 0;
3962 struct ocfs2_extent_list *el = path_leaf_el(path);
3963 struct buffer_head *eb_bh, *last_eb_bh = NULL;
3964 struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
3965 struct ocfs2_merge_ctxt ctxt;
3966 struct ocfs2_extent_list *rightmost_el;
3967
3968 if (!rec->e_flags & OCFS2_EXT_UNWRITTEN) {
3969 ret = -EIO;
3970 mlog_errno(ret);
3971 goto out;
3972 }
3973
3974 if (le32_to_cpu(rec->e_cpos) > le32_to_cpu(split_rec->e_cpos) ||
3975 ((le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)) <
3976 (le32_to_cpu(split_rec->e_cpos) + le16_to_cpu(split_rec->e_leaf_clusters)))) {
3977 ret = -EIO;
3978 mlog_errno(ret);
3979 goto out;
3980 }
3981
3982 eb_bh = path_leaf_bh(path);
3983 ret = ocfs2_journal_access(handle, inode, eb_bh,
3984 OCFS2_JOURNAL_ACCESS_WRITE);
3985 if (ret) {
3986 mlog_errno(ret);
3987 goto out;
3988 }
3989
3990 ctxt.c_contig_type = ocfs2_figure_merge_contig_type(inode, el,
3991 split_index,
3992 split_rec);
3993
3994 /*
3995 * The core merge / split code wants to know how much room is
3996 * left in this inodes allocation tree, so we pass the
3997 * rightmost extent list.
3998 */
3999 if (path->p_tree_depth) {
4000 struct ocfs2_extent_block *eb;
4001 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4002
4003 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
4004 le64_to_cpu(di->i_last_eb_blk),
4005 &last_eb_bh, OCFS2_BH_CACHED, inode);
4006 if (ret) {
4007 mlog_exit(ret);
4008 goto out;
4009 }
4010
4011 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
4012 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
4013 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
4014 ret = -EROFS;
4015 goto out;
4016 }
4017
4018 rightmost_el = &eb->h_list;
4019 } else
4020 rightmost_el = path_root_el(path);
4021
4022 ctxt.c_used_tail_recs = le16_to_cpu(rightmost_el->l_next_free_rec);
4023 if (ctxt.c_used_tail_recs > 0 &&
4024 ocfs2_is_empty_extent(&rightmost_el->l_recs[0]))
4025 ctxt.c_used_tail_recs--;
4026
4027 if (rec->e_cpos == split_rec->e_cpos &&
4028 rec->e_leaf_clusters == split_rec->e_leaf_clusters)
4029 ctxt.c_split_covers_rec = 1;
4030 else
4031 ctxt.c_split_covers_rec = 0;
4032
4033 ctxt.c_has_empty_extent = ocfs2_is_empty_extent(&el->l_recs[0]);
4034
4035 mlog(0, "index: %d, contig: %u, used_tail_recs: %u, "
4036 "has_empty: %u, split_covers: %u\n", split_index,
4037 ctxt.c_contig_type, ctxt.c_used_tail_recs,
4038 ctxt.c_has_empty_extent, ctxt.c_split_covers_rec);
4039
4040 if (ctxt.c_contig_type == CONTIG_NONE) {
4041 if (ctxt.c_split_covers_rec)
4042 el->l_recs[split_index] = *split_rec;
4043 else
4044 ret = ocfs2_split_and_insert(inode, handle, path, di_bh,
4045 &last_eb_bh, split_index,
4046 split_rec, meta_ac);
4047 if (ret)
4048 mlog_errno(ret);
4049 } else {
4050 ret = ocfs2_try_to_merge_extent(inode, handle, path,
4051 split_index, split_rec,
4052 dealloc, &ctxt);
4053 if (ret)
4054 mlog_errno(ret);
4055 }
4056
4057 ocfs2_journal_dirty(handle, eb_bh);
4058
4059out:
4060 brelse(last_eb_bh);
4061 return ret;
4062}
4063
4064/*
4065 * Mark the already-existing extent at cpos as written for len clusters.
4066 *
4067 * If the existing extent is larger than the request, initiate a
4068 * split. An attempt will be made at merging with adjacent extents.
4069 *
4070 * The caller is responsible for passing down meta_ac if we'll need it.
4071 */
4072int ocfs2_mark_extent_written(struct inode *inode, struct buffer_head *di_bh,
4073 handle_t *handle, u32 cpos, u32 len, u32 phys,
4074 struct ocfs2_alloc_context *meta_ac,
4075 struct ocfs2_cached_dealloc_ctxt *dealloc)
4076{
4077 int ret, index;
4078 u64 start_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys);
4079 struct ocfs2_extent_rec split_rec;
4080 struct ocfs2_path *left_path = NULL;
4081 struct ocfs2_extent_list *el;
4082
4083 mlog(0, "Inode %lu cpos %u, len %u, phys %u (%llu)\n",
4084 inode->i_ino, cpos, len, phys, (unsigned long long)start_blkno);
4085
4086 if (!ocfs2_writes_unwritten_extents(OCFS2_SB(inode->i_sb))) {
4087 ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents "
4088 "that are being written to, but the feature bit "
4089 "is not set in the super block.",
4090 (unsigned long long)OCFS2_I(inode)->ip_blkno);
4091 ret = -EROFS;
4092 goto out;
4093 }
4094
4095 /*
4096 * XXX: This should be fixed up so that we just re-insert the
4097 * next extent records.
4098 */
4099 ocfs2_extent_map_trunc(inode, 0);
4100
4101 left_path = ocfs2_new_inode_path(di_bh);
4102 if (!left_path) {
4103 ret = -ENOMEM;
4104 mlog_errno(ret);
4105 goto out;
4106 }
4107
4108 ret = ocfs2_find_path(inode, left_path, cpos);
4109 if (ret) {
4110 mlog_errno(ret);
4111 goto out;
4112 }
4113 el = path_leaf_el(left_path);
4114
4115 index = ocfs2_search_extent_list(el, cpos);
4116 if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4117 ocfs2_error(inode->i_sb,
4118 "Inode %llu has an extent at cpos %u which can no "
4119 "longer be found.\n",
4120 (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos);
4121 ret = -EROFS;
4122 goto out;
4123 }
4124
4125 memset(&split_rec, 0, sizeof(struct ocfs2_extent_rec));
4126 split_rec.e_cpos = cpu_to_le32(cpos);
4127 split_rec.e_leaf_clusters = cpu_to_le16(len);
4128 split_rec.e_blkno = cpu_to_le64(start_blkno);
4129 split_rec.e_flags = path_leaf_el(left_path)->l_recs[index].e_flags;
4130 split_rec.e_flags &= ~OCFS2_EXT_UNWRITTEN;
4131
4132 ret = __ocfs2_mark_extent_written(inode, di_bh, handle, left_path,
4133 index, &split_rec, meta_ac, dealloc);
4134 if (ret)
4135 mlog_errno(ret);
4136
4137out:
4138 ocfs2_free_path(left_path);
4139 return ret;
4140}
4141
Mark Fashehd0c7d702007-07-03 13:27:22 -07004142static int ocfs2_split_tree(struct inode *inode, struct buffer_head *di_bh,
4143 handle_t *handle, struct ocfs2_path *path,
4144 int index, u32 new_range,
4145 struct ocfs2_alloc_context *meta_ac)
4146{
4147 int ret, depth, credits = handle->h_buffer_credits;
4148 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4149 struct buffer_head *last_eb_bh = NULL;
4150 struct ocfs2_extent_block *eb;
4151 struct ocfs2_extent_list *rightmost_el, *el;
4152 struct ocfs2_extent_rec split_rec;
4153 struct ocfs2_extent_rec *rec;
4154 struct ocfs2_insert_type insert;
4155
4156 /*
4157 * Setup the record to split before we grow the tree.
4158 */
4159 el = path_leaf_el(path);
4160 rec = &el->l_recs[index];
4161 ocfs2_make_right_split_rec(inode->i_sb, &split_rec, new_range, rec);
4162
4163 depth = path->p_tree_depth;
4164 if (depth > 0) {
4165 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
4166 le64_to_cpu(di->i_last_eb_blk),
4167 &last_eb_bh, OCFS2_BH_CACHED, inode);
4168 if (ret < 0) {
4169 mlog_errno(ret);
4170 goto out;
4171 }
4172
4173 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
4174 rightmost_el = &eb->h_list;
4175 } else
4176 rightmost_el = path_leaf_el(path);
4177
4178 credits += path->p_tree_depth + ocfs2_extend_meta_needed(di);
4179 ret = ocfs2_extend_trans(handle, credits);
4180 if (ret) {
4181 mlog_errno(ret);
4182 goto out;
4183 }
4184
4185 if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
4186 le16_to_cpu(rightmost_el->l_count)) {
4187 int old_depth = depth;
4188
4189 ret = ocfs2_grow_tree(inode, handle, di_bh, &depth, &last_eb_bh,
4190 meta_ac);
4191 if (ret) {
4192 mlog_errno(ret);
4193 goto out;
4194 }
4195
4196 if (old_depth != depth) {
4197 eb = (struct ocfs2_extent_block *)last_eb_bh->b_data;
4198 rightmost_el = &eb->h_list;
4199 }
4200 }
4201
4202 memset(&insert, 0, sizeof(struct ocfs2_insert_type));
4203 insert.ins_appending = APPEND_NONE;
4204 insert.ins_contig = CONTIG_NONE;
4205 insert.ins_split = SPLIT_RIGHT;
4206 insert.ins_free_records = le16_to_cpu(rightmost_el->l_count)
4207 - le16_to_cpu(rightmost_el->l_next_free_rec);
4208 insert.ins_tree_depth = depth;
4209
4210 ret = ocfs2_do_insert_extent(inode, handle, di_bh, &split_rec, &insert);
4211 if (ret)
4212 mlog_errno(ret);
4213
4214out:
4215 brelse(last_eb_bh);
4216 return ret;
4217}
4218
4219static int ocfs2_truncate_rec(struct inode *inode, handle_t *handle,
4220 struct ocfs2_path *path, int index,
4221 struct ocfs2_cached_dealloc_ctxt *dealloc,
4222 u32 cpos, u32 len)
4223{
4224 int ret;
4225 u32 left_cpos, rec_range, trunc_range;
4226 int wants_rotate = 0, is_rightmost_tree_rec = 0;
4227 struct super_block *sb = inode->i_sb;
4228 struct ocfs2_path *left_path = NULL;
4229 struct ocfs2_extent_list *el = path_leaf_el(path);
4230 struct ocfs2_extent_rec *rec;
4231 struct ocfs2_extent_block *eb;
4232
4233 if (ocfs2_is_empty_extent(&el->l_recs[0]) && index > 0) {
4234 ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc);
4235 if (ret) {
4236 mlog_errno(ret);
4237 goto out;
4238 }
4239
4240 index--;
4241 }
4242
4243 if (index == (le16_to_cpu(el->l_next_free_rec) - 1) &&
4244 path->p_tree_depth) {
4245 /*
4246 * Check whether this is the rightmost tree record. If
4247 * we remove all of this record or part of its right
4248 * edge then an update of the record lengths above it
4249 * will be required.
4250 */
4251 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
4252 if (eb->h_next_leaf_blk == 0)
4253 is_rightmost_tree_rec = 1;
4254 }
4255
4256 rec = &el->l_recs[index];
4257 if (index == 0 && path->p_tree_depth &&
4258 le32_to_cpu(rec->e_cpos) == cpos) {
4259 /*
4260 * Changing the leftmost offset (via partial or whole
4261 * record truncate) of an interior (or rightmost) path
4262 * means we have to update the subtree that is formed
4263 * by this leaf and the one to it's left.
4264 *
4265 * There are two cases we can skip:
4266 * 1) Path is the leftmost one in our inode tree.
4267 * 2) The leaf is rightmost and will be empty after
4268 * we remove the extent record - the rotate code
4269 * knows how to update the newly formed edge.
4270 */
4271
4272 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path,
4273 &left_cpos);
4274 if (ret) {
4275 mlog_errno(ret);
4276 goto out;
4277 }
4278
4279 if (left_cpos && le16_to_cpu(el->l_next_free_rec) > 1) {
4280 left_path = ocfs2_new_path(path_root_bh(path),
4281 path_root_el(path));
4282 if (!left_path) {
4283 ret = -ENOMEM;
4284 mlog_errno(ret);
4285 goto out;
4286 }
4287
4288 ret = ocfs2_find_path(inode, left_path, left_cpos);
4289 if (ret) {
4290 mlog_errno(ret);
4291 goto out;
4292 }
4293 }
4294 }
4295
4296 ret = ocfs2_extend_rotate_transaction(handle, 0,
4297 handle->h_buffer_credits,
4298 path);
4299 if (ret) {
4300 mlog_errno(ret);
4301 goto out;
4302 }
4303
4304 ret = ocfs2_journal_access_path(inode, handle, path);
4305 if (ret) {
4306 mlog_errno(ret);
4307 goto out;
4308 }
4309
4310 ret = ocfs2_journal_access_path(inode, handle, left_path);
4311 if (ret) {
4312 mlog_errno(ret);
4313 goto out;
4314 }
4315
4316 rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
4317 trunc_range = cpos + len;
4318
4319 if (le32_to_cpu(rec->e_cpos) == cpos && rec_range == trunc_range) {
4320 int next_free;
4321
4322 memset(rec, 0, sizeof(*rec));
4323 ocfs2_cleanup_merge(el, index);
4324 wants_rotate = 1;
4325
4326 next_free = le16_to_cpu(el->l_next_free_rec);
4327 if (is_rightmost_tree_rec && next_free > 1) {
4328 /*
4329 * We skip the edge update if this path will
4330 * be deleted by the rotate code.
4331 */
4332 rec = &el->l_recs[next_free - 1];
4333 ocfs2_adjust_rightmost_records(inode, handle, path,
4334 rec);
4335 }
4336 } else if (le32_to_cpu(rec->e_cpos) == cpos) {
4337 /* Remove leftmost portion of the record. */
4338 le32_add_cpu(&rec->e_cpos, len);
4339 le64_add_cpu(&rec->e_blkno, ocfs2_clusters_to_blocks(sb, len));
4340 le16_add_cpu(&rec->e_leaf_clusters, -len);
4341 } else if (rec_range == trunc_range) {
4342 /* Remove rightmost portion of the record */
4343 le16_add_cpu(&rec->e_leaf_clusters, -len);
4344 if (is_rightmost_tree_rec)
4345 ocfs2_adjust_rightmost_records(inode, handle, path, rec);
4346 } else {
4347 /* Caller should have trapped this. */
4348 mlog(ML_ERROR, "Inode %llu: Invalid record truncate: (%u, %u) "
4349 "(%u, %u)\n", (unsigned long long)OCFS2_I(inode)->ip_blkno,
4350 le32_to_cpu(rec->e_cpos),
4351 le16_to_cpu(rec->e_leaf_clusters), cpos, len);
4352 BUG();
4353 }
4354
4355 if (left_path) {
4356 int subtree_index;
4357
4358 subtree_index = ocfs2_find_subtree_root(inode, left_path, path);
4359 ocfs2_complete_edge_insert(inode, handle, left_path, path,
4360 subtree_index);
4361 }
4362
4363 ocfs2_journal_dirty(handle, path_leaf_bh(path));
4364
4365 ret = ocfs2_rotate_tree_left(inode, handle, path, dealloc);
4366 if (ret) {
4367 mlog_errno(ret);
4368 goto out;
4369 }
4370
4371out:
4372 ocfs2_free_path(left_path);
4373 return ret;
4374}
4375
4376static int ocfs2_remove_extent(struct inode *inode, struct buffer_head *di_bh,
4377 u32 cpos, u32 len, handle_t *handle,
4378 struct ocfs2_alloc_context *meta_ac,
4379 struct ocfs2_cached_dealloc_ctxt *dealloc)
4380{
4381 int ret, index;
4382 u32 rec_range, trunc_range;
4383 struct ocfs2_extent_rec *rec;
4384 struct ocfs2_extent_list *el;
4385 struct ocfs2_path *path;
4386
4387 ocfs2_extent_map_trunc(inode, 0);
4388
4389 path = ocfs2_new_inode_path(di_bh);
4390 if (!path) {
4391 ret = -ENOMEM;
4392 mlog_errno(ret);
4393 goto out;
4394 }
4395
4396 ret = ocfs2_find_path(inode, path, cpos);
4397 if (ret) {
4398 mlog_errno(ret);
4399 goto out;
4400 }
4401
4402 el = path_leaf_el(path);
4403 index = ocfs2_search_extent_list(el, cpos);
4404 if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4405 ocfs2_error(inode->i_sb,
4406 "Inode %llu has an extent at cpos %u which can no "
4407 "longer be found.\n",
4408 (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos);
4409 ret = -EROFS;
4410 goto out;
4411 }
4412
4413 /*
4414 * We have 3 cases of extent removal:
4415 * 1) Range covers the entire extent rec
4416 * 2) Range begins or ends on one edge of the extent rec
4417 * 3) Range is in the middle of the extent rec (no shared edges)
4418 *
4419 * For case 1 we remove the extent rec and left rotate to
4420 * fill the hole.
4421 *
4422 * For case 2 we just shrink the existing extent rec, with a
4423 * tree update if the shrinking edge is also the edge of an
4424 * extent block.
4425 *
4426 * For case 3 we do a right split to turn the extent rec into
4427 * something case 2 can handle.
4428 */
4429 rec = &el->l_recs[index];
4430 rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
4431 trunc_range = cpos + len;
4432
4433 BUG_ON(cpos < le32_to_cpu(rec->e_cpos) || trunc_range > rec_range);
4434
4435 mlog(0, "Inode %llu, remove (cpos %u, len %u). Existing index %d "
4436 "(cpos %u, len %u)\n",
4437 (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos, len, index,
4438 le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec));
4439
4440 if (le32_to_cpu(rec->e_cpos) == cpos || rec_range == trunc_range) {
4441 ret = ocfs2_truncate_rec(inode, handle, path, index, dealloc,
4442 cpos, len);
4443 if (ret) {
4444 mlog_errno(ret);
4445 goto out;
4446 }
4447 } else {
4448 ret = ocfs2_split_tree(inode, di_bh, handle, path, index,
4449 trunc_range, meta_ac);
4450 if (ret) {
4451 mlog_errno(ret);
4452 goto out;
4453 }
4454
4455 /*
4456 * The split could have manipulated the tree enough to
4457 * move the record location, so we have to look for it again.
4458 */
4459 ocfs2_reinit_path(path, 1);
4460
4461 ret = ocfs2_find_path(inode, path, cpos);
4462 if (ret) {
4463 mlog_errno(ret);
4464 goto out;
4465 }
4466
4467 el = path_leaf_el(path);
4468 index = ocfs2_search_extent_list(el, cpos);
4469 if (index == -1 || index >= le16_to_cpu(el->l_next_free_rec)) {
4470 ocfs2_error(inode->i_sb,
4471 "Inode %llu: split at cpos %u lost record.",
4472 (unsigned long long)OCFS2_I(inode)->ip_blkno,
4473 cpos);
4474 ret = -EROFS;
4475 goto out;
4476 }
4477
4478 /*
4479 * Double check our values here. If anything is fishy,
4480 * it's easier to catch it at the top level.
4481 */
4482 rec = &el->l_recs[index];
4483 rec_range = le32_to_cpu(rec->e_cpos) +
4484 ocfs2_rec_clusters(el, rec);
4485 if (rec_range != trunc_range) {
4486 ocfs2_error(inode->i_sb,
4487 "Inode %llu: error after split at cpos %u"
4488 "trunc len %u, existing record is (%u,%u)",
4489 (unsigned long long)OCFS2_I(inode)->ip_blkno,
4490 cpos, len, le32_to_cpu(rec->e_cpos),
4491 ocfs2_rec_clusters(el, rec));
4492 ret = -EROFS;
4493 goto out;
4494 }
4495
4496 ret = ocfs2_truncate_rec(inode, handle, path, index, dealloc,
4497 cpos, len);
4498 if (ret) {
4499 mlog_errno(ret);
4500 goto out;
4501 }
4502 }
4503
4504out:
4505 ocfs2_free_path(path);
4506 return ret;
4507}
4508
Mark Fashehccd979b2005-12-15 14:31:24 -08004509static inline int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb)
4510{
4511 struct buffer_head *tl_bh = osb->osb_tl_bh;
4512 struct ocfs2_dinode *di;
4513 struct ocfs2_truncate_log *tl;
4514
4515 di = (struct ocfs2_dinode *) tl_bh->b_data;
4516 tl = &di->id2.i_dealloc;
4517
4518 mlog_bug_on_msg(le16_to_cpu(tl->tl_used) > le16_to_cpu(tl->tl_count),
4519 "slot %d, invalid truncate log parameters: used = "
4520 "%u, count = %u\n", osb->slot_num,
4521 le16_to_cpu(tl->tl_used), le16_to_cpu(tl->tl_count));
4522 return le16_to_cpu(tl->tl_used) == le16_to_cpu(tl->tl_count);
4523}
4524
4525static int ocfs2_truncate_log_can_coalesce(struct ocfs2_truncate_log *tl,
4526 unsigned int new_start)
4527{
4528 unsigned int tail_index;
4529 unsigned int current_tail;
4530
4531 /* No records, nothing to coalesce */
4532 if (!le16_to_cpu(tl->tl_used))
4533 return 0;
4534
4535 tail_index = le16_to_cpu(tl->tl_used) - 1;
4536 current_tail = le32_to_cpu(tl->tl_recs[tail_index].t_start);
4537 current_tail += le32_to_cpu(tl->tl_recs[tail_index].t_clusters);
4538
4539 return current_tail == new_start;
4540}
4541
4542static int ocfs2_truncate_log_append(struct ocfs2_super *osb,
Mark Fasheh1fabe142006-10-09 18:11:45 -07004543 handle_t *handle,
Mark Fashehccd979b2005-12-15 14:31:24 -08004544 u64 start_blk,
4545 unsigned int num_clusters)
4546{
4547 int status, index;
4548 unsigned int start_cluster, tl_count;
4549 struct inode *tl_inode = osb->osb_tl_inode;
4550 struct buffer_head *tl_bh = osb->osb_tl_bh;
4551 struct ocfs2_dinode *di;
4552 struct ocfs2_truncate_log *tl;
4553
Mark Fashehb06970532006-03-03 10:24:33 -08004554 mlog_entry("start_blk = %llu, num_clusters = %u\n",
4555 (unsigned long long)start_blk, num_clusters);
Mark Fashehccd979b2005-12-15 14:31:24 -08004556
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004557 BUG_ON(mutex_trylock(&tl_inode->i_mutex));
Mark Fashehccd979b2005-12-15 14:31:24 -08004558
4559 start_cluster = ocfs2_blocks_to_clusters(osb->sb, start_blk);
4560
4561 di = (struct ocfs2_dinode *) tl_bh->b_data;
4562 tl = &di->id2.i_dealloc;
4563 if (!OCFS2_IS_VALID_DINODE(di)) {
4564 OCFS2_RO_ON_INVALID_DINODE(osb->sb, di);
4565 status = -EIO;
4566 goto bail;
4567 }
4568
4569 tl_count = le16_to_cpu(tl->tl_count);
4570 mlog_bug_on_msg(tl_count > ocfs2_truncate_recs_per_inode(osb->sb) ||
4571 tl_count == 0,
Mark Fashehb06970532006-03-03 10:24:33 -08004572 "Truncate record count on #%llu invalid "
4573 "wanted %u, actual %u\n",
4574 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno,
Mark Fashehccd979b2005-12-15 14:31:24 -08004575 ocfs2_truncate_recs_per_inode(osb->sb),
4576 le16_to_cpu(tl->tl_count));
4577
4578 /* Caller should have known to flush before calling us. */
4579 index = le16_to_cpu(tl->tl_used);
4580 if (index >= tl_count) {
4581 status = -ENOSPC;
4582 mlog_errno(status);
4583 goto bail;
4584 }
4585
4586 status = ocfs2_journal_access(handle, tl_inode, tl_bh,
4587 OCFS2_JOURNAL_ACCESS_WRITE);
4588 if (status < 0) {
4589 mlog_errno(status);
4590 goto bail;
4591 }
4592
4593 mlog(0, "Log truncate of %u clusters starting at cluster %u to "
Mark Fashehb06970532006-03-03 10:24:33 -08004594 "%llu (index = %d)\n", num_clusters, start_cluster,
4595 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, index);
Mark Fashehccd979b2005-12-15 14:31:24 -08004596
4597 if (ocfs2_truncate_log_can_coalesce(tl, start_cluster)) {
4598 /*
4599 * Move index back to the record we are coalescing with.
4600 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
4601 */
4602 index--;
4603
4604 num_clusters += le32_to_cpu(tl->tl_recs[index].t_clusters);
4605 mlog(0, "Coalesce with index %u (start = %u, clusters = %u)\n",
4606 index, le32_to_cpu(tl->tl_recs[index].t_start),
4607 num_clusters);
4608 } else {
4609 tl->tl_recs[index].t_start = cpu_to_le32(start_cluster);
4610 tl->tl_used = cpu_to_le16(index + 1);
4611 }
4612 tl->tl_recs[index].t_clusters = cpu_to_le32(num_clusters);
4613
4614 status = ocfs2_journal_dirty(handle, tl_bh);
4615 if (status < 0) {
4616 mlog_errno(status);
4617 goto bail;
4618 }
4619
4620bail:
4621 mlog_exit(status);
4622 return status;
4623}
4624
4625static int ocfs2_replay_truncate_records(struct ocfs2_super *osb,
Mark Fasheh1fabe142006-10-09 18:11:45 -07004626 handle_t *handle,
Mark Fashehccd979b2005-12-15 14:31:24 -08004627 struct inode *data_alloc_inode,
4628 struct buffer_head *data_alloc_bh)
4629{
4630 int status = 0;
4631 int i;
4632 unsigned int num_clusters;
4633 u64 start_blk;
4634 struct ocfs2_truncate_rec rec;
4635 struct ocfs2_dinode *di;
4636 struct ocfs2_truncate_log *tl;
4637 struct inode *tl_inode = osb->osb_tl_inode;
4638 struct buffer_head *tl_bh = osb->osb_tl_bh;
4639
4640 mlog_entry_void();
4641
4642 di = (struct ocfs2_dinode *) tl_bh->b_data;
4643 tl = &di->id2.i_dealloc;
4644 i = le16_to_cpu(tl->tl_used) - 1;
4645 while (i >= 0) {
4646 /* Caller has given us at least enough credits to
4647 * update the truncate log dinode */
4648 status = ocfs2_journal_access(handle, tl_inode, tl_bh,
4649 OCFS2_JOURNAL_ACCESS_WRITE);
4650 if (status < 0) {
4651 mlog_errno(status);
4652 goto bail;
4653 }
4654
4655 tl->tl_used = cpu_to_le16(i);
4656
4657 status = ocfs2_journal_dirty(handle, tl_bh);
4658 if (status < 0) {
4659 mlog_errno(status);
4660 goto bail;
4661 }
4662
4663 /* TODO: Perhaps we can calculate the bulk of the
4664 * credits up front rather than extending like
4665 * this. */
4666 status = ocfs2_extend_trans(handle,
4667 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
4668 if (status < 0) {
4669 mlog_errno(status);
4670 goto bail;
4671 }
4672
4673 rec = tl->tl_recs[i];
4674 start_blk = ocfs2_clusters_to_blocks(data_alloc_inode->i_sb,
4675 le32_to_cpu(rec.t_start));
4676 num_clusters = le32_to_cpu(rec.t_clusters);
4677
4678 /* if start_blk is not set, we ignore the record as
4679 * invalid. */
4680 if (start_blk) {
4681 mlog(0, "free record %d, start = %u, clusters = %u\n",
4682 i, le32_to_cpu(rec.t_start), num_clusters);
4683
4684 status = ocfs2_free_clusters(handle, data_alloc_inode,
4685 data_alloc_bh, start_blk,
4686 num_clusters);
4687 if (status < 0) {
4688 mlog_errno(status);
4689 goto bail;
4690 }
4691 }
4692 i--;
4693 }
4694
4695bail:
4696 mlog_exit(status);
4697 return status;
4698}
4699
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004700/* Expects you to already be holding tl_inode->i_mutex */
Mark Fashehccd979b2005-12-15 14:31:24 -08004701static int __ocfs2_flush_truncate_log(struct ocfs2_super *osb)
4702{
4703 int status;
4704 unsigned int num_to_flush;
Mark Fasheh1fabe142006-10-09 18:11:45 -07004705 handle_t *handle;
Mark Fashehccd979b2005-12-15 14:31:24 -08004706 struct inode *tl_inode = osb->osb_tl_inode;
4707 struct inode *data_alloc_inode = NULL;
4708 struct buffer_head *tl_bh = osb->osb_tl_bh;
4709 struct buffer_head *data_alloc_bh = NULL;
4710 struct ocfs2_dinode *di;
4711 struct ocfs2_truncate_log *tl;
4712
4713 mlog_entry_void();
4714
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004715 BUG_ON(mutex_trylock(&tl_inode->i_mutex));
Mark Fashehccd979b2005-12-15 14:31:24 -08004716
4717 di = (struct ocfs2_dinode *) tl_bh->b_data;
4718 tl = &di->id2.i_dealloc;
4719 if (!OCFS2_IS_VALID_DINODE(di)) {
4720 OCFS2_RO_ON_INVALID_DINODE(osb->sb, di);
4721 status = -EIO;
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004722 goto out;
Mark Fashehccd979b2005-12-15 14:31:24 -08004723 }
4724
4725 num_to_flush = le16_to_cpu(tl->tl_used);
Mark Fashehb06970532006-03-03 10:24:33 -08004726 mlog(0, "Flush %u records from truncate log #%llu\n",
4727 num_to_flush, (unsigned long long)OCFS2_I(tl_inode)->ip_blkno);
Mark Fashehccd979b2005-12-15 14:31:24 -08004728 if (!num_to_flush) {
4729 status = 0;
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004730 goto out;
Mark Fashehccd979b2005-12-15 14:31:24 -08004731 }
4732
4733 data_alloc_inode = ocfs2_get_system_file_inode(osb,
4734 GLOBAL_BITMAP_SYSTEM_INODE,
4735 OCFS2_INVALID_SLOT);
4736 if (!data_alloc_inode) {
4737 status = -EINVAL;
4738 mlog(ML_ERROR, "Could not get bitmap inode!\n");
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004739 goto out;
Mark Fashehccd979b2005-12-15 14:31:24 -08004740 }
4741
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004742 mutex_lock(&data_alloc_inode->i_mutex);
4743
Mark Fasheh4bcec182006-10-09 16:02:40 -07004744 status = ocfs2_meta_lock(data_alloc_inode, &data_alloc_bh, 1);
Mark Fashehccd979b2005-12-15 14:31:24 -08004745 if (status < 0) {
4746 mlog_errno(status);
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004747 goto out_mutex;
Mark Fashehccd979b2005-12-15 14:31:24 -08004748 }
4749
Mark Fasheh65eff9c2006-10-09 17:26:22 -07004750 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
Mark Fashehccd979b2005-12-15 14:31:24 -08004751 if (IS_ERR(handle)) {
4752 status = PTR_ERR(handle);
Mark Fashehccd979b2005-12-15 14:31:24 -08004753 mlog_errno(status);
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004754 goto out_unlock;
Mark Fashehccd979b2005-12-15 14:31:24 -08004755 }
4756
4757 status = ocfs2_replay_truncate_records(osb, handle, data_alloc_inode,
4758 data_alloc_bh);
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004759 if (status < 0)
Mark Fashehccd979b2005-12-15 14:31:24 -08004760 mlog_errno(status);
Mark Fashehccd979b2005-12-15 14:31:24 -08004761
Mark Fasheh02dc1af2006-10-09 16:48:10 -07004762 ocfs2_commit_trans(osb, handle);
Mark Fashehccd979b2005-12-15 14:31:24 -08004763
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004764out_unlock:
4765 brelse(data_alloc_bh);
4766 ocfs2_meta_unlock(data_alloc_inode, 1);
Mark Fashehccd979b2005-12-15 14:31:24 -08004767
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004768out_mutex:
4769 mutex_unlock(&data_alloc_inode->i_mutex);
4770 iput(data_alloc_inode);
Mark Fashehccd979b2005-12-15 14:31:24 -08004771
Mark Fashehe08dc8b2006-10-05 15:58:48 -07004772out:
Mark Fashehccd979b2005-12-15 14:31:24 -08004773 mlog_exit(status);
4774 return status;
4775}
4776
4777int ocfs2_flush_truncate_log(struct ocfs2_super *osb)
4778{
4779 int status;
4780 struct inode *tl_inode = osb->osb_tl_inode;
4781
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004782 mutex_lock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08004783 status = __ocfs2_flush_truncate_log(osb);
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004784 mutex_unlock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08004785
4786 return status;
4787}
4788
David Howellsc4028952006-11-22 14:57:56 +00004789static void ocfs2_truncate_log_worker(struct work_struct *work)
Mark Fashehccd979b2005-12-15 14:31:24 -08004790{
4791 int status;
David Howellsc4028952006-11-22 14:57:56 +00004792 struct ocfs2_super *osb =
4793 container_of(work, struct ocfs2_super,
4794 osb_truncate_log_wq.work);
Mark Fashehccd979b2005-12-15 14:31:24 -08004795
4796 mlog_entry_void();
4797
4798 status = ocfs2_flush_truncate_log(osb);
4799 if (status < 0)
4800 mlog_errno(status);
4801
4802 mlog_exit(status);
4803}
4804
4805#define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
4806void ocfs2_schedule_truncate_log_flush(struct ocfs2_super *osb,
4807 int cancel)
4808{
4809 if (osb->osb_tl_inode) {
4810 /* We want to push off log flushes while truncates are
4811 * still running. */
4812 if (cancel)
4813 cancel_delayed_work(&osb->osb_truncate_log_wq);
4814
4815 queue_delayed_work(ocfs2_wq, &osb->osb_truncate_log_wq,
4816 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
4817 }
4818}
4819
4820static int ocfs2_get_truncate_log_info(struct ocfs2_super *osb,
4821 int slot_num,
4822 struct inode **tl_inode,
4823 struct buffer_head **tl_bh)
4824{
4825 int status;
4826 struct inode *inode = NULL;
4827 struct buffer_head *bh = NULL;
4828
4829 inode = ocfs2_get_system_file_inode(osb,
4830 TRUNCATE_LOG_SYSTEM_INODE,
4831 slot_num);
4832 if (!inode) {
4833 status = -EINVAL;
4834 mlog(ML_ERROR, "Could not get load truncate log inode!\n");
4835 goto bail;
4836 }
4837
4838 status = ocfs2_read_block(osb, OCFS2_I(inode)->ip_blkno, &bh,
4839 OCFS2_BH_CACHED, inode);
4840 if (status < 0) {
4841 iput(inode);
4842 mlog_errno(status);
4843 goto bail;
4844 }
4845
4846 *tl_inode = inode;
4847 *tl_bh = bh;
4848bail:
4849 mlog_exit(status);
4850 return status;
4851}
4852
4853/* called during the 1st stage of node recovery. we stamp a clean
4854 * truncate log and pass back a copy for processing later. if the
4855 * truncate log does not require processing, a *tl_copy is set to
4856 * NULL. */
4857int ocfs2_begin_truncate_log_recovery(struct ocfs2_super *osb,
4858 int slot_num,
4859 struct ocfs2_dinode **tl_copy)
4860{
4861 int status;
4862 struct inode *tl_inode = NULL;
4863 struct buffer_head *tl_bh = NULL;
4864 struct ocfs2_dinode *di;
4865 struct ocfs2_truncate_log *tl;
4866
4867 *tl_copy = NULL;
4868
4869 mlog(0, "recover truncate log from slot %d\n", slot_num);
4870
4871 status = ocfs2_get_truncate_log_info(osb, slot_num, &tl_inode, &tl_bh);
4872 if (status < 0) {
4873 mlog_errno(status);
4874 goto bail;
4875 }
4876
4877 di = (struct ocfs2_dinode *) tl_bh->b_data;
4878 tl = &di->id2.i_dealloc;
4879 if (!OCFS2_IS_VALID_DINODE(di)) {
4880 OCFS2_RO_ON_INVALID_DINODE(tl_inode->i_sb, di);
4881 status = -EIO;
4882 goto bail;
4883 }
4884
4885 if (le16_to_cpu(tl->tl_used)) {
4886 mlog(0, "We'll have %u logs to recover\n",
4887 le16_to_cpu(tl->tl_used));
4888
4889 *tl_copy = kmalloc(tl_bh->b_size, GFP_KERNEL);
4890 if (!(*tl_copy)) {
4891 status = -ENOMEM;
4892 mlog_errno(status);
4893 goto bail;
4894 }
4895
4896 /* Assuming the write-out below goes well, this copy
4897 * will be passed back to recovery for processing. */
4898 memcpy(*tl_copy, tl_bh->b_data, tl_bh->b_size);
4899
4900 /* All we need to do to clear the truncate log is set
4901 * tl_used. */
4902 tl->tl_used = 0;
4903
4904 status = ocfs2_write_block(osb, tl_bh, tl_inode);
4905 if (status < 0) {
4906 mlog_errno(status);
4907 goto bail;
4908 }
4909 }
4910
4911bail:
4912 if (tl_inode)
4913 iput(tl_inode);
4914 if (tl_bh)
4915 brelse(tl_bh);
4916
4917 if (status < 0 && (*tl_copy)) {
4918 kfree(*tl_copy);
4919 *tl_copy = NULL;
4920 }
4921
4922 mlog_exit(status);
4923 return status;
4924}
4925
4926int ocfs2_complete_truncate_log_recovery(struct ocfs2_super *osb,
4927 struct ocfs2_dinode *tl_copy)
4928{
4929 int status = 0;
4930 int i;
4931 unsigned int clusters, num_recs, start_cluster;
4932 u64 start_blk;
Mark Fasheh1fabe142006-10-09 18:11:45 -07004933 handle_t *handle;
Mark Fashehccd979b2005-12-15 14:31:24 -08004934 struct inode *tl_inode = osb->osb_tl_inode;
4935 struct ocfs2_truncate_log *tl;
4936
4937 mlog_entry_void();
4938
4939 if (OCFS2_I(tl_inode)->ip_blkno == le64_to_cpu(tl_copy->i_blkno)) {
4940 mlog(ML_ERROR, "Asked to recover my own truncate log!\n");
4941 return -EINVAL;
4942 }
4943
4944 tl = &tl_copy->id2.i_dealloc;
4945 num_recs = le16_to_cpu(tl->tl_used);
Mark Fashehb06970532006-03-03 10:24:33 -08004946 mlog(0, "cleanup %u records from %llu\n", num_recs,
Mark Fasheh1ca1a112007-04-27 16:01:25 -07004947 (unsigned long long)le64_to_cpu(tl_copy->i_blkno));
Mark Fashehccd979b2005-12-15 14:31:24 -08004948
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004949 mutex_lock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08004950 for(i = 0; i < num_recs; i++) {
4951 if (ocfs2_truncate_log_needs_flush(osb)) {
4952 status = __ocfs2_flush_truncate_log(osb);
4953 if (status < 0) {
4954 mlog_errno(status);
4955 goto bail_up;
4956 }
4957 }
4958
Mark Fasheh65eff9c2006-10-09 17:26:22 -07004959 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE);
Mark Fashehccd979b2005-12-15 14:31:24 -08004960 if (IS_ERR(handle)) {
4961 status = PTR_ERR(handle);
4962 mlog_errno(status);
4963 goto bail_up;
4964 }
4965
4966 clusters = le32_to_cpu(tl->tl_recs[i].t_clusters);
4967 start_cluster = le32_to_cpu(tl->tl_recs[i].t_start);
4968 start_blk = ocfs2_clusters_to_blocks(osb->sb, start_cluster);
4969
4970 status = ocfs2_truncate_log_append(osb, handle,
4971 start_blk, clusters);
Mark Fasheh02dc1af2006-10-09 16:48:10 -07004972 ocfs2_commit_trans(osb, handle);
Mark Fashehccd979b2005-12-15 14:31:24 -08004973 if (status < 0) {
4974 mlog_errno(status);
4975 goto bail_up;
4976 }
4977 }
4978
4979bail_up:
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08004980 mutex_unlock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08004981
4982 mlog_exit(status);
4983 return status;
4984}
4985
4986void ocfs2_truncate_log_shutdown(struct ocfs2_super *osb)
4987{
4988 int status;
4989 struct inode *tl_inode = osb->osb_tl_inode;
4990
4991 mlog_entry_void();
4992
4993 if (tl_inode) {
4994 cancel_delayed_work(&osb->osb_truncate_log_wq);
4995 flush_workqueue(ocfs2_wq);
4996
4997 status = ocfs2_flush_truncate_log(osb);
4998 if (status < 0)
4999 mlog_errno(status);
5000
5001 brelse(osb->osb_tl_bh);
5002 iput(osb->osb_tl_inode);
5003 }
5004
5005 mlog_exit_void();
5006}
5007
5008int ocfs2_truncate_log_init(struct ocfs2_super *osb)
5009{
5010 int status;
5011 struct inode *tl_inode = NULL;
5012 struct buffer_head *tl_bh = NULL;
5013
5014 mlog_entry_void();
5015
5016 status = ocfs2_get_truncate_log_info(osb,
5017 osb->slot_num,
5018 &tl_inode,
5019 &tl_bh);
5020 if (status < 0)
5021 mlog_errno(status);
5022
5023 /* ocfs2_truncate_log_shutdown keys on the existence of
5024 * osb->osb_tl_inode so we don't set any of the osb variables
5025 * until we're sure all is well. */
David Howellsc4028952006-11-22 14:57:56 +00005026 INIT_DELAYED_WORK(&osb->osb_truncate_log_wq,
5027 ocfs2_truncate_log_worker);
Mark Fashehccd979b2005-12-15 14:31:24 -08005028 osb->osb_tl_bh = tl_bh;
5029 osb->osb_tl_inode = tl_inode;
5030
5031 mlog_exit(status);
5032 return status;
5033}
5034
Mark Fasheh2b604352007-06-22 15:45:27 -07005035/*
5036 * Delayed de-allocation of suballocator blocks.
5037 *
5038 * Some sets of block de-allocations might involve multiple suballocator inodes.
5039 *
5040 * The locking for this can get extremely complicated, especially when
5041 * the suballocator inodes to delete from aren't known until deep
5042 * within an unrelated codepath.
5043 *
5044 * ocfs2_extent_block structures are a good example of this - an inode
5045 * btree could have been grown by any number of nodes each allocating
5046 * out of their own suballoc inode.
5047 *
5048 * These structures allow the delay of block de-allocation until a
5049 * later time, when locking of multiple cluster inodes won't cause
5050 * deadlock.
5051 */
5052
5053/*
5054 * Describes a single block free from a suballocator
5055 */
5056struct ocfs2_cached_block_free {
5057 struct ocfs2_cached_block_free *free_next;
5058 u64 free_blk;
5059 unsigned int free_bit;
5060};
5061
5062struct ocfs2_per_slot_free_list {
5063 struct ocfs2_per_slot_free_list *f_next_suballocator;
5064 int f_inode_type;
5065 int f_slot;
5066 struct ocfs2_cached_block_free *f_first;
5067};
5068
5069static int ocfs2_free_cached_items(struct ocfs2_super *osb,
5070 int sysfile_type,
5071 int slot,
5072 struct ocfs2_cached_block_free *head)
5073{
5074 int ret;
5075 u64 bg_blkno;
5076 handle_t *handle;
5077 struct inode *inode;
5078 struct buffer_head *di_bh = NULL;
5079 struct ocfs2_cached_block_free *tmp;
5080
5081 inode = ocfs2_get_system_file_inode(osb, sysfile_type, slot);
5082 if (!inode) {
5083 ret = -EINVAL;
5084 mlog_errno(ret);
5085 goto out;
5086 }
5087
5088 mutex_lock(&inode->i_mutex);
5089
5090 ret = ocfs2_meta_lock(inode, &di_bh, 1);
5091 if (ret) {
5092 mlog_errno(ret);
5093 goto out_mutex;
5094 }
5095
5096 handle = ocfs2_start_trans(osb, OCFS2_SUBALLOC_FREE);
5097 if (IS_ERR(handle)) {
5098 ret = PTR_ERR(handle);
5099 mlog_errno(ret);
5100 goto out_unlock;
5101 }
5102
5103 while (head) {
5104 bg_blkno = ocfs2_which_suballoc_group(head->free_blk,
5105 head->free_bit);
5106 mlog(0, "Free bit: (bit %u, blkno %llu)\n",
5107 head->free_bit, (unsigned long long)head->free_blk);
5108
5109 ret = ocfs2_free_suballoc_bits(handle, inode, di_bh,
5110 head->free_bit, bg_blkno, 1);
5111 if (ret) {
5112 mlog_errno(ret);
5113 goto out_journal;
5114 }
5115
5116 ret = ocfs2_extend_trans(handle, OCFS2_SUBALLOC_FREE);
5117 if (ret) {
5118 mlog_errno(ret);
5119 goto out_journal;
5120 }
5121
5122 tmp = head;
5123 head = head->free_next;
5124 kfree(tmp);
5125 }
5126
5127out_journal:
5128 ocfs2_commit_trans(osb, handle);
5129
5130out_unlock:
5131 ocfs2_meta_unlock(inode, 1);
5132 brelse(di_bh);
5133out_mutex:
5134 mutex_unlock(&inode->i_mutex);
5135 iput(inode);
5136out:
5137 while(head) {
5138 /* Premature exit may have left some dangling items. */
5139 tmp = head;
5140 head = head->free_next;
5141 kfree(tmp);
5142 }
5143
5144 return ret;
5145}
5146
5147int ocfs2_run_deallocs(struct ocfs2_super *osb,
5148 struct ocfs2_cached_dealloc_ctxt *ctxt)
5149{
5150 int ret = 0, ret2;
5151 struct ocfs2_per_slot_free_list *fl;
5152
5153 if (!ctxt)
5154 return 0;
5155
5156 while (ctxt->c_first_suballocator) {
5157 fl = ctxt->c_first_suballocator;
5158
5159 if (fl->f_first) {
5160 mlog(0, "Free items: (type %u, slot %d)\n",
5161 fl->f_inode_type, fl->f_slot);
5162 ret2 = ocfs2_free_cached_items(osb, fl->f_inode_type,
5163 fl->f_slot, fl->f_first);
5164 if (ret2)
5165 mlog_errno(ret2);
5166 if (!ret)
5167 ret = ret2;
5168 }
5169
5170 ctxt->c_first_suballocator = fl->f_next_suballocator;
5171 kfree(fl);
5172 }
5173
5174 return ret;
5175}
5176
5177static struct ocfs2_per_slot_free_list *
5178ocfs2_find_per_slot_free_list(int type,
5179 int slot,
5180 struct ocfs2_cached_dealloc_ctxt *ctxt)
5181{
5182 struct ocfs2_per_slot_free_list *fl = ctxt->c_first_suballocator;
5183
5184 while (fl) {
5185 if (fl->f_inode_type == type && fl->f_slot == slot)
5186 return fl;
5187
5188 fl = fl->f_next_suballocator;
5189 }
5190
5191 fl = kmalloc(sizeof(*fl), GFP_NOFS);
5192 if (fl) {
5193 fl->f_inode_type = type;
5194 fl->f_slot = slot;
5195 fl->f_first = NULL;
5196 fl->f_next_suballocator = ctxt->c_first_suballocator;
5197
5198 ctxt->c_first_suballocator = fl;
5199 }
5200 return fl;
5201}
5202
5203static int ocfs2_cache_block_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt,
5204 int type, int slot, u64 blkno,
5205 unsigned int bit)
5206{
5207 int ret;
5208 struct ocfs2_per_slot_free_list *fl;
5209 struct ocfs2_cached_block_free *item;
5210
5211 fl = ocfs2_find_per_slot_free_list(type, slot, ctxt);
5212 if (fl == NULL) {
5213 ret = -ENOMEM;
5214 mlog_errno(ret);
5215 goto out;
5216 }
5217
5218 item = kmalloc(sizeof(*item), GFP_NOFS);
5219 if (item == NULL) {
5220 ret = -ENOMEM;
5221 mlog_errno(ret);
5222 goto out;
5223 }
5224
5225 mlog(0, "Insert: (type %d, slot %u, bit %u, blk %llu)\n",
5226 type, slot, bit, (unsigned long long)blkno);
5227
5228 item->free_blk = blkno;
5229 item->free_bit = bit;
5230 item->free_next = fl->f_first;
5231
5232 fl->f_first = item;
5233
5234 ret = 0;
5235out:
5236 return ret;
5237}
5238
Mark Fasheh59a5e412007-06-22 15:52:36 -07005239static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt,
5240 struct ocfs2_extent_block *eb)
5241{
5242 return ocfs2_cache_block_dealloc(ctxt, EXTENT_ALLOC_SYSTEM_INODE,
5243 le16_to_cpu(eb->h_suballoc_slot),
5244 le64_to_cpu(eb->h_blkno),
5245 le16_to_cpu(eb->h_suballoc_bit));
5246}
5247
Mark Fashehccd979b2005-12-15 14:31:24 -08005248/* This function will figure out whether the currently last extent
5249 * block will be deleted, and if it will, what the new last extent
5250 * block will be so we can update his h_next_leaf_blk field, as well
5251 * as the dinodes i_last_eb_blk */
Mark Fashehdcd05382007-01-16 11:32:23 -08005252static int ocfs2_find_new_last_ext_blk(struct inode *inode,
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005253 unsigned int clusters_to_del,
Mark Fashehdcd05382007-01-16 11:32:23 -08005254 struct ocfs2_path *path,
Mark Fashehccd979b2005-12-15 14:31:24 -08005255 struct buffer_head **new_last_eb)
5256{
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005257 int next_free, ret = 0;
Mark Fashehdcd05382007-01-16 11:32:23 -08005258 u32 cpos;
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005259 struct ocfs2_extent_rec *rec;
Mark Fashehccd979b2005-12-15 14:31:24 -08005260 struct ocfs2_extent_block *eb;
5261 struct ocfs2_extent_list *el;
5262 struct buffer_head *bh = NULL;
5263
5264 *new_last_eb = NULL;
5265
Mark Fashehccd979b2005-12-15 14:31:24 -08005266 /* we have no tree, so of course, no last_eb. */
Mark Fashehdcd05382007-01-16 11:32:23 -08005267 if (!path->p_tree_depth)
5268 goto out;
Mark Fashehccd979b2005-12-15 14:31:24 -08005269
5270 /* trunc to zero special case - this makes tree_depth = 0
5271 * regardless of what it is. */
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005272 if (OCFS2_I(inode)->ip_clusters == clusters_to_del)
Mark Fashehdcd05382007-01-16 11:32:23 -08005273 goto out;
Mark Fashehccd979b2005-12-15 14:31:24 -08005274
Mark Fashehdcd05382007-01-16 11:32:23 -08005275 el = path_leaf_el(path);
Mark Fashehccd979b2005-12-15 14:31:24 -08005276 BUG_ON(!el->l_next_free_rec);
5277
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005278 /*
5279 * Make sure that this extent list will actually be empty
5280 * after we clear away the data. We can shortcut out if
5281 * there's more than one non-empty extent in the
5282 * list. Otherwise, a check of the remaining extent is
5283 * necessary.
5284 */
5285 next_free = le16_to_cpu(el->l_next_free_rec);
5286 rec = NULL;
Mark Fashehdcd05382007-01-16 11:32:23 -08005287 if (ocfs2_is_empty_extent(&el->l_recs[0])) {
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005288 if (next_free > 2)
Mark Fashehdcd05382007-01-16 11:32:23 -08005289 goto out;
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005290
5291 /* We may have a valid extent in index 1, check it. */
5292 if (next_free == 2)
5293 rec = &el->l_recs[1];
5294
5295 /*
5296 * Fall through - no more nonempty extents, so we want
5297 * to delete this leaf.
5298 */
5299 } else {
5300 if (next_free > 1)
5301 goto out;
5302
5303 rec = &el->l_recs[0];
5304 }
5305
5306 if (rec) {
5307 /*
5308 * Check it we'll only be trimming off the end of this
5309 * cluster.
5310 */
Mark Fashehe48edee2007-03-07 16:46:57 -08005311 if (le16_to_cpu(rec->e_leaf_clusters) > clusters_to_del)
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005312 goto out;
5313 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005314
Mark Fashehdcd05382007-01-16 11:32:23 -08005315 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos);
5316 if (ret) {
5317 mlog_errno(ret);
5318 goto out;
5319 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005320
Mark Fashehdcd05382007-01-16 11:32:23 -08005321 ret = ocfs2_find_leaf(inode, path_root_el(path), cpos, &bh);
5322 if (ret) {
5323 mlog_errno(ret);
5324 goto out;
5325 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005326
Mark Fashehdcd05382007-01-16 11:32:23 -08005327 eb = (struct ocfs2_extent_block *) bh->b_data;
5328 el = &eb->h_list;
5329 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
5330 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
5331 ret = -EROFS;
5332 goto out;
5333 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005334
5335 *new_last_eb = bh;
5336 get_bh(*new_last_eb);
Mark Fashehdcd05382007-01-16 11:32:23 -08005337 mlog(0, "returning block %llu, (cpos: %u)\n",
5338 (unsigned long long)le64_to_cpu(eb->h_blkno), cpos);
5339out:
5340 brelse(bh);
Mark Fashehccd979b2005-12-15 14:31:24 -08005341
Mark Fashehdcd05382007-01-16 11:32:23 -08005342 return ret;
Mark Fashehccd979b2005-12-15 14:31:24 -08005343}
5344
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005345/*
5346 * Trim some clusters off the rightmost edge of a tree. Only called
5347 * during truncate.
5348 *
5349 * The caller needs to:
5350 * - start journaling of each path component.
5351 * - compute and fully set up any new last ext block
5352 */
5353static int ocfs2_trim_tree(struct inode *inode, struct ocfs2_path *path,
5354 handle_t *handle, struct ocfs2_truncate_context *tc,
5355 u32 clusters_to_del, u64 *delete_start)
5356{
5357 int ret, i, index = path->p_tree_depth;
5358 u32 new_edge = 0;
5359 u64 deleted_eb = 0;
5360 struct buffer_head *bh;
5361 struct ocfs2_extent_list *el;
5362 struct ocfs2_extent_rec *rec;
5363
5364 *delete_start = 0;
5365
5366 while (index >= 0) {
5367 bh = path->p_node[index].bh;
5368 el = path->p_node[index].el;
5369
5370 mlog(0, "traveling tree (index = %d, block = %llu)\n",
5371 index, (unsigned long long)bh->b_blocknr);
5372
5373 BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0);
5374
5375 if (index !=
5376 (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) {
5377 ocfs2_error(inode->i_sb,
5378 "Inode %lu has invalid ext. block %llu",
5379 inode->i_ino,
5380 (unsigned long long)bh->b_blocknr);
5381 ret = -EROFS;
5382 goto out;
5383 }
5384
5385find_tail_record:
5386 i = le16_to_cpu(el->l_next_free_rec) - 1;
5387 rec = &el->l_recs[i];
5388
5389 mlog(0, "Extent list before: record %d: (%u, %u, %llu), "
5390 "next = %u\n", i, le32_to_cpu(rec->e_cpos),
Mark Fashehe48edee2007-03-07 16:46:57 -08005391 ocfs2_rec_clusters(el, rec),
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005392 (unsigned long long)le64_to_cpu(rec->e_blkno),
5393 le16_to_cpu(el->l_next_free_rec));
5394
Mark Fashehe48edee2007-03-07 16:46:57 -08005395 BUG_ON(ocfs2_rec_clusters(el, rec) < clusters_to_del);
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005396
5397 if (le16_to_cpu(el->l_tree_depth) == 0) {
5398 /*
5399 * If the leaf block contains a single empty
5400 * extent and no records, we can just remove
5401 * the block.
5402 */
5403 if (i == 0 && ocfs2_is_empty_extent(rec)) {
5404 memset(rec, 0,
5405 sizeof(struct ocfs2_extent_rec));
5406 el->l_next_free_rec = cpu_to_le16(0);
5407
5408 goto delete;
5409 }
5410
5411 /*
5412 * Remove any empty extents by shifting things
5413 * left. That should make life much easier on
5414 * the code below. This condition is rare
5415 * enough that we shouldn't see a performance
5416 * hit.
5417 */
5418 if (ocfs2_is_empty_extent(&el->l_recs[0])) {
5419 le16_add_cpu(&el->l_next_free_rec, -1);
5420
5421 for(i = 0;
5422 i < le16_to_cpu(el->l_next_free_rec); i++)
5423 el->l_recs[i] = el->l_recs[i + 1];
5424
5425 memset(&el->l_recs[i], 0,
5426 sizeof(struct ocfs2_extent_rec));
5427
5428 /*
5429 * We've modified our extent list. The
5430 * simplest way to handle this change
5431 * is to being the search from the
5432 * start again.
5433 */
5434 goto find_tail_record;
5435 }
5436
Mark Fashehe48edee2007-03-07 16:46:57 -08005437 le16_add_cpu(&rec->e_leaf_clusters, -clusters_to_del);
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005438
5439 /*
5440 * We'll use "new_edge" on our way back up the
5441 * tree to know what our rightmost cpos is.
5442 */
Mark Fashehe48edee2007-03-07 16:46:57 -08005443 new_edge = le16_to_cpu(rec->e_leaf_clusters);
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005444 new_edge += le32_to_cpu(rec->e_cpos);
5445
5446 /*
5447 * The caller will use this to delete data blocks.
5448 */
5449 *delete_start = le64_to_cpu(rec->e_blkno)
5450 + ocfs2_clusters_to_blocks(inode->i_sb,
Mark Fashehe48edee2007-03-07 16:46:57 -08005451 le16_to_cpu(rec->e_leaf_clusters));
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005452
5453 /*
5454 * If it's now empty, remove this record.
5455 */
Mark Fashehe48edee2007-03-07 16:46:57 -08005456 if (le16_to_cpu(rec->e_leaf_clusters) == 0) {
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005457 memset(rec, 0,
5458 sizeof(struct ocfs2_extent_rec));
5459 le16_add_cpu(&el->l_next_free_rec, -1);
5460 }
5461 } else {
5462 if (le64_to_cpu(rec->e_blkno) == deleted_eb) {
5463 memset(rec, 0,
5464 sizeof(struct ocfs2_extent_rec));
5465 le16_add_cpu(&el->l_next_free_rec, -1);
5466
5467 goto delete;
5468 }
5469
5470 /* Can this actually happen? */
5471 if (le16_to_cpu(el->l_next_free_rec) == 0)
5472 goto delete;
5473
5474 /*
5475 * We never actually deleted any clusters
5476 * because our leaf was empty. There's no
5477 * reason to adjust the rightmost edge then.
5478 */
5479 if (new_edge == 0)
5480 goto delete;
5481
Mark Fashehe48edee2007-03-07 16:46:57 -08005482 rec->e_int_clusters = cpu_to_le32(new_edge);
5483 le32_add_cpu(&rec->e_int_clusters,
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005484 -le32_to_cpu(rec->e_cpos));
5485
5486 /*
5487 * A deleted child record should have been
5488 * caught above.
5489 */
Mark Fashehe48edee2007-03-07 16:46:57 -08005490 BUG_ON(le32_to_cpu(rec->e_int_clusters) == 0);
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005491 }
5492
5493delete:
5494 ret = ocfs2_journal_dirty(handle, bh);
5495 if (ret) {
5496 mlog_errno(ret);
5497 goto out;
5498 }
5499
5500 mlog(0, "extent list container %llu, after: record %d: "
5501 "(%u, %u, %llu), next = %u.\n",
5502 (unsigned long long)bh->b_blocknr, i,
Mark Fashehe48edee2007-03-07 16:46:57 -08005503 le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec),
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005504 (unsigned long long)le64_to_cpu(rec->e_blkno),
5505 le16_to_cpu(el->l_next_free_rec));
5506
5507 /*
5508 * We must be careful to only attempt delete of an
5509 * extent block (and not the root inode block).
5510 */
5511 if (index > 0 && le16_to_cpu(el->l_next_free_rec) == 0) {
5512 struct ocfs2_extent_block *eb =
5513 (struct ocfs2_extent_block *)bh->b_data;
5514
5515 /*
5516 * Save this for use when processing the
5517 * parent block.
5518 */
5519 deleted_eb = le64_to_cpu(eb->h_blkno);
5520
5521 mlog(0, "deleting this extent block.\n");
5522
5523 ocfs2_remove_from_cache(inode, bh);
5524
Mark Fashehe48edee2007-03-07 16:46:57 -08005525 BUG_ON(ocfs2_rec_clusters(el, &el->l_recs[0]));
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005526 BUG_ON(le32_to_cpu(el->l_recs[0].e_cpos));
5527 BUG_ON(le64_to_cpu(el->l_recs[0].e_blkno));
5528
Mark Fasheh59a5e412007-06-22 15:52:36 -07005529 ret = ocfs2_cache_extent_block_free(&tc->tc_dealloc, eb);
5530 /* An error here is not fatal. */
5531 if (ret < 0)
5532 mlog_errno(ret);
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005533 } else {
5534 deleted_eb = 0;
5535 }
5536
5537 index--;
5538 }
5539
5540 ret = 0;
5541out:
5542 return ret;
5543}
5544
Mark Fashehccd979b2005-12-15 14:31:24 -08005545static int ocfs2_do_truncate(struct ocfs2_super *osb,
5546 unsigned int clusters_to_del,
5547 struct inode *inode,
5548 struct buffer_head *fe_bh,
Mark Fasheh1fabe142006-10-09 18:11:45 -07005549 handle_t *handle,
Mark Fashehdcd05382007-01-16 11:32:23 -08005550 struct ocfs2_truncate_context *tc,
5551 struct ocfs2_path *path)
Mark Fashehccd979b2005-12-15 14:31:24 -08005552{
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005553 int status;
Mark Fashehccd979b2005-12-15 14:31:24 -08005554 struct ocfs2_dinode *fe;
Mark Fashehccd979b2005-12-15 14:31:24 -08005555 struct ocfs2_extent_block *last_eb = NULL;
5556 struct ocfs2_extent_list *el;
Mark Fashehccd979b2005-12-15 14:31:24 -08005557 struct buffer_head *last_eb_bh = NULL;
Mark Fashehccd979b2005-12-15 14:31:24 -08005558 u64 delete_blk = 0;
5559
5560 fe = (struct ocfs2_dinode *) fe_bh->b_data;
5561
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005562 status = ocfs2_find_new_last_ext_blk(inode, clusters_to_del,
Mark Fashehdcd05382007-01-16 11:32:23 -08005563 path, &last_eb_bh);
Mark Fashehccd979b2005-12-15 14:31:24 -08005564 if (status < 0) {
5565 mlog_errno(status);
5566 goto bail;
5567 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005568
Mark Fashehdcd05382007-01-16 11:32:23 -08005569 /*
5570 * Each component will be touched, so we might as well journal
5571 * here to avoid having to handle errors later.
5572 */
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005573 status = ocfs2_journal_access_path(inode, handle, path);
5574 if (status < 0) {
5575 mlog_errno(status);
5576 goto bail;
Mark Fashehdcd05382007-01-16 11:32:23 -08005577 }
5578
5579 if (last_eb_bh) {
5580 status = ocfs2_journal_access(handle, inode, last_eb_bh,
5581 OCFS2_JOURNAL_ACCESS_WRITE);
5582 if (status < 0) {
5583 mlog_errno(status);
5584 goto bail;
5585 }
5586
5587 last_eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
5588 }
5589
5590 el = &(fe->id2.i_list);
5591
5592 /*
5593 * Lower levels depend on this never happening, but it's best
5594 * to check it up here before changing the tree.
5595 */
Mark Fashehe48edee2007-03-07 16:46:57 -08005596 if (el->l_tree_depth && el->l_recs[0].e_int_clusters == 0) {
Mark Fashehdcd05382007-01-16 11:32:23 -08005597 ocfs2_error(inode->i_sb,
5598 "Inode %lu has an empty extent record, depth %u\n",
5599 inode->i_ino, le16_to_cpu(el->l_tree_depth));
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005600 status = -EROFS;
Mark Fashehccd979b2005-12-15 14:31:24 -08005601 goto bail;
5602 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005603
5604 spin_lock(&OCFS2_I(inode)->ip_lock);
5605 OCFS2_I(inode)->ip_clusters = le32_to_cpu(fe->i_clusters) -
5606 clusters_to_del;
5607 spin_unlock(&OCFS2_I(inode)->ip_lock);
5608 le32_add_cpu(&fe->i_clusters, -clusters_to_del);
Mark Fashehccd979b2005-12-15 14:31:24 -08005609
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005610 status = ocfs2_trim_tree(inode, path, handle, tc,
5611 clusters_to_del, &delete_blk);
5612 if (status) {
5613 mlog_errno(status);
5614 goto bail;
Mark Fashehccd979b2005-12-15 14:31:24 -08005615 }
5616
Mark Fashehdcd05382007-01-16 11:32:23 -08005617 if (le32_to_cpu(fe->i_clusters) == 0) {
Mark Fashehccd979b2005-12-15 14:31:24 -08005618 /* trunc to zero is a special case. */
5619 el->l_tree_depth = 0;
5620 fe->i_last_eb_blk = 0;
5621 } else if (last_eb)
5622 fe->i_last_eb_blk = last_eb->h_blkno;
5623
5624 status = ocfs2_journal_dirty(handle, fe_bh);
5625 if (status < 0) {
5626 mlog_errno(status);
5627 goto bail;
5628 }
5629
5630 if (last_eb) {
5631 /* If there will be a new last extent block, then by
5632 * definition, there cannot be any leaves to the right of
5633 * him. */
Mark Fashehccd979b2005-12-15 14:31:24 -08005634 last_eb->h_next_leaf_blk = 0;
5635 status = ocfs2_journal_dirty(handle, last_eb_bh);
5636 if (status < 0) {
5637 mlog_errno(status);
5638 goto bail;
5639 }
5640 }
5641
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005642 if (delete_blk) {
5643 status = ocfs2_truncate_log_append(osb, handle, delete_blk,
5644 clusters_to_del);
Mark Fashehccd979b2005-12-15 14:31:24 -08005645 if (status < 0) {
5646 mlog_errno(status);
5647 goto bail;
5648 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005649 }
5650 status = 0;
5651bail:
Mark Fashehdcd05382007-01-16 11:32:23 -08005652
Mark Fashehccd979b2005-12-15 14:31:24 -08005653 mlog_exit(status);
5654 return status;
5655}
5656
Mark Fasheh60b11392007-02-16 11:46:50 -08005657static int ocfs2_writeback_zero_func(handle_t *handle, struct buffer_head *bh)
5658{
5659 set_buffer_uptodate(bh);
5660 mark_buffer_dirty(bh);
5661 return 0;
5662}
5663
5664static int ocfs2_ordered_zero_func(handle_t *handle, struct buffer_head *bh)
5665{
5666 set_buffer_uptodate(bh);
5667 mark_buffer_dirty(bh);
5668 return ocfs2_journal_dirty_data(handle, bh);
5669}
5670
Mark Fasheh35edec12007-07-06 14:41:18 -07005671static void ocfs2_zero_cluster_pages(struct inode *inode, loff_t start,
5672 loff_t end, struct page **pages,
5673 int numpages, u64 phys, handle_t *handle)
Mark Fasheh60b11392007-02-16 11:46:50 -08005674{
5675 int i, ret, partial = 0;
5676 void *kaddr;
5677 struct page *page;
5678 unsigned int from, to = PAGE_CACHE_SIZE;
5679 struct super_block *sb = inode->i_sb;
5680
5681 BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb)));
5682
5683 if (numpages == 0)
5684 goto out;
5685
Mark Fasheh35edec12007-07-06 14:41:18 -07005686 to = PAGE_CACHE_SIZE;
Mark Fasheh60b11392007-02-16 11:46:50 -08005687 for(i = 0; i < numpages; i++) {
5688 page = pages[i];
5689
Mark Fasheh35edec12007-07-06 14:41:18 -07005690 from = start & (PAGE_CACHE_SIZE - 1);
5691 if ((end >> PAGE_CACHE_SHIFT) == page->index)
5692 to = end & (PAGE_CACHE_SIZE - 1);
5693
Mark Fasheh60b11392007-02-16 11:46:50 -08005694 BUG_ON(from > PAGE_CACHE_SIZE);
5695 BUG_ON(to > PAGE_CACHE_SIZE);
5696
5697 ret = ocfs2_map_page_blocks(page, &phys, inode, from, to, 0);
5698 if (ret)
5699 mlog_errno(ret);
5700
5701 kaddr = kmap_atomic(page, KM_USER0);
5702 memset(kaddr + from, 0, to - from);
5703 kunmap_atomic(kaddr, KM_USER0);
5704
5705 /*
5706 * Need to set the buffers we zero'd into uptodate
5707 * here if they aren't - ocfs2_map_page_blocks()
5708 * might've skipped some
5709 */
5710 if (ocfs2_should_order_data(inode)) {
5711 ret = walk_page_buffers(handle,
5712 page_buffers(page),
5713 from, to, &partial,
5714 ocfs2_ordered_zero_func);
5715 if (ret < 0)
5716 mlog_errno(ret);
5717 } else {
5718 ret = walk_page_buffers(handle, page_buffers(page),
5719 from, to, &partial,
5720 ocfs2_writeback_zero_func);
5721 if (ret < 0)
5722 mlog_errno(ret);
5723 }
5724
5725 if (!partial)
5726 SetPageUptodate(page);
5727
5728 flush_dcache_page(page);
5729
Mark Fasheh35edec12007-07-06 14:41:18 -07005730 start = (page->index + 1) << PAGE_CACHE_SHIFT;
Mark Fasheh60b11392007-02-16 11:46:50 -08005731 }
5732out:
5733 if (pages) {
5734 for (i = 0; i < numpages; i++) {
5735 page = pages[i];
5736 unlock_page(page);
5737 mark_page_accessed(page);
5738 page_cache_release(page);
5739 }
5740 }
5741}
5742
Mark Fasheh35edec12007-07-06 14:41:18 -07005743static int ocfs2_grab_eof_pages(struct inode *inode, loff_t start, loff_t end,
5744 struct page **pages, int *num, u64 *phys)
Mark Fasheh60b11392007-02-16 11:46:50 -08005745{
5746 int i, numpages = 0, ret = 0;
Mark Fasheh49cb8d22007-03-09 16:21:46 -08005747 unsigned int ext_flags;
Mark Fasheh60b11392007-02-16 11:46:50 -08005748 struct super_block *sb = inode->i_sb;
5749 struct address_space *mapping = inode->i_mapping;
5750 unsigned long index;
Mark Fasheh35edec12007-07-06 14:41:18 -07005751 loff_t last_page_bytes;
Mark Fasheh60b11392007-02-16 11:46:50 -08005752
5753 BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb)));
Mark Fasheh35edec12007-07-06 14:41:18 -07005754 BUG_ON(start > end);
Mark Fasheh60b11392007-02-16 11:46:50 -08005755
Mark Fasheh35edec12007-07-06 14:41:18 -07005756 if (start == end)
Mark Fasheh60b11392007-02-16 11:46:50 -08005757 goto out;
5758
Mark Fasheh35edec12007-07-06 14:41:18 -07005759 BUG_ON(start >> OCFS2_SB(sb)->s_clustersize_bits !=
5760 (end - 1) >> OCFS2_SB(sb)->s_clustersize_bits);
5761
5762 ret = ocfs2_extent_map_get_blocks(inode, start >> sb->s_blocksize_bits,
Mark Fasheh49cb8d22007-03-09 16:21:46 -08005763 phys, NULL, &ext_flags);
Mark Fasheh60b11392007-02-16 11:46:50 -08005764 if (ret) {
5765 mlog_errno(ret);
5766 goto out;
5767 }
5768
5769 /* Tail is a hole. */
5770 if (*phys == 0)
5771 goto out;
5772
Mark Fasheh49cb8d22007-03-09 16:21:46 -08005773 /* Tail is marked as unwritten, we can count on write to zero
5774 * in that case. */
5775 if (ext_flags & OCFS2_EXT_UNWRITTEN)
5776 goto out;
5777
Mark Fasheh35edec12007-07-06 14:41:18 -07005778 last_page_bytes = PAGE_ALIGN(end);
5779 index = start >> PAGE_CACHE_SHIFT;
Mark Fasheh60b11392007-02-16 11:46:50 -08005780 do {
5781 pages[numpages] = grab_cache_page(mapping, index);
5782 if (!pages[numpages]) {
5783 ret = -ENOMEM;
5784 mlog_errno(ret);
5785 goto out;
5786 }
5787
5788 numpages++;
5789 index++;
Mark Fasheh35edec12007-07-06 14:41:18 -07005790 } while (index < (last_page_bytes >> PAGE_CACHE_SHIFT));
Mark Fasheh60b11392007-02-16 11:46:50 -08005791
5792out:
5793 if (ret != 0) {
5794 if (pages) {
5795 for (i = 0; i < numpages; i++) {
5796 if (pages[i]) {
5797 unlock_page(pages[i]);
5798 page_cache_release(pages[i]);
5799 }
5800 }
5801 }
5802 numpages = 0;
5803 }
5804
5805 *num = numpages;
5806
5807 return ret;
5808}
5809
5810/*
5811 * Zero the area past i_size but still within an allocated
5812 * cluster. This avoids exposing nonzero data on subsequent file
5813 * extends.
5814 *
5815 * We need to call this before i_size is updated on the inode because
5816 * otherwise block_write_full_page() will skip writeout of pages past
5817 * i_size. The new_i_size parameter is passed for this reason.
5818 */
Mark Fasheh35edec12007-07-06 14:41:18 -07005819int ocfs2_zero_range_for_truncate(struct inode *inode, handle_t *handle,
5820 u64 range_start, u64 range_end)
Mark Fasheh60b11392007-02-16 11:46:50 -08005821{
5822 int ret, numpages;
5823 struct page **pages = NULL;
5824 u64 phys;
5825
5826 /*
5827 * File systems which don't support sparse files zero on every
5828 * extend.
5829 */
5830 if (!ocfs2_sparse_alloc(OCFS2_SB(inode->i_sb)))
5831 return 0;
5832
5833 pages = kcalloc(ocfs2_pages_per_cluster(inode->i_sb),
5834 sizeof(struct page *), GFP_NOFS);
5835 if (pages == NULL) {
5836 ret = -ENOMEM;
5837 mlog_errno(ret);
5838 goto out;
5839 }
5840
Mark Fasheh35edec12007-07-06 14:41:18 -07005841 ret = ocfs2_grab_eof_pages(inode, range_start, range_end, pages,
5842 &numpages, &phys);
Mark Fasheh60b11392007-02-16 11:46:50 -08005843 if (ret) {
5844 mlog_errno(ret);
5845 goto out;
5846 }
5847
Mark Fasheh60b11392007-02-16 11:46:50 -08005848 if (numpages == 0)
5849 goto out;
5850
Mark Fasheh35edec12007-07-06 14:41:18 -07005851 ocfs2_zero_cluster_pages(inode, range_start, range_end, pages,
5852 numpages, phys, handle);
Mark Fasheh60b11392007-02-16 11:46:50 -08005853
5854 /*
5855 * Initiate writeout of the pages we zero'd here. We don't
5856 * wait on them - the truncate_inode_pages() call later will
5857 * do that for us.
5858 */
Mark Fasheh35edec12007-07-06 14:41:18 -07005859 ret = do_sync_mapping_range(inode->i_mapping, range_start,
5860 range_end - 1, SYNC_FILE_RANGE_WRITE);
Mark Fasheh60b11392007-02-16 11:46:50 -08005861 if (ret)
5862 mlog_errno(ret);
5863
5864out:
5865 if (pages)
5866 kfree(pages);
5867
5868 return ret;
5869}
5870
Mark Fashehccd979b2005-12-15 14:31:24 -08005871/*
5872 * It is expected, that by the time you call this function,
5873 * inode->i_size and fe->i_size have been adjusted.
5874 *
5875 * WARNING: This will kfree the truncate context
5876 */
5877int ocfs2_commit_truncate(struct ocfs2_super *osb,
5878 struct inode *inode,
5879 struct buffer_head *fe_bh,
5880 struct ocfs2_truncate_context *tc)
5881{
5882 int status, i, credits, tl_sem = 0;
Mark Fashehdcd05382007-01-16 11:32:23 -08005883 u32 clusters_to_del, new_highest_cpos, range;
Mark Fashehccd979b2005-12-15 14:31:24 -08005884 struct ocfs2_extent_list *el;
Mark Fasheh1fabe142006-10-09 18:11:45 -07005885 handle_t *handle = NULL;
Mark Fashehccd979b2005-12-15 14:31:24 -08005886 struct inode *tl_inode = osb->osb_tl_inode;
Mark Fashehdcd05382007-01-16 11:32:23 -08005887 struct ocfs2_path *path = NULL;
Mark Fashehccd979b2005-12-15 14:31:24 -08005888
5889 mlog_entry_void();
5890
Mark Fashehdcd05382007-01-16 11:32:23 -08005891 new_highest_cpos = ocfs2_clusters_for_bytes(osb->sb,
Mark Fashehccd979b2005-12-15 14:31:24 -08005892 i_size_read(inode));
5893
Mark Fashehdcd05382007-01-16 11:32:23 -08005894 path = ocfs2_new_inode_path(fe_bh);
5895 if (!path) {
5896 status = -ENOMEM;
5897 mlog_errno(status);
5898 goto bail;
5899 }
Mark Fasheh83418972007-04-23 18:53:12 -07005900
5901 ocfs2_extent_map_trunc(inode, new_highest_cpos);
5902
Mark Fashehccd979b2005-12-15 14:31:24 -08005903start:
Mark Fashehdcd05382007-01-16 11:32:23 -08005904 /*
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005905 * Check that we still have allocation to delete.
5906 */
5907 if (OCFS2_I(inode)->ip_clusters == 0) {
5908 status = 0;
5909 goto bail;
5910 }
5911
5912 /*
Mark Fashehdcd05382007-01-16 11:32:23 -08005913 * Truncate always works against the rightmost tree branch.
5914 */
5915 status = ocfs2_find_path(inode, path, UINT_MAX);
5916 if (status) {
5917 mlog_errno(status);
5918 goto bail;
Mark Fashehccd979b2005-12-15 14:31:24 -08005919 }
5920
Mark Fashehdcd05382007-01-16 11:32:23 -08005921 mlog(0, "inode->ip_clusters = %u, tree_depth = %u\n",
5922 OCFS2_I(inode)->ip_clusters, path->p_tree_depth);
5923
5924 /*
5925 * By now, el will point to the extent list on the bottom most
5926 * portion of this tree. Only the tail record is considered in
5927 * each pass.
5928 *
5929 * We handle the following cases, in order:
5930 * - empty extent: delete the remaining branch
5931 * - remove the entire record
5932 * - remove a partial record
5933 * - no record needs to be removed (truncate has completed)
5934 */
5935 el = path_leaf_el(path);
Mark Fasheh3a0782d2007-01-17 12:53:31 -08005936 if (le16_to_cpu(el->l_next_free_rec) == 0) {
5937 ocfs2_error(inode->i_sb,
5938 "Inode %llu has empty extent block at %llu\n",
5939 (unsigned long long)OCFS2_I(inode)->ip_blkno,
5940 (unsigned long long)path_leaf_bh(path)->b_blocknr);
5941 status = -EROFS;
5942 goto bail;
5943 }
5944
Mark Fashehccd979b2005-12-15 14:31:24 -08005945 i = le16_to_cpu(el->l_next_free_rec) - 1;
Mark Fashehdcd05382007-01-16 11:32:23 -08005946 range = le32_to_cpu(el->l_recs[i].e_cpos) +
Mark Fashehe48edee2007-03-07 16:46:57 -08005947 ocfs2_rec_clusters(el, &el->l_recs[i]);
Mark Fashehdcd05382007-01-16 11:32:23 -08005948 if (i == 0 && ocfs2_is_empty_extent(&el->l_recs[i])) {
5949 clusters_to_del = 0;
5950 } else if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_highest_cpos) {
Mark Fashehe48edee2007-03-07 16:46:57 -08005951 clusters_to_del = ocfs2_rec_clusters(el, &el->l_recs[i]);
Mark Fashehdcd05382007-01-16 11:32:23 -08005952 } else if (range > new_highest_cpos) {
Mark Fashehe48edee2007-03-07 16:46:57 -08005953 clusters_to_del = (ocfs2_rec_clusters(el, &el->l_recs[i]) +
Mark Fashehccd979b2005-12-15 14:31:24 -08005954 le32_to_cpu(el->l_recs[i].e_cpos)) -
Mark Fashehdcd05382007-01-16 11:32:23 -08005955 new_highest_cpos;
5956 } else {
5957 status = 0;
5958 goto bail;
5959 }
Mark Fashehccd979b2005-12-15 14:31:24 -08005960
Mark Fashehdcd05382007-01-16 11:32:23 -08005961 mlog(0, "clusters_to_del = %u in this pass, tail blk=%llu\n",
5962 clusters_to_del, (unsigned long long)path_leaf_bh(path)->b_blocknr);
5963
5964 BUG_ON(clusters_to_del == 0);
Mark Fashehccd979b2005-12-15 14:31:24 -08005965
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08005966 mutex_lock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08005967 tl_sem = 1;
5968 /* ocfs2_truncate_log_needs_flush guarantees us at least one
5969 * record is free for use. If there isn't any, we flush to get
5970 * an empty truncate log. */
5971 if (ocfs2_truncate_log_needs_flush(osb)) {
5972 status = __ocfs2_flush_truncate_log(osb);
5973 if (status < 0) {
5974 mlog_errno(status);
5975 goto bail;
5976 }
5977 }
5978
5979 credits = ocfs2_calc_tree_trunc_credits(osb->sb, clusters_to_del,
Mark Fashehdcd05382007-01-16 11:32:23 -08005980 (struct ocfs2_dinode *)fe_bh->b_data,
5981 el);
Mark Fasheh65eff9c2006-10-09 17:26:22 -07005982 handle = ocfs2_start_trans(osb, credits);
Mark Fashehccd979b2005-12-15 14:31:24 -08005983 if (IS_ERR(handle)) {
5984 status = PTR_ERR(handle);
5985 handle = NULL;
5986 mlog_errno(status);
5987 goto bail;
5988 }
5989
Mark Fashehdcd05382007-01-16 11:32:23 -08005990 status = ocfs2_do_truncate(osb, clusters_to_del, inode, fe_bh, handle,
5991 tc, path);
Mark Fashehccd979b2005-12-15 14:31:24 -08005992 if (status < 0) {
5993 mlog_errno(status);
5994 goto bail;
5995 }
5996
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08005997 mutex_unlock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08005998 tl_sem = 0;
5999
Mark Fasheh02dc1af2006-10-09 16:48:10 -07006000 ocfs2_commit_trans(osb, handle);
Mark Fashehccd979b2005-12-15 14:31:24 -08006001 handle = NULL;
6002
Mark Fashehdcd05382007-01-16 11:32:23 -08006003 ocfs2_reinit_path(path, 1);
6004
6005 /*
Mark Fasheh3a0782d2007-01-17 12:53:31 -08006006 * The check above will catch the case where we've truncated
6007 * away all allocation.
Mark Fashehdcd05382007-01-16 11:32:23 -08006008 */
Mark Fasheh3a0782d2007-01-17 12:53:31 -08006009 goto start;
6010
Mark Fashehccd979b2005-12-15 14:31:24 -08006011bail:
Mark Fashehccd979b2005-12-15 14:31:24 -08006012
6013 ocfs2_schedule_truncate_log_flush(osb, 1);
6014
6015 if (tl_sem)
Jes Sorensen1b1dcc12006-01-09 15:59:24 -08006016 mutex_unlock(&tl_inode->i_mutex);
Mark Fashehccd979b2005-12-15 14:31:24 -08006017
6018 if (handle)
Mark Fasheh02dc1af2006-10-09 16:48:10 -07006019 ocfs2_commit_trans(osb, handle);
Mark Fashehccd979b2005-12-15 14:31:24 -08006020
Mark Fasheh59a5e412007-06-22 15:52:36 -07006021 ocfs2_run_deallocs(osb, &tc->tc_dealloc);
6022
Mark Fashehdcd05382007-01-16 11:32:23 -08006023 ocfs2_free_path(path);
Mark Fashehccd979b2005-12-15 14:31:24 -08006024
6025 /* This will drop the ext_alloc cluster lock for us */
6026 ocfs2_free_truncate_context(tc);
6027
6028 mlog_exit(status);
6029 return status;
6030}
6031
Mark Fashehccd979b2005-12-15 14:31:24 -08006032/*
Mark Fasheh59a5e412007-06-22 15:52:36 -07006033 * Expects the inode to already be locked.
Mark Fashehccd979b2005-12-15 14:31:24 -08006034 */
6035int ocfs2_prepare_truncate(struct ocfs2_super *osb,
6036 struct inode *inode,
6037 struct buffer_head *fe_bh,
6038 struct ocfs2_truncate_context **tc)
6039{
Mark Fasheh59a5e412007-06-22 15:52:36 -07006040 int status;
Mark Fashehccd979b2005-12-15 14:31:24 -08006041 unsigned int new_i_clusters;
6042 struct ocfs2_dinode *fe;
6043 struct ocfs2_extent_block *eb;
Mark Fashehccd979b2005-12-15 14:31:24 -08006044 struct buffer_head *last_eb_bh = NULL;
Mark Fashehccd979b2005-12-15 14:31:24 -08006045
6046 mlog_entry_void();
6047
6048 *tc = NULL;
6049
6050 new_i_clusters = ocfs2_clusters_for_bytes(osb->sb,
6051 i_size_read(inode));
6052 fe = (struct ocfs2_dinode *) fe_bh->b_data;
6053
6054 mlog(0, "fe->i_clusters = %u, new_i_clusters = %u, fe->i_size ="
Mark Fasheh1ca1a112007-04-27 16:01:25 -07006055 "%llu\n", le32_to_cpu(fe->i_clusters), new_i_clusters,
6056 (unsigned long long)le64_to_cpu(fe->i_size));
Mark Fashehccd979b2005-12-15 14:31:24 -08006057
Robert P. J. Daycd861282006-12-13 00:34:52 -08006058 *tc = kzalloc(sizeof(struct ocfs2_truncate_context), GFP_KERNEL);
Mark Fashehccd979b2005-12-15 14:31:24 -08006059 if (!(*tc)) {
6060 status = -ENOMEM;
6061 mlog_errno(status);
6062 goto bail;
6063 }
Mark Fasheh59a5e412007-06-22 15:52:36 -07006064 ocfs2_init_dealloc_ctxt(&(*tc)->tc_dealloc);
Mark Fashehccd979b2005-12-15 14:31:24 -08006065
Mark Fashehccd979b2005-12-15 14:31:24 -08006066 if (fe->id2.i_list.l_tree_depth) {
Mark Fashehccd979b2005-12-15 14:31:24 -08006067 status = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk),
6068 &last_eb_bh, OCFS2_BH_CACHED, inode);
6069 if (status < 0) {
6070 mlog_errno(status);
6071 goto bail;
6072 }
6073 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
6074 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
6075 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb);
6076
6077 brelse(last_eb_bh);
6078 status = -EIO;
6079 goto bail;
6080 }
Mark Fashehccd979b2005-12-15 14:31:24 -08006081 }
6082
6083 (*tc)->tc_last_eb_bh = last_eb_bh;
6084
Mark Fashehccd979b2005-12-15 14:31:24 -08006085 status = 0;
6086bail:
6087 if (status < 0) {
6088 if (*tc)
6089 ocfs2_free_truncate_context(*tc);
6090 *tc = NULL;
6091 }
6092 mlog_exit_void();
6093 return status;
6094}
6095
6096static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc)
6097{
Mark Fasheh59a5e412007-06-22 15:52:36 -07006098 /*
6099 * The caller is responsible for completing deallocation
6100 * before freeing the context.
6101 */
6102 if (tc->tc_dealloc.c_first_suballocator != NULL)
6103 mlog(ML_NOTICE,
6104 "Truncate completion has non-empty dealloc context\n");
Mark Fashehccd979b2005-12-15 14:31:24 -08006105
6106 if (tc->tc_last_eb_bh)
6107 brelse(tc->tc_last_eb_bh);
6108
6109 kfree(tc);
6110}