1450N/A/*
1450N/A * Copyright (c) 2006, 2013, Oracle and/or its affiliates. All rights reserved.
1450N/A *
1450N/A * Permission is hereby granted, free of charge, to any person obtaining a
1450N/A * copy of this software and associated documentation files (the "Software"),
1450N/A * to deal in the Software without restriction, including without limitation
1450N/A * the rights to use, copy, modify, merge, publish, distribute, sublicense,
1450N/A * and/or sell copies of the Software, and to permit persons to whom the
1450N/A * Software is furnished to do so, subject to the following conditions:
1450N/A *
1450N/A * The above copyright notice and this permission notice (including the next
1450N/A * paragraph) shall be included in all copies or substantial portions of the
1450N/A * Software.
1450N/A *
1450N/A * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1450N/A * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1450N/A * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
1450N/A * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1450N/A * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
1450N/A * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
1450N/A * DEALINGS IN THE SOFTWARE.
1450N/A */
1450N/A
1450N/A/*
1450N/A * Copyright (c) 2012 Intel Corporation. All rights reserved.
1450N/A */
1450N/A
1450N/A#include <sys/kmem.h>
1450N/A#include "drmP.h"
1450N/A#include "drm_linux_list.h"
1450N/A#include "drm_sun_idr.h"
1450N/A
1450N/Astatic inline int
1450N/Afr_isfull(struct idr_free_id_range *range)
1450N/A{
1450N/A return range->min_unused_id >= range->end;
1450N/A}
1450N/A
1450N/Astatic struct idr_free_id_range *
1450N/Afr_new(int start)
1450N/A{
1450N/A struct idr_free_id_range *this;
1450N/A
1450N/A this = kmem_zalloc(sizeof(struct idr_free_id_range), KM_SLEEP);
1450N/A this->start = start;
1450N/A this->end = 0x7fffffff;
1450N/A this->min_unused_id = start;
1450N/A
1450N/A return this;
1450N/A}
1450N/A
1450N/Astatic struct idr_free_id_range *
1450N/Afr_destroy(struct idr_free_id_range *range)
1450N/A{
1450N/A struct idr_free_id_range *ret;
1450N/A struct idr_free_id *id;
1450N/A
1450N/A while (range->free_ids) {
1450N/A id = range->free_ids;
1450N/A range->free_ids = range->free_ids->next;
1450N/A kmem_free(id, sizeof(struct idr_free_id));
1450N/A }
1450N/A
1450N/A ret = range->next;
1450N/A kmem_free(range, sizeof(struct idr_free_id_range));
1450N/A
1450N/A return ret;
1450N/A}
1450N/A
1450N/Astatic struct idr_free_id_range *
1450N/Afr_get(struct idr_free_id_range *list, int start)
1450N/A{
1450N/A struct idr_free_id_range *entry = list;
1450N/A
1450N/A while (entry && (entry->start != start))
1450N/A entry = entry->next;
1450N/A return entry;
1450N/A}
1450N/A
1450N/Astatic struct idr_free_id_range *
1450N/Afr_insert(struct idr_free_id_range *list, int start)
1450N/A{
1450N/A struct idr_free_id_range *prev = list;
1450N/A struct idr_free_id_range *n;
1450N/A struct idr_free_id *id, **pid;
1450N/A
1450N/A while (prev->next && prev->next->start < start)
1450N/A prev = prev->next;
1450N/A
1450N/A n = fr_new(start);
1450N/A
1450N/A /* link the new range */
1450N/A n->next = prev->next;
1450N/A prev->next = n;
1450N/A
1450N/A /* change the end of the ranges */
1450N/A prev->end = start;
1450N/A if (n->next)
1450N/A n->end = n->next->start;
1450N/A
1450N/A if (fr_isfull(prev)) {
1450N/A /* change the min_unused_id of the ranges */
1450N/A n->min_unused_id = prev->min_unused_id;
1450N/A prev->min_unused_id = start;
1450N/A
1450N/A /* link free id to the new range */
1450N/A pid = &prev->free_ids;
1450N/A while (*pid) {
1450N/A if ((*pid)->id < start) {
1450N/A pid = &((*pid)->next);
1450N/A continue;
1450N/A }
1450N/A id = *pid;
1450N/A
1450N/A /* remove from the prev range */
1450N/A (*pid) = id->next;
1450N/A
1450N/A /* link to the new range */
1450N/A id->next = n->free_ids;
1450N/A n->free_ids = id;
1450N/A }
1450N/A }
1450N/A
1450N/A return n;
1450N/A}
1450N/A
1450N/Astatic int
1450N/Aidr_compare(const void *a, const void *b)
1450N/A{
1450N/A const struct idr_used_id *pa = a;
1450N/A const struct idr_used_id *pb = b;
1450N/A
1450N/A if (pa->id < pb->id)
1450N/A return (-1);
1450N/A else if (pa->id > pb->id)
1450N/A return (1);
1450N/A else
1450N/A return (0);
1450N/A}
1450N/A
1450N/Astatic int
1450N/Aidr_get_free_id_in_range(struct idr_free_id_range* range)
1450N/A{
1450N/A struct idr_free_id *idp;
1450N/A int id;
1450N/A
1450N/A if (range->free_ids) {
1450N/A idp = range->free_ids;
1450N/A range->free_ids = idp->next;
1450N/A id = idp->id;
1450N/A kmem_free(idp, sizeof(struct idr_free_id));
1450N/A return (id);
1450N/A }
1450N/A
1450N/A if (!fr_isfull(range)) {
1450N/A id = range->min_unused_id;
1450N/A range->min_unused_id++;
1450N/A return (id);
1450N/A }
1450N/A
1450N/A return (-1);
1450N/A}
1450N/A
1450N/Avoid
1450N/Aidr_init(struct idr *idrp)
1450N/A{
1450N/A avl_create(&idrp->used_ids, idr_compare, sizeof(struct idr_used_id),
1450N/A offsetof(struct idr_used_id, link));
1450N/A
1450N/A idrp->free_id_ranges = fr_new(0);
1450N/A mutex_init(&idrp->lock, NULL, MUTEX_DRIVER, NULL);
1450N/A}
1450N/A
1450N/Aint
1450N/Aidr_get_new_above(struct idr *idrp, void *obj, int start, int *newid)
1450N/A{
1450N/A struct idr_used_id *used;
1450N/A struct idr_free_id_range *range;
1450N/A int id;
1450N/A
1450N/A if (start < 0)
1450N/A return (-EINVAL);
1450N/A mutex_enter(&idrp->lock);
1450N/A range = fr_get(idrp->free_id_ranges, start);
1450N/A if (!range)
1450N/A range = fr_insert(idrp->free_id_ranges, start);
1450N/A
1450N/A while (range) {
1450N/A id = idr_get_free_id_in_range(range);
1450N/A if (id >= 0)
1450N/A goto got_id;
1450N/A range = range->next;
1450N/A }
1450N/A mutex_exit(&idrp->lock);
1450N/A return (-1);
1450N/A
1450N/Agot_id:
1450N/A used = kmem_alloc(sizeof(struct idr_used_id), KM_NOSLEEP);
1450N/A if (!used) {
1450N/A mutex_exit(&idrp->lock);
1450N/A return (-ENOMEM);
1450N/A }
1450N/A
1450N/A used->id = id;
1450N/A used->obj = obj;
1450N/A avl_add(&idrp->used_ids, used);
1450N/A
1450N/A *newid = id;
1450N/A mutex_exit(&idrp->lock);
1450N/A return (0);
1450N/A}
1450N/A
1450N/Astatic struct idr_used_id *
1450N/Aidr_find_used_id(struct idr *idrp, uint32_t id)
1450N/A{
1450N/A struct idr_used_id match;
1450N/A struct idr_used_id *ret;
1450N/A
1450N/A match.id = id;
1450N/A
1450N/A ret = avl_find(&idrp->used_ids, &match, NULL);
1450N/A if (ret) {
1450N/A return (ret);
1450N/A }
1450N/A
1450N/A return (NULL);
1450N/A}
1450N/A
1450N/Avoid *
1450N/Aidr_find(struct idr *idrp, uint32_t id)
1450N/A{
1450N/A struct idr_used_id *ret;
1450N/A
1450N/A mutex_enter(&idrp->lock);
1450N/A ret = idr_find_used_id(idrp, id);
1450N/A if (ret) {
1450N/A mutex_exit(&idrp->lock);
1450N/A return (ret->obj);
1450N/A }
1450N/A
1450N/A mutex_exit(&idrp->lock);
1450N/A return (NULL);
1450N/A}
1450N/A
1450N/Aint
1450N/Aidr_remove(struct idr *idrp, uint32_t id)
1450N/A{
1450N/A struct idr_free_id_range *range;
1450N/A struct idr_used_id *ide;
1450N/A struct idr_free_id *fid;
1450N/A
1450N/A mutex_enter(&idrp->lock);
1450N/A ide = idr_find_used_id(idrp, id);
1450N/A if (!ide) {
1450N/A mutex_exit(&idrp->lock);
1450N/A return (-EINVAL);
1450N/A }
1450N/A
1450N/A fid = kmem_alloc(sizeof(struct idr_free_id), KM_NOSLEEP);
1450N/A if (!fid) {
1450N/A mutex_exit(&idrp->lock);
1450N/A return (-ENOMEM);
1450N/A }
1450N/A fid->id = id;
1450N/A
1450N/A
1450N/A range = idrp->free_id_ranges;
1450N/A while (range->end <= id)
1450N/A range = range->next;
1450N/A fid->next = range->free_ids;
1450N/A range->free_ids = fid;
1450N/A avl_remove(&idrp->used_ids, ide);
1450N/A kmem_free(ide, sizeof (struct idr_used_id));
1450N/A mutex_exit(&idrp->lock);
1450N/A
1450N/A return (0);
1450N/A}
1450N/A
1450N/Avoid
1450N/Aidr_remove_all(struct idr *idrp)
1450N/A{
1450N/A idr_destroy(idrp);
1450N/A idr_init(idrp);
1450N/A}
1450N/A
1450N/Avoid *
1450N/Aidr_replace(struct idr *idrp, void *obj, uint32_t id)
1450N/A{
1450N/A struct idr_used_id *ide;
1450N/A void *ret;
1450N/A mutex_enter(&idrp->lock);
1450N/A ide = idr_find_used_id(idrp, id);
1450N/A if (!ide) {
1450N/A mutex_exit(&idrp->lock);
1450N/A return (void*)(-EINVAL);
1450N/A }
1450N/A
1450N/A ret = ide->obj;
1450N/A ide->obj = obj;
1450N/A mutex_exit(&idrp->lock);
1450N/A return ret;
1450N/A}
1450N/A
1450N/Aint
1450N/Aidr_for_each(struct idr *idrp, int (*fn)(int id, void *p, void *data), void *data)
1450N/A{
1450N/A struct idr_used_id *ide;
1450N/A int ret = 0;
1450N/A
1450N/A ide = avl_first(&idrp->used_ids);
1450N/A while (ide) {
1450N/A ret = fn(ide->id, ide->obj, data);
1450N/A if (ret)
1450N/A break;
1450N/A
1450N/A /* idr node has been removed by fn */
1450N/A ide = AVL_NEXT(&idrp->used_ids, ide);
1450N/A }
1450N/A
1450N/A return ret;
1450N/A}
1450N/A
1450N/Aint
1450N/A/* LINTED */
1450N/Aidr_pre_get(struct idr *idrp, int flag) {
1450N/A return (-1);
1450N/A}
1450N/A
1450N/Avoid
1450N/Aidr_destroy(struct idr *idrp)
1450N/A{
1450N/A struct idr_free_id_range *range;
1450N/A struct idr_used_id *ide;
1450N/A void *cookie = NULL;
1450N/A
1450N/A while (ide = avl_destroy_nodes(&idrp->used_ids, &cookie))
1450N/A kmem_free(ide, sizeof (struct idr_used_id));
1450N/A avl_destroy(&idrp->used_ids);
1450N/A
1450N/A range = idrp->free_id_ranges;
1450N/A while (range)
1450N/A range = fr_destroy(range);
1450N/A idrp->free_id_ranges = NULL;
1450N/A
1450N/A mutex_destroy(&idrp->lock);
1450N/A}
1450N/A
1450N/A
1450N/Auint32_t fr_id = 0;
1450N/Auint32_t fr_time = 0;
1450N/A
1450N/Aint
1450N/A/* LINTED */
1450N/Aidr_list_pre_get(struct idr_list *head, int flag) {
1450N/A return (-1);
1450N/A}
1450N/A
1450N/Avoid
1450N/Aidr_list_init(struct idr_list *head)
1450N/A{
1450N/A struct idr_list *entry;
1450N/A /* HASH for accelerate */
1450N/A entry = kmem_zalloc(DRM_GEM_OBJIDR_HASHNODE
1450N/A * sizeof (struct idr_list), KM_SLEEP);
1450N/A head->next = entry;
1450N/A for (int i = 0; i < DRM_GEM_OBJIDR_HASHNODE; i++) {
1450N/A INIT_LIST_HEAD(&entry[i]);
1450N/A }
1450N/A}
1450N/A
1450N/Aint
1450N/Aidr_list_get_new_above(struct idr_list *head,
1450N/A void *obj,
1450N/A int *handlep)
1450N/A{
1450N/A struct idr_list *entry, *node, *temp;
1450N/A int key, id;
1450N/A void *obj_temp;
1450N/A
1450N/A ASSERT(fr_id <= 0x7fffffff);
1450N/A id = ++fr_id;
1450N/A if (id == 0x7fffffff) {
1450N/A fr_time++;
1450N/A id = fr_id = 1;
1450N/A }
1450N/A if (fr_time) {
1450N/A /* find available id */
1450N/A do {
1450N/A obj_temp = idr_list_find(head, id);
1450N/A } while ((obj_temp != NULL) && (++id < 0x7fffffff));
1450N/A if (id < 0x7fffffff) {
1450N/A fr_id = id;
1450N/A } else {
1450N/A fr_id = 0;
1450N/A return (-EAGAIN);
1450N/A }
1450N/A }
1450N/A entry = kmem_zalloc(sizeof (*entry), KM_NOSLEEP);
1450N/A if (entry == NULL)
1450N/A return (-1);
1450N/A ASSERT(id <= 0x7fffffff);
1450N/A key = id % DRM_GEM_OBJIDR_HASHNODE;
1450N/A entry->obj = obj;
1450N/A entry->handle = id;
1450N/A
1450N/A /* list add */
1450N/A node = &head->next[key];
1450N/A temp = node->next;
1450N/A entry->prev = node;
1450N/A entry->next = node->next;
1450N/A temp->prev = entry;
1450N/A node->next = entry;
1450N/A
1450N/A *handlep = id;
1450N/A return (0);
1450N/A}
1450N/A
1450N/Avoid *
1450N/Aidr_list_find(struct idr_list *head,
1450N/A uint32_t name)
1450N/A{
1450N/A struct idr_list *entry;
1450N/A int key;
1450N/A key = name % DRM_GEM_OBJIDR_HASHNODE;
1450N/A
1450N/A list_for_each(entry, &head->next[key]) {
1450N/A if (entry->handle == name)
1450N/A return (entry->obj);
1450N/A }
1450N/A return (NULL);
1450N/A}
1450N/A
1450N/A#define list_del_idr_list_node(ptr) \
1450N/Ado { \
1450N/A struct idr_list *n_node = (ptr)->next; \
1450N/A struct idr_list *p_node = (ptr)->prev; \
1450N/A n_node->prev = (ptr)->prev; \
1450N/A p_node->next = (ptr)->next; \
1450N/A (ptr)->prev = NULL; \
1450N/A (ptr)->next = NULL; \
1450N/A} while (*"\0")
1450N/A
1450N/A
1450N/Aint
1450N/Aidr_list_remove(struct idr_list *head,
1450N/A uint32_t name)
1450N/A{
1450N/A struct idr_list *entry, *temp;
1450N/A int key;
1450N/A key = name % DRM_GEM_OBJIDR_HASHNODE;
1450N/A
1450N/A list_for_each_safe(entry, temp, &head->next[key]) {
1450N/A if (entry->handle == name) {
1450N/A list_del_idr_list_node(entry);
1450N/A kmem_free(entry, sizeof (*entry));
1450N/A return (0);
1450N/A }
1450N/A }
1450N/A DRM_ERROR("Failed to remove the object %d", name);
1450N/A return (-1);
1450N/A}
1450N/A
1450N/Avoid
1450N/Aidr_list_free(struct idr_list *head)
1450N/A{
1450N/A struct idr_list *entry, *temp;
1450N/A for (int key = 0; key < DRM_GEM_OBJIDR_HASHNODE; key++) {
1450N/A list_for_each_safe(entry, temp, &head->next[key]) {
1450N/A list_del_idr_list_node(entry);
1450N/A kmem_free(entry, sizeof (*entry));
1450N/A }
1450N/A }
1450N/A kmem_free(head->next,
1450N/A DRM_GEM_OBJIDR_HASHNODE * sizeof (struct idr_list));
1450N/A head->next = NULL;
1450N/A}
1450N/A
1450N/Aint
1450N/Aidr_list_empty(struct idr_list *head)
1450N/A{
1450N/A int empty;
1450N/A for (int key = 0; key < DRM_GEM_OBJIDR_HASHNODE; key++) {
1450N/A empty = list_empty(&(head)->next[key]);
1450N/A if (!empty)
1450N/A return (empty);
1450N/A }
1450N/A return (1);
1450N/A}