Why is the soil on Mars red? Ancient life?

A couple years ago I bought Life by Richard Fortey. He explained that many millions of years of stromatolites building huge towers oxidized* the iron in the soil on Earth, turning it red. That’s a paraphrase. If the soil on Mars is mostly iron and silica, the conventional wisdom, and all the iron is oxidized (?), how did the iron become oxidized without substantial oxygen present at one time? The bulk of the oxygen on Earth is attributed to life, I think.

Mars is red because it’s rusty.

Oh well, that was quick. In case anyone is wondering, this is the crux of it – unless you go with the “oceans and rain” theory:

Darn.