1 /*
2 * $OpenBSD: locate.c,v 1.34 2021/06/22 20:16:36 jmc Exp $
3 *
4 * Copyright (c) 1995 Wolfram Schneider <wosch@FreeBSD.org>. Berlin.
5 * Copyright (c) 1989, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * James A. Woods.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 /*
37 * Ref: Usenix ;login:, Vol 8, No 1, February/March, 1983, p. 8.
38 *
39 * Locate scans a file list for the full pathname of a file given only part
40 * of the name. The list has been processed with "front-compression"
41 * and bigram coding. Front compression reduces space by a factor of 4-5,
42 * bigram coding by a further 20-25%.
43 *
44 * The codes are:
45 *
46 * 0-28 likeliest differential counts + offset to make nonnegative
47 * 30 switch code for out-of-range count to follow in next word
48 * 31 an 8 bit char followed
49 * 128-255 bigram codes (128 most common, as determined by 'updatedb')
50 * 32-127 single character (printable) ascii residue (ie, literal)
51 *
52 * A novel two-tiered string search technique is employed:
53 *
54 * First, a metacharacter-free subpattern and partial pathname is matched
55 * BACKWARDS to avoid full expansion of the pathname list. The time savings
56 * is 40-50% over forward matching, which cannot efficiently handle
57 * overlapped search patterns and compressed path residue.
58 *
59 * Then, the actual shell glob-style regular expression (if in this form) is
60 * matched against the candidate pathnames using the slower routines provided
61 * in the standard 'find'.
62 */
63
64 #include <sys/mman.h>
65 #include <sys/stat.h>
66 #include <sys/types.h>
67
68 #include <ctype.h>
69 #include <err.h>
70 #include <fcntl.h>
71 #include <fnmatch.h>
72 #include <libgen.h>
73 #include <limits.h>
74 #include <stdio.h>
75 #include <stdlib.h>
76 #include <string.h>
77 #include <unistd.h>
78
79 #include "locate.h"
80 #include "pathnames.h"
81
82 #ifdef DEBUG
83 # include <sys/time.h>
84 # include <sys/types.h>
85 # include <sys/resource.h>
86 #endif
87
88 char *path_fcodes; /* locate database */
89 int f_mmap; /* use mmap */
90 int f_icase; /* ignore case */
91 int f_statistic; /* print statistic */
92 int f_silent; /* suppress output, show only count of matches */
93 int f_limit; /* limit number of output lines, 0 == infinite */
94 int f_basename; /* match only on the basename */
95 u_int counter; /* counter for matches [-c] */
96
97
98 void usage(void);
99 void statistic(FILE *, char *);
100 void fastfind(FILE *, char *, char *);
101 void fastfind_icase(FILE *, char *, char *);
102 void fastfind_mmap(char *, caddr_t, int, char *);
103 void fastfind_mmap_icase(char *, caddr_t, int, char *);
104 void search_mmap(char *, char **);
105 void search_statistic(char *, char **);
106 unsigned long cputime(void);
107
108 extern char **colon(char **, char*, char*);
109 extern int getwm(caddr_t);
110 extern int getwf(FILE *);
111 extern int check_bigram_char(int);
112 extern char *patprep(char *);
113
114
115 int
main(int argc,char * argv[])116 main(int argc, char *argv[])
117 {
118 int ch;
119 char **dbv = NULL;
120
121 if (pledge("stdio rpath", NULL) == -1)
122 err(1, "pledge");
123
124 while ((ch = getopt(argc, argv, "bScd:il:")) != -1)
125 switch (ch) {
126 case 'b':
127 f_basename = 1;
128 break;
129 case 'S': /* statistic lines */
130 f_statistic = 1;
131 break;
132 case 'l': /* limit number of output lines, 0 == infinite */
133 f_limit = atoi(optarg);
134 break;
135 case 'd': /* database */
136 dbv = colon(dbv, optarg, _PATH_FCODES);
137 break;
138 case 'i': /* ignore case */
139 f_icase = 1;
140 break;
141 case 'c': /* suppress output, show only count of matches */
142 f_silent = 1;
143 break;
144 default:
145 usage();
146 }
147 argv += optind;
148 argc -= optind;
149
150 /* to few arguments */
151 if (argc < 1 && !(f_statistic))
152 usage();
153
154 /* no (valid) database as argument */
155 if (dbv == NULL || *dbv == NULL) {
156 /* try to read database from environment */
157 if ((path_fcodes = getenv("LOCATE_PATH")) == NULL ||
158 *path_fcodes == '\0')
159 /* use default database */
160 dbv = colon(dbv, _PATH_FCODES, _PATH_FCODES);
161 else /* $LOCATE_PATH */
162 dbv = colon(dbv, path_fcodes, _PATH_FCODES);
163 }
164
165 /* foreach database ... */
166 while ((path_fcodes = *dbv) != NULL) {
167 dbv++;
168
169 if (f_statistic)
170 search_statistic(path_fcodes, argv);
171 else
172 search_mmap(path_fcodes, argv);
173 }
174
175 if (f_silent)
176 printf("%u\n", counter);
177 exit(0);
178 }
179
180
181 void
search_statistic(char * db,char ** s)182 search_statistic(char *db, char **s)
183 {
184 FILE *fp;
185 #ifdef DEBUG
186 long t0;
187 #endif
188
189 if ((fp = fopen(path_fcodes, "r")) == NULL)
190 err(1, "`%s'", path_fcodes);
191
192 /* count only chars or lines */
193 statistic(fp, path_fcodes);
194 (void)fclose(fp);
195 }
196
197 void
search_mmap(char * db,char ** s)198 search_mmap(char *db, char **s)
199 {
200 struct stat sb;
201 int fd;
202 caddr_t p;
203 off_t len;
204 #ifdef DEBUG
205 long t0;
206 #endif
207 if ((fd = open(path_fcodes, O_RDONLY)) == -1 ||
208 fstat(fd, &sb) == -1)
209 err(1, "`%s'", path_fcodes);
210 len = sb.st_size;
211 if (len < (2*NBG))
212 errx(1, "database too small: %s", db);
213
214 if ((p = mmap((caddr_t)0, (size_t)len, PROT_READ, MAP_SHARED,
215 fd, (off_t)0)) == MAP_FAILED)
216 err(1, "mmap ``%s''", path_fcodes);
217
218 /* foreach search string ... */
219 while (*s != NULL) {
220 #ifdef DEBUG
221 t0 = cputime();
222 #endif
223 if (f_icase)
224 fastfind_mmap_icase(*s, p, (int)len, path_fcodes);
225 else
226 fastfind_mmap(*s, p, (int)len, path_fcodes);
227 #ifdef DEBUG
228 (void)fprintf(stderr, "fastfind %ld ms\n", cputime () - t0);
229 #endif
230 s++;
231 }
232
233 if (munmap(p, (size_t)len) == -1)
234 warn("munmap %s", path_fcodes);
235
236 (void)close(fd);
237 }
238
239 #ifdef DEBUG
240 unsigned long
cputime(void)241 cputime(void)
242 {
243 struct rusage rus;
244
245 getrusage(RUSAGE_SELF, &rus);
246 return(rus.ru_utime.tv_sec * 1000 + rus.ru_utime.tv_usec / 1000);
247 }
248 #endif /* DEBUG */
249
250 void
usage(void)251 usage(void)
252 {
253 (void)fprintf(stderr, "usage: locate [-bciS] [-d database] ");
254 (void)fprintf(stderr, "[-l limit] pattern ...\n");
255
256 exit(1);
257 }
258
259 void
sane_count(int count)260 sane_count(int count)
261 {
262 if (count < 0 || count >= PATH_MAX) {
263 fprintf(stderr, "locate: corrupted database\n");
264 exit(1);
265 }
266 }
267
268 /* load fastfind functions */
269
270 #undef FF_ICASE
271 #include "fastfind.c"
272 #define FF_ICASE
273 #include "fastfind.c"
274