Genetic I/O CFQ scheduler support. Signed-off-by: Miguel Boton Index: linux.2.6.23/block/cfq-iosched.c =================================================================== --- linux.2.6.23.orig/block/cfq-iosched.c +++ linux.2.6.23/block/cfq-iosched.c @@ -11,25 +11,45 @@ #include #include #include +#include +#include +#include /* * tunables */ -static const int cfq_quantum = 4; /* max queue in one round of service */ -static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 }; -static const int cfq_back_max = 16 * 1024; /* maximum backwards seek, in KiB */ -static const int cfq_back_penalty = 2; /* penalty of a backwards seek */ - -static const int cfq_slice_sync = HZ / 10; -static int cfq_slice_async = HZ / 25; -static const int cfq_slice_async_rq = 2; -static int cfq_slice_idle = HZ / 125; +#define CFQ_QUANTUM 4 +#define CFQ_FIFO_EXPIRE_ASYNC HZ / 4 +#define CFQ_FIFO_EXPIRE_SYNC HZ / 8 +#define CFQ_BACK_MAX 16 * 1024 +#define CFQ_BACK_PENALTY 2 + +#define CFQ_SLICE_SYNC HZ / 10 +#define CFQ_SLICE_ASYNC HZ / 25 +#define CFQ_SLICE_ASYNC_RQ 2 +#define CFQ_SLICE_IDLE HZ / 125 + +/* max queue in one round of service */ +static int cfq_quantum = CFQ_QUANTUM; +static int cfq_fifo_expire[2] = + { CFQ_FIFO_EXPIRE_ASYNC, CFQ_FIFO_EXPIRE_SYNC }; +/* maximum backwards seek, in KiB */ +static int cfq_back_max = CFQ_BACK_MAX; +/* penalty of a backwards seek */ +static int cfq_back_penalty = CFQ_BACK_PENALTY; + +static int cfq_slice_sync = CFQ_SLICE_SYNC; +static int cfq_slice_async = CFQ_SLICE_ASYNC; +static int cfq_slice_async_rq = CFQ_SLICE_ASYNC_RQ; +static int cfq_slice_idle = CFQ_SLICE_IDLE; /* * grace period before allowing idle class to get disk access */ #define CFQ_IDLE_GRACE (HZ / 10) +static int cfq_idle_grace = CFQ_IDLE_GRACE; + /* * below this threshold, we consider thinktime immediate */ @@ -115,6 +131,10 @@ unsigned int cfq_slice_idle; struct list_head cic_list; + +#ifdef CONFIG_GENETIC_IOSCHED_CFQ + struct list_head data_list; +#endif }; /* @@ -197,6 +217,126 @@ CFQ_CFQQ_FNS(sync); #undef CFQ_CFQQ_FNS +#ifdef CONFIG_GENETIC_IOSCHED_CFQ + +struct disk_stats_snapshot *cfq_stats_snapshot; + +extern void disk_stats_snapshot(phenotype_t *pt); +#ifdef CONFIG_FINGERPRINTING +extern void disk_get_fingerprint(phenotype_t *pt); +extern void disk_update_fingerprint(phenotype_t *pt); +extern void *cfq_create_genes(phenotype_t *pt); +#endif + +static void cfq_num_ops_create_child(genetic_child_t *child); +static void cfq_throughput_create_child(genetic_child_t *child); +static void cfq_latency_create_child(genetic_child_t *child); +static void cfq_general_create_child(genetic_child_t *child); + +static void cfq_general_set_child_genes(void *in_genes); + +static void cfq_num_ops_calc_fitness(genetic_child_t *child); +static void cfq_throughput_calc_fitness(genetic_child_t *child); +static void cfq_latency_calc_fitness(genetic_child_t *child); + +static void cfq_general_calc_post_fitness(phenotype_t *in_pt); + +static void cfq_shift_mutation_rate(phenotype_t *in_pt); + +struct genetic_ops cfq_num_ops_genetic_ops = { + .create_child = cfq_num_ops_create_child, + .calc_fitness = cfq_num_ops_calc_fitness, +}; + +struct genetic_ops cfq_throughput_genetic_ops = { + .create_child = cfq_throughput_create_child, + .calc_fitness = cfq_throughput_calc_fitness, +}; + +struct genetic_ops cfq_latency_genetic_ops = { + .create_child = cfq_latency_create_child, + .calc_fitness = cfq_latency_calc_fitness, +}; + +struct genetic_ops cfq_general_genetic_ops = { + .create_child = cfq_general_create_child, + .set_child_genes = cfq_general_set_child_genes, + .combine_genes = genetic_generic_combine_genes, + .mutate_child = genetic_generic_mutate_child, + .calc_post_fitness = cfq_general_calc_post_fitness, + .take_snapshot = disk_stats_snapshot, + .shift_mutation_rate = cfq_shift_mutation_rate, + .gene_show = genetic_generic_gene_show, +#ifdef CONFIG_FINGERPRINTING + .get_fingerprint = disk_get_fingerprint, + .update_fingerprint = disk_update_fingerprint, + .create_top_genes = cfq_create_genes, + .top_fitness_show = fingerprint_top_fitness_show, + .snapshot_show = fingerprint_snapshot_show, + .state_show = fingerprint_state_show, +#endif +}; + +#define CFQ_NUM_CHILDREN 8 + +#define CFQ_NUM_OPS_UID 1 +#define CFQ_NUM_OPS_NUM_GENES 0 + +#define CFQ_THROUGHPUT_UID 2 +#define CFQ_THROUGHPUT_NUM_GENES 0 + +#define CFQ_LATENCY_UID 4 +#define CFQ_LATENCY_NUM_GENES 0 + +#define CFQ_GENERAL_UID (CFQ_NUM_OPS_UID | CFQ_THROUGHPUT_UID | CFQ_LATENCY_UID) +#define CFQ_GENERAL_NUM_GENES 11 + +struct cfq_genes { + int cfq_quantum; + int cfq_fifo_expire_async; + int cfq_fifo_expire_sync; + int cfq_back_max; + int cfq_back_penalty; + int cfq_slice_sync; + int cfq_slice_async; + int cfq_slice_async_rq; + int cfq_slice_idle; + int cfq_idle_grace; + unsigned long nr_requests; +}; + +gene_param_t cfq_gene_param[CFQ_GENERAL_NUM_GENES] = { + { "cfq_quantum", + CFQ_QUANTUM / 2, 3 * CFQ_QUANTUM / 2, CFQ_QUANTUM, 0 }, + { "cfq_fifo_expire_async", + CFQ_FIFO_EXPIRE_ASYNC / 2, 3 * CFQ_FIFO_EXPIRE_ASYNC / 2, CFQ_FIFO_EXPIRE_ASYNC, 0 }, + { "cfq_fifo_expire_sync", + CFQ_FIFO_EXPIRE_SYNC / 2, 3 * CFQ_FIFO_EXPIRE_SYNC / 2, CFQ_FIFO_EXPIRE_SYNC, 0 }, + { "cfq_back_max", + CFQ_BACK_MAX / 2, 3 * CFQ_BACK_MAX / 2, CFQ_BACK_MAX, 0 }, + { "cfq_back_penalty", + CFQ_BACK_PENALTY / 2, 3 * CFQ_BACK_PENALTY / 2, CFQ_BACK_PENALTY, 0 }, + { "cfq_slice_sync", + CFQ_SLICE_SYNC / 2, 3 * CFQ_SLICE_SYNC / 2, CFQ_SLICE_SYNC, 0 }, + { "cfq_slice_async", + CFQ_SLICE_ASYNC / 2, 3 * CFQ_SLICE_ASYNC / 2, CFQ_SLICE_ASYNC, 0 }, + { "cfq_slice_async_rq", + CFQ_SLICE_ASYNC_RQ / 2, 3 * CFQ_SLICE_ASYNC_RQ / 2, CFQ_SLICE_ASYNC_RQ, 0 }, + { "cfq_slice_idle", + CFQ_SLICE_IDLE / 2, 3 * CFQ_SLICE_IDLE / 2, CFQ_SLICE_IDLE, 0 }, + { "cfq_idle_grace", + CFQ_IDLE_GRACE / 2, 3 * CFQ_IDLE_GRACE / 2, CFQ_IDLE_GRACE, 0 }, + { "nr_requests", + BLKDEV_MIN_RQ, BLKDEV_MAX_RQ * 30, BLKDEV_MAX_RQ, genetic_generic_iterative_mutate_gene } +}; + +extern long long disk_num_ops_calc_fitness(genetic_child_t *child); +extern long long disk_throughput_calc_fitness(genetic_child_t *child); +extern long long disk_latency_calc_fitness(genetic_child_t *child); + +LIST_HEAD(cfq_data_list); +#endif + static void cfq_dispatch_insert(struct request_queue *, struct request *); static struct cfq_queue *cfq_get_queue(struct cfq_data *, int, struct task_struct *, gfp_t); @@ -813,7 +942,7 @@ * the grace period has passed or arm the idle grace * timer */ - end = cfqd->last_end_request + CFQ_IDLE_GRACE; + end = cfqd->last_end_request + cfq_idle_grace; if (time_before(jiffies, end)) { mod_timer(&cfqd->idle_class_timer, end); cfqq = NULL; @@ -2045,7 +2174,7 @@ /* * race with a non-idle queue, reset timer */ - end = cfqd->last_end_request + CFQ_IDLE_GRACE; + end = cfqd->last_end_request + cfq_idle_grace; if (!time_after_eq(jiffies, end)) mod_timer(&cfqd->idle_class_timer, end); else @@ -2101,6 +2230,10 @@ cfq_shutdown_timer_wq(cfqd); +#ifdef CONFIG_GENETIC_IOSCHED_CFQ + list_del(&cfqd->data_list); +#endif + kfree(cfqd); } @@ -2137,6 +2270,10 @@ cfqd->cfq_slice_async_rq = cfq_slice_async_rq; cfqd->cfq_slice_idle = cfq_slice_idle; +#ifdef CONFIG_GENETIC_IOSCHED_CFQ + list_add_tail(&cfqd->data_list, &cfq_data_list); +#endif + return cfqd; } @@ -2275,6 +2412,46 @@ { int ret; +#ifdef CONFIG_GENETIC_IOSCHED_CFQ + genetic_t *genetic = NULL; + + cfq_stats_snapshot = (struct disk_stats_snapshot *) + kmalloc(sizeof(struct disk_stats_snapshot), GFP_KERNEL); + if (!cfq_stats_snapshot) + panic("cfq: failed to malloc enough space"); + + ret = genetic_init(&genetic, CFQ_NUM_CHILDREN, 2 * HZ, + 1, "cfq-ioscheduler"); + if (ret) + panic("cfq: failed to init genetic lib"); + + if (genetic_register_phenotype(genetic, &cfq_num_ops_genetic_ops, + CFQ_NUM_CHILDREN, "num_ops", + CFQ_NUM_OPS_NUM_GENES, + CFQ_NUM_OPS_UID)) + panic("cfq: failed to register num_ops phenotype"); + + if (genetic_register_phenotype(genetic, &cfq_throughput_genetic_ops, + CFQ_NUM_CHILDREN, "throughput", + CFQ_THROUGHPUT_NUM_GENES, + CFQ_THROUGHPUT_UID)) + panic("cfq: failed to register throughput phenotype"); + + if (genetic_register_phenotype(genetic, &cfq_latency_genetic_ops, + CFQ_NUM_CHILDREN, "latency", + CFQ_LATENCY_NUM_GENES, + CFQ_LATENCY_UID)) + panic("cfq: failed to register latency phenotype"); + + if (genetic_register_phenotype(genetic, &cfq_general_genetic_ops, + CFQ_NUM_CHILDREN, "general", + CFQ_GENERAL_NUM_GENES, + CFQ_GENERAL_UID)) + panic("cfq: failed to register general phenotype"); + + genetic_start(genetic); +#endif + /* * could be 0 on HZ < 1000 setups */ @@ -2306,6 +2473,201 @@ cfq_slab_kill(); } +#ifdef CONFIG_GENETIC_IOSCHED_CFQ + +static void cfq_num_ops_create_child(genetic_child_t *child) +{ + BUG_ON(!child); + + child->genes = 0; + child->gene_param = 0; + child->num_genes = CFQ_NUM_OPS_NUM_GENES; + child->stats_snapshot = cfq_stats_snapshot; +} + +static void cfq_throughput_create_child(genetic_child_t *child) +{ + BUG_ON(!child); + + child->genes = 0; + child->gene_param = 0; + child->num_genes = CFQ_THROUGHPUT_NUM_GENES; + child->stats_snapshot = cfq_stats_snapshot; +} + +static void cfq_latency_create_child(genetic_child_t *child) +{ + BUG_ON(!child); + + child->genes = 0; + child->gene_param = 0; + child->num_genes = CFQ_LATENCY_NUM_GENES; + child->stats_snapshot = cfq_stats_snapshot; +} + +/* need to create the genes for the child */ +static void cfq_general_create_child(genetic_child_t *child) +{ + BUG_ON(!child); + + child->genes = kmalloc(sizeof(struct cfq_genes), GFP_KERNEL); + if (!child->genes) + panic("cfq_general_create_child: error mallocing space"); + + child->gene_param = cfq_gene_param; + child->num_genes = CFQ_GENERAL_NUM_GENES; + child->stats_snapshot = cfq_stats_snapshot; + + genetic_create_child_spread(child, CFQ_NUM_CHILDREN-1); + + ((struct cfq_genes *)child->genes)->nr_requests = BLKDEV_MAX_RQ; +} + +static void cfq_shift_mutation_rate(phenotype_t *in_pt) +{ + struct list_head *p; + phenotype_t *pt; + int count = 0; + long rate = 0; + + list_for_each(p, &in_pt->genetic->phenotype) { + pt = list_entry(p, phenotype_t, phenotype); + + /* Look at everyone else that contributes to this + phenotype */ + if (pt->uid & CFQ_GENERAL_UID && pt->uid != CFQ_GENERAL_UID) { + + switch (pt->uid) { + case CFQ_NUM_OPS_UID: + case CFQ_THROUGHPUT_UID: + case CFQ_LATENCY_UID: + rate += pt->mutation_rate; + count++; + break; + default: + BUG(); + } + } + } + + /* If we are a general phenotype that is made up of other + phenotypes then we take the average */ + if (count) + in_pt->mutation_rate = (rate / count); + else + BUG(); +} + +static void cfq_general_set_child_genes(void *in_genes) +{ + struct cfq_genes *genes = (struct cfq_genes *)in_genes; + struct list_head *d; + struct cfq_data *cfqd; + + list_for_each(d, &cfq_data_list) { + cfqd = list_entry(d, struct cfq_data, data_list); + + cfqd->cfq_quantum = genes->cfq_quantum; + cfqd->cfq_fifo_expire[0] = genes->cfq_fifo_expire_async; + cfqd->cfq_fifo_expire[1] = genes->cfq_fifo_expire_sync; + cfqd->cfq_back_max = genes->cfq_back_max; + cfqd->cfq_back_penalty = genes->cfq_back_penalty; + cfqd->cfq_slice[0] = genes->cfq_slice_async; + cfqd->cfq_slice[1] = genes->cfq_slice_sync; + cfqd->cfq_slice_async_rq = genes->cfq_slice_async_rq; + cfqd->cfq_slice_idle = genes->cfq_slice_idle; + cfqd->queue->nr_requests = genes->nr_requests; + } +} + +static void cfq_num_ops_calc_fitness(genetic_child_t *child) +{ + child->fitness = disk_num_ops_calc_fitness(child); +} + +static void cfq_throughput_calc_fitness(genetic_child_t *child) +{ + child->fitness = disk_throughput_calc_fitness(child); +} + +static void cfq_latency_calc_fitness(genetic_child_t *child) +{ + child->fitness = disk_latency_calc_fitness(child); +} + +/* Make the general the one that takes into account all the fitness + * routines, since these are the common genes that effect everything. + */ +static void cfq_general_calc_post_fitness(phenotype_t *in_pt) +{ + struct list_head *p; + phenotype_t *pt; + genetic_t *genetic = in_pt->genetic; + int ranking[CFQ_NUM_CHILDREN]; + int weight = 1; + int i; + + memset(ranking, 0, sizeof(ranking)); + + list_for_each(p, &genetic->phenotype) { + pt = list_entry(p, phenotype_t, phenotype); + + /* Look at everyone else that contributes to this + phenotype */ + if (pt->uid & CFQ_GENERAL_UID && pt->uid != CFQ_GENERAL_UID) { + + switch (pt->uid) { + case CFQ_NUM_OPS_UID: + weight = 2; + break; + case CFQ_THROUGHPUT_UID: + weight = 2; + break; + case CFQ_LATENCY_UID: + weight = 1; + break; + default: + BUG(); + } + + for (i = 0; i < pt->num_children; i++) + ranking[pt->child_ranking[i]->id] += (i * weight); + } + } + + for (i = 0; i < in_pt->num_children; i++) + in_pt->child_ranking[i]->fitness = ranking[i]; + +} + +#ifdef CONFIG_FINGERPRINTING +void *cfq_create_genes(phenotype_t *pt) +{ + struct cfq_genes *genes = kmalloc(sizeof(struct cfq_genes), GFP_KERNEL); + + if (!genes) { + printk(KERN_ERR "cfq_create_genes: unable to alloc space\n"); + return 0; + } + + /* at some point...make these intelligent depending on what + * the workload is + */ + genes->cfq_quantum = CFQ_QUANTUM; + genes->cfq_back_max = CFQ_BACK_MAX; + genes->cfq_back_penalty = CFQ_BACK_PENALTY; + genes->cfq_slice_sync = CFQ_SLICE_SYNC; + genes->cfq_slice_async = CFQ_SLICE_ASYNC; + genes->cfq_slice_async_rq = CFQ_SLICE_ASYNC_RQ; + genes->cfq_idle_grace = CFQ_IDLE_GRACE; + genes->nr_requests = BLKDEV_MAX_RQ; + + return (void *)genes; +} +#endif /* CONFIG_FINGERPRINTING */ + +#endif + module_init(cfq_init); module_exit(cfq_exit); Index: linux.2.6.23/block/Kconfig.iosched =================================================================== --- linux.2.6.23.orig/block/Kconfig.iosched +++ linux.2.6.23/block/Kconfig.iosched @@ -77,6 +77,15 @@ anticipatory scheduler autonomically and will adapt tunables depending on the present workload. +config GENETIC_IOSCHED_CFQ + bool "Genetic CFQ I/O scheduler (EXPERIMENTAL)" + depends on IOSCHED_CFQ && GENETIC_LIB && EXPERIMENTAL + default n + ---help--- + This will use a genetic algorithm to tweak the tunables of the + CFQ scheduler autonomically and will adapt tunables + depending on the present workload. + endmenu endif