[PATCH] ld: pe: Improve performance of object file exclude symbol directives

[Martin Storsjö]

On Mon, 5 Sep 2022, Nick Clifton wrote:

> Hi Martin,
>
>> Store the list of excluded symbols in a sorted list, speeding up
>> checking for duplicates when inserting new entries.
>
> An excellent idea.

FWIW, regarding most of this review here: This file already has got two 
copies of the exact same routines for inserting structs into a sorted list 
of structs (find_export_in_list, def_file_add_export, find_import_in_list, 
def_file_add_import), so for this patch I just made a third copy of the 
same routines, with the exact same behaviours, but adapted for the 
exclude_symbol structs.

I'd be happy to adjust things based on your review, but then I'll probably 
follow up with a separate patch to adapt the other existing 
implementations based on this feedback.

>
>>     /* From EXCLUDE_SYMBOLS or embedded directives. */
>> +  int num_exclude_symbols;
>
> Presumably there can never be a negative number of excluded symbols,
> so using "unsigned int" here might be more appropriate.

Sure, I can change that.

>
>
>> +  if (fdef->exclude_symbols)
>
> Given that the for() loop to follow checks fdef->num_exclude_symbols,
> this if() statement is redundant.

Sure, I can remove it. (The existing exports/imports lists of structs have 
the exact same structure.)

>> +      for (i = 0; i < fdef->num_exclude_symbols; i++)
>> +	   free (fdef->exclude_symbols[i].symbol_name);
>> +      free (fdef->exclude_symbols);
>
> Calling free(NULL) is allowed, so the if() statement is still not needed.

Sure. (Also preexisting from exports/imports.)

>> +/* Search the position of the identical element, or returns the position
>> +   of the next higher element. If last valid element is smaller, then MAX
>> +   is returned.  */
>
> The comment should explain the use of the IS_IDENT parameter.
>
> It should probably also note that MAX is expected to be the same as the 
> number
> of entries in the B array.

Ok, I can expand the comment to explain these.

>> +static int
>> +find_exclude_in_list (def_file_exclude_symbol *b, int max,
>> +		      const char *name, int *is_ident)
>
> Since we are dealing with array indicies here, I would suggest that the 
> function
> should return an unsigned int.  Likewise the MAX parameter should be 
> unsigned.
> Plus is_ident should be a boolean pointer, not an integer pointer.

Ok, I can change that. (Ditto for the preexisting functions.)

>
>> +static def_file_exclude_symbol *
>> +def_file_add_exclude_symbol (def_file *fdef, const char *name, int 
>> *is_dup)
>
> I think that IS_DUP should be a "boolean *" not a "int *".

Ok

>
>> +  int max_exclude_symbols = ROUND_UP(fdef->num_exclude_symbols, 32);
>
> Magic numbers are bad.  Please replace 32 with a defined constant.
>
>> +  if (fdef->num_exclude_symbols >= max_exclude_symbols)
>
> This is sneaky and not very intuitive.  I would prefer it if you had
> two fields in the fdef structure, one for the number of allocated
> slots in the exclude_symbols array and one for the number of used slots.
>
> Then testing for when the array needs to be extended would be a case
> of comparing these two fields.  Using two fields might take up more
> space in the structure, but it sure makes a lot more sense to me.

This was also designed according to the existing code - but yes, I agree 
that using a separate variable keeping track of the allocation is much 
safer and clearer. (It took a while to think through to see how this works 
for the initial allocation and all that.)

>> +      max_exclude_symbols = ROUND_UP(fdef->num_exclude_symbols + 1, 32);
>
> Given that the point of this patch is to improve performance when there
> are a large number of excluded symbols, incrementing the array by 32 slots
> at a time seems counter intuitive.  I would suggest a bigger number, eg 1024
> or 10240.

Sure, or doubling as Jan suggested.

>> +  e = fdef->exclude_symbols + pos;
>> +  if (pos != fdef->num_exclude_symbols)
>> +    memmove (&e[1], e, (sizeof (def_file_exclude_symbol) * 
>> (fdef->num_exclude_symbols - pos)));
>
> What the ?  OK, so what is going on here ?  At the very least I think that
> you are going to need to add a comment to this piece of code.

Sure. (This is also preexisting code for the other lists.) As this inserts 
into a sorted list of structs, it moves the later structs forward when 
inserting in the middle of the list.

// Martin