1e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat/* 2e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * blktrace output analysis: generate a timeline & gather statistics 3e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * 4e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle@hp.com> 5e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * 6e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * This program is free software; you can redistribute it and/or modify 7e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * it under the terms of the GNU General Public License as published by 8e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * the Free Software Foundation; either version 2 of the License, or 9e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * (at your option) any later version. 10e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * 11e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * This program is distributed in the hope that it will be useful, 12e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * but WITHOUT ANY WARRANTY; without even the implied warranty of 13e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * GNU General Public License for more details. 15e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * 16e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * You should have received a copy of the GNU General Public License 17e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * along with this program; if not, write to the Free Software 18e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 19e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * 20e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat */ 21e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#include <stdio.h> 22e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#include "globals.h" 23e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 24e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatint rb_insert(struct rb_root *root, struct io *iop) 25e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 26e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct io *__iop; 27e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent = NULL; 28e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node **p = &root->rb_node; 29e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __u64 __s, s = BIT_START(iop); 30e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 31e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (*p) { 32e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = *p; 33e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __iop = rb_entry(parent, struct io, rb_node); 34e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __s = BIT_START(__iop); 35e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 36e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (s < __s) 37e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat p = &(*p)->rb_left; 38e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else if (s > __s) 39e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat p = &(*p)->rb_right; 40e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 41e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return 0; 42e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 43e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 44e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_link_node(&iop->rb_node, parent, p); 45e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_insert_color(&iop->rb_node, root); 46e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return 1; 47e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 48e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 49e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct io *rb_find_sec(struct rb_root *root, __u64 sec) 50e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 51e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct io *__iop; 52e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *n = root->rb_node; 53e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 54e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (n) { 55e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __iop = rb_entry(n, struct io, rb_node); 56e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (sec < BIT_START(__iop)) 57e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = n->rb_left; 58e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else if (sec >= BIT_END(__iop)) 59e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = n->rb_right; 60e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 61e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return __iop; 62e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 63e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 64e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 65e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 66e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 67e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatvoid rb_foreach(struct rb_node *n, struct io *iop, 68e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat void (*fnc)(struct io *iop, struct io *this), 69e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct list_head *head) 70e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 71e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (n) { 72e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct io *this = rb_entry(n, struct io, rb_node); 73e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __u64 iop_s = BIT_START(iop), iop_e = BIT_END(iop); 74e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __u64 this_s = BIT_START(this), this_e = BIT_END(this); 75e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 76e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((iop_s <= this_s) && (this_e <= iop_e)) { 77e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (fnc) fnc(iop, this); 78e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (head) 79e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat list_add_tail(&this->f_head, head); 80e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 81e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (iop_s < this_s) 82e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_foreach(n->rb_left, iop, fnc, head); 83e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (this_e < iop_e) 84e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_foreach(n->rb_right, iop, fnc, head); 85e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 86e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 87