epoch(9) background information?

[Sebastian Huber]

Hello,

I update currently a port of the FreeBSD network stack, etc. to the
real-time operating system RTEMS from the head version at 2017-04-04 to
the head version of today. I noticed that some read-write locks are
replaced by a relatively new stuff called EPOCH(9). Is there some
background information available for this? The man page is a bit vague
and searching for something named epoch on the internet is not really
great. For example, what is the motivation for this change? How is this
related to read-copy-update (RCU)?
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Jacques Fourie]

On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber <

Post by Sebastian Huber
Hello,
I update currently a port of the FreeBSD network stack, etc. to the
real-time operating system RTEMS from the head version at 2017-04-04 to the
head version of today. I noticed that some read-write locks are replaced by
a relatively new stuff called EPOCH(9). Is there some background
information available for this? The man page is a bit vague and searching
for something named epoch on the internet is not really great. For example,
what is the motivation for this change? How is this related to
read-copy-update (RCU)?
--
Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
<https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g>
Phone : [phone]
Fax : [phone]
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers

Additional information is available here : http://concurrencykit.org/pr
esentations/ebr.pdf. The way I understand it is that it is mostly used in
place of read locks to provide liveness guarantees without using atomics.
Additional detail is available in the commit messages. As an example see
r333813 for some performance data.

[Sebastian Huber]

Post by Jacques Fourie
On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber
Hello,
I update currently a port of the FreeBSD network stack, etc. to
the real-time operating system RTEMS from the head version at
2017-04-04 to the head version of today. I noticed that some
read-write locks are replaced by a relatively new stuff called
EPOCH(9). Is there some background information available for this?
The man page is a bit vague and searching for something named
epoch on the internet is not really great. For example, what is
the motivation for this change? How is this related to
read-copy-update (RCU)?
--
Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
<https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g>
Phone   : [phone]
Fax     : [phone]
PGP     : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
<https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>
To unsubscribe, send any mail to
http://concurrencykit.org/presentations/ebr.pdf
<http://concurrencykit.org/presentations/ebr.pdf>. The way I
understand it is that it is mostly used in place of read locks to
provide liveness guarantees without using atomics. Additional detail
is available in the commit messages. As an example see r333813 for
some performance data.

Thanks, for the reference. The "epoch reclamation" are good keywords to
find more information.

What is the right mailing list to ask questions about the epoch
implementation of the FreeBSD kernel?

To support this machinery in RTEMS is a bit difficult (in particular
EPOCH_LOCKED). Since RTEMS is supposed to be a real-time operating
system it supports only fixed-priority and job-level fixed priority
(EDF) schedulers. To allow some scaling to larger SMP systems it
supports clustered scheduling together with the mutual exclusion locking
protocols MrsP (http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf) and
OMIP (http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf). This makes
the thread pinning hard to implement (which is very easy to support in
FreeBSD). The locking protocols may temporarily move a thread which owns
a mutex to a foreign scheduler instance, e.g. a thread which wants to
obtain the mutex helps the owner to make progress if it was pre-empted
in its home scheduler instance. Due to a timeout of the helper the owner
may loose the right to execute in the foreign scheduler instance. This
would make it impossible to fulfil the processor pinning constraint
(e.g. the thread priority in the foreign scheduler instance is undefined).

It would save me a lot of trouble if I could assume that EPOCH_LOCKED is
an exotic feature which is unlikely to get used in FreeBSD.
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Sebastian Huber]

Post by Sebastian Huber

Post by Jacques Fourie
On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber
    Hello,
    I update currently a port of the FreeBSD network stack, etc. to
    the real-time operating system RTEMS from the head version at
    2017-04-04 to the head version of today. I noticed that some
    read-write locks are replaced by a relatively new stuff called
    EPOCH(9). Is there some background information available for this?
    The man page is a bit vague and searching for something named
    epoch on the internet is not really great. For example, what is
    the motivation for this change? How is this related to
    read-copy-update (RCU)?
    --     Sebastian Huber, embedded brains GmbH
    Address : Dornierstr. 4, D-82178 Puchheim, Germany
<https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g>
    Phone   : [phone]
    Fax     : [phone]
    PGP     : Public key available on request.
    Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des
EHUG.
    _______________________________________________
    mailing list
    https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
<https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>
    To unsubscribe, send any mail to
http://concurrencykit.org/presentations/ebr.pdf
<http://concurrencykit.org/presentations/ebr.pdf>. The way I
understand it is that it is mostly used in place of read locks to
provide liveness guarantees without using atomics. Additional detail
is available in the commit messages. As an example see r333813 for
some performance data.

