Re: [PATCH] automatic initcalls

Keith Adamson (keith.adamson@attbi.com)
28 Jul 2002 04:50:59 -0400


--=-SXcrz8kgGTe1I4OhKU75
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

On Sun, 2002-07-28 at 00:47, Linus Torvalds wrote:
>
>
> On Sat, 27 Jul 2002, Jeff Garzik wrote:
> >
> > I've always preferred a system where one simply lists dependencies [as
> > you describe above], and some program actually does the hard work of
> > chasing down all the initcall dependency checking and ordering.
> >
> > Linus has traditionally poo-pooed this so I haven't put any work towards
> > it...
>
> I don't hate the notion, but at the same time every time it comes up I
> feel that there are reasonably simple ways to just avoid the ordering
> problems.
>
> Rusty had a script, but somebody complained about the speed of it. I
> haven't looked at it myself.
>
> Linus

There is a relatively simple and fast recursive algorithm I've used
before to generating a sequence from a dependency list.
For initcall sequence it would be something like this (bash scripts
attached);

Dependency database: dependency_list_database
Main programs: make_initcall_seqence.sh
Recursive routine: generate_initcall.sh

Output sequence: initcall_sequence

See attached files.

Normally I have error checking for bad dependencies (you can get into a
infinite recursive loop if for instance "foo1" needs "foo2" and also
"foo2" needs "foo1") ... but I didn't do it to keep the algorithm more
understandable.

Keith

--=-SXcrz8kgGTe1I4OhKU75
Content-Disposition: attachment; filename=make_initcall_seqence.sh
Content-Transfer-Encoding: quoted-printable
Content-Type: text/x-sh; name=make_initcall_seqence.sh; charset=UTF-8

#!/bin/bash
#
# make_initcall_seqence.sh - generate initcall sequence, file
# "initcall_sequence", from an initcall
# dependency list database, file
# "dependency_list_database"
#
# A random list of initcalls (will sequence them acording to the
# dependency database
initcall_list=3D$(sed 's,:.*$,,' dependency_list_database)
#
# Initialize the initcall_sequence file
rm -f initcall_sequence
touch initcall_sequence
#
# build the initcall_sequence file
for name in $initcall_list
do
generate_initcall.sh $name
done

--=-SXcrz8kgGTe1I4OhKU75
Content-Disposition: attachment; filename=generate_initcall.sh
Content-Transfer-Encoding: quoted-printable
Content-Type: text/x-sh; name=generate_initcall.sh; charset=UTF-8

#!/bin/bash
#
# generate_initcall.sh - Insert initcall into the "initcall_sequence"
# file in correct sequence
#
# First arg is the initcall
initcall=3D$1
#
# Get dependency initcall list for this initcall from the dependency
# database
dependency_initcall_list=3D$(
grep '^'$initcall'[ :]' dependency_list_database | \
sed 's,^.*:,,'
)
#
# function to find a missing initcall in initcall_sequence
function find_missing_initcall()
{
need_initcall=3D""
for name in $dependency_initcall_list
do
# test if initcall not done in initcall_sequence
if [ "$(grep '^'$name'$' initcall_sequence)" =3D "" ]
then
# return needed initcall
need_initcall=3D$name
break
fi
done
}
#
# generate missing initcalls that this initcall needs done first
#
find_missing_initcall
while [ -n "$need_initcall" ] # loop while adding missing initcalls
do
generate_initcall.sh $need_initcall # NOTE THE RECURSIVE CALL
find_missing_initcall
done
#
# Finally add this initcall to initcall_sequence (if missing)
if [ "$(grep '^'$initcall'$' initcall_sequence)" =3D "" ]
then
echo $initcall >> initcall_sequence
fi

--=-SXcrz8kgGTe1I4OhKU75
Content-Disposition: attachment; filename=dependency_list_database
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; name=dependency_list_database; charset=UTF-8

foo1 : foo2 foo3
foo2 : foo5
foo3 : foo2 foo4
foo4 :
foo5 : foo4=20

--=-SXcrz8kgGTe1I4OhKU75--

-
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/