Skip to contentSkip to conversation

lib: crc32: conditionally constify crc32 lookup table

PATCH Superseded Daniel Borkmann 2 participants 5 messages Dec 31, 2014 – Jan 3, 2015

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib: crc32: conditionally constify crc32 lookup table

Commit 8f243af42ade ("sections: fix const sections for crc32 table") removed the compile-time generated crc32 tables from the RO sections, because it conflicts with the definition of __cacheline_aligned which puts all such aligned data into .data..cacheline_aligned section optimized for wasting less space, and causes const align issues with some GCC versions (see #52181, for example).

We can fix that in two steps: 1) by using the ____cacheline_aligned version, which only aligns the data but doesn't move it into specific sections, 2) test GCC and in problematic cases fall back to the current code, otherwise use const and proper alignment for the lookup tables.

After patch tables are in RO:

$ nm -v lib/crc32.o | grep -1 -E "crc32c?table"
0000000000000000 t arch_local_irq_enable
0000000000000000 r crc32ctable_le
0000000000000000 t crc32_exit
--
0000000000000960 t test_buf
0000000000002000 r crc32table_be
0000000000004000 r crc32table_le
000000001d1056e5 A __crc_crc32_be
---
 Makefile                   |  5 +++++
 lib/Makefile               |  3 +++
 lib/gen_crc32table.c       | 21 +++++++++++++++------
 scripts/gcc-const-align.sh | 21 +++++++++++++++++++++
 4 files changed, 44 insertions(+), 6 deletions(-)
 create mode 100755 scripts/gcc-const-align.sh
Makefile +5 -0
index ef748e1..be02ac2 100644
@@ -776,6 +776,11 @@ ifeq ($(shell $(CONFIG_SHELL) $(srctree)/scripts/gcc-goto.sh $(CC)), y)
 	KBUILD_CFLAGS += -DCC_HAVE_ASM_GOTO
 endif
 
+# check for const + align
+ifeq ($(shell $(CONFIG_SHELL) $(srctree)/scripts/gcc-const-align.sh $(CC)), y)
+	KBUILD_CFLAGS += -DCC_HAVE_CONST_ALIGN
+endif
+
 include $(srctree)/scripts/Makefile.extrawarn
 
 # Add user supplied CPPFLAGS, AFLAGS and CFLAGS as the last assignments
lib/Makefile +3 -0
index 3c3b30b..8b33eec 100644
@@ -171,6 +171,9 @@ obj-$(CONFIG_FONT_SUPPORT) += fonts/
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
 
+# We need to transfer this flag to the host compiler if present
+HOSTCFLAGS_gen_crc32table.o := $(findstring -DCC_HAVE_CONST_ALIGN,$(KBUILD_CFLAGS))
+
 $(obj)/crc32.o: $(obj)/crc32table.h
 
 quiet_cmd_crc32 = GEN     $@
lib/gen_crc32table.c +15 -6
index 71fcfcd..2f06893 100644
@@ -21,6 +21,14 @@
 # define BE_TABLE_SIZE (1 << CRC_BE_BITS)
 #endif
 
+#ifdef CC_HAVE_CONST_ALIGN
+# define TABLE_CONST_ATTR "const"
+# define TABLE_ALIGNMENT  "____cacheline_aligned"
+#else
+# define TABLE_CONST_ATTR ""
+# define TABLE_ALIGNMENT  "__cacheline_aligned"
+#endif
+
 static uint32_t crc32table_le[LE_TABLE_ROWS][256];
 static uint32_t crc32table_be[BE_TABLE_ROWS][256];
 static uint32_t crc32ctable_le[LE_TABLE_ROWS][256];
@@ -109,8 +117,8 @@ int main(int argc, char** argv)
 
 	if (CRC_LE_BITS > 1) {
 		crc32init_le();
-		printf("static u32 __cacheline_aligned "
-		       "crc32table_le[%d][%d] = {",
+		printf("static %s u32 %s crc32table_le[%d][%d] = {",
+		       TABLE_CONST_ATTR, TABLE_ALIGNMENT,
 		       LE_TABLE_ROWS, LE_TABLE_SIZE);
 		output_table(crc32table_le, LE_TABLE_ROWS,
 			     LE_TABLE_SIZE, "tole");
@@ -119,17 +127,18 @@ int main(int argc, char** argv)
 
 	if (CRC_BE_BITS > 1) {
 		crc32init_be();
-		printf("static u32 __cacheline_aligned "
-		       "crc32table_be[%d][%d] = {",
+		printf("static %s u32 %s crc32table_be[%d][%d] = {",
+		       TABLE_CONST_ATTR, TABLE_ALIGNMENT,
 		       BE_TABLE_ROWS, BE_TABLE_SIZE);
 		output_table(crc32table_be, LE_TABLE_ROWS,
 			     BE_TABLE_SIZE, "tobe");
 		printf("};\n");
 	}
+
 	if (CRC_LE_BITS > 1) {
 		crc32cinit_le();
-		printf("static u32 __cacheline_aligned "
-		       "crc32ctable_le[%d][%d] = {",
+		printf("static %s u32 %s crc32ctable_le[%d][%d] = {",
+		       TABLE_CONST_ATTR, TABLE_ALIGNMENT,
 		       LE_TABLE_ROWS, LE_TABLE_SIZE);
 		output_table(crc32ctable_le, LE_TABLE_ROWS,
 			     LE_TABLE_SIZE, "tole");
scripts/gcc-const-align.sh new file +21 -0
new file mode 100755
index 0000000..9b4cf69
@@ -0,0 +1,21 @@
+#!/bin/sh
+# Test for gcc const + __attribute__((aligned())) support
+
+cat << "END" | $@ -x c - -c -o /dev/null >/dev/null 2>&1 && echo "y"
+/*
+ * Some GCC versions will result in broken alignment, probe for
+ * them so we can work around this (see GCC Bug 52181).
+ */
+#define SMP_CACHE_BYTES 64	/* Example alignment. */
+extern const int tv1[];
+const int __attribute__((aligned(SMP_CACHE_BYTES))) tv1[] = { 1 };
+extern const int __attribute__((aligned(SMP_CACHE_BYTES))) tv2[];
+const int tv2[] = { 1 };
+extern const int __attribute__((aligned(SMP_CACHE_BYTES))) tv3[];
+const int __attribute__((aligned(SMP_CACHE_BYTES))) tv3[] = { 1 };
+const int __attribute__((aligned(SMP_CACHE_BYTES))) tv4[] = { 1 };
+int probe[__alignof__(tv4) != __alignof__(tv1) ||
+	  __alignof__(tv4) != __alignof__(tv2) ||
+	  __alignof__(tv4) != __alignof__(tv3) ||
+	  __alignof__(tv4) != SMP_CACHE_BYTES ? -1 : 0];
+END
Signature · 1 line
1.7.11.7
maintainer
#1 lore raw
Quoted 1 line · On Wed, 31 Dec 2014 20:03:28 +0100 Daniel Borkmann <[email protected]> wrote:

Commit 8f243af42ade ("sections: fix const sections for crc32 table")

The 8f243af42ade changelog is rather poor :(. With the help of this changelog I can now see what 8f243af42ade was doing. I must have been asleep at the time.

Quoted 5 lines

removed the compile-time generated crc32 tables from the RO sections, because it conflicts with the definition of __cacheline_aligned which puts all such aligned data into .data..cacheline_aligned section optimized for wasting less space, and causes const align issues with some GCC versions (see #52181, for example).

(searches several bugzilla databases)

"https://gcc.gnu.org/bugzilla/show_bug.cgi?id=52181" would be more reader-friendly.

Quoted 17 lines

We can fix that in two steps: 1) by using the ____cacheline_aligned version, which only aligns the data but doesn't move it into specific sections, 2) test GCC and in problematic cases fall back to the current code, otherwise use const and proper alignment for the lookup tables.

After patch tables are in RO:

$ nm -v lib/crc32.o | grep -1 -E "crc32c?table"
0000000000000000 t arch_local_irq_enable
0000000000000000 r crc32ctable_le
0000000000000000 t crc32_exit
--
0000000000000960 t test_buf
0000000000002000 r crc32table_be
0000000000004000 r crc32table_le
000000001d1056e5 A __crc_crc32_be
Quoted 8 lines
---
 Makefile                   |  5 +++++
 lib/Makefile               |  3 +++
 lib/gen_crc32table.c       | 21 +++++++++++++++------
 scripts/gcc-const-align.sh | 21 +++++++++++++++++++++
 4 files changed, 44 insertions(+), 6 deletions(-)

Seems a lot of fuss. Why are these tables cacheline aligned anyway? To avoid one cache miss (most of the time, presumably) in a 16k table. Pretty marginal benefit, I suspect.

Quoted 17 lines
lib/Makefile +3 -0
@@ -171,6 +171,9 @@ obj-$(CONFIG_FONT_SUPPORT) += fonts/
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
 
+# We need to transfer this flag to the host compiler if present
+HOSTCFLAGS_gen_crc32table.o := $(findstring -DCC_HAVE_CONST_ALIGN,$(KBUILD_CFLAGS))
+
 $(obj)/crc32.o: $(obj)/crc32table.h
 
 quiet_cmd_crc32 = GEN     $@
lib/gen_crc32table.c +0 -0
index 71fcfcd..2f06893 100644

lib/gen_crc32table.c line 30

Quoted 10 lines
lib/gen_crc32table.c +7 -0
@@ -21,6 +21,14 @@
 # define BE_TABLE_SIZE (1 << CRC_BE_BITS)
 #endif
 
+#ifdef CC_HAVE_CONST_ALIGN
+# define TABLE_CONST_ATTR "const"
+# define TABLE_ALIGNMENT  "____cacheline_aligned"
+#else
+# define TABLE_CONST_ATTR ""
+# define TABLE_ALIGNMENT  "__cacheline_aligned"
+#endif

Pity out poor readers, trying to work out what all this does and why it is here. It is totally unobvious that this is working around some gcc bug. Can we please have a nice comment which explains everything?

#2 lore raw
Quoted 14 lines · Andrew Morton
Quoted 1 line · On Wed, 31 Dec 2014 20:03:28 +0100 Daniel Borkmann <[email protected]> wrote:

Commit 8f243af42ade ("sections: fix const sections for crc32 table")

The 8f243af42ade changelog is rather poor :(. With the help of this changelog I can now see what 8f243af42ade was doing. I must have been asleep at the time.

Quoted 5 lines

removed the compile-time generated crc32 tables from the RO sections, because it conflicts with the definition of __cacheline_aligned which puts all such aligned data into .data..cacheline_aligned section optimized for wasting less space, and causes const align issues with some GCC versions (see #52181, for example).

Quoted 4 lines

(searches several bugzilla databases)

"https://gcc.gnu.org/bugzilla/show_bug.cgi?id=52181" would be more reader-friendly.

Okay, will add it like that.

Quoted 26 lines
Quoted 17 lines

We can fix that in two steps: 1) by using the ____cacheline_aligned version, which only aligns the data but doesn't move it into specific sections, 2) test GCC and in problematic cases fall back to the current code, otherwise use const and proper alignment for the lookup tables.

After patch tables are in RO:

$ nm -v lib/crc32.o | grep -1 -E "crc32c?table"
0000000000000000 t arch_local_irq_enable
0000000000000000 r crc32ctable_le
0000000000000000 t crc32_exit
--
0000000000000960 t test_buf
0000000000002000 r crc32table_be
0000000000004000 r crc32table_le
000000001d1056e5 A __crc_crc32_be
Quoted 8 lines
---
  Makefile                   |  5 +++++
  lib/Makefile               |  3 +++
  lib/gen_crc32table.c       | 21 +++++++++++++++------
  scripts/gcc-const-align.sh | 21 +++++++++++++++++++++
  4 files changed, 44 insertions(+), 6 deletions(-)
Quoted 3 lines

Seems a lot of fuss. Why are these tables cacheline aligned anyway? To avoid one cache miss (most of the time, presumably) in a 16k table. Pretty marginal benefit, I suspect.

I guess, it actually came in with the slice-by-8 algorithm (e.g. used in SCTP checksumming if no offloading is available) that was added back then, that is, commit 324eb0f17d9dc ("crc32: add slice-by-8 algorithm to existing code").

Quoted 20 lines
Quoted 20 lines
lib/Makefile +3 -0
@@ -171,6 +171,9 @@ obj-$(CONFIG_FONT_SUPPORT) += fonts/
  hostprogs-y	:= gen_crc32table
  clean-files	:= crc32table.h
 
+# We need to transfer this flag to the host compiler if present
+HOSTCFLAGS_gen_crc32table.o := $(findstring -DCC_HAVE_CONST_ALIGN,$(KBUILD_CFLAGS))
+
  $(obj)/crc32.o: $(obj)/crc32table.h
 
  quiet_cmd_crc32 = GEN     $@
lib/gen_crc32table.c +0 -0
index 71fcfcd..2f06893 100644
@@ -21,6 +21,14 @@
  # define BE_TABLE_SIZE (1 << CRC_BE_BITS)
  #endif
 
Quoted 11 lines

lib/gen_crc32table.c line 30

Quoted 7 lines
lib/gen_crc32table.c +7 -0
+#ifdef CC_HAVE_CONST_ALIGN
+# define TABLE_CONST_ATTR "const"
+# define TABLE_ALIGNMENT  "____cacheline_aligned"
+#else
+# define TABLE_CONST_ATTR ""
+# define TABLE_ALIGNMENT  "__cacheline_aligned"
+#endif

Pity out poor readers, trying to work out what all this does and why it is here. It is totally unobvious that this is working around some gcc bug. Can we please have a nice comment which explains everything?

Will add a comment, sure.

Thanks, Andrew!

I'll send out v2 with your feedback tomorrow.

maintainer
#3 lore raw
Quoted 8 lines · On Sat, 03 Jan 2015 01:12:43 +0100 Daniel Borkmann <[email protected]> wrote:
Quoted 3 lines

Seems a lot of fuss. Why are these tables cacheline aligned anyway? To avoid one cache miss (most of the time, presumably) in a 16k table. Pretty marginal benefit, I suspect.

I guess, it actually came in with the slice-by-8 algorithm (e.g. used in SCTP checksumming if no offloading is available) that was added back then, that is, commit 324eb0f17d9dc ("crc32: add slice-by-8 algorithm to existing code").

non-responsive ;) By far the simplest solution is to remove the cacheline alignment.

Are there other places where CC_HAVE_CONST_ALIGN can be used? I'm seeing

z:/usr/src/linux-3.19-rc2> grep -r cacheline_aligned . | grep const ./arch/x86/um/sys_call_table_32.c:const sys_call_ptr_t sys_call_table[] __cacheline_aligned = { ./arch/x86/um/sys_call_table_64.c:const sys_call_ptr_t sys_call_table[] __cacheline_aligned = {
./include/net/netfilter/nf_tables.h: const struct nft_set_ops *ops ____cacheline_aligned;
./net/ethernet/eth.c:const struct header_ops eth_header_ops ____cacheline_aligned = {

#4 lore raw
Quoted 6 lines · Andrew Morton
Quoted 4 lines · On Sat, 03 Jan 2015 01:12:43 +0100 Daniel Borkmann <[email protected]> wrote:
Quoted 3 lines

Seems a lot of fuss. Why are these tables cacheline aligned anyway? To avoid one cache miss (most of the time, presumably) in a 16k table. Pretty marginal benefit, I suspect.

Quoted 7 lines
Quoted 4 lines

I guess, it actually came in with the slice-by-8 algorithm (e.g. used in SCTP checksumming if no offloading is available) that was added back then, that is, commit 324eb0f17d9dc ("crc32: add slice-by-8 algorithm to existing code").

non-responsive ;) By far the simplest solution is to remove the cacheline alignment.

Alternatively, I'm thinking of const + ____cacheline_aligned (w/o the gcc test case). In case some people run gcc versions that have the bug, it's worst case just as good as const only, and in the majority of cases aligned as expected.

Quoted 5 lines

Are there other places where CC_HAVE_CONST_ALIGN can be used? I'm seeing

z:/usr/src/linux-3.19-rc2> grep -r cacheline_aligned . | grep const ./arch/x86/um/sys_call_table_32.c:const sys_call_ptr_t sys_call_table[] __cacheline_aligned = { ./arch/x86/um/sys_call_table_64.c:const sys_call_ptr_t sys_call_table[] __cacheline_aligned = {

I'll investigate these two above and send a patch, thanks. They should actually be using ____cacheline_aligned instead!

Quoted 2 lines

./include/net/netfilter/nf_tables.h: const struct nft_set_ops *ops ____cacheline_aligned;
./net/ethernet/eth.c:const struct header_ops eth_header_ops ____cacheline_aligned = {