grn_pat: grn_pat_delete() fails after many adds and deletes

[s-yata]

Description

I've found some cases in which grn_pat_delete() fails even if its target key exists.
The problem happened after more than 1,000 adds and deletes.

The following is the shortest case I found.

r4-s733.txt

$ mkdir /tmp/groonga
$ groonga --file r4-s733.txt -n /tmp/groonga/db
...
$ groonga /tmp/groonga/db
$ src/groonga /tmp/groonga/db
> cache_limit 0
[[0,1445240341.14388,0.000423431396484375],100]
> select pat
[[0,1445240343.67223,0.000467061996459961],[[[3],[["_id","UInt32"],["_key","UInt8"]],[1,0],[8,1],[2,2]]]]
> delete pat --key 2
[[0,1445240349.76818,0.000156402587890625],false]
> select pat
[[0,1445240353.84036,0.000203847885131836],[[[3],[["_id","UInt32"],["_key","UInt8"]],[9,7]]]]

edit: updated at 2015-10-19 16:39.

[s-yata]

There are only 3 valid nodes after delinfo_new() and the last select returns only [9,7].

id	lr[0]	lr[1]	key	check	bits
0	0	6	0	0	0
6	9	0	6	0	4
9	0	9	7	14	4

[s-yata]

It seems that this problem happens when grn_pat_header.delinfos is full.
A smaller GRN_PAT_NDELINFOS may make debugging easier.

[s-yata]

If GRN_PAT_NDELINFOS == 4 (this macro is defined in grn_pat.h), only 7 loads and 6 deletes are required to reproduce the problem.
The following is the case.

r4-s769-n4.txt

$ mkdir /tmp/groonga
$ groonga --file r4-s769-n4.txt -n /tmp/groonga/db
...
$ groonga /tmp/groonga/db
> cache_limit 0
[[0,1445310092.03779,0.000296354293823242],100]
> select pat
[[0,1445310093.59706,0.000596761703491211],[[[2],[["_id","UInt32"],["_key","UInt8"]],[5,2],[4,7]]]]
> delete pat --key 2
[[0,1445310096.94901,0.000150918960571289],false]
> select pat
[[0,1445310098.43704,0.000145196914672852],[[[2],[["_id","UInt32"],["_key","UInt8"]],[2,5]]]]

[s-yata]

I've found a simple pattern to reproduce the problem.

First, run the following commands.

table_create pat TABLE_PAT_KEY UInt8
load --table pat
[{"_key": 0},{"_key": 1},{"_key": 2}]
delete pat --key 0
delete pat --key 1
load --table pat '[{"_key": 0}]'
delete pat --key 2

Then, repeat the following commands GRN_NDELINFOS - 1 times.

load --table pat '[{"_key": 1}]'
delete pat --key 1

The last delete fails and the table breaks as follows:

delete pat --key 1
# [[0,0,0],false]
select pat
# [[0,0,0],[[[2],[["_id","UInt32"],["_key","UInt8"]]]]]
# expected: [[[1],[["_id","UInt32"],["_key","UInt8"]],[4,0]]]

The attached file is an example for GRN_NDELINFOS == 0x100.

issue-421.txt

$ mkdir /tmp/issue-421
$ groonga --file issue-421.txt -n /tmp/issue-421/db
...
[[0,1445418260.74575,1.1444091796875e-05],1]
[[0,1445418260.74577,9.05990600585938e-06],true]
[[0,1445418260.74578,1.1444091796875e-05],1]
[[0,1445418260.7458,8.82148742675781e-06],true]
[[0,1445418260.74582,1.12056732177734e-05],1]
[[0,1445418260.74584,8.58306884765625e-06],false]
[[0,1445418260.74586,0.000433921813964844],[[[2],[["_id","UInt32"],["_key","UInt8"]]]]]

[s-yata]

This bug has been fixed.
Also, a quick-fix patch of #420 is now not required.

[s-yata]

The latest grn_pat passes tests for bit-swapped keys and ShortText keys.
I could not find any problems in tests.

[s-yata]

I've added a unit test named test-patricia-trie-delete ( 376ddf4 ).