All are fine, but note that the last two will hardly ever occur in either form. The main point to understand is the difference between the form with 'having' and the form without it. The form with 'having' typically indicates something temporally previous to the action in the accompanying main clause, and the form without 'having' typically indicates something simultaneous (or fairly recent) with the action in the main clause.
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.