diff -u b/core/includes/update.inc b/core/includes/update.inc
--- b/core/includes/update.inc
+++ b/core/includes/update.inc
@@ -1602,15 +1602,24 @@
  * Replace permissions during update.
  *
  * This function can replace one permission to several or even delete an old
- * one.
+ * one. It also maintains the list of module permissions stored in state to
+ * ensure permissions can be removed from roles during module uninstall.
  *
  * @param array $replace
  *   An associative array. The keys are the old permissions the values are
  *   an array keyed by new permission with a value of the module that implements
  *   that permission. If the list is an empty array, the old permission is
- *   removed.
+ *   removed. For example:
+ *   @code
+ *   array(
+ *     'view revisions' => array('view all revisions' => 'node'),
+ *     'revert revisions' => array('revert all revisions' => 'node'),
+ *     'delete revisions' => array('delete all revisions' => 'node'),
+ *   )
+ *   @endcode
  */
 function update_replace_permissions($replace) {
+  $module_permissions = state()->get('user.module_permissions') ?: array();
   $prefix = 'user.role.';
   $cut = strlen($prefix);
   $role_names = Drupal::service('config.storage')->listAll($prefix);
@@ -1621,11 +1630,25 @@
     foreach ($replace as $old_permission => $new_permissions) {
-      if (isset($permissions[$old_permission])) {
-        unset($permissions[$old_permission]);
-        $permissions = array_merge($permissions, $new_permissions);
+      $key = array_search($old_permission, $permissions);
+      if ($key !== FALSE) {
+        unset($permissions[$key]);
+        $permissions = array_merge($permissions, array_keys($new_permissions));
+      }
+      foreach ($new_permissions as $new_permission => $module) {
+        $module_permissions[$module][] = $new_permission;
       }
     }
     $config
       ->set('permissions', $permissions)
       ->save();
   }
+  // Remove the old permission from user.module_permissions.
+  foreach ($replace as $old_permission => $new_permissions) {
+    foreach ($module_permissions as $module => $perms) {
+      $key = array_search($old_permission, $perms);
+      if ($key !== FALSE) {
+        unset($module_permissions[$module][$key]);
+      }
+    }
+  }
+  state()->set('user.module_permissions', $module_permissions);
 }
diff -u b/core/modules/comment/comment.module b/core/modules/comment/comment.module
--- b/core/modules/comment/comment.module
+++ b/core/modules/comment/comment.module
@@ -1224,16 +1224,16 @@
     // 1. 'Authenticated user' can search content but can't access comments.
     // 2. 'Anonymous user' can search content but can't access comments.
     // 3. Any role can search content but can't access comments and access
-    // comments is not granted by the 'authenticated user' role. In this case
+    // comments is not granted to the 'authenticated user' role. In this case
     // all users might have both permissions from various roles but it is also
-    // possible to set up a user to have only search content and so a user
-    // edit could change the security situation so it is not safe to index the
+    // possible to set up a user to have only search content. Therefore a user
+    // edit could change the security situation making it not safe to index the
     // comments.
     $index_comments = TRUE;
     $roles = user_roles();
