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