[patch/rfc] implement memmem() locally in kallsyms.c

[patch/rfc] implement memmem() locally in kallsyms.c

[Mike Frysinger]

This patch basically copies the gnulib version of memmem() into
scripts/kallsyms.c.  While a useful function, it isn't in POSIX so some
systems (like Darwin) choose to omit it.  How do others feel ?

Signed-off-by: Mike Frysinger <vapier@gentoo.org>
---
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -26,8 +26,6 @@
  *
  */
 
-#define _GNU_SOURCE
-
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -56,6 +54,37 @@ int token_profit[0x10000];
 unsigned char best_table[256][2];
 unsigned char best_table_len[256];
 
+/* memmem(), while useful, is not in POSIX, so create a local version
+ * so we can compile on non-GNU systems (Darwin, *BSD, etc...)
+ */
+void *memmem(const void *haystack, size_t haystack_len,
+             const void *needle, size_t needle_len)
+{
+	const char *begin;
+	const char *const last_possible =
+		(const char *)haystack + haystack_len - needle_len;
+
+	/* The first occurrence of the empty string is deemed to occur at
+	 * the beginning of the string.
+	 */
+	if (needle_len == 0)
+		return (void *)haystack;
+
+	/* Sanity check, otherwise the loop might search through the whole
+	 * memory.
+	 */
+	if (haystack_len < needle_len)
+		return NULL;
+
+	for (begin = (const char *)haystack; begin <= last_possible; ++begin)
+		if (begin[0] == ((const char *)needle)[0] &&
+		    !memcmp((const void *)&begin[1],
+		            (const void *)((const char *)needle + 1),
+		            needle_len - 1))
+			return (void *)begin;
+
+	return NULL;
+}
 
 static void usage(void)
 {

Re: [patch/rfc] implement memmem() locally in kallsyms.c

[Jesper Juhl]

On 07/06/07, Mike Frysinger <vapier@gentoo.org> wrote:
> This patch basically copies the gnulib version of memmem() into
> scripts/kallsyms.c.  While a useful function, it isn't in POSIX so some
> systems (like Darwin) choose to omit it.  How do others feel ?
>

Do people actually build Linux kernels on Darwin & *BSD systems? If
they do then why?

What I'm getting at is; why do we care if it will build there?

-- 
Jesper Juhl <jesper.juhl@gmail.com>
Don't top-post  http://www.catb.org/~esr/jargon/html/T/top-post.html
Plain text mails only, please      http://www.expita.com/nomime.html

Re: [patch/rfc] implement memmem() locally in kallsyms.c

[Mike Frysinger]

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

On Thursday 07 June 2007, Jesper Juhl wrote:
> On 07/06/07, Mike Frysinger <vapier@gentoo.org> wrote:
> > This patch basically copies the gnulib version of memmem() into
> > scripts/kallsyms.c.  While a useful function, it isn't in POSIX so some
> > systems (like Darwin) choose to omit it.  How do others feel ?
>
> Do people actually build Linux kernels on Darwin & *BSD systems? If
> they do then why?

in the embedded world,  yes ... everything is being cross-compiled and 
deployed on different hardware anyways, so the build env shouldnt matter

> What I'm getting at is; why do we care if it will build there?

that was the [rfc] part of the e-mail ... i got enough complaints from people 
OS X people to put together the patch
-mike

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 827 bytes --]

Re: [patch/rfc] implement memmem() locally in kallsyms.c

[Paulo Marques]

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

Mike Frysinger wrote:
> This patch basically copies the gnulib version of memmem() into
> scripts/kallsyms.c.  While a useful function, it isn't in POSIX so some
> systems (like Darwin) choose to omit it.  How do others feel ?

Well, the only use of memmem in scripts/kallsyms.c is to find tokens of 
size 2, so we can use a simplified version instead (and probably get 
better code in the process).

How about the attached patch instead?

If you approve it, I'll post it appropriately for inclusion in -mm.

-- 
Paulo Marques - www.grupopie.com

"God is real, unless declared integer."

[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 1082 bytes --]

--- ./scripts/kallsyms.c.orig	2007-06-08 12:55:49.000000000 +0100
+++ ./scripts/kallsyms.c	2007-06-08 13:19:52.000000000 +0100
@@ -378,6 +378,17 @@ static void build_initial_tok_table(void
 	table_cnt = pos;
 }
 
+static void *find_token(unsigned char *str, int len, unsigned char *token)
+{
+	int i;
+
+	for (i = 0; i < len - 1; i++) {
+		if (str[i] == token[0] && str[i+1] == token[1])
+			return &str[i];
+	}
+	return NULL;
+}
+
 /* replace a given token in all the valid symbols. Use the sampled symbols
  * to update the counts */
 static void compress_symbols(unsigned char *str, int idx)
@@ -391,7 +402,7 @@ static void compress_symbols(unsigned ch
 		p1 = table[i].sym;
 
 		/* find the token on the symbol */
-		p2 = memmem(p1, len, str, 2);
+		p2 = find_token(p1, len, str);
 		if (!p2) continue;
 
 		/* decrease the counts for this symbol's tokens */
@@ -410,7 +421,7 @@ static void compress_symbols(unsigned ch
 			if (size < 2) break;
 
 			/* find the token on the symbol */
-			p2 = memmem(p1, size, str, 2);
+			p2 = find_token(p1, size, str);
 
 		} while (p2);