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