Re: svn commit: r211304 - head/lib/libutil

2010-08-24 Thread Dag-Erling Smørgrav 
Bruce Evans b...@optusnet.com.au writes:
 Dag-Erling Smørgrav d...@des.no writes:
  That's awesome!  Any way I can convince you to fix expand_number() as
  well?  I got a detailed explanation of what's wrong with it (both before
  and after my commits) from bde@ (cc:ed) in private correspondence; I can
  forward it to you if he doesn't mind.
 OK.

 I think the final point was that it should go back to supporting signed
 numbers (only), and that means int64_t ones until scientificize^dehumanize^W
 humanize_number() is fixed to support intmax_t ones.

See attachments.

DES
-- 
Dag-Erling Smørgrav - d...@des.no

---BeginMessage---
 The following places were even more broken to begin with:
 geom/core/geom.c: this calls expand_number() on an intmax_t *
 ipfw/dummynet.c: this calls expand_number() on an int64_t *, after starting
  with a uint64_t * and bogusly casting to int64_t *.

 I'll fix these two, do you have further suggestions or a list of other
 instances that need fixing?

 BTW, would you prefer fixing geom.c to use uint64_t, or fixing
 expand_number() to use uintmax_t?

I prefer fixing expand_number() to support negative numbers again.  It
should support them since it is supposed to be the inverse of
scientificize^Whumanize_number(), which can and does print them in
a useful way for at least free space in df.  I don't know of any use
for them in input, but it simplifies at least the documentation to
have an exact inverse.

However, it should probably still return negative numbers via a
uintmax_t, like strtoumax() does, so that yet another BAD API isn't
required.  Externally, this requires documenting what expand_number()
actually does, since it uses strtoumax() internally but currently says
nothing except for the false statement that it is the inverse of
scientifize_number(), plus it requires something to determine whether
the number is signed.

Internally, this requires a bit more care with shifting of negative numbers.
A negative number is by definition one with a leading minus sign.
strtoumax() will return these converted to large positive numbers, and
currently any shift of them will give overflow.  Instead, they should
be converted to a sign and a positive value before shifting.  Pseudocode:

num = strtoumax();
Return if error.
shift = mumble();   /* mult = mumble() (recursive) for dd */
Return if error.
Return if shift == 1 (this gives strtou*()'s/our historical arcane
error handling for negative values, but only for non-shifted ones).
snum = strtoimax();
Return if error (must be range error with snum  0).
signed = (snum  0);
if (signed)
num = -(uintmax_t)snum; /* XXX assumes normal machine */
cutlim = (signed ? INTMAX_MAX / ((intmax_t)1  shift) :
UINTMAX_MAX / ((uintmax_t)1  shift);
if (num  cutlim)
overflow();
else
num = shift;
if (signed)
num = -(intmax_t)num;

My dd get_off_t() gets this wrong, oops.  Just using the unsigned version
fails for things like -1k.  The -1 becomes UINTMAX_MAX and any shifing
of this overflows (or if overflow is ignored, gives back -1 on normal
machines).  -1k isn't useful in dd -- all that is needed is for things
like 0x (2**64-1) to work, which they don't if strtoimax()
is used -- with 64-bit intmax_t, it clips this value to 0x7FFF/
ERANGE.

Here is part of the man page for strtoumax() that gives details relevant
to expand_number():

% STRTOUL(3) FreeBSD Library Functions Manual STRTOUL(3)

Bug: there should be a separate man page for each function.

% 
% NAME
%  strtoul, strtoull, strtoumax, strtouq -- convert a string to an unsigned
%  long, unsigned long long, uintmax_t, or u_quad_t integer
% 
% LIBRARY
%  Standard C Library (libc, -lc)
% 
% SYNOPSIS
%  #include stdlib.h
%  #include limits.h

Bug: limits.h is not needed for using strtoul() or strtoull().

% 
%  unsigned long
%  strtoul(const char * restrict nptr, char ** restrict endptr, int base);
% 
%  unsigned long long
%  strtoull(const char * restrict nptr, char ** restrict endptr, int base);
% 
%  #include inttypes.h

Bug: not consistently buggy with the above -- no limits.h here.

% 
%  uintmax_t
%  strtoumax(const char * restrict nptr, char ** restrict endptr, int base);
% 
%  #include sys/types.h
%  #include stdlib.h
%  #include limits.h
% 
%  u_quad_t
%  strtouq(const char *nptr, char **endptr, int base);

Bugs:
1. sys/types.h is needed in theory but not in practice, since someone
changed the actual declaration of this in stdlib.h to use uint64_t.
2. stdlib.h says that this and strtoq() are to be removed in FreeBSD-6.0,.

% 
% DESCRIPTION
%  The strtoul() function converts the string in nptr to an unsigned long
%  value.  The strtoull() function converts the string

Re: svn commit: r211304 - head/lib/libutil

2010-08-23 Thread Dag-Erling Smørgrav 
Dimitry Andric dimi...@andric.com writes:
 Dag-Erling Smørgrav d...@des.no writes:
  Bruce Cran br...@cran.org.uk writes:
   Somewhat related, there are overflow bugs in humanize_number - for
   example df(1) fails to display space from a 100PB filesystem
   correctly.
  Patch?  :)
 Attached.  This makes humanize_number() work properly for all possible
 int64_t values.

