[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;
}

struct ordered_event *
ordered_events__new(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);
}

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 = machines__deliver_event(oe->machines, oe->evlist, iter->event,
						      &sample, oe->tool, iter->file_offset);
			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)
{
	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;
}

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
	134	struct ordered_event *
54bf53b1 AY	135	ordered_events__new(struct ordered_events *oe, u64 timestamp,
54bf53b1 AY	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
b7b61cbe	156	static int __ordered_events__flush(struct ordered_events *oe)
5f86b80b	157	{
5f86b80b JO	158	struct list_head *head = &oe->events;
	159	struct ordered_event tmp, iter;
	160	struct perf_sample sample;
	161	u64 limit = oe->next_flush;
	162	u64 last_ts = oe->last ? oe->last->timestamp : 0ULL;
	163	bool show_progress = limit == ULLONG_MAX;
	164	struct ui_progress prog;
	165	int ret;
	166
28083681	167	if (!limit)
5f86b80b JO	168	return 0;
	169
	170	if (show_progress)
	171	ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");
	172
	173	list_for_each_entry_safe(iter, tmp, head, list) {
	174	if (session_done())
	175	return 0;
	176
	177	if (iter->timestamp > limit)
	178	break;
	179
b7b61cbe	180	ret = perf_evlist__parse_sample(oe->evlist, iter->event, &sample);
5f86b80b JO	181	if (ret)
	182	pr_err("Can't parse sample, err = %d\n", ret);
	183	else {
b7b61cbe ACM	184	ret = machines__deliver_event(oe->machines, oe->evlist, iter->event,
b7b61cbe ACM	185	&sample, oe->tool, iter->file_offset);
5f86b80b JO	186	if (ret)
	187	return ret;
	188	}
	189
	190	ordered_events__delete(oe, iter);
	191	oe->last_flush = iter->timestamp;
	192
	193	if (show_progress)
	194	ui_progress__update(&prog, 1);
	195	}
	196
	197	if (list_empty(head))
	198	oe->last = NULL;
	199	else if (last_ts <= limit)
	200	oe->last = list_entry(head->prev, struct ordered_event, list);
	201
	202	return 0;
	203	}
	204
b7b61cbe	205	int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
5f86b80b	206	{
cee3ab9c	207	static const char * const str[] = {
b0a45203	208	"NONE",
cee3ab9c JO	209	"FINAL",
	210	"ROUND",
	211	"HALF ",
	212	};
5f86b80b JO	213	int err;
5f86b80b JO	214
28083681 ACM	215	if (oe->nr_events == 0)
	216	return 0;
	217
5f86b80b JO	218	switch (how) {
	219	case OE_FLUSH__FINAL:
	220	oe->next_flush = ULLONG_MAX;
	221	break;
	222
	223	case OE_FLUSH__HALF:
	224	{
	225	struct ordered_event first, last;
	226	struct list_head *head = &oe->events;
	227
	228	first = list_entry(head->next, struct ordered_event, list);
	229	last = oe->last;
	230
	231	/* Warn if we are called before any event got allocated. */
	232	if (WARN_ONCE(!last \|\| list_empty(head), "empty queue"))
	233	return 0;
	234
	235	oe->next_flush = first->timestamp;
	236	oe->next_flush += (last->timestamp - first->timestamp) / 2;
	237	break;
	238	}
	239
	240	case OE_FLUSH__ROUND:
b0a45203	241	case OE_FLUSH__NONE:
5f86b80b JO	242	default:
	243	break;
	244	};
	245
cee3ab9c JO	246	pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n",
	247	str[how], oe->nr_events);
	248	pr_oe_time(oe->max_timestamp, "max_timestamp\n");
	249
b7b61cbe	250	err = __ordered_events__flush(oe);
5f86b80b JO	251
	252	if (!err) {
	253	if (how == OE_FLUSH__ROUND)
	254	oe->next_flush = oe->max_timestamp;
b0a45203 JO	255
b0a45203 JO	256	oe->last_flush_type = how;
5f86b80b JO	257	}
5f86b80b JO	258
cee3ab9c JO	259	pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
	260	str[how], oe->nr_events);
	261	pr_oe_time(oe->last_flush, "last_flush\n");
	262
5f86b80b JO	263	return err;
5f86b80b JO	264	}
36522f5c	265
b7b61cbe ACM	266	void ordered_events__init(struct ordered_events oe, struct machines machines,
b7b61cbe ACM	267	struct perf_evlist evlist, struct perf_tool tool)
36522f5c JO	268	{
	269	INIT_LIST_HEAD(&oe->events);
	270	INIT_LIST_HEAD(&oe->cache);
	271	INIT_LIST_HEAD(&oe->to_free);
	272	oe->max_alloc_size = (u64) -1;
	273	oe->cur_alloc_size = 0;
b7b61cbe ACM	274	oe->evlist = evlist;
	275	oe->machines = machines;
	276	oe->tool = tool;
36522f5c	277	}
adc56ed1 JO	278
	279	void ordered_events__free(struct ordered_events *oe)
	280	{
	281	while (!list_empty(&oe->to_free)) {
	282	struct ordered_event *event;
	283
	284	event = list_entry(oe->to_free.next, struct ordered_event, list);
	285	list_del(&event->list);
54bf53b1	286	free_dup_event(oe, event->event);
adc56ed1 JO	287	free(event);
	288	}
	289	}