Parallel relaycrypt data structures for review
Please review first draft proposed parallel relaycrypt structures in my parallel_relay_crypt branch. -- Andrea Shepard <andrea@torproject.org> PGP fingerprint: 3611 95A4 0740 ED1B 7EA5 DF7E 4191 13D9 D0CF BDA5
On Nov 29, 2012 9:30 PM, "Andrea Shepard" <andrea@torproject.org> wrote:
Please review first draft proposed parallel relaycrypt structures in my parallel_relay_crypt branch.
Hi! Here are some initial thoughts: * If we're going to do it like this, maybe we need to make cell_t packed or something eventually. It's got a fair amount of padding overhead right now. * Maybe we'll need a next pointer in cells if we're queueing them? * Why is there only an rc_job for outgoing cells on a circuit? It seems for symmetry we'd need to have one for inbound cells and one for outbound cells. It looks like that code isn't there right now? * Maybe I'm confused by these queues. The system of cell queues is going to get a little confusing, maybe. Putting cells on the outgoing queue isn't always right, since some cells (e.g., relay_data cells at an exit node) need to be handled locally rather than relaying them. So we need more new queues? * Should the jobs be in some data structure other than an smartlist_t? A queue would seem to make more sense, since jobs are getting added and pulled off. (Yes, protecting the data structure there with a lock makes sense.) * If you're going to have separate locks, it's important to document how they nest, to prevent deadlock conditions. * Presumably relaycrypt_job_t would need to have a pointer to the actual circuit that needs work, and a note about whether it's a job for outbound or inbound cells. * In the non-threaded-relaycrypt case, presumably the intention is that there's a function that would otherwise queue a cell for crypto but instead just put it directly on the appropriate circuit queue? Thanks again! I'll let you know if I think of anything else. yrs, -- Nick
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 Hi everyone, This is quite interesting. I wrote back an initial proposal for this kind of work in Tor and I'm happy to see some similarities :). I've attached to the email the ideas I had based on some discussions with Nick and reading the ticket #1749. (Sorry for any obvious huge English mistakes, it's not my primary language :) I remember a discussion about parallel relay cell crypto with Nick and there was an important thing which is to prioritize quiet circuit(s). This implies that once a cell is scheduled for crypto. processing, the dispatcher should somehow know the "noise" of the circuit and dispatch accordingly. It brings the concept of priority for cells/circuit in a parallel environment which makes dispatching a bit more tricky. (More inline). Nick Mathewson:
On Nov 29, 2012 9:30 PM, "Andrea Shepard" <andrea@torproject.org> wrote:
Please review first draft proposed parallel relaycrypt structures in my parallel_relay_crypt branch.
Hi! Here are some initial thoughts:
* If we're going to do it like this, maybe we need to make cell_t packed or something eventually. It's got a fair amount of padding overhead right now.
* Maybe we'll need a next pointer in cells if we're queueing them?
* Why is there only an rc_job for outgoing cells on a circuit? It seems for symmetry we'd need to have one for inbound cells and one for outbound cells. It looks like that code isn't there right now?
* Maybe I'm confused by these queues. The system of cell queues is going to get a little confusing, maybe. Putting cells on the outgoing queue isn't always right, since some cells (e.g., relay_data cells at an exit node) need to be handled locally rather than relaying them. So we need more new queues?
What about if the main thread, when dequeuing encrypted cells, could check that and decide if it goes outbound or stays locally for more processing ?
* Should the jobs be in some data structure other than an smartlist_t? A queue would seem to make more sense, since jobs are getting added and pulled off. (Yes, protecting the data structure there with a lock makes sense.)
I would also propose the use of a priority queue because (or at least) of the aforementioned use case.
* If you're going to have separate locks, it's important to document how they nest, to prevent deadlock conditions.
* Presumably relaycrypt_job_t would need to have a pointer to the actual circuit that needs work, and a note about whether it's a job for outbound or inbound cells.
Looks like there is ? ..
* In the non-threaded-relaycrypt case, presumably the intention is that there's a function that would otherwise queue a cell for crypto but instead just put it directly on the appropriate circuit queue?
Thanks again! I'll let you know if I think of anything else.
I have question/remark on the circuit_t pointer in relaycrypt_job_s structure. I wonder if a lock might be needed since if the circuit is closed but some cells are still being processed by a relaycrypt worker thread, simply setting the circ to NULL will not indicate the thread to stop using CPU for this invalid circuit. I don't really know if Tor as some kind of refcount mechanism for circuits but in my experience this is a "time trap" when setting a pointer to NULL but still using some objects associated to that pointer. The cleanup becomes a nightmare if a thread still has ref. to some circuit's object which is invalidated when holding them. Would it be safer to simply have a STOP/CANCEL mechanism for worker thread and avoid nullifying references that might be in used? That's it for now. I'm quite happy to see this work going forward! :) Cheers! David
yrs,
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQEcBAEBCgAGBQJQuNqNAAoJEELoaioR9I025KMIALXE81lm0zpTRUWlM52HawyD lGVBqMRf/V+F/g8EFqGpyZ3drs9o3+uNhY7/+qdSY6IhWJGUfyL7vrwYSk1/yuBf RWBFE050zLhd9QwCARCoxb0E+oGsh/Z6hq8NgcDxba28Z2II+azE3KrNkwAuUnob N/6gUd8ceWpyXmFgCpf3MJLNqZKOcYXax2LFA+ocQdQ368VD+Lq8jqPXfR62Npr4 Ujhp9i2REALbbV6dOmxBVdytK9v2NfFGZIXp9n5onU8/Ym9a8fg0ZvUk+i5bwb+6 eOCYeLeVe7yNK8yzxnk6J8TbwuCRMLTSIhEfov6f+WgQYR9hfmBcY7shqFvpef4= =OQrF -----END PGP SIGNATURE-----
On Fri, Nov 30, 2012 at 08:12:10AM -0500, Nick Mathewson wrote:
Hi! Here are some initial thoughts:
* If we're going to do it like this, maybe we need to make cell_t packed or something eventually. It's got a fair amount of padding overhead right now.
Yeah - but relay_crypt() wants a cell_t, so we'd have to unpack and repack then.
* Maybe we'll need a next pointer in cells if we're queueing them?
Hmmm - yeah, I think that could be made to work. I'm mostly concerned with avoiding having to have the main thread/worker thread either hold a lock for the entire time it takes to crypt a bunch of cells/pull them off the out queue
* Why is there only an rc_job for outgoing cells on a circuit? It seems for symmetry we'd need to have one for inbound cells and one for outbound cells. It looks like that code isn't there right now?
I was trying to figure out if we can simplify it by just using the queue for the other circuit, but yeah, think it is necessary to make rc_jobs (circuit_t, cell_direction_t) tuples.
* Maybe I'm confused by these queues. The system of cell queues is going to get a little confusing, maybe. Putting cells on the outgoing queue isn't always right, since some cells (e.g., relay_data cells at an exit node) need to be handled locally rather than relaying them. So we need more new queues?
The outgoing queue is the queue of crypted cells for the main thread to pick up; it isn't the same as the circuit outgoing queue because a circuit might get closed while a worker is active, and because the thing to do after the cell is crypted is a bit complicated and I wanted to minimize the number of other things that would end up being called from the worker thread. See circuit_receive_relay_cell() in relay.c; if the cell is 'recognized', it gets special handling, or else it goes on the queue for the circuit. That logic would move to the second half of the main-thread processing, after the cell is removed from the rc_job output queue.
* Should the jobs be in some data structure other than an smartlist_t? A queue would seem to make more sense, since jobs are getting added and pulled off. (Yes, protecting the data structure there with a lock makes sense.)
Yeah, I just said that as a placeholder - what's really best surely depends on the selection policy.
* If you're going to have separate locks, it's important to document how they nest, to prevent deadlock conditions.
Yeah - I specified always lock the relaycrypt_dispatcher_t, then the relaycrypt_job_t in the comments, I believe.
* Presumably relaycrypt_job_t would need to have a pointer to the actual circuit that needs work, and a note about whether it's a job for outbound or inbound cells.
Well, it shouldn't be messing with the circuit too much because then a lot of other stuff that touches the circuit also needs to worry about being thread-safe, and the case of a circuit being shut down while a worker is active gets hairy. The worker will only be touching the queues in the rc_job, but it will need the circuit for the call to relay_crypt() - hmm, we need a way to make sure the crypto keys don't get freed out from under it if a circuit goes away.
* In the non-threaded-relaycrypt case, presumably the intention is that there's a function that would otherwise queue a cell for crypto but instead just put it directly on the appropriate circuit queue?
Yeah - the non-thready version would just call whatever (possibly refactored) relay_crypt() that the worker thread calls and then the handler for crypted cells, all in the main thread, rather than queueing anything.
Thanks again! I'll let you know if I think of anything else.
Okay, thanks. I'm trying to get some code started this weekend, I think. -- Andrea Shepard <andrea@torproject.org> PGP fingerprint: 3611 95A4 0740 ED1B 7EA5 DF7E 4191 13D9 D0CF BDA5
participants (3)
-
Andrea Shepard -
David Goulet -
Nick Mathewson