Does bending of light due to warping of space violate Fermat's Principle or is it that in the principle light goes in a straight line with respect to space (taking space as the reference) and in Relativity that reference itself is bending and so does the light?
Fermat's principle is a bit more complicated than what you state: it says that in travelling from $A$ to $B$, light will go along the paths that will minimize the time taken to get there - and these may or may not be straight lines. (See e.g. Wikipedia.)
That said, the gravitational lensing of light does not operate quite like that. Since it is in vacuum, Fermat's principle demands that light travel locally in straight lines, which indeed it does: it travels in a null geodesic. However, since spacetime itself is curved, the path appears to bend with respect to the flat-space metric you'd have without the Sun's presence.
Well, needless to say that in curved space, one should use Fermat's principle for a curved space, which for instance is worked out in my Phys.SE answer here. The solutions are geodesics wrt. the optical path length. They satisfy a ray equation. It was shown in my Phys.SE answer here that this ray equation correctly accounts for the bending/deflection of light.