[apparmor] [patch 4/5] parser: convert var expansion to use alternations

[Seth Arnold]

On Mon, Dec 09, 2013 at 12:37:13PM -0800, Steve Beattie wrote:
> This patch converts the parser's variable expansion from adding new
> entries for each additional variable value to incorporating an
> alternation that includes all the values for the variable; e.g. given:
> 
>   @{BINS}=/bin /usr/bin /sbin /usr/sbin
>   @{BINS}/binary ix,
> 
> rather than expanding to exntries for
> 
>   /bin/binary
>   /usr/bin/binary
>   /sbin/binary
>   /usr/sbin/binary
> 
> one entry would remain that looks like:
> 
>   {/bin,/usr/bin,/sbin,/usr/sbin}/binary
> 
> One complication with this patch is that we try to prevent mistakes for
> our users with variable expansion around '/'s; it's common for people to
> write profiles that contain things like:
> 
>  @{BAR}=/bingo/*/ /bango/
>  /foo/@{BAR}/baz
> 
> We already have a post-processing step that walks entries looking
> for multiple sequences of '/'s and filters them into single
> '/' which worked when creating new entries for each variable
> expansion. Converting to alternation expansion breaks this filtering,
> so code is added that removes leading and trailing slashes in variable
> values in the expansion if the character immediately preceding or
> following the variable is also a slash.
> 
> The intent behind this is to reduce the amount of memory allocations
> and structure walking that needed to occur in when converting from the
> entry strings to the back end nodes. Examples with real world profiles
> showed performance improvements ranging from 2.5% to 10%. However,
> because the back end operations are sensitive to the front end inputs,
> it is possible for worse results to occur; for example, it takes the
> simple_tests/vars/vars_stress_0[123].sd tests significantly longer to
> complete after this patch is applied (vars_stress_03.sd in particular
> takes ~23 times longer). An initial analysis of profiling output in
> this negative case looks like it causes the tree simplification in
> the back end to do more work for unknown reasons.
> 
> On the other hand, the test simple_tests/vars/vars_dbus_9.sd
> (introduced in "[patch 09/12] parser: more dbus variable testcases")
> takes ~1 sec to complete on my laptop before this patch, and roughly
> 0.01s with this patch applied.
> 
> (One option would be to keep the "expand entries" approach as an
> alternative, but I couldn't come up with a good heuristic for when
> to use it instead.)
> 
> Signed-off-by: Steve Beattie <steve at nxnw.org>

I think the leading and trailing slashes can probably be handled more
cleanly, and I think I'd like to see the free(*name) calls pulled up
towards the start of expand_by_alternations(), but there's nothing worth
holding up this patch.

Acked-by: Seth Arnold <seth.arnold at canonical.com>

Thanks


> ---
>  parser/parser_variable.c |  113 +++++++++++++++++++++++++++++++++++------------
>  1 file changed, 85 insertions(+), 28 deletions(-)
> 
> Index: b/parser/parser_variable.c
> ===================================================================
> --- a/parser/parser_variable.c
> +++ b/parser/parser_variable.c
> @@ -23,6 +23,8 @@
>  #include <libintl.h>
>  #include <linux/limits.h>
>  
> +#include <string>
> +
>  #define _(s) gettext(s)
>  
>  /* #define DEBUG */
> @@ -133,13 +135,90 @@ void free_var_string(struct var_string *
>  	free(var);
>  }
>  
> +static void trim_trailing_slash(std::string& str)
> +{
> +	for (std::string::reverse_iterator rit = str.rbegin();
> +			rit != str.rend() && *rit == '/'; ++rit) {
> +		/* yuck, reverse_iterators are ugly */
> +		str.erase(--rit.base());
> +	}
> +}
> +
> +static void write_replacement(const char separator, const char* value,
> +			     std::string& replacement, bool filter_leading_slash,
> +			     bool filter_trailing_slash)
> +{
> +	const char *p = value;
> +
> +	replacement.append(1, separator);
> +
> +	if (filter_leading_slash)
> +		while (*p == '/')
> +			p++;
> +
> +	replacement.append(p);
> +	if (filter_trailing_slash)
> +		trim_trailing_slash(replacement);
> +}
> +
> +static int expand_by_alternations(struct set_value **valuelist,
> +				  struct var_string *split_var,
> +				  char **name)
> +{
> +	char *value, *first_value;
> +	std::string replacement;
> +	bool filter_leading_slash = false;
> +	bool filter_trailing_slash = false;
> +
> +	first_value = get_next_set_value(valuelist);
> +	if (!first_value) {
> +		PERROR("ASSERT: set variable (%s) should always have at least one value assigned to it\n",
> +		       split_var->var);
> +		exit(1);
> +	}
> +
> +	value = get_next_set_value(valuelist);
> +	if (!value) {
> +		/* only one entry for the variable, so just sub it in */
> +		free(*name);
> +		if (asprintf(name, "%s%s%s",
> +			     split_var->prefix ? split_var->prefix : "",
> +			     first_value,
> +			     split_var->suffix ? split_var->suffix : "") == -1)
> +			return -1;
> +		return 0;
> +	}
> +
> +	if (split_var->prefix && split_var->prefix[strlen(split_var->prefix) - 1] == '/')
> +		filter_leading_slash = true;
> +	if (split_var->suffix && *split_var->suffix == '/')
> +		filter_trailing_slash = true;
> +
> +	write_replacement('{', first_value, replacement, filter_leading_slash, filter_trailing_slash);
> +	write_replacement(',', value, replacement, filter_leading_slash, filter_trailing_slash);
> +
> +	while ((value = get_next_set_value(valuelist))) {
> +		write_replacement(',', value, replacement, filter_leading_slash, filter_trailing_slash);
> +	}
> +
> +	free(*name);
> +	if (asprintf(name, "%s%s}%s",
> +		     split_var->prefix ? split_var->prefix : "",
> +		     replacement.c_str(),
> +		     split_var->suffix ? split_var->suffix : "") == -1) {
> +			return -1;
> +	}
> +
> +	return 0;
> +}
> +
>  /* doesn't handle variables in options atm */
> -static int expand_entry_variables(char **name, void *entry, 
> +static int expand_entry_variables(char **name, void *entry,
>  				  int (dup_and_chain)(void *))
>  {
>  	struct set_value *valuelist;
> -	char *value;
>  	struct var_string *split_var;
> +	int ret;
>  
>  	if (!entry) 		/* can happen when entry is optional */
>  		return 0;
> @@ -157,34 +236,12 @@ static int expand_entry_variables(char *
>  			exit(1);
>  		}
>  
> -		value = get_next_set_value(&valuelist);
> -		if (!value) {
> -			PERROR("ASSERT: set variable (%s) should always have at least one value assigned to them\n",
> -			       split_var->var);
> -			exit(1);
> -		}
> -		free(*name);
> -		if (asprintf(name, "%s%s%s",
> -			     split_var->prefix ? split_var->prefix : "",
> -			     value,
> -			     split_var->suffix ? split_var->suffix : "") == -1)
> -			return -1;
> -
> -		while ((value = get_next_set_value(&valuelist))) {
> -			if (!dup_and_chain(entry)) {
> -				PERROR("Memory allocation error while handling set variable %s\n",
> -				       split_var->var);
> -				exit(1);
> -			}
> -
> -			free(*name);
> -			if (asprintf(name, "%s%s%s",
> -			      split_var->prefix ? split_var->prefix : "", value,
> -			      split_var->suffix ? split_var->suffix : "") == -1)
> -				return -1;
> -		}
> +		ret = expand_by_alternations(&valuelist, split_var, name);
>  
>  		free_var_string(split_var);
> +		if (ret != 0)
> +			return -1;
> +
>  	}
>  	return 0;
>  }
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <https://lists.ubuntu.com/archives/apparmor/attachments/20131212/7f3ed570/attachment.pgp>