[RFC v0 0/1] Add support for CRC64 generation in linker

[RFC v0 0/1] Add support for CRC64 generation in linker

[binutils]

Cleaned up attempt to generate CRC64.


Added code in lang_end() to calculate the CRC.
So far, I can retrieve the location of the CRC
and the start and end for the area.
I can fetch the .text segment as an asection but
 
  if ( bfd_get_section_contents (link_info.output_bfd,
	  ts,
	  text_section,
	  0,
	  ts->size))

fails...

The patchset should contain the LICENSE and the testsuite
but git-send-email does not like if I send 8 patches.
Sending 6 patches is OK for some reason...

[PATCH v0 1/6] CRC64 header
[PATCH v0 2/6] ldlang.h: CRC64
[PATCH v0 3/6] ldlex.l: CRC64
[PATCH v0 4/6] ldgram.y: CRC64
[PATCH v0 5/6] ldlang.c: CRC64
[PATCH v0 6/6] ldlang.c: Try to get the .text section for checking

[PATCH v0 1/6] CRC64 header

[binutils]

From: Ulf Samuelsson <binutils@emagii.com>

Signed-off-by: Ulf Samuelsson <binutils@emagii.com>
---
 ld/checksum.h | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)
 create mode 100755 ld/checksum.h

diff --git a/ld/checksum.h b/ld/checksum.h
new file mode 100755
index 00000000000..49a2aedd04b
--- /dev/null
+++ b/ld/checksum.h
@@ -0,0 +1,48 @@
+/*
+ * Library: libcrc
+ * Author:  Lammert Bies
+ *
+ * This file is licensed under the MIT License as stated below
+ *
+ * Copyright (c) 2016 Lammert Bies
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ */
+
+#ifndef CHECKSUM_H
+#define CHECKSUM_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+#define		CRC_POLY_64			0x42F0E1EBA9EA3693ull
+#define		CRC_POLY_64_ISO		0xD800000000000000ull
+
+#define		CRC_START_64		0x0000000000000000ull
+#define		CRC_START_64_INV	0xFFFFFFFFFFFFFFFFull
+
+#define	CRC_ADDRESS	"___CRC64___"
+#define	CRC_START	"___CRC64_START___"
+#define	CRC_END		"___CRC64_END___"
+
+bfd_vma	crc_64    (const unsigned char *input_str, size_t num_bytes);
+bfd_vma	crc_64_inv(const unsigned char *input_str, size_t num_bytes);
+
+#endif /* CHECKSUM_H */
-- 
2.17.1

[PATCH v0 2/6] ldlang.h: CRC64

[binutils]

From: Ulf Samuelsson <binutils@emagii.com>

Signed-off-by: Ulf Samuelsson <binutils@emagii.com>
---
 ld/ldlang.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/ld/ldlang.h b/ld/ldlang.h
index 2300fa5b2a3..1e9b5324f74 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -632,6 +632,12 @@ extern lang_output_section_statement_type *lang_output_section_statement_lookup
   (const char *, int, int);
 extern lang_output_section_statement_type *next_matching_output_section_statement
   (lang_output_section_statement_type *, int);
+extern void lang_add_crc_syndrome
+  (bool, bfd_vma);
+extern void lang_add_crc_table
+  (void);
+extern void lang_set_crc_region
+  (union etree_union *start, union etree_union *end);
 extern void ldlang_add_undef
   (const char *const, bool);
 extern void ldlang_add_require_defined
-- 
2.17.1

[PATCH v0 3/6] ldlex.l: CRC64

[binutils]

From: Ulf Samuelsson <binutils@emagii.com>

Signed-off-by: Ulf Samuelsson <binutils@emagii.com>
---
 ld/ldlex.l | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/ld/ldlex.l b/ld/ldlex.l
index 910e7ea3b8b..a8c95e66f7b 100644
--- a/ld/ldlex.l
+++ b/ld/ldlex.l
@@ -298,6 +298,15 @@ V_IDENTIFIER [*?.$_a-zA-Z\[\]\-\!\^\\]([*?.$_a-zA-Z0-9\[\]\-\!\^\\]|::)*
 <SCRIPT>"AFTER"				{ RTOKEN(AFTER); }
 <SCRIPT>"BEFORE"			{ RTOKEN(BEFORE); }
 <WILD>"FILL"				{ RTOKEN(FILL); }
+<WILD>"CRC64"				{ RTOKEN(CRC64); }
+<WILD>"ECMA"				{ RTOKEN(ECMA); }
+<WILD>"ISO"					{ RTOKEN(ISO); }
+<WILD>"POLY"				{ RTOKEN(POLY); }
+<WILD>"POLYI"				{ RTOKEN(POLYI); }
+<WILD>"TABLE"				{ RTOKEN(TABLE); }
+<WILD>"DEBUG"				{ RTOKEN(DEBUG); }
+<WILD>"ON"					{ RTOKEN(ON); }
+<WILD>"OFF"					{ RTOKEN(OFF); }
 <SCRIPT>"STARTUP"			{ RTOKEN(STARTUP); }
 <SCRIPT>"OUTPUT_FORMAT"			{ RTOKEN(OUTPUT_FORMAT); }
 <SCRIPT>"OUTPUT_ARCH"			{ RTOKEN(OUTPUT_ARCH); }
-- 
2.17.1

[PATCH v0 4/6] ldgram.y: CRC64

[binutils]

From: Ulf Samuelsson <binutils@emagii.com>

