2 * Copyright (c) 2008, 2009, 2010 Zmanda, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 as published
6 * by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
10 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * You should have received a copy of the GNU General Public License along
14 * with this program; if not, write to the Free Software Foundation, Inc.,
15 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 * Contact information: Zmanda Inc., 465 S. Mathilda Ave., Suite 300
18 * Sunnyvale, CA 94085, USA, or: http://www.zmanda.com
23 #include "element-glue.h"
26 /* XMsgSource objects are GSource "subclasses" which manage
27 * a queue of messages, delivering those messages via callback
28 * in the mainloop. Messages can be *sent* from any thread without
29 * any concern for locking, but must only be received in the main
30 * thread, in the default GMainContext.
32 * An XMsgSource pointer can be cast to a GSource pointer as
35 typedef struct XMsgSource {
36 GSource source; /* must be the first element of the struct */
40 /* forward prototypes */
41 static void xfer_set_status(Xfer *xfer, xfer_status status);
42 static XMsgSource *xmsgsource_new(Xfer *xfer);
43 static void link_elements(Xfer *xfer);
47 XferElement **elements,
48 unsigned int nelements)
50 Xfer *xfer = g_new0(Xfer, 1);
54 g_assert(nelements >= 2);
56 xfer->status = XFER_INIT;
57 xfer->status_mutex = g_mutex_new();
58 xfer->status_cond = g_cond_new();
59 xfer->fd_mutex = g_mutex_new();
64 /* Create our message source and corresponding queue */
65 xfer->msg_source = xmsgsource_new(xfer);
66 xfer->queue = g_async_queue_new();
68 /* copy the elements in, verifying that they're all XferElement objects */
69 xfer->elements = g_ptr_array_sized_new(nelements);
70 for (i = 0; i < nelements; i++) {
71 g_assert(elements[i] != NULL);
72 g_assert(IS_XFER_ELEMENT(elements[i]));
73 g_assert(elements[i]->xfer == NULL);
75 g_ptr_array_add(xfer->elements, (gpointer)elements[i]);
77 g_object_ref(elements[i]);
78 elements[i]->xfer = xfer;
98 if (!xfer) return; /* be friendly to NULLs */
100 if (--xfer->refcount > 0) return;
102 g_assert(xfer != NULL);
103 g_assert(xfer->status == XFER_INIT || xfer->status == XFER_DONE);
105 /* Divorce ourselves from the message source */
106 xfer->msg_source->xfer = NULL;
107 g_source_unref((GSource *)xfer->msg_source);
108 xfer->msg_source = NULL;
110 /* Try to empty the message queue */
111 while ((msg = (XMsg *)g_async_queue_try_pop(xfer->queue))) {
112 g_warning("Dropping XMsg from %s because the XMsgSource is being destroyed",
113 xfer_element_repr(msg->elt));
116 g_async_queue_unref(xfer->queue);
118 g_mutex_free(xfer->status_mutex);
119 g_cond_free(xfer->status_cond);
120 g_mutex_free(xfer->fd_mutex);
122 /* Free our references to the elements, and also set the 'xfer'
123 * attribute of each to NULL, making them "unattached" (although
124 * subsequent reuse of elements is untested). */
125 for (i = 0; i < xfer->elements->len; i++) {
126 XferElement *elt = (XferElement *)g_ptr_array_index(xfer->elements, i);
131 g_ptr_array_free(xfer->elements, TRUE);
143 return (GSource *)xfer->msg_source;
151 g_assert(xfer != NULL);
152 g_assert(msg != NULL);
154 g_async_queue_push(xfer->queue, (gpointer)msg);
156 /* TODO: don't do this if we're in the main thread */
157 g_main_context_wakeup(NULL);
167 xfer->repr = newvstrallocf(xfer->repr, "<Xfer@%p (", xfer);
168 for (i = 0; i < xfer->elements->len; i++) {
169 XferElement *elt = (XferElement *)g_ptr_array_index(xfer->elements, i);
170 xfer->repr = newvstralloc(xfer->repr,
171 xfer->repr, (i==0)?"":" -> ", xfer_element_repr(elt), NULL);
173 xfer->repr = newvstralloc(xfer->repr, xfer->repr, ")>", NULL);
187 g_assert(xfer != NULL);
188 g_assert(xfer->status == XFER_INIT);
189 g_assert(xfer->elements->len >= 2);
191 g_debug("Starting %s", xfer_repr(xfer));
192 /* set the status to XFER_START and add a reference to our count, so that
193 * we are not freed while still in operation. We'll drop this reference
194 * when the status becomes XFER_DONE. */
196 xfer->num_active_elements = 0;
197 xfer_set_status(xfer, XFER_START);
199 /* Link the elements. This calls error() on failure, and rewrites
203 /* Tell all elements to set up. This is done before upstream and downstream
204 * are set so that elements cannot interfere with one another before setup()
207 for (i = 0; i < xfer->elements->len; i++) {
208 XferElement *xe = (XferElement *)g_ptr_array_index(xfer->elements, i);
209 if (!xfer_element_setup(xe)) {
215 /* If setup_ok is false, then there is an XMSG_CANCEL in the message queue
216 * already, so skip calling start for any of the elements and send an
217 * XMSG_DONE, since none of the elements will do so. */
220 /* Set the upstream and downstream links between elements */
221 len = xfer->elements->len;
222 for (i = 0; i < len; i++) {
223 XferElement *elt = g_ptr_array_index(xfer->elements, i);
226 elt->upstream = g_ptr_array_index(xfer->elements, i-1);
228 elt->downstream = g_ptr_array_index(xfer->elements, i+1);
231 /* now tell them all to start, in order from destination to source */
232 for (i = xfer->elements->len; i >= 1; i--) {
233 XferElement *xe = (XferElement *)g_ptr_array_index(xfer->elements, i-1);
234 if (xfer_element_start(xe))
235 xfer->num_active_elements++;
239 /* (note that status can only change in the main thread, so we can be
240 * certain that the status is still XFER_START and we have not yet been
241 * cancelled. We may have an XMSG_CANCEL already queued up for us, though) */
242 xfer_set_status(xfer, XFER_RUNNING);
244 /* If this transfer involves no active processing, then we consider it to
245 * be done already. We send a "fake" XMSG_DONE from the destination element,
246 * so that all of the usual processing will take place. */
247 if (xfer->num_active_elements == 0) {
249 g_debug("%s has no active elements; generating fake XMSG_DONE", xfer_repr(xfer));
250 xfer->num_active_elements++;
251 xfer_queue_message(xfer,
252 xmsg_new((XferElement *)g_ptr_array_index(xfer->elements, xfer->elements->len-1),
261 /* Since xfer_cancel can be called from any thread, we just send a message.
262 * The action takes place when the message is received. */
263 XferElement *src = g_ptr_array_index(xfer->elements, 0);
264 xfer_queue_message(xfer, xmsg_new(src, XMSG_CANCEL, 0));
272 if (xfer->status == status) return;
274 g_mutex_lock(xfer->status_mutex);
276 /* check that this state transition is valid */
279 g_assert(xfer->status == XFER_INIT);
282 g_assert(xfer->status == XFER_START);
284 case XFER_CANCELLING:
285 g_assert(xfer->status == XFER_RUNNING);
288 g_assert(xfer->status == XFER_CANCELLING);
291 g_assert(xfer->status == XFER_CANCELLED || xfer->status == XFER_RUNNING);
295 g_assert_not_reached();
298 xfer->status = status;
299 g_cond_broadcast(xfer->status_cond);
300 g_mutex_unlock(xfer->status_mutex);
307 /* How is ELT linked? link_recurse uses an array of these to track its progress
308 * and find the optimal overall linkage. */
309 typedef struct linkage {
311 xfer_element_mech_pair_t *mech_pairs;
312 int elt_idx; /* index into elt's mech_pairs */
313 int glue_idx; /* index into glue pairs for elt's output; -1 = no glue */
316 /* Overall state of the recursive linking process */
317 typedef struct linking_state {
318 int nlinks; /* number of linkage objects in each array */
319 linkage *cur; /* "current" linkage */
321 linkage *best; /* best linkage so far */
322 gint32 best_cost; /* cost for best */
325 /* used for debugging messages */
331 case XFER_MECH_NONE: return "NONE";
332 case XFER_MECH_READFD: return "READFD";
333 case XFER_MECH_WRITEFD: return "WRITEFD";
334 case XFER_MECH_PULL_BUFFER: return "PULL_BUFFER";
335 case XFER_MECH_PUSH_BUFFER: return "PUSH_BUFFER";
336 case XFER_MECH_DIRECTTCP_LISTEN: return "DIRECTTCP_LISTEN";
337 case XFER_MECH_DIRECTTCP_CONNECT: return "DIRECTTCP_CONNECT";
338 default: return "UNKNOWN";
342 /* calculate an integer representing the cost of a mech pair as a
343 * single integer. OPS_PER_BYTE is the most important metric,
344 * followed by NTHREADS.
346 * PAIR will be evaluated multiple times.
348 #define PAIR_COST(pair) (((pair).ops_per_byte << 8) + (pair).nthreads)
351 #define MAX_COST 0xffffff
353 /* Generate all possible linkages of elements [idx:nlinks], where
354 * elements [0:idx-1] have cost 'cost' and end with mechanism
360 xfer_mech input_mech,
363 xfer_element_mech_pair_t *elt_pairs, *glue_pairs;
366 /* if we've overrun the previous best cost already, then bail out */
367 if (cost >= st->best_cost)
370 /* have we linked everything? */
371 if (idx == st->nlinks) {
372 /* if we ended on other than XFER_MECH_NONE, then this is not a
374 if (input_mech != XFER_MECH_NONE) return;
376 /* we already know this has lower cost than the previous best */
377 memcpy(st->best, st->cur, st->nlinks * sizeof(linkage));
378 st->best_cost = cost;
383 /* recurse for each linkage we can make that starts with input_mech */
385 elt_pairs = my->mech_pairs;
386 glue_pairs = xfer_element_glue_mech_pairs;
388 for (my->elt_idx = 0;
389 elt_pairs[my->elt_idx].input_mech != XFER_MECH_NONE
390 || elt_pairs[my->elt_idx].output_mech != XFER_MECH_NONE;
392 /* reject this pair if the input mech does not match */
393 if (elt_pairs[my->elt_idx].input_mech != input_mech)
396 /* recurse with no glue */
398 link_recurse(st, idx+1,
399 elt_pairs[my->elt_idx].output_mech,
400 cost + PAIR_COST(elt_pairs[my->elt_idx]));
402 /* and recurse with glue */
403 for (my->glue_idx = 0;
404 glue_pairs[my->glue_idx].input_mech != XFER_MECH_NONE
405 || glue_pairs[my->glue_idx].output_mech != XFER_MECH_NONE;
407 /* reject this glue pair if it doesn't match with the element output */
408 if (glue_pairs[my->glue_idx].input_mech != elt_pairs[my->elt_idx].output_mech)
411 /* and recurse with the glue */
412 link_recurse(st, idx+1,
413 glue_pairs[my->glue_idx].output_mech,
414 cost + PAIR_COST(elt_pairs[my->elt_idx])
415 + PAIR_COST(glue_pairs[my->glue_idx]));
424 GPtrArray *new_elements;
430 /* Note that this algorithm's running time is polynomial in the length of
431 * the transfer, with a fairly high order. If Amanda is regularly assembling
432 * transfers with more than, say, 6 elements, then the algorithm should be
435 /* set up the state for recursion */
436 st.nlinks = xfer->elements->len;
437 st.cur = g_new0(linkage, st.nlinks);
438 st.best = g_new0(linkage, st.nlinks);
439 st.best_cost = MAX_COST;
440 for (i = 0; i < st.nlinks; i++) {
441 st.cur[i].elt = (XferElement *)g_ptr_array_index(xfer->elements, i);
442 st.cur[i].mech_pairs = xfer_element_get_mech_pairs(st.cur[i].elt);
445 /* check that the first element is an XferSource and the last is an XferDest.
446 * A source is identified by having no input mechanisms. */
447 if (st.cur[0].mech_pairs[0].input_mech != XFER_MECH_NONE)
448 error("Transfer element 0 is not a transfer source");
450 /* Similarly, a destination has no output mechanisms. */
451 if (st.cur[st.nlinks-1].mech_pairs[0].output_mech != XFER_MECH_NONE)
452 error("Last transfer element is not a transfer destination");
454 /* start recursing with the first element, asserting that its input mech is NONE */
455 link_recurse(&st, 0, XFER_MECH_NONE, 0);
457 /* check that we got *some* solution */
458 if (st.best_cost == MAX_COST) {
459 error(_("Xfer %s cannot be linked."), xfer_repr(xfer));
462 /* Now create a new list of elements, containing any glue elements
463 * that we need to add, and set their input_mech and output_mech fields */
464 new_elements = g_ptr_array_sized_new(xfer->elements->len);
465 for (i = 0; i < st.nlinks; i++) {
466 elt = st.best[i].elt;
467 elt->input_mech = st.best[i].mech_pairs[st.best[i].elt_idx].input_mech;
468 elt->output_mech = st.best[i].mech_pairs[st.best[i].elt_idx].output_mech;
469 g_ptr_array_add(new_elements, elt);
471 if (st.best[i].glue_idx != -1) {
472 elt = xfer_element_glue();
474 elt->input_mech = xfer_element_glue_mech_pairs[st.best[i].glue_idx].input_mech;
475 elt->output_mech = xfer_element_glue_mech_pairs[st.best[i].glue_idx].output_mech;
476 g_ptr_array_add(new_elements, elt);
480 /* install the new list of elements */
481 g_ptr_array_free(xfer->elements, FALSE);
482 xfer->elements = new_elements;
485 /* debug-log the xfer's linkage */
486 len = xfer->elements->len;
487 linkage_str = stralloc("Final linkage: ");
488 for (i = 0; i < len; i++) {
489 XferElement *elt = g_ptr_array_index(xfer->elements, i);
492 linkage_str = newvstralloc(linkage_str, linkage_str, xfer_element_repr(elt), NULL);
494 linkage_str = newvstrallocf(linkage_str, "%s -(%s)-> %s",
495 linkage_str, xfer_mech_name(elt->input_mech), xfer_element_repr(elt));
497 g_debug("%s", linkage_str);
513 XMsgSource *xms = (XMsgSource *)source;
516 return xms->xfer && g_async_queue_length(xms->xfer->queue) > 0;
523 XMsgSource *xms = (XMsgSource *)source;
525 return xms->xfer && g_async_queue_length(xms->xfer->queue) > 0;
530 GSource *source G_GNUC_UNUSED,
531 GSourceFunc callback,
534 XMsgSource *xms = (XMsgSource *)source;
535 Xfer *xfer = xms->xfer;
536 XMsgCallback my_cb = (XMsgCallback)callback;
538 gboolean deliver_to_caller;
540 gboolean xfer_done = FALSE;
542 /* we're potentially calling Perl code within this loop, so we have to
543 * check that everything is ok on each iteration of the loop. */
545 && xfer->status != XFER_DONE
546 && (msg = (XMsg *)g_async_queue_try_pop(xfer->queue))) {
548 /* We get first crack at interpreting messages, before calling the
549 * designated callback. */
550 deliver_to_caller = TRUE;
552 /* Intercept and count DONE messages so that we can determine when
553 * the entire transfer is finished. */
555 if (--xfer->num_active_elements <= 0) {
556 /* mark the transfer as done, and take a note to break out
557 * of this loop after delivering the message to the user */
558 xfer_set_status(xfer, XFER_DONE);
561 /* eat this XMSG_DONE, since we expect more */
562 deliver_to_caller = FALSE;
567 if (xfer->status == XFER_CANCELLING || xfer->status == XFER_CANCELLED) {
568 /* ignore duplicate cancel messages */
569 deliver_to_caller = FALSE;
571 /* call cancel() on each child element */
574 g_debug("Cancelling %s", xfer_repr(xfer));
575 xfer_set_status(xfer, XFER_CANCELLING);
578 for (i = 0; i < xfer->elements->len; i++) {
579 XferElement *elt = (XferElement *)
580 g_ptr_array_index(xfer->elements, i);
581 expect_eof = xfer_element_cancel(elt, expect_eof) || expect_eof;
584 /* if nothing in the transfer can generate an EOF, then we
585 * can't cancel this transfer, and we'll just have to wait
586 * until it's finished. This may happen, for example, if
587 * the operating system is copying data for us
590 g_warning("Transfer %s cannot be cancelled.", xfer_repr(xfer));
592 /* and now we're done cancelling */
593 xfer_set_status(xfer, XFER_CANCELLED);
598 break; /* nothing interesting to do */
601 if (deliver_to_caller) {
603 my_cb(user_data, msg, xfer);
605 g_warning("Dropping %s because no callback is set", xmsg_repr(msg));
611 /* This transfer is done, so kill it and exit the loop */
619 /* Never automatically un-queue the event source */
627 static GSourceFuncs *xmsgsource_funcs = NULL;
631 /* initialize these here to avoid a compiler warning */
632 if (!xmsgsource_funcs) {
633 xmsgsource_funcs = g_new0(GSourceFuncs, 1);
634 xmsgsource_funcs->prepare = xmsgsource_prepare;
635 xmsgsource_funcs->check = xmsgsource_check;
636 xmsgsource_funcs->dispatch = xmsgsource_dispatch;
639 src = g_source_new(xmsgsource_funcs, sizeof(XMsgSource));
640 xms = (XMsgSource *)src;
647 wait_until_xfer_cancelled(
650 xfer_status seen_status;
651 g_assert(xfer != NULL);
653 g_mutex_lock(xfer->status_mutex);
654 while (xfer->status != XFER_CANCELLED && xfer->status != XFER_DONE)
655 g_cond_wait(xfer->status_cond, xfer->status_mutex);
656 seen_status = xfer->status;
657 g_mutex_unlock(xfer->status_mutex);
663 wait_until_xfer_running(
666 xfer_status seen_status;
667 g_assert(xfer != NULL);
669 g_mutex_lock(xfer->status_mutex);
670 while (xfer->status == XFER_START)
671 g_cond_wait(xfer->status_cond, xfer->status_mutex);
672 seen_status = xfer->status;
673 g_mutex_unlock(xfer->status_mutex);
679 xfer_cancel_with_error(
687 g_assert(elt != NULL);
688 g_assert(elt->xfer != NULL);
690 msg = xmsg_new(elt, XMSG_ERROR, 0);
692 arglist_start(argp, fmt);
693 msg->message = g_strdup_vprintf(fmt, argp);
696 /* send the XMSG_ERROR */
697 xfer_queue_message(elt->xfer, msg);
699 /* cancel the transfer */
700 xfer_cancel(elt->xfer);
704 xfer_atomic_swap_fd(Xfer *xfer, gint *fdp, gint newfd)
709 g_mutex_lock(xfer->fd_mutex);
713 g_mutex_unlock(xfer->fd_mutex);