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
