[PATCH 01/18] flag parameters: helper function

[PATCH 01/18] flag parameters: helper function

[Ulrich Drepper]

In the following patches we have to map one set of flags to another one
in numerous locations.  This patch provides a generic implementation for
this.  It is basically the code Davide Libenzi suggested on 4/27/08.

I haven't checked whether this functionality can be applied to any existing
code.


 include/linux/flagsremap.h |   15 +++++++++++++++
 lib/Makefile               |    2 +-
 lib/flagsremap.c           |   17 +++++++++++++++++
 3 files changed, 33 insertions(+), 1 deletion(-)


Signed-off-by: Ulrich Drepper <drepper@redhat.com>

diff --git a/include/linux/flagsremap.h b/include/linux/flagsremap.h
new file mode 100644
index 0000000..6ea0ee3
--- /dev/null
+++ b/include/linux/flagsremap.h
@@ -0,0 +1,15 @@
+/*
+ * Generic flag remapping functionality.
+ */
+#ifndef _LINUX_FLAPREMAP_H
+#define _LINUX_FLAGREMAP_H
+
+struct flags_rmap {
+	int f;
+	int of;
+};
+
+extern int flags_remap(const struct flags_rmap *m, int n,
+		       int f, int *rf);
+
+#endif /* _LINUX_FLAGREMAP_H */
diff --git a/lib/Makefile b/lib/Makefile
index 74b0cfb..ab861ad 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -6,7 +6,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o dump_stack.o \
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
-	 proportions.o prio_heap.o ratelimit.o
+	 proportions.o prio_heap.o ratelimit.o flagsremap.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/flagsremap.c b/lib/flagsremap.c
new file mode 100644
index 0000000..7dbe8f5
--- /dev/null
+++ b/lib/flagsremap.c
@@ -0,0 +1,17 @@
+/*
+ * Implement generic flag remapping.
+ */
+#include <linux/flagsremap.h>
+
+
+int flags_remap(const struct flags_rmap *m, int n,
+		int f, int *rf)
+{
+	int i;
+	for (i = 0, *rf = 0; f && i < n; i++, m++)
+		if (f & m->f) {
+			*rf |= m->of;
+			f &= ~m->f;
+		}
+	return f;
+}

Re: [PATCH 01/18] flag parameters: helper function

[Davide Libenzi]

On Sun, 4 May 2008, Ulrich Drepper wrote:

> In the following patches we have to map one set of flags to another one
> in numerous locations.  This patch provides a generic implementation for
> this.  It is basically the code Davide Libenzi suggested on 4/27/08.
> 
> I haven't checked whether this functionality can be applied to any existing
> code.
> 
> 
>  include/linux/flagsremap.h |   15 +++++++++++++++
>  lib/Makefile               |    2 +-
>  lib/flagsremap.c           |   17 +++++++++++++++++
>  3 files changed, 33 insertions(+), 1 deletion(-)
> 
> 
> Signed-off-by: Ulrich Drepper <drepper@redhat.com>

I dunno if this deserves separate c/h files. Otherwise ...

Acked-by: Davide Libenzi <davidel@xmailserver.org>



- Davide

Re: [PATCH 01/18] flag parameters: helper function

[Ulrich Drepper]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Davide Libenzi wrote:
> I dunno if this deserves separate c/h files. Otherwise ...

I used separate files because all of the users are in optional code.  I
would have had to stuff the code in a completely unrelated file which I
think isn't clean.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkgelO4ACgkQ2ijCOnn/RHSVQgCffwvlbMeZTI5N19+J13VS8+ng
8/0AoI8wwTtrAwbFIbuu9e4RrvEIzWGC
=2gim
-----END PGP SIGNATURE-----

Re: [PATCH 01/18] flag parameters: helper function

[Andrew Morton]

On Sun, 4 May 2008 23:42:46 -0400 Ulrich Drepper <drepper@redhat.com> wrote:

