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 "gl_hash_map.h"
  48 #include "gl_rbtree_list.h"
  49 #include "gl_xlist.h"
  50 #include "gl_xmap.h"
  51
  52 #include "manconfig.h"
  53
  54 #include "glcontainers.h"
  55 #include "orderfiles.h"
  56
  57 #if defined(HAVE_LINUX_FIEMAP_H)
  58 gl_map_t physical_offsets = NULL;
  59
  60 static int compare_physical_offsets (const void *a, const void *b)
  61 {
  62         const char *left = (const char *) a;
  63         const char *right = (const char *) b;
  64         const uint64_t *left_offset_p = gl_map_get (physical_offsets, left);
  65         const uint64_t *right_offset_p = gl_map_get (physical_offsets, right);
  66         uint64_t left_offset = left_offset_p ? *left_offset_p : UINT64_MAX;
  67         uint64_t right_offset = right_offset_p ? *right_offset_p : UINT64_MAX;
  68
  69         if (left_offset < right_offset)
  70                 return -1;
  71         else if (left_offset > right_offset)
  72                 return 1;
  73         else
  74                 return 0;
  75 }
  76
  77 void order_files (const char *dir, gl_list_t *basenamesp)
  78 {
  79         gl_list_t basenames = *basenamesp, sorted_basenames;
  80         int dir_fd_open_flags;
  81         int dir_fd;
  82         struct statfs fs;
  83         const char *name;
  84
  85         dir_fd_open_flags = O_SEARCH | O_DIRECTORY;
  86 #ifdef O_PATH
  87         dir_fd_open_flags |= O_PATH;
  88 #endif
  89         dir_fd = open (dir, dir_fd_open_flags);
  90         if (dir_fd < 0)
  91                 return;
  92
  93         if (fstatfs (dir_fd, &fs) < 0) {
  94                 close (dir_fd);
  95                 return;
  96         }
  97
  98         /* Sort files by the physical locations of their first blocks, in an
  99          * attempt to minimise disk drive head movements.  This assumes that
 100          * files are small enough that they are likely to be in one block or
 101          * a small number of contiguous blocks, which seems a reasonable
 102          * assumption for manual pages.
 103          */
 104         physical_offsets = gl_map_create_empty (GL_HASH_MAP, string_equals,
 105                                                 string_hash, NULL, plain_free);
 106         sorted_basenames = new_string_list (GL_RBTREE_LIST, false);
 107         GL_LIST_FOREACH_START (basenames, name) {
 108                 struct {
 109                         struct fiemap fiemap;
 110                         struct fiemap_extent extent;
 111                 } fm;
 112                 int fd;
 113
 114                 fd = openat (dir_fd, name, O_RDONLY);
 115                 if (fd < 0)
 116                         continue;
 117
 118                 memset (&fm, 0, sizeof (fm));
 119                 fm.fiemap.fm_start = 0;
 120                 fm.fiemap.fm_length = fs.f_bsize;
 121                 fm.fiemap.fm_flags = 0;
 122                 fm.fiemap.fm_extent_count = 1;
 123
 124                 if (ioctl (fd, FS_IOC_FIEMAP, (unsigned long) &fm) == 0) {
 125                         uint64_t *offset = XMALLOC (uint64_t);
 126                         *offset = fm.extent.fe_physical;
 127                         /* Borrow the key from basenames; since
 128                          * physical_offsets has a shorter lifetime, we don't
 129                          * need to duplicate it.
 130                          */
 131                         gl_map_put (physical_offsets, name, offset);
 132                 }
 133
 134                 close (fd);
 135                 gl_sortedlist_add (sorted_basenames, compare_physical_offsets,
 136                                    xstrdup (name));
 137         } GL_LIST_FOREACH_END (basenames);
 138         gl_map_free (physical_offsets);
 139         physical_offsets = NULL;
 140         close (dir_fd);
 141         gl_list_free (basenames);
 142         *basenamesp = sorted_basenames;
 143 }
 144 #elif defined(HAVE_POSIX_FADVISE)
 145 void order_files (const char *dir, gl_list_t *basenamesp)
 146 {
 147         gl_list_t basenames = *basenamesp;
 148         int dir_fd_open_flags;
 149         int dir_fd;
 150         const char *name;
 151
 152         dir_fd_open_flags = O_SEARCH | O_DIRECTORY;
 153 #ifdef O_PATH
 154         dir_fd_open_flags |= O_PATH;
 155 #endif
 156         dir_fd = open (dir, dir_fd_open_flags);
 157         if (dir_fd < 0)
 158                 return;
 159
 160         /* While we can't actually order the files, we can at least ask the
 161          * kernel to preload them.
 162          */
 163         GL_LIST_FOREACH_START (basenames, name) {
 164                 int fd = openat (dir_fd, name, O_RDONLY | O_NONBLOCK);
 165                 if (fd >= 0) {
 166                         posix_fadvise (fd, 0, 0, POSIX_FADV_WILLNEED);
 167                         close (fd);
 168                 }
 169         } GL_LIST_FOREACH_END (basenames);
 170
 171         close (dir_fd);
 172 }
 173 #else
 174 void order_files (const char *dir _GL_UNUSED, gl_list_t *basenamesp _GL_UNUSED)
 175 {
 176 }
 177 #endif