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