That's awesome!  Any way I can convince you to fix expand_number() as
well?  I got a detailed explanation of what's wrong with it (both before
and after my commits) from bde@ (cc:ed) in private correspondence; I can
forward it to you if he doesn't mind.

DES
-- 
Dag-Erling Smørgrav - d...@des.no
___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org

Re: svn commit: r211304 - head/lib/libutil

2010-08-23 Thread Bruce Evans 

On Mon, 23 Aug 2010, [utf-8] Dag-Erling Sm??rgrav wrote:


Dimitry Andric dimi...@andric.com writes:

Dag-Erling Sm??rgrav d...@des.no writes:

Bruce Cran br...@cran.org.uk writes:

Somewhat related, there are overflow bugs in humanize_number - for
example df(1) fails to display space from a 100PB filesystem
correctly.

Patch?  :)

Attached.  This makes humanize_number() work properly for all possible
int64_t values.


That's awesome!  Any way I can convince you to fix expand_number() as
well?  I got a detailed explanation of what's wrong with it (both before
and after my commits) from bde@ (cc:ed) in private correspondence; I can
forward it to you if he doesn't mind.


OK.

I think the final point was that it should go back to supporting signed
numbers (only), and that means int64_t ones until scientificize^dehumanize^W
humanize_number() is fixed to support intmax_t ones.

Bruce___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org

Re: svn commit: r211304 - head/lib/libutil

2010-08-22 Thread Dimitry Andric 
On 2010-08-16 10:51, Dag-Erling Smørgrav wrote:
 Bruce Cran br...@cran.org.uk writes:
 Somewhat related, there are overflow bugs in humanize_number - for
 example df(1) fails to display space from a 100PB filesystem
 correctly.
 
 Patch?  :)

Attached.  This makes humanize_number() work properly for all possible
int64_t values.

It has one significant behaviour change, though: with the original
version of humanize_number(), if you used a fixed scale parameter, and
the number was larger than the buffer could contain, it would simply
stomp over the end of the buffer.  With this fix, it will return -1
instead.  I hope you agree that is better. :)
diff --git a/lib/libutil/humanize_number.c b/lib/libutil/humanize_number.c
index de98587..a304137 100644
--- a/lib/libutil/humanize_number.c
+++ b/lib/libutil/humanize_number.c
@@ -42,13 +42,34 @@ __FBSDID($FreeBSD$);
 #include locale.h
 #include libutil.h
 
