[PATCH for -tip 0/2] Generic Alignment API

[PATCH for -tip 0/2] Generic Alignment API

[Mathieu Desnoyers]

Hi,

These two patches implement a generic alignment header needed by the "Generic
Ring Buffer" patchset and by xchg() fallback implementation on some ARM
architectures.

The goal of this patch is to move pointer alignment arithmetic to one single
location in the kernel rather than spreading these all over the place as this is
currently the case in the Linux kernel (especially when an alignment on the
floor value is needed).

I submit this patch for inclusion through -tip. Meanwhile, I will pull it in a
git tree (based on -tip) on top of which I will rebase the "Generic Ring Buffer"
patchset:

 git://git.kernel.org/pub/scm/linux/kernel/git/compudj/linux-2.6-ringbuffer.git
   branch: tip-pull-queue

Ingo, to merge these patches, you can either take these 2 patches or pull from
the "tip-pull-queue", at your convenience (tip-pull-queue is based on
tip/master).

Thanks,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[PATCH for -tip 2/2] Create generic alignment API (v9)

[Mathieu Desnoyers]

[-- Attachment #1: create-generic-alignment-api.patch --]
[-- Type: text/plain, Size: 6864 bytes --]

Rather than re-doing the "alignment on a type size" trick all over again at
different levels, import the "ltt_align" from LTTng into kernel.h and make this
available to everyone. Renaming to:

- object_align()
- object_align_floor()
- offset_align()
- offset_align_floor()

Changelog since v8:
- Remove unnecessary braces.
- Update object_align/object_align_floor comments.

Changelog since v7:
- Add missing include/linux/Kconfig header-y.

Changelog since v6:
- Adapt to changes introduced by
  commit a79ff731a1b277d0e92d9453bdf374e04cec717a
- Use __alignof__() instead of sizeof() to support compound types.

Changelog since v5:
- moved alignment apis to a separate header file so that it is possible
  to use them from other header files which are, for example, included
  from kernel.h.

Changelog since v4:
- add missing ( ) around parameters within object_align() and
  object_align_floor().
- More coding style cleanups to ALIGN() (checkpatch.pl is happy now).

Changelog since v3:
- optimize object_align*() so fewer instructions are needed for alignment of
  addresses known dynamically. Use the (already existing) "ALIGN()", and create
  the "ALIGN_FLOOR()" macro.
- While we are there, let's clean up the ALIGN() macros wrt coding style. e.g.
  missing parenthesis around the first use of the "x" parameter in ALIGN().

Changelog since v2:
- Fix object_align*(): should use object size alignment, not pointer alignment.

Changelog since v1:
- Align on the object natural alignment
    (rather than min(arch word alignment, natural alignment))

The advantage of separating the API in "object alignment" and "offset alignment"
is that it gives more freedom to play with offset alignment. Very useful to
implement a tracer ring-buffer alignment. (hint hint)

Typical users will use "object alignment", but infrastructures like tracers
which need to perform alignment of statically known base+offsets will typically
use "offset alignment", because it allows to align with respect to a base rather
than to pass an absolute address.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Alexander Shishkin <virtuoso@slind.org>
Reviewed-by: Steven Rostedt <rostedt@goodmis.org>
Reviewed-by: "Kirill A. Shutemov" <kirill@shutemov.name>
CC: Russell King - ARM Linux <linux@arm.linux.org.uk>
CC: linux-arm-kernel@lists.infradead.org
CC: Imre Deak <imre.deak@nokia.com>
CC: Jamie Lokier <jamie@shareable.org>
CC: mingo@elte.hu
CC: Alexey Dobriyan <adobriyan@gmail.com>
---
 include/linux/Kbuild   |    1 
 include/linux/align.h  |   59 +++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/kernel.h |   10 ++------
 3 files changed, 63 insertions(+), 7 deletions(-)
 create mode 100644 include/linux/align.h

Index: linux.trees.git/include/linux/align.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux.trees.git/include/linux/align.h	2010-08-17 22:12:37.000000000 -0400
@@ -0,0 +1,59 @@
+#ifndef _LINUX_ALIGN_H
+#define _LINUX_ALIGN_H
+
+#define __ALIGN_KERNEL(x, a)	__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
+#define __ALIGN_KERNEL_MASK(x, mask) \
+				(((x) + (mask)) & ~(mask))
+
+#ifdef __KERNEL__
+
+#include <linux/types.h>
+#include <linux/log2.h>
+
+#define ALIGN(x, a)		__ALIGN_KERNEL(x, a)
+#define __ALIGN_MASK(x, mask)	__ALIGN_KERNEL_MASK(x, mask)
+#define PTR_ALIGN(p, a)		((typeof(p)) ALIGN((unsigned long) (p), a))
+#define ALIGN_FLOOR(x, a)	__ALIGN_FLOOR_MASK(x, (typeof(x)) (a) - 1)
+#define __ALIGN_FLOOR_MASK(x, mask)	((x) & ~(mask))
+#define PTR_ALIGN_FLOOR(p, a) \
+			((typeof(p)) ALIGN_FLOOR((unsigned long) (p), a))
+#define IS_ALIGNED(x, a)	(((x) & ((typeof(x)) (a) - 1)) == 0)
+
+/*
+ * Align pointer on natural object alignment.
+ */
+#define object_align(obj)	PTR_ALIGN(obj, __alignof__(*(obj)))
+#define object_align_floor(obj)	PTR_ALIGN_FLOOR(obj, __alignof__(*(obj)))
+
+/**
+ * offset_align - Calculate the offset needed to align an object on its natural
+ *                alignment towards higher addresses.
+ * @align_drift:  object offset from an "alignment"-aligned address.
+ * @alignment:    natural object alignment. Must be non-zero, power of 2.
+ *
+ * Returns the offset that must be added to align towards higher
+ * addresses.
+ */
+#define offset_align(align_drift, alignment)			\
+	({							\
+		MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(alignment);	\
+		((alignment - align_drift) & (alignment - 1));	\
+	})
+
+/**
+ * offset_align_floor - Calculate the offset needed to align an object
+ *                      on its natural alignment towards lower addresses.
+ * @align_drift:  object offset from an "alignment"-aligned address.
+ * @alignment:    natural object alignment. Must be non-zero, power of 2.
+ *
+ * Returns the offset that must be substracted to align towards lower addresses.
+ */
+#define offset_align_floor(align_drift, alignment)		\
+	({							\
+		MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(alignment);	\
+		((align_drift - alignment) & (alignment - 1);	\
+	})
+
+#endif /* __KERNEL__ */
+
+#endif
Index: linux.trees.git/include/linux/kernel.h
===================================================================
--- linux.trees.git.orig/include/linux/kernel.h	2010-08-17 22:12:11.000000000 -0400
+++ linux.trees.git/include/linux/kernel.h	2010-08-17 22:13:31.000000000 -0400
@@ -4,8 +4,6 @@
 /*
  * 'kernel.h' contains some often-used function prototypes etc
  */
-#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
-#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))
 
 #ifdef __KERNEL__
 
@@ -39,11 +37,6 @@ extern const char linux_proc_banner[];
 
 #define STACK_MAGIC	0xdeadbeef
 
-#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
-#define __ALIGN_MASK(x, mask)	__ALIGN_KERNEL_MASK((x), (mask))
-#define PTR_ALIGN(p, a)		((typeof(p))ALIGN((unsigned long)(p), (a)))
-#define IS_ALIGNED(x, a)		(((x) & ((typeof(x))(a) - 1)) == 0)
-
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))
 
 /*
@@ -771,6 +764,9 @@ struct sysinfo {
 #define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:-!!(e); }))
 #define BUILD_BUG_ON_NULL(e) ((void *)sizeof(struct { int:-!!(e); }))
 
+/* The header align.h depends on MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2() */
+#include <linux/align.h>
+
 /* Trap pasters of __FUNCTION__ at compile-time */
 #define __FUNCTION__ (__func__)
 
