-LIBSOLV(3)
+Libsolv(3)
==========
:man manual: LIBSOLV
:man source: libsolv
-NAME
+
+Name
----
libsolv - package dependency solver library using a satisfiability algorithm
-HISTORY
--------
-This project was started in May 2007 when the zypp folks decided to switch
-to a database to speed up installation. As I am not a big fan of databases,
-I (mls) wondered if there would be really some merit of using one for solving,
-as package dependencies of all packages have to be read in anyway.
-
-Back in 2002, I researched that using a dictionary approach for storing
-dependencies can reduce the packages file to 1/3 of its size. Extending
-this idea a bit more, I decided to store all strings and relations
-as unique 32-bit numbers. This has three big advantages:
-
-- because of the unification, testing whether two strings are equal is the
- same as testing the equality of two numbers, thus very fast
-- much space is saved, as numbers do not take up as much space as strings
- the internal memory representation does not take more space on a
- 64-bit system where a pointer is twice the size of a 32-bit number
-Thus, the solv format was created, which stores a repository as a string
-dictionary, a relation dictionary and then all packages dependencies.
-Tests showed that reading and merging multiple solv repositories takes
-just some milliseconds.
+Documentation
+-------------
+The libsolv documentation is split into multiple parts:
-=== Early solver experiments ===
-Having a new repository format was one big step, but the other area
-where libzypp needed improvement was the solver. Libzypp's solver was
-a port from the Red Carpet solver, which was written to update packages
-in an already installed system. Using it for the complete installation
-progress brought it to its limits. Also, the added extensions like
-support for weak dependencies and patches made it fragile and
-unpredictable.
+*libsolv-history*::
+ how the libsolv library came into existence
-As I was not very pleased with the way the solver worked, I looked at
-other solver algorithms. I checked smart, yum and apt, but could not
-find a convincing algorithm. My own experiments also were not very
-convincing, they worked fine for some problems but failed miserably
-for other corner cases.
+*libsolv-constantids*::
+ fixed Ids for often used strings
-=== Using SAT for solving ===
-SUSE's hack week at the end of June 2007 turned out to be a turning point
-for the solver. Googling for solver algorithms, I stumbled over some note
-saying that some people are trying to use SAT algorithms to improve
-solving on Debian. Looking at the SAT entry in Wikipedia, it was easy
-to see that this indeed was the missing piece: SAT algorithms are well
-researched and there are quite some open source implementations.
-I decided to look at the minisat code, as it is one of the fastest
-solvers while consisting of too many lines of code.
+*libsolv-bindings*::
+ access libsolv from perl/python/ruby
-Of course, directly using minisat would not work, as a package solver
-does not need to find just one correct solution, but it also has to
-optimize some metrics, i.e. keep as many packages installed as possible.
-Thus, I needed to write my own solver incorporation the ideas and
-algorithms used in minisat. This wasn't very hard, and at the end of
-the hack week the solver calculated the first right solutions.
+*libsolv-pool*::
+ libsolv's pool object
-=== Selling it to libzypp ===
-With those encouraging results, I went to Klaus Kaempf, the system
-management architect at SUSE. We spoke about how to convince the
-team to make libzypp switch to the new solver. Fortunately, libzypp comes
-with a plethora of solver test cases, so we decided to make the solver pass
-most of the test cases first. Klaus wrote a "deptestomatic" implementation
-to check the test cases. Together with Stephan Kulow, who is responsible for the
-openSUSE distribution, we tweaked and extended the solver until most of
-the test cases looked good.
+Pointer Validity
+----------------
+Note that all pointers to objects that have an Id have only a limited
+validity period, with the exception of Repo pointers. There are only
+guaranteed to be valid until a new object of that type is added or an
+object of that type is removed. Thus pointers to Solvable objects are only
+valid until another solvable is created, because adding a Solvable may
+relocate the Pool's Solvable array. This is also true for Pool strings,
+you should use solv_strdup() to create a copy of the string if you
+want to use it at some later time. You should use the Ids in the code
+and not the pointers, except for short times where you know that the
+pointer is safe.
-Duncan Mac-Vicar Prett, the team lead of the YaST team, also joined
-development by creating Ruby bindings for the solver. Later, Klaus
-improved the bindings and ported them to some other languages.
+Note also that the data lookup functions or the dataiterator also
+return values with limited lifetime, this is especially true for data
+stored in the paged data segment of solv files. This is normally
+data that consists of big strings like package descriptions or is not
+often needed like package checksums. Thus looking up a description of
+a solvable and then looking up the description of a different solvable
+or even the checksum of the same solvable may invalidate the first
+result. (The dataiterator supports a dataiterator_strdup() function
+to create a safe copy.)
-=== The attribute store ===
-The progress with the repository format and the solver attracted another
-hacker to the project: Michael Matz from the compiler team. He started
-with improving the repository parsers so that patches and content files
-also generate solvables. After that, he concentrated on storing all
-of the other metadata of the repositories that are not used for solving,
-like the package summaries and descriptions. At the end of October, a first
-version of this "attribute store" was checked in. Its design goals were:
+The language bindings already deal with pointer validity, so you do
+not have to worry about this issue when using the bindings.
-- space efficient storage of attributes
-- paging/on demand loading of data
-- page compression
-The first version of the attribute store used a different format for
-storing information, we later merged this format with the solv file
-format.
-
-=== libzypp integration ===
-Integration of the sat-solver into libzypp also started in October 2007 by
-Stefan Schubert and Michael Andres from the YaST team. The first
-versions supported both the old solver and the new one by using the
-old repository read functions and converting the old package data
-in-memory into a sat solver pool. Solvers could be switched with
-the environment variable ZYPP_SAT_SOLVER. The final decision to
-move to the new solver was made in January of 2008, first just by
-making the new solver the default one, later by completely throwing out
-the old solver code. This had the advantage that the internal solvable
-storage could also be done by using the solver pool, something Michael
-Matz already played with in a proof of concept implementation showing
-some drastic speed gains. The last traces of the old database code
-were removed in February.
-
-AUTHOR
+Author
------
Michael Schroeder <mls@suse.de>
+
projects / platform / upstream / libsolv.git / blobdiff