Signed-off-by: Ulf Samuelsson <binutils@emagii.com>
---
 ld/ldgram.y | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

diff --git a/ld/ldgram.y b/ld/ldgram.y
index faffeec94b8..0a18268cf86 100644
--- a/ld/ldgram.y
+++ b/ld/ldgram.y
@@ -41,6 +41,7 @@
 #include "mri.h"
 #include "ldctor.h"
 #include "ldlex.h"
+#include "checksum.h"
 
 #ifndef YYDEBUG
 #define YYDEBUG 1
@@ -130,6 +131,8 @@ static int error_index;
 %token DATA_SEGMENT_ALIGN DATA_SEGMENT_RELRO_END DATA_SEGMENT_END
 %token SORT_BY_NAME SORT_BY_ALIGNMENT SORT_NONE
 %token SORT_BY_INIT_PRIORITY
+%token CRC64 ECMA ISO POLY POLYI TABLE
+%token DEBUG ON OFF
 %token '{' '}'
 %token SIZEOF_HEADERS OUTPUT_FORMAT FORCE_COMMON_ALLOCATION OUTPUT_ARCH
 %token INHIBIT_COMMON_ALLOCATION FORCE_GROUP_ALLOCATION
@@ -682,6 +685,27 @@ statement:
 		{
 		  lang_add_fill ($3);
 		}
+	| DEBUG ON
+		{
+			yydebug = 1;
+		}
+	| DEBUG OFF
+		{
+			yydebug = 0;
+		}
+	| CRC64 	
+		{
+		  lang_add_assignment (exp_assign (CRC_ADDRESS, exp_nameop (NAME,"."), false));		
+		}
+		polynome '(' mustbe_exp ',' mustbe_exp ')'
+		{
+		  lang_add_assignment (exp_assign (CRC_START, $5, false));
+		  lang_add_assignment (exp_assign (CRC_END,   $7, false));
+		}
+	| CRC64 TABLE
+		{
+			lang_add_crc_table();
+		}
 	| ASSERT_K
 		{ ldlex_expression (); }
 	  '(' exp ',' NAME ')' separator
@@ -696,6 +720,25 @@ statement:
 	  statement_list_opt END
 	;
 
+polynome:
+	  ECMA
+		{
+		  lang_add_crc_syndrome(false, CRC_POLY_64);
+		}
+	| ISO
+		{
+		  lang_add_crc_syndrome(false, CRC_POLY_64_ISO);
+		}
+	| POLY '[' mustbe_exp ']'
+		{
+		  lang_add_crc_syndrome(false, $3->value.value);
+		}
+		
+	| POLYI '[' mustbe_exp ']'
+		{
+		  lang_add_crc_syndrome(true,  $3->value.value);
+		}
+
 statement_list:
 		statement_list statement
 	|	statement
-- 
2.17.1

[PATCH v0 5/6] ldlang.c: CRC64

[binutils]

From: Ulf Samuelsson <binutils@emagii.com>

Signed-off-by: Ulf Samuelsson <binutils@emagii.com>
---
 ld/ldlang.c | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 132 insertions(+)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 2852a4222d3..e0bb079b34e 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -42,6 +42,8 @@
 #include "demangle.h"
 #include "hashtab.h"
 #include "elf-bfd.h"
+#include "checksum.h"
+
 #if BFD_SUPPORTS_PLUGINS
 #include "plugin.h"
 #endif /* BFD_SUPPORTS_PLUGINS */
@@ -145,6 +147,11 @@ int lang_statement_iteration = 0;
 /* Count times through one_lang_size_sections_pass after mark phase.  */
 static int lang_sizing_iteration = 0;
 
