[linux-2.6-block.git] / tools / perf / util / ordered-events.c

#include <linux/list.h>
#include <linux/compiler.h>
#include <linux/string.h>
#include "ordered-events.h"
#include "evlist.h"
#include "session.h"
#include "asm/bug.h"
#include "debug.h"

#define pr_N(n, fmt, ...) \
	eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__)

#define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__)

static void queue_event(struct ordered_events *oe, struct ordered_event *new)
{
	struct ordered_event *last = oe->last;
	u64 timestamp = new->timestamp;
	struct list_head *p;

	++oe->nr_events;
	oe->last = new;

	pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events);

	if (!last) {
		list_add(&new->list, &oe->events);
		oe->max_timestamp = timestamp;
		return;
	}

	/*
	 * last event might point to some random place in the list as it's
	 * the last queued event. We expect that the new event is close to
	 * this.
	 */
	if (last->timestamp <= timestamp) {
		while (last->timestamp <= timestamp) {
			p = last->list.next;
			if (p == &oe->events) {
				list_add_tail(&new->list, &oe->events);
				oe->max_timestamp = timestamp;
				return;
			}
			last = list_entry(p, struct ordered_event, list);
		}
		list_add_tail(&new->list, &last->list);
	} else {
		while (last->timestamp > timestamp) {
			p = last->list.prev;
			if (p == &oe->events) {
				list_add(&new->list, &oe->events);
				return;
			}
			last = list_entry(p, struct ordered_event, list);
		}
		list_add(&new->list, &last->list);
	}
}

static union perf_event *__dup_event(struct ordered_events *oe,
				     union perf_event *event)
{
	union perf_event *new_event = NULL;

	if (oe->cur_alloc_size < oe->max_alloc_size) {
		new_event = memdup(event, event->header.size);
		if (new_event)
			oe->cur_alloc_size += event->header.size;
	}

	return new_event;
}

static union perf_event *dup_event(struct ordered_events *oe,
				   union perf_event *event)
{
	return oe->copy_on_queue ? __dup_event(oe, event) : event;
}

static void free_dup_event(struct ordered_events *oe, union perf_event *event)
{
	if (oe->copy_on_queue) {
		oe->cur_alloc_size -= event->header.size;
		free(event);
	}
}

#define MAX_SAMPLE_BUFFER	(64 * 1024 / sizeof(struct ordered_event))
static struct ordered_event *alloc_event(struct ordered_events *oe,
					 union perf_event *event)
{
	struct list_head *cache = &oe->cache;
	struct ordered_event *new = NULL;
	union perf_event *new_event;

	new_event = dup_event(oe, event);
	if (!new_event)
		return NULL;

	if (!list_empty(cache)) {
		new = list_entry(cache->next, struct ordered_event, list);
		list_del(&new->list);
	} else if (oe->buffer) {
		new = oe->buffer + oe->buffer_idx;
		if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
			oe->buffer = NULL;
	} else if (oe->cur_alloc_size < oe->max_alloc_size) {
		size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);

		oe->buffer = malloc(size);
		if (!oe->buffer) {
			free_dup_event(oe, new_event);
			return NULL;
		}

		pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
		   oe->cur_alloc_size, size, oe->max_alloc_size);

		oe->cur_alloc_size += size;
		list_add(&oe->buffer->list, &oe->to_free);

		/* First entry is abused to maintain the to_free list. */
		oe->buffer_idx = 2;
		new = oe->buffer + 1;
	} else {
		pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
	}

	new->event = new_event;
	return new;
}

static struct ordered_event *
ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
		    union perf_event *event)
{
	struct ordered_event *new;

	new = alloc_event(oe, event);
	if (new) {
		new->timestamp = timestamp;
		queue_event(oe, new);
	}

	return new;
}

void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
{
	list_move(&event->list, &oe->cache);
	oe->nr_events--;
	free_dup_event(oe, event->event);
}

