~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/tree-log.c

Version: ~ [ linux-5.11-rc3 ] ~ [ linux-5.10.7 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.89 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.167 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.215 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.251 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.251 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Copyright (C) 2008 Oracle.  All rights reserved.
  3  *
  4  * This program is free software; you can redistribute it and/or
  5  * modify it under the terms of the GNU General Public
  6  * License v2 as published by the Free Software Foundation.
  7  *
  8  * This program is distributed in the hope that it will be useful,
  9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 11  * General Public License for more details.
 12  *
 13  * You should have received a copy of the GNU General Public
 14  * License along with this program; if not, write to the
 15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 16  * Boston, MA 021110-1307, USA.
 17  */
 18 
 19 #include <linux/sched.h>
 20 #include <linux/slab.h>
 21 #include <linux/blkdev.h>
 22 #include <linux/list_sort.h>
 23 #include "ctree.h"
 24 #include "transaction.h"
 25 #include "disk-io.h"
 26 #include "locking.h"
 27 #include "print-tree.h"
 28 #include "backref.h"
 29 #include "tree-log.h"
 30 #include "hash.h"
 31 
 32 /* magic values for the inode_only field in btrfs_log_inode:
 33  *
 34  * LOG_INODE_ALL means to log everything
 35  * LOG_INODE_EXISTS means to log just enough to recreate the inode
 36  * during log replay
 37  */
 38 #define LOG_INODE_ALL 0
 39 #define LOG_INODE_EXISTS 1
 40 
 41 /*
 42  * directory trouble cases
 43  *
 44  * 1) on rename or unlink, if the inode being unlinked isn't in the fsync
 45  * log, we must force a full commit before doing an fsync of the directory
 46  * where the unlink was done.
 47  * ---> record transid of last unlink/rename per directory
 48  *
 49  * mkdir foo/some_dir
 50  * normal commit
 51  * rename foo/some_dir foo2/some_dir
 52  * mkdir foo/some_dir
 53  * fsync foo/some_dir/some_file
 54  *
 55  * The fsync above will unlink the original some_dir without recording
 56  * it in its new location (foo2).  After a crash, some_dir will be gone
 57  * unless the fsync of some_file forces a full commit
 58  *
 59  * 2) we must log any new names for any file or dir that is in the fsync
 60  * log. ---> check inode while renaming/linking.
 61  *
 62  * 2a) we must log any new names for any file or dir during rename
 63  * when the directory they are being removed from was logged.
 64  * ---> check inode and old parent dir during rename
 65  *
 66  *  2a is actually the more important variant.  With the extra logging
 67  *  a crash might unlink the old name without recreating the new one
 68  *
 69  * 3) after a crash, we must go through any directories with a link count
 70  * of zero and redo the rm -rf
 71  *
 72  * mkdir f1/foo
 73  * normal commit
 74  * rm -rf f1/foo
 75  * fsync(f1)
 76  *
 77  * The directory f1 was fully removed from the FS, but fsync was never
 78  * called on f1, only its parent dir.  After a crash the rm -rf must
 79  * be replayed.  This must be able to recurse down the entire
 80  * directory tree.  The inode link count fixup code takes care of the
 81  * ugly details.
 82  */
 83 
 84 /*
 85  * stages for the tree walking.  The first
 86  * stage (0) is to only pin down the blocks we find
 87  * the second stage (1) is to make sure that all the inodes
 88  * we find in the log are created in the subvolume.
 89  *
 90  * The last stage is to deal with directories and links and extents
 91  * and all the other fun semantics
 92  */
 93 #define LOG_WALK_PIN_ONLY 0
 94 #define LOG_WALK_REPLAY_INODES 1
 95 #define LOG_WALK_REPLAY_DIR_INDEX 2
 96 #define LOG_WALK_REPLAY_ALL 3
 97 
 98 static int btrfs_log_inode(struct btrfs_trans_handle *trans,
 99                              struct btrfs_root *root, struct inode *inode,
100                              int inode_only);
101 static int link_to_fixup_dir(struct btrfs_trans_handle *trans,
102                              struct btrfs_root *root,
103                              struct btrfs_path *path, u64 objectid);
104 static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
105                                        struct btrfs_root *root,
106                                        struct btrfs_root *log,
107                                        struct btrfs_path *path,
108                                        u64 dirid, int del_all);
109 
110 /*
111  * tree logging is a special write ahead log used to make sure that
112  * fsyncs and O_SYNCs can happen without doing full tree commits.
113  *
114  * Full tree commits are expensive because they require commonly
115  * modified blocks to be recowed, creating many dirty pages in the
116  * extent tree an 4x-6x higher write load than ext3.
117  *
118  * Instead of doing a tree commit on every fsync, we use the
119  * key ranges and transaction ids to find items for a given file or directory
120  * that have changed in this transaction.  Those items are copied into
121  * a special tree (one per subvolume root), that tree is written to disk
122  * and then the fsync is considered complete.
123  *
124  * After a crash, items are copied out of the log-tree back into the
125  * subvolume tree.  Any file data extents found are recorded in the extent
126  * allocation tree, and the log-tree freed.
127  *
128  * The log tree is read three times, once to pin down all the extents it is
129  * using in ram and once, once to create all the inodes logged in the tree
130  * and once to do all the other items.
131  */
132 
133 /*
134  * start a sub transaction and setup the log tree
135  * this increments the log tree writer count to make the people
136  * syncing the tree wait for us to finish
137  */
138 static int start_log_trans(struct btrfs_trans_handle *trans,
139                            struct btrfs_root *root)
140 {
141         int ret;
142         int err = 0;
143 
144         mutex_lock(&root->log_mutex);
145         if (root->log_root) {
146                 if (!root->log_start_pid) {
147                         root->log_start_pid = current->pid;
148                         root->log_multiple_pids = false;
149                 } else if (root->log_start_pid != current->pid) {
150                         root->log_multiple_pids = true;
151                 }
152 
153                 atomic_inc(&root->log_batch);
154                 atomic_inc(&root->log_writers);
155                 mutex_unlock(&root->log_mutex);
156                 return 0;
157         }
158         root->log_multiple_pids = false;
159         root->log_start_pid = current->pid;
160         mutex_lock(&root->fs_info->tree_log_mutex);
161         if (!root->fs_info->log_root_tree) {
162                 ret = btrfs_init_log_root_tree(trans, root->fs_info);
163                 if (ret)
164                         err = ret;
165         }
166         if (err == 0 && !root->log_root) {
167                 ret = btrfs_add_log_tree(trans, root);
168                 if (ret)
169                         err = ret;
170         }
171         mutex_unlock(&root->fs_info->tree_log_mutex);
172         atomic_inc(&root->log_batch);
173         atomic_inc(&root->log_writers);
174         mutex_unlock(&root->log_mutex);
175         return err;
176 }
177 
178 /*
179  * returns 0 if there was a log transaction running and we were able
180  * to join, or returns -ENOENT if there were not transactions
181  * in progress
182  */
183 static int join_running_log_trans(struct btrfs_root *root)
184 {
185         int ret = -ENOENT;
186 
187         smp_mb();
188         if (!root->log_root)
189                 return -ENOENT;
190 
191         mutex_lock(&root->log_mutex);
192         if (root->log_root) {
193                 ret = 0;
194                 atomic_inc(&root->log_writers);
195         }
196         mutex_unlock(&root->log_mutex);
197         return ret;
198 }
199 
200 /*
201  * This either makes the current running log transaction wait
202  * until you call btrfs_end_log_trans() or it makes any future
203  * log transactions wait until you call btrfs_end_log_trans()
204  */
205 int btrfs_pin_log_trans(struct btrfs_root *root)
206 {
207         int ret = -ENOENT;
208 
209         mutex_lock(&root->log_mutex);
210         atomic_inc(&root->log_writers);
211         mutex_unlock(&root->log_mutex);
212         return ret;
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                 smp_mb();
223                 if (waitqueue_active(&root->log_writer_wait))
224                         wake_up(&root->log_writer_wait);
225         }
226 }
227 
228 
229 /*
230  * the walk control struct is used to pass state down the chain when
231  * processing the log tree.  The stage field tells us which part
232  * of the log tree processing we are currently doing.  The others
233  * are state fields used for that specific part
234  */
235 struct walk_control {
236         /* should we free the extent on disk when done?  This is used
237          * at transaction commit time while freeing a log tree
238          */
239         int free;
240 
241         /* should we write out the extent buffer?  This is used
242          * while flushing the log tree to disk during a sync
243          */
244         int write;
245 
246         /* should we wait for the extent buffer io to finish?  Also used
247          * while flushing the log tree to disk for a sync
248          */
249         int wait;
250 
251         /* pin only walk, we record which extents on disk belong to the
252          * log trees
253          */
254         int pin;
255 
256         /* what stage of the replay code we're currently in */
257         int stage;
258 
259         /* the root we are currently replaying */
260         struct btrfs_root *replay_dest;
261 
262         /* the trans handle for the current replay */
263         struct btrfs_trans_handle *trans;
264 
265         /* the function that gets used to process blocks we find in the
266          * tree.  Note the extent_buffer might not be up to date when it is
267          * passed in, and it must be checked or read if you need the data
268          * inside it
269          */
270         int (*process_func)(struct btrfs_root *log, struct extent_buffer *eb,
271                             struct walk_control *wc, u64 gen);
272 };
273 
274 /*
275  * process_func used to pin down extents, write them or wait on them
276  */
277 static int process_one_buffer(struct btrfs_root *log,
278                               struct extent_buffer *eb,
279                               struct walk_control *wc, u64 gen)
280 {
281         int ret = 0;
282 
283         /*
284          * If this fs is mixed then we need to be able to process the leaves to
285          * pin down any logged extents, so we have to read the block.
286          */
287         if (btrfs_fs_incompat(log->fs_info, MIXED_GROUPS)) {
288                 ret = btrfs_read_buffer(eb, gen);
289                 if (ret)
290                         return ret;
291         }
292 
293         if (wc->pin)
294                 ret = btrfs_pin_extent_for_log_replay(log->fs_info->extent_root,
295                                                       eb->start, eb->len);
296 
297         if (!ret && btrfs_buffer_uptodate(eb, gen, 0)) {
298                 if (wc->pin && btrfs_header_level(eb) == 0)
299                         ret = btrfs_exclude_logged_extents(log, eb);
300                 if (wc->write)
301                         btrfs_write_tree_block(eb);
302                 if (wc->wait)
303                         btrfs_wait_tree_block_writeback(eb);
304         }
305         return ret;
306 }
307 
308 /*
309  * Item overwrite used by replay and tree logging.  eb, slot and key all refer
310  * to the src data we are copying out.
311  *
312  * root is the tree we are copying into, and path is a scratch
313  * path for use in this function (it should be released on entry and
314  * will be released on exit).
315  *
316  * If the key is already in the destination tree the existing item is
317  * overwritten.  If the existing item isn't big enough, it is extended.
318  * If it is too large, it is truncated.
319  *
320  * If the key isn't in the destination yet, a new item is inserted.
321  */
322 static noinline int overwrite_item(struct btrfs_trans_handle *trans,
323                                    struct btrfs_root *root,
324                                    struct btrfs_path *path,
325                                    struct extent_buffer *eb, int slot,
326                                    struct btrfs_key *key)
327 {
328         int ret;
329         u32 item_size;
330         u64 saved_i_size = 0;
331         int save_old_i_size = 0;
332         unsigned long src_ptr;
333         unsigned long dst_ptr;
334         int overwrite_root = 0;
335         bool inode_item = key->type == BTRFS_INODE_ITEM_KEY;
336 
337         if (root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
338                 overwrite_root = 1;
339 
340         item_size = btrfs_item_size_nr(eb, slot);
341         src_ptr = btrfs_item_ptr_offset(eb, slot);
342 
343         /* look for the key in the destination tree */
344         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
345         if (ret < 0)
346                 return ret;
347 
348         if (ret == 0) {
349                 char *src_copy;
350                 char *dst_copy;
351                 u32 dst_size = btrfs_item_size_nr(path->nodes[0],
352                                                   path->slots[0]);
353                 if (dst_size != item_size)
354                         goto insert;
355 
356                 if (item_size == 0) {
357                         btrfs_release_path(path);
358                         return 0;
359                 }
360                 dst_copy = kmalloc(item_size, GFP_NOFS);
361                 src_copy = kmalloc(item_size, GFP_NOFS);
362                 if (!dst_copy || !src_copy) {
363                         btrfs_release_path(path);
364                         kfree(dst_copy);
365                         kfree(src_copy);
366                         return -ENOMEM;
367                 }
368 
369                 read_extent_buffer(eb, src_copy, src_ptr, item_size);
370 
371                 dst_ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
372                 read_extent_buffer(path->nodes[0], dst_copy, dst_ptr,
373                                    item_size);
374                 ret = memcmp(dst_copy, src_copy, item_size);
375 
376                 kfree(dst_copy);
377                 kfree(src_copy);
378                 /*
379                  * they have the same contents, just return, this saves
380                  * us from cowing blocks in the destination tree and doing
381                  * extra writes that may not have been done by a previous
382                  * sync
383                  */
384                 if (ret == 0) {
385                         btrfs_release_path(path);
386                         return 0;
387                 }
388 
389                 /*
390                  * We need to load the old nbytes into the inode so when we
391                  * replay the extents we've logged we get the right nbytes.
392                  */
393                 if (inode_item) {
394                         struct btrfs_inode_item *item;
395                         u64 nbytes;
396                         u32 mode;
397 
398                         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
399                                               struct btrfs_inode_item);
400                         nbytes = btrfs_inode_nbytes(path->nodes[0], item);
401                         item = btrfs_item_ptr(eb, slot,
402                                               struct btrfs_inode_item);
403                         btrfs_set_inode_nbytes(eb, item, nbytes);
404 
405                         /*
406                          * If this is a directory we need to reset the i_size to
407                          * 0 so that we can set it up properly when replaying
408                          * the rest of the items in this log.
409                          */
410                         mode = btrfs_inode_mode(eb, item);
411                         if (S_ISDIR(mode))
412                                 btrfs_set_inode_size(eb, item, 0);
413                 }
414         } else if (inode_item) {
415                 struct btrfs_inode_item *item;
416                 u32 mode;
417 
418                 /*
419                  * New inode, set nbytes to 0 so that the nbytes comes out
420                  * properly when we replay the extents.
421                  */
422                 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
423                 btrfs_set_inode_nbytes(eb, item, 0);
424 
425                 /*
426                  * If this is a directory we need to reset the i_size to 0 so
427                  * that we can set it up properly when replaying the rest of
428                  * the items in this log.
429                  */
430                 mode = btrfs_inode_mode(eb, item);
431                 if (S_ISDIR(mode))
432                         btrfs_set_inode_size(eb, item, 0);
433         }
434 insert:
435         btrfs_release_path(path);
436         /* try to insert the key into the destination tree */
437         ret = btrfs_insert_empty_item(trans, root, path,
438                                       key, item_size);
439 
440         /* make sure any existing item is the correct size */
441         if (ret == -EEXIST) {
442                 u32 found_size;
443                 found_size = btrfs_item_size_nr(path->nodes[0],
444                                                 path->slots[0]);
445                 if (found_size > item_size)
446                         btrfs_truncate_item(root, path, item_size, 1);
447                 else if (found_size < item_size)
448                         btrfs_extend_item(root, path,
449                                           item_size - found_size);
450         } else if (ret) {
451                 return ret;
452         }
453         dst_ptr = btrfs_item_ptr_offset(path->nodes[0],
454                                         path->slots[0]);
455 
456         /* don't overwrite an existing inode if the generation number
457          * was logged as zero.  This is done when the tree logging code
458          * is just logging an inode to make sure it exists after recovery.
459          *
460          * Also, don't overwrite i_size on directories during replay.
461          * log replay inserts and removes directory items based on the
462          * state of the tree found in the subvolume, and i_size is modified
463          * as it goes
464          */
465         if (key->type == BTRFS_INODE_ITEM_KEY && ret == -EEXIST) {
466                 struct btrfs_inode_item *src_item;
467                 struct btrfs_inode_item *dst_item;
468 
469                 src_item = (struct btrfs_inode_item *)src_ptr;
470                 dst_item = (struct btrfs_inode_item *)dst_ptr;
471 
472                 if (btrfs_inode_generation(eb, src_item) == 0)
473                         goto no_copy;
474 
475                 if (overwrite_root &&
476                     S_ISDIR(btrfs_inode_mode(eb, src_item)) &&
477                     S_ISDIR(btrfs_inode_mode(path->nodes[0], dst_item))) {
478                         save_old_i_size = 1;
479                         saved_i_size = btrfs_inode_size(path->nodes[0],
480                                                         dst_item);
481                 }
482         }
483 
484         copy_extent_buffer(path->nodes[0], eb, dst_ptr,
485                            src_ptr, item_size);
486 
487         if (save_old_i_size) {
488                 struct btrfs_inode_item *dst_item;
489                 dst_item = (struct btrfs_inode_item *)dst_ptr;
490                 btrfs_set_inode_size(path->nodes[0], dst_item, saved_i_size);
491         }
492 
493         /* make sure the generation is filled in */
494         if (key->type == BTRFS_INODE_ITEM_KEY) {
495                 struct btrfs_inode_item *dst_item;
496                 dst_item = (struct btrfs_inode_item *)dst_ptr;
497                 if (btrfs_inode_generation(path->nodes[0], dst_item) == 0) {
498                         btrfs_set_inode_generation(path->nodes[0], dst_item,
499                                                    trans->transid);
500                 }
501         }
502 no_copy:
503         btrfs_mark_buffer_dirty(path->nodes[0]);
504         btrfs_release_path(path);
505         return 0;
506 }
507 
508 /*
509  * simple helper to read an inode off the disk from a given root
510  * This can only be called for subvolume roots and not for the log
511  */
512 static noinline struct inode *read_one_inode(struct btrfs_root *root,
513                                              u64 objectid)
514 {
515         struct btrfs_key key;
516         struct inode *inode;
517 
518         key.objectid = objectid;
519         key.type = BTRFS_INODE_ITEM_KEY;
520         key.offset = 0;
521         inode = btrfs_iget(root->fs_info->sb, &key, root, NULL);
522         if (IS_ERR(inode)) {
523                 inode = NULL;
524         } else if (is_bad_inode(inode)) {
525                 iput(inode);
526                 inode = NULL;
527         }
528         return inode;
529 }
530 
531 /* replays a single extent in 'eb' at 'slot' with 'key' into the
532  * subvolume 'root'.  path is released on entry and should be released
533  * on exit.
534  *
535  * extents in the log tree have not been allocated out of the extent
536  * tree yet.  So, this completes the allocation, taking a reference
537  * as required if the extent already exists or creating a new extent
538  * if it isn't in the extent allocation tree yet.
539  *
540  * The extent is inserted into the file, dropping any existing extents
541  * from the file that overlap the new one.
542  */
543 static noinline int replay_one_extent(struct btrfs_trans_handle *trans,
544                                       struct btrfs_root *root,
545                                       struct btrfs_path *path,
546                                       struct extent_buffer *eb, int slot,
547                                       struct btrfs_key *key)
548 {
549         int found_type;
550         u64 extent_end;
551         u64 start = key->offset;
552         u64 nbytes = 0;
553         struct btrfs_file_extent_item *item;
554         struct inode *inode = NULL;
555         unsigned long size;
556         int ret = 0;
557 
558         item = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
559         found_type = btrfs_file_extent_type(eb, item);
560 
561         if (found_type == BTRFS_FILE_EXTENT_REG ||
562             found_type == BTRFS_FILE_EXTENT_PREALLOC) {
563                 nbytes = btrfs_file_extent_num_bytes(eb, item);
564                 extent_end = start + nbytes;
565 
566                 /*
567                  * We don't add to the inodes nbytes if we are prealloc or a
568                  * hole.
569                  */
570                 if (btrfs_file_extent_disk_bytenr(eb, item) == 0)
571                         nbytes = 0;
572         } else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
573                 size = btrfs_file_extent_inline_len(eb, slot, item);
574                 nbytes = btrfs_file_extent_ram_bytes(eb, item);
575                 extent_end = ALIGN(start + size, root->sectorsize);
576         } else {
577                 ret = 0;
578                 goto out;
579         }
580 
581         inode = read_one_inode(root, key->objectid);
582         if (!inode) {
583                 ret = -EIO;
584                 goto out;
585         }
586 
587         /*
588          * first check to see if we already have this extent in the
589          * file.  This must be done before the btrfs_drop_extents run
590          * so we don't try to drop this extent.
591          */
592         ret = btrfs_lookup_file_extent(trans, root, path, btrfs_ino(inode),
593                                        start, 0);
594 
595         if (ret == 0 &&
596             (found_type == BTRFS_FILE_EXTENT_REG ||
597              found_type == BTRFS_FILE_EXTENT_PREALLOC)) {
598                 struct btrfs_file_extent_item cmp1;
599                 struct btrfs_file_extent_item cmp2;
600                 struct btrfs_file_extent_item *existing;
601                 struct extent_buffer *leaf;
602 
603                 leaf = path->nodes[0];
604                 existing = btrfs_item_ptr(leaf, path->slots[0],
605                                           struct btrfs_file_extent_item);
606 
607                 read_extent_buffer(eb, &cmp1, (unsigned long)item,
608                                    sizeof(cmp1));
609                 read_extent_buffer(leaf, &cmp2, (unsigned long)existing,
610                                    sizeof(cmp2));
611 
612                 /*
613                  * we already have a pointer to this exact extent,
614                  * we don't have to do anything
615                  */
616                 if (memcmp(&cmp1, &cmp2, sizeof(cmp1)) == 0) {
617                         btrfs_release_path(path);
618                         goto out;
619                 }
620         }
621         btrfs_release_path(path);
622 
623         /* drop any overlapping extents */
624         ret = btrfs_drop_extents(trans, root, inode, start, extent_end, 1);
625         if (ret)
626                 goto out;
627 
628         if (found_type == BTRFS_FILE_EXTENT_REG ||
629             found_type == BTRFS_FILE_EXTENT_PREALLOC) {
630                 u64 offset;
631                 unsigned long dest_offset;
632                 struct btrfs_key ins;
633 
634                 ret = btrfs_insert_empty_item(trans, root, path, key,
635                                               sizeof(*item));
636                 if (ret)
637                         goto out;
638                 dest_offset = btrfs_item_ptr_offset(path->nodes[0],
639                                                     path->slots[0]);
640                 copy_extent_buffer(path->nodes[0], eb, dest_offset,
641                                 (unsigned long)item,  sizeof(*item));
642 
643                 ins.objectid = btrfs_file_extent_disk_bytenr(eb, item);
644                 ins.offset = btrfs_file_extent_disk_num_bytes(eb, item);
645                 ins.type = BTRFS_EXTENT_ITEM_KEY;
646                 offset = key->offset - btrfs_file_extent_offset(eb, item);
647 
648                 if (ins.objectid > 0) {
649                         u64 csum_start;
650                         u64 csum_end;
651                         LIST_HEAD(ordered_sums);
652                         /*
653                          * is this extent already allocated in the extent
654                          * allocation tree?  If so, just add a reference
655                          */
656                         ret = btrfs_lookup_extent(root, ins.objectid,
657                                                 ins.offset);
658                         if (ret == 0) {
659                                 ret = btrfs_inc_extent_ref(trans, root,
660                                                 ins.objectid, ins.offset,
661                                                 0, root->root_key.objectid,
662                                                 key->objectid, offset, 0);
663                                 if (ret)
664                                         goto out;
665                         } else {
666                                 /*
667                                  * insert the extent pointer in the extent
668                                  * allocation tree
669                                  */
670                                 ret = btrfs_alloc_logged_file_extent(trans,
671                                                 root, root->root_key.objectid,
672                                                 key->objectid, offset, &ins);
673                                 if (ret)
674                                         goto out;
675                         }
676                         btrfs_release_path(path);
677 
678                         if (btrfs_file_extent_compression(eb, item)) {
679                                 csum_start = ins.objectid;
680                                 csum_end = csum_start + ins.offset;
681                         } else {
682                                 csum_start = ins.objectid +
683                                         btrfs_file_extent_offset(eb, item);
684                                 csum_end = csum_start +
685                                         btrfs_file_extent_num_bytes(eb, item);
686                         }
687 
688                         ret = btrfs_lookup_csums_range(root->log_root,
689                                                 csum_start, csum_end - 1,
690                                                 &ordered_sums, 0);
691                         if (ret)
692                                 goto out;
693                         while (!list_empty(&ordered_sums)) {
694                                 struct btrfs_ordered_sum *sums;
695                                 sums = list_entry(ordered_sums.next,
696                                                 struct btrfs_ordered_sum,
697                                                 list);
698                                 if (!ret)
699                                         ret = btrfs_csum_file_blocks(trans,
700                                                 root->fs_info->csum_root,
701                                                 sums);
702                                 list_del(&sums->list);
703                                 kfree(sums);
704                         }
705                         if (ret)
706                                 goto out;
707                 } else {
708                         btrfs_release_path(path);
709                 }
710         } else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
711                 /* inline extents are easy, we just overwrite them */
712                 ret = overwrite_item(trans, root, path, eb, slot, key);
713                 if (ret)
714                         goto out;
715         }
716 
717         inode_add_bytes(inode, nbytes);
718         ret = btrfs_update_inode(trans, root, inode);
719 out:
720         if (inode)
721                 iput(inode);
722         return ret;
723 }
724 
725 /*
726  * when cleaning up conflicts between the directory names in the
727  * subvolume, directory names in the log and directory names in the
728  * inode back references, we may have to unlink inodes from directories.
729  *
730  * This is a helper function to do the unlink of a specific directory
731  * item
732  */
733 static noinline int drop_one_dir_item(struct btrfs_trans_handle *trans,
734                                       struct btrfs_root *root,
735                                       struct btrfs_path *path,
736                                       struct inode *dir,
737                                       struct btrfs_dir_item *di)
738 {
739         struct inode *inode;
740         char *name;
741         int name_len;
742         struct extent_buffer *leaf;
743         struct btrfs_key location;
744         int ret;
745 
746         leaf = path->nodes[0];
747 
748         btrfs_dir_item_key_to_cpu(leaf, di, &location);
749         name_len = btrfs_dir_name_len(leaf, di);
750         name = kmalloc(name_len, GFP_NOFS);
751         if (!name)
752                 return -ENOMEM;
753 
754         read_extent_buffer(leaf, name, (unsigned long)(di + 1), name_len);
755         btrfs_release_path(path);
756 
757         inode = read_one_inode(root, location.objectid);
758         if (!inode) {
759                 ret = -EIO;
760                 goto out;
761         }
762 
763         ret = link_to_fixup_dir(trans, root, path, location.objectid);
764         if (ret)
765                 goto out;
766 
767         ret = btrfs_unlink_inode(trans, root, dir, inode, name, name_len);
768         if (ret)
769                 goto out;
770         else
771                 ret = btrfs_run_delayed_items(trans, root);
772 out:
773         kfree(name);
774         iput(inode);
775         return ret;
776 }
777 
778 /*
779  * helper function to see if a given name and sequence number found
780  * in an inode back reference are already in a directory and correctly
781  * point to this inode
782  */
783 static noinline int inode_in_dir(struct btrfs_root *root,
784                                  struct btrfs_path *path,
785                                  u64 dirid, u64 objectid, u64 index,
786                                  const char *name, int name_len)
787 {
788         struct btrfs_dir_item *di;
789         struct btrfs_key location;
790         int match = 0;
791 
792         di = btrfs_lookup_dir_index_item(NULL, root, path, dirid,
793                                          index, name, name_len, 0);
794         if (di && !IS_ERR(di)) {
795                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
796                 if (location.objectid != objectid)
797                         goto out;
798         } else
799                 goto out;
800         btrfs_release_path(path);
801 
802         di = btrfs_lookup_dir_item(NULL, root, path, dirid, name, name_len, 0);
803         if (di && !IS_ERR(di)) {
804                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
805                 if (location.objectid != objectid)
806                         goto out;
807         } else
808                 goto out;
809         match = 1;
810 out:
811         btrfs_release_path(path);
812         return match;
813 }
814 
815 /*
816  * helper function to check a log tree for a named back reference in
817  * an inode.  This is used to decide if a back reference that is
818  * found in the subvolume conflicts with what we find in the log.
819  *
820  * inode backreferences may have multiple refs in a single item,
821  * during replay we process one reference at a time, and we don't
822  * want to delete valid links to a file from the subvolume if that
823  * link is also in the log.
824  */
825 static noinline int backref_in_log(struct btrfs_root *log,
826                                    struct btrfs_key *key,
827                                    u64 ref_objectid,
828                                    char *name, int namelen)
829 {
830         struct btrfs_path *path;
831         struct btrfs_inode_ref *ref;
832         unsigned long ptr;
833         unsigned long ptr_end;
834         unsigned long name_ptr;
835         int found_name_len;
836         int item_size;
837         int ret;
838         int match = 0;
839 
840         path = btrfs_alloc_path();
841         if (!path)
842                 return -ENOMEM;
843 
844         ret = btrfs_search_slot(NULL, log, key, path, 0, 0);
845         if (ret != 0)
846                 goto out;
847 
848         ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
849 
850         if (key->type == BTRFS_INODE_EXTREF_KEY) {
851                 if (btrfs_find_name_in_ext_backref(path, ref_objectid,
852                                                    name, namelen, NULL))
853                         match = 1;
854 
855                 goto out;
856         }
857 
858         item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
859         ptr_end = ptr + item_size;
860         while (ptr < ptr_end) {
861                 ref = (struct btrfs_inode_ref *)ptr;
862                 found_name_len = btrfs_inode_ref_name_len(path->nodes[0], ref);
863                 if (found_name_len == namelen) {
864                         name_ptr = (unsigned long)(ref + 1);
865                         ret = memcmp_extent_buffer(path->nodes[0], name,
866                                                    name_ptr, namelen);
867                         if (ret == 0) {
868                                 match = 1;
869                                 goto out;
870                         }
871                 }
872                 ptr = (unsigned long)(ref + 1) + found_name_len;
873         }
874 out:
875         btrfs_free_path(path);
876         return match;
877 }
878 
879 static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
880                                   struct btrfs_root *root,
881                                   struct btrfs_path *path,
882                                   struct btrfs_root *log_root,
883                                   struct inode *dir, struct inode *inode,
884                                   struct extent_buffer *eb,
885                                   u64 inode_objectid, u64 parent_objectid,
886                                   u64 ref_index, char *name, int namelen,
887                                   int *search_done)
888 {
889         int ret;
890         char *victim_name;
891         int victim_name_len;
892         struct extent_buffer *leaf;
893         struct btrfs_dir_item *di;
894         struct btrfs_key search_key;
895         struct btrfs_inode_extref *extref;
896 
897 again:
898         /* Search old style refs */
899         search_key.objectid = inode_objectid;
900         search_key.type = BTRFS_INODE_REF_KEY;
901         search_key.offset = parent_objectid;
902         ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
903         if (ret == 0) {
904                 struct btrfs_inode_ref *victim_ref;
905                 unsigned long ptr;
906                 unsigned long ptr_end;
907 
908                 leaf = path->nodes[0];
909 
910                 /* are we trying to overwrite a back ref for the root directory
911                  * if so, just jump out, we're done
912                  */
913                 if (search_key.objectid == search_key.offset)
914                         return 1;
915 
916                 /* check all the names in this back reference to see
917                  * if they are in the log.  if so, we allow them to stay
918                  * otherwise they must be unlinked as a conflict
919                  */
920                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
921                 ptr_end = ptr + btrfs_item_size_nr(leaf, path->slots[0]);
922                 while (ptr < ptr_end) {
923                         victim_ref = (struct btrfs_inode_ref *)ptr;
924                         victim_name_len = btrfs_inode_ref_name_len(leaf,
925                                                                    victim_ref);
926                         victim_name = kmalloc(victim_name_len, GFP_NOFS);
927                         if (!victim_name)
928                                 return -ENOMEM;
929 
930                         read_extent_buffer(leaf, victim_name,
931                                            (unsigned long)(victim_ref + 1),
932                                            victim_name_len);
933 
934                         if (!backref_in_log(log_root, &search_key,
935                                             parent_objectid,
936                                             victim_name,
937                                             victim_name_len)) {
938                                 inc_nlink(inode);
939                                 btrfs_release_path(path);
940 
941                                 ret = btrfs_unlink_inode(trans, root, dir,
942                                                          inode, victim_name,
943                                                          victim_name_len);
944                                 kfree(victim_name);
945                                 if (ret)
946                                         return ret;
947                                 ret = btrfs_run_delayed_items(trans, root);
948                                 if (ret)
949                                         return ret;
950                                 *search_done = 1;
951                                 goto again;
952                         }
953                         kfree(victim_name);
954 
955                         ptr = (unsigned long)(victim_ref + 1) + victim_name_len;
956                 }
957 
958                 /*
959                  * NOTE: we have searched root tree and checked the
960                  * coresponding ref, it does not need to check again.
961                  */
962                 *search_done = 1;
963         }
964         btrfs_release_path(path);
965 
966         /* Same search but for extended refs */
967         extref = btrfs_lookup_inode_extref(NULL, root, path, name, namelen,
968                                            inode_objectid, parent_objectid, 0,
969                                            0);
970         if (!IS_ERR_OR_NULL(extref)) {
971                 u32 item_size;
972                 u32 cur_offset = 0;
973                 unsigned long base;
974                 struct inode *victim_parent;
975 
976                 leaf = path->nodes[0];
977 
978                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
979                 base = btrfs_item_ptr_offset(leaf, path->slots[0]);
980 
981                 while (cur_offset < item_size) {
982                         extref = (struct btrfs_inode_extref *)(base + cur_offset);
983 
984                         victim_name_len = btrfs_inode_extref_name_len(leaf, extref);
985 
986                         if (btrfs_inode_extref_parent(leaf, extref) != parent_objectid)
987                                 goto next;
988 
989                         victim_name = kmalloc(victim_name_len, GFP_NOFS);
990                         if (!victim_name)
991                                 return -ENOMEM;
992                         read_extent_buffer(leaf, victim_name, (unsigned long)&extref->name,
993                                            victim_name_len);
994 
995                         search_key.objectid = inode_objectid;
996                         search_key.type = BTRFS_INODE_EXTREF_KEY;
997                         search_key.offset = btrfs_extref_hash(parent_objectid,
998                                                               victim_name,
999                                                               victim_name_len);
1000                         ret = 0;
1001                         if (!backref_in_log(log_root, &search_key,
1002                                             parent_objectid, victim_name,
1003                                             victim_name_len)) {
1004                                 ret = -ENOENT;
1005                                 victim_parent = read_one_inode(root,
1006                                                                parent_objectid);
1007                                 if (victim_parent) {
1008                                         inc_nlink(inode);
1009                                         btrfs_release_path(path);
1010 
1011                                         ret = btrfs_unlink_inode(trans, root,
1012                                                                  victim_parent,
1013                                                                  inode,
1014                                                                  victim_name,
1015                                                                  victim_name_len);
1016                                         if (!ret)
1017                                                 ret = btrfs_run_delayed_items(
1018                                                                   trans, root);
1019                                 }
1020                                 iput(victim_parent);
1021                                 kfree(victim_name);
1022                                 if (ret)
1023                                         return ret;
1024                                 *search_done = 1;
1025                                 goto again;
1026                         }
1027                         kfree(victim_name);
1028                         if (ret)
1029                                 return ret;
1030 next:
1031                         cur_offset += victim_name_len + sizeof(*extref);
1032                 }
1033                 *search_done = 1;
1034         }
1035         btrfs_release_path(path);
1036 
1037         /* look for a conflicting sequence number */
1038         di = btrfs_lookup_dir_index_item(trans, root, path, btrfs_ino(dir),
1039                                          ref_index, name, namelen, 0);
1040         if (di && !IS_ERR(di)) {
1041                 ret = drop_one_dir_item(trans, root, path, dir, di);
1042                 if (ret)
1043                         return ret;
1044         }
1045         btrfs_release_path(path);
1046 
1047         /* look for a conflicing name */
1048         di = btrfs_lookup_dir_item(trans, root, path, btrfs_ino(dir),
1049                                    name, namelen, 0);
1050         if (di && !IS_ERR(di)) {
1051                 ret = drop_one_dir_item(trans, root, path, dir, di);
1052                 if (ret)
1053                         return ret;
1054         }
1055         btrfs_release_path(path);
1056 
1057         return 0;
1058 }
1059 
1060 static int extref_get_fields(struct extent_buffer *eb, unsigned long ref_ptr,
1061                              u32 *namelen, char **name, u64 *index,
1062                              u64 *parent_objectid)
1063 {
1064         struct btrfs_inode_extref *extref;
1065 
1066         extref = (struct btrfs_inode_extref *)ref_ptr;
1067 
1068         *namelen = btrfs_inode_extref_name_len(eb, extref);
1069         *name = kmalloc(*namelen, GFP_NOFS);
1070         if (*name == NULL)
1071                 return -ENOMEM;
1072 
1073         read_extent_buffer(eb, *name, (unsigned long)&extref->name,
1074                            *namelen);
1075 
1076         *index = btrfs_inode_extref_index(eb, extref);
1077         if (parent_objectid)
1078                 *parent_objectid = btrfs_inode_extref_parent(eb, extref);
1079 
1080         return 0;
1081 }
1082 
1083 static int ref_get_fields(struct extent_buffer *eb, unsigned long ref_ptr,
1084                           u32 *namelen, char **name, u64 *index)
1085 {
1086         struct btrfs_inode_ref *ref;
1087 
1088         ref = (struct btrfs_inode_ref *)ref_ptr;
1089 
1090         *namelen = btrfs_inode_ref_name_len(eb, ref);
1091         *name = kmalloc(*namelen, GFP_NOFS);
1092         if (*name == NULL)
1093                 return -ENOMEM;
1094 
1095         read_extent_buffer(eb, *name, (unsigned long)(ref + 1), *namelen);
1096 
1097         *index = btrfs_inode_ref_index(eb, ref);
1098 
1099         return 0;
1100 }
1101 
1102 /*
1103  * replay one inode back reference item found in the log tree.
1104  * eb, slot and key refer to the buffer and key found in the log tree.
1105  * root is the destination we are replaying into, and path is for temp
1106  * use by this function.  (it should be released on return).
1107  */
1108 static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
1109                                   struct btrfs_root *root,
1110                                   struct btrfs_root *log,
1111                                   struct btrfs_path *path,
1112                                   struct extent_buffer *eb, int slot,
1113                                   struct btrfs_key *key)
1114 {
1115         struct inode *dir = NULL;
1116         struct inode *inode = NULL;
1117         unsigned long ref_ptr;
1118         unsigned long ref_end;
1119         char *name = NULL;
1120         int namelen;
1121         int ret;
1122         int search_done = 0;
1123         int log_ref_ver = 0;
1124         u64 parent_objectid;
1125         u64 inode_objectid;
1126         u64 ref_index = 0;
1127         int ref_struct_size;
1128 
1129         ref_ptr = btrfs_item_ptr_offset(eb, slot);
1130         ref_end = ref_ptr + btrfs_item_size_nr(eb, slot);
1131 
1132         if (key->type == BTRFS_INODE_EXTREF_KEY) {
1133                 struct btrfs_inode_extref *r;
1134 
1135                 ref_struct_size = sizeof(struct btrfs_inode_extref);
1136                 log_ref_ver = 1;
1137                 r = (struct btrfs_inode_extref *)ref_ptr;
1138                 parent_objectid = btrfs_inode_extref_parent(eb, r);
1139         } else {
1140                 ref_struct_size = sizeof(struct btrfs_inode_ref);
1141                 parent_objectid = key->offset;
1142         }
1143         inode_objectid = key->objectid;
1144 
1145         /*
1146          * it is possible that we didn't log all the parent directories
1147          * for a given inode.  If we don't find the dir, just don't
1148          * copy the back ref in.  The link count fixup code will take
1149          * care of the rest
1150          */
1151         dir = read_one_inode(root, parent_objectid);
1152         if (!dir) {
1153                 ret = -ENOENT;
1154                 goto out;
1155         }
1156 
1157         inode = read_one_inode(root, inode_objectid);
1158         if (!inode) {
1159                 ret = -EIO;
1160                 goto out;
1161         }
1162 
1163         while (ref_ptr < ref_end) {
1164                 if (log_ref_ver) {
1165                         ret = extref_get_fields(eb, ref_ptr, &namelen, &name,
1166                                                 &ref_index, &parent_objectid);
1167                         /*
1168                          * parent object can change from one array
1169                          * item to another.
1170                          */
1171                         if (!dir)
1172                                 dir = read_one_inode(root, parent_objectid);
1173                         if (!dir) {
1174                                 ret = -ENOENT;
1175                                 goto out;
1176                         }
1177                 } else {
1178                         ret = ref_get_fields(eb, ref_ptr, &namelen, &name,
1179                                              &ref_index);
1180                 }
1181                 if (ret)
1182                         goto out;
1183 
1184                 /* if we already have a perfect match, we're done */
1185                 if (!inode_in_dir(root, path, btrfs_ino(dir), btrfs_ino(inode),
1186                                   ref_index, name, namelen)) {
1187                         /*
1188                          * look for a conflicting back reference in the
1189                          * metadata. if we find one we have to unlink that name
1190                          * of the file before we add our new link.  Later on, we
1191                          * overwrite any existing back reference, and we don't
1192                          * want to create dangling pointers in the directory.
1193                          */
1194 
1195                         if (!search_done) {
1196                                 ret = __add_inode_ref(trans, root, path, log,
1197                                                       dir, inode, eb,
1198                                                       inode_objectid,
1199                                                       parent_objectid,
1200                                                       ref_index, name, namelen,
1201                                                       &search_done);
1202                                 if (ret) {
1203                                         if (ret == 1)
1204                                                 ret = 0;
1205                                         goto out;
1206                                 }
1207                         }
1208 
1209                         /* insert our name */
1210                         ret = btrfs_add_link(trans, dir, inode, name, namelen,
1211                                              0, ref_index);
1212                         if (ret)
1213                                 goto out;
1214 
1215                         btrfs_update_inode(trans, root, inode);
1216                 }
1217 
1218                 ref_ptr = (unsigned long)(ref_ptr + ref_struct_size) + namelen;
1219                 kfree(name);
1220                 name = NULL;
1221                 if (log_ref_ver) {
1222                         iput(dir);
1223                         dir = NULL;
1224                 }
1225         }
1226 
1227         /* finally write the back reference in the inode */
1228         ret = overwrite_item(trans, root, path, eb, slot, key);
1229 out:
1230         btrfs_release_path(path);
1231         kfree(name);
1232         iput(dir);
1233         iput(inode);
1234         return ret;
1235 }
1236 
1237 static int insert_orphan_item(struct btrfs_trans_handle *trans,
1238                               struct btrfs_root *root, u64 ino)
1239 {
1240         int ret;
1241 
1242         ret = btrfs_insert_orphan_item(trans, root, ino);
1243         if (ret == -EEXIST)
1244                 ret = 0;
1245 
1246         return ret;
1247 }
1248 
1249 static int count_inode_extrefs(struct btrfs_root *root,
1250                                struct inode *inode, struct btrfs_path *path)
1251 {
1252         int ret = 0;
1253         int name_len;
1254         unsigned int nlink = 0;
1255         u32 item_size;
1256         u32 cur_offset = 0;
1257         u64 inode_objectid = btrfs_ino(inode);
1258         u64 offset = 0;
1259         unsigned long ptr;
1260         struct btrfs_inode_extref *extref;
1261         struct extent_buffer *leaf;
1262 
1263         while (1) {
1264                 ret = btrfs_find_one_extref(root, inode_objectid, offset, path,
1265                                             &extref, &offset);
1266                 if (ret)
1267                         break;
1268 
1269                 leaf = path->nodes[0];
1270                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1271                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1272 
1273                 while (cur_offset < item_size) {
1274                         extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
1275                         name_len = btrfs_inode_extref_name_len(leaf, extref);
1276 
1277                         nlink++;
1278 
1279                         cur_offset += name_len + sizeof(*extref);
1280                 }
1281 
1282                 offset++;
1283                 btrfs_release_path(path);
1284         }
1285         btrfs_release_path(path);
1286 
1287         if (ret < 0)
1288                 return ret;
1289         return nlink;
1290 }
1291 
1292 static int count_inode_refs(struct btrfs_root *root,
1293                                struct inode *inode, struct btrfs_path *path)
1294 {
1295         int ret;
1296         struct btrfs_key key;
1297         unsigned int nlink = 0;
1298         unsigned long ptr;
1299         unsigned long ptr_end;
1300         int name_len;
1301         u64 ino = btrfs_ino(inode);
1302 
1303         key.objectid = ino;
1304         key.type = BTRFS_INODE_REF_KEY;
1305         key.offset = (u64)-1;
1306 
1307         while (1) {
1308                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1309                 if (ret < 0)
1310                         break;
1311                 if (ret > 0) {
1312                         if (path->slots[0] == 0)
1313                                 break;
1314                         path->slots[0]--;
1315                 }
1316 process_slot:
1317                 btrfs_item_key_to_cpu(path->nodes[0], &key,
1318                                       path->slots[0]);
1319                 if (key.objectid != ino ||
1320                     key.type != BTRFS_INODE_REF_KEY)
1321                         break;
1322                 ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
1323                 ptr_end = ptr + btrfs_item_size_nr(path->nodes[0],
1324                                                    path->slots[0]);
1325                 while (ptr < ptr_end) {
1326                         struct btrfs_inode_ref *ref;
1327 
1328                         ref = (struct btrfs_inode_ref *)ptr;
1329                         name_len = btrfs_inode_ref_name_len(path->nodes[0],
1330                                                             ref);
1331                         ptr = (unsigned long)(ref + 1) + name_len;
1332                         nlink++;
1333                 }
1334 
1335                 if (key.offset == 0)
1336                         break;
1337                 if (path->slots[0] > 0) {
1338                         path->slots[0]--;
1339                         goto process_slot;
1340                 }
1341                 key.offset--;
1342                 btrfs_release_path(path);
1343         }
1344         btrfs_release_path(path);
1345 
1346         return nlink;
1347 }
1348 
1349 /*
1350  * There are a few corners where the link count of the file can't
1351  * be properly maintained during replay.  So, instead of adding
1352  * lots of complexity to the log code, we just scan the backrefs
1353  * for any file that has been through replay.
1354  *
1355  * The scan will update the link count on the inode to reflect the
1356  * number of back refs found.  If it goes down to zero, the iput
1357  * will free the inode.
1358  */
1359 static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
1360                                            struct btrfs_root *root,
1361                                            struct inode *inode)
1362 {
1363         struct btrfs_path *path;
1364         int ret;
1365         u64 nlink = 0;
1366         u64 ino = btrfs_ino(inode);
1367 
1368         path = btrfs_alloc_path();
1369         if (!path)
1370                 return -ENOMEM;
1371 
1372         ret = count_inode_refs(root, inode, path);
1373         if (ret < 0)
1374                 goto out;
1375 
1376         nlink = ret;
1377 
1378         ret = count_inode_extrefs(root, inode, path);
1379         if (ret == -ENOENT)
1380                 ret = 0;
1381 
1382         if (ret < 0)
1383                 goto out;
1384 
1385         nlink += ret;
1386 
1387         ret = 0;
1388 
1389         if (nlink != inode->i_nlink) {
1390                 set_nlink(inode, nlink);
1391                 btrfs_update_inode(trans, root, inode);
1392         }
1393         BTRFS_I(inode)->index_cnt = (u64)-1;
1394 
1395         if (inode->i_nlink == 0) {
1396                 if (S_ISDIR(inode->i_mode)) {
1397                         ret = replay_dir_deletes(trans, root, NULL, path,
1398                                                  ino, 1);
1399                         if (ret)
1400                                 goto out;
1401                 }
1402                 ret = insert_orphan_item(trans, root, ino);
1403         }
1404 
1405 out:
1406         btrfs_free_path(path);
1407         return ret;
1408 }
1409 
1410 static noinline int fixup_inode_link_counts(struct btrfs_trans_handle *trans,
1411                                             struct btrfs_root *root,
1412                                             struct btrfs_path *path)
1413 {
1414         int ret;
1415         struct btrfs_key key;
1416         struct inode *inode;
1417 
1418         key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1419         key.type = BTRFS_ORPHAN_ITEM_KEY;
1420         key.offset = (u64)-1;
1421         while (1) {
1422                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1423                 if (ret < 0)
1424                         break;
1425 
1426                 if (ret == 1) {
1427                         if (path->slots[0] == 0)
1428                                 break;
1429                         path->slots[0]--;
1430                 }
1431 
1432                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1433                 if (key.objectid != BTRFS_TREE_LOG_FIXUP_OBJECTID ||
1434                     key.type != BTRFS_ORPHAN_ITEM_KEY)
1435                         break;
1436 
1437                 ret = btrfs_del_item(trans, root, path);
1438                 if (ret)
1439                         goto out;
1440 
1441                 btrfs_release_path(path);
1442                 inode = read_one_inode(root, key.offset);
1443                 if (!inode)
1444                         return -EIO;
1445 
1446                 ret = fixup_inode_link_count(trans, root, inode);
1447                 iput(inode);
1448                 if (ret)
1449                         goto out;
1450 
1451                 /*
1452                  * fixup on a directory may create new entries,
1453                  * make sure we always look for the highset possible
1454                  * offset
1455                  */
1456                 key.offset = (u64)-1;
1457         }
1458         ret = 0;
1459 out:
1460         btrfs_release_path(path);
1461         return ret;
1462 }
1463 
1464 
1465 /*
1466  * record a given inode in the fixup dir so we can check its link
1467  * count when replay is done.  The link count is incremented here
1468  * so the inode won't go away until we check it
1469  */
1470 static noinline int link_to_fixup_dir(struct btrfs_trans_handle *trans,
1471                                       struct btrfs_root *root,
1472                                       struct btrfs_path *path,
1473                                       u64 objectid)
1474 {
1475         struct btrfs_key key;
1476         int ret = 0;
1477         struct inode *inode;
1478 
1479         inode = read_one_inode(root, objectid);
1480         if (!inode)
1481                 return -EIO;
1482 
1483         key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1484         btrfs_set_key_type(&key, BTRFS_ORPHAN_ITEM_KEY);
1485         key.offset = objectid;
1486 
1487         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
1488 
1489         btrfs_release_path(path);
1490         if (ret == 0) {
1491                 if (!inode->i_nlink)
1492                         set_nlink(inode, 1);
1493                 else
1494                         inc_nlink(inode);
1495                 ret = btrfs_update_inode(trans, root, inode);
1496         } else if (ret == -EEXIST) {
1497                 ret = 0;
1498         } else {
1499                 BUG(); /* Logic Error */
1500         }
1501         iput(inode);
1502 
1503         return ret;
1504 }
1505 
1506 /*
1507  * when replaying the log for a directory, we only insert names
1508  * for inodes that actually exist.  This means an fsync on a directory
1509  * does not implicitly fsync all the new files in it
1510  */
1511 static noinline int insert_one_name(struct btrfs_trans_handle *trans,
1512                                     struct btrfs_root *root,
1513                                     struct btrfs_path *path,
1514                                     u64 dirid, u64 index,
1515                                     char *name, int name_len, u8 type,
1516                                     struct btrfs_key *location)
1517 {
1518         struct inode *inode;
1519         struct inode *dir;
1520         int ret;
1521 
1522         inode = read_one_inode(root, location->objectid);
1523         if (!inode)
1524                 return -ENOENT;
1525 
1526         dir = read_one_inode(root, dirid);
1527         if (!dir) {
1528                 iput(inode);
1529                 return -EIO;
1530         }
1531 
1532         ret = btrfs_add_link(trans, dir, inode, name, name_len, 1, index);
1533 
1534         /* FIXME, put inode into FIXUP list */
1535 
1536         iput(inode);
1537         iput(dir);
1538         return ret;
1539 }
1540 
1541 /*
1542  * take a single entry in a log directory item and replay it into
1543  * the subvolume.
1544  *
1545  * if a conflicting item exists in the subdirectory already,
1546  * the inode it points to is unlinked and put into the link count
1547  * fix up tree.
1548  *
1549  * If a name from the log points to a file or directory that does
1550  * not exist in the FS, it is skipped.  fsyncs on directories
1551  * do not force down inodes inside that directory, just changes to the
1552  * names or unlinks in a directory.
1553  */
1554 static noinline int replay_one_name(struct btrfs_trans_handle *trans,
1555                                     struct btrfs_root *root,
1556                                     struct btrfs_path *path,
1557                                     struct extent_buffer *eb,
1558                                     struct btrfs_dir_item *di,
1559                                     struct btrfs_key *key)
1560 {
1561         char *name;
1562         int name_len;
1563         struct btrfs_dir_item *dst_di;
1564         struct btrfs_key found_key;
1565         struct btrfs_key log_key;
1566         struct inode *dir;
1567         u8 log_type;
1568         int exists;
1569         int ret = 0;
1570         bool update_size = (key->type == BTRFS_DIR_INDEX_KEY);
1571 
1572         dir = read_one_inode(root, key->objectid);
1573         if (!dir)
1574                 return -EIO;
1575 
1576         name_len = btrfs_dir_name_len(eb, di);
1577         name = kmalloc(name_len, GFP_NOFS);
1578         if (!name) {
1579                 ret = -ENOMEM;
1580                 goto out;
1581         }
1582 
1583         log_type = btrfs_dir_type(eb, di);
1584         read_extent_buffer(eb, name, (unsigned long)(di + 1),
1585                    name_len);
1586 
1587         btrfs_dir_item_key_to_cpu(eb, di, &log_key);
1588         exists = btrfs_lookup_inode(trans, root, path, &log_key, 0);
1589         if (exists == 0)
1590                 exists = 1;
1591         else
1592                 exists = 0;
1593         btrfs_release_path(path);
1594 
1595         if (key->type == BTRFS_DIR_ITEM_KEY) {
1596                 dst_di = btrfs_lookup_dir_item(trans, root, path, key->objectid,
1597                                        name, name_len, 1);
1598         } else if (key->type == BTRFS_DIR_INDEX_KEY) {
1599                 dst_di = btrfs_lookup_dir_index_item(trans, root, path,
1600                                                      key->objectid,
1601                                                      key->offset, name,
1602                                                      name_len, 1);
1603         } else {
1604                 /* Corruption */
1605                 ret = -EINVAL;
1606                 goto out;
1607         }
1608         if (IS_ERR_OR_NULL(dst_di)) {
1609                 /* we need a sequence number to insert, so we only
1610                  * do inserts for the BTRFS_DIR_INDEX_KEY types
1611                  */
1612                 if (key->type != BTRFS_DIR_INDEX_KEY)
1613                         goto out;
1614                 goto insert;
1615         }
1616 
1617         btrfs_dir_item_key_to_cpu(path->nodes[0], dst_di, &found_key);
1618         /* the existing item matches the logged item */
1619         if (found_key.objectid == log_key.objectid &&
1620             found_key.type == log_key.type &&
1621             found_key.offset == log_key.offset &&
1622             btrfs_dir_type(path->nodes[0], dst_di) == log_type) {
1623                 goto out;
1624         }
1625 
1626         /*
1627          * don't drop the conflicting directory entry if the inode
1628          * for the new entry doesn't exist
1629          */
1630         if (!exists)
1631                 goto out;
1632 
1633         ret = drop_one_dir_item(trans, root, path, dir, dst_di);
1634         if (ret)
1635                 goto out;
1636 
1637         if (key->type == BTRFS_DIR_INDEX_KEY)
1638                 goto insert;
1639 out:
1640         btrfs_release_path(path);
1641         if (!ret && update_size) {
1642                 btrfs_i_size_write(dir, dir->i_size + name_len * 2);
1643                 ret = btrfs_update_inode(trans, root, dir);
1644         }
1645         kfree(name);
1646         iput(dir);
1647         return ret;
1648 
1649 insert:
1650         btrfs_release_path(path);
1651         ret = insert_one_name(trans, root, path, key->objectid, key->offset,
1652                               name, name_len, log_type, &log_key);
1653         if (ret && ret != -ENOENT)
1654                 goto out;
1655         update_size = false;
1656         ret = 0;
1657         goto out;
1658 }
1659 
1660 /*
1661  * find all the names in a directory item and reconcile them into
1662  * the subvolume.  Only BTRFS_DIR_ITEM_KEY types will have more than
1663  * one name in a directory item, but the same code gets used for
1664  * both directory index types
1665  */
1666 static noinline int replay_one_dir_item(struct btrfs_trans_handle *trans,
1667                                         struct btrfs_root *root,
1668                                         struct btrfs_path *path,
1669                                         struct extent_buffer *eb, int slot,
1670                                         struct btrfs_key *key)
1671 {
1672         int ret;
1673         u32 item_size = btrfs_item_size_nr(eb, slot);
1674         struct btrfs_dir_item *di;
1675         int name_len;
1676         unsigned long ptr;
1677         unsigned long ptr_end;
1678 
1679         ptr = btrfs_item_ptr_offset(eb, slot);
1680         ptr_end = ptr + item_size;
1681         while (ptr < ptr_end) {
1682                 di = (struct btrfs_dir_item *)ptr;
1683                 if (verify_dir_item(root, eb, di))
1684                         return -EIO;
1685                 name_len = btrfs_dir_name_len(eb, di);
1686                 ret = replay_one_name(trans, root, path, eb, di, key);
1687                 if (ret)
1688                         return ret;
1689                 ptr = (unsigned long)(di + 1);
1690                 ptr += name_len;
1691         }
1692         return 0;
1693 }
1694 
1695 /*
1696  * directory replay has two parts.  There are the standard directory
1697  * items in the log copied from the subvolume, and range items
1698  * created in the log while the subvolume was logged.
1699  *
1700  * The range items tell us which parts of the key space the log
1701  * is authoritative for.  During replay, if a key in the subvolume
1702  * directory is in a logged range item, but not actually in the log
1703  * that means it was deleted from the directory before the fsync
1704  * and should be removed.
1705  */
1706 static noinline int find_dir_range(struct btrfs_root *root,
1707                                    struct btrfs_path *path,
1708                                    u64 dirid, int key_type,
1709                                    u64 *start_ret, u64 *end_ret)
1710 {
1711         struct btrfs_key key;
1712         u64 found_end;
1713         struct btrfs_dir_log_item *item;
1714         int ret;
1715         int nritems;
1716 
1717         if (*start_ret == (u64)-1)
1718                 return 1;
1719 
1720         key.objectid = dirid;
1721         key.type = key_type;
1722         key.offset = *start_ret;
1723 
1724         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1725         if (ret < 0)
1726                 goto out;
1727         if (ret > 0) {
1728                 if (path->slots[0] == 0)
1729                         goto out;
1730                 path->slots[0]--;
1731         }
1732         if (ret != 0)
1733                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1734 
1735         if (key.type != key_type || key.objectid != dirid) {
1736                 ret = 1;
1737                 goto next;
1738         }
1739         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1740                               struct btrfs_dir_log_item);
1741         found_end = btrfs_dir_log_end(path->nodes[0], item);
1742 
1743         if (*start_ret >= key.offset && *start_ret <= found_end) {
1744                 ret = 0;
1745                 *start_ret = key.offset;
1746                 *end_ret = found_end;
1747                 goto out;
1748         }
1749         ret = 1;
1750 next:
1751         /* check the next slot in the tree to see if it is a valid item */
1752         nritems = btrfs_header_nritems(path->nodes[0]);
1753         if (path->slots[0] >= nritems) {
1754                 ret = btrfs_next_leaf(root, path);
1755                 if (ret)
1756                         goto out;
1757         } else {
1758                 path->slots[0]++;
1759         }
1760 
1761         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1762 
1763         if (key.type != key_type || key.objectid != dirid) {
1764                 ret = 1;
1765                 goto out;
1766         }
1767         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1768                               struct btrfs_dir_log_item);
1769         found_end = btrfs_dir_log_end(path->nodes[0], item);
1770         *start_ret = key.offset;
1771         *end_ret = found_end;
1772         ret = 0;
1773 out:
1774         btrfs_release_path(path);
1775         return ret;
1776 }
1777 
1778 /*
1779  * this looks for a given directory item in the log.  If the directory
1780  * item is not in the log, the item is removed and the inode it points
1781  * to is unlinked
1782  */
1783 static noinline int check_item_in_log(struct btrfs_trans_handle *trans,
1784                                       struct btrfs_root *root,
1785                                       struct btrfs_root *log,
1786                                       struct btrfs_path *path,
1787                                       struct btrfs_path *log_path,
1788                                       struct inode *dir,
1789                                       struct btrfs_key *dir_key)
1790 {
1791         int ret;
1792         struct extent_buffer *eb;
1793         int slot;
1794         u32 item_size;
1795         struct btrfs_dir_item *di;
1796         struct btrfs_dir_item *log_di;
1797         int name_len;
1798         unsigned long ptr;
1799         unsigned long ptr_end;
1800         char *name;
1801         struct inode *inode;
1802         struct btrfs_key location;
1803 
1804 again:
1805         eb = path->nodes[0];
1806         slot = path->slots[0];
1807         item_size = btrfs_item_size_nr(eb, slot);
1808         ptr = btrfs_item_ptr_offset(eb, slot);
1809         ptr_end = ptr + item_size;
1810         while (ptr < ptr_end) {
1811                 di = (struct btrfs_dir_item *)ptr;
1812                 if (verify_dir_item(root, eb, di)) {
1813                         ret = -EIO;
1814                         goto out;
1815                 }
1816 
1817                 name_len = btrfs_dir_name_len(eb, di);
1818                 name = kmalloc(name_len, GFP_NOFS);
1819                 if (!name) {
1820                         ret = -ENOMEM;
1821                         goto out;
1822                 }
1823                 read_extent_buffer(eb, name, (unsigned long)(di + 1),
1824                                   name_len);
1825                 log_di = NULL;
1826                 if (log && dir_key->type == BTRFS_DIR_ITEM_KEY) {
1827                         log_di = btrfs_lookup_dir_item(trans, log, log_path,
1828                                                        dir_key->objectid,
1829                                                        name, name_len, 0);
1830                 } else if (log && dir_key->type == BTRFS_DIR_INDEX_KEY) {
1831                         log_di = btrfs_lookup_dir_index_item(trans, log,
1832                                                      log_path,
1833                                                      dir_key->objectid,
1834                                                      dir_key->offset,
1835                                                      name, name_len, 0);
1836                 }
1837                 if (!log_di || (IS_ERR(log_di) && PTR_ERR(log_di) == -ENOENT)) {
1838                         btrfs_dir_item_key_to_cpu(eb, di, &location);
1839                         btrfs_release_path(path);
1840                         btrfs_release_path(log_path);
1841                         inode = read_one_inode(root, location.objectid);
1842                         if (!inode) {
1843                                 kfree(name);
1844                                 return -EIO;
1845                         }
1846 
1847                         ret = link_to_fixup_dir(trans, root,
1848                                                 path, location.objectid);
1849                         if (ret) {
1850                                 kfree(name);
1851                                 iput(inode);
1852                                 goto out;
1853                         }
1854 
1855                         inc_nlink(inode);
1856                         ret = btrfs_unlink_inode(trans, root, dir, inode,
1857                                                  name, name_len);
1858                         if (!ret)
1859                                 ret = btrfs_run_delayed_items(trans, root);
1860                         kfree(name);
1861                         iput(inode);
1862                         if (ret)
1863                                 goto out;
1864 
1865                         /* there might still be more names under this key
1866                          * check and repeat if required
1867                          */
1868                         ret = btrfs_search_slot(NULL, root, dir_key, path,
1869                                                 0, 0);
1870                         if (ret == 0)
1871                                 goto again;
1872                         ret = 0;
1873                         goto out;
1874                 } else if (IS_ERR(log_di)) {
1875                         kfree(name);
1876                         return PTR_ERR(log_di);
1877                 }
1878                 btrfs_release_path(log_path);
1879                 kfree(name);
1880 
1881                 ptr = (unsigned long)(di + 1);
1882                 ptr += name_len;
1883         }
1884         ret = 0;
1885 out:
1886         btrfs_release_path(path);
1887         btrfs_release_path(log_path);
1888         return ret;
1889 }
1890 
1891 /*
1892  * deletion replay happens before we copy any new directory items
1893  * out of the log or out of backreferences from inodes.  It
1894  * scans the log to find ranges of keys that log is authoritative for,
1895  * and then scans the directory to find items in those ranges that are
1896  * not present in the log.
1897  *
1898  * Anything we don't find in the log is unlinked and removed from the
1899  * directory.
1900  */
1901 static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
1902                                        struct btrfs_root *root,
1903                                        struct btrfs_root *log,
1904                                        struct btrfs_path *path,
1905                                        u64 dirid, int del_all)
1906 {
1907         u64 range_start;
1908         u64 range_end;
1909         int key_type = BTRFS_DIR_LOG_ITEM_KEY;
1910         int ret = 0;
1911         struct btrfs_key dir_key;
1912         struct btrfs_key found_key;
1913         struct btrfs_path *log_path;
1914         struct inode *dir;
1915 
1916         dir_key.objectid = dirid;
1917         dir_key.type = BTRFS_DIR_ITEM_KEY;
1918         log_path = btrfs_alloc_path();
1919         if (!log_path)
1920                 return -ENOMEM;
1921 
1922         dir = read_one_inode(root, dirid);
1923         /* it isn't an error if the inode isn't there, that can happen
1924          * because we replay the deletes before we copy in the inode item
1925          * from the log
1926          */
1927         if (!dir) {
1928                 btrfs_free_path(log_path);
1929                 return 0;
1930         }
1931 again:
1932         range_start = 0;
1933         range_end = 0;
1934         while (1) {
1935                 if (del_all)
1936                         range_end = (u64)-1;
1937                 else {
1938                         ret = find_dir_range(log, path, dirid, key_type,
1939                                              &range_start, &range_end);
1940                         if (ret != 0)
1941                                 break;
1942                 }
1943 
1944                 dir_key.offset = range_start;
1945                 while (1) {
1946                         int nritems;
1947                         ret = btrfs_search_slot(NULL, root, &dir_key, path,
1948                                                 0, 0);
1949                         if (ret < 0)
1950                                 goto out;
1951 
1952                         nritems = btrfs_header_nritems(path->nodes[0]);
1953                         if (path->slots[0] >= nritems) {
1954                                 ret = btrfs_next_leaf(root, path);
1955                                 if (ret)
1956                                         break;
1957                         }
1958                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1959                                               path->slots[0]);
1960                         if (found_key.objectid != dirid ||
1961                             found_key.type != dir_key.type)
1962                                 goto next_type;
1963 
1964                         if (found_key.offset > range_end)
1965                                 break;
1966 
1967                         ret = check_item_in_log(trans, root, log, path,
1968                                                 log_path, dir,
1969                                                 &found_key);
1970                         if (ret)
1971                                 goto out;
1972                         if (found_key.offset == (u64)-1)
1973                                 break;
1974                         dir_key.offset = found_key.offset + 1;
1975                 }
1976                 btrfs_release_path(path);
1977                 if (range_end == (u64)-1)
1978                         break;
1979                 range_start = range_end + 1;
1980         }
1981 
1982 next_type:
1983         ret = 0;
1984         if (key_type == BTRFS_DIR_LOG_ITEM_KEY) {
1985                 key_type = BTRFS_DIR_LOG_INDEX_KEY;
1986                 dir_key.type = BTRFS_DIR_INDEX_KEY;
1987                 btrfs_release_path(path);
1988                 goto again;
1989         }
1990 out:
1991         btrfs_release_path(path);
1992         btrfs_free_path(log_path);
1993         iput(dir);
1994         return ret;
1995 }
1996 
1997 /*
1998  * the process_func used to replay items from the log tree.  This
1999  * gets called in two different stages.  The first stage just looks
2000  * for inodes and makes sure they are all copied into the subvolume.
2001  *
2002  * The second stage copies all the other item types from the log into
2003  * the subvolume.  The two stage approach is slower, but gets rid of
2004  * lots of complexity around inodes referencing other inodes that exist
2005  * only in the log (references come from either directory items or inode
2006  * back refs).
2007  */
2008 static int replay_one_buffer(struct btrfs_root *log, struct extent_buffer *eb,
2009                              struct walk_control *wc, u64 gen)
2010 {
2011         int nritems;
2012         struct btrfs_path *path;
2013         struct btrfs_root *root = wc->replay_dest;
2014         struct btrfs_key key;
2015         int level;
2016         int i;
2017         int ret;
2018 
2019         ret = btrfs_read_buffer(eb, gen);
2020         if (ret)
2021                 return ret;
2022 
2023         level = btrfs_header_level(eb);
2024 
2025         if (level != 0)
2026                 return 0;
2027 
2028         path = btrfs_alloc_path();
2029         if (!path)
2030                 return -ENOMEM;
2031 
2032         nritems = btrfs_header_nritems(eb);
2033         for (i = 0; i < nritems; i++) {
2034                 btrfs_item_key_to_cpu(eb, &key, i);
2035 
2036                 /* inode keys are done during the first stage */
2037                 if (key.type == BTRFS_INODE_ITEM_KEY &&
2038                     wc->stage == LOG_WALK_REPLAY_INODES) {
2039                         struct btrfs_inode_item *inode_item;
2040                         u32 mode;
2041 
2042                         inode_item = btrfs_item_ptr(eb, i,
2043                                             struct btrfs_inode_item);
2044                         mode = btrfs_inode_mode(eb, inode_item);
2045                         if (S_ISDIR(mode)) {
2046                                 ret = replay_dir_deletes(wc->trans,
2047                                          root, log, path, key.objectid, 0);
2048                                 if (ret)
2049                                         break;
2050                         }
2051                         ret = overwrite_item(wc->trans, root, path,
2052                                              eb, i, &key);
2053                         if (ret)
2054                                 break;
2055 
2056                         /* for regular files, make sure corresponding
2057                          * orhpan item exist. extents past the new EOF
2058                          * will be truncated later by orphan cleanup.
2059                          */
2060                         if (S_ISREG(mode)) {
2061                                 ret = insert_orphan_item(wc->trans, root,
2062                                                          key.objectid);
2063                                 if (ret)
2064                                         break;
2065                         }
2066 
2067                         ret = link_to_fixup_dir(wc->trans, root,
2068                                                 path, key.objectid);
2069                         if (ret)
2070                                 break;
2071                 }
2072 
2073                 if (key.type == BTRFS_DIR_INDEX_KEY &&
2074                     wc->stage == LOG_WALK_REPLAY_DIR_INDEX) {
2075                         ret = replay_one_dir_item(wc->trans, root, path,
2076                                                   eb, i, &key);
2077                         if (ret)
2078                                 break;
2079                 }
2080 
2081                 if (wc->stage < LOG_WALK_REPLAY_ALL)
2082                         continue;
2083 
2084                 /* these keys are simply copied */
2085                 if (key.type == BTRFS_XATTR_ITEM_KEY) {
2086                         ret = overwrite_item(wc->trans, root, path,
2087                                              eb, i, &key);
2088                         if (ret)
2089                                 break;
2090                 } else if (key.type == BTRFS_INODE_REF_KEY ||
2091                            key.type == BTRFS_INODE_EXTREF_KEY) {
2092                         ret = add_inode_ref(wc->trans, root, log, path,
2093                                             eb, i, &key);
2094                         if (ret && ret != -ENOENT)
2095                                 break;
2096                         ret = 0;
2097                 } else if (key.type == BTRFS_EXTENT_DATA_KEY) {
2098                         ret = replay_one_extent(wc->trans, root, path,
2099                                                 eb, i, &key);
2100                         if (ret)
2101                                 break;
2102                 } else if (key.type == BTRFS_DIR_ITEM_KEY) {
2103                         ret = replay_one_dir_item(wc->trans, root, path,
2104                                                   eb, i, &key);
2105                         if (ret)
2106                                 break;
2107                 }
2108         }
2109         btrfs_free_path(path);
2110         return ret;
2111 }
2112 
2113 static noinline int walk_down_log_tree(struct btrfs_trans_handle *trans,
2114                                    struct btrfs_root *root,
2115                                    struct btrfs_path *path, int *level,
2116                                    struct walk_control *wc)
2117 {
2118         u64 root_owner;
2119         u64 bytenr;
2120         u64 ptr_gen;
2121         struct extent_buffer *next;
2122         struct extent_buffer *cur;
2123         struct extent_buffer *parent;
2124         u32 blocksize;
2125         int ret = 0;
2126 
2127         WARN_ON(*level < 0);
2128         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2129 
2130         while (*level > 0) {
2131                 WARN_ON(*level < 0);
2132                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2133                 cur = path->nodes[*level];
2134 
2135                 WARN_ON(btrfs_header_level(cur) != *level);
2136 
2137                 if (path->slots[*level] >=
2138                     btrfs_header_nritems(cur))
2139                         break;
2140 
2141                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2142                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2143                 blocksize = btrfs_level_size(root, *level - 1);
2144 
2145                 parent = path->nodes[*level];
2146                 root_owner = btrfs_header_owner(parent);
2147 
2148                 next = btrfs_find_create_tree_block(root, bytenr, blocksize);
2149                 if (!next)
2150                         return -ENOMEM;
2151 
2152                 if (*level == 1) {
2153                         ret = wc->process_func(root, next, wc, ptr_gen);
2154                         if (ret) {
2155                                 free_extent_buffer(next);
2156                                 return ret;
2157                         }
2158 
2159                         path->slots[*level]++;
2160                         if (wc->free) {
2161                                 ret = btrfs_read_buffer(next, ptr_gen);
2162                                 if (ret) {
2163                                         free_extent_buffer(next);
2164                                         return ret;
2165                                 }
2166 
2167                                 if (trans) {
2168                                         btrfs_tree_lock(next);
2169                                         btrfs_set_lock_blocking(next);
2170                                         clean_tree_block(trans, root, next);
2171                                         btrfs_wait_tree_block_writeback(next);
2172                                         btrfs_tree_unlock(next);
2173                                 }
2174 
2175                                 WARN_ON(root_owner !=
2176                                         BTRFS_TREE_LOG_OBJECTID);
2177                                 ret = btrfs_free_and_pin_reserved_extent(root,
2178                                                          bytenr, blocksize);
2179                                 if (ret) {
2180                                         free_extent_buffer(next);
2181                                         return ret;
2182                                 }
2183                         }
2184                         free_extent_buffer(next);
2185                         continue;
2186                 }
2187                 ret = btrfs_read_buffer(next, ptr_gen);
2188                 if (ret) {
2189                         free_extent_buffer(next);
2190                         return ret;
2191                 }
2192 
2193                 WARN_ON(*level <= 0);
2194                 if (path->nodes[*level-1])
2195                         free_extent_buffer(path->nodes[*level-1]);
2196                 path->nodes[*level-1] = next;
2197                 *level = btrfs_header_level(next);
2198                 path->slots[*level] = 0;
2199                 cond_resched();
2200         }
2201         WARN_ON(*level < 0);
2202         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2203 
2204         path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
2205 
2206         cond_resched();
2207         return 0;
2208 }
2209 
2210 static noinline int walk_up_log_tree(struct btrfs_trans_handle *trans,
2211                                  struct btrfs_root *root,
2212                                  struct btrfs_path *path, int *level,
2213                                  struct walk_control *wc)
2214 {
2215         u64 root_owner;
2216         int i;
2217         int slot;
2218         int ret;
2219 
2220         for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2221                 slot = path->slots[i];
2222                 if (slot + 1 < btrfs_header_nritems(path->nodes[i])) {
2223                         path->slots[i]++;
2224                         *level = i;
2225                         WARN_ON(*level == 0);
2226                         return 0;
2227                 } else {
2228                         struct extent_buffer *parent;
2229                         if (path->nodes[*level] == root->node)
2230                                 parent = path->nodes[*level];
2231                         else
2232                                 parent = path->nodes[*level + 1];
2233 
2234                         root_owner = btrfs_header_owner(parent);
2235                         ret = wc->process_func(root, path->nodes[*level], wc,
2236                                  btrfs_header_generation(path->nodes[*level]));
2237                         if (ret)
2238                                 return ret;
2239 
2240                         if (wc->free) {
2241                                 struct extent_buffer *next;
2242 
2243                                 next = path->nodes[*level];
2244 
2245                                 if (trans) {
2246                                         btrfs_tree_lock(next);
2247                                         btrfs_set_lock_blocking(next);
2248                                         clean_tree_block(trans, root, next);
2249                                         btrfs_wait_tree_block_writeback(next);
2250                                         btrfs_tree_unlock(next);
2251                                 }
2252 
2253                                 WARN_ON(root_owner != BTRFS_TREE_LOG_OBJECTID);
2254                                 ret = btrfs_free_and_pin_reserved_extent(root,
2255                                                 path->nodes[*level]->start,
2256                                                 path->nodes[*level]->len);
2257                                 if (ret)
2258                                         return ret;
2259                         }
2260                         free_extent_buffer(path->nodes[*level]);
2261                         path->nodes[*level] = NULL;
2262                         *level = i + 1;
2263                 }
2264         }
2265         return 1;
2266 }
2267 
2268 /*
2269  * drop the reference count on the tree rooted at 'snap'.  This traverses
2270  * the tree freeing any blocks that have a ref count of zero after being
2271  * decremented.
2272  */
2273 static int walk_log_tree(struct btrfs_trans_handle *trans,
2274                          struct btrfs_root *log, struct walk_control *wc)
2275 {
2276         int ret = 0;
2277         int wret;
2278         int level;
2279         struct btrfs_path *path;
2280         int orig_level;
2281 
2282         path = btrfs_alloc_path();
2283         if (!path)
2284                 return -ENOMEM;
2285 
2286         level = btrfs_header_level(log->node);
2287         orig_level = level;
2288         path->nodes[level] = log->node;
2289         extent_buffer_get(log->node);
2290         path->slots[level] = 0;
2291 
2292         while (1) {
2293                 wret = walk_down_log_tree(trans, log, path, &level, wc);
2294                 if (wret > 0)
2295                         break;
2296                 if (wret < 0) {
2297                         ret = wret;
2298                         goto out;
2299                 }
2300 
2301                 wret = walk_up_log_tree(trans, log, path, &level, wc);
2302                 if (wret > 0)
2303                         break;
2304                 if (wret < 0) {
2305                         ret = wret;
2306                         goto out;
2307                 }
2308         }
2309 
2310         /* was the root node processed? if not, catch it here */
2311         if (path->nodes[orig_level]) {
2312                 ret = wc->process_func(log, path->nodes[orig_level], wc,
2313                          btrfs_header_generation(path->nodes[orig_level]));
2314                 if (ret)
2315                         goto out;
2316                 if (wc->free) {
2317                         struct extent_buffer *next;
2318 
2319                         next = path->nodes[orig_level];
2320 
2321                         if (trans) {
2322                                 btrfs_tree_lock(next);
2323                                 btrfs_set_lock_blocking(next);
2324                                 clean_tree_block(trans, log, next);
2325                                 btrfs_wait_tree_block_writeback(next);
2326                                 btrfs_tree_unlock(next);
2327                         }
2328 
2329                         WARN_ON(log->root_key.objectid !=
2330                                 BTRFS_TREE_LOG_OBJECTID);
2331                         ret = btrfs_free_and_pin_reserved_extent(log, next->start,
2332                                                          next->len);
2333                         if (ret)
2334                                 goto out;
2335                 }
2336         }
2337 
2338 out:
2339         btrfs_free_path(path);
2340         return ret;
2341 }
2342 
2343 /*
2344  * helper function to update the item for a given subvolumes log root
2345  * in the tree of log roots
2346  */
2347 static int update_log_root(struct btrfs_trans_handle *trans,
2348                            struct btrfs_root *log)
2349 {
2350         int ret;
2351 
2352         if (log->log_transid == 1) {
2353                 /* insert root item on the first sync */
2354                 ret = btrfs_insert_root(trans, log->fs_info->log_root_tree,
2355                                 &log->root_key, &log->root_item);
2356         } else {
2357                 ret = btrfs_update_root(trans, log->fs_info->log_root_tree,
2358                                 &log->root_key, &log->root_item);
2359         }
2360         return ret;
2361 }
2362 
2363 static int wait_log_commit(struct btrfs_trans_handle *trans,
2364                            struct btrfs_root *root, unsigned long transid)
2365 {
2366         DEFINE_WAIT(wait);
2367         int index = transid % 2;
2368 
2369         /*
2370          * we only allow two pending log transactions at a time,
2371          * so we know that if ours is more than 2 older than the
2372          * current transaction, we're done
2373          */
2374         do {
2375                 prepare_to_wait(&root->log_commit_wait[index],
2376                                 &wait, TASK_UNINTERRUPTIBLE);
2377                 mutex_unlock(&root->log_mutex);
2378 
2379                 if (root->fs_info->last_trans_log_full_commit !=
2380                     trans->transid && root->log_transid < transid + 2 &&
2381                     atomic_read(&root->log_commit[index]))
2382                         schedule();
2383 
2384                 finish_wait(&root->log_commit_wait[index], &wait);
2385                 mutex_lock(&root->log_mutex);
2386         } while (root->fs_info->last_trans_log_full_commit !=
2387                  trans->transid && root->log_transid < transid + 2 &&
2388                  atomic_read(&root->log_commit[index]));
2389         return 0;
2390 }
2391 
2392 static void wait_for_writer(struct btrfs_trans_handle *trans,
2393                             struct btrfs_root *root)
2394 {
2395         DEFINE_WAIT(wait);
2396         while (root->fs_info->last_trans_log_full_commit !=
2397                trans->transid && atomic_read(&root->log_writers)) {
2398                 prepare_to_wait(&root->log_writer_wait,
2399                                 &wait, TASK_UNINTERRUPTIBLE);
2400                 mutex_unlock(&root->log_mutex);
2401                 if (root->fs_info->last_trans_log_full_commit !=
2402                     trans->transid && atomic_read(&root->log_writers))
2403                         schedule();
2404                 mutex_lock(&root->log_mutex);
2405                 finish_wait(&root->log_writer_wait, &wait);
2406         }
2407 }
2408 
2409 /*
2410  * btrfs_sync_log does sends a given tree log down to the disk and
2411  * updates the super blocks to record it.  When this call is done,
2412  * you know that any inodes previously logged are safely on disk only
2413  * if it returns 0.
2414  *
2415  * Any other return value means you need to call btrfs_commit_transaction.
2416  * Some of the edge cases for fsyncing directories that have had unlinks
2417  * or renames done in the past mean that sometimes the only safe
2418  * fsync is to commit the whole FS.  When btrfs_sync_log returns -EAGAIN,
2419  * that has happened.
2420  */
2421 int btrfs_sync_log(struct btrfs_trans_handle *trans,
2422                    struct btrfs_root *root)
2423 {
2424         int index1;
2425         int index2;
2426         int mark;
2427         int ret;
2428         struct btrfs_root *log = root->log_root;
2429         struct btrfs_root *log_root_tree = root->fs_info->log_root_tree;
2430         unsigned long log_transid = 0;
2431         struct blk_plug plug;
2432 
2433         mutex_lock(&root->log_mutex);
2434         log_transid = root->log_transid;
2435         index1 = root->log_transid % 2;
2436         if (atomic_read(&root->log_commit[index1])) {
2437                 wait_log_commit(trans, root, root->log_transid);
2438                 mutex_unlock(&root->log_mutex);
2439                 return 0;
2440         }
2441         atomic_set(&root->log_commit[index1], 1);
2442 
2443         /* wait for previous tree log sync to complete */
2444         if (atomic_read(&root->log_commit[(index1 + 1) % 2]))
2445                 wait_log_commit(trans, root, root->log_transid - 1);
2446         while (1) {
2447                 int batch = atomic_read(&root->log_batch);
2448                 /* when we're on an ssd, just kick the log commit out */
2449                 if (!btrfs_test_opt(root, SSD) && root->log_multiple_pids) {
2450                         mutex_unlock(&root->log_mutex);
2451                         schedule_timeout_uninterruptible(1);
2452                         mutex_lock(&root->log_mutex);
2453                 }
2454                 wait_for_writer(trans, root);
2455                 if (batch == atomic_read(&root->log_batch))
2456                         break;
2457         }
2458 
2459         /* bail out if we need to do a full commit */
2460         if (root->fs_info->last_trans_log_full_commit == trans->transid) {
2461                 ret = -EAGAIN;
2462                 btrfs_free_logged_extents(log, log_transid);
2463                 mutex_unlock(&root->log_mutex);
2464                 goto out;
2465         }
2466 
2467         if (log_transid % 2 == 0)
2468                 mark = EXTENT_DIRTY;
2469         else
2470                 mark = EXTENT_NEW;
2471 
2472         /* we start IO on  all the marked extents here, but we don't actually
2473          * wait for them until later.
2474          */
2475         blk_start_plug(&plug);
2476         ret = btrfs_write_marked_extents(log, &log->dirty_log_pages, mark);
2477         if (ret) {
2478                 blk_finish_plug(&plug);
2479                 btrfs_abort_transaction(trans, root, ret);
2480                 btrfs_free_logged_extents(log, log_transid);
2481                 mutex_unlock(&root->log_mutex);
2482                 goto out;
2483         }
2484 
2485         btrfs_set_root_node(&log->root_item, log->node);
2486 
2487         root->log_transid++;
2488         log->log_transid = root->log_transid;
2489         root->log_start_pid = 0;
2490         smp_mb();
2491         /*
2492          * IO has been started, blocks of the log tree have WRITTEN flag set
2493          * in their headers. new modifications of the log will be written to
2494          * new positions. so it's safe to allow log writers to go in.
2495          */
2496         mutex_unlock(&root->log_mutex);
2497 
2498         mutex_lock(&log_root_tree->log_mutex);
2499         atomic_inc(&log_root_tree->log_batch);
2500         atomic_inc(&log_root_tree->log_writers);
2501         mutex_unlock(&log_root_tree->log_mutex);
2502 
2503         ret = update_log_root(trans, log);
2504 
2505         mutex_lock(&log_root_tree->log_mutex);
2506         if (atomic_dec_and_test(&log_root_tree->log_writers)) {
2507                 smp_mb();
2508                 if (waitqueue_active(&log_root_tree->log_writer_wait))
2509                         wake_up(&log_root_tree->log_writer_wait);
2510         }
2511 
2512         if (ret) {
2513                 blk_finish_plug(&plug);
2514                 if (ret != -ENOSPC) {
2515                         btrfs_abort_transaction(trans, root, ret);
2516                         mutex_unlock(&log_root_tree->log_mutex);
2517                         goto out;
2518                 }
2519                 root->fs_info->last_trans_log_full_commit = trans->transid;
2520                 btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2521                 btrfs_free_logged_extents(log, log_transid);
2522                 mutex_unlock(&log_root_tree->log_mutex);
2523                 ret = -EAGAIN;
2524                 goto out;
2525         }
2526 
2527         index2 = log_root_tree->log_transid % 2;
2528         if (atomic_read(&log_root_tree->log_commit[index2])) {
2529                 blk_finish_plug(&plug);
2530                 btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2531                 wait_log_commit(trans, log_root_tree,
2532                                 log_root_tree->log_transid);
2533                 btrfs_free_logged_extents(log, log_transid);
2534                 mutex_unlock(&log_root_tree->log_mutex);
2535                 ret = 0;
2536                 goto out;
2537         }
2538         atomic_set(&log_root_tree->log_commit[index2], 1);
2539 
2540         if (atomic_read(&log_root_tree->log_commit[(index2 + 1) % 2])) {
2541                 wait_log_commit(trans, log_root_tree,
2542                                 log_root_tree->log_transid - 1);
2543         }
2544 
2545         wait_for_writer(trans, log_root_tree);
2546 
2547         /*
2548          * now that we've moved on to the tree of log tree roots,
2549          * check the full commit flag again
2550          */
2551         if (root->fs_info->last_trans_log_full_commit == trans->transid) {
2552                 blk_finish_plug(&plug);
2553                 btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2554                 btrfs_free_logged_extents(log, log_transid);
2555                 mutex_unlock(&log_root_tree->log_mutex);
2556                 ret = -EAGAIN;
2557                 goto out_wake_log_root;
2558         }
2559 
2560         ret = btrfs_write_marked_extents(log_root_tree,
2561                                          &log_root_tree->dirty_log_pages,
2562                                          EXTENT_DIRTY | EXTENT_NEW);
2563         blk_finish_plug(&plug);
2564         if (ret) {
2565                 btrfs_abort_transaction(trans, root, ret);
2566                 btrfs_free_logged_extents(log, log_transid);
2567                 mutex_unlock(&log_root_tree->log_mutex);
2568                 goto out_wake_log_root;
2569         }
2570         btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2571         btrfs_wait_marked_extents(log_root_tree,
2572                                   &log_root_tree->dirty_log_pages,
2573                                   EXTENT_NEW | EXTENT_DIRTY);
2574         btrfs_wait_logged_extents(log, log_transid);
2575 
2576         btrfs_set_super_log_root(root->fs_info->super_for_commit,
2577                                 log_root_tree->node->start);
2578         btrfs_set_super_log_root_level(root->fs_info->super_for_commit,
2579                                 btrfs_header_level(log_root_tree->node));
2580 
2581         log_root_tree->log_transid++;
2582         smp_mb();
2583 
2584         mutex_unlock(&log_root_tree->log_mutex);
2585 
2586         /*
2587          * nobody else is going to jump in and write the the ctree
2588          * super here because the log_commit atomic below is protecting
2589          * us.  We must be called with a transaction handle pinning
2590          * the running transaction open, so a full commit can't hop
2591          * in and cause problems either.
2592          */
2593         ret = write_ctree_super(trans, root->fs_info->tree_root, 1);
2594         if (ret) {
2595                 btrfs_abort_transaction(trans, root, ret);
2596                 goto out_wake_log_root;
2597         }
2598 
2599         mutex_lock(&root->log_mutex);
2600         if (root->last_log_commit < log_transid)
2601                 root->last_log_commit = log_transid;
2602         mutex_unlock(&root->log_mutex);
2603 
2604 out_wake_log_root:
2605         atomic_set(&log_root_tree->log_commit[index2], 0);
2606         smp_mb();
2607         if (waitqueue_active(&log_root_tree->log_commit_wait[index2]))
2608                 wake_up(&log_root_tree->log_commit_wait[index2]);
2609 out:
2610         atomic_set(&root->log_commit[index1], 0);
2611         smp_mb();
2612         if (waitqueue_active(&root->log_commit_wait[index1]))
2613                 wake_up(&root->log_commit_wait[index1]);
2614         return ret;
2615 }
2616 
2617 static void free_log_tree(struct btrfs_trans_handle *trans,
2618                           struct btrfs_root *log)
2619 {
2620         int ret;
2621         u64 start;
2622         u64 end;
2623         struct walk_control wc = {
2624                 .free = 1,
2625                 .process_func = process_one_buffer
2626         };
2627 
2628         ret = walk_log_tree(trans, log, &wc);
2629         /* I don't think this can happen but just in case */
2630         if (ret)
2631                 btrfs_abort_transaction(trans, log, ret);
2632 
2633         while (1) {
2634                 ret = find_first_extent_bit(&log->dirty_log_pages,
2635                                 0, &start, &end, EXTENT_DIRTY | EXTENT_NEW,
2636                                 NULL);
2637                 if (ret)
2638                         break;
2639 
2640                 clear_extent_bits(&log->dirty_log_pages, start, end,
2641                                   EXTENT_DIRTY | EXTENT_NEW, GFP_NOFS);
2642         }
2643 
2644         /*
2645          * We may have short-circuited the log tree with the full commit logic
2646          * and left ordered extents on our list, so clear these out to keep us
2647          * from leaking inodes and memory.
2648          */
2649         btrfs_free_logged_extents(log, 0);
2650         btrfs_free_logged_extents(log, 1);
2651 
2652         free_extent_buffer(log->node);
2653         kfree(log);
2654 }
2655 
2656 /*
2657  * free all the extents used by the tree log.  This should be called
2658  * at commit time of the full transaction
2659  */
2660 int btrfs_free_log(struct btrfs_trans_handle *trans, struct btrfs_root *root)
2661 {
2662         if (root->log_root) {
2663                 free_log_tree(trans, root->log_root);
2664                 root->log_root = NULL;
2665         }
2666         return 0;
2667 }
2668 
2669 int btrfs_free_log_root_tree(struct btrfs_trans_handle *trans,
2670                              struct btrfs_fs_info *fs_info)
2671 {
2672         if (fs_info->log_root_tree) {
2673                 free_log_tree(trans, fs_info->log_root_tree);
2674                 fs_info->log_root_tree = NULL;
2675         }
2676         return 0;
2677 }
2678 
2679 /*
2680  * If both a file and directory are logged, and unlinks or renames are
2681  * mixed in, we have a few interesting corners:
2682  *
2683  * create file X in dir Y
2684  * link file X to X.link in dir Y
2685  * fsync file X
2686  * unlink file X but leave X.link
2687  * fsync dir Y
2688  *
2689  * After a crash we would expect only X.link to exist.  But file X
2690  * didn't get fsync'd again so the log has back refs for X and X.link.
2691  *
2692  * We solve this by removing directory entries and inode backrefs from the
2693  * log when a file that was logged in the current transaction is
2694  * unlinked.  Any later fsync will include the updated log entries, and
2695  * we'll be able to reconstruct the proper directory items from backrefs.
2696  *
2697  * This optimizations allows us to avoid relogging the entire inode
2698  * or the entire directory.
2699  */
2700 int btrfs_del_dir_entries_in_log(struct btrfs_trans_handle *trans,
2701                                  struct btrfs_root *root,
2702                                  const char *name, int name_len,
2703                                  struct inode *dir, u64 index)
2704 {
2705         struct btrfs_root *log;
2706         struct btrfs_dir_item *di;
2707         struct btrfs_path *path;
2708         int ret;
2709         int err = 0;
2710         int bytes_del = 0;
2711         u64 dir_ino = btrfs_ino(dir);
2712 
2713         if (BTRFS_I(dir)->logged_trans < trans->transid)
2714                 return 0;
2715 
2716         ret = join_running_log_trans(root);
2717         if (ret)
2718                 return 0;
2719 
2720         mutex_lock(&BTRFS_I(dir)->log_mutex);
2721 
2722         log = root->log_root;
2723         path = btrfs_alloc_path();
2724         if (!path) {
2725                 err = -ENOMEM;
2726                 goto out_unlock;
2727         }
2728 
2729         di = btrfs_lookup_dir_item(trans, log, path, dir_ino,
2730                                    name, name_len, -1);
2731         if (IS_ERR(di)) {
2732                 err = PTR_ERR(di);
2733                 goto fail;
2734         }
2735         if (di) {
2736                 ret = btrfs_delete_one_dir_name(trans, log, path, di);
2737                 bytes_del += name_len;
2738                 if (ret) {
2739                         err = ret;
2740                         goto fail;
2741                 }
2742         }
2743         btrfs_release_path(path);
2744         di = btrfs_lookup_dir_index_item(trans, log, path, dir_ino,
2745                                          index, name, name_len, -1);
2746         if (IS_ERR(di)) {
2747                 err = PTR_ERR(di);
2748                 goto fail;
2749         }
2750         if (di) {
2751                 ret = btrfs_delete_one_dir_name(trans, log, path, di);
2752                 bytes_del += name_len;
2753                 if (ret) {
2754                         err = ret;
2755                         goto fail;
2756                 }
2757         }
2758 
2759         /* update the directory size in the log to reflect the names
2760          * we have removed
2761          */
2762         if (bytes_del) {
2763                 struct btrfs_key key;
2764 
2765                 key.objectid = dir_ino;
2766                 key.offset = 0;
2767                 key.type = BTRFS_INODE_ITEM_KEY;
2768                 btrfs_release_path(path);
2769 
2770                 ret = btrfs_search_slot(trans, log, &key, path, 0, 1);
2771                 if (ret < 0) {
2772                         err = ret;
2773                         goto fail;
2774                 }
2775                 if (ret == 0) {
2776                         struct btrfs_inode_item *item;
2777                         u64 i_size;
2778 
2779                         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2780                                               struct btrfs_inode_item);
2781                         i_size = btrfs_inode_size(path->nodes[0], item);
2782                         if (i_size > bytes_del)
2783                                 i_size -= bytes_del;
2784                         else
2785                                 i_size = 0;
2786                         btrfs_set_inode_size(path->nodes[0], item, i_size);
2787                         btrfs_mark_buffer_dirty(path->nodes[0]);
2788                 } else
2789                         ret = 0;
2790                 btrfs_release_path(path);
2791         }
2792 fail:
2793         btrfs_free_path(path);
2794 out_unlock:
2795         mutex_unlock(&BTRFS_I(dir)->log_mutex);
2796         if (ret == -ENOSPC) {
2797                 root->fs_info->last_trans_log_full_commit = trans->transid;
2798                 ret = 0;
2799         } else if (ret < 0)
2800                 btrfs_abort_transaction(trans, root, ret);
2801 
2802         btrfs_end_log_trans(root);
2803 
2804         return err;
2805 }
2806 
2807 /* see comments for btrfs_del_dir_entries_in_log */
2808 int btrfs_del_inode_ref_in_log(struct btrfs_trans_handle *trans,
2809                                struct btrfs_root *root,
2810                                const char *name, int name_len,
2811                                struct inode *inode, u64 dirid)
2812 {
2813         struct btrfs_root *log;
2814         u64 index;
2815         int ret;
2816 
2817         if (BTRFS_I(inode)->logged_trans < trans->transid)
2818                 return 0;
2819 
2820         ret = join_running_log_trans(root);
2821         if (ret)
2822                 return 0;
2823         log = root->log_root;
2824         mutex_lock(&BTRFS_I(inode)->log_mutex);
2825 
2826         ret = btrfs_del_inode_ref(trans, log, name, name_len, btrfs_ino(inode),
2827                                   dirid, &index);
2828         mutex_unlock(&BTRFS_I(inode)->log_mutex);
2829         if (ret == -ENOSPC) {
2830                 root->fs_info->last_trans_log_full_commit = trans->transid;
2831                 ret = 0;
2832         } else if (ret < 0 && ret != -ENOENT)
2833                 btrfs_abort_transaction(trans, root, ret);
2834         btrfs_end_log_trans(root);
2835 
2836         return ret;
2837 }
2838 
2839 /*
2840  * creates a range item in the log for 'dirid'.  first_offset and
2841  * last_offset tell us which parts of the key space the log should
2842  * be considered authoritative for.
2843  */
2844 static noinline int insert_dir_log_key(struct btrfs_trans_handle *trans,
2845                                        struct btrfs_root *log,
2846                                        struct btrfs_path *path,
2847                                        int key_type, u64 dirid,
2848                                        u64 first_offset, u64 last_offset)
2849 {
2850         int ret;
2851         struct btrfs_key key;
2852         struct btrfs_dir_log_item *item;
2853 
2854         key.objectid = dirid;
2855         key.offset = first_offset;
2856         if (key_type == BTRFS_DIR_ITEM_KEY)
2857                 key.type = BTRFS_DIR_LOG_ITEM_KEY;
2858         else
2859                 key.type = BTRFS_DIR_LOG_INDEX_KEY;
2860         ret = btrfs_insert_empty_item(trans, log, path, &key, sizeof(*item));
2861         if (ret)
2862                 return ret;
2863 
2864         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2865                               struct btrfs_dir_log_item);
2866         btrfs_set_dir_log_end(path->nodes[0], item, last_offset);
2867         btrfs_mark_buffer_dirty(path->nodes[0]);
2868         btrfs_release_path(path);
2869         return 0;
2870 }
2871 
2872 /*
2873  * log all the items included in the current transaction for a given
2874  * directory.  This also creates the range items in the log tree required
2875  * to replay anything deleted before the fsync
2876  */
2877 static noinline int log_dir_items(struct btrfs_trans_handle *trans,
2878                           struct btrfs_root *root, struct inode *inode,
2879                           struct btrfs_path *path,
2880                           struct btrfs_path *dst_path, int key_type,
2881                           u64 min_offset, u64 *last_offset_ret)
2882 {
2883         struct btrfs_key min_key;
2884         struct btrfs_root *log = root->log_root;
2885         struct extent_buffer *src;
2886         int err = 0;
2887         int ret;
2888         int i;
2889         int nritems;
2890         u64 first_offset = min_offset;
2891         u64 last_offset = (u64)-1;
2892         u64 ino = btrfs_ino(inode);
2893 
2894         log = root->log_root;
2895 
2896         min_key.objectid = ino;
2897         min_key.type = key_type;
2898         min_key.offset = min_offset;
2899 
2900         path->keep_locks = 1;
2901 
2902         ret = btrfs_search_forward(root, &min_key, path, trans->transid);
2903 
2904         /*
2905          * we didn't find anything from this transaction, see if there
2906          * is anything at all
2907          */
2908         if (ret != 0 || min_key.objectid != ino || min_key.type != key_type) {
2909                 min_key.objectid = ino;
2910                 min_key.type = key_type;
2911                 min_key.offset = (u64)-1;
2912                 btrfs_release_path(path);
2913                 ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
2914                 if (ret < 0) {
2915                         btrfs_release_path(path);
2916                         return ret;
2917                 }
2918                 ret = btrfs_previous_item(root, path, ino, key_type);
2919 
2920                 /* if ret == 0 there are items for this type,
2921                  * create a range to tell us the last key of this type.
2922                  * otherwise, there are no items in this directory after
2923                  * *min_offset, and we create a range to indicate that.
2924                  */
2925                 if (ret == 0) {
2926                         struct btrfs_key tmp;
2927                         btrfs_item_key_to_cpu(path->nodes[0], &tmp,
2928                                               path->slots[0]);
2929                         if (key_type == tmp.type)
2930                                 first_offset = max(min_offset, tmp.offset) + 1;
2931                 }
2932                 goto done;
2933         }
2934 
2935         /* go backward to find any previous key */
2936         ret = btrfs_previous_item(root, path, ino, key_type);
2937         if (ret == 0) {
2938                 struct btrfs_key tmp;
2939                 btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
2940                 if (key_type == tmp.type) {
2941                         first_offset = tmp.offset;
2942                         ret = overwrite_item(trans, log, dst_path,
2943                                              path->nodes[0], path->slots[0],
2944                                              &tmp);
2945                         if (ret) {
2946                                 err = ret;
2947                                 goto done;
2948                         }
2949                 }
2950         }
2951         btrfs_release_path(path);
2952 
2953         /* find the first key from this transaction again */
2954         ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
2955         if (WARN_ON(ret != 0))
2956                 goto done;
2957 
2958         /*
2959          * we have a block from this transaction, log every item in it
2960          * from our directory
2961          */
2962         while (1) {
2963                 struct btrfs_key tmp;
2964                 src = path->nodes[0];
2965                 nritems = btrfs_header_nritems(src);
2966                 for (i = path->slots[0]; i < nritems; i++) {
2967                         btrfs_item_key_to_cpu(src, &min_key, i);
2968 
2969                         if (min_key.objectid != ino || min_key.type != key_type)
2970                                 goto done;
2971                         ret = overwrite_item(trans, log, dst_path, src, i,
2972                                              &min_key);
2973                         if (ret) {
2974                                 err = ret;
2975                                 goto done;
2976                         }
2977                 }
2978                 path->slots[0] = nritems;
2979 
2980                 /*
2981                  * look ahead to the next item and see if it is also
2982                  * from this directory and from this transaction
2983                  */
2984                 ret = btrfs_next_leaf(root, path);
2985                 if (ret == 1) {
2986                         last_offset = (u64)-1;
2987                         goto done;
2988                 }
2989                 btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
2990                 if (tmp.objectid != ino || tmp.type != key_type) {
2991                         last_offset = (u64)-1;
2992                         goto done;
2993                 }
2994                 if (btrfs_header_generation(path->nodes[0]) != trans->transid) {
2995                         ret = overwrite_item(trans, log, dst_path,
2996                                              path->nodes[0], path->slots[0],
2997                                              &tmp);
2998                         if (ret)
2999                                 err = ret;
3000                         else
3001                                 last_offset = tmp.offset;
3002                         goto done;
3003                 }
3004         }
3005 done:
3006         btrfs_release_path(path);
3007         btrfs_release_path(dst_path);
3008 
3009         if (err == 0) {
3010                 *last_offset_ret = last_offset;
3011                 /*
3012                  * insert the log range keys to indicate where the log
3013                  * is valid
3014                  */
3015                 ret = insert_dir_log_key(trans, log, path, key_type,
3016                                          ino, first_offset, last_offset);
3017                 if (ret)
3018                         err = ret;
3019         }
3020         return err;
3021 }
3022 
3023 /*
3024  * logging directories is very similar to logging inodes, We find all the items
3025  * from the current transaction and write them to the log.
3026  *
3027  * The recovery code scans the directory in the subvolume, and if it finds a
3028  * key in the range logged that is not present in the log tree, then it means
3029  * that dir entry was unlinked during the transaction.
3030  *
3031  * In order for that scan to work, we must include one key smaller than
3032  * the smallest logged by this transaction and one key larger than the largest
3033  * key logged by this transaction.
3034  */
3035 static noinline int log_directory_changes(struct btrfs_trans_handle *trans,
3036                           struct btrfs_root *root, struct inode *inode,
3037                           struct btrfs_path *path,
3038                           struct btrfs_path *dst_path)
3039 {
3040         u64 min_key;
3041         u64 max_key;
3042         int ret;
3043         int key_type = BTRFS_DIR_ITEM_KEY;
3044 
3045 again:
3046         min_key = 0;
3047         max_key = 0;
3048         while (1) {
3049                 ret = log_dir_items(trans, root, inode, path,
3050                                     dst_path, key_type, min_key,
3051                                     &max_key);
3052                 if (ret)
3053                         return ret;
3054                 if (max_key == (u64)-1)
3055                         break;
3056                 min_key = max_key + 1;
3057         }
3058 
3059         if (key_type == BTRFS_DIR_ITEM_KEY) {
3060                 key_type = BTRFS_DIR_INDEX_KEY;
3061                 goto again;
3062         }
3063         return 0;
3064 }
3065 
3066 /*
3067  * a helper function to drop items from the log before we relog an
3068  * inode.  max_key_type indicates the highest item type to remove.
3069  * This cannot be run for file data extents because it does not
3070  * free the extents they point to.
3071  */
3072 static int drop_objectid_items(struct btrfs_trans_handle *trans,
3073                                   struct btrfs_root *log,
3074                                   struct btrfs_path *path,
3075                                   u64 objectid, int max_key_type)
3076 {
3077         int ret;
3078         struct btrfs_key key;
3079         struct btrfs_key found_key;
3080         int start_slot;
3081 
3082         key.objectid = objectid;
3083         key.type = max_key_type;
3084         key.offset = (u64)-1;
3085 
3086         while (1) {
3087                 ret = btrfs_search_slot(trans, log, &key, path, -1, 1);
3088                 BUG_ON(ret == 0); /* Logic error */
3089                 if (ret < 0)
3090                         break;
3091 
3092                 if (path->slots[0] == 0)
3093                         break;
3094 
3095                 path->slots[0]--;
3096                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
3097                                       path->slots[0]);
3098 
3099                 if (found_key.objectid != objectid)
3100                         break;
3101 
3102                 found_key.offset = 0;
3103                 found_key.type = 0;
3104                 ret = btrfs_bin_search(path->nodes[0], &found_key, 0,
3105                                        &start_slot);
3106 
3107                 ret = btrfs_del_items(trans, log, path, start_slot,
3108                                       path->slots[0] - start_slot + 1);
3109                 /*
3110                  * If start slot isn't 0 then we don't need to re-search, we've
3111                  * found the last guy with the objectid in this tree.
3112                  */
3113                 if (ret || start_slot != 0)
3114                         break;
3115                 btrfs_release_path(path);
3116         }
3117         btrfs_release_path(path);
3118         if (ret > 0)
3119                 ret = 0;
3120         return ret;
3121 }
3122 
3123 static void fill_inode_item(struct btrfs_trans_handle *trans,
3124                             struct extent_buffer *leaf,
3125                             struct btrfs_inode_item *item,
3126                             struct inode *inode, int log_inode_only)
3127 {
3128         struct btrfs_map_token token;
3129 
3130         btrfs_init_map_token(&token);
3131 
3132         if (log_inode_only) {
3133                 /* set the generation to zero so the recover code
3134                  * can tell the difference between an logging
3135                  * just to say 'this inode exists' and a logging
3136                  * to say 'update this inode with these values'
3137                  */
3138                 btrfs_set_token_inode_generation(leaf, item, 0, &token);
3139                 btrfs_set_token_inode_size(leaf, item, 0, &token);
3140         } else {
3141                 btrfs_set_token_inode_generation(leaf, item,
3142                                                  BTRFS_I(inode)->generation,
3143                                                  &token);
3144                 btrfs_set_token_inode_size(leaf, item, inode->i_size, &token);
3145         }
3146 
3147         btrfs_set_token_inode_uid(leaf, item, i_uid_read(inode), &token);
3148         btrfs_set_token_inode_gid(leaf, item, i_gid_read(inode), &token);
3149         btrfs_set_token_inode_mode(leaf, item, inode->i_mode, &token);
3150         btrfs_set_token_inode_nlink(leaf, item, inode->i_nlink, &token);
3151 
3152         btrfs_set_token_timespec_sec(leaf, btrfs_inode_atime(item),
3153                                      inode->i_atime.tv_sec, &token);
3154         btrfs_set_token_timespec_nsec(leaf, btrfs_inode_atime(item),
3155                                       inode->i_atime.tv_nsec, &token);
3156 
3157         btrfs_set_token_timespec_sec(leaf, btrfs_inode_mtime(item),
3158                                      inode->i_mtime.tv_sec, &token);
3159         btrfs_set_token_timespec_nsec(leaf, btrfs_inode_mtime(item),
3160                                       inode->i_mtime.tv_nsec, &token);
3161 
3162         btrfs_set_token_timespec_sec(leaf, btrfs_inode_ctime(item),
3163                                      inode->i_ctime.tv_sec, &token);
3164         btrfs_set_token_timespec_nsec(leaf, btrfs_inode_ctime(item),
3165                                       inode->i_ctime.tv_nsec, &token);
3166 
3167         btrfs_set_token_inode_nbytes(leaf, item, inode_get_bytes(inode),
3168                                      &token);
3169 
3170         btrfs_set_token_inode_sequence(leaf, item, inode->i_version, &token);
3171         btrfs_set_token_inode_transid(leaf, item, trans->transid, &token);
3172         btrfs_set_token_inode_rdev(leaf, item, inode->i_rdev, &token);
3173         btrfs_set_token_inode_flags(leaf, item, BTRFS_I(inode)->flags, &token);
3174         btrfs_set_token_inode_block_group(leaf, item, 0, &token);
3175 }
3176 
3177 static int log_inode_item(struct btrfs_trans_handle *trans,
3178                           struct btrfs_root *log, struct btrfs_path *path,
3179                           struct inode *inode)
3180 {
3181         struct btrfs_inode_item *inode_item;
3182         int ret;
3183 
3184         ret = btrfs_insert_empty_item(trans, log, path,
3185                                       &BTRFS_I(inode)->location,
3186                                       sizeof(*inode_item));
3187         if (ret && ret != -EEXIST)
3188                 return ret;
3189         inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
3190                                     struct btrfs_inode_item);
3191         fill_inode_item(trans, path->nodes[0], inode_item, inode, 0);
3192         btrfs_release_path(path);
3193         return 0;
3194 }
3195 
3196 static noinline int copy_items(struct btrfs_trans_handle *trans,
3197                                struct inode *inode,
3198                                struct btrfs_path *dst_path,
3199                                struct btrfs_path *src_path, u64 *last_extent,
3200                                int start_slot, int nr, int inode_only)
3201 {
3202         unsigned long src_offset;
3203         unsigned long dst_offset;
3204         struct btrfs_root *log = BTRFS_I(inode)->root->log_root;
3205         struct btrfs_file_extent_item *extent;
3206         struct btrfs_inode_item *inode_item;
3207         struct extent_buffer *src = src_path->nodes[0];
3208         struct btrfs_key first_key, last_key, key;
3209         int ret;
3210         struct btrfs_key *ins_keys;
3211         u32 *ins_sizes;
3212         char *ins_data;
3213         int i;
3214         struct list_head ordered_sums;
3215         int skip_csum = BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM;
3216         bool has_extents = false;
3217         bool need_find_last_extent = (*last_extent == 0);
3218         bool done = false;
3219 
3220         INIT_LIST_HEAD(&ordered_sums);
3221 
3222         ins_data = kmalloc(nr * sizeof(struct btrfs_key) +
3223                            nr * sizeof(u32), GFP_NOFS);
3224         if (!ins_data)
3225                 return -ENOMEM;
3226 
3227         first_key.objectid = (u64)-1;
3228 
3229         ins_sizes = (u32 *)ins_data;
3230         ins_keys = (struct btrfs_key *)(ins_data + nr * sizeof(u32));
3231 
3232         for (i = 0; i < nr; i++) {
3233                 ins_sizes[i] = btrfs_item_size_nr(src, i + start_slot);
3234                 btrfs_item_key_to_cpu(src, ins_keys + i, i + start_slot);
3235         }
3236         ret = btrfs_insert_empty_items(trans, log, dst_path,
3237                                        ins_keys, ins_sizes, nr);
3238         if (ret) {
3239                 kfree(ins_data);
3240                 return ret;
3241         }
3242 
3243         for (i = 0; i < nr; i++, dst_path->slots[0]++) {
3244                 dst_offset = btrfs_item_ptr_offset(dst_path->nodes[0],
3245                                                    dst_path->slots[0]);
3246 
3247                 src_offset = btrfs_item_ptr_offset(src, start_slot + i);
3248 
3249                 if ((i == (nr - 1)))
3250                         last_key = ins_keys[i];
3251 
3252                 if (ins_keys[i].type == BTRFS_INODE_ITEM_KEY) {
3253                         inode_item = btrfs_item_ptr(dst_path->nodes[0],
3254                                                     dst_path->slots[0],
3255                                                     struct btrfs_inode_item);
3256                         fill_inode_item(trans, dst_path->nodes[0], inode_item,
3257                                         inode, inode_only == LOG_INODE_EXISTS);
3258                 } else {
3259                         copy_extent_buffer(dst_path->nodes[0], src, dst_offset,
3260                                            src_offset, ins_sizes[i]);
3261                 }
3262 
3263                 /*
3264                  * We set need_find_last_extent here in case we know we were
3265                  * processing other items and then walk into the first extent in
3266                  * the inode.  If we don't hit an extent then nothing changes,
3267                  * we'll do the last search the next time around.
3268                  */
3269                 if (ins_keys[i].type == BTRFS_EXTENT_DATA_KEY) {
3270                         has_extents = true;
3271                         if (need_find_last_extent &&
3272                             first_key.objectid == (u64)-1)
3273                                 first_key = ins_keys[i];
3274                 } else {
3275                         need_find_last_extent = false;
3276                 }
3277 
3278                 /* take a reference on file data extents so that truncates
3279                  * or deletes of this inode don't have to relog the inode
3280                  * again
3281                  */
3282                 if (btrfs_key_type(ins_keys + i) == BTRFS_EXTENT_DATA_KEY &&
3283                     !skip_csum) {
3284                         int found_type;
3285                         extent = btrfs_item_ptr(src, start_slot + i,
3286                                                 struct btrfs_file_extent_item);
3287 
3288                         if (btrfs_file_extent_generation(src, extent) < trans->transid)
3289                                 continue;
3290 
3291                         found_type = btrfs_file_extent_type(src, extent);
3292                         if (found_type == BTRFS_FILE_EXTENT_REG) {
3293                                 u64 ds, dl, cs, cl;
3294                                 ds = btrfs_file_extent_disk_bytenr(src,
3295                                                                 extent);
3296                                 /* ds == 0 is a hole */
3297                                 if (ds == 0)
3298                                         continue;
3299 
3300                                 dl = btrfs_file_extent_disk_num_bytes(src,
3301                                                                 extent);
3302                                 cs = btrfs_file_extent_offset(src, extent);
3303                                 cl = btrfs_file_extent_num_bytes(src,
3304                                                                 extent);
3305                                 if (btrfs_file_extent_compression(src,
3306                                                                   extent)) {
3307                                         cs = 0;
3308                                         cl = dl;
3309                                 }
3310 
3311                                 ret = btrfs_lookup_csums_range(
3312                                                 log->fs_info->csum_root,
3313                                                 ds + cs, ds + cs + cl - 1,
3314                                                 &ordered_sums, 0);
3315                                 if (ret) {
3316                                         btrfs_release_path(dst_path);
3317                                         kfree(ins_data);
3318                                         return ret;
3319                                 }
3320                         }
3321                 }
3322         }
3323 
3324         btrfs_mark_buffer_dirty(dst_path->nodes[0]);
3325         btrfs_release_path(dst_path);
3326         kfree(ins_data);
3327 
3328         /*
3329          * we have to do this after the loop above to avoid changing the
3330          * log tree while trying to change the log tree.
3331          */
3332         ret = 0;
3333         while (!list_empty(&ordered_sums)) {
3334                 struct btrfs_ordered_sum *sums = list_entry(ordered_sums.next,
3335                                                    struct btrfs_ordered_sum,
3336                                                    list);
3337                 if (!ret)
3338                         ret = btrfs_csum_file_blocks(trans, log, sums);
3339                 list_del(&sums->list);
3340                 kfree(sums);
3341         }
3342 
3343         if (!has_extents)
3344                 return ret;
3345 
3346         /*
3347          * Because we use btrfs_search_forward we could skip leaves that were
3348          * not modified and then assume *last_extent is valid when it really
3349          * isn't.  So back up to the previous leaf and read the end of the last
3350          * extent before we go and fill in holes.
3351          */
3352         if (need_find_last_extent) {
3353                 u64 len;
3354 
3355                 ret = btrfs_prev_leaf(BTRFS_I(inode)->root, src_path);
3356                 if (ret < 0)
3357                         return ret;
3358                 if (ret)
3359                         goto fill_holes;
3360                 if (src_path->slots[0])
3361                         src_path->slots[0]--;
3362                 src = src_path->nodes[0];
3363                 btrfs_item_key_to_cpu(src, &key, src_path->slots[0]);
3364                 if (key.objectid != btrfs_ino(inode) ||
3365                     key.type != BTRFS_EXTENT_DATA_KEY)
3366                         goto fill_holes;
3367                 extent = btrfs_item_ptr(src, src_path->slots[0],
3368                                         struct btrfs_file_extent_item);
3369                 if (btrfs_file_extent_type(src, extent) ==
3370                     BTRFS_FILE_EXTENT_INLINE) {
3371                         len = btrfs_file_extent_inline_len(src,
3372                                                            src_path->slots[0],
3373                                                            extent);
3374                         *last_extent = ALIGN(key.offset + len,
3375                                              log->sectorsize);
3376                 } else {
3377                         len = btrfs_file_extent_num_bytes(src, extent);
3378                         *last_extent = key.offset + len;
3379                 }
3380         }
3381 fill_holes:
3382         /* So we did prev_leaf, now we need to move to the next leaf, but a few
3383          * things could have happened
3384          *
3385          * 1) A merge could have happened, so we could currently be on a leaf
3386          * that holds what we were copying in the first place.
3387          * 2) A split could have happened, and now not all of the items we want
3388          * are on the same leaf.
3389          *
3390          * So we need to adjust how we search for holes, we need to drop the
3391          * path and re-search for the first extent key we found, and then walk
3392          * forward until we hit the last one we copied.
3393          */
3394         if (need_find_last_extent) {
3395                 /* btrfs_prev_leaf could return 1 without releasing the path */
3396                 btrfs_release_path(src_path);
3397                 ret = btrfs_search_slot(NULL, BTRFS_I(inode)->root, &first_key,
3398                                         src_path, 0, 0);
3399                 if (ret < 0)
3400                         return ret;
3401                 ASSERT(ret == 0);
3402                 src = src_path->nodes[0];
3403                 i = src_path->slots[0];
3404         } else {
3405                 i = start_slot;
3406         }
3407 
3408         /*
3409          * Ok so here we need to go through and fill in any holes we may have
3410          * to make sure that holes are punched for those areas in case they had
3411          * extents previously.
3412          */
3413         while (!done) {
3414                 u64 offset, len;
3415                 u64 extent_end;
3416 
3417                 if (i >= btrfs_header_nritems(src_path->nodes[0])) {
3418                         ret = btrfs_next_leaf(BTRFS_I(inode)->root, src_path);
3419                         if (ret < 0)
3420                                 return ret;
3421                         ASSERT(ret == 0);
3422                         src = src_path->nodes[0];
3423                         i = 0;
3424                 }
3425 
3426                 btrfs_item_key_to_cpu(src, &key, i);
3427                 if (!btrfs_comp_cpu_keys(&key, &last_key))
3428                         done = true;
3429                 if (key.objectid != btrfs_ino(inode) ||
3430                     key.type != BTRFS_EXTENT_DATA_KEY) {
3431                         i++;
3432                         continue;
3433                 }
3434                 extent = btrfs_item_ptr(src, i, struct btrfs_file_extent_item);
3435                 if (btrfs_file_extent_type(src, extent) ==
3436                     BTRFS_FILE_EXTENT_INLINE) {
3437                         len = btrfs_file_extent_inline_len(src, i, extent);
3438                         extent_end = ALIGN(key.offset + len, log->sectorsize);
3439                 } else {
3440                         len = btrfs_file_extent_num_bytes(src, extent);
3441                         extent_end = key.offset + len;
3442                 }
3443                 i++;
3444 
3445                 if (*last_extent == key.offset) {
3446                         *last_extent = extent_end;
3447                         continue;
3448                 }
3449                 offset = *last_extent;
3450                 len = key.offset - *last_extent;
3451                 ret = btrfs_insert_file_extent(trans, log, btrfs_ino(inode),
3452                                                offset, 0, 0, len, 0, len, 0,
3453                                                0, 0);
3454                 if (ret)
3455                         break;
3456                 *last_extent = offset + len;
3457         }
3458         /*
3459          * Need to let the callers know we dropped the path so they should
3460          * re-search.
3461          */
3462         if (!ret && need_find_last_extent)
3463                 ret = 1;
3464         return ret;
3465 }
3466 
3467 static int extent_cmp(void *priv, struct list_head *a, struct list_head *b)
3468 {
3469         struct extent_map *em1, *em2;
3470 
3471         em1 = list_entry(a, struct extent_map, list);
3472         em2 = list_entry(b, struct extent_map, list);
3473 
3474         if (em1->start < em2->start)
3475                 return -1;
3476         else if (em1->start > em2->start)
3477                 return 1;
3478         return 0;
3479 }
3480 
3481 static int log_one_extent(struct btrfs_trans_handle *trans,
3482                           struct inode *inode, struct btrfs_root *root,
3483                           struct extent_map *em, struct btrfs_path *path)
3484 {
3485         struct btrfs_root *log = root->log_root;
3486         struct btrfs_file_extent_item *fi;
3487         struct extent_buffer *leaf;
3488         struct btrfs_ordered_extent *ordered;
3489         struct list_head ordered_sums;
3490         struct btrfs_map_token token;
3491         struct btrfs_key key;
3492         u64 mod_start = em->mod_start;
3493         u64 mod_len = em->mod_len;
3494         u64 csum_offset;
3495         u64 csum_len;
3496         u64 extent_offset = em->start - em->orig_start;
3497         u64 block_len;
3498         int ret;
3499         int index = log->log_transid % 2;
3500         bool skip_csum = BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM;
3501         int extent_inserted = 0;
3502 
3503         INIT_LIST_HEAD(&ordered_sums);
3504         btrfs_init_map_token(&token);
3505 
3506         ret = __btrfs_drop_extents(trans, log, inode, path, em->start,
3507                                    em->start + em->len, NULL, 0, 1,
3508                                    sizeof(*fi), &extent_inserted);
3509         if (ret)
3510                 return ret;
3511 
3512         if (!extent_inserted) {
3513                 key.objectid = btrfs_ino(inode);
3514                 key.type = BTRFS_EXTENT_DATA_KEY;
3515                 key.offset = em->start;
3516 
3517                 ret = btrfs_insert_empty_item(trans, log, path, &key,
3518                                               sizeof(*fi));
3519                 if (ret)
3520                         return ret;
3521         }
3522         leaf = path->nodes[0];
3523         fi = btrfs_item_ptr(leaf, path->slots[0],
3524                             struct btrfs_file_extent_item);
3525 
3526         btrfs_set_token_file_extent_generation(leaf, fi, em->generation,
3527                                                &token);
3528         if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags)) {
3529                 skip_csum = true;
3530                 btrfs_set_token_file_extent_type(leaf, fi,
3531                                                  BTRFS_FILE_EXTENT_PREALLOC,
3532                                                  &token);
3533         } else {
3534                 btrfs_set_token_file_extent_type(leaf, fi,
3535                                                  BTRFS_FILE_EXTENT_REG,
3536                                                  &token);
3537                 if (em->block_start == EXTENT_MAP_HOLE)
3538                         skip_csum = true;
3539         }
3540 
3541         block_len = max(em->block_len, em->orig_block_len);
3542         if (em->compress_type != BTRFS_COMPRESS_NONE) {
3543                 btrfs_set_token_file_extent_disk_bytenr(leaf, fi,
3544                                                         em->block_start,
3545                                                         &token);
3546                 btrfs_set_token_file_extent_disk_num_bytes(leaf, fi, block_len,
3547                                                            &token);
3548         } else if (em->block_start < EXTENT_MAP_LAST_BYTE) {
3549                 btrfs_set_token_file_extent_disk_bytenr(leaf, fi,
3550                                                         em->block_start -
3551                                                         extent_offset, &token);
3552                 btrfs_set_token_file_extent_disk_num_bytes(leaf, fi, block_len,
3553                                                            &token);
3554         } else {
3555                 btrfs_set_token_file_extent_disk_bytenr(leaf, fi, 0, &token);
3556                 btrfs_set_token_file_extent_disk_num_bytes(leaf, fi, 0,
3557                                                            &token);
3558         }
3559 
3560         btrfs_set_token_file_extent_offset(leaf, fi,
3561                                            em->start - em->orig_start,
3562                                            &token);
3563         btrfs_set_token_file_extent_num_bytes(leaf, fi, em->len, &token);
3564         btrfs_set_token_file_extent_ram_bytes(leaf, fi, em->ram_bytes, &token);
3565         btrfs_set_token_file_extent_compression(leaf, fi, em->compress_type,
3566                                                 &token);
3567         btrfs_set_token_file_extent_encryption(leaf, fi, 0, &token);
3568         btrfs_set_token_file_extent_other_encoding(leaf, fi, 0, &token);
3569         btrfs_mark_buffer_dirty(leaf);
3570 
3571         btrfs_release_path(path);
3572         if (ret) {
3573                 return ret;
3574         }
3575 
3576         if (skip_csum)
3577                 return 0;
3578 
3579         /*
3580          * First check and see if our csums are on our outstanding ordered
3581          * extents.
3582          */
3583 again:
3584         spin_lock_irq(&log->log_extents_lock[index]);
3585         list_for_each_entry(ordered, &log->logged_list[index], log_list) {
3586                 struct btrfs_ordered_sum *sum;
3587 
3588                 if (!mod_len)
3589                         break;
3590 
3591                 if (ordered->inode != inode)
3592                         continue;
3593 
3594                 if (ordered->file_offset + ordered->len <= mod_start ||
3595                     mod_start + mod_len <= ordered->file_offset)
3596                         continue;
3597 
3598                 /*
3599                  * We are going to copy all the csums on this ordered extent, so
3600                  * go ahead and adjust mod_start and mod_len in case this
3601                  * ordered extent has already been logged.
3602                  */
3603                 if (ordered->file_offset > mod_start) {
3604                         if (ordered->file_offset + ordered->len >=
3605                             mod_start + mod_len)
3606                                 mod_len = ordered->file_offset - mod_start;
3607                         /*
3608                          * If we have this case
3609                          *
3610                          * |--------- logged extent ---------|
3611                          *       |----- ordered extent ----|
3612                          *
3613                          * Just don't mess with mod_start and mod_len, we'll
3614                          * just end up logging more csums than we need and it
3615                          * will be ok.
3616                          */
3617                 } else {
3618                         if (ordered->file_offset + ordered->len <
3619                             mod_start + mod_len) {
3620                                 mod_len = (mod_start + mod_len) -
3621                                         (ordered->file_offset + ordered->len);
3622                                 mod_start = ordered->file_offset +
3623                                         ordered->len;
3624                         } else {
3625                                 mod_len = 0;
3626                         }
3627                 }
3628 
3629                 /*
3630                  * To keep us from looping for the above case of an ordered
3631                  * extent that falls inside of the logged extent.
3632                  */
3633                 if (test_and_set_bit(BTRFS_ORDERED_LOGGED_CSUM,
3634                                      &ordered->flags))
3635                         continue;
3636                 atomic_inc(&ordered->refs);
3637                 spin_unlock_irq(&log->log_extents_lock[index]);
3638                 /*
3639                  * we've dropped the lock, we must either break or
3640                  * start over after this.
3641                  */
3642 
3643                 if (ordered->csum_bytes_left) {
3644                         btrfs_start_ordered_extent(inode, ordered, 0);
3645                         wait_event(ordered->wait,
3646                                    ordered->csum_bytes_left == 0);
3647                 }
3648 
3649                 list_for_each_entry(sum, &ordered->list, list) {
3650                         ret = btrfs_csum_file_blocks(trans, log, sum);
3651                         if (ret) {
3652                                 btrfs_put_ordered_extent(ordered);
3653                                 goto unlocked;
3654                         }
3655                 }
3656                 btrfs_put_ordered_extent(ordered);
3657                 goto again;
3658 
3659         }
3660         spin_unlock_irq(&log->log_extents_lock[index]);
3661 unlocked:
3662 
3663         if (!mod_len || ret)
3664                 return ret;
3665 
3666         if (em->compress_type) {
3667                 csum_offset = 0;
3668                 csum_len = block_len;
3669         } else {
3670                 csum_offset = mod_start - em->start;
3671                 csum_len = mod_len;
3672         }
3673 
3674         /* block start is already adjusted for the file extent offset. */
3675         ret = btrfs_lookup_csums_range(log->fs_info->csum_root,
3676                                        em->block_start + csum_offset,
3677                                        em->block_start + csum_offset +
3678                                        csum_len - 1, &ordered_sums, 0);
3679         if (ret)
3680                 return ret;
3681 
3682         while (!list_empty(&ordered_sums)) {
3683                 struct btrfs_ordered_sum *sums = list_entry(ordered_sums.next,
3684                                                    struct btrfs_ordered_sum,
3685                                                    list);
3686                 if (!ret)
3687                         ret = btrfs_csum_file_blocks(trans, log, sums);
3688                 list_del(&sums->list);
3689                 kfree(sums);
3690         }
3691 
3692         return ret;
3693 }
3694 
3695 static int btrfs_log_changed_extents(struct btrfs_trans_handle *trans,
3696                                      struct btrfs_root *root,
3697                                      struct inode *inode,
3698                                      struct btrfs_path *path)
3699 {
3700         struct extent_map *em, *n;
3701         struct list_head extents;
3702         struct extent_map_tree *tree = &BTRFS_I(inode)->extent_tree;
3703         u64 test_gen;
3704         int ret = 0;
3705         int num = 0;
3706 
3707         INIT_LIST_HEAD(&extents);
3708 
3709         write_lock(&tree->lock);
3710         test_gen = root->fs_info->last_trans_committed;
3711 
3712         list_for_each_entry_safe(em, n, &tree->modified_extents, list) {
3713                 list_del_init(&em->list);
3714 
3715                 /*
3716                  * Just an arbitrary number, this can be really CPU intensive
3717                  * once we start getting a lot of extents, and really once we
3718                  * have a bunch of extents we just want to commit since it will
3719                  * be faster.
3720                  */
3721                 if (++num > 32768) {
3722                         list_del_init(&tree->modified_extents);
3723                         ret = -EFBIG;
3724                         goto process;
3725                 }
3726 
3727                 if (em->generation <= test_gen)
3728                         continue;
3729                 /* Need a ref to keep it from getting evicted from cache */
3730                 atomic_inc(&em->refs);
3731                 set_bit(EXTENT_FLAG_LOGGING, &em->flags);
3732                 list_add_tail(&em->list, &extents);
3733                 num++;
3734         }
3735 
3736         list_sort(NULL, &extents, extent_cmp);
3737 
3738 process:
3739         while (!list_empty(&extents)) {
3740                 em = list_entry(extents.next, struct extent_map, list);
3741 
3742                 list_del_init(&em->list);
3743 
3744                 /*
3745                  * If we had an error we just need to delete everybody from our
3746                  * private list.
3747                  */
3748                 if (ret) {
3749                         clear_em_logging(tree, em);
3750                         free_extent_map(em);
3751                         continue;
3752                 }
3753 
3754                 write_unlock(&tree->lock);
3755 
3756                 ret = log_one_extent(trans, inode, root, em, path);
3757                 write_lock(&tree->lock);
3758                 clear_em_logging(tree, em);
3759                 free_extent_map(em);
3760         }
3761         WARN_ON(!list_empty(&extents));
3762         write_unlock(&tree->lock);
3763 
3764         btrfs_release_path(path);
3765         return ret;
3766 }
3767 
3768 /* log a single inode in the tree log.
3769  * At least one parent directory for this inode must exist in the tree
3770  * or be logged already.
3771  *
3772  * Any items from this inode changed by the current transaction are copied
3773  * to the log tree.  An extra reference is taken on any extents in this
3774  * file, allowing us to avoid a whole pile of corner cases around logging
3775  * blocks that have been removed from the tree.
3776  *
3777  * See LOG_INODE_ALL and related defines for a description of what inode_only
3778  * does.
3779  *
3780  * This handles both files and directories.
3781  */
3782 static int btrfs_log_inode(struct btrfs_trans_handle *trans,
3783                              struct btrfs_root *root, struct inode *inode,
3784                              int inode_only)
3785 {
3786         struct btrfs_path *path;
3787         struct btrfs_path *dst_path;
3788         struct btrfs_key min_key;
3789         struct btrfs_key max_key;
3790         struct btrfs_root *log = root->log_root;
3791         struct extent_buffer *src = NULL;
3792         u64 last_extent = 0;
3793         int err = 0;
3794         int ret;
3795         int nritems;
3796         int ins_start_slot = 0;
3797         int ins_nr;
3798         bool fast_search = false;
3799         u64 ino = btrfs_ino(inode);
3800 
3801         path = btrfs_alloc_path();
3802         if (!path)
3803                 return -ENOMEM;
3804         dst_path = btrfs_alloc_path();
3805         if (!dst_path) {
3806                 btrfs_free_path(path);
3807                 return -ENOMEM;
3808         }
3809 
3810         min_key.objectid = ino;
3811         min_key.type = BTRFS_INODE_ITEM_KEY;
3812         min_key.offset = 0;
3813 
3814         max_key.objectid = ino;
3815 
3816 
3817         /* today the code can only do partial logging of directories */
3818         if (S_ISDIR(inode->i_mode) ||
3819             (!test_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
3820                        &BTRFS_I(inode)->runtime_flags) &&
3821              inode_only == LOG_INODE_EXISTS))
3822                 max_key.type = BTRFS_XATTR_ITEM_KEY;
3823         else
3824                 max_key.type = (u8)-1;
3825         max_key.offset = (u64)-1;
3826 
3827         /* Only run delayed items if we are a dir or a new file */
3828         if (S_ISDIR(inode->i_mode) ||
3829             BTRFS_I(inode)->generation > root->fs_info->last_trans_committed) {
3830                 ret = btrfs_commit_inode_delayed_items(trans, inode);
3831                 if (ret) {
3832                         btrfs_free_path(path);
3833                         btrfs_free_path(dst_path);
3834                         return ret;
3835                 }
3836         }
3837 
3838         mutex_lock(&BTRFS_I(inode)->log_mutex);
3839 
3840         btrfs_get_logged_extents(log, inode);
3841 
3842         /*
3843          * a brute force approach to making sure we get the most uptodate
3844          * copies of everything.
3845          */
3846         if (S_ISDIR(inode->i_mode)) {
3847                 int max_key_type = BTRFS_DIR_LOG_INDEX_KEY;
3848 
3849                 if (inode_only == LOG_INODE_EXISTS)
3850                         max_key_type = BTRFS_XATTR_ITEM_KEY;
3851                 ret = drop_objectid_items(trans, log, path, ino, max_key_type);
3852         } else {
3853                 if (test_and_clear_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
3854                                        &BTRFS_I(inode)->runtime_flags)) {
3855                         clear_bit(BTRFS_INODE_COPY_EVERYTHING,
3856                                   &BTRFS_I(inode)->runtime_flags);
3857                         ret = btrfs_truncate_inode_items(trans, log,
3858                                                          inode, 0, 0);
3859                 } else if (test_and_clear_bit(BTRFS_INODE_COPY_EVERYTHING,
3860                                               &BTRFS_I(inode)->runtime_flags) ||
3861                            inode_only == LOG_INODE_EXISTS) {
3862                         if (inode_only == LOG_INODE_ALL)
3863                                 fast_search = true;
3864                         max_key.type = BTRFS_XATTR_ITEM_KEY;
3865                         ret = drop_objectid_items(trans, log, path, ino,
3866                                                   max_key.type);
3867                 } else {
3868                         if (inode_only == LOG_INODE_ALL)
3869                                 fast_search = true;
3870                         ret = log_inode_item(trans, log, dst_path, inode);
3871                         if (ret) {
3872                                 err = ret;
3873                                 goto out_unlock;
3874                         }
3875                         goto log_extents;
3876                 }
3877 
3878         }
3879         if (ret) {
3880                 err = ret;
3881                 goto out_unlock;
3882         }
3883         path->keep_locks = 1;
3884 
3885         while (1) {
3886                 ins_nr = 0;
3887                 ret = btrfs_search_forward(root, &min_key,
3888                                            path, trans->transid);
3889                 if (ret != 0)
3890                         break;
3891 again:
3892                 /* note, ins_nr might be > 0 here, cleanup outside the loop */
3893                 if (min_key.objectid != ino)
3894                         break;
3895                 if (min_key.type > max_key.type)
3896                         break;
3897 
3898                 src = path->nodes[0];
3899                 if (ins_nr && ins_start_slot + ins_nr == path->slots[0]) {
3900                         ins_nr++;
3901                         goto next_slot;
3902                 } else if (!ins_nr) {
3903                         ins_start_slot = path->slots[0];
3904                         ins_nr = 1;
3905                         goto next_slot;
3906                 }
3907 
3908                 ret = copy_items(trans, inode, dst_path, path, &last_extent,
3909                                  ins_start_slot, ins_nr, inode_only);
3910                 if (ret < 0) {
3911                         err = ret;
3912                         goto out_unlock;
3913                 } if (ret) {
3914                         ins_nr = 0;
3915                         btrfs_release_path(path);
3916                         continue;
3917                 }
3918                 ins_nr = 1;
3919                 ins_start_slot = path->slots[0];
3920 next_slot:
3921 
3922                 nritems = btrfs_header_nritems(path->nodes[0]);
3923                 path->slots[0]++;
3924                 if (path->slots[0] < nritems) {
3925                         btrfs_item_key_to_cpu(path->nodes[0], &min_key,
3926                                               path->slots[0]);
3927                         goto again;
3928                 }
3929                 if (ins_nr) {
3930                         ret = copy_items(trans, inode, dst_path, path,
3931                                          &last_extent, ins_start_slot,
3932                                          ins_nr, inode_only);
3933                         if (ret < 0) {
3934                                 err = ret;
3935                                 goto out_unlock;
3936                         }
3937                         ret = 0;
3938                         ins_nr = 0;
3939                 }
3940                 btrfs_release_path(path);
3941 
3942                 if (min_key.offset < (u64)-1) {
3943                         min_key.offset++;
3944                 } else if (min_key.type < max_key.type) {
3945                         min_key.type++;
3946                         min_key.offset = 0;
3947                 } else {
3948                         break;
3949                 }
3950         }
3951         if (ins_nr) {
3952                 ret = copy_items(trans, inode, dst_path, path, &last_extent,
3953                                  ins_start_slot, ins_nr, inode_only);
3954                 if (ret < 0) {
3955                         err = ret;
3956                         goto out_unlock;
3957                 }
3958                 ret = 0;
3959                 ins_nr = 0;
3960         }
3961 
3962 log_extents:
3963         btrfs_release_path(path);
3964         btrfs_release_path(dst_path);
3965         if (fast_search) {
3966                 ret = btrfs_log_changed_extents(trans, root, inode, dst_path);
3967                 if (ret) {
3968                         err = ret;
3969                         goto out_unlock;
3970                 }
3971         } else if (inode_only == LOG_INODE_ALL) {
3972                 struct extent_map_tree *tree = &BTRFS_I(inode)->extent_tree;
3973                 struct extent_map *em, *n;
3974 
3975                 write_lock(&tree->lock);
3976                 list_for_each_entry_safe(em, n, &tree->modified_extents, list)
3977                         list_del_init(&em->list);
3978                 write_unlock(&tree->lock);
3979         }
3980 
3981         if (inode_only == LOG_INODE_ALL && S_ISDIR(inode->i_mode)) {
3982                 ret = log_directory_changes(trans, root, inode, path, dst_path);
3983                 if (ret) {
3984                         err = ret;
3985                         goto out_unlock;
3986                 }
3987         }
3988         BTRFS_I(inode)->logged_trans = trans->transid;
3989         BTRFS_I(inode)->last_log_commit = BTRFS_I(inode)->last_sub_trans;
3990 out_unlock:
3991         if (err)
3992                 btrfs_free_logged_extents(log, log->log_transid);
3993         mutex_unlock(&BTRFS_I(inode)->log_mutex);
3994 
3995         btrfs_free_path(path);
3996         btrfs_free_path(dst_path);
3997         return err;
3998 }
3999 
4000 /*
4001  * follow the dentry parent pointers up the chain and see if any
4002  * of the directories in it require a full commit before they can
4003  * be logged.  Returns zero if nothing special needs to be done or 1 if
4004  * a full commit is required.
4005  */
4006 static noinline int check_parent_dirs_for_sync(struct btrfs_trans_handle *trans,
4007                                                struct inode *inode,
4008                                                struct dentry *parent,
4009                                                struct super_block *sb,
4010                                                u64 last_committed)
4011 {
4012         int ret = 0;
4013         struct btrfs_root *root;
4014         struct dentry *old_parent = NULL;
4015         struct inode *orig_inode = inode;
4016 
4017         /*
4018          * for regular files, if its inode is already on disk, we don't
4019          * have to worry about the parents at all.  This is because
4020          * we can use the last_unlink_trans field to record renames
4021          * and other fun in this file.
4022          */
4023         if (S_ISREG(inode->i_mode) &&
4024             BTRFS_I(inode)->generation <= last_committed &&
4025             BTRFS_I(inode)->last_unlink_trans <= last_committed)
4026                         goto out;
4027 
4028         if (!S_ISDIR(inode->i_mode)) {
4029                 if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
4030                         goto out;
4031                 inode = parent->d_inode;
4032         }
4033 
4034         while (1) {
4035                 /*
4036                  * If we are logging a directory then we start with our inode,
4037                  * not our parents inode, so we need to skipp setting the
4038                  * logged_trans so that further down in the log code we don't
4039                  * think this inode has already been logged.
4040                  */
4041                 if (inode != orig_inode)
4042                         BTRFS_I(inode)->logged_trans = trans->transid;
4043                 smp_mb();
4044 
4045                 if (BTRFS_I(inode)->last_unlink_trans > last_committed) {
4046                         root = BTRFS_I(inode)->root;
4047 
4048                         /*
4049                          * make sure any commits to the log are forced
4050                          * to be full commits
4051                          */
4052                         root->fs_info->last_trans_log_full_commit =
4053                                 trans->transid;
4054                         ret = 1;
4055                         break;
4056                 }
4057 
4058                 if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
4059                         break;
4060 
4061                 if (IS_ROOT(parent))
4062                         break;
4063 
4064                 parent = dget_parent(parent);
4065                 dput(old_parent);
4066                 old_parent = parent;
4067                 inode = parent->d_inode;
4068 
4069         }
4070         dput(old_parent);
4071 out:
4072         return ret;
4073 }
4074 
4075 /*
4076  * helper function around btrfs_log_inode to make sure newly created
4077  * parent directories also end up in the log.  A minimal inode and backref
4078  * only logging is done of any parent directories that are older than
4079  * the last committed transaction
4080  */
4081 static int btrfs_log_inode_parent(struct btrfs_trans_handle *trans,
4082                                   struct btrfs_root *root, struct inode *inode,
4083                                   struct dentry *parent, int exists_only)
4084 {
4085         int inode_only = exists_only ? LOG_INODE_EXISTS : LOG_INODE_ALL;
4086         struct super_block *sb;
4087         struct dentry *old_parent = NULL;
4088         int ret = 0;
4089         u64 last_committed = root->fs_info->last_trans_committed;
4090 
4091         sb = inode->i_sb;
4092 
4093         if (btrfs_test_opt(root, NOTREELOG)) {
4094                 ret = 1;
4095                 goto end_no_trans;
4096         }
4097 
4098         if (root->fs_info->last_trans_log_full_commit >
4099             root->fs_info->last_trans_committed) {
4100                 ret = 1;
4101                 goto end_no_trans;
4102         }
4103 
4104         if (root != BTRFS_I(inode)->root ||
4105             btrfs_root_refs(&root->root_item) == 0) {
4106                 ret = 1;
4107                 goto end_no_trans;
4108         }
4109 
4110         ret = check_parent_dirs_for_sync(trans, inode, parent,
4111                                          sb, last_committed);
4112         if (ret)
4113                 goto end_no_trans;
4114 
4115         if (btrfs_inode_in_log(inode, trans->transid)) {
4116                 ret = BTRFS_NO_LOG_SYNC;
4117                 goto end_no_trans;
4118         }
4119 
4120         ret = start_log_trans(trans, root);
4121         if (ret)
4122                 goto end_trans;
4123 
4124         ret = btrfs_log_inode(trans, root, inode, inode_only);
4125         if (ret)
4126                 goto end_trans;
4127 
4128         /*
4129          * for regular files, if its inode is already on disk, we don't
4130          * have to worry about the parents at all.  This is because
4131          * we can use the last_unlink_trans field to record renames
4132          * and other fun in this file.
4133          */
4134         if (S_ISREG(inode->i_mode) &&
4135             BTRFS_I(inode)->generation <= last_committed &&
4136             BTRFS_I(inode)->last_unlink_trans <= last_committed) {
4137                 ret = 0;
4138                 goto end_trans;
4139         }
4140 
4141         inode_only = LOG_INODE_EXISTS;
4142         while (1) {
4143                 if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
4144                         break;
4145 
4146                 inode = parent->d_inode;
4147                 if (root != BTRFS_I(inode)->root)
4148                         break;
4149 
4150                 if (BTRFS_I(inode)->generation >
4151                     root->fs_info->last_trans_committed) {
4152                         ret = btrfs_log_inode(trans, root, inode, inode_only);
4153                         if (ret)
4154                                 goto end_trans;
4155                 }
4156                 if (IS_ROOT(parent))
4157                         break;
4158 
4159                 parent = dget_parent(parent);
4160                 dput(old_parent);
4161                 old_parent = parent;
4162         }
4163         ret = 0;
4164 end_trans:
4165         dput(old_parent);
4166         if (ret < 0) {
4167                 root->fs_info->last_trans_log_full_commit = trans->transid;
4168                 ret = 1;
4169         }
4170         btrfs_end_log_trans(root);
4171 end_no_trans:
4172         return ret;
4173 }
4174 
4175 /*
4176  * it is not safe to log dentry if the chunk root has added new
4177  * chunks.  This returns 0 if the dentry was logged, and 1 otherwise.
4178  * If this returns 1, you must commit the transaction to safely get your
4179  * data on disk.
4180  */
4181 int btrfs_log_dentry_safe(struct btrfs_trans_handle *trans,
4182                           struct btrfs_root *root, struct dentry *dentry)
4183 {
4184         struct dentry *parent = dget_parent(dentry);
4185         int ret;
4186 
4187         ret = btrfs_log_inode_parent(trans, root, dentry->d_inode, parent, 0);
4188         dput(parent);
4189 
4190         return ret;
4191 }
4192 
4193 /*
4194  * should be called during mount to recover any replay any log trees
4195  * from the FS
4196  */
4197 int btrfs_recover_log_trees(struct btrfs_root *log_root_tree)
4198 {
4199         int ret;
4200         struct btrfs_path *path;
4201         struct btrfs_trans_handle *trans;
4202         struct btrfs_key key;
4203         struct btrfs_key found_key;
4204         struct btrfs_key tmp_key;
4205         struct btrfs_root *log;
4206         struct btrfs_fs_info *fs_info = log_root_tree->fs_info;
4207         struct walk_control wc = {
4208                 .process_func = process_one_buffer,
4209                 .stage = 0,
4210         };
4211 
4212         path = btrfs_alloc_path();
4213         if (!path)
4214                 return -ENOMEM;
4215 
4216         fs_info->log_root_recovering = 1;
4217 
4218         trans = btrfs_start_transaction(fs_info->tree_root, 0);
4219         if (IS_ERR(trans)) {
4220                 ret = PTR_ERR(trans);
4221                 goto error;
4222         }
4223 
4224         wc.trans = trans;
4225         wc.pin = 1;
4226 
4227         ret = walk_log_tree(trans, log_root_tree, &wc);
4228         if (ret) {
4229                 btrfs_error(fs_info, ret, "Failed to pin buffers while "
4230                             "recovering log root tree.");
4231                 goto error;
4232         }
4233 
4234 again:
4235         key.objectid = BTRFS_TREE_LOG_OBJECTID;
4236         key.offset = (u64)-1;
4237         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
4238 
4239         while (1) {
4240                 ret = btrfs_search_slot(NULL, log_root_tree, &key, path, 0, 0);
4241 
4242                 if (ret < 0) {
4243                         btrfs_error(fs_info, ret,
4244                                     "Couldn't find tree log root.");
4245                         goto error;
4246                 }
4247                 if (ret > 0) {
4248                         if (path->slots[0] == 0)
4249                                 break;
4250                         path->slots[0]--;
4251                 }
4252                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
4253                                       path->slots[0]);
4254                 btrfs_release_path(path);
4255                 if (found_key.objectid != BTRFS_TREE_LOG_OBJECTID)
4256                         break;
4257 
4258                 log = btrfs_read_fs_root(log_root_tree, &found_key);
4259                 if (IS_ERR(log)) {
4260                         ret = PTR_ERR(log);
4261                         btrfs_error(fs_info, ret,
4262                                     "Couldn't read tree log root.");
4263                         goto error;
4264                 }
4265 
4266                 tmp_key.objectid = found_key.offset;
4267                 tmp_key.type = BTRFS_ROOT_ITEM_KEY;
4268                 tmp_key.offset = (u64)-1;
4269 
4270                 wc.replay_dest = btrfs_read_fs_root_no_name(fs_info, &tmp_key);
4271                 if (IS_ERR(wc.replay_dest)) {
4272                         ret = PTR_ERR(wc.replay_dest);
4273                         free_extent_buffer(log->node);
4274                         free_extent_buffer(log->commit_root);
4275                         kfree(log);
4276                         btrfs_error(fs_info, ret, "Couldn't read target root "
4277                                     "for tree log recovery.");
4278                         goto error;
4279                 }
4280 
4281                 wc.replay_dest->log_root = log;
4282                 btrfs_record_root_in_trans(trans, wc.replay_dest);
4283                 ret = walk_log_tree(trans, log, &wc);
4284 
4285                 if (!ret && wc.stage == LOG_WALK_REPLAY_ALL) {
4286                         ret = fixup_inode_link_counts(trans, wc.replay_dest,
4287                                                       path);
4288                 }
4289 
4290                 key.offset = found_key.offset - 1;
4291                 wc.replay_dest->log_root = NULL;
4292                 free_extent_buffer(log->node);
4293                 free_extent_buffer(log->commit_root);
4294                 kfree(log);
4295 
4296                 if (ret)
4297                         goto error;
4298 
4299                 if (found_key.offset == 0)
4300                         break;
4301         }
4302         btrfs_release_path(path);
4303 
4304         /* step one is to pin it all, step two is to replay just inodes */
4305         if (wc.pin) {
4306                 wc.pin = 0;
4307                 wc.process_func = replay_one_buffer;
4308                 wc.stage = LOG_WALK_REPLAY_INODES;
4309                 goto again;
4310         }
4311         /* step three is to replay everything */
4312         if (wc.stage < LOG_WALK_REPLAY_ALL) {
4313                 wc.stage++;
4314                 goto again;
4315         }
4316 
4317         btrfs_free_path(path);
4318 
4319         /* step 4: commit the transaction, which also unpins the blocks */
4320         ret = btrfs_commit_transaction(trans, fs_info->tree_root);
4321         if (ret)
4322                 return ret;
4323 
4324         free_extent_buffer(log_root_tree->node);
4325         log_root_tree->log_root = NULL;
4326         fs_info->log_root_recovering = 0;
4327         kfree(log_root_tree);
4328 
4329         return 0;
4330 error:
4331         if (wc.trans)
4332                 btrfs_end_transaction(wc.trans, fs_info->tree_root);
4333         btrfs_free_path(path);
4334         return ret;
4335 }
4336 
4337 /*
4338  * there are some corner cases where we want to force a full
4339  * commit instead of allowing a directory to be logged.
4340  *
4341  * They revolve around files there were unlinked from the directory, and
4342  * this function updates the parent directory so that a full commit is
4343  * properly done if it is fsync'd later after the unlinks are done.
4344  */
4345 void btrfs_record_unlink_dir(struct btrfs_trans_handle *trans,
4346                              struct inode *dir, struct inode *inode,
4347                              int for_rename)
4348 {
4349         /*
4350          * when we're logging a file, if it hasn't been renamed
4351          * or unlinked, and its inode is fully committed on disk,
4352          * we don't have to worry about walking up the directory chain
4353          * to log its parents.
4354          *
4355          * So, we use the last_unlink_trans field to put this transid
4356          * into the file.  When the file is logged we check it and
4357          * don't log the parents if the file is fully on disk.
4358          */
4359         if (S_ISREG(inode->i_mode))
4360                 BTRFS_I(inode)->last_unlink_trans = trans->transid;
4361 
4362         /*
4363          * if this directory was already logged any new
4364          * names for this file/dir will get recorded
4365          */
4366         smp_mb();
4367         if (BTRFS_I(dir)->logged_trans == trans->transid)
4368                 return;
4369 
4370         /*
4371          * if the inode we're about to unlink was logged,
4372          * the log will be properly updated for any new names
4373          */
4374         if (BTRFS_I(inode)->logged_trans == trans->transid)
4375                 return;
4376 
4377         /*
4378          * when renaming files across directories, if the directory
4379          * there we're unlinking from gets fsync'd later on, there's
4380          * no way to find the destination directory later and fsync it
4381          * properly.  So, we have to be conservative and force commits
4382          * so the new name gets discovered.
4383          */
4384         if (for_rename)
4385                 goto record;
4386 
4387         /* we can safely do the unlink without any special recording */
4388         return;
4389 
4390 record:
4391         BTRFS_I(dir)->last_unlink_trans = trans->transid;
4392 }
4393 
4394 /*
4395  * Call this after adding a new name for a file and it will properly
4396  * update the log to reflect the new name.
4397  *
4398  * It will return zero if all goes well, and it will return 1 if a
4399  * full transaction commit is required.
4400  */
4401 int btrfs_log_new_name(struct btrfs_trans_handle *trans,
4402                         struct inode *inode, struct inode *old_dir,
4403                         struct dentry *parent)
4404 {
4405         struct btrfs_root * root = BTRFS_I(inode)->root;
4406 
4407         /*
4408          * this will force the logging code to walk the dentry chain
4409          * up for the file
4410          */
4411         if (S_ISREG(inode->i_mode))
4412                 BTRFS_I(inode)->last_unlink_trans = trans->transid;
4413 
4414         /*
4415          * if this inode hasn't been logged and directory we're renaming it
4416          * from hasn't been logged, we don't need to log it
4417          */
4418         if (BTRFS_I(inode)->logged_trans <=
4419             root->fs_info->last_trans_committed &&
4420             (!old_dir || BTRFS_I(old_dir)->logged_trans <=
4421                     root->fs_info->last_trans_committed))
4422                 return 0;
4423 
4424         return btrfs_log_inode_parent(trans, root, inode, parent, 1);
4425 }
4426 
4427 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp