This is a surprisingly simple scenario leading to a (to me) surprising deadlock. Since I'm not an expert on InnoDB I have already tried other ways to find out whether it is a bug (see https://dba.stackexchange.com/questions/216450/is-this-surprising-deadlock-reasonable-or-a-mariadb-bug), but unfortunately didn't get any helpful responses, so I'm filing it now.

Here is the setup. The isolation level is left at its default (REPEATABLE_READ):

create database deadlock;
use deadlock;
create table foo(id int primary key) engine=InnoDB;
insert into foo values (10);

Now we can start. Let's open two connections A and B to the database.

-- Connection A
begin;
select * from foo for update;

-- Connection B
begin;
select * from foo for update;

At this point, the select issued by B is waiting. This is as expected because A is holding the relevant locks. Note that the StackExchange question used "delete from foo;" instead in both transactions - it makes no difference to the result, but a select seems easier to analyze.

-- Connection A
insert into foo values (9);

And at this point, mariadb kills the waiting query of B due to a deadlock. This is very surprising to me, because it would mean that B has already managed to acquire some locks.

As an additional point of information, if you use the id 11 instead of 9 in the last statement, there is no deadlock.

This test is a simplification of a production scenario where this deadlock kept occurring - there was a transaction that first deleted "invalid" records before inserting a new one. Whether a record was "invalid" was determined in a way that did not use an index, so the entire table had to be scanned. I did not understand how the deadlock could occur, since my mental model was that the delete would essentially get an exclusive lock on everything relevant in the table, so a second transaction running the same queries would have to wait before being able to acquire any locks, and thus could not possibly contribute to a deadlock.