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);
182 gint64 offset G_GNUC_UNUSED,
189 g_assert(xfer != NULL);
190 g_assert(xfer->status == XFER_INIT);
191 g_assert(xfer->elements->len >= 2);
192 g_assert(offset == 0);
194 g_debug("Starting %s", xfer_repr(xfer));
195 /* set the status to XFER_START and add a reference to our count, so that
196 * we are not freed while still in operation. We'll drop this reference
197 * when the status becomes XFER_DONE. */
199 xfer->num_active_elements = 0;
200 xfer_set_status(xfer, XFER_START);
202 /* Link the elements. This calls error() on failure, and rewrites
206 /* Tell all elements to set up. This is done before upstream and downstream
207 * are set so that elements cannot interfere with one another before setup()
210 for (i = 0; i < xfer->elements->len; i++) {
211 XferElement *xe = (XferElement *)g_ptr_array_index(xfer->elements, i);
212 if (!xfer_element_setup(xe)) {
218 /* If setup_ok is false, then there is an XMSG_CANCEL in the message queue
219 * already, so skip calling start for any of the elements and send an
220 * XMSG_DONE, since none of the elements will do so. */
223 /* Set the upstream and downstream links between elements */
224 len = xfer->elements->len;
225 for (i = 0; i < len; i++) {
226 XferElement *elt = g_ptr_array_index(xfer->elements, i);
229 elt->upstream = g_ptr_array_index(xfer->elements, i-1);
231 elt->downstream = g_ptr_array_index(xfer->elements, i+1);
234 /* Set size for first element */
236 XferElement *xe = (XferElement *)g_ptr_array_index(xfer->elements, 0);
237 xfer_element_set_size(xe, size);
240 /* now tell them all to start, in order from destination to source */
241 for (i = xfer->elements->len; i >= 1; i--) {
242 XferElement *xe = (XferElement *)g_ptr_array_index(xfer->elements, i-1);
243 if (xfer_element_start(xe))
244 xfer->num_active_elements++;
248 /* (note that status can only change in the main thread, so we can be
249 * certain that the status is still XFER_START and we have not yet been
250 * cancelled. We may have an XMSG_CANCEL already queued up for us, though) */
251 xfer_set_status(xfer, XFER_RUNNING);
253 /* If this transfer involves no active processing, then we consider it to
254 * be done already. We send a "fake" XMSG_DONE from the destination element,
255 * so that all of the usual processing will take place. */
256 if (xfer->num_active_elements == 0) {
258 g_debug("%s has no active elements; generating fake XMSG_DONE", xfer_repr(xfer));
259 xfer->num_active_elements++;
260 xfer_queue_message(xfer,
261 xmsg_new((XferElement *)g_ptr_array_index(xfer->elements, xfer->elements->len-1),
270 /* Since xfer_cancel can be called from any thread, we just send a message.
271 * The action takes place when the message is received. */
272 XferElement *src = g_ptr_array_index(xfer->elements, 0);
273 xfer_queue_message(xfer, xmsg_new(src, XMSG_CANCEL, 0));
281 if (xfer->status == status) return;
283 g_mutex_lock(xfer->status_mutex);
285 /* check that this state transition is valid */
288 g_assert(xfer->status == XFER_INIT);
291 g_assert(xfer->status == XFER_START);
293 case XFER_CANCELLING:
294 g_assert(xfer->status == XFER_RUNNING);
297 g_assert(xfer->status == XFER_CANCELLING);
300 g_assert(xfer->status == XFER_CANCELLED || xfer->status == XFER_RUNNING);
304 g_assert_not_reached();
307 xfer->status = status;
308 g_cond_broadcast(xfer->status_cond);
309 g_mutex_unlock(xfer->status_mutex);
316 /* How is ELT linked? link_recurse uses an array of these to track its progress
317 * and find the optimal overall linkage. */
318 typedef struct linkage {
320 xfer_element_mech_pair_t *mech_pairs;
321 int elt_idx; /* index into elt's mech_pairs */
322 int glue_idx; /* index into glue pairs for elt's output; -1 = no glue */
325 /* Overall state of the recursive linking process */
326 typedef struct linking_state {
327 int nlinks; /* number of linkage objects in each array */
328 linkage *cur; /* "current" linkage */
330 linkage *best; /* best linkage so far */
331 gint32 best_cost; /* cost for best */
334 /* used for debugging messages */
340 case XFER_MECH_NONE: return "NONE";
341 case XFER_MECH_READFD: return "READFD";
342 case XFER_MECH_WRITEFD: return "WRITEFD";
343 case XFER_MECH_PULL_BUFFER: return "PULL_BUFFER";
344 case XFER_MECH_PUSH_BUFFER: return "PUSH_BUFFER";
345 case XFER_MECH_DIRECTTCP_LISTEN: return "DIRECTTCP_LISTEN";
346 case XFER_MECH_DIRECTTCP_CONNECT: return "DIRECTTCP_CONNECT";
347 default: return "UNKNOWN";
351 /* calculate an integer representing the cost of a mech pair as a
352 * single integer. OPS_PER_BYTE is the most important metric,
353 * followed by NTHREADS.
355 * PAIR will be evaluated multiple times.
357 #define PAIR_COST(pair) (((pair).ops_per_byte << 8) + (pair).nthreads)
360 #define MAX_COST 0xffffff
362 /* Generate all possible linkages of elements [idx:nlinks], where
363 * elements [0:idx-1] have cost 'cost' and end with mechanism
369 xfer_mech input_mech,
372 xfer_element_mech_pair_t *elt_pairs, *glue_pairs;
375 /* if we've overrun the previous best cost already, then bail out */
376 if (cost >= st->best_cost)
379 /* have we linked everything? */
380 if (idx == st->nlinks) {
381 /* if we ended on other than XFER_MECH_NONE, then this is not a
383 if (input_mech != XFER_MECH_NONE) return;
385 /* we already know this has lower cost than the previous best */
386 memcpy(st->best, st->cur, st->nlinks * sizeof(linkage));
387 st->best_cost = cost;
392 /* recurse for each linkage we can make that starts with input_mech */
394 elt_pairs = my->mech_pairs;
395 glue_pairs = xfer_element_glue_mech_pairs;
397 for (my->elt_idx = 0;
398 elt_pairs[my->elt_idx].input_mech != XFER_MECH_NONE
399 || elt_pairs[my->elt_idx].output_mech != XFER_MECH_NONE;
401 /* reject this pair if the input mech does not match */
402 if (elt_pairs[my->elt_idx].input_mech != input_mech)
405 /* recurse with no glue */
407 link_recurse(st, idx+1,
408 elt_pairs[my->elt_idx].output_mech,
409 cost + PAIR_COST(elt_pairs[my->elt_idx]));
411 /* and recurse with glue */
412 for (my->glue_idx = 0;
413 glue_pairs[my->glue_idx].input_mech != XFER_MECH_NONE
414 || glue_pairs[my->glue_idx].output_mech != XFER_MECH_NONE;
416 /* reject this glue pair if it doesn't match with the element output */
417 if (glue_pairs[my->glue_idx].input_mech != elt_pairs[my->elt_idx].output_mech)
420 /* and recurse with the glue */
421 link_recurse(st, idx+1,
422 glue_pairs[my->glue_idx].output_mech,
423 cost + PAIR_COST(elt_pairs[my->elt_idx])
424 + PAIR_COST(glue_pairs[my->glue_idx]));
433 GPtrArray *new_elements;
439 /* Note that this algorithm's running time is polynomial in the length of
440 * the transfer, with a fairly high order. If Amanda is regularly assembling
441 * transfers with more than, say, 6 elements, then the algorithm should be
444 /* set up the state for recursion */
445 st.nlinks = xfer->elements->len;
446 st.cur = g_new0(linkage, st.nlinks);
447 st.best = g_new0(linkage, st.nlinks);
448 st.best_cost = MAX_COST;
449 for (i = 0; i < st.nlinks; i++) {
450 st.cur[i].elt = (XferElement *)g_ptr_array_index(xfer->elements, i);
451 st.cur[i].mech_pairs = xfer_element_get_mech_pairs(st.cur[i].elt);
454 /* check that the first element is an XferSource and the last is an XferDest.
455 * A source is identified by having no input mechanisms. */
456 if (st.cur[0].mech_pairs[0].input_mech != XFER_MECH_NONE)
457 error("Transfer element 0 is not a transfer source");
459 /* Similarly, a destination has no output mechanisms. */
460 if (st.cur[st.nlinks-1].mech_pairs[0].output_mech != XFER_MECH_NONE)
461 error("Last transfer element is not a transfer destination");
463 /* start recursing with the first element, asserting that its input mech is NONE */
464 link_recurse(&st, 0, XFER_MECH_NONE, 0);
466 /* check that we got *some* solution */
467 if (st.best_cost == MAX_COST) {
468 error(_("Xfer %s cannot be linked."), xfer_repr(xfer));
471 /* Now create a new list of elements, containing any glue elements
472 * that we need to add, and set their input_mech and output_mech fields */
473 new_elements = g_ptr_array_sized_new(xfer->elements->len);
474 for (i = 0; i < st.nlinks; i++) {
475 elt = st.best[i].elt;
476 elt->input_mech = st.best[i].mech_pairs[st.best[i].elt_idx].input_mech;
477 elt->output_mech = st.best[i].mech_pairs[st.best[i].elt_idx].output_mech;
478 g_ptr_array_add(new_elements, elt);
480 if (st.best[i].glue_idx != -1) {
481 elt = xfer_element_glue();
483 elt->input_mech = xfer_element_glue_mech_pairs[st.best[i].glue_idx].input_mech;
484 elt->output_mech = xfer_element_glue_mech_pairs[st.best[i].glue_idx].output_mech;
485 g_ptr_array_add(new_elements, elt);
489 /* install the new list of elements */
490 g_ptr_array_free(xfer->elements, FALSE);
491 xfer->elements = new_elements;
494 /* debug-log the xfer's linkage */
495 len = xfer->elements->len;
496 linkage_str = stralloc("Final linkage: ");
497 for (i = 0; i < len; i++) {
498 XferElement *elt = g_ptr_array_index(xfer->elements, i);
501 linkage_str = newvstralloc(linkage_str, linkage_str, xfer_element_repr(elt), NULL);
503 linkage_str = newvstrallocf(linkage_str, "%s -(%s)-> %s",
504 linkage_str, xfer_mech_name(elt->input_mech), xfer_element_repr(elt));
506 g_debug("%s", linkage_str);
522 XMsgSource *xms = (XMsgSource *)source;
525 return xms->xfer && g_async_queue_length(xms->xfer->queue) > 0;
532 XMsgSource *xms = (XMsgSource *)source;
534 return xms->xfer && g_async_queue_length(xms->xfer->queue) > 0;
539 GSource *source G_GNUC_UNUSED,
540 GSourceFunc callback,
543 XMsgSource *xms = (XMsgSource *)source;
544 Xfer *xfer = xms->xfer;
545 XMsgCallback my_cb = (XMsgCallback)callback;
547 gboolean deliver_to_caller;
549 gboolean xfer_done = FALSE;
551 /* we're potentially calling Perl code within this loop, so we have to
552 * check that everything is ok on each iteration of the loop. */
554 && xfer->status != XFER_DONE
555 && (msg = (XMsg *)g_async_queue_try_pop(xfer->queue))) {
557 /* We get first crack at interpreting messages, before calling the
558 * designated callback. */
559 deliver_to_caller = TRUE;
561 /* Intercept and count DONE messages so that we can determine when
562 * the entire transfer is finished. */
564 if (--xfer->num_active_elements <= 0) {
565 /* mark the transfer as done, and take a note to break out
566 * of this loop after delivering the message to the user */
567 xfer_set_status(xfer, XFER_DONE);
570 /* eat this XMSG_DONE, since we expect more */
571 deliver_to_caller = FALSE;
576 if (xfer->status == XFER_CANCELLING || xfer->status == XFER_CANCELLED) {
577 /* ignore duplicate cancel messages */
578 deliver_to_caller = FALSE;
580 /* call cancel() on each child element */
583 g_debug("Cancelling %s", xfer_repr(xfer));
584 xfer_set_status(xfer, XFER_CANCELLING);
587 for (i = 0; i < xfer->elements->len; i++) {
588 XferElement *elt = (XferElement *)
589 g_ptr_array_index(xfer->elements, i);
590 expect_eof = xfer_element_cancel(elt, expect_eof) || expect_eof;
593 /* if nothing in the transfer can generate an EOF, then we
594 * can't cancel this transfer, and we'll just have to wait
595 * until it's finished. This may happen, for example, if
596 * the operating system is copying data for us
599 g_warning("Transfer %s cannot be cancelled.", xfer_repr(xfer));
601 /* and now we're done cancelling */
602 xfer_set_status(xfer, XFER_CANCELLED);
607 break; /* nothing interesting to do */
610 if (deliver_to_caller) {
612 my_cb(user_data, msg, xfer);
614 g_warning("Dropping %s because no callback is set", xmsg_repr(msg));
620 /* This transfer is done, so kill it and exit the loop */
628 /* Never automatically un-queue the event source */
636 static GSourceFuncs *xmsgsource_funcs = NULL;
640 /* initialize these here to avoid a compiler warning */
641 if (!xmsgsource_funcs) {
642 xmsgsource_funcs = g_new0(GSourceFuncs, 1);
643 xmsgsource_funcs->prepare = xmsgsource_prepare;
644 xmsgsource_funcs->check = xmsgsource_check;
645 xmsgsource_funcs->dispatch = xmsgsource_dispatch;
648 src = g_source_new(xmsgsource_funcs, sizeof(XMsgSource));
649 xms = (XMsgSource *)src;
656 wait_until_xfer_cancelled(
659 xfer_status seen_status;
660 g_assert(xfer != NULL);
662 g_mutex_lock(xfer->status_mutex);
663 while (xfer->status != XFER_CANCELLED && xfer->status != XFER_DONE)
664 g_cond_wait(xfer->status_cond, xfer->status_mutex);
665 seen_status = xfer->status;
666 g_mutex_unlock(xfer->status_mutex);
672 wait_until_xfer_running(
675 xfer_status seen_status;
676 g_assert(xfer != NULL);
678 g_mutex_lock(xfer->status_mutex);
679 while (xfer->status == XFER_START)
680 g_cond_wait(xfer->status_cond, xfer->status_mutex);
681 seen_status = xfer->status;
682 g_mutex_unlock(xfer->status_mutex);
688 xfer_cancel_with_error(
696 g_assert(elt != NULL);
697 g_assert(elt->xfer != NULL);
699 msg = xmsg_new(elt, XMSG_ERROR, 0);
701 arglist_start(argp, fmt);
702 msg->message = g_strdup_vprintf(fmt, argp);
705 /* send the XMSG_ERROR */
706 xfer_queue_message(elt->xfer, msg);
708 /* cancel the transfer */
709 xfer_cancel(elt->xfer);
713 xfer_atomic_swap_fd(Xfer *xfer, gint *fdp, gint newfd)
718 g_mutex_lock(xfer->fd_mutex);
722 g_mutex_unlock(xfer->fd_mutex);