path: root/usr/src/common/refhash/refhash.c

/*
 * This file and its contents are supplied under the terms of the
 * Common Development and Distribution License ("CDDL"), version 1.0.
 * You may only use this file in accordance with the terms of version
 * 1.0 of the CDDL.
 *
 * A full copy of the text of the CDDL should have accompanied this
 * source.  A copy of the CDDL is also available via the Internet at
 * http://www.illumos.org/license/CDDL.
 */

/*
 * Copyright (c) 2019, Joyent, Inc.
 */

#include <sys/refhash.h>
#include <sys/types.h>
#include <sys/list.h>
#include <sys/debug.h>

#ifdef _KERNEL
#include <sys/sysmacros.h>
#include <sys/ddi.h>
#include <sys/kmem.h>
#define	REFHASH_ALLOC	kmem_alloc
#define	REFHASH_ZALLOC	kmem_zalloc
#define	REFHASH_FREE	kmem_free
#else
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

extern void *refhash_alloc(size_t, int);
extern void *refhash_zalloc(size_t, int);
extern void refhash_free(void *, size_t);

/*
 * We use weak symbols to an application can supply its own
 * versions of these (e.g. to be able to use umem_alloc(..., UMEM_NOFAIL)).
 *
 * While ideally we would simply create a hard dependency on libumem, this would
 * preclude the use of librefhash by libraries that are linked into aribitrary
 * programs where forcing the use of libumem may not be desirable.
 */
#pragma weak refhash_alloc = _refhash_alloc
static void *_refhash_alloc(size_t, int);

#pragma weak refhash_zalloc = _refhash_zalloc
static void *_refhash_zalloc(size_t, int);

#pragma weak refhash_free = _refhash_free
static void _refhash_free(void *, size_t);

#define	REFHASH_ALLOC	refhash_alloc
#define	REFHASH_ZALLOC	refhash_zalloc
#define	REFHASH_FREE	refhash_free
#endif

#define	RHL_F_DEAD	0x01

#define	obj_to_link(_h, _o)	\
	((refhash_link_t *)(((char *)(_o)) + (_h)->rh_link_off))
#define	link_to_obj(_h, _l)	\
	((void *)(((char *)(_l)) - (_h)->rh_link_off))
#define	obj_to_tag(_h, _o)	\
	((void *)(((char *)(_o)) + (_h)->rh_tag_off))

refhash_t *
refhash_create(uint_t bucket_count, refhash_hash_f hash,
    refhash_cmp_f cmp, refhash_dtor_f dtor, size_t obj_size, size_t link_off,
    size_t tag_off, int km_flags)
{
	refhash_t *hp;
	uint_t i;

	hp = REFHASH_ALLOC(sizeof (refhash_t), km_flags);
	if (hp == NULL)
		return (NULL);
	hp->rh_buckets = REFHASH_ZALLOC(bucket_count * sizeof (list_t),
	    km_flags);
	if (hp->rh_buckets == NULL) {
		REFHASH_FREE(hp, sizeof (refhash_t));
		return (NULL);
	}
	hp->rh_bucket_count = bucket_count;

	for (i = 0; i < bucket_count; i++) {
		list_create(&hp->rh_buckets[i], sizeof (refhash_link_t),
		    offsetof(refhash_link_t, rhl_chain_link));
	}
	list_create(&hp->rh_objs, sizeof (refhash_link_t),
	    offsetof(refhash_link_t, rhl_global_link));

	hp->rh_obj_size = obj_size;
	hp->rh_link_off = link_off;
	hp->rh_tag_off = tag_off;
	hp->rh_hash = hash;
	hp->rh_cmp = cmp;
	hp->rh_dtor = dtor;

	return (hp);
}

void
refhash_destroy(refhash_t *hp)
{
	ASSERT(list_is_empty(&hp->rh_objs));

	REFHASH_FREE(hp->rh_buckets, hp->rh_bucket_count * sizeof (list_t));
	REFHASH_FREE(hp, sizeof (refhash_t));
}