Thanks, for the reference. The "epoch reclamation" are good keywords
to find more information.
What is the right mailing list to ask questions about the epoch
implementation of the FreeBSD kernel?
To support this machinery in RTEMS is a bit difficult (in particular
EPOCH_LOCKED). Since RTEMS is supposed to be a real-time operating
system it supports only fixed-priority and job-level fixed priority
(EDF) schedulers. To allow some scaling to larger SMP systems it
supports clustered scheduling together with the mutual exclusion
locking protocols MrsP
(http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf) and OMIP
(http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf). This makes the
thread pinning hard to implement (which is very easy to support in
FreeBSD). The locking protocols may temporarily move a thread which
owns a mutex to a foreign scheduler instance, e.g. a thread which
wants to obtain the mutex helps the owner to make progress if it was
pre-empted in its home scheduler instance. Due to a timeout of the
helper the owner may loose the right to execute in the foreign
scheduler instance. This would make it impossible to fulfil the
processor pinning constraint (e.g. the thread priority in the foreign
scheduler instance is undefined).
It would save me a lot of trouble if I could assume that EPOCH_LOCKED
is an exotic feature which is unlikely to get used in FreeBSD.

Another question, is it a common use case to call epoch_enter_preempt()
and epoch_exit_preempt() while owning a mutex?
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Matthew Macy]

On Tue, Aug 21, 2018 at 11:42 PM Sebastian Huber <

Post by Sebastian Huber

Post by Sebastian Huber

Post by Jacques Fourie
On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber
Hello,
I update currently a port of the FreeBSD network stack, etc. to
the real-time operating system RTEMS from the head version at
2017-04-04 to the head version of today. I noticed that some
read-write locks are replaced by a relatively new stuff called
EPOCH(9). Is there some background information available for this?
The man page is a bit vague and searching for something named
epoch on the internet is not really great. For example, what is
the motivation for this change? How is this related to
read-copy-update (RCU)?
-- Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
<

https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g

Post by Sebastian Huber

Post by Jacques Fourie
Phone : [phone]
Fax : [phone]
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
<https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>
To unsubscribe, send any mail to
http://concurrencykit.org/presentations/ebr.pdf
<http://concurrencykit.org/presentations/ebr.pdf>. The way I
understand it is that it is mostly used in place of read locks to
provide liveness guarantees without using atomics. Additional detail
is available in the commit messages. As an example see r333813 for
some performance data.

Thanks, for the reference. The "epoch reclamation" are good keywords
to find more information.
What is the right mailing list to ask questions about the epoch
implementation of the FreeBSD kernel?
To support this machinery in RTEMS is a bit difficult (in particular
EPOCH_LOCKED). Since RTEMS is supposed to be a real-time operating
system it supports only fixed-priority and job-level fixed priority
(EDF) schedulers. To allow some scaling to larger SMP systems it
supports clustered scheduling together with the mutual exclusion
locking protocols MrsP
(http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf) and OMIP
(http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf). This makes the
thread pinning hard to implement (which is very easy to support in
FreeBSD). The locking protocols may temporarily move a thread which
owns a mutex to a foreign scheduler instance, e.g. a thread which
wants to obtain the mutex helps the owner to make progress if it was
pre-empted in its home scheduler instance. Due to a timeout of the
helper the owner may loose the right to execute in the foreign
scheduler instance. This would make it impossible to fulfil the
processor pinning constraint (e.g. the thread priority in the foreign
scheduler instance is undefined).
It would save me a lot of trouble if I could assume that EPOCH_LOCKED
is an exotic feature which is unlikely to get used in FreeBSD.

Another question, is it a common use case to call epoch_enter_preempt()
and epoch_exit_preempt() while owning a mutex?

Yes. Very. It is generally not permitted to hold a mutex across
epoch_wait() that's why there's the special flag EPOCH_LOCKED. If you have
a very limited number of threads, you might want to have each thread have
its own record registered with the epoch. Then you wouldn't need the CPU
pinning. The pinning is just away of providing a limited number of records
to an unbounded number of threads.

-M

[Sebastian Huber]

Post by Matthew Macy
On Tue, Aug 21, 2018 at 11:42 PM Sebastian Huber

Post by Sebastian Huber

Post by Jacques Fourie
On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber
    Hello,
    I update currently a port of the FreeBSD network stack, etc. to
    the real-time operating system RTEMS from the head version at
    2017-04-04 to the head version of today. I noticed that some
    read-write locks are replaced by a relatively new stuff called
    EPOCH(9). Is there some background information available

