Logo AND Algorithmique Numérique Distribuée

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