[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 41 matching lines @@
           form->blacklisted_by_user = true;
         }
         break;
     }
   }
   keychain.ItemFreeAttributesAndData(attrList, password_data);
 
   // kSecNegativeItemAttr doesn't seem to actually be in widespread use. In
   // practice, other browsers seem to use a "" or " " password (and a special
   // user name) to indicated blacklist entries.
-  if (form->password_value.empty() || EqualsASCII(form->password_value, " ")) {
+  if (extract_password_data && (form->password_value.empty() ||
+                                EqualsASCII(form->password_value, " "))) {
     form->blacklisted_by_user = true;
   }
 
   form->origin = URLFromComponents(form->ssl_valid, server, port, path);
   // TODO(stuartmorgan): Handle proxies, which need a different signon_realm
   // format.
   form->signon_realm = form->origin.GetOrigin().spec();
   if (form->scheme != PasswordForm::SCHEME_HTML) {
     form->signon_realm.append(security_domain);
   }
@@ skipping 92 matching lines @@
 
   // Add in the blacklist entries from the database.
   merged_forms->insert(merged_forms->end(),
                        database_blacklist_forms.begin(),
                        database_blacklist_forms.end());
 
   // Clear out all the Keychain entries we used.
   DeleteVectorElementsInSet(keychain_forms, used_keychain_forms);
 }
 
+std::vector<ItemFormPair> ExtractAllKeychainItemAttributesIntoPasswordForms(
+    std::vector<SecKeychainItemRef>* keychain_items,
+    const AppleKeychain& keychain) {
+  DCHECK(keychain_items);
+  MacKeychainPasswordFormAdapter keychain_adapter(&keychain);
+  *keychain_items = keychain_adapter.GetAllPasswordFormKeychainItems();
+  std::vector<ItemFormPair> 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));
+  }
+  return item_form_pairs;
+}
+
 std::vector<PasswordForm*> GetPasswordsForForms(
     const AppleKeychain& keychain,
     std::vector<PasswordForm*>* database_forms) {
-  MacKeychainPasswordFormAdapter keychain_adapter(&keychain);
+  // 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 avoids individually searching through the keychain for passwords
+  // matching each form in |database_forms|, and results in a significant
+  // performance gain, replacing O(N) keychain search operations with a single
+  // operation that loads all keychain items, and then selective reads of only
+  // the relevant passwords. See crbug.com/263685.
+  std::vector<SecKeychainItemRef> keychain_items;
+  std::vector<ItemFormPair> item_form_pairs =
+      ExtractAllKeychainItemAttributesIntoPasswordForms(&keychain_items,
+                                                        keychain);
 
+  // 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);
+        ExtractPasswordsMergeableWithForm(keychain, item_form_pairs, **i);
     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;
 }
 
+// TODO(stuartmorgan): signon_realm for proxies is not yet supported.
+bool ExtractSignonRealmComponents(
+    const std::string& signon_realm, std::string* server, int* port,
+    bool* is_secure, std::string* security_domain) {
+  // The signon_realm will be the Origin portion of a URL for an HTML form,
+  // and the same but with the security domain as a path for HTTP auth.
+  GURL realm_as_url(signon_realm);
+  if (!realm_as_url.is_valid()) {
+    return false;
+  }
+
+  if (server)
+    *server = realm_as_url.host();
+  if (is_secure)
+    *is_secure = realm_as_url.SchemeIsSecure();
+  if (port)
+    *port = realm_as_url.has_port() ? atoi(realm_as_url.port().c_str()) : 0;
+  if (security_domain) {
+    // Strip the leading '/' off of the path to get the security domain.
+    if (realm_as_url.path().length() > 0)
+      *security_domain = realm_as_url.path().substr(1);
+    else
+      security_domain->clear();
+  }
+  return true;
+}
+
+bool FormIsValidAndMatchesOtherForm(const PasswordForm& query_form,
+                                    const PasswordForm& other_form) {
+  std::string server;
+  std::string security_domain;
+  int port;
+  bool is_secure;
+  if (!ExtractSignonRealmComponents(query_form.signon_realm, &server, &port,
+                                    &is_secure, &security_domain)) {
+    return false;
+  }
+  return internal_keychain_helpers::FormsMatchForMerge(query_form, other_form);
+}
+
+std::vector<PasswordForm*> ExtractPasswordsMergeableWithForm(
+    const AppleKeychain& keychain,
+    const std::vector<ItemFormPair>& item_form_pairs,
+    const PasswordForm& query_form) {
+  std::vector<PasswordForm*> matches;
+  for (std::vector<ItemFormPair>::const_iterator i = item_form_pairs.begin();
+       i != item_form_pairs.end(); ++i) {
+    if (FormIsValidAndMatchesOtherForm(query_form, *(i->second))) {
+      // Create a new object, since the caller is responsible for deleting the
+      // returned forms.
+      scoped_ptr<PasswordForm> form_with_password(new PasswordForm());
+      internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+          keychain,
+          *(i->first),
+          form_with_password.get(),
+          true);  // Load password attributes and data.
+      // Do not include blacklisted items found in the keychain.
+      if (!form_with_password->blacklisted_by_user)
+        matches.push_back(form_with_password.release());
+    }
+  }
+  return matches;
+}
+
 }  // 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(
