Postgres 9.5 deadlock with many updates on a table + many "select for update" on another table
There is no deterministic ORDER BY in:
SELECT FROM * machines FOR UPDATE;

So multiple transactions might try to obtain row locks in different (arbitrary) order and interlock.
Also, why would you lock the whole table machines for a single update in magictools? If it's indeed a single UPDATE on magictools per transaction, there is no need to lock rows machines manually at all. Just drop the command. (If there are multiple, then your question is lacking.)
If there is a good reason to lock many or all rows in machines, either do it in deterministic order, like:
SELECT FROM * machines ORDER BY id FOR UPDATE;

Or lock the whole table instead, that's also cheaper:
LOCK TABLE machines IN SHARE MODE;

SHARE MODE is enough for the FK case you have. There is even an example in the manual suggesting as much.
Locking the table also disallows INSERT, of course, unlike the row level locks in your example.