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
  27 #ifndef V3_CONFIG_DEBUG_EXT_CPU_MAPPER_EDF
  28 #undef PrintDebug
  29 #define PrintDebug(fmt, args...)
  30 #endif
  31
  32
  33 /* Overview
  34  *
  35  * cpu_mapper for EDF Scheduling
  36  *
  37  */
  38
  39 #define MAX_TDF 20
  40 #define MIN_TDF 1
  41
  42
  43 // First Next Fit heuristic implementation
  44
  45 int firstNextFit(int save, int tdf,struct v3_vm_info *vm){
  46
  47     V3_Print(vm, VCORE_NONE,"firstNextFit for tdf %d \n", tdf);
  48
  49     int V = vm->num_cores; // Number of virtual cores
  50     int L = vm->avail_cores;  // Number of Logical cores
  51     int ULCores[L]; // Utilization array for logical cores
  52     int uVCores[V]; // Utilization array for virtual cores
  53     int mapping[V];
  54     int vc=0; // virtual core id
  55     int lc=0; // logical core id
  56
  57     int i=0;
  58
  59     for(i=0;i<L;i++){
  60         ULCores[i] = 0;
  61     }
  62
  63     for(i=0;i<V;i++){
  64         uVCores[i] = 0;
  65     }
  66
  67     for(i=0;i<V;i++){
  68         mapping[i] = 0;
  69     }
  70
  71     // Initialize Virtual cores utilization vector
  72     v3_cfg_tree_t * cfg_tree = vm->cfg_data->cfg;
  73     v3_cfg_tree_t * core = v3_cfg_subtree(v3_cfg_subtree(cfg_tree, "cores"), "core");
  74
  75     while (core){
  76
  77         char *period = v3_cfg_val(core, "period");
  78         char *slice = v3_cfg_val(core, "slice");
  79         uint64_t p = atoi(period);
  80         uint64_t s = atoi(slice);
  81         uVCores[vc]= 100 * s / p;
  82         vc++;
  83         core = v3_cfg_next_branch(core);
  84     }
  85
  86     vc = 0;
  87
  88     // TODO Control Target CPU case
  89
  90     while(vc < V){
  91
  92         if( ULCores[lc] + (uVCores[vc])/tdf  <= 100 ){
  93             ULCores[lc] = ULCores[lc] + (uVCores[vc])/tdf;
  94             mapping[vc] = lc;
  95         }
  96         else{
  97             if ((lc+1)< L){
  98                lc = lc+1;
  99                ULCores[lc] = ULCores[lc] + (uVCores[vc])/tdf;
 100                mapping[vc] = lc;
 101             }
 102             else{
 103                 return -1;  // Could not map
 104             }
 105
 106         }
 107
 108       vc = vc +1;
 109      }
 110
 111     if(save ==0){
 112
 113         vc=0;
 114
 115         // Assing computed TDF
 116         struct v3_time *vm_ts = &(vm->time_state);
 117         vm_ts->td_denom = tdf;
 118
 119         // mapping virtual cores in logical cores
 120         for (vc = 0; vc < vm->num_cores; vc++) {
 121             struct guest_info * core = &(vm->cores[vc]);
 122             core-> pcpu_id = mapping[vc];
 123         }
 124
 125
 126         int x = 0;
 127         for(x=0;x<V;x++){
 128             PrintDebug(vm, VCORE_NONE,"%d ",mapping[x]);
 129         }
 130
 131        for(x=0;x<L; x++){
 132             PrintDebug(vm, VCORE_NONE,"%d ",ULCores[x]);
 133         }
 134         PrintDebug(vm, VCORE_NONE,"\n");
 135
 136     }
 137
 138     return 0;
 139 }
 140
 141
 142 int edf_mapper_vm_init(struct v3_vm_info *vm, unsigned int cpu_mask){
 143
 144     V3_Print(vm, VCORE_NONE,"mapper. Initializing edf cpu_mapper");
 145
 146     int min_tdf = MIN_TDF;
 147     int max_tdf = MAX_TDF;
 148     int tdf = MAX_TDF; // Time dilation factor
 149
 150
 151      // Binary Search of TDF
 152
 153     int mappable = 0;
 154
 155     while( (max_tdf-min_tdf) > 0 ){
 156
 157         mappable = firstNextFit(-1,tdf,vm);
 158
 159         if(mappable != -1){
 160             max_tdf = tdf/2;
 161         }
 162         else{
 163             max_tdf = tdf * 2;
 164             min_tdf = tdf;
 165         }
 166         tdf = max_tdf;
 167     }
 168
 169     firstNextFit(0,tdf,vm);
 170
 171
 172     return 0;
 173 }
 174
 175
 176 int edf_mapper_admit(struct v3_vm_info *vm){
 177     // TODO
 178     PrintDebug(vm, VCORE_NONE,"mapper. Edf cpu_mapper admit");
 179     return 0;
 180 }
 181
 182 int edf_mapper_admit_core(struct v3_vm_info * vm, int vcore_id, int target_cpu){
 183     // TODO
 184     PrintDebug(vm, VCORE_NONE,"mapper. Edf cpu_mapper admit core");
 185     return 0;
 186 }
 187
 188
 189 static struct vm_cpu_mapper_impl edf_mapper = {
 190
 191     .name = "edf",
 192     .init = NULL,
 193     .deinit = NULL,
 194     .vm_init = edf_mapper_vm_init,
 195     .vm_deinit = NULL,
 196     .admit = edf_mapper_admit,
 197     .admit_core = edf_mapper_admit_core
 198
 199 };
 200
 201
 202 static int
 203 ext_mapper_edf_init() {
 204     PrintDebug(VM_NONE, VCORE_NONE,"mapper. Creating (%s) cpu_mapper\n",edf_mapper.name);
 205     return v3_register_cpu_mapper(&edf_mapper);
 206 }
 207
 208 static int
 209 ext_mapper_edf_vm_init() {
 210     return 0;
 211 }
 212
 213 static struct v3_extension_impl mapper_edf_impl = {
 214
 215     .name = "cpu_mapper for EDF Scheduler",
 216     .init = ext_mapper_edf_init,
 217     .vm_init = ext_mapper_edf_vm_init,
 218     .vm_deinit = NULL,
 219     .core_init = NULL,
 220     .core_deinit = NULL,
 221     .on_entry = NULL,
 222     .on_exit = NULL
 223 };
 224
 225 register_extension(&mapper_edf_impl);