drm/src/drm_sun_idr.c

/*
 * Copyright (c) 2006, 2013, Oracle and/or its affiliates. All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

/*
 * Copyright (c) 2012 Intel Corporation.  All rights reserved.
 */

#include <sys/kmem.h>
#include "drmP.h"
#include "drm_linux_list.h"
#include "drm_sun_idr.h"

static inline int
fr_isfull(struct idr_free_id_range *range)
{
    return range->min_unused_id >= range->end;
}

static struct idr_free_id_range *
fr_new(int start)
{
    struct idr_free_id_range *this;

    this = kmem_zalloc(sizeof(struct idr_free_id_range), KM_SLEEP);
    this->start = start;
    this->end = 0x7fffffff;
    this->min_unused_id = start;

    return this;
}

static struct idr_free_id_range *
fr_destroy(struct idr_free_id_range *range)
{
    struct idr_free_id_range *ret;
    struct idr_free_id *id;

    while (range->free_ids) {
        id = range->free_ids;
        range->free_ids = range->free_ids->next;
        kmem_free(id, sizeof(struct idr_free_id));
    }

    ret = range->next;
    kmem_free(range, sizeof(struct idr_free_id_range));

    return ret;
}

static struct idr_free_id_range *
fr_get(struct idr_free_id_range *list, int start)
{
    struct idr_free_id_range *entry = list;

    while (entry && (entry->start != start))
        entry = entry->next;
    return entry;
}

static struct idr_free_id_range *
fr_insert(struct idr_free_id_range *list, int start)
{
    struct idr_free_id_range *prev = list;
    struct idr_free_id_range *n;
    struct idr_free_id *id, **pid;

    while (prev->next && prev->next->start < start)
        prev = prev->next;

    n = fr_new(start);

    /* link the new range */
    n->next = prev->next;
    prev->next = n;

    /* change the end of the ranges */
    prev->end = start;
    if (n->next)
        n->end = n->next->start;

    if (fr_isfull(prev)) {
        /* change the min_unused_id of the ranges */
        n->min_unused_id = prev->min_unused_id;
        prev->min_unused_id = start;

        /* link free id to the new range */
        pid = &prev->free_ids;
        while (*pid) {
            if ((*pid)->id < start) {
                pid = &((*pid)->next);
                continue;
            }
            id = *pid;

            /* remove from the prev range */
            (*pid) = id->next;

            /* link to the new range */
            id->next = n->free_ids;
            n->free_ids = id;
        }
    }

    return n;
}

static int
idr_compare(const void *a, const void *b)
{
    const struct idr_used_id *pa = a;
    const struct idr_used_id *pb = b;

    if (pa->id < pb->id)
        return (-1);
    else if (pa->id > pb->id)
        return (1);
    else
        return (0);
}

static int
idr_get_free_id_in_range(struct idr_free_id_range* range)
{
    struct idr_free_id *idp;
    int id;

    if (range->free_ids) {
        idp = range->free_ids;
        range->free_ids = idp->next;
        id = idp->id;
        kmem_free(idp, sizeof(struct idr_free_id));
        return (id);
    }

    if (!fr_isfull(range)) {
        id = range->min_unused_id;
        range->min_unused_id++;
        return (id);
    }

    return (-1);
}

void
idr_init(struct idr *idrp)
{
    avl_create(&idrp->used_ids, idr_compare, sizeof(struct idr_used_id),
        offsetof(struct idr_used_id, link));

    idrp->free_id_ranges = fr_new(0);
    mutex_init(&idrp->lock, NULL, MUTEX_DRIVER, NULL);
}

