diff options
author | Simon Kelley <simon@thekelleys.org.uk> | 2022-11-21 16:40:53 +0000 |
---|---|---|
committer | Simon Kelley <simon@thekelleys.org.uk> | 2022-11-21 16:40:53 +0000 |
commit | 881eaa4dbcd813f08d741909aaf48e15267326fd (patch) | |
tree | 17fb5f88690d4b74499e2f026c959af41c6cbd0c | |
parent | d6d7527c95ddd2d1ece9da3adba1502b09731602 (diff) | |
download | dnsmasq-881eaa4dbcd813f08d741909aaf48e15267326fd.tar.gz |
Optimise readng large number --server options at start up.
When re-reading upstream servers from /etc/resolv.conf or other
sources that can change dnsmasq tries to avoid memory fragmentation by
re-using existing records that are being re-read unchanged. This
involves seaching all the server records for each new one installed.
During startup this search is pointless, and can cause long start
times with thousands of --server options because the work needed is
O(n^2). Handle this case more intelligently. Thanks to Ye Zhou for
spotting the problem and an initial patch.
-rw-r--r-- | CHANGELOG | 10 | ||||
-rw-r--r-- | src/domain-match.c | 55 | ||||
-rw-r--r-- | src/option.c | 5 |
3 files changed, 49 insertions, 21 deletions
@@ -49,6 +49,16 @@ version 2.88 in the domain it attests to be returned as unvalidated, and not as a validation error. + Optimise reading large numbers of --server options. When re-reading + upstream servers from /etc/resolv.conf or other sources that + can change dnsmasq tries to avoid memory fragmentation by re-using + existing records that are being re-read unchanged. This involves + seaching all the server records for each new one installed. + During startup this search is pointless, and can cause long + start times with thousands of --server options because the work + needed is O(n^2). Handle this case more intelligently. + Thanks to Ye Zhou for spotting the problem and an initial patch. + version 2.87 Allow arbitrary prefix lengths in --rev-server and diff --git a/src/domain-match.c b/src/domain-match.c index 76a1109..bef460a 100644 --- a/src/domain-match.c +++ b/src/domain-match.c @@ -546,11 +546,23 @@ static int order_qsort(const void *a, const void *b) return rc; } + +/* When loading large numbers of server=.... lines during startup, + there's no possibility that there will be server records that can be reused, but + searching a long list for each server added grows as O(n^2) and slows things down. + This flag is set only if is known there may be free server records that can be reused. + There's a call to mark_servers(0) in read_opts() to reset the flag before + main config read. */ + +static int maybe_free_servers = 0; + /* Must be called before add_update_server() to set daemon->servers_tail */ void mark_servers(int flag) { struct server *serv, **up; + maybe_free_servers = !!flag; + daemon->servers_tail = NULL; /* mark everything with argument flag */ @@ -667,27 +679,30 @@ int add_update_server(int flags, and move to the end of the list, for order. The entry found may already be at the end. */ struct server **up, *tmp; - - for (serv = daemon->servers, up = &daemon->servers; serv; serv = tmp) - { - tmp = serv->next; - if ((serv->flags & SERV_MARK) && - hostname_isequal(alloc_domain, serv->domain)) - { - /* Need to move down? */ - if (serv->next) - { - *up = serv->next; - daemon->servers_tail->next = serv; - daemon->servers_tail = serv; - serv->next = NULL; - } - break; - } - else - up = &serv->next; - } + serv = NULL; + + if (maybe_free_servers) + for (serv = daemon->servers, up = &daemon->servers; serv; serv = tmp) + { + tmp = serv->next; + if ((serv->flags & SERV_MARK) && + hostname_isequal(alloc_domain, serv->domain)) + { + /* Need to move down? */ + if (serv->next) + { + *up = serv->next; + daemon->servers_tail->next = serv; + daemon->servers_tail = serv; + serv->next = NULL; + } + break; + } + else + up = &serv->next; + } + if (serv) { free(alloc_domain); diff --git a/src/option.c b/src/option.c index 371a32d..6a63268 100644 --- a/src/option.c +++ b/src/option.c @@ -5753,7 +5753,10 @@ void read_opts(int argc, char **argv, char *compile_opts) #endif add_txt("servers.bind", NULL, TXT_STAT_SERVERS); #endif - + + /* See comment above make_servers(). Optimises server-read code. */ + mark_servers(0); + while (1) { #ifdef HAVE_GETOPT_LONG |