Reimplement PrivilegeSet.

This new implementation embeds in PrivilegeSet the hierarchical privilege
checking algorithm.  This is necessary in order to allow a connection with
multiple authenticated princiapls to correctly resolve whether or not a
command is authorized, given the case where one principal's authority provides
some of the required privileges, and another's provides the rest.

SERVER-7767

10 files changed, 423 insertions, 170 deletions

diff --git a/src/mongo/db/auth/action_set.cpp b/src/mongo/db/auth/action_set.cpp
index 5184819c995..b7c17ae1996 100644
--- a/src/mongo/db/auth/action_set.cpp
+++ b/src/mongo/db/auth/action_set.cpp
@@ -39,6 +39,18 @@ namespace mongo {
         _actions = ~std::bitset<ActionType::NUM_ACTION_TYPES>();
     }
 
+    void ActionSet::removeAction(const ActionType& action) {
+        _actions.set(action.getIdentifier(), false);
+    }
+
+    void ActionSet::removeAllActionsFromSet(const ActionSet& other) {
+        _actions &= ~other._actions;
+    }
+
+    void ActionSet::removeAllActions() {
+        _actions = std::bitset<ActionType::NUM_ACTION_TYPES>();
+    }
+
     bool ActionSet::contains(const ActionType& action) const {
         return _actions[action.getIdentifier()];
     }
