Root/fs/btrfs/tree-log.c

1/*
2 * Copyright (C) 2008 Oracle. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18
19#include <linux/sched.h>
20#include <linux/slab.h>
21#include "ctree.h"
22#include "transaction.h"
23#include "disk-io.h"
24#include "locking.h"
25#include "print-tree.h"
26#include "compat.h"
27#include "tree-log.h"
28
29/* magic values for the inode_only field in btrfs_log_inode:
30 *
31 * LOG_INODE_ALL means to log everything
32 * LOG_INODE_EXISTS means to log just enough to recreate the inode
33 * during log replay
34 */
35#define LOG_INODE_ALL 0
36#define LOG_INODE_EXISTS 1
37
38/*
39 * directory trouble cases
40 *
41 * 1) on rename or unlink, if the inode being unlinked isn't in the fsync
42 * log, we must force a full commit before doing an fsync of the directory
43 * where the unlink was done.
44 * ---> record transid of last unlink/rename per directory
45 *
46 * mkdir foo/some_dir
47 * normal commit
48 * rename foo/some_dir foo2/some_dir
49 * mkdir foo/some_dir
50 * fsync foo/some_dir/some_file
51 *
52 * The fsync above will unlink the original some_dir without recording
53 * it in its new location (foo2). After a crash, some_dir will be gone
54 * unless the fsync of some_file forces a full commit
55 *
56 * 2) we must log any new names for any file or dir that is in the fsync
57 * log. ---> check inode while renaming/linking.
58 *
59 * 2a) we must log any new names for any file or dir during rename
60 * when the directory they are being removed from was logged.
61 * ---> check inode and old parent dir during rename
62 *
63 * 2a is actually the more important variant. With the extra logging
64 * a crash might unlink the old name without recreating the new one
65 *
66 * 3) after a crash, we must go through any directories with a link count
67 * of zero and redo the rm -rf
68 *
69 * mkdir f1/foo
70 * normal commit
71 * rm -rf f1/foo
72 * fsync(f1)
73 *
74 * The directory f1 was fully removed from the FS, but fsync was never
75 * called on f1, only its parent dir. After a crash the rm -rf must
76 * be replayed. This must be able to recurse down the entire
77 * directory tree. The inode link count fixup code takes care of the
78 * ugly details.
79 */
80
81/*
82 * stages for the tree walking. The first
83 * stage (0) is to only pin down the blocks we find
84 * the second stage (1) is to make sure that all the inodes
85 * we find in the log are created in the subvolume.
86 *
87 * The last stage is to deal with directories and links and extents
88 * and all the other fun semantics
89 */
90#define LOG_WALK_PIN_ONLY 0
91#define LOG_WALK_REPLAY_INODES 1
92#define LOG_WALK_REPLAY_ALL 2
93
94static int btrfs_log_inode(struct btrfs_trans_handle *trans,
95                 struct btrfs_root *root, struct inode *inode,
96                 int inode_only);
97static int link_to_fixup_dir(struct btrfs_trans_handle *trans,
98                 struct btrfs_root *root,
99                 struct btrfs_path *path, u64 objectid);
100static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
101                       struct btrfs_root *root,
102                       struct btrfs_root *log,
103                       struct btrfs_path *path,
104                       u64 dirid, int del_all);
105
106/*
107 * tree logging is a special write ahead log used to make sure that
108 * fsyncs and O_SYNCs can happen without doing full tree commits.
109 *
110 * Full tree commits are expensive because they require commonly
111 * modified blocks to be recowed, creating many dirty pages in the
112 * extent tree an 4x-6x higher write load than ext3.
113 *
114 * Instead of doing a tree commit on every fsync, we use the
115 * key ranges and transaction ids to find items for a given file or directory
116 * that have changed in this transaction. Those items are copied into
117 * a special tree (one per subvolume root), that tree is written to disk
118 * and then the fsync is considered complete.
119 *
120 * After a crash, items are copied out of the log-tree back into the
121 * subvolume tree. Any file data extents found are recorded in the extent
122 * allocation tree, and the log-tree freed.
123 *
124 * The log tree is read three times, once to pin down all the extents it is
125 * using in ram and once, once to create all the inodes logged in the tree
126 * and once to do all the other items.
127 */
128
129/*
130 * start a sub transaction and setup the log tree
131 * this increments the log tree writer count to make the people
132 * syncing the tree wait for us to finish
133 */
134static int start_log_trans(struct btrfs_trans_handle *trans,
135               struct btrfs_root *root)
136{
137    int ret;
138
139    mutex_lock(&root->log_mutex);
140    if (root->log_root) {
141        if (!root->log_start_pid) {
142            root->log_start_pid = current->pid;
143            root->log_multiple_pids = false;
144        } else if (root->log_start_pid != current->pid) {
145            root->log_multiple_pids = true;
146        }
147
148        root->log_batch++;
149        atomic_inc(&root->log_writers);
150        mutex_unlock(&root->log_mutex);
151        return 0;
152    }
153    root->log_multiple_pids = false;
154    root->log_start_pid = current->pid;
155    mutex_lock(&root->fs_info->tree_log_mutex);
156    if (!root->fs_info->log_root_tree) {
157        ret = btrfs_init_log_root_tree(trans, root->fs_info);
158        BUG_ON(ret);
159    }
160    if (!root->log_root) {
161        ret = btrfs_add_log_tree(trans, root);
162        BUG_ON(ret);
163    }
164    mutex_unlock(&root->fs_info->tree_log_mutex);
165    root->log_batch++;
166    atomic_inc(&root->log_writers);
167    mutex_unlock(&root->log_mutex);
168    return 0;
169}
170
171/*
172 * returns 0 if there was a log transaction running and we were able
173 * to join, or returns -ENOENT if there were not transactions
174 * in progress
175 */
176static int join_running_log_trans(struct btrfs_root *root)
177{
178    int ret = -ENOENT;
179
180    smp_mb();
181    if (!root->log_root)
182        return -ENOENT;
183
184    mutex_lock(&root->log_mutex);
185    if (root->log_root) {
186        ret = 0;
187        atomic_inc(&root->log_writers);
188    }
189    mutex_unlock(&root->log_mutex);
190    return ret;
191}
192
193/*
194 * This either makes the current running log transaction wait
195 * until you call btrfs_end_log_trans() or it makes any future
196 * log transactions wait until you call btrfs_end_log_trans()
197 */
198int btrfs_pin_log_trans(struct btrfs_root *root)
199{
200    int ret = -ENOENT;
201
202    mutex_lock(&root->log_mutex);
203    atomic_inc(&root->log_writers);
204    mutex_unlock(&root->log_mutex);
205    return ret;
206}
207
208/*
209 * indicate we're done making changes to the log tree
210 * and wake up anyone waiting to do a sync
211 */
212int btrfs_end_log_trans(struct btrfs_root *root)
213{
214    if (atomic_dec_and_test(&root->log_writers)) {
215        smp_mb();
216        if (waitqueue_active(&root->log_writer_wait))
217            wake_up(&root->log_writer_wait);
218    }
219    return 0;
220}
221
222
223/*
224 * the walk control struct is used to pass state down the chain when
225 * processing the log tree. The stage field tells us which part
226 * of the log tree processing we are currently doing. The others
227 * are state fields used for that specific part
228 */
229struct walk_control {
230    /* should we free the extent on disk when done? This is used
231     * at transaction commit time while freeing a log tree
232     */
233    int free;
234
235    /* should we write out the extent buffer? This is used
236     * while flushing the log tree to disk during a sync
237     */
238    int write;
239
240    /* should we wait for the extent buffer io to finish? Also used
241     * while flushing the log tree to disk for a sync
242     */
243    int wait;
244
245    /* pin only walk, we record which extents on disk belong to the
246     * log trees
247     */
248    int pin;
249
250    /* what stage of the replay code we're currently in */
251    int stage;
252
253    /* the root we are currently replaying */
254    struct btrfs_root *replay_dest;
255
256    /* the trans handle for the current replay */
257    struct btrfs_trans_handle *trans;
258
259    /* the function that gets used to process blocks we find in the
260     * tree. Note the extent_buffer might not be up to date when it is
261     * passed in, and it must be checked or read if you need the data
262     * inside it
263     */
264    int (*process_func)(struct btrfs_root *log, struct extent_buffer *eb,
265                struct walk_control *wc, u64 gen);
266};
267
268/*
269 * process_func used to pin down extents, write them or wait on them
270 */
271static int process_one_buffer(struct btrfs_root *log,
272                  struct extent_buffer *eb,
273                  struct walk_control *wc, u64 gen)
274{
275    if (wc->pin)
276        btrfs_pin_extent(log->fs_info->extent_root,
277                 eb->start, eb->len, 0);
278
279    if (btrfs_buffer_uptodate(eb, gen)) {
280        if (wc->write)
281            btrfs_write_tree_block(eb);
282        if (wc->wait)
283            btrfs_wait_tree_block_writeback(eb);
284    }
285    return 0;
286}
287
288/*
289 * Item overwrite used by replay and tree logging. eb, slot and key all refer
290 * to the src data we are copying out.
291 *
292 * root is the tree we are copying into, and path is a scratch
293 * path for use in this function (it should be released on entry and
294 * will be released on exit).
295 *
296 * If the key is already in the destination tree the existing item is
297 * overwritten. If the existing item isn't big enough, it is extended.
298 * If it is too large, it is truncated.
299 *
300 * If the key isn't in the destination yet, a new item is inserted.
301 */
302static noinline int overwrite_item(struct btrfs_trans_handle *trans,
303                   struct btrfs_root *root,
304                   struct btrfs_path *path,
305                   struct extent_buffer *eb, int slot,
306                   struct btrfs_key *key)
307{
308    int ret;
309    u32 item_size;
310    u64 saved_i_size = 0;
311    int save_old_i_size = 0;
312    unsigned long src_ptr;
313    unsigned long dst_ptr;
314    int overwrite_root = 0;
315
316    if (root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
317        overwrite_root = 1;
318
319    item_size = btrfs_item_size_nr(eb, slot);
320    src_ptr = btrfs_item_ptr_offset(eb, slot);
321
322    /* look for the key in the destination tree */
323    ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
324    if (ret == 0) {
325        char *src_copy;
326        char *dst_copy;
327        u32 dst_size = btrfs_item_size_nr(path->nodes[0],
328                          path->slots[0]);
329        if (dst_size != item_size)
330            goto insert;
331
332        if (item_size == 0) {
333            btrfs_release_path(root, path);
334            return 0;
335        }
336        dst_copy = kmalloc(item_size, GFP_NOFS);
337        src_copy = kmalloc(item_size, GFP_NOFS);
338
339        read_extent_buffer(eb, src_copy, src_ptr, item_size);
340
341        dst_ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
342        read_extent_buffer(path->nodes[0], dst_copy, dst_ptr,
343                   item_size);
344        ret = memcmp(dst_copy, src_copy, item_size);
345
346        kfree(dst_copy);
347        kfree(src_copy);
348        /*
349         * they have the same contents, just return, this saves
350         * us from cowing blocks in the destination tree and doing
351         * extra writes that may not have been done by a previous
352         * sync
353         */
354        if (ret == 0) {
355            btrfs_release_path(root, path);
356            return 0;
357        }
358
359    }
360insert:
361    btrfs_release_path(root, path);
362    /* try to insert the key into the destination tree */
363    ret = btrfs_insert_empty_item(trans, root, path,
364                      key, item_size);
365
366    /* make sure any existing item is the correct size */
367    if (ret == -EEXIST) {
368        u32 found_size;
369        found_size = btrfs_item_size_nr(path->nodes[0],
370                        path->slots[0]);
371        if (found_size > item_size) {
372            btrfs_truncate_item(trans, root, path, item_size, 1);
373        } else if (found_size < item_size) {
374            ret = btrfs_extend_item(trans, root, path,
375                        item_size - found_size);
376            BUG_ON(ret);
377        }
378    } else if (ret) {
379        BUG();
380    }
381    dst_ptr = btrfs_item_ptr_offset(path->nodes[0],
382                    path->slots[0]);
383
384    /* don't overwrite an existing inode if the generation number
385     * was logged as zero. This is done when the tree logging code
386     * is just logging an inode to make sure it exists after recovery.
387     *
388     * Also, don't overwrite i_size on directories during replay.
389     * log replay inserts and removes directory items based on the
390     * state of the tree found in the subvolume, and i_size is modified
391     * as it goes
392     */
393    if (key->type == BTRFS_INODE_ITEM_KEY && ret == -EEXIST) {
394        struct btrfs_inode_item *src_item;
395        struct btrfs_inode_item *dst_item;
396
397        src_item = (struct btrfs_inode_item *)src_ptr;
398        dst_item = (struct btrfs_inode_item *)dst_ptr;
399
400        if (btrfs_inode_generation(eb, src_item) == 0)
401            goto no_copy;
402
403        if (overwrite_root &&
404            S_ISDIR(btrfs_inode_mode(eb, src_item)) &&
405            S_ISDIR(btrfs_inode_mode(path->nodes[0], dst_item))) {
406            save_old_i_size = 1;
407            saved_i_size = btrfs_inode_size(path->nodes[0],
408                            dst_item);
409        }
410    }
411
412    copy_extent_buffer(path->nodes[0], eb, dst_ptr,
413               src_ptr, item_size);
414
415    if (save_old_i_size) {
416        struct btrfs_inode_item *dst_item;
417        dst_item = (struct btrfs_inode_item *)dst_ptr;
418        btrfs_set_inode_size(path->nodes[0], dst_item, saved_i_size);
419    }
420
421    /* make sure the generation is filled in */
422    if (key->type == BTRFS_INODE_ITEM_KEY) {
423        struct btrfs_inode_item *dst_item;
424        dst_item = (struct btrfs_inode_item *)dst_ptr;
425        if (btrfs_inode_generation(path->nodes[0], dst_item) == 0) {
426            btrfs_set_inode_generation(path->nodes[0], dst_item,
427                           trans->transid);
428        }
429    }
430no_copy:
431    btrfs_mark_buffer_dirty(path->nodes[0]);
432    btrfs_release_path(root, path);
433    return 0;
434}
435
436/*
437 * simple helper to read an inode off the disk from a given root
438 * This can only be called for subvolume roots and not for the log
439 */
440static noinline struct inode *read_one_inode(struct btrfs_root *root,
441                         u64 objectid)
442{
443    struct btrfs_key key;
444    struct inode *inode;
445
446    key.objectid = objectid;
447    key.type = BTRFS_INODE_ITEM_KEY;
448    key.offset = 0;
449    inode = btrfs_iget(root->fs_info->sb, &key, root, NULL);
450    if (IS_ERR(inode)) {
451        inode = NULL;
452    } else if (is_bad_inode(inode)) {
453        iput(inode);
454        inode = NULL;
455    }
456    return inode;
457}
458
459/* replays a single extent in 'eb' at 'slot' with 'key' into the
460 * subvolume 'root'. path is released on entry and should be released
461 * on exit.
462 *
463 * extents in the log tree have not been allocated out of the extent
464 * tree yet. So, this completes the allocation, taking a reference
465 * as required if the extent already exists or creating a new extent
466 * if it isn't in the extent allocation tree yet.
467 *
468 * The extent is inserted into the file, dropping any existing extents
469 * from the file that overlap the new one.
470 */
471static noinline int replay_one_extent(struct btrfs_trans_handle *trans,
472                      struct btrfs_root *root,
473                      struct btrfs_path *path,
474                      struct extent_buffer *eb, int slot,
475                      struct btrfs_key *key)
476{
477    int found_type;
478    u64 mask = root->sectorsize - 1;
479    u64 extent_end;
480    u64 alloc_hint;
481    u64 start = key->offset;
482    u64 saved_nbytes;
483    struct btrfs_file_extent_item *item;
484    struct inode *inode = NULL;
485    unsigned long size;
486    int ret = 0;
487
488    item = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
489    found_type = btrfs_file_extent_type(eb, item);
490
491    if (found_type == BTRFS_FILE_EXTENT_REG ||
492        found_type == BTRFS_FILE_EXTENT_PREALLOC)
493        extent_end = start + btrfs_file_extent_num_bytes(eb, item);
494    else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
495        size = btrfs_file_extent_inline_len(eb, item);
496        extent_end = (start + size + mask) & ~mask;
497    } else {
498        ret = 0;
499        goto out;
500    }
501
502    inode = read_one_inode(root, key->objectid);
503    if (!inode) {
504        ret = -EIO;
505        goto out;
506    }
507
508    /*
509     * first check to see if we already have this extent in the
510     * file. This must be done before the btrfs_drop_extents run
511     * so we don't try to drop this extent.
512     */
513    ret = btrfs_lookup_file_extent(trans, root, path, inode->i_ino,
514                       start, 0);
515
516    if (ret == 0 &&
517        (found_type == BTRFS_FILE_EXTENT_REG ||
518         found_type == BTRFS_FILE_EXTENT_PREALLOC)) {
519        struct btrfs_file_extent_item cmp1;
520        struct btrfs_file_extent_item cmp2;
521        struct btrfs_file_extent_item *existing;
522        struct extent_buffer *leaf;
523
524        leaf = path->nodes[0];
525        existing = btrfs_item_ptr(leaf, path->slots[0],
526                      struct btrfs_file_extent_item);
527
528        read_extent_buffer(eb, &cmp1, (unsigned long)item,
529                   sizeof(cmp1));
530        read_extent_buffer(leaf, &cmp2, (unsigned long)existing,
531                   sizeof(cmp2));
532
533        /*
534         * we already have a pointer to this exact extent,
535         * we don't have to do anything
536         */
537        if (memcmp(&cmp1, &cmp2, sizeof(cmp1)) == 0) {
538            btrfs_release_path(root, path);
539            goto out;
540        }
541    }
542    btrfs_release_path(root, path);
543
544    saved_nbytes = inode_get_bytes(inode);
545    /* drop any overlapping extents */
546    ret = btrfs_drop_extents(trans, inode, start, extent_end,
547                 &alloc_hint, 1);
548    BUG_ON(ret);
549
550    if (found_type == BTRFS_FILE_EXTENT_REG ||
551        found_type == BTRFS_FILE_EXTENT_PREALLOC) {
552        u64 offset;
553        unsigned long dest_offset;
554        struct btrfs_key ins;
555
556        ret = btrfs_insert_empty_item(trans, root, path, key,
557                          sizeof(*item));
558        BUG_ON(ret);
559        dest_offset = btrfs_item_ptr_offset(path->nodes[0],
560                            path->slots[0]);
561        copy_extent_buffer(path->nodes[0], eb, dest_offset,
562                (unsigned long)item, sizeof(*item));
563
564        ins.objectid = btrfs_file_extent_disk_bytenr(eb, item);
565        ins.offset = btrfs_file_extent_disk_num_bytes(eb, item);
566        ins.type = BTRFS_EXTENT_ITEM_KEY;
567        offset = key->offset - btrfs_file_extent_offset(eb, item);
568
569        if (ins.objectid > 0) {
570            u64 csum_start;
571            u64 csum_end;
572            LIST_HEAD(ordered_sums);
573            /*
574             * is this extent already allocated in the extent
575             * allocation tree? If so, just add a reference
576             */
577            ret = btrfs_lookup_extent(root, ins.objectid,
578                        ins.offset);
579            if (ret == 0) {
580                ret = btrfs_inc_extent_ref(trans, root,
581                        ins.objectid, ins.offset,
582                        0, root->root_key.objectid,
583                        key->objectid, offset);
584            } else {
585                /*
586                 * insert the extent pointer in the extent
587                 * allocation tree
588                 */
589                ret = btrfs_alloc_logged_file_extent(trans,
590                        root, root->root_key.objectid,
591                        key->objectid, offset, &ins);
592                BUG_ON(ret);
593            }
594            btrfs_release_path(root, path);
595
596            if (btrfs_file_extent_compression(eb, item)) {
597                csum_start = ins.objectid;
598                csum_end = csum_start + ins.offset;
599            } else {
600                csum_start = ins.objectid +
601                    btrfs_file_extent_offset(eb, item);
602                csum_end = csum_start +
603                    btrfs_file_extent_num_bytes(eb, item);
604            }
605
606            ret = btrfs_lookup_csums_range(root->log_root,
607                        csum_start, csum_end - 1,
608                        &ordered_sums);
609            BUG_ON(ret);
610            while (!list_empty(&ordered_sums)) {
611                struct btrfs_ordered_sum *sums;
612                sums = list_entry(ordered_sums.next,
613                        struct btrfs_ordered_sum,
614                        list);
615                ret = btrfs_csum_file_blocks(trans,
616                        root->fs_info->csum_root,
617                        sums);
618                BUG_ON(ret);
619                list_del(&sums->list);
620                kfree(sums);
621            }
622        } else {
623            btrfs_release_path(root, path);
624        }
625    } else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
626        /* inline extents are easy, we just overwrite them */
627        ret = overwrite_item(trans, root, path, eb, slot, key);
628        BUG_ON(ret);
629    }
630
631    inode_set_bytes(inode, saved_nbytes);
632    btrfs_update_inode(trans, root, inode);
633out:
634    if (inode)
635        iput(inode);
636    return ret;
637}
638
639/*
640 * when cleaning up conflicts between the directory names in the
641 * subvolume, directory names in the log and directory names in the
642 * inode back references, we may have to unlink inodes from directories.
643 *
644 * This is a helper function to do the unlink of a specific directory
645 * item
646 */
647static noinline int drop_one_dir_item(struct btrfs_trans_handle *trans,
648                      struct btrfs_root *root,
649                      struct btrfs_path *path,
650                      struct inode *dir,
651                      struct btrfs_dir_item *di)
652{
653    struct inode *inode;
654    char *name;
655    int name_len;
656    struct extent_buffer *leaf;
657    struct btrfs_key location;
658    int ret;
659
660    leaf = path->nodes[0];
661
662    btrfs_dir_item_key_to_cpu(leaf, di, &location);
663    name_len = btrfs_dir_name_len(leaf, di);
664    name = kmalloc(name_len, GFP_NOFS);
665    read_extent_buffer(leaf, name, (unsigned long)(di + 1), name_len);
666    btrfs_release_path(root, path);
667
668    inode = read_one_inode(root, location.objectid);
669    BUG_ON(!inode);
670
671    ret = link_to_fixup_dir(trans, root, path, location.objectid);
672    BUG_ON(ret);
673
674    ret = btrfs_unlink_inode(trans, root, dir, inode, name, name_len);
675    BUG_ON(ret);
676    kfree(name);
677
678    iput(inode);
679    return ret;
680}
681
682/*
683 * helper function to see if a given name and sequence number found
684 * in an inode back reference are already in a directory and correctly
685 * point to this inode
686 */
687static noinline int inode_in_dir(struct btrfs_root *root,
688                 struct btrfs_path *path,
689                 u64 dirid, u64 objectid, u64 index,
690                 const char *name, int name_len)
691{
692    struct btrfs_dir_item *di;
693    struct btrfs_key location;
694    int match = 0;
695
696    di = btrfs_lookup_dir_index_item(NULL, root, path, dirid,
697                     index, name, name_len, 0);
698    if (di && !IS_ERR(di)) {
699        btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
700        if (location.objectid != objectid)
701            goto out;
702    } else
703        goto out;
704    btrfs_release_path(root, path);
705
706    di = btrfs_lookup_dir_item(NULL, root, path, dirid, name, name_len, 0);
707    if (di && !IS_ERR(di)) {
708        btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
709        if (location.objectid != objectid)
710            goto out;
711    } else
712        goto out;
713    match = 1;
714out:
715    btrfs_release_path(root, path);
716    return match;
717}
718
719/*
720 * helper function to check a log tree for a named back reference in
721 * an inode. This is used to decide if a back reference that is
722 * found in the subvolume conflicts with what we find in the log.
723 *
724 * inode backreferences may have multiple refs in a single item,
725 * during replay we process one reference at a time, and we don't
726 * want to delete valid links to a file from the subvolume if that
727 * link is also in the log.
728 */
729static noinline int backref_in_log(struct btrfs_root *log,
730                   struct btrfs_key *key,
731                   char *name, int namelen)
732{
733    struct btrfs_path *path;
734    struct btrfs_inode_ref *ref;
735    unsigned long ptr;
736    unsigned long ptr_end;
737    unsigned long name_ptr;
738    int found_name_len;
739    int item_size;
740    int ret;
741    int match = 0;
742
743    path = btrfs_alloc_path();
744    ret = btrfs_search_slot(NULL, log, key, path, 0, 0);
745    if (ret != 0)
746        goto out;
747
748    item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
749    ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
750    ptr_end = ptr + item_size;
751    while (ptr < ptr_end) {
752        ref = (struct btrfs_inode_ref *)ptr;
753        found_name_len = btrfs_inode_ref_name_len(path->nodes[0], ref);
754        if (found_name_len == namelen) {
755            name_ptr = (unsigned long)(ref + 1);
756            ret = memcmp_extent_buffer(path->nodes[0], name,
757                           name_ptr, namelen);
758            if (ret == 0) {
759                match = 1;
760                goto out;
761            }
762        }
763        ptr = (unsigned long)(ref + 1) + found_name_len;
764    }
765out:
766    btrfs_free_path(path);
767    return match;
768}
769
770
771/*
772 * replay one inode back reference item found in the log tree.
773 * eb, slot and key refer to the buffer and key found in the log tree.
774 * root is the destination we are replaying into, and path is for temp
775 * use by this function. (it should be released on return).
776 */
777static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
778                  struct btrfs_root *root,
779                  struct btrfs_root *log,
780                  struct btrfs_path *path,
781                  struct extent_buffer *eb, int slot,
782                  struct btrfs_key *key)
783{
784    struct inode *dir;
785    int ret;
786    struct btrfs_key location;
787    struct btrfs_inode_ref *ref;
788    struct btrfs_dir_item *di;
789    struct inode *inode;
790    char *name;
791    int namelen;
792    unsigned long ref_ptr;
793    unsigned long ref_end;
794
795    location.objectid = key->objectid;
796    location.type = BTRFS_INODE_ITEM_KEY;
797    location.offset = 0;
798
799    /*
800     * it is possible that we didn't log all the parent directories
801     * for a given inode. If we don't find the dir, just don't
802     * copy the back ref in. The link count fixup code will take
803     * care of the rest
804     */
805    dir = read_one_inode(root, key->offset);
806    if (!dir)
807        return -ENOENT;
808
809    inode = read_one_inode(root, key->objectid);
810    BUG_ON(!inode);
811
812    ref_ptr = btrfs_item_ptr_offset(eb, slot);
813    ref_end = ref_ptr + btrfs_item_size_nr(eb, slot);
814
815again:
816    ref = (struct btrfs_inode_ref *)ref_ptr;
817
818    namelen = btrfs_inode_ref_name_len(eb, ref);
819    name = kmalloc(namelen, GFP_NOFS);
820    BUG_ON(!name);
821
822    read_extent_buffer(eb, name, (unsigned long)(ref + 1), namelen);
823
824    /* if we already have a perfect match, we're done */
825    if (inode_in_dir(root, path, dir->i_ino, inode->i_ino,
826             btrfs_inode_ref_index(eb, ref),
827             name, namelen)) {
828        goto out;
829    }
830
831    /*
832     * look for a conflicting back reference in the metadata.
833     * if we find one we have to unlink that name of the file
834     * before we add our new link. Later on, we overwrite any
835     * existing back reference, and we don't want to create
836     * dangling pointers in the directory.
837     */
838conflict_again:
839    ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
840    if (ret == 0) {
841        char *victim_name;
842        int victim_name_len;
843        struct btrfs_inode_ref *victim_ref;
844        unsigned long ptr;
845        unsigned long ptr_end;
846        struct extent_buffer *leaf = path->nodes[0];
847
848        /* are we trying to overwrite a back ref for the root directory
849         * if so, just jump out, we're done
850         */
851        if (key->objectid == key->offset)
852            goto out_nowrite;
853
854        /* check all the names in this back reference to see
855         * if they are in the log. if so, we allow them to stay
856         * otherwise they must be unlinked as a conflict
857         */
858        ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
859        ptr_end = ptr + btrfs_item_size_nr(leaf, path->slots[0]);
860        while (ptr < ptr_end) {
861            victim_ref = (struct btrfs_inode_ref *)ptr;
862            victim_name_len = btrfs_inode_ref_name_len(leaf,
863                                   victim_ref);
864            victim_name = kmalloc(victim_name_len, GFP_NOFS);
865            BUG_ON(!victim_name);
866
867            read_extent_buffer(leaf, victim_name,
868                       (unsigned long)(victim_ref + 1),
869                       victim_name_len);
870
871            if (!backref_in_log(log, key, victim_name,
872                        victim_name_len)) {
873                btrfs_inc_nlink(inode);
874                btrfs_release_path(root, path);
875
876                ret = btrfs_unlink_inode(trans, root, dir,
877                             inode, victim_name,
878                             victim_name_len);
879                kfree(victim_name);
880                btrfs_release_path(root, path);
881                goto conflict_again;
882            }
883            kfree(victim_name);
884            ptr = (unsigned long)(victim_ref + 1) + victim_name_len;
885        }
886        BUG_ON(ret);
887    }
888    btrfs_release_path(root, path);
889
890    /* look for a conflicting sequence number */
891    di = btrfs_lookup_dir_index_item(trans, root, path, dir->i_ino,
892                     btrfs_inode_ref_index(eb, ref),
893                     name, namelen, 0);
894    if (di && !IS_ERR(di)) {
895        ret = drop_one_dir_item(trans, root, path, dir, di);
896        BUG_ON(ret);
897    }
898    btrfs_release_path(root, path);
899
900
901    /* look for a conflicting name */
902    di = btrfs_lookup_dir_item(trans, root, path, dir->i_ino,
903                   name, namelen, 0);
904    if (di && !IS_ERR(di)) {
905        ret = drop_one_dir_item(trans, root, path, dir, di);
906        BUG_ON(ret);
907    }
908    btrfs_release_path(root, path);
909
910    /* insert our name */
911    ret = btrfs_add_link(trans, dir, inode, name, namelen, 0,
912                 btrfs_inode_ref_index(eb, ref));
913    BUG_ON(ret);
914
915    btrfs_update_inode(trans, root, inode);
916
917out:
918    ref_ptr = (unsigned long)(ref + 1) + namelen;
919    kfree(name);
920    if (ref_ptr < ref_end)
921        goto again;
922
923    /* finally write the back reference in the inode */
924    ret = overwrite_item(trans, root, path, eb, slot, key);
925    BUG_ON(ret);
926
927out_nowrite:
928    btrfs_release_path(root, path);
929    iput(dir);
930    iput(inode);
931    return 0;
932}
933
934static int insert_orphan_item(struct btrfs_trans_handle *trans,
935                  struct btrfs_root *root, u64 offset)
936{
937    int ret;
938    ret = btrfs_find_orphan_item(root, offset);
939    if (ret > 0)
940        ret = btrfs_insert_orphan_item(trans, root, offset);
941    return ret;
942}
943
944
945/*
946 * There are a few corners where the link count of the file can't
947 * be properly maintained during replay. So, instead of adding
948 * lots of complexity to the log code, we just scan the backrefs
949 * for any file that has been through replay.
950 *
951 * The scan will update the link count on the inode to reflect the
952 * number of back refs found. If it goes down to zero, the iput
953 * will free the inode.
954 */
955static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
956                       struct btrfs_root *root,
957                       struct inode *inode)
958{
959    struct btrfs_path *path;
960    int ret;
961    struct btrfs_key key;
962    u64 nlink = 0;
963    unsigned long ptr;
964    unsigned long ptr_end;
965    int name_len;
966
967    key.objectid = inode->i_ino;
968    key.type = BTRFS_INODE_REF_KEY;
969    key.offset = (u64)-1;
970
971    path = btrfs_alloc_path();
972
973    while (1) {
974        ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
975        if (ret < 0)
976            break;
977        if (ret > 0) {
978            if (path->slots[0] == 0)
979                break;
980            path->slots[0]--;
981        }
982        btrfs_item_key_to_cpu(path->nodes[0], &key,
983                      path->slots[0]);
984        if (key.objectid != inode->i_ino ||
985            key.type != BTRFS_INODE_REF_KEY)
986            break;
987        ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
988        ptr_end = ptr + btrfs_item_size_nr(path->nodes[0],
989                           path->slots[0]);
990        while (ptr < ptr_end) {
991            struct btrfs_inode_ref *ref;
992
993            ref = (struct btrfs_inode_ref *)ptr;
994            name_len = btrfs_inode_ref_name_len(path->nodes[0],
995                                ref);
996            ptr = (unsigned long)(ref + 1) + name_len;
997            nlink++;
998        }
999
1000        if (key.offset == 0)
1001            break;
1002        key.offset--;
1003        btrfs_release_path(root, path);
1004    }
1005    btrfs_release_path(root, path);
1006    if (nlink != inode->i_nlink) {
1007        inode->i_nlink = nlink;
1008        btrfs_update_inode(trans, root, inode);
1009    }
1010    BTRFS_I(inode)->index_cnt = (u64)-1;
1011
1012    if (inode->i_nlink == 0) {
1013        if (S_ISDIR(inode->i_mode)) {
1014            ret = replay_dir_deletes(trans, root, NULL, path,
1015                         inode->i_ino, 1);
1016            BUG_ON(ret);
1017        }
1018        ret = insert_orphan_item(trans, root, inode->i_ino);
1019        BUG_ON(ret);
1020    }
1021    btrfs_free_path(path);
1022
1023    return 0;
1024}
1025
1026static noinline int fixup_inode_link_counts(struct btrfs_trans_handle *trans,
1027                        struct btrfs_root *root,
1028                        struct btrfs_path *path)
1029{
1030    int ret;
1031    struct btrfs_key key;
1032    struct inode *inode;
1033
1034    key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1035    key.type = BTRFS_ORPHAN_ITEM_KEY;
1036    key.offset = (u64)-1;
1037    while (1) {
1038        ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1039        if (ret < 0)
1040            break;
1041
1042        if (ret == 1) {
1043            if (path->slots[0] == 0)
1044                break;
1045            path->slots[0]--;
1046        }
1047
1048        btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1049        if (key.objectid != BTRFS_TREE_LOG_FIXUP_OBJECTID ||
1050            key.type != BTRFS_ORPHAN_ITEM_KEY)
1051            break;
1052
1053        ret = btrfs_del_item(trans, root, path);
1054        BUG_ON(ret);
1055
1056        btrfs_release_path(root, path);
1057        inode = read_one_inode(root, key.offset);
1058        BUG_ON(!inode);
1059
1060        ret = fixup_inode_link_count(trans, root, inode);
1061        BUG_ON(ret);
1062
1063        iput(inode);
1064
1065        /*
1066         * fixup on a directory may create new entries,
1067         * make sure we always look for the highset possible
1068         * offset
1069         */
1070        key.offset = (u64)-1;
1071    }
1072    btrfs_release_path(root, path);
1073    return 0;
1074}
1075
1076
1077/*
1078 * record a given inode in the fixup dir so we can check its link
1079 * count when replay is done. The link count is incremented here
1080 * so the inode won't go away until we check it
1081 */
1082static noinline int link_to_fixup_dir(struct btrfs_trans_handle *trans,
1083                      struct btrfs_root *root,
1084                      struct btrfs_path *path,
1085                      u64 objectid)
1086{
1087    struct btrfs_key key;
1088    int ret = 0;
1089    struct inode *inode;
1090
1091    inode = read_one_inode(root, objectid);
1092    BUG_ON(!inode);
1093
1094    key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1095    btrfs_set_key_type(&key, BTRFS_ORPHAN_ITEM_KEY);
1096    key.offset = objectid;
1097
1098    ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
1099
1100    btrfs_release_path(root, path);
1101    if (ret == 0) {
1102        btrfs_inc_nlink(inode);
1103        btrfs_update_inode(trans, root, inode);
1104    } else if (ret == -EEXIST) {
1105        ret = 0;
1106    } else {
1107        BUG();
1108    }
1109    iput(inode);
1110
1111    return ret;
1112}
1113
1114/*
1115 * when replaying the log for a directory, we only insert names
1116 * for inodes that actually exist. This means an fsync on a directory
1117 * does not implicitly fsync all the new files in it
1118 */
1119static noinline int insert_one_name(struct btrfs_trans_handle *trans,
1120                    struct btrfs_root *root,
1121                    struct btrfs_path *path,
1122                    u64 dirid, u64 index,
1123                    char *name, int name_len, u8 type,
1124                    struct btrfs_key *location)
1125{
1126    struct inode *inode;
1127    struct inode *dir;
1128    int ret;
1129
1130    inode = read_one_inode(root, location->objectid);
1131    if (!inode)
1132        return -ENOENT;
1133
1134    dir = read_one_inode(root, dirid);
1135    if (!dir) {
1136        iput(inode);
1137        return -EIO;
1138    }
1139    ret = btrfs_add_link(trans, dir, inode, name, name_len, 1, index);
1140
1141    /* FIXME, put inode into FIXUP list */
1142
1143    iput(inode);
1144    iput(dir);
1145    return ret;
1146}
1147
1148/*
1149 * take a single entry in a log directory item and replay it into
1150 * the subvolume.
1151 *
1152 * if a conflicting item exists in the subdirectory already,
1153 * the inode it points to is unlinked and put into the link count
1154 * fix up tree.
1155 *
1156 * If a name from the log points to a file or directory that does
1157 * not exist in the FS, it is skipped. fsyncs on directories
1158 * do not force down inodes inside that directory, just changes to the
1159 * names or unlinks in a directory.
1160 */
1161static noinline int replay_one_name(struct btrfs_trans_handle *trans,
1162                    struct btrfs_root *root,
1163                    struct btrfs_path *path,
1164                    struct extent_buffer *eb,
1165                    struct btrfs_dir_item *di,
1166                    struct btrfs_key *key)
1167{
1168    char *name;
1169    int name_len;
1170    struct btrfs_dir_item *dst_di;
1171    struct btrfs_key found_key;
1172    struct btrfs_key log_key;
1173    struct inode *dir;
1174    u8 log_type;
1175    int exists;
1176    int ret;
1177
1178    dir = read_one_inode(root, key->objectid);
1179    BUG_ON(!dir);
1180
1181    name_len = btrfs_dir_name_len(eb, di);
1182    name = kmalloc(name_len, GFP_NOFS);
1183    log_type = btrfs_dir_type(eb, di);
1184    read_extent_buffer(eb, name, (unsigned long)(di + 1),
1185           name_len);
1186
1187    btrfs_dir_item_key_to_cpu(eb, di, &log_key);
1188    exists = btrfs_lookup_inode(trans, root, path, &log_key, 0);
1189    if (exists == 0)
1190        exists = 1;
1191    else
1192        exists = 0;
1193    btrfs_release_path(root, path);
1194
1195    if (key->type == BTRFS_DIR_ITEM_KEY) {
1196        dst_di = btrfs_lookup_dir_item(trans, root, path, key->objectid,
1197                       name, name_len, 1);
1198    } else if (key->type == BTRFS_DIR_INDEX_KEY) {
1199        dst_di = btrfs_lookup_dir_index_item(trans, root, path,
1200                             key->objectid,
1201                             key->offset, name,
1202                             name_len, 1);
1203    } else {
1204        BUG();
1205    }
1206    if (!dst_di || IS_ERR(dst_di)) {
1207        /* we need a sequence number to insert, so we only
1208         * do inserts for the BTRFS_DIR_INDEX_KEY types
1209         */
1210        if (key->type != BTRFS_DIR_INDEX_KEY)
1211            goto out;
1212        goto insert;
1213    }
1214
1215    btrfs_dir_item_key_to_cpu(path->nodes[0], dst_di, &found_key);
1216    /* the existing item matches the logged item */
1217    if (found_key.objectid == log_key.objectid &&
1218        found_key.type == log_key.type &&
1219        found_key.offset == log_key.offset &&
1220        btrfs_dir_type(path->nodes[0], dst_di) == log_type) {
1221        goto out;
1222    }
1223
1224    /*
1225     * don't drop the conflicting directory entry if the inode
1226     * for the new entry doesn't exist
1227     */
1228    if (!exists)
1229        goto out;
1230
1231    ret = drop_one_dir_item(trans, root, path, dir, dst_di);
1232    BUG_ON(ret);
1233
1234    if (key->type == BTRFS_DIR_INDEX_KEY)
1235        goto insert;
1236out:
1237    btrfs_release_path(root, path);
1238    kfree(name);
1239    iput(dir);
1240    return 0;
1241
1242insert:
1243    btrfs_release_path(root, path);
1244    ret = insert_one_name(trans, root, path, key->objectid, key->offset,
1245                  name, name_len, log_type, &log_key);
1246
1247    BUG_ON(ret && ret != -ENOENT);
1248    goto out;
1249}
1250
1251/*
1252 * find all the names in a directory item and reconcile them into
1253 * the subvolume. Only BTRFS_DIR_ITEM_KEY types will have more than
1254 * one name in a directory item, but the same code gets used for
1255 * both directory index types
1256 */
1257static noinline int replay_one_dir_item(struct btrfs_trans_handle *trans,
1258                    struct btrfs_root *root,
1259                    struct btrfs_path *path,
1260                    struct extent_buffer *eb, int slot,
1261                    struct btrfs_key *key)
1262{
1263    int ret;
1264    u32 item_size = btrfs_item_size_nr(eb, slot);
1265    struct btrfs_dir_item *di;
1266    int name_len;
1267    unsigned long ptr;
1268    unsigned long ptr_end;
1269
1270    ptr = btrfs_item_ptr_offset(eb, slot);
1271    ptr_end = ptr + item_size;
1272    while (ptr < ptr_end) {
1273        di = (struct btrfs_dir_item *)ptr;
1274        name_len = btrfs_dir_name_len(eb, di);
1275        ret = replay_one_name(trans, root, path, eb, di, key);
1276        BUG_ON(ret);
1277        ptr = (unsigned long)(di + 1);
1278        ptr += name_len;
1279    }
1280    return 0;
1281}
1282
1283/*
1284 * directory replay has two parts. There are the standard directory
1285 * items in the log copied from the subvolume, and range items
1286 * created in the log while the subvolume was logged.
1287 *
1288 * The range items tell us which parts of the key space the log
1289 * is authoritative for. During replay, if a key in the subvolume
1290 * directory is in a logged range item, but not actually in the log
1291 * that means it was deleted from the directory before the fsync
1292 * and should be removed.
1293 */
1294static noinline int find_dir_range(struct btrfs_root *root,
1295                   struct btrfs_path *path,
1296                   u64 dirid, int key_type,
1297                   u64 *start_ret, u64 *end_ret)
1298{
1299    struct btrfs_key key;
1300    u64 found_end;
1301    struct btrfs_dir_log_item *item;
1302    int ret;
1303    int nritems;
1304
1305    if (*start_ret == (u64)-1)
1306        return 1;
1307
1308    key.objectid = dirid;
1309    key.type = key_type;
1310    key.offset = *start_ret;
1311
1312    ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1313    if (ret < 0)
1314        goto out;
1315    if (ret > 0) {
1316        if (path->slots[0] == 0)
1317            goto out;
1318        path->slots[0]--;
1319    }
1320    if (ret != 0)
1321        btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1322
1323    if (key.type != key_type || key.objectid != dirid) {
1324        ret = 1;
1325        goto next;
1326    }
1327    item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1328                  struct btrfs_dir_log_item);
1329    found_end = btrfs_dir_log_end(path->nodes[0], item);
1330
1331    if (*start_ret >= key.offset && *start_ret <= found_end) {
1332        ret = 0;
1333        *start_ret = key.offset;
1334        *end_ret = found_end;
1335        goto out;
1336    }
1337    ret = 1;
1338next:
1339    /* check the next slot in the tree to see if it is a valid item */
1340    nritems = btrfs_header_nritems(path->nodes[0]);
1341    if (path->slots[0] >= nritems) {
1342        ret = btrfs_next_leaf(root, path);
1343        if (ret)
1344            goto out;
1345    } else {
1346        path->slots[0]++;
1347    }
1348
1349    btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1350
1351    if (key.type != key_type || key.objectid != dirid) {
1352        ret = 1;
1353        goto out;
1354    }
1355    item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1356                  struct btrfs_dir_log_item);
1357    found_end = btrfs_dir_log_end(path->nodes[0], item);
1358    *start_ret = key.offset;
1359    *end_ret = found_end;
1360    ret = 0;
1361out:
1362    btrfs_release_path(root, path);
1363    return ret;
1364}
1365
1366/*
1367 * this looks for a given directory item in the log. If the directory
1368 * item is not in the log, the item is removed and the inode it points
1369 * to is unlinked
1370 */
1371static noinline int check_item_in_log(struct btrfs_trans_handle *trans,
1372                      struct btrfs_root *root,
1373                      struct btrfs_root *log,
1374                      struct btrfs_path *path,
1375                      struct btrfs_path *log_path,
1376                      struct inode *dir,
1377                      struct btrfs_key *dir_key)
1378{
1379    int ret;
1380    struct extent_buffer *eb;
1381    int slot;
1382    u32 item_size;
1383    struct btrfs_dir_item *di;
1384    struct btrfs_dir_item *log_di;
1385    int name_len;
1386    unsigned long ptr;
1387    unsigned long ptr_end;
1388    char *name;
1389    struct inode *inode;
1390    struct btrfs_key location;
1391
1392again:
1393    eb = path->nodes[0];
1394    slot = path->slots[0];
1395    item_size = btrfs_item_size_nr(eb, slot);
1396    ptr = btrfs_item_ptr_offset(eb, slot);
1397    ptr_end = ptr + item_size;
1398    while (ptr < ptr_end) {
1399        di = (struct btrfs_dir_item *)ptr;
1400        name_len = btrfs_dir_name_len(eb, di);
1401        name = kmalloc(name_len, GFP_NOFS);
1402        if (!name) {
1403            ret = -ENOMEM;
1404            goto out;
1405        }
1406        read_extent_buffer(eb, name, (unsigned long)(di + 1),
1407                  name_len);
1408        log_di = NULL;
1409        if (log && dir_key->type == BTRFS_DIR_ITEM_KEY) {
1410            log_di = btrfs_lookup_dir_item(trans, log, log_path,
1411                               dir_key->objectid,
1412                               name, name_len, 0);
1413        } else if (log && dir_key->type == BTRFS_DIR_INDEX_KEY) {
1414            log_di = btrfs_lookup_dir_index_item(trans, log,
1415                             log_path,
1416                             dir_key->objectid,
1417                             dir_key->offset,
1418                             name, name_len, 0);
1419        }
1420        if (!log_di || IS_ERR(log_di)) {
1421            btrfs_dir_item_key_to_cpu(eb, di, &location);
1422            btrfs_release_path(root, path);
1423            btrfs_release_path(log, log_path);
1424            inode = read_one_inode(root, location.objectid);
1425            BUG_ON(!inode);
1426
1427            ret = link_to_fixup_dir(trans, root,
1428                        path, location.objectid);
1429            BUG_ON(ret);
1430            btrfs_inc_nlink(inode);
1431            ret = btrfs_unlink_inode(trans, root, dir, inode,
1432                         name, name_len);
1433            BUG_ON(ret);
1434            kfree(name);
1435            iput(inode);
1436
1437            /* there might still be more names under this key
1438             * check and repeat if required
1439             */
1440            ret = btrfs_search_slot(NULL, root, dir_key, path,
1441                        0, 0);
1442            if (ret == 0)
1443                goto again;
1444            ret = 0;
1445            goto out;
1446        }
1447        btrfs_release_path(log, log_path);
1448        kfree(name);
1449
1450        ptr = (unsigned long)(di + 1);
1451        ptr += name_len;
1452    }
1453    ret = 0;
1454out:
1455    btrfs_release_path(root, path);
1456    btrfs_release_path(log, log_path);
1457    return ret;
1458}
1459
1460/*
1461 * deletion replay happens before we copy any new directory items
1462 * out of the log or out of backreferences from inodes. It
1463 * scans the log to find ranges of keys that log is authoritative for,
1464 * and then scans the directory to find items in those ranges that are
1465 * not present in the log.
1466 *
1467 * Anything we don't find in the log is unlinked and removed from the
1468 * directory.
1469 */
1470static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
1471                       struct btrfs_root *root,
1472                       struct btrfs_root *log,
1473                       struct btrfs_path *path,
1474                       u64 dirid, int del_all)
1475{
1476    u64 range_start;
1477    u64 range_end;
1478    int key_type = BTRFS_DIR_LOG_ITEM_KEY;
1479    int ret = 0;
1480    struct btrfs_key dir_key;
1481    struct btrfs_key found_key;
1482    struct btrfs_path *log_path;
1483    struct inode *dir;
1484
1485    dir_key.objectid = dirid;
1486    dir_key.type = BTRFS_DIR_ITEM_KEY;
1487    log_path = btrfs_alloc_path();
1488    if (!log_path)
1489        return -ENOMEM;
1490
1491    dir = read_one_inode(root, dirid);
1492    /* it isn't an error if the inode isn't there, that can happen
1493     * because we replay the deletes before we copy in the inode item
1494     * from the log
1495     */
1496    if (!dir) {
1497        btrfs_free_path(log_path);
1498        return 0;
1499    }
1500again:
1501    range_start = 0;
1502    range_end = 0;
1503    while (1) {
1504        if (del_all)
1505            range_end = (u64)-1;
1506        else {
1507            ret = find_dir_range(log, path, dirid, key_type,
1508                         &range_start, &range_end);
1509            if (ret != 0)
1510                break;
1511        }
1512
1513        dir_key.offset = range_start;
1514        while (1) {
1515            int nritems;
1516            ret = btrfs_search_slot(NULL, root, &dir_key, path,
1517                        0, 0);
1518            if (ret < 0)
1519                goto out;
1520
1521            nritems = btrfs_header_nritems(path->nodes[0]);
1522            if (path->slots[0] >= nritems) {
1523                ret = btrfs_next_leaf(root, path);
1524                if (ret)
1525                    break;
1526            }
1527            btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1528                          path->slots[0]);
1529            if (found_key.objectid != dirid ||
1530                found_key.type != dir_key.type)
1531                goto next_type;
1532
1533            if (found_key.offset > range_end)
1534                break;
1535
1536            ret = check_item_in_log(trans, root, log, path,
1537                        log_path, dir,
1538                        &found_key);
1539            BUG_ON(ret);
1540            if (found_key.offset == (u64)-1)
1541                break;
1542            dir_key.offset = found_key.offset + 1;
1543        }
1544        btrfs_release_path(root, path);
1545        if (range_end == (u64)-1)
1546            break;
1547        range_start = range_end + 1;
1548    }
1549
1550next_type:
1551    ret = 0;
1552    if (key_type == BTRFS_DIR_LOG_ITEM_KEY) {
1553        key_type = BTRFS_DIR_LOG_INDEX_KEY;
1554        dir_key.type = BTRFS_DIR_INDEX_KEY;
1555        btrfs_release_path(root, path);
1556        goto again;
1557    }
1558out:
1559    btrfs_release_path(root, path);
1560    btrfs_free_path(log_path);
1561    iput(dir);
1562    return ret;
1563}
1564
1565/*
1566 * the process_func used to replay items from the log tree. This
1567 * gets called in two different stages. The first stage just looks
1568 * for inodes and makes sure they are all copied into the subvolume.
1569 *
1570 * The second stage copies all the other item types from the log into
1571 * the subvolume. The two stage approach is slower, but gets rid of
1572 * lots of complexity around inodes referencing other inodes that exist
1573 * only in the log (references come from either directory items or inode
1574 * back refs).
1575 */
1576static int replay_one_buffer(struct btrfs_root *log, struct extent_buffer *eb,
1577                 struct walk_control *wc, u64 gen)
1578{
1579    int nritems;
1580    struct btrfs_path *path;
1581    struct btrfs_root *root = wc->replay_dest;
1582    struct btrfs_key key;
1583    u32 item_size;
1584    int level;
1585    int i;
1586    int ret;
1587
1588    btrfs_read_buffer(eb, gen);
1589
1590    level = btrfs_header_level(eb);
1591
1592    if (level != 0)
1593        return 0;
1594
1595    path = btrfs_alloc_path();
1596    BUG_ON(!path);
1597
1598    nritems = btrfs_header_nritems(eb);
1599    for (i = 0; i < nritems; i++) {
1600        btrfs_item_key_to_cpu(eb, &key, i);
1601        item_size = btrfs_item_size_nr(eb, i);
1602
1603        /* inode keys are done during the first stage */
1604        if (key.type == BTRFS_INODE_ITEM_KEY &&
1605            wc->stage == LOG_WALK_REPLAY_INODES) {
1606            struct btrfs_inode_item *inode_item;
1607            u32 mode;
1608
1609            inode_item = btrfs_item_ptr(eb, i,
1610                        struct btrfs_inode_item);
1611            mode = btrfs_inode_mode(eb, inode_item);
1612            if (S_ISDIR(mode)) {
1613                ret = replay_dir_deletes(wc->trans,
1614                     root, log, path, key.objectid, 0);
1615                BUG_ON(ret);
1616            }
1617            ret = overwrite_item(wc->trans, root, path,
1618                         eb, i, &key);
1619            BUG_ON(ret);
1620
1621            /* for regular files, make sure corresponding
1622             * orhpan item exist. extents past the new EOF
1623             * will be truncated later by orphan cleanup.
1624             */
1625            if (S_ISREG(mode)) {
1626                ret = insert_orphan_item(wc->trans, root,
1627                             key.objectid);
1628                BUG_ON(ret);
1629            }
1630
1631            ret = link_to_fixup_dir(wc->trans, root,
1632                        path, key.objectid);
1633            BUG_ON(ret);
1634        }
1635        if (wc->stage < LOG_WALK_REPLAY_ALL)
1636            continue;
1637
1638        /* these keys are simply copied */
1639        if (key.type == BTRFS_XATTR_ITEM_KEY) {
1640            ret = overwrite_item(wc->trans, root, path,
1641                         eb, i, &key);
1642            BUG_ON(ret);
1643        } else if (key.type == BTRFS_INODE_REF_KEY) {
1644            ret = add_inode_ref(wc->trans, root, log, path,
1645                        eb, i, &key);
1646            BUG_ON(ret && ret != -ENOENT);
1647        } else if (key.type == BTRFS_EXTENT_DATA_KEY) {
1648            ret = replay_one_extent(wc->trans, root, path,
1649                        eb, i, &key);
1650            BUG_ON(ret);
1651        } else if (key.type == BTRFS_DIR_ITEM_KEY ||
1652               key.type == BTRFS_DIR_INDEX_KEY) {
1653            ret = replay_one_dir_item(wc->trans, root, path,
1654                          eb, i, &key);
1655            BUG_ON(ret);
1656        }
1657    }
1658    btrfs_free_path(path);
1659    return 0;
1660}
1661
1662static noinline int walk_down_log_tree(struct btrfs_trans_handle *trans,
1663                   struct btrfs_root *root,
1664                   struct btrfs_path *path, int *level,
1665                   struct walk_control *wc)
1666{
1667    u64 root_owner;
1668    u64 root_gen;
1669    u64 bytenr;
1670    u64 ptr_gen;
1671    struct extent_buffer *next;
1672    struct extent_buffer *cur;
1673    struct extent_buffer *parent;
1674    u32 blocksize;
1675    int ret = 0;
1676
1677    WARN_ON(*level < 0);
1678    WARN_ON(*level >= BTRFS_MAX_LEVEL);
1679
1680    while (*level > 0) {
1681        WARN_ON(*level < 0);
1682        WARN_ON(*level >= BTRFS_MAX_LEVEL);
1683        cur = path->nodes[*level];
1684
1685        if (btrfs_header_level(cur) != *level)
1686            WARN_ON(1);
1687
1688        if (path->slots[*level] >=
1689            btrfs_header_nritems(cur))
1690            break;
1691
1692        bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1693        ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1694        blocksize = btrfs_level_size(root, *level - 1);
1695
1696        parent = path->nodes[*level];
1697        root_owner = btrfs_header_owner(parent);
1698        root_gen = btrfs_header_generation(parent);
1699
1700        next = btrfs_find_create_tree_block(root, bytenr, blocksize);
1701
1702        wc->process_func(root, next, wc, ptr_gen);
1703
1704        if (*level == 1) {
1705            path->slots[*level]++;
1706            if (wc->free) {
1707                btrfs_read_buffer(next, ptr_gen);
1708
1709                btrfs_tree_lock(next);
1710                clean_tree_block(trans, root, next);
1711                btrfs_set_lock_blocking(next);
1712                btrfs_wait_tree_block_writeback(next);
1713                btrfs_tree_unlock(next);
1714
1715                WARN_ON(root_owner !=
1716                    BTRFS_TREE_LOG_OBJECTID);
1717                ret = btrfs_free_reserved_extent(root,
1718                             bytenr, blocksize);
1719                BUG_ON(ret);
1720            }
1721            free_extent_buffer(next);
1722            continue;
1723        }
1724        btrfs_read_buffer(next, ptr_gen);
1725
1726        WARN_ON(*level <= 0);
1727        if (path->nodes[*level-1])
1728            free_extent_buffer(path->nodes[*level-1]);
1729        path->nodes[*level-1] = next;
1730        *level = btrfs_header_level(next);
1731        path->slots[*level] = 0;
1732        cond_resched();
1733    }
1734    WARN_ON(*level < 0);
1735    WARN_ON(*level >= BTRFS_MAX_LEVEL);
1736
1737    if (path->nodes[*level] == root->node)
1738        parent = path->nodes[*level];
1739    else
1740        parent = path->nodes[*level + 1];
1741
1742    bytenr = path->nodes[*level]->start;
1743
1744    blocksize = btrfs_level_size(root, *level);
1745    root_owner = btrfs_header_owner(parent);
1746    root_gen = btrfs_header_generation(parent);
1747
1748    wc->process_func(root, path->nodes[*level], wc,
1749             btrfs_header_generation(path->nodes[*level]));
1750
1751    if (wc->free) {
1752        next = path->nodes[*level];
1753        btrfs_tree_lock(next);
1754        clean_tree_block(trans, root, next);
1755        btrfs_set_lock_blocking(next);
1756        btrfs_wait_tree_block_writeback(next);
1757        btrfs_tree_unlock(next);
1758
1759        WARN_ON(root_owner != BTRFS_TREE_LOG_OBJECTID);
1760        ret = btrfs_free_reserved_extent(root, bytenr, blocksize);
1761        BUG_ON(ret);
1762    }
1763    free_extent_buffer(path->nodes[*level]);
1764    path->nodes[*level] = NULL;
1765    *level += 1;
1766
1767    cond_resched();
1768    return 0;
1769}
1770
1771static noinline int walk_up_log_tree(struct btrfs_trans_handle *trans,
1772                 struct btrfs_root *root,
1773                 struct btrfs_path *path, int *level,
1774                 struct walk_control *wc)
1775{
1776    u64 root_owner;
1777    u64 root_gen;
1778    int i;
1779    int slot;
1780    int ret;
1781
1782    for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1783        slot = path->slots[i];
1784        if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1785            struct extent_buffer *node;
1786            node = path->nodes[i];
1787            path->slots[i]++;
1788            *level = i;
1789            WARN_ON(*level == 0);
1790            return 0;
1791        } else {
1792            struct extent_buffer *parent;
1793            if (path->nodes[*level] == root->node)
1794                parent = path->nodes[*level];
1795            else
1796                parent = path->nodes[*level + 1];
1797
1798            root_owner = btrfs_header_owner(parent);
1799            root_gen = btrfs_header_generation(parent);
1800            wc->process_func(root, path->nodes[*level], wc,
1801                 btrfs_header_generation(path->nodes[*level]));
1802            if (wc->free) {
1803                struct extent_buffer *next;
1804
1805                next = path->nodes[*level];
1806
1807                btrfs_tree_lock(next);
1808                clean_tree_block(trans, root, next);
1809                btrfs_set_lock_blocking(next);
1810                btrfs_wait_tree_block_writeback(next);
1811                btrfs_tree_unlock(next);
1812
1813                WARN_ON(root_owner != BTRFS_TREE_LOG_OBJECTID);
1814                ret = btrfs_free_reserved_extent(root,
1815                        path->nodes[*level]->start,
1816                        path->nodes[*level]->len);
1817                BUG_ON(ret);
1818            }
1819            free_extent_buffer(path->nodes[*level]);
1820            path->nodes[*level] = NULL;
1821            *level = i + 1;
1822        }
1823    }
1824    return 1;
1825}
1826
1827/*
1828 * drop the reference count on the tree rooted at 'snap'. This traverses
1829 * the tree freeing any blocks that have a ref count of zero after being
1830 * decremented.
1831 */
1832static int walk_log_tree(struct btrfs_trans_handle *trans,
1833             struct btrfs_root *log, struct walk_control *wc)
1834{
1835    int ret = 0;
1836    int wret;
1837    int level;
1838    struct btrfs_path *path;
1839    int i;
1840    int orig_level;
1841
1842    path = btrfs_alloc_path();
1843    BUG_ON(!path);
1844
1845    level = btrfs_header_level(log->node);
1846    orig_level = level;
1847    path->nodes[level] = log->node;
1848    extent_buffer_get(log->node);
1849    path->slots[level] = 0;
1850
1851    while (1) {
1852        wret = walk_down_log_tree(trans, log, path, &level, wc);
1853        if (wret > 0)
1854            break;
1855        if (wret < 0)
1856            ret = wret;
1857
1858        wret = walk_up_log_tree(trans, log, path, &level, wc);
1859        if (wret > 0)
1860            break;
1861        if (wret < 0)
1862            ret = wret;
1863    }
1864
1865    /* was the root node processed? if not, catch it here */
1866    if (path->nodes[orig_level]) {
1867        wc->process_func(log, path->nodes[orig_level], wc,
1868             btrfs_header_generation(path->nodes[orig_level]));
1869        if (wc->free) {
1870            struct extent_buffer *next;
1871
1872            next = path->nodes[orig_level];
1873
1874            btrfs_tree_lock(next);
1875            clean_tree_block(trans, log, next);
1876            btrfs_set_lock_blocking(next);
1877            btrfs_wait_tree_block_writeback(next);
1878            btrfs_tree_unlock(next);
1879
1880            WARN_ON(log->root_key.objectid !=
1881                BTRFS_TREE_LOG_OBJECTID);
1882            ret = btrfs_free_reserved_extent(log, next->start,
1883                             next->len);
1884            BUG_ON(ret);
1885        }
1886    }
1887
1888    for (i = 0; i <= orig_level; i++) {
1889        if (path->nodes[i]) {
1890            free_extent_buffer(path->nodes[i]);
1891            path->nodes[i] = NULL;
1892        }
1893    }
1894    btrfs_free_path(path);
1895    return ret;
1896}
1897
1898/*
1899 * helper function to update the item for a given subvolumes log root
1900 * in the tree of log roots
1901 */
1902static int update_log_root(struct btrfs_trans_handle *trans,
1903               struct btrfs_root *log)
1904{
1905    int ret;
1906
1907    if (log->log_transid == 1) {
1908        /* insert root item on the first sync */
1909        ret = btrfs_insert_root(trans, log->fs_info->log_root_tree,
1910                &log->root_key, &log->root_item);
1911    } else {
1912        ret = btrfs_update_root(trans, log->fs_info->log_root_tree,
1913                &log->root_key, &log->root_item);
1914    }
1915    return ret;
1916}
1917
1918static int wait_log_commit(struct btrfs_trans_handle *trans,
1919               struct btrfs_root *root, unsigned long transid)
1920{
1921    DEFINE_WAIT(wait);
1922    int index = transid % 2;
1923
1924    /*
1925     * we only allow two pending log transactions at a time,
1926     * so we know that if ours is more than 2 older than the
1927     * current transaction, we're done
1928     */
1929    do {
1930        prepare_to_wait(&root->log_commit_wait[index],
1931                &wait, TASK_UNINTERRUPTIBLE);
1932        mutex_unlock(&root->log_mutex);
1933
1934        if (root->fs_info->last_trans_log_full_commit !=
1935            trans->transid && root->log_transid < transid + 2 &&
1936            atomic_read(&root->log_commit[index]))
1937            schedule();
1938
1939        finish_wait(&root->log_commit_wait[index], &wait);
1940        mutex_lock(&root->log_mutex);
1941    } while (root->log_transid < transid + 2 &&
1942         atomic_read(&root->log_commit[index]));
1943    return 0;
1944}
1945
1946static int wait_for_writer(struct btrfs_trans_handle *trans,
1947               struct btrfs_root *root)
1948{
1949    DEFINE_WAIT(wait);
1950    while (atomic_read(&root->log_writers)) {
1951        prepare_to_wait(&root->log_writer_wait,
1952                &wait, TASK_UNINTERRUPTIBLE);
1953        mutex_unlock(&root->log_mutex);
1954        if (root->fs_info->last_trans_log_full_commit !=
1955            trans->transid && atomic_read(&root->log_writers))
1956            schedule();
1957        mutex_lock(&root->log_mutex);
1958        finish_wait(&root->log_writer_wait, &wait);
1959    }
1960    return 0;
1961}
1962
1963/*
1964 * btrfs_sync_log does sends a given tree log down to the disk and
1965 * updates the super blocks to record it. When this call is done,
1966 * you know that any inodes previously logged are safely on disk only
1967 * if it returns 0.
1968 *
1969 * Any other return value means you need to call btrfs_commit_transaction.
1970 * Some of the edge cases for fsyncing directories that have had unlinks
1971 * or renames done in the past mean that sometimes the only safe
1972 * fsync is to commit the whole FS. When btrfs_sync_log returns -EAGAIN,
1973 * that has happened.
1974 */
1975int btrfs_sync_log(struct btrfs_trans_handle *trans,
1976           struct btrfs_root *root)
1977{
1978    int index1;
1979    int index2;
1980    int mark;
1981    int ret;
1982    struct btrfs_root *log = root->log_root;
1983    struct btrfs_root *log_root_tree = root->fs_info->log_root_tree;
1984    unsigned long log_transid = 0;
1985
1986    mutex_lock(&root->log_mutex);
1987    index1 = root->log_transid % 2;
1988    if (atomic_read(&root->log_commit[index1])) {
1989        wait_log_commit(trans, root, root->log_transid);
1990        mutex_unlock(&root->log_mutex);
1991        return 0;
1992    }
1993    atomic_set(&root->log_commit[index1], 1);
1994
1995    /* wait for previous tree log sync to complete */
1996    if (atomic_read(&root->log_commit[(index1 + 1) % 2]))
1997        wait_log_commit(trans, root, root->log_transid - 1);
1998
1999    while (1) {
2000        unsigned long batch = root->log_batch;
2001        if (root->log_multiple_pids) {
2002            mutex_unlock(&root->log_mutex);
2003            schedule_timeout_uninterruptible(1);
2004            mutex_lock(&root->log_mutex);
2005        }
2006        wait_for_writer(trans, root);
2007        if (batch == root->log_batch)
2008            break;
2009    }
2010
2011    /* bail out if we need to do a full commit */
2012    if (root->fs_info->last_trans_log_full_commit == trans->transid) {
2013        ret = -EAGAIN;
2014        mutex_unlock(&root->log_mutex);
2015        goto out;
2016    }
2017
2018    log_transid = root->log_transid;
2019    if (log_transid % 2 == 0)
2020        mark = EXTENT_DIRTY;
2021    else
2022        mark = EXTENT_NEW;
2023
2024    /* we start IO on all the marked extents here, but we don't actually
2025     * wait for them until later.
2026     */
2027    ret = btrfs_write_marked_extents(log, &log->dirty_log_pages, mark);
2028    BUG_ON(ret);
2029
2030    btrfs_set_root_node(&log->root_item, log->node);
2031
2032    root->log_batch = 0;
2033    root->log_transid++;
2034    log->log_transid = root->log_transid;
2035    root->log_start_pid = 0;
2036    smp_mb();
2037    /*
2038     * IO has been started, blocks of the log tree have WRITTEN flag set
2039     * in their headers. new modifications of the log will be written to
2040     * new positions. so it's safe to allow log writers to go in.
2041     */
2042    mutex_unlock(&root->log_mutex);
2043
2044    mutex_lock(&log_root_tree->log_mutex);
2045    log_root_tree->log_batch++;
2046    atomic_inc(&log_root_tree->log_writers);
2047    mutex_unlock(&log_root_tree->log_mutex);
2048
2049    ret = update_log_root(trans, log);
2050    BUG_ON(ret);
2051
2052    mutex_lock(&log_root_tree->log_mutex);
2053    if (atomic_dec_and_test(&log_root_tree->log_writers)) {
2054        smp_mb();
2055        if (waitqueue_active(&log_root_tree->log_writer_wait))
2056            wake_up(&log_root_tree->log_writer_wait);
2057    }
2058
2059    index2 = log_root_tree->log_transid % 2;
2060    if (atomic_read(&log_root_tree->log_commit[index2])) {
2061        btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2062        wait_log_commit(trans, log_root_tree,
2063                log_root_tree->log_transid);
2064        mutex_unlock(&log_root_tree->log_mutex);
2065        goto out;
2066    }
2067    atomic_set(&log_root_tree->log_commit[index2], 1);
2068
2069    if (atomic_read(&log_root_tree->log_commit[(index2 + 1) % 2])) {
2070        wait_log_commit(trans, log_root_tree,
2071                log_root_tree->log_transid - 1);
2072    }
2073
2074    wait_for_writer(trans, log_root_tree);
2075
2076    /*
2077     * now that we've moved on to the tree of log tree roots,
2078     * check the full commit flag again
2079     */
2080    if (root->fs_info->last_trans_log_full_commit == trans->transid) {
2081        btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2082        mutex_unlock(&log_root_tree->log_mutex);
2083        ret = -EAGAIN;
2084        goto out_wake_log_root;
2085    }
2086
2087    ret = btrfs_write_and_wait_marked_extents(log_root_tree,
2088                &log_root_tree->dirty_log_pages,
2089                EXTENT_DIRTY | EXTENT_NEW);
2090    BUG_ON(ret);
2091    btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2092
2093    btrfs_set_super_log_root(&root->fs_info->super_for_commit,
2094                log_root_tree->node->start);
2095    btrfs_set_super_log_root_level(&root->fs_info->super_for_commit,
2096                btrfs_header_level(log_root_tree->node));
2097
2098    log_root_tree->log_batch = 0;
2099    log_root_tree->log_transid++;
2100    smp_mb();
2101
2102    mutex_unlock(&log_root_tree->log_mutex);
2103
2104    /*
2105     * nobody else is going to jump in and write the the ctree
2106     * super here because the log_commit atomic below is protecting
2107     * us. We must be called with a transaction handle pinning
2108     * the running transaction open, so a full commit can't hop
2109     * in and cause problems either.
2110     */
2111    write_ctree_super(trans, root->fs_info->tree_root, 1);
2112    ret = 0;
2113
2114    mutex_lock(&root->log_mutex);
2115    if (root->last_log_commit < log_transid)
2116        root->last_log_commit = log_transid;
2117    mutex_unlock(&root->log_mutex);
2118
2119out_wake_log_root:
2120    atomic_set(&log_root_tree->log_commit[index2], 0);
2121    smp_mb();
2122    if (waitqueue_active(&log_root_tree->log_commit_wait[index2]))
2123        wake_up(&log_root_tree->log_commit_wait[index2]);
2124out:
2125    atomic_set(&root->log_commit[index1], 0);
2126    smp_mb();
2127    if (waitqueue_active(&root->log_commit_wait[index1]))
2128        wake_up(&root->log_commit_wait[index1]);
2129    return 0;
2130}
2131
2132/*
2133 * free all the extents used by the tree log. This should be called
2134 * at commit time of the full transaction
2135 */
2136int btrfs_free_log(struct btrfs_trans_handle *trans, struct btrfs_root *root)
2137{
2138    int ret;
2139    struct btrfs_root *log;
2140    struct key;
2141    u64 start;
2142    u64 end;
2143    struct walk_control wc = {
2144        .free = 1,
2145        .process_func = process_one_buffer
2146    };
2147
2148    if (!root->log_root || root->fs_info->log_root_recovering)
2149        return 0;
2150
2151    log = root->log_root;
2152    ret = walk_log_tree(trans, log, &wc);
2153    BUG_ON(ret);
2154
2155    while (1) {
2156        ret = find_first_extent_bit(&log->dirty_log_pages,
2157                0, &start, &end, EXTENT_DIRTY | EXTENT_NEW);
2158        if (ret)
2159            break;
2160
2161        clear_extent_bits(&log->dirty_log_pages, start, end,
2162                  EXTENT_DIRTY | EXTENT_NEW, GFP_NOFS);
2163    }
2164
2165    if (log->log_transid > 0) {
2166        ret = btrfs_del_root(trans, root->fs_info->log_root_tree,
2167                     &log->root_key);
2168        BUG_ON(ret);
2169    }
2170    root->log_root = NULL;
2171    free_extent_buffer(log->node);
2172    kfree(log);
2173    return 0;
2174}
2175
2176/*
2177 * If both a file and directory are logged, and unlinks or renames are
2178 * mixed in, we have a few interesting corners:
2179 *
2180 * create file X in dir Y
2181 * link file X to X.link in dir Y
2182 * fsync file X
2183 * unlink file X but leave X.link
2184 * fsync dir Y
2185 *
2186 * After a crash we would expect only X.link to exist. But file X
2187 * didn't get fsync'd again so the log has back refs for X and X.link.
2188 *
2189 * We solve this by removing directory entries and inode backrefs from the
2190 * log when a file that was logged in the current transaction is
2191 * unlinked. Any later fsync will include the updated log entries, and
2192 * we'll be able to reconstruct the proper directory items from backrefs.
2193 *
2194 * This optimizations allows us to avoid relogging the entire inode
2195 * or the entire directory.
2196 */
2197int btrfs_del_dir_entries_in_log(struct btrfs_trans_handle *trans,
2198                 struct btrfs_root *root,
2199                 const char *name, int name_len,
2200                 struct inode *dir, u64 index)
2201{
2202    struct btrfs_root *log;
2203    struct btrfs_dir_item *di;
2204    struct btrfs_path *path;
2205    int ret;
2206    int bytes_del = 0;
2207
2208    if (BTRFS_I(dir)->logged_trans < trans->transid)
2209        return 0;
2210
2211    ret = join_running_log_trans(root);
2212    if (ret)
2213        return 0;
2214
2215    mutex_lock(&BTRFS_I(dir)->log_mutex);
2216
2217    log = root->log_root;
2218    path = btrfs_alloc_path();
2219    di = btrfs_lookup_dir_item(trans, log, path, dir->i_ino,
2220                   name, name_len, -1);
2221    if (di && !IS_ERR(di)) {
2222        ret = btrfs_delete_one_dir_name(trans, log, path, di);
2223        bytes_del += name_len;
2224        BUG_ON(ret);
2225    }
2226    btrfs_release_path(log, path);
2227    di = btrfs_lookup_dir_index_item(trans, log, path, dir->i_ino,
2228                     index, name, name_len, -1);
2229    if (di && !IS_ERR(di)) {
2230        ret = btrfs_delete_one_dir_name(trans, log, path, di);
2231        bytes_del += name_len;
2232        BUG_ON(ret);
2233    }
2234
2235    /* update the directory size in the log to reflect the names
2236     * we have removed
2237     */
2238    if (bytes_del) {
2239        struct btrfs_key key;
2240
2241        key.objectid = dir->i_ino;
2242        key.offset = 0;
2243        key.type = BTRFS_INODE_ITEM_KEY;
2244        btrfs_release_path(log, path);
2245
2246        ret = btrfs_search_slot(trans, log, &key, path, 0, 1);
2247        if (ret == 0) {
2248            struct btrfs_inode_item *item;
2249            u64 i_size;
2250
2251            item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2252                          struct btrfs_inode_item);
2253            i_size = btrfs_inode_size(path->nodes[0], item);
2254            if (i_size > bytes_del)
2255                i_size -= bytes_del;
2256            else
2257                i_size = 0;
2258            btrfs_set_inode_size(path->nodes[0], item, i_size);
2259            btrfs_mark_buffer_dirty(path->nodes[0]);
2260        } else
2261            ret = 0;
2262        btrfs_release_path(log, path);
2263    }
2264
2265    btrfs_free_path(path);
2266    mutex_unlock(&BTRFS_I(dir)->log_mutex);
2267    btrfs_end_log_trans(root);
2268
2269    return 0;
2270}
2271
2272/* see comments for btrfs_del_dir_entries_in_log */
2273int btrfs_del_inode_ref_in_log(struct btrfs_trans_handle *trans,
2274                   struct btrfs_root *root,
2275                   const char *name, int name_len,
2276                   struct inode *inode, u64 dirid)
2277{
2278    struct btrfs_root *log;
2279    u64 index;
2280    int ret;
2281
2282    if (BTRFS_I(inode)->logged_trans < trans->transid)
2283        return 0;
2284
2285    ret = join_running_log_trans(root);
2286    if (ret)
2287        return 0;
2288    log = root->log_root;
2289    mutex_lock(&BTRFS_I(inode)->log_mutex);
2290
2291    ret = btrfs_del_inode_ref(trans, log, name, name_len, inode->i_ino,
2292                  dirid, &index);
2293    mutex_unlock(&BTRFS_I(inode)->log_mutex);
2294    btrfs_end_log_trans(root);
2295
2296    return ret;
2297}
2298
2299/*
2300 * creates a range item in the log for 'dirid'. first_offset and
2301 * last_offset tell us which parts of the key space the log should
2302 * be considered authoritative for.
2303 */
2304static noinline int insert_dir_log_key(struct btrfs_trans_handle *trans,
2305                       struct btrfs_root *log,
2306                       struct btrfs_path *path,
2307                       int key_type, u64 dirid,
2308                       u64 first_offset, u64 last_offset)
2309{
2310    int ret;
2311    struct btrfs_key key;
2312    struct btrfs_dir_log_item *item;
2313
2314    key.objectid = dirid;
2315    key.offset = first_offset;
2316    if (key_type == BTRFS_DIR_ITEM_KEY)
2317        key.type = BTRFS_DIR_LOG_ITEM_KEY;
2318    else
2319        key.type = BTRFS_DIR_LOG_INDEX_KEY;
2320    ret = btrfs_insert_empty_item(trans, log, path, &key, sizeof(*item));
2321    BUG_ON(ret);
2322
2323    item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2324                  struct btrfs_dir_log_item);
2325    btrfs_set_dir_log_end(path->nodes[0], item, last_offset);
2326    btrfs_mark_buffer_dirty(path->nodes[0]);
2327    btrfs_release_path(log, path);
2328    return 0;
2329}
2330
2331/*
2332 * log all the items included in the current transaction for a given
2333 * directory. This also creates the range items in the log tree required
2334 * to replay anything deleted before the fsync
2335 */
2336static noinline int log_dir_items(struct btrfs_trans_handle *trans,
2337              struct btrfs_root *root, struct inode *inode,
2338              struct btrfs_path *path,
2339              struct btrfs_path *dst_path, int key_type,
2340              u64 min_offset, u64 *last_offset_ret)
2341{
2342    struct btrfs_key min_key;
2343    struct btrfs_key max_key;
2344    struct btrfs_root *log = root->log_root;
2345    struct extent_buffer *src;
2346    int ret;
2347    int i;
2348    int nritems;
2349    u64 first_offset = min_offset;
2350    u64 last_offset = (u64)-1;
2351
2352    log = root->log_root;
2353    max_key.objectid = inode->i_ino;
2354    max_key.offset = (u64)-1;
2355    max_key.type = key_type;
2356
2357    min_key.objectid = inode->i_ino;
2358    min_key.type = key_type;
2359    min_key.offset = min_offset;
2360
2361    path->keep_locks = 1;
2362
2363    ret = btrfs_search_forward(root, &min_key, &max_key,
2364                   path, 0, trans->transid);
2365
2366    /*
2367     * we didn't find anything from this transaction, see if there
2368     * is anything at all
2369     */
2370    if (ret != 0 || min_key.objectid != inode->i_ino ||
2371        min_key.type != key_type) {
2372        min_key.objectid = inode->i_ino;
2373        min_key.type = key_type;
2374        min_key.offset = (u64)-1;
2375        btrfs_release_path(root, path);
2376        ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
2377        if (ret < 0) {
2378            btrfs_release_path(root, path);
2379            return ret;
2380        }
2381        ret = btrfs_previous_item(root, path, inode->i_ino, key_type);
2382
2383        /* if ret == 0 there are items for this type,
2384         * create a range to tell us the last key of this type.
2385         * otherwise, there are no items in this directory after
2386         * *min_offset, and we create a range to indicate that.
2387         */
2388        if (ret == 0) {
2389            struct btrfs_key tmp;
2390            btrfs_item_key_to_cpu(path->nodes[0], &tmp,
2391                          path->slots[0]);
2392            if (key_type == tmp.type)
2393                first_offset = max(min_offset, tmp.offset) + 1;
2394        }
2395        goto done;
2396    }
2397
2398    /* go backward to find any previous key */
2399    ret = btrfs_previous_item(root, path, inode->i_ino, key_type);
2400    if (ret == 0) {
2401        struct btrfs_key tmp;
2402        btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
2403        if (key_type == tmp.type) {
2404            first_offset = tmp.offset;
2405            ret = overwrite_item(trans, log, dst_path,
2406                         path->nodes[0], path->slots[0],
2407                         &tmp);
2408        }
2409    }
2410    btrfs_release_path(root, path);
2411
2412    /* find the first key from this transaction again */
2413    ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
2414    if (ret != 0) {
2415        WARN_ON(1);
2416        goto done;
2417    }
2418
2419    /*
2420     * we have a block from this transaction, log every item in it
2421     * from our directory
2422     */
2423    while (1) {
2424        struct btrfs_key tmp;
2425        src = path->nodes[0];
2426        nritems = btrfs_header_nritems(src);
2427        for (i = path->slots[0]; i < nritems; i++) {
2428            btrfs_item_key_to_cpu(src, &min_key, i);
2429
2430            if (min_key.objectid != inode->i_ino ||
2431                min_key.type != key_type)
2432                goto done;
2433            ret = overwrite_item(trans, log, dst_path, src, i,
2434                         &min_key);
2435            BUG_ON(ret);
2436        }
2437        path->slots[0] = nritems;
2438
2439        /*
2440         * look ahead to the next item and see if it is also
2441         * from this directory and from this transaction
2442         */
2443        ret = btrfs_next_leaf(root, path);
2444        if (ret == 1) {
2445            last_offset = (u64)-1;
2446            goto done;
2447        }
2448        btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
2449        if (tmp.objectid != inode->i_ino || tmp.type != key_type) {
2450            last_offset = (u64)-1;
2451            goto done;
2452        }
2453        if (btrfs_header_generation(path->nodes[0]) != trans->transid) {
2454            ret = overwrite_item(trans, log, dst_path,
2455                         path->nodes[0], path->slots[0],
2456                         &tmp);
2457
2458            BUG_ON(ret);
2459            last_offset = tmp.offset;
2460            goto done;
2461        }
2462    }
2463done:
2464    *last_offset_ret = last_offset;
2465    btrfs_release_path(root, path);
2466    btrfs_release_path(log, dst_path);
2467
2468    /* insert the log range keys to indicate where the log is valid */
2469    ret = insert_dir_log_key(trans, log, path, key_type, inode->i_ino,
2470                 first_offset, last_offset);
2471    BUG_ON(ret);
2472    return 0;
2473}
2474
2475/*
2476 * logging directories is very similar to logging inodes, We find all the items
2477 * from the current transaction and write them to the log.
2478 *
2479 * The recovery code scans the directory in the subvolume, and if it finds a
2480 * key in the range logged that is not present in the log tree, then it means
2481 * that dir entry was unlinked during the transaction.
2482 *
2483 * In order for that scan to work, we must include one key smaller than
2484 * the smallest logged by this transaction and one key larger than the largest
2485 * key logged by this transaction.
2486 */
2487static noinline int log_directory_changes(struct btrfs_trans_handle *trans,
2488              struct btrfs_root *root, struct inode *inode,
2489              struct btrfs_path *path,
2490              struct btrfs_path *dst_path)
2491{
2492    u64 min_key;
2493    u64 max_key;
2494    int ret;
2495    int key_type = BTRFS_DIR_ITEM_KEY;
2496
2497again:
2498    min_key = 0;
2499    max_key = 0;
2500    while (1) {
2501        ret = log_dir_items(trans, root, inode, path,
2502                    dst_path, key_type, min_key,
2503                    &max_key);
2504        BUG_ON(ret);
2505        if (max_key == (u64)-1)
2506            break;
2507        min_key = max_key + 1;
2508    }
2509
2510    if (key_type == BTRFS_DIR_ITEM_KEY) {
2511        key_type = BTRFS_DIR_INDEX_KEY;
2512        goto again;
2513    }
2514    return 0;
2515}
2516
2517/*
2518 * a helper function to drop items from the log before we relog an
2519 * inode. max_key_type indicates the highest item type to remove.
2520 * This cannot be run for file data extents because it does not
2521 * free the extents they point to.
2522 */
2523static int drop_objectid_items(struct btrfs_trans_handle *trans,
2524                  struct btrfs_root *log,
2525                  struct btrfs_path *path,
2526                  u64 objectid, int max_key_type)
2527{
2528    int ret;
2529    struct btrfs_key key;
2530    struct btrfs_key found_key;
2531
2532    key.objectid = objectid;
2533    key.type = max_key_type;
2534    key.offset = (u64)-1;
2535
2536    while (1) {
2537        ret = btrfs_search_slot(trans, log, &key, path, -1, 1);
2538
2539        if (ret != 1)
2540            break;
2541
2542        if (path->slots[0] == 0)
2543            break;
2544
2545        path->slots[0]--;
2546        btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2547                      path->slots[0]);
2548
2549        if (found_key.objectid != objectid)
2550            break;
2551
2552        ret = btrfs_del_item(trans, log, path);
2553        BUG_ON(ret);
2554        btrfs_release_path(log, path);
2555    }
2556    btrfs_release_path(log, path);
2557    return 0;
2558}
2559
2560static noinline int copy_items(struct btrfs_trans_handle *trans,
2561                   struct btrfs_root *log,
2562                   struct btrfs_path *dst_path,
2563                   struct extent_buffer *src,
2564                   int start_slot, int nr, int inode_only)
2565{
2566    unsigned long src_offset;
2567    unsigned long dst_offset;
2568    struct btrfs_file_extent_item *extent;
2569    struct btrfs_inode_item *inode_item;
2570    int ret;
2571    struct btrfs_key *ins_keys;
2572    u32 *ins_sizes;
2573    char *ins_data;
2574    int i;
2575    struct list_head ordered_sums;
2576
2577    INIT_LIST_HEAD(&ordered_sums);
2578
2579    ins_data = kmalloc(nr * sizeof(struct btrfs_key) +
2580               nr * sizeof(u32), GFP_NOFS);
2581    ins_sizes = (u32 *)ins_data;
2582    ins_keys = (struct btrfs_key *)(ins_data + nr * sizeof(u32));
2583
2584    for (i = 0; i < nr; i++) {
2585        ins_sizes[i] = btrfs_item_size_nr(src, i + start_slot);
2586        btrfs_item_key_to_cpu(src, ins_keys + i, i + start_slot);
2587    }
2588    ret = btrfs_insert_empty_items(trans, log, dst_path,
2589                       ins_keys, ins_sizes, nr);
2590    BUG_ON(ret);
2591
2592    for (i = 0; i < nr; i++, dst_path->slots[0]++) {
2593        dst_offset = btrfs_item_ptr_offset(dst_path->nodes[0],
2594                           dst_path->slots[0]);
2595
2596        src_offset = btrfs_item_ptr_offset(src, start_slot + i);
2597
2598        copy_extent_buffer(dst_path->nodes[0], src, dst_offset,
2599                   src_offset, ins_sizes[i]);
2600
2601        if (inode_only == LOG_INODE_EXISTS &&
2602            ins_keys[i].type == BTRFS_INODE_ITEM_KEY) {
2603            inode_item = btrfs_item_ptr(dst_path->nodes[0],
2604                            dst_path->slots[0],
2605                            struct btrfs_inode_item);
2606            btrfs_set_inode_size(dst_path->nodes[0], inode_item, 0);
2607
2608            /* set the generation to zero so the recover code
2609             * can tell the difference between an logging
2610             * just to say 'this inode exists' and a logging
2611             * to say 'update this inode with these values'
2612             */
2613            btrfs_set_inode_generation(dst_path->nodes[0],
2614                           inode_item, 0);
2615        }
2616        /* take a reference on file data extents so that truncates
2617         * or deletes of this inode don't have to relog the inode
2618         * again
2619         */
2620        if (btrfs_key_type(ins_keys + i) == BTRFS_EXTENT_DATA_KEY) {
2621            int found_type;
2622            extent = btrfs_item_ptr(src, start_slot + i,
2623                        struct btrfs_file_extent_item);
2624
2625            found_type = btrfs_file_extent_type(src, extent);
2626            if (found_type == BTRFS_FILE_EXTENT_REG ||
2627                found_type == BTRFS_FILE_EXTENT_PREALLOC) {
2628                u64 ds, dl, cs, cl;
2629                ds = btrfs_file_extent_disk_bytenr(src,
2630                                extent);
2631                /* ds == 0 is a hole */
2632                if (ds == 0)
2633                    continue;
2634
2635                dl = btrfs_file_extent_disk_num_bytes(src,
2636                                extent);
2637                cs = btrfs_file_extent_offset(src, extent);
2638                cl = btrfs_file_extent_num_bytes(src,
2639                                extent);
2640                if (btrfs_file_extent_compression(src,
2641                                  extent)) {
2642                    cs = 0;
2643                    cl = dl;
2644                }
2645
2646                ret = btrfs_lookup_csums_range(
2647                        log->fs_info->csum_root,
2648                        ds + cs, ds + cs + cl - 1,
2649                        &ordered_sums);
2650                BUG_ON(ret);
2651            }
2652        }
2653    }
2654
2655    btrfs_mark_buffer_dirty(dst_path->nodes[0]);
2656    btrfs_release_path(log, dst_path);
2657    kfree(ins_data);
2658
2659    /*
2660     * we have to do this after the loop above to avoid changing the
2661     * log tree while trying to change the log tree.
2662     */
2663    while (!list_empty(&ordered_sums)) {
2664        struct btrfs_ordered_sum *sums = list_entry(ordered_sums.next,
2665                           struct btrfs_ordered_sum,
2666                           list);
2667        ret = btrfs_csum_file_blocks(trans, log, sums);
2668        BUG_ON(ret);
2669        list_del(&sums->list);
2670        kfree(sums);
2671    }
2672    return 0;
2673}
2674
2675/* log a single inode in the tree log.
2676 * At least one parent directory for this inode must exist in the tree
2677 * or be logged already.
2678 *
2679 * Any items from this inode changed by the current transaction are copied
2680 * to the log tree. An extra reference is taken on any extents in this
2681 * file, allowing us to avoid a whole pile of corner cases around logging
2682 * blocks that have been removed from the tree.
2683 *
2684 * See LOG_INODE_ALL and related defines for a description of what inode_only
2685 * does.
2686 *
2687 * This handles both files and directories.
2688 */
2689static int btrfs_log_inode(struct btrfs_trans_handle *trans,
2690                 struct btrfs_root *root, struct inode *inode,
2691                 int inode_only)
2692{
2693    struct btrfs_path *path;
2694    struct btrfs_path *dst_path;
2695    struct btrfs_key min_key;
2696    struct btrfs_key max_key;
2697    struct btrfs_root *log = root->log_root;
2698    struct extent_buffer *src = NULL;
2699    u32 size;
2700    int ret;
2701    int nritems;
2702    int ins_start_slot = 0;
2703    int ins_nr;
2704
2705    log = root->log_root;
2706
2707    path = btrfs_alloc_path();
2708    dst_path = btrfs_alloc_path();
2709
2710    min_key.objectid = inode->i_ino;
2711    min_key.type = BTRFS_INODE_ITEM_KEY;
2712    min_key.offset = 0;
2713
2714    max_key.objectid = inode->i_ino;
2715
2716    /* today the code can only do partial logging of directories */
2717    if (!S_ISDIR(inode->i_mode))
2718        inode_only = LOG_INODE_ALL;
2719
2720    if (inode_only == LOG_INODE_EXISTS || S_ISDIR(inode->i_mode))
2721        max_key.type = BTRFS_XATTR_ITEM_KEY;
2722    else
2723        max_key.type = (u8)-1;
2724    max_key.offset = (u64)-1;
2725
2726    mutex_lock(&BTRFS_I(inode)->log_mutex);
2727
2728    /*
2729     * a brute force approach to making sure we get the most uptodate
2730     * copies of everything.
2731     */
2732    if (S_ISDIR(inode->i_mode)) {
2733        int max_key_type = BTRFS_DIR_LOG_INDEX_KEY;
2734
2735        if (inode_only == LOG_INODE_EXISTS)
2736            max_key_type = BTRFS_XATTR_ITEM_KEY;
2737        ret = drop_objectid_items(trans, log, path,
2738                      inode->i_ino, max_key_type);
2739    } else {
2740        ret = btrfs_truncate_inode_items(trans, log, inode, 0, 0);
2741    }
2742    BUG_ON(ret);
2743    path->keep_locks = 1;
2744
2745    while (1) {
2746        ins_nr = 0;
2747        ret = btrfs_search_forward(root, &min_key, &max_key,
2748                       path, 0, trans->transid);
2749        if (ret != 0)
2750            break;
2751again:
2752        /* note, ins_nr might be > 0 here, cleanup outside the loop */
2753        if (min_key.objectid != inode->i_ino)
2754            break;
2755        if (min_key.type > max_key.type)
2756            break;
2757
2758        src = path->nodes[0];
2759        size = btrfs_item_size_nr(src, path->slots[0]);
2760        if (ins_nr && ins_start_slot + ins_nr == path->slots[0]) {
2761            ins_nr++;
2762            goto next_slot;
2763        } else if (!ins_nr) {
2764            ins_start_slot = path->slots[0];
2765            ins_nr = 1;
2766            goto next_slot;
2767        }
2768
2769        ret = copy_items(trans, log, dst_path, src, ins_start_slot,
2770                 ins_nr, inode_only);
2771        BUG_ON(ret);
2772        ins_nr = 1;
2773        ins_start_slot = path->slots[0];
2774next_slot:
2775
2776        nritems = btrfs_header_nritems(path->nodes[0]);
2777        path->slots[0]++;
2778        if (path->slots[0] < nritems) {
2779            btrfs_item_key_to_cpu(path->nodes[0], &min_key,
2780                          path->slots[0]);
2781            goto again;
2782        }
2783        if (ins_nr) {
2784            ret = copy_items(trans, log, dst_path, src,
2785                     ins_start_slot,
2786                     ins_nr, inode_only);
2787            BUG_ON(ret);
2788            ins_nr = 0;
2789        }
2790        btrfs_release_path(root, path);
2791
2792        if (min_key.offset < (u64)-1)
2793            min_key.offset++;
2794        else if (min_key.type < (u8)-1)
2795            min_key.type++;
2796        else if (min_key.objectid < (u64)-1)
2797            min_key.objectid++;
2798        else
2799            break;
2800    }
2801    if (ins_nr) {
2802        ret = copy_items(trans, log, dst_path, src,
2803                 ins_start_slot,
2804                 ins_nr, inode_only);
2805        BUG_ON(ret);
2806        ins_nr = 0;
2807    }
2808    WARN_ON(ins_nr);
2809    if (inode_only == LOG_INODE_ALL && S_ISDIR(inode->i_mode)) {
2810        btrfs_release_path(root, path);
2811        btrfs_release_path(log, dst_path);
2812        ret = log_directory_changes(trans, root, inode, path, dst_path);
2813        BUG_ON(ret);
2814    }
2815    BTRFS_I(inode)->logged_trans = trans->transid;
2816    mutex_unlock(&BTRFS_I(inode)->log_mutex);
2817
2818    btrfs_free_path(path);
2819    btrfs_free_path(dst_path);
2820    return 0;
2821}
2822
2823/*
2824 * follow the dentry parent pointers up the chain and see if any
2825 * of the directories in it require a full commit before they can
2826 * be logged. Returns zero if nothing special needs to be done or 1 if
2827 * a full commit is required.
2828 */
2829static noinline int check_parent_dirs_for_sync(struct btrfs_trans_handle *trans,
2830                           struct inode *inode,
2831                           struct dentry *parent,
2832                           struct super_block *sb,
2833                           u64 last_committed)
2834{
2835    int ret = 0;
2836    struct btrfs_root *root;
2837
2838    /*
2839     * for regular files, if its inode is already on disk, we don't
2840     * have to worry about the parents at all. This is because
2841     * we can use the last_unlink_trans field to record renames
2842     * and other fun in this file.
2843     */
2844    if (S_ISREG(inode->i_mode) &&
2845        BTRFS_I(inode)->generation <= last_committed &&
2846        BTRFS_I(inode)->last_unlink_trans <= last_committed)
2847            goto out;
2848
2849    if (!S_ISDIR(inode->i_mode)) {
2850        if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
2851            goto out;
2852        inode = parent->d_inode;
2853    }
2854
2855    while (1) {
2856        BTRFS_I(inode)->logged_trans = trans->transid;
2857        smp_mb();
2858
2859        if (BTRFS_I(inode)->last_unlink_trans > last_committed) {
2860            root = BTRFS_I(inode)->root;
2861
2862            /*
2863             * make sure any commits to the log are forced
2864             * to be full commits
2865             */
2866            root->fs_info->last_trans_log_full_commit =
2867                trans->transid;
2868            ret = 1;
2869            break;
2870        }
2871
2872        if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
2873            break;
2874
2875        if (IS_ROOT(parent))
2876            break;
2877
2878        parent = parent->d_parent;
2879        inode = parent->d_inode;
2880
2881    }
2882out:
2883    return ret;
2884}
2885
2886static int inode_in_log(struct btrfs_trans_handle *trans,
2887         struct inode *inode)
2888{
2889    struct btrfs_root *root = BTRFS_I(inode)->root;
2890    int ret = 0;
2891
2892    mutex_lock(&root->log_mutex);
2893    if (BTRFS_I(inode)->logged_trans == trans->transid &&
2894        BTRFS_I(inode)->last_sub_trans <= root->last_log_commit)
2895        ret = 1;
2896    mutex_unlock(&root->log_mutex);
2897    return ret;
2898}
2899
2900
2901/*
2902 * helper function around btrfs_log_inode to make sure newly created
2903 * parent directories also end up in the log. A minimal inode and backref
2904 * only logging is done of any parent directories that are older than
2905 * the last committed transaction
2906 */
2907int btrfs_log_inode_parent(struct btrfs_trans_handle *trans,
2908            struct btrfs_root *root, struct inode *inode,
2909            struct dentry *parent, int exists_only)
2910{
2911    int inode_only = exists_only ? LOG_INODE_EXISTS : LOG_INODE_ALL;
2912    struct super_block *sb;
2913    int ret = 0;
2914    u64 last_committed = root->fs_info->last_trans_committed;
2915
2916    sb = inode->i_sb;
2917
2918    if (btrfs_test_opt(root, NOTREELOG)) {
2919        ret = 1;
2920        goto end_no_trans;
2921    }
2922
2923    if (root->fs_info->last_trans_log_full_commit >
2924        root->fs_info->last_trans_committed) {
2925        ret = 1;
2926        goto end_no_trans;
2927    }
2928
2929    if (root != BTRFS_I(inode)->root ||
2930        btrfs_root_refs(&root->root_item) == 0) {
2931        ret = 1;
2932        goto end_no_trans;
2933    }
2934
2935    ret = check_parent_dirs_for_sync(trans, inode, parent,
2936                     sb, last_committed);
2937    if (ret)
2938        goto end_no_trans;
2939
2940    if (inode_in_log(trans, inode)) {
2941        ret = BTRFS_NO_LOG_SYNC;
2942        goto end_no_trans;
2943    }
2944
2945    start_log_trans(trans, root);
2946
2947    ret = btrfs_log_inode(trans, root, inode, inode_only);
2948    BUG_ON(ret);
2949
2950    /*
2951     * for regular files, if its inode is already on disk, we don't
2952     * have to worry about the parents at all. This is because
2953     * we can use the last_unlink_trans field to record renames
2954     * and other fun in this file.
2955     */
2956    if (S_ISREG(inode->i_mode) &&
2957        BTRFS_I(inode)->generation <= last_committed &&
2958        BTRFS_I(inode)->last_unlink_trans <= last_committed)
2959            goto no_parent;
2960
2961    inode_only = LOG_INODE_EXISTS;
2962    while (1) {
2963        if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
2964            break;
2965
2966        inode = parent->d_inode;
2967        if (root != BTRFS_I(inode)->root)
2968            break;
2969
2970        if (BTRFS_I(inode)->generation >
2971            root->fs_info->last_trans_committed) {
2972            ret = btrfs_log_inode(trans, root, inode, inode_only);
2973            BUG_ON(ret);
2974        }
2975        if (IS_ROOT(parent))
2976            break;
2977
2978        parent = parent->d_parent;
2979    }
2980no_parent:
2981    ret = 0;
2982    btrfs_end_log_trans(root);
2983end_no_trans:
2984    return ret;
2985}
2986
2987/*
2988 * it is not safe to log dentry if the chunk root has added new
2989 * chunks. This returns 0 if the dentry was logged, and 1 otherwise.
2990 * If this returns 1, you must commit the transaction to safely get your
2991 * data on disk.
2992 */
2993int btrfs_log_dentry_safe(struct btrfs_trans_handle *trans,
2994              struct btrfs_root *root, struct dentry *dentry)
2995{
2996    return btrfs_log_inode_parent(trans, root, dentry->d_inode,
2997                      dentry->d_parent, 0);
2998}
2999
3000/*
3001 * should be called during mount to recover any replay any log trees
3002 * from the FS
3003 */
3004int btrfs_recover_log_trees(struct btrfs_root *log_root_tree)
3005{
3006    int ret;
3007    struct btrfs_path *path;
3008    struct btrfs_trans_handle *trans;
3009    struct btrfs_key key;
3010    struct btrfs_key found_key;
3011    struct btrfs_key tmp_key;
3012    struct btrfs_root *log;
3013    struct btrfs_fs_info *fs_info = log_root_tree->fs_info;
3014    struct walk_control wc = {
3015        .process_func = process_one_buffer,
3016        .stage = 0,
3017    };
3018
3019    fs_info->log_root_recovering = 1;
3020    path = btrfs_alloc_path();
3021    BUG_ON(!path);
3022
3023    trans = btrfs_start_transaction(fs_info->tree_root, 1);
3024
3025    wc.trans = trans;
3026    wc.pin = 1;
3027
3028    walk_log_tree(trans, log_root_tree, &wc);
3029
3030again:
3031    key.objectid = BTRFS_TREE_LOG_OBJECTID;
3032    key.offset = (u64)-1;
3033    btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
3034
3035    while (1) {
3036        ret = btrfs_search_slot(NULL, log_root_tree, &key, path, 0, 0);
3037        if (ret < 0)
3038            break;
3039        if (ret > 0) {
3040            if (path->slots[0] == 0)
3041                break;
3042            path->slots[0]--;
3043        }
3044        btrfs_item_key_to_cpu(path->nodes[0], &found_key,
3045                      path->slots[0]);
3046        btrfs_release_path(log_root_tree, path);
3047        if (found_key.objectid != BTRFS_TREE_LOG_OBJECTID)
3048            break;
3049
3050        log = btrfs_read_fs_root_no_radix(log_root_tree,
3051                          &found_key);
3052        BUG_ON(!log);
3053
3054
3055        tmp_key.objectid = found_key.offset;
3056        tmp_key.type = BTRFS_ROOT_ITEM_KEY;
3057        tmp_key.offset = (u64)-1;
3058
3059        wc.replay_dest = btrfs_read_fs_root_no_name(fs_info, &tmp_key);
3060        BUG_ON(!wc.replay_dest);
3061
3062        wc.replay_dest->log_root = log;
3063        btrfs_record_root_in_trans(trans, wc.replay_dest);
3064        ret = walk_log_tree(trans, log, &wc);
3065        BUG_ON(ret);
3066
3067        if (wc.stage == LOG_WALK_REPLAY_ALL) {
3068            ret = fixup_inode_link_counts(trans, wc.replay_dest,
3069                              path);
3070            BUG_ON(ret);
3071        }
3072
3073        key.offset = found_key.offset - 1;
3074        wc.replay_dest->log_root = NULL;
3075        free_extent_buffer(log->node);
3076        free_extent_buffer(log->commit_root);
3077        kfree(log);
3078
3079        if (found_key.offset == 0)
3080            break;
3081    }
3082    btrfs_release_path(log_root_tree, path);
3083
3084    /* step one is to pin it all, step two is to replay just inodes */
3085    if (wc.pin) {
3086        wc.pin = 0;
3087        wc.process_func = replay_one_buffer;
3088        wc.stage = LOG_WALK_REPLAY_INODES;
3089        goto again;
3090    }
3091    /* step three is to replay everything */
3092    if (wc.stage < LOG_WALK_REPLAY_ALL) {
3093        wc.stage++;
3094        goto again;
3095    }
3096
3097    btrfs_free_path(path);
3098
3099    free_extent_buffer(log_root_tree->node);
3100    log_root_tree->log_root = NULL;
3101    fs_info->log_root_recovering = 0;
3102
3103    /* step 4: commit the transaction, which also unpins the blocks */
3104    btrfs_commit_transaction(trans, fs_info->tree_root);
3105
3106    kfree(log_root_tree);
3107    return 0;
3108}
3109
3110/*
3111 * there are some corner cases where we want to force a full
3112 * commit instead of allowing a directory to be logged.
3113 *
3114 * They revolve around files there were unlinked from the directory, and
3115 * this function updates the parent directory so that a full commit is
3116 * properly done if it is fsync'd later after the unlinks are done.
3117 */
3118void btrfs_record_unlink_dir(struct btrfs_trans_handle *trans,
3119                 struct inode *dir, struct inode *inode,
3120                 int for_rename)
3121{
3122    /*
3123     * when we're logging a file, if it hasn't been renamed
3124     * or unlinked, and its inode is fully committed on disk,
3125     * we don't have to worry about walking up the directory chain
3126     * to log its parents.
3127     *
3128     * So, we use the last_unlink_trans field to put this transid
3129     * into the file. When the file is logged we check it and
3130     * don't log the parents if the file is fully on disk.
3131     */
3132    if (S_ISREG(inode->i_mode))
3133        BTRFS_I(inode)->last_unlink_trans = trans->transid;
3134
3135    /*
3136     * if this directory was already logged any new
3137     * names for this file/dir will get recorded
3138     */
3139    smp_mb();
3140    if (BTRFS_I(dir)->logged_trans == trans->transid)
3141        return;
3142
3143    /*
3144     * if the inode we're about to unlink was logged,
3145     * the log will be properly updated for any new names
3146     */
3147    if (BTRFS_I(inode)->logged_trans == trans->transid)
3148        return;
3149
3150    /*
3151     * when renaming files across directories, if the directory
3152     * there we're unlinking from gets fsync'd later on, there's
3153     * no way to find the destination directory later and fsync it
3154     * properly. So, we have to be conservative and force commits
3155     * so the new name gets discovered.
3156     */
3157    if (for_rename)
3158        goto record;
3159
3160    /* we can safely do the unlink without any special recording */
3161    return;
3162
3163record:
3164    BTRFS_I(dir)->last_unlink_trans = trans->transid;
3165}
3166
3167/*
3168 * Call this after adding a new name for a file and it will properly
3169 * update the log to reflect the new name.
3170 *
3171 * It will return zero if all goes well, and it will return 1 if a
3172 * full transaction commit is required.
3173 */
3174int btrfs_log_new_name(struct btrfs_trans_handle *trans,
3175            struct inode *inode, struct inode *old_dir,
3176            struct dentry *parent)
3177{
3178    struct btrfs_root * root = BTRFS_I(inode)->root;
3179
3180    /*
3181     * this will force the logging code to walk the dentry chain
3182     * up for the file
3183     */
3184    if (S_ISREG(inode->i_mode))
3185        BTRFS_I(inode)->last_unlink_trans = trans->transid;
3186
3187    /*
3188     * if this inode hasn't been logged and directory we're renaming it
3189     * from hasn't been logged, we don't need to log it
3190     */
3191    if (BTRFS_I(inode)->logged_trans <=
3192        root->fs_info->last_trans_committed &&
3193        (!old_dir || BTRFS_I(old_dir)->logged_trans <=
3194            root->fs_info->last_trans_committed))
3195        return 0;
3196
3197    return btrfs_log_inode_parent(trans, root, inode, parent, 1);
3198}
3199
3200

Archive Download this file



interactive