core.c 60.4 KB
Newer Older
1
/*
2
 * Performance events x86 architecture code
3
 *
4 5 6 7
 *  Copyright (C) 2008 Thomas Gleixner <tglx@linutronix.de>
 *  Copyright (C) 2008-2009 Red Hat, Inc., Ingo Molnar
 *  Copyright (C) 2009 Jaswinder Singh Rajput
 *  Copyright (C) 2009 Advanced Micro Devices, Inc., Robert Richter
8
 *  Copyright (C) 2008-2009 Red Hat, Inc., Peter Zijlstra
9
 *  Copyright (C) 2009 Intel Corporation, <markus.t.metzger@intel.com>
10
 *  Copyright (C) 2009 Google, Inc., Stephane Eranian
11 12 13 14
 *
 *  For licencing details see kernel-base/COPYING
 */

15
#include <linux/perf_event.h>
16 17 18 19
#include <linux/capability.h>
#include <linux/notifier.h>
#include <linux/hardirq.h>
#include <linux/kprobes.h>
20 21
#include <linux/export.h>
#include <linux/init.h>
22
#include <linux/kdebug.h>
23
#include <linux/sched/mm.h>
24
#include <linux/sched/clock.h>
25
#include <linux/uaccess.h>
26
#include <linux/slab.h>
27
#include <linux/cpu.h>
28
#include <linux/bitops.h>
29
#include <linux/device.h>
30
#include <linux/nospec.h>
31 32

#include <asm/apic.h>
33
#include <asm/stacktrace.h>
Peter Zijlstra's avatar
Peter Zijlstra committed
34
#include <asm/nmi.h>
35
#include <asm/smp.h>
36
#include <asm/alternative.h>
37
#include <asm/mmu_context.h>
38
#include <asm/tlbflush.h>
39
#include <asm/timer.h>
40 41
#include <asm/desc.h>
#include <asm/ldt.h>
42
#include <asm/unwind.h>
43

44
#include "perf_event.h"
45 46

struct x86_pmu x86_pmu __read_mostly;
47

48
DEFINE_PER_CPU(struct cpu_hw_events, cpu_hw_events) = {
49 50
	.enabled = 1,
};
51

52
DEFINE_STATIC_KEY_FALSE(rdpmc_always_available_key);
53

54
u64 __read_mostly hw_cache_event_ids
55 56 57
				[PERF_COUNT_HW_CACHE_MAX]
				[PERF_COUNT_HW_CACHE_OP_MAX]
				[PERF_COUNT_HW_CACHE_RESULT_MAX];
58
u64 __read_mostly hw_cache_extra_regs
59 60 61
				[PERF_COUNT_HW_CACHE_MAX]
				[PERF_COUNT_HW_CACHE_OP_MAX]
				[PERF_COUNT_HW_CACHE_RESULT_MAX];
62

63
/*
64 65
 * Propagate event elapsed time into the generic event.
 * Can only be executed on the CPU where the event is active.
66 67
 * Returns the delta events processed.
 */
68
u64 x86_perf_event_update(struct perf_event *event)
69
{
70
	struct hw_perf_event *hwc = &event->hw;
71
	int shift = 64 - x86_pmu.cntval_bits;
72
	u64 prev_raw_count, new_raw_count;
73
	int idx = hwc->idx;
74
	u64 delta;
75

76
	if (idx == INTEL_PMC_IDX_FIXED_BTS)
77 78
		return 0;

79
	/*
80
	 * Careful: an NMI might modify the previous event value.
81 82 83
	 *
	 * Our tactic to handle this is to first atomically read and
	 * exchange a new raw count - then add that new-prev delta
84
	 * count to the generic event atomically:
85 86
	 */
again:
87
	prev_raw_count = local64_read(&hwc->prev_count);
88
	rdpmcl(hwc->event_base_rdpmc, new_raw_count);
89

90
	if (local64_cmpxchg(&hwc->prev_count, prev_raw_count,
91 92 93 94 95 96
					new_raw_count) != prev_raw_count)
		goto again;

	/*
	 * Now we have the new raw value and have updated the prev
	 * timestamp already. We can now calculate the elapsed delta
97
	 * (event-)time and add that to the generic event.
98 99
	 *
	 * Careful, not all hw sign-extends above the physical width
100
	 * of the count.
101
	 */
102 103
	delta = (new_raw_count << shift) - (prev_raw_count << shift);
	delta >>= shift;
104

105 106
	local64_add(delta, &event->count);
	local64_sub(delta, &hwc->period_left);
107 108

	return new_raw_count;
109 110
}