int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
			  struct perf_sample *sample, u64 file_offset)
{
	u64 timestamp = sample->time;
	struct ordered_event *oevent;

	if (!timestamp || timestamp == ~0ULL)
		return -ETIME;

	if (timestamp < oe->last_flush) {
		pr_oe_time(timestamp,      "out of order event\n");
		pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n",
			   oe->last_flush_type);

		oe->evlist->stats.nr_unordered_events++;
	}

	oevent = ordered_events__new_event(oe, timestamp, event);
	if (!oevent) {
		ordered_events__flush(oe, OE_FLUSH__HALF);
		oevent = ordered_events__new_event(oe, timestamp, event);
	}

	if (!oevent)
		return -ENOMEM;

	oevent->file_offset = file_offset;
	return 0;
}

static int __ordered_events__flush(struct ordered_events *oe)
{
	struct list_head *head = &oe->events;
	struct ordered_event *tmp, *iter;
	struct perf_sample sample;
	u64 limit = oe->next_flush;
	u64 last_ts = oe->last ? oe->last->timestamp : 0ULL;
	bool show_progress = limit == ULLONG_MAX;
	struct ui_progress prog;
	int ret;

	if (!limit)
		return 0;

	if (show_progress)
		ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");

	list_for_each_entry_safe(iter, tmp, head, list) {
		if (session_done())
			return 0;

		if (iter->timestamp > limit)
			break;

		ret = perf_evlist__parse_sample(oe->evlist, iter->event, &sample);
		if (ret)
			pr_err("Can't parse sample, err = %d\n", ret);
		else {
			ret = oe->deliver(oe, iter, &sample);
			if (ret)
				return ret;
		}

		ordered_events__delete(oe, iter);
		oe->last_flush = iter->timestamp;

		if (show_progress)
			ui_progress__update(&prog, 1);
	}

	if (list_empty(head))
		oe->last = NULL;
	else if (last_ts <= limit)
		oe->last = list_entry(head->prev, struct ordered_event, list);

	return 0;
}

int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
{
	static const char * const str[] = {
		"NONE",
		"FINAL",
		"ROUND",
		"HALF ",
	};
	int err;

	if (oe->nr_events == 0)
		return 0;

	switch (how) {
	case OE_FLUSH__FINAL:
		oe->next_flush = ULLONG_MAX;
		break;

	case OE_FLUSH__HALF:
	{
		struct ordered_event *first, *last;
		struct list_head *head = &oe->events;

		first = list_entry(head->next, struct ordered_event, list);
		last = oe->last;

		/* Warn if we are called before any event got allocated. */
		if (WARN_ONCE(!last || list_empty(head), "empty queue"))
			return 0;

		oe->next_flush  = first->timestamp;
		oe->next_flush += (last->timestamp - first->timestamp) / 2;
		break;
	}

	case OE_FLUSH__ROUND:
	case OE_FLUSH__NONE:
	default:
		break;
	};

	pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE  %s, nr_events %u\n",
		   str[how], oe->nr_events);
	pr_oe_time(oe->max_timestamp, "max_timestamp\n");

	err = __ordered_events__flush(oe);

	if (!err) {
		if (how == OE_FLUSH__ROUND)
			oe->next_flush = oe->max_timestamp;

		oe->last_flush_type = how;
	}

	pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
		   str[how], oe->nr_events);
	pr_oe_time(oe->last_flush, "last_flush\n");

	return err;
}

void ordered_events__init(struct ordered_events *oe, struct machines *machines,
			  struct perf_evlist *evlist, struct perf_tool *tool,
			  ordered_events__deliver_t deliver)
{
	INIT_LIST_HEAD(&oe->events);
	INIT_LIST_HEAD(&oe->cache);
	INIT_LIST_HEAD(&oe->to_free);
	oe->max_alloc_size = (u64) -1;
	oe->cur_alloc_size = 0;
	oe->evlist	   = evlist;
	oe->machines	   = machines;
	oe->tool	   = tool;
	oe->deliver	   = deliver;
}

