Line data Source code
1 : /*
2 : START OF LICENSE STUB
3 : DeDOS: Declarative Dispersion-Oriented Software
4 : Copyright (C) 2017 University of Pennsylvania, Georgetown University
5 :
6 : This program is free software: you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation, either version 3 of the License, or
9 : (at your option) any later version.
10 :
11 : This program is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU 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, see <http://www.gnu.org/licenses/>.
18 : END OF LICENSE STUB
19 : */
20 : /**
21 : * @file dfg.c
22 : *
23 : * Code for the creation and modifcation of the data-flow graph
24 : */
25 : #include "dfg.h"
26 : #include "logging.h"
27 :
28 : #include <stdbool.h>
29 : #include <stdlib.h>
30 :
31 : /** Static local copy of the DFG, so each call doesn't have to pass a copy */
32 : static struct dedos_dfg *dfg;
33 :
34 0 : void set_dfg(struct dedos_dfg *dfg_in) {
35 0 : dfg = dfg_in;
36 0 : }
37 :
38 : /**
39 : * Convenience macro to search a field within a structure for the element with an ID.
40 : * Specifically, searches field[i]->id for each element in field.
41 : * @param s A parent structure. If NULL, returns NULL
42 : * @param n The number of elements in the field to search
43 : * @param field The list of structures to search for the given ID
44 : * @param id_ The ID to search for in the list of structures
45 : */
46 : #define SEARCH_FOR_ID(s, n, field, id_) \
47 : if (dfg == NULL) \
48 : return NULL; \
49 : for (int i=0; i<(n); ++i) { \
50 : if (field[i]->id == id_) { \
51 : return field[i]; \
52 : } \
53 : } \
54 : return NULL;
55 :
56 0 : struct db_info *get_db_info() {
57 0 : return &dfg->db;
58 : }
59 :
60 0 : int get_dfg_n_runtimes() {
61 0 : return dfg->n_runtimes;
62 : }
63 :
64 0 : struct dfg_runtime *get_dfg_runtime(unsigned int runtime_id) {
65 0 : SEARCH_FOR_ID(dfg, dfg->n_runtimes, dfg->runtimes, runtime_id);
66 : }
67 :
68 0 : struct dfg_msu_type *get_dfg_msu_type(unsigned int id){
69 0 : SEARCH_FOR_ID(dfg, dfg->n_msu_types, dfg->msu_types, id)
70 : }
71 :
72 0 : struct dfg_route *get_dfg_runtime_route(struct dfg_runtime *rt, unsigned int id) {
73 0 : SEARCH_FOR_ID(rt, rt->n_routes, rt->routes, id);
74 : }
75 :
76 0 : struct dfg_route *get_dfg_route(unsigned int id) {
77 0 : for (int i=0; i<dfg->n_runtimes; i++) {
78 0 : struct dfg_route *route = get_dfg_runtime_route(dfg->runtimes[i], id);
79 0 : if (route != NULL) {
80 0 : return route;
81 : }
82 : }
83 0 : return NULL;
84 : }
85 :
86 0 : struct dfg_msu *get_dfg_msu(unsigned int id){
87 0 : SEARCH_FOR_ID(dfg, dfg->n_msus, dfg->msus, id)
88 : }
89 :
90 0 : struct dfg_route *get_dfg_rt_route_by_type(struct dfg_runtime *rt, struct dfg_msu_type *type) {
91 0 : for (int i=0; i<rt->n_routes; i++) {
92 0 : if (rt->routes[i]->msu_type == type) {
93 0 : return rt->routes[i];
94 : }
95 : }
96 0 : return NULL;
97 : }
98 :
99 0 : struct dfg_route *get_dfg_msu_route_by_type(struct dfg_msu *msu, struct dfg_msu_type *route_type) {
100 0 : for (int i=0; i<msu->scheduling.n_routes; i++) {
101 0 : if (msu->scheduling.routes[i]->msu_type == route_type) {
102 0 : return msu->scheduling.routes[i];
103 : }
104 : }
105 0 : return NULL;
106 : }
107 :
108 0 : struct dfg_thread *get_dfg_thread(struct dfg_runtime *rt, unsigned int id){
109 0 : SEARCH_FOR_ID(rt, rt->n_pinned_threads + rt->n_unpinned_threads, rt->threads, id)
110 : }
111 :
112 0 : struct dfg_route_endpoint *get_dfg_route_endpoint(struct dfg_route *route, unsigned int msu_id) {
113 0 : for (int i=0; i<route->n_endpoints; i++) {
114 0 : if (route->endpoints[i]->msu->id == msu_id) {
115 0 : return route->endpoints[i];
116 : }
117 : }
118 0 : return NULL;
119 : }
120 :
121 0 : int msu_has_route(struct dfg_msu *msu, struct dfg_route *route) {
122 0 : for (int i=0; i<msu->scheduling.n_routes; i++) {
123 0 : if (msu->scheduling.routes[i] == route) {
124 0 : return 1;
125 : }
126 : }
127 0 : return 0;
128 : }
129 :
130 0 : struct dfg_msu *msu_type_on_runtime(struct dfg_runtime *rt, struct dfg_msu_type *type) {
131 0 : for (int i=0; i<type->n_instances; i++) {
132 0 : if (type->instances[i]->scheduling.runtime == rt) {
133 0 : return type->instances[i];
134 : }
135 : }
136 0 : return NULL;
137 : }
138 :
139 0 : enum thread_mode str_to_thread_mode(char *mode_str) {
140 0 : if (strcasecmp(mode_str, "pinned") == 0) {
141 0 : return PINNED_THREAD;
142 0 : } else if (strcasecmp(mode_str, "unpinned") == 0) {
143 0 : return UNPINNED_THREAD;
144 : } else {
145 0 : log_warn("Unknown thread mode: %s", mode_str);
146 0 : return UNSPECIFIED_THREAD_MODE;
147 : }
148 : }
149 :
150 0 : enum blocking_mode str_to_blocking_mode(char *mode_str) {
151 0 : if (strcasecmp(mode_str, "blocking") == 0) {
152 0 : return BLOCKING_MSU;
153 0 : } else if (strcasecmp(mode_str, "nonblocking") == 0 ||
154 0 : strcasecmp(mode_str, "non-blocking") == 0) {
155 0 : return NONBLOCK_MSU;
156 : } else {
157 0 : log_warn("Unknown blocking mode: %s", mode_str);
158 0 : return UNKNOWN_BLOCKING_MODE;
159 : }
160 : }
161 :
162 0 : uint8_t str_to_vertex_type(char *str_type) {
163 0 : uint8_t vertex_type = 0;
164 0 : if (strstr(str_type, "entry") != NULL) {
165 0 : vertex_type |= ENTRY_VERTEX_TYPE;
166 : }
167 0 : if (strstr(str_type, "exit") != NULL) {
168 0 : vertex_type |= EXIT_VERTEX_TYPE;
169 : }
170 0 : if (vertex_type == 0 && strstr(str_type, "nop") == NULL) {
171 0 : log_warn("Unknown vertex type %s specified (neither exit, entry, nop found)", str_type);
172 0 : return 0;
173 : }
174 0 : return vertex_type;
175 : }
176 :
177 : /**
178 : * Sets the non-scheduling properties of the MSU to be equal to those of the passed in target
179 : * @param template The MSU from which to copy the properties
180 : * @param target The MSU into which the properties are to be copied
181 : */
182 0 : static void set_msu_properties(struct dfg_msu *template, struct dfg_msu *target) {
183 0 : target->id = template->id;
184 0 : target->vertex_type = template->vertex_type;
185 0 : target->init_data = template->init_data;
186 0 : target->type = template->type;
187 0 : target->blocking_mode = template->blocking_mode;
188 0 : }
189 :
190 0 : struct dfg_msu *copy_dfg_msu(struct dfg_msu *input) {
191 0 : struct dfg_msu *msu = calloc(1, sizeof(*input));
192 0 : if (msu == NULL) {
193 0 : log_error("Error allocating dfg MSU");
194 0 : return NULL;
195 : }
196 0 : set_msu_properties(input, msu);
197 0 : return msu;
198 : }
199 :
200 0 : struct dfg_msu *init_dfg_msu(unsigned int id, struct dfg_msu_type *type, uint8_t vertex_type,
201 : enum blocking_mode mode, struct msu_init_data *init_data) {
202 :
203 0 : struct dfg_msu *msu = get_dfg_msu(id);
204 0 : if (msu != NULL) {
205 0 : log_error("MSU %u already exists and scheduled", id);
206 0 : return NULL;
207 : }
208 :
209 0 : msu = calloc(1, sizeof(*msu));
210 0 : if (msu == NULL) {
211 0 : log_error("Error allocating dfg MSU");
212 0 : return NULL;
213 : }
214 0 : struct dfg_msu template = {
215 : .id = id,
216 : .vertex_type = vertex_type,
217 : .init_data = *init_data,
218 : .type = type,
219 : .blocking_mode = mode
220 : };
221 0 : set_msu_properties(&template, msu);
222 0 : return msu;
223 : }
224 :
225 0 : int free_dfg_msu(struct dfg_msu *input) {
226 0 : if (input->scheduling.runtime != NULL || input->scheduling.thread != NULL) {
227 0 : log_error("Cannot free MSU that is still assigned to thread or runtime");
228 0 : return -1;
229 : }
230 0 : free(input);
231 0 : return 0;
232 : }
233 :
234 : /**
235 : * Adds the MSU to the thread, runtime, and instance, and adds the thread and runtime to the MSU
236 : */
237 0 : static int schedule_msu_on_thread(struct dfg_msu *msu, struct dfg_thread *thread,
238 : struct dfg_runtime *rt) {
239 0 : if (thread->n_msus == MAX_MSU_PER_THREAD) {
240 0 : log_error("Too many MSUs on thread %d", thread->id);
241 0 : return -1;
242 : }
243 0 : if (dfg->n_msus == MAX_MSU) {
244 0 : log_error("Too many MSUs in DFG");
245 0 : return -1;
246 : }
247 0 : dfg->msus[dfg->n_msus] = msu;
248 0 : dfg->n_msus++;
249 :
250 0 : thread->msus[thread->n_msus] = msu;
251 0 : thread->n_msus++;
252 :
253 0 : msu->type->instances[msu->type->n_instances] = msu;
254 0 : msu->type->n_instances++;
255 :
256 0 : msu->scheduling.thread = thread;
257 0 : msu->scheduling.runtime = rt;
258 0 : return 0;
259 : }
260 :
261 0 : int schedule_dfg_msu(struct dfg_msu *msu, unsigned int runtime_id, unsigned int thread_id) {
262 0 : if (dfg == NULL) {
263 0 : log_error("DFG not instantiated");
264 0 : return -1;
265 : }
266 :
267 0 : if (msu->scheduling.runtime != NULL || msu->scheduling.thread != NULL) {
268 0 : log_error("MSU already scheduled");
269 0 : return -1;
270 : }
271 :
272 0 : struct dfg_runtime *rt = get_dfg_runtime(runtime_id);
273 0 : if (rt == NULL) {
274 0 : log_error("Runtime id %u not instantiated", runtime_id);
275 0 : return -1;
276 : }
277 0 : struct dfg_thread *thread = get_dfg_thread(rt, thread_id);
278 0 : if (thread == NULL) {
279 0 : log_error("Thread id %u not instantiated on runtime %u", thread_id, runtime_id);
280 0 : return -1;
281 : }
282 :
283 0 : int rtn = schedule_msu_on_thread(msu, thread, rt);
284 0 : if (rtn < 0) {
285 0 : log_error("Error scheduling MSU on thread");
286 0 : return -1;
287 : }
288 :
289 0 : log_info("TEST");
290 : log(LOG_DFG, "Scheduled DFG msu %d", msu->id);
291 0 : return 0;
292 : }
293 :
294 : /**
295 : * Removes the msu from it's thread, runtime, and instance,
296 : * and removes the thread and runtime from the MSU
297 : */
298 0 : static int remove_msu_from_thread(struct dfg_msu *msu) {
299 0 : struct dfg_thread *thread = msu->scheduling.thread;
300 : int ti;
301 0 : for (ti=0; ti<thread->n_msus && thread->msus[ti] != msu; ti++){}
302 0 : if (ti == thread->n_msus) {
303 0 : log_error("MSU %d does not exist on thread %d", msu->id, thread->id);
304 0 : return -1;
305 : }
306 : int di;
307 0 : for (di = 0; di < dfg->n_msus && dfg->msus[di] != msu; di++){}
308 0 : if (di == dfg->n_msus) {
309 0 : log_critical("Cannot find MSU %d in DFG!", msu->id);
310 0 : return -1;
311 : }
312 : int ii;
313 0 : for (ii = 0; ii < msu->type->n_instances && msu->type->instances[ii] != msu; ii++) {}
314 0 : if (ii == msu->type->n_instances) {
315 0 : log_error("Cannot find MSU %d in list of instances of %s", msu->id, msu->type->name);
316 0 : return -1;
317 : }
318 :
319 0 : for (int i=ti; i < thread->n_msus - 1; i++) {
320 0 : thread->msus[i] = thread->msus[i+1];
321 : }
322 0 : thread->n_msus--;
323 :
324 0 : for (int i=di; i < dfg->n_msus - 1; i++) {
325 0 : dfg->msus[i] = dfg->msus[i+1];
326 : }
327 0 : dfg->n_msus--;
328 :
329 0 : for (int i=ii; i < msu->type->n_instances - 1; i++) {
330 0 : msu->type->instances[i] = msu->type->instances[i+1];
331 : }
332 0 : msu->type->n_instances--;
333 :
334 0 : msu->scheduling.runtime = NULL;
335 0 : msu->scheduling.thread = NULL;
336 0 : return 0;
337 : }
338 :
339 0 : int unschedule_dfg_msu(struct dfg_msu *msu) {
340 0 : if (dfg == NULL) {
341 0 : log_error("DFG not instantiated");
342 0 : return -1;
343 : }
344 :
345 0 : if (msu->scheduling.runtime == NULL || msu->scheduling.thread == NULL) {
346 0 : log_error("MSU not scheduled");
347 0 : return -1;
348 : }
349 :
350 0 : for (int i=0; i<dfg->n_runtimes; i++) {
351 0 : struct dfg_runtime *rt = dfg->runtimes[i];
352 0 : for (int j=0; j<rt->n_routes; j++) {
353 0 : struct dfg_route *route = rt->routes[j];
354 0 : if (get_dfg_route_endpoint(route, msu->id) != NULL) {
355 0 : log_error("MSU %d Cannot be unscheduled: referenced by route %d",
356 : msu->id, route->id);
357 0 : return -1;
358 : }
359 : }
360 : }
361 :
362 : log(LOG_DFG, "Unscheduled DFG msu %d", msu->id);
363 0 : return remove_msu_from_thread(msu);
364 : }
365 :
366 0 : struct dfg_route *create_dfg_route(unsigned int id, struct dfg_msu_type *type,
367 : unsigned int runtime_id) {
368 0 : struct dfg_route *route = get_dfg_route(id);
369 0 : if (route != NULL) {
370 0 : log_error("DFG route %u already exists", id);
371 0 : return NULL;
372 : }
373 0 : struct dfg_runtime *rt = get_dfg_runtime(runtime_id);
374 0 : if (rt == NULL) {
375 0 : log_error("Runtime %u does not exist in DFG", runtime_id);
376 0 : return NULL;
377 : }
378 0 : if (rt->n_routes == MAX_ROUTES) {
379 0 : log_error("Cannot fit more routes on runtime %u", runtime_id);
380 0 : return NULL;
381 : }
382 :
383 0 : route = calloc(1, sizeof(*route));
384 0 : if (route == NULL) {
385 0 : log_error("Could not allocate DFG route %u", id);
386 0 : return NULL;
387 : }
388 :
389 0 : route->id = id;
390 0 : route->msu_type = type;
391 0 : route->runtime = rt;
392 : // TODO: Add runtime to route in dfg_reader
393 :
394 0 : rt->routes[rt->n_routes] = route;
395 0 : rt->n_routes++;
396 0 : return route;
397 : }
398 :
399 0 : int delete_dfg_route(struct dfg_route *route) {
400 0 : for (int i=0; i<dfg->n_msus; i++) {
401 0 : struct dfg_msu *msu = dfg->msus[i];
402 0 : for (int j=0; j<msu->scheduling.n_routes; j++) {
403 0 : if (msu->scheduling.routes[i] == route) {
404 0 : log_error("Cannot delete route %d while it is still attached to msu %d",
405 : route->id, msu->id);
406 0 : return -1;
407 : }
408 : }
409 : }
410 :
411 0 : struct dfg_runtime *rt = route->runtime;
412 :
413 : int i;
414 : // Find the index of the route in the runtime
415 0 : for (i=0; i<rt->n_routes && rt->routes[i] != route; i++);
416 0 : if (i == rt->n_routes) {
417 0 : log_error("Could not find route in runtime");
418 0 : return -1;
419 : }
420 0 : for (; i<rt->n_routes-1; i++) {
421 0 : rt->routes[i] = rt->routes[i+1];
422 : }
423 0 : rt->n_routes--;
424 0 : return 0;
425 : }
426 :
427 :
428 0 : int add_dfg_route_to_msu(struct dfg_route *route, struct dfg_msu *msu) {
429 0 : if (msu->scheduling.runtime != route->runtime) {
430 0 : log_error("Cannot add route on runtime %d to msu on runtime %d",
431 : route->runtime->id, msu->scheduling.runtime->id);
432 0 : return -1;
433 : }
434 0 : for (int i=0; i<msu->scheduling.n_routes; i++) {
435 0 : if (msu->scheduling.routes[i]->msu_type == route->msu_type) {
436 0 : log_error("Route with type %d already exists in MSU %d",
437 : route->msu_type->id, msu->id);
438 0 : return -1;
439 : }
440 : }
441 :
442 0 : if (route->n_endpoints == 0) {
443 0 : log_warn("Route with no destinations added to an MSU! "
444 : "(Route: %d, msu: %d) "
445 : "This could have unfortunate results!",
446 : (int)route->id, (int)msu->id);
447 : }
448 :
449 0 : msu->scheduling.routes[msu->scheduling.n_routes] = route;
450 0 : msu->scheduling.n_routes++;
451 0 : return 0;
452 : }
453 :
454 :
455 0 : struct dfg_route_endpoint *add_dfg_route_endpoint(struct dfg_msu *msu, uint32_t key,
456 : struct dfg_route *route) {
457 0 : if (route->n_endpoints == MAX_ROUTE_ENDPOINTS) {
458 0 : log_error("Cannot add more MSUs to route %d", route->id);
459 0 : return NULL;
460 : }
461 0 : if (route->msu_type != msu->type) {
462 0 : log_error("Cannot add MSU of type %d to route of type %d",
463 : msu->type->id, route->msu_type->id);
464 0 : return NULL;
465 : }
466 :
467 0 : struct dfg_route_endpoint *dest = malloc(sizeof(*dest));
468 0 : if (dest == NULL) {
469 0 : log_perror("Error allocating route destination");
470 0 : return NULL;
471 : }
472 0 : dest->msu = msu;
473 0 : dest->key = key;
474 :
475 : int i;
476 : // Insert the endpoint in the correct place (ascending keys)
477 0 : for (i=0; i<route->n_endpoints && route->endpoints[i]->key < key; i++);
478 0 : for (int j=route->n_endpoints; j>i; j--) {
479 0 : route->endpoints[j] = route->endpoints[j-1];
480 : }
481 0 : route->endpoints[i] = dest;
482 0 : route->n_endpoints++;
483 :
484 0 : return dest;
485 : }
486 :
487 0 : int del_dfg_route_endpoint(struct dfg_route *route, struct dfg_route_endpoint *ep) {
488 : int i;
489 : // Search for endpoint index
490 0 : for (i=0; i<route->n_endpoints && route->endpoints[i] != ep; i++);
491 :
492 0 : if (i == route->n_endpoints) {
493 0 : log_error("Could not find endpoint in route");
494 0 : return -1;
495 : }
496 :
497 0 : for (; i<route->n_endpoints-1; i++) {
498 0 : route->endpoints[i] = route->endpoints[i+1];
499 : }
500 0 : route->n_endpoints--;
501 : log(LOG_ROUTING_CHANGES, "Route %d now has %d endpoints", route->id, route->n_endpoints);
502 0 : return 0;
503 : }
504 :
505 0 : int mod_dfg_route_endpoint(struct dfg_route *route, struct dfg_route_endpoint *ep,
506 : uint32_t new_key) {
507 : // This is all so the keys remain in ascending order
508 :
509 : // Find where the endpoint used to be
510 : int old;
511 0 : for (old=0; old<route->n_endpoints && route->endpoints[old] != ep; old++);
512 0 : if (old == route->n_endpoints) {
513 0 : log_error("Could not find endpoint in route");
514 0 : return -1;
515 : }
516 : // Find where it should now be
517 : int new;
518 0 : for (new=0; new<route->n_endpoints && route->endpoints[new]->key < new_key; new++);
519 :
520 : // Which direction are we moving the in-between endpoints
521 0 : int delta = new > old ? 1 : -1;
522 : // If we're deleting from below the new location, subtract one to the new location
523 0 : if (delta == 1) {
524 0 : new -= 1;
525 : }
526 :
527 : // Iterate from the old to the new location, moving the endpoints in the other direction
528 0 : for (int i=old; delta * i < delta * new; i += delta) {
529 0 : route->endpoints[i] = route->endpoints[i + delta];
530 : }
531 :
532 :
533 : // Replace the new endpoint
534 0 : ep->key = new_key;
535 0 : route->endpoints[new] = ep;
536 0 : return 0;
537 : }
538 :
539 0 : struct dfg_thread * create_dfg_thread(struct dfg_runtime *rt, int thread_id,
540 : enum thread_mode mode) {
541 0 : if (mode == UNSPECIFIED_THREAD_MODE) {
542 0 : log_error("Cannot add unspecified-thread-mode thread");
543 0 : return NULL;
544 : }
545 0 : if (rt->n_pinned_threads + rt->n_unpinned_threads == MAX_THREADS) {
546 0 : log_error("Cannot add more threads to runtime %d", rt->id);
547 0 : return NULL;
548 : }
549 :
550 0 : struct dfg_thread *thread = calloc(1, sizeof(*thread));
551 0 : if (thread == NULL) {
552 0 : log_error("Could not allocate thread");
553 0 : return NULL;
554 : }
555 0 : thread->id = thread_id;
556 0 : thread->mode = mode;
557 :
558 0 : rt->threads[rt->n_pinned_threads + rt->n_unpinned_threads] = thread;
559 0 : switch(mode) {
560 : case PINNED_THREAD:
561 0 : rt->n_pinned_threads++;
562 0 : break;
563 : case UNPINNED_THREAD:
564 0 : rt->n_unpinned_threads++;
565 0 : break;
566 : default:
567 0 : log_error("Unknown thread mode %d provided", mode);
568 0 : return NULL;
569 : }
570 0 : return thread;
571 : }
572 :
573 : /** Frees elements in the MSU type structure */
574 0 : static void free_dfg_msu_type(struct dfg_msu_type *type) {
575 0 : for (int i=0; i<type->n_dependencies; i++) {
576 0 : free(type->dependencies[i]);
577 : }
578 0 : free(type);
579 0 : }
580 :
581 : /** Frees the runtime and all threads and routes associated with it */
582 0 : static void free_dfg_runtime(struct dfg_runtime *rt) {
583 0 : for (int i=0; i < rt->n_pinned_threads + rt->n_unpinned_threads; i++) {
584 0 : free(rt->threads[i]);
585 : }
586 0 : for (int i=0; i < rt->n_routes; i++) {
587 0 : for (int j=0; j < rt->routes[i]->n_endpoints; j++) {
588 0 : free(rt->routes[i]->endpoints[j]);
589 : }
590 0 : free(rt->routes[i]);
591 : }
592 0 : free(rt);
593 0 : }
594 :
595 :
596 0 : void free_dfg(struct dedos_dfg *dfg) {
597 0 : for (int i=0; i < dfg->n_msu_types; i++) {
598 0 : free_dfg_msu_type(dfg->msu_types[i]);
599 : }
600 0 : for (int i=0; i < dfg->n_msus; i++) {
601 0 : free(dfg->msus[i]);
602 : }
603 0 : for (int i=0; i < dfg->n_runtimes; i++) {
604 0 : free_dfg_runtime(dfg->runtimes[i]);
605 : }
606 0 : free(dfg);
607 0 : }
|