> In the following patches we have to map one set of flags to another one
> in numerous locations.  This patch provides a generic implementation for
> this.  It is basically the code Davide Libenzi suggested on 4/27/08.
> 
> I haven't checked whether this functionality can be applied to any existing
> code.
> 
> 
>  include/linux/flagsremap.h |   15 +++++++++++++++
>  lib/Makefile               |    2 +-
>  lib/flagsremap.c           |   17 +++++++++++++++++
>  3 files changed, 33 insertions(+), 1 deletion(-)
> 
> 
> Signed-off-by: Ulrich Drepper <drepper@redhat.com>
> 
> diff --git a/include/linux/flagsremap.h b/include/linux/flagsremap.h
> new file mode 100644
> index 0000000..6ea0ee3
> --- /dev/null
> +++ b/include/linux/flagsremap.h
> @@ -0,0 +1,15 @@
> +/*
> + * Generic flag remapping functionality.
> + */
> +#ifndef _LINUX_FLAPREMAP_H
> +#define _LINUX_FLAGREMAP_H
> +
> +struct flags_rmap {
> +	int f;
> +	int of;
> +};

In kernel world, the abbreviation "rmap" means "reverse mapping".  I think
"flags_remapping" would be a better identifier here.

> +extern int flags_remap(const struct flags_rmap *m, int n,
> +		       int f, int *rf);
> +
> +#endif /* _LINUX_FLAGREMAP_H */
> diff --git a/lib/Makefile b/lib/Makefile
> index 74b0cfb..ab861ad 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -6,7 +6,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
>  	 rbtree.o radix-tree.o dump_stack.o \
>  	 idr.o int_sqrt.o extable.o prio_tree.o \
>  	 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
> -	 proportions.o prio_heap.o ratelimit.o
> +	 proportions.o prio_heap.o ratelimit.o flagsremap.o
>  
>  lib-$(CONFIG_MMU) += ioremap.o
>  lib-$(CONFIG_SMP) += cpumask.o
> diff --git a/lib/flagsremap.c b/lib/flagsremap.c
> new file mode 100644
> index 0000000..7dbe8f5
> --- /dev/null
> +++ b/lib/flagsremap.c
> @@ -0,0 +1,17 @@
> +/*
> + * Implement generic flag remapping.
> + */
> +#include <linux/flagsremap.h>
> +
> +
> +int flags_remap(const struct flags_rmap *m, int n,
> +		int f, int *rf)
> +{
> +	int i;
> +	for (i = 0, *rf = 0; f && i < n; i++, m++)
> +		if (f & m->f) {
> +			*rf |= m->of;
> +			f &= ~m->f;
> +		}
> +	return f;
> +}

hm, that looks expensive.  The compiler will need to generate a deref of m
and rf multiple times around the loop.  Copying them into locals does
improve that a lot.

I'm only on [1/18] so I don't know how often this code gets executed.  If
it's "on each open" then ouch, perhaps it might even be worth investigating a
table-based implementation.

Also: sorry, but ugh-at-the-naming.  We don't *gain* anything from having
idenitifers called f, of, m, n and rf.  And we lose quite a lot in
readability and understandability.  It would be much nicer to invest a
little bit more typing-time here, IMO.

Re: [PATCH 01/18] flag parameters: helper function

[Davide Libenzi]

On Mon, 5 May 2008, Andrew Morton wrote:

> > +int flags_remap(const struct flags_rmap *m, int n,
> > +		int f, int *rf)
> > +{
> > +	int i;
> > +	for (i = 0, *rf = 0; f && i < n; i++, m++)
> > +		if (f & m->f) {
> > +			*rf |= m->of;
> > +			f &= ~m->f;
> > +		}
> > +	return f;
> > +}
> 
> hm, that looks expensive.  The compiler will need to generate a deref of m
> and rf multiple times around the loop.  Copying them into locals does
> improve that a lot.

That's not a fast path. The extra cycles in the ldr/str get lost in the 
overall syscall cost. But I guess Uli (or myself afterward) can change it 
if you fill picky about it ;)



