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