)]}'
{
  "commit": "03cbc358aab3faf34bfeaa02206fa660127e9b3f",
  "tree": "8d95237532390a1beeef37158174fd045b0f8819",
  "parents": [
    "632dd2053a1146c826ceb6f26ab689389c05e751"
  ],
  "author": {
    "name": "Ingo Molnar",
    "email": "mingo@elte.hu",
    "time": "Fri Sep 29 02:01:46 2006 -0700"
  },
  "committer": {
    "name": "Linus Torvalds",
    "email": "torvalds@g5.osdl.org",
    "time": "Fri Sep 29 09:18:25 2006 -0700"
  },
  "message": "[PATCH] lockdep core: improve the lock-chain-hash\n\nWith CONFIG_DEBUG_LOCK_ALLOC turned off i was getting sporadic failures in\nthe locking self-test:\n\n  ------------\u003e\n  | Locking API testsuite:\n  ----------------------------------------------------------------------------\n                                   | spin |wlock |rlock |mutex | wsem | rsem |\n    --------------------------------------------------------------------------\n                       A-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |\n                   A-B-B-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |\n               A-B-B-C-C-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |\n               A-B-C-A-B-C deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |\n           A-B-B-C-C-D-D-A deadlock:  ok  |FAILED|  ok  |  ok  |  ok  |  ok  |\n           A-B-C-D-B-D-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |\n           A-B-C-D-B-C-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |FAILED|\n\nafter much debugging it turned out to be caused by accidental chain-hash\nkey collisions.  The current hash is:\n\n #define iterate_chain_key(key1, key2) \\\n\t(((key1) \u003c\u003c MAX_LOCKDEP_KEYS_BITS/2) ^ \\\n\t((key1) \u003e\u003e (64-MAX_LOCKDEP_KEYS_BITS/2)) ^ \\\n \t(key2))\n\nwhere MAX_LOCKDEP_KEYS_BITS is 11.  This hash is pretty good as it will\nshift by 5 bits in every iteration, where every new ID \u0027mixed\u0027 into the\nhash would have up to 11 bits.  But because there was a 6 bits overlap\nbetween subsequent IDs and their high bits tended to be similar, there was\na chance for accidental chain-hash collision for a low number of locks\nheld.\n\nthe solution is to shift by 11 bits:\n\n #define iterate_chain_key(key1, key2) \\\n\t(((key1) \u003c\u003c MAX_LOCKDEP_KEYS_BITS) ^ \\\n\t((key1) \u003e\u003e (64-MAX_LOCKDEP_KEYS_BITS)) ^ \\\n \t(key2))\n\nThis keeps the hash perfect up to 5 locks held, but even above that the\nhash is still good because 11 bits is a relative prime to the total 64\nbits, so a complete match will only occur after 64 held locks (which doesnt\nhappen in Linux).  Even after 5 locks held, entropy of the 5 IDs mixed into\nthe hash is already good enough so that overlap doesnt generate a colliding\nhash ID.\n\nwith this change the false positives went away.\n\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "df1c3594de31b2649b198b1961bcb5e5ef9e8068",
      "old_mode": 33188,
      "old_path": "kernel/lockdep.c",
      "new_id": "e596525669ed4fa5018ee452c7bc429b945f8d00",
      "new_mode": 33188,
      "new_path": "kernel/lockdep.c"
    }
  ]
}