Re: [PATCH v5 4/7] kvm: x86/pmu: Introduce masked events to the pmu event filter

[Sean Christopherson <seanjc@google.com>]

On Tue, Sep 20, 2022, Aaron Lewis wrote:
>  static void convert_to_filter_events(struct kvm_pmu_event_filter *filter)
> @@ -645,7 +719,34 @@ static void convert_to_filter_events(struct kvm_pmu_event_filter *filter)
>  	for (i = 0; i < filter->nevents; i++) {
>  		u64 e = filter->events[i];
>  
> -		filter->events[i] = encode_filter_entry(e);
> +		filter->events[i] = encode_filter_entry(e, filter->flags);
> +	}
> +}
> +
> +/*
> + * Sort will order the list by exclude, then event select.  This function will
> + * then index the sublists of event selects such that when a search is done on
> + * the list, the head of the event select sublist is returned.  This simplifies
> + * the logic in filter_contains_match() when walking the list.

I'm not so sure that this is simpler overall though.  If inclusive vs. exclusive
are separate lists, then avoiding "index" would mean there's no need to convert
entries.  And IIUC, the only thing this saves in filter_contains_match() is
having to walk backwards, e.g. it's

	for (i = index; i < filter->nevents; i++) {
		if (!<eventsel event match>)
			break;

		if (is_filter_match(...))
			return true;
	}

	return false;

versus

	for (i = index; i < filter->nevents; i++) {
		if (filter_event_cmp(eventsel, filter->events[i]))
			break;

		if (is_filter_match(eventsel, filter->events[i]))
			return true;
	}

	for (i = index - 1; i > 0; i--) {
		if (filter_event_cmp(eventsel, filter->events[i]))
			break;

		if (is_filter_match(eventsel, filter->events[i]))
			return true;
	}

	return false;

It's definitely _more_ code in filter_contains_match(), and the duplicate code is
unfortunate, but I wouldn't necessarily say it's simpler.  There's a fair bit of
complexity in understanding the indexing scheme, it's just hidden.

And I believe if the indexing is dropped, then the same filter_event_cmp() helper
can be used for sort() and bsearch(), and for bounding the walks.

And here's also no need to "encode" entries or use a second struct overly.

We might need separate logic for the existing non-masked mechanism, but again
that's only more code, IMO it's not more complex.  E.g. I believe that the legacy
case can be handled with a dedicated:

	if (!(filter->flags & KVM_PMU_EVENT_FLAG_MASKED_EVENTS))
		return find_filter_index(..., cmp_u64) > 0;

Oh, and as a bonus of splitting include vs. exclude, the legacy case effectively
optimizes exclude since the length of the exclude array will be '0'.

If we do keep the indexing, I think we should rename "index" to "head", e.g. like
"head pages", to make it more obvious that the helper returns the head of a list.

> + */
> +static void index_filter_events(struct kvm_pmu_event_filter *filter)
> +{
> +	struct kvm_pmu_filter_entry *prev, *curr;
> +	int i, index = 0;
> +
> +	if (filter->nevents)
> +		prev = (struct kvm_pmu_filter_entry *)(filter->events);
> +
> +	for (i = 0; i < filter->nevents; i++) {
> +		curr = (struct kvm_pmu_filter_entry *)(&filter->events[i]);
> +
> +		if (curr->event_select != prev->event_select ||
> +		    curr->exclude != prev->exclude) {
> +			index = 0;
> +			prev = curr;
> +		}
> +
> +		curr->event_index = index++;
>  	}
>  }
> + * When filter events are converted into this format then sorted, the
> + * resulting list naturally ends up in two sublists.  One for the 'include
> + * list' and one for the 'exclude list'.  These sublists are further broken
> + * down into sublists ordered by their event select.  After that, the
> + * event select sublists are indexed such that a search for: exclude = n,
> + * event_select = n, and event_index = 0 will return the head of an event
> + * select sublist that can be walked to see if a match exists.
> + */
>  struct kvm_pmu_filter_entry {
>  	union {
>  		u64 raw;
>  		struct {
> +			u64 mask:8;
> +			u64 match:8;
> +			u64 event_index:12;

This is broken.  There are 2^12 possible event_select values, but event_index is
the index into the full list of events, i.e. is bounded only by nevents, and so
this needs to be stored as a 32-bit value.  E.g. if userspace creates a filter
with 2^32-2 entries for eventsel==0, then the index for eventsel==1 will be
2^32-1 even though there are only two event_select values in the entire list.

>  			u64 event_select:12;
> -			u64 unit_mask:8;
> -			u64 rsvd:44;
> +			u64 exclude:1;
> +			u64 rsvd:23;
>  		};
>  	};
>  };