)]}'
{
  "commit": "5beb49305251e5669852ed541e8e2f2f7696c53e",
  "tree": "46457450a22f23938b24904aeba5d4ada2f53b20",
  "parents": [
    "648bcc771145172a14bc35eeb849ed08f6aa4f1e"
  ],
  "author": {
    "name": "Rik van Riel",
    "email": "riel@redhat.com",
    "time": "Fri Mar 05 13:42:07 2010 -0800"
  },
  "committer": {
    "name": "Linus Torvalds",
    "email": "torvalds@linux-foundation.org",
    "time": "Sat Mar 06 11:26:26 2010 -0800"
  },
  "message": "mm: change anon_vma linking to fix multi-process server scalability issue\n\nThe old anon_vma code can lead to scalability issues with heavily forking\nworkloads.  Specifically, each anon_vma will be shared between the parent\nprocess and all its child processes.\n\nIn a workload with 1000 child processes and a VMA with 1000 anonymous\npages per process that get COWed, this leads to a system with a million\nanonymous pages in the same anon_vma, each of which is mapped in just one\nof the 1000 processes.  However, the current rmap code needs to walk them\nall, leading to O(N) scanning complexity for each page.\n\nThis can result in systems where one CPU is walking the page tables of\n1000 processes in page_referenced_one, while all other CPUs are stuck on\nthe anon_vma lock.  This leads to catastrophic failure for a benchmark\nlike AIM7, where the total number of processes can reach in the tens of\nthousands.  Real workloads are still a factor 10 less process intensive\nthan AIM7, but they are catching up.\n\nThis patch changes the way anon_vmas and VMAs are linked, which allows us\nto associate multiple anon_vmas with a VMA.  At fork time, each child\nprocess gets its own anon_vmas, in which its COWed pages will be\ninstantiated.  The parents\u0027 anon_vma is also linked to the VMA, because\nnon-COWed pages could be present in any of the children.\n\nThis reduces rmap scanning complexity to O(1) for the pages of the 1000\nchild processes, with O(N) complexity for at most 1/N pages in the system.\n This reduces the average scanning cost in heavily forking workloads from\nO(N) to 2.\n\nThe only real complexity in this patch stems from the fact that linking a\nVMA to anon_vmas now involves memory allocations.  This means vma_adjust\ncan fail, if it needs to attach a VMA to anon_vma structures.  This in\nturn means error handling needs to be added to the calling functions.\n\nA second source of complexity is that, because there can be multiple\nanon_vmas, the anon_vma linking in vma_adjust can no longer be done under\n\"the\" anon_vma lock.  To prevent the rmap code from walking up an\nincomplete VMA, this patch introduces the VM_LOCK_RMAP VMA flag.  This bit\nflag uses the same slot as the NOMMU VM_MAPPED_COPY, with an ifdef in mm.h\nto make sure it is impossible to compile a kernel that needs both symbolic\nvalues for the same bitflag.\n\nSome test results:\n\nWithout the anon_vma changes, when AIM7 hits around 9.7k users (on a test\nbox with 16GB RAM and not quite enough IO), the system ends up running\n\u003e99% in system time, with every CPU on the same anon_vma lock in the\npageout code.\n\nWith these changes, AIM7 hits the cross-over point around 29.7k users.\nThis happens with ~99% IO wait time, there never seems to be any spike in\nsystem time.  The anon_vma lock contention appears to be resolved.\n\n[akpm@linux-foundation.org: cleanups]\nSigned-off-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: KOSAKI Motohiro \u003ckosaki.motohiro@jp.fujitsu.com\u003e\nCc: Larry Woodman \u003clwoodman@redhat.com\u003e\nCc: Lee Schermerhorn \u003cLee.Schermerhorn@hp.com\u003e\nCc: Minchan Kim \u003cminchan.kim@gmail.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: Hugh Dickins \u003chugh.dickins@tiscali.co.uk\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": "b81e46b1629b2a0cfe12e40eac2426c33b33a4e1",
      "old_mode": 33188,
      "old_path": "arch/ia64/kernel/perfmon.c",
      "new_id": "703062c44fb9df33c7eefceefcf82b9598c71c59",
      "new_mode": 33188,
      "new_path": "arch/ia64/kernel/perfmon.c"
    },
    {
      "type": "modify",
      "old_id": "ca3335ea56ccf9dae52d19ddbe619315f1134225",
      "old_mode": 33188,
      "old_path": "arch/ia64/mm/init.c",
      "new_id": "ed41759efcac3b76e44d9a6b87c0c379448b4c5c",
      "new_mode": 33188,
      "new_path": "arch/ia64/mm/init.c"
    },
    {
      "type": "modify",
      "old_id": "ea7861727efde4f547b0dcee691afcb5a1a07a3c",
      "old_mode": 33188,
      "old_path": "fs/exec.c",
      "new_id": "5910307355914495a6ef4f27e501d5905c0dae3d",
      "new_mode": 33188,
      "new_path": "fs/exec.c"
    },
    {
      "type": "modify",
      "old_id": "8e580c07d1712b0deebd86a87d0a953eea7b8f0a",
      "old_mode": 33188,
      "old_path": "include/linux/mm.h",
      "new_id": "8e2841a2f441863105a693537704536a59ed41c1",
      "new_mode": 33188,
      "new_path": "include/linux/mm.h"
    },
    {
      "type": "modify",
      "old_id": "19549d7275abb52c2f964c4b28707f5e93335ebc",
      "old_mode": 33188,
      "old_path": "include/linux/mm_types.h",
      "new_id": "048b46270aa5220c8c70b1cf2637b1c8402bed32",
      "new_mode": 33188,
      "new_path": "include/linux/mm_types.h"
    },
    {
      "type": "modify",
      "old_id": "b019ae64e2ab1d356daf92aaa7e92547227246c7",
      "old_mode": 33188,
      "old_path": "include/linux/rmap.h",
      "new_id": "62da2001d55ccda3ada1005510f645afa4d94770",
      "new_mode": 33188,
      "new_path": "include/linux/rmap.h"
    },
    {
      "type": "modify",
      "old_id": "7616bcf107b96b97f7464a05986134e1c8b809b2",
      "old_mode": 33188,
      "old_path": "kernel/fork.c",
      "new_id": "bab7b254ad397933e1bb25f77246ff57e8473a07",
      "new_mode": 33188,
      "new_path": "kernel/fork.c"
    },
    {
      "type": "modify",
      "old_id": "56a0da1f9979d7eaa9d85cbc0b20ef76215e4abf",
      "old_mode": 33188,
      "old_path": "mm/ksm.c",
      "new_id": "a93f1b7f508cde17cb0b41f7183641dcfdb7a26f",
      "new_mode": 33188,
      "new_path": "mm/ksm.c"
    },
    {
      "type": "modify",
      "old_id": "17299fd4577c6fc903b5fcb15e52f7fba4f2149d",
      "old_mode": 33188,
      "old_path": "mm/memory-failure.c",
      "new_id": "d1f3351629766ffe112e3f904565ed3035412774",
      "new_mode": 33188,
      "new_path": "mm/memory-failure.c"
    },
    {
      "type": "modify",
      "old_id": "77d9f840936b29304773932e76f3d1103eee01ac",
      "old_mode": 33188,
      "old_path": "mm/memory.c",
      "new_id": "dc785b438d70fba119cae99e828dbc21b09cb7a1",
      "new_mode": 33188,
      "new_path": "mm/memory.c"
    },
    {
      "type": "modify",
      "old_id": "31656147128e6eb0b92edbcc4d6b535d6c0ceba9",
      "old_mode": 33188,
      "old_path": "mm/mmap.c",
      "new_id": "6a0c15db7f60663168f29e7bfdbb5aa668ba642b",
      "new_mode": 33188,
      "new_path": "mm/mmap.c"
    },
    {
      "type": "modify",
      "old_id": "4c4c803453f38a837da0e1fb3cb0e9a51d693027",
      "old_mode": 33188,
      "old_path": "mm/mremap.c",
      "new_id": "e9c75efce60938a82821d24dedf0702ea5d0a50b",
      "new_mode": 33188,
      "new_path": "mm/mremap.c"
    },
    {
      "type": "modify",
      "old_id": "48a2ecfaf05947230d32db3f54c49a3b0ba58b1d",
      "old_mode": 33188,
      "old_path": "mm/nommu.c",
      "new_id": "55727a74af98ff5266f899cf4793fc58e0f9f916",
      "new_mode": 33188,
      "new_path": "mm/nommu.c"
    },
    {
      "type": "modify",
      "old_id": "5cb47111f79e1e25fe539d3ceca3482e5bc6887f",
      "old_mode": 33188,
      "old_path": "mm/rmap.c",
      "new_id": "be34094e459565f6570ae0eb1ef46d8ec4909786",
      "new_mode": 33188,
      "new_path": "mm/rmap.c"
    }
  ]
}