--- a/security/nss/lib/dev/dev.h
+++ b/security/nss/lib/dev/dev.h
@@ -947,13 +947,23 @@ nssToken_GetTrustOrder
 );
 
 NSS_EXTERN PRStatus
 nssToken_NofifyCertsNotVisible
 (
   NSSToken *tok
 );
 
+NSS_EXTERN PRStatus
+nssToken_TraverseCertificates
+(
+  NSSToken *token,
+  nssSession *sessionOpt,
+  nssTokenSearchType searchType,
+  PRStatus (* callback)(nssCryptokiObject *instance, void *arg),
+  void *arg
+);
+
 #endif
 
 PR_END_EXTERN_C
 
 #endif /* DEV_H */

--- a/security/nss/lib/dev/devtoken.c
+++ b/security/nss/lib/dev/devtoken.c
@@ -1542,8 +1542,118 @@ NSS_IMPLEMENT PRBool
 nssToken_IsPresent
 (
   NSSToken *token
 )
 {
     return nssSlot_IsTokenPresent(token->slot);
 }
 
+/* Sigh.  The methods to find objects declared above cause problems with
+ * the low-level object cache in the softoken -- the objects are found in 
+ * toto, then one wave of GetAttributes is done, then another.  Having a 
+ * large number of objects causes the cache to be thrashed, as the objects 
+ * are gone before there's any chance to ask for their attributes.
+ * So, for now, bringing back traversal methods for certs.  This way all of 
+ * the cert's attributes can be grabbed immediately after finding it,
+ * increasing the likelihood that the cache takes care of it.
+ */
+NSS_IMPLEMENT PRStatus
+nssToken_TraverseCertificates
+(
+  NSSToken *token,
+  nssSession *sessionOpt,
+  nssTokenSearchType searchType,
+  PRStatus (* callback)(nssCryptokiObject *instance, void *arg),
+  void *arg
+)
+{
+    CK_RV ckrv;
+    CK_ULONG count;
+    CK_OBJECT_HANDLE *objectHandles;
+    CK_ATTRIBUTE_PTR attr;
+    CK_ATTRIBUTE cert_template[2];
+    CK_ULONG ctsize;
+    NSSArena *arena;
+    PRStatus status;
+    PRUint32 arraySize, numHandles;
+    nssCryptokiObject **objects;
+    void *epv = nssToken_GetCryptokiEPV(token);
+    nssSession *session = (sessionOpt) ? sessionOpt : token->defaultSession;
+
+    /* template for all certs */
+    NSS_CK_TEMPLATE_START(cert_template, attr, ctsize);
+    if (searchType == nssTokenSearchType_SessionOnly) {
+	NSS_CK_SET_ATTRIBUTE_ITEM(attr, CKA_TOKEN, &g_ck_false);
+    } else if (searchType == nssTokenSearchType_TokenOnly ||
+               searchType == nssTokenSearchType_TokenForced) {
+	NSS_CK_SET_ATTRIBUTE_ITEM(attr, CKA_TOKEN, &g_ck_true);
+    }
+    NSS_CK_SET_ATTRIBUTE_ITEM(attr, CKA_CLASS, &g_ck_class_cert);
+    NSS_CK_TEMPLATE_FINISH(cert_template, attr, ctsize);
+
+    /* the arena is only for the array of object handles */
+    arena = nssArena_Create();
+    if (!arena) {
+	return PR_FAILURE;
+    }
+    arraySize = OBJECT_STACK_SIZE;
+    numHandles = 0;
+    objectHandles = nss_ZNEWARRAY(arena, CK_OBJECT_HANDLE, arraySize);
+    if (!objectHandles) {
+	goto loser;
+    }
+    nssSession_EnterMonitor(session); /* ==== session lock === */
+    /* Initialize the find with the template */
+    ckrv = CKAPI(epv)->C_FindObjectsInit(session->handle, 
+                                         cert_template, ctsize);
+    if (ckrv != CKR_OK) {
+	nssSession_ExitMonitor(session);
+	goto loser;
+    }
+    while (PR_TRUE) {
+	/* Issue the find for up to arraySize - numHandles objects */
+	ckrv = CKAPI(epv)->C_FindObjects(session->handle, 
+	                                 objectHandles + numHandles, 
+	                                 arraySize - numHandles, 
+	                                 &count);
+	if (ckrv != CKR_OK) {
+	    nssSession_ExitMonitor(session);
+	    goto loser;
+	}
+	/* bump the number of found objects */
+	numHandles += count;
+	if (numHandles < arraySize) {
+	    break;
+	}
+	/* the array is filled, double it and continue */
+	arraySize *= 2;
+	objectHandles = nss_ZREALLOCARRAY(objectHandles, 
+	                                  CK_OBJECT_HANDLE, 
+	                                  arraySize);
+	if (!objectHandles) {
+	    nssSession_ExitMonitor(session);
+	    goto loser;
+	}
+    }
+    ckrv = CKAPI(epv)->C_FindObjectsFinal(session->handle);
+    nssSession_ExitMonitor(session); /* ==== end session lock === */
+    if (ckrv != CKR_OK) {
+	goto loser;
+    }
+    if (numHandles > 0) {
+	objects = create_objects_from_handles(token, session,
+	                                      objectHandles, numHandles);
+	if (objects) {
+	    nssCryptokiObject **op;
+	    for (op = objects; *op; op++) {
+		status = (*callback)(*op, arg);
+	    }
+	    nss_ZFreeIf(objects);
+	}
+    }
+    nssArena_Destroy(arena);
+    return PR_SUCCESS;
+loser:
+    nssArena_Destroy(arena);
+    return PR_FAILURE;
+}
+

