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