drm/vmwgfx/vmwgfx_hashtab.c

0001 /*
0002  * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
0003  * All Rights Reserved.
0004  *
0005  * Permission is hereby granted, free of charge, to any person obtaining a
0006  * copy of this software and associated documentation files (the
0007  * "Software"), to deal in the Software without restriction, including
0008  * without limitation the rights to use, copy, modify, merge, publish,
0009  * distribute, sub license, and/or sell copies of the Software, and to
0010  * permit persons to whom the Software is furnished to do so, subject to
0011  * the following conditions:
0012  *
0013  * The above copyright notice and this permission notice (including the
0014  * next paragraph) shall be included in all copies or substantial portions
0015  * of the Software.
0016  *
0017  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0018  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0019  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
0020  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
0021  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
0022  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
0023  * USE OR OTHER DEALINGS IN THE SOFTWARE.
0024  */
0025
0026 /*
0027  * Simple open hash tab implementation.
0028  *
0029  * Authors:
0030  * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
0031  */
0032
0033 #include <linux/export.h>
0034 #include <linux/hash.h>
0035 #include <linux/mm.h>
0036 #include <linux/rculist.h>
0037 #include <linux/slab.h>
0038 #include <linux/vmalloc.h>
0039
0040 #include <drm/drm_print.h>
0041
0042 #include "vmwgfx_hashtab.h"
0043
0044 int vmwgfx_ht_create(struct vmwgfx_open_hash *ht, unsigned int order)
0045 {
0046     unsigned int size = 1 << order;
0047
0048     ht->order = order;
0049     ht->table = NULL;
0050     if (size <= PAGE_SIZE / sizeof(*ht->table))
0051         ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);
0052     else
0053         ht->table = vzalloc(array_size(size, sizeof(*ht->table)));
0054     if (!ht->table) {
0055         DRM_ERROR("Out of memory for hash table\n");
0056         return -ENOMEM;
0057     }
0058     return 0;
0059 }
0060
0061 void vmwgfx_ht_verbose_list(struct vmwgfx_open_hash *ht, unsigned long key)
0062 {
0063     struct vmwgfx_hash_item *entry;
0064     struct hlist_head *h_list;
0065     unsigned int hashed_key;
0066     int count = 0;
0067
0068     hashed_key = hash_long(key, ht->order);
0069     DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
0070     h_list = &ht->table[hashed_key];
0071     hlist_for_each_entry(entry, h_list, head)
0072         DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
0073 }
0074
0075 static struct hlist_node *vmwgfx_ht_find_key(struct vmwgfx_open_hash *ht, unsigned long key)
0076 {
0077     struct vmwgfx_hash_item *entry;
0078     struct hlist_head *h_list;
0079     unsigned int hashed_key;
0080
0081     hashed_key = hash_long(key, ht->order);
0082     h_list = &ht->table[hashed_key];
0083     hlist_for_each_entry(entry, h_list, head) {
0084         if (entry->key == key)
0085             return &entry->head;
0086         if (entry->key > key)
0087             break;
0088     }
0089     return NULL;
0090 }
0091
0092 static struct hlist_node *vmwgfx_ht_find_key_rcu(struct vmwgfx_open_hash *ht, unsigned long key)
0093 {
0094     struct vmwgfx_hash_item *entry;
0095     struct hlist_head *h_list;
0096     unsigned int hashed_key;
0097
0098     hashed_key = hash_long(key, ht->order);
0099     h_list = &ht->table[hashed_key];
0100     hlist_for_each_entry_rcu(entry, h_list, head) {
0101         if (entry->key == key)
0102             return &entry->head;
0103         if (entry->key > key)
0104             break;
0105     }
0106     return NULL;
0107 }
0108
0109 int vmwgfx_ht_insert_item(struct vmwgfx_open_hash *ht, struct vmwgfx_hash_item *item)
0110 {
0111     struct vmwgfx_hash_item *entry;
0112     struct hlist_head *h_list;
0113     struct hlist_node *parent;
0114     unsigned int hashed_key;
0115     unsigned long key = item->key;
0116
0117     hashed_key = hash_long(key, ht->order);
0118     h_list = &ht->table[hashed_key];
0119     parent = NULL;
0120     hlist_for_each_entry(entry, h_list, head) {
0121         if (entry->key == key)
0122             return -EINVAL;
0123         if (entry->key > key)
0124             break;
0125         parent = &entry->head;
0126     }
0127     if (parent)
0128         hlist_add_behind_rcu(&item->head, parent);
0129     else
0130         hlist_add_head_rcu(&item->head, h_list);
0131     return 0;
0132 }
0133
0134 /*
0135  * Just insert an item and return any "bits" bit key that hasn't been
0136  * used before.
0137  */
0138 int vmwgfx_ht_just_insert_please(struct vmwgfx_open_hash *ht, struct vmwgfx_hash_item *item,
0139                  unsigned long seed, int bits, int shift,
0140                  unsigned long add)
0141 {
0142     int ret;
0143     unsigned long mask = (1UL << bits) - 1;
0144     unsigned long first, unshifted_key;
0145
0146     unshifted_key = hash_long(seed, bits);
0147     first = unshifted_key;
0148     do {
0149         item->key = (unshifted_key << shift) + add;
0150         ret = vmwgfx_ht_insert_item(ht, item);
0151         if (ret)
0152             unshifted_key = (unshifted_key + 1) & mask;
0153     } while (ret && (unshifted_key != first));
0154
0155     if (ret) {
0156         DRM_ERROR("Available key bit space exhausted\n");
0157         return -EINVAL;
0158     }
0159     return 0;
0160 }
0161
0162 int vmwgfx_ht_find_item(struct vmwgfx_open_hash *ht, unsigned long key,
0163             struct vmwgfx_hash_item **item)
0164 {
0165     struct hlist_node *list;
0166
0167     list = vmwgfx_ht_find_key_rcu(ht, key);
0168     if (!list)
0169         return -EINVAL;
0170
0171     *item = hlist_entry(list, struct vmwgfx_hash_item, head);
0172     return 0;
0173 }
0174
0175 int vmwgfx_ht_remove_key(struct vmwgfx_open_hash *ht, unsigned long key)
0176 {
0177     struct hlist_node *list;
0178
0179     list = vmwgfx_ht_find_key(ht, key);
0180     if (list) {
0181         hlist_del_init_rcu(list);
0182         return 0;
0183     }
0184     return -EINVAL;
0185 }
0186
0187 int vmwgfx_ht_remove_item(struct vmwgfx_open_hash *ht, struct vmwgfx_hash_item *item)
0188 {
0189     hlist_del_init_rcu(&item->head);
0190     return 0;
0191 }
0192
0193 void vmwgfx_ht_remove(struct vmwgfx_open_hash *ht)
0194 {
0195     if (ht->table) {
0196         kvfree(ht->table);
0197         ht->table = NULL;
0198     }
0199 }