Sachverhalt:
A.
A._ (Staatsangehöriger von Äthiopien) reiste am 4. Juli 2012 in die Schweiz ein. Ein erstes Asylgesuch wies das Staatssekretariat für Migration (SEM) am 17. Juni 2014 ab. Die Beschwerde dagegen an das Bundesverwaltungsgericht war erfolglos. Da A._ untergetaucht war, konnte die Ausreisefrist nicht gewahrt werden. Auch das zweite Asylgesuch von A._ war ohne Erfolg; dieser liess die Ausreisefrist wiederum verstreichen und zeigte keinen Ausreisewillen. Erfolglos war ebenfalls das Gesuch um Erteilung einer Aufenthaltsbewilligung aufgrund eines schwerwiegenden persönlichen Härtefalls. Ende Oktober/anfangs November 2019 tauchte A._ wiederum unter, nachdem er von einer äthiopischen Identifizierungskommission als Äthiopier anerkannt worden war und Ersatzreisedokumente vorhanden waren. Am 5. Februar 2020 wurde er im Rahmen eines Dublin-Verfahrens von Deutschland an die Schweiz rücküberstellt. Am folgenden Tag ordnete das Migrationsamt eine dreimonatige Ausschaffungshaft an. Die Beschwerde dagegen wurde abgewiesen. A._ weigerte sich am 28. Februar 2020 allerdings, einen Flug in seine Heimat anzutreten. Eine begleitete Ausschaffung konnte am 20. März 2020 wegen der Corona-Pandemie nicht mehr stattfinden. In der Folge wurde die Haft erstmals am 4. Mai und ein weiteres Mal bis am 4. November 2020 verlängert. Letztinstanzlich hiess das Bundesgericht eine Beschwerde dagegen gut (Urteil 2C_768/2020 vom 21. Oktober 2020).
B.
A._ reichte am 11. September 2020 sein drittes Asylgesuch ein. Das SEM trat am 18. September 2020 darauf nicht ein, wies A._ erneut aus der Schweiz weg und beauftragte das Migrationsamt mit dem Vollzug. Die gegen den Asylentscheid erhobene Beschwerde wies das Bundesverwaltungsgericht am 26. Oktober 2020 (Urteil E-4809/2020) ab, hielt aber präzisierend fest, dass das SEM die Beschwerde materiell behandelt und somit das Gesuch abgewiesen habe (E. 8). Am gleichen Tag ordnete das Migrationsamt gegen A._ Durchsetzungshaft, eventualiter Vorbereitungshaft mit anschliessender Durchsetzungshaft an. Das Haftgericht des Kantons Solothurn genehmigte nach mündlicher Anhörung (27. Oktober 2020) die Vorbereitungshaft vom 23. bis 26. Oktober und die daran anschliessende Durchsetzungshaft bis 25. November 2020. Die Beschwerde dagegen beim Verwaltungsgericht des Kantons Solothurn war erfolglos.
C.
Vor Bundesgericht beantragt A._ am 23. November 2020, Ziff. 1 des Urteils des Verwaltungsgerichts Solothurn vom 18. November 2020 aufzuheben, ihn unverzüglich aus der Haft zu entlassen, festzustellen, dass die Vorbereitungshaft vom 23. Oktober 2020 bis 26. Oktober 2020 unrechtmässig gewesen sei, eventuell den Fall zur Neubeurteilung an die Vorinstanz zurückzuweisen, subeventuell festzustellen, dass die Durchsetzungshaft rechtswidrig und unverhältnismässig sei. Für das bundesgerichtliche Verfahren beantragt er unentgeltliche Rechtspflege.
Das Migrationsamt, das Haftgericht und das Verwaltungsgericht des Kantons Solothurn beantragen vernehmlassungsweise die Abweisung der Beschwerde. Das SEM führt in seinem Amtsbericht zu den Ausreisemöglichkeiten aus, dass eine zwangsweise Rückführung aufgrund der Rückkehrvereinbarung zwischen Äthiopien und der Schweiz zulässig, aber im konkreten Fall wegen der COVID-19-Pandemie gescheitert sei. Zur Zeit lägen keine Anzeichen vor, dass die COVID-19-Pandemie oder der Konflikt in der äthiopischen Tigray-Region im Norden Auswirkungen auf die Rückkehrvereinbarung bzw. -zusammenarbeit habe. Zudem lägen keine technischen oder juristischen Hindernisse für eine Rückkehr vor.
D.
Am 26. November 2020 ist der Beschwerdeführer aus der Haft entlassen worden. Er hält trotzdem an seiner Beschwerde fest. Es bestünde nach wie vor ein Feststellungsinteresse. Die Haft stelle eine Verletzung von Art. 5 EMRK dar.