+static inline void
+divide(int64_t num, int64_t den, int64_t *quotp, int64_t *quotrp, int *fracrp)
+{
+   int frac;
+
+   if (den == 1) {
+   *quotp = *quotrp = num;
+   *fracrp = 0;
+   } else {
+   *quotp = *quotrp = num / den;
+   frac = (5 * (num % den)) / (den / 2);
+   if (frac = 5)
+   ++*quotp;
+   *fracrp = (5 * (num % den) + den / 4) / (den / 2);
+   if (*fracrp == 10) {
+   ++*quotrp;
+   *fracrp = 0;
+   }
+   }
+}
+
 int
 humanize_number(char *buf, size_t len, int64_t bytes,
 const char *suffix, int scale, int flags)
 {
const char *prefixes, *sep;
-   int b, i, r, maxscale, s1, s2, sign;
-   int64_t divisor, max;
+   int i, r, maxscale, sign, fracr;
+   int64_t divisor, max, fulldiv, quot, quotr;
size_t  baselen;
 
assert(buf != NULL);
@@ -88,11 +109,10 @@ humanize_number(char *buf, size_t len, int64_t bytes,
buf[0] = '\0';
if (bytes  0) {
sign = -1;
-   bytes *= -100;
+   bytes = -bytes;
baselen = 3;/* sign, digit, prefix */
} else {
sign = 1;
-   bytes *= 100;
baselen = 2;/* digit, prefix */
}
if (flags  HN_NOSPACE)
@@ -107,39 +127,42 @@ humanize_number(char *buf, size_t len, int64_t bytes,
if (len  baselen + 1)
return (-1);
 
+   /* Determine the maximum number that fits. */
+   for (max = 1, i = len - baselen; i--  0;)
+   max *= 10;
+
if (scale  (HN_AUTOSCALE | HN_GETSCALE)) {
-   /* See if there is additional columns can be used. */
-   for (max = 100, i = len - baselen; i--  0;)
-   max *= 10;
-
-   /*
-* Divide the number until it fits the given column.
-* If there will be an overflow by the rounding below,
-* divide once more.
-*/
-   for (i = 0; bytes = max - 50  i  maxscale; i++)
-   bytes /= divisor;
+   /* Divide the number until it fits the given length. */
+   for (i = 0, fulldiv = 1; i  maxscale; i++) {
+   divide(bytes, fulldiv, quot, quotr, fracr);
+   if ((quotr  10  i  0  flags  HN_DECIMAL 
+   quotr * 100  max) || quot  max)
+   break;
+   fulldiv *= divisor;
+   }
 
if (scale  HN_GETSCALE)
return (i);
-   } else
-   for (i = 0; i  scale  i  maxscale; i++)
-   bytes /= divisor;
+   } else {
+   for (i = 0, fulldiv = 1; i  scale; i++)
+   fulldiv *= divisor;
+   divide(bytes, fulldiv, quot, quotr, fracr);
+   if ((quotr  10  i  0  flags  HN_DECIMAL 
+   quotr * 100 = max) || quot = max)
+   return (-1);
+   }
 
-   /* If a value = 9.9 after rounding and ... */
-   if (bytes  995  i  0  flags  HN_DECIMAL) {
+   /* If quotient  10 after rounding and ... */
+   if (quotr  10  i  0  flags  HN_DECIMAL) {
/* baselen + \0 + .N */
if (len  baselen + 1 + 2)
return (-1);
-   b = ((int)bytes + 5) / 10;
-   s1 = b / 10;
-   s2 = b % 10;
r = snprintf(buf, len, %d%s%d%s%s%s,
-   sign * s1, localeconv()-decimal_point, s2,
+   sign * (int) quotr, localeconv()-decimal_point, fracr,
sep, SCALE2PREFIX(i), suffix);
} else
r = snprintf(buf, len, % PRId64 %s%s%s,
-   sign * ((bytes + 50) / 100),
+   sign * quot,
sep, SCALE2PREFIX(i), suffix);

Re: svn commit: r211304 - head/lib/libutil

2010-08-16 Thread Dag-Erling Smørgrav 
Bruce Cran br...@cran.org.uk writes:
 Somewhat related, there are overflow bugs in humanize_number - for
 example df(1) fails to display space from a 100PB filesystem
 correctly.

Patch?  :)

DES
-- 
Dag-Erling Smørgrav - d...@des.no
___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org

Re: svn commit: r211304 - head/lib/libutil

2010-08-15 Thread Dag-Erling Smørgrav 
m...@freebsd.org writes:
 I think it's possible for the number to overflow but also not shrink.
 e.g. 0x12345678T.

Ah, you're right, I didn't think of that.  Thanks.

DES
-- 
Dag-Erling Smørgrav - d...@des.no
___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org

Re: svn commit: r211304 - head/lib/libutil

2010-08-15 Thread Bruce Cran 
On Sat, 14 Aug 2010 14:34:36 + (UTC)
Dag-Erling Smorgrav d...@freebsd.org wrote:

 Author: des
 Date: Sat Aug 14 14:34:36 2010
 New Revision: 211304
 URL: http://svn.freebsd.org/changeset/base/211304
 
 Log:
   Simplify expand_number() by combining the (unrolled) loop with the
   switch.  Since expand_number() does not accept negative numbers,
 switch from int64_t to uint64_t; this makes it easier to check for
 overflow. 
   MFC after:  3 weeks

Somewhat related, there are overflow bugs in humanize_number - for
example df(1) fails to display space from a 100PB filesystem
correctly.

-- 
Bruce Cran
___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org

svn commit: r211304 - head/lib/libutil

2010-08-14 Thread Dag-Erling Smorgrav 
Author: des
Date: Sat Aug 14 14:34:36 2010
New Revision: 211304
URL: http://svn.freebsd.org/changeset/base/211304

Log:
  Simplify expand_number() by combining the (unrolled) loop with the
  switch.  Since expand_number() does not accept negative numbers, switch
  from int64_t to uint64_t; this makes it easier to check for overflow.
  
  MFC after:3 weeks

Modified:
  head/lib/libutil/expand_number.c
  head/lib/libutil/libutil.h

Modified: head/lib/libutil/expand_number.c
==
--- head/lib/libutil/expand_number.cSat Aug 14 14:18:02 2010
(r211303)
+++ head/lib/libutil/expand_number.cSat Aug 14 14:34:36 2010
(r211304)
@@ -37,7 +37,7 @@ __FBSDID($FreeBSD$);
 
 /*
  * Convert an expression of the following forms to a int64_t.
- * 1) A positive decimal number.
+ * 1) A positive decimal number.
  * 2) A positive decimal number followed by a 'b' or 'B' (mult by 1).
  * 3) A positive decimal number followed by a 'k' or 'K' (mult by 1  10).
  * 4) A positive decimal number followed by a 'm' or 'M' (mult by 1  20).
@@ -47,14 +47,12 @@ __FBSDID($FreeBSD$);
  * 8) A positive decimal number followed by a 'e' or 'E' (mult by 1  60).
  */
 int
-expand_number(const char *buf, int64_t *num)
+expand_number(const char *buf, uint64_t *num)
 {
-   static const char unit[] = bkmgtpe;
-   char *endptr, s;
-   int64_t number;
-   int i;
+   uint64_t number;
+   char *endptr;
 
-   number = strtoimax(buf, endptr, 0);
+   number = strtoumax(buf, endptr, 0);
 
if (endptr == buf) {
/* No valid digits. */
@@ -68,15 +66,23 @@ expand_number(const char *buf, int64_t *
return (0);
}
 
-   s = tolower(*endptr);
-   switch (s) {
-   case 'b':
-   case 'k':
-   case 'm':
-   case 'g':
-   case 't':
-   case 'p':
+#define SHIFT(n, b)\
+   do { if ((n  b)  n) goto overflow; n = b; } while (0)
+
+   switch (tolower((unsigned char)*endptr)) {
case 'e':
+   SHIFT(number, 10);
+   case 'p':
+   SHIFT(number, 10);
+   case 't':
+   SHIFT(number, 10);
+   case 'g':
+   SHIFT(number, 10);
+   case 'm':
+   SHIFT(number, 10);
+   case 'k':
+   SHIFT(number, 10);
+   case 'b':
break;
default:
/* Unrecognized unit. */
@@ -84,17 +90,11 @@ expand_number(const char *buf, int64_t *
return (-1);
}
 
-   for (i = 0; unit[i] != '\0'; i++) {
-   if (s == unit[i])
-   break;
-   if ((number  0  (number  10)  number) ||
-   (number = 0  (number  10)  number)) {
-   errno = ERANGE;
-   return (-1);
-   }
-   number = 10;
-   }
-
*num = number;
return (0);
+
+overflow:
+   /* Overflow */
+   errno = ERANGE;
+   return (-1);
 }

Modified: head/lib/libutil/libutil.h
==
--- head/lib/libutil/libutil.h  Sat Aug 14 14:18:02 2010(r211303)
+++ head/lib/libutil/libutil.h  Sat Aug 14 14:34:36 2010(r211304)
@@ -109,7 +109,7 @@ int forkpty(int *_amaster, char *_name,
 struct termios *_termp, struct winsize *_winp);
 inthumanize_number(char *_buf, size_t _len, int64_t _number,
const char *_suffix, int _scale, int _flags);
-intexpand_number(const char *_buf, int64_t *_num);
+intexpand_number(const char *_buf, uint64_t *_num);
 const char *uu_lockerr(int _uu_lockresult);
 intuu_lock(const char *_ttyname);
 intuu_unlock(const char *_ttyname);
___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org

Re: svn commit: r211304 - head/lib/libutil

2010-08-14 Thread mdf 
On Sat, Aug 14, 2010 at 2:34 PM, Dag-Erling Smorgrav d...@freebsd.org wrote:
 Author: des
 Date: Sat Aug 14 14:34:36 2010
 New Revision: 211304
 URL: http://svn.freebsd.org/changeset/base/211304

 Log:
  Simplify expand_number() by combining the (unrolled) loop with the
  switch.  Since expand_number() does not accept negative numbers, switch
  from int64_t to uint64_t; this makes it easier to check for overflow.

  MFC after:    3 weeks

 Modified:
  head/lib/libutil/expand_number.c
  head/lib/libutil/libutil.h

 Modified: head/lib/libutil/expand_number.c
 ==
 --- head/lib/libutil/expand_number.c    Sat Aug 14 14:18:02 2010        
 (r211303)
 +++ head/lib/libutil/expand_number.c    Sat Aug 14 14:34:36 2010        
 (r211304)
 @@ -37,7 +37,7 @@ __FBSDID($FreeBSD$);

  /*
  * Convert an expression of the following forms to a int64_t.
 - *     1) A positive decimal number.
 + *     1) A positive decimal number.
  *     2) A positive decimal number followed by a 'b' or 'B' (mult by 1).
  *     3) A positive decimal number followed by a 'k' or 'K' (mult by 1  
 10).
  *     4) A positive decimal number followed by a 'm' or 'M' (mult by 1  
 20).
 @@ -47,14 +47,12 @@ __FBSDID($FreeBSD$);
  *     8) A positive decimal number followed by a 'e' or 'E' (mult by 1  
 60).
  */
  int
 -expand_number(const char *buf, int64_t *num)
 +expand_number(const char *buf, uint64_t *num)
  {
 -       static const char unit[] = bkmgtpe;
 -       char *endptr, s;
 -       int64_t number;
 -       int i;
 +       uint64_t number;
 +       char *endptr;

 -       number = strtoimax(buf, endptr, 0);
 +       number = strtoumax(buf, endptr, 0);

        if (endptr == buf) {
                /* No valid digits. */
 @@ -68,15 +66,23 @@ expand_number(const char *buf, int64_t *
                return (0);
        }

 -       s = tolower(*endptr);
 -       switch (s) {
 -       case 'b':
 -       case 'k':
 -       case 'm':
 -       case 'g':
 -       case 't':
 -       case 'p':
 +#define SHIFT(n, b)                                                    \
 +       do { if ((n  b)  n) goto overflow; n = b; } while (0)

I think it's possible for the number to overflow but also not shrink.
e.g. 0x12345678T.

Perhaps if (((n  b)  b) != n) would be better.

Thanks,
matthew

 +
 +       switch (tolower((unsigned char)*endptr)) {
        case 'e':
 +               SHIFT(number, 10);
 +       case 'p':
 +               SHIFT(number, 10);
 +       case 't':
 +               SHIFT(number, 10);
 +       case 'g':
 +               SHIFT(number, 10);
 +       case 'm':
 +               SHIFT(number, 10);
 +       case 'k':
 +               SHIFT(number, 10);
 +       case 'b':
                break;
        default:
                /* Unrecognized unit. */
 @@ -84,17 +90,11 @@ expand_number(const char *buf, int64_t *
                return (-1);
        }

 -       for (i = 0; unit[i] != '\0'; i++) {
 -               if (s == unit[i])
 -                       break;
 -               if ((number  0  (number  10)  number) ||
 -                   (number = 0  (number  10)  number)) {
 -                       errno = ERANGE;
 -                       return (-1);
 -               }
 -               number = 10;
 -       }
 -
        *num = number;
        return (0);
 +
 +overflow:
 +       /* Overflow */
 +       errno = ERANGE;
 +       return (-1);
  }

 Modified: head/lib/libutil/libutil.h
 ==
 --- head/lib/libutil/libutil.h  Sat Aug 14 14:18:02 2010        (r211303)
 +++ head/lib/libutil/libutil.h  Sat Aug 14 14:34:36 2010        (r211304)
 @@ -109,7 +109,7 @@ int forkpty(int *_amaster, char *_name,
                     struct termios *_termp, struct winsize *_winp);
  int    humanize_number(char *_buf, size_t _len, int64_t _number,
            const char *_suffix, int _scale, int _flags);
 -int    expand_number(const char *_buf, int64_t *_num);
 +int    expand_number(const char *_buf, uint64_t *_num);
  const char *uu_lockerr(int _uu_lockresult);
  int    uu_lock(const char *_ttyname);
  int    uu_unlock(const char *_ttyname);

___
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to svn-src-all-unsubscr...@freebsd.org