[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[Graeme Russ]

Hello All,

This patch is a little heads-up for my upcomming INIT_FUNC patch series

This is the INIT_FUNC 'engine' - It processes a file which consists of
entries created by the following macros:

#define INIT_FUNC(fn, init_name, man_reqs, pre_reqs, post_reqs) \
	static const char __init_func_ ## fn[] __used \
	__attribute__((__section__(".initfuncs"))) = \
	"(f:" #fn ":" #init_name ":" #man_reqs " | " #pre_reqs " | " #post_reqs ")\n";

#define SKIP_INIT(init_name) \
	static const char __skip_init_ ## req[] __used \
	__attribute__((__section__(".initfuncs"))) = \
	"(s:" #init_name ")\n";

#define REPLACE_INIT(old_func, new_func) \
	static const char __replace_init_ ## old_func[] __used \
	__attribute__((__section__(".initfuncs"))) = \
	"(r:" #old_func ":" #new_func ")\n";

So an 'function' entry will look like
(f:function_name:init_step:mandatory_req_1 mandatory_req_2 | optional_req_1 optional_req_2 | post_req_1 post_req_2)

'init_step' allows multiple functions to be logically grouped (see below)

where:

mandatory_req_1 & mandatory_req_2 are functions or 'init steps' which MUST
exist and will be put  in the init sequence before 'function_name'

optional_req_1 & optional_req_2 are functions or 'init steps' which might
exist and (if they do) will be put in the init sequence before
'function_name'

post_req_1 & post_req_2 are are functions or 'init steps' which might
exist and (if they do) will be put  in the init sequence after
'function_name'

A 'skip' entry will look like:
(s:function_or_step_name)

The function named 'function_or_step_name' will not be included in the
init sequence. If 'function_or_step_name' is the name of a 'step' then
all functions which make up that step are skipped - This is to replace
a arch-level function (or set of functions) with board specific
alternatives.

A 'replace' entry will look like:
(r:old_name:new_name)

Any function named 'old_name' in the init sequence will be replaced with
'new_name' (this is like overriding a weak function without needing to
make the function weak)

So far this seems to work - It creates a list of functions with each
having a list of dependent functions (steps are expanded so the dependency
lists only have functions in them)

Now I just need to write the code that will order the function list

I think this single patch will more than double the use of struct list_head
in U-Boot. It took a while to get used to it's sematics, but the Linux
kernel list data structure is incredible

Regards,

Graeme

commit 1567e349f774d93e25b3ab2da01cab5e11632916
Author: Graeme Russ <graeme.russ@gmail.com>
Date:   Sun Apr 8 22:09:42 2012 +1000

    initcall: Some testing

diff --git a/tools/mkinitseq.c b/tools/mkinitseq.c
new file mode 100644
index 0000000..1e2bbb2
--- /dev/null
+++ b/tools/mkinitseq.c
@@ -0,0 +1,870 @@
+/*
+ * (C) Copyright 2012
+ * Graeme Russ <graeme.russ@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ * MA 02111-1307 USA
+ */
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ */
+#define container_of(ptr, type, member) ({			\
+	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+
+
+#include "os_support.h"
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <time.h>
+#include <unistd.h>
+#include <linux/list.h>
+#include <malloc.h>
+
+#undef MKINITSEQ_DEBUG
+
+#ifdef MKINITSEQ_DEBUG
+#define debug(fmt,args...)	printf (fmt ,##args)
+#else
+#define debug(fmt,args...)
+#endif /* MKINITSEQ_DEBUG */
+
+#include <version.h>
+
+struct init_id {
+	struct list_head list;
+	char *name;
+};
+
+struct replace_def {
+	struct list_head list;
+	char *old_name;
+	char *new_name;
+};
+
+struct init_function {
+	struct list_head list;
+
+	char *function_name;
+	char *init_step_name;
+
+	struct list_head mandatory_deps;
+	struct list_head pre_deps;
+	struct list_head post_deps;
+};
+
+struct init_step {
+	struct list_head list;
+
+	char *name;
+
+	struct list_head functions;
+};
+
+struct list_head init_functions;
+struct list_head mandatory_functions;
+struct list_head skip_list;
+struct list_head replace_list;
+struct list_head init_steps;
+
+/* These are the initialisation sequence placeholders */
+static char default_init_reset[] = "f:RESET:RESET: |  | SDRAM";
+static char default_init_sdram[] = "f:SDRAM:SDRAM: RESET |  | RELOC";
+static char default_init_reloc[] = "f:RELOC:RELOC: SDRAM |  | ";
+
+static int add_function_to_init_step(struct init_step *init_step,
+				     const char *function_name)
+{
+	struct init_id *init_id;
+
+	init_id = malloc(sizeof(struct init_id));
+
+	if (!init_id)
+		return ENOMEM;
+
+	init_id->name = strdup(function_name);
+
+	if (!init_id->name) {
+		free(init_id);
+		return ENOMEM;
+	}
+
+	list_add(&init_id->list, &init_step->functions);
+
+	return 0;
+}
+
+static int add_init_step_function(const char *init_step_name,
+				  const char *function_name)
+{
+	int found = 0;
+	struct list_head *position = NULL ;
+	struct init_step *init_step = NULL ;
+
+
+	list_for_each(position, &init_steps)
+	{
+		init_step = list_entry(position, struct init_step, list);
+
+		if (!strcmp(init_step->name, init_step_name)) {
+			found = 1;
+			break;
+		}
+	}
+
+	if (!found) {
+		init_step = malloc(sizeof(struct init_step));
+
+		if (!init_step)
+			return ENOMEM;
+
+		init_step->name = strdup(init_step_name);
+
+		if (!init_step->name) {
+			free(init_step);
+			return ENOMEM;
+		}
+
+		INIT_LIST_HEAD(&init_step->functions);
+		list_add(&init_step->list, &init_steps);
+	}
+
+	return add_function_to_init_step(init_step, function_name);
+
+}
+
+static int add_mandatory_init(const char *name)
+{
+	struct list_head *position = NULL ;
+	struct init_id *init_id = NULL ;
+
+	list_for_each(position, &mandatory_functions)
+	{
+		init_id = list_entry(position, struct init_id, list);
+
+		if (!strcmp(init_id->name, name))
+			return 0;
+	}
+
+	init_id = malloc(sizeof(struct init_id));
+
+	if (!init_id)
+		return ENOMEM;
+
+	init_id->name = strdup(name);
+
+	if (!init_id->name) {
+		free(init_id);
+		return ENOMEM;
+	}
+
+	list_add(&init_id->list, &mandatory_functions);
+
+	return 0;
+}
+
+static int process_dep_list(struct list_head *dep_list, char *deps, int mandatory)
+{
+	int err = 0;
+	struct init_id *new_init_id;
+	char *save_ptr;
+
+	char *init_id;
+
+	init_id = strtok_r(deps, " ", &save_ptr);
+
+	while (init_id) {
+		new_init_id = malloc(sizeof(struct init_id));
+
+		if (!new_init_id)
+			return ENOMEM;
+
+		new_init_id->name = strdup(init_id);
+
+		if (!new_init_id->name) {
+			free(new_init_id);
+			return ENOMEM;
+		}
+
+		list_add(&new_init_id->list, dep_list);
+
+		if (mandatory)
+			if (add_mandatory_init(init_id))
+				err = 1;
+
+		init_id = strtok_r(NULL, " ", &save_ptr);
+	};
+
+	return err;
+}
+
+static int process_init_info(struct init_function *init_function, char *deps)
+{
+	char *mandatory_deps;
+	char *pre_deps;
+	char *post_deps;
+	char *save_ptr;
+
+	INIT_LIST_HEAD(&init_function->mandatory_deps);
+	INIT_LIST_HEAD(&init_function->pre_deps);
+	INIT_LIST_HEAD(&init_function->post_deps);
+
+	mandatory_deps = strtok_r(deps, "|", &save_ptr);
+	pre_deps = strtok_r(NULL, "|", &save_ptr);
+	post_deps = strtok_r(NULL, "|", &save_ptr);
+
+	process_dep_list(&init_function->mandatory_deps, mandatory_deps, 1);
+	process_dep_list(&init_function->pre_deps, pre_deps, 0);
+	process_dep_list(&init_function->post_deps, post_deps, 0);
+
+	return 0;
+}
+
+static int check_for_duplicate_function(const char *function_name)
+{
+	struct list_head *position = NULL;
+	struct init_function *init_func = NULL;
+
+	list_for_each(position , &init_functions)
+	{
+		init_func = list_entry(position, struct init_function, list);
+
+		if (!strcmp(function_name, init_func->function_name)) {
+			printf("Duplicate init function: %s\n", function_name);
+
+			return EEXIST;
+		}
+	}
+
+	return 0;
+}
+
+static int add_to_skip_list(const char *function_name)
+{
+	struct list_head *position = NULL;
+	struct init_id *init_id = NULL;
+
+	/* Duplicate skip definitions are OK, but we only want the fist one */
+	list_for_each(position , &skip_list)
+	{
+		init_id = list_entry(position, struct init_id, list);
+
+		if (!strcmp(function_name, init_id->name))
+			return 0;
+	}
+
+	init_id = malloc(sizeof(struct init_id));
+
+	if (!init_id)
+		return ENOMEM;
+
+	init_id->name = strdup(function_name);
+
+	if (!init_id->name) {
+		free(init_id);
+		return ENOMEM;
+	}
+
+	list_add(&init_id->list, &skip_list);
+
+	return 0;
+}
+
+static int add_to_replace_list(const char *old_name, const char *new_name)
+{
+	struct list_head *position = NULL;
+	struct replace_def *replace_def = NULL;
+
+	/* Duplicate replace definitions are not OK */
+	list_for_each(position , &replace_list)
+	{
+		replace_def = list_entry(position, struct replace_def, list);
+
+		if (!strcmp(old_name, replace_def->old_name) ||
+		    !strcmp(old_name, replace_def->new_name) ||
+		    !strcmp(new_name, replace_def->old_name) ||
+		    !strcmp(new_name, replace_def->new_name)) {
+			printf("Multiple replace definitions for function: %s\n",
+			       old_name);
+
+			return EEXIST;
+		}
+	}
+
+	replace_def = malloc(sizeof(struct replace_def));
+
+	if (!replace_def)
+		return ENOMEM;
+
+	replace_def->old_name = strdup(old_name);
+	replace_def->new_name = strdup(new_name);
+
+	if ((!replace_def->old_name) || (!replace_def->new_name)) {
+		free(replace_def->old_name);
+		free(replace_def->new_name);
+		free(replace_def);
+		return ENOMEM;
+	}
+
+	list_add(&replace_def->list, &replace_list);
+
+	return 0;
+}
+
+static int process_init_def(char *init_def)
+{
+	struct init_function *new_init_function;
+
+	char *save_ptr;
+	char *def_type;
+	char *function_name;
+	char *init_step_name;
+	char *old_name;
+	char *new_name;
+	char *deps;
+	int err;
+
+	def_type = strtok_r(init_def, ":", &save_ptr);
+
+	switch(def_type[0]) {
+	case 'f':
+		/* An init function definition - Get the function name */
+		function_name = strtok_r(NULL, ":", &save_ptr);
+		init_step_name = strtok_r(NULL, ":", &save_ptr);
+
+		/* Check that the function is not already included */
+		err = check_for_duplicate_function(function_name);
+
+		if (err)
+			return err;
+
+		err = add_init_step_function(init_step_name, function_name);
+
+		if (err)
+			return err;
+
+		/* Create a list node for the new init function */
+		new_init_function = malloc(sizeof(struct init_function));
+
+		if (!new_init_function)
+			return ENOMEM;
+
+		new_init_function->function_name = strdup(function_name);
+		new_init_function->init_step_name = strdup(init_step_name);
+
+		if ((!new_init_function->function_name) ||
+		    (!new_init_function->init_step_name)) {
+			free(new_init_function->function_name);
+			free(new_init_function->init_step_name);
+			free(new_init_function);
+			return ENOMEM;
+		}
+
+		/* Add the new function to the init function list */
+		list_add(&new_init_function->list, &init_functions);
+
+		/* Process the new functions dependencies */
+		deps = strtok_r(NULL, ":", &save_ptr);
+		return process_init_info(new_init_function, deps);
+
+		break;
+
+	case 's':
+		function_name = strtok_r(NULL, ":", &save_ptr);
+		return add_to_skip_list(function_name);
+
+		break;
+
+	case 'r':
+		old_name = strtok_r(NULL, ":", &save_ptr);
+		new_name = strtok_r(NULL, ":", &save_ptr);
+		return add_to_replace_list(old_name, new_name);
+
+		break;
+
+	default:
+		printf("Unknown Init Type: %s", def_type);
+		break;
+	}
+
+	return 0;
+}
+
+static int build_function_list(char *buffer)
+{
+	int err = 0;
+
+	char *save_ptr;
+
+	char *init_def;
+
+	if (process_init_def(default_init_reset) ||
+	    process_init_def(default_init_sdram) ||
+	    process_init_def(default_init_reloc))
+		err = 1;
+
+	init_def = strtok_r(buffer, "()", &save_ptr);
+
+	while (init_def) {
+		if (process_init_def(init_def))
+			err = 1;
+
+		/* Skip the garbage between init definitions */
+		init_def = strtok_r(NULL, "(", &save_ptr);
+
+		/* Get the next init definition */
+		init_def = strtok_r(NULL, ")", &save_ptr);
+	};
+
+	return err;
+}
+
+
+static int open_file(const char *file, char **buffer, int *buf_size)
+{
+	struct stat sbuf;
+	int file_ptr;
+
+	char *ptr;
+
+	if ((file_ptr = open(file, O_RDONLY|O_BINARY)) < 0) {
+		fprintf (stderr, "Can't open %s: %s\n", file, strerror(errno));
+		return errno;
+	}
+
+	if (fstat(file_ptr, &sbuf) < 0) {
+		fprintf (stderr, "Can't stat %s: %s\n", file, strerror(errno));
+		return errno;
+	}
+
+	ptr = mmap(0, sbuf.st_size, PROT_READ, MAP_SHARED, file_ptr, 0);
+	if (ptr == MAP_FAILED) {
+		fprintf (stderr, "Can't read %s: %s\n", file, strerror(errno));
+		return errno;
+	}
+
+	*buffer = malloc(sbuf.st_size + 1);
+
+	if (!*buffer)
+		return ENOMEM;
+
+	*buf_size = sbuf.st_size;
+	memcpy(*buffer, ptr, sbuf.st_size);
+	(*buffer)[sbuf.st_size] = 0x00;
+
+	munmap((void *)ptr, sbuf.st_size);
+	close (file_ptr);
+
+	return 0;
+}
+
+static int check_mandatory_list(void)
+{
+	int err = 0;
+	struct list_head *position = NULL;
+	struct list_head *q = NULL;
+	struct list_head *sub_position = NULL;
+	struct init_function *init_func = NULL;
+	struct init_id *init_id = NULL;
+
+
+	/* Remove functions that exist from the mandatory functions list */
+	list_for_each_safe(position, q, &mandatory_functions)
+	{
+		init_id = list_entry(position, struct init_id, list);
+
+		list_for_each(sub_position , &init_functions)
+		{
+			init_func = list_entry(sub_position,
+					       struct init_function,
+					       list);
+
+			if (!strcmp(init_id->name, init_func->function_name) ||
+			    !strcmp(init_id->name, init_func->init_step_name))
+			{
+				free(init_id->name);
+
+				list_del(position);
+				free(init_id);
+			}
+		}
+
+	}
+
+	list_for_each(position , &mandatory_functions)
+	{
+		init_id = list_entry(position, struct init_id, list);
+
+		printf("Missing mandatory function: %s\n", init_id->name);
+		err = 1;
+	}
+
+	return err;
+}
+
+static int crosscheck_skip_replace(void)
+{
+	int err = 0;
+
+	/*
+	 * The same function cannot appear in both the skip list and the
+	 * replace list (either as the new or old function name)
+	 */
+	struct list_head *skip_pos = NULL;
+	struct list_head *replace_pos = NULL;
+
+	struct init_id *skip_def = NULL;
+	struct replace_def *replace_def = NULL;
+
+	list_for_each(skip_pos, &skip_list)
+	{
+		skip_def = list_entry(skip_pos, struct init_id, list);
+
+		list_for_each(replace_pos , &replace_list)
+		{
+			replace_def = list_entry(replace_pos,
+						 struct replace_def,
+						 list);
+
+			if (!strcmp(skip_def->name, replace_def->old_name) ||
+			    !strcmp(skip_def->name, replace_def->new_name))
+			{
+				printf("Function %s in both skip and replace definitions\n",
+				       skip_def->name);
+
+				err = 1;
+			}
+		}
+
+	}
+
+	return err;
+}
+
+static void free_dep_list(struct list_head *dep_list)
+{
+	struct init_id *tmp;
+
+	while(!list_empty(dep_list)) {
+
+		tmp = list_first_entry(dep_list, struct init_id, list);
+
+		printf("Deleting %s\n", tmp->name);
+
+		free(tmp->name);
+		list_del(&tmp->list);
+	}
+
+}
+
+static int process_skip_list(void)
+{
+	int err = 0;
+
+	/*
+	 * The same function cannot appear in both the skip list and the
+	 * replace list (either as the new or old function name)
+	 */
+	struct list_head *skip_pos = NULL;
+	struct init_id *skip_def = NULL;
+
+	struct list_head *func_pos = NULL;
+	struct list_head *q = NULL;
+	struct init_function *func_def = NULL;
+
+	list_for_each(skip_pos, &skip_list)
+	{
+		skip_def = list_entry(skip_pos, struct init_id, list);
+
+		list_for_each_safe(func_pos, q, &init_functions) {
+			func_def = list_entry(func_pos,
+					      struct init_function,
+					      list);
+
+			if (!strcmp(func_def->function_name, skip_def->name) ||
+			    !strcmp(func_def->init_step_name, skip_def->name))
+			{
+				free(func_def->function_name);
+				free(func_def->init_step_name);
+
+				free_dep_list(&func_def->mandatory_deps);
+				free_dep_list(&func_def->post_deps);
+				free_dep_list(&func_def->pre_deps);
+
+				list_del(func_pos);
+
+				free(func_def);
+			}
+		}
+	}
+
+	return err;
+}
+
+static int process_replace_list(void)
+{
+	int err = 0;
+
+	/*
+	 * The same function cannot appear in both the skip list and the
+	 * replace list (either as the new or old function name)
+	 */
+	struct list_head *func_pos = NULL;
+	struct list_head *replace_pos = NULL;
+
+	struct init_function *func_def = NULL;
+	struct replace_def *replace_def = NULL;
+
+	int found;
+
+	list_for_each(replace_pos, &replace_list)
+	{
+		replace_def = list_entry(replace_pos, struct replace_def, list);
+
+		found = 0;
+
+		list_for_each(func_pos , &init_functions)
+		{
+			func_def = list_entry(func_pos,
+					      struct init_function,
+					      list);
+
+			if (!strcmp(func_def->function_name,
+				    replace_def->old_name)) {
+				found = 1;
+				free(func_def->function_name);
+				func_def->function_name = strdup(replace_def->new_name);
+
+				if (!func_def->function_name) {
+					printf("strdup() failed!\n");
+					err = 1;
+				}
+			}
+		}
+		if (!found) {
+			printf("Replace function %s not in init list\n",
+			       replace_def->old_name);
+			err = 1;
+		}
+	}
+
+	return err;
+}
+
+static int insert_into_dep_list(struct list_head *dep_list,
+				struct init_step *init_step)
+{
+	struct list_head *position = NULL ;
+	struct init_id *init_id = NULL ;
+	struct init_id *new_init_id;
+
+	list_for_each(position, &init_step->functions)
+	{
+		init_id = list_entry(position, struct init_id, list);
+
+		new_init_id = malloc(sizeof(struct init_id));
+
+		if (!new_init_id)
+			return ENOMEM;
+
+		new_init_id->name = strdup(init_id->name);
+
+		if (!new_init_id->name) {
+			free(new_init_id);
+			return ENOMEM;
+		}
+
+		list_add(&new_init_id->list, dep_list);
+	}
+
+	return 0;
+}
+
+static int expand_dep_list(struct list_head *dep_list)
+{
+	int err = 0;
+
+	struct list_head *position = NULL ;
+	struct init_id *init_id = NULL ;
+	struct list_head *q = NULL;
+
+	struct list_head *step_pos = NULL ;
+	struct init_step *init_step = NULL ;
+
+
+	list_for_each_safe(position, q, dep_list) {
+		init_id = list_entry(position, struct init_id, list);
+
+		/* Is this a 'step' rather than a 'function' */
+		list_for_each(step_pos, &init_steps)
+		{
+			init_step = list_entry(step_pos,
+					       struct init_step,
+					       list);
+
+			if (!strcmp(init_step->name, init_id->name)) {
+				/*
+				 * Replace this init id (which is a 'step'
+				 * with the list of step functions
+				 */
+				free(init_id->name);
+
+				list_del(position);
+				free(init_id);
+
+				err = insert_into_dep_list(dep_list,
+							   init_step);
+
+				if (err)
+					return err;
+			}
+		}
+	}
+
+	return 0;
+}
+
+static int expand_dep_lists(void)
+{
+	int err = 0;
+
+	struct list_head *position = NULL ;
+	struct init_function *init_func = NULL ;
+
+	list_for_each(position , &init_functions)
+	{
+		init_func = list_entry(position, struct init_function, list);
+
+		err = expand_dep_list(&init_func->mandatory_deps);
+
+		if (err)
+			return err;
+
+		err = expand_dep_list(&init_func->pre_deps);
+
+		if (err)
+			return err;
+
+		err = expand_dep_list(&init_func->post_deps);
+
+		if (err)
+			return err;
+	}
+
+	return 0;
+}
+
+int main(int argc, const char **argv)
+{
+	int err;
+	int buf_size;
+	char *local_buffer = NULL;
+	char *x;
+
+	INIT_LIST_HEAD(&init_functions);
+	INIT_LIST_HEAD(&mandatory_functions);
+	INIT_LIST_HEAD(&skip_list);
+	INIT_LIST_HEAD(&replace_list);
+	INIT_LIST_HEAD(&init_steps);
+
+	printf("Generating init sequence from %s\n", argv[1]);
+
+	/* Read the init function definitions into a local buffer */
+	err = open_file(argv[1], &local_buffer, &buf_size);
+
+	if(err || !local_buffer)
+		exit(EXIT_FAILURE);
+
+	/*
+	 * Convert all the NULLs (except the last one) to non-NULL so
+	 * the buffer can be processed using standard string functions
+	 */
+	for(x=local_buffer; x != &local_buffer[buf_size]; x++) {
+		if(*x == 0x00)
+			*x = 0x01;
+	}
+
+	if (build_function_list(local_buffer))
+		exit(EXIT_FAILURE);
+
+	if (check_mandatory_list())
+		exit(EXIT_FAILURE);
+
+	if (crosscheck_skip_replace())
+		exit(EXIT_FAILURE);
+
+	if (process_skip_list())
+		exit(EXIT_FAILURE);
+
+	if (process_replace_list())
+		exit(EXIT_FAILURE);
+
+	if (expand_dep_lists())
+		exit(EXIT_FAILURE);
+
+	/* OK - Time to build the init sequence :) */
+
+
+	printf("*** Dumping Lists ***\n");
+
+
+	struct list_head *position = NULL ;
+	struct init_function *init_func = NULL ;
+
+	struct list_head *sub_position = NULL ;
+	struct init_id *init_id = NULL ;
+
+	list_for_each(position , &init_functions)
+	{
+		init_func = list_entry(position, struct init_function, list);
+
+		printf("Function Name   = %s\n", init_func->function_name);
+		printf("Init Step Name  = %s\n", init_func->init_step_name);
+
+		printf("  Mandatory Deps\n");
+		list_for_each(sub_position , &init_func->mandatory_deps)
+		{
+			init_id = list_entry(sub_position, struct init_id, list);
+			printf("    - %s\n", init_id->name);
+		}
+
+		printf("  Pre Deps\n");
+		list_for_each(sub_position , &init_func->pre_deps)
+		{
+			init_id = list_entry(sub_position, struct init_id, list);
+			printf("    - %s\n", init_id->name);
+		}
+
+		printf("  Post Deps\n");
+		list_for_each(sub_position , &init_func->post_deps)
+		{
+			init_id = list_entry(sub_position, struct init_id, list);
+			printf("    - %s\n", init_id->name);
+		}
+	}
+
+
+	free(local_buffer);
+	exit (EXIT_SUCCESS);
+}

[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[Detlev Zundel]

Hi Graeme,

[...]

> Now I just need to write the code that will order the function list

Did you check 'man tsort'?

Cheers
  Detlev

-- 
I've been examining the existing [linux]  kernel configuration system, and I
have about concluded that the best favor we could do everybody involved with
it is to take it out behind the barn and shoot it through the head.
                           -- Eric S. Raymond on linux-kbuild Mar 2000
--
DENX Software Engineering GmbH,      MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich,  Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-40 Fax: (+49)-8142-66989-80 Email: dzu at denx.de

[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[Wolfgang Denk]

Dear Graeme Russ,

In message <4F86CDF0.2030208@gmail.com> you wrote:
> 
> This patch is a little heads-up for my upcomming INIT_FUNC patch series
> 
> This is the INIT_FUNC 'engine' - It processes a file which consists of
> entries created by the following macros:
> 
> #define INIT_FUNC(fn, init_name, man_reqs, pre_reqs, post_reqs) \
> 	static const char __init_func_ ## fn[] __used \
> 	__attribute__((__section__(".initfuncs"))) = \
> 	"(f:" #fn ":" #init_name ":" #man_reqs " | " #pre_reqs " | " #post_reqs ")\n";
> 
> #define SKIP_INIT(init_name) \
> 	static const char __skip_init_ ## req[] __used \
> 	__attribute__((__section__(".initfuncs"))) = \
> 	"(s:" #init_name ")\n";
> 
> #define REPLACE_INIT(old_func, new_func) \
> 	static const char __replace_init_ ## old_func[] __used \
> 	__attribute__((__section__(".initfuncs"))) = \
> 	"(r:" #old_func ":" #new_func ")\n";
> 
> So an 'function' entry will look like
> (f:function_name:init_step:mandatory_req_1 mandatory_req_2 | optional_req_1 optional_req_2 | post_req_1 post_req_2)

Looks OK so far...

> So far this seems to work - It creates a list of functions with each
> having a list of dependent functions (steps are expanded so the dependency
> lists only have functions in them)
> 
> Now I just need to write the code that will order the function list
> 
> I think this single patch will more than double the use of struct list_head
> in U-Boot. It took a while to get used to it's sematics, but the Linux
> kernel list data structure is incredible

Umm... why are you writing such code in C yourself?  Don't we have
sufficient tools to perform such sorting?  Detlev already recommended
"tsort" when we discussed this befopre, and now again.  This should
allow you to avoid most of this code.

Best regards,

Wolfgang Denk

-- 
DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
Success in marriage is not so much finding the right person as it  is
being the right person.

[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[Graeme Russ]

Hi Wolfgang,

On Thu, Apr 12, 2012 at 11:28 PM, Wolfgang Denk <wd@denx.de> wrote:
> Dear Graeme Russ,
>
> In message <4F86CDF0.2030208@gmail.com> you wrote:
>>
>> This patch is a little heads-up for my upcomming INIT_FUNC patch series
>>
>> This is the INIT_FUNC 'engine' - It processes a file which consists of
>> entries created by the following macros:
>>
>> #define INIT_FUNC(fn, init_name, man_reqs, pre_reqs, post_reqs) \
>> ? ? ? static const char __init_func_ ## fn[] __used \
>> ? ? ? __attribute__((__section__(".initfuncs"))) = \
>> ? ? ? "(f:" #fn ":" #init_name ":" #man_reqs " | " #pre_reqs " | " #post_reqs ")\n";
>>
>> #define SKIP_INIT(init_name) \
>> ? ? ? static const char __skip_init_ ## req[] __used \
>> ? ? ? __attribute__((__section__(".initfuncs"))) = \
>> ? ? ? "(s:" #init_name ")\n";
>>
>> #define REPLACE_INIT(old_func, new_func) \
>> ? ? ? static const char __replace_init_ ## old_func[] __used \
>> ? ? ? __attribute__((__section__(".initfuncs"))) = \
>> ? ? ? "(r:" #old_func ":" #new_func ")\n";
>>
>> So an 'function' entry will look like
>> (f:function_name:init_step:mandatory_req_1 mandatory_req_2 | optional_req_1 optional_req_2 | post_req_1 post_req_2)
>
> Looks OK so far...
>
>> So far this seems to work - It creates a list of functions with each
>> having a list of dependent functions (steps are expanded so the dependency
>> lists only have functions in them)
>>
>> Now I just need to write the code that will order the function list
>>
>> I think this single patch will more than double the use of struct list_head
>> in U-Boot. It took a while to get used to it's sematics, but the Linux
>> kernel list data structure is incredible
>
> Umm... why are you writing such code in C yourself? ?Don't we have
> sufficient tools to perform such sorting? ?Detlev already recommended
> "tsort" when we discussed this befopre, and now again. ?This should
> allow you to avoid most of this code.

So far, the code (as posted above) doesn't do any sorting yet. What I have
so far is:
 - Reading the binary output of ld which has collected all the init
   function definitions dumped in the .initfuncs section
 - Replace NULLs with non-nulls so the .initfunc section can be processed
   as a single entity using standard C string functions
 - Use strtok_r to isolate and process each init entry - The entries are
   stored in various lists
 - Check all mandatory functions and steps have a matching INIT_FUNC
   entry
 - Check for duplicates between 'skip' and 'replace' entries (you cannot
   both skip and replace a function or step)
 - Remove all skipped functions and steps
 - Apply replacement entries
 - Expand init steps into the corresponding list of init functions

A couple of things still to be done before I can actually sort the list:
 - Remove references to non-mandatory functions which do not exist (i.e.
   so not have a matching INIT_FUNC entry)
 - Apply 'skip' processing to the init_steps list (I added init_steps
   which is used to expand steps to functions and didn't get a chance to
   add skip list processing)
 - A little more logic on 'replace' entries where an entire step is being
   replaced (replace the entry in the dependency lists and delete the
   step from the init_steps list)
 - Convert 'Post Requisites' into 'Pre-Requisites'

At which point I will have a look at tsort...

But, tsort works on paired entries, while INIT_FUNC allows functions to
have multiple dependencies. So to use tsort, I will need to process the
list to produce entry pairs - That should be a pretty simple operation.

Regards,

Graeme

[U-Boot] [RFC][PATCH] INIT_FUNC - List madness

[Graeme Russ]

Hi Wolfgang, Detlev

> But, tsort works on paired entries, while INIT_FUNC allows functions to
> have multiple dependencies. So to use tsort, I will need to process the
> list to produce entry pairs - That should be a pretty simple operation.

Well the solution appears to be trivial anyway:

http://www.algorithmist.com/index.php/Topological_sort

for each init_functions list entry {
  Check all functions which are a mandatory dependency on any other
      function exist (already done)

  Strip from pre-deps and post-deps all functions which do not have an
      INIT_FUNC entry

  Move all entries from mandatory_deps into pre_deps

  Convert all post_dep entries into corresponding pre_dep entries
}

while (init_functions list is non-empty) {

  if (no init_functions entry has an empty pre_deps) {
    Fail - cyclic dependencies
  }

  Get first entry in init_functions where pre_deps list is empty

  Add init_functions.function_name to final list

  for each init_functions list entry {
    remove init_functions.function_name from pre_deps list
  }

  remove entry from init_functions list
}

so I don't need to reduce the entries down to a list of pairs and the
sorting function will probably be one of the smaller components of the
whole thing

Regards,

Graeme