fmd/common/fmd_idspace.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright (c) 2004, 2010, Oracle and/or its affiliates. All rights reserved.
 */

#include <fmd_alloc.h>
#include <fmd_subr.h>
#include <fmd_conf.h>
#include <fmd_error.h>
#include <fmd_string.h>
#include <fmd_idspace.h>
#include <fmd.h>

fmd_idspace_t *
fmd_idspace_create(const char *name, id_t min, id_t max)
{
    fmd_idspace_t *ids = fmd_alloc(sizeof (fmd_idspace_t), FMD_SLEEP);
    uint_t ids_avg, ids_max, hashlen, hashmax;

    /*
     * Dynamically size the hash table bucket array based on the desired
     * chain length.  We hash by indexing on the low-order bits.
     * Do not permit the hash bucket array to exceed a reasonable size.
     */
    ASSERT(min >= 0 && max >= 0);
    ASSERT(max >= min);

    (void) fmd_conf_getprop(fmd.d_conf, "ids.avg", &ids_avg);
    (void) fmd_conf_getprop(fmd.d_conf, "ids.max", &ids_max);

    hashmax = max - min + 1;
    hashlen = 1 << fls(hashmax / ids_avg);
    if (hashlen > ids_max)
        hashlen = ids_max;

    (void) strlcpy(ids->ids_name, name, sizeof (ids->ids_name));
    (void) pthread_mutex_init(&ids->ids_lock, NULL);
    (void) pthread_cond_init(&ids->ids_cv, NULL);

    ids->ids_hash = fmd_zalloc(sizeof (void *) * hashlen, FMD_SLEEP);
    ids->ids_hashlen = hashlen;
    ids->ids_refs = 0;
    ids->ids_nextid = min - 1;
    ids->ids_minid = min;
    ids->ids_maxid = max;
    ids->ids_count = 0;

    return (ids);
}

void
fmd_idspace_destroy(fmd_idspace_t *ids)
{
    fmd_idelem_t *ide, *nde;
    uint_t i;

    (void) pthread_mutex_lock(&ids->ids_lock);

    while (ids->ids_refs != 0)
        (void) pthread_cond_wait(&ids->ids_cv, &ids->ids_lock);

    for (i = 0; i < ids->ids_hashlen; i++) {
        for (ide = ids->ids_hash[i]; ide != NULL; ide = nde) {
            nde = ide->ide_next;
            fmd_free(ide, sizeof (fmd_idelem_t));
        }
    }

    fmd_free(ids->ids_hash, sizeof (void *) * ids->ids_hashlen);
    fmd_free(ids, sizeof (fmd_idspace_t));
}

void
fmd_idspace_apply(fmd_idspace_t *ids,
    void (*func)(fmd_idspace_t *, id_t, void *), void *arg)
{
    fmd_idelem_t *ide;
    id_t *ida, *idp;
    uint_t i, count;

    (void) pthread_mutex_lock(&ids->ids_lock);
    count = ids->ids_count;
    ida = idp = fmd_alloc(sizeof (id_t) * count, FMD_SLEEP);

    for (i = 0; i < ids->ids_hashlen; i++) {
        for (ide = ids->ids_hash[i]; ide != NULL; ide = ide->ide_next)
            *idp++ = ide->ide_id;
    }

    ASSERT(idp == ida + count);
    (void) pthread_mutex_unlock(&ids->ids_lock);

    for (i = 0; i < count; i++)
        func(ids, ida[i], arg);

    fmd_free(ida, sizeof (id_t) * count);
}

static fmd_idelem_t *
fmd_idspace_lookup(fmd_idspace_t *ids, id_t id)
{
    fmd_idelem_t *ide;

    ASSERT(MUTEX_HELD(&ids->ids_lock));
    ide = ids->ids_hash[id & (ids->ids_hashlen - 1)];

    for (; ide != NULL; ide = ide->ide_next) {
        if (ide->ide_id == id)
            break;
    }

    return (ide);
}

void *
fmd_idspace_getspecific(fmd_idspace_t *ids, id_t id)
{
    fmd_idelem_t *ide;
    void *data;

    (void) pthread_mutex_lock(&ids->ids_lock);
    ide = fmd_idspace_lookup(ids, id);
    data = ide ? ide->ide_data : NULL;
    (void) pthread_mutex_unlock(&ids->ids_lock);

    return (data);
}

void
fmd_idspace_setspecific(fmd_idspace_t *ids, id_t id, void *data)
{
    fmd_idelem_t *ide;

    (void) pthread_mutex_lock(&ids->ids_lock);

    while (ids->ids_refs != 0)
        (void) pthread_cond_wait(&ids->ids_cv, &ids->ids_lock);

    if ((ide = fmd_idspace_lookup(ids, id)) == NULL) {
        fmd_panic("idspace %p (%s) does not contain id %ld",
            (void *)ids, ids->ids_name, id);
    }

    ide->ide_data = data;
    (void) pthread_mutex_unlock(&ids->ids_lock);
}

int
fmd_idspace_contains(fmd_idspace_t *ids, id_t id)
{
    fmd_idelem_t *ide;

    (void) pthread_mutex_lock(&ids->ids_lock);
    ide = fmd_idspace_lookup(ids, id);
    (void) pthread_mutex_unlock(&ids->ids_lock);

    return (ide != NULL);
}

