Re: [PATCH] automatic initcalls

[Keith Adamson <keith.adamson@attbi.com>]

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

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

[-- Attachment #2: make_initcall_seqence.sh --]
[-- Type: text/x-sh, Size: 618 bytes --]

#!/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=$(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

[-- Attachment #3: generate_initcall.sh --]
[-- Type: text/x-sh, Size: 1372 bytes --]

#!/bin/bash
#
#   generate_initcall.sh - Insert initcall into the "initcall_sequence"
#                          file in correct sequence
#
# First arg is the initcall
initcall=$1
#
# Get dependency initcall list for this initcall from the dependency
# database
dependency_initcall_list=$(
        grep '^'$initcall'[ :]' dependency_list_database | \
                sed 's,^.*:,,'
        )
#
#  function to find a missing initcall in initcall_sequence
function find_missing_initcall()
{
        need_initcall=""
        for name in $dependency_initcall_list
        do
                # test if initcall not done in initcall_sequence
                if [ "$(grep '^'$name'$' initcall_sequence)" = "" ]
                then
                        # return needed initcall
                        need_initcall=$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)" = "" ]
then
        echo $initcall >> initcall_sequence
fi

[-- Attachment #4: dependency_list_database --]
[-- Type: text/plain, Size: 71 bytes --]

foo1 : foo2 foo3
foo2 : foo5
foo3 : foo2 foo4
foo4 :
foo5 : foo4