Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src Introduce pserialize-safe linked lists.
details: https://anonhg.NetBSD.org/src/rev/d1e202692b19
branches: trunk
changeset: 344626:d1e202692b19
user: riastradh <riastradh%NetBSD.org@localhost>
date: Sat Apr 09 04:39:46 2016 +0000
description:
Introduce pserialize-safe linked lists.
These are like LIST_* from queue(3), but issue the appropriate memory
barriers for pserialize readers and writers.
Discussed on tech-kern:
https://mail-index.netbsd.org/tech-kern/2016/04/03/msg020365.html
diffstat:
distrib/sets/lists/comp/mi | 56 +++++-
distrib/sets/lists/tests/mi | 3 +-
share/man/man9/Makefile | 20 +-
share/man/man9/pslist.9 | 432 +++++++++++++++++++++++++++++++++++++++++++
sys/sys/pslist.h | 306 ++++++++++++++++++++++++++++++
tests/include/sys/Makefile | 4 +-
tests/include/sys/t_pslist.c | 125 ++++++++++++
7 files changed, 941 insertions(+), 5 deletions(-)
diffs (truncated from 1059 to 300 lines):
diff -r 23f1ff7d5a5d -r d1e202692b19 distrib/sets/lists/comp/mi
--- a/distrib/sets/lists/comp/mi Fri Apr 08 21:53:10 2016 +0000
+++ b/distrib/sets/lists/comp/mi Sat Apr 09 04:39:46 2016 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.2026 2016/04/03 00:20:22 christos Exp $
+# $NetBSD: mi,v 1.2027 2016/04/09 04:39:46 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
./etc/mtree/set.comp comp-sys-root
@@ -9626,6 +9626,23 @@
./usr/share/man/cat9/PCI_REVISION.0 comp-sys-catman .cat
./usr/share/man/cat9/PCI_VENDOR.0 comp-sys-catman .cat
./usr/share/man/cat9/PMC_ENABLED.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_DESTROY.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_ENTRY_DESTROY.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_ENTRY_INIT.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_ENTRY_INITIALIZER.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_INITIALIZER.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_INIT.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_INITIALIZER.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_READER_FIRST.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_READER_FOREACH.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_READER_NEXT.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_FIRST.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_FOREACH.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_INSERT_AFTER.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_INSERT_BEFORE.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_INSERT_HEAD.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_NEXT.0 comp-sys-catman .cat
+./usr/share/man/cat9/PSLIST_WRITER_REMOVE.0 comp-sys-catman .cat
./usr/share/man/cat9/RUN_ONCE.0 comp-sys-catman .cat
./usr/share/man/cat9/SCHED_LOCK.0 comp-obsolete obsolete
./usr/share/man/cat9/SCHED_UNLOCK.0 comp-obsolete obsolete
@@ -10670,6 +10687,7 @@
./usr/share/man/cat9/pserialize_read_enter.0 comp-sys-catman .cat
./usr/share/man/cat9/pserialize_read_exit.0 comp-sys-catman .cat
./usr/share/man/cat9/psignal.0 comp-sys-catman .cat
+./usr/share/man/cat9/pslist.0 comp-sys-catman .cat
./usr/share/man/cat9/ptoa.0 comp-sys-catman .cat
./usr/share/man/cat9/putiobuf.0 comp-sys-catman .cat
./usr/share/man/cat9/putter.0 comp-sys-catman .cat
@@ -16697,6 +16715,23 @@
./usr/share/man/html9/PCI_REVISION.html comp-sys-htmlman html
./usr/share/man/html9/PCI_VENDOR.html comp-sys-htmlman html
./usr/share/man/html9/PMC_ENABLED.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_DESTROY.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_ENTRY_DESTROY.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_ENTRY_INIT.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_ENTRY_INITIALIZER.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_INITIALIZER.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_INIT.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_INITIALIZER.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_READER_FIRST.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_READER_FOREACH.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_READER_NEXT.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_FIRST.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_FOREACH.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_INSERT_AFTER.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_INSERT_BEFORE.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_INSERT_HEAD.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_NEXT.html comp-sys-htmlman html
+./usr/share/man/html9/PSLIST_WRITER_REMOVE.html comp-sys-htmlman html
./usr/share/man/html9/RUN_ONCE.html comp-sys-htmlman html
./usr/share/man/html9/SET.html comp-sys-htmlman html
./usr/share/man/html9/STACK.html comp-sys-htmlman html
@@ -17692,6 +17727,7 @@
./usr/share/man/html9/pserialize_read_enter.html comp-sys-htmlman html
./usr/share/man/html9/pserialize_read_exit.html comp-sys-htmlman html
./usr/share/man/html9/psignal.html comp-sys-htmlman html
+./usr/share/man/html9/pslist.html comp-sys-htmlman html
./usr/share/man/html9/ptoa.html comp-sys-htmlman html
./usr/share/man/html9/putiobuf.html comp-sys-htmlman html
./usr/share/man/html9/putter.html comp-sys-htmlman html
@@ -23852,6 +23888,23 @@
./usr/share/man/man9/PCI_REVISION.9 comp-sys-man .man
./usr/share/man/man9/PCI_VENDOR.9 comp-sys-man .man
./usr/share/man/man9/PMC_ENABLED.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_DESTROY.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_ENTRY_DESTROY.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_ENTRY_INIT.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_ENTRY_INITIALIZER.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_INITIALIZER.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_INIT.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_INITIALIZER.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_READER_FIRST.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_READER_FOREACH.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_READER_NEXT.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_FIRST.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_FOREACH.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_INSERT_AFTER.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_INSERT_BEFORE.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_INSERT_HEAD.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_NEXT.9 comp-sys-man .man
+./usr/share/man/man9/PSLIST_WRITER_REMOVE.9 comp-sys-man .man
./usr/share/man/man9/RUN_ONCE.9 comp-sys-man .man
./usr/share/man/man9/SCHED_LOCK.9 comp-obsolete obsolete
./usr/share/man/man9/SCHED_UNLOCK.9 comp-obsolete obsolete
@@ -24896,6 +24949,7 @@
./usr/share/man/man9/pserialize_read_enter.9 comp-sys-man .man
./usr/share/man/man9/pserialize_read_exit.9 comp-sys-man .man
./usr/share/man/man9/psignal.9 comp-sys-man .man
+./usr/share/man/man9/pslist.9 comp-sys-man .man
./usr/share/man/man9/ptoa.9 comp-sys-man .man
./usr/share/man/man9/putiobuf.9 comp-sys-man .man
./usr/share/man/man9/putter.9 comp-sys-man .man
diff -r 23f1ff7d5a5d -r d1e202692b19 distrib/sets/lists/tests/mi
--- a/distrib/sets/lists/tests/mi Fri Apr 08 21:53:10 2016 +0000
+++ b/distrib/sets/lists/tests/mi Sat Apr 09 04:39:46 2016 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.671 2016/04/08 10:09:16 gson Exp $
+# $NetBSD: mi,v 1.672 2016/04/09 04:39:47 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -1559,6 +1559,7 @@
./usr/tests/include/sys/t_bitops tests-include-tests compattestfile,atf
./usr/tests/include/sys/t_bootblock tests-include-tests compattestfile,atf
./usr/tests/include/sys/t_cdefs tests-include-tests compattestfile,atf
+./usr/tests/include/sys/t_pslist tests-include-tests compattestfile,atf
./usr/tests/include/sys/t_socket tests-include-tests atf,rump
./usr/tests/include/sys/t_tree tests-include-tests compattestfile,atf
./usr/tests/include/sys/t_types tests-include-tests compattestfile,atf
diff -r 23f1ff7d5a5d -r d1e202692b19 share/man/man9/Makefile
--- a/share/man/man9/Makefile Fri Apr 08 21:53:10 2016 +0000
+++ b/share/man/man9/Makefile Sat Apr 09 04:39:46 2016 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.393 2015/10/26 07:07:36 mrg Exp $
+# $NetBSD: Makefile,v 1.394 2016/04/09 04:39:46 riastradh Exp $
# Makefile for section 9 (kernel function and variable) manual pages.
@@ -43,7 +43,7 @@
pci_msi.9 pckbport.9 pcmcia.9 pcq.9 pcu.9 \
percpu.9 pfil.9 physio.9 pmap.9 pmatch.9 pmc.9 pmf.9 pool.9 \
pool_cache.9 powerhook_establish.9 ppi.9 ppsratecheck.9 preempt.9 \
- proc_find.9 pserialize.9 putter.9 \
+ proc_find.9 pserialize.9 pslist.9 putter.9 \
radio.9 ras.9 rasops.9 ratecheck.9 resettodr.9 rnd.9 rndsink.9 \
roundup.9 rssadapt.9 rt_timer.9 rwlock.9 RUN_ONCE.9 STACK.9 \
scanc.9 \
@@ -705,6 +705,22 @@
pserialize.9 pserialize_read_enter.9 \
pserialize.9 pserialize_read_exit.9 \
pserialize.9 pserialize_perform.9
+MLINKS+=pslist.9 PSLIST_DESTROY.9 \
+ pslist.9 PSLIST_ENTRY_DESTROY.9 \
+ pslist.9 PSLIST_ENTRY_INIT.9 \
+ pslist.9 PSLIST_ENTRY_INITIALIZER.9 \
+ pslist.9 PSLIST_INIT.9 \
+ pslist.9 PSLIST_INITIALIZER.9 \
+ pslist.9 PSLIST_READER_FIRST.9 \
+ pslist.9 PSLIST_READER_FOREACH.9 \
+ pslist.9 PSLIST_READER_NEXT.9 \
+ pslist.9 PSLIST_WRITER_FIRST.9 \
+ pslist.9 PSLIST_WRITER_FOREACH.9 \
+ pslist.9 PSLIST_WRITER_INSERT_AFTER.9 \
+ pslist.9 PSLIST_WRITER_INSERT_BEFORE.9 \
+ pslist.9 PSLIST_WRITER_INSERT_HEAD.9 \
+ pslist.9 PSLIST_WRITER_NEXT.9 \
+ pslist.9 PSLIST_WRITER_REMOVE.9
MLINKS+=ras.9 ras_lookup.9 \
ras.9 ras_fork.9 \
ras.9 ras_purgeall.9
diff -r 23f1ff7d5a5d -r d1e202692b19 share/man/man9/pslist.9
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/share/man/man9/pslist.9 Sat Apr 09 04:39:46 2016 +0000
@@ -0,0 +1,432 @@
+.\" $NetBSD: pslist.9,v 1.1 2016/04/09 04:39:46 riastradh Exp $
+.\"
+.\" Copyright (c) 2016 The NetBSD Foundation, Inc.
+.\" All rights reserved.
+.\"
+.\" This code is derived from software contributed to The NetBSD Foundation
+.\" by Taylor R. Campbell.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+.\" POSSIBILITY OF SUCH DAMAGE.
+.\"
+.Dd April 8, 2016
+.Dt PSLIST 9
+.Os
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+.Sh NAME
+.Nm pslist
+.Nd pserialize-safe linked lists
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+.Sh SYNOPSIS
+.In sys/pslist.h
+.\" Exclusive operations
+.Vt struct pslist_head PSLIST_INITIALIZER ;
+.Vt struct pslist_entry PSLIST_ENTRY_INITIALIZER ;
+.Ft void
+.Fn PSLIST_INIT "struct pslist_head *head"
+.Ft void
+.Fn PSLIST_DESTROY "struct pslist_head *head"
+.Ft void
+.Fn PSLIST_ENTRY_INIT "TYPE *element" "PSLIST_ENTRY NAME"
+.Ft void
+.Fn PSLIST_ENTRY_DESTROY "TYPE *element" "PSLIST_ENTRY NAME"
+.\" Writer operations
+.Ft void
+.Fn PSLIST_WRITER_INSERT_HEAD "struct pslist_head *head" "TYPE *new" "PSLIST_ENTRY NAME"
+.Ft void
+.Fn PSLIST_WRITER_INSERT_BEFORE "TYPE *element" "TYPE *new" "PSLIST_ENTRY NAME"
+.Ft void
+.Fn PSLIST_WRITER_INSERT_AFTER "TYPE *element" "TYPE *new" "PSLIST_ENTRY NAME"
+.Ft void
+.Fn PSLIST_WRITER_REMOVE "TYPE *element" "PSLIST_ENTRY NAME"
+.Ft TYPE *
+.Fn PSLIST_WRITER_FIRST "struct pslist *head" "TYPE" "PSLIST_ENTRY NAME"
+.Ft TYPE *
+.Fn PSLIST_WRITER_NEXT "TYPE *element" "TYPE" "PSLIST_ENTRY NAME"
+.Fn PSLIST_WRITER_FOREACH "TYPE *element" "struct pslist_head *head" "TYPE" "PSLIST_ENTRY NAME"
+.\" Reader operations
+.Ft TYPE *
+.Fn PSLIST_READER_FIRST "TYPE *element" "TYPE" "PSLIST_ENTRY NAME"
+.Ft TYPE *
+.Fn PSLIST_READER_NEXT "TYPE *element" "TYPE" "PSLIST_ENTRY NAME"
+.Fn PSLIST_READER_FOREACH "TYPE *element" "struct pslist_head *head" "TYPE" "PSLIST_ENTRY NAME"
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+.Sh DESCRIPTION
+The
+.Nm
+data structure is a linked list like the
+.Fn LIST_*
+operations in
+.Xr queue 3 ,
+augmented with memory barriers so that any number of readers can safely
+run in parallel with at most one writer, without needing any
+interprocessor synchronization such as locks or atomics on the reader
+side.
+.\"
+.Pp
+The head of a linked list is represented by a
+.Vt struct pslist_head
+object allocated by the caller, e.g. by embedding it in another
+struct, which should be otherwise treated as opaque.
+A linked list head must be initialized with
+.Dv PSLIST_INITIALIZER
+or
+.Fn PSLIST_INIT
+before it may be used.
+When initialized, a list head is empty.
+A list head should be empty and destroyed with
+.Fn PSLIST_DESTROY
+before its memory is reused.
+.\"
+.Pp
+Each entry in a linked list is represented by a
+.Vt struct pslist_entry
+object, also opaque, and embedded as a member in a caller-allocated
+structure called an
+.Em element .
+A
+.Vt struct pslist_entry
+object must be initialized with
+.Dv PSLIST_ENTRY_INITIALIZER
+or
+.Fn PSLIST_ENTRY_INIT
+before it may be used.
+.\"
+.Pp
+When initialized, a list entry is unassociated.
+Inserting an entry associates it with a particular list.
+Removing it
+partially disassociates it from that list and prevents new readers from
+finding it in the list, but allows extant parallel readers to continue
+reading the next entry.
+The caller must then wait, e.g. with
+.Xr pserialize_perform 9 ,
+for all extant parallel readers to finish, before freeing or reusing
+the list entry.
+A list entry should be destroyed with
+.Fn PSLIST_ENTRY_DESTROY
+before it may be reused.
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+.Sh EXCLUSIVE OPERATIONS
+The following operations may be performed on list heads and entries
+when the caller has exclusive access to them -- no parallel writers or
+readers may have access to the same objects.
+.\""""""""""""""""
+.Bl -tag -width abcd
Home |
Main Index |
Thread Index |
Old Index