Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#5828 closed defect (fixed)

Something is super-inefficient in router_get_extrainfo_hash()

Reported by: arma Owned by:
Priority: Medium Milestone: Tor: 0.2.3.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: tor-auth
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

Directory authorities take many many seconds on startup. Here's a sample "caught in action" backtrace:

#0  __strlen_sse2 () at ../sysdeps/x86_64/multiarch/../strlen.S:42
#1  0x000000000044c559 in router_get_extrainfo_hash (
    s=0x7f6b1d7f85d0 "91636480,181809152,232414208,266457088,206202880,157964288,194236416,99298304,117380096,129568768,180029440,295925760,168070144,218587136,144269312,166875136,209831936,219027456,345060352,452635648,24"..., 
    digest=0xfffffff8 <Address 0xfffffff8 out of bounds>) at routerparse.c:690
#2  0x000000000044c5e7 in extrainfo_parse_entry_from_string (
    s=0x7f6b1c191433 "extra-info Acinonyx 00753CF56F75042D24F6E89281E8DDF283F3EFAA\npublished 2012-05-05 02:42:00\nwrite-history 2012-05-05 02:36:01 (900 s) 3520512,933888,854016,495616,362496,1203200,1422336,17627136,105410"..., 
    end=0x7f6b1c191cb0 "\nextra-info otherland ECFAA6900D5EDFEAD6E31236D9656BBC94E9DF57\npublished 2012-05-05 02:44:28\nwrite-history 2012-05-05 02:35:55 (900 s) 797696,72704,24576,43008,21504,21504,41984,16384,29696,29696,2150"..., 
    cache_copy=<value optimized out>, routermap=0x3) at routerparse.c:1646
#3  0x000000000044e23d in router_parse_list_from_string (s=0x7fffcc85ce98, 
    eos=0x7f6b1e3fe7e1 "", dest=<value optimized out>, 
    saved_location=SAVED_IN_CACHE, want_extrainfo=<value optimized out>, 
    allow_annotations=<value optimized out>, prepend_annotations=0x0)
    at routerparse.c:1199
#4  0x0000000000445afd in router_load_extrainfo_from_string (
    s=0x7f6b1c191433 "extra-info Acinonyx 00753CF56F75042D24F6E89281E8DDF283F3EFAA\npublished 2012-05-05 02:42:00\nwrite-history 2012-05-05 02:36:01 (900 s) 3520512,933888,854016,495616,362496,1203200,1422336,17627136,105410"..., 
    eos=0x7f6b1e3fe7e1 "", saved_location=SAVED_IN_CACHE, 
    requested_fingerprints=<value optimized out>, 
    descriptor_digests=<value optimized out>) at routerlist.c:3948
#5  0x0000000000445fb9 in router_reload_router_list_impl (store=0x22f9110)
    at routerlist.c:847
#6  0x0000000000446229 in router_reload_router_list () at routerlist.c:903
#7  0x0000000000409f25 in do_main_loop () at main.c:1864
#8  0x000000000040a34d in tor_main (argc=<value optimized out>, 
    argv=0x7fffcc85d158) at main.c:2619
#9  0x00007f6b1f75ac8d in __libc_start_main (main=<value optimized out>, 
    argc=<value optimized out>, ubp_av=<value optimized out>, 
    init=<value optimized out>, fini=<value optimized out>, 
    rtld_fini=<value optimized out>, stack_end=0x7fffcc85d148)
    at libc-start.c:228
#10 0x0000000000408839 in _start ()

Child Tickets

Change History (9)

comment:1 Changed 8 years ago by arma

Here it is without those sissy optimizations:

