You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@river.apache.org by Peter Firmstone <ji...@zeus.net.au> on 2009/11/01 09:47:31 UTC
Re: DynamicPolicyProvider concurrency
I'll commit an example implementation shortly called ConcurrentPermissions
Comments Inline below:
Gregg Wonderly wrote:
> Specifically I am talking about implies() vs add(). I contend that
> data races between internal state referred to by and set by
> (respectively) these two methods is a non-issue. Namely, the
> guarantees that "volatile" (which did not exist as a workable
> declaration when this code was written) provides are enough to allow
> DynamicPolicyProvider.DomainPermissions to have implies() and add()
> implementations that look like the following. This is a partial
> version of this class. Basically, I removed all use of synchronized
> (and the assert check in getPermissions() for Thread.holdsLock(this))
> and instead used copy-on-write and volatile to manage access to the
> values held in perms and grants.
>
> If add() and implies() are being used concurrently in a data race kind
> of way, then even synchronized() doesn't guarantee which version of
> the data will be visible at the moment the implies() is called because
> another thread doing add() may not be scheduled in a way to guarantee
> that it calls add() before implies() is called for example.
>
> private class DomainPermissions {
>
> private volatile PermissionCollection perms;
> private volatile List grants = new ArrayList();
>
> DomainPermissions(ProtectionDomain pd) {
> Principal[] pra;
> principals = (pd != null && (pra = pd.getPrincipals()).length
> > 0)
> ? new HashSet(Arrays.asList(pra)) : Collections.EMPTY_SET;
> perms = cacheBasePerms ? basePolicy.getPermissions(pd) : null;
> }
>
> void add(Permission[] pa) {
> List g = new ArrayList(grants);
> PermissionCollection pc = new Permissions();
> if( perms != null ) {
> Enumeration<Permission> e = perms.elements();
Looking at the source in java.security.permissions.java , the
perms.elements() method is a synchronized access to a HashMap that has
its elements returned in an iterator by two method calls,
permsMap.values().iterator() , this is still a synchronised access so
you'll not gain any performance advantage, but you'll be copying the
hashmap unneccessarily.
> while( e.hasMoreElements() ) {
> pc.add( e.nextElement() );
> }
There are synchronized accesses occurring here in underlying
implementations, however this operation isn't atomic, writes can occur
concurrently, one or more Permission objects might go missing if writes
occur concurrently to different PermissionCollection objects, where one
replaces the other.
> }
> for (int i = 0; i < pa.length; i++) {
> Permission p = pa[i];
> g.add(p);
> if (perms != null) {
> pc.add(p);
> }
> }
> grants = g;
> if( perms != null )
> perms = pc;
> }
> boolean implies(Permission p, ProtectionDomain domain) {
There is still synchronized access in the underlying Permissions object,
no increase in concurrency has been gained due to it's use of
synchronized access of HashMap.
> if (perms != null) {
> return perms.implies(p);
> }
> if (basePolicy.implies(domain, p)) {
> return true;
> }
> if (grants.isEmpty()) {
> return false;
> }
> return getPermissions(false, domain).implies(p);
> }
>
> }
>
> Gregg Wonderly
>
> Peter Firmstone wrote:
>> Ok, You'll have to forgive me, I'm not near the source code at the
>> moment, those last ideas appear useless, but I'll throw out some more
>> ideas, I could be wrong.
>>
>> I think the synchronisation problems stem from the java libraries.
>>
>> java.security.Policy - abstract class extended by
>> DynamicPolicyProvider, DynamicPolicyProvider appears to be a wrapper
>> class, it has a useful constructor:
>>
>> DynamicPolicyProvider(Policy basepolicy)
>>
>> The javadoc tends to indicate that you need a new implementation of
>> Policy that implements the DynamicProvider interface.
>>
>> You might also want to extend PermissionCollection which contains
>> Permission objects.
>>
>> Have a look at Doug Lea's concurrency utilities interest site:
>>
>> http://gee.cs.oswego.edu/dl/concurrency-interest/
>>
>> There are plenty of lock free strategies & code you can utilise. If
>> I get some time, I'll have a look on the weekend.
>>
>> Cheers,
>>
>> Peter.
>>
>>
>> Peter Firmstone wrote:
>>> Peter Firmstone wrote:
>>>> Gregg Wonderly wrote:
>>>>> Peter Firmstone wrote:
>>>>>> Gregg Wonderly wrote:
>>>>>>> I have been looking into some seemingly slow responses in
>>>>>>> several clients running simultaneously, and I see in some stack
>>>>>>> traces that there are synchronization points in
>>>>>>> DynamicPolicyProvider.implies() that seem to be heavily
>>>>>>> contended. We probably need to revisit this class and rewrite
>>>>>>> it to use copy on write mutation so that reads (the majority of
>>>>>>> activity) are completely uncontended.
>>>>>>>
>>>>>>> Any thoughts or experience with this issue?
>>>>>> This sounds like a job for
>>>>>> java.util.concurrent.ReentrantReadWriteLock! Da dat, da dat, da
>>>>>> dat, da da! Requires Java 5, works well, the javadoc is clear
>>>>>> too. Can you submit this as an issue on Jira?
>>>>>
>>>>> We don't actually want to lock, we just want to use a copy on
>>>>> write update strategy that does lock but set volatile references
>>>>> to the new contents.
>>> If you have multiple references containing object state, I'd suggest
>>> using an immutable wrapper object (no setters) containing implicit
>>> references to the objects, where it is read or replaced using a
>>> single AtomicReference. The problem you have then is whether the
>>> state your wrapping has visibility elsewhere or not, it is likely
>>> that these will all need to be created by using defensive copies in
>>> your constructor, each time you wish to update state.
>>>
>>>> In other words you want an AtomicReference, the objects being
>>>> de-referenced must be accessed by getting the referent for every
>>>> read, it also must not be published (an implicit reference allowed
>>>> to escape) after a read. When the AtomicReference is updated it is
>>>> guaranteed to be done atomically, however if the referent has
>>>> escaped, any escaped (implicit) references will still refer to the
>>>> old object. This isn't as easy as it sounds.
>>>>
>>>> Use the compareAndSet() method, in case another write occurs, if
>>>> the referent isn't the one expected (it just got updated), you can
>>>> retry it.
>>>>
>>>> I haven't had time to look into the details so can't comment on
>>>> whether this is appropriate or not. You might want to try this and
>>>> the ReentrantReadWriteLock and compare performance before
>>>> deciding. The contention write lock's cause might be negligible,
>>>> for code, much easier to protect, read and understand later on.
>>>>
>>>> Cheers,
>>>>
>>>> Peter.
>>>>>
>>>>> Gregg Wonderly
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>>
>
>
Re: DynamicPolicyProvider concurrency
Posted by Peter Firmstone <ji...@zeus.net.au>.
One point Brian makes about using synchronization is, not only writes to
mutable state need to be protected by synchronization, but reads do as
well, it has something to do with the JVM's internal memory
implementation. I don't understand it exactly, I just follow the advise.
More comments inline below.
Gregg Wonderly wrote:
> The concurrency model is about happens before relationships, and
> volatile makes that happen without locking. Volatile is a fine
> replacement for locking for anything that can be done atomically by a
> single assignment. Changing a reference to volatile and removing
> synchronization is not the only answer.
>
> If add() is being called from multiple threads simulataneously, then
> you need to be able to construct a composite value of all concurrent
> calls. That does become harder for add() with just volatile. I did
> not synchronize add() in what I showed on the list, but I have done
> that since I posted.
>
> You are right that this is not an easy thing. Performant concurrency
> is even harder. But we need to focus on keeping things "correct", and
> I think your analysis indicates a problem which is exposed by the
> removal of synchronized() which was counted on to provide the
> "happens-before" relationship for multi-threaded access.
>
> Any mutating reference that is seen by multiple threads, needs to
> either be final, volatile, or accessed within a synchronized() block.
> Synchronized seem fine for things like
>
> public sycnhronized Permission getPermission() {
> return p;
> }
>
> but this kind of usage can also be better done with volatile so that
> reads are not contending for a single lock.
This is where things get difficult, it's important to distinguish
between the reference to the object and the object itself, volatile only
guarantees memory visibility of the reference when it changes, if the
object itself has mutable state, the volatile reference won't help
control the underlying state.
In your example method above, Permission p is immutable, so using
volatile is a good solution.
Unfortunately the current implementation wont support this. The mutable
state were trying to protect is in nested PermissionCollection objects
PermissionCollection.add(Permission).
The "Permissions" class (not Permission) extends PermissionCollection,
but also contains its own PermissionCollection implementation (called
PermissionHash) and Permission classes are free to implement their own
PermissionCollection's returned by the
Permission.getPermissionCollection() factory method. Permissions can
contain any PermissionCollection or combination of PermissionCollection
types.
It helps me to think of it as a potential sequence of events like this:
1. Multiple objects are reading the state of the underlying
Permission object, accessed through a volatile reference to a
PermissionCollection instance.
2. In order to replace the PermissionCollection object we must know
it's current state, add(Permission p), then update it's volatile
reference.
3. Unfortunately step 2 opens the door for more more than one foreign
object to be modifying the state of the PermissionCollection
instance, at the same time. Then we end up with two different
copies of what the PermissionCollection object state is supposed
to be.
4. Only one of those objects will survive the reference update.
Which one? It simply means we've lost a Permission.
Using an AtomicReference instead of volatile implicit references for
mutable objects allow operations that check the object about to be
replaced hasn't changed by another thread in the interim, you can abort
and retry if it has. - Protection for the copy on write, so Permission
object's aren't lost
.
> That's what I'm after with my changes. I don't care how complex or
> how much locking add() has. implies() needs to be lockless as best as
> we can make it so.
>
>
> In my desktop ServiceUI client, at service discovery, when it is first
> launched, there are 10's of thousands of calls to implies just to
> arrive at a steady state of showing what services were discovered.
> Those calls proceed in lock step, non-concurrently, and result in
> serial code downloading and all kinds of funneling of execution.
In my implementation of ConcurrentPermissions I could achieve this by
creating a default implementation of PermissionCollection that utilises
a ReentrantReadWriteLock allowing multiple concurrent reads in between
write locks. In doing so however I'd have to create a marker interface,
so 3rd parties could utilise it too, probably called
ConcurrentPermissionCollection that checked if the underlying
PermissionCollection supported concurrent threads, falling back to
Synchronized access if not.
I could also create a wrapper PermissionCollection that encapsulates the
implementation returned from Permission.getPermissionCollection() using
ReadWriteLocks on each method. The biggest problem; I cannot predict at
runtime what other methods that implementation has outside of the
abstract PermissionCollection class's interface that also need to be
wrapped.
Due to the difficulty involved and probably my own limitations, I don't
want to write concurrent code that is low level and complex, I'd like to
utilise new concurrent libraries, to make the job easier.
It also means I'll benefit when the big guns optimise the JVM or revise
the libraries.
If you need more concurrency, let me know, there's still room left for
improvement. Before I do that though, I'm going to track down the newly
discovered concurrency bugs in the existing River PermissionCollection
implementations.
I've replaced most instances of Permissions in River with
ConcurrentPermissions in my patch for testing.
BR,
Peter.
>
> On the server side, I have a 6 machine application that uses
> transactions across all machines with about 18 participants. The
> implies calls that are flying through all the machines in a mesh
> execution pattern slow things down tremendously it seems, as a single
> ^\ thread dump had 6-10 threads waiting to lock on entry to implies().
>
> Gregg Wonderly
>
> Peter Firmstone wrote:
>> I've uploaded an implementation of what I think your were after, still
>> contains locking, it just increases the level of concurrency from single
>> threaded to multi threads probably about 16. This does have the side
>> effect of bringing out some concurrency bugs in existing code.
>>
>> I seem to have put you on the defensive, maybe I came off sounding too
>> critical, it is very important to get concurrency right though,
>> debugging's even harder. I could use some help here, someone writing a
>> book for debugging concurrent programmes?
>>
>> volatile references can't replace atomic operations or synchronization,
>> unless your working with immutable objects or primitives (with the
>> exception of long). Doing so risks loosing state / object data.
>>
>> It's worth getting a copy of Java Concurrency in Practise, I did, worth
>> it's weight in gold! There are many bad habits (good one's too
>> hopefully) we've all developed over the years, or iffy performance
>> optimisations, it can be difficult to de-programme one's mind, to
>> unlearn things, unfortunately just because someone else does something
>> that worked in the past doesn't mean it will continue to do so once
>> code is utilised in concurrent manner. One thing that stands out in
>> my mind, concurrent programming, done properly is very difficult, even
>> for the best programmers. It took 6 authors to write that book!
>>
>> Hope you like my example, it's based on what I've learnt from Brian's
>> and Josh's books among others. No one person can know everything
>> about Java, it's just getting too large, we've all got our strengths &
>> weaknesses, I've gained value from your comments in the past and am
>> glad we've got someone with your experience on the list.
>>
>> N.B. I chose encapsulation over inheritance.
>>
>> Cheers,
>>
>> Peter.
>>
>> Gregg Wonderly wrote:
>>> The primary issue peter is that only the "ready synchronization per
>>> element" is occuring, not a lock the entire time that "implies()" is
>>> being invoked. That is a reduction in the opportunity for the locks
>>> to be occuring together. Yes on a concurrent access, they will
>>> compete for access.
>>>
>>> Your comments include thoughts about competing modifications of the
>>> list of permissions as it is changed. These are immaterial. If
>>> there are permission adds being sprinked in amongst calls to
>>> implies(), then nothing will guarantee a view of the "correct" set
>>> of permissions except by changing to software to create the proper
>>> time sequencing so that all the add()s occur before any implies().
>>>
>>> Looking forward to your example. My goal was to reduce the global
>>> nature of the lock, not remove locking because as you see, there is
>>> still underlying locks being asserted by software that I don't want
>>> to change/replace.
>>>
>>> Gregg Wonderly
>>>
>>> On Nov 1, 2009, at 2:47 AM, Peter Firmstone wrote:
>>>
>>>> I'll commit an example implementation shortly called
>>>> ConcurrentPermissions
>>>>
>>>> Comments Inline below:
>>>>
>>>> Gregg Wonderly wrote:
>>>>> Specifically I am talking about implies() vs add(). I contend
>>>>> that data races between internal state referred to by and set by
>>>>> (respectively) these two methods is a non-issue. Namely, the
>>>>> guarantees that "volatile" (which did not exist as a workable
>>>>> declaration when this code was written) provides are enough to
>>>>> allow DynamicPolicyProvider.DomainPermissions to have implies()
>>>>> and add() implementations that look like the following. This is a
>>>>> partial version of this class. Basically, I removed all use of
>>>>> synchronized (and the assert check in getPermissions() for
>>>>> Thread.holdsLock(this)) and instead used copy-on-write and
>>>>> volatile to manage access to the values held in perms and grants.
>>>>>
>>>>> If add() and implies() are being used concurrently in a data race
>>>>> kind of way, then even synchronized() doesn't guarantee which
>>>>> version of the data will be visible at the moment the implies() is
>>>>> called because another thread doing add() may not be scheduled in
>>>>> a way to guarantee that it calls add() before implies() is called
>>>>> for example.
>>>>>
>>>>> private class DomainPermissions {
>>>>>
>>>>> private volatile PermissionCollection perms;
>>>>> private volatile List grants = new ArrayList();
>>>>>
>>>>> DomainPermissions(ProtectionDomain pd) {
>>>>> Principal[] pra;
>>>>> principals = (pd != null && (pra =
>>>>> pd.getPrincipals()).length > 0)
>>>>> ? new HashSet(Arrays.asList(pra)) : Collections.EMPTY_SET;
>>>>> perms = cacheBasePerms ? basePolicy.getPermissions(pd) : null;
>>>>> }
>>>>>
>>>>> void add(Permission[] pa) {
>>>>> List g = new ArrayList(grants);
>>>>> PermissionCollection pc = new Permissions();
>>>>> if( perms != null ) {
>>>>> Enumeration<Permission> e = perms.elements();
>>>> Looking at the source in java.security.permissions.java , the
>>>> perms.elements() method is a synchronized access to a HashMap that
>>>> has its elements returned in an iterator by two method calls,
>>>> permsMap.values().iterator() , this is still a synchronised access
>>>> so you'll not gain any performance advantage, but you'll be
>>>> copying the hashmap unneccessarily.
>>>>
>>>>
>>>>> while( e.hasMoreElements() ) {
>>>>> pc.add( e.nextElement() );
>>>>> }
>>>> There are synchronized accesses occurring here in underlying
>>>> implementations, however this operation isn't atomic, writes can
>>>> occur concurrently, one or more Permission objects might go missing
>>>> if writes occur concurrently to different PermissionCollection
>>>> objects, where one replaces the other.
>>>>> }
>>>>> for (int i = 0; i < pa.length; i++) {
>>>>> Permission p = pa[i];
>>>>> g.add(p);
>>>>> if (perms != null) {
>>>>> pc.add(p);
>>>>> }
>>>>> }
>>>>> grants = g;
>>>>> if( perms != null )
>>>>> perms = pc;
>>>>> }
>>>>> boolean implies(Permission p, ProtectionDomain domain) {
>>>> There is still synchronized access in the underlying Permissions
>>>> object, no increase in concurrency has been gained due to it's use
>>>> of synchronized access of HashMap.
>>>>
>>>>> if (perms != null) {
>>>>> return perms.implies(p);
>>>>> }
>>>>> if (basePolicy.implies(domain, p)) {
>>>>> return true;
>>>>> }
>>>>> if (grants.isEmpty()) {
>>>>> return false;
>>>>> }
>>>>> return getPermissions(false, domain).implies(p);
>>>>> }
>>>>>
>>>>> }
>>>>>
>>>>> Gregg Wonderly
>>>>>
>>>>> Peter Firmstone wrote:
>>>>>> Ok, You'll have to forgive me, I'm not near the source code at
>>>>>> the moment, those last ideas appear useless, but I'll throw out
>>>>>> some more ideas, I could be wrong.
>>>>>>
>>>>>> I think the synchronisation problems stem from the java libraries.
>>>>>>
>>>>>> java.security.Policy - abstract class extended by
>>>>>> DynamicPolicyProvider, DynamicPolicyProvider appears to be a
>>>>>> wrapper class, it has a useful constructor:
>>>>>>
>>>>>> DynamicPolicyProvider(Policy basepolicy)
>>>>>>
>>>>>> The javadoc tends to indicate that you need a new implementation
>>>>>> of Policy that implements the DynamicProvider interface.
>>>>>>
>>>>>> You might also want to extend PermissionCollection which contains
>>>>>> Permission objects.
>>>>>>
>>>>>> Have a look at Doug Lea's concurrency utilities interest site:
>>>>>>
>>>>>> http://gee.cs.oswego.edu/dl/concurrency-interest/
>>>>>>
>>>>>> There are plenty of lock free strategies & code you can utilise.
>>>>>> If I get some time, I'll have a look on the weekend.
>>>>>>
>>>>>> Cheers,
>>>>>>
>>>>>> Peter.
>>>>>>
>>>>>>
>>>>>> Peter Firmstone wrote:
>>>>>>> Peter Firmstone wrote:
>>>>>>>> Gregg Wonderly wrote:
>>>>>>>>> Peter Firmstone wrote:
>>>>>>>>>> Gregg Wonderly wrote:
>>>>>>>>>>> I have been looking into some seemingly slow responses in
>>>>>>>>>>> several clients running simultaneously, and I see in some
>>>>>>>>>>> stack traces that there are synchronization points in
>>>>>>>>>>> DynamicPolicyProvider.implies() that seem to be heavily
>>>>>>>>>>> contended. We probably need to revisit this class and
>>>>>>>>>>> rewrite it to use copy on write mutation so that reads (the
>>>>>>>>>>> majority of activity) are completely uncontended.
>>>>>>>>>>>
>>>>>>>>>>> Any thoughts or experience with this issue?
>>>>>>>>>> This sounds like a job for
>>>>>>>>>> java.util.concurrent.ReentrantReadWriteLock! Da dat, da dat,
>>>>>>>>>> da dat, da da! Requires Java 5, works well, the javadoc is
>>>>>>>>>> clear too. Can you submit this as an issue on Jira?
>>>>>>>>>
>>>>>>>>> We don't actually want to lock, we just want to use a copy on
>>>>>>>>> write update strategy that does lock but set volatile
>>>>>>>>> references to the new contents.
>>>>>>> If you have multiple references containing object state, I'd
>>>>>>> suggest using an immutable wrapper object (no setters)
>>>>>>> containing implicit references to the objects, where it is read
>>>>>>> or replaced using a single AtomicReference. The problem you
>>>>>>> have then is whether the state your wrapping has visibility
>>>>>>> elsewhere or not, it is likely that these will all need to be
>>>>>>> created by using defensive copies in your constructor, each time
>>>>>>> you wish to update state.
>>>>>>>
>>>>>>>> In other words you want an AtomicReference, the objects being
>>>>>>>> de-referenced must be accessed by getting the referent for
>>>>>>>> every read, it also must not be published (an implicit
>>>>>>>> reference allowed to escape) after a read. When the
>>>>>>>> AtomicReference is updated it is guaranteed to be done
>>>>>>>> atomically, however if the referent has escaped, any escaped
>>>>>>>> (implicit) references will still refer to the old object. This
>>>>>>>> isn't as easy as it sounds.
>>>>>>>>
>>>>>>>> Use the compareAndSet() method, in case another write occurs,
>>>>>>>> if the referent isn't the one expected (it just got updated),
>>>>>>>> you can retry it.
>>>>>>>>
>>>>>>>> I haven't had time to look into the details so can't comment on
>>>>>>>> whether this is appropriate or not. You might want to try this
>>>>>>>> and the ReentrantReadWriteLock and compare performance before
>>>>>>>> deciding. The contention write lock's cause might be
>>>>>>>> negligible, for code, much easier to protect, read and
>>>>>>>> understand later on.
>>>>>>>>
>>>>>>>> Cheers,
>>>>>>>>
>>>>>>>> Peter.
>>>>>>>>>
>>>>>>>>> Gregg Wonderly
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>
>>>
>>>
>>
>>
>>
>>
>
>
Re: DynamicPolicyProvider concurrency
Posted by Gregg Wonderly <ge...@cox.net>.
The concurrency model is about happens before relationships, and volatile makes
that happen without locking. Volatile is a fine replacement for locking for
anything that can be done atomically by a single assignment. Changing a
reference to volatile and removing synchronization is not the only answer.
If add() is being called from multiple threads simulataneously, then you need to
be able to construct a composite value of all concurrent calls. That does
become harder for add() with just volatile. I did not synchronize add() in what
I showed on the list, but I have done that since I posted.
You are right that this is not an easy thing. Performant concurrency is even
harder. But we need to focus on keeping things "correct", and I think your
analysis indicates a problem which is exposed by the removal of synchronized()
which was counted on to provide the "happens-before" relationship for
multi-threaded access.
Any mutating reference that is seen by multiple threads, needs to either be
final, volatile, or accessed within a synchronized() block. Synchronized seem
fine for things like
public sycnhronized Permission getPermission() {
return p;
}
but this kind of usage can also be better done with volatile so that reads are
not contending for a single lock. That's what I'm after with my changes. I
don't care how complex or how much locking add() has. implies() needs to be
lockless as best as we can make it so.
In my desktop ServiceUI client, at service discovery, when it is first launched,
there are 10's of thousands of calls to implies just to arrive at a steady state
of showing what services were discovered. Those calls proceed in lock step,
non-concurrently, and result in serial code downloading and all kinds of
funneling of execution.
On the server side, I have a 6 machine application that uses transactions across
all machines with about 18 participants. The implies calls that are flying
through all the machines in a mesh execution pattern slow things down
tremendously it seems, as a single ^\ thread dump had 6-10 threads waiting to
lock on entry to implies().
Gregg Wonderly
Peter Firmstone wrote:
> I've uploaded an implementation of what I think your were after, still
> contains locking, it just increases the level of concurrency from single
> threaded to multi threads probably about 16. This does have the side
> effect of bringing out some concurrency bugs in existing code.
>
> I seem to have put you on the defensive, maybe I came off sounding too
> critical, it is very important to get concurrency right though,
> debugging's even harder. I could use some help here, someone writing a
> book for debugging concurrent programmes?
>
> volatile references can't replace atomic operations or synchronization,
> unless your working with immutable objects or primitives (with the
> exception of long). Doing so risks loosing state / object data.
>
> It's worth getting a copy of Java Concurrency in Practise, I did, worth
> it's weight in gold! There are many bad habits (good one's too
> hopefully) we've all developed over the years, or iffy performance
> optimisations, it can be difficult to de-programme one's mind, to
> unlearn things, unfortunately just because someone else does something
> that worked in the past doesn't mean it will continue to do so once
> code is utilised in concurrent manner. One thing that stands out in
> my mind, concurrent programming, done properly is very difficult, even
> for the best programmers. It took 6 authors to write that book!
>
> Hope you like my example, it's based on what I've learnt from Brian's
> and Josh's books among others. No one person can know everything
> about Java, it's just getting too large, we've all got our strengths &
> weaknesses, I've gained value from your comments in the past and am
> glad we've got someone with your experience on the list.
>
> N.B. I chose encapsulation over inheritance.
>
> Cheers,
>
> Peter.
>
> Gregg Wonderly wrote:
>> The primary issue peter is that only the "ready synchronization per
>> element" is occuring, not a lock the entire time that "implies()" is
>> being invoked. That is a reduction in the opportunity for the locks
>> to be occuring together. Yes on a concurrent access, they will
>> compete for access.
>>
>> Your comments include thoughts about competing modifications of the
>> list of permissions as it is changed. These are immaterial. If there
>> are permission adds being sprinked in amongst calls to implies(), then
>> nothing will guarantee a view of the "correct" set of permissions
>> except by changing to software to create the proper time sequencing so
>> that all the add()s occur before any implies().
>>
>> Looking forward to your example. My goal was to reduce the global
>> nature of the lock, not remove locking because as you see, there is
>> still underlying locks being asserted by software that I don't want to
>> change/replace.
>>
>> Gregg Wonderly
>>
>> On Nov 1, 2009, at 2:47 AM, Peter Firmstone wrote:
>>
>>> I'll commit an example implementation shortly called
>>> ConcurrentPermissions
>>>
>>> Comments Inline below:
>>>
>>> Gregg Wonderly wrote:
>>>> Specifically I am talking about implies() vs add(). I contend that
>>>> data races between internal state referred to by and set by
>>>> (respectively) these two methods is a non-issue. Namely, the
>>>> guarantees that "volatile" (which did not exist as a workable
>>>> declaration when this code was written) provides are enough to allow
>>>> DynamicPolicyProvider.DomainPermissions to have implies() and add()
>>>> implementations that look like the following. This is a partial
>>>> version of this class. Basically, I removed all use of synchronized
>>>> (and the assert check in getPermissions() for
>>>> Thread.holdsLock(this)) and instead used copy-on-write and volatile
>>>> to manage access to the values held in perms and grants.
>>>>
>>>> If add() and implies() are being used concurrently in a data race
>>>> kind of way, then even synchronized() doesn't guarantee which
>>>> version of the data will be visible at the moment the implies() is
>>>> called because another thread doing add() may not be scheduled in a
>>>> way to guarantee that it calls add() before implies() is called for
>>>> example.
>>>>
>>>> private class DomainPermissions {
>>>>
>>>> private volatile PermissionCollection perms;
>>>> private volatile List grants = new ArrayList();
>>>>
>>>> DomainPermissions(ProtectionDomain pd) {
>>>> Principal[] pra;
>>>> principals = (pd != null && (pra = pd.getPrincipals()).length
>>>> > 0)
>>>> ? new HashSet(Arrays.asList(pra)) : Collections.EMPTY_SET;
>>>> perms = cacheBasePerms ? basePolicy.getPermissions(pd) : null;
>>>> }
>>>>
>>>> void add(Permission[] pa) {
>>>> List g = new ArrayList(grants);
>>>> PermissionCollection pc = new Permissions();
>>>> if( perms != null ) {
>>>> Enumeration<Permission> e = perms.elements();
>>> Looking at the source in java.security.permissions.java , the
>>> perms.elements() method is a synchronized access to a HashMap that
>>> has its elements returned in an iterator by two method calls,
>>> permsMap.values().iterator() , this is still a synchronised access so
>>> you'll not gain any performance advantage, but you'll be copying the
>>> hashmap unneccessarily.
>>>
>>>
>>>> while( e.hasMoreElements() ) {
>>>> pc.add( e.nextElement() );
>>>> }
>>> There are synchronized accesses occurring here in underlying
>>> implementations, however this operation isn't atomic, writes can
>>> occur concurrently, one or more Permission objects might go missing
>>> if writes occur concurrently to different PermissionCollection
>>> objects, where one replaces the other.
>>>> }
>>>> for (int i = 0; i < pa.length; i++) {
>>>> Permission p = pa[i];
>>>> g.add(p);
>>>> if (perms != null) {
>>>> pc.add(p);
>>>> }
>>>> }
>>>> grants = g;
>>>> if( perms != null )
>>>> perms = pc;
>>>> }
>>>> boolean implies(Permission p, ProtectionDomain domain) {
>>> There is still synchronized access in the underlying Permissions
>>> object, no increase in concurrency has been gained due to it's use of
>>> synchronized access of HashMap.
>>>
>>>> if (perms != null) {
>>>> return perms.implies(p);
>>>> }
>>>> if (basePolicy.implies(domain, p)) {
>>>> return true;
>>>> }
>>>> if (grants.isEmpty()) {
>>>> return false;
>>>> }
>>>> return getPermissions(false, domain).implies(p);
>>>> }
>>>>
>>>> }
>>>>
>>>> Gregg Wonderly
>>>>
>>>> Peter Firmstone wrote:
>>>>> Ok, You'll have to forgive me, I'm not near the source code at the
>>>>> moment, those last ideas appear useless, but I'll throw out some
>>>>> more ideas, I could be wrong.
>>>>>
>>>>> I think the synchronisation problems stem from the java libraries.
>>>>>
>>>>> java.security.Policy - abstract class extended by
>>>>> DynamicPolicyProvider, DynamicPolicyProvider appears to be a
>>>>> wrapper class, it has a useful constructor:
>>>>>
>>>>> DynamicPolicyProvider(Policy basepolicy)
>>>>>
>>>>> The javadoc tends to indicate that you need a new implementation of
>>>>> Policy that implements the DynamicProvider interface.
>>>>>
>>>>> You might also want to extend PermissionCollection which contains
>>>>> Permission objects.
>>>>>
>>>>> Have a look at Doug Lea's concurrency utilities interest site:
>>>>>
>>>>> http://gee.cs.oswego.edu/dl/concurrency-interest/
>>>>>
>>>>> There are plenty of lock free strategies & code you can utilise.
>>>>> If I get some time, I'll have a look on the weekend.
>>>>>
>>>>> Cheers,
>>>>>
>>>>> Peter.
>>>>>
>>>>>
>>>>> Peter Firmstone wrote:
>>>>>> Peter Firmstone wrote:
>>>>>>> Gregg Wonderly wrote:
>>>>>>>> Peter Firmstone wrote:
>>>>>>>>> Gregg Wonderly wrote:
>>>>>>>>>> I have been looking into some seemingly slow responses in
>>>>>>>>>> several clients running simultaneously, and I see in some
>>>>>>>>>> stack traces that there are synchronization points in
>>>>>>>>>> DynamicPolicyProvider.implies() that seem to be heavily
>>>>>>>>>> contended. We probably need to revisit this class and rewrite
>>>>>>>>>> it to use copy on write mutation so that reads (the majority
>>>>>>>>>> of activity) are completely uncontended.
>>>>>>>>>>
>>>>>>>>>> Any thoughts or experience with this issue?
>>>>>>>>> This sounds like a job for
>>>>>>>>> java.util.concurrent.ReentrantReadWriteLock! Da dat, da dat,
>>>>>>>>> da dat, da da! Requires Java 5, works well, the javadoc is
>>>>>>>>> clear too. Can you submit this as an issue on Jira?
>>>>>>>>
>>>>>>>> We don't actually want to lock, we just want to use a copy on
>>>>>>>> write update strategy that does lock but set volatile references
>>>>>>>> to the new contents.
>>>>>> If you have multiple references containing object state, I'd
>>>>>> suggest using an immutable wrapper object (no setters) containing
>>>>>> implicit references to the objects, where it is read or replaced
>>>>>> using a single AtomicReference. The problem you have then is
>>>>>> whether the state your wrapping has visibility elsewhere or not,
>>>>>> it is likely that these will all need to be created by using
>>>>>> defensive copies in your constructor, each time you wish to update
>>>>>> state.
>>>>>>
>>>>>>> In other words you want an AtomicReference, the objects being
>>>>>>> de-referenced must be accessed by getting the referent for every
>>>>>>> read, it also must not be published (an implicit reference
>>>>>>> allowed to escape) after a read. When the AtomicReference is
>>>>>>> updated it is guaranteed to be done atomically, however if the
>>>>>>> referent has escaped, any escaped (implicit) references will
>>>>>>> still refer to the old object. This isn't as easy as it sounds.
>>>>>>>
>>>>>>> Use the compareAndSet() method, in case another write occurs, if
>>>>>>> the referent isn't the one expected (it just got updated), you
>>>>>>> can retry it.
>>>>>>>
>>>>>>> I haven't had time to look into the details so can't comment on
>>>>>>> whether this is appropriate or not. You might want to try this
>>>>>>> and the ReentrantReadWriteLock and compare performance before
>>>>>>> deciding. The contention write lock's cause might be negligible,
>>>>>>> for code, much easier to protect, read and understand later on.
>>>>>>>
>>>>>>> Cheers,
>>>>>>>
>>>>>>> Peter.
>>>>>>>>
>>>>>>>> Gregg Wonderly
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>
>>
>
>
>
>
Re: DynamicPolicyProvider concurrency
Posted by Peter Firmstone <ji...@zeus.net.au>.
I've uploaded an implementation of what I think your were after, still
contains locking, it just increases the level of concurrency from single
threaded to multi threads probably about 16. This does have the side
effect of bringing out some concurrency bugs in existing code.
I seem to have put you on the defensive, maybe I came off sounding too
critical, it is very important to get concurrency right though,
debugging's even harder. I could use some help here, someone writing a
book for debugging concurrent programmes?
volatile references can't replace atomic operations or synchronization,
unless your working with immutable objects or primitives (with the
exception of long). Doing so risks loosing state / object data.
It's worth getting a copy of Java Concurrency in Practise, I did, worth
it's weight in gold! There are many bad habits (good one's too
hopefully) we've all developed over the years, or iffy performance
optimisations, it can be difficult to de-programme one's mind, to
unlearn things, unfortunately just because someone else does something
that worked in the past doesn't mean it will continue to do so once
code is utilised in concurrent manner. One thing that stands out in
my mind, concurrent programming, done properly is very difficult, even
for the best programmers. It took 6 authors to write that book!
Hope you like my example, it's based on what I've learnt from Brian's
and Josh's books among others. No one person can know everything
about Java, it's just getting too large, we've all got our strengths &
weaknesses, I've gained value from your comments in the past and am
glad we've got someone with your experience on the list.
N.B. I chose encapsulation over inheritance.
Cheers,
Peter.
Gregg Wonderly wrote:
> The primary issue peter is that only the "ready synchronization per
> element" is occuring, not a lock the entire time that "implies()" is
> being invoked. That is a reduction in the opportunity for the locks
> to be occuring together. Yes on a concurrent access, they will
> compete for access.
>
> Your comments include thoughts about competing modifications of the
> list of permissions as it is changed. These are immaterial. If there
> are permission adds being sprinked in amongst calls to implies(), then
> nothing will guarantee a view of the "correct" set of permissions
> except by changing to software to create the proper time sequencing so
> that all the add()s occur before any implies().
>
> Looking forward to your example. My goal was to reduce the global
> nature of the lock, not remove locking because as you see, there is
> still underlying locks being asserted by software that I don't want to
> change/replace.
>
> Gregg Wonderly
>
> On Nov 1, 2009, at 2:47 AM, Peter Firmstone wrote:
>
>> I'll commit an example implementation shortly called
>> ConcurrentPermissions
>>
>> Comments Inline below:
>>
>> Gregg Wonderly wrote:
>>> Specifically I am talking about implies() vs add(). I contend that
>>> data races between internal state referred to by and set by
>>> (respectively) these two methods is a non-issue. Namely, the
>>> guarantees that "volatile" (which did not exist as a workable
>>> declaration when this code was written) provides are enough to allow
>>> DynamicPolicyProvider.DomainPermissions to have implies() and add()
>>> implementations that look like the following. This is a partial
>>> version of this class. Basically, I removed all use of synchronized
>>> (and the assert check in getPermissions() for
>>> Thread.holdsLock(this)) and instead used copy-on-write and volatile
>>> to manage access to the values held in perms and grants.
>>>
>>> If add() and implies() are being used concurrently in a data race
>>> kind of way, then even synchronized() doesn't guarantee which
>>> version of the data will be visible at the moment the implies() is
>>> called because another thread doing add() may not be scheduled in a
>>> way to guarantee that it calls add() before implies() is called for
>>> example.
>>>
>>> private class DomainPermissions {
>>>
>>> private volatile PermissionCollection perms;
>>> private volatile List grants = new ArrayList();
>>>
>>> DomainPermissions(ProtectionDomain pd) {
>>> Principal[] pra;
>>> principals = (pd != null && (pra = pd.getPrincipals()).length
>>> > 0)
>>> ? new HashSet(Arrays.asList(pra)) : Collections.EMPTY_SET;
>>> perms = cacheBasePerms ? basePolicy.getPermissions(pd) : null;
>>> }
>>>
>>> void add(Permission[] pa) {
>>> List g = new ArrayList(grants);
>>> PermissionCollection pc = new Permissions();
>>> if( perms != null ) {
>>> Enumeration<Permission> e = perms.elements();
>> Looking at the source in java.security.permissions.java , the
>> perms.elements() method is a synchronized access to a HashMap that
>> has its elements returned in an iterator by two method calls,
>> permsMap.values().iterator() , this is still a synchronised access so
>> you'll not gain any performance advantage, but you'll be copying the
>> hashmap unneccessarily.
>>
>>
>>> while( e.hasMoreElements() ) {
>>> pc.add( e.nextElement() );
>>> }
>> There are synchronized accesses occurring here in underlying
>> implementations, however this operation isn't atomic, writes can
>> occur concurrently, one or more Permission objects might go missing
>> if writes occur concurrently to different PermissionCollection
>> objects, where one replaces the other.
>>> }
>>> for (int i = 0; i < pa.length; i++) {
>>> Permission p = pa[i];
>>> g.add(p);
>>> if (perms != null) {
>>> pc.add(p);
>>> }
>>> }
>>> grants = g;
>>> if( perms != null )
>>> perms = pc;
>>> }
>>> boolean implies(Permission p, ProtectionDomain domain) {
>> There is still synchronized access in the underlying Permissions
>> object, no increase in concurrency has been gained due to it's use of
>> synchronized access of HashMap.
>>
>>> if (perms != null) {
>>> return perms.implies(p);
>>> }
>>> if (basePolicy.implies(domain, p)) {
>>> return true;
>>> }
>>> if (grants.isEmpty()) {
>>> return false;
>>> }
>>> return getPermissions(false, domain).implies(p);
>>> }
>>>
>>> }
>>>
>>> Gregg Wonderly
>>>
>>> Peter Firmstone wrote:
>>>> Ok, You'll have to forgive me, I'm not near the source code at the
>>>> moment, those last ideas appear useless, but I'll throw out some
>>>> more ideas, I could be wrong.
>>>>
>>>> I think the synchronisation problems stem from the java libraries.
>>>>
>>>> java.security.Policy - abstract class extended by
>>>> DynamicPolicyProvider, DynamicPolicyProvider appears to be a
>>>> wrapper class, it has a useful constructor:
>>>>
>>>> DynamicPolicyProvider(Policy basepolicy)
>>>>
>>>> The javadoc tends to indicate that you need a new implementation of
>>>> Policy that implements the DynamicProvider interface.
>>>>
>>>> You might also want to extend PermissionCollection which contains
>>>> Permission objects.
>>>>
>>>> Have a look at Doug Lea's concurrency utilities interest site:
>>>>
>>>> http://gee.cs.oswego.edu/dl/concurrency-interest/
>>>>
>>>> There are plenty of lock free strategies & code you can utilise.
>>>> If I get some time, I'll have a look on the weekend.
>>>>
>>>> Cheers,
>>>>
>>>> Peter.
>>>>
>>>>
>>>> Peter Firmstone wrote:
>>>>> Peter Firmstone wrote:
>>>>>> Gregg Wonderly wrote:
>>>>>>> Peter Firmstone wrote:
>>>>>>>> Gregg Wonderly wrote:
>>>>>>>>> I have been looking into some seemingly slow responses in
>>>>>>>>> several clients running simultaneously, and I see in some
>>>>>>>>> stack traces that there are synchronization points in
>>>>>>>>> DynamicPolicyProvider.implies() that seem to be heavily
>>>>>>>>> contended. We probably need to revisit this class and rewrite
>>>>>>>>> it to use copy on write mutation so that reads (the majority
>>>>>>>>> of activity) are completely uncontended.
>>>>>>>>>
>>>>>>>>> Any thoughts or experience with this issue?
>>>>>>>> This sounds like a job for
>>>>>>>> java.util.concurrent.ReentrantReadWriteLock! Da dat, da dat,
>>>>>>>> da dat, da da! Requires Java 5, works well, the javadoc is
>>>>>>>> clear too. Can you submit this as an issue on Jira?
>>>>>>>
>>>>>>> We don't actually want to lock, we just want to use a copy on
>>>>>>> write update strategy that does lock but set volatile references
>>>>>>> to the new contents.
>>>>> If you have multiple references containing object state, I'd
>>>>> suggest using an immutable wrapper object (no setters) containing
>>>>> implicit references to the objects, where it is read or replaced
>>>>> using a single AtomicReference. The problem you have then is
>>>>> whether the state your wrapping has visibility elsewhere or not,
>>>>> it is likely that these will all need to be created by using
>>>>> defensive copies in your constructor, each time you wish to update
>>>>> state.
>>>>>
>>>>>> In other words you want an AtomicReference, the objects being
>>>>>> de-referenced must be accessed by getting the referent for every
>>>>>> read, it also must not be published (an implicit reference
>>>>>> allowed to escape) after a read. When the AtomicReference is
>>>>>> updated it is guaranteed to be done atomically, however if the
>>>>>> referent has escaped, any escaped (implicit) references will
>>>>>> still refer to the old object. This isn't as easy as it sounds.
>>>>>>
>>>>>> Use the compareAndSet() method, in case another write occurs, if
>>>>>> the referent isn't the one expected (it just got updated), you
>>>>>> can retry it.
>>>>>>
>>>>>> I haven't had time to look into the details so can't comment on
>>>>>> whether this is appropriate or not. You might want to try this
>>>>>> and the ReentrantReadWriteLock and compare performance before
>>>>>> deciding. The contention write lock's cause might be negligible,
>>>>>> for code, much easier to protect, read and understand later on.
>>>>>>
>>>>>> Cheers,
>>>>>>
>>>>>> Peter.
>>>>>>>
>>>>>>> Gregg Wonderly
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>
>
>
Re: DynamicPolicyProvider concurrency
Posted by Peter Firmstone <ji...@zeus.net.au>.
I've uploaded an implementation of what I think your were after, still
contains locking, it just increases the level of concurrency from single
threaded to multi threads probably about 16. This does have the side
effect of bringing out some concurrency bugs in existing code.
I seem to have put you on the defensive, maybe I came off sounding too
critical, it is very important to get concurrency right though,
debugging's even harder. I could use some help here, someone writing a
book for debugging concurrent programmes?
volatile references can't replace atomic operations or synchronization,
unless your working with immutable objects or primitives (with the
exception of long). Doing so risks loosing state / object data.
It's worth getting a copy of Java Concurrency in Practise, I did, worth
it's weight in gold! There are many bad habits (good one's too
hopefully) we've all developed over the years, or iffy performance
optimisations, it can be difficult to de-programme one's mind, to
unlearn things, unfortunately just because someone else does something
that worked in the past doesn't mean it will continue to do so once
code is utilised in concurrent manner. One thing that stands out in
my mind, concurrent programming, done properly is very difficult, even
for the best programmers. It took 6 authors to write that book!
Hope you like my example, it's based on what I've learnt from Brian's
and Josh's books among others. No one person can know everything
about Java, it's just getting too large, we've all got our strengths &
weaknesses, I've gained value from your comments in the past and am
glad we've got someone with your experience on the list.
N.B. I chose encapsulation over inheritance.
Cheers,
Peter.
Gregg Wonderly wrote:
> The primary issue peter is that only the "ready synchronization per
> element" is occuring, not a lock the entire time that "implies()" is
> being invoked. That is a reduction in the opportunity for the locks
> to be occuring together. Yes on a concurrent access, they will
> compete for access.
>
> Your comments include thoughts about competing modifications of the
> list of permissions as it is changed. These are immaterial. If there
> are permission adds being sprinked in amongst calls to implies(), then
> nothing will guarantee a view of the "correct" set of permissions
> except by changing to software to create the proper time sequencing so
> that all the add()s occur before any implies().
>
> Looking forward to your example. My goal was to reduce the global
> nature of the lock, not remove locking because as you see, there is
> still underlying locks being asserted by software that I don't want to
> change/replace.
>
> Gregg Wonderly
>
> On Nov 1, 2009, at 2:47 AM, Peter Firmstone wrote:
>
>> I'll commit an example implementation shortly called
>> ConcurrentPermissions
>>
>> Comments Inline below:
>>
>> Gregg Wonderly wrote:
>>> Specifically I am talking about implies() vs add(). I contend that
>>> data races between internal state referred to by and set by
>>> (respectively) these two methods is a non-issue. Namely, the
>>> guarantees that "volatile" (which did not exist as a workable
>>> declaration when this code was written) provides are enough to allow
>>> DynamicPolicyProvider.DomainPermissions to have implies() and add()
>>> implementations that look like the following. This is a partial
>>> version of this class. Basically, I removed all use of synchronized
>>> (and the assert check in getPermissions() for
>>> Thread.holdsLock(this)) and instead used copy-on-write and volatile
>>> to manage access to the values held in perms and grants.
>>>
>>> If add() and implies() are being used concurrently in a data race
>>> kind of way, then even synchronized() doesn't guarantee which
>>> version of the data will be visible at the moment the implies() is
>>> called because another thread doing add() may not be scheduled in a
>>> way to guarantee that it calls add() before implies() is called for
>>> example.
>>>
>>> private class DomainPermissions {
>>>
>>> private volatile PermissionCollection perms;
>>> private volatile List grants = new ArrayList();
>>>
>>> DomainPermissions(ProtectionDomain pd) {
>>> Principal[] pra;
>>> principals = (pd != null && (pra = pd.getPrincipals()).length
>>> > 0)
>>> ? new HashSet(Arrays.asList(pra)) : Collections.EMPTY_SET;
>>> perms = cacheBasePerms ? basePolicy.getPermissions(pd) : null;
>>> }
>>>
>>> void add(Permission[] pa) {
>>> List g = new ArrayList(grants);
>>> PermissionCollection pc = new Permissions();
>>> if( perms != null ) {
>>> Enumeration<Permission> e = perms.elements();
>> Looking at the source in java.security.permissions.java , the
>> perms.elements() method is a synchronized access to a HashMap that
>> has its elements returned in an iterator by two method calls,
>> permsMap.values().iterator() , this is still a synchronised access so
>> you'll not gain any performance advantage, but you'll be copying the
>> hashmap unneccessarily.
>>
>>
>>> while( e.hasMoreElements() ) {
>>> pc.add( e.nextElement() );
>>> }
>> There are synchronized accesses occurring here in underlying
>> implementations, however this operation isn't atomic, writes can
>> occur concurrently, one or more Permission objects might go missing
>> if writes occur concurrently to different PermissionCollection
>> objects, where one replaces the other.
>>> }
>>> for (int i = 0; i < pa.length; i++) {
>>> Permission p = pa[i];
>>> g.add(p);
>>> if (perms != null) {
>>> pc.add(p);
>>> }
>>> }
>>> grants = g;
>>> if( perms != null )
>>> perms = pc;
>>> }
>>> boolean implies(Permission p, ProtectionDomain domain) {
>> There is still synchronized access in the underlying Permissions
>> object, no increase in concurrency has been gained due to it's use of
>> synchronized access of HashMap.
>>
>>> if (perms != null) {
>>> return perms.implies(p);
>>> }
>>> if (basePolicy.implies(domain, p)) {
>>> return true;
>>> }
>>> if (grants.isEmpty()) {
>>> return false;
>>> }
>>> return getPermissions(false, domain).implies(p);
>>> }
>>>
>>> }
>>>
>>> Gregg Wonderly
>>>
>>> Peter Firmstone wrote:
>>>> Ok, You'll have to forgive me, I'm not near the source code at the
>>>> moment, those last ideas appear useless, but I'll throw out some
>>>> more ideas, I could be wrong.
>>>>
>>>> I think the synchronisation problems stem from the java libraries.
>>>>
>>>> java.security.Policy - abstract class extended by
>>>> DynamicPolicyProvider, DynamicPolicyProvider appears to be a
>>>> wrapper class, it has a useful constructor:
>>>>
>>>> DynamicPolicyProvider(Policy basepolicy)
>>>>
>>>> The javadoc tends to indicate that you need a new implementation of
>>>> Policy that implements the DynamicProvider interface.
>>>>
>>>> You might also want to extend PermissionCollection which contains
>>>> Permission objects.
>>>>
>>>> Have a look at Doug Lea's concurrency utilities interest site:
>>>>
>>>> http://gee.cs.oswego.edu/dl/concurrency-interest/
>>>>
>>>> There are plenty of lock free strategies & code you can utilise.
>>>> If I get some time, I'll have a look on the weekend.
>>>>
>>>> Cheers,
>>>>
>>>> Peter.
>>>>
>>>>
>>>> Peter Firmstone wrote:
>>>>> Peter Firmstone wrote:
>>>>>> Gregg Wonderly wrote:
>>>>>>> Peter Firmstone wrote:
>>>>>>>> Gregg Wonderly wrote:
>>>>>>>>> I have been looking into some seemingly slow responses in
>>>>>>>>> several clients running simultaneously, and I see in some
>>>>>>>>> stack traces that there are synchronization points in
>>>>>>>>> DynamicPolicyProvider.implies() that seem to be heavily
>>>>>>>>> contended. We probably need to revisit this class and rewrite
>>>>>>>>> it to use copy on write mutation so that reads (the majority
>>>>>>>>> of activity) are completely uncontended.
>>>>>>>>>
>>>>>>>>> Any thoughts or experience with this issue?
>>>>>>>> This sounds like a job for
>>>>>>>> java.util.concurrent.ReentrantReadWriteLock! Da dat, da dat,
>>>>>>>> da dat, da da! Requires Java 5, works well, the javadoc is
>>>>>>>> clear too. Can you submit this as an issue on Jira?
>>>>>>>
>>>>>>> We don't actually want to lock, we just want to use a copy on
>>>>>>> write update strategy that does lock but set volatile references
>>>>>>> to the new contents.
>>>>> If you have multiple references containing object state, I'd
>>>>> suggest using an immutable wrapper object (no setters) containing
>>>>> implicit references to the objects, where it is read or replaced
>>>>> using a single AtomicReference. The problem you have then is
>>>>> whether the state your wrapping has visibility elsewhere or not,
>>>>> it is likely that these will all need to be created by using
>>>>> defensive copies in your constructor, each time you wish to update
>>>>> state.
>>>>>
>>>>>> In other words you want an AtomicReference, the objects being
>>>>>> de-referenced must be accessed by getting the referent for every
>>>>>> read, it also must not be published (an implicit reference
>>>>>> allowed to escape) after a read. When the AtomicReference is
>>>>>> updated it is guaranteed to be done atomically, however if the
>>>>>> referent has escaped, any escaped (implicit) references will
>>>>>> still refer to the old object. This isn't as easy as it sounds.
>>>>>>
>>>>>> Use the compareAndSet() method, in case another write occurs, if
>>>>>> the referent isn't the one expected (it just got updated), you
>>>>>> can retry it.
>>>>>>
>>>>>> I haven't had time to look into the details so can't comment on
>>>>>> whether this is appropriate or not. You might want to try this
>>>>>> and the ReentrantReadWriteLock and compare performance before
>>>>>> deciding. The contention write lock's cause might be negligible,
>>>>>> for code, much easier to protect, read and understand later on.
>>>>>>
>>>>>> Cheers,
>>>>>>
>>>>>> Peter.
>>>>>>>
>>>>>>> Gregg Wonderly
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>
>
>
Re: DynamicPolicyProvider concurrency
Posted by Gregg Wonderly <gr...@gmail.com>.
The primary issue peter is that only the "ready synchronization per
element" is occuring, not a lock the entire time that "implies()" is
being invoked. That is a reduction in the opportunity for the locks
to be occuring together. Yes on a concurrent access, they will
compete for access.
Your comments include thoughts about competing modifications of the
list of permissions as it is changed. These are immaterial. If there
are permission adds being sprinked in amongst calls to implies(), then
nothing will guarantee a view of the "correct" set of permissions
except by changing to software to create the proper time sequencing so
that all the add()s occur before any implies().
Looking forward to your example. My goal was to reduce the global
nature of the lock, not remove locking because as you see, there is
still underlying locks being asserted by software that I don't want to
change/replace.
Gregg Wonderly
On Nov 1, 2009, at 2:47 AM, Peter Firmstone wrote:
> I'll commit an example implementation shortly called
> ConcurrentPermissions
>
> Comments Inline below:
>
> Gregg Wonderly wrote:
>> Specifically I am talking about implies() vs add(). I contend that
>> data races between internal state referred to by and set by
>> (respectively) these two methods is a non-issue. Namely, the
>> guarantees that "volatile" (which did not exist as a workable
>> declaration when this code was written) provides are enough to
>> allow DynamicPolicyProvider.DomainPermissions to have implies() and
>> add() implementations that look like the following. This is a
>> partial version of this class. Basically, I removed all use of
>> synchronized (and the assert check in getPermissions() for
>> Thread.holdsLock(this)) and instead used copy-on-write and volatile
>> to manage access to the values held in perms and grants.
>>
>> If add() and implies() are being used concurrently in a data race
>> kind of way, then even synchronized() doesn't guarantee which
>> version of the data will be visible at the moment the implies() is
>> called because another thread doing add() may not be scheduled in a
>> way to guarantee that it calls add() before implies() is called for
>> example.
>>
>> private class DomainPermissions {
>>
>> private volatile PermissionCollection perms;
>> private volatile List grants = new ArrayList();
>>
>> DomainPermissions(ProtectionDomain pd) {
>> Principal[] pra;
>> principals = (pd != null && (pra = pd.getPrincipals
>> ()).length > 0)
>> ? new HashSet(Arrays.asList(pra)) : Collections.EMPTY_SET;
>> perms = cacheBasePerms ? basePolicy.getPermissions(pd) : null;
>> }
>>
>> void add(Permission[] pa) {
>> List g = new ArrayList(grants);
>> PermissionCollection pc = new Permissions();
>> if( perms != null ) {
>> Enumeration<Permission> e = perms.elements();
> Looking at the source in java.security.permissions.java , the
> perms.elements() method is a synchronized access to a HashMap that
> has its elements returned in an iterator by two method calls,
> permsMap.values().iterator() , this is still a synchronised access
> so you'll not gain any performance advantage, but you'll be copying
> the hashmap unneccessarily.
>
>
>> while( e.hasMoreElements() ) {
>> pc.add( e.nextElement() );
>> }
> There are synchronized accesses occurring here in underlying
> implementations, however this operation isn't atomic, writes can
> occur concurrently, one or more Permission objects might go missing
> if writes occur concurrently to different PermissionCollection
> objects, where one replaces the other.
>> }
>> for (int i = 0; i < pa.length; i++) {
>> Permission p = pa[i];
>> g.add(p);
>> if (perms != null) {
>> pc.add(p);
>> }
>> }
>> grants = g;
>> if( perms != null )
>> perms = pc;
>> }
>> boolean implies(Permission p, ProtectionDomain domain) {
> There is still synchronized access in the underlying Permissions
> object, no increase in concurrency has been gained due to it's use
> of synchronized access of HashMap.
>
>> if (perms != null) {
>> return perms.implies(p);
>> }
>> if (basePolicy.implies(domain, p)) {
>> return true;
>> }
>> if (grants.isEmpty()) {
>> return false;
>> }
>> return getPermissions(false, domain).implies(p);
>> }
>>
>> }
>>
>> Gregg Wonderly
>>
>> Peter Firmstone wrote:
>>> Ok, You'll have to forgive me, I'm not near the source code at
>>> the moment, those last ideas appear useless, but I'll throw out
>>> some more ideas, I could be wrong.
>>>
>>> I think the synchronisation problems stem from the java libraries.
>>>
>>> java.security.Policy - abstract class extended by
>>> DynamicPolicyProvider, DynamicPolicyProvider appears to be a
>>> wrapper class, it has a useful constructor:
>>>
>>> DynamicPolicyProvider(Policy basepolicy)
>>>
>>> The javadoc tends to indicate that you need a new implementation
>>> of Policy that implements the DynamicProvider interface.
>>>
>>> You might also want to extend PermissionCollection which contains
>>> Permission objects.
>>>
>>> Have a look at Doug Lea's concurrency utilities interest site:
>>>
>>> http://gee.cs.oswego.edu/dl/concurrency-interest/
>>>
>>> There are plenty of lock free strategies & code you can utilise.
>>> If I get some time, I'll have a look on the weekend.
>>>
>>> Cheers,
>>>
>>> Peter.
>>>
>>>
>>> Peter Firmstone wrote:
>>>> Peter Firmstone wrote:
>>>>> Gregg Wonderly wrote:
>>>>>> Peter Firmstone wrote:
>>>>>>> Gregg Wonderly wrote:
>>>>>>>> I have been looking into some seemingly slow responses in
>>>>>>>> several clients running simultaneously, and I see in some
>>>>>>>> stack traces that there are synchronization points in
>>>>>>>> DynamicPolicyProvider.implies() that seem to be heavily
>>>>>>>> contended. We probably need to revisit this class and
>>>>>>>> rewrite it to use copy on write mutation so that reads (the
>>>>>>>> majority of activity) are completely uncontended.
>>>>>>>>
>>>>>>>> Any thoughts or experience with this issue?
>>>>>>> This sounds like a job for
>>>>>>> java.util.concurrent.ReentrantReadWriteLock! Da dat, da dat,
>>>>>>> da dat, da da! Requires Java 5, works well, the javadoc is
>>>>>>> clear too. Can you submit this as an issue on Jira?
>>>>>>
>>>>>> We don't actually want to lock, we just want to use a copy on
>>>>>> write update strategy that does lock but set volatile
>>>>>> references to the new contents.
>>>> If you have multiple references containing object state, I'd
>>>> suggest using an immutable wrapper object (no setters) containing
>>>> implicit references to the objects, where it is read or replaced
>>>> using a single AtomicReference. The problem you have then is
>>>> whether the state your wrapping has visibility elsewhere or not,
>>>> it is likely that these will all need to be created by using
>>>> defensive copies in your constructor, each time you wish to
>>>> update state.
>>>>
>>>>> In other words you want an AtomicReference, the objects being de-
>>>>> referenced must be accessed by getting the referent for every
>>>>> read, it also must not be published (an implicit reference
>>>>> allowed to escape) after a read. When the AtomicReference is
>>>>> updated it is guaranteed to be done atomically, however if the
>>>>> referent has escaped, any escaped (implicit) references will
>>>>> still refer to the old object. This isn't as easy as it sounds.
>>>>>
>>>>> Use the compareAndSet() method, in case another write occurs, if
>>>>> the referent isn't the one expected (it just got updated), you
>>>>> can retry it.
>>>>>
>>>>> I haven't had time to look into the details so can't comment on
>>>>> whether this is appropriate or not. You might want to try this
>>>>> and the ReentrantReadWriteLock and compare performance before
>>>>> deciding. The contention write lock's cause might be
>>>>> negligible, for code, much easier to protect, read and
>>>>> understand later on.
>>>>>
>>>>> Cheers,
>>>>>
>>>>> Peter.
>>>>>>
>>>>>> Gregg Wonderly
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>>
>>
>>
>