[PATCH 1/2] btrfs-progs: utils: Introduce new pseudo random API

[PATCH 1/2] btrfs-progs: utils: Introduce new pseudo random API

[Qu Wenruo]

David has reported some quite chaos usage of pseudo random numbers.
Like using static srand seed, or even calling rand() without setting
seed correctly.

The new pseudo random API will initialize the random seed on its first
calling and use uniformly distributed pseudo random number generator as
backend.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 utils.c | 36 ++++++++++++++++++++++++++++++++++++
 utils.h | 36 ++++++++++++++++++++++++++++++++++++
 2 files changed, 72 insertions(+)

diff --git a/utils.c b/utils.c
index 7761165..c0e860a 100644
--- a/utils.c
+++ b/utils.c
@@ -54,9 +54,11 @@
 #define BLKDISCARD	_IO(0x12,119)
 #endif
 
+static int seed_initlized = 0;
 static int btrfs_scan_done = 0;
 
 static char argv0_buf[ARGV0_BUF_SIZE] = "btrfs";
+static unsigned short seeds[3];
 
 const char *get_argv0_buf(void)
 {
@@ -4051,3 +4053,37 @@ out:
 
 	return ret;
 }
+
+void rand_seed(u64 seed)
+{
+	int i;
+	/* only use the last 48 bits */
+	for (i = 0; i < 3; i++) {
+		seeds[i] = (unsigned short)(seed ^ (unsigned short)(-1));
+		seed >>= 16;
+	}
+	seed_initlized = 1;
+}
+
+u32 rand_u32(void)
+{
+	struct timeval tv;
+
+	if (seed_initlized)
+		return nrand48(seeds);
+
+	/*
+	 * It's possible to use /dev/random, but we don't need that true
+	 * random number nor want to wait for entropy,
+	 * since we're only using random API to do corruption to test.
+	 * Time and pid/ppid based seed would be good enough, and won't
+	 * cause sleep for entropy pool.
+	 */
+	gettimeofday(&tv, 0);
+	seeds[0] = getpid() ^ (tv.tv_sec & 0xFFFF);
+	seeds[1] = getppid() ^ (tv.tv_usec & 0xFFFF);
+	seeds[2] = (tv.tv_sec ^ tv.tv_usec) >> 16;
+	seed_initlized = 1;
+
+	return (u32)nrand48(seeds);
+}
diff --git a/utils.h b/utils.h
index ebe6d61..0977262 100644
--- a/utils.h
+++ b/utils.h
@@ -362,4 +362,40 @@ static inline int error_on(int condition, const char *fmt, ...)
 	return 1;
 }
 
+/* pseudo random number generator wrappers */
+u32 rand_u32(void);
+
+static inline int rand_int(void)
+{
+	return (int)(rand_u32());
+}
+
+static inline u64 rand_u64(void)
+{
+	u64 ret = 0;
+
+	ret += rand_u32();
+	ret <<= 32;
+	ret += rand_u32();
+	return ret;
+}
+
+static inline u16 rand_u16(void)
+{
+	return (u16)(rand_u32());
+}
+
+static inline u8 rand_u8(void)
+{
+	return (u8)(rand_u32());
+}
+
+/* Return random number in range [0, limit) */
+static inline unsigned int rand_range(unsigned int up)
+{
+	return (unsigned int)(rand_u32() % up);
+}
+
+/* Also allow setting seeds manually */
+void rand_seed(u64 seed);
 #endif
-- 
2.8.2

[PATCH 2/2] btrfs-progs: Use new random number API

[Qu Wenruo]

Replace old and not so informal srand()/rand() calls to new random
number API.

Including btrfs-corrupt-block(main user), btrfs-image and btrfs-crc.

Some tests like dir-test/random-test/quick-test is not modified.
As random-test itself can't even pass build.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-corrupt-block.c | 23 +++++++++++------------
 btrfs-crc.c           |  9 +++++----
 btrfs-image.c         |  4 ++--
 3 files changed, 18 insertions(+), 18 deletions(-)