diff --git a/src/mongo/db/auth/action_set.h b/src/mongo/db/auth/action_set.h
index f6696e59652..2cb8997a943 100644
--- a/src/mongo/db/auth/action_set.h
+++ b/src/mongo/db/auth/action_set.h
@@ -35,6 +35,12 @@ namespace mongo {
         void addAllActionsFromSet(const ActionSet& actionSet);
         void addAllActions();
 
+        void removeAction(const ActionType& action);
+        void removeAllActionsFromSet(const ActionSet& actionSet);
+        void removeAllActions();
+
+        bool empty() const { return _actions.none(); }
+
         bool contains(const ActionType& action) const;
 
         // Returns true only if this ActionSet contains all the actions present in the 'other'
diff --git a/src/mongo/db/auth/authorization_manager.cpp b/src/mongo/db/auth/authorization_manager.cpp
index 9b3867f7d73..ae25422644c 100644
--- a/src/mongo/db/auth/authorization_manager.cpp
+++ b/src/mongo/db/auth/authorization_manager.cpp
@@ -46,7 +46,6 @@ namespace mongo {
     namespace {
         const std::string ADMIN_DBNAME = "admin";
         const std::string LOCAL_DBNAME = "local";
-        const std::string WILDCARD_DBNAME = "*";
     }
 
     // ActionSets for the various system roles.  These ActionSets contain all the actions that
@@ -193,13 +192,13 @@ namespace mongo {
         _authenticatedPrincipals.add(principal);
     }
 
-    Principal* AuthorizationManager::lookupPrincipal(const PrincipalName& name) const {
+    Principal* AuthorizationManager::lookupPrincipal(const PrincipalName& name) {
         return _authenticatedPrincipals.lookup(name);
     }
 
     void AuthorizationManager::logoutDatabase(const std::string& dbname) {
         Principal* principal = _authenticatedPrincipals.lookupByDBName(dbname);
-        _acquiredPrivileges.revokePrivilegesFromPrincipal(principal);
+        _acquiredPrivileges.revokePrivilegesFromPrincipal(principal->getName());
         _authenticatedPrincipals.removeByDBName(dbname);
     }
 
@@ -215,8 +214,7 @@ namespace mongo {
                           0);
         }
 
-        _acquiredPrivileges.grantPrivilege(privilege);
-
+        _acquiredPrivileges.grantPrivilege(privilege.getPrivilege(), principal->getName());
         return Status::OK();
     }
 
@@ -224,17 +222,17 @@ namespace mongo {
         Principal* principal = new Principal(PrincipalName(principalName, "local"));
         ActionSet actions;
         actions.addAllActions();
-        AcquiredPrivilege privilege(Privilege("*", actions), principal);
+        AcquiredPrivilege privilege(Privilege(PrivilegeSet::WILDCARD_RESOURCE, actions), principal);
 
         addAuthorizedPrincipal(principal);
-        Status status = acquirePrivilege(privilege);
-        verify(status.isOK());
+        fassert(0, acquirePrivilege(privilege).isOK());
     }
 
-    bool AuthorizationManager::hasInternalAuthorization() const {
+    bool AuthorizationManager::hasInternalAuthorization() {
         ActionSet allActions;
         allActions.addAllActions();
-        return _acquiredPrivileges.getPrivilegeForActions("*", allActions);
+        return _acquiredPrivileges.hasPrivilege(Privilege(PrivilegeSet::WILDCARD_RESOURCE,
+                                                          allActions));
     }
 
     ActionSet AuthorizationManager::getActionsForOldStyleUser(const std::string& dbname,
@@ -278,7 +276,8 @@ namespace mongo {
             // Grant full access to internal user
             ActionSet allActions;
             allActions.addAllActions();
-            AcquiredPrivilege privilege(Privilege(WILDCARD_DBNAME, allActions), principal);
+            AcquiredPrivilege privilege(Privilege(PrivilegeSet::WILDCARD_RESOURCE, allActions),
+                                        principal);
             return acquirePrivilege(privilege);
         }
         return buildPrivilegeSet(dbname, principal, privilegeDocument, &_acquiredPrivileges);
@@ -329,39 +328,26 @@ namespace mongo {
                 privilegeDocument["readOnly"].trueValue();
         ActionSet actions = getActionsForOldStyleUser(dbname, readOnly);
         std::string resourceName = (dbname == ADMIN_DBNAME || dbname == LOCAL_DBNAME) ?
-                WILDCARD_DBNAME : dbname;
-        result->grantPrivilege(AcquiredPrivilege(Privilege(resourceName, actions), principal));
+            PrivilegeSet::WILDCARD_RESOURCE : dbname;
+        result->grantPrivilege(Privilege(resourceName, actions), principal->getName());
 
         return Status::OK();
     }
 
     bool AuthorizationManager::checkAuthorization(const std::string& resource,
-                                                  ActionType action) const {
-
-        if (_externalState->shouldIgnoreAuthChecks()) {
+                                                  ActionType action) {
+        if (_externalState->shouldIgnoreAuthChecks())
             return true;
-        }
 
-        if (_acquiredPrivileges.getPrivilegeForAction(nsToDatabase(resource), action))
-            return true;
-        if (_acquiredPrivileges.getPrivilegeForAction(WILDCARD_DBNAME, action))
-            return true;
-        return false;
+        return _acquiredPrivileges.hasPrivilege(Privilege(nsToDatabase(resource), action));
     }
 
     bool AuthorizationManager::checkAuthorization(const std::string& resource,
-                                                  ActionSet actions) const {
-
-        if (_externalState->shouldIgnoreAuthChecks()) {
-            return true;
-        }
-
-        if (_acquiredPrivileges.getPrivilegeForActions(nsToDatabase(resource), actions))
-            return true;
-        if (_acquiredPrivileges.getPrivilegeForActions(WILDCARD_DBNAME, actions))
+                                                  ActionSet actions) {
+        if (_externalState->shouldIgnoreAuthChecks())
             return true;
 
-        return false;
+        return _acquiredPrivileges.hasPrivilege(Privilege(nsToDatabase(resource), actions));
     }
 
     Status AuthorizationManager::checkAuthForQuery(const std::string& ns) {
diff --git a/src/mongo/db/auth/authorization_manager.h b/src/mongo/db/auth/authorization_manager.h
index a9f069e9560..9320ef9fb56 100644
--- a/src/mongo/db/auth/authorization_manager.h
+++ b/src/mongo/db/auth/authorization_manager.h
@@ -65,7 +65,7 @@ namespace mongo {
         // Returns the authenticated principal with the given name.  Returns NULL
         // if no such user is found.
         // Ownership of the returned Principal remains with _authenticatedPrincipals
-        Principal* lookupPrincipal(const PrincipalName& name) const;
+        Principal* lookupPrincipal(const PrincipalName& name);
 
         // Removes any authenticated principals whose authorization credentials came from the given
         // database, and revokes any privileges that were granted via that principal.
@@ -79,16 +79,16 @@ namespace mongo {
         void grantInternalAuthorization(const std::string& principalName);
 
         // Checks if this connection has been authenticated as an internal user.
-        bool hasInternalAuthorization() const;
+        bool hasInternalAuthorization();
 
         // Checks if this connection has the privileges required to perform the given action
         // on the given resource.  Contains all the authorization logic including handling things
         // like the localhost exception.  Returns true if the action may proceed on the resource.
-        bool checkAuthorization(const std::string& resource, ActionType action) const;
+        bool checkAuthorization(const std::string& resource, ActionType action);
 
         // Same as above but takes an ActionSet instead of a single ActionType.  Returns true if
         // all of the actions may proceed on the resource.
-        bool checkAuthorization(const std::string& resource, ActionSet actions) const;
+        bool checkAuthorization(const std::string& resource, ActionSet actions);
 
         // Parses the privilege documents and acquires all privileges that the privilege document
         // grants
diff --git a/src/mongo/db/auth/authorization_manager_test.cpp b/src/mongo/db/auth/authorization_manager_test.cpp
index 5ad34678549..88b8c63e934 100644
--- a/src/mongo/db/auth/authorization_manager_test.cpp
+++ b/src/mongo/db/auth/authorization_manager_test.cpp
@@ -79,38 +79,37 @@ namespace {
                                                            principal,
                                                            readOnly,
                                                            &privilegeSet));
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::insert));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::find));
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("test", ActionType::insert)));
+        ASSERT(privilegeSet.hasPrivilege(Privilege("test", ActionType::find)));
 
         ASSERT_OK(AuthorizationManager::buildPrivilegeSet("test",
                                                            principal,
                                                            readWrite,
                                                            &privilegeSet));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::find));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::insert));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::userAdmin));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::compact));
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::shutdown));
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("test", ActionType::addShard));
-
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("admin", ActionType::find));
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("*", ActionType::find));
+        ASSERT(privilegeSet.hasPrivilege(Privilege("test", ActionType::find)));
+        ASSERT(privilegeSet.hasPrivilege(Privilege("test", ActionType::insert)));
+        ASSERT(privilegeSet.hasPrivilege(Privilege("test", ActionType::userAdmin)));
+        ASSERT(privilegeSet.hasPrivilege(Privilege("test", ActionType::compact)));
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("test", ActionType::shutdown)));
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("test", ActionType::addShard)));
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("admin", ActionType::find)));
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("*", ActionType::find)));
+
         ASSERT_OK(AuthorizationManager::buildPrivilegeSet("admin",
                                                            principal,
                                                            readOnly,
                                                            &privilegeSet));
