Revert "Revert "math64: New div64_u64_rem helper""
Subsystems (4)
PATCH 1/2 Revert "Revert "math64: New div64_u64_rem helper""
This reverts commit f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_rem was removed because there were no other users.
But Device Mapper's I/O statistics support has a need for div64_u64_rem; reintroduce this helper.
--- include/linux/math64.h | 19 ++++++++++++++++++- lib/div64.c | 19 +++++++++++++------ 2 files changed, 31 insertions(+), 7 deletions(-)
include/linux/math64.h +18 -1
@@ -30,6 +30,15 @@ static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) }/** +* div64_u64_rem - unsigned 64bit divide with 64bit divisor +*/ +static inline u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder) +{ + *remainder = dividend % divisor; +return dividend / divisor; +} + +/** * div64_u64 - unsigned 64bit divide with 64bit divisor */ static inline u64 div64_u64 (u64 dividend,u64 divisor)
@@ -61,8 +70,16 @@ static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)extern s64 div_s64_rem (s64 dividend,s32 divisor,s32 *remainder);#endif +#ifndef div64_u64_rem +extern u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder); +#endif +#ifndef div64_u64 -extern u64 div64_u64 (u64 dividend,u64 divisor); +static inline u64 div64_u64 (u64 dividend,u64 divisor) +{ +u64 remainder; +return div64_u64_rem (dividend, divisor, &remainder); +}#endif #ifndef div64_s64
lib/div64.c +13 -6
@@ -79,9 +79,10 @@ EXPORT_SYMBOL(div_s64_rem);#endif /** -* div64_u64 - unsigned 64bit divide with 64bit divisor +* div64_u64_rem - unsigned 64bit divide with 64bit divisor and 64bit remainder * @dividend: 64bit dividend * @divisor: 64bit divisor +* @remainder: 64bit remainder * * This implementation is a modified version of the algorithm proposed * by the book 'Hacker's Delight'. The original source and full proof
@@ -89,27 +90,33 @@ EXPORT_SYMBOL(div_s64_rem);* * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c.txt' */ -#ifndef div64_u64 -u64 div64_u64 (u64 dividend,u64 divisor) +#ifndef div64_u64_rem +u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder) {u32 high = divisor >>32 ;u64 quot;if (high ==0 ) { - quot =div_u64 (dividend, divisor); +u32 rem32; + quot =div_u64_rem (dividend, divisor, &rem32); + *remainder = rem32; }else {int n =1 +fls (high); quot =div_u64 (dividend >> n, divisor >> n);if (quot !=0 ) quot--; -if ((dividend - quot * divisor) >= divisor) + + *remainder = dividend - quot * divisor; +if (*remainder >= divisor) { quot++; + *remainder -= divisor; + } }return quot; } -EXPORT_SYMBOL (div64_u64); +EXPORT_SYMBOL (div64_u64_rem);#endif /**
Signature · 1 line
1.7.1
PATCH v3 2/2 dm: add statistics support
From: Mikulas Patocka <[email protected]>
Support the collection of I/O statistics on user-defined regions of a DM device. Only bio-based DM devices are currently supported.
Each user-defined region specifies a starting sector, ending sector and step. Individual statistics will be collected for each step-sized area between the starting and ending sector.
The I/O statistics counters for each step-sized area of a region are in the same format as /sys/block/*/stat or /proc/diskstats but extra counters (12 and 13) are provided: total time spent reading and writing in milliseconds. These counters may be accessed by sending the @stats_print message to the appropriate DM device via dmsetup.
DM statistics creation will allocate memory via kmalloc or fallback to using vmalloc space. At most, 1/4 of the overall system memory may be allocated by DM statistics. The admin can see how much memory is used by reading /sys/module/dm_mod/parameters/stats_current_allocated_bytes
See Documentation/device-mapper/statistics.txt for more details.
--- Documentation/device-mapper/statistics.txt | 132 ++++ drivers/md/Makefile | 2 +- drivers/md/dm-ioctl.c | 22 +- drivers/md/dm-stats.c | 950 ++++++++++++++++++++++++++++ drivers/md/dm-stats.h | 40 ++ drivers/md/dm.c | 63 ++- drivers/md/dm.h | 17 + include/linux/device-mapper.h | 13 + 8 files changed, 1228 insertions(+), 11 deletions(-)
Documentation/device-mapper/statistics.txt new file +132 -0
@@ -0,0 +1,132 @@ +DM statistics +============= + +Device Mapper supports the collection of I/O statistics on user-defined +regions of a DM device. Only bio-based DM devices are currently +supported. + +Each user-defined region specifies a starting sector, ending sector +and step. Individual statistics will be collected for each step-sized +area between the starting and ending sector. + +The I/O statistics counters for each step-sized area of a region are +in the same format as /sys/block/*/stat or /proc/diskstats but extra +counters (12 and 13) are provided: total time spent reading and +writing in milliseconds. These counters may be accessed by sending the +@stats_print message to the appropriate DM device via dmsetup. + +Each region has a corresponding unique identifier that is assigned when +the region is created. The region id must be supplied when querying +statistics about the region, deleting the region, etc. Unique region +ids enable multiple userspace programs to request and process statistics +for the same DM device without stepping over each other's data. + +DM statistics creation will allocate memory via kmalloc or fallback to +using vmalloc space. At most, 1/4 of the overall system memory may be +allocated by DM statistics. The admin can see how much memory is used +by reading /sys/module/dm_mod/parameters/stats_current_allocated_bytes + +Messages +======== + + @stats_create <range> <step> [<program id> [<auxiliary data>]] + + Create a new region and return the region id. + <range> + "-" - whole device + "<start>-<end>" - a specified range in 512-byte sectors + <step> + "<number>" - the number of sectors in each area + "/<number>" - the range is subdivided into the specified + number of areas + <program id> + An optional parameter. The string that identifies a program + that created this range. The kernel returns this string back + in the output of @stats_list message, but it doesn't use this + value for anything. + <auxiliary data> + An optional parameter. The string that identifies data which + is useful to the client program that created the range. The + kernel returns this string back in the output of @stats_list + message, but it doesn't use this value for anything. + + @stats_delete <region id> + + Delete the region with the specified id. + <region id> + region id returned from @stats_create + + @stats_clear <region id> + + Clear all the counters except the in-flight i/o counters. + <region id> + region id returned from @stats_create + + @stats_list [<program id>] + + List all regions registered with @stats_create. + <program id> + An optional parameter specifying the program that queries the + parameters. If this parameter is specified, only regions + belonging to this program are returned. If it is not + specified, all regions are returned. + Output format: + <id>: <start>-<end> <step size> <program id> <auxiliary data> + + @stats_print <region id> [<starting_line> <number_of_lines>] + + Print counters for each step-sized area of a region. + <region id> + region id returned from @stats_create + <starting_line> + The index of the starting line in the output. If omitted, all + lines are returned. + <number_of_lines> + The number of lines in the output. If omitted, all lines are + returned. + Output format for each step-sized area of a region: + <starting sector>-<ending sector> counters + The first 11 counters have the same meaning as + /sys/block/*/stat or /proc/diskstats. + Additional counters: + 12. the total time spent reading in milliseconds + 13. the total time spent writing in milliseconds + + @stats_print_clear <region id> [<starting_line> <number_of_lines>] + + Atomically print and then clear all the counters except the + in-flight i/o counters. Useful when client consuming the + statistics does not want to lose any statistics (those updated + between printing and clearing). + <region id> + region id returned from @stats_create + <starting_line> + The index of the starting line in the output. If omitted, all + lines are returned/cleared. + <number_of_lines> + The number of lines in the output. If omitted, all lines are + returned/cleared. + + @stats_set_aux <region id> <auxiliary data> + + Set the auxiliary data for the region with the specified id. + <region id> + region id returned from @stats_create + <auxiliary data> + The string that identifies data which is useful to the client + program that created the range. The kernel returns this + string back in the output of @stats_list message, but it + doesn't use this value for anything. + +Examples +======== + +Subdivide the DM device 'vol' into 100 pieces and start collecting +statistics on them: +dmsetup message vol 0 @stats_create - /100 + +Print the statistics: +dmsetup message vol 0 @stats_print 0 + +Delete the statistics: +dmsetup message vol 0 @stats_delete 0
drivers/md/Makefile +1 -1
@@ -3,7 +3,7 @@ # dm-mod-y += dm.o dm-table.o dm-target.o dm-linear.o dm-stripe.o \ - dm-ioctl.o dm-io.o dm-kcopyd.o dm-sysfs.o + dm-ioctl.o dm-io.o dm-kcopyd.o dm-sysfs.o dm-stats.o dm-multipath-y += dm-path-selector.o dm-mpath.o dm-snapshot-y += dm-snap.o dm-exception-store.o dm-snap-transient.o \ dm-snap-persistent.o
drivers/md/dm-ioctl.c +14 -8
@@ -1455,20 +1455,26 @@ static int table_status(struct dm_ioctl *param, size_t param_size)return 0 ; } -static bool buffer_test_overflow (char *result,unsigned maxlen) -{ -return !maxlen ||strlen (result) +1 >= maxlen; -} -/* -* Process device-mapper dependent messages. +* Process device-mapper dependent messages. Messages prefixed with '@' +* are processed by the DM core. All others are delivered to the target. * Returns a number <= 1 if message was processed by device mapper. * Returns 2 if message should be delivered to the target. */ static int message_for_md (struct mapped_device *md,unsigned argc,char **argv,char *result,unsigned maxlen) { -return 2 ; +int r; + +if (**argv !='@' ) +return 2 ;/* no '@' prefix, deliver to target */ + + r =dm_stats_message (md, argc, argv, result, maxlen); +if (r <2 ) +return r; + +DMERR ("Unsupported message sent to DM core: %s" , argv[0 ]); +return -EINVAL ; }/*
@@ -1542,7 +1548,7 @@ static int target_message(struct dm_ioctl *param, size_t param_size)if (r ==1 ) { param->flags |=DM_DATA_OUT_FLAG ; -if (buffer_test_overflow (result, maxlen)) +if (dm_message_test_buffer_overflow (result, maxlen)) param->flags |=DM_BUFFER_FULL_FLAG ;else param->data_size = param->data_start +strlen (result) +1 ;
drivers/md/dm-stats.c new file +950 -0
950 lines not on this page · raw message
drivers/md/dm-stats.h new file +40 -0
@@ -0,0 +1,40 @@ +#ifndef DM_STATS_H +#define DM_STATS_H + +#include <linux/types.h> +#include <linux/mutex.h> +#include <linux/list.h> + +int dm_statistics_init (void ); +void dm_statistics_exit (void ); + +struct dm_stats { +struct mutex mutex; +struct list_head list;/* list of struct dm_stat */ +struct dm_stats_last_position __percpu *last; +sector_t last_sector; +unsigned last_rw; +}; + +struct dm_stats_aux { +bool merged; +}; + +void dm_stats_init (struct dm_stats *st); +void dm_stats_cleanup (struct dm_stats *st); + +struct mapped_device ; + +int dm_stats_message (struct mapped_device *md,unsigned argc,char **argv, +char *result,unsigned maxlen); + +void dm_stats_account_io (struct dm_stats *stats,unsigned long bi_rw, +sector_t bi_sector,unsigned bi_sectors,bool end, +unsigned long duration,struct dm_stats_aux *aux); + +static inline bool dm_stats_used (struct dm_stats *st) +{ +return !list_empty (&st->list); +} + +#endif
drivers/md/dm.c +61 -2
136 lines not on this page · raw message
drivers/md/dm.h +17 -0
@@ -16,6 +16,8 @@#include <linux/blkdev.h> #include <linux/hdreg.h> +#include "dm-stats.h" +/* * Suspend feature flags */
@@ -146,10 +148,16 @@ void dm_destroy(struct mapped_device *md);void dm_destroy_immediate (struct mapped_device *md);int dm_open_count (struct mapped_device *md);int dm_lock_for_deletion (struct mapped_device *md); +int dm_request_based (struct mapped_device *md); +sector_t dm_get_size (struct mapped_device *md); +struct dm_stats *dm_get_stats (struct mapped_device *md);int dm_kobject_uevent (struct mapped_device *md,enum kobject_action action,unsigned cookie); +void dm_internal_suspend (struct mapped_device *md); +void dm_internal_resume (struct mapped_device *md); +int dm_io_init (void );void dm_io_exit (void );
@@ -162,4 +170,13 @@ void dm_kcopyd_exit(void);struct dm_md_mempools *dm_alloc_md_mempools (unsigned type,unsigned integrity,unsigned per_bio_data_size);void dm_free_md_mempools (struct dm_md_mempools *pools); + +/* +* Helpers that are used by DM core +*/ +static inline bool dm_message_test_buffer_overflow (char *result,unsigned maxlen) +{ +return !maxlen ||strlen (result) +1 >= maxlen; +} +#endif
include/linux/device-mapper.h +13 -0
@@ -550,6 +550,19 @@ extern struct ratelimit_state dm_ratelimit_state;#define DM_MAPIO_REMAPPED 1#define DM_MAPIO_REQUEUE DM_ENDIO_REQUEUE +#if BITS_PER_LONG ==32 && defined(CONFIG_LBDAF ) +#include <linux/math64.h> +#define dm_sector_div64 (x, y)( \ +{ \ + u64 _res; \ + (x) = div64_u64_rem(x, y, &_res); \ + _res; \ +} \ +) +#else +#define dm_sector_div64 (x, y) sector_div(x, y) +#endif +/* * Ceiling(n / sz) */
Quoted 6 lines · Mike Snitzer
This reverts commit
f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_remwas removed because there were no other users.But Device Mapper's I/O statistics support has a need for
div64_u64_rem; reintroduce this helper.
This slows down div64_u64 operation, especially on 32-bit systems.
Since dm statistic code is possibly not performance critical perhaps you could use something like below instead to calculate remainder:
res = div64_u64(a, b);
rem = a - b*res;
Stanislaw
Quoted 11 lines · Stanislaw Gruszka
Quoted 6 lines · Mike Snitzer
This reverts commit
f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_remwas removed because there were no other users.But Device Mapper's I/O statistics support has a need for
div64_u64_rem; reintroduce this helper.This slows down
div64_u64operation, especially on 32-bit systems.
Quoted 6 lines
Since dm statistic code is possibly not performance critical perhaps you could use something like below instead to calculate remainder:
res =
div64_u64(a, b);
rem = a - b*res;
Or introduce a separately named helper without touching the existing methods.
Thanks,
Ingo
Quoted 18 lines · Ingo Molnar
Quoted 15 lines · Stanislaw Gruszka
Quoted 6 lines · Mike Snitzer
This reverts commit
f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_remwas removed because there were no other users.But Device Mapper's I/O statistics support has a need for
div64_u64_rem; reintroduce this helper.This slows down
div64_u64operation, especially on 32-bit systems.Since dm statistic code is possibly not performance critical perhaps you could use something like below instead to calculate remainder:
Quoted 5 lines
Quoted 2 lines
res =
div64_u64(a, b);
rem = a - b*res;Or introduce a separately named helper without touching the existing methods.
Thanks for the feedback.
I've pushed "math64: New separate div64_u64_rem helper" to the DM tree's 'for-next' branch:
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/commit/?h=for-next&id=20e8125736d0e96b64c9b6127241d2a13529180a
Are you OK with me carrying this patch in the DM tree for 3.12 inclusion?
Mike
Quoted 27 lines · Mike Snitzer
Quoted 18 lines · Ingo Molnar
Quoted 15 lines · Stanislaw Gruszka
Quoted 6 lines · Mike Snitzer
This reverts commit
f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_remwas removed because there were no other users.But Device Mapper's I/O statistics support has a need for
div64_u64_rem; reintroduce this helper.This slows down
div64_u64operation, especially on 32-bit systems.Since dm statistic code is possibly not performance critical perhaps you could use something like below instead to calculate remainder:
Quoted 5 lines
Quoted 2 lines
res =
div64_u64(a, b);
rem = a - b*res;Or introduce a separately named helper without touching the existing methods.
Quoted 8 lines
Thanks for the feedback.
I've pushed "math64: New separate
div64_u64_remhelper" to the DM tree's 'for-next' branch:
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/commit/?h=for-next&id=20e8125736d0e96b64c9b6127241d2a13529180aAre you OK with me carrying this patch in the DM tree for 3.12 inclusion?
Would be nice to include the actual latest patch here on lkml.
Thanks,
Ingo
PATCH 1/1 math64: New separate div64_u64_rem helper
Commit f792685006274a850e6cc0ea9ade275ccdfc90bc ("math64: New div64_u64_rem helper") implemented div64_u64 in terms of div64_u64_rem. But div64_u64_rem was removed because it slowed down div64_u64 (and there were no other users of div64_u64_rem).
Device Mapper's I/O statistics support has a need for div64_u64_rem; reintroduce this helper as a separate method that doesn't slow down div64_u64, especially on 32-bit systems.
--- include/linux/math64.h | 13 +++++++++++++ lib/div64.c | 40 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 53 insertions(+), 0 deletions(-)
include/linux/math64.h +13 -0
@@ -31,6 +31,15 @@ static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) }/** +* div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder +*/ +static inline u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder) +{ + *remainder = dividend % divisor; +return dividend / divisor; +} + +/** * div64_u64 - unsigned 64bit divide with 64bit divisor */ static inline u64 div64_u64 (u64 dividend,u64 divisor)
@@ -63,6 +72,10 @@ static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)extern s64 div_s64_rem (s64 dividend,s32 divisor,s32 *remainder);#endif +#ifndef div64_u64_rem +extern u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder); +#endif +#ifndef div64_u64extern u64 div64_u64 (u64 dividend,u64 divisor);#endif
lib/div64.c +40 -0
@@ -79,6 +79,46 @@ EXPORT_SYMBOL(div_s64_rem);#endif /** +* div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder +* @dividend: 64bit dividend +* @divisor: 64bit divisor +* @remainder: 64bit remainder +* +* This implementation is a comparable to algorithm used by div64_u64. +* But this operation, which includes math for calculating the remainder, +* is kept distinct to avoid slowing down the div64_u64 operation on 32bit +* systems. +*/ +#ifndef div64_u64_rem +u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder) +{ +u32 high = divisor >>32 ; +u64 quot; + +if (high ==0 ) { +u32 rem32; + quot =div_u64_rem (dividend, divisor, &rem32); + *remainder = rem32; + }else { +int n =1 +fls (high); + quot =div_u64 (dividend >> n, divisor >> n); + +if (quot !=0 ) + quot--; + + *remainder = dividend - quot * divisor; +if (*remainder >= divisor) { + quot++; + *remainder -= divisor; + } + } + +return quot; +} +EXPORT_SYMBOL (div64_u64_rem); +#endif + +/** * div64_u64 - unsigned 64bit divide with 64bit divisor * @dividend: 64bit dividend * @divisor: 64bit divisor
Signature · 1 line
1.7.4.4
Hi,
Quoted 3 lines · Mike Snitzer
This reverts commit
f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_remwas removed because there were no other users.
In the light of this discussion https://lkml.org/lkml/2013/8/30/417 we will have more users of div64_u64_rem
For example code from ext4_mb_find_by_goal() function uses function do_div() with divisor sbi->s_stripe that has "unsigned long" type. do_div() silently truncates the type to 32bits and do_div() returns incorrect result (or crash if lower 32bits are zero). It should be either replaced with div64_u64_rem() posted here or with just "a % b".
Quoted 7 lines · Anatol Pomozov
Hi,
Quoted 3 lines · Mike Snitzer
This reverts commit
f3002134158092178be81339ec5a22ff80e6c308.
div64_u64_remwas removed because there were no other users.
Quoted 8 lines
In the light of this discussion https://lkml.org/lkml/2013/8/30/417 we will have more users of
div64_u64_remFor example code from
ext4_mb_find_by_goal()function uses functiondo_div()with divisorsbi->s_stripethat has "unsigned long" type.do_div()silently truncates the type to 32bits anddo_div()returns incorrect result (or crash if lower 32bits are zero). It should be either replaced withdiv64_u64_rem()posted here or with just "a % b".
Hi,
As Ingo suggested, I went ahead and introduced a completely new div64_u64_rem, see: https://lkml.org/lkml/2013/8/21/452
I've staged this change in linux-next for inclusion in the current 3.12 merge (via the device-mapper tree), see:
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/commit/?h=for-next&id=eb18cba78c2b9250663021e17e1e9cc34630e92a
So once this is in ext4 can make use of div64_u64_rem().
Mike