/*
* Code for working with individual keys, and sorted sets of keys with in a
* btree node
*
* Copyright 2012 Google, Inc.
*/
#include "bcache.h"
#include "btree.h"
#include "debug.h"
#include <linux/random.h>
#include <linux/prefetch.h>
/* Keylists */
void bch_keylist_copy(struct keylist *dest, struct keylist *src)
{
*dest = *src;
if (src->list == src->d) {
size_t n = (uint64_t *) src->top - src->d;
dest->top = (struct bkey *) &dest->d[n];
dest->list = dest->d;
}
}
int bch_keylist_realloc(struct keylist *l, int nptrs, struct cache_set *c)
{
unsigned oldsize = (uint64_t *) l->top - l->list;
unsigned newsize = oldsize + 2 + nptrs;
uint64_t *new;
/* The journalling code doesn't handle the case where the keys to insert
* is bigger than an empty write: If we just return -ENOMEM here,
* bio_insert() and bio_invalidate() will insert the keys created so far
* and finish the rest when the keylist is empty.
*/
if (newsize * sizeof(uint64_t) > block_bytes(c) - sizeof(struct jset))
return -ENOMEM;
newsize = roundup_pow_of_two(newsize);
if (newsize <= KEYLIST_INLINE ||
roundup_pow_of_two(oldsize) == newsize)
return 0;
new = krealloc(l->list == l->d ? NULL : l->list,
sizeof(uint64_t) * newsize, GFP_NOIO);
if (!new)
return -ENOMEM;
if (l->list == l->d)
memcpy(new, l->list, sizeof(uint64_t) * KEYLIST_INLINE);
l->list = new;
l->top = (struct bkey *) (&l->list[oldsize]);
return 0;
}
struct bkey *bch_keylist_pop(struct keylist *l)
{
struct bkey *k = l->bottom;
if (k == l->top)
return NULL;
while (bkey_next(k) != l->top)
k = bkey_next(k);
return l->top = k;
}
/* Pointer validation */
bool __bch_ptr_invalid(struct cache_set *c, int level, const struct bkey *k)
{
unsigned i;
char buf[80];
if (level && (!KEY_PTR