111 112 113 114 115
/*
 * Find and validate any extra registers to set up.
 */
static int x86_pmu_extra_regs(u64 config, struct perf_event *event)
{
116
	struct hw_perf_event_extra *reg;
117 118
	struct extra_reg *er;

119
	reg = &event->hw.extra_reg;
120 121 122 123 124 125 126 127 128

	if (!x86_pmu.extra_regs)
		return 0;

	for (er = x86_pmu.extra_regs; er->msr; er++) {
		if (er->event != (config & er->config_mask))
			continue;
		if (event->attr.config1 & ~er->valid_mask)
			return -EINVAL;
129 130 131
		/* Check if the extra msrs can be safely accessed*/
		if (!er->extra_msr_access)
			return -ENXIO;
132 133 134 135

		reg->idx = er->idx;
		reg->config = event->attr.config1;
		reg->reg = er->msr;
136 137 138 139 140
		break;
	}
	return 0;
}

141
static atomic_t active_events;
142
static atomic_t pmc_refcount;
Peter Zijlstra's avatar
Peter Zijlstra committed
143 144
static DEFINE_MUTEX(pmc_reserve_mutex);

145 146
#ifdef CONFIG_X86_LOCAL_APIC

Peter Zijlstra's avatar
Peter Zijlstra committed
147 148 149 150
static bool reserve_pmc_hardware(void)
{
	int i;

151
	for (i = 0; i < x86_pmu.num_counters; i++) {
152
		if (!reserve_perfctr_nmi(x86_pmu_event_addr(i)))
Peter Zijlstra's avatar
Peter Zijlstra committed
153 154 155
			goto perfctr_fail;
	}

156
	for (i = 0; i < x86_pmu.num_counters; i++) {
157
		if (!reserve_evntsel_nmi(x86_pmu_config_addr(i)))
Peter Zijlstra's avatar
Peter Zijlstra committed
158 159 160 161 162 163 164
			goto eventsel_fail;
	}

	return true;

eventsel_fail:
	for (i--; i >= 0; i--)
165
		release_evntsel_nmi(x86_pmu_config_addr(i));
Peter Zijlstra's avatar
Peter Zijlstra committed
166

167
	i = x86_pmu.num_counters;
Peter Zijlstra's avatar
Peter Zijlstra committed
168 169 170

perfctr_fail:
	for (i--; i >= 0; i--)
171
		release_perfctr_nmi(x86_pmu_event_addr(i));
Peter Zijlstra's avatar
Peter Zijlstra committed
172 173 174 175 176 177 178 179

	return false;
}

static void release_pmc_hardware(void)
{
	int i;

180
	for (i = 0; i < x86_pmu.num_counters; i++) {
181 182
		release_perfctr_nmi(x86_pmu_event_addr(i));
		release_evntsel_nmi(x86_pmu_config_addr(i));
Peter Zijlstra's avatar
Peter Zijlstra committed
183 184 185
	}
}

186 187 188 189 190 191 192
#else

static bool reserve_pmc_hardware(void) { return true; }
static void release_pmc_hardware(void) {}

#endif

193 194
static bool check_hw_exists(void)
{
195 196
	u64 val, val_fail = -1, val_new= ~0;
	int i, reg, reg_fail = -1, ret = 0;
197
	int bios_fail = 0;
198
	int reg_safe = -1;
199

200 201 202 203 204
	/*
	 * Check to see if the BIOS enabled any of the counters, if so
	 * complain and bail.
	 */
	for (i = 0; i < x86_pmu.num_counters; i++) {
205
		reg = x86_pmu_config_addr(i);
206 207 208
		ret = rdmsrl_safe(reg, &val);
		if (ret)
			goto msr_fail;
209 210 211 212
		if (val & ARCH_PERFMON_EVENTSEL_ENABLE) {
			bios_fail = 1;
			val_fail = val;
			reg_fail = reg;
213 214
		} else {
			reg_safe = i;
215
		}
216 217 218 219 220 221 222 223
	}

	if (x86_pmu.num_counters_fixed) {
		reg = MSR_ARCH_PERFMON_FIXED_CTR_CTRL;
		ret = rdmsrl_safe(reg, &val);
		if (ret)
			goto msr_fail;
		for (i = 0; i < x86_pmu.num_counters_fixed; i++) {
224 225 226 227 228
			if (val & (0x03 << i*4)) {
				bios_fail = 1;
				val_fail = val;
				reg_fail = reg;
			}
229 230 231
		}
	}

232 233 234 235 236 237 238 239 240 241 242
	/*
	 * If all the counters are enabled, the below test will always
	 * fail.  The tools will also become useless in this scenario.
	 * Just fail and disable the hardware counters.
	 */

	if (reg_safe == -1) {
		reg = reg_safe;
		goto msr_fail;
	}

243
	/*
244 245 246
	 * Read the current value, change it and read it back to see if it
	 * matches, this is needed to detect certain hardware emulators
	 * (qemu/kvm) that don't trap on the MSR access and always return 0s.
247
	 */
248
	reg = x86_pmu_event_addr(reg_safe);
249 250 251
	if (rdmsrl_safe(reg, &val))
		goto msr_fail;
	val ^= 0xffffUL;
252 253
	ret = wrmsrl_safe(reg, val);
	ret |= rdmsrl_safe(reg, &val_new);
254
	if (ret || val != val_new)
255
		goto msr_fail;
256

257 258 259
	/*
	 * We still allow the PMU driver to operate:
	 */
260
	if (bios_fail) {
261 262 263
		pr_cont("Broken BIOS detected, complain to your hardware vendor.\n");
		pr_err(FW_BUG "the BIOS has corrupted hw-PMU resources (MSR %x is %Lx)\n",
			      reg_fail, val_fail);
264
	}
265 266

	return true;
267 268

msr_fail:
269 270 271 272 273 274 275
	if (boot_cpu_has(X86_FEATURE_HYPERVISOR)) {
		pr_cont("PMU not available due to virtualization, using software events only.\n");
	} else {
		pr_cont("Broken PMU hardware detected, using software events only.\n");
		pr_err("Failed to access perfctr msr (MSR %x is %Lx)\n",
		       reg, val_new);
	}
276

277
	return false;
278 279
}

280
static void hw_perf_event_destroy(struct perf_event *event)
Peter Zijlstra's avatar
Peter Zijlstra committed
281
{
282
	x86_release_hardware();
283
	atomic_dec(&active_events);
Peter Zijlstra's avatar
Peter Zijlstra committed
284 285
}

286 287 288 289 290 291 292 293
void hw_perf_lbr_event_destroy(struct perf_event *event)
{
	hw_perf_event_destroy(event);

	/* undo the lbr/bts event accounting */
	x86_del_exclusive(x86_lbr_exclusive_lbr);
}

294 295 296 297 298
static inline int x86_pmu_initialized(void)
{
	return x86_pmu.handle_irq != NULL;
}

299
static inline int
300
set_ext_hw_attr(struct hw_perf_event *hwc, struct perf_event *event)
301
{
302
	struct perf_event_attr *attr = &event->attr;
303 304 305 306 307
	unsigned int cache_type, cache_op, cache_result;
	u64 config, val;

	config = attr->config;

308
	cache_type = (config >> 0) & 0xff;
309 310
	if (cache_type >= PERF_COUNT_HW_CACHE_MAX)
		return -EINVAL;
311
	cache_type = array_index_nospec(cache_type, PERF_COUNT_HW_CACHE_MAX);
312 313 314 315

	cache_op = (config >>  8) & 0xff;
	if (cache_op >= PERF_COUNT_HW_CACHE_OP_MAX)
		return -EINVAL;
316
	cache_op = array_index_nospec(cache_op, PERF_COUNT_HW_CACHE_OP_MAX);
317 318 319 320

	cache_result = (config >> 16) & 0xff;
	if (cache_result >= PERF_COUNT_HW_CACHE_RESULT_MAX)
		return -EINVAL;
321
	cache_result = array_index_nospec(cache_result, PERF_COUNT_HW_CACHE_RESULT_MAX);
322 323 324 325 326 327 328 329 330 331

	val = hw_cache_event_ids[cache_type][cache_op][cache_result];

	if (val == 0)
		return -ENOENT;

	if (val == -1)
		return -EINVAL;

	hwc->config |= val;
332 333
	attr->config1 = hw_cache_extra_regs[cache_type][cache_op][cache_result];
	return x86_pmu_extra_regs(val, event);
334 335
}

336 337 338 339
int x86_reserve_hardware(void)
{
	int err = 0;

340
	if (!atomic_inc_not_zero(&pmc_refcount)) {
341
		mutex_lock(&pmc_reserve_mutex);
342
		if (atomic_read(&pmc_refcount) == 0) {
343 344 345 346 347 348
			if (!reserve_pmc_hardware())
				err = -EBUSY;
			else
				reserve_ds_buffers();
		}
		if (!err)
349
			atomic_inc(&pmc_refcount);
350 351 352 353 354 355 356 357
		mutex_unlock(&pmc_reserve_mutex);
	}

	return err;
}

void x86_release_hardware(void)
{
358
	if (atomic_dec_and_mutex_lock(&pmc_refcount, &pmc_reserve_mutex)) {
359 360 361 362 363 364
		release_pmc_hardware();
		release_ds_buffers();
		mutex_unlock(&pmc_reserve_mutex);
	}
}

365 366 367 368 369 370
/*
 * Check if we can create event of a certain type (that no conflicting events
 * are present).
 */
int x86_add_exclusive(unsigned int what)
{
371
	int i;
372

373 374 375 376 377
	/*
	 * When lbr_pt_coexist we allow PT to coexist with either LBR or BTS.
	 * LBR and BTS are still mutually exclusive.
	 */
	if (x86_pmu.lbr_pt_coexist && what == x86_lbr_exclusive_pt)
378 379
		return 0;

380 381 382 383 384 385 386 387
	if (!atomic_inc_not_zero(&x86_pmu.lbr_exclusive[what])) {
		mutex_lock(&pmc_reserve_mutex);
		for (i = 0; i < ARRAY_SIZE(x86_pmu.lbr_exclusive); i++) {
			if (i != what && atomic_read(&x86_pmu.lbr_exclusive[i]))
				goto fail_unlock;
		}
		atomic_inc(&x86_pmu.lbr_exclusive[what]);
		mutex_unlock(&pmc_reserve_mutex);
388
	}
389

390 391
	atomic_inc(&active_events);
	return 0;
392

393
fail_unlock:
394
	mutex_unlock(&pmc_reserve_mutex);
395
	return -EBUSY;
396 397 398 399
}

void x86_del_exclusive(unsigned int what)
{
400
	if (x86_pmu.lbr_pt_coexist && what == x86_lbr_exclusive_pt)
401 402
		return;

403
	atomic_dec(&x86_pmu.lbr_exclusive[what]);
404
	atomic_dec(&active_events);
405 406
}

407
int x86_setup_perfctr(struct perf_event *event)
408 409 410 411 412
{
	struct perf_event_attr *attr = &event->attr;
	struct hw_perf_event *hwc = &event->hw;
	u64 config;

413
	if (!is_sampling_event(event)) {
414 415
		hwc->sample_period = x86_pmu.max_period;
		hwc->last_period = hwc->sample_period;
416
		local64_set(&hwc->period_left, hwc->sample_period);
417 418 419
	}

	if (attr->type == PERF_TYPE_RAW)
420
		return x86_pmu_extra_regs(event->attr.config, event);
421 422

	if (attr->type == PERF_TYPE_HW_CACHE)
423
		return set_ext_hw_attr(hwc, event);
424 425 426 427

	if (attr->config >= x86_pmu.max_events)
		return -EINVAL;

428 429
	attr->config = array_index_nospec((unsigned long)attr->config, x86_pmu.max_events);

430 431 432 433 434 435 436 437 438 439 440 441 442 443 444
	/*
	 * The generic map:
	 */
	config = x86_pmu.event_map(attr->config);

	if (config == 0)
		return -ENOENT;

	if (config == -1LL)
		return -EINVAL;

	hwc->config |= config;

	return 0;
}
445

