[sync] Significantly speed up password model association on mac

chrome/browser/password_manager/password_store_mac.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/password_manager/password_store_mac.h"
 #include "chrome/browser/password_manager/password_store_mac_internal.h"
 
 #include <CoreServices/CoreServices.h>
 #include <set>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include "base/callback.h"
 #include "base/logging.h"
 #include "base/mac/mac_logging.h"
 #include "base/mac/mac_util.h"
 #include "base/message_loop/message_loop.h"
 #include "base/stl_util.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
@@ skipping 205 matching lines @@
   switch (auth_type) {
     case kSecAuthenticationTypeHTMLForm:   return PasswordForm::SCHEME_HTML;
     case kSecAuthenticationTypeHTTPBasic:  return PasswordForm::SCHEME_BASIC;
     case kSecAuthenticationTypeHTTPDigest: return PasswordForm::SCHEME_DIGEST;
     default:                               return PasswordForm::SCHEME_OTHER;
   }
 }
 
 bool FillPasswordFormFromKeychainItem(const AppleKeychain& keychain,
                                       const SecKeychainItemRef& keychain_item,
-                                      PasswordForm* form) {
+                                      PasswordForm* form,
+                                      bool extract_password_data) {
   DCHECK(form);
 
   SecKeychainAttributeInfo attrInfo;
   UInt32 tags[] = { kSecAccountItemAttr,
                     kSecServerItemAttr,
                     kSecPortItemAttr,
                     kSecPathItemAttr,
                     kSecProtocolItemAttr,
                     kSecAuthenticationTypeItemAttr,
                     kSecSecurityDomainItemAttr,
                     kSecCreationDateItemAttr,
                     kSecNegativeItemAttr };
   attrInfo.count = arraysize(tags);
   attrInfo.tag = tags;
   attrInfo.format = NULL;
 
   SecKeychainAttributeList *attrList;
   UInt32 password_length;
-  void* password_data;
+
+  // If |extract_password_data| is false, do not pass in a reference to
+  // |password_data|. ItemCopyAttributesAndData will then extract only the
+  // attributes of |keychain_item| (doesn't require OS authorization), and not
+  // attempt to extract its password data (requires OS authorization).
+  void* password_data = NULL;
+  void** password_data_ref = extract_password_data ? &password_data : NULL;
+
   OSStatus result = keychain.ItemCopyAttributesAndData(keychain_item, &attrInfo,
                                                        NULL, &attrList,
                                                        &password_length,
-                                                       &password_data);
+                                                       password_data_ref);
 
   if (result != noErr) {
     // We don't log errSecAuthFailed because that just means that the user
     // chose not to allow us access to the item.
     if (result != errSecAuthFailed) {
       OSSTATUS_LOG(ERROR, result) << "Keychain data load failed";
     }
     return false;
   }
 
-  UTF8ToUTF16(static_cast<const char *>(password_data), password_length,
-              &(form->password_value));
+  if (extract_password_data) {
+    UTF8ToUTF16(static_cast<const char *>(password_data), password_length,
+                &(form->password_value));
+  }
 
   int port = kAnyPort;
   std::string server;
   std::string security_domain;
   std::string path;
   for (unsigned int i = 0; i < attrList->count; i++) {
     SecKeychainAttribute attr = attrList->attr[i];
     if (!attr.data) {
       continue;
     }
@@ skipping 157 matching lines @@
                        database_blacklist_forms.begin(),
                        database_blacklist_forms.end());
 
   // Clear out all the Keychain entries we used.
   DeleteVectorElementsInSet(keychain_forms, used_keychain_forms);
 }
 
 std::vector<PasswordForm*> GetPasswordsForForms(
     const AppleKeychain& keychain,
     std::vector<PasswordForm*>* database_forms) {
+  // We first load the attributes of all items in the keychain without loading
+  // their password data, and then match items in |database_forms| against them.
+  // This allows us to avoid individually searching through the keychain for
+  // passwords matching each form in |database_forms|, and results in a
+  // significant performance gain, since we are replacing O(N) keychain search
+  // operations with a single operation that loads all keychain items, and then
+  // selective reads of only the passwords we're interested in.

[stuartmorgan, 2013/09/18 19:23:32]

The we/us feels like noise here; would read better with s/We first/First/,
s/allows us to avoid/avoids/, s/since we are//, s/passwords we're interested
in/relevant passwords/

[Raghu Simha, 2013/09/19 21:23:23]

Done.

+  // See crbug.com/263685.
+
+  // First load references to all items in the system keychain, and copy all
+  // their attributes into a container of pairs of pointers to PasswordForms and
+  // SecKeychainItemRefs without copying any password data.
+  // This operation does not require OS authorization.
   MacKeychainPasswordFormAdapter keychain_adapter(&keychain);
+  std::vector<SecKeychainItemRef> keychain_items =
+      keychain_adapter.GetAllPasswordFormKeychainItems();
+  std::vector<std::pair<SecKeychainItemRef*, PasswordForm*> > item_form_pairs;
+  for (std::vector<SecKeychainItemRef>::iterator i = keychain_items.begin();
+       i != keychain_items.end(); ++i) {
+    PasswordForm* form_without_password = new PasswordForm();
+    internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+        keychain,
+        *i,
+        form_without_password,
+        false);  // Load password attributes, but not password data.
+    item_form_pairs.push_back(std::make_pair(&(*i), form_without_password));
+  }