--- a/security/nss/lib/pki/pkibase.c
+++ b/security/nss/lib/pki/pkibase.c
@@ -711,17 +711,17 @@ find_object_in_collection
 	if (i == MAX_ITEMS_FOR_UID) {
 	    return node;
 	}
 	link = PR_NEXT_LINK(link);
     }
     return (pkiObjectCollectionNode *)NULL;
 }
 
-static PRStatus
+static pkiObjectCollectionNode *
 add_object_instance
 (
   nssPKIObjectCollection *collection,
   nssCryptokiObject *instance
 )
 {
     PRUint32 i;
     PRStatus status;
@@ -735,17 +735,17 @@ add_object_instance
      * instance is already in the collection, and we have nothing to do.
      */
     node = find_instance_in_collection(collection, instance);
     if (node) {
 	/* The collection is assumed to take over the instance.  Since we
 	 * are not using it, it must be destroyed.
 	 */
 	nssCryptokiObject_Destroy(instance);
-	return PR_SUCCESS;
+	return node;
     }
     mark = nssArena_Mark(collection->arena);
     if (!mark) {
 	goto loser;
     }
     status = (*collection->getUIDFromInstance)(instance, uid, 
                                                collection->arena);
     if (status != PR_SUCCESS) {
@@ -775,42 +775,43 @@ add_object_instance
 	}
 	node->haveObject = PR_FALSE;
 	PR_INIT_CLIST(&node->link);
 	PR_INSERT_BEFORE(&node->link, &collection->head);
 	collection->size++;
 	status = PR_SUCCESS;
     }
     nssArena_Unmark(collection->arena, mark);
-    return status;
+    return node;
 loser:
     if (mark) {
 	nssArena_Release(collection->arena, mark);
     }
     nssCryptokiObject_Destroy(instance);
-    return PR_FAILURE;
+    return (pkiObjectCollectionNode *)NULL;
 }
 
 NSS_IMPLEMENT PRStatus
 nssPKIObjectCollection_AddInstances
 (
   nssPKIObjectCollection *collection,
   nssCryptokiObject **instances,
   PRUint32 numInstances
 )
 {
     PRStatus status = PR_SUCCESS;
     PRUint32 i = 0;
+    pkiObjectCollectionNode *node;
     if (instances) {
 	for (; *instances; instances++, i++) {
 	    if (numInstances > 0 && i == numInstances) {
 		break;
 	    }
-	    status = add_object_instance(collection, *instances);
-	    if (status != PR_SUCCESS) {
+	    node = add_object_instance(collection, *instances);
+	    if (node == NULL) {
 		goto loser;
 	    }
 	}
     }
     return status;
 loser:
     /* free the remaining instances */
     for (; *instances; instances++, i++) {
@@ -886,16 +887,45 @@ nssPKIObjectCollection_Traverse
 	                                     callback->arg);
 	    break;
 	}
 	link = PR_NEXT_LINK(link);
     }
     return PR_SUCCESS;
 }
 