446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
/*
 * check that branch_sample_type is compatible with
 * settings needed for precise_ip > 1 which implies
 * using the LBR to capture ALL taken branches at the
 * priv levels of the measurement
 */
static inline int precise_br_compat(struct perf_event *event)
{
	u64 m = event->attr.branch_sample_type;
	u64 b = 0;

	/* must capture all branches */
	if (!(m & PERF_SAMPLE_BRANCH_ANY))
		return 0;

	m &= PERF_SAMPLE_BRANCH_KERNEL | PERF_SAMPLE_BRANCH_USER;

	if (!event->attr.exclude_user)
		b |= PERF_SAMPLE_BRANCH_USER;

	if (!event->attr.exclude_kernel)
		b |= PERF_SAMPLE_BRANCH_KERNEL;

	/*
	 * ignore PERF_SAMPLE_BRANCH_HV, not supported on x86
	 */

	return m == b;
}

476
int x86_pmu_max_precise(void)
477
{
478 479 480 481 482
	int precise = 0;

	/* Support for constant skid */
	if (x86_pmu.pebs_active && !x86_pmu.pebs_broken) {
		precise++;
483

484 485
		/* Support for IP fixup */
		if (x86_pmu.lbr_nr || x86_pmu.intel_cap.pebs_format >= 2)
486 487
			precise++;

488 489 490 491 492
		if (x86_pmu.pebs_prec_dist)
			precise++;
	}
	return precise;
}
493

494 495 496 497
int x86_pmu_hw_config(struct perf_event *event)
{
	if (event->attr.precise_ip) {
		int precise = x86_pmu_max_precise();
498 499 500

		if (event->attr.precise_ip > precise)
			return -EOPNOTSUPP;
501 502 503 504

		/* There's no sense in having PEBS for non sampling events: */
		if (!is_sampling_event(event))
			return -EINVAL;
505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533
	}
	/*
	 * check that PEBS LBR correction does not conflict with
	 * whatever the user is asking with attr->branch_sample_type
	 */
	if (event->attr.precise_ip > 1 && x86_pmu.intel_cap.pebs_format < 2) {
		u64 *br_type = &event->attr.branch_sample_type;

		if (has_branch_stack(event)) {
			if (!precise_br_compat(event))
				return -EOPNOTSUPP;

			/* branch_sample_type is compatible */

		} else {
			/*
			 * user did not specify  branch_sample_type
			 *
			 * For PEBS fixups, we capture all
			 * the branches at the priv level of the
			 * event.
			 */
			*br_type = PERF_SAMPLE_BRANCH_ANY;

			if (!event->attr.exclude_user)
				*br_type |= PERF_SAMPLE_BRANCH_USER;

			if (!event->attr.exclude_kernel)
				*br_type |= PERF_SAMPLE_BRANCH_KERNEL;
534
		}
535 536
	}

537 538 539
	if (event->attr.branch_sample_type & PERF_SAMPLE_BRANCH_CALL_STACK)
		event->attach_state |= PERF_ATTACH_TASK_DATA;

540 541 542 543
	/*
	 * Generate PMC IRQs:
	 * (keep 'enabled' bit clear for now)
	 */
544
	event->hw.config = ARCH_PERFMON_EVENTSEL_INT;
545 546 547 548

	/*
	 * Count user and OS events unless requested not to
	 */
549 550 551 552
	if (!event->attr.exclude_user)
		event->hw.config |= ARCH_PERFMON_EVENTSEL_USR;
	if (!event->attr.exclude_kernel)
		event->hw.config |= ARCH_PERFMON_EVENTSEL_OS;
553

554 555
	if (event->attr.type == PERF_TYPE_RAW)
		event->hw.config |= event->attr.config & X86_RAW_EVENT_MASK;
556

557 558 559 560 561 562
	if (event->attr.sample_period && x86_pmu.limit_period) {
		if (x86_pmu.limit_period(event, event->attr.sample_period) >
				event->attr.sample_period)
			return -EINVAL;
	}

563
	return x86_setup_perfctr(event);
564 565
}

