Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
add a SIMIX_sem_get_capacity() function
[simgrid.git] / src / simix / smx_synchro.c
1 /*      $Id$     */
2
3 /* Copyright (c) 2007 Arnaud Legrand, Bruno Donnassolo.
4    All rights reserved.                                          */
5
6 /* This program is free software; you can redistribute it and/or modify it
7  * under the terms of the license (GNU LGPL) which comes with this package. */
8
9 #include "private.h"
10 #include "xbt/log.h"
11
12
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(simix_synchro, simix,
14                                 "Logging specific to SIMIX (synchronization)");
15
16
17 /****************************** Synchronization *******************************/
18
19 /*********************************** Mutex ************************************/
20
21 /**
22  * \brief Initialize a mutex.
23  *
24  * Allocs and creates the data for the mutex. It have to be called before the utilisation of the mutex.
25  * \return A mutex
26  */
27 smx_mutex_t SIMIX_mutex_init()
28 {
29   smx_mutex_t m = xbt_new0(s_smx_mutex_t, 1);
30   s_smx_process_t p;            /* useful to initialize sleeping swag */
31   /* structures initialization */
32   m->refcount = 0;
33   m->sleeping = xbt_swag_new(xbt_swag_offset(p, synchro_hookup));
34   return m;
35 }
36
37 /**
38  * \brief Locks a mutex.
39  *
40  * Tries to lock a mutex, if the mutex isn't used yet, the process can continue its execution, else it'll be blocked here. You have to call #SIMIX_mutex_unlock to free the mutex.
41  * \param mutex The mutex
42  */
43 void SIMIX_mutex_lock(smx_mutex_t mutex)
44 {
45   smx_process_t self = SIMIX_process_self();
46   xbt_assert0((mutex != NULL), "Invalid parameters");
47
48
49   if (mutex->refcount) {
50     /* somebody using the mutex, block */
51     xbt_swag_insert(self, mutex->sleeping);
52     self->mutex = mutex;
53     /* wait for some process make the unlock and wake up me from mutex->sleeping */
54     SIMIX_process_yield();
55     self->mutex = NULL;
56
57     /* verify if the process was suspended */
58     while (self->suspended) {
59       SIMIX_process_yield();
60     }
61
62     mutex->refcount = 1;
63   } else {
64     /* mutex free */
65     mutex->refcount = 1;
66   }
67   return;
68 }
69
70 /**
71  * \brief Tries to lock a mutex.
72  *
73  * Tries to lock a mutex, return 1 if the mutex is free, 0 else. This function does not block the process if the mutex is used.
74  * \param mutex The mutex
75  * \return 1 - mutex free, 0 - mutex used
76  */
77 XBT_INLINE int SIMIX_mutex_trylock(smx_mutex_t mutex)
78 {
79   xbt_assert0((mutex != NULL), "Invalid parameters");
80
81   if (mutex->refcount)
82     return 0;
83   else {
84     mutex->refcount = 1;
85     return 1;
86   }
87 }
88
89 /**
90  * \brief Unlocks a mutex.
91  *
92  * Unlocks the mutex and wakes up a process blocked on it. If there are no process sleeping, only sets the mutex as free.
93  * \param mutex The mutex
94  */
95 void SIMIX_mutex_unlock(smx_mutex_t mutex)
96 {
97   smx_process_t p;              /*process to wake up */
98
99   xbt_assert0((mutex != NULL), "Invalid parameters");
100
101   if (xbt_swag_size(mutex->sleeping) > 0) {
102     p = xbt_swag_extract(mutex->sleeping);
103     mutex->refcount = 0;
104     xbt_swag_insert(p, simix_global->process_to_run);
105   } else {
106     /* nobody to wake up */
107     mutex->refcount = 0;
108   }
109   return;
110 }
111
112 /**
113  * \brief Destroys a mutex.
114  *
115  * Destroys and frees the mutex's memory. 
116  * \param mutex A mutex
117  */
118 XBT_INLINE void SIMIX_mutex_destroy(smx_mutex_t mutex)
119 {
120   if (mutex == NULL)
121     return;
122   else {
123     xbt_swag_free(mutex->sleeping);
124     xbt_free(mutex);
125     return;
126   }
127 }
128
129 /******************************** Conditional *********************************/
130
131 /**
132  * \brief Initialize a condition.
133  *
134  * Allocates and creates the data for the condition.
135  * It have to be called before the use of the condition.
136  * \return A condition
137  */
138 smx_cond_t SIMIX_cond_init()
139 {
140   smx_cond_t cond = xbt_new0(s_smx_cond_t, 1);
141   s_smx_process_t p;
142
143   cond->sleeping = xbt_swag_new(xbt_swag_offset(p, synchro_hookup));
144   cond->actions = xbt_fifo_new();
145   cond->mutex = NULL;
146   return cond;
147 }
148
149 /**
150  * \brief Signalizes a condition.
151  *
152  * Signalizes a condition and wakes up a sleeping process. If there are no process sleeping, no action is done.
153  * \param cond A condition
154  */
155 void SIMIX_cond_signal(smx_cond_t cond)
156 {
157   smx_process_t proc = NULL;
158   DEBUG1("Signal condition %p", cond);
159   xbt_assert0((cond != NULL), "Invalid parameters");
160
161
162   if (xbt_swag_size(cond->sleeping) >= 1) {
163     proc = xbt_swag_extract(cond->sleeping);
164     xbt_swag_insert(proc, simix_global->process_to_run);
165   }
166
167   return;
168 }
169
170 /**
171  * \brief Waits on a condition.
172  *
173  * Blocks a process until the signal is called. This functions frees the mutex associated and locks it after its execution.
174  * \param cond A condition
175  * \param mutex A mutex
176  */
177 void SIMIX_cond_wait(smx_cond_t cond, smx_mutex_t mutex)
178 {
179   smx_action_t act_sleep;
180
181   DEBUG1("Wait condition %p", cond);
182
183   /* If there is a mutex unlock it */
184   if(mutex != NULL){
185     cond->mutex = mutex;
186     SIMIX_mutex_unlock(mutex);
187   }
188   
189   /* Always create an action null in case there is a host failure */
190   act_sleep = SIMIX_action_sleep(SIMIX_host_self(), -1);
191   SIMIX_action_set_name(act_sleep,bprintf("Wait condition %p", cond));
192   SIMIX_process_self()->waiting_action = act_sleep;
193   SIMIX_register_action_to_condition(act_sleep, cond);
194   __SIMIX_cond_wait(cond);
195   SIMIX_process_self()->waiting_action = NULL;
196   SIMIX_unregister_action_to_condition(act_sleep, cond);
197   SIMIX_action_destroy(act_sleep);
198
199   /* get the mutex again if necessary */
200   if(mutex != NULL)
201     SIMIX_mutex_lock(cond->mutex);
202
203   return;
204 }
205
206 XBT_INLINE xbt_fifo_t SIMIX_cond_get_actions(smx_cond_t cond)
207 {
208   xbt_assert0((cond != NULL), "Invalid parameters");
209   return cond->actions;
210 }
211
212 void __SIMIX_cond_wait(smx_cond_t cond)
213 {
214   smx_process_t self = SIMIX_process_self();
215   xbt_assert0((cond != NULL), "Invalid parameters");
216
217   /* process status */
218
219   self->cond = cond;
220   xbt_swag_insert(self, cond->sleeping);
221   SIMIX_process_yield();
222   self->cond = NULL;
223   while (self->suspended) {
224     SIMIX_process_yield();
225   }
226   return;
227 }
228
229 /**
230  * \brief Waits on a condition with timeout.
231  *
232  * Same behavior of #SIMIX_cond_wait, but waits a maximum time and throws an timeout_error if it happens.
233  * \param cond A condition
234  * \param mutex A mutex
235  * \param max_duration Timeout time
236  */
237 void SIMIX_cond_wait_timeout(smx_cond_t cond, smx_mutex_t mutex,
238                              double max_duration)
239 {
240   smx_action_t act_sleep;
241
242   DEBUG1("Timed wait condition %p", cond);
243
244   /* If there is a mutex unlock it */
245   if(mutex != NULL){
246     cond->mutex = mutex;
247     SIMIX_mutex_unlock(mutex);
248   }
249
250   if (max_duration >= 0) {
251     act_sleep = SIMIX_action_sleep(SIMIX_host_self(), max_duration);
252     SIMIX_action_set_name(act_sleep,bprintf("Timed wait condition %p (max_duration:%f)", cond,max_duration));
253     SIMIX_register_action_to_condition(act_sleep, cond);
254     SIMIX_process_self()->waiting_action = act_sleep;
255     __SIMIX_cond_wait(cond);
256     SIMIX_process_self()->waiting_action = NULL;
257     SIMIX_unregister_action_to_condition(act_sleep, cond);
258     if (SIMIX_action_get_state(act_sleep) == SURF_ACTION_DONE) {
259       SIMIX_action_destroy(act_sleep);
260       THROW1(timeout_error, 0, "Condition timeout after %f",max_duration);
261     } else {
262       SIMIX_action_destroy(act_sleep);
263     }
264
265   } else
266     SIMIX_cond_wait(cond,NULL);
267
268   /* get the mutex again if necessary */
269   if(mutex != NULL)
270     SIMIX_mutex_lock(cond->mutex);
271 }
272
273 /**
274  * \brief Broadcasts a condition.
275  *
276  * Signalizes a condition and wakes up ALL sleping process. If there are no process sleeping, no action is done.
277  * \param cond A condition
278  */
279 void SIMIX_cond_broadcast(smx_cond_t cond)
280 {
281   smx_process_t proc = NULL;
282   smx_process_t proc_next = NULL;
283
284   xbt_assert0((cond != NULL), "Invalid parameters");
285
286   DEBUG1("Broadcast condition %p", cond);
287   xbt_swag_foreach_safe(proc, proc_next, cond->sleeping) {
288     xbt_swag_remove(proc, cond->sleeping);
289     xbt_swag_insert(proc, simix_global->process_to_run);
290   }
291 }
292
293 /**
294  * \brief Destroys a contidion.
295  *
296  * Destroys and frees the condition's memory. 
297  * \param cond A condition
298  */
299 void SIMIX_cond_destroy(smx_cond_t cond)
300 {
301   DEBUG1("Destroy condition %p", cond);
302   if (cond == NULL)
303     return;
304   else {
305     xbt_fifo_item_t item = NULL;
306     smx_action_t action = NULL;
307
308     xbt_assert0(xbt_swag_size(cond->sleeping) == 0,
309                 "Cannot destroy conditional since someone is still using it");
310     xbt_swag_free(cond->sleeping);
311
312     DEBUG1("%d actions registered", xbt_fifo_size(cond->actions));
313     __SIMIX_cond_display_actions(cond);
314     xbt_fifo_foreach(cond->actions, item, action, smx_action_t) {
315       SIMIX_unregister_action_to_condition(action, cond);
316     }
317     __SIMIX_cond_display_actions(cond);
318
319     xbt_fifo_free(cond->actions);
320     xbt_free(cond);
321     return;
322   }
323 }
324
325 void SIMIX_cond_display_info(smx_cond_t cond)
326 {
327   if (cond == NULL)
328     return;
329   else {
330     smx_process_t process = NULL;
331
332     INFO0("Blocked process on this condition:");
333     xbt_swag_foreach(process, cond->sleeping) {
334       INFO2("\t %s running on host %s", process->name,
335             process->smx_host->name);
336     }
337   }
338 }
339
340 /* ************************** Semaphores ************************************** */
341 #define SMX_SEM_NOLIMIT 99999
342 /** @brief Initialize a semaphore */
343 smx_sem_t SIMIX_sem_init(int capacity) {
344   smx_sem_t sem = xbt_new0(s_smx_sem_t, 1);
345   s_smx_process_t p;
346
347   sem->sleeping = xbt_swag_new(xbt_swag_offset(p, synchro_hookup));
348   sem->actions = xbt_fifo_new();
349   sem->capacity = capacity;
350   return sem;
351 }
352 /** @brief Destroys a semaphore */
353 void SIMIX_sem_destroy(smx_sem_t sem) {
354   DEBUG1("Destroy semaphore %p", sem);
355   if (sem == NULL)
356     return;
357
358   smx_action_t action = NULL;
359
360   xbt_assert0(xbt_swag_size(sem->sleeping) == 0,
361       "Cannot destroy semaphore since someone is still using it");
362   xbt_swag_free(sem->sleeping);
363
364   DEBUG1("%d actions registered", xbt_fifo_size(sem->actions));
365   while((action=xbt_fifo_pop(sem->actions)))
366     SIMIX_unregister_action_to_semaphore(action, sem);
367
368   xbt_fifo_free(sem->actions);
369   xbt_free(sem);
370 }
371
372 /** @brief release the semaphore
373  *
374  * The first locked process on this semaphore is unlocked.
375  * If no one was blocked, the semaphore capacity is increased by 1.
376  * */
377 void SIMIX_sem_release(smx_sem_t sem) {
378         DEBUG1("Sem release semaphore %p", sem);
379   if (xbt_swag_size(sem->sleeping) >= 1) {
380     smx_process_t proc = xbt_swag_extract(sem->sleeping);
381     xbt_swag_insert(proc, simix_global->process_to_run);
382   } else if (sem->capacity != SMX_SEM_NOLIMIT) {
383     sem->capacity++;
384   }
385 }
386 /** @brief make sure the semaphore will never be blocking again
387  *
388  * This function is not really in the semaphore spirit. It makes
389  * sure that the semaphore will never be blocking anymore.
390  *
391  * Releasing and acquiring the semaphore after calling this
392  * function is a noop. Such "broken" semaphores are useful to
393  * implement something between condition variables (with broadcast)
394  * and semaphore (with memory). It's like a semaphore signaled for ever.
395  *
396  * There is no way to reset the semaphore to a more regular state afterward.
397  * */
398 void SIMIX_sem_release_forever(smx_sem_t sem) {
399   smx_process_t proc = NULL;
400   smx_process_t proc_next = NULL;
401
402   DEBUG1("Broadcast semaphore %p", sem);
403   xbt_swag_foreach_safe(proc, proc_next, sem->sleeping) {
404     xbt_swag_remove(proc, sem->sleeping);
405     xbt_swag_insert(proc, simix_global->process_to_run);
406   }
407 }
408
409 /**
410  * \brief Low level wait on a semaphore
411  *
412  * This function does not test the capacity of the semaphore and direcly locks
413  * the calling process on the semaphore (until someone call SIMIX_sem_release()
414  * on this semaphore). Do not call this function if you did not attach any action
415  * to this semaphore to be awaken. Note also that you may miss host failure if you
416  * do not attach a dummy action beforehand. SIMIX_sem_acquire does all these
417  * things for you so you it may be preferable to use.
418  */
419 void SIMIX_sem_block_onto(smx_sem_t sem) {
420   smx_process_t self = SIMIX_process_self();
421
422   /* process status */
423   self->sem = sem;
424   xbt_swag_insert(self, sem->sleeping);
425   SIMIX_process_yield();
426   self->sem = NULL;
427   while (self->suspended)
428     SIMIX_process_yield();
429 }
430
431 /** @brief Returns true if acquiring this semaphore would block */
432 XBT_INLINE int SIMIX_sem_would_block(smx_sem_t sem) {
433   return (sem->capacity>0);
434 }
435
436 /** @brief Returns the current capacity of the semaphore
437  *
438  * If it's negative, that's the amount of processes locked on the semaphore
439  */
440 int SIMIX_sem_get_capacity(smx_sem_t sem){
441   return sem->capacity;
442 }
443
444 /**
445  * \brief Waits on a semaphore
446  *
447  * If the capacity>0, decrease the capacity.
448  *
449  * If capacity==0, locks the current process
450  * until someone call SIMIX_sem_release() on this semaphore
451  */
452 void SIMIX_sem_acquire(smx_sem_t sem) {
453   smx_action_t act_sleep;
454
455   DEBUG1("Wait semaphore %p", sem);
456
457   if (sem->capacity == SMX_SEM_NOLIMIT)
458     return; /* don't even decrease it if wide open */
459
460   /* If capacity sufficient, decrease it */
461   if (sem->capacity>0) {
462     sem->capacity--;
463     return;
464   }
465
466   sem->capacity--;
467   /* Always create an action null in case there is a host failure */
468   act_sleep = SIMIX_action_sleep(SIMIX_host_self(), -1);
469   SIMIX_action_set_name(act_sleep,bprintf("Locked in semaphore %p", sem));
470   SIMIX_process_self()->waiting_action = act_sleep;
471   SIMIX_register_action_to_semaphore(act_sleep, sem);
472   SIMIX_sem_block_onto(sem);
473   SIMIX_process_self()->waiting_action = NULL;
474   SIMIX_unregister_action_to_semaphore(act_sleep, sem);
475   SIMIX_action_destroy(act_sleep);
476   DEBUG1("End of Wait on semaphore %p", sem);
477   sem->capacity++;
478 }
479 /**
480  * \brief Tries to acquire a semaphore before a timeout
481  *
482  * Same behavior of #SIMIX_sem_acquire, but waits a maximum time and throws an timeout_error if it happens.
483  */
484 void SIMIX_sem_acquire_timeout(smx_sem_t sem, double max_duration) {
485   smx_action_t act_sleep;
486
487   DEBUG2("Timed wait semaphore %p (timeout:%f)", sem,max_duration);
488
489   if (sem->capacity == SMX_SEM_NOLIMIT)
490     return; /* don't even decrease it if wide open */
491
492   /* If capacity sufficient, decrease it */
493   if (sem->capacity>0) {
494     sem->capacity--;
495     return;
496   }
497
498   if (max_duration >= 0) {
499     sem->capacity--;
500     act_sleep = SIMIX_action_sleep(SIMIX_host_self(), max_duration);
501     SIMIX_action_set_name(act_sleep,bprintf("Timed wait semaphore %p (max_duration:%f)", sem,max_duration));
502     SIMIX_register_action_to_semaphore(act_sleep, sem);
503     SIMIX_process_self()->waiting_action = act_sleep;
504     SIMIX_sem_block_onto(sem);
505     SIMIX_process_self()->waiting_action = NULL;
506     SIMIX_unregister_action_to_semaphore(act_sleep, sem);
507     if (SIMIX_action_get_state(act_sleep) == SURF_ACTION_DONE) {
508       SIMIX_action_destroy(act_sleep);
509       THROW1(timeout_error, 0, "Semaphore acquire timeouted after %f",max_duration);
510     } else {
511       SIMIX_action_destroy(act_sleep);
512     }
513     sem->capacity++;
514
515   } else
516     SIMIX_sem_acquire(sem);
517 }
518 /**
519  * \brief Blocks on a set of semaphore
520  *
521  * If any of the semaphores has some more capacity, it gets decreased.
522  * If not, blocks until the capacity of one of the semaphores becomes more friendly.
523  *
524  * \return the rank in the dynar of the semaphore which just got locked from the set
525  */
526 unsigned int SIMIX_sem_acquire_any(xbt_dynar_t sems) {
527   smx_sem_t sem;
528   unsigned int counter,result=-1;
529   smx_action_t act_sleep;
530   smx_process_t self = SIMIX_process_self();
531
532   xbt_assert0(xbt_dynar_length(sems),
533       "I refuse to commit sucide by locking on an **empty** set of semaphores!!");
534   DEBUG1("Wait on semaphore set %p", sems);
535
536   xbt_dynar_foreach(sems,counter,sem) {
537     if (!SIMIX_sem_would_block(sem))
538       SIMIX_sem_acquire(sem);
539     return counter;
540   }
541
542   /* Always create an action null in case there is a host failure */
543   act_sleep = SIMIX_action_sleep(SIMIX_host_self(), -1);
544   SIMIX_action_set_name(act_sleep,bprintf("Locked in semaphore %p", sem));
545   self->waiting_action = act_sleep;
546   SIMIX_register_action_to_semaphore(act_sleep, xbt_dynar_get_as(sems,0,smx_sem_t));
547
548   /* Get listed as member of all the provided semaphores */
549   self->sem = (smx_sem_t)sems; /* FIXME: we pass a pointer to dynar where a pointer to sem is expected...*/
550   xbt_dynar_foreach(sems,counter,sem) {
551     xbt_swag_insert(self, sem->sleeping);
552   }
553   SIMIX_process_yield();
554   while (self->suspended)
555     SIMIX_process_yield();
556
557   /* one of the semaphore unsuspended us -- great, let's search which one (and get out of the others) */
558   self->sem = NULL;
559   xbt_dynar_foreach(sems,counter,sem) {
560     if (xbt_swag_belongs(self,sem->sleeping))
561       xbt_swag_remove(self,sem->sleeping);
562     else {
563       xbt_assert0(result==-1,"More than one semaphore unlocked us. Dunno what to do");
564       result = counter;
565     }
566   }
567   xbt_assert0(counter!=-1,"Cannot find which semaphore unlocked me!");
568
569   /* Destroy the waiting action */
570   self->waiting_action = NULL;
571   SIMIX_unregister_action_to_semaphore(act_sleep, xbt_dynar_get_as(sems,0,smx_sem_t));
572   SIMIX_action_destroy(act_sleep);
573   return result;
574 }