Erwägungen:
1.
1.1. Gegen den kantonal letztinstanzlichen Entscheid über eine Zwangsmassnahme im Ausländerrecht kann die betroffene Person mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht gelangen (Art. 82 i.V.m. <ref-law>; Urteil 2C_408/2020 vom 21. Juli 2020 E. 1.1). Wegen des mit der Anordnung ausländerrechtlicher Administrativhaft verbundenen schweren Eingriffs in die persönliche Freiheit kommt dem entsprechenden Freiheitsentzug eigenständige Bedeutung zu; die Haft erscheint nicht als bloss untergeordnete Vollzugsmassnahme zur Wegweisung, weshalb der Ausschlussgrund von <ref-law> der Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht entgegensteht (<ref-ruling> E. 1.1.3 S. 139 f.; <ref-ruling> E. 5.5 S. 101 f.; Urteil 2C_408/2020 vom 21. Juli 2020 E. 1.1).
1.2.
1.2.1. Das Bundesgericht verzichtet ausnahmsweise im Rahmen von <ref-law> auf das Erfordernis des aktuellen praktischen Interesses, wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen deren grundsätzlicher Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1; <ref-ruling> E. 1.1 S. 103; <ref-ruling> E. 1.1 S. 81). Das Bundesgericht tritt - trotz Haftentlassung oder eines Verlängerungsentscheids, welcher den ursprünglich angefochtenen Haftentscheid ablöst (vgl. <ref-ruling> E. 1 S. 208 ff.) - auf Beschwerden gegen die Genehmigung der ausländerrechtlichen Festhaltung durch den Haftrichter bzw. den entsprechenden kantonalen Rechtsmittelentscheid ein, wenn der Betroffene rechtsgenügend begründet (<ref-law>) und in vertretbarer Weise ("griefs défendables") die Verletzung einer Garantie der EMRK rügt (vgl. das Urteil 2C_599/2020 vom 24. November 2020 E. 3.2).
1.2.2. Die strittigen freiheitsentziehenden ausländerrechtlichen Zwangsmassnahmen fallen in den Anwendungsbereich von Art. 5 EMRK (vgl. das EGMR-Urteil Jusic gegen Schweiz vom 2. Dezember 2010 [Nr. 4691/06], §§ 67 ff.). Der Beschwerdeführer macht im vorliegenden Verfahren inhaltlich in vertretbarer Weise geltend, unter Verletzung von Art. 5 Ziff. 1 EMRK in Haft gesetzt und belassen worden zu sein. An der Beurteilung der Konventionskonformität seiner Festhaltung hat er ein fortbestehendes Interesse. Da neben der Beschwerdelegitimation auch alle weiteren Prozessvoraussetzungen gegeben sind, ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten einzutreten (vgl. Art. 42, Art. 100 Abs. 1 i.V.m. <ref-law>).
2.
2.1. Der Beschwerdeführer macht geltend, dass die Haftvoraussetzungen der Vorbereitungs- und der Durchsetzungshaft nicht gegeben gewesen seien, die Haft selbst unverhältnismässig und er in Verletzung von <ref-law> (SR 142.20; bis 31. Dezember 2019: AuG [AS 2007 5437]) im Untersuchungsgefängnis Solothurn untergebracht gewesen sei; zudem habe ihm die Vorinstanz das rechtliche Gehör verweigert.
2.2. Nach <ref-law> kann eine Person, die weder eine Kurzaufenthalts-, Aufenthalts- noch Niederlassungsbewilligung besitzt, unter bestimmten Voraussetzungen in Vorbereitungshaft genommen werden, um u.a. die Durchführung eines Wegweisungsverfahrens sicherzustellen. Wie der Gesetzeswortlaut unmissverständlich festhält (Art. 75 Abs. 1 Ingress i.f. AIG), ist die Vorbereitungshaft zudem nur während der Vorbereitung des Entscheides über die Aufenthaltsberechtigung zulässig; der erstinstanzliche Entscheid ist somit noch nicht ergangen; Entscheide, welche durch ein Rechtsmittel ausgelöst werden, bereiten den Entscheid nicht vor, sondern überprüfen diesen (vgl. <ref-ruling> E. 2b S. 380; Urteil 2C_218/2013 vom 26. März 2013 E. 3.2.4).
Am 18. September 2020 hat das SEM das Gesuch materiell behandelt und abgewiesen (siehe oben Sachverhalt B.), die Wegweisung verfügt sowie das Migrationsamt des Kantons Solothurn mit dem Vollzug beauftragt. Das Bundesverwaltungsgericht entschied am 26. Oktober 2020 als Rechtsmittelbehörde. Am gleichen Tag, also am 26. Oktober 2020, ordnete das Migrationsamt eventualiter die Vorbereitungshaft mit anschliessender Durchsetzungshaft an. Das Haftgericht genehmigt am 27. Oktober 2020 u.a. die Vorbereitungshaft vom 23. bis 26. Oktober 2020. Als die kantonalen Behörden die Vorbereitungshaft verfügten, lag bereits ein erstinstanzlicher Entscheid vor. Die Anordnung einer solchen ist damit nach <ref-law> nicht mehr möglich und dementsprechend bundesrechtswidrig.
2.3.
2.3.1. Hat eine Person ihre Pflicht zur Ausreise aus der Schweiz innerhalb der ihr angesetzten Frist nicht erfüllt und kann u.a. die rechtskräftige Weg- oder Ausweisung aufgrund ihres persönlichen Verhaltens nicht vollzogen werden, so kann sie, um der Ausreisepflicht Nachachtung zu verschaffen, in Haft genommen werden, sofern die Anordnung der Ausschaffungshaft nicht zulässig ist und eine andere mildere Massnahme nicht zum Ziel führt (<ref-law>).
Zweck der Durchsetzungshaft ist es, die ausreisepflichtige Person in jenen Fällen zu einer Verhaltensänderung zu bewegen, in denen nach Ablauf der Ausreisefrist der Vollzug der rechtskräftig gegen sie angeordneten Weg- oder Ausweisung - trotz entsprechender behördlicher Bemühungen - ohne ihre Kooperation nicht (mehr) möglich erscheint. Der damit verbundene Freiheitsentzug stützt sich auf Art. 5 Ziff. 1 lit. f EMRK (Haft zur Sicherung eines schwebenden Ausweisungsverfahrens) und dient in diesem Rahmen der Erzwingung einer durch das Gesetz vorgeschriebenen Verpflichtung (Art. 5 Ziff. 1 lit. b EMRK). Die Durchsetzungshaft bildet das letzte Mittel, wenn und soweit keine andere Massnahme (mehr) zum Ziel führt, den illegal anwesenden Ausländer auch gegen seinen Willen in seine Heimat verbringen zu können. Sie darf - zusammen mit der bereits verbüssten Ausschaffungs- bzw. Vorbereitungshaft - maximal 18 Monate dauern (Art. 78 Abs. 2 i.V.m. <ref-law>), muss aber in jedem Fall verhältnismässig sein. Innerhalb dieser Höchstdauer ist jeweils aufgrund der Umstände im Einzelfall zu prüfen, ob die ausländerrechtliche Festhaltung insgesamt (noch) geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot verstösst (vgl. <ref-ruling> E. 2.1 mit weiteren Hinweisen).
2.3.2. Voraussetzung der Durchsetzungshaft bildet u.a. das Vorliegen einer rechtskräftigen Weg- oder Ausweisung. Weggewiesene Personen müssen die Schweiz selbständig in der angesetzten Frist (vgl. Art. 64 und Art. 64d AIG bzw. <ref-law> [SR 142.31]) verlassen. Darauf nimmt <ref-law> Bezug, wenn für die Durchsetzungshaft vorausgesetzt wird, dass eine Person ihre Pflicht zur Ausreise aus der Schweiz innerhalb der angesetzten Frist nicht erfüllt. Das Urteil des Bundesverwaltungsgerichts ist am 26. Oktober 2020 ergangen. Damit lag erst zu diesem Zeitpunkt ein rechtskräftiger Entscheid vor. Dessen Versand erfolgte am 26. Oktober 2020, weshalb der rechtskräftige Entscheid frühestens am 27. Oktober 2020 dem Beschwerdeführer zugestellt wurde. Bereits am 26. Oktober 2020 verfügte das Migrationsamt und genehmigte am 27. Oktober 2020 das Haftgericht die Durchsetzungshaft. Der Beschwerdeführer konnte somit eine selbständige Ausreise gar nicht wahrnehmen. Die Vorinstanz geht indes davon aus, dass mit dem rechtskräftigen Wegweisungsentscheid die Ausreisefrist abgelaufen sei. Dies ist unzutreffend. Die Ausreisefrist kann nicht bereits verstrichen sein, wenn der Wegweisungsentscheid rechtskräftig wird (vgl. ANDREAS ZÜND, in: Spescha/Zünd/Bolzli/ Hruschka/de Weck, Migrationsrecht. Kommentar, 5. Aufl. 2019, N. 5 zu <ref-law>), andernfalls Sinn und Zweck von <ref-law> unterlaufen würde. Im Übrigen kennt <ref-law> keine <ref-law> entsprechende Regelung, wonach die Wegweisung unter bestimmten Voraussetzungen sofort vollstreckbar ist. Insofern war die Durchsetzungshaft vor dem 28. Oktober 2020 unzulässig. Ob die kantonalen Behörden allenfalls aufgrund einer gegenüber dem Urteil 2C_768/2020 geänderten faktischen Lage eine erneute Ausschaffungshaft hätten anordnen können, ist hier mangels aktuellen Interesses nicht mehr zu prüfen.
2.4.
2.4.1. Nach <ref-law> ist die administrative Haft - entsprechend Art. 16 Abs. 1 Satz 1 der auch für die Schweiz geltenden Richtlinie 2008/115/EG (Rückführungsrichtline) - in einer speziellen, nur zu diesem Zweck vorgesehenen Vollzugsanstalt zu vollziehen (Ausschaffungsgefängnis). Sie kann bloss dann - in Ausnahmefällen - in ordentlichen Haftanstalten vollzogen werden, sofern ein administrativ anderweitig nicht bewältigbarer wichtiger Grund für dieses Vorgehen vorliegt sowie die Trennung von den anderen Häftlingen durch eine eigenständige Abteilung sichergestellt bleibt (<ref-ruling> E. 4-6 S. 208 ff.). Es muss sich folglich um absolute Einzelfälle handeln (<ref-ruling> E. 7 S. 215 f.). Zudem ist der Grund für diese Ausnahmefälle in der Haftverfügung sachgerecht zu begründen, damit der Haftrichter die angegebenen Gründe im Hinblick auf die Zulässigkeit der Haft und der nach Art. 16 der Rückführungsrichtlinie erforderlichen Haftbedingungen überprüfen kann (vgl. <ref-law>; <ref-ruling> E. 8 S. 216 f.).
2.4.2. Bereits in einem früheren Entscheid den Kanton Solothurn betreffend hat das Bundesgericht festgehalten, dass das Untersuchungsgefängnis Solothurn für den Vollzug der ausländerrechtlichen Administrativhaft ungeeignet im Sinne von <ref-law> ist, weshalb eine ausländische Person nur in begründeten Ausnahmefällen von äusserst beschränkter Zeitdauer im Untersuchungsgefängnis Solothurn untergebracht werden darf (Urteil 2C_844/2020 vom 30. Oktober 2020 E. 6.2).
Der Beschwerdeführer befand sich vom 27. Oktober bis zum 15. November 2020, dem vorgesehenen Tag des Rückfluges, im Untersuchungsgefängnis Solothurn. Der Beschwerdeführer sass somit während rund drei Wochen in einer nicht <ref-law> konformen Hafteinrichtung. Damit wird die kurze Dauer von wenigen Stunden oder Tagen (<ref-ruling> E. 6.2.2 S. 214) massiv überschritten. Abgesehen davon fehlt auch eine spezifische Begründung, weshalb der Beschwerdeführer seine administrative Haft in einer allgemeinen Haftanstalt anstelle einer Spezialanstalt verbringen musste (Urteil 2C_844/2020 vom 30. Oktober 2020 E. 6.2.3).
2.5. Ist bereits die Vorbereitungs- und Durchsetzungshaft sowie die Unterbringung des Beschwerdeführers im Untersuchungsgefängnis Solothurn bundesrechtswidrig und demzufolge die Beschwerde gutzuheissen, so kann offengelassen werden, ob die Vorinstanz auch das rechtliche Gehör verletzt hat.
3.
Die Beschwerde ist begründet und insofern gutzuheissen, als festgestellt wird, dass die Vorinstanz zu Unrecht eine Vorbereitungs- und Durchsetzungshaft als zulässig erachtet hat und der Beschwerdeführer einen Teil der administrativen Haft bundesrechtswidrig im Untersuchungsgefängnis Solothurn verbringen musste. Dem Verfahrensausgang entsprechend sind keine Kosten für das bundesgerichtliche Verfahren zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren entsprechend der angemessenen Honorarnote zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Das Gesuch um unentgeltliche Rechtspflege vor Bundesgericht wird damit gegenstandslos. Die Sache wird an die Vorinstanz zur Regelung der Entschädigung der Rechtsvertreterin im vorinstanzlichen Verfahren zurückgewiesen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird in dem Sinne gutgeheissen, als festgestellt wird, dass die Vorinstanz zu Unrecht eine Vorbereitungshaft und vor dem 28. Oktober 2020 eine Durchsetzungshaft als zulässig erachtet hat und der Beschwerdeführer bundesrechtswidrig einen Teil der administrativen Haft im Untersuchungsgefängnis Solothurn verbringen musste.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2408.80 zu entschädigen.
4.
Die Sache wird zur Neuverlegung der Entschädigungsfolgen an die Vorinstanz zurückgewiesen.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 24. März 2021
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Errass