Multiple SELECT ... FOR UPDATE with a delayed INSERT INTO

I am having an issue with SELECT ... FOR UPDATE and INSERT INTO statements on separate connections deadlocking.

Given an empty table tblFoo with the primary key id, consider the following pseudocode:

function locate(array values) {

    BEGIN TRANSACTION;

    rows = SELECT * FROM tblFoo WHERE id IN values FOR UPDATE;

    if (rows is empty) {
        sleep(10); // i.e., do some stuff
        rows = INSERT INTO tblFoo (id) VALUES values;
    }

    COMMIT;

    return rows;
}

On process A @ t=0: return locate([1,2,3]);

On process B @ t=1: return locate([1]);

My expectation is that process 1 would gap lock rows with ids 1, 2, 3 which blocks process B at the SELECT ... FOR UPDATE until process A's transaction is committed. Once committed, process B gets unblocked and returns the row with id 1 which was just inserted by process A.

The observed behavior is that a deadlock is encountered, causing process A to roll back and process B inserts a row with id 1.

Can anyone help me understand why MySQL is behaving this way?

I am using innoDB with MySQL version 5.5.

Edit: The following is the table structure

CREATE TABLE `tblFoo` (
    `id` INT(11) NOT NULL,
    PRIMARY KEY (`id`)
)
COLLATE='utf8mb4_unicode_ci'
ENGINE=InnoDB
;

Edit 2: The following is the innoDB status detailing the deadlock

------------------------
LATEST DETECTED DEADLOCK
------------------------
161205 15:55:50
*** (1) TRANSACTION:
TRANSACTION 32A3E743A, ACTIVE 3 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 4 lock struct(s), heap size 1248, 2 row lock(s)
MySQL thread id 12243323, OS thread handle 0x7fd7dd47f700, query id 4713227035 localhost root update
INSERT INTO test.tblFoo (id) VALUES (1)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 1556528 n bits 72 index `PRIMARY` of table `test`.`tblFoo` trx id 32A3E743A lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 4 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 80000002; asc     ;;
 1: len 6; hex 00032a3e5f6b; asc   *>_k;;
 2: len 7; hex b30017d06b0110; asc     k  ;;

*** (2) TRANSACTION:
TRANSACTION 32A3E5FD3, ACTIVE 5 sec inserting
mysql tables in use 1, locked 1
4 lock struct(s), heap size 1248, 5 row lock(s)
MySQL thread id 12243319, OS thread handle 0x7fd7f0097700, query id 4713230393 localhost root update
INSERT INTO test.tblFoo (id) VALUES (1),(2),(3)
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 1556528 n bits 72 index `PRIMARY` of table `test`.`tblFoo` trx id 32A3E5FD3 lock_mode X
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
 0: len 8; hex 73757072656d756d; asc supremum;;

Record lock, heap no 2 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 80000005; asc     ;;
 1: len 6; hex 00032a38e424; asc   *8 $;;
 2: len 7; hex cc001c166a0110; asc     j  ;;

Record lock, heap no 4 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 80000002; asc     ;;
 1: len 6; hex 00032a3e5f6b; asc   *>_k;;
 2: len 7; hex b30017d06b0110; asc     k  ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 1556528 n bits 72 index `PRIMARY` of table `test`.`tblFoo` trx id 32A3E5FD3 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 4 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 80000002; asc     ;;
 1: len 6; hex 00032a3e5f6b; asc   *>_k;;
 2: len 7; hex b30017d06b0110; asc     k  ;;

*** WE ROLL BACK TRANSACTION (2)

Solution

I think what is happening is, that you start 2 transactions. Both get a "select ... for update" on the same table. You would expect the second transaction to wait before the update. But from the docs https://dev.mysql.com/doc/refman/5.7/en/innodb-locking-reads.html it sounds like it will not (and this is the behaviour you see). So both "selects ... for update" block each other, leaving you with a deadlock.