)]}'
{
  "commit": "bf181b9f9d8dfbba58b23441ad60d0bc33806d64",
  "tree": "7ad0caaf8998f31c5d910dcbb768f5a1d381b5f4",
  "parents": [
    "108d6642ad81bb1d62b401490a334d2c12397517"
  ],
  "author": {
    "name": "Michel Lespinasse",
    "email": "walken@google.com",
    "time": "Mon Oct 08 16:31:39 2012 -0700"
  },
  "committer": {
    "name": "Linus Torvalds",
    "email": "torvalds@linux-foundation.org",
    "time": "Tue Oct 09 16:22:41 2012 +0900"
  },
  "message": "mm anon rmap: replace same_anon_vma linked list with an interval tree.\n\nWhen a large VMA (anon or private file mapping) is first touched, which\nwill populate its anon_vma field, and then split into many regions through\nthe use of mprotect(), the original anon_vma ends up linking all of the\nvmas on a linked list.  This can cause rmap to become inefficient, as we\nhave to walk potentially thousands of irrelevent vmas before finding the\none a given anon page might fall into.\n\nBy replacing the same_anon_vma linked list with an interval tree (where\neach avc\u0027s interval is determined by its vma\u0027s start and last pgoffs), we\ncan make rmap efficient for this use case again.\n\nWhile the change is large, all of its pieces are fairly simple.\n\nMost places that were walking the same_anon_vma list were looking for a\nknown pgoff, so they can just use the anon_vma_interval_tree_foreach()\ninterval tree iterator instead.  The exception here is ksm, where the\npage\u0027s index is not known.  It would probably be possible to rework ksm so\nthat the index would be known, but for now I have decided to keep things\nsimple and just walk the entirety of the interval tree there.\n\nWhen updating vma\u0027s that already have an anon_vma assigned, we must take\ncare to re-index the corresponding avc\u0027s on their interval tree.  This is\ndone through the use of anon_vma_interval_tree_pre_update_vma() and\nanon_vma_interval_tree_post_update_vma(), which remove the avc\u0027s from\ntheir interval tree before the update and re-insert them after the update.\n The anon_vma stays locked during the update, so there is no chance that\nrmap would miss the vmas that are being updated.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Hugh Dickins \u003chughd@google.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "f1d9aaadb5666da2843d0c0ca3655d2700c36e3c",
      "old_mode": 33188,
      "old_path": "include/linux/mm.h",
      "new_id": "0cdab4e0f814d21484431df0ba58a276ec918b40",
      "new_mode": 33188,
      "new_path": "include/linux/mm.h"
    },
    {
      "type": "modify",
      "old_id": "7f32cec57e6744da01f2ba47e1c96e129c56f674",
      "old_mode": 33188,
      "old_path": "include/linux/rmap.h",
      "new_id": "dce44f7d3ed80c0c786045c00f8c455dc6630ef9",
      "new_mode": 33188,
      "new_path": "include/linux/rmap.h"
    },
    {
      "type": "modify",
      "old_id": "010d32944d14d64f7b6174bc1bed9a38c159dc9d",
      "old_mode": 33188,
      "old_path": "mm/huge_memory.c",
      "new_id": "ce59ada0946263e8b1482d3249b73441905a1d14",
      "new_mode": 33188,
      "new_path": "mm/huge_memory.c"
    },
    {
      "type": "modify",
      "old_id": "4ab7b9ec3a5680723d6ac746029b2b874cbff0dc",
      "old_mode": 33188,
      "old_path": "mm/interval_tree.c",
      "new_id": "f7c72cd35e1d82aeb8e907a88a48e5cb0d9f3e9b",
      "new_mode": 33188,
      "new_path": "mm/interval_tree.c"
    },
    {
      "type": "modify",
      "old_id": "9638620a7530ed2b35ab381e751ab0ab90018cdb",
      "old_mode": 33188,
      "old_path": "mm/ksm.c",
      "new_id": "14ee5cf8a513c7abe24ff47122eec918856a3611",
      "new_mode": 33188,
      "new_path": "mm/ksm.c"
    },
    {
      "type": "modify",
      "old_id": "c38a6257d0824b722b222eb8affc366f1495597a",
      "old_mode": 33188,
      "old_path": "mm/memory-failure.c",
      "new_id": "6c5899b9034aa7d769e5fd80e139cad61af104c0",
      "new_mode": 33188,
      "new_path": "mm/memory-failure.c"
    },
    {
      "type": "modify",
      "old_id": "66984aab79152f8fba0a55ad5925e8f08dce5cf0",
      "old_mode": 33188,
      "old_path": "mm/mmap.c",
      "new_id": "2e580ed7921176b694db73693d185f0922f9926f",
      "new_mode": 33188,
      "new_path": "mm/mmap.c"
    },
    {
      "type": "modify",
      "old_id": "8cbd62fde0f18528a1eb7e15486bbc8995c70670",
      "old_mode": 33188,
      "old_path": "mm/rmap.c",
      "new_id": "9c61bf387fd1bc369638a3c33b5457f4bedb5ec0",
      "new_mode": 33188,
      "new_path": "mm/rmap.c"
    }
  ]
}