diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 258 |
1 files changed, 200 insertions, 58 deletions
@@ -1,58 +1,200 @@ -# Order-preserving minimal perfect hash function generator - -Build order-preserving minimal perfect hash functions. - -[](https://codecov.io/gh/julian-klode/triehash) -[](https://travis-ci.org/julian-klode/triehash) - -## Performance - -Performance was evaluated against other hash functions. As an input set, the -fields of Debian Packages and Sources files was used, and each hash function -was run 1,000,000 times for each word. The byte count of the words were then -summed up and divided by the total number of nanoseconds each function ran, so -all speeds below are given in bytes per nanosecond, AKA gigabyte per second. - -arch/function|jak-x230 (amd64)|backup (amd64)|asachi.d.o (arm64)|asachi.d.o (armel)|asachi.d.o (armhf)|plummer.d.o (ppc64el)|eller.d.o (mipsel) --------------|----------------|--------------|------------------|------------------|------------------|---------------------|------------------ -Trie | 2.4 | 1.9 | 1.2 | 0.9 | 0.8 | 2.0 | 0.2 -Trie (*) | 2.2 | 1.7 | 0.8 | 0.7 | 0.7 | 1.8 | 0.2 -re2c | 1.7 | 1.3 | 0.9 | 0.9 | 0.7 | 1.6 | 0.2 -re2c (*) | 1.2 | 0.9 | 0.6 | 0.6 | 0.5 | 1.1 | 0.1 -gperf (*) | 0.7 | 0.5 | 0.2 | 0.2 | 0.2 | 0.5 | 0.1 -gperf | 1.3 | 0.9 | 0.3 | 0.3 | 0.2 | 0.4 | 0.1 -djb (*) | 0.7 | 0.5 | 0.3 | 0.3 | 0.3 | 0.5 | 0.1 -djb (**) | 1.0 | 0.7 | 0.4 | 0.5 | 0.5 | 0.6 | 0.2 -djb | 0.9 | 0.7 | 0.5 | 0.5 | 0.5 | 0.7 | 0.2 -apt (*) | 1.2 | 0.9 | 0.7 | 0.7 | 0.7 | 1.1 | 0.2 -apt (**) | 2.3 | 1.7 | 0.7 | 0.9 | 0.8 | 1.9 | 0.2 - -And transposed: - -function/arch |Trie |Trie (*) |re2c |re2c (*) |gperf (*)|gperf |djb (*) |djb (**) |djb |apt (*) |apt (**) ----------------------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|--------- -jak-x230 (amd64) | 2.4| 2.2| 1.7| 1.2| 0.7| 1.3| 0.7| 1.0| 0.9| 1.2| 2.3 -backup (amd64) | 1.9| 1.7| 1.3| 0.9| 0.5| 0.9| 0.5| 0.7| 0.7| 0.9| 1.7 -asachi.d.o (arm64) | 1.2| 0.8| 0.9| 0.6| 0.2| 0.3| 0.3| 0.4| 0.5| 0.7| 0.7 -asachi.d.o (armel) | 0.9| 0.7| 0.9| 0.6| 0.2| 0.3| 0.3| 0.5| 0.5| 0.7| 0.9 -asachi.d.o (armhf) | 0.8| 0.7| 0.7| 0.5| 0.2| 0.2| 0.3| 0.5| 0.5| 0.7| 0.8 -plummer.d.o (ppc64el)| 2.0| 1.8| 1.6| 1.1| 0.5| 0.4| 0.5| 0.6| 0.7| 1.1| 1.9 -eller.d.o (mipsel) | 0.2| 0.2| 0.2| 0.1| 0.1| 0.1| 0.1| 0.2| 0.2| 0.2| 0.2 - - -Legend: - -* The (*) variants are case-insensitive, (**) are more optimised versions - of the (*) versions. -* DJB (*) is a DJB Hash with naive lowercase conversion, DJB (**) just ORs one - bit into each value to get alphabetical characters to be lowercase -* APT (*) is the AlphaHash function from APT which hashes the last 8 bytes in a - word in a case-insensitive manner. APT (**) is the same function unrolled. -* All hosts except the x230 are Debian porterboxes. The x230 has a Core i5-3320M, - barriere has an Opteron 23xx. - -Notes: - -* The overhead is larger than needed on some platforms due to gcc inserting - unneeded zero extend instructions, see: - https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77729 +APT +=== + +apt is the main commandline package manager for Debian and its derivatives. +It provides commandline tools for searching and managing as well as querying +information about packages as well as low-level access to all features +provided by the libapt-pkg and libapt-inst libraries which higher-level +package managers can depend upon. + +Included tools are: + +* apt-get for retrieval of packages and information about them + from authenticated sources and for installation, upgrade and + removal of packages together with their dependencies +* apt-cache for querying available information about installed + as well as installable packages +* apt-cdrom to use removable media as a source for packages +* apt-config as an interface to the configuration settings +* apt-key as an interface to manage authentication keys +* apt-extracttemplates to be used by debconf to prompt for configuration + questions before installation. +* apt-ftparchive creates Packages and other index files + needed to publish an archive of debian packages +* apt-sortpkgs is a Packages/Sources file normalizer. + +The libraries libapt-pkg and libapt-inst are also maintained as part of this project, +alongside various additional binaries like the acquire-methods used by them. +Bindings for Python ([python-apt](https://tracker.debian.org/pkg/python-apt)) and +Perl ([libapt-pkg-perl](https://tracker.debian.org/pkg/libapt-pkg-perl)) are available as separated projects. + +Discussion happens mostly on [the mailinglist](mailto:deity@lists.debian.org) ([archive](https://lists.debian.org/deity/)) and on [IRC](irc://irc.oftc.net/debian-apt). +Our bugtracker as well as a general overview can be found at the [Debian Tracker page](https://tracker.debian.org/pkg/apt). + + +Contributing +------------ +APT is maintained in git, the official repository being located at +`git://anonscm.debian.org/apt/apt.git` ([webgit](https://anonscm.debian.org/git/apt/apt.git)), +but also available at other locations like [GitHub](https://github.com/Debian/apt). + +The default branch is `master`, other branches targeted at different +derivatives and releases being used as needed. Various topic branches in +different stages of completion might be branched of from those, which you +are encouraged to do as well. + +### Coding + +APT uses cmake. To start building, you need to run + + cmake <path to source directory> + +from a build directory. For example, if you want to build in the source tree, +run: + + cmake . + +Then you can use make as you normally would (pass -j <count> to perform <count> +jobs in parallel). + +You can also use the Ninja generator of cmake, to do that pass + -G Ninja +to the cmake invocation, and then use ninja instead of make. + +The source code uses in most parts a relatively uncommon indent convention, +namely 3 spaces with 8 space tab (see [doc/style.txt](https://anonscm.debian.org/git/apt/apt.git/tree/doc/style.txt) for more on this). +Adhering to it avoids unnecessary code-churn destroying history (aka: `git blame`) +and you are therefore encouraged to write patches in this style. +Your editor can surely help you with this, for vim the settings would be +`setlocal shiftwidth=3 noexpandtab tabstop=8` +(the later two are the default configuration and could therefore be omitted). + +### Translations + +While we welcome contributions here, we highly encourage you to contact the [Debian Internationalization (i18n) team](https://wiki.debian.org/Teams/I18n). +Various language teams have formed which can help you creating, maintaining +and improving a translation, while we could only do a basic syntax check of the +file format… + +Further more, Translating APT is split into two independent parts: +The program translation, meaning the messages printed by the tools, +as well as the manpages and other documentation shipped with APT. + +### Bug triage + +Software tools like APT which are used by thousands of users every +day have a steady flow of incoming bugreports. Not all of them are really +bugs in APT: It can be packaging bugs like failing maintainer scripts a +user reports against apt, because apt was the command he executed leading +to this failure or various wishlist items for new features. Given enough time +also the occasional duplicate enters the system. +Our bugtracker is therefore full with open bugreports which are waiting for you! ;) + +Testing +------- + +### Manual execution + +When you make changes and want to run them manually, you can just do so. CMake +automatically inserts an rpath so the binaries find the correct libraries. + +Note that you have to invoke CMake with the right install prefix set (e.g. +`-DCMAKE_INSTALL_PREFIX=/usr`) to have your build find and use the right files +by default or alternatively set the locations at runtime via an `APT_CONFIG` +configuration file. + +### Integration tests + +There is an extensive integration testsuite available which can be run via: + + $ ./test/integration/run-tests + +Each test can also be run individually as well. The tests are very noisy by +default, especially so while running all of them it might be beneficial to +enabling quiet (`-q`) or very quiet (`-qq`) mode. The tests can also be run in +parallel via `-j X` where `X` is the number of jobs to run. + +While these tests are not executed at package build-time as they require +additional dependencies, the repository contains the configuration needed to +run them on [Travis CI](https://travis-ci.org/) and +[Shippable](https://shippable.com/) as well as via autopkgtests e.g. on +[Debian Continuous Integration](https://ci.debian.net/packages/a/apt/). + +A testcase here is a shellscript embedded in a framework creating an environment in which +apt tools can be used naturally without root-rights to test every aspect of its behavior +itself as well as in conjunction with dpkg and other tools while working with packages. + + +### Unit tests + +These tests are gtest-dev based, executed by ctest, reside in `./test/libapt` +and can be run with `make test`. They are executed at package build-time, but +not by `make`. CTest by default does not show the output of tests, even if they +failed, so to see more details you can also run them with `ctest --verbose`. + +Debugging +--------- + +APT does many things, so there is no central debug mode which could be +activated. It uses instead various config-options to activate debug output +in certain areas. The following describes some common scenarios and generally +useful options, but is in no way exhaustive. + +Note that you should *NEVER* use these settings as root to avoid accidents. +Simulation mode (`-s`) is usually sufficient to help you run apt as a non-root user. + +### Using different state files + +If a dependency solver bug is reported, but can't be reproduced by the +triager easily, it is beneficial to ask the reporter for the +`/var/lib/dpkg/status` file, which includes the packages installed on the +system and in which version. Such a file can then be used via the option +`dir::state::status`. Beware of different architecture settings! +Bugreports usually include this information in the template. Assuming you +already have the `Packages` files for the architecture (see `sources.list` +manpage for the `arch=` option) you can change to a different architecture +with a config file like: + + APT::Architecture "arch1"; + #clear APT::Architectures; + APT:: Architectures { "arch1"; "arch2"; } + +If a certain mirror state is needed, see if you can reproduce it with [snapshot.debian.org](http://snapshot.debian.org/). +Your sources.list file (`dir::etc::sourcelist`) has to be correctly mention the repository, +but if it does, you can use different downloaded archive state files via `dir::state::lists`. + +In case manually vs. automatically installed matters, you can ask the reporter for +the `/var/lib/apt/extended_states` file and use it with `dir::state::extended_states`. + +### Dependency resolution + +APT works in its internal resolver in two stages: First all packages are visited +and marked for installation, keep back or removal. Option `Debug::pkgDepCache::Marker` +shows this. This also decides which packages are to be installed to satisfy dependencies, +which can be seen by `Debug::pkgDepCache::AutoInstall`. After this is done, we might +be in a situation in which two packages want to be installed, but only on of them can be. +It is the job of the pkgProblemResolver to decide which of two packages 'wins' and can +therefore decide what has to happen. You can see the contenders as well as their fight and +the resulting resolution with `Debug::pkgProblemResolver`. + +### Downloading files + +Various binaries (called 'methods') are tasked with downloading files. The Acquire system +talks to them via simple text protocol. Depending on which side you want to see, either +`Debug::pkgAcquire::Worker` or `Debug::Acquire::http` (or similar) will show the messages. + +The integration tests use a simple self-built webserver which also logs. If you find that +the http(s) methods do not behave like they should be try to implement this behavior in the +webserver for simpler and more controlled testing. + +### Installation order + +Dependencies are solved, packages downloaded: Everything read for the installation! +The last step in the chain is often forgotten, but still very important: +Packages have to be installed in a particular order so that their dependencies are +satisfied, but at the same time you don't want to install very important and optional +packages at the same time if possible, so that a broken optional package does not +block the correct installation of very important packages. Which option to use depends on +if you are interested in the topology sorting (`Debug::pkgOrderList`), the dependency-aware +cycle and unconfigured prevention (`Debug::pkgPackageManager`) or the actual calls +to dpkg (`Debug::pkgDpkgPm`). |