12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642 |
- /* Copyright 2001 Matej Pfajfar.
- * Copyright (c) 2001-2004, Roger Dingledine.
- * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2017, The Tor Project, Inc. */
- /* See LICENSE for licensing information */
- /**
- * \file circuitlist.c
- *
- * \brief Manage global structures that list and index circuits, and
- * look up circuits within them.
- *
- * One of the most frequent operations in Tor occurs every time that
- * a relay cell arrives on a channel. When that happens, we need to
- * find which circuit it is associated with, based on the channel and the
- * circuit ID in the relay cell.
- *
- * To handle that, we maintain a global list of circuits, and a hashtable
- * mapping [channel,circID] pairs to circuits. Circuits are added to and
- * removed from this mapping using circuit_set_p_circid_chan() and
- * circuit_set_n_circid_chan(). To look up a circuit from this map, most
- * callers should use circuit_get_by_circid_channel(), though
- * circuit_get_by_circid_channel_even_if_marked() is appropriate under some
- * circumstances.
- *
- * We also need to allow for the possibility that we have blocked use of a
- * circuit ID (because we are waiting to send a DESTROY cell), but the
- * circuit is not there any more. For that case, we allow placeholder
- * entries in the table, using channel_mark_circid_unusable().
- *
- * To efficiently handle a channel that has just opened, we also maintain a
- * list of the circuits waiting for channels, so we can attach them as
- * needed without iterating through the whole list of circuits, using
- * circuit_get_all_pending_on_channel().
- *
- * In this module, we also handle the list of circuits that have been
- * marked for close elsewhere, and close them as needed. (We use this
- * "mark now, close later" pattern here and elsewhere to avoid
- * unpredictable recursion if we closed every circuit immediately upon
- * realizing it needed to close.) See circuit_mark_for_close() for the
- * mark function, and circuit_close_all_marked() for the close function.
- *
- * For hidden services, we need to be able to look up introduction point
- * circuits and rendezvous circuits by cookie, key, etc. These are
- * currently handled with linear searches in
- * circuit_get_ready_rend_circuit_by_rend_data(),
- * circuit_get_next_by_pk_and_purpose(), and with hash lookups in
- * circuit_get_rendezvous() and circuit_get_intro_point().
- *
- * This module is also the entry point for our out-of-memory handler
- * logic, which was originally circuit-focused.
- **/
- #define CIRCUITLIST_PRIVATE
- #include "torint.h" /* TOR_PRIuSZ */
- #include "or.h"
- #include "channel.h"
- #include "circpathbias.h"
- #include "circuitbuild.h"
- #include "circuitlist.h"
- #include "circuituse.h"
- #include "circuitstats.h"
- #include "connection.h"
- #include "config.h"
- #include "connection_edge.h"
- #include "connection_or.h"
- #include "control.h"
- #include "entrynodes.h"
- #include "main.h"
- #include "hs_circuit.h"
- #include "hs_circuitmap.h"
- #include "hs_ident.h"
- #include "networkstatus.h"
- #include "nodelist.h"
- #include "onion.h"
- #include "onion_fast.h"
- #include "policies.h"
- #include "relay.h"
- #include "rendclient.h"
- #include "rendcommon.h"
- #include "rephist.h"
- #include "routerlist.h"
- #include "routerset.h"
- #include "channelpadding.h"
- #include "ht.h"
- /********* START VARIABLES **********/
- /** A global list of all circuits at this hop. */
- static smartlist_t *global_circuitlist = NULL;
- /** A global list of all origin circuits. Every element of this is also
- * an element of global_circuitlist. */
- static smartlist_t *global_origin_circuit_list = NULL;
- /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
- static smartlist_t *circuits_pending_chans = NULL;
- /** List of all the (origin) circuits whose state is
- * CIRCUIT_STATE_GUARD_WAIT. */
- static smartlist_t *circuits_pending_other_guards = NULL;
- /** A list of all the circuits that have been marked with
- * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
- static smartlist_t *circuits_pending_close = NULL;
- static void circuit_free_cpath_node(crypt_path_t *victim);
- static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
- static void circuit_about_to_free_atexit(circuit_t *circ);
- static void circuit_about_to_free(circuit_t *circ);
- /**
- * A cached value of the current state of the origin circuit list. Has the
- * value 1 if we saw any opened circuits recently (since the last call to
- * circuit_any_opened_circuits(), which gets called around once a second by
- * circuit_expire_building). 0 otherwise.
- */
- static int any_opened_circs_cached_val = 0;
- /********* END VARIABLES ************/
- /** A map from channel and circuit ID to circuit. (Lookup performance is
- * very important here, since we need to do it every time a cell arrives.) */
- typedef struct chan_circid_circuit_map_t {
- HT_ENTRY(chan_circid_circuit_map_t) node;
- channel_t *chan;
- circid_t circ_id;
- circuit_t *circuit;
- /* For debugging 12184: when was this placeholder item added? */
- time_t made_placeholder_at;
- } chan_circid_circuit_map_t;
- /** Helper for hash tables: compare the channel and circuit ID for a and
- * b, and return less than, equal to, or greater than zero appropriately.
- */
- static inline int
- chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
- chan_circid_circuit_map_t *b)
- {
- return a->chan == b->chan && a->circ_id == b->circ_id;
- }
- /** Helper: return a hash based on circuit ID and the pointer value of
- * chan in <b>a</b>. */
- static inline unsigned int
- chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
- {
- /* Try to squeze the siphash input into 8 bytes to save any extra siphash
- * rounds. This hash function is in the critical path. */
- uintptr_t chan = (uintptr_t) (void*) a->chan;
- uint32_t array[2];
- array[0] = a->circ_id;
- /* The low bits of the channel pointer are uninteresting, since the channel
- * is a pretty big structure. */
- array[1] = (uint32_t) (chan >> 6);
- return (unsigned) siphash24g(array, sizeof(array));
- }
- /** Map from [chan,circid] to circuit. */
- static HT_HEAD(chan_circid_map, chan_circid_circuit_map_t)
- chan_circid_map = HT_INITIALIZER();
- HT_PROTOTYPE(chan_circid_map, chan_circid_circuit_map_t, node,
- chan_circid_entry_hash_, chan_circid_entries_eq_)
- HT_GENERATE2(chan_circid_map, chan_circid_circuit_map_t, node,
- chan_circid_entry_hash_, chan_circid_entries_eq_, 0.6,
- tor_reallocarray_, tor_free_)
- /** The most recently returned entry from circuit_get_by_circid_chan;
- * used to improve performance when many cells arrive in a row from the
- * same circuit.
- */
- static chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
- /** Implementation helper for circuit_set_{p,n}_circid_channel: A circuit ID
- * and/or channel for circ has just changed from <b>old_chan, old_id</b>
- * to <b>chan, id</b>. Adjust the chan,circid map as appropriate, removing
- * the old entry (if any) and adding a new one. */
- static void
- circuit_set_circid_chan_helper(circuit_t *circ, int direction,
- circid_t id,
- channel_t *chan)
- {
- chan_circid_circuit_map_t search;
- chan_circid_circuit_map_t *found;
- channel_t *old_chan, **chan_ptr;
- circid_t old_id, *circid_ptr;
- int make_active, attached = 0;
- if (direction == CELL_DIRECTION_OUT) {
- chan_ptr = &circ->n_chan;
- circid_ptr = &circ->n_circ_id;
- make_active = circ->n_chan_cells.n > 0;
- } else {
- or_circuit_t *c = TO_OR_CIRCUIT(circ);
- chan_ptr = &c->p_chan;
- circid_ptr = &c->p_circ_id;
- make_active = c->p_chan_cells.n > 0;
- }
- old_chan = *chan_ptr;
- old_id = *circid_ptr;
- if (id == old_id && chan == old_chan)
- return;
- if (_last_circid_chan_ent &&
- ((old_id == _last_circid_chan_ent->circ_id &&
- old_chan == _last_circid_chan_ent->chan) ||
- (id == _last_circid_chan_ent->circ_id &&
- chan == _last_circid_chan_ent->chan))) {
- _last_circid_chan_ent = NULL;
- }
- if (old_chan) {
- /*
- * If we're changing channels or ID and had an old channel and a non
- * zero old ID and weren't marked for close (i.e., we should have been
- * attached), detach the circuit. ID changes require this because
- * circuitmux hashes on (channel_id, circuit_id).
- */
- if (old_id != 0 && (old_chan != chan || old_id != id) &&
- !(circ->marked_for_close)) {
- tor_assert(old_chan->cmux);
- circuitmux_detach_circuit(old_chan->cmux, circ);
- }
- /* we may need to remove it from the conn-circid map */
- search.circ_id = old_id;
- search.chan = old_chan;
- found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
- if (found) {
- tor_free(found);
- if (direction == CELL_DIRECTION_OUT) {
- /* One fewer circuits use old_chan as n_chan */
- --(old_chan->num_n_circuits);
- } else {
- /* One fewer circuits use old_chan as p_chan */
- --(old_chan->num_p_circuits);
- }
- }
- }
- /* Change the values only after we have possibly made the circuit inactive
- * on the previous chan. */
- *chan_ptr = chan;
- *circid_ptr = id;
- if (chan == NULL)
- return;
- /* now add the new one to the conn-circid map */
- search.circ_id = id;
- search.chan = chan;
- found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
- if (found) {
- found->circuit = circ;
- found->made_placeholder_at = 0;
- } else {
- found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
- found->circ_id = id;
- found->chan = chan;
- found->circuit = circ;
- HT_INSERT(chan_circid_map, &chan_circid_map, found);
- }
- /*
- * Attach to the circuitmux if we're changing channels or IDs and
- * have a new channel and ID to use and the circuit is not marked for
- * close.
- */
- if (chan && id != 0 && (old_chan != chan || old_id != id) &&
- !(circ->marked_for_close)) {
- tor_assert(chan->cmux);
- circuitmux_attach_circuit(chan->cmux, circ, direction);
- attached = 1;
- }
- /*
- * This is a no-op if we have no cells, but if we do it marks us active to
- * the circuitmux
- */
- if (make_active && attached)
- update_circuit_on_cmux(circ, direction);
- /* Adjust circuit counts on new channel */
- if (direction == CELL_DIRECTION_OUT) {
- ++chan->num_n_circuits;
- } else {
- ++chan->num_p_circuits;
- }
- }
- /** Mark that circuit id <b>id</b> shouldn't be used on channel <b>chan</b>,
- * even if there is no circuit on the channel. We use this to keep the
- * circuit id from getting re-used while we have queued but not yet sent
- * a destroy cell. */
- void
- channel_mark_circid_unusable(channel_t *chan, circid_t id)
- {
- chan_circid_circuit_map_t search;
- chan_circid_circuit_map_t *ent;
- /* See if there's an entry there. That wouldn't be good. */
- memset(&search, 0, sizeof(search));
- search.chan = chan;
- search.circ_id = id;
- ent = HT_FIND(chan_circid_map, &chan_circid_map, &search);
- if (ent && ent->circuit) {
- /* we have a problem. */
- log_warn(LD_BUG, "Tried to mark %u unusable on %p, but there was already "
- "a circuit there.", (unsigned)id, chan);
- } else if (ent) {
- /* It's already marked. */
- if (!ent->made_placeholder_at)
- ent->made_placeholder_at = approx_time();
- } else {
- ent = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
- ent->chan = chan;
- ent->circ_id = id;
- /* leave circuit at NULL. */
- ent->made_placeholder_at = approx_time();
- HT_INSERT(chan_circid_map, &chan_circid_map, ent);
- }
- }
- /** Mark that a circuit id <b>id</b> can be used again on <b>chan</b>.
- * We use this to re-enable the circuit ID after we've sent a destroy cell.
- */
- void
- channel_mark_circid_usable(channel_t *chan, circid_t id)
- {
- chan_circid_circuit_map_t search;
- chan_circid_circuit_map_t *ent;
- /* See if there's an entry there. That wouldn't be good. */
- memset(&search, 0, sizeof(search));
- search.chan = chan;
- search.circ_id = id;
- ent = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
- if (ent && ent->circuit) {
- log_warn(LD_BUG, "Tried to mark %u usable on %p, but there was already "
- "a circuit there.", (unsigned)id, chan);
- return;
- }
- if (_last_circid_chan_ent == ent)
- _last_circid_chan_ent = NULL;
- tor_free(ent);
- }
- /** Called to indicate that a DESTROY is pending on <b>chan</b> with
- * circuit ID <b>id</b>, but hasn't been sent yet. */
- void
- channel_note_destroy_pending(channel_t *chan, circid_t id)
- {
- circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan);
- if (circ) {
- if (circ->n_chan == chan && circ->n_circ_id == id) {
- circ->n_delete_pending = 1;
- } else {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
- circ->p_delete_pending = 1;
- }
- }
- return;
- }
- channel_mark_circid_unusable(chan, id);
- }
- /** Called to indicate that a DESTROY is no longer pending on <b>chan</b> with
- * circuit ID <b>id</b> -- typically, because it has been sent. */
- MOCK_IMPL(void,
- channel_note_destroy_not_pending,(channel_t *chan, circid_t id))
- {
- circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan);
- if (circ) {
- if (circ->n_chan == chan && circ->n_circ_id == id) {
- circ->n_delete_pending = 0;
- } else {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
- circ->p_delete_pending = 0;
- }
- }
- /* XXXX this shouldn't happen; log a bug here. */
- return;
- }
- channel_mark_circid_usable(chan, id);
- }
- /** Set the p_conn field of a circuit <b>circ</b>, along
- * with the corresponding circuit ID, and add the circuit as appropriate
- * to the (chan,id)-\>circuit map. */
- void
- circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id,
- channel_t *chan)
- {
- circuit_t *circ = TO_CIRCUIT(or_circ);
- channel_t *old_chan = or_circ->p_chan;
- circid_t old_id = or_circ->p_circ_id;
- circuit_set_circid_chan_helper(circ, CELL_DIRECTION_IN, id, chan);
- if (chan) {
- tor_assert(bool_eq(or_circ->p_chan_cells.n,
- or_circ->next_active_on_p_chan));
- chan->timestamp_last_had_circuits = approx_time();
- }
- if (circ->p_delete_pending && old_chan) {
- channel_mark_circid_unusable(old_chan, old_id);
- circ->p_delete_pending = 0;
- }
- }
- /** Set the n_conn field of a circuit <b>circ</b>, along
- * with the corresponding circuit ID, and add the circuit as appropriate
- * to the (chan,id)-\>circuit map. */
- void
- circuit_set_n_circid_chan(circuit_t *circ, circid_t id,
- channel_t *chan)
- {
- channel_t *old_chan = circ->n_chan;
- circid_t old_id = circ->n_circ_id;
- circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
- if (chan) {
- tor_assert(bool_eq(circ->n_chan_cells.n, circ->next_active_on_n_chan));
- chan->timestamp_last_had_circuits = approx_time();
- }
- if (circ->n_delete_pending && old_chan) {
- channel_mark_circid_unusable(old_chan, old_id);
- circ->n_delete_pending = 0;
- }
- }
- /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
- * it from lists as appropriate. */
- void
- circuit_set_state(circuit_t *circ, uint8_t state)
- {
- tor_assert(circ);
- if (state == circ->state)
- return;
- if (PREDICT_UNLIKELY(!circuits_pending_chans))
- circuits_pending_chans = smartlist_new();
- if (PREDICT_UNLIKELY(!circuits_pending_other_guards))
- circuits_pending_other_guards = smartlist_new();
- if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
- /* remove from waiting-circuit list. */
- smartlist_remove(circuits_pending_chans, circ);
- }
- if (state == CIRCUIT_STATE_CHAN_WAIT) {
- /* add to waiting-circuit list. */
- smartlist_add(circuits_pending_chans, circ);
- }
- if (circ->state == CIRCUIT_STATE_GUARD_WAIT) {
- smartlist_remove(circuits_pending_other_guards, circ);
- }
- if (state == CIRCUIT_STATE_GUARD_WAIT) {
- smartlist_add(circuits_pending_other_guards, circ);
- }
- if (state == CIRCUIT_STATE_GUARD_WAIT || state == CIRCUIT_STATE_OPEN)
- tor_assert(!circ->n_chan_create_cell);
- circ->state = state;
- }
- /** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
- * the given connection. */
- void
- circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
- {
- tor_assert(out);
- tor_assert(chan);
- if (!circuits_pending_chans)
- return;
- SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
- if (circ->marked_for_close)
- continue;
- if (!circ->n_hop)
- continue;
- tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
- if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
- /* Look at addr/port. This is an unkeyed connection. */
- if (!channel_matches_extend_info(chan, circ->n_hop))
- continue;
- } else {
- /* We expected a key. See if it's the right one. */
- if (tor_memneq(chan->identity_digest,
- circ->n_hop->identity_digest, DIGEST_LEN))
- continue;
- }
- smartlist_add(out, circ);
- } SMARTLIST_FOREACH_END(circ);
- }
- /** Return the number of circuits in state CHAN_WAIT, waiting for the given
- * channel. */
- int
- circuit_count_pending_on_channel(channel_t *chan)
- {
- int cnt;
- smartlist_t *sl = smartlist_new();
- tor_assert(chan);
- circuit_get_all_pending_on_channel(sl, chan);
- cnt = smartlist_len(sl);
- smartlist_free(sl);
- log_debug(LD_CIRC,"or_conn to %s, %d pending circs",
- channel_get_canonical_remote_descr(chan),
- cnt);
- return cnt;
- }
- /** Remove <b>origin_circ</b> from the global list of origin circuits.
- * Called when we are freeing a circuit.
- */
- static void
- circuit_remove_from_origin_circuit_list(origin_circuit_t *origin_circ)
- {
- int origin_idx = origin_circ->global_origin_circuit_list_idx;
- if (origin_idx < 0)
- return;
- origin_circuit_t *c2;
- tor_assert(origin_idx <= smartlist_len(global_origin_circuit_list));
- c2 = smartlist_get(global_origin_circuit_list, origin_idx);
- tor_assert(origin_circ == c2);
- smartlist_del(global_origin_circuit_list, origin_idx);
- if (origin_idx < smartlist_len(global_origin_circuit_list)) {
- origin_circuit_t *replacement =
- smartlist_get(global_origin_circuit_list, origin_idx);
- replacement->global_origin_circuit_list_idx = origin_idx;
- }
- origin_circ->global_origin_circuit_list_idx = -1;
- }
- /** Add <b>origin_circ</b> to the global list of origin circuits. Called
- * when creating the circuit. */
- static void
- circuit_add_to_origin_circuit_list(origin_circuit_t *origin_circ)
- {
- tor_assert(origin_circ->global_origin_circuit_list_idx == -1);
- smartlist_t *lst = circuit_get_global_origin_circuit_list();
- smartlist_add(lst, origin_circ);
- origin_circ->global_origin_circuit_list_idx = smartlist_len(lst) - 1;
- }
- /** Detach from the global circuit list, and deallocate, all
- * circuits that have been marked for close.
- */
- void
- circuit_close_all_marked(void)
- {
- if (circuits_pending_close == NULL)
- return;
- smartlist_t *lst = circuit_get_global_list();
- SMARTLIST_FOREACH_BEGIN(circuits_pending_close, circuit_t *, circ) {
- tor_assert(circ->marked_for_close);
- /* Remove it from the circuit list. */
- int idx = circ->global_circuitlist_idx;
- smartlist_del(lst, idx);
- if (idx < smartlist_len(lst)) {
- circuit_t *replacement = smartlist_get(lst, idx);
- replacement->global_circuitlist_idx = idx;
- }
- circ->global_circuitlist_idx = -1;
- /* Remove it from the origin circuit list, if appropriate. */
- if (CIRCUIT_IS_ORIGIN(circ)) {
- circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ));
- }
- circuit_about_to_free(circ);
- circuit_free(circ);
- } SMARTLIST_FOREACH_END(circ);
- smartlist_clear(circuits_pending_close);
- }
- /** Return a pointer to the global list of circuits. */
- MOCK_IMPL(smartlist_t *,
- circuit_get_global_list,(void))
- {
- if (NULL == global_circuitlist)
- global_circuitlist = smartlist_new();
- return global_circuitlist;
- }
- /** Return a pointer to the global list of origin circuits. */
- smartlist_t *
- circuit_get_global_origin_circuit_list(void)
- {
- if (NULL == global_origin_circuit_list)
- global_origin_circuit_list = smartlist_new();
- return global_origin_circuit_list;
- }
- /**
- * Return true if we have any opened general-purpose 3 hop
- * origin circuits.
- *
- * The result from this function is cached for use by
- * circuit_any_opened_circuits_cached().
- */
- int
- circuit_any_opened_circuits(void)
- {
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_origin_circuit_list(),
- const origin_circuit_t *, next_circ) {
- if (!TO_CIRCUIT(next_circ)->marked_for_close &&
- next_circ->has_opened &&
- TO_CIRCUIT(next_circ)->state == CIRCUIT_STATE_OPEN &&
- TO_CIRCUIT(next_circ)->purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT &&
- next_circ->build_state &&
- next_circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN) {
- circuit_cache_opened_circuit_state(1);
- return 1;
- }
- } SMARTLIST_FOREACH_END(next_circ);
- circuit_cache_opened_circuit_state(0);
- return 0;
- }
- /**
- * Cache the "any circuits opened" state, as specified in param
- * circuits_are_opened. This is a helper function to update
- * the circuit opened status whenever we happen to look at the
- * circuit list.
- */
- void
- circuit_cache_opened_circuit_state(int circuits_are_opened)
- {
- any_opened_circs_cached_val = circuits_are_opened;
- }
- /**
- * Return true if there were any opened circuits since the last call to
- * circuit_any_opened_circuits(), or since circuit_expire_building() last
- * ran (it runs roughly once per second).
- */
- int
- circuit_any_opened_circuits_cached(void)
- {
- return any_opened_circs_cached_val;
- }
- /** Function to make circ-\>state human-readable */
- const char *
- circuit_state_to_string(int state)
- {
- static char buf[64];
- switch (state) {
- case CIRCUIT_STATE_BUILDING: return "doing handshakes";
- case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
- case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
- case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other "
- "guards perform";
- case CIRCUIT_STATE_OPEN: return "open";
- default:
- log_warn(LD_BUG, "Unknown circuit state %d", state);
- tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
- return buf;
- }
- }
- /** Map a circuit purpose to a string suitable to be displayed to a
- * controller. */
- const char *
- circuit_purpose_to_controller_string(uint8_t purpose)
- {
- static char buf[32];
- switch (purpose) {
- case CIRCUIT_PURPOSE_OR:
- case CIRCUIT_PURPOSE_INTRO_POINT:
- case CIRCUIT_PURPOSE_REND_POINT_WAITING:
- case CIRCUIT_PURPOSE_REND_ESTABLISHED:
- return "SERVER"; /* A controller should never see these, actually. */
- case CIRCUIT_PURPOSE_C_GENERAL:
- return "GENERAL";
- case CIRCUIT_PURPOSE_C_INTRODUCING:
- case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
- case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
- return "HS_CLIENT_INTRO";
- case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
- case CIRCUIT_PURPOSE_C_REND_READY:
- case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
- case CIRCUIT_PURPOSE_C_REND_JOINED:
- return "HS_CLIENT_REND";
- case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
- case CIRCUIT_PURPOSE_S_INTRO:
- return "HS_SERVICE_INTRO";
- case CIRCUIT_PURPOSE_S_CONNECT_REND:
- case CIRCUIT_PURPOSE_S_REND_JOINED:
- return "HS_SERVICE_REND";
- case CIRCUIT_PURPOSE_TESTING:
- return "TESTING";
- case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
- return "MEASURE_TIMEOUT";
- case CIRCUIT_PURPOSE_CONTROLLER:
- return "CONTROLLER";
- case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
- return "PATH_BIAS_TESTING";
- default:
- tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
- return buf;
- }
- }
- /** Return a string specifying the state of the hidden-service circuit
- * purpose <b>purpose</b>, or NULL if <b>purpose</b> is not a
- * hidden-service-related circuit purpose. */
- const char *
- circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
- {
- switch (purpose)
- {
- default:
- log_fn(LOG_WARN, LD_BUG,
- "Unrecognized circuit purpose: %d",
- (int)purpose);
- tor_fragile_assert();
- /* fall through */
- case CIRCUIT_PURPOSE_OR:
- case CIRCUIT_PURPOSE_C_GENERAL:
- case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
- case CIRCUIT_PURPOSE_TESTING:
- case CIRCUIT_PURPOSE_CONTROLLER:
- case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
- return NULL;
- case CIRCUIT_PURPOSE_INTRO_POINT:
- return "OR_HSSI_ESTABLISHED";
- case CIRCUIT_PURPOSE_REND_POINT_WAITING:
- return "OR_HSCR_ESTABLISHED";
- case CIRCUIT_PURPOSE_REND_ESTABLISHED:
- return "OR_HS_R_JOINED";
- case CIRCUIT_PURPOSE_C_INTRODUCING:
- return "HSCI_CONNECTING";
- case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
- return "HSCI_INTRO_SENT";
- case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
- return "HSCI_DONE";
- case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
- return "HSCR_CONNECTING";
- case CIRCUIT_PURPOSE_C_REND_READY:
- return "HSCR_ESTABLISHED_IDLE";
- case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
- return "HSCR_ESTABLISHED_WAITING";
- case CIRCUIT_PURPOSE_C_REND_JOINED:
- return "HSCR_JOINED";
- case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
- return "HSSI_CONNECTING";
- case CIRCUIT_PURPOSE_S_INTRO:
- return "HSSI_ESTABLISHED";
- case CIRCUIT_PURPOSE_S_CONNECT_REND:
- return "HSSR_CONNECTING";
- case CIRCUIT_PURPOSE_S_REND_JOINED:
- return "HSSR_JOINED";
- }
- }
- /** Return a human-readable string for the circuit purpose <b>purpose</b>. */
- const char *
- circuit_purpose_to_string(uint8_t purpose)
- {
- static char buf[32];
- switch (purpose)
- {
- case CIRCUIT_PURPOSE_OR:
- return "Circuit at relay";
- case CIRCUIT_PURPOSE_INTRO_POINT:
- return "Acting as intro point";
- case CIRCUIT_PURPOSE_REND_POINT_WAITING:
- return "Acting as rendevous (pending)";
- case CIRCUIT_PURPOSE_REND_ESTABLISHED:
- return "Acting as rendevous (established)";
- case CIRCUIT_PURPOSE_C_GENERAL:
- return "General-purpose client";
- case CIRCUIT_PURPOSE_C_INTRODUCING:
- return "Hidden service client: Connecting to intro point";
- case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
- return "Hidden service client: Waiting for ack from intro point";
- case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
- return "Hidden service client: Received ack from intro point";
- case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
- return "Hidden service client: Establishing rendezvous point";
- case CIRCUIT_PURPOSE_C_REND_READY:
- return "Hidden service client: Pending rendezvous point";
- case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
- return "Hidden service client: Pending rendezvous point (ack received)";
- case CIRCUIT_PURPOSE_C_REND_JOINED:
- return "Hidden service client: Active rendezvous point";
- case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
- return "Measuring circuit timeout";
- case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
- return "Hidden service: Establishing introduction point";
- case CIRCUIT_PURPOSE_S_INTRO:
- return "Hidden service: Introduction point";
- case CIRCUIT_PURPOSE_S_CONNECT_REND:
- return "Hidden service: Connecting to rendezvous point";
- case CIRCUIT_PURPOSE_S_REND_JOINED:
- return "Hidden service: Active rendezvous point";
- case CIRCUIT_PURPOSE_TESTING:
- return "Testing circuit";
- case CIRCUIT_PURPOSE_CONTROLLER:
- return "Circuit made by controller";
- case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
- return "Path-bias testing circuit";
- default:
- tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
- return buf;
- }
- }
- /** Pick a reasonable package_window to start out for our circuits.
- * Originally this was hard-coded at 1000, but now the consensus votes
- * on the answer. See proposal 168. */
- int32_t
- circuit_initial_package_window(void)
- {
- int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
- CIRCWINDOW_START_MIN,
- CIRCWINDOW_START_MAX);
- /* If the consensus tells us a negative number, we'd assert. */
- if (num < 0)
- num = CIRCWINDOW_START;
- return num;
- }
- /** Initialize the common elements in a circuit_t, and add it to the global
- * list. */
- static void
- init_circuit_base(circuit_t *circ)
- {
- tor_gettimeofday(&circ->timestamp_created);
- // Gets reset when we send CREATE_FAST.
- // circuit_expire_building() expects these to be equal
- // until the orconn is built.
- circ->timestamp_began = circ->timestamp_created;
- circ->package_window = circuit_initial_package_window();
- circ->deliver_window = CIRCWINDOW_START;
- cell_queue_init(&circ->n_chan_cells);
- smartlist_add(circuit_get_global_list(), circ);
- circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
- }
- /** If we haven't yet decided on a good timeout value for circuit
- * building, we close idle circuits aggressively so we can get more
- * data points. */
- #define IDLE_TIMEOUT_WHILE_LEARNING (1*60)
- /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
- * and <b>p_conn</b>. Add it to the global circuit list.
- */
- origin_circuit_t *
- origin_circuit_new(void)
- {
- origin_circuit_t *circ;
- /* never zero, since a global ID of 0 is treated specially by the
- * controller */
- static uint32_t n_circuits_allocated = 1;
- circ = tor_malloc_zero(sizeof(origin_circuit_t));
- circ->base_.magic = ORIGIN_CIRCUIT_MAGIC;
- circ->next_stream_id = crypto_rand_int(1<<16);
- circ->global_identifier = n_circuits_allocated++;
- circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
- circ->remaining_relay_early_cells -= crypto_rand_int(2);
- init_circuit_base(TO_CIRCUIT(circ));
- /* Add to origin-list. */
- circ->global_origin_circuit_list_idx = -1;
- circuit_add_to_origin_circuit_list(circ);
- circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
- if (! circuit_build_times_disabled(get_options()) &&
- circuit_build_times_needs_circuits(get_circuit_build_times())) {
- /* Circuits should be shorter lived if we need more of them
- * for learning a good build timeout */
- circ->circuit_idle_timeout = IDLE_TIMEOUT_WHILE_LEARNING;
- } else {
- // This should always be larger than the current port prediction time
- // remaining, or else we'll end up with the case where a circuit times out
- // and another one is built, effectively doubling the timeout window.
- //
- // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds,
- // depending on how much circuit prediction time is remaining) so that
- // we don't close a bunch of unused circuits all at the same time.
- int prediction_time_remaining =
- predicted_ports_prediction_time_remaining(time(NULL));
- circ->circuit_idle_timeout = prediction_time_remaining+1+
- crypto_rand_int(1+prediction_time_remaining/20);
- if (circ->circuit_idle_timeout <= 0) {
- log_warn(LD_BUG,
- "Circuit chose a negative idle timeout of %d based on "
- "%d seconds of predictive building remaining.",
- circ->circuit_idle_timeout,
- prediction_time_remaining);
- circ->circuit_idle_timeout = IDLE_TIMEOUT_WHILE_LEARNING;
- }
- log_info(LD_CIRC,
- "Circuit " U64_FORMAT " chose an idle timeout of %d based on "
- "%d seconds of predictive building remaining.",
- U64_PRINTF_ARG(circ->global_identifier),
- circ->circuit_idle_timeout,
- prediction_time_remaining);
- }
- return circ;
- }
- /** Allocate a new or_circuit_t, connected to <b>p_chan</b> as
- * <b>p_circ_id</b>. If <b>p_chan</b> is NULL, the circuit is unattached. */
- or_circuit_t *
- or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
- {
- /* CircIDs */
- or_circuit_t *circ;
- circ = tor_malloc_zero(sizeof(or_circuit_t));
- circ->base_.magic = OR_CIRCUIT_MAGIC;
- if (p_chan)
- circuit_set_p_circid_chan(circ, p_circ_id, p_chan);
- circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
- cell_queue_init(&circ->p_chan_cells);
- init_circuit_base(TO_CIRCUIT(circ));
- return circ;
- }
- /** Free all storage held in circ->testing_cell_stats */
- void
- circuit_clear_testing_cell_stats(circuit_t *circ)
- {
- if (!circ || !circ->testing_cell_stats)
- return;
- SMARTLIST_FOREACH(circ->testing_cell_stats, testing_cell_stats_entry_t *,
- ent, tor_free(ent));
- smartlist_free(circ->testing_cell_stats);
- circ->testing_cell_stats = NULL;
- }
- /** Deallocate space associated with circ.
- */
- STATIC void
- circuit_free_(circuit_t *circ)
- {
- circid_t n_circ_id = 0;
- void *mem;
- size_t memlen;
- int should_free = 1;
- if (!circ)
- return;
- /* We keep a copy of this so we can log its value before it gets unset. */
- n_circ_id = circ->n_circ_id;
- circuit_clear_testing_cell_stats(circ);
- /* Cleanup circuit from anything HS v3 related. We also do this when the
- * circuit is closed. This is to avoid any code path that free registered
- * circuits without closing them before. This needs to be done before the
- * hs identifier is freed. */
- hs_circ_cleanup(circ);
- if (CIRCUIT_IS_ORIGIN(circ)) {
- origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
- mem = ocirc;
- memlen = sizeof(origin_circuit_t);
- tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC);
- circuit_remove_from_origin_circuit_list(ocirc);
- if (ocirc->build_state) {
- extend_info_free(ocirc->build_state->chosen_exit);
- circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
- cpath_ref_decref(ocirc->build_state->service_pending_final_cpath_ref);
- }
- tor_free(ocirc->build_state);
- /* Cancel before freeing, if we haven't already succeeded or failed. */
- if (ocirc->guard_state) {
- entry_guard_cancel(ô->guard_state);
- }
- circuit_guard_state_free(ocirc->guard_state);
- circuit_clear_cpath(ocirc);
- crypto_pk_free(ocirc->intro_key);
- rend_data_free(ocirc->rend_data);
- /* Finally, free the identifier of the circuit and nullify it so multiple
- * cleanup will work. */
- hs_ident_circuit_free(ocirc->hs_ident);
- ocirc->hs_ident = NULL;
- tor_free(ocirc->dest_address);
- if (ocirc->socks_username) {
- memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len);
- tor_free(ocirc->socks_username);
- }
- if (ocirc->socks_password) {
- memwipe(ocirc->socks_password, 0x06, ocirc->socks_password_len);
- tor_free(ocirc->socks_password);
- }
- addr_policy_list_free(ocirc->prepend_policy);
- } else {
- or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
- /* Remember cell statistics for this circuit before deallocating. */
- if (get_options()->CellStatistics)
- rep_hist_buffer_stats_add_circ(circ, time(NULL));
- mem = ocirc;
- memlen = sizeof(or_circuit_t);
- tor_assert(circ->magic == OR_CIRCUIT_MAGIC);
- should_free = (ocirc->workqueue_entry == NULL);
- crypto_cipher_free(ocirc->p_crypto);
- crypto_digest_free(ocirc->p_digest);
- crypto_cipher_free(ocirc->n_crypto);
- crypto_digest_free(ocirc->n_digest);
- if (ocirc->rend_splice) {
- or_circuit_t *other = ocirc->rend_splice;
- tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC);
- other->rend_splice = NULL;
- }
- /* remove from map. */
- circuit_set_p_circid_chan(ocirc, 0, NULL);
- /* Clear cell queue _after_ removing it from the map. Otherwise our
- * "active" checks will be violated. */
- cell_queue_clear(ô->p_chan_cells);
- }
- extend_info_free(circ->n_hop);
- tor_free(circ->n_chan_create_cell);
- if (circ->global_circuitlist_idx != -1) {
- int idx = circ->global_circuitlist_idx;
- circuit_t *c2 = smartlist_get(global_circuitlist, idx);
- tor_assert(c2 == circ);
- smartlist_del(global_circuitlist, idx);
- if (idx < smartlist_len(global_circuitlist)) {
- c2 = smartlist_get(global_circuitlist, idx);
- c2->global_circuitlist_idx = idx;
- }
- }
- /* Remove from map. */
- circuit_set_n_circid_chan(circ, 0, NULL);
- /* Clear cell queue _after_ removing it from the map. Otherwise our
- * "active" checks will be violated. */
- cell_queue_clear(&circ->n_chan_cells);
- log_info(LD_CIRC, "Circuit %u (id: %" PRIu32 ") has been freed.",
- n_circ_id,
- CIRCUIT_IS_ORIGIN(circ) ?
- TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0);
- if (should_free) {
- memwipe(mem, 0xAA, memlen); /* poison memory */
- tor_free(mem);
- } else {
- /* If we made it here, this is an or_circuit_t that still has a pending
- * cpuworker request which we weren't able to cancel. Instead, set up
- * the magic value so that when the reply comes back, we'll know to discard
- * the reply and free this structure.
- */
- memwipe(mem, 0xAA, memlen);
- circ->magic = DEAD_CIRCUIT_MAGIC;
- }
- }
- /** Deallocate the linked list circ-><b>cpath</b>, and remove the cpath from
- * <b>circ</b>. */
- void
- circuit_clear_cpath(origin_circuit_t *circ)
- {
- crypt_path_t *victim, *head, *cpath;
- head = cpath = circ->cpath;
- if (!cpath)
- return;
- /* it's a circular list, so we have to notice when we've
- * gone through it once. */
- while (cpath->next && cpath->next != head) {
- victim = cpath;
- cpath = victim->next;
- circuit_free_cpath_node(victim);
- }
- circuit_free_cpath_node(cpath);
- circ->cpath = NULL;
- }
- /** Release all storage held by circuits. */
- void
- circuit_free_all(void)
- {
- smartlist_t *lst = circuit_get_global_list();
- SMARTLIST_FOREACH_BEGIN(lst, circuit_t *, tmp) {
- if (! CIRCUIT_IS_ORIGIN(tmp)) {
- or_circuit_t *or_circ = TO_OR_CIRCUIT(tmp);
- while (or_circ->resolving_streams) {
- edge_connection_t *next_conn;
- next_conn = or_circ->resolving_streams->next_stream;
- connection_free_(TO_CONN(or_circ->resolving_streams));
- or_circ->resolving_streams = next_conn;
- }
- }
- tmp->global_circuitlist_idx = -1;
- circuit_about_to_free_atexit(tmp);
- circuit_free(tmp);
- SMARTLIST_DEL_CURRENT(lst, tmp);
- } SMARTLIST_FOREACH_END(tmp);
- smartlist_free(lst);
- global_circuitlist = NULL;
- smartlist_free(global_origin_circuit_list);
- global_origin_circuit_list = NULL;
- smartlist_free(circuits_pending_chans);
- circuits_pending_chans = NULL;
- smartlist_free(circuits_pending_close);
- circuits_pending_close = NULL;
- smartlist_free(circuits_pending_other_guards);
- circuits_pending_other_guards = NULL;
- {
- chan_circid_circuit_map_t **elt, **next, *c;
- for (elt = HT_START(chan_circid_map, &chan_circid_map);
- elt;
- elt = next) {
- c = *elt;
- next = HT_NEXT_RMV(chan_circid_map, &chan_circid_map, elt);
- tor_assert(c->circuit == NULL);
- tor_free(c);
- }
- }
- HT_CLEAR(chan_circid_map, &chan_circid_map);
- }
- /** Deallocate space associated with the cpath node <b>victim</b>. */
- static void
- circuit_free_cpath_node(crypt_path_t *victim)
- {
- if (!victim)
- return;
- crypto_cipher_free(victim->f_crypto);
- crypto_cipher_free(victim->b_crypto);
- crypto_digest_free(victim->f_digest);
- crypto_digest_free(victim->b_digest);
- onion_handshake_state_release(&victim->handshake_state);
- crypto_dh_free(victim->rend_dh_handshake_state);
- extend_info_free(victim->extend_info);
- memwipe(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
- tor_free(victim);
- }
- /** Release a crypt_path_reference_t*, which may be NULL. */
- static void
- cpath_ref_decref(crypt_path_reference_t *cpath_ref)
- {
- if (cpath_ref != NULL) {
- if (--(cpath_ref->refcount) == 0) {
- circuit_free_cpath_node(cpath_ref->cpath);
- tor_free(cpath_ref);
- }
- }
- }
- /** A helper function for circuit_dump_by_conn() below. Log a bunch
- * of information about circuit <b>circ</b>.
- */
- static void
- circuit_dump_conn_details(int severity,
- circuit_t *circ,
- int conn_array_index,
- const char *type,
- circid_t this_circid,
- circid_t other_circid)
- {
- tor_log(severity, LD_CIRC, "Conn %d has %s circuit: circID %u "
- "(other side %u), state %d (%s), born %ld:",
- conn_array_index, type, (unsigned)this_circid, (unsigned)other_circid,
- circ->state, circuit_state_to_string(circ->state),
- (long)circ->timestamp_began.tv_sec);
- if (CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */
- circuit_log_path(severity, LD_CIRC, TO_ORIGIN_CIRCUIT(circ));
- }
- }
- /** Log, at severity <b>severity</b>, information about each circuit
- * that is connected to <b>conn</b>.
- */
- void
- circuit_dump_by_conn(connection_t *conn, int severity)
- {
- edge_connection_t *tmpconn;
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
- circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0;
- if (circ->marked_for_close) {
- continue;
- }
- if (!CIRCUIT_IS_ORIGIN(circ)) {
- p_circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
- }
- if (CIRCUIT_IS_ORIGIN(circ)) {
- for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
- tmpconn=tmpconn->next_stream) {
- if (TO_CONN(tmpconn) == conn) {
- circuit_dump_conn_details(severity, circ, conn->conn_array_index,
- "App-ward", p_circ_id, n_circ_id);
- }
- }
- }
- if (! CIRCUIT_IS_ORIGIN(circ)) {
- for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
- tmpconn=tmpconn->next_stream) {
- if (TO_CONN(tmpconn) == conn) {
- circuit_dump_conn_details(severity, circ, conn->conn_array_index,
- "Exit-ward", n_circ_id, p_circ_id);
- }
- }
- }
- }
- SMARTLIST_FOREACH_END(circ);
- }
- /** Return the circuit whose global ID is <b>id</b>, or NULL if no
- * such circuit exists. */
- origin_circuit_t *
- circuit_get_by_global_id(uint32_t id)
- {
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
- if (CIRCUIT_IS_ORIGIN(circ) &&
- TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) {
- if (circ->marked_for_close)
- return NULL;
- else
- return TO_ORIGIN_CIRCUIT(circ);
- }
- }
- SMARTLIST_FOREACH_END(circ);
- return NULL;
- }
- /** Return a circ such that:
- * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
- * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
- * Return NULL if no such circuit exists.
- *
- * If <b>found_entry_out</b> is provided, set it to true if we have a
- * placeholder entry for circid/chan, and leave it unset otherwise.
- */
- static inline circuit_t *
- circuit_get_by_circid_channel_impl(circid_t circ_id, channel_t *chan,
- int *found_entry_out)
- {
- chan_circid_circuit_map_t search;
- chan_circid_circuit_map_t *found;
- if (_last_circid_chan_ent &&
- circ_id == _last_circid_chan_ent->circ_id &&
- chan == _last_circid_chan_ent->chan) {
- found = _last_circid_chan_ent;
- } else {
- search.circ_id = circ_id;
- search.chan = chan;
- found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
- _last_circid_chan_ent = found;
- }
- if (found && found->circuit) {
- log_debug(LD_CIRC,
- "circuit_get_by_circid_channel_impl() returning circuit %p for"
- " circ_id %u, channel ID " U64_FORMAT " (%p)",
- found->circuit, (unsigned)circ_id,
- U64_PRINTF_ARG(chan->global_identifier), chan);
- if (found_entry_out)
- *found_entry_out = 1;
- return found->circuit;
- }
- log_debug(LD_CIRC,
- "circuit_get_by_circid_channel_impl() found %s for"
- " circ_id %u, channel ID " U64_FORMAT " (%p)",
- found ? "placeholder" : "nothing",
- (unsigned)circ_id,
- U64_PRINTF_ARG(chan->global_identifier), chan);
- if (found_entry_out)
- *found_entry_out = found ? 1 : 0;
- return NULL;
- /* The rest of this checks for bugs. Disabled by default. */
- /* We comment it out because coverity complains otherwise.
- {
- circuit_t *circ;
- TOR_LIST_FOREACH(circ, &global_circuitlist, head) {
- if (! CIRCUIT_IS_ORIGIN(circ)) {
- or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
- if (or_circ->p_chan == chan && or_circ->p_circ_id == circ_id) {
- log_warn(LD_BUG,
- "circuit matches p_chan, but not in hash table (Bug!)");
- return circ;
- }
- }
- if (circ->n_chan == chan && circ->n_circ_id == circ_id) {
- log_warn(LD_BUG,
- "circuit matches n_chan, but not in hash table (Bug!)");
- return circ;
- }
- }
- return NULL;
- } */
- }
- /** Return a circ such that:
- * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
- * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
- * - circ is not marked for close.
- * Return NULL if no such circuit exists.
- */
- circuit_t *
- circuit_get_by_circid_channel(circid_t circ_id, channel_t *chan)
- {
- circuit_t *circ = circuit_get_by_circid_channel_impl(circ_id, chan, NULL);
- if (!circ || circ->marked_for_close)
- return NULL;
- else
- return circ;
- }
- /** Return a circ such that:
- * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
- * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
- * Return NULL if no such circuit exists.
- */
- circuit_t *
- circuit_get_by_circid_channel_even_if_marked(circid_t circ_id,
- channel_t *chan)
- {
- return circuit_get_by_circid_channel_impl(circ_id, chan, NULL);
- }
- /** Return true iff the circuit ID <b>circ_id</b> is currently used by a
- * circuit, marked or not, on <b>chan</b>, or if the circ ID is reserved until
- * a queued destroy cell can be sent.
- *
- * (Return 1 if the circuit is present, marked or not; Return 2
- * if the circuit ID is pending a destroy.)
- **/
- int
- circuit_id_in_use_on_channel(circid_t circ_id, channel_t *chan)
- {
- int found = 0;
- if (circuit_get_by_circid_channel_impl(circ_id, chan, &found) != NULL)
- return 1;
- if (found)
- return 2;
- return 0;
- }
- /** Helper for debugging 12184. Returns the time since which 'circ_id' has
- * been marked unusable on 'chan'. */
- time_t
- circuit_id_when_marked_unusable_on_channel(circid_t circ_id, channel_t *chan)
- {
- chan_circid_circuit_map_t search;
- chan_circid_circuit_map_t *found;
- memset(&search, 0, sizeof(search));
- search.circ_id = circ_id;
- search.chan = chan;
- found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
- if (! found || found->circuit)
- return 0;
- return found->made_placeholder_at;
- }
- /** Return the circuit that a given edge connection is using. */
- circuit_t *
- circuit_get_by_edge_conn(edge_connection_t *conn)
- {
- circuit_t *circ;
- circ = conn->on_circuit;
- tor_assert(!circ ||
- (CIRCUIT_IS_ORIGIN(circ) ? circ->magic == ORIGIN_CIRCUIT_MAGIC
- : circ->magic == OR_CIRCUIT_MAGIC));
- return circ;
- }
- /** For each circuit that has <b>chan</b> as n_chan or p_chan, unlink the
- * circuit from the chan,circid map, and mark it for close if it hasn't
- * been marked already.
- */
- void
- circuit_unlink_all_from_channel(channel_t *chan, int reason)
- {
- smartlist_t *detached = smartlist_new();
- /* #define DEBUG_CIRCUIT_UNLINK_ALL */
- channel_unlink_all_circuits(chan, detached);
- #ifdef DEBUG_CIRCUIT_UNLINK_ALL
- {
- smartlist_t *detached_2 = smartlist_new();
- int mismatch = 0, badlen = 0;
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
- if (circ->n_chan == chan ||
- (!CIRCUIT_IS_ORIGIN(circ) &&
- TO_OR_CIRCUIT(circ)->p_chan == chan)) {
- smartlist_add(detached_2, circ);
- }
- }
- SMARTLIST_FOREACH_END(circ);
- if (smartlist_len(detached) != smartlist_len(detached_2)) {
- log_warn(LD_BUG, "List of detached circuits had the wrong length! "
- "(got %d, should have gotten %d)",
- (int)smartlist_len(detached),
- (int)smartlist_len(detached_2));
- badlen = 1;
- }
- smartlist_sort_pointers(detached);
- smartlist_sort_pointers(detached_2);
- SMARTLIST_FOREACH(detached, circuit_t *, c,
- if (c != smartlist_get(detached_2, c_sl_idx))
- mismatch = 1;
- );
- if (mismatch)
- log_warn(LD_BUG, "Mismatch in list of detached circuits.");
- if (badlen || mismatch) {
- smartlist_free(detached);
- detached = detached_2;
- } else {
- log_notice(LD_CIRC, "List of %d circuits was as expected.",
- (int)smartlist_len(detached));
- smartlist_free(detached_2);
- }
- }
- #endif /* defined(DEBUG_CIRCUIT_UNLINK_ALL) */
- SMARTLIST_FOREACH_BEGIN(detached, circuit_t *, circ) {
- int mark = 0;
- if (circ->n_chan == chan) {
- circuit_set_n_circid_chan(circ, 0, NULL);
- mark = 1;
- /* If we didn't request this closure, pass the remote
- * bit to mark_for_close. */
- if (chan->reason_for_closing != CHANNEL_CLOSE_REQUESTED)
- reason |= END_CIRC_REASON_FLAG_REMOTE;
- }
- if (! CIRCUIT_IS_ORIGIN(circ)) {
- or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
- if (or_circ->p_chan == chan) {
- circuit_set_p_circid_chan(or_circ, 0, NULL);
- mark = 1;
- }
- }
- if (!mark) {
- log_warn(LD_BUG, "Circuit on detached list which I had no reason "
- "to mark");
- continue;
- }
- if (!circ->marked_for_close)
- circuit_mark_for_close(circ, reason);
- } SMARTLIST_FOREACH_END(circ);
- smartlist_free(detached);
- }
- /** Return a circ such that
- * - circ-\>rend_data-\>onion_address is equal to
- * <b>rend_data</b>-\>onion_address,
- * - circ-\>rend_data-\>rend_cookie is equal to
- * <b>rend_data</b>-\>rend_cookie, and
- * - circ-\>purpose is equal to CIRCUIT_PURPOSE_C_REND_READY.
- *
- * Return NULL if no such circuit exists.
- */
- origin_circuit_t *
- circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data)
- {
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
- if (!circ->marked_for_close &&
- circ->purpose == CIRCUIT_PURPOSE_C_REND_READY) {
- origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
- if (ocirc->rend_data == NULL) {
- continue;
- }
- if (!rend_cmp_service_ids(rend_data_get_address(rend_data),
- rend_data_get_address(ocirc->rend_data)) &&
- tor_memeq(ocirc->rend_data->rend_cookie,
- rend_data->rend_cookie,
- REND_COOKIE_LEN))
- return ocirc;
- }
- }
- SMARTLIST_FOREACH_END(circ);
- return NULL;
- }
- /** Return the first service introduction circuit originating from the global
- * circuit list after <b>start</b> or at the start of the list if <b>start</b>
- * is NULL. Return NULL if no circuit is found.
- *
- * A service introduction point circuit has a purpose of either
- * CIRCUIT_PURPOSE_S_ESTABLISH_INTRO or CIRCUIT_PURPOSE_S_INTRO. This does not
- * return a circuit marked for close and its state must be open. */
- origin_circuit_t *
- circuit_get_next_service_intro_circ(origin_circuit_t *start)
- {
- int idx = 0;
- smartlist_t *lst = circuit_get_global_list();
- if (start) {
- idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
- }
- for ( ; idx < smartlist_len(lst); ++idx) {
- circuit_t *circ = smartlist_get(lst, idx);
- /* Ignore a marked for close circuit or purpose not matching a service
- * intro point or if the state is not open. */
- if (circ->marked_for_close || circ->state != CIRCUIT_STATE_OPEN ||
- (circ->purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO &&
- circ->purpose != CIRCUIT_PURPOSE_S_INTRO)) {
- continue;
- }
- /* The purposes we are looking for are only for origin circuits so the
- * following is valid. */
- return TO_ORIGIN_CIRCUIT(circ);
- }
- /* Not found. */
- return NULL;
- }
- /** Return the first service rendezvous circuit originating from the global
- * circuit list after <b>start</b> or at the start of the list if <b>start</b>
- * is NULL. Return NULL if no circuit is found.
- *
- * A service rendezvous point circuit has a purpose of either
- * CIRCUIT_PURPOSE_S_CONNECT_REND or CIRCUIT_PURPOSE_S_REND_JOINED. This does
- * not return a circuit marked for close and its state must be open. */
- origin_circuit_t *
- circuit_get_next_service_rp_circ(origin_circuit_t *start)
- {
- int idx = 0;
- smartlist_t *lst = circuit_get_global_list();
- if (start) {
- idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
- }
- for ( ; idx < smartlist_len(lst); ++idx) {
- circuit_t *circ = smartlist_get(lst, idx);
- /* Ignore a marked for close circuit or purpose not matching a service
- * intro point or if the state is not open. */
- if (circ->marked_for_close || circ->state != CIRCUIT_STATE_OPEN ||
- (circ->purpose != CIRCUIT_PURPOSE_S_CONNECT_REND &&
- circ->purpose != CIRCUIT_PURPOSE_S_REND_JOINED)) {
- continue;
- }
- /* The purposes we are looking for are only for origin circuits so the
- * following is valid. */
- return TO_ORIGIN_CIRCUIT(circ);
- }
- /* Not found. */
- return NULL;
- }
- /** Return the first circuit originating here in global_circuitlist after
- * <b>start</b> whose purpose is <b>purpose</b>, and where <b>digest</b> (if
- * set) matches the private key digest of the rend data associated with the
- * circuit. Return NULL if no circuit is found. If <b>start</b> is NULL,
- * begin at the start of the list.
- */
- origin_circuit_t *
- circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
- const uint8_t *digest, uint8_t purpose)
- {
- int idx;
- smartlist_t *lst = circuit_get_global_list();
- tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose));
- if (start == NULL)
- idx = 0;
- else
- idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
- for ( ; idx < smartlist_len(lst); ++idx) {
- circuit_t *circ = smartlist_get(lst, idx);
- origin_circuit_t *ocirc;
- if (circ->marked_for_close)
- continue;
- if (circ->purpose != purpose)
- continue;
- /* At this point we should be able to get a valid origin circuit because
- * the origin purpose we are looking for matches this circuit. */
- if (BUG(!CIRCUIT_PURPOSE_IS_ORIGIN(circ->purpose))) {
- break;
- }
- ocirc = TO_ORIGIN_CIRCUIT(circ);
- if (!digest)
- return ocirc;
- if (rend_circuit_pk_digest_eq(ocirc, digest)) {
- return ocirc;
- }
- }
- return NULL;
- }
- /** We might cannibalize this circuit: Return true if its last hop can be used
- * as a v3 rendezvous point. */
- static int
- circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t *circ)
- {
- if (!circ->build_state) {
- return 0;
- }
- extend_info_t *chosen_exit = circ->build_state->chosen_exit;
- if (BUG(!chosen_exit)) {
- return 0;
- }
- const node_t *rp_node = node_get_by_id(chosen_exit->identity_digest);
- if (rp_node) {
- if (node_supports_v3_rendezvous_point(rp_node)) {
- return 1;
- }
- }
- return 0;
- }
- /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
- * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
- * flags in <b>flags</b>, and if info is defined, does not already use info
- * as any of its hops; or NULL if no circuit fits this description.
- *
- * The <b>purpose</b> argument (currently ignored) refers to the purpose of
- * the circuit we want to create, not the purpose of the circuit we want to
- * cannibalize.
- *
- * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
- *
- * To "cannibalize" a circuit means to extend it an extra hop, and use it
- * for some other purpose than we had originally intended. We do this when
- * we want to perform some low-bandwidth task at a specific relay, and we
- * would like the circuit to complete as soon as possible. (If we were going
- * to use a lot of bandwidth, we wouldn't want a circuit with an extra hop.
- * If we didn't care about circuit completion latency, we would just build
- * a new circuit.)
- */
- origin_circuit_t *
- circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
- int flags)
- {
- origin_circuit_t *best=NULL;
- int need_uptime = (flags & CIRCLAUNCH_NEED_UPTIME) != 0;
- int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0;
- int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0;
- const or_options_t *options = get_options();
- /* Make sure we're not trying to create a onehop circ by
- * cannibalization. */
- tor_assert(!(flags & CIRCLAUNCH_ONEHOP_TUNNEL));
- log_debug(LD_CIRC,
- "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
- "capacity %d, internal %d",
- purpose, need_uptime, need_capacity, internal);
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ_) {
- if (CIRCUIT_IS_ORIGIN(circ_) &&
- circ_->state == CIRCUIT_STATE_OPEN &&
- !circ_->marked_for_close &&
- circ_->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
- !circ_->timestamp_dirty) {
- origin_circuit_t *circ = TO_ORIGIN_CIRCUIT(circ_);
- if ((!need_uptime || circ->build_state->need_uptime) &&
- (!need_capacity || circ->build_state->need_capacity) &&
- (internal == circ->build_state->is_internal) &&
- !circ->unusable_for_new_conns &&
- circ->remaining_relay_early_cells &&
- circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN &&
- !circ->build_state->onehop_tunnel &&
- !circ->isolation_values_set) {
- if (info) {
- /* need to make sure we don't duplicate hops */
- crypt_path_t *hop = circ->cpath;
- const node_t *ri1 = node_get_by_id(info->identity_digest);
- do {
- const node_t *ri2;
- if (tor_memeq(hop->extend_info->identity_digest,
- info->identity_digest, DIGEST_LEN))
- goto next;
- if (ri1 &&
- (ri2 = node_get_by_id(hop->extend_info->identity_digest))
- && nodes_in_same_family(ri1, ri2))
- goto next;
- hop=hop->next;
- } while (hop!=circ->cpath);
- }
- if (options->ExcludeNodes) {
- /* Make sure no existing nodes in the circuit are excluded for
- * general use. (This may be possible if StrictNodes is 0, and we
- * thought we needed to use an otherwise excluded node for, say, a
- * directory operation.) */
- crypt_path_t *hop = circ->cpath;
- do {
- if (routerset_contains_extendinfo(options->ExcludeNodes,
- hop->extend_info))
- goto next;
- hop = hop->next;
- } while (hop != circ->cpath);
- }
- if ((flags & CIRCLAUNCH_IS_V3_RP) &&
- !circuit_can_be_cannibalized_for_v3_rp(circ)) {
- log_debug(LD_GENERAL, "Skipping uncannibalizable circuit for v3 "
- "rendezvous point.");
- goto next;
- }
- if (!best || (best->build_state->need_uptime && !need_uptime))
- best = circ;
- next: ;
- }
- }
- }
- SMARTLIST_FOREACH_END(circ_);
- return best;
- }
- /**
- * Check whether any of the origin circuits that are waiting to see if
- * their guard is good enough to use can be upgraded to "ready". If so,
- * return a new smartlist containing them. Otherwise return NULL.
- */
- smartlist_t *
- circuit_find_circuits_to_upgrade_from_guard_wait(void)
- {
- /* Only if some circuit is actually waiting on an upgrade should we
- * run the algorithm. */
- if (! circuits_pending_other_guards ||
- smartlist_len(circuits_pending_other_guards)==0)
- return NULL;
- /* Only if we have some origin circuits should we run the algorithm. */
- if (!global_origin_circuit_list)
- return NULL;
- /* Okay; we can pass our circuit list to entrynodes.c.*/
- smartlist_t *result = smartlist_new();
- int circuits_upgraded = entry_guards_upgrade_waiting_circuits(
- get_guard_selection_info(),
- global_origin_circuit_list,
- result);
- if (circuits_upgraded && smartlist_len(result)) {
- return result;
- } else {
- smartlist_free(result);
- return NULL;
- }
- }
- /** Return the number of hops in circuit's path. If circ has no entries,
- * or is NULL, returns 0. */
- int
- circuit_get_cpath_len(origin_circuit_t *circ)
- {
- int n = 0;
- if (circ && circ->cpath) {
- crypt_path_t *cpath, *cpath_next = NULL;
- for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
- cpath_next = cpath->next;
- ++n;
- }
- }
- return n;
- }
- /** Return the number of opened hops in circuit's path.
- * If circ has no entries, or is NULL, returns 0. */
- int
- circuit_get_cpath_opened_len(const origin_circuit_t *circ)
- {
- int n = 0;
- if (circ && circ->cpath) {
- crypt_path_t *cpath, *cpath_next = NULL;
- for (cpath = circ->cpath;
- cpath->state == CPATH_STATE_OPEN
- && cpath_next != circ->cpath;
- cpath = cpath_next) {
- cpath_next = cpath->next;
- ++n;
- }
- }
- return n;
- }
- /** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there
- * aren't that many hops in the list. <b>hopnum</b> starts at 1.
- * Returns NULL if <b>hopnum</b> is 0 or negative. */
- crypt_path_t *
- circuit_get_cpath_hop(origin_circuit_t *circ, int hopnum)
- {
- if (circ && circ->cpath && hopnum > 0) {
- crypt_path_t *cpath, *cpath_next = NULL;
- for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
- cpath_next = cpath->next;
- if (--hopnum <= 0)
- return cpath;
- }
- }
- return NULL;
- }
- /** Go through the circuitlist; mark-for-close each circuit that starts
- * at us but has not yet been used. */
- void
- circuit_mark_all_unused_circs(void)
- {
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
- if (CIRCUIT_IS_ORIGIN(circ) &&
- !circ->marked_for_close &&
- !circ->timestamp_dirty)
- circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
- }
- SMARTLIST_FOREACH_END(circ);
- }
- /** Go through the circuitlist; for each circuit that starts at us
- * and is dirty, frob its timestamp_dirty so we won't use it for any
- * new streams.
- *
- * This is useful for letting the user change pseudonyms, so new
- * streams will not be linkable to old streams.
- */
- void
- circuit_mark_all_dirty_circs_as_unusable(void)
- {
- SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
- if (CIRCUIT_IS_ORIGIN(circ) &&
- !circ->marked_for_close &&
- circ->timestamp_dirty) {
- mark_circuit_unusable_for_new_conns(TO_ORIGIN_CIRCUIT(circ));
- }
- }
- SMARTLIST_FOREACH_END(circ);
- }
- /** Mark <b>circ</b> to be closed next time we call
- * circuit_close_all_marked(). Do any cleanup needed:
- * - If state is onionskin_pending, remove circ from the onion_pending
- * list.
- * - If circ isn't open yet: call circuit_build_failed() if we're
- * the origin, and in either case call circuit_rep_hist_note_result()
- * to note stats.
- * - If purpose is C_INTRODUCE_ACK_WAIT, report the intro point
- * failure we just had to the hidden service client module.
- * - If purpose is C_INTRODUCING and <b>reason</b> isn't TIMEOUT,
- * report to the hidden service client module that the intro point
- * we just tried may be unreachable.
- * - Send appropriate destroys and edge_destroys for conns and
- * streams attached to circ.
- * - If circ->rend_splice is set (we are the midpoint of a joined
- * rendezvous stream), then mark the other circuit to close as well.
- */
- MOCK_IMPL(void,
- circuit_mark_for_close_, (circuit_t *circ, int reason, int line,
- const char *file))
- {
- int orig_reason = reason; /* Passed to the controller */
- assert_circuit_ok(circ);
- tor_assert(line);
- tor_assert(file);
- if (circ->marked_for_close) {
- log_warn(LD_BUG,
- "Duplicate call to circuit_mark_for_close at %s:%d"
- " (first at %s:%d)", file, line,
- circ->marked_for_close_file, circ->marked_for_close);
- return;
- }
- if (reason == END_CIRC_AT_ORIGIN) {
- if (!CIRCUIT_IS_ORIGIN(circ)) {
- log_warn(LD_BUG, "Specified 'at-origin' non-reason for ending circuit, "
- "but circuit was not at origin. (called %s:%d, purpose=%d)",
- file, line, circ->purpose);
- }
- reason = END_CIRC_REASON_NONE;
- }
- if (CIRCUIT_IS_ORIGIN(circ)) {
- if (pathbias_check_close(TO_ORIGIN_CIRCUIT(circ), reason) == -1) {
- /* Don't close it yet, we need to test it first */
- return;
- }
- /* We don't send reasons when closing circuits at the origin. */
- reason = END_CIRC_REASON_NONE;
- }
- if (reason & END_CIRC_REASON_FLAG_REMOTE)
- reason &= ~END_CIRC_REASON_FLAG_REMOTE;
- if (reason < END_CIRC_REASON_MIN_ || reason > END_CIRC_REASON_MAX_) {
- if (!(orig_reason & END_CIRC_REASON_FLAG_REMOTE))
- log_warn(LD_BUG, "Reason %d out of range at %s:%d", reason, file, line);
- reason = END_CIRC_REASON_NONE;
- }
- circ->marked_for_close = line;
- circ->marked_for_close_file = file;
- circ->marked_for_close_reason = reason;
- circ->marked_for_close_orig_reason = orig_reason;
- if (!CIRCUIT_IS_ORIGIN(circ)) {
- or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
- if (or_circ->rend_splice) {
- if (!or_circ->rend_splice->base_.marked_for_close) {
- /* do this after marking this circuit, to avoid infinite recursion. */
- circuit_mark_for_close(TO_CIRCUIT(or_circ->rend_splice), reason);
- }
- or_circ->rend_splice = NULL;
- }
- }
- /* Notify the HS subsystem that this circuit is closing. */
- hs_circ_cleanup(circ);
- if (circuits_pending_close == NULL)
- circuits_pending_close = smartlist_new();
- smartlist_add(circuits_pending_close, circ);
- log_info(LD_GENERAL, "Circuit %u (id: %" PRIu32 ") marked for close at "
- "%s:%d (orig reason: %d, new reason: %d)",
- circ->n_circ_id,
- CIRCUIT_IS_ORIGIN(circ) ?
- TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0,
- file, line, orig_reason, reason);
- }
- /** Called immediately before freeing a marked circuit <b>circ</b> from
- * circuit_free_all() while shutting down Tor; this is a safe-at-shutdown
- * version of circuit_about_to_free(). It's important that it at least
- * do circuitmux_detach_circuit() when appropriate.
- */
- static void
- circuit_about_to_free_atexit(circuit_t *circ)
- {
- if (circ->n_chan) {
- circuit_clear_cell_queue(circ, circ->n_chan);
- circuitmux_detach_circuit(circ->n_chan->cmux, circ);
- circuit_set_n_circid_chan(circ, 0, NULL);
- }
- if (! CIRCUIT_IS_ORIGIN(circ)) {
- or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
- if (or_circ->p_chan) {
- circuit_clear_cell_queue(circ, or_circ->p_chan);
- circuitmux_detach_circuit(or_circ->p_chan->cmux, circ);
- circuit_set_p_circid_chan(or_circ, 0, NULL);
- }
- }
- }
- /** Called immediately before freeing a marked circuit <b>circ</b>.
- * Disconnects the circuit from other data structures, launches events
- * as appropriate, and performs other housekeeping.
- */
- static void
- circuit_about_to_free(circuit_t *circ)
- {
- int reason = circ->marked_for_close_reason;
- int orig_reason = circ->marked_for_close_orig_reason;
- if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
- onion_pending_remove(TO_OR_CIRCUIT(circ));
- }
- /* If the circuit ever became OPEN, we sent it to the reputation history
- * module then. If it isn't OPEN, we send it there now to remember which
- * links worked and which didn't.
- */
- if (circ->state != CIRCUIT_STATE_OPEN &&
- circ->state != CIRCUIT_STATE_GUARD_WAIT) {
- if (CIRCUIT_IS_ORIGIN(circ)) {
- origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
- circuit_build_failed(ocirc); /* take actions if necessary */
- circuit_rep_hist_note_result(ocirc);
- }
- }
- if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
- if (circuits_pending_chans)
- smartlist_remove(circuits_pending_chans, circ);
- }
- if (circuits_pending_other_guards) {
- smartlist_remove(circuits_pending_other_guards, circ);
- }
- if (CIRCUIT_IS_ORIGIN(circ)) {
- control_event_circuit_status(TO_ORIGIN_CIRCUIT(circ),
- (circ->state == CIRCUIT_STATE_OPEN ||
- circ->state == CIRCUIT_STATE_GUARD_WAIT) ?
- CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED,
- orig_reason);
- }
- if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
- origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
- int timed_out = (reason == END_CIRC_REASON_TIMEOUT);
- tor_assert(circ->state == CIRCUIT_STATE_OPEN);
- tor_assert(ocirc->build_state->chosen_exit);
- if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT &&
- ocirc->rend_data) {
- /* treat this like getting a nack from it */
- log_info(LD_REND, "Failed intro circ %s to %s (awaiting ack). %s",
- safe_str_client(rend_data_get_address(ocirc->rend_data)),
- safe_str_client(build_state_get_exit_nickname(ocirc->build_state)),
- timed_out ? "Recording timeout." : "Removing from descriptor.");
- rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit,
- ocirc->rend_data,
- timed_out ?
- INTRO_POINT_FAILURE_TIMEOUT :
- INTRO_POINT_FAILURE_GENERIC);
- }
- } else if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCING &&
- reason != END_CIRC_REASON_TIMEOUT) {
- origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
- if (ocirc->build_state->chosen_exit && ocirc->rend_data) {
- if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT &&
- ocirc->rend_data) {
- log_info(LD_REND, "Failed intro circ %s to %s "
- "(building circuit to intro point). "
- "Marking intro point as possibly unreachable.",
- safe_str_client(rend_data_get_address(ocirc->rend_data)),
- safe_str_client(build_state_get_exit_nickname(
- ocirc->build_state)));
- rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit,
- ocirc->rend_data,
- INTRO_POINT_FAILURE_UNREACHABLE);
- }
- }
- }
- if (circ->n_chan) {
- circuit_clear_cell_queue(circ, circ->n_chan);
- /* Only send destroy if the channel isn't closing anyway */
- if (!CHANNEL_CONDEMNED(circ->n_chan)) {
- channel_send_destroy(circ->n_circ_id, circ->n_chan, reason);
- }
- circuitmux_detach_circuit(circ->n_chan->cmux, circ);
- circuit_set_n_circid_chan(circ, 0, NULL);
- }
- if (! CIRCUIT_IS_ORIGIN(circ)) {
- or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
- edge_connection_t *conn;
- for (conn=or_circ->n_streams; conn; conn=conn->next_stream)
- connection_edge_destroy(or_circ->p_circ_id, conn);
- or_circ->n_streams = NULL;
- while (or_circ->resolving_streams) {
- conn = or_circ->resolving_streams;
- or_circ->resolving_streams = conn->next_stream;
- if (!conn->base_.marked_for_close) {
- /* The client will see a DESTROY, and infer that the connections
- * are closing because the circuit is getting torn down. No need
- * to send an end cell. */
- conn->edge_has_sent_end = 1;
- conn->end_reason = END_STREAM_REASON_DESTROY;
- conn->end_reason |= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED;
- connection_mark_for_close(TO_CONN(conn));
- }
- conn->on_circuit = NULL;
- }
- if (or_circ->p_chan) {
- circuit_clear_cell_queue(circ, or_circ->p_chan);
- /* Only send destroy if the channel isn't closing anyway */
- if (!CHANNEL_CONDEMNED(or_circ->p_chan)) {
- channel_send_destroy(or_circ->p_circ_id, or_circ->p_chan, reason);
- }
- circuitmux_detach_circuit(or_circ->p_chan->cmux, circ);
- circuit_set_p_circid_chan(or_circ, 0, NULL);
- }
- } else {
- origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
- edge_connection_t *conn;
- for (conn=ocirc->p_streams; conn; conn=conn->next_stream)
- connection_edge_destroy(circ->n_circ_id, conn);
- ocirc->p_streams = NULL;
- }
- }
- /** Given a marked circuit <b>circ</b>, aggressively free its cell queues to
- * recover memory. */
- static void
- marked_circuit_free_cells(circuit_t *circ)
- {
- if (!circ->marked_for_close) {
- log_warn(LD_BUG, "Called on non-marked circuit");
- return;
- }
- cell_queue_clear(&circ->n_chan_cells);
- if (circ->n_mux)
- circuitmux_clear_num_cells(circ->n_mux, circ);
- if (! CIRCUIT_IS_ORIGIN(circ)) {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- cell_queue_clear(&orcirc->p_chan_cells);
- if (orcirc->p_mux)
- circuitmux_clear_num_cells(orcirc->p_mux, circ);
- }
- }
- static size_t
- single_conn_free_bytes(connection_t *conn)
- {
- size_t result = 0;
- if (conn->inbuf) {
- result += buf_allocation(conn->inbuf);
- buf_clear(conn->inbuf);
- }
- if (conn->outbuf) {
- result += buf_allocation(conn->outbuf);
- buf_clear(conn->outbuf);
- conn->outbuf_flushlen = 0;
- }
- if (conn->type == CONN_TYPE_DIR) {
- dir_connection_t *dir_conn = TO_DIR_CONN(conn);
- if (dir_conn->compress_state) {
- result += tor_compress_state_size(dir_conn->compress_state);
- tor_compress_free(dir_conn->compress_state);
- dir_conn->compress_state = NULL;
- }
- }
- return result;
- }
- /** Aggressively free buffer contents on all the buffers of all streams in the
- * list starting at <b>stream</b>. Return the number of bytes recovered. */
- static size_t
- marked_circuit_streams_free_bytes(edge_connection_t *stream)
- {
- size_t result = 0;
- for ( ; stream; stream = stream->next_stream) {
- connection_t *conn = TO_CONN(stream);
- result += single_conn_free_bytes(conn);
- if (conn->linked_conn) {
- result += single_conn_free_bytes(conn->linked_conn);
- }
- }
- return result;
- }
- /** Aggressively free buffer contents on all the buffers of all streams on
- * circuit <b>c</b>. Return the number of bytes recovered. */
- static size_t
- marked_circuit_free_stream_bytes(circuit_t *c)
- {
- if (CIRCUIT_IS_ORIGIN(c)) {
- return marked_circuit_streams_free_bytes(TO_ORIGIN_CIRCUIT(c)->p_streams);
- } else {
- return marked_circuit_streams_free_bytes(TO_OR_CIRCUIT(c)->n_streams);
- }
- }
- /** Return the number of cells used by the circuit <b>c</b>'s cell queues. */
- STATIC size_t
- n_cells_in_circ_queues(const circuit_t *c)
- {
- size_t n = c->n_chan_cells.n;
- if (! CIRCUIT_IS_ORIGIN(c)) {
- circuit_t *cc = (circuit_t *) c;
- n += TO_OR_CIRCUIT(cc)->p_chan_cells.n;
- }
- return n;
- }
- /**
- * Return the age of the oldest cell queued on <b>c</b>, in timestamp units.
- * Return 0 if there are no cells queued on c. Requires that <b>now</b> be
- * the current coarse timestamp.
- *
- * This function will return incorrect results if the oldest cell queued on
- * the circuit is older than about 2**32 msec (about 49 days) old.
- */
- STATIC uint32_t
- circuit_max_queued_cell_age(const circuit_t *c, uint32_t now)
- {
- uint32_t age = 0;
- packed_cell_t *cell;
- if (NULL != (cell = TOR_SIMPLEQ_FIRST(&c->n_chan_cells.head)))
- age = now - cell->inserted_timestamp;
- if (! CIRCUIT_IS_ORIGIN(c)) {
- const or_circuit_t *orcirc = CONST_TO_OR_CIRCUIT(c);
- if (NULL != (cell = TOR_SIMPLEQ_FIRST(&orcirc->p_chan_cells.head))) {
- uint32_t age2 = now - cell->inserted_timestamp;
- if (age2 > age)
- return age2;
- }
- }
- return age;
- }
- /** Return the age of the oldest buffer chunk on <b>conn</b>, where age is
- * taken in timestamp units before the time <b>now</b>. If the connection has
- * no data, treat it as having age zero.
- **/
- static uint32_t
- conn_get_buffer_age(const connection_t *conn, uint32_t now_ts)
- {
- uint32_t age = 0, age2;
- if (conn->outbuf) {
- age2 = buf_get_oldest_chunk_timestamp(conn->outbuf, now_ts);
- if (age2 > age)
- age = age2;
- }
- if (conn->inbuf) {
- age2 = buf_get_oldest_chunk_timestamp(conn->inbuf, now_ts);
- if (age2 > age)
- age = age2;
- }
- return age;
- }
- /** Return the age in timestamp units of the oldest buffer chunk on any stream
- * in the linked list <b>stream</b>, where age is taken in timestamp units
- * before the timestamp <b>now</b>. */
- static uint32_t
- circuit_get_streams_max_data_age(const edge_connection_t *stream, uint32_t now)
- {
- uint32_t age = 0, age2;
- for (; stream; stream = stream->next_stream) {
- const connection_t *conn = TO_CONN(stream);
- age2 = conn_get_buffer_age(conn, now);
- if (age2 > age)
- age = age2;
- if (conn->linked_conn) {
- age2 = conn_get_buffer_age(conn->linked_conn, now);
- if (age2 > age)
- age = age2;
- }
- }
- return age;
- }
- /** Return the age in timestamp units of the oldest buffer chunk on any stream
- * attached to the circuit <b>c</b>, where age is taken before the timestamp
- * <b>now</b>. */
- STATIC uint32_t
- circuit_max_queued_data_age(const circuit_t *c, uint32_t now)
- {
- if (CIRCUIT_IS_ORIGIN(c)) {
- return circuit_get_streams_max_data_age(
- CONST_TO_ORIGIN_CIRCUIT(c)->p_streams, now);
- } else {
- return circuit_get_streams_max_data_age(
- CONST_TO_OR_CIRCUIT(c)->n_streams, now);
- }
- }
- /** Return the age of the oldest cell or stream buffer chunk on the circuit
- * <b>c</b>, where age is taken in timestamp units before the timestamp
- * <b>now</b> */
- STATIC uint32_t
- circuit_max_queued_item_age(const circuit_t *c, uint32_t now)
- {
- uint32_t cell_age = circuit_max_queued_cell_age(c, now);
- uint32_t data_age = circuit_max_queued_data_age(c, now);
- if (cell_age > data_age)
- return cell_age;
- else
- return data_age;
- }
- /** Helper to sort a list of circuit_t by age of oldest item, in descending
- * order. */
- static int
- circuits_compare_by_oldest_queued_item_(const void **a_, const void **b_)
- {
- const circuit_t *a = *a_;
- const circuit_t *b = *b_;
- uint32_t age_a = a->age_tmp;
- uint32_t age_b = b->age_tmp;
- if (age_a < age_b)
- return 1;
- else if (age_a == age_b)
- return 0;
- else
- return -1;
- }
- static uint32_t now_ts_for_buf_cmp;
- /** Helper to sort a list of circuit_t by age of oldest item, in descending
- * order. */
- static int
- conns_compare_by_buffer_age_(const void **a_, const void **b_)
- {
- const connection_t *a = *a_;
- const connection_t *b = *b_;
- time_t age_a = conn_get_buffer_age(a, now_ts_for_buf_cmp);
- time_t age_b = conn_get_buffer_age(b, now_ts_for_buf_cmp);
- if (age_a < age_b)
- return 1;
- else if (age_a == age_b)
- return 0;
- else
- return -1;
- }
- #define FRACTION_OF_DATA_TO_RETAIN_ON_OOM 0.90
- /** We're out of memory for cells, having allocated <b>current_allocation</b>
- * bytes' worth. Kill the 'worst' circuits until we're under
- * FRACTION_OF_DATA_TO_RETAIN_ON_OOM of our maximum usage. */
- void
- circuits_handle_oom(size_t current_allocation)
- {
- smartlist_t *circlist;
- smartlist_t *connection_array = get_connection_array();
- int conn_idx;
- size_t mem_to_recover;
- size_t mem_recovered=0;
- int n_circuits_killed=0;
- int n_dirconns_killed=0;
- uint32_t now_ts;
- log_notice(LD_GENERAL, "We're low on memory (cell queues total alloc:"
- " %"TOR_PRIuSZ" buffer total alloc: %" TOR_PRIuSZ ","
- " tor compress total alloc: %" TOR_PRIuSZ
- " rendezvous cache total alloc: %" TOR_PRIuSZ "). Killing"
- " circuits withover-long queues. (This behavior is controlled by"
- " MaxMemInQueues.)",
- cell_queues_get_total_allocation(),
- buf_get_total_allocation(),
- tor_compress_get_total_allocation(),
- rend_cache_get_total_allocation());
- {
- size_t mem_target = (size_t)(get_options()->MaxMemInQueues *
- FRACTION_OF_DATA_TO_RETAIN_ON_OOM);
- if (current_allocation <= mem_target)
- return;
- mem_to_recover = current_allocation - mem_target;
- }
- now_ts = monotime_coarse_get_stamp();
- circlist = circuit_get_global_list();
- SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
- circ->age_tmp = circuit_max_queued_item_age(circ, now_ts);
- } SMARTLIST_FOREACH_END(circ);
- /* This is O(n log n); there are faster algorithms we could use instead.
- * Let's hope this doesn't happen enough to be in the critical path. */
- smartlist_sort(circlist, circuits_compare_by_oldest_queued_item_);
- /* Fix up the indices before we run into trouble */
- SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
- circ->global_circuitlist_idx = circ_sl_idx;
- } SMARTLIST_FOREACH_END(circ);
- /* Now sort the connection array ... */
- now_ts_for_buf_cmp = now_ts;
- smartlist_sort(connection_array, conns_compare_by_buffer_age_);
- now_ts_for_buf_cmp = 0;
- /* Fix up the connection array to its new order. */
- SMARTLIST_FOREACH_BEGIN(connection_array, connection_t *, conn) {
- conn->conn_array_index = conn_sl_idx;
- } SMARTLIST_FOREACH_END(conn);
- /* Okay, now the worst circuits and connections are at the front of their
- * respective lists. Let's mark them, and reclaim their storage
- * aggressively. */
- conn_idx = 0;
- SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
- size_t n;
- size_t freed;
- /* Free storage in any non-linked directory connections that have buffered
- * data older than this circuit. */
- while (conn_idx < smartlist_len(connection_array)) {
- connection_t *conn = smartlist_get(connection_array, conn_idx);
- uint32_t conn_age = conn_get_buffer_age(conn, now_ts);
- if (conn_age < circ->age_tmp) {
- break;
- }
- if (conn->type == CONN_TYPE_DIR && conn->linked_conn == NULL) {
- if (!conn->marked_for_close)
- connection_mark_for_close(conn);
- mem_recovered += single_conn_free_bytes(conn);
- ++n_dirconns_killed;
- if (mem_recovered >= mem_to_recover)
- goto done_recovering_mem;
- }
- ++conn_idx;
- }
- /* Now, kill the circuit. */
- n = n_cells_in_circ_queues(circ);
- if (! circ->marked_for_close) {
- circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
- }
- marked_circuit_free_cells(circ);
- freed = marked_circuit_free_stream_bytes(circ);
- ++n_circuits_killed;
- mem_recovered += n * packed_cell_mem_cost();
- mem_recovered += freed;
- if (mem_recovered >= mem_to_recover)
- goto done_recovering_mem;
- } SMARTLIST_FOREACH_END(circ);
- done_recovering_mem:
- log_notice(LD_GENERAL, "Removed "U64_FORMAT" bytes by killing %d circuits; "
- "%d circuits remain alive. Also killed %d non-linked directory "
- "connections.",
- U64_PRINTF_ARG(mem_recovered),
- n_circuits_killed,
- smartlist_len(circlist) - n_circuits_killed,
- n_dirconns_killed);
- }
- /** Verify that cpath layer <b>cp</b> has all of its invariants
- * correct. Trigger an assert if anything is invalid.
- */
- void
- assert_cpath_layer_ok(const crypt_path_t *cp)
- {
- // tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
- // tor_assert(cp->port);
- tor_assert(cp);
- tor_assert(cp->magic == CRYPT_PATH_MAGIC);
- switch (cp->state)
- {
- case CPATH_STATE_OPEN:
- tor_assert(cp->f_crypto);
- tor_assert(cp->b_crypto);
- /* fall through */
- case CPATH_STATE_CLOSED:
- /*XXXX Assert that there's no handshake_state either. */
- tor_assert(!cp->rend_dh_handshake_state);
- break;
- case CPATH_STATE_AWAITING_KEYS:
- /* tor_assert(cp->dh_handshake_state); */
- break;
- default:
- log_fn(LOG_ERR, LD_BUG, "Unexpected state %d", cp->state);
- tor_assert(0);
- }
- tor_assert(cp->package_window >= 0);
- tor_assert(cp->deliver_window >= 0);
- }
- /** Verify that cpath <b>cp</b> has all of its invariants
- * correct. Trigger an assert if anything is invalid.
- */
- static void
- assert_cpath_ok(const crypt_path_t *cp)
- {
- const crypt_path_t *start = cp;
- do {
- assert_cpath_layer_ok(cp);
- /* layers must be in sequence of: "open* awaiting? closed*" */
- if (cp != start) {
- if (cp->state == CPATH_STATE_AWAITING_KEYS) {
- tor_assert(cp->prev->state == CPATH_STATE_OPEN);
- } else if (cp->state == CPATH_STATE_OPEN) {
- tor_assert(cp->prev->state == CPATH_STATE_OPEN);
- }
- }
- cp = cp->next;
- tor_assert(cp);
- } while (cp != start);
- }
- /** Verify that circuit <b>c</b> has all of its invariants
- * correct. Trigger an assert if anything is invalid.
- */
- MOCK_IMPL(void,
- assert_circuit_ok,(const circuit_t *c))
- {
- edge_connection_t *conn;
- const or_circuit_t *or_circ = NULL;
- const origin_circuit_t *origin_circ = NULL;
- tor_assert(c);
- tor_assert(c->magic == ORIGIN_CIRCUIT_MAGIC || c->magic == OR_CIRCUIT_MAGIC);
- tor_assert(c->purpose >= CIRCUIT_PURPOSE_MIN_ &&
- c->purpose <= CIRCUIT_PURPOSE_MAX_);
- if (CIRCUIT_IS_ORIGIN(c))
- origin_circ = CONST_TO_ORIGIN_CIRCUIT(c);
- else
- or_circ = CONST_TO_OR_CIRCUIT(c);
- if (c->n_chan) {
- tor_assert(!c->n_hop);
- if (c->n_circ_id) {
- /* We use the _impl variant here to make sure we don't fail on marked
- * circuits, which would not be returned by the regular function. */
- circuit_t *c2 = circuit_get_by_circid_channel_impl(c->n_circ_id,
- c->n_chan, NULL);
- tor_assert(c == c2);
- }
- }
- if (or_circ && or_circ->p_chan) {
- if (or_circ->p_circ_id) {
- /* ibid */
- circuit_t *c2 =
- circuit_get_by_circid_channel_impl(or_circ->p_circ_id,
- or_circ->p_chan, NULL);
- tor_assert(c == c2);
- }
- }
- if (or_circ)
- for (conn = or_circ->n_streams; conn; conn = conn->next_stream)
- tor_assert(conn->base_.type == CONN_TYPE_EXIT);
- tor_assert(c->deliver_window >= 0);
- tor_assert(c->package_window >= 0);
- if (c->state == CIRCUIT_STATE_OPEN ||
- c->state == CIRCUIT_STATE_GUARD_WAIT) {
- tor_assert(!c->n_chan_create_cell);
- if (or_circ) {
- tor_assert(or_circ->n_crypto);
- tor_assert(or_circ->p_crypto);
- tor_assert(or_circ->n_digest);
- tor_assert(or_circ->p_digest);
- }
- }
- if (c->state == CIRCUIT_STATE_CHAN_WAIT && !c->marked_for_close) {
- tor_assert(circuits_pending_chans &&
- smartlist_contains(circuits_pending_chans, c));
- } else {
- tor_assert(!circuits_pending_chans ||
- !smartlist_contains(circuits_pending_chans, c));
- }
- if (origin_circ && origin_circ->cpath) {
- assert_cpath_ok(origin_circ->cpath);
- }
- if (c->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED) {
- tor_assert(or_circ);
- if (!c->marked_for_close) {
- tor_assert(or_circ->rend_splice);
- tor_assert(or_circ->rend_splice->rend_splice == or_circ);
- }
- tor_assert(or_circ->rend_splice != or_circ);
- } else {
- tor_assert(!or_circ || !or_circ->rend_splice);
- }
- }
|