systemd-hostnamed[8553]: /usr/lib/systemd/systemd-hostnamed: error while loading shared libraries: libselinux.so.1: cannot open shared object file: Permission denied

Issue

• systemd-hostnamed fails to start on system boot with an error "error while loading shared libraries: libselinux.so.1: cannot open shared object file: Permission denied".

 Feb 19 18:53:56 localhost systemd-hostnamed[8553]: /usr/lib/systemd/systemd-hostnamed: error while loading shared libraries: libselinux.so.1: cannot open shared object file: Permission denied
 Feb 19 18:53:56 localhost systemd[1]: systemd-hostnamed.service: main process exited, code=exited, status=127/n/a
 Feb 19 18:53:56 localhost systemd[1]: Failed to start Hostname Service.
 Feb 19 18:53:56 localhost systemd[1]: Unit systemd-hostnamed.service entered failed state.
 Feb 19 18:53:56 localhost systemd[1]: systemd-hostnamed.service failed.

• systemd-localed.service fails to start on system boot with the same error.

 Feb 19 18:51:19 localhost systemd[1]: Starting Locale Service...
 Feb 19 18:51:19 localhost systemd-localed[5983]: /usr/lib/systemd/systemd-localed: error while loading shared libraries: libselinux.so.1: cannot open shared object file: Permission denied
 Feb 19 18:51:19 localhost systemd[1]: systemd-localed.service: main process exited, code=exited, status=127/n/a
 Feb 19 18:51:19 localhost systemd[1]: Failed to start Locale Service.
 Feb 19 18:51:19 localhost systemd[1]: Unit systemd-localed.service entered failed state.
 Feb 19 18:51:19 localhost systemd[1]: systemd-localed.service failed.

• Looks like the issue is not just about libselinux.

Feb 19 18:48:17 localhost systemd-sysctl: /usr/lib/systemd/systemd-sysctl: error while loading shared libraries: libgcc_s.so.1: cannot open shared object file: Permission denied
Feb 19 18:48:17 localhost rhel-readonly: hostname: error while loading shared libraries: libnsl.so.1: cannot open shared object file: Permission denied
Feb 19 18:48:20 localhost auditd: /sbin/auditd: error while loading shared libraries: libwrap.so.0: cannot open shared object file: Permission denied
Feb 19 18:48:20 localhost rhel-dmesg: dmesg: error while loading shared libraries: libc.so.6: cannot open shared object file: Permission denied
Feb 19 18:48:21 localhost irqbalance: /usr/sbin/irqbalance: error while loading shared libraries: libcap-ng.so.0: cannot open shared object file: Permission denied
Feb 19 18:48:21 localhost rngd: /sbin/rngd: error while loading shared libraries: libsysfs.so.2: cannot open shared object file: Permission denied
Feb 19 18:48:21 localhost mcelog: /usr/sbin/mcelog: error while loading shared libraries: libc.so.6: cannot open shared object file: Permission denied
Feb 19 18:48:22 localhost systemd-hostnamed: /usr/lib/systemd/systemd-hostnamed: error while loading shared libraries: libselinux.so.1: cannot open shared object file: Permission denied
Feb 19 18:48:34 localhost systemd-localed: /usr/lib/systemd/systemd-localed: error while loading shared libraries: libselinux.so.1: cannot open shared object file: Permission denied
Feb 19 18:48:36 localhost fprintd: /usr/libexec/fprintd: error while loading shared libraries: libfprint.so.0: cannot open shared object file: Permission denied
... skipping ...

$ grep -r error\ while\ loading sosreport-localhost.02308469-20190219185848 | awk '{print $(NF-7)}' | sort | uniq -c
      4 libcap-ng.so.0:
     12 libc.so.6:
     38 libdl.so.2:
      4 libfprint.so.0:
     11 libgcc_s.so.1:
      4 libglib-2.0.so.0:
     39 libnsl.so.1:
      9 libpython2.7.so.1.0:
    100 libselinux.so.1:
      4 libssl.so.10:
      4 libsysfs.so.2:
      4 libtinfo.so.5:
      4 libwrap.so.0: