blob: 3634f5576a22f6759aecc7f214431174719b81c1 [file] [log] [blame]
Willy Tarreau214c2032009-02-20 11:02:32 +01001/*
2 * fast fgets() replacement for log parsing
3 *
Willy Tarreaude5dc052012-06-09 09:44:03 +02004 * Copyright 2000-2012 Willy Tarreau <w@1wt.eu>
Willy Tarreau214c2032009-02-20 11:02:32 +01005 *
Willy Tarreaude5dc052012-06-09 09:44:03 +02006 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation, version 2.1
9 * exclusively.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public License
17 * along with this library; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Willy Tarreau214c2032009-02-20 11:02:32 +010019 *
20 * This function manages its own buffer and returns a pointer to that buffer
21 * in order to avoid expensive memory copies. It also checks for line breaks
Willy Tarreaude5dc052012-06-09 09:44:03 +020022 * 32 or 64 bits at a time. It could be improved a lot using mmap() but we
23 * would not be allowed to replace trailing \n with zeroes and we would be
24 * limited to small log files on 32-bit machines.
Willy Tarreau214c2032009-02-20 11:02:32 +010025 *
26 */
27
28#include <stdlib.h>
29#include <string.h>
30#include <stdio.h>
31#include <unistd.h>
32
Willy Tarreaude5dc052012-06-09 09:44:03 +020033#ifndef FGETS2_BUFSIZE
34#define FGETS2_BUFSIZE (256*1024)
35#endif
36
Willy Tarreauc4710e12021-04-02 14:57:42 +020037/* memchr() is faster in glibc with SSE since commit 093ecf92998de2 */
38#if defined(__x86_64__) && (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 15))
39#define USE_MEMCHR
40#endif
41
Willy Tarreaude5dc052012-06-09 09:44:03 +020042/* return non-zero if the integer contains at least one zero byte */
Willy Tarreauf531dff2020-12-21 08:35:24 +010043static inline __attribute__((unused)) unsigned int has_zero32(unsigned int x)
Willy Tarreau214c2032009-02-20 11:02:32 +010044{
Willy Tarreau1769a182010-05-04 10:47:57 +020045 unsigned int y;
46
47 /* Principle: we want to perform 4 tests on one 32-bit int at once. For
48 * this, we have to simulate an SIMD instruction which we don't have by
49 * default. The principle is that a zero byte is the only one which
50 * will cause a 1 to appear on the upper bit of a byte/word/etc... when
51 * we subtract 1. So we can detect a zero byte if a one appears at any
52 * of the bits 7, 15, 23 or 31 where it was not. It takes only one
53 * instruction to test for the presence of any of these bits, but it is
54 * still complex to check for their initial absence. Thus, we'll
55 * proceed differently : we first save and clear only those bits, then
56 * we check in the final result if one of them is present and was not.
Willy Tarreaude5dc052012-06-09 09:44:03 +020057 * The order of operations below is important to save registers and
58 * tests. The result is used as a boolean, so the last test must apply
59 * on the constant so that it can efficiently be inlined.
Willy Tarreau1769a182010-05-04 10:47:57 +020060 */
Willy Tarreaude5dc052012-06-09 09:44:03 +020061#if defined(__i386__)
62 /* gcc on x86 loves copying registers over and over even on code that
63 * simple, so let's do it by hand to prevent it from doing so :-(
64 */
65 asm("lea -0x01010101(%0),%1\n"
66 "not %0\n"
67 "and %1,%0\n"
68 : "=a" (x), "=r"(y)
69 : "0" (x)
70 );
71 return x & 0x80808080;
72#else
73 y = x - 0x01010101; /* generate a carry */
74 x = ~x & y; /* clear the bits that were already set */
75 return x & 0x80808080;
76#endif
Willy Tarreau214c2032009-02-20 11:02:32 +010077}
78
Willy Tarreaude5dc052012-06-09 09:44:03 +020079/* return non-zero if the argument contains at least one zero byte. See principle above. */
Willy Tarreauf531dff2020-12-21 08:35:24 +010080static inline __attribute__((unused)) unsigned long long has_zero64(unsigned long long x)
Willy Tarreaude5dc052012-06-09 09:44:03 +020081{
82 unsigned long long y;
Willy Tarreau214c2032009-02-20 11:02:32 +010083
Willy Tarreaude5dc052012-06-09 09:44:03 +020084 y = x - 0x0101010101010101ULL; /* generate a carry */
85 y &= ~x; /* clear the bits that were already set */
86 return y & 0x8080808080808080ULL;
87}
88
Willy Tarreauf531dff2020-12-21 08:35:24 +010089static inline __attribute__((unused)) unsigned long has_zero(unsigned long x)
Willy Tarreaude5dc052012-06-09 09:44:03 +020090{
91 return (sizeof(x) == 8) ? has_zero64(x) : has_zero32(x);
92}
93
Willy Tarreau419a5982012-06-12 08:52:22 +020094/* find a '\n' between <next> and <end>. Warning: may read slightly past <end>.
95 * If no '\n' is found, <end> is returned.
96 */
97static char *find_lf(char *next, char *end)
Willy Tarreau214c2032009-02-20 11:02:32 +010098{
Willy Tarreau419a5982012-06-12 08:52:22 +020099#if defined USE_MEMCHR
100 /* some recent libc use platform-specific optimizations to provide more
101 * efficient byte search than below (eg: glibc 2.11 on x86_64).
102 */
103 next = memchr(next, '\n', end - next);
104 if (!next)
105 next = end;
106#else
107 if (sizeof(long) == 4) { /* 32-bit system */
108 /* this is a speed-up, we read 32 bits at once and check for an
109 * LF character there. We stop if found then continue one at a
110 * time.
111 */
112 while (next < end && (((unsigned long)next) & 3) && *next != '\n')
113 next++;
Willy Tarreau214c2032009-02-20 11:02:32 +0100114
Willy Tarreau419a5982012-06-12 08:52:22 +0200115 /* Now next is multiple of 4 or equal to end. We know we can safely
116 * read up to 32 bytes past end if needed because they're allocated.
117 */
118 while (next < end) {
119 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
120 break;
121 next += 4;
122 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
123 break;
124 next += 4;
125 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
126 break;
127 next += 4;
128 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
129 break;
130 next += 4;
131 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
132 break;
133 next += 4;
134 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
135 break;
136 next += 4;
137 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
138 break;
139 next += 4;
140 if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A))
141 break;
142 next += 4;
143 }
144 }
145 else { /* 64-bit system */
146 /* this is a speed-up, we read 64 bits at once and check for an
147 * LF character there. We stop if found then continue one at a
148 * time.
149 */
150 if (next <= end) {
151 /* max 3 bytes tested here */
152 while ((((unsigned long)next) & 3) && *next != '\n')
Willy Tarreaude5dc052012-06-09 09:44:03 +0200153 next++;
154
Willy Tarreau419a5982012-06-12 08:52:22 +0200155 /* maybe we have can skip 4 more bytes */
156 if ((((unsigned long)next) & 4) && !has_zero32(*(unsigned int *)next ^ 0x0A0A0A0AU))
Willy Tarreaude5dc052012-06-09 09:44:03 +0200157 next += 4;
Willy Tarreaude5dc052012-06-09 09:44:03 +0200158 }
Willy Tarreaude5dc052012-06-09 09:44:03 +0200159
Willy Tarreau419a5982012-06-12 08:52:22 +0200160 /* now next is multiple of 8 or equal to end */
161 while (next <= (end-68)) {
162 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
163 break;
164 next += 8;
165 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
166 break;
167 next += 8;
168 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
169 break;
170 next += 8;
171 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
172 break;
173 next += 8;
174 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
175 break;
176 next += 8;
177 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
178 break;
179 next += 8;
180 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
181 break;
182 next += 8;
183 if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL))
184 break;
185 next += 8;
186 }
Willy Tarreaude5dc052012-06-09 09:44:03 +0200187
Willy Tarreau419a5982012-06-12 08:52:22 +0200188 /* maybe we can skip 4 more bytes */
189 if (!has_zero32(*(unsigned int *)next ^ 0x0A0A0A0AU))
190 next += 4;
191 }
Willy Tarreau214c2032009-02-20 11:02:32 +0100192
Willy Tarreau419a5982012-06-12 08:52:22 +0200193 /* We finish if needed : if <next> is below <end>, it means we
194 * found an LF in one of the 4 following bytes.
195 */
196 while (next < end) {
197 if (*next == '\n')
198 break;
199 next++;
200 }
201#endif
202 return next;
203}
Willy Tarreau214c2032009-02-20 11:02:32 +0100204
Willy Tarreau419a5982012-06-12 08:52:22 +0200205const char *fgets2(FILE *stream)
206{
207 static char buffer[FGETS2_BUFSIZE + 68]; /* Note: +32 is enough on 32-bit systems */
208 static char *end = buffer;
209 static char *line = buffer;
210 char *next;
211 int ret;
Willy Tarreau214c2032009-02-20 11:02:32 +0100212
Willy Tarreau419a5982012-06-12 08:52:22 +0200213 next = line;
214
215 while (1) {
216 next = find_lf(next, end);
217 if (next < end) {
218 const char *start = line;
219 *next = '\0';
220 line = next + 1;
221 return start;
Willy Tarreau214c2032009-02-20 11:02:32 +0100222 }
223
224 /* we found an incomplete line. First, let's move the
225 * remaining part of the buffer to the beginning, then
Willy Tarreau31a02e92011-09-10 10:25:05 +0200226 * try to complete the buffer with a new read. We can't
227 * rely on <next> anymore because it went past <end>.
Willy Tarreau214c2032009-02-20 11:02:32 +0100228 */
229 if (line > buffer) {
230 if (end != line)
231 memmove(buffer, line, end - line);
232 end = buffer + (end - line);
233 next = end;
234 line = buffer;
235 } else {
236 if (end == buffer + FGETS2_BUFSIZE)
237 return NULL;
238 }
239
240 ret = read(fileno(stream), end, buffer + FGETS2_BUFSIZE - end);
241
242 if (ret <= 0) {
243 if (end == line)
244 return NULL;
245
246 *end = '\0';
Willy Tarreau812e7a72011-07-09 14:28:01 +0200247 end = line; /* ensure we stop next time */
Willy Tarreau214c2032009-02-20 11:02:32 +0100248 return line;
249 }
250
251 end += ret;
Willy Tarreau31a02e92011-09-10 10:25:05 +0200252 *end = '\n'; /* make parser stop ASAP */
Willy Tarreau214c2032009-02-20 11:02:32 +0100253 /* search for '\n' again */
254 }
255}
256
257#ifdef BENCHMARK
258int main() {
259 const char *p;
260 unsigned int lines = 0;
261
262 while ((p=fgets2(stdin)))
263 lines++;
264 printf("lines=%d\n", lines);
265 return 0;
266}
267#endif