Delete works

The delete operation would fail if the key was located outside of a leaf node (i.e. it was being used as a median.) This was the broken code:

        if pos > 0 && node.Values[pos-1].Key == index {
                // Found the delete value
                if node.Nodes != nil {
                        // Lost median, will balance
                        tree.balance(node, pos)
                }else{

The problem is that when I lost a median I just rebalanced two subtrees, resulting in no change. What was I thinking?

if pos > 0 && node.Values[pos-1].Key == index {
// Found the delete value
tree.Stats.Size--
if node.Nodes != nil {
// Lost median, must borrow
var remaining int
node.Values[pos-1], remaining =                                                             tree.borrow(node.Nodes[pos-1])
if remaining < (tree.N/2) {
tree.balance(node, pos-1)
}

The new code implements the borrow() routine. That operates similar to the del() routine except that it always descends down the right-most tree or value, returning the largest value in the subtree.

Better testing reveals broken delete...

The latest commit on GitHub has an updated test implementation. It's a big improvement over what I had before because it uses Go's map type as a reference implementation. First I created an interface "TreeLike" that defines the basic operations on a tree:

type Treelike interface {
Insert(uint64, interface{})
Fetch(uint64) interface{}
Delete(uint64)
Iterate() chan uint64
}

I know Iterate() is basically useless, it's still a work in progress. TreeLike is already implemented by Btree. Now I make a struct that implements checking. 

type BtreeTest struct {

test *testing.T

tree Treelike 

reference map[uint64] interface{}

}

The class contains a test so that I can testing.T.Fail() when a problem is detected. The TreeLike is kept in sync with the map[] by implementing methods that operate on both structures. This is the implementation of Insert():

func (self *BtreeTest) Insert(key uint64, value interface{}) {

self.reference[key] = value

self.tree.Insert(key, value)

}

The Insert() function does no checking. The Delete() function does:

func (self *BtreeTest) Delete(key uint64) {

delete(self.reference, key)

self.tree.Delete(key)

verify := self.tree.Fetch(key) 

if (verify != nil) {

self.test.Fail()

}

}

The struct BtreeTest itself implements TreeLike so any code that requires TreeLike can be easily instrumented to be testing code. Thanks to that I found a serious bug in Delete(). My delete function fails to delete values that are not stored in leaf nodes. I'm fixing it. 

Adding Persistence to Kali Linux on a USB Key

The official Kali Linux USB Live Install guide mentions how to partition your USB stick to add a persistence partition. The persistence partition is very useful because it give Kali state. The instructions are tell you how to do the procedure on a non-Kali Linux. What's the use in that.

Here's the procedure for adding persistence from within Kali Linux:

1. Figure out what the device your flash key is using. The 'df' command gave me this output:

root@kali:~# df
Filesystem     1K-blocks    Used Available Use% Mounted on
rootfs           2050320   39228   2011092   2% /
udev               10240       0     10240   0% /dev
tmpfs             410068     716    409352   1% /run
/dev/sdb1        2553376 2553376         0 100% /lib/live/mount/medium
/dev/loop0       2354304 2354304         0 100% /lib/live/mount/rootfs/filesystem.squashfs
tmpfs            2050320       0   2050320   0% /lib/live/mount/overlay
tmpfs            2050320       0   2050320   0% /lib/live/mount/overlay
aufs             2050320   39228   2011092   2% /
tmpfs               5120       0      5120   0% /run/lock
tmpfs             820120     224    819896   1% /run/shm

2. The flash device is /dev/sdb. Start gparted on /dev/sdb:

gparted /dev/sdb

 3. Your current partitioning scheme should look similar to this:



4. Proceed to format a new partition of your desired size to be used for persistence. In our example, we used all the remaining space available. Make sure the volume label of the newly created partition is persistence, and format it using the ext4 filesystem.

 

 

5. Once the process is complete, mount your persistence USB partition using the following commands:

mkdir /mnt/usb mount /dev/sdb2 /mnt/usb echo "/ union" >> /mnt/usb/persistence.conf umount /mnt/usb

 6. The default instructions make you add the "persistence" parameter to the kernel every time you want your persistent storage. That's cumbersome. Unfortunately we're stuck with that problem because the file that controls the bootup is on an ISO9660 filesystem, therefore it cannot be changed without re-imaging the key. Bummer.

Plug the USB stick into the computer you want to boot up. Make sure your BIOS is set to boot from your USB device. When the Kali Linux boot screen is displayed, select “Live boot” from the menu (don’t press enter), and press the tab button. This will allow you to edit the boot parameters. Add the word “persistence” to the end of the boot parameter line each time you want to mount your persistent storage.

Maybe I'll blog about how to fix that one day...