void ordered_events__free(struct ordered_events *oe)
{
	while (!list_empty(&oe->to_free)) {
		struct ordered_event *event;

		event = list_entry(oe->to_free.next, struct ordered_event, list);
		list_del(&event->list);
		free_dup_event(oe, event->event);
		free(event);
	}
}
Commit	Line	Data
5f86b80b	1	#include <linux/list.h>
cee3ab9c	2	#include <linux/compiler.h>
54bf53b1	3	#include <linux/string.h>
5f86b80b JO	4	#include "ordered-events.h"
	5	#include "evlist.h"
	6	#include "session.h"
	7	#include "asm/bug.h"
	8	#include "debug.h"
	9
cee3ab9c JO	10	#define pr_N(n, fmt, ...) \
	11	eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__)
	12
	13	#define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__)
	14
5f86b80b JO	15	static void queue_event(struct ordered_events oe, struct ordered_event new)
	16	{
	17	struct ordered_event *last = oe->last;
	18	u64 timestamp = new->timestamp;
	19	struct list_head *p;
	20
	21	++oe->nr_events;
	22	oe->last = new;
	23
cee3ab9c JO	24	pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events);
cee3ab9c JO	25
5f86b80b JO	26	if (!last) {
	27	list_add(&new->list, &oe->events);
	28	oe->max_timestamp = timestamp;
	29	return;
	30	}
	31
	32	/*
	33	* last event might point to some random place in the list as it's
	34	* the last queued event. We expect that the new event is close to
	35	* this.
	36	*/
	37	if (last->timestamp <= timestamp) {
	38	while (last->timestamp <= timestamp) {
	39	p = last->list.next;
	40	if (p == &oe->events) {
	41	list_add_tail(&new->list, &oe->events);
	42	oe->max_timestamp = timestamp;
	43	return;
	44	}
	45	last = list_entry(p, struct ordered_event, list);
	46	}
	47	list_add_tail(&new->list, &last->list);
	48	} else {
	49	while (last->timestamp > timestamp) {
	50	p = last->list.prev;
	51	if (p == &oe->events) {
	52	list_add(&new->list, &oe->events);
	53	return;
	54	}
	55	last = list_entry(p, struct ordered_event, list);
	56	}
	57	list_add(&new->list, &last->list);
	58	}
	59	}
	60
54bf53b1 AY	61	static union perf_event __dup_event(struct ordered_events oe,
	62	union perf_event *event)
	63	{
	64	union perf_event *new_event = NULL;
	65
	66	if (oe->cur_alloc_size < oe->max_alloc_size) {
	67	new_event = memdup(event, event->header.size);
	68	if (new_event)
	69	oe->cur_alloc_size += event->header.size;
	70	}
	71
	72	return new_event;
	73	}
	74
	75	static union perf_event dup_event(struct ordered_events oe,
	76	union perf_event *event)
	77	{
	78	return oe->copy_on_queue ? __dup_event(oe, event) : event;
	79	}
	80
	81	static void free_dup_event(struct ordered_events oe, union perf_event event)
	82	{
	83	if (oe->copy_on_queue) {
	84	oe->cur_alloc_size -= event->header.size;
	85	free(event);
	86	}
	87	}
	88
