X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=doc%2Flibsolv.txt;h=af44168c880d58748d4babc65b980b6402a65768;hb=982625a0b9d4b97a8074bac320c23471e1cfb1b9;hp=c23f0b4fc44a393a656af0e1bd21099c0e4e4910;hpb=234a84c6f0d725e483ff5577b4f3f84d3f4e63c5;p=platform%2Fupstream%2Flibsolv.git diff --git a/doc/libsolv.txt b/doc/libsolv.txt index c23f0b4..af44168 100644 --- a/doc/libsolv.txt +++ b/doc/libsolv.txt @@ -1,113 +1,58 @@ -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 +