for this?

Post by Sebastian Huber

Post by Jacques Fourie
    The man page is a bit vague and searching for something named
    epoch on the internet is not really great. For example, what is
    the motivation for this change? How is this related to
    read-copy-update (RCU)?
    --     Sebastian Huber, embedded brains GmbH
    Address : Dornierstr. 4, D-82178 Puchheim, Germany

<https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g>

Post by Sebastian Huber

Post by Jacques Fourie
    Phone   : [phone]
    Fax     : [phone]
    PGP     : Public key available on request.
    Diese Nachricht ist keine geschäftliche Mitteilung im Sinne

des

Post by Sebastian Huber

Post by Jacques Fourie
EHUG.
    _______________________________________________
    mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
<https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>
    To unsubscribe, send any mail to
http://concurrencykit.org/presentations/ebr.pdf
<http://concurrencykit.org/presentations/ebr.pdf>. The way I
understand it is that it is mostly used in place of read locks to
provide liveness guarantees without using atomics. Additional

detail

Post by Sebastian Huber

Post by Jacques Fourie
is available in the commit messages. As an example see r333813 for
some performance data.

Thanks, for the reference. The "epoch reclamation" are good

keywords

Post by Sebastian Huber
to find more information.
What is the right mailing list to ask questions about the epoch
implementation of the FreeBSD kernel?
To support this machinery in RTEMS is a bit difficult (in

particular

Post by Sebastian Huber
EPOCH_LOCKED). Since RTEMS is supposed to be a real-time operating
system it supports only fixed-priority and job-level fixed priority
(EDF) schedulers. To allow some scaling to larger SMP systems it
supports clustered scheduling together with the mutual exclusion
locking protocols MrsP
(http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf

<http://www-users.cs.york.ac.uk/%7Eburns/MRSPpaper.pdf>) and OMIP

Post by Sebastian Huber
(http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf

<http://www.mpi-sws.org/%7Ebbb/papers/pdf/ecrts13b.pdf>). This
makes the

Post by Sebastian Huber
thread pinning hard to implement (which is very easy to support in
FreeBSD). The locking protocols may temporarily move a thread which
owns a mutex to a foreign scheduler instance, e.g. a thread which
wants to obtain the mutex helps the owner to make progress if it

was

Post by Sebastian Huber
pre-empted in its home scheduler instance. Due to a timeout of the
helper the owner may loose the right to execute in the foreign
scheduler instance. This would make it impossible to fulfil the
processor pinning constraint (e.g. the thread priority in the

foreign

Post by Sebastian Huber
scheduler instance is undefined).
It would save me a lot of trouble if I could assume that

EPOCH_LOCKED

Post by Sebastian Huber
is an exotic feature which is unlikely to get used in FreeBSD.

Another question, is it a common use case to call
epoch_enter_preempt()
and epoch_exit_preempt() while owning a mutex?
Yes. Very. It is generally not permitted to hold a mutex across
epoch_wait() that's why there's the special flag EPOCH_LOCKED. If you
have a very limited number of threads, you might want to have each
thread have its own record registered with the epoch. Then you
wouldn't need the CPU pinning. The pinning is just away of providing a
limited number of records to an unbounded number of threads.

Thanks for the prompt answer.

Do I need a record per thread and per epoch? Could I use only one (maybe
dependent on the nest level?) record per thread?
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Matthew Macy]

Post by Sebastian Huber

Post by Matthew Macy
Yes. Very. It is generally not permitted to hold a mutex across
epoch_wait() that's why there's the special flag EPOCH_LOCKED. If you
have a very limited number of threads, you might want to have each
thread have its own record registered with the epoch. Then you
wouldn't need the CPU pinning. The pinning is just away of providing a
limited number of records to an unbounded number of threads.

Thanks for the prompt answer.
Do I need a record per thread and per epoch? Could I use only one (maybe
dependent on the nest level?) record per thread?

A record can only be registered with one epoch. And yes you can have just
one single global epoch. However, then the epoch_wait_preempt time or time
until the gc task is run is determined be the longest epoch section
globally.

It may help to look at the ck_epoch man pages and the implementation in ck
https://www.mankier.com/3/ck_epoch_register

https://github.com/concurrencykit/ck/blob/master/src/ck_epoch.c

https://github.com/concurrencykit/ck/blob/master/include/ck_epoch.h

Post by Sebastian Huber
--

[Sebastian Huber]

Post by Matthew Macy

Post by Sebastian Huber

Post by Matthew Macy
Yes. Very. It is generally not permitted to hold a mutex across
epoch_wait() that's why there's the special flag EPOCH_LOCKED. If you
have a very limited number of threads, you might want to have each
thread have its own record registered with the epoch. Then you
wouldn't need the CPU pinning. The pinning is just away of providing a
limited number of records to an unbounded number of threads.

Thanks for the prompt answer.
Do I need a record per thread and per epoch? Could I use only one (maybe
dependent on the nest level?) record per thread?

A record can only be registered with one epoch. And yes you can have just
one single global epoch. However, then the epoch_wait_preempt time or time
until the gc task is run is determined be the longest epoch section
globally.

I think the thread pinning feature is absolutely necessary for an
efficient implementation. You have to avoid any atomic read-modify-write
operations in the fast path. For the preempt variants you have to
maintain a list of threads and for this you need per-processor list heads.
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Julian Elischer]