+NSS_IMPLEMENT PRStatus
+nssPKIObjectCollection_AddInstanceAsObject
+(
+  nssPKIObjectCollection *collection,
+  nssCryptokiObject *instance
+)
+{
+    pkiObjectCollectionNode *node;
+    node = add_object_instance(collection, instance);
+    if (node == NULL) {
+	return PR_FAILURE;
+    }
+    if (!node->haveObject) {
+	node->object = (*collection->createObject)(node->object);
+	node->haveObject = PR_TRUE;
+    }
+#ifdef NSS_3_4_CODE
+    else {
+	/* The instance was added to a pre-existing node.  This
+	 * function is *only* being used for certificates, and having
+	 * multiple instances of certs in 3.X requires updating the
+	 * CERTCertificate.
+	 */
+	STAN_ForceCERTCertificateUpdate((NSSCertificate *)node->object);
+    }
+#endif
+    return PR_SUCCESS;
+}
+
 /*
  * Certificate collections
  */
 
 static void
 cert_destroyObject(nssPKIObject *o)
 {
     NSSCertificate *c = (NSSCertificate *)o;

--- a/security/nss/lib/pki/pkim.h
+++ b/security/nss/lib/pki/pkim.h
@@ -491,16 +491,28 @@ nssPKIObjectCollection_AddInstances
  */
 NSS_EXTERN PRStatus
 nssPKIObjectCollection_Traverse
 (
   nssPKIObjectCollection *collection,
   nssPKIObjectCallback *callback
 );
 
+/* This function is being added for NSS 3.5.  It corresponds to the function
+ * nssToken_TraverseCertificates.  The idea is to use the collection during
+ * a traversal, creating certs each time a new instance is added for which
+ * a cert does not already exist.
+ */
+NSS_EXTERN PRStatus
+nssPKIObjectCollection_AddInstanceAsObject
+(
+  nssPKIObjectCollection *collection,
+  nssCryptokiObject *instance
+);
+
 /* nssPKIObjectCollection_GetCertificates
  *
  * Get all of the certificates in the collection. 
  */
 NSS_EXTERN NSSCertificate **
 nssPKIObjectCollection_GetCertificates
 (
   nssPKIObjectCollection *collection,

--- a/security/nss/lib/pki/trustdomain.c
+++ b/security/nss/lib/pki/trustdomain.c
@@ -1030,16 +1030,23 @@ NSSTrustDomain_FindUserCertificatesForEm
   PRUint32 rvLimit, /* zero for no limit */
   NSSArena *arenaOpt
 )
 {
     nss_SetError(NSS_ERROR_NOT_FOUND);
     return NULL;
 }
 
+static PRStatus
+collector(nssCryptokiObject *instance, void *arg)
+{
+    nssPKIObjectCollection *collection = (nssPKIObjectCollection *)arg;
+    return nssPKIObjectCollection_AddInstanceAsObject(collection, instance);
+}
+
 NSS_IMPLEMENT PRStatus *
 NSSTrustDomain_TraverseCertificates
 (
   NSSTrustDomain *td,
   PRStatus (*callback)(NSSCertificate *c, void *arg),
   void *arg
 )
 {
@@ -1047,16 +1054,17 @@ NSSTrustDomain_TraverseCertificates
     NSSToken *token = NULL;
     NSSSlot **slots = NULL;
     NSSSlot **slotp;
     nssPKIObjectCollection *collection = NULL;
     nssPKIObjectCallback pkiCallback;
     nssUpdateLevel updateLevel;
     NSSCertificate **cached = NULL;
     nssList *certList;
+
     certList = nssList_Create(NULL, PR_FALSE);
     if (!certList) return NULL;
     (void *)nssTrustDomain_GetCertsFromCache(td, certList);
     cached = get_certs_from_list(certList);
     collection = nssCertificateCollection_Create(td, cached);
     nssCertificateArray_Destroy(cached);
     nssList_Destroy(certList);
     if (!collection) {
@@ -1068,40 +1076,33 @@ NSSTrustDomain_TraverseCertificates
 	goto loser;
     }
     /* iterate over the slots */
     for (slotp = slots; *slotp; slotp++) {
 	/* get the token for the slot, if present */
 	token = nssSlot_GetToken(*slotp);
 	if (token) {
 	    nssSession *session;
-	    nssCryptokiObject **instances;
 	    nssTokenSearchType tokenOnly = nssTokenSearchType_TokenOnly;
 	    /* get a session for the token */
 	    session = nssTrustDomain_GetSessionForToken(td, token);
 	    if (!session) {
 		nssToken_Destroy(token);
 		goto loser;
 	    }
 	    /* perform the traversal */
-	    instances = nssToken_FindCertificates(token,
-	                                          session,
-	                                          tokenOnly,
-	                                          0, &status);
+	    status = nssToken_TraverseCertificates(token,
+	                                           session,
+	                                           tokenOnly,
+	                                           collector,
+	                                           collection);
 	    nssToken_Destroy(token);
 	    if (status != PR_SUCCESS) {
 		goto loser;
 	    }
-	    /* add the found certificates to the collection */
-	    status = nssPKIObjectCollection_AddInstances(collection, 
-	                                                 instances, 0);
-	    nss_ZFreeIf(instances);
-	    if (status != PR_SUCCESS) {
-		goto loser;
-	    }
 	}
     }
 
     /* Traverse the collection */
     pkiCallback.func.cert = callback;
     pkiCallback.arg = arg;
     status = nssPKIObjectCollection_Traverse(collection, &pkiCallback);
     /* clean up */