)]}'
{
  "commit": "eda09fbdcd8c5afaa81c2f1d28e8b9725bad4d5a",
  "tree": "0afe6e81172fc9508f8e4c13598a276fe3d043c6",
  "parents": [
    "1fe58a875e4bb08125c657b1b91ac515d2bdbcbe"
  ],
  "author": {
    "name": "Emil Medve",
    "email": "Emilian.Medve@Freescale.com",
    "time": "Wed Nov 14 03:24:04 2007 +1100"
  },
  "committer": {
    "name": "Paul Mackerras",
    "email": "paulus@samba.org",
    "time": "Fri Dec 21 15:05:58 2007 +1100"
  },
  "message": "[POWERPC] Optimize counting distinct entries in the relocation sections\n\nWhen a module has relocation sections with tens of thousands of\nentries, counting the distinct/unique entries only (i.e. no\nduplicates) at load time can take tens of seconds and up to minutes.\nThe sore point is the count_relocs() function which is called as part\nof the architecture specific module loading processing path:\n\n\t-\u003e load_module()\t\t\tgeneric\n\t   -\u003e module_frob_arch_sections()\tarch specific\n\t      -\u003e get_plt_size()\t\t32-bit\n\t      -\u003e get_stubs_size()\t64-bit\n\t\t -\u003e count_relocs()\n\nHere count_relocs is being called to find out how many distinct\ntargets of R_PPC_REL24 relocations there are, since each distinct\ntarget needs a PLT entry or a stub created for it.\n\nThe previous counting algorithm has O(n^2) complexity.  Basically two\nsolutions were proposed on the e-mail list: a hash based approach and\na sort based approach.\n\nThe hash based approach is the fastest (O(n)) but the has it needs\nadditional memory and for certain corner cases it could take lots of\nmemory due to the degeneration of the hash.  One such proposal was\nsubmitted here:\n\nhttp://ozlabs.org/pipermail/linuxppc-dev/2007-June/037641.html\n\nThe sort based approach is slower (O(n * log n + n)) but if the\nsorting is done \"in place\" it doesn\u0027t need additional memory.\nThis has O(n + n * log n) complexity with no additional memory\nrequirements.\n\nThis commit implements the in-place sort option.\n\nSigned-off-by: Emil Medve \u003cEmilian.Medve@Freescale.com\u003e\nSigned-off-by: Paul Mackerras \u003cpaulus@samba.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "07a89a3986394ebfd5eafabaaeb468358445beff",
      "old_mode": 33188,
      "old_path": "arch/powerpc/kernel/module_32.c",
      "new_id": "eab313858315ef991b5efc0d6886433105e1ac89",
      "new_mode": 33188,
      "new_path": "arch/powerpc/kernel/module_32.c"
    },
    {
      "type": "modify",
      "old_id": "75c7c4f1928059689353927c2c67d198c62e715f",
      "old_mode": 33188,
      "old_path": "arch/powerpc/kernel/module_64.c",
      "new_id": "3a82b02b784b0c8a4d8da7467b8c7d4410cf9ea4",
      "new_mode": 33188,
      "new_path": "arch/powerpc/kernel/module_64.c"
    }
  ]
}