Post by Matthew Macy
On Tue, Aug 21, 2018 at 11:42 PM Sebastian Huber <

Post by Sebastian Huber

Post by Sebastian Huber

Post by Jacques Fourie
On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber
Hello,
I update currently a port of the FreeBSD network stack, etc. to
the real-time operating system RTEMS from the head version at
2017-04-04 to the head version of today. I noticed that some
read-write locks are replaced by a relatively new stuff called
EPOCH(9). Is there some background information available for this?
The man page is a bit vague and searching for something named
epoch on the internet is not really great. For example, what is
the motivation for this change? How is this related to
read-copy-update (RCU)?
-- Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
<

https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g

Post by Sebastian Huber

Post by Jacques Fourie
Phone : [phone]
Fax : [phone]
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
<https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>
To unsubscribe, send any mail to
http://concurrencykit.org/presentations/ebr.pdf
<http://concurrencykit.org/presentations/ebr.pdf>. The way I
understand it is that it is mostly used in place of read locks to
provide liveness guarantees without using atomics. Additional detail
is available in the commit messages. As an example see r333813 for
some performance data.

Thanks, for the reference. The "epoch reclamation" are good keywords
to find more information.
What is the right mailing list to ask questions about the epoch
implementation of the FreeBSD kernel?
To support this machinery in RTEMS is a bit difficult (in particular
EPOCH_LOCKED). Since RTEMS is supposed to be a real-time operating
system it supports only fixed-priority and job-level fixed priority
(EDF) schedulers. To allow some scaling to larger SMP systems it
supports clustered scheduling together with the mutual exclusion
locking protocols MrsP
(http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf) and OMIP
(http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf). This makes the
thread pinning hard to implement (which is very easy to support in
FreeBSD). The locking protocols may temporarily move a thread which
owns a mutex to a foreign scheduler instance, e.g. a thread which
wants to obtain the mutex helps the owner to make progress if it was
pre-empted in its home scheduler instance. Due to a timeout of the
helper the owner may loose the right to execute in the foreign
scheduler instance. This would make it impossible to fulfil the
processor pinning constraint (e.g. the thread priority in the foreign
scheduler instance is undefined).
It would save me a lot of trouble if I could assume that EPOCH_LOCKED
is an exotic feature which is unlikely to get used in FreeBSD.

Another question, is it a common use case to call epoch_enter_preempt()
and epoch_exit_preempt() while owning a mutex?

Yes. Very. It is generally not permitted to hold a mutex across
epoch_wait() that's why there's the special flag EPOCH_LOCKED. If you have
a very limited number of threads, you might want to have each thread have
its own record registered with the epoch. Then you wouldn't need the CPU
pinning. The pinning is just away of providing a limited number of records
to an unbounded number of threads.

Matt, could you add information about this in locking(9)?

it holds information on the interaction between various locking types
and it woudl apear this needs to be added to the mix.

Julian

Post by Matthew Macy
-M
_______________________________________________
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers

[Matthew Macy]

On Tue, Aug 21, 2018 at 11:34 PM Sebastian Huber <

Post by Sebastian Huber

Post by Jacques Fourie
On Tue, Aug 21, 2018 at 8:33 AM, Sebastian Huber
Hello,
I update currently a port of the FreeBSD network stack, etc. to
the real-time operating system RTEMS from the head version at
2017-04-04 to the head version of today. I noticed that some
read-write locks are replaced by a relatively new stuff called
EPOCH(9). Is there some background information available for this?
The man page is a bit vague and searching for something named
epoch on the internet is not really great. For example, what is
the motivation for this change? How is this related to
read-copy-update (RCU)?
--
Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
<

https://maps.google.com/?q=Dornierstr.+4,+D-82178+Puchheim,+Germany&entry=gmail&source=g

Post by Jacques Fourie
Phone : [phone]
Fax : [phone]
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
<https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>
To unsubscribe, send any mail to
http://concurrencykit.org/presentations/ebr.pdf
<http://concurrencykit.org/presentations/ebr.pdf>. The way I
understand it is that it is mostly used in place of read locks to
provide liveness guarantees without using atomics. Additional detail
is available in the commit messages. As an example see r333813 for
some performance data.

Thanks, for the reference. The "epoch reclamation" are good keywords to
find more information.
What is the right mailing list to ask questions about the epoch
implementation of the FreeBSD kernel?

-hackers is probably as good as any. Your questions are at a high enough
level that they might be appropriate for -arch.


To support this machinery in RTEMS is a bit difficult (in particular

Post by Sebastian Huber
EPOCH_LOCKED). Since RTEMS is supposed to be a real-time operating
system it supports only fixed-priority and job-level fixed priority
(EDF) schedulers. To allow some scaling to larger SMP systems it
supports clustered scheduling together with the mutual exclusion locking
protocols MrsP (http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf) and
OMIP (http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf). This makes
the thread pinning hard to implement (which is very easy to support in
FreeBSD). The locking protocols may temporarily move a thread which owns
a mutex to a foreign scheduler instance, e.g. a thread which wants to
obtain the mutex helps the owner to make progress if it was pre-empted
in its home scheduler instance. Due to a timeout of the helper the owner
may loose the right to execute in the foreign scheduler instance. This
would make it impossible to fulfil the processor pinning constraint
(e.g. the thread priority in the foreign scheduler instance is undefined).
It would save me a lot of trouble if I could assume that EPOCH_LOCKED is
an exotic feature which is unlikely to get used in FreeBSD.

EPOCH_LOCKED is something that one would only want to use in a fairly
narrow set of circumstances. The only place it's being discussed currently
is in pmap:

https://reviews.freebsd.org/D15983

There it would conceivably replace a global mutex that currently serializes
all munmap operations.

-M

[Konstantin Belousov]

Post by Matthew Macy
EPOCH_LOCKED is something that one would only want to use in a fairly
narrow set of circumstances. The only place it's being discussed currently
https://reviews.freebsd.org/D15983
There it would conceivably replace a global mutex that currently serializes
all munmap operations.

I have a scetchy design which keeps the current approach of waiting
for delayed invalidation in the pmap_remove_all()/pmap_remove_write(),
simultaneosly eliminating the global_invl_mtx mutex at all. There was
some discussion about epoch vs. fine-graining of the existing DI code,
relative to the moving the sleep time to pagedaemon threads.

I did not have time to work it out (yet) due to personal issues.

[Sebastian Huber]

Post by Sebastian Huber
Hello,
I update currently a port of the FreeBSD network stack, etc. to the
real-time operating system RTEMS from the head version at 2017-04-04
to the head version of today. I noticed that some read-write locks are
replaced by a relatively new stuff called EPOCH(9). Is there some
background information available for this? The man page is a bit vague
and searching for something named epoch on the internet is not really
great. For example, what is the motivation for this change? How is
this related to read-copy-update (RCU)?

We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Eugene Grosbein]

Post by Sebastian Huber
We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.

FreeBSD as virtualized uniprocessor guest should be supported at full scale,
as well as embedded applications using single core x86 and non-x86 CPUs.

Just my 2 cents.

[Sebastian Huber]

Post by Eugene Grosbein

Post by Sebastian Huber
We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.

FreeBSD as virtualized uniprocessor guest should be supported at full scale,
as well as embedded applications using single core x86 and non-x86 CPUs.

If something should be supported, then there must be also someone who
ensures that this is actually the case. I don't know the FreeBSD
community good enough to judge if there is sufficient
manpower/funding/interest for a well supported uni-processor FreeBSD.
From the commits it is clear that FreeBSD receives a lot of attention
from CDN providers such as Netflix and Limelight Networks. They probably
don't care about uni-processor system support at all. The use of
lock-free data structures (Concurrency Kit) and the epoch memory
reclamation are now a mandatory infrastructure. There is no FreeBSD
configuration option to avoid this.

