cookie: store cookies per top-level-domain-specific hash table

This makes libcurl handle thousands of cookies much better and speedier.

Closes #2440

2 files changed, 157 insertions, 87 deletions

diff --git a/lib/cookie.c b/lib/cookie.c
index 1f932d78c..027fa0977 100644
--- a/lib/cookie.c
+++ b/lib/cookie.c
@@ -90,6 +90,7 @@ Example set of cookies:
 
 #include "urldata.h"
 #include "cookie.h"
+#include "hash.h"
 #include "strtok.h"
 #include "sendf.h"
 #include "slist.h"
@@ -143,6 +144,28 @@ static bool tailmatch(const char *cooke_domain, const char *hostname)
 }
 
 /*
+ * Return true if the given string is an IP(v4|v6) address.
+ */
+static bool isip(const char *domain)
+{
+  struct in_addr addr;
+#ifdef ENABLE_IPV6
+  struct in6_addr addr6;
+#endif
+
+  if(Curl_inet_pton(AF_INET, domain, &addr)
+#ifdef ENABLE_IPV6
+     || Curl_inet_pton(AF_INET6, domain, &addr6)
+#endif
+    ) {
+    /* domain name given as IP address */
+    return TRUE;
+  }
+
+  return FALSE;
+}
+
+/*
  * matching cookie path and url path
  * RFC6265 5.1.4 Paths and Path-Match
  */
@@ -218,6 +241,49 @@ pathmatched:
 }
 
 /*
+ * Return the top-level domain, for optimal hashing.
+ */
+static const char *get_top_domain(const char * const domain, size_t *outlen)
+{
+  size_t len;
+  const char *first, *last;
+
+  if(!domain)
+    return NULL;
+
+  len = strlen(domain);
+  first = memchr(domain, '.', len);
+  last = memrchr(domain, '.', len);
+
+  if(outlen)
+    *outlen = len;
+
+  if(first == last)
+    return domain;
+
+  first = memrchr(domain, '.', (size_t)(last - domain - 1));
+  if(outlen)
+    *outlen = len - (size_t)(first - domain) - 1;
+
+  return first + 1;
+}
+
+/*
+ * Hash this domain.
+ */
+static size_t cookiehash(const char * const domain)
+{
+  const char *top;
+  size_t len;
+
+  if(!domain || isip(domain))
+    return 0;
+
+  top = get_top_domain(domain, &len);
+  return Curl_hash_str((void *) top, len, COOKIE_HASH_SIZE);
+}
+
+/*
  * cookie path sanitize
  */
 static char *sanitize_cookie_path(const char *cookie_path)
