[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 "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->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;
	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 = oe->deliver(oe, iter);
		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);

	if (show_progress)
		ui_progress__finish();

	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, 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->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);
	}
}

void ordered_events__reinit(struct ordered_events *oe)
{
	ordered_events__deliver_t old_deliver = oe->deliver;

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