The Concurrency Kit in sys/contrib/ck has no explicit support for the
FreeBSD RISC-V and MIPS architectures. So, I guess the fall-back
sys/contrib/ck/include/gcc/ck_pr.h is used. The atomic support in
sys/contrib/ck partially duplicates/extends the general atomic support
of the FreeBSD kernel ATOMIC(9). To me it is a bit unclear what will be
the future direction in the FreeBSD kernel with respect to lock-free
data structures.
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Hans Petter Selasky]

Post by Sebastian Huber

Post by Eugene Grosbein

Post by Sebastian Huber
We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.

FreeBSD as virtualized uniprocessor guest should be supported at full scale,
as well as embedded applications using single core x86 and non-x86 CPUs.

If something should be supported, then there must be also someone who
ensures that this is actually the case. I don't know the FreeBSD
community good enough to judge if there is sufficient
manpower/funding/interest for a well supported uni-processor FreeBSD.
From the commits it is clear that FreeBSD receives a lot of attention
from CDN providers such as Netflix and Limelight Networks. They probably
don't care about uni-processor system support at all. The use of
lock-free data structures (Concurrency Kit) and the epoch memory
reclamation are now a mandatory infrastructure. There is no FreeBSD
configuration option to avoid this.
The Concurrency Kit in sys/contrib/ck has no explicit support for the
FreeBSD RISC-V and MIPS architectures. So, I guess the fall-back
sys/contrib/ck/include/gcc/ck_pr.h is used. The atomic support in
sys/contrib/ck partially duplicates/extends the general atomic support
of the FreeBSD kernel ATOMIC(9). To me it is a bit unclear what will be
the future direction in the FreeBSD kernel with respect to lock-free
data structures.

Hi Sebastian,

Do you have something like critical_enter() to disable pre-emption in
your OS? If you don't need to support SMP, the CPU pinning in the EPOCH
can be replaced by a critial_enter() / critial_exit() pair.

--HPS

[Sebastian Huber]

Post by Hans Petter Selasky

Post by Sebastian Huber

Post by Eugene Grosbein

Post by Sebastian Huber
We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP
configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.

FreeBSD as virtualized uniprocessor guest should be supported at full scale,
as well as embedded applications using single core x86 and non-x86 CPUs.

If something should be supported, then there must be also someone who
ensures that this is actually the case. I don't know the FreeBSD
community good enough to judge if there is sufficient
manpower/funding/interest for a well supported uni-processor FreeBSD.
 From the commits it is clear that FreeBSD receives a lot of
attention from CDN providers such as Netflix and Limelight Networks.
They probably don't care about uni-processor system support at all.
The use of lock-free data structures (Concurrency Kit) and the epoch
memory reclamation are now a mandatory infrastructure. There is no
FreeBSD configuration option to avoid this.
The Concurrency Kit in sys/contrib/ck has no explicit support for the
FreeBSD RISC-V and MIPS architectures. So, I guess the fall-back
sys/contrib/ck/include/gcc/ck_pr.h is used. The atomic support in
sys/contrib/ck partially duplicates/extends the general atomic
support of the FreeBSD kernel ATOMIC(9). To me it is a bit unclear
what will be the future direction in the FreeBSD kernel with respect
to lock-free data structures.

Hi Sebastian,
Do you have something like critical_enter() to disable pre-emption in
your OS? If you don't need to support SMP, the CPU pinning in the
EPOCH can be replaced by a critial_enter() / critial_exit() pair.

Yes, RTEMS has a critical_enter() to disable pre-emption (you could also
disable interrupts as a brute force means).

You still have the lock-free data structure inside the critical section.
Currently, this is only ck_queue, so not a real problem. However, in
case some more advanced lock-less algorithms would appear with a bit of
spinning here and there, then this would need further adoptions for the
uni-processor system. Not all targets support C11 atomics in hardware,
some need libatomic (a GCC thing).
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Ian Lepore]

Post by Hans Petter Selasky

Post by Sebastian Huber
We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP 
configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.

FreeBSD as virtualized uniprocessor guest should be supported at 
full scale,
as well as embedded applications using single core x86 and non-x86 
CPUs.

If something should be supported, then there must be also someone who 
ensures that this is actually the case. I don't know the FreeBSD 
community good enough to judge if there is sufficient 
manpower/funding/interest for a well supported uni-processor FreeBSD. 
 From the commits it is clear that FreeBSD receives a lot of 
