1/** 2 * \file 3 * \brief Bidirectional Multi-hop channel implementation 4 */ 5 6/* 7 * Copyright (c) 2009, 2010, 2012, ETH Zurich. 8 * All rights reserved. 9 * 10 * This file is distributed under the terms in the attached LICENSE file. 11 * If you do not find this file, copies can be found by writing to: 12 * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group. 13 */ 14 15#include <barrelfish/barrelfish.h> 16#include <barrelfish/multihop_chan.h> 17#include <barrelfish/idc_export.h> 18#include <flounder/flounder_support.h> 19#include <if/monitor_defs.h> 20#include <collections/hash_table.h> 21#include <bench/bench.h> 22 23// TODO remove this 24#include <stdio.h> 25 26#ifndef CONFIG_INTERCONNECT_DRIVER_MULTIHOP 27#error "This file shouldn't be compiled without CONFIG_INTERCONNECT_DRIVER_MULTIHOP" 28#endif 29 30/////////////////////////////////////////////////////// 31 32// HASH TABLE 33 34/////////////////////////////////////////////////////// 35 36/** 37 * We use a hash table to map VCIs to bindings. 38 */ 39static collections_hash_table *mappings; 40 41// is the mapping table initialized? 42static bool is_mapping_table_initialized = false; 43 44// initialize the mapping table 45static inline void multihop_chan_init_mapping_table(void) 46{ 47 48 if (!is_mapping_table_initialized) { 49 is_mapping_table_initialized = true; 50 collections_hash_create_with_buckets(&mappings, MULTIHOP_MAPPING_TABLE_BACKETS, 51 free); 52 /* 53 * We use a constant as seed for the random function. 54 * We could use something like bench_tsc() as seed, but 55 * this would require a dependency on lib/bench. 56 * 57 * This makes assigned VCIs predictable. But because we trust 58 * the monitor not to send manipulated VCIs, this is not a 59 * security issue. 60 */ 61 srand(11); 62 } 63} 64 65// insert entry in the mapping table and return VCI 66static inline multihop_vci_t multihop_chan_mapping_insert( 67 struct multihop_chan *chan_state) 68{ 69 70 assert(chan_state != NULL); 71 multihop_vci_t vci; 72 73 multihop_chan_init_mapping_table(); 74 75 do { 76 // we assign VCIs randomly, but need 77 // to make sure that it is not yet taken 78 vci = (multihop_vci_t) rand(); 79 } while (collections_hash_find(mappings, vci) != NULL); 80 81 // insert into forwarding table 82 collections_hash_insert(mappings, vci, chan_state); 83 return vci; 84} 85 86// delete entry from forwarding table 87static inline void multihop_chan_mapping_delete(multihop_vci_t vci) 88{ 89 assert(is_mapping_table_initialized); 90 collections_hash_delete(mappings, vci); 91} 92 93// get entry from the mapping table 94static inline struct multihop_chan* multihop_chan_mappings_lookup(multihop_vci_t vci) 95{ 96 97 assert(is_mapping_table_initialized); 98 struct multihop_chan *chan_state = collections_hash_find(mappings, vci); 99 100 if (chan_state == NULL) { 101 USER_PANIC("invalid virtual circuit identifier in multi-hop channel"); 102 } 103 return chan_state; 104} 105 106/////////////////////////////////////////////////////// 107 108// BIND & CREATE A NEW MULTIHOP CHANNEL 109 110/////////////////////////////////////////////////////// 111 112static void multihop_new_monitor_binding_continuation(void *st, errval_t err, 113 struct monitor_binding *monitor_binding); 114 115static void multihop_chan_bind_cont(void *st); 116 117/** 118 * \brief Initialize a new multihop channel 119 * 120 * \param mc Storrage for the multihop channel state 121 * \param cont Continuation for bind completion/failure 122 * \param iref IREF of the service to which we want to bind 123 * \param waitset to use 124 */ 125errval_t multihop_chan_bind(struct multihop_chan *mc, 126 struct multihop_bind_continuation cont, iref_t iref, 127 struct waitset *waitset) 128{ 129 errval_t err; 130 131 // store bind arguments 132 mc->bind_continuation = cont; 133 mc->iref = iref; 134 mc->connstate = MULTIHOP_BIND_WAIT; 135 136 // create new monitor binding 137 err = monitor_client_new_binding(multihop_new_monitor_binding_continuation, 138 mc, waitset, DEFAULT_LMP_BUF_WORDS); 139 return err; 140} 141 142/** 143 * \brief Internal function called as soon as the new monitor binding is created 144 * \param st pointer to the multi-hop channel 145 * \param err error variable indicating success / failure 146 * \param monitor_binding the new monitor binding 147 */ 148static void multihop_new_monitor_binding_continuation(void *st, errval_t err, 149 struct monitor_binding *monitor_binding) 150{ 151 struct multihop_chan *mc = st; 152 153 if (err_is_fail(err)) { 154 // report error to user 155 err = err_push(err, LIB_ERR_MONITOR_CLIENT_BIND); 156 mc->bind_continuation.handler(mc->bind_continuation.st, err, NULL); 157 } else { 158 mc->monitor_binding = monitor_binding; 159 160 // get a virtual circuit identifier (VCI) for this binding 161 mc->my_vci = multihop_chan_mapping_insert(mc); 162 163 // send request to the monitor 164 multihop_chan_bind_cont(mc); 165 } 166} 167 168/** 169 * \brief Continuation function for binding. This function 170 * send the bind request to the monitor. 171 * \param pointer to the multihop_chan 172 */ 173static void multihop_chan_bind_cont(void *st) 174{ 175 176 errval_t err; 177 struct multihop_chan *mc = st; 178 struct monitor_binding *monitor_binding = mc->monitor_binding; 179 180 // send bind request to the monitor 181 // we do not get a lock on the monitor binding, as we did not expose it to the application 182 MULTIHOP_DEBUG("sending bind request to monitor...\n"); 183 err = monitor_binding->tx_vtbl.multihop_bind_client_request(monitor_binding, 184 NOP_CONT, mc->iref, mc->my_vci); 185 186 if (err_is_ok(err)) { 187 // request was successfully sent 188 } else if (err_no(err) == FLOUNDER_ERR_TX_BUSY) { 189 // register to retry 190 err = monitor_binding->register_send(monitor_binding, 191 monitor_binding->waitset, MKCONT(multihop_chan_bind_cont, st)); 192 assert(err_is_ok(err)); 193 } else { // permanent failure sending message 194 mc->bind_continuation.handler(mc->bind_continuation.st, 195 err_push(err, LIB_ERR_BIND_MULTIHOP_REQ), NULL); 196 //TODO destroy channel state? 197 } 198} 199 200/** 201 * \brief Handles the bind reply message from the monitor 202 * \param monitor_binding 203 * \param ingoing_vci my (ingoing) virtual circuit identifier 204 * \param outgoing_vci virtual circuit identifier to use for outgoing messages 205 */ 206static void multihop_bind_reply_handler(struct monitor_binding *monitor_binding, 207 multihop_vci_t ingoing_vci, multihop_vci_t outgoing_vci, errval_t msgerr) 208{ 209 MULTIHOP_DEBUG("dispatcher has received bind reply!\n"); 210 211 struct multihop_chan *mc = multihop_chan_mappings_lookup(ingoing_vci); 212 213 assert(mc->connstate == MULTIHOP_BIND_WAIT); 214 assert(mc->bind_continuation.handler != NULL); 215 216 if (err_is_ok(msgerr)) { /* bind succeeded */ 217 mc->direction = 1; 218 mc->unacked_received = 0; 219 mc->unacked_send = 0; 220 mc->vci = outgoing_vci; 221 mc->connstate = MULTIHOP_CONNECTED; 222 mc->bind_continuation.handler(mc->bind_continuation.st, msgerr, mc); 223 } else { /* bind failed */ 224 mc->connstate = MULTIHOP_DISCONNECTED; 225 multihop_chan_mapping_delete(mc->my_vci); 226 mc->bind_continuation.handler(mc->bind_continuation.st, msgerr, mc); 227 free(mc); 228 } 229} 230 231/////////////////////////////////////////////////////// 232 233// HANDLE BIND REQUESTS 234 235/////////////////////////////////////////////////////// 236 237static void send_bind_reply(void *arg); 238 239static void multihop_new_monitor_binding_continuation2(void *st, errval_t err, 240 struct monitor_binding *monitor_binding); 241 242// struct for the reply state 243struct bind_multihop_reply_state { 244 struct multihop_chan *mc; 245 struct monitor_binding *monitor_binding; 246 struct monitor_multihop_bind_service_reply__tx_args args; 247 struct event_queue_node qnode; 248}; 249 250/** 251 * \brief This method handles incoming bind requests from the monitor 252 * \param monitor_binding 253 * \param service_id the ID of the servict to bind to 254 * \param vci the virtual circuit identifier to use on outgoing messages 255 */ 256 257static void multihop_bind_service_request_handler( 258 struct monitor_binding *monitor_binding, uintptr_t service_id, 259 multihop_vci_t vci) 260{ 261 errval_t err; 262 struct idc_export *e = (void *) service_id; 263 264 // call the binding's connect handler 265 if (e->multihop_connect_callback != NULL) { 266 err = e->multihop_connect_callback(e->connect_cb_st, vci); 267 } else { 268 err = LIB_ERR_NO_MULTIHOP_BIND_HANDLER; 269 } 270 271 if (err_is_fail(err)) { 272 multihop_chan_send_bind_reply(NULL, err, vci, NULL); 273 } else { 274 // do nothing, as the binding is responsible for sending a reply 275 } 276} 277 278/** 279 * \brief Send a reply back to the monitor. If the error code indicates success, this function 280 * creates a new monitor binding and registers to receive messages. 281 * \param multihop_chan 282 * \param err error code to send back 283 * \param vci my vci for ingoing messages 284 * \param waitset waitset to use for the channel 285 */ 286void multihop_chan_send_bind_reply(struct multihop_chan *mc, errval_t msgerr, 287 multihop_vci_t vci, struct waitset *waitset) 288{ 289 290 errval_t err; 291 struct bind_multihop_reply_state *reply_state = malloc( 292 sizeof(struct bind_multihop_reply_state)); 293 assert(reply_state != NULL); 294 295 if (err_is_ok(msgerr)) { 296 // make sure channel exists 297 assert(mc != NULL); 298 } else { 299 // make sure channel is not created 300 assert(mc == NULL); 301 } 302 303 reply_state->mc = mc; 304 reply_state->args.err = msgerr; 305 reply_state->args.receiver_vci = vci; 306 307 if (err_is_ok(msgerr)) { 308 // get a vci for this binding 309 reply_state->mc->my_vci = multihop_chan_mapping_insert(mc); 310 reply_state->args.sender_vci = reply_state->mc->my_vci; 311 } else { 312 reply_state->args.sender_vci = 0; 313 } 314 315 if (err_is_ok(msgerr)) { 316 317 // create a new monitor binding 318 err = monitor_client_new_binding( 319 multihop_new_monitor_binding_continuation2, reply_state, 320 waitset, DEFAULT_LMP_BUF_WORDS); 321 if (err_is_fail(err)) { 322 USER_PANIC_ERR( 323 err, 324 "Could not create a new monitor binding in the multi-hop interconnect driver"); 325 } 326 } else { 327 reply_state->monitor_binding = get_monitor_binding(); 328 // wait for the ability to use the monitor binding 329 event_mutex_enqueue_lock(&reply_state->monitor_binding->mutex, 330 &reply_state->qnode, MKCLOSURE(send_bind_reply, reply_state)); 331 } 332 333} 334 335/** 336 * \brief Internal function that is called as soon as a new monitor binding is created 337 */ 338static void multihop_new_monitor_binding_continuation2(void *st, errval_t err, 339 struct monitor_binding *monitor_binding) 340{ 341 342 struct bind_multihop_reply_state *reply_state = st; 343 if (err_is_fail(err)) { 344 reply_state->args.err = err; 345 } else { 346 reply_state->monitor_binding = monitor_binding; 347 reply_state->mc->monitor_binding = monitor_binding; 348 reply_state->mc->direction = 2; 349 reply_state->mc->unacked_received = 0; 350 reply_state->mc->unacked_send = 0; 351 reply_state->mc->connstate = MULTIHOP_CONNECTED; 352 } 353 354 // wait for the ability to use the monitor binding 355 event_mutex_enqueue_lock(&reply_state->monitor_binding->mutex, 356 &reply_state->qnode, MKCLOSURE(send_bind_reply, reply_state)); 357} 358 359/** 360 * \ brief Internal function to send a reply back to the monitor 361 * 362 */ 363static void send_bind_reply(void *st) 364{ 365 366 errval_t err; 367 struct bind_multihop_reply_state *reply_state = st; 368 struct monitor_binding *monitor_binding = reply_state->monitor_binding; 369 370 // send back a bind success / failure message to the monitor 371 MULTIHOP_DEBUG("sending reply back to monitor...\n"); 372 err = monitor_binding->tx_vtbl.multihop_bind_service_reply(monitor_binding, 373 NOP_CONT, reply_state->args.receiver_vci, 374 reply_state->args.sender_vci, reply_state->args.err); 375 376 if (err_is_ok(err)) { 377 event_mutex_unlock(&monitor_binding->mutex); 378 free(reply_state); 379 } else if (err_no(err) == FLOUNDER_ERR_TX_BUSY) { 380 err = monitor_binding->register_send(monitor_binding, 381 monitor_binding->waitset, MKCONT(send_bind_reply, reply_state)); 382 assert(err_is_ok(err)); 383 // this shouldn't fail, as we have the mutex 384 } else { 385 event_mutex_unlock(&monitor_binding->mutex); 386 USER_PANIC_ERR( 387 err, 388 "failed sending back reply to multi-hop bind request to monitor"); 389 free(st); 390 } 391} 392 393/////////////////////////////////////////////////////// 394 395// SEND AND RECEIVE MESSAGES 396 397/////////////////////////////////////////////////////// 398 399/** 400 * \brief Send a multi-hop message that contains no payload. 401 * It is used to acknowledge received messages. 402 * 403 * \param mc pointer to the multi-hop channel 404 */ 405static void multihop_send_dummy_message(struct multihop_chan *mc) 406{ 407 assert(mc->connstate == MULTIHOP_CONNECTED); 408 409#if MULTIHOP_FLOW_CONTROL 410 411 MULTIHOP_DEBUG("sending dummy message, ack %d...\n", mc->unacked_received); 412 413 errval_t err; 414 struct monitor_binding *monitor_binding = mc->monitor_binding; 415 416 // send message 417 err = monitor_binding->tx_vtbl.multihop_message(monitor_binding, NOP_CONT, 418 mc->vci, mc->direction, MULTIHOP_MESSAGE_FLAG_DUMMY, 419 mc->unacked_received, (uint8_t *) mc, 1); 420 421 if (err_is_ok(err)) { 422 // we have just acknowledged all received messages 423 mc->unacked_received = 0; 424 } else if (err_no(err) != FLOUNDER_ERR_TX_BUSY) { 425 USER_PANIC_ERR(err, 426 "Could not send dummy message over multi-hop channel\n"); 427 428 } 429 430#endif // MULTIHOP_FLOW_CONTROL 431} 432 433/** 434 * \brief Send a multi-hop message 435 * 436 * \param mc pointer to the multi-hop channel 437 * \param _continuation callback to be executed after the message is sent 438 * \param msg pointer to the message payload 439 * \param msglen length of the message payload (in bytes) 440 * 441 */ 442errval_t multihop_send_message(struct multihop_chan *mc, 443 struct event_closure _continuation, void *msg, size_t msglen) 444{ 445 446 errval_t err; 447 struct monitor_binding *monitor_binding = mc->monitor_binding; 448 assert(mc->connstate == MULTIHOP_CONNECTED); 449 450#if MULTIHOP_FLOW_CONTROL 451 // make sure that we can send another message 452 if (mc->unacked_send == MULTIHOP_WINDOW_SIZE) { 453 return FLOUNDER_ERR_TX_BUSY; 454 } 455#endif // MULTIHOP_FLOW_CONTROL 456 // send message 457 err = monitor_binding->tx_vtbl.multihop_message(monitor_binding, 458 _continuation, mc->vci, mc->direction, 459 MULTIHOP_MESSAGE_FLAG_PAYLOAD, mc->unacked_received, 460 (uint8_t *) msg, msglen); 461 462#if MULTIHOP_FLOW_CONTROL 463 if (err_is_ok(err)) { 464 // update flow control information 465 mc->unacked_received = 0; 466 mc->unacked_send = mc->unacked_send + 1; 467 } 468#endif // MULTIHOP_FLOW_CONTROL 469 return err; 470} 471 472/** 473 * \brief Send a capability over the multi-hop channel 474 * 475 * \param mc pointer to the multi-hop channel 476 * \param _continuation callback to be executed after the message is sent 477 * \param cap_state pointer to the cap state of the channel 478 * \param cap the capability to send 479 */ 480errval_t multihop_send_capability(struct multihop_chan *mc, 481 struct event_closure _continuation, 482 struct flounder_cap_state *cap_state, struct capref cap) 483{ 484 485 errval_t err; 486 assert(mc->connstate == MULTIHOP_CONNECTED); 487 struct monitor_binding *mon_binding = mc->monitor_binding; 488 489 // send the message 490 err = mon_binding->tx_vtbl.multihop_cap_send(mon_binding, _continuation, 491 mc->vci, mc->direction, 492 SYS_ERR_OK, cap, 493 cap_state->tx_capnum); 494 495 if (err_is_ok(err)) { 496 // increase capability number 497 cap_state->tx_capnum++; 498 return err; 499 } else if (err_no(err) == FLOUNDER_ERR_TX_BUSY) { 500 return err; 501 } else { 502 return err_push(err, LIB_ERR_MONITOR_CAP_SEND); 503 } 504} 505 506/** 507 * \brief Handle a incoming multi-hop message 508 * 509 * \param mon_closure the monitor binding 510 * \param vci the virtual circuit identifier of the channel 511 * \param direction direction of the message 512 * \param flags message flags 513 * \param ack number of messages that the sender acknowledges 514 * \param buf pointer to the message payload 515 * \param buflen size of the received message 516 * 517 */ 518static void handle_multihop_message(struct monitor_binding *mon_closure, 519 multihop_vci_t vci, uint8_t direction, uint8_t flags, uint32_t ack, 520 const uint8_t *buf, size_t buflen) 521{ 522 523 struct multihop_chan *mc = multihop_chan_mappings_lookup(vci); 524 assert(mc->connstate == MULTIHOP_CONNECTED); 525 526 if (flags == MULTIHOP_MESSAGE_FLAG_DUMMY) { 527 // this is a dummy message 528 MULTIHOP_DEBUG("received dummy message, acked: %d\n", ack); 529 assert(ack <= mc->unacked_send); 530 mc->unacked_send = mc->unacked_send - ack; 531 532 // we need to execute the message receive handler, 533 // because the flounder-stubs might be waiting to 534 // receive a dummy message 535 mc->rx_handler.handler(mc->rx_handler.arg, NULL, 0); 536 537 } else { // this message contains payload 538 539#if MULTIHOP_FLOW_CONTROL 540 541 // update flow control information 542 mc->unacked_received = mc->unacked_received + 1; 543 assert(ack <= mc->unacked_send); 544 mc->unacked_send = mc->unacked_send - ack; 545 546#endif // MULTIHOP_FLOW_CONTROL 547 // deliver message to the message handler 548 mc->rx_handler.handler(mc->rx_handler.arg, buf, buflen); 549 550 // send a dummy message back if necessary 551 if (mc->unacked_received 552 > MULTIHOP_WINDOW_SIZE * MULTIHOP_WINDOW_RATIO_DUMMY_MESSAGE) { 553 multihop_send_dummy_message(mc); 554 } 555 } 556} 557 558/** 559 * \brief Handle a incoming capability 560 * 561 * \param mon_closure the monitor binding 562 * \param vci the virtual circuit identifier of the channel 563 * \param direction direction of the message 564 * \param cap reference to the capability 565 * \param capid id of the capability 566 * 567 */ 568static void multihop_handle_capability(struct monitor_binding *mon_closure, 569 multihop_vci_t vci, uint8_t direction, errval_t msgerr, 570 struct capref cap, uint32_t capid) 571{ 572 573 struct multihop_chan *mc = multihop_chan_mappings_lookup(vci); 574 assert(mc->connstate == MULTIHOP_CONNECTED); 575 assert(mc->cap_handlers.cap_receive_handler != NULL); 576 577 // deliver capability to the handler 578 mc->cap_handlers.cap_receive_handler(mc->cap_handlers.st, msgerr, cap, capid); 579} 580 581/////////////////////////////////////////////////////// 582 583// CONTROL FUNCTIONS & INIT 584 585/////////////////////////////////////////////////////// 586 587/** 588 * \ brief Change the waitset of the multi-hop channel 589 * 590 * \param mc pointer to the multi-hop channel 591 * \param ws the new waitset 592 */ 593errval_t multihop_chan_change_waitset(struct multihop_chan *mc, 594 struct waitset *ws) 595{ 596 597 errval_t err; 598 err = flounder_support_change_monitor_waitset(mc->monitor_binding, ws); 599 if (err_is_fail(err)) { 600 return (err_push(err, FLOUNDER_ERR_CHANGE_MONITOR_WAITSET)); 601 } else { 602 return err; 603 } 604} 605 606/** 607 * \brief register a continuation closure to be invoked on the given waitset when the 608 * multi-hop channel may be able to accept the next message 609 */ 610errval_t multihop_chan_register_send(struct multihop_chan *mc, 611 struct waitset *ws, struct event_closure cont) 612{ 613 return mc->monitor_binding->register_send(mc->monitor_binding, ws, cont); 614} 615 616/** 617 * \brief Is the send window full? 618 * 619 */bool multihop_chan_is_window_full(struct multihop_chan *mc) 620{ 621#if MULTIHOP_FLOW_CONTROL 622 return mc->unacked_send == MULTIHOP_WINDOW_SIZE; 623#else 624 return false; 625#endif 626} 627 628/** 629 * \brief Initialize the multi-hop interconnect driver 630 * 631 */ 632void multihop_init(void) 633{ 634 struct monitor_binding *mb = get_monitor_binding(); 635 mb->rx_vtbl.multihop_bind_service_request = 636 &multihop_bind_service_request_handler; // handler for incoming bind request messages from the monitor 637 mb->rx_vtbl.multihop_bind_client_reply = &multihop_bind_reply_handler; // handler for incoming reply messages from the monitor 638 mb->rx_vtbl.multihop_message = &handle_multihop_message; // handler for incoming messages from the monitor 639 mb->rx_vtbl.multihop_cap_send = &multihop_handle_capability; // handler for incoming capabilities from the monitor 640} 641