|
/**
|
|
* Copyright © 2019, Oracle and/or its affiliates. All rights reserved.
|
|
*
|
|
* Licensed under the Universal Permissive License v 1.0 as shown at
|
|
* http://oss.oracle.com/licenses/upl
|
|
*
|
|
*/
|
|
/* Maintain a set of inodes */
|
|
#include "inodemap.h"
|
|
#include "malloc.h"
|
|
#include <assert.h>
|
|
#include <stdbool.h>
|
|
#include <stdint.h>
|
|
#include <string.h>
|
|
#include <stdio.h>
|
|
|
|
struct entry {
|
|
bool valid;
|
|
dev_t dev;
|
|
ino_t inode;
|
|
void *value;
|
|
};
|
|
|
|
struct inodemap {
|
|
size_t n_entries;
|
|
size_t hash_size;
|
|
struct entry *entries;
|
|
};
|
|
|
|
struct inodemap *mk_inodemap(void) {
|
|
size_t initial_hash_size = 2;
|
|
struct inodemap *MALLOC(result);
|
|
struct entry *MALLOC_N(entries, initial_hash_size);
|
|
*result = (struct inodemap){.n_entries = 0,
|
|
.hash_size = initial_hash_size,
|
|
.entries = entries};
|
|
for (size_t i = 0; i < initial_hash_size; i++) {
|
|
entries[i].valid = false;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
struct inodemap *inodemap_destroy(struct inodemap *is,
|
|
void (*destroy_value_fun)(void*)) {
|
|
assert(is);
|
|
for (size_t i = 0; i < is->hash_size; i++) {
|
|
if (is->entries[i].valid) {
|
|
destroy_value_fun(is->entries[i].value);
|
|
}
|
|
}
|
|
free(is->entries);
|
|
free(is);
|
|
return NULL;
|
|
}
|
|
|
|
static const uint64_t FNV_OFFSET = 14695981039346656037ull;
|
|
static const uint64_t FNV_PRIME = 1099511628211ull;
|
|
|
|
static uint64_t hash128(uint64_t a, uint64_t b) {
|
|
uint64_t hash = FNV_OFFSET;
|
|
for (size_t i = 0; i < 8; i++) {
|
|
hash ^= (a>>(i*8))&0xFFul;
|
|
hash *= FNV_PRIME;
|
|
hash ^= (b>>(i*8))&0xFFul;
|
|
hash *= FNV_PRIME;
|
|
}
|
|
return hash;
|
|
}
|
|
|
|
uint64_t inodemap_hash(dev_t dev, ino_t inode) {
|
|
return hash128(dev, inode);
|
|
}
|
|
|
|
static struct entry *
|
|
find_entry(struct entry *entries, size_t hash_size, dev_t dev, ino_t ino) {
|
|
// hash_size must be a power of two
|
|
assert(0 == (hash_size & (hash_size - 1)));
|
|
uint64_t h = inodemap_hash(dev, ino);
|
|
for (size_t i = 0; i < hash_size; i++) {
|
|
size_t idx = ((size_t)h + i) & (hash_size-1);
|
|
if (!entries[idx].valid
|
|
|| (entries[idx].dev == dev && entries[idx].inode == ino)) {
|
|
return entries+idx;
|
|
}
|
|
}
|
|
assert(0);
|
|
}
|
|
|
|
bool
|
|
inodemap_lookup(struct inodemap *im,
|
|
dev_t dev,
|
|
ino_t inode,
|
|
void const **value) {
|
|
struct entry *e = find_entry(im->entries, im->hash_size, dev, inode);
|
|
if (e->valid) {
|
|
*value = e->value;
|
|
}
|
|
return e->valid;
|
|
|
|
}
|
|
|
|
static void
|
|
maybe_grow_table(struct inodemap *im) {
|
|
if (im->n_entries * 2 < im->hash_size) {
|
|
return;
|
|
}
|
|
size_t new_size = 2*im->hash_size;
|
|
struct entry *MALLOC_N(new_entries, new_size);
|
|
for (size_t i = 0; i < new_size; i++) {
|
|
new_entries[i].valid = false;
|
|
}
|
|
for (size_t i = 0; i < im->hash_size; i++) {
|
|
if (im->entries[i].valid) {
|
|
struct entry *e = find_entry(new_entries, new_size,
|
|
im->entries[i].dev,
|
|
im->entries[i].inode);
|
|
assert(!e->valid);
|
|
*e = im->entries[i];
|
|
}
|
|
}
|
|
free(im->entries);
|
|
im->entries = new_entries;
|
|
im->hash_size = new_size;
|
|
}
|
|
|
|
static void
|
|
inodemap_print(struct inodemap *im, FILE *f)
|
|
__attribute__((unused));
|
|
static void
|
|
inodemap_print(struct inodemap *im, FILE *f) {
|
|
fprintf(f, "Inode map %p. n_entries=%zd hash_size=%zd\n",
|
|
im, im->n_entries, im->hash_size);
|
|
for (size_t i = 0 ; i < im->hash_size; i++) {
|
|
if (im->entries[i].valid) {
|
|
fprintf(f, "%zd: %lu,%lu -> %p\n", i,
|
|
im->entries[i].dev, im->entries[i].inode,
|
|
im->entries[i].value);
|
|
} else {
|
|
fprintf(f, "%zd: empty\n", i);
|
|
}
|
|
}
|
|
}
|
|
|
|
void
|
|
inodemap_insert(struct inodemap *im, dev_t dev, ino_t inode, void *value) {
|
|
maybe_grow_table(im);
|
|
// Now we know we have space.
|
|
struct entry *e = find_entry(im->entries, im->hash_size, dev, inode);
|
|
assert(!e->valid);
|
|
*e = (struct entry){.valid = true,
|
|
.dev = dev,
|
|
.inode = inode,
|
|
.value = value};
|
|
im->n_entries++;
|
|
}
|