Debian – Why won’t MariaDB start after upgrade (NO_NEW_PRIVILEGES)

After upgrade of my debian(testing, jessie to stretch) server on DigitalOcean, MariaDB won't start with service mariadb start.

I tried to purge all mariadb-* and mysql-* packages, delete configs and data, and reinstall them, but mariadb-server-10.1.21-5 refuses to be configured:

Setting up mariadb-server-10.1 (10.1.21-5) ...
Job for mariadb.service failed because the control process exited with error code.
See "systemctl status mariadb.service" and "journalctl -xe" for details.
invoke-rc.d: initscript mysql, action "start" failed.
● mariadb.service - MariaDB database server
   Loaded: loaded (/lib/systemd/system/mariadb.service; enabled; vendor preset: enabled)
   Active: failed (Result: exit-code) since Thu 2017-02-09 21:25:27 CET; 10ms ago
  Process: 1696 ExecStart=/usr/sbin/mysqld $MYSQLD_OPTS $_WSREP_NEW_CLUSTER $_WSREP_START_POSITION (code=exited, status=227/NO_NEW_PRIVILEGES)
  Process: 1589 ExecStartPre=/bin/sh -c [ ! -e /usr/bin/galera_recovery ] && VAR= ||   VAR=`/usr/bin/galera_recovery`; [ $? -eq 0 ]   && systemctl set-environment _WSREP_START_POSITION=$VAR || exit 1 (code=exited, status=0/SUCCESS)
  Process: 1584 ExecStartPre=/bin/sh -c systemctl unset-environment _WSREP_START_POSITION (code=exited, status=0/SUCCESS)
  Process: 1582 ExecStartPre=/usr/bin/install -m 755 -o mysql -g root -d /var/run/mysqld (code=exited, status=0/SUCCESS)
 Main PID: 1696 (code=exited, status=227/NO_NEW_PRIVILEGES)

Feb 09 21:25:27 cddssh systemd[1]: Starting MariaDB database server...
Feb 09 21:25:27 cddssh systemd[1696]: mariadb.service: Failed at step NO_NEW_PRIVILEGES spawning /usr/sbin/mysqld: Invalid argument
Feb 09 21:25:27 cddssh systemd[1]: mariadb.service: Main process exited, code=exited, status=227/NO_NEW_PRIVILEGES
Feb 09 21:25:27 cddssh systemd[1]: Failed to start MariaDB database server.
Feb 09 21:25:27 cddssh systemd[1]: mariadb.service: Unit entered failed state.
Feb 09 21:25:27 cddssh systemd[1]: mariadb.service: Failed with result 'exit-code'.
dpkg: error processing package mariadb-server-10.1 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mariadb-server:
 mariadb-server depends on mariadb-server-10.1 (>= 10.1.21-5); however:
  Package mariadb-server-10.1 is not configured yet.

dpkg: error processing package mariadb-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mariadb-server-10.1
 mariadb-server
E: Sub-process /usr/bin/dpkg returned an error code (1)

this is the output of journalctl -xe after I try to start the service:

Feb 09 05:10:52 cddssh systemd[1]: mariadb.service: Failed to set invocation ID on control group /system.slice/mariadb.service, ignoring: Operation not supported
Feb 09 05:10:52 cddssh systemd[1]: Starting MariaDB database server...
-- Subject: Unit mariadb.service has begun start-up
-- Defined-By: systemd
-- Support: https://www.debian.org/support
--
-- Unit mariadb.service has begun starting up.
Feb 09 05:10:52 cddssh systemd[7114]: mariadb.service: Failed at step NO_NEW_PRIVILEGES spawning /usr/sbin/mysqld: Invalid argument
-- Subject: Process /usr/sbin/mysqld could not be executed
-- Defined-By: systemd
-- Support: https://www.debian.org/support
--
-- The process /usr/sbin/mysqld could not be executed and failed.
--
-- The error number returned by this process is 22.
Feb 09 05:10:52 cddssh systemd[1]: mariadb.service: Main process exited, code=exited, status=227/NO_NEW_PRIVILEGES
Feb 09 05:10:52 cddssh systemd[1]: Failed to start MariaDB database server.
-- Subject: Unit mariadb.service has failed
-- Defined-By: systemd
-- Support: https://www.debian.org/support
--
-- Unit mariadb.service has failed.
--
-- The result is failed.
Feb 09 05:10:52 cddssh systemd[1]: mariadb.service: Unit entered failed state.
Feb 09 05:10:52 cddssh systemd[1]: mariadb.service: Failed with result 'exit-code'.

mysql error log has no errors/warnings.

I can start the mysqld binary just fine by itself.

I tried to follow instructions at https://mariadb.com/kb/en/mariadb/upgrade-10116maria-1jessie-broke-system/ but then I get error

mariadb.service: Failed at step NO_NEW_PRIVILEGES spawning /usr/sbin/mysqld: Invalid argument

It seems it has something to do with selinux as I found these lines in /lib/systemd/system/mariadb.service

# Doesn't yet work properly with SELinux enabled
# NoNewPrivileges=true

Someone had a very similiar question on superuser but I do not understand what he did to solve it: https://superuser.com/questions/1103321/mariadb-server-broken-after-failed-package-update