1 /*        $NetBSD: drm_hashtab.c,v 1.3 2021/12/18 23:44:57 riastradh Exp $      */
2 
3 /**************************************************************************
4  *
5  * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
6  * All Rights Reserved.
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining a
9  * copy of this software and associated documentation files (the
10  * "Software"), to deal in the Software without restriction, including
11  * without limitation the rights to use, copy, modify, merge, publish,
12  * distribute, sub license, and/or sell copies of the Software, and to
13  * permit persons to whom the Software is furnished to do so, subject to
14  * the following conditions:
15  *
16  * The above copyright notice and this permission notice (including the
17  * next paragraph) shall be included in all copies or substantial portions
18  * of the Software.
19  *
20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
23  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
24  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
25  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
26  * USE OR OTHER DEALINGS IN THE SOFTWARE.
27  *
28  *
29  **************************************************************************/
30 /*
31  * Simple open hash tab implementation.
32  *
33  * Authors:
34  * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
35  */
36 
37 #include <sys/cdefs.h>
38 __KERNEL_RCSID(0, "$NetBSD: drm_hashtab.c,v 1.3 2021/12/18 23:44:57 riastradh Exp $");
39 
40 #include <linux/export.h>
41 #include <linux/hash.h>
42 #include <linux/mm.h>
43 #include <linux/rculist.h>
44 #include <linux/slab.h>
45 #include <linux/vmalloc.h>
46 
47 #include <drm/drm_hashtab.h>
48 #include <drm/drm_print.h>
49 
drm_ht_create(struct drm_open_hash * ht,unsigned int order)50 int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
51 {
52           unsigned int size = 1 << order;
53 
54           ht->order = order;
55           ht->table = NULL;
56           if (size <= PAGE_SIZE / sizeof(*ht->table))
57                     ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);
58           else
59                     ht->table = vzalloc(array_size(size, sizeof(*ht->table)));
60           if (!ht->table) {
61                     DRM_ERROR("Out of memory for hash table\n");
62                     return -ENOMEM;
63           }
64           return 0;
65 }
66 EXPORT_SYMBOL(drm_ht_create);
67 
drm_ht_verbose_list(struct drm_open_hash * ht,unsigned long key)68 void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
69 {
70           struct drm_hash_item *entry;
71           struct hlist_head *h_list;
72           unsigned int hashed_key;
73           int count = 0;
74 
75           hashed_key = hash_long(key, ht->order);
76           DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
77           h_list = &ht->table[hashed_key];
78           hlist_for_each_entry(entry, h_list, head)
79                     DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
80 }
81 
drm_ht_find_key(struct drm_open_hash * ht,unsigned long key)82 static struct hlist_node *drm_ht_find_key(struct drm_open_hash *ht,
83                                                     unsigned long key)
84 {
85           struct drm_hash_item *entry;
86           struct hlist_head *h_list;
87           unsigned int hashed_key;
88 
89           hashed_key = hash_long(key, ht->order);
90           h_list = &ht->table[hashed_key];
91           hlist_for_each_entry(entry, h_list, head) {
92                     if (entry->key == key)
93                               return &entry->head;
94                     if (entry->key > key)
95                               break;
96           }
97           return NULL;
98 }
99 
drm_ht_find_key_rcu(struct drm_open_hash * ht,unsigned long key)100 static struct hlist_node *drm_ht_find_key_rcu(struct drm_open_hash *ht,
101                                                         unsigned long key)
102 {
103           struct drm_hash_item *entry;
104           struct hlist_head *h_list;
105           unsigned int hashed_key;
106 
107           hashed_key = hash_long(key, ht->order);
108           h_list = &ht->table[hashed_key];
109           hlist_for_each_entry_rcu(entry, h_list, head) {
110                     if (entry->key == key)
111                               return &entry->head;
112                     if (entry->key > key)
113                               break;
114           }
115           return NULL;
116 }
117 
drm_ht_insert_item(struct drm_open_hash * ht,struct drm_hash_item * item)118 int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
119 {
120           struct drm_hash_item *entry;
121           struct hlist_head *h_list;
122           struct hlist_node *parent;
123           unsigned int hashed_key;
124           unsigned long key = item->key;
125 
126           hashed_key = hash_long(key, ht->order);
127           h_list = &ht->table[hashed_key];
128           parent = NULL;
129           hlist_for_each_entry(entry, h_list, head) {
130                     if (entry->key == key)
131                               return -EINVAL;
132                     if (entry->key > key)
133                               break;
134                     parent = &entry->head;
135           }
136           if (parent) {
137                     hlist_add_behind_rcu(&item->head, parent);
138           } else {
139                     hlist_add_head_rcu(&item->head, h_list);
140           }
141           return 0;
142 }
143 EXPORT_SYMBOL(drm_ht_insert_item);
144 
145 /*
146  * Just insert an item and return any "bits" bit key that hasn't been
147  * used before.
148  */
drm_ht_just_insert_please(struct drm_open_hash * ht,struct drm_hash_item * item,unsigned long seed,int bits,int shift,unsigned long add)149 int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
150                                     unsigned long seed, int bits, int shift,
151                                     unsigned long add)
152 {
153           int ret;
154           unsigned long mask = (1UL << bits) - 1;
155           unsigned long first, unshifted_key;
156 
157           unshifted_key = hash_long(seed, bits);
158           first = unshifted_key;
159           do {
160                     item->key = (unshifted_key << shift) + add;
161                     ret = drm_ht_insert_item(ht, item);
162                     if (ret)
163                               unshifted_key = (unshifted_key + 1) & mask;
164           } while(ret && (unshifted_key != first));
165 
166           if (ret) {
167                     DRM_ERROR("Available key bit space exhausted\n");
168                     return -EINVAL;
169           }
170           return 0;
171 }
172 EXPORT_SYMBOL(drm_ht_just_insert_please);
173 
drm_ht_find_item(struct drm_open_hash * ht,unsigned long key,struct drm_hash_item ** item)174 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
175                          struct drm_hash_item **item)
176 {
177           struct hlist_node *list;
178 
179           list = drm_ht_find_key_rcu(ht, key);
180           if (!list)
181                     return -EINVAL;
182 
183           *item = hlist_entry(list, struct drm_hash_item, head);
184           return 0;
185 }
186 EXPORT_SYMBOL(drm_ht_find_item);
187 
drm_ht_remove_key(struct drm_open_hash * ht,unsigned long key)188 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
189 {
190           struct hlist_node *list;
191 
192           list = drm_ht_find_key(ht, key);
193           if (list) {
194                     hlist_del_init_rcu(list);
195                     return 0;
196           }
197           return -EINVAL;
198 }
199 
drm_ht_remove_item(struct drm_open_hash * ht,struct drm_hash_item * item)200 int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
201 {
202           hlist_del_init_rcu(&item->head);
203           return 0;
204 }
205 EXPORT_SYMBOL(drm_ht_remove_item);
206 
drm_ht_remove(struct drm_open_hash * ht)207 void drm_ht_remove(struct drm_open_hash *ht)
208 {
209           if (ht->table) {
210                     kvfree(ht->table);
211                     ht->table = NULL;
212           }
213 }
214 EXPORT_SYMBOL(drm_ht_remove);
215