566
/*
567
 * Setup the hardware configuration for a given attr_type
568
 */
569
static int __x86_pmu_event_init(struct perf_event *event)
570
{
Peter Zijlstra's avatar
Peter Zijlstra committed
571
	int err;
572

573 574
	if (!x86_pmu_initialized())
		return -ENODEV;
575

576
	err = x86_reserve_hardware();
Peter Zijlstra's avatar
Peter Zijlstra committed
577 578 579
	if (err)
		return err;

580
	atomic_inc(&active_events);
581
	event->destroy = hw_perf_event_destroy;
582

583 584 585
	event->hw.idx = -1;
	event->hw.last_cpu = -1;
	event->hw.last_tag = ~0ULL;
586

587 588
	/* mark unused */
	event->hw.extra_reg.idx = EXTRA_REG_NONE;
589 590
	event->hw.branch_reg.idx = EXTRA_REG_NONE;

591
	return x86_pmu.hw_config(event);
592 593
}

594
void x86_pmu_disable_all(void)
595
{
596
	struct cpu_hw_events *cpuc = this_cpu_ptr(&cpu_hw_events);
597 598
	int idx;

599
	for (idx = 0; idx < x86_pmu.num_counters; idx++) {
600 601
		u64 val;

602
		if (!test_bit(idx, cpuc->active_mask))
603
			continue;
604
		rdmsrl(x86_pmu_config_addr(idx), val);
605
		if (!(val & ARCH_PERFMON_EVENTSEL_ENABLE))
606
			continue;
607
		val &= ~ARCH_PERFMON_EVENTSEL_ENABLE;
608
		wrmsrl(x86_pmu_config_addr(idx), val);
609 610 611
	}
}

612 613 614 615 616 617 618 619 620 621 622 623 624
/*
 * There may be PMI landing after enabled=0. The PMI hitting could be before or
 * after disable_all.
 *
 * If PMI hits before disable_all, the PMU will be disabled in the NMI handler.
 * It will not be re-enabled in the NMI handler again, because enabled=0. After
 * handling the NMI, disable_all will be called, which will not change the
 * state either. If PMI hits after disable_all, the PMU is already disabled
 * before entering NMI handler. The NMI handler will not change the state
 * either.
 *
 * So either situation is harmless.
 */
Peter Zijlstra's avatar
Peter Zijlstra committed
625
static void x86_pmu_disable(struct pmu *pmu)
626
{
627
	struct cpu_hw_events *cpuc = this_cpu_ptr(&cpu_hw_events);
628

629
	if (!x86_pmu_initialized())
630
		return;
631

632 633 634 635 636 637
	if (!cpuc->enabled)
		return;

	cpuc->n_added = 0;
	cpuc->enabled = 0;
	barrier();
638 639

	x86_pmu.disable_all();
640
}
641

642
void x86_pmu_enable_all(int added)
643
{
644
	struct cpu_hw_events *cpuc = this_cpu_ptr(&cpu_hw_events);
645 646
	int idx;

647
	for (idx = 0; idx < x86_pmu.num_counters; idx++) {
648
		struct hw_perf_event *hwc = &cpuc->events[idx]->hw;
649

650
		if (!test_bit(idx, cpuc->active_mask))
651
			continue;
652

653
		__x86_pmu_enable_event(hwc, ARCH_PERFMON_EVENTSEL_ENABLE);
654 655 656
	}
}

Peter Zijlstra's avatar
Peter Zijlstra committed
657
static struct pmu pmu;
658 659 660 661 662 663

static inline int is_x86_event(struct perf_event *event)
{
	return event->pmu == &pmu;
}

664 665 666 667 668 669 670 671 672 673 674 675
/*
 * Event scheduler state:
 *
 * Assign events iterating over all events and counters, beginning
 * with events with least weights first. Keep the current iterator
 * state in struct sched_state.
 */
struct sched_state {
	int	weight;
	int	event;		/* event index */
	int	counter;	/* counter index */
	int	unassigned;	/* number of events to be assigned left */
676
	int	nr_gp;		/* number of GP counters used */
677 678 679
	unsigned long used[BITS_TO_LONGS(X86_PMC_IDX_MAX)];
};