+/* CRC calculation on output section */
+bfd_vma  crc64_poly  = CRC_POLY_64;	/* Default Polynome is CRC64 ECMA */
+bfd_vma *crc64_tab   = NULL;
+bool      crc64_invert= false;
+
 /* Return TRUE if the PATTERN argument is a wildcard pattern.
    Although backslashes are treated specially if a pattern contains
    wildcards, we do not consider the mere presence of a backslash to
@@ -8524,6 +8531,131 @@ lang_add_attribute (enum statement_enum attribute)
   new_statement (attribute, sizeof (lang_statement_header_type), stat_ptr);
 }
 
+/*
+ * bfd_vma *init_crc64_tab( bfd_vma poly ) ;
+ *
+ * For optimal speed, the CRC64 calculation uses a table with pre-calculated
+ * bit patterns which are used in the XOR operations in the program. This table
+ * is generated on request and is available as a table with constant values.
+ * init_crc64_tab is copyright (c) 2016 Lammert Bies
+ */
+static
+bfd_vma *init_crc64_tab( bfd_vma poly ) {
+
+	bfd_vma i;
+	bfd_vma j;
+	bfd_vma c;
+	bfd_vma crc;
+	bfd_vma *crc_tab;
+
+	crc_tab = malloc(256 * sizeof(bfd_vma));
+	if (crc_tab == NULL)
+		return NULL;
+
+	for (i=0; i<256; i++) {
+
+		crc = 0;
+		c   = i << 56;
+
+		for (j=0; j<8; j++) {
+
+			if ( ( crc ^ c ) & 0x8000000000000000ull ) crc = ( crc << 1 ) ^ poly;
+			else                                       crc =   crc << 1;
+
+			c = c << 1;
+		}
+
+		crc_tab[i] = crc;
+	}
+	return crc_tab;
+
+}  /* init_crc64_tab */
+
+/*
+ * bfd_vma crc_64_ecma( const unsigned char *input_str, size_t num_bytes );
+ *
+ * The function crc_64() calculates in one pass the 64 bit CRC value
+ * for a byte string that is passed to the function together with a parameter
+ * indicating the length.
+ * This is used for CRC64-ECMA and CRC64-ISO
+ * crc_64 is copyright (c) 2016 Lammert Bies
+ */
+
+bfd_vma crc_64(const unsigned char *input_str, size_t num_bytes)
+{
+	bfd_vma crc;
+	const unsigned char *ptr;
+	size_t a;
+	crc = CRC_START_64;
+	ptr = input_str;
+	if ( ptr != NULL ) {
+		for (a=0; a<num_bytes; a++) {
+			crc = (crc << 8) ^ crc64_tab[ ((crc >> 56) ^ (bfd_vma) *ptr++) & 0x00000000000000FFull ];
+		}
+	}
+	return crc;
+}  /* crc_64 */
+
+/*
+ * The function crc_64_inv() calculates in one pass the CRC64 64 bit CRC
+ * value for a byte string that is passed to the function together with a
+ * parameter indicating the length.
+ * This is used for CRC64-WE
+ * crc_64_inv is copyright (c) 2016 Lammert Bies
+ */
+
+bfd_vma crc_64_inv( const unsigned char *input_str, size_t num_bytes ) {
+
+	bfd_vma crc;
+	const unsigned char *ptr;
+	size_t a;
+
+	crc = CRC_START_64_INV;
+	ptr = input_str;
+
+	if ( ptr != NULL ) {
+		for (a=0; a<num_bytes; a++) {
+			crc = (crc << 8) ^ crc64_tab[ ((crc >> 56) ^ (bfd_vma) *ptr++) & 0x00000000000000FFull ];
+		}
+	}
+
+	return crc ^ 0xFFFFFFFFFFFFFFFFull;
+
+}  /* crc_64_inv */
+
+extern void lang_add_crc_syndrome(bool invert, bfd_vma poly)
+{
+  crc64_poly = poly;			/* Set the polynom */
+  crc64_invert = invert;
+  printf("Adding Syndrome: 0x%08lx\n", poly);
+  lang_add_data (QUAD, exp_intop (0));	/* Reserve room for the ECC value */
+  if (crc64_tab == NULL)
+    {
+      crc64_tab = init_crc64_tab(crc64_poly);
+    }
+  else
+    {
+      einfo (_("%P:%pS: warning: CRC polynome declared twice (ignored)\n"), NULL);
+    }
+}
+
+extern void lang_add_crc_table(void)
+{
+  if (crc64_tab == NULL)
+    {
+      crc64_tab = init_crc64_tab(crc64_poly);
+      if (crc64_tab == NULL)
+	{
+	  einfo (_("%F%P: can not allocate memory for CRC table: %E\n"));
+	  return;
+	}
+    }
+  for (bfd_vma i = 0 ; i < 256 ; i++)
+    {
+       lang_add_data (QUAD, exp_intop (crc64_tab[i]));
+    }
+}
+
 void
 lang_startup (const char *name)
 {
-- 
2.17.1

[PATCH v0 6/6] ldlang.c: Try to get the .text section for checking CRC

[binutils]

From: Ulf Samuelsson <binutils@emagii.com>

This fails to get the section:
  if ( bfd_get_section_contents (link_info.output_bfd,
	  ts,
	  text_section,
	  0,
	  ts->size))

Signed-off-by: Ulf Samuelsson <binutils@emagii.com>
---
 ld/ldlang.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 108 insertions(+)

diff --git a/ld/ldlang.c b/ld/ldlang.c
index e0bb079b34e..5d88e3aa9e5 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -6847,6 +6847,26 @@ lang_symbol_tweaks (void)
     }
 }
 
+static bool symbol_lookup(char *name, bfd_vma *val)
+{
+  struct bfd_link_hash_entry *h;
+  h = bfd_link_hash_lookup (link_info.hash, name,
+			    false, false, true);
+  if (h != NULL)
+    {
+      if ((h->type == bfd_link_hash_defined
+	  || h->type == bfd_link_hash_defweak)
+	 && h->u.def.section->output_section != NULL)
+	{
+	  *val = (h->u.def.value
+	     + bfd_section_vma (h->u.def.section->output_section)
+	     + h->u.def.section->output_offset);
+	  return true;
+	}
+    }
+    return false;
+}
+
 static void
 lang_end (void)
 {
@@ -6953,6 +6973,94 @@ lang_end (void)
 		   entry_symbol.name);
 	}
     }
