)]}' { "commit": "16cdcec736cd214350cdb591bf1091f8beedefa0", "tree": "5598d4561660c4d7a1d4de8b3703d6dd3cc7f9e7", "parents": [ "61c4f2c81c61f73549928dfd9f3e8f26aa36a8cf" ], "author": { "name": "Miao Xie", "email": "miaox@cn.fujitsu.com", "time": "Fri Apr 22 18:12:22 2011 +0800" }, "committer": { "name": "Chris Mason", "email": "chris.mason@oracle.com", "time": "Sat May 21 09:30:56 2011 -0400" }, "message": "btrfs: implement delayed inode items operation\n\nChangelog V5 -\u003e V6:\n- Fix oom when the memory load is high, by storing the delayed nodes into the\n root\u0027s radix tree, and letting btrfs inodes go.\n\nChangelog V4 -\u003e V5:\n- Fix the race on adding the delayed node to the inode, which is spotted by\n Chris Mason.\n- Merge Chris Mason\u0027s incremental patch into this patch.\n- Fix deadlock between readdir() and memory fault, which is reported by\n Itaru Kitayama.\n\nChangelog V3 -\u003e V4:\n- Fix nested lock, which is reported by Itaru Kitayama, by updating space cache\n inode in time.\n\nChangelog V2 -\u003e V3:\n- Fix the race between the delayed worker and the task which does delayed items\n balance, which is reported by Tsutomu Itoh.\n- Modify the patch address David Sterba\u0027s comment.\n- Fix the bug of the cpu recursion spinlock, reported by Chris Mason\n\nChangelog V1 -\u003e V2:\n- break up the global rb-tree, use a list to manage the delayed nodes,\n which is created for every directory and file, and used to manage the\n delayed directory name index items and the delayed inode item.\n- introduce a worker to deal with the delayed nodes.\n\nCompare with Ext3/4, the performance of file creation and deletion on btrfs\nis very poor. the reason is that btrfs must do a lot of b+ tree insertions,\nsuch as inode item, directory name item, directory name index and so on.\n\nIf we can do some delayed b+ tree insertion or deletion, we can improve the\nperformance, so we made this patch which implemented delayed directory name\nindex insertion/deletion and delayed inode update.\n\nImplementation:\n- introduce a delayed root object into the filesystem, that use two lists to\n manage the delayed nodes which are created for every file/directory.\n One is used to manage all the delayed nodes that have delayed items. And the\n other is used to manage the delayed nodes which is waiting to be dealt with\n by the work thread.\n- Every delayed node has two rb-tree, one is used to manage the directory name\n index which is going to be inserted into b+ tree, and the other is used to\n manage the directory name index which is going to be deleted from b+ tree.\n- introduce a worker to deal with the delayed operation. This worker is used\n to deal with the works of the delayed directory name index items insertion\n and deletion and the delayed inode update.\n When the delayed items is beyond the lower limit, we create works for some\n delayed nodes and insert them into the work queue of the worker, and then\n go back.\n When the delayed items is beyond the upper bound, we create works for all\n the delayed nodes that haven\u0027t been dealt with, and insert them into the work\n queue of the worker, and then wait for that the untreated items is below some\n threshold value.\n- When we want to insert a directory name index into b+ tree, we just add the\n information into the delayed inserting rb-tree.\n And then we check the number of the delayed items and do delayed items\n balance. (The balance policy is above.)\n- When we want to delete a directory name index from the b+ tree, we search it\n in the inserting rb-tree at first. If we look it up, just drop it. If not,\n add the key of it into the delayed deleting rb-tree.\n Similar to the delayed inserting rb-tree, we also check the number of the\n delayed items and do delayed items balance.\n (The same to inserting manipulation)\n- When we want to update the metadata of some inode, we cached the data of the\n inode into the delayed node. the worker will flush it into the b+ tree after\n dealing with the delayed insertion and deletion.\n- We will move the delayed node to the tail of the list after we access the\n delayed node, By this way, we can cache more delayed items and merge more\n inode updates.\n- If we want to commit transaction, we will deal with all the delayed node.\n- the delayed node will be freed when we free the btrfs inode.\n- Before we log the inode items, we commit all the directory name index items\n and the delayed inode update.\n\nI did a quick test by the benchmark tool[1] and found we can improve the\nperformance of file creation by ~15%, and file deletion by ~20%.\n\nBefore applying this patch:\nCreate files:\n Total files: 50000\n Total time: 1.096108\n Average time: 0.000022\nDelete files:\n Total files: 50000\n Total time: 1.510403\n Average time: 0.000030\n\nAfter applying this patch:\nCreate files:\n Total files: 50000\n Total time: 0.932899\n Average time: 0.000019\nDelete files:\n Total files: 50000\n Total time: 1.215732\n Average time: 0.000024\n\n[1] http://marc.info/?l\u003dlinux-btrfs\u0026m\u003d128212635122920\u0026q\u003dp3\n\nMany thanks for Kitayama-san\u0027s help!\n\nSigned-off-by: Miao Xie \u003cmiaox@cn.fujitsu.com\u003e\nReviewed-by: David Sterba \u003cdave@jikos.cz\u003e\nTested-by: Tsutomu Itoh \u003ct-itoh@jp.fujitsu.com\u003e\nTested-by: Itaru Kitayama \u003ckitayama@cl.bb4u.ne.jp\u003e\nSigned-off-by: Chris Mason \u003cchris.mason@oracle.com\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "31610ea73aec2bff3410ec7c65b3b52e2c7a14ba", "old_mode": 33188, "old_path": "fs/btrfs/Makefile", "new_id": "a8411c22313d743c8ac222b03f7e58caf185d528", "new_mode": 33188, "new_path": "fs/btrfs/Makefile" }, { "type": "modify", "old_id": "57c3bb2884ceabd2ea4be939557a6c273c9e8626", "old_mode": 33188, "old_path": "fs/btrfs/btrfs_inode.h", "new_id": "beefafd91f22d988951a1b0875e9ca95cd85222d", "new_mode": 33188, "new_path": "fs/btrfs/btrfs_inode.h" }, { "type": "modify", "old_id": "84d7ca1fe0bac42a58c9115f2dccaa68efb6b3b6", "old_mode": 33188, "old_path": "fs/btrfs/ctree.c", "new_id": "2736b6b2ff5f67484526936cb724104872770aa9", "new_mode": 33188, "new_path": "fs/btrfs/ctree.c" }, { "type": "modify", "old_id": "8f4b81de3ae2a0ffb21b57080de5649d9a3785ff", "old_mode": 33188, "old_path": "fs/btrfs/ctree.h", "new_id": "5d25129d011602e572401126a94b167743bfbe13", "new_mode": 33188, "new_path": "fs/btrfs/ctree.h" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "95485318f0011db0736d5008f3c7ebbdb4be8775", "new_mode": 33188, "new_path": "fs/btrfs/delayed-inode.c" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "eb7d240aa6485db61c8d13299519abc9b81d3cc0", "new_mode": 33188, "new_path": "fs/btrfs/delayed-inode.h" }, { "type": "modify", "old_id": "c62f02f6ae693728ce9286d963b78708428a86fb", "old_mode": 33188, "old_path": "fs/btrfs/dir-item.c", "new_id": "f53fb3847c96624eda0b1d333f1b9cbfb1df3b67", "new_mode": 33188, "new_path": "fs/btrfs/dir-item.c" }, { "type": "modify", "old_id": "228cf36ece8351475d5075f74e15624e4276e112", "old_mode": 33188, "old_path": "fs/btrfs/disk-io.c", "new_id": "22c3c958604947a3257edb9b46b2e518a9efd733", "new_mode": 33188, "new_path": "fs/btrfs/disk-io.c" }, { "type": "modify", "old_id": "07b20dc2fd9560c0f497ecc3615cf8da747c4688", "old_mode": 33188, "old_path": "fs/btrfs/disk-io.h", "new_id": "aca35af37dbc4efaee98d48eb96fe24c792d74c6", "new_mode": 33188, "new_path": "fs/btrfs/disk-io.h" }, { "type": "modify", "old_id": "9ee6bd55e16c5ea4cc9e2f1e31289ba6591730b1", "old_mode": 33188, "old_path": "fs/btrfs/extent-tree.c", "new_id": "7b0433866f36daa01941dbe346094d7c59c14931", "new_mode": 33188, "new_path": "fs/btrfs/extent-tree.c" }, { "type": "modify", "old_id": "7cd8ab0ef04d5b3e95ccd572f96ca858457e8c18", "old_mode": 33188, "old_path": "fs/btrfs/inode.c", "new_id": "3470f67c6258a42877f884625e4f099dcc9d9ed5", "new_mode": 33188, "new_path": "fs/btrfs/inode.c" }, { "type": "modify", "old_id": "2616f7ed47996a21df8b0c5de224c4b6c1aebf70", "old_mode": 33188, "old_path": "fs/btrfs/ioctl.c", "new_id": "df59401af742d3279a807f13f3eef545c4be5a39", "new_mode": 33188, "new_path": "fs/btrfs/ioctl.c" }, { "type": "modify", "old_id": "0ac712efcdf293ac8e858fef443b57316b039037", "old_mode": 33188, "old_path": "fs/btrfs/super.c", "new_id": "cc5a2a8a5acb5a2f35eaaad9ebc57c1213bd0bff", "new_mode": 33188, "new_path": "fs/btrfs/super.c" }, { "type": "modify", "old_id": "c571734d5e5a802ea73a0c6458dd41c0b2e56659", "old_mode": 33188, "old_path": "fs/btrfs/transaction.c", "new_id": "b83ed5e64a325553c85b0c7fff10c0a37821d8f5", "new_mode": 33188, "new_path": "fs/btrfs/transaction.c" }, { "type": "modify", "old_id": "e441acc6c584a7e03859d3e63cd3e455312ff631", "old_mode": 33188, "old_path": "fs/btrfs/transaction.h", "new_id": "cb928c6c42e67768bd00899f1d29d4eb533246f6", "new_mode": 33188, "new_path": "fs/btrfs/transaction.h" }, { "type": "modify", "old_id": "f997ec0c1ba4b8efb6b46f88160de43cda3da4f2", "old_mode": 33188, "old_path": "fs/btrfs/tree-log.c", "new_id": "ae0b72856bfb77a970dcc6966160de4d060e15d5", "new_mode": 33188, "new_path": "fs/btrfs/tree-log.c" } ] }