int
idr_get_new_above(struct idr *idrp, void *obj, int start, int *newid)
{
    struct idr_used_id *used;
    struct idr_free_id_range *range;
    int id;

    if (start < 0)
        return (-EINVAL);
    mutex_enter(&idrp->lock);
    range = fr_get(idrp->free_id_ranges, start);
    if (!range)
        range = fr_insert(idrp->free_id_ranges, start);

    while (range) {
        id = idr_get_free_id_in_range(range);
        if (id >= 0)
            goto got_id;
        range = range->next;
    }
    mutex_exit(&idrp->lock);
    return (-1);

got_id:
    used = kmem_alloc(sizeof(struct idr_used_id), KM_NOSLEEP);
    if (!used) {
        mutex_exit(&idrp->lock);
        return (-ENOMEM);
    }

    used->id = id;
    used->obj = obj;
    avl_add(&idrp->used_ids, used);

    *newid = id;
    mutex_exit(&idrp->lock);
    return (0);
}

static struct idr_used_id *
idr_find_used_id(struct idr *idrp, uint32_t id)
{
    struct idr_used_id match;
    struct idr_used_id *ret;

    match.id = id;

    ret = avl_find(&idrp->used_ids, &match, NULL);
    if (ret) {
        return (ret);
    }

    return (NULL);
}

void *
idr_find(struct idr *idrp, uint32_t id)
{
    struct idr_used_id *ret;

    mutex_enter(&idrp->lock);
    ret = idr_find_used_id(idrp, id);
    if (ret) {
        mutex_exit(&idrp->lock);
        return (ret->obj);
    }

    mutex_exit(&idrp->lock);
    return (NULL);
}

int
idr_remove(struct idr *idrp, uint32_t id)
{
    struct idr_free_id_range *range;
    struct idr_used_id *ide;
    struct idr_free_id *fid;

    mutex_enter(&idrp->lock);
    ide = idr_find_used_id(idrp, id);
    if (!ide) {
        mutex_exit(&idrp->lock);
        return (-EINVAL);
    }

    fid = kmem_alloc(sizeof(struct idr_free_id), KM_NOSLEEP);
    if (!fid) {
        mutex_exit(&idrp->lock);
        return (-ENOMEM);
    }
    fid->id = id;


    range = idrp->free_id_ranges;
    while (range->end <= id)
        range = range->next;
    fid->next = range->free_ids;
    range->free_ids = fid;
    avl_remove(&idrp->used_ids, ide);
    kmem_free(ide, sizeof (struct idr_used_id));
    mutex_exit(&idrp->lock);

    return (0);
}

void
idr_remove_all(struct idr *idrp)
{
    idr_destroy(idrp);
    idr_init(idrp);
}

void *
idr_replace(struct idr *idrp, void *obj, uint32_t id)
{
    struct idr_used_id *ide;
    void *ret;
    mutex_enter(&idrp->lock);
    ide = idr_find_used_id(idrp, id);
    if (!ide) {
        mutex_exit(&idrp->lock);
        return (void*)(-EINVAL);
    }

    ret = ide->obj;
    ide->obj = obj;
    mutex_exit(&idrp->lock);
    return ret;
}

int
idr_for_each(struct idr *idrp, int (*fn)(int id, void *p, void *data), void *data)
{
    struct idr_used_id *ide;
    int ret = 0;

    ide = avl_first(&idrp->used_ids);
    while (ide) {
        ret = fn(ide->id, ide->obj, data);
        if (ret)
            break;

        /* idr node has been removed by fn */
        ide = AVL_NEXT(&idrp->used_ids, ide);
    }

    return ret;
}

int
/* LINTED */
idr_pre_get(struct idr *idrp, int flag) {
    return (-1);
}

void
idr_destroy(struct idr *idrp)
{
    struct idr_free_id_range *range;
    struct idr_used_id *ide;
    void *cookie = NULL;

    while (ide = avl_destroy_nodes(&idrp->used_ids, &cookie))
        kmem_free(ide, sizeof (struct idr_used_id));
    avl_destroy(&idrp->used_ids);

    range = idrp->free_id_ranges;
    while (range)
        range = fr_destroy(range);
    idrp->free_id_ranges = NULL;

    mutex_destroy(&idrp->lock);
}