#0  __strlen_sse2 () at ../sysdeps/x86_64/multiarch/../strlen.S:40
#1  0x00000000004592dc in router_get_extrainfo_hash (
    s=0x7f4314e9ad57 "extra-info winters 810962DC3C058C757070420E9A9497532BB8185A\npublished 2012-05-09 23:40:20\nwrite-history 2012-05-09 23:27:30 (900 s) 25795584,41270272,50443264,54130688,27383808,35012608,15630336,39361"..., 
    digest=0x7fff7eb36c60 "þ5Jc¯\036\064\034±}l¼\233\016\001)¾#æ´")
    at routerparse.c:690
#2  0x000000000045c9f0 in extrainfo_parse_entry_from_string (
    s=0x7f4314e9ad57 "extra-info winters 810962DC3C058C757070420E9A9497532BB8185A\npublished 2012-05-09 23:40:20\nwrite-history 2012-05-09 23:27:30 (900 s) 25795584,41270272,50443264,54130688,27383808,35012608,15630336,39361"..., 
    end=0x7f4314e9bf79 "extra-info Unnamed 43908858A50434F3CDAEC3EA1398E4C5E41223BB\npublished 2012-05-09 23:40:27\nwrite-history 2012-05-09 23:39:48 (900 s) 1333248\nread-history 2012-05-09 23:39:48 (900 s) 4159488\nrouter-sign"..., 
    cache_copy=0, routermap=0x14978c0) at routerparse.c:1646
#3  0x000000000045ad19 in router_parse_list_from_string (s=0x7fff7eb36e28, 
    eos=0x7f4315d98d04 "", dest=0x3289450, saved_location=SAVED_IN_CACHE, 
    want_extrainfo=1, allow_annotations=0, prepend_annotations=0x0)
    at routerparse.c:1199
#4  0x00000000004538c9 in router_load_extrainfo_from_string (
    s=0x7f4314e9ad57 "extra-info winters 810962DC3C058C757070420E9A9497532BB8185A\npublished 2012-05-09 23:40:20\nwrite-history 2012-05-09 23:27:30 (900 s) 25795584,41270272,50443264,54130688,27383808,35012608,15630336,39361"..., 
    eos=0x7f4315d98d04 "", saved_location=SAVED_IN_CACHE, 
    requested_fingerprints=0x0, descriptor_digests=0) at routerlist.c:3948
#5  0x000000000044aa7b in router_reload_router_list_impl (store=0x14a5610)
    at routerlist.c:847
#6  0x000000000044ad33 in router_reload_router_list () at routerlist.c:903
#7  0x000000000040cb7c in do_main_loop () at main.c:1864
#8  0x000000000040e348 in tor_main (argc=3, argv=0x7fff7eb37168) at main.c:2619
#9  0x0000000000408b84 in main (argc=3, argv=0x7fff7eb37168) at tor_main.c:30

comment:2 Changed 8 years ago by arma

Are we strlening on the entire extrainfo document each time?

comment:3 Changed 8 years ago by arma

I think we are.

extrainfo_parse_entry_from_string() has a const char *end, but it passes s into router_get_extrainfo_hash without any help from end.

comment:4 Changed 8 years ago by arma

Milestone: Tor: 0.2.4.x-finalTor: 0.2.3.x-final

comment:5 Changed 8 years ago by nickm

Status: newneeds_review

Fix in branch "bug5828" in my public repository, against Tor 0.2.2.x. Please review and merge if you like it.

comment:6 Changed 8 years ago by arma

Milestone: Tor: 0.2.3.x-finalTor: 0.2.2.x-final

Merged into 0.2.3.

Nick suggests we leave this pending on 0.2.2 for a while "and we see if we still care in a bit." I hope we don't, but here it is.

comment:7 Changed 8 years ago by nickm

Milestone: Tor: 0.2.2.x-finalTor: 0.2.3.x-final
Resolution: fixed
Status: needs_reviewclosed

closing as fixed-in-0.2.3.

comment:8 Changed 8 years ago by nickm

Keywords: tor-auth added

comment:9 Changed 8 years ago by nickm

Component: Tor Directory AuthorityTor
Note: See TracTickets for help on using tickets.