Gitiles

commit | de5dc0509c345bccef3bcd90cda7a6945847a08b | [log] [tgz] |
---|---|---|

author | Willy Tarreau <w@1wt.eu> | Sat Jun 09 09:44:03 2012 +0200 |

committer | Willy Tarreau <w@1wt.eu> | Sat Jun 09 11:22:27 2012 +0200 |

tree | e5b7ff6fb88852d8cfd1921a6ec0a3e71d8a2e3f | |

parent | 96596aeeadcb94c87ffe7ee2ecdfef5da122fe9e [diff] |

MINOR: halog: use the more recent dual-mode fgets2 implementation This version implements both 32 and 64 bit versions at once, it avoids the need to have two separate output files. It also improves efficiency on i386 platforms by adding a little bit of assembly where gcc isn't efficient.

diff --git a/contrib/halog/Makefile b/contrib/halog/Makefile index c488470..680a5b7 100644 --- a/contrib/halog/Makefile +++ b/contrib/halog/Makefile

@@ -2,15 +2,14 @@ INCLUDE = -I../../include -I$(EBTREE_DIR) CC = gcc + +# note: it is recommended to also add -fomit-frame-pointer on i386 OPTIMIZE = -O3 -OBJS = halog halog64 +OBJS = halog halog: halog.c fgets2.c $(CC) $(OPTIMIZE) -o $@ $(INCLUDE) $(EBTREE_DIR)/ebtree.c $(EBTREE_DIR)/eb32tree.c $(EBTREE_DIR)/eb64tree.c $(EBTREE_DIR)/ebmbtree.c $(EBTREE_DIR)/ebsttree.c $(EBTREE_DIR)/ebistree.c $(EBTREE_DIR)/ebimtree.c $^ -halog64: halog.c fgets2-64.c - $(CC) $(OPTIMIZE) -o $@ $(INCLUDE) $(EBTREE_DIR)/ebtree.c $(EBTREE_DIR)/eb32tree.c $(EBTREE_DIR)/eb64tree.c $(EBTREE_DIR)/ebmbtree.c $(EBTREE_DIR)/ebsttree.c $(EBTREE_DIR)/ebistree.c $(EBTREE_DIR)/ebimtree.c $^ - clean: rm -f $(OBJS)

diff --git a/contrib/halog/fgets2-64.c b/contrib/halog/fgets2-64.c deleted file mode 100644 index 1be6f22..0000000 --- a/contrib/halog/fgets2-64.c +++ /dev/null

@@ -1,175 +0,0 @@ -/* - * fast fgets() replacement for log parsing - * - * Copyright 2000-2009 Willy Tarreau <w@1wt.eu> - * - * This program 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. - * - * This function manages its own buffer and returns a pointer to that buffer - * in order to avoid expensive memory copies. It also checks for line breaks - * 32 bits at a time. It could be improved a lot using mmap() but we would - * not be allowed to replace trailing \n with zeroes and we would be limited - * to small log files on 32-bit machines. - * - */ - -#include <stdlib.h> -#include <string.h> -#include <stdio.h> -#include <unistd.h> - -// return non-zero if the integer contains at least one zero byte -static inline unsigned int has_zero(unsigned int x) -{ - unsigned int y; - - /* Principle: we want to perform 4 tests on one 32-bit int at once. For - * this, we have to simulate an SIMD instruction which we don't have by - * default. The principle is that a zero byte is the only one which - * will cause a 1 to appear on the upper bit of a byte/word/etc... when - * we subtract 1. So we can detect a zero byte if a one appears at any - * of the bits 7, 15, 23 or 31 where it was not. It takes only one - * instruction to test for the presence of any of these bits, but it is - * still complex to check for their initial absence. Thus, we'll - * proceed differently : we first save and clear only those bits, then - * we check in the final result if one of them is present and was not. - */ - y = x; - y -= 0x01010101; /* generate a carry */ - y &= ~x; /* clear the bits that were already set */ - return y & 0x80808080; -} - - -// return non-zero if the argument contains at least one zero byte. See principle above. -static inline unsigned long long has_zero64(unsigned long long x) -{ - unsigned long long y; - - y = x; - y -= 0x0101010101010101ULL; /* generate a carry */ - y &= ~x; /* clear the bits that were already set */ - return y & 0x8080808080808080ULL; -} - -#define FGETS2_BUFSIZE (256*1024) -const char *fgets2(FILE *stream) -{ - static char buffer[FGETS2_BUFSIZE + 68]; - static char *end = buffer; - static char *line = buffer; - - char *next; - int ret; - - next = line; - - while (1) { - /* this is a speed-up, we read 64 bits at once and check for an - * LF character there. We stop if found then continue one at a - * time. - */ - - if (next <= end) { - /* max 3 bytes tested here */ - while ((((unsigned long)next) & 3) && *next != '\n') - next++; - - /* maybe we have can skip 4 more bytes */ - if ((((unsigned long)next) & 4) && !has_zero(*(unsigned int *)next ^ 0x0A0A0A0AU)) - next += 4; - } - - /* now next is multiple of 8 or equal to end */ - while (next <= (end-68)) { - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) - break; - next += 8; - } - - /* maybe we can skip 4 more bytes */ - if (!has_zero(*(unsigned int *)next ^ 0x0A0A0A0AU)) - next += 4; - - /* We finish if needed : if <next> is below <end>, it means we - * found an LF in one of the 4 following bytes. - */ - while (next < end) { - if (*next == '\n') { - const char *start = line; - - *next = '\0'; - line = next + 1; - return start; - } - next++; - } - - /* we found an incomplete line. First, let's move the - * remaining part of the buffer to the beginning, then - * try to complete the buffer with a new read. We can't - * rely on <next> anymore because it went past <end>. - */ - if (line > buffer) { - if (end != line) - memmove(buffer, line, end - line); - end = buffer + (end - line); - next = end; - line = buffer; - } else { - if (end == buffer + FGETS2_BUFSIZE) - return NULL; - } - - ret = read(fileno(stream), end, buffer + FGETS2_BUFSIZE - end); - - if (ret <= 0) { - if (end == line) - return NULL; - - *end = '\0'; - end = line; /* ensure we stop next time */ - return line; - } - - end += ret; - *end = '\n'; /* make parser stop ASAP */ - /* search for '\n' again */ - } -} - -#ifdef BENCHMARK -int main() { - const char *p; - unsigned int lines = 0; - - while ((p=fgets2(stdin))) - lines++; - printf("lines=%d\n", lines); - return 0; -} -#endif

diff --git a/contrib/halog/fgets2.c b/contrib/halog/fgets2.c index 1fd19d7..88c4d5c 100644 --- a/contrib/halog/fgets2.c +++ b/contrib/halog/fgets2.c

@@ -1,18 +1,27 @@ /* * fast fgets() replacement for log parsing * - * Copyright 2000-2009 Willy Tarreau <w@1wt.eu> + * Copyright 2000-2012 Willy Tarreau <w@1wt.eu> * - * This program 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. + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation, version 2.1 + * exclusively. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * This function manages its own buffer and returns a pointer to that buffer * in order to avoid expensive memory copies. It also checks for line breaks - * 32 bits at a time. It could be improved a lot using mmap() but we would - * not be allowed to replace trailing \n with zeroes and we would be limited - * to small log files on 32-bit machines. + * 32 or 64 bits at a time. It could be improved a lot using mmap() but we + * would not be allowed to replace trailing \n with zeroes and we would be + * limited to small log files on 32-bit machines. * */ @@ -21,8 +30,12 @@ #include <stdio.h> #include <unistd.h> +#ifndef FGETS2_BUFSIZE +#define FGETS2_BUFSIZE (256*1024) +#endif + -// return non-zero if the integer contains at least one zero byte -static inline unsigned int has_zero(unsigned int x) +/* return non-zero if the integer contains at least one zero byte */ +static inline unsigned int has_zero32(unsigned int x) { unsigned int y; @@ -36,62 +49,138 @@ * still complex to check for their initial absence. Thus, we'll * proceed differently : we first save and clear only those bits, then * we check in the final result if one of them is present and was not. + * The order of operations below is important to save registers and + * tests. The result is used as a boolean, so the last test must apply + * on the constant so that it can efficiently be inlined. */ - y = x; - y -= 0x01010101; /* generate a carry */ - y &= ~x; /* clear the bits that were already set */ - return y & 0x80808080; +#if defined(__i386__) + /* gcc on x86 loves copying registers over and over even on code that + * simple, so let's do it by hand to prevent it from doing so :-( + */ + asm("lea -0x01010101(%0),%1\n" + "not %0\n" + "and %1,%0\n" + : "=a" (x), "=r"(y) + : "0" (x) + ); + return x & 0x80808080; +#else + y = x - 0x01010101; /* generate a carry */ + x = ~x & y; /* clear the bits that were already set */ + return x & 0x80808080; +#endif } +/* return non-zero if the argument contains at least one zero byte. See principle above. */ +static inline unsigned long long has_zero64(unsigned long long x) +{ + unsigned long long y; -#define FGETS2_BUFSIZE (256*1024) + y = x - 0x0101010101010101ULL; /* generate a carry */ + y &= ~x; /* clear the bits that were already set */ + return y & 0x8080808080808080ULL; +} + +static inline unsigned long has_zero(unsigned long x) +{ + return (sizeof(x) == 8) ? has_zero64(x) : has_zero32(x); +} + const char *fgets2(FILE *stream) { - static char buffer[FGETS2_BUFSIZE + 32]; + static char buffer[FGETS2_BUFSIZE + 68]; /* Note: +32 is enough on 32-bit systems */ static char *end = buffer; static char *line = buffer; - char *next; int ret; next = line; while (1) { - /* this is a speed-up, we read 32 bits at once and check for an - * LF character there. We stop if found then continue one at a - * time. - */ - while (next < end && (((unsigned long)next) & 3) && *next != '\n') - next++; + if (sizeof(long) == 4) { /* 32-bit system */ + /* this is a speed-up, we read 32 bits at once and check for an + * LF character there. We stop if found then continue one at a + * time. + */ + while (next < end && (((unsigned long)next) & 3) && *next != '\n') + next++; + + /* Now next is multiple of 4 or equal to end. We know we can safely + * read up to 32 bytes past end if needed because they're allocated. + */ + while (next < end) { + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + if (has_zero32(*(unsigned int *)next ^ 0x0A0A0A0A)) + break; + next += 4; + } + } + else { /* 64-bit system */ + /* this is a speed-up, we read 64 bits at once and check for an + * LF character there. We stop if found then continue one at a + * time. + */ + if (next <= end) { + /* max 3 bytes tested here */ + while ((((unsigned long)next) & 3) && *next != '\n') + next++; + + /* maybe we have can skip 4 more bytes */ + if ((((unsigned long)next) & 4) && !has_zero32(*(unsigned int *)next ^ 0x0A0A0A0AU)) + next += 4; + } + + /* now next is multiple of 8 or equal to end */ + while (next <= (end-68)) { + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + if (has_zero64(*(unsigned long long *)next ^ 0x0A0A0A0A0A0A0A0AULL)) + break; + next += 8; + } - /* Now next is multiple of 4 or equal to end. We know we can safely - * read up to 32 bytes past end if needed because they're allocated. - */ - while (next < end) { - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; - if (has_zero(*(unsigned int *)next ^ 0x0A0A0A0A)) - break; - next += 4; + /* maybe we can skip 4 more bytes */ + if (!has_zero32(*(unsigned int *)next ^ 0x0A0A0A0AU)) + next += 4; } /* We finish if needed : if <next> is below <end>, it means we