/*
* 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 */
int bch_keylist_realloc(struct keylist *l, int nptrs, struct cache_set *c)
{
size_t oldsize = bch_keylist_nkeys(l);
size_t newsize = oldsize + 2 + nptrs;
uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p;
uint64_t *new_keys;
/* 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_keys = krealloc(old_keys, sizeof(uint64_t) * newsize, GFP_NOIO);
if (!new_keys)
return -ENOMEM;
if (!old_keys)
memcpy(new_keys, l->inline_keys, sizeof(uint64_t) * oldsize);
l->keys_p = new_keys;
l->top_p = new_keys + oldsize;
return 0;
}
struct bkey *bch_keylist_pop(struct keylist *l)
{
struct bkey *k = l->keys;
if (k == l->top)
return NULL;
while (bkey_next(k) != l->top)
k = bkey_next(k);
return l->top = k;
}
void bch_keylist_pop_front(struct keylist *l)
{
l->top_p -= bkey_u64s(l->keys);
memmove(l->keys,
bkey_next(l->keys),
bch_keylist_bytes(l));
}
/* Pointer validation */
static bool __ptr_invalid(struct cache_set *c, const struct bkey *k)
{
unsigned i;
for (i = 0; i < KEY_PTRS(k); i++)
if (ptr_available(c, k, i)) {
struct cache *ca = PTR_CACHE(c, k, i);
size_t bucket = PTR_BUCKET_NR(c, k, i);
size_t r = bucket_remainder(c, PTR_OFFSET(k, i));
if (