1/*
2  This file is part of drd, a thread error detector.
3
4  Copyright (C) 2006-2012 Bart Van Assche <bvanassche@acm.org>.
5
6  This program is free software; you can redistribute it and/or
7  modify it under the terms of the GNU General Public License as
8  published by the Free Software Foundation; either version 2 of the
9  License, or (at your option) any later version.
10
11  This program is distributed in the hope that it will be useful, but
12  WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  General Public License for more details.
15
16  You should have received a copy of the GNU General Public License
17  along with this program; if not, write to the Free Software
18  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19  02111-1307, USA.
20
21  The GNU General Public License is contained in the file COPYING.
22*/
23
24
25#include "drd_clientobj.h"
26#include "drd_error.h"
27#include "drd_semaphore.h"
28#include "drd_suppression.h"
29#include "pub_tool_errormgr.h"    // VG_(maybe_record_error)()
30#include "pub_tool_libcassert.h"  // tl_assert()
31#include "pub_tool_libcprint.h"   // VG_(printf)()
32#include "pub_tool_machine.h"     // VG_(get_IP)()
33#include "pub_tool_mallocfree.h"  // VG_(malloc), VG_(free)
34#include "pub_tool_threadstate.h" // VG_(get_running_tid)()
35
36
37/* Local functions. */
38
39static void semaphore_cleanup(struct semaphore_info* p);
40
41
42/* Local variables. */
43
44static Bool s_trace_semaphore;
45static ULong s_semaphore_segment_creation_count;
46
47
48/* Function definitions. */
49
50/** Push a segment at the end of the queue 'p->last_sem_post_seg'. */
51static void drd_segment_push(struct semaphore_info* p, Segment* sg)
52{
53   Word n;
54
55   tl_assert(sg);
56   n = VG_(addToXA)(p->last_sem_post_seg, &sg);
57#if 0
58   VG_(message)(Vg_DebugMsg, "0x%lx push: added at position %ld/%ld",
59                p->a1, n, VG_(sizeXA)(p->last_sem_post_seg));
60#endif
61   tl_assert(*(Segment**)VG_(indexXA)(p->last_sem_post_seg, n) == sg);
62}
63
64/** Pop a segment from the beginning of the queue 'p->last_sem_post_seg'. */
65static Segment* drd_segment_pop(struct semaphore_info* p)
66{
67   Word sz;
68   Segment* sg;
69
70   sz = VG_(sizeXA)(p->last_sem_post_seg);
71#if 0
72   VG_(message)(Vg_DebugMsg, "0x%lx pop:  removed from position %ld/%ld",
73                p->a1, sz - 1, sz);
74#endif
75   sg = 0;
76   if (sz > 0)
77   {
78      sg = *(Segment**)VG_(indexXA)(p->last_sem_post_seg, sz - 1);
79      tl_assert(sg);
80      VG_(dropTailXA)(p->last_sem_post_seg, 1);
81   }
82   return sg;
83}
84
85/** Enable or disable tracing of semaphore actions. */
86void DRD_(semaphore_set_trace)(const Bool trace_semaphore)
87{
88   s_trace_semaphore = trace_semaphore;
89}
90
91/**
92 * Initialize the memory 'p' points at as a semaphore_info structure for the
93 * client semaphore at client addres 'semaphore'.
94 */
95static
96void drd_semaphore_initialize(struct semaphore_info* const p,
97                              const Addr semaphore)
98{
99   tl_assert(semaphore != 0);
100   tl_assert(p->a1 == semaphore);
101   tl_assert(p->type == ClientSemaphore);
102
103   p->cleanup           = (void(*)(DrdClientobj*))semaphore_cleanup;
104   p->delete_thread     = 0;
105   p->waits_to_skip     = 0;
106   p->value             = 0;
107   p->waiters           = 0;
108   p->last_sem_post_tid = DRD_INVALID_THREADID;
109   p->last_sem_post_seg = VG_(newXA)(VG_(malloc), "drd.sg-stack",
110                                     VG_(free), sizeof(Segment*));
111}
112
113/**
114 * Free the memory that was allocated by semaphore_initialize(). Called by
115 * DRD_(clientobj_remove)().
116 */
117static void semaphore_cleanup(struct semaphore_info* p)
118{
119   Segment* sg;
120
121   if (p->waiters > 0)
122   {
123      SemaphoreErrInfo sei = { DRD_(thread_get_running_tid)(), p->a1 };
124      VG_(maybe_record_error)(VG_(get_running_tid)(),
125                              SemaphoreErr,
126                              VG_(get_IP)(VG_(get_running_tid)()),
127                              "Destruction of semaphore that is being waited"
128                              " upon",
129                              &sei);
130   }
131   while ((sg = drd_segment_pop(p)))
132      DRD_(sg_put)(sg);
133   VG_(deleteXA)(p->last_sem_post_seg);
134}
135
136/**
137 * Return a pointer to the structure with information about the specified
138 * client semaphore. Allocate a new structure if such a structure did not
139 * yet exist.
140 */
141static
142struct semaphore_info*
143drd_semaphore_get_or_allocate(const Addr semaphore)
144{
145   struct semaphore_info *p;
146
147   tl_assert(offsetof(DrdClientobj, semaphore) == 0);
148   p = &(DRD_(clientobj_get)(semaphore, ClientSemaphore)->semaphore);
149   if (p == 0)
150   {
151      tl_assert(offsetof(DrdClientobj, semaphore) == 0);
152      p = &(DRD_(clientobj_add)(semaphore, ClientSemaphore)->semaphore);
153      drd_semaphore_initialize(p, semaphore);
154   }
155   return p;
156}
157
158/**
159 * Return a pointer to the structure with information about the specified
160 * client semaphore, or null if no such structure was found.
161 */
162static struct semaphore_info* semaphore_get(const Addr semaphore)
163{
164   tl_assert(offsetof(DrdClientobj, semaphore) == 0);
165   return &(DRD_(clientobj_get)(semaphore, ClientSemaphore)->semaphore);
166}
167
168/** Called before sem_init(). */
169struct semaphore_info* DRD_(semaphore_init)(const Addr semaphore,
170                                            const Word pshared,
171                                            const UInt value)
172{
173   struct semaphore_info* p;
174   Segment* sg;
175
176   if (s_trace_semaphore)
177      DRD_(trace_msg)("[%d] sem_init      0x%lx value %u",
178                      DRD_(thread_get_running_tid)(), semaphore, value);
179
180   p = semaphore_get(semaphore);
181   if (p)
182   {
183      const ThreadId vg_tid = VG_(get_running_tid)();
184      SemaphoreErrInfo SEI = { DRD_(thread_get_running_tid)(), semaphore };
185      VG_(maybe_record_error)(vg_tid,
186                              SemaphoreErr,
187                              VG_(get_IP)(vg_tid),
188                              "Semaphore reinitialization",
189                              &SEI);
190      // Remove all segments from the segment stack.
191      while ((sg = drd_segment_pop(p)))
192      {
193         DRD_(sg_put)(sg);
194      }
195   }
196   else
197   {
198#if defined(VGO_darwin)
199      const ThreadId vg_tid = VG_(get_running_tid)();
200      GenericErrInfo GEI = { DRD_(thread_get_running_tid)(), 0 };
201      VG_(maybe_record_error)(vg_tid,
202			      GenericErr,
203			      VG_(get_IP)(vg_tid),
204			      "sem_init() is not yet supported on Darwin",
205			      &GEI);
206      return NULL;
207#else
208      p = drd_semaphore_get_or_allocate(semaphore);
209#endif
210   }
211   tl_assert(p);
212   p->waits_to_skip = value;
213   p->value         = value;
214   return p;
215}
216
217/** Called after sem_destroy(). */
218void DRD_(semaphore_destroy)(const Addr semaphore)
219{
220   struct semaphore_info* p;
221
222   p = semaphore_get(semaphore);
223
224   if (s_trace_semaphore)
225      DRD_(trace_msg)("[%d] sem_destroy   0x%lx value %u",
226                      DRD_(thread_get_running_tid)(), semaphore,
227                      p ? p->value : 0);
228
229   if (p == 0)
230   {
231      GenericErrInfo GEI = {
232	 .tid  = DRD_(thread_get_running_tid)(),
233	 .addr = semaphore,
234      };
235      VG_(maybe_record_error)(VG_(get_running_tid)(),
236                              GenericErr,
237                              VG_(get_IP)(VG_(get_running_tid)()),
238                              "Not a semaphore",
239                              &GEI);
240      return;
241   }
242
243   DRD_(clientobj_remove)(semaphore, ClientSemaphore);
244}
245
246/** Called after sem_open(). */
247struct semaphore_info* DRD_(semaphore_open)(const Addr semaphore,
248                                            const Char* name, const Word oflag,
249                                            const Word mode, const UInt value)
250{
251   struct semaphore_info* p;
252   Segment* sg;
253
254   if (s_trace_semaphore)
255      DRD_(trace_msg)("[%d] sem_open      0x%lx name %s"
256                      " oflag %#lx mode %#lo value %u",
257                      DRD_(thread_get_running_tid)(),
258                      semaphore, name, oflag, mode, value);
259
260   /* Return if the sem_open() call failed. */
261   if (! semaphore)
262      return NULL;
263
264   p = semaphore_get(semaphore);
265   if (p)
266   {
267      const ThreadId vg_tid = VG_(get_running_tid)();
268      SemaphoreErrInfo SEI = { DRD_(thread_get_running_tid)(), semaphore };
269      VG_(maybe_record_error)(vg_tid,
270                              SemaphoreErr,
271                              VG_(get_IP)(vg_tid),
272                              "Semaphore reinitialization",
273                              &SEI);
274      // Remove all segments from the segment stack.
275      while ((sg = drd_segment_pop(p)))
276      {
277         DRD_(sg_put)(sg);
278      }
279   }
280   else
281   {
282      p = drd_semaphore_get_or_allocate(semaphore);
283   }
284   tl_assert(p);
285   p->waits_to_skip = value;
286   p->value         = value;
287   return p;
288}
289
290/** Called before sem_close(). */
291void DRD_(semaphore_close)(const Addr semaphore)
292{
293   struct semaphore_info* p;
294
295   p = semaphore_get(semaphore);
296
297   if (s_trace_semaphore)
298      DRD_(trace_msg)("[%d] sem_close     0x%lx value %u",
299                      DRD_(thread_get_running_tid)(), semaphore,
300                      p ? p->value : 0);
301
302   if (p == 0)
303   {
304      GenericErrInfo GEI = {
305	 .tid  = DRD_(thread_get_running_tid)(),
306	 .addr = semaphore,
307      };
308      VG_(maybe_record_error)(VG_(get_running_tid)(),
309                              GenericErr,
310                              VG_(get_IP)(VG_(get_running_tid)()),
311                              "Not a semaphore",
312                              &GEI);
313      return;
314   }
315
316   DRD_(clientobj_remove)(semaphore, ClientSemaphore);
317}
318
319/** Called before sem_wait(). */
320void DRD_(semaphore_pre_wait)(const Addr semaphore)
321{
322   struct semaphore_info* p;
323
324   tl_assert(semaphore < semaphore + 1);
325   p = drd_semaphore_get_or_allocate(semaphore);
326   tl_assert(p);
327   p->waiters++;
328
329   if ((Word)(p->waiters) <= 0)
330   {
331      SemaphoreErrInfo sei = { DRD_(thread_get_running_tid)(), semaphore };
332      VG_(maybe_record_error)(VG_(get_running_tid)(),
333                              SemaphoreErr,
334                              VG_(get_IP)(VG_(get_running_tid)()),
335                              "Invalid semaphore",
336                              &sei);
337   }
338}
339
340/**
341 * Called after sem_wait() finished.
342 * @note Some C libraries do not set the 'waited' value correctly.
343 */
344void DRD_(semaphore_post_wait)(const DrdThreadId tid, const Addr semaphore,
345                               const Bool waited)
346{
347   struct semaphore_info* p;
348   Segment* sg;
349
350   tl_assert(waited == 0 || waited == 1);
351   p = semaphore_get(semaphore);
352   if (s_trace_semaphore)
353      DRD_(trace_msg)("[%d] sem_wait      0x%lx value %u -> %u%s",
354                      DRD_(thread_get_running_tid)(), semaphore,
355                      p ? p->value : 0, p ? p->value - waited : 0,
356		      waited ? "" : " (did not wait)");
357
358   if (p) {
359      p->waiters--;
360      p->value -= waited;
361   }
362
363   /*
364    * Note: if another thread destroyed and reinitialized a semaphore while
365    * the current thread was waiting in sem_wait, p->waiters may have been
366    * set to zero by drd_semaphore_initialize() after
367    * DRD_(semaphore_pre_wait)() has finished before
368    * DRD_(semaphore_post_wait)() has been called.
369    */
370   if (p == NULL || (Int)(p->value) < 0 || (Word)(p->waiters) < 0)
371   {
372      SemaphoreErrInfo sei = { DRD_(thread_get_running_tid)(), semaphore };
373      VG_(maybe_record_error)(VG_(get_running_tid)(),
374                              SemaphoreErr,
375                              VG_(get_IP)(VG_(get_running_tid)()),
376                              "Invalid semaphore",
377                              &sei);
378      return;
379   }
380
381   if (!waited)
382      return;
383
384   if (p->waits_to_skip > 0)
385      p->waits_to_skip--;
386   else
387   {
388      sg = drd_segment_pop(p);
389      tl_assert(sg);
390      if (p->last_sem_post_tid != tid
391          && p->last_sem_post_tid != DRD_INVALID_THREADID)
392      {
393         DRD_(thread_new_segment_and_combine_vc)(tid, sg);
394      }
395      else
396         DRD_(thread_new_segment)(tid);
397      s_semaphore_segment_creation_count++;
398      DRD_(sg_put)(sg);
399   }
400}
401
402/** Called before sem_post(). */
403void DRD_(semaphore_pre_post)(const DrdThreadId tid, const Addr semaphore)
404{
405   struct semaphore_info* p;
406   Segment* sg;
407
408   p = drd_semaphore_get_or_allocate(semaphore);
409   p->value++;
410
411   if (s_trace_semaphore)
412      DRD_(trace_msg)("[%d] sem_post      0x%lx value %u -> %u",
413                      DRD_(thread_get_running_tid)(),
414                      semaphore, p->value - 1, p->value);
415
416   p->last_sem_post_tid = tid;
417   sg = 0;
418   DRD_(thread_get_latest_segment)(&sg, tid);
419   tl_assert(sg);
420   drd_segment_push(p, sg);
421   DRD_(thread_new_segment)(tid);
422   s_semaphore_segment_creation_count++;
423}
424
425/** Called after sem_post() finished. */
426void DRD_(semaphore_post_post)(const DrdThreadId tid, const Addr semaphore,
427                               const Bool succeeded)
428{
429   /*
430    * Note: it is hard to implement the sem_post() wrapper correctly in
431    * case sem_post() returns an error code. This is because handling this
432    * case correctly requires restoring the vector clock associated with
433    * the semaphore to its original value here. In order to do that without
434    * introducing a race condition, extra locking has to be added around
435    * each semaphore call. Such extra locking would have to be added in
436    * drd_pthread_intercepts.c. However, it is hard to implement
437    * synchronization in drd_pthread_intercepts.c in a portable way without
438    * calling already redirected functions.
439    */
440}
441
442ULong DRD_(get_semaphore_segment_creation_count)(void)
443{
444   return s_semaphore_segment_creation_count;
445}
446