-        // Should grant privileges on *, not on admin DB directly
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("admin", ActionType::find));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("*", ActionType::find));
+        // Should grant privileges on *.
+        ASSERT(privilegeSet.hasPrivilege(Privilege("*", ActionType::find)));
+
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("admin", ActionType::insert)));
+        ASSERT(!privilegeSet.hasPrivilege(Privilege("*", ActionType::insert)));
 
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("admin", ActionType::insert));
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("*", ActionType::insert));
         ASSERT_OK(AuthorizationManager::buildPrivilegeSet("admin",
                                                            principal,
                                                            readWrite,
                                                            &privilegeSet));
-        ASSERT_NULL(privilegeSet.getPrivilegeForAction("admin", ActionType::insert));
-        ASSERT_NON_NULL(privilegeSet.getPrivilegeForAction("*", ActionType::insert));
+        ASSERT(privilegeSet.hasPrivilege(Privilege("*", ActionType::insert)));
     }
 
 }  // namespace
diff --git a/src/mongo/db/auth/privilege.cpp b/src/mongo/db/auth/privilege.cpp
index f99d099e2c8..88401c91ad5 100644
--- a/src/mongo/db/auth/privilege.cpp
+++ b/src/mongo/db/auth/privilege.cpp
@@ -23,7 +23,12 @@
 
 namespace mongo {
 
-    Privilege::Privilege(const std::string& resource, ActionSet actions) :
+    Privilege::Privilege(const std::string& resource, const ActionType& action) :
+        _resource(resource) {
+
+        _actions.addAction(action);
+    }
+    Privilege::Privilege(const std::string& resource, const ActionSet& actions) :
             _resource(resource), _actions(actions) {}
 
     bool Privilege::includesAction(const ActionType& action) const {
diff --git a/src/mongo/db/auth/privilege.h b/src/mongo/db/auth/privilege.h
index b6326860805..eef476ea224 100644
--- a/src/mongo/db/auth/privilege.h
+++ b/src/mongo/db/auth/privilege.h
@@ -29,7 +29,8 @@ namespace mongo {
     class Privilege {
     public:
 
-        Privilege(const std::string& resource, ActionSet actions);
+        Privilege(const std::string& resource, const ActionType& action);
+        Privilege(const std::string& resource, const ActionSet& actions);
         ~Privilege() {}
 
         const std::string& getResource() const { return _resource; }
diff --git a/src/mongo/db/auth/privilege_set.cpp b/src/mongo/db/auth/privilege_set.cpp
index 8555f1046e8..d572bf3b4c1 100644
--- a/src/mongo/db/auth/privilege_set.cpp
+++ b/src/mongo/db/auth/privilege_set.cpp
@@ -24,54 +24,122 @@
 #include "mongo/db/auth/action_set.h"
 #include "mongo/db/auth/action_type.h"
 #include "mongo/db/auth/principal.h"
+#include "mongo/util/map_util.h"
 
 namespace mongo {
 
-    void PrivilegeSet::grantPrivilege(const AcquiredPrivilege& privilege) {
-        _privileges.insert(std::make_pair(privilege.getPrivilege().getResource(), privilege));
+    const std::string PrivilegeSet::WILDCARD_RESOURCE = "*";
+
+    PrivilegeSet::PrivilegeSet() {}
+    PrivilegeSet::~PrivilegeSet() {}
+
+    void PrivilegeSet::grantPrivilege(const Privilege& privilege,
+                                      const PrincipalName& authorizingPrincipal) {
+        grantPrivileges(std::vector<Privilege>(1, privilege), authorizingPrincipal);
     }
 
-    const AcquiredPrivilege* PrivilegeSet::getPrivilegeForAction(const std::string& resource,
-                                                                 const ActionType& action) const {
-        PrivilegeSetConstRange range;
-        PrivilegeRangeConstIterator it;
-
-        range = _privileges.equal_range(resource);
-        for (it = range.first; it != range.second; ++it) {
-            const AcquiredPrivilege& privilege = it->second;
-            if (privilege.getPrivilege().includesAction(action)) {
-                return &privilege;
-            }
+    void PrivilegeSet::grantPrivileges(const std::vector<Privilege>& privileges,
+                                       const PrincipalName& authorizingPrincipal) {
+        StringMap<ActionSet>& byResourceForPrincipal = _byPrincipal[authorizingPrincipal];
+        for (std::vector<Privilege>::const_iterator iter = privileges.begin(),
+                 end = privileges.end();
+             iter != end; ++iter) {
+
+            byResourceForPrincipal[iter->getResource()].addAllActionsFromSet(iter->getActions());
+
+            ResourcePrivilegeCacheEntry* entry = _lookupOrInsertEntry(iter->getResource());
+            entry->actions.addAllActionsFromSet(iter->getActions());
         }
-        return NULL;
     }
 
-    const AcquiredPrivilege* PrivilegeSet::getPrivilegeForActions(const std::string& resource,
-                                                                  const ActionSet& actions) const {
-        PrivilegeSetConstRange range;
-        PrivilegeRangeConstIterator it;
-
-        range = _privileges.equal_range(resource);
-        for (it = range.first; it != range.second; ++it) {
-            const AcquiredPrivilege& privilege = it->second;
-            if (privilege.getPrivilege().includesActions(actions)) {
-                return &privilege;
-            }
+    void PrivilegeSet::revokePrivilegesFromPrincipal(const PrincipalName& principal) {
+        PrincipalPrivilegeMap::iterator principalEntry = _byPrincipal.find(principal);
+        if (principalEntry == _byPrincipal.end())
+            return;
+
+        // For every resource that "principal" authorizes, mark its entry in the _byResource table
+        // as dirty, so that it will be rebuilt on next consultation.
+        for (StringMap<ActionSet>::const_iterator resourceEntry = principalEntry->second.begin(),
+                 end = principalEntry->second.end();
+             resourceEntry != end; ++resourceEntry) {
+
+            _lookupOrInsertEntry(resourceEntry->first)->dirty = true;
         }
-        return NULL;
+
+        // Remove the princiapl from the _byPrincipal table.
+        _byPrincipal.erase(principalEntry);
     }
 
-    void PrivilegeSet::revokePrivilegesFromPrincipal(Principal* principal) {
-        PrivilegeRangeIterator it = _privileges.begin();
+    bool PrivilegeSet::hasPrivilege(const Privilege& desiredPrivilege) {
+        if (desiredPrivilege.getActions().empty())
+            return true;
+
+        StringData resourceSearchList[2];
+        resourceSearchList[0] = WILDCARD_RESOURCE;
+        resourceSearchList[1] = desiredPrivilege.getResource();
 
-        while (it != _privileges.end()) {
-            PrivilegeRangeIterator current = it;
-            ++it;  // Must advance now because erase will invalidate the iterator
-            AcquiredPrivilege& privilege = current->second;
-            if (privilege.getPrincipal() == principal) {
-                _privileges.erase(current);
-            }
+        ActionSet unmetRequirements = desiredPrivilege.getActions();
+        for (int i = 0; i < boost::size(resourceSearchList); ++i) {
+            ResourcePrivilegeCacheEntry* entry = _lookupEntry(resourceSearchList[i]);
+            if (NULL == entry)
+                continue;
+            if (entry->dirty)
+                _rebuildEntry(resourceSearchList[i], entry);
+            unmetRequirements.removeAllActionsFromSet(entry->actions);
+            if (unmetRequirements.empty())
+                return true;
         }
+        return false;
+    }
+
+    bool PrivilegeSet::hasPrivileges(const std::vector<Privilege>& desiredPrivileges) {
+        for (std::vector<Privilege>::const_iterator iter = desiredPrivileges.begin(),
+                 end = desiredPrivileges.end();
+             iter != end; ++iter) {
+
+            if (!hasPrivilege(*iter))
+                return false;
+        }
+        return true;
+    }
+
+    void PrivilegeSet::_rebuildEntry(const StringData& resource,
+                                     ResourcePrivilegeCacheEntry* entry) {
+        const ActionSet emptyActionSet;
+        entry->actions.removeAllActions();
+
+        for (PrincipalPrivilegeMap::const_iterator iter = _byPrincipal.begin(),
+                 end = _byPrincipal.end();
+             iter != end; ++iter) {
+
+            entry->actions.addAllActionsFromSet(
+                    mapFindWithDefault(iter->second, resource, emptyActionSet));
+        }
+
+        entry->dirty = false;
+    }
+
+    PrivilegeSet::ResourcePrivilegeCacheEntry* PrivilegeSet::_lookupEntry(
+            const StringData& resource) {
+
+        if (resource == WILDCARD_RESOURCE)
+            return &_globalPrivilegeEntry;
+
+        ResourcePrivilegeCache::const_iterator iter = _byResource.find(resource);
+        if (iter != _byResource.end()) {
+            // StringMap doesn't have non-const iterators, so there is no way to lookup without
+            // inserting and get a mutable value, without const-cast.
+            return const_cast<ResourcePrivilegeCacheEntry*>(&iter->second);
+        }
+        return NULL;
+    }
+
+    PrivilegeSet::ResourcePrivilegeCacheEntry* PrivilegeSet::_lookupOrInsertEntry(
+            const StringData& resource) {
+
+        if (resource == WILDCARD_RESOURCE)
+            return &_globalPrivilegeEntry;
+        return &_byResource[resource];
     }
 
 } // namespace mongo
diff --git a/src/mongo/db/auth/privilege_set.h b/src/mongo/db/auth/privilege_set.h
index 7033e738a4d..1c110f13681 100644
--- a/src/mongo/db/auth/privilege_set.h
+++ b/src/mongo/db/auth/privilege_set.h
@@ -22,51 +22,116 @@
 #include "mongo/db/auth/action_set.h"
 #include "mongo/db/auth/action_type.h"
 #include "mongo/db/auth/privilege.h"
-#include "mongo/db/auth/principal.h"
+#include "mongo/db/auth/principal_name.h"
+#include "mongo/util/string_map.h"
 
 namespace mongo {
 
     /**
-     * A collection of privileges describing which authenticated principals bestow the client
-     * the ability to perform various actions on specific resources.  Since every privilege
-     * comes from an authenticated principal, removing that principal can remove all privileges
-     * that that principal granted.
+     * A collection of privileges describing which authenticated principals bestow the client the
+     * ability to perform various actions on specific resources.  Since every privilege comes from
+     * an authenticated principal, removing that principal removes all privileges granted by that
+     * principal.
+     *
+     * Resources are arranged hierarchically, with a wildcard resource,
+     * PrivilegeSet::WILDCARD_RESOURCE, matching any resource.  In the current implementation, the
+     * only two levels of the hierarchy are the wildcard and one level below, which is analagous to
+     * the name of a database.  It is future work to support collection or other sub-database
+     * resources.
+     *
      * This class does not do any locking/synchronization, the consumer will be responsible for
      * synchronizing access.
      */
     class PrivilegeSet {
         MONGO_DISALLOW_COPYING(PrivilegeSet);
     public:
-        PrivilegeSet(){}
-        ~PrivilegeSet(){}
-
-        void grantPrivilege(const AcquiredPrivilege& privilege);
-        void revokePrivilegesFromPrincipal(Principal* principal);
-
-        // Returns the first privilege found that grants the given action on the given resource.
-        // Returns NULL if there is no such privilege.
-        // Ownership of the returned Privilege remains with the PrivilegeSet.  The pointer
-        // returned is only guaranteed to remain valid until the next non-const method is called
-        // on the PrivilegeSet.
-        const AcquiredPrivilege* getPrivilegeForAction(const std::string& resource,
-                                                       const ActionType& action) const;
-        // Same as above but takes an ActionSet.  The AcquiredPrivilege returned must include
-        // permission to perform all the actions in the ActionSet on the given resource.
-        const AcquiredPrivilege* getPrivilegeForActions(const std::string& resource,
-                                                        const ActionSet& action) const;
+        static const std::string WILDCARD_RESOURCE;
+
+        PrivilegeSet();
+        ~PrivilegeSet();
+
+        /**
+         * Adds the specified privilege to the set, associating it with the named principal.
+         *
+         * The privilege should be on a specific resource, or on the WILDCARD_RESOURCE.
+         */
+        void grantPrivilege(const Privilege& privilege, const PrincipalName& authorizingPrincipal);
+
+        /**
+         * Adds the specified privileges to the set, associating them with the named principal.
+         */
+        void grantPrivileges(const std::vector<Privilege>& privileges,
+                             const PrincipalName& authorizingPrincipal);
+
+        /**
+         * Removes from the set all privileges associated with the given principal.
+         *
+         * If multiple princpals enable the same privilege, the set will continue to
+         * contain those privileges until all authorizing principals have had their
+         * privileges revoked from the set.
+         */
+        void revokePrivilegesFromPrincipal(const PrincipalName& principal);
+
+        /**
+         * Returns true if the set authorizes "desiredPrivilege".
+         *
+         * The set is considered to authorize "desiredPrivilege" if each action in
+         * "desiredPrivilege" is satisfied either on "desiredPrivilege.getResource()" or on
+         * WILDCARD_RESOURCE.
+         */
+        bool hasPrivilege(const Privilege& desiredPrivilege);
+
+        /**
+         * Same as hasPrivilege, except checks all the privileges in a vector.
+         */
+        bool hasPrivileges(const std::vector<Privilege>& desiredPrivileges);
 
     private:
 
-        // Key is the resource the privilege is on.
-        typedef std::multimap<const std::string, AcquiredPrivilege> PrivilegeMap;
-        typedef PrivilegeMap::iterator PrivilegeRangeIterator;
-        typedef std::pair<PrivilegeRangeIterator, PrivilegeRangeIterator> PrivilegeSetRange;
-        typedef PrivilegeMap::const_iterator PrivilegeRangeConstIterator;
-        typedef std::pair<PrivilegeRangeConstIterator, PrivilegeRangeConstIterator>
-                PrivilegeSetConstRange;
+        /**
+         * Information about privileges held on a resource.
+         *
+         * Instances are stored in the _byResource map, and accelerate the fast path of
+         * hasPrivilege().  Privilege revocations via revokePrivilegesFromPrincipal() can make these
+         * entries invalid, at which point they are marked "dirty".  Dirty entries are rebuilt via
+         * _rebuildEntry(), below, during execution of hasPrivilege().
+         */
+        class ResourcePrivilegeCacheEntry {
+        public:
+            ResourcePrivilegeCacheEntry() : actions(), dirty(false) {}
+
+            // All actions enabled on the associated resource, provided that "dirty" is false.
+            ActionSet actions;
+
+            // False if this data is consistent with the full privilege information, stored in the
+            // _byPrincipal map.
+            bool dirty;
+        };
+
+        /**
+         * Type of map from resource names to authorized actions.
+         */
+        typedef StringMap<ResourcePrivilegeCacheEntry> ResourcePrivilegeCache;
+
+        /**
+         * Type of map from principal identity to information about the principal's privileges.  The
+         * values in the map are themselves maps from resource names to associated actions.
+         */
+        typedef std::map<PrincipalName, StringMap<ActionSet> > PrincipalPrivilegeMap;
+
+        void _rebuildEntry(const StringData& resource, ResourcePrivilegeCacheEntry* summary);
+
+        ResourcePrivilegeCacheEntry* _lookupEntry(const StringData& resource);
+        ResourcePrivilegeCacheEntry* _lookupOrInsertEntry(const StringData& resource);
+
+        // Information about privileges available on all resources.
+        ResourcePrivilegeCacheEntry _globalPrivilegeEntry;
+
+        // Cache of privilege information, by resource.
+        ResourcePrivilegeCache _byResource;
 
-        // Maps resource to privileges
-        PrivilegeMap _privileges;
+        // Directory of privilege information, by principal.
+        PrincipalPrivilegeMap _byPrincipal;
     };
 
 } // namespace mongo
diff --git a/src/mongo/db/auth/privilege_set_test.cpp b/src/mongo/db/auth/privilege_set_test.cpp
index 553ce9b1c1c..2d01f2b3617 100644
--- a/src/mongo/db/auth/privilege_set_test.cpp
+++ b/src/mongo/db/auth/privilege_set_test.cpp
@@ -25,74 +25,185 @@
 namespace mongo {
 namespace {
 
+    // Convenience methods for outputing PrincipalName and construction ActionSets that make tests
+    // concise, but that we're reluctant to put into the types themselves.
+
+    std::ostream& operator<<(std::ostream& os, const PrincipalName& pname) {
+        return os << pname.toString();
+    }
+
+    std::ostream& operator<<(std::ostream&os, const std::vector<PrincipalName>& ps) {
+        os << "[ ";
+        for (size_t i = 0; i < ps.size(); ++i)
+            os << ps[i] << ' ';
+        os << ']';
+        return os;
+    }
+
+    ActionSet operator|(const ActionSet& lhs, const ActionSet& rhs) {
+        ActionSet result = lhs;
+        result.addAllActionsFromSet(rhs);
+        return result;
+    }
+
+    ActionSet operator|(const ActionSet& lhs, const ActionType& rhs) {
+        ActionSet result = lhs;
+        result.addAction(rhs);
+        return result;
+    }
+
+    ActionSet operator|(const ActionType& lhs, const ActionType& rhs) {
+        ActionSet result;
+        result.addAction(lhs);
+        result.addAction(rhs);
+        return result;
+    }
+
+    // Tests
+
     TEST(PrivilegeSetTest, PrivilegeSet) {
         PrivilegeSet capSet;
-        ActionSet actions;
-        Principal user1(PrincipalName("user1", "test"));
-        Principal user2(PrincipalName("user2", "test2"));
+        PrincipalName user1("user1", "test");
+        PrincipalName user2("user2", "test2");
+
+        // Initially, the capability set contains no privileges at all.
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::find)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::find)));
+
+        // Grant find and update to "foo", only.
+        capSet.grantPrivilege(Privilege("foo", ActionType::find|ActionType::update), user1);
+
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::find)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::find|ActionType::update)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::find|ActionType::remove)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::find)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::remove)));
 
-        ASSERT_OK(ActionSet::parseActionSetFromString("find,update", &actions));
-        AcquiredPrivilege fooUser(Privilege("foo", actions), &user2);
+        // Grant "userAdmin", "update" and "remove" on "foo" to user2, which changes the set of
+        // actions this privilege set will approve.
+        capSet.grantPrivilege(
+                Privilege("foo", ActionType::userAdmin|ActionType::update|ActionType::remove),
+                user2);
 
-        ASSERT_OK(ActionSet::parseActionSetFromString("find,update,userAdmin,remove", &actions));
-        AcquiredPrivilege fooUser2(Privilege("foo", actions), &user1);
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::userAdmin)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::update)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::userAdmin)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::find|ActionType::remove)));
 
