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