Skip to content
This repository has been archived by the owner on Oct 15, 2024. It is now read-only.

Key Name Ordering broken #38

Closed
fberlakovich opened this issue Aug 7, 2014 · 16 comments
Closed

Key Name Ordering broken #38

fberlakovich opened this issue Aug 7, 2014 · 16 comments
Assignees
Milestone

Comments

@fberlakovich
Copy link
Contributor

I recently sumbled over the following problem a couple of times. I am not quite sure yet however if this is actually a bug or something on my system is broken.

My guess: if two mountpoints are created where the name of the one is a prefix of the other, the shorter mountpoint is no longer accessible. Example:

sudo kdb mount /etc/hosts system/foo hosts
kdb ls system/foo

Up to now it works as expected. Now i do

sudo kdb mount /etc/hosts system/foo-hosts hosts
kdb ls system/foo-hosts

This still works as expected. But now a kdb ls system/foo won't return any results anymore. A look into system/elektra/mountpoints reveals, that the key system/elektra/mountpoints/foo and its subkeys are not sorted continously anymore. Instead the order is

system/elektra/mountpoints/foo
system/elektra/mountpoints/foo-hosts
system/elektra/mountpoints/foo-hosts/subkeys
system/elektra/mountpoints/foo/subkeys

I suspect that this causes the problem, but I have not looked into the mount code in detail yet.

@iandonnelly
Copy link
Contributor

Confirmed, happens with other plug-ins too.

@fberlakovich
Copy link
Contributor Author

Great, then it is not my broken system :). Maybe we could take this as an opportunity to review the KeySet sorting.

@markus2330
Copy link
Contributor

This issue may have nothing to with mounting, you can also reproduce it with:

kdb set user/test/test
kdb set user/test/test/foo
kdb set user/test/test-foo
kdb set user/test/test/bar

Or for C code see 8b655c8

@markus2330
Copy link
Contributor

The problem is simple that this is the sort order of strcmp as used in keyCmpInternal().
The same problem occurs with 32 (space) up to 46 (. dot) and not only 45 (-).
I am afraid we have to reimplement strcmp, which again opens the question if #9 should be before #10. (Benchmark is needed however to see how much slower those variants are)

@markus2330 markus2330 added this to the 0.8.8 milestone Aug 7, 2014
@markus2330
Copy link
Contributor

One other way to fix the issue would be to duplicate the names for every key, replace / by 0 and use memcmp. This would also allow more efficient iteration over the key name, but more memory would be needed obviously.

markus2330 pushed a commit that referenced this issue Aug 8, 2014
@markus2330
Copy link
Contributor

          strcmp:                30537 Microseconds
          memcmp:                27664 Microseconds
          owncmp:              5607923 Microseconds
          slacmp:              6499881 Microseconds
          natcmp:             10433608 Microseconds

so using memcmp and having a duplicated name with 0 instead of / seems the only sane variant (about 30% of CPU time is spent in keyCmpInternal).

Can someone rerun the benchmark, preferable not on amd64?
Just run:
cd ~build
benchmark/cmp

If we do this, the (somehow weird) escaped slash:

  user/abc\/something

could also yield correct order. (It would be interpreted as text and not as delimiter.) The question if is this feature was a good idea after all (its already ancient).

fberlakovich pushed a commit to fberlakovich/libelektra that referenced this issue Aug 10, 2014
@fberlakovich
Copy link
Contributor Author

Values from my development machine (VMware VM running 3.2.0-4-amd64 #1 SMP Debian 3.2.57-3+deb7u2 x86_64 GNU/Linux). Host CPU is Intel Core i5-2520M

              strcmp:              1329001 Microseconds
              memcmp:              1434127 Microseconds
              owncmp:             37110741 Microseconds
              slacmp:             40140380 Microseconds
              natcmp:             56610883 Microseconds

Values from a 32-bit Server-VM follow as soon as #60 is fixed.

@markus2330
Copy link
Contributor

thank you, I think thats ok for now.

@fberlakovich
Copy link
Contributor Author

Values from a server I run (KVM VM running 2.6.32-5-486 i686 GNU/Linux). Host CPU is Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz

              strcmp:                48046 Microseconds
              memcmp:                47601 Microseconds
              owncmp:              8337193 Microseconds
              slacmp:              8524459 Microseconds
              natcmp:             13416965 Microseconds

@markus2330 markus2330 self-assigned this Aug 23, 2014
@markus2330 markus2330 changed the title Mountpoints with overlapping prefixes cause troubles Key Name Ordering broken Aug 23, 2014
@markus2330
Copy link
Contributor

Will solve this by having a keyName that has double length.

@fberlakovich Please use keySetRawName() internally, so that this issue can be solved on a single place.

@fberlakovich
Copy link
Contributor Author

Where should I use keySetRawName? This funciton does not even exist yet, does it?

@fberlakovich
Copy link
Contributor Author

Nevermind, I just found where I should use it. However, it still does not exist yet?

@markus2330
Copy link
Contributor

No, it does not exists yet

@fberlakovich
Copy link
Contributor Author

Ok, after finishing the changes on keyAddBaseName and keySetBaseName I am afraid I won't have enough time to also do this refactoring. As it turns out, there are a lot of things (at least testcases) that have to be adjusted to the new specification.

@markus2330
Copy link
Contributor

You do not have to adapt the existing test cases. Then I can decide case by case if it is actually a change of behaviour or if it fixes a problem.

So please concentrate on the implementation, refactoring and adding new tests that are missing.

@fberlakovich
Copy link
Contributor Author

Ok, as you can see in the pull request I provided a quickfix for everything that was obviously broken and fixed the tests that should still work. However, some tests contradict the new specificaiton. I disabled them and added a TODO.

markus2330 pushed a commit that referenced this issue Aug 31, 2014
also in binding
refactor with elektraFinalizeName as preparation for fixing #38
fail when no key is there before for adding functions
fix tests that try to do that
refactor keySetName to use keyAddName internally
do keyAddBaseName and keySetBaseName both with escaping
comment out KEY_FLAG_RO_NAME because some tests fail with it
fix mounting with config to properly add conf that contains /
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants