)]}'
{
  "commit": "ed3b4d6cdc81e8feefdbfa3c584614be301b6d39",
  "tree": "5b8cd5735dfbc5eb834f96d25a8eb587186715be",
  "parents": [
    "955833cf2ad0aa39b336e853cad212d867199984"
  ],
  "author": {
    "name": "Dave Chinner",
    "email": "david@fromorbit.com",
    "time": "Fri May 21 12:07:08 2010 +1000"
  },
  "committer": {
    "name": "Alex Elder",
    "email": "aelder@sgi.com",
    "time": "Mon May 24 10:34:00 2010 -0500"
  },
  "message": "xfs: Improve scalability of busy extent tracking\n\nWhen we free a metadata extent, we record it in the per-AG busy\nextent array so that it is not re-used before the freeing\ntransaction hits the disk. This array is fixed size, so when it\noverflows we make further allocation transactions synchronous\nbecause we cannot track more freed extents until those transactions\nhit the disk and are completed. Under heavy mixed allocation and\nfreeing workloads with large log buffers, we can overflow this array\nquite easily.\n\nFurther, the array is sparsely populated, which means that inserts\nneed to search for a free slot, and array searches often have to\nsearch many more slots that are actually used to check all the\nbusy extents. Quite inefficient, really.\n\nTo enable this aspect of extent freeing to scale better, we need\na structure that can grow dynamically. While in other areas of\nXFS we have used radix trees, the extents being freed are at random\nlocations on disk so are better suited to being indexed by an rbtree.\n\nSo, use a per-AG rbtree indexed by block number to track busy\nextents.  This incures a memory allocation when marking an extent\nbusy, but should not occur too often in low memory situations. This\nshould scale to an arbitrary number of extents so should not be a\nlimitation for features such as in-memory aggregation of\ntransactions.\n\nHowever, there are still situations where we can\u0027t avoid allocating\nbusy extents (such as allocation from the AGFL). To minimise the\noverhead of such occurences, we need to avoid doing a synchronous\nlog force while holding the AGF locked to ensure that the previous\ntransactions are safely on disk before we use the extent. We can do\nthis by marking the transaction doing the allocation as synchronous\nrather issuing a log force.\n\nBecause of the locking involved and the ordering of transactions,\nthe synchronous transaction provides the same guarantees as a\nsynchronous log force because it ensures that all the prior\ntransactions are already on disk when the synchronous transaction\nhits the disk. i.e. it preserves the free-\u003eallocate order of the\nextent correctly in recovery.\n\nBy doing this, we avoid holding the AGF locked while log writes are\nin progress, hence reducing the length of time the lock is held and\ntherefore we increase the rate at which we can allocate and free\nfrom the allocation group, thereby increasing overall throughput.\n\nThe only problem with this approach is that when a metadata buffer is\nmarked stale (e.g. a directory block is removed), then buffer remains\npinned and locked until the log goes to disk. The issue here is that\nif that stale buffer is reallocated in a subsequent transaction, the\nattempt to lock that buffer in the transaction will hang waiting\nthe log to go to disk to unlock and unpin the buffer. Hence if\nsomeone tries to lock a pinned, stale, locked buffer we need to\npush on the log to get it unlocked ASAP. Effectively we are trading\noff a guaranteed log force for a much less common trigger for log\nforce to occur.\n\nIdeally we should not reallocate busy extents. That is a much more\ncomplex fix to the problem as it involves direct intervention in the\nallocation btree searches in many places. This is left to a future\nset of modifications.\n\nFinally, now that we track busy extents in allocated memory, we\ndon\u0027t need the descriptors in the transaction structure to point to\nthem. We can replace the complex busy chunk infrastructure with a\nsimple linked list of busy extents. This allows us to remove a large\nchunk of code, making the overall change a net reduction in code\nsize.\n\nSigned-off-by: Dave Chinner \u003cdavid@fromorbit.com\u003e\nReviewed-by: Christoph Hellwig \u003chch@lst.de\u003e\nSigned-off-by: Alex Elder \u003caelder@sgi.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "f01de3c55c43e8ed7effa08d8b5a324e18c4bd2a",
      "old_mode": 33188,
      "old_path": "fs/xfs/linux-2.6/xfs_buf.c",
      "new_id": "649ade8ef598693e2e57ac66475c1993b57903e3",
      "new_mode": 33188,
      "new_path": "fs/xfs/linux-2.6/xfs_buf.c"
    },
    {
      "type": "modify",
      "old_id": "1947514ce1ad05722ec4ebea43219fe64f68037f",
      "old_mode": 33188,
      "old_path": "fs/xfs/linux-2.6/xfs_quotaops.c",
      "new_id": "2e73688dae9ca9e32b28bc76ded329ad857d703c",
      "new_mode": 33188,
      "new_path": "fs/xfs/linux-2.6/xfs_quotaops.c"
    },
    {
      "type": "modify",
      "old_id": "8a319cfd290120d6e5b874b1f2cce4dea9de9809",
      "old_mode": 33188,
      "old_path": "fs/xfs/linux-2.6/xfs_trace.h",
      "new_id": "ff6bc797baf290a03ee411a05c8733ecb4ed030c",
      "new_mode": 33188,
      "new_path": "fs/xfs/linux-2.6/xfs_trace.h"
    },
    {
      "type": "modify",
      "old_id": "abb8222b88c9a06e90c00784a60564170ba253da",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_ag.h",
      "new_id": "401f364ad36ce52022cabf6ccafa9d58de39dcd2",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_ag.h"
    },
    {
      "type": "modify",
      "old_id": "94cddbfb25604abed1495b488799b13e10bbead0",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_alloc.c",
      "new_id": "a7fbe8a99b12bf2c360ea19372a380ae5d27c855",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_alloc.c"
    },
    {
      "type": "modify",
      "old_id": "599bffa39784d4f425304036d152072115f77b26",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_alloc.h",
      "new_id": "6d05199b667cea3c72576750924a8ee8a63effcc",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_alloc.h"
    },
    {
      "type": "modify",
      "old_id": "b726e10d2c1c18bafa355663d822f8b9ef441d67",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_alloc_btree.c",
      "new_id": "83f4942187594ac4b998712dc66b2385b083963e",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_alloc_btree.c"
    },
    {
      "type": "modify",
      "old_id": "be578ecb4af2d756dc09538f5cc955df019ef70f",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_trans.c",
      "new_id": "40d9595a8de2ed28df29632a4d3f68ecd871d3de",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_trans.c"
    },
    {
      "type": "modify",
      "old_id": "c62beee0921ea102e1c6ba27869fd93f062e3c65",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_trans.h",
      "new_id": "ff7e9e6eee844318e68c1559e07f0acda4c01b76",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_trans.h"
    },
    {
      "type": "modify",
      "old_id": "eb3fc57f9eef681d73e39e07e3546cb45c350929",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_trans_item.c",
      "new_id": "2937a1e53318a1f43b1ed51d76f4dd1d0579eb0c",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_trans_item.c"
    },
    {
      "type": "modify",
      "old_id": "73e2ad3974328ed9a62a81663feab3aacd0f730d",
      "old_mode": 33188,
      "old_path": "fs/xfs/xfs_trans_priv.h",
      "new_id": "901dc0f032dae73a79a81c611f22171013be0b42",
      "new_mode": 33188,
      "new_path": "fs/xfs/xfs_trans_priv.h"
    }
  ]
}