/* $Id: window.c,v 0.3 2003/10/16 10:38:32 kjc Exp $ */
/*
* Copyright (c) 1996-2000
* Sony Computer Science Laboratories, Inc. All rights reserved.
*
* Redistribution and use in source and binary forms of parts of or the
* whole original or derived work are permitted provided that the above
* copyright notice is retained and the original work is properly
* attributed to the author. The name of the author may not be used to
* endorse or promote products derived from this software without
* specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/
/*
window graph module:
keep track of the top ranking protocols or hosts within the
time window.
kjc@csl.sony.co.jp
96/06/11
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <net/if.h>
#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/if_ether.h>
#include <netinet/ip.h>
#include <netinet/tcp.h>
#include <netinet/udp.h>
#include <netdb.h>
#include <ctype.h>
#include <assert.h>
#include "ttt.h"
#include "ttt_node.h"
#include "ttt_account.h"
#include "ttt_window.h"
#define WG_MAX_ENTRIES 30 /* max list size */
#define WG_LIST(type) \
(((type) < TTTTYPE_HOST) ? &wg_proto_list : &wg_host_list)
static struct wg_entry wg_proto_list, wg_host_list;
static int wg_proto_entries, wg_host_entries;
static int wg_cur_time;
static struct wg_entry *wg_create(long type, long *id);
static void wg_delete(struct wg_entry *wgp);
static void wg_qinit(struct wg_entry *wgp);
static void wg_insq(struct wg_entry *prev, struct wg_entry *wgp);
static struct wg_entry *wg_remq(struct wg_entry *wgp);
static void wg_setrank(struct wg_entry *wgp);
static void w_insq(struct w_ent *prev, struct w_ent *ep);
static struct w_ent *w_remq(struct w_ent *ep);
static void w_insert(struct w_ent *head, struct w_ent *entry);
static void w_alloc_entries(int n);
static void w_init(void);
static void w_qinit(struct w_ent *head);
static void w_removesublist(struct w_ent *head, struct w_ent *list);
static int w_getmaxsize(struct w_ent *head);
static struct w_ent *w_getent(void);
static int w_countfree(void);
static void w_collectgarbage(void);
static void w_cleanup(void);
/* get the top n protocols or hosts during this interval. */
void stat_record(long type, int n)
{
struct t_node *np;
struct wg_entry *wgp;
int i;
for (i=0, np = node_getbiggest(type);
i<n && np != NULL; i++, np = node_getnext(np)) {
if ((wgp = wg_lookup(np->t_type, np->t_id)) == NULL)
break;
wg_record(wgp, np->t_size);
}
}
int stat_ranking(long type, struct wg_entry **rank_list, int n)
{
struct wg_entry *wgp;
int i, rval;
#ifdef PRINT_RANKING
printf("%s ranking at time %d\n",
(type < TTTTYPE_HOST) ? "proto" : "host", wg_cur_time);
#endif
if (n > WG_MAX_ENTRIES)
n = WG_MAX_ENTRIES;
for (i=0, wgp = wg_getbiggest(type); i<n && wgp != NULL;
i++, wgp = wg_getnext(wgp)) {
rank_list[i] = wgp;
#ifdef PRINT_RANKING
printf("rank[%d]: [%16s] %.2fMbps\n",
i, wgp->wg_name,
(double)wg_getmaxsize(wgp)/(1000.0*1000.0));
#endif
}
#ifdef PRINT_RANKING
printf("\n");
#endif
rval = i;
for (; i<n; i++)
rank_list[i] = NULL;
return rval;
}
/* dynamically assigned colors */
static char *default_colors[] = {
"red", "green", "blue", "cyan", "magenta", "yellow",
};
static char **color_list = default_colors;
static int color_list_size = sizeof(default_colors) / sizeof(char *);
static int color_index = 0;
#define MAX_COLORS 64
int stat_set_colors(const char *string)
{
char *cp;
int i, done = 0;
static char *colors[MAX_COLORS], *buf = NULL;;
if (buf)
free(buf);
buf = malloc(strlen(string)+1);
strcpy(buf, string);
cp = buf;
for (i=0; i < MAX_COLORS && !done && *cp; i++) {
while (isspace(*cp))
cp++;
if (!(*cp))
break;
colors[i] = cp;
while (isalnum(*cp))
cp++;
if (!(*cp))
done = 1;
*cp++ = '\0';
}
color_list = colors;
color_list_size = i;
color_index = 0;
return color_list_size;
}
int stat_update(struct wg_entry **ranking, struct wg_entry **old_ranking,
int *update_list, int n)
{
int i, j, count = 0;
int colors[32];
for (i=0; i<32; i++)
colors[i] = 0;
for (i=0; i<n; i++) {
if (ranking[i] == NULL) {
update_list[i] = 0;
continue;
}
if (ranking[i] == old_ranking[i]) {
/* no change */
update_list[i] = 0;
colors[ranking[i]->wg_colorindex] = 1;
}
else {
for (j=0; j<n; j++)
if (ranking[i] == old_ranking[j]) {
/* this entry is also in the old ranking but its rank
changed. we have to update the label but keep the
same color. */
update_list[i] = 1;
colors[ranking[i]->wg_colorindex] = 1;
count++;
break;
}
if (j == n) {
/* this is a new entry, assign a new color and update label */
update_list[i] = 2;
count++;
}
}
}
/* assign unused colors to newly rank-in entries */
if (count > 0) {
for (i=0; i<n; i++)
if (update_list[i] == 2) {
int start_index = color_index;
/* get a unsed color */
while (colors[color_index]) {
color_index = (color_index + 1) % color_list_size;
if (color_index == start_index)
break;
}
ranking[i]->wg_color = color_list[color_index];
ranking[i]->wg_colorindex = color_index;
color_index = (color_index + 1) % color_list_size;
}
}
return count;
}
int wg_copybuf(struct wg_entry *wgp, double *vec, double interval, int n)
{
int i, index;
/* get the start index to the ring buf */
index = (wg_cur_time - n + 1) % WG_WIN_SIZE;
for (i=0; i<n; i++) {
int bits = wgp->wg_ringbuf[index] * 8;
vec[i] = (double)bits / interval / ttt_yscale;
if (++index == WG_WIN_SIZE)
index = 0;
}
return i;
}
void wg_init(void)
{
w_init();
wg_qinit(&wg_proto_list);
w_qinit(&wg_proto_list.wg_list);
wg_proto_list.wg_type = TTTTYPE_PROTO;
wg_qinit(&wg_host_list);
w_qinit(&wg_host_list.wg_list);
wg_host_list.wg_type = TTTTYPE_HOST;
}
void wg_cleanup(void)
{
struct wg_entry *head;
head = WG_LIST(TTTTYPE_PROTO);
while (head->wg_prev != head)
wg_delete(head->wg_prev);
head = WG_LIST(TTTTYPE_HOST);
while (head->wg_prev != head)
wg_delete(head->wg_prev);
w_cleanup();
}
int wg_gettime(void)
{
return wg_cur_time;
}
void wg_bumptime(void)
{
struct wg_entry *wgp;
wg_cur_time++;
/* clear ringbuf slot */
for (wgp = wg_proto_list.wg_next; wgp != &wg_proto_list;
wgp = wgp->wg_next)
wgp->wg_ringbuf[wg_cur_time%WG_WIN_SIZE] = 0;
for (wgp = wg_host_list.wg_next; wgp != &wg_host_list;
wgp = wgp->wg_next)
wgp->wg_ringbuf[wg_cur_time%WG_WIN_SIZE] = 0;
/* do garbage collection every 7 minutes */
if ((wg_cur_time % 420) == 0)
w_collectgarbage();
}
static struct wg_entry *wg_create(long type, long *id)
{
struct wg_entry *wgp;
wgp = malloc(sizeof(struct wg_entry));
if (wgp == NULL)
fatal_error("wg_create: no memory!");
wgp->wg_ringbuf = malloc(WG_WIN_SIZE*sizeof(int));
if (wgp->wg_ringbuf == NULL)
fatal_error("wg_create: no memory!");
memset(wgp->wg_ringbuf, 0, WG_WIN_SIZE*sizeof(int));
wgp->wg_type = type;
wgp->wg_id[0] = id[0];
#ifdef IPV6
wgp->wg_id[1] = id[1];
wgp->wg_id[2] = id[2];
wgp->wg_id[3] = id[3];
#endif
w_qinit(&wgp->wg_list);
wgp->wg_name = net_getname(type, id);
/* put this at the tail of the rank list */
if (type < TTTTYPE_HOST) {
wg_insq(wg_proto_list.wg_prev, wgp);
wg_proto_entries++;
}
else {
wg_insq(wg_host_list.wg_prev, wgp);
wg_host_entries++;
}
return wgp;
}
static void wg_delete(struct wg_entry *wgp)
{
wg_remq(wgp);
if (wgp->wg_type < TTTTYPE_HOST)
--wg_proto_entries;
else
--wg_host_entries;
/* if the history list is not empty, discard the list. */
if (wgp->wg_list.w_next != &wgp->wg_list)
w_removesublist(&wgp->wg_list, wgp->wg_list.w_next);
free(wgp->wg_name);
free(wgp->wg_ringbuf);
free(wgp);
}
struct wg_entry *wg_lookup(long type, long *id)
{
struct wg_entry *head, *wgp;
head = WG_LIST(type);
for (wgp = head->wg_next; wgp != head; wgp = wgp->wg_next)
if (wgp->wg_type == type && ISSAME_ID(wgp->wg_id, id))
return wgp;
/* if we already have too many entries, delete one. */
if ((type < TTTTYPE_HOST && wg_proto_entries >= WG_MAX_ENTRIES) ||
(type >= TTTTYPE_HOST && wg_host_entries >= WG_MAX_ENTRIES))
wg_delete(head->wg_prev);
wgp = wg_create(type, id);
return wgp;
}
int wg_getmaxsize(struct wg_entry *wgp)
{
return w_getmaxsize(&wgp->wg_list);
}
static void wg_qinit(struct wg_entry *wgp)
{
wgp->wg_next = wgp->wg_prev = wgp;
}
static void wg_insq(struct wg_entry *prev, struct wg_entry *wgp)
{
wgp->wg_next = prev->wg_next;
wgp->wg_prev = prev;
prev->wg_next = wgp;
wgp->wg_next->wg_prev = wgp;
}
static struct wg_entry *wg_remq(struct wg_entry *wgp)
{
wgp->wg_prev->wg_next = wgp->wg_next;
wgp->wg_next->wg_prev = wgp->wg_prev;
return wgp;
}
struct wg_entry *wg_getbiggest(long type)
{
struct wg_entry *wgp;
struct wg_entry *head;
head = WG_LIST(type);
/* recalculate all the ranks since the current entries may have
obsolete entries.
kludge: call wg_setrank from the bottom of the list to clear
continuous size 0 entries in one sweep. */
for (wgp = head->wg_prev; wgp != head; wgp = wgp->wg_prev)
wg_setrank(wgp);
return wg_getnext(head);
}
struct wg_entry *wg_getnext(struct wg_entry *wgp)
{
struct wg_entry *head;
head = WG_LIST(wgp->wg_type);
if (wgp->wg_next == head)
return NULL;
return wgp->wg_next;
}
void wg_record(struct wg_entry *wgp, int size)
{
struct w_ent *ep;
ep = w_getent();
ep->w_size = size;
ep->w_time = wg_cur_time;
w_insert(&wgp->wg_list, ep);
wgp->wg_ringbuf[wg_cur_time % WG_WIN_SIZE] = size;
wg_setrank(wgp);
}
static void wg_setrank(struct wg_entry *wgp)
{
struct wg_entry *head;
int size;
head = WG_LIST(wgp->wg_type);
/* move the rank if necessary */
/* note that swapping with a neighbor doesn't set the corrent rank
but it eventually converges. it is enough for us, isn't it? */
size = w_getmaxsize(&wgp->wg_list);
while (wgp->wg_prev != head &&
size > w_getmaxsize(&wgp->wg_prev->wg_list)) {
wg_insq(wgp, wg_remq(wgp->wg_prev));
}
while (wgp->wg_next != head &&
size < w_getmaxsize(&wgp->wg_next->wg_list)) {
wg_insq(wgp->wg_prev, wg_remq(wgp->wg_next));
}
}
/*
entry list:
entries are sorted by time and size like this:
list_head -- 1st -- 2nd -- 3rd -- 4th
timestamp 3 8 25 89
size 8200 6500 5032 120
this list has properties:
(1) the timestamp fields are monotonically growing from the top.
(2) the size fields are monotonically shrinking from the top.
when adding a new entry, check the entries from the top of the list
and discard
(1) smaller entries than the new entry.
(2) entries with time-stamp which became out of the time window.
by doing this, the biggest size is always kept on the top of the list.
*/
static struct w_ent free_list;
static int w_ent_allocated;
static void w_insq(struct w_ent *prev, struct w_ent *ep)
{
ep->w_next = prev->w_next;
ep->w_prev = prev;
prev->w_next = ep;
ep->w_next->w_prev = ep;
}
static struct w_ent *w_remq(struct w_ent *ep)
{
ep->w_prev->w_next = ep->w_next;
ep->w_next->w_prev = ep->w_prev;
return ep;
}
static void w_insert(struct w_ent *head, struct w_ent *entry)
{
struct w_ent *ep;
/* if the list has a sublist whose max size is smaller than entry,
remove the sublist. */
#ifdef WG_DEBUG
int tmp_size;
tmp_size = 0x0fffffff; /* big enough */
#endif
ep = head;
while (ep->w_next != head) {
#ifdef WG_DEBUG
assert(ep->w_next->w_size < tmp_size);
#endif
if (ep->w_next->w_size <= entry->w_size) {
w_removesublist(head, ep->w_next);
break;
}
#ifdef WG_DEBUG
tmp_size = ep->w_next->w_size;
#endif
if (ep->w_next->w_time <= entry->w_time - WG_WIN_SIZE) {
w_insq(free_list.w_prev, w_remq(ep->w_next));
continue;
}
ep = ep->w_next;
}
/* insert this entry at the tail */
w_insq(head->w_prev, entry);
}
static void w_alloc_entries(int n)
{
struct w_ent *ep;
int i;
for (i=0; i<n; i++) {
if ((ep = malloc(sizeof(struct w_ent))) == NULL)
fatal_error("w_alloc_entries: can't get memory");
memset(ep, 0, sizeof(struct w_ent));
w_insq(&free_list, ep);
}
w_ent_allocated += n;
}
static void w_init(void)
{
w_qinit(&free_list);
w_alloc_entries(100);
}
static void w_qinit(struct w_ent *head)
{
head->w_next = head->w_prev = head;
}
static void w_removesublist(struct w_ent *head, struct w_ent *list)
{
struct w_ent *top, *tail; /* top and tail of the sublist */
top = list;
tail = head->w_prev;
/* remove the sublist from the original list */
head->w_prev = top->w_prev;
top->w_prev->w_next = head;
/* add this sublist to the free list */
top->w_prev = free_list.w_prev;
top->w_prev->w_next = top;
free_list.w_prev = tail;
tail->w_next = &free_list;
}
static int w_getmaxsize(struct w_ent *head)
{
struct w_ent *ep;
/* expire old entries */
ep = head;
while (ep->w_next != head) {
if (ep->w_next->w_time <= wg_cur_time - WG_WIN_SIZE) {
w_insq(free_list.w_prev, w_remq(ep->w_next));
continue;
}
ep = ep->w_next;
}
if (head->w_next == head)
return 0;
return head->w_next->w_size;
}
static struct w_ent *w_getent(void)
{
struct w_ent *ep = free_list.w_next;
if (ep == &free_list) {
/* free list is empty */
w_alloc_entries(50);
#ifdef WG_DEBUG
printf("[debug] allocated another 50 entries\n");
printf("\ttotal entries=%d\n", w_ent_allocated);
#endif
ep = free_list.w_next;
}
return w_remq(ep);
}
static int w_countfree(void)
{
struct w_ent *ep;
int n = 0;
for (ep = free_list.w_next; ep != &free_list; ep = ep->w_next)
n++;
return n;
}
static void w_collectgarbage(void)
{
int n;
/* if there are more than 100 free entries, keep 50 and
discard the rest. */
n = w_countfree();
if (n > 100) {
n = n - 50;
#ifdef WG_DEBUG
printf("[debug] too much entries. discard %d out of %d\n",
n, w_ent_allocated);
#endif
while (n-- > 0) {
free(w_remq(free_list.w_next));
w_ent_allocated--;
}
#ifdef WG_DEBUG
printf("\ttotal entries=%d\n", w_ent_allocated);
#endif
}
}
/* delete all the entries on the free list */
static void w_cleanup(void)
{
#ifdef WG_DEBUG
printf("w_cleanup:\n");
#endif
while (free_list.w_next != &free_list) {
free(w_remq(free_list.w_next));
w_ent_allocated--;
}
#ifdef WG_DEBUG
printf("total entries=%d\n", w_ent_allocated);
#endif
}
syntax highlighted by Code2HTML, v. 0.9.1