palacios/src/extensions/ext_cpu_mapper_edf.c

   1 /*
   2  * This file is part of the Palacios Virtual Machine Monitor developed
   3  * by the V3VEE Project with funding from the United States National
   4  * Science Foundation and the Department of Energy.
   5  *
   6  * The V3VEE Project is a joint project between Northwestern University
   7  * and the University of New Mexico.  You can find out more at
   8  * http://www.v3vee.org
   9  *
  10  * Copyright (c) 2013, Oscar Mondragon <omondrag@cs.unm.edu>
  11  * Copyright (c) 2013, The V3VEE Project <http://www.v3vee.org>
  12  * All rights reserved.
  13  *
  14  * Author: Oscar Mondragon <omondrag@cs.unm.edu>
  15  *
  16  * This is free software.  You are permitted to use,
  17  * redistribute, and modify it as specified in the file "V3VEE_LICENSE".
  18  */
  19
  20
  21 #include <palacios/vmm.h>
  22 #include <palacios/vm_guest.h>
  23 #include <palacios/vmm_extensions.h>
  24 #include <palacios/vmm_cpu_mapper.h>
  25
  26 #ifndef V3_CONFIG_DEBUG_EXT_CPU_MAPPER_EDF
  27 #undef PrintDebug
  28 #define PrintDebug(fmt, args...)
  29 #endif
  30
  31
  32 /* Overview
  33  *
  34  * cpu_mapper for EDF Scheduling
  35  *
  36  */
  37
  38 #define MAX_TDF 20
  39 #define MIN_TDF 1
  40 #define UTILIZATION 80
  41
  42 // Next Fit heuristic implementation
  43
  44 int nextFit(int save, int tdf,struct v3_vm_info *vm){
  45
  46     PrintDebug(vm, VCORE_NONE,"nextFit for tdf %d \n", tdf);
  47
  48     int V = vm->num_cores;          // Number of virtual cores
  49     int L = vm->avail_cores;        // Number of Logical cores
  50     int speedRatio[L];              // mapped virtual cores to logical core ratio. Must be less or equal than UTILIZATION X TDF
  51     uint64_t speedVCores[V];        // Virtual core speeds
  52     int mapping[V];                 // mapping array
  53     int vc=0;                       // virtual core id
  54     int lc=0;                       // logical core id
  55     uint_t cpu_khz = V3_CPU_KHZ();  // Physical core speed
  56     int i=0;
  57
  58     for(i=0;i<L;i++){
  59         speedRatio[i]=0;
  60     }
  61
  62     for(i=0;i<V;i++){
  63         mapping[i] = 0;
  64         speedVCores[i] = 0;
  65     }
  66
  67     // Initialize Virtual cores utilization vector
  68     v3_cfg_tree_t * cfg_tree = vm->cfg_data->cfg;
  69     v3_cfg_tree_t * core = v3_cfg_subtree(v3_cfg_subtree(cfg_tree, "cores"), "core");
  70
  71     while (core){
  72
  73         uint_t vcSpeed = cpu_khz;
  74         char *speed = v3_cfg_val(core, "khz");
  75         if(speed){
  76             vcSpeed = atoi(speed);
  77         }
  78
  79         speedVCores[vc] = vcSpeed;
  80         vc++;
  81         core = v3_cfg_next_branch(core);
  82
  83         /*PrintDebug(VM_NONE, VCORE_NONE,"mapper. vc %d, speed %llu, vcores %d, lcores %d, cpu_khz %u\n",
  84                vc,
  85                vcSpeed,
  86                V,
  87                L,
  88                cpu_khz);*/
  89
  90  }
  91
  92
  93     vc = 0;
  94
  95     // TODO Control Target CPU case
  96
  97     while(vc < V){
  98
  99       //PrintDebug(VM_NONE, VCORE_NONE,"mapper. vc %d, ratio %llu, tdf %d\n",vc, (speedRatio[lc] + 100*speedVCores[vc]/cpu_khz), tdf);
 100
 101       if( (speedRatio[lc] + 100*speedVCores[vc]/cpu_khz) <= (UTILIZATION*tdf)){
 102             mapping[vc] = lc;
 103             speedRatio[lc] += 100*speedVCores[vc]/cpu_khz;
 104         }
 105         else{
 106           if (((lc+1)< L) &&  (100*speedVCores[vc]/cpu_khz <= (UTILIZATION*tdf))){
 107                lc = lc+1;
 108                mapping[vc] = lc;
 109                speedRatio[lc] += 100*speedVCores[vc]/cpu_khz;
 110             }
 111             else{
 112                 return -1;  // Could not map
 113             }
 114
 115         }
 116
 117       vc = vc +1;
 118      }
 119
 120     if(save ==0){
 121
 122         vc=0;
 123
 124         // Assing computed TDF
 125         struct v3_time *vm_ts = &(vm->time_state);
 126         vm_ts->td_denom = tdf;
 127
 128         // mapping virtual cores in logical cores
 129         for (vc = 0; vc < vm->num_cores; vc++) {
 130             struct guest_info * core = &(vm->cores[vc]);
 131             core-> pcpu_id = mapping[vc];
 132         }
 133
 134
 135         int x = 0;
 136         PrintDebug(vm, VCORE_NONE,"mapper. Number of Logical cores: %d",L);
 137         PrintDebug(vm, VCORE_NONE, "mapper. Mapping Array:\n");
 138         for(x=0;x<V;x++){
 139             PrintDebug(vm, VCORE_NONE,"mapper. vcore %d: %d ",x,mapping[x]);
 140         }
 141     }
 142
 143     return 0;
 144 }
 145
 146
 147 int edf_mapper_vm_init(struct v3_vm_info *vm){
 148
 149     PrintDebug(vm, VCORE_NONE,"mapper. Initializing edf cpu_mapper");
 150     return 0;
 151 }
 152
 153
 154 int edf_mapper_admit(struct v3_vm_info *vm, unsigned int cpu_mask){
 155     PrintDebug(vm, VCORE_NONE,"mapper. Edf cpu_mapper admit\n");
 156
 157     int min_tdf = MIN_TDF;
 158     int max_tdf = MAX_TDF;
 159     int tdf = MAX_TDF; // Time dilation factor
 160
 161
 162      // Binary Search of TDF
 163
 164     int mappable = 0;
 165
 166     while( (max_tdf-min_tdf) > 0 ){
 167
 168         mappable = nextFit(-1,tdf,vm);
 169
 170         if(mappable != -1){
 171             max_tdf = tdf/2;
 172         }
 173         else{
 174             max_tdf = tdf * 2;
 175             min_tdf = tdf;
 176         }
 177         tdf = max_tdf;
 178     }
 179
 180     mappable =  nextFit(-1,tdf,vm);
 181     if(mappable !=-1){
 182         nextFit(0,tdf,vm);
 183     }
 184     else{
 185         tdf = 2*tdf;
 186         nextFit(0,tdf,vm);
 187     }
 188
 189     PrintDebug(vm, VCORE_NONE,"mapper. Calculated TDF denom %d\n",tdf);
 190    return 0;
 191 }
 192
 193 int edf_mapper_admit_core(struct v3_vm_info * vm, int vcore_id, int target_cpu){
 194     PrintDebug(vm, VCORE_NONE,"mapper. Edf cpu_mapper admit core\n");
 195     return 0;
 196 }
 197
 198
 199 static struct vm_cpu_mapper_impl edf_mapper = {
 200
 201     .name = "edf",
 202     .init = NULL,
 203     .deinit = NULL,
 204     .vm_init = edf_mapper_vm_init,
 205     .vm_deinit = NULL,
 206     .admit = edf_mapper_admit,
 207     .admit_core = edf_mapper_admit_core
 208
 209 };
 210
 211
 212 static int
 213 ext_mapper_edf_init() {
 214     PrintDebug(VM_NONE, VCORE_NONE,"mapper. Creating (%s) cpu_mapper\n",edf_mapper.name);
 215     return v3_register_cpu_mapper(&edf_mapper);
 216 }
 217
 218 static int
 219 ext_mapper_edf_vm_init() {
 220     return 0;
 221 }
 222
 223 static struct v3_extension_impl mapper_edf_impl = {
 224
 225     .name = "cpu_mapper for EDF Scheduler",
 226     .init = ext_mapper_edf_init,
 227     .vm_init = ext_mapper_edf_vm_init,
 228     .vm_deinit = NULL,
 229     .core_init = NULL,
 230     .core_deinit = NULL,
 231     .on_entry = NULL,
 232     .on_exit = NULL
 233 };
 234
 235 register_extension(&mapper_edf_impl);