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

[Graeme Russ]

Hi Wolfgang,

On Thu, Apr 12, 2012 at 11:28 PM, Wolfgang Denk <wd at denx.de> wrote:
> Dear Graeme Russ,
>
> In message <4F86CDF0.2030208 at 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