)]}'
{
  "log": [
    {
      "commit": "9826a516ff77c5820e591211e4f3e58ff36f46be",
      "tree": "bdec1e2fe5ff95569795069bac73977faba17d57",
      "parents": [
        "9c079add0d0f45220f4bb37febf0621137ec2d38"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:35 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:40 2012 +0900"
      },
      "message": "mm: interval tree updates\n\nUpdate the generic interval tree code that was introduced in \"mm: replace\nvma prio_tree with an interval tree\".\n\nChanges:\n\n- fixed \u0027endpoing\u0027 typo noticed by Andrew Morton\n\n- replaced include/linux/interval_tree_tmpl.h, which was used as a\n  template (including it automatically defined the interval tree\n  functions) with include/linux/interval_tree_generic.h, which only\n  defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself\n  defines the interval tree functions when invoked. Now that is a very\n  long macro which is unfortunate, but it does make the usage sites\n  (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously.\n\n- make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro,\n  instead of duplicating that code in the interval tree template.\n\n- replaced vma_interval_tree_add(), which was actually handling the\n  nonlinear and interval tree cases, with vma_interval_tree_insert_after()\n  which handles only the interval tree case and has an API that is more\n  consistent with the other interval tree handling functions.\n  The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap().\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"
    },
    {
      "commit": "6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08",
      "tree": "422ed8d7ac2fe45069f20cfba84a9a097bf444af",
      "parents": [
        "fff3fd8a1210a165252cd7cd01206da7a90d3a06"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:25 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:39 2012 +0900"
      },
      "message": "mm: replace vma prio_tree with an interval tree\n\nImplement an interval tree as a replacement for the VMA prio_tree.  The\nalgorithms are similar to lib/interval_tree.c; however that code can\u0027t be\ndirectly reused as the interval endpoints are not explicitly stored in the\nVMA.  So instead, the common algorithm is moved into a template and the\ndetails (node type, how to get interval endpoints from the node, etc) are\nfilled in using the C preprocessor.\n\nOnce the interval tree functions are available, using them as a\nreplacement to the VMA prio tree is a relatively simple, mechanical job.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Hillf Danton \u003cdhillf@gmail.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Catalin Marinas \u003ccatalin.marinas@arm.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "fff3fd8a1210a165252cd7cd01206da7a90d3a06",
      "tree": "3db89d48720ba726999e9d8486d8e991c7664123",
      "parents": [
        "3908836aa77e3621aaf2101f2920e01d7c8460d6"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:23 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:39 2012 +0900"
      },
      "message": "rbtree: add prio tree and interval tree tests\n\nPatch 1 implements support for interval trees, on top of the augmented\nrbtree API. It also adds synthetic tests to compare the performance of\ninterval trees vs prio trees. Short answers is that interval trees are\nslightly faster (~25%) on insert/erase, and much faster (~2.4 - 3x)\non search. It is debatable how realistic the synthetic test is, and I have\nnot made such measurements yet, but my impression is that interval trees\nwould still come out faster.\n\nPatch 2 uses a preprocessor template to make the interval tree generic,\nand uses it as a replacement for the vma prio_tree.\n\nPatch 3 takes the other prio_tree user, kmemleak, and converts it to use\na basic rbtree. We don\u0027t actually need the augmented rbtree support here\nbecause the intervals are always non-overlapping.\n\nPatch 4 removes the now-unused prio tree library.\n\nPatch 5 proposes an additional optimization to rb_erase_augmented, now\nproviding it as an inline function so that the augmented callbacks can be\ninlined in. This provides an additional 5-10% performance improvement\nfor the interval tree insert/erase benchmark. There is a maintainance cost\nas it exposes augmented rbtree users to some of the rbtree library internals;\nhowever I think this cost shouldn\u0027t be too high as I expect the augmented\nrbtree will always have much less users than the base rbtree.\n\nI should probably add a quick summary of why I think it makes sense to\nreplace prio trees with augmented rbtree based interval trees now.  One of\nthe drivers is that we need augmented rbtrees for Rik\u0027s vma gap finding\ncode, and once you have them, it just makes sense to use them for interval\ntrees as well, as this is the simpler and more well known algorithm.  prio\ntrees, in comparison, seem *too* clever: they impose an additional \u0027heap\u0027\nconstraint on the tree, which they use to guarantee a faster worst-case\ncomplexity of O(k+log N) for stabbing queries in a well-balanced prio\ntree, vs O(k*log N) for interval trees (where k\u003dnumber of matches,\nN\u003dnumber of intervals).  Now this sounds great, but in practice prio trees\ndon\u0027t realize this theorical benefit.  First, the additional constraint\nmakes them harder to update, so that the kernel implementation has to\nsimplify things by balancing them like a radix tree, which is not always\nideal.  Second, the fact that there are both index and heap properties\nmakes both tree manipulation and search more complex, which results in a\nhigher multiplicative time constant.  As it turns out, the simple interval\ntree algorithm ends up running faster than the more clever prio tree.\n\nThis patch:\n\nAdd two test modules:\n\n- prio_tree_test measures the performance of lib/prio_tree.c, both for\n  insertion/removal and for stabbing searches\n\n- interval_tree_test measures the performance of a library of equivalent\n  functionality, built using the augmented rbtree support.\n\nIn order to support the second test module, lib/interval_tree.c is\nintroduced. It is kept separate from the interval_tree_test main file\nfor two reasons: first we don\u0027t want to provide an unfair advantage\nover prio_tree_test by having everything in a single compilation unit,\nand second there is the possibility that the interval tree functionality\ncould get some non-test users in kernel over time.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Hillf Danton \u003cdhillf@gmail.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Catalin Marinas \u003ccatalin.marinas@arm.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    }
  ]
}