void
refhash_insert(refhash_t *hp, void *op)
{
	uint_t bucket;
	refhash_link_t *lp = obj_to_link(hp, op);

	bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count;
	list_link_init(&lp->rhl_chain_link);
	list_link_init(&lp->rhl_global_link);
	lp->rhl_flags = 0;
	lp->rhl_refcnt = 0;
	list_insert_tail(&hp->rh_buckets[bucket], lp);
	list_insert_tail(&hp->rh_objs, lp);
}

static void
refhash_delete(refhash_t *hp, void *op)
{
	refhash_link_t *lp = obj_to_link(hp, op);
	uint_t bucket;

	bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count;
	list_remove(&hp->rh_buckets[bucket], lp);
	list_remove(&hp->rh_objs, lp);
	hp->rh_dtor(op);
}

void
refhash_remove(refhash_t *hp, void *op)
{
	refhash_link_t *lp = obj_to_link(hp, op);

	if (lp->rhl_refcnt > 0) {
		lp->rhl_flags |= RHL_F_DEAD;
	} else {
		refhash_delete(hp, op);
	}
}

void *
refhash_lookup(refhash_t *hp, const void *tp)
{
	uint_t bucket;
	refhash_link_t *lp;
	void *op;

	bucket = hp->rh_hash(tp) % hp->rh_bucket_count;
	for (lp = list_head(&hp->rh_buckets[bucket]); lp != NULL;
	    lp = list_next(&hp->rh_buckets[bucket], lp)) {
		op = link_to_obj(hp, lp);
		if (hp->rh_cmp(obj_to_tag(hp, op), tp) == 0 &&
		    !(lp->rhl_flags & RHL_F_DEAD)) {
			return (op);
		}
	}

	return (NULL);
}

void *
refhash_linear_search(refhash_t *hp, refhash_eval_f eval, void *arg)
{
	void *op;
	refhash_link_t *lp;

	for (lp = list_head(&hp->rh_objs); lp != NULL;
	    lp = list_next(&hp->rh_objs, lp)) {
		op = link_to_obj(hp, lp);
		if (eval(op, arg) == 0)
			return (op);
	}

	return (NULL);
}

void
refhash_hold(refhash_t *hp, void *op)
{
	refhash_link_t *lp = obj_to_link(hp, op);

	++lp->rhl_refcnt;
}

void
refhash_rele(refhash_t *hp, void *op)
{
	refhash_link_t *lp = obj_to_link(hp, op);

	ASSERT(lp->rhl_refcnt > 0);

	if (--lp->rhl_refcnt == 0 && (lp->rhl_flags & RHL_F_DEAD))
		refhash_remove(hp, op);
}

void *
refhash_first(refhash_t *hp)
{
	refhash_link_t *lp;

	lp = list_head(&hp->rh_objs);
	if (lp == NULL)
		return (NULL);

	++lp->rhl_refcnt;

	return (link_to_obj(hp, lp));
}

void *
refhash_next(refhash_t *hp, void *op)
{
	refhash_link_t *lp;

	lp = obj_to_link(hp, op);
	while ((lp = list_next(&hp->rh_objs, lp)) != NULL) {
		if (!(lp->rhl_flags & RHL_F_DEAD))
			break;
	}

	refhash_rele(hp, op);
	if (lp == NULL)
		return (NULL);

	++lp->rhl_refcnt;

	return (link_to_obj(hp, lp));
}

boolean_t
refhash_obj_valid(refhash_t *hp, const void *op)
{
	/* LINTED - E_ARG_INCOMPATIBLE_WITH_ARG_L */
	const refhash_link_t *lp = obj_to_link(hp, op);

	return ((lp->rhl_flags & RHL_F_DEAD) != 0);
}

#ifndef _KERNEL

void *
_refhash_alloc(size_t len, int flag __unused)
{
	return (malloc(len));
}

void *
_refhash_zalloc(size_t len, int flag __unused)
{
	return (calloc(1, len));
}

void
_refhash_free(void *ptr, size_t len __unused)
{
	free(ptr);
}

#endif