-        ASSERT_OK(ActionSet::parseActionSetFromString("find,update", &actions));
-        AcquiredPrivilege barUser(Privilege("bar", actions), &user1);
+        // Revoke user2's privileges.
+        capSet.revokePrivilegesFromPrincipal(user2);
+
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::userAdmin)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::find|ActionType::remove)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::update)));
+
+        // Revoke user2's privileges again; should be a no-op.
+        capSet.revokePrivilegesFromPrincipal(user2);
+
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::userAdmin)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::find|ActionType::remove)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::update)));
+
+        // Re-grant "userAdmin", "update" and "remove" on "foo" to user2.
+        capSet.grantPrivilege(
+                Privilege("foo", ActionType::userAdmin|ActionType::update|ActionType::remove),
+                user2);
+
+        // The set still contains no capabilities on "bar".
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::find)));
+
+        // Let user2 "find" on "bar".
+        capSet.grantPrivilege(Privilege("bar", ActionType::find), user2);
+
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("bar", ActionType::find)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::update)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::remove)));
+
+        // Let user1 "find" and "update" on "bar".
+        capSet.grantPrivilege(Privilege("bar", ActionType::update|ActionType::find), user1);
+
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("bar", ActionType::find|ActionType::update)));
+        ASSERT_FALSE(capSet.hasPrivilege(
+                             Privilege("bar",
+                                       ActionType::find|ActionType::update|ActionType::remove)));
+
+        // Revoke user1's privileges.
+        capSet.revokePrivilegesFromPrincipal(user1);
+
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("foo", ActionType::update)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::find)));
+        ASSERT_TRUE(capSet.hasPrivilege(Privilege("bar", ActionType::find)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::update)));
+
+        // Revoke user2's privileges.
+        capSet.revokePrivilegesFromPrincipal(user2);
+
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("foo", ActionType::update)));
+        ASSERT_FALSE(capSet.hasPrivilege(Privilege("bar", ActionType::find)));
+    }
 
