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