5f86b80b	89	#define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event))
54bf53b1 AY	90	static struct ordered_event alloc_event(struct ordered_events oe,
54bf53b1 AY	91	union perf_event *event)
5f86b80b JO	92	{
	93	struct list_head *cache = &oe->cache;
	94	struct ordered_event *new = NULL;
54bf53b1 AY	95	union perf_event *new_event;
	96
	97	new_event = dup_event(oe, event);
	98	if (!new_event)
	99	return NULL;
5f86b80b JO	100
	101	if (!list_empty(cache)) {
	102	new = list_entry(cache->next, struct ordered_event, list);
	103	list_del(&new->list);
	104	} else if (oe->buffer) {
	105	new = oe->buffer + oe->buffer_idx;
	106	if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
	107	oe->buffer = NULL;
	108	} else if (oe->cur_alloc_size < oe->max_alloc_size) {
	109	size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
	110
	111	oe->buffer = malloc(size);
54bf53b1 AY	112	if (!oe->buffer) {
54bf53b1 AY	113	free_dup_event(oe, new_event);
5f86b80b	114	return NULL;
54bf53b1	115	}
5f86b80b	116
cee3ab9c JO	117	pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
	118	oe->cur_alloc_size, size, oe->max_alloc_size);
	119
5f86b80b JO	120	oe->cur_alloc_size += size;
	121	list_add(&oe->buffer->list, &oe->to_free);
	122
	123	/* First entry is abused to maintain the to_free list. */
	124	oe->buffer_idx = 2;
	125	new = oe->buffer + 1;
cee3ab9c JO	126	} else {
cee3ab9c JO	127	pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
5f86b80b JO	128	}
5f86b80b JO	129
54bf53b1	130	new->event = new_event;
5f86b80b JO	131	return new;
	132	}
	133
4a6b362f ACM	134	static struct ordered_event *
4a6b362f ACM	135	ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
54bf53b1	136	union perf_event *event)
5f86b80b JO	137	{
	138	struct ordered_event *new;
	139
54bf53b1	140	new = alloc_event(oe, event);
5f86b80b JO	141	if (new) {
	142	new->timestamp = timestamp;
	143	queue_event(oe, new);
	144	}
	145
	146	return new;
	147	}
	148
	149	void ordered_events__delete(struct ordered_events oe, struct ordered_event event)
	150	{
fa4e5c67	151	list_move(&event->list, &oe->cache);
5f86b80b	152	oe->nr_events--;
54bf53b1	153	free_dup_event(oe, event->event);
5f86b80b JO	154	}
5f86b80b JO	155
4a6b362f ACM	156	int ordered_events__queue(struct ordered_events oe, union perf_event event,
	157	struct perf_sample *sample, u64 file_offset)
	158	{
	159	u64 timestamp = sample->time;
	160	struct ordered_event *oevent;
	161
	162	if (!timestamp \|\| timestamp == ~0ULL)
	163	return -ETIME;
	164
	165	if (timestamp < oe->last_flush) {
	166	pr_oe_time(timestamp, "out of order event\n");
	167	pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n",
	168	oe->last_flush_type);
	169
	170	oe->evlist->stats.nr_unordered_events++;
	171	}
	172
	173	oevent = ordered_events__new_event(oe, timestamp, event);
	174	if (!oevent) {
	175	ordered_events__flush(oe, OE_FLUSH__HALF);
	176	oevent = ordered_events__new_event(oe, timestamp, event);
	177	}
	178
	179	if (!oevent)
	180	return -ENOMEM;
	181
	182	oevent->file_offset = file_offset;
	183	return 0;
	184	}
	185
b7b61cbe	186	static int __ordered_events__flush(struct ordered_events *oe)
5f86b80b	187	{
5f86b80b JO	188	struct list_head *head = &oe->events;
	189	struct ordered_event tmp, iter;
	190	struct perf_sample sample;
	191	u64 limit = oe->next_flush;
	192	u64 last_ts = oe->last ? oe->last->timestamp : 0ULL;
	193	bool show_progress = limit == ULLONG_MAX;
	194	struct ui_progress prog;
	195	int ret;
	196
28083681	197	if (!limit)
5f86b80b JO	198	return 0;
	199
	200	if (show_progress)
	201	ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");
	202
	203	list_for_each_entry_safe(iter, tmp, head, list) {
	204	if (session_done())
	205	return 0;
	206
	207	if (iter->timestamp > limit)
	208	break;
	209
b7b61cbe	210	ret = perf_evlist__parse_sample(oe->evlist, iter->event, &sample);
5f86b80b JO	211	if (ret)
	212	pr_err("Can't parse sample, err = %d\n", ret);
	213	else {
d10eb1eb	214	ret = oe->deliver(oe, iter, &sample);
5f86b80b JO	215	if (ret)
	216	return ret;
	217	}
	218
	219	ordered_events__delete(oe, iter);
	220	oe->last_flush = iter->timestamp;
	221
	222	if (show_progress)
	223	ui_progress__update(&prog, 1);
	224	}
	225
	226	if (list_empty(head))
	227	oe->last = NULL;
	228	else if (last_ts <= limit)
	229	oe->last = list_entry(head->prev, struct ordered_event, list);
	230
	231	return 0;
	232	}
	233