[stuartmorgan, 2013/09/18 19:23:32]

Please extract this into a helper method; this adds a lot of low-level detail to
what's meant to be a high-level method.

[Raghu Simha, 2013/09/19 21:23:23]

Done.

 
+  // Next, compare the attributes of the PasswordForms in |database_forms|
+  // against those in |item_form_pairs|, and extract password data for each
+  // matching PasswordForm using its corresponding SecKeychainItemRef.
   std::vector<PasswordForm*> merged_forms;
   for (std::vector<PasswordForm*>::iterator i = database_forms->begin();
        i != database_forms->end();) {
     std::vector<PasswordForm*> db_form_container(1, *i);
-    std::vector<PasswordForm*> keychain_matches =
-        keychain_adapter.PasswordsMergeableWithForm(**i);
+    std::vector<PasswordForm*> keychain_matches;
+    for (std::vector<std::pair<SecKeychainItemRef*, PasswordForm*> >::iterator j
+         = item_form_pairs.begin(); j != item_form_pairs.end(); ++j) {
+      if ((*i)->username_value == j->second->username_value &&
+          (*i)->scheme == j->second->scheme &&
+          GURL((*i)->signon_realm) == GURL(j->second->signon_realm)) {

[stuartmorgan, 2013/09/18 19:23:32]

Isn't this just FormsMatchForMerge? Except that it's not clear to me at all that
you are handling blacklist times correctly in this loop, because you aren't
checking for that after you do extract the password later on.

[Raghu Simha, 2013/09/19 21:23:23]

I was getting tripped up by the fact that when FillPasswordFormFromKeychainItem
was being used to extract only password attributes without the password value,
it was (incorrectly) returning a PasswordForm with blacklisted_by_user == true.
I've fixed the logic in FillPasswordFormFromKeychainItem and replaced this block
with a call to FormsMatchForMerge. This should properly handle blacklisted items
by leaving them out.

+        // Create a new object, since the caller is responsible for deleting the
+        // returned forms.
+        PasswordForm* form_with_password = new PasswordForm();
+        internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+            keychain,
+            *(j->first),
+            form_with_password,
+            true);  // Load password attributes and data.
+        keychain_matches.push_back(form_with_password);

[stuartmorgan, 2013/09/18 19:23:32]

What happened to all the logic in MatchingKeychainItems? Where are you handling
auth type? Port? etc.

I don't see how this loop is equivalent to the code it replaces if you have any
non-trivial cases.

[Raghu Simha, 2013/09/19 21:23:23]

My earlier reasoning was as follows:
- Since server, port, and protocol were components of signon_realm, I was
matching them up by parsing the signon_realms into GURLs and comparing them.
- Since auth_type and auth_domain are inferred from scheme, I was matching them
up by comparing the scheme values.

However, you're right that I was neglecting to validate the signon_realm
components via ExtractSignonRealmComponents. I've addressed this in
FormIsValidAndMatchesOtherForm in the latest patch set. Let me know what you
think.

+      }
+    }

[stuartmorgan, 2013/09/18 19:23:32]

Again, please extract a helper method.

[Raghu Simha, 2013/09/19 21:23:23]

Done.

     MergePasswordForms(&keychain_matches, &db_form_container, &merged_forms);
     if (db_form_container.empty()) {
       i = database_forms->erase(i);
     } else {
       ++i;
     }
     STLDeleteElements(&keychain_matches);
   }