-        ASSERT_OK(ActionSet::parseActionSetFromString("find", &actions));
-        AcquiredPrivilege barReadOnly(Privilege("bar", actions), &user2);
+    TEST(PrivilegeSetTest, WildcardPrivileges) {
+        // Tests acquisition and revocation of privileges on WILDCARD_RESOURCE.
 
+        PrivilegeSet privSet;
 
-        const AcquiredPrivilege* capPtr;
-        // No capabilities
-        ASSERT(!capSet.getPrivilegeForAction("foo", ActionType::find));
+        PrincipalName user("user", "db");
+        Privilege wildcardFind("*", ActionType::find);
+        Privilege wildcardUpdate("*", ActionType::update);
+        Privilege wildcardFindAndUpdate("*", ActionType::find|ActionType::update);
+        Privilege fooFind("foo", ActionType::find);
+        Privilege fooUpdate("foo", ActionType::update);
+        Privilege fooFindAndUpdate("foo", ActionType::find|ActionType::update);
+        Privilege barFind("bar", ActionType::find);
+        Privilege barUpdate("bar", ActionType::update);
+        Privilege barFindAndUpdate("bar", ActionType::find|ActionType::update);
 
-        capSet.grantPrivilege(fooUser);
-        capPtr = capSet.getPrivilegeForAction("foo", ActionType::find);
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::find));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::remove));
+        // With no granted privileges, assert that hasPrivilege returns false.
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardFind));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardFindAndUpdate));
 
