Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
mailbox.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 
16 
17 
18 
19 */
20 
21 #ifndef _TBB_mailbox_H
22 #define _TBB_mailbox_H
23 
24 #include "tbb/tbb_stddef.h"
26 
27 #include "scheduler_common.h"
28 #include "tbb/atomic.h"
29 
30 namespace tbb {
31 namespace internal {
32 
33 struct task_proxy : public task {
34  static const intptr_t pool_bit = 1<<0;
35  static const intptr_t mailbox_bit = 1<<1;
36  static const intptr_t location_mask = pool_bit | mailbox_bit;
37  /* All but two low-order bits represent a (task*).
38  Two low-order bits mean:
39  1 = proxy is/was/will be in task pool
40  2 = proxy is/was/will be in mailbox */
41  intptr_t task_and_tag;
42 
45 
48 
50  static bool is_shared ( intptr_t tat ) {
51  return (tat & location_mask) == location_mask;
52  }
53 
55  static task* task_ptr ( intptr_t tat ) {
56  return (task*)(tat & ~location_mask);
57  }
58 
60  template<intptr_t from_bit>
61  inline task* extract_task () {
62  __TBB_ASSERT( prefix().extra_state == es_task_proxy, "Normal task misinterpreted as a proxy?" );
63  intptr_t tat = __TBB_load_with_acquire(task_and_tag);
64  __TBB_ASSERT( tat == from_bit || (is_shared(tat) && task_ptr(tat)),
65  "Proxy's tag cannot specify both locations if the proxy "
66  "was retrieved from one of its original locations" );
67  if ( tat != from_bit ) {
68  const intptr_t cleaner_bit = location_mask & ~from_bit;
69  // Attempt to transition the proxy to the "empty" state with
70  // cleaner_bit specifying entity responsible for its eventual freeing.
71  // Explicit cast to void* is to work around a seeming ICC 11.1 bug.
72  if ( as_atomic(task_and_tag).compare_and_swap(cleaner_bit, tat) == tat ) {
73  // Successfully grabbed the task, and left new owner with the job of freeing the proxy
74  return task_ptr(tat);
75  }
76  }
77  // Proxied task has already been claimed from another proxy location.
78  __TBB_ASSERT( task_and_tag == from_bit, "Empty proxy cannot contain non-zero task pointer" );
79  return NULL;
80  }
81 }; // struct task_proxy
82 
85 protected:
87 
90 
93 
95  bool my_is_idle;
96 };
97 
99 
100 class mail_outbox : padded<unpadded_mail_outbox> {
101 
104  if ( !curr )
105  return NULL;
106  task_proxy **prev_ptr = &my_first;
107 #if __TBB_TASK_ISOLATION
108  if ( isolation != no_isolation ) {
109  while ( curr->prefix().isolation != isolation ) {
110  prev_ptr = &curr->next_in_mailbox;
111  curr = curr->next_in_mailbox;
112  if ( !curr )
113  return NULL;
114  }
115  }
116 #endif /* __TBB_TASK_ISOLATION */
117  __TBB_control_consistency_helper(); // on my_first
118  // There is a first item in the mailbox. See if there is a second.
119  if ( task_proxy* second = curr->next_in_mailbox ) {
120  // There are at least two items, so first item can be popped easily.
121  *prev_ptr = second;
122  } else {
123  // There is only one item. Some care is required to pop it.
124  *prev_ptr = NULL;
125  if ( as_atomic( my_last ).compare_and_swap( prev_ptr, &curr->next_in_mailbox ) == &curr->next_in_mailbox ) {
126  // Successfully transitioned mailbox from having one item to having none.
127  __TBB_ASSERT( !curr->next_in_mailbox, NULL );
128  } else {
129  // Some other thread updated my_last but has not filled in first->next_in_mailbox
130  // Wait until first item points to second item.
131  atomic_backoff backoff;
132  while ( !(second = curr->next_in_mailbox) ) backoff.pause();
133  *prev_ptr = second;
134  }
135  }
136  __TBB_ASSERT( curr, NULL );
137  return curr;
138  }
139 public:
140  friend class mail_inbox;
141 
143 
144  void push( task_proxy* t ) {
145  __TBB_ASSERT(t, NULL);
146  t->next_in_mailbox = NULL;
147  proxy_ptr * const link = (proxy_ptr *)__TBB_FetchAndStoreW(&my_last,(intptr_t)&t->next_in_mailbox);
148  // No release fence required for the next store, because there are no memory operations
149  // between the previous fully fenced atomic operation and the store.
150  __TBB_store_relaxed(*link, t);
151  }
152 
154  bool empty() {
155  return __TBB_load_relaxed(my_first) == NULL;
156  }
157 
159 
162  void construct() {
163  __TBB_ASSERT( sizeof(*this)==NFS_MaxLineSize, NULL );
164  __TBB_ASSERT( !my_first, NULL );
165  __TBB_ASSERT( !my_last, NULL );
166  __TBB_ASSERT( !my_is_idle, NULL );
167  my_last=&my_first;
169  }
170 
172  intptr_t drain() {
173  intptr_t k = 0;
174  // No fences here because other threads have already quit.
175  for( ; task_proxy* t = my_first; ++k ) {
178  }
179  return k;
180  }
181 
184  return my_is_idle;
185  }
186 }; // class mail_outbox
187 
189 class mail_inbox {
192 public:
194  mail_inbox() : my_putter(NULL) {}
195 
197  void attach( mail_outbox& putter ) {
198  my_putter = &putter;
199  }
201  void detach() {
202  __TBB_ASSERT(my_putter,"not attached");
203  my_putter = NULL;
204  }
207  return my_putter->internal_pop( __TBB_ISOLATION_EXPR( isolation ) );
208  }
210  bool empty() {
211  return my_putter->empty();
212  }
214 
215  void set_is_idle( bool value ) {
216  if( my_putter ) {
217  __TBB_ASSERT( my_putter->my_is_idle || value, "attempt to redundantly mark mailbox as not idle" );
219  }
220  }
222  bool is_idle_state ( bool value ) const {
223  return !my_putter || my_putter->my_is_idle == value;
224  }
225 
226 #if DO_ITT_NOTIFY
227  void* outbox() const {return my_putter;}
229 #endif /* DO_ITT_NOTIFY */
230 }; // class mail_inbox
231 
232 } // namespace internal
233 } // namespace tbb
234 
235 #endif /* _TBB_mailbox_H */
static bool is_shared(intptr_t tat)
True if the proxy is stored both in its sender's pool and in the destination mailbox.
Definition: mailbox.h:50
bool my_is_idle
Owner of mailbox is not executing a task, and has drained its own task pool.
Definition: mailbox.h:95
Internal representation of mail_outbox, without padding.
Definition: mailbox.h:84
static const intptr_t mailbox_bit
Definition: mailbox.h:35
intptr_t drain()
Drain the mailbox.
Definition: mailbox.h:172
mail_outbox * my_putter
Corresponding sink where mail that we receive will be put.
Definition: mailbox.h:191
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:713
bool empty()
Return true if mailbox is empty.
Definition: mailbox.h:210
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
const isolation_tag no_isolation
Definition: task.h:129
#define __TBB_ISOLATION_EXPR(isolation)
void suppress_unused_warning(const T1 &)
Utility template function to prevent "unused" warnings by various compilers.
Definition: tbb_stddef.h:381
void pause()
Pause for a while.
Definition: tbb_machine.h:364
Base class for user-defined tasks.
Definition: task.h:592
task_proxy * internal_pop(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Definition: mailbox.h:102
Tag for v3 task_proxy.
intptr_t isolation_tag
A tag for task isolation.
Definition: task.h:128
proxy_ptr *__TBB_atomic my_last
Pointer to pointer that will point to next item in the queue. Never NULL.
Definition: mailbox.h:92
bool empty()
Return true if mailbox is empty.
Definition: mailbox.h:154
void __TBB_store_relaxed(volatile T &location, V value)
Definition: tbb_machine.h:743
task_proxy *__TBB_atomic next_in_mailbox
Pointer to next task_proxy in a mailbox.
Definition: mailbox.h:44
void attach(mail_outbox &putter)
Attach inbox to a corresponding outbox.
Definition: mailbox.h:197
void construct()
Construct *this as a mailbox from zeroed memory.
Definition: mailbox.h:162
The graph class.
static const intptr_t location_mask
Definition: mailbox.h:36
task * extract_task()
Returns a pointer to the encapsulated task or NULL, and frees proxy if necessary.
Definition: mailbox.h:61
static task * task_ptr(intptr_t tat)
Returns a pointer to the encapsulated task or NULL.
Definition: mailbox.h:55
Class representing source of mail.
Definition: mailbox.h:189
task_proxy *__TBB_atomic proxy_ptr
Definition: mailbox.h:86
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
Class that implements exponential backoff.
Definition: tbb_machine.h:349
void push(task_proxy *t)
Push task_proxy onto the mailbox queue of another thread.
Definition: mailbox.h:144
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
Definition: tbb_stddef.h:220
T __TBB_load_relaxed(const volatile T &location)
Definition: tbb_machine.h:739
mail_inbox()
Construct unattached inbox.
Definition: mailbox.h:194
#define __TBB_atomic
Definition: tbb_stddef.h:241
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
bool recipient_is_idle()
True if thread that owns this mailbox is looking for work.
Definition: mailbox.h:183
proxy_ptr my_first
Pointer to first task_proxy in mailbox, or NULL if box is empty.
Definition: mailbox.h:89
static const intptr_t pool_bit
Definition: mailbox.h:34
void set_is_idle(bool value)
Indicate whether thread that reads this mailbox is idle.
Definition: mailbox.h:215
void detach()
Detach inbox from its outbox.
Definition: mailbox.h:201
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:941
bool is_idle_state(bool value) const
Indicate whether thread that reads this mailbox is idle.
Definition: mailbox.h:222
task_proxy * pop(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Get next piece of mail, or NULL if mailbox is empty.
Definition: mailbox.h:206
const size_t task_prefix_reservation_size
Number of bytes reserved for a task prefix.
#define __TBB_control_consistency_helper()
Definition: gcc_generic.h:64
Class representing where mail is put.
Definition: mailbox.h:100
mail_outbox * outbox
Mailbox to which this was mailed.
Definition: mailbox.h:47
atomic< T > & as_atomic(T &t)
Definition: atomic.h:547
Pads type T to fill out to a multiple of cache line size.
Definition: tbb_stddef.h:265

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.