)]}'
{
  "commit": "ae108ebd09de7481b592b82e5c4677ccc3558bb6",
  "tree": "9df33155b115e78fb378a9782c501fe45c37af39",
  "parents": [
    "3df8cc9b8aaf2009b9292a128ae580a914a162a9"
  ],
  "author": {
    "name": "Rafael Aquini",
    "email": "aquini@redhat.com",
    "time": "Tue Sep 07 20:00:53 2021 -0700"
  },
  "committer": {
    "name": "COS Cherry Picker",
    "email": "cloud-image-release@prod.google.com",
    "time": "Fri Sep 02 15:01:50 2022 -0700"
  },
  "message": "ipc: replace costly bailout check in sysvipc_find_ipc()\n\nsysvipc_find_ipc() was left with a costly way to check if the offset\nposition fed to it is bigger than the total number of IPC IDs in use.  So\nmuch so that the time it takes to iterate over /proc/sysvipc/* files grows\nexponentially for a custom benchmark that creates \"N\" SYSV shm segments\nand then times the read of /proc/sysvipc/shm (milliseconds):\n\n    12 msecs to read   1024 segs from /proc/sysvipc/shm\n    18 msecs to read   2048 segs from /proc/sysvipc/shm\n    65 msecs to read   4096 segs from /proc/sysvipc/shm\n   325 msecs to read   8192 segs from /proc/sysvipc/shm\n  1303 msecs to read  16384 segs from /proc/sysvipc/shm\n  5182 msecs to read  32768 segs from /proc/sysvipc/shm\n\nThe root problem lies with the loop that computes the total amount of ids\nin use to check if the \"pos\" feeded to sysvipc_find_ipc() grew bigger than\n\"ids-\u003ein_use\".  That is a quite inneficient way to get to the maximum\nindex in the id lookup table, specially when that value is already\nprovided by struct ipc_ids.max_idx.\n\nThis patch follows up on the optimization introduced via commit\n15df03c879836 (\"sysvipc: make get_maxid O(1) again\") and gets rid of the\naforementioned costly loop replacing it by a simpler checkpoint based on\nipc_get_maxidx() returned value, which allows for a smooth linear increase\nin time complexity for the same custom benchmark:\n\n     2 msecs to read   1024 segs from /proc/sysvipc/shm\n     2 msecs to read   2048 segs from /proc/sysvipc/shm\n     4 msecs to read   4096 segs from /proc/sysvipc/shm\n     9 msecs to read   8192 segs from /proc/sysvipc/shm\n    19 msecs to read  16384 segs from /proc/sysvipc/shm\n    39 msecs to read  32768 segs from /proc/sysvipc/shm\n\nBUG\u003db/244292084\nTEST\u003dsponge2/65c60f76-e948-435a-942e-f63a59790e90\nRELEASE_NOTE\u003dFix CVE-2021-3669  in kernel\nSOURCE\u003dUPSTREAM(COMMIT\u003d20401d1058f3f841f35a594ac2fc1293710e55b9)\n\ncos-patch: security-moderate\nLink: https://lkml.kernel.org/r/20210809203554.1562989-1-aquini@redhat.com\nSigned-off-by: Rafael Aquini \u003caquini@redhat.com\u003e\nAcked-by: Davidlohr Bueso \u003cdbueso@suse.de\u003e\nAcked-by: Manfred Spraul \u003cmanfred@colorfullife.com\u003e\nCc: Waiman Long \u003cllong@redhat.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\nChange-Id: Ia607c05345e940c883c724bd2286e366e047622a\nReviewed-on: https://cos-review.googlesource.com/c/third_party/kernel/+/36553\nMain-Branch-Verified: Cusky Presubmit Bot \u003cpresubmit@cos-infra-prod.iam.gserviceaccount.com\u003e\nReviewed-by: Oleksandr Tymoshenko \u003covt@google.com\u003e\nTested-by: Cusky Presubmit Bot \u003cpresubmit@cos-infra-prod.iam.gserviceaccount.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "bbb5190af6d9f29042c4ab1403e07d63d9ead714",
      "old_mode": 33188,
      "old_path": "ipc/util.c",
      "new_id": "7c3601dad9bd51018e01a542f5cc9c06b71c9e23",
      "new_mode": 33188,
      "new_path": "ipc/util.c"
    }
  ]
}