680 681 682
/* Total max is X86_PMC_IDX_MAX, but we are O(n!) limited */
#define	SCHED_STATES_MAX	2

683 684 685
struct perf_sched {
	int			max_weight;
	int			max_events;
686 687
	int			max_gp;
	int			saved_states;
688
	struct event_constraint	**constraints;
689
	struct sched_state	state;
690
	struct sched_state	saved[SCHED_STATES_MAX];
691 692 693 694 695
};

/*
 * Initialize interator that runs through all events and counters.
 */
696
static void perf_sched_init(struct perf_sched *sched, struct event_constraint **constraints,
697
			    int num, int wmin, int wmax, int gpmax)
698 699 700 701 702 703
{
	int idx;

	memset(sched, 0, sizeof(*sched));
	sched->max_events	= num;
	sched->max_weight	= wmax;
704
	sched->max_gp		= gpmax;
705
	sched->constraints	= constraints;
706 707

	for (idx = 0; idx < num; idx++) {
708
		if (constraints[idx]->weight == wmin)
709 710 711 712 713 714 715 716
			break;
	}

	sched->state.event	= idx;		/* start with min weight */
	sched->state.weight	= wmin;
	sched->state.unassigned	= num;
}

717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739
static void perf_sched_save_state(struct perf_sched *sched)
{
	if (WARN_ON_ONCE(sched->saved_states >= SCHED_STATES_MAX))
		return;

	sched->saved[sched->saved_states] = sched->state;
	sched->saved_states++;
}

static bool perf_sched_restore_state(struct perf_sched *sched)
{
	if (!sched->saved_states)
		return false;

	sched->saved_states--;
	sched->state = sched->saved[sched->saved_states];

	/* continue with next counter: */
	clear_bit(sched->state.counter++, sched->state.used);

	return true;
}

740 741 742 743
/*
 * Select a counter for the current event to schedule. Return true on
 * success.
 */
744
static bool __perf_sched_find_counter(struct perf_sched *sched)
745 746 747 748 749 750 751 752 753 754
{
	struct event_constraint *c;
	int idx;

	if (!sched->state.unassigned)
		return false;

	if (sched->state.event >= sched->max_events)
		return false;

755
	c = sched->constraints[sched->state.event];
756
	/* Prefer fixed purpose counters */
757 758
	if (c->idxmsk64 & (~0ULL << INTEL_PMC_IDX_FIXED)) {
		idx = INTEL_PMC_IDX_FIXED;
759
		for_each_set_bit_from(idx, c->idxmsk, X86_PMC_IDX_MAX) {
760 761 762 763
			if (!__test_and_set_bit(idx, sched->state.used))
				goto done;
		}
	}
764

765 766
	/* Grab the first unused counter starting with idx */
	idx = sched->state.counter;
767
	for_each_set_bit_from(idx, c->idxmsk, INTEL_PMC_IDX_FIXED) {
768 769 770 771
		if (!__test_and_set_bit(idx, sched->state.used)) {
			if (sched->state.nr_gp++ >= sched->max_gp)
				return false;

772
			goto done;
773
		}
774 775
	}

776 777 778 779
	return false;

done:
	sched->state.counter = idx;
780

781 782 783 784 785 786 787 788 789 790 791 792 793
	if (c->overlap)
		perf_sched_save_state(sched);

	return true;
}

static bool perf_sched_find_counter(struct perf_sched *sched)
{
	while (!__perf_sched_find_counter(sched)) {
		if (!perf_sched_restore_state(sched))
			return false;
	}

794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817
	return true;
}

/*
 * Go through all unassigned events and find the next one to schedule.
 * Take events with the least weight first. Return true on success.
 */
static bool perf_sched_next_event(struct perf_sched *sched)
{
	struct event_constraint *c;

	if (!sched->state.unassigned || !--sched->state.unassigned)
		return false;

	do {
		/* next event */
		sched->state.event++;
		if (sched->state.event >= sched->max_events) {
			/* next weight */
			sched->state.event = 0;
			sched->state.weight++;
			if (sched->state.weight > sched->max_weight)
				return false;
		}
818
		c = sched->constraints[sched->state.event];
819 820 821 822 823 824 825 826 827 828
	} while (c->weight != sched->state.weight);

	sched->state.counter = 0;	/* start with first counter */

	return true;
}

