Re: [PATCH] 3/6 Avoid overflow in calculation of resvd blocks in resized fs

On Wed, Aug 16, 2006 at 03:51:50PM -0500, Eric Sandeen wrote:
> The way the new reserved blocks count was calculated at resize time could
> overflow pretty easily.
> 
> The new calculation changes the rounding slightly, so fix up the expected
> output for the resize tests as well.

I created a new function, e2p_percent, which won't overflow and which
calculates the percentages as accurately as possible, so it doesn't
need to adjust the expected output of the test suite.

						- Ted

# HG changeset patch
# User [email protected]
# Date 1156921693 14400
# Node ID 4a2b0d6c55fc3bea9e5bed4faa82845676f3be2b
# Parent  14e45223b10be14cc318f10b804a3fd535a86ad5
Fix potential 2**32-1 overflow by using e2p_percent()

Add a new functiom, e2p_percent(), which correct calculates the percentage
of a number based on a given percentage, without worrying about overflow
issues.  This is used where we calculate the number of reserved blocks using
a percentage of the total number of blocks in a filesystem.

Based on patches from Eric Sandeen, but generalized to use this new function.

Signed-off-by: "Theodore Ts'o" <[email protected]>
Signed-off-by: Eric Sandeen <[email protected]>

diff -r 14e45223b10b -r 4a2b0d6c55fc lib/e2p/ChangeLog
--- a/lib/e2p/ChangeLog	Wed Aug 30 02:16:55 2006 -0400
+++ b/lib/e2p/ChangeLog	Wed Aug 30 03:08:13 2006 -0400
@@ -1,3 +1,9 @@ 2006-08-05  Theodore Tso  <[email protected]
+2006-08-30  Theodore Tso  <[email protected]>
+
+	* percent.c (e2p_percent): Add a new function which accurate and
+		without risk of overflow calculates a percentage of a base
+		number.
+
 2006-08-05  Theodore Tso  <[email protected]>
 
 	* pf.c: Add support for EXT4_EXTENTS_FL flag.
diff -r 14e45223b10b -r 4a2b0d6c55fc lib/e2p/Makefile.in
--- a/lib/e2p/Makefile.in	Wed Aug 30 02:16:55 2006 -0400
+++ b/lib/e2p/Makefile.in	Wed Aug 30 03:08:13 2006 -0400
@@ -19,7 +19,7 @@ OBJS=		feature.o fgetflags.o fsetflags.o
 OBJS=		feature.o fgetflags.o fsetflags.o fgetversion.o fsetversion.o \
 		getflags.o getversion.o hashstr.o iod.o ls.o mntopts.o \
 		parse_num.o pe.o pf.o ps.o setflags.o setversion.o uuid.o \
-		ostype.o 
+		ostype.o percent.o
 
 SRCS=		$(srcdir)/feature.c $(srcdir)/fgetflags.c \
 		$(srcdir)/fsetflags.c $(srcdir)/fgetversion.c \
@@ -28,7 +28,7 @@ SRCS=		$(srcdir)/feature.c $(srcdir)/fge
 		$(srcdir)/ls.c $(srcdir)/mntopts.c $(srcdir)/parse_num.c \
 		$(srcdir)/pe.c $(srcdir)/pf.c $(srcdir)/ps.c \
 		$(srcdir)/setflags.c $(srcdir)/setversion.c $(srcdir)/uuid.c \
-		$(srcdir)/ostype.c
+		$(srcdir)/ostype.c $(srcdir)/percent.o
 HFILES= e2p.h
 
 LIBRARY= libe2p