Index: linux.trees.git/include/linux/Kbuild
===================================================================
--- linux.trees.git.orig/include/linux/Kbuild	2010-08-17 22:12:11.000000000 -0400
+++ linux.trees.git/include/linux/Kbuild	2010-08-17 22:12:37.000000000 -0400
@@ -38,6 +38,7 @@ header-y += adfs_fs.h
 header-y += affs_hardblocks.h
 header-y += agpgart.h
 header-y += aio_abi.h
+header-y += align.h
 header-y += apm_bios.h
 header-y += arcfb.h
 header-y += atalk.h

Re: [PATCH for -tip 1/2] kernel.h: add MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2

[Alexey Dobriyan]

On Sat, Aug 21, 2010 at 10:17:51AM -0400, Mathieu Desnoyers wrote:
> +/* Force a compilation error if condition is constant and not a power of 2 */
> +#define MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(n)		\
> +	MAYBE_BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))

Sorry, this is tasteless macro.

Re: [PATCH for -tip 1/2] kernel.h: add MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2

[Mathieu Desnoyers]

* Alexey Dobriyan (adobriyan@gmail.com) wrote:
> On Sat, Aug 21, 2010 at 10:17:51AM -0400, Mathieu Desnoyers wrote:
> > +/* Force a compilation error if condition is constant and not a power of 2 */
> > +#define MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(n)		\
> > +	MAYBE_BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))
> 
> Sorry, this is tasteless macro.

Let's look at the surrounding where I added this macro in kernel.h:


/* Force a compilation error if condition is true */
#define BUILD_BUG_ON(condition) ((void)BUILD_BUG_ON_ZERO(condition))

/* Force a compilation error if condition is constant and true */
#define MAYBE_BUILD_BUG_ON(cond) ((void)sizeof(char[1 - 2 * !!(cond)]))

/* Force a compilation error if a constant expression is not a power of 2 */
#define BUILD_BUG_ON_NOT_POWER_OF_2(n)			\
	BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))