-        ASSERT(!capSet.getPrivilegeForAction("foo", ActionType::remove));
+        ASSERT_FALSE(privSet.hasPrivilege(fooFind));
+        ASSERT_FALSE(privSet.hasPrivilege(fooUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(fooFindAndUpdate));
 
-        capSet.grantPrivilege(fooUser2);
-        capPtr = capSet.getPrivilegeForAction("foo", ActionType::userAdmin);
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::find));
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::remove));
+        ASSERT_FALSE(privSet.hasPrivilege(barFind));
+        ASSERT_FALSE(privSet.hasPrivilege(barUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(barFindAndUpdate));
 
-        // No capabilities
-        ASSERT(!capSet.getPrivilegeForAction("bar", ActionType::find));
+        // Grant some privileges, and ensure that exactly those privileges are granted.
+        std::vector<Privilege> grantedPrivileges;
+        grantedPrivileges.push_back(wildcardFind);
+        grantedPrivileges.push_back(fooUpdate);
 
-        capSet.grantPrivilege(barReadOnly);
-        capPtr = capSet.getPrivilegeForAction("bar", ActionType::find);
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::find));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::update));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::remove));
+        privSet.grantPrivileges(grantedPrivileges, user);
 
-        ASSERT(!capSet.getPrivilegeForAction("bar", ActionType::update));
+        ASSERT_TRUE(privSet.hasPrivilege(wildcardFind));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardFindAndUpdate));
 
