1 /************************************************************************
2 ** **
3 ** The YapTab/YapOr/OPTYap systems **
4 ** **
5 ** YapTab extends the Yap Prolog engine to support sequential tabling **
6 ** YapOr extends the Yap Prolog engine to support or-parallelism **
7 ** OPTYap extends the Yap Prolog engine to support or-parallel tabling **
8 ** **
9 ** **
10 ** Yap Prolog was developed at University of Porto, Portugal **
11 ** **
12 ************************************************************************/
13
14 /**********************
15 ** Typedefs **
16 **********************/
17
18 typedef double realtime;
19 typedef unsigned long bitmap;
20
21 #ifdef THREADS
22 /* Threads may not assume addresses are the same at different workers */
23 static inline choiceptr
offset_to_cptr(Int node)24 offset_to_cptr(Int node)
25 {
26 return (choiceptr)(LCL0+node);
27 }
28
29 static inline Int
cptr_to_offset(choiceptr node)30 cptr_to_offset(choiceptr node)
31 {
32 return (Int)((CELL *)node-LCL0);
33 }
34
35 static inline choiceptr
offset_to_cptr_with_null(Int node)36 offset_to_cptr_with_null(Int node)
37 {
38 if (node == 0L) return NULL;
39 return (choiceptr)(LCL0+node);
40 }
41
42 static inline Int
cptr_to_offset_with_null(choiceptr node)43 cptr_to_offset_with_null(choiceptr node)
44 {
45 if (node == NULL) return 0L;
46 return (Int)((CELL *)node-LCL0);
47 }
48 #endif /* THREADS */
49
50
51
52 /*********************************
53 ** Struct page_header **
54 *********************************/
55
56 typedef struct page_header {
57 volatile int structs_in_use;
58 void *first_free_struct;
59 struct page_header *previous;
60 struct page_header *next;
61 } *pg_hd_ptr;
62
63 #define PgHd_str_in_use(X) ((X)->structs_in_use)
64 #define PgHd_free_str(X) ((X)->first_free_struct)
65 #define PgHd_previous(X) ((X)->previous)
66 #define PgHd_next(X) ((X)->next)
67
68
69
70 /***************************
71 ** Struct pages **
72 ***************************/
73
74 struct pages {
75 #ifdef SHM_MEMORY_ALLOC_SCHEME
76 #ifdef YAPOR
77 lockvar lock;
78 #endif /* YAPOR */
79 int structs_per_page;
80 struct page_header *first_free_page;
81 volatile long pages_allocated;
82 #endif /* SHM_MEMORY_ALLOC_SCHEME */
83 volatile long structs_in_use;
84 };
85
86 #define Pg_lock(X) ((X).lock)
87 #define Pg_str_per_pg(X) ((X).structs_per_page)
88 #define Pg_free_pg(X) ((X).first_free_page)
89 #define Pg_pg_alloc(X) ((X).pages_allocated)
90 #define Pg_str_in_use(X) ((X).structs_in_use)
91 #define Pg_str_free(X) (Pg_pg_alloc(X) * Pg_str_per_pg(X) - Pg_str_in_use(X))
92
93
94
95 /**********************************
96 ** Struct global_pages **
97 **********************************/
98
99 struct global_pages {
100 #ifdef LIMIT_TABLING
101 int max_pages;
102 #endif /* LIMIT_TABLING */
103 struct pages void_pages;
104 #ifdef YAPOR
105 struct pages or_frame_pages;
106 struct pages query_goal_solution_frame_pages;
107 struct pages query_goal_answer_frame_pages;
108 #endif /* YAPOR */
109 #ifdef TABLING_INNER_CUTS
110 struct pages table_subgoal_solution_frame_pages;
111 struct pages table_subgoal_answer_frame_pages;
112 #endif /* TABLING_INNER_CUTS */
113 #ifdef TABLING
114 struct pages table_entry_pages;
115 struct pages subgoal_frame_pages;
116 struct pages dependency_frame_pages;
117 struct pages subgoal_trie_node_pages;
118 struct pages answer_trie_node_pages;
119 struct pages global_trie_node_pages;
120 struct pages subgoal_trie_hash_pages;
121 struct pages answer_trie_hash_pages;
122 struct pages global_trie_hash_pages;
123 #endif /* TABLING */
124 #if defined(YAPOR) && defined(TABLING)
125 struct pages suspension_frame_pages;
126 #endif /* YAPOR && TABLING */
127 };
128
129
130
131 /**********************************
132 ** Struct global_locks **
133 **********************************/
134
135 #ifdef YAPOR
136 struct global_locks {
137 lockvar bitmap_idle_workers;
138 lockvar bitmap_root_cp_workers;
139 lockvar bitmap_invisible_workers;
140 lockvar bitmap_requestable_workers;
141 lockvar bitmap_executing_workers;
142 lockvar bitmap_finished_workers;
143 #ifdef TABLING_INNER_CUTS
144 lockvar bitmap_pruning_workers;
145 #endif /* TABLING_INNER_CUTS */
146
147 int who_locked_heap;
148 lockvar heap_access;
149 lockvar alloc_block;
150 };
151 #endif /* YAPOR */
152
153
154
155 /*********************************
156 ** Struct global_data **
157 *********************************/
158
159 struct global_data{
160 /* global data related to memory management */
161 struct global_pages pages;
162
163 #ifdef YAPOR
164 /* global static data */
165 int scheduler_loop;
166 int delayed_release_load;
167 int number_workers;
168 int worker_pid[MAX_WORKERS];
169 #ifdef ACOW
170 int master_worker;
171 #endif /* ACOW */
172
173 /* global data related to or-performance */
174 realtime execution_time;
175 realtime best_execution_times[MAX_BEST_TIMES];
176 int number_of_executed_goals;
177 char performance_mode; /* PERFORMANCE_OFF / PERFORMANCE_ON / PERFORMANCE_IN_EXECUTION */
178
179 /* global data related to or-parallelism */
180 #if THREADS
181 Int root_choice_point_offset;
182 #else
183 choiceptr root_choice_point;
184 #endif
185 struct or_frame *root_or_frame;
186 bitmap present_workers;
187 volatile bitmap idle_workers;
188 volatile bitmap root_cp_workers;
189 volatile bitmap invisible_workers;
190 volatile bitmap requestable_workers;
191 volatile bitmap executing_workers;
192 volatile bitmap finished_workers;
193 #ifdef TABLING_INNER_CUTS
194 volatile bitmap pruning_workers;
195 #endif /* TABLING_INNER_CUTS */
196 struct global_locks locks;
197 volatile unsigned int branch[MAX_WORKERS][MAX_BRANCH_DEPTH];
198 volatile char parallel_execution_mode; /* TRUE / FALSE */
199 volatile int answers;
200 #endif /* YAPOR */
201
202 #ifdef TABLING
203 /* global data related to tabling */
204 struct global_trie_node *root_global_trie;
205 struct table_entry *root_table_entry;
206 #ifdef LIMIT_TABLING
207 struct subgoal_frame *first_subgoal_frame;
208 struct subgoal_frame *last_subgoal_frame;
209 struct subgoal_frame *check_subgoal_frame;
210 #endif /* LIMIT_TABLING */
211 struct dependency_frame *root_dependency_frame;
212 CELL table_var_enumerator[MAX_TABLE_VARS];
213 #ifdef TABLE_LOCK_AT_WRITE_LEVEL
214 lockvar table_lock[TABLE_LOCK_BUCKETS];
215 #endif /* TABLE_LOCK_AT_WRITE_LEVEL */
216 #ifdef TIMESTAMP_CHECK
217 long timestamp;
218 #endif /* TIMESTAMP_CHECK */
219 #endif /* TABLING */
220 };
221
222 #define GLOBAL_MAX_PAGES (GLOBAL.pages.max_pages)
223 #define GLOBAL_PAGES_void (GLOBAL.pages.void_pages)
224 #define GLOBAL_PAGES_or_fr (GLOBAL.pages.or_frame_pages)
225 #define GLOBAL_PAGES_qg_sol_fr (GLOBAL.pages.query_goal_solution_frame_pages)
226 #define GLOBAL_PAGES_qg_ans_fr (GLOBAL.pages.query_goal_answer_frame_pages)
227 #define GLOBAL_PAGES_tg_sol_fr (GLOBAL.pages.table_subgoal_solution_frame_pages)
228 #define GLOBAL_PAGES_tg_ans_fr (GLOBAL.pages.table_subgoal_answer_frame_pages)
229 #define GLOBAL_PAGES_tab_ent (GLOBAL.pages.table_entry_pages)
230 #define GLOBAL_PAGES_sg_fr (GLOBAL.pages.subgoal_frame_pages)
231 #define GLOBAL_PAGES_dep_fr (GLOBAL.pages.dependency_frame_pages)
232 #define GLOBAL_PAGES_sg_node (GLOBAL.pages.subgoal_trie_node_pages)
233 #define GLOBAL_PAGES_ans_node (GLOBAL.pages.answer_trie_node_pages)
234 #define GLOBAL_PAGES_gt_node (GLOBAL.pages.global_trie_node_pages)
235 #define GLOBAL_PAGES_sg_hash (GLOBAL.pages.subgoal_trie_hash_pages)
236 #define GLOBAL_PAGES_ans_hash (GLOBAL.pages.answer_trie_hash_pages)
237 #define GLOBAL_PAGES_gt_hash (GLOBAL.pages.global_trie_hash_pages)
238 #define GLOBAL_PAGES_susp_fr (GLOBAL.pages.suspension_frame_pages)
239 #define SCHEDULER_LOOP (GLOBAL.scheduler_loop)
240 #define DELAYED_RELEASE_LOAD (GLOBAL.delayed_release_load)
241 #define number_workers (GLOBAL.number_workers)
242 #define worker_pid(worker) (GLOBAL.worker_pid[worker])
243 #define GLOBAL_master_worker (GLOBAL.master_worker)
244 #define GLOBAL_execution_time (GLOBAL.execution_time)
245 #define GLOBAL_best_times(time) (GLOBAL.best_execution_times[time])
246 #define GLOBAL_number_goals (GLOBAL.number_of_executed_goals)
247 #define GLOBAL_performance_mode (GLOBAL.performance_mode)
248 #if THREADS
249 #define Get_GLOBAL_root_cp() offset_to_cptr(GLOBAL.root_choice_point_offset)
250 #define Set_GLOBAL_root_cp(bptr) (GLOBAL.root_choice_point_offset = cptr_to_offset(bptr))
251 #else
252 #define GLOBAL_root_cp (GLOBAL.root_choice_point)
253 #define Get_GLOBAL_root_cp() (GLOBAL.root_choice_point)
254 #define Set_GLOBAL_root_cp(bptr) (GLOBAL.root_choice_point = (bptr))
255 #endif
256 #define GLOBAL_root_or_fr (GLOBAL.root_or_frame)
257 #define GLOBAL_bm_present_workers (GLOBAL.present_workers)
258 #define GLOBAL_bm_idle_workers (GLOBAL.idle_workers)
259 #define GLOBAL_bm_root_cp_workers (GLOBAL.root_cp_workers)
260 #define GLOBAL_bm_invisible_workers (GLOBAL.invisible_workers)
261 #define GLOBAL_bm_requestable_workers (GLOBAL.requestable_workers)
262 #define GLOBAL_bm_executing_workers (GLOBAL.executing_workers)
263 #define GLOBAL_bm_finished_workers (GLOBAL.finished_workers)
264 #define GLOBAL_bm_pruning_workers (GLOBAL.pruning_workers)
265 #define GLOBAL_LOCKS_bm_idle_workers (GLOBAL.locks.bitmap_idle_workers)
266 #define GLOBAL_LOCKS_bm_root_cp_workers (GLOBAL.locks.bitmap_root_cp_workers)
267 #define GLOBAL_LOCKS_bm_invisible_workers (GLOBAL.locks.bitmap_invisible_workers)
268 #define GLOBAL_LOCKS_bm_requestable_workers (GLOBAL.locks.bitmap_requestable_workers)
269 #define GLOBAL_LOCKS_bm_executing_workers (GLOBAL.locks.bitmap_executing_workers)
270 #define GLOBAL_LOCKS_bm_finished_workers (GLOBAL.locks.bitmap_finished_workers)
271 #define GLOBAL_LOCKS_bm_pruning_workers (GLOBAL.locks.bitmap_pruning_workers)
272 #define GLOBAL_LOCKS_who_locked_heap (GLOBAL.locks.who_locked_heap)
273 #define GLOBAL_LOCKS_heap_access (GLOBAL.locks.heap_access)
274 #define GLOBAL_LOCKS_alloc_block (GLOBAL.locks.alloc_block)
275 #define GLOBAL_branch(worker, depth) (GLOBAL.branch[worker][depth])
276 #define PARALLEL_EXECUTION_MODE (GLOBAL.parallel_execution_mode)
277 #define GLOBAL_answers (GLOBAL.answers)
278 #define GLOBAL_root_gt (GLOBAL.root_global_trie)
279 #define GLOBAL_root_tab_ent (GLOBAL.root_table_entry)
280 #define GLOBAL_first_sg_fr (GLOBAL.first_subgoal_frame)
281 #define GLOBAL_last_sg_fr (GLOBAL.last_subgoal_frame)
282 #define GLOBAL_check_sg_fr (GLOBAL.check_subgoal_frame)
283 #define GLOBAL_root_dep_fr (GLOBAL.root_dependency_frame)
284 #define GLOBAL_table_var_enumerator(index) (GLOBAL.table_var_enumerator[index])
285 #define GLOBAL_table_var_enumerator_addr(index) (GLOBAL.table_var_enumerator + (index))
286 #define GLOBAL_table_lock(index) (GLOBAL.table_lock[index])
287 #define GLOBAL_timestamp (GLOBAL.timestamp)
288
289
290
291 /***********************************
292 ** Struct local_signals **
293 ***********************************/
294
295 #ifdef YAPOR
296 struct local_signals{
297 #if defined(ENV_COPY) || defined(THREADS)
298 lockvar lock;
299 volatile enum {
300 Q_idle = 0,
301 trail = 1,
302 global = 2,
303 local = 3,
304 P_idle = 4
305 } P_fase, Q_fase;
306 #endif /* ENV_COPY || THREADS */
307 volatile enum {
308 no_sharing = 0,
309 sharing = 1,
310 nodes_shared = 2,
311 copy_done = 3,
312 worker_ready = 4
313 } reply;
314 };
315 #endif /* YAPOR */
316
317
318
319 /********************************
320 ** Struct local_data **
321 ********************************/
322
323 struct local_data{
324 #if defined(YAPOR) || defined(THREADS)
325 lockvar lock;
326 #endif
327 #ifdef YAPOR
328 /* local data related to or-parallelism */
329 volatile int load;
330 #if THREADS
331 Int top_choice_point_offset;
332 #else
333 choiceptr top_choice_point;
334 #endif
335 struct or_frame *top_or_frame;
336 #if THREADS
337 Int prune_request_offset;
338 #else
339 choiceptr prune_request;
340 #endif
341 volatile int share_request;
342 struct local_signals share_signals;
343 volatile struct {
344 CELL start;
345 CELL end;
346 } global_copy, local_copy, trail_copy;
347 #endif /* YAPOR */
348
349 #ifdef TABLING
350 /* local data related to tabling */
351 struct answer_trie_node *next_free_answer_trie_node;
352 struct subgoal_frame *top_subgoal_frame;
353 struct dependency_frame *top_dependency_frame;
354 #ifdef TABLING_INNER_CUTS
355 choiceptr bottom_pruning_scope;
356 #endif /* TABLING_INNER_CUTS */
357 #ifdef YAPOR
358 #ifdef THREADS
359 Int top_choice_point_on_stack_offset;
360 #else
361 choiceptr top_choice_point_on_stack;
362 #endif
363 struct or_frame *top_or_frame_with_suspensions;
364 #endif /* YAPOR */
365 #endif /* TABLING */
366 };
367
368 #define LOCAL_lock (LOCAL->lock)
369 #define LOCAL_load (LOCAL->load)
370 #if THREADS
371 #define Get_LOCAL_top_cp() offset_to_cptr(LOCAL->top_choice_point_offset)
372 #define Set_LOCAL_top_cp(cpt) (LOCAL->top_choice_point_offset = cptr_to_offset(cpt))
373 #else
374 #define LOCAL_top_cp (LOCAL->top_choice_point)
375 #define Get_LOCAL_top_cp() (LOCAL->top_choice_point)
376 #define Set_LOCAL_top_cp(cpt) (LOCAL->top_choice_point = cpt)
377 #endif
378 #define LOCAL_top_or_fr (LOCAL->top_or_frame)
379 #if THREADS
380 #define Get_LOCAL_prune_request() offset_to_cptr_with_null(LOCAL->prune_request_offset)
381 #define Set_LOCAL_prune_request(cpt) (LOCAL->prune_request_offset = cptr_to_offset_with_null(cpt))
382 #else
383 #define LOCAL_prune_request (LOCAL->prune_request)
384 #define Get_LOCAL_prune_request() (LOCAL->prune_request)
385 #define Set_LOCAL_prune_request(cpt) (LOCAL->prune_request = cpt)
386 #endif
387 #define LOCAL_share_request (LOCAL->share_request)
388 #define LOCAL_reply_signal (LOCAL->share_signals.reply)
389 #define LOCAL_p_fase_signal (LOCAL->share_signals.P_fase)
390 #define LOCAL_q_fase_signal (LOCAL->share_signals.Q_fase)
391 #define LOCAL_lock_signals (LOCAL->share_signals.lock)
392 #define LOCAL_start_global_copy (LOCAL->global_copy.start)
393 #define LOCAL_end_global_copy (LOCAL->global_copy.end)
394 #define LOCAL_start_local_copy (LOCAL->local_copy.start)
395 #define LOCAL_end_local_copy (LOCAL->local_copy.end)
396 #define LOCAL_start_trail_copy (LOCAL->trail_copy.start)
397 #define LOCAL_end_trail_copy (LOCAL->trail_copy.end)
398 #define LOCAL_next_free_ans_node (LOCAL->next_free_answer_trie_node)
399 #define LOCAL_top_sg_fr (LOCAL->top_subgoal_frame)
400 #define LOCAL_top_dep_fr (LOCAL->top_dependency_frame)
401 #define LOCAL_pruning_scope (LOCAL->bottom_pruning_scope)
402 #if THREADS
403 #define Get_LOCAL_top_cp_on_stack() offset_to_cptr(LOCAL->top_choice_point_on_stack_offset)
404 #define Set_LOCAL_top_cp_on_stack(cpt) (LOCAL->top_choice_point_on_stack_offset = cptr_to_offset(cpt))
405 #else
406 #define LOCAL_top_cp_on_stack (LOCAL->top_choice_point_on_stack)
407 #define Get_LOCAL_top_cp_on_stack() (LOCAL->top_choice_point_on_stack)
408 #define Set_LOCAL_top_cp_on_stack(cpt) (LOCAL->top_choice_point_on_stack = cpt)
409 #endif
410 #define LOCAL_top_susp_or_fr (LOCAL->top_or_frame_with_suspensions)
411
412 #define REMOTE_lock(worker) (REMOTE[worker].lock)
413 #define REMOTE_load(worker) (REMOTE[worker].load)
414 #if THREADS
415 #define REMOTE_top_cp(worker) offset_to_cptr(REMOTE[worker].top_choice_point_offset)
416 #define Set_REMOTE_top_cp(worker, bptr) (REMOTE[worker].top_choice_point_offset = cptr_to_offset(bptr))
417 #else
418 #define REMOTE_top_cp(worker) (REMOTE[worker].top_choice_point)
419 #define Set_REMOTE_top_cp(worker, bptr) (REMOTE[worker].top_choice_point = (bptr))
420 #endif
421 #define REMOTE_top_or_fr(worker) (REMOTE[worker].top_or_frame)
422 #if THREADS
423 #define Get_REMOTE_prune_request(worker) offset_to_cptr_with_null(REMOTE[worker].prune_request_offset)
424 #define Set_REMOTE_prune_request(worker,cp) (REMOTE[worker].prune_request_offset = cptr_to_offset_with_null(cp))
425 #else
426 #define REMOTE_prune_request(worker) (REMOTE[worker].prune_request)
427 #define Get_REMOTE_prune_request(worker) (REMOTE[worker].prune_request)
428 #define Set_REMOTE_prune_request(worker,cp) (REMOTE[worker].prune_request = cp)
429 #endif
430 #define REMOTE_share_request(worker) (REMOTE[worker].share_request)
431 #define REMOTE_reply_signal(worker) (REMOTE[worker].share_signals.reply)
432 #define REMOTE_p_fase_signal(worker) (REMOTE[worker].share_signals.P_fase)
433 #define REMOTE_q_fase_signal(worker) (REMOTE[worker].share_signals.Q_fase)
434 #define REMOTE_lock_signals(worker) (REMOTE[worker].share_signals.lock)
435 #define REMOTE_start_global_copy(worker) (REMOTE[worker].global_copy.start)
436 #define REMOTE_end_global_copy(worker) (REMOTE[worker].global_copy.end)
437 #define REMOTE_start_local_copy(worker) (REMOTE[worker].local_copy.start)
438 #define REMOTE_end_local_copy(worker) (REMOTE[worker].local_copy.end)
439 #define REMOTE_start_trail_copy(worker) (REMOTE[worker].trail_copy.start)
440 #define REMOTE_end_trail_copy(worker) (REMOTE[worker].trail_copy.end)
441 #define REMOTE_next_free_ans_node(worker) (REMOTE[worker].next_free_answer_trie_node)
442 #define REMOTE_top_sg_fr(worker) (REMOTE[worker].top_subgoal_frame)
443 #define REMOTE_top_dep_fr(worker) (REMOTE[worker].top_dependency_frame)
444 #define REMOTE_pruning_scope(worker) (REMOTE[worker].bottom_pruning_scope)
445 #if THREADS
446 #define REMOTE_top_cp_on_stack(worker) offset_to_cptr(REMOTE[worker].top_choice_point_on_stack_offset)
447 #define Set_REMOTE_top_cp_on_stack(worker, bptr) (REMOTE[worker].top_choice_point_on_stack_offset = cptr_to_offset(bptr))
448 #else
449 #define REMOTE_top_cp_on_stack(worker) (REMOTE[worker].top_choice_point_on_stack)
450 #define Set_REMOTE_top_cp_on_stack(worker, bptr) (REMOTE[worker].top_choice_point_on_stack = (bptr))
451 #endif
452 #define REMOTE_top_susp_or_fr(worker) (REMOTE[worker].top_or_frame_with_suspensions)
453
454
455 #ifdef YAPOR
456 #include "or.structs.h"
457 #endif /* YAPOR */
458
459
460 #ifdef TABLING
461 #include "tab.structs.h"
462 #endif /* TABLING */
463