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 **      Includes      **
16 ** ------------------ */
17 
18 #include "Yap.h"
19 #ifdef ACOW
20 #include <sys/types.h>
21 #include <unistd.h>
22 #include <stdio.h>
23 #include "Yatom.h"
24 #include "YapHeap.h"
25 #include "or.macros.h"
26 
27 
28 
29 
30 /* ------------------------------------- **
31 **      Local functions declaration      **
32 ** ------------------------------------- */
33 
34 static void share_private_nodes(int worker_q);
35 
36 
37 
38 /* ----------------------- **
39 **      Local inlines      **
40 ** ----------------------- */
41 
42 STD_PROTO(static inline void PUT_BUSY, (int));
43 
44 static inline
PUT_BUSY(int worker_num)45 void PUT_BUSY(int worker_num) {
46   LOCK(GLOBAL_LOCKS_bm_idle_workers);
47   BITMAP_delete(GLOBAL_bm_idle_workers, worker_num);
48   UNLOCK(GLOBAL_LOCKS_bm_idle_workers);
49   return;
50 }
51 
52 
53 
54 /* -------------------------- **
55 **      Global functions      **
56 ** -------------------------- */
57 
make_root_choice_point(void)58 void make_root_choice_point(void) {
59   if (worker_id == 0) {
60     LOCAL_top_cp = GLOBAL_root_cp = OrFr_node(GLOBAL_root_or_fr) = B;
61   } else {
62     B = LOCAL_top_cp = GLOBAL_root_cp;
63     B->cp_tr = TR = ((choiceptr) (worker_offset(0) + (CELL)(B)))->cp_tr;
64   }
65   B->cp_h = H0;
66   B->cp_ap = GETWORK;
67   B->cp_or_fr = GLOBAL_root_or_fr;
68   LOCAL_top_or_fr = GLOBAL_root_or_fr;
69   LOCAL_load = 0;
70   LOCAL_prune_request = NULL;
71   BRANCH(worker_id, 0) = 0;
72   return;
73 }
74 
75 
free_root_choice_point(void)76 void free_root_choice_point(void) {
77   B = LOCAL_top_cp->cp_b;
78   LOCAL_top_cp = (choiceptr) Yap_LocalBase;
79   return;
80 }
81 
82 
p_share_work(void)83 int p_share_work(void) {
84   int worker_q = LOCAL_share_request;
85   int son;
86 
87   if (! BITMAP_member(OrFr_members(REMOTE_top_or_fr(worker_q)), worker_id) ||
88       B == REMOTE_top_cp(worker_q) ||
89       (LOCAL_load <= DELAYED_RELEASE_LOAD && OrFr_nearest_livenode(LOCAL_top_or_fr) == NULL)) {
90     /* refuse sharing request */
91     REMOTE_reply_signal(LOCAL_share_request) = no_sharing;
92     LOCAL_share_request = MAX_WORKERS;
93     PUT_OUT_REQUESTABLE(worker_id);
94     return TRUE;
95   }
96   /* sharing request accepted */
97   REMOTE_reply_signal(worker_q) = sharing;
98   share_private_nodes(worker_q);
99   if ((son = fork()) == 0) {
100     worker_id = worker_q;  /* child becomes requesting worker */
101     LOCAL = REMOTE + worker_id;
102     LOCAL_reply_signal = ready;
103     PUT_IN_REQUESTABLE(worker_id);
104     PUT_BUSY(worker_id);
105 
106     return FALSE;
107   } else {
108     worker_pid(worker_q) = son;
109     LOCAL_share_request = MAX_WORKERS;
110     PUT_IN_REQUESTABLE(worker_id);
111 
112     return TRUE;
113   }
114 }
115 
116 
q_share_work(int worker_p)117 int q_share_work(int worker_p) {
118   LOCK_OR_FRAME(LOCAL_top_or_fr);
119   if (Get_REMOTE_prune_request(worker_p)) {
120     /* worker p with prune request */
121     UNLOCK_OR_FRAME(LOCAL_top_or_fr);
122     return FALSE;
123   }
124   YAPOR_ERROR_CHECKING(q_share_work, OrFr_pend_prune_cp(LOCAL_top_or_fr) && BRANCH_LTT(worker_p, OrFr_depth(LOCAL_top_or_fr)) < OrFr_pend_prune_ltt(LOCAL_top_or_fr));
125   /* there is no pending prune with worker p at right --> safe move to worker p branch */
126   BRANCH(worker_id, OrFr_depth(LOCAL_top_or_fr)) = BRANCH(worker_p, OrFr_depth(LOCAL_top_or_fr));
127   LOCAL_prune_request = NULL;
128   UNLOCK_OR_FRAME(LOCAL_top_or_fr);
129 
130   /* make sharing request */
131   LOCK_WORKER(worker_p);
132   if (BITMAP_member(GLOBAL_bm_idle_workers, worker_p) ||
133       REMOTE_share_request(worker_p) != MAX_WORKERS) {
134     /* worker p is idle or has another request */
135     UNLOCK_WORKER(worker_p);
136     return FALSE;
137   }
138   REMOTE_share_request(worker_p) = worker_id;
139   UNLOCK_WORKER(worker_p);
140 
141   /* wait for an answer */
142   while (LOCAL_reply_signal == ready);
143   if (LOCAL_reply_signal == no_sharing) {
144     /* sharing request refused */
145     LOCAL_reply_signal = ready;
146     return FALSE;
147   }
148   /* exit this process */
149   exit(0);
150 }
151 
152 
153 
154 /* ------------------------- **
155 **      Local functions      **
156 ** ------------------------- */
157 
158 static
share_private_nodes(int worker_q)159 void share_private_nodes(int worker_q) {
160   int depth;
161   choiceptr AuxB;
162   or_fr_ptr or_frame, previous_or_frame;
163 
164   /* initialize auxiliary variables */
165   AuxB = B;
166   previous_or_frame = NULL;
167   depth = OrFr_depth(LOCAL_top_or_fr);
168   /* sharing loop */
169   while (AuxB != LOCAL_top_cp) {
170     depth++;
171     ALLOC_OR_FRAME(or_frame);
172     INIT_LOCK(OrFr_lock(or_frame));
173     SetOrFr_node(or_frame, AuxB);
174     OrFr_alternative(or_frame) = AuxB->cp_ap;
175     OrFr_pend_prune_cp(or_frame) = NULL;
176     OrFr_nearest_leftnode(or_frame) = LOCAL_top_or_fr;
177     OrFr_qg_solutions(or_frame) = NULL;
178     BITMAP_clear(OrFr_members(or_frame));
179     BITMAP_insert(OrFr_members(or_frame), worker_id);
180     BITMAP_insert(OrFr_members(or_frame), worker_q);
181     if (AuxB->cp_ap && YAMOP_SEQ(AuxB->cp_ap)) {
182       AuxB->cp_ap = GETWORK_SEQ;
183     } else {
184       AuxB->cp_ap = GETWORK;
185     }
186     AuxB->cp_or_fr = or_frame;
187     AuxB = AuxB->cp_b;
188     if (previous_or_frame) {
189       OrFr_nearest_livenode(previous_or_frame) = OrFr_next(previous_or_frame) = or_frame;
190     }
191     previous_or_frame = or_frame;
192   }
193   /* initialize last or-frame pointer */
194   or_frame = AuxB->cp_or_fr;
195   if (previous_or_frame) {
196     OrFr_nearest_livenode(previous_or_frame) = OrFr_next(previous_or_frame) = or_frame;
197   }
198   /* update depth */
199   if (depth >= MAX_BRANCH_DEPTH)
200     Yap_Error(INTERNAL_ERROR, TermNil, "maximum depth exceded (share_private_nodes)");
201   or_frame = B->cp_or_fr;
202   while (or_frame != LOCAL_top_or_fr) {
203     unsigned int branch;
204     if (OrFr_alternative(or_frame)) {
205       branch = YAMOP_OR_ARG(OrFr_alternative(or_frame)) + 1;
206     } else {
207       branch = 1;
208     }
209     branch |= YAMOP_CUT_FLAG;  /* in doubt, assume cut */
210     BRANCH(worker_id, depth) = BRANCH(worker_q, depth) = branch;
211     OrFr_depth(or_frame) = depth--;
212     or_frame = OrFr_next_on_stack(or_frame);
213   }
214   /* update old shared nodes */
215   while (or_frame != REMOTE_top_or_fr(worker_q)) {
216     LOCK_OR_FRAME(or_frame);
217     BRANCH(worker_q, OrFr_depth(or_frame)) = BRANCH(worker_id, OrFr_depth(or_frame));
218     BITMAP_insert(OrFr_members(or_frame), worker_q);
219     UNLOCK_OR_FRAME(or_frame);
220     or_frame = OrFr_next_on_stack(or_frame);
221   }
222   /* update top shared nodes */
223   REMOTE_top_cp(worker_q) = LOCAL_top_cp = B;
224   REMOTE_top_or_fr(worker_q) = LOCAL_top_or_fr = LOCAL_top_cp->cp_or_fr;
225   /* update prune request */
226   if (LOCAL_prune_request) {
227     CUT_send_prune_request(worker_q, LOCAL_prune_request);
228   }
229   /* update load and return */
230   REMOTE_load(worker_q) = LOCAL_load = 0;
231   return;
232 }
233 #endif /* ACOW */
234