Orange Pi5 kernel

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