+
+  // Clean up temporary PasswordForms and SecKeychainItemRefs.
+  STLDeleteContainerPairSecondPointers(item_form_pairs.begin(),
+                                       item_form_pairs.end());
+  for (std::vector<SecKeychainItemRef>::iterator i = keychain_items.begin();
+       i != keychain_items.end(); ++i) {
+    keychain.Free(*i);
+  }
   return merged_forms;
 }
 
 }  // namespace internal_keychain_helpers
 
 #pragma mark -
 
 MacKeychainPasswordFormAdapter::MacKeychainPasswordFormAdapter(
     const AppleKeychain* keychain)
     : keychain_(keychain), finds_only_owned_(false) {
 }
 
 std::vector<PasswordForm*>
     MacKeychainPasswordFormAdapter::PasswordsFillingForm(
         const PasswordForm& query_form) {
   std::vector<SecKeychainItemRef> keychain_items =
       MatchingKeychainItems(query_form.signon_realm, query_form.scheme,
                             NULL, NULL);
 
   return ConvertKeychainItemsToForms(&keychain_items);
 }
 
 std::vector<PasswordForm*>
     MacKeychainPasswordFormAdapter::PasswordsMergeableWithForm(

[stuartmorgan, 2013/09/18 19:23:32]

Looks like this is dead code now.

[Raghu Simha, 2013/09/19 21:23:23]

Removed and replaced with ExtractPasswordsMergeableWithForm. Done.

         const PasswordForm& query_form) {
   std::string username = UTF16ToUTF8(query_form.username_value);
   std::vector<SecKeychainItemRef> keychain_items =
       MatchingKeychainItems(query_form.signon_realm, query_form.scheme,
                             NULL, username.c_str());
 
   return ConvertKeychainItemsToForms(&keychain_items);
 }
 
 PasswordForm* MacKeychainPasswordFormAdapter::PasswordExactlyMatchingForm(
     const PasswordForm& query_form) {
   SecKeychainItemRef keychain_item = KeychainItemForForm(query_form);
   if (keychain_item) {
     PasswordForm* form = new PasswordForm();
     internal_keychain_helpers::FillPasswordFormFromKeychainItem(*keychain_,
                                                                 keychain_item,
-                                                                form);
+                                                                form,
+                                                                true);
     keychain_->Free(keychain_item);
     return form;
   }
   return NULL;
 }
 
 bool MacKeychainPasswordFormAdapter::HasPasswordsMergeableWithForm(
     const PasswordForm& query_form) {
   std::string username = UTF16ToUTF8(query_form.username_value);
   std::vector<SecKeychainItemRef> matches =
       MatchingKeychainItems(query_form.signon_realm, query_form.scheme,
                             NULL, username.c_str());
   for (std::vector<SecKeychainItemRef>::iterator i = matches.begin();
        i != matches.end(); ++i) {
     keychain_->Free(*i);
   }
 
   return !matches.empty();
 }
 
-std::vector<PasswordForm*>
-    MacKeychainPasswordFormAdapter::GetAllPasswordFormPasswords() {
+std::vector<SecKeychainItemRef>
+    MacKeychainPasswordFormAdapter::GetAllPasswordFormKeychainItems() {
   SecAuthenticationType supported_auth_types[] = {
     kSecAuthenticationTypeHTMLForm,
     kSecAuthenticationTypeHTTPBasic,
     kSecAuthenticationTypeHTTPDigest,
   };
 
   std::vector<SecKeychainItemRef> matches;
   for (unsigned int i = 0; i < arraysize(supported_auth_types); ++i) {
     KeychainSearch keychain_search(*keychain_);
     keychain_search.Init(NULL, 0, kSecProtocolTypeAny, supported_auth_types[i],
                          NULL, NULL, NULL, CreatorCodeForSearch());
     keychain_search.FindMatchingItems(&matches);
   }
+  return matches;
+}
 
-  return ConvertKeychainItemsToForms(&matches);
+std::vector<PasswordForm*>
+    MacKeychainPasswordFormAdapter::GetAllPasswordFormPasswords() {
+  std::vector<SecKeychainItemRef> items = GetAllPasswordFormKeychainItems();
+  return ConvertKeychainItemsToForms(&items);
 }
 
 bool MacKeychainPasswordFormAdapter::AddPassword(const PasswordForm& form) {
   // We should never be trying to store a blacklist in the keychain.
   DCHECK(!form.blacklisted_by_user);
 
   std::string server;
   std::string security_domain;
   int port;
   bool is_secure;
@@ skipping 47 matching lines @@
   finds_only_owned_ = finds_only_owned;
 }
 
 std::vector<PasswordForm*>
     MacKeychainPasswordFormAdapter::ConvertKeychainItemsToForms(
         std::vector<SecKeychainItemRef>* items) {
   std::vector<PasswordForm*> keychain_forms;
   for (std::vector<SecKeychainItemRef>::const_iterator i = items->begin();
        i != items->end(); ++i) {
     PasswordForm* form = new PasswordForm();
-    if (internal_keychain_helpers::FillPasswordFormFromKeychainItem(*keychain_,
-                                                                    *i, form)) {
+    if (internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+            *keychain_, *i, form, true)) {
       keychain_forms.push_back(form);
     }
     keychain_->Free(*i);
   }
   items->clear();
   return keychain_forms;
 }
 
 SecKeychainItemRef MacKeychainPasswordFormAdapter::KeychainItemForForm(
     const PasswordForm& form) {
@@ skipping 396 matching lines @@
   owned_keychain_adapter.SetFindsOnlyOwnedItems(true);
   for (std::vector<PasswordForm*>::const_iterator i = forms.begin();
        i != forms.end(); ++i) {
     owned_keychain_adapter.RemovePassword(**i);
   }
 }
 
 void PasswordStoreMac::CreateNotificationService() {
   notification_service_.reset(content::NotificationService::Create());
 }