10000 Avoid integer overflow while sifting-up a heap in tuplesort.c. · postgres/postgres@512f67c · GitHub
[go: up one dir, main page]
Skip to content
{"payload":{"commit":{"oid":"512f67c8d02cc558f9c269cc848b0f0f788c4fe1","url":"/postgres/postgres/commit/512f67c8d02cc558f9c269cc848b0f0f788c4fe1","authoredDate":"2017-07-12T13:24:16.000-04:00","committedDate":"2017-07-12T13:24:16.000-04:00","shortMessage":null,"shortMessageMarkdown":"\u003cdiv\u003eAvoid integer overflow while sifting-up a heap in tuplesort.c.\u003c/div\u003e","shortMessageMarkdownLink":null,"bodyMessageHtml":"If the number of tuples in the heap exceeds approximately INT_MAX/2,\nthis loop's calculation \"2*i+1\" could overflow, resulting in a crash.\nFix it by using unsigned int rather than int for the relevant local\nvariables; that shouldn't cost anything extra on any popular hardware.\nPer bug #14722 from Sergey Koposov.\n\nOriginal patch by Sergey Koposov, modified by me per a suggestion\nfrom Heikki Linnakangas to use unsigned int not int64.\n\nBack-patch to 9.4, where tuplesort.c grew the ability to sort as many\nas INT_MAX tuples in-memory (commit \u003ca class=\"commit-link\" data-hovercard-type=\"commit\" data-hovercard-url=\"https://github.com/postgres/postgres/commit/263865a48973767ce8ed7b7788059a38a24a9f37/hovercard\" href=\"https://github.com/postgres/postgres/commit/263865a48973767ce8ed7b7788059a38a24a9f37\"\u003e\u003ctt\u003e263865a\u003c/tt\u003e\u003c/a\u003e).\n\nDiscussion: \u003ca href=\"https://postgr.es/m/20170629161637.1478.93109@wrigleys.postgresql.org\" rel=\"nofollow\"\u003ehttps://postgr.es/m/20170629161637.1478.93109@wrigleys.postgresql.org\u003c/a\u003e","authors":[{"login":"tglsfdc","displayName":"Tom Lane","avatarUrl":"https://avatars.githubusercontent.com/u/8755309?v=4","path":"/tglsfdc","isGitHub":false}],"committerAttribution":false,"committer":{"login":"tglsfdc","displayName":"Tom Lane","avatarUrl":"https://avatars.githubusercontent.com/u/8755309?v=4","path":"/tglsfdc","isGitHub":false},"parents":["ca906f68f22bf2076349394a5f28caf1f6e6f2f7"],"globalRelayId":"MDY6Q29tbWl0OTI3NDQyOjUxMmY2N2M4ZDAyY2M1NThmOWMyNjljYzg0OGIwZjBmNzg4YzRmZTE=","sha1":"ca906f68f22bf2076349394a5f28caf1f6e6f2f7","sha2":"512f67c8d02cc558f9c269cc848b0f0f788c4fe1"},"currentUser":null,"repo":{"id":927442,"defaultBranch":"master","name":"postgres","ownerLogin":"postgres","currentUserCanPush":false,"isFork":false,"isEmpty":false,"createdAt":"2010-09-21T11:35:45.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/177543?v=4","public":true,"private":false,"isOrgOwned":true},"diffEntryData":[{"diffLines":[{"stylingDirective":null,"type":"HUNK","blobLineNumber":3489,"text":"@@ -3490,19 +3490,24 @@ tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple,","html":"@@ -3490,19 +3490,24 @@ tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple,","displayNoNewLineWarning":false,"position":0,"left":3489,"right":3489},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3490,"text":" \t\t\t\t\t\t bool checkIndex)","html":" \t\t\t\t\t\t \u003cspan class=pl-smi\u003ebool\u003c/span\u003e \u003cspan class=pl-s1\u003echeckIndex\u003c/span\u003e)","displayNoNewLineWarning":false,"position":1,"left":3490,"right":3490},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3491,"text":" {","html":" {","displayNoNewLineWarning":false,"position":2,"left":3491,"right":3491},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3492,"text":" \tSortTuple *memtuples = state-\u003ememtuples;","html":" \t\u003cspan class=pl-smi\u003eSortTuple\u003c/span\u003e \u003cspan class=pl-c1\u003e*\u003c/span\u003e\u003cspan class=pl-s1\u003ememtuples\u003c/span\u003e \u003cspan class=pl-c1\u003e=\u003c/span\u003e \u003cspan class=pl-s1\u003estate\u003c/span\u003e\u003cspan class=pl-c1\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=pl-c1\u003ememtuples\u003c/span\u003e;","displayNoNewLineWarning":false,"position":3,"left":3492,"right":3492},{"stylingDirective":null,"type":"DELETION","blobLineNumber":3493,"text":"-\tint\t\t\ti,","html":"-\t\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e\u003cspan class=\"x x-first x-last\"\u003e\t\t\t\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e,","displayNoNewLineWarning":false,"position":4,"left":3493,"right":3492},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3493,"text":"+\tunsigned int i,","html":"+\t\u003cspan class=\"pl-smi\"\u003e\u003cspan class=\"x x-first x-last\"\u003eunsigned \u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"x x-first x-last\"\u003e \u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e,","displayNoNewLineWarning":false,"position":5,"left":3493,"right":3493},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3494,"text":" \t\t\t\tn;","html":" \t\t\t\t\u003cspan class=pl-s1\u003en\u003c/span\u003e;","displayNoNewLineWarning":false,"position":6,"left":3494,"right":3494},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3495,"text":" ","html":"\u003cbr\u003e","displayNoNewLineWarning":false,"position":7,"left":3495,"right":3495},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3496,"text":" \tAssert(!checkIndex || state-\u003ecurrentRun == RUN_FIRST);","html":" \t\u003cspan class=pl-en\u003eAssert\u003c/span\u003e(!\u003cspan class=pl-s1\u003echeckIndex\u003c/span\u003e \u003cspan class=pl-c1\u003e||\u003c/span\u003e \u003cspan class=pl-s1\u003estate\u003c/span\u003e\u003cspan class=pl-c1\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=pl-c1\u003ecurrentRun\u003c/span\u003e \u003cspan class=pl-c1\u003e==\u003c/span\u003e \u003cspan class=pl-c1\u003eRUN_FIRST\u003c/span\u003e);","displayNoNewLineWarning":false,"position":8,"left":3496,"right":3496},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3497,"text":" \tAssert(state-\u003ememtupcount \u003e= 1);","html":" \t\u003cspan class=pl-en\u003eAssert\u003c/span\u003e(\u003cspan class=pl-s1\u003estate\u003c/span\u003e\u003cspan class=pl-c1\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=pl-c1\u003ememtupcount\u003c/span\u003e \u0026gt;= \u003cspan class=pl-c1\u003e1\u003c/span\u003e);","displayNoNewLineWarning":false,"position":9,"left":3497,"right":3497},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3498,"text":" ","html":"\u003cbr\u003e","displayNoNewLineWarning":false,"position":10,"left":3498,"right":3498},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3499,"text":" \tCHECK_FOR_INTERRUPTS();","html":" \t\u003cspan class=pl-en\u003eCHECK_FOR_INTERRUPTS\u003c/span\u003e();","displayNoNewLineWarning":false,"position":11,"left":3499,"right":3499},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3500,"text":" ","html":"\u003cbr\u003e","displayNoNewLineWarning":false,"position":12,"left":3500,"right":3500},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3501,"text":"+\t/*","html":"+\t\u003cspan class=pl-c\u003e/*\u003c/span\u003e","displayNoNewLineWarning":false,"position":13,"left":3500,"right":3501},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3502,"text":"+\t * state-\u003ememtupcount is \"int\", but we use \"unsigned int\" for i, j, n.","html":"+\u003cspan class=pl-c\u003e\t * state-\u0026gt;memtupcount is \u0026quot;int\u0026quot;, but we use \u0026quot;unsigned int\u0026quot; for i, j, n.\u003c/span\u003e","displayNoNewLineWarning":false,"position":14,"left":3500,"right":3502},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3503,"text":"+\t * This prevents overflow in the \"2 * i + 1\" calculation, since at the top","html":"+\u003cspan class=pl-c\u003e\t * This prevents overflow in the \u0026quot;2 * i + 1\u0026quot; calculation, since at the top\u003c/span\u003e","displayNoNewLineWarning":false,"position":15,"left":3500,"right":3503},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3504,"text":"+\t * of the loop we must have i \u003c n \u003c= INT_MAX \u003c= UINT_MAX/2.","html":"+\u003cspan class=pl-c\u003e\t * of the loop we must have i \u0026lt; n \u0026lt;= INT_MAX \u0026lt;= UINT_MAX/2.\u003c/span\u003e","displayNoNewLineWarning":false,"position":16,"left":3500,"right":3504},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3505,"text":"+\t */","html":"+\u003cspan class=pl-c\u003e\t */\u003c/span\u003e","displayNoNewLineWarning":false,"position":17,"left":3500,"right":3505},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3506,"text":" \tn = state-\u003ememtupcount;","html":" \t\u003cspan class=pl-s1\u003en\u003c/span\u003e \u003cspan class=pl-c1\u003e=\u003c/span\u003e \u003cspan class=pl-s1\u003estate\u003c/span\u003e\u003cspan class=pl-c1\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=pl-c1\u003ememtupcount\u003c/span\u003e;","displayNoNewLineWarning":false,"position":18,"left":3501,"right":3506},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3507,"text":" \ti = 0;\t\t\t\t\t\t/* i is where the \"hole\" is */","html":" \t\u003cspan class=pl-s1\u003ei\u003c/span\u003e \u003cspan class=pl-c1\u003e=\u003c/span\u003e \u003cspan class=pl-c1\u003e0\u003c/span\u003e;\t\t\t\t\t\t\u003cspan class=pl-c\u003e/* i is where the \u0026quot;hole\u0026quot; is */\u003c/span\u003e","displayNoNewLineWarning":false,"position":19,"left":3502,"right":3507},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3508,"text":" \tfor (;;)","html":" \t\u003cspan class=pl-k\u003efor\u003c/span\u003e (;;)","displayNoNewLineWarning":false,"position":20,"left":3503,"right":3508},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3509,"text":" \t{","html":" \t{","displayNoNewLineWarning":false,"position":21,"left":3504,"right":3509},{"stylingDirective":null,"type":"DELETION","blobLineNumber":3505,"text":"-\t\tint\t\t\tj = 2 * i + 1;","html":"-\t\t\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e\u003cspan class=\"x x-first x-last\"\u003e\t\t\t\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e;","displayNoNewLineWarning":false,"position":22,"left":3505,"right":3509},{"stylingDirective":null,"type":"ADDITION","blobLineNumber":3510,"text":"+\t\tunsigned int j = 2 * i + 1;","html":"+\t\t\u003cspan class=\"pl-smi\"\u003e\u003cspan class=\"x x-first x-last\"\u003eunsigned \u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"x x-first x-last\"\u003e \u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e;","displayNoNewLineWarning":false,"position":23,"left":3505,"right":3510},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3511,"text":" ","html":"\u003cbr\u003e","displayNoNewLineWarning":false,"position":24,"left":3506,"right":3511},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3512,"text":" \t\tif (j \u003e= n)","html":" \t\t\u003cspan class=pl-k\u003eif\u003c/span\u003e (\u003cspan class=pl-s1\u003ej\u003c/span\u003e \u0026gt;= \u003cspan class=pl-s1\u003en\u003c/span\u003e)","displayNoNewLineWarning":false,"position":25,"left":3507,"right":3512},{"stylingDirective":null,"type":"CONTEXT","blobLineNumber":3513,"text":" \t\t\tbreak;","html":" \t\t\t\u003cspan class=pl-k\u003ebreak\u003c/span\u003e;","displayNoNewLineWarning":false,"position":26,"left":3508,"right":3513}],"diffNumber":0,"diffSize":"0 Bytes","isBinary":false,"isTooBig":false,"collapsed":false,"isSubmodule":false,"lineCount":4455,"linesChanged":9,"newTreeEntry":{"lineCount":4455,"path":"src/backend/utils/sort/tuplesort.c","mode":100644,"isGenerated":false},"oldTreeEntry":{"lineCount":0,"path":"src/backend/utils/sort/tuplesort.c","mode":100644},"linesAdded":7,"linesDeleted":2,"path":"src/backend/utils/sort/tuplesort.c","pathDigest":"5b735c65568e935c0bdf768116c93c1266ac7b4c516a06fb1aa847b4e093cff1","status":"MODIFIED","truncatedReason":null,"oldOid":"ca906f68f22bf2076349394a5f28caf1f6e6f2f7","newOid":"512f67c8d02cc558f9c269cc848b0f0f788c4fe1","copilotChatReference":null,"deletedSha":"ca906f68f22bf2076349394a5f28caf1f6e6f2f7","canToggleRichDiff":false,"defaultToRichDiff":false,"proseDifffHtml":null,"renderInfo":null,"dependencyDiffPath":null,"submodule":null}],"splitViewPreference":"unified","ignoreWhitespace":false,"repoOwnerGlobalRelayId":"MDEyOk9yZ2FuaXphdGlvbjE3NzU0Mw==","commentsPreference":"visible","diffLineSpacingPreference":"relaxed","useMonospaceFont":false,"pasteUrlLinkAsPlainText":false,"userNotices":[],"path":"/postgres/postgres/commit/512f67c8d02cc558f9c269cc848b0f0f788c4fe1","fileTreeExpanded":true,"headerInfo":{"additions":7,"deletions":2,"filesChanged":1,"filesChangedString":"1"},"moreDiffsToLoad":false,"asyncDiffLoadInfo":{"startIndex":1,"truncated":false,"byteCount":718,"lineShownCount":27},"commentInfo":{"canComment":false,"locked":false,"canLock":false,"repoArchived":false},"csrf_tokens":{"/users/diffview?diff=split":{"post":"xNGBdx21lbMwVTkcTTd8ZBxeYgA4GK_LLQogPO5wWaHmTR97vD91V3tk4P54N-Sc-MCAKy5x-00fV4-hIjywfA"},"/users/diffview?diff=unified":{"post":"s_8Ocbz-Y76Nw5Zwylc3WUMsUC4B-usdXOP6KrAzhXaRY5B9HXSDWsbyT5L_V6-hp7KyBReTv5tuvlW3fH9sqw"},"/notifications/thread":{"post":"JCbSIOvmXwad4wolTbH3vIVyzsVWiUX3CkP_EWu8FF3ptOnLDLRdr-qW-F5FbcQHpcWQNBYwiseDn2Gk8-0XCA"}}},"title":"Avoid integer overflow while sifting-up a heap in tuplesort.c. · postgres/postgres@512f67c","appPayload":{"helpUrl":"https://docs.github.com","findInDiffWorkerPath":"/assets-cdn/worker/find-in-diff-worker-2bfe39677d14.js","enabled_features":{"diff_ux_refresh_beta":false,"diff_inline_comments":true,"diff_ux_refresh_ssr_five":false,"diff_ux_refresh_ssr_ten":false,"react_diff_line_type_character_correction":true}}}

Commit 512f67c

Browse files
tglsfdctglsfdc
committed
Avoid integer overflow while sifting-up a heap in tuplesort.c.
If the number of tuples in the heap exceeds approximately INT_MAX/2, this loop's calculation "2*i+1" could overflow, resulting in a crash. Fix it by using unsigned int rather than int for the relevant local variables; that shouldn't cost anything extra on any popular hardware. Per bug #14722 from Sergey Koposov. Original patch by Sergey Koposov, modified by me per a suggestion from Heikki Linnakangas to use unsigned int not int64. Back-patch to 9.4, where tuplesort.c grew the ability to sort as many as INT_MAX tuples in-memory (commit 263865a). Discussion: https://postgr.es/m/20170629161637.1478.93109@wrigleys.postgresql.org
1 parent ca906f6 commit 512f67c

File tree

1 file changed

+7
-2
lines changed

1 file changed

+7
-2
lines changed

‎src/backend/utils/sort/tuplesort.c

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3490,19 +3490,24 @@ tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple *tuple,
34903490
bool checkIndex)
34913491
{
34923492
SortTuple *memtuples = state->memtuples;
3493-
int i,
3493+
unsigned int i,
34943494
n;
34953495

34963496
Assert(!checkIndex || state->currentRun == RUN_FIRST);
34973497
Assert(state->memtupcount >= 1);
34983498

34993499
CHECK_FOR_INTERRUPTS();
35003500

3501+
/*
3502+
* state->memtupcount is "int", but we use "unsigned int" for i, j, n.
3503+
* This prevents overflow in the "2 * i + 1" calculation, since at the top
3504+
* of the loop we must have i < n <= INT_MAX <= UINT_MAX/2.
3505+
*/
35013506
n = state->memtupcount;
35023507
i = 0; /* i is where the "hole" is */
35033508
for (;;)
35043509
{
3505-
int j = 2 * i + 1;
3510+
unsigned int j = 2 * i + 1;
35063511

35073512
if (j >= n)
35083513
break;

0 commit comments

Comments
 (0)
0