-        capSet.grantPrivilege(barUser);
-        capPtr = capSet.getPrivilegeForAction("bar", ActionType::update);
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::find));
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::update));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::remove));
+        ASSERT_TRUE(privSet.hasPrivilege(fooFind));
+        ASSERT_TRUE(privSet.hasPrivilege(fooUpdate));
+        ASSERT_TRUE(privSet.hasPrivilege(fooFindAndUpdate));
 
-        // Now let's start revoking capabilities
-        capSet.revokePrivilegesFromPrincipal(&user1);
+        ASSERT_TRUE(privSet.hasPrivilege(barFind));
+        ASSERT_FALSE(privSet.hasPrivilege(barUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(barFindAndUpdate));
 
-        capPtr = capSet.getPrivilegeForAction("foo", ActionType::find);
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::find));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::remove));
+        // Revoke the granted privileges, and assert that hasPrivilege returns false.
+        privSet.revokePrivilegesFromPrincipal(user);
 
-        capPtr = capSet.getPrivilegeForAction("bar", ActionType::find);
-        ASSERT_TRUE(capPtr->getPrivilege().includesAction(ActionType::find));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::update));
-        ASSERT_FALSE(capPtr->getPrivilege().includesAction(ActionType::remove));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardFind));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(wildcardFindAndUpdate));
 
+        ASSERT_FALSE(privSet.hasPrivilege(fooFind));
+        ASSERT_FALSE(privSet.hasPrivilege(fooUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(fooFindAndUpdate));
 
-        capSet.revokePrivilegesFromPrincipal(&user2);
-        ASSERT(!capSet.getPrivilegeForAction("foo", ActionType::find));
-        ASSERT(!capSet.getPrivilegeForAction("bar", ActionType::find));
+        ASSERT_FALSE(privSet.hasPrivilege(barFind));
+        ASSERT_FALSE(privSet.hasPrivilege(barUpdate));
+        ASSERT_FALSE(privSet.hasPrivilege(barFindAndUpdate));
     }
 
 }  // namespace