From c990eadd12779a22f73c834db8e1c30c6dcf0f9c Mon Sep 17 00:00:00 2001 From: Lauri Kasanen Date: Fri, 30 Mar 2018 17:35:46 +0300 Subject: cookie: store cookies per top-level-domain-specific hash table This makes libcurl handle thousands of cookies much better and speedier. Closes #2440 --- lib/cookie.c | 240 +++++++++++++++++++++++++++++++++++------------------- lib/cookie.h | 4 +- tests/data/test46 | 4 +- 3 files changed, 159 insertions(+), 89 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" @@ -142,6 +143,28 @@ static bool tailmatch(const char *cooke_domain, const char *hostname) return FALSE; } +/* + * 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 @@ -217,6 +240,49 @@ pathmatched: return ret; } +/* + * 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 */ @@ -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 */ diff --git a/tests/data/test46 b/tests/data/test46 index abcbda8e6..e78aa72a3 100644 --- a/tests/data/test46 +++ b/tests/data/test46 @@ -74,8 +74,6 @@ Cookie: empty=; mooo2=indeed2; mooo=indeed # https://curl.haxx.se/docs/http-cookies.html # This file was generated by libcurl! Edit at your own risk. -www.fake.come FALSE / FALSE 2022144953 cookiecliente si -www.loser.com FALSE / FALSE 2139150993 UID 99 %HOSTIP FALSE / FALSE 1739150993 mooo indeed #HttpOnly_%HOSTIP FALSE /want FALSE 1739150993 mooo2 indeed2 %HOSTIP FALSE /want FALSE 0 empty @@ -84,6 +82,8 @@ www.loser.com FALSE / FALSE 2139150993 UID 99 %HOSTIP FALSE / FALSE 0 ASPSESSIONIDQGGQQSJJ GKNBDIFAAOFDPDAIEAKDIBKE %HOSTIP FALSE / FALSE 0 justaname %HOSTIP FALSE /want/ FALSE 0 simplyhuge zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz +www.fake.come FALSE / FALSE 2022144953 cookiecliente si +www.loser.com FALSE / FALSE 2139150993 UID 99 -- cgit v1.2.3