Package: fetchmail
Version: 6.3.26-1+b1
Severity: normal
Tags: patch upstream
Dear Maintainer,
Recently I've noticed that running 'fetchmail' to awake my background
fetchmail daemon is quite slow. It takes around 5 seconds to return,
where previously it was pretty much instantaneous.
I ran fetchmail under callgrind and found that it was spending all of
its time loading my (large) .fetchids file into a linked list. I've
got a POP3 server with all messages kept on it, and my .fetchids file
contains around 50,000 entries (I should probably switch to IMAP ;)
>From what I can see, the issue is that each ID from .fetchids is
appended to a linked list (by initialize_saved_lists() in uid.c), but
the append operation (save_str) has to scan the entire linked list
from head to tail on every append operation. As a result, the process
of reading the file is O(N^2) instead of O(N).
There's a struct member on 'struct query' called 'oldsavedend' that
was unused and seemed like it might have been intended to track the
end of the linked list, so I've modified uid.c to use that
variable--keeping track of the last node in the linked list and
avoiding the full scan. I've attached a patch for that, and
performance is back to instantaneous in my testing.
It's a pretty minor thing, but easy enough to fix so I thought I'd
report it.
Cheers,
Mark
-- System Information:
Debian Release: 8.1
APT prefers stable
APT policy: (500, 'stable')
Architecture: amd64 (x86_64)
Foreign Architectures: i386
Kernel: Linux 3.16.0-4-amd64 (SMP w/8 CPU cores)
Locale: LANG=en_AU.UTF-8, LC_CTYPE=en_AU.UTF-8 (charmap=UTF-8) (ignored: LC_ALL
set to en_AU.UTF-8)
Shell: /bin/sh linked to /bin/dash
Init: systemd (via /run/systemd/system)
Versions of packages fetchmail depends on:
ii adduser 3.113+nmu3
ii debianutils 4.4+b1
ii libc6 2.19-18
ii libcomerr2 1.42.12-1.1
ii libgssapi-krb5-2 1.12.1+dfsg-19
ii libkrb5-3 1.12.1+dfsg-19
ii libssl1.0.0 1.0.1k-3+deb8u1
ii lsb-base 4.1+Debian13+nmu1
Versions of packages fetchmail recommends:
ii ca-certificates 20141019
Versions of packages fetchmail suggests:
pn fetchmailconf <none>
pn resolvconf <none>
ii ssmtp [mail-transport-agent] 2.64-8
-- no debconf information
commit 4efda943a32a17b43b80fbb5e2c27ddf785dd53d
Author: Mark Triggs <m...@dishevelled.net>
Date: Sat Sep 12 20:53:12 2015 +1000
Performance fix for linked list: O(N^2) to (N)
diff --git a/fetchmail.h b/fetchmail.h
index d759d39..083a204 100644
--- a/fetchmail.h
+++ b/fetchmail.h
@@ -390,7 +390,7 @@ struct query
unsigned int uid; /* UID of user to deliver to */
struct idlist *skipped; /* messages skipped on the mail server */
struct idlist *oldsaved, *newsaved;
- struct idlist **oldsavedend;
+ struct idlist *oldsavedend;
char lastdigest[DIGESTLEN]; /* last MD5 hash seen on this connection */
char *folder; /* folder currently being polled */
diff --git a/uid.c b/uid.c
index 8a775b9..504301b 100644
--- a/uid.c
+++ b/uid.c
@@ -119,7 +119,7 @@ void initialize_saved_lists(struct query *hostlist, const char *idfile)
ctl->skipped = (struct idlist *)NULL;
ctl->oldsaved = (struct idlist *)NULL;
ctl->newsaved = (struct idlist *)NULL;
- ctl->oldsavedend = &ctl->oldsaved;
+ ctl->oldsavedend = (struct idlist *)NULL;
}
errno = 0;
@@ -216,7 +216,13 @@ void initialize_saved_lists(struct query *hostlist, const char *idfile)
for (ctl = hostlist; ctl; ctl = ctl->next) {
if (strcasecmp(host, ctl->server.queryname) == 0
&& strcasecmp(user, ctl->remotename) == 0) {
- save_str(&ctl->oldsaved, id, UID_SEEN);
+ save_str(&ctl->oldsavedend, id, UID_SEEN);
+
+ if (ctl->oldsaved == NULL) {
+ /* When we add the first element to the list, set our head to point to it. */
+ ctl->oldsaved = ctl->oldsavedend;
+ }
+
break;
}
}
