[PATCH] Use FIBMAP to sort .list files before scanning
When running dpkg from a cold cache on a system where /var/lib/dpkg/info/ lies
on a harddisk, a lot of time is spent waiting for seeks between (typically)
thousands of files. This patch ensures that the package iterator used by
ensure_allinstfiles_available returns the packages sorted by their .list file's
physical location on the harddisk, greatly reducing drive head movements.
The performance improvement is around 330% on my system: reinstalling a simple
package takes 8 seconds instead of 27 seconds. I dropped the caches before
each run, and did 10 runs with consistent results.
---
configure.ac | 2 +-
dselect/pkglist.cc | 2 +-
lib/dpkg/database.c | 87 +++++++++++++++++++++++++++++++++++++++++++++-----
lib/dpkg/dpkg-db.h | 8 ++++-
lib/dpkg/dump.c | 2 +-
src/depcon.c | 2 +-
src/enquiry.c | 10 +++---
src/filesdb.c | 2 +-
src/help.c | 2 +-
src/packages.c | 2 +-
src/pkg-array.c | 2 +-
src/processarc.c | 2 +-
src/select.c | 2 +-
src/trigproc.c | 4 +-
14 files changed, 102 insertions(+), 27 deletions(-)
diff --git a/configure.ac b/configure.ac
index bb5456c..eadf9a9 100644
--- a/configure.ac
+++ b/configure.ac
@@ -73,7 +73,7 @@ fi
# Checks for header files.
AC_HEADER_STDC
AC_CHECK_HEADERS([stddef.h error.h locale.h libintl.h kvm.h \
- sys/cdefs.h sys/syscall.h])
+ sys/cdefs.h sys/syscall.h linux/fs.h])
DPKG_CHECK_DEFINE(TIOCNOTTY, [sys/ioctl.h])
# Checks for typedefs, structures, and compiler characteristics.
diff --git a/dselect/pkglist.cc b/dselect/pkglist.cc
index 53535d0..a05e5ad 100644
--- a/dselect/pkglist.cc
+++ b/dselect/pkglist.cc
@@ -385,7 +385,7 @@ packagelist::packagelist(keybindings *kb) : baselist(kb) {
struct pkgiterator *iter;
struct pkginfo *pkg;
- for (iter=iterpkgstart(), nitems=0;
+ for (iter=iterpkgstart(iter_any), nitems=0;
(pkg=iterpkgnext(iter));
) {
struct perpackagestate *state= &datatable[nitems];
diff --git a/lib/dpkg/database.c b/lib/dpkg/database.c
index cc9dd85..322b549 100644
--- a/lib/dpkg/database.c
+++ b/lib/dpkg/database.c
@@ -20,6 +20,12 @@
*/
#include <config.h>
#include <compat.h>
+#if HAVE_LINUX_FS_H
+# include <unistd.h>
+# include <fcntl.h>
+# include <sys/ioctl.h>
+# include <linux/fs.h>
+#endif
#include <dpkg/i18n.h>
@@ -40,6 +46,10 @@
static struct pkginfo *bins[BINS];
static int npackages;
+static struct pkginfo *first_package;
+static struct pkginfo *last_package;
+static int sort_order = -1;
+
#define FNV_offset_basis 2166136261ul
#define FNV_mixing_prime 16777619ul
@@ -81,6 +91,8 @@ void blankpackage(struct pkginfo *pigp) {
pigp->trigpend_head = NULL;
blankpackageperfile(&pigp->installed);
blankpackageperfile(&pigp->available);
+ pigp->iter_next= NULL;
+ pigp->phys_offset= 0;
}
void blankpackageperfile(struct pkginfoperfile *pifp) {
@@ -141,6 +153,13 @@ struct pkginfo *findpackage(const char *inname) {
newpkg->next= NULL;
*pointerp= newpkg;
npackages++;
+ if(!first_package) {
+ first_package= newpkg;
+ last_package= newpkg;
+ } else {
+ last_package->iter_next= newpkg;
+ last_package= newpkg;
+ }
free(name);
return newpkg;
@@ -152,24 +171,74 @@ int countpackages(void) {
struct pkgiterator {
struct pkginfo *pigp;
- int nbinn;
};
-struct pkgiterator *iterpkgstart(void) {
+#if HAVE_LINUX_FS_H
+static int qsort_compare_phys_offset(const void* vlhs, const void* vrhs) {
+ struct pkginfo *const *lhs = vlhs;
+ struct pkginfo *const *rhs = vrhs;
+ return (*lhs)->phys_offset - (*rhs)->phys_offset;
+}
+
+static void pkgsort(int type) {
+ struct pkginfo **pigps;
+ struct pkginfo *pigp;
+ int i;
+ if(type != iter_list)
+ return;
+ pigps= malloc(sizeof(*pigps) * npackages);
+ pigp= first_package;
+ for (i=0; i<npackages; i++) {
+ static int have_fibmap = 1;
+ if(type == iter_list && have_fibmap
+ && pigp->status != stat_notinstalled) {
+ const char *listfile;
+ int fd, lba = 0;
+
+ listfile= pkgadminfile(pigp, LISTFILE);
+ if(-1 != (fd= open(listfile, O_RDONLY))) {
+ if(-1 != ioctl(fd, FIBMAP, &lba)) {
+ pigp->phys_offset= lba;
+ }
+ else
+ have_fibmap= 0;
+ close(fd);
+ }
+ }
+ pigps[i]= pigp;
+ pigp= pigp->iter_next;
+ }
+ qsort(pigps, npackages, sizeof(*pigps), qsort_compare_phys_offset);
+ first_package= pigp= pigps[0];
+ for (i=1; i<npackages; i++) {
+ pigp->iter_next= pigps[i];
+ pigp= pigp->iter_next;
+ }
+ last_package= pigp;
+ pigp->iter_next= 0;
+ sort_order= type;
+ free(pigps);
+}
+#endif
+
+struct pkgiterator *iterpkgstart(int type) {
struct pkgiterator *i;
+#if HAVE_LINUX_FS_H
+ if(type != iter_any && type != sort_order)
+ pkgsort(type);
+#endif
i= m_malloc(sizeof(struct pkgiterator));
- i->pigp= NULL;
- i->nbinn= 0;
+ i->pigp= first_package;
return i;
}
struct pkginfo *iterpkgnext(struct pkgiterator *i) {
struct pkginfo *r;
- while (!i->pigp) {
- if (i->nbinn >= BINS) return NULL;
- i->pigp= bins[i->nbinn++];
- }
- r= i->pigp; i->pigp= r->next; return r;
+ if(!i->pigp)
+ return NULL;
+ r= i->pigp;
+ i->pigp= i->pigp->iter_next;
+ return r;
}
void iterpkgend(struct pkgiterator *i) {
diff --git a/lib/dpkg/dpkg-db.h b/lib/dpkg/dpkg-db.h
index a9debc7..e761d3e 100644
--- a/lib/dpkg/dpkg-db.h
+++ b/lib/dpkg/dpkg-db.h
@@ -185,6 +185,8 @@ struct pkginfo { /* pig */
/* ->pend == this, non-NULL for us when Triggers-Pending. */
struct trigaw *othertrigaw_head;
struct trigpend *trigpend_head;
+ struct pkginfo *iter_next;
+ int phys_offset;
};
/*** from lock.c ***/
@@ -327,7 +329,11 @@ int informative(struct pkginfo *pkg, struct pkginfoperfile *info);
int countpackages(void);
void resetpackages(void);
-struct pkgiterator *iterpkgstart(void);
+enum itertype {
+ iter_any = 1,
+ iter_list = 2
+};
+struct pkgiterator *iterpkgstart(int type);
struct pkginfo *iterpkgnext(struct pkgiterator*);
void iterpkgend(struct pkgiterator*);
diff --git a/lib/dpkg/dump.c b/lib/dpkg/dump.c
index 33d0b1c..7c3388a 100644
--- a/lib/dpkg/dump.c
+++ b/lib/dpkg/dump.c
@@ -378,7 +378,7 @@ void writedb(const char *filename, int available, int mustsync) {
if (setvbuf(file,writebuf,_IOFBF,sizeof(writebuf)))
ohshite(_("unable to set buffering on status file"));
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pigp= iterpkgnext(it)) != NULL) {
pifp= available ? &pigp->available : &pigp->installed;
/* Don't dump records which have no useful content. */
diff --git a/src/depcon.c b/src/depcon.c
index f109384..6981803 100644
--- a/src/depcon.c
+++ b/src/depcon.c
@@ -150,7 +150,7 @@ int findbreakcycle(struct pkginfo *pkg) {
struct pkginfo *tpkg;
/* Clear the visited flag of all packages before we traverse them. */
- for (iter = iterpkgstart(); (tpkg=iterpkgnext(iter)); ) {
+ for (iter = iterpkgstart(iter_any); (tpkg=iterpkgnext(iter)); ) {
tpkg->color = white;
}
iterpkgend(iter);
diff --git a/src/enquiry.c b/src/enquiry.c
index 5f773f8..b59de2e 100644
--- a/src/enquiry.c
+++ b/src/enquiry.c
@@ -120,7 +120,7 @@ void audit(const char *const *argv) {
for (bsi= badstatinfos; bsi->yesno; bsi++) {
head= 0;
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pkg= iterpkgnext(it))) {
if (!bsi->yesno(pkg,bsi)) continue;
if (!head) {
@@ -176,7 +176,7 @@ void unpackchk(const char *const *argv) {
totalcount= 0;
sectionentries = NULL;
sects= 0;
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pkg= iterpkgnext(it))) {
if (!yettobeunpacked(pkg, &thissect)) continue;
for (se= sectionentries; se && strcasecmp(thissect,se->name); se= se->next);
@@ -198,7 +198,7 @@ void unpackchk(const char *const *argv) {
if (totalcount == 0) exit(0);
if (totalcount <= 12) {
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pkg= iterpkgnext(it))) {
if (!yettobeunpacked(pkg, NULL))
continue;
@@ -211,7 +211,7 @@ void unpackchk(const char *const *argv) {
printf(_(" %d in %s: "),se->count,se->name);
width= 70-strlen(se->name)-strlen(buf);
while (width > 59) { putchar(' '); width--; }
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pkg= iterpkgnext(it))) {
if (!yettobeunpacked(pkg,&thissect)) continue;
if (strcasecmp(thissect,se->name)) continue;
@@ -313,7 +313,7 @@ void predeppackage(const char *const *argv) {
modstatdb_init(admindir,msdbrw_readonly);
clear_istobes(); /* We use clientdata->istobe to detect loops */
- for (it = iterpkgstart(), dep = NULL;
+ for (it = iterpkgstart(iter_any), dep = NULL;
!dep && (pkg=iterpkgnext(it));
) {
if (pkg->want != want_install) continue; /* Ignore packages user doesn't want */
diff --git a/src/filesdb.c b/src/filesdb.c
index da8cde2..fd1a27b 100644
--- a/src/filesdb.c
+++ b/src/filesdb.c
@@ -222,7 +222,7 @@ void ensure_allinstfiles_available(void) {
progress_init(&progress, _("(Reading database ... "), max);
}
- it= iterpkgstart();
+ it= iterpkgstart(iter_list);
while ((pkg = iterpkgnext(it)) != NULL) {
ensure_packagefiles_available(pkg);
diff --git a/src/help.c b/src/help.c
index 3184b40..a563d0b 100644
--- a/src/help.c
+++ b/src/help.c
@@ -430,7 +430,7 @@ void clear_istobes(void) {
struct pkgiterator *it;
struct pkginfo *pkg;
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pkg = iterpkgnext(it)) != NULL) {
ensure_package_clientdata(pkg);
pkg->clientdata->istobe= itb_normal;
diff --git a/src/packages.c b/src/packages.c
index b176581..de872b4 100644
--- a/src/packages.c
+++ b/src/packages.c
@@ -107,7 +107,7 @@ void packages(const char *const *argv) {
if (*argv)
badusage(_("--%s --pending does not take any non-option arguments"),cipaction->olong);
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((pkg = iterpkgnext(it)) != NULL) {
switch (cipaction->arg) {
case act_configure:
diff --git a/src/pkg-array.c b/src/pkg-array.c
index faa4f0b..641d4c4 100644
--- a/src/pkg-array.c
+++ b/src/pkg-array.c
@@ -51,7 +51,7 @@ pkg_array_init_from_db(struct pkg_array *a)
a->n_pkgs = countpackages();
a->pkgs = m_malloc(sizeof(a->pkgs[0]) * a->n_pkgs);
- it = iterpkgstart();
+ it = iterpkgstart(iter_any);
for (i = 0; (pkg = iterpkgnext(it)); i++)
a->pkgs[i] = pkg;
iterpkgend(it);
diff --git a/src/processarc.c b/src/processarc.c
index 9024681..99b97e3 100644
--- a/src/processarc.c
+++ b/src/processarc.c
@@ -961,7 +961,7 @@ void process_archive(const char *filename) {
* Conffiles are ignored (the new package had better do something
* with them !).
*/
- it= iterpkgstart();
+ it= iterpkgstart(iter_any);
while ((otherpkg = iterpkgnext(it)) != NULL) {
ensure_package_clientdata(otherpkg);
if (otherpkg == pkg ||
diff --git a/src/select.c b/src/select.c
index 8d8a963..29019a6 100644
--- a/src/select.c
+++ b/src/select.c
@@ -152,7 +152,7 @@ void clearselections(const char *const *argv)
modstatdb_init(admindir, msdbrw_write);
- it = iterpkgstart();
+ it = iterpkgstart(iter_any);
while ((pkg = iterpkgnext(it))) {
if (!pkg->installed.essential)
pkg->want = want_deinstall;
diff --git a/src/trigproc.c b/src/trigproc.c
index 96b12c0..1b95965 100644
--- a/src/trigproc.c
+++ b/src/trigproc.c
@@ -167,7 +167,7 @@ check_trigger_cycle(struct pkginfo *processing_now)
tcn->pkgs = NULL;
tcn->then_processed = processing_now;
- it = iterpkgstart();
+ it = iterpkgstart(iter_any);
while ((pkg = iterpkgnext(it))) {
if (!pkg->trigpend_head)
continue;
@@ -357,7 +357,7 @@ trig_transitional_activate(enum modstatdb_rw cstatus)
struct pkgiterator *it;
struct pkginfo *pkg;
- it = iterpkgstart();
+ it = iterpkgstart(iter_any);
while ((pkg = iterpkgnext(it))) {
if (pkg->status <= stat_halfinstalled)
--
1.6.1.424.g2ea3.dirty
Reply to: