From: Alexander Bluhm Subject: Re: use the SMR api instead of SRPs in art/rtable code To: David Gwynne Cc: tech@openbsd.org Date: Thu, 26 Jun 2025 22:33:50 +0200 On Fri, Jun 13, 2025 at 04:44:56PM +1000, David Gwynne wrote: > On Fri, Jun 13, 2025 at 12:03:37PM +1000, David Gwynne wrote: > > there's other changes too, but moving to SMR is the important one. > > > > SRPs complicated this code massively, so moving it to SMR is almost like > > backing the SRP changes out. it becomes a lot more readable and similar > > to other ART implementations, which can't hurt. > > > > another change is strip non-ART code out of art.c, specifically the > > rwlock and route sourceaddr info. these features have been moved > > up a layer into rtable.c and are now stored as part of a new struct > > rtable. again, this makes the art code easier to read and compare. > > > > the other big change is to walking over an ART. there's now a > > reentract and non-recursive iterator api which art_walk and rtable_walk > > are now built on top of. rtable_walk can basically do a foreach > > over the ART directly rather than having to pass a bunch of state > > into callbacks to apply with art_walk. we can still do that if we > > want, i just find this easier to deal with in rtable_walk directly. > > > > i modified how the heaps are traversed inside ART as well to try and > > minimise the pointer accesses as much as possible. > > > > i'm sorry the diff is so big. i don't expect code reviews. it took > > me 4 years and at least 3 attempts to do this diff. however, tests > > would be much appreciated. > > > > it looks like the generated code is smaller too. > > apologies, i sent a slightly old version that missed some fixes around > reprio and mpath insertion. i didn't use scp enough before sending it > out. This time it crashes in regress/sbin/ifconfig ==== run-ether-inet6-contiguous-netmask ==== /sbin/ifconfig vether99 destroy 2>/dev/null || true /sbin/ifconfig vether99 create /sbin/ifconfig vether99 inet6 fdd7:e83e:66bc:254::74 netmask ffff:ffff:ffff:ffff:ffff:: /sbin/ifconfig vether99 inet6 fdd7:e83e:66bc:254::74 delete ! /sbin/ifconfig vether99 inet6 fdd7:e83e:66bc:254::74 netmask ffff:ffff:ffff:ffff:ffff:4000:: ifconfig: SIOCAIFADDR: Invalid argument Timeout, server ot29 not responding. panic: kernel diagnostic assertion "curcpu()->ci_schedstate.spc_smrdepth == 0" failed: file "/usr/src/sys/kern/subr_xxx.c", line 157 Stopped at db_enter+0x14: popq %rbp TID PID UID PRFLAGS PFLAGS CPU COMMAND 57177 76970 0 0x14000 0x200 4 sensors db_enter() at db_enter+0x14 panic(ffffffff825ee372) at panic+0xd5 __assert(ffffffff8262ac13,ffffffff8256b2e4,9d,ffffffff825e06cd) at __assert+0x29 assertwaitok() at assertwaitok+0xdc mi_switch() at mi_switch+0x218 sched_idle(ffff8000491d2ff0) at sched_idle+0x13a end trace frame: 0x0, count: 9 https://www.openbsd.org/ddb.html describes the minimum info required in bug reports. Insufficient info makes it difficult to find and fix bugs. ddb{1}> trace db_enter() at db_enter+0x14 panic(ffffffff825ee372) at panic+0xd5 __assert(ffffffff8262ac13,ffffffff8256b2e4,9d,ffffffff825e06cd) at __assert+0x29 assertwaitok() at assertwaitok+0xdc mi_switch() at mi_switch+0x218 sched_idle(ffff8000491d2ff0) at sched_idle+0x13a end trace frame: 0x0, count: -6 ddb{1}> show register rdi 0 rsi 0x10 rbp 0xffff800049772d50 rbx 0 rdx 0xfe00000000000000 rcx 0x282 rax 0x85 r8 0x101010101010101 r9 0x8080808080808080 r10 0xf324a6b3a496092d r11 0x22dfcd0f06da1750 r12 0 r13 0xffff8000491d32a0 r14 0 r15 0xffff8000491d3bd8 rip 0xffffffff8113a474 db_enter+0x14 cs 0x8 rflags 0x206 rsp 0xffff800049772d50 ss 0x10 db_enter+0x14: popq %rbp ddb{1}> ps PID TID PPID UID S FLAGS WAIT COMMAND 65031 167185 95186 0 3 0x10008a sigsusp sh 95186 413483 21722 0 3 0x10008a sigsusp make 21722 181825 51668 0 3 0x10008a sigsusp sh 51668 167105 35628 0 3 0x10008a sigsusp make 79005 301972 51355 0 3 0x100082 piperd gzip 51355 408100 35628 0 3 0x100082 piperd pax 35628 214919 1303 0 3 0x82 piperd perl 1303 309262 77038 0 3 0x10008a sigsusp ksh 77038 162015 15622 0 3 0x98 kqread sshd-session 15622 389973 71872 0 3 0x92 kqread sshd-session 29455 107815 1 0 3 0x100083 ttyin getty 46146 24277 1 0 3 0x100083 ttyin getty 38343 389764 1 0 3 0x100083 ttyin getty 70066 86976 1 0 3 0x100083 ttyin getty 55197 306882 1 0 3 0x100083 ttyin getty 31968 35364 1 0 3 0x100083 ttyin getty 52630 262572 1 0 3 0x100098 kqread cron 10440 346796 1 99 3 0x1100090 kqread sndiod 30983 382603 1 110 3 0x100090 kqread sndiod 75328 424278 7765 95 3 0x1100092 kqread smtpd 81455 23880 7765 103 3 0x1100092 kqread smtpd 60857 393451 7765 95 3 0x1100092 kqread smtpd 45873 224221 7765 95 3 0x100092 kqread smtpd 52702 99794 7765 95 3 0x1100092 kqread smtpd 58994 265172 7765 95 3 0x1100092 kqread smtpd 7765 434673 1 0 3 0x100080 kqread smtpd 48310 318854 73410 91 3 0x92 kqread snmpd_metrics 53609 308665 73410 91 3 0x1100092 kqread snmpd 73410 483655 1 0 3 0x100080 kqread snmpd 71872 506089 1 0 3 0x88 kqread sshd 64050 11918 0 0 3 0x14200 acct acct 95501 445237 0 0 3 0x14280 nfsidl nfsio 88388 89678 0 0 3 0x14280 nfsidl nfsio 98128 330474 0 0 3 0x14280 nfsidl nfsio 35300 299285 0 0 3 0x14280 nfsidl nfsio 43217 499466 1 0 3 0x100080 kqread ntpd 35901 227030 29522 83 3 0x100092 kqread ntpd 29522 54779 1 83 3 0x1100092 kqread ntpd 98047 59907 98236 74 3 0x1100092 bpf pflogd 98236 483990 1 0 3 0x80 sbwait pflogd 34550 98595 74398 73 3 0x1100090 kqread syslogd 74398 170351 1 0 3 0x100082 sbwait syslogd 9287 276295 1 0 3 0x100080 kqread resolvd 42289 49490 84025 77 3 0x100092 kqread dhcpleased 89025 311440 84025 77 3 0x100092 kqread dhcpleased 84025 198976 1 0 3 0x80 kqread dhcpleased 7560 51967 28967 115 3 0x100092 kqread slaacd 47554 502560 28967 115 3 0x100092 kqread slaacd 28967 140135 1 0 3 0x100080 kqread slaacd 80546 329744 0 0 3 0x14200 bored smr 47993 87991 0 0 3 0x14200 pgzero zerothread 94383 90344 0 0 3 0x14200 aiodoned aiodoned 9809 358278 0 0 3 0x14200 syncer update 59089 11376 0 0 3 0x14200 cleaner cleaner 5959 66152 0 0 3 0x14200 reaper reaper 31905 499218 0 0 3 0x14200 pgdaemon pagedaemon 34584 291 0 0 3 0x14200 bored wsdisplay0 73685 407600 0 0 3 0x14200 mmctsk sdmmc0 13891 413451 0 0 3 0x14200 usbtsk usbtask 30279 444504 0 0 3 0x14200 usbatsk usbatsk 68270 152571 0 0 3 0x40014200 acpi0 acpi0 10764 101012 0 0 7 0x40014200 idle11 57461 101227 0 0 7 0x40014200 idle10 55800 147769 0 0 7 0x40014200 idle9 93447 192884 0 0 7 0x40014200 idle8 7223 454164 0 0 7 0x40014200 idle7 72300 126457 0 0 7 0x40014200 idle6 74256 216536 0 0 7 0x40014200 idle5 32561 107546 0 0 3 0x40014200 idle4 64675 408456 0 0 7 0x40014200 idle3 52624 274420 0 0 7 0x40014200 idle2 *47718 72204 0 0 7 0x40014200 idle1 76970 57177 0 0 7 0x14200 sensors 78440 368691 0 0 3 0x14200 bored softnet3 79641 80710 0 0 3 0x14200 bored softnet2 71296 297826 0 0 3 0x14200 bored softnet1 36143 4573 0 0 3 0x14200 bored softnet0 23881 430264 0 0 3 0x14200 smrbar systqmp 27179 278673 0 0 3 0x14200 bored systq 83106 261401 0 0 3 0x14200 tmoslp softclockmp 76184 188269 0 0 3 0x40014200 tmoslp softclock 87575 477579 0 0 7 0x40014200 idle0 1 301649 0 0 3 0x82 wait init 0 0 -1 0 3 0x10010200 scheduler swapper ddb{1}> show all locks Process 23881 (systqmp) thread 0xffff8000ffffe7b0 (430264) shared rwlock systqmp r = 0 (0xffffffff82a2e5b0) ddb{1}> show all routes Route tree for af 2, rtableid 0 rtentry=0xfffffd8777f17bb8 flags=0x803 refcnt=2 use=71 expire=0 key=[16,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=0 gw=[16,2,0,0,10,0,1,1,0,0,0,0,0,0,0,0] ifidx=1 ifa=0xffff8000012e2c00 ifa_addr=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifa_dsta=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] ifa_mask=[7,0,0,0,255,255,255] flags=0x0, refcnt=7, metric=0 gwroute=0xfffffd8777f17dc8 llinfo=0x0 priority=8 rtentry=0xfffffd8777f17a58 flags=0x809 refcnt=2 use=1 expire=0 key=[16,2,0,0,224,0,0,0,0,0,0,0,0,0,0,0] plen=4 gw=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] ifidx=6 ifa=0xffff8000012e2500 ifa_addr=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] ifa_dsta=[] ifa_mask=[5,0,0,0,255] flags=0x0, refcnt=4, metric=0 gwroute=0x0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b79a0 flags=0x800101 refcnt=4 use=1581 expire=0 key=[16,2,0,0,10,0,1,0,0,0,0,0,0,0,0,0] plen=24 gw=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifidx=1 ifa=0xffff8000012e2c00 ifa_addr=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifa_dsta=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] ifa_mask=[7,0,0,0,255,255,255] flags=0x0, refcnt=7, metric=0 gwroute=0x0 llinfo=0x0 priority=4 rtentry=0xfffffd8777f17dc8 flags=0x30405 refcnt=5 use=834 expire=6746 key=[16,2,0,0,10,0,1,1,0,0,0,0,0,0,0,0] plen=32 gw=[32,18,1,0,6,0,6,0,144,226,186,157,240,63,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ifidx=1 ifa=0xffff8000012e2c00 ifa_addr=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifa_dsta=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] ifa_mask=[7,0,0,0,255,255,255] flags=0x0, refcnt=7, metric=0 gwroute=0x0 llinfo=0xfffffd8778198e00 priority=3 rtentry=0xfffffd8777f17798 flags=0x10405 refcnt=7 use=254 expire=6707 key=[16,2,0,0,10,0,1,2,0,0,0,0,0,0,0,0] plen=32 gw=[32,18,1,0,6,0,6,0,0,3,186,12,11,82,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ifidx=1 ifa=0xffff8000012e2c00 ifa_addr=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifa_dsta=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] ifa_mask=[7,0,0,0,255,255,255] flags=0x0, refcnt=7, metric=0 gwroute=0x0 llinfo=0xfffffd8778198d80 priority=3 rtentry=0xfffffd87784b78f0 flags=0x200405 refcnt=3 use=1834 expire=0 key=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] plen=32 gw=[32,18,1,0,6,3,6,0,101,109,48,208,80,153,249,215,11,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ifidx=1 ifa=0xffff8000012e2c00 ifa_addr=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifa_dsta=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] ifa_mask=[7,0,0,0,255,255,255] flags=0x0, refcnt=7, metric=0 gwroute=0x0 llinfo=0xfffffd8778198f00 priority=1 rtentry=0xfffffd87784b7b00 flags=0x400005 refcnt=2 use=0 expire=0 key=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] plen=32 gw=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifidx=1 ifa=0xffff8000012e2c00 ifa_addr=[16,2,0,0,10,0,1,49,0,0,0,0,0,0,0,0] ifa_dsta=[16,2,0,0,10,0,1,255,0,0,0,0,0,0,0,0] ifa_mask=[7,0,0,0,255,255,255] flags=0x0, refcnt=7, metric=0 gwroute=0x0 llinfo=0x0 priority=1 rtentry=0xfffffd8777f17008 flags=0x200005 refcnt=2 use=0 expire=0 key=[16,2,0,0,10,188,253,1,0,0,0,0,0,0,0,0] plen=32 gw=[16,2,0,0,10,188,253,1,0,0,0,0,0,0,0,0] ifidx=46 ifa=0xffff8000018b4400 ifa_addr=[16,2,0,0,10,188,253,1,0,0,0,0,0,0,0,0] ifa_dsta=[] ifa_mask=[5,0,0,0,255] flags=0x0, refcnt=2, metric=0 gwroute=0x0 llinfo=0x0 priority=1 rtentry=0xfffffd8777f178f8 flags=0x80b refcnt=2 use=0 expire=0 key=[16,2,0,0,127,0,0,0,0,0,0,0,0,0,0,0] plen=8 gw=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] ifidx=6 ifa=0xffff8000012e2500 ifa_addr=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] ifa_dsta=[] ifa_mask=[5,0,0,0,255] flags=0x0, refcnt=4, metric=0 gwroute=0xfffffd87784b7160 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7160 flags=0x220005 refcnt=6 use=15806 expire=0 key=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] plen=32 gw=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] ifidx=6 ifa=0xffff8000012e2500 ifa_addr=[16,2,0,0,127,0,0,1,0,0,0,0,0,0,0,0] ifa_dsta=[] ifa_mask=[5,0,0,0,255] flags=0x0, refcnt=4, metric=0 gwroute=0x0 llinfo=0x0 priority=1 Route tree for af 24, rtableid 0 rtentry=0xfffffd87784b7840 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=96 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b72c0 flags=0x220005 refcnt=12 use=50 expire=0 key=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] plen=128 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0x0 llinfo=0x0 priority=1 rtentry=0xfffffd87784b7210 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,255,255,0,0,0,0,0,0,0,0] plen=96 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b74d0 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,32,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=24 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7420 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,32,2,127,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=24 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7370 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,32,2,224,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=20 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7580 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,32,2,255,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=24 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b70b0 flags=0x80b refcnt=2 use=5 expire=0 key=[28,24,0,0,0,0,0,0,254,128,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=10 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7000 flags=0x80b refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,254,192,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=10 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7e70 flags=0x800100 refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=64 gw=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifidx=2 ifa=0xffff80000056eb00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0x0 priority=132 rtentry=0xfffffd87784b7c60 flags=0x200405 refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] plen=128 gw=[32,18,2,0,6,3,6,0,101,109,49,208,80,153,249,215,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ifidx=2 ifa=0xffff80000056eb00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0xfffffd8777f6cea0 priority=1 rtentry=0xfffffd87784b7bb0 flags=0x200005 refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] plen=128 gw=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2100 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=4, metric=0 gwroute=0x0 llinfo=0x0 priority=1 rtentry=0xfffffd8777f17168 flags=0x800101 refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=64 gw=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifidx=52 ifa=0xffff8000018c2c00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0x0 priority=4 rtentry=0xfffffd8777f170b8 flags=0x200405 refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] plen=128 gw=[32,18,52,0,6,8,6,0,118,101,116,104,101,114,57,57,254,225,186,210,86,226,0,0,0,0,0,0,0,0,0,0] ifidx=52 ifa=0xffff8000018c2c00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0xfffffd8777f6ce10 priority=1 rtentry=0xfffffd87784b7630 flags=0x80b refcnt=2 use=48 expire=0 key=[28,24,0,0,0,0,0,0,255,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=16 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7dc0 flags=0x200 refcnt=2 use=0 expire=0 key=[28,24,0,0,0,0,0,0,255,1,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=32 gw=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifidx=2 ifa=0xffff80000056eb00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0x0 priority=132 rtentry=0xfffffd87784b7790 flags=0x201 refcnt=2 use=1 expire=0 key=[28,24,0,0,0,0,0,0,255,1,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=32 gw=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2100 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=4, metric=0 gwroute=0x0 llinfo=0x0 priority=4 rtentry=0xfffffd8777f17638 flags=0x201 refcnt=2 use=2 expire=0 key=[28,24,0,0,0,0,0,0,255,1,0,52,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=32 gw=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifidx=52 ifa=0xffff8000018c2c00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0x0 priority=4 rtentry=0xfffffd87784b76e0 flags=0x80b refcnt=2 use=48 expire=0 key=[28,24,0,0,0,0,0,0,255,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=16 gw=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2700 ifa_addr=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[28,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,0,0,0,0] flags=0x0, refcnt=12, metric=0 gwroute=0xfffffd87784b72c0 llinfo=0x0 priority=8 rtentry=0xfffffd87784b7d10 flags=0x200 refcnt=2 use=1 expire=0 key=[28,24,0,0,0,0,0,0,255,2,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=32 gw=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifidx=2 ifa=0xffff80000056eb00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,2,0,0,0,0,210,80,153,255,254,249,215,12,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0x0 priority=132 rtentry=0xfffffd87784b7a50 flags=0x201 refcnt=2 use=1 expire=0 key=[28,24,0,0,0,0,0,0,255,2,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=32 gw=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifidx=6 ifa=0xffff8000012e2100 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,6,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0] ifa_dsta=[] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=4, metric=0 gwroute=0x0 llinfo=0x0 priority=4 rtentry=0xfffffd8777f172c8 flags=0x201 refcnt=2 use=2 expire=0 key=[28,24,0,0,0,0,0,0,255,2,0,52,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] plen=32 gw=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifidx=52 ifa=0xffff8000018c2c00 ifa_addr=[28,24,0,0,0,0,0,0,254,128,0,52,0,0,0,0,252,225,186,255,254,210,86,226,0,0,0,0] ifa_dsta=[NULL] ifa_mask=[28,24,0,0,0,0,0,0,255,255,255,255,255,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0] flags=0x0, refcnt=5, metric=0 gwroute=0x0 llinfo=0x0 priority=4 Can you reporduce it? Anything else I should collect from ddb? bluhm > Index: art.c > =================================================================== > RCS file: /cvs/src/sys/net/art.c,v > diff -u -p -r1.31 art.c > --- art.c 11 Nov 2023 12:17:50 -0000 1.31 > +++ art.c 13 Jun 2025 06:40:59 -0000 > @@ -22,6 +22,58 @@ > * > * Yoichi Hariguchi paper can be found at: > * http://www.hariguchi.org/art/art.pdf > + * > + * This implementation is tweaked to minimise pointer traversal > + * during lookups by only accessing the heaps it avoids following > + * pointers to or through the art_table structures. > + * > + * The heap is an array of art_heap_entry values which have different > + * meanings depending on their location. The majority of entries in > + * the heap are used as pointers to nodes (struct an_node, aka leaf > + * entries), or the next heap to traverse. These pointers are typed/ > + * tagged by the low bit in their heap value, and must be masked > + * appropriately before use. > + * > + * The first two entries in the heap are not used by the search > + * algorithm, so they are used to store data associated with this > + * part of the heap. The first entry (heap[0]) stores a pointer to > + * an art_table struct associated with this heap. The second entry > + * (heap[1]) stores the node pointer which would be in the parent > + * heap if this table wasn't using it. This node pointer is also known > + * as the default entry/route for the current table in the ART. > + * > + * Nodes contain the exact information about the prefix they represent > + * in the ART, ie, the address and prefix length, and a pointer to > + * data associated with that prefix (an_value). > + * > + * The relationships between the separate data structures looks > + * like the following: > + * > + * +------------------+ > + * | struct art | > + * +------------------+ NULL > + * | ^ > + * | art_root | at_parent > + * v | > + * +------------------+ heap[0] +------------------+ > + * | heap |------------>| struct art_table | > + * +------------------+ +------------------+ > + * | ^ > + * | heap entry | at_parent > + * v | > + * +------------------+ heap[0] +------------------+ > + * | heap |------------>| struct art_table | > + * +------------------+ +------------------+ > + * | > + * | node entry > + * v > + * +------------------+ > + * | struct art_node | > + * +------------------+ > + * | > + * | an_value > + * v > + * "user" data > */ > > #ifndef _KERNEL > @@ -33,43 +85,96 @@ > #include > #include > #include > +#include > #endif > > #include > > -int art_bindex(struct art_table *, const uint8_t *, int); > -void art_allot(struct art_table *at, int, struct art_node *, > - struct art_node *); > -struct art_table *art_table_get(struct art_root *, struct art_table *, > - int); > -struct art_table *art_table_put(struct art_root *, struct art_table *); > -struct art_node *art_table_insert(struct art_root *, struct art_table *, > +/* > + * Allotment Table. > + */ > +struct art_table { > + art_heap_entry *at_heap; > + struct art_table *at_parent; /* Parent table */ > + > + unsigned int at_index; /* Index in the parent table */ > + unsigned int at_minfringe; /* Index that fringe begins */ > + > + unsigned int at_level; /* Level of the table */ > + unsigned int at_bits; /* Stride length of the table */ > + unsigned int at_offset; /* Sum of parents' stride len */ > + > + unsigned int at_refcnt; > +}; > + > +static void art_allot(struct art_table *at, unsigned int, > + art_heap_entry, art_heap_entry); > +struct art_table *art_table_get(struct art *, struct art_table *, > + unsigned int); > +struct art_table *art_table_put(struct art *, struct art_table *); > +struct art_node *art_table_insert(struct art *, struct art_table *, > int, struct art_node *); > -struct art_node *art_table_delete(struct art_root *, struct art_table *, > +struct art_node *art_table_delete(struct art *, struct art_table *, > int, struct art_node *); > -struct art_table *art_table_ref(struct art_root *, struct art_table *); > -int art_table_free(struct art_root *, struct art_table *); > -int art_table_walk(struct art_root *, struct art_table *, > - int (*f)(struct art_node *, void *), void *); > -int art_walk_apply(struct art_root *, > - struct art_node *, struct art_node *, > - int (*f)(struct art_node *, void *), void *); > +struct art_table *art_table_ref(struct art *, struct art_table *); > +int art_table_free(struct art *, struct art_table *); > void art_table_gc(void *); > void art_gc(void *); > > -struct pool an_pool, at_pool, at_heap_4_pool, at_heap_8_pool; > +static struct pool an_pool, at_pool, at_heap_4_pool, at_heap_8_pool; > > -struct art_table *art_table_gc_list = NULL; > -struct mutex art_table_gc_mtx = MUTEX_INITIALIZER(IPL_SOFTNET); > -struct task art_table_gc_task = > +static struct art_table *art_table_gc_list = NULL; > +static struct mutex art_table_gc_mtx = MUTEX_INITIALIZER(IPL_SOFTNET); > +static struct task art_table_gc_task = > TASK_INITIALIZER(art_table_gc, NULL); > > -struct art_node *art_node_gc_list = NULL; > -struct mutex art_node_gc_mtx = MUTEX_INITIALIZER(IPL_SOFTNET); > -struct task art_node_gc_task = TASK_INITIALIZER(art_gc, NULL); > +static struct art_node *art_node_gc_list = NULL; > +static struct mutex art_node_gc_mtx = MUTEX_INITIALIZER(IPL_SOFTNET); > +static struct task art_node_gc_task = TASK_INITIALIZER(art_gc, NULL); > + > +#define ART_HEAP_IDX_TABLE 0 > +#define ART_HEAP_IDX_DEFAULT 1 > + > +#define AT_HEAPSIZE(bits) ((1 << ((bits) + 1)) * sizeof(art_heap_entry)) > + > +static inline struct art_table * > +art_heap_to_table(art_heap_entry *heap) > +{ > + return ((struct art_table *)heap[ART_HEAP_IDX_TABLE]); > +} > + > +static inline int > +art_heap_entry_is_node(art_heap_entry ahe) > +{ > + return (!ISSET(ahe, 1)); > +} > + > +static inline struct art_node * > +art_heap_entry_to_node(art_heap_entry ahe) > +{ > + return ((struct art_node *)ahe); > +} > + > +static inline art_heap_entry * > +art_heap_entry_to_heap(art_heap_entry ahe) > +{ > + return ((art_heap_entry *)(ahe & ~1ULL)); > +} > + > +static inline art_heap_entry > +art_node_to_heap_entry(struct art_node *an) > +{ > + return ((art_heap_entry)an); > +} > + > +static inline art_heap_entry > +art_heap_to_heap_entry(art_heap_entry *heap) > +{ > + return ((art_heap_entry)heap | 1ULL); > +} > > void > -art_init(void) > +art_boot(void) > { > pool_init(&an_pool, sizeof(struct art_node), 0, IPL_SOFTNET, 0, > "art_node", NULL); > @@ -84,56 +189,74 @@ art_init(void) > /* > * Per routing table initialization API function. > */ > -struct art_root * > -art_alloc(unsigned int rtableid, unsigned int alen, unsigned int off) > -{ > - struct art_root *ar; > - int i; > > - ar = malloc(sizeof(*ar), M_RTABLE, M_NOWAIT|M_ZERO); > - if (ar == NULL) > - return (NULL); > +static const unsigned int art_plen32_levels[] = { > + 8, 4, 4, 4, 4, 4, 4 > +}; > + > +static const unsigned int art_plen128_levels[] = { > + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, > + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 > +}; > + > +static const unsigned int art_plen20_levels[] = { > + 4, 4, 4, 4, 4 > +}; > + > +void > +art_init(struct art *art, unsigned int alen) > +{ > + const unsigned int *levels; > + unsigned int nlevels; > +#ifdef DIAGNOSTIC > + unsigned int i; > + unsigned int bits = 0; > +#endif > > switch (alen) { > case 32: > - ar->ar_alen = 32; > - ar->ar_nlvl = 7; > - ar->ar_bits[0] = 8; > - for (i = 1; i < ar->ar_nlvl; i++) > - ar->ar_bits[i] = 4; > + levels = art_plen32_levels; > + nlevels = nitems(art_plen32_levels); > break; > case 128: > - ar->ar_alen = 128; > - ar->ar_nlvl = 32; > - for (i = 0; i < ar->ar_nlvl; i++) > - ar->ar_bits[i] = 4; > + levels = art_plen128_levels; > + nlevels = nitems(art_plen128_levels); > + break; > + case 20: > + levels = art_plen20_levels; > + nlevels = nitems(art_plen20_levels); > break; > default: > - printf("%s: incorrect address length %u\n", __func__, alen); > - free(ar, M_RTABLE, sizeof(*ar)); > - return (NULL); > + panic("no configuration for alen %u", alen); > + /* NOTREACHED */ > } > > - ar->ar_off = off; > - rw_init(&ar->ar_lock, "art"); > +#ifdef DIAGNOSTIC > + for (i = 0; i < nlevels; i++) > + bits += levels[i]; > + > + if (alen != bits) > + panic("sum of levels %u != address len %u", bits, alen); > +#endif /* DIAGNOSTIC */ > > - return (ar); > + art->art_root = 0; > + art->art_levels = levels; > + art->art_nlevels = nlevels; > + art->art_alen = alen; > } > > -/* > - * Return 1 if ``old'' and ``new`` are identical, 0 otherwise. > - */ > -static inline int > -art_check_duplicate(struct art_root *ar, struct art_node *old, > - struct art_node *new) > +struct art * > +art_alloc(unsigned int alen) > { > - if (old == NULL) > - return (0); > + struct art *art; > > - if (old->an_plen == new->an_plen) > - return (1); > + art = malloc(sizeof(*art), M_RTABLE, M_NOWAIT|M_ZERO); > + if (art == NULL) > + return (NULL); > > - return (0); > + art_init(art, alen); > + > + return (art); > } > > /* > @@ -148,30 +271,31 @@ art_check_duplicate(struct art_root *ar, > * 8bit-long tables, there's a maximum of 4 base indexes if the > * prefix length is > 24. > */ > -int > -art_bindex(struct art_table *at, const uint8_t *addr, int plen) > +static unsigned int __pure > +art_bindex(unsigned int offset, unsigned int bits, > + const uint8_t *addr, unsigned int plen) > { > - uint8_t boff, bend; > + unsigned int boff, bend; > uint32_t k; > > - if (plen < at->at_offset || plen > (at->at_offset + at->at_bits)) > - return (-1); > + KASSERT(plen >= offset); > + KASSERT(plen <= (offset + bits)); > > /* > * We are only interested in the part of the prefix length > * corresponding to the range of this table. > */ > - plen -= at->at_offset; > + plen -= offset; > > /* > * Jump to the first byte of the address containing bits > * covered by this table. > */ > - addr += (at->at_offset / 8); > + addr += (offset / 8); > > /* ``at'' covers the bit range between ``boff'' & ``bend''. */ > - boff = (at->at_offset % 8); > - bend = (at->at_bits + boff); > + boff = (offset % 8); > + bend = (bits + boff); > > KASSERT(bend <= 32); > > @@ -188,25 +312,13 @@ art_bindex(struct art_table *at, const u > k = (addr[0] & ((1 << (8 - boff)) - 1)) << (bend - 8); > k |= addr[1] >> (16 - bend); > } else { > - k = (addr[0] >> (8 - bend)) & ((1 << at->at_bits) - 1); > + k = (addr[0] >> (8 - bend)) & ((1 << bits) - 1); > } > > /* > * Single level base index formula: > */ > - return ((k >> (at->at_bits - plen)) + (1 << plen)); > -} > - > -/* > - * Single level lookup function. > - * > - * Return the fringe index of the part of ``addr'' > - * corresponding to the range covered by the table ``at''. > - */ > -static inline int > -art_findex(struct art_table *at, const uint8_t *addr) > -{ > - return art_bindex(at, addr, (at->at_offset + at->at_bits)); > + return ((k >> (bits - plen)) + (1 << plen)); > } > > /* > @@ -215,60 +327,94 @@ art_findex(struct art_table *at, const u > * Return the best existing match for a destination. > */ > struct art_node * > -art_match(struct art_root *ar, const void *addr, struct srp_ref *nsr) > +art_match(struct art *art, const void *addr) > { > - struct srp_ref dsr, ndsr; > - void *entry; > - struct art_table *at; > - struct art_node *dflt, *ndflt; > - int j; > - > - entry = srp_enter(nsr, &ar->ar_root); > - at = entry; > + unsigned int offset = 0; > + unsigned int level = 0; > + art_heap_entry *heap; > + art_heap_entry ahe, dahe = 0; > + struct art_node *an; > + int j; > > - if (at == NULL) > - goto done; > + SMR_ASSERT_CRITICAL(); > > - /* > - * Remember the default route of each table we visit in case > - * we do not find a better matching route. > - */ > - dflt = srp_enter(&dsr, &at->at_default); > + heap = SMR_PTR_GET(&art->art_root); > + if (heap == NULL) > + return (NULL); > > /* > * Iterate until we find a leaf. > */ > - while (1) { > + for (;;) { > + unsigned int bits = art->art_levels[level]; > + unsigned int p = offset + bits; > + > + /* > + * Remember the default route of each table we visit in case > + * we do not find a better matching route. > + */ > + ahe = SMR_PTR_GET(&heap[ART_HEAP_IDX_DEFAULT]); > + if (ahe != 0) > + dahe = ahe; > + > /* Do a single level route lookup. */ > - j = art_findex(at, addr); > - entry = srp_follow(nsr, &at->at_heap[j].node); > + j = art_bindex(offset, bits, addr, p); > + ahe = SMR_PTR_GET(&heap[j]); > > /* If this is a leaf (NULL is a leaf) we're done. */ > - if (ISLEAF(entry)) > + if (art_heap_entry_is_node(ahe)) > break; > > - at = SUBTABLE(entry); > + heap = art_heap_entry_to_heap(ahe); > + offset = p; > + level++; > + > + KASSERT(level < art->art_nlevels); > + } > + > + an = art_heap_entry_to_node(ahe); > + if (an != NULL) > + return (an); > + > + return art_heap_entry_to_node(dahe); > +} > + > +static int > +art_node_check(const struct art_node *an, > + const uint8_t *addr, unsigned int plen) > +{ > + const uint32_t *wan = (const uint32_t *)an->an_addr; > + const uint32_t *waddr = (const uint32_t *)addr; > + unsigned int i = 0; > + unsigned int shift; > + > + if (an->an_plen != plen) > + return (0); > + > + while (plen >= 32) { > + if (wan[i] != waddr[i]) > + return (0); > + > + i++; > + plen -= 32; > + } > + if (plen == 0) > + return (1); > + > + i *= 4; > + while (plen >= 8) { > + if (an->an_addr[i] != addr[i]) > + return (0); > + > + i++; > + plen -= 8; > + } > + if (plen == 0) > + return (1); > + > + shift = 8 - plen; > > - ndflt = srp_enter(&ndsr, &at->at_default); > - if (ndflt != NULL) { > - srp_leave(&dsr); > - dsr = ndsr; > - dflt = ndflt; > - } else > - srp_leave(&ndsr); > - } > - > - if (entry == NULL) { > - srp_leave(nsr); > - *nsr = dsr; > - KASSERT(ISLEAF(dflt)); > - return (dflt); > - } > - > - srp_leave(&dsr); > -done: > - KASSERT(ISLEAF(entry)); > - return (entry); > + return ((an->an_addr[i] >> shift) == (addr[i] >> shift)); > } > > /* > @@ -278,24 +424,28 @@ done: > * it does not exist. > */ > struct art_node * > -art_lookup(struct art_root *ar, const void *addr, int plen, struct srp_ref *nsr) > +art_lookup(struct art *art, const void *addr, unsigned int plen) > { > - void *entry; > - struct art_table *at; > - int i, j; > + unsigned int offset = 0; > + unsigned int bits, p; > + unsigned int level = 0; > + art_heap_entry *heap; > + art_heap_entry ahe; > + struct art_node *an; > + unsigned int i, j; > > - KASSERT(plen >= 0 && plen <= ar->ar_alen); > + KASSERT(plen <= art->art_alen); > > - entry = srp_enter(nsr, &ar->ar_root); > - at = entry; > + SMR_ASSERT_CRITICAL(); > > - if (at == NULL) > - goto done; > + heap = SMR_PTR_GET(&art->art_root); > + if (heap == NULL) > + return (NULL); > > /* Default route */ > if (plen == 0) { > - entry = srp_follow(nsr, &at->at_default); > - goto done; > + ahe = SMR_PTR_GET(&heap[ART_HEAP_IDX_DEFAULT]); > + return art_heap_entry_to_node(ahe); > } > > /* > @@ -303,31 +453,47 @@ art_lookup(struct art_root *ar, const vo > * the stride length at this level the entry must > * be in the current table. > */ > - while (plen > (at->at_offset + at->at_bits)) { > + for (;;) { > + bits = art->art_levels[level]; > + p = offset + bits; > + if (plen <= p) > + break; > + > /* Do a single level route lookup. */ > - j = art_findex(at, addr); > - entry = srp_follow(nsr, &at->at_heap[j].node); > + j = art_bindex(offset, bits, addr, p); > + ahe = SMR_PTR_GET(&heap[j]); > > /* A leaf is a match, but not a perfect one, or NULL */ > - if (ISLEAF(entry)) > + if (art_heap_entry_is_node(ahe)) > return (NULL); > > - at = SUBTABLE(entry); > + heap = art_heap_entry_to_heap(ahe); > + offset = p; > + level++; > + > + KASSERT(level < art->art_nlevels); > } > > - i = art_bindex(at, addr, plen); > - if (i == -1) > - return (NULL); > + i = art_bindex(offset, bits, addr, plen); > + ahe = SMR_PTR_GET(&heap[i]); > + if (!art_heap_entry_is_node(ahe)) { > + heap = art_heap_entry_to_heap(ahe); > + ahe = SMR_PTR_GET(&heap[ART_HEAP_IDX_DEFAULT]); > + } > + > + /* Make sure we've got a perfect match */ > + an = art_heap_entry_to_node(ahe); > + if (an != NULL && art_node_check(an, addr, plen)) > + return (an); > > - entry = srp_follow(nsr, &at->at_heap[i].node); > - if (!ISLEAF(entry)) > - entry = srp_follow(nsr, &SUBTABLE(entry)->at_default); > - > -done: > - KASSERT(ISLEAF(entry)); > - return (entry); > + return (NULL); > } > > +int > +art_is_empty(struct art *art) > +{ > + return (SMR_PTR_GET_LOCKED(&art->art_root) == NULL); > +} > > /* > * Insertion API function. > @@ -336,32 +502,38 @@ done: > * same destination/mask pair is already present. > */ > struct art_node * > -art_insert(struct art_root *ar, struct art_node *an, const void *addr, int plen) > +art_insert(struct art *art, struct art_node *an) > { > - struct art_table *at, *child; > - struct art_node *node; > - int i, j; > - > - rw_assert_wrlock(&ar->ar_lock); > - KASSERT(plen >= 0 && plen <= ar->ar_alen); > - > - at = srp_get_locked(&ar->ar_root); > - if (at == NULL) { > - at = art_table_get(ar, NULL, -1); > + unsigned int p; > + art_heap_entry ahe, oahe, *ahep; > + art_heap_entry *heap; > + struct art_node *oan; > + struct art_table *at; > + unsigned int i, j; > + > + KASSERT(an->an_plen <= art->art_alen); > + > + heap = SMR_PTR_GET_LOCKED(&art->art_root); > + if (heap == NULL) { > + at = art_table_get(art, NULL, -1); > if (at == NULL) > return (NULL); > > - srp_swap_locked(&ar->ar_root, at); > - } > + heap = at->at_heap; > + SMR_PTR_SET_LOCKED(&art->art_root, heap); > + } else > + at = art_heap_to_table(heap); > > /* Default route */ > - if (plen == 0) { > - node = srp_get_locked(&at->at_default); > - if (node != NULL) > - return (node); > + if (an->an_plen == 0) { > + ahep = &heap[ART_HEAP_IDX_DEFAULT]; > + oahe = SMR_PTR_GET_LOCKED(ahep); > + oan = art_heap_entry_to_node(oahe); > + if (oan != NULL) > + return (oan); > > - art_table_ref(ar, at); > - srp_swap_locked(&at->at_default, an); > + art_table_ref(art, at); > + SMR_PTR_SET_LOCKED(ahep, art_node_to_heap_entry(an)); > return (an); > } > > @@ -370,10 +542,11 @@ art_insert(struct art_root *ar, struct a > * the stride length at this level the entry must > * be in the current table. > */ > - while (plen > (at->at_offset + at->at_bits)) { > + while ((p = at->at_offset + at->at_bits) < an->an_plen) { > /* Do a single level route lookup. */ > - j = art_findex(at, addr); > - node = srp_get_locked(&at->at_heap[j].node); > + j = art_bindex(at->at_offset, at->at_bits, an->an_addr, p); > + ahep = &heap[j]; > + ahe = SMR_PTR_GET_LOCKED(ahep); > > /* > * If the node corresponding to the fringe index is > @@ -381,84 +554,86 @@ art_insert(struct art_root *ar, struct a > * entry of this node will then become the default > * route of the subtable. > */ > - if (ISLEAF(node)) { > - child = art_table_get(ar, at, j); > + if (art_heap_entry_is_node(ahe)) { > + struct art_table *child = art_table_get(art, at, j); > if (child == NULL) > return (NULL); > > - art_table_ref(ar, at); > - srp_swap_locked(&at->at_heap[j].node, ASNODE(child)); > + art_table_ref(art, at); > + > at = child; > - } else > - at = SUBTABLE(node); > + heap = at->at_heap; > + SMR_PTR_SET_LOCKED(&heap[ART_HEAP_IDX_DEFAULT], ahe); > + SMR_PTR_SET_LOCKED(ahep, art_heap_to_heap_entry(heap)); > + } else { > + heap = art_heap_entry_to_heap(ahe); > + at = art_heap_to_table(heap); > + } > } > > - i = art_bindex(at, addr, plen); > - if (i == -1) > - return (NULL); > - > - return (art_table_insert(ar, at, i, an)); > -} > - > -/* > - * Single level insertion. > - */ > -struct art_node * > -art_table_insert(struct art_root *ar, struct art_table *at, int i, > - struct art_node *an) > -{ > - struct art_node *prev, *node; > - > - node = srp_get_locked(&at->at_heap[i].node); > - if (!ISLEAF(node)) > - prev = srp_get_locked(&SUBTABLE(node)->at_default); > - else > - prev = node; > - > - if (art_check_duplicate(ar, prev, an)) > - return (prev); > + i = art_bindex(at->at_offset, at->at_bits, an->an_addr, an->an_plen); > + ahep = &heap[i]; > + oahe = SMR_PTR_GET_LOCKED(ahep); > + if (!art_heap_entry_is_node(oahe)) { > + heap = art_heap_entry_to_heap(oahe); > + ahep = &heap[ART_HEAP_IDX_DEFAULT]; > + oahe = SMR_PTR_GET_LOCKED(ahep); > + } > > - art_table_ref(ar, at); > + /* Check if there's an existing node */ > + oan = art_heap_entry_to_node(oahe); > + if (oan != NULL && art_node_check(oan, an->an_addr, an->an_plen)) > + return (oan); > > /* > * If the index `i' of the route that we are inserting is not > * a fringe index, we need to allot this new route pointer to > * all the corresponding fringe indices. > */ > + art_table_ref(art, at); > + ahe = art_node_to_heap_entry(an); > if (i < at->at_minfringe) > - art_allot(at, i, prev, an); > - else if (!ISLEAF(node)) > - srp_swap_locked(&SUBTABLE(node)->at_default, an); > + art_allot(at, i, oahe, ahe); > else > - srp_swap_locked(&at->at_heap[i].node, an); > + SMR_PTR_SET_LOCKED(ahep, ahe); > > return (an); > } > > - > /* > * Deletion API function. > */ > struct art_node * > -art_delete(struct art_root *ar, struct art_node *an, const void *addr, int plen) > +art_delete(struct art *art, const void *addr, unsigned int plen) > { > + unsigned int p; > + art_heap_entry *heap; > struct art_table *at; > - struct art_node *node; > - int i, j; > + art_heap_entry ahe, pahe, *ahep; > + struct art_node *an; > + unsigned int i, j; > > - rw_assert_wrlock(&ar->ar_lock); > - KASSERT(plen >= 0 && plen <= ar->ar_alen); > + KASSERT(plen <= art->art_alen); > > - at = srp_get_locked(&ar->ar_root); > - if (at == NULL) > + heap = SMR_PTR_GET_LOCKED(&art->art_root); > + if (heap == NULL) > return (NULL); > > + at = art_heap_to_table(heap); > + > /* Default route */ > if (plen == 0) { > - node = srp_get_locked(&at->at_default); > - srp_swap_locked(&at->at_default, NULL); > - art_table_free(ar, at); > - return (node); > + ahep = &heap[ART_HEAP_IDX_DEFAULT]; > + > + ahe = SMR_PTR_GET_LOCKED(ahep); > + an = art_heap_entry_to_node(ahe); > + if (an == NULL) > + return (NULL); > + > + SMR_PTR_SET_LOCKED(ahep, 0); > + art_table_free(art, at); > + > + return (an); > } > > /* > @@ -466,53 +641,37 @@ art_delete(struct art_root *ar, struct a > * the stride length at this level the entry must > * be in the current table. > */ > - while (plen > (at->at_offset + at->at_bits)) { > + while ((p = at->at_offset + at->at_bits) < plen) { > /* Do a single level route lookup. */ > - j = art_findex(at, addr); > - node = srp_get_locked(&at->at_heap[j].node); > + j = art_bindex(at->at_offset, at->at_bits, addr, p); > + ahe = SMR_PTR_GET_LOCKED(&heap[j]); > > /* If this is a leaf, there is no route to delete. */ > - if (ISLEAF(node)) > + if (art_heap_entry_is_node(ahe)) > return (NULL); > > - at = SUBTABLE(node); > + heap = art_heap_entry_to_heap(ahe); > + at = art_heap_to_table(heap); > } > > - i = art_bindex(at, addr, plen); > - if (i == -1) > + i = art_bindex(at->at_offset, at->at_bits, addr, plen); > + ahep = &heap[i]; > + ahe = SMR_PTR_GET_LOCKED(ahep); > + if (!art_heap_entry_is_node(ahe)) { > + art_heap_entry *nheap = art_heap_entry_to_heap(ahe); > + ahep = &nheap[ART_HEAP_IDX_DEFAULT]; > + ahe = SMR_PTR_GET_LOCKED(ahep); > + } > + > + an = art_heap_entry_to_node(ahe); > + if (an == NULL) { > + /* No route to delete */ > return (NULL); > - > - return (art_table_delete(ar, at, i, an)); > -} > - > -/* > - * Single level deletion. > - */ > -struct art_node * > -art_table_delete(struct art_root *ar, struct art_table *at, int i, > - struct art_node *an) > -{ > - struct art_node *next, *node; > - > -#ifdef DIAGNOSTIC > - struct art_node *prev; > -#endif > - > - node = srp_get_locked(&at->at_heap[i].node); > -#ifdef DIAGNOSTIC > - if (!ISLEAF(node)) > - prev = srp_get_locked(&SUBTABLE(node)->at_default); > - else > - prev = node; > - > - KASSERT(prev == an); > -#endif > + } > > /* Get the next most specific route for the index `i'. */ > - if ((i >> 1) > 1) > - next = srp_get_locked(&at->at_heap[i >> 1].node); > - else > - next = NULL; > + j = i >> 1; > + pahe = (j > 1) ? SMR_PTR_GET_LOCKED(&heap[j]) : 0; > > /* > * If the index `i' of the route that we are removing is not > @@ -520,20 +679,18 @@ art_table_delete(struct art_root *ar, st > * route pointer to all the corresponding fringe indices. > */ > if (i < at->at_minfringe) > - art_allot(at, i, an, next); > - else if (!ISLEAF(node)) > - srp_swap_locked(&SUBTABLE(node)->at_default, next); > + art_allot(at, i, ahe, pahe); > else > - srp_swap_locked(&at->at_heap[i].node, next); > + SMR_PTR_SET_LOCKED(ahep, pahe); > > /* We have removed an entry from this table. */ > - art_table_free(ar, at); > + art_table_free(art, at); > > return (an); > } > > struct art_table * > -art_table_ref(struct art_root *ar, struct art_table *at) > +art_table_ref(struct art *art, struct art_table *at) > { > at->at_refcnt++; > return (at); > @@ -544,12 +701,11 @@ art_table_rele(struct art_table *at) > { > if (at == NULL) > return (0); > - > return (--at->at_refcnt == 0); > } > > int > -art_table_free(struct art_root *ar, struct art_table *at) > +art_table_free(struct art *art, struct art_table *at) > { > if (art_table_rele(at)) { > /* > @@ -557,7 +713,7 @@ art_table_free(struct art_root *ar, stru > * that are empty. > */ > do { > - at = art_table_put(ar, at); > + at = art_table_put(art, at); > } while (art_table_rele(at)); > > return (1); > @@ -569,116 +725,187 @@ art_table_free(struct art_root *ar, stru > /* > * Iteration API function. > */ > -int > -art_walk(struct art_root *ar, int (*f)(struct art_node *, void *), void *arg) > + > +static struct art_node * > +art_iter_descend(struct art_iter *ai, art_heap_entry *heap, > + art_heap_entry pahe) > { > - struct srp_ref sr; > - struct art_table *at; > - struct art_node *node; > - int error = 0; > + struct art_table *at; > + art_heap_entry ahe; > > - rw_enter_write(&ar->ar_lock); > - at = srp_get_locked(&ar->ar_root); > - if (at != NULL) { > - art_table_ref(ar, at); > + at = art_heap_to_table(heap); > + ai->ai_table = art_table_ref(ai->ai_art, at); > > - /* > - * The default route should be processed here because the root > - * table does not have a parent. > - */ > - node = srp_enter(&sr, &at->at_default); > - error = art_walk_apply(ar, node, NULL, f, arg); > - srp_leave(&sr); > + /* > + * Start looking at non-fringe nodes. > + */ > + ai->ai_j = 1; > + > + /* > + * The default route (index 1) is processed by the > + * parent table (where it belongs) otherwise it could > + * be processed more than once. > + */ > + ai->ai_i = 2; > > - if (error == 0) > - error = art_table_walk(ar, at, f, arg); > + /* > + * Process the default route now. > + */ > + ahe = SMR_PTR_GET_LOCKED(&heap[ART_HEAP_IDX_DEFAULT]); > + if (ahe != 0 && ahe != pahe) > + return (art_heap_entry_to_node(ahe)); > + > + /* > + * Tell the caller to proceed with art_iter_next. > + */ > + return (NULL); > +} > + > +struct art_node * > +art_iter_open(struct art *art, struct art_iter *ai) > +{ > + art_heap_entry *heap = SMR_PTR_GET(&art->art_root); > + struct art_node *an; > > - art_table_free(ar, at); > + ai->ai_art = art; > + > + if (heap == NULL) { > + /* empty, we're already done */ > + ai->ai_table = NULL; > + return (NULL); > } > - rw_exit_write(&ar->ar_lock); > > - return (error); > + an = art_iter_descend(ai, heap, 0); > + if (an != NULL) > + return (an); /* default route */ > + > + return (art_iter_next(ai)); > } > > -int > -art_table_walk(struct art_root *ar, struct art_table *at, > - int (*f)(struct art_node *, void *), void *arg) > +struct art_node * > +art_iter_next(struct art_iter *ai) > { > - struct srp_ref sr; > - struct art_node *node, *next; > - struct art_table *nat; > - int i, j, error = 0; > - uint32_t maxfringe = (at->at_minfringe << 1); > + struct art_table *at = ai->ai_table; > + art_heap_entry *heap = at->at_heap; > + art_heap_entry ahe, pahe; > + unsigned int i; > > +descend: > /* > * Iterate non-fringe nodes in ``natural'' order. > */ > - for (j = 1; j < at->at_minfringe; j += 2) { > - /* > - * The default route (index 1) is processed by the > - * parent table (where it belongs) otherwise it could > - * be processed more than once. > - */ > - for (i = max(j, 2); i < at->at_minfringe; i <<= 1) { > - next = srp_get_locked(&at->at_heap[i >> 1].node); > - > - node = srp_enter(&sr, &at->at_heap[i].node); > - error = art_walk_apply(ar, node, next, f, arg); > - srp_leave(&sr); > + if (ai->ai_j < at->at_minfringe) { > + for (;;) { > + while ((i = ai->ai_i) < at->at_minfringe) { > + ai->ai_i = i << 1; > + > + pahe = SMR_PTR_GET_LOCKED(&heap[i >> 1]); > + ahe = SMR_PTR_GET_LOCKED(&heap[i]); > + if (ahe != 0 && ahe != pahe) > + return (art_heap_entry_to_node(ahe)); > + } > > - if (error != 0) > - return (error); > + ai->ai_j += 2; > + if (ai->ai_j < at->at_minfringe) > + ai->ai_i = ai->ai_j; > + else { > + /* Set up the fringe loop */ > + ai->ai_i = at->at_minfringe; > + break; > + } > } > } > > /* > - * Iterate fringe nodes. > + * Descendent tables are only found on fringe nodes, and > + * they record where they were placed in their parent. This > + * allows the iterator to know where to resume traversal when > + * it ascends back to the parent table. By keeping the table > + * refs when going down the tree, the topolgy is preserved > + * even if all the nodes are removed. > */ > - for (i = at->at_minfringe; i < maxfringe; i++) { > - next = srp_get_locked(&at->at_heap[i >> 1].node); > > - node = srp_enter(&sr, &at->at_heap[i].node); > - if (!ISLEAF(node)) { > - nat = art_table_ref(ar, SUBTABLE(node)); > - node = srp_follow(&sr, &nat->at_default); > - } else > - nat = NULL; > + for (;;) { > + unsigned int maxfringe = at->at_minfringe << 1; > + struct art_table *parent; > > - error = art_walk_apply(ar, node, next, f, arg); > - srp_leave(&sr); > + /* > + * Iterate fringe nodes. > + */ > + while ((i = ai->ai_i) < maxfringe) { > + ai->ai_i = i + 1; > > - if (error != 0) { > - art_table_free(ar, nat); > - return (error); > + pahe = SMR_PTR_GET_LOCKED(&heap[i >> 1]); > + ahe = SMR_PTR_GET_LOCKED(&heap[i]); > + if (art_heap_entry_is_node(ahe)) { > + if (ahe != 0 && ahe != pahe) > + return (art_heap_entry_to_node(ahe)); > + } else { > + struct art_node *an; > + > + heap = art_heap_entry_to_heap(ahe); > + > + an = art_iter_descend(ai, heap, pahe); > + if (an != NULL) /* default route? */ > + return (an); > + > + /* Start looping over the child table */ > + at = art_heap_to_table(heap); > + goto descend; > + } > } > > - if (nat != NULL) { > - error = art_table_walk(ar, nat, f, arg); > - art_table_free(ar, nat); > - if (error != 0) > - return (error); > + /* > + * Ascend back up to the parent > + */ > + parent = at->at_parent; > + ai->ai_i = at->at_index + 1; > + art_table_free(ai->ai_art, at); > + > + ai->ai_table = parent; > + if (parent == NULL) { > + /* The root table has no parent */ > + break; > } > + > + at = parent; > + ai->ai_j = at->at_minfringe; > + heap = at->at_heap; > } > > - return (0); > + return (NULL); > } > > -int > -art_walk_apply(struct art_root *ar, > - struct art_node *an, struct art_node *next, > - int (*f)(struct art_node *, void *), void *arg) > +void > +art_iter_close(struct art_iter *ai) > { > - int error = 0; > + struct art_table *at, *parent; > > - if ((an != NULL) && (an != next)) { > - rw_exit_write(&ar->ar_lock); > - error = (*f)(an, arg); > - rw_enter_write(&ar->ar_lock); > + for (at = ai->ai_table; at != NULL; at = parent) { > + parent = at->at_parent; > + art_table_free(ai->ai_art, at); > } > > - return (error); > + ai->ai_table = NULL; > } > > +int > +art_walk(struct art *art, int (*f)(struct art_node *, void *), void *arg) > +{ > + struct art_iter ai; > + struct art_node *an; > + int error = 0; > + > + ART_FOREACH(an, art, &ai) { > + error = f(an, arg); > + if (error != 0) { > + art_iter_close(&ai); > + return (error); > + } > + } > + > + return (0); > +} > > /* > * Create a table and use the given index to set its default route. > @@ -686,89 +913,90 @@ art_walk_apply(struct art_root *ar, > * Note: This function does not modify the root or the parent. > */ > struct art_table * > -art_table_get(struct art_root *ar, struct art_table *parent, int j) > +art_table_get(struct art *art, struct art_table *parent, unsigned int j) > { > struct art_table *at; > - struct art_node *node; > - void *at_heap; > - uint32_t lvl; > + art_heap_entry *heap; > + unsigned int level; > + unsigned int bits; > > - KASSERT(j != 0 && j != 1); > + KASSERT(j != ART_HEAP_IDX_TABLE && j != ART_HEAP_IDX_DEFAULT); > KASSERT(parent != NULL || j == -1); > > - if (parent != NULL) > - lvl = parent->at_level + 1; > - else > - lvl = 0; > - > - KASSERT(lvl < ar->ar_nlvl); > + level = (parent != NULL) ? parent->at_level + 1 : 0; > + KASSERT(level < art->art_nlevels); > > at = pool_get(&at_pool, PR_NOWAIT|PR_ZERO); > if (at == NULL) > return (NULL); > > - switch (AT_HEAPSIZE(ar->ar_bits[lvl])) { > - case AT_HEAPSIZE(4): > - at_heap = pool_get(&at_heap_4_pool, PR_NOWAIT|PR_ZERO); > + bits = art->art_levels[level]; > + switch (bits) { > + case 4: > + heap = pool_get(&at_heap_4_pool, PR_NOWAIT|PR_ZERO); > break; > - case AT_HEAPSIZE(8): > - at_heap = pool_get(&at_heap_8_pool, PR_NOWAIT|PR_ZERO); > + case 8: > + heap = pool_get(&at_heap_8_pool, PR_NOWAIT|PR_ZERO); > break; > default: > - panic("incorrect stride length %u", ar->ar_bits[lvl]); > + panic("incorrect stride length %u", bits); > } > > - if (at_heap == NULL) { > + if (heap == NULL) { > pool_put(&at_pool, at); > return (NULL); > } > > + heap[ART_HEAP_IDX_TABLE] = (art_heap_entry)at; > + > at->at_parent = parent; > at->at_index = j; > - at->at_minfringe = (1 << ar->ar_bits[lvl]); > - at->at_level = lvl; > - at->at_bits = ar->ar_bits[lvl]; > - at->at_heap = at_heap; > + at->at_minfringe = (1 << bits); > + at->at_level = level; > + at->at_bits = bits; > + at->at_heap = heap; > at->at_refcnt = 0; > > if (parent != NULL) { > - node = srp_get_locked(&parent->at_heap[j].node); > - /* node isn't being deleted, no srp_finalize needed */ > - srp_swap_locked(&at->at_default, node); > + art_heap_entry ahe; > + > at->at_offset = (parent->at_offset + parent->at_bits); > + > + ahe = SMR_PTR_GET_LOCKED(&parent->at_heap[j]); > + SMR_PTR_SET_LOCKED(&heap[ART_HEAP_IDX_DEFAULT], ahe); > } > > return (at); > } > > - > /* > * Delete a table and use its index to restore its parent's default route. > * > * Note: Modify its parent to unlink the table from it. > */ > struct art_table * > -art_table_put(struct art_root *ar, struct art_table *at) > +art_table_put(struct art *art, struct art_table *at) > { > struct art_table *parent = at->at_parent; > - struct art_node *node; > - uint32_t j = at->at_index; > + unsigned int j = at->at_index; > > KASSERT(at->at_refcnt == 0); > KASSERT(j != 0 && j != 1); > > if (parent != NULL) { > + art_heap_entry ahe; > + > KASSERT(j != -1); > KASSERT(at->at_level == parent->at_level + 1); > KASSERT(parent->at_refcnt >= 1); > > /* Give the route back to its parent. */ > - node = srp_get_locked(&at->at_default); > - srp_swap_locked(&parent->at_heap[j].node, node); > + ahe = SMR_PTR_GET_LOCKED(&at->at_heap[ART_HEAP_IDX_DEFAULT]); > + SMR_PTR_SET_LOCKED(&parent->at_heap[j], ahe); > } else { > KASSERT(j == -1); > KASSERT(at->at_level == 0); > - srp_swap_locked(&ar->ar_root, NULL); > + SMR_PTR_SET_LOCKED(&art->art_root, NULL); > } > > mtx_enter(&art_table_gc_mtx); > @@ -791,19 +1019,16 @@ art_table_gc(void *null) > art_table_gc_list = NULL; > mtx_leave(&art_table_gc_mtx); > > + smr_barrier(); > + > while (at != NULL) { > next = at->at_parent; > > - if (at->at_level == 0) > - srp_finalize(at, "arttfini"); > - else > - srp_finalize(ASNODE(at), "arttfini"); > - > - switch (AT_HEAPSIZE(at->at_bits)) { > - case AT_HEAPSIZE(4): > + switch (at->at_bits) { > + case 4: > pool_put(&at_heap_4_pool, at->at_heap); > break; > - case AT_HEAPSIZE(8): > + case 8: > pool_put(&at_heap_8_pool, at->at_heap); > break; > default: > @@ -839,40 +1064,45 @@ art_table_gc(void *null) > * art_allot(at, k, old, new); > * } > */ > -void > -art_allot(struct art_table *at, int i, struct art_node *old, > - struct art_node *new) > -{ > - struct art_node *node, *dflt; > - int k = i; > +static void > +art_allot(struct art_table *at, unsigned int i, > + art_heap_entry oahe, art_heap_entry nahe) > +{ > + art_heap_entry ahe, *ahep; > + art_heap_entry *heap; > + unsigned int k = i; > > KASSERT(i < at->at_minfringe); > > + heap = at->at_heap; > + > again: > k <<= 1; > if (k < at->at_minfringe) > goto nonfringe; > > /* Change fringe nodes. */ > - while (1) { > - node = srp_get_locked(&at->at_heap[k].node); > - if (!ISLEAF(node)) { > - dflt = srp_get_locked(&SUBTABLE(node)->at_default); > - if (dflt == old) { > - srp_swap_locked(&SUBTABLE(node)->at_default, > - new); > - } > - } else if (node == old) { > - srp_swap_locked(&at->at_heap[k].node, new); > + for (;;) { > + ahep = &heap[k]; > + ahe = SMR_PTR_GET_LOCKED(ahep); > + > + if (!art_heap_entry_is_node(ahe)) { > + art_heap_entry *child = art_heap_entry_to_heap(ahe); > + ahep = &child[ART_HEAP_IDX_DEFAULT]; > + ahe = SMR_PTR_GET_LOCKED(ahep); > } > + > + if (ahe == oahe) > + SMR_PTR_SET_LOCKED(ahep, nahe); > + > if (k % 2) > goto moveup; > k++; > } > > nonfringe: > - node = srp_get_locked(&at->at_heap[k].node); > - if (node == old) > + ahe = SMR_PTR_GET_LOCKED(&heap[k]); > + if (ahe == oahe) > goto again; > moveon: > if (k % 2) > @@ -881,7 +1111,7 @@ moveon: > goto nonfringe; > moveup: > k >>= 1; > - srp_swap_locked(&at->at_heap[k].node, new); > + SMR_PTR_SET_LOCKED(&heap[k], nahe); > > /* Change non-fringe node. */ > if (k != i) > @@ -889,7 +1119,7 @@ moveup: > } > > struct art_node * > -art_get(uint8_t plen) > +art_get(const uint8_t *addr, unsigned int plen) > { > struct art_node *an; > > @@ -897,17 +1127,25 @@ art_get(uint8_t plen) > if (an == NULL) > return (NULL); > > - an->an_plen = plen; > - SRPL_INIT(&an->an_rtlist); > + art_node_init(an, addr, plen); > > return (an); > } > > void > -art_put(struct art_node *an) > +art_node_init(struct art_node *an, const uint8_t *addr, unsigned int plen) > { > - KASSERT(SRPL_EMPTY_LOCKED(&an->an_rtlist)); > + size_t len; > + > + len = roundup(plen, 8) / 8; > + KASSERT(len <= sizeof(an->an_addr)); > + memcpy(an->an_addr, addr, len); > + an->an_plen = plen; > +} > > +void > +art_put(struct art_node *an) > +{ > mtx_enter(&art_node_gc_mtx); > an->an_gc = art_node_gc_list; > art_node_gc_list = an; > @@ -919,17 +1157,17 @@ art_put(struct art_node *an) > void > art_gc(void *null) > { > - struct art_node *an, *next; > + struct art_node *an; > > mtx_enter(&art_node_gc_mtx); > an = art_node_gc_list; > art_node_gc_list = NULL; > mtx_leave(&art_node_gc_mtx); > > - while (an != NULL) { > - next = an->an_gc; > + smr_barrier(); > > - srp_finalize(an, "artnfini"); > + while (an != NULL) { > + struct art_node *next = an->an_gc; > > pool_put(&an_pool, an); > > Index: art.h > =================================================================== > RCS file: /cvs/src/sys/net/art.h,v > diff -u -p -r1.25 art.h > --- art.h 11 Nov 2023 12:17:50 -0000 1.25 > +++ art.h 13 Jun 2025 06:40:59 -0000 > @@ -19,94 +19,90 @@ > #ifndef _NET_ART_H_ > #define _NET_ART_H_ > > -#include > -#include > - > -#define ART_MAXLVL 32 /* We currently use 32 levels for IPv6. */ > - > /* > - * Root of the ART tables, equivalent to the radix head. > + * Allotment Routing Table (ART) > + * > + * Yoichi Hariguchi paper can be found at: > + * http://www.hariguchi.org/art/art.pdf > + * > + * Locking: > + * > + * Modification (ie, art_insert or art_delete) and iteration > + * (art_iter_next, etc) over the ART must be serialised by the caller. > + * Lookups (ie, art_match and art_lookup) run within an SMR critical > + * section. > * > - * Locks used to protect struct members in this file: > - * I immutable after creation > - * l root's `ar_lock' > - * K kernel lock > - * For SRP related structures that allow lock-free reads, the write lock > - * is indicated below. > + * Iteration requires serialisation as it manipulates the reference > + * counts on tables as it traverses the tree. The iterator maintains > + * these references until it runs out of entries. This allows code > + * iterating over the ART to release locks in between calls to > + * art_iter_open and art_iter_next. The references may be dropped > + * early with art_iter_close. > + * > + * Note, the iterator does not hold a reference to the art_node > + * structure or the data hanging off the an_value pointer, they must > + * be accounted for separately or their use must be serialised with > + * art_delete. > */ > -struct art_root { > - struct srp ar_root; /* [l] First table */ > - struct rwlock ar_lock; /* [] Serialise modifications */ > - uint8_t ar_bits[ART_MAXLVL]; /* [I] Per level stride */ > - uint8_t ar_nlvl; /* [I] Number of levels */ > - uint8_t ar_alen; /* [I] Address length in bits */ > - uint8_t ar_off; /* [I] Offset of key in bytes */ > - struct sockaddr *ar_source; /* [N] use optional src addr */ > -}; > > -#define ISLEAF(e) (((unsigned long)(e) & 1) == 0) > -#define SUBTABLE(e) ((struct art_table *)((unsigned long)(e) & ~1)) > -#define ASNODE(t) ((struct art_node *)((unsigned long)(t) | 1)) > +typedef uintptr_t art_heap_entry; > > /* > - * Allotment Table. > + * Root of the ART, equivalent to the radix head. > */ > -struct art_table { > - struct art_table *at_parent; /* Parent table */ > - uint32_t at_index; /* Index in the parent table */ > - uint32_t at_minfringe; /* Index that fringe begins */ > - uint32_t at_level; /* Level of the table */ > - uint8_t at_bits; /* Stride length of the table */ > - uint8_t at_offset; /* Sum of parents' stride len */ > - > - /* > - * Items stored in the heap are pointers to nodes, in the leaf > - * case, or tables otherwise. One exception is index 0 which > - * is a route counter. > - */ > - union { > - struct srp node; > - unsigned long count; > - } *at_heap; /* Array of 2^(slen+1) items */ > -}; > -#define at_refcnt at_heap[0].count/* Refcounter (1 per different route) */ > -#define at_default at_heap[1].node /* Default route (was in parent heap) */ > - > -/* Heap size for an ART table of stride length ``slen''. */ > -#define AT_HEAPSIZE(slen) ((1 << ((slen) + 1)) * sizeof(void *)) > > -/* > - * Forward declaration needed for the list of mpath routes > - * attached to a single ART node. > - */ > -struct rtentry; > +struct art { > + art_heap_entry *art_root; > + const unsigned int *art_levels; > + unsigned int art_nlevels; > + unsigned int art_alen; > +}; > > /* > * A node is the internal representation of a route entry. > */ > struct art_node { > + void *an_value; > union { > - SRPL_HEAD(, rtentry) an__rtlist; /* Route related to this node */ > - struct art_node *an__gc; /* Entry on GC list */ > - } an_pointer; > - uint8_t an_plen; /* Prefix length */ > + struct art_node *an__gc; > + uint8_t an__addr[16]; > + } an__u; > +#define an_gc an__u.an__gc > +#define an_addr an__u.an__addr > + unsigned int an_plen; > }; > -#define an_rtlist an_pointer.an__rtlist > -#define an_gc an_pointer.an__gc > - > -void art_init(void); > -struct art_root *art_alloc(unsigned int, unsigned int, unsigned int); > -struct art_node *art_insert(struct art_root *, struct art_node *, const void *, > - int); > -struct art_node *art_delete(struct art_root *, struct art_node *, const void *, > - int); > -struct art_node *art_match(struct art_root *, const void *, struct srp_ref *); > -struct art_node *art_lookup(struct art_root *, const void *, int, > - struct srp_ref *); > -int art_walk(struct art_root *, > - int (*)(struct art_node *, void *), void *); > > -struct art_node *art_get(uint8_t); > +void art_boot(void); > +struct art *art_alloc(unsigned int); > +void art_init(struct art *, unsigned int); > +struct art_node *art_insert(struct art *, struct art_node *); > +struct art_node *art_delete(struct art *, const void *, unsigned int); > +struct art_node *art_match(struct art *, const void *); > +struct art_node *art_lookup(struct art *, const void *, unsigned int); > +int art_is_empty(struct art *); > + > +struct art_node *art_get(const uint8_t *, unsigned int); > +void art_node_init(struct art_node *, > + const uint8_t *, unsigned int); > void art_put(struct art_node *); > + > +struct art_iter { > + struct art *ai_art; > + struct art_table *ai_table; > + unsigned int ai_j; > + unsigned int ai_i; > +}; > + > +struct art_node *art_iter_open(struct art *, struct art_iter *); > +struct art_node *art_iter_next(struct art_iter *); > +void art_iter_close(struct art_iter *); > + > +#define ART_FOREACH(_an, _art, _ai) \ > + for ((_an) = art_iter_open((_art), (_ai)); \ > + (_an) != NULL; \ > + (_an) = art_iter_next((_ai))) > + > +int art_walk(struct art *, > + int (*)(struct art_node *, void *), void *); > > #endif /* _NET_ART_H_ */ > Index: if_tun.c > =================================================================== > RCS file: /cvs/src/sys/net/if_tun.c,v > diff -u -p -r1.251 if_tun.c > --- if_tun.c 2 Mar 2025 21:28:32 -0000 1.251 > +++ if_tun.c 13 Jun 2025 06:40:59 -0000 > @@ -318,8 +318,6 @@ tun_clone_destroy(struct ifnet *ifp) > > if (vfinddev(dev, VCHR, &vp)) > VOP_REVOKE(vp, REVOKEALL); > - > - KASSERT(sc->sc_dev == 0); > } > > /* prevent userland from getting to the device again */ > Index: if_wg.c > =================================================================== > RCS file: /cvs/src/sys/net/if_wg.c,v > diff -u -p -r1.42 if_wg.c > --- if_wg.c 17 Apr 2025 12:42:50 -0000 1.42 > +++ if_wg.c 13 Jun 2025 06:40:59 -0000 > @@ -31,6 +31,7 @@ > #include > #include > #include > +#include > > #include > #include > @@ -251,10 +252,11 @@ struct wg_softc { > struct socket *sc_so6; > #endif > > + struct rwlock sc_aip_lock; > size_t sc_aip_num; > - struct art_root *sc_aip4; > + struct art *sc_aip4; > #ifdef INET6 > - struct art_root *sc_aip6; > + struct art *sc_aip6; > #endif > > struct rwlock sc_peer_lock; > @@ -290,7 +292,7 @@ void wg_peer_counters_add(struct wg_peer > > int wg_aip_add(struct wg_softc *, struct wg_peer *, struct wg_aip_io *); > struct wg_peer * > - wg_aip_lookup(struct art_root *, void *); > + wg_aip_lookup(struct art *, void *); > int wg_aip_remove(struct wg_softc *, struct wg_peer *, > struct wg_aip_io *); > > @@ -609,7 +611,7 @@ wg_peer_counters_add(struct wg_peer *pee > int > wg_aip_add(struct wg_softc *sc, struct wg_peer *peer, struct wg_aip_io *d) > { > - struct art_root *root; > + struct art *root; > struct art_node *node; > struct wg_aip *aip; > int ret = 0; > @@ -625,8 +627,10 @@ wg_aip_add(struct wg_softc *sc, struct w > if ((aip = pool_get(&wg_aip_pool, PR_NOWAIT|PR_ZERO)) == NULL) > return ENOBUFS; > > - rw_enter_write(&root->ar_lock); > - node = art_insert(root, &aip->a_node, &d->a_addr, d->a_cidr); > + art_node_init(&aip->a_node, &d->a_addr.addr_bytes, d->a_cidr); > + > + rw_enter_write(&sc->sc_aip_lock); > + node = art_insert(root, &aip->a_node); > > if (node == &aip->a_node) { > aip->a_peer = peer; > @@ -642,18 +646,18 @@ wg_aip_add(struct wg_softc *sc, struct w > aip->a_peer = peer; > } > } > - rw_exit_write(&root->ar_lock); > + rw_exit_write(&sc->sc_aip_lock); > return ret; > } > > struct wg_peer * > -wg_aip_lookup(struct art_root *root, void *addr) > +wg_aip_lookup(struct art *root, void *addr) > { > - struct srp_ref sr; > struct art_node *node; > > - node = art_match(root, addr, &sr); > - srp_leave(&sr); > + smr_read_enter(); > + node = art_match(root, addr); > + smr_read_leave(); > > return node == NULL ? NULL : ((struct wg_aip *) node)->a_peer; > } > @@ -661,8 +665,7 @@ wg_aip_lookup(struct art_root *root, voi > int > wg_aip_remove(struct wg_softc *sc, struct wg_peer *peer, struct wg_aip_io *d) > { > - struct srp_ref sr; > - struct art_root *root; > + struct art *root; > struct art_node *node; > struct wg_aip *aip; > int ret = 0; > @@ -675,23 +678,21 @@ wg_aip_remove(struct wg_softc *sc, struc > default: return EAFNOSUPPORT; > } > > - rw_enter_write(&root->ar_lock); > - if ((node = art_lookup(root, &d->a_addr, d->a_cidr, &sr)) == NULL) { > + rw_enter_write(&sc->sc_aip_lock); > + if ((node = art_lookup(root, &d->a_addr, d->a_cidr)) == NULL) { > ret = ENOENT; > } else if (((struct wg_aip *) node)->a_peer != peer) { > ret = EXDEV; > } else { > aip = (struct wg_aip *)node; > - if (art_delete(root, node, &d->a_addr, d->a_cidr) == NULL) > + if (art_delete(root, &d->a_addr, d->a_cidr) == NULL) > panic("art_delete failed to delete node %p", node); > > sc->sc_aip_num--; > LIST_REMOVE(aip, a_entry); > pool_put(&wg_aip_pool, aip); > } > - > - srp_leave(&sr); > - rw_exit_write(&root->ar_lock); > + rw_exit_write(&sc->sc_aip_lock); > return ret; > } > > @@ -2726,10 +2727,11 @@ wg_clone_create(struct if_clone *ifc, in > #endif > > sc->sc_aip_num = 0; > - if ((sc->sc_aip4 = art_alloc(0, 32, 0)) == NULL) > + rw_init(&sc->sc_aip_lock, "wgaip"); > + if ((sc->sc_aip4 = art_alloc(32)) == NULL) > goto ret_02; > #ifdef INET6 > - if ((sc->sc_aip6 = art_alloc(0, 128, 0)) == NULL) > + if ((sc->sc_aip6 = art_alloc(128)) == NULL) > goto ret_03; > #endif > > Index: if_wg.h > =================================================================== > RCS file: /cvs/src/sys/net/if_wg.h,v > diff -u -p -r1.6 if_wg.h > --- if_wg.h 13 Oct 2024 00:53:21 -0000 1.6 > +++ if_wg.h 13 Jun 2025 06:40:59 -0000 > @@ -46,6 +46,7 @@ struct wg_aip_io { > sa_family_t a_af; > int a_cidr; > union wg_aip_addr { > + uint8_t addr_bytes; > struct in_addr addr_ipv4; > struct in6_addr addr_ipv6; > } a_addr; > Index: route.h > =================================================================== > RCS file: /cvs/src/sys/net/route.h,v > diff -u -p -r1.216 route.h > --- route.h 16 Mar 2025 21:58:08 -0000 1.216 > +++ route.h 13 Jun 2025 06:40:59 -0000 > @@ -40,7 +40,7 @@ > * I immutable after creation > * N net lock > * X exclusive net lock, or shared net lock + kernel lock > - * R art (rtable) lock > + * R rtable lock > * r per route entry mutex rt_mtx > * L arp/nd6/etc lock for updates, net lock for reads > * T rttimer_mtx route timer lists > @@ -117,7 +117,7 @@ struct rttimer; > > struct rtentry { > struct sockaddr *rt_dest; /* [I] destination */ > - SRPL_ENTRY(rtentry) rt_next; /* [R] next mpath entry to our dst */ > + struct rtentry *rt_next; /* [R] next mpath entry to our dst */ > struct sockaddr *rt_gateway; /* [X] gateway address */ > struct ifaddr *rt_ifa; /* [N] interface addr to use */ > caddr_t rt_llinfo; /* [L] pointer to link level info or > Index: rtable.c > =================================================================== > RCS file: /cvs/src/sys/net/rtable.c,v > diff -u -p -r1.87 rtable.c > --- rtable.c 9 Apr 2024 12:53:08 -0000 1.87 > +++ rtable.c 13 Jun 2025 06:40:59 -0000 > @@ -26,12 +26,21 @@ > #include > #include > #include > +#include > #endif > > #include > #include > #include > > +struct rtable { > + struct rwlock r_lock; > + struct art *r_art; /* [I] */ > + unsigned int r_off; /* [I] Offset of key in bytes */ > + > + struct sockaddr *r_source; /* [N] use optional src addr */ > +}; > + > /* > * Structures used by rtable_get() to retrieve the corresponding > * routing table for a given pair of ``af'' and ``rtableid''. > @@ -85,8 +94,8 @@ void rtmap_dtor(void *, void *); > struct srp_gc rtmap_gc = SRP_GC_INITIALIZER(rtmap_dtor, NULL); > > void rtable_init_backend(void); > -void *rtable_alloc(unsigned int, unsigned int, unsigned int); > -void *rtable_get(unsigned int, sa_family_t); > +struct rtable *rtable_alloc(unsigned int, unsigned int, unsigned int); > +struct rtable *rtable_get(unsigned int, sa_family_t); > > void > rtmap_init(void) > @@ -193,7 +202,7 @@ int > rtable_add(unsigned int id) > { > const struct domain *dp; > - void *tbl; > + struct rtable *tbl; > struct rtmap *map; > struct dommp *dmm; > sa_family_t af; > @@ -244,11 +253,11 @@ out: > return (error); > } > > -void * > +struct rtable * > rtable_get(unsigned int rtableid, sa_family_t af) > { > struct rtmap *map; > - void *tbl = NULL; > + struct rtable *tbl = NULL; > struct srp_ref sr; > > if (af >= nitems(af2idx) || af2idx[af] == 0) > @@ -286,7 +295,7 @@ rtable_empty(unsigned int rtableid) > { > const struct domain *dp; > int i; > - struct art_root *tbl; > + struct rtable *tbl; > > for (i = 0; (dp = domains[i]) != NULL; i++) { > if (dp->dom_rtoffset == 0) > @@ -295,7 +304,7 @@ rtable_empty(unsigned int rtableid) > tbl = rtable_get(rtableid, dp->dom_family); > if (tbl == NULL) > continue; > - if (tbl->ar_root.ref != NULL) > + if (!art_is_empty(tbl->r_art)) > return (0); > } > > @@ -350,40 +359,51 @@ rtable_l2set(unsigned int rtableid, unsi > } > > > -static inline const uint8_t *satoaddr(struct art_root *, > +static inline const uint8_t *satoaddr(struct rtable *, > const struct sockaddr *); > > -int an_match(struct art_node *, const struct sockaddr *, int); > -void rtentry_ref(void *, void *); > -void rtentry_unref(void *, void *); > - > void rtable_mpath_insert(struct art_node *, struct rtentry *); > > -struct srpl_rc rt_rc = SRPL_RC_INITIALIZER(rtentry_ref, rtentry_unref, NULL); > - > void > rtable_init_backend(void) > { > - art_init(); > + art_boot(); > } > > -void * > +struct rtable * > rtable_alloc(unsigned int rtableid, unsigned int alen, unsigned int off) > { > - return (art_alloc(rtableid, alen, off)); > + struct rtable *r; > + > + r = malloc(sizeof(*r), M_RTABLE, M_NOWAIT|M_ZERO); > + if (r == NULL) > + return (r); > + > + > + r->r_art = art_alloc(alen); > + if (r->r_art == NULL) { > + free(r, M_RTABLE, sizeof(*r)); > + return (NULL); > + } > + > + rw_init(&r->r_lock, "rtable"); > + r->r_off = off; > + r->r_source = NULL; > + > + return (r); > } > > int > rtable_setsource(unsigned int rtableid, int af, struct sockaddr *src) > { > - struct art_root *ar; > + struct rtable *r; > > NET_ASSERT_LOCKED_EXCLUSIVE(); > > - if ((ar = rtable_get(rtableid, af)) == NULL) > + if ((r = rtable_get(rtableid, af)) == NULL) > return (EAFNOSUPPORT); > > - ar->ar_source = src; > + r->r_source = src; > > return (0); > } > @@ -391,15 +411,15 @@ rtable_setsource(unsigned int rtableid, > struct sockaddr * > rtable_getsource(unsigned int rtableid, int af) > { > - struct art_root *ar; > + struct rtable *r; > > NET_ASSERT_LOCKED(); > > - ar = rtable_get(rtableid, af); > - if (ar == NULL) > + r = rtable_get(rtableid, af); > + if (r == NULL) > return (NULL); > > - return (ar->ar_source); > + return (r->r_source); > } > > void > @@ -419,37 +439,34 @@ struct rtentry * > rtable_lookup(unsigned int rtableid, const struct sockaddr *dst, > const struct sockaddr *mask, const struct sockaddr *gateway, uint8_t prio) > { > - struct art_root *ar; > + struct rtable *r; > struct art_node *an; > struct rtentry *rt = NULL; > - struct srp_ref sr, nsr; > const uint8_t *addr; > int plen; > > - ar = rtable_get(rtableid, dst->sa_family); > - if (ar == NULL) > + r = rtable_get(rtableid, dst->sa_family); > + if (r == NULL) > return (NULL); > > - addr = satoaddr(ar, dst); > + addr = satoaddr(r, dst); > > - /* No need for a perfect match. */ > + smr_read_enter(); > if (mask == NULL) { > - an = art_match(ar, addr, &nsr); > - if (an == NULL) > - goto out; > + /* No need for a perfect match. */ > + an = art_match(r->r_art, addr); > } else { > plen = rtable_satoplen(dst->sa_family, mask); > if (plen == -1) > return (NULL); > > - an = art_lookup(ar, addr, plen, &nsr); > - > - /* Make sure we've got a perfect match. */ > - if (!an_match(an, dst, plen)) > - goto out; > + an = art_lookup(r->r_art, addr, plen); > } > + if (an == NULL) > + goto out; > > - SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) { > + for (rt = SMR_PTR_GET(&an->an_value); rt != NULL; > + rt = SMR_PTR_GET(&rt->rt_next)) { > if (prio != RTP_ANY && > (rt->rt_priority & RTP_MASK) != (prio & RTP_MASK)) > continue; > @@ -464,9 +481,8 @@ rtable_lookup(unsigned int rtableid, con > if (rt != NULL) > rtref(rt); > > - SRPL_LEAVE(&sr); > out: > - srp_leave(&nsr); > + smr_read_leave(); > > return (rt); > } > @@ -474,44 +490,41 @@ out: > struct rtentry * > rtable_match(unsigned int rtableid, const struct sockaddr *dst, uint32_t *src) > { > - struct art_root *ar; > + struct rtable *r; > struct art_node *an; > struct rtentry *rt = NULL; > - struct srp_ref sr, nsr; > const uint8_t *addr; > int hash; > + uint8_t prio; > > - ar = rtable_get(rtableid, dst->sa_family); > - if (ar == NULL) > + r = rtable_get(rtableid, dst->sa_family); > + if (r == NULL) > return (NULL); > > - addr = satoaddr(ar, dst); > + addr = satoaddr(r, dst); > > - an = art_match(ar, addr, &nsr); > + smr_read_enter(); > + an = art_match(r->r_art, addr); > if (an == NULL) > goto out; > > - rt = SRPL_FIRST(&sr, &an->an_rtlist); > - if (rt == NULL) { > - SRPL_LEAVE(&sr); > - goto out; > - } > - rtref(rt); > - SRPL_LEAVE(&sr); > + rt = SMR_PTR_GET(&an->an_value); > + KASSERT(rt != NULL); > + prio = rt->rt_priority; > > /* Gateway selection by Hash-Threshold (RFC 2992) */ > if ((hash = rt_hash(rt, dst, src)) != -1) { > struct rtentry *mrt; > - int threshold, npaths = 0; > + int threshold, npaths = 1; > > KASSERT(hash <= 0xffff); > > - SRPL_FOREACH(mrt, &sr, &an->an_rtlist, rt_next) { > - /* Only count nexthops with the same priority. */ > - if (mrt->rt_priority == rt->rt_priority) > + /* Only count nexthops with the same priority. */ > + mrt = rt; > + while ((mrt = SMR_PTR_GET(&mrt->rt_next)) != NULL) { > + if (mrt->rt_priority == prio) > npaths++; > } > - SRPL_LEAVE(&sr); > > threshold = (0xffff / npaths) + 1; > > @@ -520,27 +533,22 @@ rtable_match(unsigned int rtableid, cons > * route list attached to the node, so we won't necessarily > * have the same number of routes. for most modifications, > * we'll pick a route that we wouldn't have if we only saw the > - * list before or after the change. if we were going to use > - * the last available route, but it got removed, we'll hit > - * the end of the list and then pick the first route. > + * list before or after the change. > */ > - > - mrt = SRPL_FIRST(&sr, &an->an_rtlist); > - while (hash > threshold && mrt != NULL) { > - if (mrt->rt_priority == rt->rt_priority) > + mrt = rt; > + while (hash > threshold) { > + if (mrt->rt_priority == prio) { > + rt = mrt; > hash -= threshold; > - mrt = SRPL_FOLLOW(&sr, mrt, rt_next); > - } > - > - if (mrt != NULL) { > - rtref(mrt); > - rtfree(rt); > - rt = mrt; > + } > + mrt = SMR_PTR_GET(&mrt->rt_next); > + if (mrt == NULL) > + break; > } > - SRPL_LEAVE(&sr); > } > + rtref(rt); > out: > - srp_leave(&nsr); > + smr_read_leave(); > return (rt); > } > > @@ -549,35 +557,59 @@ rtable_insert(unsigned int rtableid, str > const struct sockaddr *mask, const struct sockaddr *gateway, uint8_t prio, > struct rtentry *rt) > { > - struct rtentry *mrt; > - struct srp_ref sr; > - struct art_root *ar; > + struct rtable *r; > struct art_node *an, *prev; > const uint8_t *addr; > int plen; > unsigned int rt_flags; > int error = 0; > > - ar = rtable_get(rtableid, dst->sa_family); > - if (ar == NULL) > + r = rtable_get(rtableid, dst->sa_family); > + if (r == NULL) > return (EAFNOSUPPORT); > > - addr = satoaddr(ar, dst); > + addr = satoaddr(r, dst); > plen = rtable_satoplen(dst->sa_family, mask); > if (plen == -1) > return (EINVAL); > > - rtref(rt); /* guarantee rtfree won't do anything during insert */ > - rw_enter_write(&ar->ar_lock); > + an = art_get(addr, plen); > + if (an == NULL) > + return (ENOMEM); > > - /* Do not permit exactly the same dst/mask/gw pair. */ > - an = art_lookup(ar, addr, plen, &sr); > - srp_leave(&sr); /* an can't go away while we have the lock */ > - if (an_match(an, dst, plen)) { > - struct rtentry *mrt; > - int mpathok = ISSET(rt->rt_flags, RTF_MPATH); > + /* prepare for immediate operation if insert succeeds */ > + rt_flags = rt->rt_flags; > + rt->rt_flags &= ~RTF_MPATH; > + rt->rt_dest = dst; > + rt->rt_plen = plen; > + rt->rt_next = NULL; > > - SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) { > + rtref(rt); /* take a ref for the table */ > + an->an_value = rt; > + > + rw_enter_write(&r->r_lock); > + prev = art_insert(r->r_art, an); > + if (prev == NULL) { > + error = ENOMEM; > + goto put; > + } > + > + if (prev != an) { > + struct rtentry *mrt; > + int mpathok = ISSET(rt_flags, RTF_MPATH); > + int mpath = 0; > + > + /* > + * An ART node with the same destination/netmask already > + * exists. > + */ > + art_put(an); > + an = prev; > + > + /* Do not permit exactly the same dst/mask/gw pair. */ > + for (mrt = SMR_PTR_GET_LOCKED(&an->an_value); > + mrt != NULL; > + mrt = SMR_PTR_GET_LOCKED(&mrt->rt_next)) { > if (prio != RTP_ANY && > (mrt->rt_priority & RTP_MASK) != (prio & RTP_MASK)) > continue; > @@ -589,63 +621,34 @@ rtable_insert(unsigned int rtableid, str > error = EEXIST; > goto leave; > } > + mpath = RTF_MPATH; > } > - } > > - an = art_get(plen); > - if (an == NULL) { > - error = ENOBUFS; > - goto leave; > - } > - > - /* prepare for immediate operation if insert succeeds */ > - rt_flags = rt->rt_flags; > - rt->rt_flags &= ~RTF_MPATH; > - rt->rt_dest = dst; > - rt->rt_plen = plen; > - SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); > - > - prev = art_insert(ar, an, addr, plen); > - if (prev != an) { > - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, > - rt_next); > - rt->rt_flags = rt_flags; > - art_put(an); > + /* The new route can be added to the list. */ > + if (mpath) { > + SET(rt->rt_flags, RTF_MPATH); > + > + for (mrt = SMR_PTR_GET_LOCKED(&an->an_value); > + mrt != NULL; > + mrt = SMR_PTR_GET_LOCKED(&mrt->rt_next)) { > + if ((mrt->rt_priority & RTP_MASK) != > + (prio & RTP_MASK)) > + continue; > > - if (prev == NULL) { > - error = ESRCH; > - goto leave; > - } > - > - an = prev; > - > - mrt = SRPL_FIRST_LOCKED(&an->an_rtlist); > - KASSERT(mrt != NULL); > - KASSERT((rt->rt_flags & RTF_MPATH) || mrt->rt_priority != prio); > - > - /* > - * An ART node with the same destination/netmask already > - * exists, MPATH conflict must have been already checked. > - */ > - if (rt->rt_flags & RTF_MPATH) { > - /* > - * Only keep the RTF_MPATH flag if two routes have > - * the same gateway. > - */ > - rt->rt_flags &= ~RTF_MPATH; > - SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) { > - if (mrt->rt_priority == prio) { > - mrt->rt_flags |= RTF_MPATH; > - rt->rt_flags |= RTF_MPATH; > - } > + SET(mrt->rt_flags, RTF_MPATH); > } > } > > /* Put newly inserted entry at the right place. */ > rtable_mpath_insert(an, rt); > } > + rw_exit_write(&r->r_lock); > + return (error); > + > +put: > + art_put(an); > leave: > - rw_exit_write(&ar->ar_lock); > + rw_exit_write(&r->r_lock); > rtfree(rt); > return (error); > } > @@ -654,118 +657,136 @@ int > rtable_delete(unsigned int rtableid, const struct sockaddr *dst, > const struct sockaddr *mask, struct rtentry *rt) > { > - struct art_root *ar; > + struct rtable *r; > struct art_node *an; > - struct srp_ref sr; > const uint8_t *addr; > int plen; > struct rtentry *mrt; > - int npaths = 0; > - int error = 0; > > - ar = rtable_get(rtableid, dst->sa_family); > - if (ar == NULL) > + r = rtable_get(rtableid, dst->sa_family); > + if (r == NULL) > return (EAFNOSUPPORT); > > - addr = satoaddr(ar, dst); > + addr = satoaddr(r, dst); > plen = rtable_satoplen(dst->sa_family, mask); > if (plen == -1) > return (EINVAL); > > - rtref(rt); /* guarantee rtfree won't do anything under ar_lock */ > - rw_enter_write(&ar->ar_lock); > - an = art_lookup(ar, addr, plen, &sr); > - srp_leave(&sr); /* an can't go away while we have the lock */ > - > - /* Make sure we've got a perfect match. */ > - if (!an_match(an, dst, plen)) { > - error = ESRCH; > - goto leave; > + rw_enter_write(&r->r_lock); > + smr_read_enter(); > + an = art_lookup(r->r_art, addr, plen); > + smr_read_leave(); > + if (an == NULL) { > + rw_exit_write(&r->r_lock); > + return (ESRCH); > } > > - /* > - * If other multipath route entries are still attached to > - * this ART node we only have to unlink it. > - */ > - SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) > - npaths++; > - > - if (npaths > 1) { > - KASSERT(refcnt_read(&rt->rt_refcnt) >= 1); > - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, > - rt_next); > - > - mrt = SRPL_FIRST_LOCKED(&an->an_rtlist); > - if (npaths == 2) > - mrt->rt_flags &= ~RTF_MPATH; > + /* If this is the only route in the list then we can delete the node */ > + if (SMR_PTR_GET_LOCKED(&an->an_value) == rt && > + SMR_PTR_GET_LOCKED(&rt->rt_next) == NULL) { > + struct art_node *oan; > + oan = art_delete(r->r_art, addr, plen); > + if (oan != an) > + panic("art %p changed shape during delete", r->r_art); > + art_put(an); > + /* > + * XXX an and the rt ref could still be alive on other cpus. > + * this currently works because of the NET_LOCK/KERNEL_LOCK > + * but should be fixed if we want to do route lookups outside > + * these locks. - dlg@ > + */ > + } else { > + struct rtentry **prt; > + struct rtentry *nrt; > + unsigned int found = 0; > + unsigned int npaths = 0; > > - goto leave; > + /* > + * If other multipath route entries are still attached to > + * this ART node we only have to unlink it. > + */ > + prt = (struct rtentry **)&an->an_value; > + while ((mrt = SMR_PTR_GET_LOCKED(prt)) != NULL) { > + if (mrt == rt) { > + found = 1; > + SMR_PTR_SET_LOCKED(prt, > + SMR_PTR_GET_LOCKED(&mrt->rt_next)); > + } else if ((mrt->rt_priority & RTP_MASK) == > + (rt->rt_priority & RTP_MASK)) { > + npaths++; > + nrt = mrt; > + } > + prt = &mrt->rt_next; > + } > + if (!found) > + panic("removing non-existent route"); > + if (npaths == 1) > + CLR(nrt->rt_flags, RTF_MPATH); > } > - > - if (art_delete(ar, an, addr, plen) == NULL) > - panic("art_delete failed to find node %p", an); > - > KASSERT(refcnt_read(&rt->rt_refcnt) >= 1); > - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, rt_next); > - art_put(an); > - > -leave: > - rw_exit_write(&ar->ar_lock); > + rw_exit_write(&r->r_lock); > rtfree(rt); > > - return (error); > -} > - > -struct rtable_walk_cookie { > - int (*rwc_func)(struct rtentry *, void *, unsigned int); > - void *rwc_arg; > - struct rtentry **rwc_prt; > - unsigned int rwc_rid; > -}; > - > -/* > - * Helper for rtable_walk to keep the ART code free from any "struct rtentry". > - */ > -int > -rtable_walk_helper(struct art_node *an, void *xrwc) > -{ > - struct srp_ref sr; > - struct rtable_walk_cookie *rwc = xrwc; > - struct rtentry *rt; > - int error = 0; > - > - SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) { > - error = (*rwc->rwc_func)(rt, rwc->rwc_arg, rwc->rwc_rid); > - if (error != 0) > - break; > - } > - if (rwc->rwc_prt != NULL && rt != NULL) { > - rtref(rt); > - *rwc->rwc_prt = rt; > - } > - SRPL_LEAVE(&sr); > - > - return (error); > + return (0); > } > > int > rtable_walk(unsigned int rtableid, sa_family_t af, struct rtentry **prt, > int (*func)(struct rtentry *, void *, unsigned int), void *arg) > { > - struct art_root *ar; > - struct rtable_walk_cookie rwc; > + struct rtable *r; > + struct art_iter ai; > + struct art_node *an; > int error; > > - ar = rtable_get(rtableid, af); > - if (ar == NULL) > + r = rtable_get(rtableid, af); > + if (r == NULL) > return (EAFNOSUPPORT); > > - rwc.rwc_func = func; > - rwc.rwc_arg = arg; > - rwc.rwc_prt = prt; > - rwc.rwc_rid = rtableid; > + rw_enter_write(&r->r_lock); > + ART_FOREACH(an, r->r_art, &ai) { > + /* > + * ART nodes have a list of rtentries. > + * > + * art_iter holds references to the topology > + * so it won't change, but not the an_node or rtentries. > + */ > + struct rtentry *rt = SMR_PTR_GET_LOCKED(&an->an_value); > + rtref(rt); > > - error = art_walk(ar, rtable_walk_helper, &rwc); > + rw_exit_write(&r->r_lock); > + do { > + struct rtentry *nrt; > + > + smr_read_enter(); > + /* Get ready for the next entry. */ > + nrt = SMR_PTR_GET(&rt->rt_next); > + if (nrt != NULL) > + rtref(nrt); > + smr_read_leave(); > + > + error = func(rt, arg, rtableid); > + if (error != 0) { > + if (prt != NULL) > + *prt = rt; > + else > + rtfree(rt); > + > + if (nrt != NULL) > + rtfree(nrt); > + > + rw_enter_write(&r->r_lock); > + art_iter_close(&ai); > + rw_exit_write(&r->r_lock); > + return (error); > + } > + > + rtfree(rt); > + rt = nrt; > + } while (rt != NULL); > + rw_enter_write(&r->r_lock); > + } > + rw_exit_write(&r->r_lock); > > return (error); > } > @@ -774,12 +795,12 @@ struct rtentry * > rtable_iterate(struct rtentry *rt0) > { > struct rtentry *rt = NULL; > - struct srp_ref sr; > > - rt = SRPL_NEXT(&sr, rt0, rt_next); > + smr_read_enter(); > + rt = SMR_PTR_GET(&rt0->rt_next); > if (rt != NULL) > rtref(rt); > - SRPL_LEAVE(&sr); > + smr_read_leave(); > rtfree(rt0); > return (rt); > } > @@ -794,27 +815,25 @@ int > rtable_mpath_reprio(unsigned int rtableid, struct sockaddr *dst, > int plen, uint8_t prio, struct rtentry *rt) > { > - struct art_root *ar; > + struct rtable *r; > struct art_node *an; > - struct srp_ref sr; > const uint8_t *addr; > int error = 0; > > - ar = rtable_get(rtableid, dst->sa_family); > - if (ar == NULL) > + r = rtable_get(rtableid, dst->sa_family); > + if (r == NULL) > return (EAFNOSUPPORT); > > - addr = satoaddr(ar, dst); > - > - rw_enter_write(&ar->ar_lock); > - an = art_lookup(ar, addr, plen, &sr); > - srp_leave(&sr); /* an can't go away while we have the lock */ > + addr = satoaddr(r, dst); > > - /* Make sure we've got a perfect match. */ > - if (!an_match(an, dst, plen)) { > + rw_enter_write(&r->r_lock); > + smr_read_enter(); > + an = art_lookup(r->r_art, addr, plen); > + smr_read_leave(); > + if (an == NULL) { > error = ESRCH; > - } else if (SRPL_FIRST_LOCKED(&an->an_rtlist) == rt && > - SRPL_NEXT_LOCKED(rt, rt_next) == NULL) { > + } else if (SMR_PTR_GET_LOCKED(&an->an_value) == rt && > + SMR_PTR_GET_LOCKED(&rt->rt_next) == NULL) { > /* > * If there's only one entry on the list do not go > * through an insert/remove cycle. This is done to > @@ -823,15 +842,23 @@ rtable_mpath_reprio(unsigned int rtablei > */ > rt->rt_priority = prio; > } else { > - rtref(rt); /* keep rt alive in between remove and insert */ > - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, > - rt, rtentry, rt_next); > + struct rtentry **prt; > + struct rtentry *mrt; > + > + prt = (struct rtentry **)&an->an_value; > + while ((mrt = SMR_PTR_GET_LOCKED(prt)) != NULL) { > + if (mrt == rt) > + break; > + prt = &mrt->rt_next; > + } > + KASSERT(mrt != NULL); > + > + SMR_PTR_SET_LOCKED(prt, SMR_PTR_GET_LOCKED(&rt->rt_next)); > rt->rt_priority = prio; > rtable_mpath_insert(an, rt); > - rtfree(rt); > error = EAGAIN; > } > - rw_exit_write(&ar->ar_lock); > + rw_exit_write(&r->r_lock); > > return (error); > } > @@ -839,63 +866,21 @@ rtable_mpath_reprio(unsigned int rtablei > void > rtable_mpath_insert(struct art_node *an, struct rtentry *rt) > { > - struct rtentry *mrt, *prt = NULL; > + struct rtentry *mrt, **prt; > uint8_t prio = rt->rt_priority; > > - if ((mrt = SRPL_FIRST_LOCKED(&an->an_rtlist)) == NULL) { > - SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); > - return; > - } > - > /* Iterate until we find the route to be placed after ``rt''. */ > - while (mrt->rt_priority <= prio && SRPL_NEXT_LOCKED(mrt, rt_next)) { > - prt = mrt; > - mrt = SRPL_NEXT_LOCKED(mrt, rt_next); > - } > > - if (mrt->rt_priority <= prio) { > - SRPL_INSERT_AFTER_LOCKED(&rt_rc, mrt, rt, rt_next); > - } else if (prt != NULL) { > - SRPL_INSERT_AFTER_LOCKED(&rt_rc, prt, rt, rt_next); > - } else { > - SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); > - } > -} > - > -/* > - * Returns 1 if ``an'' perfectly matches (``dst'', ``plen''), 0 otherwise. > - */ > -int > -an_match(struct art_node *an, const struct sockaddr *dst, int plen) > -{ > - struct rtentry *rt; > - struct srp_ref sr; > - int match; > - > - if (an == NULL || an->an_plen != plen) > - return (0); > - > - rt = SRPL_FIRST(&sr, &an->an_rtlist); > - match = (rt != NULL && memcmp(rt->rt_dest, dst, dst->sa_len) == 0); > - SRPL_LEAVE(&sr); > - > - return (match); > -} > - > -void > -rtentry_ref(void *null, void *xrt) > -{ > - struct rtentry *rt = xrt; > - > - rtref(rt); > -} > + prt = (struct rtentry **)&an->an_value; > + while ((mrt = SMR_PTR_GET_LOCKED(prt)) != NULL) { > + if (mrt->rt_priority >= prio) > + break; > > -void > -rtentry_unref(void *null, void *xrt) > -{ > - struct rtentry *rt = xrt; > + prt = &mrt->rt_next; > + } > > - rtfree(rt); > + SMR_PTR_SET_LOCKED(&rt->rt_next, mrt); > + SMR_PTR_SET_LOCKED(prt, rt); > } > > /* > @@ -904,9 +889,9 @@ rtentry_unref(void *null, void *xrt) > * of "struct sockaddr" used by this routing table. > */ > static inline const uint8_t * > -satoaddr(struct art_root *at, const struct sockaddr *sa) > +satoaddr(struct rtable *r, const struct sockaddr *sa) > { > - return (((const uint8_t *)sa) + at->ar_off); > + return (((const uint8_t *)sa) + r->r_off); > } > > /* > Index: rtable.h > =================================================================== > RCS file: /cvs/src/sys/net/rtable.h,v > diff -u -p -r1.30 rtable.h > --- rtable.h 13 May 2024 01:15:53 -0000 1.30 > +++ rtable.h 13 Jun 2025 06:40:59 -0000 > @@ -28,6 +28,8 @@ > #define rt_plen(rt) ((rt)->rt_plen) > #define RT_ROOT(rt) (0) > > +struct rtable; > + > int rtable_satoplen(sa_family_t, const struct sockaddr *); > > void rtable_init(void);