attention from CDN providers such as Netflix and Limelight Networks. 
They probably don't care about uni-processor system support at all. 
The use of lock-free data structures (Concurrency Kit) and the epoch 
memory reclamation are now a mandatory infrastructure. There is no 
FreeBSD configuration option to avoid this.
The Concurrency Kit in sys/contrib/ck has no explicit support for the 
FreeBSD RISC-V and MIPS architectures. So, I guess the fall-back 
sys/contrib/ck/include/gcc/ck_pr.h is used. The atomic support in 
sys/contrib/ck partially duplicates/extends the general atomic 
support of the FreeBSD kernel ATOMIC(9). To me it is a bit unclear 
what will be the future direction in the FreeBSD kernel with respect 
to lock-free data structures.

Hi Sebastian,
Do you have something like critical_enter() to disable pre-emption in 
your OS? If you don't need to support SMP, the CPU pinning in the 
EPOCH can be replaced by a critial_enter() / critial_exit() pair.

Yes, RTEMS has a critical_enter() to disable pre-emption (you could also 
disable interrupts as a brute force means).
You still have the lock-free data structure inside the critical section. 
Currently, this is only ck_queue, so not a real problem. However, in 
case some more advanced lock-less algorithms would appear with a bit of 
spinning here and there, then this would need further adoptions for the 
uni-processor system. Not all targets support C11 atomics in hardware, 
some need libatomic (a GCC thing).

Freebsd runs on many single-processor systems on all supported
architectures and that isn't going to change.

-- Ian

[Mark Johnston]

Post by Hans Petter Selasky

Post by Sebastian Huber

Post by Eugene Grosbein

Post by Sebastian Huber
We used the FreeBSD network stack also on low-end targets
(uni-processor) such as MCF548x ColdFire, Atmel SAM V71, SPARC LEON,
etc. in current production environments (not legacy systems). The
introduction of lock-free data structures (Concurrency Kit) and this
epoch memory reclamation makes little sense on these targets (at least
from my point of view). However, FreeBSD has still the SMP configuration
option (sys/conf/options) which suggests that SMP is optional. Is a
uni-processor system something which is considered by the FreeBSD
community as a thing worth supporting or can I expect that this is an
exotic environment which will get less and less well supported in the
future? I just need some guidance so that I can better plan for future
FreeBSD baseline updates.

FreeBSD as virtualized uniprocessor guest should be supported at full scale,
as well as embedded applications using single core x86 and non-x86 CPUs.

If something should be supported, then there must be also someone who
ensures that this is actually the case. I don't know the FreeBSD
community good enough to judge if there is sufficient
manpower/funding/interest for a well supported uni-processor FreeBSD.
From the commits it is clear that FreeBSD receives a lot of attention
from CDN providers such as Netflix and Limelight Networks. They probably
don't care about uni-processor system support at all. The use of
lock-free data structures (Concurrency Kit) and the epoch memory
reclamation are now a mandatory infrastructure. There is no FreeBSD
configuration option to avoid this.
The Concurrency Kit in sys/contrib/ck has no explicit support for the
FreeBSD RISC-V and MIPS architectures. So, I guess the fall-back
sys/contrib/ck/include/gcc/ck_pr.h is used. The atomic support in
sys/contrib/ck partially duplicates/extends the general atomic support
of the FreeBSD kernel ATOMIC(9). To me it is a bit unclear what will be
the future direction in the FreeBSD kernel with respect to lock-free
data structures.

Hi Sebastian,
Do you have something like critical_enter() to disable pre-emption in
your OS? If you don't need to support SMP, the CPU pinning in the EPOCH
can be replaced by a critial_enter() / critial_exit() pair.

Threads in preemptible epoch sections are allowed to acquire locks, so
critical_enter()/exit() isn't a suitable replacement for epoch sections.
I think a fallback implementation could be written without CK for the
!SMP case, but it would require some work.

[Sebastian Huber]

Hello,

I try currently to understand the epoch implementation in FreeBSD to
implement the API in RTEMS.

If I understood epoch_wait() correctly, then this function just busy
waits until all conditions are satisfied. This is all right, since all
other participants operate with thread dispatching disabled, so the time
can be only influenced by interrupts and actual work.

I have some questions to epoch_block_handler_preempt(). The caller of
epoch_wait_prempt() seems to depend on threads which are currently
blocked, so busy waiting is not a good idea. Some questions to the code:

/*
 * epoch_block_handler_preempt is a callback from the ck code when
another thread is
 * currently in an epoch section.
 */