> I'm only on [1/18] so I don't know how often this code gets executed.  If
> it's "on each open" then ouch, perhaps it might even be worth investigating a
> table-based implementation.
> 
> Also: sorry, but ugh-at-the-naming.  We don't *gain* anything from having
> idenitifers called f, of, m, n and rf.  And we lose quite a lot in
> readability and understandability.  It would be much nicer to invest a
> little bit more typing-time here, IMO.

Why? Don't you like nibble-sized variable names? :)
Uli took my email-code as is, so either he changes it, or I'll post 
patches over it later.




- Davide

Re: [PATCH 01/18] flag parameters: helper function

[Ulrich Drepper]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Andrew Morton wrote:
> hm, that looks expensive.  The compiler will need to generate a deref of m
> and rf multiple times around the loop.  Copying them into locals does
> improve that a lot.

There really is no problem.  The value is in L1d when it is reused.
This is the generated code (%rdi is m):

   f:   85 17                   test   %edx,(%rdi)
  11:   74 0b                   je     1e <flags_remap+0x1e>
  13:   8b 47 04                mov    0x4(%rdi),%eax
  16:   09 01                   or     %eax,(%rcx)
  18:   8b 07                   mov    (%rdi),%eax
  1a:   f7 d0                   not    %eax
  1c:   21 c2                   and    %eax,%edx

At address 18 the load will be satisfied from L1d.  If you would want to
cache the value at address f you'd have to create one more instruction.

This really is the best code sequence.  The compiler could have chosen
to move the value into a register because the array is const.  But it
didn't.


> Also: sorry, but ugh-at-the-naming.  We don't *gain* anything from having
> idenitifers called f, of, m, n and rf.  And we lose quite a lot in
> readability and understandability.  It would be much nicer to invest a
> little bit more typing-time here, IMO.

That's Davide's code and I didn't change it because it doesn't really
matter.  This is a trivial function which doesn't need more than 10
seconds to be understood.  If you insist I'll rename the variables and
elements but I consider this just busy work.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)

iD8DBQFIH8Tl2ijCOnn/RHQRAm+PAKDEArdgKWXLAMzzfYQ3Q8XzbJdWmgCfavq+
+THu/JEISm+IrX7oyhITYVU=
=F2Co
-----END PGP SIGNATURE-----

Re: [PATCH 01/18] flag parameters: helper function

[Andrew Morton]

On Mon, 05 May 2008 19:39:34 -0700 Ulrich Drepper <drepper@redhat.com> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Andrew Morton wrote:
> > hm, that looks expensive.  The compiler will need to generate a deref of m
> > and rf multiple times around the loop.  Copying them into locals does
> > improve that a lot.
> 
> There really is no problem.  The value is in L1d when it is reused.
> This is the generated code (%rdi is m):
> 
>    f:   85 17                   test   %edx,(%rdi)
>   11:   74 0b                   je     1e <flags_remap+0x1e>
>   13:   8b 47 04                mov    0x4(%rdi),%eax
>   16:   09 01                   or     %eax,(%rcx)

the deref of %rcx can be avoided.

>   18:   8b 07                   mov    (%rdi),%eax
>   1a:   f7 d0                   not    %eax
>   1c:   21 c2                   and    %eax,%edx
> 
> At address 18 the load will be satisfied from L1d.  If you would want to
> cache the value at address f you'd have to create one more instruction.
> 
> This really is the best code sequence.  The compiler could have chosen
> to move the value into a register because the array is const.  But it
> didn't.
> 
> 
> > Also: sorry, but ugh-at-the-naming.  We don't *gain* anything from having
> > idenitifers called f, of, m, n and rf.  And we lose quite a lot in
> > readability and understandability.  It would be much nicer to invest a
> > little bit more typing-time here, IMO.
> 
> That's Davide's code and I didn't change it because it doesn't really
> matter.  This is a trivial function which doesn't need more than 10
> seconds to be understood.  If you insist I'll rename the variables and
> elements but I consider this just busy work.

Well if the objective is saving work then why write any code at all?