Index: share/man/man9/srpl_rc_init.9 =================================================================== RCS file: share/man/man9/srpl_rc_init.9 diff -N share/man/man9/srpl_rc_init.9 --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ share/man/man9/srpl_rc_init.9 18 Aug 2015 23:54:52 -0000 @@ -0,0 +1,232 @@ +.\" $OpenBSD$ +.\" +.\" Copyright (c) 2015 David Gwynne +.\" +.\" Permission to use, copy, modify, and distribute this software for any +.\" purpose with or without fee is hereby granted, provided that the above +.\" copyright notice and this permission notice appear in all copies. +.\" +.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +.\" +.Dd $Mdocdate$ +.Dt SRPL_RC_INIT 9 +.Os +.Sh NAME +.Nm srpl_rc_init , +.Nm SRPL_INIT , +.Nm SRPL_ENTER , +.Nm SRPL_NEXT , +.Nm SRPL_FOREACH , +.Nm SRPL_LEAVE , +.Nm SRPL_EMPTY_LOCKED , +.Nm SRPL_FIRST_LOCKED , +.Nm SRPL_NEXT_LOCKED , +.Nm SRPL_FOREACH_LOCKED , +.Nm SRPL_INSERT_HEAD_LOCKED , +.Nm SRPL_REMOVE_LOCKED , +.Nm SRPL_RC_INITIALIZER , +.Nd singly-linked shared reference pointer list +.Sh SYNOPSIS +.In sys/srp.h +.Vt struct srpl; +.Vt struct srpl_entry; +.Vt struct srpl_iter; +.Vt struct srpl_rc; +.Ft void +.Fo "srpl_rc_init" +.Fa "struct srpl_rc *rc" +.Fa "void (*ref)(void *, void *)" +.Fa "void (*unref)(void *, void *)" +.Fa "void *ctx" +.Fc +.Fn "SRPL_INIT" "struct srpl_head *sl" +.Ft void * +.Fn "SRPL_ENTER" "struct srpl *sl" "struct srpl_iter *si" +.Ft void * +.Fn "SRPL_NEXT" "struct srpl_iter *si" "struct TYPE *listelm" "FIELDNAME" +.Fo "SRPL_FOREACH" +.Fa "VARNAME" +.Fa "struct srpl *sl" +.Fa "struct srpl_iter *si" +.Fa "FIELDNAME" +.Fc +.Fn "SRPL_LEAVE" "struct srpl_iter *si" "struct TYPE *listelm" +.Fn "SRPL_EMPTY_LOCKED" "struct srpl *sl" +.Ft void * +.Fn "SRPL_FIRST_LOCKED" "struct srpl *sl" +.Ft void * +.Fn "SRPL_NEXT_LOCKED" "struct TYPE *listelm" "FIELDNAME" +.Fn "SRPL_FOREACH_LOCKED" "VARNAME" "struct srpl *sl" "FIELDNAME" +.Fo "SRPL_INSERT_HEAD_LOCKED" +.Fa "struct srpl_rc *rc" +.Fa "struct srpl *sl" +.Fa "struct TYPE *elm" +.Fa "FIELDNAME" +.Fc +.Fo "SRPL_REMOVE_LOCKED" +.Fa "struct srpl_rc *rc" +.Fa "struct srpl *sl" +.Fa "struct TYPE *listelm" +.Fa "TYPE" +.Fa "FIELDNAME" +.Fc +.Sh DESCRIPTION +The +srpl +macros build a linked list on top of shared reference pointers. +This allows concurrent traversal of a linked list and access to the +items on the list. +.Pp +SRP lists are a generic type represented by a +.Vt struct srpl . +The elements inserted into the list must be structures that contain a +.Vt struct srpl_entry +field. +Further, the elements must also support reference counting as +insertion and removal operations can cause items to be temporarily +referenced by multiple SRPs within the list at the same time. +.Pp +.Fn srpl_rc_init +initialises the SRP list refcounts +.Fa rc +structure so it can be used to manage the reference counts on +elements in the list. +The insertion or removal of an element in an SRP list will increment +the reference counts on elements within the list via calls to +.Fa ref . +. +As these references are released by the SRP infrastructure, the +reference counts will be decremented by calls to +.Fa unref . +.Fa unref +is also responsible for freeing the element when the reference count +reaches 0. +Both +.Fa ref +and +.Fa unref +will be called with +.Fa ctx +as their first argument and a pointer to the element as their second +argument. +.Pp +.Fn SRPL_INIT +initialises the SRP list +.Fa sl +to an empty state. +.Pp +.Fn SRPL_ENTER +begins iterating over elements in the SRP list +.Fa sl . +Local state necessary for iterating over the list is stored in the +SRP list iterator structure +.Fa si . +Every call to +.Fn SRPL_ENTER +must have a corresponding call to +.Fn SRPL_LEAVE +to release references to the list and its elements. +.Pp +.Fn SRPL_NEXT +accesses the element in the SRP list after +.Fa listelm . +.Pp +.Fn SRPL_FOREACH +creates a loop for traversing the list. +Every call to +.Fn SRPL_FOREACH +must have a corresponding call to +.Fn SRPL_LEAVE +to release references to the list and its elements. +.Pp +.Fn SRPL_LEAVE +releases references to the list and its elements held by previous +calls to +.Fn SRPL_ENTER +or +.Fn SRPL_FOREACH . +.Pp +.Fn SRPL_EMPTY_LOCKED +tests whether the SRP list +.Fa sl +is empty. +.Pp +.Fn SRPL_FIRST_LOCKED +accesses the first element in the SRP list +.Fa sl . +.Pp +.Fn SRPL_NEXT_LOCKED +accesses the next element in the SRP list after +.Fa listelm . +.Pp +.Fn SRPL_FOREACH_LOCKED +creates a loop for traversing the elements in the SRP list +.Fa sl . +.Pp +.Fn SRPL_INSERT_HEAD_LOCKED +inserts +.Fa elm +into the SRP list +.Fa sl . +Reference counts are adjusted on the list items using the functions +specified by +.Fa rc . +.Fn SRPL_REMOVE_LOCKED +iterates over the SRP list +.Fa sl +until it finds +.Fa listelm +and then removes it. +Reference counts are adjusted on the list items using the functions +specified by +.Fa rc . +.Pp +An srpl_rc declaration can be initialised with the +.Fn SRPL_RC_INITIALIZER +macro. +.Sh CONTEXT +.Fn SRPL_INIT , +.Fn SRPL_ENTER , +.Fn SRPL_NEXT , +.Fn SRPL_FOREACH , +and +.Fn SRPL_LEAVE +may be called during autoconf, from process context, or from interrupt +context. +.Pp +.Fn srpl_rc_init , +.Fn SRPL_EMPTY_LOCKED , +.Fn SRPL_FIRST_LOCKED , +.Fn SRPL_NEXT_LOCKED , +.Fn SRPL_FOREACH_LOCKED , +.Fn SRPL_INSERT_HEAD_LOCKED , +and +.Fn SRPL_REMOVE_LOCKED +may be called during autoconf or from process context. +An appropriate lock must be held that prevents concurrent modifications +to the list. +.Sh RETURN VALUES +.Fn SRPL_ENTER , +.Fn SRPL_NEXT , +.Fn SRPL_FIRST_LOCKED , +and +.Fn SRPL_NEXT_LOCKED +return a pointer to elements in the SRP list, or +.Dv NULL +if there are no more elements. +.Pp +.Fn SRPL_EMPTY_LOCKED +returns non-zero when the list is empty, otherwise 0. +.Sh HISTORY +The srp API was originally written by +.An Jonathan Matthew Aq Mt jmatthew@openbsd.org +and +.An David Gwynne Aq Mt dlg@openbsd.org . +The SRP list API first appeared in +.Ox 5.9 . Index: share/man/man9/Makefile =================================================================== RCS file: /cvs/src/share/man/man9/Makefile,v retrieving revision 1.238 diff -u -p -r1.238 Makefile --- share/man/man9/Makefile 14 Aug 2015 05:25:29 -0000 1.238 +++ share/man/man9/Makefile 18 Aug 2015 23:54:52 -0000 @@ -29,7 +29,7 @@ MAN= aml_evalnode.9 atomic_add_int.9 ato radio.9 arc4random.9 rasops.9 ratecheck.9 resettodr.9 rssadapt.9 \ route.9 rt_ifa_add.9 rt_timer_add.9 rtalloc.9 rtable_add.9 \ rtlabel_id2name.9 rtrequest1.9 rwlock.9 SipHash24.9 sensor_attach.9 \ - spl.9 srp_enter.9 startuphook_establish.9 \ + spl.9 srp_enter.9 srpl_rc_init.9 startuphook_establish.9 \ socreate.9 sosplice.9 style.9 syscall.9 systrace.9 sysctl_int.9 \ task_add.9 tc_init.9 time.9 timeout.9 tsleep.9 tvtohz.9 \ uiomove.9 uvm.9 usbd_close_pipe.9 usbd_open_pipe.9 usbd_transfer.9 \ @@ -369,6 +369,16 @@ MLINKS+=srp_enter.9 srp_init.9 srp_enter srp_enter.9 srp_leave.9 srp_enter.9 srp_get_locked.9 \ srp_enter.9 srp_finalize.9 \ srp_enter.9 SRP_INITIALIZER.9 srp_enter.9 SRP_GC_INITIALIZER.9 +MLINKS+=srpl_rc_init.9 SRPL_HEAD_INIT.9 srpl_rc_init.9 SRPL_HEAD_INIT.9 \ + srpl_rc_init.9 SRPL_ENTRY_INIT.9 srpl_rc_init.9 SRPL_ENTER.9 \ + srpl_rc_init.9 SRPL_NEXT.9 srpl_rc_init.9 SRPL_FOREACH.9 \ + srpl_rc_init.9 SRPL_LEAVE.9 srpl_rc_init.9 SRPL_EMPTY_LOCKED.9 \ + srpl_rc_init.9 SRPL_FIRST_LOCKED.9 srpl_rc_init.9 SRPL_NEXT_LOCKED.9 \ + srpl_rc_init.9 SRPL_FOREACH_LOCKED.9 \ + srpl_rc_init.9 SRPL_INSERT_HEAD_LOCKED.9 \ + srpl_rc_init.9 SRPL_REMOVE_LOCKED.9 \ + srpl_rc_init.9 SRPL_RC_INITIALIZER.9 \ + MLINKS+=sysctl_int.9 sysctl_int_arr.9 sysctl_int.9 sysctl_quad.9 \ sysctl_int.9 sysctl_string.9 sysctl_int.9 sysctl_tstring.9 \ sysctl_int.9 sysctl_rdint.9 sysctl_int.9 sysctl_rdquad.9 \ Index: sys/sys/srp.h =================================================================== RCS file: /cvs/src/sys/sys/srp.h,v retrieving revision 1.1 diff -u -p -r1.1 srp.h --- sys/sys/srp.h 2 Jul 2015 01:34:00 -0000 1.1 +++ sys/sys/srp.h 18 Aug 2015 23:54:52 -0000 @@ -61,4 +61,110 @@ void srp_leave(struct srp *, void *); #endif /* _KERNEL */ +/* + * singly linked list built by following srps + */ + +struct srpl_rc { + void (*srpl_ref)(void *, void *); + struct srp_gc srpl_gc; +}; +#define srpl_cookie srpl_gc.srp_gc_cookie + +struct srpl { + struct srp sl_head; +}; + +struct srpl_entry { + struct srp se_next; +}; + +struct srpl_iter { + struct srp * si_ref; +}; + +#ifdef _KERNEL + +void srpl_rc_init(struct srpl_rc *, void (*)(void *, void *), + void (*)(void *, void *), void *); + +#define SRPL_RC_INITIALIZER(_r, _u, _c) { _r, SRP_GC_INITIALIZER(_u, _c) } + +#define SRPL_INIT(_sl) srp_init(&(_sl)->sl_head) + +static inline void * +_srpl_enter(struct srpl *sl, struct srpl_iter *si) +{ + si->si_ref = &sl->sl_head; + return (srp_enter(si->si_ref)); +} + +static inline void * +_srpl_next(struct srpl_iter *si, void *elm, struct srp *nref) +{ + void *n; + + n = srp_enter(nref); + srp_leave(si->si_ref, elm); + si->si_ref = nref; + + return (n); +} + +#define SRPL_ENTER(_sl, _si) _srpl_enter(_sl, _si) + +#define SRPL_NEXT(_si, _e, _ENTRY) \ + _srpl_next(_si, _e, &(_e)->_ENTRY.se_next) + +#define SRPL_FOREACH(_c, _sl, _si, _ENTRY) \ + for ((_c) = SRPL_ENTER(_sl, _si); \ + (_c) != NULL; \ + (_c) = SRPL_NEXT(_si, _c, _ENTRY)) + +#define SRPL_LEAVE(_si, _c) srp_leave((_si)->si_ref, (_c)) + +#define SRPL_EMPTY_LOCKED(_sl) (SRPL_FIRST_LOCKED(_sl) == NULL) +#define SRPL_FIRST_LOCKED(_sl) srp_get_locked(&(_sl)->sl_head) + +#define SRPL_NEXT_LOCKED(_e, _ENTRY) \ + srp_get_locked(&(_e)->_ENTRY.se_next) + +#define SRPL_FOREACH_LOCKED(_c, _sl, _ENTRY) \ + for ((_c) = SRPL_FIRST_LOCKED(_sl); \ + (_c) != NULL; \ + (_c) = SRPL_NEXT_LOCKED((_c), _ENTRY)) + +#define SRPL_INSERT_HEAD_LOCKED(_rc, _sl, _e, _ENTRY) do { \ + void *head; \ + \ + srp_init(&(_e)->_ENTRY.se_next); \ + \ + head = SRPL_FIRST_LOCKED(_sl); \ + if (head != NULL) { \ + (_rc)->srpl_ref(&(_rc)->srpl_cookie, head); \ + srp_update_locked(&(_rc)->srpl_gc, \ + &(_e)->_ENTRY.se_next, head); \ + } \ + \ + (_rc)->srpl_ref(&(_rc)->srpl_cookie, _e); \ + srp_update_locked(&(_rc)->srpl_gc, &(_sl)->sl_head, (_e)); \ +} while (0) + +#define SRPL_REMOVE_LOCKED(_rc, _sl, _e, _type, _ENTRY) do { \ + struct srp *ref; \ + struct _type *c, *n; \ + \ + ref = &(_sl)->sl_head; \ + while ((c = srp_get_locked(ref)) != (_e)) \ + ref = &c->_ENTRY.se_next; \ + \ + n = SRPL_NEXT_LOCKED(c, _ENTRY); \ + if (n != NULL) \ + (_rc)->srpl_ref(&(_rc)->srpl_cookie, n); \ + srp_update_locked(&(_rc)->srpl_gc, ref, n); \ + srp_update_locked(&(_rc)->srpl_gc, &c->_ENTRY.se_next, NULL); \ +} while (0) + +#endif /* _KERNEL */ + #endif /* _SYS_SRP_H_ */ Index: sys/kern/kern_srp.c =================================================================== RCS file: /cvs/src/sys/kern/kern_srp.c,v retrieving revision 1.1 diff -u -p -r1.1 kern_srp.c --- sys/kern/kern_srp.c 2 Jul 2015 01:34:00 -0000 1.1 +++ sys/kern/kern_srp.c 18 Aug 2015 23:54:52 -0000 @@ -27,6 +27,14 @@ void srp_v_gc_start(struct srp_gc *, struct srp *, void *); void +srpl_rc_init(struct srpl_rc *rc, void (*ref)(void *, void *), + void (*unref)(void *, void *), void *cookie) +{ + rc->srpl_ref = ref; + srp_gc_init(&rc->srpl_gc, unref, cookie); +} + +void srp_gc_init(struct srp_gc *srp_gc, void (*dtor)(void *, void *), void *cookie) { srp_gc->srp_gc_dtor = dtor; @@ -39,6 +47,12 @@ srp_init(struct srp *srp) { srp->ref = NULL; } + +void srpl_refs_init(struct srpl_rc *, void (*)(void *, void *), + void (*)(void *, void *), void *); + +#define SRPL_RC_INITIALIZER(_r, _u, _c) { _r, SRP_GC_INITIALIZER(_u, _c) } + void srp_update_locked(struct srp_gc *srp_gc, struct srp *srp, void *nv) Index: sys/net/bpf.c =================================================================== RCS file: /cvs/src/sys/net/bpf.c,v retrieving revision 1.121 diff -u -p -r1.121 bpf.c --- sys/net/bpf.c 16 Aug 2015 12:17:16 -0000 1.121 +++ sys/net/bpf.c 18 Aug 2015 23:54:52 -0000 @@ -128,8 +128,10 @@ void bpfilter_destroy(struct bpf_d *); * garbage collector srps */ -void bpf_d_dtor(void *, void *); -struct srp_gc bpf_d_gc = SRP_GC_INITIALIZER(bpf_d_dtor, NULL); +void bpf_d_ref(void *, void *); +void bpf_d_unref(void *, void *); +struct srpl_rc bpf_d_rc = SRPL_RC_INITIALIZER(bpf_d_ref, bpf_d_unref, NULL); + void bpf_insn_dtor(void *, void *); struct srp_gc bpf_insn_gc = SRP_GC_INITIALIZER(bpf_insn_dtor, NULL); @@ -261,8 +263,6 @@ bpf_movein(struct uio *uio, u_int linkty void bpf_attachd(struct bpf_d *d, struct bpf_if *bp) { - struct bpf_d *head; - /* * Point d at bp, and add d to the interface's list of listeners. * Finally, point the driver's bpf cookie at the interface so @@ -270,16 +270,9 @@ bpf_attachd(struct bpf_d *d, struct bpf_ */ d->bd_bif = bp; - srp_init(&d->bd_next); KERNEL_ASSERT_LOCKED(); - head = srp_get_locked(&bp->bif_dlist); - if (head != NULL) { - D_GET(head); - srp_update_locked(&bpf_d_gc, &d->bd_next, head); - } - D_GET(d); - srp_update_locked(&bpf_d_gc, &bp->bif_dlist, d); + SRPL_INSERT_HEAD_LOCKED(&bpf_d_rc, &bp->bif_dlist, d, bd_next); *bp->bif_driverp = bp; } @@ -290,8 +283,6 @@ bpf_attachd(struct bpf_d *d, struct bpf_ void bpf_detachd(struct bpf_d *d) { - struct srp *dref; - struct bpf_d *p, *next; struct bpf_if *bp; bp = d->bd_bif; @@ -315,24 +306,9 @@ bpf_detachd(struct bpf_d *d) /* Remove d from the interface's descriptor list. */ KERNEL_ASSERT_LOCKED(); - dref = &bp->bif_dlist; - for (;;) { - p = srp_get_locked(dref); - if (p == NULL) - panic("bpf_detachd: descriptor not in list"); - if (d == p) - break; - - dref = &p->bd_next; - } - - next = srp_get_locked(&d->bd_next); - if (next != NULL) - D_GET(next); - srp_update_locked(&bpf_d_gc, dref, next); - srp_update_locked(&bpf_d_gc, &d->bd_next, NULL); + SRPL_REMOVE_LOCKED(&bpf_d_rc, &bp->bif_dlist, d, bpf_d, bd_next); - if (srp_get_locked(&bp->bif_dlist) == NULL) { + if (SRPL_EMPTY_LOCKED(&bp->bif_dlist)) { /* * Let the driver know that there are no more listeners. */ @@ -1146,15 +1122,13 @@ int bpf_tap(caddr_t arg, u_char *pkt, u_int pktlen, u_int direction) { struct bpf_if *bp = (struct bpf_if *)arg; - struct srp *dref, *nref; - struct bpf_d *d, *next; + struct srpl_iter i; + struct bpf_d *d; size_t slen; struct timeval tv; int drop = 0, gottime = 0; - dref = &bp->bif_dlist; - d = srp_enter(dref); - while (d != NULL) { + SRPL_FOREACH(d, &bp->bif_dlist, &i, bd_next) { atomic_inc_long(&d->bd_rcount); if ((direction & d->bd_dirfilt) != 0) @@ -1177,14 +1151,8 @@ bpf_tap(caddr_t arg, u_char *pkt, u_int if (d->bd_fildrop) drop++; } - - nref = &d->bd_next; - next = srp_enter(nref); - srp_leave(dref, d); - dref = nref; - d = next; } - srp_leave(dref, d); + SRPL_LEAVE(&i, d); return (drop); } @@ -1221,8 +1189,8 @@ _bpf_mtap(caddr_t arg, struct mbuf *m, u void (*cpfn)(const void *, void *, size_t)) { struct bpf_if *bp = (struct bpf_if *)arg; - struct srp *dref, *nref; - struct bpf_d *d, *next; + struct srpl_iter i; + struct bpf_d *d; size_t pktlen, slen; struct mbuf *m0; struct timeval tv; @@ -1238,9 +1206,7 @@ _bpf_mtap(caddr_t arg, struct mbuf *m, u for (m0 = m; m0 != NULL; m0 = m0->m_next) pktlen += m0->m_len; - dref = &bp->bif_dlist; - d = srp_enter(dref); - while (d != NULL) { + SRPL_FOREACH(d, &bp->bif_dlist, &i, bd_next) { atomic_inc_long(&d->bd_rcount); if ((direction & d->bd_dirfilt) != 0) @@ -1266,14 +1232,8 @@ _bpf_mtap(caddr_t arg, struct mbuf *m, u if (d->bd_fildrop) m->m_flags |= M_FILDROP; } - - nref = &d->bd_next; - next = srp_enter(nref); - srp_leave(dref, d); - dref = nref; - d = next; } - srp_leave(dref, d); + SRPL_LEAVE(&i, d); } /* @@ -1499,7 +1459,7 @@ bpfattach(caddr_t *driverp, struct ifnet if ((bp = malloc(sizeof(*bp), M_DEVBUF, M_NOWAIT)) == NULL) panic("bpfattach"); - srp_init(&bp->bif_dlist); + SRPL_INIT(&bp->bif_dlist); bp->bif_driverp = (struct bpf_if **)driverp; bp->bif_ifp = ifp; bp->bif_dlt = dlt; @@ -1538,8 +1498,7 @@ bpfdetach(struct ifnet *ifp) if (cdevsw[maj].d_open == bpfopen) break; - for (bd = srp_get_locked(&bp->bif_dlist); - bd != NULL; bd = srp_get_locked(&bp->bif_dlist)) { + SRPL_FOREACH_LOCKED(bd, &bp->bif_dlist, bd_next) { struct bpf_d *d; /* @@ -1708,7 +1667,13 @@ bpf_setdlt(struct bpf_d *d, u_int dlt) } void -bpf_d_dtor(void *null, void *d) +bpf_d_ref(void *null, void *d) +{ + D_GET((struct bpf_d *)d); +} + +void +bpf_d_unref(void *null, void *d) { D_PUT(d); } Index: sys/net/bpfdesc.h =================================================================== RCS file: /cvs/src/sys/net/bpfdesc.h,v retrieving revision 1.25 diff -u -p -r1.25 bpfdesc.h --- sys/net/bpfdesc.h 16 Aug 2015 12:17:16 -0000 1.25 +++ sys/net/bpfdesc.h 18 Aug 2015 23:54:52 -0000 @@ -48,7 +48,7 @@ * Descriptor associated with each open bpf file. */ struct bpf_d { - struct srp bd_next; /* Linked list of descriptors */ + struct srpl_entry bd_next; /* Linked list of descriptors */ /* * Buffer slots: two mbuf clusters buffer the incoming packets. * The model has three slots. Sbuf is always occupied. @@ -98,7 +98,7 @@ struct bpf_d { */ struct bpf_if { struct bpf_if *bif_next; /* list of all interfaces */ - struct srp bif_dlist; /* descriptor list */ + struct srpl bif_dlist; /* descriptor list */ struct bpf_if **bif_driverp; /* pointer into softc */ u_int bif_dlt; /* link layer type */ u_int bif_hdrlen; /* length of header (with padding) */