examples/msg/chord/chord.c

   1
   2 /* Copyright (c) 2010. The SimGrid Team.
   3  * All rights reserved.                                                     */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 #include <stdio.h>
   9 #include "msg/msg.h"
  10 #include "xbt/log.h"
  11 #include "xbt/asserts.h"
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord,
  13                              "Messages specific for this msg example");
  14
  15 #define NB_BITS 6
  16 #define NB_KEYS 64
  17
  18 /**
  19  * Finger element.
  20  */
  21 typedef struct finger {
  22   int id;
  23   char* mailbox;
  24 } s_finger_t, *finger_t;
  25
  26 /**
  27  * Node data.
  28  */
  29 typedef struct node {
  30   int id;                                 // my id
  31   char* mailbox;
  32   s_finger_t fingers[NB_BITS];            // finger table (fingers[0] is my successor)
  33   int pred_id;                            // predecessor id
  34   char* pred_mailbox;
  35   xbt_dynar_t comms;                      // current communications to finish
  36 } s_node_t, *node_t;
  37
  38 /**
  39  * Task data
  40  */
  41 typedef struct task_data {
  42   int request_id;
  43   int request_finger;
  44   int answer_id;
  45   const char* answer_to;
  46   const char* issuer_host_name; // used for logging
  47 } s_task_data_t, *task_data_t;
  48
  49 // utility functions
  50 static int normalize(int id);
  51 static int is_in_interval(int id, int start, int end);
  52 static char* get_mailbox(int host_id);
  53 static void print_finger_table(node_t node);
  54
  55 // process functions
  56 static int node(int argc, char *argv[]);
  57
  58 // initialization
  59 static void initialize_first_node(node_t node);
  60 static void initialize_finger_table(node_t data, int known_id);
  61 static void join(node_t node, int known_id);
  62
  63 // Chord core
  64 static int find_successor(node_t node, int id);
  65 static int remote_find_successor(node_t node, int ask_to_id, int id);
  66 static int find_predecessor(node_t node, int id);
  67 static int remote_find_predecessor(node_t node, int ask_to_id, int id);
  68 static int closest_preceding_finger(node_t node, int id);
  69 static int remote_closest_preceding_finger(int ask_to_id, int id);
  70 static void notify_predecessors(node_t node);
  71 static void remote_move_keys(node_t node, int take_from_id);
  72 static void update_finger_table(node_t node, int candidate_id, int finger_index);
  73 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index);
  74 static void notify(node_t node, int predecessor_candidate_id);
  75 static void remote_notify(node_t node, int notify_to, int predecessor_candidate_id);
  76 static void stabilize(node_t node);
  77
  78 /**
  79  * \brief Turns an id into an equivalent id in [0, NB_KEYS[
  80  * \param id an id
  81  * \return the corresponding normalized id
  82  */
  83 static int normalize(int id) {
  84
  85   // make sure id >= 0
  86   while (id < 0) {
  87     id += NB_KEYS;
  88   }
  89
  90   // make sure id < NB_KEYS
  91   id = id % NB_KEYS;
  92
  93   return id;
  94 }
  95
  96 /**
  97  * \brief Returns whether a id belongs to the interval [start, end].
  98  *
  99  * The parameters are noramlized to make sure they are between 0 and CHORD_NB_KEYS - 1).
 100  * 1 belongs to [62, 3]
 101  * 1 does not belong to [3, 62]
 102  * 63 belongs to [62, 3]
 103  * 63 does not belong to [3, 62]
 104  * 24 belongs to [21, 29]
 105  * 24 does not belong to [29, 21]
 106  *
 107  * \param id id to check
 108  * \param start lower bound
 109  * \param end upper bound
 110  * \return a non-zero value if id in in [start, end]
 111  */
 112 static int is_in_interval(int id, int start, int end) {
 113
 114   id = normalize(id);
 115   start = normalize(start);
 116   end = normalize(end);
 117
 118   // make sure end >= start and id >= start
 119   if (end < start) {
 120     end += NB_KEYS;
 121   }
 122
 123   if (id < start) {
 124     id += NB_KEYS;
 125   }
 126
 127   return id <= end;
 128 }
 129
 130 /**
 131  * \brief Gets the mailbox name of a host given its chord id.
 132  * \param node_id id of a node
 133  * \return the name of its mailbox
 134  * FIXME: free the memory
 135  */
 136 static char* get_mailbox(int node_id) {
 137
 138   return bprintf("mailbox%d", node_id);
 139 }
 140
 141 /**
 142  * \brief Displays the finger table of a node.
 143  * \param node a node
 144  */
 145 static void print_finger_table(node_t node) {
 146
 147   int i;
 148   int pow = 1;
 149   INFO0("My finger table:");
 150   INFO0("Start | Succ ");
 151   for (i = 0; i < NB_BITS; i++) {
 152     INFO2(" %3d  | %3d ", (node->id + pow) % NB_KEYS, node->fingers[i].id);
 153     pow = pow << 1;
 154   }
 155   INFO1("Predecessor: %d", node->pred_id);
 156 }
 157
 158 /**
 159  * \brief Node Function
 160  * Arguments:
 161  * - my id
 162  * - the id of a guy I know in the system (except for the first node)
 163  * - the time to sleep before I join (except for the first node)
 164  */
 165 int node(int argc, char *argv[])
 166 {
 167   msg_comm_t comm = NULL;
 168   int i;
 169   char* mailbox;
 170
 171   xbt_assert0(argc == 2 || argc == 4, "Wrong number of arguments for this node");
 172
 173   // initialize my node
 174   s_node_t node = {0};
 175   node.id = atoi(argv[1]);
 176   node.mailbox = get_mailbox(node.id);
 177   node.comms = xbt_dynar_new(sizeof(msg_comm_t), NULL);
 178
 179   if (argc == 2) { // first ring
 180     initialize_first_node(&node);
 181   }
 182   else {
 183     int known_id = atoi(argv[2]);
 184     double sleep_time = atof(argv[3]);
 185
 186     // sleep before starting
 187     INFO1("Let's sleep >>%f", sleep_time);
 188     MSG_process_sleep(sleep_time);
 189     INFO0("Hey! Let's join the system.");
 190
 191     join(&node, known_id);
 192   }
 193
 194   while (1) {
 195
 196     unsigned int cursor;
 197     comm = NULL;
 198     xbt_dynar_foreach(node.comms, cursor, comm) {
 199       if (MSG_comm_test(comm)) { // FIXME: try with MSG_comm_testany instead
 200         xbt_dynar_cursor_rm(node.comms, &cursor);
 201         MSG_comm_destroy(comm);
 202       }
 203     }
 204
 205     m_task_t task = NULL;
 206     MSG_error_t res = MSG_task_receive(&task, node.mailbox);
 207
 208     xbt_assert0(res == MSG_OK, "MSG_task_receive failed");
 209
 210     // get data
 211     const char* task_name = MSG_task_get_name(task);
 212     task_data_t task_data = (task_data_t) MSG_task_get_data(task);
 213
 214     if (!strcmp(task_name, "Find Successor")) {
 215       INFO2("Receiving a 'Find Successor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
 216       // is my successor the successor?
 217       if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
 218         task_data->answer_id = node.fingers[0].id;
 219         MSG_task_set_name(task, "Find Successor Answer");
 220         INFO3("Sending back a 'Find Successor' Answer to %s: the successor of %d is %d", task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
 221         comm = MSG_task_isend(task, task_data->answer_to);
 222         xbt_dynar_push(node.comms, &comm);
 223       }
 224       else {
 225         // otherwise, forward the request to the closest preceding finger in my table
 226         int closest = closest_preceding_finger(&node, task_data->request_id);
 227         INFO2("Forwarding 'Find Successor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
 228         mailbox = get_mailbox(closest);
 229         comm = MSG_task_isend(task, mailbox);
 230         xbt_dynar_push(node.comms, &comm);
 231         xbt_free(mailbox);
 232       }
 233     }
 234     /*
 235     else if (!strcmp(task_name, "Find Successor Answer")) {
 236
 237     }
 238     */
 239     else if (!strcmp(task_name, "Find Predecessor")) {
 240       INFO2("Receiving a 'Find Predecessor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
 241       // am I the predecessor?
 242       if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
 243         task_data->answer_id = node.id;
 244         MSG_task_set_name(task, "Find Predecessor Answer");
 245         INFO3("Sending back a 'Find Predecessor' Answer to %s: the predecessor of %d is %d", task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
 246         comm = MSG_task_isend(task, task_data->answer_to);
 247         xbt_dynar_push(node.comms, &comm);
 248       }
 249       else {
 250         // otherwise, forward the request to the closest preceding finger in my table
 251         int closest = closest_preceding_finger(&node, task_data->request_id);
 252         INFO2("Forwarding 'Find Predecessor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
 253         mailbox = get_mailbox(closest);
 254         comm = MSG_task_isend(task, mailbox);
 255         xbt_dynar_push(node.comms, &comm);
 256         xbt_free(mailbox);
 257       }
 258     }
 259     /*
 260     else if (!strcmp(task_name, "Find Predecessor Answer")) {
 261
 262     }
 263     */
 264     else if (!strcmp(task_name, "Update Finger")) {
 265       // someone is telling me that he may be my new finger
 266       INFO1("Receiving an 'Update Finger' request from %s", task_data->issuer_host_name);
 267       update_finger_table(&node, task_data->request_id, task_data->request_finger);
 268     }
 269     else if (!strcmp(task_name, "Notify")) {
 270       // someone is telling me that he may be my new predecessor
 271       INFO1("Receiving a 'Notify' request from %s", task_data->issuer_host_name);
 272       notify(&node, task_data->request_id);
 273     }
 274     /*
 275     else if (!strcmp(task_name, "Fix Fingers"))
 276     {
 277       int i;
 278       for (i = KEY_BITS - 1 ; i >= 0; i--)
 279       {
 280         data->fingers[i] = find_finger_elem(data,(data->id)+pow(2,i-1));
 281       }
 282     }
 283     */
 284   }
 285
 286   xbt_dynar_free(&node.comms);
 287   xbt_free(node.mailbox);
 288   xbt_free(node.pred_mailbox);
 289   for (i = 0; i < NB_BITS - 1; i++) {
 290     xbt_free(node.fingers[i].mailbox);
 291   }
 292 }
 293
 294 /**
 295  * \brief Initializes the current node as the first one of the system.
 296  * \param node the current node
 297  */
 298 static void initialize_first_node(node_t node)
 299 {
 300   INFO0("Create a new Chord ring...");
 301
 302   // I am my own successor and predecessor
 303   int i;
 304   for (i = 0; i < NB_BITS; i++) {
 305     node->fingers[i].id = node->id;
 306     node->fingers[i].mailbox = xbt_strdup(node->mailbox);
 307   }
 308   node->pred_id = node->id;
 309   node->pred_mailbox = node->mailbox;
 310   print_finger_table(node);
 311 }
 312
 313 /**
 314  * \brief Makes the current node join the system, knowing the id of a node already in the system
 315  * \param node the current node
 316  * \param known_id id of a node already in the system
 317  */
 318 static void join(node_t node, int known_id)
 319 {
 320   initialize_finger_table(node, known_id); // determine my fingers, asking to known_id
 321   remote_notify(node, node->fingers[0].id, node->id); // tell my successor that I'm his new predecessor
 322   notify_predecessors(node); // tell others that I may have became their finger
 323   remote_move_keys(node, node->fingers[0].id); // take some key-value pairs from my sucessor
 324 }
 325
 326 /*
 327  * \brief Initializes my finger table, knowing the id of a node already in the system.
 328  * \param node the current node
 329  * \param known_id id of a node already in the system
 330  */
 331 static void initialize_finger_table(node_t node, int known_id)
 332 {
 333   int my_id = node->id;
 334   int i;
 335   int pow = 1; // 2^i
 336
 337   INFO0("Initializing my finger table...");
 338
 339   // ask known_id who is my immediate successor
 340   node->fingers[0].id = remote_find_successor(node, known_id, my_id + 1);
 341   node->fingers[0].mailbox = get_mailbox(node->fingers[0].id);
 342
 343   // find all other fingers
 344   for (i = 0; i < NB_BITS - 1; i++) {
 345
 346     pow = pow << 1; // equivalent to pow = pow * 2
 347     if (is_in_interval(my_id + pow, my_id, node->fingers[i].id - 1)) {
 348       // I already have the info for this finger
 349       node->fingers[i + 1].id = node->fingers[i].id;
 350     }
 351     else {
 352       // I don't have the info, ask the only guy I know
 353       node->fingers[i + 1].id = remote_find_successor(node, known_id, my_id + pow);
 354     }
 355     node->fingers[i + 1].mailbox = get_mailbox(node->fingers[i + 1].id);
 356   }
 357
 358   node->pred_id = find_predecessor(node, node->id);
 359   node->pred_mailbox = get_mailbox(node->pred_id);
 360
 361   INFO0("Finger table initialized!");
 362   print_finger_table(node);
 363 }
 364
 365 /**
 366  * \brief Notifies some nodes that the current node may have became their finger.
 367  * \param node the current node, which has just joined the system
 368  */
 369 static void notify_predecessors(node_t node)
 370 {
 371   int i, pred_id;
 372   int pow = 1;
 373   for (i = 0; i < NB_BITS; i++) {
 374     // find the closest node whose finger #i can be me
 375     pred_id = find_predecessor(node, node->id - pow + 1); // note: no "+1" in the article!
 376     if (pred_id != node->id) {
 377       remote_update_finger_table(node, pred_id, node->id, i);
 378     }
 379     pow = pow << 1; // pow = pow * 2
 380   }
 381 }
 382
 383 /**
 384  * \brief Tells the current node that a node may have became its new finger.
 385  * \param node the current node
 386  * \param candidate_id id of the node that may be a new finger of the current node
 387  * \param finger_index index of the finger to update
 388  */
 389 static void update_finger_table(node_t node, int candidate_id, int finger_index)
 390 {
 391   int pow = 1;
 392   int i;
 393   for (i = 0; i < finger_index; i++) {
 394     pow = pow << 1;
 395   }
 396
 397   //  if (is_in_interval(candidate_id, node->id + pow, node->fingers[finger_index].id - 1)) {
 398   if (is_in_interval(candidate_id, node->id, node->fingers[finger_index].id - 1)) {
 399 //    INFO3("Candidate %d is between %d and %d!", candidate_id, node->id + pow, node->fingers[finger_index].id - 1);
 400     // candidate_id is my new finger
 401     xbt_free(node->fingers[finger_index].mailbox);
 402     node->fingers[finger_index].id = candidate_id;
 403     node->fingers[finger_index].mailbox = get_mailbox(candidate_id);
 404     INFO2("My new finger #%d is %d", finger_index, candidate_id);
 405     print_finger_table(node);
 406
 407     if (node->pred_id != node->id) { // FIXME: is this necessary?
 408       // my predecessor may be concerned too
 409       remote_update_finger_table(node, node->pred_id, candidate_id, finger_index);
 410     }
 411   }
 412 }
 413
 414 /**
 415  * \brief Tells a remote node that a node may have became its new finger.
 416  * \param ask_to_id id of the remote node to update
 417  * \param candidate_id id of the node that may be a new finger of the remote node
 418  * \param finger_index index of the finger to update
 419  */
 420 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index)
 421 {
 422   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 423   req_data->request_id = candidate_id;
 424   req_data->request_finger = finger_index;
 425   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 426
 427   // send a "Update Finger" request to ask_to_id
 428   INFO3("Sending an 'Update Finger' request to %d: his finger #%d may be %d now", ask_to_id, finger_index, candidate_id);
 429   m_task_t task = MSG_task_create("Update Finger", 1000, 5000, req_data);
 430   char* mailbox = get_mailbox(ask_to_id);
 431   msg_comm_t comm = MSG_task_isend(task, mailbox);
 432   xbt_dynar_push(node->comms, &comm);
 433   xbt_free(mailbox);
 434 }
 435
 436 /**
 437  * \brief Makes the current node find the successor node of an id.
 438  * \param node the current node
 439  * \param id the id to find
 440  * \return the id of the successor node
 441  */
 442 static int find_successor(node_t node, int id)
 443 {
 444   // is my successor the successor?
 445   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 446     return node->fingers[0].id;
 447   }
 448
 449   // otherwise, ask the closest preceding finger in my table
 450   int closest = closest_preceding_finger(node, id);
 451   return remote_find_successor(node, closest, id);
 452 }
 453
 454 /**
 455  * \brief Asks another node the successor node of an id.
 456  * \param node the current node
 457  * \param ask_to the node to ask to
 458  * \param id the id to find
 459  * \return the id of the successor node
 460  */
 461 static int remote_find_successor(node_t node, int ask_to, int id)
 462 {
 463   s_task_data_t req_data;
 464   char* mailbox = bprintf("%s Find Successor", node->mailbox);
 465   req_data.request_id = id;
 466   req_data.answer_to = mailbox;
 467   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 468
 469   // send a "Find Successor" request to ask_to_id
 470   INFO2("Sending a 'Find Successor' request to %d for key %d", ask_to, id);
 471   m_task_t task = MSG_task_create("Find Successor", 1000, 5000, &req_data);
 472   MSG_task_send(task, get_mailbox(ask_to));
 473
 474   // receive the answer
 475   task = NULL;
 476   MSG_task_receive(&task, req_data.answer_to);
 477   task_data_t ans_data;
 478   ans_data = MSG_task_get_data(task);
 479   int successor = ans_data->answer_id;
 480   xbt_free(mailbox);
 481   INFO2("Received the answer to my Find Successor request: the successor of key %d is %d", id, successor);
 482
 483   return successor;
 484 }
 485
 486 /**
 487  * \brief Makes the current node find the predecessor node of an id.
 488  * \param node the current node
 489  * \param id the id to find
 490  * \return the id of the predecessor node
 491  */
 492 static int find_predecessor(node_t node, int id)
 493 {
 494   if (node->id == node->fingers[0].id) {
 495     // I am the only node in the system
 496     return node->id;
 497   }
 498
 499   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 500     return node->id;
 501   }
 502   int ask_to = closest_preceding_finger(node, id);
 503   return remote_find_predecessor(node, ask_to, id);
 504 }
 505
 506 /**
 507  * \brief Asks another node the predecessor node of an id.
 508  * \param node the current node
 509  * \param ask_to the node to ask to
 510  * \param id the id to find
 511  * \return the id of the predecessor node
 512  */
 513 static int remote_find_predecessor(node_t node, int ask_to, int id)
 514 {
 515   s_task_data_t req_data;
 516   char* mailbox = bprintf("%s Find Predecessor", node->mailbox);
 517   req_data.request_id = id;
 518   req_data.answer_to = mailbox;
 519   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 520
 521   // send a "Find Predecessor" request to ask_to
 522   INFO2("Sending a 'Find Predecessor' request to %d for key %d", ask_to, id);
 523   m_task_t task = MSG_task_create("Find Predecessor", 1000, 5000, &req_data);
 524   MSG_task_send(task, get_mailbox(ask_to));
 525
 526   // receive the answer
 527   task = NULL;
 528   MSG_task_receive(&task, req_data.answer_to);
 529   task_data_t ans_data;
 530   ans_data = MSG_task_get_data(task);
 531   int predecessor = ans_data->answer_id;
 532   xbt_free(mailbox);
 533   INFO2("Received the answer to my 'Find Predecessor' request: the predecessor of key %d is %d", id, predecessor);
 534
 535   return predecessor;
 536 }
 537
 538 /**
 539  * \brief Returns the closest preceding finger of an id
 540  * with respect to the finger table of the current node.
 541  * \param node the current node
 542  * \param id the id to find
 543  * \return the closest preceding finger of that id
 544  */
 545 int closest_preceding_finger(node_t node, int id)
 546 {
 547   int i;
 548   for (i = NB_BITS - 1; i >= 0; i--) {
 549     if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) {
 550       return node->fingers[i].id;
 551     }
 552   }
 553   return node->id;
 554 }
 555
 556 /**
 557  * \brief This function is called periodically. It checks the immediate
 558  * successor of the current node.
 559  * \param node the current node
 560  */
 561 static void stabilize(node_t node) {
 562
 563   int x = find_predecessor(node, node->fingers[0].id);
 564   if (is_in_interval(x, node->id + 1, node->fingers[0].id)) {
 565     xbt_free(node->fingers[0].mailbox);
 566     node->fingers[0].id = x;
 567     node->fingers[0].mailbox = get_mailbox(x);
 568   }
 569   remote_notify(node, node->fingers[0].id, node->id);
 570 }
 571
 572 /**
 573  * \brief Notifies the current node that its predecessor may have changed.
 574  * \param node the current node
 575  * \param candidate_id the possible new predecessor
 576  */
 577 static void notify(node_t node, int predecessor_candidate_id) {
 578
 579   if (node->pred_id == node->id
 580     || is_in_interval(predecessor_candidate_id, node->pred_id, node->id)) {
 581
 582     node->pred_id = predecessor_candidate_id;
 583     node->pred_mailbox = get_mailbox(predecessor_candidate_id);
 584
 585     INFO1("My new predecessor is %d", predecessor_candidate_id);
 586     print_finger_table(node);
 587   }
 588   else {
 589     INFO1("I don't have to change my predecessor to %d", predecessor_candidate_id);
 590   }
 591 }
 592
 593 /**
 594  * \brief Notifies a remote node that its predecessor may have changed.
 595  * \param node the current node
 596  * \param notify_id id of the node to notify
 597  * \param candidate_id the possible new predecessor
 598  */
 599 static void remote_notify(node_t node, int notify_id, int predecessor_candidate_id) {
 600
 601   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 602   req_data->request_id = predecessor_candidate_id;
 603   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 604
 605   // send a "Notify" request to notify_id
 606   INFO1("Sending a 'Notify' request to %d", notify_id);
 607   m_task_t task = MSG_task_create("Notify", 1000, 5000, req_data);
 608   char* mailbox = get_mailbox(notify_id);
 609   msg_comm_t comm = MSG_task_isend(task, mailbox);
 610   xbt_dynar_push(node->comms, &comm);
 611   xbt_free(mailbox);
 612 }
 613
 614 /**
 615  * \brief Asks a node to take some of its keys.
 616  * \param node the current node, which has just joined the system
 617  * \param take_from_id id of a node who may have keys to give to the current node
 618  */
 619 static void remote_move_keys(node_t node, int take_from_id) {
 620   // TODO
 621 }
 622
 623 /**
 624  * \brief Main function.
 625  */
 626 int main(int argc, char *argv[])
 627 {
 628   if (argc < 3) {
 629     printf("Usage: %s platform_file deployment_file\n", argv[0]);
 630     printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]);
 631     exit(1);
 632   }
 633
 634   MSG_global_init(&argc, argv);
 635
 636   const char* platform_file = argv[1];
 637   const char* application_file = argv[2];
 638
 639   /* MSG_config("workstation/model","KCCFLN05"); */
 640   MSG_set_channel_number(0);
 641   MSG_create_environment(platform_file);
 642
 643   MSG_function_register("node", node);
 644   MSG_launch_application(application_file);
 645
 646   MSG_error_t res = MSG_main();
 647   INFO1("Simulation time: %g", MSG_get_clock());
 648
 649   MSG_clean();
 650
 651   if (res == MSG_OK)
 652     return 0;
 653   else
 654     return 1;
 655 }