Recovery of preimage of hash function given part of it Suppose $m = m_1 \| m_2$ (concatenation, with $|m_1| = |m_2|$) and $h(m) = s$ (hash). Is it possible to recover the whole preimage $m$ in feasible time with non-negligible probability given $m_1$ (or $m_2$) and $s$? Is there such a guarantee that this can't be done theoretically or provided by concrete schemes such as SHA1/SHA256/SHA512, etc.?
You don't specify how long $m_1$ and $m_2$ are. If $|m_1| = |m_2| &gt; s$, then there is no way to recover $m$ given $s=h(m)$ (or $m_1$ given $m_2$ and $s=h(m_1\|m_2$) simply because there are exponentially many solutions to the equation $h(X)=s$ (resp., $h(X \| m_2) = s$). 

Or are you asking to find any solution, not necessarily the original one? Even in this case, the above property (namely, existence of multiple solutions) can be used to show that solving either of the stated problems is hard if $h$ is collision resistant. In fact, this remains true even if $|m_1|=|m_2|=s$.