diff --git a/btrfs-corrupt-block.c b/btrfs-corrupt-block.c
index d331f96..2cc9704 100644
--- a/btrfs-corrupt-block.c
+++ b/btrfs-corrupt-block.c
@@ -131,8 +131,8 @@ static void corrupt_keys(struct btrfs_trans_handle *trans,
 	if (nr == 0)
 		return;
 
-	slot = rand() % nr;
-	bad_slot = rand() % nr;
+	slot = rand_range(nr);
+	bad_slot = rand_range(nr);
 
 	if (bad_slot == slot)
 		return;
@@ -181,7 +181,7 @@ static int corrupt_extent(struct btrfs_trans_handle *trans,
 	struct btrfs_path *path;
 	int ret;
 	int slot;
-	int should_del = rand() % 3;
+	int should_del = rand_range(3);
 
 	path = btrfs_alloc_path();
 	if (!path)
@@ -257,7 +257,7 @@ static void btrfs_corrupt_extent_leaf(struct btrfs_trans_handle *trans,
 				      struct extent_buffer *eb)
 {
 	u32 nr = btrfs_header_nritems(eb);
-	u32 victim = rand() % nr;
+	u32 victim = rand_range(nr);
 	u64 objectid;
 	struct btrfs_key key;
 
@@ -281,7 +281,7 @@ static void btrfs_corrupt_extent_tree(struct btrfs_trans_handle *trans,
 	}
 
 	if (btrfs_header_level(eb) == 1 && eb != root->node) {
-		if (rand() % 5)
+		if (rand_range(5))
 			return;
 	}
 
@@ -390,7 +390,7 @@ static u64 generate_u64(u64 orig)
 {
 	u64 ret;
 	do {
-		ret = rand();
+		ret = rand_u64();
 	} while (ret == orig);
 	return ret;
 }
@@ -399,7 +399,7 @@ static u32 generate_u32(u32 orig)
 {
 	u32 ret;
 	do {
-		ret = rand();
+		ret = rand_u32();
 	} while (ret == orig);
 	return ret;
 }
@@ -408,7 +408,7 @@ static u8 generate_u8(u8 orig)
 {
 	u8 ret;
 	do {
-		ret = rand();
+		ret = rand_u8();
 	} while (ret == orig);
 	return ret;
 }
@@ -944,7 +944,7 @@ static int corrupt_chunk_tree(struct btrfs_trans_handle *trans,
 	while (!btrfs_previous_item(root, path, 0, BTRFS_DEV_ITEM_KEY)) {
 		slot = path->slots[0];
 		leaf = path->nodes[0];
-		del = rand() % 3;
+		del = rand_range(3);
 		/* Never delete the first item to keep the leaf structure */
 		if (path->slots[0] == 0)
 			del = 0;
@@ -971,7 +971,7 @@ static int corrupt_chunk_tree(struct btrfs_trans_handle *trans,
 	while (!btrfs_previous_item(root, path, 0, BTRFS_CHUNK_ITEM_KEY)) {
 		slot = path->slots[0];
 		leaf = path->nodes[0];
-		del = rand() % 3;
+		del = rand_range(3);
 		btrfs_item_key_to_cpu(leaf, &found_key, slot);
 		ret = corrupt_item_nocow(trans, root, path, del);
 		if (ret)
@@ -1040,7 +1040,6 @@ int main(int argc, char **argv)
 	char field[FIELD_BUF_LEN];
 
 	field[0] = '\0';
-	srand(128);
 	memset(&key, 0, sizeof(key));
 
 	while(1) {
@@ -1179,7 +1178,7 @@ int main(int argc, char **argv)
 
 		if (logical == (u64)-1)
 			print_usage(1);
-		del = rand() % 3;
+		del = rand_range(3);
 		path = btrfs_alloc_path();
 		if (!path) {
 			fprintf(stderr, "path allocation failed\n");
diff --git a/btrfs-crc.c b/btrfs-crc.c
index 723e0b7..b50b951 100644
--- a/btrfs-crc.c
+++ b/btrfs-crc.c
@@ -40,7 +40,7 @@ int main(int argc, char **argv)
 	char *str;
 	char *buf;
 	int length = 10;
-	int seed = getpid() ^ getppid();
+	u64 seed = 0;
 	int loop = 0;
 	int i;
 
@@ -54,7 +54,7 @@ int main(int argc, char **argv)
 			loop = 1;
 			break;
 		case 's':
-			seed = atol(optarg);
+			seed = atoll(optarg);
 			break;
 		case 'h':
 			usage();
@@ -77,11 +77,12 @@ int main(int argc, char **argv)
 	buf = malloc(length);
 	if (!buf)
 		return -ENOMEM;
-	srand(seed);
+	if (seed)
+		rand_seed(seed);
 
 	while (1) {
 		for (i = 0; i < length; i++)
-			buf[i] = rand() % 94 + 33;
+			buf[i] = rand_range(94) + 33;
 		if (crc32c(~1, buf, length) == checksum)
 			printf("%12lu - %.*s\n", checksum, length, buf);
 	}
diff --git a/btrfs-image.c b/btrfs-image.c
index 8a1b799..9488913 100644
--- a/btrfs-image.c
+++ b/btrfs-image.c
@@ -188,7 +188,7 @@ static char *generate_garbage(u32 name_len)
 		return NULL;
 
 	for (i = 0; i < name_len; i++) {
-		char c = rand() % 94 + 33;
+		char c = rand_range(94) + 33;
 
 		if (c == '/')
 			c++;
@@ -392,7 +392,7 @@ static char *find_collision(struct metadump_struct *md, char *name,
 			"generating normal garbage, it won't match indexes\n",
 			val->len, val->val);
 		for (i = 0; i < name_len; i++) {
-			char c = rand() % 94 + 33;
+			char c = rand_range(94) + 33;
 
 			if (c == '/')
 				c++;
-- 
2.8.2

Re: [PATCH 1/2] btrfs-progs: utils: Introduce new pseudo random API

[Noah Massey]

On Wed, May 25, 2016 at 12:14 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> wrote:
> David has reported some quite chaos usage of pseudo random numbers.
> Like using static srand seed, or even calling rand() without setting
> seed correctly.
>
> The new pseudo random API will initialize the random seed on its first
> calling and use uniformly distributed pseudo random number generator as
> backend.
>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>  utils.c | 36 ++++++++++++++++++++++++++++++++++++
>  utils.h | 36 ++++++++++++++++++++++++++++++++++++
>  2 files changed, 72 insertions(+)
>
> diff --git a/utils.c b/utils.c
> index 7761165..c0e860a 100644
> --- a/utils.c
> +++ b/utils.c
> @@ -54,9 +54,11 @@
>  #define BLKDISCARD     _IO(0x12,119)
>  #endif
>
> +static int seed_initlized = 0;
>  static int btrfs_scan_done = 0;
>
>  static char argv0_buf[ARGV0_BUF_SIZE] = "btrfs";
> +static unsigned short seeds[3];
>
>  const char *get_argv0_buf(void)
>  {
> @@ -4051,3 +4053,37 @@ out:
>
>         return ret;
>  }
> +
> +void rand_seed(u64 seed)
> +{
> +       int i;
> +       /* only use the last 48 bits */
> +       for (i = 0; i < 3; i++) {
> +               seeds[i] = (unsigned short)(seed ^ (unsigned short)(-1));
> +               seed >>= 16;
> +       }
> +       seed_initlized = 1;
> +}
> +
> +u32 rand_u32(void)
> +{
> +       struct timeval tv;
> +
> +       if (seed_initlized)
> +               return nrand48(seeds);
> +

Missing a (u32) cast.

> +       /*
> +        * It's possible to use /dev/random, but we don't need that true
> +        * random number nor want to wait for entropy,

Sounds like a good candidate for /dev/urandom, then?

> +        * since we're only using random API to do corruption to test.
> +        * Time and pid/ppid based seed would be good enough, and won't
> +        * cause sleep for entropy pool.
> +        */
> +       gettimeofday(&tv, 0);
> +       seeds[0] = getpid() ^ (tv.tv_sec & 0xFFFF);
> +       seeds[1] = getppid() ^ (tv.tv_usec & 0xFFFF);
> +       seeds[2] = (tv.tv_sec ^ tv.tv_usec) >> 16;
> +       seed_initlized = 1;
> +
> +       return (u32)nrand48(seeds);
> +}
> diff --git a/utils.h b/utils.h
> index ebe6d61..0977262 100644
> --- a/utils.h
> +++ b/utils.h
> @@ -362,4 +362,40 @@ static inline int error_on(int condition, const char *fmt, ...)
>         return 1;
>  }
>
> +/* pseudo random number generator wrappers */
> +u32 rand_u32(void);
> +
> +static inline int rand_int(void)
> +{
> +       return (int)(rand_u32());
> +}
> +
> +static inline u64 rand_u64(void)
> +{
> +       u64 ret = 0;
> +
> +       ret += rand_u32();
> +       ret <<= 32;
> +       ret += rand_u32();
> +       return ret;
> +}
> +
> +static inline u16 rand_u16(void)
> +{
> +       return (u16)(rand_u32());
> +}
> +
> +static inline u8 rand_u8(void)
> +{
> +       return (u8)(rand_u32());
> +}
> +
> +/* Return random number in range [0, limit) */
> +static inline unsigned int rand_range(unsigned int up)
> +{
> +       return (unsigned int)(rand_u32() % up);
> +}

Wouldn't distribution be more uniform if you took the full 48 bits
from nrand64(), and only downcast after the mod?

> +
> +/* Also allow setting seeds manually */
> +void rand_seed(u64 seed);
>  #endif
> --
> 2.8.2
>
>
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 1/2] btrfs-progs: utils: Introduce new pseudo random API

[Qu Wenruo]

Noah Massey wrote on 2016/05/25 12:15 -0400:
> On Wed, May 25, 2016 at 12:14 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> wrote:
>> David has reported some quite chaos usage of pseudo random numbers.
>> Like using static srand seed, or even calling rand() without setting
>> seed correctly.
>>
>> The new pseudo random API will initialize the random seed on its first
>> calling and use uniformly distributed pseudo random number generator as
>> backend.
>>
>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>> ---
>>  utils.c | 36 ++++++++++++++++++++++++++++++++++++
>>  utils.h | 36 ++++++++++++++++++++++++++++++++++++
>>  2 files changed, 72 insertions(+)
>>
>> diff --git a/utils.c b/utils.c
>> index 7761165..c0e860a 100644
>> --- a/utils.c
>> +++ b/utils.c
>> @@ -54,9 +54,11 @@
>>  #define BLKDISCARD     _IO(0x12,119)
>>  #endif
>>
>> +static int seed_initlized = 0;
>>  static int btrfs_scan_done = 0;
>>
>>  static char argv0_buf[ARGV0_BUF_SIZE] = "btrfs";
>> +static unsigned short seeds[3];
>>
>>  const char *get_argv0_buf(void)
>>  {
>> @@ -4051,3 +4053,37 @@ out:
>>
>>         return ret;
>>  }
>> +
>> +void rand_seed(u64 seed)
>> +{
>> +       int i;
>> +       /* only use the last 48 bits */
>> +       for (i = 0; i < 3; i++) {
>> +               seeds[i] = (unsigned short)(seed ^ (unsigned short)(-1));
>> +               seed >>= 16;
>> +       }
>> +       seed_initlized = 1;
>> +}
>> +
>> +u32 rand_u32(void)
>> +{
>> +       struct timeval tv;
>> +
>> +       if (seed_initlized)
>> +               return nrand48(seeds);
>> +
>
> Missing a (u32) cast.

Right, just forgot that.

>
>> +       /*
>> +        * It's possible to use /dev/random, but we don't need that true
>> +        * random number nor want to wait for entropy,
>
> Sounds like a good candidate for /dev/urandom, then?

Yes, urandom is much better for such non-cypto use case.

>
>> +        * since we're only using random API to do corruption to test.
>> +        * Time and pid/ppid based seed would be good enough, and won't
>> +        * cause sleep for entropy pool.
>> +        */
>> +       gettimeofday(&tv, 0);
>> +       seeds[0] = getpid() ^ (tv.tv_sec & 0xFFFF);
>> +       seeds[1] = getppid() ^ (tv.tv_usec & 0xFFFF);
>> +       seeds[2] = (tv.tv_sec ^ tv.tv_usec) >> 16;
>> +       seed_initlized = 1;
>> +
>> +       return (u32)nrand48(seeds);
>> +}
>> diff --git a/utils.h b/utils.h
>> index ebe6d61..0977262 100644
>> --- a/utils.h
>> +++ b/utils.h
>> @@ -362,4 +362,40 @@ static inline int error_on(int condition, const char *fmt, ...)
>>         return 1;
>>  }
>>
>> +/* pseudo random number generator wrappers */
>> +u32 rand_u32(void);
>> +
>> +static inline int rand_int(void)
>> +{
>> +       return (int)(rand_u32());
>> +}
>> +
>> +static inline u64 rand_u64(void)
>> +{
>> +       u64 ret = 0;
>> +
>> +       ret += rand_u32();
>> +       ret <<= 32;
>> +       ret += rand_u32();
>> +       return ret;
>> +}
>> +
>> +static inline u16 rand_u16(void)
>> +{
>> +       return (u16)(rand_u32());
>> +}
>> +
>> +static inline u8 rand_u8(void)
>> +{
>> +       return (u8)(rand_u32());
>> +}
>> +
>> +/* Return random number in range [0, limit) */
>> +static inline unsigned int rand_range(unsigned int up)
>> +{
>> +       return (unsigned int)(rand_u32() % up);
>> +}
>
> Wouldn't distribution be more uniform if you took the full 48 bits
> from nrand64(), and only downcast after the mod?

Makes sense.

Will update the patchset soon.

Thanks,
Qu

>
>> +
>> +/* Also allow setting seeds manually */
>> +void rand_seed(u64 seed);
>>  #endif
>> --
>> 2.8.2
>>
>>
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>

Re: [PATCH 1/2] btrfs-progs: utils: Introduce new pseudo random API

[Goffredo Baroncelli]

On 2016-05-25 06:14, Qu Wenruo wrote:
> +void rand_seed(u64 seed)
> +{
> +	int i;
> +	/* only use the last 48 bits */
> +	for (i = 0; i < 3; i++) {
> +		seeds[i] = (unsigned short)(seed ^ (unsigned short)(-1));
> +		seed >>= 16;
> +	}
> +	seed_initlized = 1;
> +}
> +
> +u32 rand_u32(void)
> +{
> +	struct timeval tv;
> +
> +	if (seed_initlized)
> +		return nrand48(seeds);
> +
> +	/*
> +	 * It's possible to use /dev/random, but we don't need that true
> +	 * random number nor want to wait for entropy,
> +	 * since we're only using random API to do corruption to test.
> +	 * Time and pid/ppid based seed would be good enough, and won't
> +	 * cause sleep for entropy pool.
> +	 */
> +	gettimeofday(&tv, 0);
> +	seeds[0] = getpid() ^ (tv.tv_sec & 0xFFFF);
> +	seeds[1] = getppid() ^ (tv.tv_usec & 0xFFFF);
> +	seeds[2] = (tv.tv_sec ^ tv.tv_usec) >> 16;
> +	seed_initlized = 1;
> +
> +	return (u32)nrand48(seeds);
> +}


Just for my curiosity, which is the advantage of rand48() respect to rand() if we utilize only the lower 32 bit ? It wouldn't be more simple to use:

#define rand_seed(x) srand((int)(x))

/*
 *  NOTE: not for cryptographic use 
 */
u32 rand_u32(void)
{
	static __thread int initialized = 0;

	if (!initialized) {
		struct timeval tv;
		gettimeofday(&tv, 0);
		rand_seed(tv.tv_usec | (tv.tv_sec ^ getpid() ^ getppid()) << 16);
		initialized = 1;
	}
	return (u32)rand();
}

this in order to avoid the mess of the 48 bit ?

BR
G.Baroncelli

-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5