diff --git a/src/com/android/providers/downloads/DownloadProvider.java b/src/com/android/providers/downloads/DownloadProvider.java
index ac89f25..561b5e4 100644
--- a/src/com/android/providers/downloads/DownloadProvider.java
+++ b/src/com/android/providers/downloads/DownloadProvider.java
@@ -467,13 +467,26 @@
         final SQLiteDatabase db = mOpenHelper.getReadableDatabase();
         final Cursor cursor = db.query(DB_TABLE, new String[] {
                 Downloads.Impl._ID, Constants.UID }, null, null, null, null, null);
+        final ArrayList<Long> idsToDelete = new ArrayList<>();
         try {
             while (cursor.moveToNext()) {
-                grantAllDownloadsPermission(cursor.getLong(0), cursor.getInt(1));
+                final long downloadId = cursor.getLong(0);
+                final int uid = cursor.getInt(1);
+                final String ownerPackage = getPackageForUid(uid);
+                if (ownerPackage == null) {
+                    idsToDelete.add(downloadId);
+                } else {
+                    grantAllDownloadsPermission(ownerPackage, downloadId);
+                }
             }
         } finally {
             cursor.close();
         }
+        if (idsToDelete.size() > 0) {
+            Log.i(Constants.TAG,
+                    "Deleting downloads with ids " + idsToDelete + " as owner package is missing");
+            deleteDownloadsWithIds(idsToDelete);
+        }
 
         // start the DownloadService class. don't wait for the 1st download to be issued.
         // saves us by getting some initialization code in DownloadService out of the way.
@@ -482,6 +495,19 @@
         return true;
     }
 
+    private void deleteDownloadsWithIds(ArrayList<Long> downloadIds) {
+        final int N = downloadIds.size();
+        if (N == 0) {
+            return;
+        }
+        final StringBuilder queryBuilder = new StringBuilder(Downloads.Impl._ID + " in (");
+        for (int i = 0; i < N; i++) {
+            queryBuilder.append(downloadIds.get(i));
+            queryBuilder.append((i == N - 1) ? ")" : ",");
+        }
+        delete(Downloads.Impl.ALL_DOWNLOADS_CONTENT_URI, queryBuilder.toString(), null);
+    }
+
     /**
      * Returns the content-provider-style MIME types of the various
      * types accessible through this content provider.
@@ -700,7 +726,13 @@
         }
 
         insertRequestHeaders(db, rowID, values);
-        grantAllDownloadsPermission(rowID, Binder.getCallingUid());
+
+        final String callingPackage = getPackageForUid(Binder.getCallingUid());
+        if (callingPackage == null) {
+            Log.e(Constants.TAG, "Package does not exist for calling uid");
+            return null;
+        }
+        grantAllDownloadsPermission(callingPackage, rowID);
         notifyContentChanged(uri, match);
 
         // Always start service to handle notifications and/or scanning
@@ -710,6 +742,15 @@
         return ContentUris.withAppendedId(Downloads.Impl.CONTENT_URI, rowID);
     }
 
+    private String getPackageForUid(int uid) {
+        String[] packages = getContext().getPackageManager().getPackagesForUid(uid);
+        if (packages == null || packages.length == 0) {
+            return null;
+        }
+        // For permission related purposes, any package belonging to the given uid should work.
+        return packages[0];
+    }
+
     /**
      * Check that the file URI provided for DESTINATION_FILE_URI is valid.
      */
@@ -1432,14 +1473,9 @@
         }
     }
 
-    private void grantAllDownloadsPermission(long id, int uid) {
-        final String[] packageNames = getContext().getPackageManager().getPackagesForUid(uid);
-        if (packageNames == null || packageNames.length == 0) return;
-
-        // We only need to grant to the first package, since the
-        // platform internally tracks based on UIDs
+    private void grantAllDownloadsPermission(String toPackage, long id) {
         final Uri uri = ContentUris.withAppendedId(Downloads.Impl.ALL_DOWNLOADS_CONTENT_URI, id);
-        getContext().grantUriPermission(packageNames[0], uri,
+        getContext().grantUriPermission(toPackage, uri,
                 Intent.FLAG_GRANT_READ_URI_PERMISSION | Intent.FLAG_GRANT_WRITE_URI_PERMISSION);
     }