1  /* SPDX-License-Identifier: GPL-2.0 */
2  /*
3   * A hash table (hashtab) maintains associations between
4   * key values and datum values.  The type of the key values
5   * and the type of the datum values is arbitrary.  The
6   * functions for hash computation and key comparison are
7   * provided by the creator of the table.
8   *
9   * Author : Stephen Smalley, <stephen.smalley.work@gmail.com>
10   */
11  
12  #ifndef _SS_HASHTAB_H_
13  #define _SS_HASHTAB_H_
14  
15  #include <linux/types.h>
16  #include <linux/errno.h>
17  #include <linux/sched.h>
18  
19  #define HASHTAB_MAX_NODES U32_MAX
20  
21  struct hashtab_key_params {
22  	u32 (*hash)(const void *key); /* hash func */
23  	int (*cmp)(const void *key1, const void *key2); /* comparison func */
24  };
25  
26  struct hashtab_node {
27  	void *key;
28  	void *datum;
29  	struct hashtab_node *next;
30  };
31  
32  struct hashtab {
33  	struct hashtab_node **htable; /* hash table */
34  	u32 size; /* number of slots in hash table */
35  	u32 nel; /* number of elements in hash table */
36  };
37  
38  struct hashtab_info {
39  	u32 slots_used;
40  	u32 max_chain_len;
41  	u64 chain2_len_sum;
42  };
43  
44  /*
45   * Initializes a new hash table with the specified characteristics.
46   *
47   * Returns -ENOMEM if insufficient space is available or 0 otherwise.
48   */
49  int hashtab_init(struct hashtab *h, u32 nel_hint);
50  
51  int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, void *key,
52  		     void *datum);
53  
54  /*
55   * Inserts the specified (key, datum) pair into the specified hash table.
56   *
57   * Returns -ENOMEM on memory allocation error,
58   * -EEXIST if there is already an entry with the same key,
59   * -EINVAL for general errors or
60    0 otherwise.
61   */
hashtab_insert(struct hashtab * h,void * key,void * datum,struct hashtab_key_params key_params)62  static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
63  				 struct hashtab_key_params key_params)
64  {
65  	u32 hvalue;
66  	struct hashtab_node *prev, *cur;
67  
68  	cond_resched();
69  
70  	if (!h->size || h->nel == HASHTAB_MAX_NODES)
71  		return -EINVAL;
72  
73  	hvalue = key_params.hash(key) & (h->size - 1);
74  	prev = NULL;
75  	cur = h->htable[hvalue];
76  	while (cur) {
77  		int cmp = key_params.cmp(key, cur->key);
78  
79  		if (cmp == 0)
80  			return -EEXIST;
81  		if (cmp < 0)
82  			break;
83  		prev = cur;
84  		cur = cur->next;
85  	}
86  
87  	return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue], key,
88  				datum);
89  }
90  
91  /*
92   * Searches for the entry with the specified key in the hash table.
93   *
94   * Returns NULL if no entry has the specified key or
95   * the datum of the entry otherwise.
96   */
hashtab_search(struct hashtab * h,const void * key,struct hashtab_key_params key_params)97  static inline void *hashtab_search(struct hashtab *h, const void *key,
98  				   struct hashtab_key_params key_params)
99  {
100  	u32 hvalue;
101  	struct hashtab_node *cur;
102  
103  	if (!h->size)
104  		return NULL;
105  
106  	hvalue = key_params.hash(key) & (h->size - 1);
107  	cur = h->htable[hvalue];
108  	while (cur) {
109  		int cmp = key_params.cmp(key, cur->key);
110  
111  		if (cmp == 0)
112  			return cur->datum;
113  		if (cmp < 0)
114  			break;
115  		cur = cur->next;
116  	}
117  	return NULL;
118  }
119  
120  /*
121   * Destroys the specified hash table.
122   */
123  void hashtab_destroy(struct hashtab *h);
124  
125  /*
126   * Applies the specified apply function to (key,datum,args)
127   * for each entry in the specified hash table.
128   *
129   * The order in which the function is applied to the entries
130   * is dependent upon the internal structure of the hash table.
131   *
132   * If apply returns a non-zero status, then hashtab_map will cease
133   * iterating through the hash table and will propagate the error
134   * return to its caller.
135   */
136  int hashtab_map(struct hashtab *h, int (*apply)(void *k, void *d, void *args),
137  		void *args);
138  
139  int hashtab_duplicate(struct hashtab *new, const struct hashtab *orig,
140  		      int (*copy)(struct hashtab_node *new,
141  				  const struct hashtab_node *orig, void *args),
142  		      int (*destroy)(void *k, void *d, void *args), void *args);
143  
144  #ifdef CONFIG_SECURITY_SELINUX_DEBUG
145  /* Fill info with some hash table statistics */
146  void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
147  #else
hashtab_stat(struct hashtab * h,struct hashtab_info * info)148  static inline void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
149  {
150  	return;
151  }
152  #endif
153  
154  #endif /* _SS_HASHTAB_H */
155