b7b61cbe	234	int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
5f86b80b	235	{
cee3ab9c	236	static const char * const str[] = {
b0a45203	237	"NONE",
cee3ab9c JO	238	"FINAL",
	239	"ROUND",
	240	"HALF ",
	241	};
5f86b80b JO	242	int err;
5f86b80b JO	243
28083681 ACM	244	if (oe->nr_events == 0)
	245	return 0;
	246
5f86b80b JO	247	switch (how) {
	248	case OE_FLUSH__FINAL:
	249	oe->next_flush = ULLONG_MAX;
	250	break;
	251
	252	case OE_FLUSH__HALF:
	253	{
	254	struct ordered_event first, last;
	255	struct list_head *head = &oe->events;
	256
	257	first = list_entry(head->next, struct ordered_event, list);
	258	last = oe->last;
	259
	260	/* Warn if we are called before any event got allocated. */
	261	if (WARN_ONCE(!last \|\| list_empty(head), "empty queue"))
	262	return 0;
	263
	264	oe->next_flush = first->timestamp;
	265	oe->next_flush += (last->timestamp - first->timestamp) / 2;
	266	break;
	267	}
	268
	269	case OE_FLUSH__ROUND:
b0a45203	270	case OE_FLUSH__NONE:
5f86b80b JO	271	default:
	272	break;
	273	};
	274
cee3ab9c JO	275	pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n",
	276	str[how], oe->nr_events);
	277	pr_oe_time(oe->max_timestamp, "max_timestamp\n");
	278
b7b61cbe	279	err = __ordered_events__flush(oe);
5f86b80b JO	280
	281	if (!err) {
	282	if (how == OE_FLUSH__ROUND)
	283	oe->next_flush = oe->max_timestamp;
b0a45203 JO	284
b0a45203 JO	285	oe->last_flush_type = how;
5f86b80b JO	286	}
5f86b80b JO	287
cee3ab9c JO	288	pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
	289	str[how], oe->nr_events);
	290	pr_oe_time(oe->last_flush, "last_flush\n");
	291
5f86b80b JO	292	return err;
5f86b80b JO	293	}
36522f5c	294
b7b61cbe	295	void ordered_events__init(struct ordered_events oe, struct machines machines,
d10eb1eb ACM	296	struct perf_evlist evlist, struct perf_tool tool,
d10eb1eb ACM	297	ordered_events__deliver_t deliver)
36522f5c JO	298	{
	299	INIT_LIST_HEAD(&oe->events);
	300	INIT_LIST_HEAD(&oe->cache);
	301	INIT_LIST_HEAD(&oe->to_free);
	302	oe->max_alloc_size = (u64) -1;
	303	oe->cur_alloc_size = 0;
b7b61cbe ACM	304	oe->evlist = evlist;
	305	oe->machines = machines;
	306	oe->tool = tool;
d10eb1eb	307	oe->deliver = deliver;
36522f5c	308	}
adc56ed1 JO	309
	310	void ordered_events__free(struct ordered_events *oe)
	311	{
	312	while (!list_empty(&oe->to_free)) {
	313	struct ordered_event *event;
	314
	315	event = list_entry(oe->to_free.next, struct ordered_event, list);
	316	list_del(&event->list);
54bf53b1	317	free_dup_event(oe, event->event);
adc56ed1 JO	318	free(event);
	319	}
	320	}