static void
epoch_block_handler_preempt(struct ck_epoch *global __unused,
ck_epoch_record_t *cr,
    void *arg __unused)
{
    epoch_record_t record;
    struct thread *td, *owner, *curwaittd;
    struct epoch_thread *tdwait;
    struct turnstile *ts;
    struct lock_object *lock;
    int spincount, gen;
    int locksheld __unused;

    record = __containerof(cr, struct epoch_record, er_record);
    td = curthread;
    locksheld = td->td_locks;
    spincount = 0;
    counter_u64_add(block_count, 1);
    /*
     * We lost a race and there's no longer any threads
     * on the CPU in an epoch section.
     */
    if (TAILQ_EMPTY(&record->er_tdlist))
        return;

    if (record->er_cpuid != curcpu) {
        ...

### this seems clear

    }
    /*
     * Try to find a thread in an epoch section on this CPU
     * waiting on a turnstile. Otherwise find the lowest
     * priority thread (highest prio value) and drop our priority
     * to match to allow it to run.
     */
    TAILQ_FOREACH(tdwait, &record->er_tdlist, et_link) {
        /*
         * Propagate our priority to any other waiters to prevent us
         * from starving them. They will have their original priority
         * restore on exit from epoch_wait().
         */
        curwaittd = tdwait->et_td;
        if (!TD_IS_INHIBITED(curwaittd) && curwaittd->td_priority >
td->td_priority) {
            critical_enter();
            thread_unlock(td);
            thread_lock(curwaittd);

### could we accidentally lower the priority here?

            sched_prio(curwaittd, td->td_priority);
            thread_unlock(curwaittd);
            thread_lock(td);
            critical_exit();
        }
        if (TD_IS_INHIBITED(curwaittd) && TD_ON_LOCK(curwaittd) &&
            ((ts = curwaittd->td_blocked) != NULL)) {
            ...

### is this some sort of condition variable which wakes us up together
with the waiting thread?

        }
    }

### is this a yield operation, e.g. in case we still the highest
priority thread, then we run immediately again?

    /*
     * We didn't find any threads actually blocked on a lock
     * so we have nothing to do except context switch away.
     */
    counter_u64_add(switch_count, 1);
    mi_switch(SW_VOL | SWT_RELINQUISH, NULL);

    /*
     * Release the thread lock while yielding to
     * allow other threads to acquire the lock
     * pointed to by TDQ_LOCKPTR(td). Else a
     * deadlock like situation might happen. (HPS)
     */
    thread_unlock(td);
    thread_lock(td);
}
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Sebastian Huber]

Hello,

I ported the epoch API to RTEMS. You can find the implementation here:

https://git.rtems.org/rtems-libbsd/tree/rtemsbsd/include/sys/epoch.h
https://git.rtems.org/rtems-libbsd/tree/rtemsbsd/rtems/rtems-kernel-epoch.c

I tested it also on low end uniprocessor targets and it works fine, e.g.

* Microchip ATSAM V71 (ARMv7-M)
* NXP MCF548x (ColdFire)
* NXP MPC860 (PowerPC 32-bit)

I tested it also on a 24-core T4240. It scales pretty well. See also:

https://git.rtems.org/rtems-libbsd/tree/testsuite/epoch01/test_main.c

If someone has ideas for good test cases, then please let me know.

I modified the CK a bit to better support RTEMS targets:

https://git.rtems.org/rtems-libbsd/commit/?id=baf1ca76290f43e054e5182c147ca332cb59890f
https://git.rtems.org/rtems-libbsd/commit/?id=3becda1fef854cbe39e462a1774b860e1455c8ef
https://git.rtems.org/rtems-libbsd/commit/?id=1af372a5eeaba3115f139e4efc0204e2cd7208bb
https://git.rtems.org/rtems-libbsd/commit/?id=be6515d2c1086c76ee965c6300cc5873c76afab9
--
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : [phone]
Fax : [phone]
E-Mail : ***@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[Will Andrews]

On Fri, Sep 21, 2018 at 5:47 AM Sebastian Huber <

Post by Sebastian Huber
https://git.rtems.org/rtems-libbsd/commit/?id=baf1ca76290f43e054e5182c147ca332cb59890f
https://git.rtems.org/rtems-libbsd/commit/?id=3becda1fef854cbe39e462a1774b860e1455c8ef
https://git.rtems.org/rtems-libbsd/commit/?id=1af372a5eeaba3115f139e4efc0204e2cd7208bb
https://git.rtems.org/rtems-libbsd/commit/?id=be6515d2c1086c76ee965c6300cc5873c76afab9

Hi,

You should open pull requests at http://github.com/concurrencykit/ck - the
maintainers routinely review and integrate.

--Will.