diff -r 14e45223b10b -r 4a2b0d6c55fc lib/e2p/e2p.h
--- a/lib/e2p/e2p.h	Wed Aug 30 02:16:55 2006 -0400
+++ b/lib/e2p/e2p.h	Wed Aug 30 03:08:13 2006 -0400
@@ -50,3 +50,5 @@ unsigned long parse_num_blocks(const cha
 
 char *e2p_os2string(int os_type);
 int e2p_string2os(char *str);
+
+unsigned int e2p_percent(int percent, unsigned int base);
diff -r 14e45223b10b -r 4a2b0d6c55fc lib/e2p/percent.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lib/e2p/percent.c	Wed Aug 30 03:08:13 2006 -0400
@@ -0,0 +1,62 @@
+/*
+ * percent.c		- Take percentage of a number
+ *
+ * Copyright (C) 2006  Theodore Ts'o <[email protected]>
+ * 
+ * This file can be redistributed under the terms of the GNU Library General
+ * Public License
+ */
+
+#include "e2p.h"
+
+#include <stdlib.h>
+
+/*
+ * We work really hard to calculate this accurately, while avoiding
+ * an overflow.  "Is there a hyphen in anal-retentive?"  :-)
+ */
+unsigned int e2p_percent(int percent, unsigned int base)
+{
+	unsigned int mask = ~((1 << (sizeof(unsigned int) - 1) * 8) - 1);
+
+	if (100 % percent == 0)
+		return base / (100 / percent);
+	if (mask & base) 
+		return (base / 100) * percent;
+	return base * percent / 100;
+}
+
+#ifdef DEBUG
+#include <unistd.h>
+#include <stdio.h>
+
+main(int argc, char **argv)
+{
+	unsigned int base;
+	int percent;
+	char *p;
+	int log_block_size = 0;
+
+	if (argc != 3) {
+		fprintf(stderr, "Usage: %s percent base\n", argv[0]);
+		exit(1);
+	}
+
+	percent = strtoul(argv[1], &p, 0);
+	if (p[0] && p[1]) {
+		fprintf(stderr, "Bad percent: %s\n", argv[1]);
+		exit(1);
+	}
+	
+	base = strtoul(argv[2], &p, 0);
+	if (p[0] && p[1]) {
+		fprintf(stderr, "Bad base: %s\n", argv[2]);
+		exit(1);
+	}
+
+	printf("%d percent of %u is %u.\n", percent, base,
+	       e2p_percent(percent, base));
+
+	exit(0);
+}
+#endif
diff -r 14e45223b10b -r 4a2b0d6c55fc misc/ChangeLog
--- a/misc/ChangeLog	Wed Aug 30 02:16:55 2006 -0400
+++ b/misc/ChangeLog	Wed Aug 30 03:08:13 2006 -0400
@@ -1,4 +1,8 @@ 2006-08-30  Theodore Tso  <[email protected]
 2006-08-30  Theodore Tso  <[email protected]>
+
+	* tune2fs.c (main), mke2fs.c (PRS): Use e2p_percent to properly
+		calculate the number of reserved blocks without worrying
+		about overflow.
 
 	* Makefile.in (resize2fs): Remove unused (and bogus) resize2fs
 		rule, which shouldn't be in misc/Makefile.in
diff -r 14e45223b10b -r 4a2b0d6c55fc misc/mke2fs.c
--- a/misc/mke2fs.c	Wed Aug 30 02:16:55 2006 -0400
+++ b/misc/mke2fs.c	Wed Aug 30 03:08:13 2006 -0400
@@ -1447,8 +1447,8 @@ static void PRS(int argc, char *argv[])
 	/*
 	 * Calculate number of blocks to reserve
 	 */
-	fs_param.s_r_blocks_count = (fs_param.s_blocks_count * reserved_ratio)
-		/ 100;
+	fs_param.s_r_blocks_count = e2p_percent(reserved_ratio, 
+						fs_param.s_blocks_count);
 }
 
 int main (int argc, char *argv[])
diff -r 14e45223b10b -r 4a2b0d6c55fc misc/tune2fs.c
--- a/misc/tune2fs.c	Wed Aug 30 02:16:55 2006 -0400
+++ b/misc/tune2fs.c	Wed Aug 30 03:08:13 2006 -0400
@@ -823,7 +823,8 @@ int main (int argc, char ** argv)
 		printf (_("Setting interval between checks to %lu seconds\n"), interval);
 	}
 	if (m_flag) {
-		sb->s_r_blocks_count = sb->s_blocks_count * reserved_ratio /100;
+		sb->s_r_blocks_count = e2p_percent(reserved_ratio,
+						   sb->s_blocks_count);
 		ext2fs_mark_super_dirty(fs);
 		printf (_("Setting reserved blocks percentage to %g%% (%u blocks)\n"),
 			reserved_ratio, sb->s_r_blocks_count);
diff -r 14e45223b10b -r 4a2b0d6c55fc resize/ChangeLog
--- a/resize/ChangeLog	Wed Aug 30 02:16:55 2006 -0400
+++ b/resize/ChangeLog	Wed Aug 30 03:08:13 2006 -0400
@@ -1,4 +1,8 @@ 2006-08-30  Theodore Tso  <[email protected]
 2006-08-30  Theodore Tso  <[email protected]>
+
+	* resize2fs.c (adjust_fs_info), online.c (online_resize_fs): Use
+		e2p_percent to properly calculate the number of reserved
+		blocks without worrying about overflow.
 
 	* resize2fs.c (ext2fs_calculate_summary_stats): Fix potential
 		overflow problems when the number of blocks is close to
diff -r 14e45223b10b -r 4a2b0d6c55fc resize/online.c
--- a/resize/online.c	Wed Aug 30 02:16:55 2006 -0400
+++ b/resize/online.c	Wed Aug 30 03:08:13 2006 -0400
@@ -107,7 +107,8 @@ errcode_t online_resize_fs(ext2_filsys f
 				sb->s_first_data_block - 
 				(i * sb->s_blocks_per_group);
 		}
-		input.reserved_blocks = input.blocks_count * r_frac / 100;
+		input.reserved_blocks = e2p_percent(r_frac, 
+						    input.blocks_count);
 
 #if 0
 		printf("new block bitmap is at 0x%04x\n", input.block_bitmap);
diff -r 14e45223b10b -r 4a2b0d6c55fc resize/resize2fs.c
--- a/resize/resize2fs.c	Wed Aug 30 02:16:55 2006 -0400
+++ b/resize/resize2fs.c	Wed Aug 30 03:08:13 2006 -0400
@@ -245,8 +245,8 @@ retry:
 	 */
 	blk = old_fs->super->s_r_blocks_count * 100 /
 		old_fs->super->s_blocks_count;
-	fs->super->s_r_blocks_count = ((fs->super->s_blocks_count * blk)
-				       / 100);
+	fs->super->s_r_blocks_count = e2p_percent(blk, 
+						  fs->super->s_blocks_count);
 
 	/*
 	 * Adjust the bitmaps for size

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642