lib/orderfiles.c

   1 /*
   2  * orderfiles.c: order file accesses to optimise disk load
   3  *
   4  * Copyright (C) 2014 Colin Watson.
   5  *
   6  * Inspired by and loosely based on dpkg/src/filesdb.c, which is:
   7  *   Copyright (C) 1995 Ian Jackson <ian@chiark.greenend.org.uk>
   8  *   Copyright (C) 2000,2001 Wichert Akkerman <wakkerma@debian.org>
   9  *   Copyright (C) 2008-2014 Guillem Jover <guillem@debian.org>
  10  *
  11  * This file is part of man-db.
  12  *
  13  * man-db is free software; you can redistribute it and/or modify it
  14  * under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version 2 of the License, or
  16  * (at your option) any later version.
  17  *
  18  * man-db is distributed in the hope that it will be useful, but
  19  * WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with man-db; if not, write to the Free Software Foundation,
  25  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #  include "config.h"
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #ifdef HAVE_LINUX_FIEMAP_H
  33 #  include <linux/fiemap.h>
  34 #  include <linux/fs.h>
  35 #  include <sys/ioctl.h>
  36 #  include <sys/vfs.h>
  37 #endif /* HAVE_LINUX_FIEMAP_H */
  38
  39 #include <sys/types.h>
  40 #include <sys/stat.h>
  41 #include <fcntl.h>
  42 #include <stdint.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include <unistd.h>
  46
  47 #include "manconfig.h"
  48
  49 #include "hashtable.h"
  50
  51 struct hashtable *physical_offsets = NULL;
  52
  53 #if defined(HAVE_LINUX_FIEMAP_H)
  54 int compare_physical_offsets (const void *a, const void *b)
  55 {
  56         const char *left = *(const char **) a;
  57         const char *right = *(const char **) b;
  58         uint64_t *left_offset_p = hashtable_lookup (physical_offsets,
  59                                                     left, strlen (left));
  60         uint64_t *right_offset_p = hashtable_lookup (physical_offsets,
  61                                                      right, strlen (right));
  62         uint64_t left_offset = left_offset_p ? *left_offset_p : UINT64_MAX;
  63         uint64_t right_offset = right_offset_p ? *right_offset_p : UINT64_MAX;
  64
  65         if (left_offset < right_offset)
  66                 return -1;
  67         else if (left_offset > right_offset)
  68                 return 1;
  69         else
  70                 return 0;
  71 }
  72
  73 void order_files (const char *dir, char **basenames, size_t n_basenames)
  74 {
  75         int dir_fd_open_flags;
  76         int dir_fd;
  77         struct statfs fs;
  78         size_t i;
  79
  80         dir_fd_open_flags = O_SEARCH | O_DIRECTORY;
  81 #ifdef O_PATH
  82         dir_fd_open_flags |= O_PATH;
  83 #endif
  84         dir_fd = open (dir, dir_fd_open_flags);
  85         if (dir_fd < 0)
  86                 return;
  87
  88         if (fstatfs (dir_fd, &fs) < 0) {
  89                 close (dir_fd);
  90                 return;
  91         }
  92
  93         /* Sort files by the physical locations of their first blocks, in an
  94          * attempt to minimise disk drive head movements.  This assumes that
  95          * files are small enough that they are likely to be in one block or
  96          * a small number of contiguous blocks, which seems a reasonable
  97          * assumption for manual pages.
  98          */
  99         physical_offsets = hashtable_create (&free);
 100         for (i = 0; i < n_basenames; ++i) {
 101                 struct {
 102                         struct fiemap fiemap;
 103                         struct fiemap_extent extent;
 104                 } fm;
 105                 int fd;
 106
 107                 fd = openat (dir_fd, basenames[i], O_RDONLY);
 108                 if (fd < 0)
 109                         continue;
 110
 111                 memset (&fm, 0, sizeof (fm));
 112                 fm.fiemap.fm_start = 0;
 113                 fm.fiemap.fm_length = fs.f_bsize;
 114                 fm.fiemap.fm_flags = 0;
 115                 fm.fiemap.fm_extent_count = 1;
 116
 117                 if (ioctl (fd, FS_IOC_FIEMAP, (unsigned long) &fm) == 0) {
 118                         uint64_t *offset = XMALLOC (uint64_t);
 119                         *offset = fm.fiemap.fm_extents[0].fe_physical;
 120                         hashtable_install (physical_offsets, basenames[i],
 121                                            strlen (basenames[i]), offset);
 122                 }
 123
 124                 close (fd);
 125         }
 126         qsort (basenames, n_basenames, sizeof *basenames,
 127                compare_physical_offsets);
 128         hashtable_free (physical_offsets);
 129         physical_offsets = NULL;
 130         close (dir_fd);
 131 }
 132 #elif defined(HAVE_POSIX_FADVISE)
 133 void order_files (const char *dir, char **basenames, size_t n_basenames)
 134 {
 135         int dir_fd_open_flags;
 136         int dir_fd;
 137         size_t i;
 138
 139         dir_fd_open_flags = O_SEARCH | O_DIRECTORY;
 140 #ifdef O_PATH
 141         dir_fd_open_flags |= O_PATH;
 142 #endif
 143         dir_fd = open (dir, dir_fd_open_flags);
 144         if (dir_fd < 0)
 145                 return;
 146
 147         /* While we can't actually order the files, we can at least ask the
 148          * kernel to preload them.
 149          */
 150         for (i = 0; i < n_basenames; ++i) {
 151                 int fd = openat (dir_fd, basenames[i], O_RDONLY | O_NONBLOCK);
 152                 if (fd >= 0) {
 153                         posix_fadvise (fd, 0, 0, POSIX_FADV_WILLNEED);
 154                         close (fd);
 155                 }
 156         }
 157
 158         close (dir_fd);
 159 }
 160 #else
 161 void order_files (const char *dir, char **basenames, size_t n_basenames)
 162 {
 163 }
 164 #endif