| Message ID | 20180202231622.23214-1-blp@ovn.org |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] util: Use lookup table to optimize hexit_value(). | expand |
Looks good to me, thanks. Reviewed-by: Yifeng Sun <pkusunyifeng@gmail.com> On Fri, Feb 2, 2018 at 3:16 PM, Ben Pfaff <blp@ovn.org> wrote: > Daniel Alvarez Sanchez reported a significant overall speedup in ovn-northd > due to a similar patch. > > Reported-by: Daniel Alvarez Sanchez <dalvarez@redhat.com> > Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018- > February/046120.html > Signed-off-by: Ben Pfaff <blp@ovn.org> > --- > lib/util.c | 39 +++++++++++++-------------------------- > 1 file changed, 13 insertions(+), 26 deletions(-) > > diff --git a/lib/util.c b/lib/util.c > index a4d22df0c359..2e7765e41f03 100644 > --- a/lib/util.c > +++ b/lib/util.c > @@ -843,32 +843,19 @@ str_to_double(const char *s, double *d) > int > hexit_value(int c) > { > - switch (c) { > - case '0': case '1': case '2': case '3': case '4': > - case '5': case '6': case '7': case '8': case '9': > - return c - '0'; > - > - case 'a': case 'A': > - return 0xa; > - > - case 'b': case 'B': > - return 0xb; > - > - case 'c': case 'C': > - return 0xc; > - > - case 'd': case 'D': > - return 0xd; > - > - case 'e': case 'E': > - return 0xe; > - > - case 'f': case 'F': > - return 0xf; > - > - default: > - return -1; > - } > + static const signed char tbl[UCHAR_MAX + 1] = { > +#define TBL(x) \ > + ( x >= '0' && x <= '9' ? x - '0' \ > + : x >= 'a' && x <= 'f' ? x - 'a' + 0xa \ > + : x >= 'A' && x <= 'F' ? x - 'A' + 0xa \ > + : -1) > +#define TBL0(x) TBL(x), TBL((x) + 1), TBL((x) + 2), TBL((x) + 3) > +#define TBL1(x) TBL0(x), TBL0((x) + 4), TBL0((x) + 8), TBL0((x) + 12) > +#define TBL2(x) TBL1(x), TBL1((x) + 16), TBL1((x) + 32), TBL1((x) + 48) > + TBL2(0), TBL2(64), TBL2(128), TBL2(192) > + }; > + > + return tbl[c]; > } > > /* Returns the integer value of the 'n' hexadecimal digits starting at > 's', or > -- > 2.15.1 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev >
Thanks for the patch, Ben. Looks good to me. Acked-by: Daniel Alvarez <dalvarez@redhat.com> On Sat, Feb 3, 2018 at 12:16 AM, Ben Pfaff <blp@ovn.org> wrote: > Daniel Alvarez Sanchez reported a significant overall speedup in ovn-northd > due to a similar patch. > > Reported-by: Daniel Alvarez Sanchez <dalvarez@redhat.com> > Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018- > February/046120.html > Signed-off-by: Ben Pfaff <blp@ovn.org> > --- > lib/util.c | 39 +++++++++++++-------------------------- > 1 file changed, 13 insertions(+), 26 deletions(-) > > diff --git a/lib/util.c b/lib/util.c > index a4d22df0c359..2e7765e41f03 100644 > --- a/lib/util.c > +++ b/lib/util.c > @@ -843,32 +843,19 @@ str_to_double(const char *s, double *d) > int > hexit_value(int c) > { > - switch (c) { > - case '0': case '1': case '2': case '3': case '4': > - case '5': case '6': case '7': case '8': case '9': > - return c - '0'; > - > - case 'a': case 'A': > - return 0xa; > - > - case 'b': case 'B': > - return 0xb; > - > - case 'c': case 'C': > - return 0xc; > - > - case 'd': case 'D': > - return 0xd; > - > - case 'e': case 'E': > - return 0xe; > - > - case 'f': case 'F': > - return 0xf; > - > - default: > - return -1; > - } > + static const signed char tbl[UCHAR_MAX + 1] = { > +#define TBL(x) \ > + ( x >= '0' && x <= '9' ? x - '0' \ > + : x >= 'a' && x <= 'f' ? x - 'a' + 0xa \ > + : x >= 'A' && x <= 'F' ? x - 'A' + 0xa \ > + : -1) > +#define TBL0(x) TBL(x), TBL((x) + 1), TBL((x) + 2), TBL((x) + 3) > +#define TBL1(x) TBL0(x), TBL0((x) + 4), TBL0((x) + 8), TBL0((x) + 12) > +#define TBL2(x) TBL1(x), TBL1((x) + 16), TBL1((x) + 32), TBL1((x) + 48) > + TBL2(0), TBL2(64), TBL2(128), TBL2(192) > + }; > + > + return tbl[c]; > } > > /* Returns the integer value of the 'n' hexadecimal digits starting at > 's', or > -- > 2.15.1 > >
Hi Ben, On Fri, Feb 02, 2018 at 11:16 PM GMT, Ben Pfaff wrote: > Daniel Alvarez Sanchez reported a significant overall speedup in ovn-northd > due to a similar patch. > > Reported-by: Daniel Alvarez Sanchez <dalvarez@redhat.com> > Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018-February/046120.html > Signed-off-by: Ben Pfaff <blp@ovn.org> > --- > lib/util.c | 39 +++++++++++++-------------------------- > 1 file changed, 13 insertions(+), 26 deletions(-) > > diff --git a/lib/util.c b/lib/util.c > index a4d22df0c359..2e7765e41f03 100644 > --- a/lib/util.c > +++ b/lib/util.c > @@ -843,32 +843,19 @@ str_to_double(const char *s, double *d) > int > hexit_value(int c) > { > - switch (c) { > - case '0': case '1': case '2': case '3': case '4': > - case '5': case '6': case '7': case '8': case '9': > - return c - '0'; > - > - case 'a': case 'A': > - return 0xa; > - > - case 'b': case 'B': > - return 0xb; > - > - case 'c': case 'C': > - return 0xc; > - > - case 'd': case 'D': > - return 0xd; > - > - case 'e': case 'E': > - return 0xe; > - > - case 'f': case 'F': > - return 0xf; > - > - default: > - return -1; > - } > + static const signed char tbl[UCHAR_MAX + 1] = { > +#define TBL(x) \ > + ( x >= '0' && x <= '9' ? x - '0' \ > + : x >= 'a' && x <= 'f' ? x - 'a' + 0xa \ > + : x >= 'A' && x <= 'F' ? x - 'A' + 0xa \ > + : -1) > +#define TBL0(x) TBL(x), TBL((x) + 1), TBL((x) + 2), TBL((x) + 3) > +#define TBL1(x) TBL0(x), TBL0((x) + 4), TBL0((x) + 8), TBL0((x) + 12) > +#define TBL2(x) TBL1(x), TBL1((x) + 16), TBL1((x) + 32), TBL1((x) + 48) > + TBL2(0), TBL2(64), TBL2(128), TBL2(192) > + }; > + > + return tbl[c]; > } > > /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or It caught my attention that the contract with hexit_value() callers has changed. Previously we had a catch-all clause for out-of-range values. Now there will be an out-of-bounds read. Perhaps a check if input is in range would be in place? Or some kind of input sanitization like in the original patch? WDYT? -Jakub
On Mon, Feb 05, 2018 at 05:03:13PM +0100, Jakub Sitnicki wrote: > Hi Ben, > > On Fri, Feb 02, 2018 at 11:16 PM GMT, Ben Pfaff wrote: > > Daniel Alvarez Sanchez reported a significant overall speedup in ovn-northd > > due to a similar patch. > > > > Reported-by: Daniel Alvarez Sanchez <dalvarez@redhat.com> > > Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018-February/046120.html > > Signed-off-by: Ben Pfaff <blp@ovn.org> > > --- > > lib/util.c | 39 +++++++++++++-------------------------- > > 1 file changed, 13 insertions(+), 26 deletions(-) > > > > diff --git a/lib/util.c b/lib/util.c > > index a4d22df0c359..2e7765e41f03 100644 > > --- a/lib/util.c > > +++ b/lib/util.c > > @@ -843,32 +843,19 @@ str_to_double(const char *s, double *d) > > int > > hexit_value(int c) > > { > > - switch (c) { > > - case '0': case '1': case '2': case '3': case '4': > > - case '5': case '6': case '7': case '8': case '9': > > - return c - '0'; > > - > > - case 'a': case 'A': > > - return 0xa; > > - > > - case 'b': case 'B': > > - return 0xb; > > - > > - case 'c': case 'C': > > - return 0xc; > > - > > - case 'd': case 'D': > > - return 0xd; > > - > > - case 'e': case 'E': > > - return 0xe; > > - > > - case 'f': case 'F': > > - return 0xf; > > - > > - default: > > - return -1; > > - } > > + static const signed char tbl[UCHAR_MAX + 1] = { > > +#define TBL(x) \ > > + ( x >= '0' && x <= '9' ? x - '0' \ > > + : x >= 'a' && x <= 'f' ? x - 'a' + 0xa \ > > + : x >= 'A' && x <= 'F' ? x - 'A' + 0xa \ > > + : -1) > > +#define TBL0(x) TBL(x), TBL((x) + 1), TBL((x) + 2), TBL((x) + 3) > > +#define TBL1(x) TBL0(x), TBL0((x) + 4), TBL0((x) + 8), TBL0((x) + 12) > > +#define TBL2(x) TBL1(x), TBL1((x) + 16), TBL1((x) + 32), TBL1((x) + 48) > > + TBL2(0), TBL2(64), TBL2(128), TBL2(192) > > + }; > > + > > + return tbl[c]; > > } > > > > /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or > > It caught my attention that the contract with hexit_value() callers has > changed. Previously we had a catch-all clause for out-of-range values. > Now there will be an out-of-bounds read. > > Perhaps a check if input is in range would be in place? > Or some kind of input sanitization like in the original patch? I don't think any current caller passes an out-of-range value. What if I just change the parameter type to "unsigned char"?
On Mon, Feb 05, 2018 at 04:25 PM GMT, Ben Pfaff wrote: > On Mon, Feb 05, 2018 at 05:03:13PM +0100, Jakub Sitnicki wrote: >> >> It caught my attention that the contract with hexit_value() callers has >> changed. Previously we had a catch-all clause for out-of-range values. >> Now there will be an out-of-bounds read. >> >> Perhaps a check if input is in range would be in place? >> Or some kind of input sanitization like in the original patch? > > I don't think any current caller passes an out-of-range value. > > What if I just change the parameter type to "unsigned char"? I also didn't find any existing callers that might be in trouble. Changing parameter type to "unsigned char" sounds good to me. Thanks, Jakub
On Mon, Feb 05, 2018 at 05:40:28PM +0100, Jakub Sitnicki wrote: > On Mon, Feb 05, 2018 at 04:25 PM GMT, Ben Pfaff wrote: > > On Mon, Feb 05, 2018 at 05:03:13PM +0100, Jakub Sitnicki wrote: > >> > >> It caught my attention that the contract with hexit_value() callers has > >> changed. Previously we had a catch-all clause for out-of-range values. > >> Now there will be an out-of-bounds read. > >> > >> Perhaps a check if input is in range would be in place? > >> Or some kind of input sanitization like in the original patch? > > > > I don't think any current caller passes an out-of-range value. > > > > What if I just change the parameter type to "unsigned char"? > > I also didn't find any existing callers that might be in trouble. > > Changing parameter type to "unsigned char" sounds good to me. Thanks. I made that change, applied acks, and pushed this to master.
diff --git a/lib/util.c b/lib/util.c index a4d22df0c359..2e7765e41f03 100644 --- a/lib/util.c +++ b/lib/util.c @@ -843,32 +843,19 @@ str_to_double(const char *s, double *d) int hexit_value(int c) { - switch (c) { - case '0': case '1': case '2': case '3': case '4': - case '5': case '6': case '7': case '8': case '9': - return c - '0'; - - case 'a': case 'A': - return 0xa; - - case 'b': case 'B': - return 0xb; - - case 'c': case 'C': - return 0xc; - - case 'd': case 'D': - return 0xd; - - case 'e': case 'E': - return 0xe; - - case 'f': case 'F': - return 0xf; - - default: - return -1; - } + static const signed char tbl[UCHAR_MAX + 1] = { +#define TBL(x) \ + ( x >= '0' && x <= '9' ? x - '0' \ + : x >= 'a' && x <= 'f' ? x - 'a' + 0xa \ + : x >= 'A' && x <= 'F' ? x - 'A' + 0xa \ + : -1) +#define TBL0(x) TBL(x), TBL((x) + 1), TBL((x) + 2), TBL((x) + 3) +#define TBL1(x) TBL0(x), TBL0((x) + 4), TBL0((x) + 8), TBL0((x) + 12) +#define TBL2(x) TBL1(x), TBL1((x) + 16), TBL1((x) + 32), TBL1((x) + 48) + TBL2(0), TBL2(64), TBL2(128), TBL2(192) + }; + + return tbl[c]; } /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
Daniel Alvarez Sanchez reported a significant overall speedup in ovn-northd due to a similar patch. Reported-by: Daniel Alvarez Sanchez <dalvarez@redhat.com> Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018-February/046120.html Signed-off-by: Ben Pfaff <blp@ovn.org> --- lib/util.c | 39 +++++++++++++-------------------------- 1 file changed, 13 insertions(+), 26 deletions(-)