@@ -303,48 +369,29 @@ static void remove_expired(struct CookieInfo *cookies)
 {
   struct Cookie *co, *nx, *pv;
   curl_off_t now = (curl_off_t)time(NULL);
-
-  co = cookies->cookies;
-  pv = NULL;
-  while(co) {
-    nx = co->next;
-    if(co->expires && co->expires < now) {
-      if(!pv) {
-        cookies->cookies = co->next;
+  unsigned int i;
+
+  for(i = 0; i < COOKIE_HASH_SIZE; i++) {
+    co = cookies->cookies[i];
+    pv = NULL;
+    while(co) {
+      nx = co->next;
+      if(co->expires && co->expires < now) {
+        if(!pv) {
+          cookies->cookies[i] = co->next;
+        }
+        else {
+          pv->next = co->next;
+        }
+        cookies->numcookies--;
+        freecookie(co);
       }
       else {
-        pv->next = co->next;
+        pv = co;
       }
-      cookies->numcookies--;
-      freecookie(co);
-    }
-    else {
-      pv = co;
+      co = nx;
     }
-    co = nx;
-  }
-}
-
-/*
- * Return true if the given string is an IP(v4|v6) address.
- */
-static bool isip(const char *domain)
-{
-  struct in_addr addr;
-#ifdef ENABLE_IPV6
-  struct in6_addr addr6;
-#endif
-
-  if(Curl_inet_pton(AF_INET, domain, &addr)
-#ifdef ENABLE_IPV6
-     || Curl_inet_pton(AF_INET6, domain, &addr6)
-#endif
-    ) {
-    /* domain name given as IP address */
-    return TRUE;
   }
-
-  return FALSE;
 }
 
 /****************************************************************************
@@ -381,6 +428,7 @@ Curl_cookie_add(struct Curl_easy *data,
   time_t now = time(NULL);
   bool replace_old = FALSE;
   bool badcookie = FALSE; /* cookies are good by default. mmmmm yummy */
+  size_t myhash;
 
 #ifdef USE_LIBPSL
   const psl_ctx_t *psl;
@@ -838,7 +886,8 @@ Curl_cookie_add(struct Curl_easy *data,
   }
 #endif
 
-  clist = c->cookies;
+  myhash = cookiehash(co->domain);
+  clist = c->cookies[myhash];
   replace_old = FALSE;
   while(clist) {
     if(strcasecompare(clist->name, co->name)) {
@@ -924,7 +973,7 @@ Curl_cookie_add(struct Curl_easy *data,
     if(lastc)
       lastc->next = co;
     else
-      c->cookies = co;
+      c->cookies[myhash] = co;
     c->numcookies++; /* one more cookie in the jar */
   }
 
@@ -1137,8 +1186,9 @@ struct Cookie *Curl_cookie_getlist(struct CookieInfo *c,
   struct Cookie *mainco = NULL;
   size_t matches = 0;
   bool is_ip;
+  const size_t myhash = cookiehash(host);
 
-  if(!c || !c->cookies)
+  if(!c || !c->cookies[myhash])
     return NULL; /* no cookie struct or no cookies in the struct */
 
   /* at first, remove expired cookies */
@@ -1147,7 +1197,7 @@ struct Cookie *Curl_cookie_getlist(struct CookieInfo *c,
   /* check if host is an IP(v4|v6) address */
   is_ip = isip(host);
 
-  co = c->cookies;
+  co = c->cookies[myhash];
 
   while(co) {
     /* only process this cookie if it is not expired or had no expire
@@ -1235,8 +1285,11 @@ struct Cookie *Curl_cookie_getlist(struct CookieInfo *c,
 void Curl_cookie_clearall(struct CookieInfo *cookies)
 {
   if(cookies) {
-    Curl_cookie_freelist(cookies->cookies);
-    cookies->cookies = NULL;
+    unsigned int i;
+    for(i = 0; i < COOKIE_HASH_SIZE; i++) {
+      Curl_cookie_freelist(cookies->cookies[i]);
+      cookies->cookies[i] = NULL;
+    }
     cookies->numcookies = 0;
   }
 }
@@ -1270,31 +1323,37 @@ void Curl_cookie_freelist(struct Cookie *co)
 void Curl_cookie_clearsess(struct CookieInfo *cookies)
 {
   struct Cookie *first, *curr, *next, *prev = NULL;
+  unsigned int i;
 
-  if(!cookies || !cookies->cookies)
+  if(!cookies)
     return;
 
-  first = curr = prev = cookies->cookies;
+  for(i = 0; i < COOKIE_HASH_SIZE; i++) {
+    if(!cookies->cookies[i])
+      continue;
+
+    first = curr = prev = cookies->cookies[i];
 
-  for(; curr; curr = next) {
-    next = curr->next;
-    if(!curr->expires) {
-      if(first == curr)
-        first = next;
+    for(; curr; curr = next) {
+      next = curr->next;
+      if(!curr->expires) {
+        if(first == curr)
+          first = next;
 
-      if(prev == curr)
-        prev = next;
-      else
-        prev->next = next;
+        if(prev == curr)
+          prev = next;
+        else
+          prev->next = next;
 
-      freecookie(curr);
-      cookies->numcookies--;
+        freecookie(curr);
+        cookies->numcookies--;
+      }
+      else
+        prev = curr;
     }
-    else
-      prev = curr;
-  }
 
-  cookies->cookies = first;
+    cookies->cookies[i] = first;
+  }
 }
 
 
@@ -1307,9 +1366,12 @@ void Curl_cookie_clearsess(struct CookieInfo *cookies)
  ****************************************************************************/
 void Curl_cookie_cleanup(struct CookieInfo *c)
 {
+  unsigned int i;
+
   if(c) {
     free(c->filename);
-    Curl_cookie_freelist(c->cookies);
+    for(i = 0; i < COOKIE_HASH_SIZE; i++)
+      Curl_cookie_freelist(c->cookies[i]);
     free(c); /* free the base struct as well */
   }
 }
@@ -1358,6 +1420,7 @@ static int cookie_output(struct CookieInfo *c, const char *dumphere)
   FILE *out;
   bool use_stdout = FALSE;
   char *format_ptr;
+  unsigned int i;
 
   if((NULL == c) || (0 == c->numcookies))
     /* If there are no known cookies, we don't write or even create any
@@ -1383,18 +1446,20 @@ static int cookie_output(struct CookieInfo *c, const char *dumphere)
         "# This file was generated by libcurl! Edit at your own risk.\n\n",
         out);
 
-  for(co = c->cookies; co; co = co->next) {
-    if(!co->domain)
-      continue;
-    format_ptr = get_netscape_format(co);
-    if(format_ptr == NULL) {
-      fprintf(out, "#\n# Fatal libcurl error\n");
-      if(!use_stdout)
-        fclose(out);
-      return 1;
+  for(i = 0; i < COOKIE_HASH_SIZE; i++) {
+    for(co = c->cookies[i]; co; co = co->next) {
+      if(!co->domain)
+        continue;
+      format_ptr = get_netscape_format(co);
+      if(format_ptr == NULL) {
+        fprintf(out, "#\n# Fatal libcurl error\n");
+        if(!use_stdout)
+          fclose(out);
+        return 1;
+      }
+      fprintf(out, "%s\n", format_ptr);
+      free(format_ptr);
     }
-    fprintf(out, "%s\n", format_ptr);
-    free(format_ptr);
   }
 
   if(!use_stdout)
@@ -1409,26 +1474,29 @@ static struct curl_slist *cookie_list(struct Curl_easy *data)
   struct curl_slist *beg;
   struct Cookie *c;
   char *line;
+  unsigned int i;
 
   if((data->cookies == NULL) ||
       (data->cookies->numcookies == 0))
     return NULL;
 
-  for(c = data->cookies->cookies; c; c = c->next) {
-    if(!c->domain)
-      continue;
-    line = get_netscape_format(c);
-    if(!line) {
-      curl_slist_free_all(list);
-      return NULL;
-    }
-    beg = Curl_slist_append_nodup(list, line);
-    if(!beg) {
-      free(line);
-      curl_slist_free_all(list);
-      return NULL;
+  for(i = 0; i < COOKIE_HASH_SIZE; i++) {
+    for(c = data->cookies->cookies[i]; c; c = c->next) {
+      if(!c->domain)
+        continue;
+      line = get_netscape_format(c);
+      if(!line) {
+        curl_slist_free_all(list);
+        return NULL;
+      }
+      beg = Curl_slist_append_nodup(list, line);
+      if(!beg) {
+        free(line);
+        curl_slist_free_all(list);
+        return NULL;
+      }
+      list = beg;
     }
-    list = beg;
   }
 
   return list;
diff --git a/lib/cookie.h b/lib/cookie.h
index 5342d528c..299eb52e7 100644
--- a/lib/cookie.h
+++ b/lib/cookie.h
@@ -45,9 +45,11 @@ struct Cookie {
   bool httponly;     /* true if the httponly directive is present */
 };
 
+#define COOKIE_HASH_SIZE 256
+
 struct CookieInfo {
   /* linked list of cookies we know of */
-  struct Cookie *cookies;
+  struct Cookie *cookies[COOKIE_HASH_SIZE];
 
   char *filename;  /* file we read from/write to */
   bool running;    /* state info, for cookie adding information */