SRC_SelectSource(SRC_Instance updated_inst)
{
  struct SelectInfo *si;
  struct timespec now, ref_time;
  int i, j, j1, j2, index, sel_prefer, n_endpoints, n_sel_sources, sel_req_source;
  int n_badstats_sources, max_sel_reach, max_sel_reach_size, max_badstat_reach;
  int depth, best_depth, trust_depth, best_trust_depth;
  int combined, stratum, min_stratum, max_score_index;
  int orphan_stratum, orphan_source, leap_votes, leap_ins, leap_del;
  double src_offset, src_offset_sd, src_frequency, src_frequency_sd, src_skew;
  double src_root_delay, src_root_dispersion;
  double best_lo, best_hi, distance, sel_src_distance, max_score;
  double first_sample_ago, max_reach_sample_ago;
  NTP_Leap leap_status;

  if (updated_inst)
    updated_inst->updates++;

  if (n_sources == 0) {
    /* In this case, we clearly cannot synchronise to anything */
    if (selected_source_index != INVALID_SOURCE) {
      log_selection_message("Can't synchronise: no sources", NULL);
      selected_source_index = INVALID_SOURCE;
    }
    return;
  }

  /* This is accurate enough and cheaper than calling LCL_ReadCookedTime */
  SCH_GetLastEventTime(&now, NULL, NULL);

  /* Step 1 - build intervals about each source */

  n_endpoints = 0;
  n_sel_sources = 0;
  n_badstats_sources = 0;
  sel_req_source = 0;
  max_sel_reach = max_badstat_reach = 0;
  max_sel_reach_size = 0;
  max_reach_sample_ago = 0.0;

  for (i = 0; i < n_sources; i++) {
    assert(sources[i]->status != SRC_OK);

    /* If some sources are specified with the require option, at least one
       of them will have to be selectable in order to update the clock */
    if (sources[i]->sel_options & SRC_SELECT_REQUIRE)
      sel_req_source = 1;

    /* Ignore sources which were added with the noselect option */
    if (sources[i]->sel_options & SRC_SELECT_NOSELECT) {
      sources[i]->status = SRC_UNSELECTABLE;
      continue;
    }

    si = &sources[i]->sel_info;
    SST_GetSelectionData(sources[i]->stats, &now, &si->stratum, &si->leap,
                         &si->lo_limit, &si->hi_limit, &si->root_distance,
                         &si->std_dev, &first_sample_ago,
                         &si->last_sample_ago, &si->select_ok);

    if (!si->select_ok) {
      ++n_badstats_sources;
      sources[i]->status = SRC_BAD_STATS;
      if (max_badstat_reach < sources[i]->reachability)
        max_badstat_reach = sources[i]->reachability;
      continue;
    }

    /* Include extra dispersion in the root distance of sources that don't
       have new samples (the last sample is older than span of all samples) */
    if (first_sample_ago < 2.0 * si->last_sample_ago) {
      double extra_disp = LCL_GetMaxClockError() *
                          (2.0 * si->last_sample_ago - first_sample_ago);
      si->root_distance += extra_disp;
      si->lo_limit -= extra_disp;
      si->hi_limit += extra_disp;
    }

    /* Require the root distance to be below the allowed maximum */
    if (si->root_distance > max_distance) {
      sources[i]->status = SRC_BAD_DISTANCE;
      continue;
    }

    /* And the same applies for the estimated standard deviation */
    if (si->std_dev > max_jitter) {
      sources[i]->status = SRC_JITTERY;
      continue;
    }

    sources[i]->status = SRC_OK; /* For now */

    if (sources[i]->reachability && max_reach_sample_ago < first_sample_ago)
      max_reach_sample_ago = first_sample_ago;

    if (max_sel_reach < sources[i]->reachability)
      max_sel_reach = sources[i]->reachability;

    if (max_sel_reach_size < sources[i]->reachability_size)
      max_sel_reach_size = sources[i]->reachability_size;
  }

  orphan_stratum = REF_GetOrphanStratum();
  orphan_source = INVALID_SOURCE;

  for (i = 0; i < n_sources; i++) {
    if (sources[i]->status != SRC_OK)
      continue;

    si = &sources[i]->sel_info;

    /* Reachability is not a requirement for selection.  An unreachable source
       can still be selected if its newest sample is not older than the oldest
       sample from reachable sources. */
    if (!sources[i]->reachability && max_reach_sample_ago < si->last_sample_ago) {
      sources[i]->status = SRC_STALE;
      continue;
    }

    /* When the local reference is configured with the orphan option, NTP
       sources that have stratum equal to the configured local stratum are
       considered to be orphans (i.e. serving local time while not being
       synchronised with real time) and are excluded from the normal source
       selection.  Sources with stratum larger than the local stratum are
       considered to be directly on indirectly synchronised to an orphan and
       are always ignored.

       If no selectable source is available and all orphan sources have
       reference IDs larger than the local ID, no source will be selected and
       the local reference mode will be activated at some point, i.e. this host
       will become an orphan.  Otherwise, the orphan source with the smallest
       reference ID will be selected.  This ensures a group of servers polling
       each other (with the same orphan configuration) which have no external
       source can settle down to a state where only one server is serving its
       local unsychronised time and others are synchronised to it. */

    if (si->stratum >= orphan_stratum && sources[i]->type == SRC_NTP) {
      sources[i]->status = SRC_ORPHAN;

      if (si->stratum == orphan_stratum && sources[i]->reachability &&
          (orphan_source == INVALID_SOURCE ||
           sources[i]->ref_id < sources[orphan_source]->ref_id))
        orphan_source = i;

      continue;
    }

    ++n_sel_sources;
  }

  /* If no selectable source is available, consider the orphan source */
  if (!n_sel_sources && orphan_source != INVALID_SOURCE) {
    uint32_t local_ref_id = NSR_GetLocalRefid(sources[orphan_source]->ip_addr);

    if (!local_ref_id) {
      LOG(LOGS_ERR, "Unknown local refid in orphan mode");
    } else if (sources[orphan_source]->ref_id < local_ref_id) {
      sources[orphan_source]->status = SRC_OK;
      n_sel_sources = 1;
      DEBUG_LOG("selecting orphan refid=%"PRIx32, sources[orphan_source]->ref_id);
    }
  }

  for (i = 0; i < n_sources; i++) {
    if (sources[i]->status != SRC_OK)
      continue;

    si = &sources[i]->sel_info;

    j1 = n_endpoints;
    j2 = j1 + 1;

    sort_list[j1].index = i;
    sort_list[j1].offset = si->lo_limit;
    sort_list[j1].tag = LOW;

    sort_list[j2].index = i;
    sort_list[j2].offset = si->hi_limit;
    sort_list[j2].tag = HIGH;

    n_endpoints += 2;
  }

  DEBUG_LOG("badstat=%d sel=%d badstat_reach=%x sel_reach=%x size=%d max_reach_ago=%f",
            n_badstats_sources, n_sel_sources, (unsigned int)max_badstat_reach,
            (unsigned int)max_sel_reach, max_sel_reach_size, max_reach_sample_ago);

  /* Wait for the next call if we have no source selected and there is
     a source with bad stats (has less than 3 samples) with reachability
     equal to shifted maximum reachability of sources with valid stats.
     This delays selecting source on start with servers using the same
     polling interval until they all have valid stats. */
  if (n_badstats_sources && n_sel_sources && selected_source_index == INVALID_SOURCE &&
      max_sel_reach_size < SOURCE_REACH_BITS && max_sel_reach >> 1 == max_badstat_reach) {
    mark_ok_sources(SRC_WAITS_STATS);
    return;
  }

  if (n_endpoints == 0) {
    /* No sources provided valid endpoints */
    if (selected_source_index != INVALID_SOURCE) {
      log_selection_message("Can't synchronise: no selectable sources", NULL);
      selected_source_index = INVALID_SOURCE;
    }
    return;
  }

  /* Now sort the endpoint list */
  qsort((void *) sort_list, n_endpoints, sizeof(struct Sort_Element), compare_sort_elements);

  /* Now search for the interval which is contained in the most
     individual source intervals.  Any source which overlaps this
     will be a candidate.

     If we get a case like

     <----------------------->
         <-->
                  <-->
         <===========>

     we will build the interval as shown with '=', whereas with an extra source we get

     <----------------------->
        <------->
         <-->
                  <-->
         <==>

     The first case is just bad luck - we need extra sources to
     detect the falseticker, so just make an arbitrary choice based
     on stratum & stability etc.

     Intervals from sources specified with the trust option have higher
     priority in the search.
     */

  trust_depth = best_trust_depth = 0;
  depth = best_depth = 0;
  best_lo = best_hi = 0.0;

  for (i = 0; i < n_endpoints; i++) {
    switch (sort_list[i].tag) {
      case LOW:
        depth++;
        if (sources[sort_list[i].index]->sel_options & SRC_SELECT_TRUST)
          trust_depth++;
        if (trust_depth > best_trust_depth ||
            (trust_depth == best_trust_depth && depth > best_depth)) {
          best_trust_depth = trust_depth;
          best_depth = depth;
          best_lo = sort_list[i].offset;
        }
        break;
      case HIGH:
        if (trust_depth == best_trust_depth && depth == best_depth)
          best_hi = sort_list[i].offset;
        if (sources[sort_list[i].index]->sel_options & SRC_SELECT_TRUST)
          trust_depth--;
        depth--;
        break;
      default:
        assert(0);
    }
  }

  if (best_depth <= n_sel_sources / 2 && !best_trust_depth) {
    /* Could not even get half the reachable sources to agree and there
       are no trusted sources - clearly we can't synchronise */

    if (selected_source_index != INVALID_SOURCE) {
      log_selection_message("Can't synchronise: no majority", NULL);
      REF_SetUnsynchronised();
      selected_source_index = INVALID_SOURCE;
    }

    /* .. and mark all sources as falsetickers (so they appear thus
       on the outputs from the command client) */
    mark_ok_sources(SRC_FALSETICKER);

    return;
  }

  /* We have our interval, now work out which source are in it,
     i.e. build list of admissible sources. */

  n_sel_sources = 0;

  for (i = 0; i < n_sources; i++) {
    /* This should be the same condition to get into the endpoint
       list */
    if (sources[i]->status != SRC_OK)
      continue;

    /* Check if source's interval contains the best interval, or is wholly
       contained within it.  If there are any trusted sources the first
       condition is applied only to them to not allow non-trusted sources to
       move the final offset outside the interval. */
    if (((!best_trust_depth || sources[i]->sel_options & SRC_SELECT_TRUST) &&
         sources[i]->sel_info.lo_limit <= best_lo &&
         sources[i]->sel_info.hi_limit >= best_hi) ||
        (sources[i]->sel_info.lo_limit >= best_lo &&
         sources[i]->sel_info.hi_limit <= best_hi)) {

      sel_sources[n_sel_sources++] = i;

      if (sources[i]->sel_options & SRC_SELECT_REQUIRE)
        sel_req_source = 0;
    } else if (sources[i]->sel_info.lo_limit <= best_lo &&
               sources[i]->sel_info.hi_limit >= best_hi) {
      sources[i]->status = SRC_UNTRUSTED;
    } else {
      sources[i]->status = SRC_FALSETICKER;
    }
  }

  if (!n_sel_sources || sel_req_source || n_sel_sources < CNF_GetMinSources()) {
    if (selected_source_index != INVALID_SOURCE) {
      log_selection_message("Can't synchronise: %s selectable sources",
                            !n_sel_sources ? "no" :
                            sel_req_source ? "no required source in" : "not enough");
      selected_source_index = INVALID_SOURCE;
    }
    mark_ok_sources(SRC_WAITS_SOURCES);
    return;
  }

  /* Accept leap second status if more than half of selectable (and trusted
     if there are any) sources agree */
  for (i = leap_ins = leap_del = leap_votes = 0; i < n_sel_sources; i++) {
    index = sel_sources[i];
    if (best_trust_depth && !(sources[index]->sel_options & SRC_SELECT_TRUST))
      continue;
    leap_votes++;
    if (sources[index]->sel_info.leap == LEAP_InsertSecond)
      leap_ins++;
    else if (sources[index]->sel_info.leap == LEAP_DeleteSecond)
      leap_del++;
  }

  if (leap_ins > leap_votes / 2)
    leap_status = LEAP_InsertSecond;
  else if (leap_del > leap_votes / 2)
    leap_status = LEAP_DeleteSecond;
  else
    leap_status = LEAP_Normal;

  /* If there are any sources with prefer option, reduce the list again
     only to the preferred sources */
  for (i = 0; i < n_sel_sources; i++) {
    if (sources[sel_sources[i]]->sel_options & SRC_SELECT_PREFER)
      break;
  }
  if (i < n_sel_sources) {
    for (i = j = 0; i < n_sel_sources; i++) {
      if (!(sources[sel_sources[i]]->sel_options & SRC_SELECT_PREFER))
        sources[sel_sources[i]]->status = SRC_NONPREFERRED;
      else
        sel_sources[j++] = sel_sources[i];
    }
    assert(j > 0);
    n_sel_sources = j;
    sel_prefer = 1;
  } else {
    sel_prefer = 0;
  }

  /* Find minimum stratum */

  index = sel_sources[0];
  min_stratum = sources[index]->sel_info.stratum;
  for (i = 1; i < n_sel_sources; i++) {
    index = sel_sources[i];
    stratum = sources[index]->sel_info.stratum;
    if (stratum < min_stratum)
      min_stratum = stratum;
  }

  /* Update scores and find the source with maximum score */

  max_score_index = INVALID_SOURCE;
  max_score = 0.0;
  sel_src_distance = 0.0;

  if (selected_source_index != INVALID_SOURCE)
    sel_src_distance = sources[selected_source_index]->sel_info.root_distance +
      (sources[selected_source_index]->sel_info.stratum - min_stratum) * stratum_weight;

  for (i = 0; i < n_sources; i++) {
    /* Reset score for non-selectable sources */
    if (sources[i]->status != SRC_OK ||
        (sel_prefer && !(sources[i]->sel_options & SRC_SELECT_PREFER))) {
      sources[i]->sel_score = 1.0;
      sources[i]->distant = DISTANT_PENALTY;
      continue;
    }

    distance = sources[i]->sel_info.root_distance +
      (sources[i]->sel_info.stratum - min_stratum) * stratum_weight;
    if (sources[i]->type == SRC_NTP)
      distance += reselect_distance;

    if (selected_source_index != INVALID_SOURCE) {
      /* Update score, but only for source pairs where one source
         has a new sample */
      if (sources[i] == updated_inst ||
          sources[selected_source_index] == updated_inst) {

        sources[i]->sel_score *= sel_src_distance / distance;

        if (sources[i]->sel_score < 1.0)
          sources[i]->sel_score = 1.0;
      }
    } else {
      /* When there is no selected source yet, assign scores so that the
         source with minimum distance will have maximum score.  The scores
         will be reset when the source is selected later in this function. */
      sources[i]->sel_score = 1.0 / distance;
    }

    DEBUG_LOG("select score=%f refid=%"PRIx32" match_refid=%"PRIx32" status=%u dist=%f",
              sources[i]->sel_score, sources[i]->ref_id,
              updated_inst ? updated_inst->ref_id : 0,
              sources[i]->status, distance);

    if (max_score < sources[i]->sel_score) {
      max_score = sources[i]->sel_score;
      max_score_index = i;
    }
  }

  assert(max_score_index != INVALID_SOURCE);

  /* Is the current source still a survivor and no other source has reached
     the score limit? */
  if (selected_source_index == INVALID_SOURCE ||
      sources[selected_source_index]->status != SRC_OK ||
      (max_score_index != selected_source_index && max_score > SCORE_LIMIT)) {

    /* Before selecting the new synchronisation source wait until the reference
       can be updated */
    if (sources[max_score_index]->updates == 0) {
      selected_source_index = INVALID_SOURCE;
      mark_ok_sources(SRC_WAITS_UPDATE);
      DEBUG_LOG("best source has no updates");
      return;
    }

    selected_source_index = max_score_index;
    log_selection_message("Selected source %s",
                          source_to_string(sources[selected_source_index]));

    /* New source has been selected, reset all scores */
    for (i = 0; i < n_sources; i++) {
      sources[i]->sel_score = 1.0;
      sources[i]->distant = 0;
    }
  }

  sources[selected_source_index]->status = SRC_SELECTED;

  /* Don't update reference when the selected source has no new samples */

  if (sources[selected_source_index]->updates == 0) {
    /* Mark the remaining sources as last combine_sources() call */

    for (i = 0; i < n_sel_sources; i++) {
      index = sel_sources[i];
      if (sources[index]->status == SRC_OK)
        sources[index]->status = sources[index]->distant ?
                                 SRC_DISTANT : SRC_UNSELECTED;
    }
    return;
  }

  for (i = 0; i < n_sources; i++)
    sources[i]->updates = 0;

  /* Now just use the statistics of the selected source combined with
     the other selectable sources for trimming the local clock */

  SST_GetTrackingData(sources[selected_source_index]->stats, &ref_time,
                      &src_offset, &src_offset_sd,
                      &src_frequency, &src_frequency_sd, &src_skew,
                      &src_root_delay, &src_root_dispersion);

  combined = combine_sources(n_sel_sources, &ref_time, &src_offset, &src_offset_sd,
                             &src_frequency, &src_frequency_sd, &src_skew);

  REF_SetReference(sources[selected_source_index]->sel_info.stratum,
                   leap_status, combined,
                   sources[selected_source_index]->ref_id,
                   sources[selected_source_index]->ip_addr,
                   &ref_time, src_offset, src_offset_sd,
                   src_frequency, src_frequency_sd, src_skew,
                   src_root_delay, src_root_dispersion);
}