| No, that is long gone. (I am bad in archiving these exercises.) I also did some work in Alloy to create a formal specification of the class loading model but never really finished this. Alloy might provide a higher level language to specify these problems. I worked on the meta model (=OSGi spec) but I think one could express a concrete resolve situation quite easily as an Alloy model which would then be translated into a SAT _expression_. This approach might give some good insights how to effectively create a SAT _expression_ since Alloy seems a wizard in that.
I won’t have time to work on this but I will follow the results since it is an area that interests me.
Kind regards,
Peter Kriens
On 11/17/2016 8:54 AM, Peter Kriens
wrote:
I remember trying to map uses constraints to a boolean _expression_
but could not find any way that did not blow up the _expression_
size. This seemed very unfortunate because I think they can
actually be used to reduce the search space considerably.
I'm really happy to see that there is at least 3 people if not
more interested in the exercise of seeing how to encode uses
constraints to SAT. How do you guys want to get moving on this?
Peter, would you happen to still have what you had done?
From an API level I do not think there is a big
deal. The resolver could just fetch all resources at start. It
can of course only return a single solution. This might be
unfortunate but I find it hard to see why that is a limitation
since any solution that satisfies all requirements should be ok.
Kind regards,
Peter
Kriens
I
will be interested to see if you can
successfully map the OSGi uses concept into the SAT
solver p2 uses. I
briefly looked at that a long time ago when we were
refactoring the Equinox
framework (Luna) and were replacing the old Equinox
resolver. It
was far from obvious how you would achieve this. At
that time I opt'ed
to collaborate with a common resolver in Felix for the
Equinox framework.
But this is no magic implementation. There are still
cases
where the OSGi resolver algorithm will blow up. In
Equinox we try
to minimize that possibility by avoiding the
resolution of all (10000)
bundles at once. But as Pascal states, this does
leave out some possible
valid solutions that you will then not discover while
resolving.
If you do
focus on how to map uses into
the SAT solver in p2 I would be interested in
collaborating to see if such
a resolver would outperform the Felix resolver we use
at runtime. My
hope at the time I was looking into this was to map an
OSGi Resolver service
on top of the SAT solver implementation. But I cannot
remember how
the SAT solver is driven. I suspect the split between
the OSGI Resovler
and the OSGi ResolveContext will not fit well into the
SAT implementation
model.
Tom
From:
Todor
Boev <rinsvind@xxxxxxxxx>
To:
Equinox
development
mailing list <equinox-dev@xxxxxxxxxxx>
Date:
11/17/2016
02:22 AM
Subject:
Re:
[equinox-dev]
Convergence between p2 and the OSGi
resolver+repository
Sent by:
equinox-dev-bounces@xxxxxxxxxxx
- Regarding batch resolution:
Ultimately I think the batch
processing is about performance.
At provisioning time where finding the best solution
trumps speed the resolver
can be executed against the entire set. But I have to
try this. After than
the equinox runtime should be able to re-create a
correct (maybe not identical)
resolution from the much smaller set of resources. I
have tried the resolver
against about 700 bundles and it did okay, but this is
well short of 10,000.
More research required....some day.
- Regarding the additional p2
concepts:
Can you point me to the
documentation of how the resolution
problem is converted to a SAT formula?
Best regards
On Thu, Nov 17, 2016 at 6:20 AM,
Pascal Rapicault <pascal@xxxxxxxxxxxxx>
wrote:
On 11/16/2016 10:49 AM, Todor
Boev wrote:
- Regarding resolver behavior:
The goal is actually to
replace the behavior of
the objective function with the behavior of the
resolver. This is the best
way to guarantee that both p2 and the OSGi runtime
agree on what is a consistent
set of bundles. For example p2 does not take into
account package uses
constraints which leads to p2 selecting bundles that
later fail to resolve
at runtime. It does not matter which way to resolve is
better, so long
as they agree. Since the OSGi resolver is very
unlikely to change it falls
on p2 to match it's behavior. My current company
(software ag) has had
quite a number of issues where essentially p2 sets up
the resolver to fail.
- Regarding resolver
scalability:
The resolution is split
between the resolver which
processes the current set of resources and the
resolver context which selects
candidates when asked. If the goal is to support a
very high number of
candidates - a resolver context impl optimized for
searches in a large
candidate space can be provided. If the goal is to
produce a solution that
includes a very high number of resources - more
research is required. Even
if the initial set is 10,000 the resolver can be asked
to process them
not all at once, but incrementally in batches or even
one by one. Which
is in fact what equinox does today.
The thing is that if you
look at a
subset of the available bundles, you may find a
solution that is not the
optimal one. p2 will consider all the possible
candidates in one resolution
invocation.
I am trying to determine if it makes sense to invest
effort in prototyping
this given that subtle changes in behavior are in fact
a goal, rather than
an issue.
Even though on the surface
p2 resolver
looks similar to what the OSGi resolver does, p2 has
at least 2 additional
concepts:
1) the _expression_ of strict negation
2) the concept of patch
I'm tempted to think that it is probably simpler to
add support for the
uses-clause in p2 (this has been a known issue for
years, but I can't seem
to find the bug tonight) than it is to replace the
resolver completely
and get all the tests to pass. The encoding of
dependencies to a SAT formula
is well documented and so are the optimization
functions.
On Wed, Nov 16, 2016 at 4:44 AM,
Pascal Rapicault <pascal@xxxxxxxxxxxxx>
wrote:
On 11/15/2016 12:52 PM, Todor
Boev wrote:
Hello,
Are there any plans to bring
together p2 and OSGi resolver+repository
standards?
There is no immediate plan
for this.
It should be beneficial to have similar (maybe
identical?) dependency resolution
at provisioning time and later at runtime.
The install time and runtime
resolvers
resolve a slightly different problem because the
install time resolver
has to look for candidates in a large space, whereas
the runtime one has
to connect as many components together.
I have not tried replacing the p2 resolver with
the
new OSGi resolver so I can't tell how it would
perform.
Specifically:
- Is it possible to publish the
bundle generic capabilities/requirements
to the p2 repository?
Yes this should be possible.
The underlying
p2 capability / requirement model is really extensible
and the current
limitation is only the serialized format.
- Is it possible to use the
equinox Resolver inside the
p2 Planner?
It is possible to get
something going
but I'm not sure if this will scale (p2 resolver is
able to perform seamlessly
on 10's of thousands of IUs), nor if you will be able
to replicate the
subtleties that result from having an objective
function.
- Even if the equinox Resolver
can not be used is
it possible for p2 to handle generic
requirements/capabilities?
Yes. This should not be too
much work.
Regards,
Todor Boev
_______________________________________________
equinox-dev mailing list
equinox-dev@xxxxxxxxxxx
To change your delivery options, retrieve your
password, or unsubscribe
from this list, visit
https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________
equinox-dev
mailing list equinox-dev@xxxxxxxxxxxTo change your delivery options,
retrieve your password, or unsubscribe
from this list, visit https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________
equinox-dev mailing list
equinox-dev@xxxxxxxxxxx
To change your delivery options, retrieve your
password, or unsubscribe
from this list, visit
https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________
equinox-dev mailing list
equinox-dev@xxxxxxxxxxx
To change your delivery options, retrieve your
password, or unsubscribe
from this list, visit
https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________
equinox-dev mailing list
equinox-dev@xxxxxxxxxxx
To change your delivery options, retrieve your
password, or unsubscribe
from this list, visit
https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________
equinox-dev mailing list
equinox-dev@xxxxxxxxxxx
To change your delivery options, retrieve your password,
or unsubscribe from this list, visit
https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________
equinox-dev mailing list
equinox-dev@xxxxxxxxxxx
To change your delivery options, retrieve your password, or unsubscribe from this list, visit
https://dev.eclipse.org/mailman/listinfo/equinox-dev
_______________________________________________ equinox-dev mailing list equinox-dev@xxxxxxxxxxxTo change your delivery options, retrieve your password, or unsubscribe from this list, visit https://dev.eclipse.org/mailman/listinfo/equinox-dev
|
