Replace more linked lists with queue.h implementations

We've got linked lists scattered through our source. Now that we have a queue.h implementation, it would be neat to use that instead.

This is something we can (and should!) do piecemeal; let's not try to do it all with one big patch.

changed milestone to %Tor: unspecified

added component::core tor/tor easy intro milestone::Tor: unspecified priority::low refactoring severity::normal status::new technical-debt tor-relay type::defect labels

Good candidates include:

• sandbox_cfg_elem
• chunk_t
• pending_connection_t
• edge_connection_t.next_stream
• vote_microdesc_hash_t
• memarea_chunk_t
• logfile_t

Tricky candidates include:

• circuit_t.next_active_on_p_chan; circuit_t.next_active_on_n_chan (need to keep these lists separate.)
• crypt_path_t (weird circular list. I forget why it is circular.)
• config_line_t (used many places; watch out!)

Trac:
Sponsor: N/A to N/A
Keywords: tor-relay refactoring deleted, tor-relay refactoring easy intro added
Severity: N/A to Normal
Reviewer: N/A to N/A

Replying to nickm:

• crypt_path_t (weird circular list. I forget why it is circular.)

It is almost entirely so we can have easy access to "the last hop in the circuit" just by looking at cpath->prev.

There are a couple of places where we use the reverse links, e.g.

  if (circ->cpath &&
      circ->cpath->prev->state != CPATH_STATE_OPEN &&
      circ->cpath->prev->prev->state == CPATH_STATE_OPEN) {
    failed_at_last_hop = 1;
  }

but those could probably be refactored or just turned into a more brute force walk over the forward list, if we needed.

Though, check out this use in circuit_package_relay_cell() where it is honestly more convenient to be able to walk backwards on the list:

    thishop = layer_hint;
    /* moving from farthest to nearest hop */
    do {
      tor_assert(thishop);
      log_debug(LD_OR,"crypting a layer of the relay cell.");
      if (relay_crypt_one_payload(thishop->f_crypto, cell->payload, 1) < 0) {
        return -1;
      }

      thishop = thishop->prev;
    } while (thishop != TO_ORIGIN_CIRCUIT(circ)->cpath->prev);

Sounds like a double-linked list might work there then.

Replying to nickm:

Sounds like a double-linked list might work there then.

If we're ok walking to the end of the list each time we need to interact with the end (which is a big part of what we do with cpaths), sure.

(To be clear, I think the difference between a doubly-linked list and a circular list is that the doubly-linked list ends, and begins, whereas the circular list has a link from the tail to the head, and from the head to the tail? Just to make sure we're using the same terms. :)

Replying to arma:

Replying to nickm:

Sounds like a double-linked list might work there then.

If we're ok walking to the end of the list each time we need to interact with the end (which is a big part of what we do with cpaths), sure.

The BSD TAILQ_* type is exactly what one wants. It's a doubly-linked list with a head pointer to the first and to the last. See src/ext/tor_queue.h

Replying to nickm:

If we're ok walking to the end of the list each time we need to interact with the end (which is a big part of what we do with cpaths), sure.

The BSD TAILQ_* type is exactly what one wants. It's a doubly-linked list with a head pointer to the first and to the last. See src/ext/tor_queue.h

Awesome. I agree that sounds like exactly the data structure we're already (wishing we were) using.

Trac:
Cc: N/A to catalyst

#31179 (moved) is a duplicate

Trac:
Cc: catalyst to catalyst, teor

Trac:
Keywords: tor-relay refactoring easy intro deleted, tor-relay refactoring easy intro technical-debt added

mentioned in issue #31074 (moved)

mentioned in issue #31179 (moved)

moved to tpo/core/tor#7479 (closed)