gdunlap/sched-sim.hg

changeset 0:d27bb3c56e71

Inital commit.
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 13 16:06:36 2009 +0100 (2009-10-13)
parents
children ec2d50e41437
files Makefile design.txt list.h sched_rr.c sim.h simulator.c stats.c stats.h workload.h workloads.c
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/Makefile	Tue Oct 13 16:06:36 2009 +0100
     1.3 @@ -0,0 +1,25 @@
     1.4 +CC = gcc
     1.5 +
     1.6 +CFLAGS += -g
     1.7 +CFLAGS += -fno-strict-aliasing
     1.8 +CFLAGS += -std=gnu99
     1.9 +CFLAGS += -Wall -Wstrict-prototypes
    1.10 +CFLAGS += -Wno-unused-value
    1.11 +CFLAGS += -Wdeclaration-after-statement
    1.12 +CFLAGS  += -Werror
    1.13 +
    1.14 +BIN      = simulator
    1.15 +
    1.16 +HDRS = list.h workload.h sim.h stats.h
    1.17 +
    1.18 +all: $(BIN)
    1.19 +
    1.20 +.PHONY: clean
    1.21 +clean:
    1.22 +	$(RM) *.a *.so *.o $(BIN) $(LIBBIN)
    1.23 +
    1.24 +%.o: %.c $(HDRS) Makefile
    1.25 +	$(CC) $(CFLAGS) -c -o $@ $<
    1.26 +
    1.27 +simulator: simulator.o workloads.o sched_rr.o stats.o
    1.28 +	$(CC) $(CFLAGS) -o $@ $^
    1.29 \ No newline at end of file
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/design.txt	Tue Oct 13 16:06:36 2009 +0100
     2.3 @@ -0,0 +1,29 @@
     2.4 +Discrete event simulator to speed the development and analysis of
     2.5 +different scheduling algorithms for the new scheduler.
     2.6 +
     2.7 +Inputs: Scheduler, Workload description
     2.8 +
     2.9 +Hmm... compile in all scheduler variants...?
    2.10 +
    2.11 +scheduler callbacks {
    2.12 +  init processor,
    2.13 +  init VM,
    2.14 +  schedule,
    2.15 +  wake,
    2.16 +  block
    2.17 +}
    2.18 +
    2.19 +scheduler interface {
    2.20 +  insert event (perhaps just SCHEDULE event)
    2.21 +}
    2.22 +
    2.23 +Workload description:
    2.24 +  To begin, wake / block lists; all unconditional.
    2.25 +  Later, deal with "dropped" work (e.g., video, audio)?
    2.26 +  Dependencies (dom0, stubdoms, driver doms)?
    2.27 +
    2.28 +Types of event:
    2.29 +* Wake
    2.30 +* Block
    2.31 +* Schedule timer
    2.32 +
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/list.h	Tue Oct 13 16:06:36 2009 +0100
     3.3 @@ -0,0 +1,928 @@
     3.4 +/******************************************************************************
     3.5 + * list.h
     3.6 + * 
     3.7 + * Useful linked-list definitions taken from the Linux kernel (2.6.18).
     3.8 + */
     3.9 +
    3.10 +#ifndef __XEN_LIST_H__
    3.11 +#define __XEN_LIST_H__
    3.12 +
    3.13 +#if __GNUC__ > 3
    3.14 +#define offsetof(a,b) __builtin_offsetof(a,b)
    3.15 +#else
    3.16 +#define offsetof(a,b) ((unsigned long)&(((a *)0)->b))
    3.17 +#endif
    3.18 +
    3.19 +/**
    3.20 + * container_of - cast a member of a structure out to the containing structure
    3.21 + *
    3.22 + * @ptr:	the pointer to the member.
    3.23 + * @type:	the type of the container struct this is embedded in.
    3.24 + * @member:	the name of the member within the struct.
    3.25 + *
    3.26 + */
    3.27 +#define container_of(ptr, type, member) ({                      \
    3.28 +        typeof( ((type *)0)->member ) *__mptr = (ptr);          \
    3.29 +        (type *)( (char *)__mptr - offsetof(type,member) );})
    3.30 +
    3.31 +#define prefetch(_x) (_x)
    3.32 +
    3.33 +/* These are non-NULL pointers that will result in page faults
    3.34 + * under normal circumstances, used to verify that nobody uses
    3.35 + * non-initialized list entries.
    3.36 + */
    3.37 +#define LIST_POISON1  ((void *) 0x00100100)
    3.38 +#define LIST_POISON2  ((void *) 0x00200200)
    3.39 +
    3.40 +/*
    3.41 + * Simple doubly linked list implementation.
    3.42 + *
    3.43 + * Some of the internal functions ("__xxx") are useful when
    3.44 + * manipulating whole lists rather than single entries, as
    3.45 + * sometimes we already know the next/prev entries and we can
    3.46 + * generate better code by using them directly rather than
    3.47 + * using the generic single-entry routines.
    3.48 + */
    3.49 +
    3.50 +struct list_head {
    3.51 +    struct list_head *next, *prev;
    3.52 +};
    3.53 +
    3.54 +#define LIST_HEAD_INIT(name) { &(name), &(name) }
    3.55 +
    3.56 +#define LIST_HEAD(name) \
    3.57 +    struct list_head name = LIST_HEAD_INIT(name)
    3.58 +
    3.59 +static inline void INIT_LIST_HEAD(struct list_head *list)
    3.60 +{
    3.61 +    list->next = list;
    3.62 +    list->prev = list;
    3.63 +}
    3.64 +
    3.65 +/*
    3.66 + * Insert a new entry between two known consecutive entries. 
    3.67 + *
    3.68 + * This is only for internal list manipulation where we know
    3.69 + * the prev/next entries already!
    3.70 + */
    3.71 +static inline void __list_add(struct list_head *new,
    3.72 +                              struct list_head *prev,
    3.73 +                              struct list_head *next)
    3.74 +{
    3.75 +    next->prev = new;
    3.76 +    new->next = next;
    3.77 +    new->prev = prev;
    3.78 +    prev->next = new;
    3.79 +}
    3.80 +
    3.81 +/**
    3.82 + * list_add - add a new entry
    3.83 + * @new: new entry to be added
    3.84 + * @head: list head to add it after
    3.85 + *
    3.86 + * Insert a new entry after the specified head.
    3.87 + * This is good for implementing stacks.
    3.88 + */
    3.89 +static inline void list_add(struct list_head *new, struct list_head *head)
    3.90 +{
    3.91 +    __list_add(new, head, head->next);
    3.92 +}
    3.93 +
    3.94 +/**
    3.95 + * list_add_tail - add a new entry
    3.96 + * @new: new entry to be added
    3.97 + * @head: list head to add it before
    3.98 + *
    3.99 + * Insert a new entry before the specified head.
   3.100 + * This is useful for implementing queues.
   3.101 + */
   3.102 +static inline void list_add_tail(struct list_head *new, struct list_head *head)
   3.103 +{
   3.104 +    __list_add(new, head->prev, head);
   3.105 +}
   3.106 +
   3.107 +/*
   3.108 + * Insert a new entry between two known consecutive entries.
   3.109 + *
   3.110 + * This is only for internal list manipulation where we know
   3.111 + * the prev/next entries already!
   3.112 + */
   3.113 +static inline void __list_add_rcu(struct list_head *new,
   3.114 +                                  struct list_head *prev,
   3.115 +                                  struct list_head *next)
   3.116 +{
   3.117 +    new->next = next;
   3.118 +    new->prev = prev;
   3.119 +    next->prev = new;
   3.120 +    prev->next = new;
   3.121 +}
   3.122 +
   3.123 +/**
   3.124 + * list_add_rcu - add a new entry to rcu-protected list
   3.125 + * @new: new entry to be added
   3.126 + * @head: list head to add it after
   3.127 + *
   3.128 + * Insert a new entry after the specified head.
   3.129 + * This is good for implementing stacks.
   3.130 + *
   3.131 + * The caller must take whatever precautions are necessary
   3.132 + * (such as holding appropriate locks) to avoid racing
   3.133 + * with another list-mutation primitive, such as list_add_rcu()
   3.134 + * or list_del_rcu(), running on this same list.
   3.135 + * However, it is perfectly legal to run concurrently with
   3.136 + * the _rcu list-traversal primitives, such as
   3.137 + * list_for_each_entry_rcu().
   3.138 + */
   3.139 +static inline void list_add_rcu(struct list_head *new, struct list_head *head)
   3.140 +{
   3.141 +    __list_add_rcu(new, head, head->next);
   3.142 +}
   3.143 +
   3.144 +/**
   3.145 + * list_add_tail_rcu - add a new entry to rcu-protected list
   3.146 + * @new: new entry to be added
   3.147 + * @head: list head to add it before
   3.148 + *
   3.149 + * Insert a new entry before the specified head.
   3.150 + * This is useful for implementing queues.
   3.151 + *
   3.152 + * The caller must take whatever precautions are necessary
   3.153 + * (such as holding appropriate locks) to avoid racing
   3.154 + * with another list-mutation primitive, such as list_add_tail_rcu()
   3.155 + * or list_del_rcu(), running on this same list.
   3.156 + * However, it is perfectly legal to run concurrently with
   3.157 + * the _rcu list-traversal primitives, such as
   3.158 + * list_for_each_entry_rcu().
   3.159 + */
   3.160 +static inline void list_add_tail_rcu(struct list_head *new,
   3.161 +                                     struct list_head *head)
   3.162 +{
   3.163 +    __list_add_rcu(new, head->prev, head);
   3.164 +}
   3.165 +
   3.166 +/*
   3.167 + * Delete a list entry by making the prev/next entries
   3.168 + * point to each other.
   3.169 + *
   3.170 + * This is only for internal list manipulation where we know
   3.171 + * the prev/next entries already!
   3.172 + */
   3.173 +static inline void __list_del(struct list_head *prev,
   3.174 +                              struct list_head *next)
   3.175 +{
   3.176 +    next->prev = prev;
   3.177 +    prev->next = next;
   3.178 +}
   3.179 +
   3.180 +/**
   3.181 + * list_del - deletes entry from list.
   3.182 + * @entry: the element to delete from the list.
   3.183 + * Note: list_empty on entry does not return true after this, the entry is
   3.184 + * in an undefined state.
   3.185 + */
   3.186 +static inline void list_del(struct list_head *entry)
   3.187 +{
   3.188 +    ASSERT(entry->next->prev == entry);
   3.189 +    ASSERT(entry->prev->next == entry);
   3.190 +    __list_del(entry->prev, entry->next);
   3.191 +    entry->next = LIST_POISON1;
   3.192 +    entry->prev = LIST_POISON2;
   3.193 +}
   3.194 +
   3.195 +/**
   3.196 + * list_del_rcu - deletes entry from list without re-initialization
   3.197 + * @entry: the element to delete from the list.
   3.198 + *
   3.199 + * Note: list_empty on entry does not return true after this,
   3.200 + * the entry is in an undefined state. It is useful for RCU based
   3.201 + * lockfree traversal.
   3.202 + *
   3.203 + * In particular, it means that we can not poison the forward
   3.204 + * pointers that may still be used for walking the list.
   3.205 + *
   3.206 + * The caller must take whatever precautions are necessary
   3.207 + * (such as holding appropriate locks) to avoid racing
   3.208 + * with another list-mutation primitive, such as list_del_rcu()
   3.209 + * or list_add_rcu(), running on this same list.
   3.210 + * However, it is perfectly legal to run concurrently with
   3.211 + * the _rcu list-traversal primitives, such as
   3.212 + * list_for_each_entry_rcu().
   3.213 + *
   3.214 + * Note that the caller is not permitted to immediately free
   3.215 + * the newly deleted entry.  Instead, either synchronize_rcu()
   3.216 + * or call_rcu() must be used to defer freeing until an RCU
   3.217 + * grace period has elapsed.
   3.218 + */
   3.219 +static inline void list_del_rcu(struct list_head *entry)
   3.220 +{
   3.221 +    __list_del(entry->prev, entry->next);
   3.222 +    entry->prev = LIST_POISON2;
   3.223 +}
   3.224 +
   3.225 +/**
   3.226 + * list_replace - replace old entry by new one
   3.227 + * @old : the element to be replaced
   3.228 + * @new : the new element to insert
   3.229 + * Note: if 'old' was empty, it will be overwritten.
   3.230 + */
   3.231 +static inline void list_replace(struct list_head *old,
   3.232 +                                struct list_head *new)
   3.233 +{
   3.234 +    new->next = old->next;
   3.235 +    new->next->prev = new;
   3.236 +    new->prev = old->prev;
   3.237 +    new->prev->next = new;
   3.238 +}
   3.239 +
   3.240 +static inline void list_replace_init(struct list_head *old,
   3.241 +                                     struct list_head *new)
   3.242 +{
   3.243 +    list_replace(old, new);
   3.244 +    INIT_LIST_HEAD(old);
   3.245 +}
   3.246 +
   3.247 +/*
   3.248 + * list_replace_rcu - replace old entry by new one
   3.249 + * @old : the element to be replaced
   3.250 + * @new : the new element to insert
   3.251 + *
   3.252 + * The old entry will be replaced with the new entry atomically.
   3.253 + * Note: 'old' should not be empty.
   3.254 + */
   3.255 +static inline void list_replace_rcu(struct list_head *old,
   3.256 +                                    struct list_head *new)
   3.257 +{
   3.258 +    new->next = old->next;
   3.259 +    new->prev = old->prev;
   3.260 +    new->next->prev = new;
   3.261 +    new->prev->next = new;
   3.262 +    old->prev = LIST_POISON2;
   3.263 +}
   3.264 +
   3.265 +/**
   3.266 + * list_del_init - deletes entry from list and reinitialize it.
   3.267 + * @entry: the element to delete from the list.
   3.268 + */
   3.269 +static inline void list_del_init(struct list_head *entry)
   3.270 +{
   3.271 +    __list_del(entry->prev, entry->next);
   3.272 +    INIT_LIST_HEAD(entry);
   3.273 +}
   3.274 +
   3.275 +/**
   3.276 + * list_move - delete from one list and add as another's head
   3.277 + * @list: the entry to move
   3.278 + * @head: the head that will precede our entry
   3.279 + */
   3.280 +static inline void list_move(struct list_head *list, struct list_head *head)
   3.281 +{
   3.282 +    __list_del(list->prev, list->next);
   3.283 +    list_add(list, head);
   3.284 +}
   3.285 +
   3.286 +/**
   3.287 + * list_move_tail - delete from one list and add as another's tail
   3.288 + * @list: the entry to move
   3.289 + * @head: the head that will follow our entry
   3.290 + */
   3.291 +static inline void list_move_tail(struct list_head *list,
   3.292 +                                  struct list_head *head)
   3.293 +{
   3.294 +    __list_del(list->prev, list->next);
   3.295 +    list_add_tail(list, head);
   3.296 +}
   3.297 +
   3.298 +/**
   3.299 + * list_is_last - tests whether @list is the last entry in list @head
   3.300 + * @list: the entry to test
   3.301 + * @head: the head of the list
   3.302 + */
   3.303 +static inline int list_is_last(const struct list_head *list,
   3.304 +                               const struct list_head *head)
   3.305 +{
   3.306 +    return list->next == head;
   3.307 +}
   3.308 +
   3.309 +/**
   3.310 + * list_empty - tests whether a list is empty
   3.311 + * @head: the list to test.
   3.312 + */
   3.313 +static inline int list_empty(const struct list_head *head)
   3.314 +{
   3.315 +    return head->next == head;
   3.316 +}
   3.317 +
   3.318 +/**
   3.319 + * list_empty_careful - tests whether a list is empty and not being modified
   3.320 + * @head: the list to test
   3.321 + *
   3.322 + * Description:
   3.323 + * tests whether a list is empty _and_ checks that no other CPU might be
   3.324 + * in the process of modifying either member (next or prev)
   3.325 + *
   3.326 + * NOTE: using list_empty_careful() without synchronization
   3.327 + * can only be safe if the only activity that can happen
   3.328 + * to the list entry is list_del_init(). Eg. it cannot be used
   3.329 + * if another CPU could re-list_add() it.
   3.330 + */
   3.331 +static inline int list_empty_careful(const struct list_head *head)
   3.332 +{
   3.333 +    struct list_head *next = head->next;
   3.334 +    return (next == head) && (next == head->prev);
   3.335 +}
   3.336 +
   3.337 +static inline void __list_splice(struct list_head *list,
   3.338 +                                 struct list_head *head)
   3.339 +{
   3.340 +    struct list_head *first = list->next;
   3.341 +    struct list_head *last = list->prev;
   3.342 +    struct list_head *at = head->next;
   3.343 +
   3.344 +    first->prev = head;
   3.345 +    head->next = first;
   3.346 +
   3.347 +    last->next = at;
   3.348 +    at->prev = last;
   3.349 +}
   3.350 +
   3.351 +/**
   3.352 + * list_splice - join two lists
   3.353 + * @list: the new list to add.
   3.354 + * @head: the place to add it in the first list.
   3.355 + */
   3.356 +static inline void list_splice(struct list_head *list, struct list_head *head)
   3.357 +{
   3.358 +    if (!list_empty(list))
   3.359 +        __list_splice(list, head);
   3.360 +}
   3.361 +
   3.362 +/**
   3.363 + * list_splice_init - join two lists and reinitialise the emptied list.
   3.364 + * @list: the new list to add.
   3.365 + * @head: the place to add it in the first list.
   3.366 + *
   3.367 + * The list at @list is reinitialised
   3.368 + */
   3.369 +static inline void list_splice_init(struct list_head *list,
   3.370 +                                    struct list_head *head)
   3.371 +{
   3.372 +    if (!list_empty(list)) {
   3.373 +        __list_splice(list, head);
   3.374 +        INIT_LIST_HEAD(list);
   3.375 +    }
   3.376 +}
   3.377 +
   3.378 +/**
   3.379 + * list_entry - get the struct for this entry
   3.380 + * @ptr:    the &struct list_head pointer.
   3.381 + * @type:    the type of the struct this is embedded in.
   3.382 + * @member:    the name of the list_struct within the struct.
   3.383 + */
   3.384 +#define list_entry(ptr, type, member) \
   3.385 +    container_of(ptr, type, member)
   3.386 +
   3.387 +/**
   3.388 + * list_for_each    -    iterate over a list
   3.389 + * @pos:    the &struct list_head to use as a loop cursor.
   3.390 + * @head:    the head for your list.
   3.391 + */
   3.392 +#define list_for_each(pos, head)                                        \
   3.393 +    for (pos = (head)->next; prefetch(pos->next), pos != (head);        \
   3.394 +         pos = pos->next)
   3.395 +
   3.396 +/**
   3.397 + * __list_for_each - iterate over a list
   3.398 + * @pos:    the &struct list_head to use as a loop cursor.
   3.399 + * @head:   the head for your list.
   3.400 + *
   3.401 + * This variant differs from list_for_each() in that it's the
   3.402 + * simplest possible list iteration code, no prefetching is done.
   3.403 + * Use this for code that knows the list to be very short (empty
   3.404 + * or 1 entry) most of the time.
   3.405 + */
   3.406 +#define __list_for_each(pos, head)                              \
   3.407 +    for (pos = (head)->next; pos != (head); pos = pos->next)
   3.408 +
   3.409 +/**
   3.410 + * list_for_each_prev - iterate over a list backwards
   3.411 + * @pos:    the &struct list_head to use as a loop cursor.
   3.412 + * @head:   the head for your list.
   3.413 + */
   3.414 +#define list_for_each_prev(pos, head)                                   \
   3.415 +    for (pos = (head)->prev; prefetch(pos->prev), pos != (head);        \
   3.416 +         pos = pos->prev)
   3.417 +
   3.418 +/**
   3.419 + * list_for_each_safe - iterate over a list safe against removal of list entry
   3.420 + * @pos:    the &struct list_head to use as a loop cursor.
   3.421 + * @n:      another &struct list_head to use as temporary storage
   3.422 + * @head:   the head for your list.
   3.423 + */
   3.424 +#define list_for_each_safe(pos, n, head)                        \
   3.425 +    for (pos = (head)->next, n = pos->next; pos != (head);      \
   3.426 +         pos = n, n = pos->next)
   3.427 +
   3.428 +/**
   3.429 + * list_for_each_backwards_safe    -    iterate backwards over a list safe
   3.430 + *                                      against removal of list entry
   3.431 + * @pos:    the &struct list_head to use as a loop counter.
   3.432 + * @n:      another &struct list_head to use as temporary storage
   3.433 + * @head:   the head for your list.
   3.434 + */
   3.435 +#define list_for_each_backwards_safe(pos, n, head)              \
   3.436 +    for ( pos = (head)->prev, n = pos->prev; pos != (head);     \
   3.437 +          pos = n, n = pos->prev )
   3.438 +
   3.439 +/**
   3.440 + * list_for_each_entry - iterate over list of given type
   3.441 + * @pos:    the type * to use as a loop cursor.
   3.442 + * @head:   the head for your list.
   3.443 + * @member: the name of the list_struct within the struct.
   3.444 + */
   3.445 +#define list_for_each_entry(pos, head, member)                          \
   3.446 +    for (pos = list_entry((head)->next, typeof(*pos), member);          \
   3.447 +         prefetch(pos->member.next), &pos->member != (head);            \
   3.448 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   3.449 +
   3.450 +/**
   3.451 + * list_for_each_entry_reverse - iterate backwards over list of given type.
   3.452 + * @pos:    the type * to use as a loop cursor.
   3.453 + * @head:   the head for your list.
   3.454 + * @member: the name of the list_struct within the struct.
   3.455 + */
   3.456 +#define list_for_each_entry_reverse(pos, head, member)                  \
   3.457 +    for (pos = list_entry((head)->prev, typeof(*pos), member);          \
   3.458 +         prefetch(pos->member.prev), &pos->member != (head);            \
   3.459 +         pos = list_entry(pos->member.prev, typeof(*pos), member))
   3.460 +
   3.461 +/**
   3.462 + * list_prepare_entry - prepare a pos entry for use in
   3.463 + *                      list_for_each_entry_continue
   3.464 + * @pos:    the type * to use as a start point
   3.465 + * @head:   the head of the list
   3.466 + * @member: the name of the list_struct within the struct.
   3.467 + *
   3.468 + * Prepares a pos entry for use as a start point in
   3.469 + * list_for_each_entry_continue.
   3.470 + */
   3.471 +#define list_prepare_entry(pos, head, member)           \
   3.472 +    ((pos) ? : list_entry(head, typeof(*pos), member))
   3.473 +
   3.474 +/**
   3.475 + * list_for_each_entry_continue - continue iteration over list of given type
   3.476 + * @pos:    the type * to use as a loop cursor.
   3.477 + * @head:   the head for your list.
   3.478 + * @member: the name of the list_struct within the struct.
   3.479 + *
   3.480 + * Continue to iterate over list of given type, continuing after
   3.481 + * the current position.
   3.482 + */
   3.483 +#define list_for_each_entry_continue(pos, head, member)                 \
   3.484 +    for (pos = list_entry(pos->member.next, typeof(*pos), member);      \
   3.485 +         prefetch(pos->member.next), &pos->member != (head);            \
   3.486 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   3.487 +
   3.488 +/**
   3.489 + * list_for_each_entry_from - iterate over list of given type from the
   3.490 + *                            current point
   3.491 + * @pos:    the type * to use as a loop cursor.
   3.492 + * @head:   the head for your list.
   3.493 + * @member: the name of the list_struct within the struct.
   3.494 + *
   3.495 + * Iterate over list of given type, continuing from current position.
   3.496 + */
   3.497 +#define list_for_each_entry_from(pos, head, member)                     \
   3.498 +    for (; prefetch(pos->member.next), &pos->member != (head);          \
   3.499 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   3.500 +
   3.501 +/**
   3.502 + * list_for_each_entry_safe - iterate over list of given type safe
   3.503 + *                            against removal of list entry
   3.504 + * @pos:    the type * to use as a loop cursor.
   3.505 + * @n:      another type * to use as temporary storage
   3.506 + * @head:   the head for your list.
   3.507 + * @member: the name of the list_struct within the struct.
   3.508 + */
   3.509 +#define list_for_each_entry_safe(pos, n, head, member)                  \
   3.510 +    for (pos = list_entry((head)->next, typeof(*pos), member),          \
   3.511 +         n = list_entry(pos->member.next, typeof(*pos), member);        \
   3.512 +         &pos->member != (head);                                        \
   3.513 +         pos = n, n = list_entry(n->member.next, typeof(*n), member))
   3.514 +
   3.515 +/**
   3.516 + * list_for_each_entry_safe_continue
   3.517 + * @pos:    the type * to use as a loop cursor.
   3.518 + * @n:      another type * to use as temporary storage
   3.519 + * @head:   the head for your list.
   3.520 + * @member: the name of the list_struct within the struct.
   3.521 + *
   3.522 + * Iterate over list of given type, continuing after current point,
   3.523 + * safe against removal of list entry.
   3.524 + */
   3.525 +#define list_for_each_entry_safe_continue(pos, n, head, member)         \
   3.526 +    for (pos = list_entry(pos->member.next, typeof(*pos), member),      \
   3.527 +         n = list_entry(pos->member.next, typeof(*pos), member);        \
   3.528 +         &pos->member != (head);                                        \
   3.529 +         pos = n, n = list_entry(n->member.next, typeof(*n), member))
   3.530 +
   3.531 +/**
   3.532 + * list_for_each_entry_safe_from
   3.533 + * @pos:    the type * to use as a loop cursor.
   3.534 + * @n:      another type * to use as temporary storage
   3.535 + * @head:   the head for your list.
   3.536 + * @member: the name of the list_struct within the struct.
   3.537 + *
   3.538 + * Iterate over list of given type from current point, safe against
   3.539 + * removal of list entry.
   3.540 + */
   3.541 +#define list_for_each_entry_safe_from(pos, n, head, member)             \
   3.542 +    for (n = list_entry(pos->member.next, typeof(*pos), member);        \
   3.543 +         &pos->member != (head);                                        \
   3.544 +         pos = n, n = list_entry(n->member.next, typeof(*n), member))
   3.545 +
   3.546 +/**
   3.547 + * list_for_each_entry_safe_reverse
   3.548 + * @pos:    the type * to use as a loop cursor.
   3.549 + * @n:      another type * to use as temporary storage
   3.550 + * @head:   the head for your list.
   3.551 + * @member: the name of the list_struct within the struct.
   3.552 + *
   3.553 + * Iterate backwards over list of given type, safe against removal
   3.554 + * of list entry.
   3.555 + */
   3.556 +#define list_for_each_entry_safe_reverse(pos, n, head, member)          \
   3.557 +    for (pos = list_entry((head)->prev, typeof(*pos), member),          \
   3.558 +         n = list_entry(pos->member.prev, typeof(*pos), member);        \
   3.559 +         &pos->member != (head);                                        \
   3.560 +         pos = n, n = list_entry(n->member.prev, typeof(*n), member))
   3.561 +
   3.562 +/**
   3.563 + * list_for_each_rcu - iterate over an rcu-protected list
   3.564 + * @pos:  the &struct list_head to use as a loop cursor.
   3.565 + * @head: the head for your list.
   3.566 + *
   3.567 + * This list-traversal primitive may safely run concurrently with
   3.568 + * the _rcu list-mutation primitives such as list_add_rcu()
   3.569 + * as long as the traversal is guarded by rcu_read_lock().
   3.570 + */
   3.571 +#define list_for_each_rcu(pos, head)                            \
   3.572 +    for (pos = (head)->next;                                    \
   3.573 +         prefetch(rcu_dereference(pos)->next), pos != (head);   \
   3.574 +         pos = pos->next)
   3.575 +
   3.576 +#define __list_for_each_rcu(pos, head)          \
   3.577 +    for (pos = (head)->next;                    \
   3.578 +         rcu_dereference(pos) != (head);        \
   3.579 +         pos = pos->next)
   3.580 +
   3.581 +/**
   3.582 + * list_for_each_safe_rcu
   3.583 + * @pos:   the &struct list_head to use as a loop cursor.
   3.584 + * @n:     another &struct list_head to use as temporary storage
   3.585 + * @head:  the head for your list.
   3.586 + *
   3.587 + * Iterate over an rcu-protected list, safe against removal of list entry.
   3.588 + *
   3.589 + * This list-traversal primitive may safely run concurrently with
   3.590 + * the _rcu list-mutation primitives such as list_add_rcu()
   3.591 + * as long as the traversal is guarded by rcu_read_lock().
   3.592 + */
   3.593 +#define list_for_each_safe_rcu(pos, n, head)            \
   3.594 +    for (pos = (head)->next;                            \
   3.595 +         n = rcu_dereference(pos)->next, pos != (head); \
   3.596 +         pos = n)
   3.597 +
   3.598 +/**
   3.599 + * list_for_each_entry_rcu - iterate over rcu list of given type
   3.600 + * @pos:    the type * to use as a loop cursor.
   3.601 + * @head:   the head for your list.
   3.602 + * @member: the name of the list_struct within the struct.
   3.603 + *
   3.604 + * This list-traversal primitive may safely run concurrently with
   3.605 + * the _rcu list-mutation primitives such as list_add_rcu()
   3.606 + * as long as the traversal is guarded by rcu_read_lock().
   3.607 + */
   3.608 +#define list_for_each_entry_rcu(pos, head, member)                      \
   3.609 +    for (pos = list_entry((head)->next, typeof(*pos), member);          \
   3.610 +         prefetch(rcu_dereference(pos)->member.next),                   \
   3.611 +         &pos->member != (head);                                        \
   3.612 +         pos = list_entry(pos->member.next, typeof(*pos), member))
   3.613 +
   3.614 +/**
   3.615 + * list_for_each_continue_rcu
   3.616 + * @pos:    the &struct list_head to use as a loop cursor.
   3.617 + * @head:   the head for your list.
   3.618 + *
   3.619 + * Iterate over an rcu-protected list, continuing after current point.
   3.620 + *
   3.621 + * This list-traversal primitive may safely run concurrently with
   3.622 + * the _rcu list-mutation primitives such as list_add_rcu()
   3.623 + * as long as the traversal is guarded by rcu_read_lock().
   3.624 + */
   3.625 +#define list_for_each_continue_rcu(pos, head)                           \
   3.626 +    for ((pos) = (pos)->next;                                           \
   3.627 +         prefetch(rcu_dereference((pos))->next), (pos) != (head);       \
   3.628 +         (pos) = (pos)->next)
   3.629 +
   3.630 +/*
   3.631 + * Double linked lists with a single pointer list head.
   3.632 + * Mostly useful for hash tables where the two pointer list head is
   3.633 + * too wasteful.
   3.634 + * You lose the ability to access the tail in O(1).
   3.635 + */
   3.636 +
   3.637 +struct hlist_head {
   3.638 +    struct hlist_node *first;
   3.639 +};
   3.640 +
   3.641 +struct hlist_node {
   3.642 +    struct hlist_node *next, **pprev;
   3.643 +};
   3.644 +
   3.645 +#define HLIST_HEAD_INIT { .first = NULL }
   3.646 +#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
   3.647 +#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
   3.648 +static inline void INIT_HLIST_NODE(struct hlist_node *h)
   3.649 +{
   3.650 +    h->next = NULL;
   3.651 +    h->pprev = NULL;
   3.652 +}
   3.653 +
   3.654 +static inline int hlist_unhashed(const struct hlist_node *h)
   3.655 +{
   3.656 +    return !h->pprev;
   3.657 +}
   3.658 +
   3.659 +static inline int hlist_empty(const struct hlist_head *h)
   3.660 +{
   3.661 +    return !h->first;
   3.662 +}
   3.663 +
   3.664 +static inline void __hlist_del(struct hlist_node *n)
   3.665 +{
   3.666 +    struct hlist_node *next = n->next;
   3.667 +    struct hlist_node **pprev = n->pprev;
   3.668 +    *pprev = next;
   3.669 +    if (next)
   3.670 +        next->pprev = pprev;
   3.671 +}
   3.672 +
   3.673 +static inline void hlist_del(struct hlist_node *n)
   3.674 +{
   3.675 +    __hlist_del(n);
   3.676 +    n->next = LIST_POISON1;
   3.677 +    n->pprev = LIST_POISON2;
   3.678 +}
   3.679 +
   3.680 +/**
   3.681 + * hlist_del_rcu - deletes entry from hash list without re-initialization
   3.682 + * @n: the element to delete from the hash list.
   3.683 + *
   3.684 + * Note: list_unhashed() on entry does not return true after this,
   3.685 + * the entry is in an undefined state. It is useful for RCU based
   3.686 + * lockfree traversal.
   3.687 + *
   3.688 + * In particular, it means that we can not poison the forward
   3.689 + * pointers that may still be used for walking the hash list.
   3.690 + *
   3.691 + * The caller must take whatever precautions are necessary
   3.692 + * (such as holding appropriate locks) to avoid racing
   3.693 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   3.694 + * or hlist_del_rcu(), running on this same list.
   3.695 + * However, it is perfectly legal to run concurrently with
   3.696 + * the _rcu list-traversal primitives, such as
   3.697 + * hlist_for_each_entry().
   3.698 + */
   3.699 +static inline void hlist_del_rcu(struct hlist_node *n)
   3.700 +{
   3.701 +    __hlist_del(n);
   3.702 +    n->pprev = LIST_POISON2;
   3.703 +}
   3.704 +
   3.705 +static inline void hlist_del_init(struct hlist_node *n)
   3.706 +{
   3.707 +    if (!hlist_unhashed(n)) {
   3.708 +        __hlist_del(n);
   3.709 +        INIT_HLIST_NODE(n);
   3.710 +    }
   3.711 +}
   3.712 +
   3.713 +/*
   3.714 + * hlist_replace_rcu - replace old entry by new one
   3.715 + * @old : the element to be replaced
   3.716 + * @new : the new element to insert
   3.717 + *
   3.718 + * The old entry will be replaced with the new entry atomically.
   3.719 + */
   3.720 +static inline void hlist_replace_rcu(struct hlist_node *old,
   3.721 +                                     struct hlist_node *new)
   3.722 +{
   3.723 +    struct hlist_node *next = old->next;
   3.724 +
   3.725 +    new->next = next;
   3.726 +    new->pprev = old->pprev;
   3.727 +    if (next)
   3.728 +        new->next->pprev = &new->next;
   3.729 +    *new->pprev = new;
   3.730 +    old->pprev = LIST_POISON2;
   3.731 +}
   3.732 +
   3.733 +static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
   3.734 +{
   3.735 +    struct hlist_node *first = h->first;
   3.736 +    n->next = first;
   3.737 +    if (first)
   3.738 +        first->pprev = &n->next;
   3.739 +    h->first = n;
   3.740 +    n->pprev = &h->first;
   3.741 +}
   3.742 +
   3.743 +/**
   3.744 + * hlist_add_head_rcu
   3.745 + * @n: the element to add to the hash list.
   3.746 + * @h: the list to add to.
   3.747 + *
   3.748 + * Description:
   3.749 + * Adds the specified element to the specified hlist,
   3.750 + * while permitting racing traversals.
   3.751 + *
   3.752 + * The caller must take whatever precautions are necessary
   3.753 + * (such as holding appropriate locks) to avoid racing
   3.754 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   3.755 + * or hlist_del_rcu(), running on this same list.
   3.756 + * However, it is perfectly legal to run concurrently with
   3.757 + * the _rcu list-traversal primitives, such as
   3.758 + * hlist_for_each_entry_rcu(), used to prevent memory-consistency
   3.759 + * problems on Alpha CPUs.  Regardless of the type of CPU, the
   3.760 + * list-traversal primitive must be guarded by rcu_read_lock().
   3.761 + */
   3.762 +static inline void hlist_add_head_rcu(struct hlist_node *n,
   3.763 +                                      struct hlist_head *h)
   3.764 +{
   3.765 +    struct hlist_node *first = h->first;
   3.766 +    n->next = first;
   3.767 +    n->pprev = &h->first;
   3.768 +    if (first)
   3.769 +        first->pprev = &n->next;
   3.770 +    h->first = n;
   3.771 +}
   3.772 +
   3.773 +/* next must be != NULL */
   3.774 +static inline void hlist_add_before(struct hlist_node *n,
   3.775 +                    struct hlist_node *next)
   3.776 +{
   3.777 +    n->pprev = next->pprev;
   3.778 +    n->next = next;
   3.779 +    next->pprev = &n->next;
   3.780 +    *(n->pprev) = n;
   3.781 +}
   3.782 +
   3.783 +static inline void hlist_add_after(struct hlist_node *n,
   3.784 +                    struct hlist_node *next)
   3.785 +{
   3.786 +    next->next = n->next;
   3.787 +    n->next = next;
   3.788 +    next->pprev = &n->next;
   3.789 +
   3.790 +    if(next->next)
   3.791 +        next->next->pprev  = &next->next;
   3.792 +}
   3.793 +
   3.794 +/**
   3.795 + * hlist_add_before_rcu
   3.796 + * @n: the new element to add to the hash list.
   3.797 + * @next: the existing element to add the new element before.
   3.798 + *
   3.799 + * Description:
   3.800 + * Adds the specified element to the specified hlist
   3.801 + * before the specified node while permitting racing traversals.
   3.802 + *
   3.803 + * The caller must take whatever precautions are necessary
   3.804 + * (such as holding appropriate locks) to avoid racing
   3.805 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   3.806 + * or hlist_del_rcu(), running on this same list.
   3.807 + * However, it is perfectly legal to run concurrently with
   3.808 + * the _rcu list-traversal primitives, such as
   3.809 + * hlist_for_each_entry_rcu(), used to prevent memory-consistency
   3.810 + * problems on Alpha CPUs.
   3.811 + */
   3.812 +static inline void hlist_add_before_rcu(struct hlist_node *n,
   3.813 +                                        struct hlist_node *next)
   3.814 +{
   3.815 +    n->pprev = next->pprev;
   3.816 +    n->next = next;
   3.817 +    next->pprev = &n->next;
   3.818 +    *(n->pprev) = n;
   3.819 +}
   3.820 +
   3.821 +/**
   3.822 + * hlist_add_after_rcu
   3.823 + * @prev: the existing element to add the new element after.
   3.824 + * @n: the new element to add to the hash list.
   3.825 + *
   3.826 + * Description:
   3.827 + * Adds the specified element to the specified hlist
   3.828 + * after the specified node while permitting racing traversals.
   3.829 + *
   3.830 + * The caller must take whatever precautions are necessary
   3.831 + * (such as holding appropriate locks) to avoid racing
   3.832 + * with another list-mutation primitive, such as hlist_add_head_rcu()
   3.833 + * or hlist_del_rcu(), running on this same list.
   3.834 + * However, it is perfectly legal to run concurrently with
   3.835 + * the _rcu list-traversal primitives, such as
   3.836 + * hlist_for_each_entry_rcu(), used to prevent memory-consistency
   3.837 + * problems on Alpha CPUs.
   3.838 + */
   3.839 +static inline void hlist_add_after_rcu(struct hlist_node *prev,
   3.840 +                                       struct hlist_node *n)
   3.841 +{
   3.842 +    n->next = prev->next;
   3.843 +    n->pprev = &prev->next;
   3.844 +    prev->next = n;
   3.845 +    if (n->next)
   3.846 +        n->next->pprev = &n->next;
   3.847 +}
   3.848 +
   3.849 +#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
   3.850 +
   3.851 +#define hlist_for_each(pos, head)                                       \
   3.852 +    for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; });     \
   3.853 +         pos = pos->next)
   3.854 +
   3.855 +#define hlist_for_each_safe(pos, n, head)                       \
   3.856 +    for (pos = (head)->first; pos && ({ n = pos->next; 1; });   \
   3.857 +         pos = n)
   3.858 +
   3.859 +/**
   3.860 + * hlist_for_each_entry    - iterate over list of given type
   3.861 + * @tpos:    the type * to use as a loop cursor.
   3.862 + * @pos:    the &struct hlist_node to use as a loop cursor.
   3.863 + * @head:    the head for your list.
   3.864 + * @member:    the name of the hlist_node within the struct.
   3.865 + */
   3.866 +#define hlist_for_each_entry(tpos, pos, head, member)                   \
   3.867 +    for (pos = (head)->first;                                           \
   3.868 +         pos && ({ prefetch(pos->next); 1;}) &&                         \
   3.869 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   3.870 +         pos = pos->next)
   3.871 +
   3.872 +/**
   3.873 + * hlist_for_each_entry_continue - iterate over a hlist continuing
   3.874 + *                                 after current point
   3.875 + * @tpos:    the type * to use as a loop cursor.
   3.876 + * @pos:    the &struct hlist_node to use as a loop cursor.
   3.877 + * @member:    the name of the hlist_node within the struct.
   3.878 + */
   3.879 +#define hlist_for_each_entry_continue(tpos, pos, member)                \
   3.880 +    for (pos = (pos)->next;                                             \
   3.881 +         pos && ({ prefetch(pos->next); 1;}) &&                         \
   3.882 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   3.883 +         pos = pos->next)
   3.884 +
   3.885 +/**
   3.886 + * hlist_for_each_entry_from - iterate over a hlist continuing from
   3.887 + *                             current point
   3.888 + * @tpos:    the type * to use as a loop cursor.
   3.889 + * @pos:    the &struct hlist_node to use as a loop cursor.
   3.890 + * @member:    the name of the hlist_node within the struct.
   3.891 + */
   3.892 +#define hlist_for_each_entry_from(tpos, pos, member)                    \
   3.893 +    for (; pos && ({ prefetch(pos->next); 1;}) &&                       \
   3.894 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   3.895 +         pos = pos->next)
   3.896 +
   3.897 +/**
   3.898 + * hlist_for_each_entry_safe - iterate over list of given type safe
   3.899 + *                             against removal of list entry
   3.900 + * @tpos:    the type * to use as a loop cursor.
   3.901 + * @pos:    the &struct hlist_node to use as a loop cursor.
   3.902 + * @n:        another &struct hlist_node to use as temporary storage
   3.903 + * @head:    the head for your list.
   3.904 + * @member:    the name of the hlist_node within the struct.
   3.905 + */
   3.906 +#define hlist_for_each_entry_safe(tpos, pos, n, head, member)           \
   3.907 +    for (pos = (head)->first;                                           \
   3.908 +         pos && ({ n = pos->next; 1; }) &&                              \
   3.909 +         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});       \
   3.910 +         pos = n)
   3.911 +
   3.912 +
   3.913 +/**
   3.914 + * hlist_for_each_entry_rcu - iterate over rcu list of given type
   3.915 + * @tpos:   the type * to use as a loop cursor.
   3.916 + * @pos:    the &struct hlist_node to use as a loop cursor.
   3.917 + * @head:   the head for your list.
   3.918 + * @member: the name of the hlist_node within the struct.
   3.919 + *
   3.920 + * This list-traversal primitive may safely run concurrently with
   3.921 + * the _rcu list-mutation primitives such as hlist_add_head_rcu()
   3.922 + * as long as the traversal is guarded by rcu_read_lock().
   3.923 + */
   3.924 +#define hlist_for_each_entry_rcu(tpos, pos, head, member)               \
   3.925 +     for (pos = (head)->first;                                          \
   3.926 +          rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&       \
   3.927 +          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   3.928 +          pos = pos->next)
   3.929 +
   3.930 +#endif /* __XEN_LIST_H__ */
   3.931 +
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/sched_rr.c	Tue Oct 13 16:06:36 2009 +0100
     4.3 @@ -0,0 +1,116 @@
     4.4 +#include <stdio.h>
     4.5 +#include <stdlib.h>
     4.6 +#include <assert.h>
     4.7 +
     4.8 +#define ASSERT assert
     4.9 +
    4.10 +#include "list.h"
    4.11 +#include "sim.h"
    4.12 +
    4.13 +
    4.14 +#define MAX_VMS 16
    4.15 +#define TSLICE 2000
    4.16 +
    4.17 +struct sched_vm {
    4.18 +    struct list_head queue;
    4.19 +    int vid;
    4.20 +    struct vm *v;
    4.21 +};
    4.22 +
    4.23 +struct {
    4.24 +    struct list_head queue;
    4.25 +    struct sched_vm vms[MAX_VMS];
    4.26 +} sched_priv;
    4.27 +
    4.28 +
    4.29 +void sched_rr_init(void)
    4.30 +{
    4.31 +    printf("%s()\n", __func__);
    4.32 +    INIT_LIST_HEAD(&sched_priv.queue);
    4.33 +}
    4.34 +
    4.35 +void sched_rr_vm_init(int vid)
    4.36 +{
    4.37 +    struct sched_vm *svm;
    4.38 +
    4.39 +    printf("%s: vm %d\n", __func__, vid);
    4.40 +
    4.41 +    if ( vid > MAX_VMS )
    4.42 +    {
    4.43 +        fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
    4.44 +        exit(1);
    4.45 +    }
    4.46 +
    4.47 +    svm = sched_priv.vms + vid;
    4.48 +
    4.49 +    INIT_LIST_HEAD(&svm->queue);
    4.50 +
    4.51 +    svm->vid = vid;
    4.52 +    svm->v = vm_from_vid(vid);
    4.53 +    
    4.54 +}
    4.55 +
    4.56 +void sched_rr_wake(int time, struct vm * v)
    4.57 +{
    4.58 +    struct sched_vm *svm;
    4.59 +
    4.60 +    printf("%s: time %d vid %d\n",
    4.61 +           __func__, time, v->vid);
    4.62 +
    4.63 +    svm = sched_priv.vms + v->vid;
    4.64 +
    4.65 +    ASSERT(list_empty(&svm->queue));
    4.66 +
    4.67 +    list_add_tail(&svm->queue, &sched_priv.queue);
    4.68 +}
    4.69 +
    4.70 +struct vm* sched_rr_schedule(int time, int pid)
    4.71 +{
    4.72 +    struct sched_vm *svm;
    4.73 +    struct vm *next, *prev;
    4.74 +
    4.75 +    printf("%s: time %d pid %d\n",
    4.76 +           __func__, time, pid);
    4.77 +    prev = current(pid);
    4.78 +
    4.79 +    if ( prev )
    4.80 +    {
    4.81 +        printf(" current v%d\n", prev->vid);
    4.82 +        svm = sched_priv.vms + prev->vid;
    4.83 +
    4.84 +        if ( svm->v->runstate == RUNSTATE_RUNNING )
    4.85 +        {
    4.86 +            printf(" adding to runqueue\n");
    4.87 +            list_add_tail(&svm->queue, &sched_priv.queue);
    4.88 +        }
    4.89 +    }
    4.90 +
    4.91 +    /* Take guy on front of runqueue, set new timer */
    4.92 +    if ( list_empty(&sched_priv.queue) )
    4.93 +    {
    4.94 +        printf(" No runnable entities\n");
    4.95 +        return NULL;
    4.96 +    }
    4.97 +
    4.98 +    svm = list_entry(sched_priv.queue.next, struct sched_vm, queue);
    4.99 +
   4.100 +    list_del_init(&svm->queue);
   4.101 +    next = svm->v;
   4.102 +
   4.103 +    sim_sched_timer(TSLICE, pid);
   4.104 +
   4.105 +    printf(" next: v%d\n", next->vid);
   4.106 +    
   4.107 +    return next;
   4.108 +}
   4.109 +
   4.110 +struct scheduler sched_rr =
   4.111 +{
   4.112 +    .name="round-robin",
   4.113 +    .ops = {
   4.114 +        .sched_init = sched_rr_init,
   4.115 +        .vm_init    = sched_rr_vm_init,
   4.116 +        .wake       = sched_rr_wake,
   4.117 +        .schedule   = sched_rr_schedule
   4.118 +    }
   4.119 +};
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/sim.h	Tue Oct 13 16:06:36 2009 +0100
     5.3 @@ -0,0 +1,74 @@
     5.4 +#ifndef __SIM_H
     5.5 +#define __SIM_H
     5.6 +
     5.7 +#include "stats.h"
     5.8 +
     5.9 +enum runstate {
    5.10 +    RUNSTATE_RUNNING,
    5.11 +    RUNSTATE_RUNNABLE,
    5.12 +    RUNSTATE_BLOCKED
    5.13 +};
    5.14 +
    5.15 +enum {
    5.16 +    STATE_RUN,
    5.17 +    STATE_PREEMPT,
    5.18 +    STATE_WAKE,
    5.19 +    STATE_BLOCK,
    5.20 +    STATE_MAX
    5.21 +};
    5.22 +
    5.23 +struct vm
    5.24 +{
    5.25 +    /* Public */
    5.26 +    int vid;
    5.27 +
    5.28 +    enum runstate runstate;
    5.29 +    int processor;
    5.30 +
    5.31 +    void *private;
    5.32 +
    5.33 +    /* State: i.e., runstate.  Phase: "runnable" or "blocked".  A single "runnable" phase may go through
    5.34 +     * several "runnable" and "running" states. */
    5.35 +    int state_start_time;
    5.36 +    int time_this_phase;
    5.37 +    int was_preempted;
    5.38 +
    5.39 +    struct {
    5.40 +        struct cycle_summary state[STATE_MAX];
    5.41 +    } stats;
    5.42 +
    5.43 +    int phase_index;
    5.44 +    const struct sim_phase *e; /* Shortcut pointer to workload->list[phase_index] */
    5.45 +    const struct vm_workload *workload;
    5.46 +
    5.47 +};
    5.48 +
    5.49 +struct sched_ops {
    5.50 +    void (*sched_init)(void);
    5.51 +    void (*vm_init)(int vid);
    5.52 +    void (*wake)(int time, struct vm* v);
    5.53 +    struct vm* (*schedule)(int time, int pid);
    5.54 +};
    5.55 +
    5.56 +struct scheduler {
    5.57 +    char *name;
    5.58 +    struct sched_ops ops;
    5.59 +};
    5.60 +
    5.61 +#define MAX_PCPU
    5.62 +struct global_pcpu_data {
    5.63 +    int count;
    5.64 +    struct pcpu {
    5.65 +        int pid;
    5.66 +        struct vm* current;
    5.67 +    } pcpus[MAX_PCPU];
    5.68 +};
    5.69 +extern struct global_pcpu_data P;
    5.70 +
    5.71 +struct vm* vm_from_vid(int vid);
    5.72 +#define current(_pid) (P.pcpus[(_pid)].current)
    5.73 +void sim_sched_timer(int time, int pid);
    5.74 +void sim_runstate_change(int now, struct vm *v, int new_runstate);
    5.75 +
    5.76 +#endif /* __SIM_H */
    5.77 +
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/simulator.c	Tue Oct 13 16:06:36 2009 +0100
     6.3 @@ -0,0 +1,491 @@
     6.4 +#include <stdlib.h>
     6.5 +#include <stdio.h>
     6.6 +#include <assert.h>
     6.7 +
     6.8 +#define ASSERT assert
     6.9 +
    6.10 +#include "stats.h"
    6.11 +#include "list.h"
    6.12 +#include "sim.h"
    6.13 +#include "workload.h"
    6.14 +
    6.15 +FILE *warn;
    6.16 +
    6.17 +enum event_type {
    6.18 +    EVT_BLOCK,
    6.19 +    EVT_WAKE,
    6.20 +    EVT_TIMER,
    6.21 +    EVT_MAX
    6.22 +};
    6.23 +
    6.24 +char *event_name[EVT_MAX] = {
    6.25 +    [EVT_BLOCK]="block",
    6.26 +    [EVT_WAKE] ="wake ",
    6.27 +    [EVT_TIMER]="timer"
    6.28 +};
    6.29 +
    6.30 +struct event {
    6.31 +    struct list_head event_list;
    6.32 +    enum event_type type;
    6.33 +    int time;
    6.34 +    int param;  /* Usually VM ID */ 
    6.35 +};
    6.36 +
    6.37 +char * state_name[STATE_MAX] = {
    6.38 +    [STATE_RUN]=    "run    ",
    6.39 +    [STATE_PREEMPT]="preempt",
    6.40 +    [STATE_WAKE]=   "wake   ",
    6.41 +    [STATE_BLOCK]=  "block  ",
    6.42 +};
    6.43 +
    6.44 +struct {
    6.45 +    int now;
    6.46 +    struct list_head events;
    6.47 +    struct list_head *timer;
    6.48 +    const struct sched_ops *sched_ops;
    6.49 +} sim;
    6.50 +
    6.51 +
    6.52 +struct {
    6.53 +    int count;
    6.54 +    struct vm vms[MAX_VMS];
    6.55 +} V;
    6.56 +
    6.57 +extern struct scheduler sched_rr;
    6.58 +int default_scheduler = 0;
    6.59 +struct scheduler *schedulers[] =
    6.60 +{
    6.61 +    &sched_rr,
    6.62 +};
    6.63 +
    6.64 +/* Options */
    6.65 +struct {
    6.66 +    int time_limit;
    6.67 +    int pcpu_count;
    6.68 +    const struct workload * workload;
    6.69 +    const struct scheduler * scheduler;
    6.70 +} opt = {
    6.71 +    .time_limit = 100000,
    6.72 +    .pcpu_count = 1,
    6.73 +    .workload = NULL,
    6.74 +};
    6.75 +
    6.76 +struct global_pcpu_data P;
    6.77 +
    6.78 +/* Sim list interface */
    6.79 +/* NB: Caller must free if they're not going to use it! */
    6.80 +#define list_event(_l) (list_entry((_l), struct event, event_list))
    6.81 +
    6.82 +struct event* sim_remove_event(int type, int param)
    6.83 +{
    6.84 +    struct event* ret = NULL;
    6.85 +    struct list_head *pos, *tmp;
    6.86 +
    6.87 +    /* Look for an event that matches this one and remove it */
    6.88 +    list_for_each_safe(pos, tmp, &sim.events)
    6.89 +    {
    6.90 +        struct event *tevt = list_event(pos);
    6.91 +        if ( tevt->type == type
    6.92 +             && tevt->param == param )
    6.93 +        {
    6.94 +            list_del(pos);
    6.95 +            ret = tevt;
    6.96 +            break;
    6.97 +        }
    6.98 +    }
    6.99 +
   6.100 +    return ret;
   6.101 +}
   6.102 +
   6.103 +void sim_insert_event(int time, int type, int param, int reset)
   6.104 +{
   6.105 +    struct list_head *pos = NULL;
   6.106 +    struct event *evt=NULL;
   6.107 +
   6.108 +    ASSERT(time >= sim.now);
   6.109 +
   6.110 +    if ( reset )
   6.111 +        evt=sim_remove_event(type, param);
   6.112 +
   6.113 +    if ( !evt )
   6.114 +        evt = (struct event *)malloc(sizeof(*evt));
   6.115 +
   6.116 +    printf(" [insert t%d %s param%d]\n",
   6.117 +           evt->time, event_name[evt->type], evt->param);
   6.118 +
   6.119 +    evt->time = time;
   6.120 +    evt->type = type;
   6.121 +    evt->param = param;
   6.122 +
   6.123 +    INIT_LIST_HEAD(&evt->event_list);
   6.124 +
   6.125 +    list_for_each(pos, &sim.events)
   6.126 +    {
   6.127 +        if ( list_event(pos)->time > evt->time )
   6.128 +            break;
   6.129 +    }
   6.130 +    list_add_tail(&evt->event_list, pos);
   6.131 +}
   6.132 +
   6.133 +struct event sim_next_event(void)
   6.134 +{
   6.135 +    struct event *evt;
   6.136 +    struct list_head *next;
   6.137 +
   6.138 +    ASSERT(!list_empty(&sim.events));
   6.139 +
   6.140 +    next=sim.events.next;
   6.141 +
   6.142 +    list_del(next);
   6.143 +    
   6.144 +    evt=list_event(next);
   6.145 +
   6.146 +    printf("%d: evt %s param%d\n",
   6.147 +           evt->time, event_name[evt->type], evt->param);
   6.148 +
   6.149 +    free(evt);
   6.150 +
   6.151 +    /* XXX */
   6.152 +    return *evt;
   6.153 +}
   6.154 +
   6.155 +/*
   6.156 + * VM simulation
   6.157 + */
   6.158 +void vm_next_event(struct vm *v)
   6.159 +{
   6.160 +    v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
   6.161 +
   6.162 +    v->e = v->workload->list + v->phase_index;
   6.163 +}
   6.164 +
   6.165 +struct vm* vm_from_vid(int vid)
   6.166 +{
   6.167 +    ASSERT(vid < V.count);
   6.168 +
   6.169 +    return V.vms + vid;
   6.170 +}
   6.171 +
   6.172 +void vm_block(int now, struct vm *v)
   6.173 +{
   6.174 +    ASSERT(v->e->type == PHASE_RUN);
   6.175 +    v->time_this_phase += now - v->state_start_time;
   6.176 +    printf("%s: v%d time_this_phase %d\n",
   6.177 +           __func__, v->vid, v->time_this_phase);
   6.178 +
   6.179 +    ASSERT(v->time_this_phase == v->e->time);
   6.180 +
   6.181 +    vm_next_event(v);
   6.182 +    
   6.183 +    ASSERT(v->e->type == PHASE_BLOCK);
   6.184 +
   6.185 +    sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
   6.186 +    v->time_this_phase = 0;
   6.187 +    v->was_preempted = 0;
   6.188 +}
   6.189 +
   6.190 +/* Called when wake event happens; increment timer and reset state */
   6.191 +void vm_wake(int now, struct vm *v)
   6.192 +{
   6.193 +    ASSERT(v->e->type == PHASE_BLOCK);
   6.194 +    ASSERT(v->time_this_phase == 0);
   6.195 +
   6.196 +    v->time_this_phase = now - v->state_start_time;
   6.197 +
   6.198 +    if ( now != 0 )
   6.199 +        ASSERT(v->time_this_phase == v->e->time);
   6.200 +
   6.201 +    vm_next_event(v);
   6.202 +
   6.203 +    v->time_this_phase = 0;
   6.204 +}
   6.205 +
   6.206 +/* Called when actually starting to run; make block event and set state */
   6.207 +void vm_run(int now, struct vm *v)
   6.208 +{
   6.209 +    ASSERT(v->e->type == PHASE_RUN);
   6.210 +    ASSERT(v->time_this_phase < v->e->time);
   6.211 +
   6.212 +    sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
   6.213 +    v->state_start_time = now;
   6.214 +}
   6.215 +
   6.216 +/* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
   6.217 + * generate a new block event) */
   6.218 +void vm_preempt(int now, struct vm *v)
   6.219 +{
   6.220 +    struct event* evt;
   6.221 +
   6.222 +    if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
   6.223 +        free(evt);
   6.224 +
   6.225 +    v->time_this_phase += now - v->state_start_time;
   6.226 +    printf("%s: v%d time_this_phase %d\n",
   6.227 +           __func__, v->vid, v->time_this_phase);
   6.228 +
   6.229 +    ASSERT(v->time_this_phase < v->e->time);
   6.230 +
   6.231 +    v->was_preempted = 1;
   6.232 +}
   6.233 +
   6.234 +
   6.235 +/* Callbacks the scheduler may make */
   6.236 +void sim_sched_timer(int time, int pid)
   6.237 +{
   6.238 +    sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
   6.239 +}
   6.240 +
   6.241 +void sim_runstate_change(int now, struct vm *v, int new_runstate)
   6.242 +{
   6.243 +    int ostate, nstate;
   6.244 +    int stime = now - v->state_start_time;
   6.245 +
   6.246 +    /* Valid transitions:
   6.247 +     * + R->A (preemption): remove block event
   6.248 +     * + R->B (block)     : Insert wake event
   6.249 +     * + A->R (run)       : Insert block event
   6.250 +     * + B->A (wake)      : No action necessary
   6.251 +     */
   6.252 +
   6.253 +    switch ( v->runstate )
   6.254 +    {
   6.255 +    case RUNSTATE_RUNNING:
   6.256 +        ostate = STATE_RUN;
   6.257 +        break;
   6.258 +    case RUNSTATE_RUNNABLE:
   6.259 +        if ( v->was_preempted )
   6.260 +            ostate = STATE_PREEMPT;
   6.261 +        else
   6.262 +            ostate = STATE_WAKE;
   6.263 +        break;
   6.264 +    case RUNSTATE_BLOCKED:
   6.265 +        ostate = STATE_BLOCK;
   6.266 +        break;
   6.267 +    }
   6.268 +
   6.269 +    update_cycles(&v->stats.state[ostate], stime);
   6.270 +
   6.271 +
   6.272 +    if ( v->runstate == RUNSTATE_RUNNING
   6.273 +         && new_runstate == RUNSTATE_RUNNABLE )
   6.274 +    {
   6.275 +        nstate = STATE_PREEMPT;
   6.276 +        vm_preempt(now, v);
   6.277 +    }
   6.278 +    else if ( v->runstate == RUNSTATE_RUNNING
   6.279 +              && new_runstate == RUNSTATE_BLOCKED )
   6.280 +    {
   6.281 +        nstate = STATE_BLOCK;
   6.282 +        vm_block(now, v);
   6.283 +    }
   6.284 +    else if ( v->runstate == RUNSTATE_RUNNABLE
   6.285 +              && new_runstate == RUNSTATE_RUNNING )
   6.286 +    {
   6.287 +        nstate = STATE_RUN;
   6.288 +        vm_run(now, v);
   6.289 +    }
   6.290 +    else if ( v->runstate == RUNSTATE_BLOCKED
   6.291 +              && new_runstate == RUNSTATE_RUNNABLE )
   6.292 +    {
   6.293 +        nstate = STATE_WAKE;
   6.294 +        vm_wake(now, v);
   6.295 +    }
   6.296 +    else
   6.297 +        goto unexpected_transition;
   6.298 +
   6.299 +    printf("%d: v%d %s %d -> %s\n",
   6.300 +           now, v->vid, state_name[ostate], stime, state_name[nstate]);
   6.301 +
   6.302 +    v->runstate = new_runstate;
   6.303 +    v->state_start_time = now;
   6.304 +
   6.305 +    return;
   6.306 +
   6.307 +unexpected_transition:
   6.308 +    fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
   6.309 +            v->vid,
   6.310 +            v->runstate,
   6.311 +            new_runstate);
   6.312 +    exit(1);
   6.313 +}
   6.314 +
   6.315 +/* 
   6.316 + * Main loop
   6.317 + */
   6.318 +void simulate(void)
   6.319 +{
   6.320 +    while ( sim.now < opt.time_limit )
   6.321 +    {
   6.322 +        /* Take next event off list */
   6.323 +        struct event evt;
   6.324 +
   6.325 +        evt = sim_next_event();
   6.326 +
   6.327 +        sim.now = evt.time;
   6.328 +
   6.329 +        switch(evt.type)
   6.330 +        {
   6.331 +        case EVT_WAKE:
   6.332 +        {
   6.333 +            struct vm *v = vm_from_vid(evt.param);
   6.334 +            ASSERT(v->processor == -1);
   6.335 +            sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
   6.336 +            sim.sched_ops->wake(sim.now, v);
   6.337 +        }
   6.338 +        break;
   6.339 +        case EVT_BLOCK:
   6.340 +        {
   6.341 +            struct vm *v = vm_from_vid(evt.param);
   6.342 +
   6.343 +            ASSERT(v->processor != -1);
   6.344 +            ASSERT(v->processor <= P.count);
   6.345 +
   6.346 +            sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
   6.347 +
   6.348 +            evt.param = v->processor; /* FIXME */
   6.349 +        }
   6.350 +        /* FALL-THRU */
   6.351 +        case EVT_TIMER:
   6.352 +        {
   6.353 +            struct vm *prev, *next;
   6.354 +            int pid = evt.param;
   6.355 +
   6.356 +            ASSERT(pid < P.count);
   6.357 +
   6.358 +            prev = P.pcpus[pid].current;
   6.359 +
   6.360 +            next = sim.sched_ops->schedule(sim.now, pid);
   6.361 +
   6.362 +            if ( prev && prev != next )
   6.363 +            {
   6.364 +                prev->processor = -1;
   6.365 +                if( prev->runstate != RUNSTATE_BLOCKED )
   6.366 +                    sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
   6.367 +            }
   6.368 +
   6.369 +            sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
   6.370 +            P.pcpus[pid].current = next;
   6.371 +            next->processor = pid;
   6.372 +        }
   6.373 +        break;
   6.374 +        default:
   6.375 +            fprintf(stderr, "Unexpected event type: %d\n", evt.type);
   6.376 +            exit(1);
   6.377 +            break;
   6.378 +        }
   6.379 +    }
   6.380 +}
   6.381 +
   6.382 +void init(void)
   6.383 +{
   6.384 +    int vid, i;
   6.385 +    const struct workload *w;
   6.386 +
   6.387 +    /* Initialize simulation variables */
   6.388 +    sim.now=0;
   6.389 +    sim.timer=NULL;
   6.390 +    INIT_LIST_HEAD(&sim.events);
   6.391 +    sim.sched_ops = &opt.scheduler->ops;
   6.392 +
   6.393 +    /* Initialize pcpus */
   6.394 +    P.count = opt.pcpu_count;
   6.395 +    for ( i=0; i<P.count; i++ )
   6.396 +    {
   6.397 +        P.pcpus[i].pid = i;
   6.398 +        P.pcpus[i].current = NULL;
   6.399 +    }
   6.400 +
   6.401 +    /* Initialize scheduler */
   6.402 +    sim.sched_ops->sched_init();
   6.403 +
   6.404 +    /* Initialize vms */
   6.405 +    w=opt.workload;
   6.406 +    for ( vid=0; vid<w->vm_count; vid++)
   6.407 +    {
   6.408 +        struct vm *v = V.vms+vid;
   6.409 +
   6.410 +        v->vid = vid;
   6.411 +        v->runstate = RUNSTATE_BLOCKED;
   6.412 +        v->processor = -1;
   6.413 +        v->private = NULL;
   6.414 +
   6.415 +        v->state_start_time = 0;
   6.416 +        v->time_this_phase = 0;
   6.417 +        
   6.418 +
   6.419 +        v->phase_index = -1;
   6.420 +        v->e = NULL;
   6.421 +        v->workload = w->vm_workloads+vid;
   6.422 +        
   6.423 +        V.count++;
   6.424 +
   6.425 +        sim.sched_ops->vm_init(vid);
   6.426 +    }
   6.427 +
   6.428 +    /* Set VM starting conditions */
   6.429 +    for ( vid=0; vid<V.count; vid++)
   6.430 +    {
   6.431 +        struct vm *v = V.vms+vid;
   6.432 +
   6.433 +        switch(v->workload->list[0].type)
   6.434 +        {
   6.435 +        case PHASE_RUN:
   6.436 +            v->phase_index = v->workload->phase_count - 1;
   6.437 +            v->e = v->workload->list + v->phase_index;
   6.438 +
   6.439 +            sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
   6.440 +            v->state_start_time = sim.now;
   6.441 +            v->time_this_phase = 0;
   6.442 +            break;
   6.443 +        case PHASE_BLOCK:
   6.444 +            v->phase_index = 0;
   6.445 +            v->e = v->workload->list;
   6.446 +
   6.447 +            sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
   6.448 +            v->state_start_time = sim.now;
   6.449 +            v->time_this_phase = 0;
   6.450 +            break;
   6.451 +        }
   6.452 +    }
   6.453 +
   6.454 +    /* Insert initial scheduler timer */
   6.455 +    for ( i=0; i<P.count; i++)
   6.456 +        sim_insert_event(sim.now, EVT_TIMER, i, 1);
   6.457 +}
   6.458 +
   6.459 +void report(void)
   6.460 +{
   6.461 +    int i, j;
   6.462 +
   6.463 +    for ( i=0; i<V.count; i++ )
   6.464 +    {
   6.465 +        struct vm *v = V.vms + i;
   6.466 +
   6.467 +        printf("VM %d\n", i);
   6.468 +        for ( j = 0; j < STATE_MAX ; j++ )
   6.469 +        {
   6.470 +            char s[128];
   6.471 +            snprintf(s, 128, " %s", state_name[j]);
   6.472 +            print_cycle_summary(&v->stats.state[j],   sim.now, s);
   6.473 +        }
   6.474 +    }
   6.475 +}
   6.476 +
   6.477 +int main(int argc, char * argv[])
   6.478 +{
   6.479 +    warn = stdout;
   6.480 +
   6.481 +    /* Read opts, config file? */
   6.482 +    if ( !opt.workload )
   6.483 +        opt.workload = builtin_workloads+default_workload;
   6.484 +
   6.485 +    if ( !opt.scheduler )
   6.486 +        opt.scheduler = schedulers[default_scheduler];
   6.487 +    /* Setup simulation */
   6.488 +    init();
   6.489 +    
   6.490 +    /* Run simulation */
   6.491 +    simulate();
   6.492 +    /* Report statistics */
   6.493 +    report();
   6.494 +}
     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/stats.c	Tue Oct 13 16:06:36 2009 +0100
     7.3 @@ -0,0 +1,339 @@
     7.4 +#include <stdlib.h>
     7.5 +#include <stdio.h>
     7.6 +#include <assert.h>
     7.7 +
     7.8 +#include "stats.h"
     7.9 +
    7.10 +#define DEFAULT_SAMPLE_SIZE 10240
    7.11 +
    7.12 +static struct {
    7.13 +    int sample_size;
    7.14 +} opt = {
    7.15 +    .sample_size = DEFAULT_SAMPLE_SIZE,
    7.16 +};
    7.17 +
    7.18 +void set_sampel_size(int n)
    7.19 +{
    7.20 +    opt.sample_size = n;
    7.21 +}
    7.22 +
    7.23 +extern FILE *warn;
    7.24 +
    7.25 +/* With compliments to "Numerical Recipes in C", which provided the algorithm
    7.26 + * and basic template for this function. */
    7.27 +#if 0
    7.28 +static long long percentile(long long * A, int N, int ple) {
    7.29 +    int I, J, L, R, K;
    7.30 +
    7.31 +    long long X, W;
    7.32 +
    7.33 +    /* No samples! */
    7.34 +    if ( N == 0 )
    7.35 +        return 0;
    7.36 +
    7.37 +    /* Find K, the element # we want */
    7.38 +    K=N*ple/100;
    7.39 +
    7.40 +    /* Set the left and right boundaries of the current search space */
    7.41 +    L=0; R=N-1;
    7.42 +
    7.43 +    while(L < R) {
    7.44 +        /* X: The value to order everything higher / lower than */
    7.45 +        X=A[K];
    7.46 +
    7.47 +        /* Starting at the left and the right... */
    7.48 +        I=L;
    7.49 +        J=R;
    7.50 +
    7.51 +        do {
    7.52 +            /* Find the first element on the left that is out-of-order w/ X */
    7.53 +            while(A[I]<X)
    7.54 +                I++;
    7.55 +            /* Find the first element on the right that is out-of-order w/ X */
    7.56 +            while(X<A[J])
    7.57 +                J--;
    7.58 +
    7.59 +            /* If we found something out-of-order */
    7.60 +            if(I<=J) {
    7.61 +                /* Switch the values */
    7.62 +                W=A[I];
    7.63 +                A[I]=A[J];
    7.64 +                A[J]=W;
    7.65 +
    7.66 +                /* And move on */
    7.67 +                I++; J--;
    7.68 +            }
    7.69 +        } while (I <= J); /* Keep going until our pointers meet or pass */
    7.70 +    
    7.71 +        /* Re-adjust L and R, based on which element we're looking for */
    7.72 +        if(J<K)
    7.73 +            L=I;
    7.74 +        if(K<I)
    7.75 +            R=J;
    7.76 +    }
    7.77 +
    7.78 +    return A[K];
    7.79 +}
    7.80 +
    7.81 +static float weighted_percentile(float * A, /* values */
    7.82 +                                       unsigned long long * w, /* weights */
    7.83 +                                       int N,                  /* total */
    7.84 +                                       int ple)                /* percentile */
    7.85 +{
    7.86 +    int L, R, I, J, K;
    7.87 +    unsigned long long L_weight, R_weight, I_weight, J_weight,
    7.88 +        K_weight, N_weight;
    7.89 +
    7.90 +    float X, t1;
    7.91 +    unsigned long long t2;
    7.92 +
    7.93 +    int progress;
    7.94 +
    7.95 +    /* Calculate total weight */
    7.96 +    N_weight=0;
    7.97 +
    7.98 +    for(I=0; I<N; I++) {
    7.99 +        assert(w[I]!=0);
   7.100 +        N_weight += w[I];
   7.101 +    }
   7.102 +
   7.103 +    /* Find K_weight, the target weight we want */
   7.104 +    K_weight = N_weight * ple / 100;
   7.105 +
   7.106 +    /* Set the left and right boundaries of the current search space */
   7.107 +    L=0;
   7.108 +    L_weight = 0;
   7.109 +    R=N-1;
   7.110 +    R_weight = N_weight - w[R];
   7.111 +
   7.112 +    /* Search between L and R, narrowing down until we're done */
   7.113 +    while(L < R) {
   7.114 +        /* Chose an ordering value from right in the middle */
   7.115 +        K = (L + R) >> 1;
   7.116 +        /* X: The value to order everything higher / lower than */
   7.117 +        X=A[K];
   7.118 +
   7.119 +        /* Starting at the left and the right... */
   7.120 +        I=L; I_weight = L_weight;
   7.121 +        J=R; J_weight = R_weight;
   7.122 +
   7.123 +        do {
   7.124 +            /* Find the first element on the left that is out-of-order w/ X */
   7.125 +            while(A[I]<X) {
   7.126 +                I_weight += w[I];
   7.127 +                I++;
   7.128 +            }
   7.129 +            /* Find the first element on the right that is out-of-order w/ X */
   7.130 +            while(X<A[J]) {
   7.131 +                J_weight -= w[J];
   7.132 +                J--;
   7.133 +            }
   7.134 +
   7.135 +            /* If we actually found something... */
   7.136 +            if(I<=J) {
   7.137 +                /* Switch the values */
   7.138 +                t1=A[I];
   7.139 +                A[I]=A[J];
   7.140 +                A[J]=t1;
   7.141 +
   7.142 +                t2=w[I];
   7.143 +                w[I]=w[J];
   7.144 +                w[J]=t2;
   7.145 +
   7.146 +                /* And move in */
   7.147 +                I_weight += w[I];
   7.148 +                I++;
   7.149 +
   7.150 +                J_weight -= w[J];
   7.151 +                J--;
   7.152 +            }
   7.153 +        } while (I <= J); /* Keep going until our pointers meet or pass */
   7.154 +
   7.155 +        progress = 0;
   7.156 +    
   7.157 +        /* Re-adjust L and R, based on which element we're looking for */
   7.158 +        if(J_weight<K_weight) {
   7.159 +            progress = 1;
   7.160 +            L=I; L_weight = I_weight;
   7.161 +        }
   7.162 +        if(K_weight<I_weight) {
   7.163 +            progress = 1;
   7.164 +            R=J; R_weight = J_weight;
   7.165 +        }
   7.166 +    }
   7.167 +
   7.168 +    return A[L];
   7.169 +}
   7.170 +#endif
   7.171 +
   7.172 +static long long self_weighted_percentile(long long * A,
   7.173 +                                   int N,            /* total */
   7.174 +                                   int ple)          /* percentile */
   7.175 +{
   7.176 +    int L, R, I, J, K;
   7.177 +    long long L_weight, R_weight, I_weight, J_weight,
   7.178 +        K_weight, N_weight;
   7.179 +
   7.180 +    long long X, t1;
   7.181 +
   7.182 +    int progress;
   7.183 +
   7.184 +    /* Calculate total weight */
   7.185 +    N_weight=0;
   7.186 +
   7.187 +    for(I=0; I<N; I++) {
   7.188 +        if(A[I] < 0)
   7.189 +            fprintf(warn, "%s: Value %lld less than zero!\n",
   7.190 +                    __func__, A[I]);
   7.191 +        assert(A[I]!=0);
   7.192 +        N_weight += A[I];
   7.193 +    }
   7.194 +
   7.195 +    /* Find K_weight, the target weight we want */
   7.196 +    K_weight = N_weight * ple / 100;
   7.197 +
   7.198 +    /* Set the left and right boundaries of the current search space */
   7.199 +    L=0;
   7.200 +    L_weight = 0;
   7.201 +    R=N-1;
   7.202 +    R_weight = N_weight - A[R];
   7.203 +
   7.204 +    /* Search between L and R, narrowing down until we're done */
   7.205 +    while(L < R) {
   7.206 +        /* Chose an ordering value from right in the middle */
   7.207 +        K = (L + R) >> 1;
   7.208 +        /* X: The value to order everything higher / lower than */
   7.209 +        X=A[K];
   7.210 +
   7.211 +        /* Starting at the left and the right... */
   7.212 +        I=L; I_weight = L_weight;
   7.213 +        J=R; J_weight = R_weight;
   7.214 +
   7.215 +        do {
   7.216 +            /* Find the first element on the left that is out-of-order w/ X */
   7.217 +            while(A[I]<X) {
   7.218 +                I_weight += A[I];
   7.219 +                I++;
   7.220 +            }
   7.221 +            /* Find the first element on the right that is out-of-order w/ X */
   7.222 +            while(X<A[J]) {
   7.223 +                J_weight -= A[J];
   7.224 +                J--;
   7.225 +            }
   7.226 +
   7.227 +            /* If we actually found something... */
   7.228 +            if(I<=J) {
   7.229 +                /* Switch the values */
   7.230 +                t1=A[I];
   7.231 +                A[I]=A[J];
   7.232 +                A[J]=t1;
   7.233 +
   7.234 +                /* And move in */
   7.235 +                I_weight += A[I];
   7.236 +                I++;
   7.237 +
   7.238 +                J_weight -= A[J];
   7.239 +                J--;
   7.240 +            }
   7.241 +        } while (I <= J); /* Keep going until our pointers meet or pass */
   7.242 +
   7.243 +        progress = 0;
   7.244 +    
   7.245 +        /* Re-adjust L and R, based on which element we're looking for */
   7.246 +        if(J_weight<K_weight) {
   7.247 +            progress = 1;
   7.248 +            L=I; L_weight = I_weight;
   7.249 +        }
   7.250 +        if(K_weight<I_weight) {
   7.251 +            progress = 1;
   7.252 +            R=J; R_weight = J_weight;
   7.253 +        }
   7.254 +    }
   7.255 +
   7.256 +    return A[L];
   7.257 +}
   7.258 +
   7.259 +void update_cycles(struct cycle_summary *s, long long c) {
   7.260 +/* We don't know ahead of time how many samples there are, and working
   7.261 + * with dynamic stuff is a pain, and unnecessary.  This algorithm will
   7.262 + * generate a sample set that approximates an even sample.  We can
   7.263 + * then take the percentiles on this, and get an approximate value. */
   7.264 +    int lap, index;
   7.265 +
   7.266 +    if ( c == 0 )
   7.267 +        return;
   7.268 +
   7.269 +    if ( opt.sample_size ) {
   7.270 +        lap = (s->count/opt.sample_size)+1;
   7.271 +        index =s->count % opt.sample_size;
   7.272 +
   7.273 +        if((index - (lap/3))%lap == 0) {
   7.274 +            if(!s->sample) {
   7.275 +                s->sample = malloc(sizeof(*s->sample) * opt.sample_size);
   7.276 +                if(!s->sample) {
   7.277 +                    fprintf(stderr, "%s: malloc failed!\n", __func__);
   7.278 +                    exit(1);
   7.279 +                }
   7.280 +            }
   7.281 +            s->sample[index] = c;
   7.282 +        }
   7.283 +    }
   7.284 +
   7.285 +    if(c > 0) {
   7.286 +        s->cycles += c;
   7.287 +    } else {
   7.288 +        s->cycles += -c;
   7.289 +    }
   7.290 +    s->count++;
   7.291 +}
   7.292 +
   7.293 +void print_cycle_summary(struct cycle_summary *s,
   7.294 +                         tsc_t total, char *p) {
   7.295 +    if(s->count) {
   7.296 +        long long avg;
   7.297 +        double percent;
   7.298 +
   7.299 +        avg = s->cycles / s->count;
   7.300 +
   7.301 +        if ( total )
   7.302 +            percent = ((double)(s->cycles * 100)) / total;
   7.303 +
   7.304 +        if ( opt.sample_size ) {
   7.305 +            long long p5, p50, p95;
   7.306 +            int data_size = s->count;
   7.307 +
   7.308 +            if(data_size > opt.sample_size)
   7.309 +                data_size = opt.sample_size;
   7.310 +
   7.311 +            p50 = self_weighted_percentile(s->sample, data_size, 50);
   7.312 +            p5 = self_weighted_percentile(s->sample, data_size, 5);
   7.313 +            p95 = self_weighted_percentile(s->sample, data_size, 95);
   7.314 +
   7.315 +            if ( total )
   7.316 +                printf("%s: %7d %llu %5.2lf%% %6lld {%6lld|%6lld|%6lld}\n",
   7.317 +                       p, s->count,
   7.318 +                       s->cycles,
   7.319 +                       percent,
   7.320 +                       avg, p5, p50, p95);
   7.321 +            else
   7.322 +                printf("%s: %7d %llu %6lld {%6lld|%6lld|%6lld}\n",
   7.323 +                       p, s->count,
   7.324 +                       s->cycles,
   7.325 +                       avg, p5, p50, p95);
   7.326 +                
   7.327 +        } else {
   7.328 +            if ( total )
   7.329 +                printf("%s: %7d %llu %5.2lf%% %6lld\n",
   7.330 +                       p, s->count, 
   7.331 +                       s->cycles,
   7.332 +                       percent,
   7.333 +                       avg);
   7.334 +            else
   7.335 +                printf("%s: %7d %llu %6lld\n",
   7.336 +                       p, s->count, 
   7.337 +                       s->cycles,
   7.338 +                       avg);
   7.339 +        }
   7.340 +    }
   7.341 +}
   7.342 +
     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/stats.h	Tue Oct 13 16:06:36 2009 +0100
     8.3 @@ -0,0 +1,16 @@
     8.4 +#ifndef _STATS_H
     8.5 +#define _STATS_H
     8.6 +
     8.7 +typedef unsigned long long tsc_t;
     8.8 +
     8.9 +struct cycle_summary {
    8.10 +    int count;
    8.11 +    unsigned long long cycles;
    8.12 +    long long *sample;
    8.13 +};
    8.14 +
    8.15 +void set_sample_size(int n);
    8.16 +void update_cycles(struct cycle_summary *s, long long c);
    8.17 +void print_cycle_summary(struct cycle_summary *s,
    8.18 +                         tsc_t total, char *p);
    8.19 +#endif
     9.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.2 +++ b/workload.h	Tue Oct 13 16:06:36 2009 +0100
     9.3 @@ -0,0 +1,23 @@
     9.4 +#ifndef __WORKLOAD_H
     9.5 +#define __WORKLOAD_H
     9.6 +struct sim_phase {
     9.7 +    enum { PHASE_RUN, PHASE_BLOCK } type;
     9.8 +    int time;
     9.9 +};
    9.10 +
    9.11 +#define MAX_VMS 16
    9.12 +#define MAX_PHASES 16
    9.13 +struct vm_workload {
    9.14 +    int phase_count;
    9.15 +    const struct sim_phase list[MAX_PHASES];
    9.16 +};
    9.17 +
    9.18 +struct workload {
    9.19 +    const char * name;
    9.20 +    int vm_count;
    9.21 +    const struct vm_workload vm_workloads[MAX_VMS];
    9.22 +};
    9.23 +
    9.24 +extern const int default_workload;
    9.25 +extern struct workload builtin_workloads[];
    9.26 +#endif
    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/workloads.c	Tue Oct 13 16:06:36 2009 +0100
    10.3 @@ -0,0 +1,48 @@
    10.4 +#include "workload.h"
    10.5 +
    10.6 +const int default_workload = 0;
    10.7 +struct workload builtin_workloads[] =
    10.8 +{
    10.9 +    {
   10.10 +        .name="Sx3",
   10.11 +        .vm_count=3,
   10.12 +        .vm_workloads = {
   10.13 +            { .phase_count = 2,
   10.14 +              .list = {
   10.15 +                    {
   10.16 +                    .type=PHASE_RUN,
   10.17 +                    .time=695
   10.18 +                    },
   10.19 +                    {
   10.20 +                    .type=PHASE_BLOCK,
   10.21 +                    .time=5
   10.22 +                    },
   10.23 +                }
   10.24 +            },
   10.25 +            { .phase_count = 2,
   10.26 +              .list = {
   10.27 +                    {
   10.28 +                    .type=PHASE_RUN,
   10.29 +                    .time=1095
   10.30 +                    },
   10.31 +                    {
   10.32 +                    .type=PHASE_BLOCK,
   10.33 +                    .time=5
   10.34 +                    },
   10.35 +                }
   10.36 +            },
   10.37 +            { .phase_count = 2,
   10.38 +              .list = {
   10.39 +                    {
   10.40 +                    .type=PHASE_RUN,
   10.41 +                    .time=1295
   10.42 +                    },
   10.43 +                    {
   10.44 +                    .type=PHASE_BLOCK,
   10.45 +                    .time=5
   10.46 +                    },
   10.47 +                }
   10.48 +            },
   10.49 +        }
   10.50 +    },
   10.51 +};