-        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;
-  if (!ExtractSignonRealmComponents(form.signon_realm, &server, &port,
-                                    &is_secure, &security_domain)) {
+  if (!internal_keychain_helpers::ExtractSignonRealmComponents(
+           form.signon_realm, &server, &port, &is_secure, &security_domain)) {
     return false;
   }
   std::string username = UTF16ToUTF8(form.username_value);
   std::string password = UTF16ToUTF8(form.password_value);
   std::string path = form.origin.path();
   SecProtocolType protocol = is_secure ? kSecProtocolTypeHTTPS
                                        : kSecProtocolTypeHTTP;
   SecKeychainItemRef new_item = NULL;
   OSStatus result = keychain_->AddInternetPassword(
       NULL, server.size(), server.c_str(),
@@ skipping 35 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 23 matching lines @@
     MacKeychainPasswordFormAdapter::MatchingKeychainItems(
         const std::string& signon_realm,
         autofill::PasswordForm::Scheme scheme,
         const char* path, const char* username) {
   std::vector<SecKeychainItemRef> matches;
 
   std::string server;
   std::string security_domain;
   int port;
   bool is_secure;
-  if (!ExtractSignonRealmComponents(signon_realm, &server, &port,
-                                    &is_secure, &security_domain)) {
+  if (!internal_keychain_helpers::ExtractSignonRealmComponents(
+           signon_realm, &server, &port, &is_secure, &security_domain)) {
     // TODO(stuartmorgan): Proxies will currently fail here, since their
     // signon_realm is not a URL. We need to detect the proxy case and handle
     // it specially.
     return matches;
   }
   SecProtocolType protocol = is_secure ? kSecProtocolTypeHTTPS
                                        : kSecProtocolTypeHTTP;
   SecAuthenticationType auth_type = AuthTypeForScheme(scheme);
   const char* auth_domain = (scheme == PasswordForm::SCHEME_HTML) ?
       NULL : security_domain.c_str();
   KeychainSearch keychain_search(*keychain_);
   keychain_search.Init(server.c_str(), port, protocol, auth_type,
                        auth_domain, path, username, CreatorCodeForSearch());
   keychain_search.FindMatchingItems(&matches);
   return matches;
 }
 
-// TODO(stuartmorgan): signon_realm for proxies is not yet supported.
-bool MacKeychainPasswordFormAdapter::ExtractSignonRealmComponents(
-    const std::string& signon_realm, std::string* server, int* port,
-    bool* is_secure, std::string* security_domain) {
-  // The signon_realm will be the Origin portion of a URL for an HTML form,
-  // and the same but with the security domain as a path for HTTP auth.
-  GURL realm_as_url(signon_realm);
-  if (!realm_as_url.is_valid()) {
-    return false;
-  }
-
-  if (server)
-    *server = realm_as_url.host();
-  if (is_secure)
-    *is_secure = realm_as_url.SchemeIsSecure();
-  if (port)
-    *port = realm_as_url.has_port() ? atoi(realm_as_url.port().c_str()) : 0;
-  if (security_domain) {
-    // Strip the leading '/' off of the path to get the security domain.
-    if (realm_as_url.path().length() > 0)
-      *security_domain = realm_as_url.path().substr(1);
-    else
-      security_domain->clear();
-  }
-  return true;
-}
-
 // Returns the Keychain SecAuthenticationType type corresponding to |scheme|.
 SecAuthenticationType MacKeychainPasswordFormAdapter::AuthTypeForScheme(
     PasswordForm::Scheme scheme) {
   switch (scheme) {
     case PasswordForm::SCHEME_HTML:   return kSecAuthenticationTypeHTMLForm;
     case PasswordForm::SCHEME_BASIC:  return kSecAuthenticationTypeHTTPBasic;
     case PasswordForm::SCHEME_DIGEST: return kSecAuthenticationTypeHTTPDigest;
     case PasswordForm::SCHEME_OTHER:  return kSecAuthenticationTypeDefault;
   }
   NOTREACHED();
@@ skipping 308 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());
 }