Opened 6 years ago

Last modified 22 months ago

#7479 new defect

Replace more linked lists with queue.h implementations

Reported by: nickm Owned by:
Priority: Low Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay refactoring easy intro
Cc: catalyst Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

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.

Child Tickets

Change History (7)

comment:1 Changed 22 months ago by nickm

Keywords: easy intro added
Severity: Normal

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!)

comment:2 in reply to:  1 Changed 22 months ago by arma

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);

comment:3 Changed 22 months ago by nickm

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

comment:4 in reply to:  3 ; Changed 22 months ago by 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.

(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. :)

comment:5 in reply to:  4 ; Changed 22 months ago by nickm

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

comment:6 in reply to:  5 Changed 22 months ago by arma

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.

comment:7 Changed 22 months ago by catalyst

Cc: catalyst added
Note: See TracTickets for help on using tickets.