Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge pull request #2 from mquinson/master
[simgrid.git] / src / surf / maxmin.cpp
1 /* Copyright (c) 2004-2015. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 /* \file callbacks.h */
8
9 #include "xbt/sysdep.h"
10 #include "xbt/log.h"
11 #include "xbt/mallocator.h"
12 #include "maxmin_private.hpp"
13 #include <stdlib.h>
14 #include <stdio.h>              /* sprintf */
15 #include <math.h>
16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf,
17                                 "Logging specific to SURF (maxmin)");
18
19 typedef struct s_dyn_light {
20   int *data;
21   int pos;
22   int size;
23 } s_dyn_light_t, *dyn_light_t;
24
25 double sg_maxmin_precision = 0.00001;
26 double sg_surf_precision   = 0.00001;
27
28 static void *lmm_variable_mallocator_new_f(void);
29 static void lmm_variable_mallocator_free_f(void *var);
30 #define lmm_variable_mallocator_reset_f ((void_f_pvoid_t)NULL)
31 static void lmm_update_modified_set(lmm_system_t sys,
32                                     lmm_constraint_t cnst);
33 static void lmm_remove_all_modified_set(lmm_system_t sys);
34 static int Global_debug_id = 1;
35 static int Global_const_debug_id = 1;
36
37 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var);
38 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
39                                      lmm_constraint_t cnst);
40
41 static void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr);
42 static void lmm_enable_var(lmm_system_t sys, lmm_variable_t var);
43 static int lmm_can_enable_var(lmm_variable_t var);
44 static void lmm_disable_var(lmm_system_t sys, lmm_variable_t var);
45 static int lmm_concurrency_slack(lmm_constraint_t cnstr);
46 static int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var);
47
48 static void lmm_check_concurrency(lmm_system_t sys);
49   
50 inline void lmm_decrease_concurrency(lmm_constraint_t cnstr){
51   xbt_assert(cnstr->concurrency_current>0);
52   cnstr->concurrency_current--;
53 }
54
55 inline void lmm_increase_concurrency(lmm_constraint_t cnstr){
56   if(++cnstr->concurrency_current > cnstr->concurrency_maximum)
57     cnstr->concurrency_maximum=cnstr->concurrency_current;
58   xbt_assert(cnstr->concurrency_limit<0 || cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency limit overflow!");
59 }
60
61 lmm_system_t lmm_system_new(int selective_update)
62 {
63   lmm_system_t l = NULL;
64   s_lmm_variable_t var;
65   s_lmm_constraint_t cnst;
66
67   l = xbt_new0(s_lmm_system_t, 1);
68
69   l->modified = 0;
70   l->selective_update_active = selective_update;
71   l->visited_counter = 1;
72
73   XBT_DEBUG("Setting selective_update_active flag to %d",
74          l->selective_update_active);
75
76   xbt_swag_init(&(l->variable_set),
77                 xbt_swag_offset(var, variable_set_hookup));
78   xbt_swag_init(&(l->constraint_set),
79                 xbt_swag_offset(cnst, constraint_set_hookup));
80
81   xbt_swag_init(&(l->active_constraint_set),
82                 xbt_swag_offset(cnst, active_constraint_set_hookup));
83
84   xbt_swag_init(&(l->modified_constraint_set),
85                 xbt_swag_offset(cnst, modified_constraint_set_hookup));
86   xbt_swag_init(&(l->saturated_variable_set),
87                 xbt_swag_offset(var, saturated_variable_set_hookup));
88   xbt_swag_init(&(l->saturated_constraint_set),
89                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
90
91   l->variable_mallocator = xbt_mallocator_new(65536,
92                                               lmm_variable_mallocator_new_f,
93                                               lmm_variable_mallocator_free_f,
94                                               lmm_variable_mallocator_reset_f);
95
96   return l;
97 }
98
99 void lmm_system_free(lmm_system_t sys)
100 {
101   lmm_variable_t var = NULL;
102   lmm_constraint_t cnst = NULL;
103
104   
105   while ((var = (lmm_variable_t) extract_variable(sys))) {
106     XBT_WARN
107         ("Variable %p (%d) still in  system when freing it: this may be a bug",
108          var, var->id_int);
109     lmm_var_free(sys, var);
110   }
111
112   while ((cnst = (lmm_constraint_t) extract_constraint(sys)))
113     lmm_cnst_free(sys, cnst);
114
115   xbt_mallocator_free(sys->variable_mallocator);
116   free(sys);
117 }
118
119 static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var)
120 {
121   int i;
122   int nelements;
123   
124   lmm_element_t elem = NULL;
125   
126   XBT_IN("(sys=%p, var=%p)", sys, var);
127   sys->modified = 1;
128
129   //TODOLATER Can do better than that by leaving only the variable in only one enabled_element_set, call lmm_update_modified_set, and then remove it..
130   if(var->cnsts_number)
131       lmm_update_modified_set(sys, var->cnsts[0].constraint);
132
133   for (i = 0; i < var->cnsts_number; i++) {
134     elem = &var->cnsts[i];
135     if(var->weight>0)
136       lmm_decrease_concurrency(elem->constraint);
137     xbt_swag_remove(elem, &(elem->constraint->enabled_element_set));
138     xbt_swag_remove(elem, &(elem->constraint->disabled_element_set));
139     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
140     nelements=xbt_swag_size(&(elem->constraint->enabled_element_set)) +
141               xbt_swag_size(&(elem->constraint->disabled_element_set));
142     if (!nelements)
143       make_constraint_inactive(sys, elem->constraint);
144   //Check if we can enable new variables going through the constraints where var was.
145     else
146       lmm_on_disabled_var(sys,elem->constraint);
147   }
148
149   var->cnsts_number = 0;
150   XBT_OUT();
151 }
152
153 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
154 {
155
156   lmm_variable_remove(sys, var);
157   xbt_mallocator_release(sys->variable_mallocator, var);
158 }
159
160 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
161                                      lmm_constraint_t cnst)
162 {
163   make_constraint_inactive(sys, cnst);
164   free(cnst);
165 }
166
167 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
168                                     double bound_value)
169 {
170   lmm_constraint_t cnst = NULL;
171   s_lmm_element_t elem;
172
173   cnst = xbt_new0(s_lmm_constraint_t, 1);
174   cnst->id = id;
175   cnst->id_int = Global_const_debug_id++;
176   xbt_swag_init(&(cnst->enabled_element_set),
177                 xbt_swag_offset(elem, enabled_element_set_hookup));
178   xbt_swag_init(&(cnst->disabled_element_set),
179                 xbt_swag_offset(elem, disabled_element_set_hookup));
180   xbt_swag_init(&(cnst->active_element_set),
181                 xbt_swag_offset(elem, active_element_set_hookup));
182
183   cnst->bound = bound_value;
184   cnst->concurrency_maximum=0;
185   cnst->concurrency_current=0;
186   //TODO MARTIN Maybe a configuration item for the default cap concurrency? 
187   cnst->concurrency_limit=100;
188   cnst->usage = 0;
189   cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */
190   insert_constraint(sys, cnst);
191
192   return cnst;
193 }
194
195 void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit)
196 {
197   cnst->concurrency_limit = concurrency_limit;
198 }
199
200 void lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst)
201 {
202   cnst->concurrency_maximum = 0;
203 }
204
205 int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst)
206 {
207   return cnst->concurrency_maximum;
208 }
209
210 void lmm_constraint_shared(lmm_constraint_t cnst)
211 {
212   cnst->sharing_policy = 0;
213 }
214
215 /** Return true if the constraint is shared, and false if it's FATPIPE */
216 int lmm_constraint_sharing_policy(lmm_constraint_t cnst)
217 {
218   return (cnst->sharing_policy);
219 }
220
221 /* @brief Remove a constraint 
222  * Currently this is dead code, but it is exposed in maxmin.h
223  * Apparently, this call was designed assuming that constraint would no more have elements in it. 
224  * If this is not the case, assertion will fail, and you need to add calls e.g. to lmm_shrink before effectively removing it.
225  */
226 XBT_INLINE void lmm_constraint_free(lmm_system_t sys,
227                                     lmm_constraint_t cnst)
228 {
229   xbt_assert(!xbt_swag_size(&(cnst->active_element_set)),"Removing constraint but it still has active elements");
230   xbt_assert(!xbt_swag_size(&(cnst->enabled_element_set)),"Removing constraint but it still has enabled elements");
231   xbt_assert(!xbt_swag_size(&(cnst->disabled_element_set)),"Removing constraint but it still has disabled elements");
232   remove_constraint(sys, cnst);
233   lmm_cnst_free(sys, cnst);
234 }
235
236 static void *lmm_variable_mallocator_new_f(void)
237 {
238   lmm_variable_t var = xbt_new(s_lmm_variable_t, 1);
239   var->cnsts = NULL; /* will be created by realloc */
240   return var;
241 }
242
243 static void lmm_variable_mallocator_free_f(void *var)
244 {
245   xbt_free(((lmm_variable_t) var)->cnsts);
246   xbt_free(var);
247 }
248
249 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
250                                 double weight,
251                                 double bound, int number_of_constraints)
252 {
253   lmm_variable_t var = NULL;
254   int i;
255
256   XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)",
257           sys, id, weight, bound, number_of_constraints);
258
259   var = (lmm_variable_t) xbt_mallocator_get(sys->variable_mallocator);
260   var->id = id;
261   var->id_int = Global_debug_id++;
262   var->cnsts = (s_lmm_element_t *) xbt_realloc(var->cnsts, number_of_constraints * sizeof(s_lmm_element_t));
263   for (i = 0; i < number_of_constraints; i++) {
264     var->cnsts[i].enabled_element_set_hookup.next = NULL;
265     var->cnsts[i].enabled_element_set_hookup.prev = NULL;
266     var->cnsts[i].disabled_element_set_hookup.next = NULL;
267     var->cnsts[i].disabled_element_set_hookup.prev = NULL;
268     var->cnsts[i].active_element_set_hookup.next = NULL;
269     var->cnsts[i].active_element_set_hookup.prev = NULL;
270     var->cnsts[i].constraint = NULL;
271     var->cnsts[i].variable = NULL;
272     var->cnsts[i].value = 0.0;
273   }
274   var->cnsts_size = number_of_constraints;
275   var->cnsts_number = 0;
276   var->weight = weight;
277   var->staged_weight = 0.0;
278   var->bound = bound;
279   var->concurrency_share = 1;
280   var->value = 0.0;
281   var->visited = sys->visited_counter - 1;
282   var->mu = 0.0;
283   var->new_mu = 0.0;
284   var->func_f = func_f_def;
285   var->func_fp = func_fp_def;
286   var->func_fpi = func_fpi_def;
287
288   var->variable_set_hookup.next = NULL;
289   var->variable_set_hookup.prev = NULL;
290   var->saturated_variable_set_hookup.next = NULL;
291   var->saturated_variable_set_hookup.prev = NULL;
292
293   if (weight)
294     xbt_swag_insert_at_head(var, &(sys->variable_set));
295   else
296     xbt_swag_insert_at_tail(var, &(sys->variable_set));
297
298   XBT_OUT(" returns %p", var);
299   return var;
300 }
301
302 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
303 {
304   remove_variable(sys, var);
305   lmm_var_free(sys, var);
306 }
307
308 double lmm_variable_getvalue(lmm_variable_t var)
309 {
310   return (var->value);
311 }
312
313
314 void lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share)
315 {
316   var->concurrency_share=concurrency_share;
317 }
318
319 double lmm_variable_getbound(lmm_variable_t var)
320 {
321   return (var->bound);
322 }
323
324 void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
325                 lmm_variable_t var)
326 {
327   lmm_element_t elem = NULL;
328   int found = 0;
329
330   int i;
331   for (i = 0; i < var->cnsts_number; i++) {
332     elem = &(var->cnsts[i]);
333     if (elem->constraint == cnst) {
334       found = 1;
335       break;
336     }
337   }
338
339   if (!found) {
340     XBT_DEBUG("cnst %p is not found in var %p", cnst, var);
341     return;
342   }
343
344   sys->modified = 1;
345
346   XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p",
347       elem->value, elem->constraint, elem->variable, var);
348
349   /* We are going to change the constraint object and the variable object.
350    * Propagate this change to other objects. Calling here before removing variable from not active elements (inactive elements are not visited)
351    */
352   lmm_update_modified_set(sys, cnst);
353   //Useful in case var was already removed from the constraint
354   lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up enabled_element_set of this constraint, and then each var in the enabled_element_set, and each var->cnsts[i].
355
356   if(xbt_swag_remove(elem, &(elem->constraint->enabled_element_set)))
357     lmm_decrease_concurrency(elem->constraint);
358
359   xbt_swag_remove(elem, &(elem->constraint->active_element_set));
360   elem->constraint = NULL;
361   elem->variable = NULL;
362   elem->value = 0;
363
364   var->cnsts_number -= 1;
365
366   //No variable in this constraint -> make it inactive
367   if (xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set)) == 0)
368     make_constraint_inactive(sys, cnst);
369   else {
370     //Check maxconcurrency to see if we can enable new variables
371     lmm_on_disabled_var(sys,elem->constraint);       
372   }
373
374   lmm_check_concurrency(sys);
375 }
376
377 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
378                 lmm_variable_t var, double value)
379 {
380   lmm_element_t elem = NULL;
381   double weight;
382   int i;
383   
384   sys->modified = 1;
385
386   if(var->weight>0 && lmm_concurrency_slack(cnst)==0){
387     weight=var->weight;
388     lmm_disable_var(sys,var);
389     for (i = 0; i < var->cnsts_number; i++)
390       lmm_on_disabled_var(sys,var->cnsts[i].constraint);
391     value=0;
392     var->staged_weight=weight;
393     xbt_assert(!var->weight);
394   }
395
396   xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints");
397
398   elem = &(var->cnsts[var->cnsts_number++]);
399
400   elem->value = value;
401   elem->constraint = cnst;
402   elem->variable = var;
403
404   
405   if (var->weight){
406     xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set));
407     lmm_increase_concurrency(elem->constraint);
408   }
409   else
410     xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set));
411
412   if(!sys->selective_update_active) {
413     make_constraint_active(sys, cnst);
414   } else if(elem->value>0 || var->weight >0) {
415     make_constraint_active(sys, cnst);
416     lmm_update_modified_set(sys, cnst);
417     //TODOLATER: Why do we need this second call?
418     if (var->cnsts_number > 1)
419       lmm_update_modified_set(sys, var->cnsts[0].constraint);
420   }
421
422   lmm_check_concurrency(sys);
423 }
424
425 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
426                     lmm_variable_t var, double value)
427 {
428   int i;
429   sys->modified = 1;
430
431   lmm_check_concurrency(sys);
432
433   for (i = 0; i < var->cnsts_number; i++)
434     if (var->cnsts[i].constraint == cnst)
435       break;
436
437   if (i < var->cnsts_number) {
438     if (cnst->sharing_policy)
439       var->cnsts[i].value += value;
440     else
441       var->cnsts[i].value = MAX(var->cnsts[i].value, value);
442     lmm_update_modified_set(sys, cnst);
443   } else
444     lmm_expand(sys, cnst, var, value);
445
446   lmm_check_concurrency(sys);
447 }
448
449 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/,
450                                                   lmm_variable_t var,
451                                                   int num)
452 {
453   if (num < var->cnsts_number)
454     return (var->cnsts[num].constraint);
455   else
456     return NULL;
457 }
458
459 double lmm_get_cnst_weight_from_var(lmm_system_t /*sys*/,
460                                                          lmm_variable_t var,
461                                                          int num)
462 {
463   if (num < var->cnsts_number)
464     return (var->cnsts[num].value);
465   else
466     return 0.0;
467 }
468
469 int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/,
470                                                lmm_variable_t var)
471 {
472   return (var->cnsts_number);
473 }
474
475 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/,
476                                      lmm_constraint_t cnst,
477                                      lmm_element_t * elem)
478 {
479   
480   if (!(*elem)) {
481     //That is the first call, pick the first element among enabled_element_set (or disabled_element_set if enabled_element_set is empty)
482     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set));
483     if (!(*elem))
484       *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
485   }  else {
486     //elem is not null, so we carry on
487     if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){
488       //Look at enabled_element_set, and jump to disabled_element_set when finished
489       *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset);
490       if (!(*elem))
491   *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
492     } else {
493       *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset);      
494     }
495   }
496   if (*elem)
497     return (*elem)->variable;
498   else
499     return NULL;
500 }
501
502 //if we modify the swag between calls, normal version may loop forever
503 //this safe version ensures that we browse the swag elements only once
504 lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
505                                      lmm_constraint_t cnst,
506                                      lmm_element_t * elem,
507                                      lmm_element_t * nextelem,
508                                      int * numelem)
509 {
510   if (!(*elem)){
511     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set));
512     *numelem = xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set))-1;
513     if (!(*elem))
514       *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
515   }else{
516     *elem = *nextelem;
517     if(*numelem>0){
518      (*numelem) --;
519     }else
520       return NULL;
521   }
522   if (*elem){
523     //elem is not null, so we carry on
524     if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){
525       //Look at enabled_element_set, and jump to disabled_element_set when finished
526       *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset);
527       if (!(*nextelem))
528   *nextelem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
529     } else {
530       *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset);      
531     }
532     return (*elem)->variable;
533   }else
534     return NULL;
535 }
536
537 void *lmm_constraint_id(lmm_constraint_t cnst)
538 {
539   return cnst->id;
540 }
541
542 void *lmm_variable_id(lmm_variable_t var)
543 {
544   return var->id;
545 }
546
547 static XBT_INLINE void saturated_constraint_set_update(double usage,
548                                                       int cnst_light_num,
549                                                       dyn_light_t saturated_constraint_set,
550                                                       double *min_usage)
551 {
552   xbt_assert(usage > 0,"Impossible");
553
554   if (*min_usage < 0 || *min_usage > usage) {
555     *min_usage = usage;
556     XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *min_usage, usage);
557     saturated_constraint_set->data[0] = cnst_light_num;
558     saturated_constraint_set->pos = 1;
559   } else if (*min_usage == usage) {
560     if(saturated_constraint_set->pos == saturated_constraint_set->size) { // realloc the size
561       saturated_constraint_set->size *= 2;
562       saturated_constraint_set->data = (int*) xbt_realloc(saturated_constraint_set->data, (saturated_constraint_set->size) * sizeof(int));
563     }
564     saturated_constraint_set->data[saturated_constraint_set->pos] = cnst_light_num;
565     saturated_constraint_set->pos++;
566   }
567 }
568
569 static XBT_INLINE void saturated_variable_set_update(
570     s_lmm_constraint_light_t *cnst_light_tab,
571     dyn_light_t saturated_constraint_set,
572     lmm_system_t sys)
573 {
574   /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate (cnst_light_tab)*/ 
575   lmm_constraint_light_t cnst = NULL;
576   void *_elem;
577   lmm_element_t elem = NULL;
578   xbt_swag_t elem_list = NULL;
579   int i;
580   for(i = 0; i< saturated_constraint_set->pos; i++){
581     cnst = &cnst_light_tab[saturated_constraint_set->data[i]];
582     elem_list = &(cnst->cnst->active_element_set);
583     xbt_swag_foreach(_elem, elem_list) {
584       elem = (lmm_element_t)_elem;
585       //Visiting active_element_set, so, by construction, should never get a zero weight, correct?
586       xbt_assert(elem->variable->weight > 0);
587       if ((elem->value > 0))
588         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
589     }
590   }
591 }
592
593 void lmm_print(lmm_system_t sys)
594 {
595   void *_cnst, *_elem, *_var;
596   lmm_constraint_t cnst = NULL;
597   lmm_element_t elem = NULL;
598   lmm_variable_t var = NULL;
599   xbt_swag_t cnst_list = NULL;
600   xbt_swag_t var_list = NULL;
601   xbt_swag_t elem_list = NULL;
602   char print_buf[1024];
603   char *trace_buf = (char*) xbt_malloc0(sizeof(char));
604   double sum = 0.0;
605
606   /* Printing Objective */
607   var_list = &(sys->variable_set);
608   sprintf(print_buf, "MAX-MIN ( ");
609   trace_buf = (char*)
610       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
611   strcat(trace_buf, print_buf);
612   xbt_swag_foreach(_var, var_list) {
613   var = (lmm_variable_t)_var;
614     sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight);
615     trace_buf = (char*)
616         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
617     strcat(trace_buf, print_buf);
618   }
619   sprintf(print_buf, ")");
620   trace_buf = (char*)
621       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
622   strcat(trace_buf, print_buf);
623   XBT_DEBUG("%20s", trace_buf);
624   trace_buf[0] = '\000';
625
626   XBT_DEBUG("Constraints");
627   /* Printing Constraints */
628   cnst_list = &(sys->active_constraint_set);
629   xbt_swag_foreach(_cnst, cnst_list) {
630   cnst = (lmm_constraint_t)_cnst;
631     sum = 0.0;
632     //Show  the enabled variables
633     elem_list = &(cnst->enabled_element_set);
634     sprintf(print_buf, "\t");
635     trace_buf = (char*)
636         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
637     strcat(trace_buf, print_buf);
638     sprintf(print_buf, "%s(",(cnst->sharing_policy)?"":"max");
639     trace_buf = (char*)
640       xbt_realloc(trace_buf,
641       strlen(trace_buf) + strlen(print_buf) + 1);
642     strcat(trace_buf, print_buf);      
643     xbt_swag_foreach(_elem, elem_list) {
644       elem = (lmm_element_t)_elem;
645       sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value,
646               elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":",");
647       trace_buf = (char*)
648           xbt_realloc(trace_buf,
649                       strlen(trace_buf) + strlen(print_buf) + 1);
650       strcat(trace_buf, print_buf);
651       if(cnst->sharing_policy)
652         sum += elem->value * elem->variable->value;
653       else 
654         sum = MAX(sum,elem->value * elem->variable->value);
655     }
656     //TODO: Adding disabled elements only for test compatibility, but do we really want them to be printed?
657     elem_list = &(cnst->disabled_element_set);
658     xbt_swag_foreach(_elem, elem_list) {
659       elem = (lmm_element_t)_elem;
660       sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value,
661               elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":",");
662       trace_buf = (char*)
663           xbt_realloc(trace_buf,
664                       strlen(trace_buf) + strlen(print_buf) + 1);
665       strcat(trace_buf, print_buf);
666       if(cnst->sharing_policy)
667         sum += elem->value * elem->variable->value;
668       else 
669         sum = MAX(sum,elem->value * elem->variable->value);
670     }
671     
672     sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int);
673     trace_buf = (char*)
674         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
675     strcat(trace_buf, print_buf);
676
677     if (!cnst->sharing_policy) {
678       sprintf(print_buf, " [MAX-Constraint]");
679       trace_buf = (char*)
680           xbt_realloc(trace_buf,
681                       strlen(trace_buf) + strlen(print_buf) + 1);
682       strcat(trace_buf, print_buf);
683     }
684     XBT_DEBUG("%s", trace_buf);
685     trace_buf[0] = '\000';
686     xbt_assert(!double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision),
687                 "Incorrect value (%f is not smaller than %f): %g",
688                 sum, cnst->bound, sum - cnst->bound);
689   }
690
691   XBT_DEBUG("Variables");
692   /* Printing Result */
693   xbt_swag_foreach(_var, var_list) {
694   var = (lmm_variable_t)_var;
695     if (var->bound > 0) {
696       XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value,
697              var->bound);
698       xbt_assert(!double_positive(var->value - var->bound, var->bound*sg_maxmin_precision),
699                   "Incorrect value (%f is not smaller than %f",
700                   var->value, var->bound);
701     } else {
702       XBT_DEBUG("'%d'(%f) : %f", var->id_int, var->weight, var->value);
703     }
704   }
705
706   free(trace_buf);
707 }
708
709 void lmm_solve(lmm_system_t sys)
710 {
711   void *_var, *_cnst, *_cnst_next, *_elem;
712   lmm_variable_t var = NULL;
713   lmm_constraint_t cnst = NULL;
714   lmm_element_t elem = NULL;
715   xbt_swag_t cnst_list = NULL;
716   xbt_swag_t var_list = NULL;
717   xbt_swag_t elem_list = NULL;
718   double min_usage = -1;
719   double min_bound = -1;
720
721   if (!(sys->modified))
722     return;
723
724   XBT_IN("(sys=%p)", sys);
725
726   /*
727    * Compute Usage and store the variables that reach the maximum. If selective_update_active is true, only constraints that changed are considered. Otherwise all constraints with active actions are considered.
728    */
729   cnst_list =
730       sys->
731       selective_update_active ? &(sys->modified_constraint_set) :
732       &(sys->active_constraint_set);
733
734   XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list));
735   /* Init: Only modified code portions: reset the value of active variables */
736   xbt_swag_foreach(_cnst, cnst_list) {
737   cnst = (lmm_constraint_t)_cnst;
738     elem_list = &(cnst->enabled_element_set);
739     //XBT_DEBUG("Variable set : %d", xbt_swag_size(elem_list));
740     xbt_swag_foreach(_elem, elem_list) {
741       var = ((lmm_element_t)_elem)->variable;
742       xbt_assert(var->weight > 0.0);
743       var->value = 0.0;
744     }
745   }
746
747   s_lmm_constraint_light_t *cnst_light_tab = (s_lmm_constraint_light_t *)xbt_malloc0(xbt_swag_size(cnst_list)*sizeof(s_lmm_constraint_light_t));
748   int cnst_light_num = 0;
749   dyn_light_t saturated_constraint_set = xbt_new0(s_dyn_light_t,1);
750   saturated_constraint_set->size = 5;
751   saturated_constraint_set->data = xbt_new0(int, saturated_constraint_set->size);
752
753   xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) {
754   cnst = (lmm_constraint_t)_cnst;
755     /* INIT: Collect constraints that actually need to be saturated (i.e remaining  and usage are strictly positive) into cnst_light_tab. */
756     cnst->remaining = cnst->bound;
757     if (!double_positive(cnst->remaining, cnst->bound*sg_maxmin_precision))
758       continue;
759     cnst->usage = 0;
760     elem_list = &(cnst->enabled_element_set);
761     xbt_swag_foreach(_elem, elem_list) {
762       elem = (lmm_element_t)_elem;
763       xbt_assert(elem->variable->weight > 0);
764       if ((elem->value > 0)) {
765         if (cnst->sharing_policy)
766           cnst->usage += elem->value / elem->variable->weight;
767         else if (cnst->usage < elem->value / elem->variable->weight)
768           cnst->usage = elem->value / elem->variable->weight;
769
770         make_elem_active(elem);
771         simgrid::surf::Action *action = static_cast<simgrid::surf::Action*>(elem->variable->id);
772         if (sys->keep_track && !action->is_linked())
773           sys->keep_track->push_back(*action);
774       }
775     }
776     XBT_DEBUG("Constraint '%d' usage: %f remaining: %f ", cnst->id_int, cnst->usage, cnst->remaining);
777     /* Saturated constraints update */
778
779     if(cnst->usage > 0) {
780       cnst_light_tab[cnst_light_num].cnst = cnst;
781       cnst->cnst_light = &(cnst_light_tab[cnst_light_num]);
782       cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage;
783       saturated_constraint_set_update(cnst_light_tab[cnst_light_num].remaining_over_usage,
784         cnst_light_num, saturated_constraint_set, &min_usage);
785       xbt_assert(cnst->active_element_set.count>0, "There is no sense adding a constraint that has no active element!" );
786       cnst_light_num++;
787     }
788   }
789
790   saturated_variable_set_update(  cnst_light_tab,
791                                   saturated_constraint_set,
792                                   sys);
793
794   /* Saturated variables update */
795
796   do {
797     /* Fix the variables that have to be */
798     var_list = &(sys->saturated_variable_set);
799
800     xbt_swag_foreach(_var, var_list) {
801       var = (lmm_variable_t)_var;
802       if (var->weight <= 0.0)
803         DIE_IMPOSSIBLE;
804       /* First check if some of these variables could reach their upper
805          bound and update min_bound accordingly. */
806       XBT_DEBUG
807           ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f",
808            var->id_int, var->bound, var->weight, min_usage,
809            var->bound * var->weight);
810       if ((var->bound > 0) && (var->bound * var->weight < min_usage)) {
811         if (min_bound < 0)
812           min_bound = var->bound*var->weight;
813         else
814           min_bound = MIN(min_bound, (var->bound*var->weight));
815         XBT_DEBUG("Updated min_bound=%f", min_bound);
816       }
817     }
818
819
820     while ((var = (lmm_variable_t)xbt_swag_getFirst(var_list))) {
821       int i;
822
823       if (min_bound < 0) {
824   //If no variable could reach its bound, deal iteratively the constraints usage ( at worst one constraint is saturated at each cycle) 
825         var->value = min_usage / var->weight;
826         XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
827       } else {
828   //If there exist a variable that can reach its bound, only update it (and other with the same bound) for now.
829       if (double_equals(min_bound, var->bound*var->weight, sg_maxmin_precision)){
830           var->value = var->bound;
831           XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
832         }
833         else {
834     // Variables which bound is different are not considered for this cycle, but they will be afterwards.  
835           XBT_DEBUG("Do not consider %p (%d) \n", var, var->id_int);
836           xbt_swag_remove(var, var_list);
837           continue;
838         }
839       }
840       XBT_DEBUG("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ",
841              min_usage, var->id_int, var->weight, var->id_int, var->value);
842
843
844       /* Update the usage of contraints where this variable is involved */
845       for (i = 0; i < var->cnsts_number; i++) {
846         elem = &var->cnsts[i];
847         cnst = elem->constraint;
848         if (cnst->sharing_policy) {
849     //Remember: shared constraints require that sum(elem->value * var->value) < cnst->bound
850           double_update(&(cnst->remaining),  elem->value * var->value, cnst->bound*sg_maxmin_precision);
851           double_update(&(cnst->usage), elem->value / var->weight, sg_maxmin_precision);
852     //If the constraint is saturated, remove it from the set of active constraints (light_tab)
853           if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) {
854             if (cnst->cnst_light) {
855               int index = (cnst->cnst_light-cnst_light_tab);
856               XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p usage: %f remaining: %f bound: %f  ",
857       index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound);
858               cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
859               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
860               cnst_light_num--;
861               cnst->cnst_light = NULL;
862             }
863           } else {
864             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
865           }
866           make_elem_inactive(elem);
867         } else {
868     //Remember: non-shared constraints only require that max(elem->value * var->value) < cnst->bound
869           cnst->usage = 0.0;
870           make_elem_inactive(elem);
871           elem_list = &(cnst->enabled_element_set);
872           xbt_swag_foreach(_elem, elem_list) {
873       elem = (lmm_element_t)_elem;
874       xbt_assert(elem->variable->weight > 0);
875       if (elem->variable->value > 0) continue;
876       if (elem->value > 0)
877         cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight);
878           }
879     //If the constraint is saturated, remove it from the set of active constraints (light_tab)
880           if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) {
881             if(cnst->cnst_light) {
882               int index = (cnst->cnst_light-cnst_light_tab);
883               XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p usage: %f remaining: %f bound: %f  ",
884       index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound);
885               cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
886               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
887               cnst_light_num--;
888               cnst->cnst_light = NULL;
889             }
890           } else {
891             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
892             xbt_assert(cnst->active_element_set.count>0, "Should not keep a maximum constraint that has no active element! You want to check the maxmin precision and possible rounding effects." );
893           }
894         }
895       }
896       xbt_swag_remove(var, var_list);
897     }
898
899     /* Find out which variables reach the maximum */
900     min_usage = -1;
901     min_bound = -1;
902     saturated_constraint_set->pos = 0;
903     int pos;
904     for(pos=0; pos<cnst_light_num; pos++){
905       xbt_assert(cnst_light_tab[pos].cnst->active_element_set.count>0, "Cannot saturate more a constraint that has no active element! You may want to change the maxmin precision (--cfg=maxmin/precision:<new_value>) because of possible rounding effects.\n\tFor the record, the usage of this constraint is %g while the maxmin precision to which it is compared is %g.\n\tThe usage of the previous constraint is %g.", cnst_light_tab[pos].cnst->usage, sg_maxmin_precision, cnst_light_tab[pos-1].cnst->usage);
906       saturated_constraint_set_update(
907           cnst_light_tab[pos].remaining_over_usage,
908           pos,
909           saturated_constraint_set,
910           &min_usage);
911   }
912
913     saturated_variable_set_update(  cnst_light_tab,
914                                     saturated_constraint_set,
915                                     sys);
916
917   } while (cnst_light_num > 0);
918
919   sys->modified = 0;
920   if (sys->selective_update_active)
921     lmm_remove_all_modified_set(sys);
922
923   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
924     lmm_print(sys);
925   }
926
927   xbt_free(saturated_constraint_set->data);
928   xbt_free(saturated_constraint_set);
929   xbt_free(cnst_light_tab);
930   XBT_OUT();
931 }
932
933
934 /** \brief Attribute the value bound to var->bound.
935  * 
936  *  \param sys the lmm_system_t
937  *  \param var the lmm_variable_t
938  *  \param bound the new bound to associate with var
939  * 
940  *  Makes var->bound equal to bound. Whenever this function is called 
941  *  a change is  signed in the system. To
942  *  avoid false system changing detection it is a good idea to test 
943  *  (bound != 0) before calling it.
944  *
945 */
946 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
947     double bound)
948 {
949   sys->modified = 1;
950   var->bound = bound;
951
952   if (var->cnsts_number)
953     lmm_update_modified_set(sys, var->cnsts[0].constraint);
954 }
955
956
957
958 int lmm_concurrency_slack(lmm_constraint_t cnstr){
959
960   xbt_assert(xbt_swag_size(&(cnstr->enabled_element_set))==cnstr->concurrency_current,"concurrency_current is not up to date!");
961
962   //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
963   if(cnstr->concurrency_limit<0)
964     return 666;
965
966   return  cnstr->concurrency_limit - cnstr->concurrency_current;  
967 }
968
969 /** \brief Measure the minimum concurrency slack across all constraints where var is involved
970  *
971  * \param The variable to check for
972  *
973  */
974 int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var){
975   int i;
976   //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
977   int slack,minslack=666;
978   for (i = 0; i < var->cnsts_number; i++) {
979     slack=lmm_concurrency_slack(var->cnsts[i].constraint);
980     
981     //This is only an optimization, to avoid looking at more constraints when slack is already zero
982     //Disable it when debugging to let lmm_concurrency_slack catch nasty things
983     if(!slack   && !XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug))
984       return 0;
985
986     if(minslack>slack)
987       minslack=slack;
988   }
989
990   return minslack;
991 }
992
993 /* /Check if a variable can be enabled
994  *
995  * Make sure to set staged_weight before, if your intent is only to check concurrency 
996  */
997 int lmm_can_enable_var(lmm_variable_t var){
998   return var->staged_weight>0 && lmm_cnstrs_min_concurrency_slack(var)>=var->concurrency_share;
999 }
1000
1001
1002 //Small remark: In this implementation of lmm_enable_var and lmm_disable_var, we will meet multiple times with var when running lmm_update_modified_set.
1003 //A priori not a big performance issue, but we might do better by calling lmm_update_modified_set within the for loops (after doing the first for enabling==1, and before doing the last for disabling==1)
1004
1005 void lmm_enable_var(lmm_system_t sys, lmm_variable_t var){
1006
1007   int i;
1008   lmm_element_t elem;
1009   
1010   xbt_assert(lmm_can_enable_var(var));
1011
1012   var->weight = var->staged_weight;
1013   var->staged_weight = 0;
1014
1015   //Enabling the variable, move to var to list head. Subtility is: here, we need to call lmm_update_modified_set AFTER moving at least one element of var.
1016
1017   xbt_swag_remove(var, &(sys->variable_set));
1018   xbt_swag_insert_at_head(var, &(sys->variable_set));
1019   for (i = 0; i < var->cnsts_number; i++) {
1020     elem = &var->cnsts[i];
1021     xbt_swag_remove(elem, &(elem->constraint->disabled_element_set));
1022     xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set));
1023     lmm_increase_concurrency(elem->constraint);
1024   }
1025   if (var->cnsts_number)
1026     lmm_update_modified_set(sys, var->cnsts[0].constraint);
1027
1028   lmm_check_concurrency(sys);
1029 }
1030
1031 void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){
1032   int i;
1033   lmm_element_t elem;
1034
1035   xbt_assert(!var->staged_weight,"Staged weight should have been cleared");
1036   //Disabling the variable, move to var to list tail. Subtility is: here, we need to call lmm_update_modified_set BEFORE moving the last element of var.
1037   xbt_swag_remove(var, &(sys->variable_set));
1038   xbt_swag_insert_at_tail(var, &(sys->variable_set));
1039   if (var->cnsts_number)
1040     lmm_update_modified_set(sys, var->cnsts[0].constraint);
1041   for (i = 0; i < var->cnsts_number; i++) {
1042     elem = &var->cnsts[i];
1043     xbt_swag_remove(elem, &(elem->constraint->enabled_element_set));
1044     xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set));
1045
1046     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
1047
1048     lmm_decrease_concurrency(elem->constraint);
1049   }
1050
1051   var->weight=0.0;
1052   var->staged_weight=0.0;
1053   var->value = 0.0;
1054   lmm_check_concurrency(sys);
1055 }
1056  
1057 /* /brief Find variables that can be enabled and enable them.
1058  * 
1059  * Assuming that the variable has already been removed from non-zero weights
1060  * Can we find a staged variable to add?
1061  * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency
1062  * And then add it to enabled variables
1063  */
1064 void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){
1065
1066   lmm_element_t elem;
1067   if(cnstr->concurrency_limit<0)
1068     return;
1069   
1070   int concurrency=cnstr->concurrency_current;
1071   xbt_swag_foreach(elem, &(cnstr->disabled_element_set)) {
1072
1073     if (elem->variable->staged_weight>0 )
1074       {
1075   //Found a staged variable
1076   //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called?
1077   if(lmm_can_enable_var(elem->variable)){
1078     lmm_enable_var(sys,elem->variable);
1079     concurrency++;
1080   }        
1081       }
1082
1083     xbt_assert(concurrency<=cnstr->concurrency_limit,"Concurrency overflow!");
1084     if(concurrency==cnstr->concurrency_limit)
1085       break;
1086   }
1087
1088   lmm_check_concurrency(sys);
1089
1090 }
1091
1092 /* \brief update the weight of a variable, and enable/disable it.
1093  * @return Returns whether a change was made
1094  */
1095 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
1096              double weight)
1097 {
1098   int minslack;
1099   
1100   xbt_assert(weight>=0,"Variable weight should not be negative!");
1101   
1102   if (weight == var->weight)
1103     return;
1104
1105   int enabling_var=  (weight>0 && var->weight<=0);
1106   int disabling_var= (weight<=0 && var->weight>0);
1107  
1108   XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight);
1109
1110   sys->modified = 1;
1111   
1112   //Are we enabling this variable?
1113   if (enabling_var){
1114     var->staged_weight = weight;
1115     minslack=lmm_cnstrs_min_concurrency_slack(var);
1116     if(minslack==0){      
1117       XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f", minslack, weight);
1118       return;
1119     }
1120     XBT_DEBUG("Enabling var with min concurrency slack %i", minslack);
1121     lmm_enable_var(sys,var);   
1122   } else if (disabling_var){
1123     //Are we disabling this variable?
1124     lmm_disable_var(sys,var);       
1125   } else {
1126     var->weight=weight;
1127   }
1128
1129   lmm_check_concurrency(sys);
1130   
1131   XBT_OUT();
1132   return;
1133 }
1134
1135 double lmm_get_variable_weight(lmm_variable_t var)
1136 {
1137   return var->weight;
1138 }
1139
1140 void lmm_update_constraint_bound(lmm_system_t sys,
1141                                             lmm_constraint_t cnst,
1142                                             double bound)
1143 {
1144   sys->modified = 1;
1145   lmm_update_modified_set(sys, cnst);
1146   cnst->bound = bound;
1147 }
1148
1149 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
1150 {
1151   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
1152 }
1153
1154 XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t
1155                                                             sys)
1156 {
1157   return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set));
1158 }
1159
1160 XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t
1161                                                            sys,
1162                                                            lmm_constraint_t
1163                                                            cnst)
1164 {
1165   return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset);
1166 }
1167
1168 #ifdef HAVE_LATENCY_BOUND_TRACKING
1169 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var)
1170 {
1171   return (double_equals(var->bound, var->value, var->bound*sg_maxmin_precision));
1172 }
1173 #endif
1174
1175
1176 /** \brief Update the constraint set propagating recursively to
1177  *  other constraints so the system should not be entirely computed.
1178  *
1179  *  \param sys the lmm_system_t
1180  *  \param cnst the lmm_constraint_t affected by the change
1181  *
1182  *  A recursive algorithm to optimize the system recalculation selecting only
1183  *  constraints that have changed. Each constraint change is propagated
1184  *  to the list of constraints for each variable.
1185  */
1186 static void lmm_update_modified_set_rec(lmm_system_t sys,
1187                                         lmm_constraint_t cnst)
1188 {
1189   void* _elem;
1190
1191   //TODOLATER: Why lmm_modified_set has been changed in git version 2392B5157...? Looks equivalent logically and less obvious..
1192   
1193   xbt_swag_foreach(_elem, &cnst->enabled_element_set) {
1194     lmm_variable_t var = ((lmm_element_t)_elem)->variable;
1195     s_lmm_element_t *cnsts = var->cnsts;
1196     int i;
1197     for (i = 0; var->visited != sys->visited_counter
1198              && i < var->cnsts_number ; i++) {
1199       if (cnsts[i].constraint != cnst
1200           && !xbt_swag_belongs(cnsts[i].constraint,
1201                                &sys->modified_constraint_set)) {
1202         xbt_swag_insert(cnsts[i].constraint, &sys->modified_constraint_set);
1203         lmm_update_modified_set_rec(sys, cnsts[i].constraint);
1204       }
1205     }
1206     //var will be ignored in later visits as long as sys->visited_counter does not move 
1207     var->visited = sys->visited_counter;
1208   }
1209 }
1210
1211 static void lmm_update_modified_set(lmm_system_t sys,
1212                                     lmm_constraint_t cnst)
1213 {
1214   /* nothing to do if selective update isn't active */
1215   if (sys->selective_update_active
1216       && !xbt_swag_belongs(cnst, &sys->modified_constraint_set)) {
1217     xbt_swag_insert(cnst, &sys->modified_constraint_set);
1218     lmm_update_modified_set_rec(sys, cnst);
1219   }
1220 }
1221
1222 /** \brief Remove all constraints of the modified_constraint_set.
1223  *
1224  *  \param sys the lmm_system_t
1225  *
1226  */
1227 static void lmm_remove_all_modified_set(lmm_system_t sys)
1228 {
1229
1230   //We cleverly un-flag all variables just by incrementing sys->visited_counter
1231   //In effect, the var->visited value will no more be equal to sys->visited counter
1232   //To be clean, when visited counter has wrapped around, we force these var->visited values so that variables that were in the modified a long (long long) time ago are not wrongly skipped here, which would lead to very nasty bugs (i.e. not readibily reproducible, and requiring a lot of run time before happening).  
1233   if (++sys->visited_counter == 1) {
1234     /* the counter wrapped around, reset each variable->visited */
1235   void *_var;
1236     xbt_swag_foreach(_var, &sys->variable_set)
1237       ((lmm_variable_t)_var)->visited = 0;
1238   }
1239   xbt_swag_reset(&sys->modified_constraint_set);
1240 }
1241
1242 /**
1243  *  Returns total resource load
1244  *
1245  * \param cnst the lmm_constraint_t associated to the resource
1246  *
1247  *
1248  * This is dead code, but we may use it later for debug/trace.
1249  */
1250 double lmm_constraint_get_usage(lmm_constraint_t cnst) {
1251    double usage = 0.0;
1252    xbt_swag_t elem_list = &(cnst->enabled_element_set);
1253    void *_elem;
1254    lmm_element_t elem = NULL;
1255
1256    xbt_swag_foreach(_elem, elem_list) {
1257    elem = (lmm_element_t)_elem;
1258      if ((elem->value > 0)) {
1259        if (cnst->sharing_policy)
1260          usage += elem->value * elem->variable->value;
1261        else if (usage < elem->value * elem->variable->value)
1262          usage = elem->value * elem->variable->value;
1263      }
1264    }
1265   return usage;
1266 }
1267
1268 void lmm_check_concurrency(lmm_system_t sys){
1269   void* _cnst;
1270   void* _elem;
1271   lmm_element_t elem;
1272   lmm_constraint_t cnst;
1273   int concurrency;
1274
1275   //These checks are very expensive, so do them only if we want to debug SURF LMM
1276   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
1277   
1278     xbt_swag_foreach(_cnst, &(sys->constraint_set)) {
1279       cnst = (lmm_constraint_t) _cnst;
1280       concurrency=0;
1281      
1282       xbt_swag_foreach(_elem, &(cnst->enabled_element_set)) {
1283   elem = (lmm_element_t)_elem;
1284   xbt_assert(elem->variable->weight > 0);
1285     concurrency++;
1286       }
1287
1288       xbt_swag_foreach(_elem, &(cnst->disabled_element_set)) {
1289   elem = (lmm_element_t)_elem;
1290   //We should have staged variables only if conccurency is reached in some constraint
1291   xbt_assert(cnst->concurrency_limit<0 || elem->variable->staged_weight==0 || lmm_cnstrs_min_concurrency_slack(elem->variable) < elem->variable->concurrency_share,"should not have staged variable!");
1292       }
1293       
1294       xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_limit >= concurrency,"concurrency check failed!");
1295       xbt_assert(cnst->concurrency_current == concurrency, "concurrency_current is out-of-date!");
1296       xbt_assert(cnst->concurrency_current == xbt_swag_size(&(cnst->enabled_element_set)), "concurrency_current is out-of-date (2) !");
1297
1298     }
1299
1300   }
1301 }