Permalinks appears to have failed

My blog has been up for months, and was working last night As of today, the main blog page and all the posts are ok, but no links work, categories display and link to the correct URL, but nothing is there, calendar links fail, even clicking the title of a displayed post fails. I regenerated the permalinks, and that does not help.

I’m wondering if mod-rewrite has failed on the host server, but don’t know how to quickly check that.