Received-SPF: PermError (protection.outlook.com: domain of
 blackducksoftware.com used an invalid SPF mechanism)
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an
 infinite loop
To: Tom Lane <tgl@sss.pgh.pa.us>, Thomas Munro <thomas.munro@enterprisedb.com>
CC: Andres Freund <andres@anarazel.de>, Tomas Vondra
	<tomas.vondra@2ndquadrant.com>, PostgreSQL Bugs <pgsql-bugs@postgresql.org>
References: <20171127185700.1470.20362@wrigleys.postgresql.org>
 <fd924fd9-8f27-d945-04a9-57b503896107@2ndquadrant.com>
 <7a22f496-92b5-d199-984e-183965918304@blackducksoftware.com>
 <20171127221041.mezzysc4zcfsqkyc@alap3.anarazel.de>
 <CAEepm=3SC9zYLKhvtZbsnwf9vEpi96WCGz1rdGLofuzBau=fqA@mail.gmail.com>
 <17357.1511841783@sss.pgh.pa.us>
From: "Todd A. Cook" <tcook@blackducksoftware.com>
Message-ID: <9cd29b81-7ba1-91a2-f491-9014f4ac87e6@blackducksoftware.com>
Date: Tue, 5 Dec 2017 16:23:02 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.4.0
MIME-Version: 1.0
In-Reply-To: <17357.1511841783@sss.pgh.pa.us>
Content-Type: text/plain; charset="utf-8"; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Dec 2017 21:23:02.9103
 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: 
 2423b037-de30-468e-b024-08d53c265e34
X-MS-Exchange-CrossTenant-Id: a8cff409-0d9d-48cf-b483-b7442cbeb39d
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: 
 TenantId=a8cff409-0d9d-48cf-b483-b7442cbeb39d;Ip=[192.231.134.1];Helo=[ops-mail01.dc2.lan]
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY1PR10MB0634
List-Id: <pgsql-bugs.lists.postgresql.org>
List-Help: <https://lists.postgresql.org/manage/>
List-Subscribe: <https://lists.postgresql.org/manage/>
List-Post: <mailto:pgsql-bugs@lists.postgresql.org>
List-Owner: <mailto:pgsql-bugs-owner@lists.postgresql.org>
List-Archive: <https://www.postgresql.org/list/pgsql-bugs>
Precedence: bulk

On 11/27/17 23:03, Tom Lane wrote:
> Thomas Munro <thomas.munro@enterprisedb.com> writes:
>> When SH_INSERT tries to insert that final extra value, insertdist
>> keeps exceeding SH_GROW_MAX_DIB (25) no matter how many times we
>> double the size (at least until my computer gives up, somewhere around
>> 11 doublings and 75GB of virtual memory).  If you set SH_GROW_MAX_DIB
>> to 26 then it succeeds, but I guess some other attack could be crafted
>> for that.  What is the theory behind this parameter?
> 
> You beat me to it --- after looking at simplehash.h I'd guessed that
> either the SH_GROW_MAX_DIB or SH_GROW_MAX_MOVE code path was causing
> an infinite loop, but I'd not gotten to determining which one yet.
> 
> I'd ask what's the theory behind SH_GROW_MAX_MOVE, as well.  Neither
> of them are obviously loop-proof.
> 
> Note that the sample data has a lot of collisions:
> 
> regression=# select hashint8(val), count(*) from reproducer group by 1 order by 2 desc;
>    hashint8   | count
> -------------+-------
>     441526644 |  2337
>   -1117776826 |  1221
>   -1202007016 |   935
>   -2068831050 |   620
>    1156644653 |   538
>     553783815 |   510
>     259780770 |   444
>     371047036 |   394
>     915722575 |   359
>   ... etc etc ...
> 
> It's evidently more complicated than just that the code fails with
> more than SH_GROW_MAX_DIB duplicate hashcodes, but I suspect not
> by a lot.  There needs to be a safety valve that prevents letting
> the hash fill factor approach zero, which is what's happening in
> this test case.

FWIW, I can also reproduce the infinite loop with 167834 unique values.

It kinda looks like the problematic collisions arise from masking the
computed hash values; e.g.:

     SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash)
     {
	return hash & tb->sizemask;
     }

(Also FWIW, changing SH_FILLFACTOR to 0.5 (from 0.9) did not help any.)

-- todd