/*
 * Assign a counter for each event.
 */
829
int perf_assign_events(struct event_constraint **constraints, int n,
830
			int wmin, int wmax, int gpmax, int *assign)
831 832 833
{
	struct perf_sched sched;

834
	perf_sched_init(&sched, constraints, n, wmin, wmax, gpmax);
835 836 837 838 839 840 841 842 843 844

	do {
		if (!perf_sched_find_counter(&sched))
			break;	/* failed */
		if (assign)
			assign[sched.state.event] = sched.state.counter;
	} while (perf_sched_next_event(&sched));

	return sched.state.unassigned;
}
845
EXPORT_SYMBOL_GPL(perf_assign_events);
846

847
int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
848
{
849
	struct event_constraint *c;
850
	unsigned long used_mask[BITS_TO_LONGS(X86_PMC_IDX_MAX)];
851
	struct perf_event *e;
852
	int i, wmin, wmax, unsched = 0;
853 854 855 856
	struct hw_perf_event *hwc;

	bitmap_zero(used_mask, X86_PMC_IDX_MAX);

857 858 859
	if (x86_pmu.start_scheduling)
		x86_pmu.start_scheduling(cpuc);

860
	for (i = 0, wmin = X86_PMC_IDX_MAX, wmax = 0; i < n; i++) {
861
		cpuc->event_constraint[i] = NULL;
862
		c = x86_pmu.get_event_constraints(cpuc, i, cpuc->event_list[i]);
863
		cpuc->event_constraint[i] = c;
864

865 866
		wmin = min(wmin, c->weight);
		wmax = max(wmax, c->weight);
867 868
	}

869 870 871
	/*
	 * fastpath, try to reuse previous register
	 */
872
	for (i = 0; i < n; i++) {
873
		hwc = &cpuc->event_list[i]->hw;
874
		c = cpuc->event_constraint[i];
875 876 877 878 879 880

		/* never assigned */
		if (hwc->idx == -1)
			break;

		/* constraint still honored */
881
		if (!test_bit(hwc->idx, c->idxmsk))
882 883 884 885 886 887
			break;

		/* not already used */
		if (test_bit(hwc->idx, used_mask))
			break;

888
		__set_bit(hwc->idx, used_mask);
889 890 891 892
		if (assign)
			assign[i] = hwc->idx;
	}

893
	/* slow path */
894
	if (i != n) {
895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910
		int gpmax = x86_pmu.num_counters;

		/*
		 * Do not allow scheduling of more than half the available
		 * generic counters.
		 *
		 * This helps avoid counter starvation of sibling thread by
		 * ensuring at most half the counters cannot be in exclusive
		 * mode. There is no designated counters for the limits. Any
		 * N/2 counters can be used. This helps with events with
		 * specific counter constraints.
		 */
		if (is_ht_workaround_enabled() && !cpuc->is_fake &&
		    READ_ONCE(cpuc->excl_cntrs->exclusive_present))
			gpmax /= 2;

911
		unsched = perf_assign_events(cpuc->event_constraint, n, wmin,
912
					     wmax, gpmax, assign);
913
	}
914

915
	/*
916 917 918 919 920 921 922 923
	 * In case of success (unsched = 0), mark events as committed,
	 * so we do not put_constraint() in case new events are added
	 * and fail to be scheduled
	 *
	 * We invoke the lower level commit callback to lock the resource
	 *
	 * We do not need to do all of this in case we are called to
	 * validate an event group (assign == NULL)
924
	 */
925
	if (!unsched && assign) {
926 927 928
		for (i = 0; i < n; i++) {
			e = cpuc->event_list[i];
			e->hw.flags |= PERF_X86_EVENT_COMMITTED;
929
			if (x86_pmu.commit_scheduling)
930
				x86_pmu.commit_scheduling(cpuc, i, assign[i]);
931
		}
932
	} else {
933
		for (i = 0; i < n; i++) {