-    $authenticated_can_access = isset($roles[DRUPAL_AUTHENTICATED_RID]->permissions['access comments']);
-    foreach ($roles as $rid => $role_object) {
-      if (isset($role_object->permissions['search content']) && !isset($role_object->permissions['access comments']) &&
+    $authenticated_can_access = $roles[DRUPAL_AUTHENTICATED_RID]->has('access comments');
+    foreach ($roles as $rid => $role) {
+      if ($role->has('search content') && !$role->has('access comments') &&
          ($rid == DRUPAL_AUTHENTICATED_RID || $rid == DRUPAL_ANONYMOUS_RID || !$authenticated_can_access)) {
         $index_comments = FALSE;
         break;
diff -u b/core/modules/node/node.views_execution.inc b/core/modules/node/node.views_execution.inc
--- b/core/modules/node/node.views_execution.inc
+++ b/core/modules/node/node.views_execution.inc
@@ -23,6 +23,7 @@
  */
 function node_views_analyze(ViewExecutable $view) {
   $ret = array();
+  $access_content_roles = user_roles(FALSE, 'access content');
   // Check for something other than the default display:
   if ($view->storage->get('base_table') == 'node') {
     foreach ($view->displayHandlers as $id => $display) {
@@ -30,9 +31,7 @@
         // check for no access control
         $access = $display->getOption('access');
         if (empty($access['type']) || $access['type'] == 'none') {
-          $anonymous_has_access = isset(entity_load('user_role', DRUPAL_ANONYMOUS_RID)->permissions['access content']);
-          $authenticated_has_access = isset(entity_load('user_role', DRUPAL_AUTHENTICATED_RID)->permissions['access content']);
-          if (!$anonymous_has_access || !$authenticated_has_access) {
+          if (!isset($access_content_roles[DRUPAL_ANONYMOUS_RID]) || !isset($access_content_roles[DRUPAL_AUTHENTICATED_RID])) {
             $ret[] = Analyzer::formatMessage(t('Some roles lack permission to access content, but display %display has no access control.', array('%display' => $display->display['display_title'])), 'warning');
           }
           $filters = $display->getOption('filters');
diff -u b/core/modules/simpletest/lib/Drupal/simpletest/WebTestBase.php b/core/modules/simpletest/lib/Drupal/simpletest/WebTestBase.php
--- b/core/modules/simpletest/lib/Drupal/simpletest/WebTestBase.php
+++ b/core/modules/simpletest/lib/Drupal/simpletest/WebTestBase.php
@@ -552,7 +552,7 @@
       if (!empty($permissions)) {
         user_role_grant_permissions($role->id(), $permissions);
         $assigned_permissions = entity_load('user_role', $role->id())->permissions;
-        $missing_permissions = array_diff($permissions, array_keys($assigned_permissions));
+        $missing_permissions = array_diff($permissions, $assigned_permissions);
         if (!$missing_permissions) {
           $this->pass(t('Created permissions: @perms', array('@perms' => implode(', ', $permissions))), t('Role'));
         }
diff -u b/core/modules/user/config/user.role.anonymous.yml b/core/modules/user/config/user.role.anonymous.yml
--- b/core/modules/user/config/user.role.anonymous.yml
+++ b/core/modules/user/config/user.role.anonymous.yml
@@ -4,3 +4,3 @@
 permissions:
-  'access content': node
+  - 'access content'
 langcode: en
diff -u b/core/modules/user/config/user.role.authenticated.yml b/core/modules/user/config/user.role.authenticated.yml
--- b/core/modules/user/config/user.role.authenticated.yml
+++ b/core/modules/user/config/user.role.authenticated.yml
@@ -4,3 +4,3 @@
 permissions:
-  'access content': node
+  - 'access content'
 langcode: en
diff -u b/core/modules/user/lib/Drupal/user/Plugin/Core/Entity/Role.php b/core/modules/user/lib/Drupal/user/Plugin/Core/Entity/Role.php
--- b/core/modules/user/lib/Drupal/user/Plugin/Core/Entity/Role.php
+++ b/core/modules/user/lib/Drupal/user/Plugin/Core/Entity/Role.php
@@ -87,2 +87,9 @@
 
+  /**
+   * {@inheritdoc}
+   */
+  public function has($permission) {
+    return in_array($permission, $this->permissions);
+  }
+
 }
diff -u b/core/modules/user/lib/Drupal/user/Plugin/views/field/Permissions.php b/core/modules/user/lib/Drupal/user/Plugin/views/field/Permissions.php
--- b/core/modules/user/lib/Drupal/user/Plugin/views/field/Permissions.php
+++ b/core/modules/user/lib/Drupal/user/Plugin/views/field/Permissions.php
@@ -56,7 +56,7 @@
       if ($rids) {
         $roles = entity_load_multiple('user_role', array_keys($rids));
         foreach ($rids as $rid => $role_uids) {
-          foreach ($roles[$rid]->permissions as $permission => $module) {
+          foreach ($roles[$rid]->permissions as $permission) {
             foreach ($role_uids as $uid) {
               $this->items[$uid][$permission]['permission'] = $permission_names[$permission]['title'];
             }
diff -u b/core/modules/user/user.install b/core/modules/user/user.install
--- b/core/modules/user/user.install
+++ b/core/modules/user/user.install
@@ -1029,16 +1029,20 @@
     ->execute()
     ->fetchAll();
   $new_permissions = array();
+  $module_permissions = array();
   foreach ($db_permissions as $permission) {
-    // The format for the permissions array in the role file is an associative
-    // array in the format $permission => $module.
-    $new_permissions[_user_update_map_rid($permission->rid)][$permission->permission] = $permission->module;
+    $new_permissions[_user_update_map_rid($permission->rid)][] = $permission->permission;
+    $module_permissions[$permission->module][] = $permission->permission;
   }
+
   foreach ($new_permissions as $rid => $permissions) {
     config("user.role.$rid")
       ->set('permissions', $permissions)
       ->save();
   }
+
+  // Save which module implements what permissions.
+  state()->set('user.module_permissions', $module_permissions);
 }
 
 /**
diff -u b/core/modules/user/user.module b/core/modules/user/user.module
--- b/core/modules/user/user.module
+++ b/core/modules/user/user.module
@@ -415,7 +415,7 @@
   foreach ($roles as $rid => $name) {
     $role_permissions[$rid] = array();
     if (isset($entities[$rid])) {;
-      foreach ($entities[$rid]->permissions as $permission => $module) {
+      foreach ($entities[$rid]->permissions as $permission) {
         $role_permissions[$rid][$permission] = TRUE;
       }
     }
@@ -442,7 +442,7 @@
   foreach ($roles as $rid => $name) {
     $role_permissions[$rid] = array();
     $permissions = Drupal::config("user.role.$rid")->get('permissions') ?: array();
-    foreach ($permissions as $permission => $module) {
+    foreach ($permissions as $permission) {
       $role_permissions[$rid][$permission] = TRUE;
     }
   }
@@ -1857,8 +1857,8 @@
   }
 
   if (!empty($permission)) {
-    foreach ($roles as $rid => $role_object) {
-      if (!isset($role_object->permissions[$permission])) {
+    foreach ($roles as $rid => $role) {
+      if (!$role->has($permission)) {
         unset($roles[$rid]);
       }
     }
@@ -1956,14 +1956,8 @@
  * @see user_role_revoke_permissions()
  */
 function user_role_grant_permissions($rid, array $permissions = array()) {
-  $modules = user_permission_get_modules();
-  // Create an array with permmission names as keys implementing modules as
-  // values.
-  $permissions_to_add = array_intersect_key($modules, array_flip($permissions));
-
-  // Grant new permissions for the role.
   $role_entity = entity_load('user_role', $rid);
-  $role_entity->permissions = array_merge($role_entity->permissions, $permissions_to_add);
+  $role_entity->permissions = array_unique(array_merge($role_entity->permissions, $permissions));
   $role_entity->save();
 
   // Clear the user access cache.
@@ -1985,7 +1979,7 @@
 
   // Revoke permissions for the role.
   $role_entity = entity_load('user_role', $rid);
-  $role_entity->permissions = array_diff_key($role_entity->permissions, array_flip($permissions));
+  $role_entity->permissions = array_diff($role_entity->permissions, $permissions);
   $role_entity->save();
   // Clear the user access cache.
   drupal_static_reset('user_access');
@@ -2588,19 +2582,26 @@
  * Implements hook_modules_installed().
  */
 function user_modules_installed($modules) {
-  // Assign all available permissions to the administrator role.
-  $rid = config('user.settings')->get('admin_role');
-  if ($rid) {
-    $permissions = array();
-    foreach ($modules as $module) {
-      if ($module_permissions = module_invoke($module, 'permission')) {
-        $permissions = array_merge($permissions, array_keys($module_permissions));
+  $module_permissions_state = state()->get('user.module_permissions') ?: array();
+  $permissions = array();
+  foreach ($modules as $module) {
+    if ($module_permissions = module_invoke($module, 'permission')) {
+      $module_permissions = array_keys($module_permissions);
+      $permissions = array_merge($permissions, $module_permissions);
+      // If the module has permissions store them in state so we can remove the
+      // permissions from roles when a module is uninstalled.
+      if (!empty($module_permissions)) {
+        $module_permissions_state[$module] = $module_permissions;
       }
     }
-    if (!empty($permissions)) {
-      user_role_grant_permissions($rid, $permissions);
-    }
   }
+
+  // Assign all available permissions to the administrator role.
+  $rid = config('user.settings')->get('admin_role');
+  if ($rid && !empty($permissions)) {
+    user_role_grant_permissions($rid, $permissions);
+  }
+  state()->set('user.module_permissions', $module_permissions_state);
 }
 
 /**
@@ -2610,8 +2611,15 @@
  * module.
  */
 function user_modules_uninstalled($modules) {
-  foreach (user_roles() as $rid => $role_entity) {
-    $permissions_to_remove = array_keys($role_entity->permissions, $modules);
+  $module_permissions = state()->get('user.module_permissions') ?: array();
+  $permissions_to_remove = array();
+  foreach ($modules as $module) {
+    if (isset($module_permissions[$module])) {
+      $permissions_to_remove += $module_permissions[$module];
+    }
+  }
+
+  foreach (user_roles() as $role_entity) {
     $role_entity->permissions = array_diff($role_entity->permissions, $permissions_to_remove);
     $role_entity->save();
   }
only in patch2:
unchanged:
--- a/core/modules/user/lib/Drupal/user/RoleInterface.php
+++ b/core/modules/user/lib/Drupal/user/RoleInterface.php
@@ -14,4 +14,15 @@
  */
 interface RoleInterface extends ConfigEntityInterface {
 
+  /**
+   * Checks if the role has a permission.
+   *
+   * @param string $permission
+   *   The permission to check for.
+   *
+   * @return bool
+   *   TRUE if the role has the permission, FALSE if not.
+   */
+  public function has($permission);
+
 }