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