/* Force a compilation error if condition is true, but also produce a
   result (of value 0 and type size_t), so the expression can be used
   e.g. in a structure initializer (or where-ever else comma expressions
   aren't permitted). */
#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:-!!(e); }))
#define BUILD_BUG_ON_NULL(e) ((void *)sizeof(struct { int:-!!(e); }))


So I am guessing that you plan to rewrite all of these ? Or perharps you have
other suggestions ? Commit cc8ef6eb21e964b1c5eb97b2d0e8ac9893e1bf86 introduced
"BUILD_BUG_ON_NOT_POWER_OF_2()" btw.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Re: [PATCH for -tip 1/2] kernel.h: add MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2

[Andi Kleen]

> +/* Force a compilation error if condition is constant and not a power of 2 */
> +#define MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(n)		\
> +	MAYBE_BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))

Looks super-ugly. IMHO just writing MAYBE_BUILD_BUG_ON(!n || n & (n - 1)) directly
would be clear enough. If you really think that's unclear define a generic
is_power_of_two() macro.

-Andi

Re: [PATCH for -tip 1/2] kernel.h: add MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2

[Mathieu Desnoyers]

* Andi Kleen (andi@firstfloor.org) wrote:
> > +/* Force a compilation error if condition is constant and not a power of 2 */
> > +#define MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(n)		\
> > +	MAYBE_BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))
> 
> Looks super-ugly. IMHO just writing MAYBE_BUILD_BUG_ON(!n || n & (n - 1)) directly
> would be clear enough. If you really think that's unclear define a generic
> is_power_of_two() macro.

There is already a is_power_of_two macro in log2.h, but I fear it might
incorrectly interact with "MAYBE_BUILD_BUG_ON" (for some reason passing the
constant result of a static inline is not treated as a constant by the macro,
and thus it always "passes" the test).

So if everyone object to this new macro, I'd be tempted to just go with your
suggestion. However the fact that we already have BUILD_BUG_ON_NOT_POWER_OF_2(n)
made me think that some people prefer to have it done as a macro.

Other opinions ?

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Re: [PATCH for -tip 1/2] kernel.h: add MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2

[Anca Emanuel]

I think about some test at the last bit if it is on, the number is not
a power of 2

On Sun, Aug 22, 2010 at 10:38 PM, Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
> * Andi Kleen (andi@firstfloor.org) wrote:
>> > +/* Force a compilation error if condition is constant and not a power of 2 */
>> > +#define MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(n)               \
>> > +   MAYBE_BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))
>>
>> Looks super-ugly. IMHO just writing MAYBE_BUILD_BUG_ON(!n || n & (n - 1)) directly
>> would be clear enough. If you really think that's unclear define a generic
>> is_power_of_two() macro.
>
> There is already a is_power_of_two macro in log2.h, but I fear it might
> incorrectly interact with "MAYBE_BUILD_BUG_ON" (for some reason passing the
> constant result of a static inline is not treated as a constant by the macro,
> and thus it always "passes" the test).
>
> So if everyone object to this new macro, I'd be tempted to just go with your
> suggestion. However the fact that we already have BUILD_BUG_ON_NOT_POWER_OF_2(n)
> made me think that some people prefer to have it done as a macro.
>
> Other opinions ?
>
> Thanks,
>
> Mathieu
>
>
> --
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: [PATCH for -tip 1/2] kernel.h: add MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2

[Mathieu Desnoyers]

* Anca Emanuel (anca.emanuel@gmail.com) wrote:
> I think about some test at the last bit if it is on, the number is not
> a power of 2

Can you give an example, along with the types you have in mind ?

Thanks,

Mathieu

> 
> On Sun, Aug 22, 2010 at 10:38 PM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
> > * Andi Kleen (andi@firstfloor.org) wrote:
> >> > +/* Force a compilation error if condition is constant and not a power of 2 */
> >> > +#define MAYBE_BUILD_BUG_ON_NOT_POWER_OF_2(n)               \
> >> > +   MAYBE_BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))
> >>
> >> Looks super-ugly. IMHO just writing MAYBE_BUILD_BUG_ON(!n || n & (n - 1)) directly
> >> would be clear enough. If you really think that's unclear define a generic
> >> is_power_of_two() macro.
> >
> > There is already a is_power_of_two macro in log2.h, but I fear it might
> > incorrectly interact with "MAYBE_BUILD_BUG_ON" (for some reason passing the
> > constant result of a static inline is not treated as a constant by the macro,
> > and thus it always "passes" the test).
> >
> > So if everyone object to this new macro, I'd be tempted to just go with your
> > suggestion. However the fact that we already have BUILD_BUG_ON_NOT_POWER_OF_2(n)
> > made me think that some people prefer to have it done as a macro.
> >
> > Other opinions ?
> >
> > Thanks,
> >
> > Mathieu
> >
> >
> > --
> > Mathieu Desnoyers
> > Operating System Efficiency R&D Consultant
> > EfficiOS Inc.
> > http://www.efficios.com
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > Please read the FAQ at  http://www.tux.org/lkml/
> >

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com