/*
* Copyright (C) 2011 Red Hat, Inc.
*
* This file is released under the GPL.
*/
#include "dm-btree-internal.h"
#include "dm-space-map.h"
#include "dm-transaction-manager.h"
#include <linux/export.h>
#include <linux/device-mapper.h>
#define DM_MSG_PREFIX "btree"
/*----------------------------------------------------------------
* Array manipulation
*--------------------------------------------------------------*/
static void memcpy_disk(void *dest, const void *src, size_t len)
__dm_written_to_disk(src)
{
memcpy(dest, src, len);
__dm_unbless_for_disk(src);
}
static void array_insert(void *base, size_t elt_size, unsigned nr_elts,
unsigned index, void *elt)
__dm_written_to_disk(elt)
{
if (index < nr_elts)
memmove(base + (elt_size * (index + 1)),
base + (elt_size * index),
(nr_elts - index) * elt_size);
memcpy_disk(base + (elt_size * index), elt, elt_size);
}
/*----------------------------------------------------------------*/
/* makes the assumption that no two keys are the same. */
static int bsearch(struct btree_node *n, uint64_t key, int want_hi)
{
int lo = -1, hi = le32_to_cpu(n->header.nr_entries);
while (hi - lo > 1) {
int mid = lo + ((hi - lo) / 2);
uint64_t mid_key = le64_to_cpu(n->keys[mid]);
if (mid_key == key)
return mid;
if (mid_key < key)
lo = mid;
else
hi = mid;
}
return want_hi ? hi : lo;
}
int lower_bound(struct btree_node *n, uint64_t key)
{
return bsearch(n, key, 0);
}
void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
struct dm_btree_value_type *vt)
{
unsigned i;
uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);
if (le32_to_cpu(n->header.flags) & INTERNAL_NODE)
for (i = 0; i < nr_entries; i++)
dm_tm_inc(tm, value64(n, i));
else if (vt->inc)
for (i = 0; i < nr_entries; i++)
vt->inc(vt->context, value_ptr(n, i));
}
static int insert_at(size_t value_size, struct btree_node *node, unsigned index,
uint64_t key, void *value)
__dm_written_to_disk(value)
{
uint32_t nr_entries = le32_to_cpu(node->header.nr_entries);
__le64 key_le = cpu_to_le64(key);
if (index > nr_entries ||
index >= le32_to_cpu(node->header.max_entries)) {
DMERR("too many entries in btree node for insert");
__dm_unbless_for_disk(value);
return -ENOMEM;
}
__dm_bless_for_disk(&key_le);
array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le);
array_insert(value_base(node), value_size, nr_entries, index, value);
node->header.nr_entries = cpu_to_le32(nr_entries + 1);
return 0;
}
/*----------------------------------------------------------------*/
/*
* We want 3n entries (for some n). This works more nicely for repeated
* insert remove loops than (2n + 1).
*/
static uint32_t calc_max_entries(size_t value_size, size_t block_size)
{
uint32_t total, n;
size_t elt_size = sizeof(uint64_t) + value_size; /* key + value */
block_size -= sizeof(struct node_header);
total = block_size / elt_size;
n = total / 3; /* rounds down */
return 3 * n;
}
int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root)
{
int r;
struct dm_block *b;
struct btree_node *n;
size_t block_size;
uint32_t max_entries;
r = new_block(info, &b);
if (r < 0)
return r;
block_size = dm_bm_block_size(dm_tm_get_bm(info->tm));
max_entries = calc_max_entries(info->value_type.size, block_size);
n = dm_block_data(b);
memset(n, 0, block_size);
n->header.flags = cpu_to_le32(LEAF_NODE);
n->header.nr_entries = cpu_to_le32(0);
n->header.max_entries = cpu_to_le32(max_entries);
n->header.value_size = cpu_to_le32(info->value_type.size);
*root