+
+
+  /* Check if we can calculate CRC64 */
+  /* All of CRC_ADDRESS CRC_START CRC_END must be defined */
+  {
+    bfd_vma crc64, start, end;
+    bool can_do_crc;
+
+    can_do_crc = symbol_lookup(CRC_ADDRESS, &crc64) &&
+		 symbol_lookup(CRC_START, &start)   &&
+		 symbol_lookup(CRC_END, &end);
+    if (can_do_crc)
+      {
+	asection *ts;
+
+	ts = bfd_get_section_by_name (link_info.output_bfd, entry_section);
+	if (ts != NULL) {
+	  bfd_vma text_start = ts->lma;
+	  bfd_vma text_end   = ts->lma + ts->size;
+	  printf("%s: [0x%08lx .. 0x%08lx]\n",
+		ts->name,
+		text_start,
+		text_end);
+	  bool OK =
+	    ((text_start <= crc64) && (crc64 <= text_end)) &&
+	    ((text_start <= start) && (start <= text_end)) &&
+	    ((text_start <= end)   && (end   <= text_end));
+	  if (OK)
+	    {
+	      printf("All the memory to be CRC checked is in the text section\n");
+	       /* allocate twice the size, since we do not know what we are doing */
+	      bfd_vma *text_section = malloc(ts->size * 2);
+	      if (text_section != NULL)
+		{
+		  if ( bfd_get_section_contents (link_info.output_bfd,
+			  ts,
+			  text_section,
+			  0,
+			  ts->size))
+		    {
+		      for (bfd_vma i = 0 ; i < ts->size ; i+=4)
+			{
+			  printf("0x%08lx: 0x%08lx 0x%08lx 0x%08lx 0x%08lx\n",
+				ts->lma + i,
+				text_section[i+0],
+				text_section[i+1],
+				text_section[i+2],
+				text_section[i+3]);
+			}
+		    }
+		  else
+		    {
+		      printf("Could not fetch contents of %s\n", ts->name);
+		    }
+		  free(text_section);
+		}
+	    }
+	}
+	printf("%-20s = 0x%08lx\n",CRC_ADDRESS , crc64);
+	ts = bfd_get_linker_section (link_info.output_bfd, CRC_ADDRESS);
+	if (ts != NULL) {
+	  printf("%s: [0x%08lx .. 0x%08lx]\n",
+		ts->name,
+		ts->lma,
+		ts->lma + ts->size);
+	}
+	printf("%-20s = 0x%08lx\n",CRC_START , start);
+	ts = bfd_get_linker_section (link_info.output_bfd, CRC_START);
+	if (ts != NULL) {
+	  printf("%s: [0x%08lx .. 0x%08lx]\n",
+		ts->name,
+		ts->lma,
+		ts->lma + ts->size);
+	}
+	printf("%-20s = 0x%08lx\n",CRC_END , end);
+	ts = bfd_get_linker_section (link_info.output_bfd, CRC_END);
+	if (ts != NULL) {
+	  printf("%s: [0x%08lx .. 0x%08lx]\n",
+		ts->name,
+		ts->lma,
+		ts->lma + ts->size);
+	}
+      }
+    else
+      {
+	printf("%-20s not found\n", CRC_ADDRESS);
+      }
+  }
 }
 
 /* This is a small function used when we want to ignore errors from
-- 
2.17.1

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Fangrui Song]

On Thu, Feb 16, 2023 at 12:40 PM Ulf Samuelsson via Binutils
<binutils@sourceware.org> wrote:
>
> Cleaned up attempt to generate CRC64.
>
>
> Added code in lang_end() to calculate the CRC.
> So far, I can retrieve the location of the CRC
> and the start and end for the area.
> I can fetch the .text segment as an asection but
>
>   if ( bfd_get_section_contents (link_info.output_bfd,
>           ts,
>           text_section,
>           0,
>           ts->size))
>
> fails...
>
> The patchset should contain the LICENSE and the testsuite
> but git-send-email does not like if I send 8 patches.
> Sending 6 patches is OK for some reason...
>
> [PATCH v0 1/6] CRC64 header
> [PATCH v0 2/6] ldlang.h: CRC64
> [PATCH v0 3/6] ldlex.l: CRC64
> [PATCH v0 4/6] ldgram.y: CRC64
> [PATCH v0 5/6] ldlang.c: CRC64
> [PATCH v0 6/6] ldlang.c: Try to get the .text section for checking
>

Hi Ulf, can you state why a built-in support of ld is needed? If you
want to embed a checksum, you can use Output Section Data to reserve a
few bytes in the output, then use a post-link tool to compute the
checksum and rewrite the reserved bytes.

I am asking because I am unsure whether this feature is generic enough
to meet a majority of future users' needs. We can reasonably expect
that other users may want to use different message digest
algorithms...

Cheers

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Ulf Samuelsson]

Den 2023-02-16 kl. 22:30, skrev Fangrui Song:
> On Thu, Feb 16, 2023 at 12:40 PM Ulf Samuelsson via Binutils
> <binutils@sourceware.org> wrote:
>> Cleaned up attempt to generate CRC64.
>>
>>
>> Added code in lang_end() to calculate the CRC.
>> So far, I can retrieve the location of the CRC
>> and the start and end for the area.
>> I can fetch the .text segment as an asection but
>>
>>    if ( bfd_get_section_contents (link_info.output_bfd,
>>            ts,
>>            text_section,
>>            0,
>>            ts->size))
>>
>> fails...
>>
>> The patchset should contain the LICENSE and the testsuite
>> but git-send-email does not like if I send 8 patches.
>> Sending 6 patches is OK for some reason...
>>
>> [PATCH v0 1/6] CRC64 header
>> [PATCH v0 2/6] ldlang.h: CRC64
>> [PATCH v0 3/6] ldlex.l: CRC64
>> [PATCH v0 4/6] ldgram.y: CRC64
>> [PATCH v0 5/6] ldlang.c: CRC64
>> [PATCH v0 6/6] ldlang.c: Try to get the .text section for checking
>>
> Hi Ulf, can you state why a built-in support of ld is needed? If you
> want to embed a checksum, you can use Output Section Data to reserve a
> few bytes in the output, then use a post-link tool to compute the
> checksum and rewrite the reserved bytes.

Yes, this is what I have been doing so far, and I am not happy about it.

In my experience, the post link tools usually work on the binary data 
and not the ELF file.
The IAR ielftool that I ported is an exception, but it is not 100% 
compatible with the result of the GNU linker.

That means that you cannot load the ELF file into a debugger and run,
because you do not have the CRC in the ELF file, only in the 
binary/hex-file.

Another thing is that the post-link tools I have seen are typically 
poorly maintained.

Adding a post-link step seems like a kludge if the linker can provide 
the CRC inside the ELF file.

> I am asking because I am unsure whether this feature is generic enough
> to meet a majority of future users' needs. We can reasonably expect
> that other users may want to use different message digest
> algorithms...

The feature allows a CRC-64 to be generated using either ECMA, ISO or a 
user defined polynom.
This means that you cannot make a more generic CRC-64.

The only projects I can see that would need anything else are 8 bit 
micros with a few kB of flash.
They could use a CRC-32 and may trade off speed for code size using a 
non-table driven version.

Adding this functionality does not mean that a user have to use it.
They can continue to use a post-link tool to create CRC64 or any other CRC.
If they want something else, they can do that as well.

For those that do want CRC64, this simplifes things a lot.

> Cheers

Best Regards
Ulf Samuelsson

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Nick Clifton]

Hi Ulf,

>> Hi Ulf, can you state why a built-in support of ld is needed? If you
>> want to embed a checksum, you can use Output Section Data to reserve a
>> few bytes in the output, then use a post-link tool to compute the
>> checksum and rewrite the reserved bytes.

> In my experience, the post link tools usually work on the binary data and not the ELF file.

The objcopy program can do most of this for you though.  For example:

   % objcopy --dump-section .text=contents-of-text a.out
   % crc32 contents-of-text > crc32-of-text
   % objcopy --add-section .crc32=crc32-of-text a.out
   % readelf -x.crc32 a.out
   Hex dump of section '.crc32':
     0x00000000 32323064 37636339 0a                220d7cc9.

In this example the crc32 is stored as ascii text, but I am sure that
you can find a version of the crc32 program that generates binary output.


> Another thing is that the post-link tools I have seen are typically poorly maintained.

...and so you want to move that maintainership burden onto us, yes ?


> Adding a post-link step seems like a kludge if the linker can provide the CRC inside the ELF file.

But it also keeps things simple.  No new code in the linker = no new
bugs in the linker.  Solving a problem using existing tools = no need
for new versions of the linker when the already existing versions will
work just fine.

Cheers
   Nick

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Ulf Samuelsson]

Den 2023-02-17 kl. 12:11, skrev Nick Clifton:
> Hi Ulf,
>
>>> Hi Ulf, can you state why a built-in support of ld is needed? If you
>>> want to embed a checksum, you can use Output Section Data to reserve a
>>> few bytes in the output, then use a post-link tool to compute the
>>> checksum and rewrite the reserved bytes.
>
>> In my experience, the post link tools usually work on the binary data 
>> and not the ELF file.
>
> The objcopy program can do most of this for you though.  For example:
>
>   % objcopy --dump-section .text=contents-of-text a.out
>   % crc32 contents-of-text > crc32-of-text
>   % objcopy --add-section .crc32=crc32-of-text a.out
>   % readelf -x.crc32 a.out
>   Hex dump of section '.crc32':
>     0x00000000 32323064 37636339 0a                220d7cc9.
>
> In this example the crc32 is stored as ascii text, but I am sure that
> you can find a version of the crc32 program that generates binary output.

The crc32 generates a 32-bit CRC. Modern microcontrollers require a 
64-bit CRC.

The second problem is: where is the .crc32 section and its contents?
The program needs to access the contents, but it is already linked.
The typical use is a header in front of the program, and the header
is part of the ".text" area.
Can you explain how this would work?

>
>
>> Another thing is that the post-link tools I have seen are typically 
>> poorly maintained.
>
> ...and so you want to move that maintainership burden onto us, yes ?

The problem with the post-link tools is that they are hard wired to work on
special use cased.
Example of problems

* CRC is fixed to be at a certain address

* CRC table is fixed to be at a certain address.

* Works on binaries and not on ELF files

* You have to have one postprocessor for each file format.

None of these problems affect the linker since it is agnostic on the 
file format
as long as there is a ".text" section.

The CRC calculation has been stable on www.libcrc.com for 7 years.
There is no reason for the CRC calculation to change.
The only chance I can see is a different polynom, but that is already 
supported.

The biggest problem is of course that it slows down the debugging
because you cannot download from an ELF file - it lacks the CRC.

>
>
>> Adding a post-link step seems like a kludge if the linker can provide 
>> the CRC inside the ELF file.
>
> But it also keeps things simple.  No new code in the linker = no new
> bugs in the linker.  Solving a problem using existing tools = no need
> for new versions of the linker when the already existing versions will
> work just fine.

The problem is that the existing versions *barely* work.
Every company have to write their own solution.
It does not support source level debugging.

Supporting it in the linker makes for a much cleaner solution.

>
> Cheers
>   Nick
>
Best Regards

Ulf Samuelsson

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Fangrui Song]

On Fri, Feb 17, 2023 at 4:03 AM Ulf Samuelsson <binutils@emagii.com> wrote:
>
>
> Den 2023-02-17 kl. 12:11, skrev Nick Clifton:
> > Hi Ulf,
> >
> >>> Hi Ulf, can you state why a built-in support of ld is needed? If you
> >>> want to embed a checksum, you can use Output Section Data to reserve a
> >>> few bytes in the output, then use a post-link tool to compute the
> >>> checksum and rewrite the reserved bytes.
> >
> >> In my experience, the post link tools usually work on the binary data
> >> and not the ELF file.
> >
> > The objcopy program can do most of this for you though.  For example:
> >
> >   % objcopy --dump-section .text=contents-of-text a.out
> >   % crc32 contents-of-text > crc32-of-text
> >   % objcopy --add-section .crc32=crc32-of-text a.out
> >   % readelf -x.crc32 a.out
> >   Hex dump of section '.crc32':
> >     0x00000000 32323064 37636339 0a                220d7cc9.
> >
> > In this example the crc32 is stored as ascii text, but I am sure that
> > you can find a version of the crc32 program that generates binary output.
>
> The crc32 generates a 32-bit CRC. Modern microcontrollers require a
> 64-bit CRC.
>
> The second problem is: where is the .crc32 section and its contents?
> The program needs to access the contents, but it is already linked.
> The typical use is a header in front of the program, and the header
> is part of the ".text" area.
> Can you explain how this would work?
>
> >
> >
> >> Another thing is that the post-link tools I have seen are typically
> >> poorly maintained.
> >
> > ...and so you want to move that maintainership burden onto us, yes ?
>
> The problem with the post-link tools is that they are hard wired to work on
> special use cased.
> Example of problems
>
> * CRC is fixed to be at a certain address
>
> * CRC table is fixed to be at a certain address.
>
> * Works on binaries and not on ELF files
>
> * You have to have one postprocessor for each file format.

Hi Ulf, I think a natural question from other binutils contributors
is: why is the CRC-64 feature so special that it deserves several
keywords dedicated for it in the linker script language.
You can place placeholder content into the CRC-64 section (say, it is
.crc64), compute its value with a post-link program, then update the
content with
objcopy --update-section .crc64=.... exe

If objcopy --update-section somehow doesn't achieve your goal, it may
be worth a feature request or bug, since the operation is generic and
useful for a large number of users, not just your CRC-64 customers.

> None of these problems affect the linker since it is agnostic on the
> file format
> as long as there is a ".text" section.
>
> The CRC calculation has been stable on www.libcrc.com for 7 years.
> There is no reason for the CRC calculation to change.
> The only chance I can see is a different polynom, but that is already
> supported.
>
> The biggest problem is of course that it slows down the debugging
> because you cannot download from an ELF file - it lacks the CRC.

I am unsure how a linker script extension is more convenient than
using the existing functionality plus a CRC64 calculator and objcopy.
The linker script extension appears to add a lot of code to the linker
script language, which is already quite challenging to maintain.

If you distribute such object files with CRC64, I don't think it harms
debuggability.

> >
> >
> >> Adding a post-link step seems like a kludge if the linker can provide
> >> the CRC inside the ELF file.
> >
> > But it also keeps things simple.  No new code in the linker = no new
> > bugs in the linker.  Solving a problem using existing tools = no need
> > for new versions of the linker when the already existing versions will
> > work just fine.
>
> The problem is that the existing versions *barely* work.
> Every company have to write their own solution.
> It does not support source level debugging.
>
> Supporting it in the linker makes for a much cleaner solution.
>
> >
> > Cheers
> >   Nick
> >
> Best Regards
>
> Ulf Samuelsson
>
>

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Ulf Samuelsson]

On 2023-03-06 08:50, Fangrui Song wrote:
> On Fri, Feb 17, 2023 at 4:03 AM Ulf Samuelsson <binutils@emagii.com> wrote:
>>
>> Den 2023-02-17 kl. 12:11, skrev Nick Clifton:
>>> Hi Ulf,
>>>
>>>>> Hi Ulf, can you state why a built-in support of ld is needed? If you
>>>>> want to embed a checksum, you can use Output Section Data to reserve a
>>>>> few bytes in the output, then use a post-link tool to compute the
>>>>> checksum and rewrite the reserved bytes.
>>>> In my experience, the post link tools usually work on the binary data
>>>> and not the ELF file.
>>> The objcopy program can do most of this for you though.  For example:
>>>
>>>    % objcopy --dump-section .text=contents-of-text a.out
>>>    % crc32 contents-of-text > crc32-of-text
>>>    % objcopy --add-section .crc32=crc32-of-text a.out
>>>    % readelf -x.crc32 a.out
>>>    Hex dump of section '.crc32':
>>>      0x00000000 32323064 37636339 0a                220d7cc9.
>>>
>>> In this example the crc32 is stored as ascii text, but I am sure that
>>> you can find a version of the crc32 program that generates binary output.
>> The crc32 generates a 32-bit CRC. Modern microcontrollers require a
>> 64-bit CRC.
>>
>> The second problem is: where is the .crc32 section and its contents?
>> The program needs to access the contents, but it is already linked.
>> The typical use is a header in front of the program, and the header
>> is part of the ".text" area.
>> Can you explain how this would work?
>>
>>>
>>>> Another thing is that the post-link tools I have seen are typically
>>>> poorly maintained.
>>> ...and so you want to move that maintainership burden onto us, yes ?
>> The problem with the post-link tools is that they are hard wired to work on
>> special use cased.
>> Example of problems
>>
>> * CRC is fixed to be at a certain address
>>
>> * CRC table is fixed to be at a certain address.
>>
>> * Works on binaries and not on ELF files
>>
>> * You have to have one postprocessor for each file format.
> Hi Ulf, I think a natural question from other binutils contributors
> is: why is the CRC-64 feature so special that it deserves several
> keywords dedicated for it in the linker script language.
> You can place placeholder content into the CRC-64 section (say, it is
> .crc64), compute its value with a post-link program, then update the
> content with
> objcopy --update-section .crc64=.... exe

If you look at the latest patchset (v11),
you will find that there is no "CRC-64" keyword.
It is replaced by the "DIGEST" keyword which takes a string parameter
describing a "known" algorithm, or the POLY keyword
which allows you to specify your own algorithm.

If someone wants to support additional algorithms like the SHA series
it is esaily extended.

> If objcopy --update-section somehow doesn't achieve your goal, it may
> be worth a feature request or bug, since the operation is generic and
> useful for a large number of users, not just your CRC-64 customers.
The problems with supporting things in an external application
is that you need an application for every conceivable object file format.

The ielftools that I have used for this is 11-12000 lines of code of 
non-trivial code.

I do not not know just how many file format are supported but to me, it 
appears
to be at least a dozen.

There is no standard for such a tool, so you will find that many companies
need to maintain their own tool for this very purpose.

The next problem is that the "crc32" application is really only good for 
very
small microcontrollers with a few kB of flash. In order to support the 
128kB-MBs
of flash available in modern microcontrollers you need a 64 bit CRC.

There is no standard application that generates CRC-64.
That means someone needs to write an application that is allows standard
polynomes as well as custom polynomes.

Since the problem is difficult, many resort to just updating the binary,

which means that the code is not easily debuggable.
You cannot load the ELF file into the debugger and run, because it does
not have the checksum.

This patchset really allows people worldwide to get rid of millions
of lines of code that no longer is needed.

=====

The alternative I am proposing is straightforward code

The core code, doing the CRC calculation is well known.
The libcrc has not changed in 7 years.

>> None of these problems affect the linker since it is agnostic on the
>> file format
>> as long as there is a ".text" section.
>>
>> The CRC calculation has been stable on www.libcrc.com for 7 years.
>> There is no reason for the CRC calculation to change.
>> The only chance I can see is a different polynom, but that is already
>> supported.
>>
>> The biggest problem is of course that it slows down the debugging
>> because you cannot download from an ELF file - it lacks the CRC.
> I am unsure how a linker script extension is more convenient than
> using the existing functionality plus a CRC64 calculator and objcopy.
> The linker script extension appears to add a lot of code to the linker
> script language, which is already quite challenging to maintain.

It supports all object file formats and all architectures immediately.
It replaces millions of lines of code.

Your solution requires that the process knows which section contains the 
CRC.
If someone moves the CRC to a different section, your toolchain is broken.

The crc32 application computes the crc of all the .text section, so it 
cannot be used.
but you need to calculate the checsum of only part of the selected section.

You also need to insert the checksum at a user selectable part of the 
section.

On top of that, not having to postprocess the object code simplifies the 
flow.

So objcopy and crc32 does not meet the requirements as of today.

KEYWORDS.

Right now it adds the following keywords "DIGEST", "TABLE", "POLY".

In addition the patch has two more features.

* Debugging feature adding "DEBUG", "ON", "OFF"

* timestamp feature adding "TIMESTAMP"

> If you distribute such object files with CRC64, I don't think it harms
> debuggability.

There is no CRC64 application, and even if it was, it is a fragile solution,
because there is no automatic information on where to put the checksum
and what area to calculate the checksum on.

Adding checksum calculations to the linker is converting a very
difficult problem into a really simple one.

If you were managing a team to decide where to put the CRC calculation
the linker is the obvious place to look at.

Best Regards
Ulf Samuelsson

>
>>>
>>>> Adding a post-link step seems like a kludge if the linker can provide
>>>> the CRC inside the ELF file.
>>> But it also keeps things simple.  No new code in the linker = no new
>>> bugs in the linker.  Solving a problem using existing tools = no need
>>> for new versions of the linker when the already existing versions will
>>> work just fine.
>> The problem is that the existing versions *barely* work.
>> Every company have to write their own solution.
>> It does not support source level debugging.
>>
>> Supporting it in the linker makes for a much cleaner solution.
>>
>>> Cheers
>>>    Nick
>>>
>> Best Regards
>>
>> Ulf Samuelsson
>>
>>

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Ulf Samuelsson]

[-- Attachment #1: Type: text/plain, Size: 1760 bytes --]


Den 2023-02-16 kl. 21:40, skrev Ulf Samuelsson via Binutils:
> Cleaned up attempt to generate CRC64.
>
>
> Added code in lang_end() to calculate the CRC.
> So far, I can retrieve the location of the CRC
> and the start and end for the area.
> I can fetch the .text segment as an asection but
>   
>    if ( bfd_get_section_contents (link_info.output_bfd,
> 	  ts,
> 	  text_section,
> 	  0,
> 	  ts->size))
>
> fails...
>
> The patchset should contain the LICENSE and the testsuite
> but git-send-email does not like if I send 8 patches.
> Sending 6 patches is OK for some reason...
>
> [PATCH v0 1/6] CRC64 header
> [PATCH v0 2/6] ldlang.h: CRC64
> [PATCH v0 3/6] ldlex.l: CRC64
> [PATCH v0 4/6] ldgram.y: CRC64
> [PATCH v0 5/6] ldlang.c: CRC64
> [PATCH v0 6/6] ldlang.c: Try to get the .text section for checking
>
gcc -c crc.s
../bin/bin/ld -T crc.t -o crc crc.o
Adding Syndrome: 0x42f0e1eba9ea3693
Adding Syndrome: 0xd800000000000000
../bin/bin/ld:crc.t:18: warning: CRC polynome declared twice (ignored)
.text: [0x00001100 .. 0x00002810]
bfd_malloc_and_get_section succeeded

Before CRC:
0x00001100: 0xefbeadde45444f43 0x0000000000000000 0x0000000000000000 
0x0000000000001118

*CRC [0xc79d3a1ef51fb737] update at 0x00001110 succeeded*

After CRC:
0x00001100: 0xefbeadde45444f43 0x0000000000000000 0xc79d3a1ef51fb737 
0x0000000000001118

Full Section After CRC:
0x00001100: 0xefbeadde45444f43 0x0000000000000000 0xc79d3a1ef51fb737 
0x0000000000001118
0x00001140: 0xffffffffffffffff 0xffffffffffffffff 0xffffffffffffffff 
0xffffffffffffffff
0x00001180: 0xffffffffffffffff 0xffffffffffffffff 0xffffffffffffffff 
0xffffffffffffffff
0x000011c0: 0xffffffffffffffff 0xffffffffffffffff 0xffffffffffffffff 
0xffffffffffffffff

:-)

Best Regards
Ulf Samuelsson

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Nick Clifton]

Hi Ulf,

> Before CRC:
> 0x00001100: 0xefbeadde45444f43 0x0000000000000000 0x0000000000000000 0x0000000000001118
> 
> *CRC [0xc79d3a1ef51fb737] update at 0x00001110 succeeded*
> 
> After CRC:
> 0x00001100: 0xefbeadde45444f43 0x0000000000000000 0xc79d3a1ef51fb737 0x0000000000001118

Sorry - I am a little confused here.  Does this mean that your v0
patch set is working ?  I was going to suggest that the reason that
calling bfd_get_section_contents() does not work, is that it is being
called too early - before the contents have actually been assigned.

I am also concerned that your patch includes copyrighted code that
appears to come without any license attached.  (Maybe it is in the
LICENSE file that you say you could not upload ?)

Also - from a flexibility point of view - wouldn't it be better if
the CRC were to be computed by an external program, rather than being
built into the linker ?  That way the user could decide exactly which
digest algorithm they wanted to use.  I am pretty sure that you can
arrange for the patch to fork/exec another program to compute the
CRC for you.

Cheers
   Nick

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Nick Clifton]

Hi Guys,

>> Cleaned up attempt to generate CRC64.

> I am asking because I am unsure whether this feature is generic enough
> to meet a majority of future users' needs. We can reasonably expect
> that other users may want to use different message digest
> algorithms...

I tend to agree with Fanguri here.  To me this seems like a situation where
using a linker plugin might be the way to go.  You could have different
plugins for different digest algorithms, and keeping the code separate from
the linker means that, if desired, the feature can be maintained and developed
without regard to the binutils release schedule.

Cheers
   Nick

[RFC v0 0/1] Add support for CRC64 generation in linker

[binutils]

Here is the first draft of introducing CRC64 generation in the linker

So far it
* reserves room for the CRC (8 bytes)
* Declares a symbol ___CRC64___ for the address of the CRC.
* Allows specifying the polynom (ECMA, ISO or your own)
* Allows for inversion in the CRC calculation (CRC64-WE)
* Allows specifying the area that should be checked.
* Declares the symbol "___CRC64_START__" for the beginning
* Declares the symbol "___CRC64_END__"   for the end (not included)
* Creates a 2kB table which speeds up the CRC calculation
* Can insert the 2kB table into the .text section

It does not yet calculate the CRC of the specified area.
I need to figure out how to access the section(s) covered
for calculating the CRC (between ___CRC64_START___ and ___CRC64_END___)
and then insert the calculated CRC at ___CRC64___ before
the output is generated.

[PATCH v0 1/1] [RFC] Add support for CRC64 generation in linker

Re: [RFC v0 0/1] Add support for CRC64 generation in linker

[Ulf Samuelsson]

Den 2023-02-16 kl. 14:19, skrev Ulf Samuelsson via Binutils:
> Here is the first draft of introducing CRC64 generation in the linker
>
> So far it
> * reserves room for the CRC (8 bytes)
> * Declares a symbol ___CRC64___ for the address of the CRC.
> * Allows specifying the polynom (ECMA, ISO or your own)
> * Allows for inversion in the CRC calculation (CRC64-WE)
> * Allows specifying the area that should be checked.
> * Declares the symbol "___CRC64_START__" for the beginning
> * Declares the symbol "___CRC64_END__"   for the end (not included)
> * Creates a 2kB table which speeds up the CRC calculation
> * Can insert the 2kB table into the .text section
>
> It does not yet calculate the CRC of the specified area.
> I need to figure out how to access the section(s) covered
> for calculating the CRC (between ___CRC64_START___ and ___CRC64_END___)
> and then insert the calculated CRC at ___CRC64___ before
> the output is generated.
>
> [PATCH v0 1/1] [RFC] Add support for CRC64 generation in linker

Some of the formatting is off as well.

Best Regards
Ulf Samuelsson