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