.TH "md_doc_help_elektra-algorithm" 3elektra "Sun May 29 2016" "Version 0.8.14" "Elektra" \" -*- nroff -*-
.ad l
.nh
.SH NAME
md_doc_help_elektra-algorithm \- elektra-algorithm(7) -- core algorithm of elektra 
You might want to read \fBabout architecture\fP\&. and \fBdata structures first\fP\&.
.PP
In this section, we will explain the heart of Elektra\&. \fC\fBkdbOpen()\fP\fP is responsible for the setup and the construction of the data structures needed later\&. \fC\fBkdbGet()\fP\fP does, together with the plugins, all actions necessary to read in the configuration\&. \fC\fBkdbSet()\fP\fP orchestrates the plugins to write out the configuration correctly\&. \fC\fBkdbClose()\fP\fP finally frees all previously allocated data structures\&.
.PP
.SS "kdbOpen"
.PP
\fC\fBkdbOpen()\fP\fP retrieves the {mount point configuration} with \fC\fBkdbGet()\fP\fP using the {default backend}\&. During this process, the function sets up the data structures which are needed for later invocations of \fC\fBkdbGet()\fP\fP or \fC\fBkdbSet()\fP\fP\&. All backends are opened and mounted in the appropriate parts of the key hierarchy\&. The resulting backends are added both to the \fCSplit\fP and the \fCTrie\fP object\&. \fC\fBkdbOpen()\fP\fP finally returns a \fCKDB\fP object that contains all this information as shown in Figure~fig:architecture}\&.
.PP
The reading of the mount point configuration and the consequential self configuring of the system is called {bootstrapping}\&. Elektra builds itself up from the simple variant with a default backend only to the sophisticated configuration system presented in this thesis\&.
.PP
\fC\fBkdbOpen()\fP\fP creates a \fCSplit\fP object\&. It adds all backend handles and \fCparentKeys\fP during bootstrapping\&. So the buildup of the \fCSplit\fP object takes place once\&. The resulting object is then used for both \fC\fBkdbGet()\fP\fP and \fC\fBkdbSet()\fP\fP\&. This approach is much better testable because the \fCSplit\fP object is first initialised using the mount point configuration -- separated from the filtering of the backends for every specific \fC\fBkdbGet()\fP\fP and \fC\fBkdbSet()\fP\fP request\&.
.PP
Afterwards the key hierarchy is static\&. Every application using Elektra will build up the same key database\&. Application specific mount points are prohibited because changes of mount points would destroy the global key database\&. Elektra could not guarantee that every application retrieves the same configuration with the same key names any longer\&.
.PP
In \fC\fBkdbOpen()\fP\fP, nearly no checks are done regarding the expected behaviour of the backend\&. The contract checker guarantees that only appropriate mount points are written into the mount point configuration\&. \fC\fBkdbOpen()\fP\fP checks only if the opening of plugin was successful\&. If not, the backend enclosing the plugin is not mounted at all\&.
.PP
.SS "Removing Keys"
.PP
In Elektra version $0\&.6$, removing keys was an explicit request\&. Only a single \fCKey\fP object could be removed from the database\&. For configuration files this method is inapplicable\&. For \fCfilesys\fP, however, it was easy to implement\&.
.PP
In Elektra version $0\&.7$, the behaviour changed\&. Removing keys was integrated into \fC\fBkdbSet()\fP\fP\&. The user tagged keys that should be removed\&. After the next \fC\fBkdbSet()\fP\fP, these keys were removed from the key database\&. On the one hand, backends writing configuration files simply ignored the keys marked for removal\&. On the other hand, \fCfilesys\fP needed that information to remove the files\&. To make this approach work for \fCfilesys\fP, the marked keys were located at the very end of the \fCKeySet\fP and sorted in reverse\&. With this trick, recursive removing worked well\&. But this approach had major defects in the usage of \fCKeySet\fP\&. Because marking a key to be removed changed the sort order of the key set {\fBksLookupByName()\fP} did not find this key anymore\&.
.PP
So in the present version removing keys is consistent again\&. A \fCKeySet\fP describes the current configuration\&. The user can reduce the \fCKeySet\fP object by [pop]{popping} keys out\&. The \fC\fBkdbSet()\fP\fP function applies exactly this configuration as specified by the key set to the key database\&. Contrary to the previous versions, the popped keys of the key set will be permanently removed\&.
.PP
The new circumstance yields \fBidempotent\fP properties for \fC\fBkdbSet()\fP\fP\&. The same \fCKeySet\fP can be applied multiple times, but after the first time, the key database will not be changed anymore\&. (Note that \fC\fBkdbSet()\fP\fP) actually detects that there are no changes and will do nothing\&. To actually show the idempotent behaviour the KeySet has to be regenerated or the key database needs to be reopened\&.
.PP
It is, however, not known if keys should be removed permanently only by investigating the \fCKeySet\fP\&. But only if this knowledge is present, the core can decide if the key set needs to be written out or if the configuration is unchanged\&. So we decided to track how many keys are delivered in \fC\fBkdbGet()\fP\fP\&. If the size of the \fCKeySet\fP is lower than this number determined at the previous \fC\fBkdbGet()\fP\fP, Elektra's core knows that some keys were popped\&. Hence, the next \fC\fBkdbSet()\fP\fP invocation needs to change the concerned key database\&.
.PP
The situation is now much clearer\&. The semantics of popping a key will result in removing the key from the key database\&. And the intuitive idea that a \fCKeySet\fP will be applied to the key database is correct again\&.
.PP
.SS "kdbGet"
.PP
It is critical for application startup time to retrieve the configuration as fast as possible\&. Hence, the design goal of the \fC\fBkdbGet()\fP\fP algorithm is to be efficient while still enabling plugins to have relaxed postconditions\&. To achieve this, the sequence of [syscall]{syscalls} must be optimal\&. On the other hand, it is not tolerable to waste time or memory inside Elektra's core, especially during an initial request or when no update is available\&.
.PP
The synopsis of the function is: 
.PP
.nf
    int kdbGet(KDB *handle, KeySet *returned, Key * parentKey);

.fi
.PP
.PP
The user passes a key set, called \fCreturned\fP\&. If the user invokes \fC\fBkdbGet()\fP\fP the first time, he or she will usually pass an empty key set\&. If the user wants to update the application's settings, \fCreturned\fP will typically contain the configuration of the previous \fC\fBkdbGet()\fP\fP request\&. The \fCparentKey\fP holds the information below which key the configuration should be retrieved\&. The \fChandle\fP contains the data structures needed for the algorithm, like the \fCSplit\fP and the \fCTrie\fP objects, as shown in Figure~fig:architecture}\&.
.PP
\fC\fBkdbGet()\fP\fP does a rather easy job, because \fC\fBkdbSet()\fP\fP already guarantees that only well formatted, non-corrupted and well-typed configuration is written out in the key database\&. The task is to query all backends in question for their configuration and then merge everything\&.
.PP
.SS "Responsibility"
.PP
A backend may yield keys that it is not responsible for\&. It is not possible for a backend to know that another backend has been mounted below and the other backend is now responsible for some of the keys that are still in the storage\&. Additionally, plugins are not able to determine if they are responsible for a key or not\&. Consequently, it can happen that more than one backend delivers a key with the same name\&.
.PP
\fC\fBkdbGet()\fP\fP ensures that a key is uniquely identified by its name\&. Elektra's core will pop keys that are outside of the backend's responsibility\&. Hence, these keys will not be passed to the user and we get the desired behaviour: The nearest mounted backend to the key is responsible\&.
.PP
For example, a generator plugin in the backend A always emits following keys{(A) and (B) indicate from which backend the key comes from\&.}: {lstlisting}[language=] user/sw/generator/akey (A) user/sw/generator/dir (A) user/sw/generator/dir/outside1 (A) user/sw/generator/dir/outside2 (A) {lstlisting} It will still return these keys even if the plugin is not responsible for some of them anymore\&. This can happen if another backend B is mounted to {user/sw/generator/dir}\&. In the example it yields the following keys: {lstlisting}[language=] user/sw/generator/dir (B) user/sw/generator/dir/new (B) user/sw/generator/dir/outside1 (B) user/sw/generator/outside (B) {lstlisting} In this situation \fC\fBkdbGet()\fP\fP is responsible to pop all three keys at, and below, {user/sw/generator/dir} of backend A and the key {user/sw/generator/outside} of backend B\&. The user will get the resulting key set: {lstlisting}[language=] user/sw/generator/akey (A) user/sw/generator/dir (B) user/sw/generator/dir/new (B) user/sw/generator/dir/outside1 (B) {lstlisting} Note that the key exactly at the mount point comes from the backend mounted at {user/sw/generator/dir}\&.
.PP
.SS "Sequence"
.PP
\fC\fBkdbOpen()\fP\fP already creates a \fCSplit\fP object for the whole configuration tree\&. In this object, \fC\fBkdbOpen()\fP\fP will append a list of all backends available\&. A specific \fC\fBkdbGet()\fP\fP request usually includes only a part of the configuration\&. For example, the user is only interested in keys below {user/sw/apps/userapp}\&. All backends that cannot contribute to configuration below {user/sw/apps/userapp} will be omitted for that request\&. To achieve this, parts of the \fCSplit\fP object are filtered out\&. After this step we know the list of backends involved\&. The \fCSplit\fP object allocates a key set for each of these backends\&.
.PP
Afterwards the first plugin of each backend is called to determine if an update is needed\&. If no update is needed, the algorithm has finished and returns zero\&.
.PP
Now we know which backends do not need an update\&. For these backends, the previous configuration from \fCreturned\fP is appointed from to the key sets of the \fCSplit\fP object\&. The algorithm will not set the {syncbits} of the \fCSplit\fP object for these backends because the storage of the backends already contains up-to-date configuration\&.
.PP
The other backends will be requested to {retrieve} their configuration\&. The initial empty \fCKeySet\fP from the \fCSplit\fP object and the relevant file name in the key value of \fCparentKey\fP are passed to each remaining plugin\&. The plugins extend, validate and process the key set\&. When an error has occurred, the algorithm can stop immediately because the user's \fCKeySet\fP \fCreturned\fP is not changed at this point\&. When this part finishes, the \fCSplit\fP object contains the whole requested configuration separated in various key sets\&.
.PP
Subsequently the freshly received keys need some {post-processing}:
.PP
.IP "\(bu" 2
Newly allocated keys in Elektra always have the {sync flag} set\&. Because the plugins allocate and modify keys with the same functions as the user, the returned keys will also have their sync flag set\&. But from the user's point of view the configuration is unmodified\&. So some code needs to remove this sync flag\&. To relax the post conditions of the plugins, \fC\fBkdbGet()\fP\fP removes it\&.
.IP "\(bu" 2
To detect removed keys in subsequent \fC\fBkdbSet()\fP\fP calls, \fC\fBkdbGet()\fP\fP needs to store the number of received keys of each backend\&.
.IP "\(bu" 2
Additionally, for every key it is checked if it belongs to this backend\&. This makes sure that every key comes from a single source only as designated by the \fCTrie\fP\&. In this process, all duplicated and overlapping keys will be popped in favour of the responsible backend as described below in responsibility\&.
.PP
.PP
The last step is to {merge} all these key sets together\&. This step changes the configuration visible to the user\&. After some cleanup the algorithm finally finishes\&.
.PP
.SS "Updating Configuration"
.PP
The user can call \fC\fBkdbGet()\fP\fP often even if the configuration or parts of it are already up to date\&. This can happen when applications reread configuration in some events\&. Examples are signals{SIGHUP is the signal used for that on UNIX systems\&. It is sent when the program's controlling terminal is closed\&. Daemons do not have a terminal so the signal is reused for reloading configuration\&.}, notifications, user requests and in the worst case periodical attempts to reread configuration\&.
.PP
The given goal is to keep the sequence of needed syscalls low\&. If no update is needed, it is sufficient to request the timestamp{On POSIX systems using {stat()}\&.} of every file\&. No other syscall is needed\&. Elektra's core alone cannot check that because getting a timestamp is not defined within the standard C99\&. So instead the resolver plugin handles this problem\&. The resolver plugin returns 0 if nothing has changed\&.
.PP
This decision yields some advantages\&. Both the storage plugins and Elektra's core can conform to C99\&. Because the resolver plugin is the very first in the chain of plugins, it is guaranteed that no useless work is done\&.
.PP
.SS "Initial kdbGet Problem"
.PP
Because Elektra provides self-contained configuration, \fC\fBkdbOpen()\fP\fP has to retrieve settings in the {bootstrapping} process below {system/elektra} as explained in {bootstrapping}\&. Because of the new way to keep track of removed keys, the internally executed \fC\fBkdbGet()\fP\fP creates a problem\&. Without countermeasures even the first \fC\fBkdbGet()\fP\fP of a user requesting the configuration below {system/elektra} fails because the resolver finds out that the configuration is already up to date\&. The configuration delivered by the user is empty at this point\&. As a result, the empty configuration will be appointed and returned to the user\&.
.PP
A simple way to resolve this issue is to reload the default backend after the internal configuration was fetched\&. Reloading resets the timestamps and \fC\fBkdbGet()\fP\fP works as expected\&.
.PP
.SS "kdbSet}"
.PP
Not the performance, but robust and reliable behaviour is the most important issue for \fC\fBkdbSet()\fP\fP\&. The design was chosen so that some additional in-memory comparisons are preferred to a suboptimal sequence of [syscall]{syscalls}\&. The algorithm makes sure that keys are written out only if it is necessary because applications can call \fC\fBkdbSet()\fP\fP with an unchanged \fCKeySet\fP\&. For the code to decide this, performance is important\&.
.PP
.SS "Properties"
.PP
\fC\fBkdbSet()\fP\fP [guarantee]{guarantees} the following properties:
.PP
{enumerate}
.PP
Modifications to permanent storage are only made when the configuration was changed\&.
.PP
When errors occur, every plugin gets a chance to rollback its changes as described in {exception safety}\&.
.PP
If every plugin does this correctly, the whole \fCKeySet\fP is propagated to permanent storage\&. Otherwise nothing is changed in the key database\&. Plugins developed during the thesis meet this requirement\&.
.PP
{enumerate}
.PP
The synopsis of the function is: {lstlisting} int kdbSet(KDB *handle, KeySet *returned, Key * parentKey); {lstlisting}
.PP
The user passes the configuration using the \fCKeySet\fP \fCreturned\fP\&. The key set will not be changed by \fC\fBkdbSet()\fP\fP\&. The \fCparentKey\fP provides a way to limit which part of the configuration is written out\&. For example, the \fCparentKey\fP {user/sw/apps/myapp} will induce \fC\fBkdbSet()\fP\fP to only modify the key databases below {user/sw/apps/myapp} even if the \fCKeySet\fP \fCreturned\fP also contains more configuration\&. Note that all backends with no keys in \fCreturned\fP but that are below \fCparentKey\fP will completely wipe out their key database\&. The \fCKDB\fP handle contains the necessary data structures as shown in Figure~fig:architecture}\&.
.PP
.SS "Search for Changes"
.PP
{wrapfigure}{r}{0\&.5} {-40pt} {center} [trim = 0 65 0 0, clip=true, width=6cm]{resolver_set} {center} {-20pt} {{\fBkdbSet()\fP} Algorithm} {fig:resolver_set} {-10pt} {wrapfigure}
.PP
As a first step, \fC\fBkdbSet()\fP\fP {divides} the configuration passed in by the user to the key sets in the \fCSplit\fP object\&. \fC\fBkdbSet()\fP\fP searches for every key if the {sync flag} is checked\&. Then \fC\fBkdbSet()\fP\fP decides if a key was removed from a backend by comparing the actual size of the key set with the size stored from the last \fC\fBkdbGet()\fP\fP call\&. We see that it is necessary to call \fC\fBkdbGet()\fP\fP first before invocations of \fC\fBkdbSet()\fP\fP are allowed\&.
.PP
We know that data of a backend has to be written out if at least one key was changed or removed\&. If no backend has any changes, the algorithm will terminate at this point\&. The careful reader notices that the process involves no file operations\&.
.PP
.SS "Duplicated Key Sets"
.PP
If some backends need synchronisation, the algorithm continues by filtering out all backends in the \fCSplit\fP object that do not have changes\&. At this point, the \fCSplit\fP object has a list of backends with their respective key sets\&.
.PP
{deep duplicate}
.PP
Plugins in \fC\fBkdbSet()\fP\fP can change values\&. Other than in \fC\fBkdbGet()\fP\fP, the user is not interested in these changes\&. Instead, the values are transformed to be suitable for the storage\&. To make sure that the changed values are not passed to the user, the algorithm continues with a {deep duplication} of all key sets in the \fCSplit\fP object\&.
.PP
.SS "Resolver"
.PP
All plugins of each included backend are executed one by one up to the resolver plugin\&. If this succeeds, the resolver plugin is responsible for committing these changes\&. After the successful commit, [error code]{error codes} of plugins are ignored\&. Only logging and notification plugins are affected\&.
.PP
.SS "Atomic Replacement"
.PP
For this thesis only file-based storage with atomic properties were developed\&. The replacement of a file with another file that has not yet been written is not trivial\&. The straightforward way is to lock a file and start writing to it\&. But this approach can result in broken or partially finished files in events like ''out of disc space'', signals or other asynchronous aborts of the program\&.
.PP
A temporary file solves this problem, because in problematic events the original file stays untouched\&. When the temporary file is written out properly, it is renamed and the original configuration file is overwritten\&. But another concurrent invocation of \fC\fBkdbSet()\fP\fP can try to do the same with the result that one of the newly written files is lost\&.
.PP
To avoid this problem, locks are needed again\&. It is not possible to lock the configuration file itself because it will be unlinked when the temporary file is renamed\&. So a third file for locking is needed\&. The resolver currently implements this approach\&.
.PP
An alternative to this approach without locks is to completely rely on the modification time\&. The modification time typically has only a resolution of one second\&. So any changes within that time slot will not be recognised\&. For this approach, however, the name of every temporary file must be unique because concurrent \fC\fBkdbSet()\fP\fP invocations each try to create one\&. The temporary file must also be unlinked in case of a rollback\&. The opened temporary file can be passed to the storage plugins using a file name in the directory {/dev/fd}\&. This approach may be more practical than the currently implemented way because it does not need the additional lock file{Nevertheless, the other way was chosen to test if the algorithm is exception safe as described in {exception safety}\&.}\&.
.PP
.SS "Errors"
.PP
The plugins within \fC\fBkdbSet()\fP\fP can fail for a variety of reasons\&. [conflict]{Conflicts} occur most frequently\&. A conflict means that during executions of \fC\fBkdbGet()\fP\fP and \fC\fBkdbSet()\fP\fP another program has changed the key database\&. In order not to lose any data, \fC\fBkdbSet()\fP\fP fails without doing anything\&. In conflict situations Elektra leaves the programmer no choice\&. The programmer has to retrieve the configuration using \fC\fBkdbGet()\fP\fP again to be up to date with the key database\&. Afterwards it is up to the application to decide which configuration to use\&. In this situation it is the best to ask the user, by showing him the description and reason of the error, how to continue:
.PP
{enumerate}
.PP
{conflicts}
.PP
Save the configuration again\&. The changes of the other program will be lost in this case\&.
.PP
The key database can also be left unchanged as the other program wrote it\&. After using \fC\fBkdbGet()\fP\fP the application is already up to date with the new configuration\&. All configuration changes the user made before will be lost\&.
.PP
The application can try to merge the key sets to get the best result\&. If no key is changed on both sides the result is clear, otherwise the application has to decide if the own or the other configuration should be favoured\&. The result of the merged key sets has to be written out with \fC\fBkdbSet()\fP\fP\&.
.PP
Merging the key sets can be done with \fC\fBksAppend()\fP\fP\&. The source parameter is the preferred configuration\&. Note that the downside of the third option is that a merged configuration can be an not validating configuration\&.
.PP
{enumerate}
.PP
Sometimes a concrete key causes the problem that the whole key set cannot be stored\&. That can happen on validation or because of type errors\&. Such errors are usually caused by a mistake made by the user\&. So the user is responsible for changing the settings to make it valid again\&. In such situations, the {internal cursor} of the \fCKeySet\fP \fCreturned\fP will point to the problematic key\&.
.PP
A completely different approach is to export the configuration when \fC\fBkdbSet()\fP\fP returned an error code\&. The user can then edit, change or merge this configuration with more powerful tools\&. Finally, the user can import the configuration into the global key database\&. The export and import mechanism is called ''streaming'' and will be explained in {streaming}\&.