)]}'
{
  "log": [
    {
      "commit": "95a06077f7edbd00d32612562be4d857a5b7df54",
      "tree": "664ff2a92a2de3ba96be5a49ac36531d933ee5eb",
      "parents": [
        "20b297d620cd1bb94127942bbb3702fb7b1030b2"
      ],
      "author": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Tue May 29 17:06:54 2012 +0200"
      },
      "committer": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Wed May 30 18:18:21 2012 +0200"
      },
      "message": "Btrfs: use delayed ref sequence numbers for all fs-tree updates\n\nThe sequence number for delayed refs is needed to postpone certain delayed\nrefs for a very short period while walking backrefs. Before the tree\nmodification log, we thought we\u0027d only have to hold back those references\nthat don\u0027t have a counter operation.\n\nWhile now we\u0027ve the tree mod log, we\u0027re rewinding fs tree blocks to a\ndefined consistent state. We cannot know in advance for which tree block\nwe\u0027ll be doing rewind operations later. Therefore, we must postpone all the\ndelayed refs for fs-tree blocks, even those having a counter operation.\n\nSigned-off-by: Jan Schmidt \u003clist.btrfs@jan-o-sch.net\u003e\n"
    },
    {
      "commit": "143bede527b054a271053f41bfaca2b57baa9408",
      "tree": "95c71d3705c73bf98e7a1547da35e70a44703c1e",
      "parents": [
        "ffd7b33944f4573a063af7a55f8a5199c8185665"
      ],
      "author": {
        "name": "Jeff Mahoney",
        "email": "jeffm@suse.com",
        "time": "Thu Mar 01 14:56:26 2012 +0100"
      },
      "committer": {
        "name": "David Sterba",
        "email": "dsterba@suse.cz",
        "time": "Thu Mar 22 01:45:34 2012 +0100"
      },
      "message": "btrfs: return void in functions without error conditions\n\nSigned-off-by: Jeff Mahoney \u003cjeffm@suse.com\u003e\n"
    },
    {
      "commit": "cddcd800189bc03745d576f913dc57692c6f439a",
      "tree": "361ed5f8c26a9820608de6d0a74f546729c90970",
      "parents": [
        "43c04fb1b8c9f45d971bb53d7cbbcda8ee85716b"
      ],
      "author": {
        "name": "Jeff Mahoney",
        "email": "jeffm@suse.com",
        "time": "Mon Oct 03 23:23:23 2011 -0400"
      },
      "committer": {
        "name": "David Sterba",
        "email": "dsterba@suse.cz",
        "time": "Thu Mar 22 01:45:30 2012 +0100"
      },
      "message": "btrfs: Fix kfree of member instead of structure\n\nCorrectness fix: The kfree calls in the add_delayed_* functions free\nthe node that\u0027s passed into it, but the node is a member of another\nstructure. It works because it\u0027s always the first member of the\ncontaining structure, but it should really be using the containing\nstructure itself.\n\nSigned-off-by: Jeff Mahoney \u003cjeffm@suse.com\u003e\n"
    },
    {
      "commit": "a168650c08300434e1456abe7b6451f1448230d3",
      "tree": "addddb060b018eb569e97c11e1a1451feef11c7a",
      "parents": [
        "d1270cd91f308c9d22b2804720c36ccd32dbc35e"
      ],
      "author": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Mon Dec 12 16:10:07 2011 +0100"
      },
      "committer": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Wed Jan 04 16:12:48 2012 +0100"
      },
      "message": "Btrfs: add waitqueue instead of doing busy waiting for more delayed refs\n\nNow that we may be holding back delayed refs for a limited period, we\nmight end up having no runnable delayed refs. Without this commit, we\u0027d\ndo busy waiting in that thread until another (runnable) ref arives.\nInstead, we\u0027re detecting this situation and use a waitqueue, such that\nwe only try to run more refs after\n\ta) another runnable ref was added  or\n\tb) delayed refs are no longer held back\n\nSigned-off-by: Jan Schmidt \u003clist.btrfs@jan-o-sch.net\u003e\n"
    },
    {
      "commit": "d1270cd91f308c9d22b2804720c36ccd32dbc35e",
      "tree": "3dfa3109f7df9983ce88dad5bcb4515f7d4b26b5",
      "parents": [
        "00f04b88791ff49dc64ada18819d40a5b0671709"
      ],
      "author": {
        "name": "Arne Jansen",
        "email": "sensille@gmx.net",
        "time": "Tue Sep 13 15:16:43 2011 +0200"
      },
      "committer": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Wed Jan 04 16:12:45 2012 +0100"
      },
      "message": "Btrfs: put back delayed refs that are too new\n\nWhen processing a delayed ref, first check if there are still old refs in\nthe process of being added. If so, put this ref back to the tree. To avoid\nlooping on this ref, choose a newer one in the next loop.\nbtrfs_find_ref_cluster has to take care of that.\n\nSigned-off-by: Arne Jansen \u003csensille@gmx.net\u003e\nSigned-off-by: Jan Schmidt \u003clist.btrfs@jan-o-sch.net\u003e\n"
    },
    {
      "commit": "00f04b88791ff49dc64ada18819d40a5b0671709",
      "tree": "fd85a5f4b374aac035388b0cbf8ef572578d5578",
      "parents": [
        "5b25f70f4200766355cdabda604e131d2fb6010d"
      ],
      "author": {
        "name": "Arne Jansen",
        "email": "sensille@gmx.net",
        "time": "Wed Sep 14 12:37:00 2011 +0200"
      },
      "committer": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Wed Jan 04 16:12:42 2012 +0100"
      },
      "message": "Btrfs: add sequence numbers to delayed refs\n\nSequence numbers are needed to reconstruct the backrefs of a given extent to\na certain point in time. The total set of backrefs consist of the set of\nbackrefs recorded on disk plus the enqueued delayed refs for it that existed\nat that moment.\n\nThis patch also adds a list that records all delayed refs which are\ncurrently in the process of being added.\n\nWhen walking all refs of an extent in btrfs_find_all_roots(), we freeze the\ncurrent state of delayed refs, honor anythinh up to this point and prevent\nprocessing newer delayed refs to assert consistency.\n\nSigned-off-by: Arne Jansen \u003csensille@gmx.net\u003e\nSigned-off-by: Jan Schmidt \u003clist.btrfs@jan-o-sch.net\u003e\n"
    },
    {
      "commit": "eebe063b7f916087cd5c61de57b20a3a30894a96",
      "tree": "d49c4a91abd9bef6f2fd546715f719c66ae1fd90",
      "parents": [
        "66d7e7f09f77456fe68683247d77721032a00ee5"
      ],
      "author": {
        "name": "Arne Jansen",
        "email": "sensille@gmx.net",
        "time": "Wed Sep 14 14:01:24 2011 +0200"
      },
      "committer": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Thu Dec 22 16:22:28 2011 +0100"
      },
      "message": "Btrfs: always save ref_root in delayed refs\n\nFor consistent backref walking and (later) qgroup calculation the\ninformation to which root a delayed ref belongs is useful even for shared\nrefs.\n\nSigned-off-by: Arne Jansen \u003csensille@gmx.net\u003e\nSigned-off-by: Jan Schmidt \u003clist.btrfs@jan-o-sch.net\u003e\n"
    },
    {
      "commit": "66d7e7f09f77456fe68683247d77721032a00ee5",
      "tree": "bbf7df3933ed47aa202d60d835864543d25df82d",
      "parents": [
        "c7d22a3c3cdb73d8a0151e2ccc8cf4a48c48310b"
      ],
      "author": {
        "name": "Arne Jansen",
        "email": "sensille@gmx.net",
        "time": "Mon Sep 12 15:26:38 2011 +0200"
      },
      "committer": {
        "name": "Jan Schmidt",
        "email": "list.btrfs@jan-o-sch.net",
        "time": "Thu Dec 22 16:22:27 2011 +0100"
      },
      "message": "Btrfs: mark delayed refs as for cow\n\nAdd a for_cow parameter to add_delayed_*_ref and pass the appropriate value\nfrom every call site. The for_cow parameter will later on be used to\ndetermine if a ref will change anything with respect to qgroups.\n\nDelayed refs coming from relocation are always counted as for_cow, as they\ndon\u0027t change subvol quota.\n\nAlso pass in the fs_info for later use.\n\nbtrfs_find_all_roots() will use this as an optimization, as changes that are\nfor_cow will not change anything with respect to which root points to a\ncertain leaf. Thus, we don\u0027t need to add the current sequence number to\nthose delayed refs.\n\nSigned-off-by: Arne Jansen \u003csensille@gmx.net\u003e\nSigned-off-by: Jan Schmidt \u003clist.btrfs@jan-o-sch.net\u003e\n"
    },
    {
      "commit": "182608c8294b5fe90d7bbd4b026c82bf0a24b736",
      "tree": "5705e84960e66caa84ac059a3528a31493e35d16",
      "parents": [
        "f2a97a9dbd86eb1ef956bdf20e05c507b32beb96"
      ],
      "author": {
        "name": "David Sterba",
        "email": "dsterba@suse.cz",
        "time": "Thu May 05 13:13:16 2011 +0200"
      },
      "committer": {
        "name": "David Sterba",
        "email": "dsterba@suse.cz",
        "time": "Fri May 06 12:34:10 2011 +0200"
      },
      "message": "btrfs: remove old unused commented out code\n\nRemove code which has been #if0-ed out for a very long time and does not\nseem to be related to current codebase anymore.\n\nSigned-off-by: David Sterba \u003cdsterba@suse.cz\u003e\n"
    },
    {
      "commit": "f2a97a9dbd86eb1ef956bdf20e05c507b32beb96",
      "tree": "756c2db8fee9c02df0e3217ea208a82b5f1d5e78",
      "parents": [
        "621496f4fd56195b7b273521f467c2945165481f"
      ],
      "author": {
        "name": "David Sterba",
        "email": "dsterba@suse.cz",
        "time": "Thu May 05 12:44:41 2011 +0200"
      },
      "committer": {
        "name": "David Sterba",
        "email": "dsterba@suse.cz",
        "time": "Fri May 06 12:34:03 2011 +0200"
      },
      "message": "btrfs: remove all unused functions\n\nRemove static and global declarations and/or definitions. Reduces size\nof btrfs.ko by ~3.4kB.\n\n  text    data     bss     dec     hex filename\n402081    7464     200  409745   64091 btrfs.ko.base\n398620    7144     200  405964   631cc btrfs.ko.remove-all\n\nSigned-off-by: David Sterba \u003cdsterba@suse.cz\u003e\n"
    },
    {
      "commit": "1abe9b8a138c9988ba8f7bfded6453649a31541f",
      "tree": "9fe0c181e78b075b65f6b1802f0a5092e7afbc6a",
      "parents": [
        "240f62c8756df285da11469259b3900f32883168"
      ],
      "author": {
        "name": "liubo",
        "email": "liubo2009@cn.fujitsu.com",
        "time": "Thu Mar 24 11:18:59 2011 +0000"
      },
      "committer": {
        "name": "root",
        "email": "Chris Mason chris.mason@oracle.com",
        "time": "Mon Mar 28 05:37:33 2011 -0400"
      },
      "message": "Btrfs: add initial tracepoint support for btrfs\n\nTracepoints can provide insight into why btrfs hits bugs and be greatly\nhelpful for debugging, e.g\n              dd-7822  [000]  2121.641088: btrfs_inode_request: root \u003d 5(FS_TREE), gen \u003d 4, ino \u003d 256, blocks \u003d 8, disk_i_size \u003d 0, last_trans \u003d 8, logged_trans \u003d 0\n              dd-7822  [000]  2121.641100: btrfs_inode_new: root \u003d 5(FS_TREE), gen \u003d 8, ino \u003d 257, blocks \u003d 0, disk_i_size \u003d 0, last_trans \u003d 0, logged_trans \u003d 0\n btrfs-transacti-7804  [001]  2146.935420: btrfs_cow_block: root \u003d 2(EXTENT_TREE), refs \u003d 2, orig_buf \u003d 29368320 (orig_level \u003d 0), cow_buf \u003d 29388800 (cow_level \u003d 0)\n btrfs-transacti-7804  [001]  2146.935473: btrfs_cow_block: root \u003d 1(ROOT_TREE), refs \u003d 2, orig_buf \u003d 29364224 (orig_level \u003d 0), cow_buf \u003d 29392896 (cow_level \u003d 0)\n btrfs-transacti-7804  [001]  2146.972221: btrfs_transaction_commit: root \u003d 1(ROOT_TREE), gen \u003d 8\n   flush-btrfs-2-7821  [001]  2155.824210: btrfs_chunk_alloc: root \u003d 3(CHUNK_TREE), offset \u003d 1103101952, size \u003d 1073741824, num_stripes \u003d 1, sub_stripes \u003d 0, type \u003d DATA\n   flush-btrfs-2-7821  [001]  2155.824241: btrfs_cow_block: root \u003d 2(EXTENT_TREE), refs \u003d 2, orig_buf \u003d 29388800 (orig_level \u003d 0), cow_buf \u003d 29396992 (cow_level \u003d 0)\n   flush-btrfs-2-7821  [001]  2155.824255: btrfs_cow_block: root \u003d 4(DEV_TREE), refs \u003d 2, orig_buf \u003d 29372416 (orig_level \u003d 0), cow_buf \u003d 29401088 (cow_level \u003d 0)\n   flush-btrfs-2-7821  [000]  2155.824329: btrfs_cow_block: root \u003d 3(CHUNK_TREE), refs \u003d 2, orig_buf \u003d 20971520 (orig_level \u003d 0), cow_buf \u003d 20975616 (cow_level \u003d 0)\n btrfs-endio-wri-7800  [001]  2155.898019: btrfs_cow_block: root \u003d 5(FS_TREE), refs \u003d 2, orig_buf \u003d 29384704 (orig_level \u003d 0), cow_buf \u003d 29405184 (cow_level \u003d 0)\n btrfs-endio-wri-7800  [001]  2155.898043: btrfs_cow_block: root \u003d 7(CSUM_TREE), refs \u003d 2, orig_buf \u003d 29376512 (orig_level \u003d 0), cow_buf \u003d 29409280 (cow_level \u003d 0)\n\nHere is what I have added:\n\n1) ordere_extent:\n        btrfs_ordered_extent_add\n        btrfs_ordered_extent_remove\n        btrfs_ordered_extent_start\n        btrfs_ordered_extent_put\n\nThese provide critical information to understand how ordered_extents are\nupdated.\n\n2) extent_map:\n        btrfs_get_extent\n\nextent_map is used in both read and write cases, and it is useful for tracking\nhow btrfs specific IO is running.\n\n3) writepage:\n        __extent_writepage\n        btrfs_writepage_end_io_hook\n\nPages are cirtical resourses and produce a lot of corner cases during writeback,\nso it is valuable to know how page is written to disk.\n\n4) inode:\n        btrfs_inode_new\n        btrfs_inode_request\n        btrfs_inode_evict\n\nThese can show where and when a inode is created, when a inode is evicted.\n\n5) sync:\n        btrfs_sync_file\n        btrfs_sync_fs\n\nThese show sync arguments.\n\n6) transaction:\n        btrfs_transaction_commit\n\nIn transaction based filesystem, it will be useful to know the generation and\nwho does commit.\n\n7) back reference and cow:\n\tbtrfs_delayed_tree_ref\n\tbtrfs_delayed_data_ref\n\tbtrfs_delayed_ref_head\n\tbtrfs_cow_block\n\nBtrfs natively supports back references, these tracepoints are helpful on\nunderstanding btrfs\u0027s COW mechanism.\n\n8) chunk:\n\tbtrfs_chunk_alloc\n\tbtrfs_chunk_free\n\nChunk is a link between physical offset and logical offset, and stands for space\ninfomation in btrfs, and these are helpful on tracing space things.\n\n9) reserved_extent:\n\tbtrfs_reserved_extent_alloc\n\tbtrfs_reserved_extent_free\n\nThese can show how btrfs uses its space.\n\nSigned-off-by: Liu Bo \u003cliubo2009@cn.fujitsu.com\u003e\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    },
    {
      "commit": "a22285a6a32390195235171b89d157ed1a1fe932",
      "tree": "3fabc88a029e1af4f2fdcc708e7b62ef3cf3703a",
      "parents": [
        "f0486c68e4bd9a06a5904d3eeb3a0d73a83befb8"
      ],
      "author": {
        "name": "Yan, Zheng",
        "email": "zheng.yan@oracle.com",
        "time": "Sun May 16 10:48:46 2010 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Tue May 25 10:34:50 2010 -0400"
      },
      "message": "Btrfs: Integrate metadata reservation with start_transaction\n\nBesides simplify the code, this change makes sure all metadata\nreservation for normal metadata operations are released after\ncommitting transaction.\n\nChanges since V1:\n\nAdd code that check if unlink and rmdir will free space.\n\nAdd ENOSPC handling for clone ioctl.\n\nSigned-off-by: Yan Zheng \u003czheng.yan@oracle.com\u003e\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    },
    {
      "commit": "5a0e3ad6af8660be21ca98a971cd00f331318c05",
      "tree": "5bfb7be11a03176a87296a43ac6647975c00a1d1",
      "parents": [
        "ed391f4ebf8f701d3566423ce8f17e614cde9806"
      ],
      "author": {
        "name": "Tejun Heo",
        "email": "tj@kernel.org",
        "time": "Wed Mar 24 17:04:11 2010 +0900"
      },
      "committer": {
        "name": "Tejun Heo",
        "email": "tj@kernel.org",
        "time": "Tue Mar 30 22:02:32 2010 +0900"
      },
      "message": "include cleanup: Update gfp.h and slab.h includes to prepare for breaking implicit slab.h inclusion from percpu.h\n\npercpu.h is included by sched.h and module.h and thus ends up being\nincluded when building most .c files.  percpu.h includes slab.h which\nin turn includes gfp.h making everything defined by the two files\nuniversally available and complicating inclusion dependencies.\n\npercpu.h -\u003e slab.h dependency is about to be removed.  Prepare for\nthis change by updating users of gfp and slab facilities include those\nheaders directly instead of assuming availability.  As this conversion\nneeds to touch large number of source files, the following script is\nused as the basis of conversion.\n\n  http://userweb.kernel.org/~tj/misc/slabh-sweep.py\n\nThe script does the followings.\n\n* Scan files for gfp and slab usages and update includes such that\n  only the necessary includes are there.  ie. if only gfp is used,\n  gfp.h, if slab is used, slab.h.\n\n* When the script inserts a new include, it looks at the include\n  blocks and try to put the new include such that its order conforms\n  to its surrounding.  It\u0027s put in the include block which contains\n  core kernel includes, in the same order that the rest are ordered -\n  alphabetical, Christmas tree, rev-Xmas-tree or at the end if there\n  doesn\u0027t seem to be any matching order.\n\n* If the script can\u0027t find a place to put a new include (mostly\n  because the file doesn\u0027t have fitting include block), it prints out\n  an error message indicating which .h file needs to be added to the\n  file.\n\nThe conversion was done in the following steps.\n\n1. The initial automatic conversion of all .c files updated slightly\n   over 4000 files, deleting around 700 includes and adding ~480 gfp.h\n   and ~3000 slab.h inclusions.  The script emitted errors for ~400\n   files.\n\n2. Each error was manually checked.  Some didn\u0027t need the inclusion,\n   some needed manual addition while adding it to implementation .h or\n   embedding .c file was more appropriate for others.  This step added\n   inclusions to around 150 files.\n\n3. The script was run again and the output was compared to the edits\n   from #2 to make sure no file was left behind.\n\n4. Several build tests were done and a couple of problems were fixed.\n   e.g. lib/decompress_*.c used malloc/free() wrappers around slab\n   APIs requiring slab.h to be added manually.\n\n5. The script was run on all .h files but without automatically\n   editing them as sprinkling gfp.h and slab.h inclusions around .h\n   files could easily lead to inclusion dependency hell.  Most gfp.h\n   inclusion directives were ignored as stuff from gfp.h was usually\n   wildly available and often used in preprocessor macros.  Each\n   slab.h inclusion directive was examined and added manually as\n   necessary.\n\n6. percpu.h was updated not to include slab.h.\n\n7. Build test were done on the following configurations and failures\n   were fixed.  CONFIG_GCOV_KERNEL was turned off for all tests (as my\n   distributed build env didn\u0027t work with gcov compiles) and a few\n   more options had to be turned off depending on archs to make things\n   build (like ipr on powerpc/64 which failed due to missing writeq).\n\n   * x86 and x86_64 UP and SMP allmodconfig and a custom test config.\n   * powerpc and powerpc64 SMP allmodconfig\n   * sparc and sparc64 SMP allmodconfig\n   * ia64 SMP allmodconfig\n   * s390 SMP allmodconfig\n   * alpha SMP allmodconfig\n   * um on x86_64 SMP allmodconfig\n\n8. percpu.h modifications were reverted so that it could be applied as\n   a separate patch and serve as bisection point.\n\nGiven the fact that I had only a couple of failures from tests on step\n6, I\u0027m fairly confident about the coverage of this conversion patch.\nIf there is a breakage, it\u0027s likely to be something in one of the arch\nheaders which should be easily discoverable easily on most builds of\nthe specific arch.\n\nSigned-off-by: Tejun Heo \u003ctj@kernel.org\u003e\nGuess-its-ok-by: Christoph Lameter \u003ccl@linux-foundation.org\u003e\nCc: Ingo Molnar \u003cmingo@redhat.com\u003e\nCc: Lee Schermerhorn \u003cLee.Schermerhorn@hp.com\u003e\n"
    },
    {
      "commit": "5d4f98a28c7d334091c1b7744f48a1acdd2a4ae0",
      "tree": "c611d7d824cbcdb777dd2d8e33e2ed1c5df8a9c6",
      "parents": [
        "5c939df56c3ea018b58e5aa76181284c2053d699"
      ],
      "author": {
        "name": "Yan Zheng",
        "email": "zheng.yan@oracle.com",
        "time": "Wed Jun 10 10:45:14 2009 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Wed Jun 10 11:29:46 2009 -0400"
      },
      "message": "Btrfs: Mixed back reference  (FORWARD ROLLING FORMAT CHANGE)\n\nThis commit introduces a new kind of back reference for btrfs metadata.\nOnce a filesystem has been mounted with this commit, IT WILL NO LONGER\nBE MOUNTABLE BY OLDER KERNELS.\n\nWhen a tree block in subvolume tree is cow\u0027d, the reference counts of all\nextents it points to are increased by one.  At transaction commit time,\nthe old root of the subvolume is recorded in a \"dead root\" data structure,\nand the btree it points to is later walked, dropping reference counts\nand freeing any blocks where the reference count goes to 0.\n\nThe increments done during cow and decrements done after commit cancel out,\nand the walk is a very expensive way to go about freeing the blocks that\nare no longer referenced by the new btree root.  This commit reduces the\ntransaction overhead by avoiding the need for dead root records.\n\nWhen a non-shared tree block is cow\u0027d, we free the old block at once, and the\nnew block inherits old block\u0027s references. When a tree block with reference\ncount \u003e 1 is cow\u0027d, we increase the reference counts of all extents\nthe new block points to by one, and decrease the old block\u0027s reference count by\none.\n\nThis dead tree avoidance code removes the need to modify the reference\ncounts of lower level extents when a non-shared tree block is cow\u0027d.\nBut we still need to update back ref for all pointers in the block.\nThis is because the location of the block is recorded in the back ref\nitem.\n\nWe can solve this by introducing a new type of back ref. The new\nback ref provides information about pointer\u0027s key, level and in which\ntree the pointer lives. This information allow us to find the pointer\nby searching the tree. The shortcoming of the new back ref is that it\nonly works for pointers in tree blocks referenced by their owner trees.\n\nThis is mostly a problem for snapshots, where resolving one of these\nfuzzy back references would be O(number_of_snapshots) and quite slow.\nThe solution used here is to use the fuzzy back references in the common\ncase where a given tree block is only referenced by one root,\nand use the full back references when multiple roots have a reference\non a given block.\n\nThis commit adds per subvolume red-black tree to keep trace of cached\ninodes. The red-black tree helps the balancing code to find cached\ninodes whose inode numbers within a given range.\n\nThis commit improves the balancing code by introducing several data\nstructures to keep the state of balancing. The most important one\nis the back ref cache. It caches how the upper level tree blocks are\nreferenced. This greatly reduce the overhead of checking back ref.\n\nThe improved balancing code scales significantly better with a large\nnumber of snapshots.\n\nThis is a very large commit and was written in a number of\npieces.  But, they depend heavily on the disk format change and were\nsquashed together to make sure git bisect didn\u0027t end up in a\nbad state wrt space balancing or the format change.\n\nSigned-off-by: Yan Zheng \u003czheng.yan@oracle.com\u003e\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    },
    {
      "commit": "2e966ed22c3c56227f8a7322d7b008945352e6ab",
      "tree": "101bb798295de6a299d7f6febd437887134f5e43",
      "parents": [
        "93dbfad7ac647d4f00354893fe93e8a55be114d5"
      ],
      "author": {
        "name": "Jim Owens",
        "email": "jowens@hp.com",
        "time": "Thu Apr 02 17:02:55 2009 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Thu Apr 02 17:02:55 2009 -0400"
      },
      "message": "Btrfs: remove unused ftrace include\n\nSigned-off-by: jim owens \u003cjowens@hp.com\u003e\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n\n"
    },
    {
      "commit": "1a81af4d1d9c60d4313309f937a1fc5567205a87",
      "tree": "535b65b3948d34f0948613afc6ebdfe693683f33",
      "parents": [
        "af4176b49c5ee15a9c9b10720c92456b28e7aac7"
      ],
      "author": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Wed Mar 25 09:55:11 2009 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Wed Mar 25 09:55:11 2009 -0400"
      },
      "message": "Btrfs: make sure btrfs_update_delayed_ref doesn\u0027t increase ref_mod\n\nbtrfs_update_delayed_ref is optimized to add and remove different\nreferences in one pass through the delayed ref tree.  It is a zero\nsum on the total number of refs on a given extent.\n\nBut, the code was recording an extra ref in the head node.  This\nnever made it down to the disk but was used when deciding if it was\nsafe to free the extent while dropping snapshots.\n\nThe fix used here is to make sure the ref_mod count is unchanged\non the head ref when btrfs_update_delayed_ref is called.\n\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    },
    {
      "commit": "c3e69d58e86c3917ae4e9e31b4acf490a7cafe60",
      "tree": "bd4f1e62446a208bdae26f0c36d67e3afbc1cd1d",
      "parents": [
        "1887be66dcc3140a81d1299958a41fc0eedfa64f"
      ],
      "author": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Fri Mar 13 10:17:05 2009 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Tue Mar 24 16:14:26 2009 -0400"
      },
      "message": "Btrfs: process the delayed reference queue in clusters\n\nThe delayed reference queue maintains pending operations that need to\nbe done to the extent allocation tree.  These are processed by\nfinding records in the tree that are not currently being processed one at\na time.\n\nThis is slow because it uses lots of time searching through the rbtree\nand because it creates lock contention on the extent allocation tree\nwhen lots of different procs are running delayed refs at the same time.\n\nThis commit changes things to grab a cluster of refs for processing,\nusing a cursor into the rbtree as the starting point of the next search.\nThis way we walk smoothly through the rbtree.\n\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    },
    {
      "commit": "1887be66dcc3140a81d1299958a41fc0eedfa64f",
      "tree": "3f0666948a83c48c77e0c37dca1c71a6aff9eb1d",
      "parents": [
        "44871b1b24b593996db43495cf4484cc580bdc10"
      ],
      "author": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Fri Mar 13 10:11:24 2009 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Tue Mar 24 16:14:26 2009 -0400"
      },
      "message": "Btrfs: try to cleanup delayed refs while freeing extents\n\nWhen extents are freed, it is likely that we\u0027ve removed the last\ndelayed reference update for the extent.  This checks the delayed\nref tree when things are freed, and if no ref updates area left it\nimmediately processes the delayed ref.\n\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    },
    {
      "commit": "56bec294dea971335d4466b30f2d959f28f6e36d",
      "tree": "fc0b5bbf4bb6ab35582a4c7f58f5ac88f71c38bf",
      "parents": [
        "9fa8cfe706f9c20067c042a064999d5825a35330"
      ],
      "author": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Fri Mar 13 10:10:06 2009 -0400"
      },
      "committer": {
        "name": "Chris Mason",
        "email": "chris.mason@oracle.com",
        "time": "Tue Mar 24 16:14:25 2009 -0400"
      },
      "message": "Btrfs: do extent allocation and reference count updates in the background\n\nThe extent allocation tree maintains a reference count and full\nback reference information for every extent allocated in the\nfilesystem.  For subvolume and snapshot trees, every time\na block goes through COW, the new copy of the block adds a reference\non every block it points to.\n\nIf a btree node points to 150 leaves, then the COW code needs to go\nand add backrefs on 150 different extents, which might be spread all\nover the extent allocation tree.\n\nThese updates currently happen during btrfs_cow_block, and most COWs\nhappen during btrfs_search_slot.  btrfs_search_slot has locks held\non both the parent and the node we are COWing, and so we really want\nto avoid IO during the COW if we can.\n\nThis commit adds an rbtree of pending reference count updates and extent\nallocations.  The tree is ordered by byte number of the extent and byte number\nof the parent for the back reference.  The tree allows us to:\n\n1) Modify back references in something close to disk order, reducing seeks\n2) Significantly reduce the number of modifications made as block pointers\nare balanced around\n3) Do all of the extent insertion and back reference modifications outside\nof the performance critical btrfs_search_slot code.\n\n#3 has the added benefit of greatly reducing the btrfs stack footprint.\nThe extent allocation tree modifications are done without the deep\n(and somewhat recursive) call chains used in the past.\n\nThese delayed back reference updates must be done before the transaction\ncommits, and so the rbtree is tied to the transaction.  Throttling is\nimplemented to help keep the queue of backrefs at a reasonable size.\n\nSince there was a similar mechanism in place for the extent tree\nextents, that is removed and replaced by the delayed reference tree.\n\nYan Zheng \u003cyan.zheng@oracle.com\u003e helped review and fixup this code.\n\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n"
    }
  ]
}