--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -365,16 +365,17 @@ NS_IMPL_ISUPPORTS(Database
 
 Database::Database()
   : mMainThreadStatements(mMainConn)
   , mMainThreadAsyncStatements(mMainConn)
   , mAsyncThreadStatements(mMainConn)
   , mDBPageSize(0)
   , mDatabaseStatus(nsINavHistoryService::DATABASE_STATUS_OK)
   , mClosed(false)
+  , mShouldConvertIconPayloads(false)
   , mClientsShutdown(new ClientsShutdownBlocker())
   , mConnectionShutdown(new ConnectionShutdownBlocker(this))
   , mMaxUrlLength(0)
   , mCacheObservers(TOPIC_PLACES_INIT_COMPLETE)
 {
   MOZ_ASSERT(!XRE_IsContentProcess(),
              "Cannot instantiate Places in the content process");
   // Attempting to create two instances of the service?
@@ -583,23 +584,41 @@ Database::EnsureConnection()
     rv = EnsureFaviconsDatabaseFile(storage);
     NS_ENSURE_SUCCESS(rv, rv);
 
     // Initialize the database schema.  In case of failure the existing schema is
     // is corrupt or incoherent, thus the database should be replaced.
     bool databaseMigrated = false;
     rv = SetupDatabaseConnection(storage);
     if (NS_SUCCEEDED(rv)) {
-      // Failing to initialize the schema always indicates a corruption.
-      if (NS_FAILED(InitSchema(&databaseMigrated))) {
-        rv = NS_ERROR_FILE_CORRUPTED;
+      // Failing to initialize the schema may indicate a corruption.
+      rv = InitSchema(&databaseMigrated);
+      if (NS_FAILED(rv)) {
+        if (rv == NS_ERROR_STORAGE_BUSY ||
+            rv == NS_ERROR_FILE_IS_LOCKED ||
+            rv == NS_ERROR_FILE_NO_DEVICE_SPACE ||
+            rv == NS_ERROR_OUT_OF_MEMORY) {
+          // The database is not corrupt, though some migration step failed.
+          // This may be caused by concurrent use of sync and async Storage APIs
+          // or by a system issue.
+          // The best we can do is trying again. If it should still fail, Places
+          // won't work properly and will be handled as LOCKED.
+          rv = InitSchema(&databaseMigrated);
+          if (NS_FAILED(rv)) {
+            rv = NS_ERROR_FILE_IS_LOCKED;
+          }
+        } else {
+          rv = NS_ERROR_FILE_CORRUPTED;
+        }
       }
     }
     if (NS_WARN_IF(NS_FAILED(rv))) {
-      mDatabaseStatus = nsINavHistoryService::DATABASE_STATUS_CORRUPT;
+      if (rv != NS_ERROR_FILE_IS_LOCKED) {
+        mDatabaseStatus = nsINavHistoryService::DATABASE_STATUS_CORRUPT;
+      }
       // Some errors may not indicate a database corruption, for those cases we
       // just bail out without throwing away a possibly valid places.sqlite.
       if (rv == NS_ERROR_FILE_CORRUPTED) {
         rv = BackupAndReplaceDatabaseFile(storage);
         NS_ENSURE_SUCCESS(rv, rv);
         // Try to initialize the new database again.
         rv = SetupDatabaseConnection(storage);
         NS_ENSURE_SUCCESS(rv, rv);
@@ -956,16 +975,24 @@ Database::InitSchema(bool* aDatabaseMigr
       *aDatabaseMigrated = true;
 
       if (currentSchemaVersion < 11) {
         // These are versions older than Firefox 4 that are not supported
         // anymore.  In this case it's safer to just replace the database.
         return NS_ERROR_FILE_CORRUPTED;
       }
 
+      auto guard = MakeScopeExit([&]() {
+        // This runs at the end of the migration, regardless of its success.
+        if (mShouldConvertIconPayloads) {
+          mShouldConvertIconPayloads = false;
+          nsFaviconService::ConvertUnsupportedPayloads(mMainConn);
+        }
+      });
+
       // Firefox 4 uses schema version 11.
 
       // Firefox 8 uses schema version 12.
 
       if (currentSchemaVersion < 13) {
         rv = MigrateV13Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
@@ -1124,16 +1151,21 @@ Database::InitSchema(bool* aDatabaseMigr
       if (currentSchemaVersion < 40) {
         rv = MigrateV40Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       // Firefox 58 uses schema version 40.
 
       // Schema Upgrades must add migration code here.
+      // >>> IMPORTANT! <<<
+      // NEVER MIX UP SYNC AND ASYNC EXECUTION IN MIGRATORS, YOU MAY LOCK THE
+      // CONNECTION AND CAUSE FURTHER STEPS TO FAIL.
+      // In case, set a bool and do the async work in the ScopeExit guard just
+      // before the migration steps.
 
       rv = UpdateBookmarkRootTitles();
       // We don't want a broken localization to cause us to think
       // the database is corrupt and needs to be replaced.
       MOZ_ASSERT(NS_SUCCEEDED(rv));
     }
   }
   else {
@@ -2308,18 +2340,19 @@ Database::MigrateV37Up() {
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
     "UPDATE moz_places SET favicon_id = NULL"
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
-  // Start the async conversion
-  nsFaviconService::ConvertUnsupportedPayloads(mMainConn);
+  // The async favicons conversion will happen at the end of the normal schema
+  // migration.
+  mShouldConvertIconPayloads = true;
 
   return NS_OK;
 }
 
 nsresult
 Database::MigrateV38Up()
 {
   MOZ_ASSERT(NS_IsMainThread());

--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -329,16 +329,19 @@ private:
 
   mutable StatementCache mMainThreadStatements;
   mutable AsyncStatementCache mMainThreadAsyncStatements;
   mutable StatementCache mAsyncThreadStatements;
 
   int32_t mDBPageSize;
   uint16_t mDatabaseStatus;
   bool mClosed;
+  // Used to track whether icon payloads should be converted at the end of
+  // schema migration.
+  bool mShouldConvertIconPayloads;
 
   /**
    * Phases for shutting down the Database.
    * See Shutdown.h for further details about the shutdown procedure.
    */
   already_AddRefed<nsIAsyncShutdownClient> GetProfileChangeTeardownPhase();
   already_AddRefed<nsIAsyncShutdownClient> GetProfileBeforeChangePhase();