uint32_t fr_id = 0;
uint32_t fr_time = 0;

int
/* LINTED */
idr_list_pre_get(struct idr_list *head, int flag) {
    return (-1);
}

void
idr_list_init(struct idr_list  *head)
{
    struct idr_list  *entry;
    /* HASH for accelerate */
    entry = kmem_zalloc(DRM_GEM_OBJIDR_HASHNODE
            * sizeof (struct idr_list), KM_SLEEP);
    head->next = entry;
    for (int i = 0; i < DRM_GEM_OBJIDR_HASHNODE; i++) {
        INIT_LIST_HEAD(&entry[i]);
    }
}

int
idr_list_get_new_above(struct idr_list *head,
            void *obj,
            int *handlep)
{
    struct idr_list  *entry, *node, *temp;
    int key, id;
    void *obj_temp;

    ASSERT(fr_id <= 0x7fffffff);
    id = ++fr_id;
    if (id == 0x7fffffff) {
        fr_time++;
        id = fr_id = 1;
    }
    if (fr_time) {
        /* find available id */
        do {
            obj_temp = idr_list_find(head, id);
        } while ((obj_temp != NULL) && (++id < 0x7fffffff));
        if (id < 0x7fffffff) {
            fr_id = id;
        } else {
            fr_id = 0;
            return (-EAGAIN);
        }
    }
    entry = kmem_zalloc(sizeof (*entry), KM_NOSLEEP);
    if (entry == NULL)
        return (-1);
    ASSERT(id <= 0x7fffffff);
    key = id % DRM_GEM_OBJIDR_HASHNODE;
    entry->obj = obj;
    entry->handle = id;

    /* list add */
    node = &head->next[key];
    temp = node->next;
    entry->prev = node;
    entry->next = node->next;
    temp->prev = entry;
    node->next = entry;

    *handlep = id;
    return (0);
}

void *
idr_list_find(struct idr_list   *head,
        uint32_t    name)
{
    struct idr_list  *entry;
    int key;
    key = name % DRM_GEM_OBJIDR_HASHNODE;

    list_for_each(entry, &head->next[key]) {
        if (entry->handle == name)
            return (entry->obj);
    }
    return (NULL);
}

#define list_del_idr_list_node(ptr)         \
do {                            \
    struct idr_list *n_node = (ptr)->next;      \
    struct idr_list *p_node = (ptr)->prev;      \
    n_node->prev = (ptr)->prev;         \
    p_node->next = (ptr)->next;         \
    (ptr)->prev = NULL;             \
    (ptr)->next = NULL;             \
} while (*"\0")


int
idr_list_remove(struct idr_list *head,
        uint32_t    name)
{
    struct idr_list  *entry, *temp;
    int key;
    key = name % DRM_GEM_OBJIDR_HASHNODE;

    list_for_each_safe(entry, temp, &head->next[key]) {
        if (entry->handle == name) {
            list_del_idr_list_node(entry);
            kmem_free(entry, sizeof (*entry));
            return (0);
        }
    }
    DRM_ERROR("Failed to remove the object %d", name);
    return (-1);
}

void
idr_list_free(struct idr_list   *head)
{
    struct idr_list  *entry, *temp;
    for (int key = 0; key < DRM_GEM_OBJIDR_HASHNODE; key++) {
        list_for_each_safe(entry, temp, &head->next[key]) {
            list_del_idr_list_node(entry);
            kmem_free(entry, sizeof (*entry));
        }
    }
    kmem_free(head->next,
            DRM_GEM_OBJIDR_HASHNODE * sizeof (struct idr_list));
    head->next = NULL;
}

int
idr_list_empty(struct idr_list  *head)
{
    int empty;
    for (int key = 0; key < DRM_GEM_OBJIDR_HASHNODE; key++) {
        empty = list_empty(&(head)->next[key]);
        if (!empty)
            return (empty);
    }
    return (1);
}