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