// SPDX-License-Identifier: GPL-2.0#include "block-range.h"#include "annotate.h"#include <assert.h>#include <stdlib.h> static struct {	struct rb_root root;	u64 blocks;} block_ranges; static void block_range__debug(void){#ifndef NDEBUG	struct rb_node *rb;	u64 old = 0; /* NULL isn't executable */ 	for (rb = rb_first(&block_ranges.root); rb; rb = rb_next(rb)) {		struct block_range *entry = rb_entry(rb, struct block_range, node); 		assert(old < entry->start);		assert(entry->start <= entry->end); /* single instruction block; jump to a jump */ 		old = entry->end;	}#endif} struct block_range *block_range__find(u64 addr){	struct rb_node **p = &block_ranges.root.rb_node;	struct rb_node *parent = NULL;	struct block_range *entry; 	while (*p != NULL) {		parent = *p;		entry = rb_entry(parent, struct block_range, node); 		if (addr < entry->start)			p = &parent->rb_left;		else if (addr > entry->end)			p = &parent->rb_right;		else			return entry;	} 	return NULL;} static inline void rb_link_left_of_node(struct rb_node *left, struct rb_node *node){	struct rb_node **p = &node->rb_left;	while (*p) {		node = *p;		p = &node->rb_right;	}	rb_link_node(left, node, p);} static inline void rb_link_right_of_node(struct rb_node *right, struct rb_node *node){	struct rb_node **p = &node->rb_right;	while (*p) {		node = *p;		p = &node->rb_left;	}	rb_link_node(right, node, p);} /** * block_range__create * @start: branch target starting this basic block * @end:   branch ending this basic block * * Create all the required block ranges to precisely span the given range. */struct block_range_iter block_range__create(u64 start, u64 end){	struct rb_node **p = &block_ranges.root.rb_node;	struct rb_node *n, *parent = NULL;	struct block_range *next, *entry = NULL;	struct block_range_iter iter = { NULL, NULL }; 	while (*p != NULL) {		parent = *p;		entry = rb_entry(parent, struct block_range, node); 		if (start < entry->start)			p = &parent->rb_left;		else if (start > entry->end)			p = &parent->rb_right;		else			break;	} 	/*	 * Didn't find anything.. there's a hole at @start, however @end might	 * be inside/behind the next range.	 */	if (!*p) {		if (!entry) /* tree empty */			goto do_whole; 		/*		 * If the last node is before, advance one to find the next.		 */		n = parent;		if (entry->end < start) {			n = rb_next(n);			if (!n)				goto do_whole;		}		next = rb_entry(n, struct block_range, node); 		if (next->start <= end) { /* add head: [start...][n->start...] */			struct block_range *head = malloc(sizeof(struct block_range));			if (!head)				return iter; 			*head = (struct block_range){				.start		= start,				.end		= next->start - 1,				.is_target	= 1,				.is_branch	= 0,			}; 			rb_link_left_of_node(&head->node, &next->node);			rb_insert_color(&head->node, &block_ranges.root);			block_range__debug(); 			iter.start = head;			goto do_tail;		} do_whole:		/*		 * The whole [start..end] range is non-overlapping.		 */		entry = malloc(sizeof(struct block_range));		if (!entry)			return iter; 		*entry = (struct block_range){			.start		= start,			.end		= end,			.is_target	= 1,			.is_branch	= 1,		}; 		rb_link_node(&entry->node, parent, p);		rb_insert_color(&entry->node, &block_ranges.root);		block_range__debug(); 		iter.start = entry;		iter.end   = entry;		goto done;	} 	/*	 * We found a range that overlapped with ours, split if needed.	 */	if (entry->start < start) { /* split: [e->start...][start...] */		struct block_range *head = malloc(sizeof(struct block_range));		if (!head)			return iter; 		*head = (struct block_range){			.start		= entry->start,			.end		= start - 1,			.is_target	= entry->is_target,			.is_branch	= 0, 			.coverage	= entry->coverage,			.entry		= entry->entry,		}; 		entry->start		= start;		entry->is_target	= 1;		entry->entry		= 0; 		rb_link_left_of_node(&head->node, &entry->node);		rb_insert_color(&head->node, &block_ranges.root);		block_range__debug(); 	} else if (entry->start == start)		entry->is_target = 1; 	iter.start = entry; do_tail:	/*	 * At this point we've got: @iter.start = [@start...] but @end can still be	 * inside or beyond it.	 */	entry = iter.start;	for (;;) {		/*		 * If @end is inside @entry, split.		 */		if (end < entry->end) { /* split: [...end][...e->end] */			struct block_range *tail = malloc(sizeof(struct block_range));			if (!tail)				return iter; 			*tail = (struct block_range){				.start		= end + 1,				.end		= entry->end,				.is_target	= 0,				.is_branch	= entry->is_branch, 				.coverage	= entry->coverage,				.taken		= entry->taken,				.pred		= entry->pred,			}; 			entry->end		= end;			entry->is_branch	= 1;			entry->taken		= 0;			entry->pred		= 0; 			rb_link_right_of_node(&tail->node, &entry->node);			rb_insert_color(&tail->node, &block_ranges.root);			block_range__debug(); 			iter.end = entry;			goto done;		} 		/*		 * If @end matches @entry, done		 */		if (end == entry->end) {			entry->is_branch = 1;			iter.end = entry;			goto done;		} 		next = block_range__next(entry);		if (!next)			goto add_tail; 		/*		 * If @end is in beyond @entry but not inside @next, add tail.		 */		if (end < next->start) { /* add tail: [...e->end][...end] */			struct block_range *tail;add_tail:			tail = malloc(sizeof(struct block_range));			if (!tail)				return iter; 			*tail = (struct block_range){				.start		= entry->end + 1,				.end		= end,				.is_target	= 0,				.is_branch	= 1,			}; 			rb_link_right_of_node(&tail->node, &entry->node);			rb_insert_color(&tail->node, &block_ranges.root);			block_range__debug(); 			iter.end = tail;			goto done;		} 		/*		 * If there is a hole between @entry and @next, fill it.		 */		if (entry->end + 1 != next->start) {			struct block_range *hole = malloc(sizeof(struct block_range));			if (!hole)				return iter; 			*hole = (struct block_range){				.start		= entry->end + 1,				.end		= next->start - 1,				.is_target	= 0,				.is_branch	= 0,			}; 			rb_link_left_of_node(&hole->node, &next->node);			rb_insert_color(&hole->node, &block_ranges.root);			block_range__debug();		} 		entry = next;	} done:	assert(iter.start->start == start && iter.start->is_target);	assert(iter.end->end == end && iter.end->is_branch); 	block_ranges.blocks++; 	return iter;}  /* * Compute coverage as: * *    br->coverage / br->sym->max_coverage * * This ensures each symbol has a 100% spot, to reflect that each symbol has a * most covered section. * * Returns [0-1] for coverage and -1 if we had no data what so ever or the * symbol does not exist. */double block_range__coverage(struct block_range *br){	struct symbol *sym;	struct annotated_branch *branch; 	if (!br) {		if (block_ranges.blocks)			return 0; 		return -1;	} 	sym = br->sym;	if (!sym)		return -1; 	branch = symbol__annotation(sym)->branch;	if (!branch)		return -1; 	return (double)br->coverage / branch->max_coverage;}