BUG #13523: Unexplained deadlocks (possible race condition)

The following bug has been logged on the website:

Bug reference: 13523
Logged by: Jack Douglas
Email address: jack(at)douglastechnology(dot)co(dot)uk
PostgreSQL version: 9.4.3
Operating system: Debian Jessie
Description:

Hi

I'm getting intermittent (but easily reproducible) deadlocks showing in my
error log, for example:

2015-07-28 16:46:19 BST ERROR: deadlock detected
2015-07-28 16:46:19 BST DETAIL: Process 9394 waits for ExclusiveLock on
relation 65605 of database 12141; blocked by process 9393.
Process 9393 waits for ExclusiveLock on relation 65605 of database
12141; blocked by process 9394.
Process 9394: select f_test('blah')
Process 9393: select f_test('blah')
2015-07-28 16:46:19 BST HINT: See server log for query details.
2015-07-28 16:46:19 BST CONTEXT: SQL function "f_test" statement 1
2015-07-28 16:46:19 BST STATEMENT: select f_test('blah')

The above is from a minimal test case I've attempted to create rather than
my production code. The test case is as follows:

create table test( id serial primary key, val text );

create function f_test(v text) returns integer language sql security definer
set search_path = postgres,pg_temp as $$
lock test in exclusive mode;
insert into test(val) select v where not exists(select * from test where
val=v);
select id from test where val=v;
$$;

then from two bash sessions simultaneously:

for i in {1..1000}; do psql postgres postgres -c "select f_test('blah')";
done

This produces a handful of deadlocks on my server, however using a VM on a
laptop another postgres user said he got far more.

More detail is on the question I posted at DBA.SE (and it's probably easier
to read the code there:

http://dba.stackexchange.com/q/108290/1396

Kind regards
Jack