int
fmd_idspace_valid(fmd_idspace_t *ids, id_t id)
{
    return (id >= ids->ids_minid && id <= ids->ids_maxid);
}

static id_t
fmd_idspace_xalloc_locked(fmd_idspace_t *ids, id_t id, void *data)
{
    fmd_idelem_t *ide;
    uint_t h;

    if (id < ids->ids_minid || id > ids->ids_maxid) {
        fmd_panic("%ld out of range [%ld .. %ld] for idspace %p (%s)\n",
            id, ids->ids_minid, ids->ids_maxid,
            (void *)ids, ids->ids_name);
    }

    if (fmd_idspace_lookup(ids, id) != NULL)
        return (fmd_set_errno(EALREADY));

    ide = fmd_alloc(sizeof (fmd_idelem_t), FMD_SLEEP);
    h = id & (ids->ids_hashlen - 1);

    ide->ide_next = ids->ids_hash[h];
    ide->ide_data = data;
    ide->ide_id = id;

    ids->ids_hash[h] = ide;
    ids->ids_count++;

    return (id);
}

id_t
fmd_idspace_xalloc(fmd_idspace_t *ids, id_t id, void *data)
{
    (void) pthread_mutex_lock(&ids->ids_lock);
    id = fmd_idspace_xalloc_locked(ids, id, data);
    (void) pthread_mutex_unlock(&ids->ids_lock);
    return (id);
}

static id_t
fmd_idspace_alloc_locked(fmd_idspace_t *ids, void *data)
{
    id_t id;

    ASSERT(MUTEX_HELD(&ids->ids_lock));

    if (ids->ids_count == ids->ids_maxid - ids->ids_minid + 1)
        return (fmd_set_errno(ENOSPC));

    do {
        if (++ids->ids_nextid > ids->ids_maxid)
            ids->ids_nextid = ids->ids_minid;
        id = ids->ids_nextid;
    } while (fmd_idspace_xalloc_locked(ids, id, data) != id);

    return (id);
}

id_t
fmd_idspace_alloc(fmd_idspace_t *ids, void *data)
{
    id_t id;

    (void) pthread_mutex_lock(&ids->ids_lock);
    id = fmd_idspace_alloc_locked(ids, data);
    (void) pthread_mutex_unlock(&ids->ids_lock);

    return (id);
}

/*
 * For the moment, we use a simple but slow implementation: reset ids_nextid to
 * the minimum id and search in order from there.  If this becomes performance
 * sensitive we can maintain a freelist of the unallocated identifiers, etc.
 */
id_t
fmd_idspace_alloc_min(fmd_idspace_t *ids, void *data)
{
    id_t id;

    (void) pthread_mutex_lock(&ids->ids_lock);
    ids->ids_nextid = ids->ids_minid - 1;
    id = fmd_idspace_alloc_locked(ids, data);
    (void) pthread_mutex_unlock(&ids->ids_lock);

    return (id);
}

void *
fmd_idspace_free(fmd_idspace_t *ids, id_t id)
{
    fmd_idelem_t *ide, **pp;
    void *data;

    (void) pthread_mutex_lock(&ids->ids_lock);
    pp = &ids->ids_hash[id & (ids->ids_hashlen - 1)];

    for (ide = *pp; ide != NULL; ide = ide->ide_next) {
        if (ide->ide_id != id)
            pp = &ide->ide_next;
        else
            break;
    }

    if (ide == NULL) {
        (void) pthread_mutex_unlock(&ids->ids_lock);
        return (NULL);
    }

    data = ide->ide_data;
    *pp = ide->ide_next;
    fmd_free(ide, sizeof (fmd_idelem_t));

    ASSERT(ids->ids_count != 0);
    ids->ids_count--;

    (void) pthread_mutex_unlock(&ids->ids_lock);
    return (data);
}

/*
 * Retrieve the id-specific data for the specified id and place a hold on the
 * id so that it cannot be or deleted until fmd_idspace_rele(ids, id) is
 * called.  For simplicity, we now use a single global reference count for all
 * holds.  If this feature needs to be used in a place where there is high
 * contention between holders and deleters, the implementation can be modified
 * to use either a per-hash-bucket or a per-id-element condition variable.
 */
void *
fmd_idspace_hold(fmd_idspace_t *ids, id_t id)
{
    fmd_idelem_t *ide;
    void *data = NULL;

    (void) pthread_mutex_lock(&ids->ids_lock);

    if ((ide = fmd_idspace_lookup(ids, id)) != NULL) {
        ids->ids_refs++;
        ASSERT(ids->ids_refs != 0);
        data = ide->ide_data;
        ASSERT(data != NULL);
    }

    (void) pthread_mutex_unlock(&ids->ids_lock);
    return (data);
}

void
fmd_idspace_rele(fmd_idspace_t *ids, id_t id)
{
    (void) pthread_mutex_lock(&ids->ids_lock);

    ASSERT(fmd_idspace_lookup(ids, id) != NULL);
    ASSERT(ids->ids_refs != 0);
    ids->ids_refs--;

    (void) pthread_cond_broadcast(&ids->ids_cv);
    (void) pthread_mutex_unlock(&ids->ids_lock);
}